1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 [1] "Branch Prediction for Free"
23 Ball and Larus; PLDI '93.
24 [2] "Static Branch Frequency and Program Profile Analysis"
25 Wu and Larus; MICRO-27.
26 [3] "Corpus-based Static Branch Prediction"
27 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
32 #include "coretypes.h"
38 #include "tree-pass.h"
44 #include "diagnostic-core.h"
45 #include "gimple-predict.h"
46 #include "fold-const.h"
53 #include "gimple-iterator.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-scalar-evolution.h"
58 #include "ipa-utils.h"
59 #include "gimple-pretty-print.h"
62 #include "stringpool.h"
65 /* Enum with reasons why a predictor is ignored. */
71 REASON_SINGLE_EDGE_DUPLICATE
,
72 REASON_EDGE_PAIR_DUPLICATE
75 /* String messages for the aforementioned enum. */
77 static const char *reason_messages
[] = {"", " (ignored)",
78 " (single edge duplicate)", " (edge pair duplicate)"};
80 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
81 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
82 static sreal real_almost_one
, real_br_prob_base
,
83 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
85 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
86 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
,
87 enum predictor_reason
, edge
);
88 static void predict_paths_leading_to (basic_block
, enum br_predictor
,
90 struct loop
*in_loop
= NULL
);
91 static void predict_paths_leading_to_edge (edge
, enum br_predictor
,
93 struct loop
*in_loop
= NULL
);
94 static bool can_predict_insn_p (const rtx_insn
*);
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 can not 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
);
880 profile_probability remainder
= prob
.invert ();
882 if (prediction
->ep_edge
== e
)
883 e
->probability
= prob
;
885 e
->probability
= remainder
.apply_scale (1, nedges
- 1);
888 e
->probability
= profile_probability::never ();
892 /* Make all unlikely edges unlikely and the rest will have even
894 unsigned scale
= nedges
- unlikely_count
;
895 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
896 if (e
->probability
.initialized_p ())
898 else if (!unlikely_executed_edge_p (e
))
900 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
901 e
->probability
= profile_probability::very_unlikely ();
903 e
->probability
= all
.apply_scale (1, scale
);
906 e
->probability
= profile_probability::never ();
910 /* Add REG_BR_PROB note to JUMP with PROB. */
913 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
915 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
916 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
919 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
920 note if not already present. Remove now useless REG_BR_PRED notes. */
923 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
928 int best_probability
= PROB_EVEN
;
929 enum br_predictor best_predictor
= END_PREDICTORS
;
930 int combined_probability
= REG_BR_PROB_BASE
/ 2;
932 bool first_match
= false;
935 if (!can_predict_insn_p (insn
))
937 set_even_probabilities (bb
);
941 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
942 pnote
= ®_NOTES (insn
);
944 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
947 /* We implement "first match" heuristics and use probability guessed
948 by predictor with smallest index. */
949 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
950 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
952 enum br_predictor predictor
= ((enum br_predictor
)
953 INTVAL (XEXP (XEXP (note
, 0), 0)));
954 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
957 if (best_predictor
> predictor
958 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
959 best_probability
= probability
, best_predictor
= predictor
;
961 d
= (combined_probability
* probability
962 + (REG_BR_PROB_BASE
- combined_probability
)
963 * (REG_BR_PROB_BASE
- probability
));
965 /* Use FP math to avoid overflows of 32bit integers. */
967 /* If one probability is 0% and one 100%, avoid division by zero. */
968 combined_probability
= REG_BR_PROB_BASE
/ 2;
970 combined_probability
= (((double) combined_probability
) * probability
971 * REG_BR_PROB_BASE
/ d
+ 0.5);
974 /* Decide which heuristic to use. In case we didn't match anything,
975 use no_prediction heuristic, in case we did match, use either
976 first match or Dempster-Shaffer theory depending on the flags. */
978 if (best_predictor
!= END_PREDICTORS
)
982 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
983 combined_probability
, bb
);
987 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
988 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
990 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
991 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
995 combined_probability
= best_probability
;
996 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1000 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
1002 enum br_predictor predictor
= ((enum br_predictor
)
1003 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
1004 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
1006 dump_prediction (dump_file
, predictor
, probability
, bb
,
1007 (!first_match
|| best_predictor
== predictor
)
1008 ? REASON_NONE
: REASON_IGNORED
);
1009 *pnote
= XEXP (*pnote
, 1);
1012 pnote
= &XEXP (*pnote
, 1);
1017 profile_probability p
1018 = profile_probability::from_reg_br_prob_base (combined_probability
);
1019 add_reg_br_prob_note (insn
, p
);
1021 /* Save the prediction into CFG in case we are seeing non-degenerated
1022 conditional jump. */
1023 if (!single_succ_p (bb
))
1025 BRANCH_EDGE (bb
)->probability
= p
;
1026 FALLTHRU_EDGE (bb
)->probability
1027 = BRANCH_EDGE (bb
)->probability
.invert ();
1030 else if (!single_succ_p (bb
))
1032 profile_probability prob
= profile_probability::from_reg_br_prob_note
1033 (XINT (prob_note
, 0));
1035 BRANCH_EDGE (bb
)->probability
= prob
;
1036 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
1039 single_succ_edge (bb
)->probability
= profile_probability::always ();
1042 /* Edge prediction hash traits. */
1044 struct predictor_hash
: pointer_hash
<edge_prediction
>
1047 static inline hashval_t
hash (const edge_prediction
*);
1048 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
1051 /* Calculate hash value of an edge prediction P based on predictor and
1052 normalized probability. */
1055 predictor_hash::hash (const edge_prediction
*p
)
1057 inchash::hash hstate
;
1058 hstate
.add_int (p
->ep_predictor
);
1060 int prob
= p
->ep_probability
;
1061 if (prob
> REG_BR_PROB_BASE
/ 2)
1062 prob
= REG_BR_PROB_BASE
- prob
;
1064 hstate
.add_int (prob
);
1066 return hstate
.end ();
1069 /* Return true whether edge predictions P1 and P2 use the same predictor and
1070 have equal (or opposed probability). */
1073 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1075 return (p1
->ep_predictor
== p2
->ep_predictor
1076 && (p1
->ep_probability
== p2
->ep_probability
1077 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1080 struct predictor_hash_traits
: predictor_hash
,
1081 typed_noop_remove
<edge_prediction
*> {};
1083 /* Return true if edge prediction P is not in DATA hash set. */
1086 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1088 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1089 return !remove
->contains (p
);
1092 /* Prune predictions for a basic block BB. Currently we do following
1095 1) remove duplicate prediction that is guessed with the same probability
1096 (different than 1/2) to both edge
1097 2) remove duplicates for a prediction that belongs with the same probability
1103 prune_predictions_for_bb (basic_block bb
)
1105 edge_prediction
**preds
= bb_predictions
->get (bb
);
1109 hash_table
<predictor_hash_traits
> s (13);
1110 hash_set
<edge_prediction
*> remove
;
1112 /* Step 1: identify predictors that should be removed. */
1113 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1115 edge_prediction
*existing
= s
.find (pred
);
1118 if (pred
->ep_edge
== existing
->ep_edge
1119 && pred
->ep_probability
== existing
->ep_probability
)
1121 /* Remove a duplicate predictor. */
1122 dump_prediction (dump_file
, pred
->ep_predictor
,
1123 pred
->ep_probability
, bb
,
1124 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1128 else if (pred
->ep_edge
!= existing
->ep_edge
1129 && pred
->ep_probability
== existing
->ep_probability
1130 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1132 /* Remove both predictors as they predict the same
1134 dump_prediction (dump_file
, existing
->ep_predictor
,
1135 pred
->ep_probability
, bb
,
1136 REASON_EDGE_PAIR_DUPLICATE
,
1138 dump_prediction (dump_file
, pred
->ep_predictor
,
1139 pred
->ep_probability
, bb
,
1140 REASON_EDGE_PAIR_DUPLICATE
,
1143 remove
.add (existing
);
1148 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1152 /* Step 2: Remove predictors. */
1153 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1157 /* Combine predictions into single probability and store them into CFG.
1158 Remove now useless prediction entries.
1159 If DRY_RUN is set, only produce dumps and do not modify profile. */
1162 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1164 int best_probability
= PROB_EVEN
;
1165 enum br_predictor best_predictor
= END_PREDICTORS
;
1166 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1168 bool first_match
= false;
1170 struct edge_prediction
*pred
;
1172 edge e
, first
= NULL
, second
= NULL
;
1177 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1179 if (!unlikely_executed_edge_p (e
))
1182 if (first
&& !second
)
1187 else if (!e
->probability
.initialized_p ())
1188 e
->probability
= profile_probability::never ();
1189 if (!e
->probability
.initialized_p ())
1191 else if (e
->probability
== profile_probability::never ())
1195 /* When there is no successor or only one choice, prediction is easy.
1197 When we have a basic block with more than 2 successors, the situation
1198 is more complicated as DS theory cannot be used literally.
1199 More precisely, let's assume we predicted edge e1 with probability p1,
1200 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1201 need to find probability of e.g. m1({b2}), which we don't know.
1202 The only approximation is to equally distribute 1-p1 to all edges
1205 According to numbers we've got from SPEC2006 benchark, there's only
1206 one interesting reliable predictor (noreturn call), which can be
1207 handled with a bit easier approach. */
1210 hash_set
<edge
> unlikely_edges (4);
1211 hash_set
<edge_prediction
*> likely_edges (4);
1213 /* Identify all edges that have a probability close to very unlikely.
1214 Doing the approach for very unlikely doesn't worth for doing as
1215 there's no such probability in SPEC2006 benchmark. */
1216 edge_prediction
**preds
= bb_predictions
->get (bb
);
1218 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1220 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
)
1221 unlikely_edges
.add (pred
->ep_edge
);
1222 if (pred
->ep_probability
>= PROB_VERY_LIKELY
1223 || pred
->ep_predictor
== PRED_BUILTIN_EXPECT
)
1224 likely_edges
.add (pred
);
1228 set_even_probabilities (bb
, &unlikely_edges
, &likely_edges
);
1229 clear_bb_predictions (bb
);
1232 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1233 if (unlikely_edges
.elements () == 0)
1235 "%i edges in bb %i predicted to even probabilities\n",
1240 "%i edges in bb %i predicted with some unlikely edges\n",
1242 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1243 if (!unlikely_executed_edge_p (e
))
1244 dump_prediction (dump_file
, PRED_COMBINED
,
1245 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1252 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1254 prune_predictions_for_bb (bb
);
1256 edge_prediction
**preds
= bb_predictions
->get (bb
);
1260 /* We implement "first match" heuristics and use probability guessed
1261 by predictor with smallest index. */
1262 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1264 enum br_predictor predictor
= pred
->ep_predictor
;
1265 int probability
= pred
->ep_probability
;
1267 if (pred
->ep_edge
!= first
)
1268 probability
= REG_BR_PROB_BASE
- probability
;
1271 /* First match heuristics would be widly confused if we predicted
1273 if (best_predictor
> predictor
1274 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1276 struct edge_prediction
*pred2
;
1277 int prob
= probability
;
1279 for (pred2
= (struct edge_prediction
*) *preds
;
1280 pred2
; pred2
= pred2
->ep_next
)
1281 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1283 int probability2
= pred2
->ep_probability
;
1285 if (pred2
->ep_edge
!= first
)
1286 probability2
= REG_BR_PROB_BASE
- probability2
;
1288 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1289 (probability2
< REG_BR_PROB_BASE
/ 2))
1292 /* If the same predictor later gave better result, go for it! */
1293 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1294 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1295 prob
= probability2
;
1298 best_probability
= prob
, best_predictor
= predictor
;
1301 d
= (combined_probability
* probability
1302 + (REG_BR_PROB_BASE
- combined_probability
)
1303 * (REG_BR_PROB_BASE
- probability
));
1305 /* Use FP math to avoid overflows of 32bit integers. */
1307 /* If one probability is 0% and one 100%, avoid division by zero. */
1308 combined_probability
= REG_BR_PROB_BASE
/ 2;
1310 combined_probability
= (((double) combined_probability
)
1312 * REG_BR_PROB_BASE
/ d
+ 0.5);
1316 /* Decide which heuristic to use. In case we didn't match anything,
1317 use no_prediction heuristic, in case we did match, use either
1318 first match or Dempster-Shaffer theory depending on the flags. */
1320 if (best_predictor
!= END_PREDICTORS
)
1324 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1328 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1329 !first_match
? REASON_NONE
: REASON_IGNORED
);
1331 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1332 first_match
? REASON_NONE
: REASON_IGNORED
);
1336 combined_probability
= best_probability
;
1337 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1341 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1343 enum br_predictor predictor
= pred
->ep_predictor
;
1344 int probability
= pred
->ep_probability
;
1346 dump_prediction (dump_file
, predictor
, probability
, bb
,
1347 (!first_match
|| best_predictor
== predictor
)
1348 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1351 clear_bb_predictions (bb
);
1354 /* If we have only one successor which is unknown, we can compute missing
1358 profile_probability prob
= profile_probability::always ();
1359 edge missing
= NULL
;
1361 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1362 if (e
->probability
.initialized_p ())
1363 prob
-= e
->probability
;
1364 else if (missing
== NULL
)
1368 missing
->probability
= prob
;
1370 /* If nothing is unknown, we have nothing to update. */
1371 else if (!nunknown
&& nzero
!= (int)EDGE_COUNT (bb
->succs
))
1376 = profile_probability::from_reg_br_prob_base (combined_probability
);
1377 second
->probability
= first
->probability
.invert ();
1381 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1382 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1384 T1 and T2 should be one of the following cases:
1385 1. T1 is SSA_NAME, T2 is NULL
1386 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1387 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1390 strips_small_constant (tree t1
, tree t2
)
1397 else if (TREE_CODE (t1
) == SSA_NAME
)
1399 else if (tree_fits_shwi_p (t1
))
1400 value
= tree_to_shwi (t1
);
1406 else if (tree_fits_shwi_p (t2
))
1407 value
= tree_to_shwi (t2
);
1408 else if (TREE_CODE (t2
) == SSA_NAME
)
1416 if (value
<= 4 && value
>= -4)
1422 /* Return the SSA_NAME in T or T's operands.
1423 Return NULL if SSA_NAME cannot be found. */
1426 get_base_value (tree t
)
1428 if (TREE_CODE (t
) == SSA_NAME
)
1431 if (!BINARY_CLASS_P (t
))
1434 switch (TREE_OPERAND_LENGTH (t
))
1437 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1439 return strips_small_constant (TREE_OPERAND (t
, 0),
1440 TREE_OPERAND (t
, 1));
1446 /* Check the compare STMT in LOOP. If it compares an induction
1447 variable to a loop invariant, return true, and save
1448 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1449 Otherwise return false and set LOOP_INVAIANT to NULL. */
1452 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1453 tree
*loop_invariant
,
1454 enum tree_code
*compare_code
,
1458 tree op0
, op1
, bound
, base
;
1460 enum tree_code code
;
1463 code
= gimple_cond_code (stmt
);
1464 *loop_invariant
= NULL
;
1480 op0
= gimple_cond_lhs (stmt
);
1481 op1
= gimple_cond_rhs (stmt
);
1483 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1484 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1486 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1488 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1490 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1491 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1493 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1494 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1497 if (integer_zerop (iv0
.step
))
1499 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1500 code
= invert_tree_comparison (code
, false);
1503 if (tree_fits_shwi_p (iv1
.step
))
1512 if (tree_fits_shwi_p (iv0
.step
))
1518 if (TREE_CODE (bound
) != INTEGER_CST
)
1519 bound
= get_base_value (bound
);
1522 if (TREE_CODE (base
) != INTEGER_CST
)
1523 base
= get_base_value (base
);
1527 *loop_invariant
= bound
;
1528 *compare_code
= code
;
1530 *loop_iv_base
= base
;
1534 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1537 expr_coherent_p (tree t1
, tree t2
)
1540 tree ssa_name_1
= NULL
;
1541 tree ssa_name_2
= NULL
;
1543 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1544 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1549 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1551 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1554 /* Check to see if t1 is expressed/defined with t2. */
1555 stmt
= SSA_NAME_DEF_STMT (t1
);
1556 gcc_assert (stmt
!= NULL
);
1557 if (is_gimple_assign (stmt
))
1559 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1560 if (ssa_name_1
&& ssa_name_1
== t2
)
1564 /* Check to see if t2 is expressed/defined with t1. */
1565 stmt
= SSA_NAME_DEF_STMT (t2
);
1566 gcc_assert (stmt
!= NULL
);
1567 if (is_gimple_assign (stmt
))
1569 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1570 if (ssa_name_2
&& ssa_name_2
== t1
)
1574 /* Compare if t1 and t2's def_stmts are identical. */
1575 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1581 /* Return true if E is predicted by one of loop heuristics. */
1584 predicted_by_loop_heuristics_p (basic_block bb
)
1586 struct edge_prediction
*i
;
1587 edge_prediction
**preds
= bb_predictions
->get (bb
);
1592 for (i
= *preds
; i
; i
= i
->ep_next
)
1593 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1594 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1595 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1596 || i
->ep_predictor
== PRED_LOOP_EXIT
1597 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1598 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1603 /* Predict branch probability of BB when BB contains a branch that compares
1604 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1605 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1608 for (int i = 0; i < bound; i++) {
1615 In this loop, we will predict the branch inside the loop to be taken. */
1618 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1619 tree loop_bound_var
,
1620 tree loop_iv_base_var
,
1621 enum tree_code loop_bound_code
,
1622 int loop_bound_step
)
1625 tree compare_var
, compare_base
;
1626 enum tree_code compare_code
;
1627 tree compare_step_var
;
1631 if (predicted_by_loop_heuristics_p (bb
))
1634 stmt
= last_stmt (bb
);
1635 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1637 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1644 /* Find the taken edge. */
1645 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1646 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1649 /* When comparing an IV to a loop invariant, NE is more likely to be
1650 taken while EQ is more likely to be not-taken. */
1651 if (compare_code
== NE_EXPR
)
1653 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1656 else if (compare_code
== EQ_EXPR
)
1658 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1662 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1665 /* If loop bound, base and compare bound are all constants, we can
1666 calculate the probability directly. */
1667 if (tree_fits_shwi_p (loop_bound_var
)
1668 && tree_fits_shwi_p (compare_var
)
1669 && tree_fits_shwi_p (compare_base
))
1672 wi::overflow_type overflow
;
1673 bool overall_overflow
= false;
1674 widest_int compare_count
, tem
;
1676 /* (loop_bound - base) / compare_step */
1677 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1678 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1679 overall_overflow
|= overflow
;
1680 widest_int loop_count
= wi::div_trunc (tem
,
1681 wi::to_widest (compare_step_var
),
1683 overall_overflow
|= overflow
;
1685 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1686 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1688 /* (loop_bound - compare_bound) / compare_step */
1689 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1690 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1691 overall_overflow
|= overflow
;
1692 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1694 overall_overflow
|= overflow
;
1698 /* (compare_bound - base) / compare_step */
1699 tem
= wi::sub (wi::to_widest (compare_var
),
1700 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1701 overall_overflow
|= overflow
;
1702 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1704 overall_overflow
|= overflow
;
1706 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1708 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1710 if (wi::neg_p (compare_count
))
1712 if (wi::neg_p (loop_count
))
1714 if (loop_count
== 0)
1716 else if (wi::cmps (compare_count
, loop_count
) == 1)
1717 probability
= REG_BR_PROB_BASE
;
1720 tem
= compare_count
* REG_BR_PROB_BASE
;
1721 tem
= wi::udiv_trunc (tem
, loop_count
);
1722 probability
= tem
.to_uhwi ();
1725 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1726 if (!overall_overflow
)
1727 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1732 if (expr_coherent_p (loop_bound_var
, compare_var
))
1734 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1735 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1736 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1737 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1738 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1739 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1740 else if (loop_bound_code
== NE_EXPR
)
1742 /* If the loop backedge condition is "(i != bound)", we do
1743 the comparison based on the step of IV:
1744 * step < 0 : backedge condition is like (i > bound)
1745 * step > 0 : backedge condition is like (i < bound) */
1746 gcc_assert (loop_bound_step
!= 0);
1747 if (loop_bound_step
> 0
1748 && (compare_code
== LT_EXPR
1749 || compare_code
== LE_EXPR
))
1750 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1751 else if (loop_bound_step
< 0
1752 && (compare_code
== GT_EXPR
1753 || compare_code
== GE_EXPR
))
1754 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1756 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1759 /* The branch is predicted not-taken if loop_bound_code is
1760 opposite with compare_code. */
1761 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1763 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1766 for (i = s; i < h; i++)
1768 The branch should be predicted taken. */
1769 if (loop_bound_step
> 0
1770 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1771 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1772 else if (loop_bound_step
< 0
1773 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1774 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1776 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1780 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1781 exits are resulted from short-circuit conditions that will generate an
1784 if (foo() || global > 10)
1787 This will be translated into:
1792 if foo() goto BB6 else goto BB5
1794 if global > 10 goto BB6 else goto BB7
1798 iftmp = (PHI 0(BB5), 1(BB6))
1799 if iftmp == 1 goto BB8 else goto BB3
1801 outside of the loop...
1803 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1804 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1805 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1806 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1809 predict_extra_loop_exits (edge exit_edge
)
1812 bool check_value_one
;
1813 gimple
*lhs_def_stmt
;
1815 tree cmp_rhs
, cmp_lhs
;
1819 last
= last_stmt (exit_edge
->src
);
1822 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1826 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1827 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1828 if (!TREE_CONSTANT (cmp_rhs
)
1829 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1831 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1834 /* If check_value_one is true, only the phi_args with value '1' will lead
1835 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1837 check_value_one
= (((integer_onep (cmp_rhs
))
1838 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1839 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1841 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1845 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1849 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1853 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1854 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1856 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1858 if ((check_value_one
^ integer_onep (val
)) == 1)
1860 if (EDGE_COUNT (e
->src
->succs
) != 1)
1862 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1866 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1867 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1872 /* Predict edge probabilities by exploiting loop structure. */
1875 predict_loops (void)
1879 hash_set
<struct loop
*> with_recursion(10);
1881 FOR_EACH_BB_FN (bb
, cfun
)
1883 gimple_stmt_iterator gsi
;
1886 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1887 if (is_gimple_call (gsi_stmt (gsi
))
1888 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1889 && recursive_call_p (current_function_decl
, decl
))
1891 loop
= bb
->loop_father
;
1892 while (loop
&& !with_recursion
.add (loop
))
1893 loop
= loop_outer (loop
);
1897 /* Try to predict out blocks in a loop that are not part of a
1899 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1901 basic_block bb
, *bbs
;
1902 unsigned j
, n_exits
= 0;
1904 struct tree_niter_desc niter_desc
;
1906 struct nb_iter_bound
*nb_iter
;
1907 enum tree_code loop_bound_code
= ERROR_MARK
;
1908 tree loop_bound_step
= NULL
;
1909 tree loop_bound_var
= NULL
;
1910 tree loop_iv_base
= NULL
;
1912 bool recursion
= with_recursion
.contains (loop
);
1914 exits
= get_loop_exit_edges (loop
);
1915 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1916 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1925 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1926 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1927 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1928 && max_loop_iterations_int (loop
) >= 0)
1931 "Loop %d iterates at most %i times.\n", loop
->num
,
1932 (int)max_loop_iterations_int (loop
));
1934 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1935 && likely_max_loop_iterations_int (loop
) >= 0)
1937 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1938 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1941 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1944 HOST_WIDE_INT nitercst
;
1945 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1947 enum br_predictor predictor
;
1950 if (unlikely_executed_edge_p (ex
)
1951 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
1953 /* Loop heuristics do not expect exit conditional to be inside
1954 inner loop. We predict from innermost to outermost loop. */
1955 if (predicted_by_loop_heuristics_p (ex
->src
))
1957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1958 fprintf (dump_file
, "Skipping exit %i->%i because "
1959 "it is already predicted.\n",
1960 ex
->src
->index
, ex
->dest
->index
);
1963 predict_extra_loop_exits (ex
);
1965 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1966 niter
= niter_desc
.niter
;
1967 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1968 niter
= loop_niter_by_eval (loop
, ex
);
1969 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1970 && TREE_CODE (niter
) == INTEGER_CST
)
1972 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1973 ex
->src
->index
, ex
->dest
->index
,
1975 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1976 fprintf (dump_file
, " times.\n");
1979 if (TREE_CODE (niter
) == INTEGER_CST
)
1981 if (tree_fits_uhwi_p (niter
)
1983 && compare_tree_int (niter
, max
- 1) == -1)
1984 nitercst
= tree_to_uhwi (niter
) + 1;
1987 predictor
= PRED_LOOP_ITERATIONS
;
1989 /* If we have just one exit and we can derive some information about
1990 the number of iterations of the loop from the statements inside
1991 the loop, use it to predict this exit. */
1992 else if (n_exits
== 1
1993 && estimated_stmt_executions (loop
, &nit
))
1995 if (wi::gtu_p (nit
, max
))
1998 nitercst
= nit
.to_shwi ();
1999 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
2001 /* If we have likely upper bound, trust it for very small iteration
2002 counts. Such loops would otherwise get mispredicted by standard
2003 LOOP_EXIT heuristics. */
2004 else if (n_exits
== 1
2005 && likely_max_stmt_executions (loop
, &nit
)
2007 RDIV (REG_BR_PROB_BASE
,
2011 ? PRED_LOOP_EXIT_WITH_RECURSION
2012 : PRED_LOOP_EXIT
].hitrate
)))
2014 nitercst
= nit
.to_shwi ();
2015 predictor
= PRED_LOOP_ITERATIONS_MAX
;
2019 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2020 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
2021 ex
->src
->index
, ex
->dest
->index
);
2025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2026 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
2027 (int)nitercst
, predictor_info
[predictor
].name
);
2028 /* If the prediction for number of iterations is zero, do not
2029 predict the exit edges. */
2033 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
2034 predict_edge (ex
, predictor
, probability
);
2038 /* Find information about loop bound variables. */
2039 for (nb_iter
= loop
->bounds
; nb_iter
;
2040 nb_iter
= nb_iter
->next
)
2042 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
2044 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
2047 if (!stmt
&& last_stmt (loop
->header
)
2048 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
2049 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2051 is_comparison_with_loop_invariant_p (stmt
, loop
,
2057 bbs
= get_loop_body (loop
);
2059 for (j
= 0; j
< loop
->num_nodes
; j
++)
2066 /* Bypass loop heuristics on continue statement. These
2067 statements construct loops via "non-loop" constructs
2068 in the source language and are better to be handled
2070 if (predicted_by_p (bb
, PRED_CONTINUE
))
2072 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2073 fprintf (dump_file
, "BB %i predicted by continue.\n",
2078 /* If we already used more reliable loop exit predictors, do not
2079 bother with PRED_LOOP_EXIT. */
2080 if (!predicted_by_loop_heuristics_p (bb
))
2082 /* For loop with many exits we don't want to predict all exits
2083 with the pretty large probability, because if all exits are
2084 considered in row, the loop would be predicted to iterate
2085 almost never. The code to divide probability by number of
2086 exits is very rough. It should compute the number of exits
2087 taken in each patch through function (not the overall number
2088 of exits that might be a lot higher for loops with wide switch
2089 statements in them) and compute n-th square root.
2091 We limit the minimal probability by 2% to avoid
2092 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2093 as this was causing regression in perl benchmark containing such
2096 int probability
= ((REG_BR_PROB_BASE
2099 ? PRED_LOOP_EXIT_WITH_RECURSION
2100 : PRED_LOOP_EXIT
].hitrate
)
2102 if (probability
< HITRATE (2))
2103 probability
= HITRATE (2);
2104 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2105 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2106 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2108 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2110 "Predicting exit %i->%i with prob %i.\n",
2111 e
->src
->index
, e
->dest
->index
, probability
);
2113 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2114 : PRED_LOOP_EXIT
, probability
);
2118 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2120 tree_to_shwi (loop_bound_step
));
2123 /* In the following code
2128 guess that cond is unlikely. */
2129 if (loop_outer (loop
)->num
)
2131 basic_block bb
= NULL
;
2132 edge preheader_edge
= loop_preheader_edge (loop
);
2134 if (single_pred_p (preheader_edge
->src
)
2135 && single_succ_p (preheader_edge
->src
))
2136 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2138 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2139 /* Pattern match fortran loop preheader:
2140 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2141 _17 = (logical(kind=4)) _16;
2147 Loop guard branch prediction says nothing about duplicated loop
2148 headers produced by fortran frontend and in this case we want
2149 to predict paths leading to this preheader. */
2152 && gimple_code (stmt
) == GIMPLE_COND
2153 && gimple_cond_code (stmt
) == NE_EXPR
2154 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2155 && integer_zerop (gimple_cond_rhs (stmt
)))
2157 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2158 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2159 && gimple_expr_code (call_stmt
) == NOP_EXPR
2160 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2161 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2162 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2163 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2164 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2165 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2166 == PRED_FORTRAN_LOOP_PREHEADER
)
2167 bb
= preheader_edge
->src
;
2171 if (!dominated_by_p (CDI_DOMINATORS
,
2172 loop_outer (loop
)->latch
, loop
->header
))
2173 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2175 ? PRED_LOOP_GUARD_WITH_RECURSION
2182 if (!dominated_by_p (CDI_DOMINATORS
,
2183 loop_outer (loop
)->latch
, bb
))
2184 predict_paths_leading_to (bb
,
2186 ? PRED_LOOP_GUARD_WITH_RECURSION
2193 /* Free basic blocks from get_loop_body. */
2198 /* Attempt to predict probabilities of BB outgoing edges using local
2201 bb_estimate_probability_locally (basic_block bb
)
2203 rtx_insn
*last_insn
= BB_END (bb
);
2206 if (! can_predict_insn_p (last_insn
))
2208 cond
= get_condition (last_insn
, NULL
, false, false);
2212 /* Try "pointer heuristic."
2213 A comparison ptr == 0 is predicted as false.
2214 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2215 if (COMPARISON_P (cond
)
2216 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2217 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2219 if (GET_CODE (cond
) == EQ
)
2220 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2221 else if (GET_CODE (cond
) == NE
)
2222 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2226 /* Try "opcode heuristic."
2227 EQ tests are usually false and NE tests are usually true. Also,
2228 most quantities are positive, so we can make the appropriate guesses
2229 about signed comparisons against zero. */
2230 switch (GET_CODE (cond
))
2233 /* Unconditional branch. */
2234 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2235 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2240 /* Floating point comparisons appears to behave in a very
2241 unpredictable way because of special role of = tests in
2243 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2245 /* Comparisons with 0 are often used for booleans and there is
2246 nothing useful to predict about them. */
2247 else if (XEXP (cond
, 1) == const0_rtx
2248 || XEXP (cond
, 0) == const0_rtx
)
2251 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2256 /* Floating point comparisons appears to behave in a very
2257 unpredictable way because of special role of = tests in
2259 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2261 /* Comparisons with 0 are often used for booleans and there is
2262 nothing useful to predict about them. */
2263 else if (XEXP (cond
, 1) == const0_rtx
2264 || XEXP (cond
, 0) == const0_rtx
)
2267 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2271 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2275 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2280 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2281 || XEXP (cond
, 1) == constm1_rtx
)
2282 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2287 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2288 || XEXP (cond
, 1) == constm1_rtx
)
2289 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2297 /* Set edge->probability for each successor edge of BB. */
2299 guess_outgoing_edge_probabilities (basic_block bb
)
2301 bb_estimate_probability_locally (bb
);
2302 combine_predictions_for_insn (BB_END (bb
), bb
);
2305 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
,
2306 HOST_WIDE_INT
*probability
);
2308 /* Helper function for expr_expected_value. */
2311 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2312 tree op1
, bitmap visited
, enum br_predictor
*predictor
,
2313 HOST_WIDE_INT
*probability
)
2317 /* Reset returned probability value. */
2319 *predictor
= PRED_UNCONDITIONAL
;
2321 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2323 if (TREE_CONSTANT (op0
))
2326 if (code
== IMAGPART_EXPR
)
2328 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2330 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2331 if (is_gimple_call (def
)
2332 && gimple_call_internal_p (def
)
2333 && (gimple_call_internal_fn (def
)
2334 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2336 /* Assume that any given atomic operation has low contention,
2337 and thus the compare-and-swap operation succeeds. */
2338 *predictor
= PRED_COMPARE_AND_SWAP
;
2339 return build_one_cst (TREE_TYPE (op0
));
2344 if (code
!= SSA_NAME
)
2347 def
= SSA_NAME_DEF_STMT (op0
);
2349 /* If we were already here, break the infinite cycle. */
2350 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2353 if (gimple_code (def
) == GIMPLE_PHI
)
2355 /* All the arguments of the PHI node must have the same constant
2357 int i
, n
= gimple_phi_num_args (def
);
2358 tree val
= NULL
, new_val
;
2360 for (i
= 0; i
< n
; i
++)
2362 tree arg
= PHI_ARG_DEF (def
, i
);
2363 enum br_predictor predictor2
;
2365 /* If this PHI has itself as an argument, we cannot
2366 determine the string length of this argument. However,
2367 if we can find an expected constant value for the other
2368 PHI args then we can still be sure that this is
2369 likely a constant. So be optimistic and just
2370 continue with the next argument. */
2371 if (arg
== PHI_RESULT (def
))
2374 HOST_WIDE_INT probability2
;
2375 new_val
= expr_expected_value (arg
, visited
, &predictor2
,
2378 /* It is difficult to combine value predictors. Simply assume
2379 that later predictor is weaker and take its prediction. */
2380 if (*predictor
< predictor2
)
2382 *predictor
= predictor2
;
2383 *probability
= probability2
;
2389 else if (!operand_equal_p (val
, new_val
, false))
2394 if (is_gimple_assign (def
))
2396 if (gimple_assign_lhs (def
) != op0
)
2399 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2400 gimple_assign_rhs1 (def
),
2401 gimple_assign_rhs_code (def
),
2402 gimple_assign_rhs2 (def
),
2403 visited
, predictor
, probability
);
2406 if (is_gimple_call (def
))
2408 tree decl
= gimple_call_fndecl (def
);
2411 if (gimple_call_internal_p (def
)
2412 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2414 gcc_assert (gimple_call_num_args (def
) == 3);
2415 tree val
= gimple_call_arg (def
, 0);
2416 if (TREE_CONSTANT (val
))
2418 tree val2
= gimple_call_arg (def
, 2);
2419 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2420 && tree_fits_uhwi_p (val2
)
2421 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2422 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2423 if (*predictor
== PRED_BUILTIN_EXPECT
)
2425 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
));
2426 return gimple_call_arg (def
, 1);
2431 if (DECL_IS_MALLOC (decl
) || DECL_IS_OPERATOR_NEW (decl
))
2434 *predictor
= PRED_MALLOC_NONNULL
;
2435 return boolean_true_node
;
2438 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2439 switch (DECL_FUNCTION_CODE (decl
))
2441 case BUILT_IN_EXPECT
:
2444 if (gimple_call_num_args (def
) != 2)
2446 val
= gimple_call_arg (def
, 0);
2447 if (TREE_CONSTANT (val
))
2449 *predictor
= PRED_BUILTIN_EXPECT
;
2451 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
));
2452 return gimple_call_arg (def
, 1);
2454 case BUILT_IN_EXPECT_WITH_PROBABILITY
:
2457 if (gimple_call_num_args (def
) != 3)
2459 val
= gimple_call_arg (def
, 0);
2460 if (TREE_CONSTANT (val
))
2462 /* Compute final probability as:
2463 probability * REG_BR_PROB_BASE. */
2464 tree prob
= gimple_call_arg (def
, 2);
2465 tree t
= TREE_TYPE (prob
);
2466 tree base
= build_int_cst (integer_type_node
,
2468 base
= build_real_from_int_cst (t
, base
);
2469 tree r
= fold_build2_initializer_loc (UNKNOWN_LOCATION
,
2470 MULT_EXPR
, t
, prob
, base
);
2471 if (TREE_CODE (r
) != REAL_CST
)
2473 error_at (gimple_location (def
),
2474 "probability %qE must be "
2475 "constant floating-point expression", prob
);
2479 = real_to_integer (TREE_REAL_CST_PTR (r
));
2480 if (probi
>= 0 && probi
<= REG_BR_PROB_BASE
)
2482 *predictor
= PRED_BUILTIN_EXPECT_WITH_PROBABILITY
;
2483 *probability
= probi
;
2486 error_at (gimple_location (def
),
2487 "probability %qE is outside "
2488 "the range [0.0, 1.0]", prob
);
2490 return gimple_call_arg (def
, 1);
2493 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2494 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2495 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2496 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2497 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2498 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2499 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2500 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2501 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2502 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2503 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2504 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2505 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2506 /* Assume that any given atomic operation has low contention,
2507 and thus the compare-and-swap operation succeeds. */
2508 *predictor
= PRED_COMPARE_AND_SWAP
;
2509 return boolean_true_node
;
2510 case BUILT_IN_REALLOC
:
2512 *predictor
= PRED_MALLOC_NONNULL
;
2513 return boolean_true_node
;
2522 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2525 enum br_predictor predictor2
;
2526 HOST_WIDE_INT probability2
;
2527 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2530 op1
= expr_expected_value (op1
, visited
, &predictor2
, &probability2
);
2533 res
= fold_build2 (code
, type
, op0
, op1
);
2534 if (TREE_CODE (res
) == INTEGER_CST
2535 && TREE_CODE (op0
) == INTEGER_CST
2536 && TREE_CODE (op1
) == INTEGER_CST
)
2538 /* Combine binary predictions. */
2539 if (*probability
!= -1 || probability2
!= -1)
2541 HOST_WIDE_INT p1
= get_predictor_value (*predictor
, *probability
);
2542 HOST_WIDE_INT p2
= get_predictor_value (predictor2
, probability2
);
2543 *probability
= RDIV (p1
* p2
, REG_BR_PROB_BASE
);
2546 if (*predictor
< predictor2
)
2547 *predictor
= predictor2
;
2553 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2556 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2559 res
= fold_build1 (code
, type
, op0
);
2560 if (TREE_CONSTANT (res
))
2567 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2568 The function is used by builtin_expect branch predictor so the evidence
2569 must come from this construct and additional possible constant folding.
2571 We may want to implement more involved value guess (such as value range
2572 propagation based prediction), but such tricks shall go to new
2576 expr_expected_value (tree expr
, bitmap visited
,
2577 enum br_predictor
*predictor
,
2578 HOST_WIDE_INT
*probability
)
2580 enum tree_code code
;
2583 if (TREE_CONSTANT (expr
))
2585 *predictor
= PRED_UNCONDITIONAL
;
2590 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2591 return expr_expected_value_1 (TREE_TYPE (expr
),
2592 op0
, code
, op1
, visited
, predictor
,
2597 /* Return probability of a PREDICTOR. If the predictor has variable
2598 probability return passed PROBABILITY. */
2600 static HOST_WIDE_INT
2601 get_predictor_value (br_predictor predictor
, HOST_WIDE_INT probability
)
2605 case PRED_BUILTIN_EXPECT
:
2606 case PRED_BUILTIN_EXPECT_WITH_PROBABILITY
:
2607 gcc_assert (probability
!= -1);
2610 gcc_assert (probability
== -1);
2611 return predictor_info
[(int) predictor
].hitrate
;
2615 /* Predict using opcode of the last statement in basic block. */
2617 tree_predict_by_opcode (basic_block bb
)
2619 gimple
*stmt
= last_stmt (bb
);
2626 enum br_predictor predictor
;
2627 HOST_WIDE_INT probability
;
2632 if (gswitch
*sw
= dyn_cast
<gswitch
*> (stmt
))
2634 tree index
= gimple_switch_index (sw
);
2635 tree val
= expr_expected_value (index
, auto_bitmap (),
2636 &predictor
, &probability
);
2637 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2639 edge e
= find_taken_edge_switch_expr (sw
, val
);
2640 if (predictor
== PRED_BUILTIN_EXPECT
)
2642 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2643 gcc_assert (percent
>= 0 && percent
<= 100);
2644 predict_edge (e
, PRED_BUILTIN_EXPECT
,
2648 predict_edge_def (e
, predictor
, TAKEN
);
2652 if (gimple_code (stmt
) != GIMPLE_COND
)
2654 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2655 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2657 op0
= gimple_cond_lhs (stmt
);
2658 op1
= gimple_cond_rhs (stmt
);
2659 cmp
= gimple_cond_code (stmt
);
2660 type
= TREE_TYPE (op0
);
2661 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2662 &predictor
, &probability
);
2663 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2665 HOST_WIDE_INT prob
= get_predictor_value (predictor
, probability
);
2666 if (integer_zerop (val
))
2667 prob
= REG_BR_PROB_BASE
- prob
;
2668 predict_edge (then_edge
, predictor
, prob
);
2670 /* Try "pointer heuristic."
2671 A comparison ptr == 0 is predicted as false.
2672 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2673 if (POINTER_TYPE_P (type
))
2676 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2677 else if (cmp
== NE_EXPR
)
2678 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2682 /* Try "opcode heuristic."
2683 EQ tests are usually false and NE tests are usually true. Also,
2684 most quantities are positive, so we can make the appropriate guesses
2685 about signed comparisons against zero. */
2690 /* Floating point comparisons appears to behave in a very
2691 unpredictable way because of special role of = tests in
2693 if (FLOAT_TYPE_P (type
))
2695 /* Comparisons with 0 are often used for booleans and there is
2696 nothing useful to predict about them. */
2697 else if (integer_zerop (op0
) || integer_zerop (op1
))
2700 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2705 /* Floating point comparisons appears to behave in a very
2706 unpredictable way because of special role of = tests in
2708 if (FLOAT_TYPE_P (type
))
2710 /* Comparisons with 0 are often used for booleans and there is
2711 nothing useful to predict about them. */
2712 else if (integer_zerop (op0
)
2713 || integer_zerop (op1
))
2716 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2720 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2723 case UNORDERED_EXPR
:
2724 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2729 if (integer_zerop (op1
)
2730 || integer_onep (op1
)
2731 || integer_all_onesp (op1
)
2734 || real_minus_onep (op1
))
2735 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, 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
, TAKEN
);
2754 /* Returns TRUE if the STMT is exit(0) like statement. */
2757 is_exit_with_zero_arg (const gimple
*stmt
)
2759 /* This is not exit, _exit or _Exit. */
2760 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2761 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2762 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2765 /* Argument is an interger zero. */
2766 return integer_zerop (gimple_call_arg (stmt
, 0));
2769 /* Try to guess whether the value of return means error code. */
2771 static enum br_predictor
2772 return_prediction (tree val
, enum prediction
*prediction
)
2776 return PRED_NO_PREDICTION
;
2777 /* Different heuristics for pointers and scalars. */
2778 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2780 /* NULL is usually not returned. */
2781 if (integer_zerop (val
))
2783 *prediction
= NOT_TAKEN
;
2784 return PRED_NULL_RETURN
;
2787 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2789 /* Negative return values are often used to indicate
2791 if (TREE_CODE (val
) == INTEGER_CST
2792 && tree_int_cst_sgn (val
) < 0)
2794 *prediction
= NOT_TAKEN
;
2795 return PRED_NEGATIVE_RETURN
;
2797 /* Constant return values seems to be commonly taken.
2798 Zero/one often represent booleans so exclude them from the
2800 if (TREE_CONSTANT (val
)
2801 && (!integer_zerop (val
) && !integer_onep (val
)))
2803 *prediction
= NOT_TAKEN
;
2804 return PRED_CONST_RETURN
;
2807 return PRED_NO_PREDICTION
;
2810 /* Return zero if phi result could have values other than -1, 0 or 1,
2811 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2812 values are used or likely. */
2815 zero_one_minusone (gphi
*phi
, int limit
)
2817 int phi_num_args
= gimple_phi_num_args (phi
);
2819 for (int i
= 0; i
< phi_num_args
; i
++)
2821 tree t
= PHI_ARG_DEF (phi
, i
);
2822 if (TREE_CODE (t
) != INTEGER_CST
)
2824 wide_int w
= wi::to_wide (t
);
2834 for (int i
= 0; i
< phi_num_args
; i
++)
2836 tree t
= PHI_ARG_DEF (phi
, i
);
2837 if (TREE_CODE (t
) == INTEGER_CST
)
2839 if (TREE_CODE (t
) != SSA_NAME
)
2841 gimple
*g
= SSA_NAME_DEF_STMT (t
);
2842 if (gimple_code (g
) == GIMPLE_PHI
&& limit
> 0)
2843 if (int r
= zero_one_minusone (as_a
<gphi
*> (g
), limit
- 1))
2848 if (!is_gimple_assign (g
))
2850 if (gimple_assign_cast_p (g
))
2852 tree rhs1
= gimple_assign_rhs1 (g
);
2853 if (TREE_CODE (rhs1
) != SSA_NAME
2854 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
2855 || TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2856 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2861 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g
)) != tcc_comparison
)
2868 /* Find the basic block with return expression and look up for possible
2869 return value trying to apply RETURN_PREDICTION heuristics. */
2871 apply_return_prediction (void)
2873 greturn
*return_stmt
= NULL
;
2877 int phi_num_args
, i
;
2878 enum br_predictor pred
;
2879 enum prediction direction
;
2882 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2884 gimple
*last
= last_stmt (e
->src
);
2886 && gimple_code (last
) == GIMPLE_RETURN
)
2888 return_stmt
= as_a
<greturn
*> (last
);
2894 return_val
= gimple_return_retval (return_stmt
);
2897 if (TREE_CODE (return_val
) != SSA_NAME
2898 || !SSA_NAME_DEF_STMT (return_val
)
2899 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2901 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2902 phi_num_args
= gimple_phi_num_args (phi
);
2903 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2905 /* Avoid the case where the function returns -1, 0 and 1 values and
2906 nothing else. Those could be qsort etc. comparison functions
2907 where the negative return isn't less probable than positive.
2908 For this require that the function returns at least -1 or 1
2909 or -1 and a boolean value or comparison result, so that functions
2910 returning just -1 and 0 are treated as if -1 represents error value. */
2911 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val
))
2912 && !TYPE_UNSIGNED (TREE_TYPE (return_val
))
2913 && TYPE_PRECISION (TREE_TYPE (return_val
)) > 1)
2914 if (int r
= zero_one_minusone (phi
, 3))
2915 if ((r
& (1 | 4)) == (1 | 4))
2918 /* Avoid the degenerate case where all return values form the function
2919 belongs to same category (ie they are all positive constants)
2920 so we can hardly say something about them. */
2921 for (i
= 1; i
< phi_num_args
; i
++)
2922 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2924 if (i
!= phi_num_args
)
2925 for (i
= 0; i
< phi_num_args
; i
++)
2927 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2928 if (pred
!= PRED_NO_PREDICTION
)
2929 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2934 /* Look for basic block that contains unlikely to happen events
2935 (such as noreturn calls) and mark all paths leading to execution
2936 of this basic blocks as unlikely. */
2939 tree_bb_level_predictions (void)
2942 bool has_return_edges
= false;
2946 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2947 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2949 has_return_edges
= true;
2953 apply_return_prediction ();
2955 FOR_EACH_BB_FN (bb
, cfun
)
2957 gimple_stmt_iterator gsi
;
2959 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2961 gimple
*stmt
= gsi_stmt (gsi
);
2964 if (is_gimple_call (stmt
))
2966 if (gimple_call_noreturn_p (stmt
)
2968 && !is_exit_with_zero_arg (stmt
))
2969 predict_paths_leading_to (bb
, PRED_NORETURN
,
2971 decl
= gimple_call_fndecl (stmt
);
2973 && lookup_attribute ("cold",
2974 DECL_ATTRIBUTES (decl
)))
2975 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2977 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2978 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2981 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2983 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2984 gimple_predict_outcome (stmt
));
2985 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2986 hints to callers. */
2992 /* Callback for hash_map::traverse, asserts that the pointer map is
2996 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2999 gcc_assert (!value
);
3003 /* Predict branch probabilities and estimate profile for basic block BB.
3004 When LOCAL_ONLY is set do not use any global properties of CFG. */
3007 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
3012 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3014 /* Look for block we are guarding (ie we dominate it,
3015 but it doesn't postdominate us). */
3016 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
3018 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
3019 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
3021 gimple_stmt_iterator bi
;
3023 /* The call heuristic claims that a guarded function call
3024 is improbable. This is because such calls are often used
3025 to signal exceptional situations such as printing error
3027 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
3030 gimple
*stmt
= gsi_stmt (bi
);
3031 if (is_gimple_call (stmt
)
3032 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
3033 /* Constant and pure calls are hardly used to signalize
3034 something exceptional. */
3035 && gimple_has_side_effects (stmt
))
3037 if (gimple_call_fndecl (stmt
))
3038 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
3039 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
3040 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
3042 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
3048 tree_predict_by_opcode (bb
);
3051 /* Predict branch probabilities and estimate profile of the tree CFG.
3052 This function can be called from the loop optimizers to recompute
3053 the profile information.
3054 If DRY_RUN is set, do not modify CFG and only produce dump files. */
3057 tree_estimate_probability (bool dry_run
)
3061 add_noreturn_fake_exit_edges ();
3062 connect_infinite_loops_to_exit ();
3063 /* We use loop_niter_by_eval, which requires that the loops have
3065 create_preheaders (CP_SIMPLE_PREHEADERS
);
3066 calculate_dominance_info (CDI_POST_DOMINATORS
);
3067 /* Decide which edges are known to be unlikely. This improves later
3068 branch prediction. */
3069 determine_unlikely_bbs ();
3071 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3072 tree_bb_level_predictions ();
3073 record_loop_exits ();
3075 if (number_of_loops (cfun
) > 1)
3078 FOR_EACH_BB_FN (bb
, cfun
)
3079 tree_estimate_probability_bb (bb
, false);
3081 FOR_EACH_BB_FN (bb
, cfun
)
3082 combine_predictions_for_bb (bb
, dry_run
);
3085 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3087 delete bb_predictions
;
3088 bb_predictions
= NULL
;
3091 estimate_bb_frequencies (false);
3092 free_dominance_info (CDI_POST_DOMINATORS
);
3093 remove_fake_exit_edges ();
3096 /* Set edge->probability for each successor edge of BB. */
3098 tree_guess_outgoing_edge_probabilities (basic_block bb
)
3100 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3101 tree_estimate_probability_bb (bb
, true);
3102 combine_predictions_for_bb (bb
, false);
3104 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3105 delete bb_predictions
;
3106 bb_predictions
= NULL
;
3109 /* Predict edges to successors of CUR whose sources are not postdominated by
3110 BB by PRED and recurse to all postdominators. */
3113 predict_paths_for_bb (basic_block cur
, basic_block bb
,
3114 enum br_predictor pred
,
3115 enum prediction taken
,
3116 bitmap visited
, struct loop
*in_loop
= NULL
)
3122 /* If we exited the loop or CUR is unconditional in the loop, there is
3125 && (!flow_bb_inside_loop_p (in_loop
, cur
)
3126 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
3129 /* We are looking for all edges forming edge cut induced by
3130 set of all blocks postdominated by BB. */
3131 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
3132 if (e
->src
->index
>= NUM_FIXED_BLOCKS
3133 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
3139 /* Ignore fake edges and eh, we predict them as not taken anyway. */
3140 if (unlikely_executed_edge_p (e
))
3142 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
3144 /* See if there is an edge from e->src that is not abnormal
3145 and does not lead to BB and does not exit the loop. */
3146 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
3148 && !unlikely_executed_edge_p (e2
)
3149 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
3150 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
3156 /* If there is non-abnormal path leaving e->src, predict edge
3157 using predictor. Otherwise we need to look for paths
3160 The second may lead to infinite loop in the case we are predicitng
3161 regions that are only reachable by abnormal edges. We simply
3162 prevent visiting given BB twice. */
3165 if (!edge_predicted_by_p (e
, pred
, taken
))
3166 predict_edge_def (e
, pred
, taken
);
3168 else if (bitmap_set_bit (visited
, e
->src
->index
))
3169 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
3171 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
3173 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
3174 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
3177 /* Sets branch probabilities according to PREDiction and
3181 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
3182 enum prediction taken
, struct loop
*in_loop
)
3184 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3187 /* Like predict_paths_leading_to but take edge instead of basic block. */
3190 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
3191 enum prediction taken
, struct loop
*in_loop
)
3193 bool has_nonloop_edge
= false;
3197 basic_block bb
= e
->src
;
3198 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
3199 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
3200 && !unlikely_executed_edge_p (e
)
3201 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
3203 has_nonloop_edge
= true;
3206 if (!has_nonloop_edge
)
3208 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3211 predict_edge_def (e
, pred
, taken
);
3214 /* This is used to carry information about basic blocks. It is
3215 attached to the AUX field of the standard CFG block. */
3219 /* Estimated frequency of execution of basic_block. */
3222 /* To keep queue of basic blocks to process. */
3225 /* Number of predecessors we need to visit first. */
3229 /* Similar information for edges. */
3230 struct edge_prob_info
3232 /* In case edge is a loopback edge, the probability edge will be reached
3233 in case header is. Estimated number of iterations of the loop can be
3234 then computed as 1 / (1 - back_edge_prob). */
3235 sreal back_edge_prob
;
3236 /* True if the edge is a loopback edge in the natural loop. */
3237 unsigned int back_edge
:1;
3240 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3242 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3244 /* Helper function for estimate_bb_frequencies.
3245 Propagate the frequencies in blocks marked in
3246 TOVISIT, starting in HEAD. */
3249 propagate_freq (basic_block head
, bitmap tovisit
)
3258 /* For each basic block we need to visit count number of his predecessors
3259 we need to visit first. */
3260 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
3265 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3267 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3269 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3271 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3273 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3275 "Irreducible region hit, ignoring edge to %i->%i\n",
3276 e
->src
->index
, bb
->index
);
3278 BLOCK_INFO (bb
)->npredecessors
= count
;
3279 /* When function never returns, we will never process exit block. */
3280 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3281 bb
->count
= profile_count::zero ();
3284 BLOCK_INFO (head
)->frequency
= 1;
3286 for (bb
= head
; bb
; bb
= nextbb
)
3289 sreal cyclic_probability
= 0;
3290 sreal frequency
= 0;
3292 nextbb
= BLOCK_INFO (bb
)->next
;
3293 BLOCK_INFO (bb
)->next
= NULL
;
3295 /* Compute frequency of basic block. */
3299 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3300 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3301 || (e
->flags
& EDGE_DFS_BACK
));
3303 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3304 if (EDGE_INFO (e
)->back_edge
)
3306 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3308 else if (!(e
->flags
& EDGE_DFS_BACK
))
3310 /* frequency += (e->probability
3311 * BLOCK_INFO (e->src)->frequency /
3312 REG_BR_PROB_BASE); */
3314 /* FIXME: Graphite is producing edges with no profile. Once
3315 this is fixed, drop this. */
3316 sreal tmp
= e
->probability
.initialized_p () ?
3317 e
->probability
.to_reg_br_prob_base () : 0;
3318 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
3319 tmp
*= real_inv_br_prob_base
;
3323 if (cyclic_probability
== 0)
3325 BLOCK_INFO (bb
)->frequency
= frequency
;
3329 if (cyclic_probability
> real_almost_one
)
3330 cyclic_probability
= real_almost_one
;
3332 /* BLOCK_INFO (bb)->frequency = frequency
3333 / (1 - cyclic_probability) */
3335 cyclic_probability
= sreal (1) - cyclic_probability
;
3336 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
3340 bitmap_clear_bit (tovisit
, bb
->index
);
3342 e
= find_edge (bb
, head
);
3345 /* EDGE_INFO (e)->back_edge_prob
3346 = ((e->probability * BLOCK_INFO (bb)->frequency)
3347 / REG_BR_PROB_BASE); */
3349 /* FIXME: Graphite is producing edges with no profile. Once
3350 this is fixed, drop this. */
3351 sreal tmp
= e
->probability
.initialized_p () ?
3352 e
->probability
.to_reg_br_prob_base () : 0;
3353 tmp
*= BLOCK_INFO (bb
)->frequency
;
3354 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
3357 /* Propagate to successor blocks. */
3358 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3359 if (!(e
->flags
& EDGE_DFS_BACK
)
3360 && BLOCK_INFO (e
->dest
)->npredecessors
)
3362 BLOCK_INFO (e
->dest
)->npredecessors
--;
3363 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3368 BLOCK_INFO (last
)->next
= e
->dest
;
3376 /* Estimate frequencies in loops at same nest level. */
3379 estimate_loops_at_level (struct loop
*first_loop
)
3383 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3388 auto_bitmap tovisit
;
3390 estimate_loops_at_level (loop
->inner
);
3392 /* Find current loop back edge and mark it. */
3393 e
= loop_latch_edge (loop
);
3394 EDGE_INFO (e
)->back_edge
= 1;
3396 bbs
= get_loop_body (loop
);
3397 for (i
= 0; i
< loop
->num_nodes
; i
++)
3398 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3400 propagate_freq (loop
->header
, tovisit
);
3404 /* Propagates frequencies through structure of loops. */
3407 estimate_loops (void)
3409 auto_bitmap tovisit
;
3412 /* Start by estimating the frequencies in the loops. */
3413 if (number_of_loops (cfun
) > 1)
3414 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3416 /* Now propagate the frequencies through all the blocks. */
3417 FOR_ALL_BB_FN (bb
, cfun
)
3419 bitmap_set_bit (tovisit
, bb
->index
);
3421 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3424 /* Drop the profile for NODE to guessed, and update its frequency based on
3425 whether it is expected to be hot given the CALL_COUNT. */
3428 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3430 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3431 /* In the case where this was called by another function with a
3432 dropped profile, call_count will be 0. Since there are no
3433 non-zero call counts to this function, we don't know for sure
3434 whether it is hot, and therefore it will be marked normal below. */
3435 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3439 "Dropping 0 profile for %s. %s based on calls.\n",
3441 hot
? "Function is hot" : "Function is normal");
3442 /* We only expect to miss profiles for functions that are reached
3443 via non-zero call edges in cases where the function may have
3444 been linked from another module or library (COMDATs and extern
3445 templates). See the comments below for handle_missing_profiles.
3446 Also, only warn in cases where the missing counts exceed the
3447 number of training runs. In certain cases with an execv followed
3448 by a no-return call the profile for the no-return call is not
3449 dumped and there can be a mismatch. */
3450 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3451 && call_count
> profile_info
->runs
)
3453 if (flag_profile_correction
)
3457 "Missing counts for called function %s\n",
3458 node
->dump_name ());
3461 warning (0, "Missing counts for called function %s",
3462 node
->dump_name ());
3466 if (opt_for_fn (node
->decl
, flag_guess_branch_prob
))
3469 = !ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
.nonzero_p ();
3470 FOR_ALL_BB_FN (bb
, fn
)
3471 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3472 bb
->count
= bb
->count
.guessed_local ();
3473 fn
->cfg
->count_max
= fn
->cfg
->count_max
.guessed_local ();
3477 FOR_ALL_BB_FN (bb
, fn
)
3478 bb
->count
= profile_count::uninitialized ();
3479 fn
->cfg
->count_max
= profile_count::uninitialized ();
3482 struct cgraph_edge
*e
;
3483 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3484 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3485 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3486 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3487 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
;
3489 profile_status_for_fn (fn
)
3490 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3492 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3495 /* In the case of COMDAT routines, multiple object files will contain the same
3496 function and the linker will select one for the binary. In that case
3497 all the other copies from the profile instrument binary will be missing
3498 profile counts. Look for cases where this happened, due to non-zero
3499 call counts going to 0-count functions, and drop the profile to guessed
3500 so that we can use the estimated probabilities and avoid optimizing only
3503 The other case where the profile may be missing is when the routine
3504 is not going to be emitted to the object file, e.g. for "extern template"
3505 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3506 all other cases of non-zero calls to 0-count functions. */
3509 handle_missing_profiles (void)
3511 struct cgraph_node
*node
;
3512 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3513 auto_vec
<struct cgraph_node
*, 64> worklist
;
3515 /* See if 0 count function has non-0 count callers. In this case we
3516 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3517 FOR_EACH_DEFINED_FUNCTION (node
)
3519 struct cgraph_edge
*e
;
3520 profile_count call_count
= profile_count::zero ();
3521 gcov_type max_tp_first_run
= 0;
3522 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3524 if (node
->count
.ipa ().nonzero_p ())
3526 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3527 if (e
->count
.ipa ().initialized_p () && e
->count
.ipa () > 0)
3529 call_count
= call_count
+ e
->count
.ipa ();
3531 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3532 max_tp_first_run
= e
->caller
->tp_first_run
;
3535 /* If time profile is missing, let assign the maximum that comes from
3536 caller functions. */
3537 if (!node
->tp_first_run
&& max_tp_first_run
)
3538 node
->tp_first_run
= max_tp_first_run
+ 1;
3542 && (call_count
.apply_scale (unlikely_count_fraction
, 1)
3543 >= profile_info
->runs
))
3545 drop_profile (node
, call_count
);
3546 worklist
.safe_push (node
);
3550 /* Propagate the profile dropping to other 0-count COMDATs that are
3551 potentially called by COMDATs we already dropped the profile on. */
3552 while (worklist
.length () > 0)
3554 struct cgraph_edge
*e
;
3556 node
= worklist
.pop ();
3557 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3559 struct cgraph_node
*callee
= e
->callee
;
3560 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3562 if (!(e
->count
.ipa () == profile_count::zero ())
3563 && callee
->count
.ipa ().nonzero_p ())
3565 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3567 && profile_status_for_fn (fn
) == PROFILE_READ
)
3569 drop_profile (node
, profile_count::zero ());
3570 worklist
.safe_push (callee
);
3576 /* Convert counts measured by profile driven feedback to frequencies.
3577 Return nonzero iff there was any nonzero execution count. */
3580 update_max_bb_count (void)
3582 profile_count true_count_max
= profile_count::uninitialized ();
3585 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3586 true_count_max
= true_count_max
.max (bb
->count
);
3588 cfun
->cfg
->count_max
= true_count_max
;
3590 return true_count_max
.ipa ().nonzero_p ();
3593 /* Return true if function is likely to be expensive, so there is no point to
3594 optimize performance of prologue, epilogue or do inlining at the expense
3595 of code size growth. THRESHOLD is the limit of number of instructions
3596 function can execute at average to be still considered not expensive. */
3599 expensive_function_p (int threshold
)
3603 /* If profile was scaled in a way entry block has count 0, then the function
3604 is deifnitly taking a lot of time. */
3605 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3608 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN
3609 (cfun
)->count
.apply_scale (threshold
, 1);
3610 profile_count sum
= profile_count::zero ();
3611 FOR_EACH_BB_FN (bb
, cfun
)
3615 if (!bb
->count
.initialized_p ())
3618 fprintf (dump_file
, "Function is considered expensive because"
3619 " count of bb %i is not initialized\n", bb
->index
);
3623 FOR_BB_INSNS (bb
, insn
)
3624 if (active_insn_p (insn
))
3635 /* All basic blocks that are reachable only from unlikely basic blocks are
3639 propagate_unlikely_bbs_forward (void)
3641 auto_vec
<basic_block
, 64> worklist
;
3646 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3648 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3649 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3651 while (worklist
.length () > 0)
3653 bb
= worklist
.pop ();
3654 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3655 if (!(e
->count () == profile_count::zero ())
3656 && !(e
->dest
->count
== profile_count::zero ())
3659 e
->dest
->aux
= (void *)(size_t) 1;
3660 worklist
.safe_push (e
->dest
);
3665 FOR_ALL_BB_FN (bb
, cfun
)
3669 if (!(bb
->count
== profile_count::zero ())
3670 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3672 "Basic block %i is marked unlikely by forward prop\n",
3674 bb
->count
= profile_count::zero ();
3681 /* Determine basic blocks/edges that are known to be unlikely executed and set
3682 their counters to zero.
3683 This is done with first identifying obviously unlikely BBs/edges and then
3684 propagating in both directions. */
3687 determine_unlikely_bbs ()
3690 auto_vec
<basic_block
, 64> worklist
;
3694 FOR_EACH_BB_FN (bb
, cfun
)
3696 if (!(bb
->count
== profile_count::zero ())
3697 && unlikely_executed_bb_p (bb
))
3699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3700 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3702 bb
->count
= profile_count::zero ();
3705 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3706 if (!(e
->probability
== profile_probability::never ())
3707 && unlikely_executed_edge_p (e
))
3709 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3710 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3711 bb
->index
, e
->dest
->index
);
3712 e
->probability
= profile_probability::never ();
3715 gcc_checking_assert (!bb
->aux
);
3717 propagate_unlikely_bbs_forward ();
3719 auto_vec
<int, 64> nsuccs
;
3720 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
3721 FOR_ALL_BB_FN (bb
, cfun
)
3722 if (!(bb
->count
== profile_count::zero ())
3723 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3725 nsuccs
[bb
->index
] = 0;
3726 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3727 if (!(e
->probability
== profile_probability::never ())
3728 && !(e
->dest
->count
== profile_count::zero ()))
3729 nsuccs
[bb
->index
]++;
3730 if (!nsuccs
[bb
->index
])
3731 worklist
.safe_push (bb
);
3733 while (worklist
.length () > 0)
3735 bb
= worklist
.pop ();
3736 if (bb
->count
== profile_count::zero ())
3738 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3741 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3742 !gsi_end_p (gsi
); gsi_next (&gsi
))
3743 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3744 /* stmt_can_terminate_bb_p special cases noreturns because it
3745 assumes that fake edges are created. We want to know that
3746 noreturn alone does not imply BB to be unlikely. */
3747 || (is_gimple_call (gsi_stmt (gsi
))
3748 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3756 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3758 "Basic block %i is marked unlikely by backward prop\n",
3760 bb
->count
= profile_count::zero ();
3761 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3762 if (!(e
->probability
== profile_probability::never ()))
3764 if (!(e
->src
->count
== profile_count::zero ()))
3766 gcc_checking_assert (nsuccs
[e
->src
->index
] > 0);
3767 nsuccs
[e
->src
->index
]--;
3768 if (!nsuccs
[e
->src
->index
])
3769 worklist
.safe_push (e
->src
);
3773 /* Finally all edges from non-0 regions to 0 are unlikely. */
3774 FOR_ALL_BB_FN (bb
, cfun
)
3776 if (!(bb
->count
== profile_count::zero ()))
3777 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3778 if (!(e
->probability
== profile_probability::never ())
3779 && e
->dest
->count
== profile_count::zero ())
3781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3782 fprintf (dump_file
, "Edge %i->%i is unlikely because "
3783 "it enters unlikely block\n",
3784 bb
->index
, e
->dest
->index
);
3785 e
->probability
= profile_probability::never ();
3790 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3791 if (e
->probability
== profile_probability::never ())
3801 && !(other
->probability
== profile_probability::always ()))
3803 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3804 fprintf (dump_file
, "Edge %i->%i is locally likely\n",
3805 bb
->index
, other
->dest
->index
);
3806 other
->probability
= profile_probability::always ();
3809 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3810 cgraph_node::get (current_function_decl
)->count
= profile_count::zero ();
3813 /* Estimate and propagate basic block frequencies using the given branch
3814 probabilities. If FORCE is true, the frequencies are used to estimate
3815 the counts even when there are already non-zero profile counts. */
3818 estimate_bb_frequencies (bool force
)
3823 determine_unlikely_bbs ();
3825 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3826 || !update_max_bb_count ())
3828 static int real_values_initialized
= 0;
3830 if (!real_values_initialized
)
3832 real_values_initialized
= 1;
3833 real_br_prob_base
= REG_BR_PROB_BASE
;
3834 /* Scaling frequencies up to maximal profile count may result in
3835 frequent overflows especially when inlining loops.
3836 Small scalling results in unnecesary precision loss. Stay in
3837 the half of the (exponential) range. */
3838 real_bb_freq_max
= (uint64_t)1 << (profile_count::n_bits
/ 2);
3839 real_one_half
= sreal (1, -1);
3840 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3841 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3844 mark_dfs_back_edges ();
3846 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3847 profile_probability::always ();
3849 /* Set up block info for each basic block. */
3850 alloc_aux_for_blocks (sizeof (block_info
));
3851 alloc_aux_for_edges (sizeof (edge_prob_info
));
3852 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3857 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3859 /* FIXME: Graphite is producing edges with no profile. Once
3860 this is fixed, drop this. */
3861 if (e
->probability
.initialized_p ())
3862 EDGE_INFO (e
)->back_edge_prob
3863 = e
->probability
.to_reg_br_prob_base ();
3865 EDGE_INFO (e
)->back_edge_prob
= REG_BR_PROB_BASE
/ 2;
3866 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3870 /* First compute frequencies locally for each loop from innermost
3871 to outermost to examine frequencies for back edges. */
3875 FOR_EACH_BB_FN (bb
, cfun
)
3876 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3877 freq_max
= BLOCK_INFO (bb
)->frequency
;
3879 freq_max
= real_bb_freq_max
/ freq_max
;
3882 profile_count ipa_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ();
3883 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3884 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3886 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3887 profile_count count
= profile_count::from_gcov_type (tmp
.to_int ());
3889 /* If we have profile feedback in which this function was never
3890 executed, then preserve this info. */
3891 if (!(bb
->count
== profile_count::zero ()))
3892 bb
->count
= count
.guessed_local ().combine_with_ipa_count (ipa_count
);
3893 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3896 free_aux_for_blocks ();
3897 free_aux_for_edges ();
3899 compute_function_frequency ();
3902 /* Decide whether function is hot, cold or unlikely executed. */
3904 compute_function_frequency (void)
3907 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3909 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3910 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3911 node
->only_called_at_startup
= true;
3912 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3913 node
->only_called_at_exit
= true;
3915 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3917 int flags
= flags_from_decl_or_type (current_function_decl
);
3918 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ()
3919 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3920 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3923 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3924 warn_function_cold (current_function_decl
);
3926 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3928 node
->frequency
= NODE_FREQUENCY_HOT
;
3929 else if (flags
& ECF_NORETURN
)
3930 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3931 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3932 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3933 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3934 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3935 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3939 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3940 warn_function_cold (current_function_decl
);
3941 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3943 FOR_EACH_BB_FN (bb
, cfun
)
3945 if (maybe_hot_bb_p (cfun
, bb
))
3947 node
->frequency
= NODE_FREQUENCY_HOT
;
3950 if (!probably_never_executed_bb_p (cfun
, bb
))
3951 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3955 /* Build PREDICT_EXPR. */
3957 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3959 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3960 build_int_cst (integer_type_node
, predictor
));
3961 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3966 predictor_name (enum br_predictor predictor
)
3968 return predictor_info
[predictor
].name
;
3971 /* Predict branch probabilities and estimate profile of the tree CFG. */
3975 const pass_data pass_data_profile
=
3977 GIMPLE_PASS
, /* type */
3978 "profile_estimate", /* name */
3979 OPTGROUP_NONE
, /* optinfo_flags */
3980 TV_BRANCH_PROB
, /* tv_id */
3981 PROP_cfg
, /* properties_required */
3982 0, /* properties_provided */
3983 0, /* properties_destroyed */
3984 0, /* todo_flags_start */
3985 0, /* todo_flags_finish */
3988 class pass_profile
: public gimple_opt_pass
3991 pass_profile (gcc::context
*ctxt
)
3992 : gimple_opt_pass (pass_data_profile
, ctxt
)
3995 /* opt_pass methods: */
3996 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3997 virtual unsigned int execute (function
*);
3999 }; // class pass_profile
4002 pass_profile::execute (function
*fun
)
4006 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4009 loop_optimizer_init (LOOPS_NORMAL
);
4010 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4011 flow_loops_dump (dump_file
, NULL
, 0);
4013 mark_irreducible_loops ();
4015 nb_loops
= number_of_loops (fun
);
4019 tree_estimate_probability (false);
4024 loop_optimizer_finalize ();
4025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4026 gimple_dump_cfg (dump_file
, dump_flags
);
4027 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
4028 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
4029 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4032 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
4033 if (loop
->header
->count
.initialized_p ())
4034 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
4036 (int)expected_loop_iterations_unbounded (loop
));
4044 make_pass_profile (gcc::context
*ctxt
)
4046 return new pass_profile (ctxt
);
4049 /* Return true when PRED predictor should be removed after early
4050 tree passes. Most of the predictors are beneficial to survive
4051 as early inlining can also distribute then into caller's bodies. */
4054 strip_predictor_early (enum br_predictor pred
)
4058 case PRED_TREE_EARLY_RETURN
:
4065 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4066 we no longer need. EARLY is set to true when called from early
4070 strip_predict_hints (function
*fun
, bool early
)
4075 bool changed
= false;
4077 FOR_EACH_BB_FN (bb
, fun
)
4079 gimple_stmt_iterator bi
;
4080 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
4082 gimple
*stmt
= gsi_stmt (bi
);
4084 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
4087 || strip_predictor_early (gimple_predict_predictor (stmt
)))
4089 gsi_remove (&bi
, true);
4094 else if (is_gimple_call (stmt
))
4096 tree fndecl
= gimple_call_fndecl (stmt
);
4099 && ((fndecl
!= NULL_TREE
4100 && fndecl_built_in_p (fndecl
, BUILT_IN_EXPECT
)
4101 && gimple_call_num_args (stmt
) == 2)
4102 || (fndecl
!= NULL_TREE
4103 && fndecl_built_in_p (fndecl
,
4104 BUILT_IN_EXPECT_WITH_PROBABILITY
)
4105 && gimple_call_num_args (stmt
) == 3)
4106 || (gimple_call_internal_p (stmt
)
4107 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
)))
4109 var
= gimple_call_lhs (stmt
);
4114 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
4115 gsi_replace (&bi
, ass_stmt
, true);
4119 gsi_remove (&bi
, true);
4127 return changed
? TODO_cleanup_cfg
: 0;
4132 const pass_data pass_data_strip_predict_hints
=
4134 GIMPLE_PASS
, /* type */
4135 "*strip_predict_hints", /* name */
4136 OPTGROUP_NONE
, /* optinfo_flags */
4137 TV_BRANCH_PROB
, /* tv_id */
4138 PROP_cfg
, /* properties_required */
4139 0, /* properties_provided */
4140 0, /* properties_destroyed */
4141 0, /* todo_flags_start */
4142 0, /* todo_flags_finish */
4145 class pass_strip_predict_hints
: public gimple_opt_pass
4148 pass_strip_predict_hints (gcc::context
*ctxt
)
4149 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
4152 /* opt_pass methods: */
4153 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
4154 void set_pass_param (unsigned int n
, bool param
)
4156 gcc_assert (n
== 0);
4160 virtual unsigned int execute (function
*);
4165 }; // class pass_strip_predict_hints
4168 pass_strip_predict_hints::execute (function
*fun
)
4170 return strip_predict_hints (fun
, early_p
);
4176 make_pass_strip_predict_hints (gcc::context
*ctxt
)
4178 return new pass_strip_predict_hints (ctxt
);
4181 /* Rebuild function frequencies. Passes are in general expected to
4182 maintain profile by hand, however in some cases this is not possible:
4183 for example when inlining several functions with loops freuqencies might run
4184 out of scale and thus needs to be recomputed. */
4187 rebuild_frequencies (void)
4189 timevar_push (TV_REBUILD_FREQUENCIES
);
4191 /* When the max bb count in the function is small, there is a higher
4192 chance that there were truncation errors in the integer scaling
4193 of counts by inlining and other optimizations. This could lead
4194 to incorrect classification of code as being cold when it isn't.
4195 In that case, force the estimation of bb counts/frequencies from the
4196 branch probabilities, rather than computing frequencies from counts,
4197 which may also lead to frequencies incorrectly reduced to 0. There
4198 is less precision in the probabilities, so we only do this for small
4200 cfun
->cfg
->count_max
= profile_count::uninitialized ();
4202 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
4203 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
4205 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4207 loop_optimizer_init (0);
4208 add_noreturn_fake_exit_edges ();
4209 mark_irreducible_loops ();
4210 connect_infinite_loops_to_exit ();
4211 estimate_bb_frequencies (true);
4212 remove_fake_exit_edges ();
4213 loop_optimizer_finalize ();
4215 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
4216 update_max_bb_count ();
4217 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
4218 && !flag_guess_branch_prob
)
4222 timevar_pop (TV_REBUILD_FREQUENCIES
);
4225 /* Perform a dry run of the branch prediction pass and report comparsion of
4226 the predicted and real profile into the dump file. */
4229 report_predictor_hitrates (void)
4233 loop_optimizer_init (LOOPS_NORMAL
);
4234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4235 flow_loops_dump (dump_file
, NULL
, 0);
4237 mark_irreducible_loops ();
4239 nb_loops
= number_of_loops (cfun
);
4243 tree_estimate_probability (true);
4248 loop_optimizer_finalize ();
4251 /* Force edge E to be cold.
4252 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4253 keep low probability to represent possible error in a guess. This is used
4254 i.e. in case we predict loop to likely iterate given number of times but
4255 we are not 100% sure.
4257 This function locally updates profile without attempt to keep global
4258 consistency which can not be reached in full generality without full profile
4259 rebuild from probabilities alone. Doing so is not necessarily a good idea
4260 because frequencies and counts may be more realistic then probabilities.
4262 In some cases (such as for elimination of early exits during full loop
4263 unrolling) the caller can ensure that profile will get consistent
4267 force_edge_cold (edge e
, bool impossible
)
4269 profile_count count_sum
= profile_count::zero ();
4270 profile_probability prob_sum
= profile_probability::never ();
4273 bool uninitialized_exit
= false;
4275 /* When branch probability guesses are not known, then do nothing. */
4276 if (!impossible
&& !e
->count ().initialized_p ())
4279 profile_probability goal
= (impossible
? profile_probability::never ()
4280 : profile_probability::very_unlikely ());
4282 /* If edge is already improbably or cold, just return. */
4283 if (e
->probability
<= goal
4284 && (!impossible
|| e
->count () == profile_count::zero ()))
4286 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4289 if (e
->flags
& EDGE_FAKE
)
4291 if (e2
->count ().initialized_p ())
4292 count_sum
+= e2
->count ();
4293 if (e2
->probability
.initialized_p ())
4294 prob_sum
+= e2
->probability
;
4296 uninitialized_exit
= true;
4299 /* If we are not guessing profiles but have some other edges out,
4300 just assume the control flow goes elsewhere. */
4301 if (uninitialized_exit
)
4302 e
->probability
= goal
;
4303 /* If there are other edges out of e->src, redistribute probabilitity
4305 else if (prob_sum
> profile_probability::never ())
4307 if (!(e
->probability
< goal
))
4308 e
->probability
= goal
;
4310 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
4312 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4313 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
4314 "probability to other edges.\n",
4315 e
->src
->index
, e
->dest
->index
,
4316 impossible
? "impossible" : "cold");
4317 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4320 e2
->probability
/= prob_comp
;
4322 if (current_ir_type () != IR_GIMPLE
4323 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4324 update_br_prob_note (e
->src
);
4326 /* If all edges out of e->src are unlikely, the basic block itself
4330 if (prob_sum
== profile_probability::never ())
4331 e
->probability
= profile_probability::always ();
4335 e
->probability
= profile_probability::never ();
4336 /* If BB has some edges out that are not impossible, we can not
4337 assume that BB itself is. */
4340 if (current_ir_type () != IR_GIMPLE
4341 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4342 update_br_prob_note (e
->src
);
4343 if (e
->src
->count
== profile_count::zero ())
4345 if (count_sum
== profile_count::zero () && impossible
)
4348 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4350 else if (current_ir_type () == IR_GIMPLE
)
4351 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4352 !gsi_end_p (gsi
); gsi_next (&gsi
))
4354 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4360 /* FIXME: Implement RTL path. */
4365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4367 "Making bb %i impossible and dropping count to 0.\n",
4369 e
->src
->count
= profile_count::zero ();
4370 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4371 force_edge_cold (e2
, impossible
);
4376 /* If we did not adjusting, the source basic block has no likely edeges
4377 leaving other direction. In that case force that bb cold, too.
4378 This in general is difficult task to do, but handle special case when
4379 BB has only one predecestor. This is common case when we are updating
4380 after loop transforms. */
4381 if (!(prob_sum
> profile_probability::never ())
4382 && count_sum
== profile_count::zero ()
4383 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4384 > (impossible
? 0 : 1))
4386 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4387 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4388 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4389 impossible
? "impossible" : "cold");
4390 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4391 impossible
? 0 : 1);
4393 e
->src
->count
= profile_count::zero ();
4395 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4397 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4399 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4400 && maybe_hot_bb_p (cfun
, e
->src
))
4401 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4402 impossible
? "impossible" : "cold");
4408 namespace selftest
{
4410 /* Test that value range of predictor values defined in predict.def is
4411 within range (50, 100]. */
4413 struct branch_predictor
4419 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4422 test_prediction_value_range ()
4424 branch_predictor predictors
[] = {
4425 #include "predict.def"
4426 { NULL
, PROB_UNINITIALIZED
}
4429 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4431 if (predictors
[i
].probability
== PROB_UNINITIALIZED
)
4434 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4435 ASSERT_TRUE (p
>= 50 && p
<= 100);
4439 #undef DEF_PREDICTOR
4441 /* Run all of the selfests within this file. */
4446 test_prediction_value_range ();
4449 } // namespace selftest
4450 #endif /* CHECKING_P. */