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"
54 #include "pointer-set.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_get_node (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
)
171 /* Code executed at most once is not hot. */
172 if (profile_info
->runs
>= count
)
174 return (count
>= get_hot_bb_threshold ());
177 /* Return true in case BB can be CPU intensive and should be optimized
178 for maximal performance. */
181 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
183 gcc_checking_assert (fun
);
184 if (profile_status_for_fn (fun
) == PROFILE_READ
)
185 return maybe_hot_count_p (fun
, bb
->count
);
186 return maybe_hot_frequency_p (fun
, bb
->frequency
);
189 /* Return true if the call can be hot. */
192 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
194 if (profile_info
&& flag_branch_probabilities
195 && !maybe_hot_count_p (NULL
,
198 if (edge
->caller
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
200 && edge
->callee
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
202 if (edge
->caller
->frequency
> NODE_FREQUENCY_UNLIKELY_EXECUTED
204 && edge
->callee
->frequency
<= NODE_FREQUENCY_EXECUTED_ONCE
))
208 if (edge
->caller
->frequency
== NODE_FREQUENCY_HOT
)
210 if (edge
->caller
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
211 && edge
->frequency
< CGRAPH_FREQ_BASE
* 3 / 2)
213 if (flag_guess_branch_prob
)
215 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0
216 || edge
->frequency
<= (CGRAPH_FREQ_BASE
217 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
223 /* Return true in case BB can be CPU intensive and should be optimized
224 for maximal performance. */
227 maybe_hot_edge_p (edge e
)
229 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
230 return maybe_hot_count_p (cfun
, e
->count
);
231 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
236 /* Return true if profile COUNT and FREQUENCY, or function FUN static
237 node frequency reflects never being executed. */
240 probably_never_executed (struct function
*fun
,
241 gcov_type count
, int frequency
)
243 gcc_checking_assert (fun
);
244 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
246 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
247 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
251 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
253 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
255 gcov_type computed_count
;
256 /* Check for possibility of overflow, in which case entry bb count
257 is large enough to do the division first without losing much
259 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
< REG_BR_PROB_BASE
*
262 gcov_type scaled_count
263 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
*
264 unlikely_count_fraction
;
265 computed_count
= RDIV (scaled_count
,
266 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
);
270 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
,
271 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
);
272 computed_count
*= frequency
* unlikely_count_fraction
;
274 if (computed_count
>= profile_info
->runs
)
279 if ((!profile_info
|| !flag_branch_probabilities
)
280 && (cgraph_get_node (fun
->decl
)->frequency
281 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
287 /* Return true in case BB is probably never executed. */
290 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
292 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
296 /* Return true in case edge E is probably never executed. */
299 probably_never_executed_edge_p (struct function
*fun
, edge e
)
301 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
304 /* Return true if NODE should be optimized for size. */
307 cgraph_optimize_for_size_p (struct cgraph_node
*node
)
311 if (node
&& (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
317 /* Return true when current function should always be optimized for size. */
320 optimize_function_for_size_p (struct function
*fun
)
324 if (!fun
|| !fun
->decl
)
326 return cgraph_optimize_for_size_p (cgraph_get_node (fun
->decl
));
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
) || !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 /* This map contains for a basic block the list of predictions for the
496 static struct pointer_map_t
*bb_predictions
;
498 /* Structure representing predictions in tree level. */
500 struct edge_prediction
{
501 struct edge_prediction
*ep_next
;
503 enum br_predictor ep_predictor
;
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 void **preds
= pointer_map_contains (bb_predictions
, bb
);
519 for (i
= (struct edge_prediction
*) *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
, 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
, 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 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
623 i
->ep_next
= (struct edge_prediction
*) *preds
;
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
)
641 preds
= pointer_map_contains (bb_predictions
, e
->src
);
645 struct edge_prediction
**prediction
= (struct edge_prediction
**) preds
;
646 struct edge_prediction
*next
;
650 if ((*prediction
)->ep_edge
== e
)
652 next
= (*prediction
)->ep_next
;
657 prediction
= &((*prediction
)->ep_next
);
662 /* Clears the list of predictions stored for BB. */
665 clear_bb_predictions (basic_block bb
)
667 void **preds
= pointer_map_contains (bb_predictions
, bb
);
668 struct edge_prediction
*pred
, *next
;
673 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= next
)
675 next
= pred
->ep_next
;
681 /* Return true when we can store prediction on insn INSN.
682 At the moment we represent predictions only on conditional
683 jumps, not at computed jump or other complicated cases. */
685 can_predict_insn_p (const_rtx insn
)
687 return (JUMP_P (insn
)
688 && any_condjump_p (insn
)
689 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
692 /* Predict edge E by given predictor if possible. */
695 predict_edge_def (edge e
, enum br_predictor predictor
,
696 enum prediction taken
)
698 int probability
= predictor_info
[(int) predictor
].hitrate
;
701 probability
= REG_BR_PROB_BASE
- probability
;
703 predict_edge (e
, predictor
, probability
);
706 /* Invert all branch predictions or probability notes in the INSN. This needs
707 to be done each time we invert the condition used by the jump. */
710 invert_br_probabilities (rtx insn
)
714 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
715 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
716 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
717 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
718 XEXP (XEXP (note
, 0), 1)
719 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
722 /* Dump information about the branch prediction to the output file. */
725 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
726 basic_block bb
, int used
)
734 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
735 if (! (e
->flags
& EDGE_FALLTHRU
))
738 fprintf (file
, " %s heuristics%s: %.1f%%",
739 predictor_info
[predictor
].name
,
740 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
744 fprintf (file
, " exec ");
745 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
748 fprintf (file
, " hit ");
749 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
750 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
754 fprintf (file
, "\n");
757 /* We can not predict the probabilities of outgoing edges of bb. Set them
758 evenly and hope for the best. */
760 set_even_probabilities (basic_block bb
)
766 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
767 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
769 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
770 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
771 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
776 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
777 note if not already present. Remove now useless REG_BR_PRED notes. */
780 combine_predictions_for_insn (rtx insn
, basic_block bb
)
785 int best_probability
= PROB_EVEN
;
786 enum br_predictor best_predictor
= END_PREDICTORS
;
787 int combined_probability
= REG_BR_PROB_BASE
/ 2;
789 bool first_match
= false;
792 if (!can_predict_insn_p (insn
))
794 set_even_probabilities (bb
);
798 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
799 pnote
= ®_NOTES (insn
);
801 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
804 /* We implement "first match" heuristics and use probability guessed
805 by predictor with smallest index. */
806 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
807 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
809 enum br_predictor predictor
= ((enum br_predictor
)
810 INTVAL (XEXP (XEXP (note
, 0), 0)));
811 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
814 if (best_predictor
> predictor
)
815 best_probability
= probability
, best_predictor
= predictor
;
817 d
= (combined_probability
* probability
818 + (REG_BR_PROB_BASE
- combined_probability
)
819 * (REG_BR_PROB_BASE
- probability
));
821 /* Use FP math to avoid overflows of 32bit integers. */
823 /* If one probability is 0% and one 100%, avoid division by zero. */
824 combined_probability
= REG_BR_PROB_BASE
/ 2;
826 combined_probability
= (((double) combined_probability
) * probability
827 * REG_BR_PROB_BASE
/ d
+ 0.5);
830 /* Decide which heuristic to use. In case we didn't match anything,
831 use no_prediction heuristic, in case we did match, use either
832 first match or Dempster-Shaffer theory depending on the flags. */
834 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
838 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
839 combined_probability
, bb
, true);
842 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
844 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
849 combined_probability
= best_probability
;
850 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
854 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
856 enum br_predictor predictor
= ((enum br_predictor
)
857 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
858 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
860 dump_prediction (dump_file
, predictor
, probability
, bb
,
861 !first_match
|| best_predictor
== predictor
);
862 *pnote
= XEXP (*pnote
, 1);
865 pnote
= &XEXP (*pnote
, 1);
870 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
872 /* Save the prediction into CFG in case we are seeing non-degenerated
874 if (!single_succ_p (bb
))
876 BRANCH_EDGE (bb
)->probability
= combined_probability
;
877 FALLTHRU_EDGE (bb
)->probability
878 = REG_BR_PROB_BASE
- combined_probability
;
881 else if (!single_succ_p (bb
))
883 int prob
= XINT (prob_note
, 0);
885 BRANCH_EDGE (bb
)->probability
= prob
;
886 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
889 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
892 /* Combine predictions into single probability and store them into CFG.
893 Remove now useless prediction entries. */
896 combine_predictions_for_bb (basic_block bb
)
898 int best_probability
= PROB_EVEN
;
899 enum br_predictor best_predictor
= END_PREDICTORS
;
900 int combined_probability
= REG_BR_PROB_BASE
/ 2;
902 bool first_match
= false;
904 struct edge_prediction
*pred
;
906 edge e
, first
= NULL
, second
= NULL
;
910 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
911 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
914 if (first
&& !second
)
920 /* When there is no successor or only one choice, prediction is easy.
922 We are lazy for now and predict only basic blocks with two outgoing
923 edges. It is possible to predict generic case too, but we have to
924 ignore first match heuristics and do more involved combining. Implement
929 set_even_probabilities (bb
);
930 clear_bb_predictions (bb
);
932 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
938 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
940 preds
= pointer_map_contains (bb_predictions
, bb
);
943 /* We implement "first match" heuristics and use probability guessed
944 by predictor with smallest index. */
945 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
947 enum br_predictor predictor
= pred
->ep_predictor
;
948 int probability
= pred
->ep_probability
;
950 if (pred
->ep_edge
!= first
)
951 probability
= REG_BR_PROB_BASE
- probability
;
954 /* First match heuristics would be widly confused if we predicted
956 if (best_predictor
> predictor
)
958 struct edge_prediction
*pred2
;
959 int prob
= probability
;
961 for (pred2
= (struct edge_prediction
*) *preds
;
962 pred2
; pred2
= pred2
->ep_next
)
963 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
965 int probability2
= pred
->ep_probability
;
967 if (pred2
->ep_edge
!= first
)
968 probability2
= REG_BR_PROB_BASE
- probability2
;
970 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
971 (probability2
< REG_BR_PROB_BASE
/ 2))
974 /* If the same predictor later gave better result, go for it! */
975 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
976 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
980 best_probability
= prob
, best_predictor
= predictor
;
983 d
= (combined_probability
* probability
984 + (REG_BR_PROB_BASE
- combined_probability
)
985 * (REG_BR_PROB_BASE
- probability
));
987 /* Use FP math to avoid overflows of 32bit integers. */
989 /* If one probability is 0% and one 100%, avoid division by zero. */
990 combined_probability
= REG_BR_PROB_BASE
/ 2;
992 combined_probability
= (((double) combined_probability
)
994 * REG_BR_PROB_BASE
/ d
+ 0.5);
998 /* Decide which heuristic to use. In case we didn't match anything,
999 use no_prediction heuristic, in case we did match, use either
1000 first match or Dempster-Shaffer theory depending on the flags. */
1002 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1006 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
1009 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1011 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1016 combined_probability
= best_probability
;
1017 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
1021 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1023 enum br_predictor predictor
= pred
->ep_predictor
;
1024 int probability
= pred
->ep_probability
;
1026 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
1027 probability
= REG_BR_PROB_BASE
- probability
;
1028 dump_prediction (dump_file
, predictor
, probability
, bb
,
1029 !first_match
|| best_predictor
== predictor
);
1032 clear_bb_predictions (bb
);
1036 first
->probability
= combined_probability
;
1037 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1041 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1042 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1044 T1 and T2 should be one of the following cases:
1045 1. T1 is SSA_NAME, T2 is NULL
1046 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1047 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1050 strips_small_constant (tree t1
, tree t2
)
1057 else if (TREE_CODE (t1
) == SSA_NAME
)
1059 else if (tree_fits_shwi_p (t1
))
1060 value
= tree_to_shwi (t1
);
1066 else if (tree_fits_shwi_p (t2
))
1067 value
= tree_to_shwi (t2
);
1068 else if (TREE_CODE (t2
) == SSA_NAME
)
1076 if (value
<= 4 && value
>= -4)
1082 /* Return the SSA_NAME in T or T's operands.
1083 Return NULL if SSA_NAME cannot be found. */
1086 get_base_value (tree t
)
1088 if (TREE_CODE (t
) == SSA_NAME
)
1091 if (!BINARY_CLASS_P (t
))
1094 switch (TREE_OPERAND_LENGTH (t
))
1097 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1099 return strips_small_constant (TREE_OPERAND (t
, 0),
1100 TREE_OPERAND (t
, 1));
1106 /* Check the compare STMT in LOOP. If it compares an induction
1107 variable to a loop invariant, return true, and save
1108 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1109 Otherwise return false and set LOOP_INVAIANT to NULL. */
1112 is_comparison_with_loop_invariant_p (gimple stmt
, struct loop
*loop
,
1113 tree
*loop_invariant
,
1114 enum tree_code
*compare_code
,
1118 tree op0
, op1
, bound
, base
;
1120 enum tree_code code
;
1123 code
= gimple_cond_code (stmt
);
1124 *loop_invariant
= NULL
;
1140 op0
= gimple_cond_lhs (stmt
);
1141 op1
= gimple_cond_rhs (stmt
);
1143 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1144 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1146 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1148 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1150 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1151 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1153 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1154 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1157 if (integer_zerop (iv0
.step
))
1159 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1160 code
= invert_tree_comparison (code
, false);
1163 if (tree_fits_shwi_p (iv1
.step
))
1172 if (tree_fits_shwi_p (iv0
.step
))
1178 if (TREE_CODE (bound
) != INTEGER_CST
)
1179 bound
= get_base_value (bound
);
1182 if (TREE_CODE (base
) != INTEGER_CST
)
1183 base
= get_base_value (base
);
1187 *loop_invariant
= bound
;
1188 *compare_code
= code
;
1190 *loop_iv_base
= base
;
1194 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1197 expr_coherent_p (tree t1
, tree t2
)
1200 tree ssa_name_1
= NULL
;
1201 tree ssa_name_2
= NULL
;
1203 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1204 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1209 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1211 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1214 /* Check to see if t1 is expressed/defined with t2. */
1215 stmt
= SSA_NAME_DEF_STMT (t1
);
1216 gcc_assert (stmt
!= NULL
);
1217 if (is_gimple_assign (stmt
))
1219 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1220 if (ssa_name_1
&& ssa_name_1
== t2
)
1224 /* Check to see if t2 is expressed/defined with t1. */
1225 stmt
= SSA_NAME_DEF_STMT (t2
);
1226 gcc_assert (stmt
!= NULL
);
1227 if (is_gimple_assign (stmt
))
1229 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1230 if (ssa_name_2
&& ssa_name_2
== t1
)
1234 /* Compare if t1 and t2's def_stmts are identical. */
1235 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1241 /* Predict branch probability of BB when BB contains a branch that compares
1242 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1243 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1246 for (int i = 0; i < bound; i++) {
1253 In this loop, we will predict the branch inside the loop to be taken. */
1256 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1257 tree loop_bound_var
,
1258 tree loop_iv_base_var
,
1259 enum tree_code loop_bound_code
,
1260 int loop_bound_step
)
1263 tree compare_var
, compare_base
;
1264 enum tree_code compare_code
;
1265 tree compare_step_var
;
1269 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1270 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1271 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1274 stmt
= last_stmt (bb
);
1275 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1277 if (!is_comparison_with_loop_invariant_p (stmt
, loop
, &compare_var
,
1283 /* Find the taken edge. */
1284 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1285 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1288 /* When comparing an IV to a loop invariant, NE is more likely to be
1289 taken while EQ is more likely to be not-taken. */
1290 if (compare_code
== NE_EXPR
)
1292 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1295 else if (compare_code
== EQ_EXPR
)
1297 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1301 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1304 /* If loop bound, base and compare bound are all constants, we can
1305 calculate the probability directly. */
1306 if (tree_fits_shwi_p (loop_bound_var
)
1307 && tree_fits_shwi_p (compare_var
)
1308 && tree_fits_shwi_p (compare_base
))
1311 bool of
, overflow
= false;
1312 double_int mod
, compare_count
, tem
, loop_count
;
1314 double_int loop_bound
= tree_to_double_int (loop_bound_var
);
1315 double_int compare_bound
= tree_to_double_int (compare_var
);
1316 double_int base
= tree_to_double_int (compare_base
);
1317 double_int compare_step
= tree_to_double_int (compare_step_var
);
1319 /* (loop_bound - base) / compare_step */
1320 tem
= loop_bound
.sub_with_overflow (base
, &of
);
1322 loop_count
= tem
.divmod_with_overflow (compare_step
,
1327 if ((!compare_step
.is_negative ())
1328 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1330 /* (loop_bound - compare_bound) / compare_step */
1331 tem
= loop_bound
.sub_with_overflow (compare_bound
, &of
);
1333 compare_count
= tem
.divmod_with_overflow (compare_step
,
1340 /* (compare_bound - base) / compare_step */
1341 tem
= compare_bound
.sub_with_overflow (base
, &of
);
1343 compare_count
= tem
.divmod_with_overflow (compare_step
,
1348 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1350 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1352 if (compare_count
.is_negative ())
1353 compare_count
= double_int_zero
;
1354 if (loop_count
.is_negative ())
1355 loop_count
= double_int_zero
;
1356 if (loop_count
.is_zero ())
1358 else if (compare_count
.scmp (loop_count
) == 1)
1359 probability
= REG_BR_PROB_BASE
;
1362 /* If loop_count is too big, such that REG_BR_PROB_BASE * loop_count
1363 could overflow, shift both loop_count and compare_count right
1364 a bit so that it doesn't overflow. Note both counts are known not
1365 to be negative at this point. */
1366 int clz_bits
= clz_hwi (loop_count
.high
);
1367 gcc_assert (REG_BR_PROB_BASE
< 32768);
1370 loop_count
.arshift (16 - clz_bits
, HOST_BITS_PER_DOUBLE_INT
);
1371 compare_count
.arshift (16 - clz_bits
, HOST_BITS_PER_DOUBLE_INT
);
1373 tem
= compare_count
.mul_with_sign (double_int::from_shwi
1374 (REG_BR_PROB_BASE
), true, &of
);
1376 tem
= tem
.divmod (loop_count
, true, TRUNC_DIV_EXPR
, &mod
);
1377 probability
= tem
.to_uhwi ();
1381 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1386 if (expr_coherent_p (loop_bound_var
, compare_var
))
1388 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1389 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1390 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1391 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1392 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1393 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1394 else if (loop_bound_code
== NE_EXPR
)
1396 /* If the loop backedge condition is "(i != bound)", we do
1397 the comparison based on the step of IV:
1398 * step < 0 : backedge condition is like (i > bound)
1399 * step > 0 : backedge condition is like (i < bound) */
1400 gcc_assert (loop_bound_step
!= 0);
1401 if (loop_bound_step
> 0
1402 && (compare_code
== LT_EXPR
1403 || compare_code
== LE_EXPR
))
1404 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1405 else if (loop_bound_step
< 0
1406 && (compare_code
== GT_EXPR
1407 || compare_code
== GE_EXPR
))
1408 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1410 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1413 /* The branch is predicted not-taken if loop_bound_code is
1414 opposite with compare_code. */
1415 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1417 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1420 for (i = s; i < h; i++)
1422 The branch should be predicted taken. */
1423 if (loop_bound_step
> 0
1424 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1425 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1426 else if (loop_bound_step
< 0
1427 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1428 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1430 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1434 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1435 exits are resulted from short-circuit conditions that will generate an
1438 if (foo() || global > 10)
1441 This will be translated into:
1446 if foo() goto BB6 else goto BB5
1448 if global > 10 goto BB6 else goto BB7
1452 iftmp = (PHI 0(BB5), 1(BB6))
1453 if iftmp == 1 goto BB8 else goto BB3
1455 outside of the loop...
1457 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1458 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1459 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1460 exits to predict them using PRED_LOOP_EXIT. */
1463 predict_extra_loop_exits (edge exit_edge
)
1466 bool check_value_one
;
1468 tree cmp_rhs
, cmp_lhs
;
1469 gimple cmp_stmt
= last_stmt (exit_edge
->src
);
1471 if (!cmp_stmt
|| gimple_code (cmp_stmt
) != GIMPLE_COND
)
1473 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1474 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1475 if (!TREE_CONSTANT (cmp_rhs
)
1476 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1478 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1481 /* If check_value_one is true, only the phi_args with value '1' will lead
1482 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1484 check_value_one
= (((integer_onep (cmp_rhs
))
1485 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1486 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1488 phi_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1489 if (!phi_stmt
|| gimple_code (phi_stmt
) != GIMPLE_PHI
)
1492 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1496 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1497 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1499 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1501 if ((check_value_one
^ integer_onep (val
)) == 1)
1503 if (EDGE_COUNT (e
->src
->succs
) != 1)
1505 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1509 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1510 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1514 /* Predict edge probabilities by exploiting loop structure. */
1517 predict_loops (void)
1521 /* Try to predict out blocks in a loop that are not part of a
1523 FOR_EACH_LOOP (loop
, 0)
1525 basic_block bb
, *bbs
;
1526 unsigned j
, n_exits
;
1528 struct tree_niter_desc niter_desc
;
1530 struct nb_iter_bound
*nb_iter
;
1531 enum tree_code loop_bound_code
= ERROR_MARK
;
1532 tree loop_bound_step
= NULL
;
1533 tree loop_bound_var
= NULL
;
1534 tree loop_iv_base
= NULL
;
1537 exits
= get_loop_exit_edges (loop
);
1538 n_exits
= exits
.length ();
1545 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1548 HOST_WIDE_INT nitercst
;
1549 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1551 enum br_predictor predictor
;
1553 predict_extra_loop_exits (ex
);
1555 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1556 niter
= niter_desc
.niter
;
1557 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1558 niter
= loop_niter_by_eval (loop
, ex
);
1560 if (TREE_CODE (niter
) == INTEGER_CST
)
1562 if (tree_fits_uhwi_p (niter
)
1564 && compare_tree_int (niter
, max
- 1) == -1)
1565 nitercst
= tree_to_uhwi (niter
) + 1;
1568 predictor
= PRED_LOOP_ITERATIONS
;
1570 /* If we have just one exit and we can derive some information about
1571 the number of iterations of the loop from the statements inside
1572 the loop, use it to predict this exit. */
1573 else if (n_exits
== 1)
1575 nitercst
= estimated_stmt_executions_int (loop
);
1581 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1586 /* If the prediction for number of iterations is zero, do not
1587 predict the exit edges. */
1591 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1592 predict_edge (ex
, predictor
, probability
);
1596 /* Find information about loop bound variables. */
1597 for (nb_iter
= loop
->bounds
; nb_iter
;
1598 nb_iter
= nb_iter
->next
)
1600 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1602 stmt
= nb_iter
->stmt
;
1605 if (!stmt
&& last_stmt (loop
->header
)
1606 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1607 stmt
= last_stmt (loop
->header
);
1609 is_comparison_with_loop_invariant_p (stmt
, loop
,
1615 bbs
= get_loop_body (loop
);
1617 for (j
= 0; j
< loop
->num_nodes
; j
++)
1619 int header_found
= 0;
1625 /* Bypass loop heuristics on continue statement. These
1626 statements construct loops via "non-loop" constructs
1627 in the source language and are better to be handled
1629 if (predicted_by_p (bb
, PRED_CONTINUE
))
1632 /* Loop branch heuristics - predict an edge back to a
1633 loop's head as taken. */
1634 if (bb
== loop
->latch
)
1636 e
= find_edge (loop
->latch
, loop
->header
);
1640 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1644 /* Loop exit heuristics - predict an edge exiting the loop if the
1645 conditional has no loop header successors as not taken. */
1647 /* If we already used more reliable loop exit predictors, do not
1648 bother with PRED_LOOP_EXIT. */
1649 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1650 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1652 /* For loop with many exits we don't want to predict all exits
1653 with the pretty large probability, because if all exits are
1654 considered in row, the loop would be predicted to iterate
1655 almost never. The code to divide probability by number of
1656 exits is very rough. It should compute the number of exits
1657 taken in each patch through function (not the overall number
1658 of exits that might be a lot higher for loops with wide switch
1659 statements in them) and compute n-th square root.
1661 We limit the minimal probability by 2% to avoid
1662 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1663 as this was causing regression in perl benchmark containing such
1666 int probability
= ((REG_BR_PROB_BASE
1667 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1669 if (probability
< HITRATE (2))
1670 probability
= HITRATE (2);
1671 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1672 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1673 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1674 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1677 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1679 tree_to_shwi (loop_bound_step
));
1682 /* Free basic blocks from get_loop_body. */
1687 /* Attempt to predict probabilities of BB outgoing edges using local
1690 bb_estimate_probability_locally (basic_block bb
)
1692 rtx last_insn
= BB_END (bb
);
1695 if (! can_predict_insn_p (last_insn
))
1697 cond
= get_condition (last_insn
, NULL
, false, false);
1701 /* Try "pointer heuristic."
1702 A comparison ptr == 0 is predicted as false.
1703 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1704 if (COMPARISON_P (cond
)
1705 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1706 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1708 if (GET_CODE (cond
) == EQ
)
1709 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1710 else if (GET_CODE (cond
) == NE
)
1711 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1715 /* Try "opcode heuristic."
1716 EQ tests are usually false and NE tests are usually true. Also,
1717 most quantities are positive, so we can make the appropriate guesses
1718 about signed comparisons against zero. */
1719 switch (GET_CODE (cond
))
1722 /* Unconditional branch. */
1723 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1724 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1729 /* Floating point comparisons appears to behave in a very
1730 unpredictable way because of special role of = tests in
1732 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1734 /* Comparisons with 0 are often used for booleans and there is
1735 nothing useful to predict about them. */
1736 else if (XEXP (cond
, 1) == const0_rtx
1737 || XEXP (cond
, 0) == const0_rtx
)
1740 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1745 /* Floating point comparisons appears to behave in a very
1746 unpredictable way because of special role of = tests in
1748 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1750 /* Comparisons with 0 are often used for booleans and there is
1751 nothing useful to predict about them. */
1752 else if (XEXP (cond
, 1) == const0_rtx
1753 || XEXP (cond
, 0) == const0_rtx
)
1756 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1760 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1764 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1769 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1770 || XEXP (cond
, 1) == constm1_rtx
)
1771 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1776 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1777 || XEXP (cond
, 1) == constm1_rtx
)
1778 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1786 /* Set edge->probability for each successor edge of BB. */
1788 guess_outgoing_edge_probabilities (basic_block bb
)
1790 bb_estimate_probability_locally (bb
);
1791 combine_predictions_for_insn (BB_END (bb
), bb
);
1794 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
1796 /* Helper function for expr_expected_value. */
1799 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1800 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
1805 *predictor
= PRED_UNCONDITIONAL
;
1807 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1809 if (TREE_CONSTANT (op0
))
1812 if (code
!= SSA_NAME
)
1815 def
= SSA_NAME_DEF_STMT (op0
);
1817 /* If we were already here, break the infinite cycle. */
1818 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1821 if (gimple_code (def
) == GIMPLE_PHI
)
1823 /* All the arguments of the PHI node must have the same constant
1825 int i
, n
= gimple_phi_num_args (def
);
1826 tree val
= NULL
, new_val
;
1828 for (i
= 0; i
< n
; i
++)
1830 tree arg
= PHI_ARG_DEF (def
, i
);
1831 enum br_predictor predictor2
;
1833 /* If this PHI has itself as an argument, we cannot
1834 determine the string length of this argument. However,
1835 if we can find an expected constant value for the other
1836 PHI args then we can still be sure that this is
1837 likely a constant. So be optimistic and just
1838 continue with the next argument. */
1839 if (arg
== PHI_RESULT (def
))
1842 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
1844 /* It is difficult to combine value predictors. Simply assume
1845 that later predictor is weaker and take its prediction. */
1846 if (predictor
&& *predictor
< predictor2
)
1847 *predictor
= predictor2
;
1852 else if (!operand_equal_p (val
, new_val
, false))
1857 if (is_gimple_assign (def
))
1859 if (gimple_assign_lhs (def
) != op0
)
1862 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1863 gimple_assign_rhs1 (def
),
1864 gimple_assign_rhs_code (def
),
1865 gimple_assign_rhs2 (def
),
1866 visited
, predictor
);
1869 if (is_gimple_call (def
))
1871 tree decl
= gimple_call_fndecl (def
);
1874 if (gimple_call_internal_p (def
)
1875 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
1877 gcc_assert (gimple_call_num_args (def
) == 3);
1878 tree val
= gimple_call_arg (def
, 0);
1879 if (TREE_CONSTANT (val
))
1883 *predictor
= PRED_BUILTIN_EXPECT
;
1884 tree val2
= gimple_call_arg (def
, 2);
1885 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
1886 && tree_fits_uhwi_p (val2
)
1887 && tree_to_uhwi (val2
) < END_PREDICTORS
);
1888 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
1890 return gimple_call_arg (def
, 1);
1894 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1895 switch (DECL_FUNCTION_CODE (decl
))
1897 case BUILT_IN_EXPECT
:
1900 if (gimple_call_num_args (def
) != 2)
1902 val
= gimple_call_arg (def
, 0);
1903 if (TREE_CONSTANT (val
))
1906 *predictor
= PRED_BUILTIN_EXPECT
;
1907 return gimple_call_arg (def
, 1);
1910 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1911 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1912 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1913 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1914 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1915 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1916 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1917 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1918 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1919 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1920 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1921 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1922 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1923 /* Assume that any given atomic operation has low contention,
1924 and thus the compare-and-swap operation succeeds. */
1926 *predictor
= PRED_COMPARE_AND_SWAP
;
1927 return boolean_true_node
;
1934 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1937 enum br_predictor predictor2
;
1938 op0
= expr_expected_value (op0
, visited
, predictor
);
1941 op1
= expr_expected_value (op1
, visited
, &predictor2
);
1942 if (predictor
&& *predictor
< predictor2
)
1943 *predictor
= predictor2
;
1946 res
= fold_build2 (code
, type
, op0
, op1
);
1947 if (TREE_CONSTANT (res
))
1951 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1954 op0
= expr_expected_value (op0
, visited
, predictor
);
1957 res
= fold_build1 (code
, type
, op0
);
1958 if (TREE_CONSTANT (res
))
1965 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1966 The function is used by builtin_expect branch predictor so the evidence
1967 must come from this construct and additional possible constant folding.
1969 We may want to implement more involved value guess (such as value range
1970 propagation based prediction), but such tricks shall go to new
1974 expr_expected_value (tree expr
, bitmap visited
,
1975 enum br_predictor
*predictor
)
1977 enum tree_code code
;
1980 if (TREE_CONSTANT (expr
))
1983 *predictor
= PRED_UNCONDITIONAL
;
1987 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1988 return expr_expected_value_1 (TREE_TYPE (expr
),
1989 op0
, code
, op1
, visited
, predictor
);
1993 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1994 we no longer need. */
1996 strip_predict_hints (void)
2002 FOR_EACH_BB_FN (bb
, cfun
)
2004 gimple_stmt_iterator bi
;
2005 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
2007 gimple stmt
= gsi_stmt (bi
);
2009 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2011 gsi_remove (&bi
, true);
2014 else if (is_gimple_call (stmt
))
2016 tree fndecl
= gimple_call_fndecl (stmt
);
2019 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
2020 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
2021 && gimple_call_num_args (stmt
) == 2)
2022 || (gimple_call_internal_p (stmt
)
2023 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
2025 var
= gimple_call_lhs (stmt
);
2029 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
2030 gsi_replace (&bi
, ass_stmt
, true);
2034 gsi_remove (&bi
, true);
2045 /* Predict using opcode of the last statement in basic block. */
2047 tree_predict_by_opcode (basic_block bb
)
2049 gimple stmt
= last_stmt (bb
);
2057 enum br_predictor predictor
;
2059 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2061 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2062 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2064 op0
= gimple_cond_lhs (stmt
);
2065 op1
= gimple_cond_rhs (stmt
);
2066 cmp
= gimple_cond_code (stmt
);
2067 type
= TREE_TYPE (op0
);
2068 visited
= BITMAP_ALLOC (NULL
);
2069 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
2071 BITMAP_FREE (visited
);
2072 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2074 if (predictor
== PRED_BUILTIN_EXPECT
)
2076 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2078 gcc_assert (percent
>= 0 && percent
<= 100);
2079 if (integer_zerop (val
))
2080 percent
= 100 - percent
;
2081 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2084 predict_edge (then_edge
, predictor
,
2085 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2087 /* Try "pointer heuristic."
2088 A comparison ptr == 0 is predicted as false.
2089 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2090 if (POINTER_TYPE_P (type
))
2093 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2094 else if (cmp
== NE_EXPR
)
2095 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2099 /* Try "opcode heuristic."
2100 EQ tests are usually false and NE tests are usually true. Also,
2101 most quantities are positive, so we can make the appropriate guesses
2102 about signed comparisons against zero. */
2107 /* Floating point comparisons appears to behave in a very
2108 unpredictable way because of special role of = tests in
2110 if (FLOAT_TYPE_P (type
))
2112 /* Comparisons with 0 are often used for booleans and there is
2113 nothing useful to predict about them. */
2114 else if (integer_zerop (op0
) || integer_zerop (op1
))
2117 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2122 /* Floating point comparisons appears to behave in a very
2123 unpredictable way because of special role of = tests in
2125 if (FLOAT_TYPE_P (type
))
2127 /* Comparisons with 0 are often used for booleans and there is
2128 nothing useful to predict about them. */
2129 else if (integer_zerop (op0
)
2130 || integer_zerop (op1
))
2133 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2137 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2140 case UNORDERED_EXPR
:
2141 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2146 if (integer_zerop (op1
)
2147 || integer_onep (op1
)
2148 || integer_all_onesp (op1
)
2151 || real_minus_onep (op1
))
2152 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2157 if (integer_zerop (op1
)
2158 || integer_onep (op1
)
2159 || integer_all_onesp (op1
)
2162 || real_minus_onep (op1
))
2163 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2171 /* Try to guess whether the value of return means error code. */
2173 static enum br_predictor
2174 return_prediction (tree val
, enum prediction
*prediction
)
2178 return PRED_NO_PREDICTION
;
2179 /* Different heuristics for pointers and scalars. */
2180 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2182 /* NULL is usually not returned. */
2183 if (integer_zerop (val
))
2185 *prediction
= NOT_TAKEN
;
2186 return PRED_NULL_RETURN
;
2189 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2191 /* Negative return values are often used to indicate
2193 if (TREE_CODE (val
) == INTEGER_CST
2194 && tree_int_cst_sgn (val
) < 0)
2196 *prediction
= NOT_TAKEN
;
2197 return PRED_NEGATIVE_RETURN
;
2199 /* Constant return values seems to be commonly taken.
2200 Zero/one often represent booleans so exclude them from the
2202 if (TREE_CONSTANT (val
)
2203 && (!integer_zerop (val
) && !integer_onep (val
)))
2205 *prediction
= TAKEN
;
2206 return PRED_CONST_RETURN
;
2209 return PRED_NO_PREDICTION
;
2212 /* Find the basic block with return expression and look up for possible
2213 return value trying to apply RETURN_PREDICTION heuristics. */
2215 apply_return_prediction (void)
2217 gimple return_stmt
= NULL
;
2221 int phi_num_args
, i
;
2222 enum br_predictor pred
;
2223 enum prediction direction
;
2226 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2228 return_stmt
= last_stmt (e
->src
);
2230 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
2235 return_val
= gimple_return_retval (return_stmt
);
2238 if (TREE_CODE (return_val
) != SSA_NAME
2239 || !SSA_NAME_DEF_STMT (return_val
)
2240 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2242 phi
= SSA_NAME_DEF_STMT (return_val
);
2243 phi_num_args
= gimple_phi_num_args (phi
);
2244 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2246 /* Avoid the degenerate case where all return values form the function
2247 belongs to same category (ie they are all positive constants)
2248 so we can hardly say something about them. */
2249 for (i
= 1; i
< phi_num_args
; i
++)
2250 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2252 if (i
!= phi_num_args
)
2253 for (i
= 0; i
< phi_num_args
; i
++)
2255 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2256 if (pred
!= PRED_NO_PREDICTION
)
2257 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2262 /* Look for basic block that contains unlikely to happen events
2263 (such as noreturn calls) and mark all paths leading to execution
2264 of this basic blocks as unlikely. */
2267 tree_bb_level_predictions (void)
2270 bool has_return_edges
= false;
2274 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2275 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2277 has_return_edges
= true;
2281 apply_return_prediction ();
2283 FOR_EACH_BB_FN (bb
, cfun
)
2285 gimple_stmt_iterator gsi
;
2287 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2289 gimple stmt
= gsi_stmt (gsi
);
2292 if (is_gimple_call (stmt
))
2294 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2295 && has_return_edges
)
2296 predict_paths_leading_to (bb
, PRED_NORETURN
,
2298 decl
= gimple_call_fndecl (stmt
);
2300 && lookup_attribute ("cold",
2301 DECL_ATTRIBUTES (decl
)))
2302 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2305 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2307 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2308 gimple_predict_outcome (stmt
));
2309 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2310 hints to callers. */
2316 #ifdef ENABLE_CHECKING
2318 /* Callback for pointer_map_traverse, asserts that the pointer map is
2322 assert_is_empty (const void *key ATTRIBUTE_UNUSED
, void **value
,
2323 void *data ATTRIBUTE_UNUSED
)
2325 gcc_assert (!*value
);
2330 /* Predict branch probabilities and estimate profile for basic block BB. */
2333 tree_estimate_probability_bb (basic_block bb
)
2339 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2341 /* Predict edges to user labels with attributes. */
2342 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2344 gimple_stmt_iterator gi
;
2345 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2347 gimple stmt
= gsi_stmt (gi
);
2350 if (gimple_code (stmt
) != GIMPLE_LABEL
)
2352 decl
= gimple_label_label (stmt
);
2353 if (DECL_ARTIFICIAL (decl
))
2356 /* Finally, we have a user-defined label. */
2357 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2358 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2359 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2360 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2364 /* Predict early returns to be probable, as we've already taken
2365 care for error returns and other cases are often used for
2366 fast paths through function.
2368 Since we've already removed the return statements, we are
2369 looking for CFG like:
2379 if (e
->dest
!= bb
->next_bb
2380 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2381 && single_succ_p (e
->dest
)
2382 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2383 && (last
= last_stmt (e
->dest
)) != NULL
2384 && gimple_code (last
) == GIMPLE_RETURN
)
2389 if (single_succ_p (bb
))
2391 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2392 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2393 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2394 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2395 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2398 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2399 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2400 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2401 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2404 /* Look for block we are guarding (ie we dominate it,
2405 but it doesn't postdominate us). */
2406 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2407 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2408 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2410 gimple_stmt_iterator bi
;
2412 /* The call heuristic claims that a guarded function call
2413 is improbable. This is because such calls are often used
2414 to signal exceptional situations such as printing error
2416 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2419 gimple stmt
= gsi_stmt (bi
);
2420 if (is_gimple_call (stmt
)
2421 /* Constant and pure calls are hardly used to signalize
2422 something exceptional. */
2423 && gimple_has_side_effects (stmt
))
2425 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2431 tree_predict_by_opcode (bb
);
2434 /* Predict branch probabilities and estimate profile of the tree CFG.
2435 This function can be called from the loop optimizers to recompute
2436 the profile information. */
2439 tree_estimate_probability (void)
2443 add_noreturn_fake_exit_edges ();
2444 connect_infinite_loops_to_exit ();
2445 /* We use loop_niter_by_eval, which requires that the loops have
2447 create_preheaders (CP_SIMPLE_PREHEADERS
);
2448 calculate_dominance_info (CDI_POST_DOMINATORS
);
2450 bb_predictions
= pointer_map_create ();
2451 tree_bb_level_predictions ();
2452 record_loop_exits ();
2454 if (number_of_loops (cfun
) > 1)
2457 FOR_EACH_BB_FN (bb
, cfun
)
2458 tree_estimate_probability_bb (bb
);
2460 FOR_EACH_BB_FN (bb
, cfun
)
2461 combine_predictions_for_bb (bb
);
2463 #ifdef ENABLE_CHECKING
2464 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
2466 pointer_map_destroy (bb_predictions
);
2467 bb_predictions
= NULL
;
2469 estimate_bb_frequencies (false);
2470 free_dominance_info (CDI_POST_DOMINATORS
);
2471 remove_fake_exit_edges ();
2474 /* Predict branch probabilities and estimate profile of the tree CFG.
2475 This is the driver function for PASS_PROFILE. */
2478 tree_estimate_probability_driver (void)
2482 loop_optimizer_init (LOOPS_NORMAL
);
2483 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2484 flow_loops_dump (dump_file
, NULL
, 0);
2486 mark_irreducible_loops ();
2488 nb_loops
= number_of_loops (cfun
);
2492 tree_estimate_probability ();
2497 loop_optimizer_finalize ();
2498 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2499 gimple_dump_cfg (dump_file
, dump_flags
);
2500 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
2501 profile_status_for_fn (cfun
) = PROFILE_GUESSED
;
2505 /* Predict edges to successors of CUR whose sources are not postdominated by
2506 BB by PRED and recurse to all postdominators. */
2509 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2510 enum br_predictor pred
,
2511 enum prediction taken
,
2518 /* We are looking for all edges forming edge cut induced by
2519 set of all blocks postdominated by BB. */
2520 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2521 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2522 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2528 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2529 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2531 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2533 /* See if there is an edge from e->src that is not abnormal
2534 and does not lead to BB. */
2535 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2537 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2538 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2544 /* If there is non-abnormal path leaving e->src, predict edge
2545 using predictor. Otherwise we need to look for paths
2548 The second may lead to infinite loop in the case we are predicitng
2549 regions that are only reachable by abnormal edges. We simply
2550 prevent visiting given BB twice. */
2552 predict_edge_def (e
, pred
, taken
);
2553 else if (bitmap_set_bit (visited
, e
->src
->index
))
2554 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2556 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2558 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2559 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2562 /* Sets branch probabilities according to PREDiction and
2566 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2567 enum prediction taken
)
2569 bitmap visited
= BITMAP_ALLOC (NULL
);
2570 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2571 BITMAP_FREE (visited
);
2574 /* Like predict_paths_leading_to but take edge instead of basic block. */
2577 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2578 enum prediction taken
)
2580 bool has_nonloop_edge
= false;
2584 basic_block bb
= e
->src
;
2585 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2586 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2587 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2588 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2590 has_nonloop_edge
= true;
2593 if (!has_nonloop_edge
)
2595 bitmap visited
= BITMAP_ALLOC (NULL
);
2596 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2597 BITMAP_FREE (visited
);
2600 predict_edge_def (e
, pred
, taken
);
2603 /* This is used to carry information about basic blocks. It is
2604 attached to the AUX field of the standard CFG block. */
2606 typedef struct block_info_def
2608 /* Estimated frequency of execution of basic_block. */
2611 /* To keep queue of basic blocks to process. */
2614 /* Number of predecessors we need to visit first. */
2618 /* Similar information for edges. */
2619 typedef struct edge_info_def
2621 /* In case edge is a loopback edge, the probability edge will be reached
2622 in case header is. Estimated number of iterations of the loop can be
2623 then computed as 1 / (1 - back_edge_prob). */
2624 sreal back_edge_prob
;
2625 /* True if the edge is a loopback edge in the natural loop. */
2626 unsigned int back_edge
:1;
2629 #define BLOCK_INFO(B) ((block_info) (B)->aux)
2630 #define EDGE_INFO(E) ((edge_info) (E)->aux)
2632 /* Helper function for estimate_bb_frequencies.
2633 Propagate the frequencies in blocks marked in
2634 TOVISIT, starting in HEAD. */
2637 propagate_freq (basic_block head
, bitmap tovisit
)
2646 /* For each basic block we need to visit count number of his predecessors
2647 we need to visit first. */
2648 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2653 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2655 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2657 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2659 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2661 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2663 "Irreducible region hit, ignoring edge to %i->%i\n",
2664 e
->src
->index
, bb
->index
);
2666 BLOCK_INFO (bb
)->npredecessors
= count
;
2667 /* When function never returns, we will never process exit block. */
2668 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2669 bb
->count
= bb
->frequency
= 0;
2672 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
2674 for (bb
= head
; bb
; bb
= nextbb
)
2677 sreal cyclic_probability
, frequency
;
2679 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
2680 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
2682 nextbb
= BLOCK_INFO (bb
)->next
;
2683 BLOCK_INFO (bb
)->next
= NULL
;
2685 /* Compute frequency of basic block. */
2688 #ifdef ENABLE_CHECKING
2689 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2690 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2691 || (e
->flags
& EDGE_DFS_BACK
));
2694 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2695 if (EDGE_INFO (e
)->back_edge
)
2697 sreal_add (&cyclic_probability
, &cyclic_probability
,
2698 &EDGE_INFO (e
)->back_edge_prob
);
2700 else if (!(e
->flags
& EDGE_DFS_BACK
))
2704 /* frequency += (e->probability
2705 * BLOCK_INFO (e->src)->frequency /
2706 REG_BR_PROB_BASE); */
2708 sreal_init (&tmp
, e
->probability
, 0);
2709 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
2710 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
2711 sreal_add (&frequency
, &frequency
, &tmp
);
2714 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
2716 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
2717 sizeof (frequency
));
2721 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
2723 memcpy (&cyclic_probability
, &real_almost_one
,
2724 sizeof (real_almost_one
));
2727 /* BLOCK_INFO (bb)->frequency = frequency
2728 / (1 - cyclic_probability) */
2730 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
2731 sreal_div (&BLOCK_INFO (bb
)->frequency
,
2732 &frequency
, &cyclic_probability
);
2736 bitmap_clear_bit (tovisit
, bb
->index
);
2738 e
= find_edge (bb
, head
);
2743 /* EDGE_INFO (e)->back_edge_prob
2744 = ((e->probability * BLOCK_INFO (bb)->frequency)
2745 / REG_BR_PROB_BASE); */
2747 sreal_init (&tmp
, e
->probability
, 0);
2748 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
2749 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2750 &tmp
, &real_inv_br_prob_base
);
2753 /* Propagate to successor blocks. */
2754 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2755 if (!(e
->flags
& EDGE_DFS_BACK
)
2756 && BLOCK_INFO (e
->dest
)->npredecessors
)
2758 BLOCK_INFO (e
->dest
)->npredecessors
--;
2759 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2764 BLOCK_INFO (last
)->next
= e
->dest
;
2772 /* Estimate frequencies in loops at same nest level. */
2775 estimate_loops_at_level (struct loop
*first_loop
)
2779 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2784 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2786 estimate_loops_at_level (loop
->inner
);
2788 /* Find current loop back edge and mark it. */
2789 e
= loop_latch_edge (loop
);
2790 EDGE_INFO (e
)->back_edge
= 1;
2792 bbs
= get_loop_body (loop
);
2793 for (i
= 0; i
< loop
->num_nodes
; i
++)
2794 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2796 propagate_freq (loop
->header
, tovisit
);
2797 BITMAP_FREE (tovisit
);
2801 /* Propagates frequencies through structure of loops. */
2804 estimate_loops (void)
2806 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2809 /* Start by estimating the frequencies in the loops. */
2810 if (number_of_loops (cfun
) > 1)
2811 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2813 /* Now propagate the frequencies through all the blocks. */
2814 FOR_ALL_BB_FN (bb
, cfun
)
2816 bitmap_set_bit (tovisit
, bb
->index
);
2818 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
2819 BITMAP_FREE (tovisit
);
2822 /* Drop the profile for NODE to guessed, and update its frequency based on
2823 whether it is expected to be hot given the CALL_COUNT. */
2826 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
2828 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2829 /* In the case where this was called by another function with a
2830 dropped profile, call_count will be 0. Since there are no
2831 non-zero call counts to this function, we don't know for sure
2832 whether it is hot, and therefore it will be marked normal below. */
2833 bool hot
= maybe_hot_count_p (NULL
, call_count
);
2837 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2838 node
->name (), node
->order
,
2839 hot
? "Function is hot" : "Function is normal");
2840 /* We only expect to miss profiles for functions that are reached
2841 via non-zero call edges in cases where the function may have
2842 been linked from another module or library (COMDATs and extern
2843 templates). See the comments below for handle_missing_profiles.
2844 Also, only warn in cases where the missing counts exceed the
2845 number of training runs. In certain cases with an execv followed
2846 by a no-return call the profile for the no-return call is not
2847 dumped and there can be a mismatch. */
2848 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
2849 && call_count
> profile_info
->runs
)
2851 if (flag_profile_correction
)
2855 "Missing counts for called function %s/%i\n",
2856 node
->name (), node
->order
);
2859 warning (0, "Missing counts for called function %s/%i",
2860 node
->name (), node
->order
);
2863 profile_status_for_fn (fn
)
2864 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2866 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2869 /* In the case of COMDAT routines, multiple object files will contain the same
2870 function and the linker will select one for the binary. In that case
2871 all the other copies from the profile instrument binary will be missing
2872 profile counts. Look for cases where this happened, due to non-zero
2873 call counts going to 0-count functions, and drop the profile to guessed
2874 so that we can use the estimated probabilities and avoid optimizing only
2877 The other case where the profile may be missing is when the routine
2878 is not going to be emitted to the object file, e.g. for "extern template"
2879 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2880 all other cases of non-zero calls to 0-count functions. */
2883 handle_missing_profiles (void)
2885 struct cgraph_node
*node
;
2886 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2887 vec
<struct cgraph_node
*> worklist
;
2888 worklist
.create (64);
2890 /* See if 0 count function has non-0 count callers. In this case we
2891 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2892 FOR_EACH_DEFINED_FUNCTION (node
)
2894 struct cgraph_edge
*e
;
2895 gcov_type call_count
= 0;
2896 gcov_type max_tp_first_run
= 0;
2897 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2901 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2903 call_count
+= e
->count
;
2905 if (e
->caller
->tp_first_run
> max_tp_first_run
)
2906 max_tp_first_run
= e
->caller
->tp_first_run
;
2909 /* If time profile is missing, let assign the maximum that comes from
2910 caller functions. */
2911 if (!node
->tp_first_run
&& max_tp_first_run
)
2912 node
->tp_first_run
= max_tp_first_run
+ 1;
2916 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2918 drop_profile (node
, call_count
);
2919 worklist
.safe_push (node
);
2923 /* Propagate the profile dropping to other 0-count COMDATs that are
2924 potentially called by COMDATs we already dropped the profile on. */
2925 while (worklist
.length () > 0)
2927 struct cgraph_edge
*e
;
2929 node
= worklist
.pop ();
2930 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2932 struct cgraph_node
*callee
= e
->callee
;
2933 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2935 if (callee
->count
> 0)
2937 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2938 && profile_status_for_fn (fn
) == PROFILE_READ
)
2940 drop_profile (node
, 0);
2941 worklist
.safe_push (callee
);
2945 worklist
.release ();
2948 /* Convert counts measured by profile driven feedback to frequencies.
2949 Return nonzero iff there was any nonzero execution count. */
2952 counts_to_freqs (void)
2954 gcov_type count_max
, true_count_max
= 0;
2957 /* Don't overwrite the estimated frequencies when the profile for
2958 the function is missing. We may drop this function PROFILE_GUESSED
2959 later in drop_profile (). */
2960 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
2963 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2964 true_count_max
= MAX (bb
->count
, true_count_max
);
2966 count_max
= MAX (true_count_max
, 1);
2967 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2968 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2970 return true_count_max
;
2973 /* Return true if function is likely to be expensive, so there is no point to
2974 optimize performance of prologue, epilogue or do inlining at the expense
2975 of code size growth. THRESHOLD is the limit of number of instructions
2976 function can execute at average to be still considered not expensive. */
2979 expensive_function_p (int threshold
)
2981 unsigned int sum
= 0;
2985 /* We can not compute accurately for large thresholds due to scaled
2987 gcc_assert (threshold
<= BB_FREQ_MAX
);
2989 /* Frequencies are out of range. This either means that function contains
2990 internal loop executing more than BB_FREQ_MAX times or profile feedback
2991 is available and function has not been executed at all. */
2992 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
2995 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2996 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
2997 FOR_EACH_BB_FN (bb
, cfun
)
3001 FOR_BB_INSNS (bb
, insn
)
3002 if (active_insn_p (insn
))
3004 sum
+= bb
->frequency
;
3013 /* Estimate and propagate basic block frequencies using the given branch
3014 probabilities. If FORCE is true, the frequencies are used to estimate
3015 the counts even when there are already non-zero profile counts. */
3018 estimate_bb_frequencies (bool force
)
3023 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
3025 static int real_values_initialized
= 0;
3027 if (!real_values_initialized
)
3029 real_values_initialized
= 1;
3030 sreal_init (&real_zero
, 0, 0);
3031 sreal_init (&real_one
, 1, 0);
3032 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
3033 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
3034 sreal_init (&real_one_half
, 1, -1);
3035 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
3036 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
3039 mark_dfs_back_edges ();
3041 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3044 /* Set up block info for each basic block. */
3045 alloc_aux_for_blocks (sizeof (struct block_info_def
));
3046 alloc_aux_for_edges (sizeof (struct edge_info_def
));
3047 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3052 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3054 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
3055 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
3056 &EDGE_INFO (e
)->back_edge_prob
,
3057 &real_inv_br_prob_base
);
3061 /* First compute frequencies locally for each loop from innermost
3062 to outermost to examine frequencies for back edges. */
3065 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
3066 FOR_EACH_BB_FN (bb
, cfun
)
3067 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
3068 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
3070 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
3071 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3075 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
3076 sreal_add (&tmp
, &tmp
, &real_one_half
);
3077 bb
->frequency
= sreal_to_int (&tmp
);
3080 free_aux_for_blocks ();
3081 free_aux_for_edges ();
3083 compute_function_frequency ();
3086 /* Decide whether function is hot, cold or unlikely executed. */
3088 compute_function_frequency (void)
3091 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
3093 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3094 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3095 node
->only_called_at_startup
= true;
3096 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3097 node
->only_called_at_exit
= true;
3099 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3101 int flags
= flags_from_decl_or_type (current_function_decl
);
3102 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3104 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3105 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3107 node
->frequency
= NODE_FREQUENCY_HOT
;
3108 else if (flags
& ECF_NORETURN
)
3109 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3110 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3111 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3112 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3113 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3114 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3118 /* Only first time try to drop function into unlikely executed.
3119 After inlining the roundoff errors may confuse us.
3120 Ipa-profile pass will drop functions only called from unlikely
3121 functions to unlikely and that is most of what we care about. */
3122 if (!cfun
->after_inlining
)
3123 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3124 FOR_EACH_BB_FN (bb
, cfun
)
3126 if (maybe_hot_bb_p (cfun
, bb
))
3128 node
->frequency
= NODE_FREQUENCY_HOT
;
3131 if (!probably_never_executed_bb_p (cfun
, bb
))
3132 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3137 gate_estimate_probability (void)
3139 return flag_guess_branch_prob
;
3142 /* Build PREDICT_EXPR. */
3144 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3146 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3147 build_int_cst (integer_type_node
, predictor
));
3148 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3153 predictor_name (enum br_predictor predictor
)
3155 return predictor_info
[predictor
].name
;
3160 const pass_data pass_data_profile
=
3162 GIMPLE_PASS
, /* type */
3163 "profile_estimate", /* name */
3164 OPTGROUP_NONE
, /* optinfo_flags */
3165 true, /* has_gate */
3166 true, /* has_execute */
3167 TV_BRANCH_PROB
, /* tv_id */
3168 PROP_cfg
, /* properties_required */
3169 0, /* properties_provided */
3170 0, /* properties_destroyed */
3171 0, /* todo_flags_start */
3172 TODO_verify_ssa
, /* todo_flags_finish */
3175 class pass_profile
: public gimple_opt_pass
3178 pass_profile (gcc::context
*ctxt
)
3179 : gimple_opt_pass (pass_data_profile
, ctxt
)
3182 /* opt_pass methods: */
3183 bool gate () { return gate_estimate_probability (); }
3184 unsigned int execute () { return tree_estimate_probability_driver (); }
3186 }; // class pass_profile
3191 make_pass_profile (gcc::context
*ctxt
)
3193 return new pass_profile (ctxt
);
3198 const pass_data pass_data_strip_predict_hints
=
3200 GIMPLE_PASS
, /* type */
3201 "*strip_predict_hints", /* name */
3202 OPTGROUP_NONE
, /* optinfo_flags */
3203 false, /* has_gate */
3204 true, /* has_execute */
3205 TV_BRANCH_PROB
, /* tv_id */
3206 PROP_cfg
, /* properties_required */
3207 0, /* properties_provided */
3208 0, /* properties_destroyed */
3209 0, /* todo_flags_start */
3210 TODO_verify_ssa
, /* todo_flags_finish */
3213 class pass_strip_predict_hints
: public gimple_opt_pass
3216 pass_strip_predict_hints (gcc::context
*ctxt
)
3217 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3220 /* opt_pass methods: */
3221 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3222 unsigned int execute () { return strip_predict_hints (); }
3224 }; // class pass_strip_predict_hints
3229 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3231 return new pass_strip_predict_hints (ctxt
);
3234 /* Rebuild function frequencies. Passes are in general expected to
3235 maintain profile by hand, however in some cases this is not possible:
3236 for example when inlining several functions with loops freuqencies might run
3237 out of scale and thus needs to be recomputed. */
3240 rebuild_frequencies (void)
3242 timevar_push (TV_REBUILD_FREQUENCIES
);
3244 /* When the max bb count in the function is small, there is a higher
3245 chance that there were truncation errors in the integer scaling
3246 of counts by inlining and other optimizations. This could lead
3247 to incorrect classification of code as being cold when it isn't.
3248 In that case, force the estimation of bb counts/frequencies from the
3249 branch probabilities, rather than computing frequencies from counts,
3250 which may also lead to frequencies incorrectly reduced to 0. There
3251 is less precision in the probabilities, so we only do this for small
3253 gcov_type count_max
= 0;
3255 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3256 count_max
= MAX (bb
->count
, count_max
);
3258 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3259 || (profile_status_for_fn (cfun
) == PROFILE_READ
&& count_max
< REG_BR_PROB_BASE
/10))
3261 loop_optimizer_init (0);
3262 add_noreturn_fake_exit_edges ();
3263 mark_irreducible_loops ();
3264 connect_infinite_loops_to_exit ();
3265 estimate_bb_frequencies (true);
3266 remove_fake_exit_edges ();
3267 loop_optimizer_finalize ();
3269 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3273 timevar_pop (TV_REBUILD_FREQUENCIES
);