1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2017 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"
60 #include "diagnostic-core.h"
62 #include "value-prof.h"
63 #include "gimple-iterator.h"
70 /* Map from BBs/edges to gcov counters. */
71 vec
<gcov_type
> bb_gcov_counts
;
72 hash_map
<edge
,gcov_type
> *edge_gcov_counts
;
74 struct bb_profile_info
{
75 unsigned int count_valid
: 1;
77 /* Number of successor and predecessor edges. */
82 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
85 /* Counter summary from the last set of coverage counts read. */
87 const struct gcov_ctr_summary
*profile_info
;
89 /* Counter working set information computed from the current counter
90 summary. Not initialized unless profile_info summary is non-NULL. */
91 static gcov_working_set_t gcov_working_sets
[NUM_GCOV_WORKING_SETS
];
93 /* Collect statistics on the performance of this pass for the entire source
96 static int total_num_blocks
;
97 static int total_num_edges
;
98 static int total_num_edges_ignored
;
99 static int total_num_edges_instrumented
;
100 static int total_num_blocks_created
;
101 static int total_num_passes
;
102 static int total_num_times_called
;
103 static int total_hist_br_prob
[20];
104 static int total_num_branches
;
106 /* Helper function to update gcov_working_sets. */
108 void add_working_set (gcov_working_set_t
*set
) {
110 for (; i
< NUM_GCOV_WORKING_SETS
; i
++)
111 gcov_working_sets
[i
] = set
[i
];
114 /* Forward declarations. */
115 static void find_spanning_tree (struct edge_list
*);
117 /* Add edge instrumentation code to the entire insn chain.
119 F is the first insn of the chain.
120 NUM_BLOCKS is the number of basic blocks found in F. */
123 instrument_edges (struct edge_list
*el
)
125 unsigned num_instr_edges
= 0;
126 int num_edges
= NUM_EDGES (el
);
129 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
134 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
136 struct edge_profile_info
*inf
= EDGE_INFO (e
);
138 if (!inf
->ignore
&& !inf
->on_tree
)
140 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
142 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
143 e
->src
->index
, e
->dest
->index
,
144 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
145 gimple_gen_edge_profiler (num_instr_edges
++, e
);
150 total_num_blocks_created
+= num_edges
;
152 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
153 return num_instr_edges
;
156 /* Add code to measure histograms for values in list VALUES. */
158 instrument_values (histogram_values values
)
162 /* Emit code to generate the histograms before the insns. */
164 for (i
= 0; i
< values
.length (); i
++)
166 histogram_value hist
= values
[i
];
167 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
169 if (!coverage_counter_alloc (t
, hist
->n_counters
))
174 case HIST_TYPE_INTERVAL
:
175 gimple_gen_interval_profiler (hist
, t
, 0);
179 gimple_gen_pow2_profiler (hist
, t
, 0);
182 case HIST_TYPE_SINGLE_VALUE
:
183 gimple_gen_one_value_profiler (hist
, t
, 0);
186 case HIST_TYPE_INDIR_CALL
:
187 case HIST_TYPE_INDIR_CALL_TOPN
:
188 gimple_gen_ic_profiler (hist
, t
, 0);
191 case HIST_TYPE_AVERAGE
:
192 gimple_gen_average_profiler (hist
, t
, 0);
196 gimple_gen_ior_profiler (hist
, t
, 0);
199 case HIST_TYPE_TIME_PROFILE
:
200 gimple_gen_time_profiler (t
, 0);
210 /* Fill the working set information into the profile_info structure. */
213 get_working_sets (void)
215 unsigned ws_ix
, pctinc
, pct
;
216 gcov_working_set_t
*ws_info
;
221 compute_working_sets (profile_info
, gcov_working_sets
);
225 fprintf (dump_file
, "Counter working sets:\n");
226 /* Multiply the percentage by 100 to avoid float. */
227 pctinc
= 100 * 100 / NUM_GCOV_WORKING_SETS
;
228 for (ws_ix
= 0, pct
= pctinc
; ws_ix
< NUM_GCOV_WORKING_SETS
;
229 ws_ix
++, pct
+= pctinc
)
231 if (ws_ix
== NUM_GCOV_WORKING_SETS
- 1)
233 ws_info
= &gcov_working_sets
[ws_ix
];
234 /* Print out the percentage using int arithmatic to avoid float. */
235 fprintf (dump_file
, "\t\t%u.%02u%%: num counts=%u, min counter="
237 pct
/ 100, pct
- (pct
/ 100 * 100),
238 ws_info
->num_counters
,
239 (int64_t)ws_info
->min_counter
);
244 /* Given a the desired percentage of the full profile (sum_all from the
245 summary), multiplied by 10 to avoid float in PCT_TIMES_10, returns
246 the corresponding working set information. If an exact match for
247 the percentage isn't found, the closest value is used. */
250 find_working_set (unsigned pct_times_10
)
255 gcc_assert (pct_times_10
<= 1000);
256 if (pct_times_10
>= 999)
257 return &gcov_working_sets
[NUM_GCOV_WORKING_SETS
- 1];
258 i
= pct_times_10
* NUM_GCOV_WORKING_SETS
/ 1000;
260 return &gcov_working_sets
[0];
261 return &gcov_working_sets
[i
- 1];
264 /* Computes hybrid profile for all matching entries in da_file.
266 CFG_CHECKSUM is the precomputed checksum for the CFG. */
269 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
271 unsigned num_edges
= 0;
275 /* Count the edges to be (possibly) instrumented. */
276 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
281 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
282 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
286 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, num_edges
, cfg_checksum
,
287 lineno_checksum
, &profile_info
);
293 if (dump_file
&& profile_info
)
294 fprintf (dump_file
, "Merged %u profiles with maximal count %u.\n",
295 profile_info
->runs
, (unsigned) profile_info
->sum_max
);
302 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
306 FOR_EACH_EDGE (e
, ei
, edges
)
308 if (!EDGE_INFO (e
)->ignore
)
310 if (edge_gcov_count (e
) < 0
311 && (!(e
->flags
& EDGE_FAKE
)
312 || !block_ends_with_call_p (e
->src
)))
317 "Edge %i->%i is inconsistent, count%" PRId64
,
318 e
->src
->index
, e
->dest
->index
, edge_gcov_count (e
));
319 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
320 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
330 correct_negative_edge_counts (void)
336 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
338 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
340 if (edge_gcov_count (e
) < 0)
341 edge_gcov_count (e
) = 0;
346 /* Check consistency.
347 Return true if inconsistency is found. */
349 is_inconsistent (void)
352 bool inconsistent
= false;
353 FOR_EACH_BB_FN (bb
, cfun
)
355 inconsistent
|= is_edge_inconsistent (bb
->preds
);
356 if (!dump_file
&& inconsistent
)
358 inconsistent
|= is_edge_inconsistent (bb
->succs
);
359 if (!dump_file
&& inconsistent
)
361 if (bb_gcov_count (bb
) < 0)
365 fprintf (dump_file
, "BB %i count is negative "
369 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
373 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->preds
))
377 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
378 "%" PRId64
" should be %" PRId64
,
381 sum_edge_counts (bb
->preds
));
382 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
386 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->succs
) &&
387 ! (find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
)) != NULL
388 && block_ends_with_call_p (bb
)))
392 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
393 "%" PRId64
" should be %" PRId64
,
396 sum_edge_counts (bb
->succs
));
397 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
401 if (!dump_file
&& inconsistent
)
408 /* Set each basic block count to the sum of its outgoing edge counts */
413 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
415 bb_gcov_count (bb
) = sum_edge_counts (bb
->succs
);
416 gcc_assert (bb_gcov_count (bb
) >= 0);
420 /* Reads profile data and returns total number of edge counts read */
422 read_profile_edge_counts (gcov_type
*exec_counts
)
426 int exec_counts_pos
= 0;
427 /* For each edge not on the spanning tree, set its execution count from
429 /* The first count in the .da file is the number of times that the function
430 was entered. This is the exec_count for block zero. */
432 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
437 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
438 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
443 edge_gcov_count (e
) = exec_counts
[exec_counts_pos
++];
444 if (edge_gcov_count (e
) > profile_info
->sum_max
)
446 if (flag_profile_correction
)
448 static bool informed
= 0;
449 if (dump_enabled_p () && !informed
)
450 dump_printf_loc (MSG_NOTE
, input_location
,
451 "corrupted profile info: edge count"
452 " exceeds maximal count\n");
456 error ("corrupted profile info: edge from %i to %i exceeds maximal count",
457 bb
->index
, e
->dest
->index
);
461 edge_gcov_count (e
) = 0;
463 EDGE_INFO (e
)->count_valid
= 1;
464 BB_INFO (bb
)->succ_count
--;
465 BB_INFO (e
->dest
)->pred_count
--;
468 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
469 bb
->index
, e
->dest
->index
);
470 fprintf (dump_file
, "%" PRId64
,
471 (int64_t) edge_gcov_count (e
));
479 #define OVERLAP_BASE 10000
481 /* Compare the static estimated profile to the actual profile, and
482 return the "degree of overlap" measure between them.
484 Degree of overlap is a number between 0 and OVERLAP_BASE. It is
485 the sum of each basic block's minimum relative weights between
486 two profiles. And overlap of OVERLAP_BASE means two profiles are
490 compute_frequency_overlap (void)
492 gcov_type count_total
= 0, freq_total
= 0;
496 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
498 count_total
+= bb_gcov_count (bb
);
499 freq_total
+= bb
->frequency
;
502 if (count_total
== 0 || freq_total
== 0)
505 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
506 overlap
+= MIN (bb_gcov_count (bb
) * OVERLAP_BASE
/ count_total
,
507 bb
->frequency
* OVERLAP_BASE
/ freq_total
);
512 /* Compute the branch probabilities for the various branches.
513 Annotate them accordingly.
515 CFG_CHECKSUM is the precomputed checksum for the CFG. */
518 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
525 int hist_br_prob
[20];
527 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
528 int inconsistent
= 0;
530 /* Very simple sanity checks so we catch bugs in our profiling code. */
534 bb_gcov_counts
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
535 edge_gcov_counts
= new hash_map
<edge
,gcov_type
>;
537 if (profile_info
->sum_all
< profile_info
->sum_max
)
539 error ("corrupted profile info: sum_all is smaller than sum_max");
543 /* Attach extra info block to each bb. */
544 alloc_aux_for_blocks (sizeof (struct bb_profile_info
));
545 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
550 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
551 if (!EDGE_INFO (e
)->ignore
)
552 BB_INFO (bb
)->succ_count
++;
553 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
554 if (!EDGE_INFO (e
)->ignore
)
555 BB_INFO (bb
)->pred_count
++;
558 /* Avoid predicting entry on exit nodes. */
559 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun
))->succ_count
= 2;
560 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->pred_count
= 2;
562 num_edges
= read_profile_edge_counts (exec_counts
);
565 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
567 /* For every block in the file,
568 - if every exit/entrance edge has a known count, then set the block count
569 - if the block count is known, and every exit/entrance edge but one has
570 a known execution count, then set the count of the remaining edge
572 As edge counts are set, decrement the succ/pred count, but don't delete
573 the edge, that way we can easily tell when all edges are known, or only
574 one edge is unknown. */
576 /* The order that the basic blocks are iterated through is important.
577 Since the code that finds spanning trees starts with block 0, low numbered
578 edges are put on the spanning tree in preference to high numbered edges.
579 Hence, most instrumented edges are at the end. Graph solving works much
580 faster if we propagate numbers from the end to the start.
582 This takes an average of slightly more than 3 passes. */
590 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, prev_bb
)
592 struct bb_profile_info
*bi
= BB_INFO (bb
);
593 if (! bi
->count_valid
)
595 if (bi
->succ_count
== 0)
601 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
602 total
+= edge_gcov_count (e
);
603 bb_gcov_count (bb
) = total
;
607 else if (bi
->pred_count
== 0)
613 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
614 total
+= edge_gcov_count (e
);
615 bb_gcov_count (bb
) = total
;
622 if (bi
->succ_count
== 1)
628 /* One of the counts will be invalid, but it is zero,
629 so adding it in also doesn't hurt. */
630 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
631 total
+= edge_gcov_count (e
);
633 /* Search for the invalid edge, and set its count. */
634 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
635 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
638 /* Calculate count for remaining edge by conservation. */
639 total
= bb_gcov_count (bb
) - total
;
642 EDGE_INFO (e
)->count_valid
= 1;
643 edge_gcov_count (e
) = total
;
646 BB_INFO (e
->dest
)->pred_count
--;
649 if (bi
->pred_count
== 1)
655 /* One of the counts will be invalid, but it is zero,
656 so adding it in also doesn't hurt. */
657 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
658 total
+= edge_gcov_count (e
);
660 /* Search for the invalid edge, and set its count. */
661 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
662 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
665 /* Calculate count for remaining edge by conservation. */
666 total
= bb_gcov_count (bb
) - total
+ edge_gcov_count (e
);
669 EDGE_INFO (e
)->count_valid
= 1;
670 edge_gcov_count (e
) = total
;
673 BB_INFO (e
->src
)->succ_count
--;
681 int overlap
= compute_frequency_overlap ();
682 gimple_dump_cfg (dump_file
, dump_flags
);
683 fprintf (dump_file
, "Static profile overlap: %d.%d%%\n",
684 overlap
/ (OVERLAP_BASE
/ 100),
685 overlap
% (OVERLAP_BASE
/ 100));
688 total_num_passes
+= passes
;
690 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
692 /* If the graph has been correctly solved, every block will have a
693 succ and pred count of zero. */
694 FOR_EACH_BB_FN (bb
, cfun
)
696 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
699 /* Check for inconsistent basic block counts */
700 inconsistent
= is_inconsistent ();
704 if (flag_profile_correction
)
706 /* Inconsistency detected. Make it flow-consistent. */
707 static int informed
= 0;
708 if (dump_enabled_p () && informed
== 0)
711 dump_printf_loc (MSG_NOTE
, input_location
,
712 "correcting inconsistent profile data\n");
714 correct_negative_edge_counts ();
715 /* Set bb counts to the sum of the outgoing edge counts */
718 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
722 error ("corrupted profile info: profile data is not flow-consistent");
725 /* For every edge, calculate its branch probability and add a reg_note
726 to the branch insn to indicate this. */
728 for (i
= 0; i
< 20; i
++)
732 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
737 if (bb_gcov_count (bb
) < 0)
739 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
740 bb
->index
, (int)bb_gcov_count (bb
));
741 bb_gcov_count (bb
) = 0;
743 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
745 /* Function may return twice in the cased the called function is
746 setjmp or calls fork, but we can't represent this by extra
747 edge from the entry, since extra edge from the exit is
748 already present. We get negative frequency from the entry
750 if ((edge_gcov_count (e
) < 0
751 && e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
752 || (edge_gcov_count (e
) > bb_gcov_count (bb
)
753 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
755 if (block_ends_with_call_p (bb
))
756 edge_gcov_count (e
) = edge_gcov_count (e
) < 0
757 ? 0 : bb_gcov_count (bb
);
759 if (edge_gcov_count (e
) < 0
760 || edge_gcov_count (e
) > bb_gcov_count (bb
))
762 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
763 e
->src
->index
, e
->dest
->index
,
764 (int)edge_gcov_count (e
));
765 edge_gcov_count (e
) = bb_gcov_count (bb
) / 2;
768 if (bb_gcov_count (bb
))
770 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
771 e
->probability
= GCOV_COMPUTE_SCALE (edge_gcov_count (e
),
773 if (bb
->index
>= NUM_FIXED_BLOCKS
774 && block_ends_with_condjump_p (bb
)
775 && EDGE_COUNT (bb
->succs
) >= 2)
781 /* Find the branch edge. It is possible that we do have fake
783 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
784 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
787 prob
= e
->probability
;
788 index
= prob
* 20 / REG_BR_PROB_BASE
;
792 hist_br_prob
[index
]++;
797 /* As a last resort, distribute the probabilities evenly.
798 Use simple heuristics that if there are normal edges,
799 give all abnormals frequency of 0, otherwise distribute the
800 frequency over abnormals (this is the case of noreturn
802 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
806 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
807 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
811 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
812 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
813 e
->probability
= REG_BR_PROB_BASE
/ total
;
819 total
+= EDGE_COUNT (bb
->succs
);
820 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
821 e
->probability
= REG_BR_PROB_BASE
/ total
;
823 if (bb
->index
>= NUM_FIXED_BLOCKS
824 && block_ends_with_condjump_p (bb
)
825 && EDGE_COUNT (bb
->succs
) >= 2)
830 FOR_ALL_BB_FN (bb
, cfun
)
835 bb
->count
= profile_count::from_gcov_type (bb_gcov_count (bb
));
836 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
837 e
->count
= profile_count::from_gcov_type (edge_gcov_count (e
));
839 bb_gcov_counts
.release ();
840 delete edge_gcov_counts
;
841 edge_gcov_counts
= NULL
;
847 fprintf (dump_file
, "%d branches\n", num_branches
);
849 for (i
= 0; i
< 10; i
++)
850 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
851 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
854 total_num_branches
+= num_branches
;
855 for (i
= 0; i
< 20; i
++)
856 total_hist_br_prob
[i
] += hist_br_prob
[i
];
858 fputc ('\n', dump_file
);
859 fputc ('\n', dump_file
);
862 free_aux_for_blocks ();
865 /* Load value histograms values whose description is stored in VALUES array
868 CFG_CHECKSUM is the precomputed checksum for the CFG. */
871 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
872 unsigned lineno_checksum
)
874 unsigned i
, j
, t
, any
;
875 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
876 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
877 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
878 gcov_type
*aact_count
;
879 struct cgraph_node
*node
;
881 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
882 n_histogram_counters
[t
] = 0;
884 for (i
= 0; i
< values
.length (); i
++)
886 histogram_value hist
= values
[i
];
887 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
891 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
893 if (!n_histogram_counters
[t
])
895 histogram_counts
[t
] = NULL
;
899 histogram_counts
[t
] =
900 get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
901 n_histogram_counters
[t
], cfg_checksum
,
902 lineno_checksum
, NULL
);
903 if (histogram_counts
[t
])
905 act_count
[t
] = histogram_counts
[t
];
910 for (i
= 0; i
< values
.length (); i
++)
912 histogram_value hist
= values
[i
];
913 gimple
*stmt
= hist
->hvalue
.stmt
;
915 t
= (int) hist
->type
;
917 aact_count
= act_count
[t
];
920 act_count
[t
] += hist
->n_counters
;
922 gimple_add_histogram_value (cfun
, stmt
, hist
);
923 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
924 for (j
= 0; j
< hist
->n_counters
; j
++)
926 hist
->hvalue
.counters
[j
] = aact_count
[j
];
928 hist
->hvalue
.counters
[j
] = 0;
930 /* Time profiler counter is not related to any statement,
931 so that we have to read the counter and set the value to
932 the corresponding call graph node. */
933 if (hist
->type
== HIST_TYPE_TIME_PROFILE
)
935 node
= cgraph_node::get (hist
->fun
->decl
);
936 node
->tp_first_run
= hist
->hvalue
.counters
[0];
939 fprintf (dump_file
, "Read tp_first_run: %d\n", node
->tp_first_run
);
943 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
944 free (histogram_counts
[t
]);
947 /* When passed NULL as file_name, initialize.
948 When passed something else, output the necessary commands to change
949 line to LINE and offset to FILE_NAME. */
951 output_location (char const *file_name
, int line
,
952 gcov_position_t
*offset
, basic_block bb
)
954 static char const *prev_file_name
;
955 static int prev_line
;
956 bool name_differs
, line_differs
;
960 prev_file_name
= NULL
;
965 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
966 line_differs
= prev_line
!= line
;
970 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
971 gcov_write_unsigned (bb
->index
);
972 name_differs
= line_differs
= true;
975 /* If this is a new source file, then output the
976 file's name to the .bb file. */
979 prev_file_name
= file_name
;
980 gcov_write_unsigned (0);
981 gcov_write_filename (prev_file_name
);
985 gcov_write_unsigned (line
);
990 /* Instrument and/or analyze program behavior based on program the CFG.
992 This function creates a representation of the control flow graph (of
993 the function being compiled) that is suitable for the instrumentation
994 of edges and/or converting measured edge counts to counts on the
997 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
998 the flow graph that are needed to reconstruct the dynamic behavior of the
999 flow graph. This data is written to the gcno file for gcov.
1001 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1002 information from the gcda file containing edge count information from
1003 previous executions of the function being compiled. In this case, the
1004 control flow graph is annotated with actual execution counts by
1005 compute_branch_probabilities().
1007 Main entry point of this file. */
1014 unsigned num_edges
, ignored_edges
;
1015 unsigned num_instrumented
;
1016 struct edge_list
*el
;
1017 histogram_values values
= histogram_values ();
1018 unsigned cfg_checksum
, lineno_checksum
;
1020 total_num_times_called
++;
1022 flow_call_edges_add (NULL
);
1023 add_noreturn_fake_exit_edges ();
1025 /* We can't handle cyclic regions constructed using abnormal edges.
1026 To avoid these we replace every source of abnormal edge by a fake
1027 edge from entry node and every destination by fake edge to exit.
1028 This keeps graph acyclic and our calculation exact for all normal
1029 edges except for exit and entrance ones.
1031 We also add fake exit edges for each call and asm statement in the
1032 basic, since it may not return. */
1034 FOR_EACH_BB_FN (bb
, cfun
)
1036 int need_exit_edge
= 0, need_entry_edge
= 0;
1037 int have_exit_edge
= 0, have_entry_edge
= 0;
1041 /* Functions returning multiple times are not handled by extra edges.
1042 Instead we simply allow negative counts on edges from exit to the
1043 block past call and corresponding probabilities. We can't go
1044 with the extra edges because that would result in flowgraph that
1045 needs to have fake edges outside the spanning tree. */
1047 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1049 gimple_stmt_iterator gsi
;
1050 gimple
*last
= NULL
;
1052 /* It may happen that there are compiler generated statements
1053 without a locus at all. Go through the basic block from the
1054 last to the first statement looking for a locus. */
1055 for (gsi
= gsi_last_nondebug_bb (bb
);
1057 gsi_prev_nondebug (&gsi
))
1059 last
= gsi_stmt (gsi
);
1060 if (!RESERVED_LOCATION_P (gimple_location (last
)))
1064 /* Edge with goto locus might get wrong coverage info unless
1065 it is the only edge out of BB.
1066 Don't do that when the locuses match, so
1067 if (blah) goto something;
1068 is not computed twice. */
1070 && gimple_has_location (last
)
1071 && !RESERVED_LOCATION_P (e
->goto_locus
)
1072 && !single_succ_p (bb
)
1073 && (LOCATION_FILE (e
->goto_locus
)
1074 != LOCATION_FILE (gimple_location (last
))
1075 || (LOCATION_LINE (e
->goto_locus
)
1076 != LOCATION_LINE (gimple_location (last
)))))
1078 basic_block new_bb
= split_edge (e
);
1079 edge ne
= single_succ_edge (new_bb
);
1080 ne
->goto_locus
= e
->goto_locus
;
1082 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1083 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1085 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1088 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1090 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1091 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1092 need_entry_edge
= 1;
1093 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1094 have_entry_edge
= 1;
1097 if (need_exit_edge
&& !have_exit_edge
)
1100 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1102 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
1104 if (need_entry_edge
&& !have_entry_edge
)
1107 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1109 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
, EDGE_FAKE
);
1110 /* Avoid bbs that have both fake entry edge and also some
1111 exit edge. One of those edges wouldn't be added to the
1112 spanning tree, but we can't instrument any of them. */
1113 if (have_exit_edge
|| need_exit_edge
)
1115 gimple_stmt_iterator gsi
;
1118 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
1119 gcc_checking_assert (!gsi_end_p (gsi
));
1120 first
= gsi_stmt (gsi
);
1121 /* Don't split the bbs containing __builtin_setjmp_receiver
1122 or ABNORMAL_DISPATCHER calls. These are very
1123 special and don't expect anything to be inserted before
1125 if (is_gimple_call (first
)
1126 && (gimple_call_builtin_p (first
, BUILT_IN_SETJMP_RECEIVER
)
1127 || (gimple_call_flags (first
) & ECF_RETURNS_TWICE
)
1128 || (gimple_call_internal_p (first
)
1129 && (gimple_call_internal_fn (first
)
1130 == IFN_ABNORMAL_DISPATCHER
))))
1134 fprintf (dump_file
, "Splitting bb %i after labels\n",
1136 split_block_after_labels (bb
);
1141 el
= create_edge_list ();
1142 num_edges
= NUM_EDGES (el
);
1143 alloc_aux_for_edges (sizeof (struct edge_profile_info
));
1145 /* The basic blocks are expected to be numbered sequentially. */
1149 for (i
= 0 ; i
< num_edges
; i
++)
1151 edge e
= INDEX_EDGE (el
, i
);
1153 /* Mark edges we've replaced by fake edges above as ignored. */
1154 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1155 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1156 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1158 EDGE_INFO (e
)->ignore
= 1;
1163 /* Create spanning tree from basic block graph, mark each edge that is
1164 on the spanning tree. We insert as many abnormal and critical edges
1165 as possible to minimize number of edge splits necessary. */
1167 find_spanning_tree (el
);
1169 /* Fake edges that are not on the tree will not be instrumented, so
1170 mark them ignored. */
1171 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1173 edge e
= INDEX_EDGE (el
, i
);
1174 struct edge_profile_info
*inf
= EDGE_INFO (e
);
1176 if (inf
->ignore
|| inf
->on_tree
)
1178 else if (e
->flags
& EDGE_FAKE
)
1187 total_num_blocks
+= n_basic_blocks_for_fn (cfun
);
1189 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks_for_fn (cfun
));
1191 total_num_edges
+= num_edges
;
1193 fprintf (dump_file
, "%d edges\n", num_edges
);
1195 total_num_edges_ignored
+= ignored_edges
;
1197 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1199 total_num_edges_instrumented
+= num_instrumented
;
1201 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1203 /* Compute two different checksums. Note that we want to compute
1204 the checksum in only once place, since it depends on the shape
1205 of the control flow which can change during
1206 various transformations. */
1207 cfg_checksum
= coverage_compute_cfg_checksum (cfun
);
1208 lineno_checksum
= coverage_compute_lineno_checksum ();
1210 /* Write the data from which gcov can reconstruct the basic block
1211 graph and function line numbers (the gcno file). */
1212 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1214 gcov_position_t offset
;
1216 /* Basic block flags */
1217 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1218 gcov_write_unsigned (n_basic_blocks_for_fn (cfun
));
1219 gcov_write_length (offset
);
1222 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1223 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1228 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1229 gcov_write_unsigned (bb
->index
);
1231 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1233 struct edge_profile_info
*i
= EDGE_INFO (e
);
1236 unsigned flag_bits
= 0;
1239 flag_bits
|= GCOV_ARC_ON_TREE
;
1240 if (e
->flags
& EDGE_FAKE
)
1241 flag_bits
|= GCOV_ARC_FAKE
;
1242 if (e
->flags
& EDGE_FALLTHRU
)
1243 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1244 /* On trees we don't have fallthru flags, but we can
1245 recompute them from CFG shape. */
1246 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1247 && e
->src
->next_bb
== e
->dest
)
1248 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1250 gcov_write_unsigned (e
->dest
->index
);
1251 gcov_write_unsigned (flag_bits
);
1255 gcov_write_length (offset
);
1259 /* Initialize the output. */
1260 output_location (NULL
, 0, NULL
, NULL
);
1262 FOR_EACH_BB_FN (bb
, cfun
)
1264 gimple_stmt_iterator gsi
;
1265 gcov_position_t offset
= 0;
1267 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
1269 expanded_location curr_location
=
1270 expand_location (DECL_SOURCE_LOCATION (current_function_decl
));
1271 output_location (curr_location
.file
, curr_location
.line
,
1275 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1277 gimple
*stmt
= gsi_stmt (gsi
);
1278 if (!RESERVED_LOCATION_P (gimple_location (stmt
)))
1279 output_location (gimple_filename (stmt
), gimple_lineno (stmt
),
1283 /* Notice GOTO expressions eliminated while constructing the CFG. */
1284 if (single_succ_p (bb
)
1285 && !RESERVED_LOCATION_P (single_succ_edge (bb
)->goto_locus
))
1287 expanded_location curr_location
1288 = expand_location (single_succ_edge (bb
)->goto_locus
);
1289 output_location (curr_location
.file
, curr_location
.line
,
1295 /* A file of NULL indicates the end of run. */
1296 gcov_write_unsigned (0);
1297 gcov_write_string (NULL
);
1298 gcov_write_length (offset
);
1303 if (flag_profile_values
)
1304 gimple_find_values_to_profile (&values
);
1306 if (flag_branch_probabilities
)
1308 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1309 if (flag_profile_values
)
1310 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1313 remove_fake_edges ();
1315 /* For each edge not on the spanning tree, add counting code. */
1316 if (profile_arc_flag
1317 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1319 unsigned n_instrumented
;
1321 gimple_init_gcov_profiler ();
1323 n_instrumented
= instrument_edges (el
);
1325 gcc_assert (n_instrumented
== num_instrumented
);
1327 if (flag_profile_values
)
1328 instrument_values (values
);
1330 /* Commit changes done by instrumentation. */
1331 gsi_commit_edge_inserts ();
1334 free_aux_for_edges ();
1337 free_edge_list (el
);
1338 coverage_end_function (lineno_checksum
, cfg_checksum
);
1339 if (flag_branch_probabilities
&& profile_info
)
1342 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1343 report_predictor_hitrates ();
1344 profile_status_for_fn (cfun
) = PROFILE_READ
;
1346 /* At this moment we have precise loop iteration count estimates.
1347 Record them to loop structure before the profile gets out of date. */
1348 FOR_EACH_LOOP (loop
, 0)
1349 if (loop
->header
->count
> 0)
1351 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
1352 widest_int bound
= gcov_type_to_wide_int (nit
);
1353 loop
->any_estimate
= false;
1354 record_niter_bound (loop
, bound
, true, false);
1356 compute_function_frequency ();
1360 /* Union find algorithm implementation for the basic blocks using
1364 find_group (basic_block bb
)
1366 basic_block group
= bb
, bb1
;
1368 while ((basic_block
) group
->aux
!= group
)
1369 group
= (basic_block
) group
->aux
;
1371 /* Compress path. */
1372 while ((basic_block
) bb
->aux
!= group
)
1374 bb1
= (basic_block
) bb
->aux
;
1375 bb
->aux
= (void *) group
;
1382 union_groups (basic_block bb1
, basic_block bb2
)
1384 basic_block bb1g
= find_group (bb1
);
1385 basic_block bb2g
= find_group (bb2
);
1387 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1388 this code is unlikely going to be performance problem anyway. */
1389 gcc_assert (bb1g
!= bb2g
);
1394 /* This function searches all of the edges in the program flow graph, and puts
1395 as many bad edges as possible onto the spanning tree. Bad edges include
1396 abnormals edges, which can't be instrumented at the moment. Since it is
1397 possible for fake edges to form a cycle, we will have to develop some
1398 better way in the future. Also put critical edges to the tree, since they
1399 are more expensive to instrument. */
1402 find_spanning_tree (struct edge_list
*el
)
1405 int num_edges
= NUM_EDGES (el
);
1408 /* We use aux field for standard union-find algorithm. */
1409 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
1412 /* Add fake edge exit to entry we can't instrument. */
1413 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun
), ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1415 /* First add all abnormal edges to the tree unless they form a cycle. Also
1416 add all edges to the exit block to avoid inserting profiling code behind
1417 setting return value from function. */
1418 for (i
= 0; i
< num_edges
; i
++)
1420 edge e
= INDEX_EDGE (el
, i
);
1421 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1422 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1423 && !EDGE_INFO (e
)->ignore
1424 && (find_group (e
->src
) != find_group (e
->dest
)))
1427 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1428 e
->src
->index
, e
->dest
->index
);
1429 EDGE_INFO (e
)->on_tree
= 1;
1430 union_groups (e
->src
, e
->dest
);
1434 /* Now insert all critical edges to the tree unless they form a cycle. */
1435 for (i
= 0; i
< num_edges
; i
++)
1437 edge e
= INDEX_EDGE (el
, i
);
1438 if (EDGE_CRITICAL_P (e
) && !EDGE_INFO (e
)->ignore
1439 && find_group (e
->src
) != find_group (e
->dest
))
1442 fprintf (dump_file
, "Critical edge %d to %d put to tree\n",
1443 e
->src
->index
, e
->dest
->index
);
1444 EDGE_INFO (e
)->on_tree
= 1;
1445 union_groups (e
->src
, e
->dest
);
1449 /* And now the rest. */
1450 for (i
= 0; i
< num_edges
; i
++)
1452 edge e
= INDEX_EDGE (el
, i
);
1453 if (!EDGE_INFO (e
)->ignore
1454 && find_group (e
->src
) != find_group (e
->dest
))
1457 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1458 e
->src
->index
, e
->dest
->index
);
1459 EDGE_INFO (e
)->on_tree
= 1;
1460 union_groups (e
->src
, e
->dest
);
1464 clear_aux_for_blocks ();
1467 /* Perform file-level initialization for branch-prob processing. */
1470 init_branch_prob (void)
1474 total_num_blocks
= 0;
1475 total_num_edges
= 0;
1476 total_num_edges_ignored
= 0;
1477 total_num_edges_instrumented
= 0;
1478 total_num_blocks_created
= 0;
1479 total_num_passes
= 0;
1480 total_num_times_called
= 0;
1481 total_num_branches
= 0;
1482 for (i
= 0; i
< 20; i
++)
1483 total_hist_br_prob
[i
] = 0;
1486 /* Performs file-level cleanup after branch-prob processing
1490 end_branch_prob (void)
1494 fprintf (dump_file
, "\n");
1495 fprintf (dump_file
, "Total number of blocks: %d\n",
1497 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1498 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1499 total_num_edges_ignored
);
1500 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1501 total_num_edges_instrumented
);
1502 fprintf (dump_file
, "Total number of blocks created: %d\n",
1503 total_num_blocks_created
);
1504 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1506 if (total_num_times_called
!= 0)
1507 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1508 (total_num_passes
+ (total_num_times_called
>> 1))
1509 / total_num_times_called
);
1510 fprintf (dump_file
, "Total number of branches: %d\n",
1511 total_num_branches
);
1512 if (total_num_branches
)
1516 for (i
= 0; i
< 10; i
++)
1517 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1518 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1519 / total_num_branches
, 5*i
, 5*i
+5);