gcc/gcov.c

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