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"
55 #include "tree-flow.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
60 #include "tree-scalar-evolution.h"
62 #include "pointer-set.h"
64 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
65 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
66 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
67 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
69 /* Random guesstimation given names.
70 PROV_VERY_UNLIKELY should be small enough so basic block predicted
71 by it gets bellow HOT_BB_FREQUENCY_FRANCTION. */
72 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
73 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
74 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
75 #define PROB_ALWAYS (REG_BR_PROB_BASE)
77 static void combine_predictions_for_insn (rtx
, basic_block
);
78 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
79 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
80 static void choose_function_section (void);
81 static bool can_predict_insn_p (const_rtx
);
83 /* Information we hold about each branch predictor.
84 Filled using information from predict.def. */
88 const char *const name
; /* Name used in the debugging dumps. */
89 const int hitrate
; /* Expected hitrate used by
90 predict_insn_def call. */
94 /* Use given predictor without Dempster-Shaffer theory if it matches
95 using first_match heuristics. */
96 #define PRED_FLAG_FIRST_MATCH 1
98 /* Recompute hitrate in percent to our representation. */
100 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
102 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
103 static const struct predictor_info predictor_info
[]= {
104 #include "predict.def"
106 /* Upper bound on predictors. */
111 /* Return TRUE if frequency FREQ is considered to be hot. */
114 maybe_hot_frequency_p (int freq
)
116 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
117 if (!profile_info
|| !flag_branch_probabilities
)
119 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
121 if (node
->frequency
== NODE_FREQUENCY_HOT
)
124 if (profile_status
== PROFILE_ABSENT
)
126 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
127 && freq
<= (ENTRY_BLOCK_PTR
->frequency
* 2 / 3))
129 if (freq
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
134 /* Return TRUE if frequency FREQ is considered to be hot. */
137 maybe_hot_count_p (gcov_type count
)
139 if (profile_status
!= PROFILE_READ
)
141 /* Code executed at most once is not hot. */
142 if (profile_info
->runs
>= count
)
145 > profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
));
148 /* Return true in case BB can be CPU intensive and should be optimized
149 for maximal performance. */
152 maybe_hot_bb_p (const_basic_block bb
)
154 if (profile_status
== PROFILE_READ
)
155 return maybe_hot_count_p (bb
->count
);
156 return maybe_hot_frequency_p (bb
->frequency
);
159 /* Return true if the call can be hot. */
162 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
164 if (profile_info
&& flag_branch_probabilities
166 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
168 if (edge
->caller
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
169 || edge
->callee
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
171 if (edge
->caller
->frequency
> NODE_FREQUENCY_UNLIKELY_EXECUTED
172 && edge
->callee
->frequency
<= NODE_FREQUENCY_EXECUTED_ONCE
)
176 if (edge
->caller
->frequency
== NODE_FREQUENCY_HOT
)
178 if (edge
->caller
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
179 && edge
->frequency
< CGRAPH_FREQ_BASE
* 3 / 2)
181 if (flag_guess_branch_prob
182 && edge
->frequency
<= (CGRAPH_FREQ_BASE
183 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
188 /* Return true in case BB can be CPU intensive and should be optimized
189 for maximal performance. */
192 maybe_hot_edge_p (edge e
)
194 if (profile_status
== PROFILE_READ
)
195 return maybe_hot_count_p (e
->count
);
196 return maybe_hot_frequency_p (EDGE_FREQUENCY (e
));
199 /* Return true in case BB is probably never executed. */
201 probably_never_executed_bb_p (const_basic_block bb
)
203 if (profile_info
&& flag_branch_probabilities
)
204 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
205 if ((!profile_info
|| !flag_branch_probabilities
)
206 && cgraph_node (current_function_decl
)->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
211 /* Return true when current function should always be optimized for size. */
214 optimize_function_for_size_p (struct function
*fun
)
216 return (optimize_size
218 && (cgraph_node (fun
->decl
)->frequency
219 == NODE_FREQUENCY_UNLIKELY_EXECUTED
)));
222 /* Return true when current function should always be optimized for speed. */
225 optimize_function_for_speed_p (struct function
*fun
)
227 return !optimize_function_for_size_p (fun
);
230 /* Return TRUE when BB should be optimized for size. */
233 optimize_bb_for_size_p (const_basic_block bb
)
235 return optimize_function_for_size_p (cfun
) || !maybe_hot_bb_p (bb
);
238 /* Return TRUE when BB should be optimized for speed. */
241 optimize_bb_for_speed_p (const_basic_block bb
)
243 return !optimize_bb_for_size_p (bb
);
246 /* Return TRUE when BB should be optimized for size. */
249 optimize_edge_for_size_p (edge e
)
251 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
254 /* Return TRUE when BB should be optimized for speed. */
257 optimize_edge_for_speed_p (edge e
)
259 return !optimize_edge_for_size_p (e
);
262 /* Return TRUE when BB should be optimized for size. */
265 optimize_insn_for_size_p (void)
267 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
270 /* Return TRUE when BB should be optimized for speed. */
273 optimize_insn_for_speed_p (void)
275 return !optimize_insn_for_size_p ();
278 /* Return TRUE when LOOP should be optimized for size. */
281 optimize_loop_for_size_p (struct loop
*loop
)
283 return optimize_bb_for_size_p (loop
->header
);
286 /* Return TRUE when LOOP should be optimized for speed. */
289 optimize_loop_for_speed_p (struct loop
*loop
)
291 return optimize_bb_for_speed_p (loop
->header
);
294 /* Return TRUE when LOOP nest should be optimized for speed. */
297 optimize_loop_nest_for_speed_p (struct loop
*loop
)
299 struct loop
*l
= loop
;
300 if (optimize_loop_for_speed_p (loop
))
303 while (l
&& l
!= loop
)
305 if (optimize_loop_for_speed_p (l
))
313 while (l
!= loop
&& !l
->next
)
322 /* Return TRUE when LOOP nest should be optimized for size. */
325 optimize_loop_nest_for_size_p (struct loop
*loop
)
327 return !optimize_loop_nest_for_speed_p (loop
);
330 /* Return true when edge E is likely to be well predictable by branch
334 predictable_edge_p (edge e
)
336 if (profile_status
== PROFILE_ABSENT
)
339 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
340 || (REG_BR_PROB_BASE
- e
->probability
341 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
347 /* Set RTL expansion for BB profile. */
350 rtl_profile_for_bb (basic_block bb
)
352 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (bb
);
355 /* Set RTL expansion for edge profile. */
358 rtl_profile_for_edge (edge e
)
360 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
363 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
365 default_rtl_profile (void)
367 crtl
->maybe_hot_insn_p
= true;
370 /* Return true if the one of outgoing edges is already predicted by
374 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
377 if (!INSN_P (BB_END (bb
)))
379 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
380 if (REG_NOTE_KIND (note
) == REG_BR_PRED
381 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
386 /* This map contains for a basic block the list of predictions for the
389 static struct pointer_map_t
*bb_predictions
;
391 /* Return true if the one of outgoing edges is already predicted by
395 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
397 struct edge_prediction
*i
;
398 void **preds
= pointer_map_contains (bb_predictions
, bb
);
403 for (i
= (struct edge_prediction
*) *preds
; i
; i
= i
->ep_next
)
404 if (i
->ep_predictor
== predictor
)
409 /* Return true when the probability of edge is reliable.
411 The profile guessing code is good at predicting branch outcome (ie.
412 taken/not taken), that is predicted right slightly over 75% of time.
413 It is however notoriously poor on predicting the probability itself.
414 In general the profile appear a lot flatter (with probabilities closer
415 to 50%) than the reality so it is bad idea to use it to drive optimization
416 such as those disabling dynamic branch prediction for well predictable
419 There are two exceptions - edges leading to noreturn edges and edges
420 predicted by number of iterations heuristics are predicted well. This macro
421 should be able to distinguish those, but at the moment it simply check for
422 noreturn heuristic that is only one giving probability over 99% or bellow
423 1%. In future we might want to propagate reliability information across the
424 CFG if we find this information useful on multiple places. */
426 probability_reliable_p (int prob
)
428 return (profile_status
== PROFILE_READ
429 || (profile_status
== PROFILE_GUESSED
430 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
433 /* Same predicate as above, working on edges. */
435 edge_probability_reliable_p (const_edge e
)
437 return probability_reliable_p (e
->probability
);
440 /* Same predicate as edge_probability_reliable_p, working on notes. */
442 br_prob_note_reliable_p (const_rtx note
)
444 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
445 return probability_reliable_p (INTVAL (XEXP (note
, 0)));
449 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
451 gcc_assert (any_condjump_p (insn
));
452 if (!flag_guess_branch_prob
)
455 add_reg_note (insn
, REG_BR_PRED
,
456 gen_rtx_CONCAT (VOIDmode
,
457 GEN_INT ((int) predictor
),
458 GEN_INT ((int) probability
)));
461 /* Predict insn by given predictor. */
464 predict_insn_def (rtx insn
, enum br_predictor predictor
,
465 enum prediction taken
)
467 int probability
= predictor_info
[(int) predictor
].hitrate
;
470 probability
= REG_BR_PROB_BASE
- probability
;
472 predict_insn (insn
, predictor
, probability
);
475 /* Predict edge E with given probability if possible. */
478 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
481 last_insn
= BB_END (e
->src
);
483 /* We can store the branch prediction information only about
484 conditional jumps. */
485 if (!any_condjump_p (last_insn
))
488 /* We always store probability of branching. */
489 if (e
->flags
& EDGE_FALLTHRU
)
490 probability
= REG_BR_PROB_BASE
- probability
;
492 predict_insn (last_insn
, predictor
, probability
);
495 /* Predict edge E with the given PROBABILITY. */
497 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
499 gcc_assert (profile_status
!= PROFILE_GUESSED
);
500 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
501 && flag_guess_branch_prob
&& optimize
)
503 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
504 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
506 i
->ep_next
= (struct edge_prediction
*) *preds
;
508 i
->ep_probability
= probability
;
509 i
->ep_predictor
= predictor
;
514 /* Remove all predictions on given basic block that are attached
517 remove_predictions_associated_with_edge (edge e
)
524 preds
= pointer_map_contains (bb_predictions
, e
->src
);
528 struct edge_prediction
**prediction
= (struct edge_prediction
**) preds
;
529 struct edge_prediction
*next
;
533 if ((*prediction
)->ep_edge
== e
)
535 next
= (*prediction
)->ep_next
;
540 prediction
= &((*prediction
)->ep_next
);
545 /* Clears the list of predictions stored for BB. */
548 clear_bb_predictions (basic_block bb
)
550 void **preds
= pointer_map_contains (bb_predictions
, bb
);
551 struct edge_prediction
*pred
, *next
;
556 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= next
)
558 next
= pred
->ep_next
;
564 /* Return true when we can store prediction on insn INSN.
565 At the moment we represent predictions only on conditional
566 jumps, not at computed jump or other complicated cases. */
568 can_predict_insn_p (const_rtx insn
)
570 return (JUMP_P (insn
)
571 && any_condjump_p (insn
)
572 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
575 /* Predict edge E by given predictor if possible. */
578 predict_edge_def (edge e
, enum br_predictor predictor
,
579 enum prediction taken
)
581 int probability
= predictor_info
[(int) predictor
].hitrate
;
584 probability
= REG_BR_PROB_BASE
- probability
;
586 predict_edge (e
, predictor
, probability
);
589 /* Invert all branch predictions or probability notes in the INSN. This needs
590 to be done each time we invert the condition used by the jump. */
593 invert_br_probabilities (rtx insn
)
597 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
598 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
599 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
600 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
601 XEXP (XEXP (note
, 0), 1)
602 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
605 /* Dump information about the branch prediction to the output file. */
608 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
609 basic_block bb
, int used
)
617 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
618 if (! (e
->flags
& EDGE_FALLTHRU
))
621 fprintf (file
, " %s heuristics%s: %.1f%%",
622 predictor_info
[predictor
].name
,
623 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
627 fprintf (file
, " exec ");
628 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
631 fprintf (file
, " hit ");
632 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
633 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
637 fprintf (file
, "\n");
640 /* We can not predict the probabilities of outgoing edges of bb. Set them
641 evenly and hope for the best. */
643 set_even_probabilities (basic_block bb
)
649 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
650 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
652 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
653 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
654 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
659 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
660 note if not already present. Remove now useless REG_BR_PRED notes. */
663 combine_predictions_for_insn (rtx insn
, basic_block bb
)
668 int best_probability
= PROB_EVEN
;
669 enum br_predictor best_predictor
= END_PREDICTORS
;
670 int combined_probability
= REG_BR_PROB_BASE
/ 2;
672 bool first_match
= false;
675 if (!can_predict_insn_p (insn
))
677 set_even_probabilities (bb
);
681 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
682 pnote
= ®_NOTES (insn
);
684 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
687 /* We implement "first match" heuristics and use probability guessed
688 by predictor with smallest index. */
689 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
690 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
692 enum br_predictor predictor
= ((enum br_predictor
)
693 INTVAL (XEXP (XEXP (note
, 0), 0)));
694 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
697 if (best_predictor
> predictor
)
698 best_probability
= probability
, best_predictor
= predictor
;
700 d
= (combined_probability
* probability
701 + (REG_BR_PROB_BASE
- combined_probability
)
702 * (REG_BR_PROB_BASE
- probability
));
704 /* Use FP math to avoid overflows of 32bit integers. */
706 /* If one probability is 0% and one 100%, avoid division by zero. */
707 combined_probability
= REG_BR_PROB_BASE
/ 2;
709 combined_probability
= (((double) combined_probability
) * probability
710 * REG_BR_PROB_BASE
/ d
+ 0.5);
713 /* Decide which heuristic to use. In case we didn't match anything,
714 use no_prediction heuristic, in case we did match, use either
715 first match or Dempster-Shaffer theory depending on the flags. */
717 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
721 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
722 combined_probability
, bb
, true);
725 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
727 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
732 combined_probability
= best_probability
;
733 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
737 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
739 enum br_predictor predictor
= ((enum br_predictor
)
740 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
741 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
743 dump_prediction (dump_file
, predictor
, probability
, bb
,
744 !first_match
|| best_predictor
== predictor
);
745 *pnote
= XEXP (*pnote
, 1);
748 pnote
= &XEXP (*pnote
, 1);
753 add_reg_note (insn
, REG_BR_PROB
, GEN_INT (combined_probability
));
755 /* Save the prediction into CFG in case we are seeing non-degenerated
757 if (!single_succ_p (bb
))
759 BRANCH_EDGE (bb
)->probability
= combined_probability
;
760 FALLTHRU_EDGE (bb
)->probability
761 = REG_BR_PROB_BASE
- combined_probability
;
764 else if (!single_succ_p (bb
))
766 int prob
= INTVAL (XEXP (prob_note
, 0));
768 BRANCH_EDGE (bb
)->probability
= prob
;
769 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
772 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
775 /* Combine predictions into single probability and store them into CFG.
776 Remove now useless prediction entries. */
779 combine_predictions_for_bb (basic_block bb
)
781 int best_probability
= PROB_EVEN
;
782 enum br_predictor best_predictor
= END_PREDICTORS
;
783 int combined_probability
= REG_BR_PROB_BASE
/ 2;
785 bool first_match
= false;
787 struct edge_prediction
*pred
;
789 edge e
, first
= NULL
, second
= NULL
;
793 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
794 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
797 if (first
&& !second
)
803 /* When there is no successor or only one choice, prediction is easy.
805 We are lazy for now and predict only basic blocks with two outgoing
806 edges. It is possible to predict generic case too, but we have to
807 ignore first match heuristics and do more involved combining. Implement
812 set_even_probabilities (bb
);
813 clear_bb_predictions (bb
);
815 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
821 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
823 preds
= pointer_map_contains (bb_predictions
, bb
);
826 /* We implement "first match" heuristics and use probability guessed
827 by predictor with smallest index. */
828 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
830 enum br_predictor predictor
= pred
->ep_predictor
;
831 int probability
= pred
->ep_probability
;
833 if (pred
->ep_edge
!= first
)
834 probability
= REG_BR_PROB_BASE
- probability
;
837 /* First match heuristics would be widly confused if we predicted
839 if (best_predictor
> predictor
)
841 struct edge_prediction
*pred2
;
842 int prob
= probability
;
844 for (pred2
= (struct edge_prediction
*) *preds
; pred2
; pred2
= pred2
->ep_next
)
845 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
847 int probability2
= pred
->ep_probability
;
849 if (pred2
->ep_edge
!= first
)
850 probability2
= REG_BR_PROB_BASE
- probability2
;
852 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
853 (probability2
< REG_BR_PROB_BASE
/ 2))
856 /* If the same predictor later gave better result, go for it! */
857 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
858 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
862 best_probability
= prob
, best_predictor
= predictor
;
865 d
= (combined_probability
* probability
866 + (REG_BR_PROB_BASE
- combined_probability
)
867 * (REG_BR_PROB_BASE
- probability
));
869 /* Use FP math to avoid overflows of 32bit integers. */
871 /* If one probability is 0% and one 100%, avoid division by zero. */
872 combined_probability
= REG_BR_PROB_BASE
/ 2;
874 combined_probability
= (((double) combined_probability
)
876 * REG_BR_PROB_BASE
/ d
+ 0.5);
880 /* Decide which heuristic to use. In case we didn't match anything,
881 use no_prediction heuristic, in case we did match, use either
882 first match or Dempster-Shaffer theory depending on the flags. */
884 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
888 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
891 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
893 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
898 combined_probability
= best_probability
;
899 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
903 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
905 enum br_predictor predictor
= pred
->ep_predictor
;
906 int probability
= pred
->ep_probability
;
908 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
909 probability
= REG_BR_PROB_BASE
- probability
;
910 dump_prediction (dump_file
, predictor
, probability
, bb
,
911 !first_match
|| best_predictor
== predictor
);
914 clear_bb_predictions (bb
);
918 first
->probability
= combined_probability
;
919 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
923 /* Predict edge probabilities by exploiting loop structure. */
931 /* Try to predict out blocks in a loop that are not part of a
933 FOR_EACH_LOOP (li
, loop
, 0)
935 basic_block bb
, *bbs
;
937 VEC (edge
, heap
) *exits
;
938 struct tree_niter_desc niter_desc
;
941 exits
= get_loop_exit_edges (loop
);
942 n_exits
= VEC_length (edge
, exits
);
944 for (j
= 0; VEC_iterate (edge
, exits
, j
, ex
); j
++)
947 HOST_WIDE_INT nitercst
;
948 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
950 enum br_predictor predictor
;
952 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
953 niter
= niter_desc
.niter
;
954 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
955 niter
= loop_niter_by_eval (loop
, ex
);
957 if (TREE_CODE (niter
) == INTEGER_CST
)
959 if (host_integerp (niter
, 1)
960 && compare_tree_int (niter
, max
-1) == -1)
961 nitercst
= tree_low_cst (niter
, 1) + 1;
964 predictor
= PRED_LOOP_ITERATIONS
;
966 /* If we have just one exit and we can derive some information about
967 the number of iterations of the loop from the statements inside
968 the loop, use it to predict this exit. */
969 else if (n_exits
== 1)
971 nitercst
= estimated_loop_iterations_int (loop
, false);
977 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
982 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
983 predict_edge (ex
, predictor
, probability
);
985 VEC_free (edge
, heap
, exits
);
987 bbs
= get_loop_body (loop
);
989 for (j
= 0; j
< loop
->num_nodes
; j
++)
991 int header_found
= 0;
997 /* Bypass loop heuristics on continue statement. These
998 statements construct loops via "non-loop" constructs
999 in the source language and are better to be handled
1001 if (predicted_by_p (bb
, PRED_CONTINUE
))
1004 /* Loop branch heuristics - predict an edge back to a
1005 loop's head as taken. */
1006 if (bb
== loop
->latch
)
1008 e
= find_edge (loop
->latch
, loop
->header
);
1012 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1016 /* Loop exit heuristics - predict an edge exiting the loop if the
1017 conditional has no loop header successors as not taken. */
1019 /* If we already used more reliable loop exit predictors, do not
1020 bother with PRED_LOOP_EXIT. */
1021 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1022 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1024 /* For loop with many exits we don't want to predict all exits
1025 with the pretty large probability, because if all exits are
1026 considered in row, the loop would be predicted to iterate
1027 almost never. The code to divide probability by number of
1028 exits is very rough. It should compute the number of exits
1029 taken in each patch through function (not the overall number
1030 of exits that might be a lot higher for loops with wide switch
1031 statements in them) and compute n-th square root.
1033 We limit the minimal probability by 2% to avoid
1034 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1035 as this was causing regression in perl benchmark containing such
1038 int probability
= ((REG_BR_PROB_BASE
1039 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1041 if (probability
< HITRATE (2))
1042 probability
= HITRATE (2);
1043 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1044 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1045 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1046 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1050 /* Free basic blocks from get_loop_body. */
1055 /* Attempt to predict probabilities of BB outgoing edges using local
1058 bb_estimate_probability_locally (basic_block bb
)
1060 rtx last_insn
= BB_END (bb
);
1063 if (! can_predict_insn_p (last_insn
))
1065 cond
= get_condition (last_insn
, NULL
, false, false);
1069 /* Try "pointer heuristic."
1070 A comparison ptr == 0 is predicted as false.
1071 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1072 if (COMPARISON_P (cond
)
1073 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1074 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1076 if (GET_CODE (cond
) == EQ
)
1077 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1078 else if (GET_CODE (cond
) == NE
)
1079 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1083 /* Try "opcode heuristic."
1084 EQ tests are usually false and NE tests are usually true. Also,
1085 most quantities are positive, so we can make the appropriate guesses
1086 about signed comparisons against zero. */
1087 switch (GET_CODE (cond
))
1090 /* Unconditional branch. */
1091 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1092 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1097 /* Floating point comparisons appears to behave in a very
1098 unpredictable way because of special role of = tests in
1100 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1102 /* Comparisons with 0 are often used for booleans and there is
1103 nothing useful to predict about them. */
1104 else if (XEXP (cond
, 1) == const0_rtx
1105 || XEXP (cond
, 0) == const0_rtx
)
1108 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1113 /* Floating point comparisons appears to behave in a very
1114 unpredictable way because of special role of = tests in
1116 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1118 /* Comparisons with 0 are often used for booleans and there is
1119 nothing useful to predict about them. */
1120 else if (XEXP (cond
, 1) == const0_rtx
1121 || XEXP (cond
, 0) == const0_rtx
)
1124 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1128 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1132 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1137 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1138 || XEXP (cond
, 1) == constm1_rtx
)
1139 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1144 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1145 || XEXP (cond
, 1) == constm1_rtx
)
1146 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1154 /* Set edge->probability for each successor edge of BB. */
1156 guess_outgoing_edge_probabilities (basic_block bb
)
1158 bb_estimate_probability_locally (bb
);
1159 combine_predictions_for_insn (BB_END (bb
), bb
);
1162 static tree
expr_expected_value (tree
, bitmap
);
1164 /* Helper function for expr_expected_value. */
1167 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
, tree op1
, bitmap visited
)
1171 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1173 if (TREE_CONSTANT (op0
))
1176 if (code
!= SSA_NAME
)
1179 def
= SSA_NAME_DEF_STMT (op0
);
1181 /* If we were already here, break the infinite cycle. */
1182 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (op0
)))
1184 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
);
1332 ass_stmt
= gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
1334 gsi_replace (&bi
, ass_stmt
, true);
1343 /* Predict using opcode of the last statement in basic block. */
1345 tree_predict_by_opcode (basic_block bb
)
1347 gimple stmt
= last_stmt (bb
);
1356 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1358 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1359 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1361 op0
= gimple_cond_lhs (stmt
);
1362 op1
= gimple_cond_rhs (stmt
);
1363 cmp
= gimple_cond_code (stmt
);
1364 type
= TREE_TYPE (op0
);
1365 visited
= BITMAP_ALLOC (NULL
);
1366 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
);
1367 BITMAP_FREE (visited
);
1370 if (integer_zerop (val
))
1371 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1373 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1376 /* Try "pointer heuristic."
1377 A comparison ptr == 0 is predicted as false.
1378 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1379 if (POINTER_TYPE_P (type
))
1382 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1383 else if (cmp
== NE_EXPR
)
1384 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1388 /* Try "opcode heuristic."
1389 EQ tests are usually false and NE tests are usually true. Also,
1390 most quantities are positive, so we can make the appropriate guesses
1391 about signed comparisons against zero. */
1396 /* Floating point comparisons appears to behave in a very
1397 unpredictable way because of special role of = tests in
1399 if (FLOAT_TYPE_P (type
))
1401 /* Comparisons with 0 are often used for booleans and there is
1402 nothing useful to predict about them. */
1403 else if (integer_zerop (op0
) || integer_zerop (op1
))
1406 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1411 /* Floating point comparisons appears to behave in a very
1412 unpredictable way because of special role of = tests in
1414 if (FLOAT_TYPE_P (type
))
1416 /* Comparisons with 0 are often used for booleans and there is
1417 nothing useful to predict about them. */
1418 else if (integer_zerop (op0
)
1419 || integer_zerop (op1
))
1422 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1426 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1429 case UNORDERED_EXPR
:
1430 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1435 if (integer_zerop (op1
)
1436 || integer_onep (op1
)
1437 || integer_all_onesp (op1
)
1440 || real_minus_onep (op1
))
1441 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1446 if (integer_zerop (op1
)
1447 || integer_onep (op1
)
1448 || integer_all_onesp (op1
)
1451 || real_minus_onep (op1
))
1452 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1460 /* Try to guess whether the value of return means error code. */
1462 static enum br_predictor
1463 return_prediction (tree val
, enum prediction
*prediction
)
1467 return PRED_NO_PREDICTION
;
1468 /* Different heuristics for pointers and scalars. */
1469 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1471 /* NULL is usually not returned. */
1472 if (integer_zerop (val
))
1474 *prediction
= NOT_TAKEN
;
1475 return PRED_NULL_RETURN
;
1478 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1480 /* Negative return values are often used to indicate
1482 if (TREE_CODE (val
) == INTEGER_CST
1483 && tree_int_cst_sgn (val
) < 0)
1485 *prediction
= NOT_TAKEN
;
1486 return PRED_NEGATIVE_RETURN
;
1488 /* Constant return values seems to be commonly taken.
1489 Zero/one often represent booleans so exclude them from the
1491 if (TREE_CONSTANT (val
)
1492 && (!integer_zerop (val
) && !integer_onep (val
)))
1494 *prediction
= TAKEN
;
1495 return PRED_CONST_RETURN
;
1498 return PRED_NO_PREDICTION
;
1501 /* Find the basic block with return expression and look up for possible
1502 return value trying to apply RETURN_PREDICTION heuristics. */
1504 apply_return_prediction (void)
1506 gimple return_stmt
= NULL
;
1510 int phi_num_args
, i
;
1511 enum br_predictor pred
;
1512 enum prediction direction
;
1515 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1517 return_stmt
= last_stmt (e
->src
);
1519 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
1524 return_val
= gimple_return_retval (return_stmt
);
1527 if (TREE_CODE (return_val
) != SSA_NAME
1528 || !SSA_NAME_DEF_STMT (return_val
)
1529 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
1531 phi
= SSA_NAME_DEF_STMT (return_val
);
1532 phi_num_args
= gimple_phi_num_args (phi
);
1533 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
1535 /* Avoid the degenerate case where all return values form the function
1536 belongs to same category (ie they are all positive constants)
1537 so we can hardly say something about them. */
1538 for (i
= 1; i
< phi_num_args
; i
++)
1539 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
1541 if (i
!= phi_num_args
)
1542 for (i
= 0; i
< phi_num_args
; i
++)
1544 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
1545 if (pred
!= PRED_NO_PREDICTION
)
1546 predict_paths_leading_to (gimple_phi_arg_edge (phi
, i
)->src
, pred
,
1551 /* Look for basic block that contains unlikely to happen events
1552 (such as noreturn calls) and mark all paths leading to execution
1553 of this basic blocks as unlikely. */
1556 tree_bb_level_predictions (void)
1559 bool has_return_edges
= false;
1563 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1564 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
1566 has_return_edges
= true;
1570 apply_return_prediction ();
1574 gimple_stmt_iterator gsi
;
1576 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1578 gimple stmt
= gsi_stmt (gsi
);
1581 if (is_gimple_call (stmt
))
1583 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
1584 && has_return_edges
)
1585 predict_paths_leading_to (bb
, PRED_NORETURN
,
1587 decl
= gimple_call_fndecl (stmt
);
1589 && lookup_attribute ("cold",
1590 DECL_ATTRIBUTES (decl
)))
1591 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
1594 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
1596 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
1597 gimple_predict_outcome (stmt
));
1598 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1599 hints to callers. */
1605 #ifdef ENABLE_CHECKING
1607 /* Callback for pointer_map_traverse, asserts that the pointer map is
1611 assert_is_empty (const void *key ATTRIBUTE_UNUSED
, void **value
,
1612 void *data ATTRIBUTE_UNUSED
)
1614 gcc_assert (!*value
);
1619 /* Predict branch probabilities and estimate profile for basic block BB. */
1622 tree_estimate_probability_bb (basic_block bb
)
1628 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1630 /* Predict early returns to be probable, as we've already taken
1631 care for error returns and other cases are often used for
1632 fast paths through function.
1634 Since we've already removed the return statements, we are
1635 looking for CFG like:
1645 if (e
->dest
!= bb
->next_bb
1646 && e
->dest
!= EXIT_BLOCK_PTR
1647 && single_succ_p (e
->dest
)
1648 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR
1649 && (last
= last_stmt (e
->dest
)) != NULL
1650 && gimple_code (last
) == GIMPLE_RETURN
)
1655 if (single_succ_p (bb
))
1657 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
1658 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
1659 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
1660 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
1661 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1664 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
1665 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
1666 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
1667 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1670 /* Look for block we are guarding (ie we dominate it,
1671 but it doesn't postdominate us). */
1672 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1673 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1674 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1676 gimple_stmt_iterator bi
;
1678 /* The call heuristic claims that a guarded function call
1679 is improbable. This is because such calls are often used
1680 to signal exceptional situations such as printing error
1682 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
1685 gimple stmt
= gsi_stmt (bi
);
1686 if (is_gimple_call (stmt
)
1687 /* Constant and pure calls are hardly used to signalize
1688 something exceptional. */
1689 && gimple_has_side_effects (stmt
))
1691 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1697 tree_predict_by_opcode (bb
);
1700 /* Predict branch probabilities and estimate profile of the tree CFG.
1701 This function can be called from the loop optimizers to recompute
1702 the profile information. */
1705 tree_estimate_probability (void)
1709 add_noreturn_fake_exit_edges ();
1710 connect_infinite_loops_to_exit ();
1711 /* We use loop_niter_by_eval, which requires that the loops have
1713 create_preheaders (CP_SIMPLE_PREHEADERS
);
1714 calculate_dominance_info (CDI_POST_DOMINATORS
);
1716 bb_predictions
= pointer_map_create ();
1717 tree_bb_level_predictions ();
1718 record_loop_exits ();
1720 if (number_of_loops () > 1)
1724 tree_estimate_probability_bb (bb
);
1727 combine_predictions_for_bb (bb
);
1729 #ifdef ENABLE_CHECKING
1730 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
1732 pointer_map_destroy (bb_predictions
);
1733 bb_predictions
= NULL
;
1735 estimate_bb_frequencies ();
1736 free_dominance_info (CDI_POST_DOMINATORS
);
1737 remove_fake_exit_edges ();
1740 /* Predict branch probabilities and estimate profile of the tree CFG.
1741 This is the driver function for PASS_PROFILE. */
1744 tree_estimate_probability_driver (void)
1748 loop_optimizer_init (0);
1749 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1750 flow_loops_dump (dump_file
, NULL
, 0);
1752 mark_irreducible_loops ();
1754 nb_loops
= number_of_loops ();
1758 tree_estimate_probability ();
1763 loop_optimizer_finalize ();
1764 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1765 gimple_dump_cfg (dump_file
, dump_flags
);
1766 if (profile_status
== PROFILE_ABSENT
)
1767 profile_status
= PROFILE_GUESSED
;
1771 /* Predict edges to successors of CUR whose sources are not postdominated by
1772 BB by PRED and recurse to all postdominators. */
1775 predict_paths_for_bb (basic_block cur
, basic_block bb
,
1776 enum br_predictor pred
,
1777 enum prediction taken
)
1783 /* We are looking for all edges forming edge cut induced by
1784 set of all blocks postdominated by BB. */
1785 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
1786 if (e
->src
->index
>= NUM_FIXED_BLOCKS
1787 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
1789 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
1790 predict_edge_def (e
, pred
, taken
);
1792 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
1794 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1795 predict_paths_for_bb (son
, bb
, pred
, taken
);
1798 /* Sets branch probabilities according to PREDiction and
1802 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
1803 enum prediction taken
)
1805 predict_paths_for_bb (bb
, bb
, pred
, taken
);
1808 /* This is used to carry information about basic blocks. It is
1809 attached to the AUX field of the standard CFG block. */
1811 typedef struct block_info_def
1813 /* Estimated frequency of execution of basic_block. */
1816 /* To keep queue of basic blocks to process. */
1819 /* Number of predecessors we need to visit first. */
1823 /* Similar information for edges. */
1824 typedef struct edge_info_def
1826 /* In case edge is a loopback edge, the probability edge will be reached
1827 in case header is. Estimated number of iterations of the loop can be
1828 then computed as 1 / (1 - back_edge_prob). */
1829 sreal back_edge_prob
;
1830 /* True if the edge is a loopback edge in the natural loop. */
1831 unsigned int back_edge
:1;
1834 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1835 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1837 /* Helper function for estimate_bb_frequencies.
1838 Propagate the frequencies in blocks marked in
1839 TOVISIT, starting in HEAD. */
1842 propagate_freq (basic_block head
, bitmap tovisit
)
1851 /* For each basic block we need to visit count number of his predecessors
1852 we need to visit first. */
1853 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
1858 /* The outermost "loop" includes the exit block, which we can not
1859 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1860 directly. Do the same for the entry block. */
1861 bb
= BASIC_BLOCK (i
);
1863 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1865 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
1867 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
1869 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
1871 "Irreducible region hit, ignoring edge to %i->%i\n",
1872 e
->src
->index
, bb
->index
);
1874 BLOCK_INFO (bb
)->npredecessors
= count
;
1877 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1879 for (bb
= head
; bb
; bb
= nextbb
)
1882 sreal cyclic_probability
, frequency
;
1884 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1885 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1887 nextbb
= BLOCK_INFO (bb
)->next
;
1888 BLOCK_INFO (bb
)->next
= NULL
;
1890 /* Compute frequency of basic block. */
1893 #ifdef ENABLE_CHECKING
1894 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1895 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
1896 || (e
->flags
& EDGE_DFS_BACK
));
1899 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1900 if (EDGE_INFO (e
)->back_edge
)
1902 sreal_add (&cyclic_probability
, &cyclic_probability
,
1903 &EDGE_INFO (e
)->back_edge_prob
);
1905 else if (!(e
->flags
& EDGE_DFS_BACK
))
1909 /* frequency += (e->probability
1910 * BLOCK_INFO (e->src)->frequency /
1911 REG_BR_PROB_BASE); */
1913 sreal_init (&tmp
, e
->probability
, 0);
1914 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1915 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1916 sreal_add (&frequency
, &frequency
, &tmp
);
1919 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1921 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1922 sizeof (frequency
));
1926 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1928 memcpy (&cyclic_probability
, &real_almost_one
,
1929 sizeof (real_almost_one
));
1932 /* BLOCK_INFO (bb)->frequency = frequency
1933 / (1 - cyclic_probability) */
1935 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1936 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1937 &frequency
, &cyclic_probability
);
1941 bitmap_clear_bit (tovisit
, bb
->index
);
1943 e
= find_edge (bb
, head
);
1948 /* EDGE_INFO (e)->back_edge_prob
1949 = ((e->probability * BLOCK_INFO (bb)->frequency)
1950 / REG_BR_PROB_BASE); */
1952 sreal_init (&tmp
, e
->probability
, 0);
1953 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1954 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1955 &tmp
, &real_inv_br_prob_base
);
1958 /* Propagate to successor blocks. */
1959 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1960 if (!(e
->flags
& EDGE_DFS_BACK
)
1961 && BLOCK_INFO (e
->dest
)->npredecessors
)
1963 BLOCK_INFO (e
->dest
)->npredecessors
--;
1964 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1969 BLOCK_INFO (last
)->next
= e
->dest
;
1977 /* Estimate probabilities of loopback edges in loops at same nest level. */
1980 estimate_loops_at_level (struct loop
*first_loop
)
1984 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1989 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1991 estimate_loops_at_level (loop
->inner
);
1993 /* Find current loop back edge and mark it. */
1994 e
= loop_latch_edge (loop
);
1995 EDGE_INFO (e
)->back_edge
= 1;
1997 bbs
= get_loop_body (loop
);
1998 for (i
= 0; i
< loop
->num_nodes
; i
++)
1999 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2001 propagate_freq (loop
->header
, tovisit
);
2002 BITMAP_FREE (tovisit
);
2006 /* Propagates frequencies through structure of loops. */
2009 estimate_loops (void)
2011 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2014 /* Start by estimating the frequencies in the loops. */
2015 if (number_of_loops () > 1)
2016 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2018 /* Now propagate the frequencies through all the blocks. */
2021 bitmap_set_bit (tovisit
, bb
->index
);
2023 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
2024 BITMAP_FREE (tovisit
);
2027 /* Convert counts measured by profile driven feedback to frequencies.
2028 Return nonzero iff there was any nonzero execution count. */
2031 counts_to_freqs (void)
2033 gcov_type count_max
, true_count_max
= 0;
2036 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2037 true_count_max
= MAX (bb
->count
, true_count_max
);
2039 count_max
= MAX (true_count_max
, 1);
2040 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2041 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2043 return true_count_max
;
2046 /* Return true if function is likely to be expensive, so there is no point to
2047 optimize performance of prologue, epilogue or do inlining at the expense
2048 of code size growth. THRESHOLD is the limit of number of instructions
2049 function can execute at average to be still considered not expensive. */
2052 expensive_function_p (int threshold
)
2054 unsigned int sum
= 0;
2058 /* We can not compute accurately for large thresholds due to scaled
2060 gcc_assert (threshold
<= BB_FREQ_MAX
);
2062 /* Frequencies are out of range. This either means that function contains
2063 internal loop executing more than BB_FREQ_MAX times or profile feedback
2064 is available and function has not been executed at all. */
2065 if (ENTRY_BLOCK_PTR
->frequency
== 0)
2068 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2069 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
2074 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
2075 insn
= NEXT_INSN (insn
))
2076 if (active_insn_p (insn
))
2078 sum
+= bb
->frequency
;
2087 /* Estimate basic blocks frequency by given branch probabilities. */
2090 estimate_bb_frequencies (void)
2095 if (profile_status
!= PROFILE_READ
|| !counts_to_freqs ())
2097 static int real_values_initialized
= 0;
2099 if (!real_values_initialized
)
2101 real_values_initialized
= 1;
2102 sreal_init (&real_zero
, 0, 0);
2103 sreal_init (&real_one
, 1, 0);
2104 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2105 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2106 sreal_init (&real_one_half
, 1, -1);
2107 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2108 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2111 mark_dfs_back_edges ();
2113 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
2115 /* Set up block info for each basic block. */
2116 alloc_aux_for_blocks (sizeof (struct block_info_def
));
2117 alloc_aux_for_edges (sizeof (struct edge_info_def
));
2118 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2123 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2125 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2126 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2127 &EDGE_INFO (e
)->back_edge_prob
,
2128 &real_inv_br_prob_base
);
2132 /* First compute probabilities locally for each loop from innermost
2133 to outermost to examine probabilities for back edges. */
2136 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2138 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2139 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2141 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
2142 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2146 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
2147 sreal_add (&tmp
, &tmp
, &real_one_half
);
2148 bb
->frequency
= sreal_to_int (&tmp
);
2151 free_aux_for_blocks ();
2152 free_aux_for_edges ();
2154 compute_function_frequency ();
2155 if (flag_reorder_functions
)
2156 choose_function_section ();
2159 /* Decide whether function is hot, cold or unlikely executed. */
2161 compute_function_frequency (void)
2164 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
2166 if (!profile_info
|| !flag_branch_probabilities
)
2168 int flags
= flags_from_decl_or_type (current_function_decl
);
2169 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2171 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2172 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
2174 node
->frequency
= NODE_FREQUENCY_HOT
;
2175 else if (flags
& ECF_NORETURN
)
2176 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2177 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2178 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2179 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2180 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
2181 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2184 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2187 if (maybe_hot_bb_p (bb
))
2189 node
->frequency
= NODE_FREQUENCY_HOT
;
2192 if (!probably_never_executed_bb_p (bb
))
2193 node
->frequency
= NODE_FREQUENCY_NORMAL
;
2197 /* Choose appropriate section for the function. */
2199 choose_function_section (void)
2201 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
2202 if (DECL_SECTION_NAME (current_function_decl
)
2203 || !targetm
.have_named_sections
2204 /* Theoretically we can split the gnu.linkonce text section too,
2205 but this requires more work as the frequency needs to match
2206 for all generated objects so we need to merge the frequency
2207 of all instances. For now just never set frequency for these. */
2208 || DECL_ONE_ONLY (current_function_decl
))
2211 /* If we are doing the partitioning optimization, let the optimization
2212 choose the correct section into which to put things. */
2214 if (flag_reorder_blocks_and_partition
)
2217 if (node
->frequency
== NODE_FREQUENCY_HOT
)
2218 DECL_SECTION_NAME (current_function_decl
) =
2219 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
2220 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
2221 DECL_SECTION_NAME (current_function_decl
) =
2222 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
2223 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
2227 gate_estimate_probability (void)
2229 return flag_guess_branch_prob
;
2232 /* Build PREDICT_EXPR. */
2234 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
2236 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
2237 build_int_cst (NULL
, predictor
));
2238 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
2243 predictor_name (enum br_predictor predictor
)
2245 return predictor_info
[predictor
].name
;
2248 struct gimple_opt_pass pass_profile
=
2252 "profile", /* name */
2253 gate_estimate_probability
, /* gate */
2254 tree_estimate_probability_driver
, /* execute */
2257 0, /* static_pass_number */
2258 TV_BRANCH_PROB
, /* tv_id */
2259 PROP_cfg
, /* properties_required */
2260 0, /* properties_provided */
2261 0, /* properties_destroyed */
2262 0, /* todo_flags_start */
2263 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
2267 struct gimple_opt_pass pass_strip_predict_hints
=
2271 "*strip_predict_hints", /* name */
2273 strip_predict_hints
, /* execute */
2276 0, /* static_pass_number */
2277 TV_BRANCH_PROB
, /* tv_id */
2278 PROP_cfg
, /* properties_required */
2279 0, /* properties_provided */
2280 0, /* properties_destroyed */
2281 0, /* todo_flags_start */
2282 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */