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"
37 #include "double-int.h"
44 #include "fold-const.h"
48 #include "hard-reg-set.h"
52 #include "dominance.h"
55 #include "basic-block.h"
56 #include "insn-config.h"
61 #include "diagnostic-core.h"
70 #include "tree-ssa-alias.h"
71 #include "internal-fn.h"
72 #include "gimple-expr.h"
75 #include "gimple-iterator.h"
76 #include "gimple-ssa.h"
77 #include "plugin-api.h"
81 #include "tree-phinodes.h"
82 #include "ssa-iterators.h"
83 #include "tree-ssa-loop-niter.h"
84 #include "tree-ssa-loop.h"
85 #include "tree-pass.h"
86 #include "tree-scalar-evolution.h"
89 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
90 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
91 static sreal real_almost_one
, real_br_prob_base
,
92 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
94 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
95 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
96 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
97 static void predict_paths_leading_to_edge (edge
, enum br_predictor
, enum prediction
);
98 static bool can_predict_insn_p (const rtx_insn
*);
100 /* Information we hold about each branch predictor.
101 Filled using information from predict.def. */
103 struct predictor_info
105 const char *const name
; /* Name used in the debugging dumps. */
106 const int hitrate
; /* Expected hitrate used by
107 predict_insn_def call. */
111 /* Use given predictor without Dempster-Shaffer theory if it matches
112 using first_match heuristics. */
113 #define PRED_FLAG_FIRST_MATCH 1
115 /* Recompute hitrate in percent to our representation. */
117 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
119 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
120 static const struct predictor_info predictor_info
[]= {
121 #include "predict.def"
123 /* Upper bound on predictors. */
128 /* Return TRUE if frequency FREQ is considered to be hot. */
131 maybe_hot_frequency_p (struct function
*fun
, int freq
)
133 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
135 || !opt_for_fn (fun
->decl
, flag_branch_probabilities
))
137 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
139 if (node
->frequency
== NODE_FREQUENCY_HOT
)
142 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
144 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
145 && freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
* 2 / 3))
147 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
149 if (freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
150 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
155 static gcov_type min_count
= -1;
157 /* Determine the threshold for hot BB counts. */
160 get_hot_bb_threshold ()
162 gcov_working_set_t
*ws
;
165 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
167 min_count
= ws
->min_counter
;
172 /* Set the threshold for hot BB counts. */
175 set_hot_bb_threshold (gcov_type min
)
180 /* Return TRUE if frequency FREQ is considered to be hot. */
183 maybe_hot_count_p (struct function
*fun
, gcov_type count
)
185 if (fun
&& profile_status_for_fn (fun
) != PROFILE_READ
)
187 /* Code executed at most once is not hot. */
188 if (profile_info
->runs
>= count
)
190 return (count
>= get_hot_bb_threshold ());
193 /* Return true in case BB can be CPU intensive and should be optimized
194 for maximal performance. */
197 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
199 gcc_checking_assert (fun
);
200 if (profile_status_for_fn (fun
) == PROFILE_READ
)
201 return maybe_hot_count_p (fun
, bb
->count
);
202 return maybe_hot_frequency_p (fun
, bb
->frequency
);
205 /* Return true in case BB can be CPU intensive and should be optimized
206 for maximal performance. */
209 maybe_hot_edge_p (edge e
)
211 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
212 return maybe_hot_count_p (cfun
, e
->count
);
213 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
216 /* Return true if profile COUNT and FREQUENCY, or function FUN static
217 node frequency reflects never being executed. */
220 probably_never_executed (struct function
*fun
,
221 gcov_type count
, int frequency
)
223 gcc_checking_assert (fun
);
224 if (profile_status_for_fn (fun
) == PROFILE_READ
)
226 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
227 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
231 if (!ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
233 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
235 gcov_type computed_count
;
236 /* Check for possibility of overflow, in which case entry bb count
237 is large enough to do the division first without losing much
239 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
< REG_BR_PROB_BASE
*
242 gcov_type scaled_count
243 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
*
244 unlikely_count_fraction
;
245 computed_count
= RDIV (scaled_count
,
246 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
250 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
,
251 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
252 computed_count
*= frequency
* unlikely_count_fraction
;
254 if (computed_count
>= profile_info
->runs
)
259 if ((!profile_info
|| !(opt_for_fn (fun
->decl
, flag_branch_probabilities
)))
260 && (cgraph_node::get (fun
->decl
)->frequency
261 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
267 /* Return true in case BB is probably never executed. */
270 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
272 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
276 /* Return true in case edge E is probably never executed. */
279 probably_never_executed_edge_p (struct function
*fun
, edge e
)
281 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
284 /* Return true when current function should always be optimized for size. */
287 optimize_function_for_size_p (struct function
*fun
)
289 if (!fun
|| !fun
->decl
)
290 return optimize_size
;
291 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
292 return n
&& n
->optimize_for_size_p ();
295 /* Return true when current function should always be optimized for speed. */
298 optimize_function_for_speed_p (struct function
*fun
)
300 return !optimize_function_for_size_p (fun
);
303 /* Return TRUE when BB should be optimized for size. */
306 optimize_bb_for_size_p (const_basic_block bb
)
308 return (optimize_function_for_size_p (cfun
)
309 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
312 /* Return TRUE when BB should be optimized for speed. */
315 optimize_bb_for_speed_p (const_basic_block bb
)
317 return !optimize_bb_for_size_p (bb
);
320 /* Return TRUE when BB should be optimized for size. */
323 optimize_edge_for_size_p (edge e
)
325 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
328 /* Return TRUE when BB should be optimized for speed. */
331 optimize_edge_for_speed_p (edge e
)
333 return !optimize_edge_for_size_p (e
);
336 /* Return TRUE when BB should be optimized for size. */
339 optimize_insn_for_size_p (void)
341 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
344 /* Return TRUE when BB should be optimized for speed. */
347 optimize_insn_for_speed_p (void)
349 return !optimize_insn_for_size_p ();
352 /* Return TRUE when LOOP should be optimized for size. */
355 optimize_loop_for_size_p (struct loop
*loop
)
357 return optimize_bb_for_size_p (loop
->header
);
360 /* Return TRUE when LOOP should be optimized for speed. */
363 optimize_loop_for_speed_p (struct loop
*loop
)
365 return optimize_bb_for_speed_p (loop
->header
);
368 /* Return TRUE when LOOP nest should be optimized for speed. */
371 optimize_loop_nest_for_speed_p (struct loop
*loop
)
373 struct loop
*l
= loop
;
374 if (optimize_loop_for_speed_p (loop
))
377 while (l
&& l
!= loop
)
379 if (optimize_loop_for_speed_p (l
))
387 while (l
!= loop
&& !l
->next
)
396 /* Return TRUE when LOOP nest should be optimized for size. */
399 optimize_loop_nest_for_size_p (struct loop
*loop
)
401 return !optimize_loop_nest_for_speed_p (loop
);
404 /* Return true when edge E is likely to be well predictable by branch
408 predictable_edge_p (edge e
)
410 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
413 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
414 || (REG_BR_PROB_BASE
- e
->probability
415 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
421 /* Set RTL expansion for BB profile. */
424 rtl_profile_for_bb (basic_block bb
)
426 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
429 /* Set RTL expansion for edge profile. */
432 rtl_profile_for_edge (edge e
)
434 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
437 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
439 default_rtl_profile (void)
441 crtl
->maybe_hot_insn_p
= true;
444 /* Return true if the one of outgoing edges is already predicted by
448 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
451 if (!INSN_P (BB_END (bb
)))
453 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
454 if (REG_NOTE_KIND (note
) == REG_BR_PRED
455 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
460 /* Structure representing predictions in tree level. */
462 struct edge_prediction
{
463 struct edge_prediction
*ep_next
;
465 enum br_predictor ep_predictor
;
469 /* This map contains for a basic block the list of predictions for the
472 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
474 /* Return true if the one of outgoing edges is already predicted by
478 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
480 struct edge_prediction
*i
;
481 edge_prediction
**preds
= bb_predictions
->get (bb
);
486 for (i
= *preds
; i
; i
= i
->ep_next
)
487 if (i
->ep_predictor
== predictor
)
492 /* Return true when the probability of edge is reliable.
494 The profile guessing code is good at predicting branch outcome (ie.
495 taken/not taken), that is predicted right slightly over 75% of time.
496 It is however notoriously poor on predicting the probability itself.
497 In general the profile appear a lot flatter (with probabilities closer
498 to 50%) than the reality so it is bad idea to use it to drive optimization
499 such as those disabling dynamic branch prediction for well predictable
502 There are two exceptions - edges leading to noreturn edges and edges
503 predicted by number of iterations heuristics are predicted well. This macro
504 should be able to distinguish those, but at the moment it simply check for
505 noreturn heuristic that is only one giving probability over 99% or bellow
506 1%. In future we might want to propagate reliability information across the
507 CFG if we find this information useful on multiple places. */
509 probability_reliable_p (int prob
)
511 return (profile_status_for_fn (cfun
) == PROFILE_READ
512 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
513 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
516 /* Same predicate as above, working on edges. */
518 edge_probability_reliable_p (const_edge e
)
520 return probability_reliable_p (e
->probability
);
523 /* Same predicate as edge_probability_reliable_p, working on notes. */
525 br_prob_note_reliable_p (const_rtx note
)
527 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
528 return probability_reliable_p (XINT (note
, 0));
532 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
534 gcc_assert (any_condjump_p (insn
));
535 if (!flag_guess_branch_prob
)
538 add_reg_note (insn
, REG_BR_PRED
,
539 gen_rtx_CONCAT (VOIDmode
,
540 GEN_INT ((int) predictor
),
541 GEN_INT ((int) probability
)));
544 /* Predict insn by given predictor. */
547 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
548 enum prediction taken
)
550 int probability
= predictor_info
[(int) predictor
].hitrate
;
553 probability
= REG_BR_PROB_BASE
- probability
;
555 predict_insn (insn
, predictor
, probability
);
558 /* Predict edge E with given probability if possible. */
561 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
564 last_insn
= BB_END (e
->src
);
566 /* We can store the branch prediction information only about
567 conditional jumps. */
568 if (!any_condjump_p (last_insn
))
571 /* We always store probability of branching. */
572 if (e
->flags
& EDGE_FALLTHRU
)
573 probability
= REG_BR_PROB_BASE
- probability
;
575 predict_insn (last_insn
, predictor
, probability
);
578 /* Predict edge E with the given PROBABILITY. */
580 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
582 gcc_assert (profile_status_for_fn (cfun
) != PROFILE_GUESSED
);
583 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && EDGE_COUNT (e
->src
->succs
) >
585 && flag_guess_branch_prob
&& optimize
)
587 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
588 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
592 i
->ep_probability
= probability
;
593 i
->ep_predictor
= predictor
;
598 /* Remove all predictions on given basic block that are attached
601 remove_predictions_associated_with_edge (edge e
)
606 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
610 struct edge_prediction
**prediction
= preds
;
611 struct edge_prediction
*next
;
615 if ((*prediction
)->ep_edge
== e
)
617 next
= (*prediction
)->ep_next
;
622 prediction
= &((*prediction
)->ep_next
);
627 /* Clears the list of predictions stored for BB. */
630 clear_bb_predictions (basic_block bb
)
632 edge_prediction
**preds
= bb_predictions
->get (bb
);
633 struct edge_prediction
*pred
, *next
;
638 for (pred
= *preds
; pred
; pred
= next
)
640 next
= pred
->ep_next
;
646 /* Return true when we can store prediction on insn INSN.
647 At the moment we represent predictions only on conditional
648 jumps, not at computed jump or other complicated cases. */
650 can_predict_insn_p (const rtx_insn
*insn
)
652 return (JUMP_P (insn
)
653 && any_condjump_p (insn
)
654 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
657 /* Predict edge E by given predictor if possible. */
660 predict_edge_def (edge e
, enum br_predictor predictor
,
661 enum prediction taken
)
663 int probability
= predictor_info
[(int) predictor
].hitrate
;
666 probability
= REG_BR_PROB_BASE
- probability
;
668 predict_edge (e
, predictor
, probability
);
671 /* Invert all branch predictions or probability notes in the INSN. This needs
672 to be done each time we invert the condition used by the jump. */
675 invert_br_probabilities (rtx insn
)
679 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
680 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
681 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
682 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
683 XEXP (XEXP (note
, 0), 1)
684 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
687 /* Dump information about the branch prediction to the output file. */
690 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
691 basic_block bb
, int used
)
699 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
700 if (! (e
->flags
& EDGE_FALLTHRU
))
703 fprintf (file
, " %s heuristics%s: %.1f%%",
704 predictor_info
[predictor
].name
,
705 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
709 fprintf (file
, " exec %"PRId64
, bb
->count
);
712 fprintf (file
, " hit %"PRId64
, e
->count
);
713 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
717 fprintf (file
, "\n");
720 /* We can not predict the probabilities of outgoing edges of bb. Set them
721 evenly and hope for the best. */
723 set_even_probabilities (basic_block bb
)
729 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
730 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
732 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
733 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
734 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
739 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
740 note if not already present. Remove now useless REG_BR_PRED notes. */
743 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
748 int best_probability
= PROB_EVEN
;
749 enum br_predictor best_predictor
= END_PREDICTORS
;
750 int combined_probability
= REG_BR_PROB_BASE
/ 2;
752 bool first_match
= false;
755 if (!can_predict_insn_p (insn
))
757 set_even_probabilities (bb
);
761 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
762 pnote
= ®_NOTES (insn
);
764 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
767 /* We implement "first match" heuristics and use probability guessed
768 by predictor with smallest index. */
769 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
770 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
772 enum br_predictor predictor
= ((enum br_predictor
)
773 INTVAL (XEXP (XEXP (note
, 0), 0)));
774 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
777 if (best_predictor
> predictor
)
778 best_probability
= probability
, best_predictor
= predictor
;
780 d
= (combined_probability
* probability
781 + (REG_BR_PROB_BASE
- combined_probability
)
782 * (REG_BR_PROB_BASE
- probability
));
784 /* Use FP math to avoid overflows of 32bit integers. */
786 /* If one probability is 0% and one 100%, avoid division by zero. */
787 combined_probability
= REG_BR_PROB_BASE
/ 2;
789 combined_probability
= (((double) combined_probability
) * probability
790 * REG_BR_PROB_BASE
/ d
+ 0.5);
793 /* Decide which heuristic to use. In case we didn't match anything,
794 use no_prediction heuristic, in case we did match, use either
795 first match or Dempster-Shaffer theory depending on the flags. */
797 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
801 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
802 combined_probability
, bb
, true);
805 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
807 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
812 combined_probability
= best_probability
;
813 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
817 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
819 enum br_predictor predictor
= ((enum br_predictor
)
820 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
821 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
823 dump_prediction (dump_file
, predictor
, probability
, bb
,
824 !first_match
|| best_predictor
== predictor
);
825 *pnote
= XEXP (*pnote
, 1);
828 pnote
= &XEXP (*pnote
, 1);
833 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
835 /* Save the prediction into CFG in case we are seeing non-degenerated
837 if (!single_succ_p (bb
))
839 BRANCH_EDGE (bb
)->probability
= combined_probability
;
840 FALLTHRU_EDGE (bb
)->probability
841 = REG_BR_PROB_BASE
- combined_probability
;
844 else if (!single_succ_p (bb
))
846 int prob
= XINT (prob_note
, 0);
848 BRANCH_EDGE (bb
)->probability
= prob
;
849 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
852 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
855 /* Combine predictions into single probability and store them into CFG.
856 Remove now useless prediction entries. */
859 combine_predictions_for_bb (basic_block bb
)
861 int best_probability
= PROB_EVEN
;
862 enum br_predictor best_predictor
= END_PREDICTORS
;
863 int combined_probability
= REG_BR_PROB_BASE
/ 2;
865 bool first_match
= false;
867 struct edge_prediction
*pred
;
869 edge e
, first
= NULL
, second
= NULL
;
872 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
873 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
876 if (first
&& !second
)
882 /* When there is no successor or only one choice, prediction is easy.
884 We are lazy for now and predict only basic blocks with two outgoing
885 edges. It is possible to predict generic case too, but we have to
886 ignore first match heuristics and do more involved combining. Implement
891 set_even_probabilities (bb
);
892 clear_bb_predictions (bb
);
894 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
900 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
902 edge_prediction
**preds
= bb_predictions
->get (bb
);
905 /* We implement "first match" heuristics and use probability guessed
906 by predictor with smallest index. */
907 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
909 enum br_predictor predictor
= pred
->ep_predictor
;
910 int probability
= pred
->ep_probability
;
912 if (pred
->ep_edge
!= first
)
913 probability
= REG_BR_PROB_BASE
- probability
;
916 /* First match heuristics would be widly confused if we predicted
918 if (best_predictor
> predictor
)
920 struct edge_prediction
*pred2
;
921 int prob
= probability
;
923 for (pred2
= (struct edge_prediction
*) *preds
;
924 pred2
; pred2
= pred2
->ep_next
)
925 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
927 int probability2
= pred
->ep_probability
;
929 if (pred2
->ep_edge
!= first
)
930 probability2
= REG_BR_PROB_BASE
- probability2
;
932 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
933 (probability2
< REG_BR_PROB_BASE
/ 2))
936 /* If the same predictor later gave better result, go for it! */
937 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
938 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
942 best_probability
= prob
, best_predictor
= predictor
;
945 d
= (combined_probability
* probability
946 + (REG_BR_PROB_BASE
- combined_probability
)
947 * (REG_BR_PROB_BASE
- probability
));
949 /* Use FP math to avoid overflows of 32bit integers. */
951 /* If one probability is 0% and one 100%, avoid division by zero. */
952 combined_probability
= REG_BR_PROB_BASE
/ 2;
954 combined_probability
= (((double) combined_probability
)
956 * REG_BR_PROB_BASE
/ d
+ 0.5);
960 /* Decide which heuristic to use. In case we didn't match anything,
961 use no_prediction heuristic, in case we did match, use either
962 first match or Dempster-Shaffer theory depending on the flags. */
964 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
968 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
971 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
973 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
978 combined_probability
= best_probability
;
979 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
983 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
985 enum br_predictor predictor
= pred
->ep_predictor
;
986 int probability
= pred
->ep_probability
;
988 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
989 probability
= REG_BR_PROB_BASE
- probability
;
990 dump_prediction (dump_file
, predictor
, probability
, bb
,
991 !first_match
|| best_predictor
== predictor
);
994 clear_bb_predictions (bb
);
998 first
->probability
= combined_probability
;
999 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1003 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1004 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1006 T1 and T2 should be one of the following cases:
1007 1. T1 is SSA_NAME, T2 is NULL
1008 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1009 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1012 strips_small_constant (tree t1
, tree t2
)
1019 else if (TREE_CODE (t1
) == SSA_NAME
)
1021 else if (tree_fits_shwi_p (t1
))
1022 value
= tree_to_shwi (t1
);
1028 else if (tree_fits_shwi_p (t2
))
1029 value
= tree_to_shwi (t2
);
1030 else if (TREE_CODE (t2
) == SSA_NAME
)
1038 if (value
<= 4 && value
>= -4)
1044 /* Return the SSA_NAME in T or T's operands.
1045 Return NULL if SSA_NAME cannot be found. */
1048 get_base_value (tree t
)
1050 if (TREE_CODE (t
) == SSA_NAME
)
1053 if (!BINARY_CLASS_P (t
))
1056 switch (TREE_OPERAND_LENGTH (t
))
1059 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1061 return strips_small_constant (TREE_OPERAND (t
, 0),
1062 TREE_OPERAND (t
, 1));
1068 /* Check the compare STMT in LOOP. If it compares an induction
1069 variable to a loop invariant, return true, and save
1070 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1071 Otherwise return false and set LOOP_INVAIANT to NULL. */
1074 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1075 tree
*loop_invariant
,
1076 enum tree_code
*compare_code
,
1080 tree op0
, op1
, bound
, base
;
1082 enum tree_code code
;
1085 code
= gimple_cond_code (stmt
);
1086 *loop_invariant
= NULL
;
1102 op0
= gimple_cond_lhs (stmt
);
1103 op1
= gimple_cond_rhs (stmt
);
1105 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1106 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1108 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1110 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1112 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1113 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1115 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1116 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1119 if (integer_zerop (iv0
.step
))
1121 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1122 code
= invert_tree_comparison (code
, false);
1125 if (tree_fits_shwi_p (iv1
.step
))
1134 if (tree_fits_shwi_p (iv0
.step
))
1140 if (TREE_CODE (bound
) != INTEGER_CST
)
1141 bound
= get_base_value (bound
);
1144 if (TREE_CODE (base
) != INTEGER_CST
)
1145 base
= get_base_value (base
);
1149 *loop_invariant
= bound
;
1150 *compare_code
= code
;
1152 *loop_iv_base
= base
;
1156 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1159 expr_coherent_p (tree t1
, tree t2
)
1162 tree ssa_name_1
= NULL
;
1163 tree ssa_name_2
= NULL
;
1165 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1166 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1171 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1173 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1176 /* Check to see if t1 is expressed/defined with t2. */
1177 stmt
= SSA_NAME_DEF_STMT (t1
);
1178 gcc_assert (stmt
!= NULL
);
1179 if (is_gimple_assign (stmt
))
1181 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1182 if (ssa_name_1
&& ssa_name_1
== t2
)
1186 /* Check to see if t2 is expressed/defined with t1. */
1187 stmt
= SSA_NAME_DEF_STMT (t2
);
1188 gcc_assert (stmt
!= NULL
);
1189 if (is_gimple_assign (stmt
))
1191 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1192 if (ssa_name_2
&& ssa_name_2
== t1
)
1196 /* Compare if t1 and t2's def_stmts are identical. */
1197 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1203 /* Predict branch probability of BB when BB contains a branch that compares
1204 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1205 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1208 for (int i = 0; i < bound; i++) {
1215 In this loop, we will predict the branch inside the loop to be taken. */
1218 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1219 tree loop_bound_var
,
1220 tree loop_iv_base_var
,
1221 enum tree_code loop_bound_code
,
1222 int loop_bound_step
)
1225 tree compare_var
, compare_base
;
1226 enum tree_code compare_code
;
1227 tree compare_step_var
;
1231 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1232 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1233 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1236 stmt
= last_stmt (bb
);
1237 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1239 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1246 /* Find the taken edge. */
1247 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1248 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1251 /* When comparing an IV to a loop invariant, NE is more likely to be
1252 taken while EQ is more likely to be not-taken. */
1253 if (compare_code
== NE_EXPR
)
1255 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1258 else if (compare_code
== EQ_EXPR
)
1260 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1264 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1267 /* If loop bound, base and compare bound are all constants, we can
1268 calculate the probability directly. */
1269 if (tree_fits_shwi_p (loop_bound_var
)
1270 && tree_fits_shwi_p (compare_var
)
1271 && tree_fits_shwi_p (compare_base
))
1274 bool overflow
, overall_overflow
= false;
1275 widest_int compare_count
, tem
;
1277 /* (loop_bound - base) / compare_step */
1278 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1279 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1280 overall_overflow
|= overflow
;
1281 widest_int loop_count
= wi::div_trunc (tem
,
1282 wi::to_widest (compare_step_var
),
1284 overall_overflow
|= overflow
;
1286 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1287 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1289 /* (loop_bound - compare_bound) / compare_step */
1290 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1291 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1292 overall_overflow
|= overflow
;
1293 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1295 overall_overflow
|= overflow
;
1299 /* (compare_bound - base) / compare_step */
1300 tem
= wi::sub (wi::to_widest (compare_var
),
1301 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1302 overall_overflow
|= overflow
;
1303 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1305 overall_overflow
|= overflow
;
1307 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1309 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1311 if (wi::neg_p (compare_count
))
1313 if (wi::neg_p (loop_count
))
1315 if (loop_count
== 0)
1317 else if (wi::cmps (compare_count
, loop_count
) == 1)
1318 probability
= REG_BR_PROB_BASE
;
1321 tem
= compare_count
* REG_BR_PROB_BASE
;
1322 tem
= wi::udiv_trunc (tem
, loop_count
);
1323 probability
= tem
.to_uhwi ();
1326 if (!overall_overflow
)
1327 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1332 if (expr_coherent_p (loop_bound_var
, compare_var
))
1334 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1335 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1336 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1337 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1338 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1339 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1340 else if (loop_bound_code
== NE_EXPR
)
1342 /* If the loop backedge condition is "(i != bound)", we do
1343 the comparison based on the step of IV:
1344 * step < 0 : backedge condition is like (i > bound)
1345 * step > 0 : backedge condition is like (i < bound) */
1346 gcc_assert (loop_bound_step
!= 0);
1347 if (loop_bound_step
> 0
1348 && (compare_code
== LT_EXPR
1349 || compare_code
== LE_EXPR
))
1350 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1351 else if (loop_bound_step
< 0
1352 && (compare_code
== GT_EXPR
1353 || compare_code
== GE_EXPR
))
1354 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1356 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1359 /* The branch is predicted not-taken if loop_bound_code is
1360 opposite with compare_code. */
1361 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1363 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1366 for (i = s; i < h; i++)
1368 The branch should be predicted taken. */
1369 if (loop_bound_step
> 0
1370 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1371 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1372 else if (loop_bound_step
< 0
1373 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1374 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1376 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1380 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1381 exits are resulted from short-circuit conditions that will generate an
1384 if (foo() || global > 10)
1387 This will be translated into:
1392 if foo() goto BB6 else goto BB5
1394 if global > 10 goto BB6 else goto BB7
1398 iftmp = (PHI 0(BB5), 1(BB6))
1399 if iftmp == 1 goto BB8 else goto BB3
1401 outside of the loop...
1403 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1404 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1405 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1406 exits to predict them using PRED_LOOP_EXIT. */
1409 predict_extra_loop_exits (edge exit_edge
)
1412 bool check_value_one
;
1413 gimple lhs_def_stmt
;
1415 tree cmp_rhs
, cmp_lhs
;
1419 last
= last_stmt (exit_edge
->src
);
1422 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1426 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1427 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1428 if (!TREE_CONSTANT (cmp_rhs
)
1429 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1431 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1434 /* If check_value_one is true, only the phi_args with value '1' will lead
1435 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1437 check_value_one
= (((integer_onep (cmp_rhs
))
1438 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1439 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1441 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1445 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1449 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1453 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1454 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1456 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1458 if ((check_value_one
^ integer_onep (val
)) == 1)
1460 if (EDGE_COUNT (e
->src
->succs
) != 1)
1462 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1466 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1467 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1471 /* Predict edge probabilities by exploiting loop structure. */
1474 predict_loops (void)
1478 /* Try to predict out blocks in a loop that are not part of a
1480 FOR_EACH_LOOP (loop
, 0)
1482 basic_block bb
, *bbs
;
1483 unsigned j
, n_exits
;
1485 struct tree_niter_desc niter_desc
;
1487 struct nb_iter_bound
*nb_iter
;
1488 enum tree_code loop_bound_code
= ERROR_MARK
;
1489 tree loop_bound_step
= NULL
;
1490 tree loop_bound_var
= NULL
;
1491 tree loop_iv_base
= NULL
;
1494 exits
= get_loop_exit_edges (loop
);
1495 n_exits
= exits
.length ();
1502 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1505 HOST_WIDE_INT nitercst
;
1506 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1508 enum br_predictor predictor
;
1510 predict_extra_loop_exits (ex
);
1512 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1513 niter
= niter_desc
.niter
;
1514 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1515 niter
= loop_niter_by_eval (loop
, ex
);
1517 if (TREE_CODE (niter
) == INTEGER_CST
)
1519 if (tree_fits_uhwi_p (niter
)
1521 && compare_tree_int (niter
, max
- 1) == -1)
1522 nitercst
= tree_to_uhwi (niter
) + 1;
1525 predictor
= PRED_LOOP_ITERATIONS
;
1527 /* If we have just one exit and we can derive some information about
1528 the number of iterations of the loop from the statements inside
1529 the loop, use it to predict this exit. */
1530 else if (n_exits
== 1)
1532 nitercst
= estimated_stmt_executions_int (loop
);
1538 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1543 /* If the prediction for number of iterations is zero, do not
1544 predict the exit edges. */
1548 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1549 predict_edge (ex
, predictor
, probability
);
1553 /* Find information about loop bound variables. */
1554 for (nb_iter
= loop
->bounds
; nb_iter
;
1555 nb_iter
= nb_iter
->next
)
1557 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1559 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1562 if (!stmt
&& last_stmt (loop
->header
)
1563 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1564 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1566 is_comparison_with_loop_invariant_p (stmt
, loop
,
1572 bbs
= get_loop_body (loop
);
1574 for (j
= 0; j
< loop
->num_nodes
; j
++)
1576 int header_found
= 0;
1582 /* Bypass loop heuristics on continue statement. These
1583 statements construct loops via "non-loop" constructs
1584 in the source language and are better to be handled
1586 if (predicted_by_p (bb
, PRED_CONTINUE
))
1589 /* Loop branch heuristics - predict an edge back to a
1590 loop's head as taken. */
1591 if (bb
== loop
->latch
)
1593 e
= find_edge (loop
->latch
, loop
->header
);
1597 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1601 /* Loop exit heuristics - predict an edge exiting the loop if the
1602 conditional has no loop header successors as not taken. */
1604 /* If we already used more reliable loop exit predictors, do not
1605 bother with PRED_LOOP_EXIT. */
1606 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1607 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1609 /* For loop with many exits we don't want to predict all exits
1610 with the pretty large probability, because if all exits are
1611 considered in row, the loop would be predicted to iterate
1612 almost never. The code to divide probability by number of
1613 exits is very rough. It should compute the number of exits
1614 taken in each patch through function (not the overall number
1615 of exits that might be a lot higher for loops with wide switch
1616 statements in them) and compute n-th square root.
1618 We limit the minimal probability by 2% to avoid
1619 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1620 as this was causing regression in perl benchmark containing such
1623 int probability
= ((REG_BR_PROB_BASE
1624 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1626 if (probability
< HITRATE (2))
1627 probability
= HITRATE (2);
1628 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1629 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1630 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1631 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1634 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1636 tree_to_shwi (loop_bound_step
));
1639 /* Free basic blocks from get_loop_body. */
1644 /* Attempt to predict probabilities of BB outgoing edges using local
1647 bb_estimate_probability_locally (basic_block bb
)
1649 rtx_insn
*last_insn
= BB_END (bb
);
1652 if (! can_predict_insn_p (last_insn
))
1654 cond
= get_condition (last_insn
, NULL
, false, false);
1658 /* Try "pointer heuristic."
1659 A comparison ptr == 0 is predicted as false.
1660 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1661 if (COMPARISON_P (cond
)
1662 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1663 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1665 if (GET_CODE (cond
) == EQ
)
1666 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1667 else if (GET_CODE (cond
) == NE
)
1668 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1672 /* Try "opcode heuristic."
1673 EQ tests are usually false and NE tests are usually true. Also,
1674 most quantities are positive, so we can make the appropriate guesses
1675 about signed comparisons against zero. */
1676 switch (GET_CODE (cond
))
1679 /* Unconditional branch. */
1680 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1681 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1686 /* Floating point comparisons appears to behave in a very
1687 unpredictable way because of special role of = tests in
1689 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1691 /* Comparisons with 0 are often used for booleans and there is
1692 nothing useful to predict about them. */
1693 else if (XEXP (cond
, 1) == const0_rtx
1694 || XEXP (cond
, 0) == const0_rtx
)
1697 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1702 /* Floating point comparisons appears to behave in a very
1703 unpredictable way because of special role of = tests in
1705 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1707 /* Comparisons with 0 are often used for booleans and there is
1708 nothing useful to predict about them. */
1709 else if (XEXP (cond
, 1) == const0_rtx
1710 || XEXP (cond
, 0) == const0_rtx
)
1713 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1717 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1721 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1726 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1727 || XEXP (cond
, 1) == constm1_rtx
)
1728 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1733 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1734 || XEXP (cond
, 1) == constm1_rtx
)
1735 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1743 /* Set edge->probability for each successor edge of BB. */
1745 guess_outgoing_edge_probabilities (basic_block bb
)
1747 bb_estimate_probability_locally (bb
);
1748 combine_predictions_for_insn (BB_END (bb
), bb
);
1751 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
1753 /* Helper function for expr_expected_value. */
1756 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1757 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
1762 *predictor
= PRED_UNCONDITIONAL
;
1764 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1766 if (TREE_CONSTANT (op0
))
1769 if (code
!= SSA_NAME
)
1772 def
= SSA_NAME_DEF_STMT (op0
);
1774 /* If we were already here, break the infinite cycle. */
1775 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1778 if (gimple_code (def
) == GIMPLE_PHI
)
1780 /* All the arguments of the PHI node must have the same constant
1782 int i
, n
= gimple_phi_num_args (def
);
1783 tree val
= NULL
, new_val
;
1785 for (i
= 0; i
< n
; i
++)
1787 tree arg
= PHI_ARG_DEF (def
, i
);
1788 enum br_predictor predictor2
;
1790 /* If this PHI has itself as an argument, we cannot
1791 determine the string length of this argument. However,
1792 if we can find an expected constant value for the other
1793 PHI args then we can still be sure that this is
1794 likely a constant. So be optimistic and just
1795 continue with the next argument. */
1796 if (arg
== PHI_RESULT (def
))
1799 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
1801 /* It is difficult to combine value predictors. Simply assume
1802 that later predictor is weaker and take its prediction. */
1803 if (predictor
&& *predictor
< predictor2
)
1804 *predictor
= predictor2
;
1809 else if (!operand_equal_p (val
, new_val
, false))
1814 if (is_gimple_assign (def
))
1816 if (gimple_assign_lhs (def
) != op0
)
1819 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1820 gimple_assign_rhs1 (def
),
1821 gimple_assign_rhs_code (def
),
1822 gimple_assign_rhs2 (def
),
1823 visited
, predictor
);
1826 if (is_gimple_call (def
))
1828 tree decl
= gimple_call_fndecl (def
);
1831 if (gimple_call_internal_p (def
)
1832 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
1834 gcc_assert (gimple_call_num_args (def
) == 3);
1835 tree val
= gimple_call_arg (def
, 0);
1836 if (TREE_CONSTANT (val
))
1840 tree val2
= gimple_call_arg (def
, 2);
1841 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
1842 && tree_fits_uhwi_p (val2
)
1843 && tree_to_uhwi (val2
) < END_PREDICTORS
);
1844 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
1846 return gimple_call_arg (def
, 1);
1850 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1851 switch (DECL_FUNCTION_CODE (decl
))
1853 case BUILT_IN_EXPECT
:
1856 if (gimple_call_num_args (def
) != 2)
1858 val
= gimple_call_arg (def
, 0);
1859 if (TREE_CONSTANT (val
))
1862 *predictor
= PRED_BUILTIN_EXPECT
;
1863 return gimple_call_arg (def
, 1);
1866 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1867 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1868 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1869 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1870 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1871 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1872 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1873 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1874 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1875 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1876 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1877 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1878 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1879 /* Assume that any given atomic operation has low contention,
1880 and thus the compare-and-swap operation succeeds. */
1882 *predictor
= PRED_COMPARE_AND_SWAP
;
1883 return boolean_true_node
;
1892 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1895 enum br_predictor predictor2
;
1896 op0
= expr_expected_value (op0
, visited
, predictor
);
1899 op1
= expr_expected_value (op1
, visited
, &predictor2
);
1900 if (predictor
&& *predictor
< predictor2
)
1901 *predictor
= predictor2
;
1904 res
= fold_build2 (code
, type
, op0
, op1
);
1905 if (TREE_CONSTANT (res
))
1909 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1912 op0
= expr_expected_value (op0
, visited
, predictor
);
1915 res
= fold_build1 (code
, type
, op0
);
1916 if (TREE_CONSTANT (res
))
1923 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1924 The function is used by builtin_expect branch predictor so the evidence
1925 must come from this construct and additional possible constant folding.
1927 We may want to implement more involved value guess (such as value range
1928 propagation based prediction), but such tricks shall go to new
1932 expr_expected_value (tree expr
, bitmap visited
,
1933 enum br_predictor
*predictor
)
1935 enum tree_code code
;
1938 if (TREE_CONSTANT (expr
))
1941 *predictor
= PRED_UNCONDITIONAL
;
1945 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1946 return expr_expected_value_1 (TREE_TYPE (expr
),
1947 op0
, code
, op1
, visited
, predictor
);
1950 /* Predict using opcode of the last statement in basic block. */
1952 tree_predict_by_opcode (basic_block bb
)
1954 gimple stmt
= last_stmt (bb
);
1962 enum br_predictor predictor
;
1964 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1966 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1967 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1969 op0
= gimple_cond_lhs (stmt
);
1970 op1
= gimple_cond_rhs (stmt
);
1971 cmp
= gimple_cond_code (stmt
);
1972 type
= TREE_TYPE (op0
);
1973 visited
= BITMAP_ALLOC (NULL
);
1974 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
1976 BITMAP_FREE (visited
);
1977 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
1979 if (predictor
== PRED_BUILTIN_EXPECT
)
1981 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
1983 gcc_assert (percent
>= 0 && percent
<= 100);
1984 if (integer_zerop (val
))
1985 percent
= 100 - percent
;
1986 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
1989 predict_edge (then_edge
, predictor
,
1990 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
1992 /* Try "pointer heuristic."
1993 A comparison ptr == 0 is predicted as false.
1994 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1995 if (POINTER_TYPE_P (type
))
1998 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1999 else if (cmp
== NE_EXPR
)
2000 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2004 /* Try "opcode heuristic."
2005 EQ tests are usually false and NE tests are usually true. Also,
2006 most quantities are positive, so we can make the appropriate guesses
2007 about signed comparisons against zero. */
2012 /* Floating point comparisons appears to behave in a very
2013 unpredictable way because of special role of = tests in
2015 if (FLOAT_TYPE_P (type
))
2017 /* Comparisons with 0 are often used for booleans and there is
2018 nothing useful to predict about them. */
2019 else if (integer_zerop (op0
) || integer_zerop (op1
))
2022 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2027 /* Floating point comparisons appears to behave in a very
2028 unpredictable way because of special role of = tests in
2030 if (FLOAT_TYPE_P (type
))
2032 /* Comparisons with 0 are often used for booleans and there is
2033 nothing useful to predict about them. */
2034 else if (integer_zerop (op0
)
2035 || integer_zerop (op1
))
2038 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2042 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2045 case UNORDERED_EXPR
:
2046 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2051 if (integer_zerop (op1
)
2052 || integer_onep (op1
)
2053 || integer_all_onesp (op1
)
2056 || real_minus_onep (op1
))
2057 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2062 if (integer_zerop (op1
)
2063 || integer_onep (op1
)
2064 || integer_all_onesp (op1
)
2067 || real_minus_onep (op1
))
2068 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2076 /* Try to guess whether the value of return means error code. */
2078 static enum br_predictor
2079 return_prediction (tree val
, enum prediction
*prediction
)
2083 return PRED_NO_PREDICTION
;
2084 /* Different heuristics for pointers and scalars. */
2085 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2087 /* NULL is usually not returned. */
2088 if (integer_zerop (val
))
2090 *prediction
= NOT_TAKEN
;
2091 return PRED_NULL_RETURN
;
2094 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2096 /* Negative return values are often used to indicate
2098 if (TREE_CODE (val
) == INTEGER_CST
2099 && tree_int_cst_sgn (val
) < 0)
2101 *prediction
= NOT_TAKEN
;
2102 return PRED_NEGATIVE_RETURN
;
2104 /* Constant return values seems to be commonly taken.
2105 Zero/one often represent booleans so exclude them from the
2107 if (TREE_CONSTANT (val
)
2108 && (!integer_zerop (val
) && !integer_onep (val
)))
2110 *prediction
= TAKEN
;
2111 return PRED_CONST_RETURN
;
2114 return PRED_NO_PREDICTION
;
2117 /* Find the basic block with return expression and look up for possible
2118 return value trying to apply RETURN_PREDICTION heuristics. */
2120 apply_return_prediction (void)
2122 greturn
*return_stmt
= NULL
;
2126 int phi_num_args
, i
;
2127 enum br_predictor pred
;
2128 enum prediction direction
;
2131 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2133 gimple last
= last_stmt (e
->src
);
2135 && gimple_code (last
) == GIMPLE_RETURN
)
2137 return_stmt
= as_a
<greturn
*> (last
);
2143 return_val
= gimple_return_retval (return_stmt
);
2146 if (TREE_CODE (return_val
) != SSA_NAME
2147 || !SSA_NAME_DEF_STMT (return_val
)
2148 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2150 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2151 phi_num_args
= gimple_phi_num_args (phi
);
2152 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2154 /* Avoid the degenerate case where all return values form the function
2155 belongs to same category (ie they are all positive constants)
2156 so we can hardly say something about them. */
2157 for (i
= 1; i
< phi_num_args
; i
++)
2158 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2160 if (i
!= phi_num_args
)
2161 for (i
= 0; i
< phi_num_args
; i
++)
2163 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2164 if (pred
!= PRED_NO_PREDICTION
)
2165 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2170 /* Look for basic block that contains unlikely to happen events
2171 (such as noreturn calls) and mark all paths leading to execution
2172 of this basic blocks as unlikely. */
2175 tree_bb_level_predictions (void)
2178 bool has_return_edges
= false;
2182 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2183 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2185 has_return_edges
= true;
2189 apply_return_prediction ();
2191 FOR_EACH_BB_FN (bb
, cfun
)
2193 gimple_stmt_iterator gsi
;
2195 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2197 gimple stmt
= gsi_stmt (gsi
);
2200 if (is_gimple_call (stmt
))
2202 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2203 && has_return_edges
)
2204 predict_paths_leading_to (bb
, PRED_NORETURN
,
2206 decl
= gimple_call_fndecl (stmt
);
2208 && lookup_attribute ("cold",
2209 DECL_ATTRIBUTES (decl
)))
2210 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2213 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2215 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2216 gimple_predict_outcome (stmt
));
2217 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2218 hints to callers. */
2224 #ifdef ENABLE_CHECKING
2226 /* Callback for hash_map::traverse, asserts that the pointer map is
2230 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2233 gcc_assert (!value
);
2238 /* Predict branch probabilities and estimate profile for basic block BB. */
2241 tree_estimate_probability_bb (basic_block bb
)
2247 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2249 /* Predict edges to user labels with attributes. */
2250 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2252 gimple_stmt_iterator gi
;
2253 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2255 glabel
*label_stmt
= dyn_cast
<glabel
*> (gsi_stmt (gi
));
2260 decl
= gimple_label_label (label_stmt
);
2261 if (DECL_ARTIFICIAL (decl
))
2264 /* Finally, we have a user-defined label. */
2265 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2266 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2267 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2268 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2272 /* Predict early returns to be probable, as we've already taken
2273 care for error returns and other cases are often used for
2274 fast paths through function.
2276 Since we've already removed the return statements, we are
2277 looking for CFG like:
2287 if (e
->dest
!= bb
->next_bb
2288 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2289 && single_succ_p (e
->dest
)
2290 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2291 && (last
= last_stmt (e
->dest
)) != NULL
2292 && gimple_code (last
) == GIMPLE_RETURN
)
2297 if (single_succ_p (bb
))
2299 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2300 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2301 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2302 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2303 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2306 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2307 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2308 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2309 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2312 /* Look for block we are guarding (ie we dominate it,
2313 but it doesn't postdominate us). */
2314 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2315 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2316 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2318 gimple_stmt_iterator bi
;
2320 /* The call heuristic claims that a guarded function call
2321 is improbable. This is because such calls are often used
2322 to signal exceptional situations such as printing error
2324 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2327 gimple stmt
= gsi_stmt (bi
);
2328 if (is_gimple_call (stmt
)
2329 /* Constant and pure calls are hardly used to signalize
2330 something exceptional. */
2331 && gimple_has_side_effects (stmt
))
2333 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2339 tree_predict_by_opcode (bb
);
2342 /* Predict branch probabilities and estimate profile of the tree CFG.
2343 This function can be called from the loop optimizers to recompute
2344 the profile information. */
2347 tree_estimate_probability (void)
2351 add_noreturn_fake_exit_edges ();
2352 connect_infinite_loops_to_exit ();
2353 /* We use loop_niter_by_eval, which requires that the loops have
2355 create_preheaders (CP_SIMPLE_PREHEADERS
);
2356 calculate_dominance_info (CDI_POST_DOMINATORS
);
2358 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2359 tree_bb_level_predictions ();
2360 record_loop_exits ();
2362 if (number_of_loops (cfun
) > 1)
2365 FOR_EACH_BB_FN (bb
, cfun
)
2366 tree_estimate_probability_bb (bb
);
2368 FOR_EACH_BB_FN (bb
, cfun
)
2369 combine_predictions_for_bb (bb
);
2371 #ifdef ENABLE_CHECKING
2372 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2374 delete bb_predictions
;
2375 bb_predictions
= NULL
;
2377 estimate_bb_frequencies (false);
2378 free_dominance_info (CDI_POST_DOMINATORS
);
2379 remove_fake_exit_edges ();
2382 /* Predict edges to successors of CUR whose sources are not postdominated by
2383 BB by PRED and recurse to all postdominators. */
2386 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2387 enum br_predictor pred
,
2388 enum prediction taken
,
2395 /* We are looking for all edges forming edge cut induced by
2396 set of all blocks postdominated by BB. */
2397 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2398 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2399 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2405 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2406 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2408 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2410 /* See if there is an edge from e->src that is not abnormal
2411 and does not lead to BB. */
2412 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2414 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2415 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2421 /* If there is non-abnormal path leaving e->src, predict edge
2422 using predictor. Otherwise we need to look for paths
2425 The second may lead to infinite loop in the case we are predicitng
2426 regions that are only reachable by abnormal edges. We simply
2427 prevent visiting given BB twice. */
2429 predict_edge_def (e
, pred
, taken
);
2430 else if (bitmap_set_bit (visited
, e
->src
->index
))
2431 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2433 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2435 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2436 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2439 /* Sets branch probabilities according to PREDiction and
2443 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2444 enum prediction taken
)
2446 bitmap visited
= BITMAP_ALLOC (NULL
);
2447 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2448 BITMAP_FREE (visited
);
2451 /* Like predict_paths_leading_to but take edge instead of basic block. */
2454 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2455 enum prediction taken
)
2457 bool has_nonloop_edge
= false;
2461 basic_block bb
= e
->src
;
2462 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2463 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2464 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2465 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2467 has_nonloop_edge
= true;
2470 if (!has_nonloop_edge
)
2472 bitmap visited
= BITMAP_ALLOC (NULL
);
2473 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2474 BITMAP_FREE (visited
);
2477 predict_edge_def (e
, pred
, taken
);
2480 /* This is used to carry information about basic blocks. It is
2481 attached to the AUX field of the standard CFG block. */
2485 /* Estimated frequency of execution of basic_block. */
2488 /* To keep queue of basic blocks to process. */
2491 /* Number of predecessors we need to visit first. */
2495 /* Similar information for edges. */
2496 struct edge_prob_info
2498 /* In case edge is a loopback edge, the probability edge will be reached
2499 in case header is. Estimated number of iterations of the loop can be
2500 then computed as 1 / (1 - back_edge_prob). */
2501 sreal back_edge_prob
;
2502 /* True if the edge is a loopback edge in the natural loop. */
2503 unsigned int back_edge
:1;
2506 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2508 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2510 /* Helper function for estimate_bb_frequencies.
2511 Propagate the frequencies in blocks marked in
2512 TOVISIT, starting in HEAD. */
2515 propagate_freq (basic_block head
, bitmap tovisit
)
2524 /* For each basic block we need to visit count number of his predecessors
2525 we need to visit first. */
2526 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2531 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2533 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2535 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2537 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2539 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2541 "Irreducible region hit, ignoring edge to %i->%i\n",
2542 e
->src
->index
, bb
->index
);
2544 BLOCK_INFO (bb
)->npredecessors
= count
;
2545 /* When function never returns, we will never process exit block. */
2546 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2547 bb
->count
= bb
->frequency
= 0;
2550 BLOCK_INFO (head
)->frequency
= 1;
2552 for (bb
= head
; bb
; bb
= nextbb
)
2555 sreal cyclic_probability
= 0;
2556 sreal frequency
= 0;
2558 nextbb
= BLOCK_INFO (bb
)->next
;
2559 BLOCK_INFO (bb
)->next
= NULL
;
2561 /* Compute frequency of basic block. */
2564 #ifdef ENABLE_CHECKING
2565 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2566 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2567 || (e
->flags
& EDGE_DFS_BACK
));
2570 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2571 if (EDGE_INFO (e
)->back_edge
)
2573 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
2575 else if (!(e
->flags
& EDGE_DFS_BACK
))
2577 /* frequency += (e->probability
2578 * BLOCK_INFO (e->src)->frequency /
2579 REG_BR_PROB_BASE); */
2581 sreal tmp
= e
->probability
;
2582 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
2583 tmp
*= real_inv_br_prob_base
;
2587 if (cyclic_probability
== 0)
2589 BLOCK_INFO (bb
)->frequency
= frequency
;
2593 if (cyclic_probability
> real_almost_one
)
2594 cyclic_probability
= real_almost_one
;
2596 /* BLOCK_INFO (bb)->frequency = frequency
2597 / (1 - cyclic_probability) */
2599 cyclic_probability
= sreal (1) - cyclic_probability
;
2600 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
2604 bitmap_clear_bit (tovisit
, bb
->index
);
2606 e
= find_edge (bb
, head
);
2609 /* EDGE_INFO (e)->back_edge_prob
2610 = ((e->probability * BLOCK_INFO (bb)->frequency)
2611 / REG_BR_PROB_BASE); */
2613 sreal tmp
= e
->probability
;
2614 tmp
*= BLOCK_INFO (bb
)->frequency
;
2615 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
2618 /* Propagate to successor blocks. */
2619 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2620 if (!(e
->flags
& EDGE_DFS_BACK
)
2621 && BLOCK_INFO (e
->dest
)->npredecessors
)
2623 BLOCK_INFO (e
->dest
)->npredecessors
--;
2624 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2629 BLOCK_INFO (last
)->next
= e
->dest
;
2637 /* Estimate frequencies in loops at same nest level. */
2640 estimate_loops_at_level (struct loop
*first_loop
)
2644 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2649 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2651 estimate_loops_at_level (loop
->inner
);
2653 /* Find current loop back edge and mark it. */
2654 e
= loop_latch_edge (loop
);
2655 EDGE_INFO (e
)->back_edge
= 1;
2657 bbs
= get_loop_body (loop
);
2658 for (i
= 0; i
< loop
->num_nodes
; i
++)
2659 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2661 propagate_freq (loop
->header
, tovisit
);
2662 BITMAP_FREE (tovisit
);
2666 /* Propagates frequencies through structure of loops. */
2669 estimate_loops (void)
2671 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2674 /* Start by estimating the frequencies in the loops. */
2675 if (number_of_loops (cfun
) > 1)
2676 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2678 /* Now propagate the frequencies through all the blocks. */
2679 FOR_ALL_BB_FN (bb
, cfun
)
2681 bitmap_set_bit (tovisit
, bb
->index
);
2683 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
2684 BITMAP_FREE (tovisit
);
2687 /* Drop the profile for NODE to guessed, and update its frequency based on
2688 whether it is expected to be hot given the CALL_COUNT. */
2691 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
2693 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2694 /* In the case where this was called by another function with a
2695 dropped profile, call_count will be 0. Since there are no
2696 non-zero call counts to this function, we don't know for sure
2697 whether it is hot, and therefore it will be marked normal below. */
2698 bool hot
= maybe_hot_count_p (NULL
, call_count
);
2702 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2703 node
->name (), node
->order
,
2704 hot
? "Function is hot" : "Function is normal");
2705 /* We only expect to miss profiles for functions that are reached
2706 via non-zero call edges in cases where the function may have
2707 been linked from another module or library (COMDATs and extern
2708 templates). See the comments below for handle_missing_profiles.
2709 Also, only warn in cases where the missing counts exceed the
2710 number of training runs. In certain cases with an execv followed
2711 by a no-return call the profile for the no-return call is not
2712 dumped and there can be a mismatch. */
2713 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
2714 && call_count
> profile_info
->runs
)
2716 if (flag_profile_correction
)
2720 "Missing counts for called function %s/%i\n",
2721 node
->name (), node
->order
);
2724 warning (0, "Missing counts for called function %s/%i",
2725 node
->name (), node
->order
);
2728 profile_status_for_fn (fn
)
2729 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2731 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2734 /* In the case of COMDAT routines, multiple object files will contain the same
2735 function and the linker will select one for the binary. In that case
2736 all the other copies from the profile instrument binary will be missing
2737 profile counts. Look for cases where this happened, due to non-zero
2738 call counts going to 0-count functions, and drop the profile to guessed
2739 so that we can use the estimated probabilities and avoid optimizing only
2742 The other case where the profile may be missing is when the routine
2743 is not going to be emitted to the object file, e.g. for "extern template"
2744 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2745 all other cases of non-zero calls to 0-count functions. */
2748 handle_missing_profiles (void)
2750 struct cgraph_node
*node
;
2751 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2752 vec
<struct cgraph_node
*> worklist
;
2753 worklist
.create (64);
2755 /* See if 0 count function has non-0 count callers. In this case we
2756 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2757 FOR_EACH_DEFINED_FUNCTION (node
)
2759 struct cgraph_edge
*e
;
2760 gcov_type call_count
= 0;
2761 gcov_type max_tp_first_run
= 0;
2762 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2766 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2768 call_count
+= e
->count
;
2770 if (e
->caller
->tp_first_run
> max_tp_first_run
)
2771 max_tp_first_run
= e
->caller
->tp_first_run
;
2774 /* If time profile is missing, let assign the maximum that comes from
2775 caller functions. */
2776 if (!node
->tp_first_run
&& max_tp_first_run
)
2777 node
->tp_first_run
= max_tp_first_run
+ 1;
2781 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2783 drop_profile (node
, call_count
);
2784 worklist
.safe_push (node
);
2788 /* Propagate the profile dropping to other 0-count COMDATs that are
2789 potentially called by COMDATs we already dropped the profile on. */
2790 while (worklist
.length () > 0)
2792 struct cgraph_edge
*e
;
2794 node
= worklist
.pop ();
2795 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2797 struct cgraph_node
*callee
= e
->callee
;
2798 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2800 if (callee
->count
> 0)
2802 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2803 && profile_status_for_fn (fn
) == PROFILE_READ
)
2805 drop_profile (node
, 0);
2806 worklist
.safe_push (callee
);
2810 worklist
.release ();
2813 /* Convert counts measured by profile driven feedback to frequencies.
2814 Return nonzero iff there was any nonzero execution count. */
2817 counts_to_freqs (void)
2819 gcov_type count_max
, true_count_max
= 0;
2822 /* Don't overwrite the estimated frequencies when the profile for
2823 the function is missing. We may drop this function PROFILE_GUESSED
2824 later in drop_profile (). */
2825 if (!flag_auto_profile
&& !ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
2828 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2829 true_count_max
= MAX (bb
->count
, true_count_max
);
2831 count_max
= MAX (true_count_max
, 1);
2832 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2833 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2835 return true_count_max
;
2838 /* Return true if function is likely to be expensive, so there is no point to
2839 optimize performance of prologue, epilogue or do inlining at the expense
2840 of code size growth. THRESHOLD is the limit of number of instructions
2841 function can execute at average to be still considered not expensive. */
2844 expensive_function_p (int threshold
)
2846 unsigned int sum
= 0;
2850 /* We can not compute accurately for large thresholds due to scaled
2852 gcc_assert (threshold
<= BB_FREQ_MAX
);
2854 /* Frequencies are out of range. This either means that function contains
2855 internal loop executing more than BB_FREQ_MAX times or profile feedback
2856 is available and function has not been executed at all. */
2857 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
2860 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2861 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
2862 FOR_EACH_BB_FN (bb
, cfun
)
2866 FOR_BB_INSNS (bb
, insn
)
2867 if (active_insn_p (insn
))
2869 sum
+= bb
->frequency
;
2878 /* Estimate and propagate basic block frequencies using the given branch
2879 probabilities. If FORCE is true, the frequencies are used to estimate
2880 the counts even when there are already non-zero profile counts. */
2883 estimate_bb_frequencies (bool force
)
2888 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
2890 static int real_values_initialized
= 0;
2892 if (!real_values_initialized
)
2894 real_values_initialized
= 1;
2895 real_br_prob_base
= REG_BR_PROB_BASE
;
2896 real_bb_freq_max
= BB_FREQ_MAX
;
2897 real_one_half
= sreal (1, -1);
2898 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
2899 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
2902 mark_dfs_back_edges ();
2904 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
2907 /* Set up block info for each basic block. */
2908 alloc_aux_for_blocks (sizeof (block_info
));
2909 alloc_aux_for_edges (sizeof (edge_prob_info
));
2910 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2915 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2917 EDGE_INFO (e
)->back_edge_prob
= e
->probability
;
2918 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
2922 /* First compute frequencies locally for each loop from innermost
2923 to outermost to examine frequencies for back edges. */
2927 FOR_EACH_BB_FN (bb
, cfun
)
2928 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
2929 freq_max
= BLOCK_INFO (bb
)->frequency
;
2931 freq_max
= real_bb_freq_max
/ freq_max
;
2932 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2934 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
2935 bb
->frequency
= tmp
.to_int ();
2938 free_aux_for_blocks ();
2939 free_aux_for_edges ();
2941 compute_function_frequency ();
2944 /* Decide whether function is hot, cold or unlikely executed. */
2946 compute_function_frequency (void)
2949 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2951 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2952 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2953 node
->only_called_at_startup
= true;
2954 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
2955 node
->only_called_at_exit
= true;
2957 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
2959 int flags
= flags_from_decl_or_type (current_function_decl
);
2960 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2962 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2963 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
2965 node
->frequency
= NODE_FREQUENCY_HOT
;
2966 else if (flags
& ECF_NORETURN
)
2967 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2968 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2969 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2970 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2971 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
2972 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2976 /* Only first time try to drop function into unlikely executed.
2977 After inlining the roundoff errors may confuse us.
2978 Ipa-profile pass will drop functions only called from unlikely
2979 functions to unlikely and that is most of what we care about. */
2980 if (!cfun
->after_inlining
)
2981 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2982 FOR_EACH_BB_FN (bb
, cfun
)
2984 if (maybe_hot_bb_p (cfun
, bb
))
2986 node
->frequency
= NODE_FREQUENCY_HOT
;
2989 if (!probably_never_executed_bb_p (cfun
, bb
))
2990 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2994 /* Build PREDICT_EXPR. */
2996 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
2998 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
2999 build_int_cst (integer_type_node
, predictor
));
3000 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3005 predictor_name (enum br_predictor predictor
)
3007 return predictor_info
[predictor
].name
;
3010 /* Predict branch probabilities and estimate profile of the tree CFG. */
3014 const pass_data pass_data_profile
=
3016 GIMPLE_PASS
, /* type */
3017 "profile_estimate", /* name */
3018 OPTGROUP_NONE
, /* optinfo_flags */
3019 TV_BRANCH_PROB
, /* tv_id */
3020 PROP_cfg
, /* properties_required */
3021 0, /* properties_provided */
3022 0, /* properties_destroyed */
3023 0, /* todo_flags_start */
3024 0, /* todo_flags_finish */
3027 class pass_profile
: public gimple_opt_pass
3030 pass_profile (gcc::context
*ctxt
)
3031 : gimple_opt_pass (pass_data_profile
, ctxt
)
3034 /* opt_pass methods: */
3035 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3036 virtual unsigned int execute (function
*);
3038 }; // class pass_profile
3041 pass_profile::execute (function
*fun
)
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
);