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"
45 #include "diagnostic-core.h"
54 #include "tree-flow.h"
56 #include "tree-pass.h"
57 #include "tree-scalar-evolution.h"
59 #include "pointer-set.h"
61 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
62 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
63 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
64 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
66 /* Random guesstimation given names.
67 PROV_VERY_UNLIKELY should be small enough so basic block predicted
68 by it gets bellow HOT_BB_FREQUENCY_FRANCTION. */
69 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
70 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
71 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
72 #define PROB_ALWAYS (REG_BR_PROB_BASE)
74 static void combine_predictions_for_insn (rtx
, basic_block
);
75 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
76 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
77 static void predict_paths_leading_to_edge (edge
, enum br_predictor
, enum prediction
);
78 static bool can_predict_insn_p (const_rtx
);
80 /* Information we hold about each branch predictor.
81 Filled using information from predict.def. */
85 const char *const name
; /* Name used in the debugging dumps. */
86 const int hitrate
; /* Expected hitrate used by
87 predict_insn_def call. */
91 /* Use given predictor without Dempster-Shaffer theory if it matches
92 using first_match heuristics. */
93 #define PRED_FLAG_FIRST_MATCH 1
95 /* Recompute hitrate in percent to our representation. */
97 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
99 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
100 static const struct predictor_info predictor_info
[]= {
101 #include "predict.def"
103 /* Upper bound on predictors. */
108 /* Return TRUE if frequency FREQ is considered to be hot. */
111 maybe_hot_frequency_p (struct function
*fun
, int freq
)
113 struct cgraph_node
*node
= cgraph_get_node (fun
->decl
);
114 if (!profile_info
|| !flag_branch_probabilities
)
116 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
118 if (node
->frequency
== NODE_FREQUENCY_HOT
)
121 if (profile_status_for_function (fun
) == PROFILE_ABSENT
)
123 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
124 && freq
< (ENTRY_BLOCK_PTR_FOR_FUNCTION (fun
)->frequency
* 2 / 3))
126 if (freq
< (ENTRY_BLOCK_PTR_FOR_FUNCTION (fun
)->frequency
127 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
132 /* Return TRUE if frequency FREQ is considered to be hot. */
135 maybe_hot_count_p (struct function
*fun
, gcov_type count
)
137 if (profile_status_for_function (fun
) != PROFILE_READ
)
139 /* Code executed at most once is not hot. */
140 if (profile_info
->runs
>= count
)
143 > profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
));
146 /* Return true in case BB can be CPU intensive and should be optimized
147 for maximal performance. */
150 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
152 gcc_checking_assert (fun
);
153 if (profile_status_for_function (fun
) == PROFILE_READ
)
154 return maybe_hot_count_p (fun
, bb
->count
);
155 return maybe_hot_frequency_p (fun
, bb
->frequency
);
158 /* Return true if the call can be hot. */
161 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
163 if (profile_info
&& flag_branch_probabilities
165 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
167 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
173 && edge
->callee
->frequency
<= NODE_FREQUENCY_EXECUTED_ONCE
))
177 if (edge
->caller
->frequency
== NODE_FREQUENCY_HOT
)
179 if (edge
->caller
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
180 && edge
->frequency
< CGRAPH_FREQ_BASE
* 3 / 2)
182 if (flag_guess_branch_prob
183 && edge
->frequency
<= (CGRAPH_FREQ_BASE
184 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
189 /* Return true in case BB can be CPU intensive and should be optimized
190 for maximal performance. */
193 maybe_hot_edge_p (edge e
)
195 if (profile_status
== PROFILE_READ
)
196 return maybe_hot_count_p (cfun
, e
->count
);
197 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
201 /* Return true in case BB is probably never executed. */
204 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
206 gcc_checking_assert (fun
);
207 if (profile_info
&& flag_branch_probabilities
)
208 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
209 if ((!profile_info
|| !flag_branch_probabilities
)
210 && (cgraph_get_node (fun
->decl
)->frequency
211 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
216 /* Return true if NODE should be optimized for size. */
219 cgraph_optimize_for_size_p (struct cgraph_node
*node
)
223 if (node
&& (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
229 /* Return true when current function should always be optimized for size. */
232 optimize_function_for_size_p (struct function
*fun
)
236 if (!fun
|| !fun
->decl
)
238 return cgraph_optimize_for_size_p (cgraph_get_node (fun
->decl
));
241 /* Return true when current function should always be optimized for speed. */
244 optimize_function_for_speed_p (struct function
*fun
)
246 return !optimize_function_for_size_p (fun
);
249 /* Return TRUE when BB should be optimized for size. */
252 optimize_bb_for_size_p (const_basic_block bb
)
254 return optimize_function_for_size_p (cfun
) || !maybe_hot_bb_p (cfun
, bb
);
257 /* Return TRUE when BB should be optimized for speed. */
260 optimize_bb_for_speed_p (const_basic_block bb
)
262 return !optimize_bb_for_size_p (bb
);
265 /* Return TRUE when BB should be optimized for size. */
268 optimize_edge_for_size_p (edge e
)
270 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
273 /* Return TRUE when BB should be optimized for speed. */
276 optimize_edge_for_speed_p (edge e
)
278 return !optimize_edge_for_size_p (e
);
281 /* Return TRUE when BB should be optimized for size. */
284 optimize_insn_for_size_p (void)
286 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
289 /* Return TRUE when BB should be optimized for speed. */
292 optimize_insn_for_speed_p (void)
294 return !optimize_insn_for_size_p ();
297 /* Return TRUE when LOOP should be optimized for size. */
300 optimize_loop_for_size_p (struct loop
*loop
)
302 return optimize_bb_for_size_p (loop
->header
);
305 /* Return TRUE when LOOP should be optimized for speed. */
308 optimize_loop_for_speed_p (struct loop
*loop
)
310 return optimize_bb_for_speed_p (loop
->header
);
313 /* Return TRUE when LOOP nest should be optimized for speed. */
316 optimize_loop_nest_for_speed_p (struct loop
*loop
)
318 struct loop
*l
= loop
;
319 if (optimize_loop_for_speed_p (loop
))
322 while (l
&& l
!= loop
)
324 if (optimize_loop_for_speed_p (l
))
332 while (l
!= loop
&& !l
->next
)
341 /* Return TRUE when LOOP nest should be optimized for size. */
344 optimize_loop_nest_for_size_p (struct loop
*loop
)
346 return !optimize_loop_nest_for_speed_p (loop
);
349 /* Return true when edge E is likely to be well predictable by branch
353 predictable_edge_p (edge e
)
355 if (profile_status
== PROFILE_ABSENT
)
358 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
359 || (REG_BR_PROB_BASE
- e
->probability
360 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
366 /* Set RTL expansion for BB profile. */
369 rtl_profile_for_bb (basic_block bb
)
371 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
374 /* Set RTL expansion for edge profile. */
377 rtl_profile_for_edge (edge e
)
379 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
382 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
384 default_rtl_profile (void)
386 crtl
->maybe_hot_insn_p
= true;
389 /* Return true if the one of outgoing edges is already predicted by
393 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
396 if (!INSN_P (BB_END (bb
)))
398 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
399 if (REG_NOTE_KIND (note
) == REG_BR_PRED
400 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
405 /* This map contains for a basic block the list of predictions for the
408 static struct pointer_map_t
*bb_predictions
;
410 /* Structure representing predictions in tree level. */
412 struct edge_prediction
{
413 struct edge_prediction
*ep_next
;
415 enum br_predictor ep_predictor
;
419 /* Return true if the one of outgoing edges is already predicted by
423 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
425 struct edge_prediction
*i
;
426 void **preds
= pointer_map_contains (bb_predictions
, bb
);
431 for (i
= (struct edge_prediction
*) *preds
; i
; i
= i
->ep_next
)
432 if (i
->ep_predictor
== predictor
)
437 /* Return true when the probability of edge is reliable.
439 The profile guessing code is good at predicting branch outcome (ie.
440 taken/not taken), that is predicted right slightly over 75% of time.
441 It is however notoriously poor on predicting the probability itself.
442 In general the profile appear a lot flatter (with probabilities closer
443 to 50%) than the reality so it is bad idea to use it to drive optimization
444 such as those disabling dynamic branch prediction for well predictable
447 There are two exceptions - edges leading to noreturn edges and edges
448 predicted by number of iterations heuristics are predicted well. This macro
449 should be able to distinguish those, but at the moment it simply check for
450 noreturn heuristic that is only one giving probability over 99% or bellow
451 1%. In future we might want to propagate reliability information across the
452 CFG if we find this information useful on multiple places. */
454 probability_reliable_p (int prob
)
456 return (profile_status
== PROFILE_READ
457 || (profile_status
== PROFILE_GUESSED
458 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
461 /* Same predicate as above, working on edges. */
463 edge_probability_reliable_p (const_edge e
)
465 return probability_reliable_p (e
->probability
);
468 /* Same predicate as edge_probability_reliable_p, working on notes. */
470 br_prob_note_reliable_p (const_rtx note
)
472 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
473 return probability_reliable_p (INTVAL (XEXP (note
, 0)));
477 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
479 gcc_assert (any_condjump_p (insn
));
480 if (!flag_guess_branch_prob
)
483 add_reg_note (insn
, REG_BR_PRED
,
484 gen_rtx_CONCAT (VOIDmode
,
485 GEN_INT ((int) predictor
),
486 GEN_INT ((int) probability
)));
489 /* Predict insn by given predictor. */
492 predict_insn_def (rtx insn
, enum br_predictor predictor
,
493 enum prediction taken
)
495 int probability
= predictor_info
[(int) predictor
].hitrate
;
498 probability
= REG_BR_PROB_BASE
- probability
;
500 predict_insn (insn
, predictor
, probability
);
503 /* Predict edge E with given probability if possible. */
506 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
509 last_insn
= BB_END (e
->src
);
511 /* We can store the branch prediction information only about
512 conditional jumps. */
513 if (!any_condjump_p (last_insn
))
516 /* We always store probability of branching. */
517 if (e
->flags
& EDGE_FALLTHRU
)
518 probability
= REG_BR_PROB_BASE
- probability
;
520 predict_insn (last_insn
, predictor
, probability
);
523 /* Predict edge E with the given PROBABILITY. */
525 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
527 gcc_assert (profile_status
!= PROFILE_GUESSED
);
528 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
529 && flag_guess_branch_prob
&& optimize
)
531 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
532 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
534 i
->ep_next
= (struct edge_prediction
*) *preds
;
536 i
->ep_probability
= probability
;
537 i
->ep_predictor
= predictor
;
542 /* Remove all predictions on given basic block that are attached
545 remove_predictions_associated_with_edge (edge e
)
552 preds
= pointer_map_contains (bb_predictions
, e
->src
);
556 struct edge_prediction
**prediction
= (struct edge_prediction
**) preds
;
557 struct edge_prediction
*next
;
561 if ((*prediction
)->ep_edge
== e
)
563 next
= (*prediction
)->ep_next
;
568 prediction
= &((*prediction
)->ep_next
);
573 /* Clears the list of predictions stored for BB. */
576 clear_bb_predictions (basic_block bb
)
578 void **preds
= pointer_map_contains (bb_predictions
, bb
);
579 struct edge_prediction
*pred
, *next
;
584 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= next
)
586 next
= pred
->ep_next
;
592 /* Return true when we can store prediction on insn INSN.
593 At the moment we represent predictions only on conditional
594 jumps, not at computed jump or other complicated cases. */
596 can_predict_insn_p (const_rtx insn
)
598 return (JUMP_P (insn
)
599 && any_condjump_p (insn
)
600 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
603 /* Predict edge E by given predictor if possible. */
606 predict_edge_def (edge e
, enum br_predictor predictor
,
607 enum prediction taken
)
609 int probability
= predictor_info
[(int) predictor
].hitrate
;
612 probability
= REG_BR_PROB_BASE
- probability
;
614 predict_edge (e
, predictor
, probability
);
617 /* Invert all branch predictions or probability notes in the INSN. This needs
618 to be done each time we invert the condition used by the jump. */
621 invert_br_probabilities (rtx insn
)
625 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
626 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
627 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
628 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
629 XEXP (XEXP (note
, 0), 1)
630 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
633 /* Dump information about the branch prediction to the output file. */
636 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
637 basic_block bb
, int used
)
645 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
646 if (! (e
->flags
& EDGE_FALLTHRU
))
649 fprintf (file
, " %s heuristics%s: %.1f%%",
650 predictor_info
[predictor
].name
,
651 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
655 fprintf (file
, " exec ");
656 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
659 fprintf (file
, " hit ");
660 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
661 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
665 fprintf (file
, "\n");
668 /* We can not predict the probabilities of outgoing edges of bb. Set them
669 evenly and hope for the best. */
671 set_even_probabilities (basic_block bb
)
677 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
678 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
680 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
681 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
682 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
687 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
688 note if not already present. Remove now useless REG_BR_PRED notes. */
691 combine_predictions_for_insn (rtx insn
, basic_block bb
)
696 int best_probability
= PROB_EVEN
;
697 enum br_predictor best_predictor
= END_PREDICTORS
;
698 int combined_probability
= REG_BR_PROB_BASE
/ 2;
700 bool first_match
= false;
703 if (!can_predict_insn_p (insn
))
705 set_even_probabilities (bb
);
709 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
710 pnote
= ®_NOTES (insn
);
712 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
715 /* We implement "first match" heuristics and use probability guessed
716 by predictor with smallest index. */
717 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
718 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
720 enum br_predictor predictor
= ((enum br_predictor
)
721 INTVAL (XEXP (XEXP (note
, 0), 0)));
722 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
725 if (best_predictor
> predictor
)
726 best_probability
= probability
, best_predictor
= predictor
;
728 d
= (combined_probability
* probability
729 + (REG_BR_PROB_BASE
- combined_probability
)
730 * (REG_BR_PROB_BASE
- probability
));
732 /* Use FP math to avoid overflows of 32bit integers. */
734 /* If one probability is 0% and one 100%, avoid division by zero. */
735 combined_probability
= REG_BR_PROB_BASE
/ 2;
737 combined_probability
= (((double) combined_probability
) * probability
738 * REG_BR_PROB_BASE
/ d
+ 0.5);
741 /* Decide which heuristic to use. In case we didn't match anything,
742 use no_prediction heuristic, in case we did match, use either
743 first match or Dempster-Shaffer theory depending on the flags. */
745 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
749 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
750 combined_probability
, bb
, true);
753 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
755 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
760 combined_probability
= best_probability
;
761 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
765 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
767 enum br_predictor predictor
= ((enum br_predictor
)
768 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
769 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
771 dump_prediction (dump_file
, predictor
, probability
, bb
,
772 !first_match
|| best_predictor
== predictor
);
773 *pnote
= XEXP (*pnote
, 1);
776 pnote
= &XEXP (*pnote
, 1);
781 add_reg_note (insn
, REG_BR_PROB
, GEN_INT (combined_probability
));
783 /* Save the prediction into CFG in case we are seeing non-degenerated
785 if (!single_succ_p (bb
))
787 BRANCH_EDGE (bb
)->probability
= combined_probability
;
788 FALLTHRU_EDGE (bb
)->probability
789 = REG_BR_PROB_BASE
- combined_probability
;
792 else if (!single_succ_p (bb
))
794 int prob
= INTVAL (XEXP (prob_note
, 0));
796 BRANCH_EDGE (bb
)->probability
= prob
;
797 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
800 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
803 /* Combine predictions into single probability and store them into CFG.
804 Remove now useless prediction entries. */
807 combine_predictions_for_bb (basic_block bb
)
809 int best_probability
= PROB_EVEN
;
810 enum br_predictor best_predictor
= END_PREDICTORS
;
811 int combined_probability
= REG_BR_PROB_BASE
/ 2;
813 bool first_match
= false;
815 struct edge_prediction
*pred
;
817 edge e
, first
= NULL
, second
= NULL
;
821 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
822 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
825 if (first
&& !second
)
831 /* When there is no successor or only one choice, prediction is easy.
833 We are lazy for now and predict only basic blocks with two outgoing
834 edges. It is possible to predict generic case too, but we have to
835 ignore first match heuristics and do more involved combining. Implement
840 set_even_probabilities (bb
);
841 clear_bb_predictions (bb
);
843 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
849 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
851 preds
= pointer_map_contains (bb_predictions
, bb
);
854 /* We implement "first match" heuristics and use probability guessed
855 by predictor with smallest index. */
856 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
858 enum br_predictor predictor
= pred
->ep_predictor
;
859 int probability
= pred
->ep_probability
;
861 if (pred
->ep_edge
!= first
)
862 probability
= REG_BR_PROB_BASE
- probability
;
865 /* First match heuristics would be widly confused if we predicted
867 if (best_predictor
> predictor
)
869 struct edge_prediction
*pred2
;
870 int prob
= probability
;
872 for (pred2
= (struct edge_prediction
*) *preds
; pred2
; pred2
= pred2
->ep_next
)
873 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
875 int probability2
= pred
->ep_probability
;
877 if (pred2
->ep_edge
!= first
)
878 probability2
= REG_BR_PROB_BASE
- probability2
;
880 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
881 (probability2
< REG_BR_PROB_BASE
/ 2))
884 /* If the same predictor later gave better result, go for it! */
885 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
886 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
890 best_probability
= prob
, best_predictor
= predictor
;
893 d
= (combined_probability
* probability
894 + (REG_BR_PROB_BASE
- combined_probability
)
895 * (REG_BR_PROB_BASE
- probability
));
897 /* Use FP math to avoid overflows of 32bit integers. */
899 /* If one probability is 0% and one 100%, avoid division by zero. */
900 combined_probability
= REG_BR_PROB_BASE
/ 2;
902 combined_probability
= (((double) combined_probability
)
904 * REG_BR_PROB_BASE
/ d
+ 0.5);
908 /* Decide which heuristic to use. In case we didn't match anything,
909 use no_prediction heuristic, in case we did match, use either
910 first match or Dempster-Shaffer theory depending on the flags. */
912 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
916 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
919 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
921 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
926 combined_probability
= best_probability
;
927 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
931 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
933 enum br_predictor predictor
= pred
->ep_predictor
;
934 int probability
= pred
->ep_probability
;
936 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
937 probability
= REG_BR_PROB_BASE
- probability
;
938 dump_prediction (dump_file
, predictor
, probability
, bb
,
939 !first_match
|| best_predictor
== predictor
);
942 clear_bb_predictions (bb
);
946 first
->probability
= combined_probability
;
947 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
951 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
952 Return the SSA_NAME if the condition satisfies, NULL otherwise.
954 T1 and T2 should be one of the following cases:
955 1. T1 is SSA_NAME, T2 is NULL
956 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
957 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
960 strips_small_constant (tree t1
, tree t2
)
967 else if (TREE_CODE (t1
) == SSA_NAME
)
969 else if (host_integerp (t1
, 0))
970 value
= tree_low_cst (t1
, 0);
976 else if (host_integerp (t2
, 0))
977 value
= tree_low_cst (t2
, 0);
978 else if (TREE_CODE (t2
) == SSA_NAME
)
986 if (value
<= 4 && value
>= -4)
992 /* Return the SSA_NAME in T or T's operands.
993 Return NULL if SSA_NAME cannot be found. */
996 get_base_value (tree t
)
998 if (TREE_CODE (t
) == SSA_NAME
)
1001 if (!BINARY_CLASS_P (t
))
1004 switch (TREE_OPERAND_LENGTH (t
))
1007 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1009 return strips_small_constant (TREE_OPERAND (t
, 0),
1010 TREE_OPERAND (t
, 1));
1016 /* Check the compare STMT in LOOP. If it compares an induction
1017 variable to a loop invariant, return true, and save
1018 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1019 Otherwise return false and set LOOP_INVAIANT to NULL. */
1022 is_comparison_with_loop_invariant_p (gimple stmt
, struct loop
*loop
,
1023 tree
*loop_invariant
,
1024 enum tree_code
*compare_code
,
1028 tree op0
, op1
, bound
, base
;
1030 enum tree_code code
;
1033 code
= gimple_cond_code (stmt
);
1034 *loop_invariant
= NULL
;
1050 op0
= gimple_cond_lhs (stmt
);
1051 op1
= gimple_cond_rhs (stmt
);
1053 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1054 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1056 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1058 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1060 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1061 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1063 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1064 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1067 if (integer_zerop (iv0
.step
))
1069 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1070 code
= invert_tree_comparison (code
, false);
1073 if (host_integerp (iv1
.step
, 0))
1074 step
= tree_low_cst (iv1
.step
, 0);
1082 if (host_integerp (iv0
.step
, 0))
1083 step
= tree_low_cst (iv0
.step
, 0);
1088 if (TREE_CODE (bound
) != INTEGER_CST
)
1089 bound
= get_base_value (bound
);
1092 if (TREE_CODE (base
) != INTEGER_CST
)
1093 base
= get_base_value (base
);
1097 *loop_invariant
= bound
;
1098 *compare_code
= code
;
1100 *loop_iv_base
= base
;
1104 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1107 expr_coherent_p (tree t1
, tree t2
)
1110 tree ssa_name_1
= NULL
;
1111 tree ssa_name_2
= NULL
;
1113 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1114 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1119 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1121 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1124 /* Check to see if t1 is expressed/defined with t2. */
1125 stmt
= SSA_NAME_DEF_STMT (t1
);
1126 gcc_assert (stmt
!= NULL
);
1127 if (is_gimple_assign (stmt
))
1129 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1130 if (ssa_name_1
&& ssa_name_1
== t2
)
1134 /* Check to see if t2 is expressed/defined with t1. */
1135 stmt
= SSA_NAME_DEF_STMT (t2
);
1136 gcc_assert (stmt
!= NULL
);
1137 if (is_gimple_assign (stmt
))
1139 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1140 if (ssa_name_2
&& ssa_name_2
== t1
)
1144 /* Compare if t1 and t2's def_stmts are identical. */
1145 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1151 /* Predict branch probability of BB when BB contains a branch that compares
1152 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1153 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1156 for (int i = 0; i < bound; i++) {
1163 In this loop, we will predict the branch inside the loop to be taken. */
1166 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1167 tree loop_bound_var
,
1168 tree loop_iv_base_var
,
1169 enum tree_code loop_bound_code
,
1170 int loop_bound_step
)
1173 tree compare_var
, compare_base
;
1174 enum tree_code compare_code
;
1179 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1180 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1181 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1184 stmt
= last_stmt (bb
);
1185 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1187 if (!is_comparison_with_loop_invariant_p (stmt
, loop
, &compare_var
,
1193 /* Find the taken edge. */
1194 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1195 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1198 /* When comparing an IV to a loop invariant, NE is more likely to be
1199 taken while EQ is more likely to be not-taken. */
1200 if (compare_code
== NE_EXPR
)
1202 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1205 else if (compare_code
== EQ_EXPR
)
1207 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1211 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1214 /* If loop bound, base and compare bound are all constants, we can
1215 calculate the probability directly. */
1216 if (host_integerp (loop_bound_var
, 0)
1217 && host_integerp (compare_var
, 0)
1218 && host_integerp (compare_base
, 0))
1221 HOST_WIDE_INT compare_count
;
1222 HOST_WIDE_INT loop_bound
= tree_low_cst (loop_bound_var
, 0);
1223 HOST_WIDE_INT compare_bound
= tree_low_cst (compare_var
, 0);
1224 HOST_WIDE_INT base
= tree_low_cst (compare_base
, 0);
1225 HOST_WIDE_INT loop_count
= (loop_bound
- base
) / compare_step
;
1227 if ((compare_step
> 0)
1228 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1229 compare_count
= (loop_bound
- compare_bound
) / compare_step
;
1231 compare_count
= (compare_bound
- base
) / compare_step
;
1233 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1235 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1237 if (compare_count
< 0)
1242 if (loop_count
== 0)
1244 else if (compare_count
> loop_count
)
1245 probability
= REG_BR_PROB_BASE
;
1247 probability
= (double) REG_BR_PROB_BASE
* compare_count
/ loop_count
;
1248 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1252 if (expr_coherent_p (loop_bound_var
, compare_var
))
1254 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1255 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1256 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1257 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1258 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1259 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1260 else if (loop_bound_code
== NE_EXPR
)
1262 /* If the loop backedge condition is "(i != bound)", we do
1263 the comparison based on the step of IV:
1264 * step < 0 : backedge condition is like (i > bound)
1265 * step > 0 : backedge condition is like (i < bound) */
1266 gcc_assert (loop_bound_step
!= 0);
1267 if (loop_bound_step
> 0
1268 && (compare_code
== LT_EXPR
1269 || compare_code
== LE_EXPR
))
1270 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1271 else if (loop_bound_step
< 0
1272 && (compare_code
== GT_EXPR
1273 || compare_code
== GE_EXPR
))
1274 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1276 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1279 /* The branch is predicted not-taken if loop_bound_code is
1280 opposite with compare_code. */
1281 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1283 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1286 for (i = s; i < h; i++)
1288 The branch should be predicted taken. */
1289 if (loop_bound_step
> 0
1290 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1291 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1292 else if (loop_bound_step
< 0
1293 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1294 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1296 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1300 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1301 exits are resulted from short-circuit conditions that will generate an
1304 if (foo() || global > 10)
1307 This will be translated into:
1312 if foo() goto BB6 else goto BB5
1314 if global > 10 goto BB6 else goto BB7
1318 iftmp = (PHI 0(BB5), 1(BB6))
1319 if iftmp == 1 goto BB8 else goto BB3
1321 outside of the loop...
1323 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1324 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1325 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1326 exits to predict them using PRED_LOOP_EXIT. */
1329 predict_extra_loop_exits (edge exit_edge
)
1332 bool check_value_one
;
1334 tree cmp_rhs
, cmp_lhs
;
1335 gimple cmp_stmt
= last_stmt (exit_edge
->src
);
1337 if (!cmp_stmt
|| gimple_code (cmp_stmt
) != GIMPLE_COND
)
1339 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1340 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1341 if (!TREE_CONSTANT (cmp_rhs
)
1342 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1344 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1347 /* If check_value_one is true, only the phi_args with value '1' will lead
1348 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1350 check_value_one
= (((integer_onep (cmp_rhs
))
1351 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1352 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1354 phi_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1355 if (!phi_stmt
|| gimple_code (phi_stmt
) != GIMPLE_PHI
)
1358 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1362 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1363 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1365 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1367 if ((check_value_one
^ integer_onep (val
)) == 1)
1369 if (EDGE_COUNT (e
->src
->succs
) != 1)
1371 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1375 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1376 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1380 /* Predict edge probabilities by exploiting loop structure. */
1383 predict_loops (void)
1388 /* Try to predict out blocks in a loop that are not part of a
1390 FOR_EACH_LOOP (li
, loop
, 0)
1392 basic_block bb
, *bbs
;
1393 unsigned j
, n_exits
;
1394 VEC (edge
, heap
) *exits
;
1395 struct tree_niter_desc niter_desc
;
1397 struct nb_iter_bound
*nb_iter
;
1398 enum tree_code loop_bound_code
= ERROR_MARK
;
1399 int loop_bound_step
= 0;
1400 tree loop_bound_var
= NULL
;
1401 tree loop_iv_base
= NULL
;
1404 exits
= get_loop_exit_edges (loop
);
1405 n_exits
= VEC_length (edge
, exits
);
1407 FOR_EACH_VEC_ELT (edge
, exits
, j
, ex
)
1410 HOST_WIDE_INT nitercst
;
1411 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1413 enum br_predictor predictor
;
1415 predict_extra_loop_exits (ex
);
1417 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
1418 niter
= niter_desc
.niter
;
1419 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1420 niter
= loop_niter_by_eval (loop
, ex
);
1422 if (TREE_CODE (niter
) == INTEGER_CST
)
1424 if (host_integerp (niter
, 1)
1425 && compare_tree_int (niter
, max
-1) == -1)
1426 nitercst
= tree_low_cst (niter
, 1) + 1;
1429 predictor
= PRED_LOOP_ITERATIONS
;
1431 /* If we have just one exit and we can derive some information about
1432 the number of iterations of the loop from the statements inside
1433 the loop, use it to predict this exit. */
1434 else if (n_exits
== 1)
1436 nitercst
= estimated_stmt_executions_int (loop
);
1442 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1447 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1448 predict_edge (ex
, predictor
, probability
);
1450 VEC_free (edge
, heap
, exits
);
1452 /* Find information about loop bound variables. */
1453 for (nb_iter
= loop
->bounds
; nb_iter
;
1454 nb_iter
= nb_iter
->next
)
1456 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1458 stmt
= nb_iter
->stmt
;
1461 if (!stmt
&& last_stmt (loop
->header
)
1462 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1463 stmt
= last_stmt (loop
->header
);
1465 is_comparison_with_loop_invariant_p (stmt
, loop
,
1471 bbs
= get_loop_body (loop
);
1473 for (j
= 0; j
< loop
->num_nodes
; j
++)
1475 int header_found
= 0;
1481 /* Bypass loop heuristics on continue statement. These
1482 statements construct loops via "non-loop" constructs
1483 in the source language and are better to be handled
1485 if (predicted_by_p (bb
, PRED_CONTINUE
))
1488 /* Loop branch heuristics - predict an edge back to a
1489 loop's head as taken. */
1490 if (bb
== loop
->latch
)
1492 e
= find_edge (loop
->latch
, loop
->header
);
1496 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1500 /* Loop exit heuristics - predict an edge exiting the loop if the
1501 conditional has no loop header successors as not taken. */
1503 /* If we already used more reliable loop exit predictors, do not
1504 bother with PRED_LOOP_EXIT. */
1505 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1506 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1508 /* For loop with many exits we don't want to predict all exits
1509 with the pretty large probability, because if all exits are
1510 considered in row, the loop would be predicted to iterate
1511 almost never. The code to divide probability by number of
1512 exits is very rough. It should compute the number of exits
1513 taken in each patch through function (not the overall number
1514 of exits that might be a lot higher for loops with wide switch
1515 statements in them) and compute n-th square root.
1517 We limit the minimal probability by 2% to avoid
1518 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1519 as this was causing regression in perl benchmark containing such
1522 int probability
= ((REG_BR_PROB_BASE
1523 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1525 if (probability
< HITRATE (2))
1526 probability
= HITRATE (2);
1527 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1528 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1529 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1530 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1533 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1538 /* Free basic blocks from get_loop_body. */
1543 /* Attempt to predict probabilities of BB outgoing edges using local
1546 bb_estimate_probability_locally (basic_block bb
)
1548 rtx last_insn
= BB_END (bb
);
1551 if (! can_predict_insn_p (last_insn
))
1553 cond
= get_condition (last_insn
, NULL
, false, false);
1557 /* Try "pointer heuristic."
1558 A comparison ptr == 0 is predicted as false.
1559 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1560 if (COMPARISON_P (cond
)
1561 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1562 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1564 if (GET_CODE (cond
) == EQ
)
1565 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1566 else if (GET_CODE (cond
) == NE
)
1567 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1571 /* Try "opcode heuristic."
1572 EQ tests are usually false and NE tests are usually true. Also,
1573 most quantities are positive, so we can make the appropriate guesses
1574 about signed comparisons against zero. */
1575 switch (GET_CODE (cond
))
1578 /* Unconditional branch. */
1579 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1580 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1585 /* Floating point comparisons appears to behave in a very
1586 unpredictable way because of special role of = tests in
1588 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1590 /* Comparisons with 0 are often used for booleans and there is
1591 nothing useful to predict about them. */
1592 else if (XEXP (cond
, 1) == const0_rtx
1593 || XEXP (cond
, 0) == const0_rtx
)
1596 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1601 /* Floating point comparisons appears to behave in a very
1602 unpredictable way because of special role of = tests in
1604 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1606 /* Comparisons with 0 are often used for booleans and there is
1607 nothing useful to predict about them. */
1608 else if (XEXP (cond
, 1) == const0_rtx
1609 || XEXP (cond
, 0) == const0_rtx
)
1612 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1616 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1620 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1625 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1626 || XEXP (cond
, 1) == constm1_rtx
)
1627 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1632 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1633 || XEXP (cond
, 1) == constm1_rtx
)
1634 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1642 /* Set edge->probability for each successor edge of BB. */
1644 guess_outgoing_edge_probabilities (basic_block bb
)
1646 bb_estimate_probability_locally (bb
);
1647 combine_predictions_for_insn (BB_END (bb
), bb
);
1650 static tree
expr_expected_value (tree
, bitmap
);
1652 /* Helper function for expr_expected_value. */
1655 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1656 tree op1
, bitmap visited
)
1660 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1662 if (TREE_CONSTANT (op0
))
1665 if (code
!= SSA_NAME
)
1668 def
= SSA_NAME_DEF_STMT (op0
);
1670 /* If we were already here, break the infinite cycle. */
1671 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1674 if (gimple_code (def
) == GIMPLE_PHI
)
1676 /* All the arguments of the PHI node must have the same constant
1678 int i
, n
= gimple_phi_num_args (def
);
1679 tree val
= NULL
, new_val
;
1681 for (i
= 0; i
< n
; i
++)
1683 tree arg
= PHI_ARG_DEF (def
, i
);
1685 /* If this PHI has itself as an argument, we cannot
1686 determine the string length of this argument. However,
1687 if we can find an expected constant value for the other
1688 PHI args then we can still be sure that this is
1689 likely a constant. So be optimistic and just
1690 continue with the next argument. */
1691 if (arg
== PHI_RESULT (def
))
1694 new_val
= expr_expected_value (arg
, visited
);
1699 else if (!operand_equal_p (val
, new_val
, false))
1704 if (is_gimple_assign (def
))
1706 if (gimple_assign_lhs (def
) != op0
)
1709 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1710 gimple_assign_rhs1 (def
),
1711 gimple_assign_rhs_code (def
),
1712 gimple_assign_rhs2 (def
),
1716 if (is_gimple_call (def
))
1718 tree decl
= gimple_call_fndecl (def
);
1721 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1722 switch (DECL_FUNCTION_CODE (decl
))
1724 case BUILT_IN_EXPECT
:
1727 if (gimple_call_num_args (def
) != 2)
1729 val
= gimple_call_arg (def
, 0);
1730 if (TREE_CONSTANT (val
))
1732 return gimple_call_arg (def
, 1);
1735 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1736 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1737 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1738 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1739 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1740 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1741 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1742 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1743 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1744 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1745 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1746 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1747 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1748 /* Assume that any given atomic operation has low contention,
1749 and thus the compare-and-swap operation succeeds. */
1750 return boolean_true_node
;
1757 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1760 op0
= expr_expected_value (op0
, visited
);
1763 op1
= expr_expected_value (op1
, visited
);
1766 res
= fold_build2 (code
, type
, op0
, op1
);
1767 if (TREE_CONSTANT (res
))
1771 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1774 op0
= expr_expected_value (op0
, visited
);
1777 res
= fold_build1 (code
, type
, op0
);
1778 if (TREE_CONSTANT (res
))
1785 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1786 The function is used by builtin_expect branch predictor so the evidence
1787 must come from this construct and additional possible constant folding.
1789 We may want to implement more involved value guess (such as value range
1790 propagation based prediction), but such tricks shall go to new
1794 expr_expected_value (tree expr
, bitmap visited
)
1796 enum tree_code code
;
1799 if (TREE_CONSTANT (expr
))
1802 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1803 return expr_expected_value_1 (TREE_TYPE (expr
),
1804 op0
, code
, op1
, visited
);
1808 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1809 we no longer need. */
1811 strip_predict_hints (void)
1819 gimple_stmt_iterator bi
;
1820 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
1822 gimple stmt
= gsi_stmt (bi
);
1824 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
1826 gsi_remove (&bi
, true);
1829 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1831 tree fndecl
= gimple_call_fndecl (stmt
);
1834 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1835 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1836 && gimple_call_num_args (stmt
) == 2)
1838 var
= gimple_call_lhs (stmt
);
1842 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
1843 gsi_replace (&bi
, ass_stmt
, true);
1847 gsi_remove (&bi
, true);
1858 /* Predict using opcode of the last statement in basic block. */
1860 tree_predict_by_opcode (basic_block bb
)
1862 gimple stmt
= last_stmt (bb
);
1871 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1873 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1874 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1876 op0
= gimple_cond_lhs (stmt
);
1877 op1
= gimple_cond_rhs (stmt
);
1878 cmp
= gimple_cond_code (stmt
);
1879 type
= TREE_TYPE (op0
);
1880 visited
= BITMAP_ALLOC (NULL
);
1881 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
);
1882 BITMAP_FREE (visited
);
1885 if (integer_zerop (val
))
1886 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1888 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1891 /* Try "pointer heuristic."
1892 A comparison ptr == 0 is predicted as false.
1893 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1894 if (POINTER_TYPE_P (type
))
1897 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1898 else if (cmp
== NE_EXPR
)
1899 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1903 /* Try "opcode heuristic."
1904 EQ tests are usually false and NE tests are usually true. Also,
1905 most quantities are positive, so we can make the appropriate guesses
1906 about signed comparisons against zero. */
1911 /* Floating point comparisons appears to behave in a very
1912 unpredictable way because of special role of = tests in
1914 if (FLOAT_TYPE_P (type
))
1916 /* Comparisons with 0 are often used for booleans and there is
1917 nothing useful to predict about them. */
1918 else if (integer_zerop (op0
) || integer_zerop (op1
))
1921 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1926 /* Floating point comparisons appears to behave in a very
1927 unpredictable way because of special role of = tests in
1929 if (FLOAT_TYPE_P (type
))
1931 /* Comparisons with 0 are often used for booleans and there is
1932 nothing useful to predict about them. */
1933 else if (integer_zerop (op0
)
1934 || integer_zerop (op1
))
1937 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1941 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1944 case UNORDERED_EXPR
:
1945 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1950 if (integer_zerop (op1
)
1951 || integer_onep (op1
)
1952 || integer_all_onesp (op1
)
1955 || real_minus_onep (op1
))
1956 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1961 if (integer_zerop (op1
)
1962 || integer_onep (op1
)
1963 || integer_all_onesp (op1
)
1966 || real_minus_onep (op1
))
1967 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1975 /* Try to guess whether the value of return means error code. */
1977 static enum br_predictor
1978 return_prediction (tree val
, enum prediction
*prediction
)
1982 return PRED_NO_PREDICTION
;
1983 /* Different heuristics for pointers and scalars. */
1984 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1986 /* NULL is usually not returned. */
1987 if (integer_zerop (val
))
1989 *prediction
= NOT_TAKEN
;
1990 return PRED_NULL_RETURN
;
1993 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1995 /* Negative return values are often used to indicate
1997 if (TREE_CODE (val
) == INTEGER_CST
1998 && tree_int_cst_sgn (val
) < 0)
2000 *prediction
= NOT_TAKEN
;
2001 return PRED_NEGATIVE_RETURN
;
2003 /* Constant return values seems to be commonly taken.
2004 Zero/one often represent booleans so exclude them from the
2006 if (TREE_CONSTANT (val
)
2007 && (!integer_zerop (val
) && !integer_onep (val
)))
2009 *prediction
= TAKEN
;
2010 return PRED_CONST_RETURN
;
2013 return PRED_NO_PREDICTION
;
2016 /* Find the basic block with return expression and look up for possible
2017 return value trying to apply RETURN_PREDICTION heuristics. */
2019 apply_return_prediction (void)
2021 gimple return_stmt
= NULL
;
2025 int phi_num_args
, i
;
2026 enum br_predictor pred
;
2027 enum prediction direction
;
2030 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
2032 return_stmt
= last_stmt (e
->src
);
2034 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
2039 return_val
= gimple_return_retval (return_stmt
);
2042 if (TREE_CODE (return_val
) != SSA_NAME
2043 || !SSA_NAME_DEF_STMT (return_val
)
2044 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2046 phi
= SSA_NAME_DEF_STMT (return_val
);
2047 phi_num_args
= gimple_phi_num_args (phi
);
2048 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2050 /* Avoid the degenerate case where all return values form the function
2051 belongs to same category (ie they are all positive constants)
2052 so we can hardly say something about them. */
2053 for (i
= 1; i
< phi_num_args
; i
++)
2054 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2056 if (i
!= phi_num_args
)
2057 for (i
= 0; i
< phi_num_args
; i
++)
2059 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2060 if (pred
!= PRED_NO_PREDICTION
)
2061 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2066 /* Look for basic block that contains unlikely to happen events
2067 (such as noreturn calls) and mark all paths leading to execution
2068 of this basic blocks as unlikely. */
2071 tree_bb_level_predictions (void)
2074 bool has_return_edges
= false;
2078 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
2079 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2081 has_return_edges
= true;
2085 apply_return_prediction ();
2089 gimple_stmt_iterator gsi
;
2091 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2093 gimple stmt
= gsi_stmt (gsi
);
2096 if (is_gimple_call (stmt
))
2098 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2099 && has_return_edges
)
2100 predict_paths_leading_to (bb
, PRED_NORETURN
,
2102 decl
= gimple_call_fndecl (stmt
);
2104 && lookup_attribute ("cold",
2105 DECL_ATTRIBUTES (decl
)))
2106 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2109 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2111 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2112 gimple_predict_outcome (stmt
));
2113 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2114 hints to callers. */
2120 #ifdef ENABLE_CHECKING
2122 /* Callback for pointer_map_traverse, asserts that the pointer map is
2126 assert_is_empty (const void *key ATTRIBUTE_UNUSED
, void **value
,
2127 void *data ATTRIBUTE_UNUSED
)
2129 gcc_assert (!*value
);
2134 /* Predict branch probabilities and estimate profile for basic block BB. */
2137 tree_estimate_probability_bb (basic_block bb
)
2143 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2145 /* Predict edges to user labels with attributes. */
2146 if (e
->dest
!= EXIT_BLOCK_PTR
)
2148 gimple_stmt_iterator gi
;
2149 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2151 gimple stmt
= gsi_stmt (gi
);
2154 if (gimple_code (stmt
) != GIMPLE_LABEL
)
2156 decl
= gimple_label_label (stmt
);
2157 if (DECL_ARTIFICIAL (decl
))
2160 /* Finally, we have a user-defined label. */
2161 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2162 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2163 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2164 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2168 /* Predict early returns to be probable, as we've already taken
2169 care for error returns and other cases are often used for
2170 fast paths through function.
2172 Since we've already removed the return statements, we are
2173 looking for CFG like:
2183 if (e
->dest
!= bb
->next_bb
2184 && e
->dest
!= EXIT_BLOCK_PTR
2185 && single_succ_p (e
->dest
)
2186 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR
2187 && (last
= last_stmt (e
->dest
)) != NULL
2188 && gimple_code (last
) == GIMPLE_RETURN
)
2193 if (single_succ_p (bb
))
2195 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2196 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2197 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2198 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2199 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2202 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2203 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2204 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2205 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2208 /* Look for block we are guarding (ie we dominate it,
2209 but it doesn't postdominate us). */
2210 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
2211 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2212 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2214 gimple_stmt_iterator bi
;
2216 /* The call heuristic claims that a guarded function call
2217 is improbable. This is because such calls are often used
2218 to signal exceptional situations such as printing error
2220 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2223 gimple stmt
= gsi_stmt (bi
);
2224 if (is_gimple_call (stmt
)
2225 /* Constant and pure calls are hardly used to signalize
2226 something exceptional. */
2227 && gimple_has_side_effects (stmt
))
2229 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2235 tree_predict_by_opcode (bb
);
2238 /* Predict branch probabilities and estimate profile of the tree CFG.
2239 This function can be called from the loop optimizers to recompute
2240 the profile information. */
2243 tree_estimate_probability (void)
2247 add_noreturn_fake_exit_edges ();
2248 connect_infinite_loops_to_exit ();
2249 /* We use loop_niter_by_eval, which requires that the loops have
2251 create_preheaders (CP_SIMPLE_PREHEADERS
);
2252 calculate_dominance_info (CDI_POST_DOMINATORS
);
2254 bb_predictions
= pointer_map_create ();
2255 tree_bb_level_predictions ();
2256 record_loop_exits ();
2258 if (number_of_loops () > 1)
2262 tree_estimate_probability_bb (bb
);
2265 combine_predictions_for_bb (bb
);
2267 #ifdef ENABLE_CHECKING
2268 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
2270 pointer_map_destroy (bb_predictions
);
2271 bb_predictions
= NULL
;
2273 estimate_bb_frequencies ();
2274 free_dominance_info (CDI_POST_DOMINATORS
);
2275 remove_fake_exit_edges ();
2278 /* Predict branch probabilities and estimate profile of the tree CFG.
2279 This is the driver function for PASS_PROFILE. */
2282 tree_estimate_probability_driver (void)
2286 loop_optimizer_init (LOOPS_NORMAL
);
2287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2288 flow_loops_dump (dump_file
, NULL
, 0);
2290 mark_irreducible_loops ();
2292 nb_loops
= number_of_loops ();
2296 tree_estimate_probability ();
2301 loop_optimizer_finalize ();
2302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2303 gimple_dump_cfg (dump_file
, dump_flags
);
2304 if (profile_status
== PROFILE_ABSENT
)
2305 profile_status
= PROFILE_GUESSED
;
2309 /* Predict edges to successors of CUR whose sources are not postdominated by
2310 BB by PRED and recurse to all postdominators. */
2313 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2314 enum br_predictor pred
,
2315 enum prediction taken
,
2322 /* We are looking for all edges forming edge cut induced by
2323 set of all blocks postdominated by BB. */
2324 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2325 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2326 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2332 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2333 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2335 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2337 /* See if there is an edge from e->src that is not abnormal
2338 and does not lead to BB. */
2339 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2341 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2342 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2348 /* If there is non-abnormal path leaving e->src, predict edge
2349 using predictor. Otherwise we need to look for paths
2352 The second may lead to infinite loop in the case we are predicitng
2353 regions that are only reachable by abnormal edges. We simply
2354 prevent visiting given BB twice. */
2356 predict_edge_def (e
, pred
, taken
);
2357 else if (bitmap_set_bit (visited
, e
->src
->index
))
2358 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2360 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2362 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2363 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2366 /* Sets branch probabilities according to PREDiction and
2370 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2371 enum prediction taken
)
2373 bitmap visited
= BITMAP_ALLOC (NULL
);
2374 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2375 BITMAP_FREE (visited
);
2378 /* Like predict_paths_leading_to but take edge instead of basic block. */
2381 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2382 enum prediction taken
)
2384 bool has_nonloop_edge
= false;
2388 basic_block bb
= e
->src
;
2389 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2390 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2391 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2392 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2394 has_nonloop_edge
= true;
2397 if (!has_nonloop_edge
)
2399 bitmap visited
= BITMAP_ALLOC (NULL
);
2400 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2401 BITMAP_FREE (visited
);
2404 predict_edge_def (e
, pred
, taken
);
2407 /* This is used to carry information about basic blocks. It is
2408 attached to the AUX field of the standard CFG block. */
2410 typedef struct block_info_def
2412 /* Estimated frequency of execution of basic_block. */
2415 /* To keep queue of basic blocks to process. */
2418 /* Number of predecessors we need to visit first. */
2422 /* Similar information for edges. */
2423 typedef struct edge_info_def
2425 /* In case edge is a loopback edge, the probability edge will be reached
2426 in case header is. Estimated number of iterations of the loop can be
2427 then computed as 1 / (1 - back_edge_prob). */
2428 sreal back_edge_prob
;
2429 /* True if the edge is a loopback edge in the natural loop. */
2430 unsigned int back_edge
:1;
2433 #define BLOCK_INFO(B) ((block_info) (B)->aux)
2434 #define EDGE_INFO(E) ((edge_info) (E)->aux)
2436 /* Helper function for estimate_bb_frequencies.
2437 Propagate the frequencies in blocks marked in
2438 TOVISIT, starting in HEAD. */
2441 propagate_freq (basic_block head
, bitmap tovisit
)
2450 /* For each basic block we need to visit count number of his predecessors
2451 we need to visit first. */
2452 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2457 bb
= BASIC_BLOCK (i
);
2459 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2461 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2463 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2465 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2467 "Irreducible region hit, ignoring edge to %i->%i\n",
2468 e
->src
->index
, bb
->index
);
2470 BLOCK_INFO (bb
)->npredecessors
= count
;
2471 /* When function never returns, we will never process exit block. */
2472 if (!count
&& bb
== EXIT_BLOCK_PTR
)
2473 bb
->count
= bb
->frequency
= 0;
2476 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
2478 for (bb
= head
; bb
; bb
= nextbb
)
2481 sreal cyclic_probability
, frequency
;
2483 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
2484 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
2486 nextbb
= BLOCK_INFO (bb
)->next
;
2487 BLOCK_INFO (bb
)->next
= NULL
;
2489 /* Compute frequency of basic block. */
2492 #ifdef ENABLE_CHECKING
2493 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2494 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2495 || (e
->flags
& EDGE_DFS_BACK
));
2498 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2499 if (EDGE_INFO (e
)->back_edge
)
2501 sreal_add (&cyclic_probability
, &cyclic_probability
,
2502 &EDGE_INFO (e
)->back_edge_prob
);
2504 else if (!(e
->flags
& EDGE_DFS_BACK
))
2508 /* frequency += (e->probability
2509 * BLOCK_INFO (e->src)->frequency /
2510 REG_BR_PROB_BASE); */
2512 sreal_init (&tmp
, e
->probability
, 0);
2513 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
2514 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
2515 sreal_add (&frequency
, &frequency
, &tmp
);
2518 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
2520 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
2521 sizeof (frequency
));
2525 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
2527 memcpy (&cyclic_probability
, &real_almost_one
,
2528 sizeof (real_almost_one
));
2531 /* BLOCK_INFO (bb)->frequency = frequency
2532 / (1 - cyclic_probability) */
2534 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
2535 sreal_div (&BLOCK_INFO (bb
)->frequency
,
2536 &frequency
, &cyclic_probability
);
2540 bitmap_clear_bit (tovisit
, bb
->index
);
2542 e
= find_edge (bb
, head
);
2547 /* EDGE_INFO (e)->back_edge_prob
2548 = ((e->probability * BLOCK_INFO (bb)->frequency)
2549 / REG_BR_PROB_BASE); */
2551 sreal_init (&tmp
, e
->probability
, 0);
2552 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
2553 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2554 &tmp
, &real_inv_br_prob_base
);
2557 /* Propagate to successor blocks. */
2558 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2559 if (!(e
->flags
& EDGE_DFS_BACK
)
2560 && BLOCK_INFO (e
->dest
)->npredecessors
)
2562 BLOCK_INFO (e
->dest
)->npredecessors
--;
2563 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2568 BLOCK_INFO (last
)->next
= e
->dest
;
2576 /* Estimate probabilities of loopback edges in loops at same nest level. */
2579 estimate_loops_at_level (struct loop
*first_loop
)
2583 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2588 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2590 estimate_loops_at_level (loop
->inner
);
2592 /* Find current loop back edge and mark it. */
2593 e
= loop_latch_edge (loop
);
2594 EDGE_INFO (e
)->back_edge
= 1;
2596 bbs
= get_loop_body (loop
);
2597 for (i
= 0; i
< loop
->num_nodes
; i
++)
2598 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2600 propagate_freq (loop
->header
, tovisit
);
2601 BITMAP_FREE (tovisit
);
2605 /* Propagates frequencies through structure of loops. */
2608 estimate_loops (void)
2610 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2613 /* Start by estimating the frequencies in the loops. */
2614 if (number_of_loops () > 1)
2615 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2617 /* Now propagate the frequencies through all the blocks. */
2620 bitmap_set_bit (tovisit
, bb
->index
);
2622 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
2623 BITMAP_FREE (tovisit
);
2626 /* Convert counts measured by profile driven feedback to frequencies.
2627 Return nonzero iff there was any nonzero execution count. */
2630 counts_to_freqs (void)
2632 gcov_type count_max
, true_count_max
= 0;
2635 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2636 true_count_max
= MAX (bb
->count
, true_count_max
);
2638 count_max
= MAX (true_count_max
, 1);
2639 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2640 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2642 return true_count_max
;
2645 /* Return true if function is likely to be expensive, so there is no point to
2646 optimize performance of prologue, epilogue or do inlining at the expense
2647 of code size growth. THRESHOLD is the limit of number of instructions
2648 function can execute at average to be still considered not expensive. */
2651 expensive_function_p (int threshold
)
2653 unsigned int sum
= 0;
2657 /* We can not compute accurately for large thresholds due to scaled
2659 gcc_assert (threshold
<= BB_FREQ_MAX
);
2661 /* Frequencies are out of range. This either means that function contains
2662 internal loop executing more than BB_FREQ_MAX times or profile feedback
2663 is available and function has not been executed at all. */
2664 if (ENTRY_BLOCK_PTR
->frequency
== 0)
2667 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2668 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
2673 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
2674 insn
= NEXT_INSN (insn
))
2675 if (active_insn_p (insn
))
2677 sum
+= bb
->frequency
;
2686 /* Estimate basic blocks frequency by given branch probabilities. */
2689 estimate_bb_frequencies (void)
2694 if (profile_status
!= PROFILE_READ
|| !counts_to_freqs ())
2696 static int real_values_initialized
= 0;
2698 if (!real_values_initialized
)
2700 real_values_initialized
= 1;
2701 sreal_init (&real_zero
, 0, 0);
2702 sreal_init (&real_one
, 1, 0);
2703 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2704 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2705 sreal_init (&real_one_half
, 1, -1);
2706 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2707 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2710 mark_dfs_back_edges ();
2712 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
2714 /* Set up block info for each basic block. */
2715 alloc_aux_for_blocks (sizeof (struct block_info_def
));
2716 alloc_aux_for_edges (sizeof (struct edge_info_def
));
2717 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2722 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2724 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2725 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2726 &EDGE_INFO (e
)->back_edge_prob
,
2727 &real_inv_br_prob_base
);
2731 /* First compute probabilities locally for each loop from innermost
2732 to outermost to examine probabilities for back edges. */
2735 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2737 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2738 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2740 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
2741 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2745 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
2746 sreal_add (&tmp
, &tmp
, &real_one_half
);
2747 bb
->frequency
= sreal_to_int (&tmp
);
2750 free_aux_for_blocks ();
2751 free_aux_for_edges ();
2753 compute_function_frequency ();
2756 /* Decide whether function is hot, cold or unlikely executed. */
2758 compute_function_frequency (void)
2761 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
2762 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2763 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2764 node
->only_called_at_startup
= true;
2765 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
2766 node
->only_called_at_exit
= true;
2768 if (!profile_info
|| !flag_branch_probabilities
)
2770 int flags
= flags_from_decl_or_type (current_function_decl
);
2771 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2773 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2774 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
2776 node
->frequency
= NODE_FREQUENCY_HOT
;
2777 else if (flags
& ECF_NORETURN
)
2778 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2779 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2780 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2781 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2782 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
2783 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2786 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2789 if (maybe_hot_bb_p (cfun
, bb
))
2791 node
->frequency
= NODE_FREQUENCY_HOT
;
2794 if (!probably_never_executed_bb_p (cfun
, bb
))
2795 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2800 gate_estimate_probability (void)
2802 return flag_guess_branch_prob
;
2805 /* Build PREDICT_EXPR. */
2807 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
2809 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
2810 build_int_cst (integer_type_node
, predictor
));
2811 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
2816 predictor_name (enum br_predictor predictor
)
2818 return predictor_info
[predictor
].name
;
2821 struct gimple_opt_pass pass_profile
=
2825 "profile_estimate", /* name */
2826 gate_estimate_probability
, /* gate */
2827 tree_estimate_probability_driver
, /* execute */
2830 0, /* static_pass_number */
2831 TV_BRANCH_PROB
, /* tv_id */
2832 PROP_cfg
, /* properties_required */
2833 0, /* properties_provided */
2834 0, /* properties_destroyed */
2835 0, /* todo_flags_start */
2836 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
2840 struct gimple_opt_pass pass_strip_predict_hints
=
2844 "*strip_predict_hints", /* name */
2846 strip_predict_hints
, /* execute */
2849 0, /* static_pass_number */
2850 TV_BRANCH_PROB
, /* tv_id */
2851 PROP_cfg
, /* properties_required */
2852 0, /* properties_provided */
2853 0, /* properties_destroyed */
2854 0, /* todo_flags_start */
2855 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
2859 /* Rebuild function frequencies. Passes are in general expected to
2860 maintain profile by hand, however in some cases this is not possible:
2861 for example when inlining several functions with loops freuqencies might run
2862 out of scale and thus needs to be recomputed. */
2865 rebuild_frequencies (void)
2867 timevar_push (TV_REBUILD_FREQUENCIES
);
2868 if (profile_status
== PROFILE_GUESSED
)
2870 loop_optimizer_init (0);
2871 add_noreturn_fake_exit_edges ();
2872 mark_irreducible_loops ();
2873 connect_infinite_loops_to_exit ();
2874 estimate_bb_frequencies ();
2875 remove_fake_exit_edges ();
2876 loop_optimizer_finalize ();
2878 else if (profile_status
== PROFILE_READ
)
2882 timevar_pop (TV_REBUILD_FREQUENCIES
);