1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 [1] "Branch Prediction for Free"
23 Ball and Larus; PLDI '93.
24 [2] "Static Branch Frequency and Program Profile Analysis"
25 Wu and Larus; MICRO-27.
26 [3] "Corpus-based Static Branch Prediction"
27 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
32 #include "coretypes.h"
38 #include "tree-pass.h"
44 #include "diagnostic-core.h"
45 #include "gimple-predict.h"
46 #include "fold-const.h"
53 #include "gimple-iterator.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-scalar-evolution.h"
58 #include "ipa-utils.h"
59 #include "gimple-pretty-print.h"
62 #include "stringpool.h"
65 /* Enum with reasons why a predictor is ignored. */
71 REASON_SINGLE_EDGE_DUPLICATE
,
72 REASON_EDGE_PAIR_DUPLICATE
75 /* String messages for the aforementioned enum. */
77 static const char *reason_messages
[] = {"", " (ignored)",
78 " (single edge duplicate)", " (edge pair duplicate)"};
80 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
81 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
82 static sreal real_almost_one
, real_br_prob_base
,
83 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
85 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
86 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
,
87 enum predictor_reason
, edge
);
88 static void predict_paths_leading_to (basic_block
, enum br_predictor
,
90 struct loop
*in_loop
= NULL
);
91 static void predict_paths_leading_to_edge (edge
, enum br_predictor
,
93 struct loop
*in_loop
= NULL
);
94 static bool can_predict_insn_p (const rtx_insn
*);
95 static HOST_WIDE_INT
get_predictor_value (br_predictor
, HOST_WIDE_INT
);
96 static void determine_unlikely_bbs ();
98 /* Information we hold about each branch predictor.
99 Filled using information from predict.def. */
101 struct predictor_info
103 const char *const name
; /* Name used in the debugging dumps. */
104 const int hitrate
; /* Expected hitrate used by
105 predict_insn_def call. */
109 /* Use given predictor without Dempster-Shaffer theory if it matches
110 using first_match heuristics. */
111 #define PRED_FLAG_FIRST_MATCH 1
113 /* Recompute hitrate in percent to our representation. */
115 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
117 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
118 static const struct predictor_info predictor_info
[]= {
119 #include "predict.def"
121 /* Upper bound on predictors. */
126 static gcov_type min_count
= -1;
128 /* Determine the threshold for hot BB counts. */
131 get_hot_bb_threshold ()
136 = profile_info
->sum_max
/ PARAM_VALUE (HOT_BB_COUNT_FRACTION
);
138 fprintf (dump_file
, "Setting hotness threshold to %" PRId64
".\n",
144 /* Set the threshold for hot BB counts. */
147 set_hot_bb_threshold (gcov_type min
)
152 /* Return TRUE if frequency FREQ is considered to be hot. */
155 maybe_hot_count_p (struct function
*fun
, profile_count count
)
157 if (!count
.initialized_p ())
159 if (count
.ipa () == profile_count::zero ())
163 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
164 if (!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
166 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
168 if (node
->frequency
== NODE_FREQUENCY_HOT
)
171 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
173 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
174 && count
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
.apply_scale (2, 3)))
176 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
178 if (count
.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
), 1)
179 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
183 /* Code executed at most once is not hot. */
184 if (count
<= MAX (profile_info
? profile_info
->runs
: 1, 1))
186 return (count
.to_gcov_type () >= get_hot_bb_threshold ());
189 /* Return true in case BB can be CPU intensive and should be optimized
190 for maximal performance. */
193 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
195 gcc_checking_assert (fun
);
196 return maybe_hot_count_p (fun
, bb
->count
);
199 /* Return true in case BB can be CPU intensive and should be optimized
200 for maximal performance. */
203 maybe_hot_edge_p (edge e
)
205 return maybe_hot_count_p (cfun
, e
->count ());
208 /* Return true if profile COUNT and FREQUENCY, or function FUN static
209 node frequency reflects never being executed. */
212 probably_never_executed (struct function
*fun
,
215 gcc_checking_assert (fun
);
216 if (count
.ipa () == profile_count::zero ())
218 /* Do not trust adjusted counts. This will make us to drop int cold section
219 code with low execution count as a result of inlining. These low counts
220 are not safe even with read profile and may lead us to dropping
221 code which actually gets executed into cold section of binary that is not
223 if (count
.precise_p () && profile_status_for_fn (fun
) == PROFILE_READ
)
225 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
226 if (count
.apply_scale (unlikely_count_fraction
, 1) >= profile_info
->runs
)
230 if ((!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
231 && (cgraph_node::get (fun
->decl
)->frequency
232 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
238 /* Return true in case BB is probably never executed. */
241 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
243 return probably_never_executed (fun
, bb
->count
);
247 /* Return true if E is unlikely executed for obvious reasons. */
250 unlikely_executed_edge_p (edge e
)
252 return (e
->count () == profile_count::zero ()
253 || e
->probability
== profile_probability::never ())
254 || (e
->flags
& (EDGE_EH
| EDGE_FAKE
));
257 /* Return true in case edge E is probably never executed. */
260 probably_never_executed_edge_p (struct function
*fun
, edge e
)
262 if (unlikely_executed_edge_p (e
))
264 return probably_never_executed (fun
, e
->count ());
267 /* Return true when current function should always be optimized for size. */
270 optimize_function_for_size_p (struct function
*fun
)
272 if (!fun
|| !fun
->decl
)
273 return optimize_size
;
274 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
275 return n
&& n
->optimize_for_size_p ();
278 /* Return true when current function should always be optimized for speed. */
281 optimize_function_for_speed_p (struct function
*fun
)
283 return !optimize_function_for_size_p (fun
);
286 /* Return the optimization type that should be used for the function FUN. */
289 function_optimization_type (struct function
*fun
)
291 return (optimize_function_for_speed_p (fun
)
293 : OPTIMIZE_FOR_SIZE
);
296 /* Return TRUE when BB should be optimized for size. */
299 optimize_bb_for_size_p (const_basic_block bb
)
301 return (optimize_function_for_size_p (cfun
)
302 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
305 /* Return TRUE when BB should be optimized for speed. */
308 optimize_bb_for_speed_p (const_basic_block bb
)
310 return !optimize_bb_for_size_p (bb
);
313 /* Return the optimization type that should be used for block BB. */
316 bb_optimization_type (const_basic_block bb
)
318 return (optimize_bb_for_speed_p (bb
)
320 : OPTIMIZE_FOR_SIZE
);
323 /* Return TRUE when BB should be optimized for size. */
326 optimize_edge_for_size_p (edge e
)
328 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
331 /* Return TRUE when BB should be optimized for speed. */
334 optimize_edge_for_speed_p (edge e
)
336 return !optimize_edge_for_size_p (e
);
339 /* Return TRUE when BB should be optimized for size. */
342 optimize_insn_for_size_p (void)
344 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
347 /* Return TRUE when BB should be optimized for speed. */
350 optimize_insn_for_speed_p (void)
352 return !optimize_insn_for_size_p ();
355 /* Return TRUE when LOOP should be optimized for size. */
358 optimize_loop_for_size_p (struct loop
*loop
)
360 return optimize_bb_for_size_p (loop
->header
);
363 /* Return TRUE when LOOP should be optimized for speed. */
366 optimize_loop_for_speed_p (struct loop
*loop
)
368 return optimize_bb_for_speed_p (loop
->header
);
371 /* Return TRUE when LOOP nest should be optimized for speed. */
374 optimize_loop_nest_for_speed_p (struct loop
*loop
)
376 struct loop
*l
= loop
;
377 if (optimize_loop_for_speed_p (loop
))
380 while (l
&& l
!= loop
)
382 if (optimize_loop_for_speed_p (l
))
390 while (l
!= loop
&& !l
->next
)
399 /* Return TRUE when LOOP nest should be optimized for size. */
402 optimize_loop_nest_for_size_p (struct loop
*loop
)
404 return !optimize_loop_nest_for_speed_p (loop
);
407 /* Return true when edge E is likely to be well predictable by branch
411 predictable_edge_p (edge e
)
413 if (!e
->probability
.initialized_p ())
415 if ((e
->probability
.to_reg_br_prob_base ()
416 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
417 || (REG_BR_PROB_BASE
- e
->probability
.to_reg_br_prob_base ()
418 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
424 /* Set RTL expansion for BB profile. */
427 rtl_profile_for_bb (basic_block bb
)
429 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
432 /* Set RTL expansion for edge profile. */
435 rtl_profile_for_edge (edge e
)
437 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
440 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
442 default_rtl_profile (void)
444 crtl
->maybe_hot_insn_p
= true;
447 /* Return true if the one of outgoing edges is already predicted by
451 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
454 if (!INSN_P (BB_END (bb
)))
456 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
457 if (REG_NOTE_KIND (note
) == REG_BR_PRED
458 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
463 /* Structure representing predictions in tree level. */
465 struct edge_prediction
{
466 struct edge_prediction
*ep_next
;
468 enum br_predictor ep_predictor
;
472 /* This map contains for a basic block the list of predictions for the
475 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
477 /* Return true if the one of outgoing edges is already predicted by
481 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
483 struct edge_prediction
*i
;
484 edge_prediction
**preds
= bb_predictions
->get (bb
);
489 for (i
= *preds
; i
; i
= i
->ep_next
)
490 if (i
->ep_predictor
== predictor
)
495 /* Return true if the one of outgoing edges is already predicted by
496 PREDICTOR for edge E predicted as TAKEN. */
499 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
501 struct edge_prediction
*i
;
502 basic_block bb
= e
->src
;
503 edge_prediction
**preds
= bb_predictions
->get (bb
);
507 int probability
= predictor_info
[(int) predictor
].hitrate
;
510 probability
= REG_BR_PROB_BASE
- probability
;
512 for (i
= *preds
; i
; i
= i
->ep_next
)
513 if (i
->ep_predictor
== predictor
515 && i
->ep_probability
== probability
)
520 /* Same predicate as above, working on edges. */
522 edge_probability_reliable_p (const_edge e
)
524 return e
->probability
.probably_reliable_p ();
527 /* Same predicate as edge_probability_reliable_p, working on notes. */
529 br_prob_note_reliable_p (const_rtx note
)
531 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
532 return profile_probability::from_reg_br_prob_note
533 (XINT (note
, 0)).probably_reliable_p ();
537 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
539 gcc_assert (any_condjump_p (insn
));
540 if (!flag_guess_branch_prob
)
543 add_reg_note (insn
, REG_BR_PRED
,
544 gen_rtx_CONCAT (VOIDmode
,
545 GEN_INT ((int) predictor
),
546 GEN_INT ((int) probability
)));
549 /* Predict insn by given predictor. */
552 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
553 enum prediction taken
)
555 int probability
= predictor_info
[(int) predictor
].hitrate
;
556 gcc_assert (probability
!= PROB_UNINITIALIZED
);
559 probability
= REG_BR_PROB_BASE
- probability
;
561 predict_insn (insn
, predictor
, probability
);
564 /* Predict edge E with given probability if possible. */
567 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
570 last_insn
= BB_END (e
->src
);
572 /* We can store the branch prediction information only about
573 conditional jumps. */
574 if (!any_condjump_p (last_insn
))
577 /* We always store probability of branching. */
578 if (e
->flags
& EDGE_FALLTHRU
)
579 probability
= REG_BR_PROB_BASE
- probability
;
581 predict_insn (last_insn
, predictor
, probability
);
584 /* Predict edge E with the given PROBABILITY. */
586 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
588 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
589 && EDGE_COUNT (e
->src
->succs
) > 1
590 && flag_guess_branch_prob
593 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
594 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
598 i
->ep_probability
= probability
;
599 i
->ep_predictor
= predictor
;
604 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
605 to the filter function. */
608 filter_predictions (edge_prediction
**preds
,
609 bool (*filter
) (edge_prediction
*, void *), void *data
)
616 struct edge_prediction
**prediction
= preds
;
617 struct edge_prediction
*next
;
621 if ((*filter
) (*prediction
, data
))
622 prediction
= &((*prediction
)->ep_next
);
625 next
= (*prediction
)->ep_next
;
633 /* Filter function predicate that returns true for a edge predicate P
634 if its edge is equal to DATA. */
637 equal_edge_p (edge_prediction
*p
, void *data
)
639 return p
->ep_edge
== (edge
)data
;
642 /* Remove all predictions on given basic block that are attached
645 remove_predictions_associated_with_edge (edge e
)
650 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
651 filter_predictions (preds
, equal_edge_p
, e
);
654 /* Clears the list of predictions stored for BB. */
657 clear_bb_predictions (basic_block bb
)
659 edge_prediction
**preds
= bb_predictions
->get (bb
);
660 struct edge_prediction
*pred
, *next
;
665 for (pred
= *preds
; pred
; pred
= next
)
667 next
= pred
->ep_next
;
673 /* Return true when we can store prediction on insn INSN.
674 At the moment we represent predictions only on conditional
675 jumps, not at computed jump or other complicated cases. */
677 can_predict_insn_p (const rtx_insn
*insn
)
679 return (JUMP_P (insn
)
680 && any_condjump_p (insn
)
681 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
684 /* Predict edge E by given predictor if possible. */
687 predict_edge_def (edge e
, enum br_predictor predictor
,
688 enum prediction taken
)
690 int probability
= predictor_info
[(int) predictor
].hitrate
;
693 probability
= REG_BR_PROB_BASE
- probability
;
695 predict_edge (e
, predictor
, probability
);
698 /* Invert all branch predictions or probability notes in the INSN. This needs
699 to be done each time we invert the condition used by the jump. */
702 invert_br_probabilities (rtx insn
)
706 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
707 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
708 XINT (note
, 0) = profile_probability::from_reg_br_prob_note
709 (XINT (note
, 0)).invert ().to_reg_br_prob_note ();
710 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
711 XEXP (XEXP (note
, 0), 1)
712 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
715 /* Dump information about the branch prediction to the output file. */
718 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
719 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
729 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
730 if (! (e
->flags
& EDGE_FALLTHRU
))
733 char edge_info_str
[128];
735 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
736 ep_edge
->dest
->index
);
738 edge_info_str
[0] = '\0';
740 fprintf (file
, " %s heuristics%s%s: %.2f%%",
741 predictor_info
[predictor
].name
,
742 edge_info_str
, reason_messages
[reason
],
743 probability
* 100.0 / REG_BR_PROB_BASE
);
745 if (bb
->count
.initialized_p ())
747 fprintf (file
, " exec ");
748 bb
->count
.dump (file
);
751 fprintf (file
, " hit ");
752 e
->count ().dump (file
);
753 fprintf (file
, " (%.1f%%)", e
->count ().to_gcov_type() * 100.0
754 / bb
->count
.to_gcov_type ());
758 fprintf (file
, "\n");
760 /* Print output that be easily read by analyze_brprob.py script. We are
761 interested only in counts that are read from GCDA files. */
762 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
763 && bb
->count
.precise_p ()
764 && reason
== REASON_NONE
)
766 gcc_assert (e
->count ().precise_p ());
767 fprintf (file
, ";;heuristics;%s;%" PRId64
";%" PRId64
";%.1f;\n",
768 predictor_info
[predictor
].name
,
769 bb
->count
.to_gcov_type (), e
->count ().to_gcov_type (),
770 probability
* 100.0 / REG_BR_PROB_BASE
);
774 /* Return true if STMT is known to be unlikely executed. */
777 unlikely_executed_stmt_p (gimple
*stmt
)
779 if (!is_gimple_call (stmt
))
781 /* NORETURN attribute alone is not strong enough: exit() may be quite
782 likely executed once during program run. */
783 if (gimple_call_fntype (stmt
)
784 && lookup_attribute ("cold",
785 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
786 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
788 tree decl
= gimple_call_fndecl (stmt
);
791 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
792 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
795 cgraph_node
*n
= cgraph_node::get (decl
);
800 n
= n
->ultimate_alias_target (&avail
);
801 if (avail
< AVAIL_AVAILABLE
)
804 || n
->decl
== current_function_decl
)
806 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
809 /* Return true if BB is unlikely executed. */
812 unlikely_executed_bb_p (basic_block bb
)
814 if (bb
->count
== profile_count::zero ())
816 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
818 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
819 !gsi_end_p (gsi
); gsi_next (&gsi
))
821 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
823 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
829 /* We cannot predict the probabilities of outgoing edges of bb. Set them
830 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
831 even probability for all edges not mentioned in the set. These edges
832 are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES,
833 if we have exactly one likely edge, make the other edges predicted
837 set_even_probabilities (basic_block bb
,
838 hash_set
<edge
> *unlikely_edges
= NULL
,
839 hash_set
<edge_prediction
*> *likely_edges
= NULL
)
841 unsigned nedges
= 0, unlikely_count
= 0;
844 profile_probability all
= profile_probability::always ();
846 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
847 if (e
->probability
.initialized_p ())
848 all
-= e
->probability
;
849 else if (!unlikely_executed_edge_p (e
))
852 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
854 all
-= profile_probability::very_unlikely ();
859 /* Make the distribution even if all edges are unlikely. */
860 unsigned likely_count
= likely_edges
? likely_edges
->elements () : 0;
861 if (unlikely_count
== nedges
)
863 unlikely_edges
= NULL
;
867 /* If we have one likely edge, then use its probability and distribute
868 remaining probabilities as even. */
869 if (likely_count
== 1)
871 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
872 if (e
->probability
.initialized_p ())
874 else if (!unlikely_executed_edge_p (e
))
876 edge_prediction
*prediction
= *likely_edges
->begin ();
877 int p
= prediction
->ep_probability
;
878 profile_probability prob
879 = profile_probability::from_reg_br_prob_base (p
);
881 if (prediction
->ep_edge
== e
)
882 e
->probability
= prob
;
883 else if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
884 e
->probability
= profile_probability::very_unlikely ();
887 profile_probability remainder
= prob
.invert ();
888 remainder
-= profile_probability::very_unlikely ()
889 .apply_scale (unlikely_count
, 1);
890 int count
= nedges
- unlikely_count
- 1;
891 gcc_assert (count
>= 0);
893 e
->probability
= remainder
.apply_scale (1, count
);
897 e
->probability
= profile_probability::never ();
901 /* Make all unlikely edges unlikely and the rest will have even
903 unsigned scale
= nedges
- unlikely_count
;
904 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
905 if (e
->probability
.initialized_p ())
907 else if (!unlikely_executed_edge_p (e
))
909 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
910 e
->probability
= profile_probability::very_unlikely ();
912 e
->probability
= all
.apply_scale (1, scale
);
915 e
->probability
= profile_probability::never ();
919 /* Add REG_BR_PROB note to JUMP with PROB. */
922 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
924 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
925 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
928 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
929 note if not already present. Remove now useless REG_BR_PRED notes. */
932 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
937 int best_probability
= PROB_EVEN
;
938 enum br_predictor best_predictor
= END_PREDICTORS
;
939 int combined_probability
= REG_BR_PROB_BASE
/ 2;
941 bool first_match
= false;
944 if (!can_predict_insn_p (insn
))
946 set_even_probabilities (bb
);
950 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
951 pnote
= ®_NOTES (insn
);
953 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
956 /* We implement "first match" heuristics and use probability guessed
957 by predictor with smallest index. */
958 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
959 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
961 enum br_predictor predictor
= ((enum br_predictor
)
962 INTVAL (XEXP (XEXP (note
, 0), 0)));
963 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
966 if (best_predictor
> predictor
967 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
968 best_probability
= probability
, best_predictor
= predictor
;
970 d
= (combined_probability
* probability
971 + (REG_BR_PROB_BASE
- combined_probability
)
972 * (REG_BR_PROB_BASE
- probability
));
974 /* Use FP math to avoid overflows of 32bit integers. */
976 /* If one probability is 0% and one 100%, avoid division by zero. */
977 combined_probability
= REG_BR_PROB_BASE
/ 2;
979 combined_probability
= (((double) combined_probability
) * probability
980 * REG_BR_PROB_BASE
/ d
+ 0.5);
983 /* Decide which heuristic to use. In case we didn't match anything,
984 use no_prediction heuristic, in case we did match, use either
985 first match or Dempster-Shaffer theory depending on the flags. */
987 if (best_predictor
!= END_PREDICTORS
)
991 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
992 combined_probability
, bb
);
996 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
997 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
999 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
1000 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
1004 combined_probability
= best_probability
;
1005 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1009 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
1011 enum br_predictor predictor
= ((enum br_predictor
)
1012 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
1013 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
1015 dump_prediction (dump_file
, predictor
, probability
, bb
,
1016 (!first_match
|| best_predictor
== predictor
)
1017 ? REASON_NONE
: REASON_IGNORED
);
1018 *pnote
= XEXP (*pnote
, 1);
1021 pnote
= &XEXP (*pnote
, 1);
1026 profile_probability p
1027 = profile_probability::from_reg_br_prob_base (combined_probability
);
1028 add_reg_br_prob_note (insn
, p
);
1030 /* Save the prediction into CFG in case we are seeing non-degenerated
1031 conditional jump. */
1032 if (!single_succ_p (bb
))
1034 BRANCH_EDGE (bb
)->probability
= p
;
1035 FALLTHRU_EDGE (bb
)->probability
1036 = BRANCH_EDGE (bb
)->probability
.invert ();
1039 else if (!single_succ_p (bb
))
1041 profile_probability prob
= profile_probability::from_reg_br_prob_note
1042 (XINT (prob_note
, 0));
1044 BRANCH_EDGE (bb
)->probability
= prob
;
1045 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
1048 single_succ_edge (bb
)->probability
= profile_probability::always ();
1051 /* Edge prediction hash traits. */
1053 struct predictor_hash
: pointer_hash
<edge_prediction
>
1056 static inline hashval_t
hash (const edge_prediction
*);
1057 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
1060 /* Calculate hash value of an edge prediction P based on predictor and
1061 normalized probability. */
1064 predictor_hash::hash (const edge_prediction
*p
)
1066 inchash::hash hstate
;
1067 hstate
.add_int (p
->ep_predictor
);
1069 int prob
= p
->ep_probability
;
1070 if (prob
> REG_BR_PROB_BASE
/ 2)
1071 prob
= REG_BR_PROB_BASE
- prob
;
1073 hstate
.add_int (prob
);
1075 return hstate
.end ();
1078 /* Return true whether edge predictions P1 and P2 use the same predictor and
1079 have equal (or opposed probability). */
1082 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1084 return (p1
->ep_predictor
== p2
->ep_predictor
1085 && (p1
->ep_probability
== p2
->ep_probability
1086 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1089 struct predictor_hash_traits
: predictor_hash
,
1090 typed_noop_remove
<edge_prediction
*> {};
1092 /* Return true if edge prediction P is not in DATA hash set. */
1095 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1097 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1098 return !remove
->contains (p
);
1101 /* Prune predictions for a basic block BB. Currently we do following
1104 1) remove duplicate prediction that is guessed with the same probability
1105 (different than 1/2) to both edge
1106 2) remove duplicates for a prediction that belongs with the same probability
1112 prune_predictions_for_bb (basic_block bb
)
1114 edge_prediction
**preds
= bb_predictions
->get (bb
);
1118 hash_table
<predictor_hash_traits
> s (13);
1119 hash_set
<edge_prediction
*> remove
;
1121 /* Step 1: identify predictors that should be removed. */
1122 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1124 edge_prediction
*existing
= s
.find (pred
);
1127 if (pred
->ep_edge
== existing
->ep_edge
1128 && pred
->ep_probability
== existing
->ep_probability
)
1130 /* Remove a duplicate predictor. */
1131 dump_prediction (dump_file
, pred
->ep_predictor
,
1132 pred
->ep_probability
, bb
,
1133 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1137 else if (pred
->ep_edge
!= existing
->ep_edge
1138 && pred
->ep_probability
== existing
->ep_probability
1139 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1141 /* Remove both predictors as they predict the same
1143 dump_prediction (dump_file
, existing
->ep_predictor
,
1144 pred
->ep_probability
, bb
,
1145 REASON_EDGE_PAIR_DUPLICATE
,
1147 dump_prediction (dump_file
, pred
->ep_predictor
,
1148 pred
->ep_probability
, bb
,
1149 REASON_EDGE_PAIR_DUPLICATE
,
1152 remove
.add (existing
);
1157 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1161 /* Step 2: Remove predictors. */
1162 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1166 /* Combine predictions into single probability and store them into CFG.
1167 Remove now useless prediction entries.
1168 If DRY_RUN is set, only produce dumps and do not modify profile. */
1171 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1173 int best_probability
= PROB_EVEN
;
1174 enum br_predictor best_predictor
= END_PREDICTORS
;
1175 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1177 bool first_match
= false;
1179 struct edge_prediction
*pred
;
1181 edge e
, first
= NULL
, second
= NULL
;
1186 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1188 if (!unlikely_executed_edge_p (e
))
1191 if (first
&& !second
)
1196 else if (!e
->probability
.initialized_p ())
1197 e
->probability
= profile_probability::never ();
1198 if (!e
->probability
.initialized_p ())
1200 else if (e
->probability
== profile_probability::never ())
1204 /* When there is no successor or only one choice, prediction is easy.
1206 When we have a basic block with more than 2 successors, the situation
1207 is more complicated as DS theory cannot be used literally.
1208 More precisely, let's assume we predicted edge e1 with probability p1,
1209 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1210 need to find probability of e.g. m1({b2}), which we don't know.
1211 The only approximation is to equally distribute 1-p1 to all edges
1214 According to numbers we've got from SPEC2006 benchark, there's only
1215 one interesting reliable predictor (noreturn call), which can be
1216 handled with a bit easier approach. */
1219 hash_set
<edge
> unlikely_edges (4);
1220 hash_set
<edge_prediction
*> likely_edges (4);
1222 /* Identify all edges that have a probability close to very unlikely.
1223 Doing the approach for very unlikely doesn't worth for doing as
1224 there's no such probability in SPEC2006 benchmark. */
1225 edge_prediction
**preds
= bb_predictions
->get (bb
);
1227 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1229 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
1230 || pred
->ep_predictor
== PRED_COLD_LABEL
)
1231 unlikely_edges
.add (pred
->ep_edge
);
1232 if (pred
->ep_probability
>= PROB_VERY_LIKELY
1233 || pred
->ep_predictor
== PRED_BUILTIN_EXPECT
1234 || pred
->ep_predictor
== PRED_HOT_LABEL
)
1235 likely_edges
.add (pred
);
1239 set_even_probabilities (bb
, &unlikely_edges
, &likely_edges
);
1240 clear_bb_predictions (bb
);
1243 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1244 if (unlikely_edges
.elements () == 0)
1246 "%i edges in bb %i predicted to even probabilities\n",
1251 "%i edges in bb %i predicted with some unlikely edges\n",
1253 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1254 if (!unlikely_executed_edge_p (e
))
1255 dump_prediction (dump_file
, PRED_COMBINED
,
1256 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1263 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1265 prune_predictions_for_bb (bb
);
1267 edge_prediction
**preds
= bb_predictions
->get (bb
);
1271 /* We implement "first match" heuristics and use probability guessed
1272 by predictor with smallest index. */
1273 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1275 enum br_predictor predictor
= pred
->ep_predictor
;
1276 int probability
= pred
->ep_probability
;
1278 if (pred
->ep_edge
!= first
)
1279 probability
= REG_BR_PROB_BASE
- probability
;
1282 /* First match heuristics would be widly confused if we predicted
1284 if (best_predictor
> predictor
1285 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1287 struct edge_prediction
*pred2
;
1288 int prob
= probability
;
1290 for (pred2
= (struct edge_prediction
*) *preds
;
1291 pred2
; pred2
= pred2
->ep_next
)
1292 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1294 int probability2
= pred2
->ep_probability
;
1296 if (pred2
->ep_edge
!= first
)
1297 probability2
= REG_BR_PROB_BASE
- probability2
;
1299 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1300 (probability2
< REG_BR_PROB_BASE
/ 2))
1303 /* If the same predictor later gave better result, go for it! */
1304 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1305 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1306 prob
= probability2
;
1309 best_probability
= prob
, best_predictor
= predictor
;
1312 d
= (combined_probability
* probability
1313 + (REG_BR_PROB_BASE
- combined_probability
)
1314 * (REG_BR_PROB_BASE
- probability
));
1316 /* Use FP math to avoid overflows of 32bit integers. */
1318 /* If one probability is 0% and one 100%, avoid division by zero. */
1319 combined_probability
= REG_BR_PROB_BASE
/ 2;
1321 combined_probability
= (((double) combined_probability
)
1323 * REG_BR_PROB_BASE
/ d
+ 0.5);
1327 /* Decide which heuristic to use. In case we didn't match anything,
1328 use no_prediction heuristic, in case we did match, use either
1329 first match or Dempster-Shaffer theory depending on the flags. */
1331 if (best_predictor
!= END_PREDICTORS
)
1335 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1339 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1340 !first_match
? REASON_NONE
: REASON_IGNORED
);
1342 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1343 first_match
? REASON_NONE
: REASON_IGNORED
);
1347 combined_probability
= best_probability
;
1348 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1352 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1354 enum br_predictor predictor
= pred
->ep_predictor
;
1355 int probability
= pred
->ep_probability
;
1357 dump_prediction (dump_file
, predictor
, probability
, bb
,
1358 (!first_match
|| best_predictor
== predictor
)
1359 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1362 clear_bb_predictions (bb
);
1365 /* If we have only one successor which is unknown, we can compute missing
1369 profile_probability prob
= profile_probability::always ();
1370 edge missing
= NULL
;
1372 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1373 if (e
->probability
.initialized_p ())
1374 prob
-= e
->probability
;
1375 else if (missing
== NULL
)
1379 missing
->probability
= prob
;
1381 /* If nothing is unknown, we have nothing to update. */
1382 else if (!nunknown
&& nzero
!= (int)EDGE_COUNT (bb
->succs
))
1387 = profile_probability::from_reg_br_prob_base (combined_probability
);
1388 second
->probability
= first
->probability
.invert ();
1392 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1393 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1395 T1 and T2 should be one of the following cases:
1396 1. T1 is SSA_NAME, T2 is NULL
1397 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1398 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1401 strips_small_constant (tree t1
, tree t2
)
1408 else if (TREE_CODE (t1
) == SSA_NAME
)
1410 else if (tree_fits_shwi_p (t1
))
1411 value
= tree_to_shwi (t1
);
1417 else if (tree_fits_shwi_p (t2
))
1418 value
= tree_to_shwi (t2
);
1419 else if (TREE_CODE (t2
) == SSA_NAME
)
1427 if (value
<= 4 && value
>= -4)
1433 /* Return the SSA_NAME in T or T's operands.
1434 Return NULL if SSA_NAME cannot be found. */
1437 get_base_value (tree t
)
1439 if (TREE_CODE (t
) == SSA_NAME
)
1442 if (!BINARY_CLASS_P (t
))
1445 switch (TREE_OPERAND_LENGTH (t
))
1448 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1450 return strips_small_constant (TREE_OPERAND (t
, 0),
1451 TREE_OPERAND (t
, 1));
1457 /* Check the compare STMT in LOOP. If it compares an induction
1458 variable to a loop invariant, return true, and save
1459 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1460 Otherwise return false and set LOOP_INVAIANT to NULL. */
1463 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1464 tree
*loop_invariant
,
1465 enum tree_code
*compare_code
,
1469 tree op0
, op1
, bound
, base
;
1471 enum tree_code code
;
1474 code
= gimple_cond_code (stmt
);
1475 *loop_invariant
= NULL
;
1491 op0
= gimple_cond_lhs (stmt
);
1492 op1
= gimple_cond_rhs (stmt
);
1494 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1495 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1497 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1499 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1501 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1502 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1504 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1505 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1508 if (integer_zerop (iv0
.step
))
1510 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1511 code
= invert_tree_comparison (code
, false);
1514 if (tree_fits_shwi_p (iv1
.step
))
1523 if (tree_fits_shwi_p (iv0
.step
))
1529 if (TREE_CODE (bound
) != INTEGER_CST
)
1530 bound
= get_base_value (bound
);
1533 if (TREE_CODE (base
) != INTEGER_CST
)
1534 base
= get_base_value (base
);
1538 *loop_invariant
= bound
;
1539 *compare_code
= code
;
1541 *loop_iv_base
= base
;
1545 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1548 expr_coherent_p (tree t1
, tree t2
)
1551 tree ssa_name_1
= NULL
;
1552 tree ssa_name_2
= NULL
;
1554 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1555 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1560 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1562 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1565 /* Check to see if t1 is expressed/defined with t2. */
1566 stmt
= SSA_NAME_DEF_STMT (t1
);
1567 gcc_assert (stmt
!= NULL
);
1568 if (is_gimple_assign (stmt
))
1570 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1571 if (ssa_name_1
&& ssa_name_1
== t2
)
1575 /* Check to see if t2 is expressed/defined with t1. */
1576 stmt
= SSA_NAME_DEF_STMT (t2
);
1577 gcc_assert (stmt
!= NULL
);
1578 if (is_gimple_assign (stmt
))
1580 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1581 if (ssa_name_2
&& ssa_name_2
== t1
)
1585 /* Compare if t1 and t2's def_stmts are identical. */
1586 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1592 /* Return true if E is predicted by one of loop heuristics. */
1595 predicted_by_loop_heuristics_p (basic_block bb
)
1597 struct edge_prediction
*i
;
1598 edge_prediction
**preds
= bb_predictions
->get (bb
);
1603 for (i
= *preds
; i
; i
= i
->ep_next
)
1604 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1605 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1606 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1607 || i
->ep_predictor
== PRED_LOOP_EXIT
1608 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1609 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1614 /* Predict branch probability of BB when BB contains a branch that compares
1615 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1616 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1619 for (int i = 0; i < bound; i++) {
1626 In this loop, we will predict the branch inside the loop to be taken. */
1629 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1630 tree loop_bound_var
,
1631 tree loop_iv_base_var
,
1632 enum tree_code loop_bound_code
,
1633 int loop_bound_step
)
1636 tree compare_var
, compare_base
;
1637 enum tree_code compare_code
;
1638 tree compare_step_var
;
1642 if (predicted_by_loop_heuristics_p (bb
))
1645 stmt
= last_stmt (bb
);
1646 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1648 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1655 /* Find the taken edge. */
1656 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1657 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1660 /* When comparing an IV to a loop invariant, NE is more likely to be
1661 taken while EQ is more likely to be not-taken. */
1662 if (compare_code
== NE_EXPR
)
1664 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1667 else if (compare_code
== EQ_EXPR
)
1669 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1673 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1676 /* If loop bound, base and compare bound are all constants, we can
1677 calculate the probability directly. */
1678 if (tree_fits_shwi_p (loop_bound_var
)
1679 && tree_fits_shwi_p (compare_var
)
1680 && tree_fits_shwi_p (compare_base
))
1683 wi::overflow_type overflow
;
1684 bool overall_overflow
= false;
1685 widest_int compare_count
, tem
;
1687 /* (loop_bound - base) / compare_step */
1688 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1689 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1690 overall_overflow
|= overflow
;
1691 widest_int loop_count
= wi::div_trunc (tem
,
1692 wi::to_widest (compare_step_var
),
1694 overall_overflow
|= overflow
;
1696 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1697 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1699 /* (loop_bound - compare_bound) / compare_step */
1700 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1701 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1702 overall_overflow
|= overflow
;
1703 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1705 overall_overflow
|= overflow
;
1709 /* (compare_bound - base) / compare_step */
1710 tem
= wi::sub (wi::to_widest (compare_var
),
1711 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1712 overall_overflow
|= overflow
;
1713 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1715 overall_overflow
|= overflow
;
1717 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1719 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1721 if (wi::neg_p (compare_count
))
1723 if (wi::neg_p (loop_count
))
1725 if (loop_count
== 0)
1727 else if (wi::cmps (compare_count
, loop_count
) == 1)
1728 probability
= REG_BR_PROB_BASE
;
1731 tem
= compare_count
* REG_BR_PROB_BASE
;
1732 tem
= wi::udiv_trunc (tem
, loop_count
);
1733 probability
= tem
.to_uhwi ();
1736 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1737 if (!overall_overflow
)
1738 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1743 if (expr_coherent_p (loop_bound_var
, compare_var
))
1745 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1746 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1747 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1748 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1749 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1750 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1751 else if (loop_bound_code
== NE_EXPR
)
1753 /* If the loop backedge condition is "(i != bound)", we do
1754 the comparison based on the step of IV:
1755 * step < 0 : backedge condition is like (i > bound)
1756 * step > 0 : backedge condition is like (i < bound) */
1757 gcc_assert (loop_bound_step
!= 0);
1758 if (loop_bound_step
> 0
1759 && (compare_code
== LT_EXPR
1760 || compare_code
== LE_EXPR
))
1761 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1762 else if (loop_bound_step
< 0
1763 && (compare_code
== GT_EXPR
1764 || compare_code
== GE_EXPR
))
1765 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1767 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1770 /* The branch is predicted not-taken if loop_bound_code is
1771 opposite with compare_code. */
1772 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1774 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1777 for (i = s; i < h; i++)
1779 The branch should be predicted taken. */
1780 if (loop_bound_step
> 0
1781 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1782 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1783 else if (loop_bound_step
< 0
1784 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1785 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1787 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1791 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1792 exits are resulted from short-circuit conditions that will generate an
1795 if (foo() || global > 10)
1798 This will be translated into:
1803 if foo() goto BB6 else goto BB5
1805 if global > 10 goto BB6 else goto BB7
1809 iftmp = (PHI 0(BB5), 1(BB6))
1810 if iftmp == 1 goto BB8 else goto BB3
1812 outside of the loop...
1814 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1815 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1816 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1817 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1820 predict_extra_loop_exits (edge exit_edge
)
1823 bool check_value_one
;
1824 gimple
*lhs_def_stmt
;
1826 tree cmp_rhs
, cmp_lhs
;
1830 last
= last_stmt (exit_edge
->src
);
1833 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1837 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1838 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1839 if (!TREE_CONSTANT (cmp_rhs
)
1840 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1842 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1845 /* If check_value_one is true, only the phi_args with value '1' will lead
1846 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1848 check_value_one
= (((integer_onep (cmp_rhs
))
1849 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1850 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1852 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1856 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1860 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1864 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1865 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1867 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1869 if ((check_value_one
^ integer_onep (val
)) == 1)
1871 if (EDGE_COUNT (e
->src
->succs
) != 1)
1873 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1877 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1878 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1883 /* Predict edge probabilities by exploiting loop structure. */
1886 predict_loops (void)
1890 hash_set
<struct loop
*> with_recursion(10);
1892 FOR_EACH_BB_FN (bb
, cfun
)
1894 gimple_stmt_iterator gsi
;
1897 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1898 if (is_gimple_call (gsi_stmt (gsi
))
1899 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1900 && recursive_call_p (current_function_decl
, decl
))
1902 loop
= bb
->loop_father
;
1903 while (loop
&& !with_recursion
.add (loop
))
1904 loop
= loop_outer (loop
);
1908 /* Try to predict out blocks in a loop that are not part of a
1910 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1912 basic_block bb
, *bbs
;
1913 unsigned j
, n_exits
= 0;
1915 struct tree_niter_desc niter_desc
;
1917 struct nb_iter_bound
*nb_iter
;
1918 enum tree_code loop_bound_code
= ERROR_MARK
;
1919 tree loop_bound_step
= NULL
;
1920 tree loop_bound_var
= NULL
;
1921 tree loop_iv_base
= NULL
;
1923 bool recursion
= with_recursion
.contains (loop
);
1925 exits
= get_loop_exit_edges (loop
);
1926 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1927 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1936 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1937 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1938 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1939 && max_loop_iterations_int (loop
) >= 0)
1942 "Loop %d iterates at most %i times.\n", loop
->num
,
1943 (int)max_loop_iterations_int (loop
));
1945 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1946 && likely_max_loop_iterations_int (loop
) >= 0)
1948 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1949 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1952 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1955 HOST_WIDE_INT nitercst
;
1956 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1958 enum br_predictor predictor
;
1961 if (unlikely_executed_edge_p (ex
)
1962 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
1964 /* Loop heuristics do not expect exit conditional to be inside
1965 inner loop. We predict from innermost to outermost loop. */
1966 if (predicted_by_loop_heuristics_p (ex
->src
))
1968 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1969 fprintf (dump_file
, "Skipping exit %i->%i because "
1970 "it is already predicted.\n",
1971 ex
->src
->index
, ex
->dest
->index
);
1974 predict_extra_loop_exits (ex
);
1976 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1977 niter
= niter_desc
.niter
;
1978 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1979 niter
= loop_niter_by_eval (loop
, ex
);
1980 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1981 && TREE_CODE (niter
) == INTEGER_CST
)
1983 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1984 ex
->src
->index
, ex
->dest
->index
,
1986 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1987 fprintf (dump_file
, " times.\n");
1990 if (TREE_CODE (niter
) == INTEGER_CST
)
1992 if (tree_fits_uhwi_p (niter
)
1994 && compare_tree_int (niter
, max
- 1) == -1)
1995 nitercst
= tree_to_uhwi (niter
) + 1;
1998 predictor
= PRED_LOOP_ITERATIONS
;
2000 /* If we have just one exit and we can derive some information about
2001 the number of iterations of the loop from the statements inside
2002 the loop, use it to predict this exit. */
2003 else if (n_exits
== 1
2004 && estimated_stmt_executions (loop
, &nit
))
2006 if (wi::gtu_p (nit
, max
))
2009 nitercst
= nit
.to_shwi ();
2010 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
2012 /* If we have likely upper bound, trust it for very small iteration
2013 counts. Such loops would otherwise get mispredicted by standard
2014 LOOP_EXIT heuristics. */
2015 else if (n_exits
== 1
2016 && likely_max_stmt_executions (loop
, &nit
)
2018 RDIV (REG_BR_PROB_BASE
,
2022 ? PRED_LOOP_EXIT_WITH_RECURSION
2023 : PRED_LOOP_EXIT
].hitrate
)))
2025 nitercst
= nit
.to_shwi ();
2026 predictor
= PRED_LOOP_ITERATIONS_MAX
;
2030 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2031 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
2032 ex
->src
->index
, ex
->dest
->index
);
2036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2037 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
2038 (int)nitercst
, predictor_info
[predictor
].name
);
2039 /* If the prediction for number of iterations is zero, do not
2040 predict the exit edges. */
2044 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
2045 predict_edge (ex
, predictor
, probability
);
2049 /* Find information about loop bound variables. */
2050 for (nb_iter
= loop
->bounds
; nb_iter
;
2051 nb_iter
= nb_iter
->next
)
2053 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
2055 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
2058 if (!stmt
&& last_stmt (loop
->header
)
2059 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
2060 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2062 is_comparison_with_loop_invariant_p (stmt
, loop
,
2068 bbs
= get_loop_body (loop
);
2070 for (j
= 0; j
< loop
->num_nodes
; j
++)
2077 /* Bypass loop heuristics on continue statement. These
2078 statements construct loops via "non-loop" constructs
2079 in the source language and are better to be handled
2081 if (predicted_by_p (bb
, PRED_CONTINUE
))
2083 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2084 fprintf (dump_file
, "BB %i predicted by continue.\n",
2089 /* If we already used more reliable loop exit predictors, do not
2090 bother with PRED_LOOP_EXIT. */
2091 if (!predicted_by_loop_heuristics_p (bb
))
2093 /* For loop with many exits we don't want to predict all exits
2094 with the pretty large probability, because if all exits are
2095 considered in row, the loop would be predicted to iterate
2096 almost never. The code to divide probability by number of
2097 exits is very rough. It should compute the number of exits
2098 taken in each patch through function (not the overall number
2099 of exits that might be a lot higher for loops with wide switch
2100 statements in them) and compute n-th square root.
2102 We limit the minimal probability by 2% to avoid
2103 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2104 as this was causing regression in perl benchmark containing such
2107 int probability
= ((REG_BR_PROB_BASE
2110 ? PRED_LOOP_EXIT_WITH_RECURSION
2111 : PRED_LOOP_EXIT
].hitrate
)
2113 if (probability
< HITRATE (2))
2114 probability
= HITRATE (2);
2115 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2116 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2117 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2121 "Predicting exit %i->%i with prob %i.\n",
2122 e
->src
->index
, e
->dest
->index
, probability
);
2124 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2125 : PRED_LOOP_EXIT
, probability
);
2129 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2131 tree_to_shwi (loop_bound_step
));
2134 /* In the following code
2139 guess that cond is unlikely. */
2140 if (loop_outer (loop
)->num
)
2142 basic_block bb
= NULL
;
2143 edge preheader_edge
= loop_preheader_edge (loop
);
2145 if (single_pred_p (preheader_edge
->src
)
2146 && single_succ_p (preheader_edge
->src
))
2147 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2149 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2150 /* Pattern match fortran loop preheader:
2151 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2152 _17 = (logical(kind=4)) _16;
2158 Loop guard branch prediction says nothing about duplicated loop
2159 headers produced by fortran frontend and in this case we want
2160 to predict paths leading to this preheader. */
2163 && gimple_code (stmt
) == GIMPLE_COND
2164 && gimple_cond_code (stmt
) == NE_EXPR
2165 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2166 && integer_zerop (gimple_cond_rhs (stmt
)))
2168 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2169 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2170 && gimple_expr_code (call_stmt
) == NOP_EXPR
2171 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2172 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2173 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2174 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2175 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2176 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2177 == PRED_FORTRAN_LOOP_PREHEADER
)
2178 bb
= preheader_edge
->src
;
2182 if (!dominated_by_p (CDI_DOMINATORS
,
2183 loop_outer (loop
)->latch
, loop
->header
))
2184 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2186 ? PRED_LOOP_GUARD_WITH_RECURSION
2193 if (!dominated_by_p (CDI_DOMINATORS
,
2194 loop_outer (loop
)->latch
, bb
))
2195 predict_paths_leading_to (bb
,
2197 ? PRED_LOOP_GUARD_WITH_RECURSION
2204 /* Free basic blocks from get_loop_body. */
2209 /* Attempt to predict probabilities of BB outgoing edges using local
2212 bb_estimate_probability_locally (basic_block bb
)
2214 rtx_insn
*last_insn
= BB_END (bb
);
2217 if (! can_predict_insn_p (last_insn
))
2219 cond
= get_condition (last_insn
, NULL
, false, false);
2223 /* Try "pointer heuristic."
2224 A comparison ptr == 0 is predicted as false.
2225 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2226 if (COMPARISON_P (cond
)
2227 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2228 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2230 if (GET_CODE (cond
) == EQ
)
2231 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2232 else if (GET_CODE (cond
) == NE
)
2233 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2237 /* Try "opcode heuristic."
2238 EQ tests are usually false and NE tests are usually true. Also,
2239 most quantities are positive, so we can make the appropriate guesses
2240 about signed comparisons against zero. */
2241 switch (GET_CODE (cond
))
2244 /* Unconditional branch. */
2245 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2246 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2251 /* Floating point comparisons appears to behave in a very
2252 unpredictable way because of special role of = tests in
2254 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2256 /* Comparisons with 0 are often used for booleans and there is
2257 nothing useful to predict about them. */
2258 else if (XEXP (cond
, 1) == const0_rtx
2259 || XEXP (cond
, 0) == const0_rtx
)
2262 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2267 /* Floating point comparisons appears to behave in a very
2268 unpredictable way because of special role of = tests in
2270 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2272 /* Comparisons with 0 are often used for booleans and there is
2273 nothing useful to predict about them. */
2274 else if (XEXP (cond
, 1) == const0_rtx
2275 || XEXP (cond
, 0) == const0_rtx
)
2278 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2282 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2286 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2291 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2292 || XEXP (cond
, 1) == constm1_rtx
)
2293 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2298 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2299 || XEXP (cond
, 1) == constm1_rtx
)
2300 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2308 /* Set edge->probability for each successor edge of BB. */
2310 guess_outgoing_edge_probabilities (basic_block bb
)
2312 bb_estimate_probability_locally (bb
);
2313 combine_predictions_for_insn (BB_END (bb
), bb
);
2316 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
,
2317 HOST_WIDE_INT
*probability
);
2319 /* Helper function for expr_expected_value. */
2322 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2323 tree op1
, bitmap visited
, enum br_predictor
*predictor
,
2324 HOST_WIDE_INT
*probability
)
2328 /* Reset returned probability value. */
2330 *predictor
= PRED_UNCONDITIONAL
;
2332 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2334 if (TREE_CONSTANT (op0
))
2337 if (code
== IMAGPART_EXPR
)
2339 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2341 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2342 if (is_gimple_call (def
)
2343 && gimple_call_internal_p (def
)
2344 && (gimple_call_internal_fn (def
)
2345 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2347 /* Assume that any given atomic operation has low contention,
2348 and thus the compare-and-swap operation succeeds. */
2349 *predictor
= PRED_COMPARE_AND_SWAP
;
2350 return build_one_cst (TREE_TYPE (op0
));
2355 if (code
!= SSA_NAME
)
2358 def
= SSA_NAME_DEF_STMT (op0
);
2360 /* If we were already here, break the infinite cycle. */
2361 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2364 if (gimple_code (def
) == GIMPLE_PHI
)
2366 /* All the arguments of the PHI node must have the same constant
2368 int i
, n
= gimple_phi_num_args (def
);
2369 tree val
= NULL
, new_val
;
2371 for (i
= 0; i
< n
; i
++)
2373 tree arg
= PHI_ARG_DEF (def
, i
);
2374 enum br_predictor predictor2
;
2376 /* If this PHI has itself as an argument, we cannot
2377 determine the string length of this argument. However,
2378 if we can find an expected constant value for the other
2379 PHI args then we can still be sure that this is
2380 likely a constant. So be optimistic and just
2381 continue with the next argument. */
2382 if (arg
== PHI_RESULT (def
))
2385 HOST_WIDE_INT probability2
;
2386 new_val
= expr_expected_value (arg
, visited
, &predictor2
,
2389 /* It is difficult to combine value predictors. Simply assume
2390 that later predictor is weaker and take its prediction. */
2391 if (*predictor
< predictor2
)
2393 *predictor
= predictor2
;
2394 *probability
= probability2
;
2400 else if (!operand_equal_p (val
, new_val
, false))
2405 if (is_gimple_assign (def
))
2407 if (gimple_assign_lhs (def
) != op0
)
2410 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2411 gimple_assign_rhs1 (def
),
2412 gimple_assign_rhs_code (def
),
2413 gimple_assign_rhs2 (def
),
2414 visited
, predictor
, probability
);
2417 if (is_gimple_call (def
))
2419 tree decl
= gimple_call_fndecl (def
);
2422 if (gimple_call_internal_p (def
)
2423 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2425 gcc_assert (gimple_call_num_args (def
) == 3);
2426 tree val
= gimple_call_arg (def
, 0);
2427 if (TREE_CONSTANT (val
))
2429 tree val2
= gimple_call_arg (def
, 2);
2430 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2431 && tree_fits_uhwi_p (val2
)
2432 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2433 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2434 if (*predictor
== PRED_BUILTIN_EXPECT
)
2436 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
));
2437 return gimple_call_arg (def
, 1);
2442 if (DECL_IS_MALLOC (decl
) || DECL_IS_OPERATOR_NEW (decl
))
2445 *predictor
= PRED_MALLOC_NONNULL
;
2446 return boolean_true_node
;
2449 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2450 switch (DECL_FUNCTION_CODE (decl
))
2452 case BUILT_IN_EXPECT
:
2455 if (gimple_call_num_args (def
) != 2)
2457 val
= gimple_call_arg (def
, 0);
2458 if (TREE_CONSTANT (val
))
2460 *predictor
= PRED_BUILTIN_EXPECT
;
2462 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
));
2463 return gimple_call_arg (def
, 1);
2465 case BUILT_IN_EXPECT_WITH_PROBABILITY
:
2468 if (gimple_call_num_args (def
) != 3)
2470 val
= gimple_call_arg (def
, 0);
2471 if (TREE_CONSTANT (val
))
2473 /* Compute final probability as:
2474 probability * REG_BR_PROB_BASE. */
2475 tree prob
= gimple_call_arg (def
, 2);
2476 tree t
= TREE_TYPE (prob
);
2477 tree base
= build_int_cst (integer_type_node
,
2479 base
= build_real_from_int_cst (t
, base
);
2480 tree r
= fold_build2_initializer_loc (UNKNOWN_LOCATION
,
2481 MULT_EXPR
, t
, prob
, base
);
2482 if (TREE_CODE (r
) != REAL_CST
)
2484 error_at (gimple_location (def
),
2485 "probability %qE must be "
2486 "constant floating-point expression", prob
);
2490 = real_to_integer (TREE_REAL_CST_PTR (r
));
2491 if (probi
>= 0 && probi
<= REG_BR_PROB_BASE
)
2493 *predictor
= PRED_BUILTIN_EXPECT_WITH_PROBABILITY
;
2494 *probability
= probi
;
2497 error_at (gimple_location (def
),
2498 "probability %qE is outside "
2499 "the range [0.0, 1.0]", prob
);
2501 return gimple_call_arg (def
, 1);
2504 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2505 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2506 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2507 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2508 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2509 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2510 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2511 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2512 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2513 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2514 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2515 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2516 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2517 /* Assume that any given atomic operation has low contention,
2518 and thus the compare-and-swap operation succeeds. */
2519 *predictor
= PRED_COMPARE_AND_SWAP
;
2520 return boolean_true_node
;
2521 case BUILT_IN_REALLOC
:
2523 *predictor
= PRED_MALLOC_NONNULL
;
2524 return boolean_true_node
;
2533 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2536 enum br_predictor predictor2
;
2537 HOST_WIDE_INT probability2
;
2538 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2541 op1
= expr_expected_value (op1
, visited
, &predictor2
, &probability2
);
2544 res
= fold_build2 (code
, type
, op0
, op1
);
2545 if (TREE_CODE (res
) == INTEGER_CST
2546 && TREE_CODE (op0
) == INTEGER_CST
2547 && TREE_CODE (op1
) == INTEGER_CST
)
2549 /* Combine binary predictions. */
2550 if (*probability
!= -1 || probability2
!= -1)
2552 HOST_WIDE_INT p1
= get_predictor_value (*predictor
, *probability
);
2553 HOST_WIDE_INT p2
= get_predictor_value (predictor2
, probability2
);
2554 *probability
= RDIV (p1
* p2
, REG_BR_PROB_BASE
);
2557 if (*predictor
< predictor2
)
2558 *predictor
= predictor2
;
2564 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2567 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2570 res
= fold_build1 (code
, type
, op0
);
2571 if (TREE_CONSTANT (res
))
2578 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2579 The function is used by builtin_expect branch predictor so the evidence
2580 must come from this construct and additional possible constant folding.
2582 We may want to implement more involved value guess (such as value range
2583 propagation based prediction), but such tricks shall go to new
2587 expr_expected_value (tree expr
, bitmap visited
,
2588 enum br_predictor
*predictor
,
2589 HOST_WIDE_INT
*probability
)
2591 enum tree_code code
;
2594 if (TREE_CONSTANT (expr
))
2596 *predictor
= PRED_UNCONDITIONAL
;
2601 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2602 return expr_expected_value_1 (TREE_TYPE (expr
),
2603 op0
, code
, op1
, visited
, predictor
,
2608 /* Return probability of a PREDICTOR. If the predictor has variable
2609 probability return passed PROBABILITY. */
2611 static HOST_WIDE_INT
2612 get_predictor_value (br_predictor predictor
, HOST_WIDE_INT probability
)
2616 case PRED_BUILTIN_EXPECT
:
2617 case PRED_BUILTIN_EXPECT_WITH_PROBABILITY
:
2618 gcc_assert (probability
!= -1);
2621 gcc_assert (probability
== -1);
2622 return predictor_info
[(int) predictor
].hitrate
;
2626 /* Predict using opcode of the last statement in basic block. */
2628 tree_predict_by_opcode (basic_block bb
)
2630 gimple
*stmt
= last_stmt (bb
);
2637 enum br_predictor predictor
;
2638 HOST_WIDE_INT probability
;
2643 if (gswitch
*sw
= dyn_cast
<gswitch
*> (stmt
))
2645 tree index
= gimple_switch_index (sw
);
2646 tree val
= expr_expected_value (index
, auto_bitmap (),
2647 &predictor
, &probability
);
2648 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2650 edge e
= find_taken_edge_switch_expr (sw
, val
);
2651 if (predictor
== PRED_BUILTIN_EXPECT
)
2653 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2654 gcc_assert (percent
>= 0 && percent
<= 100);
2655 predict_edge (e
, PRED_BUILTIN_EXPECT
,
2659 predict_edge_def (e
, predictor
, TAKEN
);
2663 if (gimple_code (stmt
) != GIMPLE_COND
)
2665 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2666 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2668 op0
= gimple_cond_lhs (stmt
);
2669 op1
= gimple_cond_rhs (stmt
);
2670 cmp
= gimple_cond_code (stmt
);
2671 type
= TREE_TYPE (op0
);
2672 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2673 &predictor
, &probability
);
2674 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2676 HOST_WIDE_INT prob
= get_predictor_value (predictor
, probability
);
2677 if (integer_zerop (val
))
2678 prob
= REG_BR_PROB_BASE
- prob
;
2679 predict_edge (then_edge
, predictor
, prob
);
2681 /* Try "pointer heuristic."
2682 A comparison ptr == 0 is predicted as false.
2683 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2684 if (POINTER_TYPE_P (type
))
2687 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2688 else if (cmp
== NE_EXPR
)
2689 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2693 /* Try "opcode heuristic."
2694 EQ tests are usually false and NE tests are usually true. Also,
2695 most quantities are positive, so we can make the appropriate guesses
2696 about signed comparisons against zero. */
2701 /* Floating point comparisons appears to behave in a very
2702 unpredictable way because of special role of = tests in
2704 if (FLOAT_TYPE_P (type
))
2706 /* Comparisons with 0 are often used for booleans and there is
2707 nothing useful to predict about them. */
2708 else if (integer_zerop (op0
) || integer_zerop (op1
))
2711 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2716 /* Floating point comparisons appears to behave in a very
2717 unpredictable way because of special role of = tests in
2719 if (FLOAT_TYPE_P (type
))
2721 /* Comparisons with 0 are often used for booleans and there is
2722 nothing useful to predict about them. */
2723 else if (integer_zerop (op0
)
2724 || integer_zerop (op1
))
2727 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2731 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2734 case UNORDERED_EXPR
:
2735 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2740 if (integer_zerop (op1
)
2741 || integer_onep (op1
)
2742 || integer_all_onesp (op1
)
2745 || real_minus_onep (op1
))
2746 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2751 if (integer_zerop (op1
)
2752 || integer_onep (op1
)
2753 || integer_all_onesp (op1
)
2756 || real_minus_onep (op1
))
2757 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2765 /* Returns TRUE if the STMT is exit(0) like statement. */
2768 is_exit_with_zero_arg (const gimple
*stmt
)
2770 /* This is not exit, _exit or _Exit. */
2771 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2772 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2773 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2776 /* Argument is an interger zero. */
2777 return integer_zerop (gimple_call_arg (stmt
, 0));
2780 /* Try to guess whether the value of return means error code. */
2782 static enum br_predictor
2783 return_prediction (tree val
, enum prediction
*prediction
)
2787 return PRED_NO_PREDICTION
;
2788 /* Different heuristics for pointers and scalars. */
2789 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2791 /* NULL is usually not returned. */
2792 if (integer_zerop (val
))
2794 *prediction
= NOT_TAKEN
;
2795 return PRED_NULL_RETURN
;
2798 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2800 /* Negative return values are often used to indicate
2802 if (TREE_CODE (val
) == INTEGER_CST
2803 && tree_int_cst_sgn (val
) < 0)
2805 *prediction
= NOT_TAKEN
;
2806 return PRED_NEGATIVE_RETURN
;
2808 /* Constant return values seems to be commonly taken.
2809 Zero/one often represent booleans so exclude them from the
2811 if (TREE_CONSTANT (val
)
2812 && (!integer_zerop (val
) && !integer_onep (val
)))
2814 *prediction
= NOT_TAKEN
;
2815 return PRED_CONST_RETURN
;
2818 return PRED_NO_PREDICTION
;
2821 /* Return zero if phi result could have values other than -1, 0 or 1,
2822 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2823 values are used or likely. */
2826 zero_one_minusone (gphi
*phi
, int limit
)
2828 int phi_num_args
= gimple_phi_num_args (phi
);
2830 for (int i
= 0; i
< phi_num_args
; i
++)
2832 tree t
= PHI_ARG_DEF (phi
, i
);
2833 if (TREE_CODE (t
) != INTEGER_CST
)
2835 wide_int w
= wi::to_wide (t
);
2845 for (int i
= 0; i
< phi_num_args
; i
++)
2847 tree t
= PHI_ARG_DEF (phi
, i
);
2848 if (TREE_CODE (t
) == INTEGER_CST
)
2850 if (TREE_CODE (t
) != SSA_NAME
)
2852 gimple
*g
= SSA_NAME_DEF_STMT (t
);
2853 if (gimple_code (g
) == GIMPLE_PHI
&& limit
> 0)
2854 if (int r
= zero_one_minusone (as_a
<gphi
*> (g
), limit
- 1))
2859 if (!is_gimple_assign (g
))
2861 if (gimple_assign_cast_p (g
))
2863 tree rhs1
= gimple_assign_rhs1 (g
);
2864 if (TREE_CODE (rhs1
) != SSA_NAME
2865 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
2866 || TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2867 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2872 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g
)) != tcc_comparison
)
2879 /* Find the basic block with return expression and look up for possible
2880 return value trying to apply RETURN_PREDICTION heuristics. */
2882 apply_return_prediction (void)
2884 greturn
*return_stmt
= NULL
;
2888 int phi_num_args
, i
;
2889 enum br_predictor pred
;
2890 enum prediction direction
;
2893 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2895 gimple
*last
= last_stmt (e
->src
);
2897 && gimple_code (last
) == GIMPLE_RETURN
)
2899 return_stmt
= as_a
<greturn
*> (last
);
2905 return_val
= gimple_return_retval (return_stmt
);
2908 if (TREE_CODE (return_val
) != SSA_NAME
2909 || !SSA_NAME_DEF_STMT (return_val
)
2910 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2912 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2913 phi_num_args
= gimple_phi_num_args (phi
);
2914 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2916 /* Avoid the case where the function returns -1, 0 and 1 values and
2917 nothing else. Those could be qsort etc. comparison functions
2918 where the negative return isn't less probable than positive.
2919 For this require that the function returns at least -1 or 1
2920 or -1 and a boolean value or comparison result, so that functions
2921 returning just -1 and 0 are treated as if -1 represents error value. */
2922 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val
))
2923 && !TYPE_UNSIGNED (TREE_TYPE (return_val
))
2924 && TYPE_PRECISION (TREE_TYPE (return_val
)) > 1)
2925 if (int r
= zero_one_minusone (phi
, 3))
2926 if ((r
& (1 | 4)) == (1 | 4))
2929 /* Avoid the degenerate case where all return values form the function
2930 belongs to same category (ie they are all positive constants)
2931 so we can hardly say something about them. */
2932 for (i
= 1; i
< phi_num_args
; i
++)
2933 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2935 if (i
!= phi_num_args
)
2936 for (i
= 0; i
< phi_num_args
; i
++)
2938 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2939 if (pred
!= PRED_NO_PREDICTION
)
2940 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2945 /* Look for basic block that contains unlikely to happen events
2946 (such as noreturn calls) and mark all paths leading to execution
2947 of this basic blocks as unlikely. */
2950 tree_bb_level_predictions (void)
2953 bool has_return_edges
= false;
2957 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2958 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2960 has_return_edges
= true;
2964 apply_return_prediction ();
2966 FOR_EACH_BB_FN (bb
, cfun
)
2968 gimple_stmt_iterator gsi
;
2970 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2972 gimple
*stmt
= gsi_stmt (gsi
);
2975 if (is_gimple_call (stmt
))
2977 if (gimple_call_noreturn_p (stmt
)
2979 && !is_exit_with_zero_arg (stmt
))
2980 predict_paths_leading_to (bb
, PRED_NORETURN
,
2982 decl
= gimple_call_fndecl (stmt
);
2984 && lookup_attribute ("cold",
2985 DECL_ATTRIBUTES (decl
)))
2986 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2988 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2989 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2992 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2994 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2995 gimple_predict_outcome (stmt
));
2996 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2997 hints to callers. */
3003 /* Callback for hash_map::traverse, asserts that the pointer map is
3007 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
3010 gcc_assert (!value
);
3014 /* Predict branch probabilities and estimate profile for basic block BB.
3015 When LOCAL_ONLY is set do not use any global properties of CFG. */
3018 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
3023 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3025 /* Look for block we are guarding (ie we dominate it,
3026 but it doesn't postdominate us). */
3027 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
3029 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
3030 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
3032 gimple_stmt_iterator bi
;
3034 /* The call heuristic claims that a guarded function call
3035 is improbable. This is because such calls are often used
3036 to signal exceptional situations such as printing error
3038 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
3041 gimple
*stmt
= gsi_stmt (bi
);
3042 if (is_gimple_call (stmt
)
3043 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
3044 /* Constant and pure calls are hardly used to signalize
3045 something exceptional. */
3046 && gimple_has_side_effects (stmt
))
3048 if (gimple_call_fndecl (stmt
))
3049 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
3050 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
3051 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
3053 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
3059 tree_predict_by_opcode (bb
);
3062 /* Predict branch probabilities and estimate profile of the tree CFG.
3063 This function can be called from the loop optimizers to recompute
3064 the profile information.
3065 If DRY_RUN is set, do not modify CFG and only produce dump files. */
3068 tree_estimate_probability (bool dry_run
)
3072 add_noreturn_fake_exit_edges ();
3073 connect_infinite_loops_to_exit ();
3074 /* We use loop_niter_by_eval, which requires that the loops have
3076 create_preheaders (CP_SIMPLE_PREHEADERS
);
3077 calculate_dominance_info (CDI_POST_DOMINATORS
);
3078 /* Decide which edges are known to be unlikely. This improves later
3079 branch prediction. */
3080 determine_unlikely_bbs ();
3082 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3083 tree_bb_level_predictions ();
3084 record_loop_exits ();
3086 if (number_of_loops (cfun
) > 1)
3089 FOR_EACH_BB_FN (bb
, cfun
)
3090 tree_estimate_probability_bb (bb
, false);
3092 FOR_EACH_BB_FN (bb
, cfun
)
3093 combine_predictions_for_bb (bb
, dry_run
);
3096 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3098 delete bb_predictions
;
3099 bb_predictions
= NULL
;
3102 estimate_bb_frequencies (false);
3103 free_dominance_info (CDI_POST_DOMINATORS
);
3104 remove_fake_exit_edges ();
3107 /* Set edge->probability for each successor edge of BB. */
3109 tree_guess_outgoing_edge_probabilities (basic_block bb
)
3111 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3112 tree_estimate_probability_bb (bb
, true);
3113 combine_predictions_for_bb (bb
, false);
3115 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3116 delete bb_predictions
;
3117 bb_predictions
= NULL
;
3120 /* Predict edges to successors of CUR whose sources are not postdominated by
3121 BB by PRED and recurse to all postdominators. */
3124 predict_paths_for_bb (basic_block cur
, basic_block bb
,
3125 enum br_predictor pred
,
3126 enum prediction taken
,
3127 bitmap visited
, struct loop
*in_loop
= NULL
)
3133 /* If we exited the loop or CUR is unconditional in the loop, there is
3136 && (!flow_bb_inside_loop_p (in_loop
, cur
)
3137 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
3140 /* We are looking for all edges forming edge cut induced by
3141 set of all blocks postdominated by BB. */
3142 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
3143 if (e
->src
->index
>= NUM_FIXED_BLOCKS
3144 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
3150 /* Ignore fake edges and eh, we predict them as not taken anyway. */
3151 if (unlikely_executed_edge_p (e
))
3153 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
3155 /* See if there is an edge from e->src that is not abnormal
3156 and does not lead to BB and does not exit the loop. */
3157 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
3159 && !unlikely_executed_edge_p (e2
)
3160 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
3161 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
3167 /* If there is non-abnormal path leaving e->src, predict edge
3168 using predictor. Otherwise we need to look for paths
3171 The second may lead to infinite loop in the case we are predicitng
3172 regions that are only reachable by abnormal edges. We simply
3173 prevent visiting given BB twice. */
3176 if (!edge_predicted_by_p (e
, pred
, taken
))
3177 predict_edge_def (e
, pred
, taken
);
3179 else if (bitmap_set_bit (visited
, e
->src
->index
))
3180 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
3182 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
3184 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
3185 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
3188 /* Sets branch probabilities according to PREDiction and
3192 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
3193 enum prediction taken
, struct loop
*in_loop
)
3195 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3198 /* Like predict_paths_leading_to but take edge instead of basic block. */
3201 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
3202 enum prediction taken
, struct loop
*in_loop
)
3204 bool has_nonloop_edge
= false;
3208 basic_block bb
= e
->src
;
3209 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
3210 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
3211 && !unlikely_executed_edge_p (e
)
3212 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
3214 has_nonloop_edge
= true;
3217 if (!has_nonloop_edge
)
3219 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3222 predict_edge_def (e
, pred
, taken
);
3225 /* This is used to carry information about basic blocks. It is
3226 attached to the AUX field of the standard CFG block. */
3230 /* Estimated frequency of execution of basic_block. */
3233 /* To keep queue of basic blocks to process. */
3236 /* Number of predecessors we need to visit first. */
3240 /* Similar information for edges. */
3241 struct edge_prob_info
3243 /* In case edge is a loopback edge, the probability edge will be reached
3244 in case header is. Estimated number of iterations of the loop can be
3245 then computed as 1 / (1 - back_edge_prob). */
3246 sreal back_edge_prob
;
3247 /* True if the edge is a loopback edge in the natural loop. */
3248 unsigned int back_edge
:1;
3251 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3253 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3255 /* Helper function for estimate_bb_frequencies.
3256 Propagate the frequencies in blocks marked in
3257 TOVISIT, starting in HEAD. */
3260 propagate_freq (basic_block head
, bitmap tovisit
)
3269 /* For each basic block we need to visit count number of his predecessors
3270 we need to visit first. */
3271 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
3276 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3278 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3280 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3282 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3284 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3286 "Irreducible region hit, ignoring edge to %i->%i\n",
3287 e
->src
->index
, bb
->index
);
3289 BLOCK_INFO (bb
)->npredecessors
= count
;
3290 /* When function never returns, we will never process exit block. */
3291 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3292 bb
->count
= profile_count::zero ();
3295 BLOCK_INFO (head
)->frequency
= 1;
3297 for (bb
= head
; bb
; bb
= nextbb
)
3300 sreal cyclic_probability
= 0;
3301 sreal frequency
= 0;
3303 nextbb
= BLOCK_INFO (bb
)->next
;
3304 BLOCK_INFO (bb
)->next
= NULL
;
3306 /* Compute frequency of basic block. */
3310 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3311 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3312 || (e
->flags
& EDGE_DFS_BACK
));
3314 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3315 if (EDGE_INFO (e
)->back_edge
)
3317 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3319 else if (!(e
->flags
& EDGE_DFS_BACK
))
3321 /* frequency += (e->probability
3322 * BLOCK_INFO (e->src)->frequency /
3323 REG_BR_PROB_BASE); */
3325 /* FIXME: Graphite is producing edges with no profile. Once
3326 this is fixed, drop this. */
3327 sreal tmp
= e
->probability
.initialized_p () ?
3328 e
->probability
.to_reg_br_prob_base () : 0;
3329 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
3330 tmp
*= real_inv_br_prob_base
;
3334 if (cyclic_probability
== 0)
3336 BLOCK_INFO (bb
)->frequency
= frequency
;
3340 if (cyclic_probability
> real_almost_one
)
3341 cyclic_probability
= real_almost_one
;
3343 /* BLOCK_INFO (bb)->frequency = frequency
3344 / (1 - cyclic_probability) */
3346 cyclic_probability
= sreal (1) - cyclic_probability
;
3347 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
3351 bitmap_clear_bit (tovisit
, bb
->index
);
3353 e
= find_edge (bb
, head
);
3356 /* EDGE_INFO (e)->back_edge_prob
3357 = ((e->probability * BLOCK_INFO (bb)->frequency)
3358 / REG_BR_PROB_BASE); */
3360 /* FIXME: Graphite is producing edges with no profile. Once
3361 this is fixed, drop this. */
3362 sreal tmp
= e
->probability
.initialized_p () ?
3363 e
->probability
.to_reg_br_prob_base () : 0;
3364 tmp
*= BLOCK_INFO (bb
)->frequency
;
3365 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
3368 /* Propagate to successor blocks. */
3369 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3370 if (!(e
->flags
& EDGE_DFS_BACK
)
3371 && BLOCK_INFO (e
->dest
)->npredecessors
)
3373 BLOCK_INFO (e
->dest
)->npredecessors
--;
3374 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3379 BLOCK_INFO (last
)->next
= e
->dest
;
3387 /* Estimate frequencies in loops at same nest level. */
3390 estimate_loops_at_level (struct loop
*first_loop
)
3394 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3399 auto_bitmap tovisit
;
3401 estimate_loops_at_level (loop
->inner
);
3403 /* Find current loop back edge and mark it. */
3404 e
= loop_latch_edge (loop
);
3405 EDGE_INFO (e
)->back_edge
= 1;
3407 bbs
= get_loop_body (loop
);
3408 for (i
= 0; i
< loop
->num_nodes
; i
++)
3409 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3411 propagate_freq (loop
->header
, tovisit
);
3415 /* Propagates frequencies through structure of loops. */
3418 estimate_loops (void)
3420 auto_bitmap tovisit
;
3423 /* Start by estimating the frequencies in the loops. */
3424 if (number_of_loops (cfun
) > 1)
3425 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3427 /* Now propagate the frequencies through all the blocks. */
3428 FOR_ALL_BB_FN (bb
, cfun
)
3430 bitmap_set_bit (tovisit
, bb
->index
);
3432 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3435 /* Drop the profile for NODE to guessed, and update its frequency based on
3436 whether it is expected to be hot given the CALL_COUNT. */
3439 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3441 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3442 /* In the case where this was called by another function with a
3443 dropped profile, call_count will be 0. Since there are no
3444 non-zero call counts to this function, we don't know for sure
3445 whether it is hot, and therefore it will be marked normal below. */
3446 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3450 "Dropping 0 profile for %s. %s based on calls.\n",
3452 hot
? "Function is hot" : "Function is normal");
3453 /* We only expect to miss profiles for functions that are reached
3454 via non-zero call edges in cases where the function may have
3455 been linked from another module or library (COMDATs and extern
3456 templates). See the comments below for handle_missing_profiles.
3457 Also, only warn in cases where the missing counts exceed the
3458 number of training runs. In certain cases with an execv followed
3459 by a no-return call the profile for the no-return call is not
3460 dumped and there can be a mismatch. */
3461 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3462 && call_count
> profile_info
->runs
)
3464 if (flag_profile_correction
)
3468 "Missing counts for called function %s\n",
3469 node
->dump_name ());
3472 warning (0, "Missing counts for called function %s",
3473 node
->dump_name ());
3477 if (opt_for_fn (node
->decl
, flag_guess_branch_prob
))
3480 = !ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
.nonzero_p ();
3481 FOR_ALL_BB_FN (bb
, fn
)
3482 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3483 bb
->count
= bb
->count
.guessed_local ();
3484 fn
->cfg
->count_max
= fn
->cfg
->count_max
.guessed_local ();
3488 FOR_ALL_BB_FN (bb
, fn
)
3489 bb
->count
= profile_count::uninitialized ();
3490 fn
->cfg
->count_max
= profile_count::uninitialized ();
3493 struct cgraph_edge
*e
;
3494 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3495 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3496 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3497 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3498 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
;
3500 profile_status_for_fn (fn
)
3501 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3503 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3506 /* In the case of COMDAT routines, multiple object files will contain the same
3507 function and the linker will select one for the binary. In that case
3508 all the other copies from the profile instrument binary will be missing
3509 profile counts. Look for cases where this happened, due to non-zero
3510 call counts going to 0-count functions, and drop the profile to guessed
3511 so that we can use the estimated probabilities and avoid optimizing only
3514 The other case where the profile may be missing is when the routine
3515 is not going to be emitted to the object file, e.g. for "extern template"
3516 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3517 all other cases of non-zero calls to 0-count functions. */
3520 handle_missing_profiles (void)
3522 struct cgraph_node
*node
;
3523 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3524 auto_vec
<struct cgraph_node
*, 64> worklist
;
3526 /* See if 0 count function has non-0 count callers. In this case we
3527 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3528 FOR_EACH_DEFINED_FUNCTION (node
)
3530 struct cgraph_edge
*e
;
3531 profile_count call_count
= profile_count::zero ();
3532 gcov_type max_tp_first_run
= 0;
3533 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3535 if (node
->count
.ipa ().nonzero_p ())
3537 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3538 if (e
->count
.ipa ().initialized_p () && e
->count
.ipa () > 0)
3540 call_count
= call_count
+ e
->count
.ipa ();
3542 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3543 max_tp_first_run
= e
->caller
->tp_first_run
;
3546 /* If time profile is missing, let assign the maximum that comes from
3547 caller functions. */
3548 if (!node
->tp_first_run
&& max_tp_first_run
)
3549 node
->tp_first_run
= max_tp_first_run
+ 1;
3553 && (call_count
.apply_scale (unlikely_count_fraction
, 1)
3554 >= profile_info
->runs
))
3556 drop_profile (node
, call_count
);
3557 worklist
.safe_push (node
);
3561 /* Propagate the profile dropping to other 0-count COMDATs that are
3562 potentially called by COMDATs we already dropped the profile on. */
3563 while (worklist
.length () > 0)
3565 struct cgraph_edge
*e
;
3567 node
= worklist
.pop ();
3568 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3570 struct cgraph_node
*callee
= e
->callee
;
3571 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3573 if (!(e
->count
.ipa () == profile_count::zero ())
3574 && callee
->count
.ipa ().nonzero_p ())
3576 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3578 && profile_status_for_fn (fn
) == PROFILE_READ
)
3580 drop_profile (node
, profile_count::zero ());
3581 worklist
.safe_push (callee
);
3587 /* Convert counts measured by profile driven feedback to frequencies.
3588 Return nonzero iff there was any nonzero execution count. */
3591 update_max_bb_count (void)
3593 profile_count true_count_max
= profile_count::uninitialized ();
3596 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3597 true_count_max
= true_count_max
.max (bb
->count
);
3599 cfun
->cfg
->count_max
= true_count_max
;
3601 return true_count_max
.ipa ().nonzero_p ();
3604 /* Return true if function is likely to be expensive, so there is no point to
3605 optimize performance of prologue, epilogue or do inlining at the expense
3606 of code size growth. THRESHOLD is the limit of number of instructions
3607 function can execute at average to be still considered not expensive. */
3610 expensive_function_p (int threshold
)
3614 /* If profile was scaled in a way entry block has count 0, then the function
3615 is deifnitly taking a lot of time. */
3616 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3619 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN
3620 (cfun
)->count
.apply_scale (threshold
, 1);
3621 profile_count sum
= profile_count::zero ();
3622 FOR_EACH_BB_FN (bb
, cfun
)
3626 if (!bb
->count
.initialized_p ())
3629 fprintf (dump_file
, "Function is considered expensive because"
3630 " count of bb %i is not initialized\n", bb
->index
);
3634 FOR_BB_INSNS (bb
, insn
)
3635 if (active_insn_p (insn
))
3646 /* All basic blocks that are reachable only from unlikely basic blocks are
3650 propagate_unlikely_bbs_forward (void)
3652 auto_vec
<basic_block
, 64> worklist
;
3657 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3659 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3660 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3662 while (worklist
.length () > 0)
3664 bb
= worklist
.pop ();
3665 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3666 if (!(e
->count () == profile_count::zero ())
3667 && !(e
->dest
->count
== profile_count::zero ())
3670 e
->dest
->aux
= (void *)(size_t) 1;
3671 worklist
.safe_push (e
->dest
);
3676 FOR_ALL_BB_FN (bb
, cfun
)
3680 if (!(bb
->count
== profile_count::zero ())
3681 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3683 "Basic block %i is marked unlikely by forward prop\n",
3685 bb
->count
= profile_count::zero ();
3692 /* Determine basic blocks/edges that are known to be unlikely executed and set
3693 their counters to zero.
3694 This is done with first identifying obviously unlikely BBs/edges and then
3695 propagating in both directions. */
3698 determine_unlikely_bbs ()
3701 auto_vec
<basic_block
, 64> worklist
;
3705 FOR_EACH_BB_FN (bb
, cfun
)
3707 if (!(bb
->count
== profile_count::zero ())
3708 && unlikely_executed_bb_p (bb
))
3710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3711 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3713 bb
->count
= profile_count::zero ();
3716 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3717 if (!(e
->probability
== profile_probability::never ())
3718 && unlikely_executed_edge_p (e
))
3720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3721 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3722 bb
->index
, e
->dest
->index
);
3723 e
->probability
= profile_probability::never ();
3726 gcc_checking_assert (!bb
->aux
);
3728 propagate_unlikely_bbs_forward ();
3730 auto_vec
<int, 64> nsuccs
;
3731 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
3732 FOR_ALL_BB_FN (bb
, cfun
)
3733 if (!(bb
->count
== profile_count::zero ())
3734 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3736 nsuccs
[bb
->index
] = 0;
3737 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3738 if (!(e
->probability
== profile_probability::never ())
3739 && !(e
->dest
->count
== profile_count::zero ()))
3740 nsuccs
[bb
->index
]++;
3741 if (!nsuccs
[bb
->index
])
3742 worklist
.safe_push (bb
);
3744 while (worklist
.length () > 0)
3746 bb
= worklist
.pop ();
3747 if (bb
->count
== profile_count::zero ())
3749 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3752 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3753 !gsi_end_p (gsi
); gsi_next (&gsi
))
3754 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3755 /* stmt_can_terminate_bb_p special cases noreturns because it
3756 assumes that fake edges are created. We want to know that
3757 noreturn alone does not imply BB to be unlikely. */
3758 || (is_gimple_call (gsi_stmt (gsi
))
3759 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3767 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3769 "Basic block %i is marked unlikely by backward prop\n",
3771 bb
->count
= profile_count::zero ();
3772 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3773 if (!(e
->probability
== profile_probability::never ()))
3775 if (!(e
->src
->count
== profile_count::zero ()))
3777 gcc_checking_assert (nsuccs
[e
->src
->index
] > 0);
3778 nsuccs
[e
->src
->index
]--;
3779 if (!nsuccs
[e
->src
->index
])
3780 worklist
.safe_push (e
->src
);
3784 /* Finally all edges from non-0 regions to 0 are unlikely. */
3785 FOR_ALL_BB_FN (bb
, cfun
)
3787 if (!(bb
->count
== profile_count::zero ()))
3788 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3789 if (!(e
->probability
== profile_probability::never ())
3790 && e
->dest
->count
== profile_count::zero ())
3792 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3793 fprintf (dump_file
, "Edge %i->%i is unlikely because "
3794 "it enters unlikely block\n",
3795 bb
->index
, e
->dest
->index
);
3796 e
->probability
= profile_probability::never ();
3801 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3802 if (e
->probability
== profile_probability::never ())
3812 && !(other
->probability
== profile_probability::always ()))
3814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3815 fprintf (dump_file
, "Edge %i->%i is locally likely\n",
3816 bb
->index
, other
->dest
->index
);
3817 other
->probability
= profile_probability::always ();
3820 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3821 cgraph_node::get (current_function_decl
)->count
= profile_count::zero ();
3824 /* Estimate and propagate basic block frequencies using the given branch
3825 probabilities. If FORCE is true, the frequencies are used to estimate
3826 the counts even when there are already non-zero profile counts. */
3829 estimate_bb_frequencies (bool force
)
3834 determine_unlikely_bbs ();
3836 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3837 || !update_max_bb_count ())
3839 static int real_values_initialized
= 0;
3841 if (!real_values_initialized
)
3843 real_values_initialized
= 1;
3844 real_br_prob_base
= REG_BR_PROB_BASE
;
3845 /* Scaling frequencies up to maximal profile count may result in
3846 frequent overflows especially when inlining loops.
3847 Small scalling results in unnecesary precision loss. Stay in
3848 the half of the (exponential) range. */
3849 real_bb_freq_max
= (uint64_t)1 << (profile_count::n_bits
/ 2);
3850 real_one_half
= sreal (1, -1);
3851 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3852 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3855 mark_dfs_back_edges ();
3857 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3858 profile_probability::always ();
3860 /* Set up block info for each basic block. */
3861 alloc_aux_for_blocks (sizeof (block_info
));
3862 alloc_aux_for_edges (sizeof (edge_prob_info
));
3863 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3868 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3870 /* FIXME: Graphite is producing edges with no profile. Once
3871 this is fixed, drop this. */
3872 if (e
->probability
.initialized_p ())
3873 EDGE_INFO (e
)->back_edge_prob
3874 = e
->probability
.to_reg_br_prob_base ();
3876 EDGE_INFO (e
)->back_edge_prob
= REG_BR_PROB_BASE
/ 2;
3877 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3881 /* First compute frequencies locally for each loop from innermost
3882 to outermost to examine frequencies for back edges. */
3886 FOR_EACH_BB_FN (bb
, cfun
)
3887 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3888 freq_max
= BLOCK_INFO (bb
)->frequency
;
3890 freq_max
= real_bb_freq_max
/ freq_max
;
3893 profile_count ipa_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ();
3894 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3895 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3897 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3898 profile_count count
= profile_count::from_gcov_type (tmp
.to_int ());
3900 /* If we have profile feedback in which this function was never
3901 executed, then preserve this info. */
3902 if (!(bb
->count
== profile_count::zero ()))
3903 bb
->count
= count
.guessed_local ().combine_with_ipa_count (ipa_count
);
3904 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3907 free_aux_for_blocks ();
3908 free_aux_for_edges ();
3910 compute_function_frequency ();
3913 /* Decide whether function is hot, cold or unlikely executed. */
3915 compute_function_frequency (void)
3918 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3920 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3921 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3922 node
->only_called_at_startup
= true;
3923 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3924 node
->only_called_at_exit
= true;
3926 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3928 int flags
= flags_from_decl_or_type (current_function_decl
);
3929 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ()
3930 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3931 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3934 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3935 warn_function_cold (current_function_decl
);
3937 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3939 node
->frequency
= NODE_FREQUENCY_HOT
;
3940 else if (flags
& ECF_NORETURN
)
3941 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3942 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3943 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3944 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3945 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3946 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3950 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3951 warn_function_cold (current_function_decl
);
3952 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3954 FOR_EACH_BB_FN (bb
, cfun
)
3956 if (maybe_hot_bb_p (cfun
, bb
))
3958 node
->frequency
= NODE_FREQUENCY_HOT
;
3961 if (!probably_never_executed_bb_p (cfun
, bb
))
3962 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3966 /* Build PREDICT_EXPR. */
3968 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3970 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3971 build_int_cst (integer_type_node
, predictor
));
3972 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3977 predictor_name (enum br_predictor predictor
)
3979 return predictor_info
[predictor
].name
;
3982 /* Predict branch probabilities and estimate profile of the tree CFG. */
3986 const pass_data pass_data_profile
=
3988 GIMPLE_PASS
, /* type */
3989 "profile_estimate", /* name */
3990 OPTGROUP_NONE
, /* optinfo_flags */
3991 TV_BRANCH_PROB
, /* tv_id */
3992 PROP_cfg
, /* properties_required */
3993 0, /* properties_provided */
3994 0, /* properties_destroyed */
3995 0, /* todo_flags_start */
3996 0, /* todo_flags_finish */
3999 class pass_profile
: public gimple_opt_pass
4002 pass_profile (gcc::context
*ctxt
)
4003 : gimple_opt_pass (pass_data_profile
, ctxt
)
4006 /* opt_pass methods: */
4007 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
4008 virtual unsigned int execute (function
*);
4010 }; // class pass_profile
4013 pass_profile::execute (function
*fun
)
4017 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4020 loop_optimizer_init (LOOPS_NORMAL
);
4021 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4022 flow_loops_dump (dump_file
, NULL
, 0);
4024 mark_irreducible_loops ();
4026 nb_loops
= number_of_loops (fun
);
4030 tree_estimate_probability (false);
4035 loop_optimizer_finalize ();
4036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4037 gimple_dump_cfg (dump_file
, dump_flags
);
4038 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
4039 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
4040 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4043 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
4044 if (loop
->header
->count
.initialized_p ())
4045 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
4047 (int)expected_loop_iterations_unbounded (loop
));
4055 make_pass_profile (gcc::context
*ctxt
)
4057 return new pass_profile (ctxt
);
4060 /* Return true when PRED predictor should be removed after early
4061 tree passes. Most of the predictors are beneficial to survive
4062 as early inlining can also distribute then into caller's bodies. */
4065 strip_predictor_early (enum br_predictor pred
)
4069 case PRED_TREE_EARLY_RETURN
:
4076 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4077 we no longer need. EARLY is set to true when called from early
4081 strip_predict_hints (function
*fun
, bool early
)
4086 bool changed
= false;
4088 FOR_EACH_BB_FN (bb
, fun
)
4090 gimple_stmt_iterator bi
;
4091 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
4093 gimple
*stmt
= gsi_stmt (bi
);
4095 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
4098 || strip_predictor_early (gimple_predict_predictor (stmt
)))
4100 gsi_remove (&bi
, true);
4105 else if (is_gimple_call (stmt
))
4107 tree fndecl
= gimple_call_fndecl (stmt
);
4110 && ((fndecl
!= NULL_TREE
4111 && fndecl_built_in_p (fndecl
, BUILT_IN_EXPECT
)
4112 && gimple_call_num_args (stmt
) == 2)
4113 || (fndecl
!= NULL_TREE
4114 && fndecl_built_in_p (fndecl
,
4115 BUILT_IN_EXPECT_WITH_PROBABILITY
)
4116 && gimple_call_num_args (stmt
) == 3)
4117 || (gimple_call_internal_p (stmt
)
4118 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
)))
4120 var
= gimple_call_lhs (stmt
);
4125 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
4126 gsi_replace (&bi
, ass_stmt
, true);
4130 gsi_remove (&bi
, true);
4138 return changed
? TODO_cleanup_cfg
: 0;
4143 const pass_data pass_data_strip_predict_hints
=
4145 GIMPLE_PASS
, /* type */
4146 "*strip_predict_hints", /* name */
4147 OPTGROUP_NONE
, /* optinfo_flags */
4148 TV_BRANCH_PROB
, /* tv_id */
4149 PROP_cfg
, /* properties_required */
4150 0, /* properties_provided */
4151 0, /* properties_destroyed */
4152 0, /* todo_flags_start */
4153 0, /* todo_flags_finish */
4156 class pass_strip_predict_hints
: public gimple_opt_pass
4159 pass_strip_predict_hints (gcc::context
*ctxt
)
4160 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
4163 /* opt_pass methods: */
4164 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
4165 void set_pass_param (unsigned int n
, bool param
)
4167 gcc_assert (n
== 0);
4171 virtual unsigned int execute (function
*);
4176 }; // class pass_strip_predict_hints
4179 pass_strip_predict_hints::execute (function
*fun
)
4181 return strip_predict_hints (fun
, early_p
);
4187 make_pass_strip_predict_hints (gcc::context
*ctxt
)
4189 return new pass_strip_predict_hints (ctxt
);
4192 /* Rebuild function frequencies. Passes are in general expected to
4193 maintain profile by hand, however in some cases this is not possible:
4194 for example when inlining several functions with loops freuqencies might run
4195 out of scale and thus needs to be recomputed. */
4198 rebuild_frequencies (void)
4200 timevar_push (TV_REBUILD_FREQUENCIES
);
4202 /* When the max bb count in the function is small, there is a higher
4203 chance that there were truncation errors in the integer scaling
4204 of counts by inlining and other optimizations. This could lead
4205 to incorrect classification of code as being cold when it isn't.
4206 In that case, force the estimation of bb counts/frequencies from the
4207 branch probabilities, rather than computing frequencies from counts,
4208 which may also lead to frequencies incorrectly reduced to 0. There
4209 is less precision in the probabilities, so we only do this for small
4211 cfun
->cfg
->count_max
= profile_count::uninitialized ();
4213 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
4214 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
4216 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4218 loop_optimizer_init (0);
4219 add_noreturn_fake_exit_edges ();
4220 mark_irreducible_loops ();
4221 connect_infinite_loops_to_exit ();
4222 estimate_bb_frequencies (true);
4223 remove_fake_exit_edges ();
4224 loop_optimizer_finalize ();
4226 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
4227 update_max_bb_count ();
4228 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
4229 && !flag_guess_branch_prob
)
4233 timevar_pop (TV_REBUILD_FREQUENCIES
);
4236 /* Perform a dry run of the branch prediction pass and report comparsion of
4237 the predicted and real profile into the dump file. */
4240 report_predictor_hitrates (void)
4244 loop_optimizer_init (LOOPS_NORMAL
);
4245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4246 flow_loops_dump (dump_file
, NULL
, 0);
4248 mark_irreducible_loops ();
4250 nb_loops
= number_of_loops (cfun
);
4254 tree_estimate_probability (true);
4259 loop_optimizer_finalize ();
4262 /* Force edge E to be cold.
4263 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4264 keep low probability to represent possible error in a guess. This is used
4265 i.e. in case we predict loop to likely iterate given number of times but
4266 we are not 100% sure.
4268 This function locally updates profile without attempt to keep global
4269 consistency which cannot be reached in full generality without full profile
4270 rebuild from probabilities alone. Doing so is not necessarily a good idea
4271 because frequencies and counts may be more realistic then probabilities.
4273 In some cases (such as for elimination of early exits during full loop
4274 unrolling) the caller can ensure that profile will get consistent
4278 force_edge_cold (edge e
, bool impossible
)
4280 profile_count count_sum
= profile_count::zero ();
4281 profile_probability prob_sum
= profile_probability::never ();
4284 bool uninitialized_exit
= false;
4286 /* When branch probability guesses are not known, then do nothing. */
4287 if (!impossible
&& !e
->count ().initialized_p ())
4290 profile_probability goal
= (impossible
? profile_probability::never ()
4291 : profile_probability::very_unlikely ());
4293 /* If edge is already improbably or cold, just return. */
4294 if (e
->probability
<= goal
4295 && (!impossible
|| e
->count () == profile_count::zero ()))
4297 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4300 if (e
->flags
& EDGE_FAKE
)
4302 if (e2
->count ().initialized_p ())
4303 count_sum
+= e2
->count ();
4304 if (e2
->probability
.initialized_p ())
4305 prob_sum
+= e2
->probability
;
4307 uninitialized_exit
= true;
4310 /* If we are not guessing profiles but have some other edges out,
4311 just assume the control flow goes elsewhere. */
4312 if (uninitialized_exit
)
4313 e
->probability
= goal
;
4314 /* If there are other edges out of e->src, redistribute probabilitity
4316 else if (prob_sum
> profile_probability::never ())
4318 if (!(e
->probability
< goal
))
4319 e
->probability
= goal
;
4321 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
4323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4324 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
4325 "probability to other edges.\n",
4326 e
->src
->index
, e
->dest
->index
,
4327 impossible
? "impossible" : "cold");
4328 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4331 e2
->probability
/= prob_comp
;
4333 if (current_ir_type () != IR_GIMPLE
4334 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4335 update_br_prob_note (e
->src
);
4337 /* If all edges out of e->src are unlikely, the basic block itself
4341 if (prob_sum
== profile_probability::never ())
4342 e
->probability
= profile_probability::always ();
4346 e
->probability
= profile_probability::never ();
4347 /* If BB has some edges out that are not impossible, we cannot
4348 assume that BB itself is. */
4351 if (current_ir_type () != IR_GIMPLE
4352 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4353 update_br_prob_note (e
->src
);
4354 if (e
->src
->count
== profile_count::zero ())
4356 if (count_sum
== profile_count::zero () && impossible
)
4359 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4361 else if (current_ir_type () == IR_GIMPLE
)
4362 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4363 !gsi_end_p (gsi
); gsi_next (&gsi
))
4365 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4371 /* FIXME: Implement RTL path. */
4376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4378 "Making bb %i impossible and dropping count to 0.\n",
4380 e
->src
->count
= profile_count::zero ();
4381 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4382 force_edge_cold (e2
, impossible
);
4387 /* If we did not adjusting, the source basic block has no likely edeges
4388 leaving other direction. In that case force that bb cold, too.
4389 This in general is difficult task to do, but handle special case when
4390 BB has only one predecestor. This is common case when we are updating
4391 after loop transforms. */
4392 if (!(prob_sum
> profile_probability::never ())
4393 && count_sum
== profile_count::zero ()
4394 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4395 > (impossible
? 0 : 1))
4397 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4399 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4400 impossible
? "impossible" : "cold");
4401 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4402 impossible
? 0 : 1);
4404 e
->src
->count
= profile_count::zero ();
4406 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4408 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4410 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4411 && maybe_hot_bb_p (cfun
, e
->src
))
4412 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4413 impossible
? "impossible" : "cold");
4419 namespace selftest
{
4421 /* Test that value range of predictor values defined in predict.def is
4422 within range (50, 100]. */
4424 struct branch_predictor
4430 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4433 test_prediction_value_range ()
4435 branch_predictor predictors
[] = {
4436 #include "predict.def"
4437 { NULL
, PROB_UNINITIALIZED
}
4440 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4442 if (predictors
[i
].probability
== PROB_UNINITIALIZED
)
4445 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4446 ASSERT_TRUE (p
>= 50 && p
<= 100);
4450 #undef DEF_PREDICTOR
4452 /* Run all of the selfests within this file. */
4457 test_prediction_value_range ();
4460 } // namespace selftest
4461 #endif /* CHECKING_P. */