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