gcc/gcov.c

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