gcc/gcov.c

   1 /* Gcov.c: prepend line execution counts and branch probabilities to a
   2    source file.
   3    Copyright (C) 1990-2016 Free Software Foundation, Inc.
   4    Contributed by James E. Wilson of Cygnus Support.
   5    Mangled by Bob Manson of Cygnus Support.
   6    Mangled further by Nathan Sidwell <nathan@codesourcery.com>
   7
   8 Gcov is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 Gcov is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with Gcov; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* ??? Print a list of the ten blocks with the highest execution counts,
  23    and list the line numbers corresponding to those blocks.  Also, perhaps
  24    list the line numbers with the highest execution counts, only printing
  25    the first if there are several which are all listed in the same block.  */
  26
  27 /* ??? Should have an option to print the number of basic blocks, and the
  28    percent of them that are covered.  */
  29
  30 /* Need an option to show individual block counts, and show
  31    probabilities of fall through arcs.  */
  32
  33 #include "config.h"
  34 #include "system.h"
  35 #include "coretypes.h"
  36 #include "tm.h"
  37 #include "intl.h"
  38 #include "diagnostic.h"
  39 #include "version.h"
  40 #include "demangle.h"
  41
  42 #include <getopt.h>
  43
  44 #define IN_GCOV 1
  45 #include "gcov-io.h"
  46 #include "gcov-io.c"
  47
  48 /* The gcno file is generated by -ftest-coverage option. The gcda file is
  49    generated by a program compiled with -fprofile-arcs. Their formats
  50    are documented in gcov-io.h.  */
  51
  52 /* The functions in this file for creating and solution program flow graphs
  53    are very similar to functions in the gcc source file profile.c.  In
  54    some places we make use of the knowledge of how profile.c works to
  55    select particular algorithms here.  */
  56
  57 /* The code validates that the profile information read in corresponds
  58    to the code currently being compiled.  Rather than checking for
  59    identical files, the code below compares a checksum on the CFG
  60    (based on the order of basic blocks and the arcs in the CFG).  If
  61    the CFG checksum in the gcda file match the CFG checksum in the
  62    gcno file, the profile data will be used.  */
  63
  64 /* This is the size of the buffer used to read in source file lines.  */
  65
  66 struct function_info;
  67 struct block_info;
  68 struct source_info;
  69
  70 /* Describes an arc between two basic blocks.  */
  71
  72 typedef struct arc_info
  73 {
  74   /* source and destination blocks.  */
  75   struct block_info *src;
  76   struct block_info *dst;
  77
  78   /* transition counts.  */
  79   gcov_type count;
  80   /* used in cycle search, so that we do not clobber original counts.  */
  81   gcov_type cs_count;
  82
  83   unsigned int count_valid : 1;
  84   unsigned int on_tree : 1;
  85   unsigned int fake : 1;
  86   unsigned int fall_through : 1;
  87
  88   /* Arc to a catch handler.  */
  89   unsigned int is_throw : 1;
  90
  91   /* Arc is for a function that abnormally returns.  */
  92   unsigned int is_call_non_return : 1;
  93
  94   /* Arc is for catch/setjmp.  */
  95   unsigned int is_nonlocal_return : 1;
  96
  97   /* Is an unconditional branch.  */
  98   unsigned int is_unconditional : 1;
  99
 100   /* Loop making arc.  */
 101   unsigned int cycle : 1;
 102
 103   /* Next branch on line.  */
 104   struct arc_info *line_next;
 105
 106   /* Links to next arc on src and dst lists.  */
 107   struct arc_info *succ_next;
 108   struct arc_info *pred_next;
 109 } arc_t;
 110
 111 /* Describes a basic block. Contains lists of arcs to successor and
 112    predecessor blocks.  */
 113
 114 typedef struct block_info
 115 {
 116   /* Chain of exit and entry arcs.  */
 117   arc_t *succ;
 118   arc_t *pred;
 119
 120   /* Number of unprocessed exit and entry arcs.  */
 121   gcov_type num_succ;
 122   gcov_type num_pred;
 123
 124   /* Block execution count.  */
 125   gcov_type count;
 126   unsigned flags : 12;
 127   unsigned count_valid : 1;
 128   unsigned valid_chain : 1;
 129   unsigned invalid_chain : 1;
 130   unsigned exceptional : 1;
 131
 132   /* Block is a call instrumenting site.  */
 133   unsigned is_call_site : 1; /* Does the call.  */
 134   unsigned is_call_return : 1; /* Is the return.  */
 135
 136   /* Block is a landing pad for longjmp or throw.  */
 137   unsigned is_nonlocal_return : 1;
 138
 139   union
 140   {
 141     struct
 142     {
 143      /* Array of line numbers and source files. source files are
 144         introduced by a linenumber of zero, the next 'line number' is
 145         the number of the source file.  Always starts with a source
 146         file.  */
 147       unsigned *encoding;
 148       unsigned num;
 149     } line; /* Valid until blocks are linked onto lines */
 150     struct
 151     {
 152       /* Single line graph cycle workspace.  Used for all-blocks
 153          mode.  */
 154       arc_t *arc;
 155       unsigned ident;
 156     } cycle; /* Used in all-blocks mode, after blocks are linked onto
 157                lines.  */
 158   } u;
 159
 160   /* Temporary chain for solving graph, and for chaining blocks on one
 161      line.  */
 162   struct block_info *chain;
 163
 164 } block_t;
 165
 166 /* Describes a single function. Contains an array of basic blocks.  */
 167
 168 typedef struct function_info
 169 {
 170   /* Name of function.  */
 171   char *name;
 172   char *demangled_name;
 173   unsigned ident;
 174   unsigned lineno_checksum;
 175   unsigned cfg_checksum;
 176
 177   /* The graph contains at least one fake incoming edge.  */
 178   unsigned has_catch : 1;
 179
 180   /* Array of basic blocks.  Like in GCC, the entry block is
 181      at blocks[0] and the exit block is at blocks[1].  */
 182 #define ENTRY_BLOCK (0)
 183 #define EXIT_BLOCK (1)
 184   block_t *blocks;
 185   unsigned num_blocks;
 186   unsigned blocks_executed;
 187
 188   /* Raw arc coverage counts.  */
 189   gcov_type *counts;
 190   unsigned num_counts;
 191
 192   /* First line number & file.  */
 193   unsigned line;
 194   unsigned src;
 195
 196   /* Next function in same source file.  */
 197   struct function_info *line_next;
 198
 199   /* Next function.  */
 200   struct function_info *next;
 201 } function_t;
 202
 203 /* Describes coverage of a file or function.  */
 204
 205 typedef struct coverage_info
 206 {
 207   int lines;
 208   int lines_executed;
 209
 210   int branches;
 211   int branches_executed;
 212   int branches_taken;
 213
 214   int calls;
 215   int calls_executed;
 216
 217   char *name;
 218 } coverage_t;
 219
 220 /* Describes a single line of source. Contains a chain of basic blocks
 221    with code on it.  */
 222
 223 typedef struct line_info
 224 {
 225   gcov_type count;         /* execution count */
 226   union
 227   {
 228     arc_t *branches;       /* branches from blocks that end on this
 229                               line. Used for branch-counts when not
 230                               all-blocks mode.  */
 231     block_t *blocks;       /* blocks which start on this line.  Used
 232                               in all-blocks mode.  */
 233   } u;
 234   unsigned exists : 1;
 235   unsigned unexceptional : 1;
 236 } line_t;
 237
 238 /* Describes a file mentioned in the block graph.  Contains an array
 239    of line info.  */
 240
 241 typedef struct source_info
 242 {
 243   /* Canonical name of source file.  */
 244   char *name;
 245   time_t file_time;
 246
 247   /* Array of line information.  */
 248   line_t *lines;
 249   unsigned num_lines;
 250
 251   coverage_t coverage;
 252
 253   /* Functions in this source file.  These are in ascending line
 254      number order.  */
 255   function_t *functions;
 256 } source_t;
 257
 258 typedef struct name_map
 259 {
 260   char *name;  /* Source file name */
 261   unsigned src;  /* Source file */
 262 } name_map_t;
 263
 264 /* Holds a list of function basic block graphs.  */
 265
 266 static function_t *functions;
 267 static function_t **fn_end = &functions;
 268
 269 static source_t *sources;   /* Array of source files  */
 270 static unsigned n_sources;  /* Number of sources */
 271 static unsigned a_sources;  /* Allocated sources */
 272
 273 static name_map_t *names;   /* Mapping of file names to sources */
 274 static unsigned n_names;    /* Number of names */
 275 static unsigned a_names;    /* Allocated names */
 276
 277 /* This holds data summary information.  */
 278
 279 static unsigned object_runs;
 280 static unsigned program_count;
 281
 282 static unsigned total_lines;
 283 static unsigned total_executed;
 284
 285 /* Modification time of graph file.  */
 286
 287 static time_t bbg_file_time;
 288
 289 /* Name of the notes (gcno) output file.  The "bbg" prefix is for
 290    historical reasons, when the notes file contained only the
 291    basic block graph notes.  */
 292
 293 static char *bbg_file_name;
 294
 295 /* Stamp of the bbg file */
 296 static unsigned bbg_stamp;
 297
 298 /* Name and file pointer of the input file for the count data (gcda).  */
 299
 300 static char *da_file_name;
 301
 302 /* Data file is missing.  */
 303
 304 static int no_data_file;
 305
 306 /* If there is several input files, compute and display results after
 307    reading all data files.  This way if two or more gcda file refer to
 308    the same source file (eg inline subprograms in a .h file), the
 309    counts are added.  */
 310
 311 static int multiple_files = 0;
 312
 313 /* Output branch probabilities.  */
 314
 315 static int flag_branches = 0;
 316
 317 /* Show unconditional branches too.  */
 318 static int flag_unconditional = 0;
 319
 320 /* Output a gcov file if this is true.  This is on by default, and can
 321    be turned off by the -n option.  */
 322
 323 static int flag_gcov_file = 1;
 324
 325 /* Output progress indication if this is true.  This is off by default
 326    and can be turned on by the -d option.  */
 327
 328 static int flag_display_progress = 0;
 329
 330 /* Output *.gcov file in intermediate format used by 'lcov'.  */
 331
 332 static int flag_intermediate_format = 0;
 333
 334 /* Output demangled function names.  */
 335
 336 static int flag_demangled_names = 0;
 337
 338 /* For included files, make the gcov output file name include the name
 339    of the input source file.  For example, if x.h is included in a.c,
 340    then the output file name is a.c##x.h.gcov instead of x.h.gcov.  */
 341
 342 static int flag_long_names = 0;
 343
 344 /* Output count information for every basic block, not merely those
 345    that contain line number information.  */
 346
 347 static int flag_all_blocks = 0;
 348
 349 /* Output summary info for each function.  */
 350
 351 static int flag_function_summary = 0;
 352
 353 /* Object directory file prefix.  This is the directory/file where the
 354    graph and data files are looked for, if nonzero.  */
 355
 356 static char *object_directory = 0;
 357
 358 /* Source directory prefix.  This is removed from source pathnames
 359    that match, when generating the output file name.  */
 360
 361 static char *source_prefix = 0;
 362 static size_t source_length = 0;
 363
 364 /* Only show data for sources with relative pathnames.  Absolute ones
 365    usually indicate a system header file, which although it may
 366    contain inline functions, is usually uninteresting.  */
 367 static int flag_relative_only = 0;
 368
 369 /* Preserve all pathname components. Needed when object files and
 370    source files are in subdirectories. '/' is mangled as '#', '.' is
 371    elided and '..' mangled to '^'.  */
 372
 373 static int flag_preserve_paths = 0;
 374
 375 /* Output the number of times a branch was taken as opposed to the percentage
 376    of times it was taken.  */
 377
 378 static int flag_counts = 0;
 379
 380 /* Forward declarations.  */
 381 static int process_args (int, char **);
 382 static void print_usage (int) ATTRIBUTE_NORETURN;
 383 static void print_version (void) ATTRIBUTE_NORETURN;
 384 static void process_file (const char *);
 385 static void generate_results (const char *);
 386 static void create_file_names (const char *);
 387 static int name_search (const void *, const void *);
 388 static int name_sort (const void *, const void *);
 389 static char *canonicalize_name (const char *);
 390 static unsigned find_source (const char *);
 391 static function_t *read_graph_file (void);
 392 static int read_count_file (function_t *);
 393 static void solve_flow_graph (function_t *);
 394 static void find_exception_blocks (function_t *);
 395 static void add_branch_counts (coverage_t *, const arc_t *);
 396 static void add_line_counts (coverage_t *, function_t *);
 397 static void executed_summary (unsigned, unsigned);
 398 static void function_summary (const coverage_t *, const char *);
 399 static const char *format_gcov (gcov_type, gcov_type, int);
 400 static void accumulate_line_counts (source_t *);
 401 static void output_gcov_file (const char *, source_t *);
 402 static int output_branch_count (FILE *, int, const arc_t *);
 403 static void output_lines (FILE *, const source_t *);
 404 static char *make_gcov_file_name (const char *, const char *);
 405 static char *mangle_name (const char *, char *);
 406 static void release_structures (void);
 407 static void release_function (function_t *);
 408 extern int main (int, char **);
 409
 410 int
 411 main (int argc, char **argv)
 412 {
 413   int argno;
 414   int first_arg;
 415   const char *p;
 416
 417   p = argv[0] + strlen (argv[0]);
 418   while (p != argv[0] && !IS_DIR_SEPARATOR (p[-1]))
 419     --p;
 420   progname = p;
 421
 422   xmalloc_set_program_name (progname);
 423
 424   /* Unlock the stdio streams.  */
 425   unlock_std_streams ();
 426
 427   gcc_init_libintl ();
 428
 429   diagnostic_initialize (global_dc, 0);
 430
 431   /* Handle response files.  */
 432   expandargv (&argc, &argv);
 433
 434   a_names = 10;
 435   names = XNEWVEC (name_map_t, a_names);
 436   a_sources = 10;
 437   sources = XNEWVEC (source_t, a_sources);
 438
 439   argno = process_args (argc, argv);
 440   if (optind == argc)
 441     print_usage (true);
 442
 443   if (argc - argno > 1)
 444     multiple_files = 1;
 445
 446   first_arg = argno;
 447
 448   for (; argno != argc; argno++)
 449     {
 450       if (flag_display_progress)
 451         printf ("Processing file %d out of %d\n",
 452                 argno - first_arg + 1, argc - first_arg);
 453       process_file (argv[argno]);
 454     }
 455
 456   generate_results (multiple_files ? NULL : argv[argc - 1]);
 457
 458   release_structures ();
 459
 460   return 0;
 461 }
 462 \f
 463 /* Print a usage message and exit.  If ERROR_P is nonzero, this is an error,
 464    otherwise the output of --help.  */
 465
 466 static void
 467 print_usage (int error_p)
 468 {
 469   FILE *file = error_p ? stderr : stdout;
 470   int status = error_p ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE;
 471
 472   fnotice (file, "Usage: gcov [OPTION]... SOURCE|OBJ...\n\n");
 473   fnotice (file, "Print code coverage information.\n\n");
 474   fnotice (file, "  -h, --help                      Print this help, then exit\n");
 475   fnotice (file, "  -a, --all-blocks                Show information for every basic block\n");
 476   fnotice (file, "  -b, --branch-probabilities      Include branch probabilities in output\n");
 477   fnotice (file, "  -c, --branch-counts             Output counts of branches taken\n\
 478                                     rather than percentages\n");
 479   fnotice (file, "  -d, --display-progress          Display progress information\n");
 480   fnotice (file, "  -f, --function-summaries        Output summaries for each function\n");
 481   fnotice (file, "  -i, --intermediate-format       Output .gcov file in intermediate text format\n");
 482   fnotice (file, "  -l, --long-file-names           Use long output file names for included\n\
 483                                     source files\n");
 484   fnotice (file, "  -m, --demangled-names           Output demangled function names\n");
 485   fnotice (file, "  -n, --no-output                 Do not create an output file\n");
 486   fnotice (file, "  -o, --object-directory DIR|FILE Search for object files in DIR or called FILE\n");
 487   fnotice (file, "  -p, --preserve-paths            Preserve all pathname components\n");
 488   fnotice (file, "  -r, --relative-only             Only show data for relative sources\n");
 489   fnotice (file, "  -s, --source-prefix DIR         Source prefix to elide\n");
 490   fnotice (file, "  -u, --unconditional-branches    Show unconditional branch counts too\n");
 491   fnotice (file, "  -v, --version                   Print version number, then exit\n");
 492   fnotice (file, "\nFor bug reporting instructions, please see:\n%s.\n",
 493            bug_report_url);
 494   exit (status);
 495 }
 496
 497 /* Print version information and exit.  */
 498
 499 static void
 500 print_version (void)
 501 {
 502   fnotice (stdout, "gcov %s%s\n", pkgversion_string, version_string);
 503   fprintf (stdout, "Copyright %s 2016 Free Software Foundation, Inc.\n",
 504            _("(C)"));
 505   fnotice (stdout,
 506            _("This is free software; see the source for copying conditions.\n"
 507              "There is NO warranty; not even for MERCHANTABILITY or \n"
 508              "FITNESS FOR A PARTICULAR PURPOSE.\n\n"));
 509   exit (SUCCESS_EXIT_CODE);
 510 }
 511
 512 static const struct option options[] =
 513 {
 514   { "help",                 no_argument,       NULL, 'h' },
 515   { "version",              no_argument,       NULL, 'v' },
 516   { "all-blocks",           no_argument,       NULL, 'a' },
 517   { "branch-probabilities", no_argument,       NULL, 'b' },
 518   { "branch-counts",        no_argument,       NULL, 'c' },
 519   { "intermediate-format",  no_argument,       NULL, 'i' },
 520   { "no-output",            no_argument,       NULL, 'n' },
 521   { "long-file-names",      no_argument,       NULL, 'l' },
 522   { "function-summaries",   no_argument,       NULL, 'f' },
 523   { "demangled-names",      no_argument,       NULL, 'm' },
 524   { "preserve-paths",       no_argument,       NULL, 'p' },
 525   { "relative-only",        no_argument,       NULL, 'r' },
 526   { "object-directory",     required_argument, NULL, 'o' },
 527   { "object-file",          required_argument, NULL, 'o' },
 528   { "source-prefix",        required_argument, NULL, 's' },
 529   { "unconditional-branches", no_argument,     NULL, 'u' },
 530   { "display-progress",     no_argument,       NULL, 'd' },
 531   { 0, 0, 0, 0 }
 532 };
 533
 534 /* Process args, return index to first non-arg.  */
 535
 536 static int
 537 process_args (int argc, char **argv)
 538 {
 539   int opt;
 540
 541   while ((opt = getopt_long (argc, argv, "abcdfhilmno:s:pruv", options, NULL)) !=
 542          -1)
 543     {
 544       switch (opt)
 545         {
 546         case 'a':
 547           flag_all_blocks = 1;
 548           break;
 549         case 'b':
 550           flag_branches = 1;
 551           break;
 552         case 'c':
 553           flag_counts = 1;
 554           break;
 555         case 'f':
 556           flag_function_summary = 1;
 557           break;
 558         case 'h':
 559           print_usage (false);
 560           /* print_usage will exit.  */
 561         case 'l':
 562           flag_long_names = 1;
 563           break;
 564         case 'm':
 565           flag_demangled_names = 1;
 566           break;
 567         case 'n':
 568           flag_gcov_file = 0;
 569           break;
 570         case 'o':
 571           object_directory = optarg;
 572           break;
 573         case 's':
 574           source_prefix = optarg;
 575           source_length = strlen (source_prefix);
 576           break;
 577         case 'r':
 578           flag_relative_only = 1;
 579           break;
 580         case 'p':
 581           flag_preserve_paths = 1;
 582           break;
 583         case 'u':
 584           flag_unconditional = 1;
 585           break;
 586         case 'i':
 587           flag_intermediate_format = 1;
 588           flag_gcov_file = 1;
 589           break;
 590         case 'd':
 591           flag_display_progress = 1;
 592           break;
 593         case 'v':
 594           print_version ();
 595           /* print_version will exit.  */
 596         default:
 597           print_usage (true);
 598           /* print_usage will exit.  */
 599         }
 600     }
 601
 602   return optind;
 603 }
 604
 605 /* Get the name of the gcov file.  The return value must be free'd.
 606
 607    It appends the '.gcov' extension to the *basename* of the file.
 608    The resulting file name will be in PWD.
 609
 610    e.g.,
 611    input: foo.da,       output: foo.da.gcov
 612    input: a/b/foo.cc,   output: foo.cc.gcov  */
 613
 614 static char *
 615 get_gcov_intermediate_filename (const char *file_name)
 616 {
 617   const char *gcov = ".gcov";
 618   char *result;
 619   const char *cptr;
 620
 621   /* Find the 'basename'.  */
 622   cptr = lbasename (file_name);
 623
 624   result = XNEWVEC (char, strlen (cptr) + strlen (gcov) + 1);
 625   sprintf (result, "%s%s", cptr, gcov);
 626
 627   return result;
 628 }
 629
 630 /* Output the result in intermediate format used by 'lcov'.
 631
 632 The intermediate format contains a single file named 'foo.cc.gcov',
 633 with no source code included. A sample output is
 634
 635 file:foo.cc
 636 function:5,1,_Z3foov
 637 function:13,1,main
 638 function:19,1,_GLOBAL__sub_I__Z3foov
 639 function:19,1,_Z41__static_initialization_and_destruction_0ii
 640 lcount:5,1
 641 lcount:7,9
 642 lcount:9,8
 643 lcount:11,1
 644 file:/.../iostream
 645 lcount:74,1
 646 file:/.../basic_ios.h
 647 file:/.../ostream
 648 file:/.../ios_base.h
 649 function:157,0,_ZStorSt12_Ios_IostateS_
 650 lcount:157,0
 651 file:/.../char_traits.h
 652 function:258,0,_ZNSt11char_traitsIcE6lengthEPKc
 653 lcount:258,0
 654 ...
 655
 656 The default gcov outputs multiple files: 'foo.cc.gcov',
 657 'iostream.gcov', 'ios_base.h.gcov', etc. with source code
 658 included. Instead the intermediate format here outputs only a single
 659 file 'foo.cc.gcov' similar to the above example. */
 660
 661 static void
 662 output_intermediate_file (FILE *gcov_file, source_t *src)
 663 {
 664   unsigned line_num;    /* current line number.  */
 665   const line_t *line;   /* current line info ptr.  */
 666   function_t *fn;       /* current function info ptr. */
 667
 668   fprintf (gcov_file, "file:%s\n", src->name);    /* source file name */
 669
 670   for (fn = src->functions; fn; fn = fn->line_next)
 671     {
 672       /* function:<name>,<line_number>,<execution_count> */
 673       fprintf (gcov_file, "function:%d,%s,%s\n", fn->line,
 674                format_gcov (fn->blocks[0].count, 0, -1),
 675                flag_demangled_names ? fn->demangled_name : fn->name);
 676     }
 677
 678   for (line_num = 1, line = &src->lines[line_num];
 679        line_num < src->num_lines;
 680        line_num++, line++)
 681     {
 682       arc_t *arc;
 683       if (line->exists)
 684         fprintf (gcov_file, "lcount:%u,%s\n", line_num,
 685                  format_gcov (line->count, 0, -1));
 686       if (flag_branches)
 687         for (arc = line->u.branches; arc; arc = arc->line_next)
 688           {
 689             if (!arc->is_unconditional && !arc->is_call_non_return)
 690               {
 691                 const char *branch_type;
 692                 /* branch:<line_num>,<branch_coverage_type>
 693                    branch_coverage_type
 694                      : notexec (Branch not executed)
 695                      : taken (Branch executed and taken)
 696                      : nottaken (Branch executed, but not taken)
 697                 */
 698                 if (arc->src->count)
 699                   branch_type = (arc->count > 0) ? "taken" : "nottaken";
 700                 else
 701                   branch_type = "notexec";
 702                 fprintf (gcov_file, "branch:%d,%s\n", line_num, branch_type);
 703               }
 704           }
 705     }
 706 }
 707
 708
 709 /* Process a single input file.  */
 710
 711 static void
 712 process_file (const char *file_name)
 713 {
 714   function_t *fns;
 715
 716   create_file_names (file_name);
 717   fns = read_graph_file ();
 718   if (!fns)
 719     return;
 720
 721   read_count_file (fns);
 722   while (fns)
 723     {
 724       function_t *fn = fns;
 725
 726       fns = fn->next;
 727       fn->next = NULL;
 728       if (fn->counts)
 729         {
 730           unsigned src = fn->src;
 731           unsigned line = fn->line;
 732           unsigned block_no;
 733           function_t *probe, **prev;
 734
 735           /* Now insert it into the source file's list of
 736              functions. Normally functions will be encountered in
 737              ascending order, so a simple scan is quick.  Note we're
 738              building this list in reverse order.  */
 739           for (prev = &sources[src].functions;
 740                (probe = *prev); prev = &probe->line_next)
 741             if (probe->line <= line)
 742               break;
 743           fn->line_next = probe;
 744           *prev = fn;
 745
 746           /* Mark last line in files touched by function.  */
 747           for (block_no = 0; block_no != fn->num_blocks; block_no++)
 748             {
 749               unsigned *enc = fn->blocks[block_no].u.line.encoding;
 750               unsigned num = fn->blocks[block_no].u.line.num;
 751
 752               for (; num--; enc++)
 753                 if (!*enc)
 754                   {
 755                     if (enc[1] != src)
 756                       {
 757                         if (line >= sources[src].num_lines)
 758                           sources[src].num_lines = line + 1;
 759                         line = 0;
 760                         src = enc[1];
 761                       }
 762                     enc++;
 763                     num--;
 764                   }
 765                 else if (*enc > line)
 766                   line = *enc;
 767             }
 768           if (line >= sources[src].num_lines)
 769             sources[src].num_lines = line + 1;
 770
 771           solve_flow_graph (fn);
 772           if (fn->has_catch)
 773             find_exception_blocks (fn);
 774           *fn_end = fn;
 775           fn_end = &fn->next;
 776         }
 777       else
 778         /* The function was not in the executable -- some other
 779            instance must have been selected.  */
 780         release_function (fn);
 781     }
 782 }
 783
 784 static void
 785 output_gcov_file (const char *file_name, source_t *src)
 786 {
 787   char *gcov_file_name = make_gcov_file_name (file_name, src->coverage.name);
 788
 789   if (src->coverage.lines)
 790     {
 791       FILE *gcov_file = fopen (gcov_file_name, "w");
 792       if (gcov_file)
 793         {
 794           fnotice (stdout, "Creating '%s'\n", gcov_file_name);
 795           output_lines (gcov_file, src);
 796           if (ferror (gcov_file))
 797             fnotice (stderr, "Error writing output file '%s'\n", gcov_file_name);
 798           fclose (gcov_file);
 799         }
 800       else
 801         fnotice (stderr, "Could not open output file '%s'\n", gcov_file_name);
 802     }
 803   else
 804     {
 805       unlink (gcov_file_name);
 806       fnotice (stdout, "Removing '%s'\n", gcov_file_name);
 807     }
 808   free (gcov_file_name);
 809 }
 810
 811 static void
 812 generate_results (const char *file_name)
 813 {
 814   unsigned ix;
 815   source_t *src;
 816   function_t *fn;
 817   FILE *gcov_intermediate_file = NULL;
 818   char *gcov_intermediate_filename = NULL;
 819
 820   for (ix = n_sources, src = sources; ix--; src++)
 821     if (src->num_lines)
 822       src->lines = XCNEWVEC (line_t, src->num_lines);
 823
 824   for (fn = functions; fn; fn = fn->next)
 825     {
 826       coverage_t coverage;
 827
 828       memset (&coverage, 0, sizeof (coverage));
 829       coverage.name = flag_demangled_names ? fn->demangled_name : fn->name;
 830       add_line_counts (flag_function_summary ? &coverage : NULL, fn);
 831       if (flag_function_summary)
 832         {
 833           function_summary (&coverage, "Function");
 834           fnotice (stdout, "\n");
 835         }
 836     }
 837
 838   if (file_name)
 839     {
 840       name_map_t *name_map = (name_map_t *)bsearch
 841         (file_name, names, n_names, sizeof (*names), name_search);
 842       if (name_map)
 843         file_name = sources[name_map->src].coverage.name;
 844       else
 845         file_name = canonicalize_name (file_name);
 846     }
 847
 848   if (flag_gcov_file && flag_intermediate_format)
 849     {
 850       /* Open the intermediate file.  */
 851       gcov_intermediate_filename =
 852         get_gcov_intermediate_filename (file_name);
 853       gcov_intermediate_file = fopen (gcov_intermediate_filename, "w");
 854       if (!gcov_intermediate_file)
 855         {
 856           fnotice (stderr, "Cannot open intermediate output file %s\n",
 857                    gcov_intermediate_filename);
 858           return;
 859         }
 860     }
 861
 862   for (ix = n_sources, src = sources; ix--; src++)
 863     {
 864       if (flag_relative_only)
 865         {
 866           /* Ignore this source, if it is an absolute path (after
 867              source prefix removal).  */
 868           char first = src->coverage.name[0];
 869
 870 #if HAVE_DOS_BASED_FILE_SYSTEM
 871           if (first && src->coverage.name[1] == ':')
 872             first = src->coverage.name[2];
 873 #endif
 874           if (IS_DIR_SEPARATOR (first))
 875             continue;
 876         }
 877
 878       accumulate_line_counts (src);
 879       function_summary (&src->coverage, "File");
 880       total_lines += src->coverage.lines;
 881       total_executed += src->coverage.lines_executed;
 882       if (flag_gcov_file)
 883         {
 884           if (flag_intermediate_format)
 885             /* Output the intermediate format without requiring source
 886                files.  This outputs a section to a *single* file.  */
 887             output_intermediate_file (gcov_intermediate_file, src);
 888           else
 889             output_gcov_file (file_name, src);
 890           fnotice (stdout, "\n");
 891         }
 892     }
 893
 894   if (flag_gcov_file && flag_intermediate_format)
 895     {
 896       /* Now we've finished writing the intermediate file.  */
 897       fclose (gcov_intermediate_file);
 898       XDELETEVEC (gcov_intermediate_filename);
 899     }
 900
 901   if (!file_name)
 902     executed_summary (total_lines, total_executed);
 903 }
 904
 905 /* Release a function structure */
 906
 907 static void
 908 release_function (function_t *fn)
 909 {
 910   unsigned ix;
 911   block_t *block;
 912
 913   for (ix = fn->num_blocks, block = fn->blocks; ix--; block++)
 914     {
 915       arc_t *arc, *arc_n;
 916
 917       for (arc = block->succ; arc; arc = arc_n)
 918         {
 919           arc_n = arc->succ_next;
 920           free (arc);
 921         }
 922     }
 923   free (fn->blocks);
 924   free (fn->counts);
 925   if (flag_demangled_names && fn->demangled_name != fn->name)
 926     free (fn->demangled_name);
 927   free (fn->name);
 928 }
 929
 930 /* Release all memory used.  */
 931
 932 static void
 933 release_structures (void)
 934 {
 935   unsigned ix;
 936   function_t *fn;
 937
 938   for (ix = n_sources; ix--;)
 939     free (sources[ix].lines);
 940   free (sources);
 941
 942   for (ix = n_names; ix--;)
 943     free (names[ix].name);
 944   free (names);
 945
 946   while ((fn = functions))
 947     {
 948       functions = fn->next;
 949       release_function (fn);
 950     }
 951 }
 952
 953 /* Generate the names of the graph and data files.  If OBJECT_DIRECTORY
 954    is not specified, these are named from FILE_NAME sans extension.  If
 955    OBJECT_DIRECTORY is specified and is a directory, the files are in that
 956    directory, but named from the basename of the FILE_NAME, sans extension.
 957    Otherwise OBJECT_DIRECTORY is taken to be the name of the object *file*
 958    and the data files are named from that.  */
 959
 960 static void
 961 create_file_names (const char *file_name)
 962 {
 963   char *cptr;
 964   char *name;
 965   int length = strlen (file_name);
 966   int base;
 967
 968   /* Free previous file names.  */
 969   free (bbg_file_name);
 970   free (da_file_name);
 971   da_file_name = bbg_file_name = NULL;
 972   bbg_file_time = 0;
 973   bbg_stamp = 0;
 974
 975   if (object_directory && object_directory[0])
 976     {
 977       struct stat status;
 978
 979       length += strlen (object_directory) + 2;
 980       name = XNEWVEC (char, length);
 981       name[0] = 0;
 982
 983       base = !stat (object_directory, &status) && S_ISDIR (status.st_mode);
 984       strcat (name, object_directory);
 985       if (base && (! IS_DIR_SEPARATOR (name[strlen (name) - 1])))
 986         strcat (name, "/");
 987     }
 988   else
 989     {
 990       name = XNEWVEC (char, length + 1);
 991       strcpy (name, file_name);
 992       base = 0;
 993     }
 994
 995   if (base)
 996     {
 997       /* Append source file name.  */
 998       const char *cptr = lbasename (file_name);
 999       strcat (name, cptr ? cptr : file_name);
1000     }
1001
1002   /* Remove the extension.  */
1003   cptr = strrchr (CONST_CAST (char *, lbasename (name)), '.');
1004   if (cptr)
1005     *cptr = 0;
1006
1007   length = strlen (name);
1008
1009   bbg_file_name = XNEWVEC (char, length + strlen (GCOV_NOTE_SUFFIX) + 1);
1010   strcpy (bbg_file_name, name);
1011   strcpy (bbg_file_name + length, GCOV_NOTE_SUFFIX);
1012
1013   da_file_name = XNEWVEC (char, length + strlen (GCOV_DATA_SUFFIX) + 1);
1014   strcpy (da_file_name, name);
1015   strcpy (da_file_name + length, GCOV_DATA_SUFFIX);
1016
1017   free (name);
1018   return;
1019 }
1020
1021 /* A is a string and B is a pointer to name_map_t.  Compare for file
1022    name orderability.  */
1023
1024 static int
1025 name_search (const void *a_, const void *b_)
1026 {
1027   const char *a = (const char *)a_;
1028   const name_map_t *b = (const name_map_t *)b_;
1029
1030 #if HAVE_DOS_BASED_FILE_SYSTEM
1031   return strcasecmp (a, b->name);
1032 #else
1033   return strcmp (a, b->name);
1034 #endif
1035 }
1036
1037 /* A and B are a pointer to name_map_t.  Compare for file name
1038    orderability.  */
1039
1040 static int
1041 name_sort (const void *a_, const void *b_)
1042 {
1043   const name_map_t *a = (const name_map_t *)a_;
1044   return name_search (a->name, b_);
1045 }
1046
1047 /* Find or create a source file structure for FILE_NAME. Copies
1048    FILE_NAME on creation */
1049
1050 static unsigned
1051 find_source (const char *file_name)
1052 {
1053   name_map_t *name_map;
1054   char *canon;
1055   unsigned idx;
1056   struct stat status;
1057
1058   if (!file_name)
1059     file_name = "<unknown>";
1060   name_map = (name_map_t *)bsearch
1061     (file_name, names, n_names, sizeof (*names), name_search);
1062   if (name_map)
1063     {
1064       idx = name_map->src;
1065       goto check_date;
1066     }
1067
1068   if (n_names + 2 > a_names)
1069     {
1070       /* Extend the name map array -- we'll be inserting one or two
1071          entries.  */
1072       a_names *= 2;
1073       name_map = XNEWVEC (name_map_t, a_names);
1074       memcpy (name_map, names, n_names * sizeof (*names));
1075       free (names);
1076       names = name_map;
1077     }
1078
1079   /* Not found, try the canonical name. */
1080   canon = canonicalize_name (file_name);
1081   name_map = (name_map_t *)bsearch
1082     (canon, names, n_names, sizeof (*names), name_search);
1083   if (!name_map)
1084     {
1085       /* Not found with canonical name, create a new source.  */
1086       source_t *src;
1087
1088       if (n_sources == a_sources)
1089         {
1090           a_sources *= 2;
1091           src = XNEWVEC (source_t, a_sources);
1092           memcpy (src, sources, n_sources * sizeof (*sources));
1093           free (sources);
1094           sources = src;
1095         }
1096
1097       idx = n_sources;
1098
1099       name_map = &names[n_names++];
1100       name_map->name = canon;
1101       name_map->src = idx;
1102
1103       src = &sources[n_sources++];
1104       memset (src, 0, sizeof (*src));
1105       src->name = canon;
1106       src->coverage.name = src->name;
1107       if (source_length
1108 #if HAVE_DOS_BASED_FILE_SYSTEM
1109           /* You lose if separators don't match exactly in the
1110              prefix.  */
1111           && !strncasecmp (source_prefix, src->coverage.name, source_length)
1112 #else
1113           && !strncmp (source_prefix, src->coverage.name, source_length)
1114 #endif
1115           && IS_DIR_SEPARATOR (src->coverage.name[source_length]))
1116         src->coverage.name += source_length + 1;
1117       if (!stat (src->name, &status))
1118         src->file_time = status.st_mtime;
1119     }
1120   else
1121     idx = name_map->src;
1122
1123   if (name_search (file_name, name_map))
1124     {
1125       /* Append the non-canonical name.  */
1126       name_map = &names[n_names++];
1127       name_map->name = xstrdup (file_name);
1128       name_map->src = idx;
1129     }
1130
1131   /* Resort the name map.  */
1132   qsort (names, n_names, sizeof (*names), name_sort);
1133
1134  check_date:
1135   if (sources[idx].file_time > bbg_file_time)
1136     {
1137       static int info_emitted;
1138
1139       fnotice (stderr, "%s:source file is newer than notes file '%s'\n",
1140                file_name, bbg_file_name);
1141       if (!info_emitted)
1142         {
1143           fnotice (stderr,
1144                    "(the message is displayed only once per source file)\n");
1145           info_emitted = 1;
1146         }
1147       sources[idx].file_time = 0;
1148     }
1149
1150   return idx;
1151 }
1152
1153 /* Read the notes file.  Return list of functions read -- in reverse order.  */
1154
1155 static function_t *
1156 read_graph_file (void)
1157 {
1158   unsigned version;
1159   unsigned current_tag = 0;
1160   function_t *fn = NULL;
1161   function_t *fns = NULL;
1162   function_t **fns_end = &fns;
1163   unsigned src_idx = 0;
1164   unsigned ix;
1165   unsigned tag;
1166
1167   if (!gcov_open (bbg_file_name, 1))
1168     {
1169       fnotice (stderr, "%s:cannot open notes file\n", bbg_file_name);
1170       return fns;
1171     }
1172   bbg_file_time = gcov_time ();
1173   if (!gcov_magic (gcov_read_unsigned (), GCOV_NOTE_MAGIC))
1174     {
1175       fnotice (stderr, "%s:not a gcov notes file\n", bbg_file_name);
1176       gcov_close ();
1177       return fns;
1178     }
1179
1180   version = gcov_read_unsigned ();
1181   if (version != GCOV_VERSION)
1182     {
1183       char v[4], e[4];
1184
1185       GCOV_UNSIGNED2STRING (v, version);
1186       GCOV_UNSIGNED2STRING (e, GCOV_VERSION);
1187
1188       fnotice (stderr, "%s:version '%.4s', prefer '%.4s'\n",
1189                bbg_file_name, v, e);
1190     }
1191   bbg_stamp = gcov_read_unsigned ();
1192
1193   while ((tag = gcov_read_unsigned ()))
1194     {
1195       unsigned length = gcov_read_unsigned ();
1196       gcov_position_t base = gcov_position ();
1197
1198       if (tag == GCOV_TAG_FUNCTION)
1199         {
1200           char *function_name;
1201           unsigned ident, lineno;
1202           unsigned lineno_checksum, cfg_checksum;
1203
1204           ident = gcov_read_unsigned ();
1205           lineno_checksum = gcov_read_unsigned ();
1206           cfg_checksum = gcov_read_unsigned ();
1207           function_name = xstrdup (gcov_read_string ());
1208           src_idx = find_source (gcov_read_string ());
1209           lineno = gcov_read_unsigned ();
1210
1211           fn = XCNEW (function_t);
1212           fn->name = function_name;
1213           if (flag_demangled_names)
1214             {
1215               fn->demangled_name = cplus_demangle (fn->name, DMGL_PARAMS);
1216               if (!fn->demangled_name)
1217                 fn->demangled_name = fn->name;
1218             }
1219           fn->ident = ident;
1220           fn->lineno_checksum = lineno_checksum;
1221           fn->cfg_checksum = cfg_checksum;
1222           fn->src = src_idx;
1223           fn->line = lineno;
1224
1225           fn->line_next = NULL;
1226           fn->next = NULL;
1227           *fns_end = fn;
1228           fns_end = &fn->next;
1229           current_tag = tag;
1230         }
1231       else if (fn && tag == GCOV_TAG_BLOCKS)
1232         {
1233           if (fn->blocks)
1234             fnotice (stderr, "%s:already seen blocks for '%s'\n",
1235                      bbg_file_name, fn->name);
1236           else
1237             {
1238               unsigned ix, num_blocks = GCOV_TAG_BLOCKS_NUM (length);
1239               fn->num_blocks = num_blocks;
1240
1241               fn->blocks = XCNEWVEC (block_t, fn->num_blocks);
1242               for (ix = 0; ix != num_blocks; ix++)
1243                 fn->blocks[ix].flags = gcov_read_unsigned ();
1244             }
1245         }
1246       else if (fn && tag == GCOV_TAG_ARCS)
1247         {
1248           unsigned src = gcov_read_unsigned ();
1249           unsigned num_dests = GCOV_TAG_ARCS_NUM (length);
1250           block_t *src_blk = &fn->blocks[src];
1251           unsigned mark_catches = 0;
1252           struct arc_info *arc;
1253
1254           if (src >= fn->num_blocks || fn->blocks[src].succ)
1255             goto corrupt;
1256
1257           while (num_dests--)
1258             {
1259               unsigned dest = gcov_read_unsigned ();
1260               unsigned flags = gcov_read_unsigned ();
1261
1262               if (dest >= fn->num_blocks)
1263                 goto corrupt;
1264               arc = XCNEW (arc_t);
1265
1266               arc->dst = &fn->blocks[dest];
1267               arc->src = src_blk;
1268
1269               arc->count = 0;
1270               arc->count_valid = 0;
1271               arc->on_tree = !!(flags & GCOV_ARC_ON_TREE);
1272               arc->fake = !!(flags & GCOV_ARC_FAKE);
1273               arc->fall_through = !!(flags & GCOV_ARC_FALLTHROUGH);
1274
1275               arc->succ_next = src_blk->succ;
1276               src_blk->succ = arc;
1277               src_blk->num_succ++;
1278
1279               arc->pred_next = fn->blocks[dest].pred;
1280               fn->blocks[dest].pred = arc;
1281               fn->blocks[dest].num_pred++;
1282
1283               if (arc->fake)
1284                 {
1285                   if (src)
1286                     {
1287                       /* Exceptional exit from this function, the
1288                          source block must be a call.  */
1289                       fn->blocks[src].is_call_site = 1;
1290                       arc->is_call_non_return = 1;
1291                       mark_catches = 1;
1292                     }
1293                   else
1294                     {
1295                       /* Non-local return from a callee of this
1296                          function. The destination block is a setjmp.  */
1297                       arc->is_nonlocal_return = 1;
1298                       fn->blocks[dest].is_nonlocal_return = 1;
1299                     }
1300                 }
1301
1302               if (!arc->on_tree)
1303                 fn->num_counts++;
1304             }
1305
1306           if (mark_catches)
1307             {
1308               /* We have a fake exit from this block.  The other
1309                  non-fall through exits must be to catch handlers.
1310                  Mark them as catch arcs.  */
1311
1312               for (arc = src_blk->succ; arc; arc = arc->succ_next)
1313                 if (!arc->fake && !arc->fall_through)
1314                   {
1315                     arc->is_throw = 1;
1316                     fn->has_catch = 1;
1317                   }
1318             }
1319         }
1320       else if (fn && tag == GCOV_TAG_LINES)
1321         {
1322           unsigned blockno = gcov_read_unsigned ();
1323           unsigned *line_nos = XCNEWVEC (unsigned, length - 1);
1324
1325           if (blockno >= fn->num_blocks || fn->blocks[blockno].u.line.encoding)
1326             goto corrupt;
1327
1328           for (ix = 0; ;  )
1329             {
1330               unsigned lineno = gcov_read_unsigned ();
1331
1332               if (lineno)
1333                 {
1334                   if (!ix)
1335                     {
1336                       line_nos[ix++] = 0;
1337                       line_nos[ix++] = src_idx;
1338                     }
1339                   line_nos[ix++] = lineno;
1340                 }
1341               else
1342                 {
1343                   const char *file_name = gcov_read_string ();
1344
1345                   if (!file_name)
1346                     break;
1347                   src_idx = find_source (file_name);
1348                   line_nos[ix++] = 0;
1349                   line_nos[ix++] = src_idx;
1350                 }
1351             }
1352
1353           fn->blocks[blockno].u.line.encoding = line_nos;
1354           fn->blocks[blockno].u.line.num = ix;
1355         }
1356       else if (current_tag && !GCOV_TAG_IS_SUBTAG (current_tag, tag))
1357         {
1358           fn = NULL;
1359           current_tag = 0;
1360         }
1361       gcov_sync (base, length);
1362       if (gcov_is_error ())
1363         {
1364         corrupt:;
1365           fnotice (stderr, "%s:corrupted\n", bbg_file_name);
1366           break;
1367         }
1368     }
1369   gcov_close ();
1370
1371   if (!fns)
1372     fnotice (stderr, "%s:no functions found\n", bbg_file_name);
1373
1374   return fns;
1375 }
1376
1377 /* Reads profiles from the count file and attach to each
1378    function. Return nonzero if fatal error.  */
1379
1380 static int
1381 read_count_file (function_t *fns)
1382 {
1383   unsigned ix;
1384   unsigned version;
1385   unsigned tag;
1386   function_t *fn = NULL;
1387   int error = 0;
1388
1389   if (!gcov_open (da_file_name, 1))
1390     {
1391       fnotice (stderr, "%s:cannot open data file, assuming not executed\n",
1392                da_file_name);
1393       no_data_file = 1;
1394       return 0;
1395     }
1396   if (!gcov_magic (gcov_read_unsigned (), GCOV_DATA_MAGIC))
1397     {
1398       fnotice (stderr, "%s:not a gcov data file\n", da_file_name);
1399     cleanup:;
1400       gcov_close ();
1401       return 1;
1402     }
1403   version = gcov_read_unsigned ();
1404   if (version != GCOV_VERSION)
1405     {
1406       char v[4], e[4];
1407
1408       GCOV_UNSIGNED2STRING (v, version);
1409       GCOV_UNSIGNED2STRING (e, GCOV_VERSION);
1410
1411       fnotice (stderr, "%s:version '%.4s', prefer version '%.4s'\n",
1412                da_file_name, v, e);
1413     }
1414   tag = gcov_read_unsigned ();
1415   if (tag != bbg_stamp)
1416     {
1417       fnotice (stderr, "%s:stamp mismatch with notes file\n", da_file_name);
1418       goto cleanup;
1419     }
1420
1421   while ((tag = gcov_read_unsigned ()))
1422     {
1423       unsigned length = gcov_read_unsigned ();
1424       unsigned long base = gcov_position ();
1425
1426       if (tag == GCOV_TAG_PROGRAM_SUMMARY)
1427         {
1428           struct gcov_summary summary;
1429           gcov_read_summary (&summary);
1430           object_runs += summary.ctrs[GCOV_COUNTER_ARCS].runs;
1431           program_count++;
1432         }
1433       else if (tag == GCOV_TAG_FUNCTION && !length)
1434         ; /* placeholder  */
1435       else if (tag == GCOV_TAG_FUNCTION && length == GCOV_TAG_FUNCTION_LENGTH)
1436         {
1437           unsigned ident;
1438           struct function_info *fn_n;
1439
1440           /* Try to find the function in the list.  To speed up the
1441              search, first start from the last function found.  */
1442           ident = gcov_read_unsigned ();
1443           fn_n = fns;
1444           for (fn = fn ? fn->next : NULL; ; fn = fn->next)
1445             {
1446               if (fn)
1447                 ;
1448               else if ((fn = fn_n))
1449                 fn_n = NULL;
1450               else
1451                 {
1452                   fnotice (stderr, "%s:unknown function '%u'\n",
1453                            da_file_name, ident);
1454                   break;
1455                 }
1456               if (fn->ident == ident)
1457                 break;
1458             }
1459
1460           if (!fn)
1461             ;
1462           else if (gcov_read_unsigned () != fn->lineno_checksum
1463                    || gcov_read_unsigned () != fn->cfg_checksum)
1464             {
1465             mismatch:;
1466               fnotice (stderr, "%s:profile mismatch for '%s'\n",
1467                        da_file_name, fn->name);
1468               goto cleanup;
1469             }
1470         }
1471       else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn)
1472         {
1473           if (length != GCOV_TAG_COUNTER_LENGTH (fn->num_counts))
1474             goto mismatch;
1475
1476           if (!fn->counts)
1477             fn->counts = XCNEWVEC (gcov_type, fn->num_counts);
1478
1479           for (ix = 0; ix != fn->num_counts; ix++)
1480             fn->counts[ix] += gcov_read_counter ();
1481         }
1482       gcov_sync (base, length);
1483       if ((error = gcov_is_error ()))
1484         {
1485           fnotice (stderr, error < 0 ? "%s:overflowed\n" : "%s:corrupted\n",
1486                    da_file_name);
1487           goto cleanup;
1488         }
1489     }
1490
1491   gcov_close ();
1492   return 0;
1493 }
1494
1495 /* Solve the flow graph. Propagate counts from the instrumented arcs
1496    to the blocks and the uninstrumented arcs.  */
1497
1498 static void
1499 solve_flow_graph (function_t *fn)
1500 {
1501   unsigned ix;
1502   arc_t *arc;
1503   gcov_type *count_ptr = fn->counts;
1504   block_t *blk;
1505   block_t *valid_blocks = NULL;    /* valid, but unpropagated blocks.  */
1506   block_t *invalid_blocks = NULL;  /* invalid, but inferable blocks.  */
1507
1508   /* The arcs were built in reverse order.  Fix that now.  */
1509   for (ix = fn->num_blocks; ix--;)
1510     {
1511       arc_t *arc_p, *arc_n;
1512
1513       for (arc_p = NULL, arc = fn->blocks[ix].succ; arc;
1514            arc_p = arc, arc = arc_n)
1515         {
1516           arc_n = arc->succ_next;
1517           arc->succ_next = arc_p;
1518         }
1519       fn->blocks[ix].succ = arc_p;
1520
1521       for (arc_p = NULL, arc = fn->blocks[ix].pred; arc;
1522            arc_p = arc, arc = arc_n)
1523         {
1524           arc_n = arc->pred_next;
1525           arc->pred_next = arc_p;
1526         }
1527       fn->blocks[ix].pred = arc_p;
1528     }
1529
1530   if (fn->num_blocks < 2)
1531     fnotice (stderr, "%s:'%s' lacks entry and/or exit blocks\n",
1532              bbg_file_name, fn->name);
1533   else
1534     {
1535       if (fn->blocks[ENTRY_BLOCK].num_pred)
1536         fnotice (stderr, "%s:'%s' has arcs to entry block\n",
1537                  bbg_file_name, fn->name);
1538       else
1539         /* We can't deduce the entry block counts from the lack of
1540            predecessors.  */
1541         fn->blocks[ENTRY_BLOCK].num_pred = ~(unsigned)0;
1542
1543       if (fn->blocks[EXIT_BLOCK].num_succ)
1544         fnotice (stderr, "%s:'%s' has arcs from exit block\n",
1545                  bbg_file_name, fn->name);
1546       else
1547         /* Likewise, we can't deduce exit block counts from the lack
1548            of its successors.  */
1549         fn->blocks[EXIT_BLOCK].num_succ = ~(unsigned)0;
1550     }
1551
1552   /* Propagate the measured counts, this must be done in the same
1553      order as the code in profile.c  */
1554   for (ix = 0, blk = fn->blocks; ix != fn->num_blocks; ix++, blk++)
1555     {
1556       block_t const *prev_dst = NULL;
1557       int out_of_order = 0;
1558       int non_fake_succ = 0;
1559
1560       for (arc = blk->succ; arc; arc = arc->succ_next)
1561         {
1562           if (!arc->fake)
1563             non_fake_succ++;
1564
1565           if (!arc->on_tree)
1566             {
1567               if (count_ptr)
1568                 arc->count = *count_ptr++;
1569               arc->count_valid = 1;
1570               blk->num_succ--;
1571               arc->dst->num_pred--;
1572             }
1573           if (prev_dst && prev_dst > arc->dst)
1574             out_of_order = 1;
1575           prev_dst = arc->dst;
1576         }
1577       if (non_fake_succ == 1)
1578         {
1579           /* If there is only one non-fake exit, it is an
1580              unconditional branch.  */
1581           for (arc = blk->succ; arc; arc = arc->succ_next)
1582             if (!arc->fake)
1583               {
1584                 arc->is_unconditional = 1;
1585                 /* If this block is instrumenting a call, it might be
1586                    an artificial block. It is not artificial if it has
1587                    a non-fallthrough exit, or the destination of this
1588                    arc has more than one entry.  Mark the destination
1589                    block as a return site, if none of those conditions
1590                    hold.  */
1591                 if (blk->is_call_site && arc->fall_through
1592                     && arc->dst->pred == arc && !arc->pred_next)
1593                   arc->dst->is_call_return = 1;
1594               }
1595         }
1596
1597       /* Sort the successor arcs into ascending dst order. profile.c
1598          normally produces arcs in the right order, but sometimes with
1599          one or two out of order.  We're not using a particularly
1600          smart sort.  */
1601       if (out_of_order)
1602         {
1603           arc_t *start = blk->succ;
1604           unsigned changes = 1;
1605
1606           while (changes)
1607             {
1608               arc_t *arc, *arc_p, *arc_n;
1609
1610               changes = 0;
1611               for (arc_p = NULL, arc = start; (arc_n = arc->succ_next);)
1612                 {
1613                   if (arc->dst > arc_n->dst)
1614                     {
1615                       changes = 1;
1616                       if (arc_p)
1617                         arc_p->succ_next = arc_n;
1618                       else
1619                         start = arc_n;
1620                       arc->succ_next = arc_n->succ_next;
1621                       arc_n->succ_next = arc;
1622                       arc_p = arc_n;
1623                     }
1624                   else
1625                     {
1626                       arc_p = arc;
1627                       arc = arc_n;
1628                     }
1629                 }
1630             }
1631           blk->succ = start;
1632         }
1633
1634       /* Place it on the invalid chain, it will be ignored if that's
1635          wrong.  */
1636       blk->invalid_chain = 1;
1637       blk->chain = invalid_blocks;
1638       invalid_blocks = blk;
1639     }
1640
1641   while (invalid_blocks || valid_blocks)
1642     {
1643       while ((blk = invalid_blocks))
1644         {
1645           gcov_type total = 0;
1646           const arc_t *arc;
1647
1648           invalid_blocks = blk->chain;
1649           blk->invalid_chain = 0;
1650           if (!blk->num_succ)
1651             for (arc = blk->succ; arc; arc = arc->succ_next)
1652               total += arc->count;
1653           else if (!blk->num_pred)
1654             for (arc = blk->pred; arc; arc = arc->pred_next)
1655               total += arc->count;
1656           else
1657             continue;
1658
1659           blk->count = total;
1660           blk->count_valid = 1;
1661           blk->chain = valid_blocks;
1662           blk->valid_chain = 1;
1663           valid_blocks = blk;
1664         }
1665       while ((blk = valid_blocks))
1666         {
1667           gcov_type total;
1668           arc_t *arc, *inv_arc;
1669
1670           valid_blocks = blk->chain;
1671           blk->valid_chain = 0;
1672           if (blk->num_succ == 1)
1673             {
1674               block_t *dst;
1675
1676               total = blk->count;
1677               inv_arc = NULL;
1678               for (arc = blk->succ; arc; arc = arc->succ_next)
1679                 {
1680                   total -= arc->count;
1681                   if (!arc->count_valid)
1682                     inv_arc = arc;
1683                 }
1684               dst = inv_arc->dst;
1685               inv_arc->count_valid = 1;
1686               inv_arc->count = total;
1687               blk->num_succ--;
1688               dst->num_pred--;
1689               if (dst->count_valid)
1690                 {
1691                   if (dst->num_pred == 1 && !dst->valid_chain)
1692                     {
1693                       dst->chain = valid_blocks;
1694                       dst->valid_chain = 1;
1695                       valid_blocks = dst;
1696                     }
1697                 }
1698               else
1699                 {
1700                   if (!dst->num_pred && !dst->invalid_chain)
1701                     {
1702                       dst->chain = invalid_blocks;
1703                       dst->invalid_chain = 1;
1704                       invalid_blocks = dst;
1705                     }
1706                 }
1707             }
1708           if (blk->num_pred == 1)
1709             {
1710               block_t *src;
1711
1712               total = blk->count;
1713               inv_arc = NULL;
1714               for (arc = blk->pred; arc; arc = arc->pred_next)
1715                 {
1716                   total -= arc->count;
1717                   if (!arc->count_valid)
1718                     inv_arc = arc;
1719                 }
1720               src = inv_arc->src;
1721               inv_arc->count_valid = 1;
1722               inv_arc->count = total;
1723               blk->num_pred--;
1724               src->num_succ--;
1725               if (src->count_valid)
1726                 {
1727                   if (src->num_succ == 1 && !src->valid_chain)
1728                     {
1729                       src->chain = valid_blocks;
1730                       src->valid_chain = 1;
1731                       valid_blocks = src;
1732                     }
1733                 }
1734               else
1735                 {
1736                   if (!src->num_succ && !src->invalid_chain)
1737                     {
1738                       src->chain = invalid_blocks;
1739                       src->invalid_chain = 1;
1740                       invalid_blocks = src;
1741                     }
1742                 }
1743             }
1744         }
1745     }
1746
1747   /* If the graph has been correctly solved, every block will have a
1748      valid count.  */
1749   for (ix = 0; ix < fn->num_blocks; ix++)
1750     if (!fn->blocks[ix].count_valid)
1751       {
1752         fnotice (stderr, "%s:graph is unsolvable for '%s'\n",
1753                  bbg_file_name, fn->name);
1754         break;
1755       }
1756 }
1757
1758 /* Mark all the blocks only reachable via an incoming catch.  */
1759
1760 static void
1761 find_exception_blocks (function_t *fn)
1762 {
1763   unsigned ix;
1764   block_t **queue = XALLOCAVEC (block_t *, fn->num_blocks);
1765
1766   /* First mark all blocks as exceptional.  */
1767   for (ix = fn->num_blocks; ix--;)
1768     fn->blocks[ix].exceptional = 1;
1769
1770   /* Now mark all the blocks reachable via non-fake edges */
1771   queue[0] = fn->blocks;
1772   queue[0]->exceptional = 0;
1773   for (ix = 1; ix;)
1774     {
1775       block_t *block = queue[--ix];
1776       const arc_t *arc;
1777
1778       for (arc = block->succ; arc; arc = arc->succ_next)
1779         if (!arc->fake && !arc->is_throw && arc->dst->exceptional)
1780           {
1781             arc->dst->exceptional = 0;
1782             queue[ix++] = arc->dst;
1783           }
1784     }
1785 }
1786 \f
1787
1788 /* Increment totals in COVERAGE according to arc ARC.  */
1789
1790 static void
1791 add_branch_counts (coverage_t *coverage, const arc_t *arc)
1792 {
1793   if (arc->is_call_non_return)
1794     {
1795       coverage->calls++;
1796       if (arc->src->count)
1797         coverage->calls_executed++;
1798     }
1799   else if (!arc->is_unconditional)
1800     {
1801       coverage->branches++;
1802       if (arc->src->count)
1803         coverage->branches_executed++;
1804       if (arc->count)
1805         coverage->branches_taken++;
1806     }
1807 }
1808
1809 /* Format a GCOV_TYPE integer as either a percent ratio, or absolute
1810    count.  If dp >= 0, format TOP/BOTTOM * 100 to DP decimal places.
1811    If DP is zero, no decimal point is printed. Only print 100% when
1812    TOP==BOTTOM and only print 0% when TOP=0.  If dp < 0, then simply
1813    format TOP.  Return pointer to a static string.  */
1814
1815 static char const *
1816 format_gcov (gcov_type top, gcov_type bottom, int dp)
1817 {
1818   static char buffer[20];
1819
1820   if (dp >= 0)
1821     {
1822       float ratio = bottom ? (float)top / bottom : 0;
1823       int ix;
1824       unsigned limit = 100;
1825       unsigned percent;
1826
1827       for (ix = dp; ix--; )
1828         limit *= 10;
1829
1830       percent = (unsigned) (ratio * limit + (float)0.5);
1831       if (percent <= 0 && top)
1832         percent = 1;
1833       else if (percent >= limit && top != bottom)
1834         percent = limit - 1;
1835       ix = sprintf (buffer, "%.*u%%", dp + 1, percent);
1836       if (dp)
1837         {
1838           dp++;
1839           do
1840             {
1841               buffer[ix+1] = buffer[ix];
1842               ix--;
1843             }
1844           while (dp--);
1845           buffer[ix + 1] = '.';
1846         }
1847     }
1848   else
1849     sprintf (buffer, "%" PRId64, (int64_t)top);
1850
1851   return buffer;
1852 }
1853
1854 /* Summary of execution */
1855
1856 static void
1857 executed_summary (unsigned lines, unsigned executed)
1858 {
1859   if (lines)
1860     fnotice (stdout, "Lines executed:%s of %d\n",
1861              format_gcov (executed, lines, 2), lines);
1862   else
1863     fnotice (stdout, "No executable lines\n");
1864 }
1865
1866 /* Output summary info for a function or file.  */
1867
1868 static void
1869 function_summary (const coverage_t *coverage, const char *title)
1870 {
1871   fnotice (stdout, "%s '%s'\n", title, coverage->name);
1872   executed_summary (coverage->lines, coverage->lines_executed);
1873
1874   if (flag_branches)
1875     {
1876       if (coverage->branches)
1877         {
1878           fnotice (stdout, "Branches executed:%s of %d\n",
1879                    format_gcov (coverage->branches_executed,
1880                                 coverage->branches, 2),
1881                    coverage->branches);
1882           fnotice (stdout, "Taken at least once:%s of %d\n",
1883                    format_gcov (coverage->branches_taken,
1884                                 coverage->branches, 2),
1885                    coverage->branches);
1886         }
1887       else
1888         fnotice (stdout, "No branches\n");
1889       if (coverage->calls)
1890         fnotice (stdout, "Calls executed:%s of %d\n",
1891                  format_gcov (coverage->calls_executed, coverage->calls, 2),
1892                  coverage->calls);
1893       else
1894         fnotice (stdout, "No calls\n");
1895     }
1896 }
1897
1898 /* Canonicalize the filename NAME by canonicalizing directory
1899    separators, eliding . components and resolving .. components
1900    appropriately.  Always returns a unique string.  */
1901
1902 static char *
1903 canonicalize_name (const char *name)
1904 {
1905   /* The canonical name cannot be longer than the incoming name.  */
1906   char *result = XNEWVEC (char, strlen (name) + 1);
1907   const char *base = name, *probe;
1908   char *ptr = result;
1909   char *dd_base;
1910   int slash = 0;
1911
1912 #if HAVE_DOS_BASED_FILE_SYSTEM
1913   if (base[0] && base[1] == ':')
1914     {
1915       result[0] = base[0];
1916       result[1] = ':';
1917       base += 2;
1918       ptr += 2;
1919     }
1920 #endif
1921   for (dd_base = ptr; *base; base = probe)
1922     {
1923       size_t len;
1924
1925       for (probe = base; *probe; probe++)
1926         if (IS_DIR_SEPARATOR (*probe))
1927           break;
1928
1929       len = probe - base;
1930       if (len == 1 && base[0] == '.')
1931         /* Elide a '.' directory */
1932         ;
1933       else if (len == 2 && base[0] == '.' && base[1] == '.')
1934         {
1935           /* '..', we can only elide it and the previous directory, if
1936              we're not a symlink.  */
1937           struct stat ATTRIBUTE_UNUSED buf;
1938
1939           *ptr = 0;
1940           if (dd_base == ptr
1941 #if defined (S_ISLNK)
1942               /* S_ISLNK is not POSIX.1-1996.  */
1943               || stat (result, &buf) || S_ISLNK (buf.st_mode)
1944 #endif
1945               )
1946             {
1947               /* Cannot elide, or unreadable or a symlink.  */
1948               dd_base = ptr + 2 + slash;
1949               goto regular;
1950             }
1951           while (ptr != dd_base && *ptr != '/')
1952             ptr--;
1953           slash = ptr != result;
1954         }
1955       else
1956         {
1957         regular:
1958           /* Regular pathname component.  */
1959           if (slash)
1960             *ptr++ = '/';
1961           memcpy (ptr, base, len);
1962           ptr += len;
1963           slash = 1;
1964         }
1965
1966       for (; IS_DIR_SEPARATOR (*probe); probe++)
1967         continue;
1968     }
1969   *ptr = 0;
1970
1971   return result;
1972 }
1973
1974 /* Generate an output file name. INPUT_NAME is the canonicalized main
1975    input file and SRC_NAME is the canonicalized file name.
1976    LONG_OUTPUT_NAMES and PRESERVE_PATHS affect name generation.  With
1977    long_output_names we prepend the processed name of the input file
1978    to each output name (except when the current source file is the
1979    input file, so you don't get a double concatenation). The two
1980    components are separated by '##'.  With preserve_paths we create a
1981    filename from all path components of the source file, replacing '/'
1982    with '#', and .. with '^', without it we simply take the basename
1983    component.  (Remember, the canonicalized name will already have
1984    elided '.' components and converted \\ separators.)  */
1985
1986 static char *
1987 make_gcov_file_name (const char *input_name, const char *src_name)
1988 {
1989   char *ptr;
1990   char *result;
1991
1992   if (flag_long_names && input_name && strcmp (src_name, input_name))
1993     {
1994       /* Generate the input filename part.  */
1995       result = XNEWVEC (char, strlen (input_name) + strlen (src_name) + 10);
1996
1997       ptr = result;
1998       ptr = mangle_name (input_name, ptr);
1999       ptr[0] = ptr[1] = '#';
2000       ptr += 2;
2001     }
2002   else
2003     {
2004       result = XNEWVEC (char, strlen (src_name) + 10);
2005       ptr = result;
2006     }
2007
2008   ptr = mangle_name (src_name, ptr);
2009   strcpy (ptr, ".gcov");
2010
2011   return result;
2012 }
2013
2014 static char *
2015 mangle_name (char const *base, char *ptr)
2016 {
2017   size_t len;
2018
2019   /* Generate the source filename part.  */
2020   if (!flag_preserve_paths)
2021     {
2022       base = lbasename (base);
2023       len = strlen (base);
2024       memcpy (ptr, base, len);
2025       ptr += len;
2026     }
2027   else
2028     {
2029       /* Convert '/' to '#', convert '..' to '^',
2030          convert ':' to '~' on DOS based file system.  */
2031       const char *probe;
2032
2033 #if HAVE_DOS_BASED_FILE_SYSTEM
2034       if (base[0] && base[1] == ':')
2035         {
2036           ptr[0] = base[0];
2037           ptr[1] = '~';
2038           ptr += 2;
2039           base += 2;
2040         }
2041 #endif
2042       for (; *base; base = probe)
2043         {
2044           size_t len;
2045
2046           for (probe = base; *probe; probe++)
2047             if (*probe == '/')
2048               break;
2049           len = probe - base;
2050           if (len == 2 && base[0] == '.' && base[1] == '.')
2051             *ptr++ = '^';
2052           else
2053             {
2054               memcpy (ptr, base, len);
2055               ptr += len;
2056             }
2057           if (*probe)
2058             {
2059               *ptr++ = '#';
2060               probe++;
2061             }
2062         }
2063     }
2064
2065   return ptr;
2066 }
2067
2068 /* Scan through the bb_data for each line in the block, increment
2069    the line number execution count indicated by the execution count of
2070    the appropriate basic block.  */
2071
2072 static void
2073 add_line_counts (coverage_t *coverage, function_t *fn)
2074 {
2075   unsigned ix;
2076   line_t *line = NULL; /* This is propagated from one iteration to the
2077                           next.  */
2078
2079   /* Scan each basic block.  */
2080   for (ix = 0; ix != fn->num_blocks; ix++)
2081     {
2082       block_t *block = &fn->blocks[ix];
2083       unsigned *encoding;
2084       const source_t *src = NULL;
2085       unsigned jx;
2086
2087       if (block->count && ix && ix + 1 != fn->num_blocks)
2088         fn->blocks_executed++;
2089       for (jx = 0, encoding = block->u.line.encoding;
2090            jx != block->u.line.num; jx++, encoding++)
2091         if (!*encoding)
2092           {
2093             src = &sources[*++encoding];
2094             jx++;
2095           }
2096         else
2097           {
2098             line = &src->lines[*encoding];
2099
2100             if (coverage)
2101               {
2102                 if (!line->exists)
2103                   coverage->lines++;
2104                 if (!line->count && block->count)
2105                   coverage->lines_executed++;
2106               }
2107             line->exists = 1;
2108             if (!block->exceptional)
2109               line->unexceptional = 1;
2110             line->count += block->count;
2111           }
2112       free (block->u.line.encoding);
2113       block->u.cycle.arc = NULL;
2114       block->u.cycle.ident = ~0U;
2115
2116       if (!ix || ix + 1 == fn->num_blocks)
2117         /* Entry or exit block */;
2118       else if (flag_all_blocks)
2119         {
2120           line_t *block_line = line;
2121
2122           if (!block_line)
2123             block_line = &sources[fn->src].lines[fn->line];
2124
2125           block->chain = block_line->u.blocks;
2126           block_line->u.blocks = block;
2127         }
2128       else if (flag_branches)
2129         {
2130           arc_t *arc;
2131
2132           for (arc = block->succ; arc; arc = arc->succ_next)
2133             {
2134               arc->line_next = line->u.branches;
2135               line->u.branches = arc;
2136               if (coverage && !arc->is_unconditional)
2137                 add_branch_counts (coverage, arc);
2138             }
2139         }
2140     }
2141   if (!line)
2142     fnotice (stderr, "%s:no lines for '%s'\n", bbg_file_name, fn->name);
2143 }
2144
2145 /* Accumulate the line counts of a file.  */
2146
2147 static void
2148 accumulate_line_counts (source_t *src)
2149 {
2150   line_t *line;
2151   function_t *fn, *fn_p, *fn_n;
2152   unsigned ix;
2153
2154   /* Reverse the function order.  */
2155   for (fn = src->functions, fn_p = NULL; fn;
2156        fn_p = fn, fn = fn_n)
2157     {
2158       fn_n = fn->line_next;
2159       fn->line_next = fn_p;
2160     }
2161   src->functions = fn_p;
2162
2163   for (ix = src->num_lines, line = src->lines; ix--; line++)
2164     {
2165       if (!flag_all_blocks)
2166         {
2167           arc_t *arc, *arc_p, *arc_n;
2168
2169           /* Total and reverse the branch information.  */
2170           for (arc = line->u.branches, arc_p = NULL; arc;
2171                arc_p = arc, arc = arc_n)
2172             {
2173               arc_n = arc->line_next;
2174               arc->line_next = arc_p;
2175
2176               add_branch_counts (&src->coverage, arc);
2177             }
2178           line->u.branches = arc_p;
2179         }
2180       else if (line->u.blocks)
2181         {
2182           /* The user expects the line count to be the number of times
2183              a line has been executed. Simply summing the block count
2184              will give an artificially high number.  The Right Thing
2185              is to sum the entry counts to the graph of blocks on this
2186              line, then find the elementary cycles of the local graph
2187              and add the transition counts of those cycles.  */
2188           block_t *block, *block_p, *block_n;
2189           gcov_type count = 0;
2190
2191           /* Reverse the block information.  */
2192           for (block = line->u.blocks, block_p = NULL; block;
2193                block_p = block, block = block_n)
2194             {
2195               block_n = block->chain;
2196               block->chain = block_p;
2197               block->u.cycle.ident = ix;
2198             }
2199           line->u.blocks = block_p;
2200
2201           /* Sum the entry arcs.  */
2202           for (block = line->u.blocks; block; block = block->chain)
2203             {
2204               arc_t *arc;
2205
2206               for (arc = block->pred; arc; arc = arc->pred_next)
2207                 {
2208                   if (arc->src->u.cycle.ident != ix)
2209                     count += arc->count;
2210                   if (flag_branches)
2211                     add_branch_counts (&src->coverage, arc);
2212                 }
2213
2214               /* Initialize the cs_count.  */
2215               for (arc = block->succ; arc; arc = arc->succ_next)
2216                 arc->cs_count = arc->count;
2217             }
2218
2219           /* Find the loops. This uses the algorithm described in
2220              Tiernan 'An Efficient Search Algorithm to Find the
2221              Elementary Circuits of a Graph', CACM Dec 1970. We hold
2222              the P array by having each block point to the arc that
2223              connects to the previous block. The H array is implicitly
2224              held because of the arc ordering, and the block's
2225              previous arc pointer.
2226
2227              Although the algorithm is O(N^3) for highly connected
2228              graphs, at worst we'll have O(N^2), as most blocks have
2229              only one or two exits. Most graphs will be small.
2230
2231              For each loop we find, locate the arc with the smallest
2232              transition count, and add that to the cumulative
2233              count.  Decrease flow over the cycle and remove the arc
2234              from consideration.  */
2235           for (block = line->u.blocks; block; block = block->chain)
2236             {
2237               block_t *head = block;
2238               arc_t *arc;
2239
2240             next_vertex:;
2241               arc = head->succ;
2242             current_vertex:;
2243               while (arc)
2244                 {
2245                   block_t *dst = arc->dst;
2246                   if (/* Already used that arc.  */
2247                       arc->cycle
2248                       /* Not to same graph, or before first vertex.  */
2249                       || dst->u.cycle.ident != ix
2250                       /* Already in path.  */
2251                       || dst->u.cycle.arc)
2252                     {
2253                       arc = arc->succ_next;
2254                       continue;
2255                     }
2256
2257                   if (dst == block)
2258                     {
2259                       /* Found a closing arc.  */
2260                       gcov_type cycle_count = arc->cs_count;
2261                       arc_t *cycle_arc = arc;
2262                       arc_t *probe_arc;
2263
2264                       /* Locate the smallest arc count of the loop.  */
2265                       for (dst = head; (probe_arc = dst->u.cycle.arc);
2266                            dst = probe_arc->src)
2267                         if (cycle_count > probe_arc->cs_count)
2268                           {
2269                             cycle_count = probe_arc->cs_count;
2270                             cycle_arc = probe_arc;
2271                           }
2272
2273                       count += cycle_count;
2274                       cycle_arc->cycle = 1;
2275
2276                       /* Remove the flow from the cycle.  */
2277                       arc->cs_count -= cycle_count;
2278                       for (dst = head; (probe_arc = dst->u.cycle.arc);
2279                            dst = probe_arc->src)
2280                         probe_arc->cs_count -= cycle_count;
2281
2282                       /* Unwind to the cyclic arc.  */
2283                       while (head != cycle_arc->src)
2284                         {
2285                           arc = head->u.cycle.arc;
2286                           head->u.cycle.arc = NULL;
2287                           head = arc->src;
2288                         }
2289                       /* Move on.  */
2290                       arc = arc->succ_next;
2291                       continue;
2292                     }
2293
2294                   /* Add new block to chain.  */
2295                   dst->u.cycle.arc = arc;
2296                   head = dst;
2297                   goto next_vertex;
2298                 }
2299               /* We could not add another vertex to the path. Remove
2300                  the last vertex from the list.  */
2301               arc = head->u.cycle.arc;
2302               if (arc)
2303                 {
2304                   /* It was not the first vertex. Move onto next arc.  */
2305                   head->u.cycle.arc = NULL;
2306                   head = arc->src;
2307                   arc = arc->succ_next;
2308                   goto current_vertex;
2309                 }
2310               /* Mark this block as unusable.  */
2311               block->u.cycle.ident = ~0U;
2312             }
2313
2314           line->count = count;
2315         }
2316
2317       if (line->exists)
2318         {
2319           src->coverage.lines++;
2320           if (line->count)
2321             src->coverage.lines_executed++;
2322         }
2323     }
2324 }
2325
2326 /* Output information about ARC number IX.  Returns nonzero if
2327    anything is output.  */
2328
2329 static int
2330 output_branch_count (FILE *gcov_file, int ix, const arc_t *arc)
2331 {
2332   if (arc->is_call_non_return)
2333     {
2334       if (arc->src->count)
2335         {
2336           fnotice (gcov_file, "call   %2d returned %s\n", ix,
2337                    format_gcov (arc->src->count - arc->count,
2338                                 arc->src->count, -flag_counts));
2339         }
2340       else
2341         fnotice (gcov_file, "call   %2d never executed\n", ix);
2342     }
2343   else if (!arc->is_unconditional)
2344     {
2345       if (arc->src->count)
2346         fnotice (gcov_file, "branch %2d taken %s%s\n", ix,
2347                  format_gcov (arc->count, arc->src->count, -flag_counts),
2348                  arc->fall_through ? " (fallthrough)"
2349                  : arc->is_throw ? " (throw)" : "");
2350       else
2351         fnotice (gcov_file, "branch %2d never executed\n", ix);
2352     }
2353   else if (flag_unconditional && !arc->dst->is_call_return)
2354     {
2355       if (arc->src->count)
2356         fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
2357                  format_gcov (arc->count, arc->src->count, -flag_counts));
2358       else
2359         fnotice (gcov_file, "unconditional %2d never executed\n", ix);
2360     }
2361   else
2362     return 0;
2363   return 1;
2364
2365 }
2366
2367 static const char *
2368 read_line (FILE *file)
2369 {
2370   static char *string;
2371   static size_t string_len;
2372   size_t pos = 0;
2373   char *ptr;
2374
2375   if (!string_len)
2376     {
2377       string_len = 200;
2378       string = XNEWVEC (char, string_len);
2379     }
2380
2381   while ((ptr = fgets (string + pos, string_len - pos, file)))
2382     {
2383       size_t len = strlen (string + pos);
2384
2385       if (string[pos + len - 1] == '\n')
2386         {
2387           string[pos + len - 1] = 0;
2388           return string;
2389         }
2390       pos += len;
2391       string = XRESIZEVEC (char, string, string_len * 2);
2392       string_len *= 2;
2393     }
2394
2395   return pos ? string : NULL;
2396 }
2397
2398 /* Read in the source file one line at a time, and output that line to
2399    the gcov file preceded by its execution count and other
2400    information.  */
2401
2402 static void
2403 output_lines (FILE *gcov_file, const source_t *src)
2404 {
2405   FILE *source_file;
2406   unsigned line_num;    /* current line number.  */
2407   const line_t *line;           /* current line info ptr.  */
2408   const char *retval = "";      /* status of source file reading.  */
2409   function_t *fn = NULL;
2410
2411   fprintf (gcov_file, "%9s:%5d:Source:%s\n", "-", 0, src->coverage.name);
2412   if (!multiple_files)
2413     {
2414       fprintf (gcov_file, "%9s:%5d:Graph:%s\n", "-", 0, bbg_file_name);
2415       fprintf (gcov_file, "%9s:%5d:Data:%s\n", "-", 0,
2416                no_data_file ? "-" : da_file_name);
2417       fprintf (gcov_file, "%9s:%5d:Runs:%u\n", "-", 0, object_runs);
2418     }
2419   fprintf (gcov_file, "%9s:%5d:Programs:%u\n", "-", 0, program_count);
2420
2421   source_file = fopen (src->name, "r");
2422   if (!source_file)
2423     {
2424       fnotice (stderr, "Cannot open source file %s\n", src->name);
2425       retval = NULL;
2426     }
2427   else if (src->file_time == 0)
2428     fprintf (gcov_file, "%9s:%5d:Source is newer than graph\n", "-", 0);
2429
2430   if (flag_branches)
2431     fn = src->functions;
2432
2433   for (line_num = 1, line = &src->lines[line_num];
2434        line_num < src->num_lines; line_num++, line++)
2435     {
2436       for (; fn && fn->line == line_num; fn = fn->line_next)
2437         {
2438           arc_t *arc = fn->blocks[EXIT_BLOCK].pred;
2439           gcov_type return_count = fn->blocks[EXIT_BLOCK].count;
2440           gcov_type called_count = fn->blocks[ENTRY_BLOCK].count;
2441
2442           for (; arc; arc = arc->pred_next)
2443             if (arc->fake)
2444               return_count -= arc->count;
2445
2446           fprintf (gcov_file, "function %s", flag_demangled_names ?
2447                    fn->demangled_name : fn->name);
2448           fprintf (gcov_file, " called %s",
2449                    format_gcov (called_count, 0, -1));
2450           fprintf (gcov_file, " returned %s",
2451                    format_gcov (return_count, called_count, 0));
2452           fprintf (gcov_file, " blocks executed %s",
2453                    format_gcov (fn->blocks_executed, fn->num_blocks - 2, 0));
2454           fprintf (gcov_file, "\n");
2455         }
2456
2457       if (retval)
2458         retval = read_line (source_file);
2459
2460       /* For lines which don't exist in the .bb file, print '-' before
2461          the source line.  For lines which exist but were never
2462          executed, print '#####' or '=====' before the source line.
2463          Otherwise, print the execution count before the source line.
2464          There are 16 spaces of indentation added before the source
2465          line so that tabs won't be messed up.  */
2466       fprintf (gcov_file, "%9s:%5u:%s\n",
2467                !line->exists ? "-" : line->count
2468                ? format_gcov (line->count, 0, -1)
2469                : line->unexceptional ? "#####" : "=====", line_num,
2470                retval ? retval : "/*EOF*/");
2471
2472       if (flag_all_blocks)
2473         {
2474           block_t *block;
2475           arc_t *arc;
2476           int ix, jx;
2477
2478           for (ix = jx = 0, block = line->u.blocks; block;
2479                block = block->chain)
2480             {
2481               if (!block->is_call_return)
2482                 fprintf (gcov_file, "%9s:%5u-block %2d\n",
2483                          !line->exists ? "-" : block->count
2484                          ? format_gcov (block->count, 0, -1)
2485                          : block->exceptional ? "%%%%%" : "$$$$$",
2486                          line_num, ix++);
2487               if (flag_branches)
2488                 for (arc = block->succ; arc; arc = arc->succ_next)
2489                   jx += output_branch_count (gcov_file, jx, arc);
2490             }
2491         }
2492       else if (flag_branches)
2493         {
2494           int ix;
2495           arc_t *arc;
2496
2497           for (ix = 0, arc = line->u.branches; arc; arc = arc->line_next)
2498             ix += output_branch_count (gcov_file, ix, arc);
2499         }
2500     }
2501
2502   /* Handle all remaining source lines.  There may be lines after the
2503      last line of code.  */
2504   if (retval)
2505     {
2506       for (; (retval = read_line (source_file)); line_num++)
2507         fprintf (gcov_file, "%9s:%5u:%s\n", "-", line_num, retval);
2508     }
2509
2510   if (source_file)
2511     fclose (source_file);
2512 }