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