1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 [1] "Branch Prediction for Free"
24 Ball and Larus; PLDI '93.
25 [2] "Static Branch Frequency and Program Profile Analysis"
26 Wu and Larus; MICRO-27.
27 [3] "Corpus-based Static Branch Prediction"
28 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
33 #include "coretypes.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
46 #include "diagnostic-core.h"
55 #include "tree-flow.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
60 #include "tree-scalar-evolution.h"
62 #include "pointer-set.h"
64 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
65 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
66 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
67 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
69 /* Random guesstimation given names.
70 PROV_VERY_UNLIKELY should be small enough so basic block predicted
71 by it gets bellow HOT_BB_FREQUENCY_FRANCTION. */
72 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
73 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
74 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
75 #define PROB_ALWAYS (REG_BR_PROB_BASE)
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 (int freq
)
116 struct cgraph_node
*node
= cgraph_node (current_function_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
== PROFILE_ABSENT
)
126 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
127 && freq
<= (ENTRY_BLOCK_PTR
->frequency
* 2 / 3))
129 if (freq
< ENTRY_BLOCK_PTR
->frequency
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
134 /* Return TRUE if frequency COUNT is considered to be hot. */
137 maybe_hot_count_p (gcov_type count
)
141 /* Code executed at most once is not hot. */
142 if (profile_info
->runs
>= count
)
145 > profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
));
148 /* Return true in case BB can be CPU intensive and should be optimized
149 for maximal performance. */
152 maybe_hot_bb_p (const_basic_block bb
)
154 if (profile_status
== PROFILE_READ
)
155 return maybe_hot_count_p (bb
->count
);
156 return maybe_hot_frequency_p (bb
->frequency
);
159 /* Return true if the call can be hot. */
162 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
164 if (profile_info
&& flag_branch_probabilities
166 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
168 if (edge
->caller
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
169 || edge
->callee
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
171 if (edge
->caller
->frequency
> NODE_FREQUENCY_UNLIKELY_EXECUTED
172 && edge
->callee
->frequency
<= NODE_FREQUENCY_EXECUTED_ONCE
)
176 if (edge
->caller
->frequency
== NODE_FREQUENCY_HOT
)
178 if (edge
->caller
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
179 && edge
->frequency
< CGRAPH_FREQ_BASE
* 3 / 2)
181 if (flag_guess_branch_prob
182 && edge
->frequency
<= (CGRAPH_FREQ_BASE
183 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
188 /* Return true in case BB can be CPU intensive and should be optimized
189 for maximal performance. */
192 maybe_hot_edge_p (edge e
)
194 if (profile_status
== PROFILE_READ
)
195 return maybe_hot_count_p (e
->count
);
196 return maybe_hot_frequency_p (EDGE_FREQUENCY (e
));
199 /* Return true in case BB is probably never executed. */
201 probably_never_executed_bb_p (const_basic_block bb
)
203 if (profile_info
&& flag_branch_probabilities
)
204 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
205 if ((!profile_info
|| !flag_branch_probabilities
)
206 && cgraph_node (current_function_decl
)->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
211 /* Return true when current function should always be optimized for size. */
214 optimize_function_for_size_p (struct function
*fun
)
216 return (optimize_size
218 && (cgraph_node (fun
->decl
)->frequency
219 == NODE_FREQUENCY_UNLIKELY_EXECUTED
)));
222 /* Return true when current function should always be optimized for speed. */
225 optimize_function_for_speed_p (struct function
*fun
)
227 return !optimize_function_for_size_p (fun
);
230 /* Return TRUE when BB should be optimized for size. */
233 optimize_bb_for_size_p (const_basic_block bb
)
235 return optimize_function_for_size_p (cfun
) || !maybe_hot_bb_p (bb
);
238 /* Return TRUE when BB should be optimized for speed. */
241 optimize_bb_for_speed_p (const_basic_block bb
)
243 return !optimize_bb_for_size_p (bb
);
246 /* Return TRUE when BB should be optimized for size. */
249 optimize_edge_for_size_p (edge e
)
251 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
254 /* Return TRUE when BB should be optimized for speed. */
257 optimize_edge_for_speed_p (edge e
)
259 return !optimize_edge_for_size_p (e
);
262 /* Return TRUE when BB should be optimized for size. */
265 optimize_insn_for_size_p (void)
267 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
270 /* Return TRUE when BB should be optimized for speed. */
273 optimize_insn_for_speed_p (void)
275 return !optimize_insn_for_size_p ();
278 /* Return TRUE when LOOP should be optimized for size. */
281 optimize_loop_for_size_p (struct loop
*loop
)
283 return optimize_bb_for_size_p (loop
->header
);
286 /* Return TRUE when LOOP should be optimized for speed. */
289 optimize_loop_for_speed_p (struct loop
*loop
)
291 return optimize_bb_for_speed_p (loop
->header
);
294 /* Return TRUE when LOOP nest should be optimized for speed. */
297 optimize_loop_nest_for_speed_p (struct loop
*loop
)
299 struct loop
*l
= loop
;
300 if (optimize_loop_for_speed_p (loop
))
303 while (l
&& l
!= loop
)
305 if (optimize_loop_for_speed_p (l
))
313 while (l
!= loop
&& !l
->next
)
322 /* Return TRUE when LOOP nest should be optimized for size. */
325 optimize_loop_nest_for_size_p (struct loop
*loop
)
327 return !optimize_loop_nest_for_speed_p (loop
);
330 /* Return true when edge E is likely to be well predictable by branch
334 predictable_edge_p (edge e
)
336 if (profile_status
== PROFILE_ABSENT
)
339 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
340 || (REG_BR_PROB_BASE
- e
->probability
341 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
347 /* Set RTL expansion for BB profile. */
350 rtl_profile_for_bb (basic_block bb
)
352 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (bb
);
355 /* Set RTL expansion for edge profile. */
358 rtl_profile_for_edge (edge e
)
360 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
363 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
365 default_rtl_profile (void)
367 crtl
->maybe_hot_insn_p
= true;
370 /* Return true if the one of outgoing edges is already predicted by
374 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
377 if (!INSN_P (BB_END (bb
)))
379 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
380 if (REG_NOTE_KIND (note
) == REG_BR_PRED
381 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
386 /* This map contains for a basic block the list of predictions for the
389 static struct pointer_map_t
*bb_predictions
;
391 /* Structure representing predictions in tree level. */
393 struct edge_prediction
{
394 struct edge_prediction
*ep_next
;
396 enum br_predictor ep_predictor
;
400 /* Return true if the one of outgoing edges is already predicted by
404 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
406 struct edge_prediction
*i
;
407 void **preds
= pointer_map_contains (bb_predictions
, bb
);
412 for (i
= (struct edge_prediction
*) *preds
; i
; i
= i
->ep_next
)
413 if (i
->ep_predictor
== predictor
)
418 /* Return true when the probability of edge is reliable.
420 The profile guessing code is good at predicting branch outcome (ie.
421 taken/not taken), that is predicted right slightly over 75% of time.
422 It is however notoriously poor on predicting the probability itself.
423 In general the profile appear a lot flatter (with probabilities closer
424 to 50%) than the reality so it is bad idea to use it to drive optimization
425 such as those disabling dynamic branch prediction for well predictable
428 There are two exceptions - edges leading to noreturn edges and edges
429 predicted by number of iterations heuristics are predicted well. This macro
430 should be able to distinguish those, but at the moment it simply check for
431 noreturn heuristic that is only one giving probability over 99% or bellow
432 1%. In future we might want to propagate reliability information across the
433 CFG if we find this information useful on multiple places. */
435 probability_reliable_p (int prob
)
437 return (profile_status
== PROFILE_READ
438 || (profile_status
== PROFILE_GUESSED
439 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
442 /* Same predicate as above, working on edges. */
444 edge_probability_reliable_p (const_edge e
)
446 return probability_reliable_p (e
->probability
);
449 /* Same predicate as edge_probability_reliable_p, working on notes. */
451 br_prob_note_reliable_p (const_rtx note
)
453 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
454 return probability_reliable_p (INTVAL (XEXP (note
, 0)));
458 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
460 gcc_assert (any_condjump_p (insn
));
461 if (!flag_guess_branch_prob
)
464 add_reg_note (insn
, REG_BR_PRED
,
465 gen_rtx_CONCAT (VOIDmode
,
466 GEN_INT ((int) predictor
),
467 GEN_INT ((int) probability
)));
470 /* Predict insn by given predictor. */
473 predict_insn_def (rtx insn
, enum br_predictor predictor
,
474 enum prediction taken
)
476 int probability
= predictor_info
[(int) predictor
].hitrate
;
479 probability
= REG_BR_PROB_BASE
- probability
;
481 predict_insn (insn
, predictor
, probability
);
484 /* Predict edge E with given probability if possible. */
487 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
490 last_insn
= BB_END (e
->src
);
492 /* We can store the branch prediction information only about
493 conditional jumps. */
494 if (!any_condjump_p (last_insn
))
497 /* We always store probability of branching. */
498 if (e
->flags
& EDGE_FALLTHRU
)
499 probability
= REG_BR_PROB_BASE
- probability
;
501 predict_insn (last_insn
, predictor
, probability
);
504 /* Predict edge E with the given PROBABILITY. */
506 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
508 gcc_assert (profile_status
!= PROFILE_GUESSED
);
509 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
510 && flag_guess_branch_prob
&& optimize
)
512 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
513 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
515 i
->ep_next
= (struct edge_prediction
*) *preds
;
517 i
->ep_probability
= probability
;
518 i
->ep_predictor
= predictor
;
523 /* Remove all predictions on given basic block that are attached
526 remove_predictions_associated_with_edge (edge e
)
533 preds
= pointer_map_contains (bb_predictions
, e
->src
);
537 struct edge_prediction
**prediction
= (struct edge_prediction
**) preds
;
538 struct edge_prediction
*next
;
542 if ((*prediction
)->ep_edge
== e
)
544 next
= (*prediction
)->ep_next
;
549 prediction
= &((*prediction
)->ep_next
);
554 /* Clears the list of predictions stored for BB. */
557 clear_bb_predictions (basic_block bb
)
559 void **preds
= pointer_map_contains (bb_predictions
, bb
);
560 struct edge_prediction
*pred
, *next
;
565 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= next
)
567 next
= pred
->ep_next
;
573 /* Return true when we can store prediction on insn INSN.
574 At the moment we represent predictions only on conditional
575 jumps, not at computed jump or other complicated cases. */
577 can_predict_insn_p (const_rtx insn
)
579 return (JUMP_P (insn
)
580 && any_condjump_p (insn
)
581 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
584 /* Predict edge E by given predictor if possible. */
587 predict_edge_def (edge e
, enum br_predictor predictor
,
588 enum prediction taken
)
590 int probability
= predictor_info
[(int) predictor
].hitrate
;
593 probability
= REG_BR_PROB_BASE
- probability
;
595 predict_edge (e
, predictor
, probability
);
598 /* Invert all branch predictions or probability notes in the INSN. This needs
599 to be done each time we invert the condition used by the jump. */
602 invert_br_probabilities (rtx insn
)
606 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
607 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
608 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
609 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
610 XEXP (XEXP (note
, 0), 1)
611 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
614 /* Dump information about the branch prediction to the output file. */
617 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
618 basic_block bb
, int used
)
626 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
627 if (! (e
->flags
& EDGE_FALLTHRU
))
630 fprintf (file
, " %s heuristics%s: %.1f%%",
631 predictor_info
[predictor
].name
,
632 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
636 fprintf (file
, " exec ");
637 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
640 fprintf (file
, " hit ");
641 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
642 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
646 fprintf (file
, "\n");
649 /* We can not predict the probabilities of outgoing edges of bb. Set them
650 evenly and hope for the best. */
652 set_even_probabilities (basic_block bb
)
658 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
659 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
661 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
662 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
663 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
668 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
669 note if not already present. Remove now useless REG_BR_PRED notes. */
672 combine_predictions_for_insn (rtx insn
, basic_block bb
)
677 int best_probability
= PROB_EVEN
;
678 enum br_predictor best_predictor
= END_PREDICTORS
;
679 int combined_probability
= REG_BR_PROB_BASE
/ 2;
681 bool first_match
= false;
684 if (!can_predict_insn_p (insn
))
686 set_even_probabilities (bb
);
690 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
691 pnote
= ®_NOTES (insn
);
693 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
696 /* We implement "first match" heuristics and use probability guessed
697 by predictor with smallest index. */
698 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
699 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
701 enum br_predictor predictor
= ((enum br_predictor
)
702 INTVAL (XEXP (XEXP (note
, 0), 0)));
703 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
706 if (best_predictor
> predictor
)
707 best_probability
= probability
, best_predictor
= predictor
;
709 d
= (combined_probability
* probability
710 + (REG_BR_PROB_BASE
- combined_probability
)
711 * (REG_BR_PROB_BASE
- probability
));
713 /* Use FP math to avoid overflows of 32bit integers. */
715 /* If one probability is 0% and one 100%, avoid division by zero. */
716 combined_probability
= REG_BR_PROB_BASE
/ 2;
718 combined_probability
= (((double) combined_probability
) * probability
719 * REG_BR_PROB_BASE
/ d
+ 0.5);
722 /* Decide which heuristic to use. In case we didn't match anything,
723 use no_prediction heuristic, in case we did match, use either
724 first match or Dempster-Shaffer theory depending on the flags. */
726 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
730 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
731 combined_probability
, bb
, true);
734 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
736 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
741 combined_probability
= best_probability
;
742 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
746 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
748 enum br_predictor predictor
= ((enum br_predictor
)
749 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
750 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
752 dump_prediction (dump_file
, predictor
, probability
, bb
,
753 !first_match
|| best_predictor
== predictor
);
754 *pnote
= XEXP (*pnote
, 1);
757 pnote
= &XEXP (*pnote
, 1);
762 add_reg_note (insn
, REG_BR_PROB
, GEN_INT (combined_probability
));
764 /* Save the prediction into CFG in case we are seeing non-degenerated
766 if (!single_succ_p (bb
))
768 BRANCH_EDGE (bb
)->probability
= combined_probability
;
769 FALLTHRU_EDGE (bb
)->probability
770 = REG_BR_PROB_BASE
- combined_probability
;
773 else if (!single_succ_p (bb
))
775 int prob
= INTVAL (XEXP (prob_note
, 0));
777 BRANCH_EDGE (bb
)->probability
= prob
;
778 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
781 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
784 /* Combine predictions into single probability and store them into CFG.
785 Remove now useless prediction entries. */
788 combine_predictions_for_bb (basic_block bb
)
790 int best_probability
= PROB_EVEN
;
791 enum br_predictor best_predictor
= END_PREDICTORS
;
792 int combined_probability
= REG_BR_PROB_BASE
/ 2;
794 bool first_match
= false;
796 struct edge_prediction
*pred
;
798 edge e
, first
= NULL
, second
= NULL
;
802 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
803 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
806 if (first
&& !second
)
812 /* When there is no successor or only one choice, prediction is easy.
814 We are lazy for now and predict only basic blocks with two outgoing
815 edges. It is possible to predict generic case too, but we have to
816 ignore first match heuristics and do more involved combining. Implement
821 set_even_probabilities (bb
);
822 clear_bb_predictions (bb
);
824 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
830 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
832 preds
= pointer_map_contains (bb_predictions
, bb
);
835 /* We implement "first match" heuristics and use probability guessed
836 by predictor with smallest index. */
837 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
839 enum br_predictor predictor
= pred
->ep_predictor
;
840 int probability
= pred
->ep_probability
;
842 if (pred
->ep_edge
!= first
)
843 probability
= REG_BR_PROB_BASE
- probability
;
846 /* First match heuristics would be widly confused if we predicted
848 if (best_predictor
> predictor
)
850 struct edge_prediction
*pred2
;
851 int prob
= probability
;
853 for (pred2
= (struct edge_prediction
*) *preds
; pred2
; pred2
= pred2
->ep_next
)
854 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
856 int probability2
= pred
->ep_probability
;
858 if (pred2
->ep_edge
!= first
)
859 probability2
= REG_BR_PROB_BASE
- probability2
;
861 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
862 (probability2
< REG_BR_PROB_BASE
/ 2))
865 /* If the same predictor later gave better result, go for it! */
866 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
867 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
871 best_probability
= prob
, best_predictor
= predictor
;
874 d
= (combined_probability
* probability
875 + (REG_BR_PROB_BASE
- combined_probability
)
876 * (REG_BR_PROB_BASE
- probability
));
878 /* Use FP math to avoid overflows of 32bit integers. */
880 /* If one probability is 0% and one 100%, avoid division by zero. */
881 combined_probability
= REG_BR_PROB_BASE
/ 2;
883 combined_probability
= (((double) combined_probability
)
885 * REG_BR_PROB_BASE
/ d
+ 0.5);
889 /* Decide which heuristic to use. In case we didn't match anything,
890 use no_prediction heuristic, in case we did match, use either
891 first match or Dempster-Shaffer theory depending on the flags. */
893 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
897 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
900 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
902 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
907 combined_probability
= best_probability
;
908 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
912 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
914 enum br_predictor predictor
= pred
->ep_predictor
;
915 int probability
= pred
->ep_probability
;
917 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
918 probability
= REG_BR_PROB_BASE
- probability
;
919 dump_prediction (dump_file
, predictor
, probability
, bb
,
920 !first_match
|| best_predictor
== predictor
);
923 clear_bb_predictions (bb
);
927 first
->probability
= combined_probability
;
928 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
932 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
933 Return the SSA_NAME if the condition satisfies, NULL otherwise.
935 T1 and T2 should be one of the following cases:
936 1. T1 is SSA_NAME, T2 is NULL
937 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
938 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
941 strips_small_constant (tree t1
, tree t2
)
948 else if (TREE_CODE (t1
) == SSA_NAME
)
950 else if (TREE_CODE (t1
) == INTEGER_CST
&& host_integerp (t1
, 0))
951 value
= tree_low_cst (t1
, 0);
957 else if (TREE_CODE (t2
) == INTEGER_CST
&& host_integerp (t2
, 0))
958 value
= tree_low_cst (t2
, 0);
959 else if (TREE_CODE (t2
) == SSA_NAME
)
967 if (value
<= 4 && value
>= -4)
973 /* Return the SSA_NAME in T or T's operands.
974 Return NULL if SSA_NAME cannot be found. */
977 get_base_value (tree t
)
979 if (TREE_CODE (t
) == SSA_NAME
)
982 if (!BINARY_CLASS_P (t
))
985 switch (TREE_OPERAND_LENGTH (t
))
988 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
990 return strips_small_constant (TREE_OPERAND (t
, 0),
991 TREE_OPERAND (t
, 1));
997 /* Check the compare STMT in LOOP. If it compares an induction
998 variable to a loop invariant, return true, and save
999 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1000 Otherwise return false and set LOOP_INVAIANT to NULL. */
1003 is_comparison_with_loop_invariant_p (gimple stmt
, struct loop
*loop
,
1004 tree
*loop_invariant
,
1005 enum tree_code
*compare_code
,
1009 tree op0
, op1
, bound
, base
;
1011 enum tree_code code
;
1014 code
= gimple_cond_code (stmt
);
1015 *loop_invariant
= NULL
;
1031 op0
= gimple_cond_lhs (stmt
);
1032 op1
= gimple_cond_rhs (stmt
);
1034 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1035 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1037 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1039 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1041 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1042 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1044 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1045 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1048 if (integer_zerop (iv0
.step
))
1050 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1051 code
= invert_tree_comparison (code
, false);
1054 if (host_integerp (iv1
.step
, 0))
1055 step
= tree_low_cst (iv1
.step
, 0);
1063 if (host_integerp (iv0
.step
, 0))
1064 step
= tree_low_cst (iv0
.step
, 0);
1069 if (TREE_CODE (bound
) != INTEGER_CST
)
1070 bound
= get_base_value (bound
);
1073 if (TREE_CODE (base
) != INTEGER_CST
)
1074 base
= get_base_value (base
);
1078 *loop_invariant
= bound
;
1079 *compare_code
= code
;
1081 *loop_iv_base
= base
;
1085 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1088 expr_coherent_p (tree t1
, tree t2
)
1091 tree ssa_name_1
= NULL
;
1092 tree ssa_name_2
= NULL
;
1094 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1095 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1100 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1102 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1105 /* Check to see if t1 is expressed/defined with t2. */
1106 stmt
= SSA_NAME_DEF_STMT (t1
);
1107 gcc_assert (stmt
!= NULL
);
1108 if (is_gimple_assign (stmt
))
1110 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1111 if (ssa_name_1
&& ssa_name_1
== t2
)
1115 /* Check to see if t2 is expressed/defined with t1. */
1116 stmt
= SSA_NAME_DEF_STMT (t2
);
1117 gcc_assert (stmt
!= NULL
);
1118 if (is_gimple_assign (stmt
))
1120 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1121 if (ssa_name_2
&& ssa_name_2
== t1
)
1125 /* Compare if t1 and t2's def_stmts are identical. */
1126 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1132 /* Predict branch probability of BB when BB contains a branch that compares
1133 an induction variable with LOOP_IV_BASE_VAR in LOOP to LOOP_BOUND_VAR. The
1134 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1137 for (int i = 0; i < bound; i++) {
1144 In this loop, we will predict the branch inside the loop to be taken. */
1147 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1148 tree loop_bound_var
,
1149 tree loop_iv_base_var
,
1150 enum tree_code loop_bound_code
,
1151 int loop_bound_step
)
1154 tree compare_var
, compare_base
;
1155 enum tree_code compare_code
;
1160 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1161 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1162 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1165 stmt
= last_stmt (bb
);
1166 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1168 if (!is_comparison_with_loop_invariant_p (stmt
, loop
, &compare_var
,
1174 /* Find the taken edge. */
1175 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1176 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1179 /* When comparing an IV to a loop invariant, NE is more likely to be
1180 taken while EQ is more likely to be not-taken. */
1181 if (compare_code
== NE_EXPR
)
1183 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, TAKEN
);
1186 else if (compare_code
== EQ_EXPR
)
1188 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, NOT_TAKEN
);
1192 if (!expr_coherent_p(loop_iv_base_var
, compare_base
))
1195 /* If loop bound, base and compare bound are all constents, we can
1196 calculate the probability directly. */
1197 if (TREE_CODE (loop_bound_var
) == INTEGER_CST
1198 && TREE_CODE (compare_var
) == INTEGER_CST
1199 && TREE_CODE (compare_base
) == INTEGER_CST
1200 && host_integerp (loop_bound_var
, 0)
1201 && host_integerp (compare_var
, 0)
1202 && host_integerp (compare_base
, 0))
1205 HOST_WIDE_INT compare_count
;
1206 HOST_WIDE_INT loop_bound
= tree_low_cst (loop_bound_var
, 0);
1207 HOST_WIDE_INT compare_bound
= tree_low_cst (compare_var
, 0);
1208 HOST_WIDE_INT base
= tree_low_cst (compare_base
, 0);
1209 HOST_WIDE_INT loop_count
= (loop_bound
- base
) / compare_step
;
1211 if ((compare_step
> 0)
1212 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1213 compare_count
= (loop_bound
- compare_bound
) / compare_step
;
1215 compare_count
= (compare_bound
- base
) / compare_step
;
1217 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1219 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1221 if (compare_count
< 0)
1226 if (loop_count
== 0)
1228 else if (compare_count
> loop_count
)
1229 probability
= REG_BR_PROB_BASE
;
1231 probability
= (double) REG_BR_PROB_BASE
* compare_count
/ loop_count
;
1232 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1236 if (expr_coherent_p (loop_bound_var
, compare_var
))
1238 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1239 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1240 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, TAKEN
);
1241 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1242 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1243 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, TAKEN
);
1244 else if (loop_bound_code
== NE_EXPR
)
1246 /* If the loop backedge condition is "(i != bound)", we do
1247 the comparison based on the step of IV:
1248 * step < 0 : backedge condition is like (i > bound)
1249 * step > 0 : backedge condition is like (i < bound) */
1250 gcc_assert (loop_bound_step
!= 0);
1251 if (loop_bound_step
> 0
1252 && (compare_code
== LT_EXPR
1253 || compare_code
== LE_EXPR
))
1254 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, TAKEN
);
1255 else if (loop_bound_step
< 0
1256 && (compare_code
== GT_EXPR
1257 || compare_code
== GE_EXPR
))
1258 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, TAKEN
);
1260 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, NOT_TAKEN
);
1263 /* The branch is predicted not-taken if loop_bound_code is
1264 opposite with compare_code. */
1265 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, NOT_TAKEN
);
1267 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1270 for (i = s; i < h; i++)
1272 The branch should be predicted taken. */
1273 if (loop_bound_step
> 0
1274 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1275 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, TAKEN
);
1276 else if (loop_bound_step
< 0
1277 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1278 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, TAKEN
);
1280 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE
, NOT_TAKEN
);
1284 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1285 exits are resulted from short-circuit conditions that will generate an
1288 if (foo() || global > 10)
1291 This will be translated into:
1296 if foo() goto BB6 else goto BB5
1298 if global > 10 goto BB6 else goto BB7
1302 iftmp = (PHI 0(BB5), 1(BB6))
1303 if iftmp == 1 goto BB8 else goto BB3
1305 outside of the loop...
1307 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1308 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1309 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1310 exits to predict them using PRED_LOOP_EXIT. */
1313 predict_extra_loop_exits (edge exit_edge
)
1316 bool check_value_one
;
1318 tree cmp_rhs
, cmp_lhs
;
1319 gimple cmp_stmt
= last_stmt (exit_edge
->src
);
1321 if (!cmp_stmt
|| gimple_code (cmp_stmt
) != GIMPLE_COND
)
1323 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1324 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1325 if (!TREE_CONSTANT (cmp_rhs
)
1326 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1328 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1331 /* If check_value_one is true, only the phi_args with value '1' will lead
1332 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1334 check_value_one
= (((integer_onep (cmp_rhs
))
1335 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1336 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1338 phi_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1339 if (!phi_stmt
|| gimple_code (phi_stmt
) != GIMPLE_PHI
)
1342 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1346 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1347 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1349 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1351 if (check_value_one
^ integer_onep (val
))
1353 if (VEC_length (edge
, e
->src
->succs
) != 1)
1355 if (!predicted_by_p (exit_edge
->src
, PRED_LOOP_ITERATIONS_GUESSED
)
1356 && !predicted_by_p (exit_edge
->src
, PRED_LOOP_ITERATIONS
)
1357 && !predicted_by_p (exit_edge
->src
, PRED_LOOP_EXIT
))
1358 predict_edge_def (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1362 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1363 if (!predicted_by_p (exit_edge
->src
, PRED_LOOP_ITERATIONS_GUESSED
)
1364 && !predicted_by_p (exit_edge
->src
, PRED_LOOP_ITERATIONS
)
1365 && !predicted_by_p (exit_edge
->src
, PRED_LOOP_EXIT
))
1366 predict_edge_def (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1370 /* Predict edge probabilities by exploiting loop structure. */
1373 predict_loops (void)
1378 /* Try to predict out blocks in a loop that are not part of a
1380 FOR_EACH_LOOP (li
, loop
, 0)
1382 basic_block bb
, *bbs
;
1383 unsigned j
, n_exits
;
1384 VEC (edge
, heap
) *exits
;
1385 struct tree_niter_desc niter_desc
;
1387 struct nb_iter_bound
*nb_iter
;
1388 enum tree_code loop_bound_code
= ERROR_MARK
;
1389 int loop_bound_step
= 0;
1390 tree loop_bound_var
= NULL
;
1391 tree loop_iv_base
= NULL
;
1394 exits
= get_loop_exit_edges (loop
);
1395 n_exits
= VEC_length (edge
, exits
);
1397 FOR_EACH_VEC_ELT (edge
, exits
, j
, ex
)
1400 HOST_WIDE_INT nitercst
;
1401 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1403 enum br_predictor predictor
;
1405 predict_extra_loop_exits (ex
);
1407 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
1408 niter
= niter_desc
.niter
;
1409 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1410 niter
= loop_niter_by_eval (loop
, ex
);
1412 if (TREE_CODE (niter
) == INTEGER_CST
)
1414 if (host_integerp (niter
, 1)
1415 && compare_tree_int (niter
, max
-1) == -1)
1416 nitercst
= tree_low_cst (niter
, 1) + 1;
1419 predictor
= PRED_LOOP_ITERATIONS
;
1421 /* If we have just one exit and we can derive some information about
1422 the number of iterations of the loop from the statements inside
1423 the loop, use it to predict this exit. */
1424 else if (n_exits
== 1)
1426 nitercst
= estimated_loop_iterations_int (loop
, false);
1432 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1437 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1438 predict_edge (ex
, predictor
, probability
);
1440 VEC_free (edge
, heap
, exits
);
1442 /* Find information about loop bound variables. */
1443 for (nb_iter
= loop
->bounds
; nb_iter
;
1444 nb_iter
= nb_iter
->next
)
1446 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1448 stmt
= nb_iter
->stmt
;
1451 if (!stmt
&& last_stmt (loop
->header
)
1452 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1453 stmt
= last_stmt (loop
->header
);
1455 is_comparison_with_loop_invariant_p (stmt
, loop
,
1461 bbs
= get_loop_body (loop
);
1463 for (j
= 0; j
< loop
->num_nodes
; j
++)
1465 int header_found
= 0;
1471 /* Bypass loop heuristics on continue statement. These
1472 statements construct loops via "non-loop" constructs
1473 in the source language and are better to be handled
1475 if (predicted_by_p (bb
, PRED_CONTINUE
))
1478 /* Loop branch heuristics - predict an edge back to a
1479 loop's head as taken. */
1480 if (bb
== loop
->latch
)
1482 e
= find_edge (loop
->latch
, loop
->header
);
1486 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1490 /* Loop exit heuristics - predict an edge exiting the loop if the
1491 conditional has no loop header successors as not taken. */
1493 /* If we already used more reliable loop exit predictors, do not
1494 bother with PRED_LOOP_EXIT. */
1495 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1496 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1498 /* For loop with many exits we don't want to predict all exits
1499 with the pretty large probability, because if all exits are
1500 considered in row, the loop would be predicted to iterate
1501 almost never. The code to divide probability by number of
1502 exits is very rough. It should compute the number of exits
1503 taken in each patch through function (not the overall number
1504 of exits that might be a lot higher for loops with wide switch
1505 statements in them) and compute n-th square root.
1507 We limit the minimal probability by 2% to avoid
1508 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1509 as this was causing regression in perl benchmark containing such
1512 int probability
= ((REG_BR_PROB_BASE
1513 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1515 if (probability
< HITRATE (2))
1516 probability
= HITRATE (2);
1517 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1518 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1519 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1520 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1523 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1528 /* Free basic blocks from get_loop_body. */
1533 /* Attempt to predict probabilities of BB outgoing edges using local
1536 bb_estimate_probability_locally (basic_block bb
)
1538 rtx last_insn
= BB_END (bb
);
1541 if (! can_predict_insn_p (last_insn
))
1543 cond
= get_condition (last_insn
, NULL
, false, false);
1547 /* Try "pointer heuristic."
1548 A comparison ptr == 0 is predicted as false.
1549 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1550 if (COMPARISON_P (cond
)
1551 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1552 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1554 if (GET_CODE (cond
) == EQ
)
1555 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1556 else if (GET_CODE (cond
) == NE
)
1557 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1561 /* Try "opcode heuristic."
1562 EQ tests are usually false and NE tests are usually true. Also,
1563 most quantities are positive, so we can make the appropriate guesses
1564 about signed comparisons against zero. */
1565 switch (GET_CODE (cond
))
1568 /* Unconditional branch. */
1569 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1570 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1575 /* Floating point comparisons appears to behave in a very
1576 unpredictable way because of special role of = tests in
1578 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1580 /* Comparisons with 0 are often used for booleans and there is
1581 nothing useful to predict about them. */
1582 else if (XEXP (cond
, 1) == const0_rtx
1583 || XEXP (cond
, 0) == const0_rtx
)
1586 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1591 /* Floating point comparisons appears to behave in a very
1592 unpredictable way because of special role of = tests in
1594 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1596 /* Comparisons with 0 are often used for booleans and there is
1597 nothing useful to predict about them. */
1598 else if (XEXP (cond
, 1) == const0_rtx
1599 || XEXP (cond
, 0) == const0_rtx
)
1602 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1606 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1610 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1615 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1616 || XEXP (cond
, 1) == constm1_rtx
)
1617 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1622 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1623 || XEXP (cond
, 1) == constm1_rtx
)
1624 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1632 /* Set edge->probability for each successor edge of BB. */
1634 guess_outgoing_edge_probabilities (basic_block bb
)
1636 bb_estimate_probability_locally (bb
);
1637 combine_predictions_for_insn (BB_END (bb
), bb
);
1640 static tree
expr_expected_value (tree
, bitmap
);
1642 /* Helper function for expr_expected_value. */
1645 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
, tree op1
, bitmap visited
)
1649 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1651 if (TREE_CONSTANT (op0
))
1654 if (code
!= SSA_NAME
)
1657 def
= SSA_NAME_DEF_STMT (op0
);
1659 /* If we were already here, break the infinite cycle. */
1660 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1663 if (gimple_code (def
) == GIMPLE_PHI
)
1665 /* All the arguments of the PHI node must have the same constant
1667 int i
, n
= gimple_phi_num_args (def
);
1668 tree val
= NULL
, new_val
;
1670 for (i
= 0; i
< n
; i
++)
1672 tree arg
= PHI_ARG_DEF (def
, i
);
1674 /* If this PHI has itself as an argument, we cannot
1675 determine the string length of this argument. However,
1676 if we can find an expected constant value for the other
1677 PHI args then we can still be sure that this is
1678 likely a constant. So be optimistic and just
1679 continue with the next argument. */
1680 if (arg
== PHI_RESULT (def
))
1683 new_val
= expr_expected_value (arg
, visited
);
1688 else if (!operand_equal_p (val
, new_val
, false))
1693 if (is_gimple_assign (def
))
1695 if (gimple_assign_lhs (def
) != op0
)
1698 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1699 gimple_assign_rhs1 (def
),
1700 gimple_assign_rhs_code (def
),
1701 gimple_assign_rhs2 (def
),
1705 if (is_gimple_call (def
))
1707 tree decl
= gimple_call_fndecl (def
);
1710 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
1711 && DECL_FUNCTION_CODE (decl
) == BUILT_IN_EXPECT
)
1715 if (gimple_call_num_args (def
) != 2)
1717 val
= gimple_call_arg (def
, 0);
1718 if (TREE_CONSTANT (val
))
1720 return gimple_call_arg (def
, 1);
1727 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1730 op0
= expr_expected_value (op0
, visited
);
1733 op1
= expr_expected_value (op1
, visited
);
1736 res
= fold_build2 (code
, type
, op0
, op1
);
1737 if (TREE_CONSTANT (res
))
1741 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1744 op0
= expr_expected_value (op0
, visited
);
1747 res
= fold_build1 (code
, type
, op0
);
1748 if (TREE_CONSTANT (res
))
1755 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1756 The function is used by builtin_expect branch predictor so the evidence
1757 must come from this construct and additional possible constant folding.
1759 We may want to implement more involved value guess (such as value range
1760 propagation based prediction), but such tricks shall go to new
1764 expr_expected_value (tree expr
, bitmap visited
)
1766 enum tree_code code
;
1769 if (TREE_CONSTANT (expr
))
1772 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1773 return expr_expected_value_1 (TREE_TYPE (expr
),
1774 op0
, code
, op1
, visited
);
1778 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1779 we no longer need. */
1781 strip_predict_hints (void)
1789 gimple_stmt_iterator bi
;
1790 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
1792 gimple stmt
= gsi_stmt (bi
);
1794 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
1796 gsi_remove (&bi
, true);
1799 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1801 tree fndecl
= gimple_call_fndecl (stmt
);
1804 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1805 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1806 && gimple_call_num_args (stmt
) == 2)
1808 var
= gimple_call_lhs (stmt
);
1812 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
1813 gsi_replace (&bi
, ass_stmt
, true);
1817 gsi_remove (&bi
, true);
1828 /* Predict using opcode of the last statement in basic block. */
1830 tree_predict_by_opcode (basic_block bb
)
1832 gimple stmt
= last_stmt (bb
);
1841 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1843 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1844 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1846 op0
= gimple_cond_lhs (stmt
);
1847 op1
= gimple_cond_rhs (stmt
);
1848 cmp
= gimple_cond_code (stmt
);
1849 type
= TREE_TYPE (op0
);
1850 visited
= BITMAP_ALLOC (NULL
);
1851 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
);
1852 BITMAP_FREE (visited
);
1855 if (integer_zerop (val
))
1856 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1858 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1861 /* Try "pointer heuristic."
1862 A comparison ptr == 0 is predicted as false.
1863 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1864 if (POINTER_TYPE_P (type
))
1867 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1868 else if (cmp
== NE_EXPR
)
1869 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1873 /* Try "opcode heuristic."
1874 EQ tests are usually false and NE tests are usually true. Also,
1875 most quantities are positive, so we can make the appropriate guesses
1876 about signed comparisons against zero. */
1881 /* Floating point comparisons appears to behave in a very
1882 unpredictable way because of special role of = tests in
1884 if (FLOAT_TYPE_P (type
))
1886 /* Comparisons with 0 are often used for booleans and there is
1887 nothing useful to predict about them. */
1888 else if (integer_zerop (op0
) || integer_zerop (op1
))
1891 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1896 /* Floating point comparisons appears to behave in a very
1897 unpredictable way because of special role of = tests in
1899 if (FLOAT_TYPE_P (type
))
1901 /* Comparisons with 0 are often used for booleans and there is
1902 nothing useful to predict about them. */
1903 else if (integer_zerop (op0
)
1904 || integer_zerop (op1
))
1907 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1911 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1914 case UNORDERED_EXPR
:
1915 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1920 if (integer_zerop (op1
)
1921 || integer_onep (op1
)
1922 || integer_all_onesp (op1
)
1925 || real_minus_onep (op1
))
1926 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1931 if (integer_zerop (op1
)
1932 || integer_onep (op1
)
1933 || integer_all_onesp (op1
)
1936 || real_minus_onep (op1
))
1937 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1945 /* Try to guess whether the value of return means error code. */
1947 static enum br_predictor
1948 return_prediction (tree val
, enum prediction
*prediction
)
1952 return PRED_NO_PREDICTION
;
1953 /* Different heuristics for pointers and scalars. */
1954 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1956 /* NULL is usually not returned. */
1957 if (integer_zerop (val
))
1959 *prediction
= NOT_TAKEN
;
1960 return PRED_NULL_RETURN
;
1963 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1965 /* Negative return values are often used to indicate
1967 if (TREE_CODE (val
) == INTEGER_CST
1968 && tree_int_cst_sgn (val
) < 0)
1970 *prediction
= NOT_TAKEN
;
1971 return PRED_NEGATIVE_RETURN
;
1973 /* Constant return values seems to be commonly taken.
1974 Zero/one often represent booleans so exclude them from the
1976 if (TREE_CONSTANT (val
)
1977 && (!integer_zerop (val
) && !integer_onep (val
)))
1979 *prediction
= TAKEN
;
1980 return PRED_CONST_RETURN
;
1983 return PRED_NO_PREDICTION
;
1986 /* Find the basic block with return expression and look up for possible
1987 return value trying to apply RETURN_PREDICTION heuristics. */
1989 apply_return_prediction (void)
1991 gimple return_stmt
= NULL
;
1995 int phi_num_args
, i
;
1996 enum br_predictor pred
;
1997 enum prediction direction
;
2000 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
2002 return_stmt
= last_stmt (e
->src
);
2004 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
2009 return_val
= gimple_return_retval (return_stmt
);
2012 if (TREE_CODE (return_val
) != SSA_NAME
2013 || !SSA_NAME_DEF_STMT (return_val
)
2014 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2016 phi
= SSA_NAME_DEF_STMT (return_val
);
2017 phi_num_args
= gimple_phi_num_args (phi
);
2018 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2020 /* Avoid the degenerate case where all return values form the function
2021 belongs to same category (ie they are all positive constants)
2022 so we can hardly say something about them. */
2023 for (i
= 1; i
< phi_num_args
; i
++)
2024 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2026 if (i
!= phi_num_args
)
2027 for (i
= 0; i
< phi_num_args
; i
++)
2029 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2030 if (pred
!= PRED_NO_PREDICTION
)
2031 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2036 /* Look for basic block that contains unlikely to happen events
2037 (such as noreturn calls) and mark all paths leading to execution
2038 of this basic blocks as unlikely. */
2041 tree_bb_level_predictions (void)
2044 bool has_return_edges
= false;
2048 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
2049 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2051 has_return_edges
= true;
2055 apply_return_prediction ();
2059 gimple_stmt_iterator gsi
;
2061 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2063 gimple stmt
= gsi_stmt (gsi
);
2066 if (is_gimple_call (stmt
))
2068 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2069 && has_return_edges
)
2070 predict_paths_leading_to (bb
, PRED_NORETURN
,
2072 decl
= gimple_call_fndecl (stmt
);
2074 && lookup_attribute ("cold",
2075 DECL_ATTRIBUTES (decl
)))
2076 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2079 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2081 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2082 gimple_predict_outcome (stmt
));
2083 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2084 hints to callers. */
2090 #ifdef ENABLE_CHECKING
2092 /* Callback for pointer_map_traverse, asserts that the pointer map is
2096 assert_is_empty (const void *key ATTRIBUTE_UNUSED
, void **value
,
2097 void *data ATTRIBUTE_UNUSED
)
2099 gcc_assert (!*value
);
2104 /* Predict branch probabilities and estimate profile for basic block BB. */
2107 tree_estimate_probability_bb (basic_block bb
)
2113 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2115 /* Predict early returns to be probable, as we've already taken
2116 care for error returns and other cases are often used for
2117 fast paths through function.
2119 Since we've already removed the return statements, we are
2120 looking for CFG like:
2130 if (e
->dest
!= bb
->next_bb
2131 && e
->dest
!= EXIT_BLOCK_PTR
2132 && single_succ_p (e
->dest
)
2133 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR
2134 && (last
= last_stmt (e
->dest
)) != NULL
2135 && gimple_code (last
) == GIMPLE_RETURN
)
2140 if (single_succ_p (bb
))
2142 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2143 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2144 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2145 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2146 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2149 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2150 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2151 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2152 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2155 /* Look for block we are guarding (ie we dominate it,
2156 but it doesn't postdominate us). */
2157 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
2158 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2159 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2161 gimple_stmt_iterator bi
;
2163 /* The call heuristic claims that a guarded function call
2164 is improbable. This is because such calls are often used
2165 to signal exceptional situations such as printing error
2167 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2170 gimple stmt
= gsi_stmt (bi
);
2171 if (is_gimple_call (stmt
)
2172 /* Constant and pure calls are hardly used to signalize
2173 something exceptional. */
2174 && gimple_has_side_effects (stmt
))
2176 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2182 tree_predict_by_opcode (bb
);
2185 /* Predict branch probabilities and estimate profile of the tree CFG.
2186 This function can be called from the loop optimizers to recompute
2187 the profile information. */
2190 tree_estimate_probability (void)
2194 add_noreturn_fake_exit_edges ();
2195 connect_infinite_loops_to_exit ();
2196 /* We use loop_niter_by_eval, which requires that the loops have
2198 create_preheaders (CP_SIMPLE_PREHEADERS
);
2199 calculate_dominance_info (CDI_POST_DOMINATORS
);
2201 bb_predictions
= pointer_map_create ();
2202 tree_bb_level_predictions ();
2203 record_loop_exits ();
2205 if (number_of_loops () > 1)
2209 tree_estimate_probability_bb (bb
);
2212 combine_predictions_for_bb (bb
);
2214 #ifdef ENABLE_CHECKING
2215 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
2217 pointer_map_destroy (bb_predictions
);
2218 bb_predictions
= NULL
;
2220 estimate_bb_frequencies ();
2221 free_dominance_info (CDI_POST_DOMINATORS
);
2222 remove_fake_exit_edges ();
2225 /* Predict branch probabilities and estimate profile of the tree CFG.
2226 This is the driver function for PASS_PROFILE. */
2229 tree_estimate_probability_driver (void)
2233 loop_optimizer_init (0);
2234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2235 flow_loops_dump (dump_file
, NULL
, 0);
2237 mark_irreducible_loops ();
2239 nb_loops
= number_of_loops ();
2243 tree_estimate_probability ();
2248 loop_optimizer_finalize ();
2249 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2250 gimple_dump_cfg (dump_file
, dump_flags
);
2251 if (profile_status
== PROFILE_ABSENT
)
2252 profile_status
= PROFILE_GUESSED
;
2256 /* Predict edges to successors of CUR whose sources are not postdominated by
2257 BB by PRED and recurse to all postdominators. */
2260 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2261 enum br_predictor pred
,
2262 enum prediction taken
,
2269 /* We are looking for all edges forming edge cut induced by
2270 set of all blocks postdominated by BB. */
2271 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2272 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2273 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2279 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2280 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2282 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2284 /* See if there is an edge from e->src that is not abnormal
2285 and does not lead to BB. */
2286 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2288 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2289 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2295 /* If there is non-abnormal path leaving e->src, predict edge
2296 using predictor. Otherwise we need to look for paths
2299 The second may lead to infinite loop in the case we are predicitng
2300 regions that are only reachable by abnormal edges. We simply
2301 prevent visiting given BB twice. */
2303 predict_edge_def (e
, pred
, taken
);
2304 else if (bitmap_set_bit (visited
, e
->src
->index
))
2305 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2307 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2309 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2310 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2313 /* Sets branch probabilities according to PREDiction and
2317 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2318 enum prediction taken
)
2320 bitmap visited
= BITMAP_ALLOC (NULL
);
2321 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2322 BITMAP_FREE (visited
);
2325 /* Like predict_paths_leading_to but take edge instead of basic block. */
2328 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2329 enum prediction taken
)
2331 bool has_nonloop_edge
= false;
2335 basic_block bb
= e
->src
;
2336 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2337 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2338 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2339 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2341 has_nonloop_edge
= true;
2344 if (!has_nonloop_edge
)
2346 bitmap visited
= BITMAP_ALLOC (NULL
);
2347 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2348 BITMAP_FREE (visited
);
2351 predict_edge_def (e
, pred
, taken
);
2354 /* This is used to carry information about basic blocks. It is
2355 attached to the AUX field of the standard CFG block. */
2357 typedef struct block_info_def
2359 /* Estimated frequency of execution of basic_block. */
2362 /* To keep queue of basic blocks to process. */
2365 /* Number of predecessors we need to visit first. */
2369 /* Similar information for edges. */
2370 typedef struct edge_info_def
2372 /* In case edge is a loopback edge, the probability edge will be reached
2373 in case header is. Estimated number of iterations of the loop can be
2374 then computed as 1 / (1 - back_edge_prob). */
2375 sreal back_edge_prob
;
2376 /* True if the edge is a loopback edge in the natural loop. */
2377 unsigned int back_edge
:1;
2380 #define BLOCK_INFO(B) ((block_info) (B)->aux)
2381 #define EDGE_INFO(E) ((edge_info) (E)->aux)
2383 /* Helper function for estimate_bb_frequencies.
2384 Propagate the frequencies in blocks marked in
2385 TOVISIT, starting in HEAD. */
2388 propagate_freq (basic_block head
, bitmap tovisit
)
2397 /* For each basic block we need to visit count number of his predecessors
2398 we need to visit first. */
2399 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2404 bb
= BASIC_BLOCK (i
);
2406 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2408 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2410 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2412 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2414 "Irreducible region hit, ignoring edge to %i->%i\n",
2415 e
->src
->index
, bb
->index
);
2417 BLOCK_INFO (bb
)->npredecessors
= count
;
2418 /* When function never returns, we will never process exit block. */
2419 if (!count
&& bb
== EXIT_BLOCK_PTR
)
2420 bb
->count
= bb
->frequency
= 0;
2423 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
2425 for (bb
= head
; bb
; bb
= nextbb
)
2428 sreal cyclic_probability
, frequency
;
2430 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
2431 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
2433 nextbb
= BLOCK_INFO (bb
)->next
;
2434 BLOCK_INFO (bb
)->next
= NULL
;
2436 /* Compute frequency of basic block. */
2439 #ifdef ENABLE_CHECKING
2440 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2441 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2442 || (e
->flags
& EDGE_DFS_BACK
));
2445 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2446 if (EDGE_INFO (e
)->back_edge
)
2448 sreal_add (&cyclic_probability
, &cyclic_probability
,
2449 &EDGE_INFO (e
)->back_edge_prob
);
2451 else if (!(e
->flags
& EDGE_DFS_BACK
))
2455 /* frequency += (e->probability
2456 * BLOCK_INFO (e->src)->frequency /
2457 REG_BR_PROB_BASE); */
2459 sreal_init (&tmp
, e
->probability
, 0);
2460 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
2461 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
2462 sreal_add (&frequency
, &frequency
, &tmp
);
2465 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
2467 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
2468 sizeof (frequency
));
2472 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
2474 memcpy (&cyclic_probability
, &real_almost_one
,
2475 sizeof (real_almost_one
));
2478 /* BLOCK_INFO (bb)->frequency = frequency
2479 / (1 - cyclic_probability) */
2481 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
2482 sreal_div (&BLOCK_INFO (bb
)->frequency
,
2483 &frequency
, &cyclic_probability
);
2487 bitmap_clear_bit (tovisit
, bb
->index
);
2489 e
= find_edge (bb
, head
);
2494 /* EDGE_INFO (e)->back_edge_prob
2495 = ((e->probability * BLOCK_INFO (bb)->frequency)
2496 / REG_BR_PROB_BASE); */
2498 sreal_init (&tmp
, e
->probability
, 0);
2499 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
2500 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2501 &tmp
, &real_inv_br_prob_base
);
2504 /* Propagate to successor blocks. */
2505 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2506 if (!(e
->flags
& EDGE_DFS_BACK
)
2507 && BLOCK_INFO (e
->dest
)->npredecessors
)
2509 BLOCK_INFO (e
->dest
)->npredecessors
--;
2510 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2515 BLOCK_INFO (last
)->next
= e
->dest
;
2523 /* Estimate probabilities of loopback edges in loops at same nest level. */
2526 estimate_loops_at_level (struct loop
*first_loop
)
2530 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2535 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2537 estimate_loops_at_level (loop
->inner
);
2539 /* Find current loop back edge and mark it. */
2540 e
= loop_latch_edge (loop
);
2541 EDGE_INFO (e
)->back_edge
= 1;
2543 bbs
= get_loop_body (loop
);
2544 for (i
= 0; i
< loop
->num_nodes
; i
++)
2545 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2547 propagate_freq (loop
->header
, tovisit
);
2548 BITMAP_FREE (tovisit
);
2552 /* Propagates frequencies through structure of loops. */
2555 estimate_loops (void)
2557 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2560 /* Start by estimating the frequencies in the loops. */
2561 if (number_of_loops () > 1)
2562 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2564 /* Now propagate the frequencies through all the blocks. */
2567 bitmap_set_bit (tovisit
, bb
->index
);
2569 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
2570 BITMAP_FREE (tovisit
);
2573 /* Convert counts measured by profile driven feedback to frequencies.
2574 Return nonzero iff there was any nonzero execution count. */
2577 counts_to_freqs (void)
2579 gcov_type count_max
, true_count_max
= 0;
2582 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2583 true_count_max
= MAX (bb
->count
, true_count_max
);
2585 count_max
= MAX (true_count_max
, 1);
2586 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2587 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2589 return true_count_max
;
2592 /* Return true if function is likely to be expensive, so there is no point to
2593 optimize performance of prologue, epilogue or do inlining at the expense
2594 of code size growth. THRESHOLD is the limit of number of instructions
2595 function can execute at average to be still considered not expensive. */
2598 expensive_function_p (int threshold
)
2600 unsigned int sum
= 0;
2604 /* We can not compute accurately for large thresholds due to scaled
2606 gcc_assert (threshold
<= BB_FREQ_MAX
);
2608 /* Frequencies are out of range. This either means that function contains
2609 internal loop executing more than BB_FREQ_MAX times or profile feedback
2610 is available and function has not been executed at all. */
2611 if (ENTRY_BLOCK_PTR
->frequency
== 0)
2614 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2615 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
2620 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
2621 insn
= NEXT_INSN (insn
))
2622 if (active_insn_p (insn
))
2624 sum
+= bb
->frequency
;
2633 /* Estimate basic blocks frequency by given branch probabilities. */
2636 estimate_bb_frequencies (void)
2641 if (profile_status
!= PROFILE_READ
|| !counts_to_freqs ())
2643 static int real_values_initialized
= 0;
2645 if (!real_values_initialized
)
2647 real_values_initialized
= 1;
2648 sreal_init (&real_zero
, 0, 0);
2649 sreal_init (&real_one
, 1, 0);
2650 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2651 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2652 sreal_init (&real_one_half
, 1, -1);
2653 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2654 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2657 mark_dfs_back_edges ();
2659 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
2661 /* Set up block info for each basic block. */
2662 alloc_aux_for_blocks (sizeof (struct block_info_def
));
2663 alloc_aux_for_edges (sizeof (struct edge_info_def
));
2664 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2669 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2671 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2672 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2673 &EDGE_INFO (e
)->back_edge_prob
,
2674 &real_inv_br_prob_base
);
2678 /* First compute probabilities locally for each loop from innermost
2679 to outermost to examine probabilities for back edges. */
2682 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2684 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2685 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2687 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
2688 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2692 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
2693 sreal_add (&tmp
, &tmp
, &real_one_half
);
2694 bb
->frequency
= sreal_to_int (&tmp
);
2697 free_aux_for_blocks ();
2698 free_aux_for_edges ();
2700 compute_function_frequency ();
2703 /* Decide whether function is hot, cold or unlikely executed. */
2705 compute_function_frequency (void)
2708 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
2709 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2710 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2711 node
->only_called_at_startup
= true;
2712 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
2713 node
->only_called_at_exit
= true;
2715 if (!profile_info
|| !flag_branch_probabilities
)
2717 int flags
= flags_from_decl_or_type (current_function_decl
);
2718 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2720 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2721 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
2723 node
->frequency
= NODE_FREQUENCY_HOT
;
2724 else if (flags
& ECF_NORETURN
)
2725 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2726 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2727 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2728 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2729 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
2730 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2733 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2736 if (maybe_hot_bb_p (bb
))
2738 node
->frequency
= NODE_FREQUENCY_HOT
;
2741 if (!probably_never_executed_bb_p (bb
))
2742 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2747 gate_estimate_probability (void)
2749 return flag_guess_branch_prob
;
2752 /* Build PREDICT_EXPR. */
2754 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
2756 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
2757 build_int_cst (NULL
, predictor
));
2758 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
2763 predictor_name (enum br_predictor predictor
)
2765 return predictor_info
[predictor
].name
;
2768 struct gimple_opt_pass pass_profile
=
2772 "profile_estimate", /* name */
2773 gate_estimate_probability
, /* gate */
2774 tree_estimate_probability_driver
, /* execute */
2777 0, /* static_pass_number */
2778 TV_BRANCH_PROB
, /* tv_id */
2779 PROP_cfg
, /* properties_required */
2780 0, /* properties_provided */
2781 0, /* properties_destroyed */
2782 0, /* todo_flags_start */
2783 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
2787 struct gimple_opt_pass pass_strip_predict_hints
=
2791 "*strip_predict_hints", /* name */
2793 strip_predict_hints
, /* execute */
2796 0, /* static_pass_number */
2797 TV_BRANCH_PROB
, /* tv_id */
2798 PROP_cfg
, /* properties_required */
2799 0, /* properties_provided */
2800 0, /* properties_destroyed */
2801 0, /* todo_flags_start */
2802 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
2806 /* Rebuild function frequencies. Passes are in general expected to
2807 maintain profile by hand, however in some cases this is not possible:
2808 for example when inlining several functions with loops freuqencies might run
2809 out of scale and thus needs to be recomputed. */
2812 rebuild_frequencies (void)
2814 timevar_push (TV_REBUILD_FREQUENCIES
);
2815 if (profile_status
== PROFILE_GUESSED
)
2817 loop_optimizer_init (0);
2818 add_noreturn_fake_exit_edges ();
2819 mark_irreducible_loops ();
2820 connect_infinite_loops_to_exit ();
2821 estimate_bb_frequencies ();
2822 remove_fake_exit_edges ();
2823 loop_optimizer_finalize ();
2825 else if (profile_status
== PROFILE_READ
)
2829 timevar_pop (TV_REBUILD_FREQUENCIES
);