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