1 /* Calculate branch probabilities, and basic block execution counts.
2 Copyright (C) 1990-2024 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"
73 struct condcov
*find_conditions (struct function
*);
74 size_t cov_length (const struct condcov
*);
75 array_slice
<basic_block
> cov_blocks (struct condcov
*, size_t);
76 array_slice
<uint64_t> cov_masks (struct condcov
*, size_t);
77 array_slice
<sbitmap
> cov_maps (struct condcov
* cov
, size_t n
);
78 void cov_free (struct condcov
*);
79 size_t instrument_decisions (array_slice
<basic_block
>, size_t,
81 array_slice
<gcov_type_unsigned
>);
83 /* Map from BBs/edges to gcov counters. */
84 vec
<gcov_type
> bb_gcov_counts
;
85 hash_map
<edge
,gcov_type
> *edge_gcov_counts
;
87 struct bb_profile_info
{
88 unsigned int count_valid
: 1;
90 /* Number of successor and predecessor edges. */
95 #define BB_INFO(b) ((struct bb_profile_info *) (b)->aux)
98 /* Counter summary from the last set of coverage counts read. */
100 gcov_summary
*profile_info
;
102 /* Collect statistics on the performance of this pass for the entire source
105 static int total_num_blocks
;
106 static int total_num_edges
;
107 static int total_num_edges_ignored
;
108 static int total_num_edges_instrumented
;
109 static int total_num_blocks_created
;
110 static int total_num_passes
;
111 static int total_num_times_called
;
112 static int total_hist_br_prob
[20];
113 static int total_num_branches
;
114 static int total_num_conds
;
116 /* Forward declarations. */
117 static void find_spanning_tree (struct edge_list
*);
119 /* Add edge instrumentation code to the entire insn chain.
121 F is the first insn of the chain.
122 NUM_BLOCKS is the number of basic blocks found in F. */
125 instrument_edges (struct edge_list
*el
)
127 unsigned num_instr_edges
= 0;
128 int num_edges
= NUM_EDGES (el
);
131 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
136 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
138 struct edge_profile_info
*inf
= EDGE_INFO (e
);
140 if (!inf
->ignore
&& !inf
->on_tree
)
142 gcc_assert (!(e
->flags
& EDGE_ABNORMAL
));
144 fprintf (dump_file
, "Edge %d to %d instrumented%s\n",
145 e
->src
->index
, e
->dest
->index
,
146 EDGE_CRITICAL_P (e
) ? " (and split)" : "");
147 gimple_gen_edge_profiler (num_instr_edges
++, e
);
152 total_num_blocks_created
+= num_edges
;
154 fprintf (dump_file
, "%d edges instrumented\n", num_instr_edges
);
155 return num_instr_edges
;
158 /* Add code to measure histograms for values in list VALUES. */
160 instrument_values (histogram_values values
)
164 /* Emit code to generate the histograms before the insns. */
166 for (i
= 0; i
< values
.length (); i
++)
168 histogram_value hist
= values
[i
];
169 unsigned t
= COUNTER_FOR_HIST_TYPE (hist
->type
);
171 if (!coverage_counter_alloc (t
, hist
->n_counters
))
176 case HIST_TYPE_INTERVAL
:
177 gimple_gen_interval_profiler (hist
, t
);
181 gimple_gen_pow2_profiler (hist
, t
);
184 case HIST_TYPE_TOPN_VALUES
:
185 gimple_gen_topn_values_profiler (hist
, t
);
188 case HIST_TYPE_INDIR_CALL
:
189 gimple_gen_ic_profiler (hist
, t
);
192 case HIST_TYPE_AVERAGE
:
193 gimple_gen_average_profiler (hist
, t
);
197 gimple_gen_ior_profiler (hist
, t
);
200 case HIST_TYPE_TIME_PROFILE
:
201 gimple_gen_time_profiler (t
);
211 /* Computes hybrid profile for all matching entries in da_file.
213 CFG_CHECKSUM is the precomputed checksum for the CFG. */
216 get_exec_counts (unsigned cfg_checksum
, unsigned lineno_checksum
)
218 unsigned num_edges
= 0;
222 /* Count the edges to be (possibly) instrumented. */
223 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
228 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
229 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
233 counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, cfg_checksum
,
234 lineno_checksum
, num_edges
);
242 is_edge_inconsistent (vec
<edge
, va_gc
> *edges
)
246 FOR_EACH_EDGE (e
, ei
, edges
)
248 if (!EDGE_INFO (e
)->ignore
)
250 if (edge_gcov_count (e
) < 0
251 && (!(e
->flags
& EDGE_FAKE
)
252 || !block_ends_with_call_p (e
->src
)))
257 "Edge %i->%i is inconsistent, count%" PRId64
,
258 e
->src
->index
, e
->dest
->index
, edge_gcov_count (e
));
259 dump_bb (dump_file
, e
->src
, 0, TDF_DETAILS
);
260 dump_bb (dump_file
, e
->dest
, 0, TDF_DETAILS
);
270 correct_negative_edge_counts (void)
276 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
278 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
280 if (edge_gcov_count (e
) < 0)
281 edge_gcov_count (e
) = 0;
286 /* Check consistency.
287 Return true if inconsistency is found. */
289 is_inconsistent (void)
292 bool inconsistent
= false;
293 FOR_EACH_BB_FN (bb
, cfun
)
295 inconsistent
|= is_edge_inconsistent (bb
->preds
);
296 if (!dump_file
&& inconsistent
)
298 inconsistent
|= is_edge_inconsistent (bb
->succs
);
299 if (!dump_file
&& inconsistent
)
301 if (bb_gcov_count (bb
) < 0)
305 fprintf (dump_file
, "BB %i count is negative "
309 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
313 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->preds
))
317 fprintf (dump_file
, "BB %i count does not match sum of incoming edges "
318 "%" PRId64
" should be %" PRId64
,
321 sum_edge_counts (bb
->preds
));
322 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
326 if (bb_gcov_count (bb
) != sum_edge_counts (bb
->succs
) &&
327 ! (find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
)) != NULL
328 && block_ends_with_call_p (bb
)))
332 fprintf (dump_file
, "BB %i count does not match sum of outgoing edges "
333 "%" PRId64
" should be %" PRId64
,
336 sum_edge_counts (bb
->succs
));
337 dump_bb (dump_file
, bb
, 0, TDF_DETAILS
);
341 if (!dump_file
&& inconsistent
)
348 /* Set each basic block count to the sum of its outgoing edge counts */
353 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
355 bb_gcov_count (bb
) = sum_edge_counts (bb
->succs
);
356 gcc_assert (bb_gcov_count (bb
) >= 0);
360 /* Reads profile data and returns total number of edge counts read */
362 read_profile_edge_counts (gcov_type
*exec_counts
)
366 int exec_counts_pos
= 0;
367 /* For each edge not on the spanning tree, set its execution count from
369 /* The first count in the .da file is the number of times that the function
370 was entered. This is the exec_count for block zero. */
372 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
377 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
378 if (!EDGE_INFO (e
)->ignore
&& !EDGE_INFO (e
)->on_tree
)
382 edge_gcov_count (e
) = exec_counts
[exec_counts_pos
++];
384 edge_gcov_count (e
) = 0;
386 EDGE_INFO (e
)->count_valid
= 1;
387 BB_INFO (bb
)->succ_count
--;
388 BB_INFO (e
->dest
)->pred_count
--;
391 fprintf (dump_file
, "\nRead edge from %i to %i, count:",
392 bb
->index
, e
->dest
->index
);
393 fprintf (dump_file
, "%" PRId64
,
394 (int64_t) edge_gcov_count (e
));
402 /* BB statistics comparing guessed frequency of BB with feedback. */
407 double guessed
, feedback
;
411 /* Compare limit_tuple intervals by first item in descending order. */
414 cmp_stats (const void *ptr1
, const void *ptr2
)
416 const bb_stats
*p1
= (const bb_stats
*)ptr1
;
417 const bb_stats
*p2
= (const bb_stats
*)ptr2
;
419 if (p1
->feedback
< p2
->feedback
)
421 else if (p1
->feedback
> p2
->feedback
)
427 /* Compute the branch probabilities for the various branches.
428 Annotate them accordingly.
430 CFG_CHECKSUM is the precomputed checksum for the CFG. */
433 compute_branch_probabilities (unsigned cfg_checksum
, unsigned lineno_checksum
)
440 int hist_br_prob
[20];
442 gcov_type
*exec_counts
= get_exec_counts (cfg_checksum
, lineno_checksum
);
443 int inconsistent
= 0;
445 /* Very simple sanity checks so we catch bugs in our profiling code. */
449 fprintf (dump_file
, "Profile info is missing; giving up\n");
453 bb_gcov_counts
.safe_grow_cleared (last_basic_block_for_fn (cfun
), true);
454 edge_gcov_counts
= new hash_map
<edge
,gcov_type
>;
456 /* Attach extra info block to each bb. */
457 alloc_aux_for_blocks (sizeof (struct bb_profile_info
));
458 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
463 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
464 if (!EDGE_INFO (e
)->ignore
)
465 BB_INFO (bb
)->succ_count
++;
466 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
467 if (!EDGE_INFO (e
)->ignore
)
468 BB_INFO (bb
)->pred_count
++;
471 /* Avoid predicting entry on exit nodes. */
472 BB_INFO (EXIT_BLOCK_PTR_FOR_FN (cfun
))->succ_count
= 2;
473 BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->pred_count
= 2;
475 num_edges
= read_profile_edge_counts (exec_counts
);
478 fprintf (dump_file
, "\n%d edge counts read\n", num_edges
);
480 /* For every block in the file,
481 - if every exit/entrance edge has a known count, then set the block count
482 - if the block count is known, and every exit/entrance edge but one has
483 a known execution count, then set the count of the remaining edge
485 As edge counts are set, decrement the succ/pred count, but don't delete
486 the edge, that way we can easily tell when all edges are known, or only
487 one edge is unknown. */
489 /* The order that the basic blocks are iterated through is important.
490 Since the code that finds spanning trees starts with block 0, low numbered
491 edges are put on the spanning tree in preference to high numbered edges.
492 Hence, most instrumented edges are at the end. Graph solving works much
493 faster if we propagate numbers from the end to the start.
495 This takes an average of slightly more than 3 passes. */
503 FOR_BB_BETWEEN (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), NULL
, prev_bb
)
505 struct bb_profile_info
*bi
= BB_INFO (bb
);
506 if (! bi
->count_valid
)
508 if (bi
->succ_count
== 0)
514 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
515 total
+= edge_gcov_count (e
);
516 bb_gcov_count (bb
) = total
;
520 else if (bi
->pred_count
== 0)
526 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
527 total
+= edge_gcov_count (e
);
528 bb_gcov_count (bb
) = total
;
535 if (bi
->succ_count
== 1)
541 /* One of the counts will be invalid, but it is zero,
542 so adding it in also doesn't hurt. */
543 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
544 total
+= edge_gcov_count (e
);
546 /* Search for the invalid edge, and set its count. */
547 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
548 if (! EDGE_INFO (e
)->count_valid
&& ! EDGE_INFO (e
)->ignore
)
551 /* Calculate count for remaining edge by conservation. */
552 total
= bb_gcov_count (bb
) - total
;
555 EDGE_INFO (e
)->count_valid
= 1;
556 edge_gcov_count (e
) = total
;
559 BB_INFO (e
->dest
)->pred_count
--;
562 if (bi
->pred_count
== 1)
568 /* One of the counts will be invalid, but it is zero,
569 so adding it in also doesn't hurt. */
570 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
571 total
+= edge_gcov_count (e
);
573 /* Search for the invalid edge, and set its count. */
574 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
575 if (!EDGE_INFO (e
)->count_valid
&& !EDGE_INFO (e
)->ignore
)
578 /* Calculate count for remaining edge by conservation. */
579 total
= bb_gcov_count (bb
) - total
+ edge_gcov_count (e
);
582 EDGE_INFO (e
)->count_valid
= 1;
583 edge_gcov_count (e
) = total
;
586 BB_INFO (e
->src
)->succ_count
--;
593 total_num_passes
+= passes
;
595 fprintf (dump_file
, "Graph solving took %d passes.\n\n", passes
);
597 /* If the graph has been correctly solved, every block will have a
598 succ and pred count of zero. */
599 FOR_EACH_BB_FN (bb
, cfun
)
601 gcc_assert (!BB_INFO (bb
)->succ_count
&& !BB_INFO (bb
)->pred_count
);
604 /* Check for inconsistent basic block counts */
605 inconsistent
= is_inconsistent ();
609 if (flag_profile_correction
)
611 /* Inconsistency detected. Make it flow-consistent. */
612 static int informed
= 0;
613 if (dump_enabled_p () && informed
== 0)
616 dump_printf_loc (MSG_NOTE
,
617 dump_user_location_t::from_location_t (input_location
),
618 "correcting inconsistent profile data\n");
620 correct_negative_edge_counts ();
621 /* Set bb counts to the sum of the outgoing edge counts */
624 fprintf (dump_file
, "\nCalling mcf_smooth_cfg\n");
628 error ("corrupted profile info: profile data is not flow-consistent");
631 /* For every edge, calculate its branch probability and add a reg_note
632 to the branch insn to indicate this. */
634 for (i
= 0; i
< 20; i
++)
638 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
643 if (bb_gcov_count (bb
) < 0)
645 error ("corrupted profile info: number of iterations for basic block %d thought to be %i",
646 bb
->index
, (int)bb_gcov_count (bb
));
647 bb_gcov_count (bb
) = 0;
649 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
651 /* Function may return twice in the cased the called function is
652 setjmp or calls fork, but we can't represent this by extra
653 edge from the entry, since extra edge from the exit is
654 already present. We get negative frequency from the entry
656 if ((edge_gcov_count (e
) < 0
657 && e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
658 || (edge_gcov_count (e
) > bb_gcov_count (bb
)
659 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
661 if (block_ends_with_call_p (bb
))
662 edge_gcov_count (e
) = edge_gcov_count (e
) < 0
663 ? 0 : bb_gcov_count (bb
);
665 if (edge_gcov_count (e
) < 0
666 || edge_gcov_count (e
) > bb_gcov_count (bb
))
668 error ("corrupted profile info: number of executions for edge %d-%d thought to be %i",
669 e
->src
->index
, e
->dest
->index
,
670 (int)edge_gcov_count (e
));
671 edge_gcov_count (e
) = bb_gcov_count (bb
) / 2;
674 if (bb_gcov_count (bb
))
676 bool set_to_guessed
= false;
677 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
679 bool prev_never
= e
->probability
== profile_probability::never ();
680 e
->probability
= profile_probability::probability_in_gcov_type
681 (edge_gcov_count (e
), bb_gcov_count (bb
));
682 if (e
->probability
== profile_probability::never ()
684 && flag_profile_partial_training
)
685 set_to_guessed
= true;
688 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
689 e
->probability
= e
->probability
.guessed ();
690 if (bb
->index
>= NUM_FIXED_BLOCKS
691 && block_ends_with_condjump_p (bb
)
692 && EDGE_COUNT (bb
->succs
) >= 2)
698 /* Find the branch edge. It is possible that we do have fake
700 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
701 if (!(e
->flags
& (EDGE_FAKE
| EDGE_FALLTHRU
)))
704 prob
= e
->probability
.to_reg_br_prob_base ();
705 index
= prob
* 20 / REG_BR_PROB_BASE
;
709 hist_br_prob
[index
]++;
714 /* As a last resort, distribute the probabilities evenly.
715 Use simple heuristics that if there are normal edges,
716 give all abnormals frequency of 0, otherwise distribute the
717 frequency over abnormals (this is the case of noreturn
719 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
723 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
724 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
728 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
729 if (!(e
->flags
& (EDGE_COMPLEX
| EDGE_FAKE
)))
731 = profile_probability::guessed_always () / total
;
733 e
->probability
= profile_probability::never ();
737 total
+= EDGE_COUNT (bb
->succs
);
738 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
739 e
->probability
= profile_probability::guessed_always () / total
;
741 if (bb
->index
>= NUM_FIXED_BLOCKS
742 && block_ends_with_condjump_p (bb
)
743 && EDGE_COUNT (bb
->succs
) >= 2)
749 && (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
750 || !flag_profile_partial_training
))
751 profile_status_for_fn (cfun
) = PROFILE_READ
;
753 /* If we have real data, use them! */
754 if (bb_gcov_count (ENTRY_BLOCK_PTR_FOR_FN (cfun
))
755 || !flag_guess_branch_prob
)
757 profile_count old_entry_cnt
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
758 auto_vec
<bb_stats
> stats
;
759 double sum1
= 0, sum2
= 0;
761 FOR_ALL_BB_FN (bb
, cfun
)
763 profile_count cnt
= bb
->count
;
764 if (bb_gcov_count (bb
) || !flag_profile_partial_training
)
765 bb
->count
= profile_count::from_gcov_type (bb_gcov_count (bb
));
767 bb
->count
= profile_count::guessed_zero ();
769 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && bb
->index
>= 0)
771 double freq1
= cnt
.to_sreal_scale (old_entry_cnt
).to_double ();
772 double freq2
= bb
->count
.to_sreal_scale
773 (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
).
775 bb_stats stat
= {bb
, freq1
, freq2
,
776 (int64_t) bb_gcov_count (bb
)};
777 stats
.safe_push (stat
);
782 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
784 double nsum1
= 0, nsum2
= 0;
785 stats
.qsort (cmp_stats
);
786 for (auto stat
: stats
)
788 nsum1
+= stat
.guessed
;
789 nsum2
+= stat
.feedback
;
791 " Basic block %4i guessed freq: %12.3f"
792 " cumulative:%6.2f%% "
793 " feedback freq: %12.3f cumulative:%7.2f%%"
794 " cnt: 10%" PRId64
"\n", stat
.bb
->index
,
803 /* If function was not trained, preserve local estimates including statically
804 determined zero counts. */
805 else if (profile_status_for_fn (cfun
) == PROFILE_READ
806 && !flag_profile_partial_training
)
807 FOR_ALL_BB_FN (bb
, cfun
)
808 if (!(bb
->count
== profile_count::zero ()))
809 bb
->count
= bb
->count
.global0 ();
811 bb_gcov_counts
.release ();
812 delete edge_gcov_counts
;
813 edge_gcov_counts
= NULL
;
815 update_max_bb_count ();
819 fprintf (dump_file
, " Profile feedback for function");
820 fprintf (dump_file
, ((profile_status_for_fn (cfun
) == PROFILE_READ
)
822 : " is not available \n"));
824 fprintf (dump_file
, "%d branches\n", num_branches
);
826 for (i
= 0; i
< 10; i
++)
827 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
828 (hist_br_prob
[i
] + hist_br_prob
[19-i
]) * 100 / num_branches
,
831 total_num_branches
+= num_branches
;
832 for (i
= 0; i
< 20; i
++)
833 total_hist_br_prob
[i
] += hist_br_prob
[i
];
835 fputc ('\n', dump_file
);
836 fputc ('\n', dump_file
);
838 gimple_dump_cfg (dump_file
, TDF_BLOCKS
);
841 free_aux_for_blocks ();
844 /* Sort the histogram value and count for TOPN and INDIR_CALL type. */
847 sort_hist_values (histogram_value hist
)
849 gcc_assert (hist
->type
== HIST_TYPE_TOPN_VALUES
850 || hist
->type
== HIST_TYPE_INDIR_CALL
);
852 int counters
= hist
->hvalue
.counters
[1];
853 for (int i
= 0; i
< counters
- 1; i
++)
854 /* Hist value is organized as:
855 [total_executions, N, value1, counter1, ..., valueN, counterN]
856 Use decrease bubble sort to rearrange it. The sort starts from <value1,
857 counter1> and compares counter first. If counter is same, compares the
858 value, exchange it if small to keep stable. */
861 bool swapped
= false;
862 for (int j
= 0; j
< counters
- 1 - i
; j
++)
864 gcov_type
*p
= &hist
->hvalue
.counters
[2 * j
+ 2];
865 if (p
[1] < p
[3] || (p
[1] == p
[3] && p
[0] < p
[2]))
867 std::swap (p
[0], p
[2]);
868 std::swap (p
[1], p
[3]);
876 /* Load value histograms values whose description is stored in VALUES array
879 CFG_CHECKSUM is the precomputed checksum for the CFG. */
882 compute_value_histograms (histogram_values values
, unsigned cfg_checksum
,
883 unsigned lineno_checksum
)
885 unsigned i
, j
, t
, any
;
886 unsigned n_histogram_counters
[GCOV_N_VALUE_COUNTERS
];
887 gcov_type
*histogram_counts
[GCOV_N_VALUE_COUNTERS
];
888 gcov_type
*act_count
[GCOV_N_VALUE_COUNTERS
];
889 gcov_type
*aact_count
;
890 struct cgraph_node
*node
;
892 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
893 n_histogram_counters
[t
] = 0;
895 for (i
= 0; i
< values
.length (); i
++)
897 histogram_value hist
= values
[i
];
898 n_histogram_counters
[(int) hist
->type
] += hist
->n_counters
;
902 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
904 if (!n_histogram_counters
[t
])
906 histogram_counts
[t
] = NULL
;
910 histogram_counts
[t
] = get_coverage_counts (COUNTER_FOR_HIST_TYPE (t
),
913 n_histogram_counters
[t
]);
914 if (histogram_counts
[t
])
916 act_count
[t
] = histogram_counts
[t
];
921 for (i
= 0; i
< values
.length (); i
++)
923 histogram_value hist
= values
[i
];
924 gimple
*stmt
= hist
->hvalue
.stmt
;
926 t
= (int) hist
->type
;
927 bool topn_p
= (hist
->type
== HIST_TYPE_TOPN_VALUES
928 || hist
->type
== HIST_TYPE_INDIR_CALL
);
930 /* TOP N counter uses variable number of counters. */
935 total_size
= 2 + 2 * act_count
[t
][1];
938 gimple_add_histogram_value (cfun
, stmt
, hist
);
939 hist
->n_counters
= total_size
;
940 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
941 for (j
= 0; j
< hist
->n_counters
; j
++)
943 hist
->hvalue
.counters
[j
] = act_count
[t
][j
];
945 hist
->hvalue
.counters
[j
] = 0;
946 act_count
[t
] += hist
->n_counters
;
947 sort_hist_values (hist
);
951 aact_count
= act_count
[t
];
954 act_count
[t
] += hist
->n_counters
;
956 gimple_add_histogram_value (cfun
, stmt
, hist
);
957 hist
->hvalue
.counters
= XNEWVEC (gcov_type
, hist
->n_counters
);
958 for (j
= 0; j
< hist
->n_counters
; j
++)
960 hist
->hvalue
.counters
[j
] = aact_count
[j
];
962 hist
->hvalue
.counters
[j
] = 0;
965 /* Time profiler counter is not related to any statement,
966 so that we have to read the counter and set the value to
967 the corresponding call graph node. */
968 if (hist
->type
== HIST_TYPE_TIME_PROFILE
)
970 node
= cgraph_node::get (hist
->fun
->decl
);
971 if (hist
->hvalue
.counters
[0] >= 0
972 && hist
->hvalue
.counters
[0] < INT_MAX
/ 2)
973 node
->tp_first_run
= hist
->hvalue
.counters
[0];
976 if (flag_profile_correction
)
977 error ("corrupted profile info: invalid time profile");
978 node
->tp_first_run
= 0;
981 /* Drop profile for -fprofile-reproducible=multithreaded. */
983 = (flag_profile_reproducible
== PROFILE_REPRODUCIBILITY_MULTITHREADED
);
985 node
->tp_first_run
= 0;
988 fprintf (dump_file
, "Read tp_first_run: %d%s\n", node
->tp_first_run
,
989 drop
? "; ignored because profile reproducibility is "
990 "multi-threaded" : "");
994 for (t
= 0; t
< GCOV_N_VALUE_COUNTERS
; t
++)
995 free (histogram_counts
[t
]);
998 /* Location triplet which records a location. */
999 struct location_triplet
1001 const char *filename
;
1006 /* Traits class for streamed_locations hash set below. */
1008 struct location_triplet_hash
: typed_noop_remove
<location_triplet
>
1010 typedef location_triplet value_type
;
1011 typedef location_triplet compare_type
;
1014 hash (const location_triplet
&ref
)
1016 inchash::hash
hstate (0);
1018 hstate
.add_int (strlen (ref
.filename
));
1019 hstate
.add_int (ref
.lineno
);
1020 hstate
.add_int (ref
.bb_index
);
1021 return hstate
.end ();
1025 equal (const location_triplet
&ref1
, const location_triplet
&ref2
)
1027 return ref1
.lineno
== ref2
.lineno
1028 && ref1
.bb_index
== ref2
.bb_index
1029 && ref1
.filename
!= NULL
1030 && ref2
.filename
!= NULL
1031 && strcmp (ref1
.filename
, ref2
.filename
) == 0;
1035 mark_deleted (location_triplet
&ref
)
1040 static const bool empty_zero_p
= false;
1043 mark_empty (location_triplet
&ref
)
1049 is_deleted (const location_triplet
&ref
)
1051 return ref
.lineno
== -1;
1055 is_empty (const location_triplet
&ref
)
1057 return ref
.lineno
== -2;
1064 /* When passed NULL as file_name, initialize.
1065 When passed something else, output the necessary commands to change
1066 line to LINE and offset to FILE_NAME. */
1068 output_location (hash_set
<location_triplet_hash
> *streamed_locations
,
1069 char const *file_name
, int line
,
1070 gcov_position_t
*offset
, basic_block bb
)
1072 static char const *prev_file_name
;
1073 static int prev_line
;
1074 bool name_differs
, line_differs
;
1076 if (file_name
!= NULL
)
1077 file_name
= remap_profile_filename (file_name
);
1079 location_triplet triplet
;
1080 triplet
.filename
= file_name
;
1081 triplet
.lineno
= line
;
1082 triplet
.bb_index
= bb
? bb
->index
: 0;
1084 if (streamed_locations
->add (triplet
))
1089 prev_file_name
= NULL
;
1094 name_differs
= !prev_file_name
|| filename_cmp (file_name
, prev_file_name
);
1095 line_differs
= prev_line
!= line
;
1099 *offset
= gcov_write_tag (GCOV_TAG_LINES
);
1100 gcov_write_unsigned (bb
->index
);
1101 name_differs
= line_differs
= true;
1104 /* If this is a new source file, then output the
1105 file's name to the .bb file. */
1108 prev_file_name
= file_name
;
1109 gcov_write_unsigned (0);
1110 gcov_write_filename (prev_file_name
);
1114 gcov_write_unsigned (line
);
1119 /* Helper for qsort so edges get sorted from highest frequency to smallest.
1120 This controls the weight for minimal spanning tree algorithm */
1122 compare_freqs (const void *p1
, const void *p2
)
1124 const_edge e1
= *(const const_edge
*)p1
;
1125 const_edge e2
= *(const const_edge
*)p2
;
1127 /* Critical edges needs to be split which introduce extra control flow.
1128 Make them more heavy. */
1129 int m1
= EDGE_CRITICAL_P (e1
) ? 2 : 1;
1130 int m2
= EDGE_CRITICAL_P (e2
) ? 2 : 1;
1132 if (EDGE_FREQUENCY (e1
) * m1
+ m1
!= EDGE_FREQUENCY (e2
) * m2
+ m2
)
1133 return EDGE_FREQUENCY (e2
) * m2
+ m2
- EDGE_FREQUENCY (e1
) * m1
- m1
;
1134 /* Stabilize sort. */
1135 if (e1
->src
->index
!= e2
->src
->index
)
1136 return e2
->src
->index
- e1
->src
->index
;
1137 return e2
->dest
->index
- e1
->dest
->index
;
1140 /* Only read execution count for thunks. */
1143 read_thunk_profile (struct cgraph_node
*node
)
1145 tree old
= current_function_decl
;
1146 current_function_decl
= node
->decl
;
1147 gcov_type
*counts
= get_coverage_counts (GCOV_COUNTER_ARCS
, 0, 0, 1);
1150 node
->callees
->count
= node
->count
1151 = profile_count::from_gcov_type (counts
[0]);
1154 current_function_decl
= old
;
1159 /* Instrument and/or analyze program behavior based on program the CFG.
1161 This function creates a representation of the control flow graph (of
1162 the function being compiled) that is suitable for the instrumentation
1163 of edges and/or converting measured edge counts to counts on the
1166 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
1167 the flow graph that are needed to reconstruct the dynamic behavior of the
1168 flow graph. This data is written to the gcno file for gcov.
1170 When FLAG_PROFILE_CONDITIONS is nonzero, this functions instruments the
1171 edges in the control flow graph to track what conditions are evaluated to in
1172 order to determine what conditions are covered and have an independent
1173 effect on the outcome (modified condition/decision coverage). This data is
1174 written to the gcno file for gcov.
1176 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
1177 information from the gcda file containing edge count information from
1178 previous executions of the function being compiled. In this case, the
1179 control flow graph is annotated with actual execution counts by
1180 compute_branch_probabilities().
1182 Main entry point of this file. */
1185 branch_prob (bool thunk
)
1189 unsigned num_edges
, ignored_edges
;
1190 unsigned num_instrumented
;
1191 struct edge_list
*el
;
1192 histogram_values values
= histogram_values ();
1193 unsigned cfg_checksum
, lineno_checksum
;
1194 bool output_to_file
;
1196 total_num_times_called
++;
1198 flow_call_edges_add (NULL
);
1199 add_noreturn_fake_exit_edges ();
1201 hash_set
<location_triplet_hash
> streamed_locations
;
1205 /* We can't handle cyclic regions constructed using abnormal edges.
1206 To avoid these we replace every source of abnormal edge by a fake
1207 edge from entry node and every destination by fake edge to exit.
1208 This keeps graph acyclic and our calculation exact for all normal
1209 edges except for exit and entrance ones.
1211 We also add fake exit edges for each call and asm statement in the
1212 basic, since it may not return. */
1214 FOR_EACH_BB_FN (bb
, cfun
)
1216 int need_exit_edge
= 0, need_entry_edge
= 0;
1217 int have_exit_edge
= 0, have_entry_edge
= 0;
1221 /* Functions returning multiple times are not handled by extra edges.
1222 Instead we simply allow negative counts on edges from exit to the
1223 block past call and corresponding probabilities. We can't go
1224 with the extra edges because that would result in flowgraph that
1225 needs to have fake edges outside the spanning tree. */
1227 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1229 gimple_stmt_iterator gsi
;
1230 gimple
*last
= NULL
;
1232 /* It may happen that there are compiler generated statements
1233 without a locus at all. Go through the basic block from the
1234 last to the first statement looking for a locus. */
1235 for (gsi
= gsi_last_nondebug_bb (bb
);
1237 gsi_prev_nondebug (&gsi
))
1239 last
= gsi_stmt (gsi
);
1240 if (!RESERVED_LOCATION_P (gimple_location (last
)))
1244 /* Edge with goto locus might get wrong coverage info unless
1245 it is the only edge out of BB.
1246 Don't do that when the locuses match, so
1247 if (blah) goto something;
1248 is not computed twice. */
1250 && gimple_has_location (last
)
1251 && !RESERVED_LOCATION_P (e
->goto_locus
)
1252 && !single_succ_p (bb
)
1253 && (LOCATION_FILE (e
->goto_locus
)
1254 != LOCATION_FILE (gimple_location (last
))
1255 || (LOCATION_LINE (e
->goto_locus
)
1256 != LOCATION_LINE (gimple_location (last
)))))
1258 basic_block new_bb
= split_edge (e
);
1259 edge ne
= single_succ_edge (new_bb
);
1260 ne
->goto_locus
= e
->goto_locus
;
1262 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1263 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1265 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1268 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1270 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1271 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1272 need_entry_edge
= 1;
1273 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1274 have_entry_edge
= 1;
1277 if (need_exit_edge
&& !have_exit_edge
)
1280 fprintf (dump_file
, "Adding fake exit edge to bb %i\n",
1282 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
1284 if (need_entry_edge
&& !have_entry_edge
)
1287 fprintf (dump_file
, "Adding fake entry edge to bb %i\n",
1289 make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
, EDGE_FAKE
);
1290 /* Avoid bbs that have both fake entry edge and also some
1291 exit edge. One of those edges wouldn't be added to the
1292 spanning tree, but we can't instrument any of them. */
1293 if (have_exit_edge
|| need_exit_edge
)
1295 gimple_stmt_iterator gsi
;
1298 gsi
= gsi_start_nondebug_after_labels_bb (bb
);
1299 gcc_checking_assert (!gsi_end_p (gsi
));
1300 first
= gsi_stmt (gsi
);
1301 /* Don't split the bbs containing __builtin_setjmp_receiver
1302 or ABNORMAL_DISPATCHER calls. These are very
1303 special and don't expect anything to be inserted before
1305 if (is_gimple_call (first
)
1306 && (gimple_call_builtin_p (first
, BUILT_IN_SETJMP_RECEIVER
)
1307 || (gimple_call_flags (first
) & ECF_RETURNS_TWICE
)
1308 || (gimple_call_internal_p (first
)
1309 && (gimple_call_internal_fn (first
)
1310 == IFN_ABNORMAL_DISPATCHER
))))
1314 fprintf (dump_file
, "Splitting bb %i after labels\n",
1316 split_block_after_labels (bb
);
1322 el
= create_edge_list ();
1323 num_edges
= NUM_EDGES (el
);
1324 qsort (el
->index_to_edge
, num_edges
, sizeof (edge
), compare_freqs
);
1325 alloc_aux_for_edges (sizeof (struct edge_profile_info
));
1327 /* The basic blocks are expected to be numbered sequentially. */
1331 for (i
= 0 ; i
< num_edges
; i
++)
1333 edge e
= INDEX_EDGE (el
, i
);
1335 /* Mark edges we've replaced by fake edges above as ignored. */
1336 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
))
1337 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1338 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1340 EDGE_INFO (e
)->ignore
= 1;
1345 /* Create spanning tree from basic block graph, mark each edge that is
1346 on the spanning tree. We insert as many abnormal and critical edges
1347 as possible to minimize number of edge splits necessary. */
1350 find_spanning_tree (el
);
1355 /* Keep only edge from entry block to be instrumented. */
1356 FOR_EACH_BB_FN (bb
, cfun
)
1357 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1358 EDGE_INFO (e
)->ignore
= true;
1362 /* Fake edges that are not on the tree will not be instrumented, so
1363 mark them ignored. */
1364 for (num_instrumented
= i
= 0; i
< num_edges
; i
++)
1366 edge e
= INDEX_EDGE (el
, i
);
1367 struct edge_profile_info
*inf
= EDGE_INFO (e
);
1369 if (inf
->ignore
|| inf
->on_tree
)
1371 else if (e
->flags
& EDGE_FAKE
)
1380 total_num_blocks
+= n_basic_blocks_for_fn (cfun
);
1382 fprintf (dump_file
, "%d basic blocks\n", n_basic_blocks_for_fn (cfun
));
1384 total_num_edges
+= num_edges
;
1386 fprintf (dump_file
, "%d edges\n", num_edges
);
1388 total_num_edges_ignored
+= ignored_edges
;
1390 fprintf (dump_file
, "%d ignored edges\n", ignored_edges
);
1392 total_num_edges_instrumented
+= num_instrumented
;
1394 fprintf (dump_file
, "%d instrumentation edges\n", num_instrumented
);
1396 /* Dump function body before it's instrumented.
1397 It helps to debug gcov tool. */
1398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1399 dump_function_to_file (cfun
->decl
, dump_file
, dump_flags
);
1401 /* Compute two different checksums. Note that we want to compute
1402 the checksum in only once place, since it depends on the shape
1403 of the control flow which can change during
1404 various transformations. */
1407 /* At stream in time we do not have CFG, so we cannot do checksums. */
1409 lineno_checksum
= 0;
1413 cfg_checksum
= coverage_compute_cfg_checksum (cfun
);
1414 lineno_checksum
= coverage_compute_lineno_checksum ();
1417 /* Write the data from which gcov can reconstruct the basic block
1418 graph and function line numbers (the gcno file). */
1419 output_to_file
= false;
1420 if (coverage_begin_function (lineno_checksum
, cfg_checksum
))
1422 gcov_position_t offset
;
1424 /* The condition coverage needs a deeper analysis to identify expressions
1425 of conditions, which means it is not yet ready to write to the gcno
1426 file. It will write its entries later, but needs to know if it do it
1427 in the first place, which is controlled by the return value of
1428 coverage_begin_function. */
1429 output_to_file
= true;
1431 /* Basic block flags */
1432 offset
= gcov_write_tag (GCOV_TAG_BLOCKS
);
1433 gcov_write_unsigned (n_basic_blocks_for_fn (cfun
));
1434 gcov_write_length (offset
);
1437 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1438 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1443 offset
= gcov_write_tag (GCOV_TAG_ARCS
);
1444 gcov_write_unsigned (bb
->index
);
1446 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1448 struct edge_profile_info
*i
= EDGE_INFO (e
);
1451 unsigned flag_bits
= 0;
1454 flag_bits
|= GCOV_ARC_ON_TREE
;
1455 if (e
->flags
& EDGE_FAKE
)
1456 flag_bits
|= GCOV_ARC_FAKE
;
1457 if (e
->flags
& EDGE_FALLTHRU
)
1458 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1459 /* On trees we don't have fallthru flags, but we can
1460 recompute them from CFG shape. */
1461 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)
1462 && e
->src
->next_bb
== e
->dest
)
1463 flag_bits
|= GCOV_ARC_FALLTHROUGH
;
1465 gcov_write_unsigned (e
->dest
->index
);
1466 gcov_write_unsigned (flag_bits
);
1470 gcov_write_length (offset
);
1474 /* Initialize the output. */
1475 output_location (&streamed_locations
, NULL
, 0, NULL
, NULL
);
1477 hash_set
<location_hash
> seen_locations
;
1479 FOR_EACH_BB_FN (bb
, cfun
)
1481 gimple_stmt_iterator gsi
;
1482 gcov_position_t offset
= 0;
1484 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
1486 location_t loc
= DECL_SOURCE_LOCATION (current_function_decl
);
1487 if (!RESERVED_LOCATION_P (loc
))
1489 seen_locations
.add (loc
);
1490 expanded_location curr_location
= expand_location (loc
);
1491 output_location (&streamed_locations
, curr_location
.file
,
1492 MAX (1, curr_location
.line
), &offset
, bb
);
1496 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1498 gimple
*stmt
= gsi_stmt (gsi
);
1499 location_t loc
= gimple_location (stmt
);
1500 if (!RESERVED_LOCATION_P (loc
))
1502 seen_locations
.add (loc
);
1503 output_location (&streamed_locations
, gimple_filename (stmt
),
1504 MAX (1, gimple_lineno (stmt
)), &offset
, bb
);
1508 /* Notice GOTO expressions eliminated while constructing the CFG.
1509 It's hard to distinguish such expression, but goto_locus should
1510 not be any of already seen location. */
1512 if (single_succ_p (bb
)
1513 && (loc
= single_succ_edge (bb
)->goto_locus
)
1514 && !RESERVED_LOCATION_P (loc
)
1515 && !seen_locations
.contains (loc
))
1517 expanded_location curr_location
= expand_location (loc
);
1518 output_location (&streamed_locations
, curr_location
.file
,
1519 MAX (1, curr_location
.line
), &offset
, bb
);
1524 /* A file of NULL indicates the end of run. */
1525 gcov_write_unsigned (0);
1526 gcov_write_string (NULL
);
1527 gcov_write_length (offset
);
1532 if (flag_profile_values
)
1533 gimple_find_values_to_profile (&values
);
1535 if (flag_branch_probabilities
)
1537 compute_branch_probabilities (cfg_checksum
, lineno_checksum
);
1538 if (flag_profile_values
)
1539 compute_value_histograms (values
, cfg_checksum
, lineno_checksum
);
1542 remove_fake_edges ();
1544 if (condition_coverage_flag
|| profile_arc_flag
)
1545 gimple_init_gcov_profiler ();
1547 if (condition_coverage_flag
)
1549 struct condcov
*cov
= find_conditions (cfun
);
1551 const size_t nconds
= cov_length (cov
);
1552 total_num_conds
+= nconds
;
1554 if (coverage_counter_alloc (GCOV_COUNTER_CONDS
, 2 * nconds
))
1556 gcov_position_t offset
{};
1558 offset
= gcov_write_tag (GCOV_TAG_CONDS
);
1560 for (size_t i
= 0; i
!= nconds
; ++i
)
1562 array_slice
<basic_block
> expr
= cov_blocks (cov
, i
);
1563 array_slice
<uint64_t> masks
= cov_masks (cov
, i
);
1564 array_slice
<sbitmap
> maps
= cov_maps (cov
, i
);
1565 gcc_assert (expr
.is_valid ());
1566 gcc_assert (masks
.is_valid ());
1567 gcc_assert (maps
.is_valid ());
1569 size_t terms
= instrument_decisions (expr
, i
, maps
, masks
);
1572 gcov_write_unsigned (expr
.front ()->index
);
1573 gcov_write_unsigned (terms
);
1577 gcov_write_length (offset
);
1582 /* For each edge not on the spanning tree, add counting code. */
1583 if (profile_arc_flag
1584 && coverage_counter_alloc (GCOV_COUNTER_ARCS
, num_instrumented
))
1586 unsigned n_instrumented
;
1588 n_instrumented
= instrument_edges (el
);
1590 gcc_assert (n_instrumented
== num_instrumented
);
1592 if (flag_profile_values
)
1593 instrument_values (values
);
1596 free_aux_for_edges ();
1599 free_edge_list (el
);
1600 /* Commit changes done by instrumentation. */
1601 gsi_commit_edge_inserts ();
1603 coverage_end_function (lineno_checksum
, cfg_checksum
);
1604 if (flag_branch_probabilities
1605 && (profile_status_for_fn (cfun
) == PROFILE_READ
))
1607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1608 report_predictor_hitrates ();
1612 /* At this moment we have precise loop iteration count estimates.
1613 Record them to loop structure before the profile gets out of date. */
1614 for (auto loop
: loops_list (cfun
, 0))
1615 if (loop
->header
->count
.ipa ().nonzero_p ()
1616 && expected_loop_iterations_by_profile (loop
, &nit
, &reliable
)
1619 widest_int bound
= nit
.to_nearest_int ();
1620 loop
->any_estimate
= false;
1621 record_niter_bound (loop
, bound
, true, false);
1623 compute_function_frequency ();
1627 /* Union find algorithm implementation for the basic blocks using
1631 find_group (basic_block bb
)
1633 basic_block group
= bb
, bb1
;
1635 while ((basic_block
) group
->aux
!= group
)
1636 group
= (basic_block
) group
->aux
;
1638 /* Compress path. */
1639 while ((basic_block
) bb
->aux
!= group
)
1641 bb1
= (basic_block
) bb
->aux
;
1642 bb
->aux
= (void *) group
;
1649 union_groups (basic_block bb1
, basic_block bb2
)
1651 basic_block bb1g
= find_group (bb1
);
1652 basic_block bb2g
= find_group (bb2
);
1654 /* ??? I don't have a place for the rank field. OK. Lets go w/o it,
1655 this code is unlikely going to be performance problem anyway. */
1656 gcc_assert (bb1g
!= bb2g
);
1661 /* This function searches all of the edges in the program flow graph, and puts
1662 as many bad edges as possible onto the spanning tree. Bad edges include
1663 abnormals edges, which can't be instrumented at the moment. Since it is
1664 possible for fake edges to form a cycle, we will have to develop some
1665 better way in the future. Also put critical edges to the tree, since they
1666 are more expensive to instrument. */
1669 find_spanning_tree (struct edge_list
*el
)
1672 int num_edges
= NUM_EDGES (el
);
1675 /* We use aux field for standard union-find algorithm. */
1676 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
1679 /* Add fake edge exit to entry we can't instrument. */
1680 union_groups (EXIT_BLOCK_PTR_FOR_FN (cfun
), ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1682 /* First add all abnormal edges to the tree unless they form a cycle. Also
1683 add all edges to the exit block to avoid inserting profiling code behind
1684 setting return value from function. */
1685 for (i
= 0; i
< num_edges
; i
++)
1687 edge e
= INDEX_EDGE (el
, i
);
1688 if (((e
->flags
& (EDGE_ABNORMAL
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1689 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1690 && !EDGE_INFO (e
)->ignore
1691 && (find_group (e
->src
) != find_group (e
->dest
)))
1694 fprintf (dump_file
, "Abnormal edge %d to %d put to tree\n",
1695 e
->src
->index
, e
->dest
->index
);
1696 EDGE_INFO (e
)->on_tree
= 1;
1697 union_groups (e
->src
, e
->dest
);
1701 /* And now the rest. Edge list is sorted according to frequencies and
1702 thus we will produce minimal spanning tree. */
1703 for (i
= 0; i
< num_edges
; i
++)
1705 edge e
= INDEX_EDGE (el
, i
);
1706 if (!EDGE_INFO (e
)->ignore
1707 && find_group (e
->src
) != find_group (e
->dest
))
1710 fprintf (dump_file
, "Normal edge %d to %d put to tree\n",
1711 e
->src
->index
, e
->dest
->index
);
1712 EDGE_INFO (e
)->on_tree
= 1;
1713 union_groups (e
->src
, e
->dest
);
1717 clear_aux_for_blocks ();
1720 /* Perform file-level initialization for branch-prob processing. */
1723 init_branch_prob (void)
1727 total_num_blocks
= 0;
1728 total_num_edges
= 0;
1729 total_num_edges_ignored
= 0;
1730 total_num_edges_instrumented
= 0;
1731 total_num_blocks_created
= 0;
1732 total_num_passes
= 0;
1733 total_num_times_called
= 0;
1734 total_num_branches
= 0;
1735 total_num_conds
= 0;
1736 for (i
= 0; i
< 20; i
++)
1737 total_hist_br_prob
[i
] = 0;
1740 /* Performs file-level cleanup after branch-prob processing
1744 end_branch_prob (void)
1748 fprintf (dump_file
, "\n");
1749 fprintf (dump_file
, "Total number of blocks: %d\n",
1751 fprintf (dump_file
, "Total number of edges: %d\n", total_num_edges
);
1752 fprintf (dump_file
, "Total number of ignored edges: %d\n",
1753 total_num_edges_ignored
);
1754 fprintf (dump_file
, "Total number of instrumented edges: %d\n",
1755 total_num_edges_instrumented
);
1756 fprintf (dump_file
, "Total number of blocks created: %d\n",
1757 total_num_blocks_created
);
1758 fprintf (dump_file
, "Total number of graph solution passes: %d\n",
1760 if (total_num_times_called
!= 0)
1761 fprintf (dump_file
, "Average number of graph solution passes: %d\n",
1762 (total_num_passes
+ (total_num_times_called
>> 1))
1763 / total_num_times_called
);
1764 fprintf (dump_file
, "Total number of branches: %d\n",
1765 total_num_branches
);
1766 if (total_num_branches
)
1770 for (i
= 0; i
< 10; i
++)
1771 fprintf (dump_file
, "%d%% branches in range %d-%d%%\n",
1772 (total_hist_br_prob
[i
] + total_hist_br_prob
[19-i
]) * 100
1773 / total_num_branches
, 5*i
, 5*i
+5);
1775 fprintf (dump_file
, "Total number of conditions: %d\n",