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, 2004 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. */
85 /* used in cycle search, so that we do not clobber original counts. */
88 unsigned int count_valid : 1;
89 unsigned int on_tree : 1;
90 unsigned int fake : 1;
91 unsigned int fall_through : 1;
93 /* Arc is for a function that abnormally returns. */
94 unsigned int is_call_non_return : 1;
96 /* Arc is for catch/setjump. */
97 unsigned int is_nonlocal_return : 1;
99 /* Is an unconditional branch. */
100 unsigned int is_unconditional : 1;
102 /* Loop making arc. */
103 unsigned int cycle : 1;
105 /* Next branch on line. */
106 struct arc_info *line_next;
108 /* Links to next arc on src and dst lists. */
109 struct arc_info *succ_next;
110 struct arc_info *pred_next;
113 /* Describes a basic block. Contains lists of arcs to successor and
114 predecessor blocks. */
116 typedef struct block_info
118 /* Chain of exit and entry arcs. */
122 /* Number of unprocessed exit and entry arcs. */
126 /* Block execution count. */
129 unsigned count_valid : 1;
130 unsigned valid_chain : 1;
131 unsigned invalid_chain : 1;
133 /* Block is a call instrumenting site. */
134 unsigned is_call_site : 1; /* Does the call. */
135 unsigned is_call_return : 1; /* Is the return. */
137 /* Block is a landing pad for longjmp or throw. */
138 unsigned is_nonlocal_return : 1;
144 /* Array of line numbers and source files. source files are
145 introduced by a linenumber of zero, the next 'line number' is
146 the number of the source file. Always starts with a source
150 } line; /* Valid until blocks are linked onto lines */
153 /* Single line graph cycle workspace. Used for all-blocks
157 } cycle; /* Used in all-blocks mode, after blocks are linked onto
161 /* Temporary chain for solving graph, and for chaining blocks on one
163 struct block_info *chain;
167 /* Describes a single function. Contains an array of basic blocks. */
169 typedef struct function_info
171 /* Name of function. */
176 /* Array of basic blocks. */
179 unsigned blocks_executed;
181 /* Raw arc coverage counts. */
185 /* First line number. */
187 struct source_info *src;
189 /* Next function in same source file. */
190 struct function_info *line_next;
193 struct function_info *next;
196 /* Describes coverage of a file or function. */
198 typedef struct coverage_info
204 int branches_executed;
213 /* Describes a single line of source. Contains a chain of basic blocks
216 typedef struct line_info
218 gcov_type count; /* execution count */
221 arc_t *branches; /* branches from blocks that end on this
222 line. Used for branch-counts when not
224 block_t *blocks; /* blocks which start on this line. Used
225 in all-blocks mode. */
230 /* Describes a file mentioned in the block graph. Contains an array
233 typedef struct source_info
235 /* Name of source file. */
239 /* Array of line information. */
245 /* Functions in this source file. These are in ascending line
247 function_t *functions;
249 /* Next source file. */
250 struct source_info *next;
253 /* Holds a list of function basic block graphs. */
255 static function_t *functions;
257 /* This points to the head of the sourcefile structure list. */
259 static source_t *sources;
261 /* This holds data summary information. */
263 static struct gcov_summary object_summary;
264 static unsigned program_count;
266 /* Modification time of graph file. */
268 static time_t bbg_file_time;
270 /* Name and file pointer of the input file for the basic block graph. */
272 static char *bbg_file_name;
274 /* Stamp of the bbg file */
275 static unsigned bbg_stamp;
277 /* Name and file pointer of the input file for the arc count data. */
279 static char *da_file_name;
281 /* Output branch probabilities. */
283 static int flag_branches = 0;
285 /* Show unconditional branches too. */
286 static int flag_unconditional = 0;
288 /* Output a gcov file if this is true. This is on by default, and can
289 be turned off by the -n option. */
291 static int flag_gcov_file = 1;
293 /* For included files, make the gcov output file name include the name
294 of the input source file. For example, if x.h is included in a.c,
295 then the output file name is a.c##x.h.gcov instead of x.h.gcov. */
297 static int flag_long_names = 0;
299 /* Output count information for every basic block, not merely those
300 that contain line number information. */
302 static int flag_all_blocks = 0;
304 /* Output summary info for each function. */
306 static int flag_function_summary = 0;
308 /* Object directory file prefix. This is the directory/file where the
309 graph and data files are looked for, if nonzero. */
311 static char *object_directory = 0;
313 /* Preserve all pathname components. Needed when object files and
314 source files are in subdirectories. '/' is mangled as '#', '.' is
315 elided and '..' mangled to '^'. */
317 static int flag_preserve_paths = 0;
319 /* Output the number of times a branch was taken as opposed to the percentage
320 of times it was taken. */
322 static int flag_counts = 0;
324 /* Forward declarations. */
325 static void fnotice (FILE *, const char *, ...) ATTRIBUTE_PRINTF_2;
326 static int process_args (int, char **);
327 static void print_usage (int) ATTRIBUTE_NORETURN;
328 static void print_version (void) ATTRIBUTE_NORETURN;
329 static void process_file (const char *);
330 static void create_file_names (const char *);
331 static source_t *find_source (const char *);
332 static int read_graph_file (void);
333 static int read_count_file (void);
334 static void solve_flow_graph (function_t *);
335 static void add_branch_counts (coverage_t *, const arc_t *);
336 static void add_line_counts (coverage_t *, function_t *);
337 static void function_summary (const coverage_t *, const char *);
338 static const char *format_gcov (gcov_type, gcov_type, int);
339 static void accumulate_line_counts (source_t *);
340 static int output_branch_count (FILE *, int, const arc_t *);
341 static void output_lines (FILE *, const source_t *);
342 static char *make_gcov_file_name (const char *, const char *);
343 static void release_structures (void);
344 extern int main (int, char **);
347 main (int argc, char **argv)
353 argno = process_args (argc, argv);
357 for (; argno != argc; argno++)
359 release_structures ();
361 process_file (argv[argno]);
368 fnotice (FILE *file, const char *msgid, ...)
372 va_start (ap, msgid);
373 vfprintf (file, _(msgid), ap);
377 /* More 'friendly' abort that prints the line and file.
378 config.h can #define abort fancy_abort if you like that sort of thing. */
379 extern void fancy_abort (void) ATTRIBUTE_NORETURN;
384 fnotice (stderr, "Internal gcov abort.\n");
385 exit (FATAL_EXIT_CODE);
388 /* Print a usage message and exit. If ERROR_P is nonzero, this is an error,
389 otherwise the output of --help. */
392 print_usage (int error_p)
394 FILE *file = error_p ? stderr : stdout;
395 int status = error_p ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE;
397 fnotice (file, "Usage: gcov [OPTION]... SOURCEFILE\n\n");
398 fnotice (file, "Print code coverage information.\n\n");
399 fnotice (file, " -h, --help Print this help, then exit\n");
400 fnotice (file, " -v, --version Print version number, then exit\n");
401 fnotice (file, " -a, --all-blocks Show information for every basic block\n");
402 fnotice (file, " -b, --branch-probabilities Include branch probabilities in output\n");
403 fnotice (file, " -c, --branch-counts Given counts of branches taken\n\
404 rather than percentages\n");
405 fnotice (file, " -n, --no-output Do not create an output file\n");
406 fnotice (file, " -l, --long-file-names Use long output file names for included\n\
408 fnotice (file, " -f, --function-summaries Output summaries for each function\n");
409 fnotice (file, " -o, --object-directory DIR|FILE Search for object files in DIR or called FILE\n");
410 fnotice (file, " -p, --preserve-paths Preserve all pathname components\n");
411 fnotice (file, " -u, --unconditional-branches Show unconditional branch counts too\n");
412 fnotice (file, "\nFor bug reporting instructions, please see:\n%s.\n",
417 /* Print version information and exit. */
422 fnotice (stdout, "gcov (GCC) %s\n", version_string);
423 fprintf (stdout, "Copyright %s 2004 Free Software Foundation, Inc.\n",
426 _("This is free software; see the source for copying conditions.\n"
427 "There is NO warranty; not even for MERCHANTABILITY or \n"
428 "FITNESS FOR A PARTICULAR PURPOSE.\n\n"));
429 exit (SUCCESS_EXIT_CODE);
432 static const struct option options[] =
434 { "help", no_argument, NULL, 'h' },
435 { "version", no_argument, NULL, 'v' },
436 { "all-blocks", no_argument, NULL, 'a' },
437 { "branch-probabilities", no_argument, NULL, 'b' },
438 { "branch-counts", no_argument, NULL, 'c' },
439 { "no-output", no_argument, NULL, 'n' },
440 { "long-file-names", no_argument, NULL, 'l' },
441 { "function-summaries", no_argument, NULL, 'f' },
442 { "preserve-paths", no_argument, NULL, 'p' },
443 { "object-directory", required_argument, NULL, 'o' },
444 { "object-file", required_argument, NULL, 'o' },
445 { "unconditional-branches", no_argument, NULL, 'u' },
449 /* Process args, return index to first non-arg. */
452 process_args (int argc, char **argv)
456 while ((opt = getopt_long (argc, argv, "abcfhlno:puv", options, NULL)) != -1)
470 flag_function_summary = 1;
474 /* print_usage will exit. */
482 object_directory = optarg;
485 flag_preserve_paths = 1;
488 flag_unconditional = 1;
492 /* print_version will exit. */
495 /* print_usage will exit. */
502 /* Process a single source file. */
505 process_file (const char *file_name)
510 create_file_names (file_name);
511 if (read_graph_file ())
516 fnotice (stderr, "%s:no functions found\n", bbg_file_name);
520 if (read_count_file ())
523 for (fn = functions; fn; fn = fn->next)
524 solve_flow_graph (fn);
525 for (src = sources; src; src = src->next)
526 src->lines = xcalloc (src->num_lines, sizeof (line_t));
527 for (fn = functions; fn; fn = fn->next)
531 memset (&coverage, 0, sizeof (coverage));
532 coverage.name = fn->name;
533 add_line_counts (flag_function_summary ? &coverage : NULL, fn);
534 if (flag_function_summary)
536 function_summary (&coverage, "Function");
537 fnotice (stdout, "\n");
541 for (src = sources; src; src = src->next)
543 accumulate_line_counts (src);
544 function_summary (&src->coverage, "File");
547 char *gcov_file_name = make_gcov_file_name (file_name, src->name);
548 FILE *gcov_file = fopen (gcov_file_name, "w");
552 fnotice (stdout, "%s:creating `%s'\n",
553 src->name, gcov_file_name);
554 output_lines (gcov_file, src);
555 if (ferror (gcov_file))
556 fnotice (stderr, "%s:error writing output file `%s'\n",
557 src->name, gcov_file_name);
561 fnotice (stderr, "%s:could not open output file `%s'\n",
562 src->name, gcov_file_name);
563 free (gcov_file_name);
565 fnotice (stdout, "\n");
569 /* Release all memory used. */
572 release_structures (void)
577 free (bbg_file_name);
579 da_file_name = bbg_file_name = NULL;
583 while ((src = sources))
591 while ((fn = functions))
596 functions = fn->next;
597 for (ix = fn->num_blocks, block = fn->blocks; ix--; block++)
601 for (arc = block->succ; arc; arc = arc_n)
603 arc_n = arc->succ_next;
612 /* Generate the names of the graph and data files. If OBJECT_DIRECTORY
613 is not specified, these are looked for in the current directory,
614 and named from the basename of the FILE_NAME sans extension. If
615 OBJECT_DIRECTORY is specified and is a directory, the files are in
616 that directory, but named from the basename of the FILE_NAME, sans
617 extension. Otherwise OBJECT_DIRECTORY is taken to be the name of
618 the object *file*, and the data files are named from that. */
621 create_file_names (const char *file_name)
625 int length = strlen (file_name);
628 if (object_directory && object_directory[0])
632 length += strlen (object_directory) + 2;
633 name = xmalloc (length);
636 base = !stat (object_directory, &status) && S_ISDIR (status.st_mode);
637 strcat (name, object_directory);
638 if (base && name[strlen (name) - 1] != '/')
643 name = xmalloc (length + 1);
650 /* Append source file name. */
651 cptr = strrchr (file_name, '/');
652 strcat (name, cptr ? cptr + 1 : file_name);
655 /* Remove the extension. */
656 cptr = strrchr (name, '.');
660 length = strlen (name);
662 bbg_file_name = xmalloc (length + strlen (GCOV_NOTE_SUFFIX) + 1);
663 strcpy (bbg_file_name, name);
664 strcpy (bbg_file_name + length, GCOV_NOTE_SUFFIX);
666 da_file_name = xmalloc (length + strlen (GCOV_DATA_SUFFIX) + 1);
667 strcpy (da_file_name, name);
668 strcpy (da_file_name + length, GCOV_DATA_SUFFIX);
673 /* Find or create a source file structure for FILE_NAME. Copies
674 FILE_NAME on creation */
677 find_source (const char *file_name)
682 file_name = "<unknown>";
684 for (src = sources; src; src = src->next)
685 if (!strcmp (file_name, src->name))
688 src = xcalloc (1, sizeof (source_t));
689 src->name = xstrdup (file_name);
690 src->coverage.name = src->name;
691 src->index = sources ? sources->index + 1 : 1;
698 /* Read the graph file. Return nonzero on fatal error. */
701 read_graph_file (void)
704 unsigned current_tag = 0;
705 struct function_info *fn = NULL;
706 source_t *src = NULL;
710 if (!gcov_open (bbg_file_name, 1))
712 fnotice (stderr, "%s:cannot open graph file\n", bbg_file_name);
715 bbg_file_time = gcov_time ();
716 if (!gcov_magic (gcov_read_unsigned (), GCOV_NOTE_MAGIC))
718 fnotice (stderr, "%s:not a gcov graph file\n", bbg_file_name);
723 version = gcov_read_unsigned ();
724 if (version != GCOV_VERSION)
728 GCOV_UNSIGNED2STRING (v, version);
729 GCOV_UNSIGNED2STRING (e, GCOV_VERSION);
731 fnotice (stderr, "%s:version `%.4s', prefer `%.4s'\n",
732 bbg_file_name, v, e);
734 bbg_stamp = gcov_read_unsigned ();
736 while ((tag = gcov_read_unsigned ()))
738 unsigned length = gcov_read_unsigned ();
739 gcov_position_t base = gcov_position ();
741 if (tag == GCOV_TAG_FUNCTION)
744 unsigned ident, checksum, lineno;
746 function_t *probe, *prev;
748 ident = gcov_read_unsigned ();
749 checksum = gcov_read_unsigned ();
750 function_name = xstrdup (gcov_read_string ());
751 src = find_source (gcov_read_string ());
752 lineno = gcov_read_unsigned ();
754 fn = xcalloc (1, sizeof (function_t));
755 fn->name = function_name;
757 fn->checksum = checksum;
761 fn->next = functions;
765 if (lineno >= src->num_lines)
766 src->num_lines = lineno + 1;
767 /* Now insert it into the source file's list of
768 functions. Normally functions will be encountered in
769 ascending order, so a simple scan is quick. */
770 for (probe = src->functions, prev = NULL;
771 probe && probe->line > lineno;
772 prev = probe, probe = probe->line_next)
774 fn->line_next = probe;
776 prev->line_next = fn;
780 else if (fn && tag == GCOV_TAG_BLOCKS)
783 fnotice (stderr, "%s:already seen blocks for `%s'\n",
784 bbg_file_name, fn->name);
787 unsigned ix, num_blocks = GCOV_TAG_BLOCKS_NUM (length);
788 fn->num_blocks = num_blocks;
790 fn->blocks = xcalloc (fn->num_blocks, sizeof (block_t));
791 for (ix = 0; ix != num_blocks; ix++)
792 fn->blocks[ix].flags = gcov_read_unsigned ();
795 else if (fn && tag == GCOV_TAG_ARCS)
797 unsigned src = gcov_read_unsigned ();
798 unsigned num_dests = GCOV_TAG_ARCS_NUM (length);
800 if (src >= fn->num_blocks || fn->blocks[src].succ)
805 struct arc_info *arc;
806 unsigned dest = gcov_read_unsigned ();
807 unsigned flags = gcov_read_unsigned ();
809 if (dest >= fn->num_blocks)
811 arc = xcalloc (1, sizeof (arc_t));
813 arc->dst = &fn->blocks[dest];
814 arc->src = &fn->blocks[src];
817 arc->count_valid = 0;
818 arc->on_tree = !!(flags & GCOV_ARC_ON_TREE);
819 arc->fake = !!(flags & GCOV_ARC_FAKE);
820 arc->fall_through = !!(flags & GCOV_ARC_FALLTHROUGH);
822 arc->succ_next = fn->blocks[src].succ;
823 fn->blocks[src].succ = arc;
824 fn->blocks[src].num_succ++;
826 arc->pred_next = fn->blocks[dest].pred;
827 fn->blocks[dest].pred = arc;
828 fn->blocks[dest].num_pred++;
834 /* Exceptional exit from this function, the
835 source block must be a call. */
836 fn->blocks[src].is_call_site = 1;
837 arc->is_call_non_return = 1;
841 /* Non-local return from a callee of this
842 function. The destination block is a catch or
844 arc->is_nonlocal_return = 1;
845 fn->blocks[dest].is_nonlocal_return = 1;
853 else if (fn && tag == GCOV_TAG_LINES)
855 unsigned blockno = gcov_read_unsigned ();
856 unsigned *line_nos = xcalloc (length - 1, sizeof (unsigned));
858 if (blockno >= fn->num_blocks || fn->blocks[blockno].u.line.encoding)
863 unsigned lineno = gcov_read_unsigned ();
870 line_nos[ix++] = src->index;
872 line_nos[ix++] = lineno;
873 if (lineno >= src->num_lines)
874 src->num_lines = lineno + 1;
878 const char *file_name = gcov_read_string ();
882 src = find_source (file_name);
885 line_nos[ix++] = src->index;
889 fn->blocks[blockno].u.line.encoding = line_nos;
890 fn->blocks[blockno].u.line.num = ix;
892 else if (current_tag && !GCOV_TAG_IS_SUBTAG (current_tag, tag))
897 gcov_sync (base, length);
898 if (gcov_is_error ())
901 fnotice (stderr, "%s:corrupted\n", bbg_file_name);
908 /* We built everything backwards, so nreverse them all. */
910 /* Reverse sources. Not strictly necessary, but we'll then process
911 them in the 'expected' order. */
913 source_t *src, *src_p, *src_n;
915 for (src_p = NULL, src = sources; src; src_p = src, src = src_n)
923 /* Reverse functions. */
925 function_t *fn, *fn_p, *fn_n;
927 for (fn_p = NULL, fn = functions; fn; fn_p = fn, fn = fn_n)
934 /* Reverse the arcs. */
935 for (ix = fn->num_blocks; ix--;)
937 arc_t *arc, *arc_p, *arc_n;
939 for (arc_p = NULL, arc = fn->blocks[ix].succ; arc;
940 arc_p = arc, arc = arc_n)
942 arc_n = arc->succ_next;
943 arc->succ_next = arc_p;
945 fn->blocks[ix].succ = arc_p;
947 for (arc_p = NULL, arc = fn->blocks[ix].pred; arc;
948 arc_p = arc, arc = arc_n)
950 arc_n = arc->pred_next;
951 arc->pred_next = arc_p;
953 fn->blocks[ix].pred = arc_p;
961 /* Reads profiles from the count file and attach to each
962 function. Return nonzero if fatal error. */
965 read_count_file (void)
970 function_t *fn = NULL;
973 if (!gcov_open (da_file_name, 1))
975 fnotice (stderr, "%s:cannot open data file\n", da_file_name);
978 if (!gcov_magic (gcov_read_unsigned (), GCOV_DATA_MAGIC))
980 fnotice (stderr, "%s:not a gcov data file\n", da_file_name);
985 version = gcov_read_unsigned ();
986 if (version != GCOV_VERSION)
990 GCOV_UNSIGNED2STRING (v, version);
991 GCOV_UNSIGNED2STRING (e, GCOV_VERSION);
993 fnotice (stderr, "%s:version `%.4s', prefer version `%.4s'\n",
996 tag = gcov_read_unsigned ();
997 if (tag != bbg_stamp)
999 fnotice (stderr, "%s:stamp mismatch with graph file\n", da_file_name);
1003 while ((tag = gcov_read_unsigned ()))
1005 unsigned length = gcov_read_unsigned ();
1006 unsigned long base = gcov_position ();
1008 if (tag == GCOV_TAG_OBJECT_SUMMARY)
1009 gcov_read_summary (&object_summary);
1010 else if (tag == GCOV_TAG_PROGRAM_SUMMARY)
1012 else if (tag == GCOV_TAG_FUNCTION)
1014 unsigned ident = gcov_read_unsigned ();
1015 struct function_info *fn_n = functions;
1017 for (fn = fn ? fn->next : NULL; ; fn = fn->next)
1021 else if ((fn = fn_n))
1025 fnotice (stderr, "%s:unknown function `%u'\n",
1026 da_file_name, ident);
1029 if (fn->ident == ident)
1035 else if (gcov_read_unsigned () != fn->checksum)
1038 fnotice (stderr, "%s:profile mismatch for `%s'\n",
1039 da_file_name, fn->name);
1043 else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn)
1045 if (length != GCOV_TAG_COUNTER_LENGTH (fn->num_counts))
1049 fn->counts = xcalloc (fn->num_counts, sizeof (gcov_type));
1051 for (ix = 0; ix != fn->num_counts; ix++)
1052 fn->counts[ix] += gcov_read_counter ();
1054 gcov_sync (base, length);
1055 if ((error = gcov_is_error ()))
1057 fnotice (stderr, error < 0 ? "%s:overflowed\n" : "%s:corrupted\n",
1067 /* Solve the flow graph. Propagate counts from the instrumented arcs
1068 to the blocks and the uninstrumented arcs. */
1071 solve_flow_graph (function_t *fn)
1075 gcov_type *count_ptr = fn->counts;
1077 block_t *valid_blocks = NULL; /* valid, but unpropagated blocks. */
1078 block_t *invalid_blocks = NULL; /* invalid, but inferable blocks. */
1080 if (fn->num_blocks < 2)
1081 fnotice (stderr, "%s:`%s' lacks entry and/or exit blocks\n",
1082 bbg_file_name, fn->name);
1085 if (fn->blocks[0].num_pred)
1086 fnotice (stderr, "%s:`%s' has arcs to entry block\n",
1087 bbg_file_name, fn->name);
1089 /* We can't deduce the entry block counts from the lack of
1091 fn->blocks[0].num_pred = ~(unsigned)0;
1093 if (fn->blocks[fn->num_blocks - 1].num_succ)
1094 fnotice (stderr, "%s:`%s' has arcs from exit block\n",
1095 bbg_file_name, fn->name);
1097 /* Likewise, we can't deduce exit block counts from the lack
1098 of its successors. */
1099 fn->blocks[fn->num_blocks - 1].num_succ = ~(unsigned)0;
1102 /* Propagate the measured counts, this must be done in the same
1103 order as the code in profile.c */
1104 for (ix = 0, blk = fn->blocks; ix != fn->num_blocks; ix++, blk++)
1106 block_t const *prev_dst = NULL;
1107 int out_of_order = 0;
1108 int non_fake_succ = 0;
1110 for (arc = blk->succ; arc; arc = arc->succ_next)
1118 arc->count = *count_ptr++;
1119 arc->count_valid = 1;
1121 arc->dst->num_pred--;
1123 if (prev_dst && prev_dst > arc->dst)
1125 prev_dst = arc->dst;
1127 if (non_fake_succ == 1)
1129 /* If there is only one non-fake exit, it is an
1130 unconditional branch. */
1131 for (arc = blk->succ; arc; arc = arc->succ_next)
1134 arc->is_unconditional = 1;
1135 /* If this block is instrumenting a call, it might be
1136 an artificial block. It is not artificial if it has
1137 a non-fallthrough exit, or the destination of this
1138 arc has more than one entry. Mark the destination
1139 block as a return site, if none of those conditions
1141 if (blk->is_call_site && arc->fall_through
1142 && arc->dst->pred == arc && !arc->pred_next)
1143 arc->dst->is_call_return = 1;
1147 /* Sort the successor arcs into ascending dst order. profile.c
1148 normally produces arcs in the right order, but sometimes with
1149 one or two out of order. We're not using a particularly
1153 arc_t *start = blk->succ;
1154 unsigned changes = 1;
1158 arc_t *arc, *arc_p, *arc_n;
1161 for (arc_p = NULL, arc = start; (arc_n = arc->succ_next);)
1163 if (arc->dst > arc_n->dst)
1167 arc_p->succ_next = arc_n;
1170 arc->succ_next = arc_n->succ_next;
1171 arc_n->succ_next = arc;
1184 /* Place it on the invalid chain, it will be ignored if that's
1186 blk->invalid_chain = 1;
1187 blk->chain = invalid_blocks;
1188 invalid_blocks = blk;
1191 while (invalid_blocks || valid_blocks)
1193 while ((blk = invalid_blocks))
1195 gcov_type total = 0;
1198 invalid_blocks = blk->chain;
1199 blk->invalid_chain = 0;
1201 for (arc = blk->succ; arc; arc = arc->succ_next)
1202 total += arc->count;
1203 else if (!blk->num_pred)
1204 for (arc = blk->pred; arc; arc = arc->pred_next)
1205 total += arc->count;
1210 blk->count_valid = 1;
1211 blk->chain = valid_blocks;
1212 blk->valid_chain = 1;
1215 while ((blk = valid_blocks))
1218 arc_t *arc, *inv_arc;
1220 valid_blocks = blk->chain;
1221 blk->valid_chain = 0;
1222 if (blk->num_succ == 1)
1228 for (arc = blk->succ; arc; arc = arc->succ_next)
1230 total -= arc->count;
1231 if (!arc->count_valid)
1235 inv_arc->count_valid = 1;
1236 inv_arc->count = total;
1239 if (dst->count_valid)
1241 if (dst->num_pred == 1 && !dst->valid_chain)
1243 dst->chain = valid_blocks;
1244 dst->valid_chain = 1;
1250 if (!dst->num_pred && !dst->invalid_chain)
1252 dst->chain = invalid_blocks;
1253 dst->invalid_chain = 1;
1254 invalid_blocks = dst;
1258 if (blk->num_pred == 1)
1264 for (arc = blk->pred; arc; arc = arc->pred_next)
1266 total -= arc->count;
1267 if (!arc->count_valid)
1271 inv_arc->count_valid = 1;
1272 inv_arc->count = total;
1275 if (src->count_valid)
1277 if (src->num_succ == 1 && !src->valid_chain)
1279 src->chain = valid_blocks;
1280 src->valid_chain = 1;
1286 if (!src->num_succ && !src->invalid_chain)
1288 src->chain = invalid_blocks;
1289 src->invalid_chain = 1;
1290 invalid_blocks = src;
1297 /* If the graph has been correctly solved, every block will have a
1299 for (ix = 0; ix < fn->num_blocks; ix++)
1300 if (!fn->blocks[ix].count_valid)
1302 fnotice (stderr, "%s:graph is unsolvable for `%s'\n",
1303 bbg_file_name, fn->name);
1310 /* Increment totals in COVERAGE according to arc ARC. */
1313 add_branch_counts (coverage_t *coverage, const arc_t *arc)
1315 if (arc->is_call_non_return)
1318 if (arc->src->count)
1319 coverage->calls_executed++;
1321 else if (!arc->is_unconditional)
1323 coverage->branches++;
1324 if (arc->src->count)
1325 coverage->branches_executed++;
1327 coverage->branches_taken++;
1331 /* Format a HOST_WIDE_INT as either a percent ratio, or absolute
1332 count. If dp >= 0, format TOP/BOTTOM * 100 to DP decimal places.
1333 If DP is zero, no decimal point is printed. Only print 100% when
1334 TOP==BOTTOM and only print 0% when TOP=0. If dp < 0, then simply
1335 format TOP. Return pointer to a static string. */
1338 format_gcov (gcov_type top, gcov_type bottom, int dp)
1340 static char buffer[20];
1344 float ratio = bottom ? (float)top / bottom : 0;
1346 unsigned limit = 100;
1349 for (ix = dp; ix--; )
1352 percent = (unsigned) (ratio * limit + (float)0.5);
1353 if (percent <= 0 && top)
1355 else if (percent >= limit && top != bottom)
1356 percent = limit - 1;
1357 ix = sprintf (buffer, "%.*u%%", dp + 1, percent);
1363 buffer[ix+1] = buffer[ix];
1367 buffer[ix + 1] = '.';
1371 sprintf (buffer, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT)top);
1377 /* Output summary info for a function. */
1380 function_summary (const coverage_t *coverage, const char *title)
1382 fnotice (stdout, "%s `%s'\n", title, coverage->name);
1384 if (coverage->lines)
1385 fnotice (stdout, "Lines executed:%s of %d\n",
1386 format_gcov (coverage->lines_executed, coverage->lines, 2),
1389 fnotice (stdout, "No executable lines\n");
1393 if (coverage->branches)
1395 fnotice (stdout, "Branches executed:%s of %d\n",
1396 format_gcov (coverage->branches_executed,
1397 coverage->branches, 2),
1398 coverage->branches);
1399 fnotice (stdout, "Taken at least once:%s of %d\n",
1400 format_gcov (coverage->branches_taken,
1401 coverage->branches, 2),
1402 coverage->branches);
1405 fnotice (stdout, "No branches\n");
1406 if (coverage->calls)
1407 fnotice (stdout, "Calls executed:%s of %d\n",
1408 format_gcov (coverage->calls_executed, coverage->calls, 2),
1411 fnotice (stdout, "No calls\n");
1415 /* Generate an output file name. LONG_OUTPUT_NAMES and PRESERVE_PATHS
1416 affect name generation. With preserve_paths we create a filename
1417 from all path components of the source file, replacing '/' with
1418 '#', without it we simply take the basename component. With
1419 long_output_names we prepend the processed name of the input file
1420 to each output name (except when the current source file is the
1421 input file, so you don't get a double concatenation). The two
1422 components are separated by '##'. Also '.' filename components are
1423 removed and '..' components are renamed to '^'. */
1426 make_gcov_file_name (const char *input_name, const char *src_name)
1429 char *name = xmalloc (strlen (src_name) + strlen (input_name) + 10);
1432 if (flag_long_names && strcmp (src_name, input_name))
1434 /* Generate the input filename part. */
1435 cptr = flag_preserve_paths ? NULL : strrchr (input_name, '/');
1436 strcat (name, cptr ? cptr + 1 : input_name);
1437 strcat (name, "##");
1440 /* Generate the source filename part. */
1441 cptr = flag_preserve_paths ? NULL : strrchr (src_name, '/');
1442 strcat (name, cptr ? cptr + 1 : src_name);
1444 if (flag_preserve_paths)
1446 /* Convert '/' to '#', remove '/./', convert '/../' to '/^/' */
1449 for (cptr = name; (cptr = strchr ((prev = cptr), '/'));)
1453 if (prev + 1 == cptr && prev[0] == '.')
1458 else if (prev + 2 == cptr && prev[0] == '.' && prev[1] == '.')
1470 prev[0] = prev[shift];
1476 strcat (name, ".gcov");
1480 /* Scan through the bb_data for each line in the block, increment
1481 the line number execution count indicated by the execution count of
1482 the appropriate basic block. */
1485 add_line_counts (coverage_t *coverage, function_t *fn)
1488 line_t *line = NULL; /* This is propagated from one iteration to the
1491 /* Scan each basic block. */
1492 for (ix = 0; ix != fn->num_blocks; ix++)
1494 block_t *block = &fn->blocks[ix];
1496 const source_t *src = NULL;
1499 if (block->count && ix && ix + 1 != fn->num_blocks)
1500 fn->blocks_executed++;
1501 for (jx = 0, encoding = block->u.line.encoding;
1502 jx != block->u.line.num; jx++, encoding++)
1505 unsigned src_n = *++encoding;
1507 for (src = sources; src->index != src_n; src = src->next)
1513 line = &src->lines[*encoding];
1519 if (!line->count && block->count)
1520 coverage->lines_executed++;
1523 line->count += block->count;
1525 free (block->u.line.encoding);
1526 block->u.cycle.arc = NULL;
1527 block->u.cycle.ident = ~0U;
1529 if (!ix || ix + 1 == fn->num_blocks)
1530 /* Entry or exit block */;
1531 else if (flag_all_blocks)
1533 line_t *block_line = line ? line : &fn->src->lines[fn->line];
1535 block->chain = block_line->u.blocks;
1536 block_line->u.blocks = block;
1538 else if (flag_branches)
1542 for (arc = block->succ; arc; arc = arc->succ_next)
1544 arc->line_next = line->u.branches;
1545 line->u.branches = arc;
1546 if (coverage && !arc->is_unconditional)
1547 add_branch_counts (coverage, arc);
1552 fnotice (stderr, "%s:no lines for `%s'\n", bbg_file_name, fn->name);
1555 /* Accumulate the line counts of a file. */
1558 accumulate_line_counts (source_t *src)
1561 function_t *fn, *fn_p, *fn_n;
1564 /* Reverse the function order. */
1565 for (fn = src->functions, fn_p = NULL; fn;
1566 fn_p = fn, fn = fn_n)
1568 fn_n = fn->line_next;
1569 fn->line_next = fn_p;
1571 src->functions = fn_p;
1573 for (ix = src->num_lines, line = src->lines; ix--; line++)
1575 if (!flag_all_blocks)
1577 arc_t *arc, *arc_p, *arc_n;
1579 /* Total and reverse the branch information. */
1580 for (arc = line->u.branches, arc_p = NULL; arc;
1581 arc_p = arc, arc = arc_n)
1583 arc_n = arc->line_next;
1584 arc->line_next = arc_p;
1586 add_branch_counts (&src->coverage, arc);
1588 line->u.branches = arc_p;
1590 else if (line->u.blocks)
1592 /* The user expects the line count to be the number of times
1593 a line has been executed. Simply summing the block count
1594 will give an artificially high number. The Right Thing
1595 is to sum the entry counts to the graph of blocks on this
1596 line, then find the elementary cycles of the local graph
1597 and add the transition counts of those cycles. */
1598 block_t *block, *block_p, *block_n;
1599 gcov_type count = 0;
1601 /* Reverse the block information. */
1602 for (block = line->u.blocks, block_p = NULL; block;
1603 block_p = block, block = block_n)
1605 block_n = block->chain;
1606 block->chain = block_p;
1607 block->u.cycle.ident = ix;
1609 line->u.blocks = block_p;
1611 /* Sum the entry arcs. */
1612 for (block = line->u.blocks; block; block = block->chain)
1616 for (arc = block->pred; arc; arc = arc->pred_next)
1618 if (arc->src->u.cycle.ident != ix)
1619 count += arc->count;
1621 add_branch_counts (&src->coverage, arc);
1624 /* Initialize the cs_count. */
1625 for (arc = block->succ; arc; arc = arc->succ_next)
1626 arc->cs_count = arc->count;
1629 /* Find the loops. This uses the algorithm described in
1630 Tiernan 'An Efficient Search Algorithm to Find the
1631 Elementary Circuits of a Graph', CACM Dec 1970. We hold
1632 the P array by having each block point to the arc that
1633 connects to the previous block. The H array is implicitly
1634 held because of the arc ordering, and the block's
1635 previous arc pointer.
1637 Although the algorithm is O(N^3) for highly connected
1638 graphs, at worst we'll have O(N^2), as most blocks have
1639 only one or two exits. Most graphs will be small.
1641 For each loop we find, locate the arc with the smallest
1642 transition count, and add that to the cumulative
1643 count. Decrease flow over the cycle and remove the arc
1644 from consideration. */
1645 for (block = line->u.blocks; block; block = block->chain)
1647 block_t *head = block;
1655 block_t *dst = arc->dst;
1656 if (/* Already used that arc. */
1658 /* Not to same graph, or before first vertex. */
1659 || dst->u.cycle.ident != ix
1660 /* Already in path. */
1661 || dst->u.cycle.arc)
1663 arc = arc->succ_next;
1669 /* Found a closing arc. */
1670 gcov_type cycle_count = arc->cs_count;
1671 arc_t *cycle_arc = arc;
1674 /* Locate the smallest arc count of the loop. */
1675 for (dst = head; (probe_arc = dst->u.cycle.arc);
1676 dst = probe_arc->src)
1677 if (cycle_count > probe_arc->cs_count)
1679 cycle_count = probe_arc->cs_count;
1680 cycle_arc = probe_arc;
1683 count += cycle_count;
1684 cycle_arc->cycle = 1;
1686 /* Remove the flow from the cycle. */
1687 arc->cs_count -= cycle_count;
1688 for (dst = head; (probe_arc = dst->u.cycle.arc);
1689 dst = probe_arc->src)
1690 probe_arc->cs_count -= cycle_count;
1692 /* Unwind to the cyclic arc. */
1693 while (head != cycle_arc->src)
1695 arc = head->u.cycle.arc;
1696 head->u.cycle.arc = NULL;
1700 arc = arc->succ_next;
1704 /* Add new block to chain. */
1705 dst->u.cycle.arc = arc;
1709 /* We could not add another vertex to the path. Remove
1710 the last vertex from the list. */
1711 arc = head->u.cycle.arc;
1714 /* It was not the first vertex. Move onto next arc. */
1715 head->u.cycle.arc = NULL;
1717 arc = arc->succ_next;
1718 goto current_vertex;
1720 /* Mark this block as unusable. */
1721 block->u.cycle.ident = ~0U;
1724 line->count = count;
1729 src->coverage.lines++;
1731 src->coverage.lines_executed++;
1736 /* Output information about ARC number IX. Returns nonzero if
1737 anything is output. */
1740 output_branch_count (FILE *gcov_file, int ix, const arc_t *arc)
1743 if (arc->is_call_non_return)
1745 if (arc->src->count)
1747 fnotice (gcov_file, "call %2d returned %s\n", ix,
1748 format_gcov (arc->src->count - arc->count,
1749 arc->src->count, -flag_counts));
1752 fnotice (gcov_file, "call %2d never executed\n", ix);
1754 else if (!arc->is_unconditional)
1756 if (arc->src->count)
1757 fnotice (gcov_file, "branch %2d taken %s%s\n", ix,
1758 format_gcov (arc->count, arc->src->count, -flag_counts),
1759 arc->fall_through ? " (fallthrough)" : "");
1761 fnotice (gcov_file, "branch %2d never executed\n", ix);
1763 else if (flag_unconditional && !arc->dst->is_call_return)
1765 if (arc->src->count)
1766 fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
1767 format_gcov (arc->count, arc->src->count, -flag_counts));
1769 fnotice (gcov_file, "unconditional %2d never executed\n", ix);
1777 /* Read in the source file one line at a time, and output that line to
1778 the gcov file preceded by its execution count and other
1782 output_lines (FILE *gcov_file, const source_t *src)
1785 unsigned line_num; /* current line number. */
1786 const line_t *line; /* current line info ptr. */
1787 char string[STRING_SIZE]; /* line buffer. */
1788 char const *retval = ""; /* status of source file reading. */
1789 function_t *fn = src->functions;
1791 fprintf (gcov_file, "%9s:%5d:Source:%s\n", "-", 0, src->name);
1792 fprintf (gcov_file, "%9s:%5d:Graph:%s\n", "-", 0, bbg_file_name);
1793 fprintf (gcov_file, "%9s:%5d:Data:%s\n", "-", 0, da_file_name);
1794 fprintf (gcov_file, "%9s:%5d:Runs:%u\n", "-", 0,
1795 object_summary.ctrs[GCOV_COUNTER_ARCS].runs);
1796 fprintf (gcov_file, "%9s:%5d:Programs:%u\n", "-", 0, program_count);
1798 source_file = fopen (src->name, "r");
1801 fnotice (stderr, "%s:cannot open source file\n", src->name);
1808 if (!fstat (fileno (source_file), &status)
1809 && status.st_mtime > bbg_file_time)
1811 fnotice (stderr, "%s:source file is newer than graph file `%s'\n",
1812 src->name, bbg_file_name);
1813 fprintf (gcov_file, "%9s:%5d:Source is newer than graph\n",
1818 for (line_num = 1, line = &src->lines[line_num];
1819 line_num < src->num_lines; line_num++, line++)
1821 for (; fn && fn->line == line_num; fn = fn->line_next)
1823 arc_t *arc = fn->blocks[fn->num_blocks - 1].pred;
1824 gcov_type return_count = fn->blocks[fn->num_blocks - 1].count;
1826 for (; arc; arc = arc->pred_next)
1828 return_count -= arc->count;
1830 fprintf (gcov_file, "function %s", fn->name);
1831 fprintf (gcov_file, " called %s",
1832 format_gcov (fn->blocks[0].count, 0, -1));
1833 fprintf (gcov_file, " returned %s",
1834 format_gcov (return_count, fn->blocks[0].count, 0));
1835 fprintf (gcov_file, " blocks executed %s",
1836 format_gcov (fn->blocks_executed, fn->num_blocks - 2, 0));
1837 fprintf (gcov_file, "\n");
1840 /* For lines which don't exist in the .bb file, print '-' before
1841 the source line. For lines which exist but were never
1842 executed, print '#####' before the source line. Otherwise,
1843 print the execution count before the source line. There are
1844 16 spaces of indentation added before the source line so that
1845 tabs won't be messed up. */
1846 fprintf (gcov_file, "%9s:%5u:",
1847 !line->exists ? "-" : !line->count ? "#####"
1848 : format_gcov (line->count, 0, -1), line_num);
1852 /* Copy source line. */
1855 retval = fgets (string, STRING_SIZE, source_file);
1858 fputs (retval, gcov_file);
1860 while (!retval[0] || retval[strlen (retval) - 1] != '\n');
1863 fputs ("/*EOF*/\n", gcov_file);
1865 if (flag_all_blocks)
1871 for (ix = jx = 0, block = line->u.blocks; block;
1872 block = block->chain)
1874 if (!block->is_call_return)
1875 fprintf (gcov_file, "%9s:%5u-block %2d\n",
1876 !line->exists ? "-" : !block->count ? "$$$$$"
1877 : format_gcov (block->count, 0, -1),
1880 for (arc = block->succ; arc; arc = arc->succ_next)
1881 jx += output_branch_count (gcov_file, jx, arc);
1884 else if (flag_branches)
1889 for (ix = 0, arc = line->u.branches; arc; arc = arc->line_next)
1890 ix += output_branch_count (gcov_file, ix, arc);
1894 /* Handle all remaining source lines. There may be lines after the
1895 last line of code. */
1898 for (; (retval = fgets (string, STRING_SIZE, source_file)); line_num++)
1900 fprintf (gcov_file, "%9s:%5u:%s", "-", line_num, retval);
1902 while (!retval[0] || retval[strlen (retval) - 1] != '\n')
1904 retval = fgets (string, STRING_SIZE, source_file);
1907 fputs (retval, gcov_file);
1913 fclose (source_file);