1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 [1] "Branch Prediction for Free"
23 Ball and Larus; PLDI '93.
24 [2] "Static Branch Frequency and Program Profile Analysis"
25 Wu and Larus; MICRO-27.
26 [3] "Corpus-based Static Branch Prediction"
27 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
32 #include "coretypes.h"
37 #include "hard-reg-set.h"
38 #include "basic-block.h"
39 #include "insn-config.h"
44 #include "diagnostic-core.h"
54 #include "gimple-ssa.h"
57 #include "tree-phinodes.h"
58 #include "ssa-iterators.h"
59 #include "tree-ssa-loop-niter.h"
60 #include "tree-ssa-loop.h"
62 #include "tree-pass.h"
63 #include "tree-scalar-evolution.h"
65 #include "pointer-set.h"
67 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
68 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
69 static sreal real_zero
, real_one
, real_almost_one
, real_br_prob_base
,
70 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
72 /* Random guesstimation given names.
73 PROV_VERY_UNLIKELY should be small enough so basic block predicted
74 by it gets below HOT_BB_FREQUENCY_FRACTION. */
75 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
76 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
77 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
78 #define PROB_ALWAYS (REG_BR_PROB_BASE)
80 static void combine_predictions_for_insn (rtx
, basic_block
);
81 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
82 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
83 static void predict_paths_leading_to_edge (edge
, enum br_predictor
, enum prediction
);
84 static bool can_predict_insn_p (const_rtx
);
86 /* Information we hold about each branch predictor.
87 Filled using information from predict.def. */
91 const char *const name
; /* Name used in the debugging dumps. */
92 const int hitrate
; /* Expected hitrate used by
93 predict_insn_def call. */
97 /* Use given predictor without Dempster-Shaffer theory if it matches
98 using first_match heuristics. */
99 #define PRED_FLAG_FIRST_MATCH 1
101 /* Recompute hitrate in percent to our representation. */
103 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
105 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
106 static const struct predictor_info predictor_info
[]= {
107 #include "predict.def"
109 /* Upper bound on predictors. */
114 /* Return TRUE if frequency FREQ is considered to be hot. */
117 maybe_hot_frequency_p (struct function
*fun
, int freq
)
119 struct cgraph_node
*node
= cgraph_get_node (fun
->decl
);
120 if (!profile_info
|| !flag_branch_probabilities
)
122 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
124 if (node
->frequency
== NODE_FREQUENCY_HOT
)
127 if (profile_status_for_function (fun
) == PROFILE_ABSENT
)
129 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
130 && freq
< (ENTRY_BLOCK_PTR_FOR_FUNCTION (fun
)->frequency
* 2 / 3))
132 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
134 if (freq
< (ENTRY_BLOCK_PTR_FOR_FUNCTION (fun
)->frequency
135 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
140 static gcov_type min_count
= -1;
142 /* Determine the threshold for hot BB counts. */
145 get_hot_bb_threshold ()
147 gcov_working_set_t
*ws
;
150 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
152 min_count
= ws
->min_counter
;
157 /* Set the threshold for hot BB counts. */
160 set_hot_bb_threshold (gcov_type min
)
165 /* Return TRUE if frequency FREQ is considered to be hot. */
168 maybe_hot_count_p (struct function
*fun
, gcov_type count
)
170 if (fun
&& profile_status_for_function (fun
) != PROFILE_READ
)
172 /* Code executed at most once is not hot. */
173 if (profile_info
->runs
>= count
)
175 return (count
>= get_hot_bb_threshold ());
178 /* Return true in case BB can be CPU intensive and should be optimized
179 for maximal performance. */
182 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
184 gcc_checking_assert (fun
);
185 if (profile_status_for_function (fun
) == PROFILE_READ
)
186 return maybe_hot_count_p (fun
, bb
->count
);
187 return maybe_hot_frequency_p (fun
, bb
->frequency
);
190 /* Return true if the call can be hot. */
193 cgraph_maybe_hot_edge_p (struct cgraph_edge
*edge
)
195 if (profile_info
&& flag_branch_probabilities
196 && !maybe_hot_count_p (NULL
,
199 if (edge
->caller
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
201 && edge
->callee
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
203 if (edge
->caller
->frequency
> NODE_FREQUENCY_UNLIKELY_EXECUTED
205 && edge
->callee
->frequency
<= NODE_FREQUENCY_EXECUTED_ONCE
))
209 if (edge
->caller
->frequency
== NODE_FREQUENCY_HOT
)
211 if (edge
->caller
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
212 && edge
->frequency
< CGRAPH_FREQ_BASE
* 3 / 2)
214 if (flag_guess_branch_prob
)
216 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0
217 || edge
->frequency
<= (CGRAPH_FREQ_BASE
218 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)))
224 /* Return true in case BB can be CPU intensive and should be optimized
225 for maximal performance. */
228 maybe_hot_edge_p (edge e
)
230 if (profile_status
== PROFILE_READ
)
231 return maybe_hot_count_p (cfun
, e
->count
);
232 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
237 /* Return true if profile COUNT and FREQUENCY, or function FUN static
238 node frequency reflects never being executed. */
241 probably_never_executed (struct function
*fun
,
242 gcov_type count
, int frequency
)
244 gcc_checking_assert (fun
);
245 if (profile_status_for_function (fun
) == PROFILE_READ
)
247 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
248 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
252 if (!ENTRY_BLOCK_PTR
->frequency
)
254 if (ENTRY_BLOCK_PTR
->count
)
256 gcov_type computed_count
;
257 /* Check for possibility of overflow, in which case entry bb count
258 is large enough to do the division first without losing much
260 if (ENTRY_BLOCK_PTR
->count
< REG_BR_PROB_BASE
* REG_BR_PROB_BASE
)
262 gcov_type scaled_count
263 = frequency
* ENTRY_BLOCK_PTR
->count
* unlikely_count_fraction
;
264 computed_count
= RDIV (scaled_count
, ENTRY_BLOCK_PTR
->frequency
);
268 computed_count
= RDIV (ENTRY_BLOCK_PTR
->count
,
269 ENTRY_BLOCK_PTR
->frequency
);
270 computed_count
*= frequency
* unlikely_count_fraction
;
272 if (computed_count
>= profile_info
->runs
)
277 if ((!profile_info
|| !flag_branch_probabilities
)
278 && (cgraph_get_node (fun
->decl
)->frequency
279 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
285 /* Return true in case BB is probably never executed. */
288 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
290 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
294 /* Return true in case edge E is probably never executed. */
297 probably_never_executed_edge_p (struct function
*fun
, edge e
)
299 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
302 /* Return true if NODE should be optimized for size. */
305 cgraph_optimize_for_size_p (struct cgraph_node
*node
)
309 if (node
&& (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
))
315 /* Return true when current function should always be optimized for size. */
318 optimize_function_for_size_p (struct function
*fun
)
322 if (!fun
|| !fun
->decl
)
324 return cgraph_optimize_for_size_p (cgraph_get_node (fun
->decl
));
327 /* Return true when current function should always be optimized for speed. */
330 optimize_function_for_speed_p (struct function
*fun
)
332 return !optimize_function_for_size_p (fun
);
335 /* Return TRUE when BB should be optimized for size. */
338 optimize_bb_for_size_p (const_basic_block bb
)
340 return optimize_function_for_size_p (cfun
) || !maybe_hot_bb_p (cfun
, bb
);
343 /* Return TRUE when BB should be optimized for speed. */
346 optimize_bb_for_speed_p (const_basic_block bb
)
348 return !optimize_bb_for_size_p (bb
);
351 /* Return TRUE when BB should be optimized for size. */
354 optimize_edge_for_size_p (edge e
)
356 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
359 /* Return TRUE when BB should be optimized for speed. */
362 optimize_edge_for_speed_p (edge e
)
364 return !optimize_edge_for_size_p (e
);
367 /* Return TRUE when BB should be optimized for size. */
370 optimize_insn_for_size_p (void)
372 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
375 /* Return TRUE when BB should be optimized for speed. */
378 optimize_insn_for_speed_p (void)
380 return !optimize_insn_for_size_p ();
383 /* Return TRUE when LOOP should be optimized for size. */
386 optimize_loop_for_size_p (struct loop
*loop
)
388 return optimize_bb_for_size_p (loop
->header
);
391 /* Return TRUE when LOOP should be optimized for speed. */
394 optimize_loop_for_speed_p (struct loop
*loop
)
396 return optimize_bb_for_speed_p (loop
->header
);
399 /* Return TRUE when LOOP nest should be optimized for speed. */
402 optimize_loop_nest_for_speed_p (struct loop
*loop
)
404 struct loop
*l
= loop
;
405 if (optimize_loop_for_speed_p (loop
))
408 while (l
&& l
!= loop
)
410 if (optimize_loop_for_speed_p (l
))
418 while (l
!= loop
&& !l
->next
)
427 /* Return TRUE when LOOP nest should be optimized for size. */
430 optimize_loop_nest_for_size_p (struct loop
*loop
)
432 return !optimize_loop_nest_for_speed_p (loop
);
435 /* Return true when edge E is likely to be well predictable by branch
439 predictable_edge_p (edge e
)
441 if (profile_status
== PROFILE_ABSENT
)
444 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
445 || (REG_BR_PROB_BASE
- e
->probability
446 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
452 /* Set RTL expansion for BB profile. */
455 rtl_profile_for_bb (basic_block bb
)
457 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
460 /* Set RTL expansion for edge profile. */
463 rtl_profile_for_edge (edge e
)
465 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
468 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
470 default_rtl_profile (void)
472 crtl
->maybe_hot_insn_p
= true;
475 /* Return true if the one of outgoing edges is already predicted by
479 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
482 if (!INSN_P (BB_END (bb
)))
484 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
485 if (REG_NOTE_KIND (note
) == REG_BR_PRED
486 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
491 /* This map contains for a basic block the list of predictions for the
494 static struct pointer_map_t
*bb_predictions
;
496 /* Structure representing predictions in tree level. */
498 struct edge_prediction
{
499 struct edge_prediction
*ep_next
;
501 enum br_predictor ep_predictor
;
505 /* Return true if the one of outgoing edges is already predicted by
509 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
511 struct edge_prediction
*i
;
512 void **preds
= pointer_map_contains (bb_predictions
, bb
);
517 for (i
= (struct edge_prediction
*) *preds
; i
; i
= i
->ep_next
)
518 if (i
->ep_predictor
== predictor
)
523 /* Return true when the probability of edge is reliable.
525 The profile guessing code is good at predicting branch outcome (ie.
526 taken/not taken), that is predicted right slightly over 75% of time.
527 It is however notoriously poor on predicting the probability itself.
528 In general the profile appear a lot flatter (with probabilities closer
529 to 50%) than the reality so it is bad idea to use it to drive optimization
530 such as those disabling dynamic branch prediction for well predictable
533 There are two exceptions - edges leading to noreturn edges and edges
534 predicted by number of iterations heuristics are predicted well. This macro
535 should be able to distinguish those, but at the moment it simply check for
536 noreturn heuristic that is only one giving probability over 99% or bellow
537 1%. In future we might want to propagate reliability information across the
538 CFG if we find this information useful on multiple places. */
540 probability_reliable_p (int prob
)
542 return (profile_status
== PROFILE_READ
543 || (profile_status
== PROFILE_GUESSED
544 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
547 /* Same predicate as above, working on edges. */
549 edge_probability_reliable_p (const_edge e
)
551 return probability_reliable_p (e
->probability
);
554 /* Same predicate as edge_probability_reliable_p, working on notes. */
556 br_prob_note_reliable_p (const_rtx note
)
558 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
559 return probability_reliable_p (XINT (note
, 0));
563 predict_insn (rtx insn
, enum br_predictor predictor
, int probability
)
565 gcc_assert (any_condjump_p (insn
));
566 if (!flag_guess_branch_prob
)
569 add_reg_note (insn
, REG_BR_PRED
,
570 gen_rtx_CONCAT (VOIDmode
,
571 GEN_INT ((int) predictor
),
572 GEN_INT ((int) probability
)));
575 /* Predict insn by given predictor. */
578 predict_insn_def (rtx insn
, 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_insn (insn
, predictor
, probability
);
589 /* Predict edge E with given probability if possible. */
592 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
595 last_insn
= BB_END (e
->src
);
597 /* We can store the branch prediction information only about
598 conditional jumps. */
599 if (!any_condjump_p (last_insn
))
602 /* We always store probability of branching. */
603 if (e
->flags
& EDGE_FALLTHRU
)
604 probability
= REG_BR_PROB_BASE
- probability
;
606 predict_insn (last_insn
, predictor
, probability
);
609 /* Predict edge E with the given PROBABILITY. */
611 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
613 gcc_assert (profile_status
!= PROFILE_GUESSED
);
614 if ((e
->src
!= ENTRY_BLOCK_PTR
&& EDGE_COUNT (e
->src
->succs
) > 1)
615 && flag_guess_branch_prob
&& optimize
)
617 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
618 void **preds
= pointer_map_insert (bb_predictions
, e
->src
);
620 i
->ep_next
= (struct edge_prediction
*) *preds
;
622 i
->ep_probability
= probability
;
623 i
->ep_predictor
= predictor
;
628 /* Remove all predictions on given basic block that are attached
631 remove_predictions_associated_with_edge (edge e
)
638 preds
= pointer_map_contains (bb_predictions
, e
->src
);
642 struct edge_prediction
**prediction
= (struct edge_prediction
**) preds
;
643 struct edge_prediction
*next
;
647 if ((*prediction
)->ep_edge
== e
)
649 next
= (*prediction
)->ep_next
;
654 prediction
= &((*prediction
)->ep_next
);
659 /* Clears the list of predictions stored for BB. */
662 clear_bb_predictions (basic_block bb
)
664 void **preds
= pointer_map_contains (bb_predictions
, bb
);
665 struct edge_prediction
*pred
, *next
;
670 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= next
)
672 next
= pred
->ep_next
;
678 /* Return true when we can store prediction on insn INSN.
679 At the moment we represent predictions only on conditional
680 jumps, not at computed jump or other complicated cases. */
682 can_predict_insn_p (const_rtx insn
)
684 return (JUMP_P (insn
)
685 && any_condjump_p (insn
)
686 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
689 /* Predict edge E by given predictor if possible. */
692 predict_edge_def (edge e
, enum br_predictor predictor
,
693 enum prediction taken
)
695 int probability
= predictor_info
[(int) predictor
].hitrate
;
698 probability
= REG_BR_PROB_BASE
- probability
;
700 predict_edge (e
, predictor
, probability
);
703 /* Invert all branch predictions or probability notes in the INSN. This needs
704 to be done each time we invert the condition used by the jump. */
707 invert_br_probabilities (rtx insn
)
711 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
712 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
713 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
714 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
715 XEXP (XEXP (note
, 0), 1)
716 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
719 /* Dump information about the branch prediction to the output file. */
722 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
723 basic_block bb
, int used
)
731 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
732 if (! (e
->flags
& EDGE_FALLTHRU
))
735 fprintf (file
, " %s heuristics%s: %.1f%%",
736 predictor_info
[predictor
].name
,
737 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
741 fprintf (file
, " exec ");
742 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, bb
->count
);
745 fprintf (file
, " hit ");
746 fprintf (file
, HOST_WIDEST_INT_PRINT_DEC
, e
->count
);
747 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
751 fprintf (file
, "\n");
754 /* We can not predict the probabilities of outgoing edges of bb. Set them
755 evenly and hope for the best. */
757 set_even_probabilities (basic_block bb
)
763 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
764 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
766 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
767 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
768 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
773 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
774 note if not already present. Remove now useless REG_BR_PRED notes. */
777 combine_predictions_for_insn (rtx insn
, basic_block bb
)
782 int best_probability
= PROB_EVEN
;
783 enum br_predictor best_predictor
= END_PREDICTORS
;
784 int combined_probability
= REG_BR_PROB_BASE
/ 2;
786 bool first_match
= false;
789 if (!can_predict_insn_p (insn
))
791 set_even_probabilities (bb
);
795 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
796 pnote
= ®_NOTES (insn
);
798 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
801 /* We implement "first match" heuristics and use probability guessed
802 by predictor with smallest index. */
803 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
804 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
806 enum br_predictor predictor
= ((enum br_predictor
)
807 INTVAL (XEXP (XEXP (note
, 0), 0)));
808 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
811 if (best_predictor
> predictor
)
812 best_probability
= probability
, best_predictor
= predictor
;
814 d
= (combined_probability
* probability
815 + (REG_BR_PROB_BASE
- combined_probability
)
816 * (REG_BR_PROB_BASE
- probability
));
818 /* Use FP math to avoid overflows of 32bit integers. */
820 /* If one probability is 0% and one 100%, avoid division by zero. */
821 combined_probability
= REG_BR_PROB_BASE
/ 2;
823 combined_probability
= (((double) combined_probability
) * probability
824 * REG_BR_PROB_BASE
/ d
+ 0.5);
827 /* Decide which heuristic to use. In case we didn't match anything,
828 use no_prediction heuristic, in case we did match, use either
829 first match or Dempster-Shaffer theory depending on the flags. */
831 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
835 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
836 combined_probability
, bb
, true);
839 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
841 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
846 combined_probability
= best_probability
;
847 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
851 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
853 enum br_predictor predictor
= ((enum br_predictor
)
854 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
855 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
857 dump_prediction (dump_file
, predictor
, probability
, bb
,
858 !first_match
|| best_predictor
== predictor
);
859 *pnote
= XEXP (*pnote
, 1);
862 pnote
= &XEXP (*pnote
, 1);
867 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
869 /* Save the prediction into CFG in case we are seeing non-degenerated
871 if (!single_succ_p (bb
))
873 BRANCH_EDGE (bb
)->probability
= combined_probability
;
874 FALLTHRU_EDGE (bb
)->probability
875 = REG_BR_PROB_BASE
- combined_probability
;
878 else if (!single_succ_p (bb
))
880 int prob
= XINT (prob_note
, 0);
882 BRANCH_EDGE (bb
)->probability
= prob
;
883 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
886 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
889 /* Combine predictions into single probability and store them into CFG.
890 Remove now useless prediction entries. */
893 combine_predictions_for_bb (basic_block bb
)
895 int best_probability
= PROB_EVEN
;
896 enum br_predictor best_predictor
= END_PREDICTORS
;
897 int combined_probability
= REG_BR_PROB_BASE
/ 2;
899 bool first_match
= false;
901 struct edge_prediction
*pred
;
903 edge e
, first
= NULL
, second
= NULL
;
907 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
908 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
911 if (first
&& !second
)
917 /* When there is no successor or only one choice, prediction is easy.
919 We are lazy for now and predict only basic blocks with two outgoing
920 edges. It is possible to predict generic case too, but we have to
921 ignore first match heuristics and do more involved combining. Implement
926 set_even_probabilities (bb
);
927 clear_bb_predictions (bb
);
929 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
935 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
937 preds
= pointer_map_contains (bb_predictions
, bb
);
940 /* We implement "first match" heuristics and use probability guessed
941 by predictor with smallest index. */
942 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
944 enum br_predictor predictor
= pred
->ep_predictor
;
945 int probability
= pred
->ep_probability
;
947 if (pred
->ep_edge
!= first
)
948 probability
= REG_BR_PROB_BASE
- probability
;
951 /* First match heuristics would be widly confused if we predicted
953 if (best_predictor
> predictor
)
955 struct edge_prediction
*pred2
;
956 int prob
= probability
;
958 for (pred2
= (struct edge_prediction
*) *preds
; pred2
; pred2
= pred2
->ep_next
)
959 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
961 int probability2
= pred
->ep_probability
;
963 if (pred2
->ep_edge
!= first
)
964 probability2
= REG_BR_PROB_BASE
- probability2
;
966 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
967 (probability2
< REG_BR_PROB_BASE
/ 2))
970 /* If the same predictor later gave better result, go for it! */
971 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
972 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
976 best_probability
= prob
, best_predictor
= predictor
;
979 d
= (combined_probability
* probability
980 + (REG_BR_PROB_BASE
- combined_probability
)
981 * (REG_BR_PROB_BASE
- probability
));
983 /* Use FP math to avoid overflows of 32bit integers. */
985 /* If one probability is 0% and one 100%, avoid division by zero. */
986 combined_probability
= REG_BR_PROB_BASE
/ 2;
988 combined_probability
= (((double) combined_probability
)
990 * REG_BR_PROB_BASE
/ d
+ 0.5);
994 /* Decide which heuristic to use. In case we didn't match anything,
995 use no_prediction heuristic, in case we did match, use either
996 first match or Dempster-Shaffer theory depending on the flags. */
998 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1002 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
1005 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1007 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1012 combined_probability
= best_probability
;
1013 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
1017 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1019 enum br_predictor predictor
= pred
->ep_predictor
;
1020 int probability
= pred
->ep_probability
;
1022 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
1023 probability
= REG_BR_PROB_BASE
- probability
;
1024 dump_prediction (dump_file
, predictor
, probability
, bb
,
1025 !first_match
|| best_predictor
== predictor
);
1028 clear_bb_predictions (bb
);
1032 first
->probability
= combined_probability
;
1033 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1037 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1038 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1040 T1 and T2 should be one of the following cases:
1041 1. T1 is SSA_NAME, T2 is NULL
1042 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1043 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1046 strips_small_constant (tree t1
, tree t2
)
1053 else if (TREE_CODE (t1
) == SSA_NAME
)
1055 else if (host_integerp (t1
, 0))
1056 value
= tree_low_cst (t1
, 0);
1062 else if (host_integerp (t2
, 0))
1063 value
= tree_low_cst (t2
, 0);
1064 else if (TREE_CODE (t2
) == SSA_NAME
)
1072 if (value
<= 4 && value
>= -4)
1078 /* Return the SSA_NAME in T or T's operands.
1079 Return NULL if SSA_NAME cannot be found. */
1082 get_base_value (tree t
)
1084 if (TREE_CODE (t
) == SSA_NAME
)
1087 if (!BINARY_CLASS_P (t
))
1090 switch (TREE_OPERAND_LENGTH (t
))
1093 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1095 return strips_small_constant (TREE_OPERAND (t
, 0),
1096 TREE_OPERAND (t
, 1));
1102 /* Check the compare STMT in LOOP. If it compares an induction
1103 variable to a loop invariant, return true, and save
1104 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1105 Otherwise return false and set LOOP_INVAIANT to NULL. */
1108 is_comparison_with_loop_invariant_p (gimple stmt
, struct loop
*loop
,
1109 tree
*loop_invariant
,
1110 enum tree_code
*compare_code
,
1114 tree op0
, op1
, bound
, base
;
1116 enum tree_code code
;
1119 code
= gimple_cond_code (stmt
);
1120 *loop_invariant
= NULL
;
1136 op0
= gimple_cond_lhs (stmt
);
1137 op1
= gimple_cond_rhs (stmt
);
1139 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1140 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1142 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1144 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1146 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1147 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1149 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1150 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1153 if (integer_zerop (iv0
.step
))
1155 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1156 code
= invert_tree_comparison (code
, false);
1159 if (host_integerp (iv1
.step
, 0))
1168 if (host_integerp (iv0
.step
, 0))
1174 if (TREE_CODE (bound
) != INTEGER_CST
)
1175 bound
= get_base_value (bound
);
1178 if (TREE_CODE (base
) != INTEGER_CST
)
1179 base
= get_base_value (base
);
1183 *loop_invariant
= bound
;
1184 *compare_code
= code
;
1186 *loop_iv_base
= base
;
1190 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1193 expr_coherent_p (tree t1
, tree t2
)
1196 tree ssa_name_1
= NULL
;
1197 tree ssa_name_2
= NULL
;
1199 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1200 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1205 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1207 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1210 /* Check to see if t1 is expressed/defined with t2. */
1211 stmt
= SSA_NAME_DEF_STMT (t1
);
1212 gcc_assert (stmt
!= NULL
);
1213 if (is_gimple_assign (stmt
))
1215 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1216 if (ssa_name_1
&& ssa_name_1
== t2
)
1220 /* Check to see if t2 is expressed/defined with t1. */
1221 stmt
= SSA_NAME_DEF_STMT (t2
);
1222 gcc_assert (stmt
!= NULL
);
1223 if (is_gimple_assign (stmt
))
1225 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1226 if (ssa_name_2
&& ssa_name_2
== t1
)
1230 /* Compare if t1 and t2's def_stmts are identical. */
1231 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1237 /* Predict branch probability of BB when BB contains a branch that compares
1238 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1239 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1242 for (int i = 0; i < bound; i++) {
1249 In this loop, we will predict the branch inside the loop to be taken. */
1252 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1253 tree loop_bound_var
,
1254 tree loop_iv_base_var
,
1255 enum tree_code loop_bound_code
,
1256 int loop_bound_step
)
1259 tree compare_var
, compare_base
;
1260 enum tree_code compare_code
;
1261 tree compare_step_var
;
1265 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1266 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1267 || predicted_by_p (bb
, PRED_LOOP_EXIT
))
1270 stmt
= last_stmt (bb
);
1271 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1273 if (!is_comparison_with_loop_invariant_p (stmt
, loop
, &compare_var
,
1279 /* Find the taken edge. */
1280 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1281 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1284 /* When comparing an IV to a loop invariant, NE is more likely to be
1285 taken while EQ is more likely to be not-taken. */
1286 if (compare_code
== NE_EXPR
)
1288 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1291 else if (compare_code
== EQ_EXPR
)
1293 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1297 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1300 /* If loop bound, base and compare bound are all constants, we can
1301 calculate the probability directly. */
1302 if (host_integerp (loop_bound_var
, 0)
1303 && host_integerp (compare_var
, 0)
1304 && host_integerp (compare_base
, 0))
1307 bool of
, overflow
= false;
1308 double_int mod
, compare_count
, tem
, loop_count
;
1310 double_int loop_bound
= tree_to_double_int (loop_bound_var
);
1311 double_int compare_bound
= tree_to_double_int (compare_var
);
1312 double_int base
= tree_to_double_int (compare_base
);
1313 double_int compare_step
= tree_to_double_int (compare_step_var
);
1315 /* (loop_bound - base) / compare_step */
1316 tem
= loop_bound
.sub_with_overflow (base
, &of
);
1318 loop_count
= tem
.divmod_with_overflow (compare_step
,
1323 if ((!compare_step
.is_negative ())
1324 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1326 /* (loop_bound - compare_bound) / compare_step */
1327 tem
= loop_bound
.sub_with_overflow (compare_bound
, &of
);
1329 compare_count
= tem
.divmod_with_overflow (compare_step
,
1336 /* (compare_bound - base) / compare_step */
1337 tem
= compare_bound
.sub_with_overflow (base
, &of
);
1339 compare_count
= tem
.divmod_with_overflow (compare_step
,
1344 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1346 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1348 if (compare_count
.is_negative ())
1349 compare_count
= double_int_zero
;
1350 if (loop_count
.is_negative ())
1351 loop_count
= double_int_zero
;
1352 if (loop_count
.is_zero ())
1354 else if (compare_count
.scmp (loop_count
) == 1)
1355 probability
= REG_BR_PROB_BASE
;
1358 /* If loop_count is too big, such that REG_BR_PROB_BASE * loop_count
1359 could overflow, shift both loop_count and compare_count right
1360 a bit so that it doesn't overflow. Note both counts are known not
1361 to be negative at this point. */
1362 int clz_bits
= clz_hwi (loop_count
.high
);
1363 gcc_assert (REG_BR_PROB_BASE
< 32768);
1366 loop_count
.arshift (16 - clz_bits
, HOST_BITS_PER_DOUBLE_INT
);
1367 compare_count
.arshift (16 - clz_bits
, HOST_BITS_PER_DOUBLE_INT
);
1369 tem
= compare_count
.mul_with_sign (double_int::from_shwi
1370 (REG_BR_PROB_BASE
), true, &of
);
1372 tem
= tem
.divmod (loop_count
, true, TRUNC_DIV_EXPR
, &mod
);
1373 probability
= tem
.to_uhwi ();
1377 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1382 if (expr_coherent_p (loop_bound_var
, compare_var
))
1384 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1385 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1386 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1387 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1388 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1389 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1390 else if (loop_bound_code
== NE_EXPR
)
1392 /* If the loop backedge condition is "(i != bound)", we do
1393 the comparison based on the step of IV:
1394 * step < 0 : backedge condition is like (i > bound)
1395 * step > 0 : backedge condition is like (i < bound) */
1396 gcc_assert (loop_bound_step
!= 0);
1397 if (loop_bound_step
> 0
1398 && (compare_code
== LT_EXPR
1399 || compare_code
== LE_EXPR
))
1400 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1401 else if (loop_bound_step
< 0
1402 && (compare_code
== GT_EXPR
1403 || compare_code
== GE_EXPR
))
1404 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1406 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1409 /* The branch is predicted not-taken if loop_bound_code is
1410 opposite with compare_code. */
1411 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1413 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1416 for (i = s; i < h; i++)
1418 The branch should be predicted taken. */
1419 if (loop_bound_step
> 0
1420 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1421 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1422 else if (loop_bound_step
< 0
1423 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1424 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1426 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1430 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1431 exits are resulted from short-circuit conditions that will generate an
1434 if (foo() || global > 10)
1437 This will be translated into:
1442 if foo() goto BB6 else goto BB5
1444 if global > 10 goto BB6 else goto BB7
1448 iftmp = (PHI 0(BB5), 1(BB6))
1449 if iftmp == 1 goto BB8 else goto BB3
1451 outside of the loop...
1453 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1454 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1455 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1456 exits to predict them using PRED_LOOP_EXIT. */
1459 predict_extra_loop_exits (edge exit_edge
)
1462 bool check_value_one
;
1464 tree cmp_rhs
, cmp_lhs
;
1465 gimple cmp_stmt
= last_stmt (exit_edge
->src
);
1467 if (!cmp_stmt
|| gimple_code (cmp_stmt
) != GIMPLE_COND
)
1469 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1470 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1471 if (!TREE_CONSTANT (cmp_rhs
)
1472 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1474 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1477 /* If check_value_one is true, only the phi_args with value '1' will lead
1478 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1480 check_value_one
= (((integer_onep (cmp_rhs
))
1481 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1482 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1484 phi_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1485 if (!phi_stmt
|| gimple_code (phi_stmt
) != GIMPLE_PHI
)
1488 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1492 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1493 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1495 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1497 if ((check_value_one
^ integer_onep (val
)) == 1)
1499 if (EDGE_COUNT (e
->src
->succs
) != 1)
1501 predict_paths_leading_to_edge (e
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1505 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1506 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXIT
, NOT_TAKEN
);
1510 /* Predict edge probabilities by exploiting loop structure. */
1513 predict_loops (void)
1518 /* Try to predict out blocks in a loop that are not part of a
1520 FOR_EACH_LOOP (li
, loop
, 0)
1522 basic_block bb
, *bbs
;
1523 unsigned j
, n_exits
;
1525 struct tree_niter_desc niter_desc
;
1527 struct nb_iter_bound
*nb_iter
;
1528 enum tree_code loop_bound_code
= ERROR_MARK
;
1529 tree loop_bound_step
= NULL
;
1530 tree loop_bound_var
= NULL
;
1531 tree loop_iv_base
= NULL
;
1534 exits
= get_loop_exit_edges (loop
);
1535 n_exits
= exits
.length ();
1542 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1545 HOST_WIDE_INT nitercst
;
1546 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1548 enum br_predictor predictor
;
1550 predict_extra_loop_exits (ex
);
1552 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1553 niter
= niter_desc
.niter
;
1554 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1555 niter
= loop_niter_by_eval (loop
, ex
);
1557 if (TREE_CODE (niter
) == INTEGER_CST
)
1559 if (host_integerp (niter
, 1)
1561 && compare_tree_int (niter
, max
- 1) == -1)
1562 nitercst
= tree_low_cst (niter
, 1) + 1;
1565 predictor
= PRED_LOOP_ITERATIONS
;
1567 /* If we have just one exit and we can derive some information about
1568 the number of iterations of the loop from the statements inside
1569 the loop, use it to predict this exit. */
1570 else if (n_exits
== 1)
1572 nitercst
= estimated_stmt_executions_int (loop
);
1578 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1583 /* If the prediction for number of iterations is zero, do not
1584 predict the exit edges. */
1588 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1589 predict_edge (ex
, predictor
, probability
);
1593 /* Find information about loop bound variables. */
1594 for (nb_iter
= loop
->bounds
; nb_iter
;
1595 nb_iter
= nb_iter
->next
)
1597 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1599 stmt
= nb_iter
->stmt
;
1602 if (!stmt
&& last_stmt (loop
->header
)
1603 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1604 stmt
= last_stmt (loop
->header
);
1606 is_comparison_with_loop_invariant_p (stmt
, loop
,
1612 bbs
= get_loop_body (loop
);
1614 for (j
= 0; j
< loop
->num_nodes
; j
++)
1616 int header_found
= 0;
1622 /* Bypass loop heuristics on continue statement. These
1623 statements construct loops via "non-loop" constructs
1624 in the source language and are better to be handled
1626 if (predicted_by_p (bb
, PRED_CONTINUE
))
1629 /* Loop branch heuristics - predict an edge back to a
1630 loop's head as taken. */
1631 if (bb
== loop
->latch
)
1633 e
= find_edge (loop
->latch
, loop
->header
);
1637 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1641 /* Loop exit heuristics - predict an edge exiting the loop if the
1642 conditional has no loop header successors as not taken. */
1644 /* If we already used more reliable loop exit predictors, do not
1645 bother with PRED_LOOP_EXIT. */
1646 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1647 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1649 /* For loop with many exits we don't want to predict all exits
1650 with the pretty large probability, because if all exits are
1651 considered in row, the loop would be predicted to iterate
1652 almost never. The code to divide probability by number of
1653 exits is very rough. It should compute the number of exits
1654 taken in each patch through function (not the overall number
1655 of exits that might be a lot higher for loops with wide switch
1656 statements in them) and compute n-th square root.
1658 We limit the minimal probability by 2% to avoid
1659 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1660 as this was causing regression in perl benchmark containing such
1663 int probability
= ((REG_BR_PROB_BASE
1664 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1666 if (probability
< HITRATE (2))
1667 probability
= HITRATE (2);
1668 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1669 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1670 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1671 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1674 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1676 tree_low_cst (loop_bound_step
, 0));
1679 /* Free basic blocks from get_loop_body. */
1684 /* Attempt to predict probabilities of BB outgoing edges using local
1687 bb_estimate_probability_locally (basic_block bb
)
1689 rtx last_insn
= BB_END (bb
);
1692 if (! can_predict_insn_p (last_insn
))
1694 cond
= get_condition (last_insn
, NULL
, false, false);
1698 /* Try "pointer heuristic."
1699 A comparison ptr == 0 is predicted as false.
1700 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1701 if (COMPARISON_P (cond
)
1702 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1703 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1705 if (GET_CODE (cond
) == EQ
)
1706 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1707 else if (GET_CODE (cond
) == NE
)
1708 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1712 /* Try "opcode heuristic."
1713 EQ tests are usually false and NE tests are usually true. Also,
1714 most quantities are positive, so we can make the appropriate guesses
1715 about signed comparisons against zero. */
1716 switch (GET_CODE (cond
))
1719 /* Unconditional branch. */
1720 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1721 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1726 /* Floating point comparisons appears to behave in a very
1727 unpredictable way because of special role of = tests in
1729 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1731 /* Comparisons with 0 are often used for booleans and there is
1732 nothing useful to predict about them. */
1733 else if (XEXP (cond
, 1) == const0_rtx
1734 || XEXP (cond
, 0) == const0_rtx
)
1737 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1742 /* Floating point comparisons appears to behave in a very
1743 unpredictable way because of special role of = tests in
1745 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1747 /* Comparisons with 0 are often used for booleans and there is
1748 nothing useful to predict about them. */
1749 else if (XEXP (cond
, 1) == const0_rtx
1750 || XEXP (cond
, 0) == const0_rtx
)
1753 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1757 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1761 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1766 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1767 || XEXP (cond
, 1) == constm1_rtx
)
1768 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1773 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1774 || XEXP (cond
, 1) == constm1_rtx
)
1775 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1783 /* Set edge->probability for each successor edge of BB. */
1785 guess_outgoing_edge_probabilities (basic_block bb
)
1787 bb_estimate_probability_locally (bb
);
1788 combine_predictions_for_insn (BB_END (bb
), bb
);
1791 static tree
expr_expected_value (tree
, bitmap
);
1793 /* Helper function for expr_expected_value. */
1796 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1797 tree op1
, bitmap visited
)
1801 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1803 if (TREE_CONSTANT (op0
))
1806 if (code
!= SSA_NAME
)
1809 def
= SSA_NAME_DEF_STMT (op0
);
1811 /* If we were already here, break the infinite cycle. */
1812 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1815 if (gimple_code (def
) == GIMPLE_PHI
)
1817 /* All the arguments of the PHI node must have the same constant
1819 int i
, n
= gimple_phi_num_args (def
);
1820 tree val
= NULL
, new_val
;
1822 for (i
= 0; i
< n
; i
++)
1824 tree arg
= PHI_ARG_DEF (def
, i
);
1826 /* If this PHI has itself as an argument, we cannot
1827 determine the string length of this argument. However,
1828 if we can find an expected constant value for the other
1829 PHI args then we can still be sure that this is
1830 likely a constant. So be optimistic and just
1831 continue with the next argument. */
1832 if (arg
== PHI_RESULT (def
))
1835 new_val
= expr_expected_value (arg
, visited
);
1840 else if (!operand_equal_p (val
, new_val
, false))
1845 if (is_gimple_assign (def
))
1847 if (gimple_assign_lhs (def
) != op0
)
1850 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1851 gimple_assign_rhs1 (def
),
1852 gimple_assign_rhs_code (def
),
1853 gimple_assign_rhs2 (def
),
1857 if (is_gimple_call (def
))
1859 tree decl
= gimple_call_fndecl (def
);
1862 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1863 switch (DECL_FUNCTION_CODE (decl
))
1865 case BUILT_IN_EXPECT
:
1868 if (gimple_call_num_args (def
) != 2)
1870 val
= gimple_call_arg (def
, 0);
1871 if (TREE_CONSTANT (val
))
1873 return gimple_call_arg (def
, 1);
1876 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1877 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1878 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1879 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1880 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1881 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1882 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1883 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1884 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1885 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1886 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1887 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1888 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1889 /* Assume that any given atomic operation has low contention,
1890 and thus the compare-and-swap operation succeeds. */
1891 return boolean_true_node
;
1898 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1901 op0
= expr_expected_value (op0
, visited
);
1904 op1
= expr_expected_value (op1
, visited
);
1907 res
= fold_build2 (code
, type
, op0
, op1
);
1908 if (TREE_CONSTANT (res
))
1912 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1915 op0
= expr_expected_value (op0
, visited
);
1918 res
= fold_build1 (code
, type
, op0
);
1919 if (TREE_CONSTANT (res
))
1926 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1927 The function is used by builtin_expect branch predictor so the evidence
1928 must come from this construct and additional possible constant folding.
1930 We may want to implement more involved value guess (such as value range
1931 propagation based prediction), but such tricks shall go to new
1935 expr_expected_value (tree expr
, bitmap visited
)
1937 enum tree_code code
;
1940 if (TREE_CONSTANT (expr
))
1943 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1944 return expr_expected_value_1 (TREE_TYPE (expr
),
1945 op0
, code
, op1
, visited
);
1949 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1950 we no longer need. */
1952 strip_predict_hints (void)
1960 gimple_stmt_iterator bi
;
1961 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
1963 gimple stmt
= gsi_stmt (bi
);
1965 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
1967 gsi_remove (&bi
, true);
1970 else if (gimple_code (stmt
) == GIMPLE_CALL
)
1972 tree fndecl
= gimple_call_fndecl (stmt
);
1975 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
1976 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
1977 && gimple_call_num_args (stmt
) == 2)
1979 var
= gimple_call_lhs (stmt
);
1983 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
1984 gsi_replace (&bi
, ass_stmt
, true);
1988 gsi_remove (&bi
, true);
1999 /* Predict using opcode of the last statement in basic block. */
2001 tree_predict_by_opcode (basic_block bb
)
2003 gimple stmt
= last_stmt (bb
);
2012 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2014 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2015 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2017 op0
= gimple_cond_lhs (stmt
);
2018 op1
= gimple_cond_rhs (stmt
);
2019 cmp
= gimple_cond_code (stmt
);
2020 type
= TREE_TYPE (op0
);
2021 visited
= BITMAP_ALLOC (NULL
);
2022 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
);
2023 BITMAP_FREE (visited
);
2026 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2028 gcc_assert (percent
>= 0 && percent
<= 100);
2029 if (integer_zerop (val
))
2030 percent
= 100 - percent
;
2031 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2033 /* Try "pointer heuristic."
2034 A comparison ptr == 0 is predicted as false.
2035 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2036 if (POINTER_TYPE_P (type
))
2039 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2040 else if (cmp
== NE_EXPR
)
2041 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2045 /* Try "opcode heuristic."
2046 EQ tests are usually false and NE tests are usually true. Also,
2047 most quantities are positive, so we can make the appropriate guesses
2048 about signed comparisons against zero. */
2053 /* Floating point comparisons appears to behave in a very
2054 unpredictable way because of special role of = tests in
2056 if (FLOAT_TYPE_P (type
))
2058 /* Comparisons with 0 are often used for booleans and there is
2059 nothing useful to predict about them. */
2060 else if (integer_zerop (op0
) || integer_zerop (op1
))
2063 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2068 /* Floating point comparisons appears to behave in a very
2069 unpredictable way because of special role of = tests in
2071 if (FLOAT_TYPE_P (type
))
2073 /* Comparisons with 0 are often used for booleans and there is
2074 nothing useful to predict about them. */
2075 else if (integer_zerop (op0
)
2076 || integer_zerop (op1
))
2079 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2083 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2086 case UNORDERED_EXPR
:
2087 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2092 if (integer_zerop (op1
)
2093 || integer_onep (op1
)
2094 || integer_all_onesp (op1
)
2097 || real_minus_onep (op1
))
2098 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2103 if (integer_zerop (op1
)
2104 || integer_onep (op1
)
2105 || integer_all_onesp (op1
)
2108 || real_minus_onep (op1
))
2109 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2117 /* Try to guess whether the value of return means error code. */
2119 static enum br_predictor
2120 return_prediction (tree val
, enum prediction
*prediction
)
2124 return PRED_NO_PREDICTION
;
2125 /* Different heuristics for pointers and scalars. */
2126 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2128 /* NULL is usually not returned. */
2129 if (integer_zerop (val
))
2131 *prediction
= NOT_TAKEN
;
2132 return PRED_NULL_RETURN
;
2135 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2137 /* Negative return values are often used to indicate
2139 if (TREE_CODE (val
) == INTEGER_CST
2140 && tree_int_cst_sgn (val
) < 0)
2142 *prediction
= NOT_TAKEN
;
2143 return PRED_NEGATIVE_RETURN
;
2145 /* Constant return values seems to be commonly taken.
2146 Zero/one often represent booleans so exclude them from the
2148 if (TREE_CONSTANT (val
)
2149 && (!integer_zerop (val
) && !integer_onep (val
)))
2151 *prediction
= TAKEN
;
2152 return PRED_CONST_RETURN
;
2155 return PRED_NO_PREDICTION
;
2158 /* Find the basic block with return expression and look up for possible
2159 return value trying to apply RETURN_PREDICTION heuristics. */
2161 apply_return_prediction (void)
2163 gimple return_stmt
= NULL
;
2167 int phi_num_args
, i
;
2168 enum br_predictor pred
;
2169 enum prediction direction
;
2172 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
2174 return_stmt
= last_stmt (e
->src
);
2176 && gimple_code (return_stmt
) == GIMPLE_RETURN
)
2181 return_val
= gimple_return_retval (return_stmt
);
2184 if (TREE_CODE (return_val
) != SSA_NAME
2185 || !SSA_NAME_DEF_STMT (return_val
)
2186 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2188 phi
= SSA_NAME_DEF_STMT (return_val
);
2189 phi_num_args
= gimple_phi_num_args (phi
);
2190 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2192 /* Avoid the degenerate case where all return values form the function
2193 belongs to same category (ie they are all positive constants)
2194 so we can hardly say something about them. */
2195 for (i
= 1; i
< phi_num_args
; i
++)
2196 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2198 if (i
!= phi_num_args
)
2199 for (i
= 0; i
< phi_num_args
; i
++)
2201 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2202 if (pred
!= PRED_NO_PREDICTION
)
2203 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2208 /* Look for basic block that contains unlikely to happen events
2209 (such as noreturn calls) and mark all paths leading to execution
2210 of this basic blocks as unlikely. */
2213 tree_bb_level_predictions (void)
2216 bool has_return_edges
= false;
2220 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
2221 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2223 has_return_edges
= true;
2227 apply_return_prediction ();
2231 gimple_stmt_iterator gsi
;
2233 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2235 gimple stmt
= gsi_stmt (gsi
);
2238 if (is_gimple_call (stmt
))
2240 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2241 && has_return_edges
)
2242 predict_paths_leading_to (bb
, PRED_NORETURN
,
2244 decl
= gimple_call_fndecl (stmt
);
2246 && lookup_attribute ("cold",
2247 DECL_ATTRIBUTES (decl
)))
2248 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2251 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2253 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2254 gimple_predict_outcome (stmt
));
2255 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2256 hints to callers. */
2262 #ifdef ENABLE_CHECKING
2264 /* Callback for pointer_map_traverse, asserts that the pointer map is
2268 assert_is_empty (const void *key ATTRIBUTE_UNUSED
, void **value
,
2269 void *data ATTRIBUTE_UNUSED
)
2271 gcc_assert (!*value
);
2276 /* Predict branch probabilities and estimate profile for basic block BB. */
2279 tree_estimate_probability_bb (basic_block bb
)
2285 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2287 /* Predict edges to user labels with attributes. */
2288 if (e
->dest
!= EXIT_BLOCK_PTR
)
2290 gimple_stmt_iterator gi
;
2291 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2293 gimple stmt
= gsi_stmt (gi
);
2296 if (gimple_code (stmt
) != GIMPLE_LABEL
)
2298 decl
= gimple_label_label (stmt
);
2299 if (DECL_ARTIFICIAL (decl
))
2302 /* Finally, we have a user-defined label. */
2303 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2304 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2305 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2306 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2310 /* Predict early returns to be probable, as we've already taken
2311 care for error returns and other cases are often used for
2312 fast paths through function.
2314 Since we've already removed the return statements, we are
2315 looking for CFG like:
2325 if (e
->dest
!= bb
->next_bb
2326 && e
->dest
!= EXIT_BLOCK_PTR
2327 && single_succ_p (e
->dest
)
2328 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR
2329 && (last
= last_stmt (e
->dest
)) != NULL
2330 && gimple_code (last
) == GIMPLE_RETURN
)
2335 if (single_succ_p (bb
))
2337 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2338 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2339 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2340 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2341 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2344 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2345 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2346 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2347 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2350 /* Look for block we are guarding (ie we dominate it,
2351 but it doesn't postdominate us). */
2352 if (e
->dest
!= EXIT_BLOCK_PTR
&& e
->dest
!= bb
2353 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2354 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2356 gimple_stmt_iterator bi
;
2358 /* The call heuristic claims that a guarded function call
2359 is improbable. This is because such calls are often used
2360 to signal exceptional situations such as printing error
2362 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2365 gimple stmt
= gsi_stmt (bi
);
2366 if (is_gimple_call (stmt
)
2367 /* Constant and pure calls are hardly used to signalize
2368 something exceptional. */
2369 && gimple_has_side_effects (stmt
))
2371 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2377 tree_predict_by_opcode (bb
);
2380 /* Predict branch probabilities and estimate profile of the tree CFG.
2381 This function can be called from the loop optimizers to recompute
2382 the profile information. */
2385 tree_estimate_probability (void)
2389 add_noreturn_fake_exit_edges ();
2390 connect_infinite_loops_to_exit ();
2391 /* We use loop_niter_by_eval, which requires that the loops have
2393 create_preheaders (CP_SIMPLE_PREHEADERS
);
2394 calculate_dominance_info (CDI_POST_DOMINATORS
);
2396 bb_predictions
= pointer_map_create ();
2397 tree_bb_level_predictions ();
2398 record_loop_exits ();
2400 if (number_of_loops (cfun
) > 1)
2404 tree_estimate_probability_bb (bb
);
2407 combine_predictions_for_bb (bb
);
2409 #ifdef ENABLE_CHECKING
2410 pointer_map_traverse (bb_predictions
, assert_is_empty
, NULL
);
2412 pointer_map_destroy (bb_predictions
);
2413 bb_predictions
= NULL
;
2415 estimate_bb_frequencies (false);
2416 free_dominance_info (CDI_POST_DOMINATORS
);
2417 remove_fake_exit_edges ();
2420 /* Predict branch probabilities and estimate profile of the tree CFG.
2421 This is the driver function for PASS_PROFILE. */
2424 tree_estimate_probability_driver (void)
2428 loop_optimizer_init (LOOPS_NORMAL
);
2429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2430 flow_loops_dump (dump_file
, NULL
, 0);
2432 mark_irreducible_loops ();
2434 nb_loops
= number_of_loops (cfun
);
2438 tree_estimate_probability ();
2443 loop_optimizer_finalize ();
2444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2445 gimple_dump_cfg (dump_file
, dump_flags
);
2446 if (profile_status
== PROFILE_ABSENT
)
2447 profile_status
= PROFILE_GUESSED
;
2451 /* Predict edges to successors of CUR whose sources are not postdominated by
2452 BB by PRED and recurse to all postdominators. */
2455 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2456 enum br_predictor pred
,
2457 enum prediction taken
,
2464 /* We are looking for all edges forming edge cut induced by
2465 set of all blocks postdominated by BB. */
2466 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2467 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2468 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2474 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2475 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2477 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2479 /* See if there is an edge from e->src that is not abnormal
2480 and does not lead to BB. */
2481 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2483 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2484 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2490 /* If there is non-abnormal path leaving e->src, predict edge
2491 using predictor. Otherwise we need to look for paths
2494 The second may lead to infinite loop in the case we are predicitng
2495 regions that are only reachable by abnormal edges. We simply
2496 prevent visiting given BB twice. */
2498 predict_edge_def (e
, pred
, taken
);
2499 else if (bitmap_set_bit (visited
, e
->src
->index
))
2500 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2502 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2504 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2505 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2508 /* Sets branch probabilities according to PREDiction and
2512 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2513 enum prediction taken
)
2515 bitmap visited
= BITMAP_ALLOC (NULL
);
2516 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2517 BITMAP_FREE (visited
);
2520 /* Like predict_paths_leading_to but take edge instead of basic block. */
2523 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2524 enum prediction taken
)
2526 bool has_nonloop_edge
= false;
2530 basic_block bb
= e
->src
;
2531 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2532 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2533 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2534 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2536 has_nonloop_edge
= true;
2539 if (!has_nonloop_edge
)
2541 bitmap visited
= BITMAP_ALLOC (NULL
);
2542 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2543 BITMAP_FREE (visited
);
2546 predict_edge_def (e
, pred
, taken
);
2549 /* This is used to carry information about basic blocks. It is
2550 attached to the AUX field of the standard CFG block. */
2552 typedef struct block_info_def
2554 /* Estimated frequency of execution of basic_block. */
2557 /* To keep queue of basic blocks to process. */
2560 /* Number of predecessors we need to visit first. */
2564 /* Similar information for edges. */
2565 typedef struct edge_info_def
2567 /* In case edge is a loopback edge, the probability edge will be reached
2568 in case header is. Estimated number of iterations of the loop can be
2569 then computed as 1 / (1 - back_edge_prob). */
2570 sreal back_edge_prob
;
2571 /* True if the edge is a loopback edge in the natural loop. */
2572 unsigned int back_edge
:1;
2575 #define BLOCK_INFO(B) ((block_info) (B)->aux)
2576 #define EDGE_INFO(E) ((edge_info) (E)->aux)
2578 /* Helper function for estimate_bb_frequencies.
2579 Propagate the frequencies in blocks marked in
2580 TOVISIT, starting in HEAD. */
2583 propagate_freq (basic_block head
, bitmap tovisit
)
2592 /* For each basic block we need to visit count number of his predecessors
2593 we need to visit first. */
2594 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2599 bb
= BASIC_BLOCK (i
);
2601 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2603 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2605 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2607 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2609 "Irreducible region hit, ignoring edge to %i->%i\n",
2610 e
->src
->index
, bb
->index
);
2612 BLOCK_INFO (bb
)->npredecessors
= count
;
2613 /* When function never returns, we will never process exit block. */
2614 if (!count
&& bb
== EXIT_BLOCK_PTR
)
2615 bb
->count
= bb
->frequency
= 0;
2618 memcpy (&BLOCK_INFO (head
)->frequency
, &real_one
, sizeof (real_one
));
2620 for (bb
= head
; bb
; bb
= nextbb
)
2623 sreal cyclic_probability
, frequency
;
2625 memcpy (&cyclic_probability
, &real_zero
, sizeof (real_zero
));
2626 memcpy (&frequency
, &real_zero
, sizeof (real_zero
));
2628 nextbb
= BLOCK_INFO (bb
)->next
;
2629 BLOCK_INFO (bb
)->next
= NULL
;
2631 /* Compute frequency of basic block. */
2634 #ifdef ENABLE_CHECKING
2635 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2636 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2637 || (e
->flags
& EDGE_DFS_BACK
));
2640 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2641 if (EDGE_INFO (e
)->back_edge
)
2643 sreal_add (&cyclic_probability
, &cyclic_probability
,
2644 &EDGE_INFO (e
)->back_edge_prob
);
2646 else if (!(e
->flags
& EDGE_DFS_BACK
))
2650 /* frequency += (e->probability
2651 * BLOCK_INFO (e->src)->frequency /
2652 REG_BR_PROB_BASE); */
2654 sreal_init (&tmp
, e
->probability
, 0);
2655 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (e
->src
)->frequency
);
2656 sreal_mul (&tmp
, &tmp
, &real_inv_br_prob_base
);
2657 sreal_add (&frequency
, &frequency
, &tmp
);
2660 if (sreal_compare (&cyclic_probability
, &real_zero
) == 0)
2662 memcpy (&BLOCK_INFO (bb
)->frequency
, &frequency
,
2663 sizeof (frequency
));
2667 if (sreal_compare (&cyclic_probability
, &real_almost_one
) > 0)
2669 memcpy (&cyclic_probability
, &real_almost_one
,
2670 sizeof (real_almost_one
));
2673 /* BLOCK_INFO (bb)->frequency = frequency
2674 / (1 - cyclic_probability) */
2676 sreal_sub (&cyclic_probability
, &real_one
, &cyclic_probability
);
2677 sreal_div (&BLOCK_INFO (bb
)->frequency
,
2678 &frequency
, &cyclic_probability
);
2682 bitmap_clear_bit (tovisit
, bb
->index
);
2684 e
= find_edge (bb
, head
);
2689 /* EDGE_INFO (e)->back_edge_prob
2690 = ((e->probability * BLOCK_INFO (bb)->frequency)
2691 / REG_BR_PROB_BASE); */
2693 sreal_init (&tmp
, e
->probability
, 0);
2694 sreal_mul (&tmp
, &tmp
, &BLOCK_INFO (bb
)->frequency
);
2695 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2696 &tmp
, &real_inv_br_prob_base
);
2699 /* Propagate to successor blocks. */
2700 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2701 if (!(e
->flags
& EDGE_DFS_BACK
)
2702 && BLOCK_INFO (e
->dest
)->npredecessors
)
2704 BLOCK_INFO (e
->dest
)->npredecessors
--;
2705 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2710 BLOCK_INFO (last
)->next
= e
->dest
;
2718 /* Estimate frequencies in loops at same nest level. */
2721 estimate_loops_at_level (struct loop
*first_loop
)
2725 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2730 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2732 estimate_loops_at_level (loop
->inner
);
2734 /* Find current loop back edge and mark it. */
2735 e
= loop_latch_edge (loop
);
2736 EDGE_INFO (e
)->back_edge
= 1;
2738 bbs
= get_loop_body (loop
);
2739 for (i
= 0; i
< loop
->num_nodes
; i
++)
2740 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2742 propagate_freq (loop
->header
, tovisit
);
2743 BITMAP_FREE (tovisit
);
2747 /* Propagates frequencies through structure of loops. */
2750 estimate_loops (void)
2752 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2755 /* Start by estimating the frequencies in the loops. */
2756 if (number_of_loops (cfun
) > 1)
2757 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2759 /* Now propagate the frequencies through all the blocks. */
2762 bitmap_set_bit (tovisit
, bb
->index
);
2764 propagate_freq (ENTRY_BLOCK_PTR
, tovisit
);
2765 BITMAP_FREE (tovisit
);
2768 /* Drop the profile for NODE to guessed, and update its frequency based on
2769 whether it is expected to be HOT. */
2772 drop_profile (struct cgraph_node
*node
, bool hot
)
2774 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2778 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2779 cgraph_node_name (node
), node
->order
,
2780 hot
? "Function is hot" : "Function is normal");
2781 /* We only expect to miss profiles for functions that are reached
2782 via non-zero call edges in cases where the function may have
2783 been linked from another module or library (COMDATs and extern
2784 templates). See the comments below for handle_missing_profiles. */
2785 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
))
2787 if (flag_profile_correction
)
2791 "Missing counts for called function %s/%i\n",
2792 cgraph_node_name (node
), node
->order
);
2795 error ("Missing counts for called function %s/%i",
2796 cgraph_node_name (node
), node
->order
);
2799 profile_status_for_function (fn
)
2800 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2802 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2805 /* In the case of COMDAT routines, multiple object files will contain the same
2806 function and the linker will select one for the binary. In that case
2807 all the other copies from the profile instrument binary will be missing
2808 profile counts. Look for cases where this happened, due to non-zero
2809 call counts going to 0-count functions, and drop the profile to guessed
2810 so that we can use the estimated probabilities and avoid optimizing only
2813 The other case where the profile may be missing is when the routine
2814 is not going to be emitted to the object file, e.g. for "extern template"
2815 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2816 all other cases of non-zero calls to 0-count functions. */
2819 handle_missing_profiles (void)
2821 struct cgraph_node
*node
;
2822 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2823 vec
<struct cgraph_node
*> worklist
;
2824 worklist
.create (64);
2826 /* See if 0 count function has non-0 count callers. In this case we
2827 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2828 FOR_EACH_DEFINED_FUNCTION (node
)
2830 struct cgraph_edge
*e
;
2831 gcov_type call_count
= 0;
2832 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2836 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2837 call_count
+= e
->count
;
2840 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2842 bool maybe_hot
= maybe_hot_count_p (NULL
, call_count
);
2844 drop_profile (node
, maybe_hot
);
2845 worklist
.safe_push (node
);
2849 /* Propagate the profile dropping to other 0-count COMDATs that are
2850 potentially called by COMDATs we already dropped the profile on. */
2851 while (worklist
.length () > 0)
2853 struct cgraph_edge
*e
;
2855 node
= worklist
.pop ();
2856 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2858 struct cgraph_node
*callee
= e
->callee
;
2859 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2861 if (callee
->count
> 0)
2863 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2864 && profile_status_for_function (fn
) == PROFILE_READ
)
2866 /* Since there are no non-0 call counts to this function,
2867 we don't know for sure whether it is hot. Indicate to
2868 the drop_profile routine that function should be marked
2869 normal, rather than hot. */
2870 drop_profile (node
, false);
2871 worklist
.safe_push (callee
);
2875 worklist
.release ();
2878 /* Convert counts measured by profile driven feedback to frequencies.
2879 Return nonzero iff there was any nonzero execution count. */
2882 counts_to_freqs (void)
2884 gcov_type count_max
, true_count_max
= 0;
2887 /* Don't overwrite the estimated frequencies when the profile for
2888 the function is missing. We may drop this function PROFILE_GUESSED
2889 later in drop_profile (). */
2890 if (!ENTRY_BLOCK_PTR
->count
)
2893 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2894 true_count_max
= MAX (bb
->count
, true_count_max
);
2896 count_max
= MAX (true_count_max
, 1);
2897 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2898 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2900 return true_count_max
;
2903 /* Return true if function is likely to be expensive, so there is no point to
2904 optimize performance of prologue, epilogue or do inlining at the expense
2905 of code size growth. THRESHOLD is the limit of number of instructions
2906 function can execute at average to be still considered not expensive. */
2909 expensive_function_p (int threshold
)
2911 unsigned int sum
= 0;
2915 /* We can not compute accurately for large thresholds due to scaled
2917 gcc_assert (threshold
<= BB_FREQ_MAX
);
2919 /* Frequencies are out of range. This either means that function contains
2920 internal loop executing more than BB_FREQ_MAX times or profile feedback
2921 is available and function has not been executed at all. */
2922 if (ENTRY_BLOCK_PTR
->frequency
== 0)
2925 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2926 limit
= ENTRY_BLOCK_PTR
->frequency
* threshold
;
2931 FOR_BB_INSNS (bb
, insn
)
2932 if (active_insn_p (insn
))
2934 sum
+= bb
->frequency
;
2943 /* Estimate and propagate basic block frequencies using the given branch
2944 probabilities. If FORCE is true, the frequencies are used to estimate
2945 the counts even when there are already non-zero profile counts. */
2948 estimate_bb_frequencies (bool force
)
2953 if (force
|| profile_status
!= PROFILE_READ
|| !counts_to_freqs ())
2955 static int real_values_initialized
= 0;
2957 if (!real_values_initialized
)
2959 real_values_initialized
= 1;
2960 sreal_init (&real_zero
, 0, 0);
2961 sreal_init (&real_one
, 1, 0);
2962 sreal_init (&real_br_prob_base
, REG_BR_PROB_BASE
, 0);
2963 sreal_init (&real_bb_freq_max
, BB_FREQ_MAX
, 0);
2964 sreal_init (&real_one_half
, 1, -1);
2965 sreal_div (&real_inv_br_prob_base
, &real_one
, &real_br_prob_base
);
2966 sreal_sub (&real_almost_one
, &real_one
, &real_inv_br_prob_base
);
2969 mark_dfs_back_edges ();
2971 single_succ_edge (ENTRY_BLOCK_PTR
)->probability
= REG_BR_PROB_BASE
;
2973 /* Set up block info for each basic block. */
2974 alloc_aux_for_blocks (sizeof (struct block_info_def
));
2975 alloc_aux_for_edges (sizeof (struct edge_info_def
));
2976 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2981 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2983 sreal_init (&EDGE_INFO (e
)->back_edge_prob
, e
->probability
, 0);
2984 sreal_mul (&EDGE_INFO (e
)->back_edge_prob
,
2985 &EDGE_INFO (e
)->back_edge_prob
,
2986 &real_inv_br_prob_base
);
2990 /* First compute frequencies locally for each loop from innermost
2991 to outermost to examine frequencies for back edges. */
2994 memcpy (&freq_max
, &real_zero
, sizeof (real_zero
));
2996 if (sreal_compare (&freq_max
, &BLOCK_INFO (bb
)->frequency
) < 0)
2997 memcpy (&freq_max
, &BLOCK_INFO (bb
)->frequency
, sizeof (freq_max
));
2999 sreal_div (&freq_max
, &real_bb_freq_max
, &freq_max
);
3000 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
3004 sreal_mul (&tmp
, &BLOCK_INFO (bb
)->frequency
, &freq_max
);
3005 sreal_add (&tmp
, &tmp
, &real_one_half
);
3006 bb
->frequency
= sreal_to_int (&tmp
);
3009 free_aux_for_blocks ();
3010 free_aux_for_edges ();
3012 compute_function_frequency ();
3015 /* Decide whether function is hot, cold or unlikely executed. */
3017 compute_function_frequency (void)
3020 struct cgraph_node
*node
= cgraph_get_node (current_function_decl
);
3022 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3023 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3024 node
->only_called_at_startup
= true;
3025 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3026 node
->only_called_at_exit
= true;
3028 if (profile_status
!= PROFILE_READ
)
3030 int flags
= flags_from_decl_or_type (current_function_decl
);
3031 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3033 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3034 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3036 node
->frequency
= NODE_FREQUENCY_HOT
;
3037 else if (flags
& ECF_NORETURN
)
3038 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3039 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3040 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3041 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3042 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3043 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3047 /* Only first time try to drop function into unlikely executed.
3048 After inlining the roundoff errors may confuse us.
3049 Ipa-profile pass will drop functions only called from unlikely
3050 functions to unlikely and that is most of what we care about. */
3051 if (!cfun
->after_inlining
)
3052 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3055 if (maybe_hot_bb_p (cfun
, bb
))
3057 node
->frequency
= NODE_FREQUENCY_HOT
;
3060 if (!probably_never_executed_bb_p (cfun
, bb
))
3061 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3066 gate_estimate_probability (void)
3068 return flag_guess_branch_prob
;
3071 /* Build PREDICT_EXPR. */
3073 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3075 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3076 build_int_cst (integer_type_node
, predictor
));
3077 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3082 predictor_name (enum br_predictor predictor
)
3084 return predictor_info
[predictor
].name
;
3089 const pass_data pass_data_profile
=
3091 GIMPLE_PASS
, /* type */
3092 "profile_estimate", /* name */
3093 OPTGROUP_NONE
, /* optinfo_flags */
3094 true, /* has_gate */
3095 true, /* has_execute */
3096 TV_BRANCH_PROB
, /* tv_id */
3097 PROP_cfg
, /* properties_required */
3098 0, /* properties_provided */
3099 0, /* properties_destroyed */
3100 0, /* todo_flags_start */
3101 TODO_verify_ssa
, /* todo_flags_finish */
3104 class pass_profile
: public gimple_opt_pass
3107 pass_profile (gcc::context
*ctxt
)
3108 : gimple_opt_pass (pass_data_profile
, ctxt
)
3111 /* opt_pass methods: */
3112 bool gate () { return gate_estimate_probability (); }
3113 unsigned int execute () { return tree_estimate_probability_driver (); }
3115 }; // class pass_profile
3120 make_pass_profile (gcc::context
*ctxt
)
3122 return new pass_profile (ctxt
);
3127 const pass_data pass_data_strip_predict_hints
=
3129 GIMPLE_PASS
, /* type */
3130 "*strip_predict_hints", /* name */
3131 OPTGROUP_NONE
, /* optinfo_flags */
3132 false, /* has_gate */
3133 true, /* has_execute */
3134 TV_BRANCH_PROB
, /* tv_id */
3135 PROP_cfg
, /* properties_required */
3136 0, /* properties_provided */
3137 0, /* properties_destroyed */
3138 0, /* todo_flags_start */
3139 TODO_verify_ssa
, /* todo_flags_finish */
3142 class pass_strip_predict_hints
: public gimple_opt_pass
3145 pass_strip_predict_hints (gcc::context
*ctxt
)
3146 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3149 /* opt_pass methods: */
3150 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3151 unsigned int execute () { return strip_predict_hints (); }
3153 }; // class pass_strip_predict_hints
3158 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3160 return new pass_strip_predict_hints (ctxt
);
3163 /* Rebuild function frequencies. Passes are in general expected to
3164 maintain profile by hand, however in some cases this is not possible:
3165 for example when inlining several functions with loops freuqencies might run
3166 out of scale and thus needs to be recomputed. */
3169 rebuild_frequencies (void)
3171 timevar_push (TV_REBUILD_FREQUENCIES
);
3173 /* When the max bb count in the function is small, there is a higher
3174 chance that there were truncation errors in the integer scaling
3175 of counts by inlining and other optimizations. This could lead
3176 to incorrect classification of code as being cold when it isn't.
3177 In that case, force the estimation of bb counts/frequencies from the
3178 branch probabilities, rather than computing frequencies from counts,
3179 which may also lead to frequencies incorrectly reduced to 0. There
3180 is less precision in the probabilities, so we only do this for small
3182 gcov_type count_max
= 0;
3184 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
3185 count_max
= MAX (bb
->count
, count_max
);
3187 if (profile_status
== PROFILE_GUESSED
3188 || (profile_status
== PROFILE_READ
&& count_max
< REG_BR_PROB_BASE
/10))
3190 loop_optimizer_init (0);
3191 add_noreturn_fake_exit_edges ();
3192 mark_irreducible_loops ();
3193 connect_infinite_loops_to_exit ();
3194 estimate_bb_frequencies (true);
3195 remove_fake_exit_edges ();
3196 loop_optimizer_finalize ();
3198 else if (profile_status
== PROFILE_READ
)
3202 timevar_pop (TV_REBUILD_FREQUENCIES
);