1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2017 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"
44 #include "diagnostic-core.h"
45 #include "gimple-predict.h"
46 #include "fold-const.h"
53 #include "gimple-iterator.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-scalar-evolution.h"
58 #include "ipa-utils.h"
59 #include "gimple-pretty-print.h"
63 /* Enum with reasons why a predictor is ignored. */
69 REASON_SINGLE_EDGE_DUPLICATE
,
70 REASON_EDGE_PAIR_DUPLICATE
73 /* String messages for the aforementioned enum. */
75 static const char *reason_messages
[] = {"", " (ignored)",
76 " (single edge duplicate)", " (edge pair duplicate)"};
78 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
79 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
80 static sreal real_almost_one
, real_br_prob_base
,
81 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
83 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
84 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
,
85 enum predictor_reason
, edge
);
86 static void predict_paths_leading_to (basic_block
, enum br_predictor
,
88 struct loop
*in_loop
= NULL
);
89 static void predict_paths_leading_to_edge (edge
, enum br_predictor
,
91 struct loop
*in_loop
= NULL
);
92 static bool can_predict_insn_p (const rtx_insn
*);
94 /* Information we hold about each branch predictor.
95 Filled using information from predict.def. */
99 const char *const name
; /* Name used in the debugging dumps. */
100 const int hitrate
; /* Expected hitrate used by
101 predict_insn_def call. */
105 /* Use given predictor without Dempster-Shaffer theory if it matches
106 using first_match heuristics. */
107 #define PRED_FLAG_FIRST_MATCH 1
109 /* Recompute hitrate in percent to our representation. */
111 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
113 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
114 static const struct predictor_info predictor_info
[]= {
115 #include "predict.def"
117 /* Upper bound on predictors. */
122 /* Return TRUE if frequency FREQ is considered to be hot. */
125 maybe_hot_frequency_p (struct function
*fun
, int freq
)
127 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
128 if (!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
130 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
132 if (node
->frequency
== NODE_FREQUENCY_HOT
)
135 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
137 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
138 && freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
* 2 / 3))
140 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
142 if (freq
* PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)
143 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
148 static gcov_type min_count
= -1;
150 /* Determine the threshold for hot BB counts. */
153 get_hot_bb_threshold ()
155 gcov_working_set_t
*ws
;
158 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
160 min_count
= ws
->min_counter
;
165 /* Set the threshold for hot BB counts. */
168 set_hot_bb_threshold (gcov_type min
)
173 /* Return TRUE if frequency FREQ is considered to be hot. */
176 maybe_hot_count_p (struct function
*, profile_count count
)
178 if (!count
.initialized_p ())
180 /* Code executed at most once is not hot. */
181 if (count
<= MAX (profile_info
? profile_info
->runs
: 1, 1))
183 return (count
.to_gcov_type () >= get_hot_bb_threshold ());
186 /* Return true in case BB can be CPU intensive and should be optimized
187 for maximal performance. */
190 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
192 gcc_checking_assert (fun
);
193 if (!maybe_hot_count_p (fun
, bb
->count
))
195 return maybe_hot_frequency_p (fun
, bb
->frequency
);
198 /* Return true in case BB can be CPU intensive and should be optimized
199 for maximal performance. */
202 maybe_hot_edge_p (edge e
)
204 if (!maybe_hot_count_p (cfun
, e
->count
))
206 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
209 /* Return true if profile COUNT and FREQUENCY, or function FUN static
210 node frequency reflects never being executed. */
213 probably_never_executed (struct function
*fun
,
214 profile_count count
, int)
216 gcc_checking_assert (fun
);
217 if (count
== profile_count::zero ())
219 if (count
.initialized_p () && profile_status_for_fn (fun
) == PROFILE_READ
)
221 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
222 if (count
.apply_scale (unlikely_count_fraction
, 1) >= profile_info
->runs
)
226 if ((!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
227 && (cgraph_node::get (fun
->decl
)->frequency
228 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
234 /* Return true in case BB is probably never executed. */
237 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
239 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
243 /* Return true if E is unlikely executed for obvious reasons. */
246 unlikely_executed_edge_p (edge e
)
248 return (e
->count
== profile_count::zero ()
249 || e
->probability
== profile_probability::never ())
250 || (e
->flags
& (EDGE_EH
| EDGE_FAKE
));
253 /* Return true in case edge E is probably never executed. */
256 probably_never_executed_edge_p (struct function
*fun
, edge e
)
258 if (unlikely_executed_edge_p (e
))
260 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
263 /* Return true when current function should always be optimized for size. */
266 optimize_function_for_size_p (struct function
*fun
)
268 if (!fun
|| !fun
->decl
)
269 return optimize_size
;
270 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
271 return n
&& n
->optimize_for_size_p ();
274 /* Return true when current function should always be optimized for speed. */
277 optimize_function_for_speed_p (struct function
*fun
)
279 return !optimize_function_for_size_p (fun
);
282 /* Return the optimization type that should be used for the function FUN. */
285 function_optimization_type (struct function
*fun
)
287 return (optimize_function_for_speed_p (fun
)
289 : OPTIMIZE_FOR_SIZE
);
292 /* Return TRUE when BB should be optimized for size. */
295 optimize_bb_for_size_p (const_basic_block bb
)
297 return (optimize_function_for_size_p (cfun
)
298 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
301 /* Return TRUE when BB should be optimized for speed. */
304 optimize_bb_for_speed_p (const_basic_block bb
)
306 return !optimize_bb_for_size_p (bb
);
309 /* Return the optimization type that should be used for block BB. */
312 bb_optimization_type (const_basic_block bb
)
314 return (optimize_bb_for_speed_p (bb
)
316 : OPTIMIZE_FOR_SIZE
);
319 /* Return TRUE when BB should be optimized for size. */
322 optimize_edge_for_size_p (edge e
)
324 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
327 /* Return TRUE when BB should be optimized for speed. */
330 optimize_edge_for_speed_p (edge e
)
332 return !optimize_edge_for_size_p (e
);
335 /* Return TRUE when BB should be optimized for size. */
338 optimize_insn_for_size_p (void)
340 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
343 /* Return TRUE when BB should be optimized for speed. */
346 optimize_insn_for_speed_p (void)
348 return !optimize_insn_for_size_p ();
351 /* Return TRUE when LOOP should be optimized for size. */
354 optimize_loop_for_size_p (struct loop
*loop
)
356 return optimize_bb_for_size_p (loop
->header
);
359 /* Return TRUE when LOOP should be optimized for speed. */
362 optimize_loop_for_speed_p (struct loop
*loop
)
364 return optimize_bb_for_speed_p (loop
->header
);
367 /* Return TRUE when LOOP nest should be optimized for speed. */
370 optimize_loop_nest_for_speed_p (struct loop
*loop
)
372 struct loop
*l
= loop
;
373 if (optimize_loop_for_speed_p (loop
))
376 while (l
&& l
!= loop
)
378 if (optimize_loop_for_speed_p (l
))
386 while (l
!= loop
&& !l
->next
)
395 /* Return TRUE when LOOP nest should be optimized for size. */
398 optimize_loop_nest_for_size_p (struct loop
*loop
)
400 return !optimize_loop_nest_for_speed_p (loop
);
403 /* Return true when edge E is likely to be well predictable by branch
407 predictable_edge_p (edge e
)
409 if (!e
->probability
.initialized_p ())
411 if ((e
->probability
.to_reg_br_prob_base ()
412 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
413 || (REG_BR_PROB_BASE
- e
->probability
.to_reg_br_prob_base ()
414 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
420 /* Set RTL expansion for BB profile. */
423 rtl_profile_for_bb (basic_block bb
)
425 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
428 /* Set RTL expansion for edge profile. */
431 rtl_profile_for_edge (edge e
)
433 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
436 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
438 default_rtl_profile (void)
440 crtl
->maybe_hot_insn_p
= true;
443 /* Return true if the one of outgoing edges is already predicted by
447 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
450 if (!INSN_P (BB_END (bb
)))
452 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
453 if (REG_NOTE_KIND (note
) == REG_BR_PRED
454 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
459 /* Structure representing predictions in tree level. */
461 struct edge_prediction
{
462 struct edge_prediction
*ep_next
;
464 enum br_predictor ep_predictor
;
468 /* This map contains for a basic block the list of predictions for the
471 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
473 /* Return true if the one of outgoing edges is already predicted by
477 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
479 struct edge_prediction
*i
;
480 edge_prediction
**preds
= bb_predictions
->get (bb
);
485 for (i
= *preds
; i
; i
= i
->ep_next
)
486 if (i
->ep_predictor
== predictor
)
491 /* Return true if the one of outgoing edges is already predicted by
492 PREDICTOR for edge E predicted as TAKEN. */
495 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
497 struct edge_prediction
*i
;
498 basic_block bb
= e
->src
;
499 edge_prediction
**preds
= bb_predictions
->get (bb
);
503 int probability
= predictor_info
[(int) predictor
].hitrate
;
506 probability
= REG_BR_PROB_BASE
- probability
;
508 for (i
= *preds
; i
; i
= i
->ep_next
)
509 if (i
->ep_predictor
== predictor
511 && i
->ep_probability
== probability
)
516 /* Same predicate as above, working on edges. */
518 edge_probability_reliable_p (const_edge e
)
520 return e
->probability
.probably_reliable_p ();
523 /* Same predicate as edge_probability_reliable_p, working on notes. */
525 br_prob_note_reliable_p (const_rtx note
)
527 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
528 return profile_probability::from_reg_br_prob_note
529 (XINT (note
, 0)).probably_reliable_p ();
533 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
535 gcc_assert (any_condjump_p (insn
));
536 if (!flag_guess_branch_prob
)
539 add_reg_note (insn
, REG_BR_PRED
,
540 gen_rtx_CONCAT (VOIDmode
,
541 GEN_INT ((int) predictor
),
542 GEN_INT ((int) probability
)));
545 /* Predict insn by given predictor. */
548 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
549 enum prediction taken
)
551 int probability
= predictor_info
[(int) predictor
].hitrate
;
554 probability
= REG_BR_PROB_BASE
- probability
;
556 predict_insn (insn
, predictor
, probability
);
559 /* Predict edge E with given probability if possible. */
562 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
565 last_insn
= BB_END (e
->src
);
567 /* We can store the branch prediction information only about
568 conditional jumps. */
569 if (!any_condjump_p (last_insn
))
572 /* We always store probability of branching. */
573 if (e
->flags
& EDGE_FALLTHRU
)
574 probability
= REG_BR_PROB_BASE
- probability
;
576 predict_insn (last_insn
, predictor
, probability
);
579 /* Predict edge E with the given PROBABILITY. */
581 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
583 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
584 && EDGE_COUNT (e
->src
->succs
) > 1
585 && flag_guess_branch_prob
588 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
589 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
593 i
->ep_probability
= probability
;
594 i
->ep_predictor
= predictor
;
599 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
600 to the filter function. */
603 filter_predictions (edge_prediction
**preds
,
604 bool (*filter
) (edge_prediction
*, void *), void *data
)
611 struct edge_prediction
**prediction
= preds
;
612 struct edge_prediction
*next
;
616 if ((*filter
) (*prediction
, data
))
617 prediction
= &((*prediction
)->ep_next
);
620 next
= (*prediction
)->ep_next
;
628 /* Filter function predicate that returns true for a edge predicate P
629 if its edge is equal to DATA. */
632 equal_edge_p (edge_prediction
*p
, void *data
)
634 return p
->ep_edge
== (edge
)data
;
637 /* Remove all predictions on given basic block that are attached
640 remove_predictions_associated_with_edge (edge e
)
645 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
646 filter_predictions (preds
, equal_edge_p
, e
);
649 /* Clears the list of predictions stored for BB. */
652 clear_bb_predictions (basic_block bb
)
654 edge_prediction
**preds
= bb_predictions
->get (bb
);
655 struct edge_prediction
*pred
, *next
;
660 for (pred
= *preds
; pred
; pred
= next
)
662 next
= pred
->ep_next
;
668 /* Return true when we can store prediction on insn INSN.
669 At the moment we represent predictions only on conditional
670 jumps, not at computed jump or other complicated cases. */
672 can_predict_insn_p (const rtx_insn
*insn
)
674 return (JUMP_P (insn
)
675 && any_condjump_p (insn
)
676 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
679 /* Predict edge E by given predictor if possible. */
682 predict_edge_def (edge e
, enum br_predictor predictor
,
683 enum prediction taken
)
685 int probability
= predictor_info
[(int) predictor
].hitrate
;
688 probability
= REG_BR_PROB_BASE
- probability
;
690 predict_edge (e
, predictor
, probability
);
693 /* Invert all branch predictions or probability notes in the INSN. This needs
694 to be done each time we invert the condition used by the jump. */
697 invert_br_probabilities (rtx insn
)
701 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
702 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
703 XINT (note
, 0) = profile_probability::from_reg_br_prob_note
704 (XINT (note
, 0)).invert ().to_reg_br_prob_note ();
705 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
706 XEXP (XEXP (note
, 0), 1)
707 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
710 /* Dump information about the branch prediction to the output file. */
713 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
714 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
724 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
725 if (! (e
->flags
& EDGE_FALLTHRU
))
728 char edge_info_str
[128];
730 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
731 ep_edge
->dest
->index
);
733 edge_info_str
[0] = '\0';
735 fprintf (file
, " %s heuristics%s%s: %.1f%%",
736 predictor_info
[predictor
].name
,
737 edge_info_str
, reason_messages
[reason
],
738 probability
* 100.0 / REG_BR_PROB_BASE
);
740 if (bb
->count
.initialized_p ())
742 fprintf (file
, " exec ");
743 bb
->count
.dump (file
);
746 fprintf (file
, " hit ");
747 e
->count
.dump (file
);
748 fprintf (file
, " (%.1f%%)", e
->count
.to_gcov_type() * 100.0
749 / bb
->count
.to_gcov_type ());
753 fprintf (file
, "\n");
756 /* Return true if STMT is known to be unlikely executed. */
759 unlikely_executed_stmt_p (gimple
*stmt
)
761 if (!is_gimple_call (stmt
))
763 /* NORETURN attribute alone is not strong enough: exit() may be quite
764 likely executed once during program run. */
765 if (gimple_call_fntype (stmt
)
766 && lookup_attribute ("cold",
767 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
768 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
770 tree decl
= gimple_call_fndecl (stmt
);
773 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
774 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
777 cgraph_node
*n
= cgraph_node::get (decl
);
782 n
= n
->ultimate_alias_target (&avail
);
783 if (avail
< AVAIL_AVAILABLE
)
786 || n
->decl
== current_function_decl
)
788 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
791 /* Return true if BB is unlikely executed. */
794 unlikely_executed_bb_p (basic_block bb
)
796 if (bb
->count
== profile_count::zero ())
798 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
800 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
801 !gsi_end_p (gsi
); gsi_next (&gsi
))
803 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
805 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
811 /* We can not predict the probabilities of outgoing edges of bb. Set them
812 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
813 even probability for all edges not mentioned in the set. These edges
814 are given PROB_VERY_UNLIKELY probability. */
817 set_even_probabilities (basic_block bb
,
818 hash_set
<edge
> *unlikely_edges
= NULL
)
824 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
825 if (!unlikely_executed_edge_p (e
))
828 /* Make the distribution even if all edges are unlikely. */
829 unsigned unlikely_count
= unlikely_edges
? unlikely_edges
->elements () : 0;
830 if (unlikely_count
== nedges
)
832 unlikely_edges
= NULL
;
836 unsigned c
= nedges
- unlikely_count
;
838 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
839 if (!unlikely_executed_edge_p (e
))
841 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
842 e
->probability
= profile_probability::very_unlikely ();
844 e
->probability
= profile_probability::guessed_always ()
848 e
->probability
= profile_probability::never ();
851 /* Add REG_BR_PROB note to JUMP with PROB. */
854 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
856 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
857 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
860 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
861 note if not already present. Remove now useless REG_BR_PRED notes. */
864 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
869 int best_probability
= PROB_EVEN
;
870 enum br_predictor best_predictor
= END_PREDICTORS
;
871 int combined_probability
= REG_BR_PROB_BASE
/ 2;
873 bool first_match
= false;
876 if (!can_predict_insn_p (insn
))
878 set_even_probabilities (bb
);
882 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
883 pnote
= ®_NOTES (insn
);
885 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
888 /* We implement "first match" heuristics and use probability guessed
889 by predictor with smallest index. */
890 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
891 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
893 enum br_predictor predictor
= ((enum br_predictor
)
894 INTVAL (XEXP (XEXP (note
, 0), 0)));
895 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
898 if (best_predictor
> predictor
899 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
900 best_probability
= probability
, best_predictor
= predictor
;
902 d
= (combined_probability
* probability
903 + (REG_BR_PROB_BASE
- combined_probability
)
904 * (REG_BR_PROB_BASE
- probability
));
906 /* Use FP math to avoid overflows of 32bit integers. */
908 /* If one probability is 0% and one 100%, avoid division by zero. */
909 combined_probability
= REG_BR_PROB_BASE
/ 2;
911 combined_probability
= (((double) combined_probability
) * probability
912 * REG_BR_PROB_BASE
/ d
+ 0.5);
915 /* Decide which heuristic to use. In case we didn't match anything,
916 use no_prediction heuristic, in case we did match, use either
917 first match or Dempster-Shaffer theory depending on the flags. */
919 if (best_predictor
!= END_PREDICTORS
)
923 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
924 combined_probability
, bb
);
928 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
929 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
931 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
932 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
936 combined_probability
= best_probability
;
937 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
941 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
943 enum br_predictor predictor
= ((enum br_predictor
)
944 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
945 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
947 dump_prediction (dump_file
, predictor
, probability
, bb
,
948 (!first_match
|| best_predictor
== predictor
)
949 ? REASON_NONE
: REASON_IGNORED
);
950 *pnote
= XEXP (*pnote
, 1);
953 pnote
= &XEXP (*pnote
, 1);
958 profile_probability p
959 = profile_probability::from_reg_br_prob_base (combined_probability
);
960 add_reg_br_prob_note (insn
, p
);
962 /* Save the prediction into CFG in case we are seeing non-degenerated
964 if (!single_succ_p (bb
))
966 BRANCH_EDGE (bb
)->probability
= p
;
967 FALLTHRU_EDGE (bb
)->probability
968 = BRANCH_EDGE (bb
)->probability
.invert ();
971 else if (!single_succ_p (bb
))
973 profile_probability prob
= profile_probability::from_reg_br_prob_note
974 (XINT (prob_note
, 0));
976 BRANCH_EDGE (bb
)->probability
= prob
;
977 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
980 single_succ_edge (bb
)->probability
= profile_probability::always ();
983 /* Edge prediction hash traits. */
985 struct predictor_hash
: pointer_hash
<edge_prediction
>
988 static inline hashval_t
hash (const edge_prediction
*);
989 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
992 /* Calculate hash value of an edge prediction P based on predictor and
993 normalized probability. */
996 predictor_hash::hash (const edge_prediction
*p
)
998 inchash::hash hstate
;
999 hstate
.add_int (p
->ep_predictor
);
1001 int prob
= p
->ep_probability
;
1002 if (prob
> REG_BR_PROB_BASE
/ 2)
1003 prob
= REG_BR_PROB_BASE
- prob
;
1005 hstate
.add_int (prob
);
1007 return hstate
.end ();
1010 /* Return true whether edge predictions P1 and P2 use the same predictor and
1011 have equal (or opposed probability). */
1014 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1016 return (p1
->ep_predictor
== p2
->ep_predictor
1017 && (p1
->ep_probability
== p2
->ep_probability
1018 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1021 struct predictor_hash_traits
: predictor_hash
,
1022 typed_noop_remove
<edge_prediction
*> {};
1024 /* Return true if edge prediction P is not in DATA hash set. */
1027 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1029 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1030 return !remove
->contains (p
);
1033 /* Prune predictions for a basic block BB. Currently we do following
1036 1) remove duplicate prediction that is guessed with the same probability
1037 (different than 1/2) to both edge
1038 2) remove duplicates for a prediction that belongs with the same probability
1044 prune_predictions_for_bb (basic_block bb
)
1046 edge_prediction
**preds
= bb_predictions
->get (bb
);
1050 hash_table
<predictor_hash_traits
> s (13);
1051 hash_set
<edge_prediction
*> remove
;
1053 /* Step 1: identify predictors that should be removed. */
1054 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1056 edge_prediction
*existing
= s
.find (pred
);
1059 if (pred
->ep_edge
== existing
->ep_edge
1060 && pred
->ep_probability
== existing
->ep_probability
)
1062 /* Remove a duplicate predictor. */
1063 dump_prediction (dump_file
, pred
->ep_predictor
,
1064 pred
->ep_probability
, bb
,
1065 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1069 else if (pred
->ep_edge
!= existing
->ep_edge
1070 && pred
->ep_probability
== existing
->ep_probability
1071 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1073 /* Remove both predictors as they predict the same
1075 dump_prediction (dump_file
, existing
->ep_predictor
,
1076 pred
->ep_probability
, bb
,
1077 REASON_EDGE_PAIR_DUPLICATE
,
1079 dump_prediction (dump_file
, pred
->ep_predictor
,
1080 pred
->ep_probability
, bb
,
1081 REASON_EDGE_PAIR_DUPLICATE
,
1084 remove
.add (existing
);
1089 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1093 /* Step 2: Remove predictors. */
1094 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1098 /* Combine predictions into single probability and store them into CFG.
1099 Remove now useless prediction entries.
1100 If DRY_RUN is set, only produce dumps and do not modify profile. */
1103 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1105 int best_probability
= PROB_EVEN
;
1106 enum br_predictor best_predictor
= END_PREDICTORS
;
1107 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1109 bool first_match
= false;
1111 struct edge_prediction
*pred
;
1113 edge e
, first
= NULL
, second
= NULL
;
1116 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1117 if (!unlikely_executed_edge_p (e
))
1120 if (first
&& !second
)
1125 else if (!e
->probability
.initialized_p ())
1126 e
->probability
= profile_probability::never ();
1128 /* When there is no successor or only one choice, prediction is easy.
1130 When we have a basic block with more than 2 successors, the situation
1131 is more complicated as DS theory cannot be used literally.
1132 More precisely, let's assume we predicted edge e1 with probability p1,
1133 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1134 need to find probability of e.g. m1({b2}), which we don't know.
1135 The only approximation is to equally distribute 1-p1 to all edges
1138 According to numbers we've got from SPEC2006 benchark, there's only
1139 one interesting reliable predictor (noreturn call), which can be
1140 handled with a bit easier approach. */
1143 hash_set
<edge
> unlikely_edges (4);
1145 /* Identify all edges that have a probability close to very unlikely.
1146 Doing the approach for very unlikely doesn't worth for doing as
1147 there's no such probability in SPEC2006 benchmark. */
1148 edge_prediction
**preds
= bb_predictions
->get (bb
);
1150 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1151 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
)
1152 unlikely_edges
.add (pred
->ep_edge
);
1154 if (!bb
->count
.initialized_p () && !dry_run
)
1155 set_even_probabilities (bb
, &unlikely_edges
);
1156 clear_bb_predictions (bb
);
1159 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1160 if (unlikely_edges
.elements () == 0)
1162 "%i edges in bb %i predicted to even probabilities\n",
1167 "%i edges in bb %i predicted with some unlikely edges\n",
1169 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1170 if (!unlikely_executed_edge_p (e
))
1171 dump_prediction (dump_file
, PRED_COMBINED
,
1172 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1179 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1181 prune_predictions_for_bb (bb
);
1183 edge_prediction
**preds
= bb_predictions
->get (bb
);
1187 /* We implement "first match" heuristics and use probability guessed
1188 by predictor with smallest index. */
1189 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1191 enum br_predictor predictor
= pred
->ep_predictor
;
1192 int probability
= pred
->ep_probability
;
1194 if (pred
->ep_edge
!= first
)
1195 probability
= REG_BR_PROB_BASE
- probability
;
1198 /* First match heuristics would be widly confused if we predicted
1200 if (best_predictor
> predictor
1201 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1203 struct edge_prediction
*pred2
;
1204 int prob
= probability
;
1206 for (pred2
= (struct edge_prediction
*) *preds
;
1207 pred2
; pred2
= pred2
->ep_next
)
1208 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1210 int probability2
= pred2
->ep_probability
;
1212 if (pred2
->ep_edge
!= first
)
1213 probability2
= REG_BR_PROB_BASE
- probability2
;
1215 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1216 (probability2
< REG_BR_PROB_BASE
/ 2))
1219 /* If the same predictor later gave better result, go for it! */
1220 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1221 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1222 prob
= probability2
;
1225 best_probability
= prob
, best_predictor
= predictor
;
1228 d
= (combined_probability
* probability
1229 + (REG_BR_PROB_BASE
- combined_probability
)
1230 * (REG_BR_PROB_BASE
- probability
));
1232 /* Use FP math to avoid overflows of 32bit integers. */
1234 /* If one probability is 0% and one 100%, avoid division by zero. */
1235 combined_probability
= REG_BR_PROB_BASE
/ 2;
1237 combined_probability
= (((double) combined_probability
)
1239 * REG_BR_PROB_BASE
/ d
+ 0.5);
1243 /* Decide which heuristic to use. In case we didn't match anything,
1244 use no_prediction heuristic, in case we did match, use either
1245 first match or Dempster-Shaffer theory depending on the flags. */
1247 if (best_predictor
!= END_PREDICTORS
)
1251 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1255 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1256 !first_match
? REASON_NONE
: REASON_IGNORED
);
1258 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1259 first_match
? REASON_NONE
: REASON_IGNORED
);
1263 combined_probability
= best_probability
;
1264 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1268 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1270 enum br_predictor predictor
= pred
->ep_predictor
;
1271 int probability
= pred
->ep_probability
;
1273 dump_prediction (dump_file
, predictor
, probability
, bb
,
1274 (!first_match
|| best_predictor
== predictor
)
1275 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1278 clear_bb_predictions (bb
);
1280 if (!bb
->count
.initialized_p () && !dry_run
)
1283 = profile_probability::from_reg_br_prob_base (combined_probability
);
1284 second
->probability
= first
->probability
.invert ();
1288 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1289 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1291 T1 and T2 should be one of the following cases:
1292 1. T1 is SSA_NAME, T2 is NULL
1293 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1294 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1297 strips_small_constant (tree t1
, tree t2
)
1304 else if (TREE_CODE (t1
) == SSA_NAME
)
1306 else if (tree_fits_shwi_p (t1
))
1307 value
= tree_to_shwi (t1
);
1313 else if (tree_fits_shwi_p (t2
))
1314 value
= tree_to_shwi (t2
);
1315 else if (TREE_CODE (t2
) == SSA_NAME
)
1323 if (value
<= 4 && value
>= -4)
1329 /* Return the SSA_NAME in T or T's operands.
1330 Return NULL if SSA_NAME cannot be found. */
1333 get_base_value (tree t
)
1335 if (TREE_CODE (t
) == SSA_NAME
)
1338 if (!BINARY_CLASS_P (t
))
1341 switch (TREE_OPERAND_LENGTH (t
))
1344 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1346 return strips_small_constant (TREE_OPERAND (t
, 0),
1347 TREE_OPERAND (t
, 1));
1353 /* Check the compare STMT in LOOP. If it compares an induction
1354 variable to a loop invariant, return true, and save
1355 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1356 Otherwise return false and set LOOP_INVAIANT to NULL. */
1359 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1360 tree
*loop_invariant
,
1361 enum tree_code
*compare_code
,
1365 tree op0
, op1
, bound
, base
;
1367 enum tree_code code
;
1370 code
= gimple_cond_code (stmt
);
1371 *loop_invariant
= NULL
;
1387 op0
= gimple_cond_lhs (stmt
);
1388 op1
= gimple_cond_rhs (stmt
);
1390 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1391 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1393 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1395 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1397 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1398 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1400 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1401 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1404 if (integer_zerop (iv0
.step
))
1406 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1407 code
= invert_tree_comparison (code
, false);
1410 if (tree_fits_shwi_p (iv1
.step
))
1419 if (tree_fits_shwi_p (iv0
.step
))
1425 if (TREE_CODE (bound
) != INTEGER_CST
)
1426 bound
= get_base_value (bound
);
1429 if (TREE_CODE (base
) != INTEGER_CST
)
1430 base
= get_base_value (base
);
1434 *loop_invariant
= bound
;
1435 *compare_code
= code
;
1437 *loop_iv_base
= base
;
1441 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1444 expr_coherent_p (tree t1
, tree t2
)
1447 tree ssa_name_1
= NULL
;
1448 tree ssa_name_2
= NULL
;
1450 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1451 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1456 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1458 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1461 /* Check to see if t1 is expressed/defined with t2. */
1462 stmt
= SSA_NAME_DEF_STMT (t1
);
1463 gcc_assert (stmt
!= NULL
);
1464 if (is_gimple_assign (stmt
))
1466 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1467 if (ssa_name_1
&& ssa_name_1
== t2
)
1471 /* Check to see if t2 is expressed/defined with t1. */
1472 stmt
= SSA_NAME_DEF_STMT (t2
);
1473 gcc_assert (stmt
!= NULL
);
1474 if (is_gimple_assign (stmt
))
1476 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1477 if (ssa_name_2
&& ssa_name_2
== t1
)
1481 /* Compare if t1 and t2's def_stmts are identical. */
1482 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1488 /* Return true if E is predicted by one of loop heuristics. */
1491 predicted_by_loop_heuristics_p (basic_block bb
)
1493 struct edge_prediction
*i
;
1494 edge_prediction
**preds
= bb_predictions
->get (bb
);
1499 for (i
= *preds
; i
; i
= i
->ep_next
)
1500 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1501 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1502 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1503 || i
->ep_predictor
== PRED_LOOP_EXIT
1504 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1505 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1510 /* Predict branch probability of BB when BB contains a branch that compares
1511 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1512 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1515 for (int i = 0; i < bound; i++) {
1522 In this loop, we will predict the branch inside the loop to be taken. */
1525 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1526 tree loop_bound_var
,
1527 tree loop_iv_base_var
,
1528 enum tree_code loop_bound_code
,
1529 int loop_bound_step
)
1532 tree compare_var
, compare_base
;
1533 enum tree_code compare_code
;
1534 tree compare_step_var
;
1538 if (predicted_by_loop_heuristics_p (bb
))
1541 stmt
= last_stmt (bb
);
1542 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1544 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1551 /* Find the taken edge. */
1552 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1553 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1556 /* When comparing an IV to a loop invariant, NE is more likely to be
1557 taken while EQ is more likely to be not-taken. */
1558 if (compare_code
== NE_EXPR
)
1560 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1563 else if (compare_code
== EQ_EXPR
)
1565 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1569 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1572 /* If loop bound, base and compare bound are all constants, we can
1573 calculate the probability directly. */
1574 if (tree_fits_shwi_p (loop_bound_var
)
1575 && tree_fits_shwi_p (compare_var
)
1576 && tree_fits_shwi_p (compare_base
))
1579 bool overflow
, overall_overflow
= false;
1580 widest_int compare_count
, tem
;
1582 /* (loop_bound - base) / compare_step */
1583 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1584 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1585 overall_overflow
|= overflow
;
1586 widest_int loop_count
= wi::div_trunc (tem
,
1587 wi::to_widest (compare_step_var
),
1589 overall_overflow
|= overflow
;
1591 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1592 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1594 /* (loop_bound - compare_bound) / compare_step */
1595 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1596 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1597 overall_overflow
|= overflow
;
1598 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1600 overall_overflow
|= overflow
;
1604 /* (compare_bound - base) / compare_step */
1605 tem
= wi::sub (wi::to_widest (compare_var
),
1606 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1607 overall_overflow
|= overflow
;
1608 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1610 overall_overflow
|= overflow
;
1612 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1614 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1616 if (wi::neg_p (compare_count
))
1618 if (wi::neg_p (loop_count
))
1620 if (loop_count
== 0)
1622 else if (wi::cmps (compare_count
, loop_count
) == 1)
1623 probability
= REG_BR_PROB_BASE
;
1626 tem
= compare_count
* REG_BR_PROB_BASE
;
1627 tem
= wi::udiv_trunc (tem
, loop_count
);
1628 probability
= tem
.to_uhwi ();
1631 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1632 if (!overall_overflow
)
1633 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1638 if (expr_coherent_p (loop_bound_var
, compare_var
))
1640 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1641 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1642 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1643 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1644 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1645 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1646 else if (loop_bound_code
== NE_EXPR
)
1648 /* If the loop backedge condition is "(i != bound)", we do
1649 the comparison based on the step of IV:
1650 * step < 0 : backedge condition is like (i > bound)
1651 * step > 0 : backedge condition is like (i < bound) */
1652 gcc_assert (loop_bound_step
!= 0);
1653 if (loop_bound_step
> 0
1654 && (compare_code
== LT_EXPR
1655 || compare_code
== LE_EXPR
))
1656 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1657 else if (loop_bound_step
< 0
1658 && (compare_code
== GT_EXPR
1659 || compare_code
== GE_EXPR
))
1660 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1662 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1665 /* The branch is predicted not-taken if loop_bound_code is
1666 opposite with compare_code. */
1667 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1669 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1672 for (i = s; i < h; i++)
1674 The branch should be predicted taken. */
1675 if (loop_bound_step
> 0
1676 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1677 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1678 else if (loop_bound_step
< 0
1679 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1680 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1682 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1686 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1687 exits are resulted from short-circuit conditions that will generate an
1690 if (foo() || global > 10)
1693 This will be translated into:
1698 if foo() goto BB6 else goto BB5
1700 if global > 10 goto BB6 else goto BB7
1704 iftmp = (PHI 0(BB5), 1(BB6))
1705 if iftmp == 1 goto BB8 else goto BB3
1707 outside of the loop...
1709 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1710 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1711 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1712 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1715 predict_extra_loop_exits (edge exit_edge
)
1718 bool check_value_one
;
1719 gimple
*lhs_def_stmt
;
1721 tree cmp_rhs
, cmp_lhs
;
1725 last
= last_stmt (exit_edge
->src
);
1728 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1732 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1733 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1734 if (!TREE_CONSTANT (cmp_rhs
)
1735 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1737 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1740 /* If check_value_one is true, only the phi_args with value '1' will lead
1741 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1743 check_value_one
= (((integer_onep (cmp_rhs
))
1744 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1745 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1747 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1751 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1755 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1759 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1760 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1762 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1764 if ((check_value_one
^ integer_onep (val
)) == 1)
1766 if (EDGE_COUNT (e
->src
->succs
) != 1)
1768 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1772 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1773 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1778 /* Predict edge probabilities by exploiting loop structure. */
1781 predict_loops (void)
1785 hash_set
<struct loop
*> with_recursion(10);
1787 FOR_EACH_BB_FN (bb
, cfun
)
1789 gimple_stmt_iterator gsi
;
1792 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1793 if (is_gimple_call (gsi_stmt (gsi
))
1794 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1795 && recursive_call_p (current_function_decl
, decl
))
1797 loop
= bb
->loop_father
;
1798 while (loop
&& !with_recursion
.add (loop
))
1799 loop
= loop_outer (loop
);
1803 /* Try to predict out blocks in a loop that are not part of a
1805 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1807 basic_block bb
, *bbs
;
1808 unsigned j
, n_exits
= 0;
1810 struct tree_niter_desc niter_desc
;
1812 struct nb_iter_bound
*nb_iter
;
1813 enum tree_code loop_bound_code
= ERROR_MARK
;
1814 tree loop_bound_step
= NULL
;
1815 tree loop_bound_var
= NULL
;
1816 tree loop_iv_base
= NULL
;
1818 bool recursion
= with_recursion
.contains (loop
);
1820 exits
= get_loop_exit_edges (loop
);
1821 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1822 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1830 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1831 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1832 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1833 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1834 && max_loop_iterations_int (loop
) >= 0)
1837 "Loop %d iterates at most %i times.\n", loop
->num
,
1838 (int)max_loop_iterations_int (loop
));
1840 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1841 && likely_max_loop_iterations_int (loop
) >= 0)
1843 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1844 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1847 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1850 HOST_WIDE_INT nitercst
;
1851 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1853 enum br_predictor predictor
;
1856 if (unlikely_executed_edge_p (ex
)
1857 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
1859 /* Loop heuristics do not expect exit conditional to be inside
1860 inner loop. We predict from innermost to outermost loop. */
1861 if (predicted_by_loop_heuristics_p (ex
->src
))
1863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1864 fprintf (dump_file
, "Skipping exit %i->%i because "
1865 "it is already predicted.\n",
1866 ex
->src
->index
, ex
->dest
->index
);
1869 predict_extra_loop_exits (ex
);
1871 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1872 niter
= niter_desc
.niter
;
1873 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1874 niter
= loop_niter_by_eval (loop
, ex
);
1875 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1876 && TREE_CODE (niter
) == INTEGER_CST
)
1878 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1879 ex
->src
->index
, ex
->dest
->index
,
1881 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1882 fprintf (dump_file
, " times.\n");
1885 if (TREE_CODE (niter
) == INTEGER_CST
)
1887 if (tree_fits_uhwi_p (niter
)
1889 && compare_tree_int (niter
, max
- 1) == -1)
1890 nitercst
= tree_to_uhwi (niter
) + 1;
1893 predictor
= PRED_LOOP_ITERATIONS
;
1895 /* If we have just one exit and we can derive some information about
1896 the number of iterations of the loop from the statements inside
1897 the loop, use it to predict this exit. */
1898 else if (n_exits
== 1
1899 && estimated_stmt_executions (loop
, &nit
))
1901 if (wi::gtu_p (nit
, max
))
1904 nitercst
= nit
.to_shwi ();
1905 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1907 /* If we have likely upper bound, trust it for very small iteration
1908 counts. Such loops would otherwise get mispredicted by standard
1909 LOOP_EXIT heuristics. */
1910 else if (n_exits
== 1
1911 && likely_max_stmt_executions (loop
, &nit
)
1913 RDIV (REG_BR_PROB_BASE
,
1917 ? PRED_LOOP_EXIT_WITH_RECURSION
1918 : PRED_LOOP_EXIT
].hitrate
)))
1920 nitercst
= nit
.to_shwi ();
1921 predictor
= PRED_LOOP_ITERATIONS_MAX
;
1925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1926 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
1927 ex
->src
->index
, ex
->dest
->index
);
1931 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1932 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
1933 (int)nitercst
, predictor_info
[predictor
].name
);
1934 /* If the prediction for number of iterations is zero, do not
1935 predict the exit edges. */
1939 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
1940 predict_edge (ex
, predictor
, probability
);
1944 /* Find information about loop bound variables. */
1945 for (nb_iter
= loop
->bounds
; nb_iter
;
1946 nb_iter
= nb_iter
->next
)
1948 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1950 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1953 if (!stmt
&& last_stmt (loop
->header
)
1954 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1955 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1957 is_comparison_with_loop_invariant_p (stmt
, loop
,
1963 bbs
= get_loop_body (loop
);
1965 for (j
= 0; j
< loop
->num_nodes
; j
++)
1972 /* Bypass loop heuristics on continue statement. These
1973 statements construct loops via "non-loop" constructs
1974 in the source language and are better to be handled
1976 if (predicted_by_p (bb
, PRED_CONTINUE
))
1978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1979 fprintf (dump_file
, "BB %i predicted by continue.\n",
1984 /* If we already used more reliable loop exit predictors, do not
1985 bother with PRED_LOOP_EXIT. */
1986 if (!predicted_by_loop_heuristics_p (bb
))
1988 /* For loop with many exits we don't want to predict all exits
1989 with the pretty large probability, because if all exits are
1990 considered in row, the loop would be predicted to iterate
1991 almost never. The code to divide probability by number of
1992 exits is very rough. It should compute the number of exits
1993 taken in each patch through function (not the overall number
1994 of exits that might be a lot higher for loops with wide switch
1995 statements in them) and compute n-th square root.
1997 We limit the minimal probability by 2% to avoid
1998 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1999 as this was causing regression in perl benchmark containing such
2002 int probability
= ((REG_BR_PROB_BASE
2005 ? PRED_LOOP_EXIT_WITH_RECURSION
2006 : PRED_LOOP_EXIT
].hitrate
)
2008 if (probability
< HITRATE (2))
2009 probability
= HITRATE (2);
2010 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2011 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2012 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2016 "Predicting exit %i->%i with prob %i.\n",
2017 e
->src
->index
, e
->dest
->index
, probability
);
2019 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2020 : PRED_LOOP_EXIT
, probability
);
2024 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2026 tree_to_shwi (loop_bound_step
));
2029 /* In the following code
2034 guess that cond is unlikely. */
2035 if (loop_outer (loop
)->num
)
2037 basic_block bb
= NULL
;
2038 edge preheader_edge
= loop_preheader_edge (loop
);
2040 if (single_pred_p (preheader_edge
->src
)
2041 && single_succ_p (preheader_edge
->src
))
2042 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2044 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2045 /* Pattern match fortran loop preheader:
2046 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2047 _17 = (logical(kind=4)) _16;
2053 Loop guard branch prediction says nothing about duplicated loop
2054 headers produced by fortran frontend and in this case we want
2055 to predict paths leading to this preheader. */
2058 && gimple_code (stmt
) == GIMPLE_COND
2059 && gimple_cond_code (stmt
) == NE_EXPR
2060 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2061 && integer_zerop (gimple_cond_rhs (stmt
)))
2063 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2064 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2065 && gimple_expr_code (call_stmt
) == NOP_EXPR
2066 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2067 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2068 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2069 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2070 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2071 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2072 == PRED_FORTRAN_LOOP_PREHEADER
)
2073 bb
= preheader_edge
->src
;
2077 if (!dominated_by_p (CDI_DOMINATORS
,
2078 loop_outer (loop
)->latch
, loop
->header
))
2079 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2081 ? PRED_LOOP_GUARD_WITH_RECURSION
2088 if (!dominated_by_p (CDI_DOMINATORS
,
2089 loop_outer (loop
)->latch
, bb
))
2090 predict_paths_leading_to (bb
,
2092 ? PRED_LOOP_GUARD_WITH_RECURSION
2099 /* Free basic blocks from get_loop_body. */
2104 /* Attempt to predict probabilities of BB outgoing edges using local
2107 bb_estimate_probability_locally (basic_block bb
)
2109 rtx_insn
*last_insn
= BB_END (bb
);
2112 if (! can_predict_insn_p (last_insn
))
2114 cond
= get_condition (last_insn
, NULL
, false, false);
2118 /* Try "pointer heuristic."
2119 A comparison ptr == 0 is predicted as false.
2120 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2121 if (COMPARISON_P (cond
)
2122 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2123 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2125 if (GET_CODE (cond
) == EQ
)
2126 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2127 else if (GET_CODE (cond
) == NE
)
2128 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2132 /* Try "opcode heuristic."
2133 EQ tests are usually false and NE tests are usually true. Also,
2134 most quantities are positive, so we can make the appropriate guesses
2135 about signed comparisons against zero. */
2136 switch (GET_CODE (cond
))
2139 /* Unconditional branch. */
2140 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2141 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2146 /* Floating point comparisons appears to behave in a very
2147 unpredictable way because of special role of = tests in
2149 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2151 /* Comparisons with 0 are often used for booleans and there is
2152 nothing useful to predict about them. */
2153 else if (XEXP (cond
, 1) == const0_rtx
2154 || XEXP (cond
, 0) == const0_rtx
)
2157 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2162 /* Floating point comparisons appears to behave in a very
2163 unpredictable way because of special role of = tests in
2165 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2167 /* Comparisons with 0 are often used for booleans and there is
2168 nothing useful to predict about them. */
2169 else if (XEXP (cond
, 1) == const0_rtx
2170 || XEXP (cond
, 0) == const0_rtx
)
2173 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2177 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2181 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2186 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2187 || XEXP (cond
, 1) == constm1_rtx
)
2188 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2193 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2194 || XEXP (cond
, 1) == constm1_rtx
)
2195 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2203 /* Set edge->probability for each successor edge of BB. */
2205 guess_outgoing_edge_probabilities (basic_block bb
)
2207 bb_estimate_probability_locally (bb
);
2208 combine_predictions_for_insn (BB_END (bb
), bb
);
2211 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
2213 /* Helper function for expr_expected_value. */
2216 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2217 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
2222 *predictor
= PRED_UNCONDITIONAL
;
2224 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2226 if (TREE_CONSTANT (op0
))
2229 if (code
== IMAGPART_EXPR
)
2231 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2233 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2234 if (is_gimple_call (def
)
2235 && gimple_call_internal_p (def
)
2236 && (gimple_call_internal_fn (def
)
2237 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2239 /* Assume that any given atomic operation has low contention,
2240 and thus the compare-and-swap operation succeeds. */
2242 *predictor
= PRED_COMPARE_AND_SWAP
;
2243 return build_one_cst (TREE_TYPE (op0
));
2248 if (code
!= SSA_NAME
)
2251 def
= SSA_NAME_DEF_STMT (op0
);
2253 /* If we were already here, break the infinite cycle. */
2254 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2257 if (gimple_code (def
) == GIMPLE_PHI
)
2259 /* All the arguments of the PHI node must have the same constant
2261 int i
, n
= gimple_phi_num_args (def
);
2262 tree val
= NULL
, new_val
;
2264 for (i
= 0; i
< n
; i
++)
2266 tree arg
= PHI_ARG_DEF (def
, i
);
2267 enum br_predictor predictor2
;
2269 /* If this PHI has itself as an argument, we cannot
2270 determine the string length of this argument. However,
2271 if we can find an expected constant value for the other
2272 PHI args then we can still be sure that this is
2273 likely a constant. So be optimistic and just
2274 continue with the next argument. */
2275 if (arg
== PHI_RESULT (def
))
2278 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
2280 /* It is difficult to combine value predictors. Simply assume
2281 that later predictor is weaker and take its prediction. */
2282 if (predictor
&& *predictor
< predictor2
)
2283 *predictor
= predictor2
;
2288 else if (!operand_equal_p (val
, new_val
, false))
2293 if (is_gimple_assign (def
))
2295 if (gimple_assign_lhs (def
) != op0
)
2298 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2299 gimple_assign_rhs1 (def
),
2300 gimple_assign_rhs_code (def
),
2301 gimple_assign_rhs2 (def
),
2302 visited
, predictor
);
2305 if (is_gimple_call (def
))
2307 tree decl
= gimple_call_fndecl (def
);
2310 if (gimple_call_internal_p (def
)
2311 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2313 gcc_assert (gimple_call_num_args (def
) == 3);
2314 tree val
= gimple_call_arg (def
, 0);
2315 if (TREE_CONSTANT (val
))
2319 tree val2
= gimple_call_arg (def
, 2);
2320 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2321 && tree_fits_uhwi_p (val2
)
2322 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2323 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2325 return gimple_call_arg (def
, 1);
2329 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2330 switch (DECL_FUNCTION_CODE (decl
))
2332 case BUILT_IN_EXPECT
:
2335 if (gimple_call_num_args (def
) != 2)
2337 val
= gimple_call_arg (def
, 0);
2338 if (TREE_CONSTANT (val
))
2341 *predictor
= PRED_BUILTIN_EXPECT
;
2342 return gimple_call_arg (def
, 1);
2345 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2346 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2347 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2348 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2349 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2350 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2351 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2352 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2353 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2354 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2355 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2356 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2357 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2358 /* Assume that any given atomic operation has low contention,
2359 and thus the compare-and-swap operation succeeds. */
2361 *predictor
= PRED_COMPARE_AND_SWAP
;
2362 return boolean_true_node
;
2371 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2374 enum br_predictor predictor2
;
2375 op0
= expr_expected_value (op0
, visited
, predictor
);
2378 op1
= expr_expected_value (op1
, visited
, &predictor2
);
2379 if (predictor
&& *predictor
< predictor2
)
2380 *predictor
= predictor2
;
2383 res
= fold_build2 (code
, type
, op0
, op1
);
2384 if (TREE_CONSTANT (res
))
2388 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2391 op0
= expr_expected_value (op0
, visited
, predictor
);
2394 res
= fold_build1 (code
, type
, op0
);
2395 if (TREE_CONSTANT (res
))
2402 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2403 The function is used by builtin_expect branch predictor so the evidence
2404 must come from this construct and additional possible constant folding.
2406 We may want to implement more involved value guess (such as value range
2407 propagation based prediction), but such tricks shall go to new
2411 expr_expected_value (tree expr
, bitmap visited
,
2412 enum br_predictor
*predictor
)
2414 enum tree_code code
;
2417 if (TREE_CONSTANT (expr
))
2420 *predictor
= PRED_UNCONDITIONAL
;
2424 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2425 return expr_expected_value_1 (TREE_TYPE (expr
),
2426 op0
, code
, op1
, visited
, predictor
);
2429 /* Predict using opcode of the last statement in basic block. */
2431 tree_predict_by_opcode (basic_block bb
)
2433 gimple
*stmt
= last_stmt (bb
);
2440 enum br_predictor predictor
;
2442 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2444 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2445 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2447 op0
= gimple_cond_lhs (stmt
);
2448 op1
= gimple_cond_rhs (stmt
);
2449 cmp
= gimple_cond_code (stmt
);
2450 type
= TREE_TYPE (op0
);
2451 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2453 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2455 if (predictor
== PRED_BUILTIN_EXPECT
)
2457 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2459 gcc_assert (percent
>= 0 && percent
<= 100);
2460 if (integer_zerop (val
))
2461 percent
= 100 - percent
;
2462 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2465 predict_edge_def (then_edge
, predictor
,
2466 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2468 /* Try "pointer heuristic."
2469 A comparison ptr == 0 is predicted as false.
2470 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2471 if (POINTER_TYPE_P (type
))
2474 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2475 else if (cmp
== NE_EXPR
)
2476 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2480 /* Try "opcode heuristic."
2481 EQ tests are usually false and NE tests are usually true. Also,
2482 most quantities are positive, so we can make the appropriate guesses
2483 about signed comparisons against zero. */
2488 /* Floating point comparisons appears to behave in a very
2489 unpredictable way because of special role of = tests in
2491 if (FLOAT_TYPE_P (type
))
2493 /* Comparisons with 0 are often used for booleans and there is
2494 nothing useful to predict about them. */
2495 else if (integer_zerop (op0
) || integer_zerop (op1
))
2498 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2503 /* Floating point comparisons appears to behave in a very
2504 unpredictable way because of special role of = tests in
2506 if (FLOAT_TYPE_P (type
))
2508 /* Comparisons with 0 are often used for booleans and there is
2509 nothing useful to predict about them. */
2510 else if (integer_zerop (op0
)
2511 || integer_zerop (op1
))
2514 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2518 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2521 case UNORDERED_EXPR
:
2522 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2527 if (integer_zerop (op1
)
2528 || integer_onep (op1
)
2529 || integer_all_onesp (op1
)
2532 || real_minus_onep (op1
))
2533 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2538 if (integer_zerop (op1
)
2539 || integer_onep (op1
)
2540 || integer_all_onesp (op1
)
2543 || real_minus_onep (op1
))
2544 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2552 /* Returns TRUE if the STMT is exit(0) like statement. */
2555 is_exit_with_zero_arg (const gimple
*stmt
)
2557 /* This is not exit, _exit or _Exit. */
2558 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2559 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2560 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2563 /* Argument is an interger zero. */
2564 return integer_zerop (gimple_call_arg (stmt
, 0));
2567 /* Try to guess whether the value of return means error code. */
2569 static enum br_predictor
2570 return_prediction (tree val
, enum prediction
*prediction
)
2574 return PRED_NO_PREDICTION
;
2575 /* Different heuristics for pointers and scalars. */
2576 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2578 /* NULL is usually not returned. */
2579 if (integer_zerop (val
))
2581 *prediction
= NOT_TAKEN
;
2582 return PRED_NULL_RETURN
;
2585 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2587 /* Negative return values are often used to indicate
2589 if (TREE_CODE (val
) == INTEGER_CST
2590 && tree_int_cst_sgn (val
) < 0)
2592 *prediction
= NOT_TAKEN
;
2593 return PRED_NEGATIVE_RETURN
;
2595 /* Constant return values seems to be commonly taken.
2596 Zero/one often represent booleans so exclude them from the
2598 if (TREE_CONSTANT (val
)
2599 && (!integer_zerop (val
) && !integer_onep (val
)))
2601 *prediction
= NOT_TAKEN
;
2602 return PRED_CONST_RETURN
;
2605 return PRED_NO_PREDICTION
;
2608 /* Find the basic block with return expression and look up for possible
2609 return value trying to apply RETURN_PREDICTION heuristics. */
2611 apply_return_prediction (void)
2613 greturn
*return_stmt
= NULL
;
2617 int phi_num_args
, i
;
2618 enum br_predictor pred
;
2619 enum prediction direction
;
2622 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2624 gimple
*last
= last_stmt (e
->src
);
2626 && gimple_code (last
) == GIMPLE_RETURN
)
2628 return_stmt
= as_a
<greturn
*> (last
);
2634 return_val
= gimple_return_retval (return_stmt
);
2637 if (TREE_CODE (return_val
) != SSA_NAME
2638 || !SSA_NAME_DEF_STMT (return_val
)
2639 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2641 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2642 phi_num_args
= gimple_phi_num_args (phi
);
2643 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2645 /* Avoid the degenerate case where all return values form the function
2646 belongs to same category (ie they are all positive constants)
2647 so we can hardly say something about them. */
2648 for (i
= 1; i
< phi_num_args
; i
++)
2649 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2651 if (i
!= phi_num_args
)
2652 for (i
= 0; i
< phi_num_args
; i
++)
2654 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2655 if (pred
!= PRED_NO_PREDICTION
)
2656 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2661 /* Look for basic block that contains unlikely to happen events
2662 (such as noreturn calls) and mark all paths leading to execution
2663 of this basic blocks as unlikely. */
2666 tree_bb_level_predictions (void)
2669 bool has_return_edges
= false;
2673 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2674 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2676 has_return_edges
= true;
2680 apply_return_prediction ();
2682 FOR_EACH_BB_FN (bb
, cfun
)
2684 gimple_stmt_iterator gsi
;
2686 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2688 gimple
*stmt
= gsi_stmt (gsi
);
2691 if (is_gimple_call (stmt
))
2693 if (gimple_call_noreturn_p (stmt
)
2695 && !is_exit_with_zero_arg (stmt
))
2696 predict_paths_leading_to (bb
, PRED_NORETURN
,
2698 decl
= gimple_call_fndecl (stmt
);
2700 && lookup_attribute ("cold",
2701 DECL_ATTRIBUTES (decl
)))
2702 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2704 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2705 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2708 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2710 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2711 gimple_predict_outcome (stmt
));
2712 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2713 hints to callers. */
2719 /* Callback for hash_map::traverse, asserts that the pointer map is
2723 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2726 gcc_assert (!value
);
2730 /* Predict branch probabilities and estimate profile for basic block BB.
2731 When LOCAL_ONLY is set do not use any global properties of CFG. */
2734 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
2739 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2741 /* Look for block we are guarding (ie we dominate it,
2742 but it doesn't postdominate us). */
2743 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2745 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2746 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2748 gimple_stmt_iterator bi
;
2750 /* The call heuristic claims that a guarded function call
2751 is improbable. This is because such calls are often used
2752 to signal exceptional situations such as printing error
2754 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2757 gimple
*stmt
= gsi_stmt (bi
);
2758 if (is_gimple_call (stmt
)
2759 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
2760 /* Constant and pure calls are hardly used to signalize
2761 something exceptional. */
2762 && gimple_has_side_effects (stmt
))
2764 if (gimple_call_fndecl (stmt
))
2765 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2766 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
2767 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
2769 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
2775 tree_predict_by_opcode (bb
);
2778 /* Predict branch probabilities and estimate profile of the tree CFG.
2779 This function can be called from the loop optimizers to recompute
2780 the profile information.
2781 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2784 tree_estimate_probability (bool dry_run
)
2788 add_noreturn_fake_exit_edges ();
2789 connect_infinite_loops_to_exit ();
2790 /* We use loop_niter_by_eval, which requires that the loops have
2792 create_preheaders (CP_SIMPLE_PREHEADERS
);
2793 calculate_dominance_info (CDI_POST_DOMINATORS
);
2795 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2796 tree_bb_level_predictions ();
2797 record_loop_exits ();
2799 if (number_of_loops (cfun
) > 1)
2802 FOR_EACH_BB_FN (bb
, cfun
)
2803 tree_estimate_probability_bb (bb
, false);
2805 FOR_EACH_BB_FN (bb
, cfun
)
2806 combine_predictions_for_bb (bb
, dry_run
);
2809 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2811 delete bb_predictions
;
2812 bb_predictions
= NULL
;
2815 estimate_bb_frequencies (false);
2816 free_dominance_info (CDI_POST_DOMINATORS
);
2817 remove_fake_exit_edges ();
2820 /* Set edge->probability for each successor edge of BB. */
2822 tree_guess_outgoing_edge_probabilities (basic_block bb
)
2824 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2825 tree_estimate_probability_bb (bb
, true);
2826 combine_predictions_for_bb (bb
, false);
2828 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2829 delete bb_predictions
;
2830 bb_predictions
= NULL
;
2833 /* Predict edges to successors of CUR whose sources are not postdominated by
2834 BB by PRED and recurse to all postdominators. */
2837 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2838 enum br_predictor pred
,
2839 enum prediction taken
,
2840 bitmap visited
, struct loop
*in_loop
= NULL
)
2846 /* If we exited the loop or CUR is unconditional in the loop, there is
2849 && (!flow_bb_inside_loop_p (in_loop
, cur
)
2850 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
2853 /* We are looking for all edges forming edge cut induced by
2854 set of all blocks postdominated by BB. */
2855 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2856 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2857 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2863 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2864 if (unlikely_executed_edge_p (e
))
2866 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2868 /* See if there is an edge from e->src that is not abnormal
2869 and does not lead to BB and does not exit the loop. */
2870 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2872 && !unlikely_executed_edge_p (e2
)
2873 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
2874 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
2880 /* If there is non-abnormal path leaving e->src, predict edge
2881 using predictor. Otherwise we need to look for paths
2884 The second may lead to infinite loop in the case we are predicitng
2885 regions that are only reachable by abnormal edges. We simply
2886 prevent visiting given BB twice. */
2889 if (!edge_predicted_by_p (e
, pred
, taken
))
2890 predict_edge_def (e
, pred
, taken
);
2892 else if (bitmap_set_bit (visited
, e
->src
->index
))
2893 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
2895 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2897 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2898 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
2901 /* Sets branch probabilities according to PREDiction and
2905 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2906 enum prediction taken
, struct loop
*in_loop
)
2908 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
2911 /* Like predict_paths_leading_to but take edge instead of basic block. */
2914 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2915 enum prediction taken
, struct loop
*in_loop
)
2917 bool has_nonloop_edge
= false;
2921 basic_block bb
= e
->src
;
2922 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2923 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2924 && !unlikely_executed_edge_p (e
)
2925 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2927 has_nonloop_edge
= true;
2930 if (!has_nonloop_edge
)
2932 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
2935 predict_edge_def (e
, pred
, taken
);
2938 /* This is used to carry information about basic blocks. It is
2939 attached to the AUX field of the standard CFG block. */
2943 /* Estimated frequency of execution of basic_block. */
2946 /* To keep queue of basic blocks to process. */
2949 /* Number of predecessors we need to visit first. */
2953 /* Similar information for edges. */
2954 struct edge_prob_info
2956 /* In case edge is a loopback edge, the probability edge will be reached
2957 in case header is. Estimated number of iterations of the loop can be
2958 then computed as 1 / (1 - back_edge_prob). */
2959 sreal back_edge_prob
;
2960 /* True if the edge is a loopback edge in the natural loop. */
2961 unsigned int back_edge
:1;
2964 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2966 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2968 /* Helper function for estimate_bb_frequencies.
2969 Propagate the frequencies in blocks marked in
2970 TOVISIT, starting in HEAD. */
2973 propagate_freq (basic_block head
, bitmap tovisit
)
2982 /* For each basic block we need to visit count number of his predecessors
2983 we need to visit first. */
2984 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2989 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2991 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2993 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2995 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2997 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2999 "Irreducible region hit, ignoring edge to %i->%i\n",
3000 e
->src
->index
, bb
->index
);
3002 BLOCK_INFO (bb
)->npredecessors
= count
;
3003 /* When function never returns, we will never process exit block. */
3004 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3006 bb
->count
= profile_count::zero ();
3011 BLOCK_INFO (head
)->frequency
= 1;
3013 for (bb
= head
; bb
; bb
= nextbb
)
3016 sreal cyclic_probability
= 0;
3017 sreal frequency
= 0;
3019 nextbb
= BLOCK_INFO (bb
)->next
;
3020 BLOCK_INFO (bb
)->next
= NULL
;
3022 /* Compute frequency of basic block. */
3026 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3027 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3028 || (e
->flags
& EDGE_DFS_BACK
));
3030 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3031 if (EDGE_INFO (e
)->back_edge
)
3033 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3035 else if (!(e
->flags
& EDGE_DFS_BACK
))
3037 /* frequency += (e->probability
3038 * BLOCK_INFO (e->src)->frequency /
3039 REG_BR_PROB_BASE); */
3041 sreal tmp
= e
->probability
.to_reg_br_prob_base ();
3042 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
3043 tmp
*= real_inv_br_prob_base
;
3047 if (cyclic_probability
== 0)
3049 BLOCK_INFO (bb
)->frequency
= frequency
;
3053 if (cyclic_probability
> real_almost_one
)
3054 cyclic_probability
= real_almost_one
;
3056 /* BLOCK_INFO (bb)->frequency = frequency
3057 / (1 - cyclic_probability) */
3059 cyclic_probability
= sreal (1) - cyclic_probability
;
3060 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
3064 bitmap_clear_bit (tovisit
, bb
->index
);
3066 e
= find_edge (bb
, head
);
3069 /* EDGE_INFO (e)->back_edge_prob
3070 = ((e->probability * BLOCK_INFO (bb)->frequency)
3071 / REG_BR_PROB_BASE); */
3073 sreal tmp
= e
->probability
.to_reg_br_prob_base ();
3074 tmp
*= BLOCK_INFO (bb
)->frequency
;
3075 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
3078 /* Propagate to successor blocks. */
3079 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3080 if (!(e
->flags
& EDGE_DFS_BACK
)
3081 && BLOCK_INFO (e
->dest
)->npredecessors
)
3083 BLOCK_INFO (e
->dest
)->npredecessors
--;
3084 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3089 BLOCK_INFO (last
)->next
= e
->dest
;
3097 /* Estimate frequencies in loops at same nest level. */
3100 estimate_loops_at_level (struct loop
*first_loop
)
3104 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3109 auto_bitmap tovisit
;
3111 estimate_loops_at_level (loop
->inner
);
3113 /* Find current loop back edge and mark it. */
3114 e
= loop_latch_edge (loop
);
3115 EDGE_INFO (e
)->back_edge
= 1;
3117 bbs
= get_loop_body (loop
);
3118 for (i
= 0; i
< loop
->num_nodes
; i
++)
3119 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3121 propagate_freq (loop
->header
, tovisit
);
3125 /* Propagates frequencies through structure of loops. */
3128 estimate_loops (void)
3130 auto_bitmap tovisit
;
3133 /* Start by estimating the frequencies in the loops. */
3134 if (number_of_loops (cfun
) > 1)
3135 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3137 /* Now propagate the frequencies through all the blocks. */
3138 FOR_ALL_BB_FN (bb
, cfun
)
3140 bitmap_set_bit (tovisit
, bb
->index
);
3142 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3145 /* Drop the profile for NODE to guessed, and update its frequency based on
3146 whether it is expected to be hot given the CALL_COUNT. */
3149 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3151 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3152 /* In the case where this was called by another function with a
3153 dropped profile, call_count will be 0. Since there are no
3154 non-zero call counts to this function, we don't know for sure
3155 whether it is hot, and therefore it will be marked normal below. */
3156 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3160 "Dropping 0 profile for %s. %s based on calls.\n",
3162 hot
? "Function is hot" : "Function is normal");
3163 /* We only expect to miss profiles for functions that are reached
3164 via non-zero call edges in cases where the function may have
3165 been linked from another module or library (COMDATs and extern
3166 templates). See the comments below for handle_missing_profiles.
3167 Also, only warn in cases where the missing counts exceed the
3168 number of training runs. In certain cases with an execv followed
3169 by a no-return call the profile for the no-return call is not
3170 dumped and there can be a mismatch. */
3171 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3172 && call_count
> profile_info
->runs
)
3174 if (flag_profile_correction
)
3178 "Missing counts for called function %s\n",
3179 node
->dump_name ());
3182 warning (0, "Missing counts for called function %s",
3183 node
->dump_name ());
3187 FOR_ALL_BB_FN (bb
, fn
)
3189 bb
->count
= profile_count::uninitialized ();
3193 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3194 e
->count
= profile_count::uninitialized ();
3197 struct cgraph_edge
*e
;
3198 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3200 e
->count
= profile_count::uninitialized ();
3201 e
->frequency
= compute_call_stmt_bb_frequency (e
->caller
->decl
,
3202 gimple_bb (e
->call_stmt
));
3204 node
->count
= profile_count::uninitialized ();
3206 profile_status_for_fn (fn
)
3207 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3209 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3212 /* In the case of COMDAT routines, multiple object files will contain the same
3213 function and the linker will select one for the binary. In that case
3214 all the other copies from the profile instrument binary will be missing
3215 profile counts. Look for cases where this happened, due to non-zero
3216 call counts going to 0-count functions, and drop the profile to guessed
3217 so that we can use the estimated probabilities and avoid optimizing only
3220 The other case where the profile may be missing is when the routine
3221 is not going to be emitted to the object file, e.g. for "extern template"
3222 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3223 all other cases of non-zero calls to 0-count functions. */
3226 handle_missing_profiles (void)
3228 struct cgraph_node
*node
;
3229 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3230 auto_vec
<struct cgraph_node
*, 64> worklist
;
3232 /* See if 0 count function has non-0 count callers. In this case we
3233 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3234 FOR_EACH_DEFINED_FUNCTION (node
)
3236 struct cgraph_edge
*e
;
3237 profile_count call_count
= profile_count::zero ();
3238 gcov_type max_tp_first_run
= 0;
3239 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3241 if (!(node
->count
== profile_count::zero ()))
3243 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3244 if (e
->count
.initialized_p () && e
->count
> 0)
3246 call_count
= call_count
+ e
->count
;
3248 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3249 max_tp_first_run
= e
->caller
->tp_first_run
;
3252 /* If time profile is missing, let assign the maximum that comes from
3253 caller functions. */
3254 if (!node
->tp_first_run
&& max_tp_first_run
)
3255 node
->tp_first_run
= max_tp_first_run
+ 1;
3259 && (call_count
.apply_scale (unlikely_count_fraction
, 1)
3260 >= profile_info
->runs
))
3262 drop_profile (node
, call_count
);
3263 worklist
.safe_push (node
);
3267 /* Propagate the profile dropping to other 0-count COMDATs that are
3268 potentially called by COMDATs we already dropped the profile on. */
3269 while (worklist
.length () > 0)
3271 struct cgraph_edge
*e
;
3273 node
= worklist
.pop ();
3274 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3276 struct cgraph_node
*callee
= e
->callee
;
3277 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3279 if (callee
->count
> 0)
3281 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3283 && profile_status_for_fn (fn
) == PROFILE_READ
)
3285 drop_profile (node
, profile_count::zero ());
3286 worklist
.safe_push (callee
);
3292 /* Convert counts measured by profile driven feedback to frequencies.
3293 Return nonzero iff there was any nonzero execution count. */
3296 counts_to_freqs (void)
3298 gcov_type count_max
;
3299 profile_count true_count_max
= profile_count::zero ();
3302 /* Don't overwrite the estimated frequencies when the profile for
3303 the function is missing. We may drop this function PROFILE_GUESSED
3304 later in drop_profile (). */
3305 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.initialized_p ()
3306 || ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3309 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3310 if (bb
->count
> true_count_max
)
3311 true_count_max
= bb
->count
;
3313 /* If we have no counts to base frequencies on, keep those that are
3315 if (!(true_count_max
> 0))
3318 count_max
= true_count_max
.to_gcov_type ();
3320 FOR_ALL_BB_FN (bb
, cfun
)
3321 if (bb
->count
.initialized_p ())
3322 bb
->frequency
= RDIV (bb
->count
.to_gcov_type () * BB_FREQ_MAX
, count_max
);
3327 /* Return true if function is likely to be expensive, so there is no point to
3328 optimize performance of prologue, epilogue or do inlining at the expense
3329 of code size growth. THRESHOLD is the limit of number of instructions
3330 function can execute at average to be still considered not expensive. */
3333 expensive_function_p (int threshold
)
3335 unsigned int sum
= 0;
3339 /* We can not compute accurately for large thresholds due to scaled
3341 gcc_assert (threshold
<= BB_FREQ_MAX
);
3343 /* Frequencies are out of range. This either means that function contains
3344 internal loop executing more than BB_FREQ_MAX times or profile feedback
3345 is available and function has not been executed at all. */
3346 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
3349 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
3350 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
3351 FOR_EACH_BB_FN (bb
, cfun
)
3355 FOR_BB_INSNS (bb
, insn
)
3356 if (active_insn_p (insn
))
3358 sum
+= bb
->frequency
;
3367 /* Determine basic blocks/edges that are known to be unlikely executed and set
3368 their counters to zero.
3369 This is done with first identifying obviously unlikely BBs/edges and then
3370 propagating in both directions. */
3373 determine_unlikely_bbs ()
3376 auto_vec
<basic_block
, 64> worklist
;
3380 FOR_EACH_BB_FN (bb
, cfun
)
3382 if (!(bb
->count
== profile_count::zero ())
3383 && unlikely_executed_bb_p (bb
))
3385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3386 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3388 bb
->count
= profile_count::zero ();
3391 if (bb
->count
== profile_count::zero ())
3394 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3395 e
->count
= profile_count::zero ();
3398 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3399 if (!(e
->count
== profile_count::zero ())
3400 && unlikely_executed_edge_p (e
))
3402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3403 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3404 bb
->index
, e
->dest
->index
);
3405 e
->count
= profile_count::zero ();
3408 gcc_checking_assert (!bb
->aux
);
3411 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3413 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3414 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3416 while (worklist
.length () > 0)
3418 bb
= worklist
.pop ();
3419 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3420 if (!(e
->count
== profile_count::zero ())
3421 && !(e
->dest
->count
== profile_count::zero ())
3424 e
->dest
->aux
= (void *)(size_t) 1;
3425 worklist
.safe_push (e
->dest
);
3430 FOR_ALL_BB_FN (bb
, cfun
)
3434 if (!(bb
->count
== profile_count::zero ())
3435 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3437 "Basic block %i is marked unlikely by forward prop\n",
3439 bb
->count
= profile_count::zero ();
3441 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3442 e
->count
= profile_count::zero ();
3448 auto_vec
<int, 64> nsuccs
;
3449 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
3450 FOR_ALL_BB_FN (bb
, cfun
)
3451 if (!(bb
->count
== profile_count::zero ())
3452 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3454 nsuccs
[bb
->index
] = 0;
3455 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3456 if (!(e
->count
== profile_count::zero ()))
3457 nsuccs
[bb
->index
]++;
3458 if (!nsuccs
[bb
->index
])
3459 worklist
.safe_push (bb
);
3461 while (worklist
.length () > 0)
3463 bb
= worklist
.pop ();
3464 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3467 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3468 !gsi_end_p (gsi
); gsi_next (&gsi
))
3469 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3470 /* stmt_can_terminate_bb_p special cases noreturns because it
3471 assumes that fake edges are created. We want to know that
3472 noreturn alone does not imply BB to be unlikely. */
3473 || (is_gimple_call (gsi_stmt (gsi
))
3474 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3482 if (!(bb
->count
== profile_count::zero ())
3483 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3485 "Basic block %i is marked unlikely by backward prop\n",
3487 bb
->count
= profile_count::zero ();
3489 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3490 if (!(e
->count
== profile_count::zero ()))
3492 e
->count
= profile_count::zero ();
3493 if (!(e
->src
->count
== profile_count::zero ()))
3495 nsuccs
[e
->src
->index
]--;
3496 if (!nsuccs
[e
->src
->index
])
3497 worklist
.safe_push (e
->src
);
3503 /* Estimate and propagate basic block frequencies using the given branch
3504 probabilities. If FORCE is true, the frequencies are used to estimate
3505 the counts even when there are already non-zero profile counts. */
3508 estimate_bb_frequencies (bool force
)
3513 determine_unlikely_bbs ();
3515 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3516 || !counts_to_freqs ())
3518 static int real_values_initialized
= 0;
3520 if (!real_values_initialized
)
3522 real_values_initialized
= 1;
3523 real_br_prob_base
= REG_BR_PROB_BASE
;
3524 real_bb_freq_max
= BB_FREQ_MAX
;
3525 real_one_half
= sreal (1, -1);
3526 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3527 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3530 mark_dfs_back_edges ();
3532 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3533 profile_probability::always ();
3535 /* Set up block info for each basic block. */
3536 alloc_aux_for_blocks (sizeof (block_info
));
3537 alloc_aux_for_edges (sizeof (edge_prob_info
));
3538 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3543 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3545 EDGE_INFO (e
)->back_edge_prob
3546 = e
->probability
.to_reg_br_prob_base ();
3547 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3551 /* First compute frequencies locally for each loop from innermost
3552 to outermost to examine frequencies for back edges. */
3556 FOR_EACH_BB_FN (bb
, cfun
)
3557 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3558 freq_max
= BLOCK_INFO (bb
)->frequency
;
3560 freq_max
= real_bb_freq_max
/ freq_max
;
3561 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3563 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3564 bb
->frequency
= tmp
.to_int ();
3567 free_aux_for_blocks ();
3568 free_aux_for_edges ();
3570 compute_function_frequency ();
3573 /* Decide whether function is hot, cold or unlikely executed. */
3575 compute_function_frequency (void)
3578 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3580 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3581 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3582 node
->only_called_at_startup
= true;
3583 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3584 node
->only_called_at_exit
= true;
3586 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3588 int flags
= flags_from_decl_or_type (current_function_decl
);
3589 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()
3590 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3592 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3593 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3595 node
->frequency
= NODE_FREQUENCY_HOT
;
3596 else if (flags
& ECF_NORETURN
)
3597 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3598 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3599 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3600 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3601 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3602 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3606 /* Only first time try to drop function into unlikely executed.
3607 After inlining the roundoff errors may confuse us.
3608 Ipa-profile pass will drop functions only called from unlikely
3609 functions to unlikely and that is most of what we care about. */
3610 if (!cfun
->after_inlining
)
3611 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3612 FOR_EACH_BB_FN (bb
, cfun
)
3614 if (maybe_hot_bb_p (cfun
, bb
))
3616 node
->frequency
= NODE_FREQUENCY_HOT
;
3619 if (!probably_never_executed_bb_p (cfun
, bb
))
3620 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3624 /* Build PREDICT_EXPR. */
3626 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3628 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3629 build_int_cst (integer_type_node
, predictor
));
3630 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3635 predictor_name (enum br_predictor predictor
)
3637 return predictor_info
[predictor
].name
;
3640 /* Predict branch probabilities and estimate profile of the tree CFG. */
3644 const pass_data pass_data_profile
=
3646 GIMPLE_PASS
, /* type */
3647 "profile_estimate", /* name */
3648 OPTGROUP_NONE
, /* optinfo_flags */
3649 TV_BRANCH_PROB
, /* tv_id */
3650 PROP_cfg
, /* properties_required */
3651 0, /* properties_provided */
3652 0, /* properties_destroyed */
3653 0, /* todo_flags_start */
3654 0, /* todo_flags_finish */
3657 class pass_profile
: public gimple_opt_pass
3660 pass_profile (gcc::context
*ctxt
)
3661 : gimple_opt_pass (pass_data_profile
, ctxt
)
3664 /* opt_pass methods: */
3665 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3666 virtual unsigned int execute (function
*);
3668 }; // class pass_profile
3671 pass_profile::execute (function
*fun
)
3675 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3678 loop_optimizer_init (LOOPS_NORMAL
);
3679 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3680 flow_loops_dump (dump_file
, NULL
, 0);
3682 mark_irreducible_loops ();
3684 nb_loops
= number_of_loops (fun
);
3688 tree_estimate_probability (false);
3693 loop_optimizer_finalize ();
3694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3695 gimple_dump_cfg (dump_file
, dump_flags
);
3696 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3697 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3698 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3701 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3702 if (loop
->header
->frequency
)
3703 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
3705 (int)expected_loop_iterations_unbounded (loop
));
3713 make_pass_profile (gcc::context
*ctxt
)
3715 return new pass_profile (ctxt
);
3720 const pass_data pass_data_strip_predict_hints
=
3722 GIMPLE_PASS
, /* type */
3723 "*strip_predict_hints", /* name */
3724 OPTGROUP_NONE
, /* optinfo_flags */
3725 TV_BRANCH_PROB
, /* tv_id */
3726 PROP_cfg
, /* properties_required */
3727 0, /* properties_provided */
3728 0, /* properties_destroyed */
3729 0, /* todo_flags_start */
3730 0, /* todo_flags_finish */
3733 class pass_strip_predict_hints
: public gimple_opt_pass
3736 pass_strip_predict_hints (gcc::context
*ctxt
)
3737 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3740 /* opt_pass methods: */
3741 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3742 virtual unsigned int execute (function
*);
3744 }; // class pass_strip_predict_hints
3746 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3747 we no longer need. */
3749 pass_strip_predict_hints::execute (function
*fun
)
3754 bool changed
= false;
3756 FOR_EACH_BB_FN (bb
, fun
)
3758 gimple_stmt_iterator bi
;
3759 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3761 gimple
*stmt
= gsi_stmt (bi
);
3763 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3765 gsi_remove (&bi
, true);
3769 else if (is_gimple_call (stmt
))
3771 tree fndecl
= gimple_call_fndecl (stmt
);
3774 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3775 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3776 && gimple_call_num_args (stmt
) == 2)
3777 || (gimple_call_internal_p (stmt
)
3778 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3780 var
= gimple_call_lhs (stmt
);
3785 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3786 gsi_replace (&bi
, ass_stmt
, true);
3790 gsi_remove (&bi
, true);
3798 return changed
? TODO_cleanup_cfg
: 0;
3804 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3806 return new pass_strip_predict_hints (ctxt
);
3809 /* Rebuild function frequencies. Passes are in general expected to
3810 maintain profile by hand, however in some cases this is not possible:
3811 for example when inlining several functions with loops freuqencies might run
3812 out of scale and thus needs to be recomputed. */
3815 rebuild_frequencies (void)
3817 timevar_push (TV_REBUILD_FREQUENCIES
);
3819 /* When the max bb count in the function is small, there is a higher
3820 chance that there were truncation errors in the integer scaling
3821 of counts by inlining and other optimizations. This could lead
3822 to incorrect classification of code as being cold when it isn't.
3823 In that case, force the estimation of bb counts/frequencies from the
3824 branch probabilities, rather than computing frequencies from counts,
3825 which may also lead to frequencies incorrectly reduced to 0. There
3826 is less precision in the probabilities, so we only do this for small
3828 profile_count count_max
= profile_count::zero ();
3830 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3831 if (bb
->count
> count_max
)
3832 count_max
= bb
->count
;
3834 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3835 || (!flag_auto_profile
&& profile_status_for_fn (cfun
) == PROFILE_READ
3836 && count_max
< REG_BR_PROB_BASE
/ 10))
3838 loop_optimizer_init (0);
3839 add_noreturn_fake_exit_edges ();
3840 mark_irreducible_loops ();
3841 connect_infinite_loops_to_exit ();
3842 estimate_bb_frequencies (true);
3843 remove_fake_exit_edges ();
3844 loop_optimizer_finalize ();
3846 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3850 timevar_pop (TV_REBUILD_FREQUENCIES
);
3853 /* Perform a dry run of the branch prediction pass and report comparsion of
3854 the predicted and real profile into the dump file. */
3857 report_predictor_hitrates (void)
3861 loop_optimizer_init (LOOPS_NORMAL
);
3862 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3863 flow_loops_dump (dump_file
, NULL
, 0);
3865 mark_irreducible_loops ();
3867 nb_loops
= number_of_loops (cfun
);
3871 tree_estimate_probability (true);
3876 loop_optimizer_finalize ();
3879 /* Force edge E to be cold.
3880 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
3881 keep low probability to represent possible error in a guess. This is used
3882 i.e. in case we predict loop to likely iterate given number of times but
3883 we are not 100% sure.
3885 This function locally updates profile without attempt to keep global
3886 consistency which can not be reached in full generality without full profile
3887 rebuild from probabilities alone. Doing so is not necessarily a good idea
3888 because frequencies and counts may be more realistic then probabilities.
3890 In some cases (such as for elimination of early exits during full loop
3891 unrolling) the caller can ensure that profile will get consistent
3895 force_edge_cold (edge e
, bool impossible
)
3897 profile_count count_sum
= profile_count::zero ();
3898 profile_probability prob_sum
= profile_probability::never ();
3901 profile_count old_count
= e
->count
;
3902 profile_probability old_probability
= e
->probability
;
3903 bool uninitialized_exit
= false;
3905 profile_probability goal
= (impossible
? profile_probability::never ()
3906 : profile_probability::very_unlikely ());
3908 /* If edge is already improbably or cold, just return. */
3909 if (e
->probability
<= goal
3910 && (!impossible
|| e
->count
== profile_count::zero ()))
3912 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3915 if (e2
->count
.initialized_p ())
3916 count_sum
+= e2
->count
;
3918 uninitialized_exit
= true;
3919 if (e2
->probability
.initialized_p ())
3920 prob_sum
+= e2
->probability
;
3923 /* If there are other edges out of e->src, redistribute probabilitity
3925 if (prob_sum
> profile_probability::never ())
3927 if (!(e
->probability
< goal
))
3928 e
->probability
= goal
;
3930 e
->count
= profile_count::zero ();
3931 else if (old_probability
> profile_probability::never ())
3932 e
->count
= e
->count
.apply_probability (e
->probability
3935 e
->count
= e
->count
.apply_scale (1, REG_BR_PROB_BASE
);
3937 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
3939 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3940 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
3941 "probability to other edges.\n",
3942 e
->src
->index
, e
->dest
->index
,
3943 impossible
? "impossible" : "cold");
3944 profile_count count_sum2
= count_sum
+ old_count
- e
->count
;
3945 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3949 e2
->count
.apply_scale (count_sum2
, count_sum
);
3950 e2
->probability
/= prob_comp
;
3952 if (current_ir_type () != IR_GIMPLE
3953 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3954 update_br_prob_note (e
->src
);
3956 /* If all edges out of e->src are unlikely, the basic block itself
3960 if (prob_sum
== profile_probability::never ())
3961 e
->probability
= profile_probability::always ();
3965 e
->probability
= profile_probability::never ();
3966 /* If BB has some edges out that are not impossible, we can not
3967 assume that BB itself is. */
3970 if (current_ir_type () != IR_GIMPLE
3971 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3972 update_br_prob_note (e
->src
);
3973 if (e
->src
->count
== profile_count::zero ())
3975 if (count_sum
== profile_count::zero () && !uninitialized_exit
3979 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3981 else if (current_ir_type () == IR_GIMPLE
)
3982 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
3983 !gsi_end_p (gsi
); gsi_next (&gsi
))
3985 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
3991 /* FIXME: Implement RTL path. */
3996 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3998 "Making bb %i impossible and dropping count to 0.\n",
4000 e
->count
= profile_count::zero ();
4001 e
->src
->count
= profile_count::zero ();
4002 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4003 force_edge_cold (e2
, impossible
);
4008 /* If we did not adjusting, the source basic block has no likely edeges
4009 leaving other direction. In that case force that bb cold, too.
4010 This in general is difficult task to do, but handle special case when
4011 BB has only one predecestor. This is common case when we are updating
4012 after loop transforms. */
4013 if (!(prob_sum
> profile_probability::never ())
4014 && count_sum
== profile_count::zero ()
4015 && single_pred_p (e
->src
) && e
->src
->frequency
> (impossible
? 0 : 1))
4017 int old_frequency
= e
->src
->frequency
;
4018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4019 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4020 impossible
? "impossible" : "cold");
4021 e
->src
->frequency
= MIN (e
->src
->frequency
, impossible
? 0 : 1);
4023 e
->src
->count
= e
->count
= profile_count::zero ();
4025 e
->src
->count
= e
->count
= e
->count
.apply_scale (e
->src
->frequency
,
4027 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4029 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4030 && maybe_hot_bb_p (cfun
, e
->src
))
4031 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4032 impossible
? "impossible" : "cold");
4038 namespace selftest
{
4040 /* Test that value range of predictor values defined in predict.def is
4041 within range (50, 100]. */
4043 struct branch_predictor
4046 unsigned probability
;
4049 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4052 test_prediction_value_range ()
4054 branch_predictor predictors
[] = {
4055 #include "predict.def"
4059 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4061 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4062 ASSERT_TRUE (p
> 50 && p
<= 100);
4066 #undef DEF_PREDICTOR
4068 /* Run all of the selfests within this file. */
4073 test_prediction_value_range ();
4076 } // namespace selftest
4077 #endif /* CHECKING_P. */