gcc/gcov.c

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