1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2015 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"
58 #include "hard-reg-set.h"
63 #include "insn-config.h"
73 #include "dominance.h"
76 #include "basic-block.h"
77 #include "diagnostic-core.h"
79 #include "value-prof.h"
80 #include "fold-const.h"
81 #include "tree-ssa-alias.h"
82 #include "internal-fn.h"
83 #include "gimple-expr.h"
86 #include "gimple-iterator.h"
90 #include "plugin-api.h"
96 struct bb_profile_info
{
97 unsigned int count_valid
: 1;
99 /* Number of successor and predecessor edges. */
100 gcov_type succ_count
;
101 gcov_type pred_count
;
104 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
107 /* Counter summary from the last set of coverage counts read. */
109 const struct gcov_ctr_summary
*profile_info
;
111 /* Counter working set information computed from the current counter
112 summary. Not initialized unless profile_info summary is non-NULL. */
113 static gcov_working_set_t gcov_working_sets
[NUM_GCOV_WORKING_SETS
];
115 /* Collect statistics on the performance of this pass for the entire source
118 static int total_num_blocks
;
119 static int total_num_edges
;
120 static int total_num_edges_ignored
;
121 static int total_num_edges_instrumented
;
122 static int total_num_blocks_created
;
123 static int total_num_passes
;
124 static int total_num_times_called
;
125 static int total_hist_br_prob
[20];
126 static int total_num_branches
;
128 /* Helper function to update gcov_working_sets. */
130 void add_working_set (gcov_working_set_t
*set
) {
132 for (; i
< NUM_GCOV_WORKING_SETS
; i
++)
133 gcov_working_sets
[i
] = set
[i
];
136 /* Forward declarations. */
137 static void find_spanning_tree (struct edge_list
*);
139 /* Add edge instrumentation code to the entire insn chain.
141 F is the first insn of the chain.
142 NUM_BLOCKS is the number of basic blocks found in F. */
145 instrument_edges (struct edge_list
*el
)
147 unsigned num_instr_edges
= 0;
148 int num_edges
= NUM_EDGES (el
);
151 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
156 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
158 struct edge_profile_info
*inf
= EDGE_INFO (e
);
160 if (!inf
->ignore
&& !inf
->on_tree
)
162 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
164 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
165 e
->src
->index
, e
->dest
->index
,
166 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
167 gimple_gen_edge_profiler (num_instr_edges
++, e
);
172 total_num_blocks_created
+= num_edges
;
174 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
175 return num_instr_edges
;
178 /* Add code to measure histograms for values in list VALUES. */
180 instrument_values (histogram_values values
)
184 /* Emit code to generate the histograms before the insns. */
186 for (i
= 0; i
< values
.length (); i
++)
188 histogram_value hist
= values
[i
];
189 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
191 if (!coverage_counter_alloc (t
, hist
->n_counters
))
196 case HIST_TYPE_INTERVAL
:
197 gimple_gen_interval_profiler (hist
, t
, 0);
201 gimple_gen_pow2_profiler (hist
, t
, 0);
204 case HIST_TYPE_SINGLE_VALUE
:
205 gimple_gen_one_value_profiler (hist
, t
, 0);
208 case HIST_TYPE_CONST_DELTA
:
209 gimple_gen_const_delta_profiler (hist
, t
, 0);
212 case HIST_TYPE_INDIR_CALL
:
213 case HIST_TYPE_INDIR_CALL_TOPN
:
214 gimple_gen_ic_profiler (hist
, t
, 0);
217 case HIST_TYPE_AVERAGE
:
218 gimple_gen_average_profiler (hist
, t
, 0);
222 gimple_gen_ior_profiler (hist
, t
, 0);
225 case HIST_TYPE_TIME_PROFILE
:
228 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
229 gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
231 gimple_gen_time_profiler (t
, 0, gsi
);
242 /* Fill the working set information into the profile_info structure. */
245 get_working_sets (void)
247 unsigned ws_ix
, pctinc
, pct
;
248 gcov_working_set_t
*ws_info
;
253 compute_working_sets (profile_info
, gcov_working_sets
);
257 fprintf (dump_file
, "Counter working sets:\n");
258 /* Multiply the percentage by 100 to avoid float. */
259 pctinc
= 100 * 100 / NUM_GCOV_WORKING_SETS
;
260 for (ws_ix
= 0, pct
= pctinc
; ws_ix
< NUM_GCOV_WORKING_SETS
;
261 ws_ix
++, pct
+= pctinc
)
263 if (ws_ix
== NUM_GCOV_WORKING_SETS
- 1)
265 ws_info
= &gcov_working_sets
[ws_ix
];
266 /* Print out the percentage using int arithmatic to avoid float. */
267 fprintf (dump_file
, "\t\t%u.%02u%%: num counts=%u, min counter="
269 pct
/ 100, pct
- (pct
/ 100 * 100),
270 ws_info
->num_counters
,
271 (int64_t)ws_info
->min_counter
);
276 /* Given a the desired percentage of the full profile (sum_all from the
277 summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns
278 the corresponding working set information. If an exact match for
279 the percentage isn't found, the closest value is used. */
282 find_working_set (unsigned pct_times_10
)
287 gcc_assert (pct_times_10
<= 1000);
288 if (pct_times_10
>= 999)
289 return &gcov_working_sets
[NUM_GCOV_WORKING_SETS
- 1];
290 i
= pct_times_10
* NUM_GCOV_WORKING_SETS
/ 1000;
292 return &gcov_working_sets
[0];
293 return &gcov_working_sets
[i
- 1];
296 /* Computes hybrid profile for all matching entries in da_file.
298 CFG_CHECKSUM is the precomputed checksum for the CFG. */
301 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
303 unsigned num_edges
= 0;
307 /* Count the edges to be (possibly) instrumented. */
308 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
313 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
314 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
318 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, num_edges
, cfg_checksum
,
319 lineno_checksum
, &profile_info
);
325 if (dump_file
&& profile_info
)
326 fprintf (dump_file
, "Merged %u profiles with maximal count %u.\n",
327 profile_info
->runs
, (unsigned) profile_info
->sum_max
);
334 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
338 FOR_EACH_EDGE (e
, ei
, edges
)
340 if (!EDGE_INFO (e
)->ignore
)
343 && (!(e
->flags
& EDGE_FAKE
)
344 || !block_ends_with_call_p (e
->src
)))
349 "Edge %i->%i is inconsistent, count%" PRId64
,
350 e
->src
->index
, e
->dest
->index
, e
->count
);
351 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
352 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
362 correct_negative_edge_counts (void)
368 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
370 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
378 /* Check consistency.
379 Return true if inconsistency is found. */
381 is_inconsistent (void)
384 bool inconsistent
= false;
385 FOR_EACH_BB_FN (bb
, cfun
)
387 inconsistent
|= is_edge_inconsistent (bb
->preds
);
388 if (!dump_file
&& inconsistent
)
390 inconsistent
|= is_edge_inconsistent (bb
->succs
);
391 if (!dump_file
&& inconsistent
)
397 fprintf (dump_file
, "BB %i count is negative "
401 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
405 if (bb
->count
!= sum_edge_counts (bb
->preds
))
409 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
410 "%" PRId64
" should be %" PRId64
,
413 sum_edge_counts (bb
->preds
));
414 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
418 if (bb
->count
!= sum_edge_counts (bb
->succs
) &&
419 ! (find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
)) != NULL
420 && block_ends_with_call_p (bb
)))
424 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
425 "%" PRId64
" should be %" PRId64
,
428 sum_edge_counts (bb
->succs
));
429 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
433 if (!dump_file
&& inconsistent
)
440 /* Set each basic block count to the sum of its outgoing edge counts */
445 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
447 bb
->count
= sum_edge_counts (bb
->succs
);
448 gcc_assert (bb
->count
>= 0);
452 /* Reads profile data and returns total number of edge counts read */
454 read_profile_edge_counts (gcov_type
*exec_counts
)
458 int exec_counts_pos
= 0;
459 /* For each edge not on the spanning tree, set its execution count from
461 /* The first count in the .da file is the number of times that the function
462 was entered. This is the exec_count for block zero. */
464 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
469 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
470 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
475 e
->count
= exec_counts
[exec_counts_pos
++];
476 if (e
->count
> profile_info
->sum_max
)
478 if (flag_profile_correction
)
480 static bool informed
= 0;
481 if (dump_enabled_p () && !informed
)
482 dump_printf_loc (MSG_NOTE
, input_location
,
483 "corrupted profile info: edge count"
484 " exceeds maximal count\n");
488 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
489 bb
->index
, e
->dest
->index
);
495 EDGE_INFO (e
)->count_valid
= 1;
496 BB_INFO (bb
)->succ_count
--;
497 BB_INFO (e
->dest
)->pred_count
--;
500 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
501 bb
->index
, e
->dest
->index
);
502 fprintf (dump_file
, "%" PRId64
,
511 #define OVERLAP_BASE 10000
513 /* Compare the static estimated profile to the actual profile, and
514 return the "degree of overlap" measure between them.
516 Degree of overlap is a number between 0 and OVERLAP_BASE. It is
517 the sum of each basic block's minimum relative weights between
518 two profiles. And overlap of OVERLAP_BASE means two profiles are
522 compute_frequency_overlap (void)
524 gcov_type count_total
= 0, freq_total
= 0;
528 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
530 count_total
+= bb
->count
;
531 freq_total
+= bb
->frequency
;
534 if (count_total
== 0 || freq_total
== 0)
537 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
538 overlap
+= MIN (bb
->count
* OVERLAP_BASE
/ count_total
,
539 bb
->frequency
* OVERLAP_BASE
/ freq_total
);
544 /* Compute the branch probabilities for the various branches.
545 Annotate them accordingly.
547 CFG_CHECKSUM is the precomputed checksum for the CFG. */
550 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
557 int hist_br_prob
[20];
559 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
560 int inconsistent
= 0;
562 /* Very simple sanity checks so we catch bugs in our profiling code. */
566 if (profile_info
->sum_all
< profile_info
->sum_max
)
568 error ("corrupted profile info: sum_all is smaller than sum_max");
572 /* Attach extra info block to each bb. */
573 alloc_aux_for_blocks (sizeof (struct bb_profile_info
));
574 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
579 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
580 if (!EDGE_INFO (e
)->ignore
)
581 BB_INFO (bb
)->succ_count
++;
582 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
583 if (!EDGE_INFO (e
)->ignore
)
584 BB_INFO (bb
)->pred_count
++;
587 /* Avoid predicting entry on exit nodes. */
588 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun
))->succ_count
= 2;
589 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->pred_count
= 2;
591 num_edges
= read_profile_edge_counts (exec_counts
);
594 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
596 /* For every block in the file,
597 - if every exit/entrance edge has a known count, then set the block count
598 - if the block count is known, and every exit/entrance edge but one has
599 a known execution count, then set the count of the remaining edge
601 As edge counts are set, decrement the succ/pred count, but don't delete
602 the edge, that way we can easily tell when all edges are known, or only
603 one edge is unknown. */
605 /* The order that the basic blocks are iterated through is important.
606 Since the code that finds spanning trees starts with block 0, low numbered
607 edges are put on the spanning tree in preference to high numbered edges.
608 Hence, most instrumented edges are at the end. Graph solving works much
609 faster if we propagate numbers from the end to the start.
611 This takes an average of slightly more than 3 passes. */
619 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, prev_bb
)
621 struct bb_profile_info
*bi
= BB_INFO (bb
);
622 if (! bi
->count_valid
)
624 if (bi
->succ_count
== 0)
630 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
636 else if (bi
->pred_count
== 0)
642 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
651 if (bi
->succ_count
== 1)
657 /* One of the counts will be invalid, but it is zero,
658 so adding it in also doesn't hurt. */
659 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
662 /* Search for the invalid edge, and set its count. */
663 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
664 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
667 /* Calculate count for remaining edge by conservation. */
668 total
= bb
->count
- total
;
671 EDGE_INFO (e
)->count_valid
= 1;
675 BB_INFO (e
->dest
)->pred_count
--;
678 if (bi
->pred_count
== 1)
684 /* One of the counts will be invalid, but it is zero,
685 so adding it in also doesn't hurt. */
686 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
689 /* Search for the invalid edge, and set its count. */
690 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
691 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
694 /* Calculate count for remaining edge by conservation. */
695 total
= bb
->count
- total
+ e
->count
;
698 EDGE_INFO (e
)->count_valid
= 1;
702 BB_INFO (e
->src
)->succ_count
--;
710 int overlap
= compute_frequency_overlap ();
711 gimple_dump_cfg (dump_file
, dump_flags
);
712 fprintf (dump_file
, "Static profile overlap: %d.%d%%\n",
713 overlap
/ (OVERLAP_BASE
/ 100),
714 overlap
% (OVERLAP_BASE
/ 100));
717 total_num_passes
+= passes
;
719 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
721 /* If the graph has been correctly solved, every block will have a
722 succ and pred count of zero. */
723 FOR_EACH_BB_FN (bb
, cfun
)
725 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
728 /* Check for inconsistent basic block counts */
729 inconsistent
= is_inconsistent ();
733 if (flag_profile_correction
)
735 /* Inconsistency detected. Make it flow-consistent. */
736 static int informed
= 0;
737 if (dump_enabled_p () && informed
== 0)
740 dump_printf_loc (MSG_NOTE
, input_location
,
741 "correcting inconsistent profile data\n");
743 correct_negative_edge_counts ();
744 /* Set bb counts to the sum of the outgoing edge counts */
747 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
751 error ("corrupted profile info: profile data is not flow-consistent");
754 /* For every edge, calculate its branch probability and add a reg_note
755 to the branch insn to indicate this. */
757 for (i
= 0; i
< 20; i
++)
761 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
768 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
769 bb
->index
, (int)bb
->count
);
772 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
774 /* Function may return twice in the cased the called function is
775 setjmp or calls fork, but we can't represent this by extra
776 edge from the entry, since extra edge from the exit is
777 already present. We get negative frequency from the entry
780 && e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
781 || (e
->count
> bb
->count
782 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
784 if (block_ends_with_call_p (bb
))
785 e
->count
= e
->count
< 0 ? 0 : bb
->count
;
787 if (e
->count
< 0 || e
->count
> bb
->count
)
789 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
790 e
->src
->index
, e
->dest
->index
,
792 e
->count
= bb
->count
/ 2;
797 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
798 e
->probability
= GCOV_COMPUTE_SCALE (e
->count
, bb
->count
);
799 if (bb
->index
>= NUM_FIXED_BLOCKS
800 && block_ends_with_condjump_p (bb
)
801 && EDGE_COUNT (bb
->succs
) >= 2)
807 /* Find the branch edge. It is possible that we do have fake
809 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
810 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
813 prob
= e
->probability
;
814 index
= prob
* 20 / REG_BR_PROB_BASE
;
818 hist_br_prob
[index
]++;
823 /* As a last resort, distribute the probabilities evenly.
824 Use simple heuristics that if there are normal edges,
825 give all abnormals frequency of 0, otherwise distribute the
826 frequency over abnormals (this is the case of noreturn
828 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
832 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
833 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
837 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
838 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
839 e
->probability
= REG_BR_PROB_BASE
/ total
;
845 total
+= EDGE_COUNT (bb
->succs
);
846 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
847 e
->probability
= REG_BR_PROB_BASE
/ total
;
849 if (bb
->index
>= NUM_FIXED_BLOCKS
850 && block_ends_with_condjump_p (bb
)
851 && EDGE_COUNT (bb
->succs
) >= 2)
856 profile_status_for_fn (cfun
) = PROFILE_READ
;
857 compute_function_frequency ();
861 fprintf (dump_file
, "%d branches\n", num_branches
);
863 for (i
= 0; i
< 10; i
++)
864 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
865 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
868 total_num_branches
+= num_branches
;
869 for (i
= 0; i
< 20; i
++)
870 total_hist_br_prob
[i
] += hist_br_prob
[i
];
872 fputc ('\n', dump_file
);
873 fputc ('\n', dump_file
);
876 free_aux_for_blocks ();
879 /* Load value histograms values whose description is stored in VALUES array
882 CFG_CHECKSUM is the precomputed checksum for the CFG. */
885 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
886 unsigned lineno_checksum
)
888 unsigned i
, j
, t
, any
;
889 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
890 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
891 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
892 gcov_type
*aact_count
;
893 struct cgraph_node
*node
;
895 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
896 n_histogram_counters
[t
] = 0;
898 for (i
= 0; i
< values
.length (); i
++)
900 histogram_value hist
= values
[i
];
901 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
905 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
907 if (!n_histogram_counters
[t
])
909 histogram_counts
[t
] = NULL
;
913 histogram_counts
[t
] =
914 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
915 n_histogram_counters
[t
], cfg_checksum
,
916 lineno_checksum
, NULL
);
917 if (histogram_counts
[t
])
919 act_count
[t
] = histogram_counts
[t
];
924 for (i
= 0; i
< values
.length (); i
++)
926 histogram_value hist
= values
[i
];
927 gimple stmt
= hist
->hvalue
.stmt
;
929 t
= (int) hist
->type
;
931 aact_count
= act_count
[t
];
934 act_count
[t
] += hist
->n_counters
;
936 gimple_add_histogram_value (cfun
, stmt
, hist
);
937 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
938 for (j
= 0; j
< hist
->n_counters
; j
++)
940 hist
->hvalue
.counters
[j
] = aact_count
[j
];
942 hist
->hvalue
.counters
[j
] = 0;
944 /* Time profiler counter is not related to any statement,
945 so that we have to read the counter and set the value to
946 the corresponding call graph node. */
947 if (hist
->type
== HIST_TYPE_TIME_PROFILE
)
949 node
= cgraph_node::get (hist
->fun
->decl
);
950 node
->tp_first_run
= hist
->hvalue
.counters
[0];
953 fprintf (dump_file
, "Read tp_first_run: %d\n", node
->tp_first_run
);
957 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
958 free (histogram_counts
[t
]);
961 /* When passed NULL as file_name, initialize.
962 When passed something else, output the necessary commands to change
963 line to LINE and offset to FILE_NAME. */
965 output_location (char const *file_name
, int line
,
966 gcov_position_t
*offset
, basic_block bb
)
968 static char const *prev_file_name
;
969 static int prev_line
;
970 bool name_differs
, line_differs
;
974 prev_file_name
= NULL
;
979 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
980 line_differs
= prev_line
!= line
;
982 if (name_differs
|| line_differs
)
986 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
987 gcov_write_unsigned (bb
->index
);
988 name_differs
= line_differs
=true;
991 /* If this is a new source file, then output the
992 file's name to the .bb file. */
995 prev_file_name
= file_name
;
996 gcov_write_unsigned (0);
997 gcov_write_string (prev_file_name
);
1001 gcov_write_unsigned (line
);
1007 /* Instrument and/or analyze program behavior based on program the CFG.
1009 This function creates a representation of the control flow graph (of
1010 the function being compiled) that is suitable for the instrumentation
1011 of edges and/or converting measured edge counts to counts on the
1014 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
1015 the flow graph that are needed to reconstruct the dynamic behavior of the
1016 flow graph. This data is written to the gcno file for gcov.
1018 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1019 information from the gcda file containing edge count information from
1020 previous executions of the function being compiled. In this case, the
1021 control flow graph is annotated with actual execution counts by
1022 compute_branch_probabilities().
1024 Main entry point of this file. */
1031 unsigned num_edges
, ignored_edges
;
1032 unsigned num_instrumented
;
1033 struct edge_list
*el
;
1034 histogram_values values
= histogram_values ();
1035 unsigned cfg_checksum
, lineno_checksum
;
1037 total_num_times_called
++;
1039 flow_call_edges_add (NULL
);
1040 add_noreturn_fake_exit_edges ();
1042 /* We can't handle cyclic regions constructed using abnormal edges.
1043 To avoid these we replace every source of abnormal edge by a fake
1044 edge from entry node and every destination by fake edge to exit.
1045 This keeps graph acyclic and our calculation exact for all normal
1046 edges except for exit and entrance ones.
1048 We also add fake exit edges for each call and asm statement in the
1049 basic, since it may not return. */
1051 FOR_EACH_BB_FN (bb
, cfun
)
1053 int need_exit_edge
= 0, need_entry_edge
= 0;
1054 int have_exit_edge
= 0, have_entry_edge
= 0;
1058 /* Functions returning multiple times are not handled by extra edges.
1059 Instead we simply allow negative counts on edges from exit to the
1060 block past call and corresponding probabilities. We can't go
1061 with the extra edges because that would result in flowgraph that
1062 needs to have fake edges outside the spanning tree. */
1064 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1066 gimple_stmt_iterator gsi
;
1069 /* It may happen that there are compiler generated statements
1070 without a locus at all. Go through the basic block from the
1071 last to the first statement looking for a locus. */
1072 for (gsi
= gsi_last_nondebug_bb (bb
);
1074 gsi_prev_nondebug (&gsi
))
1076 last
= gsi_stmt (gsi
);
1077 if (gimple_has_location (last
))
1081 /* Edge with goto locus might get wrong coverage info unless
1082 it is the only edge out of BB.
1083 Don't do that when the locuses match, so
1084 if (blah) goto something;
1085 is not computed twice. */
1087 && gimple_has_location (last
)
1088 && LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
1089 && !single_succ_p (bb
)
1090 && (LOCATION_FILE (e
->goto_locus
)
1091 != LOCATION_FILE (gimple_location (last
))
1092 || (LOCATION_LINE (e
->goto_locus
)
1093 != LOCATION_LINE (gimple_location (last
)))))
1095 basic_block new_bb
= split_edge (e
);
1096 edge ne
= single_succ_edge (new_bb
);
1097 ne
->goto_locus
= e
->goto_locus
;
1099 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1100 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1102 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1105 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1107 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1108 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1109 need_entry_edge
= 1;
1110 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1111 have_entry_edge
= 1;
1114 if (need_exit_edge
&& !have_exit_edge
)
1117 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1119 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
1121 if (need_entry_edge
&& !have_entry_edge
)
1124 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1126 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
, EDGE_FAKE
);
1127 /* Avoid bbs that have both fake entry edge and also some
1128 exit edge. One of those edges wouldn't be added to the
1129 spanning tree, but we can't instrument any of them. */
1130 if (have_exit_edge
|| need_exit_edge
)
1132 gimple_stmt_iterator gsi
;
1135 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
1136 gcc_checking_assert (!gsi_end_p (gsi
));
1137 first
= gsi_stmt (gsi
);
1138 /* Don't split the bbs containing __builtin_setjmp_receiver
1139 or ABNORMAL_DISPATCHER calls. These are very
1140 special and don't expect anything to be inserted before
1142 if (is_gimple_call (first
)
1143 && (gimple_call_builtin_p (first
, BUILT_IN_SETJMP_RECEIVER
)
1144 || (gimple_call_flags (first
) & ECF_RETURNS_TWICE
)
1145 || (gimple_call_internal_p (first
)
1146 && (gimple_call_internal_fn (first
)
1147 == IFN_ABNORMAL_DISPATCHER
))))
1151 fprintf (dump_file
, "Splitting bb %i after labels\n",
1153 split_block_after_labels (bb
);
1158 el
= create_edge_list ();
1159 num_edges
= NUM_EDGES (el
);
1160 alloc_aux_for_edges (sizeof (struct edge_profile_info
));
1162 /* The basic blocks are expected to be numbered sequentially. */
1166 for (i
= 0 ; i
< num_edges
; i
++)
1168 edge e
= INDEX_EDGE (el
, i
);
1171 /* Mark edges we've replaced by fake edges above as ignored. */
1172 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1173 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1174 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1176 EDGE_INFO (e
)->ignore
= 1;
1181 /* Create spanning tree from basic block graph, mark each edge that is
1182 on the spanning tree. We insert as many abnormal and critical edges
1183 as possible to minimize number of edge splits necessary. */
1185 find_spanning_tree (el
);
1187 /* Fake edges that are not on the tree will not be instrumented, so
1188 mark them ignored. */
1189 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1191 edge e
= INDEX_EDGE (el
, i
);
1192 struct edge_profile_info
*inf
= EDGE_INFO (e
);
1194 if (inf
->ignore
|| inf
->on_tree
)
1196 else if (e
->flags
& EDGE_FAKE
)
1205 total_num_blocks
+= n_basic_blocks_for_fn (cfun
);
1207 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks_for_fn (cfun
));
1209 total_num_edges
+= num_edges
;
1211 fprintf (dump_file
, "%d edges\n", num_edges
);
1213 total_num_edges_ignored
+= ignored_edges
;
1215 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1217 total_num_edges_instrumented
+= num_instrumented
;
1219 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1221 /* Compute two different checksums. Note that we want to compute
1222 the checksum in only once place, since it depends on the shape
1223 of the control flow which can change during
1224 various transformations. */
1225 cfg_checksum
= coverage_compute_cfg_checksum (cfun
);
1226 lineno_checksum
= coverage_compute_lineno_checksum ();
1228 /* Write the data from which gcov can reconstruct the basic block
1229 graph and function line numbers (the gcno file). */
1230 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1232 gcov_position_t offset
;
1234 /* Basic block flags */
1235 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1236 for (i
= 0; i
!= (unsigned) (n_basic_blocks_for_fn (cfun
)); i
++)
1237 gcov_write_unsigned (0);
1238 gcov_write_length (offset
);
1241 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1242 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1247 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1248 gcov_write_unsigned (bb
->index
);
1250 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1252 struct edge_profile_info
*i
= EDGE_INFO (e
);
1255 unsigned flag_bits
= 0;
1258 flag_bits
|= GCOV_ARC_ON_TREE
;
1259 if (e
->flags
& EDGE_FAKE
)
1260 flag_bits
|= GCOV_ARC_FAKE
;
1261 if (e
->flags
& EDGE_FALLTHRU
)
1262 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1263 /* On trees we don't have fallthru flags, but we can
1264 recompute them from CFG shape. */
1265 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1266 && e
->src
->next_bb
== e
->dest
)
1267 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1269 gcov_write_unsigned (e
->dest
->index
);
1270 gcov_write_unsigned (flag_bits
);
1274 gcov_write_length (offset
);
1278 /* Initialize the output. */
1279 output_location (NULL
, 0, NULL
, NULL
);
1281 FOR_EACH_BB_FN (bb
, cfun
)
1283 gimple_stmt_iterator gsi
;
1284 gcov_position_t offset
= 0;
1286 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
1288 expanded_location curr_location
=
1289 expand_location (DECL_SOURCE_LOCATION (current_function_decl
));
1290 output_location (curr_location
.file
, curr_location
.line
,
1294 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1296 gimple stmt
= gsi_stmt (gsi
);
1297 if (gimple_has_location (stmt
))
1298 output_location (gimple_filename (stmt
), gimple_lineno (stmt
),
1302 /* Notice GOTO expressions eliminated while constructing the CFG. */
1303 if (single_succ_p (bb
)
1304 && LOCATION_LOCUS (single_succ_edge (bb
)->goto_locus
)
1305 != UNKNOWN_LOCATION
)
1307 expanded_location curr_location
1308 = expand_location (single_succ_edge (bb
)->goto_locus
);
1309 output_location (curr_location
.file
, curr_location
.line
,
1315 /* A file of NULL indicates the end of run. */
1316 gcov_write_unsigned (0);
1317 gcov_write_string (NULL
);
1318 gcov_write_length (offset
);
1323 if (flag_profile_values
)
1324 gimple_find_values_to_profile (&values
);
1326 if (flag_branch_probabilities
)
1328 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1329 if (flag_profile_values
)
1330 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1333 remove_fake_edges ();
1335 /* For each edge not on the spanning tree, add counting code. */
1336 if (profile_arc_flag
1337 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1339 unsigned n_instrumented
;
1341 gimple_init_edge_profiler ();
1343 n_instrumented
= instrument_edges (el
);
1345 gcc_assert (n_instrumented
== num_instrumented
);
1347 if (flag_profile_values
)
1348 instrument_values (values
);
1350 /* Commit changes done by instrumentation. */
1351 gsi_commit_edge_inserts ();
1354 free_aux_for_edges ();
1357 free_edge_list (el
);
1358 coverage_end_function (lineno_checksum
, cfg_checksum
);
1361 /* Union find algorithm implementation for the basic blocks using
1365 find_group (basic_block bb
)
1367 basic_block group
= bb
, bb1
;
1369 while ((basic_block
) group
->aux
!= group
)
1370 group
= (basic_block
) group
->aux
;
1372 /* Compress path. */
1373 while ((basic_block
) bb
->aux
!= group
)
1375 bb1
= (basic_block
) bb
->aux
;
1376 bb
->aux
= (void *) group
;
1383 union_groups (basic_block bb1
, basic_block bb2
)
1385 basic_block bb1g
= find_group (bb1
);
1386 basic_block bb2g
= find_group (bb2
);
1388 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1389 this code is unlikely going to be performance problem anyway. */
1390 gcc_assert (bb1g
!= bb2g
);
1395 /* This function searches all of the edges in the program flow graph, and puts
1396 as many bad edges as possible onto the spanning tree. Bad edges include
1397 abnormals edges, which can't be instrumented at the moment. Since it is
1398 possible for fake edges to form a cycle, we will have to develop some
1399 better way in the future. Also put critical edges to the tree, since they
1400 are more expensive to instrument. */
1403 find_spanning_tree (struct edge_list
*el
)
1406 int num_edges
= NUM_EDGES (el
);
1409 /* We use aux field for standard union-find algorithm. */
1410 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
1413 /* Add fake edge exit to entry we can't instrument. */
1414 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun
), ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1416 /* First add all abnormal edges to the tree unless they form a cycle. Also
1417 add all edges to the exit block to avoid inserting profiling code behind
1418 setting return value from function. */
1419 for (i
= 0; i
< num_edges
; i
++)
1421 edge e
= INDEX_EDGE (el
, i
);
1422 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1423 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1424 && !EDGE_INFO (e
)->ignore
1425 && (find_group (e
->src
) != find_group (e
->dest
)))
1428 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1429 e
->src
->index
, e
->dest
->index
);
1430 EDGE_INFO (e
)->on_tree
= 1;
1431 union_groups (e
->src
, e
->dest
);
1435 /* Now insert all critical edges to the tree unless they form a cycle. */
1436 for (i
= 0; i
< num_edges
; i
++)
1438 edge e
= INDEX_EDGE (el
, i
);
1439 if (EDGE_CRITICAL_P (e
) && !EDGE_INFO (e
)->ignore
1440 && find_group (e
->src
) != find_group (e
->dest
))
1443 fprintf (dump_file
, "Critical edge %d to %d put to tree\n",
1444 e
->src
->index
, e
->dest
->index
);
1445 EDGE_INFO (e
)->on_tree
= 1;
1446 union_groups (e
->src
, e
->dest
);
1450 /* And now the rest. */
1451 for (i
= 0; i
< num_edges
; i
++)
1453 edge e
= INDEX_EDGE (el
, i
);
1454 if (!EDGE_INFO (e
)->ignore
1455 && find_group (e
->src
) != find_group (e
->dest
))
1458 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1459 e
->src
->index
, e
->dest
->index
);
1460 EDGE_INFO (e
)->on_tree
= 1;
1461 union_groups (e
->src
, e
->dest
);
1465 clear_aux_for_blocks ();
1468 /* Perform file-level initialization for branch-prob processing. */
1471 init_branch_prob (void)
1475 total_num_blocks
= 0;
1476 total_num_edges
= 0;
1477 total_num_edges_ignored
= 0;
1478 total_num_edges_instrumented
= 0;
1479 total_num_blocks_created
= 0;
1480 total_num_passes
= 0;
1481 total_num_times_called
= 0;
1482 total_num_branches
= 0;
1483 for (i
= 0; i
< 20; i
++)
1484 total_hist_br_prob
[i
] = 0;
1487 /* Performs file-level cleanup after branch-prob processing
1491 end_branch_prob (void)
1495 fprintf (dump_file
, "\n");
1496 fprintf (dump_file
, "Total number of blocks: %d\n",
1498 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1499 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1500 total_num_edges_ignored
);
1501 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1502 total_num_edges_instrumented
);
1503 fprintf (dump_file
, "Total number of blocks created: %d\n",
1504 total_num_blocks_created
);
1505 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1507 if (total_num_times_called
!= 0)
1508 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1509 (total_num_passes
+ (total_num_times_called
>> 1))
1510 / total_num_times_called
);
1511 fprintf (dump_file
, "Total number of branches: %d\n",
1512 total_num_branches
);
1513 if (total_num_branches
)
1517 for (i
= 0; i
< 10; i
++)
1518 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1519 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1520 / total_num_branches
, 5*i
, 5*i
+5);