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 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 /* Name and file pointer of the input file for the arc count data. */
274 static char *da_file_name;
276 /* Output branch probabilities. */
278 static int flag_branches = 0;
280 /* Show unconditional branches too. */
281 static int flag_unconditional = 0;
283 /* Output a gcov file if this is true. This is on by default, and can
284 be turned off by the -n option. */
286 static int flag_gcov_file = 1;
288 /* For included files, make the gcov output file name include the name
289 of the input source file. For example, if x.h is included in a.c,
290 then the output file name is a.c##x.h.gcov instead of x.h.gcov. */
292 static int flag_long_names = 0;
294 /* Output count information for every basic block, not merely those
295 that contain line number information. */
297 static int flag_all_blocks = 0;
299 /* Output summary info for each function. */
301 static int flag_function_summary = 0;
303 /* Object directory file prefix. This is the directory/file where the
304 graph and data files are looked for, if nonzero. */
306 static char *object_directory = 0;
308 /* Preserve all pathname components. Needed when object files and
309 source files are in subdirectories. '/' is mangled as '#', '.' is
310 elided and '..' mangled to '^'. */
312 static int flag_preserve_paths = 0;
314 /* Output the number of times a branch was taken as opposed to the percentage
315 of times it was taken. */
317 static int flag_counts = 0;
319 /* Forward declarations. */
320 static void fnotice PARAMS ((FILE *, const char *, ...)) ATTRIBUTE_PRINTF_2;
321 static int process_args PARAMS ((int, char **));
322 static void print_usage PARAMS ((int)) ATTRIBUTE_NORETURN;
323 static void print_version PARAMS ((void)) ATTRIBUTE_NORETURN;
324 static void process_file PARAMS ((const char *));
325 static void create_file_names PARAMS ((const char *));
326 static source_t *find_source PARAMS ((const char *));
327 static int read_graph_file PARAMS ((void));
328 static int read_count_file PARAMS ((void));
329 static void solve_flow_graph PARAMS ((function_t *));
330 static void add_branch_counts PARAMS ((coverage_t *, const arc_t *));
331 static void add_line_counts PARAMS ((coverage_t *, function_t *));
332 static void function_summary PARAMS ((const coverage_t *, const char *));
333 static const char *format_gcov PARAMS ((gcov_type, gcov_type, int));
334 static void accumulate_line_counts PARAMS ((source_t *));
335 static int output_branch_count PARAMS ((FILE *, int, const arc_t *));
336 static void output_lines PARAMS ((FILE *, const source_t *));
337 static char *make_gcov_file_name PARAMS ((const char *, const char *));
338 static void release_structures PARAMS ((void));
339 extern int main PARAMS ((int, char **));
350 argno = process_args (argc, argv);
354 for (; argno != argc; argno++)
356 release_structures ();
358 process_file (argv[argno]);
365 fnotice (FILE *file, const char *msgid, ...)
369 va_start (ap, msgid);
370 vfprintf (file, _(msgid), ap);
374 /* More 'friendly' abort that prints the line and file.
375 config.h can #define abort fancy_abort if you like that sort of thing. */
376 extern void fancy_abort PARAMS ((void)) ATTRIBUTE_NORETURN;
381 fnotice (stderr, "Internal gcov abort.\n");
382 exit (FATAL_EXIT_CODE);
385 /* Print a usage message and exit. If ERROR_P is nonzero, this is an error,
386 otherwise the output of --help. */
389 print_usage (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. */
421 unsigned version = GCOV_VERSION;
424 for (ix = 4; ix--; version >>= 8)
426 fnotice (stdout, "gcov %.4s (GCC %s)\n", v, version_string);
427 fnotice (stdout, "Copyright (C) 2002 Free Software Foundation, Inc.\n");
429 "This is free software; see the source for copying conditions. There is NO\n\
430 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\n");
431 exit (SUCCESS_EXIT_CODE);
434 static const struct option options[] =
436 { "help", no_argument, NULL, 'h' },
437 { "version", no_argument, NULL, 'v' },
438 { "all-blocks", no_argument, NULL, 'a' },
439 { "branch-probabilities", no_argument, NULL, 'b' },
440 { "branch-counts", no_argument, NULL, 'c' },
441 { "no-output", no_argument, NULL, 'n' },
442 { "long-file-names", no_argument, NULL, 'l' },
443 { "function-summaries", no_argument, NULL, 'f' },
444 { "preserve-paths", no_argument, NULL, 'p' },
445 { "object-directory", required_argument, NULL, 'o' },
446 { "object-file", required_argument, NULL, 'o' },
447 { "unconditional-branches", no_argument, NULL, 'u' },
450 /* Process args, return index to first non-arg. */
453 process_args (argc, argv)
459 while ((opt = getopt_long (argc, argv, "abcfhlno:puv", options, NULL)) != -1)
473 flag_function_summary = 1;
477 /* print_usage will exit. */
485 object_directory = optarg;
488 flag_preserve_paths = 1;
491 flag_unconditional = 1;
495 /* print_version will exit. */
498 /* print_usage will exit. */
505 /* Process a single source file. */
508 process_file (file_name)
509 const char *file_name;
514 create_file_names (file_name);
515 if (read_graph_file ())
520 fnotice (stderr, "%s:no functions found\n", bbg_file_name);
524 if (read_count_file ())
527 for (fn = functions; fn; fn = fn->next)
528 solve_flow_graph (fn);
529 for (src = sources; src; src = src->next)
530 src->lines = (line_t *) xcalloc (src->num_lines, sizeof (line_t));
531 for (fn = functions; fn; fn = fn->next)
535 memset (&coverage, 0, sizeof (coverage));
536 coverage.name = fn->name;
537 add_line_counts (flag_function_summary ? &coverage : NULL, fn);
538 if (flag_function_summary)
540 function_summary (&coverage, "Function");
541 fnotice (stdout, "\n");
545 for (src = sources; src; src = src->next)
547 accumulate_line_counts (src);
548 function_summary (&src->coverage, "File");
551 char *gcov_file_name = make_gcov_file_name (file_name, src->name);
552 FILE *gcov_file = fopen (gcov_file_name, "w");
556 fnotice (stdout, "%s:creating `%s'\n",
557 src->name, gcov_file_name);
558 output_lines (gcov_file, src);
559 if (ferror (gcov_file))
560 fnotice (stderr, "%s:error writing output file `%s'\n",
561 src->name, gcov_file_name);
565 fnotice (stderr, "%s:could not open output file `%s'\n",
566 src->name, gcov_file_name);
567 free (gcov_file_name);
569 fnotice (stdout, "\n");
573 /* Release all memory used. */
576 release_structures ()
581 free (bbg_file_name);
583 da_file_name = bbg_file_name = NULL;
586 while ((src = sources))
594 while ((fn = functions))
599 functions = fn->next;
600 for (ix = fn->num_blocks, block = fn->blocks; ix--; block++)
604 for (arc = block->succ; arc; arc = arc_n)
606 arc_n = arc->succ_next;
615 /* Generate the names of the graph and data files. If OBJECT_DIRECTORY
616 is not specified, these are looked for in the current directory,
617 and named from the basename of the FILE_NAME sans extension. If
618 OBJECT_DIRECTORY is specified and is a directory, the files are in
619 that directory, but named from the basename of the FILE_NAME, sans
620 extension. Otherwise OBJECT_DIRECTORY is taken to be the name of
621 the object *file*, and the data files are named from that. */
624 create_file_names (file_name)
625 const char *file_name;
629 int length = strlen (file_name);
632 if (object_directory && object_directory[0])
636 length += strlen (object_directory) + 2;
637 name = xmalloc (length);
640 base = !stat (object_directory, &status) && S_ISDIR (status.st_mode);
641 strcat (name, object_directory);
642 if (base && name[strlen (name) - 1] != '/')
647 name = xmalloc (length + 1);
654 /* Append source file name */
655 cptr = strrchr (file_name, '/');
656 strcat (name, cptr ? cptr + 1 : file_name);
659 /* Remove the extension. */
660 cptr = strrchr (name, '.');
664 length = strlen (name);
666 bbg_file_name = xmalloc (length + strlen (GCOV_GRAPH_SUFFIX) + 1);
667 strcpy (bbg_file_name, name);
668 strcpy (bbg_file_name + length, GCOV_GRAPH_SUFFIX);
670 da_file_name = xmalloc (length + strlen (GCOV_DATA_SUFFIX) + 1);
671 strcpy (da_file_name, name);
672 strcpy (da_file_name + length, GCOV_DATA_SUFFIX);
677 /* Find or create a source file structure for FILE_NAME. Copies
678 FILE_NAME on creation */
681 find_source (file_name)
682 const char *file_name;
687 file_name = "<unknown>";
689 for (src = sources; src; src = src->next)
690 if (!strcmp (file_name, src->name))
693 src = (source_t *)xcalloc (1, sizeof (source_t));
694 src->name = xstrdup (file_name);
695 src->coverage.name = src->name;
696 src->index = sources ? sources->index + 1 : 1;
703 /* Read the graph file. Return nonzero on fatal error. */
709 unsigned current_tag = 0;
710 struct function_info *fn = NULL;
711 source_t *src = NULL;
715 if (!gcov_open (bbg_file_name, 1))
717 fnotice (stderr, "%s:cannot open graph file\n", bbg_file_name);
720 bbg_file_time = gcov_time ();
721 if (gcov_read_unsigned () != GCOV_GRAPH_MAGIC)
723 fnotice (stderr, "%s:not a gcov graph file\n", bbg_file_name);
728 version = gcov_read_unsigned ();
729 if (version != GCOV_VERSION)
732 unsigned required = GCOV_VERSION;
734 for (ix = 4; ix--; required >>= 8, version >>= 8)
739 fnotice (stderr, "%s:version `%.4s', prefer `%.4s'\n",
740 bbg_file_name, v, e);
743 while ((tag = gcov_read_unsigned ()))
745 unsigned length = gcov_read_unsigned ();
746 gcov_position_t base = gcov_position ();
748 if (tag == GCOV_TAG_FUNCTION)
751 unsigned ident, checksum, lineno;
753 function_t *probe, *prev;
755 ident = gcov_read_unsigned ();
756 checksum = gcov_read_unsigned ();
757 function_name = xstrdup (gcov_read_string ());
758 src = find_source (gcov_read_string ());
759 lineno = gcov_read_unsigned ();
761 fn = (function_t *)xcalloc (1, sizeof (function_t));
762 fn->name = function_name;
764 fn->checksum = checksum;
768 fn->next = functions;
772 if (lineno >= src->num_lines)
773 src->num_lines = lineno + 1;
774 /* Now insert it into the source file's list of
775 functions. Normally functions will be encountered in
776 ascending order, so a simple scan is quick. */
777 for (probe = src->functions, prev = NULL;
778 probe && probe->line > lineno;
779 prev = probe, probe = probe->line_next)
781 fn->line_next = probe;
783 prev->line_next = fn;
787 else if (fn && tag == GCOV_TAG_BLOCKS)
790 fnotice (stderr, "%s:already seen blocks for `%s'\n",
791 bbg_file_name, fn->name);
794 unsigned ix, num_blocks = length / 4;
795 fn->num_blocks = num_blocks;
798 = (block_t *)xcalloc (fn->num_blocks, sizeof (block_t));
799 for (ix = 0; ix != num_blocks; ix++)
800 fn->blocks[ix].flags = gcov_read_unsigned ();
803 else if (fn && tag == GCOV_TAG_ARCS)
805 unsigned src = gcov_read_unsigned ();
806 unsigned num_dests = (length - 4) / 8;
808 if (src >= fn->num_blocks || fn->blocks[src].succ)
813 struct arc_info *arc;
814 unsigned dest = gcov_read_unsigned ();
815 unsigned flags = gcov_read_unsigned ();
817 if (dest >= fn->num_blocks)
819 arc = (arc_t *) xcalloc (1, sizeof (arc_t));
821 arc->dst = &fn->blocks[dest];
822 arc->src = &fn->blocks[src];
825 arc->count_valid = 0;
826 arc->on_tree = !!(flags & GCOV_ARC_ON_TREE);
827 arc->fake = !!(flags & GCOV_ARC_FAKE);
828 arc->fall_through = !!(flags & GCOV_ARC_FALLTHROUGH);
830 arc->succ_next = fn->blocks[src].succ;
831 fn->blocks[src].succ = arc;
832 fn->blocks[src].num_succ++;
834 arc->pred_next = fn->blocks[dest].pred;
835 fn->blocks[dest].pred = arc;
836 fn->blocks[dest].num_pred++;
842 /* Exceptional exit from this function, the
843 source block must be a call. */
844 fn->blocks[src].is_call_site = 1;
845 arc->is_call_non_return = 1;
849 /* Non-local return from a callee of this
850 function. The destination block is a catch or
852 arc->is_nonlocal_return = 1;
853 fn->blocks[dest].is_nonlocal_return = 1;
861 else if (fn && tag == GCOV_TAG_LINES)
863 unsigned blockno = gcov_read_unsigned ();
865 = (unsigned *)xcalloc ((length - 4) / 4, sizeof (unsigned));
867 if (blockno >= fn->num_blocks || fn->blocks[blockno].u.line.encoding)
872 unsigned lineno = gcov_read_unsigned ();
879 line_nos[ix++] = src->index;
881 line_nos[ix++] = lineno;
882 if (lineno >= src->num_lines)
883 src->num_lines = lineno + 1;
887 const char *file_name = gcov_read_string ();
891 src = find_source (file_name);
894 line_nos[ix++] = src->index;
898 fn->blocks[blockno].u.line.encoding = line_nos;
899 fn->blocks[blockno].u.line.num = ix;
901 else if (current_tag && !GCOV_TAG_IS_SUBTAG (current_tag, tag))
906 gcov_sync (base, length);
907 if (gcov_is_error ())
913 fnotice (stderr, "%s:corrupted\n", bbg_file_name);
919 /* We built everything backwards, so nreverse them all */
921 /* Reverse sources. Not strictly necessary, but we'll then process
922 them in the 'expected' order. */
924 source_t *src, *src_p, *src_n;
926 for (src_p = NULL, src = sources; src; src_p = src, src = src_n)
934 /* Reverse functions. */
936 function_t *fn, *fn_p, *fn_n;
938 for (fn_p = NULL, fn = functions; fn; fn_p = fn, fn = fn_n)
945 /* Reverse the arcs */
946 for (ix = fn->num_blocks; ix--;)
948 arc_t *arc, *arc_p, *arc_n;
950 for (arc_p = NULL, arc = fn->blocks[ix].succ; arc;
951 arc_p = arc, arc = arc_n)
953 arc_n = arc->succ_next;
954 arc->succ_next = arc_p;
956 fn->blocks[ix].succ = arc_p;
958 for (arc_p = NULL, arc = fn->blocks[ix].pred; arc;
959 arc_p = arc, arc = arc_n)
961 arc_n = arc->pred_next;
962 arc->pred_next = arc_p;
964 fn->blocks[ix].pred = arc_p;
972 /* Reads profiles from the count file and attach to each
973 function. Return nonzero if fatal error. */
981 function_t *fn = NULL;
984 if (!gcov_open (da_file_name, 1))
986 fnotice (stderr, "%s:cannot open data file\n", da_file_name);
989 if (gcov_read_unsigned () != GCOV_DATA_MAGIC)
991 fnotice (stderr, "%s:not a gcov data file\n", da_file_name);
996 version = gcov_read_unsigned ();
997 if (version != GCOV_VERSION)
1000 unsigned desired = GCOV_VERSION;
1002 for (ix = 4; ix--; desired >>= 8, version >>= 8)
1007 fnotice (stderr, "%s:version `%.4s', prefer version `%.4s'\n",
1008 da_file_name, v, e);
1011 while ((tag = gcov_read_unsigned ()))
1013 unsigned length = gcov_read_unsigned ();
1014 unsigned long base = gcov_position ();
1016 if (tag == GCOV_TAG_OBJECT_SUMMARY)
1017 gcov_read_summary (&object_summary);
1018 else if (tag == GCOV_TAG_PROGRAM_SUMMARY)
1020 else if (tag == GCOV_TAG_FUNCTION)
1022 unsigned ident = gcov_read_unsigned ();
1023 struct function_info *fn_n = functions;
1025 for (fn = fn ? fn->next : NULL; ; fn = fn->next)
1029 else if ((fn = fn_n))
1033 fnotice (stderr, "%s:unknown function `%u'\n",
1034 da_file_name, ident);
1037 if (fn->ident == ident)
1043 else if (gcov_read_unsigned () != fn->checksum)
1046 fnotice (stderr, "%s:profile mismatch for `%s'\n",
1047 da_file_name, fn->name);
1051 else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn)
1053 if (length != 8 * fn->num_counts)
1058 = (gcov_type *)xcalloc (fn->num_counts, sizeof (gcov_type));
1060 for (ix = 0; ix != fn->num_counts; ix++)
1061 fn->counts[ix] += gcov_read_counter ();
1063 gcov_sync (base, length);
1064 if ((error = gcov_is_error ()))
1068 if (!gcov_is_eof ())
1070 fnotice (stderr, error < 0 ? "%s:overflowed\n" : "%s:corrupted\n",
1079 /* Solve the flow graph. Propagate counts from the instrumented arcs
1080 to the blocks and the uninstrumented arcs. */
1083 solve_flow_graph (fn)
1088 gcov_type *count_ptr = fn->counts;
1090 block_t *valid_blocks = NULL; /* valid, but unpropagated blocks. */
1091 block_t *invalid_blocks = NULL; /* invalid, but inferable blocks. */
1093 if (fn->num_blocks < 2)
1094 fnotice (stderr, "%s:`%s' lacks entry and/or exit blocks\n",
1095 bbg_file_name, fn->name);
1098 if (fn->blocks[0].num_pred)
1099 fnotice (stderr, "%s:`%s' has arcs to entry block\n",
1100 bbg_file_name, fn->name);
1102 /* We can't deduce the entry block counts from the lack of
1104 fn->blocks[0].num_pred = ~(unsigned)0;
1106 if (fn->blocks[fn->num_blocks - 1].num_succ)
1107 fnotice (stderr, "%s:`%s' has arcs from exit block\n",
1108 bbg_file_name, fn->name);
1110 /* Likewise, we can't deduce exit block counts from the lack
1111 of its successors. */
1112 fn->blocks[fn->num_blocks - 1].num_succ = ~(unsigned)0;
1115 /* Propagate the measured counts, this must be done in the same
1116 order as the code in profile.c */
1117 for (ix = 0, blk = fn->blocks; ix != fn->num_blocks; ix++, blk++)
1119 block_t const *prev_dst = NULL;
1120 int out_of_order = 0;
1121 int non_fake_succ = 0;
1123 for (arc = blk->succ; arc; arc = arc->succ_next)
1131 arc->count = *count_ptr++;
1132 arc->count_valid = 1;
1134 arc->dst->num_pred--;
1136 if (prev_dst && prev_dst > arc->dst)
1138 prev_dst = arc->dst;
1140 if (non_fake_succ == 1)
1142 /* If there is only one non-fake exit, it is an
1143 unconditional branch. */
1144 for (arc = blk->succ; arc; arc = arc->succ_next)
1147 arc->is_unconditional = 1;
1148 /* If this block is instrumenting a call, it might be
1149 an artifical block. It is not artificial if it has
1150 a non-fallthrough exit, or the destination of this
1151 arc has more than one entry. Mark the destination
1152 block as a return site, if none of those conditions
1154 if (blk->is_call_site && arc->fall_through
1155 && arc->dst->pred == arc && !arc->pred_next)
1156 arc->dst->is_call_return = 1;
1160 /* Sort the successor arcs into ascending dst order. profile.c
1161 normally produces arcs in the right order, but sometimes with
1162 one or two out of order. We're not using a particularly
1166 arc_t *start = blk->succ;
1167 unsigned changes = 1;
1171 arc_t *arc, *arc_p, *arc_n;
1174 for (arc_p = NULL, arc = start; (arc_n = arc->succ_next);)
1176 if (arc->dst > arc_n->dst)
1180 arc_p->succ_next = arc_n;
1183 arc->succ_next = arc_n->succ_next;
1184 arc_n->succ_next = arc;
1197 /* Place it on the invalid chain, it will be ignored if that's
1199 blk->invalid_chain = 1;
1200 blk->chain = invalid_blocks;
1201 invalid_blocks = blk;
1204 while (invalid_blocks || valid_blocks)
1206 while ((blk = invalid_blocks))
1208 gcov_type total = 0;
1211 invalid_blocks = blk->chain;
1212 blk->invalid_chain = 0;
1214 for (arc = blk->succ; arc; arc = arc->succ_next)
1215 total += arc->count;
1216 else if (!blk->num_pred)
1217 for (arc = blk->pred; arc; arc = arc->pred_next)
1218 total += arc->count;
1223 blk->count_valid = 1;
1224 blk->chain = valid_blocks;
1225 blk->valid_chain = 1;
1228 while ((blk = valid_blocks))
1231 arc_t *arc, *inv_arc;
1233 valid_blocks = blk->chain;
1234 blk->valid_chain = 0;
1235 if (blk->num_succ == 1)
1241 for (arc = blk->succ; arc; arc = arc->succ_next)
1243 total -= arc->count;
1244 if (!arc->count_valid)
1248 inv_arc->count_valid = 1;
1249 inv_arc->count = total;
1252 if (dst->count_valid)
1254 if (dst->num_pred == 1 && !dst->valid_chain)
1256 dst->chain = valid_blocks;
1257 dst->valid_chain = 1;
1263 if (!dst->num_pred && !dst->invalid_chain)
1265 dst->chain = invalid_blocks;
1266 dst->invalid_chain = 1;
1267 invalid_blocks = dst;
1271 if (blk->num_pred == 1)
1277 for (arc = blk->pred; arc; arc = arc->pred_next)
1279 total -= arc->count;
1280 if (!arc->count_valid)
1284 inv_arc->count_valid = 1;
1285 inv_arc->count = total;
1288 if (src->count_valid)
1290 if (src->num_succ == 1 && !src->valid_chain)
1292 src->chain = valid_blocks;
1293 src->valid_chain = 1;
1299 if (!src->num_succ && !src->invalid_chain)
1301 src->chain = invalid_blocks;
1302 src->invalid_chain = 1;
1303 invalid_blocks = src;
1310 /* If the graph has been correctly solved, every block will have a
1312 for (ix = 0; ix < fn->num_blocks; ix++)
1313 if (!fn->blocks[ix].count_valid)
1315 fnotice (stderr, "%s:graph is unsolvable for `%s'\n",
1316 bbg_file_name, fn->name);
1323 /* Increment totals in COVERAGE according to arc ARC. */
1326 add_branch_counts (coverage, arc)
1327 coverage_t *coverage;
1330 if (arc->is_call_non_return)
1333 if (arc->src->count)
1334 coverage->calls_executed++;
1336 else if (!arc->is_unconditional)
1338 coverage->branches++;
1339 if (arc->src->count)
1340 coverage->branches_executed++;
1342 coverage->branches_taken++;
1346 /* Format a HOST_WIDE_INT as either a percent ratio, or absolute
1347 count. If dp >= 0, format TOP/BOTTOM * 100 to DP decimal places.
1348 If DP is zero, no decimal point is printed. Only print 100% when
1349 TOP==BOTTOM and only print 0% when TOP=0. If dp < 0, then simply
1350 format TOP. Return pointer to a static string. */
1353 format_gcov (top, bottom, dp)
1354 gcov_type top, bottom;
1357 static char buffer[20];
1361 float ratio = bottom ? (float)top / bottom : 0;
1363 unsigned limit = 100;
1366 for (ix = dp; ix--; )
1369 percent = (unsigned) (ratio * limit + (float)0.5);
1370 if (percent <= 0 && top)
1372 else if (percent >= limit && top != bottom)
1373 percent = limit - 1;
1374 ix = sprintf (buffer, "%.*u%%", dp + 1, percent);
1380 buffer[ix+1] = buffer[ix];
1384 buffer[ix + 1] = '.';
1388 sprintf (buffer, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT)top);
1394 /* Output summary info for a function. */
1397 function_summary (coverage, title)
1398 const coverage_t *coverage;
1401 fnotice (stdout, "%s `%s'\n", title, coverage->name);
1403 if (coverage->lines)
1404 fnotice (stdout, "Lines executed:%s of %d\n",
1405 format_gcov (coverage->lines_executed, coverage->lines, 2),
1408 fnotice (stdout, "No executable lines");
1412 if (coverage->branches)
1414 fnotice (stdout, "Branches executed:%s of %d\n",
1415 format_gcov (coverage->branches_executed,
1416 coverage->branches, 2),
1417 coverage->branches);
1418 fnotice (stdout, "Taken at least once:%s of %d\n",
1419 format_gcov (coverage->branches_taken,
1420 coverage->branches, 2),
1421 coverage->branches);
1424 fnotice (stdout, "No branches\n");
1425 if (coverage->calls)
1426 fnotice (stdout, "Calls executed:%s of %d\n",
1427 format_gcov (coverage->calls_executed, coverage->calls, 2),
1430 fnotice (stdout, "No calls\n");
1434 /* Generate an output file name. LONG_OUTPUT_NAMES and PRESERVE_PATHS
1435 affect name generation. With preserve_paths we create a filename
1436 from all path components of the source file, replacing '/' with
1437 '#', without it we simply take the basename component. With
1438 long_output_names we prepend the processed name of the input file
1439 to each output name (except when the current source file is the
1440 input file, so you don't get a double concatenation). The two
1441 components are separated by '##'. Also '.' filename components are
1442 removed and '..' components are renamed to '^'. */
1445 make_gcov_file_name (input_name, src_name)
1446 const char *input_name;
1447 const char *src_name;
1450 char *name = xmalloc (strlen (src_name) + strlen (input_name) + 10);
1453 if (flag_long_names && strcmp (src_name, input_name))
1455 /* Generate the input filename part. */
1456 cptr = flag_preserve_paths ? NULL : strrchr (input_name, '/');
1457 strcat (name, cptr ? cptr + 1 : input_name);
1458 strcat (name, "##");
1461 /* Generate the source filename part. */
1462 cptr = flag_preserve_paths ? NULL : strrchr (src_name, '/');
1463 strcat (name, cptr ? cptr + 1 : src_name);
1465 if (flag_preserve_paths)
1467 /* Convert '/' to '#', remove '/./', convert '/../' to '/^/' */
1470 for (cptr = name; (cptr = strchr ((prev = cptr), '/'));)
1474 if (prev + 1 == cptr && prev[0] == '.')
1479 else if (prev + 2 == cptr && prev[0] == '.' && prev[1] == '.')
1491 prev[0] = prev[shift];
1497 strcat (name, ".gcov");
1501 /* Scan through the bb_data for each line in the block, increment
1502 the line number execution count indicated by the execution count of
1503 the appropriate basic block. */
1506 add_line_counts (coverage, fn)
1507 coverage_t *coverage;
1511 line_t *line = NULL; /* this is propagated from one iteration to the
1514 /* Scan each basic block. */
1515 for (ix = 0; ix != fn->num_blocks; ix++)
1517 block_t *block = &fn->blocks[ix];
1519 const source_t *src = NULL;
1522 if (block->count && ix && ix + 1 != fn->num_blocks)
1523 fn->blocks_executed++;
1524 for (jx = 0, encoding = block->u.line.encoding;
1525 jx != block->u.line.num; jx++, encoding++)
1528 unsigned src_n = *++encoding;
1530 for (src = sources; src->index != src_n; src = src->next)
1536 line = &src->lines[*encoding];
1542 if (!line->count && block->count)
1543 coverage->lines_executed++;
1546 line->count += block->count;
1548 free (block->u.line.encoding);
1549 block->u.cycle.arc = NULL;
1550 block->u.cycle.ident = ~0U;
1552 if (!ix || ix + 1 == fn->num_blocks)
1553 /* Entry or exit block */;
1554 else if (flag_all_blocks)
1556 line_t *block_line = line ? line : &fn->src->lines[fn->line];
1558 block->chain = block_line->u.blocks;
1559 block_line->u.blocks = block;
1561 else if (flag_branches)
1565 for (arc = block->succ; arc; arc = arc->succ_next)
1567 arc->line_next = line->u.branches;
1568 line->u.branches = arc;
1569 if (coverage && !arc->is_unconditional)
1570 add_branch_counts (coverage, arc);
1575 fnotice (stderr, "%s:no lines for `%s'\n", bbg_file_name, fn->name);
1578 /* Accumulate the line counts of a file. */
1581 accumulate_line_counts (src)
1585 function_t *fn, *fn_p, *fn_n;
1588 /* Reverse the function order. */
1589 for (fn = src->functions, fn_p = NULL; fn;
1590 fn_p = fn, fn = fn_n)
1592 fn_n = fn->line_next;
1593 fn->line_next = fn_p;
1595 src->functions = fn_p;
1597 for (ix = src->num_lines, line = src->lines; ix--; line++)
1599 if (!flag_all_blocks)
1601 arc_t *arc, *arc_p, *arc_n;
1603 /* Total and reverse the branch information. */
1604 for (arc = line->u.branches, arc_p = NULL; arc;
1605 arc_p = arc, arc = arc_n)
1607 arc_n = arc->line_next;
1608 arc->line_next = arc_p;
1610 add_branch_counts (&src->coverage, arc);
1612 line->u.branches = arc_p;
1614 else if (line->u.blocks)
1616 /* The user expects the line count to be the number of times
1617 a line has been executed. Simply summing the block count
1618 will give an artificially high number. The Right Thing
1619 is to sum the entry counts to the graph of blocks on this
1620 line, then find the elementary cycles of the local graph
1621 and add the transition counts of those cycles. */
1622 block_t *block, *block_p, *block_n;
1623 gcov_type count = 0;
1625 /* Reverse the block information */
1626 for (block = line->u.blocks, block_p = NULL; block;
1627 block_p = block, block = block_n)
1629 block_n = block->chain;
1630 block->chain = block_p;
1631 block->u.cycle.ident = ix;
1633 line->u.blocks = block_p;
1635 /* Sum the entry arcs. */
1636 for (block = line->u.blocks; block; block = block->chain)
1640 for (arc = block->pred; arc; arc = arc->pred_next)
1642 if (arc->src->u.cycle.ident != ix)
1643 count += arc->count;
1645 add_branch_counts (&src->coverage, arc);
1649 /* Find the loops. This uses the algorithm described in
1650 Tiernan 'An Efficient Search Algorithm to Find the
1651 Elementary Circuits of a Graph', CACM Dec 1970. We hold
1652 the P array by having each block point to the arc that
1653 connects to the previous block. The H array is implicitly
1654 held because of the arc ordering, and the block's
1655 previous arc pointer.
1657 Although the algorithm is O(N^3) for highly connected
1658 graphs, at worst we'll have O(N^2), as most blocks have
1659 only one or two exits. Most graphs will be small.
1661 For each loop we find, locate the arc with the smallest
1662 transition count, and add that to the cumulative
1663 count. Remove the arc from consideration. */
1664 for (block = line->u.blocks; block; block = block->chain)
1666 block_t *head = block;
1674 block_t *dst = arc->dst;
1675 if (/* Already used that arc. */
1677 /* Not to same graph, or before first vertex. */
1678 || dst->u.cycle.ident != ix
1679 /* Already in path. */
1680 || dst->u.cycle.arc)
1682 arc = arc->succ_next;
1688 /* Found a closing arc. */
1689 gcov_type cycle_count = arc->count;
1690 arc_t *cycle_arc = arc;
1693 /* Locate the smallest arc count of the loop. */
1694 for (dst = head; (probe_arc = dst->u.cycle.arc);
1695 dst = probe_arc->src)
1696 if (cycle_count > probe_arc->count)
1698 cycle_count = probe_arc->count;
1699 cycle_arc = probe_arc;
1702 count += cycle_count;
1703 cycle_arc->cycle = 1;
1704 /* Unwind to the cyclic arc. */
1705 while (head != cycle_arc->src)
1707 arc = head->u.cycle.arc;
1711 arc = arc->succ_next;
1715 /* Add new block to chain. */
1716 dst->u.cycle.arc = arc;
1720 /* We could not add another vertex to the path. Remove
1721 the last vertex from the list. */
1722 arc = head->u.cycle.arc;
1725 /* It was not the first vertex. Move onto next arc. */
1726 head->u.cycle.arc = NULL;
1728 arc = arc->succ_next;
1729 goto current_vertex;
1731 /* Mark this block as unusable. */
1732 block->u.cycle.ident = ~0U;
1735 line->count = count;
1740 src->coverage.lines++;
1742 src->coverage.lines_executed++;
1747 /* Ouput information about ARC number IX. Returns non-zero if
1748 anything is output. */
1751 output_branch_count (gcov_file, ix, arc)
1757 if (arc->is_call_non_return)
1759 if (arc->src->count)
1761 fnotice (gcov_file, "call %2d returned %s\n", ix,
1762 format_gcov (arc->src->count - arc->count,
1763 arc->src->count, -flag_counts));
1766 fnotice (gcov_file, "call %2d never executed\n", ix);
1768 else if (!arc->is_unconditional)
1770 if (arc->src->count)
1771 fnotice (gcov_file, "branch %2d taken %s%s\n", ix,
1772 format_gcov (arc->count, arc->src->count, -flag_counts),
1773 arc->fall_through ? " (fallthrough)" : "");
1775 fnotice (gcov_file, "branch %2d never executed\n", ix);
1777 else if (flag_unconditional && !arc->dst->is_call_return)
1779 if (arc->src->count)
1780 fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
1781 format_gcov (arc->count, arc->src->count, -flag_counts));
1783 fnotice (gcov_file, "unconditional %2d never executed\n", ix);
1791 /* Read in the source file one line at a time, and output that line to
1792 the gcov file preceded by its execution count and other
1796 output_lines (gcov_file, src)
1798 const source_t *src;
1801 unsigned line_num; /* current line number. */
1802 const line_t *line; /* current line info ptr. */
1803 char string[STRING_SIZE]; /* line buffer. */
1804 char const *retval = ""; /* status of source file reading. */
1805 function_t *fn = src->functions;
1807 fprintf (gcov_file, "%9s:%5d:Source:%s\n", "-", 0, src->name);
1808 fprintf (gcov_file, "%9s:%5d:Graph:%s\n", "-", 0, bbg_file_name);
1809 fprintf (gcov_file, "%9s:%5d:Data:%s\n", "-", 0, da_file_name);
1810 fprintf (gcov_file, "%9s:%5d:Runs:%u\n", "-", 0,
1811 object_summary.ctrs[GCOV_COUNTER_ARCS].runs);
1812 fprintf (gcov_file, "%9s:%5d:Programs:%u\n", "-", 0, program_count);
1814 source_file = fopen (src->name, "r");
1817 fnotice (stderr, "%s:cannot open source file\n", src->name);
1824 if (!fstat (fileno (source_file), &status)
1825 && status.st_mtime > bbg_file_time)
1827 fnotice (stderr, "%s:source file is newer than graph file `%s'\n",
1828 src->name, bbg_file_name);
1829 fprintf (gcov_file, "%9s:%5d:Source is newer than graph\n",
1834 for (line_num = 1, line = &src->lines[line_num];
1835 line_num < src->num_lines; line_num++, line++)
1837 for (; fn && fn->line == line_num; fn = fn->line_next)
1839 arc_t *arc = fn->blocks[fn->num_blocks - 1].pred;
1840 gcov_type return_count = fn->blocks[fn->num_blocks - 1].count;
1842 for (; arc; arc = arc->pred_next)
1844 return_count -= arc->count;
1846 fprintf (gcov_file, "function %s", fn->name);
1847 fprintf (gcov_file, " called %s",
1848 format_gcov (fn->blocks[0].count, 0, -1));
1849 fprintf (gcov_file, " returned %s",
1850 format_gcov (return_count, fn->blocks[0].count, 0));
1851 fprintf (gcov_file, " blocks executed %s",
1852 format_gcov (fn->blocks_executed, fn->num_blocks - 2, 0));
1853 fprintf (gcov_file, "\n");
1856 /* For lines which don't exist in the .bb file, print '-' before
1857 the source line. For lines which exist but were never
1858 executed, print '#####' before the source line. Otherwise,
1859 print the execution count before the source line. There are
1860 16 spaces of indentation added before the source line so that
1861 tabs won't be messed up. */
1862 fprintf (gcov_file, "%9s:%5u:",
1863 !line->exists ? "-" : !line->count ? "#####"
1864 : format_gcov (line->count, 0, -1), line_num);
1868 /* Copy source line. */
1871 retval = fgets (string, STRING_SIZE, source_file);
1874 fputs (retval, gcov_file);
1876 while (!retval[0] || retval[strlen (retval) - 1] != '\n');
1879 fputs ("/*EOF*/\n", gcov_file);
1881 if (flag_all_blocks)
1887 for (ix = jx = 0, block = line->u.blocks; block;
1888 block = block->chain)
1890 if (!block->is_call_return)
1891 fprintf (gcov_file, "%9s:%5u-block %2d\n",
1892 !line->exists ? "-" : !block->count ? "$$$$$"
1893 : format_gcov (block->count, 0, -1),
1896 for (arc = block->succ; arc; arc = arc->succ_next)
1897 jx += output_branch_count (gcov_file, jx, arc);
1900 else if (flag_branches)
1905 for (ix = 0, arc = line->u.branches; arc; arc = arc->line_next)
1906 ix += output_branch_count (gcov_file, ix, arc);
1910 /* Handle all remaining source lines. There may be lines after the
1911 last line of code. */
1914 for (; (retval = fgets (string, STRING_SIZE, source_file)); line_num++)
1916 fprintf (gcov_file, "%9s:%5u:%s", "-", line_num, retval);
1918 while (!retval[0] || retval[strlen (retval) - 1] != '\n')
1920 retval = fgets (string, STRING_SIZE, source_file);
1923 fputs (retval, gcov_file);
1929 fclose (source_file);