gcc/gcov.c

   1 /* Gcov.c: prepend line execution counts and branch probabilities to a
   2    source file.
   3    Copyright (C) 1990, 91, 92, 93, 94, 96, 1997 Free Software Foundation, Inc.
   4    Contributed by James E. Wilson of Cygnus Support.
   5    Mangled by Bob Manson of Cygnus Support.
   6
   7 Gcov is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 Gcov is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Gcov; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21 /* ??? The code in final.c that produces the struct bb assumes that there is
  22    no padding between the fields.  This is not necessary true.  The current
  23    code can only be trusted if longs and pointers are the same size.  */
  24
  25 /* ??? No need to print an execution count on every line, could just print
  26    it on the first line of each block, and only print it on a subsequent
  27    line in the same block if the count changes.  */
  28
  29 /* ??? Print a list of the ten blocks with the highest execution counts,
  30    and list the line numbers corresponding to those blocks.  Also, perhaps
  31    list the line numbers with the highest execution counts, only printing
  32    the first if there are several which are all listed in the same block.  */
  33
  34 /* ??? Should have an option to print the number of basic blocks, and the
  35    percent of them that are covered.  */
  36
  37 /* ??? Does not correctly handle the case where two .bb files refer to the
  38    same included source file.  For example, if one has a short file containing
  39    only inline functions, which is then included in two other files, then
  40    there will be two .bb files which refer to the include file, but there
  41    is no way to get the total execution counts for the included file, can
  42    only get execution counts for one or the other of the including files.  */
  43
  44 #include "config.h"
  45 #include <stdio.h>
  46 #include "gansidecl.h"
  47 #include <sys/types.h>
  48 #include <sys/stat.h>
  49
  50 #ifdef HAVE_STDLIB_H
  51 #include <stdlib.h>
  52 #endif
  53
  54 #ifdef HAVE_STRING_H
  55 #include <string.h>
  56 #else
  57 #ifdef HAVE_STRINGS_H
  58 #include <strings.h>
  59 #endif
  60 #endif
  61
  62 #include "gcov-io.h"
  63
  64 #ifdef NEED_DECLARATION_RINDEX
  65 extern char *rindex ();
  66 #endif
  67
  68 /* The .bb file format consists of several lists of 4-byte integers
  69    which are the line numbers of each basic block in the file.  Each
  70    list is terminated by a zero.  These lists correspond to the basic
  71    blocks in the reconstructed program flow graph.
  72
  73    A line number of -1 indicates that a source file name (padded to a
  74    long boundary) follows.  The padded file name is followed by
  75    another -1 to make it easy to scan past file names.  A -2 indicates
  76    that a function name (padded to a long boundary) follows; the name
  77    is followed by another -2 to make it easy to scan past the function
  78    name.
  79
  80    The .bbg file contains enough info to enable gcov to reconstruct the
  81    program flow graph.  The first word is the number of basic blocks,
  82    the second word is the number of arcs, followed by the list of arcs
  83    (source bb, dest bb pairs), then a -1, then the number of instrumented
  84    arcs followed by the instrumented arcs, followed by another -1.  This
  85    is repeated for each function.
  86
  87    The .da file contains the execution count for each instrumented branch.
  88
  89    The .bb and .bbg files are created by giving GCC the -ftest-coverage option,
  90    and the .da files are created when an executable compiled with
  91    -fprofile-arcs is run.  */
  92
  93 /* The functions in this file for creating and solution program flow graphs
  94    are very similar to functions in the gcc source file profile.c.  */
  95
  96 char gcov_version_string[] = "GNU gcov version 1.5\n";
  97
  98 /* This is the size of the buffer used to read in source file lines.  */
  99
 100 #define STRING_SIZE 200
 101
 102 /* One copy of this structure is created for each source file mentioned in the
 103    .bb file.  */
 104
 105 struct sourcefile
 106 {
 107   char *name;
 108   int maxlineno;
 109   struct sourcefile *next;
 110 };
 111
 112 /* This points to the head of the sourcefile structure list.  */
 113
 114 struct sourcefile *sources;
 115
 116 /* One of these is dynamically created whenever we identify an arc in the
 117    function.  */
 118
 119 struct adj_list {
 120   int source;
 121   int target;
 122   int arc_count;
 123   unsigned int count_valid : 1;
 124   unsigned int on_tree : 1;
 125   unsigned int fake : 1;
 126   unsigned int fall_through : 1;
 127 #if 0
 128   /* Not needed for gcov, but defined in profile.c.  */
 129   rtx branch_insn;
 130 #endif
 131   struct adj_list *pred_next;
 132   struct adj_list *succ_next;
 133 };
 134
 135 /* Count the number of basic blocks, and create an array of these structures,
 136    one for each bb in the function.  */
 137
 138 struct bb_info {
 139   struct adj_list *succ;
 140   struct adj_list *pred;
 141   int succ_count;
 142   int pred_count;
 143   int exec_count;
 144   unsigned int count_valid : 1;
 145   unsigned int on_tree : 1;
 146 #if 0
 147   /* Not needed for gcov, but defined in profile.c.  */
 148   rtx first_insn;
 149 #endif
 150 };
 151
 152 /* When outputting branch probabilities, one of these structures is created
 153    for each branch/call.  */
 154
 155 struct arcdata
 156 {
 157   int prob;
 158   int call_insn;
 159   struct arcdata *next;
 160 };
 161
 162 /* Used to save the list of bb_graphs, one per function.  */
 163
 164 struct bb_info_list {
 165   /* Indexed by block number, holds the basic block graph for one function.  */
 166   struct bb_info *bb_graph;
 167   int num_blocks;
 168   struct bb_info_list *next;
 169 };
 170
 171 /* Holds a list of function basic block graphs.  */
 172
 173 static struct bb_info_list *bb_graph_list = 0;
 174
 175 /* Name and file pointer of the input file for the basic block graph.  */
 176
 177 static char *bbg_file_name;
 178 static FILE *bbg_file;
 179
 180 /* Name and file pointer of the input file for the arc count data.  */
 181
 182 static char *da_file_name;
 183 static FILE *da_file;
 184
 185 /* Name and file pointer of the input file for the basic block line counts.  */
 186
 187 static char *bb_file_name;
 188 static FILE *bb_file;
 189
 190 /* Holds the entire contents of the bb_file read into memory.  */
 191
 192 static char *bb_data;
 193
 194 /* Size of bb_data array in longs.  */
 195
 196 static long bb_data_size;
 197
 198 /* Name and file pointer of the output file.  */
 199
 200 static char *gcov_file_name;
 201 static FILE *gcov_file;
 202
 203 /* Name of the file mentioned on the command line.  */
 204
 205 static char *input_file_name = 0;
 206
 207 /* Output branch probabilities if true.  */
 208
 209 static int output_branch_probs = 0;
 210
 211 /* Output a gcov file if this is true.  This is on by default, and can
 212    be turned off by the -n option.  */
 213
 214 static int output_gcov_file = 1;
 215
 216 /* For included files, make the gcov output file name include the name of
 217    the input source file.  For example, if x.h is included in a.c, then the
 218    output file name is a.c.x.h.gcov instead of x.h.gcov.  This works only
 219    when a single source file is specified.  */
 220
 221 static int output_long_names = 0;
 222
 223 /* Output summary info for each function.  */
 224
 225 static int output_function_summary = 0;
 226
 227 /* Object directory file prefix.  This is the directory where .bb and .bbg
 228    files are looked for, if non-zero.  */
 229
 230 static char *object_directory = 0;
 231
 232 /* Forward declarations.  */
 233 static void process_args ();
 234 static void open_files ();
 235 static void read_files ();
 236 static void scan_for_source_files ();
 237 static void output_data ();
 238 char * xmalloc ();
 239
 240 int
 241 main (argc, argv)
 242      int argc;
 243      char **argv;
 244 {
 245   process_args (argc, argv);
 246
 247   open_files ();
 248
 249   read_files ();
 250
 251   scan_for_source_files ();
 252
 253   output_data ();
 254
 255   return 0;
 256 }
 257
 258 char *
 259 xmalloc (size)
 260      unsigned size;
 261 {
 262   register char *value = (char *) malloc (size);
 263   if (value == 0)
 264     {
 265       fprintf (stderr, "error: virtual memory exhausted");
 266       exit (FATAL_EXIT_CODE);
 267     }
 268   return value;
 269 }
 270
 271 /* More 'friendly' abort that prints the line and file.
 272    config.h can #define abort fancy_abort if you like that sort of thing.  */
 273
 274 void
 275 fancy_abort ()
 276 {
 277   fprintf (stderr, "Internal gcc abort.\n");
 278   exit (FATAL_EXIT_CODE);
 279 }
 280 \f
 281 /* Print a usage message and exit.  */
 282
 283 static void
 284 print_usage ()
 285 {
 286   fprintf (stderr, "gcov [-b] [-v] [-n] [-l] [-f] [-o OBJDIR] file\n");
 287   exit (FATAL_EXIT_CODE);
 288 }
 289
 290 /* Parse the command line.  */
 291
 292 static void
 293 process_args (argc, argv)
 294      int argc;
 295      char **argv;
 296 {
 297   int i;
 298
 299   for (i = 1; i < argc; i++)
 300     {
 301       if (argv[i][0] == '-')
 302         {
 303           if (argv[i][1] == 'b')
 304             output_branch_probs = 1;
 305           else if (argv[i][1] == 'v')
 306             fputs (gcov_version_string, stderr);
 307           else if (argv[i][1] == 'n')
 308             output_gcov_file = 0;
 309           else if (argv[i][1] == 'l')
 310             output_long_names = 1;
 311           else if (argv[i][1] == 'f')
 312             output_function_summary = 1;
 313           else if (argv[i][1] == 'o' && argv[i][2] == '\0')
 314             object_directory = argv[++i];
 315           else
 316             print_usage ();
 317         }
 318       else if (! input_file_name)
 319         input_file_name = argv[i];
 320       else
 321         print_usage ();
 322     }
 323
 324   if (! input_file_name)
 325     print_usage ();
 326 }
 327
 328
 329 /* Find and open the .bb, .da, and .bbg files.  */
 330
 331 static void
 332 open_files ()
 333 {
 334   int count, objdir_count;
 335   char *cptr;
 336
 337   /* Determine the names of the .bb, .bbg, and .da files.  Strip off the
 338      extension, if any, and append the new extensions.  */
 339   count = strlen (input_file_name);
 340   if (object_directory)
 341     objdir_count = strlen (object_directory);
 342   else
 343     objdir_count = 0;
 344
 345   da_file_name = xmalloc (count + objdir_count + 4);
 346   bb_file_name = xmalloc (count + objdir_count + 4);
 347   bbg_file_name = xmalloc (count + objdir_count + 5);
 348
 349   if (object_directory)
 350     {
 351       strcpy (da_file_name, object_directory);
 352       strcpy (bb_file_name, object_directory);
 353       strcpy (bbg_file_name, object_directory);
 354
 355       if (object_directory[objdir_count - 1] != '/')
 356         {
 357           strcat (da_file_name, "/");
 358           strcat (bb_file_name, "/");
 359           strcat (bbg_file_name, "/");
 360         }
 361
 362       cptr = rindex (input_file_name, '/');
 363       if (cptr)
 364         {
 365           strcat (da_file_name, cptr + 1);
 366           strcat (bb_file_name, cptr + 1);
 367           strcat (bbg_file_name, cptr + 1);
 368         }
 369       else
 370         {
 371           strcat (da_file_name, input_file_name);
 372           strcat (bb_file_name, input_file_name);
 373           strcat (bbg_file_name, input_file_name);
 374         }
 375     }
 376   else
 377     {
 378       strcpy (da_file_name, input_file_name);
 379       strcpy (bb_file_name, input_file_name);
 380       strcpy (bbg_file_name, input_file_name);
 381     }
 382
 383   cptr = rindex (bb_file_name, '.');
 384   if (cptr)
 385     strcpy (cptr, ".bb");
 386   else
 387     strcat (bb_file_name, ".bb");
 388
 389   cptr = rindex (da_file_name, '.');
 390   if (cptr)
 391     strcpy (cptr, ".da");
 392   else
 393     strcat (da_file_name, ".da");
 394
 395   cptr = rindex (bbg_file_name, '.');
 396   if (cptr)
 397     strcpy (cptr, ".bbg");
 398   else
 399     strcat (bbg_file_name, ".bbg");
 400
 401   bb_file = fopen (bb_file_name, "r");
 402   if (bb_file == NULL)
 403     {
 404       fprintf (stderr, "Could not open basic block file %s.\n", bb_file_name);
 405       exit (FATAL_EXIT_CODE);
 406     }
 407
 408   /* If none of the functions in the file were executed, then there won't
 409      be a .da file.  Just assume that all counts are zero in this case.  */
 410   da_file = fopen (da_file_name, "r");
 411   if (da_file == NULL)
 412     {
 413       fprintf (stderr, "Could not open data file %s.\n", da_file_name);
 414       fprintf (stderr, "Assuming that all execution counts are zero.\n");
 415     }
 416
 417   bbg_file = fopen (bbg_file_name, "r");
 418   if (bbg_file == NULL)
 419     {
 420       fprintf (stderr, "Could not open program flow graph file %s.\n",
 421                bbg_file_name);
 422       exit (FATAL_EXIT_CODE);
 423     }
 424
 425   /* Check for empty .bbg file.  This indicates that there is no executable
 426      code in this source file.  */
 427   /* Set the EOF condition if at the end of file.  */
 428   ungetc (getc (bbg_file), bbg_file);
 429   if (feof (bbg_file))
 430     {
 431       fprintf (stderr, "No executable code associated with file %s.\n",
 432                input_file_name);
 433       exit (FATAL_EXIT_CODE);
 434     }
 435 }
 436 \f
 437 /* Initialize a new arc.  */
 438
 439 static void
 440 init_arc (arcptr, source, target, bb_graph)
 441      struct adj_list *arcptr;
 442      int source, target;
 443      struct bb_info *bb_graph;
 444 {
 445   arcptr->target = target;
 446   arcptr->source = source;
 447
 448   arcptr->arc_count = 0;
 449   arcptr->count_valid = 0;
 450   arcptr->on_tree = 0;
 451   arcptr->fake = 0;
 452   arcptr->fall_through = 0;
 453
 454   arcptr->succ_next = bb_graph[source].succ;
 455   bb_graph[source].succ = arcptr;
 456   bb_graph[source].succ_count++;
 457
 458   arcptr->pred_next = bb_graph[target].pred;
 459   bb_graph[target].pred = arcptr;
 460   bb_graph[target].pred_count++;
 461 }
 462
 463
 464 /* Reverse the arcs on a arc list.  */
 465
 466 static struct adj_list *
 467 reverse_arcs (arcptr)
 468      struct adj_list *arcptr;
 469 {
 470   struct adj_list *prev = 0;
 471   struct adj_list *next;
 472
 473   for ( ; arcptr; arcptr = next)
 474     {
 475       next = arcptr->succ_next;
 476       arcptr->succ_next = prev;
 477       prev = arcptr;
 478     }
 479
 480   return prev;
 481 }
 482
 483
 484 /* Construct the program flow graph from the .bbg file, and read in the data
 485    in the .da file.  */
 486
 487 static void
 488 create_program_flow_graph (bptr)
 489      struct bb_info_list *bptr;
 490 {
 491   long num_blocks, number_arcs, src, dest, flag_bits, num_arcs_per_block;
 492   int i;
 493   struct adj_list *arcptr;
 494   struct bb_info *bb_graph;
 495
 496   /* Read the number of blocks.  */
 497   __read_long (&num_blocks, bbg_file, 4);
 498
 499   /* Create an array of size bb number of bb_info structs.  Bzero it.  */
 500   bb_graph = (struct bb_info *) xmalloc (num_blocks
 501                                          * sizeof (struct bb_info));
 502   bzero ((char *) bb_graph, sizeof (struct bb_info) * num_blocks);
 503
 504   bptr->bb_graph = bb_graph;
 505   bptr->num_blocks = num_blocks;
 506
 507   /* Read and create each arc from the .bbg file.  */
 508   __read_long (&number_arcs, bbg_file, 4);
 509   for (i = 0; i < num_blocks; i++)
 510     {
 511       int j;
 512
 513       __read_long (&num_arcs_per_block, bbg_file, 4);
 514       for (j = 0; j < num_arcs_per_block; j++)
 515         {
 516           if (number_arcs-- < 0)
 517             abort ();
 518
 519           src = i;
 520           __read_long (&dest, bbg_file, 4);
 521
 522           arcptr = (struct adj_list *) xmalloc (sizeof (struct adj_list));
 523           init_arc (arcptr, src, dest, bb_graph);
 524
 525           __read_long (&flag_bits, bbg_file, 4);
 526           arcptr->on_tree = flag_bits & 0x1;
 527           arcptr->fake = !! (flag_bits & 0x2);
 528           arcptr->fall_through = !! (flag_bits & 0x4);
 529         }
 530     }
 531
 532   if (number_arcs)
 533     abort ();
 534
 535   /* Read and ignore the -1 separating the arc list from the arc list of the
 536      next function.  */
 537   __read_long (&src, bbg_file, 4);
 538   if (src != -1)
 539     abort ();
 540
 541   /* Must reverse the order of all succ arcs, to ensure that they match
 542      the order of the data in the .da file.  */
 543
 544   for (i = 0; i < num_blocks; i++)
 545     if (bb_graph[i].succ)
 546       bb_graph[i].succ = reverse_arcs (bb_graph[i].succ);
 547
 548   /* For each arc not on the spanning tree, set its execution count from
 549      the .da file.  */
 550
 551   /* The first count in the .da file is the number of times that the function
 552      was entered.  This is the exec_count for block zero.  */
 553
 554   /* This duplicates code in branch_prob in profile.c.  */
 555
 556   for (i = 0; i < num_blocks; i++)
 557     for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
 558       if (! arcptr->on_tree)
 559         {
 560           long tmp_count = 0;;
 561           if (da_file && __read_long (&tmp_count, da_file, 8))
 562             abort();
 563
 564           arcptr->arc_count = tmp_count;
 565           arcptr->count_valid = 1;
 566           bb_graph[i].succ_count--;
 567           bb_graph[arcptr->target].pred_count--;
 568         }
 569 }
 570
 571 static void
 572 solve_program_flow_graph (bptr)
 573      struct bb_info_list *bptr;
 574 {
 575   int passes, changes, total;
 576   int i;
 577   struct adj_list *arcptr;
 578   struct bb_info *bb_graph;
 579   int num_blocks;
 580
 581   num_blocks = bptr->num_blocks;
 582   bb_graph = bptr->bb_graph;
 583
 584   /* For every block in the file,
 585      - if every exit/entrance arc has a known count, then set the block count
 586      - if the block count is known, and every exit/entrance arc but one has
 587        a known execution count, then set the count of the remaining arc
 588
 589      As arc counts are set, decrement the succ/pred count, but don't delete
 590      the arc, that way we can easily tell when all arcs are known, or only
 591      one arc is unknown.  */
 592
 593   /* The order that the basic blocks are iterated through is important.
 594      Since the code that finds spanning trees starts with block 0, low numbered
 595      arcs are put on the spanning tree in preference to high numbered arcs.
 596      Hence, most instrumented arcs are at the end.  Graph solving works much
 597      faster if we propagate numbers from the end to the start.
 598
 599      This takes an average of slightly more than 3 passes.  */
 600
 601   changes = 1;
 602   passes = 0;
 603   while (changes)
 604     {
 605       passes++;
 606       changes = 0;
 607
 608       for (i = num_blocks - 1; i >= 0; i--)
 609         {
 610           if (! bb_graph[i].count_valid)
 611             {
 612               if (bb_graph[i].succ_count == 0)
 613                 {
 614                   total = 0;
 615                   for (arcptr = bb_graph[i].succ; arcptr;
 616                        arcptr = arcptr->succ_next)
 617                     total += arcptr->arc_count;
 618                   bb_graph[i].exec_count = total;
 619                   bb_graph[i].count_valid = 1;
 620                   changes = 1;
 621                 }
 622               else if (bb_graph[i].pred_count == 0)
 623                 {
 624                   total = 0;
 625                   for (arcptr = bb_graph[i].pred; arcptr;
 626                        arcptr = arcptr->pred_next)
 627                     total += arcptr->arc_count;
 628                   bb_graph[i].exec_count = total;
 629                   bb_graph[i].count_valid = 1;
 630                   changes = 1;
 631                 }
 632             }
 633           if (bb_graph[i].count_valid)
 634             {
 635               if (bb_graph[i].succ_count == 1)
 636                 {
 637                   total = 0;
 638                   /* One of the counts will be invalid, but it is zero,
 639                      so adding it in also doesn't hurt.  */
 640                   for (arcptr = bb_graph[i].succ; arcptr;
 641                        arcptr = arcptr->succ_next)
 642                     total += arcptr->arc_count;
 643                   /* Calculate count for remaining arc by conservation.  */
 644                   total = bb_graph[i].exec_count - total;
 645                   /* Search for the invalid arc, and set its count.  */
 646                   for (arcptr = bb_graph[i].succ; arcptr;
 647                        arcptr = arcptr->succ_next)
 648                     if (! arcptr->count_valid)
 649                       break;
 650                   if (! arcptr)
 651                     abort ();
 652                   arcptr->count_valid = 1;
 653                   arcptr->arc_count = total;
 654                   bb_graph[i].succ_count--;
 655
 656                   bb_graph[arcptr->target].pred_count--;
 657                   changes = 1;
 658                 }
 659               if (bb_graph[i].pred_count == 1)
 660                 {
 661                   total = 0;
 662                   /* One of the counts will be invalid, but it is zero,
 663                      so adding it in also doesn't hurt.  */
 664                   for (arcptr = bb_graph[i].pred; arcptr;
 665                        arcptr = arcptr->pred_next)
 666                     total += arcptr->arc_count;
 667                   /* Calculate count for remaining arc by conservation.  */
 668                   total = bb_graph[i].exec_count - total;
 669                   /* Search for the invalid arc, and set its count.  */
 670                   for (arcptr = bb_graph[i].pred; arcptr;
 671                        arcptr = arcptr->pred_next)
 672                     if (! arcptr->count_valid)
 673                       break;
 674                   if (! arcptr)
 675                     abort ();
 676                   arcptr->count_valid = 1;
 677                   arcptr->arc_count = total;
 678                   bb_graph[i].pred_count--;
 679
 680                   bb_graph[arcptr->source].succ_count--;
 681                   changes = 1;
 682                 }
 683             }
 684         }
 685     }
 686
 687   /* If the graph has been correctly solved, every block will have a
 688      succ and pred count of zero.  */
 689   for (i = 0; i < num_blocks; i++)
 690     if (bb_graph[i].succ_count || bb_graph[i].pred_count)
 691       abort ();
 692 }
 693
 694
 695 static void
 696 read_files ()
 697 {
 698   struct stat buf;
 699   struct bb_info_list *list_end = 0;
 700   struct bb_info_list *b_ptr;
 701   long total;
 702
 703   /* Read and ignore the first word of the .da file, which is the count of
 704      how many numbers follow.  */
 705   if (da_file && __read_long (&total, da_file, 8))
 706     abort();
 707
 708   while (! feof (bbg_file))
 709     {
 710       b_ptr = (struct bb_info_list *) xmalloc (sizeof (struct bb_info_list));
 711
 712       b_ptr->next = 0;
 713       if (list_end)
 714         list_end->next = b_ptr;
 715       else
 716         bb_graph_list = b_ptr;
 717       list_end = b_ptr;
 718
 719       /* Read in the data in the .bbg file and reconstruct the program flow
 720          graph for one function.  */
 721       create_program_flow_graph (b_ptr);
 722
 723       /* Set the EOF condition if at the end of file.  */
 724       ungetc (getc (bbg_file), bbg_file);
 725     }
 726
 727   /* Check to make sure the .da file data is valid.  */
 728
 729   if (da_file)
 730     {
 731       if (feof (da_file))
 732         fprintf (stderr, ".da file contents exhausted too early\n");
 733       /* Should be at end of file now.  */
 734       if (__read_long (&total, da_file, 8) == 0)
 735         fprintf (stderr, ".da file contents not exhausted\n");
 736     }
 737
 738   /* Calculate all of the basic block execution counts and branch
 739      taken probabilities.  */
 740
 741   for (b_ptr = bb_graph_list; b_ptr; b_ptr = b_ptr->next)
 742     solve_program_flow_graph (b_ptr);
 743
 744   /* Read in all of the data from the .bb file.   This info will be accessed
 745      sequentially twice.  */
 746   stat (bb_file_name, &buf);
 747   bb_data_size = buf.st_size / 4;
 748
 749   bb_data = (char *) xmalloc ((unsigned) buf.st_size);
 750   fread (bb_data, sizeof (char), buf.st_size, bb_file);
 751
 752   fclose (bb_file);
 753   if (da_file)
 754     fclose (da_file);
 755   fclose (bbg_file);
 756 }
 757
 758
 759 /* Scan the data in the .bb file to find all source files referenced,
 760    and the largest line number mentioned in each one.  */
 761
 762 static void
 763 scan_for_source_files ()
 764 {
 765   struct sourcefile *s_ptr = NULL;
 766   char *ptr;
 767   int count;
 768   long line_num;
 769
 770   /* Search the bb_data to find:
 771      1) The number of sources files contained herein, and
 772      2) The largest line number for each source file.  */
 773
 774   ptr = bb_data;
 775   sources = 0;
 776   for (count = 0; count < bb_data_size; count++)
 777     {
 778       __fetch_long (&line_num, ptr, 4);
 779       ptr += 4;
 780       if (line_num == -1)
 781         {
 782           /* A source file name follows.  Check to see if we already have
 783            a sourcefile structure for this file.  */
 784           s_ptr = sources;
 785           while (s_ptr && strcmp (s_ptr->name, ptr))
 786             s_ptr = s_ptr->next;
 787
 788           if (s_ptr == 0)
 789             {
 790               /* No sourcefile structure for this file name exists, create
 791                  a new one, and append it to the front of the sources list.  */
 792               s_ptr = (struct sourcefile *) xmalloc (sizeof(struct sourcefile));
 793               s_ptr->name = xmalloc (strlen ((char *) ptr) + 1);
 794               strcpy (s_ptr->name, (char *) ptr);
 795               s_ptr->maxlineno = 0;
 796               s_ptr->next = sources;
 797               sources = s_ptr;
 798             }
 799
 800           /* Scan past the file name.  */
 801           {
 802             long delim;
 803             do {
 804               count++;
 805               __fetch_long (&delim, ptr, 4);
 806               ptr += 4;
 807             } while (delim != line_num);
 808           }
 809         }
 810       else if (line_num == -2)
 811         {
 812           long delim;
 813
 814           /* A function name follows.  Ignore it.  */
 815           do {
 816             count++;
 817             __fetch_long (&delim, ptr, 4);
 818             ptr += 4;
 819           } while (delim != line_num);
 820         }
 821       /* There will be a zero before the first file name, in which case s_ptr
 822          will still be uninitialized.  So, only try to set the maxlineno
 823          field if line_num is non-zero.  */
 824       else if (line_num > 0)
 825         {
 826           if (s_ptr->maxlineno <= line_num)
 827             s_ptr->maxlineno = line_num + 1;
 828         }
 829       else if (line_num < 0)
 830         {
 831           /* Don't know what this is, but it's garbage. */
 832           abort();
 833         }
 834     }
 835 }
 836 \f
 837 /* For calculating coverage at the function level.  */
 838
 839 static int function_source_lines;
 840 static int function_source_lines_executed;
 841 static int function_branches;
 842 static int function_branches_executed;
 843 static int function_branches_taken;
 844 static int function_calls;
 845 static int function_calls_executed;
 846 static char *function_name;
 847
 848 /* Calculate the branch taken probabilities for all arcs branches at the
 849    end of this block.  */
 850
 851 static void
 852 calculate_branch_probs (current_graph, block_num, branch_probs, last_line_num)
 853      struct bb_info_list *current_graph;
 854      int block_num;
 855      struct arcdata **branch_probs;
 856      int last_line_num;
 857 {
 858   int total;
 859   struct adj_list *arcptr;
 860   struct arcdata *end_ptr, *a_ptr;
 861
 862   total = current_graph->bb_graph[block_num].exec_count;
 863   for (arcptr = current_graph->bb_graph[block_num].succ; arcptr;
 864        arcptr = arcptr->succ_next)
 865     {
 866       /* Ignore fall through arcs as they aren't really branches.  */
 867
 868       if (arcptr->fall_through)
 869         continue;
 870
 871       a_ptr = (struct arcdata *) xmalloc (sizeof (struct arcdata));
 872       if (total == 0)
 873         a_ptr->prob = -1;
 874       else
 875         a_ptr->prob = ((arcptr->arc_count * 100) + (total >> 1)) / total;
 876       a_ptr->call_insn = arcptr->fake;
 877
 878       if (output_function_summary)
 879         {
 880           if (a_ptr->call_insn)
 881             {
 882               function_calls++;
 883               if (a_ptr->prob != -1)
 884                 function_calls_executed++;
 885             }
 886           else
 887             {
 888               function_branches++;
 889               if (a_ptr->prob != -1)
 890                 function_branches_executed++;
 891               if (a_ptr->prob > 0)
 892                 function_branches_taken++;
 893             }
 894         }
 895
 896       /* Append the new branch to the end of the list.  */
 897       a_ptr->next = 0;
 898       if (! branch_probs[last_line_num])
 899         branch_probs[last_line_num] = a_ptr;
 900       else
 901         {
 902           end_ptr = branch_probs[last_line_num];
 903           while (end_ptr->next != 0)
 904             end_ptr = end_ptr->next;
 905           end_ptr->next = a_ptr;
 906         }
 907     }
 908 }
 909
 910 /* Output summary info for a function.  */
 911
 912 static void
 913 function_summary ()
 914 {
 915   if (function_source_lines)
 916     fprintf (stdout, "%6.2f%% of %d source lines executed in function %s\n",
 917              (((double) function_source_lines_executed / function_source_lines)
 918               * 100), function_source_lines, function_name);
 919   else
 920     fprintf (stdout, "No executable source lines in function %s\n",
 921              function_name);
 922
 923   if (output_branch_probs)
 924     {
 925       if (function_branches)
 926         {
 927           fprintf (stdout, "%6.2f%% of %d branches executed in function %s\n",
 928                    (((double) function_branches_executed / function_branches)
 929                     * 100), function_branches, function_name);
 930           fprintf (stdout,
 931                 "%6.2f%% of %d branches taken at least once in function %s\n",
 932                    (((double) function_branches_taken / function_branches)
 933                     * 100), function_branches, function_name);
 934         }
 935       else
 936         fprintf (stdout, "No branches in function %s\n", function_name);
 937       if (function_calls)
 938         fprintf (stdout, "%6.2f%% of %d calls executed in function %s\n",
 939                  (((double) function_calls_executed / function_calls)
 940                   * 100), function_calls, function_name);
 941       else
 942         fprintf (stdout, "No calls in function %s\n", function_name);
 943     }
 944 }
 945
 946 /* Calculate line execution counts, and output the data to a .tcov file.  */
 947
 948 static void
 949 output_data ()
 950 {
 951   /* When scanning data, this is true only if the data applies to the
 952      current source file.  */
 953   int this_file;
 954   /* An array indexed by line number which indicates how many times that line
 955      was executed.  */
 956   long *line_counts;
 957   /* An array indexed by line number which indicates whether the line was
 958      present in the bb file (i.e. whether it had code associate with it).
 959      Lines never executed are those which both exist, and have zero execution
 960      counts.  */
 961   char *line_exists;
 962   /* An array indexed by line number, which contains a list of branch
 963      probabilities, one for each branch on that line.  */
 964   struct arcdata **branch_probs = NULL;
 965   struct sourcefile *s_ptr;
 966   char *source_file_name;
 967   FILE *source_file;
 968   struct bb_info_list *current_graph;
 969   int count;
 970   char *cptr;
 971   long block_num;
 972   long line_num;
 973   long last_line_num = 0;
 974   int i;
 975   struct arcdata *a_ptr;
 976   /* Buffer used for reading in lines from the source file.  */
 977   char string[STRING_SIZE];
 978   /* For calculating coverage at the file level.  */
 979   int total_source_lines;
 980   int total_source_lines_executed;
 981   int total_branches;
 982   int total_branches_executed;
 983   int total_branches_taken;
 984   int total_calls;
 985   int total_calls_executed;
 986
 987   /* Now, for each source file, allocate an array big enough to hold a count
 988      for each line.  Scan through the bb_data, and when the file name matches
 989      the current file name, then for each following line number, increment
 990      the line number execution count indicated by the execution count of
 991      the appropriate basic block.  */
 992
 993   for (s_ptr = sources; s_ptr; s_ptr = s_ptr->next)
 994     {
 995       /* If this is a relative file name, and an object directory has been
 996          specified, then make it relative to the object directory name.  */
 997       if (*s_ptr->name != '/' && object_directory != 0
 998           && *object_directory != '\0')
 999         {
1000           int objdir_count = strlen (object_directory);
1001           source_file_name = xmalloc (objdir_count + strlen (s_ptr->name) + 2);
1002           strcpy (source_file_name, object_directory);
1003           if (object_directory[objdir_count - 1] != '/')
1004             source_file_name[objdir_count++] = '/';
1005           strcpy (source_file_name + objdir_count, s_ptr->name);
1006         }
1007       else
1008         source_file_name = s_ptr->name;
1009
1010       line_counts = (long *) xmalloc (sizeof (long) * s_ptr->maxlineno);
1011       bzero ((char *) line_counts, sizeof (long) * s_ptr->maxlineno);
1012       line_exists = xmalloc (s_ptr->maxlineno);
1013       bzero (line_exists, s_ptr->maxlineno);
1014       if (output_branch_probs)
1015         {
1016           branch_probs = (struct arcdata **) xmalloc (sizeof (struct arcdata **)
1017                                                       * s_ptr->maxlineno);
1018           bzero ((char *) branch_probs,
1019                  sizeof (struct arcdata **) * s_ptr->maxlineno);
1020         }
1021
1022       /* There will be a zero at the beginning of the bb info, before the
1023          first list of line numbers, so must initialize block_num to 0.  */
1024       block_num = 0;
1025       this_file = 0;
1026       current_graph = 0;
1027       {
1028         /* Pointer into the bb_data, incremented while scanning the data.  */
1029         char *ptr = bb_data;
1030         for (count = 0; count < bb_data_size; count++)
1031           {
1032             long delim;
1033
1034             __fetch_long (&line_num, ptr, 4);
1035             ptr += 4;
1036             if (line_num == -1)
1037               {
1038                 /* Marks the beginning of a file name.  Check to see whether
1039                    this is the filename we are currently collecting data for.  */
1040
1041                 if (strcmp (s_ptr->name, ptr))
1042                   this_file = 0;
1043                 else
1044                   this_file = 1;
1045
1046                 /* Scan past the file name.  */
1047                 do {
1048                   count++;
1049                   __fetch_long (&delim, ptr, 4);
1050                   ptr += 4;
1051                 } while (delim != line_num);
1052               }
1053             else if (line_num == -2)
1054               {
1055                 /* Marks the start of a new function.  Advance to the next
1056                    program flow graph.  */
1057
1058                 if (! current_graph)
1059                   current_graph = bb_graph_list;
1060                 else
1061                   {
1062                     if (block_num == current_graph->num_blocks - 1)
1063                       /* Last block falls through to exit.  */
1064                       ;
1065                     else if (block_num == current_graph->num_blocks - 2)
1066                       {
1067                         if (output_branch_probs && this_file)
1068                           calculate_branch_probs (current_graph, block_num,
1069                                                   branch_probs, last_line_num);
1070                       }
1071                     else
1072                       {
1073                         fprintf (stderr,
1074                                  "didn't use all bb entries of graph, function %s\n",
1075                                  function_name);
1076                         fprintf (stderr, "block_num = %ld, num_blocks = %d\n",
1077                                  block_num, current_graph->num_blocks);
1078                       }
1079
1080                     current_graph = current_graph->next;
1081                     block_num = 0;
1082
1083                     if (output_function_summary && this_file)
1084                       function_summary ();
1085                   }
1086
1087                 if (output_function_summary)
1088                   {
1089                     function_source_lines = 0;
1090                     function_source_lines_executed = 0;
1091                     function_branches = 0;
1092                     function_branches_executed = 0;
1093                     function_branches_taken = 0;
1094                     function_calls = 0;
1095                     function_calls_executed = 0;
1096                   }
1097
1098                 /* Save the function name for later use.  */
1099                 function_name = ptr;
1100
1101                 /* Scan past the file name.  */
1102                 do {
1103                   count++;
1104                   __fetch_long (&delim, ptr, 4);
1105                   ptr += 4;
1106                 } while (delim != line_num);
1107               }
1108             else if (line_num == 0)
1109               {
1110                 /* Marks the end of a block.  */
1111
1112                 if (block_num >= current_graph->num_blocks)
1113                   {
1114                     fprintf (stderr, "ERROR: too many basic blocks in .bb file %s\n",
1115                              function_name);
1116                     abort ();
1117                   }
1118
1119                 if (output_branch_probs && this_file)
1120                   calculate_branch_probs (current_graph, block_num,
1121                                           branch_probs, last_line_num);
1122
1123                 block_num++;
1124               }
1125             else if (this_file)
1126               {
1127                 if (output_function_summary)
1128                   {
1129                     if (line_exists[line_num] == 0)
1130                       function_source_lines++;
1131                     if (line_counts[line_num] == 0
1132                         && current_graph->bb_graph[block_num].exec_count != 0)
1133                       function_source_lines_executed++;
1134                   }
1135
1136                 /* Accumulate execution data for this line number.  */
1137
1138                 line_counts[line_num]
1139                   += current_graph->bb_graph[block_num].exec_count;
1140                 line_exists[line_num] = 1;
1141                 last_line_num = line_num;
1142               }
1143           }
1144       }
1145
1146       if (output_function_summary && this_file)
1147         function_summary ();
1148
1149       /* Calculate summary test coverage statistics.  */
1150
1151       total_source_lines = 0;
1152       total_source_lines_executed = 0;
1153       total_branches = 0;
1154       total_branches_executed = 0;
1155       total_branches_taken = 0;
1156       total_calls = 0;
1157       total_calls_executed = 0;
1158
1159       for (count = 1; count < s_ptr->maxlineno; count++)
1160         {
1161           if (line_exists[count])
1162             {
1163               total_source_lines++;
1164               if (line_counts[count])
1165                 total_source_lines_executed++;
1166             }
1167           if (output_branch_probs)
1168             {
1169               for (a_ptr = branch_probs[count]; a_ptr; a_ptr = a_ptr->next)
1170                 {
1171                   if (a_ptr->call_insn)
1172                     {
1173                       total_calls++;
1174                       if (a_ptr->prob != -1)
1175                         total_calls_executed++;
1176                     }
1177                   else
1178                     {
1179                       total_branches++;
1180                       if (a_ptr->prob != -1)
1181                         total_branches_executed++;
1182                       if (a_ptr->prob > 0)
1183                         total_branches_taken++;
1184                     }
1185                 }
1186             }
1187         }
1188
1189       if (total_source_lines)
1190         fprintf (stdout,
1191                  "%6.2f%% of %d source lines executed in file %s\n",
1192                  (((double) total_source_lines_executed / total_source_lines)
1193                   * 100), total_source_lines, source_file_name);
1194       else
1195         fprintf (stdout, "No executable source lines in file %s\n",
1196                  source_file_name);
1197
1198       if (output_branch_probs)
1199         {
1200           if (total_branches)
1201             {
1202               fprintf (stdout, "%6.2f%% of %d branches executed in file %s\n",
1203                        (((double) total_branches_executed / total_branches)
1204                         * 100), total_branches, source_file_name);
1205               fprintf (stdout,
1206                     "%6.2f%% of %d branches taken at least once in file %s\n",
1207                        (((double) total_branches_taken / total_branches)
1208                         * 100), total_branches, source_file_name);
1209             }
1210           else
1211             fprintf (stdout, "No branches in file %s\n", source_file_name);
1212           if (total_calls)
1213             fprintf (stdout, "%6.2f%% of %d calls executed in file %s\n",
1214                      (((double) total_calls_executed / total_calls)
1215                       * 100), total_calls, source_file_name);
1216           else
1217             fprintf (stdout, "No calls in file %s\n", source_file_name);
1218         }
1219
1220       if (output_gcov_file)
1221         {
1222           /* Now the statistics are ready.  Read in the source file one line
1223              at a time, and output that line to the gcov file preceded by
1224              its execution count if non zero.  */
1225
1226           source_file = fopen (source_file_name, "r");
1227           if (source_file == NULL)
1228             {
1229               fprintf (stderr, "Could not open source file %s.\n",
1230                        source_file_name);
1231               free (line_counts);
1232               free (line_exists);
1233               continue;
1234             }
1235
1236           count = strlen (source_file_name);
1237           cptr = rindex (s_ptr->name, '/');
1238           if (cptr)
1239             cptr = cptr + 1;
1240           else
1241             cptr = s_ptr->name;
1242           if (output_long_names && strcmp (cptr, input_file_name))
1243             {
1244               gcov_file_name = xmalloc (count + 7 + strlen (input_file_name));
1245
1246               cptr = rindex (input_file_name, '/');
1247               if (cptr)
1248                 strcpy (gcov_file_name, cptr + 1);
1249               else
1250                 strcpy (gcov_file_name, input_file_name);
1251
1252               strcat (gcov_file_name, ".");
1253
1254               cptr = rindex (source_file_name, '/');
1255               if (cptr)
1256                 strcat (gcov_file_name, cptr + 1);
1257               else
1258                 strcat (gcov_file_name, source_file_name);
1259             }
1260           else
1261             {
1262               gcov_file_name = xmalloc (count + 6);
1263               cptr = rindex (source_file_name, '/');
1264               if (cptr)
1265                 strcpy (gcov_file_name, cptr + 1);
1266               else
1267                 strcpy (gcov_file_name, source_file_name);
1268             }
1269
1270           /* Don't strip off the ending for compatibility with tcov, since
1271              this results in confusion if there is more than one file with
1272              the same basename, e.g. tmp.c and tmp.h.  */
1273           strcat (gcov_file_name, ".gcov");
1274
1275           gcov_file = fopen (gcov_file_name, "w");
1276
1277           if (gcov_file == NULL)
1278             {
1279               fprintf (stderr, "Could not open output file %s.\n",
1280                        gcov_file_name);
1281               fclose (source_file);
1282               free (line_counts);
1283               free (line_exists);
1284               continue;
1285             }
1286
1287           fprintf (stdout, "Creating %s.\n", gcov_file_name);
1288
1289           for (count = 1; count < s_ptr->maxlineno; count++)
1290             {
1291               char *retval;
1292               int len;
1293
1294               retval = fgets (string, STRING_SIZE, source_file);
1295
1296               /* For lines which don't exist in the .bb file, print nothing
1297                  before the source line.  For lines which exist but were never
1298                  executed, print ###### before the source line.  Otherwise,
1299                  print the execution count before the source line.  */
1300               /* There are 16 spaces of indentation added before the source
1301                  line so that tabs won't be messed up.  */
1302               if (line_exists[count])
1303                 {
1304                   if (line_counts[count])
1305                     fprintf (gcov_file, "%12ld    %s", line_counts[count],
1306                              string);
1307                   else
1308                     fprintf (gcov_file, "      ######    %s", string);
1309                 }
1310               else
1311                 fprintf (gcov_file, "\t\t%s", string);
1312
1313               /* In case the source file line is larger than our buffer, keep
1314                  reading and outputting lines until we get a newline.  */
1315               len = strlen (string);
1316               while ((len == 0 || string[strlen (string) - 1] != '\n')
1317                      && retval != NULL)
1318                 {
1319                   retval = fgets (string, STRING_SIZE, source_file);
1320                   fputs (string, gcov_file);
1321                 }
1322
1323               if (output_branch_probs)
1324                 {
1325                   for (i = 0, a_ptr = branch_probs[count]; a_ptr;
1326                        a_ptr = a_ptr->next, i++)
1327                     {
1328                       if (a_ptr->call_insn)
1329                         {
1330                           if (a_ptr->prob == -1)
1331                             fprintf (gcov_file, "call %d never executed\n", i);
1332                           else
1333                             fprintf (gcov_file,
1334                                      "call %d returns = %d%%\n",
1335                                      i, 100 - a_ptr->prob);
1336                         }
1337                       else
1338                         {
1339                           if (a_ptr->prob == -1)
1340                             fprintf (gcov_file, "branch %d never executed\n",
1341                                      i);
1342                           else
1343                             fprintf (gcov_file, "branch %d taken = %d%%\n", i,
1344                                      a_ptr->prob);
1345                         }
1346                     }
1347                 }
1348
1349               /* Gracefully handle errors while reading the source file.  */
1350               if (retval == NULL)
1351                 {
1352                   fprintf (stderr,
1353                            "Unexpected EOF while reading source file %s.\n",
1354                            source_file_name);
1355                   break;
1356                 }
1357             }
1358
1359           /* Handle all remaining source lines.  There may be lines
1360              after the last line of code.  */
1361
1362           {
1363             char *retval = fgets (string, STRING_SIZE, source_file);
1364             while (retval != NULL)
1365               {
1366                 int len;
1367
1368                 fprintf (gcov_file, "\t\t%s", string);
1369
1370                 /* In case the source file line is larger than our buffer, keep
1371                    reading and outputting lines until we get a newline.  */
1372                 len = strlen (string);
1373                 while ((len == 0 || string[strlen (string) - 1] != '\n')
1374                        && retval != NULL)
1375                   {
1376                     retval = fgets (string, STRING_SIZE, source_file);
1377                     fputs (string, gcov_file);
1378                   }
1379
1380                 retval = fgets (string, STRING_SIZE, source_file);
1381               }
1382           }
1383
1384           fclose (source_file);
1385           fclose (gcov_file);
1386         }
1387
1388       free (line_counts);
1389       free (line_exists);
1390     }
1391 }