1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
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"
56 #include "tree-flow.h"
58 #include "tree-dump.h"
59 #include "tree-pass.h"
61 #include "tree-scalar-evolution.h"
63 #include "pointer-set.h"
65 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
66 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
67 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
68 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
70 /* Random guesstimation given names.
71 PROV_VERY_UNLIKELY should be small enough so basic block predicted
72 by it gets bellow HOT_BB_FREQUENCY_FRANCTION. */
73 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
74 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
75 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
76 #define PROB_ALWAYS (REG_BR_PROB_BASE)
78 static void combine_predictions_for_insn (rtx
, basic_block
);
79 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
80 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
81 static void choose_function_section (void);
82 static bool can_predict_insn_p (const_rtx
);
84 /* Information we hold about each branch predictor.
85 Filled using information from predict.def. */
89 const char *const name
; /* Name used in the debugging dumps. */
90 const int hitrate
; /* Expected hitrate used by
91 predict_insn_def call. */
95 /* Use given predictor without Dempster-Shaffer theory if it matches
96 using first_match heuristics. */
97 #define PRED_FLAG_FIRST_MATCH 1
99 /* Recompute hitrate in percent to our representation. */
101 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
103 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
104 static const struct predictor_info predictor_info
[]= {
105 #include "predict.def"
107 /* Upper bound on predictors. */
112 /* Return TRUE if frequency FREQ is considered to be hot. */
115 maybe_hot_frequency_p (int freq
)
117 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
118 if (!profile_info
|| !flag_branch_probabilities
)
120 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
122 if (node
->frequency
== NODE_FREQUENCY_HOT
)
125 if (profile_status
== PROFILE_ABSENT
)
127 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
128 && freq
<= (ENTRY_BLOCK_PTR
->frequency
* 2 / 3))
130 if (freq
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
135 /* Return TRUE if frequency FREQ is considered to be hot. */
138 maybe_hot_count_p (gcov_type count
)
140 if (profile_status
!= PROFILE_READ
)
142 /* Code executed at most once is not hot. */
143 if (profile_info
->runs
>= count
)
146 > profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
));
149 /* Return true in case BB can be CPU intensive and should be optimized
150 for maximal performance. */
153 maybe_hot_bb_p (const_basic_block bb
)
155 if (profile_status
== PROFILE_READ
)
156 return maybe_hot_count_p (bb
->count
);
157 return maybe_hot_frequency_p (bb
->frequency
);
160 /* Return true if the call can be hot. */
163 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
165 if (profile_info
&& flag_branch_probabilities
167 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
169 if (edge
->caller
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
170 || edge
->callee
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
172 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 (e
->count
);
197 return maybe_hot_frequency_p (EDGE_FREQUENCY (e
));
200 /* Return true in case BB is probably never executed. */
202 probably_never_executed_bb_p (const_basic_block bb
)
204 if (profile_info
&& flag_branch_probabilities
)
205 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
206 if ((!profile_info
|| !flag_branch_probabilities
)
207 && cgraph_node (current_function_decl
)->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
212 /* Return true when current function should always be optimized for size. */
215 optimize_function_for_size_p (struct function
*fun
)
217 return (optimize_size
219 && (cgraph_node (fun
->decl
)->frequency
220 == NODE_FREQUENCY_UNLIKELY_EXECUTED
)));
223 /* Return true when current function should always be optimized for speed. */
226 optimize_function_for_speed_p (struct function
*fun
)
228 return !optimize_function_for_size_p (fun
);
231 /* Return TRUE when BB should be optimized for size. */
234 optimize_bb_for_size_p (const_basic_block bb
)
236 return optimize_function_for_size_p (cfun
) || !maybe_hot_bb_p (bb
);
239 /* Return TRUE when BB should be optimized for speed. */
242 optimize_bb_for_speed_p (const_basic_block bb
)
244 return !optimize_bb_for_size_p (bb
);
247 /* Return TRUE when BB should be optimized for size. */
250 optimize_edge_for_size_p (edge e
)
252 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
255 /* Return TRUE when BB should be optimized for speed. */
258 optimize_edge_for_speed_p (edge e
)
260 return !optimize_edge_for_size_p (e
);
263 /* Return TRUE when BB should be optimized for size. */
266 optimize_insn_for_size_p (void)
268 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
271 /* Return TRUE when BB should be optimized for speed. */
274 optimize_insn_for_speed_p (void)
276 return !optimize_insn_for_size_p ();
279 /* Return TRUE when LOOP should be optimized for size. */
282 optimize_loop_for_size_p (struct loop
*loop
)
284 return optimize_bb_for_size_p (loop
->header
);
287 /* Return TRUE when LOOP should be optimized for speed. */
290 optimize_loop_for_speed_p (struct loop
*loop
)
292 return optimize_bb_for_speed_p (loop
->header
);
295 /* Return TRUE when LOOP nest should be optimized for speed. */
298 optimize_loop_nest_for_speed_p (struct loop
*loop
)
300 struct loop
*l
= loop
;
301 if (optimize_loop_for_speed_p (loop
))
304 while (l
&& l
!= loop
)
306 if (optimize_loop_for_speed_p (l
))
314 while (l
!= loop
&& !l
->next
)
323 /* Return TRUE when LOOP nest should be optimized for size. */
326 optimize_loop_nest_for_size_p (struct loop
*loop
)
328 return !optimize_loop_nest_for_speed_p (loop
);
331 /* Return true when edge E is likely to be well predictable by branch
335 predictable_edge_p (edge e
)
337 if (profile_status
== PROFILE_ABSENT
)
340 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
341 || (REG_BR_PROB_BASE
- e
->probability
342 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
348 /* Set RTL expansion for BB profile. */
351 rtl_profile_for_bb (basic_block bb
)
353 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (bb
);
356 /* Set RTL expansion for edge profile. */
359 rtl_profile_for_edge (edge e
)
361 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
364 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
366 default_rtl_profile (void)
368 crtl
->maybe_hot_insn_p
= true;
371 /* Return true if the one of outgoing edges is already predicted by
375 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
378 if (!INSN_P (BB_END (bb
)))
380 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
381 if (REG_NOTE_KIND (note
) == REG_BR_PRED
382 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
387 /* This map contains for a basic block the list of predictions for the
390 static struct pointer_map_t
*bb_predictions
;
392 /* Return true if the one of outgoing edges is already predicted by
396 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
398 struct edge_prediction
*i
;
399 void **preds
= pointer_map_contains (bb_predictions
, bb
);
404 for (i
= (struct edge_prediction
*) *preds
; i
; i
= i
->ep_next
)
405 if (i
->ep_predictor
== predictor
)
410 /* Return true when the probability of edge is reliable.
412 The profile guessing code is good at predicting branch outcome (ie.
413 taken/not taken), that is predicted right slightly over 75% of time.
414 It is however notoriously poor on predicting the probability itself.
415 In general the profile appear a lot flatter (with probabilities closer
416 to 50%) than the reality so it is bad idea to use it to drive optimization
417 such as those disabling dynamic branch prediction for well predictable
420 There are two exceptions - edges leading to noreturn edges and edges
421 predicted by number of iterations heuristics are predicted well. This macro
422 should be able to distinguish those, but at the moment it simply check for
423 noreturn heuristic that is only one giving probability over 99% or bellow
424 1%. In future we might want to propagate reliability information across the
425 CFG if we find this information useful on multiple places. */
427 probability_reliable_p (int prob
)
429 return (profile_status
== PROFILE_READ
430 || (profile_status
== PROFILE_GUESSED
431 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
434 /* Same predicate as above, working on edges. */
436 edge_probability_reliable_p (const_edge e
)
438 return probability_reliable_p (e
->probability
);
441 /* Same predicate as edge_probability_reliable_p, working on notes. */
443 br_prob_note_reliable_p (const_rtx note
)
445 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
446 return probability_reliable_p (INTVAL (XEXP (note
, 0)));
450 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
452 gcc_assert (any_condjump_p (insn
));
453 if (!flag_guess_branch_prob
)
456 add_reg_note (insn
, REG_BR_PRED
,
457 gen_rtx_CONCAT (VOIDmode
,
458 GEN_INT ((int) predictor
),
459 GEN_INT ((int) probability
)));
462 /* Predict insn by given predictor. */
465 predict_insn_def (rtx insn
, enum br_predictor predictor
,
466 enum prediction taken
)
468 int probability
= predictor_info
[(int) predictor
].hitrate
;
471 probability
= REG_BR_PROB_BASE
- probability
;
473 predict_insn (insn
, predictor
, probability
);
476 /* Predict edge E with given probability if possible. */
479 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
482 last_insn
= BB_END (e
->src
);
484 /* We can store the branch prediction information only about
485 conditional jumps. */
486 if (!any_condjump_p (last_insn
))
489 /* We always store probability of branching. */
490 if (e
->flags
& EDGE_FALLTHRU
)
491 probability
= REG_BR_PROB_BASE
- probability
;
493 predict_insn (last_insn
, predictor
, probability
);
496 /* Predict edge E with the given PROBABILITY. */
498 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
500 gcc_assert (profile_status
!= PROFILE_GUESSED
);
501 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
502 && flag_guess_branch_prob
&& optimize
)
504 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
505 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
507 i
->ep_next
= (struct edge_prediction
*) *preds
;
509 i
->ep_probability
= probability
;
510 i
->ep_predictor
= predictor
;
515 /* Remove all predictions on given basic block that are attached
518 remove_predictions_associated_with_edge (edge e
)
525 preds
= pointer_map_contains (bb_predictions
, e
->src
);
529 struct edge_prediction
**prediction
= (struct edge_prediction
**) preds
;
530 struct edge_prediction
*next
;
534 if ((*prediction
)->ep_edge
== e
)
536 next
= (*prediction
)->ep_next
;
541 prediction
= &((*prediction
)->ep_next
);
546 /* Clears the list of predictions stored for BB. */
549 clear_bb_predictions (basic_block bb
)
551 void **preds
= pointer_map_contains (bb_predictions
, bb
);
552 struct edge_prediction
*pred
, *next
;
557 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= next
)
559 next
= pred
->ep_next
;
565 /* Return true when we can store prediction on insn INSN.
566 At the moment we represent predictions only on conditional
567 jumps, not at computed jump or other complicated cases. */
569 can_predict_insn_p (const_rtx insn
)
571 return (JUMP_P (insn
)
572 && any_condjump_p (insn
)
573 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
576 /* Predict edge E by given predictor if possible. */
579 predict_edge_def (edge e
, enum br_predictor predictor
,
580 enum prediction taken
)
582 int probability
= predictor_info
[(int) predictor
].hitrate
;
585 probability
= REG_BR_PROB_BASE
- probability
;
587 predict_edge (e
, predictor
, probability
);
590 /* Invert all branch predictions or probability notes in the INSN. This needs
591 to be done each time we invert the condition used by the jump. */
594 invert_br_probabilities (rtx insn
)
598 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
599 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
600 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
601 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
602 XEXP (XEXP (note
, 0), 1)
603 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
606 /* Dump information about the branch prediction to the output file. */
609 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
610 basic_block bb
, int used
)
618 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
619 if (! (e
->flags
& EDGE_FALLTHRU
))
622 fprintf (file
, " %s heuristics%s: %.1f%%",
623 predictor_info
[predictor
].name
,
624 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
628 fprintf (file
, " exec ");
629 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
632 fprintf (file
, " hit ");
633 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
634 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
638 fprintf (file
, "\n");
641 /* We can not predict the probabilities of outgoing edges of bb. Set them
642 evenly and hope for the best. */
644 set_even_probabilities (basic_block bb
)
650 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
651 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
653 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
654 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
655 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
660 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
661 note if not already present. Remove now useless REG_BR_PRED notes. */
664 combine_predictions_for_insn (rtx insn
, basic_block bb
)
669 int best_probability
= PROB_EVEN
;
670 enum br_predictor best_predictor
= END_PREDICTORS
;
671 int combined_probability
= REG_BR_PROB_BASE
/ 2;
673 bool first_match
= false;
676 if (!can_predict_insn_p (insn
))
678 set_even_probabilities (bb
);
682 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
683 pnote
= ®_NOTES (insn
);
685 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
688 /* We implement "first match" heuristics and use probability guessed
689 by predictor with smallest index. */
690 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
691 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
693 enum br_predictor predictor
= ((enum br_predictor
)
694 INTVAL (XEXP (XEXP (note
, 0), 0)));
695 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
698 if (best_predictor
> predictor
)
699 best_probability
= probability
, best_predictor
= predictor
;
701 d
= (combined_probability
* probability
702 + (REG_BR_PROB_BASE
- combined_probability
)
703 * (REG_BR_PROB_BASE
- probability
));
705 /* Use FP math to avoid overflows of 32bit integers. */
707 /* If one probability is 0% and one 100%, avoid division by zero. */
708 combined_probability
= REG_BR_PROB_BASE
/ 2;
710 combined_probability
= (((double) combined_probability
) * probability
711 * REG_BR_PROB_BASE
/ d
+ 0.5);
714 /* Decide which heuristic to use. In case we didn't match anything,
715 use no_prediction heuristic, in case we did match, use either
716 first match or Dempster-Shaffer theory depending on the flags. */
718 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
722 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
723 combined_probability
, bb
, true);
726 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
728 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
733 combined_probability
= best_probability
;
734 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
738 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
740 enum br_predictor predictor
= ((enum br_predictor
)
741 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
742 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
744 dump_prediction (dump_file
, predictor
, probability
, bb
,
745 !first_match
|| best_predictor
== predictor
);
746 *pnote
= XEXP (*pnote
, 1);
749 pnote
= &XEXP (*pnote
, 1);
754 add_reg_note (insn
, REG_BR_PROB
, GEN_INT (combined_probability
));
756 /* Save the prediction into CFG in case we are seeing non-degenerated
758 if (!single_succ_p (bb
))
760 BRANCH_EDGE (bb
)->probability
= combined_probability
;
761 FALLTHRU_EDGE (bb
)->probability
762 = REG_BR_PROB_BASE
- combined_probability
;
765 else if (!single_succ_p (bb
))
767 int prob
= INTVAL (XEXP (prob_note
, 0));
769 BRANCH_EDGE (bb
)->probability
= prob
;
770 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
773 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
776 /* Combine predictions into single probability and store them into CFG.
777 Remove now useless prediction entries. */
780 combine_predictions_for_bb (basic_block bb
)
782 int best_probability
= PROB_EVEN
;
783 enum br_predictor best_predictor
= END_PREDICTORS
;
784 int combined_probability
= REG_BR_PROB_BASE
/ 2;
786 bool first_match
= false;
788 struct edge_prediction
*pred
;
790 edge e
, first
= NULL
, second
= NULL
;
794 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
795 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
798 if (first
&& !second
)
804 /* When there is no successor or only one choice, prediction is easy.
806 We are lazy for now and predict only basic blocks with two outgoing
807 edges. It is possible to predict generic case too, but we have to
808 ignore first match heuristics and do more involved combining. Implement
813 set_even_probabilities (bb
);
814 clear_bb_predictions (bb
);
816 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
822 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
824 preds
= pointer_map_contains (bb_predictions
, bb
);
827 /* We implement "first match" heuristics and use probability guessed
828 by predictor with smallest index. */
829 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
831 enum br_predictor predictor
= pred
->ep_predictor
;
832 int probability
= pred
->ep_probability
;
834 if (pred
->ep_edge
!= first
)
835 probability
= REG_BR_PROB_BASE
- probability
;
838 /* First match heuristics would be widly confused if we predicted
840 if (best_predictor
> predictor
)
842 struct edge_prediction
*pred2
;
843 int prob
= probability
;
845 for (pred2
= (struct edge_prediction
*) *preds
; pred2
; pred2
= pred2
->ep_next
)
846 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
848 int probability2
= pred
->ep_probability
;
850 if (pred2
->ep_edge
!= first
)
851 probability2
= REG_BR_PROB_BASE
- probability2
;
853 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
854 (probability2
< REG_BR_PROB_BASE
/ 2))
857 /* If the same predictor later gave better result, go for it! */
858 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
859 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
863 best_probability
= prob
, best_predictor
= predictor
;
866 d
= (combined_probability
* probability
867 + (REG_BR_PROB_BASE
- combined_probability
)
868 * (REG_BR_PROB_BASE
- probability
));
870 /* Use FP math to avoid overflows of 32bit integers. */
872 /* If one probability is 0% and one 100%, avoid division by zero. */
873 combined_probability
= REG_BR_PROB_BASE
/ 2;
875 combined_probability
= (((double) combined_probability
)
877 * REG_BR_PROB_BASE
/ d
+ 0.5);
881 /* Decide which heuristic to use. In case we didn't match anything,
882 use no_prediction heuristic, in case we did match, use either
883 first match or Dempster-Shaffer theory depending on the flags. */
885 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
889 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
892 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
894 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
899 combined_probability
= best_probability
;
900 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
904 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
906 enum br_predictor predictor
= pred
->ep_predictor
;
907 int probability
= pred
->ep_probability
;
909 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
910 probability
= REG_BR_PROB_BASE
- probability
;
911 dump_prediction (dump_file
, predictor
, probability
, bb
,
912 !first_match
|| best_predictor
== predictor
);
915 clear_bb_predictions (bb
);
919 first
->probability
= combined_probability
;
920 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
924 /* Predict edge probabilities by exploiting loop structure. */
932 /* Try to predict out blocks in a loop that are not part of a
934 FOR_EACH_LOOP (li
, loop
, 0)
936 basic_block bb
, *bbs
;
938 VEC (edge
, heap
) *exits
;
939 struct tree_niter_desc niter_desc
;
942 exits
= get_loop_exit_edges (loop
);
943 n_exits
= VEC_length (edge
, exits
);
945 FOR_EACH_VEC_ELT (edge
, exits
, j
, ex
)
948 HOST_WIDE_INT nitercst
;
949 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
951 enum br_predictor predictor
;
953 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
954 niter
= niter_desc
.niter
;
955 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
956 niter
= loop_niter_by_eval (loop
, ex
);
958 if (TREE_CODE (niter
) == INTEGER_CST
)
960 if (host_integerp (niter
, 1)
961 && compare_tree_int (niter
, max
-1) == -1)
962 nitercst
= tree_low_cst (niter
, 1) + 1;
965 predictor
= PRED_LOOP_ITERATIONS
;
967 /* If we have just one exit and we can derive some information about
968 the number of iterations of the loop from the statements inside
969 the loop, use it to predict this exit. */
970 else if (n_exits
== 1)
972 nitercst
= estimated_loop_iterations_int (loop
, false);
978 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
983 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
984 predict_edge (ex
, predictor
, probability
);
986 VEC_free (edge
, heap
, exits
);
988 bbs
= get_loop_body (loop
);
990 for (j
= 0; j
< loop
->num_nodes
; j
++)
992 int header_found
= 0;
998 /* Bypass loop heuristics on continue statement. These
999 statements construct loops via "non-loop" constructs
1000 in the source language and are better to be handled
1002 if (predicted_by_p (bb
, PRED_CONTINUE
))
1005 /* Loop branch heuristics - predict an edge back to a
1006 loop's head as taken. */
1007 if (bb
== loop
->latch
)
1009 e
= find_edge (loop
->latch
, loop
->header
);
1013 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1017 /* Loop exit heuristics - predict an edge exiting the loop if the
1018 conditional has no loop header successors as not taken. */
1020 /* If we already used more reliable loop exit predictors, do not
1021 bother with PRED_LOOP_EXIT. */
1022 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1023 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1025 /* For loop with many exits we don't want to predict all exits
1026 with the pretty large probability, because if all exits are
1027 considered in row, the loop would be predicted to iterate
1028 almost never. The code to divide probability by number of
1029 exits is very rough. It should compute the number of exits
1030 taken in each patch through function (not the overall number
1031 of exits that might be a lot higher for loops with wide switch
1032 statements in them) and compute n-th square root.
1034 We limit the minimal probability by 2% to avoid
1035 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1036 as this was causing regression in perl benchmark containing such
1039 int probability
= ((REG_BR_PROB_BASE
1040 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1042 if (probability
< HITRATE (2))
1043 probability
= HITRATE (2);
1044 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1045 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1046 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1047 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1051 /* Free basic blocks from get_loop_body. */
1056 /* Attempt to predict probabilities of BB outgoing edges using local
1059 bb_estimate_probability_locally (basic_block bb
)
1061 rtx last_insn
= BB_END (bb
);
1064 if (! can_predict_insn_p (last_insn
))
1066 cond
= get_condition (last_insn
, NULL
, false, false);
1070 /* Try "pointer heuristic."
1071 A comparison ptr == 0 is predicted as false.
1072 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1073 if (COMPARISON_P (cond
)
1074 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1075 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1077 if (GET_CODE (cond
) == EQ
)
1078 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1079 else if (GET_CODE (cond
) == NE
)
1080 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1084 /* Try "opcode heuristic."
1085 EQ tests are usually false and NE tests are usually true. Also,
1086 most quantities are positive, so we can make the appropriate guesses
1087 about signed comparisons against zero. */
1088 switch (GET_CODE (cond
))
1091 /* Unconditional branch. */
1092 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1093 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1098 /* Floating point comparisons appears to behave in a very
1099 unpredictable way because of special role of = tests in
1101 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1103 /* Comparisons with 0 are often used for booleans and there is
1104 nothing useful to predict about them. */
1105 else if (XEXP (cond
, 1) == const0_rtx
1106 || XEXP (cond
, 0) == const0_rtx
)
1109 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1114 /* Floating point comparisons appears to behave in a very
1115 unpredictable way because of special role of = tests in
1117 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1119 /* Comparisons with 0 are often used for booleans and there is
1120 nothing useful to predict about them. */
1121 else if (XEXP (cond
, 1) == const0_rtx
1122 || XEXP (cond
, 0) == const0_rtx
)
1125 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1129 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1133 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1138 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1139 || XEXP (cond
, 1) == constm1_rtx
)
1140 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1145 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1146 || XEXP (cond
, 1) == constm1_rtx
)
1147 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1155 /* Set edge->probability for each successor edge of BB. */
1157 guess_outgoing_edge_probabilities (basic_block bb
)
1159 bb_estimate_probability_locally (bb
);
1160 combine_predictions_for_insn (BB_END (bb
), bb
);
1163 static tree
expr_expected_value (tree
, bitmap
);
1165 /* Helper function for expr_expected_value. */
1168 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
, tree op1
, bitmap visited
)
1172 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1174 if (TREE_CONSTANT (op0
))
1177 if (code
!= SSA_NAME
)
1180 def
= SSA_NAME_DEF_STMT (op0
);
1182 /* If we were already here, break the infinite cycle. */
1183 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1186 if (gimple_code (def
) == GIMPLE_PHI
)
1188 /* All the arguments of the PHI node must have the same constant
1190 int i
, n
= gimple_phi_num_args (def
);
1191 tree val
= NULL
, new_val
;
1193 for (i
= 0; i
< n
; i
++)
1195 tree arg
= PHI_ARG_DEF (def
, i
);
1197 /* If this PHI has itself as an argument, we cannot
1198 determine the string length of this argument. However,
1199 if we can find an expected constant value for the other
1200 PHI args then we can still be sure that this is
1201 likely a constant. So be optimistic and just
1202 continue with the next argument. */
1203 if (arg
== PHI_RESULT (def
))
1206 new_val
= expr_expected_value (arg
, visited
);
1211 else if (!operand_equal_p (val
, new_val
, false))
1216 if (is_gimple_assign (def
))
1218 if (gimple_assign_lhs (def
) != op0
)
1221 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1222 gimple_assign_rhs1 (def
),
1223 gimple_assign_rhs_code (def
),
1224 gimple_assign_rhs2 (def
),
1228 if (is_gimple_call (def
))
1230 tree decl
= gimple_call_fndecl (def
);
1233 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
1234 && DECL_FUNCTION_CODE (decl
) == BUILT_IN_EXPECT
)
1238 if (gimple_call_num_args (def
) != 2)
1240 val
= gimple_call_arg (def
, 0);
1241 if (TREE_CONSTANT (val
))
1243 return gimple_call_arg (def
, 1);
1250 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1253 op0
= expr_expected_value (op0
, visited
);
1256 op1
= expr_expected_value (op1
, visited
);
1259 res
= fold_build2 (code
, type
, op0
, op1
);
1260 if (TREE_CONSTANT (res
))
1264 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1267 op0
= expr_expected_value (op0
, visited
);
1270 res
= fold_build1 (code
, type
, op0
);
1271 if (TREE_CONSTANT (res
))
1278 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1279 The function is used by builtin_expect branch predictor so the evidence
1280 must come from this construct and additional possible constant folding.
1282 We may want to implement more involved value guess (such as value range
1283 propagation based prediction), but such tricks shall go to new
1287 expr_expected_value (tree expr
, bitmap visited
)
1289 enum tree_code code
;
1292 if (TREE_CONSTANT (expr
))
1295 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1296 return expr_expected_value_1 (TREE_TYPE (expr
),
1297 op0
, code
, op1
, visited
);
1301 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1302 we no longer need. */
1304 strip_predict_hints (void)
1312 gimple_stmt_iterator bi
;
1313 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
1315 gimple stmt
= gsi_stmt (bi
);
1317 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
1319 gsi_remove (&bi
, true);
1322 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1324 tree fndecl
= gimple_call_fndecl (stmt
);
1327 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1328 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1329 && gimple_call_num_args (stmt
) == 2)
1331 var
= gimple_call_lhs (stmt
);
1335 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
1336 gsi_replace (&bi
, ass_stmt
, true);
1340 gsi_remove (&bi
, true);
1351 /* Predict using opcode of the last statement in basic block. */
1353 tree_predict_by_opcode (basic_block bb
)
1355 gimple stmt
= last_stmt (bb
);
1364 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1366 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1367 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1369 op0
= gimple_cond_lhs (stmt
);
1370 op1
= gimple_cond_rhs (stmt
);
1371 cmp
= gimple_cond_code (stmt
);
1372 type
= TREE_TYPE (op0
);
1373 visited
= BITMAP_ALLOC (NULL
);
1374 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
);
1375 BITMAP_FREE (visited
);
1378 if (integer_zerop (val
))
1379 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1381 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1384 /* Try "pointer heuristic."
1385 A comparison ptr == 0 is predicted as false.
1386 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1387 if (POINTER_TYPE_P (type
))
1390 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1391 else if (cmp
== NE_EXPR
)
1392 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1396 /* Try "opcode heuristic."
1397 EQ tests are usually false and NE tests are usually true. Also,
1398 most quantities are positive, so we can make the appropriate guesses
1399 about signed comparisons against zero. */
1404 /* Floating point comparisons appears to behave in a very
1405 unpredictable way because of special role of = tests in
1407 if (FLOAT_TYPE_P (type
))
1409 /* Comparisons with 0 are often used for booleans and there is
1410 nothing useful to predict about them. */
1411 else if (integer_zerop (op0
) || integer_zerop (op1
))
1414 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1419 /* Floating point comparisons appears to behave in a very
1420 unpredictable way because of special role of = tests in
1422 if (FLOAT_TYPE_P (type
))
1424 /* Comparisons with 0 are often used for booleans and there is
1425 nothing useful to predict about them. */
1426 else if (integer_zerop (op0
)
1427 || integer_zerop (op1
))
1430 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1434 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1437 case UNORDERED_EXPR
:
1438 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1443 if (integer_zerop (op1
)
1444 || integer_onep (op1
)
1445 || integer_all_onesp (op1
)
1448 || real_minus_onep (op1
))
1449 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1454 if (integer_zerop (op1
)
1455 || integer_onep (op1
)
1456 || integer_all_onesp (op1
)
1459 || real_minus_onep (op1
))
1460 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1468 /* Try to guess whether the value of return means error code. */
1470 static enum br_predictor
1471 return_prediction (tree val
, enum prediction
*prediction
)
1475 return PRED_NO_PREDICTION
;
1476 /* Different heuristics for pointers and scalars. */
1477 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1479 /* NULL is usually not returned. */
1480 if (integer_zerop (val
))
1482 *prediction
= NOT_TAKEN
;
1483 return PRED_NULL_RETURN
;
1486 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1488 /* Negative return values are often used to indicate
1490 if (TREE_CODE (val
) == INTEGER_CST
1491 && tree_int_cst_sgn (val
) < 0)
1493 *prediction
= NOT_TAKEN
;
1494 return PRED_NEGATIVE_RETURN
;
1496 /* Constant return values seems to be commonly taken.
1497 Zero/one often represent booleans so exclude them from the
1499 if (TREE_CONSTANT (val
)
1500 && (!integer_zerop (val
) && !integer_onep (val
)))
1502 *prediction
= TAKEN
;
1503 return PRED_CONST_RETURN
;
1506 return PRED_NO_PREDICTION
;
1509 /* Find the basic block with return expression and look up for possible
1510 return value trying to apply RETURN_PREDICTION heuristics. */
1512 apply_return_prediction (void)
1514 gimple return_stmt
= NULL
;
1518 int phi_num_args
, i
;
1519 enum br_predictor pred
;
1520 enum prediction direction
;
1523 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1525 return_stmt
= last_stmt (e
->src
);
1527 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
1532 return_val
= gimple_return_retval (return_stmt
);
1535 if (TREE_CODE (return_val
) != SSA_NAME
1536 || !SSA_NAME_DEF_STMT (return_val
)
1537 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
1539 phi
= SSA_NAME_DEF_STMT (return_val
);
1540 phi_num_args
= gimple_phi_num_args (phi
);
1541 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
1543 /* Avoid the degenerate case where all return values form the function
1544 belongs to same category (ie they are all positive constants)
1545 so we can hardly say something about them. */
1546 for (i
= 1; i
< phi_num_args
; i
++)
1547 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
1549 if (i
!= phi_num_args
)
1550 for (i
= 0; i
< phi_num_args
; i
++)
1552 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
1553 if (pred
!= PRED_NO_PREDICTION
)
1554 predict_paths_leading_to (gimple_phi_arg_edge (phi
, i
)->src
, pred
,
1559 /* Look for basic block that contains unlikely to happen events
1560 (such as noreturn calls) and mark all paths leading to execution
1561 of this basic blocks as unlikely. */
1564 tree_bb_level_predictions (void)
1567 bool has_return_edges
= false;
1571 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1572 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
1574 has_return_edges
= true;
1578 apply_return_prediction ();
1582 gimple_stmt_iterator gsi
;
1584 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1586 gimple stmt
= gsi_stmt (gsi
);
1589 if (is_gimple_call (stmt
))
1591 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
1592 && has_return_edges
)
1593 predict_paths_leading_to (bb
, PRED_NORETURN
,
1595 decl
= gimple_call_fndecl (stmt
);
1597 && lookup_attribute ("cold",
1598 DECL_ATTRIBUTES (decl
)))
1599 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
1602 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
1604 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
1605 gimple_predict_outcome (stmt
));
1606 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1607 hints to callers. */
1613 #ifdef ENABLE_CHECKING
1615 /* Callback for pointer_map_traverse, asserts that the pointer map is
1619 assert_is_empty (const void *key ATTRIBUTE_UNUSED
, void **value
,
1620 void *data ATTRIBUTE_UNUSED
)
1622 gcc_assert (!*value
);
1627 /* Predict branch probabilities and estimate profile for basic block BB. */
1630 tree_estimate_probability_bb (basic_block bb
)
1636 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1638 /* Predict early returns to be probable, as we've already taken
1639 care for error returns and other cases are often used for
1640 fast paths through function.
1642 Since we've already removed the return statements, we are
1643 looking for CFG like:
1653 if (e
->dest
!= bb
->next_bb
1654 && e
->dest
!= EXIT_BLOCK_PTR
1655 && single_succ_p (e
->dest
)
1656 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR
1657 && (last
= last_stmt (e
->dest
)) != NULL
1658 && gimple_code (last
) == GIMPLE_RETURN
)
1663 if (single_succ_p (bb
))
1665 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
1666 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
1667 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
1668 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
1669 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1672 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
1673 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
1674 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
1675 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1678 /* Look for block we are guarding (ie we dominate it,
1679 but it doesn't postdominate us). */
1680 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1681 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1682 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1684 gimple_stmt_iterator bi
;
1686 /* The call heuristic claims that a guarded function call
1687 is improbable. This is because such calls are often used
1688 to signal exceptional situations such as printing error
1690 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
1693 gimple stmt
= gsi_stmt (bi
);
1694 if (is_gimple_call (stmt
)
1695 /* Constant and pure calls are hardly used to signalize
1696 something exceptional. */
1697 && gimple_has_side_effects (stmt
))
1699 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1705 tree_predict_by_opcode (bb
);
1708 /* Predict branch probabilities and estimate profile of the tree CFG.
1709 This function can be called from the loop optimizers to recompute
1710 the profile information. */
1713 tree_estimate_probability (void)
1717 add_noreturn_fake_exit_edges ();
1718 connect_infinite_loops_to_exit ();
1719 /* We use loop_niter_by_eval, which requires that the loops have
1721 create_preheaders (CP_SIMPLE_PREHEADERS
);
1722 calculate_dominance_info (CDI_POST_DOMINATORS
);
1724 bb_predictions
= pointer_map_create ();
1725 tree_bb_level_predictions ();
1726 record_loop_exits ();
1728 if (number_of_loops () > 1)
1732 tree_estimate_probability_bb (bb
);
1735 combine_predictions_for_bb (bb
);
1737 #ifdef ENABLE_CHECKING
1738 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
1740 pointer_map_destroy (bb_predictions
);
1741 bb_predictions
= NULL
;
1743 estimate_bb_frequencies ();
1744 free_dominance_info (CDI_POST_DOMINATORS
);
1745 remove_fake_exit_edges ();
1748 /* Predict branch probabilities and estimate profile of the tree CFG.
1749 This is the driver function for PASS_PROFILE. */
1752 tree_estimate_probability_driver (void)
1756 loop_optimizer_init (0);
1757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1758 flow_loops_dump (dump_file
, NULL
, 0);
1760 mark_irreducible_loops ();
1762 nb_loops
= number_of_loops ();
1766 tree_estimate_probability ();
1771 loop_optimizer_finalize ();
1772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1773 gimple_dump_cfg (dump_file
, dump_flags
);
1774 if (profile_status
== PROFILE_ABSENT
)
1775 profile_status
= PROFILE_GUESSED
;
1779 /* Predict edges to successors of CUR whose sources are not postdominated by
1780 BB by PRED and recurse to all postdominators. */
1783 predict_paths_for_bb (basic_block cur
, basic_block bb
,
1784 enum br_predictor pred
,
1785 enum prediction taken
)
1791 /* We are looking for all edges forming edge cut induced by
1792 set of all blocks postdominated by BB. */
1793 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
1794 if (e
->src
->index
>= NUM_FIXED_BLOCKS
1795 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
1801 /* Ignore abnormals, we predict them as not taken anyway. */
1802 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
| EDGE_ABNORMAL
))
1804 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
1806 /* See if there is how many edge from e->src that is not abnormal
1807 and does not lead to BB. */
1808 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
1810 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
| EDGE_ABNORMAL
))
1811 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
1817 /* If there is non-abnormal path leaving e->src, predict edge
1818 using predictor. Otherwise we need to look for paths
1819 leading to e->src. */
1821 predict_edge_def (e
, pred
, taken
);
1823 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
);
1825 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
1827 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1828 predict_paths_for_bb (son
, bb
, pred
, taken
);
1831 /* Sets branch probabilities according to PREDiction and
1835 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
1836 enum prediction taken
)
1838 predict_paths_for_bb (bb
, bb
, pred
, taken
);
1841 /* This is used to carry information about basic blocks. It is
1842 attached to the AUX field of the standard CFG block. */
1844 typedef struct block_info_def
1846 /* Estimated frequency of execution of basic_block. */
1849 /* To keep queue of basic blocks to process. */
1852 /* Number of predecessors we need to visit first. */
1856 /* Similar information for edges. */
1857 typedef struct edge_info_def
1859 /* In case edge is a loopback edge, the probability edge will be reached
1860 in case header is. Estimated number of iterations of the loop can be
1861 then computed as 1 / (1 - back_edge_prob). */
1862 sreal back_edge_prob
;
1863 /* True if the edge is a loopback edge in the natural loop. */
1864 unsigned int back_edge
:1;
1867 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1868 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1870 /* Helper function for estimate_bb_frequencies.
1871 Propagate the frequencies in blocks marked in
1872 TOVISIT, starting in HEAD. */
1875 propagate_freq (basic_block head
, bitmap tovisit
)
1884 /* For each basic block we need to visit count number of his predecessors
1885 we need to visit first. */
1886 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
1891 bb
= BASIC_BLOCK (i
);
1893 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1895 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
1897 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
1899 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
1901 "Irreducible region hit, ignoring edge to %i->%i\n",
1902 e
->src
->index
, bb
->index
);
1904 BLOCK_INFO (bb
)->npredecessors
= count
;
1905 /* When function never returns, we will never process exit block. */
1906 if (!count
&& bb
== EXIT_BLOCK_PTR
)
1907 bb
->count
= bb
->frequency
= 0;
1910 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1912 for (bb
= head
; bb
; bb
= nextbb
)
1915 sreal cyclic_probability
, frequency
;
1917 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1918 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1920 nextbb
= BLOCK_INFO (bb
)->next
;
1921 BLOCK_INFO (bb
)->next
= NULL
;
1923 /* Compute frequency of basic block. */
1926 #ifdef ENABLE_CHECKING
1927 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1928 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
1929 || (e
->flags
& EDGE_DFS_BACK
));
1932 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1933 if (EDGE_INFO (e
)->back_edge
)
1935 sreal_add (&cyclic_probability
, &cyclic_probability
,
1936 &EDGE_INFO (e
)->back_edge_prob
);
1938 else if (!(e
->flags
& EDGE_DFS_BACK
))
1942 /* frequency += (e->probability
1943 * BLOCK_INFO (e->src)->frequency /
1944 REG_BR_PROB_BASE); */
1946 sreal_init (&tmp
, e
->probability
, 0);
1947 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1948 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1949 sreal_add (&frequency
, &frequency
, &tmp
);
1952 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1954 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1955 sizeof (frequency
));
1959 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1961 memcpy (&cyclic_probability
, &real_almost_one
,
1962 sizeof (real_almost_one
));
1965 /* BLOCK_INFO (bb)->frequency = frequency
1966 / (1 - cyclic_probability) */
1968 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1969 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1970 &frequency
, &cyclic_probability
);
1974 bitmap_clear_bit (tovisit
, bb
->index
);
1976 e
= find_edge (bb
, head
);
1981 /* EDGE_INFO (e)->back_edge_prob
1982 = ((e->probability * BLOCK_INFO (bb)->frequency)
1983 / REG_BR_PROB_BASE); */
1985 sreal_init (&tmp
, e
->probability
, 0);
1986 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1987 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1988 &tmp
, &real_inv_br_prob_base
);
1991 /* Propagate to successor blocks. */
1992 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1993 if (!(e
->flags
& EDGE_DFS_BACK
)
1994 && BLOCK_INFO (e
->dest
)->npredecessors
)
1996 BLOCK_INFO (e
->dest
)->npredecessors
--;
1997 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2002 BLOCK_INFO (last
)->next
= e
->dest
;
2010 /* Estimate probabilities of loopback edges in loops at same nest level. */
2013 estimate_loops_at_level (struct loop
*first_loop
)
2017 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2022 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2024 estimate_loops_at_level (loop
->inner
);
2026 /* Find current loop back edge and mark it. */
2027 e
= loop_latch_edge (loop
);
2028 EDGE_INFO (e
)->back_edge
= 1;
2030 bbs
= get_loop_body (loop
);
2031 for (i
= 0; i
< loop
->num_nodes
; i
++)
2032 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2034 propagate_freq (loop
->header
, tovisit
);
2035 BITMAP_FREE (tovisit
);
2039 /* Propagates frequencies through structure of loops. */
2042 estimate_loops (void)
2044 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2047 /* Start by estimating the frequencies in the loops. */
2048 if (number_of_loops () > 1)
2049 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2051 /* Now propagate the frequencies through all the blocks. */
2054 bitmap_set_bit (tovisit
, bb
->index
);
2056 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
2057 BITMAP_FREE (tovisit
);
2060 /* Convert counts measured by profile driven feedback to frequencies.
2061 Return nonzero iff there was any nonzero execution count. */
2064 counts_to_freqs (void)
2066 gcov_type count_max
, true_count_max
= 0;
2069 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2070 true_count_max
= MAX (bb
->count
, true_count_max
);
2072 count_max
= MAX (true_count_max
, 1);
2073 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2074 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2076 return true_count_max
;
2079 /* Return true if function is likely to be expensive, so there is no point to
2080 optimize performance of prologue, epilogue or do inlining at the expense
2081 of code size growth. THRESHOLD is the limit of number of instructions
2082 function can execute at average to be still considered not expensive. */
2085 expensive_function_p (int threshold
)
2087 unsigned int sum
= 0;
2091 /* We can not compute accurately for large thresholds due to scaled
2093 gcc_assert (threshold
<= BB_FREQ_MAX
);
2095 /* Frequencies are out of range. This either means that function contains
2096 internal loop executing more than BB_FREQ_MAX times or profile feedback
2097 is available and function has not been executed at all. */
2098 if (ENTRY_BLOCK_PTR
->frequency
== 0)
2101 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2102 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
2107 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
2108 insn
= NEXT_INSN (insn
))
2109 if (active_insn_p (insn
))
2111 sum
+= bb
->frequency
;
2120 /* Estimate basic blocks frequency by given branch probabilities. */
2123 estimate_bb_frequencies (void)
2128 if (profile_status
!= PROFILE_READ
|| !counts_to_freqs ())
2130 static int real_values_initialized
= 0;
2132 if (!real_values_initialized
)
2134 real_values_initialized
= 1;
2135 sreal_init (&real_zero
, 0, 0);
2136 sreal_init (&real_one
, 1, 0);
2137 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2138 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2139 sreal_init (&real_one_half
, 1, -1);
2140 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2141 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2144 mark_dfs_back_edges ();
2146 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
2148 /* Set up block info for each basic block. */
2149 alloc_aux_for_blocks (sizeof (struct block_info_def
));
2150 alloc_aux_for_edges (sizeof (struct edge_info_def
));
2151 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2156 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2158 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2159 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2160 &EDGE_INFO (e
)->back_edge_prob
,
2161 &real_inv_br_prob_base
);
2165 /* First compute probabilities locally for each loop from innermost
2166 to outermost to examine probabilities for back edges. */
2169 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2171 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2172 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2174 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
2175 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2179 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
2180 sreal_add (&tmp
, &tmp
, &real_one_half
);
2181 bb
->frequency
= sreal_to_int (&tmp
);
2184 free_aux_for_blocks ();
2185 free_aux_for_edges ();
2187 compute_function_frequency ();
2188 if (flag_reorder_functions
)
2189 choose_function_section ();
2192 /* Decide whether function is hot, cold or unlikely executed. */
2194 compute_function_frequency (void)
2197 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
2198 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2199 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2200 node
->only_called_at_startup
= true;
2201 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
2202 node
->only_called_at_exit
= true;
2204 if (!profile_info
|| !flag_branch_probabilities
)
2206 int flags
= flags_from_decl_or_type (current_function_decl
);
2207 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2209 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2210 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
2212 node
->frequency
= NODE_FREQUENCY_HOT
;
2213 else if (flags
& ECF_NORETURN
)
2214 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2215 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2216 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2217 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2218 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
2219 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2222 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2225 if (maybe_hot_bb_p (bb
))
2227 node
->frequency
= NODE_FREQUENCY_HOT
;
2230 if (!probably_never_executed_bb_p (bb
))
2231 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2235 /* Choose appropriate section for the function. */
2237 choose_function_section (void)
2239 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
2240 if (DECL_SECTION_NAME (current_function_decl
)
2241 || !targetm
.have_named_sections
2242 /* Theoretically we can split the gnu.linkonce text section too,
2243 but this requires more work as the frequency needs to match
2244 for all generated objects so we need to merge the frequency
2245 of all instances. For now just never set frequency for these. */
2246 || DECL_ONE_ONLY (current_function_decl
))
2249 /* If we are doing the partitioning optimization, let the optimization
2250 choose the correct section into which to put things. */
2252 if (flag_reorder_blocks_and_partition
)
2255 if (node
->frequency
== NODE_FREQUENCY_HOT
)
2256 DECL_SECTION_NAME (current_function_decl
) =
2257 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
2258 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
2259 DECL_SECTION_NAME (current_function_decl
) =
2260 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
2261 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
2265 gate_estimate_probability (void)
2267 return flag_guess_branch_prob
;
2270 /* Build PREDICT_EXPR. */
2272 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
2274 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
2275 build_int_cst (NULL
, predictor
));
2276 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
2281 predictor_name (enum br_predictor predictor
)
2283 return predictor_info
[predictor
].name
;
2286 struct gimple_opt_pass pass_profile
=
2290 "profile", /* name */
2291 gate_estimate_probability
, /* gate */
2292 tree_estimate_probability_driver
, /* execute */
2295 0, /* static_pass_number */
2296 TV_BRANCH_PROB
, /* tv_id */
2297 PROP_cfg
, /* properties_required */
2298 0, /* properties_provided */
2299 0, /* properties_destroyed */
2300 0, /* todo_flags_start */
2301 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
2305 struct gimple_opt_pass pass_strip_predict_hints
=
2309 "*strip_predict_hints", /* name */
2311 strip_predict_hints
, /* execute */
2314 0, /* static_pass_number */
2315 TV_BRANCH_PROB
, /* tv_id */
2316 PROP_cfg
, /* properties_required */
2317 0, /* properties_provided */
2318 0, /* properties_destroyed */
2319 0, /* todo_flags_start */
2320 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
2324 /* Rebuild function frequencies. Passes are in general expected to
2325 maintain profile by hand, however in some cases this is not possible:
2326 for example when inlining several functions with loops freuqencies might run
2327 out of scale and thus needs to be recomputed. */
2330 rebuild_frequencies (void)
2332 if (profile_status
== PROFILE_GUESSED
)
2334 loop_optimizer_init (0);
2335 add_noreturn_fake_exit_edges ();
2336 mark_irreducible_loops ();
2337 connect_infinite_loops_to_exit ();
2338 estimate_bb_frequencies ();
2339 remove_fake_exit_edges ();
2340 loop_optimizer_finalize ();
2342 else if (profile_status
== PROFILE_READ
)