1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2021 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
.apply_scale (param_hot_bb_frequency_fraction
, 1)
176 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
180 /* Code executed at most once is not hot. */
181 if (count
<= MAX (profile_info
? profile_info
->runs
: 1, 1))
183 return (count
>= 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
.apply_scale (unlikely_frac
, 1) >= profile_info
->runs
)
226 if ((!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
227 && (cgraph_node::get (fun
->decl
)->frequency
228 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
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 ()
920 .apply_scale (unlikely_count
, 1);
921 int count
= nedges
- unlikely_count
- 1;
922 gcc_assert (count
>= 0);
924 e
->probability
= remainder
.apply_scale (1, 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
.apply_scale (1, 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 (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
);
1919 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1920 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1925 /* Predict edge probabilities by exploiting loop structure. */
1928 predict_loops (void)
1931 hash_set
<class loop
*> with_recursion(10);
1933 FOR_EACH_BB_FN (bb
, cfun
)
1935 gimple_stmt_iterator gsi
;
1938 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1939 if (is_gimple_call (gsi_stmt (gsi
))
1940 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1941 && recursive_call_p (current_function_decl
, decl
))
1943 class loop
*loop
= bb
->loop_father
;
1944 while (loop
&& !with_recursion
.add (loop
))
1945 loop
= loop_outer (loop
);
1949 /* Try to predict out blocks in a loop that are not part of a
1951 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
1953 basic_block bb
, *bbs
;
1954 unsigned j
, n_exits
= 0;
1955 class tree_niter_desc niter_desc
;
1957 class nb_iter_bound
*nb_iter
;
1958 enum tree_code loop_bound_code
= ERROR_MARK
;
1959 tree loop_bound_step
= NULL
;
1960 tree loop_bound_var
= NULL
;
1961 tree loop_iv_base
= NULL
;
1963 bool recursion
= with_recursion
.contains (loop
);
1965 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
1966 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1967 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1973 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1974 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1975 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1976 && max_loop_iterations_int (loop
) >= 0)
1979 "Loop %d iterates at most %i times.\n", loop
->num
,
1980 (int)max_loop_iterations_int (loop
));
1982 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1983 && likely_max_loop_iterations_int (loop
) >= 0)
1985 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1986 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1989 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1992 HOST_WIDE_INT nitercst
;
1993 int max
= param_max_predicted_iterations
;
1995 enum br_predictor predictor
;
1998 if (unlikely_executed_edge_p (ex
)
1999 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
2001 /* Loop heuristics do not expect exit conditional to be inside
2002 inner loop. We predict from innermost to outermost loop. */
2003 if (predicted_by_loop_heuristics_p (ex
->src
))
2005 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2006 fprintf (dump_file
, "Skipping exit %i->%i because "
2007 "it is already predicted.\n",
2008 ex
->src
->index
, ex
->dest
->index
);
2011 predict_extra_loop_exits (ex
);
2013 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
2014 niter
= niter_desc
.niter
;
2015 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
2016 niter
= loop_niter_by_eval (loop
, ex
);
2017 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
2018 && TREE_CODE (niter
) == INTEGER_CST
)
2020 fprintf (dump_file
, "Exit %i->%i %d iterates ",
2021 ex
->src
->index
, ex
->dest
->index
,
2023 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
2024 fprintf (dump_file
, " times.\n");
2027 if (TREE_CODE (niter
) == INTEGER_CST
)
2029 if (tree_fits_uhwi_p (niter
)
2031 && compare_tree_int (niter
, max
- 1) == -1)
2032 nitercst
= tree_to_uhwi (niter
) + 1;
2035 predictor
= PRED_LOOP_ITERATIONS
;
2037 /* If we have just one exit and we can derive some information about
2038 the number of iterations of the loop from the statements inside
2039 the loop, use it to predict this exit. */
2040 else if (n_exits
== 1
2041 && estimated_stmt_executions (loop
, &nit
))
2043 if (wi::gtu_p (nit
, max
))
2046 nitercst
= nit
.to_shwi ();
2047 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
2049 /* If we have likely upper bound, trust it for very small iteration
2050 counts. Such loops would otherwise get mispredicted by standard
2051 LOOP_EXIT heuristics. */
2052 else if (n_exits
== 1
2053 && likely_max_stmt_executions (loop
, &nit
)
2055 RDIV (REG_BR_PROB_BASE
,
2059 ? PRED_LOOP_EXIT_WITH_RECURSION
2060 : PRED_LOOP_EXIT
].hitrate
)))
2062 nitercst
= nit
.to_shwi ();
2063 predictor
= PRED_LOOP_ITERATIONS_MAX
;
2067 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2068 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
2069 ex
->src
->index
, ex
->dest
->index
);
2073 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2074 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
2075 (int)nitercst
, predictor_info
[predictor
].name
);
2076 /* If the prediction for number of iterations is zero, do not
2077 predict the exit edges. */
2081 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
2082 predict_edge (ex
, predictor
, probability
);
2085 /* Find information about loop bound variables. */
2086 for (nb_iter
= loop
->bounds
; nb_iter
;
2087 nb_iter
= nb_iter
->next
)
2089 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
2091 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
2094 if (!stmt
&& last_stmt (loop
->header
)
2095 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
2096 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2098 is_comparison_with_loop_invariant_p (stmt
, loop
,
2104 bbs
= get_loop_body (loop
);
2106 for (j
= 0; j
< loop
->num_nodes
; j
++)
2113 /* Bypass loop heuristics on continue statement. These
2114 statements construct loops via "non-loop" constructs
2115 in the source language and are better to be handled
2117 if (predicted_by_p (bb
, PRED_CONTINUE
))
2119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2120 fprintf (dump_file
, "BB %i predicted by continue.\n",
2125 /* If we already used more reliable loop exit predictors, do not
2126 bother with PRED_LOOP_EXIT. */
2127 if (!predicted_by_loop_heuristics_p (bb
))
2129 /* For loop with many exits we don't want to predict all exits
2130 with the pretty large probability, because if all exits are
2131 considered in row, the loop would be predicted to iterate
2132 almost never. The code to divide probability by number of
2133 exits is very rough. It should compute the number of exits
2134 taken in each patch through function (not the overall number
2135 of exits that might be a lot higher for loops with wide switch
2136 statements in them) and compute n-th square root.
2138 We limit the minimal probability by 2% to avoid
2139 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2140 as this was causing regression in perl benchmark containing such
2143 int probability
= ((REG_BR_PROB_BASE
2146 ? PRED_LOOP_EXIT_WITH_RECURSION
2147 : PRED_LOOP_EXIT
].hitrate
)
2149 if (probability
< HITRATE (2))
2150 probability
= HITRATE (2);
2151 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2152 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2153 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2155 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2157 "Predicting exit %i->%i with prob %i.\n",
2158 e
->src
->index
, e
->dest
->index
, probability
);
2160 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2161 : PRED_LOOP_EXIT
, probability
);
2165 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2167 tree_to_shwi (loop_bound_step
));
2170 /* In the following code
2175 guess that cond is unlikely. */
2176 if (loop_outer (loop
)->num
)
2178 basic_block bb
= NULL
;
2179 edge preheader_edge
= loop_preheader_edge (loop
);
2181 if (single_pred_p (preheader_edge
->src
)
2182 && single_succ_p (preheader_edge
->src
))
2183 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2185 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2186 /* Pattern match fortran loop preheader:
2187 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2188 _17 = (logical(kind=4)) _16;
2194 Loop guard branch prediction says nothing about duplicated loop
2195 headers produced by fortran frontend and in this case we want
2196 to predict paths leading to this preheader. */
2199 && gimple_code (stmt
) == GIMPLE_COND
2200 && gimple_cond_code (stmt
) == NE_EXPR
2201 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2202 && integer_zerop (gimple_cond_rhs (stmt
)))
2204 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2205 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2206 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (call_stmt
))
2207 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2208 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2209 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2210 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2211 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2212 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2213 == PRED_FORTRAN_LOOP_PREHEADER
)
2214 bb
= preheader_edge
->src
;
2218 if (!dominated_by_p (CDI_DOMINATORS
,
2219 loop_outer (loop
)->latch
, loop
->header
))
2220 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2222 ? PRED_LOOP_GUARD_WITH_RECURSION
2229 if (!dominated_by_p (CDI_DOMINATORS
,
2230 loop_outer (loop
)->latch
, bb
))
2231 predict_paths_leading_to (bb
,
2233 ? PRED_LOOP_GUARD_WITH_RECURSION
2240 /* Free basic blocks from get_loop_body. */
2245 /* Attempt to predict probabilities of BB outgoing edges using local
2248 bb_estimate_probability_locally (basic_block bb
)
2250 rtx_insn
*last_insn
= BB_END (bb
);
2253 if (! can_predict_insn_p (last_insn
))
2255 cond
= get_condition (last_insn
, NULL
, false, false);
2259 /* Try "pointer heuristic."
2260 A comparison ptr == 0 is predicted as false.
2261 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2262 if (COMPARISON_P (cond
)
2263 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2264 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2266 if (GET_CODE (cond
) == EQ
)
2267 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2268 else if (GET_CODE (cond
) == NE
)
2269 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2273 /* Try "opcode heuristic."
2274 EQ tests are usually false and NE tests are usually true. Also,
2275 most quantities are positive, so we can make the appropriate guesses
2276 about signed comparisons against zero. */
2277 switch (GET_CODE (cond
))
2280 /* Unconditional branch. */
2281 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2282 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2287 /* Floating point comparisons appears to behave in a very
2288 unpredictable way because of special role of = tests in
2290 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2292 /* Comparisons with 0 are often used for booleans and there is
2293 nothing useful to predict about them. */
2294 else if (XEXP (cond
, 1) == const0_rtx
2295 || XEXP (cond
, 0) == const0_rtx
)
2298 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2303 /* Floating point comparisons appears to behave in a very
2304 unpredictable way because of special role of = tests in
2306 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2308 /* Comparisons with 0 are often used for booleans and there is
2309 nothing useful to predict about them. */
2310 else if (XEXP (cond
, 1) == const0_rtx
2311 || XEXP (cond
, 0) == const0_rtx
)
2314 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2318 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2322 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2327 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2328 || XEXP (cond
, 1) == constm1_rtx
)
2329 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2334 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2335 || XEXP (cond
, 1) == constm1_rtx
)
2336 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2344 /* Set edge->probability for each successor edge of BB. */
2346 guess_outgoing_edge_probabilities (basic_block bb
)
2348 bb_estimate_probability_locally (bb
);
2349 combine_predictions_for_insn (BB_END (bb
), bb
);
2352 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
,
2353 HOST_WIDE_INT
*probability
);
2355 /* Helper function for expr_expected_value. */
2358 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2359 tree op1
, bitmap visited
, enum br_predictor
*predictor
,
2360 HOST_WIDE_INT
*probability
)
2364 /* Reset returned probability value. */
2366 *predictor
= PRED_UNCONDITIONAL
;
2368 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2370 if (TREE_CONSTANT (op0
))
2373 if (code
== IMAGPART_EXPR
)
2375 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2377 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2378 if (is_gimple_call (def
)
2379 && gimple_call_internal_p (def
)
2380 && (gimple_call_internal_fn (def
)
2381 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2383 /* Assume that any given atomic operation has low contention,
2384 and thus the compare-and-swap operation succeeds. */
2385 *predictor
= PRED_COMPARE_AND_SWAP
;
2386 return build_one_cst (TREE_TYPE (op0
));
2391 if (code
!= SSA_NAME
)
2394 def
= SSA_NAME_DEF_STMT (op0
);
2396 /* If we were already here, break the infinite cycle. */
2397 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2400 if (gimple_code (def
) == GIMPLE_PHI
)
2402 /* All the arguments of the PHI node must have the same constant
2404 int i
, n
= gimple_phi_num_args (def
);
2405 tree val
= NULL
, new_val
;
2407 for (i
= 0; i
< n
; i
++)
2409 tree arg
= PHI_ARG_DEF (def
, i
);
2410 enum br_predictor predictor2
;
2412 /* If this PHI has itself as an argument, we cannot
2413 determine the string length of this argument. However,
2414 if we can find an expected constant value for the other
2415 PHI args then we can still be sure that this is
2416 likely a constant. So be optimistic and just
2417 continue with the next argument. */
2418 if (arg
== PHI_RESULT (def
))
2421 HOST_WIDE_INT probability2
;
2422 new_val
= expr_expected_value (arg
, visited
, &predictor2
,
2425 /* It is difficult to combine value predictors. Simply assume
2426 that later predictor is weaker and take its prediction. */
2427 if (*predictor
< predictor2
)
2429 *predictor
= predictor2
;
2430 *probability
= probability2
;
2436 else if (!operand_equal_p (val
, new_val
, false))
2441 if (is_gimple_assign (def
))
2443 if (gimple_assign_lhs (def
) != op0
)
2446 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2447 gimple_assign_rhs1 (def
),
2448 gimple_assign_rhs_code (def
),
2449 gimple_assign_rhs2 (def
),
2450 visited
, predictor
, probability
);
2453 if (is_gimple_call (def
))
2455 tree decl
= gimple_call_fndecl (def
);
2458 if (gimple_call_internal_p (def
)
2459 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2461 gcc_assert (gimple_call_num_args (def
) == 3);
2462 tree val
= gimple_call_arg (def
, 0);
2463 if (TREE_CONSTANT (val
))
2465 tree val2
= gimple_call_arg (def
, 2);
2466 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2467 && tree_fits_uhwi_p (val2
)
2468 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2469 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2470 if (*predictor
== PRED_BUILTIN_EXPECT
)
2472 = HITRATE (param_builtin_expect_probability
);
2473 return gimple_call_arg (def
, 1);
2478 if (DECL_IS_MALLOC (decl
) || DECL_IS_OPERATOR_NEW_P (decl
))
2481 *predictor
= PRED_MALLOC_NONNULL
;
2482 return boolean_true_node
;
2485 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2486 switch (DECL_FUNCTION_CODE (decl
))
2488 case BUILT_IN_EXPECT
:
2491 if (gimple_call_num_args (def
) != 2)
2493 val
= gimple_call_arg (def
, 0);
2494 if (TREE_CONSTANT (val
))
2496 *predictor
= PRED_BUILTIN_EXPECT
;
2498 = HITRATE (param_builtin_expect_probability
);
2499 return gimple_call_arg (def
, 1);
2501 case BUILT_IN_EXPECT_WITH_PROBABILITY
:
2504 if (gimple_call_num_args (def
) != 3)
2506 val
= gimple_call_arg (def
, 0);
2507 if (TREE_CONSTANT (val
))
2509 /* Compute final probability as:
2510 probability * REG_BR_PROB_BASE. */
2511 tree prob
= gimple_call_arg (def
, 2);
2512 tree t
= TREE_TYPE (prob
);
2513 tree base
= build_int_cst (integer_type_node
,
2515 base
= build_real_from_int_cst (t
, base
);
2516 tree r
= fold_build2_initializer_loc (UNKNOWN_LOCATION
,
2517 MULT_EXPR
, t
, prob
, base
);
2518 if (TREE_CODE (r
) != REAL_CST
)
2520 error_at (gimple_location (def
),
2521 "probability %qE must be "
2522 "constant floating-point expression", prob
);
2526 = real_to_integer (TREE_REAL_CST_PTR (r
));
2527 if (probi
>= 0 && probi
<= REG_BR_PROB_BASE
)
2529 *predictor
= PRED_BUILTIN_EXPECT_WITH_PROBABILITY
;
2530 *probability
= probi
;
2533 error_at (gimple_location (def
),
2534 "probability %qE is outside "
2535 "the range [0.0, 1.0]", prob
);
2537 return gimple_call_arg (def
, 1);
2540 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2541 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2542 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2543 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2544 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2545 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2546 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2547 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2548 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2549 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2550 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2551 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2552 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2553 /* Assume that any given atomic operation has low contention,
2554 and thus the compare-and-swap operation succeeds. */
2555 *predictor
= PRED_COMPARE_AND_SWAP
;
2556 return boolean_true_node
;
2557 case BUILT_IN_REALLOC
:
2559 *predictor
= PRED_MALLOC_NONNULL
;
2560 return boolean_true_node
;
2569 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2572 enum br_predictor predictor2
;
2573 HOST_WIDE_INT probability2
;
2574 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2577 op1
= expr_expected_value (op1
, visited
, &predictor2
, &probability2
);
2580 res
= fold_build2 (code
, type
, op0
, op1
);
2581 if (TREE_CODE (res
) == INTEGER_CST
2582 && TREE_CODE (op0
) == INTEGER_CST
2583 && TREE_CODE (op1
) == INTEGER_CST
)
2585 /* Combine binary predictions. */
2586 if (*probability
!= -1 || probability2
!= -1)
2588 HOST_WIDE_INT p1
= get_predictor_value (*predictor
, *probability
);
2589 HOST_WIDE_INT p2
= get_predictor_value (predictor2
, probability2
);
2590 *probability
= RDIV (p1
* p2
, REG_BR_PROB_BASE
);
2593 if (*predictor
< predictor2
)
2594 *predictor
= predictor2
;
2600 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2603 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2606 res
= fold_build1 (code
, type
, op0
);
2607 if (TREE_CONSTANT (res
))
2614 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2615 The function is used by builtin_expect branch predictor so the evidence
2616 must come from this construct and additional possible constant folding.
2618 We may want to implement more involved value guess (such as value range
2619 propagation based prediction), but such tricks shall go to new
2623 expr_expected_value (tree expr
, bitmap visited
,
2624 enum br_predictor
*predictor
,
2625 HOST_WIDE_INT
*probability
)
2627 enum tree_code code
;
2630 if (TREE_CONSTANT (expr
))
2632 *predictor
= PRED_UNCONDITIONAL
;
2637 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2638 return expr_expected_value_1 (TREE_TYPE (expr
),
2639 op0
, code
, op1
, visited
, predictor
,
2644 /* Return probability of a PREDICTOR. If the predictor has variable
2645 probability return passed PROBABILITY. */
2647 static HOST_WIDE_INT
2648 get_predictor_value (br_predictor predictor
, HOST_WIDE_INT probability
)
2652 case PRED_BUILTIN_EXPECT
:
2653 case PRED_BUILTIN_EXPECT_WITH_PROBABILITY
:
2654 gcc_assert (probability
!= -1);
2657 gcc_assert (probability
== -1);
2658 return predictor_info
[(int) predictor
].hitrate
;
2662 /* Predict using opcode of the last statement in basic block. */
2664 tree_predict_by_opcode (basic_block bb
)
2666 gimple
*stmt
= last_stmt (bb
);
2673 enum br_predictor predictor
;
2674 HOST_WIDE_INT probability
;
2679 if (gswitch
*sw
= dyn_cast
<gswitch
*> (stmt
))
2681 tree index
= gimple_switch_index (sw
);
2682 tree val
= expr_expected_value (index
, auto_bitmap (),
2683 &predictor
, &probability
);
2684 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2686 edge e
= find_taken_edge_switch_expr (sw
, val
);
2687 if (predictor
== PRED_BUILTIN_EXPECT
)
2689 int percent
= param_builtin_expect_probability
;
2690 gcc_assert (percent
>= 0 && percent
<= 100);
2691 predict_edge (e
, PRED_BUILTIN_EXPECT
,
2695 predict_edge_def (e
, predictor
, TAKEN
);
2699 if (gimple_code (stmt
) != GIMPLE_COND
)
2701 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2702 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2704 op0
= gimple_cond_lhs (stmt
);
2705 op1
= gimple_cond_rhs (stmt
);
2706 cmp
= gimple_cond_code (stmt
);
2707 type
= TREE_TYPE (op0
);
2708 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2709 &predictor
, &probability
);
2710 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2712 HOST_WIDE_INT prob
= get_predictor_value (predictor
, probability
);
2713 if (integer_zerop (val
))
2714 prob
= REG_BR_PROB_BASE
- prob
;
2715 predict_edge (then_edge
, predictor
, prob
);
2717 /* Try "pointer heuristic."
2718 A comparison ptr == 0 is predicted as false.
2719 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2720 if (POINTER_TYPE_P (type
))
2723 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2724 else if (cmp
== NE_EXPR
)
2725 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2729 /* Try "opcode heuristic."
2730 EQ tests are usually false and NE tests are usually true. Also,
2731 most quantities are positive, so we can make the appropriate guesses
2732 about signed comparisons against zero. */
2737 /* Floating point comparisons appears to behave in a very
2738 unpredictable way because of special role of = tests in
2740 if (FLOAT_TYPE_P (type
))
2742 /* Comparisons with 0 are often used for booleans and there is
2743 nothing useful to predict about them. */
2744 else if (integer_zerop (op0
) || integer_zerop (op1
))
2747 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2752 /* Floating point comparisons appears to behave in a very
2753 unpredictable way because of special role of = tests in
2755 if (FLOAT_TYPE_P (type
))
2757 /* Comparisons with 0 are often used for booleans and there is
2758 nothing useful to predict about them. */
2759 else if (integer_zerop (op0
)
2760 || integer_zerop (op1
))
2763 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2767 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2770 case UNORDERED_EXPR
:
2771 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2776 if (integer_zerop (op1
)
2777 || integer_onep (op1
)
2778 || integer_all_onesp (op1
)
2781 || real_minus_onep (op1
))
2782 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2787 if (integer_zerop (op1
)
2788 || integer_onep (op1
)
2789 || integer_all_onesp (op1
)
2792 || real_minus_onep (op1
))
2793 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2801 /* Returns TRUE if the STMT is exit(0) like statement. */
2804 is_exit_with_zero_arg (const gimple
*stmt
)
2806 /* This is not exit, _exit or _Exit. */
2807 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2808 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2809 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2812 /* Argument is an interger zero. */
2813 return integer_zerop (gimple_call_arg (stmt
, 0));
2816 /* Try to guess whether the value of return means error code. */
2818 static enum br_predictor
2819 return_prediction (tree val
, enum prediction
*prediction
)
2823 return PRED_NO_PREDICTION
;
2824 /* Different heuristics for pointers and scalars. */
2825 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2827 /* NULL is usually not returned. */
2828 if (integer_zerop (val
))
2830 *prediction
= NOT_TAKEN
;
2831 return PRED_NULL_RETURN
;
2834 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2836 /* Negative return values are often used to indicate
2838 if (TREE_CODE (val
) == INTEGER_CST
2839 && tree_int_cst_sgn (val
) < 0)
2841 *prediction
= NOT_TAKEN
;
2842 return PRED_NEGATIVE_RETURN
;
2844 /* Constant return values seems to be commonly taken.
2845 Zero/one often represent booleans so exclude them from the
2847 if (TREE_CONSTANT (val
)
2848 && (!integer_zerop (val
) && !integer_onep (val
)))
2850 *prediction
= NOT_TAKEN
;
2851 return PRED_CONST_RETURN
;
2854 return PRED_NO_PREDICTION
;
2857 /* Return zero if phi result could have values other than -1, 0 or 1,
2858 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2859 values are used or likely. */
2862 zero_one_minusone (gphi
*phi
, int limit
)
2864 int phi_num_args
= gimple_phi_num_args (phi
);
2866 for (int i
= 0; i
< phi_num_args
; i
++)
2868 tree t
= PHI_ARG_DEF (phi
, i
);
2869 if (TREE_CODE (t
) != INTEGER_CST
)
2871 wide_int w
= wi::to_wide (t
);
2881 for (int i
= 0; i
< phi_num_args
; i
++)
2883 tree t
= PHI_ARG_DEF (phi
, i
);
2884 if (TREE_CODE (t
) == INTEGER_CST
)
2886 if (TREE_CODE (t
) != SSA_NAME
)
2888 gimple
*g
= SSA_NAME_DEF_STMT (t
);
2889 if (gimple_code (g
) == GIMPLE_PHI
&& limit
> 0)
2890 if (int r
= zero_one_minusone (as_a
<gphi
*> (g
), limit
- 1))
2895 if (!is_gimple_assign (g
))
2897 if (gimple_assign_cast_p (g
))
2899 tree rhs1
= gimple_assign_rhs1 (g
);
2900 if (TREE_CODE (rhs1
) != SSA_NAME
2901 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
2902 || TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2903 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2908 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g
)) != tcc_comparison
)
2915 /* Find the basic block with return expression and look up for possible
2916 return value trying to apply RETURN_PREDICTION heuristics. */
2918 apply_return_prediction (void)
2920 greturn
*return_stmt
= NULL
;
2924 int phi_num_args
, i
;
2925 enum br_predictor pred
;
2926 enum prediction direction
;
2929 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2931 gimple
*last
= last_stmt (e
->src
);
2933 && gimple_code (last
) == GIMPLE_RETURN
)
2935 return_stmt
= as_a
<greturn
*> (last
);
2941 return_val
= gimple_return_retval (return_stmt
);
2944 if (TREE_CODE (return_val
) != SSA_NAME
2945 || !SSA_NAME_DEF_STMT (return_val
)
2946 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2948 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2949 phi_num_args
= gimple_phi_num_args (phi
);
2950 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2952 /* Avoid the case where the function returns -1, 0 and 1 values and
2953 nothing else. Those could be qsort etc. comparison functions
2954 where the negative return isn't less probable than positive.
2955 For this require that the function returns at least -1 or 1
2956 or -1 and a boolean value or comparison result, so that functions
2957 returning just -1 and 0 are treated as if -1 represents error value. */
2958 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val
))
2959 && !TYPE_UNSIGNED (TREE_TYPE (return_val
))
2960 && TYPE_PRECISION (TREE_TYPE (return_val
)) > 1)
2961 if (int r
= zero_one_minusone (phi
, 3))
2962 if ((r
& (1 | 4)) == (1 | 4))
2965 /* Avoid the degenerate case where all return values form the function
2966 belongs to same category (ie they are all positive constants)
2967 so we can hardly say something about them. */
2968 for (i
= 1; i
< phi_num_args
; i
++)
2969 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2971 if (i
!= phi_num_args
)
2972 for (i
= 0; i
< phi_num_args
; i
++)
2974 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2975 if (pred
!= PRED_NO_PREDICTION
)
2976 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2981 /* Look for basic block that contains unlikely to happen events
2982 (such as noreturn calls) and mark all paths leading to execution
2983 of this basic blocks as unlikely. */
2986 tree_bb_level_predictions (void)
2989 bool has_return_edges
= false;
2993 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2994 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2996 has_return_edges
= true;
3000 apply_return_prediction ();
3002 FOR_EACH_BB_FN (bb
, cfun
)
3004 gimple_stmt_iterator gsi
;
3006 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3008 gimple
*stmt
= gsi_stmt (gsi
);
3011 if (is_gimple_call (stmt
))
3013 if (gimple_call_noreturn_p (stmt
)
3015 && !is_exit_with_zero_arg (stmt
))
3016 predict_paths_leading_to (bb
, PRED_NORETURN
,
3018 decl
= gimple_call_fndecl (stmt
);
3020 && lookup_attribute ("cold",
3021 DECL_ATTRIBUTES (decl
)))
3022 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
3024 if (decl
&& recursive_call_p (current_function_decl
, decl
))
3025 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
3028 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3030 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
3031 gimple_predict_outcome (stmt
));
3032 /* Keep GIMPLE_PREDICT around so early inlining will propagate
3033 hints to callers. */
3039 /* Callback for hash_map::traverse, asserts that the pointer map is
3043 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
3046 gcc_assert (!value
);
3050 /* Predict branch probabilities and estimate profile for basic block BB.
3051 When LOCAL_ONLY is set do not use any global properties of CFG. */
3054 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
3059 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3061 /* Look for block we are guarding (ie we dominate it,
3062 but it doesn't postdominate us). */
3063 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
3065 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
3066 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
3068 gimple_stmt_iterator bi
;
3070 /* The call heuristic claims that a guarded function call
3071 is improbable. This is because such calls are often used
3072 to signal exceptional situations such as printing error
3074 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
3077 gimple
*stmt
= gsi_stmt (bi
);
3078 if (is_gimple_call (stmt
)
3079 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
3080 /* Constant and pure calls are hardly used to signalize
3081 something exceptional. */
3082 && gimple_has_side_effects (stmt
))
3084 if (gimple_call_fndecl (stmt
))
3085 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
3086 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
3087 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
3089 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
3095 tree_predict_by_opcode (bb
);
3098 /* Predict branch probabilities and estimate profile of the tree CFG.
3099 This function can be called from the loop optimizers to recompute
3100 the profile information.
3101 If DRY_RUN is set, do not modify CFG and only produce dump files. */
3104 tree_estimate_probability (bool dry_run
)
3108 connect_infinite_loops_to_exit ();
3109 /* We use loop_niter_by_eval, which requires that the loops have
3111 create_preheaders (CP_SIMPLE_PREHEADERS
);
3112 calculate_dominance_info (CDI_POST_DOMINATORS
);
3113 /* Decide which edges are known to be unlikely. This improves later
3114 branch prediction. */
3115 determine_unlikely_bbs ();
3117 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3118 tree_bb_level_predictions ();
3119 record_loop_exits ();
3121 if (number_of_loops (cfun
) > 1)
3124 FOR_EACH_BB_FN (bb
, cfun
)
3125 tree_estimate_probability_bb (bb
, false);
3127 FOR_EACH_BB_FN (bb
, cfun
)
3128 combine_predictions_for_bb (bb
, dry_run
);
3131 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3133 delete bb_predictions
;
3134 bb_predictions
= NULL
;
3137 estimate_bb_frequencies (false);
3138 free_dominance_info (CDI_POST_DOMINATORS
);
3139 remove_fake_exit_edges ();
3142 /* Set edge->probability for each successor edge of BB. */
3144 tree_guess_outgoing_edge_probabilities (basic_block bb
)
3146 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3147 tree_estimate_probability_bb (bb
, true);
3148 combine_predictions_for_bb (bb
, false);
3150 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3151 delete bb_predictions
;
3152 bb_predictions
= NULL
;
3155 /* Filter function predicate that returns true for a edge predicate P
3156 if its edge is equal to DATA. */
3159 not_loop_guard_equal_edge_p (edge_prediction
*p
, void *data
)
3161 return p
->ep_edge
!= (edge
)data
|| p
->ep_predictor
!= PRED_LOOP_GUARD
;
3164 /* Predict edge E with PRED unless it is already predicted by some predictor
3165 considered equivalent. */
3168 maybe_predict_edge (edge e
, enum br_predictor pred
, enum prediction taken
)
3170 if (edge_predicted_by_p (e
, pred
, taken
))
3172 if (pred
== PRED_LOOP_GUARD
3173 && edge_predicted_by_p (e
, PRED_LOOP_GUARD_WITH_RECURSION
, taken
))
3175 /* Consider PRED_LOOP_GUARD_WITH_RECURSION superrior to LOOP_GUARD. */
3176 if (pred
== PRED_LOOP_GUARD_WITH_RECURSION
)
3178 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
3180 filter_predictions (preds
, not_loop_guard_equal_edge_p
, e
);
3182 predict_edge_def (e
, pred
, taken
);
3184 /* Predict edges to successors of CUR whose sources are not postdominated by
3185 BB by PRED and recurse to all postdominators. */
3188 predict_paths_for_bb (basic_block cur
, basic_block bb
,
3189 enum br_predictor pred
,
3190 enum prediction taken
,
3191 bitmap visited
, class loop
*in_loop
= NULL
)
3197 /* If we exited the loop or CUR is unconditional in the loop, there is
3200 && (!flow_bb_inside_loop_p (in_loop
, cur
)
3201 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
3204 /* We are looking for all edges forming edge cut induced by
3205 set of all blocks postdominated by BB. */
3206 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
3207 if (e
->src
->index
>= NUM_FIXED_BLOCKS
3208 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
3214 /* Ignore fake edges and eh, we predict them as not taken anyway. */
3215 if (unlikely_executed_edge_p (e
))
3217 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
3219 /* See if there is an edge from e->src that is not abnormal
3220 and does not lead to BB and does not exit the loop. */
3221 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
3223 && !unlikely_executed_edge_p (e2
)
3224 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
3225 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
3231 /* If there is non-abnormal path leaving e->src, predict edge
3232 using predictor. Otherwise we need to look for paths
3235 The second may lead to infinite loop in the case we are predicitng
3236 regions that are only reachable by abnormal edges. We simply
3237 prevent visiting given BB twice. */
3239 maybe_predict_edge (e
, pred
, taken
);
3240 else if (bitmap_set_bit (visited
, e
->src
->index
))
3241 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
3243 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
3245 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
3246 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
3249 /* Sets branch probabilities according to PREDiction and
3253 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
3254 enum prediction taken
, class loop
*in_loop
)
3256 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3259 /* Like predict_paths_leading_to but take edge instead of basic block. */
3262 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
3263 enum prediction taken
, class loop
*in_loop
)
3265 bool has_nonloop_edge
= false;
3269 basic_block bb
= e
->src
;
3270 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
3271 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
3272 && !unlikely_executed_edge_p (e2
)
3273 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
3275 has_nonloop_edge
= true;
3279 if (!has_nonloop_edge
)
3280 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3282 maybe_predict_edge (e
, pred
, taken
);
3285 /* This is used to carry information about basic blocks. It is
3286 attached to the AUX field of the standard CFG block. */
3291 /* Estimated frequency of execution of basic_block. */
3294 /* To keep queue of basic blocks to process. */
3297 /* Number of predecessors we need to visit first. */
3301 /* Similar information for edges. */
3302 class edge_prob_info
3305 /* In case edge is a loopback edge, the probability edge will be reached
3306 in case header is. Estimated number of iterations of the loop can be
3307 then computed as 1 / (1 - back_edge_prob). */
3308 sreal back_edge_prob
;
3309 /* True if the edge is a loopback edge in the natural loop. */
3310 unsigned int back_edge
:1;
3313 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3315 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3317 /* Helper function for estimate_bb_frequencies.
3318 Propagate the frequencies in blocks marked in
3319 TOVISIT, starting in HEAD. */
3322 propagate_freq (basic_block head
, bitmap tovisit
,
3323 sreal max_cyclic_prob
)
3332 /* For each basic block we need to visit count number of his predecessors
3333 we need to visit first. */
3334 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
3339 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3341 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3343 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3345 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3347 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3349 "Irreducible region hit, ignoring edge to %i->%i\n",
3350 e
->src
->index
, bb
->index
);
3352 BLOCK_INFO (bb
)->npredecessors
= count
;
3353 /* When function never returns, we will never process exit block. */
3354 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3355 bb
->count
= profile_count::zero ();
3358 BLOCK_INFO (head
)->frequency
= 1;
3360 for (bb
= head
; bb
; bb
= nextbb
)
3363 sreal cyclic_probability
= 0;
3364 sreal frequency
= 0;
3366 nextbb
= BLOCK_INFO (bb
)->next
;
3367 BLOCK_INFO (bb
)->next
= NULL
;
3369 /* Compute frequency of basic block. */
3373 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3374 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3375 || (e
->flags
& EDGE_DFS_BACK
));
3377 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3378 if (EDGE_INFO (e
)->back_edge
)
3379 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3380 else if (!(e
->flags
& EDGE_DFS_BACK
))
3382 /* FIXME: Graphite is producing edges with no profile. Once
3383 this is fixed, drop this. */
3384 sreal tmp
= e
->probability
.initialized_p () ?
3385 e
->probability
.to_sreal () : 0;
3386 frequency
+= tmp
* BLOCK_INFO (e
->src
)->frequency
;
3389 if (cyclic_probability
== 0)
3391 BLOCK_INFO (bb
)->frequency
= frequency
;
3395 if (cyclic_probability
> max_cyclic_prob
)
3399 "cyclic probability of bb %i is %f (capped to %f)"
3400 "; turning freq %f",
3401 bb
->index
, cyclic_probability
.to_double (),
3402 max_cyclic_prob
.to_double (),
3403 frequency
.to_double ());
3405 cyclic_probability
= max_cyclic_prob
;
3409 "cyclic probability of bb %i is %f; turning freq %f",
3410 bb
->index
, cyclic_probability
.to_double (),
3411 frequency
.to_double ());
3413 BLOCK_INFO (bb
)->frequency
= frequency
3414 / (sreal (1) - cyclic_probability
);
3416 fprintf (dump_file
, " to %f\n",
3417 BLOCK_INFO (bb
)->frequency
.to_double ());
3421 bitmap_clear_bit (tovisit
, bb
->index
);
3423 e
= find_edge (bb
, head
);
3426 /* FIXME: Graphite is producing edges with no profile. Once
3427 this is fixed, drop this. */
3428 sreal tmp
= e
->probability
.initialized_p () ?
3429 e
->probability
.to_sreal () : 0;
3430 EDGE_INFO (e
)->back_edge_prob
= tmp
* BLOCK_INFO (bb
)->frequency
;
3433 /* Propagate to successor blocks. */
3434 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3435 if (!(e
->flags
& EDGE_DFS_BACK
)
3436 && BLOCK_INFO (e
->dest
)->npredecessors
)
3438 BLOCK_INFO (e
->dest
)->npredecessors
--;
3439 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3444 BLOCK_INFO (last
)->next
= e
->dest
;
3452 /* Estimate frequencies in loops at same nest level. */
3455 estimate_loops_at_level (class loop
*first_loop
, sreal max_cyclic_prob
)
3459 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3464 auto_bitmap tovisit
;
3466 estimate_loops_at_level (loop
->inner
, max_cyclic_prob
);
3468 /* Find current loop back edge and mark it. */
3469 e
= loop_latch_edge (loop
);
3470 EDGE_INFO (e
)->back_edge
= 1;
3472 bbs
= get_loop_body (loop
);
3473 for (i
= 0; i
< loop
->num_nodes
; i
++)
3474 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3476 propagate_freq (loop
->header
, tovisit
, max_cyclic_prob
);
3480 /* Propagates frequencies through structure of loops. */
3483 estimate_loops (void)
3485 auto_bitmap tovisit
;
3487 sreal max_cyclic_prob
= (sreal
)1
3488 - (sreal
)1 / (param_max_predicted_iterations
+ 1);
3490 /* Start by estimating the frequencies in the loops. */
3491 if (number_of_loops (cfun
) > 1)
3492 estimate_loops_at_level (current_loops
->tree_root
->inner
, max_cyclic_prob
);
3494 /* Now propagate the frequencies through all the blocks. */
3495 FOR_ALL_BB_FN (bb
, cfun
)
3497 bitmap_set_bit (tovisit
, bb
->index
);
3499 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
, max_cyclic_prob
);
3502 /* Drop the profile for NODE to guessed, and update its frequency based on
3503 whether it is expected to be hot given the CALL_COUNT. */
3506 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3508 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3509 /* In the case where this was called by another function with a
3510 dropped profile, call_count will be 0. Since there are no
3511 non-zero call counts to this function, we don't know for sure
3512 whether it is hot, and therefore it will be marked normal below. */
3513 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3517 "Dropping 0 profile for %s. %s based on calls.\n",
3519 hot
? "Function is hot" : "Function is normal");
3520 /* We only expect to miss profiles for functions that are reached
3521 via non-zero call edges in cases where the function may have
3522 been linked from another module or library (COMDATs and extern
3523 templates). See the comments below for handle_missing_profiles.
3524 Also, only warn in cases where the missing counts exceed the
3525 number of training runs. In certain cases with an execv followed
3526 by a no-return call the profile for the no-return call is not
3527 dumped and there can be a mismatch. */
3528 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3529 && call_count
> profile_info
->runs
)
3531 if (flag_profile_correction
)
3535 "Missing counts for called function %s\n",
3536 node
->dump_name ());
3539 warning (0, "Missing counts for called function %s",
3540 node
->dump_name ());
3544 if (opt_for_fn (node
->decl
, flag_guess_branch_prob
))
3547 = !ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
.nonzero_p ();
3548 FOR_ALL_BB_FN (bb
, fn
)
3549 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3550 bb
->count
= bb
->count
.guessed_local ();
3551 fn
->cfg
->count_max
= fn
->cfg
->count_max
.guessed_local ();
3555 FOR_ALL_BB_FN (bb
, fn
)
3556 bb
->count
= profile_count::uninitialized ();
3557 fn
->cfg
->count_max
= profile_count::uninitialized ();
3560 struct cgraph_edge
*e
;
3561 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3562 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3563 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3564 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3565 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
;
3567 profile_status_for_fn (fn
)
3568 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3570 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3573 /* In the case of COMDAT routines, multiple object files will contain the same
3574 function and the linker will select one for the binary. In that case
3575 all the other copies from the profile instrument binary will be missing
3576 profile counts. Look for cases where this happened, due to non-zero
3577 call counts going to 0-count functions, and drop the profile to guessed
3578 so that we can use the estimated probabilities and avoid optimizing only
3581 The other case where the profile may be missing is when the routine
3582 is not going to be emitted to the object file, e.g. for "extern template"
3583 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3584 all other cases of non-zero calls to 0-count functions. */
3587 handle_missing_profiles (void)
3589 const int unlikely_frac
= param_unlikely_bb_count_fraction
;
3590 struct cgraph_node
*node
;
3591 auto_vec
<struct cgraph_node
*, 64> worklist
;
3593 /* See if 0 count function has non-0 count callers. In this case we
3594 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3595 FOR_EACH_DEFINED_FUNCTION (node
)
3597 struct cgraph_edge
*e
;
3598 profile_count call_count
= profile_count::zero ();
3599 gcov_type max_tp_first_run
= 0;
3600 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3602 if (node
->count
.ipa ().nonzero_p ())
3604 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3605 if (e
->count
.ipa ().initialized_p () && e
->count
.ipa () > 0)
3607 call_count
= call_count
+ e
->count
.ipa ();
3609 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3610 max_tp_first_run
= e
->caller
->tp_first_run
;
3613 /* If time profile is missing, let assign the maximum that comes from
3614 caller functions. */
3615 if (!node
->tp_first_run
&& max_tp_first_run
)
3616 node
->tp_first_run
= max_tp_first_run
+ 1;
3620 && call_count
.apply_scale (unlikely_frac
, 1) >= profile_info
->runs
)
3622 drop_profile (node
, call_count
);
3623 worklist
.safe_push (node
);
3627 /* Propagate the profile dropping to other 0-count COMDATs that are
3628 potentially called by COMDATs we already dropped the profile on. */
3629 while (worklist
.length () > 0)
3631 struct cgraph_edge
*e
;
3633 node
= worklist
.pop ();
3634 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3636 struct cgraph_node
*callee
= e
->callee
;
3637 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3639 if (!(e
->count
.ipa () == profile_count::zero ())
3640 && callee
->count
.ipa ().nonzero_p ())
3642 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3644 && profile_status_for_fn (fn
) == PROFILE_READ
)
3646 drop_profile (node
, profile_count::zero ());
3647 worklist
.safe_push (callee
);
3653 /* Convert counts measured by profile driven feedback to frequencies.
3654 Return nonzero iff there was any nonzero execution count. */
3657 update_max_bb_count (void)
3659 profile_count true_count_max
= profile_count::uninitialized ();
3662 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3663 true_count_max
= true_count_max
.max (bb
->count
);
3665 cfun
->cfg
->count_max
= true_count_max
;
3667 return true_count_max
.ipa ().nonzero_p ();
3670 /* Return true if function is likely to be expensive, so there is no point to
3671 optimize performance of prologue, epilogue or do inlining at the expense
3672 of code size growth. THRESHOLD is the limit of number of instructions
3673 function can execute at average to be still considered not expensive. */
3676 expensive_function_p (int threshold
)
3680 /* If profile was scaled in a way entry block has count 0, then the function
3681 is deifnitly taking a lot of time. */
3682 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3685 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN
3686 (cfun
)->count
.apply_scale (threshold
, 1);
3687 profile_count sum
= profile_count::zero ();
3688 FOR_EACH_BB_FN (bb
, cfun
)
3692 if (!bb
->count
.initialized_p ())
3695 fprintf (dump_file
, "Function is considered expensive because"
3696 " count of bb %i is not initialized\n", bb
->index
);
3700 FOR_BB_INSNS (bb
, insn
)
3701 if (active_insn_p (insn
))
3712 /* All basic blocks that are reachable only from unlikely basic blocks are
3716 propagate_unlikely_bbs_forward (void)
3718 auto_vec
<basic_block
, 64> worklist
;
3723 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3725 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3726 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3728 while (worklist
.length () > 0)
3730 bb
= worklist
.pop ();
3731 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3732 if (!(e
->count () == profile_count::zero ())
3733 && !(e
->dest
->count
== profile_count::zero ())
3736 e
->dest
->aux
= (void *)(size_t) 1;
3737 worklist
.safe_push (e
->dest
);
3742 FOR_ALL_BB_FN (bb
, cfun
)
3746 if (!(bb
->count
== profile_count::zero ())
3747 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3749 "Basic block %i is marked unlikely by forward prop\n",
3751 bb
->count
= profile_count::zero ();
3758 /* Determine basic blocks/edges that are known to be unlikely executed and set
3759 their counters to zero.
3760 This is done with first identifying obviously unlikely BBs/edges and then
3761 propagating in both directions. */
3764 determine_unlikely_bbs ()
3767 auto_vec
<basic_block
, 64> worklist
;
3771 FOR_EACH_BB_FN (bb
, cfun
)
3773 if (!(bb
->count
== profile_count::zero ())
3774 && unlikely_executed_bb_p (bb
))
3776 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3777 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3779 bb
->count
= profile_count::zero ();
3782 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3783 if (!(e
->probability
== profile_probability::never ())
3784 && unlikely_executed_edge_p (e
))
3786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3787 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3788 bb
->index
, e
->dest
->index
);
3789 e
->probability
= profile_probability::never ();
3792 gcc_checking_assert (!bb
->aux
);
3794 propagate_unlikely_bbs_forward ();
3796 auto_vec
<int, 64> nsuccs
;
3797 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
), true);
3798 FOR_ALL_BB_FN (bb
, cfun
)
3799 if (!(bb
->count
== profile_count::zero ())
3800 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3802 nsuccs
[bb
->index
] = 0;
3803 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3804 if (!(e
->probability
== profile_probability::never ())
3805 && !(e
->dest
->count
== profile_count::zero ()))
3806 nsuccs
[bb
->index
]++;
3807 if (!nsuccs
[bb
->index
])
3808 worklist
.safe_push (bb
);
3810 while (worklist
.length () > 0)
3812 bb
= worklist
.pop ();
3813 if (bb
->count
== profile_count::zero ())
3815 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3818 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3819 !gsi_end_p (gsi
); gsi_next (&gsi
))
3820 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3821 /* stmt_can_terminate_bb_p special cases noreturns because it
3822 assumes that fake edges are created. We want to know that
3823 noreturn alone does not imply BB to be unlikely. */
3824 || (is_gimple_call (gsi_stmt (gsi
))
3825 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3833 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3835 "Basic block %i is marked unlikely by backward prop\n",
3837 bb
->count
= profile_count::zero ();
3838 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3839 if (!(e
->probability
== profile_probability::never ()))
3841 if (!(e
->src
->count
== profile_count::zero ()))
3843 gcc_checking_assert (nsuccs
[e
->src
->index
] > 0);
3844 nsuccs
[e
->src
->index
]--;
3845 if (!nsuccs
[e
->src
->index
])
3846 worklist
.safe_push (e
->src
);
3850 /* Finally all edges from non-0 regions to 0 are unlikely. */
3851 FOR_ALL_BB_FN (bb
, cfun
)
3853 if (!(bb
->count
== profile_count::zero ()))
3854 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3855 if (!(e
->probability
== profile_probability::never ())
3856 && e
->dest
->count
== profile_count::zero ())
3858 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3859 fprintf (dump_file
, "Edge %i->%i is unlikely because "
3860 "it enters unlikely block\n",
3861 bb
->index
, e
->dest
->index
);
3862 e
->probability
= profile_probability::never ();
3867 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3868 if (e
->probability
== profile_probability::never ())
3878 && !(other
->probability
== profile_probability::always ()))
3880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3881 fprintf (dump_file
, "Edge %i->%i is locally likely\n",
3882 bb
->index
, other
->dest
->index
);
3883 other
->probability
= profile_probability::always ();
3886 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3887 cgraph_node::get (current_function_decl
)->count
= profile_count::zero ();
3890 /* Estimate and propagate basic block frequencies using the given branch
3891 probabilities. If FORCE is true, the frequencies are used to estimate
3892 the counts even when there are already non-zero profile counts. */
3895 estimate_bb_frequencies (bool force
)
3900 determine_unlikely_bbs ();
3902 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3903 || !update_max_bb_count ())
3906 mark_dfs_back_edges ();
3908 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3909 profile_probability::always ();
3911 /* Set up block info for each basic block. */
3912 alloc_aux_for_blocks (sizeof (block_info
));
3913 alloc_aux_for_edges (sizeof (edge_prob_info
));
3914 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3919 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3921 /* FIXME: Graphite is producing edges with no profile. Once
3922 this is fixed, drop this. */
3923 if (e
->probability
.initialized_p ())
3924 EDGE_INFO (e
)->back_edge_prob
3925 = e
->probability
.to_sreal ();
3927 /* back_edge_prob = 0.5 */
3928 EDGE_INFO (e
)->back_edge_prob
= sreal (1, -1);
3932 /* First compute frequencies locally for each loop from innermost
3933 to outermost to examine frequencies for back edges. */
3937 FOR_EACH_BB_FN (bb
, cfun
)
3938 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3939 freq_max
= BLOCK_INFO (bb
)->frequency
;
3941 /* Scaling frequencies up to maximal profile count may result in
3942 frequent overflows especially when inlining loops.
3943 Small scalling results in unnecesary precision loss. Stay in
3944 the half of the (exponential) range. */
3945 freq_max
= (sreal (1) << (profile_count::n_bits
/ 2)) / freq_max
;
3948 profile_count ipa_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ();
3949 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3950 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3952 sreal tmp
= BLOCK_INFO (bb
)->frequency
;
3955 gimple_stmt_iterator gsi
;
3958 /* Self recursive calls can not have frequency greater than 1
3959 or program will never terminate. This will result in an
3960 inconsistent bb profile but it is better than greatly confusing
3961 IPA cost metrics. */
3962 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3963 if (is_gimple_call (gsi_stmt (gsi
))
3964 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
3965 && recursive_call_p (current_function_decl
, decl
))
3968 fprintf (dump_file
, "Dropping frequency of recursive call"
3969 " in bb %i from %f\n", bb
->index
,
3971 tmp
= (sreal
)9 / (sreal
)10;
3975 tmp
= tmp
* freq_max
+ sreal (1, -1);
3976 profile_count count
= profile_count::from_gcov_type (tmp
.to_int ());
3978 /* If we have profile feedback in which this function was never
3979 executed, then preserve this info. */
3980 if (!(bb
->count
== profile_count::zero ()))
3981 bb
->count
= count
.guessed_local ().combine_with_ipa_count (ipa_count
);
3982 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3985 free_aux_for_blocks ();
3986 free_aux_for_edges ();
3988 compute_function_frequency ();
3991 /* Decide whether function is hot, cold or unlikely executed. */
3993 compute_function_frequency (void)
3996 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3998 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3999 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
4000 node
->only_called_at_startup
= true;
4001 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
4002 node
->only_called_at_exit
= true;
4004 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ())
4006 int flags
= flags_from_decl_or_type (current_function_decl
);
4007 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
4009 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
4010 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
4012 node
->frequency
= NODE_FREQUENCY_HOT
;
4013 else if (flags
& ECF_NORETURN
)
4014 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4015 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
4016 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4017 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
4018 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
4019 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
4023 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
4024 warn_function_cold (current_function_decl
);
4025 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
4027 FOR_EACH_BB_FN (bb
, cfun
)
4029 if (maybe_hot_bb_p (cfun
, bb
))
4031 node
->frequency
= NODE_FREQUENCY_HOT
;
4034 if (!probably_never_executed_bb_p (cfun
, bb
))
4035 node
->frequency
= NODE_FREQUENCY_NORMAL
;
4039 /* Build PREDICT_EXPR. */
4041 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
4043 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
4044 build_int_cst (integer_type_node
, predictor
));
4045 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
4050 predictor_name (enum br_predictor predictor
)
4052 return predictor_info
[predictor
].name
;
4055 /* Predict branch probabilities and estimate profile of the tree CFG. */
4059 const pass_data pass_data_profile
=
4061 GIMPLE_PASS
, /* type */
4062 "profile_estimate", /* name */
4063 OPTGROUP_NONE
, /* optinfo_flags */
4064 TV_BRANCH_PROB
, /* tv_id */
4065 PROP_cfg
, /* properties_required */
4066 0, /* properties_provided */
4067 0, /* properties_destroyed */
4068 0, /* todo_flags_start */
4069 0, /* todo_flags_finish */
4072 class pass_profile
: public gimple_opt_pass
4075 pass_profile (gcc::context
*ctxt
)
4076 : gimple_opt_pass (pass_data_profile
, ctxt
)
4079 /* opt_pass methods: */
4080 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
4081 virtual unsigned int execute (function
*);
4083 }; // class pass_profile
4086 pass_profile::execute (function
*fun
)
4090 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4093 loop_optimizer_init (LOOPS_NORMAL
);
4094 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4095 flow_loops_dump (dump_file
, NULL
, 0);
4097 nb_loops
= number_of_loops (fun
);
4101 tree_estimate_probability (false);
4106 loop_optimizer_finalize ();
4107 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4108 gimple_dump_cfg (dump_file
, dump_flags
);
4109 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
4110 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
4111 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4113 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
4114 if (loop
->header
->count
.initialized_p ())
4115 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
4117 (int)expected_loop_iterations_unbounded (loop
));
4125 make_pass_profile (gcc::context
*ctxt
)
4127 return new pass_profile (ctxt
);
4130 /* Return true when PRED predictor should be removed after early
4131 tree passes. Most of the predictors are beneficial to survive
4132 as early inlining can also distribute then into caller's bodies. */
4135 strip_predictor_early (enum br_predictor pred
)
4139 case PRED_TREE_EARLY_RETURN
:
4146 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4147 we no longer need. EARLY is set to true when called from early
4151 strip_predict_hints (function
*fun
, bool early
)
4156 bool changed
= false;
4158 FOR_EACH_BB_FN (bb
, fun
)
4160 gimple_stmt_iterator bi
;
4161 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
4163 gimple
*stmt
= gsi_stmt (bi
);
4165 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
4168 || strip_predictor_early (gimple_predict_predictor (stmt
)))
4170 gsi_remove (&bi
, true);
4175 else if (is_gimple_call (stmt
))
4177 tree fndecl
= gimple_call_fndecl (stmt
);
4180 && ((fndecl
!= NULL_TREE
4181 && fndecl_built_in_p (fndecl
, BUILT_IN_EXPECT
)
4182 && gimple_call_num_args (stmt
) == 2)
4183 || (fndecl
!= NULL_TREE
4184 && fndecl_built_in_p (fndecl
,
4185 BUILT_IN_EXPECT_WITH_PROBABILITY
)
4186 && gimple_call_num_args (stmt
) == 3)
4187 || (gimple_call_internal_p (stmt
)
4188 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
)))
4190 var
= gimple_call_lhs (stmt
);
4195 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
4196 gsi_replace (&bi
, ass_stmt
, true);
4200 gsi_remove (&bi
, true);
4208 return changed
? TODO_cleanup_cfg
: 0;
4213 const pass_data pass_data_strip_predict_hints
=
4215 GIMPLE_PASS
, /* type */
4216 "*strip_predict_hints", /* name */
4217 OPTGROUP_NONE
, /* optinfo_flags */
4218 TV_BRANCH_PROB
, /* tv_id */
4219 PROP_cfg
, /* properties_required */
4220 0, /* properties_provided */
4221 0, /* properties_destroyed */
4222 0, /* todo_flags_start */
4223 0, /* todo_flags_finish */
4226 class pass_strip_predict_hints
: public gimple_opt_pass
4229 pass_strip_predict_hints (gcc::context
*ctxt
)
4230 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
4233 /* opt_pass methods: */
4234 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
4235 void set_pass_param (unsigned int n
, bool param
)
4237 gcc_assert (n
== 0);
4241 virtual unsigned int execute (function
*);
4246 }; // class pass_strip_predict_hints
4249 pass_strip_predict_hints::execute (function
*fun
)
4251 return strip_predict_hints (fun
, early_p
);
4257 make_pass_strip_predict_hints (gcc::context
*ctxt
)
4259 return new pass_strip_predict_hints (ctxt
);
4262 /* Rebuild function frequencies. Passes are in general expected to
4263 maintain profile by hand, however in some cases this is not possible:
4264 for example when inlining several functions with loops freuqencies might run
4265 out of scale and thus needs to be recomputed. */
4268 rebuild_frequencies (void)
4270 timevar_push (TV_REBUILD_FREQUENCIES
);
4272 /* When the max bb count in the function is small, there is a higher
4273 chance that there were truncation errors in the integer scaling
4274 of counts by inlining and other optimizations. This could lead
4275 to incorrect classification of code as being cold when it isn't.
4276 In that case, force the estimation of bb counts/frequencies from the
4277 branch probabilities, rather than computing frequencies from counts,
4278 which may also lead to frequencies incorrectly reduced to 0. There
4279 is less precision in the probabilities, so we only do this for small
4281 cfun
->cfg
->count_max
= profile_count::uninitialized ();
4283 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
4284 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
4286 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4288 loop_optimizer_init (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
);
4289 connect_infinite_loops_to_exit ();
4290 estimate_bb_frequencies (true);
4291 remove_fake_exit_edges ();
4292 loop_optimizer_finalize ();
4294 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
4295 update_max_bb_count ();
4296 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
4297 && !flag_guess_branch_prob
)
4301 timevar_pop (TV_REBUILD_FREQUENCIES
);
4304 /* Perform a dry run of the branch prediction pass and report comparsion of
4305 the predicted and real profile into the dump file. */
4308 report_predictor_hitrates (void)
4312 loop_optimizer_init (LOOPS_NORMAL
);
4313 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4314 flow_loops_dump (dump_file
, NULL
, 0);
4316 nb_loops
= number_of_loops (cfun
);
4320 tree_estimate_probability (true);
4325 loop_optimizer_finalize ();
4328 /* Force edge E to be cold.
4329 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4330 keep low probability to represent possible error in a guess. This is used
4331 i.e. in case we predict loop to likely iterate given number of times but
4332 we are not 100% sure.
4334 This function locally updates profile without attempt to keep global
4335 consistency which cannot be reached in full generality without full profile
4336 rebuild from probabilities alone. Doing so is not necessarily a good idea
4337 because frequencies and counts may be more realistic then probabilities.
4339 In some cases (such as for elimination of early exits during full loop
4340 unrolling) the caller can ensure that profile will get consistent
4344 force_edge_cold (edge e
, bool impossible
)
4346 profile_count count_sum
= profile_count::zero ();
4347 profile_probability prob_sum
= profile_probability::never ();
4350 bool uninitialized_exit
= false;
4352 /* When branch probability guesses are not known, then do nothing. */
4353 if (!impossible
&& !e
->count ().initialized_p ())
4356 profile_probability goal
= (impossible
? profile_probability::never ()
4357 : profile_probability::very_unlikely ());
4359 /* If edge is already improbably or cold, just return. */
4360 if (e
->probability
<= goal
4361 && (!impossible
|| e
->count () == profile_count::zero ()))
4363 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4366 if (e
->flags
& EDGE_FAKE
)
4368 if (e2
->count ().initialized_p ())
4369 count_sum
+= e2
->count ();
4370 if (e2
->probability
.initialized_p ())
4371 prob_sum
+= e2
->probability
;
4373 uninitialized_exit
= true;
4376 /* If we are not guessing profiles but have some other edges out,
4377 just assume the control flow goes elsewhere. */
4378 if (uninitialized_exit
)
4379 e
->probability
= goal
;
4380 /* If there are other edges out of e->src, redistribute probabilitity
4382 else if (prob_sum
> profile_probability::never ())
4384 if (!(e
->probability
< goal
))
4385 e
->probability
= goal
;
4387 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
4389 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4390 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
4391 "probability to other edges.\n",
4392 e
->src
->index
, e
->dest
->index
,
4393 impossible
? "impossible" : "cold");
4394 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4397 e2
->probability
/= prob_comp
;
4399 if (current_ir_type () != IR_GIMPLE
4400 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4401 update_br_prob_note (e
->src
);
4403 /* If all edges out of e->src are unlikely, the basic block itself
4407 if (prob_sum
== profile_probability::never ())
4408 e
->probability
= profile_probability::always ();
4412 e
->probability
= profile_probability::never ();
4413 /* If BB has some edges out that are not impossible, we cannot
4414 assume that BB itself is. */
4417 if (current_ir_type () != IR_GIMPLE
4418 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4419 update_br_prob_note (e
->src
);
4420 if (e
->src
->count
== profile_count::zero ())
4422 if (count_sum
== profile_count::zero () && impossible
)
4425 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4427 else if (current_ir_type () == IR_GIMPLE
)
4428 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4429 !gsi_end_p (gsi
); gsi_next (&gsi
))
4431 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4437 /* FIXME: Implement RTL path. */
4442 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4444 "Making bb %i impossible and dropping count to 0.\n",
4446 e
->src
->count
= profile_count::zero ();
4447 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4448 force_edge_cold (e2
, impossible
);
4453 /* If we did not adjusting, the source basic block has no likely edeges
4454 leaving other direction. In that case force that bb cold, too.
4455 This in general is difficult task to do, but handle special case when
4456 BB has only one predecestor. This is common case when we are updating
4457 after loop transforms. */
4458 if (!(prob_sum
> profile_probability::never ())
4459 && count_sum
== profile_count::zero ()
4460 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4461 > (impossible
? 0 : 1))
4463 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4465 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4466 impossible
? "impossible" : "cold");
4467 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4468 impossible
? 0 : 1);
4470 e
->src
->count
= profile_count::zero ();
4472 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4474 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4476 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4477 && maybe_hot_bb_p (cfun
, e
->src
))
4478 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4479 impossible
? "impossible" : "cold");
4483 /* Change E's probability to NEW_E_PROB, redistributing the probabilities
4484 of other outgoing edges proportionally.
4486 Note that this function does not change the profile counts of any
4487 basic blocks. The caller must do that instead, using whatever
4488 information it has about the region that needs updating. */
4491 change_edge_frequency (edge e
, profile_probability new_e_prob
)
4493 profile_probability old_e_prob
= e
->probability
;
4494 profile_probability old_other_prob
= old_e_prob
.invert ();
4495 profile_probability new_other_prob
= new_e_prob
.invert ();
4497 e
->probability
= new_e_prob
;
4498 profile_probability cumulative_prob
= new_e_prob
;
4500 unsigned int num_other
= EDGE_COUNT (e
->src
->succs
) - 1;
4503 FOR_EACH_EDGE (other_e
, ei
, e
->src
->succs
)
4508 /* Ensure that the probabilities add up to 1 without
4510 other_e
->probability
= cumulative_prob
.invert ();
4513 other_e
->probability
/= old_other_prob
;
4514 other_e
->probability
*= new_other_prob
;
4515 cumulative_prob
+= other_e
->probability
;
4522 namespace selftest
{
4524 /* Test that value range of predictor values defined in predict.def is
4525 within range (50, 100]. */
4527 struct branch_predictor
4533 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4536 test_prediction_value_range ()
4538 branch_predictor predictors
[] = {
4539 #include "predict.def"
4540 { NULL
, PROB_UNINITIALIZED
}
4543 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4545 if (predictors
[i
].probability
== PROB_UNINITIALIZED
)
4548 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4549 ASSERT_TRUE (p
>= 50 && p
<= 100);
4553 #undef DEF_PREDICTOR
4555 /* Run all of the selfests within this file. */
4560 test_prediction_value_range ();
4563 } // namespace selftest
4564 #endif /* CHECKING_P. */