1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2023 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"
52 #include "gimple-iterator.h"
54 #include "tree-ssa-loop-niter.h"
55 #include "tree-ssa-loop.h"
56 #include "tree-scalar-evolution.h"
57 #include "ipa-utils.h"
58 #include "gimple-pretty-print.h"
61 #include "stringpool.h"
64 /* Enum with reasons why a predictor is ignored. */
70 REASON_SINGLE_EDGE_DUPLICATE
,
71 REASON_EDGE_PAIR_DUPLICATE
74 /* String messages for the aforementioned enum. */
76 static const char *reason_messages
[] = {"", " (ignored)",
77 " (single edge duplicate)", " (edge pair duplicate)"};
80 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
81 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
,
82 enum predictor_reason
, edge
);
83 static void predict_paths_leading_to (basic_block
, enum br_predictor
,
85 class loop
*in_loop
= NULL
);
86 static void predict_paths_leading_to_edge (edge
, enum br_predictor
,
88 class loop
*in_loop
= NULL
);
89 static bool can_predict_insn_p (const rtx_insn
*);
90 static HOST_WIDE_INT
get_predictor_value (br_predictor
, HOST_WIDE_INT
);
91 static void determine_unlikely_bbs ();
92 static void estimate_bb_frequencies ();
94 /* Information we hold about each branch predictor.
95 Filled using information from predict.def. */
99 const char *const name
; /* Name used in the debugging dumps. */
100 const int hitrate
; /* Expected hitrate used by
101 predict_insn_def call. */
105 /* Use given predictor without Dempster-Shaffer theory if it matches
106 using first_match heuristics. */
107 #define PRED_FLAG_FIRST_MATCH 1
109 /* Recompute hitrate in percent to our representation. */
111 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
113 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
114 static const struct predictor_info predictor_info
[]= {
115 #include "predict.def"
117 /* Upper bound on predictors. */
122 static gcov_type min_count
= -1;
124 /* Determine the threshold for hot BB counts. */
127 get_hot_bb_threshold ()
131 const int hot_frac
= param_hot_bb_count_fraction
;
132 const gcov_type min_hot_count
134 ? profile_info
->sum_max
/ hot_frac
135 : (gcov_type
)profile_count::max_count
;
136 set_hot_bb_threshold (min_hot_count
);
138 fprintf (dump_file
, "Setting hotness threshold to %" PRId64
".\n",
144 /* Set the threshold for hot BB counts. */
147 set_hot_bb_threshold (gcov_type min
)
152 /* Return TRUE if COUNT is considered to be hot in function FUN. */
155 maybe_hot_count_p (struct function
*fun
, profile_count count
)
157 if (!count
.initialized_p ())
159 if (count
.ipa () == profile_count::zero ())
163 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
164 if (!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
166 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
168 if (node
->frequency
== NODE_FREQUENCY_HOT
)
171 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
173 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
174 && count
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
.apply_scale (2, 3)))
176 if (count
* param_hot_bb_frequency_fraction
177 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
181 /* Code executed at most once is not hot. */
182 if (count
<= MAX (profile_info
? profile_info
->runs
: 1, 1))
184 return (count
>= get_hot_bb_threshold ());
187 /* Return true if basic block BB of function FUN can be CPU intensive
188 and should thus be optimized for maximum performance. */
191 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
193 gcc_checking_assert (fun
);
194 return maybe_hot_count_p (fun
, bb
->count
);
197 /* Return true if edge E can be CPU intensive and should thus be optimized
198 for maximum performance. */
201 maybe_hot_edge_p (edge e
)
203 return maybe_hot_count_p (cfun
, e
->count ());
206 /* Return true if COUNT is considered to be never executed in function FUN
207 or if function FUN is considered so in the static profile. */
210 probably_never_executed (struct function
*fun
, profile_count count
)
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 const int unlikely_frac
= param_unlikely_bb_count_fraction
;
223 if (count
* unlikely_frac
>= 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
))
234 /* Return true if basic block BB of function FUN is probably never executed. */
237 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
239 return probably_never_executed (fun
, bb
->count
);
242 /* Return true if edge E is unlikely executed for obvious reasons. */
245 unlikely_executed_edge_p (edge e
)
247 return (e
->src
->count
== profile_count::zero ()
248 || e
->probability
== profile_probability::never ())
249 || (e
->flags
& (EDGE_EH
| EDGE_FAKE
));
252 /* Return true if edge E of function FUN is probably never executed. */
255 probably_never_executed_edge_p (struct function
*fun
, edge e
)
257 if (unlikely_executed_edge_p (e
))
259 return probably_never_executed (fun
, e
->count ());
262 /* Return true if function FUN should always be optimized for size. */
265 optimize_function_for_size_p (struct function
*fun
)
267 if (!fun
|| !fun
->decl
)
268 return optimize_size
? OPTIMIZE_SIZE_MAX
: OPTIMIZE_SIZE_NO
;
269 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
271 return n
->optimize_for_size_p ();
272 return OPTIMIZE_SIZE_NO
;
275 /* Return true if function FUN 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 function FUN. */
286 function_optimization_type (struct function
*fun
)
288 return (optimize_function_for_speed_p (fun
)
290 : OPTIMIZE_FOR_SIZE
);
293 /* Return TRUE if basic block BB should be optimized for size. */
296 optimize_bb_for_size_p (const_basic_block bb
)
298 enum optimize_size_level ret
= optimize_function_for_size_p (cfun
);
300 if (bb
&& ret
< OPTIMIZE_SIZE_MAX
&& bb
->count
== profile_count::zero ())
301 ret
= OPTIMIZE_SIZE_MAX
;
302 if (bb
&& ret
< OPTIMIZE_SIZE_BALANCED
&& !maybe_hot_bb_p (cfun
, bb
))
303 ret
= OPTIMIZE_SIZE_BALANCED
;
307 /* Return TRUE if basic block BB should be optimized for speed. */
310 optimize_bb_for_speed_p (const_basic_block bb
)
312 return !optimize_bb_for_size_p (bb
);
315 /* Return the optimization type that should be used for basic block BB. */
318 bb_optimization_type (const_basic_block bb
)
320 return (optimize_bb_for_speed_p (bb
)
322 : OPTIMIZE_FOR_SIZE
);
325 /* Return TRUE if edge E should be optimized for size. */
328 optimize_edge_for_size_p (edge e
)
330 enum optimize_size_level ret
= optimize_function_for_size_p (cfun
);
332 if (ret
< OPTIMIZE_SIZE_MAX
&& unlikely_executed_edge_p (e
))
333 ret
= OPTIMIZE_SIZE_MAX
;
334 if (ret
< OPTIMIZE_SIZE_BALANCED
&& !maybe_hot_edge_p (e
))
335 ret
= OPTIMIZE_SIZE_BALANCED
;
339 /* Return TRUE if edge E should be optimized for speed. */
342 optimize_edge_for_speed_p (edge e
)
344 return !optimize_edge_for_size_p (e
);
347 /* Return TRUE if the current function is optimized for size. */
350 optimize_insn_for_size_p (void)
352 enum optimize_size_level ret
= optimize_function_for_size_p (cfun
);
353 if (ret
< OPTIMIZE_SIZE_BALANCED
&& !crtl
->maybe_hot_insn_p
)
354 ret
= OPTIMIZE_SIZE_BALANCED
;
358 /* Return TRUE if the current function is optimized for speed. */
361 optimize_insn_for_speed_p (void)
363 return !optimize_insn_for_size_p ();
366 /* Return the optimization type that should be used for the current
370 insn_optimization_type ()
372 return (optimize_insn_for_speed_p ()
374 : OPTIMIZE_FOR_SIZE
);
377 /* Return TRUE if LOOP should be optimized for size. */
380 optimize_loop_for_size_p (class loop
*loop
)
382 return optimize_bb_for_size_p (loop
->header
);
385 /* Return TRUE if LOOP should be optimized for speed. */
388 optimize_loop_for_speed_p (class loop
*loop
)
390 return optimize_bb_for_speed_p (loop
->header
);
393 /* Return TRUE if nest rooted at LOOP should be optimized for speed. */
396 optimize_loop_nest_for_speed_p (class loop
*loop
)
398 class loop
*l
= loop
;
399 if (optimize_loop_for_speed_p (loop
))
402 while (l
&& l
!= loop
)
404 if (optimize_loop_for_speed_p (l
))
412 while (l
!= loop
&& !l
->next
)
421 /* Return TRUE if nest rooted at LOOP should be optimized for size. */
424 optimize_loop_nest_for_size_p (class loop
*loop
)
426 enum optimize_size_level ret
= optimize_loop_for_size_p (loop
);
427 class loop
*l
= loop
;
430 while (l
&& l
!= loop
)
432 if (ret
== OPTIMIZE_SIZE_NO
)
434 ret
= MIN (optimize_loop_for_size_p (l
), ret
);
441 while (l
!= loop
&& !l
->next
)
450 /* Return true if edge E is likely to be well predictable by branch
454 predictable_edge_p (edge e
)
456 if (!e
->probability
.initialized_p ())
458 if ((e
->probability
.to_reg_br_prob_base ()
459 <= param_predictable_branch_outcome
* REG_BR_PROB_BASE
/ 100)
460 || (REG_BR_PROB_BASE
- e
->probability
.to_reg_br_prob_base ()
461 <= param_predictable_branch_outcome
* REG_BR_PROB_BASE
/ 100))
467 /* Set RTL expansion for BB profile. */
470 rtl_profile_for_bb (basic_block bb
)
472 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
475 /* Set RTL expansion for edge profile. */
478 rtl_profile_for_edge (edge e
)
480 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
483 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
485 default_rtl_profile (void)
487 crtl
->maybe_hot_insn_p
= true;
490 /* Return true if the one of outgoing edges is already predicted by
494 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
497 if (!INSN_P (BB_END (bb
)))
499 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
500 if (REG_NOTE_KIND (note
) == REG_BR_PRED
501 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
506 /* Structure representing predictions in tree level. */
508 struct edge_prediction
{
509 struct edge_prediction
*ep_next
;
511 enum br_predictor ep_predictor
;
515 /* This map contains for a basic block the list of predictions for the
518 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
520 /* Return true if the one of outgoing edges is already predicted by
524 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
526 struct edge_prediction
*i
;
527 edge_prediction
**preds
= bb_predictions
->get (bb
);
532 for (i
= *preds
; i
; i
= i
->ep_next
)
533 if (i
->ep_predictor
== predictor
)
538 /* Return true if the one of outgoing edges is already predicted by
539 PREDICTOR for edge E predicted as TAKEN. */
542 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
544 struct edge_prediction
*i
;
545 basic_block bb
= e
->src
;
546 edge_prediction
**preds
= bb_predictions
->get (bb
);
550 int probability
= predictor_info
[(int) predictor
].hitrate
;
553 probability
= REG_BR_PROB_BASE
- probability
;
555 for (i
= *preds
; i
; i
= i
->ep_next
)
556 if (i
->ep_predictor
== predictor
558 && i
->ep_probability
== probability
)
563 /* Same predicate as above, working on edges. */
565 edge_probability_reliable_p (const_edge e
)
567 return e
->probability
.probably_reliable_p ();
570 /* Same predicate as edge_probability_reliable_p, working on notes. */
572 br_prob_note_reliable_p (const_rtx note
)
574 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
575 return profile_probability::from_reg_br_prob_note
576 (XINT (note
, 0)).probably_reliable_p ();
580 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
582 gcc_assert (any_condjump_p (insn
));
583 if (!flag_guess_branch_prob
)
586 add_reg_note (insn
, REG_BR_PRED
,
587 gen_rtx_CONCAT (VOIDmode
,
588 GEN_INT ((int) predictor
),
589 GEN_INT ((int) probability
)));
592 /* Predict insn by given predictor. */
595 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
596 enum prediction taken
)
598 int probability
= predictor_info
[(int) predictor
].hitrate
;
599 gcc_assert (probability
!= PROB_UNINITIALIZED
);
602 probability
= REG_BR_PROB_BASE
- probability
;
604 predict_insn (insn
, predictor
, probability
);
607 /* Predict edge E with given probability if possible. */
610 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
613 last_insn
= BB_END (e
->src
);
615 /* We can store the branch prediction information only about
616 conditional jumps. */
617 if (!any_condjump_p (last_insn
))
620 /* We always store probability of branching. */
621 if (e
->flags
& EDGE_FALLTHRU
)
622 probability
= REG_BR_PROB_BASE
- probability
;
624 predict_insn (last_insn
, predictor
, probability
);
627 /* Predict edge E with the given PROBABILITY. */
629 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
631 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
632 && EDGE_COUNT (e
->src
->succs
) > 1
633 && flag_guess_branch_prob
636 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
637 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
641 i
->ep_probability
= probability
;
642 i
->ep_predictor
= predictor
;
647 /* Filter edge predictions PREDS by a function FILTER: if FILTER return false
648 the prediction is removed.
649 DATA are passed to the filter function. */
652 filter_predictions (edge_prediction
**preds
,
653 bool (*filter
) (edge_prediction
*, void *), void *data
)
660 struct edge_prediction
**prediction
= preds
;
661 struct edge_prediction
*next
;
665 if ((*filter
) (*prediction
, data
))
666 prediction
= &((*prediction
)->ep_next
);
669 next
= (*prediction
)->ep_next
;
677 /* Filter function predicate that returns true for a edge predicate P
678 if its edge is equal to DATA. */
681 not_equal_edge_p (edge_prediction
*p
, void *data
)
683 return p
->ep_edge
!= (edge
)data
;
686 /* Remove all predictions on given basic block that are attached
689 remove_predictions_associated_with_edge (edge e
)
694 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
695 filter_predictions (preds
, not_equal_edge_p
, e
);
698 /* Clears the list of predictions stored for BB. */
701 clear_bb_predictions (basic_block bb
)
703 edge_prediction
**preds
= bb_predictions
->get (bb
);
704 struct edge_prediction
*pred
, *next
;
709 for (pred
= *preds
; pred
; pred
= next
)
711 next
= pred
->ep_next
;
717 /* Return true when we can store prediction on insn INSN.
718 At the moment we represent predictions only on conditional
719 jumps, not at computed jump or other complicated cases. */
721 can_predict_insn_p (const rtx_insn
*insn
)
723 return (JUMP_P (insn
)
724 && any_condjump_p (insn
)
725 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
728 /* Predict edge E by given predictor if possible. */
731 predict_edge_def (edge e
, enum br_predictor predictor
,
732 enum prediction taken
)
734 int probability
= predictor_info
[(int) predictor
].hitrate
;
737 probability
= REG_BR_PROB_BASE
- probability
;
739 predict_edge (e
, predictor
, probability
);
742 /* Invert all branch predictions or probability notes in the INSN. This needs
743 to be done each time we invert the condition used by the jump. */
746 invert_br_probabilities (rtx insn
)
750 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
751 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
752 XINT (note
, 0) = profile_probability::from_reg_br_prob_note
753 (XINT (note
, 0)).invert ().to_reg_br_prob_note ();
754 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
755 XEXP (XEXP (note
, 0), 1)
756 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
759 /* Dump information about the branch prediction to the output file. */
762 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
763 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
773 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
774 if (! (e
->flags
& EDGE_FALLTHRU
))
777 char edge_info_str
[128];
779 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
780 ep_edge
->dest
->index
);
782 edge_info_str
[0] = '\0';
784 fprintf (file
, " %s heuristics%s%s: %.2f%%",
785 predictor_info
[predictor
].name
,
786 edge_info_str
, reason_messages
[reason
],
787 probability
* 100.0 / REG_BR_PROB_BASE
);
789 if (bb
->count
.initialized_p ())
791 fprintf (file
, " exec ");
792 bb
->count
.dump (file
);
793 if (e
&& e
->count ().initialized_p () && bb
->count
.to_gcov_type ())
795 fprintf (file
, " hit ");
796 e
->count ().dump (file
);
797 fprintf (file
, " (%.1f%%)", e
->count ().to_gcov_type() * 100.0
798 / bb
->count
.to_gcov_type ());
802 fprintf (file
, "\n");
804 /* Print output that be easily read by analyze_brprob.py script. We are
805 interested only in counts that are read from GCDA files. */
806 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
807 && bb
->count
.precise_p ()
808 && reason
== REASON_NONE
)
810 fprintf (file
, ";;heuristics;%s;%" PRId64
";%" PRId64
";%.1f;\n",
811 predictor_info
[predictor
].name
,
812 bb
->count
.to_gcov_type (), e
->count ().to_gcov_type (),
813 probability
* 100.0 / REG_BR_PROB_BASE
);
817 /* Return true if STMT is known to be unlikely executed. */
820 unlikely_executed_stmt_p (gimple
*stmt
)
822 if (!is_gimple_call (stmt
))
824 /* NORETURN attribute alone is not strong enough: exit() may be quite
825 likely executed once during program run. */
826 if (gimple_call_fntype (stmt
)
827 && lookup_attribute ("cold",
828 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
829 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
831 tree decl
= gimple_call_fndecl (stmt
);
834 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
835 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
838 cgraph_node
*n
= cgraph_node::get (decl
);
843 n
= n
->ultimate_alias_target (&avail
);
844 if (avail
< AVAIL_AVAILABLE
)
847 || n
->decl
== current_function_decl
)
849 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
852 /* Return true if BB is unlikely executed. */
855 unlikely_executed_bb_p (basic_block bb
)
857 if (bb
->count
== profile_count::zero ())
859 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
861 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
862 !gsi_end_p (gsi
); gsi_next (&gsi
))
864 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
866 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
872 /* We cannot predict the probabilities of outgoing edges of bb. Set them
873 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
874 even probability for all edges not mentioned in the set. These edges
875 are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES,
876 if we have exactly one likely edge, make the other edges predicted
880 set_even_probabilities (basic_block bb
,
881 hash_set
<edge
> *unlikely_edges
= NULL
,
882 hash_set
<edge_prediction
*> *likely_edges
= NULL
)
884 unsigned nedges
= 0, unlikely_count
= 0;
887 profile_probability all
= profile_probability::always ();
889 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
890 if (e
->probability
.initialized_p ())
891 all
-= e
->probability
;
892 else if (!unlikely_executed_edge_p (e
))
895 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
897 all
-= profile_probability::very_unlikely ();
902 /* Make the distribution even if all edges are unlikely. */
903 unsigned likely_count
= likely_edges
? likely_edges
->elements () : 0;
904 if (unlikely_count
== nedges
)
906 unlikely_edges
= NULL
;
910 /* If we have one likely edge, then use its probability and distribute
911 remaining probabilities as even. */
912 if (likely_count
== 1)
914 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
915 if (e
->probability
.initialized_p ())
917 else if (!unlikely_executed_edge_p (e
))
919 edge_prediction
*prediction
= *likely_edges
->begin ();
920 int p
= prediction
->ep_probability
;
921 profile_probability prob
922 = profile_probability::from_reg_br_prob_base (p
);
924 if (prediction
->ep_edge
== e
)
925 e
->probability
= prob
;
926 else if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
927 e
->probability
= profile_probability::very_unlikely ();
930 profile_probability remainder
= prob
.invert ();
931 remainder
-= (profile_probability::very_unlikely ()
933 int count
= nedges
- unlikely_count
- 1;
934 gcc_assert (count
>= 0);
936 e
->probability
= remainder
/ count
;
940 e
->probability
= profile_probability::never ();
944 /* Make all unlikely edges unlikely and the rest will have even
946 unsigned scale
= nedges
- unlikely_count
;
947 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
948 if (e
->probability
.initialized_p ())
950 else if (!unlikely_executed_edge_p (e
))
952 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
953 e
->probability
= profile_probability::very_unlikely ();
955 e
->probability
= all
/ scale
;
958 e
->probability
= profile_probability::never ();
962 /* Add REG_BR_PROB note to JUMP with PROB. */
965 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
967 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
968 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
971 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
972 note if not already present. Remove now useless REG_BR_PRED notes. */
975 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
980 int best_probability
= PROB_EVEN
;
981 enum br_predictor best_predictor
= END_PREDICTORS
;
982 int combined_probability
= REG_BR_PROB_BASE
/ 2;
984 bool first_match
= false;
987 if (!can_predict_insn_p (insn
))
989 set_even_probabilities (bb
);
993 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
994 pnote
= ®_NOTES (insn
);
996 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
999 /* We implement "first match" heuristics and use probability guessed
1000 by predictor with smallest index. */
1001 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1002 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
1004 enum br_predictor predictor
= ((enum br_predictor
)
1005 INTVAL (XEXP (XEXP (note
, 0), 0)));
1006 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
1009 if (best_predictor
> predictor
1010 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1011 best_probability
= probability
, best_predictor
= predictor
;
1013 d
= (combined_probability
* probability
1014 + (REG_BR_PROB_BASE
- combined_probability
)
1015 * (REG_BR_PROB_BASE
- probability
));
1017 /* Use FP math to avoid overflows of 32bit integers. */
1019 /* If one probability is 0% and one 100%, avoid division by zero. */
1020 combined_probability
= REG_BR_PROB_BASE
/ 2;
1022 combined_probability
= (((double) combined_probability
) * probability
1023 * REG_BR_PROB_BASE
/ d
+ 0.5);
1026 /* Decide which heuristic to use. In case we didn't match anything,
1027 use no_prediction heuristic, in case we did match, use either
1028 first match or Dempster-Shaffer theory depending on the flags. */
1030 if (best_predictor
!= END_PREDICTORS
)
1034 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
1035 combined_probability
, bb
);
1039 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
1040 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
1042 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
1043 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
1047 combined_probability
= best_probability
;
1048 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1052 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
1054 enum br_predictor predictor
= ((enum br_predictor
)
1055 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
1056 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
1058 dump_prediction (dump_file
, predictor
, probability
, bb
,
1059 (!first_match
|| best_predictor
== predictor
)
1060 ? REASON_NONE
: REASON_IGNORED
);
1061 *pnote
= XEXP (*pnote
, 1);
1064 pnote
= &XEXP (*pnote
, 1);
1069 profile_probability p
1070 = profile_probability::from_reg_br_prob_base (combined_probability
);
1071 add_reg_br_prob_note (insn
, p
);
1073 /* Save the prediction into CFG in case we are seeing non-degenerated
1074 conditional jump. */
1075 if (!single_succ_p (bb
))
1077 BRANCH_EDGE (bb
)->probability
= p
;
1078 FALLTHRU_EDGE (bb
)->probability
1079 = BRANCH_EDGE (bb
)->probability
.invert ();
1082 else if (!single_succ_p (bb
))
1084 profile_probability prob
= profile_probability::from_reg_br_prob_note
1085 (XINT (prob_note
, 0));
1087 BRANCH_EDGE (bb
)->probability
= prob
;
1088 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
1091 single_succ_edge (bb
)->probability
= profile_probability::always ();
1094 /* Edge prediction hash traits. */
1096 struct predictor_hash
: pointer_hash
<edge_prediction
>
1099 static inline hashval_t
hash (const edge_prediction
*);
1100 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
1103 /* Calculate hash value of an edge prediction P based on predictor and
1104 normalized probability. */
1107 predictor_hash::hash (const edge_prediction
*p
)
1109 inchash::hash hstate
;
1110 hstate
.add_int (p
->ep_predictor
);
1112 int prob
= p
->ep_probability
;
1113 if (prob
> REG_BR_PROB_BASE
/ 2)
1114 prob
= REG_BR_PROB_BASE
- prob
;
1116 hstate
.add_int (prob
);
1118 return hstate
.end ();
1121 /* Return true whether edge predictions P1 and P2 use the same predictor and
1122 have equal (or opposed probability). */
1125 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1127 return (p1
->ep_predictor
== p2
->ep_predictor
1128 && (p1
->ep_probability
== p2
->ep_probability
1129 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1132 struct predictor_hash_traits
: predictor_hash
,
1133 typed_noop_remove
<edge_prediction
*> {};
1135 /* Return true if edge prediction P is not in DATA hash set. */
1138 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1140 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1141 return !remove
->contains (p
);
1144 /* Prune predictions for a basic block BB. Currently we do following
1147 1) remove duplicate prediction that is guessed with the same probability
1148 (different than 1/2) to both edge
1149 2) remove duplicates for a prediction that belongs with the same probability
1155 prune_predictions_for_bb (basic_block bb
)
1157 edge_prediction
**preds
= bb_predictions
->get (bb
);
1161 hash_table
<predictor_hash_traits
> s (13);
1162 hash_set
<edge_prediction
*> remove
;
1164 /* Step 1: identify predictors that should be removed. */
1165 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1167 edge_prediction
*existing
= s
.find (pred
);
1170 if (pred
->ep_edge
== existing
->ep_edge
1171 && pred
->ep_probability
== existing
->ep_probability
)
1173 /* Remove a duplicate predictor. */
1174 dump_prediction (dump_file
, pred
->ep_predictor
,
1175 pred
->ep_probability
, bb
,
1176 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1180 else if (pred
->ep_edge
!= existing
->ep_edge
1181 && pred
->ep_probability
== existing
->ep_probability
1182 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1184 /* Remove both predictors as they predict the same
1186 dump_prediction (dump_file
, existing
->ep_predictor
,
1187 pred
->ep_probability
, bb
,
1188 REASON_EDGE_PAIR_DUPLICATE
,
1190 dump_prediction (dump_file
, pred
->ep_predictor
,
1191 pred
->ep_probability
, bb
,
1192 REASON_EDGE_PAIR_DUPLICATE
,
1195 remove
.add (existing
);
1200 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1204 /* Step 2: Remove predictors. */
1205 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1209 /* Combine predictions into single probability and store them into CFG.
1210 Remove now useless prediction entries.
1211 If DRY_RUN is set, only produce dumps and do not modify profile. */
1214 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1216 int best_probability
= PROB_EVEN
;
1217 enum br_predictor best_predictor
= END_PREDICTORS
;
1218 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1220 bool first_match
= false;
1222 struct edge_prediction
*pred
;
1224 edge e
, first
= NULL
, second
= NULL
;
1229 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1231 if (!unlikely_executed_edge_p (e
))
1234 if (first
&& !second
)
1239 else if (!e
->probability
.initialized_p ())
1240 e
->probability
= profile_probability::never ();
1241 if (!e
->probability
.initialized_p ())
1243 else if (e
->probability
== profile_probability::never ())
1247 /* When there is no successor or only one choice, prediction is easy.
1249 When we have a basic block with more than 2 successors, the situation
1250 is more complicated as DS theory cannot be used literally.
1251 More precisely, let's assume we predicted edge e1 with probability p1,
1252 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1253 need to find probability of e.g. m1({b2}), which we don't know.
1254 The only approximation is to equally distribute 1-p1 to all edges
1257 According to numbers we've got from SPEC2006 benchark, there's only
1258 one interesting reliable predictor (noreturn call), which can be
1259 handled with a bit easier approach. */
1262 hash_set
<edge
> unlikely_edges (4);
1263 hash_set
<edge_prediction
*> likely_edges (4);
1265 /* Identify all edges that have a probability close to very unlikely.
1266 Doing the approach for very unlikely doesn't worth for doing as
1267 there's no such probability in SPEC2006 benchmark. */
1268 edge_prediction
**preds
= bb_predictions
->get (bb
);
1270 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1272 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
1273 || pred
->ep_predictor
== PRED_COLD_LABEL
)
1274 unlikely_edges
.add (pred
->ep_edge
);
1275 else if (pred
->ep_probability
>= PROB_VERY_LIKELY
1276 || pred
->ep_predictor
== PRED_BUILTIN_EXPECT
1277 || pred
->ep_predictor
== PRED_HOT_LABEL
)
1278 likely_edges
.add (pred
);
1281 /* It can happen that an edge is both in likely_edges and unlikely_edges.
1282 Clear both sets in that situation. */
1283 for (hash_set
<edge_prediction
*>::iterator it
= likely_edges
.begin ();
1284 it
!= likely_edges
.end (); ++it
)
1285 if (unlikely_edges
.contains ((*it
)->ep_edge
))
1287 likely_edges
.empty ();
1288 unlikely_edges
.empty ();
1293 set_even_probabilities (bb
, &unlikely_edges
, &likely_edges
);
1294 clear_bb_predictions (bb
);
1297 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1298 if (unlikely_edges
.is_empty ())
1300 "%i edges in bb %i predicted to even probabilities\n",
1305 "%i edges in bb %i predicted with some unlikely edges\n",
1307 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1308 if (!unlikely_executed_edge_p (e
))
1309 dump_prediction (dump_file
, PRED_COMBINED
,
1310 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1317 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1319 prune_predictions_for_bb (bb
);
1321 edge_prediction
**preds
= bb_predictions
->get (bb
);
1325 /* We implement "first match" heuristics and use probability guessed
1326 by predictor with smallest index. */
1327 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1329 enum br_predictor predictor
= pred
->ep_predictor
;
1330 int probability
= pred
->ep_probability
;
1332 if (pred
->ep_edge
!= first
)
1333 probability
= REG_BR_PROB_BASE
- probability
;
1336 /* First match heuristics would be widly confused if we predicted
1338 if (best_predictor
> predictor
1339 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1341 struct edge_prediction
*pred2
;
1342 int prob
= probability
;
1344 for (pred2
= (struct edge_prediction
*) *preds
;
1345 pred2
; pred2
= pred2
->ep_next
)
1346 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1348 int probability2
= pred2
->ep_probability
;
1350 if (pred2
->ep_edge
!= first
)
1351 probability2
= REG_BR_PROB_BASE
- probability2
;
1353 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1354 (probability2
< REG_BR_PROB_BASE
/ 2))
1357 /* If the same predictor later gave better result, go for it! */
1358 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1359 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1360 prob
= probability2
;
1363 best_probability
= prob
, best_predictor
= predictor
;
1366 d
= (combined_probability
* probability
1367 + (REG_BR_PROB_BASE
- combined_probability
)
1368 * (REG_BR_PROB_BASE
- probability
));
1370 /* Use FP math to avoid overflows of 32bit integers. */
1372 /* If one probability is 0% and one 100%, avoid division by zero. */
1373 combined_probability
= REG_BR_PROB_BASE
/ 2;
1375 combined_probability
= (((double) combined_probability
)
1377 * REG_BR_PROB_BASE
/ d
+ 0.5);
1381 /* Decide which heuristic to use. In case we didn't match anything,
1382 use no_prediction heuristic, in case we did match, use either
1383 first match or Dempster-Shaffer theory depending on the flags. */
1385 if (best_predictor
!= END_PREDICTORS
)
1389 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1393 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1394 !first_match
? REASON_NONE
: REASON_IGNORED
);
1396 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1397 first_match
? REASON_NONE
: REASON_IGNORED
);
1401 combined_probability
= best_probability
;
1402 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1406 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1408 enum br_predictor predictor
= pred
->ep_predictor
;
1409 int probability
= pred
->ep_probability
;
1411 dump_prediction (dump_file
, predictor
, probability
, bb
,
1412 (!first_match
|| best_predictor
== predictor
)
1413 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1416 clear_bb_predictions (bb
);
1419 /* If we have only one successor which is unknown, we can compute missing
1423 profile_probability prob
= profile_probability::always ();
1424 edge missing
= NULL
;
1426 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1427 if (e
->probability
.initialized_p ())
1428 prob
-= e
->probability
;
1429 else if (missing
== NULL
)
1433 missing
->probability
= prob
;
1435 /* If nothing is unknown, we have nothing to update. */
1436 else if (!nunknown
&& nzero
!= (int)EDGE_COUNT (bb
->succs
))
1441 = profile_probability::from_reg_br_prob_base (combined_probability
);
1442 second
->probability
= first
->probability
.invert ();
1446 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1447 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1449 T1 and T2 should be one of the following cases:
1450 1. T1 is SSA_NAME, T2 is NULL
1451 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1452 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1455 strips_small_constant (tree t1
, tree t2
)
1462 else if (TREE_CODE (t1
) == SSA_NAME
)
1464 else if (tree_fits_shwi_p (t1
))
1465 value
= tree_to_shwi (t1
);
1471 else if (tree_fits_shwi_p (t2
))
1472 value
= tree_to_shwi (t2
);
1473 else if (TREE_CODE (t2
) == SSA_NAME
)
1481 if (value
<= 4 && value
>= -4)
1487 /* Return the SSA_NAME in T or T's operands.
1488 Return NULL if SSA_NAME cannot be found. */
1491 get_base_value (tree t
)
1493 if (TREE_CODE (t
) == SSA_NAME
)
1496 if (!BINARY_CLASS_P (t
))
1499 switch (TREE_OPERAND_LENGTH (t
))
1502 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1504 return strips_small_constant (TREE_OPERAND (t
, 0),
1505 TREE_OPERAND (t
, 1));
1511 /* Check the compare STMT in LOOP. If it compares an induction
1512 variable to a loop invariant, return true, and save
1513 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1514 Otherwise return false and set LOOP_INVAIANT to NULL. */
1517 is_comparison_with_loop_invariant_p (gcond
*stmt
, class loop
*loop
,
1518 tree
*loop_invariant
,
1519 enum tree_code
*compare_code
,
1523 tree op0
, op1
, bound
, base
;
1525 enum tree_code code
;
1528 code
= gimple_cond_code (stmt
);
1529 *loop_invariant
= NULL
;
1545 op0
= gimple_cond_lhs (stmt
);
1546 op1
= gimple_cond_rhs (stmt
);
1548 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1549 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1551 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1553 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1555 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1556 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1558 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1559 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1562 if (integer_zerop (iv0
.step
))
1564 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1565 code
= invert_tree_comparison (code
, false);
1568 if (tree_fits_shwi_p (iv1
.step
))
1577 if (tree_fits_shwi_p (iv0
.step
))
1583 if (TREE_CODE (bound
) != INTEGER_CST
)
1584 bound
= get_base_value (bound
);
1587 if (TREE_CODE (base
) != INTEGER_CST
)
1588 base
= get_base_value (base
);
1592 *loop_invariant
= bound
;
1593 *compare_code
= code
;
1595 *loop_iv_base
= base
;
1599 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1602 expr_coherent_p (tree t1
, tree t2
)
1605 tree ssa_name_1
= NULL
;
1606 tree ssa_name_2
= NULL
;
1608 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1609 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1614 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1616 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1619 /* Check to see if t1 is expressed/defined with t2. */
1620 stmt
= SSA_NAME_DEF_STMT (t1
);
1621 gcc_assert (stmt
!= NULL
);
1622 if (is_gimple_assign (stmt
))
1624 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1625 if (ssa_name_1
&& ssa_name_1
== t2
)
1629 /* Check to see if t2 is expressed/defined with t1. */
1630 stmt
= SSA_NAME_DEF_STMT (t2
);
1631 gcc_assert (stmt
!= NULL
);
1632 if (is_gimple_assign (stmt
))
1634 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1635 if (ssa_name_2
&& ssa_name_2
== t1
)
1639 /* Compare if t1 and t2's def_stmts are identical. */
1640 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1646 /* Return true if E is predicted by one of loop heuristics. */
1649 predicted_by_loop_heuristics_p (basic_block bb
)
1651 struct edge_prediction
*i
;
1652 edge_prediction
**preds
= bb_predictions
->get (bb
);
1657 for (i
= *preds
; i
; i
= i
->ep_next
)
1658 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1659 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1660 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1661 || i
->ep_predictor
== PRED_LOOP_EXIT
1662 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1663 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1668 /* Predict branch probability of BB when BB contains a branch that compares
1669 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1670 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1673 for (int i = 0; i < bound; i++) {
1680 In this loop, we will predict the branch inside the loop to be taken. */
1683 predict_iv_comparison (class loop
*loop
, basic_block bb
,
1684 tree loop_bound_var
,
1685 tree loop_iv_base_var
,
1686 enum tree_code loop_bound_code
,
1687 int loop_bound_step
)
1689 tree compare_var
, compare_base
;
1690 enum tree_code compare_code
;
1691 tree compare_step_var
;
1695 if (predicted_by_loop_heuristics_p (bb
))
1698 gcond
*stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (bb
));
1701 if (!is_comparison_with_loop_invariant_p (stmt
,
1708 /* Find the taken edge. */
1709 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1710 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1713 /* When comparing an IV to a loop invariant, NE is more likely to be
1714 taken while EQ is more likely to be not-taken. */
1715 if (compare_code
== NE_EXPR
)
1717 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1720 else if (compare_code
== EQ_EXPR
)
1722 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1726 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1729 /* If loop bound, base and compare bound are all constants, we can
1730 calculate the probability directly. */
1731 if (tree_fits_shwi_p (loop_bound_var
)
1732 && tree_fits_shwi_p (compare_var
)
1733 && tree_fits_shwi_p (compare_base
))
1736 wi::overflow_type overflow
;
1737 bool overall_overflow
= false;
1738 widest_int compare_count
, tem
;
1740 /* (loop_bound - base) / compare_step */
1741 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1742 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1743 overall_overflow
|= overflow
;
1744 widest_int loop_count
= wi::div_trunc (tem
,
1745 wi::to_widest (compare_step_var
),
1747 overall_overflow
|= overflow
;
1749 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1750 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1752 /* (loop_bound - compare_bound) / compare_step */
1753 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1754 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1755 overall_overflow
|= overflow
;
1756 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1758 overall_overflow
|= overflow
;
1762 /* (compare_bound - base) / compare_step */
1763 tem
= wi::sub (wi::to_widest (compare_var
),
1764 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1765 overall_overflow
|= overflow
;
1766 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1768 overall_overflow
|= overflow
;
1770 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1772 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1774 if (wi::neg_p (compare_count
))
1776 if (wi::neg_p (loop_count
))
1778 if (loop_count
== 0)
1780 else if (wi::cmps (compare_count
, loop_count
) == 1)
1781 probability
= REG_BR_PROB_BASE
;
1784 tem
= compare_count
* REG_BR_PROB_BASE
;
1785 tem
= wi::udiv_trunc (tem
, loop_count
);
1786 probability
= tem
.to_uhwi ();
1789 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1790 if (!overall_overflow
)
1791 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1796 if (expr_coherent_p (loop_bound_var
, compare_var
))
1798 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1799 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1800 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1801 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1802 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1803 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1804 else if (loop_bound_code
== NE_EXPR
)
1806 /* If the loop backedge condition is "(i != bound)", we do
1807 the comparison based on the step of IV:
1808 * step < 0 : backedge condition is like (i > bound)
1809 * step > 0 : backedge condition is like (i < bound) */
1810 gcc_assert (loop_bound_step
!= 0);
1811 if (loop_bound_step
> 0
1812 && (compare_code
== LT_EXPR
1813 || compare_code
== LE_EXPR
))
1814 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1815 else if (loop_bound_step
< 0
1816 && (compare_code
== GT_EXPR
1817 || compare_code
== GE_EXPR
))
1818 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1820 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1823 /* The branch is predicted not-taken if loop_bound_code is
1824 opposite with compare_code. */
1825 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1827 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1830 for (i = s; i < h; i++)
1832 The branch should be predicted taken. */
1833 if (loop_bound_step
> 0
1834 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1835 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1836 else if (loop_bound_step
< 0
1837 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1838 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1840 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1844 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1845 exits are resulted from short-circuit conditions that will generate an
1848 if (foo() || global > 10)
1851 This will be translated into:
1856 if foo() goto BB6 else goto BB5
1858 if global > 10 goto BB6 else goto BB7
1862 iftmp = (PHI 0(BB5), 1(BB6))
1863 if iftmp == 1 goto BB8 else goto BB3
1865 outside of the loop...
1867 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1868 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1869 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1870 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1873 predict_extra_loop_exits (class loop
*loop
, edge exit_edge
)
1876 bool check_value_one
;
1877 gimple
*lhs_def_stmt
;
1879 tree cmp_rhs
, cmp_lhs
;
1881 gcond
*cmp_stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (exit_edge
->src
));
1885 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1886 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1887 if (!TREE_CONSTANT (cmp_rhs
)
1888 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1890 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1893 /* If check_value_one is true, only the phi_args with value '1' will lead
1894 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1896 check_value_one
= (((integer_onep (cmp_rhs
))
1897 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1898 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1900 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1904 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1908 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1912 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1913 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1915 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1917 if ((check_value_one
^ integer_onep (val
)) == 1)
1919 if (EDGE_COUNT (e
->src
->succs
) != 1)
1921 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
,
1926 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1927 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
,
1933 /* Predict edge probabilities by exploiting loop structure. */
1936 predict_loops (void)
1939 hash_set
<class loop
*> with_recursion(10);
1941 FOR_EACH_BB_FN (bb
, cfun
)
1943 gimple_stmt_iterator gsi
;
1946 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1947 if (is_gimple_call (gsi_stmt (gsi
))
1948 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1949 && recursive_call_p (current_function_decl
, decl
))
1951 class loop
*loop
= bb
->loop_father
;
1952 while (loop
&& !with_recursion
.add (loop
))
1953 loop
= loop_outer (loop
);
1957 /* Try to predict out blocks in a loop that are not part of a
1959 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
1961 basic_block bb
, *bbs
;
1962 unsigned j
, n_exits
= 0;
1963 class tree_niter_desc niter_desc
;
1965 class nb_iter_bound
*nb_iter
;
1966 enum tree_code loop_bound_code
= ERROR_MARK
;
1967 tree loop_bound_step
= NULL
;
1968 tree loop_bound_var
= NULL
;
1969 tree loop_iv_base
= NULL
;
1971 bool recursion
= with_recursion
.contains (loop
);
1973 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
1974 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1975 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1980 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1981 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1982 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1983 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1984 && max_loop_iterations_int (loop
) >= 0)
1987 "Loop %d iterates at most %i times.\n", loop
->num
,
1988 (int)max_loop_iterations_int (loop
));
1990 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1991 && likely_max_loop_iterations_int (loop
) >= 0)
1993 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1994 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1997 FOR_EACH_VEC_ELT (exits
, j
, ex
)
2000 HOST_WIDE_INT nitercst
;
2001 int max
= param_max_predicted_iterations
;
2003 enum br_predictor predictor
;
2006 if (unlikely_executed_edge_p (ex
)
2007 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
2009 /* Loop heuristics do not expect exit conditional to be inside
2010 inner loop. We predict from innermost to outermost loop. */
2011 if (predicted_by_loop_heuristics_p (ex
->src
))
2013 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2014 fprintf (dump_file
, "Skipping exit %i->%i because "
2015 "it is already predicted.\n",
2016 ex
->src
->index
, ex
->dest
->index
);
2019 predict_extra_loop_exits (loop
, ex
);
2021 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
2022 niter
= niter_desc
.niter
;
2023 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
2024 niter
= loop_niter_by_eval (loop
, ex
);
2025 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
2026 && TREE_CODE (niter
) == INTEGER_CST
)
2028 fprintf (dump_file
, "Exit %i->%i %d iterates ",
2029 ex
->src
->index
, ex
->dest
->index
,
2031 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
2032 fprintf (dump_file
, " times.\n");
2035 if (TREE_CODE (niter
) == INTEGER_CST
)
2037 if (tree_fits_uhwi_p (niter
)
2039 && compare_tree_int (niter
, max
- 1) == -1)
2040 nitercst
= tree_to_uhwi (niter
) + 1;
2043 predictor
= PRED_LOOP_ITERATIONS
;
2045 /* If we have just one exit and we can derive some information about
2046 the number of iterations of the loop from the statements inside
2047 the loop, use it to predict this exit. */
2048 else if (n_exits
== 1
2049 && estimated_stmt_executions (loop
, &nit
))
2051 if (wi::gtu_p (nit
, max
))
2054 nitercst
= nit
.to_shwi ();
2055 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
2057 /* If we have likely upper bound, trust it for very small iteration
2058 counts. Such loops would otherwise get mispredicted by standard
2059 LOOP_EXIT heuristics. */
2060 else if (n_exits
== 1
2061 && likely_max_stmt_executions (loop
, &nit
)
2063 RDIV (REG_BR_PROB_BASE
,
2067 ? PRED_LOOP_EXIT_WITH_RECURSION
2068 : PRED_LOOP_EXIT
].hitrate
)))
2070 nitercst
= nit
.to_shwi ();
2071 predictor
= PRED_LOOP_ITERATIONS_MAX
;
2075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2076 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
2077 ex
->src
->index
, ex
->dest
->index
);
2081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2082 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
2083 (int)nitercst
, predictor_info
[predictor
].name
);
2084 /* If the prediction for number of iterations is zero, do not
2085 predict the exit edges. */
2089 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
2090 predict_edge (ex
, predictor
, probability
);
2093 /* Find information about loop bound variables. */
2094 for (nb_iter
= loop
->bounds
; nb_iter
;
2095 nb_iter
= nb_iter
->next
)
2097 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
2099 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
2103 stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (loop
->header
));
2105 is_comparison_with_loop_invariant_p (stmt
, loop
,
2111 bbs
= get_loop_body (loop
);
2113 for (j
= 0; j
< loop
->num_nodes
; j
++)
2120 /* Bypass loop heuristics on continue statement. These
2121 statements construct loops via "non-loop" constructs
2122 in the source language and are better to be handled
2124 if (predicted_by_p (bb
, PRED_CONTINUE
))
2126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2127 fprintf (dump_file
, "BB %i predicted by continue.\n",
2132 /* If we already used more reliable loop exit predictors, do not
2133 bother with PRED_LOOP_EXIT. */
2134 if (!predicted_by_loop_heuristics_p (bb
))
2136 /* For loop with many exits we don't want to predict all exits
2137 with the pretty large probability, because if all exits are
2138 considered in row, the loop would be predicted to iterate
2139 almost never. The code to divide probability by number of
2140 exits is very rough. It should compute the number of exits
2141 taken in each patch through function (not the overall number
2142 of exits that might be a lot higher for loops with wide switch
2143 statements in them) and compute n-th square root.
2145 We limit the minimal probability by 2% to avoid
2146 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2147 as this was causing regression in perl benchmark containing such
2150 int probability
= ((REG_BR_PROB_BASE
2153 ? PRED_LOOP_EXIT_WITH_RECURSION
2154 : PRED_LOOP_EXIT
].hitrate
)
2156 if (probability
< HITRATE (2))
2157 probability
= HITRATE (2);
2158 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2159 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2160 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2164 "Predicting exit %i->%i with prob %i.\n",
2165 e
->src
->index
, e
->dest
->index
, probability
);
2167 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2168 : PRED_LOOP_EXIT
, probability
);
2172 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2174 tree_to_shwi (loop_bound_step
));
2177 /* In the following code
2182 guess that cond is unlikely. */
2183 if (loop_outer (loop
)->num
)
2185 basic_block bb
= NULL
;
2186 edge preheader_edge
= loop_preheader_edge (loop
);
2188 if (single_pred_p (preheader_edge
->src
)
2189 && single_succ_p (preheader_edge
->src
))
2190 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2192 /* Pattern match fortran loop preheader:
2193 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2194 _17 = (logical(kind=4)) _16;
2200 Loop guard branch prediction says nothing about duplicated loop
2201 headers produced by fortran frontend and in this case we want
2202 to predict paths leading to this preheader. */
2205 = safe_dyn_cast
<gcond
*> (*gsi_last_bb (preheader_edge
->src
));
2207 && gimple_cond_code (stmt
) == NE_EXPR
2208 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2209 && integer_zerop (gimple_cond_rhs (stmt
)))
2211 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2212 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2213 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt
))
2214 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2215 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2216 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2217 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2218 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2219 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2220 == PRED_FORTRAN_LOOP_PREHEADER
)
2221 bb
= preheader_edge
->src
;
2225 if (!dominated_by_p (CDI_DOMINATORS
,
2226 loop_outer (loop
)->latch
, loop
->header
))
2227 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2229 ? PRED_LOOP_GUARD_WITH_RECURSION
2236 if (!dominated_by_p (CDI_DOMINATORS
,
2237 loop_outer (loop
)->latch
, bb
))
2238 predict_paths_leading_to (bb
,
2240 ? PRED_LOOP_GUARD_WITH_RECURSION
2247 /* Free basic blocks from get_loop_body. */
2252 /* Attempt to predict probabilities of BB outgoing edges using local
2255 bb_estimate_probability_locally (basic_block bb
)
2257 rtx_insn
*last_insn
= BB_END (bb
);
2260 if (! can_predict_insn_p (last_insn
))
2262 cond
= get_condition (last_insn
, NULL
, false, false);
2266 /* Try "pointer heuristic."
2267 A comparison ptr == 0 is predicted as false.
2268 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2269 if (COMPARISON_P (cond
)
2270 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2271 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2273 if (GET_CODE (cond
) == EQ
)
2274 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2275 else if (GET_CODE (cond
) == NE
)
2276 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2280 /* Try "opcode heuristic."
2281 EQ tests are usually false and NE tests are usually true. Also,
2282 most quantities are positive, so we can make the appropriate guesses
2283 about signed comparisons against zero. */
2284 switch (GET_CODE (cond
))
2287 /* Unconditional branch. */
2288 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2289 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2294 /* Floating point comparisons appears to behave in a very
2295 unpredictable way because of special role of = tests in
2297 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2299 /* Comparisons with 0 are often used for booleans and there is
2300 nothing useful to predict about them. */
2301 else if (XEXP (cond
, 1) == const0_rtx
2302 || XEXP (cond
, 0) == const0_rtx
)
2305 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2310 /* Floating point comparisons appears to behave in a very
2311 unpredictable way because of special role of = tests in
2313 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2315 /* Comparisons with 0 are often used for booleans and there is
2316 nothing useful to predict about them. */
2317 else if (XEXP (cond
, 1) == const0_rtx
2318 || XEXP (cond
, 0) == const0_rtx
)
2321 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2325 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2329 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2334 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2335 || XEXP (cond
, 1) == constm1_rtx
)
2336 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2341 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2342 || XEXP (cond
, 1) == constm1_rtx
)
2343 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2351 /* Set edge->probability for each successor edge of BB. */
2353 guess_outgoing_edge_probabilities (basic_block bb
)
2355 bb_estimate_probability_locally (bb
);
2356 combine_predictions_for_insn (BB_END (bb
), bb
);
2359 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
,
2360 HOST_WIDE_INT
*probability
);
2362 /* Helper function for expr_expected_value. */
2365 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2366 tree op1
, bitmap visited
, enum br_predictor
*predictor
,
2367 HOST_WIDE_INT
*probability
)
2371 /* Reset returned probability value. */
2373 *predictor
= PRED_UNCONDITIONAL
;
2375 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2377 if (TREE_CONSTANT (op0
))
2380 if (code
== IMAGPART_EXPR
)
2382 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2384 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2385 if (is_gimple_call (def
)
2386 && gimple_call_internal_p (def
)
2387 && (gimple_call_internal_fn (def
)
2388 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2390 /* Assume that any given atomic operation has low contention,
2391 and thus the compare-and-swap operation succeeds. */
2392 *predictor
= PRED_COMPARE_AND_SWAP
;
2393 return build_one_cst (TREE_TYPE (op0
));
2398 if (code
!= SSA_NAME
)
2401 def
= SSA_NAME_DEF_STMT (op0
);
2403 /* If we were already here, break the infinite cycle. */
2404 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2407 if (gimple_code (def
) == GIMPLE_PHI
)
2409 /* All the arguments of the PHI node must have the same constant
2411 int i
, n
= gimple_phi_num_args (def
);
2412 tree val
= NULL
, new_val
;
2414 for (i
= 0; i
< n
; i
++)
2416 tree arg
= PHI_ARG_DEF (def
, i
);
2417 enum br_predictor predictor2
;
2419 /* If this PHI has itself as an argument, we cannot
2420 determine the string length of this argument. However,
2421 if we can find an expected constant value for the other
2422 PHI args then we can still be sure that this is
2423 likely a constant. So be optimistic and just
2424 continue with the next argument. */
2425 if (arg
== PHI_RESULT (def
))
2428 HOST_WIDE_INT probability2
;
2429 new_val
= expr_expected_value (arg
, visited
, &predictor2
,
2432 /* It is difficult to combine value predictors. Simply assume
2433 that later predictor is weaker and take its prediction. */
2434 if (*predictor
< predictor2
)
2436 *predictor
= predictor2
;
2437 *probability
= probability2
;
2443 else if (!operand_equal_p (val
, new_val
, false))
2448 if (is_gimple_assign (def
))
2450 if (gimple_assign_lhs (def
) != op0
)
2453 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2454 gimple_assign_rhs1 (def
),
2455 gimple_assign_rhs_code (def
),
2456 gimple_assign_rhs2 (def
),
2457 visited
, predictor
, probability
);
2460 if (is_gimple_call (def
))
2462 tree decl
= gimple_call_fndecl (def
);
2465 if (gimple_call_internal_p (def
)
2466 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2468 gcc_assert (gimple_call_num_args (def
) == 3);
2469 tree val
= gimple_call_arg (def
, 0);
2470 if (TREE_CONSTANT (val
))
2472 tree val2
= gimple_call_arg (def
, 2);
2473 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2474 && tree_fits_uhwi_p (val2
)
2475 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2476 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2477 if (*predictor
== PRED_BUILTIN_EXPECT
)
2479 = HITRATE (param_builtin_expect_probability
);
2480 return gimple_call_arg (def
, 1);
2485 if (DECL_IS_MALLOC (decl
) || DECL_IS_OPERATOR_NEW_P (decl
))
2488 *predictor
= PRED_MALLOC_NONNULL
;
2489 /* FIXME: This is wrong and we need to convert the logic
2490 to value ranges. This makes predictor to assume that
2491 malloc always returns (size_t)1 which is not the same
2492 as returning non-NULL. */
2493 return fold_convert (type
, boolean_true_node
);
2496 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2497 switch (DECL_FUNCTION_CODE (decl
))
2499 case BUILT_IN_EXPECT
:
2502 if (gimple_call_num_args (def
) != 2)
2504 val
= gimple_call_arg (def
, 0);
2505 if (TREE_CONSTANT (val
))
2507 *predictor
= PRED_BUILTIN_EXPECT
;
2509 = HITRATE (param_builtin_expect_probability
);
2510 return gimple_call_arg (def
, 1);
2512 case BUILT_IN_EXPECT_WITH_PROBABILITY
:
2515 if (gimple_call_num_args (def
) != 3)
2517 val
= gimple_call_arg (def
, 0);
2518 if (TREE_CONSTANT (val
))
2520 /* Compute final probability as:
2521 probability * REG_BR_PROB_BASE. */
2522 tree prob
= gimple_call_arg (def
, 2);
2523 tree t
= TREE_TYPE (prob
);
2524 tree base
= build_int_cst (integer_type_node
,
2526 base
= build_real_from_int_cst (t
, base
);
2527 tree r
= fold_build2_initializer_loc (UNKNOWN_LOCATION
,
2528 MULT_EXPR
, t
, prob
, base
);
2529 if (TREE_CODE (r
) != REAL_CST
)
2531 error_at (gimple_location (def
),
2532 "probability %qE must be "
2533 "constant floating-point expression", prob
);
2537 = real_to_integer (TREE_REAL_CST_PTR (r
));
2538 if (probi
>= 0 && probi
<= REG_BR_PROB_BASE
)
2540 *predictor
= PRED_BUILTIN_EXPECT_WITH_PROBABILITY
;
2541 *probability
= probi
;
2544 error_at (gimple_location (def
),
2545 "probability %qE is outside "
2546 "the range [0.0, 1.0]", prob
);
2548 return gimple_call_arg (def
, 1);
2551 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2552 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2553 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2554 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2555 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2556 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2557 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2558 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2559 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2560 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2561 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2562 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2563 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2564 /* Assume that any given atomic operation has low contention,
2565 and thus the compare-and-swap operation succeeds. */
2566 *predictor
= PRED_COMPARE_AND_SWAP
;
2567 return boolean_true_node
;
2568 case BUILT_IN_REALLOC
:
2569 case BUILT_IN_GOMP_REALLOC
:
2571 *predictor
= PRED_MALLOC_NONNULL
;
2572 /* FIXME: This is wrong and we need to convert the logic
2574 return fold_convert (type
, boolean_true_node
);
2583 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2588 if (TREE_CODE (op0
) != INTEGER_CST
)
2590 /* See if expected value of op0 is good enough to determine the result. */
2591 nop0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2593 && (res
= fold_build2 (code
, type
, nop0
, op1
)) != NULL
2594 && TREE_CODE (res
) == INTEGER_CST
)
2599 enum br_predictor predictor2
;
2600 HOST_WIDE_INT probability2
;
2601 if (TREE_CODE (op1
) != INTEGER_CST
)
2603 /* See if expected value of op1 is good enough to determine the result. */
2604 nop1
= expr_expected_value (op1
, visited
, &predictor2
, &probability2
);
2606 && (res
= fold_build2 (code
, type
, op0
, nop1
)) != NULL
2607 && TREE_CODE (res
) == INTEGER_CST
)
2609 *predictor
= predictor2
;
2610 *probability
= probability2
;
2616 if (nop0
== op0
|| nop1
== op1
)
2618 /* Finally see if we have two known values. */
2619 res
= fold_build2 (code
, type
, nop0
, nop1
);
2620 if (TREE_CODE (res
) == INTEGER_CST
2621 && TREE_CODE (nop0
) == INTEGER_CST
2622 && TREE_CODE (nop1
) == INTEGER_CST
)
2624 /* Combine binary predictions. */
2625 if (*probability
!= -1 || probability2
!= -1)
2627 HOST_WIDE_INT p1
= get_predictor_value (*predictor
, *probability
);
2628 HOST_WIDE_INT p2
= get_predictor_value (predictor2
, probability2
);
2629 *probability
= RDIV (p1
* p2
, REG_BR_PROB_BASE
);
2632 if (predictor2
< *predictor
)
2633 *predictor
= predictor2
;
2639 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2642 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2645 res
= fold_build1 (code
, type
, op0
);
2646 if (TREE_CONSTANT (res
))
2653 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2654 The function is used by builtin_expect branch predictor so the evidence
2655 must come from this construct and additional possible constant folding.
2657 We may want to implement more involved value guess (such as value range
2658 propagation based prediction), but such tricks shall go to new
2662 expr_expected_value (tree expr
, bitmap visited
,
2663 enum br_predictor
*predictor
,
2664 HOST_WIDE_INT
*probability
)
2666 enum tree_code code
;
2669 if (TREE_CONSTANT (expr
))
2671 *predictor
= PRED_UNCONDITIONAL
;
2676 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2677 return expr_expected_value_1 (TREE_TYPE (expr
),
2678 op0
, code
, op1
, visited
, predictor
,
2683 /* Return probability of a PREDICTOR. If the predictor has variable
2684 probability return passed PROBABILITY. */
2686 static HOST_WIDE_INT
2687 get_predictor_value (br_predictor predictor
, HOST_WIDE_INT probability
)
2691 case PRED_BUILTIN_EXPECT
:
2692 case PRED_BUILTIN_EXPECT_WITH_PROBABILITY
:
2693 gcc_assert (probability
!= -1);
2696 gcc_assert (probability
== -1);
2697 return predictor_info
[(int) predictor
].hitrate
;
2701 /* Predict using opcode of the last statement in basic block. */
2703 tree_predict_by_opcode (basic_block bb
)
2711 enum br_predictor predictor
;
2712 HOST_WIDE_INT probability
;
2714 gimple
*stmt
= *gsi_last_bb (bb
);
2718 if (gswitch
*sw
= dyn_cast
<gswitch
*> (stmt
))
2720 tree index
= gimple_switch_index (sw
);
2721 tree val
= expr_expected_value (index
, auto_bitmap (),
2722 &predictor
, &probability
);
2723 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2725 edge e
= find_taken_edge_switch_expr (sw
, val
);
2726 if (predictor
== PRED_BUILTIN_EXPECT
)
2728 int percent
= param_builtin_expect_probability
;
2729 gcc_assert (percent
>= 0 && percent
<= 100);
2730 predict_edge (e
, PRED_BUILTIN_EXPECT
,
2734 predict_edge_def (e
, predictor
, TAKEN
);
2738 if (gimple_code (stmt
) != GIMPLE_COND
)
2740 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2741 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2743 op0
= gimple_cond_lhs (stmt
);
2744 op1
= gimple_cond_rhs (stmt
);
2745 cmp
= gimple_cond_code (stmt
);
2746 type
= TREE_TYPE (op0
);
2747 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2748 &predictor
, &probability
);
2749 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2751 HOST_WIDE_INT prob
= get_predictor_value (predictor
, probability
);
2752 if (integer_zerop (val
))
2753 prob
= REG_BR_PROB_BASE
- prob
;
2754 predict_edge (then_edge
, predictor
, prob
);
2756 /* Try "pointer heuristic."
2757 A comparison ptr == 0 is predicted as false.
2758 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2759 if (POINTER_TYPE_P (type
))
2762 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2763 else if (cmp
== NE_EXPR
)
2764 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2768 /* Try "opcode heuristic."
2769 EQ tests are usually false and NE tests are usually true. Also,
2770 most quantities are positive, so we can make the appropriate guesses
2771 about signed comparisons against zero. */
2776 /* Floating point comparisons appears to behave in a very
2777 unpredictable way because of special role of = tests in
2779 if (FLOAT_TYPE_P (type
))
2781 /* Comparisons with 0 are often used for booleans and there is
2782 nothing useful to predict about them. */
2783 else if (integer_zerop (op0
) || integer_zerop (op1
))
2786 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2791 /* Floating point comparisons appears to behave in a very
2792 unpredictable way because of special role of = tests in
2794 if (FLOAT_TYPE_P (type
))
2796 /* Comparisons with 0 are often used for booleans and there is
2797 nothing useful to predict about them. */
2798 else if (integer_zerop (op0
)
2799 || integer_zerop (op1
))
2802 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2806 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2809 case UNORDERED_EXPR
:
2810 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2815 if (integer_zerop (op1
)
2816 || integer_onep (op1
)
2817 || integer_all_onesp (op1
)
2820 || real_minus_onep (op1
))
2821 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2826 if (integer_zerop (op1
)
2827 || integer_onep (op1
)
2828 || integer_all_onesp (op1
)
2831 || real_minus_onep (op1
))
2832 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2840 /* Returns TRUE if the STMT is exit(0) like statement. */
2843 is_exit_with_zero_arg (const gimple
*stmt
)
2845 /* This is not exit, _exit or _Exit. */
2846 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2847 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2848 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2851 /* Argument is an interger zero. */
2852 return integer_zerop (gimple_call_arg (stmt
, 0));
2855 /* Try to guess whether the value of return means error code. */
2857 static enum br_predictor
2858 return_prediction (tree val
, enum prediction
*prediction
)
2862 return PRED_NO_PREDICTION
;
2863 /* Different heuristics for pointers and scalars. */
2864 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2866 /* NULL is usually not returned. */
2867 if (integer_zerop (val
))
2869 *prediction
= NOT_TAKEN
;
2870 return PRED_NULL_RETURN
;
2873 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2875 /* Negative return values are often used to indicate
2877 if (TREE_CODE (val
) == INTEGER_CST
2878 && tree_int_cst_sgn (val
) < 0)
2880 *prediction
= NOT_TAKEN
;
2881 return PRED_NEGATIVE_RETURN
;
2883 /* Constant return values seems to be commonly taken.
2884 Zero/one often represent booleans so exclude them from the
2886 if (TREE_CONSTANT (val
)
2887 && (!integer_zerop (val
) && !integer_onep (val
)))
2889 *prediction
= NOT_TAKEN
;
2890 return PRED_CONST_RETURN
;
2893 return PRED_NO_PREDICTION
;
2896 /* Return zero if phi result could have values other than -1, 0 or 1,
2897 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2898 values are used or likely. */
2901 zero_one_minusone (gphi
*phi
, int limit
)
2903 int phi_num_args
= gimple_phi_num_args (phi
);
2905 for (int i
= 0; i
< phi_num_args
; i
++)
2907 tree t
= PHI_ARG_DEF (phi
, i
);
2908 if (TREE_CODE (t
) != INTEGER_CST
)
2910 wide_int w
= wi::to_wide (t
);
2920 for (int i
= 0; i
< phi_num_args
; i
++)
2922 tree t
= PHI_ARG_DEF (phi
, i
);
2923 if (TREE_CODE (t
) == INTEGER_CST
)
2925 if (TREE_CODE (t
) != SSA_NAME
)
2927 gimple
*g
= SSA_NAME_DEF_STMT (t
);
2928 if (gimple_code (g
) == GIMPLE_PHI
&& limit
> 0)
2929 if (int r
= zero_one_minusone (as_a
<gphi
*> (g
), limit
- 1))
2934 if (!is_gimple_assign (g
))
2936 if (gimple_assign_cast_p (g
))
2938 tree rhs1
= gimple_assign_rhs1 (g
);
2939 if (TREE_CODE (rhs1
) != SSA_NAME
2940 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
2941 || TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2942 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2947 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g
)) != tcc_comparison
)
2954 /* Find the basic block with return expression and look up for possible
2955 return value trying to apply RETURN_PREDICTION heuristics. */
2957 apply_return_prediction (void)
2959 greturn
*return_stmt
= NULL
;
2963 int phi_num_args
, i
;
2964 enum br_predictor pred
;
2965 enum prediction direction
;
2968 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2970 if (greturn
*last
= safe_dyn_cast
<greturn
*> (*gsi_last_bb (e
->src
)))
2978 return_val
= gimple_return_retval (return_stmt
);
2981 if (TREE_CODE (return_val
) != SSA_NAME
2982 || !SSA_NAME_DEF_STMT (return_val
)
2983 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2985 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2986 phi_num_args
= gimple_phi_num_args (phi
);
2987 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2989 /* Avoid the case where the function returns -1, 0 and 1 values and
2990 nothing else. Those could be qsort etc. comparison functions
2991 where the negative return isn't less probable than positive.
2992 For this require that the function returns at least -1 or 1
2993 or -1 and a boolean value or comparison result, so that functions
2994 returning just -1 and 0 are treated as if -1 represents error value. */
2995 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val
))
2996 && !TYPE_UNSIGNED (TREE_TYPE (return_val
))
2997 && TYPE_PRECISION (TREE_TYPE (return_val
)) > 1)
2998 if (int r
= zero_one_minusone (phi
, 3))
2999 if ((r
& (1 | 4)) == (1 | 4))
3002 /* Avoid the degenerate case where all return values form the function
3003 belongs to same category (ie they are all positive constants)
3004 so we can hardly say something about them. */
3005 for (i
= 1; i
< phi_num_args
; i
++)
3006 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
3008 if (i
!= phi_num_args
)
3009 for (i
= 0; i
< phi_num_args
; i
++)
3011 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
3012 if (pred
!= PRED_NO_PREDICTION
)
3013 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
3018 /* Look for basic block that contains unlikely to happen events
3019 (such as noreturn calls) and mark all paths leading to execution
3020 of this basic blocks as unlikely. */
3023 tree_bb_level_predictions (void)
3026 bool has_return_edges
= false;
3030 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
3031 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
3033 has_return_edges
= true;
3037 apply_return_prediction ();
3039 FOR_EACH_BB_FN (bb
, cfun
)
3041 gimple_stmt_iterator gsi
;
3043 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3045 gimple
*stmt
= gsi_stmt (gsi
);
3048 if (is_gimple_call (stmt
))
3050 if (gimple_call_noreturn_p (stmt
)
3052 && !is_exit_with_zero_arg (stmt
))
3053 predict_paths_leading_to (bb
, PRED_NORETURN
,
3055 decl
= gimple_call_fndecl (stmt
);
3057 && lookup_attribute ("cold",
3058 DECL_ATTRIBUTES (decl
)))
3059 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
3061 if (decl
&& recursive_call_p (current_function_decl
, decl
))
3062 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
3065 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3067 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
3068 gimple_predict_outcome (stmt
));
3069 /* Keep GIMPLE_PREDICT around so early inlining will propagate
3070 hints to callers. */
3076 /* Callback for hash_map::traverse, asserts that the pointer map is
3080 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
3083 gcc_assert (!value
);
3087 /* Predict branch probabilities and estimate profile for basic block BB.
3088 When LOCAL_ONLY is set do not use any global properties of CFG. */
3091 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
3096 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3098 /* Look for block we are guarding (ie we dominate it,
3099 but it doesn't postdominate us). */
3100 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
3102 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
3103 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
3105 gimple_stmt_iterator bi
;
3107 /* The call heuristic claims that a guarded function call
3108 is improbable. This is because such calls are often used
3109 to signal exceptional situations such as printing error
3111 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
3114 gimple
*stmt
= gsi_stmt (bi
);
3115 if (is_gimple_call (stmt
)
3116 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
3117 /* Constant and pure calls are hardly used to signalize
3118 something exceptional. */
3119 && gimple_has_side_effects (stmt
))
3121 if (gimple_call_fndecl (stmt
))
3122 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
3123 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
3124 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
3126 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
3132 tree_predict_by_opcode (bb
);
3135 /* Predict branch probabilities and estimate profile of the tree CFG.
3136 This function can be called from the loop optimizers to recompute
3137 the profile information.
3138 If DRY_RUN is set, do not modify CFG and only produce dump files. */
3141 tree_estimate_probability (bool dry_run
)
3145 connect_infinite_loops_to_exit ();
3146 /* We use loop_niter_by_eval, which requires that the loops have
3148 create_preheaders (CP_SIMPLE_PREHEADERS
);
3149 calculate_dominance_info (CDI_POST_DOMINATORS
);
3150 /* Decide which edges are known to be unlikely. This improves later
3151 branch prediction. */
3152 determine_unlikely_bbs ();
3154 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3155 tree_bb_level_predictions ();
3156 record_loop_exits ();
3158 if (number_of_loops (cfun
) > 1)
3161 FOR_EACH_BB_FN (bb
, cfun
)
3162 tree_estimate_probability_bb (bb
, false);
3164 FOR_EACH_BB_FN (bb
, cfun
)
3165 combine_predictions_for_bb (bb
, dry_run
);
3168 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3170 delete bb_predictions
;
3171 bb_predictions
= NULL
;
3174 && profile_status_for_fn (cfun
) != PROFILE_READ
)
3175 estimate_bb_frequencies ();
3176 free_dominance_info (CDI_POST_DOMINATORS
);
3177 remove_fake_exit_edges ();
3180 /* Set edge->probability for each successor edge of BB. */
3182 tree_guess_outgoing_edge_probabilities (basic_block bb
)
3184 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3185 tree_estimate_probability_bb (bb
, true);
3186 combine_predictions_for_bb (bb
, false);
3188 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3189 delete bb_predictions
;
3190 bb_predictions
= NULL
;
3193 /* Filter function predicate that returns true for a edge predicate P
3194 if its edge is equal to DATA. */
3197 not_loop_guard_equal_edge_p (edge_prediction
*p
, void *data
)
3199 return p
->ep_edge
!= (edge
)data
|| p
->ep_predictor
!= PRED_LOOP_GUARD
;
3202 /* Predict edge E with PRED unless it is already predicted by some predictor
3203 considered equivalent. */
3206 maybe_predict_edge (edge e
, enum br_predictor pred
, enum prediction taken
)
3208 if (edge_predicted_by_p (e
, pred
, taken
))
3210 if (pred
== PRED_LOOP_GUARD
3211 && edge_predicted_by_p (e
, PRED_LOOP_GUARD_WITH_RECURSION
, taken
))
3213 /* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD. */
3214 if (pred
== PRED_LOOP_GUARD_WITH_RECURSION
)
3216 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
3218 filter_predictions (preds
, not_loop_guard_equal_edge_p
, e
);
3220 predict_edge_def (e
, pred
, taken
);
3222 /* Predict edges to successors of CUR whose sources are not postdominated by
3223 BB by PRED and recurse to all postdominators. */
3226 predict_paths_for_bb (basic_block cur
, basic_block bb
,
3227 enum br_predictor pred
,
3228 enum prediction taken
,
3229 bitmap visited
, class loop
*in_loop
= NULL
)
3235 /* If we exited the loop or CUR is unconditional in the loop, there is
3238 && (!flow_bb_inside_loop_p (in_loop
, cur
)
3239 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
3242 /* We are looking for all edges forming edge cut induced by
3243 set of all blocks postdominated by BB. */
3244 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
3245 if (e
->src
->index
>= NUM_FIXED_BLOCKS
3246 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
3252 /* Ignore fake edges and eh, we predict them as not taken anyway. */
3253 if (unlikely_executed_edge_p (e
))
3255 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
3257 /* See if there is an edge from e->src that is not abnormal
3258 and does not lead to BB and does not exit the loop. */
3259 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
3261 && !unlikely_executed_edge_p (e2
)
3262 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
3263 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
3269 /* If there is non-abnormal path leaving e->src, predict edge
3270 using predictor. Otherwise we need to look for paths
3273 The second may lead to infinite loop in the case we are predicitng
3274 regions that are only reachable by abnormal edges. We simply
3275 prevent visiting given BB twice. */
3277 maybe_predict_edge (e
, pred
, taken
);
3278 else if (bitmap_set_bit (visited
, e
->src
->index
))
3279 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
3281 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
3283 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
3284 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
3287 /* Sets branch probabilities according to PREDiction and
3291 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
3292 enum prediction taken
, class loop
*in_loop
)
3294 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3297 /* Like predict_paths_leading_to but take edge instead of basic block. */
3300 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
3301 enum prediction taken
, class loop
*in_loop
)
3303 bool has_nonloop_edge
= false;
3307 basic_block bb
= e
->src
;
3308 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
3309 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
3310 && !unlikely_executed_edge_p (e2
)
3311 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
3313 has_nonloop_edge
= true;
3317 if (!has_nonloop_edge
)
3318 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3320 maybe_predict_edge (e
, pred
, taken
);
3323 /* This is used to carry information about basic blocks. It is
3324 attached to the AUX field of the standard CFG block. */
3329 /* Estimated frequency of execution of basic_block. */
3332 /* To keep queue of basic blocks to process. */
3335 /* Number of predecessors we need to visit first. */
3339 /* Similar information for edges. */
3340 class edge_prob_info
3343 /* In case edge is a loopback edge, the probability edge will be reached
3344 in case header is. Estimated number of iterations of the loop can be
3345 then computed as 1 / (1 - back_edge_prob). */
3346 sreal back_edge_prob
;
3347 /* True if the edge is a loopback edge in the natural loop. */
3348 unsigned int back_edge
:1;
3351 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3353 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3355 /* Helper function for estimate_bb_frequencies.
3356 Propagate the frequencies in blocks marked in
3357 TOVISIT, starting in HEAD. */
3360 propagate_freq (basic_block head
, bitmap tovisit
,
3361 sreal max_cyclic_prob
)
3370 /* For each basic block we need to visit count number of his predecessors
3371 we need to visit first. */
3372 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
3377 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3379 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3381 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3383 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3385 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3387 "Irreducible region hit, ignoring edge to %i->%i\n",
3388 e
->src
->index
, bb
->index
);
3390 BLOCK_INFO (bb
)->npredecessors
= count
;
3391 /* When function never returns, we will never process exit block. */
3392 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3393 bb
->count
= profile_count::zero ();
3396 BLOCK_INFO (head
)->frequency
= 1;
3398 for (bb
= head
; bb
; bb
= nextbb
)
3401 sreal cyclic_probability
= 0;
3402 sreal frequency
= 0;
3404 nextbb
= BLOCK_INFO (bb
)->next
;
3405 BLOCK_INFO (bb
)->next
= NULL
;
3407 /* Compute frequency of basic block. */
3411 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3412 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3413 || (e
->flags
& EDGE_DFS_BACK
));
3415 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3416 if (EDGE_INFO (e
)->back_edge
)
3417 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3418 else if (!(e
->flags
& EDGE_DFS_BACK
))
3420 /* FIXME: Graphite is producing edges with no profile. Once
3421 this is fixed, drop this. */
3422 sreal tmp
= e
->probability
.initialized_p () ?
3423 e
->probability
.to_sreal () : 0;
3424 frequency
+= tmp
* BLOCK_INFO (e
->src
)->frequency
;
3427 if (cyclic_probability
== 0)
3429 BLOCK_INFO (bb
)->frequency
= frequency
;
3433 if (cyclic_probability
> max_cyclic_prob
)
3437 "cyclic probability of bb %i is %f (capped to %f)"
3438 "; turning freq %f",
3439 bb
->index
, cyclic_probability
.to_double (),
3440 max_cyclic_prob
.to_double (),
3441 frequency
.to_double ());
3443 cyclic_probability
= max_cyclic_prob
;
3447 "cyclic probability of bb %i is %f; turning freq %f",
3448 bb
->index
, cyclic_probability
.to_double (),
3449 frequency
.to_double ());
3451 BLOCK_INFO (bb
)->frequency
= frequency
3452 / (sreal (1) - cyclic_probability
);
3454 fprintf (dump_file
, " to %f\n",
3455 BLOCK_INFO (bb
)->frequency
.to_double ());
3459 bitmap_clear_bit (tovisit
, bb
->index
);
3461 e
= find_edge (bb
, head
);
3464 /* FIXME: Graphite is producing edges with no profile. Once
3465 this is fixed, drop this. */
3466 sreal tmp
= e
->probability
.initialized_p () ?
3467 e
->probability
.to_sreal () : 0;
3468 EDGE_INFO (e
)->back_edge_prob
= tmp
* BLOCK_INFO (bb
)->frequency
;
3471 /* Propagate to successor blocks. */
3472 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3473 if (!(e
->flags
& EDGE_DFS_BACK
)
3474 && BLOCK_INFO (e
->dest
)->npredecessors
)
3476 BLOCK_INFO (e
->dest
)->npredecessors
--;
3477 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3482 BLOCK_INFO (last
)->next
= e
->dest
;
3490 /* Estimate frequencies in loops at same nest level. */
3493 estimate_loops_at_level (class loop
*first_loop
, sreal max_cyclic_prob
)
3497 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3502 auto_bitmap tovisit
;
3504 estimate_loops_at_level (loop
->inner
, max_cyclic_prob
);
3506 /* Find current loop back edge and mark it. */
3507 e
= loop_latch_edge (loop
);
3508 EDGE_INFO (e
)->back_edge
= 1;
3510 bbs
= get_loop_body (loop
);
3511 for (i
= 0; i
< loop
->num_nodes
; i
++)
3512 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3514 propagate_freq (loop
->header
, tovisit
, max_cyclic_prob
);
3518 /* Propagates frequencies through structure of loops. */
3521 estimate_loops (void)
3523 auto_bitmap tovisit
;
3525 sreal max_cyclic_prob
= (sreal
)1
3526 - (sreal
)1 / (param_max_predicted_iterations
+ 1);
3528 /* Start by estimating the frequencies in the loops. */
3529 if (number_of_loops (cfun
) > 1)
3530 estimate_loops_at_level (current_loops
->tree_root
->inner
, max_cyclic_prob
);
3532 /* Now propagate the frequencies through all the blocks. */
3533 FOR_ALL_BB_FN (bb
, cfun
)
3535 bitmap_set_bit (tovisit
, bb
->index
);
3537 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
, max_cyclic_prob
);
3540 /* Drop the profile for NODE to guessed, and update its frequency based on
3541 whether it is expected to be hot given the CALL_COUNT. */
3544 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3546 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3547 /* In the case where this was called by another function with a
3548 dropped profile, call_count will be 0. Since there are no
3549 non-zero call counts to this function, we don't know for sure
3550 whether it is hot, and therefore it will be marked normal below. */
3551 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3555 "Dropping 0 profile for %s. %s based on calls.\n",
3557 hot
? "Function is hot" : "Function is normal");
3558 /* We only expect to miss profiles for functions that are reached
3559 via non-zero call edges in cases where the function may have
3560 been linked from another module or library (COMDATs and extern
3561 templates). See the comments below for handle_missing_profiles.
3562 Also, only warn in cases where the missing counts exceed the
3563 number of training runs. In certain cases with an execv followed
3564 by a no-return call the profile for the no-return call is not
3565 dumped and there can be a mismatch. */
3566 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3567 && call_count
> profile_info
->runs
)
3569 if (flag_profile_correction
)
3573 "Missing counts for called function %s\n",
3574 node
->dump_name ());
3577 warning (0, "Missing counts for called function %s",
3578 node
->dump_name ());
3582 if (opt_for_fn (node
->decl
, flag_guess_branch_prob
))
3585 = !ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
.nonzero_p ();
3586 FOR_ALL_BB_FN (bb
, fn
)
3587 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3588 bb
->count
= bb
->count
.guessed_local ();
3589 fn
->cfg
->count_max
= fn
->cfg
->count_max
.guessed_local ();
3593 FOR_ALL_BB_FN (bb
, fn
)
3594 bb
->count
= profile_count::uninitialized ();
3595 fn
->cfg
->count_max
= profile_count::uninitialized ();
3598 struct cgraph_edge
*e
;
3599 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3600 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3601 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3602 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3603 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
;
3605 profile_status_for_fn (fn
)
3606 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3608 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3611 /* In the case of COMDAT routines, multiple object files will contain the same
3612 function and the linker will select one for the binary. In that case
3613 all the other copies from the profile instrument binary will be missing
3614 profile counts. Look for cases where this happened, due to non-zero
3615 call counts going to 0-count functions, and drop the profile to guessed
3616 so that we can use the estimated probabilities and avoid optimizing only
3619 The other case where the profile may be missing is when the routine
3620 is not going to be emitted to the object file, e.g. for "extern template"
3621 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3622 all other cases of non-zero calls to 0-count functions. */
3625 handle_missing_profiles (void)
3627 const int unlikely_frac
= param_unlikely_bb_count_fraction
;
3628 struct cgraph_node
*node
;
3629 auto_vec
<struct cgraph_node
*, 64> worklist
;
3631 /* See if 0 count function has non-0 count callers. In this case we
3632 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3633 FOR_EACH_DEFINED_FUNCTION (node
)
3635 struct cgraph_edge
*e
;
3636 profile_count call_count
= profile_count::zero ();
3637 gcov_type max_tp_first_run
= 0;
3638 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3640 if (node
->count
.ipa ().nonzero_p ())
3642 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3643 if (e
->count
.ipa ().initialized_p () && e
->count
.ipa () > 0)
3645 call_count
= call_count
+ e
->count
.ipa ();
3647 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3648 max_tp_first_run
= e
->caller
->tp_first_run
;
3651 /* If time profile is missing, let assign the maximum that comes from
3652 caller functions. */
3653 if (!node
->tp_first_run
&& max_tp_first_run
)
3654 node
->tp_first_run
= max_tp_first_run
+ 1;
3658 && call_count
* unlikely_frac
>= profile_info
->runs
)
3660 drop_profile (node
, call_count
);
3661 worklist
.safe_push (node
);
3665 /* Propagate the profile dropping to other 0-count COMDATs that are
3666 potentially called by COMDATs we already dropped the profile on. */
3667 while (worklist
.length () > 0)
3669 struct cgraph_edge
*e
;
3671 node
= worklist
.pop ();
3672 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3674 struct cgraph_node
*callee
= e
->callee
;
3675 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3677 if (!(e
->count
.ipa () == profile_count::zero ())
3678 && callee
->count
.ipa ().nonzero_p ())
3680 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3682 && profile_status_for_fn (fn
) == PROFILE_READ
)
3684 drop_profile (node
, profile_count::zero ());
3685 worklist
.safe_push (callee
);
3691 /* Convert counts measured by profile driven feedback to frequencies.
3692 Return nonzero iff there was any nonzero execution count. */
3695 update_max_bb_count (void)
3697 profile_count true_count_max
= profile_count::uninitialized ();
3700 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3701 true_count_max
= true_count_max
.max (bb
->count
);
3703 cfun
->cfg
->count_max
= true_count_max
;
3705 return true_count_max
.ipa ().nonzero_p ();
3708 /* Return true if function is likely to be expensive, so there is no point to
3709 optimize performance of prologue, epilogue or do inlining at the expense
3710 of code size growth. THRESHOLD is the limit of number of instructions
3711 function can execute at average to be still considered not expensive. */
3714 expensive_function_p (int threshold
)
3718 /* If profile was scaled in a way entry block has count 0, then the function
3719 is deifnitly taking a lot of time. */
3720 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3723 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
* threshold
;
3724 profile_count sum
= profile_count::zero ();
3725 FOR_EACH_BB_FN (bb
, cfun
)
3729 if (!bb
->count
.initialized_p ())
3732 fprintf (dump_file
, "Function is considered expensive because"
3733 " count of bb %i is not initialized\n", bb
->index
);
3737 FOR_BB_INSNS (bb
, insn
)
3738 if (active_insn_p (insn
))
3749 /* All basic blocks that are reachable only from unlikely basic blocks are
3753 propagate_unlikely_bbs_forward (void)
3755 auto_vec
<basic_block
, 64> worklist
;
3760 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3762 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3763 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3765 while (worklist
.length () > 0)
3767 bb
= worklist
.pop ();
3768 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3769 if (!(e
->count () == profile_count::zero ())
3770 && !(e
->dest
->count
== profile_count::zero ())
3773 e
->dest
->aux
= (void *)(size_t) 1;
3774 worklist
.safe_push (e
->dest
);
3779 FOR_ALL_BB_FN (bb
, cfun
)
3783 if (!(bb
->count
== profile_count::zero ())
3784 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3786 "Basic block %i is marked unlikely by forward prop\n",
3788 bb
->count
= profile_count::zero ();
3795 /* Determine basic blocks/edges that are known to be unlikely executed and set
3796 their counters to zero.
3797 This is done with first identifying obviously unlikely BBs/edges and then
3798 propagating in both directions. */
3801 determine_unlikely_bbs ()
3804 auto_vec
<basic_block
, 64> worklist
;
3808 FOR_EACH_BB_FN (bb
, cfun
)
3810 if (!(bb
->count
== profile_count::zero ())
3811 && unlikely_executed_bb_p (bb
))
3813 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3814 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3816 bb
->count
= profile_count::zero ();
3819 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3820 if (!(e
->probability
== profile_probability::never ())
3821 && unlikely_executed_edge_p (e
))
3823 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3824 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3825 bb
->index
, e
->dest
->index
);
3826 e
->probability
= profile_probability::never ();
3829 gcc_checking_assert (!bb
->aux
);
3831 propagate_unlikely_bbs_forward ();
3833 auto_vec
<int, 64> nsuccs
;
3834 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
), true);
3835 FOR_ALL_BB_FN (bb
, cfun
)
3836 if (!(bb
->count
== profile_count::zero ())
3837 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3839 nsuccs
[bb
->index
] = 0;
3840 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3841 if (!(e
->probability
== profile_probability::never ())
3842 && !(e
->dest
->count
== profile_count::zero ()))
3843 nsuccs
[bb
->index
]++;
3844 if (!nsuccs
[bb
->index
])
3845 worklist
.safe_push (bb
);
3847 while (worklist
.length () > 0)
3849 bb
= worklist
.pop ();
3850 if (bb
->count
== profile_count::zero ())
3852 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3855 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3856 !gsi_end_p (gsi
); gsi_next (&gsi
))
3857 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3858 /* stmt_can_terminate_bb_p special cases noreturns because it
3859 assumes that fake edges are created. We want to know that
3860 noreturn alone does not imply BB to be unlikely. */
3861 || (is_gimple_call (gsi_stmt (gsi
))
3862 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3872 "Basic block %i is marked unlikely by backward prop\n",
3874 bb
->count
= profile_count::zero ();
3875 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3876 if (!(e
->probability
== profile_probability::never ()))
3878 if (!(e
->src
->count
== profile_count::zero ()))
3880 gcc_checking_assert (nsuccs
[e
->src
->index
] > 0);
3881 nsuccs
[e
->src
->index
]--;
3882 if (!nsuccs
[e
->src
->index
])
3883 worklist
.safe_push (e
->src
);
3887 /* Finally all edges from non-0 regions to 0 are unlikely. */
3888 FOR_ALL_BB_FN (bb
, cfun
)
3890 if (!(bb
->count
== profile_count::zero ()))
3891 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3892 if (!(e
->probability
== profile_probability::never ())
3893 && e
->dest
->count
== profile_count::zero ())
3895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3896 fprintf (dump_file
, "Edge %i->%i is unlikely because "
3897 "it enters unlikely block\n",
3898 bb
->index
, e
->dest
->index
);
3899 e
->probability
= profile_probability::never ();
3904 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3905 if (e
->probability
== profile_probability::never ())
3915 && !(other
->probability
== profile_probability::always ()))
3917 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3918 fprintf (dump_file
, "Edge %i->%i is locally likely\n",
3919 bb
->index
, other
->dest
->index
);
3920 other
->probability
= profile_probability::always ();
3923 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3924 cgraph_node::get (current_function_decl
)->count
= profile_count::zero ();
3927 /* Estimate and propagate basic block frequencies using the given branch
3931 estimate_bb_frequencies ()
3936 determine_unlikely_bbs ();
3938 mark_dfs_back_edges ();
3940 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3941 profile_probability::always ();
3943 /* Set up block info for each basic block. */
3944 alloc_aux_for_blocks (sizeof (block_info
));
3945 alloc_aux_for_edges (sizeof (edge_prob_info
));
3946 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3951 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3953 /* FIXME: Graphite is producing edges with no profile. Once
3954 this is fixed, drop this. */
3955 if (e
->probability
.initialized_p ())
3956 EDGE_INFO (e
)->back_edge_prob
3957 = e
->probability
.to_sreal ();
3959 /* back_edge_prob = 0.5 */
3960 EDGE_INFO (e
)->back_edge_prob
= sreal (1, -1);
3964 /* First compute frequencies locally for each loop from innermost
3965 to outermost to examine frequencies for back edges. */
3969 FOR_EACH_BB_FN (bb
, cfun
)
3970 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3971 freq_max
= BLOCK_INFO (bb
)->frequency
;
3973 /* Scaling frequencies up to maximal profile count may result in
3974 frequent overflows especially when inlining loops.
3975 Small scalling results in unnecesary precision loss. Stay in
3976 the half of the (exponential) range. */
3977 freq_max
= (sreal (1) << (profile_count::n_bits
/ 2)) / freq_max
;
3980 profile_count ipa_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ();
3981 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3982 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3984 sreal tmp
= BLOCK_INFO (bb
)->frequency
;
3987 gimple_stmt_iterator gsi
;
3990 /* Self recursive calls can not have frequency greater than 1
3991 or program will never terminate. This will result in an
3992 inconsistent bb profile but it is better than greatly confusing
3993 IPA cost metrics. */
3994 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3995 if (is_gimple_call (gsi_stmt (gsi
))
3996 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
3997 && recursive_call_p (current_function_decl
, decl
))
4000 fprintf (dump_file
, "Dropping frequency of recursive call"
4001 " in bb %i from %f\n", bb
->index
,
4003 tmp
= (sreal
)9 / (sreal
)10;
4007 tmp
= tmp
* freq_max
;
4008 profile_count count
= profile_count::from_gcov_type (tmp
.to_nearest_int ());
4010 /* If we have profile feedback in which this function was never
4011 executed, then preserve this info. */
4012 if (!(bb
->count
== profile_count::zero ()))
4013 bb
->count
= count
.guessed_local ().combine_with_ipa_count (ipa_count
);
4014 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
4017 free_aux_for_blocks ();
4018 free_aux_for_edges ();
4019 compute_function_frequency ();
4022 /* Decide whether function is hot, cold or unlikely executed. */
4024 compute_function_frequency (void)
4027 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
4029 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
4030 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
4031 node
->only_called_at_startup
= true;
4032 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
4033 node
->only_called_at_exit
= true;
4035 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ())
4037 int flags
= flags_from_decl_or_type (current_function_decl
);
4038 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
4040 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
4041 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
4043 node
->frequency
= NODE_FREQUENCY_HOT
;
4044 else if (flags
& ECF_NORETURN
)
4045 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4046 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
4047 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4048 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
4049 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
4050 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4054 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
4055 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
4057 warn_function_cold (current_function_decl
);
4058 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
4060 FOR_EACH_BB_FN (bb
, cfun
)
4062 if (maybe_hot_bb_p (cfun
, bb
))
4064 node
->frequency
= NODE_FREQUENCY_HOT
;
4067 if (!probably_never_executed_bb_p (cfun
, bb
))
4068 node
->frequency
= NODE_FREQUENCY_NORMAL
;
4072 /* Build PREDICT_EXPR. */
4074 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
4076 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
4077 build_int_cst (integer_type_node
, predictor
));
4078 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
4083 predictor_name (enum br_predictor predictor
)
4085 return predictor_info
[predictor
].name
;
4088 /* Predict branch probabilities and estimate profile of the tree CFG. */
4092 const pass_data pass_data_profile
=
4094 GIMPLE_PASS
, /* type */
4095 "profile_estimate", /* name */
4096 OPTGROUP_NONE
, /* optinfo_flags */
4097 TV_BRANCH_PROB
, /* tv_id */
4098 PROP_cfg
, /* properties_required */
4099 0, /* properties_provided */
4100 0, /* properties_destroyed */
4101 0, /* todo_flags_start */
4102 0, /* todo_flags_finish */
4105 class pass_profile
: public gimple_opt_pass
4108 pass_profile (gcc::context
*ctxt
)
4109 : gimple_opt_pass (pass_data_profile
, ctxt
)
4112 /* opt_pass methods: */
4113 bool gate (function
*) final override
{ return flag_guess_branch_prob
; }
4114 unsigned int execute (function
*) final override
;
4116 }; // class pass_profile
4119 pass_profile::execute (function
*fun
)
4123 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4126 loop_optimizer_init (LOOPS_NORMAL
);
4127 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4128 flow_loops_dump (dump_file
, NULL
, 0);
4130 nb_loops
= number_of_loops (fun
);
4134 tree_estimate_probability (false);
4135 cfun
->cfg
->full_profile
= true;
4140 loop_optimizer_finalize ();
4141 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4142 gimple_dump_cfg (dump_file
, dump_flags
);
4143 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
4144 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
4145 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4148 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
4149 if (expected_loop_iterations_by_profile (loop
, &iterations
))
4150 fprintf (dump_file
, "Loop got predicted %d to iterate %f times.\n",
4151 loop
->num
, iterations
.to_double ());
4159 make_pass_profile (gcc::context
*ctxt
)
4161 return new pass_profile (ctxt
);
4164 /* Return true when PRED predictor should be removed after early
4165 tree passes. Most of the predictors are beneficial to survive
4166 as early inlining can also distribute then into caller's bodies. */
4169 strip_predictor_early (enum br_predictor pred
)
4173 case PRED_TREE_EARLY_RETURN
:
4180 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4181 we no longer need. EARLY is set to true when called from early
4185 strip_predict_hints (function
*fun
, bool early
)
4190 bool changed
= false;
4192 FOR_EACH_BB_FN (bb
, fun
)
4194 gimple_stmt_iterator bi
;
4195 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
4197 gimple
*stmt
= gsi_stmt (bi
);
4199 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
4202 || strip_predictor_early (gimple_predict_predictor (stmt
)))
4204 gsi_remove (&bi
, true);
4209 else if (is_gimple_call (stmt
))
4211 tree fndecl
= gimple_call_fndecl (stmt
);
4214 && ((fndecl
!= NULL_TREE
4215 && fndecl_built_in_p (fndecl
, BUILT_IN_EXPECT
)
4216 && gimple_call_num_args (stmt
) == 2)
4217 || (fndecl
!= NULL_TREE
4218 && fndecl_built_in_p (fndecl
,
4219 BUILT_IN_EXPECT_WITH_PROBABILITY
)
4220 && gimple_call_num_args (stmt
) == 3)
4221 || (gimple_call_internal_p (stmt
)
4222 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
)))
4224 var
= gimple_call_lhs (stmt
);
4229 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
4230 gsi_replace (&bi
, ass_stmt
, true);
4234 gsi_remove (&bi
, true);
4242 return changed
? TODO_cleanup_cfg
: 0;
4247 const pass_data pass_data_strip_predict_hints
=
4249 GIMPLE_PASS
, /* type */
4250 "*strip_predict_hints", /* name */
4251 OPTGROUP_NONE
, /* optinfo_flags */
4252 TV_BRANCH_PROB
, /* tv_id */
4253 PROP_cfg
, /* properties_required */
4254 0, /* properties_provided */
4255 0, /* properties_destroyed */
4256 0, /* todo_flags_start */
4257 0, /* todo_flags_finish */
4260 class pass_strip_predict_hints
: public gimple_opt_pass
4263 pass_strip_predict_hints (gcc::context
*ctxt
)
4264 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
4267 /* opt_pass methods: */
4268 opt_pass
* clone () final override
4270 return new pass_strip_predict_hints (m_ctxt
);
4272 void set_pass_param (unsigned int n
, bool param
) final override
4274 gcc_assert (n
== 0);
4278 unsigned int execute (function
*) final override
;
4283 }; // class pass_strip_predict_hints
4286 pass_strip_predict_hints::execute (function
*fun
)
4288 return strip_predict_hints (fun
, early_p
);
4294 make_pass_strip_predict_hints (gcc::context
*ctxt
)
4296 return new pass_strip_predict_hints (ctxt
);
4299 /* Rebuild function frequencies. Passes are in general expected to
4300 maintain profile by hand, however in some cases this is not possible:
4301 for example when inlining several functions with loops freuqencies might run
4302 out of scale and thus needs to be recomputed. */
4305 rebuild_frequencies (void)
4307 /* If we have no profile, do nothing. Note that after inlining
4308 profile_status_for_fn may not represent the actual presence/absence of
4310 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
4311 && !ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.initialized_p ())
4315 /* See if everything is OK and update count_max. */
4317 bool inconsistency_found
= false;
4318 bool uninitialized_probablity_found
= false;
4319 bool uninitialized_count_found
= false;
4321 cfun
->cfg
->count_max
= profile_count::uninitialized ();
4322 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
4324 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
4325 /* Uninitialized count may be result of inlining or an omision in an
4326 optimization pass. */
4327 if (!bb
->count
.initialized_p ())
4329 uninitialized_count_found
= true;
4331 fprintf (dump_file
, "BB %i has uninitialized count\n",
4334 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4335 && (!uninitialized_probablity_found
|| !inconsistency_found
))
4337 profile_count sum
= profile_count::zero ();
4341 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4344 /* Uninitialized probability may be result of inlining or an
4345 omision in an optimization pass. */
4346 if (!e
->probability
.initialized_p ())
4350 "Edge %i->%i has uninitialized probability\n",
4351 e
->src
->index
, e
->dest
->index
);
4354 if (sum
.differs_from_p (bb
->count
))
4358 "BB %i has invalid sum of incomming counts\n",
4360 inconsistency_found
= true;
4365 /* If everything is OK, do not re-propagate frequencies. */
4366 if (!inconsistency_found
4367 && (!uninitialized_count_found
|| uninitialized_probablity_found
)
4368 && !cfun
->cfg
->count_max
.very_large_p ())
4371 fprintf (dump_file
, "Profile is consistent\n");
4374 /* Do not re-propagate if we have profile feedback. Even if the profile is
4375 inconsistent from previous transofrmations, it is probably more realistic
4376 for hot part of the program than result of repropagating.
4378 Consider example where we previously has
4381 then [large probability for true]
4383 and we later proved that test is always 0. In this case, if profile was
4384 read correctly, we must have duplicated the conditional (for example by
4385 inlining) in to a context where test is false. From profile feedback
4386 we know that most executions if the conditionals were true, so the
4387 important copy is not the one we look on.
4389 Propagating from probabilities would make profile look consistent, but
4390 because probablities after code duplication may not be representative
4391 for a given run, we would only propagate the error further. */
4392 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ().nonzero_p ()
4393 && !uninitialized_count_found
)
4397 "Profile is inconsistent but read from profile feedback;"
4398 " not rebuilding\n");
4402 loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
4403 connect_infinite_loops_to_exit ();
4404 estimate_bb_frequencies ();
4405 remove_fake_exit_edges ();
4406 loop_optimizer_finalize ();
4408 fprintf (dump_file
, "Rebuilt basic block counts\n");
4415 const pass_data pass_data_rebuild_frequencies
=
4417 GIMPLE_PASS
, /* type */
4418 "rebuild_frequencies", /* name */
4419 OPTGROUP_NONE
, /* optinfo_flags */
4420 TV_REBUILD_FREQUENCIES
, /* tv_id */
4421 PROP_cfg
, /* properties_required */
4422 0, /* properties_provided */
4423 0, /* properties_destroyed */
4424 0, /* todo_flags_start */
4425 0, /* todo_flags_finish */
4428 class pass_rebuild_frequencies
: public gimple_opt_pass
4431 pass_rebuild_frequencies (gcc::context
*ctxt
)
4432 : gimple_opt_pass (pass_data_rebuild_frequencies
, ctxt
)
4435 /* opt_pass methods: */
4436 opt_pass
* clone () final override
4438 return new pass_rebuild_frequencies (m_ctxt
);
4440 void set_pass_param (unsigned int n
, bool param
) final override
4442 gcc_assert (n
== 0);
4446 unsigned int execute (function
*) final override
4448 rebuild_frequencies ();
4455 }; // class pass_rebuild_frequencies
4460 make_pass_rebuild_frequencies (gcc::context
*ctxt
)
4462 return new pass_rebuild_frequencies (ctxt
);
4465 /* Perform a dry run of the branch prediction pass and report comparsion of
4466 the predicted and real profile into the dump file. */
4469 report_predictor_hitrates (void)
4473 loop_optimizer_init (LOOPS_NORMAL
);
4474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4475 flow_loops_dump (dump_file
, NULL
, 0);
4477 nb_loops
= number_of_loops (cfun
);
4481 tree_estimate_probability (true);
4486 loop_optimizer_finalize ();
4489 /* Force edge E to be cold.
4490 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4491 keep low probability to represent possible error in a guess. This is used
4492 i.e. in case we predict loop to likely iterate given number of times but
4493 we are not 100% sure.
4495 This function locally updates profile without attempt to keep global
4496 consistency which cannot be reached in full generality without full profile
4497 rebuild from probabilities alone. Doing so is not necessarily a good idea
4498 because frequencies and counts may be more realistic then probabilities.
4500 In some cases (such as for elimination of early exits during full loop
4501 unrolling) the caller can ensure that profile will get consistent
4505 force_edge_cold (edge e
, bool impossible
)
4507 profile_count count_sum
= profile_count::zero ();
4508 profile_probability prob_sum
= profile_probability::never ();
4511 bool uninitialized_exit
= false;
4513 /* When branch probability guesses are not known, then do nothing. */
4514 if (!impossible
&& !e
->count ().initialized_p ())
4517 profile_probability goal
= (impossible
? profile_probability::never ()
4518 : profile_probability::very_unlikely ());
4520 /* If edge is already improbably or cold, just return. */
4521 if (e
->probability
<= goal
4522 && (!impossible
|| e
->count () == profile_count::zero ()))
4524 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4527 if (e
->flags
& EDGE_FAKE
)
4529 if (e2
->count ().initialized_p ())
4530 count_sum
+= e2
->count ();
4531 if (e2
->probability
.initialized_p ())
4532 prob_sum
+= e2
->probability
;
4534 uninitialized_exit
= true;
4537 /* If we are not guessing profiles but have some other edges out,
4538 just assume the control flow goes elsewhere. */
4539 if (uninitialized_exit
)
4540 e
->probability
= goal
;
4541 /* If there are other edges out of e->src, redistribute probabilitity
4543 else if (prob_sum
> profile_probability::never ())
4545 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4547 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
4548 "probability to other edges. Original probability: ",
4549 e
->src
->index
, e
->dest
->index
,
4550 impossible
? "impossible" : "cold");
4551 e
->probability
.dump (dump_file
);
4552 fprintf (dump_file
, "\n");
4554 set_edge_probability_and_rescale_others (e
, goal
);
4555 if (current_ir_type () != IR_GIMPLE
4556 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4557 update_br_prob_note (e
->src
);
4559 /* If all edges out of e->src are unlikely, the basic block itself
4563 if (prob_sum
== profile_probability::never ())
4564 e
->probability
= profile_probability::always ();
4568 e
->probability
= profile_probability::never ();
4569 /* If BB has some edges out that are not impossible, we cannot
4570 assume that BB itself is. */
4573 if (current_ir_type () != IR_GIMPLE
4574 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4575 update_br_prob_note (e
->src
);
4576 if (e
->src
->count
== profile_count::zero ())
4578 if (count_sum
== profile_count::zero () && impossible
)
4581 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4583 else if (current_ir_type () == IR_GIMPLE
)
4584 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4585 !gsi_end_p (gsi
); gsi_next (&gsi
))
4587 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4593 /* FIXME: Implement RTL path. */
4598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4600 "Making bb %i impossible and dropping count to 0.\n",
4602 e
->src
->count
= profile_count::zero ();
4603 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4604 force_edge_cold (e2
, impossible
);
4609 /* If we did not adjusting, the source basic block has no likely edeges
4610 leaving other direction. In that case force that bb cold, too.
4611 This in general is difficult task to do, but handle special case when
4612 BB has only one predecestor. This is common case when we are updating
4613 after loop transforms. */
4614 if (!(prob_sum
> profile_probability::never ())
4615 && count_sum
== profile_count::zero ()
4616 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4617 > (impossible
? 0 : 1))
4619 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4621 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4622 impossible
? "impossible" : "cold");
4623 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4624 impossible
? 0 : 1);
4626 e
->src
->count
= profile_count::zero ();
4628 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4630 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4632 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4633 && maybe_hot_bb_p (cfun
, e
->src
))
4634 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4635 impossible
? "impossible" : "cold");
4641 namespace selftest
{
4643 /* Test that value range of predictor values defined in predict.def is
4644 within range (50, 100]. */
4646 struct branch_predictor
4652 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4655 test_prediction_value_range ()
4657 branch_predictor predictors
[] = {
4658 #include "predict.def"
4659 { NULL
, PROB_UNINITIALIZED
}
4662 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4664 if (predictors
[i
].probability
== PROB_UNINITIALIZED
)
4667 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4668 ASSERT_TRUE (p
>= 50 && p
<= 100);
4672 #undef DEF_PREDICTOR
4674 /* Run all of the selfests within this file. */
4679 test_prediction_value_range ();
4682 } // namespace selftest
4683 #endif /* CHECKING_P. */