1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 [1] "Branch Prediction for Free"
23 Ball and Larus; PLDI '93.
24 [2] "Static Branch Frequency and Program Profile Analysis"
25 Wu and Larus; MICRO-27.
26 [3] "Corpus-based Static Branch Prediction"
27 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
32 #include "coretypes.h"
38 #include "fold-const.h"
42 #include "hard-reg-set.h"
45 #include "dominance.h"
48 #include "basic-block.h"
49 #include "insn-config.h"
54 #include "diagnostic-core.h"
68 #include "tree-ssa-alias.h"
69 #include "internal-fn.h"
70 #include "gimple-expr.h"
73 #include "gimple-iterator.h"
74 #include "gimple-ssa.h"
75 #include "plugin-api.h"
79 #include "tree-phinodes.h"
80 #include "ssa-iterators.h"
81 #include "tree-ssa-loop-niter.h"
82 #include "tree-ssa-loop.h"
83 #include "tree-pass.h"
84 #include "tree-scalar-evolution.h"
86 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
87 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
88 static sreal real_almost_one
, real_br_prob_base
,
89 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
91 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
92 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
93 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
94 static void predict_paths_leading_to_edge (edge
, enum br_predictor
, enum prediction
);
95 static bool can_predict_insn_p (const rtx_insn
*);
97 /* Information we hold about each branch predictor.
98 Filled using information from predict.def. */
100 struct predictor_info
102 const char *const name
; /* Name used in the debugging dumps. */
103 const int hitrate
; /* Expected hitrate used by
104 predict_insn_def call. */
108 /* Use given predictor without Dempster-Shaffer theory if it matches
109 using first_match heuristics. */
110 #define PRED_FLAG_FIRST_MATCH 1
112 /* Recompute hitrate in percent to our representation. */
114 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
116 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
117 static const struct predictor_info predictor_info
[]= {
118 #include "predict.def"
120 /* Upper bound on predictors. */
125 /* Return TRUE if frequency FREQ is considered to be hot. */
128 maybe_hot_frequency_p (struct function
*fun
, int freq
)
130 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
132 || !opt_for_fn (fun
->decl
, flag_branch_probabilities
))
134 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
136 if (node
->frequency
== NODE_FREQUENCY_HOT
)
139 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
141 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
142 && freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
* 2 / 3))
144 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
146 if (freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
147 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
152 static gcov_type min_count
= -1;
154 /* Determine the threshold for hot BB counts. */
157 get_hot_bb_threshold ()
159 gcov_working_set_t
*ws
;
162 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
164 min_count
= ws
->min_counter
;
169 /* Set the threshold for hot BB counts. */
172 set_hot_bb_threshold (gcov_type min
)
177 /* Return TRUE if frequency FREQ is considered to be hot. */
180 maybe_hot_count_p (struct function
*fun
, gcov_type count
)
182 if (fun
&& profile_status_for_fn (fun
) != PROFILE_READ
)
184 /* Code executed at most once is not hot. */
185 if (profile_info
->runs
>= count
)
187 return (count
>= get_hot_bb_threshold ());
190 /* Return true in case BB can be CPU intensive and should be optimized
191 for maximal performance. */
194 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
196 gcc_checking_assert (fun
);
197 if (profile_status_for_fn (fun
) == PROFILE_READ
)
198 return maybe_hot_count_p (fun
, bb
->count
);
199 return maybe_hot_frequency_p (fun
, bb
->frequency
);
202 /* Return true in case BB can be CPU intensive and should be optimized
203 for maximal performance. */
206 maybe_hot_edge_p (edge e
)
208 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
209 return maybe_hot_count_p (cfun
, e
->count
);
210 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
213 /* Return true if profile COUNT and FREQUENCY, or function FUN static
214 node frequency reflects never being executed. */
217 probably_never_executed (struct function
*fun
,
218 gcov_type count
, int frequency
)
220 gcc_checking_assert (fun
);
221 if (profile_status_for_fn (fun
) == PROFILE_READ
)
223 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
224 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
228 if (!ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
230 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
232 gcov_type computed_count
;
233 /* Check for possibility of overflow, in which case entry bb count
234 is large enough to do the division first without losing much
236 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
< REG_BR_PROB_BASE
*
239 gcov_type scaled_count
240 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
*
241 unlikely_count_fraction
;
242 computed_count
= RDIV (scaled_count
,
243 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
247 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
,
248 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
249 computed_count
*= frequency
* unlikely_count_fraction
;
251 if (computed_count
>= profile_info
->runs
)
256 if ((!profile_info
|| !(opt_for_fn (fun
->decl
, flag_branch_probabilities
)))
257 && (cgraph_node::get (fun
->decl
)->frequency
258 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
264 /* Return true in case BB is probably never executed. */
267 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
269 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
273 /* Return true in case edge E is probably never executed. */
276 probably_never_executed_edge_p (struct function
*fun
, edge e
)
278 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
281 /* Return true when current function should always be optimized for size. */
284 optimize_function_for_size_p (struct function
*fun
)
286 if (!fun
|| !fun
->decl
)
287 return optimize_size
;
288 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
289 return n
&& n
->optimize_for_size_p ();
292 /* Return true when current function should always be optimized for speed. */
295 optimize_function_for_speed_p (struct function
*fun
)
297 return !optimize_function_for_size_p (fun
);
300 /* Return TRUE when BB should be optimized for size. */
303 optimize_bb_for_size_p (const_basic_block bb
)
305 return (optimize_function_for_size_p (cfun
)
306 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
309 /* Return TRUE when BB should be optimized for speed. */
312 optimize_bb_for_speed_p (const_basic_block bb
)
314 return !optimize_bb_for_size_p (bb
);
317 /* Return TRUE when BB should be optimized for size. */
320 optimize_edge_for_size_p (edge e
)
322 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
325 /* Return TRUE when BB should be optimized for speed. */
328 optimize_edge_for_speed_p (edge e
)
330 return !optimize_edge_for_size_p (e
);
333 /* Return TRUE when BB should be optimized for size. */
336 optimize_insn_for_size_p (void)
338 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
341 /* Return TRUE when BB should be optimized for speed. */
344 optimize_insn_for_speed_p (void)
346 return !optimize_insn_for_size_p ();
349 /* Return TRUE when LOOP should be optimized for size. */
352 optimize_loop_for_size_p (struct loop
*loop
)
354 return optimize_bb_for_size_p (loop
->header
);
357 /* Return TRUE when LOOP should be optimized for speed. */
360 optimize_loop_for_speed_p (struct loop
*loop
)
362 return optimize_bb_for_speed_p (loop
->header
);
365 /* Return TRUE when LOOP nest should be optimized for speed. */
368 optimize_loop_nest_for_speed_p (struct loop
*loop
)
370 struct loop
*l
= loop
;
371 if (optimize_loop_for_speed_p (loop
))
374 while (l
&& l
!= loop
)
376 if (optimize_loop_for_speed_p (l
))
384 while (l
!= loop
&& !l
->next
)
393 /* Return TRUE when LOOP nest should be optimized for size. */
396 optimize_loop_nest_for_size_p (struct loop
*loop
)
398 return !optimize_loop_nest_for_speed_p (loop
);
401 /* Return true when edge E is likely to be well predictable by branch
405 predictable_edge_p (edge e
)
407 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
410 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
411 || (REG_BR_PROB_BASE
- e
->probability
412 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
418 /* Set RTL expansion for BB profile. */
421 rtl_profile_for_bb (basic_block bb
)
423 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
426 /* Set RTL expansion for edge profile. */
429 rtl_profile_for_edge (edge e
)
431 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
434 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
436 default_rtl_profile (void)
438 crtl
->maybe_hot_insn_p
= true;
441 /* Return true if the one of outgoing edges is already predicted by
445 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
448 if (!INSN_P (BB_END (bb
)))
450 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
451 if (REG_NOTE_KIND (note
) == REG_BR_PRED
452 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
457 /* Structure representing predictions in tree level. */
459 struct edge_prediction
{
460 struct edge_prediction
*ep_next
;
462 enum br_predictor ep_predictor
;
466 /* This map contains for a basic block the list of predictions for the
469 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
471 /* Return true if the one of outgoing edges is already predicted by
475 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
477 struct edge_prediction
*i
;
478 edge_prediction
**preds
= bb_predictions
->get (bb
);
483 for (i
= *preds
; i
; i
= i
->ep_next
)
484 if (i
->ep_predictor
== predictor
)
489 /* Return true when the probability of edge is reliable.
491 The profile guessing code is good at predicting branch outcome (ie.
492 taken/not taken), that is predicted right slightly over 75% of time.
493 It is however notoriously poor on predicting the probability itself.
494 In general the profile appear a lot flatter (with probabilities closer
495 to 50%) than the reality so it is bad idea to use it to drive optimization
496 such as those disabling dynamic branch prediction for well predictable
499 There are two exceptions - edges leading to noreturn edges and edges
500 predicted by number of iterations heuristics are predicted well. This macro
501 should be able to distinguish those, but at the moment it simply check for
502 noreturn heuristic that is only one giving probability over 99% or bellow
503 1%. In future we might want to propagate reliability information across the
504 CFG if we find this information useful on multiple places. */
506 probability_reliable_p (int prob
)
508 return (profile_status_for_fn (cfun
) == PROFILE_READ
509 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
510 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
513 /* Same predicate as above, working on edges. */
515 edge_probability_reliable_p (const_edge e
)
517 return probability_reliable_p (e
->probability
);
520 /* Same predicate as edge_probability_reliable_p, working on notes. */
522 br_prob_note_reliable_p (const_rtx note
)
524 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
525 return probability_reliable_p (XINT (note
, 0));
529 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
531 gcc_assert (any_condjump_p (insn
));
532 if (!flag_guess_branch_prob
)
535 add_reg_note (insn
, REG_BR_PRED
,
536 gen_rtx_CONCAT (VOIDmode
,
537 GEN_INT ((int) predictor
),
538 GEN_INT ((int) probability
)));
541 /* Predict insn by given predictor. */
544 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
545 enum prediction taken
)
547 int probability
= predictor_info
[(int) predictor
].hitrate
;
550 probability
= REG_BR_PROB_BASE
- probability
;
552 predict_insn (insn
, predictor
, probability
);
555 /* Predict edge E with given probability if possible. */
558 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
561 last_insn
= BB_END (e
->src
);
563 /* We can store the branch prediction information only about
564 conditional jumps. */
565 if (!any_condjump_p (last_insn
))
568 /* We always store probability of branching. */
569 if (e
->flags
& EDGE_FALLTHRU
)
570 probability
= REG_BR_PROB_BASE
- probability
;
572 predict_insn (last_insn
, predictor
, probability
);
575 /* Predict edge E with the given PROBABILITY. */
577 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
579 gcc_assert (profile_status_for_fn (cfun
) != PROFILE_GUESSED
);
580 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && EDGE_COUNT (e
->src
->succs
) >
582 && flag_guess_branch_prob
&& optimize
)
584 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
585 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
589 i
->ep_probability
= probability
;
590 i
->ep_predictor
= predictor
;
595 /* Remove all predictions on given basic block that are attached
598 remove_predictions_associated_with_edge (edge e
)
603 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
607 struct edge_prediction
**prediction
= preds
;
608 struct edge_prediction
*next
;
612 if ((*prediction
)->ep_edge
== e
)
614 next
= (*prediction
)->ep_next
;
619 prediction
= &((*prediction
)->ep_next
);
624 /* Clears the list of predictions stored for BB. */
627 clear_bb_predictions (basic_block bb
)
629 edge_prediction
**preds
= bb_predictions
->get (bb
);
630 struct edge_prediction
*pred
, *next
;
635 for (pred
= *preds
; pred
; pred
= next
)
637 next
= pred
->ep_next
;
643 /* Return true when we can store prediction on insn INSN.
644 At the moment we represent predictions only on conditional
645 jumps, not at computed jump or other complicated cases. */
647 can_predict_insn_p (const rtx_insn
*insn
)
649 return (JUMP_P (insn
)
650 && any_condjump_p (insn
)
651 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
654 /* Predict edge E by given predictor if possible. */
657 predict_edge_def (edge e
, enum br_predictor predictor
,
658 enum prediction taken
)
660 int probability
= predictor_info
[(int) predictor
].hitrate
;
663 probability
= REG_BR_PROB_BASE
- probability
;
665 predict_edge (e
, predictor
, probability
);
668 /* Invert all branch predictions or probability notes in the INSN. This needs
669 to be done each time we invert the condition used by the jump. */
672 invert_br_probabilities (rtx insn
)
676 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
677 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
678 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
679 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
680 XEXP (XEXP (note
, 0), 1)
681 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
684 /* Dump information about the branch prediction to the output file. */
687 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
688 basic_block bb
, int used
)
696 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
697 if (! (e
->flags
& EDGE_FALLTHRU
))
700 fprintf (file
, " %s heuristics%s: %.1f%%",
701 predictor_info
[predictor
].name
,
702 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
706 fprintf (file
, " exec %" PRId64
, bb
->count
);
709 fprintf (file
, " hit %" PRId64
, e
->count
);
710 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
714 fprintf (file
, "\n");
717 /* We can not predict the probabilities of outgoing edges of bb. Set them
718 evenly and hope for the best. */
720 set_even_probabilities (basic_block bb
)
726 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
727 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
729 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
730 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
731 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
736 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
737 note if not already present. Remove now useless REG_BR_PRED notes. */
740 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
745 int best_probability
= PROB_EVEN
;
746 enum br_predictor best_predictor
= END_PREDICTORS
;
747 int combined_probability
= REG_BR_PROB_BASE
/ 2;
749 bool first_match
= false;
752 if (!can_predict_insn_p (insn
))
754 set_even_probabilities (bb
);
758 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
759 pnote
= ®_NOTES (insn
);
761 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
764 /* We implement "first match" heuristics and use probability guessed
765 by predictor with smallest index. */
766 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
767 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
769 enum br_predictor predictor
= ((enum br_predictor
)
770 INTVAL (XEXP (XEXP (note
, 0), 0)));
771 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
774 if (best_predictor
> predictor
)
775 best_probability
= probability
, best_predictor
= predictor
;
777 d
= (combined_probability
* probability
778 + (REG_BR_PROB_BASE
- combined_probability
)
779 * (REG_BR_PROB_BASE
- probability
));
781 /* Use FP math to avoid overflows of 32bit integers. */
783 /* If one probability is 0% and one 100%, avoid division by zero. */
784 combined_probability
= REG_BR_PROB_BASE
/ 2;
786 combined_probability
= (((double) combined_probability
) * probability
787 * REG_BR_PROB_BASE
/ d
+ 0.5);
790 /* Decide which heuristic to use. In case we didn't match anything,
791 use no_prediction heuristic, in case we did match, use either
792 first match or Dempster-Shaffer theory depending on the flags. */
794 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
798 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
799 combined_probability
, bb
, true);
802 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
804 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
809 combined_probability
= best_probability
;
810 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
814 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
816 enum br_predictor predictor
= ((enum br_predictor
)
817 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
818 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
820 dump_prediction (dump_file
, predictor
, probability
, bb
,
821 !first_match
|| best_predictor
== predictor
);
822 *pnote
= XEXP (*pnote
, 1);
825 pnote
= &XEXP (*pnote
, 1);
830 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
832 /* Save the prediction into CFG in case we are seeing non-degenerated
834 if (!single_succ_p (bb
))
836 BRANCH_EDGE (bb
)->probability
= combined_probability
;
837 FALLTHRU_EDGE (bb
)->probability
838 = REG_BR_PROB_BASE
- combined_probability
;
841 else if (!single_succ_p (bb
))
843 int prob
= XINT (prob_note
, 0);
845 BRANCH_EDGE (bb
)->probability
= prob
;
846 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
849 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
852 /* Combine predictions into single probability and store them into CFG.
853 Remove now useless prediction entries. */
856 combine_predictions_for_bb (basic_block bb
)
858 int best_probability
= PROB_EVEN
;
859 enum br_predictor best_predictor
= END_PREDICTORS
;
860 int combined_probability
= REG_BR_PROB_BASE
/ 2;
862 bool first_match
= false;
864 struct edge_prediction
*pred
;
866 edge e
, first
= NULL
, second
= NULL
;
869 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
870 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
873 if (first
&& !second
)
879 /* When there is no successor or only one choice, prediction is easy.
881 We are lazy for now and predict only basic blocks with two outgoing
882 edges. It is possible to predict generic case too, but we have to
883 ignore first match heuristics and do more involved combining. Implement
888 set_even_probabilities (bb
);
889 clear_bb_predictions (bb
);
891 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
897 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
899 edge_prediction
**preds
= bb_predictions
->get (bb
);
902 /* We implement "first match" heuristics and use probability guessed
903 by predictor with smallest index. */
904 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
906 enum br_predictor predictor
= pred
->ep_predictor
;
907 int probability
= pred
->ep_probability
;
909 if (pred
->ep_edge
!= first
)
910 probability
= REG_BR_PROB_BASE
- probability
;
913 /* First match heuristics would be widly confused if we predicted
915 if (best_predictor
> predictor
)
917 struct edge_prediction
*pred2
;
918 int prob
= probability
;
920 for (pred2
= (struct edge_prediction
*) *preds
;
921 pred2
; pred2
= pred2
->ep_next
)
922 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
924 int probability2
= pred
->ep_probability
;
926 if (pred2
->ep_edge
!= first
)
927 probability2
= REG_BR_PROB_BASE
- probability2
;
929 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
930 (probability2
< REG_BR_PROB_BASE
/ 2))
933 /* If the same predictor later gave better result, go for it! */
934 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
935 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
939 best_probability
= prob
, best_predictor
= predictor
;
942 d
= (combined_probability
* probability
943 + (REG_BR_PROB_BASE
- combined_probability
)
944 * (REG_BR_PROB_BASE
- probability
));
946 /* Use FP math to avoid overflows of 32bit integers. */
948 /* If one probability is 0% and one 100%, avoid division by zero. */
949 combined_probability
= REG_BR_PROB_BASE
/ 2;
951 combined_probability
= (((double) combined_probability
)
953 * REG_BR_PROB_BASE
/ d
+ 0.5);
957 /* Decide which heuristic to use. In case we didn't match anything,
958 use no_prediction heuristic, in case we did match, use either
959 first match or Dempster-Shaffer theory depending on the flags. */
961 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
965 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
968 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
970 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
975 combined_probability
= best_probability
;
976 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
980 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
982 enum br_predictor predictor
= pred
->ep_predictor
;
983 int probability
= pred
->ep_probability
;
985 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
986 probability
= REG_BR_PROB_BASE
- probability
;
987 dump_prediction (dump_file
, predictor
, probability
, bb
,
988 !first_match
|| best_predictor
== predictor
);
991 clear_bb_predictions (bb
);
995 first
->probability
= combined_probability
;
996 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1000 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1001 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1003 T1 and T2 should be one of the following cases:
1004 1. T1 is SSA_NAME, T2 is NULL
1005 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1006 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1009 strips_small_constant (tree t1
, tree t2
)
1016 else if (TREE_CODE (t1
) == SSA_NAME
)
1018 else if (tree_fits_shwi_p (t1
))
1019 value
= tree_to_shwi (t1
);
1025 else if (tree_fits_shwi_p (t2
))
1026 value
= tree_to_shwi (t2
);
1027 else if (TREE_CODE (t2
) == SSA_NAME
)
1035 if (value
<= 4 && value
>= -4)
1041 /* Return the SSA_NAME in T or T's operands.
1042 Return NULL if SSA_NAME cannot be found. */
1045 get_base_value (tree t
)
1047 if (TREE_CODE (t
) == SSA_NAME
)
1050 if (!BINARY_CLASS_P (t
))
1053 switch (TREE_OPERAND_LENGTH (t
))
1056 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1058 return strips_small_constant (TREE_OPERAND (t
, 0),
1059 TREE_OPERAND (t
, 1));
1065 /* Check the compare STMT in LOOP. If it compares an induction
1066 variable to a loop invariant, return true, and save
1067 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1068 Otherwise return false and set LOOP_INVAIANT to NULL. */
1071 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1072 tree
*loop_invariant
,
1073 enum tree_code
*compare_code
,
1077 tree op0
, op1
, bound
, base
;
1079 enum tree_code code
;
1082 code
= gimple_cond_code (stmt
);
1083 *loop_invariant
= NULL
;
1099 op0
= gimple_cond_lhs (stmt
);
1100 op1
= gimple_cond_rhs (stmt
);
1102 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1103 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1105 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1107 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1109 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1110 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1112 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1113 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1116 if (integer_zerop (iv0
.step
))
1118 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1119 code
= invert_tree_comparison (code
, false);
1122 if (tree_fits_shwi_p (iv1
.step
))
1131 if (tree_fits_shwi_p (iv0
.step
))
1137 if (TREE_CODE (bound
) != INTEGER_CST
)
1138 bound
= get_base_value (bound
);
1141 if (TREE_CODE (base
) != INTEGER_CST
)
1142 base
= get_base_value (base
);
1146 *loop_invariant
= bound
;
1147 *compare_code
= code
;
1149 *loop_iv_base
= base
;
1153 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1156 expr_coherent_p (tree t1
, tree t2
)
1159 tree ssa_name_1
= NULL
;
1160 tree ssa_name_2
= NULL
;
1162 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1163 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1168 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1170 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1173 /* Check to see if t1 is expressed/defined with t2. */
1174 stmt
= SSA_NAME_DEF_STMT (t1
);
1175 gcc_assert (stmt
!= NULL
);
1176 if (is_gimple_assign (stmt
))
1178 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1179 if (ssa_name_1
&& ssa_name_1
== t2
)
1183 /* Check to see if t2 is expressed/defined with t1. */
1184 stmt
= SSA_NAME_DEF_STMT (t2
);
1185 gcc_assert (stmt
!= NULL
);
1186 if (is_gimple_assign (stmt
))
1188 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1189 if (ssa_name_2
&& ssa_name_2
== t1
)
1193 /* Compare if t1 and t2's def_stmts are identical. */
1194 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1200 /* Predict branch probability of BB when BB contains a branch that compares
1201 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1202 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1205 for (int i = 0; i < bound; i++) {
1212 In this loop, we will predict the branch inside the loop to be taken. */
1215 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1216 tree loop_bound_var
,
1217 tree loop_iv_base_var
,
1218 enum tree_code loop_bound_code
,
1219 int loop_bound_step
)
1222 tree compare_var
, compare_base
;
1223 enum tree_code compare_code
;
1224 tree compare_step_var
;
1228 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1229 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1230 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1233 stmt
= last_stmt (bb
);
1234 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1236 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1243 /* Find the taken edge. */
1244 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1245 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1248 /* When comparing an IV to a loop invariant, NE is more likely to be
1249 taken while EQ is more likely to be not-taken. */
1250 if (compare_code
== NE_EXPR
)
1252 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1255 else if (compare_code
== EQ_EXPR
)
1257 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1261 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1264 /* If loop bound, base and compare bound are all constants, we can
1265 calculate the probability directly. */
1266 if (tree_fits_shwi_p (loop_bound_var
)
1267 && tree_fits_shwi_p (compare_var
)
1268 && tree_fits_shwi_p (compare_base
))
1271 bool overflow
, overall_overflow
= false;
1272 widest_int compare_count
, tem
;
1274 /* (loop_bound - base) / compare_step */
1275 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1276 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1277 overall_overflow
|= overflow
;
1278 widest_int loop_count
= wi::div_trunc (tem
,
1279 wi::to_widest (compare_step_var
),
1281 overall_overflow
|= overflow
;
1283 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1284 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1286 /* (loop_bound - compare_bound) / compare_step */
1287 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1288 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1289 overall_overflow
|= overflow
;
1290 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1292 overall_overflow
|= overflow
;
1296 /* (compare_bound - base) / compare_step */
1297 tem
= wi::sub (wi::to_widest (compare_var
),
1298 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1299 overall_overflow
|= overflow
;
1300 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1302 overall_overflow
|= overflow
;
1304 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1306 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1308 if (wi::neg_p (compare_count
))
1310 if (wi::neg_p (loop_count
))
1312 if (loop_count
== 0)
1314 else if (wi::cmps (compare_count
, loop_count
) == 1)
1315 probability
= REG_BR_PROB_BASE
;
1318 tem
= compare_count
* REG_BR_PROB_BASE
;
1319 tem
= wi::udiv_trunc (tem
, loop_count
);
1320 probability
= tem
.to_uhwi ();
1323 if (!overall_overflow
)
1324 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1329 if (expr_coherent_p (loop_bound_var
, compare_var
))
1331 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1332 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1333 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1334 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1335 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1336 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1337 else if (loop_bound_code
== NE_EXPR
)
1339 /* If the loop backedge condition is "(i != bound)", we do
1340 the comparison based on the step of IV:
1341 * step < 0 : backedge condition is like (i > bound)
1342 * step > 0 : backedge condition is like (i < bound) */
1343 gcc_assert (loop_bound_step
!= 0);
1344 if (loop_bound_step
> 0
1345 && (compare_code
== LT_EXPR
1346 || compare_code
== LE_EXPR
))
1347 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1348 else if (loop_bound_step
< 0
1349 && (compare_code
== GT_EXPR
1350 || compare_code
== GE_EXPR
))
1351 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1353 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1356 /* The branch is predicted not-taken if loop_bound_code is
1357 opposite with compare_code. */
1358 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1360 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1363 for (i = s; i < h; i++)
1365 The branch should be predicted taken. */
1366 if (loop_bound_step
> 0
1367 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1368 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1369 else if (loop_bound_step
< 0
1370 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1371 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1373 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1377 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1378 exits are resulted from short-circuit conditions that will generate an
1381 if (foo() || global > 10)
1384 This will be translated into:
1389 if foo() goto BB6 else goto BB5
1391 if global > 10 goto BB6 else goto BB7
1395 iftmp = (PHI 0(BB5), 1(BB6))
1396 if iftmp == 1 goto BB8 else goto BB3
1398 outside of the loop...
1400 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1401 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1402 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1403 exits to predict them using PRED_LOOP_EXIT. */
1406 predict_extra_loop_exits (edge exit_edge
)
1409 bool check_value_one
;
1410 gimple lhs_def_stmt
;
1412 tree cmp_rhs
, cmp_lhs
;
1416 last
= last_stmt (exit_edge
->src
);
1419 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1423 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1424 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1425 if (!TREE_CONSTANT (cmp_rhs
)
1426 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1428 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1431 /* If check_value_one is true, only the phi_args with value '1' will lead
1432 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1434 check_value_one
= (((integer_onep (cmp_rhs
))
1435 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1436 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1438 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1442 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1446 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1450 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1451 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1453 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1455 if ((check_value_one
^ integer_onep (val
)) == 1)
1457 if (EDGE_COUNT (e
->src
->succs
) != 1)
1459 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1463 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1464 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1468 /* Predict edge probabilities by exploiting loop structure. */
1471 predict_loops (void)
1475 /* Try to predict out blocks in a loop that are not part of a
1477 FOR_EACH_LOOP (loop
, 0)
1479 basic_block bb
, *bbs
;
1480 unsigned j
, n_exits
;
1482 struct tree_niter_desc niter_desc
;
1484 struct nb_iter_bound
*nb_iter
;
1485 enum tree_code loop_bound_code
= ERROR_MARK
;
1486 tree loop_bound_step
= NULL
;
1487 tree loop_bound_var
= NULL
;
1488 tree loop_iv_base
= NULL
;
1491 exits
= get_loop_exit_edges (loop
);
1492 n_exits
= exits
.length ();
1499 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1502 HOST_WIDE_INT nitercst
;
1503 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1505 enum br_predictor predictor
;
1507 predict_extra_loop_exits (ex
);
1509 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1510 niter
= niter_desc
.niter
;
1511 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1512 niter
= loop_niter_by_eval (loop
, ex
);
1514 if (TREE_CODE (niter
) == INTEGER_CST
)
1516 if (tree_fits_uhwi_p (niter
)
1518 && compare_tree_int (niter
, max
- 1) == -1)
1519 nitercst
= tree_to_uhwi (niter
) + 1;
1522 predictor
= PRED_LOOP_ITERATIONS
;
1524 /* If we have just one exit and we can derive some information about
1525 the number of iterations of the loop from the statements inside
1526 the loop, use it to predict this exit. */
1527 else if (n_exits
== 1)
1529 nitercst
= estimated_stmt_executions_int (loop
);
1535 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1540 /* If the prediction for number of iterations is zero, do not
1541 predict the exit edges. */
1545 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1546 predict_edge (ex
, predictor
, probability
);
1550 /* Find information about loop bound variables. */
1551 for (nb_iter
= loop
->bounds
; nb_iter
;
1552 nb_iter
= nb_iter
->next
)
1554 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1556 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1559 if (!stmt
&& last_stmt (loop
->header
)
1560 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1561 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1563 is_comparison_with_loop_invariant_p (stmt
, loop
,
1569 bbs
= get_loop_body (loop
);
1571 for (j
= 0; j
< loop
->num_nodes
; j
++)
1573 int header_found
= 0;
1579 /* Bypass loop heuristics on continue statement. These
1580 statements construct loops via "non-loop" constructs
1581 in the source language and are better to be handled
1583 if (predicted_by_p (bb
, PRED_CONTINUE
))
1586 /* Loop branch heuristics - predict an edge back to a
1587 loop's head as taken. */
1588 if (bb
== loop
->latch
)
1590 e
= find_edge (loop
->latch
, loop
->header
);
1594 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1598 /* Loop exit heuristics - predict an edge exiting the loop if the
1599 conditional has no loop header successors as not taken. */
1601 /* If we already used more reliable loop exit predictors, do not
1602 bother with PRED_LOOP_EXIT. */
1603 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1604 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1606 /* For loop with many exits we don't want to predict all exits
1607 with the pretty large probability, because if all exits are
1608 considered in row, the loop would be predicted to iterate
1609 almost never. The code to divide probability by number of
1610 exits is very rough. It should compute the number of exits
1611 taken in each patch through function (not the overall number
1612 of exits that might be a lot higher for loops with wide switch
1613 statements in them) and compute n-th square root.
1615 We limit the minimal probability by 2% to avoid
1616 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1617 as this was causing regression in perl benchmark containing such
1620 int probability
= ((REG_BR_PROB_BASE
1621 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1623 if (probability
< HITRATE (2))
1624 probability
= HITRATE (2);
1625 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1626 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1627 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1628 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1631 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1633 tree_to_shwi (loop_bound_step
));
1636 /* Free basic blocks from get_loop_body. */
1641 /* Attempt to predict probabilities of BB outgoing edges using local
1644 bb_estimate_probability_locally (basic_block bb
)
1646 rtx_insn
*last_insn
= BB_END (bb
);
1649 if (! can_predict_insn_p (last_insn
))
1651 cond
= get_condition (last_insn
, NULL
, false, false);
1655 /* Try "pointer heuristic."
1656 A comparison ptr == 0 is predicted as false.
1657 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1658 if (COMPARISON_P (cond
)
1659 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1660 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1662 if (GET_CODE (cond
) == EQ
)
1663 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1664 else if (GET_CODE (cond
) == NE
)
1665 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1669 /* Try "opcode heuristic."
1670 EQ tests are usually false and NE tests are usually true. Also,
1671 most quantities are positive, so we can make the appropriate guesses
1672 about signed comparisons against zero. */
1673 switch (GET_CODE (cond
))
1676 /* Unconditional branch. */
1677 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1678 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1683 /* Floating point comparisons appears to behave in a very
1684 unpredictable way because of special role of = tests in
1686 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1688 /* Comparisons with 0 are often used for booleans and there is
1689 nothing useful to predict about them. */
1690 else if (XEXP (cond
, 1) == const0_rtx
1691 || XEXP (cond
, 0) == const0_rtx
)
1694 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1699 /* Floating point comparisons appears to behave in a very
1700 unpredictable way because of special role of = tests in
1702 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1704 /* Comparisons with 0 are often used for booleans and there is
1705 nothing useful to predict about them. */
1706 else if (XEXP (cond
, 1) == const0_rtx
1707 || XEXP (cond
, 0) == const0_rtx
)
1710 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1714 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1718 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1723 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1724 || XEXP (cond
, 1) == constm1_rtx
)
1725 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1730 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1731 || XEXP (cond
, 1) == constm1_rtx
)
1732 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1740 /* Set edge->probability for each successor edge of BB. */
1742 guess_outgoing_edge_probabilities (basic_block bb
)
1744 bb_estimate_probability_locally (bb
);
1745 combine_predictions_for_insn (BB_END (bb
), bb
);
1748 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
1750 /* Helper function for expr_expected_value. */
1753 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1754 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
1759 *predictor
= PRED_UNCONDITIONAL
;
1761 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1763 if (TREE_CONSTANT (op0
))
1766 if (code
!= SSA_NAME
)
1769 def
= SSA_NAME_DEF_STMT (op0
);
1771 /* If we were already here, break the infinite cycle. */
1772 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1775 if (gimple_code (def
) == GIMPLE_PHI
)
1777 /* All the arguments of the PHI node must have the same constant
1779 int i
, n
= gimple_phi_num_args (def
);
1780 tree val
= NULL
, new_val
;
1782 for (i
= 0; i
< n
; i
++)
1784 tree arg
= PHI_ARG_DEF (def
, i
);
1785 enum br_predictor predictor2
;
1787 /* If this PHI has itself as an argument, we cannot
1788 determine the string length of this argument. However,
1789 if we can find an expected constant value for the other
1790 PHI args then we can still be sure that this is
1791 likely a constant. So be optimistic and just
1792 continue with the next argument. */
1793 if (arg
== PHI_RESULT (def
))
1796 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
1798 /* It is difficult to combine value predictors. Simply assume
1799 that later predictor is weaker and take its prediction. */
1800 if (predictor
&& *predictor
< predictor2
)
1801 *predictor
= predictor2
;
1806 else if (!operand_equal_p (val
, new_val
, false))
1811 if (is_gimple_assign (def
))
1813 if (gimple_assign_lhs (def
) != op0
)
1816 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1817 gimple_assign_rhs1 (def
),
1818 gimple_assign_rhs_code (def
),
1819 gimple_assign_rhs2 (def
),
1820 visited
, predictor
);
1823 if (is_gimple_call (def
))
1825 tree decl
= gimple_call_fndecl (def
);
1828 if (gimple_call_internal_p (def
)
1829 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
1831 gcc_assert (gimple_call_num_args (def
) == 3);
1832 tree val
= gimple_call_arg (def
, 0);
1833 if (TREE_CONSTANT (val
))
1837 tree val2
= gimple_call_arg (def
, 2);
1838 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
1839 && tree_fits_uhwi_p (val2
)
1840 && tree_to_uhwi (val2
) < END_PREDICTORS
);
1841 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
1843 return gimple_call_arg (def
, 1);
1847 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1848 switch (DECL_FUNCTION_CODE (decl
))
1850 case BUILT_IN_EXPECT
:
1853 if (gimple_call_num_args (def
) != 2)
1855 val
= gimple_call_arg (def
, 0);
1856 if (TREE_CONSTANT (val
))
1859 *predictor
= PRED_BUILTIN_EXPECT
;
1860 return gimple_call_arg (def
, 1);
1863 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1864 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1865 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1866 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1867 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1868 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1869 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1870 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1871 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1872 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1873 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1874 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1875 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1876 /* Assume that any given atomic operation has low contention,
1877 and thus the compare-and-swap operation succeeds. */
1879 *predictor
= PRED_COMPARE_AND_SWAP
;
1880 return boolean_true_node
;
1889 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1892 enum br_predictor predictor2
;
1893 op0
= expr_expected_value (op0
, visited
, predictor
);
1896 op1
= expr_expected_value (op1
, visited
, &predictor2
);
1897 if (predictor
&& *predictor
< predictor2
)
1898 *predictor
= predictor2
;
1901 res
= fold_build2 (code
, type
, op0
, op1
);
1902 if (TREE_CONSTANT (res
))
1906 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1909 op0
= expr_expected_value (op0
, visited
, predictor
);
1912 res
= fold_build1 (code
, type
, op0
);
1913 if (TREE_CONSTANT (res
))
1920 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1921 The function is used by builtin_expect branch predictor so the evidence
1922 must come from this construct and additional possible constant folding.
1924 We may want to implement more involved value guess (such as value range
1925 propagation based prediction), but such tricks shall go to new
1929 expr_expected_value (tree expr
, bitmap visited
,
1930 enum br_predictor
*predictor
)
1932 enum tree_code code
;
1935 if (TREE_CONSTANT (expr
))
1938 *predictor
= PRED_UNCONDITIONAL
;
1942 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1943 return expr_expected_value_1 (TREE_TYPE (expr
),
1944 op0
, code
, op1
, visited
, predictor
);
1947 /* Predict using opcode of the last statement in basic block. */
1949 tree_predict_by_opcode (basic_block bb
)
1951 gimple stmt
= last_stmt (bb
);
1959 enum br_predictor predictor
;
1961 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1963 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1964 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1966 op0
= gimple_cond_lhs (stmt
);
1967 op1
= gimple_cond_rhs (stmt
);
1968 cmp
= gimple_cond_code (stmt
);
1969 type
= TREE_TYPE (op0
);
1970 visited
= BITMAP_ALLOC (NULL
);
1971 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
1973 BITMAP_FREE (visited
);
1974 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
1976 if (predictor
== PRED_BUILTIN_EXPECT
)
1978 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
1980 gcc_assert (percent
>= 0 && percent
<= 100);
1981 if (integer_zerop (val
))
1982 percent
= 100 - percent
;
1983 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
1986 predict_edge (then_edge
, predictor
,
1987 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
1989 /* Try "pointer heuristic."
1990 A comparison ptr == 0 is predicted as false.
1991 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1992 if (POINTER_TYPE_P (type
))
1995 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1996 else if (cmp
== NE_EXPR
)
1997 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2001 /* Try "opcode heuristic."
2002 EQ tests are usually false and NE tests are usually true. Also,
2003 most quantities are positive, so we can make the appropriate guesses
2004 about signed comparisons against zero. */
2009 /* Floating point comparisons appears to behave in a very
2010 unpredictable way because of special role of = tests in
2012 if (FLOAT_TYPE_P (type
))
2014 /* Comparisons with 0 are often used for booleans and there is
2015 nothing useful to predict about them. */
2016 else if (integer_zerop (op0
) || integer_zerop (op1
))
2019 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2024 /* Floating point comparisons appears to behave in a very
2025 unpredictable way because of special role of = tests in
2027 if (FLOAT_TYPE_P (type
))
2029 /* Comparisons with 0 are often used for booleans and there is
2030 nothing useful to predict about them. */
2031 else if (integer_zerop (op0
)
2032 || integer_zerop (op1
))
2035 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2039 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2042 case UNORDERED_EXPR
:
2043 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2048 if (integer_zerop (op1
)
2049 || integer_onep (op1
)
2050 || integer_all_onesp (op1
)
2053 || real_minus_onep (op1
))
2054 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2059 if (integer_zerop (op1
)
2060 || integer_onep (op1
)
2061 || integer_all_onesp (op1
)
2064 || real_minus_onep (op1
))
2065 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2073 /* Try to guess whether the value of return means error code. */
2075 static enum br_predictor
2076 return_prediction (tree val
, enum prediction
*prediction
)
2080 return PRED_NO_PREDICTION
;
2081 /* Different heuristics for pointers and scalars. */
2082 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2084 /* NULL is usually not returned. */
2085 if (integer_zerop (val
))
2087 *prediction
= NOT_TAKEN
;
2088 return PRED_NULL_RETURN
;
2091 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2093 /* Negative return values are often used to indicate
2095 if (TREE_CODE (val
) == INTEGER_CST
2096 && tree_int_cst_sgn (val
) < 0)
2098 *prediction
= NOT_TAKEN
;
2099 return PRED_NEGATIVE_RETURN
;
2101 /* Constant return values seems to be commonly taken.
2102 Zero/one often represent booleans so exclude them from the
2104 if (TREE_CONSTANT (val
)
2105 && (!integer_zerop (val
) && !integer_onep (val
)))
2107 *prediction
= TAKEN
;
2108 return PRED_CONST_RETURN
;
2111 return PRED_NO_PREDICTION
;
2114 /* Find the basic block with return expression and look up for possible
2115 return value trying to apply RETURN_PREDICTION heuristics. */
2117 apply_return_prediction (void)
2119 greturn
*return_stmt
= NULL
;
2123 int phi_num_args
, i
;
2124 enum br_predictor pred
;
2125 enum prediction direction
;
2128 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2130 gimple last
= last_stmt (e
->src
);
2132 && gimple_code (last
) == GIMPLE_RETURN
)
2134 return_stmt
= as_a
<greturn
*> (last
);
2140 return_val
= gimple_return_retval (return_stmt
);
2143 if (TREE_CODE (return_val
) != SSA_NAME
2144 || !SSA_NAME_DEF_STMT (return_val
)
2145 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2147 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2148 phi_num_args
= gimple_phi_num_args (phi
);
2149 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2151 /* Avoid the degenerate case where all return values form the function
2152 belongs to same category (ie they are all positive constants)
2153 so we can hardly say something about them. */
2154 for (i
= 1; i
< phi_num_args
; i
++)
2155 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2157 if (i
!= phi_num_args
)
2158 for (i
= 0; i
< phi_num_args
; i
++)
2160 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2161 if (pred
!= PRED_NO_PREDICTION
)
2162 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2167 /* Look for basic block that contains unlikely to happen events
2168 (such as noreturn calls) and mark all paths leading to execution
2169 of this basic blocks as unlikely. */
2172 tree_bb_level_predictions (void)
2175 bool has_return_edges
= false;
2179 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2180 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2182 has_return_edges
= true;
2186 apply_return_prediction ();
2188 FOR_EACH_BB_FN (bb
, cfun
)
2190 gimple_stmt_iterator gsi
;
2192 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2194 gimple stmt
= gsi_stmt (gsi
);
2197 if (is_gimple_call (stmt
))
2199 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2200 && has_return_edges
)
2201 predict_paths_leading_to (bb
, PRED_NORETURN
,
2203 decl
= gimple_call_fndecl (stmt
);
2205 && lookup_attribute ("cold",
2206 DECL_ATTRIBUTES (decl
)))
2207 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2210 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2212 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2213 gimple_predict_outcome (stmt
));
2214 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2215 hints to callers. */
2221 #ifdef ENABLE_CHECKING
2223 /* Callback for hash_map::traverse, asserts that the pointer map is
2227 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2230 gcc_assert (!value
);
2235 /* Predict branch probabilities and estimate profile for basic block BB. */
2238 tree_estimate_probability_bb (basic_block bb
)
2244 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2246 /* Predict edges to user labels with attributes. */
2247 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2249 gimple_stmt_iterator gi
;
2250 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2252 glabel
*label_stmt
= dyn_cast
<glabel
*> (gsi_stmt (gi
));
2257 decl
= gimple_label_label (label_stmt
);
2258 if (DECL_ARTIFICIAL (decl
))
2261 /* Finally, we have a user-defined label. */
2262 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2263 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2264 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2265 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2269 /* Predict early returns to be probable, as we've already taken
2270 care for error returns and other cases are often used for
2271 fast paths through function.
2273 Since we've already removed the return statements, we are
2274 looking for CFG like:
2284 if (e
->dest
!= bb
->next_bb
2285 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2286 && single_succ_p (e
->dest
)
2287 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2288 && (last
= last_stmt (e
->dest
)) != NULL
2289 && gimple_code (last
) == GIMPLE_RETURN
)
2294 if (single_succ_p (bb
))
2296 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2297 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2298 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2299 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2300 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2303 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2304 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2305 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2306 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2309 /* Look for block we are guarding (ie we dominate it,
2310 but it doesn't postdominate us). */
2311 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2312 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2313 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2315 gimple_stmt_iterator bi
;
2317 /* The call heuristic claims that a guarded function call
2318 is improbable. This is because such calls are often used
2319 to signal exceptional situations such as printing error
2321 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2324 gimple stmt
= gsi_stmt (bi
);
2325 if (is_gimple_call (stmt
)
2326 /* Constant and pure calls are hardly used to signalize
2327 something exceptional. */
2328 && gimple_has_side_effects (stmt
))
2330 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2336 tree_predict_by_opcode (bb
);
2339 /* Predict branch probabilities and estimate profile of the tree CFG.
2340 This function can be called from the loop optimizers to recompute
2341 the profile information. */
2344 tree_estimate_probability (void)
2348 add_noreturn_fake_exit_edges ();
2349 connect_infinite_loops_to_exit ();
2350 /* We use loop_niter_by_eval, which requires that the loops have
2352 create_preheaders (CP_SIMPLE_PREHEADERS
);
2353 calculate_dominance_info (CDI_POST_DOMINATORS
);
2355 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2356 tree_bb_level_predictions ();
2357 record_loop_exits ();
2359 if (number_of_loops (cfun
) > 1)
2362 FOR_EACH_BB_FN (bb
, cfun
)
2363 tree_estimate_probability_bb (bb
);
2365 FOR_EACH_BB_FN (bb
, cfun
)
2366 combine_predictions_for_bb (bb
);
2368 #ifdef ENABLE_CHECKING
2369 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2371 delete bb_predictions
;
2372 bb_predictions
= NULL
;
2374 estimate_bb_frequencies (false);
2375 free_dominance_info (CDI_POST_DOMINATORS
);
2376 remove_fake_exit_edges ();
2379 /* Predict edges to successors of CUR whose sources are not postdominated by
2380 BB by PRED and recurse to all postdominators. */
2383 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2384 enum br_predictor pred
,
2385 enum prediction taken
,
2392 /* We are looking for all edges forming edge cut induced by
2393 set of all blocks postdominated by BB. */
2394 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2395 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2396 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2402 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2403 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2405 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2407 /* See if there is an edge from e->src that is not abnormal
2408 and does not lead to BB. */
2409 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2411 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2412 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2418 /* If there is non-abnormal path leaving e->src, predict edge
2419 using predictor. Otherwise we need to look for paths
2422 The second may lead to infinite loop in the case we are predicitng
2423 regions that are only reachable by abnormal edges. We simply
2424 prevent visiting given BB twice. */
2426 predict_edge_def (e
, pred
, taken
);
2427 else if (bitmap_set_bit (visited
, e
->src
->index
))
2428 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2430 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2432 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2433 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2436 /* Sets branch probabilities according to PREDiction and
2440 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2441 enum prediction taken
)
2443 bitmap visited
= BITMAP_ALLOC (NULL
);
2444 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2445 BITMAP_FREE (visited
);
2448 /* Like predict_paths_leading_to but take edge instead of basic block. */
2451 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2452 enum prediction taken
)
2454 bool has_nonloop_edge
= false;
2458 basic_block bb
= e
->src
;
2459 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2460 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2461 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2462 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2464 has_nonloop_edge
= true;
2467 if (!has_nonloop_edge
)
2469 bitmap visited
= BITMAP_ALLOC (NULL
);
2470 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2471 BITMAP_FREE (visited
);
2474 predict_edge_def (e
, pred
, taken
);
2477 /* This is used to carry information about basic blocks. It is
2478 attached to the AUX field of the standard CFG block. */
2482 /* Estimated frequency of execution of basic_block. */
2485 /* To keep queue of basic blocks to process. */
2488 /* Number of predecessors we need to visit first. */
2492 /* Similar information for edges. */
2493 struct edge_prob_info
2495 /* In case edge is a loopback edge, the probability edge will be reached
2496 in case header is. Estimated number of iterations of the loop can be
2497 then computed as 1 / (1 - back_edge_prob). */
2498 sreal back_edge_prob
;
2499 /* True if the edge is a loopback edge in the natural loop. */
2500 unsigned int back_edge
:1;
2503 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2505 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2507 /* Helper function for estimate_bb_frequencies.
2508 Propagate the frequencies in blocks marked in
2509 TOVISIT, starting in HEAD. */
2512 propagate_freq (basic_block head
, bitmap tovisit
)
2521 /* For each basic block we need to visit count number of his predecessors
2522 we need to visit first. */
2523 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2528 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2530 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2532 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2534 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2536 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2538 "Irreducible region hit, ignoring edge to %i->%i\n",
2539 e
->src
->index
, bb
->index
);
2541 BLOCK_INFO (bb
)->npredecessors
= count
;
2542 /* When function never returns, we will never process exit block. */
2543 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2544 bb
->count
= bb
->frequency
= 0;
2547 BLOCK_INFO (head
)->frequency
= 1;
2549 for (bb
= head
; bb
; bb
= nextbb
)
2552 sreal cyclic_probability
= 0;
2553 sreal frequency
= 0;
2555 nextbb
= BLOCK_INFO (bb
)->next
;
2556 BLOCK_INFO (bb
)->next
= NULL
;
2558 /* Compute frequency of basic block. */
2561 #ifdef ENABLE_CHECKING
2562 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2563 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2564 || (e
->flags
& EDGE_DFS_BACK
));
2567 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2568 if (EDGE_INFO (e
)->back_edge
)
2570 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
2572 else if (!(e
->flags
& EDGE_DFS_BACK
))
2574 /* frequency += (e->probability
2575 * BLOCK_INFO (e->src)->frequency /
2576 REG_BR_PROB_BASE); */
2578 sreal tmp
= e
->probability
;
2579 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
2580 tmp
*= real_inv_br_prob_base
;
2584 if (cyclic_probability
== 0)
2586 BLOCK_INFO (bb
)->frequency
= frequency
;
2590 if (cyclic_probability
> real_almost_one
)
2591 cyclic_probability
= real_almost_one
;
2593 /* BLOCK_INFO (bb)->frequency = frequency
2594 / (1 - cyclic_probability) */
2596 cyclic_probability
= sreal (1) - cyclic_probability
;
2597 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
2601 bitmap_clear_bit (tovisit
, bb
->index
);
2603 e
= find_edge (bb
, head
);
2606 /* EDGE_INFO (e)->back_edge_prob
2607 = ((e->probability * BLOCK_INFO (bb)->frequency)
2608 / REG_BR_PROB_BASE); */
2610 sreal tmp
= e
->probability
;
2611 tmp
*= BLOCK_INFO (bb
)->frequency
;
2612 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
2615 /* Propagate to successor blocks. */
2616 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2617 if (!(e
->flags
& EDGE_DFS_BACK
)
2618 && BLOCK_INFO (e
->dest
)->npredecessors
)
2620 BLOCK_INFO (e
->dest
)->npredecessors
--;
2621 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2626 BLOCK_INFO (last
)->next
= e
->dest
;
2634 /* Estimate frequencies in loops at same nest level. */
2637 estimate_loops_at_level (struct loop
*first_loop
)
2641 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2646 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2648 estimate_loops_at_level (loop
->inner
);
2650 /* Find current loop back edge and mark it. */
2651 e
= loop_latch_edge (loop
);
2652 EDGE_INFO (e
)->back_edge
= 1;
2654 bbs
= get_loop_body (loop
);
2655 for (i
= 0; i
< loop
->num_nodes
; i
++)
2656 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2658 propagate_freq (loop
->header
, tovisit
);
2659 BITMAP_FREE (tovisit
);
2663 /* Propagates frequencies through structure of loops. */
2666 estimate_loops (void)
2668 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2671 /* Start by estimating the frequencies in the loops. */
2672 if (number_of_loops (cfun
) > 1)
2673 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2675 /* Now propagate the frequencies through all the blocks. */
2676 FOR_ALL_BB_FN (bb
, cfun
)
2678 bitmap_set_bit (tovisit
, bb
->index
);
2680 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
2681 BITMAP_FREE (tovisit
);
2684 /* Drop the profile for NODE to guessed, and update its frequency based on
2685 whether it is expected to be hot given the CALL_COUNT. */
2688 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
2690 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2691 /* In the case where this was called by another function with a
2692 dropped profile, call_count will be 0. Since there are no
2693 non-zero call counts to this function, we don't know for sure
2694 whether it is hot, and therefore it will be marked normal below. */
2695 bool hot
= maybe_hot_count_p (NULL
, call_count
);
2699 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2700 node
->name (), node
->order
,
2701 hot
? "Function is hot" : "Function is normal");
2702 /* We only expect to miss profiles for functions that are reached
2703 via non-zero call edges in cases where the function may have
2704 been linked from another module or library (COMDATs and extern
2705 templates). See the comments below for handle_missing_profiles.
2706 Also, only warn in cases where the missing counts exceed the
2707 number of training runs. In certain cases with an execv followed
2708 by a no-return call the profile for the no-return call is not
2709 dumped and there can be a mismatch. */
2710 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
2711 && call_count
> profile_info
->runs
)
2713 if (flag_profile_correction
)
2717 "Missing counts for called function %s/%i\n",
2718 node
->name (), node
->order
);
2721 warning (0, "Missing counts for called function %s/%i",
2722 node
->name (), node
->order
);
2725 profile_status_for_fn (fn
)
2726 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2728 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2731 /* In the case of COMDAT routines, multiple object files will contain the same
2732 function and the linker will select one for the binary. In that case
2733 all the other copies from the profile instrument binary will be missing
2734 profile counts. Look for cases where this happened, due to non-zero
2735 call counts going to 0-count functions, and drop the profile to guessed
2736 so that we can use the estimated probabilities and avoid optimizing only
2739 The other case where the profile may be missing is when the routine
2740 is not going to be emitted to the object file, e.g. for "extern template"
2741 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2742 all other cases of non-zero calls to 0-count functions. */
2745 handle_missing_profiles (void)
2747 struct cgraph_node
*node
;
2748 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2749 vec
<struct cgraph_node
*> worklist
;
2750 worklist
.create (64);
2752 /* See if 0 count function has non-0 count callers. In this case we
2753 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2754 FOR_EACH_DEFINED_FUNCTION (node
)
2756 struct cgraph_edge
*e
;
2757 gcov_type call_count
= 0;
2758 gcov_type max_tp_first_run
= 0;
2759 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2763 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2765 call_count
+= e
->count
;
2767 if (e
->caller
->tp_first_run
> max_tp_first_run
)
2768 max_tp_first_run
= e
->caller
->tp_first_run
;
2771 /* If time profile is missing, let assign the maximum that comes from
2772 caller functions. */
2773 if (!node
->tp_first_run
&& max_tp_first_run
)
2774 node
->tp_first_run
= max_tp_first_run
+ 1;
2778 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2780 drop_profile (node
, call_count
);
2781 worklist
.safe_push (node
);
2785 /* Propagate the profile dropping to other 0-count COMDATs that are
2786 potentially called by COMDATs we already dropped the profile on. */
2787 while (worklist
.length () > 0)
2789 struct cgraph_edge
*e
;
2791 node
= worklist
.pop ();
2792 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2794 struct cgraph_node
*callee
= e
->callee
;
2795 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2797 if (callee
->count
> 0)
2799 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2800 && profile_status_for_fn (fn
) == PROFILE_READ
)
2802 drop_profile (node
, 0);
2803 worklist
.safe_push (callee
);
2807 worklist
.release ();
2810 /* Convert counts measured by profile driven feedback to frequencies.
2811 Return nonzero iff there was any nonzero execution count. */
2814 counts_to_freqs (void)
2816 gcov_type count_max
, true_count_max
= 0;
2819 /* Don't overwrite the estimated frequencies when the profile for
2820 the function is missing. We may drop this function PROFILE_GUESSED
2821 later in drop_profile (). */
2822 if (!flag_auto_profile
&& !ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
2825 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2826 true_count_max
= MAX (bb
->count
, true_count_max
);
2828 count_max
= MAX (true_count_max
, 1);
2829 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2830 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2832 return true_count_max
;
2835 /* Return true if function is likely to be expensive, so there is no point to
2836 optimize performance of prologue, epilogue or do inlining at the expense
2837 of code size growth. THRESHOLD is the limit of number of instructions
2838 function can execute at average to be still considered not expensive. */
2841 expensive_function_p (int threshold
)
2843 unsigned int sum
= 0;
2847 /* We can not compute accurately for large thresholds due to scaled
2849 gcc_assert (threshold
<= BB_FREQ_MAX
);
2851 /* Frequencies are out of range. This either means that function contains
2852 internal loop executing more than BB_FREQ_MAX times or profile feedback
2853 is available and function has not been executed at all. */
2854 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
2857 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2858 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
2859 FOR_EACH_BB_FN (bb
, cfun
)
2863 FOR_BB_INSNS (bb
, insn
)
2864 if (active_insn_p (insn
))
2866 sum
+= bb
->frequency
;
2875 /* Estimate and propagate basic block frequencies using the given branch
2876 probabilities. If FORCE is true, the frequencies are used to estimate
2877 the counts even when there are already non-zero profile counts. */
2880 estimate_bb_frequencies (bool force
)
2885 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
2887 static int real_values_initialized
= 0;
2889 if (!real_values_initialized
)
2891 real_values_initialized
= 1;
2892 real_br_prob_base
= REG_BR_PROB_BASE
;
2893 real_bb_freq_max
= BB_FREQ_MAX
;
2894 real_one_half
= sreal (1, -1);
2895 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
2896 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
2899 mark_dfs_back_edges ();
2901 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
2904 /* Set up block info for each basic block. */
2905 alloc_aux_for_blocks (sizeof (block_info
));
2906 alloc_aux_for_edges (sizeof (edge_prob_info
));
2907 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2912 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2914 EDGE_INFO (e
)->back_edge_prob
= e
->probability
;
2915 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
2919 /* First compute frequencies locally for each loop from innermost
2920 to outermost to examine frequencies for back edges. */
2924 FOR_EACH_BB_FN (bb
, cfun
)
2925 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
2926 freq_max
= BLOCK_INFO (bb
)->frequency
;
2928 freq_max
= real_bb_freq_max
/ freq_max
;
2929 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2931 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
2932 bb
->frequency
= tmp
.to_int ();
2935 free_aux_for_blocks ();
2936 free_aux_for_edges ();
2938 compute_function_frequency ();
2941 /* Decide whether function is hot, cold or unlikely executed. */
2943 compute_function_frequency (void)
2946 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2948 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2949 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2950 node
->only_called_at_startup
= true;
2951 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
2952 node
->only_called_at_exit
= true;
2954 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
2956 int flags
= flags_from_decl_or_type (current_function_decl
);
2957 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2959 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2960 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
2962 node
->frequency
= NODE_FREQUENCY_HOT
;
2963 else if (flags
& ECF_NORETURN
)
2964 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2965 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2966 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2967 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2968 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
2969 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2973 /* Only first time try to drop function into unlikely executed.
2974 After inlining the roundoff errors may confuse us.
2975 Ipa-profile pass will drop functions only called from unlikely
2976 functions to unlikely and that is most of what we care about. */
2977 if (!cfun
->after_inlining
)
2978 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2979 FOR_EACH_BB_FN (bb
, cfun
)
2981 if (maybe_hot_bb_p (cfun
, bb
))
2983 node
->frequency
= NODE_FREQUENCY_HOT
;
2986 if (!probably_never_executed_bb_p (cfun
, bb
))
2987 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2991 /* Build PREDICT_EXPR. */
2993 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
2995 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
2996 build_int_cst (integer_type_node
, predictor
));
2997 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3002 predictor_name (enum br_predictor predictor
)
3004 return predictor_info
[predictor
].name
;
3007 /* Predict branch probabilities and estimate profile of the tree CFG. */
3011 const pass_data pass_data_profile
=
3013 GIMPLE_PASS
, /* type */
3014 "profile_estimate", /* name */
3015 OPTGROUP_NONE
, /* optinfo_flags */
3016 TV_BRANCH_PROB
, /* tv_id */
3017 PROP_cfg
, /* properties_required */
3018 0, /* properties_provided */
3019 0, /* properties_destroyed */
3020 0, /* todo_flags_start */
3021 0, /* todo_flags_finish */
3024 class pass_profile
: public gimple_opt_pass
3027 pass_profile (gcc::context
*ctxt
)
3028 : gimple_opt_pass (pass_data_profile
, ctxt
)
3031 /* opt_pass methods: */
3032 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3033 virtual unsigned int execute (function
*);
3035 }; // class pass_profile
3038 pass_profile::execute (function
*fun
)
3042 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3045 loop_optimizer_init (LOOPS_NORMAL
);
3046 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3047 flow_loops_dump (dump_file
, NULL
, 0);
3049 mark_irreducible_loops ();
3051 nb_loops
= number_of_loops (fun
);
3055 tree_estimate_probability ();
3060 loop_optimizer_finalize ();
3061 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3062 gimple_dump_cfg (dump_file
, dump_flags
);
3063 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3064 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3071 make_pass_profile (gcc::context
*ctxt
)
3073 return new pass_profile (ctxt
);
3078 const pass_data pass_data_strip_predict_hints
=
3080 GIMPLE_PASS
, /* type */
3081 "*strip_predict_hints", /* name */
3082 OPTGROUP_NONE
, /* optinfo_flags */
3083 TV_BRANCH_PROB
, /* tv_id */
3084 PROP_cfg
, /* properties_required */
3085 0, /* properties_provided */
3086 0, /* properties_destroyed */
3087 0, /* todo_flags_start */
3088 0, /* todo_flags_finish */
3091 class pass_strip_predict_hints
: public gimple_opt_pass
3094 pass_strip_predict_hints (gcc::context
*ctxt
)
3095 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3098 /* opt_pass methods: */
3099 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3100 virtual unsigned int execute (function
*);
3102 }; // class pass_strip_predict_hints
3104 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3105 we no longer need. */
3107 pass_strip_predict_hints::execute (function
*fun
)
3113 FOR_EACH_BB_FN (bb
, fun
)
3115 gimple_stmt_iterator bi
;
3116 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3118 gimple stmt
= gsi_stmt (bi
);
3120 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3122 gsi_remove (&bi
, true);
3125 else if (is_gimple_call (stmt
))
3127 tree fndecl
= gimple_call_fndecl (stmt
);
3130 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3131 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3132 && gimple_call_num_args (stmt
) == 2)
3133 || (gimple_call_internal_p (stmt
)
3134 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3136 var
= gimple_call_lhs (stmt
);
3140 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3141 gsi_replace (&bi
, ass_stmt
, true);
3145 gsi_remove (&bi
, true);
3159 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3161 return new pass_strip_predict_hints (ctxt
);
3164 /* Rebuild function frequencies. Passes are in general expected to
3165 maintain profile by hand, however in some cases this is not possible:
3166 for example when inlining several functions with loops freuqencies might run
3167 out of scale and thus needs to be recomputed. */
3170 rebuild_frequencies (void)
3172 timevar_push (TV_REBUILD_FREQUENCIES
);
3174 /* When the max bb count in the function is small, there is a higher
3175 chance that there were truncation errors in the integer scaling
3176 of counts by inlining and other optimizations. This could lead
3177 to incorrect classification of code as being cold when it isn't.
3178 In that case, force the estimation of bb counts/frequencies from the
3179 branch probabilities, rather than computing frequencies from counts,
3180 which may also lead to frequencies incorrectly reduced to 0. There
3181 is less precision in the probabilities, so we only do this for small
3183 gcov_type count_max
= 0;
3185 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3186 count_max
= MAX (bb
->count
, count_max
);
3188 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3189 || (!flag_auto_profile
&& profile_status_for_fn (cfun
) == PROFILE_READ
3190 && count_max
< REG_BR_PROB_BASE
/10))
3192 loop_optimizer_init (0);
3193 add_noreturn_fake_exit_edges ();
3194 mark_irreducible_loops ();
3195 connect_infinite_loops_to_exit ();
3196 estimate_bb_frequencies (true);
3197 remove_fake_exit_edges ();
3198 loop_optimizer_finalize ();
3200 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3204 timevar_pop (TV_REBUILD_FREQUENCIES
);