1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2013 Free Software Foundation, Inc.
3 Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
4 based on some ideas from Dain Samples of UC Berkeley.
5 Further mangling by Bob Manson, Cygnus Support.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Generate basic block profile instrumentation and auxiliary files.
24 Profile generation is optimized, so that not all arcs in the basic
25 block graph need instrumenting. First, the BB graph is closed with
26 one entry (function start), and one exit (function exit). Any
27 ABNORMAL_EDGE cannot be instrumented (because there is no control
28 path to place the code). We close the graph by inserting fake
29 EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
30 edges that do not go to the exit_block. We ignore such abnormal
31 edges. Naturally these fake edges are never directly traversed,
32 and so *cannot* be directly instrumented. Some other graph
33 massaging is done. To optimize the instrumentation we generate the
34 BB minimal span tree, only edges that are not on the span tree
35 (plus the entry point) need instrumenting. From that information
36 all other edge counts can be deduced. By construction all fake
37 edges must be on the spanning tree. We also attempt to place
38 EDGE_CRITICAL edges on the spanning tree.
40 The auxiliary files generated are <dumpbase>.gcno (at compile time)
41 and <dumpbase>.gcda (at run time). The format is
42 described in full in gcov-io.h. */
44 /* ??? Register allocation should use basic block execution counts to
45 give preference to the most commonly executed blocks. */
47 /* ??? Should calculate branch probabilities before instrumenting code, since
48 then we can use arc counts to help decide which arcs to instrument. */
52 #include "coretypes.h"
59 #include "basic-block.h"
60 #include "diagnostic-core.h"
62 #include "value-prof.h"
71 unsigned int count_valid
: 1;
73 /* Number of successor and predecessor edges. */
78 #define BB_INFO(b) ((struct bb_info *) (b)->aux)
81 /* Counter summary from the last set of coverage counts read. */
83 const struct gcov_ctr_summary
*profile_info
;
85 /* Counter working set information computed from the current counter
86 summary. Not initialized unless profile_info summary is non-NULL. */
87 static gcov_working_set_t gcov_working_sets
[NUM_GCOV_WORKING_SETS
];
89 /* Collect statistics on the performance of this pass for the entire source
92 static int total_num_blocks
;
93 static int total_num_edges
;
94 static int total_num_edges_ignored
;
95 static int total_num_edges_instrumented
;
96 static int total_num_blocks_created
;
97 static int total_num_passes
;
98 static int total_num_times_called
;
99 static int total_hist_br_prob
[20];
100 static int total_num_branches
;
102 /* Forward declarations. */
103 static void find_spanning_tree (struct edge_list
*);
105 /* Add edge instrumentation code to the entire insn chain.
107 F is the first insn of the chain.
108 NUM_BLOCKS is the number of basic blocks found in F. */
111 instrument_edges (struct edge_list
*el
)
113 unsigned num_instr_edges
= 0;
114 int num_edges
= NUM_EDGES (el
);
117 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
122 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
124 struct edge_info
*inf
= EDGE_INFO (e
);
126 if (!inf
->ignore
&& !inf
->on_tree
)
128 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
130 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
131 e
->src
->index
, e
->dest
->index
,
132 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
133 gimple_gen_edge_profiler (num_instr_edges
++, e
);
138 total_num_blocks_created
+= num_edges
;
140 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
141 return num_instr_edges
;
144 /* Add code to measure histograms for values in list VALUES. */
146 instrument_values (histogram_values values
)
150 /* Emit code to generate the histograms before the insns. */
152 for (i
= 0; i
< values
.length (); i
++)
154 histogram_value hist
= values
[i
];
155 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
157 if (!coverage_counter_alloc (t
, hist
->n_counters
))
162 case HIST_TYPE_INTERVAL
:
163 gimple_gen_interval_profiler (hist
, t
, 0);
167 gimple_gen_pow2_profiler (hist
, t
, 0);
170 case HIST_TYPE_SINGLE_VALUE
:
171 gimple_gen_one_value_profiler (hist
, t
, 0);
174 case HIST_TYPE_CONST_DELTA
:
175 gimple_gen_const_delta_profiler (hist
, t
, 0);
178 case HIST_TYPE_INDIR_CALL
:
179 gimple_gen_ic_profiler (hist
, t
, 0);
182 case HIST_TYPE_AVERAGE
:
183 gimple_gen_average_profiler (hist
, t
, 0);
187 gimple_gen_ior_profiler (hist
, t
, 0);
197 /* Fill the working set information into the profile_info structure. */
200 get_working_sets (void)
202 unsigned ws_ix
, pctinc
, pct
;
203 gcov_working_set_t
*ws_info
;
208 compute_working_sets (profile_info
, gcov_working_sets
);
212 fprintf (dump_file
, "Counter working sets:\n");
213 /* Multiply the percentage by 100 to avoid float. */
214 pctinc
= 100 * 100 / NUM_GCOV_WORKING_SETS
;
215 for (ws_ix
= 0, pct
= pctinc
; ws_ix
< NUM_GCOV_WORKING_SETS
;
216 ws_ix
++, pct
+= pctinc
)
218 if (ws_ix
== NUM_GCOV_WORKING_SETS
- 1)
220 ws_info
= &gcov_working_sets
[ws_ix
];
221 /* Print out the percentage using int arithmatic to avoid float. */
222 fprintf (dump_file
, "\t\t%u.%02u%%: num counts=%u, min counter="
223 HOST_WIDEST_INT_PRINT_DEC
"\n",
224 pct
/ 100, pct
- (pct
/ 100 * 100),
225 ws_info
->num_counters
,
226 (HOST_WIDEST_INT
)ws_info
->min_counter
);
231 /* Given a the desired percentage of the full profile (sum_all from the
232 summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns
233 the corresponding working set information. If an exact match for
234 the percentage isn't found, the closest value is used. */
237 find_working_set (unsigned pct_times_10
)
242 gcc_assert (pct_times_10
<= 1000);
243 if (pct_times_10
>= 999)
244 return &gcov_working_sets
[NUM_GCOV_WORKING_SETS
- 1];
245 i
= pct_times_10
* NUM_GCOV_WORKING_SETS
/ 1000;
247 return &gcov_working_sets
[0];
248 return &gcov_working_sets
[i
- 1];
251 /* Computes hybrid profile for all matching entries in da_file.
253 CFG_CHECKSUM is the precomputed checksum for the CFG. */
256 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
258 unsigned num_edges
= 0;
262 /* Count the edges to be (possibly) instrumented. */
263 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
268 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
269 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
273 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, num_edges
, cfg_checksum
,
274 lineno_checksum
, &profile_info
);
280 if (dump_file
&& profile_info
)
281 fprintf (dump_file
, "Merged %u profiles with maximal count %u.\n",
282 profile_info
->runs
, (unsigned) profile_info
->sum_max
);
289 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
293 FOR_EACH_EDGE (e
, ei
, edges
)
295 if (!EDGE_INFO (e
)->ignore
)
298 && (!(e
->flags
& EDGE_FAKE
)
299 || !block_ends_with_call_p (e
->src
)))
304 "Edge %i->%i is inconsistent, count"HOST_WIDEST_INT_PRINT_DEC
,
305 e
->src
->index
, e
->dest
->index
, e
->count
);
306 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
307 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
317 correct_negative_edge_counts (void)
323 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
325 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
333 /* Check consistency.
334 Return true if inconsistency is found. */
336 is_inconsistent (void)
339 bool inconsistent
= false;
342 inconsistent
|= is_edge_inconsistent (bb
->preds
);
343 if (!dump_file
&& inconsistent
)
345 inconsistent
|= is_edge_inconsistent (bb
->succs
);
346 if (!dump_file
&& inconsistent
)
352 fprintf (dump_file
, "BB %i count is negative "
353 HOST_WIDEST_INT_PRINT_DEC
,
356 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
360 if (bb
->count
!= sum_edge_counts (bb
->preds
))
364 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
365 HOST_WIDEST_INT_PRINT_DEC
" should be " HOST_WIDEST_INT_PRINT_DEC
,
368 sum_edge_counts (bb
->preds
));
369 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
373 if (bb
->count
!= sum_edge_counts (bb
->succs
) &&
374 ! (find_edge (bb
, EXIT_BLOCK_PTR
) != NULL
&& block_ends_with_call_p (bb
)))
378 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
379 HOST_WIDEST_INT_PRINT_DEC
" should be " HOST_WIDEST_INT_PRINT_DEC
,
382 sum_edge_counts (bb
->succs
));
383 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
387 if (!dump_file
&& inconsistent
)
394 /* Set each basic block count to the sum of its outgoing edge counts */
399 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
401 bb
->count
= sum_edge_counts (bb
->succs
);
402 gcc_assert (bb
->count
>= 0);
406 /* Reads profile data and returns total number of edge counts read */
408 read_profile_edge_counts (gcov_type
*exec_counts
)
412 int exec_counts_pos
= 0;
413 /* For each edge not on the spanning tree, set its execution count from
415 /* The first count in the .da file is the number of times that the function
416 was entered. This is the exec_count for block zero. */
418 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
423 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
424 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
429 e
->count
= exec_counts
[exec_counts_pos
++];
430 if (e
->count
> profile_info
->sum_max
)
432 if (flag_profile_correction
)
434 static bool informed
= 0;
435 if (dump_enabled_p () && !informed
)
436 dump_printf_loc (MSG_NOTE
, input_location
,
437 "corrupted profile info: edge count"
438 " exceeds maximal count\n");
442 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
443 bb
->index
, e
->dest
->index
);
449 EDGE_INFO (e
)->count_valid
= 1;
450 BB_INFO (bb
)->succ_count
--;
451 BB_INFO (e
->dest
)->pred_count
--;
454 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
455 bb
->index
, e
->dest
->index
);
456 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
457 (HOST_WIDEST_INT
) e
->count
);
465 #define OVERLAP_BASE 10000
467 /* Compare the static estimated profile to the actual profile, and
468 return the "degree of overlap" measure between them.
470 Degree of overlap is a number between 0 and OVERLAP_BASE. It is
471 the sum of each basic block's minimum relative weights between
472 two profiles. And overlap of OVERLAP_BASE means two profiles are
476 compute_frequency_overlap (void)
478 gcov_type count_total
= 0, freq_total
= 0;
482 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
484 count_total
+= bb
->count
;
485 freq_total
+= bb
->frequency
;
488 if (count_total
== 0 || freq_total
== 0)
491 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
492 overlap
+= MIN (bb
->count
* OVERLAP_BASE
/ count_total
,
493 bb
->frequency
* OVERLAP_BASE
/ freq_total
);
498 /* Compute the branch probabilities for the various branches.
499 Annotate them accordingly.
501 CFG_CHECKSUM is the precomputed checksum for the CFG. */
504 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
511 int hist_br_prob
[20];
513 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
514 int inconsistent
= 0;
516 /* Very simple sanity checks so we catch bugs in our profiling code. */
519 if (profile_info
->run_max
* profile_info
->runs
< profile_info
->sum_max
)
521 error ("corrupted profile info: run_max * runs < sum_max");
525 if (profile_info
->sum_all
< profile_info
->sum_max
)
527 error ("corrupted profile info: sum_all is smaller than sum_max");
531 /* Attach extra info block to each bb. */
532 alloc_aux_for_blocks (sizeof (struct bb_info
));
533 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
538 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
539 if (!EDGE_INFO (e
)->ignore
)
540 BB_INFO (bb
)->succ_count
++;
541 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
542 if (!EDGE_INFO (e
)->ignore
)
543 BB_INFO (bb
)->pred_count
++;
546 /* Avoid predicting entry on exit nodes. */
547 BB_INFO (EXIT_BLOCK_PTR
)->succ_count
= 2;
548 BB_INFO (ENTRY_BLOCK_PTR
)->pred_count
= 2;
550 num_edges
= read_profile_edge_counts (exec_counts
);
553 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
555 /* For every block in the file,
556 - if every exit/entrance edge has a known count, then set the block count
557 - if the block count is known, and every exit/entrance edge but one has
558 a known execution count, then set the count of the remaining edge
560 As edge counts are set, decrement the succ/pred count, but don't delete
561 the edge, that way we can easily tell when all edges are known, or only
562 one edge is unknown. */
564 /* The order that the basic blocks are iterated through is important.
565 Since the code that finds spanning trees starts with block 0, low numbered
566 edges are put on the spanning tree in preference to high numbered edges.
567 Hence, most instrumented edges are at the end. Graph solving works much
568 faster if we propagate numbers from the end to the start.
570 This takes an average of slightly more than 3 passes. */
578 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR
, NULL
, prev_bb
)
580 struct bb_info
*bi
= BB_INFO (bb
);
581 if (! bi
->count_valid
)
583 if (bi
->succ_count
== 0)
589 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
595 else if (bi
->pred_count
== 0)
601 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
610 if (bi
->succ_count
== 1)
616 /* One of the counts will be invalid, but it is zero,
617 so adding it in also doesn't hurt. */
618 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
621 /* Search for the invalid edge, and set its count. */
622 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
623 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
626 /* Calculate count for remaining edge by conservation. */
627 total
= bb
->count
- total
;
630 EDGE_INFO (e
)->count_valid
= 1;
634 BB_INFO (e
->dest
)->pred_count
--;
637 if (bi
->pred_count
== 1)
643 /* One of the counts will be invalid, but it is zero,
644 so adding it in also doesn't hurt. */
645 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
648 /* Search for the invalid edge, and set its count. */
649 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
650 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
653 /* Calculate count for remaining edge by conservation. */
654 total
= bb
->count
- total
+ e
->count
;
657 EDGE_INFO (e
)->count_valid
= 1;
661 BB_INFO (e
->src
)->succ_count
--;
669 int overlap
= compute_frequency_overlap ();
670 gimple_dump_cfg (dump_file
, dump_flags
);
671 fprintf (dump_file
, "Static profile overlap: %d.%d%%\n",
672 overlap
/ (OVERLAP_BASE
/ 100),
673 overlap
% (OVERLAP_BASE
/ 100));
676 total_num_passes
+= passes
;
678 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
680 /* If the graph has been correctly solved, every block will have a
681 succ and pred count of zero. */
684 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
687 /* Check for inconsistent basic block counts */
688 inconsistent
= is_inconsistent ();
692 if (flag_profile_correction
)
694 /* Inconsistency detected. Make it flow-consistent. */
695 static int informed
= 0;
696 if (dump_enabled_p () && informed
== 0)
699 dump_printf_loc (MSG_NOTE
, input_location
,
700 "correcting inconsistent profile data\n");
702 correct_negative_edge_counts ();
703 /* Set bb counts to the sum of the outgoing edge counts */
706 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
710 error ("corrupted profile info: profile data is not flow-consistent");
713 /* For every edge, calculate its branch probability and add a reg_note
714 to the branch insn to indicate this. */
716 for (i
= 0; i
< 20; i
++)
720 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
727 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
728 bb
->index
, (int)bb
->count
);
731 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
733 /* Function may return twice in the cased the called function is
734 setjmp or calls fork, but we can't represent this by extra
735 edge from the entry, since extra edge from the exit is
736 already present. We get negative frequency from the entry
739 && e
->dest
== EXIT_BLOCK_PTR
)
740 || (e
->count
> bb
->count
741 && e
->dest
!= EXIT_BLOCK_PTR
))
743 if (block_ends_with_call_p (bb
))
744 e
->count
= e
->count
< 0 ? 0 : bb
->count
;
746 if (e
->count
< 0 || e
->count
> bb
->count
)
748 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
749 e
->src
->index
, e
->dest
->index
,
751 e
->count
= bb
->count
/ 2;
756 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
757 e
->probability
= GCOV_COMPUTE_SCALE (e
->count
, bb
->count
);
758 if (bb
->index
>= NUM_FIXED_BLOCKS
759 && block_ends_with_condjump_p (bb
)
760 && EDGE_COUNT (bb
->succs
) >= 2)
766 /* Find the branch edge. It is possible that we do have fake
768 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
769 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
772 prob
= e
->probability
;
773 index
= prob
* 20 / REG_BR_PROB_BASE
;
777 hist_br_prob
[index
]++;
782 /* As a last resort, distribute the probabilities evenly.
783 Use simple heuristics that if there are normal edges,
784 give all abnormals frequency of 0, otherwise distribute the
785 frequency over abnormals (this is the case of noreturn
787 else if (profile_status
== PROFILE_ABSENT
)
791 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
792 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
796 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
797 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
798 e
->probability
= REG_BR_PROB_BASE
/ total
;
804 total
+= EDGE_COUNT (bb
->succs
);
805 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
806 e
->probability
= REG_BR_PROB_BASE
/ total
;
808 if (bb
->index
>= NUM_FIXED_BLOCKS
809 && block_ends_with_condjump_p (bb
)
810 && EDGE_COUNT (bb
->succs
) >= 2)
815 profile_status
= PROFILE_READ
;
816 compute_function_frequency ();
820 fprintf (dump_file
, "%d branches\n", num_branches
);
822 for (i
= 0; i
< 10; i
++)
823 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
824 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
827 total_num_branches
+= num_branches
;
828 for (i
= 0; i
< 20; i
++)
829 total_hist_br_prob
[i
] += hist_br_prob
[i
];
831 fputc ('\n', dump_file
);
832 fputc ('\n', dump_file
);
835 free_aux_for_blocks ();
838 /* Load value histograms values whose description is stored in VALUES array
841 CFG_CHECKSUM is the precomputed checksum for the CFG. */
844 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
845 unsigned lineno_checksum
)
847 unsigned i
, j
, t
, any
;
848 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
849 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
850 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
851 gcov_type
*aact_count
;
853 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
854 n_histogram_counters
[t
] = 0;
856 for (i
= 0; i
< values
.length (); i
++)
858 histogram_value hist
= values
[i
];
859 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
863 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
865 if (!n_histogram_counters
[t
])
867 histogram_counts
[t
] = NULL
;
871 histogram_counts
[t
] =
872 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
873 n_histogram_counters
[t
], cfg_checksum
,
874 lineno_checksum
, NULL
);
875 if (histogram_counts
[t
])
877 act_count
[t
] = histogram_counts
[t
];
882 for (i
= 0; i
< values
.length (); i
++)
884 histogram_value hist
= values
[i
];
885 gimple stmt
= hist
->hvalue
.stmt
;
887 t
= (int) hist
->type
;
889 aact_count
= act_count
[t
];
891 act_count
[t
] += hist
->n_counters
;
893 gimple_add_histogram_value (cfun
, stmt
, hist
);
894 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
895 for (j
= 0; j
< hist
->n_counters
; j
++)
897 hist
->hvalue
.counters
[j
] = aact_count
[j
];
899 hist
->hvalue
.counters
[j
] = 0;
902 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
903 free (histogram_counts
[t
]);
906 /* When passed NULL as file_name, initialize.
907 When passed something else, output the necessary commands to change
908 line to LINE and offset to FILE_NAME. */
910 output_location (char const *file_name
, int line
,
911 gcov_position_t
*offset
, basic_block bb
)
913 static char const *prev_file_name
;
914 static int prev_line
;
915 bool name_differs
, line_differs
;
919 prev_file_name
= NULL
;
924 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
925 line_differs
= prev_line
!= line
;
927 if (name_differs
|| line_differs
)
931 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
932 gcov_write_unsigned (bb
->index
);
933 name_differs
= line_differs
=true;
936 /* If this is a new source file, then output the
937 file's name to the .bb file. */
940 prev_file_name
= file_name
;
941 gcov_write_unsigned (0);
942 gcov_write_string (prev_file_name
);
946 gcov_write_unsigned (line
);
952 /* Instrument and/or analyze program behavior based on program the CFG.
954 This function creates a representation of the control flow graph (of
955 the function being compiled) that is suitable for the instrumentation
956 of edges and/or converting measured edge counts to counts on the
959 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
960 the flow graph that are needed to reconstruct the dynamic behavior of the
961 flow graph. This data is written to the gcno file for gcov.
963 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
964 information from the gcda file containing edge count information from
965 previous executions of the function being compiled. In this case, the
966 control flow graph is annotated with actual execution counts by
967 compute_branch_probabilities().
969 Main entry point of this file. */
976 unsigned num_edges
, ignored_edges
;
977 unsigned num_instrumented
;
978 struct edge_list
*el
;
979 histogram_values values
= histogram_values ();
980 unsigned cfg_checksum
, lineno_checksum
;
982 total_num_times_called
++;
984 flow_call_edges_add (NULL
);
985 add_noreturn_fake_exit_edges ();
987 /* We can't handle cyclic regions constructed using abnormal edges.
988 To avoid these we replace every source of abnormal edge by a fake
989 edge from entry node and every destination by fake edge to exit.
990 This keeps graph acyclic and our calculation exact for all normal
991 edges except for exit and entrance ones.
993 We also add fake exit edges for each call and asm statement in the
994 basic, since it may not return. */
998 int need_exit_edge
= 0, need_entry_edge
= 0;
999 int have_exit_edge
= 0, have_entry_edge
= 0;
1003 /* Functions returning multiple times are not handled by extra edges.
1004 Instead we simply allow negative counts on edges from exit to the
1005 block past call and corresponding probabilities. We can't go
1006 with the extra edges because that would result in flowgraph that
1007 needs to have fake edges outside the spanning tree. */
1009 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1011 gimple_stmt_iterator gsi
;
1014 /* It may happen that there are compiler generated statements
1015 without a locus at all. Go through the basic block from the
1016 last to the first statement looking for a locus. */
1017 for (gsi
= gsi_last_nondebug_bb (bb
);
1019 gsi_prev_nondebug (&gsi
))
1021 last
= gsi_stmt (gsi
);
1022 if (gimple_has_location (last
))
1026 /* Edge with goto locus might get wrong coverage info unless
1027 it is the only edge out of BB.
1028 Don't do that when the locuses match, so
1029 if (blah) goto something;
1030 is not computed twice. */
1032 && gimple_has_location (last
)
1033 && LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
1034 && !single_succ_p (bb
)
1035 && (LOCATION_FILE (e
->goto_locus
)
1036 != LOCATION_FILE (gimple_location (last
))
1037 || (LOCATION_LINE (e
->goto_locus
)
1038 != LOCATION_LINE (gimple_location (last
)))))
1040 basic_block new_bb
= split_edge (e
);
1041 edge ne
= single_succ_edge (new_bb
);
1042 ne
->goto_locus
= e
->goto_locus
;
1044 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1045 && e
->dest
!= EXIT_BLOCK_PTR
)
1047 if (e
->dest
== EXIT_BLOCK_PTR
)
1050 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1052 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1053 && e
->src
!= ENTRY_BLOCK_PTR
)
1054 need_entry_edge
= 1;
1055 if (e
->src
== ENTRY_BLOCK_PTR
)
1056 have_entry_edge
= 1;
1059 if (need_exit_edge
&& !have_exit_edge
)
1062 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1064 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
1066 if (need_entry_edge
&& !have_entry_edge
)
1069 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1071 make_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FAKE
);
1072 /* Avoid bbs that have both fake entry edge and also some
1073 exit edge. One of those edges wouldn't be added to the
1074 spanning tree, but we can't instrument any of them. */
1075 if (have_exit_edge
|| need_exit_edge
)
1077 gimple_stmt_iterator gsi
;
1081 gsi
= gsi_after_labels (bb
);
1082 gcc_checking_assert (!gsi_end_p (gsi
));
1083 first
= gsi_stmt (gsi
);
1084 if (is_gimple_debug (first
))
1086 gsi_next_nondebug (&gsi
);
1087 gcc_checking_assert (!gsi_end_p (gsi
));
1088 first
= gsi_stmt (gsi
);
1090 /* Don't split the bbs containing __builtin_setjmp_receiver
1091 or __builtin_setjmp_dispatcher calls. These are very
1092 special and don't expect anything to be inserted before
1094 if (is_gimple_call (first
)
1095 && (((fndecl
= gimple_call_fndecl (first
)) != NULL
1096 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1097 && (DECL_FUNCTION_CODE (fndecl
)
1098 == BUILT_IN_SETJMP_RECEIVER
1099 || (DECL_FUNCTION_CODE (fndecl
)
1100 == BUILT_IN_SETJMP_DISPATCHER
)))
1101 || gimple_call_flags (first
) & ECF_RETURNS_TWICE
))
1105 fprintf (dump_file
, "Splitting bb %i after labels\n",
1107 split_block_after_labels (bb
);
1112 el
= create_edge_list ();
1113 num_edges
= NUM_EDGES (el
);
1114 alloc_aux_for_edges (sizeof (struct edge_info
));
1116 /* The basic blocks are expected to be numbered sequentially. */
1120 for (i
= 0 ; i
< num_edges
; i
++)
1122 edge e
= INDEX_EDGE (el
, i
);
1125 /* Mark edges we've replaced by fake edges above as ignored. */
1126 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1127 && e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
)
1129 EDGE_INFO (e
)->ignore
= 1;
1134 /* Create spanning tree from basic block graph, mark each edge that is
1135 on the spanning tree. We insert as many abnormal and critical edges
1136 as possible to minimize number of edge splits necessary. */
1138 find_spanning_tree (el
);
1140 /* Fake edges that are not on the tree will not be instrumented, so
1141 mark them ignored. */
1142 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1144 edge e
= INDEX_EDGE (el
, i
);
1145 struct edge_info
*inf
= EDGE_INFO (e
);
1147 if (inf
->ignore
|| inf
->on_tree
)
1149 else if (e
->flags
& EDGE_FAKE
)
1158 total_num_blocks
+= n_basic_blocks
;
1160 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks
);
1162 total_num_edges
+= num_edges
;
1164 fprintf (dump_file
, "%d edges\n", num_edges
);
1166 total_num_edges_ignored
+= ignored_edges
;
1168 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1170 total_num_edges_instrumented
+= num_instrumented
;
1172 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1174 /* Compute two different checksums. Note that we want to compute
1175 the checksum in only once place, since it depends on the shape
1176 of the control flow which can change during
1177 various transformations. */
1178 cfg_checksum
= coverage_compute_cfg_checksum ();
1179 lineno_checksum
= coverage_compute_lineno_checksum ();
1181 /* Write the data from which gcov can reconstruct the basic block
1182 graph and function line numbers (the gcno file). */
1183 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1185 gcov_position_t offset
;
1187 /* Basic block flags */
1188 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1189 for (i
= 0; i
!= (unsigned) (n_basic_blocks
); i
++)
1190 gcov_write_unsigned (0);
1191 gcov_write_length (offset
);
1194 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1199 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1200 gcov_write_unsigned (bb
->index
);
1202 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1204 struct edge_info
*i
= EDGE_INFO (e
);
1207 unsigned flag_bits
= 0;
1210 flag_bits
|= GCOV_ARC_ON_TREE
;
1211 if (e
->flags
& EDGE_FAKE
)
1212 flag_bits
|= GCOV_ARC_FAKE
;
1213 if (e
->flags
& EDGE_FALLTHRU
)
1214 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1215 /* On trees we don't have fallthru flags, but we can
1216 recompute them from CFG shape. */
1217 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1218 && e
->src
->next_bb
== e
->dest
)
1219 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1221 gcov_write_unsigned (e
->dest
->index
);
1222 gcov_write_unsigned (flag_bits
);
1226 gcov_write_length (offset
);
1230 /* Initialize the output. */
1231 output_location (NULL
, 0, NULL
, NULL
);
1235 gimple_stmt_iterator gsi
;
1236 gcov_position_t offset
= 0;
1238 if (bb
== ENTRY_BLOCK_PTR
->next_bb
)
1240 expanded_location curr_location
=
1241 expand_location (DECL_SOURCE_LOCATION (current_function_decl
));
1242 output_location (curr_location
.file
, curr_location
.line
,
1246 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1248 gimple stmt
= gsi_stmt (gsi
);
1249 if (gimple_has_location (stmt
))
1250 output_location (gimple_filename (stmt
), gimple_lineno (stmt
),
1254 /* Notice GOTO expressions eliminated while constructing the CFG. */
1255 if (single_succ_p (bb
)
1256 && LOCATION_LOCUS (single_succ_edge (bb
)->goto_locus
)
1257 != UNKNOWN_LOCATION
)
1259 expanded_location curr_location
1260 = expand_location (single_succ_edge (bb
)->goto_locus
);
1261 output_location (curr_location
.file
, curr_location
.line
,
1267 /* A file of NULL indicates the end of run. */
1268 gcov_write_unsigned (0);
1269 gcov_write_string (NULL
);
1270 gcov_write_length (offset
);
1275 if (flag_profile_values
)
1276 gimple_find_values_to_profile (&values
);
1278 if (flag_branch_probabilities
)
1280 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1281 if (flag_profile_values
)
1282 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1285 remove_fake_edges ();
1287 /* For each edge not on the spanning tree, add counting code. */
1288 if (profile_arc_flag
1289 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1291 unsigned n_instrumented
;
1293 gimple_init_edge_profiler ();
1295 n_instrumented
= instrument_edges (el
);
1297 gcc_assert (n_instrumented
== num_instrumented
);
1299 if (flag_profile_values
)
1300 instrument_values (values
);
1302 /* Commit changes done by instrumentation. */
1303 gsi_commit_edge_inserts ();
1306 free_aux_for_edges ();
1309 free_edge_list (el
);
1310 coverage_end_function (lineno_checksum
, cfg_checksum
);
1313 /* Union find algorithm implementation for the basic blocks using
1317 find_group (basic_block bb
)
1319 basic_block group
= bb
, bb1
;
1321 while ((basic_block
) group
->aux
!= group
)
1322 group
= (basic_block
) group
->aux
;
1324 /* Compress path. */
1325 while ((basic_block
) bb
->aux
!= group
)
1327 bb1
= (basic_block
) bb
->aux
;
1328 bb
->aux
= (void *) group
;
1335 union_groups (basic_block bb1
, basic_block bb2
)
1337 basic_block bb1g
= find_group (bb1
);
1338 basic_block bb2g
= find_group (bb2
);
1340 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1341 this code is unlikely going to be performance problem anyway. */
1342 gcc_assert (bb1g
!= bb2g
);
1347 /* This function searches all of the edges in the program flow graph, and puts
1348 as many bad edges as possible onto the spanning tree. Bad edges include
1349 abnormals edges, which can't be instrumented at the moment. Since it is
1350 possible for fake edges to form a cycle, we will have to develop some
1351 better way in the future. Also put critical edges to the tree, since they
1352 are more expensive to instrument. */
1355 find_spanning_tree (struct edge_list
*el
)
1358 int num_edges
= NUM_EDGES (el
);
1361 /* We use aux field for standard union-find algorithm. */
1362 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1365 /* Add fake edge exit to entry we can't instrument. */
1366 union_groups (EXIT_BLOCK_PTR
, ENTRY_BLOCK_PTR
);
1368 /* First add all abnormal edges to the tree unless they form a cycle. Also
1369 add all edges to EXIT_BLOCK_PTR to avoid inserting profiling code behind
1370 setting return value from function. */
1371 for (i
= 0; i
< num_edges
; i
++)
1373 edge e
= INDEX_EDGE (el
, i
);
1374 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1375 || e
->dest
== EXIT_BLOCK_PTR
)
1376 && !EDGE_INFO (e
)->ignore
1377 && (find_group (e
->src
) != find_group (e
->dest
)))
1380 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1381 e
->src
->index
, e
->dest
->index
);
1382 EDGE_INFO (e
)->on_tree
= 1;
1383 union_groups (e
->src
, e
->dest
);
1387 /* Now insert all critical edges to the tree unless they form a cycle. */
1388 for (i
= 0; i
< num_edges
; i
++)
1390 edge e
= INDEX_EDGE (el
, i
);
1391 if (EDGE_CRITICAL_P (e
) && !EDGE_INFO (e
)->ignore
1392 && find_group (e
->src
) != find_group (e
->dest
))
1395 fprintf (dump_file
, "Critical edge %d to %d put to tree\n",
1396 e
->src
->index
, e
->dest
->index
);
1397 EDGE_INFO (e
)->on_tree
= 1;
1398 union_groups (e
->src
, e
->dest
);
1402 /* And now the rest. */
1403 for (i
= 0; i
< num_edges
; i
++)
1405 edge e
= INDEX_EDGE (el
, i
);
1406 if (!EDGE_INFO (e
)->ignore
1407 && find_group (e
->src
) != find_group (e
->dest
))
1410 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1411 e
->src
->index
, e
->dest
->index
);
1412 EDGE_INFO (e
)->on_tree
= 1;
1413 union_groups (e
->src
, e
->dest
);
1417 clear_aux_for_blocks ();
1420 /* Perform file-level initialization for branch-prob processing. */
1423 init_branch_prob (void)
1427 total_num_blocks
= 0;
1428 total_num_edges
= 0;
1429 total_num_edges_ignored
= 0;
1430 total_num_edges_instrumented
= 0;
1431 total_num_blocks_created
= 0;
1432 total_num_passes
= 0;
1433 total_num_times_called
= 0;
1434 total_num_branches
= 0;
1435 for (i
= 0; i
< 20; i
++)
1436 total_hist_br_prob
[i
] = 0;
1439 /* Performs file-level cleanup after branch-prob processing
1443 end_branch_prob (void)
1447 fprintf (dump_file
, "\n");
1448 fprintf (dump_file
, "Total number of blocks: %d\n",
1450 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1451 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1452 total_num_edges_ignored
);
1453 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1454 total_num_edges_instrumented
);
1455 fprintf (dump_file
, "Total number of blocks created: %d\n",
1456 total_num_blocks_created
);
1457 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1459 if (total_num_times_called
!= 0)
1460 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1461 (total_num_passes
+ (total_num_times_called
>> 1))
1462 / total_num_times_called
);
1463 fprintf (dump_file
, "Total number of branches: %d\n",
1464 total_num_branches
);
1465 if (total_num_branches
)
1469 for (i
= 0; i
< 10; i
++)
1470 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1471 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1472 / total_num_branches
, 5*i
, 5*i
+5);