1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2018 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"
62 #include "stringpool.h"
65 /* Enum with reasons why a predictor is ignored. */
71 REASON_SINGLE_EDGE_DUPLICATE
,
72 REASON_EDGE_PAIR_DUPLICATE
75 /* String messages for the aforementioned enum. */
77 static const char *reason_messages
[] = {"", " (ignored)",
78 " (single edge duplicate)", " (edge pair duplicate)"};
80 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
81 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
82 static sreal real_almost_one
, real_br_prob_base
,
83 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
85 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
86 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
,
87 enum predictor_reason
, edge
);
88 static void predict_paths_leading_to (basic_block
, enum br_predictor
,
90 struct loop
*in_loop
= NULL
);
91 static void predict_paths_leading_to_edge (edge
, enum br_predictor
,
93 struct loop
*in_loop
= NULL
);
94 static bool can_predict_insn_p (const rtx_insn
*);
96 /* Information we hold about each branch predictor.
97 Filled using information from predict.def. */
101 const char *const name
; /* Name used in the debugging dumps. */
102 const int hitrate
; /* Expected hitrate used by
103 predict_insn_def call. */
107 /* Use given predictor without Dempster-Shaffer theory if it matches
108 using first_match heuristics. */
109 #define PRED_FLAG_FIRST_MATCH 1
111 /* Recompute hitrate in percent to our representation. */
113 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
115 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
116 static const struct predictor_info predictor_info
[]= {
117 #include "predict.def"
119 /* Upper bound on predictors. */
124 static gcov_type min_count
= -1;
126 /* Determine the threshold for hot BB counts. */
129 get_hot_bb_threshold ()
131 gcov_working_set_t
*ws
;
134 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
136 min_count
= ws
->min_counter
;
141 /* Set the threshold for hot BB counts. */
144 set_hot_bb_threshold (gcov_type min
)
149 /* Return TRUE if frequency FREQ is considered to be hot. */
152 maybe_hot_count_p (struct function
*fun
, profile_count count
)
154 if (!count
.initialized_p ())
156 if (count
.ipa () == profile_count::zero ())
160 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
161 if (!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
163 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
165 if (node
->frequency
== NODE_FREQUENCY_HOT
)
168 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
170 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
171 && count
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
.apply_scale (2, 3)))
173 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
175 if (count
.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
), 1)
176 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
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 return maybe_hot_count_p (fun
, bb
->count
);
196 /* Return true in case BB can be CPU intensive and should be optimized
197 for maximal performance. */
200 maybe_hot_edge_p (edge e
)
202 return maybe_hot_count_p (cfun
, e
->count ());
205 /* Return true if profile COUNT and FREQUENCY, or function FUN static
206 node frequency reflects never being executed. */
209 probably_never_executed (struct function
*fun
,
212 gcc_checking_assert (fun
);
213 if (count
.ipa () == profile_count::zero ())
215 /* Do not trust adjusted counts. This will make us to drop int cold section
216 code with low execution count as a result of inlining. These low counts
217 are not safe even with read profile and may lead us to dropping
218 code which actually gets executed into cold section of binary that is not
220 if (count
.precise_p () && profile_status_for_fn (fun
) == PROFILE_READ
)
222 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
223 if (count
.apply_scale (unlikely_count_fraction
, 1) >= profile_info
->runs
)
227 if ((!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
228 && (cgraph_node::get (fun
->decl
)->frequency
229 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
235 /* Return true in case BB is probably never executed. */
238 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
240 return probably_never_executed (fun
, bb
->count
);
244 /* Return true if E is unlikely executed for obvious reasons. */
247 unlikely_executed_edge_p (edge e
)
249 return (e
->count () == profile_count::zero ()
250 || e
->probability
== profile_probability::never ())
251 || (e
->flags
& (EDGE_EH
| EDGE_FAKE
));
254 /* Return true in case edge E is probably never executed. */
257 probably_never_executed_edge_p (struct function
*fun
, edge e
)
259 if (unlikely_executed_edge_p (e
))
261 return probably_never_executed (fun
, e
->count ());
264 /* Return true when current function should always be optimized for size. */
267 optimize_function_for_size_p (struct function
*fun
)
269 if (!fun
|| !fun
->decl
)
270 return optimize_size
;
271 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
272 return n
&& n
->optimize_for_size_p ();
275 /* Return true when current function should always be optimized for speed. */
278 optimize_function_for_speed_p (struct function
*fun
)
280 return !optimize_function_for_size_p (fun
);
283 /* Return the optimization type that should be used for the function FUN. */
286 function_optimization_type (struct function
*fun
)
288 return (optimize_function_for_speed_p (fun
)
290 : OPTIMIZE_FOR_SIZE
);
293 /* Return TRUE when BB should be optimized for size. */
296 optimize_bb_for_size_p (const_basic_block bb
)
298 return (optimize_function_for_size_p (cfun
)
299 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
302 /* Return TRUE when BB should be optimized for speed. */
305 optimize_bb_for_speed_p (const_basic_block bb
)
307 return !optimize_bb_for_size_p (bb
);
310 /* Return the optimization type that should be used for block BB. */
313 bb_optimization_type (const_basic_block bb
)
315 return (optimize_bb_for_speed_p (bb
)
317 : OPTIMIZE_FOR_SIZE
);
320 /* Return TRUE when BB should be optimized for size. */
323 optimize_edge_for_size_p (edge e
)
325 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
328 /* Return TRUE when BB should be optimized for speed. */
331 optimize_edge_for_speed_p (edge e
)
333 return !optimize_edge_for_size_p (e
);
336 /* Return TRUE when BB should be optimized for size. */
339 optimize_insn_for_size_p (void)
341 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
344 /* Return TRUE when BB should be optimized for speed. */
347 optimize_insn_for_speed_p (void)
349 return !optimize_insn_for_size_p ();
352 /* Return TRUE when LOOP should be optimized for size. */
355 optimize_loop_for_size_p (struct loop
*loop
)
357 return optimize_bb_for_size_p (loop
->header
);
360 /* Return TRUE when LOOP should be optimized for speed. */
363 optimize_loop_for_speed_p (struct loop
*loop
)
365 return optimize_bb_for_speed_p (loop
->header
);
368 /* Return TRUE when LOOP nest should be optimized for speed. */
371 optimize_loop_nest_for_speed_p (struct loop
*loop
)
373 struct loop
*l
= loop
;
374 if (optimize_loop_for_speed_p (loop
))
377 while (l
&& l
!= loop
)
379 if (optimize_loop_for_speed_p (l
))
387 while (l
!= loop
&& !l
->next
)
396 /* Return TRUE when LOOP nest should be optimized for size. */
399 optimize_loop_nest_for_size_p (struct loop
*loop
)
401 return !optimize_loop_nest_for_speed_p (loop
);
404 /* Return true when edge E is likely to be well predictable by branch
408 predictable_edge_p (edge e
)
410 if (!e
->probability
.initialized_p ())
412 if ((e
->probability
.to_reg_br_prob_base ()
413 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
414 || (REG_BR_PROB_BASE
- e
->probability
.to_reg_br_prob_base ()
415 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
421 /* Set RTL expansion for BB profile. */
424 rtl_profile_for_bb (basic_block bb
)
426 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
429 /* Set RTL expansion for edge profile. */
432 rtl_profile_for_edge (edge e
)
434 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
437 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
439 default_rtl_profile (void)
441 crtl
->maybe_hot_insn_p
= true;
444 /* Return true if the one of outgoing edges is already predicted by
448 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
451 if (!INSN_P (BB_END (bb
)))
453 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
454 if (REG_NOTE_KIND (note
) == REG_BR_PRED
455 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
460 /* Structure representing predictions in tree level. */
462 struct edge_prediction
{
463 struct edge_prediction
*ep_next
;
465 enum br_predictor ep_predictor
;
469 /* This map contains for a basic block the list of predictions for the
472 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
474 /* Return true if the one of outgoing edges is already predicted by
478 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
480 struct edge_prediction
*i
;
481 edge_prediction
**preds
= bb_predictions
->get (bb
);
486 for (i
= *preds
; i
; i
= i
->ep_next
)
487 if (i
->ep_predictor
== predictor
)
492 /* Return true if the one of outgoing edges is already predicted by
493 PREDICTOR for edge E predicted as TAKEN. */
496 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
498 struct edge_prediction
*i
;
499 basic_block bb
= e
->src
;
500 edge_prediction
**preds
= bb_predictions
->get (bb
);
504 int probability
= predictor_info
[(int) predictor
].hitrate
;
507 probability
= REG_BR_PROB_BASE
- probability
;
509 for (i
= *preds
; i
; i
= i
->ep_next
)
510 if (i
->ep_predictor
== predictor
512 && i
->ep_probability
== probability
)
517 /* Same predicate as above, working on edges. */
519 edge_probability_reliable_p (const_edge e
)
521 return e
->probability
.probably_reliable_p ();
524 /* Same predicate as edge_probability_reliable_p, working on notes. */
526 br_prob_note_reliable_p (const_rtx note
)
528 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
529 return profile_probability::from_reg_br_prob_note
530 (XINT (note
, 0)).probably_reliable_p ();
534 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
536 gcc_assert (any_condjump_p (insn
));
537 if (!flag_guess_branch_prob
)
540 add_reg_note (insn
, REG_BR_PRED
,
541 gen_rtx_CONCAT (VOIDmode
,
542 GEN_INT ((int) predictor
),
543 GEN_INT ((int) probability
)));
546 /* Predict insn by given predictor. */
549 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
550 enum prediction taken
)
552 int probability
= predictor_info
[(int) predictor
].hitrate
;
553 gcc_assert (probability
!= PROB_UNINITIALIZED
);
556 probability
= REG_BR_PROB_BASE
- probability
;
558 predict_insn (insn
, predictor
, probability
);
561 /* Predict edge E with given probability if possible. */
564 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
567 last_insn
= BB_END (e
->src
);
569 /* We can store the branch prediction information only about
570 conditional jumps. */
571 if (!any_condjump_p (last_insn
))
574 /* We always store probability of branching. */
575 if (e
->flags
& EDGE_FALLTHRU
)
576 probability
= REG_BR_PROB_BASE
- probability
;
578 predict_insn (last_insn
, predictor
, probability
);
581 /* Predict edge E with the given PROBABILITY. */
583 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
585 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
586 && EDGE_COUNT (e
->src
->succs
) > 1
587 && flag_guess_branch_prob
590 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
591 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
595 i
->ep_probability
= probability
;
596 i
->ep_predictor
= predictor
;
601 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
602 to the filter function. */
605 filter_predictions (edge_prediction
**preds
,
606 bool (*filter
) (edge_prediction
*, void *), void *data
)
613 struct edge_prediction
**prediction
= preds
;
614 struct edge_prediction
*next
;
618 if ((*filter
) (*prediction
, data
))
619 prediction
= &((*prediction
)->ep_next
);
622 next
= (*prediction
)->ep_next
;
630 /* Filter function predicate that returns true for a edge predicate P
631 if its edge is equal to DATA. */
634 equal_edge_p (edge_prediction
*p
, void *data
)
636 return p
->ep_edge
== (edge
)data
;
639 /* Remove all predictions on given basic block that are attached
642 remove_predictions_associated_with_edge (edge e
)
647 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
648 filter_predictions (preds
, equal_edge_p
, e
);
651 /* Clears the list of predictions stored for BB. */
654 clear_bb_predictions (basic_block bb
)
656 edge_prediction
**preds
= bb_predictions
->get (bb
);
657 struct edge_prediction
*pred
, *next
;
662 for (pred
= *preds
; pred
; pred
= next
)
664 next
= pred
->ep_next
;
670 /* Return true when we can store prediction on insn INSN.
671 At the moment we represent predictions only on conditional
672 jumps, not at computed jump or other complicated cases. */
674 can_predict_insn_p (const rtx_insn
*insn
)
676 return (JUMP_P (insn
)
677 && any_condjump_p (insn
)
678 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
681 /* Predict edge E by given predictor if possible. */
684 predict_edge_def (edge e
, enum br_predictor predictor
,
685 enum prediction taken
)
687 int probability
= predictor_info
[(int) predictor
].hitrate
;
690 probability
= REG_BR_PROB_BASE
- probability
;
692 predict_edge (e
, predictor
, probability
);
695 /* Invert all branch predictions or probability notes in the INSN. This needs
696 to be done each time we invert the condition used by the jump. */
699 invert_br_probabilities (rtx insn
)
703 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
704 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
705 XINT (note
, 0) = profile_probability::from_reg_br_prob_note
706 (XINT (note
, 0)).invert ().to_reg_br_prob_note ();
707 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
708 XEXP (XEXP (note
, 0), 1)
709 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
712 /* Dump information about the branch prediction to the output file. */
715 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
716 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
726 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
727 if (! (e
->flags
& EDGE_FALLTHRU
))
730 char edge_info_str
[128];
732 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
733 ep_edge
->dest
->index
);
735 edge_info_str
[0] = '\0';
737 fprintf (file
, " %s heuristics%s%s: %.2f%%",
738 predictor_info
[predictor
].name
,
739 edge_info_str
, reason_messages
[reason
],
740 probability
* 100.0 / REG_BR_PROB_BASE
);
742 if (bb
->count
.initialized_p ())
744 fprintf (file
, " exec ");
745 bb
->count
.dump (file
);
748 fprintf (file
, " hit ");
749 e
->count ().dump (file
);
750 fprintf (file
, " (%.1f%%)", e
->count ().to_gcov_type() * 100.0
751 / bb
->count
.to_gcov_type ());
755 fprintf (file
, "\n");
757 /* Print output that be easily read by analyze_brprob.py script. We are
758 interested only in counts that are read from GCDA files. */
759 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
760 && bb
->count
.precise_p ()
761 && reason
== REASON_NONE
)
763 gcc_assert (e
->count ().precise_p ());
764 fprintf (file
, ";;heuristics;%s;%" PRId64
";%" PRId64
";%.1f;\n",
765 predictor_info
[predictor
].name
,
766 bb
->count
.to_gcov_type (), e
->count ().to_gcov_type (),
767 probability
* 100.0 / REG_BR_PROB_BASE
);
771 /* Return true if STMT is known to be unlikely executed. */
774 unlikely_executed_stmt_p (gimple
*stmt
)
776 if (!is_gimple_call (stmt
))
778 /* NORETURN attribute alone is not strong enough: exit() may be quite
779 likely executed once during program run. */
780 if (gimple_call_fntype (stmt
)
781 && lookup_attribute ("cold",
782 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
783 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
785 tree decl
= gimple_call_fndecl (stmt
);
788 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
789 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
792 cgraph_node
*n
= cgraph_node::get (decl
);
797 n
= n
->ultimate_alias_target (&avail
);
798 if (avail
< AVAIL_AVAILABLE
)
801 || n
->decl
== current_function_decl
)
803 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
806 /* Return true if BB is unlikely executed. */
809 unlikely_executed_bb_p (basic_block bb
)
811 if (bb
->count
== profile_count::zero ())
813 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
815 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
816 !gsi_end_p (gsi
); gsi_next (&gsi
))
818 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
820 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
826 /* We can not predict the probabilities of outgoing edges of bb. Set them
827 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
828 even probability for all edges not mentioned in the set. These edges
829 are given PROB_VERY_UNLIKELY probability. */
832 set_even_probabilities (basic_block bb
,
833 hash_set
<edge
> *unlikely_edges
= NULL
)
835 unsigned nedges
= 0, unlikely_count
= 0;
838 profile_probability all
= profile_probability::always ();
840 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
841 if (e
->probability
.initialized_p ())
842 all
-= e
->probability
;
843 else if (!unlikely_executed_edge_p (e
))
846 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
848 all
-= profile_probability::very_unlikely ();
853 /* Make the distribution even if all edges are unlikely. */
854 if (unlikely_count
== nedges
)
856 unlikely_edges
= NULL
;
860 unsigned c
= nedges
- unlikely_count
;
862 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
863 if (e
->probability
.initialized_p ())
865 else if (!unlikely_executed_edge_p (e
))
867 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
868 e
->probability
= profile_probability::very_unlikely ();
870 e
->probability
= all
.apply_scale (1, c
).guessed ();
873 e
->probability
= profile_probability::never ();
876 /* Add REG_BR_PROB note to JUMP with PROB. */
879 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
881 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
882 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
885 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
886 note if not already present. Remove now useless REG_BR_PRED notes. */
889 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
894 int best_probability
= PROB_EVEN
;
895 enum br_predictor best_predictor
= END_PREDICTORS
;
896 int combined_probability
= REG_BR_PROB_BASE
/ 2;
898 bool first_match
= false;
901 if (!can_predict_insn_p (insn
))
903 set_even_probabilities (bb
);
907 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
908 pnote
= ®_NOTES (insn
);
910 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
913 /* We implement "first match" heuristics and use probability guessed
914 by predictor with smallest index. */
915 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
916 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
918 enum br_predictor predictor
= ((enum br_predictor
)
919 INTVAL (XEXP (XEXP (note
, 0), 0)));
920 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
923 if (best_predictor
> predictor
924 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
925 best_probability
= probability
, best_predictor
= predictor
;
927 d
= (combined_probability
* probability
928 + (REG_BR_PROB_BASE
- combined_probability
)
929 * (REG_BR_PROB_BASE
- probability
));
931 /* Use FP math to avoid overflows of 32bit integers. */
933 /* If one probability is 0% and one 100%, avoid division by zero. */
934 combined_probability
= REG_BR_PROB_BASE
/ 2;
936 combined_probability
= (((double) combined_probability
) * probability
937 * REG_BR_PROB_BASE
/ d
+ 0.5);
940 /* Decide which heuristic to use. In case we didn't match anything,
941 use no_prediction heuristic, in case we did match, use either
942 first match or Dempster-Shaffer theory depending on the flags. */
944 if (best_predictor
!= END_PREDICTORS
)
948 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
949 combined_probability
, bb
);
953 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
954 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
956 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
957 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
961 combined_probability
= best_probability
;
962 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
966 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
968 enum br_predictor predictor
= ((enum br_predictor
)
969 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
970 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
972 dump_prediction (dump_file
, predictor
, probability
, bb
,
973 (!first_match
|| best_predictor
== predictor
)
974 ? REASON_NONE
: REASON_IGNORED
);
975 *pnote
= XEXP (*pnote
, 1);
978 pnote
= &XEXP (*pnote
, 1);
983 profile_probability p
984 = profile_probability::from_reg_br_prob_base (combined_probability
);
985 add_reg_br_prob_note (insn
, p
);
987 /* Save the prediction into CFG in case we are seeing non-degenerated
989 if (!single_succ_p (bb
))
991 BRANCH_EDGE (bb
)->probability
= p
;
992 FALLTHRU_EDGE (bb
)->probability
993 = BRANCH_EDGE (bb
)->probability
.invert ();
996 else if (!single_succ_p (bb
))
998 profile_probability prob
= profile_probability::from_reg_br_prob_note
999 (XINT (prob_note
, 0));
1001 BRANCH_EDGE (bb
)->probability
= prob
;
1002 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
1005 single_succ_edge (bb
)->probability
= profile_probability::always ();
1008 /* Edge prediction hash traits. */
1010 struct predictor_hash
: pointer_hash
<edge_prediction
>
1013 static inline hashval_t
hash (const edge_prediction
*);
1014 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
1017 /* Calculate hash value of an edge prediction P based on predictor and
1018 normalized probability. */
1021 predictor_hash::hash (const edge_prediction
*p
)
1023 inchash::hash hstate
;
1024 hstate
.add_int (p
->ep_predictor
);
1026 int prob
= p
->ep_probability
;
1027 if (prob
> REG_BR_PROB_BASE
/ 2)
1028 prob
= REG_BR_PROB_BASE
- prob
;
1030 hstate
.add_int (prob
);
1032 return hstate
.end ();
1035 /* Return true whether edge predictions P1 and P2 use the same predictor and
1036 have equal (or opposed probability). */
1039 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1041 return (p1
->ep_predictor
== p2
->ep_predictor
1042 && (p1
->ep_probability
== p2
->ep_probability
1043 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1046 struct predictor_hash_traits
: predictor_hash
,
1047 typed_noop_remove
<edge_prediction
*> {};
1049 /* Return true if edge prediction P is not in DATA hash set. */
1052 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1054 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1055 return !remove
->contains (p
);
1058 /* Prune predictions for a basic block BB. Currently we do following
1061 1) remove duplicate prediction that is guessed with the same probability
1062 (different than 1/2) to both edge
1063 2) remove duplicates for a prediction that belongs with the same probability
1069 prune_predictions_for_bb (basic_block bb
)
1071 edge_prediction
**preds
= bb_predictions
->get (bb
);
1075 hash_table
<predictor_hash_traits
> s (13);
1076 hash_set
<edge_prediction
*> remove
;
1078 /* Step 1: identify predictors that should be removed. */
1079 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1081 edge_prediction
*existing
= s
.find (pred
);
1084 if (pred
->ep_edge
== existing
->ep_edge
1085 && pred
->ep_probability
== existing
->ep_probability
)
1087 /* Remove a duplicate predictor. */
1088 dump_prediction (dump_file
, pred
->ep_predictor
,
1089 pred
->ep_probability
, bb
,
1090 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1094 else if (pred
->ep_edge
!= existing
->ep_edge
1095 && pred
->ep_probability
== existing
->ep_probability
1096 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1098 /* Remove both predictors as they predict the same
1100 dump_prediction (dump_file
, existing
->ep_predictor
,
1101 pred
->ep_probability
, bb
,
1102 REASON_EDGE_PAIR_DUPLICATE
,
1104 dump_prediction (dump_file
, pred
->ep_predictor
,
1105 pred
->ep_probability
, bb
,
1106 REASON_EDGE_PAIR_DUPLICATE
,
1109 remove
.add (existing
);
1114 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1118 /* Step 2: Remove predictors. */
1119 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1123 /* Combine predictions into single probability and store them into CFG.
1124 Remove now useless prediction entries.
1125 If DRY_RUN is set, only produce dumps and do not modify profile. */
1128 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1130 int best_probability
= PROB_EVEN
;
1131 enum br_predictor best_predictor
= END_PREDICTORS
;
1132 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1134 bool first_match
= false;
1136 struct edge_prediction
*pred
;
1138 edge e
, first
= NULL
, second
= NULL
;
1143 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1145 if (!unlikely_executed_edge_p (e
))
1148 if (first
&& !second
)
1153 else if (!e
->probability
.initialized_p ())
1154 e
->probability
= profile_probability::never ();
1155 if (!e
->probability
.initialized_p ())
1157 else if (e
->probability
== profile_probability::never ())
1161 /* When there is no successor or only one choice, prediction is easy.
1163 When we have a basic block with more than 2 successors, the situation
1164 is more complicated as DS theory cannot be used literally.
1165 More precisely, let's assume we predicted edge e1 with probability p1,
1166 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1167 need to find probability of e.g. m1({b2}), which we don't know.
1168 The only approximation is to equally distribute 1-p1 to all edges
1171 According to numbers we've got from SPEC2006 benchark, there's only
1172 one interesting reliable predictor (noreturn call), which can be
1173 handled with a bit easier approach. */
1176 hash_set
<edge
> unlikely_edges (4);
1178 /* Identify all edges that have a probability close to very unlikely.
1179 Doing the approach for very unlikely doesn't worth for doing as
1180 there's no such probability in SPEC2006 benchmark. */
1181 edge_prediction
**preds
= bb_predictions
->get (bb
);
1183 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1184 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
)
1185 unlikely_edges
.add (pred
->ep_edge
);
1188 set_even_probabilities (bb
, &unlikely_edges
);
1189 clear_bb_predictions (bb
);
1192 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1193 if (unlikely_edges
.elements () == 0)
1195 "%i edges in bb %i predicted to even probabilities\n",
1200 "%i edges in bb %i predicted with some unlikely edges\n",
1202 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1203 if (!unlikely_executed_edge_p (e
))
1204 dump_prediction (dump_file
, PRED_COMBINED
,
1205 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1212 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1214 prune_predictions_for_bb (bb
);
1216 edge_prediction
**preds
= bb_predictions
->get (bb
);
1220 /* We implement "first match" heuristics and use probability guessed
1221 by predictor with smallest index. */
1222 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1224 enum br_predictor predictor
= pred
->ep_predictor
;
1225 int probability
= pred
->ep_probability
;
1227 if (pred
->ep_edge
!= first
)
1228 probability
= REG_BR_PROB_BASE
- probability
;
1231 /* First match heuristics would be widly confused if we predicted
1233 if (best_predictor
> predictor
1234 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1236 struct edge_prediction
*pred2
;
1237 int prob
= probability
;
1239 for (pred2
= (struct edge_prediction
*) *preds
;
1240 pred2
; pred2
= pred2
->ep_next
)
1241 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1243 int probability2
= pred2
->ep_probability
;
1245 if (pred2
->ep_edge
!= first
)
1246 probability2
= REG_BR_PROB_BASE
- probability2
;
1248 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1249 (probability2
< REG_BR_PROB_BASE
/ 2))
1252 /* If the same predictor later gave better result, go for it! */
1253 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1254 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1255 prob
= probability2
;
1258 best_probability
= prob
, best_predictor
= predictor
;
1261 d
= (combined_probability
* probability
1262 + (REG_BR_PROB_BASE
- combined_probability
)
1263 * (REG_BR_PROB_BASE
- probability
));
1265 /* Use FP math to avoid overflows of 32bit integers. */
1267 /* If one probability is 0% and one 100%, avoid division by zero. */
1268 combined_probability
= REG_BR_PROB_BASE
/ 2;
1270 combined_probability
= (((double) combined_probability
)
1272 * REG_BR_PROB_BASE
/ d
+ 0.5);
1276 /* Decide which heuristic to use. In case we didn't match anything,
1277 use no_prediction heuristic, in case we did match, use either
1278 first match or Dempster-Shaffer theory depending on the flags. */
1280 if (best_predictor
!= END_PREDICTORS
)
1284 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1288 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1289 !first_match
? REASON_NONE
: REASON_IGNORED
);
1291 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1292 first_match
? REASON_NONE
: REASON_IGNORED
);
1296 combined_probability
= best_probability
;
1297 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1301 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1303 enum br_predictor predictor
= pred
->ep_predictor
;
1304 int probability
= pred
->ep_probability
;
1306 dump_prediction (dump_file
, predictor
, probability
, bb
,
1307 (!first_match
|| best_predictor
== predictor
)
1308 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1311 clear_bb_predictions (bb
);
1314 /* If we have only one successor which is unknown, we can compute missing
1318 profile_probability prob
= profile_probability::always ();
1319 edge missing
= NULL
;
1321 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1322 if (e
->probability
.initialized_p ())
1323 prob
-= e
->probability
;
1324 else if (missing
== NULL
)
1328 missing
->probability
= prob
;
1330 /* If nothing is unknown, we have nothing to update. */
1331 else if (!nunknown
&& nzero
!= (int)EDGE_COUNT (bb
->succs
))
1336 = profile_probability::from_reg_br_prob_base (combined_probability
);
1337 second
->probability
= first
->probability
.invert ();
1341 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1342 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1344 T1 and T2 should be one of the following cases:
1345 1. T1 is SSA_NAME, T2 is NULL
1346 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1347 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1350 strips_small_constant (tree t1
, tree t2
)
1357 else if (TREE_CODE (t1
) == SSA_NAME
)
1359 else if (tree_fits_shwi_p (t1
))
1360 value
= tree_to_shwi (t1
);
1366 else if (tree_fits_shwi_p (t2
))
1367 value
= tree_to_shwi (t2
);
1368 else if (TREE_CODE (t2
) == SSA_NAME
)
1376 if (value
<= 4 && value
>= -4)
1382 /* Return the SSA_NAME in T or T's operands.
1383 Return NULL if SSA_NAME cannot be found. */
1386 get_base_value (tree t
)
1388 if (TREE_CODE (t
) == SSA_NAME
)
1391 if (!BINARY_CLASS_P (t
))
1394 switch (TREE_OPERAND_LENGTH (t
))
1397 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1399 return strips_small_constant (TREE_OPERAND (t
, 0),
1400 TREE_OPERAND (t
, 1));
1406 /* Check the compare STMT in LOOP. If it compares an induction
1407 variable to a loop invariant, return true, and save
1408 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1409 Otherwise return false and set LOOP_INVAIANT to NULL. */
1412 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1413 tree
*loop_invariant
,
1414 enum tree_code
*compare_code
,
1418 tree op0
, op1
, bound
, base
;
1420 enum tree_code code
;
1423 code
= gimple_cond_code (stmt
);
1424 *loop_invariant
= NULL
;
1440 op0
= gimple_cond_lhs (stmt
);
1441 op1
= gimple_cond_rhs (stmt
);
1443 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1444 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1446 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1448 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1450 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1451 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1453 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1454 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1457 if (integer_zerop (iv0
.step
))
1459 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1460 code
= invert_tree_comparison (code
, false);
1463 if (tree_fits_shwi_p (iv1
.step
))
1472 if (tree_fits_shwi_p (iv0
.step
))
1478 if (TREE_CODE (bound
) != INTEGER_CST
)
1479 bound
= get_base_value (bound
);
1482 if (TREE_CODE (base
) != INTEGER_CST
)
1483 base
= get_base_value (base
);
1487 *loop_invariant
= bound
;
1488 *compare_code
= code
;
1490 *loop_iv_base
= base
;
1494 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1497 expr_coherent_p (tree t1
, tree t2
)
1500 tree ssa_name_1
= NULL
;
1501 tree ssa_name_2
= NULL
;
1503 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1504 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1509 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1511 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1514 /* Check to see if t1 is expressed/defined with t2. */
1515 stmt
= SSA_NAME_DEF_STMT (t1
);
1516 gcc_assert (stmt
!= NULL
);
1517 if (is_gimple_assign (stmt
))
1519 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1520 if (ssa_name_1
&& ssa_name_1
== t2
)
1524 /* Check to see if t2 is expressed/defined with t1. */
1525 stmt
= SSA_NAME_DEF_STMT (t2
);
1526 gcc_assert (stmt
!= NULL
);
1527 if (is_gimple_assign (stmt
))
1529 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1530 if (ssa_name_2
&& ssa_name_2
== t1
)
1534 /* Compare if t1 and t2's def_stmts are identical. */
1535 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1541 /* Return true if E is predicted by one of loop heuristics. */
1544 predicted_by_loop_heuristics_p (basic_block bb
)
1546 struct edge_prediction
*i
;
1547 edge_prediction
**preds
= bb_predictions
->get (bb
);
1552 for (i
= *preds
; i
; i
= i
->ep_next
)
1553 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1554 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1555 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1556 || i
->ep_predictor
== PRED_LOOP_EXIT
1557 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1558 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1563 /* Predict branch probability of BB when BB contains a branch that compares
1564 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1565 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1568 for (int i = 0; i < bound; i++) {
1575 In this loop, we will predict the branch inside the loop to be taken. */
1578 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1579 tree loop_bound_var
,
1580 tree loop_iv_base_var
,
1581 enum tree_code loop_bound_code
,
1582 int loop_bound_step
)
1585 tree compare_var
, compare_base
;
1586 enum tree_code compare_code
;
1587 tree compare_step_var
;
1591 if (predicted_by_loop_heuristics_p (bb
))
1594 stmt
= last_stmt (bb
);
1595 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1597 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1604 /* Find the taken edge. */
1605 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1606 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1609 /* When comparing an IV to a loop invariant, NE is more likely to be
1610 taken while EQ is more likely to be not-taken. */
1611 if (compare_code
== NE_EXPR
)
1613 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1616 else if (compare_code
== EQ_EXPR
)
1618 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1622 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1625 /* If loop bound, base and compare bound are all constants, we can
1626 calculate the probability directly. */
1627 if (tree_fits_shwi_p (loop_bound_var
)
1628 && tree_fits_shwi_p (compare_var
)
1629 && tree_fits_shwi_p (compare_base
))
1632 wi::overflow_type overflow
;
1633 bool overall_overflow
= false;
1634 widest_int compare_count
, tem
;
1636 /* (loop_bound - base) / compare_step */
1637 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1638 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1639 overall_overflow
|= overflow
;
1640 widest_int loop_count
= wi::div_trunc (tem
,
1641 wi::to_widest (compare_step_var
),
1643 overall_overflow
|= overflow
;
1645 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1646 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1648 /* (loop_bound - compare_bound) / compare_step */
1649 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1650 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1651 overall_overflow
|= overflow
;
1652 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1654 overall_overflow
|= overflow
;
1658 /* (compare_bound - base) / compare_step */
1659 tem
= wi::sub (wi::to_widest (compare_var
),
1660 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1661 overall_overflow
|= overflow
;
1662 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1664 overall_overflow
|= overflow
;
1666 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1668 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1670 if (wi::neg_p (compare_count
))
1672 if (wi::neg_p (loop_count
))
1674 if (loop_count
== 0)
1676 else if (wi::cmps (compare_count
, loop_count
) == 1)
1677 probability
= REG_BR_PROB_BASE
;
1680 tem
= compare_count
* REG_BR_PROB_BASE
;
1681 tem
= wi::udiv_trunc (tem
, loop_count
);
1682 probability
= tem
.to_uhwi ();
1685 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1686 if (!overall_overflow
)
1687 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1692 if (expr_coherent_p (loop_bound_var
, compare_var
))
1694 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1695 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1696 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1697 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1698 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1699 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1700 else if (loop_bound_code
== NE_EXPR
)
1702 /* If the loop backedge condition is "(i != bound)", we do
1703 the comparison based on the step of IV:
1704 * step < 0 : backedge condition is like (i > bound)
1705 * step > 0 : backedge condition is like (i < bound) */
1706 gcc_assert (loop_bound_step
!= 0);
1707 if (loop_bound_step
> 0
1708 && (compare_code
== LT_EXPR
1709 || compare_code
== LE_EXPR
))
1710 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1711 else if (loop_bound_step
< 0
1712 && (compare_code
== GT_EXPR
1713 || compare_code
== GE_EXPR
))
1714 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1716 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1719 /* The branch is predicted not-taken if loop_bound_code is
1720 opposite with compare_code. */
1721 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1723 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1726 for (i = s; i < h; i++)
1728 The branch should be predicted taken. */
1729 if (loop_bound_step
> 0
1730 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1731 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1732 else if (loop_bound_step
< 0
1733 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1734 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1736 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1740 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1741 exits are resulted from short-circuit conditions that will generate an
1744 if (foo() || global > 10)
1747 This will be translated into:
1752 if foo() goto BB6 else goto BB5
1754 if global > 10 goto BB6 else goto BB7
1758 iftmp = (PHI 0(BB5), 1(BB6))
1759 if iftmp == 1 goto BB8 else goto BB3
1761 outside of the loop...
1763 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1764 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1765 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1766 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1769 predict_extra_loop_exits (edge exit_edge
)
1772 bool check_value_one
;
1773 gimple
*lhs_def_stmt
;
1775 tree cmp_rhs
, cmp_lhs
;
1779 last
= last_stmt (exit_edge
->src
);
1782 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1786 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1787 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1788 if (!TREE_CONSTANT (cmp_rhs
)
1789 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1791 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1794 /* If check_value_one is true, only the phi_args with value '1' will lead
1795 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1797 check_value_one
= (((integer_onep (cmp_rhs
))
1798 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1799 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1801 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1805 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1809 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1813 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1814 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1816 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1818 if ((check_value_one
^ integer_onep (val
)) == 1)
1820 if (EDGE_COUNT (e
->src
->succs
) != 1)
1822 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1826 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1827 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1832 /* Predict edge probabilities by exploiting loop structure. */
1835 predict_loops (void)
1839 hash_set
<struct loop
*> with_recursion(10);
1841 FOR_EACH_BB_FN (bb
, cfun
)
1843 gimple_stmt_iterator gsi
;
1846 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1847 if (is_gimple_call (gsi_stmt (gsi
))
1848 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1849 && recursive_call_p (current_function_decl
, decl
))
1851 loop
= bb
->loop_father
;
1852 while (loop
&& !with_recursion
.add (loop
))
1853 loop
= loop_outer (loop
);
1857 /* Try to predict out blocks in a loop that are not part of a
1859 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1861 basic_block bb
, *bbs
;
1862 unsigned j
, n_exits
= 0;
1864 struct tree_niter_desc niter_desc
;
1866 struct nb_iter_bound
*nb_iter
;
1867 enum tree_code loop_bound_code
= ERROR_MARK
;
1868 tree loop_bound_step
= NULL
;
1869 tree loop_bound_var
= NULL
;
1870 tree loop_iv_base
= NULL
;
1872 bool recursion
= with_recursion
.contains (loop
);
1874 exits
= get_loop_exit_edges (loop
);
1875 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1876 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1885 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1886 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1887 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1888 && max_loop_iterations_int (loop
) >= 0)
1891 "Loop %d iterates at most %i times.\n", loop
->num
,
1892 (int)max_loop_iterations_int (loop
));
1894 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1895 && likely_max_loop_iterations_int (loop
) >= 0)
1897 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1898 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1901 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1904 HOST_WIDE_INT nitercst
;
1905 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1907 enum br_predictor predictor
;
1910 if (unlikely_executed_edge_p (ex
)
1911 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
1913 /* Loop heuristics do not expect exit conditional to be inside
1914 inner loop. We predict from innermost to outermost loop. */
1915 if (predicted_by_loop_heuristics_p (ex
->src
))
1917 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1918 fprintf (dump_file
, "Skipping exit %i->%i because "
1919 "it is already predicted.\n",
1920 ex
->src
->index
, ex
->dest
->index
);
1923 predict_extra_loop_exits (ex
);
1925 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1926 niter
= niter_desc
.niter
;
1927 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1928 niter
= loop_niter_by_eval (loop
, ex
);
1929 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1930 && TREE_CODE (niter
) == INTEGER_CST
)
1932 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1933 ex
->src
->index
, ex
->dest
->index
,
1935 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1936 fprintf (dump_file
, " times.\n");
1939 if (TREE_CODE (niter
) == INTEGER_CST
)
1941 if (tree_fits_uhwi_p (niter
)
1943 && compare_tree_int (niter
, max
- 1) == -1)
1944 nitercst
= tree_to_uhwi (niter
) + 1;
1947 predictor
= PRED_LOOP_ITERATIONS
;
1949 /* If we have just one exit and we can derive some information about
1950 the number of iterations of the loop from the statements inside
1951 the loop, use it to predict this exit. */
1952 else if (n_exits
== 1
1953 && estimated_stmt_executions (loop
, &nit
))
1955 if (wi::gtu_p (nit
, max
))
1958 nitercst
= nit
.to_shwi ();
1959 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1961 /* If we have likely upper bound, trust it for very small iteration
1962 counts. Such loops would otherwise get mispredicted by standard
1963 LOOP_EXIT heuristics. */
1964 else if (n_exits
== 1
1965 && likely_max_stmt_executions (loop
, &nit
)
1967 RDIV (REG_BR_PROB_BASE
,
1971 ? PRED_LOOP_EXIT_WITH_RECURSION
1972 : PRED_LOOP_EXIT
].hitrate
)))
1974 nitercst
= nit
.to_shwi ();
1975 predictor
= PRED_LOOP_ITERATIONS_MAX
;
1979 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1980 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
1981 ex
->src
->index
, ex
->dest
->index
);
1985 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1986 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
1987 (int)nitercst
, predictor_info
[predictor
].name
);
1988 /* If the prediction for number of iterations is zero, do not
1989 predict the exit edges. */
1993 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
1994 predict_edge (ex
, predictor
, probability
);
1998 /* Find information about loop bound variables. */
1999 for (nb_iter
= loop
->bounds
; nb_iter
;
2000 nb_iter
= nb_iter
->next
)
2002 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
2004 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
2007 if (!stmt
&& last_stmt (loop
->header
)
2008 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
2009 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2011 is_comparison_with_loop_invariant_p (stmt
, loop
,
2017 bbs
= get_loop_body (loop
);
2019 for (j
= 0; j
< loop
->num_nodes
; j
++)
2026 /* Bypass loop heuristics on continue statement. These
2027 statements construct loops via "non-loop" constructs
2028 in the source language and are better to be handled
2030 if (predicted_by_p (bb
, PRED_CONTINUE
))
2032 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2033 fprintf (dump_file
, "BB %i predicted by continue.\n",
2038 /* If we already used more reliable loop exit predictors, do not
2039 bother with PRED_LOOP_EXIT. */
2040 if (!predicted_by_loop_heuristics_p (bb
))
2042 /* For loop with many exits we don't want to predict all exits
2043 with the pretty large probability, because if all exits are
2044 considered in row, the loop would be predicted to iterate
2045 almost never. The code to divide probability by number of
2046 exits is very rough. It should compute the number of exits
2047 taken in each patch through function (not the overall number
2048 of exits that might be a lot higher for loops with wide switch
2049 statements in them) and compute n-th square root.
2051 We limit the minimal probability by 2% to avoid
2052 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2053 as this was causing regression in perl benchmark containing such
2056 int probability
= ((REG_BR_PROB_BASE
2059 ? PRED_LOOP_EXIT_WITH_RECURSION
2060 : PRED_LOOP_EXIT
].hitrate
)
2062 if (probability
< HITRATE (2))
2063 probability
= HITRATE (2);
2064 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2065 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2066 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2068 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2070 "Predicting exit %i->%i with prob %i.\n",
2071 e
->src
->index
, e
->dest
->index
, probability
);
2073 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2074 : PRED_LOOP_EXIT
, probability
);
2078 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2080 tree_to_shwi (loop_bound_step
));
2083 /* In the following code
2088 guess that cond is unlikely. */
2089 if (loop_outer (loop
)->num
)
2091 basic_block bb
= NULL
;
2092 edge preheader_edge
= loop_preheader_edge (loop
);
2094 if (single_pred_p (preheader_edge
->src
)
2095 && single_succ_p (preheader_edge
->src
))
2096 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2098 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2099 /* Pattern match fortran loop preheader:
2100 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2101 _17 = (logical(kind=4)) _16;
2107 Loop guard branch prediction says nothing about duplicated loop
2108 headers produced by fortran frontend and in this case we want
2109 to predict paths leading to this preheader. */
2112 && gimple_code (stmt
) == GIMPLE_COND
2113 && gimple_cond_code (stmt
) == NE_EXPR
2114 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2115 && integer_zerop (gimple_cond_rhs (stmt
)))
2117 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2118 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2119 && gimple_expr_code (call_stmt
) == NOP_EXPR
2120 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2121 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2122 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2123 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2124 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2125 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2126 == PRED_FORTRAN_LOOP_PREHEADER
)
2127 bb
= preheader_edge
->src
;
2131 if (!dominated_by_p (CDI_DOMINATORS
,
2132 loop_outer (loop
)->latch
, loop
->header
))
2133 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2135 ? PRED_LOOP_GUARD_WITH_RECURSION
2142 if (!dominated_by_p (CDI_DOMINATORS
,
2143 loop_outer (loop
)->latch
, bb
))
2144 predict_paths_leading_to (bb
,
2146 ? PRED_LOOP_GUARD_WITH_RECURSION
2153 /* Free basic blocks from get_loop_body. */
2158 /* Attempt to predict probabilities of BB outgoing edges using local
2161 bb_estimate_probability_locally (basic_block bb
)
2163 rtx_insn
*last_insn
= BB_END (bb
);
2166 if (! can_predict_insn_p (last_insn
))
2168 cond
= get_condition (last_insn
, NULL
, false, false);
2172 /* Try "pointer heuristic."
2173 A comparison ptr == 0 is predicted as false.
2174 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2175 if (COMPARISON_P (cond
)
2176 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2177 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2179 if (GET_CODE (cond
) == EQ
)
2180 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2181 else if (GET_CODE (cond
) == NE
)
2182 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2186 /* Try "opcode heuristic."
2187 EQ tests are usually false and NE tests are usually true. Also,
2188 most quantities are positive, so we can make the appropriate guesses
2189 about signed comparisons against zero. */
2190 switch (GET_CODE (cond
))
2193 /* Unconditional branch. */
2194 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2195 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2200 /* Floating point comparisons appears to behave in a very
2201 unpredictable way because of special role of = tests in
2203 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2205 /* Comparisons with 0 are often used for booleans and there is
2206 nothing useful to predict about them. */
2207 else if (XEXP (cond
, 1) == const0_rtx
2208 || XEXP (cond
, 0) == const0_rtx
)
2211 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2216 /* Floating point comparisons appears to behave in a very
2217 unpredictable way because of special role of = tests in
2219 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2221 /* Comparisons with 0 are often used for booleans and there is
2222 nothing useful to predict about them. */
2223 else if (XEXP (cond
, 1) == const0_rtx
2224 || XEXP (cond
, 0) == const0_rtx
)
2227 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2231 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2235 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2240 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2241 || XEXP (cond
, 1) == constm1_rtx
)
2242 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2247 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2248 || XEXP (cond
, 1) == constm1_rtx
)
2249 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2257 /* Set edge->probability for each successor edge of BB. */
2259 guess_outgoing_edge_probabilities (basic_block bb
)
2261 bb_estimate_probability_locally (bb
);
2262 combine_predictions_for_insn (BB_END (bb
), bb
);
2265 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
2267 /* Helper function for expr_expected_value. */
2270 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2271 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
2276 *predictor
= PRED_UNCONDITIONAL
;
2278 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2280 if (TREE_CONSTANT (op0
))
2283 if (code
== IMAGPART_EXPR
)
2285 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2287 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2288 if (is_gimple_call (def
)
2289 && gimple_call_internal_p (def
)
2290 && (gimple_call_internal_fn (def
)
2291 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2293 /* Assume that any given atomic operation has low contention,
2294 and thus the compare-and-swap operation succeeds. */
2296 *predictor
= PRED_COMPARE_AND_SWAP
;
2297 return build_one_cst (TREE_TYPE (op0
));
2302 if (code
!= SSA_NAME
)
2305 def
= SSA_NAME_DEF_STMT (op0
);
2307 /* If we were already here, break the infinite cycle. */
2308 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2311 if (gimple_code (def
) == GIMPLE_PHI
)
2313 /* All the arguments of the PHI node must have the same constant
2315 int i
, n
= gimple_phi_num_args (def
);
2316 tree val
= NULL
, new_val
;
2318 for (i
= 0; i
< n
; i
++)
2320 tree arg
= PHI_ARG_DEF (def
, i
);
2321 enum br_predictor predictor2
;
2323 /* If this PHI has itself as an argument, we cannot
2324 determine the string length of this argument. However,
2325 if we can find an expected constant value for the other
2326 PHI args then we can still be sure that this is
2327 likely a constant. So be optimistic and just
2328 continue with the next argument. */
2329 if (arg
== PHI_RESULT (def
))
2332 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
2334 /* It is difficult to combine value predictors. Simply assume
2335 that later predictor is weaker and take its prediction. */
2336 if (predictor
&& *predictor
< predictor2
)
2337 *predictor
= predictor2
;
2342 else if (!operand_equal_p (val
, new_val
, false))
2347 if (is_gimple_assign (def
))
2349 if (gimple_assign_lhs (def
) != op0
)
2352 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2353 gimple_assign_rhs1 (def
),
2354 gimple_assign_rhs_code (def
),
2355 gimple_assign_rhs2 (def
),
2356 visited
, predictor
);
2359 if (is_gimple_call (def
))
2361 tree decl
= gimple_call_fndecl (def
);
2364 if (gimple_call_internal_p (def
)
2365 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2367 gcc_assert (gimple_call_num_args (def
) == 3);
2368 tree val
= gimple_call_arg (def
, 0);
2369 if (TREE_CONSTANT (val
))
2373 tree val2
= gimple_call_arg (def
, 2);
2374 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2375 && tree_fits_uhwi_p (val2
)
2376 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2377 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2379 return gimple_call_arg (def
, 1);
2383 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2384 switch (DECL_FUNCTION_CODE (decl
))
2386 case BUILT_IN_EXPECT
:
2389 if (gimple_call_num_args (def
) != 2)
2391 val
= gimple_call_arg (def
, 0);
2392 if (TREE_CONSTANT (val
))
2395 *predictor
= PRED_BUILTIN_EXPECT
;
2396 return gimple_call_arg (def
, 1);
2399 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2400 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2401 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2402 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2403 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2404 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2405 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2406 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2407 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2408 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2409 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2410 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2411 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2412 /* Assume that any given atomic operation has low contention,
2413 and thus the compare-and-swap operation succeeds. */
2415 *predictor
= PRED_COMPARE_AND_SWAP
;
2416 return boolean_true_node
;
2425 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2428 enum br_predictor predictor2
;
2429 op0
= expr_expected_value (op0
, visited
, predictor
);
2432 op1
= expr_expected_value (op1
, visited
, &predictor2
);
2433 if (predictor
&& *predictor
< predictor2
)
2434 *predictor
= predictor2
;
2437 res
= fold_build2 (code
, type
, op0
, op1
);
2438 if (TREE_CONSTANT (res
))
2442 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2445 op0
= expr_expected_value (op0
, visited
, predictor
);
2448 res
= fold_build1 (code
, type
, op0
);
2449 if (TREE_CONSTANT (res
))
2456 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2457 The function is used by builtin_expect branch predictor so the evidence
2458 must come from this construct and additional possible constant folding.
2460 We may want to implement more involved value guess (such as value range
2461 propagation based prediction), but such tricks shall go to new
2465 expr_expected_value (tree expr
, bitmap visited
,
2466 enum br_predictor
*predictor
)
2468 enum tree_code code
;
2471 if (TREE_CONSTANT (expr
))
2474 *predictor
= PRED_UNCONDITIONAL
;
2478 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2479 return expr_expected_value_1 (TREE_TYPE (expr
),
2480 op0
, code
, op1
, visited
, predictor
);
2483 /* Predict using opcode of the last statement in basic block. */
2485 tree_predict_by_opcode (basic_block bb
)
2487 gimple
*stmt
= last_stmt (bb
);
2494 enum br_predictor predictor
;
2496 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2498 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2499 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2501 op0
= gimple_cond_lhs (stmt
);
2502 op1
= gimple_cond_rhs (stmt
);
2503 cmp
= gimple_cond_code (stmt
);
2504 type
= TREE_TYPE (op0
);
2505 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2507 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2509 if (predictor
== PRED_BUILTIN_EXPECT
)
2511 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2513 gcc_assert (percent
>= 0 && percent
<= 100);
2514 if (integer_zerop (val
))
2515 percent
= 100 - percent
;
2516 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2519 predict_edge_def (then_edge
, predictor
,
2520 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2522 /* Try "pointer heuristic."
2523 A comparison ptr == 0 is predicted as false.
2524 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2525 if (POINTER_TYPE_P (type
))
2528 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2529 else if (cmp
== NE_EXPR
)
2530 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2534 /* Try "opcode heuristic."
2535 EQ tests are usually false and NE tests are usually true. Also,
2536 most quantities are positive, so we can make the appropriate guesses
2537 about signed comparisons against zero. */
2542 /* Floating point comparisons appears to behave in a very
2543 unpredictable way because of special role of = tests in
2545 if (FLOAT_TYPE_P (type
))
2547 /* Comparisons with 0 are often used for booleans and there is
2548 nothing useful to predict about them. */
2549 else if (integer_zerop (op0
) || integer_zerop (op1
))
2552 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2557 /* Floating point comparisons appears to behave in a very
2558 unpredictable way because of special role of = tests in
2560 if (FLOAT_TYPE_P (type
))
2562 /* Comparisons with 0 are often used for booleans and there is
2563 nothing useful to predict about them. */
2564 else if (integer_zerop (op0
)
2565 || integer_zerop (op1
))
2568 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2572 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2575 case UNORDERED_EXPR
:
2576 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2581 if (integer_zerop (op1
)
2582 || integer_onep (op1
)
2583 || integer_all_onesp (op1
)
2586 || real_minus_onep (op1
))
2587 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2592 if (integer_zerop (op1
)
2593 || integer_onep (op1
)
2594 || integer_all_onesp (op1
)
2597 || real_minus_onep (op1
))
2598 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2606 /* Returns TRUE if the STMT is exit(0) like statement. */
2609 is_exit_with_zero_arg (const gimple
*stmt
)
2611 /* This is not exit, _exit or _Exit. */
2612 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2613 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2614 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2617 /* Argument is an interger zero. */
2618 return integer_zerop (gimple_call_arg (stmt
, 0));
2621 /* Try to guess whether the value of return means error code. */
2623 static enum br_predictor
2624 return_prediction (tree val
, enum prediction
*prediction
)
2628 return PRED_NO_PREDICTION
;
2629 /* Different heuristics for pointers and scalars. */
2630 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2632 /* NULL is usually not returned. */
2633 if (integer_zerop (val
))
2635 *prediction
= NOT_TAKEN
;
2636 return PRED_NULL_RETURN
;
2639 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2641 /* Negative return values are often used to indicate
2643 if (TREE_CODE (val
) == INTEGER_CST
2644 && tree_int_cst_sgn (val
) < 0)
2646 *prediction
= NOT_TAKEN
;
2647 return PRED_NEGATIVE_RETURN
;
2649 /* Constant return values seems to be commonly taken.
2650 Zero/one often represent booleans so exclude them from the
2652 if (TREE_CONSTANT (val
)
2653 && (!integer_zerop (val
) && !integer_onep (val
)))
2655 *prediction
= NOT_TAKEN
;
2656 return PRED_CONST_RETURN
;
2659 return PRED_NO_PREDICTION
;
2662 /* Return zero if phi result could have values other than -1, 0 or 1,
2663 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2664 values are used or likely. */
2667 zero_one_minusone (gphi
*phi
, int limit
)
2669 int phi_num_args
= gimple_phi_num_args (phi
);
2671 for (int i
= 0; i
< phi_num_args
; i
++)
2673 tree t
= PHI_ARG_DEF (phi
, i
);
2674 if (TREE_CODE (t
) != INTEGER_CST
)
2676 wide_int w
= wi::to_wide (t
);
2686 for (int i
= 0; i
< phi_num_args
; i
++)
2688 tree t
= PHI_ARG_DEF (phi
, i
);
2689 if (TREE_CODE (t
) == INTEGER_CST
)
2691 if (TREE_CODE (t
) != SSA_NAME
)
2693 gimple
*g
= SSA_NAME_DEF_STMT (t
);
2694 if (gimple_code (g
) == GIMPLE_PHI
&& limit
> 0)
2695 if (int r
= zero_one_minusone (as_a
<gphi
*> (g
), limit
- 1))
2700 if (!is_gimple_assign (g
))
2702 if (gimple_assign_cast_p (g
))
2704 tree rhs1
= gimple_assign_rhs1 (g
);
2705 if (TREE_CODE (rhs1
) != SSA_NAME
2706 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
2707 || TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2708 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2713 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g
)) != tcc_comparison
)
2720 /* Find the basic block with return expression and look up for possible
2721 return value trying to apply RETURN_PREDICTION heuristics. */
2723 apply_return_prediction (void)
2725 greturn
*return_stmt
= NULL
;
2729 int phi_num_args
, i
;
2730 enum br_predictor pred
;
2731 enum prediction direction
;
2734 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2736 gimple
*last
= last_stmt (e
->src
);
2738 && gimple_code (last
) == GIMPLE_RETURN
)
2740 return_stmt
= as_a
<greturn
*> (last
);
2746 return_val
= gimple_return_retval (return_stmt
);
2749 if (TREE_CODE (return_val
) != SSA_NAME
2750 || !SSA_NAME_DEF_STMT (return_val
)
2751 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2753 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2754 phi_num_args
= gimple_phi_num_args (phi
);
2755 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2757 /* Avoid the case where the function returns -1, 0 and 1 values and
2758 nothing else. Those could be qsort etc. comparison functions
2759 where the negative return isn't less probable than positive.
2760 For this require that the function returns at least -1 or 1
2761 or -1 and a boolean value or comparison result, so that functions
2762 returning just -1 and 0 are treated as if -1 represents error value. */
2763 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val
))
2764 && !TYPE_UNSIGNED (TREE_TYPE (return_val
))
2765 && TYPE_PRECISION (TREE_TYPE (return_val
)) > 1)
2766 if (int r
= zero_one_minusone (phi
, 3))
2767 if ((r
& (1 | 4)) == (1 | 4))
2770 /* Avoid the degenerate case where all return values form the function
2771 belongs to same category (ie they are all positive constants)
2772 so we can hardly say something about them. */
2773 for (i
= 1; i
< phi_num_args
; i
++)
2774 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2776 if (i
!= phi_num_args
)
2777 for (i
= 0; i
< phi_num_args
; i
++)
2779 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2780 if (pred
!= PRED_NO_PREDICTION
)
2781 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2786 /* Look for basic block that contains unlikely to happen events
2787 (such as noreturn calls) and mark all paths leading to execution
2788 of this basic blocks as unlikely. */
2791 tree_bb_level_predictions (void)
2794 bool has_return_edges
= false;
2798 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2799 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2801 has_return_edges
= true;
2805 apply_return_prediction ();
2807 FOR_EACH_BB_FN (bb
, cfun
)
2809 gimple_stmt_iterator gsi
;
2811 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2813 gimple
*stmt
= gsi_stmt (gsi
);
2816 if (is_gimple_call (stmt
))
2818 if (gimple_call_noreturn_p (stmt
)
2820 && !is_exit_with_zero_arg (stmt
))
2821 predict_paths_leading_to (bb
, PRED_NORETURN
,
2823 decl
= gimple_call_fndecl (stmt
);
2825 && lookup_attribute ("cold",
2826 DECL_ATTRIBUTES (decl
)))
2827 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2829 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2830 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2833 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2835 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2836 gimple_predict_outcome (stmt
));
2837 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2838 hints to callers. */
2844 /* Callback for hash_map::traverse, asserts that the pointer map is
2848 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2851 gcc_assert (!value
);
2855 /* Predict branch probabilities and estimate profile for basic block BB.
2856 When LOCAL_ONLY is set do not use any global properties of CFG. */
2859 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
2864 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2866 /* Look for block we are guarding (ie we dominate it,
2867 but it doesn't postdominate us). */
2868 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2870 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2871 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2873 gimple_stmt_iterator bi
;
2875 /* The call heuristic claims that a guarded function call
2876 is improbable. This is because such calls are often used
2877 to signal exceptional situations such as printing error
2879 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2882 gimple
*stmt
= gsi_stmt (bi
);
2883 if (is_gimple_call (stmt
)
2884 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
2885 /* Constant and pure calls are hardly used to signalize
2886 something exceptional. */
2887 && gimple_has_side_effects (stmt
))
2889 if (gimple_call_fndecl (stmt
))
2890 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2891 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
2892 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
2894 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
2900 tree_predict_by_opcode (bb
);
2903 /* Predict branch probabilities and estimate profile of the tree CFG.
2904 This function can be called from the loop optimizers to recompute
2905 the profile information.
2906 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2909 tree_estimate_probability (bool dry_run
)
2913 add_noreturn_fake_exit_edges ();
2914 connect_infinite_loops_to_exit ();
2915 /* We use loop_niter_by_eval, which requires that the loops have
2917 create_preheaders (CP_SIMPLE_PREHEADERS
);
2918 calculate_dominance_info (CDI_POST_DOMINATORS
);
2920 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2921 tree_bb_level_predictions ();
2922 record_loop_exits ();
2924 if (number_of_loops (cfun
) > 1)
2927 FOR_EACH_BB_FN (bb
, cfun
)
2928 tree_estimate_probability_bb (bb
, false);
2930 FOR_EACH_BB_FN (bb
, cfun
)
2931 combine_predictions_for_bb (bb
, dry_run
);
2934 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2936 delete bb_predictions
;
2937 bb_predictions
= NULL
;
2940 estimate_bb_frequencies (false);
2941 free_dominance_info (CDI_POST_DOMINATORS
);
2942 remove_fake_exit_edges ();
2945 /* Set edge->probability for each successor edge of BB. */
2947 tree_guess_outgoing_edge_probabilities (basic_block bb
)
2949 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2950 tree_estimate_probability_bb (bb
, true);
2951 combine_predictions_for_bb (bb
, false);
2953 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2954 delete bb_predictions
;
2955 bb_predictions
= NULL
;
2958 /* Predict edges to successors of CUR whose sources are not postdominated by
2959 BB by PRED and recurse to all postdominators. */
2962 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2963 enum br_predictor pred
,
2964 enum prediction taken
,
2965 bitmap visited
, struct loop
*in_loop
= NULL
)
2971 /* If we exited the loop or CUR is unconditional in the loop, there is
2974 && (!flow_bb_inside_loop_p (in_loop
, cur
)
2975 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
2978 /* We are looking for all edges forming edge cut induced by
2979 set of all blocks postdominated by BB. */
2980 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2981 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2982 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2988 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2989 if (unlikely_executed_edge_p (e
))
2991 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2993 /* See if there is an edge from e->src that is not abnormal
2994 and does not lead to BB and does not exit the loop. */
2995 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2997 && !unlikely_executed_edge_p (e2
)
2998 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
2999 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
3005 /* If there is non-abnormal path leaving e->src, predict edge
3006 using predictor. Otherwise we need to look for paths
3009 The second may lead to infinite loop in the case we are predicitng
3010 regions that are only reachable by abnormal edges. We simply
3011 prevent visiting given BB twice. */
3014 if (!edge_predicted_by_p (e
, pred
, taken
))
3015 predict_edge_def (e
, pred
, taken
);
3017 else if (bitmap_set_bit (visited
, e
->src
->index
))
3018 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
3020 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
3022 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
3023 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
3026 /* Sets branch probabilities according to PREDiction and
3030 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
3031 enum prediction taken
, struct loop
*in_loop
)
3033 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3036 /* Like predict_paths_leading_to but take edge instead of basic block. */
3039 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
3040 enum prediction taken
, struct loop
*in_loop
)
3042 bool has_nonloop_edge
= false;
3046 basic_block bb
= e
->src
;
3047 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
3048 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
3049 && !unlikely_executed_edge_p (e
)
3050 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
3052 has_nonloop_edge
= true;
3055 if (!has_nonloop_edge
)
3057 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3060 predict_edge_def (e
, pred
, taken
);
3063 /* This is used to carry information about basic blocks. It is
3064 attached to the AUX field of the standard CFG block. */
3068 /* Estimated frequency of execution of basic_block. */
3071 /* To keep queue of basic blocks to process. */
3074 /* Number of predecessors we need to visit first. */
3078 /* Similar information for edges. */
3079 struct edge_prob_info
3081 /* In case edge is a loopback edge, the probability edge will be reached
3082 in case header is. Estimated number of iterations of the loop can be
3083 then computed as 1 / (1 - back_edge_prob). */
3084 sreal back_edge_prob
;
3085 /* True if the edge is a loopback edge in the natural loop. */
3086 unsigned int back_edge
:1;
3089 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3091 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3093 /* Helper function for estimate_bb_frequencies.
3094 Propagate the frequencies in blocks marked in
3095 TOVISIT, starting in HEAD. */
3098 propagate_freq (basic_block head
, bitmap tovisit
)
3107 /* For each basic block we need to visit count number of his predecessors
3108 we need to visit first. */
3109 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
3114 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3116 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3118 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3120 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3122 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3124 "Irreducible region hit, ignoring edge to %i->%i\n",
3125 e
->src
->index
, bb
->index
);
3127 BLOCK_INFO (bb
)->npredecessors
= count
;
3128 /* When function never returns, we will never process exit block. */
3129 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3130 bb
->count
= profile_count::zero ();
3133 BLOCK_INFO (head
)->frequency
= 1;
3135 for (bb
= head
; bb
; bb
= nextbb
)
3138 sreal cyclic_probability
= 0;
3139 sreal frequency
= 0;
3141 nextbb
= BLOCK_INFO (bb
)->next
;
3142 BLOCK_INFO (bb
)->next
= NULL
;
3144 /* Compute frequency of basic block. */
3148 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3149 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3150 || (e
->flags
& EDGE_DFS_BACK
));
3152 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3153 if (EDGE_INFO (e
)->back_edge
)
3155 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3157 else if (!(e
->flags
& EDGE_DFS_BACK
))
3159 /* frequency += (e->probability
3160 * BLOCK_INFO (e->src)->frequency /
3161 REG_BR_PROB_BASE); */
3163 /* FIXME: Graphite is producing edges with no profile. Once
3164 this is fixed, drop this. */
3165 sreal tmp
= e
->probability
.initialized_p () ?
3166 e
->probability
.to_reg_br_prob_base () : 0;
3167 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
3168 tmp
*= real_inv_br_prob_base
;
3172 if (cyclic_probability
== 0)
3174 BLOCK_INFO (bb
)->frequency
= frequency
;
3178 if (cyclic_probability
> real_almost_one
)
3179 cyclic_probability
= real_almost_one
;
3181 /* BLOCK_INFO (bb)->frequency = frequency
3182 / (1 - cyclic_probability) */
3184 cyclic_probability
= sreal (1) - cyclic_probability
;
3185 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
3189 bitmap_clear_bit (tovisit
, bb
->index
);
3191 e
= find_edge (bb
, head
);
3194 /* EDGE_INFO (e)->back_edge_prob
3195 = ((e->probability * BLOCK_INFO (bb)->frequency)
3196 / REG_BR_PROB_BASE); */
3198 /* FIXME: Graphite is producing edges with no profile. Once
3199 this is fixed, drop this. */
3200 sreal tmp
= e
->probability
.initialized_p () ?
3201 e
->probability
.to_reg_br_prob_base () : 0;
3202 tmp
*= BLOCK_INFO (bb
)->frequency
;
3203 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
3206 /* Propagate to successor blocks. */
3207 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3208 if (!(e
->flags
& EDGE_DFS_BACK
)
3209 && BLOCK_INFO (e
->dest
)->npredecessors
)
3211 BLOCK_INFO (e
->dest
)->npredecessors
--;
3212 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3217 BLOCK_INFO (last
)->next
= e
->dest
;
3225 /* Estimate frequencies in loops at same nest level. */
3228 estimate_loops_at_level (struct loop
*first_loop
)
3232 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3237 auto_bitmap tovisit
;
3239 estimate_loops_at_level (loop
->inner
);
3241 /* Find current loop back edge and mark it. */
3242 e
= loop_latch_edge (loop
);
3243 EDGE_INFO (e
)->back_edge
= 1;
3245 bbs
= get_loop_body (loop
);
3246 for (i
= 0; i
< loop
->num_nodes
; i
++)
3247 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3249 propagate_freq (loop
->header
, tovisit
);
3253 /* Propagates frequencies through structure of loops. */
3256 estimate_loops (void)
3258 auto_bitmap tovisit
;
3261 /* Start by estimating the frequencies in the loops. */
3262 if (number_of_loops (cfun
) > 1)
3263 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3265 /* Now propagate the frequencies through all the blocks. */
3266 FOR_ALL_BB_FN (bb
, cfun
)
3268 bitmap_set_bit (tovisit
, bb
->index
);
3270 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3273 /* Drop the profile for NODE to guessed, and update its frequency based on
3274 whether it is expected to be hot given the CALL_COUNT. */
3277 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3279 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3280 /* In the case where this was called by another function with a
3281 dropped profile, call_count will be 0. Since there are no
3282 non-zero call counts to this function, we don't know for sure
3283 whether it is hot, and therefore it will be marked normal below. */
3284 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3288 "Dropping 0 profile for %s. %s based on calls.\n",
3290 hot
? "Function is hot" : "Function is normal");
3291 /* We only expect to miss profiles for functions that are reached
3292 via non-zero call edges in cases where the function may have
3293 been linked from another module or library (COMDATs and extern
3294 templates). See the comments below for handle_missing_profiles.
3295 Also, only warn in cases where the missing counts exceed the
3296 number of training runs. In certain cases with an execv followed
3297 by a no-return call the profile for the no-return call is not
3298 dumped and there can be a mismatch. */
3299 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3300 && call_count
> profile_info
->runs
)
3302 if (flag_profile_correction
)
3306 "Missing counts for called function %s\n",
3307 node
->dump_name ());
3310 warning (0, "Missing counts for called function %s",
3311 node
->dump_name ());
3315 if (opt_for_fn (node
->decl
, flag_guess_branch_prob
))
3318 = !ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
.nonzero_p ();
3319 FOR_ALL_BB_FN (bb
, fn
)
3320 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3321 bb
->count
= bb
->count
.guessed_local ();
3322 fn
->cfg
->count_max
= fn
->cfg
->count_max
.guessed_local ();
3326 FOR_ALL_BB_FN (bb
, fn
)
3327 bb
->count
= profile_count::uninitialized ();
3328 fn
->cfg
->count_max
= profile_count::uninitialized ();
3331 struct cgraph_edge
*e
;
3332 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3333 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3334 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3335 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3336 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
;
3338 profile_status_for_fn (fn
)
3339 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3341 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3344 /* In the case of COMDAT routines, multiple object files will contain the same
3345 function and the linker will select one for the binary. In that case
3346 all the other copies from the profile instrument binary will be missing
3347 profile counts. Look for cases where this happened, due to non-zero
3348 call counts going to 0-count functions, and drop the profile to guessed
3349 so that we can use the estimated probabilities and avoid optimizing only
3352 The other case where the profile may be missing is when the routine
3353 is not going to be emitted to the object file, e.g. for "extern template"
3354 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3355 all other cases of non-zero calls to 0-count functions. */
3358 handle_missing_profiles (void)
3360 struct cgraph_node
*node
;
3361 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3362 auto_vec
<struct cgraph_node
*, 64> worklist
;
3364 /* See if 0 count function has non-0 count callers. In this case we
3365 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3366 FOR_EACH_DEFINED_FUNCTION (node
)
3368 struct cgraph_edge
*e
;
3369 profile_count call_count
= profile_count::zero ();
3370 gcov_type max_tp_first_run
= 0;
3371 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3373 if (node
->count
.ipa ().nonzero_p ())
3375 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3376 if (e
->count
.ipa ().initialized_p () && e
->count
.ipa () > 0)
3378 call_count
= call_count
+ e
->count
.ipa ();
3380 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3381 max_tp_first_run
= e
->caller
->tp_first_run
;
3384 /* If time profile is missing, let assign the maximum that comes from
3385 caller functions. */
3386 if (!node
->tp_first_run
&& max_tp_first_run
)
3387 node
->tp_first_run
= max_tp_first_run
+ 1;
3391 && (call_count
.apply_scale (unlikely_count_fraction
, 1)
3392 >= profile_info
->runs
))
3394 drop_profile (node
, call_count
);
3395 worklist
.safe_push (node
);
3399 /* Propagate the profile dropping to other 0-count COMDATs that are
3400 potentially called by COMDATs we already dropped the profile on. */
3401 while (worklist
.length () > 0)
3403 struct cgraph_edge
*e
;
3405 node
= worklist
.pop ();
3406 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3408 struct cgraph_node
*callee
= e
->callee
;
3409 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3411 if (!(e
->count
.ipa () == profile_count::zero ())
3412 && callee
->count
.ipa ().nonzero_p ())
3414 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3416 && profile_status_for_fn (fn
) == PROFILE_READ
)
3418 drop_profile (node
, profile_count::zero ());
3419 worklist
.safe_push (callee
);
3425 /* Convert counts measured by profile driven feedback to frequencies.
3426 Return nonzero iff there was any nonzero execution count. */
3429 update_max_bb_count (void)
3431 profile_count true_count_max
= profile_count::uninitialized ();
3434 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3435 true_count_max
= true_count_max
.max (bb
->count
);
3437 cfun
->cfg
->count_max
= true_count_max
;
3439 return true_count_max
.ipa ().nonzero_p ();
3442 /* Return true if function is likely to be expensive, so there is no point to
3443 optimize performance of prologue, epilogue or do inlining at the expense
3444 of code size growth. THRESHOLD is the limit of number of instructions
3445 function can execute at average to be still considered not expensive. */
3448 expensive_function_p (int threshold
)
3452 /* If profile was scaled in a way entry block has count 0, then the function
3453 is deifnitly taking a lot of time. */
3454 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3457 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN
3458 (cfun
)->count
.apply_scale (threshold
, 1);
3459 profile_count sum
= profile_count::zero ();
3460 FOR_EACH_BB_FN (bb
, cfun
)
3464 if (!bb
->count
.initialized_p ())
3467 fprintf (dump_file
, "Function is considered expensive because"
3468 " count of bb %i is not initialized\n", bb
->index
);
3472 FOR_BB_INSNS (bb
, insn
)
3473 if (active_insn_p (insn
))
3484 /* All basic blocks that are reachable only from unlikely basic blocks are
3488 propagate_unlikely_bbs_forward (void)
3490 auto_vec
<basic_block
, 64> worklist
;
3495 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3497 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3498 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3500 while (worklist
.length () > 0)
3502 bb
= worklist
.pop ();
3503 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3504 if (!(e
->count () == profile_count::zero ())
3505 && !(e
->dest
->count
== profile_count::zero ())
3508 e
->dest
->aux
= (void *)(size_t) 1;
3509 worklist
.safe_push (e
->dest
);
3514 FOR_ALL_BB_FN (bb
, cfun
)
3518 if (!(bb
->count
== profile_count::zero ())
3519 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3521 "Basic block %i is marked unlikely by forward prop\n",
3523 bb
->count
= profile_count::zero ();
3530 /* Determine basic blocks/edges that are known to be unlikely executed and set
3531 their counters to zero.
3532 This is done with first identifying obviously unlikely BBs/edges and then
3533 propagating in both directions. */
3536 determine_unlikely_bbs ()
3539 auto_vec
<basic_block
, 64> worklist
;
3543 FOR_EACH_BB_FN (bb
, cfun
)
3545 if (!(bb
->count
== profile_count::zero ())
3546 && unlikely_executed_bb_p (bb
))
3548 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3549 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3551 bb
->count
= profile_count::zero ();
3554 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3555 if (!(e
->probability
== profile_probability::never ())
3556 && unlikely_executed_edge_p (e
))
3558 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3559 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3560 bb
->index
, e
->dest
->index
);
3561 e
->probability
= profile_probability::never ();
3564 gcc_checking_assert (!bb
->aux
);
3566 propagate_unlikely_bbs_forward ();
3568 auto_vec
<int, 64> nsuccs
;
3569 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
3570 FOR_ALL_BB_FN (bb
, cfun
)
3571 if (!(bb
->count
== profile_count::zero ())
3572 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3574 nsuccs
[bb
->index
] = 0;
3575 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3576 if (!(e
->probability
== profile_probability::never ())
3577 && !(e
->dest
->count
== profile_count::zero ()))
3578 nsuccs
[bb
->index
]++;
3579 if (!nsuccs
[bb
->index
])
3580 worklist
.safe_push (bb
);
3582 while (worklist
.length () > 0)
3584 bb
= worklist
.pop ();
3585 if (bb
->count
== profile_count::zero ())
3587 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3590 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3591 !gsi_end_p (gsi
); gsi_next (&gsi
))
3592 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3593 /* stmt_can_terminate_bb_p special cases noreturns because it
3594 assumes that fake edges are created. We want to know that
3595 noreturn alone does not imply BB to be unlikely. */
3596 || (is_gimple_call (gsi_stmt (gsi
))
3597 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3605 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3607 "Basic block %i is marked unlikely by backward prop\n",
3609 bb
->count
= profile_count::zero ();
3610 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3611 if (!(e
->probability
== profile_probability::never ()))
3613 if (!(e
->src
->count
== profile_count::zero ()))
3615 gcc_checking_assert (nsuccs
[e
->src
->index
] > 0);
3616 nsuccs
[e
->src
->index
]--;
3617 if (!nsuccs
[e
->src
->index
])
3618 worklist
.safe_push (e
->src
);
3622 /* Finally all edges from non-0 regions to 0 are unlikely. */
3623 FOR_ALL_BB_FN (bb
, cfun
)
3624 if (!(bb
->count
== profile_count::zero ()))
3625 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3626 if (!(e
->probability
== profile_probability::never ())
3627 && e
->dest
->count
== profile_count::zero ())
3629 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3630 fprintf (dump_file
, "Edge %i->%i is unlikely because "
3631 "it enters unlikely block\n",
3632 bb
->index
, e
->dest
->index
);
3633 e
->probability
= profile_probability::never ();
3635 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3636 cgraph_node::get (current_function_decl
)->count
= profile_count::zero ();
3639 /* Estimate and propagate basic block frequencies using the given branch
3640 probabilities. If FORCE is true, the frequencies are used to estimate
3641 the counts even when there are already non-zero profile counts. */
3644 estimate_bb_frequencies (bool force
)
3649 determine_unlikely_bbs ();
3651 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3652 || !update_max_bb_count ())
3654 static int real_values_initialized
= 0;
3656 if (!real_values_initialized
)
3658 real_values_initialized
= 1;
3659 real_br_prob_base
= REG_BR_PROB_BASE
;
3660 /* Scaling frequencies up to maximal profile count may result in
3661 frequent overflows especially when inlining loops.
3662 Small scalling results in unnecesary precision loss. Stay in
3663 the half of the (exponential) range. */
3664 real_bb_freq_max
= (uint64_t)1 << (profile_count::n_bits
/ 2);
3665 real_one_half
= sreal (1, -1);
3666 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3667 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3670 mark_dfs_back_edges ();
3672 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3673 profile_probability::always ();
3675 /* Set up block info for each basic block. */
3676 alloc_aux_for_blocks (sizeof (block_info
));
3677 alloc_aux_for_edges (sizeof (edge_prob_info
));
3678 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3683 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3685 /* FIXME: Graphite is producing edges with no profile. Once
3686 this is fixed, drop this. */
3687 if (e
->probability
.initialized_p ())
3688 EDGE_INFO (e
)->back_edge_prob
3689 = e
->probability
.to_reg_br_prob_base ();
3691 EDGE_INFO (e
)->back_edge_prob
= REG_BR_PROB_BASE
/ 2;
3692 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3696 /* First compute frequencies locally for each loop from innermost
3697 to outermost to examine frequencies for back edges. */
3701 FOR_EACH_BB_FN (bb
, cfun
)
3702 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3703 freq_max
= BLOCK_INFO (bb
)->frequency
;
3705 freq_max
= real_bb_freq_max
/ freq_max
;
3708 profile_count ipa_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ();
3709 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3710 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3712 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3713 profile_count count
= profile_count::from_gcov_type (tmp
.to_int ());
3715 /* If we have profile feedback in which this function was never
3716 executed, then preserve this info. */
3717 if (!(bb
->count
== profile_count::zero ()))
3718 bb
->count
= count
.guessed_local ().combine_with_ipa_count (ipa_count
);
3719 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3722 free_aux_for_blocks ();
3723 free_aux_for_edges ();
3725 compute_function_frequency ();
3728 /* Decide whether function is hot, cold or unlikely executed. */
3730 compute_function_frequency (void)
3733 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3735 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3736 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3737 node
->only_called_at_startup
= true;
3738 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3739 node
->only_called_at_exit
= true;
3741 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3743 int flags
= flags_from_decl_or_type (current_function_decl
);
3744 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ()
3745 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3746 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3749 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3750 warn_function_cold (current_function_decl
);
3752 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3754 node
->frequency
= NODE_FREQUENCY_HOT
;
3755 else if (flags
& ECF_NORETURN
)
3756 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3757 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3758 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3759 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3760 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3761 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3765 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3766 warn_function_cold (current_function_decl
);
3767 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3769 FOR_EACH_BB_FN (bb
, cfun
)
3771 if (maybe_hot_bb_p (cfun
, bb
))
3773 node
->frequency
= NODE_FREQUENCY_HOT
;
3776 if (!probably_never_executed_bb_p (cfun
, bb
))
3777 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3781 /* Build PREDICT_EXPR. */
3783 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3785 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3786 build_int_cst (integer_type_node
, predictor
));
3787 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3792 predictor_name (enum br_predictor predictor
)
3794 return predictor_info
[predictor
].name
;
3797 /* Predict branch probabilities and estimate profile of the tree CFG. */
3801 const pass_data pass_data_profile
=
3803 GIMPLE_PASS
, /* type */
3804 "profile_estimate", /* name */
3805 OPTGROUP_NONE
, /* optinfo_flags */
3806 TV_BRANCH_PROB
, /* tv_id */
3807 PROP_cfg
, /* properties_required */
3808 0, /* properties_provided */
3809 0, /* properties_destroyed */
3810 0, /* todo_flags_start */
3811 0, /* todo_flags_finish */
3814 class pass_profile
: public gimple_opt_pass
3817 pass_profile (gcc::context
*ctxt
)
3818 : gimple_opt_pass (pass_data_profile
, ctxt
)
3821 /* opt_pass methods: */
3822 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3823 virtual unsigned int execute (function
*);
3825 }; // class pass_profile
3828 pass_profile::execute (function
*fun
)
3832 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3835 loop_optimizer_init (LOOPS_NORMAL
);
3836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3837 flow_loops_dump (dump_file
, NULL
, 0);
3839 mark_irreducible_loops ();
3841 nb_loops
= number_of_loops (fun
);
3845 tree_estimate_probability (false);
3850 loop_optimizer_finalize ();
3851 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3852 gimple_dump_cfg (dump_file
, dump_flags
);
3853 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3854 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3855 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3858 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3859 if (loop
->header
->count
.initialized_p ())
3860 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
3862 (int)expected_loop_iterations_unbounded (loop
));
3870 make_pass_profile (gcc::context
*ctxt
)
3872 return new pass_profile (ctxt
);
3877 const pass_data pass_data_strip_predict_hints
=
3879 GIMPLE_PASS
, /* type */
3880 "*strip_predict_hints", /* name */
3881 OPTGROUP_NONE
, /* optinfo_flags */
3882 TV_BRANCH_PROB
, /* tv_id */
3883 PROP_cfg
, /* properties_required */
3884 0, /* properties_provided */
3885 0, /* properties_destroyed */
3886 0, /* todo_flags_start */
3887 0, /* todo_flags_finish */
3890 class pass_strip_predict_hints
: public gimple_opt_pass
3893 pass_strip_predict_hints (gcc::context
*ctxt
)
3894 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3897 /* opt_pass methods: */
3898 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3899 virtual unsigned int execute (function
*);
3901 }; // class pass_strip_predict_hints
3903 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3904 we no longer need. */
3906 pass_strip_predict_hints::execute (function
*fun
)
3911 bool changed
= false;
3913 FOR_EACH_BB_FN (bb
, fun
)
3915 gimple_stmt_iterator bi
;
3916 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3918 gimple
*stmt
= gsi_stmt (bi
);
3920 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3922 gsi_remove (&bi
, true);
3926 else if (is_gimple_call (stmt
))
3928 tree fndecl
= gimple_call_fndecl (stmt
);
3931 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3932 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3933 && gimple_call_num_args (stmt
) == 2)
3934 || (gimple_call_internal_p (stmt
)
3935 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3937 var
= gimple_call_lhs (stmt
);
3942 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3943 gsi_replace (&bi
, ass_stmt
, true);
3947 gsi_remove (&bi
, true);
3955 return changed
? TODO_cleanup_cfg
: 0;
3961 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3963 return new pass_strip_predict_hints (ctxt
);
3966 /* Rebuild function frequencies. Passes are in general expected to
3967 maintain profile by hand, however in some cases this is not possible:
3968 for example when inlining several functions with loops freuqencies might run
3969 out of scale and thus needs to be recomputed. */
3972 rebuild_frequencies (void)
3974 timevar_push (TV_REBUILD_FREQUENCIES
);
3976 /* When the max bb count in the function is small, there is a higher
3977 chance that there were truncation errors in the integer scaling
3978 of counts by inlining and other optimizations. This could lead
3979 to incorrect classification of code as being cold when it isn't.
3980 In that case, force the estimation of bb counts/frequencies from the
3981 branch probabilities, rather than computing frequencies from counts,
3982 which may also lead to frequencies incorrectly reduced to 0. There
3983 is less precision in the probabilities, so we only do this for small
3985 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3987 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3988 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3990 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3992 loop_optimizer_init (0);
3993 add_noreturn_fake_exit_edges ();
3994 mark_irreducible_loops ();
3995 connect_infinite_loops_to_exit ();
3996 estimate_bb_frequencies (true);
3997 remove_fake_exit_edges ();
3998 loop_optimizer_finalize ();
4000 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
4001 update_max_bb_count ();
4002 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
4003 && !flag_guess_branch_prob
)
4007 timevar_pop (TV_REBUILD_FREQUENCIES
);
4010 /* Perform a dry run of the branch prediction pass and report comparsion of
4011 the predicted and real profile into the dump file. */
4014 report_predictor_hitrates (void)
4018 loop_optimizer_init (LOOPS_NORMAL
);
4019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4020 flow_loops_dump (dump_file
, NULL
, 0);
4022 mark_irreducible_loops ();
4024 nb_loops
= number_of_loops (cfun
);
4028 tree_estimate_probability (true);
4033 loop_optimizer_finalize ();
4036 /* Force edge E to be cold.
4037 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4038 keep low probability to represent possible error in a guess. This is used
4039 i.e. in case we predict loop to likely iterate given number of times but
4040 we are not 100% sure.
4042 This function locally updates profile without attempt to keep global
4043 consistency which can not be reached in full generality without full profile
4044 rebuild from probabilities alone. Doing so is not necessarily a good idea
4045 because frequencies and counts may be more realistic then probabilities.
4047 In some cases (such as for elimination of early exits during full loop
4048 unrolling) the caller can ensure that profile will get consistent
4052 force_edge_cold (edge e
, bool impossible
)
4054 profile_count count_sum
= profile_count::zero ();
4055 profile_probability prob_sum
= profile_probability::never ();
4058 bool uninitialized_exit
= false;
4060 /* When branch probability guesses are not known, then do nothing. */
4061 if (!impossible
&& !e
->count ().initialized_p ())
4064 profile_probability goal
= (impossible
? profile_probability::never ()
4065 : profile_probability::very_unlikely ());
4067 /* If edge is already improbably or cold, just return. */
4068 if (e
->probability
<= goal
4069 && (!impossible
|| e
->count () == profile_count::zero ()))
4071 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4074 if (e
->flags
& EDGE_FAKE
)
4076 if (e2
->count ().initialized_p ())
4077 count_sum
+= e2
->count ();
4078 if (e2
->probability
.initialized_p ())
4079 prob_sum
+= e2
->probability
;
4081 uninitialized_exit
= true;
4084 /* If we are not guessing profiles but have some other edges out,
4085 just assume the control flow goes elsewhere. */
4086 if (uninitialized_exit
)
4087 e
->probability
= goal
;
4088 /* If there are other edges out of e->src, redistribute probabilitity
4090 else if (prob_sum
> profile_probability::never ())
4092 if (!(e
->probability
< goal
))
4093 e
->probability
= goal
;
4095 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
4097 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4098 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
4099 "probability to other edges.\n",
4100 e
->src
->index
, e
->dest
->index
,
4101 impossible
? "impossible" : "cold");
4102 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4105 e2
->probability
/= prob_comp
;
4107 if (current_ir_type () != IR_GIMPLE
4108 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4109 update_br_prob_note (e
->src
);
4111 /* If all edges out of e->src are unlikely, the basic block itself
4115 if (prob_sum
== profile_probability::never ())
4116 e
->probability
= profile_probability::always ();
4120 e
->probability
= profile_probability::never ();
4121 /* If BB has some edges out that are not impossible, we can not
4122 assume that BB itself is. */
4125 if (current_ir_type () != IR_GIMPLE
4126 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4127 update_br_prob_note (e
->src
);
4128 if (e
->src
->count
== profile_count::zero ())
4130 if (count_sum
== profile_count::zero () && impossible
)
4133 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4135 else if (current_ir_type () == IR_GIMPLE
)
4136 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4137 !gsi_end_p (gsi
); gsi_next (&gsi
))
4139 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4145 /* FIXME: Implement RTL path. */
4150 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4152 "Making bb %i impossible and dropping count to 0.\n",
4154 e
->src
->count
= profile_count::zero ();
4155 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4156 force_edge_cold (e2
, impossible
);
4161 /* If we did not adjusting, the source basic block has no likely edeges
4162 leaving other direction. In that case force that bb cold, too.
4163 This in general is difficult task to do, but handle special case when
4164 BB has only one predecestor. This is common case when we are updating
4165 after loop transforms. */
4166 if (!(prob_sum
> profile_probability::never ())
4167 && count_sum
== profile_count::zero ()
4168 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4169 > (impossible
? 0 : 1))
4171 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4172 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4173 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4174 impossible
? "impossible" : "cold");
4175 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4176 impossible
? 0 : 1);
4178 e
->src
->count
= profile_count::zero ();
4180 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4182 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4184 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4185 && maybe_hot_bb_p (cfun
, e
->src
))
4186 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4187 impossible
? "impossible" : "cold");
4193 namespace selftest
{
4195 /* Test that value range of predictor values defined in predict.def is
4196 within range (50, 100]. */
4198 struct branch_predictor
4204 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4207 test_prediction_value_range ()
4209 branch_predictor predictors
[] = {
4210 #include "predict.def"
4211 { NULL
, PROB_UNINITIALIZED
}
4214 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4216 if (predictors
[i
].probability
== PROB_UNINITIALIZED
)
4219 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4220 ASSERT_TRUE (p
>= 50 && p
<= 100);
4224 #undef DEF_PREDICTOR
4226 /* Run all of the selfests within this file. */
4231 test_prediction_value_range ();
4234 } // namespace selftest
4235 #endif /* CHECKING_P. */