1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2014 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 "hard-reg-set.h"
46 #include "dominance.h"
49 #include "basic-block.h"
50 #include "insn-config.h"
55 #include "diagnostic-core.h"
64 #include "tree-ssa-alias.h"
65 #include "internal-fn.h"
66 #include "gimple-expr.h"
69 #include "gimple-iterator.h"
70 #include "gimple-ssa.h"
71 #include "plugin-api.h"
75 #include "tree-phinodes.h"
76 #include "ssa-iterators.h"
77 #include "tree-ssa-loop-niter.h"
78 #include "tree-ssa-loop.h"
79 #include "tree-pass.h"
80 #include "tree-scalar-evolution.h"
83 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
84 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
85 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
86 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
88 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
89 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
90 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
91 static void predict_paths_leading_to_edge (edge
, enum br_predictor
, enum prediction
);
92 static bool can_predict_insn_p (const rtx_insn
*);
94 /* Information we hold about each branch predictor.
95 Filled using information from predict.def. */
99 const char *const name
; /* Name used in the debugging dumps. */
100 const int hitrate
; /* Expected hitrate used by
101 predict_insn_def call. */
105 /* Use given predictor without Dempster-Shaffer theory if it matches
106 using first_match heuristics. */
107 #define PRED_FLAG_FIRST_MATCH 1
109 /* Recompute hitrate in percent to our representation. */
111 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
113 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
114 static const struct predictor_info predictor_info
[]= {
115 #include "predict.def"
117 /* Upper bound on predictors. */
122 /* Return TRUE if frequency FREQ is considered to be hot. */
125 maybe_hot_frequency_p (struct function
*fun
, int freq
)
127 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
129 || !opt_for_fn (fun
->decl
, flag_branch_probabilities
))
131 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
133 if (node
->frequency
== NODE_FREQUENCY_HOT
)
136 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
138 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
139 && freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
* 2 / 3))
141 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
143 if (freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
144 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
149 static gcov_type min_count
= -1;
151 /* Determine the threshold for hot BB counts. */
154 get_hot_bb_threshold ()
156 gcov_working_set_t
*ws
;
159 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
161 min_count
= ws
->min_counter
;
166 /* Set the threshold for hot BB counts. */
169 set_hot_bb_threshold (gcov_type min
)
174 /* Return TRUE if frequency FREQ is considered to be hot. */
177 maybe_hot_count_p (struct function
*fun
, gcov_type count
)
179 if (fun
&& profile_status_for_fn (fun
) != PROFILE_READ
)
181 /* Code executed at most once is not hot. */
182 if (profile_info
->runs
>= count
)
184 return (count
>= get_hot_bb_threshold ());
187 /* Return true in case BB can be CPU intensive and should be optimized
188 for maximal performance. */
191 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
193 gcc_checking_assert (fun
);
194 if (profile_status_for_fn (fun
) == PROFILE_READ
)
195 return maybe_hot_count_p (fun
, bb
->count
);
196 return maybe_hot_frequency_p (fun
, bb
->frequency
);
199 /* Return true in case BB can be CPU intensive and should be optimized
200 for maximal performance. */
203 maybe_hot_edge_p (edge e
)
205 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
206 return maybe_hot_count_p (cfun
, e
->count
);
207 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
210 /* Return true if profile COUNT and FREQUENCY, or function FUN static
211 node frequency reflects never being executed. */
214 probably_never_executed (struct function
*fun
,
215 gcov_type count
, int frequency
)
217 gcc_checking_assert (fun
);
218 if (profile_status_for_fn (fun
) == PROFILE_READ
)
220 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
221 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
225 if (!ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
227 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
229 gcov_type computed_count
;
230 /* Check for possibility of overflow, in which case entry bb count
231 is large enough to do the division first without losing much
233 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
< REG_BR_PROB_BASE
*
236 gcov_type scaled_count
237 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
*
238 unlikely_count_fraction
;
239 computed_count
= RDIV (scaled_count
,
240 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
244 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
,
245 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
246 computed_count
*= frequency
* unlikely_count_fraction
;
248 if (computed_count
>= profile_info
->runs
)
253 if ((!profile_info
|| !(opt_for_fn (fun
->decl
, flag_branch_probabilities
)))
254 && (cgraph_node::get (fun
->decl
)->frequency
255 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
261 /* Return true in case BB is probably never executed. */
264 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
266 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
270 /* Return true in case edge E is probably never executed. */
273 probably_never_executed_edge_p (struct function
*fun
, edge e
)
275 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
278 /* Return true when current function should always be optimized for size. */
281 optimize_function_for_size_p (struct function
*fun
)
283 if (!fun
|| !fun
->decl
)
284 return optimize_size
;
285 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
286 return n
&& n
->optimize_for_size_p ();
289 /* Return true when current function should always be optimized for speed. */
292 optimize_function_for_speed_p (struct function
*fun
)
294 return !optimize_function_for_size_p (fun
);
297 /* Return TRUE when BB should be optimized for size. */
300 optimize_bb_for_size_p (const_basic_block bb
)
302 return (optimize_function_for_size_p (cfun
)
303 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
306 /* Return TRUE when BB should be optimized for speed. */
309 optimize_bb_for_speed_p (const_basic_block bb
)
311 return !optimize_bb_for_size_p (bb
);
314 /* Return TRUE when BB should be optimized for size. */
317 optimize_edge_for_size_p (edge e
)
319 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
322 /* Return TRUE when BB should be optimized for speed. */
325 optimize_edge_for_speed_p (edge e
)
327 return !optimize_edge_for_size_p (e
);
330 /* Return TRUE when BB should be optimized for size. */
333 optimize_insn_for_size_p (void)
335 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
338 /* Return TRUE when BB should be optimized for speed. */
341 optimize_insn_for_speed_p (void)
343 return !optimize_insn_for_size_p ();
346 /* Return TRUE when LOOP should be optimized for size. */
349 optimize_loop_for_size_p (struct loop
*loop
)
351 return optimize_bb_for_size_p (loop
->header
);
354 /* Return TRUE when LOOP should be optimized for speed. */
357 optimize_loop_for_speed_p (struct loop
*loop
)
359 return optimize_bb_for_speed_p (loop
->header
);
362 /* Return TRUE when LOOP nest should be optimized for speed. */
365 optimize_loop_nest_for_speed_p (struct loop
*loop
)
367 struct loop
*l
= loop
;
368 if (optimize_loop_for_speed_p (loop
))
371 while (l
&& l
!= loop
)
373 if (optimize_loop_for_speed_p (l
))
381 while (l
!= loop
&& !l
->next
)
390 /* Return TRUE when LOOP nest should be optimized for size. */
393 optimize_loop_nest_for_size_p (struct loop
*loop
)
395 return !optimize_loop_nest_for_speed_p (loop
);
398 /* Return true when edge E is likely to be well predictable by branch
402 predictable_edge_p (edge e
)
404 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
407 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
408 || (REG_BR_PROB_BASE
- e
->probability
409 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
415 /* Set RTL expansion for BB profile. */
418 rtl_profile_for_bb (basic_block bb
)
420 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
423 /* Set RTL expansion for edge profile. */
426 rtl_profile_for_edge (edge e
)
428 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
431 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
433 default_rtl_profile (void)
435 crtl
->maybe_hot_insn_p
= true;
438 /* Return true if the one of outgoing edges is already predicted by
442 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
445 if (!INSN_P (BB_END (bb
)))
447 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
448 if (REG_NOTE_KIND (note
) == REG_BR_PRED
449 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
454 /* Structure representing predictions in tree level. */
456 struct edge_prediction
{
457 struct edge_prediction
*ep_next
;
459 enum br_predictor ep_predictor
;
463 /* This map contains for a basic block the list of predictions for the
466 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
468 /* Return true if the one of outgoing edges is already predicted by
472 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
474 struct edge_prediction
*i
;
475 edge_prediction
**preds
= bb_predictions
->get (bb
);
480 for (i
= *preds
; i
; i
= i
->ep_next
)
481 if (i
->ep_predictor
== predictor
)
486 /* Return true when the probability of edge is reliable.
488 The profile guessing code is good at predicting branch outcome (ie.
489 taken/not taken), that is predicted right slightly over 75% of time.
490 It is however notoriously poor on predicting the probability itself.
491 In general the profile appear a lot flatter (with probabilities closer
492 to 50%) than the reality so it is bad idea to use it to drive optimization
493 such as those disabling dynamic branch prediction for well predictable
496 There are two exceptions - edges leading to noreturn edges and edges
497 predicted by number of iterations heuristics are predicted well. This macro
498 should be able to distinguish those, but at the moment it simply check for
499 noreturn heuristic that is only one giving probability over 99% or bellow
500 1%. In future we might want to propagate reliability information across the
501 CFG if we find this information useful on multiple places. */
503 probability_reliable_p (int prob
)
505 return (profile_status_for_fn (cfun
) == PROFILE_READ
506 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
507 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
510 /* Same predicate as above, working on edges. */
512 edge_probability_reliable_p (const_edge e
)
514 return probability_reliable_p (e
->probability
);
517 /* Same predicate as edge_probability_reliable_p, working on notes. */
519 br_prob_note_reliable_p (const_rtx note
)
521 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
522 return probability_reliable_p (XINT (note
, 0));
526 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
528 gcc_assert (any_condjump_p (insn
));
529 if (!flag_guess_branch_prob
)
532 add_reg_note (insn
, REG_BR_PRED
,
533 gen_rtx_CONCAT (VOIDmode
,
534 GEN_INT ((int) predictor
),
535 GEN_INT ((int) probability
)));
538 /* Predict insn by given predictor. */
541 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
542 enum prediction taken
)
544 int probability
= predictor_info
[(int) predictor
].hitrate
;
547 probability
= REG_BR_PROB_BASE
- probability
;
549 predict_insn (insn
, predictor
, probability
);
552 /* Predict edge E with given probability if possible. */
555 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
558 last_insn
= BB_END (e
->src
);
560 /* We can store the branch prediction information only about
561 conditional jumps. */
562 if (!any_condjump_p (last_insn
))
565 /* We always store probability of branching. */
566 if (e
->flags
& EDGE_FALLTHRU
)
567 probability
= REG_BR_PROB_BASE
- probability
;
569 predict_insn (last_insn
, predictor
, probability
);
572 /* Predict edge E with the given PROBABILITY. */
574 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
576 gcc_assert (profile_status_for_fn (cfun
) != PROFILE_GUESSED
);
577 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && EDGE_COUNT (e
->src
->succs
) >
579 && flag_guess_branch_prob
&& optimize
)
581 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
582 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
586 i
->ep_probability
= probability
;
587 i
->ep_predictor
= predictor
;
592 /* Remove all predictions on given basic block that are attached
595 remove_predictions_associated_with_edge (edge e
)
600 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
604 struct edge_prediction
**prediction
= preds
;
605 struct edge_prediction
*next
;
609 if ((*prediction
)->ep_edge
== e
)
611 next
= (*prediction
)->ep_next
;
616 prediction
= &((*prediction
)->ep_next
);
621 /* Clears the list of predictions stored for BB. */
624 clear_bb_predictions (basic_block bb
)
626 edge_prediction
**preds
= bb_predictions
->get (bb
);
627 struct edge_prediction
*pred
, *next
;
632 for (pred
= *preds
; pred
; pred
= next
)
634 next
= pred
->ep_next
;
640 /* Return true when we can store prediction on insn INSN.
641 At the moment we represent predictions only on conditional
642 jumps, not at computed jump or other complicated cases. */
644 can_predict_insn_p (const rtx_insn
*insn
)
646 return (JUMP_P (insn
)
647 && any_condjump_p (insn
)
648 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
651 /* Predict edge E by given predictor if possible. */
654 predict_edge_def (edge e
, enum br_predictor predictor
,
655 enum prediction taken
)
657 int probability
= predictor_info
[(int) predictor
].hitrate
;
660 probability
= REG_BR_PROB_BASE
- probability
;
662 predict_edge (e
, predictor
, probability
);
665 /* Invert all branch predictions or probability notes in the INSN. This needs
666 to be done each time we invert the condition used by the jump. */
669 invert_br_probabilities (rtx insn
)
673 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
674 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
675 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
676 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
677 XEXP (XEXP (note
, 0), 1)
678 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
681 /* Dump information about the branch prediction to the output file. */
684 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
685 basic_block bb
, int used
)
693 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
694 if (! (e
->flags
& EDGE_FALLTHRU
))
697 fprintf (file
, " %s heuristics%s: %.1f%%",
698 predictor_info
[predictor
].name
,
699 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
703 fprintf (file
, " exec %"PRId64
, bb
->count
);
706 fprintf (file
, " hit %"PRId64
, e
->count
);
707 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
711 fprintf (file
, "\n");
714 /* We can not predict the probabilities of outgoing edges of bb. Set them
715 evenly and hope for the best. */
717 set_even_probabilities (basic_block bb
)
723 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
724 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
726 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
727 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
728 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
733 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
734 note if not already present. Remove now useless REG_BR_PRED notes. */
737 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
742 int best_probability
= PROB_EVEN
;
743 enum br_predictor best_predictor
= END_PREDICTORS
;
744 int combined_probability
= REG_BR_PROB_BASE
/ 2;
746 bool first_match
= false;
749 if (!can_predict_insn_p (insn
))
751 set_even_probabilities (bb
);
755 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
756 pnote
= ®_NOTES (insn
);
758 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
761 /* We implement "first match" heuristics and use probability guessed
762 by predictor with smallest index. */
763 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
764 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
766 enum br_predictor predictor
= ((enum br_predictor
)
767 INTVAL (XEXP (XEXP (note
, 0), 0)));
768 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
771 if (best_predictor
> predictor
)
772 best_probability
= probability
, best_predictor
= predictor
;
774 d
= (combined_probability
* probability
775 + (REG_BR_PROB_BASE
- combined_probability
)
776 * (REG_BR_PROB_BASE
- probability
));
778 /* Use FP math to avoid overflows of 32bit integers. */
780 /* If one probability is 0% and one 100%, avoid division by zero. */
781 combined_probability
= REG_BR_PROB_BASE
/ 2;
783 combined_probability
= (((double) combined_probability
) * probability
784 * REG_BR_PROB_BASE
/ d
+ 0.5);
787 /* Decide which heuristic to use. In case we didn't match anything,
788 use no_prediction heuristic, in case we did match, use either
789 first match or Dempster-Shaffer theory depending on the flags. */
791 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
795 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
796 combined_probability
, bb
, true);
799 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
801 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
806 combined_probability
= best_probability
;
807 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
811 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
813 enum br_predictor predictor
= ((enum br_predictor
)
814 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
815 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
817 dump_prediction (dump_file
, predictor
, probability
, bb
,
818 !first_match
|| best_predictor
== predictor
);
819 *pnote
= XEXP (*pnote
, 1);
822 pnote
= &XEXP (*pnote
, 1);
827 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
829 /* Save the prediction into CFG in case we are seeing non-degenerated
831 if (!single_succ_p (bb
))
833 BRANCH_EDGE (bb
)->probability
= combined_probability
;
834 FALLTHRU_EDGE (bb
)->probability
835 = REG_BR_PROB_BASE
- combined_probability
;
838 else if (!single_succ_p (bb
))
840 int prob
= XINT (prob_note
, 0);
842 BRANCH_EDGE (bb
)->probability
= prob
;
843 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
846 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
849 /* Combine predictions into single probability and store them into CFG.
850 Remove now useless prediction entries. */
853 combine_predictions_for_bb (basic_block bb
)
855 int best_probability
= PROB_EVEN
;
856 enum br_predictor best_predictor
= END_PREDICTORS
;
857 int combined_probability
= REG_BR_PROB_BASE
/ 2;
859 bool first_match
= false;
861 struct edge_prediction
*pred
;
863 edge e
, first
= NULL
, second
= NULL
;
866 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
867 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
870 if (first
&& !second
)
876 /* When there is no successor or only one choice, prediction is easy.
878 We are lazy for now and predict only basic blocks with two outgoing
879 edges. It is possible to predict generic case too, but we have to
880 ignore first match heuristics and do more involved combining. Implement
885 set_even_probabilities (bb
);
886 clear_bb_predictions (bb
);
888 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
894 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
896 edge_prediction
**preds
= bb_predictions
->get (bb
);
899 /* We implement "first match" heuristics and use probability guessed
900 by predictor with smallest index. */
901 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
903 enum br_predictor predictor
= pred
->ep_predictor
;
904 int probability
= pred
->ep_probability
;
906 if (pred
->ep_edge
!= first
)
907 probability
= REG_BR_PROB_BASE
- probability
;
910 /* First match heuristics would be widly confused if we predicted
912 if (best_predictor
> predictor
)
914 struct edge_prediction
*pred2
;
915 int prob
= probability
;
917 for (pred2
= (struct edge_prediction
*) *preds
;
918 pred2
; pred2
= pred2
->ep_next
)
919 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
921 int probability2
= pred
->ep_probability
;
923 if (pred2
->ep_edge
!= first
)
924 probability2
= REG_BR_PROB_BASE
- probability2
;
926 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
927 (probability2
< REG_BR_PROB_BASE
/ 2))
930 /* If the same predictor later gave better result, go for it! */
931 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
932 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
936 best_probability
= prob
, best_predictor
= predictor
;
939 d
= (combined_probability
* probability
940 + (REG_BR_PROB_BASE
- combined_probability
)
941 * (REG_BR_PROB_BASE
- probability
));
943 /* Use FP math to avoid overflows of 32bit integers. */
945 /* If one probability is 0% and one 100%, avoid division by zero. */
946 combined_probability
= REG_BR_PROB_BASE
/ 2;
948 combined_probability
= (((double) combined_probability
)
950 * REG_BR_PROB_BASE
/ d
+ 0.5);
954 /* Decide which heuristic to use. In case we didn't match anything,
955 use no_prediction heuristic, in case we did match, use either
956 first match or Dempster-Shaffer theory depending on the flags. */
958 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
962 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
965 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
967 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
972 combined_probability
= best_probability
;
973 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
977 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
979 enum br_predictor predictor
= pred
->ep_predictor
;
980 int probability
= pred
->ep_probability
;
982 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
983 probability
= REG_BR_PROB_BASE
- probability
;
984 dump_prediction (dump_file
, predictor
, probability
, bb
,
985 !first_match
|| best_predictor
== predictor
);
988 clear_bb_predictions (bb
);
992 first
->probability
= combined_probability
;
993 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
997 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
998 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1000 T1 and T2 should be one of the following cases:
1001 1. T1 is SSA_NAME, T2 is NULL
1002 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1003 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1006 strips_small_constant (tree t1
, tree t2
)
1013 else if (TREE_CODE (t1
) == SSA_NAME
)
1015 else if (tree_fits_shwi_p (t1
))
1016 value
= tree_to_shwi (t1
);
1022 else if (tree_fits_shwi_p (t2
))
1023 value
= tree_to_shwi (t2
);
1024 else if (TREE_CODE (t2
) == SSA_NAME
)
1032 if (value
<= 4 && value
>= -4)
1038 /* Return the SSA_NAME in T or T's operands.
1039 Return NULL if SSA_NAME cannot be found. */
1042 get_base_value (tree t
)
1044 if (TREE_CODE (t
) == SSA_NAME
)
1047 if (!BINARY_CLASS_P (t
))
1050 switch (TREE_OPERAND_LENGTH (t
))
1053 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1055 return strips_small_constant (TREE_OPERAND (t
, 0),
1056 TREE_OPERAND (t
, 1));
1062 /* Check the compare STMT in LOOP. If it compares an induction
1063 variable to a loop invariant, return true, and save
1064 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1065 Otherwise return false and set LOOP_INVAIANT to NULL. */
1068 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1069 tree
*loop_invariant
,
1070 enum tree_code
*compare_code
,
1074 tree op0
, op1
, bound
, base
;
1076 enum tree_code code
;
1079 code
= gimple_cond_code (stmt
);
1080 *loop_invariant
= NULL
;
1096 op0
= gimple_cond_lhs (stmt
);
1097 op1
= gimple_cond_rhs (stmt
);
1099 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1100 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1102 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1104 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1106 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1107 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1109 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1110 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1113 if (integer_zerop (iv0
.step
))
1115 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1116 code
= invert_tree_comparison (code
, false);
1119 if (tree_fits_shwi_p (iv1
.step
))
1128 if (tree_fits_shwi_p (iv0
.step
))
1134 if (TREE_CODE (bound
) != INTEGER_CST
)
1135 bound
= get_base_value (bound
);
1138 if (TREE_CODE (base
) != INTEGER_CST
)
1139 base
= get_base_value (base
);
1143 *loop_invariant
= bound
;
1144 *compare_code
= code
;
1146 *loop_iv_base
= base
;
1150 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1153 expr_coherent_p (tree t1
, tree t2
)
1156 tree ssa_name_1
= NULL
;
1157 tree ssa_name_2
= NULL
;
1159 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1160 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1165 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1167 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1170 /* Check to see if t1 is expressed/defined with t2. */
1171 stmt
= SSA_NAME_DEF_STMT (t1
);
1172 gcc_assert (stmt
!= NULL
);
1173 if (is_gimple_assign (stmt
))
1175 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1176 if (ssa_name_1
&& ssa_name_1
== t2
)
1180 /* Check to see if t2 is expressed/defined with t1. */
1181 stmt
= SSA_NAME_DEF_STMT (t2
);
1182 gcc_assert (stmt
!= NULL
);
1183 if (is_gimple_assign (stmt
))
1185 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1186 if (ssa_name_2
&& ssa_name_2
== t1
)
1190 /* Compare if t1 and t2's def_stmts are identical. */
1191 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1197 /* Predict branch probability of BB when BB contains a branch that compares
1198 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1199 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1202 for (int i = 0; i < bound; i++) {
1209 In this loop, we will predict the branch inside the loop to be taken. */
1212 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1213 tree loop_bound_var
,
1214 tree loop_iv_base_var
,
1215 enum tree_code loop_bound_code
,
1216 int loop_bound_step
)
1219 tree compare_var
, compare_base
;
1220 enum tree_code compare_code
;
1221 tree compare_step_var
;
1225 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1226 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1227 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1230 stmt
= last_stmt (bb
);
1231 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1233 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1240 /* Find the taken edge. */
1241 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1242 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1245 /* When comparing an IV to a loop invariant, NE is more likely to be
1246 taken while EQ is more likely to be not-taken. */
1247 if (compare_code
== NE_EXPR
)
1249 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1252 else if (compare_code
== EQ_EXPR
)
1254 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1258 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1261 /* If loop bound, base and compare bound are all constants, we can
1262 calculate the probability directly. */
1263 if (tree_fits_shwi_p (loop_bound_var
)
1264 && tree_fits_shwi_p (compare_var
)
1265 && tree_fits_shwi_p (compare_base
))
1268 bool overflow
, overall_overflow
= false;
1269 widest_int compare_count
, tem
;
1271 /* (loop_bound - base) / compare_step */
1272 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1273 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1274 overall_overflow
|= overflow
;
1275 widest_int loop_count
= wi::div_trunc (tem
,
1276 wi::to_widest (compare_step_var
),
1278 overall_overflow
|= overflow
;
1280 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1281 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1283 /* (loop_bound - compare_bound) / compare_step */
1284 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1285 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1286 overall_overflow
|= overflow
;
1287 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1289 overall_overflow
|= overflow
;
1293 /* (compare_bound - base) / compare_step */
1294 tem
= wi::sub (wi::to_widest (compare_var
),
1295 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1296 overall_overflow
|= overflow
;
1297 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1299 overall_overflow
|= overflow
;
1301 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1303 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1305 if (wi::neg_p (compare_count
))
1307 if (wi::neg_p (loop_count
))
1309 if (loop_count
== 0)
1311 else if (wi::cmps (compare_count
, loop_count
) == 1)
1312 probability
= REG_BR_PROB_BASE
;
1315 tem
= compare_count
* REG_BR_PROB_BASE
;
1316 tem
= wi::udiv_trunc (tem
, loop_count
);
1317 probability
= tem
.to_uhwi ();
1320 if (!overall_overflow
)
1321 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1326 if (expr_coherent_p (loop_bound_var
, compare_var
))
1328 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1329 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1330 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1331 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1332 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1333 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1334 else if (loop_bound_code
== NE_EXPR
)
1336 /* If the loop backedge condition is "(i != bound)", we do
1337 the comparison based on the step of IV:
1338 * step < 0 : backedge condition is like (i > bound)
1339 * step > 0 : backedge condition is like (i < bound) */
1340 gcc_assert (loop_bound_step
!= 0);
1341 if (loop_bound_step
> 0
1342 && (compare_code
== LT_EXPR
1343 || compare_code
== LE_EXPR
))
1344 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1345 else if (loop_bound_step
< 0
1346 && (compare_code
== GT_EXPR
1347 || compare_code
== GE_EXPR
))
1348 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1350 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1353 /* The branch is predicted not-taken if loop_bound_code is
1354 opposite with compare_code. */
1355 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1357 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1360 for (i = s; i < h; i++)
1362 The branch should be predicted taken. */
1363 if (loop_bound_step
> 0
1364 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1365 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1366 else if (loop_bound_step
< 0
1367 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1368 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1370 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1374 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1375 exits are resulted from short-circuit conditions that will generate an
1378 if (foo() || global > 10)
1381 This will be translated into:
1386 if foo() goto BB6 else goto BB5
1388 if global > 10 goto BB6 else goto BB7
1392 iftmp = (PHI 0(BB5), 1(BB6))
1393 if iftmp == 1 goto BB8 else goto BB3
1395 outside of the loop...
1397 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1398 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1399 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1400 exits to predict them using PRED_LOOP_EXIT. */
1403 predict_extra_loop_exits (edge exit_edge
)
1406 bool check_value_one
;
1407 gimple lhs_def_stmt
;
1409 tree cmp_rhs
, cmp_lhs
;
1413 last
= last_stmt (exit_edge
->src
);
1416 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1420 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1421 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1422 if (!TREE_CONSTANT (cmp_rhs
)
1423 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1425 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1428 /* If check_value_one is true, only the phi_args with value '1' will lead
1429 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1431 check_value_one
= (((integer_onep (cmp_rhs
))
1432 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1433 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1435 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1439 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1443 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1447 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1448 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1450 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1452 if ((check_value_one
^ integer_onep (val
)) == 1)
1454 if (EDGE_COUNT (e
->src
->succs
) != 1)
1456 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1460 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1461 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1465 /* Predict edge probabilities by exploiting loop structure. */
1468 predict_loops (void)
1472 /* Try to predict out blocks in a loop that are not part of a
1474 FOR_EACH_LOOP (loop
, 0)
1476 basic_block bb
, *bbs
;
1477 unsigned j
, n_exits
;
1479 struct tree_niter_desc niter_desc
;
1481 struct nb_iter_bound
*nb_iter
;
1482 enum tree_code loop_bound_code
= ERROR_MARK
;
1483 tree loop_bound_step
= NULL
;
1484 tree loop_bound_var
= NULL
;
1485 tree loop_iv_base
= NULL
;
1488 exits
= get_loop_exit_edges (loop
);
1489 n_exits
= exits
.length ();
1496 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1499 HOST_WIDE_INT nitercst
;
1500 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1502 enum br_predictor predictor
;
1504 predict_extra_loop_exits (ex
);
1506 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1507 niter
= niter_desc
.niter
;
1508 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1509 niter
= loop_niter_by_eval (loop
, ex
);
1511 if (TREE_CODE (niter
) == INTEGER_CST
)
1513 if (tree_fits_uhwi_p (niter
)
1515 && compare_tree_int (niter
, max
- 1) == -1)
1516 nitercst
= tree_to_uhwi (niter
) + 1;
1519 predictor
= PRED_LOOP_ITERATIONS
;
1521 /* If we have just one exit and we can derive some information about
1522 the number of iterations of the loop from the statements inside
1523 the loop, use it to predict this exit. */
1524 else if (n_exits
== 1)
1526 nitercst
= estimated_stmt_executions_int (loop
);
1532 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1537 /* If the prediction for number of iterations is zero, do not
1538 predict the exit edges. */
1542 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1543 predict_edge (ex
, predictor
, probability
);
1547 /* Find information about loop bound variables. */
1548 for (nb_iter
= loop
->bounds
; nb_iter
;
1549 nb_iter
= nb_iter
->next
)
1551 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1553 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1556 if (!stmt
&& last_stmt (loop
->header
)
1557 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1558 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1560 is_comparison_with_loop_invariant_p (stmt
, loop
,
1566 bbs
= get_loop_body (loop
);
1568 for (j
= 0; j
< loop
->num_nodes
; j
++)
1570 int header_found
= 0;
1576 /* Bypass loop heuristics on continue statement. These
1577 statements construct loops via "non-loop" constructs
1578 in the source language and are better to be handled
1580 if (predicted_by_p (bb
, PRED_CONTINUE
))
1583 /* Loop branch heuristics - predict an edge back to a
1584 loop's head as taken. */
1585 if (bb
== loop
->latch
)
1587 e
= find_edge (loop
->latch
, loop
->header
);
1591 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1595 /* Loop exit heuristics - predict an edge exiting the loop if the
1596 conditional has no loop header successors as not taken. */
1598 /* If we already used more reliable loop exit predictors, do not
1599 bother with PRED_LOOP_EXIT. */
1600 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1601 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1603 /* For loop with many exits we don't want to predict all exits
1604 with the pretty large probability, because if all exits are
1605 considered in row, the loop would be predicted to iterate
1606 almost never. The code to divide probability by number of
1607 exits is very rough. It should compute the number of exits
1608 taken in each patch through function (not the overall number
1609 of exits that might be a lot higher for loops with wide switch
1610 statements in them) and compute n-th square root.
1612 We limit the minimal probability by 2% to avoid
1613 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1614 as this was causing regression in perl benchmark containing such
1617 int probability
= ((REG_BR_PROB_BASE
1618 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1620 if (probability
< HITRATE (2))
1621 probability
= HITRATE (2);
1622 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1623 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1624 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1625 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1628 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1630 tree_to_shwi (loop_bound_step
));
1633 /* Free basic blocks from get_loop_body. */
1638 /* Attempt to predict probabilities of BB outgoing edges using local
1641 bb_estimate_probability_locally (basic_block bb
)
1643 rtx_insn
*last_insn
= BB_END (bb
);
1646 if (! can_predict_insn_p (last_insn
))
1648 cond
= get_condition (last_insn
, NULL
, false, false);
1652 /* Try "pointer heuristic."
1653 A comparison ptr == 0 is predicted as false.
1654 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1655 if (COMPARISON_P (cond
)
1656 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1657 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1659 if (GET_CODE (cond
) == EQ
)
1660 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1661 else if (GET_CODE (cond
) == NE
)
1662 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1666 /* Try "opcode heuristic."
1667 EQ tests are usually false and NE tests are usually true. Also,
1668 most quantities are positive, so we can make the appropriate guesses
1669 about signed comparisons against zero. */
1670 switch (GET_CODE (cond
))
1673 /* Unconditional branch. */
1674 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1675 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1680 /* Floating point comparisons appears to behave in a very
1681 unpredictable way because of special role of = tests in
1683 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1685 /* Comparisons with 0 are often used for booleans and there is
1686 nothing useful to predict about them. */
1687 else if (XEXP (cond
, 1) == const0_rtx
1688 || XEXP (cond
, 0) == const0_rtx
)
1691 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1696 /* Floating point comparisons appears to behave in a very
1697 unpredictable way because of special role of = tests in
1699 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1701 /* Comparisons with 0 are often used for booleans and there is
1702 nothing useful to predict about them. */
1703 else if (XEXP (cond
, 1) == const0_rtx
1704 || XEXP (cond
, 0) == const0_rtx
)
1707 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1711 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1715 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1720 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1721 || XEXP (cond
, 1) == constm1_rtx
)
1722 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1727 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1728 || XEXP (cond
, 1) == constm1_rtx
)
1729 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1737 /* Set edge->probability for each successor edge of BB. */
1739 guess_outgoing_edge_probabilities (basic_block bb
)
1741 bb_estimate_probability_locally (bb
);
1742 combine_predictions_for_insn (BB_END (bb
), bb
);
1745 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
1747 /* Helper function for expr_expected_value. */
1750 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1751 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
1756 *predictor
= PRED_UNCONDITIONAL
;
1758 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1760 if (TREE_CONSTANT (op0
))
1763 if (code
!= SSA_NAME
)
1766 def
= SSA_NAME_DEF_STMT (op0
);
1768 /* If we were already here, break the infinite cycle. */
1769 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1772 if (gimple_code (def
) == GIMPLE_PHI
)
1774 /* All the arguments of the PHI node must have the same constant
1776 int i
, n
= gimple_phi_num_args (def
);
1777 tree val
= NULL
, new_val
;
1779 for (i
= 0; i
< n
; i
++)
1781 tree arg
= PHI_ARG_DEF (def
, i
);
1782 enum br_predictor predictor2
;
1784 /* If this PHI has itself as an argument, we cannot
1785 determine the string length of this argument. However,
1786 if we can find an expected constant value for the other
1787 PHI args then we can still be sure that this is
1788 likely a constant. So be optimistic and just
1789 continue with the next argument. */
1790 if (arg
== PHI_RESULT (def
))
1793 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
1795 /* It is difficult to combine value predictors. Simply assume
1796 that later predictor is weaker and take its prediction. */
1797 if (predictor
&& *predictor
< predictor2
)
1798 *predictor
= predictor2
;
1803 else if (!operand_equal_p (val
, new_val
, false))
1808 if (is_gimple_assign (def
))
1810 if (gimple_assign_lhs (def
) != op0
)
1813 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1814 gimple_assign_rhs1 (def
),
1815 gimple_assign_rhs_code (def
),
1816 gimple_assign_rhs2 (def
),
1817 visited
, predictor
);
1820 if (is_gimple_call (def
))
1822 tree decl
= gimple_call_fndecl (def
);
1825 if (gimple_call_internal_p (def
)
1826 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
1828 gcc_assert (gimple_call_num_args (def
) == 3);
1829 tree val
= gimple_call_arg (def
, 0);
1830 if (TREE_CONSTANT (val
))
1834 tree val2
= gimple_call_arg (def
, 2);
1835 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
1836 && tree_fits_uhwi_p (val2
)
1837 && tree_to_uhwi (val2
) < END_PREDICTORS
);
1838 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
1840 return gimple_call_arg (def
, 1);
1844 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1845 switch (DECL_FUNCTION_CODE (decl
))
1847 case BUILT_IN_EXPECT
:
1850 if (gimple_call_num_args (def
) != 2)
1852 val
= gimple_call_arg (def
, 0);
1853 if (TREE_CONSTANT (val
))
1856 *predictor
= PRED_BUILTIN_EXPECT
;
1857 return gimple_call_arg (def
, 1);
1860 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1861 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1862 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1863 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1864 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1865 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1866 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1867 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1868 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1869 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1870 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1871 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1872 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1873 /* Assume that any given atomic operation has low contention,
1874 and thus the compare-and-swap operation succeeds. */
1876 *predictor
= PRED_COMPARE_AND_SWAP
;
1877 return boolean_true_node
;
1886 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1889 enum br_predictor predictor2
;
1890 op0
= expr_expected_value (op0
, visited
, predictor
);
1893 op1
= expr_expected_value (op1
, visited
, &predictor2
);
1894 if (predictor
&& *predictor
< predictor2
)
1895 *predictor
= predictor2
;
1898 res
= fold_build2 (code
, type
, op0
, op1
);
1899 if (TREE_CONSTANT (res
))
1903 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1906 op0
= expr_expected_value (op0
, visited
, predictor
);
1909 res
= fold_build1 (code
, type
, op0
);
1910 if (TREE_CONSTANT (res
))
1917 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1918 The function is used by builtin_expect branch predictor so the evidence
1919 must come from this construct and additional possible constant folding.
1921 We may want to implement more involved value guess (such as value range
1922 propagation based prediction), but such tricks shall go to new
1926 expr_expected_value (tree expr
, bitmap visited
,
1927 enum br_predictor
*predictor
)
1929 enum tree_code code
;
1932 if (TREE_CONSTANT (expr
))
1935 *predictor
= PRED_UNCONDITIONAL
;
1939 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1940 return expr_expected_value_1 (TREE_TYPE (expr
),
1941 op0
, code
, op1
, visited
, predictor
);
1944 /* Predict using opcode of the last statement in basic block. */
1946 tree_predict_by_opcode (basic_block bb
)
1948 gimple stmt
= last_stmt (bb
);
1956 enum br_predictor predictor
;
1958 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1960 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1961 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1963 op0
= gimple_cond_lhs (stmt
);
1964 op1
= gimple_cond_rhs (stmt
);
1965 cmp
= gimple_cond_code (stmt
);
1966 type
= TREE_TYPE (op0
);
1967 visited
= BITMAP_ALLOC (NULL
);
1968 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
1970 BITMAP_FREE (visited
);
1971 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
1973 if (predictor
== PRED_BUILTIN_EXPECT
)
1975 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
1977 gcc_assert (percent
>= 0 && percent
<= 100);
1978 if (integer_zerop (val
))
1979 percent
= 100 - percent
;
1980 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
1983 predict_edge (then_edge
, predictor
,
1984 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
1986 /* Try "pointer heuristic."
1987 A comparison ptr == 0 is predicted as false.
1988 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1989 if (POINTER_TYPE_P (type
))
1992 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1993 else if (cmp
== NE_EXPR
)
1994 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1998 /* Try "opcode heuristic."
1999 EQ tests are usually false and NE tests are usually true. Also,
2000 most quantities are positive, so we can make the appropriate guesses
2001 about signed comparisons against zero. */
2006 /* Floating point comparisons appears to behave in a very
2007 unpredictable way because of special role of = tests in
2009 if (FLOAT_TYPE_P (type
))
2011 /* Comparisons with 0 are often used for booleans and there is
2012 nothing useful to predict about them. */
2013 else if (integer_zerop (op0
) || integer_zerop (op1
))
2016 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2021 /* Floating point comparisons appears to behave in a very
2022 unpredictable way because of special role of = tests in
2024 if (FLOAT_TYPE_P (type
))
2026 /* Comparisons with 0 are often used for booleans and there is
2027 nothing useful to predict about them. */
2028 else if (integer_zerop (op0
)
2029 || integer_zerop (op1
))
2032 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2036 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2039 case UNORDERED_EXPR
:
2040 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2045 if (integer_zerop (op1
)
2046 || integer_onep (op1
)
2047 || integer_all_onesp (op1
)
2050 || real_minus_onep (op1
))
2051 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2056 if (integer_zerop (op1
)
2057 || integer_onep (op1
)
2058 || integer_all_onesp (op1
)
2061 || real_minus_onep (op1
))
2062 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2070 /* Try to guess whether the value of return means error code. */
2072 static enum br_predictor
2073 return_prediction (tree val
, enum prediction
*prediction
)
2077 return PRED_NO_PREDICTION
;
2078 /* Different heuristics for pointers and scalars. */
2079 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2081 /* NULL is usually not returned. */
2082 if (integer_zerop (val
))
2084 *prediction
= NOT_TAKEN
;
2085 return PRED_NULL_RETURN
;
2088 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2090 /* Negative return values are often used to indicate
2092 if (TREE_CODE (val
) == INTEGER_CST
2093 && tree_int_cst_sgn (val
) < 0)
2095 *prediction
= NOT_TAKEN
;
2096 return PRED_NEGATIVE_RETURN
;
2098 /* Constant return values seems to be commonly taken.
2099 Zero/one often represent booleans so exclude them from the
2101 if (TREE_CONSTANT (val
)
2102 && (!integer_zerop (val
) && !integer_onep (val
)))
2104 *prediction
= TAKEN
;
2105 return PRED_CONST_RETURN
;
2108 return PRED_NO_PREDICTION
;
2111 /* Find the basic block with return expression and look up for possible
2112 return value trying to apply RETURN_PREDICTION heuristics. */
2114 apply_return_prediction (void)
2116 greturn
*return_stmt
= NULL
;
2120 int phi_num_args
, i
;
2121 enum br_predictor pred
;
2122 enum prediction direction
;
2125 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2127 gimple last
= last_stmt (e
->src
);
2129 && gimple_code (last
) == GIMPLE_RETURN
)
2131 return_stmt
= as_a
<greturn
*> (last
);
2137 return_val
= gimple_return_retval (return_stmt
);
2140 if (TREE_CODE (return_val
) != SSA_NAME
2141 || !SSA_NAME_DEF_STMT (return_val
)
2142 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2144 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2145 phi_num_args
= gimple_phi_num_args (phi
);
2146 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2148 /* Avoid the degenerate case where all return values form the function
2149 belongs to same category (ie they are all positive constants)
2150 so we can hardly say something about them. */
2151 for (i
= 1; i
< phi_num_args
; i
++)
2152 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2154 if (i
!= phi_num_args
)
2155 for (i
= 0; i
< phi_num_args
; i
++)
2157 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2158 if (pred
!= PRED_NO_PREDICTION
)
2159 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2164 /* Look for basic block that contains unlikely to happen events
2165 (such as noreturn calls) and mark all paths leading to execution
2166 of this basic blocks as unlikely. */
2169 tree_bb_level_predictions (void)
2172 bool has_return_edges
= false;
2176 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2177 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2179 has_return_edges
= true;
2183 apply_return_prediction ();
2185 FOR_EACH_BB_FN (bb
, cfun
)
2187 gimple_stmt_iterator gsi
;
2189 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2191 gimple stmt
= gsi_stmt (gsi
);
2194 if (is_gimple_call (stmt
))
2196 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2197 && has_return_edges
)
2198 predict_paths_leading_to (bb
, PRED_NORETURN
,
2200 decl
= gimple_call_fndecl (stmt
);
2202 && lookup_attribute ("cold",
2203 DECL_ATTRIBUTES (decl
)))
2204 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2207 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2209 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2210 gimple_predict_outcome (stmt
));
2211 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2212 hints to callers. */
2218 #ifdef ENABLE_CHECKING
2220 /* Callback for hash_map::traverse, asserts that the pointer map is
2224 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2227 gcc_assert (!value
);
2232 /* Predict branch probabilities and estimate profile for basic block BB. */
2235 tree_estimate_probability_bb (basic_block bb
)
2241 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2243 /* Predict edges to user labels with attributes. */
2244 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2246 gimple_stmt_iterator gi
;
2247 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2249 glabel
*label_stmt
=
2250 dyn_cast
<glabel
*> (gsi_stmt (gi
));
2255 decl
= gimple_label_label (label_stmt
);
2256 if (DECL_ARTIFICIAL (decl
))
2259 /* Finally, we have a user-defined label. */
2260 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2261 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2262 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2263 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2267 /* Predict early returns to be probable, as we've already taken
2268 care for error returns and other cases are often used for
2269 fast paths through function.
2271 Since we've already removed the return statements, we are
2272 looking for CFG like:
2282 if (e
->dest
!= bb
->next_bb
2283 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2284 && single_succ_p (e
->dest
)
2285 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2286 && (last
= last_stmt (e
->dest
)) != NULL
2287 && gimple_code (last
) == GIMPLE_RETURN
)
2292 if (single_succ_p (bb
))
2294 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2295 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2296 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2297 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2298 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2301 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2302 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2303 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2304 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2307 /* Look for block we are guarding (ie we dominate it,
2308 but it doesn't postdominate us). */
2309 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2310 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2311 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2313 gimple_stmt_iterator bi
;
2315 /* The call heuristic claims that a guarded function call
2316 is improbable. This is because such calls are often used
2317 to signal exceptional situations such as printing error
2319 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2322 gimple stmt
= gsi_stmt (bi
);
2323 if (is_gimple_call (stmt
)
2324 /* Constant and pure calls are hardly used to signalize
2325 something exceptional. */
2326 && gimple_has_side_effects (stmt
))
2328 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2334 tree_predict_by_opcode (bb
);
2337 /* Predict branch probabilities and estimate profile of the tree CFG.
2338 This function can be called from the loop optimizers to recompute
2339 the profile information. */
2342 tree_estimate_probability (void)
2346 add_noreturn_fake_exit_edges ();
2347 connect_infinite_loops_to_exit ();
2348 /* We use loop_niter_by_eval, which requires that the loops have
2350 create_preheaders (CP_SIMPLE_PREHEADERS
);
2351 calculate_dominance_info (CDI_POST_DOMINATORS
);
2353 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2354 tree_bb_level_predictions ();
2355 record_loop_exits ();
2357 if (number_of_loops (cfun
) > 1)
2360 FOR_EACH_BB_FN (bb
, cfun
)
2361 tree_estimate_probability_bb (bb
);
2363 FOR_EACH_BB_FN (bb
, cfun
)
2364 combine_predictions_for_bb (bb
);
2366 #ifdef ENABLE_CHECKING
2367 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2369 delete bb_predictions
;
2370 bb_predictions
= NULL
;
2372 estimate_bb_frequencies (false);
2373 free_dominance_info (CDI_POST_DOMINATORS
);
2374 remove_fake_exit_edges ();
2377 /* Predict edges to successors of CUR whose sources are not postdominated by
2378 BB by PRED and recurse to all postdominators. */
2381 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2382 enum br_predictor pred
,
2383 enum prediction taken
,
2390 /* We are looking for all edges forming edge cut induced by
2391 set of all blocks postdominated by BB. */
2392 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2393 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2394 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2400 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2401 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2403 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2405 /* See if there is an edge from e->src that is not abnormal
2406 and does not lead to BB. */
2407 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2409 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2410 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2416 /* If there is non-abnormal path leaving e->src, predict edge
2417 using predictor. Otherwise we need to look for paths
2420 The second may lead to infinite loop in the case we are predicitng
2421 regions that are only reachable by abnormal edges. We simply
2422 prevent visiting given BB twice. */
2424 predict_edge_def (e
, pred
, taken
);
2425 else if (bitmap_set_bit (visited
, e
->src
->index
))
2426 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2428 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2430 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2431 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2434 /* Sets branch probabilities according to PREDiction and
2438 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2439 enum prediction taken
)
2441 bitmap visited
= BITMAP_ALLOC (NULL
);
2442 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2443 BITMAP_FREE (visited
);
2446 /* Like predict_paths_leading_to but take edge instead of basic block. */
2449 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2450 enum prediction taken
)
2452 bool has_nonloop_edge
= false;
2456 basic_block bb
= e
->src
;
2457 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2458 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2459 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2460 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2462 has_nonloop_edge
= true;
2465 if (!has_nonloop_edge
)
2467 bitmap visited
= BITMAP_ALLOC (NULL
);
2468 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2469 BITMAP_FREE (visited
);
2472 predict_edge_def (e
, pred
, taken
);
2475 /* This is used to carry information about basic blocks. It is
2476 attached to the AUX field of the standard CFG block. */
2480 /* Estimated frequency of execution of basic_block. */
2483 /* To keep queue of basic blocks to process. */
2486 /* Number of predecessors we need to visit first. */
2490 /* Similar information for edges. */
2491 struct edge_prob_info
2493 /* In case edge is a loopback edge, the probability edge will be reached
2494 in case header is. Estimated number of iterations of the loop can be
2495 then computed as 1 / (1 - back_edge_prob). */
2496 sreal back_edge_prob
;
2497 /* True if the edge is a loopback edge in the natural loop. */
2498 unsigned int back_edge
:1;
2501 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2503 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2505 /* Helper function for estimate_bb_frequencies.
2506 Propagate the frequencies in blocks marked in
2507 TOVISIT, starting in HEAD. */
2510 propagate_freq (basic_block head
, bitmap tovisit
)
2519 /* For each basic block we need to visit count number of his predecessors
2520 we need to visit first. */
2521 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2526 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2528 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2530 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2532 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2534 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2536 "Irreducible region hit, ignoring edge to %i->%i\n",
2537 e
->src
->index
, bb
->index
);
2539 BLOCK_INFO (bb
)->npredecessors
= count
;
2540 /* When function never returns, we will never process exit block. */
2541 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2542 bb
->count
= bb
->frequency
= 0;
2545 BLOCK_INFO (head
)->frequency
= real_one
;
2547 for (bb
= head
; bb
; bb
= nextbb
)
2550 sreal cyclic_probability
= real_zero
;
2551 sreal frequency
= real_zero
;
2553 nextbb
= BLOCK_INFO (bb
)->next
;
2554 BLOCK_INFO (bb
)->next
= NULL
;
2556 /* Compute frequency of basic block. */
2559 #ifdef ENABLE_CHECKING
2560 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2561 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2562 || (e
->flags
& EDGE_DFS_BACK
));
2565 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2566 if (EDGE_INFO (e
)->back_edge
)
2568 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
2570 else if (!(e
->flags
& EDGE_DFS_BACK
))
2572 /* frequency += (e->probability
2573 * BLOCK_INFO (e->src)->frequency /
2574 REG_BR_PROB_BASE); */
2576 sreal
tmp (e
->probability
, 0);
2577 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
2578 tmp
*= real_inv_br_prob_base
;
2582 if (cyclic_probability
== real_zero
)
2584 BLOCK_INFO (bb
)->frequency
= frequency
;
2588 if (cyclic_probability
> real_almost_one
)
2589 cyclic_probability
= real_almost_one
;
2591 /* BLOCK_INFO (bb)->frequency = frequency
2592 / (1 - cyclic_probability) */
2594 cyclic_probability
= real_one
- cyclic_probability
;
2595 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
2599 bitmap_clear_bit (tovisit
, bb
->index
);
2601 e
= find_edge (bb
, head
);
2604 /* EDGE_INFO (e)->back_edge_prob
2605 = ((e->probability * BLOCK_INFO (bb)->frequency)
2606 / REG_BR_PROB_BASE); */
2608 sreal
tmp (e
->probability
, 0);
2609 tmp
*= BLOCK_INFO (bb
)->frequency
;
2610 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
2613 /* Propagate to successor blocks. */
2614 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2615 if (!(e
->flags
& EDGE_DFS_BACK
)
2616 && BLOCK_INFO (e
->dest
)->npredecessors
)
2618 BLOCK_INFO (e
->dest
)->npredecessors
--;
2619 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2624 BLOCK_INFO (last
)->next
= e
->dest
;
2632 /* Estimate frequencies in loops at same nest level. */
2635 estimate_loops_at_level (struct loop
*first_loop
)
2639 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2644 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2646 estimate_loops_at_level (loop
->inner
);
2648 /* Find current loop back edge and mark it. */
2649 e
= loop_latch_edge (loop
);
2650 EDGE_INFO (e
)->back_edge
= 1;
2652 bbs
= get_loop_body (loop
);
2653 for (i
= 0; i
< loop
->num_nodes
; i
++)
2654 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2656 propagate_freq (loop
->header
, tovisit
);
2657 BITMAP_FREE (tovisit
);
2661 /* Propagates frequencies through structure of loops. */
2664 estimate_loops (void)
2666 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2669 /* Start by estimating the frequencies in the loops. */
2670 if (number_of_loops (cfun
) > 1)
2671 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2673 /* Now propagate the frequencies through all the blocks. */
2674 FOR_ALL_BB_FN (bb
, cfun
)
2676 bitmap_set_bit (tovisit
, bb
->index
);
2678 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
2679 BITMAP_FREE (tovisit
);
2682 /* Drop the profile for NODE to guessed, and update its frequency based on
2683 whether it is expected to be hot given the CALL_COUNT. */
2686 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
2688 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2689 /* In the case where this was called by another function with a
2690 dropped profile, call_count will be 0. Since there are no
2691 non-zero call counts to this function, we don't know for sure
2692 whether it is hot, and therefore it will be marked normal below. */
2693 bool hot
= maybe_hot_count_p (NULL
, call_count
);
2697 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2698 node
->name (), node
->order
,
2699 hot
? "Function is hot" : "Function is normal");
2700 /* We only expect to miss profiles for functions that are reached
2701 via non-zero call edges in cases where the function may have
2702 been linked from another module or library (COMDATs and extern
2703 templates). See the comments below for handle_missing_profiles.
2704 Also, only warn in cases where the missing counts exceed the
2705 number of training runs. In certain cases with an execv followed
2706 by a no-return call the profile for the no-return call is not
2707 dumped and there can be a mismatch. */
2708 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
2709 && call_count
> profile_info
->runs
)
2711 if (flag_profile_correction
)
2715 "Missing counts for called function %s/%i\n",
2716 node
->name (), node
->order
);
2719 warning (0, "Missing counts for called function %s/%i",
2720 node
->name (), node
->order
);
2723 profile_status_for_fn (fn
)
2724 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2726 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2729 /* In the case of COMDAT routines, multiple object files will contain the same
2730 function and the linker will select one for the binary. In that case
2731 all the other copies from the profile instrument binary will be missing
2732 profile counts. Look for cases where this happened, due to non-zero
2733 call counts going to 0-count functions, and drop the profile to guessed
2734 so that we can use the estimated probabilities and avoid optimizing only
2737 The other case where the profile may be missing is when the routine
2738 is not going to be emitted to the object file, e.g. for "extern template"
2739 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2740 all other cases of non-zero calls to 0-count functions. */
2743 handle_missing_profiles (void)
2745 struct cgraph_node
*node
;
2746 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2747 vec
<struct cgraph_node
*> worklist
;
2748 worklist
.create (64);
2750 /* See if 0 count function has non-0 count callers. In this case we
2751 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2752 FOR_EACH_DEFINED_FUNCTION (node
)
2754 struct cgraph_edge
*e
;
2755 gcov_type call_count
= 0;
2756 gcov_type max_tp_first_run
= 0;
2757 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2761 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2763 call_count
+= e
->count
;
2765 if (e
->caller
->tp_first_run
> max_tp_first_run
)
2766 max_tp_first_run
= e
->caller
->tp_first_run
;
2769 /* If time profile is missing, let assign the maximum that comes from
2770 caller functions. */
2771 if (!node
->tp_first_run
&& max_tp_first_run
)
2772 node
->tp_first_run
= max_tp_first_run
+ 1;
2776 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2778 drop_profile (node
, call_count
);
2779 worklist
.safe_push (node
);
2783 /* Propagate the profile dropping to other 0-count COMDATs that are
2784 potentially called by COMDATs we already dropped the profile on. */
2785 while (worklist
.length () > 0)
2787 struct cgraph_edge
*e
;
2789 node
= worklist
.pop ();
2790 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2792 struct cgraph_node
*callee
= e
->callee
;
2793 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2795 if (callee
->count
> 0)
2797 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2798 && profile_status_for_fn (fn
) == PROFILE_READ
)
2800 drop_profile (node
, 0);
2801 worklist
.safe_push (callee
);
2805 worklist
.release ();
2808 /* Convert counts measured by profile driven feedback to frequencies.
2809 Return nonzero iff there was any nonzero execution count. */
2812 counts_to_freqs (void)
2814 gcov_type count_max
, true_count_max
= 0;
2817 /* Don't overwrite the estimated frequencies when the profile for
2818 the function is missing. We may drop this function PROFILE_GUESSED
2819 later in drop_profile (). */
2820 if (!flag_auto_profile
&& !ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
2823 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2824 true_count_max
= MAX (bb
->count
, true_count_max
);
2826 count_max
= MAX (true_count_max
, 1);
2827 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2828 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2830 return true_count_max
;
2833 /* Return true if function is likely to be expensive, so there is no point to
2834 optimize performance of prologue, epilogue or do inlining at the expense
2835 of code size growth. THRESHOLD is the limit of number of instructions
2836 function can execute at average to be still considered not expensive. */
2839 expensive_function_p (int threshold
)
2841 unsigned int sum
= 0;
2845 /* We can not compute accurately for large thresholds due to scaled
2847 gcc_assert (threshold
<= BB_FREQ_MAX
);
2849 /* Frequencies are out of range. This either means that function contains
2850 internal loop executing more than BB_FREQ_MAX times or profile feedback
2851 is available and function has not been executed at all. */
2852 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
2855 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2856 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
2857 FOR_EACH_BB_FN (bb
, cfun
)
2861 FOR_BB_INSNS (bb
, insn
)
2862 if (active_insn_p (insn
))
2864 sum
+= bb
->frequency
;
2873 /* Estimate and propagate basic block frequencies using the given branch
2874 probabilities. If FORCE is true, the frequencies are used to estimate
2875 the counts even when there are already non-zero profile counts. */
2878 estimate_bb_frequencies (bool force
)
2883 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
2885 static int real_values_initialized
= 0;
2887 if (!real_values_initialized
)
2889 real_values_initialized
= 1;
2890 real_zero
= sreal (0, 0);
2891 real_one
= sreal (1, 0);
2892 real_br_prob_base
= sreal (REG_BR_PROB_BASE
, 0);
2893 real_bb_freq_max
= sreal (BB_FREQ_MAX
, 0);
2894 real_one_half
= sreal (1, -1);
2895 real_inv_br_prob_base
= real_one
/ real_br_prob_base
;
2896 real_almost_one
= real_one
- 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
= sreal (e
->probability
, 0);
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. */
2923 freq_max
= real_zero
;
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 loop_optimizer_init (LOOPS_NORMAL
);
3043 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3044 flow_loops_dump (dump_file
, NULL
, 0);
3046 mark_irreducible_loops ();
3048 nb_loops
= number_of_loops (fun
);
3052 tree_estimate_probability ();
3057 loop_optimizer_finalize ();
3058 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3059 gimple_dump_cfg (dump_file
, dump_flags
);
3060 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3061 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3068 make_pass_profile (gcc::context
*ctxt
)
3070 return new pass_profile (ctxt
);
3075 const pass_data pass_data_strip_predict_hints
=
3077 GIMPLE_PASS
, /* type */
3078 "*strip_predict_hints", /* name */
3079 OPTGROUP_NONE
, /* optinfo_flags */
3080 TV_BRANCH_PROB
, /* tv_id */
3081 PROP_cfg
, /* properties_required */
3082 0, /* properties_provided */
3083 0, /* properties_destroyed */
3084 0, /* todo_flags_start */
3085 0, /* todo_flags_finish */
3088 class pass_strip_predict_hints
: public gimple_opt_pass
3091 pass_strip_predict_hints (gcc::context
*ctxt
)
3092 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3095 /* opt_pass methods: */
3096 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3097 virtual unsigned int execute (function
*);
3099 }; // class pass_strip_predict_hints
3101 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3102 we no longer need. */
3104 pass_strip_predict_hints::execute (function
*fun
)
3110 FOR_EACH_BB_FN (bb
, fun
)
3112 gimple_stmt_iterator bi
;
3113 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3115 gimple stmt
= gsi_stmt (bi
);
3117 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3119 gsi_remove (&bi
, true);
3122 else if (is_gimple_call (stmt
))
3124 tree fndecl
= gimple_call_fndecl (stmt
);
3127 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3128 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3129 && gimple_call_num_args (stmt
) == 2)
3130 || (gimple_call_internal_p (stmt
)
3131 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3133 var
= gimple_call_lhs (stmt
);
3137 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3138 gsi_replace (&bi
, ass_stmt
, true);
3142 gsi_remove (&bi
, true);
3156 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3158 return new pass_strip_predict_hints (ctxt
);
3161 /* Rebuild function frequencies. Passes are in general expected to
3162 maintain profile by hand, however in some cases this is not possible:
3163 for example when inlining several functions with loops freuqencies might run
3164 out of scale and thus needs to be recomputed. */
3167 rebuild_frequencies (void)
3169 timevar_push (TV_REBUILD_FREQUENCIES
);
3171 /* When the max bb count in the function is small, there is a higher
3172 chance that there were truncation errors in the integer scaling
3173 of counts by inlining and other optimizations. This could lead
3174 to incorrect classification of code as being cold when it isn't.
3175 In that case, force the estimation of bb counts/frequencies from the
3176 branch probabilities, rather than computing frequencies from counts,
3177 which may also lead to frequencies incorrectly reduced to 0. There
3178 is less precision in the probabilities, so we only do this for small
3180 gcov_type count_max
= 0;
3182 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3183 count_max
= MAX (bb
->count
, count_max
);
3185 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3186 || (!flag_auto_profile
&& profile_status_for_fn (cfun
) == PROFILE_READ
3187 && count_max
< REG_BR_PROB_BASE
/10))
3189 loop_optimizer_init (0);
3190 add_noreturn_fake_exit_edges ();
3191 mark_irreducible_loops ();
3192 connect_infinite_loops_to_exit ();
3193 estimate_bb_frequencies (true);
3194 remove_fake_exit_edges ();
3195 loop_optimizer_finalize ();
3197 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3201 timevar_pop (TV_REBUILD_FREQUENCIES
);