1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2022 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"
68 #include "file-prefix-map.h"
72 /* Map from BBs/edges to gcov counters. */
73 vec
<gcov_type
> bb_gcov_counts
;
74 hash_map
<edge
,gcov_type
> *edge_gcov_counts
;
76 struct bb_profile_info
{
77 unsigned int count_valid
: 1;
79 /* Number of successor and predecessor edges. */
84 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
87 /* Counter summary from the last set of coverage counts read. */
89 gcov_summary
*profile_info
;
91 /* Collect statistics on the performance of this pass for the entire source
94 static int total_num_blocks
;
95 static int total_num_edges
;
96 static int total_num_edges_ignored
;
97 static int total_num_edges_instrumented
;
98 static int total_num_blocks_created
;
99 static int total_num_passes
;
100 static int total_num_times_called
;
101 static int total_hist_br_prob
[20];
102 static int total_num_branches
;
104 /* Forward declarations. */
105 static void find_spanning_tree (struct edge_list
*);
107 /* Add edge instrumentation code to the entire insn chain.
109 F is the first insn of the chain.
110 NUM_BLOCKS is the number of basic blocks found in F. */
113 instrument_edges (struct edge_list
*el
)
115 unsigned num_instr_edges
= 0;
116 int num_edges
= NUM_EDGES (el
);
119 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
124 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
126 struct edge_profile_info
*inf
= EDGE_INFO (e
);
128 if (!inf
->ignore
&& !inf
->on_tree
)
130 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
132 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
133 e
->src
->index
, e
->dest
->index
,
134 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
135 gimple_gen_edge_profiler (num_instr_edges
++, e
);
140 total_num_blocks_created
+= num_edges
;
142 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
143 return num_instr_edges
;
146 /* Add code to measure histograms for values in list VALUES. */
148 instrument_values (histogram_values values
)
152 /* Emit code to generate the histograms before the insns. */
154 for (i
= 0; i
< values
.length (); i
++)
156 histogram_value hist
= values
[i
];
157 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
159 if (!coverage_counter_alloc (t
, hist
->n_counters
))
164 case HIST_TYPE_INTERVAL
:
165 gimple_gen_interval_profiler (hist
, t
);
169 gimple_gen_pow2_profiler (hist
, t
);
172 case HIST_TYPE_TOPN_VALUES
:
173 gimple_gen_topn_values_profiler (hist
, t
);
176 case HIST_TYPE_INDIR_CALL
:
177 gimple_gen_ic_profiler (hist
, t
);
180 case HIST_TYPE_AVERAGE
:
181 gimple_gen_average_profiler (hist
, t
);
185 gimple_gen_ior_profiler (hist
, t
);
188 case HIST_TYPE_TIME_PROFILE
:
189 gimple_gen_time_profiler (t
);
199 /* Computes hybrid profile for all matching entries in da_file.
201 CFG_CHECKSUM is the precomputed checksum for the CFG. */
204 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
206 unsigned num_edges
= 0;
210 /* Count the edges to be (possibly) instrumented. */
211 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
216 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
217 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
221 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, cfg_checksum
,
222 lineno_checksum
, num_edges
);
230 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
234 FOR_EACH_EDGE (e
, ei
, edges
)
236 if (!EDGE_INFO (e
)->ignore
)
238 if (edge_gcov_count (e
) < 0
239 && (!(e
->flags
& EDGE_FAKE
)
240 || !block_ends_with_call_p (e
->src
)))
245 "Edge %i->%i is inconsistent, count%" PRId64
,
246 e
->src
->index
, e
->dest
->index
, edge_gcov_count (e
));
247 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
248 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
258 correct_negative_edge_counts (void)
264 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
266 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
268 if (edge_gcov_count (e
) < 0)
269 edge_gcov_count (e
) = 0;
274 /* Check consistency.
275 Return true if inconsistency is found. */
277 is_inconsistent (void)
280 bool inconsistent
= false;
281 FOR_EACH_BB_FN (bb
, cfun
)
283 inconsistent
|= is_edge_inconsistent (bb
->preds
);
284 if (!dump_file
&& inconsistent
)
286 inconsistent
|= is_edge_inconsistent (bb
->succs
);
287 if (!dump_file
&& inconsistent
)
289 if (bb_gcov_count (bb
) < 0)
293 fprintf (dump_file
, "BB %i count is negative "
297 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
301 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->preds
))
305 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
306 "%" PRId64
" should be %" PRId64
,
309 sum_edge_counts (bb
->preds
));
310 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
314 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->succs
) &&
315 ! (find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
)) != NULL
316 && block_ends_with_call_p (bb
)))
320 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
321 "%" PRId64
" should be %" PRId64
,
324 sum_edge_counts (bb
->succs
));
325 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
329 if (!dump_file
&& inconsistent
)
336 /* Set each basic block count to the sum of its outgoing edge counts */
341 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
343 bb_gcov_count (bb
) = sum_edge_counts (bb
->succs
);
344 gcc_assert (bb_gcov_count (bb
) >= 0);
348 /* Reads profile data and returns total number of edge counts read */
350 read_profile_edge_counts (gcov_type
*exec_counts
)
354 int exec_counts_pos
= 0;
355 /* For each edge not on the spanning tree, set its execution count from
357 /* The first count in the .da file is the number of times that the function
358 was entered. This is the exec_count for block zero. */
360 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
365 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
366 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
370 edge_gcov_count (e
) = exec_counts
[exec_counts_pos
++];
372 edge_gcov_count (e
) = 0;
374 EDGE_INFO (e
)->count_valid
= 1;
375 BB_INFO (bb
)->succ_count
--;
376 BB_INFO (e
->dest
)->pred_count
--;
379 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
380 bb
->index
, e
->dest
->index
);
381 fprintf (dump_file
, "%" PRId64
,
382 (int64_t) edge_gcov_count (e
));
390 /* BB statistics comparing guessed frequency of BB with feedback. */
395 double guessed
, feedback
;
399 /* Compare limit_tuple intervals by first item in descending order. */
402 cmp_stats (const void *ptr1
, const void *ptr2
)
404 const bb_stats
*p1
= (const bb_stats
*)ptr1
;
405 const bb_stats
*p2
= (const bb_stats
*)ptr2
;
407 if (p1
->feedback
< p2
->feedback
)
409 else if (p1
->feedback
> p2
->feedback
)
415 /* Compute the branch probabilities for the various branches.
416 Annotate them accordingly.
418 CFG_CHECKSUM is the precomputed checksum for the CFG. */
421 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
428 int hist_br_prob
[20];
430 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
431 int inconsistent
= 0;
433 /* Very simple sanity checks so we catch bugs in our profiling code. */
437 fprintf (dump_file
, "Profile info is missing; giving up\n");
441 bb_gcov_counts
.safe_grow_cleared (last_basic_block_for_fn (cfun
), true);
442 edge_gcov_counts
= new hash_map
<edge
,gcov_type
>;
444 /* Attach extra info block to each bb. */
445 alloc_aux_for_blocks (sizeof (struct bb_profile_info
));
446 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
451 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
452 if (!EDGE_INFO (e
)->ignore
)
453 BB_INFO (bb
)->succ_count
++;
454 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
455 if (!EDGE_INFO (e
)->ignore
)
456 BB_INFO (bb
)->pred_count
++;
459 /* Avoid predicting entry on exit nodes. */
460 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun
))->succ_count
= 2;
461 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->pred_count
= 2;
463 num_edges
= read_profile_edge_counts (exec_counts
);
466 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
468 /* For every block in the file,
469 - if every exit/entrance edge has a known count, then set the block count
470 - if the block count is known, and every exit/entrance edge but one has
471 a known execution count, then set the count of the remaining edge
473 As edge counts are set, decrement the succ/pred count, but don't delete
474 the edge, that way we can easily tell when all edges are known, or only
475 one edge is unknown. */
477 /* The order that the basic blocks are iterated through is important.
478 Since the code that finds spanning trees starts with block 0, low numbered
479 edges are put on the spanning tree in preference to high numbered edges.
480 Hence, most instrumented edges are at the end. Graph solving works much
481 faster if we propagate numbers from the end to the start.
483 This takes an average of slightly more than 3 passes. */
491 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, prev_bb
)
493 struct bb_profile_info
*bi
= BB_INFO (bb
);
494 if (! bi
->count_valid
)
496 if (bi
->succ_count
== 0)
502 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
503 total
+= edge_gcov_count (e
);
504 bb_gcov_count (bb
) = total
;
508 else if (bi
->pred_count
== 0)
514 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
515 total
+= edge_gcov_count (e
);
516 bb_gcov_count (bb
) = total
;
523 if (bi
->succ_count
== 1)
529 /* One of the counts will be invalid, but it is zero,
530 so adding it in also doesn't hurt. */
531 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
532 total
+= edge_gcov_count (e
);
534 /* Search for the invalid edge, and set its count. */
535 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
536 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
539 /* Calculate count for remaining edge by conservation. */
540 total
= bb_gcov_count (bb
) - total
;
543 EDGE_INFO (e
)->count_valid
= 1;
544 edge_gcov_count (e
) = total
;
547 BB_INFO (e
->dest
)->pred_count
--;
550 if (bi
->pred_count
== 1)
556 /* One of the counts will be invalid, but it is zero,
557 so adding it in also doesn't hurt. */
558 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
559 total
+= edge_gcov_count (e
);
561 /* Search for the invalid edge, and set its count. */
562 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
563 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
566 /* Calculate count for remaining edge by conservation. */
567 total
= bb_gcov_count (bb
) - total
+ edge_gcov_count (e
);
570 EDGE_INFO (e
)->count_valid
= 1;
571 edge_gcov_count (e
) = total
;
574 BB_INFO (e
->src
)->succ_count
--;
581 total_num_passes
+= passes
;
583 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
585 /* If the graph has been correctly solved, every block will have a
586 succ and pred count of zero. */
587 FOR_EACH_BB_FN (bb
, cfun
)
589 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
592 /* Check for inconsistent basic block counts */
593 inconsistent
= is_inconsistent ();
597 if (flag_profile_correction
)
599 /* Inconsistency detected. Make it flow-consistent. */
600 static int informed
= 0;
601 if (dump_enabled_p () && informed
== 0)
604 dump_printf_loc (MSG_NOTE
,
605 dump_user_location_t::from_location_t (input_location
),
606 "correcting inconsistent profile data\n");
608 correct_negative_edge_counts ();
609 /* Set bb counts to the sum of the outgoing edge counts */
612 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
616 error ("corrupted profile info: profile data is not flow-consistent");
619 /* For every edge, calculate its branch probability and add a reg_note
620 to the branch insn to indicate this. */
622 for (i
= 0; i
< 20; i
++)
626 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
631 if (bb_gcov_count (bb
) < 0)
633 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
634 bb
->index
, (int)bb_gcov_count (bb
));
635 bb_gcov_count (bb
) = 0;
637 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
639 /* Function may return twice in the cased the called function is
640 setjmp or calls fork, but we can't represent this by extra
641 edge from the entry, since extra edge from the exit is
642 already present. We get negative frequency from the entry
644 if ((edge_gcov_count (e
) < 0
645 && e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
646 || (edge_gcov_count (e
) > bb_gcov_count (bb
)
647 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
649 if (block_ends_with_call_p (bb
))
650 edge_gcov_count (e
) = edge_gcov_count (e
) < 0
651 ? 0 : bb_gcov_count (bb
);
653 if (edge_gcov_count (e
) < 0
654 || edge_gcov_count (e
) > bb_gcov_count (bb
))
656 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
657 e
->src
->index
, e
->dest
->index
,
658 (int)edge_gcov_count (e
));
659 edge_gcov_count (e
) = bb_gcov_count (bb
) / 2;
662 if (bb_gcov_count (bb
))
664 bool set_to_guessed
= false;
665 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
667 bool prev_never
= e
->probability
== profile_probability::never ();
668 e
->probability
= profile_probability::probability_in_gcov_type
669 (edge_gcov_count (e
), bb_gcov_count (bb
));
670 if (e
->probability
== profile_probability::never ()
672 && flag_profile_partial_training
)
673 set_to_guessed
= true;
676 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
677 e
->probability
= e
->probability
.guessed ();
678 if (bb
->index
>= NUM_FIXED_BLOCKS
679 && block_ends_with_condjump_p (bb
)
680 && EDGE_COUNT (bb
->succs
) >= 2)
686 /* Find the branch edge. It is possible that we do have fake
688 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
689 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
692 prob
= e
->probability
.to_reg_br_prob_base ();
693 index
= prob
* 20 / REG_BR_PROB_BASE
;
697 hist_br_prob
[index
]++;
702 /* As a last resort, distribute the probabilities evenly.
703 Use simple heuristics that if there are normal edges,
704 give all abnormals frequency of 0, otherwise distribute the
705 frequency over abnormals (this is the case of noreturn
707 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
711 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
712 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
716 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
717 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
719 = profile_probability::guessed_always ().apply_scale (1, total
);
721 e
->probability
= profile_probability::never ();
725 total
+= EDGE_COUNT (bb
->succs
);
726 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
728 = profile_probability::guessed_always ().apply_scale (1, total
);
730 if (bb
->index
>= NUM_FIXED_BLOCKS
731 && block_ends_with_condjump_p (bb
)
732 && EDGE_COUNT (bb
->succs
) >= 2)
738 && (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
739 || !flag_profile_partial_training
))
740 profile_status_for_fn (cfun
) = PROFILE_READ
;
742 /* If we have real data, use them! */
743 if (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
744 || !flag_guess_branch_prob
)
746 profile_count old_entry_cnt
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
747 auto_vec
<bb_stats
> stats
;
748 double sum1
= 0, sum2
= 0;
750 FOR_ALL_BB_FN (bb
, cfun
)
752 profile_count cnt
= bb
->count
;
753 if (bb_gcov_count (bb
) || !flag_profile_partial_training
)
754 bb
->count
= profile_count::from_gcov_type (bb_gcov_count (bb
));
756 bb
->count
= profile_count::guessed_zero ();
757 if (dump_file
&& bb
->index
>= 0)
759 double freq1
= cnt
.to_sreal_scale (old_entry_cnt
).to_double ();
760 double freq2
= bb
->count
.to_sreal_scale
761 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).
763 bb_stats stat
= {bb
, freq1
, freq2
,
764 (int64_t) bb_gcov_count (bb
)};
765 stats
.safe_push (stat
);
772 double nsum1
= 0, nsum2
= 0;
773 stats
.qsort (cmp_stats
);
774 for (auto stat
: stats
)
776 nsum1
+= stat
.guessed
;
777 nsum2
+= stat
.feedback
;
779 " Basic block %4i guessed freq: %12.3f"
780 " cummulative:%6.2f%% "
781 " feedback freq: %12.3f cummulative:%7.2f%%"
782 " cnt: 10%" PRId64
"\n", stat
.bb
->index
,
791 /* If function was not trained, preserve local estimates including statically
792 determined zero counts. */
793 else if (profile_status_for_fn (cfun
) == PROFILE_READ
794 && !flag_profile_partial_training
)
795 FOR_ALL_BB_FN (bb
, cfun
)
796 if (!(bb
->count
== profile_count::zero ()))
797 bb
->count
= bb
->count
.global0 ();
799 bb_gcov_counts
.release ();
800 delete edge_gcov_counts
;
801 edge_gcov_counts
= NULL
;
803 update_max_bb_count ();
807 fprintf (dump_file
, " Profile feedback for function");
808 fprintf (dump_file
, ((profile_status_for_fn (cfun
) == PROFILE_READ
)
810 : " is not available \n"));
812 fprintf (dump_file
, "%d branches\n", num_branches
);
814 for (i
= 0; i
< 10; i
++)
815 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
816 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
819 total_num_branches
+= num_branches
;
820 for (i
= 0; i
< 20; i
++)
821 total_hist_br_prob
[i
] += hist_br_prob
[i
];
823 fputc ('\n', dump_file
);
824 fputc ('\n', dump_file
);
826 gimple_dump_cfg (dump_file
, TDF_BLOCKS
);
829 free_aux_for_blocks ();
832 /* Sort the histogram value and count for TOPN and INDIR_CALL type. */
835 sort_hist_values (histogram_value hist
)
837 gcc_assert (hist
->type
== HIST_TYPE_TOPN_VALUES
838 || hist
->type
== HIST_TYPE_INDIR_CALL
);
840 int counters
= hist
->hvalue
.counters
[1];
841 for (int i
= 0; i
< counters
- 1; i
++)
842 /* Hist value is organized as:
843 [total_executions, N, value1, counter1, ..., valueN, counterN]
844 Use decrease bubble sort to rearrange it. The sort starts from <value1,
845 counter1> and compares counter first. If counter is same, compares the
846 value, exchange it if small to keep stable. */
849 bool swapped
= false;
850 for (int j
= 0; j
< counters
- 1 - i
; j
++)
852 gcov_type
*p
= &hist
->hvalue
.counters
[2 * j
+ 2];
853 if (p
[1] < p
[3] || (p
[1] == p
[3] && p
[0] < p
[2]))
855 std::swap (p
[0], p
[2]);
856 std::swap (p
[1], p
[3]);
864 /* Load value histograms values whose description is stored in VALUES array
867 CFG_CHECKSUM is the precomputed checksum for the CFG. */
870 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
871 unsigned lineno_checksum
)
873 unsigned i
, j
, t
, any
;
874 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
875 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
876 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
877 gcov_type
*aact_count
;
878 struct cgraph_node
*node
;
880 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
881 n_histogram_counters
[t
] = 0;
883 for (i
= 0; i
< values
.length (); i
++)
885 histogram_value hist
= values
[i
];
886 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
890 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
892 if (!n_histogram_counters
[t
])
894 histogram_counts
[t
] = NULL
;
898 histogram_counts
[t
] = get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
901 n_histogram_counters
[t
]);
902 if (histogram_counts
[t
])
904 act_count
[t
] = histogram_counts
[t
];
909 for (i
= 0; i
< values
.length (); i
++)
911 histogram_value hist
= values
[i
];
912 gimple
*stmt
= hist
->hvalue
.stmt
;
914 t
= (int) hist
->type
;
915 bool topn_p
= (hist
->type
== HIST_TYPE_TOPN_VALUES
916 || hist
->type
== HIST_TYPE_INDIR_CALL
);
918 /* TOP N counter uses variable number of counters. */
923 total_size
= 2 + 2 * act_count
[t
][1];
926 gimple_add_histogram_value (cfun
, stmt
, hist
);
927 hist
->n_counters
= total_size
;
928 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
929 for (j
= 0; j
< hist
->n_counters
; j
++)
931 hist
->hvalue
.counters
[j
] = act_count
[t
][j
];
933 hist
->hvalue
.counters
[j
] = 0;
934 act_count
[t
] += hist
->n_counters
;
935 sort_hist_values (hist
);
939 aact_count
= act_count
[t
];
942 act_count
[t
] += hist
->n_counters
;
944 gimple_add_histogram_value (cfun
, stmt
, hist
);
945 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
946 for (j
= 0; j
< hist
->n_counters
; j
++)
948 hist
->hvalue
.counters
[j
] = aact_count
[j
];
950 hist
->hvalue
.counters
[j
] = 0;
953 /* Time profiler counter is not related to any statement,
954 so that we have to read the counter and set the value to
955 the corresponding call graph node. */
956 if (hist
->type
== HIST_TYPE_TIME_PROFILE
)
958 node
= cgraph_node::get (hist
->fun
->decl
);
959 if (hist
->hvalue
.counters
[0] >= 0
960 && hist
->hvalue
.counters
[0] < INT_MAX
/ 2)
961 node
->tp_first_run
= hist
->hvalue
.counters
[0];
964 if (flag_profile_correction
)
965 error ("corrupted profile info: invalid time profile");
966 node
->tp_first_run
= 0;
969 /* Drop profile for -fprofile-reproducible=multithreaded. */
971 = (flag_profile_reproducible
== PROFILE_REPRODUCIBILITY_MULTITHREADED
);
973 node
->tp_first_run
= 0;
976 fprintf (dump_file
, "Read tp_first_run: %d%s\n", node
->tp_first_run
,
977 drop
? "; ignored because profile reproducibility is "
978 "multi-threaded" : "");
982 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
983 free (histogram_counts
[t
]);
986 /* Location triplet which records a location. */
987 struct location_triplet
989 const char *filename
;
994 /* Traits class for streamed_locations hash set below. */
996 struct location_triplet_hash
: typed_noop_remove
<location_triplet
>
998 typedef location_triplet value_type
;
999 typedef location_triplet compare_type
;
1002 hash (const location_triplet
&ref
)
1004 inchash::hash
hstate (0);
1006 hstate
.add_int (strlen (ref
.filename
));
1007 hstate
.add_int (ref
.lineno
);
1008 hstate
.add_int (ref
.bb_index
);
1009 return hstate
.end ();
1013 equal (const location_triplet
&ref1
, const location_triplet
&ref2
)
1015 return ref1
.lineno
== ref2
.lineno
1016 && ref1
.bb_index
== ref2
.bb_index
1017 && ref1
.filename
!= NULL
1018 && ref2
.filename
!= NULL
1019 && strcmp (ref1
.filename
, ref2
.filename
) == 0;
1023 mark_deleted (location_triplet
&ref
)
1028 static const bool empty_zero_p
= false;
1031 mark_empty (location_triplet
&ref
)
1037 is_deleted (const location_triplet
&ref
)
1039 return ref
.lineno
== -1;
1043 is_empty (const location_triplet
&ref
)
1045 return ref
.lineno
== -2;
1052 /* When passed NULL as file_name, initialize.
1053 When passed something else, output the necessary commands to change
1054 line to LINE and offset to FILE_NAME. */
1056 output_location (hash_set
<location_triplet_hash
> *streamed_locations
,
1057 char const *file_name
, int line
,
1058 gcov_position_t
*offset
, basic_block bb
)
1060 static char const *prev_file_name
;
1061 static int prev_line
;
1062 bool name_differs
, line_differs
;
1064 if (file_name
!= NULL
)
1065 file_name
= remap_profile_filename (file_name
);
1067 location_triplet triplet
;
1068 triplet
.filename
= file_name
;
1069 triplet
.lineno
= line
;
1070 triplet
.bb_index
= bb
? bb
->index
: 0;
1072 if (streamed_locations
->add (triplet
))
1077 prev_file_name
= NULL
;
1082 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
1083 line_differs
= prev_line
!= line
;
1087 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
1088 gcov_write_unsigned (bb
->index
);
1089 name_differs
= line_differs
= true;
1092 /* If this is a new source file, then output the
1093 file's name to the .bb file. */
1096 prev_file_name
= file_name
;
1097 gcov_write_unsigned (0);
1098 gcov_write_filename (prev_file_name
);
1102 gcov_write_unsigned (line
);
1107 /* Helper for qsort so edges get sorted from highest frequency to smallest.
1108 This controls the weight for minimal spanning tree algorithm */
1110 compare_freqs (const void *p1
, const void *p2
)
1112 const_edge e1
= *(const const_edge
*)p1
;
1113 const_edge e2
= *(const const_edge
*)p2
;
1115 /* Critical edges needs to be split which introduce extra control flow.
1116 Make them more heavy. */
1117 int m1
= EDGE_CRITICAL_P (e1
) ? 2 : 1;
1118 int m2
= EDGE_CRITICAL_P (e2
) ? 2 : 1;
1120 if (EDGE_FREQUENCY (e1
) * m1
+ m1
!= EDGE_FREQUENCY (e2
) * m2
+ m2
)
1121 return EDGE_FREQUENCY (e2
) * m2
+ m2
- EDGE_FREQUENCY (e1
) * m1
- m1
;
1122 /* Stabilize sort. */
1123 if (e1
->src
->index
!= e2
->src
->index
)
1124 return e2
->src
->index
- e1
->src
->index
;
1125 return e2
->dest
->index
- e1
->dest
->index
;
1128 /* Only read execution count for thunks. */
1131 read_thunk_profile (struct cgraph_node
*node
)
1133 tree old
= current_function_decl
;
1134 current_function_decl
= node
->decl
;
1135 gcov_type
*counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, 0, 0, 1);
1138 node
->callees
->count
= node
->count
1139 = profile_count::from_gcov_type (counts
[0]);
1142 current_function_decl
= old
;
1147 /* Instrument and/or analyze program behavior based on program the CFG.
1149 This function creates a representation of the control flow graph (of
1150 the function being compiled) that is suitable for the instrumentation
1151 of edges and/or converting measured edge counts to counts on the
1154 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
1155 the flow graph that are needed to reconstruct the dynamic behavior of the
1156 flow graph. This data is written to the gcno file for gcov.
1158 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1159 information from the gcda file containing edge count information from
1160 previous executions of the function being compiled. In this case, the
1161 control flow graph is annotated with actual execution counts by
1162 compute_branch_probabilities().
1164 Main entry point of this file. */
1167 branch_prob (bool thunk
)
1171 unsigned num_edges
, ignored_edges
;
1172 unsigned num_instrumented
;
1173 struct edge_list
*el
;
1174 histogram_values values
= histogram_values ();
1175 unsigned cfg_checksum
, lineno_checksum
;
1177 total_num_times_called
++;
1179 flow_call_edges_add (NULL
);
1180 add_noreturn_fake_exit_edges ();
1182 hash_set
<location_triplet_hash
> streamed_locations
;
1186 /* We can't handle cyclic regions constructed using abnormal edges.
1187 To avoid these we replace every source of abnormal edge by a fake
1188 edge from entry node and every destination by fake edge to exit.
1189 This keeps graph acyclic and our calculation exact for all normal
1190 edges except for exit and entrance ones.
1192 We also add fake exit edges for each call and asm statement in the
1193 basic, since it may not return. */
1195 FOR_EACH_BB_FN (bb
, cfun
)
1197 int need_exit_edge
= 0, need_entry_edge
= 0;
1198 int have_exit_edge
= 0, have_entry_edge
= 0;
1202 /* Functions returning multiple times are not handled by extra edges.
1203 Instead we simply allow negative counts on edges from exit to the
1204 block past call and corresponding probabilities. We can't go
1205 with the extra edges because that would result in flowgraph that
1206 needs to have fake edges outside the spanning tree. */
1208 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1210 gimple_stmt_iterator gsi
;
1211 gimple
*last
= NULL
;
1213 /* It may happen that there are compiler generated statements
1214 without a locus at all. Go through the basic block from the
1215 last to the first statement looking for a locus. */
1216 for (gsi
= gsi_last_nondebug_bb (bb
);
1218 gsi_prev_nondebug (&gsi
))
1220 last
= gsi_stmt (gsi
);
1221 if (!RESERVED_LOCATION_P (gimple_location (last
)))
1225 /* Edge with goto locus might get wrong coverage info unless
1226 it is the only edge out of BB.
1227 Don't do that when the locuses match, so
1228 if (blah) goto something;
1229 is not computed twice. */
1231 && gimple_has_location (last
)
1232 && !RESERVED_LOCATION_P (e
->goto_locus
)
1233 && !single_succ_p (bb
)
1234 && (LOCATION_FILE (e
->goto_locus
)
1235 != LOCATION_FILE (gimple_location (last
))
1236 || (LOCATION_LINE (e
->goto_locus
)
1237 != LOCATION_LINE (gimple_location (last
)))))
1239 basic_block new_bb
= split_edge (e
);
1240 edge ne
= single_succ_edge (new_bb
);
1241 ne
->goto_locus
= e
->goto_locus
;
1243 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1244 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1246 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1249 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1251 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1252 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1253 need_entry_edge
= 1;
1254 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1255 have_entry_edge
= 1;
1258 if (need_exit_edge
&& !have_exit_edge
)
1261 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1263 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
1265 if (need_entry_edge
&& !have_entry_edge
)
1268 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1270 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
, EDGE_FAKE
);
1271 /* Avoid bbs that have both fake entry edge and also some
1272 exit edge. One of those edges wouldn't be added to the
1273 spanning tree, but we can't instrument any of them. */
1274 if (have_exit_edge
|| need_exit_edge
)
1276 gimple_stmt_iterator gsi
;
1279 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
1280 gcc_checking_assert (!gsi_end_p (gsi
));
1281 first
= gsi_stmt (gsi
);
1282 /* Don't split the bbs containing __builtin_setjmp_receiver
1283 or ABNORMAL_DISPATCHER calls. These are very
1284 special and don't expect anything to be inserted before
1286 if (is_gimple_call (first
)
1287 && (gimple_call_builtin_p (first
, BUILT_IN_SETJMP_RECEIVER
)
1288 || (gimple_call_flags (first
) & ECF_RETURNS_TWICE
)
1289 || (gimple_call_internal_p (first
)
1290 && (gimple_call_internal_fn (first
)
1291 == IFN_ABNORMAL_DISPATCHER
))))
1295 fprintf (dump_file
, "Splitting bb %i after labels\n",
1297 split_block_after_labels (bb
);
1303 el
= create_edge_list ();
1304 num_edges
= NUM_EDGES (el
);
1305 qsort (el
->index_to_edge
, num_edges
, sizeof (edge
), compare_freqs
);
1306 alloc_aux_for_edges (sizeof (struct edge_profile_info
));
1308 /* The basic blocks are expected to be numbered sequentially. */
1312 for (i
= 0 ; i
< num_edges
; i
++)
1314 edge e
= INDEX_EDGE (el
, i
);
1316 /* Mark edges we've replaced by fake edges above as ignored. */
1317 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1318 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1319 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1321 EDGE_INFO (e
)->ignore
= 1;
1326 /* Create spanning tree from basic block graph, mark each edge that is
1327 on the spanning tree. We insert as many abnormal and critical edges
1328 as possible to minimize number of edge splits necessary. */
1331 find_spanning_tree (el
);
1336 /* Keep only edge from entry block to be instrumented. */
1337 FOR_EACH_BB_FN (bb
, cfun
)
1338 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1339 EDGE_INFO (e
)->ignore
= true;
1343 /* Fake edges that are not on the tree will not be instrumented, so
1344 mark them ignored. */
1345 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1347 edge e
= INDEX_EDGE (el
, i
);
1348 struct edge_profile_info
*inf
= EDGE_INFO (e
);
1350 if (inf
->ignore
|| inf
->on_tree
)
1352 else if (e
->flags
& EDGE_FAKE
)
1361 total_num_blocks
+= n_basic_blocks_for_fn (cfun
);
1363 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks_for_fn (cfun
));
1365 total_num_edges
+= num_edges
;
1367 fprintf (dump_file
, "%d edges\n", num_edges
);
1369 total_num_edges_ignored
+= ignored_edges
;
1371 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1373 total_num_edges_instrumented
+= num_instrumented
;
1375 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1377 /* Dump function body before it's instrumented.
1378 It helps to debug gcov tool. */
1379 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1380 dump_function_to_file (cfun
->decl
, dump_file
, dump_flags
);
1382 /* Compute two different checksums. Note that we want to compute
1383 the checksum in only once place, since it depends on the shape
1384 of the control flow which can change during
1385 various transformations. */
1388 /* At stream in time we do not have CFG, so we cannot do checksums. */
1390 lineno_checksum
= 0;
1394 cfg_checksum
= coverage_compute_cfg_checksum (cfun
);
1395 lineno_checksum
= coverage_compute_lineno_checksum ();
1398 /* Write the data from which gcov can reconstruct the basic block
1399 graph and function line numbers (the gcno file). */
1400 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1402 gcov_position_t offset
;
1404 /* Basic block flags */
1405 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1406 gcov_write_unsigned (n_basic_blocks_for_fn (cfun
));
1407 gcov_write_length (offset
);
1410 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1411 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1416 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1417 gcov_write_unsigned (bb
->index
);
1419 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1421 struct edge_profile_info
*i
= EDGE_INFO (e
);
1424 unsigned flag_bits
= 0;
1427 flag_bits
|= GCOV_ARC_ON_TREE
;
1428 if (e
->flags
& EDGE_FAKE
)
1429 flag_bits
|= GCOV_ARC_FAKE
;
1430 if (e
->flags
& EDGE_FALLTHRU
)
1431 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1432 /* On trees we don't have fallthru flags, but we can
1433 recompute them from CFG shape. */
1434 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1435 && e
->src
->next_bb
== e
->dest
)
1436 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1438 gcov_write_unsigned (e
->dest
->index
);
1439 gcov_write_unsigned (flag_bits
);
1443 gcov_write_length (offset
);
1447 /* Initialize the output. */
1448 output_location (&streamed_locations
, NULL
, 0, NULL
, NULL
);
1450 hash_set
<location_hash
> seen_locations
;
1452 FOR_EACH_BB_FN (bb
, cfun
)
1454 gimple_stmt_iterator gsi
;
1455 gcov_position_t offset
= 0;
1457 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
1459 location_t loc
= DECL_SOURCE_LOCATION (current_function_decl
);
1460 gcc_checking_assert (!RESERVED_LOCATION_P (loc
));
1461 seen_locations
.add (loc
);
1462 expanded_location curr_location
= expand_location (loc
);
1463 output_location (&streamed_locations
, curr_location
.file
,
1464 MAX (1, curr_location
.line
), &offset
, bb
);
1467 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1469 gimple
*stmt
= gsi_stmt (gsi
);
1470 location_t loc
= gimple_location (stmt
);
1471 if (!RESERVED_LOCATION_P (loc
))
1473 seen_locations
.add (loc
);
1474 output_location (&streamed_locations
, gimple_filename (stmt
),
1475 MAX (1, gimple_lineno (stmt
)), &offset
, bb
);
1479 /* Notice GOTO expressions eliminated while constructing the CFG.
1480 It's hard to distinguish such expression, but goto_locus should
1481 not be any of already seen location. */
1483 if (single_succ_p (bb
)
1484 && (loc
= single_succ_edge (bb
)->goto_locus
)
1485 && !RESERVED_LOCATION_P (loc
)
1486 && !seen_locations
.contains (loc
))
1488 expanded_location curr_location
= expand_location (loc
);
1489 output_location (&streamed_locations
, curr_location
.file
,
1490 MAX (1, curr_location
.line
), &offset
, bb
);
1495 /* A file of NULL indicates the end of run. */
1496 gcov_write_unsigned (0);
1497 gcov_write_string (NULL
);
1498 gcov_write_length (offset
);
1503 if (flag_profile_values
)
1504 gimple_find_values_to_profile (&values
);
1506 if (flag_branch_probabilities
)
1508 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1509 if (flag_profile_values
)
1510 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1513 remove_fake_edges ();
1515 /* For each edge not on the spanning tree, add counting code. */
1516 if (profile_arc_flag
1517 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1519 unsigned n_instrumented
;
1521 gimple_init_gcov_profiler ();
1523 n_instrumented
= instrument_edges (el
);
1525 gcc_assert (n_instrumented
== num_instrumented
);
1527 if (flag_profile_values
)
1528 instrument_values (values
);
1530 /* Commit changes done by instrumentation. */
1531 gsi_commit_edge_inserts ();
1534 free_aux_for_edges ();
1537 free_edge_list (el
);
1538 coverage_end_function (lineno_checksum
, cfg_checksum
);
1539 if (flag_branch_probabilities
1540 && (profile_status_for_fn (cfun
) == PROFILE_READ
))
1542 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1543 report_predictor_hitrates ();
1545 /* At this moment we have precise loop iteration count estimates.
1546 Record them to loop structure before the profile gets out of date. */
1547 for (auto loop
: loops_list (cfun
, 0))
1548 if (loop
->header
->count
> 0 && loop
->header
->count
.reliable_p ())
1550 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
1551 widest_int bound
= gcov_type_to_wide_int (nit
);
1552 loop
->any_estimate
= false;
1553 record_niter_bound (loop
, bound
, true, false);
1555 compute_function_frequency ();
1559 /* Union find algorithm implementation for the basic blocks using
1563 find_group (basic_block bb
)
1565 basic_block group
= bb
, bb1
;
1567 while ((basic_block
) group
->aux
!= group
)
1568 group
= (basic_block
) group
->aux
;
1570 /* Compress path. */
1571 while ((basic_block
) bb
->aux
!= group
)
1573 bb1
= (basic_block
) bb
->aux
;
1574 bb
->aux
= (void *) group
;
1581 union_groups (basic_block bb1
, basic_block bb2
)
1583 basic_block bb1g
= find_group (bb1
);
1584 basic_block bb2g
= find_group (bb2
);
1586 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1587 this code is unlikely going to be performance problem anyway. */
1588 gcc_assert (bb1g
!= bb2g
);
1593 /* This function searches all of the edges in the program flow graph, and puts
1594 as many bad edges as possible onto the spanning tree. Bad edges include
1595 abnormals edges, which can't be instrumented at the moment. Since it is
1596 possible for fake edges to form a cycle, we will have to develop some
1597 better way in the future. Also put critical edges to the tree, since they
1598 are more expensive to instrument. */
1601 find_spanning_tree (struct edge_list
*el
)
1604 int num_edges
= NUM_EDGES (el
);
1607 /* We use aux field for standard union-find algorithm. */
1608 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
1611 /* Add fake edge exit to entry we can't instrument. */
1612 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun
), ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1614 /* First add all abnormal edges to the tree unless they form a cycle. Also
1615 add all edges to the exit block to avoid inserting profiling code behind
1616 setting return value from function. */
1617 for (i
= 0; i
< num_edges
; i
++)
1619 edge e
= INDEX_EDGE (el
, i
);
1620 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1621 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1622 && !EDGE_INFO (e
)->ignore
1623 && (find_group (e
->src
) != find_group (e
->dest
)))
1626 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1627 e
->src
->index
, e
->dest
->index
);
1628 EDGE_INFO (e
)->on_tree
= 1;
1629 union_groups (e
->src
, e
->dest
);
1633 /* And now the rest. Edge list is sorted according to frequencies and
1634 thus we will produce minimal spanning tree. */
1635 for (i
= 0; i
< num_edges
; i
++)
1637 edge e
= INDEX_EDGE (el
, i
);
1638 if (!EDGE_INFO (e
)->ignore
1639 && find_group (e
->src
) != find_group (e
->dest
))
1642 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1643 e
->src
->index
, e
->dest
->index
);
1644 EDGE_INFO (e
)->on_tree
= 1;
1645 union_groups (e
->src
, e
->dest
);
1649 clear_aux_for_blocks ();
1652 /* Perform file-level initialization for branch-prob processing. */
1655 init_branch_prob (void)
1659 total_num_blocks
= 0;
1660 total_num_edges
= 0;
1661 total_num_edges_ignored
= 0;
1662 total_num_edges_instrumented
= 0;
1663 total_num_blocks_created
= 0;
1664 total_num_passes
= 0;
1665 total_num_times_called
= 0;
1666 total_num_branches
= 0;
1667 for (i
= 0; i
< 20; i
++)
1668 total_hist_br_prob
[i
] = 0;
1671 /* Performs file-level cleanup after branch-prob processing
1675 end_branch_prob (void)
1679 fprintf (dump_file
, "\n");
1680 fprintf (dump_file
, "Total number of blocks: %d\n",
1682 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1683 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1684 total_num_edges_ignored
);
1685 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1686 total_num_edges_instrumented
);
1687 fprintf (dump_file
, "Total number of blocks created: %d\n",
1688 total_num_blocks_created
);
1689 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1691 if (total_num_times_called
!= 0)
1692 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1693 (total_num_passes
+ (total_num_times_called
>> 1))
1694 / total_num_times_called
);
1695 fprintf (dump_file
, "Total number of branches: %d\n",
1696 total_num_branches
);
1697 if (total_num_branches
)
1701 for (i
= 0; i
< 10; i
++)
1702 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1703 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1704 / total_num_branches
, 5*i
, 5*i
+5);