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"
39 #include "basic-block.h"
40 #include "insn-config.h"
45 #include "diagnostic-core.h"
55 #include "tree-ssa-alias.h"
56 #include "internal-fn.h"
57 #include "gimple-expr.h"
60 #include "gimple-iterator.h"
61 #include "gimple-ssa.h"
64 #include "tree-phinodes.h"
65 #include "ssa-iterators.h"
66 #include "tree-ssa-loop-niter.h"
67 #include "tree-ssa-loop.h"
68 #include "tree-pass.h"
69 #include "tree-scalar-evolution.h"
72 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
73 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
74 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
75 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
77 static void combine_predictions_for_insn (rtx
, basic_block
);
78 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
79 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
80 static void predict_paths_leading_to_edge (edge
, enum br_predictor
, enum prediction
);
81 static bool can_predict_insn_p (const_rtx
);
83 /* Information we hold about each branch predictor.
84 Filled using information from predict.def. */
88 const char *const name
; /* Name used in the debugging dumps. */
89 const int hitrate
; /* Expected hitrate used by
90 predict_insn_def call. */
94 /* Use given predictor without Dempster-Shaffer theory if it matches
95 using first_match heuristics. */
96 #define PRED_FLAG_FIRST_MATCH 1
98 /* Recompute hitrate in percent to our representation. */
100 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
102 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
103 static const struct predictor_info predictor_info
[]= {
104 #include "predict.def"
106 /* Upper bound on predictors. */
111 /* Return TRUE if frequency FREQ is considered to be hot. */
114 maybe_hot_frequency_p (struct function
*fun
, int freq
)
116 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
117 if (!profile_info
|| !flag_branch_probabilities
)
119 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
121 if (node
->frequency
== NODE_FREQUENCY_HOT
)
124 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
126 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
127 && freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
* 2 / 3))
129 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
131 if (freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
132 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
137 static gcov_type min_count
= -1;
139 /* Determine the threshold for hot BB counts. */
142 get_hot_bb_threshold ()
144 gcov_working_set_t
*ws
;
147 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
149 min_count
= ws
->min_counter
;
154 /* Set the threshold for hot BB counts. */
157 set_hot_bb_threshold (gcov_type min
)
162 /* Return TRUE if frequency FREQ is considered to be hot. */
165 maybe_hot_count_p (struct function
*fun
, gcov_type count
)
167 if (fun
&& profile_status_for_fn (fun
) != PROFILE_READ
)
169 /* Code executed at most once is not hot. */
170 if (profile_info
->runs
>= count
)
172 return (count
>= get_hot_bb_threshold ());
175 /* Return true in case BB can be CPU intensive and should be optimized
176 for maximal performance. */
179 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
181 gcc_checking_assert (fun
);
182 if (profile_status_for_fn (fun
) == PROFILE_READ
)
183 return maybe_hot_count_p (fun
, bb
->count
);
184 return maybe_hot_frequency_p (fun
, bb
->frequency
);
187 /* Return true if the call can be hot. */
190 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
192 if (profile_info
&& flag_branch_probabilities
193 && !maybe_hot_count_p (NULL
,
196 if (edge
->caller
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
198 && edge
->callee
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
200 if (edge
->caller
->frequency
> NODE_FREQUENCY_UNLIKELY_EXECUTED
202 && edge
->callee
->frequency
<= NODE_FREQUENCY_EXECUTED_ONCE
))
206 if (edge
->caller
->frequency
== NODE_FREQUENCY_HOT
)
208 if (edge
->caller
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
209 && edge
->frequency
< CGRAPH_FREQ_BASE
* 3 / 2)
211 if (flag_guess_branch_prob
)
213 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0
214 || edge
->frequency
<= (CGRAPH_FREQ_BASE
215 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
221 /* Return true in case BB can be CPU intensive and should be optimized
222 for maximal performance. */
225 maybe_hot_edge_p (edge e
)
227 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
228 return maybe_hot_count_p (cfun
, e
->count
);
229 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
234 /* Return true if profile COUNT and FREQUENCY, or function FUN static
235 node frequency reflects never being executed. */
238 probably_never_executed (struct function
*fun
,
239 gcov_type count
, int frequency
)
241 gcc_checking_assert (fun
);
242 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
244 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
245 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
249 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
251 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
253 gcov_type computed_count
;
254 /* Check for possibility of overflow, in which case entry bb count
255 is large enough to do the division first without losing much
257 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
< REG_BR_PROB_BASE
*
260 gcov_type scaled_count
261 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
*
262 unlikely_count_fraction
;
263 computed_count
= RDIV (scaled_count
,
264 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
);
268 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
,
269 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
);
270 computed_count
*= frequency
* unlikely_count_fraction
;
272 if (computed_count
>= profile_info
->runs
)
277 if ((!profile_info
|| !flag_branch_probabilities
)
278 && (cgraph_node::get (fun
->decl
)->frequency
279 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
285 /* Return true in case BB is probably never executed. */
288 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
290 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
294 /* Return true in case edge E is probably never executed. */
297 probably_never_executed_edge_p (struct function
*fun
, edge e
)
299 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
302 /* Return true if function should be optimized for size. */
305 cgraph_node::optimize_for_size_p (void)
309 if (frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
315 /* Return true when current function should always be optimized for size. */
318 optimize_function_for_size_p (struct function
*fun
)
322 if (!fun
|| !fun
->decl
)
325 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
326 return n
&& n
->optimize_for_size_p ();
329 /* Return true when current function should always be optimized for speed. */
332 optimize_function_for_speed_p (struct function
*fun
)
334 return !optimize_function_for_size_p (fun
);
337 /* Return TRUE when BB should be optimized for size. */
340 optimize_bb_for_size_p (const_basic_block bb
)
342 return (optimize_function_for_size_p (cfun
)
343 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
346 /* Return TRUE when BB should be optimized for speed. */
349 optimize_bb_for_speed_p (const_basic_block bb
)
351 return !optimize_bb_for_size_p (bb
);
354 /* Return TRUE when BB should be optimized for size. */
357 optimize_edge_for_size_p (edge e
)
359 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
362 /* Return TRUE when BB should be optimized for speed. */
365 optimize_edge_for_speed_p (edge e
)
367 return !optimize_edge_for_size_p (e
);
370 /* Return TRUE when BB should be optimized for size. */
373 optimize_insn_for_size_p (void)
375 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
378 /* Return TRUE when BB should be optimized for speed. */
381 optimize_insn_for_speed_p (void)
383 return !optimize_insn_for_size_p ();
386 /* Return TRUE when LOOP should be optimized for size. */
389 optimize_loop_for_size_p (struct loop
*loop
)
391 return optimize_bb_for_size_p (loop
->header
);
394 /* Return TRUE when LOOP should be optimized for speed. */
397 optimize_loop_for_speed_p (struct loop
*loop
)
399 return optimize_bb_for_speed_p (loop
->header
);
402 /* Return TRUE when LOOP nest should be optimized for speed. */
405 optimize_loop_nest_for_speed_p (struct loop
*loop
)
407 struct loop
*l
= loop
;
408 if (optimize_loop_for_speed_p (loop
))
411 while (l
&& l
!= loop
)
413 if (optimize_loop_for_speed_p (l
))
421 while (l
!= loop
&& !l
->next
)
430 /* Return TRUE when LOOP nest should be optimized for size. */
433 optimize_loop_nest_for_size_p (struct loop
*loop
)
435 return !optimize_loop_nest_for_speed_p (loop
);
438 /* Return true when edge E is likely to be well predictable by branch
442 predictable_edge_p (edge e
)
444 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
447 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
448 || (REG_BR_PROB_BASE
- e
->probability
449 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
455 /* Set RTL expansion for BB profile. */
458 rtl_profile_for_bb (basic_block bb
)
460 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
463 /* Set RTL expansion for edge profile. */
466 rtl_profile_for_edge (edge e
)
468 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
471 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
473 default_rtl_profile (void)
475 crtl
->maybe_hot_insn_p
= true;
478 /* Return true if the one of outgoing edges is already predicted by
482 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
485 if (!INSN_P (BB_END (bb
)))
487 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
488 if (REG_NOTE_KIND (note
) == REG_BR_PRED
489 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
494 /* Structure representing predictions in tree level. */
496 struct edge_prediction
{
497 struct edge_prediction
*ep_next
;
499 enum br_predictor ep_predictor
;
503 /* This map contains for a basic block the list of predictions for the
506 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
508 /* Return true if the one of outgoing edges is already predicted by
512 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
514 struct edge_prediction
*i
;
515 edge_prediction
**preds
= bb_predictions
->get (bb
);
520 for (i
= *preds
; i
; i
= i
->ep_next
)
521 if (i
->ep_predictor
== predictor
)
526 /* Return true when the probability of edge is reliable.
528 The profile guessing code is good at predicting branch outcome (ie.
529 taken/not taken), that is predicted right slightly over 75% of time.
530 It is however notoriously poor on predicting the probability itself.
531 In general the profile appear a lot flatter (with probabilities closer
532 to 50%) than the reality so it is bad idea to use it to drive optimization
533 such as those disabling dynamic branch prediction for well predictable
536 There are two exceptions - edges leading to noreturn edges and edges
537 predicted by number of iterations heuristics are predicted well. This macro
538 should be able to distinguish those, but at the moment it simply check for
539 noreturn heuristic that is only one giving probability over 99% or bellow
540 1%. In future we might want to propagate reliability information across the
541 CFG if we find this information useful on multiple places. */
543 probability_reliable_p (int prob
)
545 return (profile_status_for_fn (cfun
) == PROFILE_READ
546 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
547 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
550 /* Same predicate as above, working on edges. */
552 edge_probability_reliable_p (const_edge e
)
554 return probability_reliable_p (e
->probability
);
557 /* Same predicate as edge_probability_reliable_p, working on notes. */
559 br_prob_note_reliable_p (const_rtx note
)
561 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
562 return probability_reliable_p (XINT (note
, 0));
566 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
568 gcc_assert (any_condjump_p (insn
));
569 if (!flag_guess_branch_prob
)
572 add_reg_note (insn
, REG_BR_PRED
,
573 gen_rtx_CONCAT (VOIDmode
,
574 GEN_INT ((int) predictor
),
575 GEN_INT ((int) probability
)));
578 /* Predict insn by given predictor. */
581 predict_insn_def (rtx insn
, enum br_predictor predictor
,
582 enum prediction taken
)
584 int probability
= predictor_info
[(int) predictor
].hitrate
;
587 probability
= REG_BR_PROB_BASE
- probability
;
589 predict_insn (insn
, predictor
, probability
);
592 /* Predict edge E with given probability if possible. */
595 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
598 last_insn
= BB_END (e
->src
);
600 /* We can store the branch prediction information only about
601 conditional jumps. */
602 if (!any_condjump_p (last_insn
))
605 /* We always store probability of branching. */
606 if (e
->flags
& EDGE_FALLTHRU
)
607 probability
= REG_BR_PROB_BASE
- probability
;
609 predict_insn (last_insn
, predictor
, probability
);
612 /* Predict edge E with the given PROBABILITY. */
614 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
616 gcc_assert (profile_status_for_fn (cfun
) != PROFILE_GUESSED
);
617 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && EDGE_COUNT (e
->src
->succs
) >
619 && flag_guess_branch_prob
&& optimize
)
621 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
622 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
626 i
->ep_probability
= probability
;
627 i
->ep_predictor
= predictor
;
632 /* Remove all predictions on given basic block that are attached
635 remove_predictions_associated_with_edge (edge e
)
640 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
644 struct edge_prediction
**prediction
= preds
;
645 struct edge_prediction
*next
;
649 if ((*prediction
)->ep_edge
== e
)
651 next
= (*prediction
)->ep_next
;
656 prediction
= &((*prediction
)->ep_next
);
661 /* Clears the list of predictions stored for BB. */
664 clear_bb_predictions (basic_block bb
)
666 edge_prediction
**preds
= bb_predictions
->get (bb
);
667 struct edge_prediction
*pred
, *next
;
672 for (pred
= *preds
; pred
; pred
= next
)
674 next
= pred
->ep_next
;
680 /* Return true when we can store prediction on insn INSN.
681 At the moment we represent predictions only on conditional
682 jumps, not at computed jump or other complicated cases. */
684 can_predict_insn_p (const_rtx insn
)
686 return (JUMP_P (insn
)
687 && any_condjump_p (insn
)
688 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
691 /* Predict edge E by given predictor if possible. */
694 predict_edge_def (edge e
, enum br_predictor predictor
,
695 enum prediction taken
)
697 int probability
= predictor_info
[(int) predictor
].hitrate
;
700 probability
= REG_BR_PROB_BASE
- probability
;
702 predict_edge (e
, predictor
, probability
);
705 /* Invert all branch predictions or probability notes in the INSN. This needs
706 to be done each time we invert the condition used by the jump. */
709 invert_br_probabilities (rtx insn
)
713 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
714 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
715 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
716 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
717 XEXP (XEXP (note
, 0), 1)
718 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
721 /* Dump information about the branch prediction to the output file. */
724 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
725 basic_block bb
, int used
)
733 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
734 if (! (e
->flags
& EDGE_FALLTHRU
))
737 fprintf (file
, " %s heuristics%s: %.1f%%",
738 predictor_info
[predictor
].name
,
739 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
743 fprintf (file
, " exec %"PRId64
, bb
->count
);
746 fprintf (file
, " hit %"PRId64
, e
->count
);
747 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
751 fprintf (file
, "\n");
754 /* We can not predict the probabilities of outgoing edges of bb. Set them
755 evenly and hope for the best. */
757 set_even_probabilities (basic_block bb
)
763 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
764 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
766 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
767 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
768 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
773 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
774 note if not already present. Remove now useless REG_BR_PRED notes. */
777 combine_predictions_for_insn (rtx insn
, basic_block bb
)
782 int best_probability
= PROB_EVEN
;
783 enum br_predictor best_predictor
= END_PREDICTORS
;
784 int combined_probability
= REG_BR_PROB_BASE
/ 2;
786 bool first_match
= false;
789 if (!can_predict_insn_p (insn
))
791 set_even_probabilities (bb
);
795 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
796 pnote
= ®_NOTES (insn
);
798 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
801 /* We implement "first match" heuristics and use probability guessed
802 by predictor with smallest index. */
803 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
804 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
806 enum br_predictor predictor
= ((enum br_predictor
)
807 INTVAL (XEXP (XEXP (note
, 0), 0)));
808 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
811 if (best_predictor
> predictor
)
812 best_probability
= probability
, best_predictor
= predictor
;
814 d
= (combined_probability
* probability
815 + (REG_BR_PROB_BASE
- combined_probability
)
816 * (REG_BR_PROB_BASE
- probability
));
818 /* Use FP math to avoid overflows of 32bit integers. */
820 /* If one probability is 0% and one 100%, avoid division by zero. */
821 combined_probability
= REG_BR_PROB_BASE
/ 2;
823 combined_probability
= (((double) combined_probability
) * probability
824 * REG_BR_PROB_BASE
/ d
+ 0.5);
827 /* Decide which heuristic to use. In case we didn't match anything,
828 use no_prediction heuristic, in case we did match, use either
829 first match or Dempster-Shaffer theory depending on the flags. */
831 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
835 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
836 combined_probability
, bb
, true);
839 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
841 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
846 combined_probability
= best_probability
;
847 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
851 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
853 enum br_predictor predictor
= ((enum br_predictor
)
854 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
855 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
857 dump_prediction (dump_file
, predictor
, probability
, bb
,
858 !first_match
|| best_predictor
== predictor
);
859 *pnote
= XEXP (*pnote
, 1);
862 pnote
= &XEXP (*pnote
, 1);
867 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
869 /* Save the prediction into CFG in case we are seeing non-degenerated
871 if (!single_succ_p (bb
))
873 BRANCH_EDGE (bb
)->probability
= combined_probability
;
874 FALLTHRU_EDGE (bb
)->probability
875 = REG_BR_PROB_BASE
- combined_probability
;
878 else if (!single_succ_p (bb
))
880 int prob
= XINT (prob_note
, 0);
882 BRANCH_EDGE (bb
)->probability
= prob
;
883 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
886 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
889 /* Combine predictions into single probability and store them into CFG.
890 Remove now useless prediction entries. */
893 combine_predictions_for_bb (basic_block bb
)
895 int best_probability
= PROB_EVEN
;
896 enum br_predictor best_predictor
= END_PREDICTORS
;
897 int combined_probability
= REG_BR_PROB_BASE
/ 2;
899 bool first_match
= false;
901 struct edge_prediction
*pred
;
903 edge e
, first
= NULL
, second
= NULL
;
906 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
907 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
910 if (first
&& !second
)
916 /* When there is no successor or only one choice, prediction is easy.
918 We are lazy for now and predict only basic blocks with two outgoing
919 edges. It is possible to predict generic case too, but we have to
920 ignore first match heuristics and do more involved combining. Implement
925 set_even_probabilities (bb
);
926 clear_bb_predictions (bb
);
928 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
934 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
936 edge_prediction
**preds
= bb_predictions
->get (bb
);
939 /* We implement "first match" heuristics and use probability guessed
940 by predictor with smallest index. */
941 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
943 enum br_predictor predictor
= pred
->ep_predictor
;
944 int probability
= pred
->ep_probability
;
946 if (pred
->ep_edge
!= first
)
947 probability
= REG_BR_PROB_BASE
- probability
;
950 /* First match heuristics would be widly confused if we predicted
952 if (best_predictor
> predictor
)
954 struct edge_prediction
*pred2
;
955 int prob
= probability
;
957 for (pred2
= (struct edge_prediction
*) *preds
;
958 pred2
; pred2
= pred2
->ep_next
)
959 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
961 int probability2
= pred
->ep_probability
;
963 if (pred2
->ep_edge
!= first
)
964 probability2
= REG_BR_PROB_BASE
- probability2
;
966 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
967 (probability2
< REG_BR_PROB_BASE
/ 2))
970 /* If the same predictor later gave better result, go for it! */
971 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
972 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
976 best_probability
= prob
, best_predictor
= predictor
;
979 d
= (combined_probability
* probability
980 + (REG_BR_PROB_BASE
- combined_probability
)
981 * (REG_BR_PROB_BASE
- probability
));
983 /* Use FP math to avoid overflows of 32bit integers. */
985 /* If one probability is 0% and one 100%, avoid division by zero. */
986 combined_probability
= REG_BR_PROB_BASE
/ 2;
988 combined_probability
= (((double) combined_probability
)
990 * REG_BR_PROB_BASE
/ d
+ 0.5);
994 /* Decide which heuristic to use. In case we didn't match anything,
995 use no_prediction heuristic, in case we did match, use either
996 first match or Dempster-Shaffer theory depending on the flags. */
998 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1002 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
1005 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1007 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1012 combined_probability
= best_probability
;
1013 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
1017 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1019 enum br_predictor predictor
= pred
->ep_predictor
;
1020 int probability
= pred
->ep_probability
;
1022 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
1023 probability
= REG_BR_PROB_BASE
- probability
;
1024 dump_prediction (dump_file
, predictor
, probability
, bb
,
1025 !first_match
|| best_predictor
== predictor
);
1028 clear_bb_predictions (bb
);
1032 first
->probability
= combined_probability
;
1033 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1037 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1038 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1040 T1 and T2 should be one of the following cases:
1041 1. T1 is SSA_NAME, T2 is NULL
1042 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1043 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1046 strips_small_constant (tree t1
, tree t2
)
1053 else if (TREE_CODE (t1
) == SSA_NAME
)
1055 else if (tree_fits_shwi_p (t1
))
1056 value
= tree_to_shwi (t1
);
1062 else if (tree_fits_shwi_p (t2
))
1063 value
= tree_to_shwi (t2
);
1064 else if (TREE_CODE (t2
) == SSA_NAME
)
1072 if (value
<= 4 && value
>= -4)
1078 /* Return the SSA_NAME in T or T's operands.
1079 Return NULL if SSA_NAME cannot be found. */
1082 get_base_value (tree t
)
1084 if (TREE_CODE (t
) == SSA_NAME
)
1087 if (!BINARY_CLASS_P (t
))
1090 switch (TREE_OPERAND_LENGTH (t
))
1093 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1095 return strips_small_constant (TREE_OPERAND (t
, 0),
1096 TREE_OPERAND (t
, 1));
1102 /* Check the compare STMT in LOOP. If it compares an induction
1103 variable to a loop invariant, return true, and save
1104 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1105 Otherwise return false and set LOOP_INVAIANT to NULL. */
1108 is_comparison_with_loop_invariant_p (gimple stmt
, struct loop
*loop
,
1109 tree
*loop_invariant
,
1110 enum tree_code
*compare_code
,
1114 tree op0
, op1
, bound
, base
;
1116 enum tree_code code
;
1119 code
= gimple_cond_code (stmt
);
1120 *loop_invariant
= NULL
;
1136 op0
= gimple_cond_lhs (stmt
);
1137 op1
= gimple_cond_rhs (stmt
);
1139 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1140 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1142 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1144 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1146 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1147 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1149 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1150 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1153 if (integer_zerop (iv0
.step
))
1155 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1156 code
= invert_tree_comparison (code
, false);
1159 if (tree_fits_shwi_p (iv1
.step
))
1168 if (tree_fits_shwi_p (iv0
.step
))
1174 if (TREE_CODE (bound
) != INTEGER_CST
)
1175 bound
= get_base_value (bound
);
1178 if (TREE_CODE (base
) != INTEGER_CST
)
1179 base
= get_base_value (base
);
1183 *loop_invariant
= bound
;
1184 *compare_code
= code
;
1186 *loop_iv_base
= base
;
1190 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1193 expr_coherent_p (tree t1
, tree t2
)
1196 tree ssa_name_1
= NULL
;
1197 tree ssa_name_2
= NULL
;
1199 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1200 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1205 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1207 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1210 /* Check to see if t1 is expressed/defined with t2. */
1211 stmt
= SSA_NAME_DEF_STMT (t1
);
1212 gcc_assert (stmt
!= NULL
);
1213 if (is_gimple_assign (stmt
))
1215 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1216 if (ssa_name_1
&& ssa_name_1
== t2
)
1220 /* Check to see if t2 is expressed/defined with t1. */
1221 stmt
= SSA_NAME_DEF_STMT (t2
);
1222 gcc_assert (stmt
!= NULL
);
1223 if (is_gimple_assign (stmt
))
1225 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1226 if (ssa_name_2
&& ssa_name_2
== t1
)
1230 /* Compare if t1 and t2's def_stmts are identical. */
1231 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1237 /* Predict branch probability of BB when BB contains a branch that compares
1238 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1239 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1242 for (int i = 0; i < bound; i++) {
1249 In this loop, we will predict the branch inside the loop to be taken. */
1252 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1253 tree loop_bound_var
,
1254 tree loop_iv_base_var
,
1255 enum tree_code loop_bound_code
,
1256 int loop_bound_step
)
1259 tree compare_var
, compare_base
;
1260 enum tree_code compare_code
;
1261 tree compare_step_var
;
1265 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1266 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1267 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1270 stmt
= last_stmt (bb
);
1271 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1273 if (!is_comparison_with_loop_invariant_p (stmt
, loop
, &compare_var
,
1279 /* Find the taken edge. */
1280 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1281 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1284 /* When comparing an IV to a loop invariant, NE is more likely to be
1285 taken while EQ is more likely to be not-taken. */
1286 if (compare_code
== NE_EXPR
)
1288 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1291 else if (compare_code
== EQ_EXPR
)
1293 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1297 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1300 /* If loop bound, base and compare bound are all constants, we can
1301 calculate the probability directly. */
1302 if (tree_fits_shwi_p (loop_bound_var
)
1303 && tree_fits_shwi_p (compare_var
)
1304 && tree_fits_shwi_p (compare_base
))
1307 bool overflow
, overall_overflow
= false;
1308 widest_int compare_count
, tem
;
1310 /* (loop_bound - base) / compare_step */
1311 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1312 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1313 overall_overflow
|= overflow
;
1314 widest_int loop_count
= wi::div_trunc (tem
,
1315 wi::to_widest (compare_step_var
),
1317 overall_overflow
|= overflow
;
1319 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1320 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1322 /* (loop_bound - compare_bound) / compare_step */
1323 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1324 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1325 overall_overflow
|= overflow
;
1326 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1328 overall_overflow
|= overflow
;
1332 /* (compare_bound - base) / compare_step */
1333 tem
= wi::sub (wi::to_widest (compare_var
),
1334 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1335 overall_overflow
|= overflow
;
1336 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1338 overall_overflow
|= overflow
;
1340 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1342 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1344 if (wi::neg_p (compare_count
))
1346 if (wi::neg_p (loop_count
))
1348 if (loop_count
== 0)
1350 else if (wi::cmps (compare_count
, loop_count
) == 1)
1351 probability
= REG_BR_PROB_BASE
;
1354 tem
= compare_count
* REG_BR_PROB_BASE
;
1355 tem
= wi::udiv_trunc (tem
, loop_count
);
1356 probability
= tem
.to_uhwi ();
1359 if (!overall_overflow
)
1360 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1365 if (expr_coherent_p (loop_bound_var
, compare_var
))
1367 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1368 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1369 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1370 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1371 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1372 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1373 else if (loop_bound_code
== NE_EXPR
)
1375 /* If the loop backedge condition is "(i != bound)", we do
1376 the comparison based on the step of IV:
1377 * step < 0 : backedge condition is like (i > bound)
1378 * step > 0 : backedge condition is like (i < bound) */
1379 gcc_assert (loop_bound_step
!= 0);
1380 if (loop_bound_step
> 0
1381 && (compare_code
== LT_EXPR
1382 || compare_code
== LE_EXPR
))
1383 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1384 else if (loop_bound_step
< 0
1385 && (compare_code
== GT_EXPR
1386 || compare_code
== GE_EXPR
))
1387 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1389 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1392 /* The branch is predicted not-taken if loop_bound_code is
1393 opposite with compare_code. */
1394 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1396 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1399 for (i = s; i < h; i++)
1401 The branch should be predicted taken. */
1402 if (loop_bound_step
> 0
1403 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1404 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1405 else if (loop_bound_step
< 0
1406 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1407 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1409 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1413 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1414 exits are resulted from short-circuit conditions that will generate an
1417 if (foo() || global > 10)
1420 This will be translated into:
1425 if foo() goto BB6 else goto BB5
1427 if global > 10 goto BB6 else goto BB7
1431 iftmp = (PHI 0(BB5), 1(BB6))
1432 if iftmp == 1 goto BB8 else goto BB3
1434 outside of the loop...
1436 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1437 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1438 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1439 exits to predict them using PRED_LOOP_EXIT. */
1442 predict_extra_loop_exits (edge exit_edge
)
1445 bool check_value_one
;
1447 tree cmp_rhs
, cmp_lhs
;
1448 gimple cmp_stmt
= last_stmt (exit_edge
->src
);
1450 if (!cmp_stmt
|| gimple_code (cmp_stmt
) != GIMPLE_COND
)
1452 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1453 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1454 if (!TREE_CONSTANT (cmp_rhs
)
1455 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1457 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1460 /* If check_value_one is true, only the phi_args with value '1' will lead
1461 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1463 check_value_one
= (((integer_onep (cmp_rhs
))
1464 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1465 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1467 phi_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1468 if (!phi_stmt
|| gimple_code (phi_stmt
) != GIMPLE_PHI
)
1471 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1475 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1476 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1478 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1480 if ((check_value_one
^ integer_onep (val
)) == 1)
1482 if (EDGE_COUNT (e
->src
->succs
) != 1)
1484 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1488 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1489 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1493 /* Predict edge probabilities by exploiting loop structure. */
1496 predict_loops (void)
1500 /* Try to predict out blocks in a loop that are not part of a
1502 FOR_EACH_LOOP (loop
, 0)
1504 basic_block bb
, *bbs
;
1505 unsigned j
, n_exits
;
1507 struct tree_niter_desc niter_desc
;
1509 struct nb_iter_bound
*nb_iter
;
1510 enum tree_code loop_bound_code
= ERROR_MARK
;
1511 tree loop_bound_step
= NULL
;
1512 tree loop_bound_var
= NULL
;
1513 tree loop_iv_base
= NULL
;
1516 exits
= get_loop_exit_edges (loop
);
1517 n_exits
= exits
.length ();
1524 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1527 HOST_WIDE_INT nitercst
;
1528 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1530 enum br_predictor predictor
;
1532 predict_extra_loop_exits (ex
);
1534 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1535 niter
= niter_desc
.niter
;
1536 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1537 niter
= loop_niter_by_eval (loop
, ex
);
1539 if (TREE_CODE (niter
) == INTEGER_CST
)
1541 if (tree_fits_uhwi_p (niter
)
1543 && compare_tree_int (niter
, max
- 1) == -1)
1544 nitercst
= tree_to_uhwi (niter
) + 1;
1547 predictor
= PRED_LOOP_ITERATIONS
;
1549 /* If we have just one exit and we can derive some information about
1550 the number of iterations of the loop from the statements inside
1551 the loop, use it to predict this exit. */
1552 else if (n_exits
== 1)
1554 nitercst
= estimated_stmt_executions_int (loop
);
1560 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1565 /* If the prediction for number of iterations is zero, do not
1566 predict the exit edges. */
1570 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1571 predict_edge (ex
, predictor
, probability
);
1575 /* Find information about loop bound variables. */
1576 for (nb_iter
= loop
->bounds
; nb_iter
;
1577 nb_iter
= nb_iter
->next
)
1579 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1581 stmt
= nb_iter
->stmt
;
1584 if (!stmt
&& last_stmt (loop
->header
)
1585 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1586 stmt
= last_stmt (loop
->header
);
1588 is_comparison_with_loop_invariant_p (stmt
, loop
,
1594 bbs
= get_loop_body (loop
);
1596 for (j
= 0; j
< loop
->num_nodes
; j
++)
1598 int header_found
= 0;
1604 /* Bypass loop heuristics on continue statement. These
1605 statements construct loops via "non-loop" constructs
1606 in the source language and are better to be handled
1608 if (predicted_by_p (bb
, PRED_CONTINUE
))
1611 /* Loop branch heuristics - predict an edge back to a
1612 loop's head as taken. */
1613 if (bb
== loop
->latch
)
1615 e
= find_edge (loop
->latch
, loop
->header
);
1619 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1623 /* Loop exit heuristics - predict an edge exiting the loop if the
1624 conditional has no loop header successors as not taken. */
1626 /* If we already used more reliable loop exit predictors, do not
1627 bother with PRED_LOOP_EXIT. */
1628 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1629 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1631 /* For loop with many exits we don't want to predict all exits
1632 with the pretty large probability, because if all exits are
1633 considered in row, the loop would be predicted to iterate
1634 almost never. The code to divide probability by number of
1635 exits is very rough. It should compute the number of exits
1636 taken in each patch through function (not the overall number
1637 of exits that might be a lot higher for loops with wide switch
1638 statements in them) and compute n-th square root.
1640 We limit the minimal probability by 2% to avoid
1641 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1642 as this was causing regression in perl benchmark containing such
1645 int probability
= ((REG_BR_PROB_BASE
1646 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1648 if (probability
< HITRATE (2))
1649 probability
= HITRATE (2);
1650 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1651 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1652 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1653 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1656 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1658 tree_to_shwi (loop_bound_step
));
1661 /* Free basic blocks from get_loop_body. */
1666 /* Attempt to predict probabilities of BB outgoing edges using local
1669 bb_estimate_probability_locally (basic_block bb
)
1671 rtx last_insn
= BB_END (bb
);
1674 if (! can_predict_insn_p (last_insn
))
1676 cond
= get_condition (last_insn
, NULL
, false, false);
1680 /* Try "pointer heuristic."
1681 A comparison ptr == 0 is predicted as false.
1682 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1683 if (COMPARISON_P (cond
)
1684 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1685 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1687 if (GET_CODE (cond
) == EQ
)
1688 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1689 else if (GET_CODE (cond
) == NE
)
1690 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1694 /* Try "opcode heuristic."
1695 EQ tests are usually false and NE tests are usually true. Also,
1696 most quantities are positive, so we can make the appropriate guesses
1697 about signed comparisons against zero. */
1698 switch (GET_CODE (cond
))
1701 /* Unconditional branch. */
1702 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1703 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1708 /* Floating point comparisons appears to behave in a very
1709 unpredictable way because of special role of = tests in
1711 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1713 /* Comparisons with 0 are often used for booleans and there is
1714 nothing useful to predict about them. */
1715 else if (XEXP (cond
, 1) == const0_rtx
1716 || XEXP (cond
, 0) == const0_rtx
)
1719 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1724 /* Floating point comparisons appears to behave in a very
1725 unpredictable way because of special role of = tests in
1727 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1729 /* Comparisons with 0 are often used for booleans and there is
1730 nothing useful to predict about them. */
1731 else if (XEXP (cond
, 1) == const0_rtx
1732 || XEXP (cond
, 0) == const0_rtx
)
1735 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1739 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1743 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1748 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1749 || XEXP (cond
, 1) == constm1_rtx
)
1750 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1755 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1756 || XEXP (cond
, 1) == constm1_rtx
)
1757 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1765 /* Set edge->probability for each successor edge of BB. */
1767 guess_outgoing_edge_probabilities (basic_block bb
)
1769 bb_estimate_probability_locally (bb
);
1770 combine_predictions_for_insn (BB_END (bb
), bb
);
1773 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
1775 /* Helper function for expr_expected_value. */
1778 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1779 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
1784 *predictor
= PRED_UNCONDITIONAL
;
1786 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1788 if (TREE_CONSTANT (op0
))
1791 if (code
!= SSA_NAME
)
1794 def
= SSA_NAME_DEF_STMT (op0
);
1796 /* If we were already here, break the infinite cycle. */
1797 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1800 if (gimple_code (def
) == GIMPLE_PHI
)
1802 /* All the arguments of the PHI node must have the same constant
1804 int i
, n
= gimple_phi_num_args (def
);
1805 tree val
= NULL
, new_val
;
1807 for (i
= 0; i
< n
; i
++)
1809 tree arg
= PHI_ARG_DEF (def
, i
);
1810 enum br_predictor predictor2
;
1812 /* If this PHI has itself as an argument, we cannot
1813 determine the string length of this argument. However,
1814 if we can find an expected constant value for the other
1815 PHI args then we can still be sure that this is
1816 likely a constant. So be optimistic and just
1817 continue with the next argument. */
1818 if (arg
== PHI_RESULT (def
))
1821 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
1823 /* It is difficult to combine value predictors. Simply assume
1824 that later predictor is weaker and take its prediction. */
1825 if (predictor
&& *predictor
< predictor2
)
1826 *predictor
= predictor2
;
1831 else if (!operand_equal_p (val
, new_val
, false))
1836 if (is_gimple_assign (def
))
1838 if (gimple_assign_lhs (def
) != op0
)
1841 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1842 gimple_assign_rhs1 (def
),
1843 gimple_assign_rhs_code (def
),
1844 gimple_assign_rhs2 (def
),
1845 visited
, predictor
);
1848 if (is_gimple_call (def
))
1850 tree decl
= gimple_call_fndecl (def
);
1853 if (gimple_call_internal_p (def
)
1854 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
1856 gcc_assert (gimple_call_num_args (def
) == 3);
1857 tree val
= gimple_call_arg (def
, 0);
1858 if (TREE_CONSTANT (val
))
1862 tree val2
= gimple_call_arg (def
, 2);
1863 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
1864 && tree_fits_uhwi_p (val2
)
1865 && tree_to_uhwi (val2
) < END_PREDICTORS
);
1866 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
1868 return gimple_call_arg (def
, 1);
1872 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1873 switch (DECL_FUNCTION_CODE (decl
))
1875 case BUILT_IN_EXPECT
:
1878 if (gimple_call_num_args (def
) != 2)
1880 val
= gimple_call_arg (def
, 0);
1881 if (TREE_CONSTANT (val
))
1884 *predictor
= PRED_BUILTIN_EXPECT
;
1885 return gimple_call_arg (def
, 1);
1888 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1889 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1890 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1891 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1892 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1893 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1894 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1895 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1896 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1897 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1898 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1899 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1900 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1901 /* Assume that any given atomic operation has low contention,
1902 and thus the compare-and-swap operation succeeds. */
1904 *predictor
= PRED_COMPARE_AND_SWAP
;
1905 return boolean_true_node
;
1912 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1915 enum br_predictor predictor2
;
1916 op0
= expr_expected_value (op0
, visited
, predictor
);
1919 op1
= expr_expected_value (op1
, visited
, &predictor2
);
1920 if (predictor
&& *predictor
< predictor2
)
1921 *predictor
= predictor2
;
1924 res
= fold_build2 (code
, type
, op0
, op1
);
1925 if (TREE_CONSTANT (res
))
1929 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1932 op0
= expr_expected_value (op0
, visited
, predictor
);
1935 res
= fold_build1 (code
, type
, op0
);
1936 if (TREE_CONSTANT (res
))
1943 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1944 The function is used by builtin_expect branch predictor so the evidence
1945 must come from this construct and additional possible constant folding.
1947 We may want to implement more involved value guess (such as value range
1948 propagation based prediction), but such tricks shall go to new
1952 expr_expected_value (tree expr
, bitmap visited
,
1953 enum br_predictor
*predictor
)
1955 enum tree_code code
;
1958 if (TREE_CONSTANT (expr
))
1961 *predictor
= PRED_UNCONDITIONAL
;
1965 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1966 return expr_expected_value_1 (TREE_TYPE (expr
),
1967 op0
, code
, op1
, visited
, predictor
);
1970 /* Predict using opcode of the last statement in basic block. */
1972 tree_predict_by_opcode (basic_block bb
)
1974 gimple stmt
= last_stmt (bb
);
1982 enum br_predictor predictor
;
1984 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1986 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1987 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1989 op0
= gimple_cond_lhs (stmt
);
1990 op1
= gimple_cond_rhs (stmt
);
1991 cmp
= gimple_cond_code (stmt
);
1992 type
= TREE_TYPE (op0
);
1993 visited
= BITMAP_ALLOC (NULL
);
1994 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
1996 BITMAP_FREE (visited
);
1997 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
1999 if (predictor
== PRED_BUILTIN_EXPECT
)
2001 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2003 gcc_assert (percent
>= 0 && percent
<= 100);
2004 if (integer_zerop (val
))
2005 percent
= 100 - percent
;
2006 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2009 predict_edge (then_edge
, predictor
,
2010 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2012 /* Try "pointer heuristic."
2013 A comparison ptr == 0 is predicted as false.
2014 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2015 if (POINTER_TYPE_P (type
))
2018 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2019 else if (cmp
== NE_EXPR
)
2020 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2024 /* Try "opcode heuristic."
2025 EQ tests are usually false and NE tests are usually true. Also,
2026 most quantities are positive, so we can make the appropriate guesses
2027 about signed comparisons against zero. */
2032 /* Floating point comparisons appears to behave in a very
2033 unpredictable way because of special role of = tests in
2035 if (FLOAT_TYPE_P (type
))
2037 /* Comparisons with 0 are often used for booleans and there is
2038 nothing useful to predict about them. */
2039 else if (integer_zerop (op0
) || integer_zerop (op1
))
2042 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2047 /* Floating point comparisons appears to behave in a very
2048 unpredictable way because of special role of = tests in
2050 if (FLOAT_TYPE_P (type
))
2052 /* Comparisons with 0 are often used for booleans and there is
2053 nothing useful to predict about them. */
2054 else if (integer_zerop (op0
)
2055 || integer_zerop (op1
))
2058 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2062 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2065 case UNORDERED_EXPR
:
2066 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2071 if (integer_zerop (op1
)
2072 || integer_onep (op1
)
2073 || integer_all_onesp (op1
)
2076 || real_minus_onep (op1
))
2077 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2082 if (integer_zerop (op1
)
2083 || integer_onep (op1
)
2084 || integer_all_onesp (op1
)
2087 || real_minus_onep (op1
))
2088 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2096 /* Try to guess whether the value of return means error code. */
2098 static enum br_predictor
2099 return_prediction (tree val
, enum prediction
*prediction
)
2103 return PRED_NO_PREDICTION
;
2104 /* Different heuristics for pointers and scalars. */
2105 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2107 /* NULL is usually not returned. */
2108 if (integer_zerop (val
))
2110 *prediction
= NOT_TAKEN
;
2111 return PRED_NULL_RETURN
;
2114 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2116 /* Negative return values are often used to indicate
2118 if (TREE_CODE (val
) == INTEGER_CST
2119 && tree_int_cst_sgn (val
) < 0)
2121 *prediction
= NOT_TAKEN
;
2122 return PRED_NEGATIVE_RETURN
;
2124 /* Constant return values seems to be commonly taken.
2125 Zero/one often represent booleans so exclude them from the
2127 if (TREE_CONSTANT (val
)
2128 && (!integer_zerop (val
) && !integer_onep (val
)))
2130 *prediction
= TAKEN
;
2131 return PRED_CONST_RETURN
;
2134 return PRED_NO_PREDICTION
;
2137 /* Find the basic block with return expression and look up for possible
2138 return value trying to apply RETURN_PREDICTION heuristics. */
2140 apply_return_prediction (void)
2142 gimple return_stmt
= NULL
;
2146 int phi_num_args
, i
;
2147 enum br_predictor pred
;
2148 enum prediction direction
;
2151 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2153 return_stmt
= last_stmt (e
->src
);
2155 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
2160 return_val
= gimple_return_retval (return_stmt
);
2163 if (TREE_CODE (return_val
) != SSA_NAME
2164 || !SSA_NAME_DEF_STMT (return_val
)
2165 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2167 phi
= SSA_NAME_DEF_STMT (return_val
);
2168 phi_num_args
= gimple_phi_num_args (phi
);
2169 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2171 /* Avoid the degenerate case where all return values form the function
2172 belongs to same category (ie they are all positive constants)
2173 so we can hardly say something about them. */
2174 for (i
= 1; i
< phi_num_args
; i
++)
2175 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2177 if (i
!= phi_num_args
)
2178 for (i
= 0; i
< phi_num_args
; i
++)
2180 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2181 if (pred
!= PRED_NO_PREDICTION
)
2182 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2187 /* Look for basic block that contains unlikely to happen events
2188 (such as noreturn calls) and mark all paths leading to execution
2189 of this basic blocks as unlikely. */
2192 tree_bb_level_predictions (void)
2195 bool has_return_edges
= false;
2199 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2200 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2202 has_return_edges
= true;
2206 apply_return_prediction ();
2208 FOR_EACH_BB_FN (bb
, cfun
)
2210 gimple_stmt_iterator gsi
;
2212 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2214 gimple stmt
= gsi_stmt (gsi
);
2217 if (is_gimple_call (stmt
))
2219 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2220 && has_return_edges
)
2221 predict_paths_leading_to (bb
, PRED_NORETURN
,
2223 decl
= gimple_call_fndecl (stmt
);
2225 && lookup_attribute ("cold",
2226 DECL_ATTRIBUTES (decl
)))
2227 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2230 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2232 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2233 gimple_predict_outcome (stmt
));
2234 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2235 hints to callers. */
2241 #ifdef ENABLE_CHECKING
2243 /* Callback for hash_map::traverse, asserts that the pointer map is
2247 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2250 gcc_assert (!value
);
2255 /* Predict branch probabilities and estimate profile for basic block BB. */
2258 tree_estimate_probability_bb (basic_block bb
)
2264 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2266 /* Predict edges to user labels with attributes. */
2267 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2269 gimple_stmt_iterator gi
;
2270 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2272 gimple stmt
= gsi_stmt (gi
);
2275 if (gimple_code (stmt
) != GIMPLE_LABEL
)
2277 decl
= gimple_label_label (stmt
);
2278 if (DECL_ARTIFICIAL (decl
))
2281 /* Finally, we have a user-defined label. */
2282 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2283 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2284 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2285 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2289 /* Predict early returns to be probable, as we've already taken
2290 care for error returns and other cases are often used for
2291 fast paths through function.
2293 Since we've already removed the return statements, we are
2294 looking for CFG like:
2304 if (e
->dest
!= bb
->next_bb
2305 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2306 && single_succ_p (e
->dest
)
2307 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2308 && (last
= last_stmt (e
->dest
)) != NULL
2309 && gimple_code (last
) == GIMPLE_RETURN
)
2314 if (single_succ_p (bb
))
2316 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2317 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2318 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2319 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2320 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2323 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2324 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2325 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2326 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2329 /* Look for block we are guarding (ie we dominate it,
2330 but it doesn't postdominate us). */
2331 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2332 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2333 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2335 gimple_stmt_iterator bi
;
2337 /* The call heuristic claims that a guarded function call
2338 is improbable. This is because such calls are often used
2339 to signal exceptional situations such as printing error
2341 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2344 gimple stmt
= gsi_stmt (bi
);
2345 if (is_gimple_call (stmt
)
2346 /* Constant and pure calls are hardly used to signalize
2347 something exceptional. */
2348 && gimple_has_side_effects (stmt
))
2350 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2356 tree_predict_by_opcode (bb
);
2359 /* Predict branch probabilities and estimate profile of the tree CFG.
2360 This function can be called from the loop optimizers to recompute
2361 the profile information. */
2364 tree_estimate_probability (void)
2368 add_noreturn_fake_exit_edges ();
2369 connect_infinite_loops_to_exit ();
2370 /* We use loop_niter_by_eval, which requires that the loops have
2372 create_preheaders (CP_SIMPLE_PREHEADERS
);
2373 calculate_dominance_info (CDI_POST_DOMINATORS
);
2375 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2376 tree_bb_level_predictions ();
2377 record_loop_exits ();
2379 if (number_of_loops (cfun
) > 1)
2382 FOR_EACH_BB_FN (bb
, cfun
)
2383 tree_estimate_probability_bb (bb
);
2385 FOR_EACH_BB_FN (bb
, cfun
)
2386 combine_predictions_for_bb (bb
);
2388 #ifdef ENABLE_CHECKING
2389 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2391 delete bb_predictions
;
2392 bb_predictions
= NULL
;
2394 estimate_bb_frequencies (false);
2395 free_dominance_info (CDI_POST_DOMINATORS
);
2396 remove_fake_exit_edges ();
2399 /* Predict edges to successors of CUR whose sources are not postdominated by
2400 BB by PRED and recurse to all postdominators. */
2403 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2404 enum br_predictor pred
,
2405 enum prediction taken
,
2412 /* We are looking for all edges forming edge cut induced by
2413 set of all blocks postdominated by BB. */
2414 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2415 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2416 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2422 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2423 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2425 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2427 /* See if there is an edge from e->src that is not abnormal
2428 and does not lead to BB. */
2429 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2431 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2432 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2438 /* If there is non-abnormal path leaving e->src, predict edge
2439 using predictor. Otherwise we need to look for paths
2442 The second may lead to infinite loop in the case we are predicitng
2443 regions that are only reachable by abnormal edges. We simply
2444 prevent visiting given BB twice. */
2446 predict_edge_def (e
, pred
, taken
);
2447 else if (bitmap_set_bit (visited
, e
->src
->index
))
2448 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2450 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2452 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2453 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2456 /* Sets branch probabilities according to PREDiction and
2460 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2461 enum prediction taken
)
2463 bitmap visited
= BITMAP_ALLOC (NULL
);
2464 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2465 BITMAP_FREE (visited
);
2468 /* Like predict_paths_leading_to but take edge instead of basic block. */
2471 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2472 enum prediction taken
)
2474 bool has_nonloop_edge
= false;
2478 basic_block bb
= e
->src
;
2479 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2480 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2481 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2482 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2484 has_nonloop_edge
= true;
2487 if (!has_nonloop_edge
)
2489 bitmap visited
= BITMAP_ALLOC (NULL
);
2490 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2491 BITMAP_FREE (visited
);
2494 predict_edge_def (e
, pred
, taken
);
2497 /* This is used to carry information about basic blocks. It is
2498 attached to the AUX field of the standard CFG block. */
2500 typedef struct block_info_def
2502 /* Estimated frequency of execution of basic_block. */
2505 /* To keep queue of basic blocks to process. */
2508 /* Number of predecessors we need to visit first. */
2512 /* Similar information for edges. */
2513 typedef struct edge_info_def
2515 /* In case edge is a loopback edge, the probability edge will be reached
2516 in case header is. Estimated number of iterations of the loop can be
2517 then computed as 1 / (1 - back_edge_prob). */
2518 sreal back_edge_prob
;
2519 /* True if the edge is a loopback edge in the natural loop. */
2520 unsigned int back_edge
:1;
2523 #define BLOCK_INFO(B) ((block_info) (B)->aux)
2524 #define EDGE_INFO(E) ((edge_info) (E)->aux)
2526 /* Helper function for estimate_bb_frequencies.
2527 Propagate the frequencies in blocks marked in
2528 TOVISIT, starting in HEAD. */
2531 propagate_freq (basic_block head
, bitmap tovisit
)
2540 /* For each basic block we need to visit count number of his predecessors
2541 we need to visit first. */
2542 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2547 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2549 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2551 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2553 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2555 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2557 "Irreducible region hit, ignoring edge to %i->%i\n",
2558 e
->src
->index
, bb
->index
);
2560 BLOCK_INFO (bb
)->npredecessors
= count
;
2561 /* When function never returns, we will never process exit block. */
2562 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2563 bb
->count
= bb
->frequency
= 0;
2566 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
2568 for (bb
= head
; bb
; bb
= nextbb
)
2571 sreal cyclic_probability
, frequency
;
2573 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
2574 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
2576 nextbb
= BLOCK_INFO (bb
)->next
;
2577 BLOCK_INFO (bb
)->next
= NULL
;
2579 /* Compute frequency of basic block. */
2582 #ifdef ENABLE_CHECKING
2583 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2584 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2585 || (e
->flags
& EDGE_DFS_BACK
));
2588 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2589 if (EDGE_INFO (e
)->back_edge
)
2591 sreal_add (&cyclic_probability
, &cyclic_probability
,
2592 &EDGE_INFO (e
)->back_edge_prob
);
2594 else if (!(e
->flags
& EDGE_DFS_BACK
))
2598 /* frequency += (e->probability
2599 * BLOCK_INFO (e->src)->frequency /
2600 REG_BR_PROB_BASE); */
2602 sreal_init (&tmp
, e
->probability
, 0);
2603 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
2604 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
2605 sreal_add (&frequency
, &frequency
, &tmp
);
2608 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
2610 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
2611 sizeof (frequency
));
2615 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
2617 memcpy (&cyclic_probability
, &real_almost_one
,
2618 sizeof (real_almost_one
));
2621 /* BLOCK_INFO (bb)->frequency = frequency
2622 / (1 - cyclic_probability) */
2624 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
2625 sreal_div (&BLOCK_INFO (bb
)->frequency
,
2626 &frequency
, &cyclic_probability
);
2630 bitmap_clear_bit (tovisit
, bb
->index
);
2632 e
= find_edge (bb
, head
);
2637 /* EDGE_INFO (e)->back_edge_prob
2638 = ((e->probability * BLOCK_INFO (bb)->frequency)
2639 / REG_BR_PROB_BASE); */
2641 sreal_init (&tmp
, e
->probability
, 0);
2642 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
2643 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2644 &tmp
, &real_inv_br_prob_base
);
2647 /* Propagate to successor blocks. */
2648 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2649 if (!(e
->flags
& EDGE_DFS_BACK
)
2650 && BLOCK_INFO (e
->dest
)->npredecessors
)
2652 BLOCK_INFO (e
->dest
)->npredecessors
--;
2653 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2658 BLOCK_INFO (last
)->next
= e
->dest
;
2666 /* Estimate frequencies in loops at same nest level. */
2669 estimate_loops_at_level (struct loop
*first_loop
)
2673 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2678 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2680 estimate_loops_at_level (loop
->inner
);
2682 /* Find current loop back edge and mark it. */
2683 e
= loop_latch_edge (loop
);
2684 EDGE_INFO (e
)->back_edge
= 1;
2686 bbs
= get_loop_body (loop
);
2687 for (i
= 0; i
< loop
->num_nodes
; i
++)
2688 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2690 propagate_freq (loop
->header
, tovisit
);
2691 BITMAP_FREE (tovisit
);
2695 /* Propagates frequencies through structure of loops. */
2698 estimate_loops (void)
2700 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2703 /* Start by estimating the frequencies in the loops. */
2704 if (number_of_loops (cfun
) > 1)
2705 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2707 /* Now propagate the frequencies through all the blocks. */
2708 FOR_ALL_BB_FN (bb
, cfun
)
2710 bitmap_set_bit (tovisit
, bb
->index
);
2712 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
2713 BITMAP_FREE (tovisit
);
2716 /* Drop the profile for NODE to guessed, and update its frequency based on
2717 whether it is expected to be hot given the CALL_COUNT. */
2720 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
2722 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2723 /* In the case where this was called by another function with a
2724 dropped profile, call_count will be 0. Since there are no
2725 non-zero call counts to this function, we don't know for sure
2726 whether it is hot, and therefore it will be marked normal below. */
2727 bool hot
= maybe_hot_count_p (NULL
, call_count
);
2731 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2732 node
->name (), node
->order
,
2733 hot
? "Function is hot" : "Function is normal");
2734 /* We only expect to miss profiles for functions that are reached
2735 via non-zero call edges in cases where the function may have
2736 been linked from another module or library (COMDATs and extern
2737 templates). See the comments below for handle_missing_profiles.
2738 Also, only warn in cases where the missing counts exceed the
2739 number of training runs. In certain cases with an execv followed
2740 by a no-return call the profile for the no-return call is not
2741 dumped and there can be a mismatch. */
2742 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
2743 && call_count
> profile_info
->runs
)
2745 if (flag_profile_correction
)
2749 "Missing counts for called function %s/%i\n",
2750 node
->name (), node
->order
);
2753 warning (0, "Missing counts for called function %s/%i",
2754 node
->name (), node
->order
);
2757 profile_status_for_fn (fn
)
2758 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2760 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2763 /* In the case of COMDAT routines, multiple object files will contain the same
2764 function and the linker will select one for the binary. In that case
2765 all the other copies from the profile instrument binary will be missing
2766 profile counts. Look for cases where this happened, due to non-zero
2767 call counts going to 0-count functions, and drop the profile to guessed
2768 so that we can use the estimated probabilities and avoid optimizing only
2771 The other case where the profile may be missing is when the routine
2772 is not going to be emitted to the object file, e.g. for "extern template"
2773 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2774 all other cases of non-zero calls to 0-count functions. */
2777 handle_missing_profiles (void)
2779 struct cgraph_node
*node
;
2780 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2781 vec
<struct cgraph_node
*> worklist
;
2782 worklist
.create (64);
2784 /* See if 0 count function has non-0 count callers. In this case we
2785 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2786 FOR_EACH_DEFINED_FUNCTION (node
)
2788 struct cgraph_edge
*e
;
2789 gcov_type call_count
= 0;
2790 gcov_type max_tp_first_run
= 0;
2791 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2795 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2797 call_count
+= e
->count
;
2799 if (e
->caller
->tp_first_run
> max_tp_first_run
)
2800 max_tp_first_run
= e
->caller
->tp_first_run
;
2803 /* If time profile is missing, let assign the maximum that comes from
2804 caller functions. */
2805 if (!node
->tp_first_run
&& max_tp_first_run
)
2806 node
->tp_first_run
= max_tp_first_run
+ 1;
2810 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2812 drop_profile (node
, call_count
);
2813 worklist
.safe_push (node
);
2817 /* Propagate the profile dropping to other 0-count COMDATs that are
2818 potentially called by COMDATs we already dropped the profile on. */
2819 while (worklist
.length () > 0)
2821 struct cgraph_edge
*e
;
2823 node
= worklist
.pop ();
2824 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2826 struct cgraph_node
*callee
= e
->callee
;
2827 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2829 if (callee
->count
> 0)
2831 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2832 && profile_status_for_fn (fn
) == PROFILE_READ
)
2834 drop_profile (node
, 0);
2835 worklist
.safe_push (callee
);
2839 worklist
.release ();
2842 /* Convert counts measured by profile driven feedback to frequencies.
2843 Return nonzero iff there was any nonzero execution count. */
2846 counts_to_freqs (void)
2848 gcov_type count_max
, true_count_max
= 0;
2851 /* Don't overwrite the estimated frequencies when the profile for
2852 the function is missing. We may drop this function PROFILE_GUESSED
2853 later in drop_profile (). */
2854 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
2857 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2858 true_count_max
= MAX (bb
->count
, true_count_max
);
2860 count_max
= MAX (true_count_max
, 1);
2861 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2862 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2864 return true_count_max
;
2867 /* Return true if function is likely to be expensive, so there is no point to
2868 optimize performance of prologue, epilogue or do inlining at the expense
2869 of code size growth. THRESHOLD is the limit of number of instructions
2870 function can execute at average to be still considered not expensive. */
2873 expensive_function_p (int threshold
)
2875 unsigned int sum
= 0;
2879 /* We can not compute accurately for large thresholds due to scaled
2881 gcc_assert (threshold
<= BB_FREQ_MAX
);
2883 /* Frequencies are out of range. This either means that function contains
2884 internal loop executing more than BB_FREQ_MAX times or profile feedback
2885 is available and function has not been executed at all. */
2886 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
2889 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2890 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
2891 FOR_EACH_BB_FN (bb
, cfun
)
2895 FOR_BB_INSNS (bb
, insn
)
2896 if (active_insn_p (insn
))
2898 sum
+= bb
->frequency
;
2907 /* Estimate and propagate basic block frequencies using the given branch
2908 probabilities. If FORCE is true, the frequencies are used to estimate
2909 the counts even when there are already non-zero profile counts. */
2912 estimate_bb_frequencies (bool force
)
2917 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
2919 static int real_values_initialized
= 0;
2921 if (!real_values_initialized
)
2923 real_values_initialized
= 1;
2924 sreal_init (&real_zero
, 0, 0);
2925 sreal_init (&real_one
, 1, 0);
2926 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2927 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2928 sreal_init (&real_one_half
, 1, -1);
2929 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2930 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2933 mark_dfs_back_edges ();
2935 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
2938 /* Set up block info for each basic block. */
2939 alloc_aux_for_blocks (sizeof (struct block_info_def
));
2940 alloc_aux_for_edges (sizeof (struct edge_info_def
));
2941 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2946 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2948 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2949 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2950 &EDGE_INFO (e
)->back_edge_prob
,
2951 &real_inv_br_prob_base
);
2955 /* First compute frequencies locally for each loop from innermost
2956 to outermost to examine frequencies for back edges. */
2959 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2960 FOR_EACH_BB_FN (bb
, cfun
)
2961 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2962 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2964 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
2965 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2969 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
2970 sreal_add (&tmp
, &tmp
, &real_one_half
);
2971 bb
->frequency
= sreal_to_int (&tmp
);
2974 free_aux_for_blocks ();
2975 free_aux_for_edges ();
2977 compute_function_frequency ();
2980 /* Decide whether function is hot, cold or unlikely executed. */
2982 compute_function_frequency (void)
2985 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2987 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2988 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2989 node
->only_called_at_startup
= true;
2990 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
2991 node
->only_called_at_exit
= true;
2993 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
2995 int flags
= flags_from_decl_or_type (current_function_decl
);
2996 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2998 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2999 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3001 node
->frequency
= NODE_FREQUENCY_HOT
;
3002 else if (flags
& ECF_NORETURN
)
3003 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3004 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3005 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3006 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3007 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3008 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3012 /* Only first time try to drop function into unlikely executed.
3013 After inlining the roundoff errors may confuse us.
3014 Ipa-profile pass will drop functions only called from unlikely
3015 functions to unlikely and that is most of what we care about. */
3016 if (!cfun
->after_inlining
)
3017 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3018 FOR_EACH_BB_FN (bb
, cfun
)
3020 if (maybe_hot_bb_p (cfun
, bb
))
3022 node
->frequency
= NODE_FREQUENCY_HOT
;
3025 if (!probably_never_executed_bb_p (cfun
, bb
))
3026 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3030 /* Build PREDICT_EXPR. */
3032 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3034 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3035 build_int_cst (integer_type_node
, predictor
));
3036 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3041 predictor_name (enum br_predictor predictor
)
3043 return predictor_info
[predictor
].name
;
3046 /* Predict branch probabilities and estimate profile of the tree CFG. */
3050 const pass_data pass_data_profile
=
3052 GIMPLE_PASS
, /* type */
3053 "profile_estimate", /* name */
3054 OPTGROUP_NONE
, /* optinfo_flags */
3055 TV_BRANCH_PROB
, /* tv_id */
3056 PROP_cfg
, /* properties_required */
3057 0, /* properties_provided */
3058 0, /* properties_destroyed */
3059 0, /* todo_flags_start */
3060 0, /* todo_flags_finish */
3063 class pass_profile
: public gimple_opt_pass
3066 pass_profile (gcc::context
*ctxt
)
3067 : gimple_opt_pass (pass_data_profile
, ctxt
)
3070 /* opt_pass methods: */
3071 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3072 virtual unsigned int execute (function
*);
3074 }; // class pass_profile
3077 pass_profile::execute (function
*fun
)
3081 loop_optimizer_init (LOOPS_NORMAL
);
3082 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3083 flow_loops_dump (dump_file
, NULL
, 0);
3085 mark_irreducible_loops ();
3087 nb_loops
= number_of_loops (fun
);
3091 tree_estimate_probability ();
3096 loop_optimizer_finalize ();
3097 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3098 gimple_dump_cfg (dump_file
, dump_flags
);
3099 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3100 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3107 make_pass_profile (gcc::context
*ctxt
)
3109 return new pass_profile (ctxt
);
3114 const pass_data pass_data_strip_predict_hints
=
3116 GIMPLE_PASS
, /* type */
3117 "*strip_predict_hints", /* name */
3118 OPTGROUP_NONE
, /* optinfo_flags */
3119 TV_BRANCH_PROB
, /* tv_id */
3120 PROP_cfg
, /* properties_required */
3121 0, /* properties_provided */
3122 0, /* properties_destroyed */
3123 0, /* todo_flags_start */
3124 0, /* todo_flags_finish */
3127 class pass_strip_predict_hints
: public gimple_opt_pass
3130 pass_strip_predict_hints (gcc::context
*ctxt
)
3131 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3134 /* opt_pass methods: */
3135 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3136 virtual unsigned int execute (function
*);
3138 }; // class pass_strip_predict_hints
3140 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3141 we no longer need. */
3143 pass_strip_predict_hints::execute (function
*fun
)
3149 FOR_EACH_BB_FN (bb
, fun
)
3151 gimple_stmt_iterator bi
;
3152 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3154 gimple stmt
= gsi_stmt (bi
);
3156 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3158 gsi_remove (&bi
, true);
3161 else if (is_gimple_call (stmt
))
3163 tree fndecl
= gimple_call_fndecl (stmt
);
3166 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3167 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3168 && gimple_call_num_args (stmt
) == 2)
3169 || (gimple_call_internal_p (stmt
)
3170 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3172 var
= gimple_call_lhs (stmt
);
3176 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3177 gsi_replace (&bi
, ass_stmt
, true);
3181 gsi_remove (&bi
, true);
3195 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3197 return new pass_strip_predict_hints (ctxt
);
3200 /* Rebuild function frequencies. Passes are in general expected to
3201 maintain profile by hand, however in some cases this is not possible:
3202 for example when inlining several functions with loops freuqencies might run
3203 out of scale and thus needs to be recomputed. */
3206 rebuild_frequencies (void)
3208 timevar_push (TV_REBUILD_FREQUENCIES
);
3210 /* When the max bb count in the function is small, there is a higher
3211 chance that there were truncation errors in the integer scaling
3212 of counts by inlining and other optimizations. This could lead
3213 to incorrect classification of code as being cold when it isn't.
3214 In that case, force the estimation of bb counts/frequencies from the
3215 branch probabilities, rather than computing frequencies from counts,
3216 which may also lead to frequencies incorrectly reduced to 0. There
3217 is less precision in the probabilities, so we only do this for small
3219 gcov_type count_max
= 0;
3221 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3222 count_max
= MAX (bb
->count
, count_max
);
3224 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3225 || (profile_status_for_fn (cfun
) == PROFILE_READ
&& count_max
< REG_BR_PROB_BASE
/10))
3227 loop_optimizer_init (0);
3228 add_noreturn_fake_exit_edges ();
3229 mark_irreducible_loops ();
3230 connect_infinite_loops_to_exit ();
3231 estimate_bb_frequencies (true);
3232 remove_fake_exit_edges ();
3233 loop_optimizer_finalize ();
3235 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3239 timevar_pop (TV_REBUILD_FREQUENCIES
);