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