1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2021 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"
71 /* Map from BBs/edges to gcov counters. */
72 vec
<gcov_type
> bb_gcov_counts
;
73 hash_map
<edge
,gcov_type
> *edge_gcov_counts
;
75 struct bb_profile_info
{
76 unsigned int count_valid
: 1;
78 /* Number of successor and predecessor edges. */
83 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
86 /* Counter summary from the last set of coverage counts read. */
88 gcov_summary
*profile_info
;
90 /* Collect statistics on the performance of this pass for the entire source
93 static int total_num_blocks
;
94 static int total_num_edges
;
95 static int total_num_edges_ignored
;
96 static int total_num_edges_instrumented
;
97 static int total_num_blocks_created
;
98 static int total_num_passes
;
99 static int total_num_times_called
;
100 static int total_hist_br_prob
[20];
101 static int total_num_branches
;
103 /* Forward declarations. */
104 static void find_spanning_tree (struct edge_list
*);
106 /* Add edge instrumentation code to the entire insn chain.
108 F is the first insn of the chain.
109 NUM_BLOCKS is the number of basic blocks found in F. */
112 instrument_edges (struct edge_list
*el
)
114 unsigned num_instr_edges
= 0;
115 int num_edges
= NUM_EDGES (el
);
118 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
123 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
125 struct edge_profile_info
*inf
= EDGE_INFO (e
);
127 if (!inf
->ignore
&& !inf
->on_tree
)
129 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
131 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
132 e
->src
->index
, e
->dest
->index
,
133 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
134 gimple_gen_edge_profiler (num_instr_edges
++, e
);
139 total_num_blocks_created
+= num_edges
;
141 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
142 return num_instr_edges
;
145 /* Add code to measure histograms for values in list VALUES. */
147 instrument_values (histogram_values values
)
151 /* Emit code to generate the histograms before the insns. */
153 for (i
= 0; i
< values
.length (); i
++)
155 histogram_value hist
= values
[i
];
156 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
158 if (!coverage_counter_alloc (t
, hist
->n_counters
))
163 case HIST_TYPE_INTERVAL
:
164 gimple_gen_interval_profiler (hist
, t
);
168 gimple_gen_pow2_profiler (hist
, t
);
171 case HIST_TYPE_TOPN_VALUES
:
172 gimple_gen_topn_values_profiler (hist
, t
);
175 case HIST_TYPE_INDIR_CALL
:
176 gimple_gen_ic_profiler (hist
, t
);
179 case HIST_TYPE_AVERAGE
:
180 gimple_gen_average_profiler (hist
, t
);
184 gimple_gen_ior_profiler (hist
, t
);
187 case HIST_TYPE_TIME_PROFILE
:
188 gimple_gen_time_profiler (t
);
198 /* Computes hybrid profile for all matching entries in da_file.
200 CFG_CHECKSUM is the precomputed checksum for the CFG. */
203 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
205 unsigned num_edges
= 0;
209 /* Count the edges to be (possibly) instrumented. */
210 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
215 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
216 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
220 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, cfg_checksum
,
221 lineno_checksum
, num_edges
);
229 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
233 FOR_EACH_EDGE (e
, ei
, edges
)
235 if (!EDGE_INFO (e
)->ignore
)
237 if (edge_gcov_count (e
) < 0
238 && (!(e
->flags
& EDGE_FAKE
)
239 || !block_ends_with_call_p (e
->src
)))
244 "Edge %i->%i is inconsistent, count%" PRId64
,
245 e
->src
->index
, e
->dest
->index
, edge_gcov_count (e
));
246 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
247 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
257 correct_negative_edge_counts (void)
263 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
265 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
267 if (edge_gcov_count (e
) < 0)
268 edge_gcov_count (e
) = 0;
273 /* Check consistency.
274 Return true if inconsistency is found. */
276 is_inconsistent (void)
279 bool inconsistent
= false;
280 FOR_EACH_BB_FN (bb
, cfun
)
282 inconsistent
|= is_edge_inconsistent (bb
->preds
);
283 if (!dump_file
&& inconsistent
)
285 inconsistent
|= is_edge_inconsistent (bb
->succs
);
286 if (!dump_file
&& inconsistent
)
288 if (bb_gcov_count (bb
) < 0)
292 fprintf (dump_file
, "BB %i count is negative "
296 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
300 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->preds
))
304 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
305 "%" PRId64
" should be %" PRId64
,
308 sum_edge_counts (bb
->preds
));
309 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
313 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->succs
) &&
314 ! (find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
)) != NULL
315 && block_ends_with_call_p (bb
)))
319 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
320 "%" PRId64
" should be %" PRId64
,
323 sum_edge_counts (bb
->succs
));
324 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
328 if (!dump_file
&& inconsistent
)
335 /* Set each basic block count to the sum of its outgoing edge counts */
340 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
342 bb_gcov_count (bb
) = sum_edge_counts (bb
->succs
);
343 gcc_assert (bb_gcov_count (bb
) >= 0);
347 /* Reads profile data and returns total number of edge counts read */
349 read_profile_edge_counts (gcov_type
*exec_counts
)
353 int exec_counts_pos
= 0;
354 /* For each edge not on the spanning tree, set its execution count from
356 /* The first count in the .da file is the number of times that the function
357 was entered. This is the exec_count for block zero. */
359 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
364 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
365 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
369 edge_gcov_count (e
) = exec_counts
[exec_counts_pos
++];
371 edge_gcov_count (e
) = 0;
373 EDGE_INFO (e
)->count_valid
= 1;
374 BB_INFO (bb
)->succ_count
--;
375 BB_INFO (e
->dest
)->pred_count
--;
378 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
379 bb
->index
, e
->dest
->index
);
380 fprintf (dump_file
, "%" PRId64
,
381 (int64_t) edge_gcov_count (e
));
389 /* BB statistics comparing guessed frequency of BB with feedback. */
394 double guessed
, feedback
;
398 /* Compare limit_tuple intervals by first item in descending order. */
401 cmp_stats (const void *ptr1
, const void *ptr2
)
403 const bb_stats
*p1
= (const bb_stats
*)ptr1
;
404 const bb_stats
*p2
= (const bb_stats
*)ptr2
;
406 if (p1
->feedback
< p2
->feedback
)
408 else if (p1
->feedback
> p2
->feedback
)
414 /* Compute the branch probabilities for the various branches.
415 Annotate them accordingly.
417 CFG_CHECKSUM is the precomputed checksum for the CFG. */
420 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
427 int hist_br_prob
[20];
429 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
430 int inconsistent
= 0;
432 /* Very simple sanity checks so we catch bugs in our profiling code. */
436 fprintf (dump_file
, "Profile info is missing; giving up\n");
440 bb_gcov_counts
.safe_grow_cleared (last_basic_block_for_fn (cfun
), true);
441 edge_gcov_counts
= new hash_map
<edge
,gcov_type
>;
443 /* Attach extra info block to each bb. */
444 alloc_aux_for_blocks (sizeof (struct bb_profile_info
));
445 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
450 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
451 if (!EDGE_INFO (e
)->ignore
)
452 BB_INFO (bb
)->succ_count
++;
453 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
454 if (!EDGE_INFO (e
)->ignore
)
455 BB_INFO (bb
)->pred_count
++;
458 /* Avoid predicting entry on exit nodes. */
459 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun
))->succ_count
= 2;
460 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->pred_count
= 2;
462 num_edges
= read_profile_edge_counts (exec_counts
);
465 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
467 /* For every block in the file,
468 - if every exit/entrance edge has a known count, then set the block count
469 - if the block count is known, and every exit/entrance edge but one has
470 a known execution count, then set the count of the remaining edge
472 As edge counts are set, decrement the succ/pred count, but don't delete
473 the edge, that way we can easily tell when all edges are known, or only
474 one edge is unknown. */
476 /* The order that the basic blocks are iterated through is important.
477 Since the code that finds spanning trees starts with block 0, low numbered
478 edges are put on the spanning tree in preference to high numbered edges.
479 Hence, most instrumented edges are at the end. Graph solving works much
480 faster if we propagate numbers from the end to the start.
482 This takes an average of slightly more than 3 passes. */
490 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, prev_bb
)
492 struct bb_profile_info
*bi
= BB_INFO (bb
);
493 if (! bi
->count_valid
)
495 if (bi
->succ_count
== 0)
501 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
502 total
+= edge_gcov_count (e
);
503 bb_gcov_count (bb
) = total
;
507 else if (bi
->pred_count
== 0)
513 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
514 total
+= edge_gcov_count (e
);
515 bb_gcov_count (bb
) = total
;
522 if (bi
->succ_count
== 1)
528 /* One of the counts will be invalid, but it is zero,
529 so adding it in also doesn't hurt. */
530 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
531 total
+= edge_gcov_count (e
);
533 /* Search for the invalid edge, and set its count. */
534 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
535 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
538 /* Calculate count for remaining edge by conservation. */
539 total
= bb_gcov_count (bb
) - total
;
542 EDGE_INFO (e
)->count_valid
= 1;
543 edge_gcov_count (e
) = total
;
546 BB_INFO (e
->dest
)->pred_count
--;
549 if (bi
->pred_count
== 1)
555 /* One of the counts will be invalid, but it is zero,
556 so adding it in also doesn't hurt. */
557 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
558 total
+= edge_gcov_count (e
);
560 /* Search for the invalid edge, and set its count. */
561 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
562 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
565 /* Calculate count for remaining edge by conservation. */
566 total
= bb_gcov_count (bb
) - total
+ edge_gcov_count (e
);
569 EDGE_INFO (e
)->count_valid
= 1;
570 edge_gcov_count (e
) = total
;
573 BB_INFO (e
->src
)->succ_count
--;
580 total_num_passes
+= passes
;
582 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
584 /* If the graph has been correctly solved, every block will have a
585 succ and pred count of zero. */
586 FOR_EACH_BB_FN (bb
, cfun
)
588 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
591 /* Check for inconsistent basic block counts */
592 inconsistent
= is_inconsistent ();
596 if (flag_profile_correction
)
598 /* Inconsistency detected. Make it flow-consistent. */
599 static int informed
= 0;
600 if (dump_enabled_p () && informed
== 0)
603 dump_printf_loc (MSG_NOTE
,
604 dump_user_location_t::from_location_t (input_location
),
605 "correcting inconsistent profile data\n");
607 correct_negative_edge_counts ();
608 /* Set bb counts to the sum of the outgoing edge counts */
611 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
615 error ("corrupted profile info: profile data is not flow-consistent");
618 /* For every edge, calculate its branch probability and add a reg_note
619 to the branch insn to indicate this. */
621 for (i
= 0; i
< 20; i
++)
625 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
630 if (bb_gcov_count (bb
) < 0)
632 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
633 bb
->index
, (int)bb_gcov_count (bb
));
634 bb_gcov_count (bb
) = 0;
636 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
638 /* Function may return twice in the cased the called function is
639 setjmp or calls fork, but we can't represent this by extra
640 edge from the entry, since extra edge from the exit is
641 already present. We get negative frequency from the entry
643 if ((edge_gcov_count (e
) < 0
644 && e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
645 || (edge_gcov_count (e
) > bb_gcov_count (bb
)
646 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
648 if (block_ends_with_call_p (bb
))
649 edge_gcov_count (e
) = edge_gcov_count (e
) < 0
650 ? 0 : bb_gcov_count (bb
);
652 if (edge_gcov_count (e
) < 0
653 || edge_gcov_count (e
) > bb_gcov_count (bb
))
655 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
656 e
->src
->index
, e
->dest
->index
,
657 (int)edge_gcov_count (e
));
658 edge_gcov_count (e
) = bb_gcov_count (bb
) / 2;
661 if (bb_gcov_count (bb
))
663 bool set_to_guessed
= false;
664 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
666 bool prev_never
= e
->probability
== profile_probability::never ();
667 e
->probability
= profile_probability::probability_in_gcov_type
668 (edge_gcov_count (e
), bb_gcov_count (bb
));
669 if (e
->probability
== profile_probability::never ()
671 && flag_profile_partial_training
)
672 set_to_guessed
= true;
675 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
676 e
->probability
= e
->probability
.guessed ();
677 if (bb
->index
>= NUM_FIXED_BLOCKS
678 && block_ends_with_condjump_p (bb
)
679 && EDGE_COUNT (bb
->succs
) >= 2)
685 /* Find the branch edge. It is possible that we do have fake
687 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
688 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
691 prob
= e
->probability
.to_reg_br_prob_base ();
692 index
= prob
* 20 / REG_BR_PROB_BASE
;
696 hist_br_prob
[index
]++;
701 /* As a last resort, distribute the probabilities evenly.
702 Use simple heuristics that if there are normal edges,
703 give all abnormals frequency of 0, otherwise distribute the
704 frequency over abnormals (this is the case of noreturn
706 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
710 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
711 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
715 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
716 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
718 = profile_probability::guessed_always ().apply_scale (1, total
);
720 e
->probability
= profile_probability::never ();
724 total
+= EDGE_COUNT (bb
->succs
);
725 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
727 = profile_probability::guessed_always ().apply_scale (1, total
);
729 if (bb
->index
>= NUM_FIXED_BLOCKS
730 && block_ends_with_condjump_p (bb
)
731 && EDGE_COUNT (bb
->succs
) >= 2)
737 && (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
738 || !flag_profile_partial_training
))
739 profile_status_for_fn (cfun
) = PROFILE_READ
;
741 /* If we have real data, use them! */
742 if (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
743 || !flag_guess_branch_prob
)
745 profile_count old_entry_cnt
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
746 auto_vec
<bb_stats
> stats
;
747 double sum1
= 0, sum2
= 0;
749 FOR_ALL_BB_FN (bb
, cfun
)
751 profile_count cnt
= bb
->count
;
752 if (bb_gcov_count (bb
) || !flag_profile_partial_training
)
753 bb
->count
= profile_count::from_gcov_type (bb_gcov_count (bb
));
755 bb
->count
= profile_count::guessed_zero ();
756 if (dump_file
&& bb
->index
>= 0)
758 double freq1
= cnt
.to_sreal_scale (old_entry_cnt
).to_double ();
759 double freq2
= bb
->count
.to_sreal_scale
760 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).
762 bb_stats stat
= {bb
, freq1
, freq2
,
763 (int64_t) bb_gcov_count (bb
)};
764 stats
.safe_push (stat
);
771 double nsum1
= 0, nsum2
= 0;
772 stats
.qsort (cmp_stats
);
773 for (auto stat
: stats
)
775 nsum1
+= stat
.guessed
;
776 nsum2
+= stat
.feedback
;
778 " Basic block %4i guessed freq: %12.3f"
779 " cummulative:%6.2f%% "
780 " feedback freq: %12.3f cummulative:%7.2f%%"
781 " cnt: 10%" PRId64
"\n", stat
.bb
->index
,
790 /* If function was not trained, preserve local estimates including statically
791 determined zero counts. */
792 else if (profile_status_for_fn (cfun
) == PROFILE_READ
793 && !flag_profile_partial_training
)
794 FOR_ALL_BB_FN (bb
, cfun
)
795 if (!(bb
->count
== profile_count::zero ()))
796 bb
->count
= bb
->count
.global0 ();
798 bb_gcov_counts
.release ();
799 delete edge_gcov_counts
;
800 edge_gcov_counts
= NULL
;
802 update_max_bb_count ();
806 fprintf (dump_file
, " Profile feedback for function");
807 fprintf (dump_file
, ((profile_status_for_fn (cfun
) == PROFILE_READ
)
809 : " is not available \n"));
811 fprintf (dump_file
, "%d branches\n", num_branches
);
813 for (i
= 0; i
< 10; i
++)
814 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
815 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
818 total_num_branches
+= num_branches
;
819 for (i
= 0; i
< 20; i
++)
820 total_hist_br_prob
[i
] += hist_br_prob
[i
];
822 fputc ('\n', dump_file
);
823 fputc ('\n', dump_file
);
825 gimple_dump_cfg (dump_file
, TDF_BLOCKS
);
828 free_aux_for_blocks ();
831 /* Sort the histogram value and count for TOPN and INDIR_CALL type. */
834 sort_hist_values (histogram_value hist
)
836 gcc_assert (hist
->type
== HIST_TYPE_TOPN_VALUES
837 || hist
->type
== HIST_TYPE_INDIR_CALL
);
839 int counters
= hist
->hvalue
.counters
[1];
840 for (int i
= 0; i
< counters
- 1; i
++)
841 /* Hist value is organized as:
842 [total_executions, N, value1, counter1, ..., valueN, counterN]
843 Use decrease bubble sort to rearrange it. The sort starts from <value1,
844 counter1> and compares counter first. If counter is same, compares the
845 value, exchange it if small to keep stable. */
848 bool swapped
= false;
849 for (int j
= 0; j
< counters
- 1 - i
; j
++)
851 gcov_type
*p
= &hist
->hvalue
.counters
[2 * j
+ 2];
852 if (p
[1] < p
[3] || (p
[1] == p
[3] && p
[0] < p
[2]))
854 std::swap (p
[0], p
[2]);
855 std::swap (p
[1], p
[3]);
863 /* Load value histograms values whose description is stored in VALUES array
866 CFG_CHECKSUM is the precomputed checksum for the CFG. */
869 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
870 unsigned lineno_checksum
)
872 unsigned i
, j
, t
, any
;
873 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
874 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
875 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
876 gcov_type
*aact_count
;
877 struct cgraph_node
*node
;
879 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
880 n_histogram_counters
[t
] = 0;
882 for (i
= 0; i
< values
.length (); i
++)
884 histogram_value hist
= values
[i
];
885 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
889 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
891 if (!n_histogram_counters
[t
])
893 histogram_counts
[t
] = NULL
;
897 histogram_counts
[t
] = get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
900 n_histogram_counters
[t
]);
901 if (histogram_counts
[t
])
903 act_count
[t
] = histogram_counts
[t
];
908 for (i
= 0; i
< values
.length (); i
++)
910 histogram_value hist
= values
[i
];
911 gimple
*stmt
= hist
->hvalue
.stmt
;
913 t
= (int) hist
->type
;
914 bool topn_p
= (hist
->type
== HIST_TYPE_TOPN_VALUES
915 || hist
->type
== HIST_TYPE_INDIR_CALL
);
917 /* TOP N counter uses variable number of counters. */
922 total_size
= 2 + 2 * act_count
[t
][1];
925 gimple_add_histogram_value (cfun
, stmt
, hist
);
926 hist
->n_counters
= total_size
;
927 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
928 for (j
= 0; j
< hist
->n_counters
; j
++)
930 hist
->hvalue
.counters
[j
] = act_count
[t
][j
];
932 hist
->hvalue
.counters
[j
] = 0;
933 act_count
[t
] += hist
->n_counters
;
934 sort_hist_values (hist
);
938 aact_count
= act_count
[t
];
941 act_count
[t
] += hist
->n_counters
;
943 gimple_add_histogram_value (cfun
, stmt
, hist
);
944 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
945 for (j
= 0; j
< hist
->n_counters
; j
++)
947 hist
->hvalue
.counters
[j
] = aact_count
[j
];
949 hist
->hvalue
.counters
[j
] = 0;
952 /* Time profiler counter is not related to any statement,
953 so that we have to read the counter and set the value to
954 the corresponding call graph node. */
955 if (hist
->type
== HIST_TYPE_TIME_PROFILE
)
957 node
= cgraph_node::get (hist
->fun
->decl
);
958 if (hist
->hvalue
.counters
[0] >= 0
959 && hist
->hvalue
.counters
[0] < INT_MAX
/ 2)
960 node
->tp_first_run
= hist
->hvalue
.counters
[0];
963 if (flag_profile_correction
)
964 error ("corrupted profile info: invalid time profile");
965 node
->tp_first_run
= 0;
968 /* Drop profile for -fprofile-reproducible=multithreaded. */
970 = (flag_profile_reproducible
== PROFILE_REPRODUCIBILITY_MULTITHREADED
);
972 node
->tp_first_run
= 0;
975 fprintf (dump_file
, "Read tp_first_run: %d%s\n", node
->tp_first_run
,
976 drop
? "; ignored because profile reproducibility is "
977 "multi-threaded" : "");
981 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
982 free (histogram_counts
[t
]);
985 /* Location triplet which records a location. */
986 struct location_triplet
988 const char *filename
;
993 /* Traits class for streamed_locations hash set below. */
995 struct location_triplet_hash
: typed_noop_remove
<location_triplet
>
997 typedef location_triplet value_type
;
998 typedef location_triplet compare_type
;
1001 hash (const location_triplet
&ref
)
1003 inchash::hash
hstate (0);
1005 hstate
.add_int (strlen (ref
.filename
));
1006 hstate
.add_int (ref
.lineno
);
1007 hstate
.add_int (ref
.bb_index
);
1008 return hstate
.end ();
1012 equal (const location_triplet
&ref1
, const location_triplet
&ref2
)
1014 return ref1
.lineno
== ref2
.lineno
1015 && ref1
.bb_index
== ref2
.bb_index
1016 && ref1
.filename
!= NULL
1017 && ref2
.filename
!= NULL
1018 && strcmp (ref1
.filename
, ref2
.filename
) == 0;
1022 mark_deleted (location_triplet
&ref
)
1027 static const bool empty_zero_p
= false;
1030 mark_empty (location_triplet
&ref
)
1036 is_deleted (const location_triplet
&ref
)
1038 return ref
.lineno
== -1;
1042 is_empty (const location_triplet
&ref
)
1044 return ref
.lineno
== -2;
1051 /* When passed NULL as file_name, initialize.
1052 When passed something else, output the necessary commands to change
1053 line to LINE and offset to FILE_NAME. */
1055 output_location (hash_set
<location_triplet_hash
> *streamed_locations
,
1056 char const *file_name
, int line
,
1057 gcov_position_t
*offset
, basic_block bb
)
1059 static char const *prev_file_name
;
1060 static int prev_line
;
1061 bool name_differs
, line_differs
;
1063 location_triplet triplet
;
1064 triplet
.filename
= file_name
;
1065 triplet
.lineno
= line
;
1066 triplet
.bb_index
= bb
? bb
->index
: 0;
1068 if (streamed_locations
->add (triplet
))
1073 prev_file_name
= NULL
;
1078 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
1079 line_differs
= prev_line
!= line
;
1083 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
1084 gcov_write_unsigned (bb
->index
);
1085 name_differs
= line_differs
= true;
1088 /* If this is a new source file, then output the
1089 file's name to the .bb file. */
1092 prev_file_name
= file_name
;
1093 gcov_write_unsigned (0);
1094 gcov_write_filename (prev_file_name
);
1098 gcov_write_unsigned (line
);
1103 /* Helper for qsort so edges get sorted from highest frequency to smallest.
1104 This controls the weight for minimal spanning tree algorithm */
1106 compare_freqs (const void *p1
, const void *p2
)
1108 const_edge e1
= *(const const_edge
*)p1
;
1109 const_edge e2
= *(const const_edge
*)p2
;
1111 /* Critical edges needs to be split which introduce extra control flow.
1112 Make them more heavy. */
1113 int m1
= EDGE_CRITICAL_P (e1
) ? 2 : 1;
1114 int m2
= EDGE_CRITICAL_P (e2
) ? 2 : 1;
1116 if (EDGE_FREQUENCY (e1
) * m1
+ m1
!= EDGE_FREQUENCY (e2
) * m2
+ m2
)
1117 return EDGE_FREQUENCY (e2
) * m2
+ m2
- EDGE_FREQUENCY (e1
) * m1
- m1
;
1118 /* Stabilize sort. */
1119 if (e1
->src
->index
!= e2
->src
->index
)
1120 return e2
->src
->index
- e1
->src
->index
;
1121 return e2
->dest
->index
- e1
->dest
->index
;
1124 /* Only read execution count for thunks. */
1127 read_thunk_profile (struct cgraph_node
*node
)
1129 tree old
= current_function_decl
;
1130 current_function_decl
= node
->decl
;
1131 gcov_type
*counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, 0, 0, 1);
1134 node
->callees
->count
= node
->count
1135 = profile_count::from_gcov_type (counts
[0]);
1138 current_function_decl
= old
;
1143 /* Instrument and/or analyze program behavior based on program the CFG.
1145 This function creates a representation of the control flow graph (of
1146 the function being compiled) that is suitable for the instrumentation
1147 of edges and/or converting measured edge counts to counts on the
1150 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
1151 the flow graph that are needed to reconstruct the dynamic behavior of the
1152 flow graph. This data is written to the gcno file for gcov.
1154 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1155 information from the gcda file containing edge count information from
1156 previous executions of the function being compiled. In this case, the
1157 control flow graph is annotated with actual execution counts by
1158 compute_branch_probabilities().
1160 Main entry point of this file. */
1163 branch_prob (bool thunk
)
1167 unsigned num_edges
, ignored_edges
;
1168 unsigned num_instrumented
;
1169 struct edge_list
*el
;
1170 histogram_values values
= histogram_values ();
1171 unsigned cfg_checksum
, lineno_checksum
;
1173 total_num_times_called
++;
1175 flow_call_edges_add (NULL
);
1176 add_noreturn_fake_exit_edges ();
1178 hash_set
<location_triplet_hash
> streamed_locations
;
1182 /* We can't handle cyclic regions constructed using abnormal edges.
1183 To avoid these we replace every source of abnormal edge by a fake
1184 edge from entry node and every destination by fake edge to exit.
1185 This keeps graph acyclic and our calculation exact for all normal
1186 edges except for exit and entrance ones.
1188 We also add fake exit edges for each call and asm statement in the
1189 basic, since it may not return. */
1191 FOR_EACH_BB_FN (bb
, cfun
)
1193 int need_exit_edge
= 0, need_entry_edge
= 0;
1194 int have_exit_edge
= 0, have_entry_edge
= 0;
1198 /* Functions returning multiple times are not handled by extra edges.
1199 Instead we simply allow negative counts on edges from exit to the
1200 block past call and corresponding probabilities. We can't go
1201 with the extra edges because that would result in flowgraph that
1202 needs to have fake edges outside the spanning tree. */
1204 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1206 gimple_stmt_iterator gsi
;
1207 gimple
*last
= NULL
;
1209 /* It may happen that there are compiler generated statements
1210 without a locus at all. Go through the basic block from the
1211 last to the first statement looking for a locus. */
1212 for (gsi
= gsi_last_nondebug_bb (bb
);
1214 gsi_prev_nondebug (&gsi
))
1216 last
= gsi_stmt (gsi
);
1217 if (!RESERVED_LOCATION_P (gimple_location (last
)))
1221 /* Edge with goto locus might get wrong coverage info unless
1222 it is the only edge out of BB.
1223 Don't do that when the locuses match, so
1224 if (blah) goto something;
1225 is not computed twice. */
1227 && gimple_has_location (last
)
1228 && !RESERVED_LOCATION_P (e
->goto_locus
)
1229 && !single_succ_p (bb
)
1230 && (LOCATION_FILE (e
->goto_locus
)
1231 != LOCATION_FILE (gimple_location (last
))
1232 || (LOCATION_LINE (e
->goto_locus
)
1233 != LOCATION_LINE (gimple_location (last
)))))
1235 basic_block new_bb
= split_edge (e
);
1236 edge ne
= single_succ_edge (new_bb
);
1237 ne
->goto_locus
= e
->goto_locus
;
1239 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1240 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1242 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1245 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1247 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1248 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1249 need_entry_edge
= 1;
1250 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1251 have_entry_edge
= 1;
1254 if (need_exit_edge
&& !have_exit_edge
)
1257 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1259 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
1261 if (need_entry_edge
&& !have_entry_edge
)
1264 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1266 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
, EDGE_FAKE
);
1267 /* Avoid bbs that have both fake entry edge and also some
1268 exit edge. One of those edges wouldn't be added to the
1269 spanning tree, but we can't instrument any of them. */
1270 if (have_exit_edge
|| need_exit_edge
)
1272 gimple_stmt_iterator gsi
;
1275 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
1276 gcc_checking_assert (!gsi_end_p (gsi
));
1277 first
= gsi_stmt (gsi
);
1278 /* Don't split the bbs containing __builtin_setjmp_receiver
1279 or ABNORMAL_DISPATCHER calls. These are very
1280 special and don't expect anything to be inserted before
1282 if (is_gimple_call (first
)
1283 && (gimple_call_builtin_p (first
, BUILT_IN_SETJMP_RECEIVER
)
1284 || (gimple_call_flags (first
) & ECF_RETURNS_TWICE
)
1285 || (gimple_call_internal_p (first
)
1286 && (gimple_call_internal_fn (first
)
1287 == IFN_ABNORMAL_DISPATCHER
))))
1291 fprintf (dump_file
, "Splitting bb %i after labels\n",
1293 split_block_after_labels (bb
);
1299 el
= create_edge_list ();
1300 num_edges
= NUM_EDGES (el
);
1301 qsort (el
->index_to_edge
, num_edges
, sizeof (edge
), compare_freqs
);
1302 alloc_aux_for_edges (sizeof (struct edge_profile_info
));
1304 /* The basic blocks are expected to be numbered sequentially. */
1308 for (i
= 0 ; i
< num_edges
; i
++)
1310 edge e
= INDEX_EDGE (el
, i
);
1312 /* Mark edges we've replaced by fake edges above as ignored. */
1313 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1314 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1315 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1317 EDGE_INFO (e
)->ignore
= 1;
1322 /* Create spanning tree from basic block graph, mark each edge that is
1323 on the spanning tree. We insert as many abnormal and critical edges
1324 as possible to minimize number of edge splits necessary. */
1327 find_spanning_tree (el
);
1332 /* Keep only edge from entry block to be instrumented. */
1333 FOR_EACH_BB_FN (bb
, cfun
)
1334 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1335 EDGE_INFO (e
)->ignore
= true;
1339 /* Fake edges that are not on the tree will not be instrumented, so
1340 mark them ignored. */
1341 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1343 edge e
= INDEX_EDGE (el
, i
);
1344 struct edge_profile_info
*inf
= EDGE_INFO (e
);
1346 if (inf
->ignore
|| inf
->on_tree
)
1348 else if (e
->flags
& EDGE_FAKE
)
1357 total_num_blocks
+= n_basic_blocks_for_fn (cfun
);
1359 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks_for_fn (cfun
));
1361 total_num_edges
+= num_edges
;
1363 fprintf (dump_file
, "%d edges\n", num_edges
);
1365 total_num_edges_ignored
+= ignored_edges
;
1367 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1369 total_num_edges_instrumented
+= num_instrumented
;
1371 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1373 /* Dump function body before it's instrumented.
1374 It helps to debug gcov tool. */
1375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1376 dump_function_to_file (cfun
->decl
, dump_file
, dump_flags
);
1378 /* Compute two different checksums. Note that we want to compute
1379 the checksum in only once place, since it depends on the shape
1380 of the control flow which can change during
1381 various transformations. */
1384 /* At stream in time we do not have CFG, so we cannot do checksums. */
1386 lineno_checksum
= 0;
1390 cfg_checksum
= coverage_compute_cfg_checksum (cfun
);
1391 lineno_checksum
= coverage_compute_lineno_checksum ();
1394 /* Write the data from which gcov can reconstruct the basic block
1395 graph and function line numbers (the gcno file). */
1396 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1398 gcov_position_t offset
;
1400 /* Basic block flags */
1401 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1402 gcov_write_unsigned (n_basic_blocks_for_fn (cfun
));
1403 gcov_write_length (offset
);
1406 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1407 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1412 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1413 gcov_write_unsigned (bb
->index
);
1415 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1417 struct edge_profile_info
*i
= EDGE_INFO (e
);
1420 unsigned flag_bits
= 0;
1423 flag_bits
|= GCOV_ARC_ON_TREE
;
1424 if (e
->flags
& EDGE_FAKE
)
1425 flag_bits
|= GCOV_ARC_FAKE
;
1426 if (e
->flags
& EDGE_FALLTHRU
)
1427 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1428 /* On trees we don't have fallthru flags, but we can
1429 recompute them from CFG shape. */
1430 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1431 && e
->src
->next_bb
== e
->dest
)
1432 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1434 gcov_write_unsigned (e
->dest
->index
);
1435 gcov_write_unsigned (flag_bits
);
1439 gcov_write_length (offset
);
1443 /* Initialize the output. */
1444 output_location (&streamed_locations
, NULL
, 0, NULL
, NULL
);
1446 hash_set
<location_hash
> seen_locations
;
1448 FOR_EACH_BB_FN (bb
, cfun
)
1450 gimple_stmt_iterator gsi
;
1451 gcov_position_t offset
= 0;
1453 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
1455 location_t loc
= DECL_SOURCE_LOCATION (current_function_decl
);
1456 gcc_checking_assert (!RESERVED_LOCATION_P (loc
));
1457 seen_locations
.add (loc
);
1458 expanded_location curr_location
= expand_location (loc
);
1459 output_location (&streamed_locations
, curr_location
.file
,
1460 MAX (1, curr_location
.line
), &offset
, bb
);
1463 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1465 gimple
*stmt
= gsi_stmt (gsi
);
1466 location_t loc
= gimple_location (stmt
);
1467 if (!RESERVED_LOCATION_P (loc
))
1469 seen_locations
.add (loc
);
1470 output_location (&streamed_locations
, gimple_filename (stmt
),
1471 MAX (1, gimple_lineno (stmt
)), &offset
, bb
);
1475 /* Notice GOTO expressions eliminated while constructing the CFG.
1476 It's hard to distinguish such expression, but goto_locus should
1477 not be any of already seen location. */
1479 if (single_succ_p (bb
)
1480 && (loc
= single_succ_edge (bb
)->goto_locus
)
1481 && !RESERVED_LOCATION_P (loc
)
1482 && !seen_locations
.contains (loc
))
1484 expanded_location curr_location
= expand_location (loc
);
1485 output_location (&streamed_locations
, curr_location
.file
,
1486 MAX (1, curr_location
.line
), &offset
, bb
);
1491 /* A file of NULL indicates the end of run. */
1492 gcov_write_unsigned (0);
1493 gcov_write_string (NULL
);
1494 gcov_write_length (offset
);
1499 if (flag_profile_values
)
1500 gimple_find_values_to_profile (&values
);
1502 if (flag_branch_probabilities
)
1504 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1505 if (flag_profile_values
)
1506 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1509 remove_fake_edges ();
1511 /* For each edge not on the spanning tree, add counting code. */
1512 if (profile_arc_flag
1513 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1515 unsigned n_instrumented
;
1517 gimple_init_gcov_profiler ();
1519 n_instrumented
= instrument_edges (el
);
1521 gcc_assert (n_instrumented
== num_instrumented
);
1523 if (flag_profile_values
)
1524 instrument_values (values
);
1526 /* Commit changes done by instrumentation. */
1527 gsi_commit_edge_inserts ();
1530 free_aux_for_edges ();
1533 free_edge_list (el
);
1534 coverage_end_function (lineno_checksum
, cfg_checksum
);
1535 if (flag_branch_probabilities
1536 && (profile_status_for_fn (cfun
) == PROFILE_READ
))
1538 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1539 report_predictor_hitrates ();
1541 /* At this moment we have precise loop iteration count estimates.
1542 Record them to loop structure before the profile gets out of date. */
1543 for (auto loop
: loops_list (cfun
, 0))
1544 if (loop
->header
->count
> 0 && loop
->header
->count
.reliable_p ())
1546 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
1547 widest_int bound
= gcov_type_to_wide_int (nit
);
1548 loop
->any_estimate
= false;
1549 record_niter_bound (loop
, bound
, true, false);
1551 compute_function_frequency ();
1555 /* Union find algorithm implementation for the basic blocks using
1559 find_group (basic_block bb
)
1561 basic_block group
= bb
, bb1
;
1563 while ((basic_block
) group
->aux
!= group
)
1564 group
= (basic_block
) group
->aux
;
1566 /* Compress path. */
1567 while ((basic_block
) bb
->aux
!= group
)
1569 bb1
= (basic_block
) bb
->aux
;
1570 bb
->aux
= (void *) group
;
1577 union_groups (basic_block bb1
, basic_block bb2
)
1579 basic_block bb1g
= find_group (bb1
);
1580 basic_block bb2g
= find_group (bb2
);
1582 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1583 this code is unlikely going to be performance problem anyway. */
1584 gcc_assert (bb1g
!= bb2g
);
1589 /* This function searches all of the edges in the program flow graph, and puts
1590 as many bad edges as possible onto the spanning tree. Bad edges include
1591 abnormals edges, which can't be instrumented at the moment. Since it is
1592 possible for fake edges to form a cycle, we will have to develop some
1593 better way in the future. Also put critical edges to the tree, since they
1594 are more expensive to instrument. */
1597 find_spanning_tree (struct edge_list
*el
)
1600 int num_edges
= NUM_EDGES (el
);
1603 /* We use aux field for standard union-find algorithm. */
1604 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
1607 /* Add fake edge exit to entry we can't instrument. */
1608 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun
), ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1610 /* First add all abnormal edges to the tree unless they form a cycle. Also
1611 add all edges to the exit block to avoid inserting profiling code behind
1612 setting return value from function. */
1613 for (i
= 0; i
< num_edges
; i
++)
1615 edge e
= INDEX_EDGE (el
, i
);
1616 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1617 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1618 && !EDGE_INFO (e
)->ignore
1619 && (find_group (e
->src
) != find_group (e
->dest
)))
1622 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1623 e
->src
->index
, e
->dest
->index
);
1624 EDGE_INFO (e
)->on_tree
= 1;
1625 union_groups (e
->src
, e
->dest
);
1629 /* And now the rest. Edge list is sorted according to frequencies and
1630 thus we will produce minimal spanning tree. */
1631 for (i
= 0; i
< num_edges
; i
++)
1633 edge e
= INDEX_EDGE (el
, i
);
1634 if (!EDGE_INFO (e
)->ignore
1635 && find_group (e
->src
) != find_group (e
->dest
))
1638 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1639 e
->src
->index
, e
->dest
->index
);
1640 EDGE_INFO (e
)->on_tree
= 1;
1641 union_groups (e
->src
, e
->dest
);
1645 clear_aux_for_blocks ();
1648 /* Perform file-level initialization for branch-prob processing. */
1651 init_branch_prob (void)
1655 total_num_blocks
= 0;
1656 total_num_edges
= 0;
1657 total_num_edges_ignored
= 0;
1658 total_num_edges_instrumented
= 0;
1659 total_num_blocks_created
= 0;
1660 total_num_passes
= 0;
1661 total_num_times_called
= 0;
1662 total_num_branches
= 0;
1663 for (i
= 0; i
< 20; i
++)
1664 total_hist_br_prob
[i
] = 0;
1667 /* Performs file-level cleanup after branch-prob processing
1671 end_branch_prob (void)
1675 fprintf (dump_file
, "\n");
1676 fprintf (dump_file
, "Total number of blocks: %d\n",
1678 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1679 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1680 total_num_edges_ignored
);
1681 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1682 total_num_edges_instrumented
);
1683 fprintf (dump_file
, "Total number of blocks created: %d\n",
1684 total_num_blocks_created
);
1685 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1687 if (total_num_times_called
!= 0)
1688 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1689 (total_num_passes
+ (total_num_times_called
>> 1))
1690 / total_num_times_called
);
1691 fprintf (dump_file
, "Total number of branches: %d\n",
1692 total_num_branches
);
1693 if (total_num_branches
)
1697 for (i
= 0; i
< 10; i
++)
1698 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1699 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1700 / total_num_branches
, 5*i
, 5*i
+5);