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 compute_function_frequency (void);
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 if (!profile_info
|| !flag_branch_probabilities
)
119 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
121 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
124 if (profile_status
== PROFILE_ABSENT
)
126 if (freq
< BB_FREQ_MAX
/ PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
))
131 /* Return TRUE if frequency FREQ is considered to be hot. */
134 maybe_hot_count_p (gcov_type count
)
136 if (profile_status
!= PROFILE_READ
)
138 /* Code executed at most once is not hot. */
139 if (profile_info
->runs
>= count
)
142 > profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
));
145 /* Return true in case BB can be CPU intensive and should be optimized
146 for maximal performance. */
149 maybe_hot_bb_p (const_basic_block bb
)
151 if (profile_status
== PROFILE_READ
)
152 return maybe_hot_count_p (bb
->count
);
153 return maybe_hot_frequency_p (bb
->frequency
);
156 /* Return true if the call can be hot. */
159 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
161 if (profile_info
&& flag_branch_probabilities
163 <= profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
)))
165 if (lookup_attribute ("cold", DECL_ATTRIBUTES (edge
->callee
->decl
))
166 || lookup_attribute ("cold", DECL_ATTRIBUTES (edge
->caller
->decl
)))
168 if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge
->caller
->decl
)))
170 if (flag_guess_branch_prob
171 && edge
->frequency
<= (CGRAPH_FREQ_BASE
172 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
177 /* Return true in case BB can be CPU intensive and should be optimized
178 for maximal performance. */
181 maybe_hot_edge_p (edge e
)
183 if (profile_status
== PROFILE_READ
)
184 return maybe_hot_count_p (e
->count
);
185 return maybe_hot_frequency_p (EDGE_FREQUENCY (e
));
188 /* Return true in case BB is probably never executed. */
190 probably_never_executed_bb_p (const_basic_block bb
)
192 if (profile_info
&& flag_branch_probabilities
)
193 return ((bb
->count
+ profile_info
->runs
/ 2) / profile_info
->runs
) == 0;
194 if ((!profile_info
|| !flag_branch_probabilities
)
195 && cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
200 /* Return true when current function should always be optimized for size. */
203 optimize_function_for_size_p (struct function
*fun
)
205 return (optimize_size
206 || (fun
&& (fun
->function_frequency
207 == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)));
210 /* Return true when current function should always be optimized for speed. */
213 optimize_function_for_speed_p (struct function
*fun
)
215 return !optimize_function_for_size_p (fun
);
218 /* Return TRUE when BB should be optimized for size. */
221 optimize_bb_for_size_p (const_basic_block bb
)
223 return optimize_function_for_size_p (cfun
) || !maybe_hot_bb_p (bb
);
226 /* Return TRUE when BB should be optimized for speed. */
229 optimize_bb_for_speed_p (const_basic_block bb
)
231 return !optimize_bb_for_size_p (bb
);
234 /* Return TRUE when BB should be optimized for size. */
237 optimize_edge_for_size_p (edge e
)
239 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
242 /* Return TRUE when BB should be optimized for speed. */
245 optimize_edge_for_speed_p (edge e
)
247 return !optimize_edge_for_size_p (e
);
250 /* Return TRUE when BB should be optimized for size. */
253 optimize_insn_for_size_p (void)
255 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
258 /* Return TRUE when BB should be optimized for speed. */
261 optimize_insn_for_speed_p (void)
263 return !optimize_insn_for_size_p ();
266 /* Return TRUE when LOOP should be optimized for size. */
269 optimize_loop_for_size_p (struct loop
*loop
)
271 return optimize_bb_for_size_p (loop
->header
);
274 /* Return TRUE when LOOP should be optimized for speed. */
277 optimize_loop_for_speed_p (struct loop
*loop
)
279 return optimize_bb_for_speed_p (loop
->header
);
282 /* Return TRUE when LOOP nest should be optimized for speed. */
285 optimize_loop_nest_for_speed_p (struct loop
*loop
)
287 struct loop
*l
= loop
;
288 if (optimize_loop_for_speed_p (loop
))
291 while (l
&& l
!= loop
)
293 if (optimize_loop_for_speed_p (l
))
301 while (l
!= loop
&& !l
->next
)
310 /* Return TRUE when LOOP nest should be optimized for size. */
313 optimize_loop_nest_for_size_p (struct loop
*loop
)
315 return !optimize_loop_nest_for_speed_p (loop
);
318 /* Return true when edge E is likely to be well predictable by branch
322 predictable_edge_p (edge e
)
324 if (profile_status
== PROFILE_ABSENT
)
327 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
328 || (REG_BR_PROB_BASE
- e
->probability
329 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
335 /* Set RTL expansion for BB profile. */
338 rtl_profile_for_bb (basic_block bb
)
340 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (bb
);
343 /* Set RTL expansion for edge profile. */
346 rtl_profile_for_edge (edge e
)
348 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
351 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
353 default_rtl_profile (void)
355 crtl
->maybe_hot_insn_p
= true;
358 /* Return true if the one of outgoing edges is already predicted by
362 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
365 if (!INSN_P (BB_END (bb
)))
367 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
368 if (REG_NOTE_KIND (note
) == REG_BR_PRED
369 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
374 /* This map contains for a basic block the list of predictions for the
377 static struct pointer_map_t
*bb_predictions
;
379 /* Return true if the one of outgoing edges is already predicted by
383 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
385 struct edge_prediction
*i
;
386 void **preds
= pointer_map_contains (bb_predictions
, bb
);
391 for (i
= (struct edge_prediction
*) *preds
; i
; i
= i
->ep_next
)
392 if (i
->ep_predictor
== predictor
)
397 /* Return true when the probability of edge is reliable.
399 The profile guessing code is good at predicting branch outcome (ie.
400 taken/not taken), that is predicted right slightly over 75% of time.
401 It is however notoriously poor on predicting the probability itself.
402 In general the profile appear a lot flatter (with probabilities closer
403 to 50%) than the reality so it is bad idea to use it to drive optimization
404 such as those disabling dynamic branch prediction for well predictable
407 There are two exceptions - edges leading to noreturn edges and edges
408 predicted by number of iterations heuristics are predicted well. This macro
409 should be able to distinguish those, but at the moment it simply check for
410 noreturn heuristic that is only one giving probability over 99% or bellow
411 1%. In future we might want to propagate reliability information across the
412 CFG if we find this information useful on multiple places. */
414 probability_reliable_p (int prob
)
416 return (profile_status
== PROFILE_READ
417 || (profile_status
== PROFILE_GUESSED
418 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
421 /* Same predicate as above, working on edges. */
423 edge_probability_reliable_p (const_edge e
)
425 return probability_reliable_p (e
->probability
);
428 /* Same predicate as edge_probability_reliable_p, working on notes. */
430 br_prob_note_reliable_p (const_rtx note
)
432 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
433 return probability_reliable_p (INTVAL (XEXP (note
, 0)));
437 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
439 gcc_assert (any_condjump_p (insn
));
440 if (!flag_guess_branch_prob
)
443 add_reg_note (insn
, REG_BR_PRED
,
444 gen_rtx_CONCAT (VOIDmode
,
445 GEN_INT ((int) predictor
),
446 GEN_INT ((int) probability
)));
449 /* Predict insn by given predictor. */
452 predict_insn_def (rtx insn
, enum br_predictor predictor
,
453 enum prediction taken
)
455 int probability
= predictor_info
[(int) predictor
].hitrate
;
458 probability
= REG_BR_PROB_BASE
- probability
;
460 predict_insn (insn
, predictor
, probability
);
463 /* Predict edge E with given probability if possible. */
466 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
469 last_insn
= BB_END (e
->src
);
471 /* We can store the branch prediction information only about
472 conditional jumps. */
473 if (!any_condjump_p (last_insn
))
476 /* We always store probability of branching. */
477 if (e
->flags
& EDGE_FALLTHRU
)
478 probability
= REG_BR_PROB_BASE
- probability
;
480 predict_insn (last_insn
, predictor
, probability
);
483 /* Predict edge E with the given PROBABILITY. */
485 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
487 gcc_assert (profile_status
!= PROFILE_GUESSED
);
488 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
489 && flag_guess_branch_prob
&& optimize
)
491 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
492 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
494 i
->ep_next
= (struct edge_prediction
*) *preds
;
496 i
->ep_probability
= probability
;
497 i
->ep_predictor
= predictor
;
502 /* Remove all predictions on given basic block that are attached
505 remove_predictions_associated_with_edge (edge e
)
512 preds
= pointer_map_contains (bb_predictions
, e
->src
);
516 struct edge_prediction
**prediction
= (struct edge_prediction
**) preds
;
517 struct edge_prediction
*next
;
521 if ((*prediction
)->ep_edge
== e
)
523 next
= (*prediction
)->ep_next
;
528 prediction
= &((*prediction
)->ep_next
);
533 /* Clears the list of predictions stored for BB. */
536 clear_bb_predictions (basic_block bb
)
538 void **preds
= pointer_map_contains (bb_predictions
, bb
);
539 struct edge_prediction
*pred
, *next
;
544 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= next
)
546 next
= pred
->ep_next
;
552 /* Return true when we can store prediction on insn INSN.
553 At the moment we represent predictions only on conditional
554 jumps, not at computed jump or other complicated cases. */
556 can_predict_insn_p (const_rtx insn
)
558 return (JUMP_P (insn
)
559 && any_condjump_p (insn
)
560 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
563 /* Predict edge E by given predictor if possible. */
566 predict_edge_def (edge e
, enum br_predictor predictor
,
567 enum prediction taken
)
569 int probability
= predictor_info
[(int) predictor
].hitrate
;
572 probability
= REG_BR_PROB_BASE
- probability
;
574 predict_edge (e
, predictor
, probability
);
577 /* Invert all branch predictions or probability notes in the INSN. This needs
578 to be done each time we invert the condition used by the jump. */
581 invert_br_probabilities (rtx insn
)
585 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
586 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
587 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
588 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
589 XEXP (XEXP (note
, 0), 1)
590 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
593 /* Dump information about the branch prediction to the output file. */
596 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
597 basic_block bb
, int used
)
605 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
606 if (! (e
->flags
& EDGE_FALLTHRU
))
609 fprintf (file
, " %s heuristics%s: %.1f%%",
610 predictor_info
[predictor
].name
,
611 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
615 fprintf (file
, " exec ");
616 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
619 fprintf (file
, " hit ");
620 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
621 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
625 fprintf (file
, "\n");
628 /* We can not predict the probabilities of outgoing edges of bb. Set them
629 evenly and hope for the best. */
631 set_even_probabilities (basic_block bb
)
637 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
638 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
640 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
641 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
642 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
647 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
648 note if not already present. Remove now useless REG_BR_PRED notes. */
651 combine_predictions_for_insn (rtx insn
, basic_block bb
)
656 int best_probability
= PROB_EVEN
;
657 enum br_predictor best_predictor
= END_PREDICTORS
;
658 int combined_probability
= REG_BR_PROB_BASE
/ 2;
660 bool first_match
= false;
663 if (!can_predict_insn_p (insn
))
665 set_even_probabilities (bb
);
669 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
670 pnote
= ®_NOTES (insn
);
672 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
675 /* We implement "first match" heuristics and use probability guessed
676 by predictor with smallest index. */
677 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
678 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
680 enum br_predictor predictor
= ((enum br_predictor
)
681 INTVAL (XEXP (XEXP (note
, 0), 0)));
682 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
685 if (best_predictor
> predictor
)
686 best_probability
= probability
, best_predictor
= predictor
;
688 d
= (combined_probability
* probability
689 + (REG_BR_PROB_BASE
- combined_probability
)
690 * (REG_BR_PROB_BASE
- probability
));
692 /* Use FP math to avoid overflows of 32bit integers. */
694 /* If one probability is 0% and one 100%, avoid division by zero. */
695 combined_probability
= REG_BR_PROB_BASE
/ 2;
697 combined_probability
= (((double) combined_probability
) * probability
698 * REG_BR_PROB_BASE
/ d
+ 0.5);
701 /* Decide which heuristic to use. In case we didn't match anything,
702 use no_prediction heuristic, in case we did match, use either
703 first match or Dempster-Shaffer theory depending on the flags. */
705 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
709 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
710 combined_probability
, bb
, true);
713 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
715 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
720 combined_probability
= best_probability
;
721 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
725 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
727 enum br_predictor predictor
= ((enum br_predictor
)
728 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
729 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
731 dump_prediction (dump_file
, predictor
, probability
, bb
,
732 !first_match
|| best_predictor
== predictor
);
733 *pnote
= XEXP (*pnote
, 1);
736 pnote
= &XEXP (*pnote
, 1);
741 add_reg_note (insn
, REG_BR_PROB
, GEN_INT (combined_probability
));
743 /* Save the prediction into CFG in case we are seeing non-degenerated
745 if (!single_succ_p (bb
))
747 BRANCH_EDGE (bb
)->probability
= combined_probability
;
748 FALLTHRU_EDGE (bb
)->probability
749 = REG_BR_PROB_BASE
- combined_probability
;
752 else if (!single_succ_p (bb
))
754 int prob
= INTVAL (XEXP (prob_note
, 0));
756 BRANCH_EDGE (bb
)->probability
= prob
;
757 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
760 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
763 /* Combine predictions into single probability and store them into CFG.
764 Remove now useless prediction entries. */
767 combine_predictions_for_bb (basic_block bb
)
769 int best_probability
= PROB_EVEN
;
770 enum br_predictor best_predictor
= END_PREDICTORS
;
771 int combined_probability
= REG_BR_PROB_BASE
/ 2;
773 bool first_match
= false;
775 struct edge_prediction
*pred
;
777 edge e
, first
= NULL
, second
= NULL
;
781 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
782 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
785 if (first
&& !second
)
791 /* When there is no successor or only one choice, prediction is easy.
793 We are lazy for now and predict only basic blocks with two outgoing
794 edges. It is possible to predict generic case too, but we have to
795 ignore first match heuristics and do more involved combining. Implement
800 set_even_probabilities (bb
);
801 clear_bb_predictions (bb
);
803 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
809 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
811 preds
= pointer_map_contains (bb_predictions
, bb
);
814 /* We implement "first match" heuristics and use probability guessed
815 by predictor with smallest index. */
816 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
818 enum br_predictor predictor
= pred
->ep_predictor
;
819 int probability
= pred
->ep_probability
;
821 if (pred
->ep_edge
!= first
)
822 probability
= REG_BR_PROB_BASE
- probability
;
825 /* First match heuristics would be widly confused if we predicted
827 if (best_predictor
> predictor
)
829 struct edge_prediction
*pred2
;
830 int prob
= probability
;
832 for (pred2
= (struct edge_prediction
*) *preds
; pred2
; pred2
= pred2
->ep_next
)
833 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
835 int probability2
= pred
->ep_probability
;
837 if (pred2
->ep_edge
!= first
)
838 probability2
= REG_BR_PROB_BASE
- probability2
;
840 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
841 (probability2
< REG_BR_PROB_BASE
/ 2))
844 /* If the same predictor later gave better result, go for it! */
845 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
846 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
850 best_probability
= prob
, best_predictor
= predictor
;
853 d
= (combined_probability
* probability
854 + (REG_BR_PROB_BASE
- combined_probability
)
855 * (REG_BR_PROB_BASE
- probability
));
857 /* Use FP math to avoid overflows of 32bit integers. */
859 /* If one probability is 0% and one 100%, avoid division by zero. */
860 combined_probability
= REG_BR_PROB_BASE
/ 2;
862 combined_probability
= (((double) combined_probability
)
864 * REG_BR_PROB_BASE
/ d
+ 0.5);
868 /* Decide which heuristic to use. In case we didn't match anything,
869 use no_prediction heuristic, in case we did match, use either
870 first match or Dempster-Shaffer theory depending on the flags. */
872 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
876 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
879 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
881 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
886 combined_probability
= best_probability
;
887 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
891 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
893 enum br_predictor predictor
= pred
->ep_predictor
;
894 int probability
= pred
->ep_probability
;
896 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
897 probability
= REG_BR_PROB_BASE
- probability
;
898 dump_prediction (dump_file
, predictor
, probability
, bb
,
899 !first_match
|| best_predictor
== predictor
);
902 clear_bb_predictions (bb
);
906 first
->probability
= combined_probability
;
907 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
911 /* Predict edge probabilities by exploiting loop structure. */
921 /* Try to predict out blocks in a loop that are not part of a
923 FOR_EACH_LOOP (li
, loop
, 0)
925 basic_block bb
, *bbs
;
927 VEC (edge
, heap
) *exits
;
928 struct tree_niter_desc niter_desc
;
931 exits
= get_loop_exit_edges (loop
);
932 n_exits
= VEC_length (edge
, exits
);
934 for (j
= 0; VEC_iterate (edge
, exits
, j
, ex
); j
++)
937 HOST_WIDE_INT nitercst
;
938 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
940 enum br_predictor predictor
;
942 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
943 niter
= niter_desc
.niter
;
944 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
945 niter
= loop_niter_by_eval (loop
, ex
);
947 if (TREE_CODE (niter
) == INTEGER_CST
)
949 if (host_integerp (niter
, 1)
950 && compare_tree_int (niter
, max
-1) == -1)
951 nitercst
= tree_low_cst (niter
, 1) + 1;
954 predictor
= PRED_LOOP_ITERATIONS
;
956 /* If we have just one exit and we can derive some information about
957 the number of iterations of the loop from the statements inside
958 the loop, use it to predict this exit. */
959 else if (n_exits
== 1)
961 nitercst
= estimated_loop_iterations_int (loop
, false);
967 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
972 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
973 predict_edge (ex
, predictor
, probability
);
975 VEC_free (edge
, heap
, exits
);
977 bbs
= get_loop_body (loop
);
979 for (j
= 0; j
< loop
->num_nodes
; j
++)
981 int header_found
= 0;
987 /* Bypass loop heuristics on continue statement. These
988 statements construct loops via "non-loop" constructs
989 in the source language and are better to be handled
991 if (predicted_by_p (bb
, PRED_CONTINUE
))
994 /* Loop branch heuristics - predict an edge back to a
995 loop's head as taken. */
996 if (bb
== loop
->latch
)
998 e
= find_edge (loop
->latch
, loop
->header
);
1002 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1006 /* Loop exit heuristics - predict an edge exiting the loop if the
1007 conditional has no loop header successors as not taken. */
1009 /* If we already used more reliable loop exit predictors, do not
1010 bother with PRED_LOOP_EXIT. */
1011 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1012 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1014 /* For loop with many exits we don't want to predict all exits
1015 with the pretty large probability, because if all exits are
1016 considered in row, the loop would be predicted to iterate
1017 almost never. The code to divide probability by number of
1018 exits is very rough. It should compute the number of exits
1019 taken in each patch through function (not the overall number
1020 of exits that might be a lot higher for loops with wide switch
1021 statements in them) and compute n-th square root.
1023 We limit the minimal probability by 2% to avoid
1024 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1025 as this was causing regression in perl benchmark containing such
1028 int probability
= ((REG_BR_PROB_BASE
1029 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1031 if (probability
< HITRATE (2))
1032 probability
= HITRATE (2);
1033 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1034 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1035 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1036 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1040 /* Free basic blocks from get_loop_body. */
1047 /* Attempt to predict probabilities of BB outgoing edges using local
1050 bb_estimate_probability_locally (basic_block bb
)
1052 rtx last_insn
= BB_END (bb
);
1055 if (! can_predict_insn_p (last_insn
))
1057 cond
= get_condition (last_insn
, NULL
, false, false);
1061 /* Try "pointer heuristic."
1062 A comparison ptr == 0 is predicted as false.
1063 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1064 if (COMPARISON_P (cond
)
1065 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1066 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1068 if (GET_CODE (cond
) == EQ
)
1069 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1070 else if (GET_CODE (cond
) == NE
)
1071 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1075 /* Try "opcode heuristic."
1076 EQ tests are usually false and NE tests are usually true. Also,
1077 most quantities are positive, so we can make the appropriate guesses
1078 about signed comparisons against zero. */
1079 switch (GET_CODE (cond
))
1082 /* Unconditional branch. */
1083 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1084 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1089 /* Floating point comparisons appears to behave in a very
1090 unpredictable way because of special role of = tests in
1092 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1094 /* Comparisons with 0 are often used for booleans and there is
1095 nothing useful to predict about them. */
1096 else if (XEXP (cond
, 1) == const0_rtx
1097 || XEXP (cond
, 0) == const0_rtx
)
1100 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1105 /* Floating point comparisons appears to behave in a very
1106 unpredictable way because of special role of = tests in
1108 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1110 /* Comparisons with 0 are often used for booleans and there is
1111 nothing useful to predict about them. */
1112 else if (XEXP (cond
, 1) == const0_rtx
1113 || XEXP (cond
, 0) == const0_rtx
)
1116 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1120 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1124 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1129 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1130 || XEXP (cond
, 1) == constm1_rtx
)
1131 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1136 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1137 || XEXP (cond
, 1) == constm1_rtx
)
1138 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1146 /* Set edge->probability for each successor edge of BB. */
1148 guess_outgoing_edge_probabilities (basic_block bb
)
1150 bb_estimate_probability_locally (bb
);
1151 combine_predictions_for_insn (BB_END (bb
), bb
);
1154 static tree
expr_expected_value (tree
, bitmap
);
1156 /* Helper function for expr_expected_value. */
1159 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
, tree op1
, bitmap visited
)
1163 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1165 if (TREE_CONSTANT (op0
))
1168 if (code
!= SSA_NAME
)
1171 def
= SSA_NAME_DEF_STMT (op0
);
1173 /* If we were already here, break the infinite cycle. */
1174 if (bitmap_bit_p (visited
, SSA_NAME_VERSION (op0
)))
1176 bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
));
1178 if (gimple_code (def
) == GIMPLE_PHI
)
1180 /* All the arguments of the PHI node must have the same constant
1182 int i
, n
= gimple_phi_num_args (def
);
1183 tree val
= NULL
, new_val
;
1185 for (i
= 0; i
< n
; i
++)
1187 tree arg
= PHI_ARG_DEF (def
, i
);
1189 /* If this PHI has itself as an argument, we cannot
1190 determine the string length of this argument. However,
1191 if we can find an expected constant value for the other
1192 PHI args then we can still be sure that this is
1193 likely a constant. So be optimistic and just
1194 continue with the next argument. */
1195 if (arg
== PHI_RESULT (def
))
1198 new_val
= expr_expected_value (arg
, visited
);
1203 else if (!operand_equal_p (val
, new_val
, false))
1208 if (is_gimple_assign (def
))
1210 if (gimple_assign_lhs (def
) != op0
)
1213 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1214 gimple_assign_rhs1 (def
),
1215 gimple_assign_rhs_code (def
),
1216 gimple_assign_rhs2 (def
),
1220 if (is_gimple_call (def
))
1222 tree decl
= gimple_call_fndecl (def
);
1225 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
1226 && DECL_FUNCTION_CODE (decl
) == BUILT_IN_EXPECT
)
1230 if (gimple_call_num_args (def
) != 2)
1232 val
= gimple_call_arg (def
, 0);
1233 if (TREE_CONSTANT (val
))
1235 return gimple_call_arg (def
, 1);
1242 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1245 op0
= expr_expected_value (op0
, visited
);
1248 op1
= expr_expected_value (op1
, visited
);
1251 res
= fold_build2 (code
, type
, op0
, op1
);
1252 if (TREE_CONSTANT (res
))
1256 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1259 op0
= expr_expected_value (op0
, visited
);
1262 res
= fold_build1 (code
, type
, op0
);
1263 if (TREE_CONSTANT (res
))
1270 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1271 The function is used by builtin_expect branch predictor so the evidence
1272 must come from this construct and additional possible constant folding.
1274 We may want to implement more involved value guess (such as value range
1275 propagation based prediction), but such tricks shall go to new
1279 expr_expected_value (tree expr
, bitmap visited
)
1281 enum tree_code code
;
1284 if (TREE_CONSTANT (expr
))
1287 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1288 return expr_expected_value_1 (TREE_TYPE (expr
),
1289 op0
, code
, op1
, visited
);
1293 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1294 we no longer need. */
1296 strip_predict_hints (void)
1304 gimple_stmt_iterator bi
;
1305 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
1307 gimple stmt
= gsi_stmt (bi
);
1309 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
1311 gsi_remove (&bi
, true);
1314 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1316 tree fndecl
= gimple_call_fndecl (stmt
);
1319 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1320 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1321 && gimple_call_num_args (stmt
) == 2)
1323 var
= gimple_call_lhs (stmt
);
1324 ass_stmt
= gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
1326 gsi_replace (&bi
, ass_stmt
, true);
1335 /* Predict using opcode of the last statement in basic block. */
1337 tree_predict_by_opcode (basic_block bb
)
1339 gimple stmt
= last_stmt (bb
);
1348 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1350 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1351 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1353 op0
= gimple_cond_lhs (stmt
);
1354 op1
= gimple_cond_rhs (stmt
);
1355 cmp
= gimple_cond_code (stmt
);
1356 type
= TREE_TYPE (op0
);
1357 visited
= BITMAP_ALLOC (NULL
);
1358 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
);
1359 BITMAP_FREE (visited
);
1362 if (integer_zerop (val
))
1363 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, NOT_TAKEN
);
1365 predict_edge_def (then_edge
, PRED_BUILTIN_EXPECT
, TAKEN
);
1368 /* Try "pointer heuristic."
1369 A comparison ptr == 0 is predicted as false.
1370 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1371 if (POINTER_TYPE_P (type
))
1374 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
1375 else if (cmp
== NE_EXPR
)
1376 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
1380 /* Try "opcode heuristic."
1381 EQ tests are usually false and NE tests are usually true. Also,
1382 most quantities are positive, so we can make the appropriate guesses
1383 about signed comparisons against zero. */
1388 /* Floating point comparisons appears to behave in a very
1389 unpredictable way because of special role of = tests in
1391 if (FLOAT_TYPE_P (type
))
1393 /* Comparisons with 0 are often used for booleans and there is
1394 nothing useful to predict about them. */
1395 else if (integer_zerop (op0
) || integer_zerop (op1
))
1398 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
1403 /* Floating point comparisons appears to behave in a very
1404 unpredictable way because of special role of = tests in
1406 if (FLOAT_TYPE_P (type
))
1408 /* Comparisons with 0 are often used for booleans and there is
1409 nothing useful to predict about them. */
1410 else if (integer_zerop (op0
)
1411 || integer_zerop (op1
))
1414 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
1418 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
1421 case UNORDERED_EXPR
:
1422 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
1427 if (integer_zerop (op1
)
1428 || integer_onep (op1
)
1429 || integer_all_onesp (op1
)
1432 || real_minus_onep (op1
))
1433 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
1438 if (integer_zerop (op1
)
1439 || integer_onep (op1
)
1440 || integer_all_onesp (op1
)
1443 || real_minus_onep (op1
))
1444 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
1452 /* Try to guess whether the value of return means error code. */
1454 static enum br_predictor
1455 return_prediction (tree val
, enum prediction
*prediction
)
1459 return PRED_NO_PREDICTION
;
1460 /* Different heuristics for pointers and scalars. */
1461 if (POINTER_TYPE_P (TREE_TYPE (val
)))
1463 /* NULL is usually not returned. */
1464 if (integer_zerop (val
))
1466 *prediction
= NOT_TAKEN
;
1467 return PRED_NULL_RETURN
;
1470 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
1472 /* Negative return values are often used to indicate
1474 if (TREE_CODE (val
) == INTEGER_CST
1475 && tree_int_cst_sgn (val
) < 0)
1477 *prediction
= NOT_TAKEN
;
1478 return PRED_NEGATIVE_RETURN
;
1480 /* Constant return values seems to be commonly taken.
1481 Zero/one often represent booleans so exclude them from the
1483 if (TREE_CONSTANT (val
)
1484 && (!integer_zerop (val
) && !integer_onep (val
)))
1486 *prediction
= TAKEN
;
1487 return PRED_CONST_RETURN
;
1490 return PRED_NO_PREDICTION
;
1493 /* Find the basic block with return expression and look up for possible
1494 return value trying to apply RETURN_PREDICTION heuristics. */
1496 apply_return_prediction (void)
1498 gimple return_stmt
= NULL
;
1502 int phi_num_args
, i
;
1503 enum br_predictor pred
;
1504 enum prediction direction
;
1507 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1509 return_stmt
= last_stmt (e
->src
);
1511 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
1516 return_val
= gimple_return_retval (return_stmt
);
1519 if (TREE_CODE (return_val
) != SSA_NAME
1520 || !SSA_NAME_DEF_STMT (return_val
)
1521 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
1523 phi
= SSA_NAME_DEF_STMT (return_val
);
1524 phi_num_args
= gimple_phi_num_args (phi
);
1525 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
1527 /* Avoid the degenerate case where all return values form the function
1528 belongs to same category (ie they are all positive constants)
1529 so we can hardly say something about them. */
1530 for (i
= 1; i
< phi_num_args
; i
++)
1531 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
1533 if (i
!= phi_num_args
)
1534 for (i
= 0; i
< phi_num_args
; i
++)
1536 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
1537 if (pred
!= PRED_NO_PREDICTION
)
1538 predict_paths_leading_to (gimple_phi_arg_edge (phi
, i
)->src
, pred
,
1543 /* Look for basic block that contains unlikely to happen events
1544 (such as noreturn calls) and mark all paths leading to execution
1545 of this basic blocks as unlikely. */
1548 tree_bb_level_predictions (void)
1551 bool has_return_edges
= false;
1555 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
1556 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
1558 has_return_edges
= true;
1562 apply_return_prediction ();
1566 gimple_stmt_iterator gsi
;
1568 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1570 gimple stmt
= gsi_stmt (gsi
);
1573 if (is_gimple_call (stmt
))
1575 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
1576 && has_return_edges
)
1577 predict_paths_leading_to (bb
, PRED_NORETURN
,
1579 decl
= gimple_call_fndecl (stmt
);
1581 && lookup_attribute ("cold",
1582 DECL_ATTRIBUTES (decl
)))
1583 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
1586 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
1588 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
1589 gimple_predict_outcome (stmt
));
1590 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1591 hints to callers. */
1597 #ifdef ENABLE_CHECKING
1599 /* Callback for pointer_map_traverse, asserts that the pointer map is
1603 assert_is_empty (const void *key ATTRIBUTE_UNUSED
, void **value
,
1604 void *data ATTRIBUTE_UNUSED
)
1606 gcc_assert (!*value
);
1611 /* Predict branch probabilities and estimate profile of the tree CFG. */
1613 tree_estimate_probability (void)
1617 loop_optimizer_init (0);
1618 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1619 flow_loops_dump (dump_file
, NULL
, 0);
1621 add_noreturn_fake_exit_edges ();
1622 connect_infinite_loops_to_exit ();
1623 /* We use loop_niter_by_eval, which requires that the loops have
1625 create_preheaders (CP_SIMPLE_PREHEADERS
);
1626 calculate_dominance_info (CDI_POST_DOMINATORS
);
1628 bb_predictions
= pointer_map_create ();
1629 tree_bb_level_predictions ();
1631 mark_irreducible_loops ();
1632 record_loop_exits ();
1633 if (number_of_loops () > 1)
1642 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1644 /* Predict early returns to be probable, as we've already taken
1645 care for error returns and other cases are often used for
1646 fast paths through function.
1648 Since we've already removed the return statements, we are
1649 looking for CFG like:
1659 if (e
->dest
!= bb
->next_bb
1660 && e
->dest
!= EXIT_BLOCK_PTR
1661 && single_succ_p (e
->dest
)
1662 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR
1663 && (last
= last_stmt (e
->dest
)) != NULL
1664 && gimple_code (last
) == GIMPLE_RETURN
)
1669 if (single_succ_p (bb
))
1671 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
1672 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
1673 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
1674 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
1675 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1678 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
1679 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
1680 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
1681 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
1684 /* Look for block we are guarding (ie we dominate it,
1685 but it doesn't postdominate us). */
1686 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
1687 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
1688 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
1690 gimple_stmt_iterator bi
;
1692 /* The call heuristic claims that a guarded function call
1693 is improbable. This is because such calls are often used
1694 to signal exceptional situations such as printing error
1696 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
1699 gimple stmt
= gsi_stmt (bi
);
1700 if (is_gimple_call (stmt
)
1701 /* Constant and pure calls are hardly used to signalize
1702 something exceptional. */
1703 && gimple_has_side_effects (stmt
))
1705 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
1711 tree_predict_by_opcode (bb
);
1714 combine_predictions_for_bb (bb
);
1716 #ifdef ENABLE_CHECKING
1717 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
1719 pointer_map_destroy (bb_predictions
);
1720 bb_predictions
= NULL
;
1722 estimate_bb_frequencies ();
1723 free_dominance_info (CDI_POST_DOMINATORS
);
1724 remove_fake_exit_edges ();
1725 loop_optimizer_finalize ();
1726 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1727 gimple_dump_cfg (dump_file
, dump_flags
);
1728 if (profile_status
== PROFILE_ABSENT
)
1729 profile_status
= PROFILE_GUESSED
;
1733 /* Predict edges to successors of CUR whose sources are not postdominated by
1734 BB by PRED and recurse to all postdominators. */
1737 predict_paths_for_bb (basic_block cur
, basic_block bb
,
1738 enum br_predictor pred
,
1739 enum prediction taken
)
1745 /* We are looking for all edges forming edge cut induced by
1746 set of all blocks postdominated by BB. */
1747 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
1748 if (e
->src
->index
>= NUM_FIXED_BLOCKS
1749 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
1751 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
1752 predict_edge_def (e
, pred
, taken
);
1754 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
1756 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
1757 predict_paths_for_bb (son
, bb
, pred
, taken
);
1760 /* Sets branch probabilities according to PREDiction and
1764 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
1765 enum prediction taken
)
1767 predict_paths_for_bb (bb
, bb
, pred
, taken
);
1770 /* This is used to carry information about basic blocks. It is
1771 attached to the AUX field of the standard CFG block. */
1773 typedef struct block_info_def
1775 /* Estimated frequency of execution of basic_block. */
1778 /* To keep queue of basic blocks to process. */
1781 /* Number of predecessors we need to visit first. */
1785 /* Similar information for edges. */
1786 typedef struct edge_info_def
1788 /* In case edge is a loopback edge, the probability edge will be reached
1789 in case header is. Estimated number of iterations of the loop can be
1790 then computed as 1 / (1 - back_edge_prob). */
1791 sreal back_edge_prob
;
1792 /* True if the edge is a loopback edge in the natural loop. */
1793 unsigned int back_edge
:1;
1796 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1797 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1799 /* Helper function for estimate_bb_frequencies.
1800 Propagate the frequencies in blocks marked in
1801 TOVISIT, starting in HEAD. */
1804 propagate_freq (basic_block head
, bitmap tovisit
)
1813 /* For each basic block we need to visit count number of his predecessors
1814 we need to visit first. */
1815 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
1820 /* The outermost "loop" includes the exit block, which we can not
1821 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1822 directly. Do the same for the entry block. */
1823 bb
= BASIC_BLOCK (i
);
1825 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1827 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
1829 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
1831 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
1833 "Irreducible region hit, ignoring edge to %i->%i\n",
1834 e
->src
->index
, bb
->index
);
1836 BLOCK_INFO (bb
)->npredecessors
= count
;
1839 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
1841 for (bb
= head
; bb
; bb
= nextbb
)
1844 sreal cyclic_probability
, frequency
;
1846 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
1847 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
1849 nextbb
= BLOCK_INFO (bb
)->next
;
1850 BLOCK_INFO (bb
)->next
= NULL
;
1852 /* Compute frequency of basic block. */
1855 #ifdef ENABLE_CHECKING
1856 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1857 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
1858 || (e
->flags
& EDGE_DFS_BACK
));
1861 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1862 if (EDGE_INFO (e
)->back_edge
)
1864 sreal_add (&cyclic_probability
, &cyclic_probability
,
1865 &EDGE_INFO (e
)->back_edge_prob
);
1867 else if (!(e
->flags
& EDGE_DFS_BACK
))
1871 /* frequency += (e->probability
1872 * BLOCK_INFO (e->src)->frequency /
1873 REG_BR_PROB_BASE); */
1875 sreal_init (&tmp
, e
->probability
, 0);
1876 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
1877 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
1878 sreal_add (&frequency
, &frequency
, &tmp
);
1881 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
1883 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
1884 sizeof (frequency
));
1888 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
1890 memcpy (&cyclic_probability
, &real_almost_one
,
1891 sizeof (real_almost_one
));
1894 /* BLOCK_INFO (bb)->frequency = frequency
1895 / (1 - cyclic_probability) */
1897 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
1898 sreal_div (&BLOCK_INFO (bb
)->frequency
,
1899 &frequency
, &cyclic_probability
);
1903 bitmap_clear_bit (tovisit
, bb
->index
);
1905 e
= find_edge (bb
, head
);
1910 /* EDGE_INFO (e)->back_edge_prob
1911 = ((e->probability * BLOCK_INFO (bb)->frequency)
1912 / REG_BR_PROB_BASE); */
1914 sreal_init (&tmp
, e
->probability
, 0);
1915 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
1916 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
1917 &tmp
, &real_inv_br_prob_base
);
1920 /* Propagate to successor blocks. */
1921 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1922 if (!(e
->flags
& EDGE_DFS_BACK
)
1923 && BLOCK_INFO (e
->dest
)->npredecessors
)
1925 BLOCK_INFO (e
->dest
)->npredecessors
--;
1926 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
1931 BLOCK_INFO (last
)->next
= e
->dest
;
1939 /* Estimate probabilities of loopback edges in loops at same nest level. */
1942 estimate_loops_at_level (struct loop
*first_loop
)
1946 for (loop
= first_loop
; loop
; loop
= loop
->next
)
1951 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1953 estimate_loops_at_level (loop
->inner
);
1955 /* Find current loop back edge and mark it. */
1956 e
= loop_latch_edge (loop
);
1957 EDGE_INFO (e
)->back_edge
= 1;
1959 bbs
= get_loop_body (loop
);
1960 for (i
= 0; i
< loop
->num_nodes
; i
++)
1961 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
1963 propagate_freq (loop
->header
, tovisit
);
1964 BITMAP_FREE (tovisit
);
1968 /* Propagates frequencies through structure of loops. */
1971 estimate_loops (void)
1973 bitmap tovisit
= BITMAP_ALLOC (NULL
);
1976 /* Start by estimating the frequencies in the loops. */
1977 if (number_of_loops () > 1)
1978 estimate_loops_at_level (current_loops
->tree_root
->inner
);
1980 /* Now propagate the frequencies through all the blocks. */
1983 bitmap_set_bit (tovisit
, bb
->index
);
1985 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
1986 BITMAP_FREE (tovisit
);
1989 /* Convert counts measured by profile driven feedback to frequencies.
1990 Return nonzero iff there was any nonzero execution count. */
1993 counts_to_freqs (void)
1995 gcov_type count_max
, true_count_max
= 0;
1999 true_count_max
= MAX (bb
->count
, true_count_max
);
2001 count_max
= MAX (true_count_max
, 1);
2002 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2003 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2005 return true_count_max
;
2008 /* Return true if function is likely to be expensive, so there is no point to
2009 optimize performance of prologue, epilogue or do inlining at the expense
2010 of code size growth. THRESHOLD is the limit of number of instructions
2011 function can execute at average to be still considered not expensive. */
2014 expensive_function_p (int threshold
)
2016 unsigned int sum
= 0;
2020 /* We can not compute accurately for large thresholds due to scaled
2022 gcc_assert (threshold
<= BB_FREQ_MAX
);
2024 /* Frequencies are out of range. This either means that function contains
2025 internal loop executing more than BB_FREQ_MAX times or profile feedback
2026 is available and function has not been executed at all. */
2027 if (ENTRY_BLOCK_PTR
->frequency
== 0)
2030 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2031 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
2036 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
));
2037 insn
= NEXT_INSN (insn
))
2038 if (active_insn_p (insn
))
2040 sum
+= bb
->frequency
;
2049 /* Estimate basic blocks frequency by given branch probabilities. */
2052 estimate_bb_frequencies (void)
2057 if (profile_status
!= PROFILE_READ
|| !counts_to_freqs ())
2059 static int real_values_initialized
= 0;
2061 if (!real_values_initialized
)
2063 real_values_initialized
= 1;
2064 sreal_init (&real_zero
, 0, 0);
2065 sreal_init (&real_one
, 1, 0);
2066 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2067 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2068 sreal_init (&real_one_half
, 1, -1);
2069 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2070 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2073 mark_dfs_back_edges ();
2075 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
2077 /* Set up block info for each basic block. */
2078 alloc_aux_for_blocks (sizeof (struct block_info_def
));
2079 alloc_aux_for_edges (sizeof (struct edge_info_def
));
2080 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2085 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2087 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2088 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2089 &EDGE_INFO (e
)->back_edge_prob
,
2090 &real_inv_br_prob_base
);
2094 /* First compute probabilities locally for each loop from innermost
2095 to outermost to examine probabilities for back edges. */
2098 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2100 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2101 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2103 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
2104 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2108 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
2109 sreal_add (&tmp
, &tmp
, &real_one_half
);
2110 bb
->frequency
= sreal_to_int (&tmp
);
2113 free_aux_for_blocks ();
2114 free_aux_for_edges ();
2116 compute_function_frequency ();
2117 if (flag_reorder_functions
)
2118 choose_function_section ();
2121 /* Decide whether function is hot, cold or unlikely executed. */
2123 compute_function_frequency (void)
2127 if (!profile_info
|| !flag_branch_probabilities
)
2129 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2131 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
2132 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
2134 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
2137 cfun
->function_frequency
= FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
;
2140 if (maybe_hot_bb_p (bb
))
2142 cfun
->function_frequency
= FUNCTION_FREQUENCY_HOT
;
2145 if (!probably_never_executed_bb_p (bb
))
2146 cfun
->function_frequency
= FUNCTION_FREQUENCY_NORMAL
;
2150 /* Choose appropriate section for the function. */
2152 choose_function_section (void)
2154 if (DECL_SECTION_NAME (current_function_decl
)
2155 || !targetm
.have_named_sections
2156 /* Theoretically we can split the gnu.linkonce text section too,
2157 but this requires more work as the frequency needs to match
2158 for all generated objects so we need to merge the frequency
2159 of all instances. For now just never set frequency for these. */
2160 || DECL_ONE_ONLY (current_function_decl
))
2163 /* If we are doing the partitioning optimization, let the optimization
2164 choose the correct section into which to put things. */
2166 if (flag_reorder_blocks_and_partition
)
2169 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_HOT
)
2170 DECL_SECTION_NAME (current_function_decl
) =
2171 build_string (strlen (HOT_TEXT_SECTION_NAME
), HOT_TEXT_SECTION_NAME
);
2172 if (cfun
->function_frequency
== FUNCTION_FREQUENCY_UNLIKELY_EXECUTED
)
2173 DECL_SECTION_NAME (current_function_decl
) =
2174 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME
),
2175 UNLIKELY_EXECUTED_TEXT_SECTION_NAME
);
2179 gate_estimate_probability (void)
2181 return flag_guess_branch_prob
;
2184 /* Build PREDICT_EXPR. */
2186 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
2188 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
2189 build_int_cst (NULL
, predictor
));
2190 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
2195 predictor_name (enum br_predictor predictor
)
2197 return predictor_info
[predictor
].name
;
2200 struct gimple_opt_pass pass_profile
=
2204 "profile", /* name */
2205 gate_estimate_probability
, /* gate */
2206 tree_estimate_probability
, /* execute */
2209 0, /* static_pass_number */
2210 TV_BRANCH_PROB
, /* tv_id */
2211 PROP_cfg
, /* properties_required */
2212 0, /* properties_provided */
2213 0, /* properties_destroyed */
2214 0, /* todo_flags_start */
2215 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */
2219 struct gimple_opt_pass pass_strip_predict_hints
=
2225 strip_predict_hints
, /* execute */
2228 0, /* static_pass_number */
2229 TV_BRANCH_PROB
, /* tv_id */
2230 PROP_cfg
, /* properties_required */
2231 0, /* properties_provided */
2232 0, /* properties_destroyed */
2233 0, /* todo_flags_start */
2234 TODO_ggc_collect
| TODO_verify_ssa
/* todo_flags_finish */