1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2022 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 ();
93 /* Information we hold about each branch predictor.
94 Filled using information from predict.def. */
98 const char *const name
; /* Name used in the debugging dumps. */
99 const int hitrate
; /* Expected hitrate used by
100 predict_insn_def call. */
104 /* Use given predictor without Dempster-Shaffer theory if it matches
105 using first_match heuristics. */
106 #define PRED_FLAG_FIRST_MATCH 1
108 /* Recompute hitrate in percent to our representation. */
110 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
112 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
113 static const struct predictor_info predictor_info
[]= {
114 #include "predict.def"
116 /* Upper bound on predictors. */
121 static gcov_type min_count
= -1;
123 /* Determine the threshold for hot BB counts. */
126 get_hot_bb_threshold ()
130 const int hot_frac
= param_hot_bb_count_fraction
;
131 const gcov_type min_hot_count
133 ? profile_info
->sum_max
/ hot_frac
134 : (gcov_type
)profile_count::max_count
;
135 set_hot_bb_threshold (min_hot_count
);
137 fprintf (dump_file
, "Setting hotness threshold to %" PRId64
".\n",
143 /* Set the threshold for hot BB counts. */
146 set_hot_bb_threshold (gcov_type min
)
151 /* Return TRUE if COUNT is considered to be hot in function FUN. */
154 maybe_hot_count_p (struct function
*fun
, profile_count count
)
156 if (!count
.initialized_p ())
158 if (count
.ipa () == profile_count::zero ())
162 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
163 if (!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
165 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
167 if (node
->frequency
== NODE_FREQUENCY_HOT
)
170 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
172 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
173 && count
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
.apply_scale (2, 3)))
175 if (count
* param_hot_bb_frequency_fraction
176 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
180 /* Code executed at most once is not hot. */
181 if (count
<= MAX (profile_info
? profile_info
->runs
: 1, 1))
183 return (count
>= get_hot_bb_threshold ());
186 /* Return true if basic block BB of function FUN can be CPU intensive
187 and should thus be optimized for maximum performance. */
190 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
192 gcc_checking_assert (fun
);
193 return maybe_hot_count_p (fun
, bb
->count
);
196 /* Return true if edge E can be CPU intensive and should thus be optimized
197 for maximum performance. */
200 maybe_hot_edge_p (edge e
)
202 return maybe_hot_count_p (cfun
, e
->count ());
205 /* Return true if COUNT is considered to be never executed in function FUN
206 or if function FUN is considered so in the static profile. */
209 probably_never_executed (struct function
*fun
, profile_count count
)
211 gcc_checking_assert (fun
);
212 if (count
.ipa () == profile_count::zero ())
214 /* Do not trust adjusted counts. This will make us to drop int cold section
215 code with low execution count as a result of inlining. These low counts
216 are not safe even with read profile and may lead us to dropping
217 code which actually gets executed into cold section of binary that is not
219 if (count
.precise_p () && profile_status_for_fn (fun
) == PROFILE_READ
)
221 const int unlikely_frac
= param_unlikely_bb_count_fraction
;
222 if (count
* unlikely_frac
>= profile_info
->runs
)
226 if ((!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
227 && (cgraph_node::get (fun
->decl
)->frequency
228 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
233 /* Return true if basic block BB of function FUN is probably never executed. */
236 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
238 return probably_never_executed (fun
, bb
->count
);
241 /* Return true if edge E is unlikely executed for obvious reasons. */
244 unlikely_executed_edge_p (edge e
)
246 return (e
->src
->count
== profile_count::zero ()
247 || e
->probability
== profile_probability::never ())
248 || (e
->flags
& (EDGE_EH
| EDGE_FAKE
));
251 /* Return true if edge E of function FUN is probably never executed. */
254 probably_never_executed_edge_p (struct function
*fun
, edge e
)
256 if (unlikely_executed_edge_p (e
))
258 return probably_never_executed (fun
, e
->count ());
261 /* Return true if function FUN should always be optimized for size. */
264 optimize_function_for_size_p (struct function
*fun
)
266 if (!fun
|| !fun
->decl
)
267 return optimize_size
? OPTIMIZE_SIZE_MAX
: OPTIMIZE_SIZE_NO
;
268 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
270 return n
->optimize_for_size_p ();
271 return OPTIMIZE_SIZE_NO
;
274 /* Return true if function FUN should always be optimized for speed. */
277 optimize_function_for_speed_p (struct function
*fun
)
279 return !optimize_function_for_size_p (fun
);
282 /* Return the optimization type that should be used for function FUN. */
285 function_optimization_type (struct function
*fun
)
287 return (optimize_function_for_speed_p (fun
)
289 : OPTIMIZE_FOR_SIZE
);
292 /* Return TRUE if basic block BB should be optimized for size. */
295 optimize_bb_for_size_p (const_basic_block bb
)
297 enum optimize_size_level ret
= optimize_function_for_size_p (cfun
);
299 if (bb
&& ret
< OPTIMIZE_SIZE_MAX
&& bb
->count
== profile_count::zero ())
300 ret
= OPTIMIZE_SIZE_MAX
;
301 if (bb
&& ret
< OPTIMIZE_SIZE_BALANCED
&& !maybe_hot_bb_p (cfun
, bb
))
302 ret
= OPTIMIZE_SIZE_BALANCED
;
306 /* Return TRUE if basic block BB should be optimized for speed. */
309 optimize_bb_for_speed_p (const_basic_block bb
)
311 return !optimize_bb_for_size_p (bb
);
314 /* Return the optimization type that should be used for basic block BB. */
317 bb_optimization_type (const_basic_block bb
)
319 return (optimize_bb_for_speed_p (bb
)
321 : OPTIMIZE_FOR_SIZE
);
324 /* Return TRUE if edge E should be optimized for size. */
327 optimize_edge_for_size_p (edge e
)
329 enum optimize_size_level ret
= optimize_function_for_size_p (cfun
);
331 if (ret
< OPTIMIZE_SIZE_MAX
&& unlikely_executed_edge_p (e
))
332 ret
= OPTIMIZE_SIZE_MAX
;
333 if (ret
< OPTIMIZE_SIZE_BALANCED
&& !maybe_hot_edge_p (e
))
334 ret
= OPTIMIZE_SIZE_BALANCED
;
338 /* Return TRUE if edge E should be optimized for speed. */
341 optimize_edge_for_speed_p (edge e
)
343 return !optimize_edge_for_size_p (e
);
346 /* Return TRUE if the current function is optimized for size. */
349 optimize_insn_for_size_p (void)
351 enum optimize_size_level ret
= optimize_function_for_size_p (cfun
);
352 if (ret
< OPTIMIZE_SIZE_BALANCED
&& !crtl
->maybe_hot_insn_p
)
353 ret
= OPTIMIZE_SIZE_BALANCED
;
357 /* Return TRUE if the current function is optimized for speed. */
360 optimize_insn_for_speed_p (void)
362 return !optimize_insn_for_size_p ();
365 /* Return TRUE if LOOP should be optimized for size. */
368 optimize_loop_for_size_p (class loop
*loop
)
370 return optimize_bb_for_size_p (loop
->header
);
373 /* Return TRUE if LOOP should be optimized for speed. */
376 optimize_loop_for_speed_p (class loop
*loop
)
378 return optimize_bb_for_speed_p (loop
->header
);
381 /* Return TRUE if nest rooted at LOOP should be optimized for speed. */
384 optimize_loop_nest_for_speed_p (class loop
*loop
)
386 class loop
*l
= loop
;
387 if (optimize_loop_for_speed_p (loop
))
390 while (l
&& l
!= loop
)
392 if (optimize_loop_for_speed_p (l
))
400 while (l
!= loop
&& !l
->next
)
409 /* Return TRUE if nest rooted at LOOP should be optimized for size. */
412 optimize_loop_nest_for_size_p (class loop
*loop
)
414 enum optimize_size_level ret
= optimize_loop_for_size_p (loop
);
415 class loop
*l
= loop
;
418 while (l
&& l
!= loop
)
420 if (ret
== OPTIMIZE_SIZE_NO
)
422 ret
= MIN (optimize_loop_for_size_p (l
), ret
);
429 while (l
!= loop
&& !l
->next
)
438 /* Return true if edge E is likely to be well predictable by branch
442 predictable_edge_p (edge e
)
444 if (!e
->probability
.initialized_p ())
446 if ((e
->probability
.to_reg_br_prob_base ()
447 <= param_predictable_branch_outcome
* REG_BR_PROB_BASE
/ 100)
448 || (REG_BR_PROB_BASE
- e
->probability
.to_reg_br_prob_base ()
449 <= param_predictable_branch_outcome
* REG_BR_PROB_BASE
/ 100))
455 /* Set RTL expansion for BB profile. */
458 rtl_profile_for_bb (basic_block bb
)
460 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
463 /* Set RTL expansion for edge profile. */
466 rtl_profile_for_edge (edge e
)
468 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
471 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
473 default_rtl_profile (void)
475 crtl
->maybe_hot_insn_p
= true;
478 /* Return true if the one of outgoing edges is already predicted by
482 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
485 if (!INSN_P (BB_END (bb
)))
487 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
488 if (REG_NOTE_KIND (note
) == REG_BR_PRED
489 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
494 /* Structure representing predictions in tree level. */
496 struct edge_prediction
{
497 struct edge_prediction
*ep_next
;
499 enum br_predictor ep_predictor
;
503 /* This map contains for a basic block the list of predictions for the
506 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
508 /* Return true if the one of outgoing edges is already predicted by
512 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
514 struct edge_prediction
*i
;
515 edge_prediction
**preds
= bb_predictions
->get (bb
);
520 for (i
= *preds
; i
; i
= i
->ep_next
)
521 if (i
->ep_predictor
== predictor
)
526 /* Return true if the one of outgoing edges is already predicted by
527 PREDICTOR for edge E predicted as TAKEN. */
530 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
532 struct edge_prediction
*i
;
533 basic_block bb
= e
->src
;
534 edge_prediction
**preds
= bb_predictions
->get (bb
);
538 int probability
= predictor_info
[(int) predictor
].hitrate
;
541 probability
= REG_BR_PROB_BASE
- probability
;
543 for (i
= *preds
; i
; i
= i
->ep_next
)
544 if (i
->ep_predictor
== predictor
546 && i
->ep_probability
== probability
)
551 /* Same predicate as above, working on edges. */
553 edge_probability_reliable_p (const_edge e
)
555 return e
->probability
.probably_reliable_p ();
558 /* Same predicate as edge_probability_reliable_p, working on notes. */
560 br_prob_note_reliable_p (const_rtx note
)
562 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
563 return profile_probability::from_reg_br_prob_note
564 (XINT (note
, 0)).probably_reliable_p ();
568 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
570 gcc_assert (any_condjump_p (insn
));
571 if (!flag_guess_branch_prob
)
574 add_reg_note (insn
, REG_BR_PRED
,
575 gen_rtx_CONCAT (VOIDmode
,
576 GEN_INT ((int) predictor
),
577 GEN_INT ((int) probability
)));
580 /* Predict insn by given predictor. */
583 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
584 enum prediction taken
)
586 int probability
= predictor_info
[(int) predictor
].hitrate
;
587 gcc_assert (probability
!= PROB_UNINITIALIZED
);
590 probability
= REG_BR_PROB_BASE
- probability
;
592 predict_insn (insn
, predictor
, probability
);
595 /* Predict edge E with given probability if possible. */
598 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
601 last_insn
= BB_END (e
->src
);
603 /* We can store the branch prediction information only about
604 conditional jumps. */
605 if (!any_condjump_p (last_insn
))
608 /* We always store probability of branching. */
609 if (e
->flags
& EDGE_FALLTHRU
)
610 probability
= REG_BR_PROB_BASE
- probability
;
612 predict_insn (last_insn
, predictor
, probability
);
615 /* Predict edge E with the given PROBABILITY. */
617 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
619 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
620 && EDGE_COUNT (e
->src
->succs
) > 1
621 && flag_guess_branch_prob
624 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
625 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
629 i
->ep_probability
= probability
;
630 i
->ep_predictor
= predictor
;
635 /* Filter edge predictions PREDS by a function FILTER: if FILTER return false
636 the prediction is removed.
637 DATA are passed to the filter function. */
640 filter_predictions (edge_prediction
**preds
,
641 bool (*filter
) (edge_prediction
*, void *), void *data
)
648 struct edge_prediction
**prediction
= preds
;
649 struct edge_prediction
*next
;
653 if ((*filter
) (*prediction
, data
))
654 prediction
= &((*prediction
)->ep_next
);
657 next
= (*prediction
)->ep_next
;
665 /* Filter function predicate that returns true for a edge predicate P
666 if its edge is equal to DATA. */
669 not_equal_edge_p (edge_prediction
*p
, void *data
)
671 return p
->ep_edge
!= (edge
)data
;
674 /* Remove all predictions on given basic block that are attached
677 remove_predictions_associated_with_edge (edge e
)
682 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
683 filter_predictions (preds
, not_equal_edge_p
, e
);
686 /* Clears the list of predictions stored for BB. */
689 clear_bb_predictions (basic_block bb
)
691 edge_prediction
**preds
= bb_predictions
->get (bb
);
692 struct edge_prediction
*pred
, *next
;
697 for (pred
= *preds
; pred
; pred
= next
)
699 next
= pred
->ep_next
;
705 /* Return true when we can store prediction on insn INSN.
706 At the moment we represent predictions only on conditional
707 jumps, not at computed jump or other complicated cases. */
709 can_predict_insn_p (const rtx_insn
*insn
)
711 return (JUMP_P (insn
)
712 && any_condjump_p (insn
)
713 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
716 /* Predict edge E by given predictor if possible. */
719 predict_edge_def (edge e
, enum br_predictor predictor
,
720 enum prediction taken
)
722 int probability
= predictor_info
[(int) predictor
].hitrate
;
725 probability
= REG_BR_PROB_BASE
- probability
;
727 predict_edge (e
, predictor
, probability
);
730 /* Invert all branch predictions or probability notes in the INSN. This needs
731 to be done each time we invert the condition used by the jump. */
734 invert_br_probabilities (rtx insn
)
738 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
739 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
740 XINT (note
, 0) = profile_probability::from_reg_br_prob_note
741 (XINT (note
, 0)).invert ().to_reg_br_prob_note ();
742 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
743 XEXP (XEXP (note
, 0), 1)
744 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
747 /* Dump information about the branch prediction to the output file. */
750 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
751 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
761 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
762 if (! (e
->flags
& EDGE_FALLTHRU
))
765 char edge_info_str
[128];
767 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
768 ep_edge
->dest
->index
);
770 edge_info_str
[0] = '\0';
772 fprintf (file
, " %s heuristics%s%s: %.2f%%",
773 predictor_info
[predictor
].name
,
774 edge_info_str
, reason_messages
[reason
],
775 probability
* 100.0 / REG_BR_PROB_BASE
);
777 if (bb
->count
.initialized_p ())
779 fprintf (file
, " exec ");
780 bb
->count
.dump (file
);
783 fprintf (file
, " hit ");
784 e
->count ().dump (file
);
785 fprintf (file
, " (%.1f%%)", e
->count ().to_gcov_type() * 100.0
786 / bb
->count
.to_gcov_type ());
790 fprintf (file
, "\n");
792 /* Print output that be easily read by analyze_brprob.py script. We are
793 interested only in counts that are read from GCDA files. */
794 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
795 && bb
->count
.precise_p ()
796 && reason
== REASON_NONE
)
798 fprintf (file
, ";;heuristics;%s;%" PRId64
";%" PRId64
";%.1f;\n",
799 predictor_info
[predictor
].name
,
800 bb
->count
.to_gcov_type (), e
->count ().to_gcov_type (),
801 probability
* 100.0 / REG_BR_PROB_BASE
);
805 /* Return true if STMT is known to be unlikely executed. */
808 unlikely_executed_stmt_p (gimple
*stmt
)
810 if (!is_gimple_call (stmt
))
812 /* NORETURN attribute alone is not strong enough: exit() may be quite
813 likely executed once during program run. */
814 if (gimple_call_fntype (stmt
)
815 && lookup_attribute ("cold",
816 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
817 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
819 tree decl
= gimple_call_fndecl (stmt
);
822 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
823 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
826 cgraph_node
*n
= cgraph_node::get (decl
);
831 n
= n
->ultimate_alias_target (&avail
);
832 if (avail
< AVAIL_AVAILABLE
)
835 || n
->decl
== current_function_decl
)
837 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
840 /* Return true if BB is unlikely executed. */
843 unlikely_executed_bb_p (basic_block bb
)
845 if (bb
->count
== profile_count::zero ())
847 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
849 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
850 !gsi_end_p (gsi
); gsi_next (&gsi
))
852 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
854 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
860 /* We cannot predict the probabilities of outgoing edges of bb. Set them
861 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
862 even probability for all edges not mentioned in the set. These edges
863 are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES,
864 if we have exactly one likely edge, make the other edges predicted
868 set_even_probabilities (basic_block bb
,
869 hash_set
<edge
> *unlikely_edges
= NULL
,
870 hash_set
<edge_prediction
*> *likely_edges
= NULL
)
872 unsigned nedges
= 0, unlikely_count
= 0;
875 profile_probability all
= profile_probability::always ();
877 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
878 if (e
->probability
.initialized_p ())
879 all
-= e
->probability
;
880 else if (!unlikely_executed_edge_p (e
))
883 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
885 all
-= profile_probability::very_unlikely ();
890 /* Make the distribution even if all edges are unlikely. */
891 unsigned likely_count
= likely_edges
? likely_edges
->elements () : 0;
892 if (unlikely_count
== nedges
)
894 unlikely_edges
= NULL
;
898 /* If we have one likely edge, then use its probability and distribute
899 remaining probabilities as even. */
900 if (likely_count
== 1)
902 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
903 if (e
->probability
.initialized_p ())
905 else if (!unlikely_executed_edge_p (e
))
907 edge_prediction
*prediction
= *likely_edges
->begin ();
908 int p
= prediction
->ep_probability
;
909 profile_probability prob
910 = profile_probability::from_reg_br_prob_base (p
);
912 if (prediction
->ep_edge
== e
)
913 e
->probability
= prob
;
914 else if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
915 e
->probability
= profile_probability::very_unlikely ();
918 profile_probability remainder
= prob
.invert ();
919 remainder
-= (profile_probability::very_unlikely ()
921 int count
= nedges
- unlikely_count
- 1;
922 gcc_assert (count
>= 0);
924 e
->probability
= remainder
/ count
;
928 e
->probability
= profile_probability::never ();
932 /* Make all unlikely edges unlikely and the rest will have even
934 unsigned scale
= nedges
- unlikely_count
;
935 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
936 if (e
->probability
.initialized_p ())
938 else if (!unlikely_executed_edge_p (e
))
940 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
941 e
->probability
= profile_probability::very_unlikely ();
943 e
->probability
= all
/ scale
;
946 e
->probability
= profile_probability::never ();
950 /* Add REG_BR_PROB note to JUMP with PROB. */
953 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
955 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
956 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
959 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
960 note if not already present. Remove now useless REG_BR_PRED notes. */
963 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
968 int best_probability
= PROB_EVEN
;
969 enum br_predictor best_predictor
= END_PREDICTORS
;
970 int combined_probability
= REG_BR_PROB_BASE
/ 2;
972 bool first_match
= false;
975 if (!can_predict_insn_p (insn
))
977 set_even_probabilities (bb
);
981 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
982 pnote
= ®_NOTES (insn
);
984 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
987 /* We implement "first match" heuristics and use probability guessed
988 by predictor with smallest index. */
989 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
990 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
992 enum br_predictor predictor
= ((enum br_predictor
)
993 INTVAL (XEXP (XEXP (note
, 0), 0)));
994 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
997 if (best_predictor
> predictor
998 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
999 best_probability
= probability
, best_predictor
= predictor
;
1001 d
= (combined_probability
* probability
1002 + (REG_BR_PROB_BASE
- combined_probability
)
1003 * (REG_BR_PROB_BASE
- probability
));
1005 /* Use FP math to avoid overflows of 32bit integers. */
1007 /* If one probability is 0% and one 100%, avoid division by zero. */
1008 combined_probability
= REG_BR_PROB_BASE
/ 2;
1010 combined_probability
= (((double) combined_probability
) * probability
1011 * REG_BR_PROB_BASE
/ d
+ 0.5);
1014 /* Decide which heuristic to use. In case we didn't match anything,
1015 use no_prediction heuristic, in case we did match, use either
1016 first match or Dempster-Shaffer theory depending on the flags. */
1018 if (best_predictor
!= END_PREDICTORS
)
1022 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
1023 combined_probability
, bb
);
1027 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
1028 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
1030 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
1031 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
1035 combined_probability
= best_probability
;
1036 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1040 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
1042 enum br_predictor predictor
= ((enum br_predictor
)
1043 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
1044 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
1046 dump_prediction (dump_file
, predictor
, probability
, bb
,
1047 (!first_match
|| best_predictor
== predictor
)
1048 ? REASON_NONE
: REASON_IGNORED
);
1049 *pnote
= XEXP (*pnote
, 1);
1052 pnote
= &XEXP (*pnote
, 1);
1057 profile_probability p
1058 = profile_probability::from_reg_br_prob_base (combined_probability
);
1059 add_reg_br_prob_note (insn
, p
);
1061 /* Save the prediction into CFG in case we are seeing non-degenerated
1062 conditional jump. */
1063 if (!single_succ_p (bb
))
1065 BRANCH_EDGE (bb
)->probability
= p
;
1066 FALLTHRU_EDGE (bb
)->probability
1067 = BRANCH_EDGE (bb
)->probability
.invert ();
1070 else if (!single_succ_p (bb
))
1072 profile_probability prob
= profile_probability::from_reg_br_prob_note
1073 (XINT (prob_note
, 0));
1075 BRANCH_EDGE (bb
)->probability
= prob
;
1076 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
1079 single_succ_edge (bb
)->probability
= profile_probability::always ();
1082 /* Edge prediction hash traits. */
1084 struct predictor_hash
: pointer_hash
<edge_prediction
>
1087 static inline hashval_t
hash (const edge_prediction
*);
1088 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
1091 /* Calculate hash value of an edge prediction P based on predictor and
1092 normalized probability. */
1095 predictor_hash::hash (const edge_prediction
*p
)
1097 inchash::hash hstate
;
1098 hstate
.add_int (p
->ep_predictor
);
1100 int prob
= p
->ep_probability
;
1101 if (prob
> REG_BR_PROB_BASE
/ 2)
1102 prob
= REG_BR_PROB_BASE
- prob
;
1104 hstate
.add_int (prob
);
1106 return hstate
.end ();
1109 /* Return true whether edge predictions P1 and P2 use the same predictor and
1110 have equal (or opposed probability). */
1113 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1115 return (p1
->ep_predictor
== p2
->ep_predictor
1116 && (p1
->ep_probability
== p2
->ep_probability
1117 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1120 struct predictor_hash_traits
: predictor_hash
,
1121 typed_noop_remove
<edge_prediction
*> {};
1123 /* Return true if edge prediction P is not in DATA hash set. */
1126 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1128 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1129 return !remove
->contains (p
);
1132 /* Prune predictions for a basic block BB. Currently we do following
1135 1) remove duplicate prediction that is guessed with the same probability
1136 (different than 1/2) to both edge
1137 2) remove duplicates for a prediction that belongs with the same probability
1143 prune_predictions_for_bb (basic_block bb
)
1145 edge_prediction
**preds
= bb_predictions
->get (bb
);
1149 hash_table
<predictor_hash_traits
> s (13);
1150 hash_set
<edge_prediction
*> remove
;
1152 /* Step 1: identify predictors that should be removed. */
1153 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1155 edge_prediction
*existing
= s
.find (pred
);
1158 if (pred
->ep_edge
== existing
->ep_edge
1159 && pred
->ep_probability
== existing
->ep_probability
)
1161 /* Remove a duplicate predictor. */
1162 dump_prediction (dump_file
, pred
->ep_predictor
,
1163 pred
->ep_probability
, bb
,
1164 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1168 else if (pred
->ep_edge
!= existing
->ep_edge
1169 && pred
->ep_probability
== existing
->ep_probability
1170 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1172 /* Remove both predictors as they predict the same
1174 dump_prediction (dump_file
, existing
->ep_predictor
,
1175 pred
->ep_probability
, bb
,
1176 REASON_EDGE_PAIR_DUPLICATE
,
1178 dump_prediction (dump_file
, pred
->ep_predictor
,
1179 pred
->ep_probability
, bb
,
1180 REASON_EDGE_PAIR_DUPLICATE
,
1183 remove
.add (existing
);
1188 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1192 /* Step 2: Remove predictors. */
1193 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1197 /* Combine predictions into single probability and store them into CFG.
1198 Remove now useless prediction entries.
1199 If DRY_RUN is set, only produce dumps and do not modify profile. */
1202 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1204 int best_probability
= PROB_EVEN
;
1205 enum br_predictor best_predictor
= END_PREDICTORS
;
1206 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1208 bool first_match
= false;
1210 struct edge_prediction
*pred
;
1212 edge e
, first
= NULL
, second
= NULL
;
1217 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1219 if (!unlikely_executed_edge_p (e
))
1222 if (first
&& !second
)
1227 else if (!e
->probability
.initialized_p ())
1228 e
->probability
= profile_probability::never ();
1229 if (!e
->probability
.initialized_p ())
1231 else if (e
->probability
== profile_probability::never ())
1235 /* When there is no successor or only one choice, prediction is easy.
1237 When we have a basic block with more than 2 successors, the situation
1238 is more complicated as DS theory cannot be used literally.
1239 More precisely, let's assume we predicted edge e1 with probability p1,
1240 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1241 need to find probability of e.g. m1({b2}), which we don't know.
1242 The only approximation is to equally distribute 1-p1 to all edges
1245 According to numbers we've got from SPEC2006 benchark, there's only
1246 one interesting reliable predictor (noreturn call), which can be
1247 handled with a bit easier approach. */
1250 hash_set
<edge
> unlikely_edges (4);
1251 hash_set
<edge_prediction
*> likely_edges (4);
1253 /* Identify all edges that have a probability close to very unlikely.
1254 Doing the approach for very unlikely doesn't worth for doing as
1255 there's no such probability in SPEC2006 benchmark. */
1256 edge_prediction
**preds
= bb_predictions
->get (bb
);
1258 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1260 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
1261 || pred
->ep_predictor
== PRED_COLD_LABEL
)
1262 unlikely_edges
.add (pred
->ep_edge
);
1263 else if (pred
->ep_probability
>= PROB_VERY_LIKELY
1264 || pred
->ep_predictor
== PRED_BUILTIN_EXPECT
1265 || pred
->ep_predictor
== PRED_HOT_LABEL
)
1266 likely_edges
.add (pred
);
1269 /* It can happen that an edge is both in likely_edges and unlikely_edges.
1270 Clear both sets in that situation. */
1271 for (hash_set
<edge_prediction
*>::iterator it
= likely_edges
.begin ();
1272 it
!= likely_edges
.end (); ++it
)
1273 if (unlikely_edges
.contains ((*it
)->ep_edge
))
1275 likely_edges
.empty ();
1276 unlikely_edges
.empty ();
1281 set_even_probabilities (bb
, &unlikely_edges
, &likely_edges
);
1282 clear_bb_predictions (bb
);
1285 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1286 if (unlikely_edges
.is_empty ())
1288 "%i edges in bb %i predicted to even probabilities\n",
1293 "%i edges in bb %i predicted with some unlikely edges\n",
1295 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1296 if (!unlikely_executed_edge_p (e
))
1297 dump_prediction (dump_file
, PRED_COMBINED
,
1298 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1305 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1307 prune_predictions_for_bb (bb
);
1309 edge_prediction
**preds
= bb_predictions
->get (bb
);
1313 /* We implement "first match" heuristics and use probability guessed
1314 by predictor with smallest index. */
1315 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1317 enum br_predictor predictor
= pred
->ep_predictor
;
1318 int probability
= pred
->ep_probability
;
1320 if (pred
->ep_edge
!= first
)
1321 probability
= REG_BR_PROB_BASE
- probability
;
1324 /* First match heuristics would be widly confused if we predicted
1326 if (best_predictor
> predictor
1327 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1329 struct edge_prediction
*pred2
;
1330 int prob
= probability
;
1332 for (pred2
= (struct edge_prediction
*) *preds
;
1333 pred2
; pred2
= pred2
->ep_next
)
1334 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1336 int probability2
= pred2
->ep_probability
;
1338 if (pred2
->ep_edge
!= first
)
1339 probability2
= REG_BR_PROB_BASE
- probability2
;
1341 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1342 (probability2
< REG_BR_PROB_BASE
/ 2))
1345 /* If the same predictor later gave better result, go for it! */
1346 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1347 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1348 prob
= probability2
;
1351 best_probability
= prob
, best_predictor
= predictor
;
1354 d
= (combined_probability
* probability
1355 + (REG_BR_PROB_BASE
- combined_probability
)
1356 * (REG_BR_PROB_BASE
- probability
));
1358 /* Use FP math to avoid overflows of 32bit integers. */
1360 /* If one probability is 0% and one 100%, avoid division by zero. */
1361 combined_probability
= REG_BR_PROB_BASE
/ 2;
1363 combined_probability
= (((double) combined_probability
)
1365 * REG_BR_PROB_BASE
/ d
+ 0.5);
1369 /* Decide which heuristic to use. In case we didn't match anything,
1370 use no_prediction heuristic, in case we did match, use either
1371 first match or Dempster-Shaffer theory depending on the flags. */
1373 if (best_predictor
!= END_PREDICTORS
)
1377 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1381 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1382 !first_match
? REASON_NONE
: REASON_IGNORED
);
1384 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1385 first_match
? REASON_NONE
: REASON_IGNORED
);
1389 combined_probability
= best_probability
;
1390 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1394 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1396 enum br_predictor predictor
= pred
->ep_predictor
;
1397 int probability
= pred
->ep_probability
;
1399 dump_prediction (dump_file
, predictor
, probability
, bb
,
1400 (!first_match
|| best_predictor
== predictor
)
1401 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1404 clear_bb_predictions (bb
);
1407 /* If we have only one successor which is unknown, we can compute missing
1411 profile_probability prob
= profile_probability::always ();
1412 edge missing
= NULL
;
1414 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1415 if (e
->probability
.initialized_p ())
1416 prob
-= e
->probability
;
1417 else if (missing
== NULL
)
1421 missing
->probability
= prob
;
1423 /* If nothing is unknown, we have nothing to update. */
1424 else if (!nunknown
&& nzero
!= (int)EDGE_COUNT (bb
->succs
))
1429 = profile_probability::from_reg_br_prob_base (combined_probability
);
1430 second
->probability
= first
->probability
.invert ();
1434 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1435 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1437 T1 and T2 should be one of the following cases:
1438 1. T1 is SSA_NAME, T2 is NULL
1439 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1440 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1443 strips_small_constant (tree t1
, tree t2
)
1450 else if (TREE_CODE (t1
) == SSA_NAME
)
1452 else if (tree_fits_shwi_p (t1
))
1453 value
= tree_to_shwi (t1
);
1459 else if (tree_fits_shwi_p (t2
))
1460 value
= tree_to_shwi (t2
);
1461 else if (TREE_CODE (t2
) == SSA_NAME
)
1469 if (value
<= 4 && value
>= -4)
1475 /* Return the SSA_NAME in T or T's operands.
1476 Return NULL if SSA_NAME cannot be found. */
1479 get_base_value (tree t
)
1481 if (TREE_CODE (t
) == SSA_NAME
)
1484 if (!BINARY_CLASS_P (t
))
1487 switch (TREE_OPERAND_LENGTH (t
))
1490 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1492 return strips_small_constant (TREE_OPERAND (t
, 0),
1493 TREE_OPERAND (t
, 1));
1499 /* Check the compare STMT in LOOP. If it compares an induction
1500 variable to a loop invariant, return true, and save
1501 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1502 Otherwise return false and set LOOP_INVAIANT to NULL. */
1505 is_comparison_with_loop_invariant_p (gcond
*stmt
, class loop
*loop
,
1506 tree
*loop_invariant
,
1507 enum tree_code
*compare_code
,
1511 tree op0
, op1
, bound
, base
;
1513 enum tree_code code
;
1516 code
= gimple_cond_code (stmt
);
1517 *loop_invariant
= NULL
;
1533 op0
= gimple_cond_lhs (stmt
);
1534 op1
= gimple_cond_rhs (stmt
);
1536 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1537 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1539 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1541 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1543 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1544 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1546 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1547 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1550 if (integer_zerop (iv0
.step
))
1552 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1553 code
= invert_tree_comparison (code
, false);
1556 if (tree_fits_shwi_p (iv1
.step
))
1565 if (tree_fits_shwi_p (iv0
.step
))
1571 if (TREE_CODE (bound
) != INTEGER_CST
)
1572 bound
= get_base_value (bound
);
1575 if (TREE_CODE (base
) != INTEGER_CST
)
1576 base
= get_base_value (base
);
1580 *loop_invariant
= bound
;
1581 *compare_code
= code
;
1583 *loop_iv_base
= base
;
1587 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1590 expr_coherent_p (tree t1
, tree t2
)
1593 tree ssa_name_1
= NULL
;
1594 tree ssa_name_2
= NULL
;
1596 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1597 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1602 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1604 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1607 /* Check to see if t1 is expressed/defined with t2. */
1608 stmt
= SSA_NAME_DEF_STMT (t1
);
1609 gcc_assert (stmt
!= NULL
);
1610 if (is_gimple_assign (stmt
))
1612 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1613 if (ssa_name_1
&& ssa_name_1
== t2
)
1617 /* Check to see if t2 is expressed/defined with t1. */
1618 stmt
= SSA_NAME_DEF_STMT (t2
);
1619 gcc_assert (stmt
!= NULL
);
1620 if (is_gimple_assign (stmt
))
1622 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1623 if (ssa_name_2
&& ssa_name_2
== t1
)
1627 /* Compare if t1 and t2's def_stmts are identical. */
1628 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1634 /* Return true if E is predicted by one of loop heuristics. */
1637 predicted_by_loop_heuristics_p (basic_block bb
)
1639 struct edge_prediction
*i
;
1640 edge_prediction
**preds
= bb_predictions
->get (bb
);
1645 for (i
= *preds
; i
; i
= i
->ep_next
)
1646 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1647 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1648 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1649 || i
->ep_predictor
== PRED_LOOP_EXIT
1650 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1651 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1656 /* Predict branch probability of BB when BB contains a branch that compares
1657 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1658 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1661 for (int i = 0; i < bound; i++) {
1668 In this loop, we will predict the branch inside the loop to be taken. */
1671 predict_iv_comparison (class loop
*loop
, basic_block bb
,
1672 tree loop_bound_var
,
1673 tree loop_iv_base_var
,
1674 enum tree_code loop_bound_code
,
1675 int loop_bound_step
)
1678 tree compare_var
, compare_base
;
1679 enum tree_code compare_code
;
1680 tree compare_step_var
;
1684 if (predicted_by_loop_heuristics_p (bb
))
1687 stmt
= last_stmt (bb
);
1688 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1690 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1697 /* Find the taken edge. */
1698 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1699 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1702 /* When comparing an IV to a loop invariant, NE is more likely to be
1703 taken while EQ is more likely to be not-taken. */
1704 if (compare_code
== NE_EXPR
)
1706 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1709 else if (compare_code
== EQ_EXPR
)
1711 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1715 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1718 /* If loop bound, base and compare bound are all constants, we can
1719 calculate the probability directly. */
1720 if (tree_fits_shwi_p (loop_bound_var
)
1721 && tree_fits_shwi_p (compare_var
)
1722 && tree_fits_shwi_p (compare_base
))
1725 wi::overflow_type overflow
;
1726 bool overall_overflow
= false;
1727 widest_int compare_count
, tem
;
1729 /* (loop_bound - base) / compare_step */
1730 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1731 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1732 overall_overflow
|= overflow
;
1733 widest_int loop_count
= wi::div_trunc (tem
,
1734 wi::to_widest (compare_step_var
),
1736 overall_overflow
|= overflow
;
1738 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1739 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1741 /* (loop_bound - compare_bound) / compare_step */
1742 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1743 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1744 overall_overflow
|= overflow
;
1745 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1747 overall_overflow
|= overflow
;
1751 /* (compare_bound - base) / compare_step */
1752 tem
= wi::sub (wi::to_widest (compare_var
),
1753 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1754 overall_overflow
|= overflow
;
1755 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1757 overall_overflow
|= overflow
;
1759 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1761 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1763 if (wi::neg_p (compare_count
))
1765 if (wi::neg_p (loop_count
))
1767 if (loop_count
== 0)
1769 else if (wi::cmps (compare_count
, loop_count
) == 1)
1770 probability
= REG_BR_PROB_BASE
;
1773 tem
= compare_count
* REG_BR_PROB_BASE
;
1774 tem
= wi::udiv_trunc (tem
, loop_count
);
1775 probability
= tem
.to_uhwi ();
1778 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1779 if (!overall_overflow
)
1780 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1785 if (expr_coherent_p (loop_bound_var
, compare_var
))
1787 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1788 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1789 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1790 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1791 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1792 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1793 else if (loop_bound_code
== NE_EXPR
)
1795 /* If the loop backedge condition is "(i != bound)", we do
1796 the comparison based on the step of IV:
1797 * step < 0 : backedge condition is like (i > bound)
1798 * step > 0 : backedge condition is like (i < bound) */
1799 gcc_assert (loop_bound_step
!= 0);
1800 if (loop_bound_step
> 0
1801 && (compare_code
== LT_EXPR
1802 || compare_code
== LE_EXPR
))
1803 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1804 else if (loop_bound_step
< 0
1805 && (compare_code
== GT_EXPR
1806 || compare_code
== GE_EXPR
))
1807 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1809 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1812 /* The branch is predicted not-taken if loop_bound_code is
1813 opposite with compare_code. */
1814 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1816 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1819 for (i = s; i < h; i++)
1821 The branch should be predicted taken. */
1822 if (loop_bound_step
> 0
1823 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1824 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1825 else if (loop_bound_step
< 0
1826 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1827 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1829 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1833 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1834 exits are resulted from short-circuit conditions that will generate an
1837 if (foo() || global > 10)
1840 This will be translated into:
1845 if foo() goto BB6 else goto BB5
1847 if global > 10 goto BB6 else goto BB7
1851 iftmp = (PHI 0(BB5), 1(BB6))
1852 if iftmp == 1 goto BB8 else goto BB3
1854 outside of the loop...
1856 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1857 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1858 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1859 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1862 predict_extra_loop_exits (class loop
*loop
, edge exit_edge
)
1865 bool check_value_one
;
1866 gimple
*lhs_def_stmt
;
1868 tree cmp_rhs
, cmp_lhs
;
1872 last
= last_stmt (exit_edge
->src
);
1875 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1879 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1880 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1881 if (!TREE_CONSTANT (cmp_rhs
)
1882 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1884 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1887 /* If check_value_one is true, only the phi_args with value '1' will lead
1888 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1890 check_value_one
= (((integer_onep (cmp_rhs
))
1891 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1892 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1894 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1898 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1902 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1906 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1907 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1909 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1911 if ((check_value_one
^ integer_onep (val
)) == 1)
1913 if (EDGE_COUNT (e
->src
->succs
) != 1)
1915 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
,
1920 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1921 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
,
1927 /* Predict edge probabilities by exploiting loop structure. */
1930 predict_loops (void)
1933 hash_set
<class loop
*> with_recursion(10);
1935 FOR_EACH_BB_FN (bb
, cfun
)
1937 gimple_stmt_iterator gsi
;
1940 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1941 if (is_gimple_call (gsi_stmt (gsi
))
1942 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1943 && recursive_call_p (current_function_decl
, decl
))
1945 class loop
*loop
= bb
->loop_father
;
1946 while (loop
&& !with_recursion
.add (loop
))
1947 loop
= loop_outer (loop
);
1951 /* Try to predict out blocks in a loop that are not part of a
1953 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
1955 basic_block bb
, *bbs
;
1956 unsigned j
, n_exits
= 0;
1957 class tree_niter_desc niter_desc
;
1959 class nb_iter_bound
*nb_iter
;
1960 enum tree_code loop_bound_code
= ERROR_MARK
;
1961 tree loop_bound_step
= NULL
;
1962 tree loop_bound_var
= NULL
;
1963 tree loop_iv_base
= NULL
;
1965 bool recursion
= with_recursion
.contains (loop
);
1967 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
1968 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1969 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1974 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1975 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1976 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1977 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1978 && max_loop_iterations_int (loop
) >= 0)
1981 "Loop %d iterates at most %i times.\n", loop
->num
,
1982 (int)max_loop_iterations_int (loop
));
1984 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1985 && likely_max_loop_iterations_int (loop
) >= 0)
1987 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1988 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1991 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1994 HOST_WIDE_INT nitercst
;
1995 int max
= param_max_predicted_iterations
;
1997 enum br_predictor predictor
;
2000 if (unlikely_executed_edge_p (ex
)
2001 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
2003 /* Loop heuristics do not expect exit conditional to be inside
2004 inner loop. We predict from innermost to outermost loop. */
2005 if (predicted_by_loop_heuristics_p (ex
->src
))
2007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2008 fprintf (dump_file
, "Skipping exit %i->%i because "
2009 "it is already predicted.\n",
2010 ex
->src
->index
, ex
->dest
->index
);
2013 predict_extra_loop_exits (loop
, ex
);
2015 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
2016 niter
= niter_desc
.niter
;
2017 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
2018 niter
= loop_niter_by_eval (loop
, ex
);
2019 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
2020 && TREE_CODE (niter
) == INTEGER_CST
)
2022 fprintf (dump_file
, "Exit %i->%i %d iterates ",
2023 ex
->src
->index
, ex
->dest
->index
,
2025 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
2026 fprintf (dump_file
, " times.\n");
2029 if (TREE_CODE (niter
) == INTEGER_CST
)
2031 if (tree_fits_uhwi_p (niter
)
2033 && compare_tree_int (niter
, max
- 1) == -1)
2034 nitercst
= tree_to_uhwi (niter
) + 1;
2037 predictor
= PRED_LOOP_ITERATIONS
;
2039 /* If we have just one exit and we can derive some information about
2040 the number of iterations of the loop from the statements inside
2041 the loop, use it to predict this exit. */
2042 else if (n_exits
== 1
2043 && estimated_stmt_executions (loop
, &nit
))
2045 if (wi::gtu_p (nit
, max
))
2048 nitercst
= nit
.to_shwi ();
2049 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
2051 /* If we have likely upper bound, trust it for very small iteration
2052 counts. Such loops would otherwise get mispredicted by standard
2053 LOOP_EXIT heuristics. */
2054 else if (n_exits
== 1
2055 && likely_max_stmt_executions (loop
, &nit
)
2057 RDIV (REG_BR_PROB_BASE
,
2061 ? PRED_LOOP_EXIT_WITH_RECURSION
2062 : PRED_LOOP_EXIT
].hitrate
)))
2064 nitercst
= nit
.to_shwi ();
2065 predictor
= PRED_LOOP_ITERATIONS_MAX
;
2069 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2070 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
2071 ex
->src
->index
, ex
->dest
->index
);
2075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2076 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
2077 (int)nitercst
, predictor_info
[predictor
].name
);
2078 /* If the prediction for number of iterations is zero, do not
2079 predict the exit edges. */
2083 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
2084 predict_edge (ex
, predictor
, probability
);
2087 /* Find information about loop bound variables. */
2088 for (nb_iter
= loop
->bounds
; nb_iter
;
2089 nb_iter
= nb_iter
->next
)
2091 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
2093 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
2096 if (!stmt
&& last_stmt (loop
->header
)
2097 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
2098 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2100 is_comparison_with_loop_invariant_p (stmt
, loop
,
2106 bbs
= get_loop_body (loop
);
2108 for (j
= 0; j
< loop
->num_nodes
; j
++)
2115 /* Bypass loop heuristics on continue statement. These
2116 statements construct loops via "non-loop" constructs
2117 in the source language and are better to be handled
2119 if (predicted_by_p (bb
, PRED_CONTINUE
))
2121 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2122 fprintf (dump_file
, "BB %i predicted by continue.\n",
2127 /* If we already used more reliable loop exit predictors, do not
2128 bother with PRED_LOOP_EXIT. */
2129 if (!predicted_by_loop_heuristics_p (bb
))
2131 /* For loop with many exits we don't want to predict all exits
2132 with the pretty large probability, because if all exits are
2133 considered in row, the loop would be predicted to iterate
2134 almost never. The code to divide probability by number of
2135 exits is very rough. It should compute the number of exits
2136 taken in each patch through function (not the overall number
2137 of exits that might be a lot higher for loops with wide switch
2138 statements in them) and compute n-th square root.
2140 We limit the minimal probability by 2% to avoid
2141 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2142 as this was causing regression in perl benchmark containing such
2145 int probability
= ((REG_BR_PROB_BASE
2148 ? PRED_LOOP_EXIT_WITH_RECURSION
2149 : PRED_LOOP_EXIT
].hitrate
)
2151 if (probability
< HITRATE (2))
2152 probability
= HITRATE (2);
2153 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2154 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2155 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2157 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2159 "Predicting exit %i->%i with prob %i.\n",
2160 e
->src
->index
, e
->dest
->index
, probability
);
2162 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2163 : PRED_LOOP_EXIT
, probability
);
2167 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2169 tree_to_shwi (loop_bound_step
));
2172 /* In the following code
2177 guess that cond is unlikely. */
2178 if (loop_outer (loop
)->num
)
2180 basic_block bb
= NULL
;
2181 edge preheader_edge
= loop_preheader_edge (loop
);
2183 if (single_pred_p (preheader_edge
->src
)
2184 && single_succ_p (preheader_edge
->src
))
2185 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2187 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2188 /* Pattern match fortran loop preheader:
2189 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2190 _17 = (logical(kind=4)) _16;
2196 Loop guard branch prediction says nothing about duplicated loop
2197 headers produced by fortran frontend and in this case we want
2198 to predict paths leading to this preheader. */
2201 && gimple_code (stmt
) == GIMPLE_COND
2202 && gimple_cond_code (stmt
) == NE_EXPR
2203 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2204 && integer_zerop (gimple_cond_rhs (stmt
)))
2206 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2207 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2208 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt
))
2209 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2210 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2211 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2212 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2213 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2214 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2215 == PRED_FORTRAN_LOOP_PREHEADER
)
2216 bb
= preheader_edge
->src
;
2220 if (!dominated_by_p (CDI_DOMINATORS
,
2221 loop_outer (loop
)->latch
, loop
->header
))
2222 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2224 ? PRED_LOOP_GUARD_WITH_RECURSION
2231 if (!dominated_by_p (CDI_DOMINATORS
,
2232 loop_outer (loop
)->latch
, bb
))
2233 predict_paths_leading_to (bb
,
2235 ? PRED_LOOP_GUARD_WITH_RECURSION
2242 /* Free basic blocks from get_loop_body. */
2247 /* Attempt to predict probabilities of BB outgoing edges using local
2250 bb_estimate_probability_locally (basic_block bb
)
2252 rtx_insn
*last_insn
= BB_END (bb
);
2255 if (! can_predict_insn_p (last_insn
))
2257 cond
= get_condition (last_insn
, NULL
, false, false);
2261 /* Try "pointer heuristic."
2262 A comparison ptr == 0 is predicted as false.
2263 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2264 if (COMPARISON_P (cond
)
2265 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2266 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2268 if (GET_CODE (cond
) == EQ
)
2269 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2270 else if (GET_CODE (cond
) == NE
)
2271 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2275 /* Try "opcode heuristic."
2276 EQ tests are usually false and NE tests are usually true. Also,
2277 most quantities are positive, so we can make the appropriate guesses
2278 about signed comparisons against zero. */
2279 switch (GET_CODE (cond
))
2282 /* Unconditional branch. */
2283 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2284 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2289 /* Floating point comparisons appears to behave in a very
2290 unpredictable way because of special role of = tests in
2292 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2294 /* Comparisons with 0 are often used for booleans and there is
2295 nothing useful to predict about them. */
2296 else if (XEXP (cond
, 1) == const0_rtx
2297 || XEXP (cond
, 0) == const0_rtx
)
2300 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2305 /* Floating point comparisons appears to behave in a very
2306 unpredictable way because of special role of = tests in
2308 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2310 /* Comparisons with 0 are often used for booleans and there is
2311 nothing useful to predict about them. */
2312 else if (XEXP (cond
, 1) == const0_rtx
2313 || XEXP (cond
, 0) == const0_rtx
)
2316 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2320 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2324 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2329 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2330 || XEXP (cond
, 1) == constm1_rtx
)
2331 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2336 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2337 || XEXP (cond
, 1) == constm1_rtx
)
2338 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2346 /* Set edge->probability for each successor edge of BB. */
2348 guess_outgoing_edge_probabilities (basic_block bb
)
2350 bb_estimate_probability_locally (bb
);
2351 combine_predictions_for_insn (BB_END (bb
), bb
);
2354 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
,
2355 HOST_WIDE_INT
*probability
);
2357 /* Helper function for expr_expected_value. */
2360 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2361 tree op1
, bitmap visited
, enum br_predictor
*predictor
,
2362 HOST_WIDE_INT
*probability
)
2366 /* Reset returned probability value. */
2368 *predictor
= PRED_UNCONDITIONAL
;
2370 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2372 if (TREE_CONSTANT (op0
))
2375 if (code
== IMAGPART_EXPR
)
2377 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2379 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2380 if (is_gimple_call (def
)
2381 && gimple_call_internal_p (def
)
2382 && (gimple_call_internal_fn (def
)
2383 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2385 /* Assume that any given atomic operation has low contention,
2386 and thus the compare-and-swap operation succeeds. */
2387 *predictor
= PRED_COMPARE_AND_SWAP
;
2388 return build_one_cst (TREE_TYPE (op0
));
2393 if (code
!= SSA_NAME
)
2396 def
= SSA_NAME_DEF_STMT (op0
);
2398 /* If we were already here, break the infinite cycle. */
2399 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2402 if (gimple_code (def
) == GIMPLE_PHI
)
2404 /* All the arguments of the PHI node must have the same constant
2406 int i
, n
= gimple_phi_num_args (def
);
2407 tree val
= NULL
, new_val
;
2409 for (i
= 0; i
< n
; i
++)
2411 tree arg
= PHI_ARG_DEF (def
, i
);
2412 enum br_predictor predictor2
;
2414 /* If this PHI has itself as an argument, we cannot
2415 determine the string length of this argument. However,
2416 if we can find an expected constant value for the other
2417 PHI args then we can still be sure that this is
2418 likely a constant. So be optimistic and just
2419 continue with the next argument. */
2420 if (arg
== PHI_RESULT (def
))
2423 HOST_WIDE_INT probability2
;
2424 new_val
= expr_expected_value (arg
, visited
, &predictor2
,
2427 /* It is difficult to combine value predictors. Simply assume
2428 that later predictor is weaker and take its prediction. */
2429 if (*predictor
< predictor2
)
2431 *predictor
= predictor2
;
2432 *probability
= probability2
;
2438 else if (!operand_equal_p (val
, new_val
, false))
2443 if (is_gimple_assign (def
))
2445 if (gimple_assign_lhs (def
) != op0
)
2448 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2449 gimple_assign_rhs1 (def
),
2450 gimple_assign_rhs_code (def
),
2451 gimple_assign_rhs2 (def
),
2452 visited
, predictor
, probability
);
2455 if (is_gimple_call (def
))
2457 tree decl
= gimple_call_fndecl (def
);
2460 if (gimple_call_internal_p (def
)
2461 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2463 gcc_assert (gimple_call_num_args (def
) == 3);
2464 tree val
= gimple_call_arg (def
, 0);
2465 if (TREE_CONSTANT (val
))
2467 tree val2
= gimple_call_arg (def
, 2);
2468 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2469 && tree_fits_uhwi_p (val2
)
2470 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2471 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2472 if (*predictor
== PRED_BUILTIN_EXPECT
)
2474 = HITRATE (param_builtin_expect_probability
);
2475 return gimple_call_arg (def
, 1);
2480 if (DECL_IS_MALLOC (decl
) || DECL_IS_OPERATOR_NEW_P (decl
))
2483 *predictor
= PRED_MALLOC_NONNULL
;
2484 return boolean_true_node
;
2487 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2488 switch (DECL_FUNCTION_CODE (decl
))
2490 case BUILT_IN_EXPECT
:
2493 if (gimple_call_num_args (def
) != 2)
2495 val
= gimple_call_arg (def
, 0);
2496 if (TREE_CONSTANT (val
))
2498 *predictor
= PRED_BUILTIN_EXPECT
;
2500 = HITRATE (param_builtin_expect_probability
);
2501 return gimple_call_arg (def
, 1);
2503 case BUILT_IN_EXPECT_WITH_PROBABILITY
:
2506 if (gimple_call_num_args (def
) != 3)
2508 val
= gimple_call_arg (def
, 0);
2509 if (TREE_CONSTANT (val
))
2511 /* Compute final probability as:
2512 probability * REG_BR_PROB_BASE. */
2513 tree prob
= gimple_call_arg (def
, 2);
2514 tree t
= TREE_TYPE (prob
);
2515 tree base
= build_int_cst (integer_type_node
,
2517 base
= build_real_from_int_cst (t
, base
);
2518 tree r
= fold_build2_initializer_loc (UNKNOWN_LOCATION
,
2519 MULT_EXPR
, t
, prob
, base
);
2520 if (TREE_CODE (r
) != REAL_CST
)
2522 error_at (gimple_location (def
),
2523 "probability %qE must be "
2524 "constant floating-point expression", prob
);
2528 = real_to_integer (TREE_REAL_CST_PTR (r
));
2529 if (probi
>= 0 && probi
<= REG_BR_PROB_BASE
)
2531 *predictor
= PRED_BUILTIN_EXPECT_WITH_PROBABILITY
;
2532 *probability
= probi
;
2535 error_at (gimple_location (def
),
2536 "probability %qE is outside "
2537 "the range [0.0, 1.0]", prob
);
2539 return gimple_call_arg (def
, 1);
2542 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2543 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2544 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2545 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2546 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2547 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2548 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2549 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2550 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2551 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2552 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2553 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2554 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2555 /* Assume that any given atomic operation has low contention,
2556 and thus the compare-and-swap operation succeeds. */
2557 *predictor
= PRED_COMPARE_AND_SWAP
;
2558 return boolean_true_node
;
2559 case BUILT_IN_REALLOC
:
2561 *predictor
= PRED_MALLOC_NONNULL
;
2562 return boolean_true_node
;
2571 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2574 enum br_predictor predictor2
;
2575 HOST_WIDE_INT probability2
;
2576 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2579 op1
= expr_expected_value (op1
, visited
, &predictor2
, &probability2
);
2582 res
= fold_build2 (code
, type
, op0
, op1
);
2583 if (TREE_CODE (res
) == INTEGER_CST
2584 && TREE_CODE (op0
) == INTEGER_CST
2585 && TREE_CODE (op1
) == INTEGER_CST
)
2587 /* Combine binary predictions. */
2588 if (*probability
!= -1 || probability2
!= -1)
2590 HOST_WIDE_INT p1
= get_predictor_value (*predictor
, *probability
);
2591 HOST_WIDE_INT p2
= get_predictor_value (predictor2
, probability2
);
2592 *probability
= RDIV (p1
* p2
, REG_BR_PROB_BASE
);
2595 if (*predictor
< predictor2
)
2596 *predictor
= predictor2
;
2602 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2605 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2608 res
= fold_build1 (code
, type
, op0
);
2609 if (TREE_CONSTANT (res
))
2616 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2617 The function is used by builtin_expect branch predictor so the evidence
2618 must come from this construct and additional possible constant folding.
2620 We may want to implement more involved value guess (such as value range
2621 propagation based prediction), but such tricks shall go to new
2625 expr_expected_value (tree expr
, bitmap visited
,
2626 enum br_predictor
*predictor
,
2627 HOST_WIDE_INT
*probability
)
2629 enum tree_code code
;
2632 if (TREE_CONSTANT (expr
))
2634 *predictor
= PRED_UNCONDITIONAL
;
2639 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2640 return expr_expected_value_1 (TREE_TYPE (expr
),
2641 op0
, code
, op1
, visited
, predictor
,
2646 /* Return probability of a PREDICTOR. If the predictor has variable
2647 probability return passed PROBABILITY. */
2649 static HOST_WIDE_INT
2650 get_predictor_value (br_predictor predictor
, HOST_WIDE_INT probability
)
2654 case PRED_BUILTIN_EXPECT
:
2655 case PRED_BUILTIN_EXPECT_WITH_PROBABILITY
:
2656 gcc_assert (probability
!= -1);
2659 gcc_assert (probability
== -1);
2660 return predictor_info
[(int) predictor
].hitrate
;
2664 /* Predict using opcode of the last statement in basic block. */
2666 tree_predict_by_opcode (basic_block bb
)
2668 gimple
*stmt
= last_stmt (bb
);
2675 enum br_predictor predictor
;
2676 HOST_WIDE_INT probability
;
2681 if (gswitch
*sw
= dyn_cast
<gswitch
*> (stmt
))
2683 tree index
= gimple_switch_index (sw
);
2684 tree val
= expr_expected_value (index
, auto_bitmap (),
2685 &predictor
, &probability
);
2686 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2688 edge e
= find_taken_edge_switch_expr (sw
, val
);
2689 if (predictor
== PRED_BUILTIN_EXPECT
)
2691 int percent
= param_builtin_expect_probability
;
2692 gcc_assert (percent
>= 0 && percent
<= 100);
2693 predict_edge (e
, PRED_BUILTIN_EXPECT
,
2697 predict_edge_def (e
, predictor
, TAKEN
);
2701 if (gimple_code (stmt
) != GIMPLE_COND
)
2703 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2704 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2706 op0
= gimple_cond_lhs (stmt
);
2707 op1
= gimple_cond_rhs (stmt
);
2708 cmp
= gimple_cond_code (stmt
);
2709 type
= TREE_TYPE (op0
);
2710 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2711 &predictor
, &probability
);
2712 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2714 HOST_WIDE_INT prob
= get_predictor_value (predictor
, probability
);
2715 if (integer_zerop (val
))
2716 prob
= REG_BR_PROB_BASE
- prob
;
2717 predict_edge (then_edge
, predictor
, prob
);
2719 /* Try "pointer heuristic."
2720 A comparison ptr == 0 is predicted as false.
2721 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2722 if (POINTER_TYPE_P (type
))
2725 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2726 else if (cmp
== NE_EXPR
)
2727 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2731 /* Try "opcode heuristic."
2732 EQ tests are usually false and NE tests are usually true. Also,
2733 most quantities are positive, so we can make the appropriate guesses
2734 about signed comparisons against zero. */
2739 /* Floating point comparisons appears to behave in a very
2740 unpredictable way because of special role of = tests in
2742 if (FLOAT_TYPE_P (type
))
2744 /* Comparisons with 0 are often used for booleans and there is
2745 nothing useful to predict about them. */
2746 else if (integer_zerop (op0
) || integer_zerop (op1
))
2749 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2754 /* Floating point comparisons appears to behave in a very
2755 unpredictable way because of special role of = tests in
2757 if (FLOAT_TYPE_P (type
))
2759 /* Comparisons with 0 are often used for booleans and there is
2760 nothing useful to predict about them. */
2761 else if (integer_zerop (op0
)
2762 || integer_zerop (op1
))
2765 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2769 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2772 case UNORDERED_EXPR
:
2773 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2778 if (integer_zerop (op1
)
2779 || integer_onep (op1
)
2780 || integer_all_onesp (op1
)
2783 || real_minus_onep (op1
))
2784 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2789 if (integer_zerop (op1
)
2790 || integer_onep (op1
)
2791 || integer_all_onesp (op1
)
2794 || real_minus_onep (op1
))
2795 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2803 /* Returns TRUE if the STMT is exit(0) like statement. */
2806 is_exit_with_zero_arg (const gimple
*stmt
)
2808 /* This is not exit, _exit or _Exit. */
2809 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2810 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2811 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2814 /* Argument is an interger zero. */
2815 return integer_zerop (gimple_call_arg (stmt
, 0));
2818 /* Try to guess whether the value of return means error code. */
2820 static enum br_predictor
2821 return_prediction (tree val
, enum prediction
*prediction
)
2825 return PRED_NO_PREDICTION
;
2826 /* Different heuristics for pointers and scalars. */
2827 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2829 /* NULL is usually not returned. */
2830 if (integer_zerop (val
))
2832 *prediction
= NOT_TAKEN
;
2833 return PRED_NULL_RETURN
;
2836 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2838 /* Negative return values are often used to indicate
2840 if (TREE_CODE (val
) == INTEGER_CST
2841 && tree_int_cst_sgn (val
) < 0)
2843 *prediction
= NOT_TAKEN
;
2844 return PRED_NEGATIVE_RETURN
;
2846 /* Constant return values seems to be commonly taken.
2847 Zero/one often represent booleans so exclude them from the
2849 if (TREE_CONSTANT (val
)
2850 && (!integer_zerop (val
) && !integer_onep (val
)))
2852 *prediction
= NOT_TAKEN
;
2853 return PRED_CONST_RETURN
;
2856 return PRED_NO_PREDICTION
;
2859 /* Return zero if phi result could have values other than -1, 0 or 1,
2860 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2861 values are used or likely. */
2864 zero_one_minusone (gphi
*phi
, int limit
)
2866 int phi_num_args
= gimple_phi_num_args (phi
);
2868 for (int i
= 0; i
< phi_num_args
; i
++)
2870 tree t
= PHI_ARG_DEF (phi
, i
);
2871 if (TREE_CODE (t
) != INTEGER_CST
)
2873 wide_int w
= wi::to_wide (t
);
2883 for (int i
= 0; i
< phi_num_args
; i
++)
2885 tree t
= PHI_ARG_DEF (phi
, i
);
2886 if (TREE_CODE (t
) == INTEGER_CST
)
2888 if (TREE_CODE (t
) != SSA_NAME
)
2890 gimple
*g
= SSA_NAME_DEF_STMT (t
);
2891 if (gimple_code (g
) == GIMPLE_PHI
&& limit
> 0)
2892 if (int r
= zero_one_minusone (as_a
<gphi
*> (g
), limit
- 1))
2897 if (!is_gimple_assign (g
))
2899 if (gimple_assign_cast_p (g
))
2901 tree rhs1
= gimple_assign_rhs1 (g
);
2902 if (TREE_CODE (rhs1
) != SSA_NAME
2903 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
2904 || TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2905 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2910 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g
)) != tcc_comparison
)
2917 /* Find the basic block with return expression and look up for possible
2918 return value trying to apply RETURN_PREDICTION heuristics. */
2920 apply_return_prediction (void)
2922 greturn
*return_stmt
= NULL
;
2926 int phi_num_args
, i
;
2927 enum br_predictor pred
;
2928 enum prediction direction
;
2931 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2933 gimple
*last
= last_stmt (e
->src
);
2935 && gimple_code (last
) == GIMPLE_RETURN
)
2937 return_stmt
= as_a
<greturn
*> (last
);
2943 return_val
= gimple_return_retval (return_stmt
);
2946 if (TREE_CODE (return_val
) != SSA_NAME
2947 || !SSA_NAME_DEF_STMT (return_val
)
2948 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2950 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2951 phi_num_args
= gimple_phi_num_args (phi
);
2952 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2954 /* Avoid the case where the function returns -1, 0 and 1 values and
2955 nothing else. Those could be qsort etc. comparison functions
2956 where the negative return isn't less probable than positive.
2957 For this require that the function returns at least -1 or 1
2958 or -1 and a boolean value or comparison result, so that functions
2959 returning just -1 and 0 are treated as if -1 represents error value. */
2960 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val
))
2961 && !TYPE_UNSIGNED (TREE_TYPE (return_val
))
2962 && TYPE_PRECISION (TREE_TYPE (return_val
)) > 1)
2963 if (int r
= zero_one_minusone (phi
, 3))
2964 if ((r
& (1 | 4)) == (1 | 4))
2967 /* Avoid the degenerate case where all return values form the function
2968 belongs to same category (ie they are all positive constants)
2969 so we can hardly say something about them. */
2970 for (i
= 1; i
< phi_num_args
; i
++)
2971 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2973 if (i
!= phi_num_args
)
2974 for (i
= 0; i
< phi_num_args
; i
++)
2976 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2977 if (pred
!= PRED_NO_PREDICTION
)
2978 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2983 /* Look for basic block that contains unlikely to happen events
2984 (such as noreturn calls) and mark all paths leading to execution
2985 of this basic blocks as unlikely. */
2988 tree_bb_level_predictions (void)
2991 bool has_return_edges
= false;
2995 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2996 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2998 has_return_edges
= true;
3002 apply_return_prediction ();
3004 FOR_EACH_BB_FN (bb
, cfun
)
3006 gimple_stmt_iterator gsi
;
3008 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3010 gimple
*stmt
= gsi_stmt (gsi
);
3013 if (is_gimple_call (stmt
))
3015 if (gimple_call_noreturn_p (stmt
)
3017 && !is_exit_with_zero_arg (stmt
))
3018 predict_paths_leading_to (bb
, PRED_NORETURN
,
3020 decl
= gimple_call_fndecl (stmt
);
3022 && lookup_attribute ("cold",
3023 DECL_ATTRIBUTES (decl
)))
3024 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
3026 if (decl
&& recursive_call_p (current_function_decl
, decl
))
3027 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
3030 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3032 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
3033 gimple_predict_outcome (stmt
));
3034 /* Keep GIMPLE_PREDICT around so early inlining will propagate
3035 hints to callers. */
3041 /* Callback for hash_map::traverse, asserts that the pointer map is
3045 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
3048 gcc_assert (!value
);
3052 /* Predict branch probabilities and estimate profile for basic block BB.
3053 When LOCAL_ONLY is set do not use any global properties of CFG. */
3056 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
3061 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3063 /* Look for block we are guarding (ie we dominate it,
3064 but it doesn't postdominate us). */
3065 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
3067 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
3068 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
3070 gimple_stmt_iterator bi
;
3072 /* The call heuristic claims that a guarded function call
3073 is improbable. This is because such calls are often used
3074 to signal exceptional situations such as printing error
3076 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
3079 gimple
*stmt
= gsi_stmt (bi
);
3080 if (is_gimple_call (stmt
)
3081 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
3082 /* Constant and pure calls are hardly used to signalize
3083 something exceptional. */
3084 && gimple_has_side_effects (stmt
))
3086 if (gimple_call_fndecl (stmt
))
3087 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
3088 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
3089 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
3091 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
3097 tree_predict_by_opcode (bb
);
3100 /* Predict branch probabilities and estimate profile of the tree CFG.
3101 This function can be called from the loop optimizers to recompute
3102 the profile information.
3103 If DRY_RUN is set, do not modify CFG and only produce dump files. */
3106 tree_estimate_probability (bool dry_run
)
3110 connect_infinite_loops_to_exit ();
3111 /* We use loop_niter_by_eval, which requires that the loops have
3113 create_preheaders (CP_SIMPLE_PREHEADERS
);
3114 calculate_dominance_info (CDI_POST_DOMINATORS
);
3115 /* Decide which edges are known to be unlikely. This improves later
3116 branch prediction. */
3117 determine_unlikely_bbs ();
3119 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3120 tree_bb_level_predictions ();
3121 record_loop_exits ();
3123 if (number_of_loops (cfun
) > 1)
3126 FOR_EACH_BB_FN (bb
, cfun
)
3127 tree_estimate_probability_bb (bb
, false);
3129 FOR_EACH_BB_FN (bb
, cfun
)
3130 combine_predictions_for_bb (bb
, dry_run
);
3133 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3135 delete bb_predictions
;
3136 bb_predictions
= NULL
;
3139 estimate_bb_frequencies (false);
3140 free_dominance_info (CDI_POST_DOMINATORS
);
3141 remove_fake_exit_edges ();
3144 /* Set edge->probability for each successor edge of BB. */
3146 tree_guess_outgoing_edge_probabilities (basic_block bb
)
3148 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3149 tree_estimate_probability_bb (bb
, true);
3150 combine_predictions_for_bb (bb
, false);
3152 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3153 delete bb_predictions
;
3154 bb_predictions
= NULL
;
3157 /* Filter function predicate that returns true for a edge predicate P
3158 if its edge is equal to DATA. */
3161 not_loop_guard_equal_edge_p (edge_prediction
*p
, void *data
)
3163 return p
->ep_edge
!= (edge
)data
|| p
->ep_predictor
!= PRED_LOOP_GUARD
;
3166 /* Predict edge E with PRED unless it is already predicted by some predictor
3167 considered equivalent. */
3170 maybe_predict_edge (edge e
, enum br_predictor pred
, enum prediction taken
)
3172 if (edge_predicted_by_p (e
, pred
, taken
))
3174 if (pred
== PRED_LOOP_GUARD
3175 && edge_predicted_by_p (e
, PRED_LOOP_GUARD_WITH_RECURSION
, taken
))
3177 /* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD. */
3178 if (pred
== PRED_LOOP_GUARD_WITH_RECURSION
)
3180 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
3182 filter_predictions (preds
, not_loop_guard_equal_edge_p
, e
);
3184 predict_edge_def (e
, pred
, taken
);
3186 /* Predict edges to successors of CUR whose sources are not postdominated by
3187 BB by PRED and recurse to all postdominators. */
3190 predict_paths_for_bb (basic_block cur
, basic_block bb
,
3191 enum br_predictor pred
,
3192 enum prediction taken
,
3193 bitmap visited
, class loop
*in_loop
= NULL
)
3199 /* If we exited the loop or CUR is unconditional in the loop, there is
3202 && (!flow_bb_inside_loop_p (in_loop
, cur
)
3203 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
3206 /* We are looking for all edges forming edge cut induced by
3207 set of all blocks postdominated by BB. */
3208 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
3209 if (e
->src
->index
>= NUM_FIXED_BLOCKS
3210 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
3216 /* Ignore fake edges and eh, we predict them as not taken anyway. */
3217 if (unlikely_executed_edge_p (e
))
3219 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
3221 /* See if there is an edge from e->src that is not abnormal
3222 and does not lead to BB and does not exit the loop. */
3223 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
3225 && !unlikely_executed_edge_p (e2
)
3226 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
3227 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
3233 /* If there is non-abnormal path leaving e->src, predict edge
3234 using predictor. Otherwise we need to look for paths
3237 The second may lead to infinite loop in the case we are predicitng
3238 regions that are only reachable by abnormal edges. We simply
3239 prevent visiting given BB twice. */
3241 maybe_predict_edge (e
, pred
, taken
);
3242 else if (bitmap_set_bit (visited
, e
->src
->index
))
3243 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
3245 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
3247 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
3248 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
3251 /* Sets branch probabilities according to PREDiction and
3255 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
3256 enum prediction taken
, class loop
*in_loop
)
3258 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3261 /* Like predict_paths_leading_to but take edge instead of basic block. */
3264 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
3265 enum prediction taken
, class loop
*in_loop
)
3267 bool has_nonloop_edge
= false;
3271 basic_block bb
= e
->src
;
3272 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
3273 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
3274 && !unlikely_executed_edge_p (e2
)
3275 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
3277 has_nonloop_edge
= true;
3281 if (!has_nonloop_edge
)
3282 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3284 maybe_predict_edge (e
, pred
, taken
);
3287 /* This is used to carry information about basic blocks. It is
3288 attached to the AUX field of the standard CFG block. */
3293 /* Estimated frequency of execution of basic_block. */
3296 /* To keep queue of basic blocks to process. */
3299 /* Number of predecessors we need to visit first. */
3303 /* Similar information for edges. */
3304 class edge_prob_info
3307 /* In case edge is a loopback edge, the probability edge will be reached
3308 in case header is. Estimated number of iterations of the loop can be
3309 then computed as 1 / (1 - back_edge_prob). */
3310 sreal back_edge_prob
;
3311 /* True if the edge is a loopback edge in the natural loop. */
3312 unsigned int back_edge
:1;
3315 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3317 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3319 /* Helper function for estimate_bb_frequencies.
3320 Propagate the frequencies in blocks marked in
3321 TOVISIT, starting in HEAD. */
3324 propagate_freq (basic_block head
, bitmap tovisit
,
3325 sreal max_cyclic_prob
)
3334 /* For each basic block we need to visit count number of his predecessors
3335 we need to visit first. */
3336 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
3341 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3343 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3345 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3347 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3349 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3351 "Irreducible region hit, ignoring edge to %i->%i\n",
3352 e
->src
->index
, bb
->index
);
3354 BLOCK_INFO (bb
)->npredecessors
= count
;
3355 /* When function never returns, we will never process exit block. */
3356 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3357 bb
->count
= profile_count::zero ();
3360 BLOCK_INFO (head
)->frequency
= 1;
3362 for (bb
= head
; bb
; bb
= nextbb
)
3365 sreal cyclic_probability
= 0;
3366 sreal frequency
= 0;
3368 nextbb
= BLOCK_INFO (bb
)->next
;
3369 BLOCK_INFO (bb
)->next
= NULL
;
3371 /* Compute frequency of basic block. */
3375 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3376 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3377 || (e
->flags
& EDGE_DFS_BACK
));
3379 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3380 if (EDGE_INFO (e
)->back_edge
)
3381 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3382 else if (!(e
->flags
& EDGE_DFS_BACK
))
3384 /* FIXME: Graphite is producing edges with no profile. Once
3385 this is fixed, drop this. */
3386 sreal tmp
= e
->probability
.initialized_p () ?
3387 e
->probability
.to_sreal () : 0;
3388 frequency
+= tmp
* BLOCK_INFO (e
->src
)->frequency
;
3391 if (cyclic_probability
== 0)
3393 BLOCK_INFO (bb
)->frequency
= frequency
;
3397 if (cyclic_probability
> max_cyclic_prob
)
3401 "cyclic probability of bb %i is %f (capped to %f)"
3402 "; turning freq %f",
3403 bb
->index
, cyclic_probability
.to_double (),
3404 max_cyclic_prob
.to_double (),
3405 frequency
.to_double ());
3407 cyclic_probability
= max_cyclic_prob
;
3411 "cyclic probability of bb %i is %f; turning freq %f",
3412 bb
->index
, cyclic_probability
.to_double (),
3413 frequency
.to_double ());
3415 BLOCK_INFO (bb
)->frequency
= frequency
3416 / (sreal (1) - cyclic_probability
);
3418 fprintf (dump_file
, " to %f\n",
3419 BLOCK_INFO (bb
)->frequency
.to_double ());
3423 bitmap_clear_bit (tovisit
, bb
->index
);
3425 e
= find_edge (bb
, head
);
3428 /* FIXME: Graphite is producing edges with no profile. Once
3429 this is fixed, drop this. */
3430 sreal tmp
= e
->probability
.initialized_p () ?
3431 e
->probability
.to_sreal () : 0;
3432 EDGE_INFO (e
)->back_edge_prob
= tmp
* BLOCK_INFO (bb
)->frequency
;
3435 /* Propagate to successor blocks. */
3436 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3437 if (!(e
->flags
& EDGE_DFS_BACK
)
3438 && BLOCK_INFO (e
->dest
)->npredecessors
)
3440 BLOCK_INFO (e
->dest
)->npredecessors
--;
3441 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3446 BLOCK_INFO (last
)->next
= e
->dest
;
3454 /* Estimate frequencies in loops at same nest level. */
3457 estimate_loops_at_level (class loop
*first_loop
, sreal max_cyclic_prob
)
3461 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3466 auto_bitmap tovisit
;
3468 estimate_loops_at_level (loop
->inner
, max_cyclic_prob
);
3470 /* Find current loop back edge and mark it. */
3471 e
= loop_latch_edge (loop
);
3472 EDGE_INFO (e
)->back_edge
= 1;
3474 bbs
= get_loop_body (loop
);
3475 for (i
= 0; i
< loop
->num_nodes
; i
++)
3476 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3478 propagate_freq (loop
->header
, tovisit
, max_cyclic_prob
);
3482 /* Propagates frequencies through structure of loops. */
3485 estimate_loops (void)
3487 auto_bitmap tovisit
;
3489 sreal max_cyclic_prob
= (sreal
)1
3490 - (sreal
)1 / (param_max_predicted_iterations
+ 1);
3492 /* Start by estimating the frequencies in the loops. */
3493 if (number_of_loops (cfun
) > 1)
3494 estimate_loops_at_level (current_loops
->tree_root
->inner
, max_cyclic_prob
);
3496 /* Now propagate the frequencies through all the blocks. */
3497 FOR_ALL_BB_FN (bb
, cfun
)
3499 bitmap_set_bit (tovisit
, bb
->index
);
3501 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
, max_cyclic_prob
);
3504 /* Drop the profile for NODE to guessed, and update its frequency based on
3505 whether it is expected to be hot given the CALL_COUNT. */
3508 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3510 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3511 /* In the case where this was called by another function with a
3512 dropped profile, call_count will be 0. Since there are no
3513 non-zero call counts to this function, we don't know for sure
3514 whether it is hot, and therefore it will be marked normal below. */
3515 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3519 "Dropping 0 profile for %s. %s based on calls.\n",
3521 hot
? "Function is hot" : "Function is normal");
3522 /* We only expect to miss profiles for functions that are reached
3523 via non-zero call edges in cases where the function may have
3524 been linked from another module or library (COMDATs and extern
3525 templates). See the comments below for handle_missing_profiles.
3526 Also, only warn in cases where the missing counts exceed the
3527 number of training runs. In certain cases with an execv followed
3528 by a no-return call the profile for the no-return call is not
3529 dumped and there can be a mismatch. */
3530 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3531 && call_count
> profile_info
->runs
)
3533 if (flag_profile_correction
)
3537 "Missing counts for called function %s\n",
3538 node
->dump_name ());
3541 warning (0, "Missing counts for called function %s",
3542 node
->dump_name ());
3546 if (opt_for_fn (node
->decl
, flag_guess_branch_prob
))
3549 = !ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
.nonzero_p ();
3550 FOR_ALL_BB_FN (bb
, fn
)
3551 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3552 bb
->count
= bb
->count
.guessed_local ();
3553 fn
->cfg
->count_max
= fn
->cfg
->count_max
.guessed_local ();
3557 FOR_ALL_BB_FN (bb
, fn
)
3558 bb
->count
= profile_count::uninitialized ();
3559 fn
->cfg
->count_max
= profile_count::uninitialized ();
3562 struct cgraph_edge
*e
;
3563 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3564 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3565 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3566 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3567 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
;
3569 profile_status_for_fn (fn
)
3570 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3572 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3575 /* In the case of COMDAT routines, multiple object files will contain the same
3576 function and the linker will select one for the binary. In that case
3577 all the other copies from the profile instrument binary will be missing
3578 profile counts. Look for cases where this happened, due to non-zero
3579 call counts going to 0-count functions, and drop the profile to guessed
3580 so that we can use the estimated probabilities and avoid optimizing only
3583 The other case where the profile may be missing is when the routine
3584 is not going to be emitted to the object file, e.g. for "extern template"
3585 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3586 all other cases of non-zero calls to 0-count functions. */
3589 handle_missing_profiles (void)
3591 const int unlikely_frac
= param_unlikely_bb_count_fraction
;
3592 struct cgraph_node
*node
;
3593 auto_vec
<struct cgraph_node
*, 64> worklist
;
3595 /* See if 0 count function has non-0 count callers. In this case we
3596 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3597 FOR_EACH_DEFINED_FUNCTION (node
)
3599 struct cgraph_edge
*e
;
3600 profile_count call_count
= profile_count::zero ();
3601 gcov_type max_tp_first_run
= 0;
3602 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3604 if (node
->count
.ipa ().nonzero_p ())
3606 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3607 if (e
->count
.ipa ().initialized_p () && e
->count
.ipa () > 0)
3609 call_count
= call_count
+ e
->count
.ipa ();
3611 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3612 max_tp_first_run
= e
->caller
->tp_first_run
;
3615 /* If time profile is missing, let assign the maximum that comes from
3616 caller functions. */
3617 if (!node
->tp_first_run
&& max_tp_first_run
)
3618 node
->tp_first_run
= max_tp_first_run
+ 1;
3622 && call_count
* unlikely_frac
>= profile_info
->runs
)
3624 drop_profile (node
, call_count
);
3625 worklist
.safe_push (node
);
3629 /* Propagate the profile dropping to other 0-count COMDATs that are
3630 potentially called by COMDATs we already dropped the profile on. */
3631 while (worklist
.length () > 0)
3633 struct cgraph_edge
*e
;
3635 node
= worklist
.pop ();
3636 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3638 struct cgraph_node
*callee
= e
->callee
;
3639 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3641 if (!(e
->count
.ipa () == profile_count::zero ())
3642 && callee
->count
.ipa ().nonzero_p ())
3644 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3646 && profile_status_for_fn (fn
) == PROFILE_READ
)
3648 drop_profile (node
, profile_count::zero ());
3649 worklist
.safe_push (callee
);
3655 /* Convert counts measured by profile driven feedback to frequencies.
3656 Return nonzero iff there was any nonzero execution count. */
3659 update_max_bb_count (void)
3661 profile_count true_count_max
= profile_count::uninitialized ();
3664 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3665 true_count_max
= true_count_max
.max (bb
->count
);
3667 cfun
->cfg
->count_max
= true_count_max
;
3669 return true_count_max
.ipa ().nonzero_p ();
3672 /* Return true if function is likely to be expensive, so there is no point to
3673 optimize performance of prologue, epilogue or do inlining at the expense
3674 of code size growth. THRESHOLD is the limit of number of instructions
3675 function can execute at average to be still considered not expensive. */
3678 expensive_function_p (int threshold
)
3682 /* If profile was scaled in a way entry block has count 0, then the function
3683 is deifnitly taking a lot of time. */
3684 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3687 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
* threshold
;
3688 profile_count sum
= profile_count::zero ();
3689 FOR_EACH_BB_FN (bb
, cfun
)
3693 if (!bb
->count
.initialized_p ())
3696 fprintf (dump_file
, "Function is considered expensive because"
3697 " count of bb %i is not initialized\n", bb
->index
);
3701 FOR_BB_INSNS (bb
, insn
)
3702 if (active_insn_p (insn
))
3713 /* All basic blocks that are reachable only from unlikely basic blocks are
3717 propagate_unlikely_bbs_forward (void)
3719 auto_vec
<basic_block
, 64> worklist
;
3724 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3726 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3727 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3729 while (worklist
.length () > 0)
3731 bb
= worklist
.pop ();
3732 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3733 if (!(e
->count () == profile_count::zero ())
3734 && !(e
->dest
->count
== profile_count::zero ())
3737 e
->dest
->aux
= (void *)(size_t) 1;
3738 worklist
.safe_push (e
->dest
);
3743 FOR_ALL_BB_FN (bb
, cfun
)
3747 if (!(bb
->count
== profile_count::zero ())
3748 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3750 "Basic block %i is marked unlikely by forward prop\n",
3752 bb
->count
= profile_count::zero ();
3759 /* Determine basic blocks/edges that are known to be unlikely executed and set
3760 their counters to zero.
3761 This is done with first identifying obviously unlikely BBs/edges and then
3762 propagating in both directions. */
3765 determine_unlikely_bbs ()
3768 auto_vec
<basic_block
, 64> worklist
;
3772 FOR_EACH_BB_FN (bb
, cfun
)
3774 if (!(bb
->count
== profile_count::zero ())
3775 && unlikely_executed_bb_p (bb
))
3777 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3778 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3780 bb
->count
= profile_count::zero ();
3783 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3784 if (!(e
->probability
== profile_probability::never ())
3785 && unlikely_executed_edge_p (e
))
3787 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3788 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3789 bb
->index
, e
->dest
->index
);
3790 e
->probability
= profile_probability::never ();
3793 gcc_checking_assert (!bb
->aux
);
3795 propagate_unlikely_bbs_forward ();
3797 auto_vec
<int, 64> nsuccs
;
3798 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
), true);
3799 FOR_ALL_BB_FN (bb
, cfun
)
3800 if (!(bb
->count
== profile_count::zero ())
3801 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3803 nsuccs
[bb
->index
] = 0;
3804 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3805 if (!(e
->probability
== profile_probability::never ())
3806 && !(e
->dest
->count
== profile_count::zero ()))
3807 nsuccs
[bb
->index
]++;
3808 if (!nsuccs
[bb
->index
])
3809 worklist
.safe_push (bb
);
3811 while (worklist
.length () > 0)
3813 bb
= worklist
.pop ();
3814 if (bb
->count
== profile_count::zero ())
3816 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3819 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3820 !gsi_end_p (gsi
); gsi_next (&gsi
))
3821 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3822 /* stmt_can_terminate_bb_p special cases noreturns because it
3823 assumes that fake edges are created. We want to know that
3824 noreturn alone does not imply BB to be unlikely. */
3825 || (is_gimple_call (gsi_stmt (gsi
))
3826 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3834 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3836 "Basic block %i is marked unlikely by backward prop\n",
3838 bb
->count
= profile_count::zero ();
3839 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3840 if (!(e
->probability
== profile_probability::never ()))
3842 if (!(e
->src
->count
== profile_count::zero ()))
3844 gcc_checking_assert (nsuccs
[e
->src
->index
] > 0);
3845 nsuccs
[e
->src
->index
]--;
3846 if (!nsuccs
[e
->src
->index
])
3847 worklist
.safe_push (e
->src
);
3851 /* Finally all edges from non-0 regions to 0 are unlikely. */
3852 FOR_ALL_BB_FN (bb
, cfun
)
3854 if (!(bb
->count
== profile_count::zero ()))
3855 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3856 if (!(e
->probability
== profile_probability::never ())
3857 && e
->dest
->count
== profile_count::zero ())
3859 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3860 fprintf (dump_file
, "Edge %i->%i is unlikely because "
3861 "it enters unlikely block\n",
3862 bb
->index
, e
->dest
->index
);
3863 e
->probability
= profile_probability::never ();
3868 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3869 if (e
->probability
== profile_probability::never ())
3879 && !(other
->probability
== profile_probability::always ()))
3881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3882 fprintf (dump_file
, "Edge %i->%i is locally likely\n",
3883 bb
->index
, other
->dest
->index
);
3884 other
->probability
= profile_probability::always ();
3887 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3888 cgraph_node::get (current_function_decl
)->count
= profile_count::zero ();
3891 /* Estimate and propagate basic block frequencies using the given branch
3892 probabilities. If FORCE is true, the frequencies are used to estimate
3893 the counts even when there are already non-zero profile counts. */
3896 estimate_bb_frequencies (bool force
)
3901 determine_unlikely_bbs ();
3903 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3904 || !update_max_bb_count ())
3907 mark_dfs_back_edges ();
3909 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3910 profile_probability::always ();
3912 /* Set up block info for each basic block. */
3913 alloc_aux_for_blocks (sizeof (block_info
));
3914 alloc_aux_for_edges (sizeof (edge_prob_info
));
3915 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3920 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3922 /* FIXME: Graphite is producing edges with no profile. Once
3923 this is fixed, drop this. */
3924 if (e
->probability
.initialized_p ())
3925 EDGE_INFO (e
)->back_edge_prob
3926 = e
->probability
.to_sreal ();
3928 /* back_edge_prob = 0.5 */
3929 EDGE_INFO (e
)->back_edge_prob
= sreal (1, -1);
3933 /* First compute frequencies locally for each loop from innermost
3934 to outermost to examine frequencies for back edges. */
3938 FOR_EACH_BB_FN (bb
, cfun
)
3939 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3940 freq_max
= BLOCK_INFO (bb
)->frequency
;
3942 /* Scaling frequencies up to maximal profile count may result in
3943 frequent overflows especially when inlining loops.
3944 Small scalling results in unnecesary precision loss. Stay in
3945 the half of the (exponential) range. */
3946 freq_max
= (sreal (1) << (profile_count::n_bits
/ 2)) / freq_max
;
3949 profile_count ipa_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ();
3950 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3951 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3953 sreal tmp
= BLOCK_INFO (bb
)->frequency
;
3956 gimple_stmt_iterator gsi
;
3959 /* Self recursive calls can not have frequency greater than 1
3960 or program will never terminate. This will result in an
3961 inconsistent bb profile but it is better than greatly confusing
3962 IPA cost metrics. */
3963 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3964 if (is_gimple_call (gsi_stmt (gsi
))
3965 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
3966 && recursive_call_p (current_function_decl
, decl
))
3969 fprintf (dump_file
, "Dropping frequency of recursive call"
3970 " in bb %i from %f\n", bb
->index
,
3972 tmp
= (sreal
)9 / (sreal
)10;
3976 tmp
= tmp
* freq_max
+ sreal (1, -1);
3977 profile_count count
= profile_count::from_gcov_type (tmp
.to_int ());
3979 /* If we have profile feedback in which this function was never
3980 executed, then preserve this info. */
3981 if (!(bb
->count
== profile_count::zero ()))
3982 bb
->count
= count
.guessed_local ().combine_with_ipa_count (ipa_count
);
3983 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3986 free_aux_for_blocks ();
3987 free_aux_for_edges ();
3989 compute_function_frequency ();
3992 /* Decide whether function is hot, cold or unlikely executed. */
3994 compute_function_frequency (void)
3997 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3999 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
4000 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
4001 node
->only_called_at_startup
= true;
4002 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
4003 node
->only_called_at_exit
= true;
4005 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ())
4007 int flags
= flags_from_decl_or_type (current_function_decl
);
4008 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
4010 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
4011 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
4013 node
->frequency
= NODE_FREQUENCY_HOT
;
4014 else if (flags
& ECF_NORETURN
)
4015 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4016 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
4017 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4018 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
4019 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
4020 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4024 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
4025 warn_function_cold (current_function_decl
);
4026 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
4028 FOR_EACH_BB_FN (bb
, cfun
)
4030 if (maybe_hot_bb_p (cfun
, bb
))
4032 node
->frequency
= NODE_FREQUENCY_HOT
;
4035 if (!probably_never_executed_bb_p (cfun
, bb
))
4036 node
->frequency
= NODE_FREQUENCY_NORMAL
;
4040 /* Build PREDICT_EXPR. */
4042 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
4044 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
4045 build_int_cst (integer_type_node
, predictor
));
4046 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
4051 predictor_name (enum br_predictor predictor
)
4053 return predictor_info
[predictor
].name
;
4056 /* Predict branch probabilities and estimate profile of the tree CFG. */
4060 const pass_data pass_data_profile
=
4062 GIMPLE_PASS
, /* type */
4063 "profile_estimate", /* name */
4064 OPTGROUP_NONE
, /* optinfo_flags */
4065 TV_BRANCH_PROB
, /* tv_id */
4066 PROP_cfg
, /* properties_required */
4067 0, /* properties_provided */
4068 0, /* properties_destroyed */
4069 0, /* todo_flags_start */
4070 0, /* todo_flags_finish */
4073 class pass_profile
: public gimple_opt_pass
4076 pass_profile (gcc::context
*ctxt
)
4077 : gimple_opt_pass (pass_data_profile
, ctxt
)
4080 /* opt_pass methods: */
4081 bool gate (function
*) final override
{ return flag_guess_branch_prob
; }
4082 unsigned int execute (function
*) final override
;
4084 }; // class pass_profile
4087 pass_profile::execute (function
*fun
)
4091 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4094 loop_optimizer_init (LOOPS_NORMAL
);
4095 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4096 flow_loops_dump (dump_file
, NULL
, 0);
4098 nb_loops
= number_of_loops (fun
);
4102 tree_estimate_probability (false);
4107 loop_optimizer_finalize ();
4108 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4109 gimple_dump_cfg (dump_file
, dump_flags
);
4110 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
4111 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
4112 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4114 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
4115 if (loop
->header
->count
.initialized_p ())
4116 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
4118 (int)expected_loop_iterations_unbounded (loop
));
4126 make_pass_profile (gcc::context
*ctxt
)
4128 return new pass_profile (ctxt
);
4131 /* Return true when PRED predictor should be removed after early
4132 tree passes. Most of the predictors are beneficial to survive
4133 as early inlining can also distribute then into caller's bodies. */
4136 strip_predictor_early (enum br_predictor pred
)
4140 case PRED_TREE_EARLY_RETURN
:
4147 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4148 we no longer need. EARLY is set to true when called from early
4152 strip_predict_hints (function
*fun
, bool early
)
4157 bool changed
= false;
4159 FOR_EACH_BB_FN (bb
, fun
)
4161 gimple_stmt_iterator bi
;
4162 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
4164 gimple
*stmt
= gsi_stmt (bi
);
4166 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
4169 || strip_predictor_early (gimple_predict_predictor (stmt
)))
4171 gsi_remove (&bi
, true);
4176 else if (is_gimple_call (stmt
))
4178 tree fndecl
= gimple_call_fndecl (stmt
);
4181 && ((fndecl
!= NULL_TREE
4182 && fndecl_built_in_p (fndecl
, BUILT_IN_EXPECT
)
4183 && gimple_call_num_args (stmt
) == 2)
4184 || (fndecl
!= NULL_TREE
4185 && fndecl_built_in_p (fndecl
,
4186 BUILT_IN_EXPECT_WITH_PROBABILITY
)
4187 && gimple_call_num_args (stmt
) == 3)
4188 || (gimple_call_internal_p (stmt
)
4189 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
)))
4191 var
= gimple_call_lhs (stmt
);
4196 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
4197 gsi_replace (&bi
, ass_stmt
, true);
4201 gsi_remove (&bi
, true);
4209 return changed
? TODO_cleanup_cfg
: 0;
4214 const pass_data pass_data_strip_predict_hints
=
4216 GIMPLE_PASS
, /* type */
4217 "*strip_predict_hints", /* name */
4218 OPTGROUP_NONE
, /* optinfo_flags */
4219 TV_BRANCH_PROB
, /* tv_id */
4220 PROP_cfg
, /* properties_required */
4221 0, /* properties_provided */
4222 0, /* properties_destroyed */
4223 0, /* todo_flags_start */
4224 0, /* todo_flags_finish */
4227 class pass_strip_predict_hints
: public gimple_opt_pass
4230 pass_strip_predict_hints (gcc::context
*ctxt
)
4231 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
4234 /* opt_pass methods: */
4235 opt_pass
* clone () final override
4237 return new pass_strip_predict_hints (m_ctxt
);
4239 void set_pass_param (unsigned int n
, bool param
) final override
4241 gcc_assert (n
== 0);
4245 unsigned int execute (function
*) final override
;
4250 }; // class pass_strip_predict_hints
4253 pass_strip_predict_hints::execute (function
*fun
)
4255 return strip_predict_hints (fun
, early_p
);
4261 make_pass_strip_predict_hints (gcc::context
*ctxt
)
4263 return new pass_strip_predict_hints (ctxt
);
4266 /* Rebuild function frequencies. Passes are in general expected to
4267 maintain profile by hand, however in some cases this is not possible:
4268 for example when inlining several functions with loops freuqencies might run
4269 out of scale and thus needs to be recomputed. */
4272 rebuild_frequencies (void)
4274 timevar_push (TV_REBUILD_FREQUENCIES
);
4276 /* When the max bb count in the function is small, there is a higher
4277 chance that there were truncation errors in the integer scaling
4278 of counts by inlining and other optimizations. This could lead
4279 to incorrect classification of code as being cold when it isn't.
4280 In that case, force the estimation of bb counts/frequencies from the
4281 branch probabilities, rather than computing frequencies from counts,
4282 which may also lead to frequencies incorrectly reduced to 0. There
4283 is less precision in the probabilities, so we only do this for small
4285 cfun
->cfg
->count_max
= profile_count::uninitialized ();
4287 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
4288 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
4290 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4292 loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
4293 connect_infinite_loops_to_exit ();
4294 estimate_bb_frequencies (true);
4295 remove_fake_exit_edges ();
4296 loop_optimizer_finalize ();
4298 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
4299 update_max_bb_count ();
4300 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
4301 && !flag_guess_branch_prob
)
4305 timevar_pop (TV_REBUILD_FREQUENCIES
);
4308 /* Perform a dry run of the branch prediction pass and report comparsion of
4309 the predicted and real profile into the dump file. */
4312 report_predictor_hitrates (void)
4316 loop_optimizer_init (LOOPS_NORMAL
);
4317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4318 flow_loops_dump (dump_file
, NULL
, 0);
4320 nb_loops
= number_of_loops (cfun
);
4324 tree_estimate_probability (true);
4329 loop_optimizer_finalize ();
4332 /* Force edge E to be cold.
4333 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4334 keep low probability to represent possible error in a guess. This is used
4335 i.e. in case we predict loop to likely iterate given number of times but
4336 we are not 100% sure.
4338 This function locally updates profile without attempt to keep global
4339 consistency which cannot be reached in full generality without full profile
4340 rebuild from probabilities alone. Doing so is not necessarily a good idea
4341 because frequencies and counts may be more realistic then probabilities.
4343 In some cases (such as for elimination of early exits during full loop
4344 unrolling) the caller can ensure that profile will get consistent
4348 force_edge_cold (edge e
, bool impossible
)
4350 profile_count count_sum
= profile_count::zero ();
4351 profile_probability prob_sum
= profile_probability::never ();
4354 bool uninitialized_exit
= false;
4356 /* When branch probability guesses are not known, then do nothing. */
4357 if (!impossible
&& !e
->count ().initialized_p ())
4360 profile_probability goal
= (impossible
? profile_probability::never ()
4361 : profile_probability::very_unlikely ());
4363 /* If edge is already improbably or cold, just return. */
4364 if (e
->probability
<= goal
4365 && (!impossible
|| e
->count () == profile_count::zero ()))
4367 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4370 if (e
->flags
& EDGE_FAKE
)
4372 if (e2
->count ().initialized_p ())
4373 count_sum
+= e2
->count ();
4374 if (e2
->probability
.initialized_p ())
4375 prob_sum
+= e2
->probability
;
4377 uninitialized_exit
= true;
4380 /* If we are not guessing profiles but have some other edges out,
4381 just assume the control flow goes elsewhere. */
4382 if (uninitialized_exit
)
4383 e
->probability
= goal
;
4384 /* If there are other edges out of e->src, redistribute probabilitity
4386 else if (prob_sum
> profile_probability::never ())
4388 if (!(e
->probability
< goal
))
4389 e
->probability
= goal
;
4391 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
4393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4394 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
4395 "probability to other edges.\n",
4396 e
->src
->index
, e
->dest
->index
,
4397 impossible
? "impossible" : "cold");
4398 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4401 e2
->probability
/= prob_comp
;
4403 if (current_ir_type () != IR_GIMPLE
4404 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4405 update_br_prob_note (e
->src
);
4407 /* If all edges out of e->src are unlikely, the basic block itself
4411 if (prob_sum
== profile_probability::never ())
4412 e
->probability
= profile_probability::always ();
4416 e
->probability
= profile_probability::never ();
4417 /* If BB has some edges out that are not impossible, we cannot
4418 assume that BB itself is. */
4421 if (current_ir_type () != IR_GIMPLE
4422 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4423 update_br_prob_note (e
->src
);
4424 if (e
->src
->count
== profile_count::zero ())
4426 if (count_sum
== profile_count::zero () && impossible
)
4429 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4431 else if (current_ir_type () == IR_GIMPLE
)
4432 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4433 !gsi_end_p (gsi
); gsi_next (&gsi
))
4435 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4441 /* FIXME: Implement RTL path. */
4446 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4448 "Making bb %i impossible and dropping count to 0.\n",
4450 e
->src
->count
= profile_count::zero ();
4451 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4452 force_edge_cold (e2
, impossible
);
4457 /* If we did not adjusting, the source basic block has no likely edeges
4458 leaving other direction. In that case force that bb cold, too.
4459 This in general is difficult task to do, but handle special case when
4460 BB has only one predecestor. This is common case when we are updating
4461 after loop transforms. */
4462 if (!(prob_sum
> profile_probability::never ())
4463 && count_sum
== profile_count::zero ()
4464 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4465 > (impossible
? 0 : 1))
4467 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4468 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4469 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4470 impossible
? "impossible" : "cold");
4471 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4472 impossible
? 0 : 1);
4474 e
->src
->count
= profile_count::zero ();
4476 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4478 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4480 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4481 && maybe_hot_bb_p (cfun
, e
->src
))
4482 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4483 impossible
? "impossible" : "cold");
4487 /* Change E's probability to NEW_E_PROB, redistributing the probabilities
4488 of other outgoing edges proportionally.
4490 Note that this function does not change the profile counts of any
4491 basic blocks. The caller must do that instead, using whatever
4492 information it has about the region that needs updating. */
4495 change_edge_frequency (edge e
, profile_probability new_e_prob
)
4497 profile_probability old_e_prob
= e
->probability
;
4498 profile_probability old_other_prob
= old_e_prob
.invert ();
4499 profile_probability new_other_prob
= new_e_prob
.invert ();
4501 e
->probability
= new_e_prob
;
4502 profile_probability cumulative_prob
= new_e_prob
;
4504 unsigned int num_other
= EDGE_COUNT (e
->src
->succs
) - 1;
4507 FOR_EACH_EDGE (other_e
, ei
, e
->src
->succs
)
4512 /* Ensure that the probabilities add up to 1 without
4514 other_e
->probability
= cumulative_prob
.invert ();
4517 other_e
->probability
/= old_other_prob
;
4518 other_e
->probability
*= new_other_prob
;
4519 cumulative_prob
+= other_e
->probability
;
4526 namespace selftest
{
4528 /* Test that value range of predictor values defined in predict.def is
4529 within range (50, 100]. */
4531 struct branch_predictor
4537 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4540 test_prediction_value_range ()
4542 branch_predictor predictors
[] = {
4543 #include "predict.def"
4544 { NULL
, PROB_UNINITIALIZED
}
4547 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4549 if (predictors
[i
].probability
== PROB_UNINITIALIZED
)
4552 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4553 ASSERT_TRUE (p
>= 50 && p
<= 100);
4557 #undef DEF_PREDICTOR
4559 /* Run all of the selfests within this file. */
4564 test_prediction_value_range ();
4567 } // namespace selftest
4568 #endif /* CHECKING_P. */