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
)
169 /* Code executed at most once is not hot. */
170 if (profile_info
->runs
>= count
)
172 return (count
>= get_hot_bb_threshold ());
175 /* Return true in case BB can be CPU intensive and should be optimized
176 for maximal performance. */
179 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
181 gcc_checking_assert (fun
);
182 if (profile_status_for_fn (fun
) == PROFILE_READ
)
183 return maybe_hot_count_p (fun
, bb
->count
);
184 return maybe_hot_frequency_p (fun
, bb
->frequency
);
187 /* Return true if the call can be hot. */
190 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
192 if (profile_info
&& flag_branch_probabilities
193 && !maybe_hot_count_p (NULL
,
196 if (edge
->caller
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
198 && edge
->callee
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
200 if (edge
->caller
->frequency
> NODE_FREQUENCY_UNLIKELY_EXECUTED
202 && edge
->callee
->frequency
<= NODE_FREQUENCY_EXECUTED_ONCE
))
206 if (edge
->caller
->frequency
== NODE_FREQUENCY_HOT
)
208 if (edge
->caller
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
209 && edge
->frequency
< CGRAPH_FREQ_BASE
* 3 / 2)
211 if (flag_guess_branch_prob
)
213 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0
214 || edge
->frequency
<= (CGRAPH_FREQ_BASE
215 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
221 /* Return true in case BB can be CPU intensive and should be optimized
222 for maximal performance. */
225 maybe_hot_edge_p (edge e
)
227 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
228 return maybe_hot_count_p (cfun
, e
->count
);
229 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
234 /* Return true if profile COUNT and FREQUENCY, or function FUN static
235 node frequency reflects never being executed. */
238 probably_never_executed (struct function
*fun
,
239 gcov_type count
, int frequency
)
241 gcc_checking_assert (fun
);
242 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
244 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
245 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
249 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
)
251 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
253 gcov_type computed_count
;
254 /* Check for possibility of overflow, in which case entry bb count
255 is large enough to do the division first without losing much
257 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
< REG_BR_PROB_BASE
*
260 gcov_type scaled_count
261 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
*
262 unlikely_count_fraction
;
263 computed_count
= RDIV (scaled_count
,
264 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
);
268 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
,
269 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
);
270 computed_count
*= frequency
* unlikely_count_fraction
;
272 if (computed_count
>= profile_info
->runs
)
277 if ((!profile_info
|| !flag_branch_probabilities
)
278 && (cgraph_get_node (fun
->decl
)->frequency
279 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
285 /* Return true in case BB is probably never executed. */
288 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
290 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
294 /* Return true in case edge E is probably never executed. */
297 probably_never_executed_edge_p (struct function
*fun
, edge e
)
299 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
302 /* Return true if NODE should be optimized for size. */
305 cgraph_optimize_for_size_p (struct cgraph_node
*node
)
309 if (node
&& (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
315 /* Return true when current function should always be optimized for size. */
318 optimize_function_for_size_p (struct function
*fun
)
322 if (!fun
|| !fun
->decl
)
324 return cgraph_optimize_for_size_p (cgraph_get_node (fun
->decl
));
327 /* Return true when current function should always be optimized for speed. */
330 optimize_function_for_speed_p (struct function
*fun
)
332 return !optimize_function_for_size_p (fun
);
335 /* Return TRUE when BB should be optimized for size. */
338 optimize_bb_for_size_p (const_basic_block bb
)
340 return optimize_function_for_size_p (cfun
) || !maybe_hot_bb_p (cfun
, bb
);
343 /* Return TRUE when BB should be optimized for speed. */
346 optimize_bb_for_speed_p (const_basic_block bb
)
348 return !optimize_bb_for_size_p (bb
);
351 /* Return TRUE when BB should be optimized for size. */
354 optimize_edge_for_size_p (edge e
)
356 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
359 /* Return TRUE when BB should be optimized for speed. */
362 optimize_edge_for_speed_p (edge e
)
364 return !optimize_edge_for_size_p (e
);
367 /* Return TRUE when BB should be optimized for size. */
370 optimize_insn_for_size_p (void)
372 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
375 /* Return TRUE when BB should be optimized for speed. */
378 optimize_insn_for_speed_p (void)
380 return !optimize_insn_for_size_p ();
383 /* Return TRUE when LOOP should be optimized for size. */
386 optimize_loop_for_size_p (struct loop
*loop
)
388 return optimize_bb_for_size_p (loop
->header
);
391 /* Return TRUE when LOOP should be optimized for speed. */
394 optimize_loop_for_speed_p (struct loop
*loop
)
396 return optimize_bb_for_speed_p (loop
->header
);
399 /* Return TRUE when LOOP nest should be optimized for speed. */
402 optimize_loop_nest_for_speed_p (struct loop
*loop
)
404 struct loop
*l
= loop
;
405 if (optimize_loop_for_speed_p (loop
))
408 while (l
&& l
!= loop
)
410 if (optimize_loop_for_speed_p (l
))
418 while (l
!= loop
&& !l
->next
)
427 /* Return TRUE when LOOP nest should be optimized for size. */
430 optimize_loop_nest_for_size_p (struct loop
*loop
)
432 return !optimize_loop_nest_for_speed_p (loop
);
435 /* Return true when edge E is likely to be well predictable by branch
439 predictable_edge_p (edge e
)
441 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
444 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
445 || (REG_BR_PROB_BASE
- e
->probability
446 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
452 /* Set RTL expansion for BB profile. */
455 rtl_profile_for_bb (basic_block bb
)
457 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
460 /* Set RTL expansion for edge profile. */
463 rtl_profile_for_edge (edge e
)
465 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
468 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
470 default_rtl_profile (void)
472 crtl
->maybe_hot_insn_p
= true;
475 /* Return true if the one of outgoing edges is already predicted by
479 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
482 if (!INSN_P (BB_END (bb
)))
484 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
485 if (REG_NOTE_KIND (note
) == REG_BR_PRED
486 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
491 /* This map contains for a basic block the list of predictions for the
494 static struct pointer_map_t
*bb_predictions
;
496 /* Structure representing predictions in tree level. */
498 struct edge_prediction
{
499 struct edge_prediction
*ep_next
;
501 enum br_predictor ep_predictor
;
505 /* Return true if the one of outgoing edges is already predicted by
509 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
511 struct edge_prediction
*i
;
512 void **preds
= pointer_map_contains (bb_predictions
, bb
);
517 for (i
= (struct edge_prediction
*) *preds
; i
; i
= i
->ep_next
)
518 if (i
->ep_predictor
== predictor
)
523 /* Return true when the probability of edge is reliable.
525 The profile guessing code is good at predicting branch outcome (ie.
526 taken/not taken), that is predicted right slightly over 75% of time.
527 It is however notoriously poor on predicting the probability itself.
528 In general the profile appear a lot flatter (with probabilities closer
529 to 50%) than the reality so it is bad idea to use it to drive optimization
530 such as those disabling dynamic branch prediction for well predictable
533 There are two exceptions - edges leading to noreturn edges and edges
534 predicted by number of iterations heuristics are predicted well. This macro
535 should be able to distinguish those, but at the moment it simply check for
536 noreturn heuristic that is only one giving probability over 99% or bellow
537 1%. In future we might want to propagate reliability information across the
538 CFG if we find this information useful on multiple places. */
540 probability_reliable_p (int prob
)
542 return (profile_status_for_fn (cfun
) == PROFILE_READ
543 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
544 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
547 /* Same predicate as above, working on edges. */
549 edge_probability_reliable_p (const_edge e
)
551 return probability_reliable_p (e
->probability
);
554 /* Same predicate as edge_probability_reliable_p, working on notes. */
556 br_prob_note_reliable_p (const_rtx note
)
558 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
559 return probability_reliable_p (XINT (note
, 0));
563 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
565 gcc_assert (any_condjump_p (insn
));
566 if (!flag_guess_branch_prob
)
569 add_reg_note (insn
, REG_BR_PRED
,
570 gen_rtx_CONCAT (VOIDmode
,
571 GEN_INT ((int) predictor
),
572 GEN_INT ((int) probability
)));
575 /* Predict insn by given predictor. */
578 predict_insn_def (rtx insn
, enum br_predictor predictor
,
579 enum prediction taken
)
581 int probability
= predictor_info
[(int) predictor
].hitrate
;
584 probability
= REG_BR_PROB_BASE
- probability
;
586 predict_insn (insn
, predictor
, probability
);
589 /* Predict edge E with given probability if possible. */
592 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
595 last_insn
= BB_END (e
->src
);
597 /* We can store the branch prediction information only about
598 conditional jumps. */
599 if (!any_condjump_p (last_insn
))
602 /* We always store probability of branching. */
603 if (e
->flags
& EDGE_FALLTHRU
)
604 probability
= REG_BR_PROB_BASE
- probability
;
606 predict_insn (last_insn
, predictor
, probability
);
609 /* Predict edge E with the given PROBABILITY. */
611 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
613 gcc_assert (profile_status_for_fn (cfun
) != PROFILE_GUESSED
);
614 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && EDGE_COUNT (e
->src
->succs
) >
616 && flag_guess_branch_prob
&& optimize
)
618 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
619 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
621 i
->ep_next
= (struct edge_prediction
*) *preds
;
623 i
->ep_probability
= probability
;
624 i
->ep_predictor
= predictor
;
629 /* Remove all predictions on given basic block that are attached
632 remove_predictions_associated_with_edge (edge e
)
639 preds
= pointer_map_contains (bb_predictions
, e
->src
);
643 struct edge_prediction
**prediction
= (struct edge_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 void **preds
= pointer_map_contains (bb_predictions
, bb
);
666 struct edge_prediction
*pred
, *next
;
671 for (pred
= (struct edge_prediction
*) *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
)
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 ");
743 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
746 fprintf (file
, " hit ");
747 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
748 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
752 fprintf (file
, "\n");
755 /* We can not predict the probabilities of outgoing edges of bb. Set them
756 evenly and hope for the best. */
758 set_even_probabilities (basic_block bb
)
764 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
765 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
767 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
768 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
769 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
774 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
775 note if not already present. Remove now useless REG_BR_PRED notes. */
778 combine_predictions_for_insn (rtx insn
, basic_block bb
)
783 int best_probability
= PROB_EVEN
;
784 enum br_predictor best_predictor
= END_PREDICTORS
;
785 int combined_probability
= REG_BR_PROB_BASE
/ 2;
787 bool first_match
= false;
790 if (!can_predict_insn_p (insn
))
792 set_even_probabilities (bb
);
796 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
797 pnote
= ®_NOTES (insn
);
799 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
802 /* We implement "first match" heuristics and use probability guessed
803 by predictor with smallest index. */
804 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
805 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
807 enum br_predictor predictor
= ((enum br_predictor
)
808 INTVAL (XEXP (XEXP (note
, 0), 0)));
809 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
812 if (best_predictor
> predictor
)
813 best_probability
= probability
, best_predictor
= predictor
;
815 d
= (combined_probability
* probability
816 + (REG_BR_PROB_BASE
- combined_probability
)
817 * (REG_BR_PROB_BASE
- probability
));
819 /* Use FP math to avoid overflows of 32bit integers. */
821 /* If one probability is 0% and one 100%, avoid division by zero. */
822 combined_probability
= REG_BR_PROB_BASE
/ 2;
824 combined_probability
= (((double) combined_probability
) * probability
825 * REG_BR_PROB_BASE
/ d
+ 0.5);
828 /* Decide which heuristic to use. In case we didn't match anything,
829 use no_prediction heuristic, in case we did match, use either
830 first match or Dempster-Shaffer theory depending on the flags. */
832 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
836 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
837 combined_probability
, bb
, true);
840 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
842 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
847 combined_probability
= best_probability
;
848 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
852 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
854 enum br_predictor predictor
= ((enum br_predictor
)
855 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
856 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
858 dump_prediction (dump_file
, predictor
, probability
, bb
,
859 !first_match
|| best_predictor
== predictor
);
860 *pnote
= XEXP (*pnote
, 1);
863 pnote
= &XEXP (*pnote
, 1);
868 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
870 /* Save the prediction into CFG in case we are seeing non-degenerated
872 if (!single_succ_p (bb
))
874 BRANCH_EDGE (bb
)->probability
= combined_probability
;
875 FALLTHRU_EDGE (bb
)->probability
876 = REG_BR_PROB_BASE
- combined_probability
;
879 else if (!single_succ_p (bb
))
881 int prob
= XINT (prob_note
, 0);
883 BRANCH_EDGE (bb
)->probability
= prob
;
884 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
887 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
890 /* Combine predictions into single probability and store them into CFG.
891 Remove now useless prediction entries. */
894 combine_predictions_for_bb (basic_block bb
)
896 int best_probability
= PROB_EVEN
;
897 enum br_predictor best_predictor
= END_PREDICTORS
;
898 int combined_probability
= REG_BR_PROB_BASE
/ 2;
900 bool first_match
= false;
902 struct edge_prediction
*pred
;
904 edge e
, first
= NULL
, second
= NULL
;
908 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
909 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
912 if (first
&& !second
)
918 /* When there is no successor or only one choice, prediction is easy.
920 We are lazy for now and predict only basic blocks with two outgoing
921 edges. It is possible to predict generic case too, but we have to
922 ignore first match heuristics and do more involved combining. Implement
927 set_even_probabilities (bb
);
928 clear_bb_predictions (bb
);
930 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
936 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
938 preds
= pointer_map_contains (bb_predictions
, bb
);
941 /* We implement "first match" heuristics and use probability guessed
942 by predictor with smallest index. */
943 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
945 enum br_predictor predictor
= pred
->ep_predictor
;
946 int probability
= pred
->ep_probability
;
948 if (pred
->ep_edge
!= first
)
949 probability
= REG_BR_PROB_BASE
- probability
;
952 /* First match heuristics would be widly confused if we predicted
954 if (best_predictor
> predictor
)
956 struct edge_prediction
*pred2
;
957 int prob
= probability
;
959 for (pred2
= (struct edge_prediction
*) *preds
;
960 pred2
; pred2
= pred2
->ep_next
)
961 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
963 int probability2
= pred
->ep_probability
;
965 if (pred2
->ep_edge
!= first
)
966 probability2
= REG_BR_PROB_BASE
- probability2
;
968 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
969 (probability2
< REG_BR_PROB_BASE
/ 2))
972 /* If the same predictor later gave better result, go for it! */
973 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
974 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
978 best_probability
= prob
, best_predictor
= predictor
;
981 d
= (combined_probability
* probability
982 + (REG_BR_PROB_BASE
- combined_probability
)
983 * (REG_BR_PROB_BASE
- probability
));
985 /* Use FP math to avoid overflows of 32bit integers. */
987 /* If one probability is 0% and one 100%, avoid division by zero. */
988 combined_probability
= REG_BR_PROB_BASE
/ 2;
990 combined_probability
= (((double) combined_probability
)
992 * REG_BR_PROB_BASE
/ d
+ 0.5);
996 /* Decide which heuristic to use. In case we didn't match anything,
997 use no_prediction heuristic, in case we did match, use either
998 first match or Dempster-Shaffer theory depending on the flags. */
1000 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1004 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
1007 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1009 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1014 combined_probability
= best_probability
;
1015 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
1019 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1021 enum br_predictor predictor
= pred
->ep_predictor
;
1022 int probability
= pred
->ep_probability
;
1024 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
1025 probability
= REG_BR_PROB_BASE
- probability
;
1026 dump_prediction (dump_file
, predictor
, probability
, bb
,
1027 !first_match
|| best_predictor
== predictor
);
1030 clear_bb_predictions (bb
);
1034 first
->probability
= combined_probability
;
1035 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1039 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1040 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1042 T1 and T2 should be one of the following cases:
1043 1. T1 is SSA_NAME, T2 is NULL
1044 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1045 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1048 strips_small_constant (tree t1
, tree t2
)
1055 else if (TREE_CODE (t1
) == SSA_NAME
)
1057 else if (tree_fits_shwi_p (t1
))
1058 value
= tree_to_shwi (t1
);
1064 else if (tree_fits_shwi_p (t2
))
1065 value
= tree_to_shwi (t2
);
1066 else if (TREE_CODE (t2
) == SSA_NAME
)
1074 if (value
<= 4 && value
>= -4)
1080 /* Return the SSA_NAME in T or T's operands.
1081 Return NULL if SSA_NAME cannot be found. */
1084 get_base_value (tree t
)
1086 if (TREE_CODE (t
) == SSA_NAME
)
1089 if (!BINARY_CLASS_P (t
))
1092 switch (TREE_OPERAND_LENGTH (t
))
1095 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1097 return strips_small_constant (TREE_OPERAND (t
, 0),
1098 TREE_OPERAND (t
, 1));
1104 /* Check the compare STMT in LOOP. If it compares an induction
1105 variable to a loop invariant, return true, and save
1106 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1107 Otherwise return false and set LOOP_INVAIANT to NULL. */
1110 is_comparison_with_loop_invariant_p (gimple stmt
, struct loop
*loop
,
1111 tree
*loop_invariant
,
1112 enum tree_code
*compare_code
,
1116 tree op0
, op1
, bound
, base
;
1118 enum tree_code code
;
1121 code
= gimple_cond_code (stmt
);
1122 *loop_invariant
= NULL
;
1138 op0
= gimple_cond_lhs (stmt
);
1139 op1
= gimple_cond_rhs (stmt
);
1141 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1142 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1144 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1146 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1148 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1149 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1151 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1152 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1155 if (integer_zerop (iv0
.step
))
1157 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1158 code
= invert_tree_comparison (code
, false);
1161 if (tree_fits_shwi_p (iv1
.step
))
1170 if (tree_fits_shwi_p (iv0
.step
))
1176 if (TREE_CODE (bound
) != INTEGER_CST
)
1177 bound
= get_base_value (bound
);
1180 if (TREE_CODE (base
) != INTEGER_CST
)
1181 base
= get_base_value (base
);
1185 *loop_invariant
= bound
;
1186 *compare_code
= code
;
1188 *loop_iv_base
= base
;
1192 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1195 expr_coherent_p (tree t1
, tree t2
)
1198 tree ssa_name_1
= NULL
;
1199 tree ssa_name_2
= NULL
;
1201 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1202 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1207 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1209 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1212 /* Check to see if t1 is expressed/defined with t2. */
1213 stmt
= SSA_NAME_DEF_STMT (t1
);
1214 gcc_assert (stmt
!= NULL
);
1215 if (is_gimple_assign (stmt
))
1217 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1218 if (ssa_name_1
&& ssa_name_1
== t2
)
1222 /* Check to see if t2 is expressed/defined with t1. */
1223 stmt
= SSA_NAME_DEF_STMT (t2
);
1224 gcc_assert (stmt
!= NULL
);
1225 if (is_gimple_assign (stmt
))
1227 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1228 if (ssa_name_2
&& ssa_name_2
== t1
)
1232 /* Compare if t1 and t2's def_stmts are identical. */
1233 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1239 /* Predict branch probability of BB when BB contains a branch that compares
1240 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1241 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1244 for (int i = 0; i < bound; i++) {
1251 In this loop, we will predict the branch inside the loop to be taken. */
1254 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1255 tree loop_bound_var
,
1256 tree loop_iv_base_var
,
1257 enum tree_code loop_bound_code
,
1258 int loop_bound_step
)
1261 tree compare_var
, compare_base
;
1262 enum tree_code compare_code
;
1263 tree compare_step_var
;
1267 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1268 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1269 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1272 stmt
= last_stmt (bb
);
1273 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1275 if (!is_comparison_with_loop_invariant_p (stmt
, loop
, &compare_var
,
1281 /* Find the taken edge. */
1282 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1283 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1286 /* When comparing an IV to a loop invariant, NE is more likely to be
1287 taken while EQ is more likely to be not-taken. */
1288 if (compare_code
== NE_EXPR
)
1290 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1293 else if (compare_code
== EQ_EXPR
)
1295 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1299 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1302 /* If loop bound, base and compare bound are all constants, we can
1303 calculate the probability directly. */
1304 if (tree_fits_shwi_p (loop_bound_var
)
1305 && tree_fits_shwi_p (compare_var
)
1306 && tree_fits_shwi_p (compare_base
))
1309 bool of
, overflow
= false;
1310 double_int mod
, compare_count
, tem
, loop_count
;
1312 double_int loop_bound
= tree_to_double_int (loop_bound_var
);
1313 double_int compare_bound
= tree_to_double_int (compare_var
);
1314 double_int base
= tree_to_double_int (compare_base
);
1315 double_int compare_step
= tree_to_double_int (compare_step_var
);
1317 /* (loop_bound - base) / compare_step */
1318 tem
= loop_bound
.sub_with_overflow (base
, &of
);
1320 loop_count
= tem
.divmod_with_overflow (compare_step
,
1325 if ((!compare_step
.is_negative ())
1326 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1328 /* (loop_bound - compare_bound) / compare_step */
1329 tem
= loop_bound
.sub_with_overflow (compare_bound
, &of
);
1331 compare_count
= tem
.divmod_with_overflow (compare_step
,
1338 /* (compare_bound - base) / compare_step */
1339 tem
= compare_bound
.sub_with_overflow (base
, &of
);
1341 compare_count
= tem
.divmod_with_overflow (compare_step
,
1346 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1348 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1350 if (compare_count
.is_negative ())
1351 compare_count
= double_int_zero
;
1352 if (loop_count
.is_negative ())
1353 loop_count
= double_int_zero
;
1354 if (loop_count
.is_zero ())
1356 else if (compare_count
.scmp (loop_count
) == 1)
1357 probability
= REG_BR_PROB_BASE
;
1360 /* If loop_count is too big, such that REG_BR_PROB_BASE * loop_count
1361 could overflow, shift both loop_count and compare_count right
1362 a bit so that it doesn't overflow. Note both counts are known not
1363 to be negative at this point. */
1364 int clz_bits
= clz_hwi (loop_count
.high
);
1365 gcc_assert (REG_BR_PROB_BASE
< 32768);
1368 loop_count
.arshift (16 - clz_bits
, HOST_BITS_PER_DOUBLE_INT
);
1369 compare_count
.arshift (16 - clz_bits
, HOST_BITS_PER_DOUBLE_INT
);
1371 tem
= compare_count
.mul_with_sign (double_int::from_shwi
1372 (REG_BR_PROB_BASE
), true, &of
);
1374 tem
= tem
.divmod (loop_count
, true, TRUNC_DIV_EXPR
, &mod
);
1375 probability
= tem
.to_uhwi ();
1379 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1384 if (expr_coherent_p (loop_bound_var
, compare_var
))
1386 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1387 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1388 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1389 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1390 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1391 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1392 else if (loop_bound_code
== NE_EXPR
)
1394 /* If the loop backedge condition is "(i != bound)", we do
1395 the comparison based on the step of IV:
1396 * step < 0 : backedge condition is like (i > bound)
1397 * step > 0 : backedge condition is like (i < bound) */
1398 gcc_assert (loop_bound_step
!= 0);
1399 if (loop_bound_step
> 0
1400 && (compare_code
== LT_EXPR
1401 || compare_code
== LE_EXPR
))
1402 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1403 else if (loop_bound_step
< 0
1404 && (compare_code
== GT_EXPR
1405 || compare_code
== GE_EXPR
))
1406 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1408 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1411 /* The branch is predicted not-taken if loop_bound_code is
1412 opposite with compare_code. */
1413 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1415 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1418 for (i = s; i < h; i++)
1420 The branch should be predicted taken. */
1421 if (loop_bound_step
> 0
1422 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1423 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1424 else if (loop_bound_step
< 0
1425 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1426 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1428 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1432 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1433 exits are resulted from short-circuit conditions that will generate an
1436 if (foo() || global > 10)
1439 This will be translated into:
1444 if foo() goto BB6 else goto BB5
1446 if global > 10 goto BB6 else goto BB7
1450 iftmp = (PHI 0(BB5), 1(BB6))
1451 if iftmp == 1 goto BB8 else goto BB3
1453 outside of the loop...
1455 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1456 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1457 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1458 exits to predict them using PRED_LOOP_EXIT. */
1461 predict_extra_loop_exits (edge exit_edge
)
1464 bool check_value_one
;
1466 tree cmp_rhs
, cmp_lhs
;
1467 gimple cmp_stmt
= last_stmt (exit_edge
->src
);
1469 if (!cmp_stmt
|| gimple_code (cmp_stmt
) != GIMPLE_COND
)
1471 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1472 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1473 if (!TREE_CONSTANT (cmp_rhs
)
1474 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1476 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1479 /* If check_value_one is true, only the phi_args with value '1' will lead
1480 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1482 check_value_one
= (((integer_onep (cmp_rhs
))
1483 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1484 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1486 phi_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1487 if (!phi_stmt
|| gimple_code (phi_stmt
) != GIMPLE_PHI
)
1490 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1494 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1495 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1497 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1499 if ((check_value_one
^ integer_onep (val
)) == 1)
1501 if (EDGE_COUNT (e
->src
->succs
) != 1)
1503 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1507 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1508 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1512 /* Predict edge probabilities by exploiting loop structure. */
1515 predict_loops (void)
1519 /* Try to predict out blocks in a loop that are not part of a
1521 FOR_EACH_LOOP (loop
, 0)
1523 basic_block bb
, *bbs
;
1524 unsigned j
, n_exits
;
1526 struct tree_niter_desc niter_desc
;
1528 struct nb_iter_bound
*nb_iter
;
1529 enum tree_code loop_bound_code
= ERROR_MARK
;
1530 tree loop_bound_step
= NULL
;
1531 tree loop_bound_var
= NULL
;
1532 tree loop_iv_base
= NULL
;
1535 exits
= get_loop_exit_edges (loop
);
1536 n_exits
= exits
.length ();
1543 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1546 HOST_WIDE_INT nitercst
;
1547 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1549 enum br_predictor predictor
;
1551 predict_extra_loop_exits (ex
);
1553 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1554 niter
= niter_desc
.niter
;
1555 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1556 niter
= loop_niter_by_eval (loop
, ex
);
1558 if (TREE_CODE (niter
) == INTEGER_CST
)
1560 if (tree_fits_uhwi_p (niter
)
1562 && compare_tree_int (niter
, max
- 1) == -1)
1563 nitercst
= tree_to_uhwi (niter
) + 1;
1566 predictor
= PRED_LOOP_ITERATIONS
;
1568 /* If we have just one exit and we can derive some information about
1569 the number of iterations of the loop from the statements inside
1570 the loop, use it to predict this exit. */
1571 else if (n_exits
== 1)
1573 nitercst
= estimated_stmt_executions_int (loop
);
1579 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1584 /* If the prediction for number of iterations is zero, do not
1585 predict the exit edges. */
1589 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1590 predict_edge (ex
, predictor
, probability
);
1594 /* Find information about loop bound variables. */
1595 for (nb_iter
= loop
->bounds
; nb_iter
;
1596 nb_iter
= nb_iter
->next
)
1598 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1600 stmt
= nb_iter
->stmt
;
1603 if (!stmt
&& last_stmt (loop
->header
)
1604 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1605 stmt
= last_stmt (loop
->header
);
1607 is_comparison_with_loop_invariant_p (stmt
, loop
,
1613 bbs
= get_loop_body (loop
);
1615 for (j
= 0; j
< loop
->num_nodes
; j
++)
1617 int header_found
= 0;
1623 /* Bypass loop heuristics on continue statement. These
1624 statements construct loops via "non-loop" constructs
1625 in the source language and are better to be handled
1627 if (predicted_by_p (bb
, PRED_CONTINUE
))
1630 /* Loop branch heuristics - predict an edge back to a
1631 loop's head as taken. */
1632 if (bb
== loop
->latch
)
1634 e
= find_edge (loop
->latch
, loop
->header
);
1638 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1642 /* Loop exit heuristics - predict an edge exiting the loop if the
1643 conditional has no loop header successors as not taken. */
1645 /* If we already used more reliable loop exit predictors, do not
1646 bother with PRED_LOOP_EXIT. */
1647 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1648 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1650 /* For loop with many exits we don't want to predict all exits
1651 with the pretty large probability, because if all exits are
1652 considered in row, the loop would be predicted to iterate
1653 almost never. The code to divide probability by number of
1654 exits is very rough. It should compute the number of exits
1655 taken in each patch through function (not the overall number
1656 of exits that might be a lot higher for loops with wide switch
1657 statements in them) and compute n-th square root.
1659 We limit the minimal probability by 2% to avoid
1660 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1661 as this was causing regression in perl benchmark containing such
1664 int probability
= ((REG_BR_PROB_BASE
1665 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1667 if (probability
< HITRATE (2))
1668 probability
= HITRATE (2);
1669 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1670 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1671 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1672 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1675 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1677 tree_to_shwi (loop_bound_step
));
1680 /* Free basic blocks from get_loop_body. */
1685 /* Attempt to predict probabilities of BB outgoing edges using local
1688 bb_estimate_probability_locally (basic_block bb
)
1690 rtx last_insn
= BB_END (bb
);
1693 if (! can_predict_insn_p (last_insn
))
1695 cond
= get_condition (last_insn
, NULL
, false, false);
1699 /* Try "pointer heuristic."
1700 A comparison ptr == 0 is predicted as false.
1701 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1702 if (COMPARISON_P (cond
)
1703 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1704 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1706 if (GET_CODE (cond
) == EQ
)
1707 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1708 else if (GET_CODE (cond
) == NE
)
1709 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1713 /* Try "opcode heuristic."
1714 EQ tests are usually false and NE tests are usually true. Also,
1715 most quantities are positive, so we can make the appropriate guesses
1716 about signed comparisons against zero. */
1717 switch (GET_CODE (cond
))
1720 /* Unconditional branch. */
1721 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1722 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1727 /* Floating point comparisons appears to behave in a very
1728 unpredictable way because of special role of = tests in
1730 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1732 /* Comparisons with 0 are often used for booleans and there is
1733 nothing useful to predict about them. */
1734 else if (XEXP (cond
, 1) == const0_rtx
1735 || XEXP (cond
, 0) == const0_rtx
)
1738 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1743 /* Floating point comparisons appears to behave in a very
1744 unpredictable way because of special role of = tests in
1746 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1748 /* Comparisons with 0 are often used for booleans and there is
1749 nothing useful to predict about them. */
1750 else if (XEXP (cond
, 1) == const0_rtx
1751 || XEXP (cond
, 0) == const0_rtx
)
1754 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1758 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1762 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1767 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1768 || XEXP (cond
, 1) == constm1_rtx
)
1769 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1774 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1775 || XEXP (cond
, 1) == constm1_rtx
)
1776 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1784 /* Set edge->probability for each successor edge of BB. */
1786 guess_outgoing_edge_probabilities (basic_block bb
)
1788 bb_estimate_probability_locally (bb
);
1789 combine_predictions_for_insn (BB_END (bb
), bb
);
1792 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
1794 /* Helper function for expr_expected_value. */
1797 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1798 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
1803 *predictor
= PRED_UNCONDITIONAL
;
1805 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1807 if (TREE_CONSTANT (op0
))
1810 if (code
!= SSA_NAME
)
1813 def
= SSA_NAME_DEF_STMT (op0
);
1815 /* If we were already here, break the infinite cycle. */
1816 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1819 if (gimple_code (def
) == GIMPLE_PHI
)
1821 /* All the arguments of the PHI node must have the same constant
1823 int i
, n
= gimple_phi_num_args (def
);
1824 tree val
= NULL
, new_val
;
1826 for (i
= 0; i
< n
; i
++)
1828 tree arg
= PHI_ARG_DEF (def
, i
);
1829 enum br_predictor predictor2
;
1831 /* If this PHI has itself as an argument, we cannot
1832 determine the string length of this argument. However,
1833 if we can find an expected constant value for the other
1834 PHI args then we can still be sure that this is
1835 likely a constant. So be optimistic and just
1836 continue with the next argument. */
1837 if (arg
== PHI_RESULT (def
))
1840 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
1842 /* It is difficult to combine value predictors. Simply assume
1843 that later predictor is weaker and take its prediction. */
1844 if (predictor
&& *predictor
< predictor2
)
1845 *predictor
= predictor2
;
1850 else if (!operand_equal_p (val
, new_val
, false))
1855 if (is_gimple_assign (def
))
1857 if (gimple_assign_lhs (def
) != op0
)
1860 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1861 gimple_assign_rhs1 (def
),
1862 gimple_assign_rhs_code (def
),
1863 gimple_assign_rhs2 (def
),
1864 visited
, predictor
);
1867 if (is_gimple_call (def
))
1869 tree decl
= gimple_call_fndecl (def
);
1872 if (gimple_call_internal_p (def
)
1873 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
1875 gcc_assert (gimple_call_num_args (def
) == 3);
1876 tree val
= gimple_call_arg (def
, 0);
1877 if (TREE_CONSTANT (val
))
1881 *predictor
= PRED_BUILTIN_EXPECT
;
1882 tree val2
= gimple_call_arg (def
, 2);
1883 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
1884 && tree_fits_uhwi_p (val2
)
1885 && tree_to_uhwi (val2
) < END_PREDICTORS
);
1886 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
1888 return gimple_call_arg (def
, 1);
1892 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1893 switch (DECL_FUNCTION_CODE (decl
))
1895 case BUILT_IN_EXPECT
:
1898 if (gimple_call_num_args (def
) != 2)
1900 val
= gimple_call_arg (def
, 0);
1901 if (TREE_CONSTANT (val
))
1904 *predictor
= PRED_BUILTIN_EXPECT
;
1905 return gimple_call_arg (def
, 1);
1908 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1909 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1910 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1911 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1912 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1913 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1914 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1915 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1916 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1917 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1918 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1919 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1920 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1921 /* Assume that any given atomic operation has low contention,
1922 and thus the compare-and-swap operation succeeds. */
1924 *predictor
= PRED_COMPARE_AND_SWAP
;
1925 return boolean_true_node
;
1932 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1935 enum br_predictor predictor2
;
1936 op0
= expr_expected_value (op0
, visited
, predictor
);
1939 op1
= expr_expected_value (op1
, visited
, &predictor2
);
1940 if (predictor
&& *predictor
< predictor2
)
1941 *predictor
= predictor2
;
1944 res
= fold_build2 (code
, type
, op0
, op1
);
1945 if (TREE_CONSTANT (res
))
1949 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1952 op0
= expr_expected_value (op0
, visited
, predictor
);
1955 res
= fold_build1 (code
, type
, op0
);
1956 if (TREE_CONSTANT (res
))
1963 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1964 The function is used by builtin_expect branch predictor so the evidence
1965 must come from this construct and additional possible constant folding.
1967 We may want to implement more involved value guess (such as value range
1968 propagation based prediction), but such tricks shall go to new
1972 expr_expected_value (tree expr
, bitmap visited
,
1973 enum br_predictor
*predictor
)
1975 enum tree_code code
;
1978 if (TREE_CONSTANT (expr
))
1981 *predictor
= PRED_UNCONDITIONAL
;
1985 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1986 return expr_expected_value_1 (TREE_TYPE (expr
),
1987 op0
, code
, op1
, visited
, predictor
);
1990 /* Predict using opcode of the last statement in basic block. */
1992 tree_predict_by_opcode (basic_block bb
)
1994 gimple stmt
= last_stmt (bb
);
2002 enum br_predictor predictor
;
2004 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2006 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2007 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2009 op0
= gimple_cond_lhs (stmt
);
2010 op1
= gimple_cond_rhs (stmt
);
2011 cmp
= gimple_cond_code (stmt
);
2012 type
= TREE_TYPE (op0
);
2013 visited
= BITMAP_ALLOC (NULL
);
2014 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
2016 BITMAP_FREE (visited
);
2017 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2019 if (predictor
== PRED_BUILTIN_EXPECT
)
2021 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2023 gcc_assert (percent
>= 0 && percent
<= 100);
2024 if (integer_zerop (val
))
2025 percent
= 100 - percent
;
2026 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2029 predict_edge (then_edge
, predictor
,
2030 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2032 /* Try "pointer heuristic."
2033 A comparison ptr == 0 is predicted as false.
2034 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2035 if (POINTER_TYPE_P (type
))
2038 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2039 else if (cmp
== NE_EXPR
)
2040 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2044 /* Try "opcode heuristic."
2045 EQ tests are usually false and NE tests are usually true. Also,
2046 most quantities are positive, so we can make the appropriate guesses
2047 about signed comparisons against zero. */
2052 /* Floating point comparisons appears to behave in a very
2053 unpredictable way because of special role of = tests in
2055 if (FLOAT_TYPE_P (type
))
2057 /* Comparisons with 0 are often used for booleans and there is
2058 nothing useful to predict about them. */
2059 else if (integer_zerop (op0
) || integer_zerop (op1
))
2062 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2067 /* Floating point comparisons appears to behave in a very
2068 unpredictable way because of special role of = tests in
2070 if (FLOAT_TYPE_P (type
))
2072 /* Comparisons with 0 are often used for booleans and there is
2073 nothing useful to predict about them. */
2074 else if (integer_zerop (op0
)
2075 || integer_zerop (op1
))
2078 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2082 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2085 case UNORDERED_EXPR
:
2086 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2091 if (integer_zerop (op1
)
2092 || integer_onep (op1
)
2093 || integer_all_onesp (op1
)
2096 || real_minus_onep (op1
))
2097 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2102 if (integer_zerop (op1
)
2103 || integer_onep (op1
)
2104 || integer_all_onesp (op1
)
2107 || real_minus_onep (op1
))
2108 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2116 /* Try to guess whether the value of return means error code. */
2118 static enum br_predictor
2119 return_prediction (tree val
, enum prediction
*prediction
)
2123 return PRED_NO_PREDICTION
;
2124 /* Different heuristics for pointers and scalars. */
2125 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2127 /* NULL is usually not returned. */
2128 if (integer_zerop (val
))
2130 *prediction
= NOT_TAKEN
;
2131 return PRED_NULL_RETURN
;
2134 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2136 /* Negative return values are often used to indicate
2138 if (TREE_CODE (val
) == INTEGER_CST
2139 && tree_int_cst_sgn (val
) < 0)
2141 *prediction
= NOT_TAKEN
;
2142 return PRED_NEGATIVE_RETURN
;
2144 /* Constant return values seems to be commonly taken.
2145 Zero/one often represent booleans so exclude them from the
2147 if (TREE_CONSTANT (val
)
2148 && (!integer_zerop (val
) && !integer_onep (val
)))
2150 *prediction
= TAKEN
;
2151 return PRED_CONST_RETURN
;
2154 return PRED_NO_PREDICTION
;
2157 /* Find the basic block with return expression and look up for possible
2158 return value trying to apply RETURN_PREDICTION heuristics. */
2160 apply_return_prediction (void)
2162 gimple return_stmt
= NULL
;
2166 int phi_num_args
, i
;
2167 enum br_predictor pred
;
2168 enum prediction direction
;
2171 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2173 return_stmt
= last_stmt (e
->src
);
2175 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
2180 return_val
= gimple_return_retval (return_stmt
);
2183 if (TREE_CODE (return_val
) != SSA_NAME
2184 || !SSA_NAME_DEF_STMT (return_val
)
2185 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2187 phi
= SSA_NAME_DEF_STMT (return_val
);
2188 phi_num_args
= gimple_phi_num_args (phi
);
2189 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2191 /* Avoid the degenerate case where all return values form the function
2192 belongs to same category (ie they are all positive constants)
2193 so we can hardly say something about them. */
2194 for (i
= 1; i
< phi_num_args
; i
++)
2195 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2197 if (i
!= phi_num_args
)
2198 for (i
= 0; i
< phi_num_args
; i
++)
2200 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2201 if (pred
!= PRED_NO_PREDICTION
)
2202 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2207 /* Look for basic block that contains unlikely to happen events
2208 (such as noreturn calls) and mark all paths leading to execution
2209 of this basic blocks as unlikely. */
2212 tree_bb_level_predictions (void)
2215 bool has_return_edges
= false;
2219 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2220 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2222 has_return_edges
= true;
2226 apply_return_prediction ();
2228 FOR_EACH_BB_FN (bb
, cfun
)
2230 gimple_stmt_iterator gsi
;
2232 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2234 gimple stmt
= gsi_stmt (gsi
);
2237 if (is_gimple_call (stmt
))
2239 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2240 && has_return_edges
)
2241 predict_paths_leading_to (bb
, PRED_NORETURN
,
2243 decl
= gimple_call_fndecl (stmt
);
2245 && lookup_attribute ("cold",
2246 DECL_ATTRIBUTES (decl
)))
2247 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2250 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2252 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2253 gimple_predict_outcome (stmt
));
2254 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2255 hints to callers. */
2261 #ifdef ENABLE_CHECKING
2263 /* Callback for pointer_map_traverse, asserts that the pointer map is
2267 assert_is_empty (const void *key ATTRIBUTE_UNUSED
, void **value
,
2268 void *data ATTRIBUTE_UNUSED
)
2270 gcc_assert (!*value
);
2275 /* Predict branch probabilities and estimate profile for basic block BB. */
2278 tree_estimate_probability_bb (basic_block bb
)
2284 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2286 /* Predict edges to user labels with attributes. */
2287 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2289 gimple_stmt_iterator gi
;
2290 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2292 gimple stmt
= gsi_stmt (gi
);
2295 if (gimple_code (stmt
) != GIMPLE_LABEL
)
2297 decl
= gimple_label_label (stmt
);
2298 if (DECL_ARTIFICIAL (decl
))
2301 /* Finally, we have a user-defined label. */
2302 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2303 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2304 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2305 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2309 /* Predict early returns to be probable, as we've already taken
2310 care for error returns and other cases are often used for
2311 fast paths through function.
2313 Since we've already removed the return statements, we are
2314 looking for CFG like:
2324 if (e
->dest
!= bb
->next_bb
2325 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2326 && single_succ_p (e
->dest
)
2327 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2328 && (last
= last_stmt (e
->dest
)) != NULL
2329 && gimple_code (last
) == GIMPLE_RETURN
)
2334 if (single_succ_p (bb
))
2336 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2337 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2338 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2339 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2340 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2343 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2344 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2345 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2346 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2349 /* Look for block we are guarding (ie we dominate it,
2350 but it doesn't postdominate us). */
2351 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2352 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2353 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2355 gimple_stmt_iterator bi
;
2357 /* The call heuristic claims that a guarded function call
2358 is improbable. This is because such calls are often used
2359 to signal exceptional situations such as printing error
2361 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2364 gimple stmt
= gsi_stmt (bi
);
2365 if (is_gimple_call (stmt
)
2366 /* Constant and pure calls are hardly used to signalize
2367 something exceptional. */
2368 && gimple_has_side_effects (stmt
))
2370 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2376 tree_predict_by_opcode (bb
);
2379 /* Predict branch probabilities and estimate profile of the tree CFG.
2380 This function can be called from the loop optimizers to recompute
2381 the profile information. */
2384 tree_estimate_probability (void)
2388 add_noreturn_fake_exit_edges ();
2389 connect_infinite_loops_to_exit ();
2390 /* We use loop_niter_by_eval, which requires that the loops have
2392 create_preheaders (CP_SIMPLE_PREHEADERS
);
2393 calculate_dominance_info (CDI_POST_DOMINATORS
);
2395 bb_predictions
= pointer_map_create ();
2396 tree_bb_level_predictions ();
2397 record_loop_exits ();
2399 if (number_of_loops (cfun
) > 1)
2402 FOR_EACH_BB_FN (bb
, cfun
)
2403 tree_estimate_probability_bb (bb
);
2405 FOR_EACH_BB_FN (bb
, cfun
)
2406 combine_predictions_for_bb (bb
);
2408 #ifdef ENABLE_CHECKING
2409 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
2411 pointer_map_destroy (bb_predictions
);
2412 bb_predictions
= NULL
;
2414 estimate_bb_frequencies (false);
2415 free_dominance_info (CDI_POST_DOMINATORS
);
2416 remove_fake_exit_edges ();
2419 /* Predict edges to successors of CUR whose sources are not postdominated by
2420 BB by PRED and recurse to all postdominators. */
2423 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2424 enum br_predictor pred
,
2425 enum prediction taken
,
2432 /* We are looking for all edges forming edge cut induced by
2433 set of all blocks postdominated by BB. */
2434 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2435 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2436 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2442 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2443 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2445 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2447 /* See if there is an edge from e->src that is not abnormal
2448 and does not lead to BB. */
2449 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2451 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2452 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2458 /* If there is non-abnormal path leaving e->src, predict edge
2459 using predictor. Otherwise we need to look for paths
2462 The second may lead to infinite loop in the case we are predicitng
2463 regions that are only reachable by abnormal edges. We simply
2464 prevent visiting given BB twice. */
2466 predict_edge_def (e
, pred
, taken
);
2467 else if (bitmap_set_bit (visited
, e
->src
->index
))
2468 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2470 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2472 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2473 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2476 /* Sets branch probabilities according to PREDiction and
2480 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2481 enum prediction taken
)
2483 bitmap visited
= BITMAP_ALLOC (NULL
);
2484 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2485 BITMAP_FREE (visited
);
2488 /* Like predict_paths_leading_to but take edge instead of basic block. */
2491 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2492 enum prediction taken
)
2494 bool has_nonloop_edge
= false;
2498 basic_block bb
= e
->src
;
2499 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2500 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2501 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2502 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2504 has_nonloop_edge
= true;
2507 if (!has_nonloop_edge
)
2509 bitmap visited
= BITMAP_ALLOC (NULL
);
2510 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2511 BITMAP_FREE (visited
);
2514 predict_edge_def (e
, pred
, taken
);
2517 /* This is used to carry information about basic blocks. It is
2518 attached to the AUX field of the standard CFG block. */
2520 typedef struct block_info_def
2522 /* Estimated frequency of execution of basic_block. */
2525 /* To keep queue of basic blocks to process. */
2528 /* Number of predecessors we need to visit first. */
2532 /* Similar information for edges. */
2533 typedef struct edge_info_def
2535 /* In case edge is a loopback edge, the probability edge will be reached
2536 in case header is. Estimated number of iterations of the loop can be
2537 then computed as 1 / (1 - back_edge_prob). */
2538 sreal back_edge_prob
;
2539 /* True if the edge is a loopback edge in the natural loop. */
2540 unsigned int back_edge
:1;
2543 #define BLOCK_INFO(B) ((block_info) (B)->aux)
2544 #define EDGE_INFO(E) ((edge_info) (E)->aux)
2546 /* Helper function for estimate_bb_frequencies.
2547 Propagate the frequencies in blocks marked in
2548 TOVISIT, starting in HEAD. */
2551 propagate_freq (basic_block head
, bitmap tovisit
)
2560 /* For each basic block we need to visit count number of his predecessors
2561 we need to visit first. */
2562 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2567 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2569 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2571 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2573 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2575 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2577 "Irreducible region hit, ignoring edge to %i->%i\n",
2578 e
->src
->index
, bb
->index
);
2580 BLOCK_INFO (bb
)->npredecessors
= count
;
2581 /* When function never returns, we will never process exit block. */
2582 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2583 bb
->count
= bb
->frequency
= 0;
2586 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
2588 for (bb
= head
; bb
; bb
= nextbb
)
2591 sreal cyclic_probability
, frequency
;
2593 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
2594 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
2596 nextbb
= BLOCK_INFO (bb
)->next
;
2597 BLOCK_INFO (bb
)->next
= NULL
;
2599 /* Compute frequency of basic block. */
2602 #ifdef ENABLE_CHECKING
2603 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2604 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2605 || (e
->flags
& EDGE_DFS_BACK
));
2608 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2609 if (EDGE_INFO (e
)->back_edge
)
2611 sreal_add (&cyclic_probability
, &cyclic_probability
,
2612 &EDGE_INFO (e
)->back_edge_prob
);
2614 else if (!(e
->flags
& EDGE_DFS_BACK
))
2618 /* frequency += (e->probability
2619 * BLOCK_INFO (e->src)->frequency /
2620 REG_BR_PROB_BASE); */
2622 sreal_init (&tmp
, e
->probability
, 0);
2623 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
2624 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
2625 sreal_add (&frequency
, &frequency
, &tmp
);
2628 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
2630 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
2631 sizeof (frequency
));
2635 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
2637 memcpy (&cyclic_probability
, &real_almost_one
,
2638 sizeof (real_almost_one
));
2641 /* BLOCK_INFO (bb)->frequency = frequency
2642 / (1 - cyclic_probability) */
2644 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
2645 sreal_div (&BLOCK_INFO (bb
)->frequency
,
2646 &frequency
, &cyclic_probability
);
2650 bitmap_clear_bit (tovisit
, bb
->index
);
2652 e
= find_edge (bb
, head
);
2657 /* EDGE_INFO (e)->back_edge_prob
2658 = ((e->probability * BLOCK_INFO (bb)->frequency)
2659 / REG_BR_PROB_BASE); */
2661 sreal_init (&tmp
, e
->probability
, 0);
2662 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
2663 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2664 &tmp
, &real_inv_br_prob_base
);
2667 /* Propagate to successor blocks. */
2668 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2669 if (!(e
->flags
& EDGE_DFS_BACK
)
2670 && BLOCK_INFO (e
->dest
)->npredecessors
)
2672 BLOCK_INFO (e
->dest
)->npredecessors
--;
2673 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2678 BLOCK_INFO (last
)->next
= e
->dest
;
2686 /* Estimate frequencies in loops at same nest level. */
2689 estimate_loops_at_level (struct loop
*first_loop
)
2693 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2698 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2700 estimate_loops_at_level (loop
->inner
);
2702 /* Find current loop back edge and mark it. */
2703 e
= loop_latch_edge (loop
);
2704 EDGE_INFO (e
)->back_edge
= 1;
2706 bbs
= get_loop_body (loop
);
2707 for (i
= 0; i
< loop
->num_nodes
; i
++)
2708 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2710 propagate_freq (loop
->header
, tovisit
);
2711 BITMAP_FREE (tovisit
);
2715 /* Propagates frequencies through structure of loops. */
2718 estimate_loops (void)
2720 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2723 /* Start by estimating the frequencies in the loops. */
2724 if (number_of_loops (cfun
) > 1)
2725 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2727 /* Now propagate the frequencies through all the blocks. */
2728 FOR_ALL_BB_FN (bb
, cfun
)
2730 bitmap_set_bit (tovisit
, bb
->index
);
2732 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
2733 BITMAP_FREE (tovisit
);
2736 /* Drop the profile for NODE to guessed, and update its frequency based on
2737 whether it is expected to be hot given the CALL_COUNT. */
2740 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
2742 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2743 /* In the case where this was called by another function with a
2744 dropped profile, call_count will be 0. Since there are no
2745 non-zero call counts to this function, we don't know for sure
2746 whether it is hot, and therefore it will be marked normal below. */
2747 bool hot
= maybe_hot_count_p (NULL
, call_count
);
2751 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2752 node
->name (), node
->order
,
2753 hot
? "Function is hot" : "Function is normal");
2754 /* We only expect to miss profiles for functions that are reached
2755 via non-zero call edges in cases where the function may have
2756 been linked from another module or library (COMDATs and extern
2757 templates). See the comments below for handle_missing_profiles.
2758 Also, only warn in cases where the missing counts exceed the
2759 number of training runs. In certain cases with an execv followed
2760 by a no-return call the profile for the no-return call is not
2761 dumped and there can be a mismatch. */
2762 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
2763 && call_count
> profile_info
->runs
)
2765 if (flag_profile_correction
)
2769 "Missing counts for called function %s/%i\n",
2770 node
->name (), node
->order
);
2773 warning (0, "Missing counts for called function %s/%i",
2774 node
->name (), node
->order
);
2777 profile_status_for_fn (fn
)
2778 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2780 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2783 /* In the case of COMDAT routines, multiple object files will contain the same
2784 function and the linker will select one for the binary. In that case
2785 all the other copies from the profile instrument binary will be missing
2786 profile counts. Look for cases where this happened, due to non-zero
2787 call counts going to 0-count functions, and drop the profile to guessed
2788 so that we can use the estimated probabilities and avoid optimizing only
2791 The other case where the profile may be missing is when the routine
2792 is not going to be emitted to the object file, e.g. for "extern template"
2793 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2794 all other cases of non-zero calls to 0-count functions. */
2797 handle_missing_profiles (void)
2799 struct cgraph_node
*node
;
2800 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2801 vec
<struct cgraph_node
*> worklist
;
2802 worklist
.create (64);
2804 /* See if 0 count function has non-0 count callers. In this case we
2805 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2806 FOR_EACH_DEFINED_FUNCTION (node
)
2808 struct cgraph_edge
*e
;
2809 gcov_type call_count
= 0;
2810 gcov_type max_tp_first_run
= 0;
2811 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2815 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2817 call_count
+= e
->count
;
2819 if (e
->caller
->tp_first_run
> max_tp_first_run
)
2820 max_tp_first_run
= e
->caller
->tp_first_run
;
2823 /* If time profile is missing, let assign the maximum that comes from
2824 caller functions. */
2825 if (!node
->tp_first_run
&& max_tp_first_run
)
2826 node
->tp_first_run
= max_tp_first_run
+ 1;
2830 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2832 drop_profile (node
, call_count
);
2833 worklist
.safe_push (node
);
2837 /* Propagate the profile dropping to other 0-count COMDATs that are
2838 potentially called by COMDATs we already dropped the profile on. */
2839 while (worklist
.length () > 0)
2841 struct cgraph_edge
*e
;
2843 node
= worklist
.pop ();
2844 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2846 struct cgraph_node
*callee
= e
->callee
;
2847 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2849 if (callee
->count
> 0)
2851 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2852 && profile_status_for_fn (fn
) == PROFILE_READ
)
2854 drop_profile (node
, 0);
2855 worklist
.safe_push (callee
);
2859 worklist
.release ();
2862 /* Convert counts measured by profile driven feedback to frequencies.
2863 Return nonzero iff there was any nonzero execution count. */
2866 counts_to_freqs (void)
2868 gcov_type count_max
, true_count_max
= 0;
2871 /* Don't overwrite the estimated frequencies when the profile for
2872 the function is missing. We may drop this function PROFILE_GUESSED
2873 later in drop_profile (). */
2874 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
2877 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2878 true_count_max
= MAX (bb
->count
, true_count_max
);
2880 count_max
= MAX (true_count_max
, 1);
2881 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2882 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2884 return true_count_max
;
2887 /* Return true if function is likely to be expensive, so there is no point to
2888 optimize performance of prologue, epilogue or do inlining at the expense
2889 of code size growth. THRESHOLD is the limit of number of instructions
2890 function can execute at average to be still considered not expensive. */
2893 expensive_function_p (int threshold
)
2895 unsigned int sum
= 0;
2899 /* We can not compute accurately for large thresholds due to scaled
2901 gcc_assert (threshold
<= BB_FREQ_MAX
);
2903 /* Frequencies are out of range. This either means that function contains
2904 internal loop executing more than BB_FREQ_MAX times or profile feedback
2905 is available and function has not been executed at all. */
2906 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
2909 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2910 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
2911 FOR_EACH_BB_FN (bb
, cfun
)
2915 FOR_BB_INSNS (bb
, insn
)
2916 if (active_insn_p (insn
))
2918 sum
+= bb
->frequency
;
2927 /* Estimate and propagate basic block frequencies using the given branch
2928 probabilities. If FORCE is true, the frequencies are used to estimate
2929 the counts even when there are already non-zero profile counts. */
2932 estimate_bb_frequencies (bool force
)
2937 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
2939 static int real_values_initialized
= 0;
2941 if (!real_values_initialized
)
2943 real_values_initialized
= 1;
2944 sreal_init (&real_zero
, 0, 0);
2945 sreal_init (&real_one
, 1, 0);
2946 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2947 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2948 sreal_init (&real_one_half
, 1, -1);
2949 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2950 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2953 mark_dfs_back_edges ();
2955 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
2958 /* Set up block info for each basic block. */
2959 alloc_aux_for_blocks (sizeof (struct block_info_def
));
2960 alloc_aux_for_edges (sizeof (struct edge_info_def
));
2961 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2966 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2968 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2969 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2970 &EDGE_INFO (e
)->back_edge_prob
,
2971 &real_inv_br_prob_base
);
2975 /* First compute frequencies locally for each loop from innermost
2976 to outermost to examine frequencies for back edges. */
2979 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2980 FOR_EACH_BB_FN (bb
, cfun
)
2981 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2982 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2984 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
2985 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2989 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
2990 sreal_add (&tmp
, &tmp
, &real_one_half
);
2991 bb
->frequency
= sreal_to_int (&tmp
);
2994 free_aux_for_blocks ();
2995 free_aux_for_edges ();
2997 compute_function_frequency ();
3000 /* Decide whether function is hot, cold or unlikely executed. */
3002 compute_function_frequency (void)
3005 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
3007 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3008 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3009 node
->only_called_at_startup
= true;
3010 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3011 node
->only_called_at_exit
= true;
3013 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3015 int flags
= flags_from_decl_or_type (current_function_decl
);
3016 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3018 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3019 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3021 node
->frequency
= NODE_FREQUENCY_HOT
;
3022 else if (flags
& ECF_NORETURN
)
3023 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3024 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3025 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3026 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3027 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3028 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3032 /* Only first time try to drop function into unlikely executed.
3033 After inlining the roundoff errors may confuse us.
3034 Ipa-profile pass will drop functions only called from unlikely
3035 functions to unlikely and that is most of what we care about. */
3036 if (!cfun
->after_inlining
)
3037 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3038 FOR_EACH_BB_FN (bb
, cfun
)
3040 if (maybe_hot_bb_p (cfun
, bb
))
3042 node
->frequency
= NODE_FREQUENCY_HOT
;
3045 if (!probably_never_executed_bb_p (cfun
, bb
))
3046 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3050 /* Build PREDICT_EXPR. */
3052 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3054 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3055 build_int_cst (integer_type_node
, predictor
));
3056 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3061 predictor_name (enum br_predictor predictor
)
3063 return predictor_info
[predictor
].name
;
3066 /* Predict branch probabilities and estimate profile of the tree CFG. */
3070 const pass_data pass_data_profile
=
3072 GIMPLE_PASS
, /* type */
3073 "profile_estimate", /* name */
3074 OPTGROUP_NONE
, /* optinfo_flags */
3075 true, /* has_execute */
3076 TV_BRANCH_PROB
, /* tv_id */
3077 PROP_cfg
, /* properties_required */
3078 0, /* properties_provided */
3079 0, /* properties_destroyed */
3080 0, /* todo_flags_start */
3081 TODO_verify_ssa
, /* todo_flags_finish */
3084 class pass_profile
: public gimple_opt_pass
3087 pass_profile (gcc::context
*ctxt
)
3088 : gimple_opt_pass (pass_data_profile
, ctxt
)
3091 /* opt_pass methods: */
3092 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3093 virtual unsigned int execute (function
*);
3095 }; // class pass_profile
3098 pass_profile::execute (function
*fun
)
3102 loop_optimizer_init (LOOPS_NORMAL
);
3103 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3104 flow_loops_dump (dump_file
, NULL
, 0);
3106 mark_irreducible_loops ();
3108 nb_loops
= number_of_loops (fun
);
3112 tree_estimate_probability ();
3117 loop_optimizer_finalize ();
3118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3119 gimple_dump_cfg (dump_file
, dump_flags
);
3120 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3121 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3128 make_pass_profile (gcc::context
*ctxt
)
3130 return new pass_profile (ctxt
);
3135 const pass_data pass_data_strip_predict_hints
=
3137 GIMPLE_PASS
, /* type */
3138 "*strip_predict_hints", /* name */
3139 OPTGROUP_NONE
, /* optinfo_flags */
3140 true, /* has_execute */
3141 TV_BRANCH_PROB
, /* tv_id */
3142 PROP_cfg
, /* properties_required */
3143 0, /* properties_provided */
3144 0, /* properties_destroyed */
3145 0, /* todo_flags_start */
3146 TODO_verify_ssa
, /* todo_flags_finish */
3149 class pass_strip_predict_hints
: public gimple_opt_pass
3152 pass_strip_predict_hints (gcc::context
*ctxt
)
3153 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3156 /* opt_pass methods: */
3157 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3158 virtual unsigned int execute (function
*);
3160 }; // class pass_strip_predict_hints
3162 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3163 we no longer need. */
3165 pass_strip_predict_hints::execute (function
*fun
)
3171 FOR_EACH_BB_FN (bb
, fun
)
3173 gimple_stmt_iterator bi
;
3174 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3176 gimple stmt
= gsi_stmt (bi
);
3178 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3180 gsi_remove (&bi
, true);
3183 else if (is_gimple_call (stmt
))
3185 tree fndecl
= gimple_call_fndecl (stmt
);
3188 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3189 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3190 && gimple_call_num_args (stmt
) == 2)
3191 || (gimple_call_internal_p (stmt
)
3192 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3194 var
= gimple_call_lhs (stmt
);
3198 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3199 gsi_replace (&bi
, ass_stmt
, true);
3203 gsi_remove (&bi
, true);
3217 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3219 return new pass_strip_predict_hints (ctxt
);
3222 /* Rebuild function frequencies. Passes are in general expected to
3223 maintain profile by hand, however in some cases this is not possible:
3224 for example when inlining several functions with loops freuqencies might run
3225 out of scale and thus needs to be recomputed. */
3228 rebuild_frequencies (void)
3230 timevar_push (TV_REBUILD_FREQUENCIES
);
3232 /* When the max bb count in the function is small, there is a higher
3233 chance that there were truncation errors in the integer scaling
3234 of counts by inlining and other optimizations. This could lead
3235 to incorrect classification of code as being cold when it isn't.
3236 In that case, force the estimation of bb counts/frequencies from the
3237 branch probabilities, rather than computing frequencies from counts,
3238 which may also lead to frequencies incorrectly reduced to 0. There
3239 is less precision in the probabilities, so we only do this for small
3241 gcov_type count_max
= 0;
3243 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3244 count_max
= MAX (bb
->count
, count_max
);
3246 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3247 || (profile_status_for_fn (cfun
) == PROFILE_READ
&& count_max
< REG_BR_PROB_BASE
/10))
3249 loop_optimizer_init (0);
3250 add_noreturn_fake_exit_edges ();
3251 mark_irreducible_loops ();
3252 connect_infinite_loops_to_exit ();
3253 estimate_bb_frequencies (true);
3254 remove_fake_exit_edges ();
3255 loop_optimizer_finalize ();
3257 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3261 timevar_pop (TV_REBUILD_FREQUENCIES
);