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"
61 #include "hard-reg-set.h"
64 #include "statistics.h"
68 #include "insn-config.h"
78 #include "dominance.h"
81 #include "basic-block.h"
82 #include "diagnostic-core.h"
84 #include "value-prof.h"
85 #include "fold-const.h"
86 #include "tree-ssa-alias.h"
87 #include "internal-fn.h"
88 #include "gimple-expr.h"
91 #include "gimple-iterator.h"
96 #include "plugin-api.h"
102 struct bb_profile_info
{
103 unsigned int count_valid
: 1;
105 /* Number of successor and predecessor edges. */
106 gcov_type succ_count
;
107 gcov_type pred_count
;
110 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
113 /* Counter summary from the last set of coverage counts read. */
115 const struct gcov_ctr_summary
*profile_info
;
117 /* Counter working set information computed from the current counter
118 summary. Not initialized unless profile_info summary is non-NULL. */
119 static gcov_working_set_t gcov_working_sets
[NUM_GCOV_WORKING_SETS
];
121 /* Collect statistics on the performance of this pass for the entire source
124 static int total_num_blocks
;
125 static int total_num_edges
;
126 static int total_num_edges_ignored
;
127 static int total_num_edges_instrumented
;
128 static int total_num_blocks_created
;
129 static int total_num_passes
;
130 static int total_num_times_called
;
131 static int total_hist_br_prob
[20];
132 static int total_num_branches
;
134 /* Helper function to update gcov_working_sets. */
136 void add_working_set (gcov_working_set_t
*set
) {
138 for (; i
< NUM_GCOV_WORKING_SETS
; i
++)
139 gcov_working_sets
[i
] = set
[i
];
142 /* Forward declarations. */
143 static void find_spanning_tree (struct edge_list
*);
145 /* Add edge instrumentation code to the entire insn chain.
147 F is the first insn of the chain.
148 NUM_BLOCKS is the number of basic blocks found in F. */
151 instrument_edges (struct edge_list
*el
)
153 unsigned num_instr_edges
= 0;
154 int num_edges
= NUM_EDGES (el
);
157 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
162 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
164 struct edge_profile_info
*inf
= EDGE_INFO (e
);
166 if (!inf
->ignore
&& !inf
->on_tree
)
168 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
170 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
171 e
->src
->index
, e
->dest
->index
,
172 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
173 gimple_gen_edge_profiler (num_instr_edges
++, e
);
178 total_num_blocks_created
+= num_edges
;
180 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
181 return num_instr_edges
;
184 /* Add code to measure histograms for values in list VALUES. */
186 instrument_values (histogram_values values
)
190 /* Emit code to generate the histograms before the insns. */
192 for (i
= 0; i
< values
.length (); i
++)
194 histogram_value hist
= values
[i
];
195 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
197 if (!coverage_counter_alloc (t
, hist
->n_counters
))
202 case HIST_TYPE_INTERVAL
:
203 gimple_gen_interval_profiler (hist
, t
, 0);
207 gimple_gen_pow2_profiler (hist
, t
, 0);
210 case HIST_TYPE_SINGLE_VALUE
:
211 gimple_gen_one_value_profiler (hist
, t
, 0);
214 case HIST_TYPE_CONST_DELTA
:
215 gimple_gen_const_delta_profiler (hist
, t
, 0);
218 case HIST_TYPE_INDIR_CALL
:
219 case HIST_TYPE_INDIR_CALL_TOPN
:
220 gimple_gen_ic_profiler (hist
, t
, 0);
223 case HIST_TYPE_AVERAGE
:
224 gimple_gen_average_profiler (hist
, t
, 0);
228 gimple_gen_ior_profiler (hist
, t
, 0);
231 case HIST_TYPE_TIME_PROFILE
:
234 split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
235 gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
237 gimple_gen_time_profiler (t
, 0, gsi
);
248 /* Fill the working set information into the profile_info structure. */
251 get_working_sets (void)
253 unsigned ws_ix
, pctinc
, pct
;
254 gcov_working_set_t
*ws_info
;
259 compute_working_sets (profile_info
, gcov_working_sets
);
263 fprintf (dump_file
, "Counter working sets:\n");
264 /* Multiply the percentage by 100 to avoid float. */
265 pctinc
= 100 * 100 / NUM_GCOV_WORKING_SETS
;
266 for (ws_ix
= 0, pct
= pctinc
; ws_ix
< NUM_GCOV_WORKING_SETS
;
267 ws_ix
++, pct
+= pctinc
)
269 if (ws_ix
== NUM_GCOV_WORKING_SETS
- 1)
271 ws_info
= &gcov_working_sets
[ws_ix
];
272 /* Print out the percentage using int arithmatic to avoid float. */
273 fprintf (dump_file
, "\t\t%u.%02u%%: num counts=%u, min counter="
275 pct
/ 100, pct
- (pct
/ 100 * 100),
276 ws_info
->num_counters
,
277 (int64_t)ws_info
->min_counter
);
282 /* Given a the desired percentage of the full profile (sum_all from the
283 summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns
284 the corresponding working set information. If an exact match for
285 the percentage isn't found, the closest value is used. */
288 find_working_set (unsigned pct_times_10
)
293 gcc_assert (pct_times_10
<= 1000);
294 if (pct_times_10
>= 999)
295 return &gcov_working_sets
[NUM_GCOV_WORKING_SETS
- 1];
296 i
= pct_times_10
* NUM_GCOV_WORKING_SETS
/ 1000;
298 return &gcov_working_sets
[0];
299 return &gcov_working_sets
[i
- 1];
302 /* Computes hybrid profile for all matching entries in da_file.
304 CFG_CHECKSUM is the precomputed checksum for the CFG. */
307 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
309 unsigned num_edges
= 0;
313 /* Count the edges to be (possibly) instrumented. */
314 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
319 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
320 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
324 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, num_edges
, cfg_checksum
,
325 lineno_checksum
, &profile_info
);
331 if (dump_file
&& profile_info
)
332 fprintf (dump_file
, "Merged %u profiles with maximal count %u.\n",
333 profile_info
->runs
, (unsigned) profile_info
->sum_max
);
340 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
344 FOR_EACH_EDGE (e
, ei
, edges
)
346 if (!EDGE_INFO (e
)->ignore
)
349 && (!(e
->flags
& EDGE_FAKE
)
350 || !block_ends_with_call_p (e
->src
)))
355 "Edge %i->%i is inconsistent, count%" PRId64
,
356 e
->src
->index
, e
->dest
->index
, e
->count
);
357 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
358 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
368 correct_negative_edge_counts (void)
374 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
376 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
384 /* Check consistency.
385 Return true if inconsistency is found. */
387 is_inconsistent (void)
390 bool inconsistent
= false;
391 FOR_EACH_BB_FN (bb
, cfun
)
393 inconsistent
|= is_edge_inconsistent (bb
->preds
);
394 if (!dump_file
&& inconsistent
)
396 inconsistent
|= is_edge_inconsistent (bb
->succs
);
397 if (!dump_file
&& inconsistent
)
403 fprintf (dump_file
, "BB %i count is negative "
407 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
411 if (bb
->count
!= sum_edge_counts (bb
->preds
))
415 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
416 "%" PRId64
" should be %" PRId64
,
419 sum_edge_counts (bb
->preds
));
420 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
424 if (bb
->count
!= sum_edge_counts (bb
->succs
) &&
425 ! (find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
)) != NULL
426 && block_ends_with_call_p (bb
)))
430 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
431 "%" PRId64
" should be %" PRId64
,
434 sum_edge_counts (bb
->succs
));
435 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
439 if (!dump_file
&& inconsistent
)
446 /* Set each basic block count to the sum of its outgoing edge counts */
451 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
453 bb
->count
= sum_edge_counts (bb
->succs
);
454 gcc_assert (bb
->count
>= 0);
458 /* Reads profile data and returns total number of edge counts read */
460 read_profile_edge_counts (gcov_type
*exec_counts
)
464 int exec_counts_pos
= 0;
465 /* For each edge not on the spanning tree, set its execution count from
467 /* The first count in the .da file is the number of times that the function
468 was entered. This is the exec_count for block zero. */
470 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
475 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
476 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
481 e
->count
= exec_counts
[exec_counts_pos
++];
482 if (e
->count
> profile_info
->sum_max
)
484 if (flag_profile_correction
)
486 static bool informed
= 0;
487 if (dump_enabled_p () && !informed
)
488 dump_printf_loc (MSG_NOTE
, input_location
,
489 "corrupted profile info: edge count"
490 " exceeds maximal count\n");
494 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
495 bb
->index
, e
->dest
->index
);
501 EDGE_INFO (e
)->count_valid
= 1;
502 BB_INFO (bb
)->succ_count
--;
503 BB_INFO (e
->dest
)->pred_count
--;
506 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
507 bb
->index
, e
->dest
->index
);
508 fprintf (dump_file
, "%" PRId64
,
517 #define OVERLAP_BASE 10000
519 /* Compare the static estimated profile to the actual profile, and
520 return the "degree of overlap" measure between them.
522 Degree of overlap is a number between 0 and OVERLAP_BASE. It is
523 the sum of each basic block's minimum relative weights between
524 two profiles. And overlap of OVERLAP_BASE means two profiles are
528 compute_frequency_overlap (void)
530 gcov_type count_total
= 0, freq_total
= 0;
534 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
536 count_total
+= bb
->count
;
537 freq_total
+= bb
->frequency
;
540 if (count_total
== 0 || freq_total
== 0)
543 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
544 overlap
+= MIN (bb
->count
* OVERLAP_BASE
/ count_total
,
545 bb
->frequency
* OVERLAP_BASE
/ freq_total
);
550 /* Compute the branch probabilities for the various branches.
551 Annotate them accordingly.
553 CFG_CHECKSUM is the precomputed checksum for the CFG. */
556 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
563 int hist_br_prob
[20];
565 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
566 int inconsistent
= 0;
568 /* Very simple sanity checks so we catch bugs in our profiling code. */
572 if (profile_info
->sum_all
< profile_info
->sum_max
)
574 error ("corrupted profile info: sum_all is smaller than sum_max");
578 /* Attach extra info block to each bb. */
579 alloc_aux_for_blocks (sizeof (struct bb_profile_info
));
580 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
585 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
586 if (!EDGE_INFO (e
)->ignore
)
587 BB_INFO (bb
)->succ_count
++;
588 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
589 if (!EDGE_INFO (e
)->ignore
)
590 BB_INFO (bb
)->pred_count
++;
593 /* Avoid predicting entry on exit nodes. */
594 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun
))->succ_count
= 2;
595 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->pred_count
= 2;
597 num_edges
= read_profile_edge_counts (exec_counts
);
600 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
602 /* For every block in the file,
603 - if every exit/entrance edge has a known count, then set the block count
604 - if the block count is known, and every exit/entrance edge but one has
605 a known execution count, then set the count of the remaining edge
607 As edge counts are set, decrement the succ/pred count, but don't delete
608 the edge, that way we can easily tell when all edges are known, or only
609 one edge is unknown. */
611 /* The order that the basic blocks are iterated through is important.
612 Since the code that finds spanning trees starts with block 0, low numbered
613 edges are put on the spanning tree in preference to high numbered edges.
614 Hence, most instrumented edges are at the end. Graph solving works much
615 faster if we propagate numbers from the end to the start.
617 This takes an average of slightly more than 3 passes. */
625 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, prev_bb
)
627 struct bb_profile_info
*bi
= BB_INFO (bb
);
628 if (! bi
->count_valid
)
630 if (bi
->succ_count
== 0)
636 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
642 else if (bi
->pred_count
== 0)
648 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
657 if (bi
->succ_count
== 1)
663 /* One of the counts will be invalid, but it is zero,
664 so adding it in also doesn't hurt. */
665 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
668 /* Search for the invalid edge, and set its count. */
669 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
670 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
673 /* Calculate count for remaining edge by conservation. */
674 total
= bb
->count
- total
;
677 EDGE_INFO (e
)->count_valid
= 1;
681 BB_INFO (e
->dest
)->pred_count
--;
684 if (bi
->pred_count
== 1)
690 /* One of the counts will be invalid, but it is zero,
691 so adding it in also doesn't hurt. */
692 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
695 /* Search for the invalid edge, and set its count. */
696 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
697 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
700 /* Calculate count for remaining edge by conservation. */
701 total
= bb
->count
- total
+ e
->count
;
704 EDGE_INFO (e
)->count_valid
= 1;
708 BB_INFO (e
->src
)->succ_count
--;
716 int overlap
= compute_frequency_overlap ();
717 gimple_dump_cfg (dump_file
, dump_flags
);
718 fprintf (dump_file
, "Static profile overlap: %d.%d%%\n",
719 overlap
/ (OVERLAP_BASE
/ 100),
720 overlap
% (OVERLAP_BASE
/ 100));
723 total_num_passes
+= passes
;
725 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
727 /* If the graph has been correctly solved, every block will have a
728 succ and pred count of zero. */
729 FOR_EACH_BB_FN (bb
, cfun
)
731 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
734 /* Check for inconsistent basic block counts */
735 inconsistent
= is_inconsistent ();
739 if (flag_profile_correction
)
741 /* Inconsistency detected. Make it flow-consistent. */
742 static int informed
= 0;
743 if (dump_enabled_p () && informed
== 0)
746 dump_printf_loc (MSG_NOTE
, input_location
,
747 "correcting inconsistent profile data\n");
749 correct_negative_edge_counts ();
750 /* Set bb counts to the sum of the outgoing edge counts */
753 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
757 error ("corrupted profile info: profile data is not flow-consistent");
760 /* For every edge, calculate its branch probability and add a reg_note
761 to the branch insn to indicate this. */
763 for (i
= 0; i
< 20; i
++)
767 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
774 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
775 bb
->index
, (int)bb
->count
);
778 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
780 /* Function may return twice in the cased the called function is
781 setjmp or calls fork, but we can't represent this by extra
782 edge from the entry, since extra edge from the exit is
783 already present. We get negative frequency from the entry
786 && e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
787 || (e
->count
> bb
->count
788 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
790 if (block_ends_with_call_p (bb
))
791 e
->count
= e
->count
< 0 ? 0 : bb
->count
;
793 if (e
->count
< 0 || e
->count
> bb
->count
)
795 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
796 e
->src
->index
, e
->dest
->index
,
798 e
->count
= bb
->count
/ 2;
803 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
804 e
->probability
= GCOV_COMPUTE_SCALE (e
->count
, bb
->count
);
805 if (bb
->index
>= NUM_FIXED_BLOCKS
806 && block_ends_with_condjump_p (bb
)
807 && EDGE_COUNT (bb
->succs
) >= 2)
813 /* Find the branch edge. It is possible that we do have fake
815 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
816 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
819 prob
= e
->probability
;
820 index
= prob
* 20 / REG_BR_PROB_BASE
;
824 hist_br_prob
[index
]++;
829 /* As a last resort, distribute the probabilities evenly.
830 Use simple heuristics that if there are normal edges,
831 give all abnormals frequency of 0, otherwise distribute the
832 frequency over abnormals (this is the case of noreturn
834 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
838 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
839 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
843 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
844 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
845 e
->probability
= REG_BR_PROB_BASE
/ total
;
851 total
+= EDGE_COUNT (bb
->succs
);
852 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
853 e
->probability
= REG_BR_PROB_BASE
/ total
;
855 if (bb
->index
>= NUM_FIXED_BLOCKS
856 && block_ends_with_condjump_p (bb
)
857 && EDGE_COUNT (bb
->succs
) >= 2)
862 profile_status_for_fn (cfun
) = PROFILE_READ
;
863 compute_function_frequency ();
867 fprintf (dump_file
, "%d branches\n", num_branches
);
869 for (i
= 0; i
< 10; i
++)
870 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
871 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
874 total_num_branches
+= num_branches
;
875 for (i
= 0; i
< 20; i
++)
876 total_hist_br_prob
[i
] += hist_br_prob
[i
];
878 fputc ('\n', dump_file
);
879 fputc ('\n', dump_file
);
882 free_aux_for_blocks ();
885 /* Load value histograms values whose description is stored in VALUES array
888 CFG_CHECKSUM is the precomputed checksum for the CFG. */
891 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
892 unsigned lineno_checksum
)
894 unsigned i
, j
, t
, any
;
895 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
896 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
897 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
898 gcov_type
*aact_count
;
899 struct cgraph_node
*node
;
901 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
902 n_histogram_counters
[t
] = 0;
904 for (i
= 0; i
< values
.length (); i
++)
906 histogram_value hist
= values
[i
];
907 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
911 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
913 if (!n_histogram_counters
[t
])
915 histogram_counts
[t
] = NULL
;
919 histogram_counts
[t
] =
920 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
921 n_histogram_counters
[t
], cfg_checksum
,
922 lineno_checksum
, NULL
);
923 if (histogram_counts
[t
])
925 act_count
[t
] = histogram_counts
[t
];
930 for (i
= 0; i
< values
.length (); i
++)
932 histogram_value hist
= values
[i
];
933 gimple stmt
= hist
->hvalue
.stmt
;
935 t
= (int) hist
->type
;
937 aact_count
= act_count
[t
];
940 act_count
[t
] += hist
->n_counters
;
942 gimple_add_histogram_value (cfun
, stmt
, hist
);
943 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
944 for (j
= 0; j
< hist
->n_counters
; j
++)
946 hist
->hvalue
.counters
[j
] = aact_count
[j
];
948 hist
->hvalue
.counters
[j
] = 0;
950 /* Time profiler counter is not related to any statement,
951 so that we have to read the counter and set the value to
952 the corresponding call graph node. */
953 if (hist
->type
== HIST_TYPE_TIME_PROFILE
)
955 node
= cgraph_node::get (hist
->fun
->decl
);
956 node
->tp_first_run
= hist
->hvalue
.counters
[0];
959 fprintf (dump_file
, "Read tp_first_run: %d\n", node
->tp_first_run
);
963 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
964 free (histogram_counts
[t
]);
967 /* When passed NULL as file_name, initialize.
968 When passed something else, output the necessary commands to change
969 line to LINE and offset to FILE_NAME. */
971 output_location (char const *file_name
, int line
,
972 gcov_position_t
*offset
, basic_block bb
)
974 static char const *prev_file_name
;
975 static int prev_line
;
976 bool name_differs
, line_differs
;
980 prev_file_name
= NULL
;
985 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
986 line_differs
= prev_line
!= line
;
988 if (name_differs
|| line_differs
)
992 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
993 gcov_write_unsigned (bb
->index
);
994 name_differs
= line_differs
=true;
997 /* If this is a new source file, then output the
998 file's name to the .bb file. */
1001 prev_file_name
= file_name
;
1002 gcov_write_unsigned (0);
1003 gcov_write_string (prev_file_name
);
1007 gcov_write_unsigned (line
);
1013 /* Instrument and/or analyze program behavior based on program the CFG.
1015 This function creates a representation of the control flow graph (of
1016 the function being compiled) that is suitable for the instrumentation
1017 of edges and/or converting measured edge counts to counts on the
1020 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
1021 the flow graph that are needed to reconstruct the dynamic behavior of the
1022 flow graph. This data is written to the gcno file for gcov.
1024 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1025 information from the gcda file containing edge count information from
1026 previous executions of the function being compiled. In this case, the
1027 control flow graph is annotated with actual execution counts by
1028 compute_branch_probabilities().
1030 Main entry point of this file. */
1037 unsigned num_edges
, ignored_edges
;
1038 unsigned num_instrumented
;
1039 struct edge_list
*el
;
1040 histogram_values values
= histogram_values ();
1041 unsigned cfg_checksum
, lineno_checksum
;
1043 total_num_times_called
++;
1045 flow_call_edges_add (NULL
);
1046 add_noreturn_fake_exit_edges ();
1048 /* We can't handle cyclic regions constructed using abnormal edges.
1049 To avoid these we replace every source of abnormal edge by a fake
1050 edge from entry node and every destination by fake edge to exit.
1051 This keeps graph acyclic and our calculation exact for all normal
1052 edges except for exit and entrance ones.
1054 We also add fake exit edges for each call and asm statement in the
1055 basic, since it may not return. */
1057 FOR_EACH_BB_FN (bb
, cfun
)
1059 int need_exit_edge
= 0, need_entry_edge
= 0;
1060 int have_exit_edge
= 0, have_entry_edge
= 0;
1064 /* Functions returning multiple times are not handled by extra edges.
1065 Instead we simply allow negative counts on edges from exit to the
1066 block past call and corresponding probabilities. We can't go
1067 with the extra edges because that would result in flowgraph that
1068 needs to have fake edges outside the spanning tree. */
1070 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1072 gimple_stmt_iterator gsi
;
1075 /* It may happen that there are compiler generated statements
1076 without a locus at all. Go through the basic block from the
1077 last to the first statement looking for a locus. */
1078 for (gsi
= gsi_last_nondebug_bb (bb
);
1080 gsi_prev_nondebug (&gsi
))
1082 last
= gsi_stmt (gsi
);
1083 if (gimple_has_location (last
))
1087 /* Edge with goto locus might get wrong coverage info unless
1088 it is the only edge out of BB.
1089 Don't do that when the locuses match, so
1090 if (blah) goto something;
1091 is not computed twice. */
1093 && gimple_has_location (last
)
1094 && LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
1095 && !single_succ_p (bb
)
1096 && (LOCATION_FILE (e
->goto_locus
)
1097 != LOCATION_FILE (gimple_location (last
))
1098 || (LOCATION_LINE (e
->goto_locus
)
1099 != LOCATION_LINE (gimple_location (last
)))))
1101 basic_block new_bb
= split_edge (e
);
1102 edge ne
= single_succ_edge (new_bb
);
1103 ne
->goto_locus
= e
->goto_locus
;
1105 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1106 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1108 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1111 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1113 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1114 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1115 need_entry_edge
= 1;
1116 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1117 have_entry_edge
= 1;
1120 if (need_exit_edge
&& !have_exit_edge
)
1123 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1125 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
1127 if (need_entry_edge
&& !have_entry_edge
)
1130 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1132 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
, EDGE_FAKE
);
1133 /* Avoid bbs that have both fake entry edge and also some
1134 exit edge. One of those edges wouldn't be added to the
1135 spanning tree, but we can't instrument any of them. */
1136 if (have_exit_edge
|| need_exit_edge
)
1138 gimple_stmt_iterator gsi
;
1141 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
1142 gcc_checking_assert (!gsi_end_p (gsi
));
1143 first
= gsi_stmt (gsi
);
1144 /* Don't split the bbs containing __builtin_setjmp_receiver
1145 or ABNORMAL_DISPATCHER calls. These are very
1146 special and don't expect anything to be inserted before
1148 if (is_gimple_call (first
)
1149 && (gimple_call_builtin_p (first
, BUILT_IN_SETJMP_RECEIVER
)
1150 || (gimple_call_flags (first
) & ECF_RETURNS_TWICE
)
1151 || (gimple_call_internal_p (first
)
1152 && (gimple_call_internal_fn (first
)
1153 == IFN_ABNORMAL_DISPATCHER
))))
1157 fprintf (dump_file
, "Splitting bb %i after labels\n",
1159 split_block_after_labels (bb
);
1164 el
= create_edge_list ();
1165 num_edges
= NUM_EDGES (el
);
1166 alloc_aux_for_edges (sizeof (struct edge_profile_info
));
1168 /* The basic blocks are expected to be numbered sequentially. */
1172 for (i
= 0 ; i
< num_edges
; i
++)
1174 edge e
= INDEX_EDGE (el
, i
);
1177 /* Mark edges we've replaced by fake edges above as ignored. */
1178 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1179 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1180 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1182 EDGE_INFO (e
)->ignore
= 1;
1187 /* Create spanning tree from basic block graph, mark each edge that is
1188 on the spanning tree. We insert as many abnormal and critical edges
1189 as possible to minimize number of edge splits necessary. */
1191 find_spanning_tree (el
);
1193 /* Fake edges that are not on the tree will not be instrumented, so
1194 mark them ignored. */
1195 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1197 edge e
= INDEX_EDGE (el
, i
);
1198 struct edge_profile_info
*inf
= EDGE_INFO (e
);
1200 if (inf
->ignore
|| inf
->on_tree
)
1202 else if (e
->flags
& EDGE_FAKE
)
1211 total_num_blocks
+= n_basic_blocks_for_fn (cfun
);
1213 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks_for_fn (cfun
));
1215 total_num_edges
+= num_edges
;
1217 fprintf (dump_file
, "%d edges\n", num_edges
);
1219 total_num_edges_ignored
+= ignored_edges
;
1221 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1223 total_num_edges_instrumented
+= num_instrumented
;
1225 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1227 /* Compute two different checksums. Note that we want to compute
1228 the checksum in only once place, since it depends on the shape
1229 of the control flow which can change during
1230 various transformations. */
1231 cfg_checksum
= coverage_compute_cfg_checksum (cfun
);
1232 lineno_checksum
= coverage_compute_lineno_checksum ();
1234 /* Write the data from which gcov can reconstruct the basic block
1235 graph and function line numbers (the gcno file). */
1236 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1238 gcov_position_t offset
;
1240 /* Basic block flags */
1241 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1242 for (i
= 0; i
!= (unsigned) (n_basic_blocks_for_fn (cfun
)); i
++)
1243 gcov_write_unsigned (0);
1244 gcov_write_length (offset
);
1247 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1248 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1253 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1254 gcov_write_unsigned (bb
->index
);
1256 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1258 struct edge_profile_info
*i
= EDGE_INFO (e
);
1261 unsigned flag_bits
= 0;
1264 flag_bits
|= GCOV_ARC_ON_TREE
;
1265 if (e
->flags
& EDGE_FAKE
)
1266 flag_bits
|= GCOV_ARC_FAKE
;
1267 if (e
->flags
& EDGE_FALLTHRU
)
1268 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1269 /* On trees we don't have fallthru flags, but we can
1270 recompute them from CFG shape. */
1271 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1272 && e
->src
->next_bb
== e
->dest
)
1273 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1275 gcov_write_unsigned (e
->dest
->index
);
1276 gcov_write_unsigned (flag_bits
);
1280 gcov_write_length (offset
);
1284 /* Initialize the output. */
1285 output_location (NULL
, 0, NULL
, NULL
);
1287 FOR_EACH_BB_FN (bb
, cfun
)
1289 gimple_stmt_iterator gsi
;
1290 gcov_position_t offset
= 0;
1292 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
1294 expanded_location curr_location
=
1295 expand_location (DECL_SOURCE_LOCATION (current_function_decl
));
1296 output_location (curr_location
.file
, curr_location
.line
,
1300 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1302 gimple stmt
= gsi_stmt (gsi
);
1303 if (gimple_has_location (stmt
))
1304 output_location (gimple_filename (stmt
), gimple_lineno (stmt
),
1308 /* Notice GOTO expressions eliminated while constructing the CFG. */
1309 if (single_succ_p (bb
)
1310 && LOCATION_LOCUS (single_succ_edge (bb
)->goto_locus
)
1311 != UNKNOWN_LOCATION
)
1313 expanded_location curr_location
1314 = expand_location (single_succ_edge (bb
)->goto_locus
);
1315 output_location (curr_location
.file
, curr_location
.line
,
1321 /* A file of NULL indicates the end of run. */
1322 gcov_write_unsigned (0);
1323 gcov_write_string (NULL
);
1324 gcov_write_length (offset
);
1329 if (flag_profile_values
)
1330 gimple_find_values_to_profile (&values
);
1332 if (flag_branch_probabilities
)
1334 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1335 if (flag_profile_values
)
1336 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1339 remove_fake_edges ();
1341 /* For each edge not on the spanning tree, add counting code. */
1342 if (profile_arc_flag
1343 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1345 unsigned n_instrumented
;
1347 gimple_init_edge_profiler ();
1349 n_instrumented
= instrument_edges (el
);
1351 gcc_assert (n_instrumented
== num_instrumented
);
1353 if (flag_profile_values
)
1354 instrument_values (values
);
1356 /* Commit changes done by instrumentation. */
1357 gsi_commit_edge_inserts ();
1360 free_aux_for_edges ();
1363 free_edge_list (el
);
1364 coverage_end_function (lineno_checksum
, cfg_checksum
);
1367 /* Union find algorithm implementation for the basic blocks using
1371 find_group (basic_block bb
)
1373 basic_block group
= bb
, bb1
;
1375 while ((basic_block
) group
->aux
!= group
)
1376 group
= (basic_block
) group
->aux
;
1378 /* Compress path. */
1379 while ((basic_block
) bb
->aux
!= group
)
1381 bb1
= (basic_block
) bb
->aux
;
1382 bb
->aux
= (void *) group
;
1389 union_groups (basic_block bb1
, basic_block bb2
)
1391 basic_block bb1g
= find_group (bb1
);
1392 basic_block bb2g
= find_group (bb2
);
1394 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1395 this code is unlikely going to be performance problem anyway. */
1396 gcc_assert (bb1g
!= bb2g
);
1401 /* This function searches all of the edges in the program flow graph, and puts
1402 as many bad edges as possible onto the spanning tree. Bad edges include
1403 abnormals edges, which can't be instrumented at the moment. Since it is
1404 possible for fake edges to form a cycle, we will have to develop some
1405 better way in the future. Also put critical edges to the tree, since they
1406 are more expensive to instrument. */
1409 find_spanning_tree (struct edge_list
*el
)
1412 int num_edges
= NUM_EDGES (el
);
1415 /* We use aux field for standard union-find algorithm. */
1416 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
1419 /* Add fake edge exit to entry we can't instrument. */
1420 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun
), ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1422 /* First add all abnormal edges to the tree unless they form a cycle. Also
1423 add all edges to the exit block to avoid inserting profiling code behind
1424 setting return value from function. */
1425 for (i
= 0; i
< num_edges
; i
++)
1427 edge e
= INDEX_EDGE (el
, i
);
1428 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1429 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1430 && !EDGE_INFO (e
)->ignore
1431 && (find_group (e
->src
) != find_group (e
->dest
)))
1434 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1435 e
->src
->index
, e
->dest
->index
);
1436 EDGE_INFO (e
)->on_tree
= 1;
1437 union_groups (e
->src
, e
->dest
);
1441 /* Now insert all critical edges to the tree unless they form a cycle. */
1442 for (i
= 0; i
< num_edges
; i
++)
1444 edge e
= INDEX_EDGE (el
, i
);
1445 if (EDGE_CRITICAL_P (e
) && !EDGE_INFO (e
)->ignore
1446 && find_group (e
->src
) != find_group (e
->dest
))
1449 fprintf (dump_file
, "Critical edge %d to %d put to tree\n",
1450 e
->src
->index
, e
->dest
->index
);
1451 EDGE_INFO (e
)->on_tree
= 1;
1452 union_groups (e
->src
, e
->dest
);
1456 /* And now the rest. */
1457 for (i
= 0; i
< num_edges
; i
++)
1459 edge e
= INDEX_EDGE (el
, i
);
1460 if (!EDGE_INFO (e
)->ignore
1461 && find_group (e
->src
) != find_group (e
->dest
))
1464 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1465 e
->src
->index
, e
->dest
->index
);
1466 EDGE_INFO (e
)->on_tree
= 1;
1467 union_groups (e
->src
, e
->dest
);
1471 clear_aux_for_blocks ();
1474 /* Perform file-level initialization for branch-prob processing. */
1477 init_branch_prob (void)
1481 total_num_blocks
= 0;
1482 total_num_edges
= 0;
1483 total_num_edges_ignored
= 0;
1484 total_num_edges_instrumented
= 0;
1485 total_num_blocks_created
= 0;
1486 total_num_passes
= 0;
1487 total_num_times_called
= 0;
1488 total_num_branches
= 0;
1489 for (i
= 0; i
< 20; i
++)
1490 total_hist_br_prob
[i
] = 0;
1493 /* Performs file-level cleanup after branch-prob processing
1497 end_branch_prob (void)
1501 fprintf (dump_file
, "\n");
1502 fprintf (dump_file
, "Total number of blocks: %d\n",
1504 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1505 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1506 total_num_edges_ignored
);
1507 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1508 total_num_edges_instrumented
);
1509 fprintf (dump_file
, "Total number of blocks created: %d\n",
1510 total_num_blocks_created
);
1511 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1513 if (total_num_times_called
!= 0)
1514 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1515 (total_num_passes
+ (total_num_times_called
>> 1))
1516 / total_num_times_called
);
1517 fprintf (dump_file
, "Total number of branches: %d\n",
1518 total_num_branches
);
1519 if (total_num_branches
)
1523 for (i
= 0; i
< 10; i
++)
1524 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1525 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1526 / total_num_branches
, 5*i
, 5*i
+5);