1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2016 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"
38 #include "tree-pass.h"
43 #include "diagnostic-core.h"
44 #include "gimple-predict.h"
45 #include "fold-const.h"
52 #include "gimple-iterator.h"
54 #include "tree-ssa-loop-niter.h"
55 #include "tree-ssa-loop.h"
56 #include "tree-scalar-evolution.h"
58 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
59 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
60 static sreal real_almost_one
, real_br_prob_base
,
61 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
63 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
64 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
, int);
65 static void predict_paths_leading_to (basic_block
, enum br_predictor
, enum prediction
);
66 static void predict_paths_leading_to_edge (edge
, enum br_predictor
, enum prediction
);
67 static bool can_predict_insn_p (const rtx_insn
*);
69 /* Information we hold about each branch predictor.
70 Filled using information from predict.def. */
74 const char *const name
; /* Name used in the debugging dumps. */
75 const int hitrate
; /* Expected hitrate used by
76 predict_insn_def call. */
80 /* Use given predictor without Dempster-Shaffer theory if it matches
81 using first_match heuristics. */
82 #define PRED_FLAG_FIRST_MATCH 1
84 /* Recompute hitrate in percent to our representation. */
86 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
88 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
89 static const struct predictor_info predictor_info
[]= {
90 #include "predict.def"
92 /* Upper bound on predictors. */
97 /* Return TRUE if frequency FREQ is considered to be hot. */
100 maybe_hot_frequency_p (struct function
*fun
, int freq
)
102 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
104 || !opt_for_fn (fun
->decl
, flag_branch_probabilities
))
106 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
108 if (node
->frequency
== NODE_FREQUENCY_HOT
)
111 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
113 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
114 && freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
* 2 / 3))
116 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
118 if (freq
* PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)
119 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
124 static gcov_type min_count
= -1;
126 /* Determine the threshold for hot BB counts. */
129 get_hot_bb_threshold ()
131 gcov_working_set_t
*ws
;
134 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
136 min_count
= ws
->min_counter
;
141 /* Set the threshold for hot BB counts. */
144 set_hot_bb_threshold (gcov_type min
)
149 /* Return TRUE if frequency FREQ is considered to be hot. */
152 maybe_hot_count_p (struct function
*fun
, gcov_type count
)
154 if (fun
&& profile_status_for_fn (fun
) != PROFILE_READ
)
156 /* Code executed at most once is not hot. */
157 if (profile_info
->runs
>= count
)
159 return (count
>= get_hot_bb_threshold ());
162 /* Return true in case BB can be CPU intensive and should be optimized
163 for maximal performance. */
166 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
168 gcc_checking_assert (fun
);
169 if (profile_status_for_fn (fun
) == PROFILE_READ
)
170 return maybe_hot_count_p (fun
, bb
->count
);
171 return maybe_hot_frequency_p (fun
, bb
->frequency
);
174 /* Return true in case BB can be CPU intensive and should be optimized
175 for maximal performance. */
178 maybe_hot_edge_p (edge e
)
180 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
181 return maybe_hot_count_p (cfun
, e
->count
);
182 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
185 /* Return true if profile COUNT and FREQUENCY, or function FUN static
186 node frequency reflects never being executed. */
189 probably_never_executed (struct function
*fun
,
190 gcov_type count
, int frequency
)
192 gcc_checking_assert (fun
);
193 if (profile_status_for_fn (fun
) == PROFILE_READ
)
195 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
196 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
200 if (!ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
202 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
204 gcov_type computed_count
;
205 /* Check for possibility of overflow, in which case entry bb count
206 is large enough to do the division first without losing much
208 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
< REG_BR_PROB_BASE
*
211 gcov_type scaled_count
212 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
*
213 unlikely_count_fraction
;
214 computed_count
= RDIV (scaled_count
,
215 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
219 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
,
220 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
221 computed_count
*= frequency
* unlikely_count_fraction
;
223 if (computed_count
>= profile_info
->runs
)
228 if ((!profile_info
|| !(opt_for_fn (fun
->decl
, flag_branch_probabilities
)))
229 && (cgraph_node::get (fun
->decl
)->frequency
230 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
236 /* Return true in case BB is probably never executed. */
239 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
241 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
245 /* Return true in case edge E is probably never executed. */
248 probably_never_executed_edge_p (struct function
*fun
, edge e
)
250 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
253 /* Return true when current function should always be optimized for size. */
256 optimize_function_for_size_p (struct function
*fun
)
258 if (!fun
|| !fun
->decl
)
259 return optimize_size
;
260 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
261 return n
&& n
->optimize_for_size_p ();
264 /* Return true when current function should always be optimized for speed. */
267 optimize_function_for_speed_p (struct function
*fun
)
269 return !optimize_function_for_size_p (fun
);
272 /* Return the optimization type that should be used for the function FUN. */
275 function_optimization_type (struct function
*fun
)
277 return (optimize_function_for_speed_p (fun
)
279 : OPTIMIZE_FOR_SIZE
);
282 /* Return TRUE when BB should be optimized for size. */
285 optimize_bb_for_size_p (const_basic_block bb
)
287 return (optimize_function_for_size_p (cfun
)
288 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
291 /* Return TRUE when BB should be optimized for speed. */
294 optimize_bb_for_speed_p (const_basic_block bb
)
296 return !optimize_bb_for_size_p (bb
);
299 /* Return the optimization type that should be used for block BB. */
302 bb_optimization_type (const_basic_block bb
)
304 return (optimize_bb_for_speed_p (bb
)
306 : OPTIMIZE_FOR_SIZE
);
309 /* Return TRUE when BB should be optimized for size. */
312 optimize_edge_for_size_p (edge e
)
314 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
317 /* Return TRUE when BB should be optimized for speed. */
320 optimize_edge_for_speed_p (edge e
)
322 return !optimize_edge_for_size_p (e
);
325 /* Return TRUE when BB should be optimized for size. */
328 optimize_insn_for_size_p (void)
330 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
333 /* Return TRUE when BB should be optimized for speed. */
336 optimize_insn_for_speed_p (void)
338 return !optimize_insn_for_size_p ();
341 /* Return TRUE when LOOP should be optimized for size. */
344 optimize_loop_for_size_p (struct loop
*loop
)
346 return optimize_bb_for_size_p (loop
->header
);
349 /* Return TRUE when LOOP should be optimized for speed. */
352 optimize_loop_for_speed_p (struct loop
*loop
)
354 return optimize_bb_for_speed_p (loop
->header
);
357 /* Return TRUE when LOOP nest should be optimized for speed. */
360 optimize_loop_nest_for_speed_p (struct loop
*loop
)
362 struct loop
*l
= loop
;
363 if (optimize_loop_for_speed_p (loop
))
366 while (l
&& l
!= loop
)
368 if (optimize_loop_for_speed_p (l
))
376 while (l
!= loop
&& !l
->next
)
385 /* Return TRUE when LOOP nest should be optimized for size. */
388 optimize_loop_nest_for_size_p (struct loop
*loop
)
390 return !optimize_loop_nest_for_speed_p (loop
);
393 /* Return true when edge E is likely to be well predictable by branch
397 predictable_edge_p (edge e
)
399 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
402 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
403 || (REG_BR_PROB_BASE
- e
->probability
404 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
410 /* Set RTL expansion for BB profile. */
413 rtl_profile_for_bb (basic_block bb
)
415 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
418 /* Set RTL expansion for edge profile. */
421 rtl_profile_for_edge (edge e
)
423 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
426 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
428 default_rtl_profile (void)
430 crtl
->maybe_hot_insn_p
= true;
433 /* Return true if the one of outgoing edges is already predicted by
437 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
440 if (!INSN_P (BB_END (bb
)))
442 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
443 if (REG_NOTE_KIND (note
) == REG_BR_PRED
444 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
449 /* Structure representing predictions in tree level. */
451 struct edge_prediction
{
452 struct edge_prediction
*ep_next
;
454 enum br_predictor ep_predictor
;
458 /* This map contains for a basic block the list of predictions for the
461 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
463 /* Return true if the one of outgoing edges is already predicted by
467 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
469 struct edge_prediction
*i
;
470 edge_prediction
**preds
= bb_predictions
->get (bb
);
475 for (i
= *preds
; i
; i
= i
->ep_next
)
476 if (i
->ep_predictor
== predictor
)
481 /* Return true if the one of outgoing edges is already predicted by
482 PREDICTOR for edge E predicted as TAKEN. */
485 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
487 struct edge_prediction
*i
;
488 basic_block bb
= e
->src
;
489 edge_prediction
**preds
= bb_predictions
->get (bb
);
493 int probability
= predictor_info
[(int) predictor
].hitrate
;
496 probability
= REG_BR_PROB_BASE
- probability
;
498 for (i
= *preds
; i
; i
= i
->ep_next
)
499 if (i
->ep_predictor
== predictor
501 && i
->ep_probability
== probability
)
506 /* Return true when the probability of edge is reliable.
508 The profile guessing code is good at predicting branch outcome (ie.
509 taken/not taken), that is predicted right slightly over 75% of time.
510 It is however notoriously poor on predicting the probability itself.
511 In general the profile appear a lot flatter (with probabilities closer
512 to 50%) than the reality so it is bad idea to use it to drive optimization
513 such as those disabling dynamic branch prediction for well predictable
516 There are two exceptions - edges leading to noreturn edges and edges
517 predicted by number of iterations heuristics are predicted well. This macro
518 should be able to distinguish those, but at the moment it simply check for
519 noreturn heuristic that is only one giving probability over 99% or bellow
520 1%. In future we might want to propagate reliability information across the
521 CFG if we find this information useful on multiple places. */
523 probability_reliable_p (int prob
)
525 return (profile_status_for_fn (cfun
) == PROFILE_READ
526 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
527 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
530 /* Same predicate as above, working on edges. */
532 edge_probability_reliable_p (const_edge e
)
534 return probability_reliable_p (e
->probability
);
537 /* Same predicate as edge_probability_reliable_p, working on notes. */
539 br_prob_note_reliable_p (const_rtx note
)
541 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
542 return probability_reliable_p (XINT (note
, 0));
546 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
548 gcc_assert (any_condjump_p (insn
));
549 if (!flag_guess_branch_prob
)
552 add_reg_note (insn
, REG_BR_PRED
,
553 gen_rtx_CONCAT (VOIDmode
,
554 GEN_INT ((int) predictor
),
555 GEN_INT ((int) probability
)));
558 /* Predict insn by given predictor. */
561 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
562 enum prediction taken
)
564 int probability
= predictor_info
[(int) predictor
].hitrate
;
567 probability
= REG_BR_PROB_BASE
- probability
;
569 predict_insn (insn
, predictor
, probability
);
572 /* Predict edge E with given probability if possible. */
575 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
578 last_insn
= BB_END (e
->src
);
580 /* We can store the branch prediction information only about
581 conditional jumps. */
582 if (!any_condjump_p (last_insn
))
585 /* We always store probability of branching. */
586 if (e
->flags
& EDGE_FALLTHRU
)
587 probability
= REG_BR_PROB_BASE
- probability
;
589 predict_insn (last_insn
, predictor
, probability
);
592 /* Predict edge E with the given PROBABILITY. */
594 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
596 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
597 && EDGE_COUNT (e
->src
->succs
) > 1
598 && flag_guess_branch_prob
601 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
602 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
606 i
->ep_probability
= probability
;
607 i
->ep_predictor
= predictor
;
612 /* Remove all predictions on given basic block that are attached
615 remove_predictions_associated_with_edge (edge e
)
620 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
624 struct edge_prediction
**prediction
= preds
;
625 struct edge_prediction
*next
;
629 if ((*prediction
)->ep_edge
== e
)
631 next
= (*prediction
)->ep_next
;
636 prediction
= &((*prediction
)->ep_next
);
641 /* Clears the list of predictions stored for BB. */
644 clear_bb_predictions (basic_block bb
)
646 edge_prediction
**preds
= bb_predictions
->get (bb
);
647 struct edge_prediction
*pred
, *next
;
652 for (pred
= *preds
; pred
; pred
= next
)
654 next
= pred
->ep_next
;
660 /* Return true when we can store prediction on insn INSN.
661 At the moment we represent predictions only on conditional
662 jumps, not at computed jump or other complicated cases. */
664 can_predict_insn_p (const rtx_insn
*insn
)
666 return (JUMP_P (insn
)
667 && any_condjump_p (insn
)
668 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
671 /* Predict edge E by given predictor if possible. */
674 predict_edge_def (edge e
, enum br_predictor predictor
,
675 enum prediction taken
)
677 int probability
= predictor_info
[(int) predictor
].hitrate
;
680 probability
= REG_BR_PROB_BASE
- probability
;
682 predict_edge (e
, predictor
, probability
);
685 /* Invert all branch predictions or probability notes in the INSN. This needs
686 to be done each time we invert the condition used by the jump. */
689 invert_br_probabilities (rtx insn
)
693 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
694 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
695 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
696 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
697 XEXP (XEXP (note
, 0), 1)
698 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
701 /* Dump information about the branch prediction to the output file. */
704 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
705 basic_block bb
, int used
)
713 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
714 if (! (e
->flags
& EDGE_FALLTHRU
))
717 fprintf (file
, " %s heuristics%s: %.1f%%",
718 predictor_info
[predictor
].name
,
719 used
? "" : " (ignored)", probability
* 100.0 / REG_BR_PROB_BASE
);
723 fprintf (file
, " exec %" PRId64
, bb
->count
);
726 fprintf (file
, " hit %" PRId64
, e
->count
);
727 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
731 fprintf (file
, "\n");
734 /* We can not predict the probabilities of outgoing edges of bb. Set them
735 evenly and hope for the best. */
737 set_even_probabilities (basic_block bb
)
743 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
744 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
746 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
747 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
748 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
753 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
754 note if not already present. Remove now useless REG_BR_PRED notes. */
757 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
762 int best_probability
= PROB_EVEN
;
763 enum br_predictor best_predictor
= END_PREDICTORS
;
764 int combined_probability
= REG_BR_PROB_BASE
/ 2;
766 bool first_match
= false;
769 if (!can_predict_insn_p (insn
))
771 set_even_probabilities (bb
);
775 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
776 pnote
= ®_NOTES (insn
);
778 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
781 /* We implement "first match" heuristics and use probability guessed
782 by predictor with smallest index. */
783 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
784 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
786 enum br_predictor predictor
= ((enum br_predictor
)
787 INTVAL (XEXP (XEXP (note
, 0), 0)));
788 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
791 if (best_predictor
> predictor
)
792 best_probability
= probability
, best_predictor
= predictor
;
794 d
= (combined_probability
* probability
795 + (REG_BR_PROB_BASE
- combined_probability
)
796 * (REG_BR_PROB_BASE
- probability
));
798 /* Use FP math to avoid overflows of 32bit integers. */
800 /* If one probability is 0% and one 100%, avoid division by zero. */
801 combined_probability
= REG_BR_PROB_BASE
/ 2;
803 combined_probability
= (((double) combined_probability
) * probability
804 * REG_BR_PROB_BASE
/ d
+ 0.5);
807 /* Decide which heuristic to use. In case we didn't match anything,
808 use no_prediction heuristic, in case we did match, use either
809 first match or Dempster-Shaffer theory depending on the flags. */
811 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
815 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
816 combined_probability
, bb
, true);
819 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
821 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
826 combined_probability
= best_probability
;
827 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
831 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
833 enum br_predictor predictor
= ((enum br_predictor
)
834 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
835 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
837 dump_prediction (dump_file
, predictor
, probability
, bb
,
838 !first_match
|| best_predictor
== predictor
);
839 *pnote
= XEXP (*pnote
, 1);
842 pnote
= &XEXP (*pnote
, 1);
847 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
849 /* Save the prediction into CFG in case we are seeing non-degenerated
851 if (!single_succ_p (bb
))
853 BRANCH_EDGE (bb
)->probability
= combined_probability
;
854 FALLTHRU_EDGE (bb
)->probability
855 = REG_BR_PROB_BASE
- combined_probability
;
858 else if (!single_succ_p (bb
))
860 int prob
= XINT (prob_note
, 0);
862 BRANCH_EDGE (bb
)->probability
= prob
;
863 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
866 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
869 /* Combine predictions into single probability and store them into CFG.
870 Remove now useless prediction entries.
871 If DRY_RUN is set, only produce dumps and do not modify profile. */
874 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
876 int best_probability
= PROB_EVEN
;
877 enum br_predictor best_predictor
= END_PREDICTORS
;
878 int combined_probability
= REG_BR_PROB_BASE
/ 2;
880 bool first_match
= false;
882 struct edge_prediction
*pred
;
884 edge e
, first
= NULL
, second
= NULL
;
887 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
888 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
891 if (first
&& !second
)
897 /* When there is no successor or only one choice, prediction is easy.
899 We are lazy for now and predict only basic blocks with two outgoing
900 edges. It is possible to predict generic case too, but we have to
901 ignore first match heuristics and do more involved combining. Implement
905 if (!bb
->count
&& !dry_run
)
906 set_even_probabilities (bb
);
907 clear_bb_predictions (bb
);
909 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
915 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
917 edge_prediction
**preds
= bb_predictions
->get (bb
);
920 /* We implement "first match" heuristics and use probability guessed
921 by predictor with smallest index. */
922 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
924 enum br_predictor predictor
= pred
->ep_predictor
;
925 int probability
= pred
->ep_probability
;
927 if (pred
->ep_edge
!= first
)
928 probability
= REG_BR_PROB_BASE
- probability
;
931 /* First match heuristics would be widly confused if we predicted
933 if (best_predictor
> predictor
)
935 struct edge_prediction
*pred2
;
936 int prob
= probability
;
938 for (pred2
= (struct edge_prediction
*) *preds
;
939 pred2
; pred2
= pred2
->ep_next
)
940 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
942 int probability2
= pred2
->ep_probability
;
944 if (pred2
->ep_edge
!= first
)
945 probability2
= REG_BR_PROB_BASE
- probability2
;
947 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
948 (probability2
< REG_BR_PROB_BASE
/ 2))
951 /* If the same predictor later gave better result, go for it! */
952 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
953 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
957 best_probability
= prob
, best_predictor
= predictor
;
960 d
= (combined_probability
* probability
961 + (REG_BR_PROB_BASE
- combined_probability
)
962 * (REG_BR_PROB_BASE
- probability
));
964 /* Use FP math to avoid overflows of 32bit integers. */
966 /* If one probability is 0% and one 100%, avoid division by zero. */
967 combined_probability
= REG_BR_PROB_BASE
/ 2;
969 combined_probability
= (((double) combined_probability
)
971 * REG_BR_PROB_BASE
/ d
+ 0.5);
975 /* Decide which heuristic to use. In case we didn't match anything,
976 use no_prediction heuristic, in case we did match, use either
977 first match or Dempster-Shaffer theory depending on the flags. */
979 if (predictor_info
[best_predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
983 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
, true);
986 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
988 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
993 combined_probability
= best_probability
;
994 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
, true);
998 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1000 enum br_predictor predictor
= pred
->ep_predictor
;
1001 int probability
= pred
->ep_probability
;
1003 if (pred
->ep_edge
!= EDGE_SUCC (bb
, 0))
1004 probability
= REG_BR_PROB_BASE
- probability
;
1005 dump_prediction (dump_file
, predictor
, probability
, bb
,
1006 !first_match
|| best_predictor
== predictor
);
1009 clear_bb_predictions (bb
);
1011 if (!bb
->count
&& !dry_run
)
1013 first
->probability
= combined_probability
;
1014 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1018 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1019 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1021 T1 and T2 should be one of the following cases:
1022 1. T1 is SSA_NAME, T2 is NULL
1023 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1024 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1027 strips_small_constant (tree t1
, tree t2
)
1034 else if (TREE_CODE (t1
) == SSA_NAME
)
1036 else if (tree_fits_shwi_p (t1
))
1037 value
= tree_to_shwi (t1
);
1043 else if (tree_fits_shwi_p (t2
))
1044 value
= tree_to_shwi (t2
);
1045 else if (TREE_CODE (t2
) == SSA_NAME
)
1053 if (value
<= 4 && value
>= -4)
1059 /* Return the SSA_NAME in T or T's operands.
1060 Return NULL if SSA_NAME cannot be found. */
1063 get_base_value (tree t
)
1065 if (TREE_CODE (t
) == SSA_NAME
)
1068 if (!BINARY_CLASS_P (t
))
1071 switch (TREE_OPERAND_LENGTH (t
))
1074 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1076 return strips_small_constant (TREE_OPERAND (t
, 0),
1077 TREE_OPERAND (t
, 1));
1083 /* Check the compare STMT in LOOP. If it compares an induction
1084 variable to a loop invariant, return true, and save
1085 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1086 Otherwise return false and set LOOP_INVAIANT to NULL. */
1089 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1090 tree
*loop_invariant
,
1091 enum tree_code
*compare_code
,
1095 tree op0
, op1
, bound
, base
;
1097 enum tree_code code
;
1100 code
= gimple_cond_code (stmt
);
1101 *loop_invariant
= NULL
;
1117 op0
= gimple_cond_lhs (stmt
);
1118 op1
= gimple_cond_rhs (stmt
);
1120 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1121 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1123 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1125 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1127 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1128 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1130 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1131 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1134 if (integer_zerop (iv0
.step
))
1136 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1137 code
= invert_tree_comparison (code
, false);
1140 if (tree_fits_shwi_p (iv1
.step
))
1149 if (tree_fits_shwi_p (iv0
.step
))
1155 if (TREE_CODE (bound
) != INTEGER_CST
)
1156 bound
= get_base_value (bound
);
1159 if (TREE_CODE (base
) != INTEGER_CST
)
1160 base
= get_base_value (base
);
1164 *loop_invariant
= bound
;
1165 *compare_code
= code
;
1167 *loop_iv_base
= base
;
1171 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1174 expr_coherent_p (tree t1
, tree t2
)
1177 tree ssa_name_1
= NULL
;
1178 tree ssa_name_2
= NULL
;
1180 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1181 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1186 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1188 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1191 /* Check to see if t1 is expressed/defined with t2. */
1192 stmt
= SSA_NAME_DEF_STMT (t1
);
1193 gcc_assert (stmt
!= NULL
);
1194 if (is_gimple_assign (stmt
))
1196 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1197 if (ssa_name_1
&& ssa_name_1
== t2
)
1201 /* Check to see if t2 is expressed/defined with t1. */
1202 stmt
= SSA_NAME_DEF_STMT (t2
);
1203 gcc_assert (stmt
!= NULL
);
1204 if (is_gimple_assign (stmt
))
1206 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1207 if (ssa_name_2
&& ssa_name_2
== t1
)
1211 /* Compare if t1 and t2's def_stmts are identical. */
1212 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1218 /* Predict branch probability of BB when BB contains a branch that compares
1219 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1220 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1223 for (int i = 0; i < bound; i++) {
1230 In this loop, we will predict the branch inside the loop to be taken. */
1233 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1234 tree loop_bound_var
,
1235 tree loop_iv_base_var
,
1236 enum tree_code loop_bound_code
,
1237 int loop_bound_step
)
1240 tree compare_var
, compare_base
;
1241 enum tree_code compare_code
;
1242 tree compare_step_var
;
1246 if (predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1247 || predicted_by_p (bb
, PRED_LOOP_ITERATIONS
)
1248 || predicted_by_p (bb
, PRED_LOOP_EXIT
)
1249 || predicted_by_p (bb
, PRED_LOOP_EXTRA_EXIT
))
1252 stmt
= last_stmt (bb
);
1253 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1255 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1262 /* Find the taken edge. */
1263 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1264 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1267 /* When comparing an IV to a loop invariant, NE is more likely to be
1268 taken while EQ is more likely to be not-taken. */
1269 if (compare_code
== NE_EXPR
)
1271 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1274 else if (compare_code
== EQ_EXPR
)
1276 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1280 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1283 /* If loop bound, base and compare bound are all constants, we can
1284 calculate the probability directly. */
1285 if (tree_fits_shwi_p (loop_bound_var
)
1286 && tree_fits_shwi_p (compare_var
)
1287 && tree_fits_shwi_p (compare_base
))
1290 bool overflow
, overall_overflow
= false;
1291 widest_int compare_count
, tem
;
1293 /* (loop_bound - base) / compare_step */
1294 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1295 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1296 overall_overflow
|= overflow
;
1297 widest_int loop_count
= wi::div_trunc (tem
,
1298 wi::to_widest (compare_step_var
),
1300 overall_overflow
|= overflow
;
1302 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1303 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1305 /* (loop_bound - compare_bound) / compare_step */
1306 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1307 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1308 overall_overflow
|= overflow
;
1309 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1311 overall_overflow
|= overflow
;
1315 /* (compare_bound - base) / compare_step */
1316 tem
= wi::sub (wi::to_widest (compare_var
),
1317 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1318 overall_overflow
|= overflow
;
1319 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1321 overall_overflow
|= overflow
;
1323 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1325 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1327 if (wi::neg_p (compare_count
))
1329 if (wi::neg_p (loop_count
))
1331 if (loop_count
== 0)
1333 else if (wi::cmps (compare_count
, loop_count
) == 1)
1334 probability
= REG_BR_PROB_BASE
;
1337 tem
= compare_count
* REG_BR_PROB_BASE
;
1338 tem
= wi::udiv_trunc (tem
, loop_count
);
1339 probability
= tem
.to_uhwi ();
1342 if (!overall_overflow
)
1343 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1348 if (expr_coherent_p (loop_bound_var
, compare_var
))
1350 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1351 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1352 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1353 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1354 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1355 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1356 else if (loop_bound_code
== NE_EXPR
)
1358 /* If the loop backedge condition is "(i != bound)", we do
1359 the comparison based on the step of IV:
1360 * step < 0 : backedge condition is like (i > bound)
1361 * step > 0 : backedge condition is like (i < bound) */
1362 gcc_assert (loop_bound_step
!= 0);
1363 if (loop_bound_step
> 0
1364 && (compare_code
== LT_EXPR
1365 || compare_code
== LE_EXPR
))
1366 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1367 else if (loop_bound_step
< 0
1368 && (compare_code
== GT_EXPR
1369 || compare_code
== GE_EXPR
))
1370 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1372 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1375 /* The branch is predicted not-taken if loop_bound_code is
1376 opposite with compare_code. */
1377 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1379 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1382 for (i = s; i < h; i++)
1384 The branch should be predicted taken. */
1385 if (loop_bound_step
> 0
1386 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1387 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1388 else if (loop_bound_step
< 0
1389 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1390 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1392 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1396 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1397 exits are resulted from short-circuit conditions that will generate an
1400 if (foo() || global > 10)
1403 This will be translated into:
1408 if foo() goto BB6 else goto BB5
1410 if global > 10 goto BB6 else goto BB7
1414 iftmp = (PHI 0(BB5), 1(BB6))
1415 if iftmp == 1 goto BB8 else goto BB3
1417 outside of the loop...
1419 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1420 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1421 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1422 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1425 predict_extra_loop_exits (edge exit_edge
)
1428 bool check_value_one
;
1429 gimple
*lhs_def_stmt
;
1431 tree cmp_rhs
, cmp_lhs
;
1435 last
= last_stmt (exit_edge
->src
);
1438 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1442 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1443 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1444 if (!TREE_CONSTANT (cmp_rhs
)
1445 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1447 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1450 /* If check_value_one is true, only the phi_args with value '1' will lead
1451 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1453 check_value_one
= (((integer_onep (cmp_rhs
))
1454 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1455 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1457 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1461 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1465 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1469 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1470 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1472 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1474 if ((check_value_one
^ integer_onep (val
)) == 1)
1476 if (EDGE_COUNT (e
->src
->succs
) != 1)
1478 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1482 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1483 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1487 /* Predict edge probabilities by exploiting loop structure. */
1490 predict_loops (void)
1494 /* Try to predict out blocks in a loop that are not part of a
1496 FOR_EACH_LOOP (loop
, 0)
1498 basic_block bb
, *bbs
;
1499 unsigned j
, n_exits
;
1501 struct tree_niter_desc niter_desc
;
1503 struct nb_iter_bound
*nb_iter
;
1504 enum tree_code loop_bound_code
= ERROR_MARK
;
1505 tree loop_bound_step
= NULL
;
1506 tree loop_bound_var
= NULL
;
1507 tree loop_iv_base
= NULL
;
1510 exits
= get_loop_exit_edges (loop
);
1511 n_exits
= exits
.length ();
1518 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1521 HOST_WIDE_INT nitercst
;
1522 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1524 enum br_predictor predictor
;
1526 predict_extra_loop_exits (ex
);
1528 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1529 niter
= niter_desc
.niter
;
1530 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1531 niter
= loop_niter_by_eval (loop
, ex
);
1533 if (TREE_CODE (niter
) == INTEGER_CST
)
1535 if (tree_fits_uhwi_p (niter
)
1537 && compare_tree_int (niter
, max
- 1) == -1)
1538 nitercst
= tree_to_uhwi (niter
) + 1;
1541 predictor
= PRED_LOOP_ITERATIONS
;
1543 /* If we have just one exit and we can derive some information about
1544 the number of iterations of the loop from the statements inside
1545 the loop, use it to predict this exit. */
1546 else if (n_exits
== 1)
1548 nitercst
= estimated_stmt_executions_int (loop
);
1554 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1559 /* If the prediction for number of iterations is zero, do not
1560 predict the exit edges. */
1564 probability
= ((REG_BR_PROB_BASE
+ nitercst
/ 2) / nitercst
);
1565 predict_edge (ex
, predictor
, probability
);
1569 /* Find information about loop bound variables. */
1570 for (nb_iter
= loop
->bounds
; nb_iter
;
1571 nb_iter
= nb_iter
->next
)
1573 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1575 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1578 if (!stmt
&& last_stmt (loop
->header
)
1579 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1580 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1582 is_comparison_with_loop_invariant_p (stmt
, loop
,
1588 bbs
= get_loop_body (loop
);
1590 for (j
= 0; j
< loop
->num_nodes
; j
++)
1592 int header_found
= 0;
1598 /* Bypass loop heuristics on continue statement. These
1599 statements construct loops via "non-loop" constructs
1600 in the source language and are better to be handled
1602 if (predicted_by_p (bb
, PRED_CONTINUE
))
1605 /* Loop branch heuristics - predict an edge back to a
1606 loop's head as taken. */
1607 if (bb
== loop
->latch
)
1609 e
= find_edge (loop
->latch
, loop
->header
);
1613 predict_edge_def (e
, PRED_LOOP_BRANCH
, TAKEN
);
1617 /* Loop exit heuristics - predict an edge exiting the loop if the
1618 conditional has no loop header successors as not taken. */
1620 /* If we already used more reliable loop exit predictors, do not
1621 bother with PRED_LOOP_EXIT. */
1622 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS_GUESSED
)
1623 && !predicted_by_p (bb
, PRED_LOOP_ITERATIONS
))
1625 /* For loop with many exits we don't want to predict all exits
1626 with the pretty large probability, because if all exits are
1627 considered in row, the loop would be predicted to iterate
1628 almost never. The code to divide probability by number of
1629 exits is very rough. It should compute the number of exits
1630 taken in each patch through function (not the overall number
1631 of exits that might be a lot higher for loops with wide switch
1632 statements in them) and compute n-th square root.
1634 We limit the minimal probability by 2% to avoid
1635 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1636 as this was causing regression in perl benchmark containing such
1639 int probability
= ((REG_BR_PROB_BASE
1640 - predictor_info
[(int) PRED_LOOP_EXIT
].hitrate
)
1642 if (probability
< HITRATE (2))
1643 probability
= HITRATE (2);
1644 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1645 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1646 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1647 predict_edge (e
, PRED_LOOP_EXIT
, probability
);
1650 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1652 tree_to_shwi (loop_bound_step
));
1655 /* Free basic blocks from get_loop_body. */
1660 /* Attempt to predict probabilities of BB outgoing edges using local
1663 bb_estimate_probability_locally (basic_block bb
)
1665 rtx_insn
*last_insn
= BB_END (bb
);
1668 if (! can_predict_insn_p (last_insn
))
1670 cond
= get_condition (last_insn
, NULL
, false, false);
1674 /* Try "pointer heuristic."
1675 A comparison ptr == 0 is predicted as false.
1676 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1677 if (COMPARISON_P (cond
)
1678 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
1679 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
1681 if (GET_CODE (cond
) == EQ
)
1682 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
1683 else if (GET_CODE (cond
) == NE
)
1684 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
1688 /* Try "opcode heuristic."
1689 EQ tests are usually false and NE tests are usually true. Also,
1690 most quantities are positive, so we can make the appropriate guesses
1691 about signed comparisons against zero. */
1692 switch (GET_CODE (cond
))
1695 /* Unconditional branch. */
1696 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
1697 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
1702 /* Floating point comparisons appears to behave in a very
1703 unpredictable way because of special role of = tests in
1705 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1707 /* Comparisons with 0 are often used for booleans and there is
1708 nothing useful to predict about them. */
1709 else if (XEXP (cond
, 1) == const0_rtx
1710 || XEXP (cond
, 0) == const0_rtx
)
1713 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
1718 /* Floating point comparisons appears to behave in a very
1719 unpredictable way because of special role of = tests in
1721 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
1723 /* Comparisons with 0 are often used for booleans and there is
1724 nothing useful to predict about them. */
1725 else if (XEXP (cond
, 1) == const0_rtx
1726 || XEXP (cond
, 0) == const0_rtx
)
1729 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
1733 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
1737 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
1742 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1743 || XEXP (cond
, 1) == constm1_rtx
)
1744 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
1749 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
1750 || XEXP (cond
, 1) == constm1_rtx
)
1751 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
1759 /* Set edge->probability for each successor edge of BB. */
1761 guess_outgoing_edge_probabilities (basic_block bb
)
1763 bb_estimate_probability_locally (bb
);
1764 combine_predictions_for_insn (BB_END (bb
), bb
);
1767 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
1769 /* Helper function for expr_expected_value. */
1772 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
1773 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
1778 *predictor
= PRED_UNCONDITIONAL
;
1780 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1782 if (TREE_CONSTANT (op0
))
1785 if (code
!= SSA_NAME
)
1788 def
= SSA_NAME_DEF_STMT (op0
);
1790 /* If we were already here, break the infinite cycle. */
1791 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
1794 if (gimple_code (def
) == GIMPLE_PHI
)
1796 /* All the arguments of the PHI node must have the same constant
1798 int i
, n
= gimple_phi_num_args (def
);
1799 tree val
= NULL
, new_val
;
1801 for (i
= 0; i
< n
; i
++)
1803 tree arg
= PHI_ARG_DEF (def
, i
);
1804 enum br_predictor predictor2
;
1806 /* If this PHI has itself as an argument, we cannot
1807 determine the string length of this argument. However,
1808 if we can find an expected constant value for the other
1809 PHI args then we can still be sure that this is
1810 likely a constant. So be optimistic and just
1811 continue with the next argument. */
1812 if (arg
== PHI_RESULT (def
))
1815 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
1817 /* It is difficult to combine value predictors. Simply assume
1818 that later predictor is weaker and take its prediction. */
1819 if (predictor
&& *predictor
< predictor2
)
1820 *predictor
= predictor2
;
1825 else if (!operand_equal_p (val
, new_val
, false))
1830 if (is_gimple_assign (def
))
1832 if (gimple_assign_lhs (def
) != op0
)
1835 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
1836 gimple_assign_rhs1 (def
),
1837 gimple_assign_rhs_code (def
),
1838 gimple_assign_rhs2 (def
),
1839 visited
, predictor
);
1842 if (is_gimple_call (def
))
1844 tree decl
= gimple_call_fndecl (def
);
1847 if (gimple_call_internal_p (def
)
1848 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
1850 gcc_assert (gimple_call_num_args (def
) == 3);
1851 tree val
= gimple_call_arg (def
, 0);
1852 if (TREE_CONSTANT (val
))
1856 tree val2
= gimple_call_arg (def
, 2);
1857 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
1858 && tree_fits_uhwi_p (val2
)
1859 && tree_to_uhwi (val2
) < END_PREDICTORS
);
1860 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
1862 return gimple_call_arg (def
, 1);
1866 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
1867 switch (DECL_FUNCTION_CODE (decl
))
1869 case BUILT_IN_EXPECT
:
1872 if (gimple_call_num_args (def
) != 2)
1874 val
= gimple_call_arg (def
, 0);
1875 if (TREE_CONSTANT (val
))
1878 *predictor
= PRED_BUILTIN_EXPECT
;
1879 return gimple_call_arg (def
, 1);
1882 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
1883 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
1884 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
1885 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
1886 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
1887 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
1888 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
1889 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
1890 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
1891 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
1892 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
1893 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
1894 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
1895 /* Assume that any given atomic operation has low contention,
1896 and thus the compare-and-swap operation succeeds. */
1898 *predictor
= PRED_COMPARE_AND_SWAP
;
1899 return boolean_true_node
;
1908 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
1911 enum br_predictor predictor2
;
1912 op0
= expr_expected_value (op0
, visited
, predictor
);
1915 op1
= expr_expected_value (op1
, visited
, &predictor2
);
1916 if (predictor
&& *predictor
< predictor2
)
1917 *predictor
= predictor2
;
1920 res
= fold_build2 (code
, type
, op0
, op1
);
1921 if (TREE_CONSTANT (res
))
1925 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
1928 op0
= expr_expected_value (op0
, visited
, predictor
);
1931 res
= fold_build1 (code
, type
, op0
);
1932 if (TREE_CONSTANT (res
))
1939 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1940 The function is used by builtin_expect branch predictor so the evidence
1941 must come from this construct and additional possible constant folding.
1943 We may want to implement more involved value guess (such as value range
1944 propagation based prediction), but such tricks shall go to new
1948 expr_expected_value (tree expr
, bitmap visited
,
1949 enum br_predictor
*predictor
)
1951 enum tree_code code
;
1954 if (TREE_CONSTANT (expr
))
1957 *predictor
= PRED_UNCONDITIONAL
;
1961 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
1962 return expr_expected_value_1 (TREE_TYPE (expr
),
1963 op0
, code
, op1
, visited
, predictor
);
1966 /* Predict using opcode of the last statement in basic block. */
1968 tree_predict_by_opcode (basic_block bb
)
1970 gimple
*stmt
= last_stmt (bb
);
1978 enum br_predictor predictor
;
1980 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1982 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1983 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1985 op0
= gimple_cond_lhs (stmt
);
1986 op1
= gimple_cond_rhs (stmt
);
1987 cmp
= gimple_cond_code (stmt
);
1988 type
= TREE_TYPE (op0
);
1989 visited
= BITMAP_ALLOC (NULL
);
1990 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
1992 BITMAP_FREE (visited
);
1993 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
1995 if (predictor
== PRED_BUILTIN_EXPECT
)
1997 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
1999 gcc_assert (percent
>= 0 && percent
<= 100);
2000 if (integer_zerop (val
))
2001 percent
= 100 - percent
;
2002 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2005 predict_edge (then_edge
, predictor
,
2006 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2008 /* Try "pointer heuristic."
2009 A comparison ptr == 0 is predicted as false.
2010 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2011 if (POINTER_TYPE_P (type
))
2014 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2015 else if (cmp
== NE_EXPR
)
2016 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2020 /* Try "opcode heuristic."
2021 EQ tests are usually false and NE tests are usually true. Also,
2022 most quantities are positive, so we can make the appropriate guesses
2023 about signed comparisons against zero. */
2028 /* Floating point comparisons appears to behave in a very
2029 unpredictable way because of special role of = tests in
2031 if (FLOAT_TYPE_P (type
))
2033 /* Comparisons with 0 are often used for booleans and there is
2034 nothing useful to predict about them. */
2035 else if (integer_zerop (op0
) || integer_zerop (op1
))
2038 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2043 /* Floating point comparisons appears to behave in a very
2044 unpredictable way because of special role of = tests in
2046 if (FLOAT_TYPE_P (type
))
2048 /* Comparisons with 0 are often used for booleans and there is
2049 nothing useful to predict about them. */
2050 else if (integer_zerop (op0
)
2051 || integer_zerop (op1
))
2054 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2058 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2061 case UNORDERED_EXPR
:
2062 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2067 if (integer_zerop (op1
)
2068 || integer_onep (op1
)
2069 || integer_all_onesp (op1
)
2072 || real_minus_onep (op1
))
2073 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2078 if (integer_zerop (op1
)
2079 || integer_onep (op1
)
2080 || integer_all_onesp (op1
)
2083 || real_minus_onep (op1
))
2084 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2092 /* Try to guess whether the value of return means error code. */
2094 static enum br_predictor
2095 return_prediction (tree val
, enum prediction
*prediction
)
2099 return PRED_NO_PREDICTION
;
2100 /* Different heuristics for pointers and scalars. */
2101 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2103 /* NULL is usually not returned. */
2104 if (integer_zerop (val
))
2106 *prediction
= NOT_TAKEN
;
2107 return PRED_NULL_RETURN
;
2110 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2112 /* Negative return values are often used to indicate
2114 if (TREE_CODE (val
) == INTEGER_CST
2115 && tree_int_cst_sgn (val
) < 0)
2117 *prediction
= NOT_TAKEN
;
2118 return PRED_NEGATIVE_RETURN
;
2120 /* Constant return values seems to be commonly taken.
2121 Zero/one often represent booleans so exclude them from the
2123 if (TREE_CONSTANT (val
)
2124 && (!integer_zerop (val
) && !integer_onep (val
)))
2126 *prediction
= TAKEN
;
2127 return PRED_CONST_RETURN
;
2130 return PRED_NO_PREDICTION
;
2133 /* Find the basic block with return expression and look up for possible
2134 return value trying to apply RETURN_PREDICTION heuristics. */
2136 apply_return_prediction (void)
2138 greturn
*return_stmt
= NULL
;
2142 int phi_num_args
, i
;
2143 enum br_predictor pred
;
2144 enum prediction direction
;
2147 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2149 gimple
*last
= last_stmt (e
->src
);
2151 && gimple_code (last
) == GIMPLE_RETURN
)
2153 return_stmt
= as_a
<greturn
*> (last
);
2159 return_val
= gimple_return_retval (return_stmt
);
2162 if (TREE_CODE (return_val
) != SSA_NAME
2163 || !SSA_NAME_DEF_STMT (return_val
)
2164 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2166 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2167 phi_num_args
= gimple_phi_num_args (phi
);
2168 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2170 /* Avoid the degenerate case where all return values form the function
2171 belongs to same category (ie they are all positive constants)
2172 so we can hardly say something about them. */
2173 for (i
= 1; i
< phi_num_args
; i
++)
2174 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2176 if (i
!= phi_num_args
)
2177 for (i
= 0; i
< phi_num_args
; i
++)
2179 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2180 if (pred
!= PRED_NO_PREDICTION
)
2181 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2186 /* Look for basic block that contains unlikely to happen events
2187 (such as noreturn calls) and mark all paths leading to execution
2188 of this basic blocks as unlikely. */
2191 tree_bb_level_predictions (void)
2194 bool has_return_edges
= false;
2198 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2199 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2201 has_return_edges
= true;
2205 apply_return_prediction ();
2207 FOR_EACH_BB_FN (bb
, cfun
)
2209 gimple_stmt_iterator gsi
;
2211 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2213 gimple
*stmt
= gsi_stmt (gsi
);
2216 if (is_gimple_call (stmt
))
2218 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2219 && has_return_edges
)
2220 predict_paths_leading_to (bb
, PRED_NORETURN
,
2222 decl
= gimple_call_fndecl (stmt
);
2224 && lookup_attribute ("cold",
2225 DECL_ATTRIBUTES (decl
)))
2226 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2229 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2231 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2232 gimple_predict_outcome (stmt
));
2233 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2234 hints to callers. */
2240 /* Callback for hash_map::traverse, asserts that the pointer map is
2244 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2247 gcc_assert (!value
);
2251 /* Predict branch probabilities and estimate profile for basic block BB. */
2254 tree_estimate_probability_bb (basic_block bb
)
2260 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2262 /* Predict edges to user labels with attributes. */
2263 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2265 gimple_stmt_iterator gi
;
2266 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2268 glabel
*label_stmt
= dyn_cast
<glabel
*> (gsi_stmt (gi
));
2273 decl
= gimple_label_label (label_stmt
);
2274 if (DECL_ARTIFICIAL (decl
))
2277 /* Finally, we have a user-defined label. */
2278 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2279 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2280 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2281 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2285 /* Predict early returns to be probable, as we've already taken
2286 care for error returns and other cases are often used for
2287 fast paths through function.
2289 Since we've already removed the return statements, we are
2290 looking for CFG like:
2300 if (e
->dest
!= bb
->next_bb
2301 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2302 && single_succ_p (e
->dest
)
2303 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2304 && (last
= last_stmt (e
->dest
)) != NULL
2305 && gimple_code (last
) == GIMPLE_RETURN
)
2310 if (single_succ_p (bb
))
2312 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2313 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2314 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2315 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2316 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2319 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2320 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2321 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2322 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2325 /* Look for block we are guarding (ie we dominate it,
2326 but it doesn't postdominate us). */
2327 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2328 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2329 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2331 gimple_stmt_iterator bi
;
2333 /* The call heuristic claims that a guarded function call
2334 is improbable. This is because such calls are often used
2335 to signal exceptional situations such as printing error
2337 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2340 gimple
*stmt
= gsi_stmt (bi
);
2341 if (is_gimple_call (stmt
)
2342 /* Constant and pure calls are hardly used to signalize
2343 something exceptional. */
2344 && gimple_has_side_effects (stmt
))
2346 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2352 tree_predict_by_opcode (bb
);
2355 /* Predict branch probabilities and estimate profile of the tree CFG.
2356 This function can be called from the loop optimizers to recompute
2357 the profile information.
2358 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2361 tree_estimate_probability (bool dry_run
)
2365 add_noreturn_fake_exit_edges ();
2366 connect_infinite_loops_to_exit ();
2367 /* We use loop_niter_by_eval, which requires that the loops have
2369 create_preheaders (CP_SIMPLE_PREHEADERS
);
2370 calculate_dominance_info (CDI_POST_DOMINATORS
);
2372 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2373 tree_bb_level_predictions ();
2374 record_loop_exits ();
2376 if (number_of_loops (cfun
) > 1)
2379 FOR_EACH_BB_FN (bb
, cfun
)
2380 tree_estimate_probability_bb (bb
);
2382 FOR_EACH_BB_FN (bb
, cfun
)
2383 combine_predictions_for_bb (bb
, dry_run
);
2386 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2388 delete bb_predictions
;
2389 bb_predictions
= NULL
;
2392 estimate_bb_frequencies (false);
2393 free_dominance_info (CDI_POST_DOMINATORS
);
2394 remove_fake_exit_edges ();
2397 /* Predict edges to successors of CUR whose sources are not postdominated by
2398 BB by PRED and recurse to all postdominators. */
2401 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2402 enum br_predictor pred
,
2403 enum prediction taken
,
2410 /* We are looking for all edges forming edge cut induced by
2411 set of all blocks postdominated by BB. */
2412 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2413 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2414 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2420 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2421 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2423 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2425 /* See if there is an edge from e->src that is not abnormal
2426 and does not lead to BB. */
2427 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2429 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2430 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
))
2436 /* If there is non-abnormal path leaving e->src, predict edge
2437 using predictor. Otherwise we need to look for paths
2440 The second may lead to infinite loop in the case we are predicitng
2441 regions that are only reachable by abnormal edges. We simply
2442 prevent visiting given BB twice. */
2445 if (!edge_predicted_by_p (e
, pred
, taken
))
2446 predict_edge_def (e
, pred
, taken
);
2448 else if (bitmap_set_bit (visited
, e
->src
->index
))
2449 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
);
2451 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2453 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2454 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
);
2457 /* Sets branch probabilities according to PREDiction and
2461 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2462 enum prediction taken
)
2464 bitmap visited
= BITMAP_ALLOC (NULL
);
2465 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2466 BITMAP_FREE (visited
);
2469 /* Like predict_paths_leading_to but take edge instead of basic block. */
2472 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2473 enum prediction taken
)
2475 bool has_nonloop_edge
= false;
2479 basic_block bb
= e
->src
;
2480 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2481 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2482 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2483 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2485 has_nonloop_edge
= true;
2488 if (!has_nonloop_edge
)
2490 bitmap visited
= BITMAP_ALLOC (NULL
);
2491 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
);
2492 BITMAP_FREE (visited
);
2495 predict_edge_def (e
, pred
, taken
);
2498 /* This is used to carry information about basic blocks. It is
2499 attached to the AUX field of the standard CFG block. */
2503 /* Estimated frequency of execution of basic_block. */
2506 /* To keep queue of basic blocks to process. */
2509 /* Number of predecessors we need to visit first. */
2513 /* Similar information for edges. */
2514 struct edge_prob_info
2516 /* In case edge is a loopback edge, the probability edge will be reached
2517 in case header is. Estimated number of iterations of the loop can be
2518 then computed as 1 / (1 - back_edge_prob). */
2519 sreal back_edge_prob
;
2520 /* True if the edge is a loopback edge in the natural loop. */
2521 unsigned int back_edge
:1;
2524 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2526 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2528 /* Helper function for estimate_bb_frequencies.
2529 Propagate the frequencies in blocks marked in
2530 TOVISIT, starting in HEAD. */
2533 propagate_freq (basic_block head
, bitmap tovisit
)
2542 /* For each basic block we need to visit count number of his predecessors
2543 we need to visit first. */
2544 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2549 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2551 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2553 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2555 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2557 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2559 "Irreducible region hit, ignoring edge to %i->%i\n",
2560 e
->src
->index
, bb
->index
);
2562 BLOCK_INFO (bb
)->npredecessors
= count
;
2563 /* When function never returns, we will never process exit block. */
2564 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2565 bb
->count
= bb
->frequency
= 0;
2568 BLOCK_INFO (head
)->frequency
= 1;
2570 for (bb
= head
; bb
; bb
= nextbb
)
2573 sreal cyclic_probability
= 0;
2574 sreal frequency
= 0;
2576 nextbb
= BLOCK_INFO (bb
)->next
;
2577 BLOCK_INFO (bb
)->next
= NULL
;
2579 /* Compute frequency of basic block. */
2583 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2584 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2585 || (e
->flags
& EDGE_DFS_BACK
));
2587 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2588 if (EDGE_INFO (e
)->back_edge
)
2590 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
2592 else if (!(e
->flags
& EDGE_DFS_BACK
))
2594 /* frequency += (e->probability
2595 * BLOCK_INFO (e->src)->frequency /
2596 REG_BR_PROB_BASE); */
2598 sreal tmp
= e
->probability
;
2599 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
2600 tmp
*= real_inv_br_prob_base
;
2604 if (cyclic_probability
== 0)
2606 BLOCK_INFO (bb
)->frequency
= frequency
;
2610 if (cyclic_probability
> real_almost_one
)
2611 cyclic_probability
= real_almost_one
;
2613 /* BLOCK_INFO (bb)->frequency = frequency
2614 / (1 - cyclic_probability) */
2616 cyclic_probability
= sreal (1) - cyclic_probability
;
2617 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
2621 bitmap_clear_bit (tovisit
, bb
->index
);
2623 e
= find_edge (bb
, head
);
2626 /* EDGE_INFO (e)->back_edge_prob
2627 = ((e->probability * BLOCK_INFO (bb)->frequency)
2628 / REG_BR_PROB_BASE); */
2630 sreal tmp
= e
->probability
;
2631 tmp
*= BLOCK_INFO (bb
)->frequency
;
2632 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
2635 /* Propagate to successor blocks. */
2636 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2637 if (!(e
->flags
& EDGE_DFS_BACK
)
2638 && BLOCK_INFO (e
->dest
)->npredecessors
)
2640 BLOCK_INFO (e
->dest
)->npredecessors
--;
2641 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
2646 BLOCK_INFO (last
)->next
= e
->dest
;
2654 /* Estimate frequencies in loops at same nest level. */
2657 estimate_loops_at_level (struct loop
*first_loop
)
2661 for (loop
= first_loop
; loop
; loop
= loop
->next
)
2666 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2668 estimate_loops_at_level (loop
->inner
);
2670 /* Find current loop back edge and mark it. */
2671 e
= loop_latch_edge (loop
);
2672 EDGE_INFO (e
)->back_edge
= 1;
2674 bbs
= get_loop_body (loop
);
2675 for (i
= 0; i
< loop
->num_nodes
; i
++)
2676 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
2678 propagate_freq (loop
->header
, tovisit
);
2679 BITMAP_FREE (tovisit
);
2683 /* Propagates frequencies through structure of loops. */
2686 estimate_loops (void)
2688 bitmap tovisit
= BITMAP_ALLOC (NULL
);
2691 /* Start by estimating the frequencies in the loops. */
2692 if (number_of_loops (cfun
) > 1)
2693 estimate_loops_at_level (current_loops
->tree_root
->inner
);
2695 /* Now propagate the frequencies through all the blocks. */
2696 FOR_ALL_BB_FN (bb
, cfun
)
2698 bitmap_set_bit (tovisit
, bb
->index
);
2700 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
2701 BITMAP_FREE (tovisit
);
2704 /* Drop the profile for NODE to guessed, and update its frequency based on
2705 whether it is expected to be hot given the CALL_COUNT. */
2708 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
2710 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2711 /* In the case where this was called by another function with a
2712 dropped profile, call_count will be 0. Since there are no
2713 non-zero call counts to this function, we don't know for sure
2714 whether it is hot, and therefore it will be marked normal below. */
2715 bool hot
= maybe_hot_count_p (NULL
, call_count
);
2719 "Dropping 0 profile for %s/%i. %s based on calls.\n",
2720 node
->name (), node
->order
,
2721 hot
? "Function is hot" : "Function is normal");
2722 /* We only expect to miss profiles for functions that are reached
2723 via non-zero call edges in cases where the function may have
2724 been linked from another module or library (COMDATs and extern
2725 templates). See the comments below for handle_missing_profiles.
2726 Also, only warn in cases where the missing counts exceed the
2727 number of training runs. In certain cases with an execv followed
2728 by a no-return call the profile for the no-return call is not
2729 dumped and there can be a mismatch. */
2730 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
2731 && call_count
> profile_info
->runs
)
2733 if (flag_profile_correction
)
2737 "Missing counts for called function %s/%i\n",
2738 node
->name (), node
->order
);
2741 warning (0, "Missing counts for called function %s/%i",
2742 node
->name (), node
->order
);
2745 profile_status_for_fn (fn
)
2746 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
2748 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
2751 /* In the case of COMDAT routines, multiple object files will contain the same
2752 function and the linker will select one for the binary. In that case
2753 all the other copies from the profile instrument binary will be missing
2754 profile counts. Look for cases where this happened, due to non-zero
2755 call counts going to 0-count functions, and drop the profile to guessed
2756 so that we can use the estimated probabilities and avoid optimizing only
2759 The other case where the profile may be missing is when the routine
2760 is not going to be emitted to the object file, e.g. for "extern template"
2761 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
2762 all other cases of non-zero calls to 0-count functions. */
2765 handle_missing_profiles (void)
2767 struct cgraph_node
*node
;
2768 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
2769 vec
<struct cgraph_node
*> worklist
;
2770 worklist
.create (64);
2772 /* See if 0 count function has non-0 count callers. In this case we
2773 lost some profile. Drop its function profile to PROFILE_GUESSED. */
2774 FOR_EACH_DEFINED_FUNCTION (node
)
2776 struct cgraph_edge
*e
;
2777 gcov_type call_count
= 0;
2778 gcov_type max_tp_first_run
= 0;
2779 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
2783 for (e
= node
->callers
; e
; e
= e
->next_caller
)
2785 call_count
+= e
->count
;
2787 if (e
->caller
->tp_first_run
> max_tp_first_run
)
2788 max_tp_first_run
= e
->caller
->tp_first_run
;
2791 /* If time profile is missing, let assign the maximum that comes from
2792 caller functions. */
2793 if (!node
->tp_first_run
&& max_tp_first_run
)
2794 node
->tp_first_run
= max_tp_first_run
+ 1;
2798 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
2800 drop_profile (node
, call_count
);
2801 worklist
.safe_push (node
);
2805 /* Propagate the profile dropping to other 0-count COMDATs that are
2806 potentially called by COMDATs we already dropped the profile on. */
2807 while (worklist
.length () > 0)
2809 struct cgraph_edge
*e
;
2811 node
= worklist
.pop ();
2812 for (e
= node
->callees
; e
; e
= e
->next_caller
)
2814 struct cgraph_node
*callee
= e
->callee
;
2815 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
2817 if (callee
->count
> 0)
2819 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
2820 && profile_status_for_fn (fn
) == PROFILE_READ
)
2822 drop_profile (node
, 0);
2823 worklist
.safe_push (callee
);
2827 worklist
.release ();
2830 /* Convert counts measured by profile driven feedback to frequencies.
2831 Return nonzero iff there was any nonzero execution count. */
2834 counts_to_freqs (void)
2836 gcov_type count_max
, true_count_max
= 0;
2839 /* Don't overwrite the estimated frequencies when the profile for
2840 the function is missing. We may drop this function PROFILE_GUESSED
2841 later in drop_profile (). */
2842 if (!flag_auto_profile
&& !ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
2845 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2846 true_count_max
= MAX (bb
->count
, true_count_max
);
2848 count_max
= MAX (true_count_max
, 1);
2849 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2850 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
2852 return true_count_max
;
2855 /* Return true if function is likely to be expensive, so there is no point to
2856 optimize performance of prologue, epilogue or do inlining at the expense
2857 of code size growth. THRESHOLD is the limit of number of instructions
2858 function can execute at average to be still considered not expensive. */
2861 expensive_function_p (int threshold
)
2863 unsigned int sum
= 0;
2867 /* We can not compute accurately for large thresholds due to scaled
2869 gcc_assert (threshold
<= BB_FREQ_MAX
);
2871 /* Frequencies are out of range. This either means that function contains
2872 internal loop executing more than BB_FREQ_MAX times or profile feedback
2873 is available and function has not been executed at all. */
2874 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
2877 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2878 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
2879 FOR_EACH_BB_FN (bb
, cfun
)
2883 FOR_BB_INSNS (bb
, insn
)
2884 if (active_insn_p (insn
))
2886 sum
+= bb
->frequency
;
2895 /* Estimate and propagate basic block frequencies using the given branch
2896 probabilities. If FORCE is true, the frequencies are used to estimate
2897 the counts even when there are already non-zero profile counts. */
2900 estimate_bb_frequencies (bool force
)
2905 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
2907 static int real_values_initialized
= 0;
2909 if (!real_values_initialized
)
2911 real_values_initialized
= 1;
2912 real_br_prob_base
= REG_BR_PROB_BASE
;
2913 real_bb_freq_max
= BB_FREQ_MAX
;
2914 real_one_half
= sreal (1, -1);
2915 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
2916 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
2919 mark_dfs_back_edges ();
2921 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
2924 /* Set up block info for each basic block. */
2925 alloc_aux_for_blocks (sizeof (block_info
));
2926 alloc_aux_for_edges (sizeof (edge_prob_info
));
2927 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2932 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2934 EDGE_INFO (e
)->back_edge_prob
= e
->probability
;
2935 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
2939 /* First compute frequencies locally for each loop from innermost
2940 to outermost to examine frequencies for back edges. */
2944 FOR_EACH_BB_FN (bb
, cfun
)
2945 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
2946 freq_max
= BLOCK_INFO (bb
)->frequency
;
2948 freq_max
= real_bb_freq_max
/ freq_max
;
2949 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
2951 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
2952 bb
->frequency
= tmp
.to_int ();
2955 free_aux_for_blocks ();
2956 free_aux_for_edges ();
2958 compute_function_frequency ();
2961 /* Decide whether function is hot, cold or unlikely executed. */
2963 compute_function_frequency (void)
2966 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
2968 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2969 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2970 node
->only_called_at_startup
= true;
2971 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
2972 node
->only_called_at_exit
= true;
2974 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
2976 int flags
= flags_from_decl_or_type (current_function_decl
);
2977 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
2979 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2980 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
2982 node
->frequency
= NODE_FREQUENCY_HOT
;
2983 else if (flags
& ECF_NORETURN
)
2984 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2985 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
2986 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2987 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
2988 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
2989 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
2993 /* Only first time try to drop function into unlikely executed.
2994 After inlining the roundoff errors may confuse us.
2995 Ipa-profile pass will drop functions only called from unlikely
2996 functions to unlikely and that is most of what we care about. */
2997 if (!cfun
->after_inlining
)
2998 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
2999 FOR_EACH_BB_FN (bb
, cfun
)
3001 if (maybe_hot_bb_p (cfun
, bb
))
3003 node
->frequency
= NODE_FREQUENCY_HOT
;
3006 if (!probably_never_executed_bb_p (cfun
, bb
))
3007 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3011 /* Build PREDICT_EXPR. */
3013 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3015 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3016 build_int_cst (integer_type_node
, predictor
));
3017 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3022 predictor_name (enum br_predictor predictor
)
3024 return predictor_info
[predictor
].name
;
3027 /* Predict branch probabilities and estimate profile of the tree CFG. */
3031 const pass_data pass_data_profile
=
3033 GIMPLE_PASS
, /* type */
3034 "profile_estimate", /* name */
3035 OPTGROUP_NONE
, /* optinfo_flags */
3036 TV_BRANCH_PROB
, /* tv_id */
3037 PROP_cfg
, /* properties_required */
3038 0, /* properties_provided */
3039 0, /* properties_destroyed */
3040 0, /* todo_flags_start */
3041 0, /* todo_flags_finish */
3044 class pass_profile
: public gimple_opt_pass
3047 pass_profile (gcc::context
*ctxt
)
3048 : gimple_opt_pass (pass_data_profile
, ctxt
)
3051 /* opt_pass methods: */
3052 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3053 virtual unsigned int execute (function
*);
3055 }; // class pass_profile
3058 pass_profile::execute (function
*fun
)
3062 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3065 loop_optimizer_init (LOOPS_NORMAL
);
3066 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3067 flow_loops_dump (dump_file
, NULL
, 0);
3069 mark_irreducible_loops ();
3071 nb_loops
= number_of_loops (fun
);
3075 tree_estimate_probability (false);
3080 loop_optimizer_finalize ();
3081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3082 gimple_dump_cfg (dump_file
, dump_flags
);
3083 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3084 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3091 make_pass_profile (gcc::context
*ctxt
)
3093 return new pass_profile (ctxt
);
3098 const pass_data pass_data_strip_predict_hints
=
3100 GIMPLE_PASS
, /* type */
3101 "*strip_predict_hints", /* name */
3102 OPTGROUP_NONE
, /* optinfo_flags */
3103 TV_BRANCH_PROB
, /* tv_id */
3104 PROP_cfg
, /* properties_required */
3105 0, /* properties_provided */
3106 0, /* properties_destroyed */
3107 0, /* todo_flags_start */
3108 0, /* todo_flags_finish */
3111 class pass_strip_predict_hints
: public gimple_opt_pass
3114 pass_strip_predict_hints (gcc::context
*ctxt
)
3115 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3118 /* opt_pass methods: */
3119 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3120 virtual unsigned int execute (function
*);
3122 }; // class pass_strip_predict_hints
3124 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3125 we no longer need. */
3127 pass_strip_predict_hints::execute (function
*fun
)
3133 FOR_EACH_BB_FN (bb
, fun
)
3135 gimple_stmt_iterator bi
;
3136 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3138 gimple
*stmt
= gsi_stmt (bi
);
3140 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3142 gsi_remove (&bi
, true);
3145 else if (is_gimple_call (stmt
))
3147 tree fndecl
= gimple_call_fndecl (stmt
);
3150 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3151 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3152 && gimple_call_num_args (stmt
) == 2)
3153 || (gimple_call_internal_p (stmt
)
3154 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3156 var
= gimple_call_lhs (stmt
);
3160 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3161 gsi_replace (&bi
, ass_stmt
, true);
3165 gsi_remove (&bi
, true);
3179 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3181 return new pass_strip_predict_hints (ctxt
);
3184 /* Rebuild function frequencies. Passes are in general expected to
3185 maintain profile by hand, however in some cases this is not possible:
3186 for example when inlining several functions with loops freuqencies might run
3187 out of scale and thus needs to be recomputed. */
3190 rebuild_frequencies (void)
3192 timevar_push (TV_REBUILD_FREQUENCIES
);
3194 /* When the max bb count in the function is small, there is a higher
3195 chance that there were truncation errors in the integer scaling
3196 of counts by inlining and other optimizations. This could lead
3197 to incorrect classification of code as being cold when it isn't.
3198 In that case, force the estimation of bb counts/frequencies from the
3199 branch probabilities, rather than computing frequencies from counts,
3200 which may also lead to frequencies incorrectly reduced to 0. There
3201 is less precision in the probabilities, so we only do this for small
3203 gcov_type count_max
= 0;
3205 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3206 count_max
= MAX (bb
->count
, count_max
);
3208 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3209 || (!flag_auto_profile
&& profile_status_for_fn (cfun
) == PROFILE_READ
3210 && count_max
< REG_BR_PROB_BASE
/10))
3212 loop_optimizer_init (0);
3213 add_noreturn_fake_exit_edges ();
3214 mark_irreducible_loops ();
3215 connect_infinite_loops_to_exit ();
3216 estimate_bb_frequencies (true);
3217 remove_fake_exit_edges ();
3218 loop_optimizer_finalize ();
3220 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3224 timevar_pop (TV_REBUILD_FREQUENCIES
);
3227 /* Perform a dry run of the branch prediction pass and report comparsion of
3228 the predicted and real profile into the dump file. */
3231 report_predictor_hitrates (void)
3235 loop_optimizer_init (LOOPS_NORMAL
);
3236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3237 flow_loops_dump (dump_file
, NULL
, 0);
3239 mark_irreducible_loops ();
3241 nb_loops
= number_of_loops (cfun
);
3245 tree_estimate_probability (true);
3250 loop_optimizer_finalize ();
3253 /* Force edge E to be cold.
3254 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
3255 keep low probability to represent possible error in a guess. This is used
3256 i.e. in case we predict loop to likely iterate given number of times but
3257 we are not 100% sure.
3259 This function locally updates profile without attempt to keep global
3260 consistency which can not be reached in full generality without full profile
3261 rebuild from probabilities alone. Doing so is not necessarily a good idea
3262 because frequencies and counts may be more realistic then probabilities.
3264 In some cases (such as for elimination of early exits during full loop
3265 unrolling) the caller can ensure that profile will get consistent
3269 force_edge_cold (edge e
, bool impossible
)
3271 gcov_type count_sum
= 0;
3275 gcov_type old_count
= e
->count
;
3276 int old_probability
= e
->probability
;
3277 gcov_type gcov_scale
= REG_BR_PROB_BASE
;
3278 int prob_scale
= REG_BR_PROB_BASE
;
3280 /* If edge is already improbably or cold, just return. */
3281 if (e
->probability
<= impossible
? PROB_VERY_UNLIKELY
: 0
3282 && (!impossible
|| !e
->count
))
3284 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3287 count_sum
+= e2
->count
;
3288 prob_sum
+= e2
->probability
;
3291 /* If there are other edges out of e->src, redistribute probabilitity
3296 = MIN (e
->probability
, impossible
? 0 : PROB_VERY_UNLIKELY
);
3297 if (old_probability
)
3298 e
->count
= RDIV (e
->count
* e
->probability
, old_probability
);
3300 e
->count
= MIN (e
->count
, impossible
? 0 : 1);
3303 gcov_scale
= RDIV ((count_sum
+ old_count
- e
->count
) * REG_BR_PROB_BASE
,
3305 prob_scale
= RDIV ((REG_BR_PROB_BASE
- e
->probability
) * REG_BR_PROB_BASE
,
3307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3308 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
3309 "probability to other edges.\n",
3310 e
->src
->index
, e
->dest
->index
,
3311 impossible
? "imposisble" : "cold");
3312 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3315 e2
->count
= RDIV (e2
->count
* gcov_scale
, REG_BR_PROB_BASE
);
3316 e2
->probability
= RDIV (e2
->probability
* prob_scale
,
3320 /* If all edges out of e->src are unlikely, the basic block itself
3324 e
->probability
= REG_BR_PROB_BASE
;
3326 /* If we did not adjusting, the source basic block has no likely edeges
3327 leaving other direction. In that case force that bb cold, too.
3328 This in general is difficult task to do, but handle special case when
3329 BB has only one predecestor. This is common case when we are updating
3330 after loop transforms. */
3331 if (!prob_sum
&& !count_sum
&& single_pred_p (e
->src
)
3332 && e
->src
->frequency
> (impossible
? 0 : 1))
3334 int old_frequency
= e
->src
->frequency
;
3335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3336 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
3337 impossible
? "imposisble" : "cold");
3338 e
->src
->frequency
= MIN (e
->src
->frequency
, impossible
? 0 : 1);
3339 e
->src
->count
= e
->count
= RDIV (e
->src
->count
* e
->src
->frequency
,
3341 force_edge_cold (single_pred_edge (e
->src
), impossible
);
3343 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3344 && maybe_hot_bb_p (cfun
, e
->src
))
3345 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
3346 impossible
? "imposisble" : "cold");