gcc/gcov.c

   1 /* Gcov.c: prepend line execution counts and branch probabilities to a
   2    source file.
   3    Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998,
   4    1999, 2000, 2001, 2002 Free Software Foundation, Inc.
   5    Contributed by James E. Wilson of Cygnus Support.
   6    Mangled by Bob Manson of Cygnus Support.
   7    Mangled further by Nathan Sidwell <nathan@codesourcery.com>
   8
   9 Gcov is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation; either version 2, or (at your option)
  12 any later version.
  13
  14 Gcov is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Gcov; see the file COPYING.  If not, write to
  21 the Free Software Foundation, 59 Temple Place - Suite 330,
  22 Boston, MA 02111-1307, USA.  */
  23
  24 /* ??? Print a list of the ten blocks with the highest execution counts,
  25    and list the line numbers corresponding to those blocks.  Also, perhaps
  26    list the line numbers with the highest execution counts, only printing
  27    the first if there are several which are all listed in the same block.  */
  28
  29 /* ??? Should have an option to print the number of basic blocks, and the
  30    percent of them that are covered.  */
  31
  32 /* ??? Does not correctly handle the case where two .bb files refer to
  33    the same included source file.  For example, if one has a short
  34    file containing only inline functions, which is then included in
  35    two other files, then there will be two .bb files which refer to
  36    the include file, but there is no way to get the total execution
  37    counts for the included file, can only get execution counts for one
  38    or the other of the including files. this can be fixed by --ratios
  39    --long-file-names --preserve-paths and perl.  */
  40
  41 /* Need an option to show individual block counts, and show
  42    probabilities of fall through arcs.  */
  43
  44 #include "config.h"
  45 #include "system.h"
  46 #include "coretypes.h"
  47 #include "tm.h"
  48 #include "intl.h"
  49 #include "version.h"
  50 #undef abort
  51
  52 #include <getopt.h>
  53
  54 #define IN_GCOV 1
  55 #include "gcov-io.h"
  56
  57 /* The bbg file is generated by -ftest-coverage option. The da file is
  58    generated by a program compiled with -fprofile-arcs. Their formats
  59    are documented in gcov-io.h.  */
  60
  61 /* The functions in this file for creating and solution program flow graphs
  62    are very similar to functions in the gcc source file profile.c.  In
  63    some places we make use of the knowledge of how profile.c works to
  64    select particular algorithms here.  */
  65
  66 /* This is the size of the buffer used to read in source file lines.  */
  67
  68 #define STRING_SIZE 200
  69
  70 struct function_info;
  71 struct block_info;
  72 struct source_info;
  73
  74 /* Describes an arc between two basic blocks.  */
  75
  76 typedef struct arc_info
  77 {
  78   /* source and destination blocks.  */
  79   struct block_info *src;
  80   struct block_info *dst;
  81
  82   /* transition counts.  */
  83   gcov_type count;
  84
  85   unsigned int count_valid : 1;
  86   unsigned int on_tree : 1;
  87   unsigned int fake : 1;
  88   unsigned int fall_through : 1;
  89
  90   /* Arc is for a function that abnormally returns.  */
  91   unsigned int is_call_non_return : 1;
  92
  93   /* Arc is for catch/setjump.  */
  94   unsigned int is_nonlocal_return : 1;
  95
  96   /* Is an unconditional branch.  */
  97   unsigned int is_unconditional : 1;
  98
  99   /* Loop making arc.  */
 100   unsigned int cycle : 1;
 101
 102   /* Next branch on line.  */
 103   struct arc_info *line_next;
 104
 105   /* Links to next arc on src and dst lists.  */
 106   struct arc_info *succ_next;
 107   struct arc_info *pred_next;
 108 } arc_t;
 109
 110 /* Describes a basic block. Contains lists of arcs to successor and
 111    predecessor blocks.  */
 112
 113 typedef struct block_info
 114 {
 115   /* Chain of exit and entry arcs.  */
 116   arc_t *succ;
 117   arc_t *pred;
 118
 119   /* Number of unprocessed exit and entry arcs.  */
 120   gcov_type num_succ;
 121   gcov_type num_pred;
 122
 123   /* Block execution count.  */
 124   gcov_type count;
 125   unsigned flags : 13;
 126   unsigned count_valid : 1;
 127   unsigned valid_chain : 1;
 128   unsigned invalid_chain : 1;
 129
 130   /* Block is a call instrumenting site.  */
 131   unsigned is_call_site : 1; /* Does the call.  */
 132   unsigned is_call_return : 1; /* Is the return.  */
 133
 134   /* Block is a landing pad for longjmp or throw.  */
 135   unsigned is_nonlocal_return : 1;
 136
 137   union
 138   {
 139     struct
 140     {
 141      /* Array of line numbers and source files. source files are
 142         introduced by a linenumber of zero, the next 'line number' is
 143         the number of the source file.  Always starts with a source
 144         file.  */
 145       unsigned *encoding;
 146       unsigned num;
 147     } line; /* Valid until blocks are linked onto lines */
 148     struct
 149     {
 150       /* Single line graph cycle workspace.  Used for all-blocks
 151          mode. */
 152       arc_t *arc;
 153       unsigned ident;
 154     } cycle; /* Used in all-blocks mode, after blocks are linked onto
 155                lines. */
 156   } u;
 157
 158   /* Temporary chain for solving graph, and for chaining blocks on one
 159      line.  */
 160   struct block_info *chain;
 161
 162 } block_t;
 163
 164 /* Describes a single function. Contains an array of basic blocks.  */
 165
 166 typedef struct function_info
 167 {
 168   /* Name of function.  */
 169   char *name;
 170   unsigned checksum;
 171
 172   /* Array of basic blocks.  */
 173   block_t *blocks;
 174   unsigned num_blocks;
 175   unsigned blocks_executed;
 176
 177   /* Raw arc coverage counts.  */
 178   gcov_type *counts;
 179   unsigned num_counts;
 180
 181   /* First line number.  */
 182   unsigned line;
 183   struct source_info *src;
 184
 185   /* Next function in same source file.  */
 186   struct function_info *line_next;
 187
 188   /* Next function.  */
 189   struct function_info *next;
 190 } function_t;
 191
 192 /* Describes coverage of a file or function.  */
 193
 194 typedef struct coverage_info
 195 {
 196   int lines;
 197   int lines_executed;
 198
 199   int branches;
 200   int branches_executed;
 201   int branches_taken;
 202
 203   int calls;
 204   int calls_executed;
 205
 206   char *name;
 207 } coverage_t;
 208
 209 /* Describes a single line of source. Contains a chain of basic blocks
 210    with code on it.  */
 211
 212 typedef struct line_info
 213 {
 214   gcov_type count;         /* execution count */
 215   union
 216   {
 217     arc_t *branches;       /* branches from blocks that end on this
 218                               line. Used for branch-counts when not
 219                               all-blocks mode. */
 220     block_t *blocks;       /* blocks which start on this line.  Used
 221                               in all-blocks mode. */
 222   } u;
 223   unsigned exists : 1;
 224 } line_t;
 225
 226 /* Describes a file mentioned in the block graph.  Contains an array
 227    of line info.  */
 228
 229 typedef struct source_info
 230 {
 231   /* Name of source file.  */
 232   char *name;
 233   unsigned index;
 234
 235   /* Array of line information.  */
 236   line_t *lines;
 237   unsigned num_lines;
 238
 239   coverage_t coverage;
 240
 241   /* Functions in this source file.  These are in ascending line
 242      number order.  */
 243   function_t *functions;
 244
 245   /* Next source file.  */
 246   struct source_info *next;
 247 } source_t;
 248
 249 /* Holds a list of function basic block graphs.  */
 250
 251 static function_t *functions;
 252
 253 /* This points to the head of the sourcefile structure list.  */
 254
 255 static source_t *sources;
 256
 257 /* This holds data summary information.  */
 258
 259 static struct gcov_summary object_summary;
 260 static unsigned program_count;
 261
 262 /* Modification time of graph file.  */
 263
 264 static time_t bbg_file_time;
 265
 266 /* Name and file pointer of the input file for the basic block graph.  */
 267
 268 static char *bbg_file_name;
 269
 270 /* Name and file pointer of the input file for the arc count data.  */
 271
 272 static char *da_file_name;
 273
 274 /* Output branch probabilities.  */
 275
 276 static int flag_branches = 0;
 277
 278 /* Show unconditional branches too.  */
 279 static int flag_unconditional = 0;
 280
 281 /* Output a gcov file if this is true.  This is on by default, and can
 282    be turned off by the -n option.  */
 283
 284 static int flag_gcov_file = 1;
 285
 286 /* For included files, make the gcov output file name include the name
 287    of the input source file.  For example, if x.h is included in a.c,
 288    then the output file name is a.c##x.h.gcov instead of x.h.gcov.  */
 289
 290 static int flag_long_names = 0;
 291
 292 /* Output count information for every basic block, not merely those
 293    that contain line number information.  */
 294
 295 static int flag_all_blocks = 0;
 296
 297 /* Output summary info for each function.  */
 298
 299 static int flag_function_summary = 0;
 300
 301 /* Object directory file prefix.  This is the directory/file where the
 302    graph and data files are looked for, if nonzero.  */
 303
 304 static char *object_directory = 0;
 305
 306 /* Preserve all pathname components. Needed when object files and
 307    source files are in subdirectories. '/' is mangled as '#', '.' is
 308    elided and '..' mangled to '^'.  */
 309
 310 static int flag_preserve_paths = 0;
 311
 312 /* Output the number of times a branch was taken as opposed to the percentage
 313    of times it was taken.  */
 314
 315 static int flag_counts = 0;
 316
 317 /* Forward declarations.  */
 318 static void fnotice PARAMS ((FILE *, const char *, ...)) ATTRIBUTE_PRINTF_2;
 319 static int process_args PARAMS ((int, char **));
 320 static void print_usage PARAMS ((int)) ATTRIBUTE_NORETURN;
 321 static void print_version PARAMS ((void)) ATTRIBUTE_NORETURN;
 322 static void process_file PARAMS ((const char *));
 323 static void create_file_names PARAMS ((const char *));
 324 static source_t *find_source PARAMS ((const char *));
 325 static int read_graph_file PARAMS ((void));
 326 static int read_count_file PARAMS ((void));
 327 static void solve_flow_graph PARAMS ((function_t *));
 328 static void add_branch_counts PARAMS ((coverage_t *, const arc_t *));
 329 static void add_line_counts PARAMS ((coverage_t *, function_t *));
 330 static void function_summary PARAMS ((const coverage_t *, const char *));
 331 static const char *format_gcov PARAMS ((gcov_type, gcov_type, int));
 332 static void accumulate_line_counts PARAMS ((source_t *));
 333 static int output_branch_count PARAMS ((FILE *, int, const arc_t *));
 334 static void output_lines PARAMS ((FILE *, const source_t *));
 335 static char *make_gcov_file_name PARAMS ((const char *, const char *));
 336 static void release_structures PARAMS ((void));
 337 extern int main PARAMS ((int, char **));
 338
 339 int
 340 main (argc, argv)
 341      int argc;
 342      char **argv;
 343 {
 344   int argno;
 345
 346   gcc_init_libintl ();
 347
 348   argno = process_args (argc, argv);
 349   if (optind == argc)
 350     print_usage (true);
 351
 352   for (; argno != argc; argno++)
 353     {
 354       release_structures ();
 355
 356       process_file (argv[argno]);
 357     }
 358
 359   return 0;
 360 }
 361
 362 static void
 363 fnotice VPARAMS ((FILE *file, const char *msgid, ...))
 364 {
 365   VA_OPEN (ap, msgid);
 366   VA_FIXEDARG (ap, FILE *, file);
 367   VA_FIXEDARG (ap, const char *, msgid);
 368
 369   vfprintf (file, _(msgid), ap);
 370   VA_CLOSE (ap);
 371 }
 372
 373 /* More 'friendly' abort that prints the line and file.
 374    config.h can #define abort fancy_abort if you like that sort of thing.  */
 375 extern void fancy_abort PARAMS ((void)) ATTRIBUTE_NORETURN;
 376
 377 void
 378 fancy_abort ()
 379 {
 380   fnotice (stderr, "Internal gcov abort.\n");
 381   exit (FATAL_EXIT_CODE);
 382 }
 383 \f
 384 /* Print a usage message and exit.  If ERROR_P is nonzero, this is an error,
 385    otherwise the output of --help.  */
 386
 387 static void
 388 print_usage (error_p)
 389      int error_p;
 390 {
 391   FILE *file = error_p ? stderr : stdout;
 392   int status = error_p ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE;
 393
 394   fnotice (file, "Usage: gcov [OPTION]... SOURCEFILE\n\n");
 395   fnotice (file, "Print code coverage information.\n\n");
 396   fnotice (file, "  -h, --help                      Print this help, then exit\n");
 397   fnotice (file, "  -v, --version                   Print version number, then exit\n");
 398   fnotice (file, "  -a, --all-blocks                Show information for every basic block\n");
 399   fnotice (file, "  -b, --branch-probabilities      Include branch probabilities in output\n");
 400   fnotice (file, "  -c, --branch-counts             Given counts of branches taken\n\
 401                                     rather than percentages\n");
 402   fnotice (file, "  -n, --no-output                 Do not create an output file\n");
 403   fnotice (file, "  -l, --long-file-names           Use long output file names for included\n\
 404                                     source files\n");
 405   fnotice (file, "  -f, --function-summaries        Output summaries for each function\n");
 406   fnotice (file, "  -o, --object-directory DIR|FILE Search for object files in DIR or called FILE\n");
 407   fnotice (file, "  -p, --preserve-paths            Preserve all pathname components\n");
 408   fnotice (file, "  -u, --unconditional-branches    Show unconditional branch counts too\n");
 409   fnotice (file, "\nFor bug reporting instructions, please see:\n%s.\n",
 410            bug_report_url);
 411   exit (status);
 412 }
 413
 414 /* Print version information and exit.  */
 415
 416 static void
 417 print_version ()
 418 {
 419   char v[4];
 420   unsigned version = GCOV_VERSION;
 421   unsigned ix;
 422
 423   for (ix = 4; ix--; version >>= 8)
 424     v[ix] = version;
 425   fnotice (stdout, "gcov %.4s (GCC %s)\n", v, version_string);
 426   fnotice (stdout, "Copyright (C) 2002 Free Software Foundation, Inc.\n");
 427   fnotice (stdout,
 428            "This is free software; see the source for copying conditions.  There is NO\n\
 429 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\n");
 430   exit (SUCCESS_EXIT_CODE);
 431 }
 432
 433 static const struct option options[] =
 434 {
 435   { "help",                 no_argument,       NULL, 'h' },
 436   { "version",              no_argument,       NULL, 'v' },
 437   { "all-blocks",           no_argument,       NULL, 'a' },
 438   { "branch-probabilities", no_argument,       NULL, 'b' },
 439   { "branch-counts",        no_argument,       NULL, 'c' },
 440   { "no-output",            no_argument,       NULL, 'n' },
 441   { "long-file-names",      no_argument,       NULL, 'l' },
 442   { "function-summaries",   no_argument,       NULL, 'f' },
 443   { "preserve-paths",       no_argument,       NULL, 'p' },
 444   { "object-directory",     required_argument, NULL, 'o' },
 445   { "object-file",          required_argument, NULL, 'o' },
 446   { "unconditional-branches", no_argument,     NULL, 'u' },
 447 };
 448
 449 /* Process args, return index to first non-arg.  */
 450
 451 static int
 452 process_args (argc, argv)
 453      int argc;
 454      char **argv;
 455 {
 456   int opt;
 457
 458   while ((opt = getopt_long (argc, argv, "abcfhlno:puv", options, NULL)) != -1)
 459     {
 460       switch (opt)
 461         {
 462         case 'a':
 463           flag_all_blocks = 1;
 464           break;
 465         case 'b':
 466           flag_branches = 1;
 467           break;
 468         case 'c':
 469           flag_counts = 1;
 470           break;
 471         case 'f':
 472           flag_function_summary = 1;
 473           break;
 474         case 'h':
 475           print_usage (false);
 476           /* print_usage will exit.  */
 477         case 'l':
 478           flag_long_names = 1;
 479           break;
 480         case 'n':
 481           flag_gcov_file = 0;
 482           break;
 483         case 'o':
 484           object_directory = optarg;
 485           break;
 486         case 'p':
 487           flag_preserve_paths = 1;
 488           break;
 489         case 'u':
 490           flag_unconditional = 1;
 491           break;
 492         case 'v':
 493           print_version ();
 494           /* print_version will exit.  */
 495         default:
 496           print_usage (true);
 497           /* print_usage will exit.  */
 498         }
 499     }
 500
 501   return optind;
 502 }
 503
 504 /* Process a single source file.  */
 505
 506 static void
 507 process_file (file_name)
 508      const char *file_name;
 509 {
 510   source_t *src;
 511   function_t *fn;
 512
 513   create_file_names (file_name);
 514   if (read_graph_file ())
 515     return;
 516
 517   if (!functions)
 518     {
 519       fnotice (stderr, "%s:no functions found\n", bbg_file_name);
 520       return;
 521     }
 522
 523   if (read_count_file ())
 524     return;
 525
 526   for (fn = functions; fn; fn = fn->next)
 527     solve_flow_graph (fn);
 528   for (src = sources; src; src = src->next)
 529     src->lines = (line_t *) xcalloc (src->num_lines, sizeof (line_t));
 530   for (fn = functions; fn; fn = fn->next)
 531     {
 532       coverage_t coverage;
 533
 534       memset (&coverage, 0, sizeof (coverage));
 535       coverage.name = fn->name;
 536       add_line_counts (flag_function_summary ? &coverage : NULL, fn);
 537       if (flag_function_summary)
 538         {
 539           function_summary (&coverage, "Function");
 540           fnotice (stdout, "\n");
 541         }
 542     }
 543
 544   for (src = sources; src; src = src->next)
 545     {
 546       accumulate_line_counts (src);
 547       function_summary (&src->coverage, "File");
 548       if (flag_gcov_file)
 549         {
 550           char *gcov_file_name = make_gcov_file_name (file_name, src->name);
 551           FILE *gcov_file = fopen (gcov_file_name, "w");
 552
 553           if (gcov_file)
 554             {
 555               fnotice (stdout, "%s:creating `%s'\n",
 556                        src->name, gcov_file_name);
 557               output_lines (gcov_file, src);
 558               if (ferror (gcov_file))
 559                     fnotice (stderr, "%s:error writing output file `%s'\n",
 560                              src->name, gcov_file_name);
 561               fclose (gcov_file);
 562             }
 563           else
 564             fnotice (stderr, "%s:could not open output file `%s'\n",
 565                      src->name, gcov_file_name);
 566           free (gcov_file_name);
 567         }
 568       fnotice (stdout, "\n");
 569     }
 570 }
 571
 572 /* Release all memory used.  */
 573
 574 static void
 575 release_structures ()
 576 {
 577   function_t *fn;
 578   source_t *src;
 579
 580   free (bbg_file_name);
 581   free (da_file_name);
 582   da_file_name = bbg_file_name = NULL;
 583   bbg_file_time = 0;
 584
 585   while ((src = sources))
 586     {
 587       sources = src->next;
 588
 589       free (src->name);
 590       free (src->lines);
 591     }
 592
 593   while ((fn = functions))
 594     {
 595       unsigned ix;
 596       block_t *block;
 597
 598       functions = fn->next;
 599       for (ix = fn->num_blocks, block = fn->blocks; ix--; block++)
 600         {
 601           arc_t *arc, *arc_n;
 602
 603           for (arc = block->succ; arc; arc = arc_n)
 604             {
 605               arc_n = arc->succ_next;
 606               free (arc);
 607             }
 608         }
 609       free (fn->blocks);
 610       free (fn->counts);
 611     }
 612 }
 613
 614 /* Generate the names of the graph and data files. If OBJECT_DIRECTORY
 615    is not specified, these are looked for in the current directory,
 616    and named from the basename of the FILE_NAME sans extension. If
 617    OBJECT_DIRECTORY is specified and is a directory, the files are in
 618    that directory, but named from the basename of the FILE_NAME, sans
 619    extension. Otherwise OBJECT_DIRECTORY is taken to be the name of
 620    the object *file*, and the data files are named from that.  */
 621
 622 static void
 623 create_file_names (file_name)
 624      const char *file_name;
 625 {
 626   char *cptr;
 627   char *name;
 628   int length = strlen (file_name);
 629   int base;
 630
 631   if (object_directory && object_directory[0])
 632     {
 633       struct stat status;
 634
 635       length += strlen (object_directory) + 2;
 636       name = xmalloc (length);
 637       name[0] = 0;
 638
 639       base = !stat (object_directory, &status) && S_ISDIR (status.st_mode);
 640       strcat (name, object_directory);
 641       if (base && name[strlen (name) - 1] != '/')
 642         strcat (name, "/");
 643     }
 644   else
 645     {
 646       name = xmalloc (length + 1);
 647       name[0] = 0;
 648       base = 1;
 649     }
 650
 651   if (base)
 652     {
 653       /* Append source file name */
 654       cptr = strrchr (file_name, '/');
 655       strcat (name, cptr ? cptr + 1 : file_name);
 656     }
 657
 658   /* Remove the extension.  */
 659   cptr = strrchr (name, '.');
 660   if (cptr)
 661     *cptr = 0;
 662
 663   length = strlen (name);
 664
 665   bbg_file_name = xmalloc (length + strlen (GCOV_GRAPH_SUFFIX) + 1);
 666   strcpy (bbg_file_name, name);
 667   strcpy (bbg_file_name + length, GCOV_GRAPH_SUFFIX);
 668
 669   da_file_name = xmalloc (length + strlen (GCOV_DATA_SUFFIX) + 1);
 670   strcpy (da_file_name, name);
 671   strcpy (da_file_name + length, GCOV_DATA_SUFFIX);
 672
 673   return;
 674 }
 675
 676 /* Find or create a source file structure for FILE_NAME. Copies
 677    FILE_NAME on creation */
 678
 679 static source_t *
 680 find_source (file_name)
 681      const char *file_name;
 682 {
 683   source_t *src;
 684
 685   if (!file_name)
 686     file_name = "<unknown>";
 687
 688   for (src = sources; src; src = src->next)
 689     if (!strcmp (file_name, src->name))
 690       return src;
 691
 692   src = (source_t *)xcalloc (1, sizeof (source_t));
 693   src->name = xstrdup (file_name);
 694   src->coverage.name = src->name;
 695   src->index = sources ? sources->index + 1 : 1;
 696   src->next = sources;
 697   sources = src;
 698
 699   return src;
 700 }
 701
 702 /* Read the graph file. Return nonzero on fatal error.  */
 703
 704 static int
 705 read_graph_file ()
 706 {
 707   unsigned version;
 708   unsigned current_tag = 0;
 709   struct function_info *fn = NULL;
 710   source_t *src = NULL;
 711   unsigned ix;
 712
 713   if (!gcov_open (bbg_file_name, 1))
 714     {
 715       fnotice (stderr, "%s:cannot open graph file\n", bbg_file_name);
 716       return 1;
 717     }
 718   bbg_file_time = gcov_time ();
 719   if (gcov_read_unsigned () != GCOV_GRAPH_MAGIC)
 720     {
 721       fnotice (stderr, "%s:not a gcov graph file\n", bbg_file_name);
 722       gcov_close ();
 723       return 1;
 724     }
 725
 726   version = gcov_read_unsigned ();
 727   if (version != GCOV_VERSION)
 728     {
 729       char v[4], e[4];
 730       unsigned required = GCOV_VERSION;
 731
 732       for (ix = 4; ix--; required >>= 8, version >>= 8)
 733         {
 734           v[ix] = version;
 735           e[ix] = required;
 736         }
 737       fnotice (stderr, "%s:version `%.4s', prefer `%.4s'\n",
 738                bbg_file_name, v, e);
 739     }
 740
 741   while (!gcov_is_eof ())
 742     {
 743       unsigned tag = gcov_read_unsigned ();
 744       unsigned length = gcov_read_unsigned ();
 745       unsigned long base = gcov_position ();
 746
 747       if (tag == GCOV_TAG_FUNCTION)
 748         {
 749           char *function_name;
 750           unsigned checksum, lineno;
 751           source_t *src;
 752           function_t *probe, *prev;
 753
 754           function_name = xstrdup (gcov_read_string ());
 755           checksum = gcov_read_unsigned ();
 756           src = find_source (gcov_read_string ());
 757           lineno = gcov_read_unsigned ();
 758
 759           fn = (function_t *)xcalloc (1, sizeof (function_t));
 760           fn->name = function_name;
 761           fn->checksum = checksum;
 762           fn->src = src;
 763           fn->line = lineno;
 764
 765           fn->next = functions;
 766           functions = fn;
 767           current_tag = tag;
 768
 769           if (lineno >= src->num_lines)
 770             src->num_lines = lineno + 1;
 771           /* Now insert it into the source file's list of
 772              functions. Normally functions will be encountered in
 773              ascending order, so a simple scan is quick.  */
 774           for (probe = src->functions, prev = NULL;
 775                probe && probe->line > lineno;
 776                prev = probe, probe = probe->line_next)
 777             continue;
 778           fn->line_next = probe;
 779           if (prev)
 780             prev->line_next = fn;
 781           else
 782             src->functions = fn;
 783         }
 784       else if (fn && tag == GCOV_TAG_BLOCKS)
 785         {
 786           if (fn->blocks)
 787             fnotice (stderr, "%s:already seen blocks for `%s'\n",
 788                      bbg_file_name, fn->name);
 789           else
 790             {
 791               unsigned ix, num_blocks = length / 4;
 792               fn->num_blocks = num_blocks;
 793
 794               fn->blocks
 795                 = (block_t *)xcalloc (fn->num_blocks, sizeof (block_t));
 796               for (ix = 0; ix != num_blocks; ix++)
 797                 fn->blocks[ix].flags = gcov_read_unsigned ();
 798             }
 799         }
 800       else if (fn && tag == GCOV_TAG_ARCS)
 801         {
 802           unsigned src = gcov_read_unsigned ();
 803           unsigned num_dests = (length - 4) / 8;
 804
 805           if (src >= fn->num_blocks || fn->blocks[src].succ)
 806             goto corrupt;
 807
 808           while (num_dests--)
 809             {
 810               struct arc_info *arc;
 811               unsigned dest = gcov_read_unsigned ();
 812               unsigned flags = gcov_read_unsigned ();
 813
 814               if (dest >= fn->num_blocks)
 815                 goto corrupt;
 816               arc = (arc_t *) xcalloc (1, sizeof (arc_t));
 817
 818               arc->dst = &fn->blocks[dest];
 819               arc->src = &fn->blocks[src];
 820
 821               arc->count = 0;
 822               arc->count_valid = 0;
 823               arc->on_tree = !!(flags & GCOV_ARC_ON_TREE);
 824               arc->fake = !!(flags & GCOV_ARC_FAKE);
 825               arc->fall_through = !!(flags & GCOV_ARC_FALLTHROUGH);
 826
 827               arc->succ_next = fn->blocks[src].succ;
 828               fn->blocks[src].succ = arc;
 829               fn->blocks[src].num_succ++;
 830
 831               arc->pred_next = fn->blocks[dest].pred;
 832               fn->blocks[dest].pred = arc;
 833               fn->blocks[dest].num_pred++;
 834
 835               if (arc->fake)
 836                 {
 837                   if (src)
 838                     {
 839                       /* Exceptional exit from this function, the
 840                          source block must be a call.  */
 841                       fn->blocks[src].is_call_site = 1;
 842                       arc->is_call_non_return = 1;
 843                     }
 844                   else
 845                     {
 846                       /* Non-local return from a callee of this
 847                          function. The destination block is a catch or
 848                          setjmp.  */
 849                       arc->is_nonlocal_return = 1;
 850                       fn->blocks[dest].is_nonlocal_return = 1;
 851                     }
 852                 }
 853
 854               if (!arc->on_tree)
 855                 fn->num_counts++;
 856             }
 857         }
 858       else if (fn && tag == GCOV_TAG_LINES)
 859         {
 860           unsigned blockno = gcov_read_unsigned ();
 861           unsigned *line_nos
 862             = (unsigned *)xcalloc ((length - 4) / 4, sizeof (unsigned));
 863
 864           if (blockno >= fn->num_blocks || fn->blocks[blockno].u.line.encoding)
 865             goto corrupt;
 866
 867           for (ix = 0; ;  )
 868             {
 869               unsigned lineno = gcov_read_unsigned ();
 870
 871               if (lineno)
 872                 {
 873                   if (!ix)
 874                     {
 875                       line_nos[ix++] = 0;
 876                       line_nos[ix++] = src->index;
 877                     }
 878                   line_nos[ix++] = lineno;
 879                   if (lineno >= src->num_lines)
 880                     src->num_lines = lineno + 1;
 881                 }
 882               else
 883                 {
 884                   const char *file_name = gcov_read_string ();
 885
 886                   if (!file_name)
 887                     break;
 888                   src = find_source (file_name);
 889
 890                   line_nos[ix++] = 0;
 891                   line_nos[ix++] = src->index;
 892                 }
 893             }
 894
 895           fn->blocks[blockno].u.line.encoding = line_nos;
 896           fn->blocks[blockno].u.line.num = ix;
 897         }
 898       else if (current_tag && !GCOV_TAG_IS_SUBTAG (current_tag, tag))
 899         {
 900           fn = NULL;
 901           current_tag = 0;
 902         }
 903       gcov_seek (base, length);
 904       if (gcov_is_error ())
 905         {
 906         corrupt:;
 907           fnotice (stderr, "%s:corrupted\n", bbg_file_name);
 908           gcov_close ();
 909           return 1;
 910         }
 911     }
 912   gcov_close ();
 913
 914   /* We built everything backwards, so nreverse them all */
 915
 916   /* Reverse sources. Not strictly necessary, but we'll then process
 917      them in the 'expected' order.  */
 918   {
 919     source_t *src, *src_p, *src_n;
 920
 921     for (src_p = NULL, src = sources; src; src_p = src, src = src_n)
 922       {
 923         src_n = src->next;
 924         src->next = src_p;
 925       }
 926     sources =  src_p;
 927   }
 928
 929   /* Reverse functions.  */
 930   {
 931     function_t *fn, *fn_p, *fn_n;
 932
 933     for (fn_p = NULL, fn = functions; fn; fn_p = fn, fn = fn_n)
 934       {
 935         unsigned ix;
 936
 937         fn_n = fn->next;
 938         fn->next = fn_p;
 939
 940         /* Reverse the arcs */
 941         for (ix = fn->num_blocks; ix--;)
 942           {
 943             arc_t *arc, *arc_p, *arc_n;
 944
 945             for (arc_p = NULL, arc = fn->blocks[ix].succ; arc;
 946                  arc_p = arc, arc = arc_n)
 947               {
 948                 arc_n = arc->succ_next;
 949                 arc->succ_next = arc_p;
 950               }
 951             fn->blocks[ix].succ = arc_p;
 952
 953             for (arc_p = NULL, arc = fn->blocks[ix].pred; arc;
 954                  arc_p = arc, arc = arc_n)
 955               {
 956                 arc_n = arc->pred_next;
 957                 arc->pred_next = arc_p;
 958               }
 959             fn->blocks[ix].pred = arc_p;
 960           }
 961       }
 962     functions = fn_p;
 963   }
 964   return 0;
 965 }
 966
 967 /* Reads profiles from the count file and attach to each
 968    function. Return nonzero if fatal error.  */
 969
 970 static int
 971 read_count_file ()
 972 {
 973   unsigned ix;
 974   unsigned version;
 975   function_t *fn = NULL;
 976
 977   if (!gcov_open (da_file_name, 1))
 978     {
 979       fnotice (stderr, "%s:cannot open data file\n", da_file_name);
 980       return 1;
 981     }
 982   if (gcov_read_unsigned () != GCOV_DATA_MAGIC)
 983     {
 984       fnotice (stderr, "%s:not a gcov data file\n", da_file_name);
 985     cleanup:;
 986       gcov_close ();
 987       return 1;
 988     }
 989   version = gcov_read_unsigned ();
 990   if (version != GCOV_VERSION)
 991     {
 992       char v[4], e[4];
 993       unsigned desired = GCOV_VERSION;
 994
 995       for (ix = 4; ix--; desired >>= 8, version >>= 8)
 996         {
 997           v[ix] = version;
 998           e[ix] = desired;
 999         }
1000       fnotice (stderr, "%s:version `%.4s', prefer version `%.4s'\n",
1001                da_file_name, v, e);
1002     }
1003
1004   while (!gcov_is_eof ())
1005     {
1006       unsigned tag = gcov_read_unsigned ();
1007       unsigned length = gcov_read_unsigned ();
1008       unsigned long base = gcov_position ();
1009       int error;
1010
1011       if (tag == GCOV_TAG_OBJECT_SUMMARY)
1012         gcov_read_summary (&object_summary);
1013       else if (tag == GCOV_TAG_PROGRAM_SUMMARY
1014                || tag == GCOV_TAG_INCORRECT_SUMMARY)
1015         program_count++;
1016       else if (tag == GCOV_TAG_FUNCTION)
1017         {
1018           const char *function_name = gcov_read_string ();
1019           struct function_info *fn_n = functions;
1020
1021           for (fn = fn ? fn->next : NULL; ; fn = fn->next)
1022             {
1023               if (fn)
1024                 ;
1025               else if ((fn = fn_n))
1026                 fn_n = NULL;
1027               else
1028                 {
1029                   fnotice (stderr, "%s:unknown function `%s'\n",
1030                            da_file_name, function_name);
1031                   break;
1032                 }
1033               if (!strcmp (fn->name, function_name))
1034                 break;
1035             }
1036
1037           if (!fn)
1038             ;
1039           else if (gcov_read_unsigned () != fn->checksum)
1040             {
1041             mismatch:;
1042               fnotice (stderr, "%s:profile mismatch for `%s'\n",
1043                        da_file_name, fn->name);
1044               goto cleanup;
1045             }
1046         }
1047       else if (tag == GCOV_TAG_ARC_COUNTS && fn)
1048         {
1049           if (length != 8 * fn->num_counts)
1050             goto mismatch;
1051
1052           if (!fn->counts)
1053             fn->counts
1054               = (gcov_type *)xcalloc (fn->num_counts, sizeof (gcov_type));
1055
1056           for (ix = 0; ix != fn->num_counts; ix++)
1057             fn->counts[ix] += gcov_read_counter ();
1058         }
1059       gcov_seek (base, length);
1060       if ((error = gcov_is_error ()))
1061         {
1062           fnotice (stderr, error < 0
1063                    ? "%s:overflowed\n" : "%s:corrupted\n", da_file_name);
1064           goto cleanup;
1065         }
1066     }
1067
1068   gcov_close ();
1069   return 0;
1070 }
1071
1072 /* Solve the flow graph. Propagate counts from the instrumented arcs
1073    to the blocks and the uninstrumented arcs.  */
1074
1075 static void
1076 solve_flow_graph (fn)
1077      function_t *fn;
1078 {
1079   unsigned ix;
1080   arc_t *arc;
1081   gcov_type *count_ptr = fn->counts;
1082   block_t *blk;
1083   block_t *valid_blocks = NULL;    /* valid, but unpropagated blocks.  */
1084   block_t *invalid_blocks = NULL;  /* invalid, but inferable blocks.  */
1085
1086   if (fn->num_blocks < 2)
1087     fnotice (stderr, "%s:`%s' lacks entry and/or exit blocks\n",
1088              bbg_file_name, fn->name);
1089   else
1090     {
1091       if (fn->blocks[0].num_pred)
1092         fnotice (stderr, "%s:`%s' has arcs to entry block\n",
1093                  bbg_file_name, fn->name);
1094       else
1095         /* We can't deduce the entry block counts from the lack of
1096            predecessors.  */
1097         fn->blocks[0].num_pred = ~(unsigned)0;
1098
1099       if (fn->blocks[fn->num_blocks - 1].num_succ)
1100         fnotice (stderr, "%s:`%s' has arcs from exit block\n",
1101                  bbg_file_name, fn->name);
1102       else
1103         /* Likewise, we can't deduce exit block counts from the lack
1104            of its successors.  */
1105         fn->blocks[fn->num_blocks - 1].num_succ = ~(unsigned)0;
1106     }
1107
1108   /* Propagate the measured counts, this must be done in the same
1109      order as the code in profile.c  */
1110   for (ix = 0, blk = fn->blocks; ix != fn->num_blocks; ix++, blk++)
1111     {
1112       block_t const *prev_dst = NULL;
1113       int out_of_order = 0;
1114       int non_fake_succ = 0;
1115
1116       for (arc = blk->succ; arc; arc = arc->succ_next)
1117         {
1118           if (!arc->fake)
1119             non_fake_succ++;
1120
1121           if (!arc->on_tree)
1122             {
1123               if (count_ptr)
1124                 arc->count = *count_ptr++;
1125               arc->count_valid = 1;
1126               blk->num_succ--;
1127               arc->dst->num_pred--;
1128             }
1129           if (prev_dst && prev_dst > arc->dst)
1130             out_of_order = 1;
1131           prev_dst = arc->dst;
1132         }
1133       if (non_fake_succ == 1)
1134         {
1135           /* If there is only one non-fake exit, it is an
1136              unconditional branch.  */
1137           for (arc = blk->succ; arc; arc = arc->succ_next)
1138             if (!arc->fake)
1139               {
1140                 arc->is_unconditional = 1;
1141                 /* If this block is instrumenting a call, it might be
1142                    an artifical block. It is not artificial if it has
1143                    a non-fallthrough exit, or the destination of this
1144                    arc has more than one entry.  Mark the destination
1145                    block as a return site, if none of those conditions
1146                    hold.  */
1147                 if (blk->is_call_site && arc->fall_through
1148                     && arc->dst->pred == arc && !arc->pred_next)
1149                   arc->dst->is_call_return = 1;
1150               }
1151         }
1152
1153       /* Sort the successor arcs into ascending dst order. profile.c
1154          normally produces arcs in the right order, but sometimes with
1155          one or two out of order.  We're not using a particularly
1156          smart sort.  */
1157       if (out_of_order)
1158         {
1159           arc_t *start = blk->succ;
1160           unsigned changes = 1;
1161
1162           while (changes)
1163             {
1164               arc_t *arc, *arc_p, *arc_n;
1165
1166               changes = 0;
1167               for (arc_p = NULL, arc = start; (arc_n = arc->succ_next);)
1168                 {
1169                   if (arc->dst > arc_n->dst)
1170                     {
1171                       changes = 1;
1172                       if (arc_p)
1173                         arc_p->succ_next = arc_n;
1174                       else
1175                         start = arc_n;
1176                       arc->succ_next = arc_n->succ_next;
1177                       arc_n->succ_next = arc;
1178                       arc_p = arc_n;
1179                     }
1180                   else
1181                     {
1182                       arc_p = arc;
1183                       arc = arc_n;
1184                     }
1185                 }
1186             }
1187           blk->succ = start;
1188         }
1189
1190       /* Place it on the invalid chain, it will be ignored if that's
1191          wrong.  */
1192       blk->invalid_chain = 1;
1193       blk->chain = invalid_blocks;
1194       invalid_blocks = blk;
1195     }
1196
1197   while (invalid_blocks || valid_blocks)
1198     {
1199       while ((blk = invalid_blocks))
1200         {
1201           gcov_type total = 0;
1202           const arc_t *arc;
1203
1204           invalid_blocks = blk->chain;
1205           blk->invalid_chain = 0;
1206           if (!blk->num_succ)
1207             for (arc = blk->succ; arc; arc = arc->succ_next)
1208               total += arc->count;
1209           else if (!blk->num_pred)
1210             for (arc = blk->pred; arc; arc = arc->pred_next)
1211               total += arc->count;
1212           else
1213             continue;
1214
1215           blk->count = total;
1216           blk->count_valid = 1;
1217           blk->chain = valid_blocks;
1218           blk->valid_chain = 1;
1219           valid_blocks = blk;
1220         }
1221       while ((blk = valid_blocks))
1222         {
1223           gcov_type total;
1224           arc_t *arc, *inv_arc;
1225
1226           valid_blocks = blk->chain;
1227           blk->valid_chain = 0;
1228           if (blk->num_succ == 1)
1229             {
1230               block_t *dst;
1231
1232               total = blk->count;
1233               inv_arc = NULL;
1234               for (arc = blk->succ; arc; arc = arc->succ_next)
1235                 {
1236                   total -= arc->count;
1237                   if (!arc->count_valid)
1238                     inv_arc = arc;
1239                 }
1240               dst = inv_arc->dst;
1241               inv_arc->count_valid = 1;
1242               inv_arc->count = total;
1243               blk->num_succ--;
1244               dst->num_pred--;
1245               if (dst->count_valid)
1246                 {
1247                   if (dst->num_pred == 1 && !dst->valid_chain)
1248                     {
1249                       dst->chain = valid_blocks;
1250                       dst->valid_chain = 1;
1251                       valid_blocks = dst;
1252                     }
1253                 }
1254               else
1255                 {
1256                   if (!dst->num_pred && !dst->invalid_chain)
1257                     {
1258                       dst->chain = invalid_blocks;
1259                       dst->invalid_chain = 1;
1260                       invalid_blocks = dst;
1261                     }
1262                 }
1263             }
1264           if (blk->num_pred == 1)
1265             {
1266               block_t *src;
1267
1268               total = blk->count;
1269               inv_arc = NULL;
1270               for (arc = blk->pred; arc; arc = arc->pred_next)
1271                 {
1272                   total -= arc->count;
1273                   if (!arc->count_valid)
1274                     inv_arc = arc;
1275                 }
1276               src = inv_arc->src;
1277               inv_arc->count_valid = 1;
1278               inv_arc->count = total;
1279               blk->num_pred--;
1280               src->num_succ--;
1281               if (src->count_valid)
1282                 {
1283                   if (src->num_succ == 1 && !src->valid_chain)
1284                     {
1285                       src->chain = valid_blocks;
1286                       src->valid_chain = 1;
1287                       valid_blocks = src;
1288                     }
1289                 }
1290               else
1291                 {
1292                   if (!src->num_succ && !src->invalid_chain)
1293                     {
1294                       src->chain = invalid_blocks;
1295                       src->invalid_chain = 1;
1296                       invalid_blocks = src;
1297                     }
1298                 }
1299             }
1300         }
1301     }
1302
1303   /* If the graph has been correctly solved, every block will have a
1304      valid count.  */
1305   for (ix = 0; ix < fn->num_blocks; ix++)
1306     if (!fn->blocks[ix].count_valid)
1307       {
1308         fnotice (stderr, "%s:graph is unsolvable for `%s'\n",
1309                  bbg_file_name, fn->name);
1310         break;
1311       }
1312 }
1313
1314 \f
1315
1316 /* Increment totals in COVERAGE according to arc ARC.  */
1317
1318 static void
1319 add_branch_counts (coverage, arc)
1320      coverage_t *coverage;
1321      const arc_t *arc;
1322 {
1323   if (arc->is_call_non_return)
1324     {
1325       coverage->calls++;
1326       if (arc->src->count)
1327         coverage->calls_executed++;
1328     }
1329   else if (!arc->is_unconditional)
1330     {
1331       coverage->branches++;
1332       if (arc->src->count)
1333         coverage->branches_executed++;
1334       if (arc->count)
1335         coverage->branches_taken++;
1336     }
1337 }
1338
1339 /* Format a HOST_WIDE_INT as either a percent ratio, or absolute
1340    count.  If dp >= 0, format TOP/BOTTOM * 100 to DP decimal places.
1341    If DP is zero, no decimal point is printed. Only print 100% when
1342    TOP==BOTTOM and only print 0% when TOP=0.  If dp < 0, then simply
1343    format TOP.  Return pointer to a static string.  */
1344
1345 static char const *
1346 format_gcov (top, bottom, dp)
1347      gcov_type top, bottom;
1348      int dp;
1349 {
1350   static char buffer[20];
1351
1352   if (dp >= 0)
1353     {
1354       float ratio = bottom ? (float)top / bottom : 0;
1355       int ix;
1356       unsigned limit = 100;
1357       unsigned percent;
1358
1359       for (ix = dp; ix--; )
1360         limit *= 10;
1361
1362       percent = (unsigned) (ratio * limit + (float)0.5);
1363       if (percent <= 0 && top)
1364         percent = 1;
1365       else if (percent >= limit && top != bottom)
1366         percent = limit - 1;
1367       ix = sprintf (buffer, "%.*u%%", dp + 1, percent);
1368       if (dp)
1369         {
1370           dp++;
1371           do
1372             {
1373               buffer[ix+1] = buffer[ix];
1374               ix--;
1375             }
1376           while (dp--);
1377           buffer[ix + 1] = '.';
1378         }
1379     }
1380   else
1381     sprintf (buffer, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT)top);
1382
1383   return buffer;
1384 }
1385
1386
1387 /* Output summary info for a function.  */
1388
1389 static void
1390 function_summary (coverage, title)
1391      const coverage_t *coverage;
1392      const char *title;
1393 {
1394   fnotice (stdout, "%s `%s'\n", title, coverage->name);
1395
1396   if (coverage->lines)
1397     fnotice (stdout, "Lines executed:%s of %d\n",
1398              format_gcov (coverage->lines_executed, coverage->lines, 2),
1399              coverage->lines);
1400   else
1401     fnotice (stdout, "No executable lines");
1402
1403   if (flag_branches)
1404     {
1405       if (coverage->branches)
1406         {
1407           fnotice (stdout, "Branches executed:%s of %d\n",
1408                    format_gcov (coverage->branches_executed,
1409                                 coverage->branches, 2),
1410                    coverage->branches);
1411           fnotice (stdout, "Taken at least once:%s of %d\n",
1412                    format_gcov (coverage->branches_taken,
1413                                 coverage->branches, 2),
1414                    coverage->branches);
1415         }
1416       else
1417         fnotice (stdout, "No branches\n");
1418       if (coverage->calls)
1419         fnotice (stdout, "Calls executed:%s of %d\n",
1420                  format_gcov (coverage->calls_executed, coverage->calls, 2),
1421                  coverage->calls);
1422       else
1423         fnotice (stdout, "No calls\n");
1424     }
1425 }
1426
1427 /* Generate an output file name. LONG_OUTPUT_NAMES and PRESERVE_PATHS
1428    affect name generation. With preserve_paths we create a filename
1429    from all path components of the source file, replacing '/' with
1430    '#', without it we simply take the basename component. With
1431    long_output_names we prepend the processed name of the input file
1432    to each output name (except when the current source file is the
1433    input file, so you don't get a double concatenation). The two
1434    components are separated by '##'. Also '.' filename components are
1435    removed and '..'  components are renamed to '^'.  */
1436
1437 static char *
1438 make_gcov_file_name (input_name, src_name)
1439      const char *input_name;
1440      const char *src_name;
1441 {
1442   char *cptr;
1443   char *name = xmalloc (strlen (src_name) + strlen (input_name) + 10);
1444
1445   name[0] = 0;
1446   if (flag_long_names && strcmp (src_name, input_name))
1447     {
1448       /* Generate the input filename part.  */
1449       cptr = flag_preserve_paths ? NULL : strrchr (input_name, '/');
1450       strcat (name, cptr ? cptr + 1 : input_name);
1451       strcat (name, "##");
1452     }
1453
1454   /* Generate the source filename part.  */
1455   cptr = flag_preserve_paths ? NULL : strrchr (src_name, '/');
1456   strcat (name, cptr ? cptr + 1 : src_name);
1457
1458   if (flag_preserve_paths)
1459     {
1460       /* Convert '/' to '#', remove '/./', convert '/../' to '/^/' */
1461       char *prev;
1462
1463       for (cptr = name; (cptr = strchr ((prev = cptr), '/'));)
1464         {
1465           unsigned shift = 0;
1466
1467           if (prev + 1 == cptr && prev[0] == '.')
1468             {
1469               /* Remove '.' */
1470               shift = 2;
1471             }
1472           else if (prev + 2 == cptr && prev[0] == '.' && prev[1] == '.')
1473             {
1474               /* Convert '..' */
1475               shift = 1;
1476               prev[1] = '^';
1477             }
1478           else
1479             *cptr++ = '#';
1480           if (shift)
1481             {
1482               cptr = prev;
1483               do
1484                 prev[0] = prev[shift];
1485               while (*prev++);
1486             }
1487         }
1488     }
1489
1490   strcat (name, ".gcov");
1491   return name;
1492 }
1493
1494 /* Scan through the bb_data for each line in the block, increment
1495    the line number execution count indicated by the execution count of
1496    the appropriate basic block.  */
1497
1498 static void
1499 add_line_counts (coverage, fn)
1500      coverage_t *coverage;
1501      function_t *fn;
1502 {
1503   unsigned ix;
1504   line_t *line = NULL; /* this is propagated from one iteration to the
1505                           next.  */
1506
1507   /* Scan each basic block.  */
1508   for (ix = 0; ix != fn->num_blocks; ix++)
1509     {
1510       block_t *block = &fn->blocks[ix];
1511       unsigned *encoding;
1512       const source_t *src = NULL;
1513       unsigned jx;
1514
1515       if (block->count && ix && ix + 1 != fn->num_blocks)
1516         fn->blocks_executed++;
1517       for (jx = 0, encoding = block->u.line.encoding;
1518            jx != block->u.line.num; jx++, encoding++)
1519         if (!*encoding)
1520           {
1521             unsigned src_n = *++encoding;
1522
1523             for (src = sources; src->index != src_n; src = src->next)
1524               continue;
1525             jx++;
1526           }
1527         else
1528           {
1529             line = &src->lines[*encoding];
1530
1531             if (coverage)
1532               {
1533                 if (!line->exists)
1534                   coverage->lines++;
1535                 if (!line->count && block->count)
1536                   coverage->lines_executed++;
1537               }
1538             line->exists = 1;
1539             line->count += block->count;
1540           }
1541       free (block->u.line.encoding);
1542       block->u.cycle.arc = NULL;
1543       block->u.cycle.ident = ~0U;
1544
1545       if (!ix || ix + 1 == fn->num_blocks)
1546         /* Entry or exit block */;
1547       else if (flag_all_blocks)
1548         {
1549           line_t *block_line = line ? line : &fn->src->lines[fn->line];
1550
1551           block->chain = block_line->u.blocks;
1552           block_line->u.blocks = block;
1553         }
1554       else if (flag_branches)
1555         {
1556           arc_t *arc;
1557
1558           for (arc = block->succ; arc; arc = arc->succ_next)
1559             {
1560               arc->line_next = line->u.branches;
1561               line->u.branches = arc;
1562               if (coverage && !arc->is_unconditional)
1563                 add_branch_counts (coverage, arc);
1564             }
1565         }
1566     }
1567   if (!line)
1568     fnotice (stderr, "%s:no lines for `%s'\n", bbg_file_name, fn->name);
1569 }
1570
1571 /* Accumulate the line counts of a file.  */
1572
1573 static void
1574 accumulate_line_counts (src)
1575      source_t *src;
1576 {
1577   line_t *line;
1578   function_t *fn, *fn_p, *fn_n;
1579   unsigned ix;
1580
1581   /* Reverse the function order.  */
1582   for (fn = src->functions, fn_p = NULL; fn;
1583        fn_p = fn, fn = fn_n)
1584     {
1585       fn_n = fn->line_next;
1586       fn->line_next = fn_p;
1587     }
1588   src->functions = fn_p;
1589
1590   for (ix = src->num_lines, line = src->lines; ix--; line++)
1591     {
1592       if (!flag_all_blocks)
1593         {
1594           arc_t *arc, *arc_p, *arc_n;
1595
1596           /* Total and reverse the branch information.  */
1597           for (arc = line->u.branches, arc_p = NULL; arc;
1598                arc_p = arc, arc = arc_n)
1599             {
1600               arc_n = arc->line_next;
1601               arc->line_next = arc_p;
1602
1603               add_branch_counts (&src->coverage, arc);
1604             }
1605           line->u.branches = arc_p;
1606         }
1607       else if (line->u.blocks)
1608         {
1609           /* The user expects the line count to be the number of times
1610              a line has been executed. Simply summing the block count
1611              will give an artificially high number.  The Right Thing
1612              is to sum the entry counts to the graph of blocks on this
1613              line, then find the elementary cycles of the local graph
1614              and add the transition counts of those cycles.  */
1615           block_t *block, *block_p, *block_n;
1616           gcov_type count = 0;
1617
1618           /* Reverse the block information */
1619           for (block = line->u.blocks, block_p = NULL; block;
1620                block_p = block, block = block_n)
1621             {
1622               block_n = block->chain;
1623               block->chain = block_p;
1624               block->u.cycle.ident = ix;
1625             }
1626           line->u.blocks = block_p;
1627
1628           /* Sum the entry arcs.  */
1629           for (block = line->u.blocks; block; block = block->chain)
1630             {
1631               arc_t *arc;
1632
1633               for (arc = block->pred; arc; arc = arc->pred_next)
1634                 {
1635                   if (arc->src->u.cycle.ident != ix)
1636                     count += arc->count;
1637                   if (flag_branches)
1638                     add_branch_counts (&src->coverage, arc);
1639                 }
1640             }
1641
1642           /* Find the loops. This uses the algorithm described in
1643              Tiernan 'An Efficient Search Algorithm to Find the
1644              Elementary Circuits of a Graph', CACM Dec 1970. We hold
1645              the P array by having each block point to the arc that
1646              connects to the previous block. The H array is implicitly
1647              held because of the arc ordering, and the block's
1648              previous arc pointer.
1649
1650              Although the algorithm is O(N^3) for highly connected
1651              graphs, at worst we'll have O(N^2), as most blocks have
1652              only one or two exits. Most graphs will be small.
1653
1654              For each loop we find, locate the arc with the smallest
1655              transition count, and add that to the cumulative
1656              count. Remove the arc from consideration.  */
1657           for (block = line->u.blocks; block; block = block->chain)
1658             {
1659               block_t *head = block;
1660               arc_t *arc;
1661
1662             next_vertex:;
1663               arc = head->succ;
1664             current_vertex:;
1665               while (arc)
1666                 {
1667                   block_t *dst = arc->dst;
1668                   if (/* Already used that arc.  */
1669                       arc->cycle
1670                       /* Not to same graph, or before first vertex.  */
1671                       || dst->u.cycle.ident != ix
1672                       /* Already in path.  */
1673                       || dst->u.cycle.arc)
1674                     {
1675                       arc = arc->succ_next;
1676                       continue;
1677                     }
1678
1679                   if (dst == block)
1680                     {
1681                       /* Found a closing arc.  */
1682                       gcov_type cycle_count = arc->count;
1683                       arc_t *cycle_arc = arc;
1684                       arc_t *probe_arc;
1685
1686                       /* Locate the smallest arc count of the loop. */
1687                       for (dst = head; (probe_arc = dst->u.cycle.arc);
1688                            dst = probe_arc->src)
1689                         if (cycle_count > probe_arc->count)
1690                           {
1691                             cycle_count = probe_arc->count;
1692                             cycle_arc = probe_arc;
1693                           }
1694
1695                       count += cycle_count;
1696                       cycle_arc->cycle = 1;
1697                       /* Unwind to the cyclic arc.  */
1698                       while (head != cycle_arc->src)
1699                         {
1700                           arc = head->u.cycle.arc;
1701                           head = arc->src;
1702                         }
1703                       /* Move on.  */
1704                       arc = arc->succ_next;
1705                       continue;
1706                     }
1707
1708                   /* Add new block to chain.  */
1709                   dst->u.cycle.arc = arc;
1710                   head = dst;
1711                   goto next_vertex;
1712                 }
1713               /* We could not add another vertex to the path. Remove
1714                  the last vertex from the list.  */
1715               arc = head->u.cycle.arc;
1716               if (arc)
1717                 {
1718                   /* It was not the first vertex. Move onto next arc. */
1719                   head->u.cycle.arc = NULL;
1720                   head = arc->src;
1721                   arc = arc->succ_next;
1722                   goto current_vertex;
1723                 }
1724               /* Mark this block as unusable.  */
1725               block->u.cycle.ident = ~0U;
1726             }
1727
1728           line->count = count;
1729         }
1730
1731       if (line->exists)
1732         {
1733           src->coverage.lines++;
1734           if (line->count)
1735             src->coverage.lines_executed++;
1736         }
1737     }
1738 }
1739
1740 /* Ouput information about ARC number IX.  Returns non-zero if
1741    anything is output.  */
1742
1743 static int
1744 output_branch_count (gcov_file, ix, arc)
1745      FILE *gcov_file;
1746      int ix;
1747      const arc_t *arc;
1748 {
1749
1750   if (arc->is_call_non_return)
1751     {
1752       if (arc->src->count)
1753         {
1754           fnotice (gcov_file, "call   %2d returned %s\n", ix,
1755                    format_gcov (arc->src->count - arc->count,
1756                                 arc->src->count, -flag_counts));
1757         }
1758       else
1759         fnotice (gcov_file, "call   %2d never executed\n", ix);
1760     }
1761   else if (!arc->is_unconditional)
1762     {
1763       if (arc->src->count)
1764         fnotice (gcov_file, "branch %2d taken %s%s\n", ix,
1765                  format_gcov (arc->count, arc->src->count, -flag_counts),
1766                  arc->fall_through ? " (fallthrough)" : "");
1767       else
1768         fnotice (gcov_file, "branch %2d never executed\n", ix);
1769     }
1770   else if (flag_unconditional && !arc->dst->is_call_return)
1771     {
1772       if (arc->src->count)
1773         fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
1774                  format_gcov (arc->count, arc->src->count, -flag_counts));
1775       else
1776         fnotice (gcov_file, "unconditional %2d never executed\n", ix);
1777     }
1778   else
1779     return 0;
1780   return 1;
1781
1782 }
1783
1784 /* Read in the source file one line at a time, and output that line to
1785    the gcov file preceded by its execution count and other
1786    information.  */
1787
1788 static void
1789 output_lines (gcov_file, src)
1790      FILE *gcov_file;
1791      const source_t *src;
1792 {
1793   FILE *source_file;
1794   unsigned line_num;            /* current line number.  */
1795   const line_t *line;           /* current line info ptr.  */
1796   char string[STRING_SIZE];     /* line buffer.  */
1797   char const *retval = "";      /* status of source file reading.  */
1798   function_t *fn = src->functions;
1799
1800   fprintf (gcov_file, "%9s:%5d:Source:%s\n", "-", 0, src->name);
1801   fprintf (gcov_file, "%9s:%5d:Graph:%s\n", "-", 0, bbg_file_name);
1802   fprintf (gcov_file, "%9s:%5d:Data:%s\n", "-", 0, da_file_name);
1803   fprintf (gcov_file, "%9s:%5d:Runs:%u\n", "-", 0, object_summary.runs);
1804   fprintf (gcov_file, "%9s:%5d:Programs:%u\n", "-", 0, program_count);
1805
1806   source_file = fopen (src->name, "r");
1807   if (!source_file)
1808     {
1809       fnotice (stderr, "%s:cannot open source file\n", src->name);
1810       retval = NULL;
1811     }
1812   else
1813     {
1814       struct stat status;
1815
1816       if (!fstat (fileno (source_file), &status)
1817           && status.st_mtime > bbg_file_time)
1818         {
1819           fnotice (stderr, "%s:source file is newer than graph file `%s'\n",
1820                    src->name, bbg_file_name);
1821           fprintf (gcov_file, "%9s:%5d:Source is newer than graph\n",
1822                    "-", 0);
1823         }
1824     }
1825
1826   for (line_num = 1, line = &src->lines[line_num];
1827        line_num < src->num_lines; line_num++, line++)
1828     {
1829       for (; fn && fn->line == line_num; fn = fn->line_next)
1830         {
1831           arc_t *arc = fn->blocks[fn->num_blocks - 1].pred;
1832           gcov_type return_count = fn->blocks[fn->num_blocks - 1].count;
1833
1834           for (; arc; arc = arc->pred_next)
1835             if (arc->fake)
1836               return_count -= arc->count;
1837
1838           fprintf (gcov_file, "function %s", fn->name);
1839           fprintf (gcov_file, " called %s",
1840                    format_gcov (fn->blocks[0].count, 0, -1));
1841           fprintf (gcov_file, " returned %s",
1842                    format_gcov (return_count, fn->blocks[0].count, 0));
1843           fprintf (gcov_file, " blocks executed %s",
1844                    format_gcov (fn->blocks_executed, fn->num_blocks - 2, 0));
1845           fprintf (gcov_file, "\n");
1846         }
1847
1848       /* For lines which don't exist in the .bb file, print '-' before
1849          the source line.  For lines which exist but were never
1850          executed, print '#####' before the source line.  Otherwise,
1851          print the execution count before the source line.  There are
1852          16 spaces of indentation added before the source line so that
1853          tabs won't be messed up.  */
1854       fprintf (gcov_file, "%9s:%5u:",
1855                !line->exists ? "-" : !line->count ? "#####"
1856                : format_gcov (line->count, 0, -1), line_num);
1857
1858       if (retval)
1859         {
1860           /* Copy source line.  */
1861           do
1862             {
1863               retval = fgets (string, STRING_SIZE, source_file);
1864               if (!retval)
1865                 {
1866                   fnotice (stderr, "%s:unexpected EOF\n", src->name);
1867                   break;
1868                 }
1869               fputs (retval, gcov_file);
1870             }
1871           while (!retval[0] || retval[strlen (retval) - 1] != '\n');
1872         }
1873       if (!retval)
1874         fputs ("??\n", gcov_file);
1875
1876       if (flag_all_blocks)
1877         {
1878           block_t *block;
1879           arc_t *arc;
1880           int ix, jx;
1881
1882           for (ix = jx = 0, block = line->u.blocks; block;
1883                block = block->chain)
1884             {
1885               if (!block->is_call_return)
1886                 fprintf (gcov_file, "%9s:%5u-block %2d\n",
1887                          !line->exists ? "-" : !block->count ? "$$$$$"
1888                          : format_gcov (block->count, 0, -1),
1889                          line_num, ix++);
1890               if (flag_branches)
1891                 for (arc = block->succ; arc; arc = arc->succ_next)
1892                   jx += output_branch_count (gcov_file, jx, arc);
1893             }
1894         }
1895       else if (flag_branches)
1896         {
1897           int ix;
1898           arc_t *arc;
1899
1900           for (ix = 0, arc = line->u.branches; arc; arc = arc->line_next)
1901             ix += output_branch_count (gcov_file, ix, arc);
1902         }
1903     }
1904
1905   /* Handle all remaining source lines.  There may be lines after the
1906      last line of code.  */
1907   if (retval)
1908     {
1909       for (; (retval = fgets (string, STRING_SIZE, source_file)); line_num++)
1910         {
1911           fprintf (gcov_file, "%9s:%5u:%s", "-", line_num, retval);
1912
1913           while (!retval[0] || retval[strlen (retval) - 1] != '\n')
1914             {
1915               retval = fgets (string, STRING_SIZE, source_file);
1916               if (!retval)
1917                 break;
1918               fputs (retval, gcov_file);
1919             }
1920         }
1921     }
1922
1923   if (source_file)
1924     fclose (source_file);
1925 }