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_insn
*, 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_insn
*);
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_edge::maybe_hot_p (void)
192 if (profile_info
&& flag_branch_probabilities
193 && !maybe_hot_count_p (NULL
, count
))
195 if (caller
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
197 && callee
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
199 if (caller
->frequency
> NODE_FREQUENCY_UNLIKELY_EXECUTED
201 && callee
->frequency
<= NODE_FREQUENCY_EXECUTED_ONCE
))
205 if (caller
->frequency
== NODE_FREQUENCY_HOT
)
207 if (caller
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
208 && frequency
< CGRAPH_FREQ_BASE
* 3 / 2)
210 if (flag_guess_branch_prob
)
212 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0
213 || frequency
<= (CGRAPH_FREQ_BASE
214 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
220 /* Return true in case BB can be CPU intensive and should be optimized
221 for maximal performance. */
224 maybe_hot_edge_p (edge e
)
226 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
227 return maybe_hot_count_p (cfun
, e
->count
);
228 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
233 /* Return true if profile COUNT and FREQUENCY, or function FUN static
234 node frequency reflects never being executed. */
237 probably_never_executed (struct function
*fun
,
238 gcov_type count
, int frequency
)
240 gcc_checking_assert (fun
);
241 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
243 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
244 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
248 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
250 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
252 gcov_type computed_count
;
253 /* Check for possibility of overflow, in which case entry bb count
254 is large enough to do the division first without losing much
256 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
< REG_BR_PROB_BASE
*
259 gcov_type scaled_count
260 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
*
261 unlikely_count_fraction
;
262 computed_count
= RDIV (scaled_count
,
263 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
);
267 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
,
268 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
);
269 computed_count
*= frequency
* unlikely_count_fraction
;
271 if (computed_count
>= profile_info
->runs
)
276 if ((!profile_info
|| !flag_branch_probabilities
)
277 && (cgraph_node::get (fun
->decl
)->frequency
278 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
284 /* Return true in case BB is probably never executed. */
287 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
289 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
293 /* Return true in case edge E is probably never executed. */
296 probably_never_executed_edge_p (struct function
*fun
, edge e
)
298 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
301 /* Return true if function should be optimized for size. */
304 cgraph_node::optimize_for_size_p (void)
308 if (frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
314 /* Return true when current function should always be optimized for size. */
317 optimize_function_for_size_p (struct function
*fun
)
321 if (!fun
|| !fun
->decl
)
324 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
325 return n
&& n
->optimize_for_size_p ();
328 /* Return true when current function should always be optimized for speed. */
331 optimize_function_for_speed_p (struct function
*fun
)
333 return !optimize_function_for_size_p (fun
);
336 /* Return TRUE when BB should be optimized for size. */
339 optimize_bb_for_size_p (const_basic_block bb
)
341 return (optimize_function_for_size_p (cfun
)
342 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
345 /* Return TRUE when BB should be optimized for speed. */
348 optimize_bb_for_speed_p (const_basic_block bb
)
350 return !optimize_bb_for_size_p (bb
);
353 /* Return TRUE when BB should be optimized for size. */
356 optimize_edge_for_size_p (edge e
)
358 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
361 /* Return TRUE when BB should be optimized for speed. */
364 optimize_edge_for_speed_p (edge e
)
366 return !optimize_edge_for_size_p (e
);
369 /* Return TRUE when BB should be optimized for size. */
372 optimize_insn_for_size_p (void)
374 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
377 /* Return TRUE when BB should be optimized for speed. */
380 optimize_insn_for_speed_p (void)
382 return !optimize_insn_for_size_p ();
385 /* Return TRUE when LOOP should be optimized for size. */
388 optimize_loop_for_size_p (struct loop
*loop
)
390 return optimize_bb_for_size_p (loop
->header
);
393 /* Return TRUE when LOOP should be optimized for speed. */
396 optimize_loop_for_speed_p (struct loop
*loop
)
398 return optimize_bb_for_speed_p (loop
->header
);
401 /* Return TRUE when LOOP nest should be optimized for speed. */
404 optimize_loop_nest_for_speed_p (struct loop
*loop
)
406 struct loop
*l
= loop
;
407 if (optimize_loop_for_speed_p (loop
))
410 while (l
&& l
!= loop
)
412 if (optimize_loop_for_speed_p (l
))
420 while (l
!= loop
&& !l
->next
)
429 /* Return TRUE when LOOP nest should be optimized for size. */
432 optimize_loop_nest_for_size_p (struct loop
*loop
)
434 return !optimize_loop_nest_for_speed_p (loop
);
437 /* Return true when edge E is likely to be well predictable by branch
441 predictable_edge_p (edge e
)
443 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
446 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
447 || (REG_BR_PROB_BASE
- e
->probability
448 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
454 /* Set RTL expansion for BB profile. */
457 rtl_profile_for_bb (basic_block bb
)
459 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
462 /* Set RTL expansion for edge profile. */
465 rtl_profile_for_edge (edge e
)
467 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
470 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
472 default_rtl_profile (void)
474 crtl
->maybe_hot_insn_p
= true;
477 /* Return true if the one of outgoing edges is already predicted by
481 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
484 if (!INSN_P (BB_END (bb
)))
486 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
487 if (REG_NOTE_KIND (note
) == REG_BR_PRED
488 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
493 /* Structure representing predictions in tree level. */
495 struct edge_prediction
{
496 struct edge_prediction
*ep_next
;
498 enum br_predictor ep_predictor
;
502 /* This map contains for a basic block the list of predictions for the
505 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
507 /* Return true if the one of outgoing edges is already predicted by
511 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
513 struct edge_prediction
*i
;
514 edge_prediction
**preds
= bb_predictions
->get (bb
);
519 for (i
= *preds
; i
; i
= i
->ep_next
)
520 if (i
->ep_predictor
== predictor
)
525 /* Return true when the probability of edge is reliable.
527 The profile guessing code is good at predicting branch outcome (ie.
528 taken/not taken), that is predicted right slightly over 75% of time.
529 It is however notoriously poor on predicting the probability itself.
530 In general the profile appear a lot flatter (with probabilities closer
531 to 50%) than the reality so it is bad idea to use it to drive optimization
532 such as those disabling dynamic branch prediction for well predictable
535 There are two exceptions - edges leading to noreturn edges and edges
536 predicted by number of iterations heuristics are predicted well. This macro
537 should be able to distinguish those, but at the moment it simply check for
538 noreturn heuristic that is only one giving probability over 99% or bellow
539 1%. In future we might want to propagate reliability information across the
540 CFG if we find this information useful on multiple places. */
542 probability_reliable_p (int prob
)
544 return (profile_status_for_fn (cfun
) == PROFILE_READ
545 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
546 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
549 /* Same predicate as above, working on edges. */
551 edge_probability_reliable_p (const_edge e
)
553 return probability_reliable_p (e
->probability
);
556 /* Same predicate as edge_probability_reliable_p, working on notes. */
558 br_prob_note_reliable_p (const_rtx note
)
560 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
561 return probability_reliable_p (XINT (note
, 0));
565 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
567 gcc_assert (any_condjump_p (insn
));
568 if (!flag_guess_branch_prob
)
571 add_reg_note (insn
, REG_BR_PRED
,
572 gen_rtx_CONCAT (VOIDmode
,
573 GEN_INT ((int) predictor
),
574 GEN_INT ((int) probability
)));
577 /* Predict insn by given predictor. */
580 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
581 enum prediction taken
)
583 int probability
= predictor_info
[(int) predictor
].hitrate
;
586 probability
= REG_BR_PROB_BASE
- probability
;
588 predict_insn (insn
, predictor
, probability
);
591 /* Predict edge E with given probability if possible. */
594 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
597 last_insn
= BB_END (e
->src
);
599 /* We can store the branch prediction information only about
600 conditional jumps. */
601 if (!any_condjump_p (last_insn
))
604 /* We always store probability of branching. */
605 if (e
->flags
& EDGE_FALLTHRU
)
606 probability
= REG_BR_PROB_BASE
- probability
;
608 predict_insn (last_insn
, predictor
, probability
);
611 /* Predict edge E with the given PROBABILITY. */
613 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
615 gcc_assert (profile_status_for_fn (cfun
) != PROFILE_GUESSED
);
616 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && EDGE_COUNT (e
->src
->succs
) >
618 && flag_guess_branch_prob
&& optimize
)
620 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
621 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
625 i
->ep_probability
= probability
;
626 i
->ep_predictor
= predictor
;
631 /* Remove all predictions on given basic block that are attached
634 remove_predictions_associated_with_edge (edge e
)
639 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
643 struct edge_prediction
**prediction
= preds
;
644 struct edge_prediction
*next
;
648 if ((*prediction
)->ep_edge
== e
)
650 next
= (*prediction
)->ep_next
;
655 prediction
= &((*prediction
)->ep_next
);
660 /* Clears the list of predictions stored for BB. */
663 clear_bb_predictions (basic_block bb
)
665 edge_prediction
**preds
= bb_predictions
->get (bb
);
666 struct edge_prediction
*pred
, *next
;
671 for (pred
= *preds
; pred
; pred
= next
)
673 next
= pred
->ep_next
;
679 /* Return true when we can store prediction on insn INSN.
680 At the moment we represent predictions only on conditional
681 jumps, not at computed jump or other complicated cases. */
683 can_predict_insn_p (const rtx_insn
*insn
)
685 return (JUMP_P (insn
)
686 && any_condjump_p (insn
)
687 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
690 /* Predict edge E by given predictor if possible. */
693 predict_edge_def (edge e
, enum br_predictor predictor
,
694 enum prediction taken
)
696 int probability
= predictor_info
[(int) predictor
].hitrate
;
699 probability
= REG_BR_PROB_BASE
- probability
;
701 predict_edge (e
, predictor
, probability
);
704 /* Invert all branch predictions or probability notes in the INSN. This needs
705 to be done each time we invert the condition used by the jump. */
708 invert_br_probabilities (rtx insn
)
712 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
713 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
714 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
715 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
716 XEXP (XEXP (note
, 0), 1)
717 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
720 /* Dump information about the branch prediction to the output file. */
723 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
724 basic_block bb
, int used
)
732 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
733 if (! (e
->flags
& EDGE_FALLTHRU
))
736 fprintf (file
, " %s heuristics%s: %.1f%%",
737 predictor_info
[predictor
].name
,
738 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
742 fprintf (file
, " exec %"PRId64
, bb
->count
);
745 fprintf (file
, " hit %"PRId64
, e
->count
);
746 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
750 fprintf (file
, "\n");
753 /* We can not predict the probabilities of outgoing edges of bb. Set them
754 evenly and hope for the best. */
756 set_even_probabilities (basic_block bb
)
762 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
763 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
765 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
766 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
767 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
772 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
773 note if not already present. Remove now useless REG_BR_PRED notes. */
776 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
781 int best_probability
= PROB_EVEN
;
782 enum br_predictor best_predictor
= END_PREDICTORS
;
783 int combined_probability
= REG_BR_PROB_BASE
/ 2;
785 bool first_match
= false;
788 if (!can_predict_insn_p (insn
))
790 set_even_probabilities (bb
);
794 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
795 pnote
= ®_NOTES (insn
);
797 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
800 /* We implement "first match" heuristics and use probability guessed
801 by predictor with smallest index. */
802 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
803 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
805 enum br_predictor predictor
= ((enum br_predictor
)
806 INTVAL (XEXP (XEXP (note
, 0), 0)));
807 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
810 if (best_predictor
> predictor
)
811 best_probability
= probability
, best_predictor
= predictor
;
813 d
= (combined_probability
* probability
814 + (REG_BR_PROB_BASE
- combined_probability
)
815 * (REG_BR_PROB_BASE
- probability
));
817 /* Use FP math to avoid overflows of 32bit integers. */
819 /* If one probability is 0% and one 100%, avoid division by zero. */
820 combined_probability
= REG_BR_PROB_BASE
/ 2;
822 combined_probability
= (((double) combined_probability
) * probability
823 * REG_BR_PROB_BASE
/ d
+ 0.5);
826 /* Decide which heuristic to use. In case we didn't match anything,
827 use no_prediction heuristic, in case we did match, use either
828 first match or Dempster-Shaffer theory depending on the flags. */
830 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
834 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
835 combined_probability
, bb
, true);
838 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
840 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
845 combined_probability
= best_probability
;
846 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
850 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
852 enum br_predictor predictor
= ((enum br_predictor
)
853 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
854 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
856 dump_prediction (dump_file
, predictor
, probability
, bb
,
857 !first_match
|| best_predictor
== predictor
);
858 *pnote
= XEXP (*pnote
, 1);
861 pnote
= &XEXP (*pnote
, 1);
866 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
868 /* Save the prediction into CFG in case we are seeing non-degenerated
870 if (!single_succ_p (bb
))
872 BRANCH_EDGE (bb
)->probability
= combined_probability
;
873 FALLTHRU_EDGE (bb
)->probability
874 = REG_BR_PROB_BASE
- combined_probability
;
877 else if (!single_succ_p (bb
))
879 int prob
= XINT (prob_note
, 0);
881 BRANCH_EDGE (bb
)->probability
= prob
;
882 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
885 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
888 /* Combine predictions into single probability and store them into CFG.
889 Remove now useless prediction entries. */
892 combine_predictions_for_bb (basic_block bb
)
894 int best_probability
= PROB_EVEN
;
895 enum br_predictor best_predictor
= END_PREDICTORS
;
896 int combined_probability
= REG_BR_PROB_BASE
/ 2;
898 bool first_match
= false;
900 struct edge_prediction
*pred
;
902 edge e
, first
= NULL
, second
= NULL
;
905 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
906 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
909 if (first
&& !second
)
915 /* When there is no successor or only one choice, prediction is easy.
917 We are lazy for now and predict only basic blocks with two outgoing
918 edges. It is possible to predict generic case too, but we have to
919 ignore first match heuristics and do more involved combining. Implement
924 set_even_probabilities (bb
);
925 clear_bb_predictions (bb
);
927 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
933 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
935 edge_prediction
**preds
= bb_predictions
->get (bb
);
938 /* We implement "first match" heuristics and use probability guessed
939 by predictor with smallest index. */
940 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
942 enum br_predictor predictor
= pred
->ep_predictor
;
943 int probability
= pred
->ep_probability
;
945 if (pred
->ep_edge
!= first
)
946 probability
= REG_BR_PROB_BASE
- probability
;
949 /* First match heuristics would be widly confused if we predicted
951 if (best_predictor
> predictor
)
953 struct edge_prediction
*pred2
;
954 int prob
= probability
;
956 for (pred2
= (struct edge_prediction
*) *preds
;
957 pred2
; pred2
= pred2
->ep_next
)
958 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
960 int probability2
= pred
->ep_probability
;
962 if (pred2
->ep_edge
!= first
)
963 probability2
= REG_BR_PROB_BASE
- probability2
;
965 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
966 (probability2
< REG_BR_PROB_BASE
/ 2))
969 /* If the same predictor later gave better result, go for it! */
970 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
971 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
975 best_probability
= prob
, best_predictor
= predictor
;
978 d
= (combined_probability
* probability
979 + (REG_BR_PROB_BASE
- combined_probability
)
980 * (REG_BR_PROB_BASE
- probability
));
982 /* Use FP math to avoid overflows of 32bit integers. */
984 /* If one probability is 0% and one 100%, avoid division by zero. */
985 combined_probability
= REG_BR_PROB_BASE
/ 2;
987 combined_probability
= (((double) combined_probability
)
989 * REG_BR_PROB_BASE
/ d
+ 0.5);
993 /* Decide which heuristic to use. In case we didn't match anything,
994 use no_prediction heuristic, in case we did match, use either
995 first match or Dempster-Shaffer theory depending on the flags. */
997 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1001 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
1004 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1006 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1011 combined_probability
= best_probability
;
1012 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
1016 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1018 enum br_predictor predictor
= pred
->ep_predictor
;
1019 int probability
= pred
->ep_probability
;
1021 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
1022 probability
= REG_BR_PROB_BASE
- probability
;
1023 dump_prediction (dump_file
, predictor
, probability
, bb
,
1024 !first_match
|| best_predictor
== predictor
);
1027 clear_bb_predictions (bb
);
1031 first
->probability
= combined_probability
;
1032 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1036 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1037 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1039 T1 and T2 should be one of the following cases:
1040 1. T1 is SSA_NAME, T2 is NULL
1041 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1042 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1045 strips_small_constant (tree t1
, tree t2
)
1052 else if (TREE_CODE (t1
) == SSA_NAME
)
1054 else if (tree_fits_shwi_p (t1
))
1055 value
= tree_to_shwi (t1
);
1061 else if (tree_fits_shwi_p (t2
))
1062 value
= tree_to_shwi (t2
);
1063 else if (TREE_CODE (t2
) == SSA_NAME
)
1071 if (value
<= 4 && value
>= -4)
1077 /* Return the SSA_NAME in T or T's operands.
1078 Return NULL if SSA_NAME cannot be found. */
1081 get_base_value (tree t
)
1083 if (TREE_CODE (t
) == SSA_NAME
)
1086 if (!BINARY_CLASS_P (t
))
1089 switch (TREE_OPERAND_LENGTH (t
))
1092 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1094 return strips_small_constant (TREE_OPERAND (t
, 0),
1095 TREE_OPERAND (t
, 1));
1101 /* Check the compare STMT in LOOP. If it compares an induction
1102 variable to a loop invariant, return true, and save
1103 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1104 Otherwise return false and set LOOP_INVAIANT to NULL. */
1107 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1108 tree
*loop_invariant
,
1109 enum tree_code
*compare_code
,
1113 tree op0
, op1
, bound
, base
;
1115 enum tree_code code
;
1118 code
= gimple_cond_code (stmt
);
1119 *loop_invariant
= NULL
;
1135 op0
= gimple_cond_lhs (stmt
);
1136 op1
= gimple_cond_rhs (stmt
);
1138 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1139 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1141 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1143 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1145 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1146 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1148 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1149 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1152 if (integer_zerop (iv0
.step
))
1154 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1155 code
= invert_tree_comparison (code
, false);
1158 if (tree_fits_shwi_p (iv1
.step
))
1167 if (tree_fits_shwi_p (iv0
.step
))
1173 if (TREE_CODE (bound
) != INTEGER_CST
)
1174 bound
= get_base_value (bound
);
1177 if (TREE_CODE (base
) != INTEGER_CST
)
1178 base
= get_base_value (base
);
1182 *loop_invariant
= bound
;
1183 *compare_code
= code
;
1185 *loop_iv_base
= base
;
1189 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1192 expr_coherent_p (tree t1
, tree t2
)
1195 tree ssa_name_1
= NULL
;
1196 tree ssa_name_2
= NULL
;
1198 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1199 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1204 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1206 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1209 /* Check to see if t1 is expressed/defined with t2. */
1210 stmt
= SSA_NAME_DEF_STMT (t1
);
1211 gcc_assert (stmt
!= NULL
);
1212 if (is_gimple_assign (stmt
))
1214 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1215 if (ssa_name_1
&& ssa_name_1
== t2
)
1219 /* Check to see if t2 is expressed/defined with t1. */
1220 stmt
= SSA_NAME_DEF_STMT (t2
);
1221 gcc_assert (stmt
!= NULL
);
1222 if (is_gimple_assign (stmt
))
1224 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1225 if (ssa_name_2
&& ssa_name_2
== t1
)
1229 /* Compare if t1 and t2's def_stmts are identical. */
1230 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1236 /* Predict branch probability of BB when BB contains a branch that compares
1237 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1238 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1241 for (int i = 0; i < bound; i++) {
1248 In this loop, we will predict the branch inside the loop to be taken. */
1251 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1252 tree loop_bound_var
,
1253 tree loop_iv_base_var
,
1254 enum tree_code loop_bound_code
,
1255 int loop_bound_step
)
1258 tree compare_var
, compare_base
;
1259 enum tree_code compare_code
;
1260 tree compare_step_var
;
1264 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1265 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1266 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1269 stmt
= last_stmt (bb
);
1270 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1272 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
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
;
1446 gimple lhs_def_stmt
;
1448 tree cmp_rhs
, cmp_lhs
;
1452 last
= last_stmt (exit_edge
->src
);
1455 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1459 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1460 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1461 if (!TREE_CONSTANT (cmp_rhs
)
1462 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1464 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1467 /* If check_value_one is true, only the phi_args with value '1' will lead
1468 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1470 check_value_one
= (((integer_onep (cmp_rhs
))
1471 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1472 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1474 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1478 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1482 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1486 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1487 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1489 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1491 if ((check_value_one
^ integer_onep (val
)) == 1)
1493 if (EDGE_COUNT (e
->src
->succs
) != 1)
1495 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1499 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1500 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1504 /* Predict edge probabilities by exploiting loop structure. */
1507 predict_loops (void)
1511 /* Try to predict out blocks in a loop that are not part of a
1513 FOR_EACH_LOOP (loop
, 0)
1515 basic_block bb
, *bbs
;
1516 unsigned j
, n_exits
;
1518 struct tree_niter_desc niter_desc
;
1520 struct nb_iter_bound
*nb_iter
;
1521 enum tree_code loop_bound_code
= ERROR_MARK
;
1522 tree loop_bound_step
= NULL
;
1523 tree loop_bound_var
= NULL
;
1524 tree loop_iv_base
= NULL
;
1527 exits
= get_loop_exit_edges (loop
);
1528 n_exits
= exits
.length ();
1535 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1538 HOST_WIDE_INT nitercst
;
1539 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1541 enum br_predictor predictor
;
1543 predict_extra_loop_exits (ex
);
1545 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1546 niter
= niter_desc
.niter
;
1547 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1548 niter
= loop_niter_by_eval (loop
, ex
);
1550 if (TREE_CODE (niter
) == INTEGER_CST
)
1552 if (tree_fits_uhwi_p (niter
)
1554 && compare_tree_int (niter
, max
- 1) == -1)
1555 nitercst
= tree_to_uhwi (niter
) + 1;
1558 predictor
= PRED_LOOP_ITERATIONS
;
1560 /* If we have just one exit and we can derive some information about
1561 the number of iterations of the loop from the statements inside
1562 the loop, use it to predict this exit. */
1563 else if (n_exits
== 1)
1565 nitercst
= estimated_stmt_executions_int (loop
);
1571 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1576 /* If the prediction for number of iterations is zero, do not
1577 predict the exit edges. */
1581 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1582 predict_edge (ex
, predictor
, probability
);
1586 /* Find information about loop bound variables. */
1587 for (nb_iter
= loop
->bounds
; nb_iter
;
1588 nb_iter
= nb_iter
->next
)
1590 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1592 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1595 if (!stmt
&& last_stmt (loop
->header
)
1596 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1597 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1599 is_comparison_with_loop_invariant_p (stmt
, loop
,
1605 bbs
= get_loop_body (loop
);
1607 for (j
= 0; j
< loop
->num_nodes
; j
++)
1609 int header_found
= 0;
1615 /* Bypass loop heuristics on continue statement. These
1616 statements construct loops via "non-loop" constructs
1617 in the source language and are better to be handled
1619 if (predicted_by_p (bb
, PRED_CONTINUE
))
1622 /* Loop branch heuristics - predict an edge back to a
1623 loop's head as taken. */
1624 if (bb
== loop
->latch
)
1626 e
= find_edge (loop
->latch
, loop
->header
);
1630 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1634 /* Loop exit heuristics - predict an edge exiting the loop if the
1635 conditional has no loop header successors as not taken. */
1637 /* If we already used more reliable loop exit predictors, do not
1638 bother with PRED_LOOP_EXIT. */
1639 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1640 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1642 /* For loop with many exits we don't want to predict all exits
1643 with the pretty large probability, because if all exits are
1644 considered in row, the loop would be predicted to iterate
1645 almost never. The code to divide probability by number of
1646 exits is very rough. It should compute the number of exits
1647 taken in each patch through function (not the overall number
1648 of exits that might be a lot higher for loops with wide switch
1649 statements in them) and compute n-th square root.
1651 We limit the minimal probability by 2% to avoid
1652 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1653 as this was causing regression in perl benchmark containing such
1656 int probability
= ((REG_BR_PROB_BASE
1657 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1659 if (probability
< HITRATE (2))
1660 probability
= HITRATE (2);
1661 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1662 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1663 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1664 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1667 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1669 tree_to_shwi (loop_bound_step
));
1672 /* Free basic blocks from get_loop_body. */
1677 /* Attempt to predict probabilities of BB outgoing edges using local
1680 bb_estimate_probability_locally (basic_block bb
)
1682 rtx_insn
*last_insn
= BB_END (bb
);
1685 if (! can_predict_insn_p (last_insn
))
1687 cond
= get_condition (last_insn
, NULL
, false, false);
1691 /* Try "pointer heuristic."
1692 A comparison ptr == 0 is predicted as false.
1693 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1694 if (COMPARISON_P (cond
)
1695 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1696 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1698 if (GET_CODE (cond
) == EQ
)
1699 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1700 else if (GET_CODE (cond
) == NE
)
1701 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1705 /* Try "opcode heuristic."
1706 EQ tests are usually false and NE tests are usually true. Also,
1707 most quantities are positive, so we can make the appropriate guesses
1708 about signed comparisons against zero. */
1709 switch (GET_CODE (cond
))
1712 /* Unconditional branch. */
1713 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1714 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1719 /* Floating point comparisons appears to behave in a very
1720 unpredictable way because of special role of = tests in
1722 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1724 /* Comparisons with 0 are often used for booleans and there is
1725 nothing useful to predict about them. */
1726 else if (XEXP (cond
, 1) == const0_rtx
1727 || XEXP (cond
, 0) == const0_rtx
)
1730 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1735 /* Floating point comparisons appears to behave in a very
1736 unpredictable way because of special role of = tests in
1738 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1740 /* Comparisons with 0 are often used for booleans and there is
1741 nothing useful to predict about them. */
1742 else if (XEXP (cond
, 1) == const0_rtx
1743 || XEXP (cond
, 0) == const0_rtx
)
1746 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1750 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1754 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1759 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1760 || XEXP (cond
, 1) == constm1_rtx
)
1761 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1766 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1767 || XEXP (cond
, 1) == constm1_rtx
)
1768 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1776 /* Set edge->probability for each successor edge of BB. */
1778 guess_outgoing_edge_probabilities (basic_block bb
)
1780 bb_estimate_probability_locally (bb
);
1781 combine_predictions_for_insn (BB_END (bb
), bb
);
1784 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
1786 /* Helper function for expr_expected_value. */
1789 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1790 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
1795 *predictor
= PRED_UNCONDITIONAL
;
1797 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1799 if (TREE_CONSTANT (op0
))
1802 if (code
!= SSA_NAME
)
1805 def
= SSA_NAME_DEF_STMT (op0
);
1807 /* If we were already here, break the infinite cycle. */
1808 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1811 if (gimple_code (def
) == GIMPLE_PHI
)
1813 /* All the arguments of the PHI node must have the same constant
1815 int i
, n
= gimple_phi_num_args (def
);
1816 tree val
= NULL
, new_val
;
1818 for (i
= 0; i
< n
; i
++)
1820 tree arg
= PHI_ARG_DEF (def
, i
);
1821 enum br_predictor predictor2
;
1823 /* If this PHI has itself as an argument, we cannot
1824 determine the string length of this argument. However,
1825 if we can find an expected constant value for the other
1826 PHI args then we can still be sure that this is
1827 likely a constant. So be optimistic and just
1828 continue with the next argument. */
1829 if (arg
== PHI_RESULT (def
))
1832 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
1834 /* It is difficult to combine value predictors. Simply assume
1835 that later predictor is weaker and take its prediction. */
1836 if (predictor
&& *predictor
< predictor2
)
1837 *predictor
= predictor2
;
1842 else if (!operand_equal_p (val
, new_val
, false))
1847 if (is_gimple_assign (def
))
1849 if (gimple_assign_lhs (def
) != op0
)
1852 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1853 gimple_assign_rhs1 (def
),
1854 gimple_assign_rhs_code (def
),
1855 gimple_assign_rhs2 (def
),
1856 visited
, predictor
);
1859 if (is_gimple_call (def
))
1861 tree decl
= gimple_call_fndecl (def
);
1864 if (gimple_call_internal_p (def
)
1865 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
1867 gcc_assert (gimple_call_num_args (def
) == 3);
1868 tree val
= gimple_call_arg (def
, 0);
1869 if (TREE_CONSTANT (val
))
1873 tree val2
= gimple_call_arg (def
, 2);
1874 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
1875 && tree_fits_uhwi_p (val2
)
1876 && tree_to_uhwi (val2
) < END_PREDICTORS
);
1877 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
1879 return gimple_call_arg (def
, 1);
1883 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1884 switch (DECL_FUNCTION_CODE (decl
))
1886 case BUILT_IN_EXPECT
:
1889 if (gimple_call_num_args (def
) != 2)
1891 val
= gimple_call_arg (def
, 0);
1892 if (TREE_CONSTANT (val
))
1895 *predictor
= PRED_BUILTIN_EXPECT
;
1896 return gimple_call_arg (def
, 1);
1899 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1900 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1901 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1902 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1903 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1904 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1905 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1906 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1907 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1908 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1909 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1910 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1911 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1912 /* Assume that any given atomic operation has low contention,
1913 and thus the compare-and-swap operation succeeds. */
1915 *predictor
= PRED_COMPARE_AND_SWAP
;
1916 return boolean_true_node
;
1925 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1928 enum br_predictor predictor2
;
1929 op0
= expr_expected_value (op0
, visited
, predictor
);
1932 op1
= expr_expected_value (op1
, visited
, &predictor2
);
1933 if (predictor
&& *predictor
< predictor2
)
1934 *predictor
= predictor2
;
1937 res
= fold_build2 (code
, type
, op0
, op1
);
1938 if (TREE_CONSTANT (res
))
1942 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1945 op0
= expr_expected_value (op0
, visited
, predictor
);
1948 res
= fold_build1 (code
, type
, op0
);
1949 if (TREE_CONSTANT (res
))
1956 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1957 The function is used by builtin_expect branch predictor so the evidence
1958 must come from this construct and additional possible constant folding.
1960 We may want to implement more involved value guess (such as value range
1961 propagation based prediction), but such tricks shall go to new
1965 expr_expected_value (tree expr
, bitmap visited
,
1966 enum br_predictor
*predictor
)
1968 enum tree_code code
;
1971 if (TREE_CONSTANT (expr
))
1974 *predictor
= PRED_UNCONDITIONAL
;
1978 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1979 return expr_expected_value_1 (TREE_TYPE (expr
),
1980 op0
, code
, op1
, visited
, predictor
);
1983 /* Predict using opcode of the last statement in basic block. */
1985 tree_predict_by_opcode (basic_block bb
)
1987 gimple stmt
= last_stmt (bb
);
1995 enum br_predictor predictor
;
1997 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1999 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2000 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2002 op0
= gimple_cond_lhs (stmt
);
2003 op1
= gimple_cond_rhs (stmt
);
2004 cmp
= gimple_cond_code (stmt
);
2005 type
= TREE_TYPE (op0
);
2006 visited
= BITMAP_ALLOC (NULL
);
2007 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
2009 BITMAP_FREE (visited
);
2010 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2012 if (predictor
== PRED_BUILTIN_EXPECT
)
2014 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2016 gcc_assert (percent
>= 0 && percent
<= 100);
2017 if (integer_zerop (val
))
2018 percent
= 100 - percent
;
2019 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2022 predict_edge (then_edge
, predictor
,
2023 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2025 /* Try "pointer heuristic."
2026 A comparison ptr == 0 is predicted as false.
2027 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2028 if (POINTER_TYPE_P (type
))
2031 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2032 else if (cmp
== NE_EXPR
)
2033 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2037 /* Try "opcode heuristic."
2038 EQ tests are usually false and NE tests are usually true. Also,
2039 most quantities are positive, so we can make the appropriate guesses
2040 about signed comparisons against zero. */
2045 /* Floating point comparisons appears to behave in a very
2046 unpredictable way because of special role of = tests in
2048 if (FLOAT_TYPE_P (type
))
2050 /* Comparisons with 0 are often used for booleans and there is
2051 nothing useful to predict about them. */
2052 else if (integer_zerop (op0
) || integer_zerop (op1
))
2055 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2060 /* Floating point comparisons appears to behave in a very
2061 unpredictable way because of special role of = tests in
2063 if (FLOAT_TYPE_P (type
))
2065 /* Comparisons with 0 are often used for booleans and there is
2066 nothing useful to predict about them. */
2067 else if (integer_zerop (op0
)
2068 || integer_zerop (op1
))
2071 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2075 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2078 case UNORDERED_EXPR
:
2079 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2084 if (integer_zerop (op1
)
2085 || integer_onep (op1
)
2086 || integer_all_onesp (op1
)
2089 || real_minus_onep (op1
))
2090 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2095 if (integer_zerop (op1
)
2096 || integer_onep (op1
)
2097 || integer_all_onesp (op1
)
2100 || real_minus_onep (op1
))
2101 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2109 /* Try to guess whether the value of return means error code. */
2111 static enum br_predictor
2112 return_prediction (tree val
, enum prediction
*prediction
)
2116 return PRED_NO_PREDICTION
;
2117 /* Different heuristics for pointers and scalars. */
2118 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2120 /* NULL is usually not returned. */
2121 if (integer_zerop (val
))
2123 *prediction
= NOT_TAKEN
;
2124 return PRED_NULL_RETURN
;
2127 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2129 /* Negative return values are often used to indicate
2131 if (TREE_CODE (val
) == INTEGER_CST
2132 && tree_int_cst_sgn (val
) < 0)
2134 *prediction
= NOT_TAKEN
;
2135 return PRED_NEGATIVE_RETURN
;
2137 /* Constant return values seems to be commonly taken.
2138 Zero/one often represent booleans so exclude them from the
2140 if (TREE_CONSTANT (val
)
2141 && (!integer_zerop (val
) && !integer_onep (val
)))
2143 *prediction
= TAKEN
;
2144 return PRED_CONST_RETURN
;
2147 return PRED_NO_PREDICTION
;
2150 /* Find the basic block with return expression and look up for possible
2151 return value trying to apply RETURN_PREDICTION heuristics. */
2153 apply_return_prediction (void)
2155 greturn
*return_stmt
= NULL
;
2159 int phi_num_args
, i
;
2160 enum br_predictor pred
;
2161 enum prediction direction
;
2164 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2166 gimple last
= last_stmt (e
->src
);
2168 && gimple_code (last
) == GIMPLE_RETURN
)
2170 return_stmt
= as_a
<greturn
*> (last
);
2176 return_val
= gimple_return_retval (return_stmt
);
2179 if (TREE_CODE (return_val
) != SSA_NAME
2180 || !SSA_NAME_DEF_STMT (return_val
)
2181 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2183 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2184 phi_num_args
= gimple_phi_num_args (phi
);
2185 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2187 /* Avoid the degenerate case where all return values form the function
2188 belongs to same category (ie they are all positive constants)
2189 so we can hardly say something about them. */
2190 for (i
= 1; i
< phi_num_args
; i
++)
2191 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2193 if (i
!= phi_num_args
)
2194 for (i
= 0; i
< phi_num_args
; i
++)
2196 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2197 if (pred
!= PRED_NO_PREDICTION
)
2198 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2203 /* Look for basic block that contains unlikely to happen events
2204 (such as noreturn calls) and mark all paths leading to execution
2205 of this basic blocks as unlikely. */
2208 tree_bb_level_predictions (void)
2211 bool has_return_edges
= false;
2215 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2216 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2218 has_return_edges
= true;
2222 apply_return_prediction ();
2224 FOR_EACH_BB_FN (bb
, cfun
)
2226 gimple_stmt_iterator gsi
;
2228 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2230 gimple stmt
= gsi_stmt (gsi
);
2233 if (is_gimple_call (stmt
))
2235 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2236 && has_return_edges
)
2237 predict_paths_leading_to (bb
, PRED_NORETURN
,
2239 decl
= gimple_call_fndecl (stmt
);
2241 && lookup_attribute ("cold",
2242 DECL_ATTRIBUTES (decl
)))
2243 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2246 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2248 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2249 gimple_predict_outcome (stmt
));
2250 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2251 hints to callers. */
2257 #ifdef ENABLE_CHECKING
2259 /* Callback for hash_map::traverse, asserts that the pointer map is
2263 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2266 gcc_assert (!value
);
2271 /* Predict branch probabilities and estimate profile for basic block BB. */
2274 tree_estimate_probability_bb (basic_block bb
)
2280 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2282 /* Predict edges to user labels with attributes. */
2283 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2285 gimple_stmt_iterator gi
;
2286 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2288 glabel
*label_stmt
=
2289 dyn_cast
<glabel
*> (gsi_stmt (gi
));
2294 decl
= gimple_label_label (label_stmt
);
2295 if (DECL_ARTIFICIAL (decl
))
2298 /* Finally, we have a user-defined label. */
2299 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2300 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2301 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2302 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2306 /* Predict early returns to be probable, as we've already taken
2307 care for error returns and other cases are often used for
2308 fast paths through function.
2310 Since we've already removed the return statements, we are
2311 looking for CFG like:
2321 if (e
->dest
!= bb
->next_bb
2322 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2323 && single_succ_p (e
->dest
)
2324 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2325 && (last
= last_stmt (e
->dest
)) != NULL
2326 && gimple_code (last
) == GIMPLE_RETURN
)
2331 if (single_succ_p (bb
))
2333 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2334 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2335 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2336 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2337 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2340 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2341 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2342 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2343 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2346 /* Look for block we are guarding (ie we dominate it,
2347 but it doesn't postdominate us). */
2348 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2349 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2350 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2352 gimple_stmt_iterator bi
;
2354 /* The call heuristic claims that a guarded function call
2355 is improbable. This is because such calls are often used
2356 to signal exceptional situations such as printing error
2358 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2361 gimple stmt
= gsi_stmt (bi
);
2362 if (is_gimple_call (stmt
)
2363 /* Constant and pure calls are hardly used to signalize
2364 something exceptional. */
2365 && gimple_has_side_effects (stmt
))
2367 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2373 tree_predict_by_opcode (bb
);
2376 /* Predict branch probabilities and estimate profile of the tree CFG.
2377 This function can be called from the loop optimizers to recompute
2378 the profile information. */
2381 tree_estimate_probability (void)
2385 add_noreturn_fake_exit_edges ();
2386 connect_infinite_loops_to_exit ();
2387 /* We use loop_niter_by_eval, which requires that the loops have
2389 create_preheaders (CP_SIMPLE_PREHEADERS
);
2390 calculate_dominance_info (CDI_POST_DOMINATORS
);
2392 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2393 tree_bb_level_predictions ();
2394 record_loop_exits ();
2396 if (number_of_loops (cfun
) > 1)
2399 FOR_EACH_BB_FN (bb
, cfun
)
2400 tree_estimate_probability_bb (bb
);
2402 FOR_EACH_BB_FN (bb
, cfun
)
2403 combine_predictions_for_bb (bb
);
2405 #ifdef ENABLE_CHECKING
2406 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2408 delete bb_predictions
;
2409 bb_predictions
= NULL
;
2411 estimate_bb_frequencies (false);
2412 free_dominance_info (CDI_POST_DOMINATORS
);
2413 remove_fake_exit_edges ();
2416 /* Predict edges to successors of CUR whose sources are not postdominated by
2417 BB by PRED and recurse to all postdominators. */
2420 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2421 enum br_predictor pred
,
2422 enum prediction taken
,
2429 /* We are looking for all edges forming edge cut induced by
2430 set of all blocks postdominated by BB. */
2431 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2432 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2433 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2439 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2440 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2442 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2444 /* See if there is an edge from e->src that is not abnormal
2445 and does not lead to BB. */
2446 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2448 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2449 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2455 /* If there is non-abnormal path leaving e->src, predict edge
2456 using predictor. Otherwise we need to look for paths
2459 The second may lead to infinite loop in the case we are predicitng
2460 regions that are only reachable by abnormal edges. We simply
2461 prevent visiting given BB twice. */
2463 predict_edge_def (e
, pred
, taken
);
2464 else if (bitmap_set_bit (visited
, e
->src
->index
))
2465 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2467 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2469 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2470 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2473 /* Sets branch probabilities according to PREDiction and
2477 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2478 enum prediction taken
)
2480 bitmap visited
= BITMAP_ALLOC (NULL
);
2481 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2482 BITMAP_FREE (visited
);
2485 /* Like predict_paths_leading_to but take edge instead of basic block. */
2488 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2489 enum prediction taken
)
2491 bool has_nonloop_edge
= false;
2495 basic_block bb
= e
->src
;
2496 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2497 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2498 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2499 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2501 has_nonloop_edge
= true;
2504 if (!has_nonloop_edge
)
2506 bitmap visited
= BITMAP_ALLOC (NULL
);
2507 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2508 BITMAP_FREE (visited
);
2511 predict_edge_def (e
, pred
, taken
);
2514 /* This is used to carry information about basic blocks. It is
2515 attached to the AUX field of the standard CFG block. */
2519 /* Estimated frequency of execution of basic_block. */
2522 /* To keep queue of basic blocks to process. */
2525 /* Number of predecessors we need to visit first. */
2529 /* Similar information for edges. */
2530 struct edge_prob_info
2532 /* In case edge is a loopback edge, the probability edge will be reached
2533 in case header is. Estimated number of iterations of the loop can be
2534 then computed as 1 / (1 - back_edge_prob). */
2535 sreal back_edge_prob
;
2536 /* True if the edge is a loopback edge in the natural loop. */
2537 unsigned int back_edge
:1;
2540 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2541 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2543 /* Helper function for estimate_bb_frequencies.
2544 Propagate the frequencies in blocks marked in
2545 TOVISIT, starting in HEAD. */
2548 propagate_freq (basic_block head
, bitmap tovisit
)
2557 /* For each basic block we need to visit count number of his predecessors
2558 we need to visit first. */
2559 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2564 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2566 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2568 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2570 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2572 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2574 "Irreducible region hit, ignoring edge to %i->%i\n",
2575 e
->src
->index
, bb
->index
);
2577 BLOCK_INFO (bb
)->npredecessors
= count
;
2578 /* When function never returns, we will never process exit block. */
2579 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2580 bb
->count
= bb
->frequency
= 0;
2583 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
2585 for (bb
= head
; bb
; bb
= nextbb
)
2588 sreal cyclic_probability
, frequency
;
2590 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
2591 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
2593 nextbb
= BLOCK_INFO (bb
)->next
;
2594 BLOCK_INFO (bb
)->next
= NULL
;
2596 /* Compute frequency of basic block. */
2599 #ifdef ENABLE_CHECKING
2600 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2601 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2602 || (e
->flags
& EDGE_DFS_BACK
));
2605 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2606 if (EDGE_INFO (e
)->back_edge
)
2608 sreal_add (&cyclic_probability
, &cyclic_probability
,
2609 &EDGE_INFO (e
)->back_edge_prob
);
2611 else if (!(e
->flags
& EDGE_DFS_BACK
))
2615 /* frequency += (e->probability
2616 * BLOCK_INFO (e->src)->frequency /
2617 REG_BR_PROB_BASE); */
2619 sreal_init (&tmp
, e
->probability
, 0);
2620 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
2621 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
2622 sreal_add (&frequency
, &frequency
, &tmp
);
2625 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
2627 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
2628 sizeof (frequency
));
2632 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
2634 memcpy (&cyclic_probability
, &real_almost_one
,
2635 sizeof (real_almost_one
));
2638 /* BLOCK_INFO (bb)->frequency = frequency
2639 / (1 - cyclic_probability) */
2641 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
2642 sreal_div (&BLOCK_INFO (bb
)->frequency
,
2643 &frequency
, &cyclic_probability
);
2647 bitmap_clear_bit (tovisit
, bb
->index
);
2649 e
= find_edge (bb
, head
);
2654 /* EDGE_INFO (e)->back_edge_prob
2655 = ((e->probability * BLOCK_INFO (bb)->frequency)
2656 / REG_BR_PROB_BASE); */
2658 sreal_init (&tmp
, e
->probability
, 0);
2659 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
2660 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2661 &tmp
, &real_inv_br_prob_base
);
2664 /* Propagate to successor blocks. */
2665 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2666 if (!(e
->flags
& EDGE_DFS_BACK
)
2667 && BLOCK_INFO (e
->dest
)->npredecessors
)
2669 BLOCK_INFO (e
->dest
)->npredecessors
--;
2670 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2675 BLOCK_INFO (last
)->next
= e
->dest
;
2683 /* Estimate frequencies in loops at same nest level. */
2686 estimate_loops_at_level (struct loop
*first_loop
)
2690 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2695 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2697 estimate_loops_at_level (loop
->inner
);
2699 /* Find current loop back edge and mark it. */
2700 e
= loop_latch_edge (loop
);
2701 EDGE_INFO (e
)->back_edge
= 1;
2703 bbs
= get_loop_body (loop
);
2704 for (i
= 0; i
< loop
->num_nodes
; i
++)
2705 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2707 propagate_freq (loop
->header
, tovisit
);
2708 BITMAP_FREE (tovisit
);
2712 /* Propagates frequencies through structure of loops. */
2715 estimate_loops (void)
2717 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2720 /* Start by estimating the frequencies in the loops. */
2721 if (number_of_loops (cfun
) > 1)
2722 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2724 /* Now propagate the frequencies through all the blocks. */
2725 FOR_ALL_BB_FN (bb
, cfun
)
2727 bitmap_set_bit (tovisit
, bb
->index
);
2729 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
2730 BITMAP_FREE (tovisit
);
2733 /* Drop the profile for NODE to guessed, and update its frequency based on
2734 whether it is expected to be hot given the CALL_COUNT. */
2737 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
2739 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2740 /* In the case where this was called by another function with a
2741 dropped profile, call_count will be 0. Since there are no
2742 non-zero call counts to this function, we don't know for sure
2743 whether it is hot, and therefore it will be marked normal below. */
2744 bool hot
= maybe_hot_count_p (NULL
, call_count
);
2748 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2749 node
->name (), node
->order
,
2750 hot
? "Function is hot" : "Function is normal");
2751 /* We only expect to miss profiles for functions that are reached
2752 via non-zero call edges in cases where the function may have
2753 been linked from another module or library (COMDATs and extern
2754 templates). See the comments below for handle_missing_profiles.
2755 Also, only warn in cases where the missing counts exceed the
2756 number of training runs. In certain cases with an execv followed
2757 by a no-return call the profile for the no-return call is not
2758 dumped and there can be a mismatch. */
2759 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
2760 && call_count
> profile_info
->runs
)
2762 if (flag_profile_correction
)
2766 "Missing counts for called function %s/%i\n",
2767 node
->name (), node
->order
);
2770 warning (0, "Missing counts for called function %s/%i",
2771 node
->name (), node
->order
);
2774 profile_status_for_fn (fn
)
2775 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2777 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2780 /* In the case of COMDAT routines, multiple object files will contain the same
2781 function and the linker will select one for the binary. In that case
2782 all the other copies from the profile instrument binary will be missing
2783 profile counts. Look for cases where this happened, due to non-zero
2784 call counts going to 0-count functions, and drop the profile to guessed
2785 so that we can use the estimated probabilities and avoid optimizing only
2788 The other case where the profile may be missing is when the routine
2789 is not going to be emitted to the object file, e.g. for "extern template"
2790 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2791 all other cases of non-zero calls to 0-count functions. */
2794 handle_missing_profiles (void)
2796 struct cgraph_node
*node
;
2797 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2798 vec
<struct cgraph_node
*> worklist
;
2799 worklist
.create (64);
2801 /* See if 0 count function has non-0 count callers. In this case we
2802 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2803 FOR_EACH_DEFINED_FUNCTION (node
)
2805 struct cgraph_edge
*e
;
2806 gcov_type call_count
= 0;
2807 gcov_type max_tp_first_run
= 0;
2808 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2812 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2814 call_count
+= e
->count
;
2816 if (e
->caller
->tp_first_run
> max_tp_first_run
)
2817 max_tp_first_run
= e
->caller
->tp_first_run
;
2820 /* If time profile is missing, let assign the maximum that comes from
2821 caller functions. */
2822 if (!node
->tp_first_run
&& max_tp_first_run
)
2823 node
->tp_first_run
= max_tp_first_run
+ 1;
2827 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2829 drop_profile (node
, call_count
);
2830 worklist
.safe_push (node
);
2834 /* Propagate the profile dropping to other 0-count COMDATs that are
2835 potentially called by COMDATs we already dropped the profile on. */
2836 while (worklist
.length () > 0)
2838 struct cgraph_edge
*e
;
2840 node
= worklist
.pop ();
2841 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2843 struct cgraph_node
*callee
= e
->callee
;
2844 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2846 if (callee
->count
> 0)
2848 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2849 && profile_status_for_fn (fn
) == PROFILE_READ
)
2851 drop_profile (node
, 0);
2852 worklist
.safe_push (callee
);
2856 worklist
.release ();
2859 /* Convert counts measured by profile driven feedback to frequencies.
2860 Return nonzero iff there was any nonzero execution count. */
2863 counts_to_freqs (void)
2865 gcov_type count_max
, true_count_max
= 0;
2868 /* Don't overwrite the estimated frequencies when the profile for
2869 the function is missing. We may drop this function PROFILE_GUESSED
2870 later in drop_profile (). */
2871 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
2874 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2875 true_count_max
= MAX (bb
->count
, true_count_max
);
2877 count_max
= MAX (true_count_max
, 1);
2878 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2879 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2881 return true_count_max
;
2884 /* Return true if function is likely to be expensive, so there is no point to
2885 optimize performance of prologue, epilogue or do inlining at the expense
2886 of code size growth. THRESHOLD is the limit of number of instructions
2887 function can execute at average to be still considered not expensive. */
2890 expensive_function_p (int threshold
)
2892 unsigned int sum
= 0;
2896 /* We can not compute accurately for large thresholds due to scaled
2898 gcc_assert (threshold
<= BB_FREQ_MAX
);
2900 /* Frequencies are out of range. This either means that function contains
2901 internal loop executing more than BB_FREQ_MAX times or profile feedback
2902 is available and function has not been executed at all. */
2903 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
2906 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2907 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
2908 FOR_EACH_BB_FN (bb
, cfun
)
2912 FOR_BB_INSNS (bb
, insn
)
2913 if (active_insn_p (insn
))
2915 sum
+= bb
->frequency
;
2924 /* Estimate and propagate basic block frequencies using the given branch
2925 probabilities. If FORCE is true, the frequencies are used to estimate
2926 the counts even when there are already non-zero profile counts. */
2929 estimate_bb_frequencies (bool force
)
2934 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
2936 static int real_values_initialized
= 0;
2938 if (!real_values_initialized
)
2940 real_values_initialized
= 1;
2941 sreal_init (&real_zero
, 0, 0);
2942 sreal_init (&real_one
, 1, 0);
2943 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2944 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2945 sreal_init (&real_one_half
, 1, -1);
2946 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2947 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2950 mark_dfs_back_edges ();
2952 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
2955 /* Set up block info for each basic block. */
2956 alloc_aux_for_blocks (sizeof (block_info
));
2957 alloc_aux_for_edges (sizeof (edge_prob_info
));
2958 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2963 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2965 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2966 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2967 &EDGE_INFO (e
)->back_edge_prob
,
2968 &real_inv_br_prob_base
);
2972 /* First compute frequencies locally for each loop from innermost
2973 to outermost to examine frequencies for back edges. */
2976 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2977 FOR_EACH_BB_FN (bb
, cfun
)
2978 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2979 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2981 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
2982 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2986 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
2987 sreal_add (&tmp
, &tmp
, &real_one_half
);
2988 bb
->frequency
= sreal_to_int (&tmp
);
2991 free_aux_for_blocks ();
2992 free_aux_for_edges ();
2994 compute_function_frequency ();
2997 /* Decide whether function is hot, cold or unlikely executed. */
2999 compute_function_frequency (void)
3002 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3004 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3005 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3006 node
->only_called_at_startup
= true;
3007 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3008 node
->only_called_at_exit
= true;
3010 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3012 int flags
= flags_from_decl_or_type (current_function_decl
);
3013 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3015 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3016 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3018 node
->frequency
= NODE_FREQUENCY_HOT
;
3019 else if (flags
& ECF_NORETURN
)
3020 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3021 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3022 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3023 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3024 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3025 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3029 /* Only first time try to drop function into unlikely executed.
3030 After inlining the roundoff errors may confuse us.
3031 Ipa-profile pass will drop functions only called from unlikely
3032 functions to unlikely and that is most of what we care about. */
3033 if (!cfun
->after_inlining
)
3034 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3035 FOR_EACH_BB_FN (bb
, cfun
)
3037 if (maybe_hot_bb_p (cfun
, bb
))
3039 node
->frequency
= NODE_FREQUENCY_HOT
;
3042 if (!probably_never_executed_bb_p (cfun
, bb
))
3043 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3047 /* Build PREDICT_EXPR. */
3049 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3051 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3052 build_int_cst (integer_type_node
, predictor
));
3053 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3058 predictor_name (enum br_predictor predictor
)
3060 return predictor_info
[predictor
].name
;
3063 /* Predict branch probabilities and estimate profile of the tree CFG. */
3067 const pass_data pass_data_profile
=
3069 GIMPLE_PASS
, /* type */
3070 "profile_estimate", /* name */
3071 OPTGROUP_NONE
, /* optinfo_flags */
3072 TV_BRANCH_PROB
, /* tv_id */
3073 PROP_cfg
, /* properties_required */
3074 0, /* properties_provided */
3075 0, /* properties_destroyed */
3076 0, /* todo_flags_start */
3077 0, /* todo_flags_finish */
3080 class pass_profile
: public gimple_opt_pass
3083 pass_profile (gcc::context
*ctxt
)
3084 : gimple_opt_pass (pass_data_profile
, ctxt
)
3087 /* opt_pass methods: */
3088 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3089 virtual unsigned int execute (function
*);
3091 }; // class pass_profile
3094 pass_profile::execute (function
*fun
)
3098 loop_optimizer_init (LOOPS_NORMAL
);
3099 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3100 flow_loops_dump (dump_file
, NULL
, 0);
3102 mark_irreducible_loops ();
3104 nb_loops
= number_of_loops (fun
);
3108 tree_estimate_probability ();
3113 loop_optimizer_finalize ();
3114 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3115 gimple_dump_cfg (dump_file
, dump_flags
);
3116 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3117 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3124 make_pass_profile (gcc::context
*ctxt
)
3126 return new pass_profile (ctxt
);
3131 const pass_data pass_data_strip_predict_hints
=
3133 GIMPLE_PASS
, /* type */
3134 "*strip_predict_hints", /* name */
3135 OPTGROUP_NONE
, /* optinfo_flags */
3136 TV_BRANCH_PROB
, /* tv_id */
3137 PROP_cfg
, /* properties_required */
3138 0, /* properties_provided */
3139 0, /* properties_destroyed */
3140 0, /* todo_flags_start */
3141 0, /* todo_flags_finish */
3144 class pass_strip_predict_hints
: public gimple_opt_pass
3147 pass_strip_predict_hints (gcc::context
*ctxt
)
3148 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3151 /* opt_pass methods: */
3152 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3153 virtual unsigned int execute (function
*);
3155 }; // class pass_strip_predict_hints
3157 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3158 we no longer need. */
3160 pass_strip_predict_hints::execute (function
*fun
)
3166 FOR_EACH_BB_FN (bb
, fun
)
3168 gimple_stmt_iterator bi
;
3169 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3171 gimple stmt
= gsi_stmt (bi
);
3173 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3175 gsi_remove (&bi
, true);
3178 else if (is_gimple_call (stmt
))
3180 tree fndecl
= gimple_call_fndecl (stmt
);
3183 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3184 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3185 && gimple_call_num_args (stmt
) == 2)
3186 || (gimple_call_internal_p (stmt
)
3187 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3189 var
= gimple_call_lhs (stmt
);
3193 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3194 gsi_replace (&bi
, ass_stmt
, true);
3198 gsi_remove (&bi
, true);
3212 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3214 return new pass_strip_predict_hints (ctxt
);
3217 /* Rebuild function frequencies. Passes are in general expected to
3218 maintain profile by hand, however in some cases this is not possible:
3219 for example when inlining several functions with loops freuqencies might run
3220 out of scale and thus needs to be recomputed. */
3223 rebuild_frequencies (void)
3225 timevar_push (TV_REBUILD_FREQUENCIES
);
3227 /* When the max bb count in the function is small, there is a higher
3228 chance that there were truncation errors in the integer scaling
3229 of counts by inlining and other optimizations. This could lead
3230 to incorrect classification of code as being cold when it isn't.
3231 In that case, force the estimation of bb counts/frequencies from the
3232 branch probabilities, rather than computing frequencies from counts,
3233 which may also lead to frequencies incorrectly reduced to 0. There
3234 is less precision in the probabilities, so we only do this for small
3236 gcov_type count_max
= 0;
3238 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3239 count_max
= MAX (bb
->count
, count_max
);
3241 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3242 || (profile_status_for_fn (cfun
) == PROFILE_READ
&& count_max
< REG_BR_PROB_BASE
/10))
3244 loop_optimizer_init (0);
3245 add_noreturn_fake_exit_edges ();
3246 mark_irreducible_loops ();
3247 connect_infinite_loops_to_exit ();
3248 estimate_bb_frequencies (true);
3249 remove_fake_exit_edges ();
3250 loop_optimizer_finalize ();
3252 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3256 timevar_pop (TV_REBUILD_FREQUENCIES
);