1 /* Gcov.c: prepend line execution counts and branch probabilities to a
3 Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998,
4 1999, 2000, 2001, 2002, 2003 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>
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)
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.
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. */
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. */
29 /* ??? Should have an option to print the number of basic blocks, and the
30 percent of them that are covered. */
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. */
41 /* Need an option to show individual block counts, and show
42 probabilities of fall through arcs. */
46 #include "coretypes.h"
58 /* The bbg file is generated by -ftest-coverage option. The da file is
59 generated by a program compiled with -fprofile-arcs. Their formats
60 are documented in gcov-io.h. */
62 /* The functions in this file for creating and solution program flow graphs
63 are very similar to functions in the gcc source file profile.c. In
64 some places we make use of the knowledge of how profile.c works to
65 select particular algorithms here. */
67 /* This is the size of the buffer used to read in source file lines. */
69 #define STRING_SIZE 200
75 /* Describes an arc between two basic blocks. */
77 typedef struct arc_info
79 /* source and destination blocks. */
80 struct block_info *src;
81 struct block_info *dst;
83 /* transition counts. */
86 unsigned int count_valid : 1;
87 unsigned int on_tree : 1;
88 unsigned int fake : 1;
89 unsigned int fall_through : 1;
91 /* Arc is for a function that abnormally returns. */
92 unsigned int is_call_non_return : 1;
94 /* Arc is for catch/setjump. */
95 unsigned int is_nonlocal_return : 1;
97 /* Is an unconditional branch. */
98 unsigned int is_unconditional : 1;
100 /* Loop making arc. */
101 unsigned int cycle : 1;
103 /* Next branch on line. */
104 struct arc_info *line_next;
106 /* Links to next arc on src and dst lists. */
107 struct arc_info *succ_next;
108 struct arc_info *pred_next;
111 /* Describes a basic block. Contains lists of arcs to successor and
112 predecessor blocks. */
114 typedef struct block_info
116 /* Chain of exit and entry arcs. */
120 /* Number of unprocessed exit and entry arcs. */
124 /* Block execution count. */
127 unsigned count_valid : 1;
128 unsigned valid_chain : 1;
129 unsigned invalid_chain : 1;
131 /* Block is a call instrumenting site. */
132 unsigned is_call_site : 1; /* Does the call. */
133 unsigned is_call_return : 1; /* Is the return. */
135 /* Block is a landing pad for longjmp or throw. */
136 unsigned is_nonlocal_return : 1;
142 /* Array of line numbers and source files. source files are
143 introduced by a linenumber of zero, the next 'line number' is
144 the number of the source file. Always starts with a source
148 } line; /* Valid until blocks are linked onto lines */
151 /* Single line graph cycle workspace. Used for all-blocks
155 } cycle; /* Used in all-blocks mode, after blocks are linked onto
159 /* Temporary chain for solving graph, and for chaining blocks on one
161 struct block_info *chain;
165 /* Describes a single function. Contains an array of basic blocks. */
167 typedef struct function_info
169 /* Name of function. */
174 /* Array of basic blocks. */
177 unsigned blocks_executed;
179 /* Raw arc coverage counts. */
183 /* First line number. */
185 struct source_info *src;
187 /* Next function in same source file. */
188 struct function_info *line_next;
191 struct function_info *next;
194 /* Describes coverage of a file or function. */
196 typedef struct coverage_info
202 int branches_executed;
211 /* Describes a single line of source. Contains a chain of basic blocks
214 typedef struct line_info
216 gcov_type count; /* execution count */
219 arc_t *branches; /* branches from blocks that end on this
220 line. Used for branch-counts when not
222 block_t *blocks; /* blocks which start on this line. Used
223 in all-blocks mode. */
228 /* Describes a file mentioned in the block graph. Contains an array
231 typedef struct source_info
233 /* Name of source file. */
237 /* Array of line information. */
243 /* Functions in this source file. These are in ascending line
245 function_t *functions;
247 /* Next source file. */
248 struct source_info *next;
251 /* Holds a list of function basic block graphs. */
253 static function_t *functions;
255 /* This points to the head of the sourcefile structure list. */
257 static source_t *sources;
259 /* This holds data summary information. */
261 static struct gcov_summary object_summary;
262 static unsigned program_count;
264 /* Modification time of graph file. */
266 static time_t bbg_file_time;
268 /* Name and file pointer of the input file for the basic block graph. */
270 static char *bbg_file_name;
272 /* Stamp of the bbg file */
273 static unsigned bbg_stamp;
275 /* Name and file pointer of the input file for the arc count data. */
277 static char *da_file_name;
279 /* Output branch probabilities. */
281 static int flag_branches = 0;
283 /* Show unconditional branches too. */
284 static int flag_unconditional = 0;
286 /* Output a gcov file if this is true. This is on by default, and can
287 be turned off by the -n option. */
289 static int flag_gcov_file = 1;
291 /* For included files, make the gcov output file name include the name
292 of the input source file. For example, if x.h is included in a.c,
293 then the output file name is a.c##x.h.gcov instead of x.h.gcov. */
295 static int flag_long_names = 0;
297 /* Output count information for every basic block, not merely those
298 that contain line number information. */
300 static int flag_all_blocks = 0;
302 /* Output summary info for each function. */
304 static int flag_function_summary = 0;
306 /* Object directory file prefix. This is the directory/file where the
307 graph and data files are looked for, if nonzero. */
309 static char *object_directory = 0;
311 /* Preserve all pathname components. Needed when object files and
312 source files are in subdirectories. '/' is mangled as '#', '.' is
313 elided and '..' mangled to '^'. */
315 static int flag_preserve_paths = 0;
317 /* Output the number of times a branch was taken as opposed to the percentage
318 of times it was taken. */
320 static int flag_counts = 0;
322 /* Forward declarations. */
323 static void fnotice (FILE *, const char *, ...) ATTRIBUTE_PRINTF_2;
324 static int process_args (int, char **);
325 static void print_usage (int) ATTRIBUTE_NORETURN;
326 static void print_version (void) ATTRIBUTE_NORETURN;
327 static void process_file (const char *);
328 static void create_file_names (const char *);
329 static source_t *find_source (const char *);
330 static int read_graph_file (void);
331 static int read_count_file (void);
332 static void solve_flow_graph (function_t *);
333 static void add_branch_counts (coverage_t *, const arc_t *);
334 static void add_line_counts (coverage_t *, function_t *);
335 static void function_summary (const coverage_t *, const char *);
336 static const char *format_gcov (gcov_type, gcov_type, int);
337 static void accumulate_line_counts (source_t *);
338 static int output_branch_count (FILE *, int, const arc_t *);
339 static void output_lines (FILE *, const source_t *);
340 static char *make_gcov_file_name (const char *, const char *);
341 static void release_structures (void);
342 extern int main (int, char **);
345 main (int argc, char **argv)
351 argno = process_args (argc, argv);
355 for (; argno != argc; argno++)
357 release_structures ();
359 process_file (argv[argno]);
366 fnotice (FILE *file, const char *msgid, ...)
370 va_start (ap, msgid);
371 vfprintf (file, _(msgid), ap);
375 /* More 'friendly' abort that prints the line and file.
376 config.h can #define abort fancy_abort if you like that sort of thing. */
377 extern void fancy_abort (void) ATTRIBUTE_NORETURN;
382 fnotice (stderr, "Internal gcov abort.\n");
383 exit (FATAL_EXIT_CODE);
386 /* Print a usage message and exit. If ERROR_P is nonzero, this is an error,
387 otherwise the output of --help. */
390 print_usage (int error_p)
392 FILE *file = error_p ? stderr : stdout;
393 int status = error_p ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE;
395 fnotice (file, "Usage: gcov [OPTION]... SOURCEFILE\n\n");
396 fnotice (file, "Print code coverage information.\n\n");
397 fnotice (file, " -h, --help Print this help, then exit\n");
398 fnotice (file, " -v, --version Print version number, then exit\n");
399 fnotice (file, " -a, --all-blocks Show information for every basic block\n");
400 fnotice (file, " -b, --branch-probabilities Include branch probabilities in output\n");
401 fnotice (file, " -c, --branch-counts Given counts of branches taken\n\
402 rather than percentages\n");
403 fnotice (file, " -n, --no-output Do not create an output file\n");
404 fnotice (file, " -l, --long-file-names Use long output file names for included\n\
406 fnotice (file, " -f, --function-summaries Output summaries for each function\n");
407 fnotice (file, " -o, --object-directory DIR|FILE Search for object files in DIR or called FILE\n");
408 fnotice (file, " -p, --preserve-paths Preserve all pathname components\n");
409 fnotice (file, " -u, --unconditional-branches Show unconditional branch counts too\n");
410 fnotice (file, "\nFor bug reporting instructions, please see:\n%s.\n",
415 /* Print version information and exit. */
420 fnotice (stdout, "gcov (GCC) %s\n", version_string);
421 fnotice (stdout, "Copyright (C) 2003 Free Software Foundation, Inc.\n");
423 "This is free software; see the source for copying conditions.\n"
424 "There is NO warranty; not even for MERCHANTABILITY or \n"
425 "FITNESS FOR A PARTICULAR PURPOSE.\n\n");
426 exit (SUCCESS_EXIT_CODE);
429 static const struct option options[] =
431 { "help", no_argument, NULL, 'h' },
432 { "version", no_argument, NULL, 'v' },
433 { "all-blocks", no_argument, NULL, 'a' },
434 { "branch-probabilities", no_argument, NULL, 'b' },
435 { "branch-counts", no_argument, NULL, 'c' },
436 { "no-output", no_argument, NULL, 'n' },
437 { "long-file-names", no_argument, NULL, 'l' },
438 { "function-summaries", no_argument, NULL, 'f' },
439 { "preserve-paths", no_argument, NULL, 'p' },
440 { "object-directory", required_argument, NULL, 'o' },
441 { "object-file", required_argument, NULL, 'o' },
442 { "unconditional-branches", no_argument, NULL, 'u' },
446 /* Process args, return index to first non-arg. */
449 process_args (int argc, char **argv)
453 while ((opt = getopt_long (argc, argv, "abcfhlno:puv", options, NULL)) != -1)
467 flag_function_summary = 1;
471 /* print_usage will exit. */
479 object_directory = optarg;
482 flag_preserve_paths = 1;
485 flag_unconditional = 1;
489 /* print_version will exit. */
492 /* print_usage will exit. */
499 /* Process a single source file. */
502 process_file (const char *file_name)
507 create_file_names (file_name);
508 if (read_graph_file ())
513 fnotice (stderr, "%s:no functions found\n", bbg_file_name);
517 if (read_count_file ())
520 for (fn = functions; fn; fn = fn->next)
521 solve_flow_graph (fn);
522 for (src = sources; src; src = src->next)
523 src->lines = xcalloc (src->num_lines, sizeof (line_t));
524 for (fn = functions; fn; fn = fn->next)
528 memset (&coverage, 0, sizeof (coverage));
529 coverage.name = fn->name;
530 add_line_counts (flag_function_summary ? &coverage : NULL, fn);
531 if (flag_function_summary)
533 function_summary (&coverage, "Function");
534 fnotice (stdout, "\n");
538 for (src = sources; src; src = src->next)
540 accumulate_line_counts (src);
541 function_summary (&src->coverage, "File");
544 char *gcov_file_name = make_gcov_file_name (file_name, src->name);
545 FILE *gcov_file = fopen (gcov_file_name, "w");
549 fnotice (stdout, "%s:creating `%s'\n",
550 src->name, gcov_file_name);
551 output_lines (gcov_file, src);
552 if (ferror (gcov_file))
553 fnotice (stderr, "%s:error writing output file `%s'\n",
554 src->name, gcov_file_name);
558 fnotice (stderr, "%s:could not open output file `%s'\n",
559 src->name, gcov_file_name);
560 free (gcov_file_name);
562 fnotice (stdout, "\n");
566 /* Release all memory used. */
569 release_structures (void)
574 free (bbg_file_name);
576 da_file_name = bbg_file_name = NULL;
580 while ((src = sources))
588 while ((fn = functions))
593 functions = fn->next;
594 for (ix = fn->num_blocks, block = fn->blocks; ix--; block++)
598 for (arc = block->succ; arc; arc = arc_n)
600 arc_n = arc->succ_next;
609 /* Generate the names of the graph and data files. If OBJECT_DIRECTORY
610 is not specified, these are looked for in the current directory,
611 and named from the basename of the FILE_NAME sans extension. If
612 OBJECT_DIRECTORY is specified and is a directory, the files are in
613 that directory, but named from the basename of the FILE_NAME, sans
614 extension. Otherwise OBJECT_DIRECTORY is taken to be the name of
615 the object *file*, and the data files are named from that. */
618 create_file_names (const char *file_name)
622 int length = strlen (file_name);
625 if (object_directory && object_directory[0])
629 length += strlen (object_directory) + 2;
630 name = xmalloc (length);
633 base = !stat (object_directory, &status) && S_ISDIR (status.st_mode);
634 strcat (name, object_directory);
635 if (base && name[strlen (name) - 1] != '/')
640 name = xmalloc (length + 1);
647 /* Append source file name. */
648 cptr = strrchr (file_name, '/');
649 strcat (name, cptr ? cptr + 1 : file_name);
652 /* Remove the extension. */
653 cptr = strrchr (name, '.');
657 length = strlen (name);
659 bbg_file_name = xmalloc (length + strlen (GCOV_NOTE_SUFFIX) + 1);
660 strcpy (bbg_file_name, name);
661 strcpy (bbg_file_name + length, GCOV_NOTE_SUFFIX);
663 da_file_name = xmalloc (length + strlen (GCOV_DATA_SUFFIX) + 1);
664 strcpy (da_file_name, name);
665 strcpy (da_file_name + length, GCOV_DATA_SUFFIX);
670 /* Find or create a source file structure for FILE_NAME. Copies
671 FILE_NAME on creation */
674 find_source (const char *file_name)
679 file_name = "<unknown>";
681 for (src = sources; src; src = src->next)
682 if (!strcmp (file_name, src->name))
685 src = xcalloc (1, sizeof (source_t));
686 src->name = xstrdup (file_name);
687 src->coverage.name = src->name;
688 src->index = sources ? sources->index + 1 : 1;
695 /* Read the graph file. Return nonzero on fatal error. */
698 read_graph_file (void)
701 unsigned current_tag = 0;
702 struct function_info *fn = NULL;
703 source_t *src = NULL;
707 if (!gcov_open (bbg_file_name, 1))
709 fnotice (stderr, "%s:cannot open graph file\n", bbg_file_name);
712 bbg_file_time = gcov_time ();
713 if (!gcov_magic (gcov_read_unsigned (), GCOV_NOTE_MAGIC))
715 fnotice (stderr, "%s:not a gcov graph file\n", bbg_file_name);
720 version = gcov_read_unsigned ();
721 if (version != GCOV_VERSION)
725 GCOV_UNSIGNED2STRING (v, version);
726 GCOV_UNSIGNED2STRING (e, GCOV_VERSION);
728 fnotice (stderr, "%s:version `%.4s', prefer `%.4s'\n",
729 bbg_file_name, v, e);
731 bbg_stamp = gcov_read_unsigned ();
733 while ((tag = gcov_read_unsigned ()))
735 unsigned length = gcov_read_unsigned ();
736 gcov_position_t base = gcov_position ();
738 if (tag == GCOV_TAG_FUNCTION)
741 unsigned ident, checksum, lineno;
743 function_t *probe, *prev;
745 ident = gcov_read_unsigned ();
746 checksum = gcov_read_unsigned ();
747 function_name = xstrdup (gcov_read_string ());
748 src = find_source (gcov_read_string ());
749 lineno = gcov_read_unsigned ();
751 fn = xcalloc (1, sizeof (function_t));
752 fn->name = function_name;
754 fn->checksum = checksum;
758 fn->next = functions;
762 if (lineno >= src->num_lines)
763 src->num_lines = lineno + 1;
764 /* Now insert it into the source file's list of
765 functions. Normally functions will be encountered in
766 ascending order, so a simple scan is quick. */
767 for (probe = src->functions, prev = NULL;
768 probe && probe->line > lineno;
769 prev = probe, probe = probe->line_next)
771 fn->line_next = probe;
773 prev->line_next = fn;
777 else if (fn && tag == GCOV_TAG_BLOCKS)
780 fnotice (stderr, "%s:already seen blocks for `%s'\n",
781 bbg_file_name, fn->name);
784 unsigned ix, num_blocks = GCOV_TAG_BLOCKS_NUM (length);
785 fn->num_blocks = num_blocks;
787 fn->blocks = xcalloc (fn->num_blocks, sizeof (block_t));
788 for (ix = 0; ix != num_blocks; ix++)
789 fn->blocks[ix].flags = gcov_read_unsigned ();
792 else if (fn && tag == GCOV_TAG_ARCS)
794 unsigned src = gcov_read_unsigned ();
795 unsigned num_dests = GCOV_TAG_ARCS_NUM (length);
797 if (src >= fn->num_blocks || fn->blocks[src].succ)
802 struct arc_info *arc;
803 unsigned dest = gcov_read_unsigned ();
804 unsigned flags = gcov_read_unsigned ();
806 if (dest >= fn->num_blocks)
808 arc = xcalloc (1, sizeof (arc_t));
810 arc->dst = &fn->blocks[dest];
811 arc->src = &fn->blocks[src];
814 arc->count_valid = 0;
815 arc->on_tree = !!(flags & GCOV_ARC_ON_TREE);
816 arc->fake = !!(flags & GCOV_ARC_FAKE);
817 arc->fall_through = !!(flags & GCOV_ARC_FALLTHROUGH);
819 arc->succ_next = fn->blocks[src].succ;
820 fn->blocks[src].succ = arc;
821 fn->blocks[src].num_succ++;
823 arc->pred_next = fn->blocks[dest].pred;
824 fn->blocks[dest].pred = arc;
825 fn->blocks[dest].num_pred++;
831 /* Exceptional exit from this function, the
832 source block must be a call. */
833 fn->blocks[src].is_call_site = 1;
834 arc->is_call_non_return = 1;
838 /* Non-local return from a callee of this
839 function. The destination block is a catch or
841 arc->is_nonlocal_return = 1;
842 fn->blocks[dest].is_nonlocal_return = 1;
850 else if (fn && tag == GCOV_TAG_LINES)
852 unsigned blockno = gcov_read_unsigned ();
853 unsigned *line_nos = xcalloc (length - 1, sizeof (unsigned));
855 if (blockno >= fn->num_blocks || fn->blocks[blockno].u.line.encoding)
860 unsigned lineno = gcov_read_unsigned ();
867 line_nos[ix++] = src->index;
869 line_nos[ix++] = lineno;
870 if (lineno >= src->num_lines)
871 src->num_lines = lineno + 1;
875 const char *file_name = gcov_read_string ();
879 src = find_source (file_name);
882 line_nos[ix++] = src->index;
886 fn->blocks[blockno].u.line.encoding = line_nos;
887 fn->blocks[blockno].u.line.num = ix;
889 else if (current_tag && !GCOV_TAG_IS_SUBTAG (current_tag, tag))
894 gcov_sync (base, length);
895 if (gcov_is_error ())
901 fnotice (stderr, "%s:corrupted\n", bbg_file_name);
907 /* We built everything backwards, so nreverse them all */
909 /* Reverse sources. Not strictly necessary, but we'll then process
910 them in the 'expected' order. */
912 source_t *src, *src_p, *src_n;
914 for (src_p = NULL, src = sources; src; src_p = src, src = src_n)
922 /* Reverse functions. */
924 function_t *fn, *fn_p, *fn_n;
926 for (fn_p = NULL, fn = functions; fn; fn_p = fn, fn = fn_n)
933 /* Reverse the arcs. */
934 for (ix = fn->num_blocks; ix--;)
936 arc_t *arc, *arc_p, *arc_n;
938 for (arc_p = NULL, arc = fn->blocks[ix].succ; arc;
939 arc_p = arc, arc = arc_n)
941 arc_n = arc->succ_next;
942 arc->succ_next = arc_p;
944 fn->blocks[ix].succ = arc_p;
946 for (arc_p = NULL, arc = fn->blocks[ix].pred; arc;
947 arc_p = arc, arc = arc_n)
949 arc_n = arc->pred_next;
950 arc->pred_next = arc_p;
952 fn->blocks[ix].pred = arc_p;
960 /* Reads profiles from the count file and attach to each
961 function. Return nonzero if fatal error. */
964 read_count_file (void)
969 function_t *fn = NULL;
972 if (!gcov_open (da_file_name, 1))
974 fnotice (stderr, "%s:cannot open data file\n", da_file_name);
977 if (!gcov_magic (gcov_read_unsigned (), GCOV_DATA_MAGIC))
979 fnotice (stderr, "%s:not a gcov data file\n", da_file_name);
984 version = gcov_read_unsigned ();
985 if (version != GCOV_VERSION)
989 GCOV_UNSIGNED2STRING (v, version);
990 GCOV_UNSIGNED2STRING (e, GCOV_VERSION);
992 fnotice (stderr, "%s:version `%.4s', prefer version `%.4s'\n",
995 tag = gcov_read_unsigned ();
996 if (tag != bbg_stamp)
998 fnotice (stderr, "%s:stamp mismatch with graph file\n", da_file_name);
1002 while ((tag = gcov_read_unsigned ()))
1004 unsigned length = gcov_read_unsigned ();
1005 unsigned long base = gcov_position ();
1007 if (tag == GCOV_TAG_OBJECT_SUMMARY)
1008 gcov_read_summary (&object_summary);
1009 else if (tag == GCOV_TAG_PROGRAM_SUMMARY)
1011 else if (tag == GCOV_TAG_FUNCTION)
1013 unsigned ident = gcov_read_unsigned ();
1014 struct function_info *fn_n = functions;
1016 for (fn = fn ? fn->next : NULL; ; fn = fn->next)
1020 else if ((fn = fn_n))
1024 fnotice (stderr, "%s:unknown function `%u'\n",
1025 da_file_name, ident);
1028 if (fn->ident == ident)
1034 else if (gcov_read_unsigned () != fn->checksum)
1037 fnotice (stderr, "%s:profile mismatch for `%s'\n",
1038 da_file_name, fn->name);
1042 else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn)
1044 if (length != GCOV_TAG_COUNTER_LENGTH (fn->num_counts))
1048 fn->counts = xcalloc (fn->num_counts, sizeof (gcov_type));
1050 for (ix = 0; ix != fn->num_counts; ix++)
1051 fn->counts[ix] += gcov_read_counter ();
1053 gcov_sync (base, length);
1054 if ((error = gcov_is_error ()))
1058 if (!gcov_is_eof ())
1060 fnotice (stderr, error < 0 ? "%s:overflowed\n" : "%s:corrupted\n",
1069 /* Solve the flow graph. Propagate counts from the instrumented arcs
1070 to the blocks and the uninstrumented arcs. */
1073 solve_flow_graph (function_t *fn)
1077 gcov_type *count_ptr = fn->counts;
1079 block_t *valid_blocks = NULL; /* valid, but unpropagated blocks. */
1080 block_t *invalid_blocks = NULL; /* invalid, but inferable blocks. */
1082 if (fn->num_blocks < 2)
1083 fnotice (stderr, "%s:`%s' lacks entry and/or exit blocks\n",
1084 bbg_file_name, fn->name);
1087 if (fn->blocks[0].num_pred)
1088 fnotice (stderr, "%s:`%s' has arcs to entry block\n",
1089 bbg_file_name, fn->name);
1091 /* We can't deduce the entry block counts from the lack of
1093 fn->blocks[0].num_pred = ~(unsigned)0;
1095 if (fn->blocks[fn->num_blocks - 1].num_succ)
1096 fnotice (stderr, "%s:`%s' has arcs from exit block\n",
1097 bbg_file_name, fn->name);
1099 /* Likewise, we can't deduce exit block counts from the lack
1100 of its successors. */
1101 fn->blocks[fn->num_blocks - 1].num_succ = ~(unsigned)0;
1104 /* Propagate the measured counts, this must be done in the same
1105 order as the code in profile.c */
1106 for (ix = 0, blk = fn->blocks; ix != fn->num_blocks; ix++, blk++)
1108 block_t const *prev_dst = NULL;
1109 int out_of_order = 0;
1110 int non_fake_succ = 0;
1112 for (arc = blk->succ; arc; arc = arc->succ_next)
1120 arc->count = *count_ptr++;
1121 arc->count_valid = 1;
1123 arc->dst->num_pred--;
1125 if (prev_dst && prev_dst > arc->dst)
1127 prev_dst = arc->dst;
1129 if (non_fake_succ == 1)
1131 /* If there is only one non-fake exit, it is an
1132 unconditional branch. */
1133 for (arc = blk->succ; arc; arc = arc->succ_next)
1136 arc->is_unconditional = 1;
1137 /* If this block is instrumenting a call, it might be
1138 an artificial block. It is not artificial if it has
1139 a non-fallthrough exit, or the destination of this
1140 arc has more than one entry. Mark the destination
1141 block as a return site, if none of those conditions
1143 if (blk->is_call_site && arc->fall_through
1144 && arc->dst->pred == arc && !arc->pred_next)
1145 arc->dst->is_call_return = 1;
1149 /* Sort the successor arcs into ascending dst order. profile.c
1150 normally produces arcs in the right order, but sometimes with
1151 one or two out of order. We're not using a particularly
1155 arc_t *start = blk->succ;
1156 unsigned changes = 1;
1160 arc_t *arc, *arc_p, *arc_n;
1163 for (arc_p = NULL, arc = start; (arc_n = arc->succ_next);)
1165 if (arc->dst > arc_n->dst)
1169 arc_p->succ_next = arc_n;
1172 arc->succ_next = arc_n->succ_next;
1173 arc_n->succ_next = arc;
1186 /* Place it on the invalid chain, it will be ignored if that's
1188 blk->invalid_chain = 1;
1189 blk->chain = invalid_blocks;
1190 invalid_blocks = blk;
1193 while (invalid_blocks || valid_blocks)
1195 while ((blk = invalid_blocks))
1197 gcov_type total = 0;
1200 invalid_blocks = blk->chain;
1201 blk->invalid_chain = 0;
1203 for (arc = blk->succ; arc; arc = arc->succ_next)
1204 total += arc->count;
1205 else if (!blk->num_pred)
1206 for (arc = blk->pred; arc; arc = arc->pred_next)
1207 total += arc->count;
1212 blk->count_valid = 1;
1213 blk->chain = valid_blocks;
1214 blk->valid_chain = 1;
1217 while ((blk = valid_blocks))
1220 arc_t *arc, *inv_arc;
1222 valid_blocks = blk->chain;
1223 blk->valid_chain = 0;
1224 if (blk->num_succ == 1)
1230 for (arc = blk->succ; arc; arc = arc->succ_next)
1232 total -= arc->count;
1233 if (!arc->count_valid)
1237 inv_arc->count_valid = 1;
1238 inv_arc->count = total;
1241 if (dst->count_valid)
1243 if (dst->num_pred == 1 && !dst->valid_chain)
1245 dst->chain = valid_blocks;
1246 dst->valid_chain = 1;
1252 if (!dst->num_pred && !dst->invalid_chain)
1254 dst->chain = invalid_blocks;
1255 dst->invalid_chain = 1;
1256 invalid_blocks = dst;
1260 if (blk->num_pred == 1)
1266 for (arc = blk->pred; arc; arc = arc->pred_next)
1268 total -= arc->count;
1269 if (!arc->count_valid)
1273 inv_arc->count_valid = 1;
1274 inv_arc->count = total;
1277 if (src->count_valid)
1279 if (src->num_succ == 1 && !src->valid_chain)
1281 src->chain = valid_blocks;
1282 src->valid_chain = 1;
1288 if (!src->num_succ && !src->invalid_chain)
1290 src->chain = invalid_blocks;
1291 src->invalid_chain = 1;
1292 invalid_blocks = src;
1299 /* If the graph has been correctly solved, every block will have a
1301 for (ix = 0; ix < fn->num_blocks; ix++)
1302 if (!fn->blocks[ix].count_valid)
1304 fnotice (stderr, "%s:graph is unsolvable for `%s'\n",
1305 bbg_file_name, fn->name);
1312 /* Increment totals in COVERAGE according to arc ARC. */
1315 add_branch_counts (coverage_t *coverage, const arc_t *arc)
1317 if (arc->is_call_non_return)
1320 if (arc->src->count)
1321 coverage->calls_executed++;
1323 else if (!arc->is_unconditional)
1325 coverage->branches++;
1326 if (arc->src->count)
1327 coverage->branches_executed++;
1329 coverage->branches_taken++;
1333 /* Format a HOST_WIDE_INT as either a percent ratio, or absolute
1334 count. If dp >= 0, format TOP/BOTTOM * 100 to DP decimal places.
1335 If DP is zero, no decimal point is printed. Only print 100% when
1336 TOP==BOTTOM and only print 0% when TOP=0. If dp < 0, then simply
1337 format TOP. Return pointer to a static string. */
1340 format_gcov (gcov_type top, gcov_type bottom, int dp)
1342 static char buffer[20];
1346 float ratio = bottom ? (float)top / bottom : 0;
1348 unsigned limit = 100;
1351 for (ix = dp; ix--; )
1354 percent = (unsigned) (ratio * limit + (float)0.5);
1355 if (percent <= 0 && top)
1357 else if (percent >= limit && top != bottom)
1358 percent = limit - 1;
1359 ix = sprintf (buffer, "%.*u%%", dp + 1, percent);
1365 buffer[ix+1] = buffer[ix];
1369 buffer[ix + 1] = '.';
1373 sprintf (buffer, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT)top);
1379 /* Output summary info for a function. */
1382 function_summary (const coverage_t *coverage, const char *title)
1384 fnotice (stdout, "%s `%s'\n", title, coverage->name);
1386 if (coverage->lines)
1387 fnotice (stdout, "Lines executed:%s of %d\n",
1388 format_gcov (coverage->lines_executed, coverage->lines, 2),
1391 fnotice (stdout, "No executable lines");
1395 if (coverage->branches)
1397 fnotice (stdout, "Branches executed:%s of %d\n",
1398 format_gcov (coverage->branches_executed,
1399 coverage->branches, 2),
1400 coverage->branches);
1401 fnotice (stdout, "Taken at least once:%s of %d\n",
1402 format_gcov (coverage->branches_taken,
1403 coverage->branches, 2),
1404 coverage->branches);
1407 fnotice (stdout, "No branches\n");
1408 if (coverage->calls)
1409 fnotice (stdout, "Calls executed:%s of %d\n",
1410 format_gcov (coverage->calls_executed, coverage->calls, 2),
1413 fnotice (stdout, "No calls\n");
1417 /* Generate an output file name. LONG_OUTPUT_NAMES and PRESERVE_PATHS
1418 affect name generation. With preserve_paths we create a filename
1419 from all path components of the source file, replacing '/' with
1420 '#', without it we simply take the basename component. With
1421 long_output_names we prepend the processed name of the input file
1422 to each output name (except when the current source file is the
1423 input file, so you don't get a double concatenation). The two
1424 components are separated by '##'. Also '.' filename components are
1425 removed and '..' components are renamed to '^'. */
1428 make_gcov_file_name (const char *input_name, const char *src_name)
1431 char *name = xmalloc (strlen (src_name) + strlen (input_name) + 10);
1434 if (flag_long_names && strcmp (src_name, input_name))
1436 /* Generate the input filename part. */
1437 cptr = flag_preserve_paths ? NULL : strrchr (input_name, '/');
1438 strcat (name, cptr ? cptr + 1 : input_name);
1439 strcat (name, "##");
1442 /* Generate the source filename part. */
1443 cptr = flag_preserve_paths ? NULL : strrchr (src_name, '/');
1444 strcat (name, cptr ? cptr + 1 : src_name);
1446 if (flag_preserve_paths)
1448 /* Convert '/' to '#', remove '/./', convert '/../' to '/^/' */
1451 for (cptr = name; (cptr = strchr ((prev = cptr), '/'));)
1455 if (prev + 1 == cptr && prev[0] == '.')
1460 else if (prev + 2 == cptr && prev[0] == '.' && prev[1] == '.')
1472 prev[0] = prev[shift];
1478 strcat (name, ".gcov");
1482 /* Scan through the bb_data for each line in the block, increment
1483 the line number execution count indicated by the execution count of
1484 the appropriate basic block. */
1487 add_line_counts (coverage_t *coverage, function_t *fn)
1490 line_t *line = NULL; /* This is propagated from one iteration to the
1493 /* Scan each basic block. */
1494 for (ix = 0; ix != fn->num_blocks; ix++)
1496 block_t *block = &fn->blocks[ix];
1498 const source_t *src = NULL;
1501 if (block->count && ix && ix + 1 != fn->num_blocks)
1502 fn->blocks_executed++;
1503 for (jx = 0, encoding = block->u.line.encoding;
1504 jx != block->u.line.num; jx++, encoding++)
1507 unsigned src_n = *++encoding;
1509 for (src = sources; src->index != src_n; src = src->next)
1515 line = &src->lines[*encoding];
1521 if (!line->count && block->count)
1522 coverage->lines_executed++;
1525 line->count += block->count;
1527 free (block->u.line.encoding);
1528 block->u.cycle.arc = NULL;
1529 block->u.cycle.ident = ~0U;
1531 if (!ix || ix + 1 == fn->num_blocks)
1532 /* Entry or exit block */;
1533 else if (flag_all_blocks)
1535 line_t *block_line = line ? line : &fn->src->lines[fn->line];
1537 block->chain = block_line->u.blocks;
1538 block_line->u.blocks = block;
1540 else if (flag_branches)
1544 for (arc = block->succ; arc; arc = arc->succ_next)
1546 arc->line_next = line->u.branches;
1547 line->u.branches = arc;
1548 if (coverage && !arc->is_unconditional)
1549 add_branch_counts (coverage, arc);
1554 fnotice (stderr, "%s:no lines for `%s'\n", bbg_file_name, fn->name);
1557 /* Accumulate the line counts of a file. */
1560 accumulate_line_counts (source_t *src)
1563 function_t *fn, *fn_p, *fn_n;
1566 /* Reverse the function order. */
1567 for (fn = src->functions, fn_p = NULL; fn;
1568 fn_p = fn, fn = fn_n)
1570 fn_n = fn->line_next;
1571 fn->line_next = fn_p;
1573 src->functions = fn_p;
1575 for (ix = src->num_lines, line = src->lines; ix--; line++)
1577 if (!flag_all_blocks)
1579 arc_t *arc, *arc_p, *arc_n;
1581 /* Total and reverse the branch information. */
1582 for (arc = line->u.branches, arc_p = NULL; arc;
1583 arc_p = arc, arc = arc_n)
1585 arc_n = arc->line_next;
1586 arc->line_next = arc_p;
1588 add_branch_counts (&src->coverage, arc);
1590 line->u.branches = arc_p;
1592 else if (line->u.blocks)
1594 /* The user expects the line count to be the number of times
1595 a line has been executed. Simply summing the block count
1596 will give an artificially high number. The Right Thing
1597 is to sum the entry counts to the graph of blocks on this
1598 line, then find the elementary cycles of the local graph
1599 and add the transition counts of those cycles. */
1600 block_t *block, *block_p, *block_n;
1601 gcov_type count = 0;
1603 /* Reverse the block information. */
1604 for (block = line->u.blocks, block_p = NULL; block;
1605 block_p = block, block = block_n)
1607 block_n = block->chain;
1608 block->chain = block_p;
1609 block->u.cycle.ident = ix;
1611 line->u.blocks = block_p;
1613 /* Sum the entry arcs. */
1614 for (block = line->u.blocks; block; block = block->chain)
1618 for (arc = block->pred; arc; arc = arc->pred_next)
1620 if (arc->src->u.cycle.ident != ix)
1621 count += arc->count;
1623 add_branch_counts (&src->coverage, arc);
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.
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.
1639 For each loop we find, locate the arc with the smallest
1640 transition count, and add that to the cumulative
1641 count. Remove the arc from consideration. */
1642 for (block = line->u.blocks; block; block = block->chain)
1644 block_t *head = block;
1652 block_t *dst = arc->dst;
1653 if (/* Already used that arc. */
1655 /* Not to same graph, or before first vertex. */
1656 || dst->u.cycle.ident != ix
1657 /* Already in path. */
1658 || dst->u.cycle.arc)
1660 arc = arc->succ_next;
1666 /* Found a closing arc. */
1667 gcov_type cycle_count = arc->count;
1668 arc_t *cycle_arc = arc;
1671 /* Locate the smallest arc count of the loop. */
1672 for (dst = head; (probe_arc = dst->u.cycle.arc);
1673 dst = probe_arc->src)
1674 if (cycle_count > probe_arc->count)
1676 cycle_count = probe_arc->count;
1677 cycle_arc = probe_arc;
1680 count += cycle_count;
1681 cycle_arc->cycle = 1;
1682 /* Unwind to the cyclic arc. */
1683 while (head != cycle_arc->src)
1685 arc = head->u.cycle.arc;
1689 arc = arc->succ_next;
1693 /* Add new block to chain. */
1694 dst->u.cycle.arc = arc;
1698 /* We could not add another vertex to the path. Remove
1699 the last vertex from the list. */
1700 arc = head->u.cycle.arc;
1703 /* It was not the first vertex. Move onto next arc. */
1704 head->u.cycle.arc = NULL;
1706 arc = arc->succ_next;
1707 goto current_vertex;
1709 /* Mark this block as unusable. */
1710 block->u.cycle.ident = ~0U;
1713 line->count = count;
1718 src->coverage.lines++;
1720 src->coverage.lines_executed++;
1725 /* Ouput information about ARC number IX. Returns nonzero if
1726 anything is output. */
1729 output_branch_count (FILE *gcov_file, int ix, const arc_t *arc)
1732 if (arc->is_call_non_return)
1734 if (arc->src->count)
1736 fnotice (gcov_file, "call %2d returned %s\n", ix,
1737 format_gcov (arc->src->count - arc->count,
1738 arc->src->count, -flag_counts));
1741 fnotice (gcov_file, "call %2d never executed\n", ix);
1743 else if (!arc->is_unconditional)
1745 if (arc->src->count)
1746 fnotice (gcov_file, "branch %2d taken %s%s\n", ix,
1747 format_gcov (arc->count, arc->src->count, -flag_counts),
1748 arc->fall_through ? " (fallthrough)" : "");
1750 fnotice (gcov_file, "branch %2d never executed\n", ix);
1752 else if (flag_unconditional && !arc->dst->is_call_return)
1754 if (arc->src->count)
1755 fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
1756 format_gcov (arc->count, arc->src->count, -flag_counts));
1758 fnotice (gcov_file, "unconditional %2d never executed\n", ix);
1766 /* Read in the source file one line at a time, and output that line to
1767 the gcov file preceded by its execution count and other
1771 output_lines (FILE *gcov_file, const source_t *src)
1774 unsigned line_num; /* current line number. */
1775 const line_t *line; /* current line info ptr. */
1776 char string[STRING_SIZE]; /* line buffer. */
1777 char const *retval = ""; /* status of source file reading. */
1778 function_t *fn = src->functions;
1780 fprintf (gcov_file, "%9s:%5d:Source:%s\n", "-", 0, src->name);
1781 fprintf (gcov_file, "%9s:%5d:Graph:%s\n", "-", 0, bbg_file_name);
1782 fprintf (gcov_file, "%9s:%5d:Data:%s\n", "-", 0, da_file_name);
1783 fprintf (gcov_file, "%9s:%5d:Runs:%u\n", "-", 0,
1784 object_summary.ctrs[GCOV_COUNTER_ARCS].runs);
1785 fprintf (gcov_file, "%9s:%5d:Programs:%u\n", "-", 0, program_count);
1787 source_file = fopen (src->name, "r");
1790 fnotice (stderr, "%s:cannot open source file\n", src->name);
1797 if (!fstat (fileno (source_file), &status)
1798 && status.st_mtime > bbg_file_time)
1800 fnotice (stderr, "%s:source file is newer than graph file `%s'\n",
1801 src->name, bbg_file_name);
1802 fprintf (gcov_file, "%9s:%5d:Source is newer than graph\n",
1807 for (line_num = 1, line = &src->lines[line_num];
1808 line_num < src->num_lines; line_num++, line++)
1810 for (; fn && fn->line == line_num; fn = fn->line_next)
1812 arc_t *arc = fn->blocks[fn->num_blocks - 1].pred;
1813 gcov_type return_count = fn->blocks[fn->num_blocks - 1].count;
1815 for (; arc; arc = arc->pred_next)
1817 return_count -= arc->count;
1819 fprintf (gcov_file, "function %s", fn->name);
1820 fprintf (gcov_file, " called %s",
1821 format_gcov (fn->blocks[0].count, 0, -1));
1822 fprintf (gcov_file, " returned %s",
1823 format_gcov (return_count, fn->blocks[0].count, 0));
1824 fprintf (gcov_file, " blocks executed %s",
1825 format_gcov (fn->blocks_executed, fn->num_blocks - 2, 0));
1826 fprintf (gcov_file, "\n");
1829 /* For lines which don't exist in the .bb file, print '-' before
1830 the source line. For lines which exist but were never
1831 executed, print '#####' before the source line. Otherwise,
1832 print the execution count before the source line. There are
1833 16 spaces of indentation added before the source line so that
1834 tabs won't be messed up. */
1835 fprintf (gcov_file, "%9s:%5u:",
1836 !line->exists ? "-" : !line->count ? "#####"
1837 : format_gcov (line->count, 0, -1), line_num);
1841 /* Copy source line. */
1844 retval = fgets (string, STRING_SIZE, source_file);
1847 fputs (retval, gcov_file);
1849 while (!retval[0] || retval[strlen (retval) - 1] != '\n');
1852 fputs ("/*EOF*/\n", gcov_file);
1854 if (flag_all_blocks)
1860 for (ix = jx = 0, block = line->u.blocks; block;
1861 block = block->chain)
1863 if (!block->is_call_return)
1864 fprintf (gcov_file, "%9s:%5u-block %2d\n",
1865 !line->exists ? "-" : !block->count ? "$$$$$"
1866 : format_gcov (block->count, 0, -1),
1869 for (arc = block->succ; arc; arc = arc->succ_next)
1870 jx += output_branch_count (gcov_file, jx, arc);
1873 else if (flag_branches)
1878 for (ix = 0, arc = line->u.branches; arc; arc = arc->line_next)
1879 ix += output_branch_count (gcov_file, ix, arc);
1883 /* Handle all remaining source lines. There may be lines after the
1884 last line of code. */
1887 for (; (retval = fgets (string, STRING_SIZE, source_file)); line_num++)
1889 fprintf (gcov_file, "%9s:%5u:%s", "-", line_num, retval);
1891 while (!retval[0] || retval[strlen (retval) - 1] != '\n')
1893 retval = fgets (string, STRING_SIZE, source_file);
1896 fputs (retval, gcov_file);
1902 fclose (source_file);