gcc-4_9-mobile/gcc/gcov.c

   1 /* Gcov.c: prepend line execution counts and branch probabilities to a
   2    source file.
   3    Copyright (C) 1990-2014 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 2014 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 only displayed one 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         }
1232       else if (fn && tag == GCOV_TAG_BLOCKS)
1233         {
1234           if (fn->blocks)
1235             fnotice (stderr, "%s:already seen blocks for '%s'\n",
1236                      bbg_file_name, fn->name);
1237           else
1238             {
1239               unsigned ix, num_blocks = GCOV_TAG_BLOCKS_NUM (length);
1240               fn->num_blocks = num_blocks;
1241
1242               fn->blocks = XCNEWVEC (block_t, fn->num_blocks);
1243               for (ix = 0; ix != num_blocks; ix++)
1244                 fn->blocks[ix].flags = gcov_read_unsigned ();
1245             }
1246         }
1247       else if (fn && tag == GCOV_TAG_ARCS)
1248         {
1249           unsigned src = gcov_read_unsigned ();
1250           unsigned num_dests = GCOV_TAG_ARCS_NUM (length);
1251           block_t *src_blk = &fn->blocks[src];
1252           unsigned mark_catches = 0;
1253           struct arc_info *arc;
1254
1255           if (src >= fn->num_blocks || fn->blocks[src].succ)
1256             goto corrupt;
1257
1258           while (num_dests--)
1259             {
1260               unsigned dest = gcov_read_unsigned ();
1261               unsigned flags = gcov_read_unsigned ();
1262
1263               if (dest >= fn->num_blocks)
1264                 goto corrupt;
1265               arc = XCNEW (arc_t);
1266
1267               arc->dst = &fn->blocks[dest];
1268               arc->src = src_blk;
1269
1270               arc->count = 0;
1271               arc->count_valid = 0;
1272               arc->on_tree = !!(flags & GCOV_ARC_ON_TREE);
1273               arc->fake = !!(flags & GCOV_ARC_FAKE);
1274               arc->fall_through = !!(flags & GCOV_ARC_FALLTHROUGH);
1275
1276               arc->succ_next = src_blk->succ;
1277               src_blk->succ = arc;
1278               src_blk->num_succ++;
1279
1280               arc->pred_next = fn->blocks[dest].pred;
1281               fn->blocks[dest].pred = arc;
1282               fn->blocks[dest].num_pred++;
1283
1284               if (arc->fake)
1285                 {
1286                   if (src)
1287                     {
1288                       /* Exceptional exit from this function, the
1289                          source block must be a call.  */
1290                       fn->blocks[src].is_call_site = 1;
1291                       arc->is_call_non_return = 1;
1292                       mark_catches = 1;
1293                     }
1294                   else
1295                     {
1296                       /* Non-local return from a callee of this
1297                          function. The destination block is a setjmp.  */
1298                       arc->is_nonlocal_return = 1;
1299                       fn->blocks[dest].is_nonlocal_return = 1;
1300                     }
1301                 }
1302
1303               if (!arc->on_tree)
1304                 fn->num_counts++;
1305             }
1306
1307           if (mark_catches)
1308             {
1309               /* We have a fake exit from this block.  The other
1310                  non-fall through exits must be to catch handlers.
1311                  Mark them as catch arcs.  */
1312
1313               for (arc = src_blk->succ; arc; arc = arc->succ_next)
1314                 if (!arc->fake && !arc->fall_through)
1315                   {
1316                     arc->is_throw = 1;
1317                     fn->has_catch = 1;
1318                   }
1319             }
1320         }
1321       else if (fn && tag == GCOV_TAG_LINES)
1322         {
1323           unsigned blockno = gcov_read_unsigned ();
1324           unsigned *line_nos = XCNEWVEC (unsigned, length - 1);
1325
1326           if (blockno >= fn->num_blocks || fn->blocks[blockno].u.line.encoding)
1327             goto corrupt;
1328
1329           for (ix = 0; ;  )
1330             {
1331               unsigned lineno = gcov_read_unsigned ();
1332
1333               if (lineno)
1334                 {
1335                   if (!ix)
1336                     {
1337                       line_nos[ix++] = 0;
1338                       line_nos[ix++] = src_idx;
1339                     }
1340                   line_nos[ix++] = lineno;
1341
1342                 }
1343               else
1344                 {
1345                   const char *file_name = gcov_read_string ();
1346
1347                   if (!file_name)
1348                     break;
1349                   src_idx = find_source (file_name);
1350                   line_nos[ix++] = 0;
1351                   line_nos[ix++] = src_idx;
1352                 }
1353             }
1354
1355           fn->blocks[blockno].u.line.encoding = line_nos;
1356           fn->blocks[blockno].u.line.num = ix;
1357         }
1358       else if (current_tag && !GCOV_TAG_IS_SUBTAG (current_tag, tag))
1359         {
1360           fn = NULL;
1361           current_tag = 0;
1362         }
1363       gcov_sync (base, length);
1364       if (gcov_is_error ())
1365         {
1366         corrupt:;
1367           fnotice (stderr, "%s:corrupted\n", bbg_file_name);
1368           break;
1369         }
1370     }
1371   gcov_close ();
1372
1373   if (!fns)
1374     fnotice (stderr, "%s:no functions found\n", bbg_file_name);
1375
1376   return fns;
1377 }
1378
1379 /* Reads profiles from the count file and attach to each
1380    function. Return nonzero if fatal error.  */
1381
1382 static int
1383 read_count_file (function_t *fns)
1384 {
1385   unsigned ix;
1386   unsigned version;
1387   unsigned tag;
1388   function_t *fn = NULL;
1389   int error = 0;
1390
1391   if (!gcov_open (da_file_name, 1))
1392     {
1393       fnotice (stderr, "%s:cannot open data file, assuming not executed\n",
1394                da_file_name);
1395       no_data_file = 1;
1396       return 0;
1397     }
1398   if (!gcov_magic (gcov_read_unsigned (), GCOV_DATA_MAGIC))
1399     {
1400       fnotice (stderr, "%s:not a gcov data file\n", da_file_name);
1401     cleanup:;
1402       gcov_close ();
1403       return 1;
1404     }
1405   version = gcov_read_unsigned ();
1406   if (version != GCOV_VERSION)
1407     {
1408       char v[4], e[4];
1409
1410       GCOV_UNSIGNED2STRING (v, version);
1411       GCOV_UNSIGNED2STRING (e, GCOV_VERSION);
1412
1413       fnotice (stderr, "%s:version '%.4s', prefer version '%.4s'\n",
1414                da_file_name, v, e);
1415     }
1416   tag = gcov_read_unsigned ();
1417   if (tag != bbg_stamp)
1418     {
1419       fnotice (stderr, "%s:stamp mismatch with notes file\n", da_file_name);
1420       goto cleanup;
1421     }
1422
1423   while ((tag = gcov_read_unsigned ()))
1424     {
1425       unsigned length = gcov_read_unsigned ();
1426       unsigned long base = gcov_position ();
1427
1428       if (tag == GCOV_TAG_PROGRAM_SUMMARY)
1429         {
1430           struct gcov_summary summary;
1431           gcov_read_summary (&summary);
1432           object_runs += summary.ctrs[GCOV_COUNTER_ARCS].runs;
1433           program_count++;
1434         }
1435       else if (tag == GCOV_TAG_BUILD_INFO)
1436         {
1437           gcov_unsigned_t num_strings;
1438           char **build_info_strings = gcov_read_build_info (length,
1439                                                             &num_strings);
1440           for (unsigned i = 0; i < num_strings; i++)
1441             free (build_info_strings[i]);
1442           free (build_info_strings);
1443         }
1444       else if (tag == GCOV_TAG_COMDAT_ZERO_FIXUP)
1445         {
1446           gcov_unsigned_t num_fn;
1447           int *zero_fixup_flags = gcov_read_comdat_zero_fixup (length, &num_fn);
1448           free (zero_fixup_flags);
1449         }
1450       else if (tag == GCOV_TAG_FUNCTION && !length)
1451         ; /* placeholder  */
1452       else if (tag == GCOV_TAG_FUNCTION && length == GCOV_TAG_FUNCTION_LENGTH)
1453         {
1454           unsigned ident;
1455           struct function_info *fn_n;
1456
1457           /* Try to find the function in the list.  To speed up the
1458              search, first start from the last function found.  */
1459           ident = gcov_read_unsigned ();
1460           fn_n = fns;
1461           for (fn = fn ? fn->next : NULL; ; fn = fn->next)
1462             {
1463               if (fn)
1464                 ;
1465               else if ((fn = fn_n))
1466                 fn_n = NULL;
1467               else
1468                 {
1469                   fnotice (stderr, "%s:unknown function '%u'\n",
1470                            da_file_name, ident);
1471                   break;
1472                 }
1473               if (fn->ident == ident)
1474                 break;
1475             }
1476
1477           if (!fn)
1478             ;
1479           else if (gcov_read_unsigned () != fn->lineno_checksum
1480                    || gcov_read_unsigned () != fn->cfg_checksum)
1481             {
1482             mismatch:;
1483               fnotice (stderr, "%s:profile mismatch for '%s'\n",
1484                        da_file_name, fn->name);
1485               goto cleanup;
1486             }
1487         }
1488       else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn)
1489         {
1490           if (length != GCOV_TAG_COUNTER_LENGTH (fn->num_counts))
1491             goto mismatch;
1492
1493           if (!fn->counts)
1494             fn->counts = XCNEWVEC (gcov_type, fn->num_counts);
1495
1496           for (ix = 0; ix != fn->num_counts; ix++)
1497             fn->counts[ix] += gcov_read_counter ();
1498         }
1499       gcov_sync (base, length);
1500       if ((error = gcov_is_error ()))
1501         {
1502           fnotice (stderr, error < 0 ? "%s:overflowed\n" : "%s:corrupted\n",
1503                    da_file_name);
1504           goto cleanup;
1505         }
1506     }
1507
1508   gcov_close ();
1509   return 0;
1510 }
1511
1512 /* Solve the flow graph. Propagate counts from the instrumented arcs
1513    to the blocks and the uninstrumented arcs.  */
1514
1515 static void
1516 solve_flow_graph (function_t *fn)
1517 {
1518   unsigned ix;
1519   arc_t *arc;
1520   gcov_type *count_ptr = fn->counts;
1521   block_t *blk;
1522   block_t *valid_blocks = NULL;    /* valid, but unpropagated blocks.  */
1523   block_t *invalid_blocks = NULL;  /* invalid, but inferable blocks.  */
1524
1525   /* The arcs were built in reverse order.  Fix that now.  */
1526   for (ix = fn->num_blocks; ix--;)
1527     {
1528       arc_t *arc_p, *arc_n;
1529
1530       for (arc_p = NULL, arc = fn->blocks[ix].succ; arc;
1531            arc_p = arc, arc = arc_n)
1532         {
1533           arc_n = arc->succ_next;
1534           arc->succ_next = arc_p;
1535         }
1536       fn->blocks[ix].succ = arc_p;
1537
1538       for (arc_p = NULL, arc = fn->blocks[ix].pred; arc;
1539            arc_p = arc, arc = arc_n)
1540         {
1541           arc_n = arc->pred_next;
1542           arc->pred_next = arc_p;
1543         }
1544       fn->blocks[ix].pred = arc_p;
1545     }
1546
1547   if (fn->num_blocks < 2)
1548     fnotice (stderr, "%s:'%s' lacks entry and/or exit blocks\n",
1549              bbg_file_name, fn->name);
1550   else
1551     {
1552       if (fn->blocks[ENTRY_BLOCK].num_pred)
1553         fnotice (stderr, "%s:'%s' has arcs to entry block\n",
1554                  bbg_file_name, fn->name);
1555       else
1556         /* We can't deduce the entry block counts from the lack of
1557            predecessors.  */
1558         fn->blocks[ENTRY_BLOCK].num_pred = ~(unsigned)0;
1559
1560       if (fn->blocks[EXIT_BLOCK].num_succ)
1561         fnotice (stderr, "%s:'%s' has arcs from exit block\n",
1562                  bbg_file_name, fn->name);
1563       else
1564         /* Likewise, we can't deduce exit block counts from the lack
1565            of its successors.  */
1566         fn->blocks[EXIT_BLOCK].num_succ = ~(unsigned)0;
1567     }
1568
1569   /* Propagate the measured counts, this must be done in the same
1570      order as the code in profile.c  */
1571   for (ix = 0, blk = fn->blocks; ix != fn->num_blocks; ix++, blk++)
1572     {
1573       block_t const *prev_dst = NULL;
1574       int out_of_order = 0;
1575       int non_fake_succ = 0;
1576
1577       for (arc = blk->succ; arc; arc = arc->succ_next)
1578         {
1579           if (!arc->fake)
1580             non_fake_succ++;
1581
1582           if (!arc->on_tree)
1583             {
1584               if (count_ptr)
1585                 arc->count = *count_ptr++;
1586               arc->count_valid = 1;
1587               blk->num_succ--;
1588               arc->dst->num_pred--;
1589             }
1590           if (prev_dst && prev_dst > arc->dst)
1591             out_of_order = 1;
1592           prev_dst = arc->dst;
1593         }
1594       if (non_fake_succ == 1)
1595         {
1596           /* If there is only one non-fake exit, it is an
1597              unconditional branch.  */
1598           for (arc = blk->succ; arc; arc = arc->succ_next)
1599             if (!arc->fake)
1600               {
1601                 arc->is_unconditional = 1;
1602                 /* If this block is instrumenting a call, it might be
1603                    an artificial block. It is not artificial if it has
1604                    a non-fallthrough exit, or the destination of this
1605                    arc has more than one entry.  Mark the destination
1606                    block as a return site, if none of those conditions
1607                    hold.  */
1608                 if (blk->is_call_site && arc->fall_through
1609                     && arc->dst->pred == arc && !arc->pred_next)
1610                   arc->dst->is_call_return = 1;
1611               }
1612         }
1613
1614       /* Sort the successor arcs into ascending dst order. profile.c
1615          normally produces arcs in the right order, but sometimes with
1616          one or two out of order.  We're not using a particularly
1617          smart sort.  */
1618       if (out_of_order)
1619         {
1620           arc_t *start = blk->succ;
1621           unsigned changes = 1;
1622
1623           while (changes)
1624             {
1625               arc_t *arc, *arc_p, *arc_n;
1626
1627               changes = 0;
1628               for (arc_p = NULL, arc = start; (arc_n = arc->succ_next);)
1629                 {
1630                   if (arc->dst > arc_n->dst)
1631                     {
1632                       changes = 1;
1633                       if (arc_p)
1634                         arc_p->succ_next = arc_n;
1635                       else
1636                         start = arc_n;
1637                       arc->succ_next = arc_n->succ_next;
1638                       arc_n->succ_next = arc;
1639                       arc_p = arc_n;
1640                     }
1641                   else
1642                     {
1643                       arc_p = arc;
1644                       arc = arc_n;
1645                     }
1646                 }
1647             }
1648           blk->succ = start;
1649         }
1650
1651       /* Place it on the invalid chain, it will be ignored if that's
1652          wrong.  */
1653       blk->invalid_chain = 1;
1654       blk->chain = invalid_blocks;
1655       invalid_blocks = blk;
1656     }
1657
1658   while (invalid_blocks || valid_blocks)
1659     {
1660       while ((blk = invalid_blocks))
1661         {
1662           gcov_type total = 0;
1663           const arc_t *arc;
1664
1665           invalid_blocks = blk->chain;
1666           blk->invalid_chain = 0;
1667           if (!blk->num_succ)
1668             for (arc = blk->succ; arc; arc = arc->succ_next)
1669               total += arc->count;
1670           else if (!blk->num_pred)
1671             for (arc = blk->pred; arc; arc = arc->pred_next)
1672               total += arc->count;
1673           else
1674             continue;
1675
1676           blk->count = total;
1677           blk->count_valid = 1;
1678           blk->chain = valid_blocks;
1679           blk->valid_chain = 1;
1680           valid_blocks = blk;
1681         }
1682       while ((blk = valid_blocks))
1683         {
1684           gcov_type total;
1685           arc_t *arc, *inv_arc;
1686
1687           valid_blocks = blk->chain;
1688           blk->valid_chain = 0;
1689           if (blk->num_succ == 1)
1690             {
1691               block_t *dst;
1692
1693               total = blk->count;
1694               inv_arc = NULL;
1695               for (arc = blk->succ; arc; arc = arc->succ_next)
1696                 {
1697                   total -= arc->count;
1698                   if (!arc->count_valid)
1699                     inv_arc = arc;
1700                 }
1701               dst = inv_arc->dst;
1702               inv_arc->count_valid = 1;
1703               inv_arc->count = total;
1704               blk->num_succ--;
1705               dst->num_pred--;
1706               if (dst->count_valid)
1707                 {
1708                   if (dst->num_pred == 1 && !dst->valid_chain)
1709                     {
1710                       dst->chain = valid_blocks;
1711                       dst->valid_chain = 1;
1712                       valid_blocks = dst;
1713                     }
1714                 }
1715               else
1716                 {
1717                   if (!dst->num_pred && !dst->invalid_chain)
1718                     {
1719                       dst->chain = invalid_blocks;
1720                       dst->invalid_chain = 1;
1721                       invalid_blocks = dst;
1722                     }
1723                 }
1724             }
1725           if (blk->num_pred == 1)
1726             {
1727               block_t *src;
1728
1729               total = blk->count;
1730               inv_arc = NULL;
1731               for (arc = blk->pred; arc; arc = arc->pred_next)
1732                 {
1733                   total -= arc->count;
1734                   if (!arc->count_valid)
1735                     inv_arc = arc;
1736                 }
1737               src = inv_arc->src;
1738               inv_arc->count_valid = 1;
1739               inv_arc->count = total;
1740               blk->num_pred--;
1741               src->num_succ--;
1742               if (src->count_valid)
1743                 {
1744                   if (src->num_succ == 1 && !src->valid_chain)
1745                     {
1746                       src->chain = valid_blocks;
1747                       src->valid_chain = 1;
1748                       valid_blocks = src;
1749                     }
1750                 }
1751               else
1752                 {
1753                   if (!src->num_succ && !src->invalid_chain)
1754                     {
1755                       src->chain = invalid_blocks;
1756                       src->invalid_chain = 1;
1757                       invalid_blocks = src;
1758                     }
1759                 }
1760             }
1761         }
1762     }
1763
1764   /* If the graph has been correctly solved, every block will have a
1765      valid count.  */
1766   for (ix = 0; ix < fn->num_blocks; ix++)
1767     if (!fn->blocks[ix].count_valid)
1768       {
1769         fnotice (stderr, "%s:graph is unsolvable for '%s'\n",
1770                  bbg_file_name, fn->name);
1771         break;
1772       }
1773 }
1774
1775 /* Mark all the blocks only reachable via an incoming catch.  */
1776
1777 static void
1778 find_exception_blocks (function_t *fn)
1779 {
1780   unsigned ix;
1781   block_t **queue = XALLOCAVEC (block_t *, fn->num_blocks);
1782
1783   /* First mark all blocks as exceptional.  */
1784   for (ix = fn->num_blocks; ix--;)
1785     fn->blocks[ix].exceptional = 1;
1786
1787   /* Now mark all the blocks reachable via non-fake edges */
1788   queue[0] = fn->blocks;
1789   queue[0]->exceptional = 0;
1790   for (ix = 1; ix;)
1791     {
1792       block_t *block = queue[--ix];
1793       const arc_t *arc;
1794
1795       for (arc = block->succ; arc; arc = arc->succ_next)
1796         if (!arc->fake && !arc->is_throw && arc->dst->exceptional)
1797           {
1798             arc->dst->exceptional = 0;
1799             queue[ix++] = arc->dst;
1800           }
1801     }
1802 }
1803 \f
1804
1805 /* Increment totals in COVERAGE according to arc ARC.  */
1806
1807 static void
1808 add_branch_counts (coverage_t *coverage, const arc_t *arc)
1809 {
1810   if (arc->is_call_non_return)
1811     {
1812       coverage->calls++;
1813       if (arc->src->count)
1814         coverage->calls_executed++;
1815     }
1816   else if (!arc->is_unconditional)
1817     {
1818       coverage->branches++;
1819       if (arc->src->count)
1820         coverage->branches_executed++;
1821       if (arc->count)
1822         coverage->branches_taken++;
1823     }
1824 }
1825
1826 /* Format a GCOV_TYPE integer as either a percent ratio, or absolute
1827    count.  If dp >= 0, format TOP/BOTTOM * 100 to DP decimal places.
1828    If DP is zero, no decimal point is printed. Only print 100% when
1829    TOP==BOTTOM and only print 0% when TOP=0.  If dp < 0, then simply
1830    format TOP.  Return pointer to a static string.  */
1831
1832 static char const *
1833 format_gcov (gcov_type top, gcov_type bottom, int dp)
1834 {
1835   static char buffer[20];
1836
1837   if (dp >= 0)
1838     {
1839       float ratio = bottom ? (float)top / bottom : 0;
1840       int ix;
1841       unsigned limit = 100;
1842       unsigned percent;
1843
1844       for (ix = dp; ix--; )
1845         limit *= 10;
1846
1847       percent = (unsigned) (ratio * limit + (float)0.5);
1848       if (percent <= 0 && top)
1849         percent = 1;
1850       else if (percent >= limit && top != bottom)
1851         percent = limit - 1;
1852       ix = sprintf (buffer, "%.*u%%", dp + 1, percent);
1853       if (dp)
1854         {
1855           dp++;
1856           do
1857             {
1858               buffer[ix+1] = buffer[ix];
1859               ix--;
1860             }
1861           while (dp--);
1862           buffer[ix + 1] = '.';
1863         }
1864     }
1865   else
1866     sprintf (buffer, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT)top);
1867
1868   return buffer;
1869 }
1870
1871 /* Summary of execution */
1872
1873 static void
1874 executed_summary (unsigned lines, unsigned executed)
1875 {
1876   if (lines)
1877     fnotice (stdout, "Lines executed:%s of %d\n",
1878              format_gcov (executed, lines, 2), lines);
1879   else
1880     fnotice (stdout, "No executable lines\n");
1881 }
1882
1883 /* Output summary info for a function or file.  */
1884
1885 static void
1886 function_summary (const coverage_t *coverage, const char *title)
1887 {
1888   fnotice (stdout, "%s '%s'\n", title, coverage->name);
1889   executed_summary (coverage->lines, coverage->lines_executed);
1890
1891   if (flag_branches)
1892     {
1893       if (coverage->branches)
1894         {
1895           fnotice (stdout, "Branches executed:%s of %d\n",
1896                    format_gcov (coverage->branches_executed,
1897                                 coverage->branches, 2),
1898                    coverage->branches);
1899           fnotice (stdout, "Taken at least once:%s of %d\n",
1900                    format_gcov (coverage->branches_taken,
1901                                 coverage->branches, 2),
1902                    coverage->branches);
1903         }
1904       else
1905         fnotice (stdout, "No branches\n");
1906       if (coverage->calls)
1907         fnotice (stdout, "Calls executed:%s of %d\n",
1908                  format_gcov (coverage->calls_executed, coverage->calls, 2),
1909                  coverage->calls);
1910       else
1911         fnotice (stdout, "No calls\n");
1912     }
1913 }
1914
1915 /* Canonicalize the filename NAME by canonicalizing directory
1916    separators, eliding . components and resolving .. components
1917    appropriately.  Always returns a unique string.  */
1918
1919 static char *
1920 canonicalize_name (const char *name)
1921 {
1922   /* The canonical name cannot be longer than the incoming name.  */
1923   char *result = XNEWVEC (char, strlen (name) + 1);
1924   const char *base = name, *probe;
1925   char *ptr = result;
1926   char *dd_base;
1927   int slash = 0;
1928
1929 #if HAVE_DOS_BASED_FILE_SYSTEM
1930   if (base[0] && base[1] == ':')
1931     {
1932       result[0] = base[0];
1933       result[1] = ':';
1934       base += 2;
1935       ptr += 2;
1936     }
1937 #endif
1938   for (dd_base = ptr; *base; base = probe)
1939     {
1940       size_t len;
1941
1942       for (probe = base; *probe; probe++)
1943         if (IS_DIR_SEPARATOR (*probe))
1944           break;
1945
1946       len = probe - base;
1947       if (len == 1 && base[0] == '.')
1948         /* Elide a '.' directory */
1949         ;
1950       else if (len == 2 && base[0] == '.' && base[1] == '.')
1951         {
1952           /* '..', we can only elide it and the previous directory, if
1953              we're not a symlink.  */
1954           struct stat ATTRIBUTE_UNUSED buf;
1955
1956           *ptr = 0;
1957           if (dd_base == ptr
1958 #if defined (S_ISLNK)
1959               /* S_ISLNK is not POSIX.1-1996.  */
1960               || stat (result, &buf) || S_ISLNK (buf.st_mode)
1961 #endif
1962               )
1963             {
1964               /* Cannot elide, or unreadable or a symlink.  */
1965               dd_base = ptr + 2 + slash;
1966               goto regular;
1967             }
1968           while (ptr != dd_base && *ptr != '/')
1969             ptr--;
1970           slash = ptr != result;
1971         }
1972       else
1973         {
1974         regular:
1975           /* Regular pathname component.  */
1976           if (slash)
1977             *ptr++ = '/';
1978           memcpy (ptr, base, len);
1979           ptr += len;
1980           slash = 1;
1981         }
1982
1983       for (; IS_DIR_SEPARATOR (*probe); probe++)
1984         continue;
1985     }
1986   *ptr = 0;
1987
1988   return result;
1989 }
1990
1991 /* Generate an output file name. INPUT_NAME is the canonicalized main
1992    input file and SRC_NAME is the canonicalized file name.
1993    LONG_OUTPUT_NAMES and PRESERVE_PATHS affect name generation.  With
1994    long_output_names we prepend the processed name of the input file
1995    to each output name (except when the current source file is the
1996    input file, so you don't get a double concatenation). The two
1997    components are separated by '##'.  With preserve_paths we create a
1998    filename from all path components of the source file, replacing '/'
1999    with '#', and .. with '^', without it we simply take the basename
2000    component.  (Remember, the canonicalized name will already have
2001    elided '.' components and converted \\ separators.)  */
2002
2003 static char *
2004 make_gcov_file_name (const char *input_name, const char *src_name)
2005 {
2006   char *ptr;
2007   char *result;
2008
2009   if (flag_long_names && input_name && strcmp (src_name, input_name))
2010     {
2011       /* Generate the input filename part.  */
2012       result = XNEWVEC (char, strlen (input_name) + strlen (src_name) + 10);
2013
2014       ptr = result;
2015       ptr = mangle_name (input_name, ptr);
2016       ptr[0] = ptr[1] = '#';
2017       ptr += 2;
2018     }
2019   else
2020     {
2021       result = XNEWVEC (char, strlen (src_name) + 10);
2022       ptr = result;
2023     }
2024
2025   ptr = mangle_name (src_name, ptr);
2026   strcpy (ptr, ".gcov");
2027
2028   return result;
2029 }
2030
2031 static char *
2032 mangle_name (char const *base, char *ptr)
2033 {
2034   size_t len;
2035
2036   /* Generate the source filename part.  */
2037   if (!flag_preserve_paths)
2038     {
2039       base = lbasename (base);
2040       len = strlen (base);
2041       memcpy (ptr, base, len);
2042       ptr += len;
2043     }
2044   else
2045     {
2046       /* Convert '/' to '#', convert '..' to '^',
2047          convert ':' to '~' on DOS based file system.  */
2048       const char *probe;
2049
2050 #if HAVE_DOS_BASED_FILE_SYSTEM
2051       if (base[0] && base[1] == ':')
2052         {
2053           ptr[0] = base[0];
2054           ptr[1] = '~';
2055           ptr += 2;
2056           base += 2;
2057         }
2058 #endif
2059       for (; *base; base = probe)
2060         {
2061           size_t len;
2062
2063           for (probe = base; *probe; probe++)
2064             if (*probe == '/')
2065               break;
2066           len = probe - base;
2067           if (len == 2 && base[0] == '.' && base[1] == '.')
2068             *ptr++ = '^';
2069           else
2070             {
2071               memcpy (ptr, base, len);
2072               ptr += len;
2073             }
2074           if (*probe)
2075             {
2076               *ptr++ = '#';
2077               probe++;
2078             }
2079         }
2080     }
2081
2082   return ptr;
2083 }
2084
2085 /* Scan through the bb_data for each line in the block, increment
2086    the line number execution count indicated by the execution count of
2087    the appropriate basic block.  */
2088
2089 static void
2090 add_line_counts (coverage_t *coverage, function_t *fn)
2091 {
2092   unsigned ix;
2093   line_t *line = NULL; /* This is propagated from one iteration to the
2094                           next.  */
2095
2096   /* Scan each basic block.  */
2097   for (ix = 0; ix != fn->num_blocks; ix++)
2098     {
2099       block_t *block = &fn->blocks[ix];
2100       unsigned *encoding;
2101       const source_t *src = NULL;
2102       unsigned jx;
2103
2104       if (block->count && ix && ix + 1 != fn->num_blocks)
2105         fn->blocks_executed++;
2106       for (jx = 0, encoding = block->u.line.encoding;
2107            jx != block->u.line.num; jx++, encoding++)
2108         if (!*encoding)
2109           {
2110             src = &sources[*++encoding];
2111             jx++;
2112           }
2113         else
2114           {
2115             line = &src->lines[*encoding];
2116
2117             if (coverage)
2118               {
2119                 if (!line->exists)
2120                   coverage->lines++;
2121                 if (!line->count && block->count)
2122                   coverage->lines_executed++;
2123               }
2124             line->exists = 1;
2125             if (!block->exceptional)
2126               line->unexceptional = 1;
2127             line->count += block->count;
2128           }
2129       free (block->u.line.encoding);
2130       block->u.cycle.arc = NULL;
2131       block->u.cycle.ident = ~0U;
2132
2133       if (!ix || ix + 1 == fn->num_blocks)
2134         /* Entry or exit block */;
2135       else if (flag_all_blocks)
2136         {
2137           line_t *block_line = line;
2138
2139           if (!block_line)
2140             block_line = &sources[fn->src].lines[fn->line];
2141
2142           block->chain = block_line->u.blocks;
2143           block_line->u.blocks = block;
2144         }
2145       else if (flag_branches)
2146         {
2147           arc_t *arc;
2148
2149           for (arc = block->succ; arc; arc = arc->succ_next)
2150             {
2151               arc->line_next = line->u.branches;
2152               line->u.branches = arc;
2153               if (coverage && !arc->is_unconditional)
2154                 add_branch_counts (coverage, arc);
2155             }
2156         }
2157     }
2158   if (!line)
2159     fnotice (stderr, "%s:no lines for '%s'\n", bbg_file_name, fn->name);
2160 }
2161
2162 /* Accumulate the line counts of a file.  */
2163
2164 static void
2165 accumulate_line_counts (source_t *src)
2166 {
2167   line_t *line;
2168   function_t *fn, *fn_p, *fn_n;
2169   unsigned ix;
2170
2171   /* Reverse the function order.  */
2172   for (fn = src->functions, fn_p = NULL; fn;
2173        fn_p = fn, fn = fn_n)
2174     {
2175       fn_n = fn->line_next;
2176       fn->line_next = fn_p;
2177     }
2178   src->functions = fn_p;
2179
2180   for (ix = src->num_lines, line = src->lines; ix--; line++)
2181     {
2182       if (!flag_all_blocks)
2183         {
2184           arc_t *arc, *arc_p, *arc_n;
2185
2186           /* Total and reverse the branch information.  */
2187           for (arc = line->u.branches, arc_p = NULL; arc;
2188                arc_p = arc, arc = arc_n)
2189             {
2190               arc_n = arc->line_next;
2191               arc->line_next = arc_p;
2192
2193               add_branch_counts (&src->coverage, arc);
2194             }
2195           line->u.branches = arc_p;
2196         }
2197       else if (line->u.blocks)
2198         {
2199           /* The user expects the line count to be the number of times
2200              a line has been executed. Simply summing the block count
2201              will give an artificially high number.  The Right Thing
2202              is to sum the entry counts to the graph of blocks on this
2203              line, then find the elementary cycles of the local graph
2204              and add the transition counts of those cycles.  */
2205           block_t *block, *block_p, *block_n;
2206           gcov_type count = 0;
2207
2208           /* Reverse the block information.  */
2209           for (block = line->u.blocks, block_p = NULL; block;
2210                block_p = block, block = block_n)
2211             {
2212               block_n = block->chain;
2213               block->chain = block_p;
2214               block->u.cycle.ident = ix;
2215             }
2216           line->u.blocks = block_p;
2217
2218           /* Sum the entry arcs.  */
2219           for (block = line->u.blocks; block; block = block->chain)
2220             {
2221               arc_t *arc;
2222
2223               for (arc = block->pred; arc; arc = arc->pred_next)
2224                 {
2225                   if (arc->src->u.cycle.ident != ix)
2226                     count += arc->count;
2227                   if (flag_branches)
2228                     add_branch_counts (&src->coverage, arc);
2229                 }
2230
2231               /* Initialize the cs_count.  */
2232               for (arc = block->succ; arc; arc = arc->succ_next)
2233                 arc->cs_count = arc->count;
2234             }
2235
2236           /* Find the loops. This uses the algorithm described in
2237              Tiernan 'An Efficient Search Algorithm to Find the
2238              Elementary Circuits of a Graph', CACM Dec 1970. We hold
2239              the P array by having each block point to the arc that
2240              connects to the previous block. The H array is implicitly
2241              held because of the arc ordering, and the block's
2242              previous arc pointer.
2243
2244              Although the algorithm is O(N^3) for highly connected
2245              graphs, at worst we'll have O(N^2), as most blocks have
2246              only one or two exits. Most graphs will be small.
2247
2248              For each loop we find, locate the arc with the smallest
2249              transition count, and add that to the cumulative
2250              count.  Decrease flow over the cycle and remove the arc
2251              from consideration.  */
2252           for (block = line->u.blocks; block; block = block->chain)
2253             {
2254               block_t *head = block;
2255               arc_t *arc;
2256
2257             next_vertex:;
2258               arc = head->succ;
2259             current_vertex:;
2260               while (arc)
2261                 {
2262                   block_t *dst = arc->dst;
2263                   if (/* Already used that arc.  */
2264                       arc->cycle
2265                       /* Not to same graph, or before first vertex.  */
2266                       || dst->u.cycle.ident != ix
2267                       /* Already in path.  */
2268                       || dst->u.cycle.arc)
2269                     {
2270                       arc = arc->succ_next;
2271                       continue;
2272                     }
2273
2274                   if (dst == block)
2275                     {
2276                       /* Found a closing arc.  */
2277                       gcov_type cycle_count = arc->cs_count;
2278                       arc_t *cycle_arc = arc;
2279                       arc_t *probe_arc;
2280
2281                       /* Locate the smallest arc count of the loop.  */
2282                       for (dst = head; (probe_arc = dst->u.cycle.arc);
2283                            dst = probe_arc->src)
2284                         if (cycle_count > probe_arc->cs_count)
2285                           {
2286                             cycle_count = probe_arc->cs_count;
2287                             cycle_arc = probe_arc;
2288                           }
2289
2290                       count += cycle_count;
2291                       cycle_arc->cycle = 1;
2292
2293                       /* Remove the flow from the cycle.  */
2294                       arc->cs_count -= cycle_count;
2295                       for (dst = head; (probe_arc = dst->u.cycle.arc);
2296                            dst = probe_arc->src)
2297                         probe_arc->cs_count -= cycle_count;
2298
2299                       /* Unwind to the cyclic arc.  */
2300                       while (head != cycle_arc->src)
2301                         {
2302                           arc = head->u.cycle.arc;
2303                           head->u.cycle.arc = NULL;
2304                           head = arc->src;
2305                         }
2306                       /* Move on.  */
2307                       arc = arc->succ_next;
2308                       continue;
2309                     }
2310
2311                   /* Add new block to chain.  */
2312                   dst->u.cycle.arc = arc;
2313                   head = dst;
2314                   goto next_vertex;
2315                 }
2316               /* We could not add another vertex to the path. Remove
2317                  the last vertex from the list.  */
2318               arc = head->u.cycle.arc;
2319               if (arc)
2320                 {
2321                   /* It was not the first vertex. Move onto next arc.  */
2322                   head->u.cycle.arc = NULL;
2323                   head = arc->src;
2324                   arc = arc->succ_next;
2325                   goto current_vertex;
2326                 }
2327               /* Mark this block as unusable.  */
2328               block->u.cycle.ident = ~0U;
2329             }
2330
2331           line->count = count;
2332         }
2333
2334       if (line->exists)
2335         {
2336           src->coverage.lines++;
2337           if (line->count)
2338             src->coverage.lines_executed++;
2339         }
2340     }
2341 }
2342
2343 /* Output information about ARC number IX.  Returns nonzero if
2344    anything is output.  */
2345
2346 static int
2347 output_branch_count (FILE *gcov_file, int ix, const arc_t *arc)
2348 {
2349   if (arc->is_call_non_return)
2350     {
2351       if (arc->src->count)
2352         {
2353           fnotice (gcov_file, "call   %2d returned %s\n", ix,
2354                    format_gcov (arc->src->count - arc->count,
2355                                 arc->src->count, -flag_counts));
2356         }
2357       else
2358         fnotice (gcov_file, "call   %2d never executed\n", ix);
2359     }
2360   else if (!arc->is_unconditional)
2361     {
2362       if (arc->src->count)
2363         fnotice (gcov_file, "branch %2d taken %s%s\n", ix,
2364                  format_gcov (arc->count, arc->src->count, -flag_counts),
2365                  arc->fall_through ? " (fallthrough)"
2366                  : arc->is_throw ? " (throw)" : "");
2367       else
2368         fnotice (gcov_file, "branch %2d never executed\n", ix);
2369     }
2370   else if (flag_unconditional && !arc->dst->is_call_return)
2371     {
2372       if (arc->src->count)
2373         fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
2374                  format_gcov (arc->count, arc->src->count, -flag_counts));
2375       else
2376         fnotice (gcov_file, "unconditional %2d never executed\n", ix);
2377     }
2378   else
2379     return 0;
2380   return 1;
2381
2382 }
2383
2384 static const char *
2385 read_line (FILE *file)
2386 {
2387   static char *string;
2388   static size_t string_len;
2389   size_t pos = 0;
2390   char *ptr;
2391
2392   if (!string_len)
2393     {
2394       string_len = 200;
2395       string = XNEWVEC (char, string_len);
2396     }
2397
2398   while ((ptr = fgets (string + pos, string_len - pos, file)))
2399     {
2400       size_t len = strlen (string + pos);
2401
2402       if (string[pos + len - 1] == '\n')
2403         {
2404           string[pos + len - 1] = 0;
2405           return string;
2406         }
2407       pos += len;
2408       string = XRESIZEVEC (char, string, string_len * 2);
2409       string_len *= 2;
2410     }
2411
2412   return pos ? string : NULL;
2413 }
2414
2415 /* Read in the source file one line at a time, and output that line to
2416    the gcov file preceded by its execution count and other
2417    information.  */
2418
2419 static void
2420 output_lines (FILE *gcov_file, const source_t *src)
2421 {
2422   FILE *source_file;
2423   unsigned line_num;    /* current line number.  */
2424   const line_t *line;           /* current line info ptr.  */
2425   const char *retval = "";      /* status of source file reading.  */
2426   function_t *fn = NULL;
2427
2428   fprintf (gcov_file, "%9s:%5d:Source:%s\n", "-", 0, src->coverage.name);
2429   if (!multiple_files)
2430     {
2431       fprintf (gcov_file, "%9s:%5d:Graph:%s\n", "-", 0, bbg_file_name);
2432       fprintf (gcov_file, "%9s:%5d:Data:%s\n", "-", 0,
2433                no_data_file ? "-" : da_file_name);
2434       fprintf (gcov_file, "%9s:%5d:Runs:%u\n", "-", 0, object_runs);
2435     }
2436   fprintf (gcov_file, "%9s:%5d:Programs:%u\n", "-", 0, program_count);
2437
2438   source_file = fopen (src->name, "r");
2439   if (!source_file)
2440     {
2441       fnotice (stderr, "Cannot open source file %s\n", src->name);
2442       retval = NULL;
2443     }
2444   else if (src->file_time == 0)
2445     fprintf (gcov_file, "%9s:%5d:Source is newer than graph\n", "-", 0);
2446
2447   if (flag_branches)
2448     fn = src->functions;
2449
2450   for (line_num = 1, line = &src->lines[line_num];
2451        line_num < src->num_lines; line_num++, line++)
2452     {
2453       for (; fn && fn->line == line_num; fn = fn->line_next)
2454         {
2455           arc_t *arc = fn->blocks[EXIT_BLOCK].pred;
2456           gcov_type return_count = fn->blocks[EXIT_BLOCK].count;
2457           gcov_type called_count = fn->blocks[ENTRY_BLOCK].count;
2458
2459           for (; arc; arc = arc->pred_next)
2460             if (arc->fake)
2461               return_count -= arc->count;
2462
2463           fprintf (gcov_file, "function %s", flag_demangled_names ?
2464                    fn->demangled_name : fn->name);
2465           fprintf (gcov_file, " called %s",
2466                    format_gcov (called_count, 0, -1));
2467           fprintf (gcov_file, " returned %s",
2468                    format_gcov (return_count, called_count, 0));
2469           fprintf (gcov_file, " blocks executed %s",
2470                    format_gcov (fn->blocks_executed, fn->num_blocks - 2, 0));
2471           fprintf (gcov_file, "\n");
2472         }
2473
2474       if (retval)
2475         retval = read_line (source_file);
2476
2477       /* For lines which don't exist in the .bb file, print '-' before
2478          the source line.  For lines which exist but were never
2479          executed, print '#####' or '=====' before the source line.
2480          Otherwise, print the execution count before the source line.
2481          There are 16 spaces of indentation added before the source
2482          line so that tabs won't be messed up.  */
2483       fprintf (gcov_file, "%9s:%5u:%s\n",
2484                !line->exists ? "-" : line->count
2485                ? format_gcov (line->count, 0, -1)
2486                : line->unexceptional ? "#####" : "=====", line_num,
2487                retval ? retval : "/*EOF*/");
2488
2489       if (flag_all_blocks)
2490         {
2491           block_t *block;
2492           arc_t *arc;
2493           int ix, jx;
2494
2495           for (ix = jx = 0, block = line->u.blocks; block;
2496                block = block->chain)
2497             {
2498               if (!block->is_call_return)
2499                 fprintf (gcov_file, "%9s:%5u-block %2d\n",
2500                          !line->exists ? "-" : block->count
2501                          ? format_gcov (block->count, 0, -1)
2502                          : block->exceptional ? "%%%%%" : "$$$$$",
2503                          line_num, ix++);
2504               if (flag_branches)
2505                 for (arc = block->succ; arc; arc = arc->succ_next)
2506                   jx += output_branch_count (gcov_file, jx, arc);
2507             }
2508         }
2509       else if (flag_branches)
2510         {
2511           int ix;
2512           arc_t *arc;
2513
2514           for (ix = 0, arc = line->u.branches; arc; arc = arc->line_next)
2515             ix += output_branch_count (gcov_file, ix, arc);
2516         }
2517     }
2518
2519   /* Handle all remaining source lines.  There may be lines after the
2520      last line of code.  */
2521   if (retval)
2522     {
2523       for (; (retval = read_line (source_file)); line_num++)
2524         fprintf (gcov_file, "%9s:%5u:%s\n", "-", line_num, retval);
2525     }
2526
2527   if (source_file)
2528     fclose (source_file);
2529 }