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
);
97 /* Information we hold about each branch predictor.
98 Filled using information from predict.def. */
100 struct predictor_info
102 const char *const name
; /* Name used in the debugging dumps. */
103 const int hitrate
; /* Expected hitrate used by
104 predict_insn_def call. */
108 /* Use given predictor without Dempster-Shaffer theory if it matches
109 using first_match heuristics. */
110 #define PRED_FLAG_FIRST_MATCH 1
112 /* Recompute hitrate in percent to our representation. */
114 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
116 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
117 static const struct predictor_info predictor_info
[]= {
118 #include "predict.def"
120 /* Upper bound on predictors. */
125 static gcov_type min_count
= -1;
127 /* Determine the threshold for hot BB counts. */
130 get_hot_bb_threshold ()
132 gcov_working_set_t
*ws
;
135 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
137 min_count
= ws
->min_counter
;
142 /* Set the threshold for hot BB counts. */
145 set_hot_bb_threshold (gcov_type min
)
150 /* Return TRUE if frequency FREQ is considered to be hot. */
153 maybe_hot_count_p (struct function
*fun
, profile_count count
)
155 if (!count
.initialized_p ())
157 if (count
.ipa () == profile_count::zero ())
161 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
162 if (!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
164 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
166 if (node
->frequency
== NODE_FREQUENCY_HOT
)
169 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
171 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
172 && count
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
.apply_scale (2, 3)))
174 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
176 if (count
.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
), 1)
177 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
181 /* Code executed at most once is not hot. */
182 if (count
<= MAX (profile_info
? profile_info
->runs
: 1, 1))
184 return (count
.to_gcov_type () >= get_hot_bb_threshold ());
187 /* Return true in case BB can be CPU intensive and should be optimized
188 for maximal performance. */
191 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
193 gcc_checking_assert (fun
);
194 return maybe_hot_count_p (fun
, bb
->count
);
197 /* Return true in case BB can be CPU intensive and should be optimized
198 for maximal performance. */
201 maybe_hot_edge_p (edge e
)
203 return maybe_hot_count_p (cfun
, e
->count ());
206 /* Return true if profile COUNT and FREQUENCY, or function FUN static
207 node frequency reflects never being executed. */
210 probably_never_executed (struct function
*fun
,
213 gcc_checking_assert (fun
);
214 if (count
.ipa () == profile_count::zero ())
216 /* Do not trust adjusted counts. This will make us to drop int cold section
217 code with low execution count as a result of inlining. These low counts
218 are not safe even with read profile and may lead us to dropping
219 code which actually gets executed into cold section of binary that is not
221 if (count
.precise_p () && profile_status_for_fn (fun
) == PROFILE_READ
)
223 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
224 if (count
.apply_scale (unlikely_count_fraction
, 1) >= profile_info
->runs
)
228 if ((!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
229 && (cgraph_node::get (fun
->decl
)->frequency
230 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
236 /* Return true in case BB is probably never executed. */
239 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
241 return probably_never_executed (fun
, bb
->count
);
245 /* Return true if E is unlikely executed for obvious reasons. */
248 unlikely_executed_edge_p (edge e
)
250 return (e
->count () == profile_count::zero ()
251 || e
->probability
== profile_probability::never ())
252 || (e
->flags
& (EDGE_EH
| EDGE_FAKE
));
255 /* Return true in case edge E is probably never executed. */
258 probably_never_executed_edge_p (struct function
*fun
, edge e
)
260 if (unlikely_executed_edge_p (e
))
262 return probably_never_executed (fun
, e
->count ());
265 /* Return true when current function should always be optimized for size. */
268 optimize_function_for_size_p (struct function
*fun
)
270 if (!fun
|| !fun
->decl
)
271 return optimize_size
;
272 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
273 return n
&& n
->optimize_for_size_p ();
276 /* Return true when current function should always be optimized for speed. */
279 optimize_function_for_speed_p (struct function
*fun
)
281 return !optimize_function_for_size_p (fun
);
284 /* Return the optimization type that should be used for the function FUN. */
287 function_optimization_type (struct function
*fun
)
289 return (optimize_function_for_speed_p (fun
)
291 : OPTIMIZE_FOR_SIZE
);
294 /* Return TRUE when BB should be optimized for size. */
297 optimize_bb_for_size_p (const_basic_block bb
)
299 return (optimize_function_for_size_p (cfun
)
300 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
303 /* Return TRUE when BB should be optimized for speed. */
306 optimize_bb_for_speed_p (const_basic_block bb
)
308 return !optimize_bb_for_size_p (bb
);
311 /* Return the optimization type that should be used for block BB. */
314 bb_optimization_type (const_basic_block bb
)
316 return (optimize_bb_for_speed_p (bb
)
318 : OPTIMIZE_FOR_SIZE
);
321 /* Return TRUE when BB should be optimized for size. */
324 optimize_edge_for_size_p (edge e
)
326 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
329 /* Return TRUE when BB should be optimized for speed. */
332 optimize_edge_for_speed_p (edge e
)
334 return !optimize_edge_for_size_p (e
);
337 /* Return TRUE when BB should be optimized for size. */
340 optimize_insn_for_size_p (void)
342 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
345 /* Return TRUE when BB should be optimized for speed. */
348 optimize_insn_for_speed_p (void)
350 return !optimize_insn_for_size_p ();
353 /* Return TRUE when LOOP should be optimized for size. */
356 optimize_loop_for_size_p (struct loop
*loop
)
358 return optimize_bb_for_size_p (loop
->header
);
361 /* Return TRUE when LOOP should be optimized for speed. */
364 optimize_loop_for_speed_p (struct loop
*loop
)
366 return optimize_bb_for_speed_p (loop
->header
);
369 /* Return TRUE when LOOP nest should be optimized for speed. */
372 optimize_loop_nest_for_speed_p (struct loop
*loop
)
374 struct loop
*l
= loop
;
375 if (optimize_loop_for_speed_p (loop
))
378 while (l
&& l
!= loop
)
380 if (optimize_loop_for_speed_p (l
))
388 while (l
!= loop
&& !l
->next
)
397 /* Return TRUE when LOOP nest should be optimized for size. */
400 optimize_loop_nest_for_size_p (struct loop
*loop
)
402 return !optimize_loop_nest_for_speed_p (loop
);
405 /* Return true when edge E is likely to be well predictable by branch
409 predictable_edge_p (edge e
)
411 if (!e
->probability
.initialized_p ())
413 if ((e
->probability
.to_reg_br_prob_base ()
414 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
415 || (REG_BR_PROB_BASE
- e
->probability
.to_reg_br_prob_base ()
416 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
422 /* Set RTL expansion for BB profile. */
425 rtl_profile_for_bb (basic_block bb
)
427 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
430 /* Set RTL expansion for edge profile. */
433 rtl_profile_for_edge (edge e
)
435 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
438 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
440 default_rtl_profile (void)
442 crtl
->maybe_hot_insn_p
= true;
445 /* Return true if the one of outgoing edges is already predicted by
449 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
452 if (!INSN_P (BB_END (bb
)))
454 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
455 if (REG_NOTE_KIND (note
) == REG_BR_PRED
456 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
461 /* Structure representing predictions in tree level. */
463 struct edge_prediction
{
464 struct edge_prediction
*ep_next
;
466 enum br_predictor ep_predictor
;
470 /* This map contains for a basic block the list of predictions for the
473 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
475 /* Return true if the one of outgoing edges is already predicted by
479 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
481 struct edge_prediction
*i
;
482 edge_prediction
**preds
= bb_predictions
->get (bb
);
487 for (i
= *preds
; i
; i
= i
->ep_next
)
488 if (i
->ep_predictor
== predictor
)
493 /* Return true if the one of outgoing edges is already predicted by
494 PREDICTOR for edge E predicted as TAKEN. */
497 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
499 struct edge_prediction
*i
;
500 basic_block bb
= e
->src
;
501 edge_prediction
**preds
= bb_predictions
->get (bb
);
505 int probability
= predictor_info
[(int) predictor
].hitrate
;
508 probability
= REG_BR_PROB_BASE
- probability
;
510 for (i
= *preds
; i
; i
= i
->ep_next
)
511 if (i
->ep_predictor
== predictor
513 && i
->ep_probability
== probability
)
518 /* Same predicate as above, working on edges. */
520 edge_probability_reliable_p (const_edge e
)
522 return e
->probability
.probably_reliable_p ();
525 /* Same predicate as edge_probability_reliable_p, working on notes. */
527 br_prob_note_reliable_p (const_rtx note
)
529 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
530 return profile_probability::from_reg_br_prob_note
531 (XINT (note
, 0)).probably_reliable_p ();
535 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
537 gcc_assert (any_condjump_p (insn
));
538 if (!flag_guess_branch_prob
)
541 add_reg_note (insn
, REG_BR_PRED
,
542 gen_rtx_CONCAT (VOIDmode
,
543 GEN_INT ((int) predictor
),
544 GEN_INT ((int) probability
)));
547 /* Predict insn by given predictor. */
550 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
551 enum prediction taken
)
553 int probability
= predictor_info
[(int) predictor
].hitrate
;
554 gcc_assert (probability
!= PROB_UNINITIALIZED
);
557 probability
= REG_BR_PROB_BASE
- probability
;
559 predict_insn (insn
, predictor
, probability
);
562 /* Predict edge E with given probability if possible. */
565 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
568 last_insn
= BB_END (e
->src
);
570 /* We can store the branch prediction information only about
571 conditional jumps. */
572 if (!any_condjump_p (last_insn
))
575 /* We always store probability of branching. */
576 if (e
->flags
& EDGE_FALLTHRU
)
577 probability
= REG_BR_PROB_BASE
- probability
;
579 predict_insn (last_insn
, predictor
, probability
);
582 /* Predict edge E with the given PROBABILITY. */
584 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
586 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
587 && EDGE_COUNT (e
->src
->succs
) > 1
588 && flag_guess_branch_prob
591 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
592 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
596 i
->ep_probability
= probability
;
597 i
->ep_predictor
= predictor
;
602 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
603 to the filter function. */
606 filter_predictions (edge_prediction
**preds
,
607 bool (*filter
) (edge_prediction
*, void *), void *data
)
614 struct edge_prediction
**prediction
= preds
;
615 struct edge_prediction
*next
;
619 if ((*filter
) (*prediction
, data
))
620 prediction
= &((*prediction
)->ep_next
);
623 next
= (*prediction
)->ep_next
;
631 /* Filter function predicate that returns true for a edge predicate P
632 if its edge is equal to DATA. */
635 equal_edge_p (edge_prediction
*p
, void *data
)
637 return p
->ep_edge
== (edge
)data
;
640 /* Remove all predictions on given basic block that are attached
643 remove_predictions_associated_with_edge (edge e
)
648 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
649 filter_predictions (preds
, equal_edge_p
, e
);
652 /* Clears the list of predictions stored for BB. */
655 clear_bb_predictions (basic_block bb
)
657 edge_prediction
**preds
= bb_predictions
->get (bb
);
658 struct edge_prediction
*pred
, *next
;
663 for (pred
= *preds
; pred
; pred
= next
)
665 next
= pred
->ep_next
;
671 /* Return true when we can store prediction on insn INSN.
672 At the moment we represent predictions only on conditional
673 jumps, not at computed jump or other complicated cases. */
675 can_predict_insn_p (const rtx_insn
*insn
)
677 return (JUMP_P (insn
)
678 && any_condjump_p (insn
)
679 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
682 /* Predict edge E by given predictor if possible. */
685 predict_edge_def (edge e
, enum br_predictor predictor
,
686 enum prediction taken
)
688 int probability
= predictor_info
[(int) predictor
].hitrate
;
691 probability
= REG_BR_PROB_BASE
- probability
;
693 predict_edge (e
, predictor
, probability
);
696 /* Invert all branch predictions or probability notes in the INSN. This needs
697 to be done each time we invert the condition used by the jump. */
700 invert_br_probabilities (rtx insn
)
704 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
705 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
706 XINT (note
, 0) = profile_probability::from_reg_br_prob_note
707 (XINT (note
, 0)).invert ().to_reg_br_prob_note ();
708 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
709 XEXP (XEXP (note
, 0), 1)
710 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
713 /* Dump information about the branch prediction to the output file. */
716 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
717 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
727 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
728 if (! (e
->flags
& EDGE_FALLTHRU
))
731 char edge_info_str
[128];
733 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
734 ep_edge
->dest
->index
);
736 edge_info_str
[0] = '\0';
738 fprintf (file
, " %s heuristics%s%s: %.2f%%",
739 predictor_info
[predictor
].name
,
740 edge_info_str
, reason_messages
[reason
],
741 probability
* 100.0 / REG_BR_PROB_BASE
);
743 if (bb
->count
.initialized_p ())
745 fprintf (file
, " exec ");
746 bb
->count
.dump (file
);
749 fprintf (file
, " hit ");
750 e
->count ().dump (file
);
751 fprintf (file
, " (%.1f%%)", e
->count ().to_gcov_type() * 100.0
752 / bb
->count
.to_gcov_type ());
756 fprintf (file
, "\n");
758 /* Print output that be easily read by analyze_brprob.py script. We are
759 interested only in counts that are read from GCDA files. */
760 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
761 && bb
->count
.precise_p ()
762 && reason
== REASON_NONE
)
764 gcc_assert (e
->count ().precise_p ());
765 fprintf (file
, ";;heuristics;%s;%" PRId64
";%" PRId64
";%.1f;\n",
766 predictor_info
[predictor
].name
,
767 bb
->count
.to_gcov_type (), e
->count ().to_gcov_type (),
768 probability
* 100.0 / REG_BR_PROB_BASE
);
772 /* Return true if STMT is known to be unlikely executed. */
775 unlikely_executed_stmt_p (gimple
*stmt
)
777 if (!is_gimple_call (stmt
))
779 /* NORETURN attribute alone is not strong enough: exit() may be quite
780 likely executed once during program run. */
781 if (gimple_call_fntype (stmt
)
782 && lookup_attribute ("cold",
783 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
784 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
786 tree decl
= gimple_call_fndecl (stmt
);
789 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
790 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
793 cgraph_node
*n
= cgraph_node::get (decl
);
798 n
= n
->ultimate_alias_target (&avail
);
799 if (avail
< AVAIL_AVAILABLE
)
802 || n
->decl
== current_function_decl
)
804 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
807 /* Return true if BB is unlikely executed. */
810 unlikely_executed_bb_p (basic_block bb
)
812 if (bb
->count
== profile_count::zero ())
814 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
816 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
817 !gsi_end_p (gsi
); gsi_next (&gsi
))
819 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
821 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
827 /* We can not predict the probabilities of outgoing edges of bb. Set them
828 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
829 even probability for all edges not mentioned in the set. These edges
830 are given PROB_VERY_UNLIKELY probability. */
833 set_even_probabilities (basic_block bb
,
834 hash_set
<edge
> *unlikely_edges
= NULL
)
836 unsigned nedges
= 0, unlikely_count
= 0;
839 profile_probability all
= profile_probability::always ();
841 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
842 if (e
->probability
.initialized_p ())
843 all
-= e
->probability
;
844 else if (!unlikely_executed_edge_p (e
))
847 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
849 all
-= profile_probability::very_unlikely ();
854 /* Make the distribution even if all edges are unlikely. */
855 if (unlikely_count
== nedges
)
857 unlikely_edges
= NULL
;
861 unsigned c
= nedges
- unlikely_count
;
863 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
864 if (e
->probability
.initialized_p ())
866 else if (!unlikely_executed_edge_p (e
))
868 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
869 e
->probability
= profile_probability::very_unlikely ();
871 e
->probability
= all
.apply_scale (1, c
).guessed ();
874 e
->probability
= profile_probability::never ();
877 /* Add REG_BR_PROB note to JUMP with PROB. */
880 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
882 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
883 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
886 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
887 note if not already present. Remove now useless REG_BR_PRED notes. */
890 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
895 int best_probability
= PROB_EVEN
;
896 enum br_predictor best_predictor
= END_PREDICTORS
;
897 int combined_probability
= REG_BR_PROB_BASE
/ 2;
899 bool first_match
= false;
902 if (!can_predict_insn_p (insn
))
904 set_even_probabilities (bb
);
908 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
909 pnote
= ®_NOTES (insn
);
911 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
914 /* We implement "first match" heuristics and use probability guessed
915 by predictor with smallest index. */
916 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
917 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
919 enum br_predictor predictor
= ((enum br_predictor
)
920 INTVAL (XEXP (XEXP (note
, 0), 0)));
921 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
924 if (best_predictor
> predictor
925 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
926 best_probability
= probability
, best_predictor
= predictor
;
928 d
= (combined_probability
* probability
929 + (REG_BR_PROB_BASE
- combined_probability
)
930 * (REG_BR_PROB_BASE
- probability
));
932 /* Use FP math to avoid overflows of 32bit integers. */
934 /* If one probability is 0% and one 100%, avoid division by zero. */
935 combined_probability
= REG_BR_PROB_BASE
/ 2;
937 combined_probability
= (((double) combined_probability
) * probability
938 * REG_BR_PROB_BASE
/ d
+ 0.5);
941 /* Decide which heuristic to use. In case we didn't match anything,
942 use no_prediction heuristic, in case we did match, use either
943 first match or Dempster-Shaffer theory depending on the flags. */
945 if (best_predictor
!= END_PREDICTORS
)
949 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
950 combined_probability
, bb
);
954 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
955 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
957 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
958 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
962 combined_probability
= best_probability
;
963 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
967 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
969 enum br_predictor predictor
= ((enum br_predictor
)
970 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
971 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
973 dump_prediction (dump_file
, predictor
, probability
, bb
,
974 (!first_match
|| best_predictor
== predictor
)
975 ? REASON_NONE
: REASON_IGNORED
);
976 *pnote
= XEXP (*pnote
, 1);
979 pnote
= &XEXP (*pnote
, 1);
984 profile_probability p
985 = profile_probability::from_reg_br_prob_base (combined_probability
);
986 add_reg_br_prob_note (insn
, p
);
988 /* Save the prediction into CFG in case we are seeing non-degenerated
990 if (!single_succ_p (bb
))
992 BRANCH_EDGE (bb
)->probability
= p
;
993 FALLTHRU_EDGE (bb
)->probability
994 = BRANCH_EDGE (bb
)->probability
.invert ();
997 else if (!single_succ_p (bb
))
999 profile_probability prob
= profile_probability::from_reg_br_prob_note
1000 (XINT (prob_note
, 0));
1002 BRANCH_EDGE (bb
)->probability
= prob
;
1003 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
1006 single_succ_edge (bb
)->probability
= profile_probability::always ();
1009 /* Edge prediction hash traits. */
1011 struct predictor_hash
: pointer_hash
<edge_prediction
>
1014 static inline hashval_t
hash (const edge_prediction
*);
1015 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
1018 /* Calculate hash value of an edge prediction P based on predictor and
1019 normalized probability. */
1022 predictor_hash::hash (const edge_prediction
*p
)
1024 inchash::hash hstate
;
1025 hstate
.add_int (p
->ep_predictor
);
1027 int prob
= p
->ep_probability
;
1028 if (prob
> REG_BR_PROB_BASE
/ 2)
1029 prob
= REG_BR_PROB_BASE
- prob
;
1031 hstate
.add_int (prob
);
1033 return hstate
.end ();
1036 /* Return true whether edge predictions P1 and P2 use the same predictor and
1037 have equal (or opposed probability). */
1040 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1042 return (p1
->ep_predictor
== p2
->ep_predictor
1043 && (p1
->ep_probability
== p2
->ep_probability
1044 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1047 struct predictor_hash_traits
: predictor_hash
,
1048 typed_noop_remove
<edge_prediction
*> {};
1050 /* Return true if edge prediction P is not in DATA hash set. */
1053 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1055 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1056 return !remove
->contains (p
);
1059 /* Prune predictions for a basic block BB. Currently we do following
1062 1) remove duplicate prediction that is guessed with the same probability
1063 (different than 1/2) to both edge
1064 2) remove duplicates for a prediction that belongs with the same probability
1070 prune_predictions_for_bb (basic_block bb
)
1072 edge_prediction
**preds
= bb_predictions
->get (bb
);
1076 hash_table
<predictor_hash_traits
> s (13);
1077 hash_set
<edge_prediction
*> remove
;
1079 /* Step 1: identify predictors that should be removed. */
1080 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1082 edge_prediction
*existing
= s
.find (pred
);
1085 if (pred
->ep_edge
== existing
->ep_edge
1086 && pred
->ep_probability
== existing
->ep_probability
)
1088 /* Remove a duplicate predictor. */
1089 dump_prediction (dump_file
, pred
->ep_predictor
,
1090 pred
->ep_probability
, bb
,
1091 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1095 else if (pred
->ep_edge
!= existing
->ep_edge
1096 && pred
->ep_probability
== existing
->ep_probability
1097 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1099 /* Remove both predictors as they predict the same
1101 dump_prediction (dump_file
, existing
->ep_predictor
,
1102 pred
->ep_probability
, bb
,
1103 REASON_EDGE_PAIR_DUPLICATE
,
1105 dump_prediction (dump_file
, pred
->ep_predictor
,
1106 pred
->ep_probability
, bb
,
1107 REASON_EDGE_PAIR_DUPLICATE
,
1110 remove
.add (existing
);
1115 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1119 /* Step 2: Remove predictors. */
1120 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1124 /* Combine predictions into single probability and store them into CFG.
1125 Remove now useless prediction entries.
1126 If DRY_RUN is set, only produce dumps and do not modify profile. */
1129 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1131 int best_probability
= PROB_EVEN
;
1132 enum br_predictor best_predictor
= END_PREDICTORS
;
1133 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1135 bool first_match
= false;
1137 struct edge_prediction
*pred
;
1139 edge e
, first
= NULL
, second
= NULL
;
1144 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1146 if (!unlikely_executed_edge_p (e
))
1149 if (first
&& !second
)
1154 else if (!e
->probability
.initialized_p ())
1155 e
->probability
= profile_probability::never ();
1156 if (!e
->probability
.initialized_p ())
1158 else if (e
->probability
== profile_probability::never ())
1162 /* When there is no successor or only one choice, prediction is easy.
1164 When we have a basic block with more than 2 successors, the situation
1165 is more complicated as DS theory cannot be used literally.
1166 More precisely, let's assume we predicted edge e1 with probability p1,
1167 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1168 need to find probability of e.g. m1({b2}), which we don't know.
1169 The only approximation is to equally distribute 1-p1 to all edges
1172 According to numbers we've got from SPEC2006 benchark, there's only
1173 one interesting reliable predictor (noreturn call), which can be
1174 handled with a bit easier approach. */
1177 hash_set
<edge
> unlikely_edges (4);
1179 /* Identify all edges that have a probability close to very unlikely.
1180 Doing the approach for very unlikely doesn't worth for doing as
1181 there's no such probability in SPEC2006 benchmark. */
1182 edge_prediction
**preds
= bb_predictions
->get (bb
);
1184 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1185 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
)
1186 unlikely_edges
.add (pred
->ep_edge
);
1189 set_even_probabilities (bb
, &unlikely_edges
);
1190 clear_bb_predictions (bb
);
1193 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1194 if (unlikely_edges
.elements () == 0)
1196 "%i edges in bb %i predicted to even probabilities\n",
1201 "%i edges in bb %i predicted with some unlikely edges\n",
1203 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1204 if (!unlikely_executed_edge_p (e
))
1205 dump_prediction (dump_file
, PRED_COMBINED
,
1206 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1213 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1215 prune_predictions_for_bb (bb
);
1217 edge_prediction
**preds
= bb_predictions
->get (bb
);
1221 /* We implement "first match" heuristics and use probability guessed
1222 by predictor with smallest index. */
1223 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1225 enum br_predictor predictor
= pred
->ep_predictor
;
1226 int probability
= pred
->ep_probability
;
1228 if (pred
->ep_edge
!= first
)
1229 probability
= REG_BR_PROB_BASE
- probability
;
1232 /* First match heuristics would be widly confused if we predicted
1234 if (best_predictor
> predictor
1235 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1237 struct edge_prediction
*pred2
;
1238 int prob
= probability
;
1240 for (pred2
= (struct edge_prediction
*) *preds
;
1241 pred2
; pred2
= pred2
->ep_next
)
1242 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1244 int probability2
= pred2
->ep_probability
;
1246 if (pred2
->ep_edge
!= first
)
1247 probability2
= REG_BR_PROB_BASE
- probability2
;
1249 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1250 (probability2
< REG_BR_PROB_BASE
/ 2))
1253 /* If the same predictor later gave better result, go for it! */
1254 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1255 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1256 prob
= probability2
;
1259 best_probability
= prob
, best_predictor
= predictor
;
1262 d
= (combined_probability
* probability
1263 + (REG_BR_PROB_BASE
- combined_probability
)
1264 * (REG_BR_PROB_BASE
- probability
));
1266 /* Use FP math to avoid overflows of 32bit integers. */
1268 /* If one probability is 0% and one 100%, avoid division by zero. */
1269 combined_probability
= REG_BR_PROB_BASE
/ 2;
1271 combined_probability
= (((double) combined_probability
)
1273 * REG_BR_PROB_BASE
/ d
+ 0.5);
1277 /* Decide which heuristic to use. In case we didn't match anything,
1278 use no_prediction heuristic, in case we did match, use either
1279 first match or Dempster-Shaffer theory depending on the flags. */
1281 if (best_predictor
!= END_PREDICTORS
)
1285 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1289 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1290 !first_match
? REASON_NONE
: REASON_IGNORED
);
1292 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1293 first_match
? REASON_NONE
: REASON_IGNORED
);
1297 combined_probability
= best_probability
;
1298 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1302 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1304 enum br_predictor predictor
= pred
->ep_predictor
;
1305 int probability
= pred
->ep_probability
;
1307 dump_prediction (dump_file
, predictor
, probability
, bb
,
1308 (!first_match
|| best_predictor
== predictor
)
1309 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1312 clear_bb_predictions (bb
);
1315 /* If we have only one successor which is unknown, we can compute missing
1319 profile_probability prob
= profile_probability::always ();
1320 edge missing
= NULL
;
1322 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1323 if (e
->probability
.initialized_p ())
1324 prob
-= e
->probability
;
1325 else if (missing
== NULL
)
1329 missing
->probability
= prob
;
1331 /* If nothing is unknown, we have nothing to update. */
1332 else if (!nunknown
&& nzero
!= (int)EDGE_COUNT (bb
->succs
))
1337 = profile_probability::from_reg_br_prob_base (combined_probability
);
1338 second
->probability
= first
->probability
.invert ();
1342 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1343 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1345 T1 and T2 should be one of the following cases:
1346 1. T1 is SSA_NAME, T2 is NULL
1347 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1348 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1351 strips_small_constant (tree t1
, tree t2
)
1358 else if (TREE_CODE (t1
) == SSA_NAME
)
1360 else if (tree_fits_shwi_p (t1
))
1361 value
= tree_to_shwi (t1
);
1367 else if (tree_fits_shwi_p (t2
))
1368 value
= tree_to_shwi (t2
);
1369 else if (TREE_CODE (t2
) == SSA_NAME
)
1377 if (value
<= 4 && value
>= -4)
1383 /* Return the SSA_NAME in T or T's operands.
1384 Return NULL if SSA_NAME cannot be found. */
1387 get_base_value (tree t
)
1389 if (TREE_CODE (t
) == SSA_NAME
)
1392 if (!BINARY_CLASS_P (t
))
1395 switch (TREE_OPERAND_LENGTH (t
))
1398 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1400 return strips_small_constant (TREE_OPERAND (t
, 0),
1401 TREE_OPERAND (t
, 1));
1407 /* Check the compare STMT in LOOP. If it compares an induction
1408 variable to a loop invariant, return true, and save
1409 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1410 Otherwise return false and set LOOP_INVAIANT to NULL. */
1413 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1414 tree
*loop_invariant
,
1415 enum tree_code
*compare_code
,
1419 tree op0
, op1
, bound
, base
;
1421 enum tree_code code
;
1424 code
= gimple_cond_code (stmt
);
1425 *loop_invariant
= NULL
;
1441 op0
= gimple_cond_lhs (stmt
);
1442 op1
= gimple_cond_rhs (stmt
);
1444 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1445 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1447 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1449 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1451 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1452 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1454 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1455 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1458 if (integer_zerop (iv0
.step
))
1460 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1461 code
= invert_tree_comparison (code
, false);
1464 if (tree_fits_shwi_p (iv1
.step
))
1473 if (tree_fits_shwi_p (iv0
.step
))
1479 if (TREE_CODE (bound
) != INTEGER_CST
)
1480 bound
= get_base_value (bound
);
1483 if (TREE_CODE (base
) != INTEGER_CST
)
1484 base
= get_base_value (base
);
1488 *loop_invariant
= bound
;
1489 *compare_code
= code
;
1491 *loop_iv_base
= base
;
1495 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1498 expr_coherent_p (tree t1
, tree t2
)
1501 tree ssa_name_1
= NULL
;
1502 tree ssa_name_2
= NULL
;
1504 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1505 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1510 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1512 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1515 /* Check to see if t1 is expressed/defined with t2. */
1516 stmt
= SSA_NAME_DEF_STMT (t1
);
1517 gcc_assert (stmt
!= NULL
);
1518 if (is_gimple_assign (stmt
))
1520 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1521 if (ssa_name_1
&& ssa_name_1
== t2
)
1525 /* Check to see if t2 is expressed/defined with t1. */
1526 stmt
= SSA_NAME_DEF_STMT (t2
);
1527 gcc_assert (stmt
!= NULL
);
1528 if (is_gimple_assign (stmt
))
1530 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1531 if (ssa_name_2
&& ssa_name_2
== t1
)
1535 /* Compare if t1 and t2's def_stmts are identical. */
1536 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1542 /* Return true if E is predicted by one of loop heuristics. */
1545 predicted_by_loop_heuristics_p (basic_block bb
)
1547 struct edge_prediction
*i
;
1548 edge_prediction
**preds
= bb_predictions
->get (bb
);
1553 for (i
= *preds
; i
; i
= i
->ep_next
)
1554 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1555 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1556 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1557 || i
->ep_predictor
== PRED_LOOP_EXIT
1558 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1559 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1564 /* Predict branch probability of BB when BB contains a branch that compares
1565 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1566 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1569 for (int i = 0; i < bound; i++) {
1576 In this loop, we will predict the branch inside the loop to be taken. */
1579 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1580 tree loop_bound_var
,
1581 tree loop_iv_base_var
,
1582 enum tree_code loop_bound_code
,
1583 int loop_bound_step
)
1586 tree compare_var
, compare_base
;
1587 enum tree_code compare_code
;
1588 tree compare_step_var
;
1592 if (predicted_by_loop_heuristics_p (bb
))
1595 stmt
= last_stmt (bb
);
1596 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1598 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1605 /* Find the taken edge. */
1606 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1607 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1610 /* When comparing an IV to a loop invariant, NE is more likely to be
1611 taken while EQ is more likely to be not-taken. */
1612 if (compare_code
== NE_EXPR
)
1614 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1617 else if (compare_code
== EQ_EXPR
)
1619 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1623 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1626 /* If loop bound, base and compare bound are all constants, we can
1627 calculate the probability directly. */
1628 if (tree_fits_shwi_p (loop_bound_var
)
1629 && tree_fits_shwi_p (compare_var
)
1630 && tree_fits_shwi_p (compare_base
))
1633 wi::overflow_type overflow
;
1634 bool overall_overflow
= false;
1635 widest_int compare_count
, tem
;
1637 /* (loop_bound - base) / compare_step */
1638 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1639 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1640 overall_overflow
|= overflow
;
1641 widest_int loop_count
= wi::div_trunc (tem
,
1642 wi::to_widest (compare_step_var
),
1644 overall_overflow
|= overflow
;
1646 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1647 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1649 /* (loop_bound - compare_bound) / compare_step */
1650 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1651 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1652 overall_overflow
|= overflow
;
1653 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1655 overall_overflow
|= overflow
;
1659 /* (compare_bound - base) / compare_step */
1660 tem
= wi::sub (wi::to_widest (compare_var
),
1661 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1662 overall_overflow
|= overflow
;
1663 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1665 overall_overflow
|= overflow
;
1667 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1669 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1671 if (wi::neg_p (compare_count
))
1673 if (wi::neg_p (loop_count
))
1675 if (loop_count
== 0)
1677 else if (wi::cmps (compare_count
, loop_count
) == 1)
1678 probability
= REG_BR_PROB_BASE
;
1681 tem
= compare_count
* REG_BR_PROB_BASE
;
1682 tem
= wi::udiv_trunc (tem
, loop_count
);
1683 probability
= tem
.to_uhwi ();
1686 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1687 if (!overall_overflow
)
1688 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1693 if (expr_coherent_p (loop_bound_var
, compare_var
))
1695 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1696 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1697 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1698 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1699 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1700 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1701 else if (loop_bound_code
== NE_EXPR
)
1703 /* If the loop backedge condition is "(i != bound)", we do
1704 the comparison based on the step of IV:
1705 * step < 0 : backedge condition is like (i > bound)
1706 * step > 0 : backedge condition is like (i < bound) */
1707 gcc_assert (loop_bound_step
!= 0);
1708 if (loop_bound_step
> 0
1709 && (compare_code
== LT_EXPR
1710 || compare_code
== LE_EXPR
))
1711 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1712 else if (loop_bound_step
< 0
1713 && (compare_code
== GT_EXPR
1714 || compare_code
== GE_EXPR
))
1715 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1717 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1720 /* The branch is predicted not-taken if loop_bound_code is
1721 opposite with compare_code. */
1722 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1724 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1727 for (i = s; i < h; i++)
1729 The branch should be predicted taken. */
1730 if (loop_bound_step
> 0
1731 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1732 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1733 else if (loop_bound_step
< 0
1734 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1735 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1737 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1741 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1742 exits are resulted from short-circuit conditions that will generate an
1745 if (foo() || global > 10)
1748 This will be translated into:
1753 if foo() goto BB6 else goto BB5
1755 if global > 10 goto BB6 else goto BB7
1759 iftmp = (PHI 0(BB5), 1(BB6))
1760 if iftmp == 1 goto BB8 else goto BB3
1762 outside of the loop...
1764 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1765 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1766 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1767 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1770 predict_extra_loop_exits (edge exit_edge
)
1773 bool check_value_one
;
1774 gimple
*lhs_def_stmt
;
1776 tree cmp_rhs
, cmp_lhs
;
1780 last
= last_stmt (exit_edge
->src
);
1783 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1787 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1788 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1789 if (!TREE_CONSTANT (cmp_rhs
)
1790 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1792 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1795 /* If check_value_one is true, only the phi_args with value '1' will lead
1796 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1798 check_value_one
= (((integer_onep (cmp_rhs
))
1799 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1800 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1802 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1806 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1810 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1814 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1815 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1817 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1819 if ((check_value_one
^ integer_onep (val
)) == 1)
1821 if (EDGE_COUNT (e
->src
->succs
) != 1)
1823 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1827 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1828 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1833 /* Predict edge probabilities by exploiting loop structure. */
1836 predict_loops (void)
1840 hash_set
<struct loop
*> with_recursion(10);
1842 FOR_EACH_BB_FN (bb
, cfun
)
1844 gimple_stmt_iterator gsi
;
1847 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1848 if (is_gimple_call (gsi_stmt (gsi
))
1849 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1850 && recursive_call_p (current_function_decl
, decl
))
1852 loop
= bb
->loop_father
;
1853 while (loop
&& !with_recursion
.add (loop
))
1854 loop
= loop_outer (loop
);
1858 /* Try to predict out blocks in a loop that are not part of a
1860 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1862 basic_block bb
, *bbs
;
1863 unsigned j
, n_exits
= 0;
1865 struct tree_niter_desc niter_desc
;
1867 struct nb_iter_bound
*nb_iter
;
1868 enum tree_code loop_bound_code
= ERROR_MARK
;
1869 tree loop_bound_step
= NULL
;
1870 tree loop_bound_var
= NULL
;
1871 tree loop_iv_base
= NULL
;
1873 bool recursion
= with_recursion
.contains (loop
);
1875 exits
= get_loop_exit_edges (loop
);
1876 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1877 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1886 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1887 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1888 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1889 && max_loop_iterations_int (loop
) >= 0)
1892 "Loop %d iterates at most %i times.\n", loop
->num
,
1893 (int)max_loop_iterations_int (loop
));
1895 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1896 && likely_max_loop_iterations_int (loop
) >= 0)
1898 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1899 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1902 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1905 HOST_WIDE_INT nitercst
;
1906 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1908 enum br_predictor predictor
;
1911 if (unlikely_executed_edge_p (ex
)
1912 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
1914 /* Loop heuristics do not expect exit conditional to be inside
1915 inner loop. We predict from innermost to outermost loop. */
1916 if (predicted_by_loop_heuristics_p (ex
->src
))
1918 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1919 fprintf (dump_file
, "Skipping exit %i->%i because "
1920 "it is already predicted.\n",
1921 ex
->src
->index
, ex
->dest
->index
);
1924 predict_extra_loop_exits (ex
);
1926 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1927 niter
= niter_desc
.niter
;
1928 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1929 niter
= loop_niter_by_eval (loop
, ex
);
1930 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1931 && TREE_CODE (niter
) == INTEGER_CST
)
1933 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1934 ex
->src
->index
, ex
->dest
->index
,
1936 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1937 fprintf (dump_file
, " times.\n");
1940 if (TREE_CODE (niter
) == INTEGER_CST
)
1942 if (tree_fits_uhwi_p (niter
)
1944 && compare_tree_int (niter
, max
- 1) == -1)
1945 nitercst
= tree_to_uhwi (niter
) + 1;
1948 predictor
= PRED_LOOP_ITERATIONS
;
1950 /* If we have just one exit and we can derive some information about
1951 the number of iterations of the loop from the statements inside
1952 the loop, use it to predict this exit. */
1953 else if (n_exits
== 1
1954 && estimated_stmt_executions (loop
, &nit
))
1956 if (wi::gtu_p (nit
, max
))
1959 nitercst
= nit
.to_shwi ();
1960 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1962 /* If we have likely upper bound, trust it for very small iteration
1963 counts. Such loops would otherwise get mispredicted by standard
1964 LOOP_EXIT heuristics. */
1965 else if (n_exits
== 1
1966 && likely_max_stmt_executions (loop
, &nit
)
1968 RDIV (REG_BR_PROB_BASE
,
1972 ? PRED_LOOP_EXIT_WITH_RECURSION
1973 : PRED_LOOP_EXIT
].hitrate
)))
1975 nitercst
= nit
.to_shwi ();
1976 predictor
= PRED_LOOP_ITERATIONS_MAX
;
1980 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1981 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
1982 ex
->src
->index
, ex
->dest
->index
);
1986 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1987 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
1988 (int)nitercst
, predictor_info
[predictor
].name
);
1989 /* If the prediction for number of iterations is zero, do not
1990 predict the exit edges. */
1994 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
1995 predict_edge (ex
, predictor
, probability
);
1999 /* Find information about loop bound variables. */
2000 for (nb_iter
= loop
->bounds
; nb_iter
;
2001 nb_iter
= nb_iter
->next
)
2003 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
2005 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
2008 if (!stmt
&& last_stmt (loop
->header
)
2009 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
2010 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2012 is_comparison_with_loop_invariant_p (stmt
, loop
,
2018 bbs
= get_loop_body (loop
);
2020 for (j
= 0; j
< loop
->num_nodes
; j
++)
2027 /* Bypass loop heuristics on continue statement. These
2028 statements construct loops via "non-loop" constructs
2029 in the source language and are better to be handled
2031 if (predicted_by_p (bb
, PRED_CONTINUE
))
2033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2034 fprintf (dump_file
, "BB %i predicted by continue.\n",
2039 /* If we already used more reliable loop exit predictors, do not
2040 bother with PRED_LOOP_EXIT. */
2041 if (!predicted_by_loop_heuristics_p (bb
))
2043 /* For loop with many exits we don't want to predict all exits
2044 with the pretty large probability, because if all exits are
2045 considered in row, the loop would be predicted to iterate
2046 almost never. The code to divide probability by number of
2047 exits is very rough. It should compute the number of exits
2048 taken in each patch through function (not the overall number
2049 of exits that might be a lot higher for loops with wide switch
2050 statements in them) and compute n-th square root.
2052 We limit the minimal probability by 2% to avoid
2053 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2054 as this was causing regression in perl benchmark containing such
2057 int probability
= ((REG_BR_PROB_BASE
2060 ? PRED_LOOP_EXIT_WITH_RECURSION
2061 : PRED_LOOP_EXIT
].hitrate
)
2063 if (probability
< HITRATE (2))
2064 probability
= HITRATE (2);
2065 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2066 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2067 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2069 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2071 "Predicting exit %i->%i with prob %i.\n",
2072 e
->src
->index
, e
->dest
->index
, probability
);
2074 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2075 : PRED_LOOP_EXIT
, probability
);
2079 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2081 tree_to_shwi (loop_bound_step
));
2084 /* In the following code
2089 guess that cond is unlikely. */
2090 if (loop_outer (loop
)->num
)
2092 basic_block bb
= NULL
;
2093 edge preheader_edge
= loop_preheader_edge (loop
);
2095 if (single_pred_p (preheader_edge
->src
)
2096 && single_succ_p (preheader_edge
->src
))
2097 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2099 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2100 /* Pattern match fortran loop preheader:
2101 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2102 _17 = (logical(kind=4)) _16;
2108 Loop guard branch prediction says nothing about duplicated loop
2109 headers produced by fortran frontend and in this case we want
2110 to predict paths leading to this preheader. */
2113 && gimple_code (stmt
) == GIMPLE_COND
2114 && gimple_cond_code (stmt
) == NE_EXPR
2115 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2116 && integer_zerop (gimple_cond_rhs (stmt
)))
2118 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2119 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2120 && gimple_expr_code (call_stmt
) == NOP_EXPR
2121 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2122 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2123 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2124 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2125 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2126 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2127 == PRED_FORTRAN_LOOP_PREHEADER
)
2128 bb
= preheader_edge
->src
;
2132 if (!dominated_by_p (CDI_DOMINATORS
,
2133 loop_outer (loop
)->latch
, loop
->header
))
2134 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2136 ? PRED_LOOP_GUARD_WITH_RECURSION
2143 if (!dominated_by_p (CDI_DOMINATORS
,
2144 loop_outer (loop
)->latch
, bb
))
2145 predict_paths_leading_to (bb
,
2147 ? PRED_LOOP_GUARD_WITH_RECURSION
2154 /* Free basic blocks from get_loop_body. */
2159 /* Attempt to predict probabilities of BB outgoing edges using local
2162 bb_estimate_probability_locally (basic_block bb
)
2164 rtx_insn
*last_insn
= BB_END (bb
);
2167 if (! can_predict_insn_p (last_insn
))
2169 cond
= get_condition (last_insn
, NULL
, false, false);
2173 /* Try "pointer heuristic."
2174 A comparison ptr == 0 is predicted as false.
2175 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2176 if (COMPARISON_P (cond
)
2177 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2178 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2180 if (GET_CODE (cond
) == EQ
)
2181 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2182 else if (GET_CODE (cond
) == NE
)
2183 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2187 /* Try "opcode heuristic."
2188 EQ tests are usually false and NE tests are usually true. Also,
2189 most quantities are positive, so we can make the appropriate guesses
2190 about signed comparisons against zero. */
2191 switch (GET_CODE (cond
))
2194 /* Unconditional branch. */
2195 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2196 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2201 /* Floating point comparisons appears to behave in a very
2202 unpredictable way because of special role of = tests in
2204 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2206 /* Comparisons with 0 are often used for booleans and there is
2207 nothing useful to predict about them. */
2208 else if (XEXP (cond
, 1) == const0_rtx
2209 || XEXP (cond
, 0) == const0_rtx
)
2212 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2217 /* Floating point comparisons appears to behave in a very
2218 unpredictable way because of special role of = tests in
2220 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2222 /* Comparisons with 0 are often used for booleans and there is
2223 nothing useful to predict about them. */
2224 else if (XEXP (cond
, 1) == const0_rtx
2225 || XEXP (cond
, 0) == const0_rtx
)
2228 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2232 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2236 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2241 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2242 || XEXP (cond
, 1) == constm1_rtx
)
2243 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2248 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2249 || XEXP (cond
, 1) == constm1_rtx
)
2250 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2258 /* Set edge->probability for each successor edge of BB. */
2260 guess_outgoing_edge_probabilities (basic_block bb
)
2262 bb_estimate_probability_locally (bb
);
2263 combine_predictions_for_insn (BB_END (bb
), bb
);
2266 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
,
2267 HOST_WIDE_INT
*probability
);
2269 /* Helper function for expr_expected_value. */
2272 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2273 tree op1
, bitmap visited
, enum br_predictor
*predictor
,
2274 HOST_WIDE_INT
*probability
)
2278 /* Reset returned probability value. */
2280 *predictor
= PRED_UNCONDITIONAL
;
2282 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2284 if (TREE_CONSTANT (op0
))
2287 if (code
== IMAGPART_EXPR
)
2289 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2291 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2292 if (is_gimple_call (def
)
2293 && gimple_call_internal_p (def
)
2294 && (gimple_call_internal_fn (def
)
2295 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2297 /* Assume that any given atomic operation has low contention,
2298 and thus the compare-and-swap operation succeeds. */
2299 *predictor
= PRED_COMPARE_AND_SWAP
;
2300 return build_one_cst (TREE_TYPE (op0
));
2305 if (code
!= SSA_NAME
)
2308 def
= SSA_NAME_DEF_STMT (op0
);
2310 /* If we were already here, break the infinite cycle. */
2311 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2314 if (gimple_code (def
) == GIMPLE_PHI
)
2316 /* All the arguments of the PHI node must have the same constant
2318 int i
, n
= gimple_phi_num_args (def
);
2319 tree val
= NULL
, new_val
;
2321 for (i
= 0; i
< n
; i
++)
2323 tree arg
= PHI_ARG_DEF (def
, i
);
2324 enum br_predictor predictor2
;
2326 /* If this PHI has itself as an argument, we cannot
2327 determine the string length of this argument. However,
2328 if we can find an expected constant value for the other
2329 PHI args then we can still be sure that this is
2330 likely a constant. So be optimistic and just
2331 continue with the next argument. */
2332 if (arg
== PHI_RESULT (def
))
2335 HOST_WIDE_INT probability2
;
2336 new_val
= expr_expected_value (arg
, visited
, &predictor2
,
2339 /* It is difficult to combine value predictors. Simply assume
2340 that later predictor is weaker and take its prediction. */
2341 if (*predictor
< predictor2
)
2343 *predictor
= predictor2
;
2344 *probability
= probability2
;
2350 else if (!operand_equal_p (val
, new_val
, false))
2355 if (is_gimple_assign (def
))
2357 if (gimple_assign_lhs (def
) != op0
)
2360 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2361 gimple_assign_rhs1 (def
),
2362 gimple_assign_rhs_code (def
),
2363 gimple_assign_rhs2 (def
),
2364 visited
, predictor
, probability
);
2367 if (is_gimple_call (def
))
2369 tree decl
= gimple_call_fndecl (def
);
2372 if (gimple_call_internal_p (def
)
2373 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2375 gcc_assert (gimple_call_num_args (def
) == 3);
2376 tree val
= gimple_call_arg (def
, 0);
2377 if (TREE_CONSTANT (val
))
2379 tree val2
= gimple_call_arg (def
, 2);
2380 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2381 && tree_fits_uhwi_p (val2
)
2382 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2383 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2384 if (*predictor
== PRED_BUILTIN_EXPECT
)
2386 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
));
2387 return gimple_call_arg (def
, 1);
2392 if (DECL_IS_MALLOC (decl
) || DECL_IS_OPERATOR_NEW (decl
))
2395 *predictor
= PRED_MALLOC_NONNULL
;
2396 return boolean_true_node
;
2399 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2400 switch (DECL_FUNCTION_CODE (decl
))
2402 case BUILT_IN_EXPECT
:
2405 if (gimple_call_num_args (def
) != 2)
2407 val
= gimple_call_arg (def
, 0);
2408 if (TREE_CONSTANT (val
))
2410 *predictor
= PRED_BUILTIN_EXPECT
;
2412 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
));
2413 return gimple_call_arg (def
, 1);
2415 case BUILT_IN_EXPECT_WITH_PROBABILITY
:
2418 if (gimple_call_num_args (def
) != 3)
2420 val
= gimple_call_arg (def
, 0);
2421 if (TREE_CONSTANT (val
))
2423 /* Compute final probability as:
2424 probability * REG_BR_PROB_BASE. */
2425 tree prob
= gimple_call_arg (def
, 2);
2426 tree t
= TREE_TYPE (prob
);
2427 tree base
= build_int_cst (integer_type_node
,
2429 base
= build_real_from_int_cst (t
, base
);
2430 tree r
= fold_build2_initializer_loc (UNKNOWN_LOCATION
,
2431 MULT_EXPR
, t
, prob
, base
);
2433 = real_to_integer (TREE_REAL_CST_PTR (r
));
2434 if (probi
>= 0 && probi
<= REG_BR_PROB_BASE
)
2436 *predictor
= PRED_BUILTIN_EXPECT_WITH_PROBABILITY
;
2437 *probability
= probi
;
2439 return gimple_call_arg (def
, 1);
2442 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2443 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2444 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2445 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2446 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2447 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2448 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2449 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2450 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2451 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2452 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2453 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2454 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2455 /* Assume that any given atomic operation has low contention,
2456 and thus the compare-and-swap operation succeeds. */
2457 *predictor
= PRED_COMPARE_AND_SWAP
;
2458 return boolean_true_node
;
2459 case BUILT_IN_REALLOC
:
2461 *predictor
= PRED_MALLOC_NONNULL
;
2462 return boolean_true_node
;
2471 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2474 enum br_predictor predictor2
;
2475 HOST_WIDE_INT probability2
;
2476 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2479 op1
= expr_expected_value (op1
, visited
, &predictor2
, &probability2
);
2482 res
= fold_build2 (code
, type
, op0
, op1
);
2483 if (TREE_CODE (res
) == INTEGER_CST
2484 && TREE_CODE (op0
) == INTEGER_CST
2485 && TREE_CODE (op1
) == INTEGER_CST
)
2487 /* Combine binary predictions. */
2488 if (*probability
!= -1 || probability2
!= -1)
2490 HOST_WIDE_INT p1
= get_predictor_value (*predictor
, *probability
);
2491 HOST_WIDE_INT p2
= get_predictor_value (predictor2
, probability2
);
2492 *probability
= RDIV (p1
* p2
, REG_BR_PROB_BASE
);
2495 if (*predictor
< predictor2
)
2496 *predictor
= predictor2
;
2502 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2505 op0
= expr_expected_value (op0
, visited
, predictor
, probability
);
2508 res
= fold_build1 (code
, type
, op0
);
2509 if (TREE_CONSTANT (res
))
2516 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2517 The function is used by builtin_expect branch predictor so the evidence
2518 must come from this construct and additional possible constant folding.
2520 We may want to implement more involved value guess (such as value range
2521 propagation based prediction), but such tricks shall go to new
2525 expr_expected_value (tree expr
, bitmap visited
,
2526 enum br_predictor
*predictor
,
2527 HOST_WIDE_INT
*probability
)
2529 enum tree_code code
;
2532 if (TREE_CONSTANT (expr
))
2534 *predictor
= PRED_UNCONDITIONAL
;
2539 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2540 return expr_expected_value_1 (TREE_TYPE (expr
),
2541 op0
, code
, op1
, visited
, predictor
,
2546 /* Return probability of a PREDICTOR. If the predictor has variable
2547 probability return passed PROBABILITY. */
2549 static HOST_WIDE_INT
2550 get_predictor_value (br_predictor predictor
, HOST_WIDE_INT probability
)
2554 case PRED_BUILTIN_EXPECT
:
2555 case PRED_BUILTIN_EXPECT_WITH_PROBABILITY
:
2556 gcc_assert (probability
!= -1);
2559 gcc_assert (probability
== -1);
2560 return predictor_info
[(int) predictor
].hitrate
;
2564 /* Predict using opcode of the last statement in basic block. */
2566 tree_predict_by_opcode (basic_block bb
)
2568 gimple
*stmt
= last_stmt (bb
);
2575 enum br_predictor predictor
;
2576 HOST_WIDE_INT probability
;
2578 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2580 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2581 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2583 op0
= gimple_cond_lhs (stmt
);
2584 op1
= gimple_cond_rhs (stmt
);
2585 cmp
= gimple_cond_code (stmt
);
2586 type
= TREE_TYPE (op0
);
2587 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2588 &predictor
, &probability
);
2589 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2591 HOST_WIDE_INT prob
= get_predictor_value (predictor
, probability
);
2592 if (integer_zerop (val
))
2593 prob
= REG_BR_PROB_BASE
- prob
;
2594 predict_edge (then_edge
, predictor
, prob
);
2596 /* Try "pointer heuristic."
2597 A comparison ptr == 0 is predicted as false.
2598 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2599 if (POINTER_TYPE_P (type
))
2602 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2603 else if (cmp
== NE_EXPR
)
2604 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2608 /* Try "opcode heuristic."
2609 EQ tests are usually false and NE tests are usually true. Also,
2610 most quantities are positive, so we can make the appropriate guesses
2611 about signed comparisons against zero. */
2616 /* Floating point comparisons appears to behave in a very
2617 unpredictable way because of special role of = tests in
2619 if (FLOAT_TYPE_P (type
))
2621 /* Comparisons with 0 are often used for booleans and there is
2622 nothing useful to predict about them. */
2623 else if (integer_zerop (op0
) || integer_zerop (op1
))
2626 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2631 /* Floating point comparisons appears to behave in a very
2632 unpredictable way because of special role of = tests in
2634 if (FLOAT_TYPE_P (type
))
2636 /* Comparisons with 0 are often used for booleans and there is
2637 nothing useful to predict about them. */
2638 else if (integer_zerop (op0
)
2639 || integer_zerop (op1
))
2642 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2646 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2649 case UNORDERED_EXPR
:
2650 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2655 if (integer_zerop (op1
)
2656 || integer_onep (op1
)
2657 || integer_all_onesp (op1
)
2660 || real_minus_onep (op1
))
2661 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2666 if (integer_zerop (op1
)
2667 || integer_onep (op1
)
2668 || integer_all_onesp (op1
)
2671 || real_minus_onep (op1
))
2672 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2680 /* Returns TRUE if the STMT is exit(0) like statement. */
2683 is_exit_with_zero_arg (const gimple
*stmt
)
2685 /* This is not exit, _exit or _Exit. */
2686 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2687 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2688 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2691 /* Argument is an interger zero. */
2692 return integer_zerop (gimple_call_arg (stmt
, 0));
2695 /* Try to guess whether the value of return means error code. */
2697 static enum br_predictor
2698 return_prediction (tree val
, enum prediction
*prediction
)
2702 return PRED_NO_PREDICTION
;
2703 /* Different heuristics for pointers and scalars. */
2704 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2706 /* NULL is usually not returned. */
2707 if (integer_zerop (val
))
2709 *prediction
= NOT_TAKEN
;
2710 return PRED_NULL_RETURN
;
2713 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2715 /* Negative return values are often used to indicate
2717 if (TREE_CODE (val
) == INTEGER_CST
2718 && tree_int_cst_sgn (val
) < 0)
2720 *prediction
= NOT_TAKEN
;
2721 return PRED_NEGATIVE_RETURN
;
2723 /* Constant return values seems to be commonly taken.
2724 Zero/one often represent booleans so exclude them from the
2726 if (TREE_CONSTANT (val
)
2727 && (!integer_zerop (val
) && !integer_onep (val
)))
2729 *prediction
= NOT_TAKEN
;
2730 return PRED_CONST_RETURN
;
2733 return PRED_NO_PREDICTION
;
2736 /* Return zero if phi result could have values other than -1, 0 or 1,
2737 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2738 values are used or likely. */
2741 zero_one_minusone (gphi
*phi
, int limit
)
2743 int phi_num_args
= gimple_phi_num_args (phi
);
2745 for (int i
= 0; i
< phi_num_args
; i
++)
2747 tree t
= PHI_ARG_DEF (phi
, i
);
2748 if (TREE_CODE (t
) != INTEGER_CST
)
2750 wide_int w
= wi::to_wide (t
);
2760 for (int i
= 0; i
< phi_num_args
; i
++)
2762 tree t
= PHI_ARG_DEF (phi
, i
);
2763 if (TREE_CODE (t
) == INTEGER_CST
)
2765 if (TREE_CODE (t
) != SSA_NAME
)
2767 gimple
*g
= SSA_NAME_DEF_STMT (t
);
2768 if (gimple_code (g
) == GIMPLE_PHI
&& limit
> 0)
2769 if (int r
= zero_one_minusone (as_a
<gphi
*> (g
), limit
- 1))
2774 if (!is_gimple_assign (g
))
2776 if (gimple_assign_cast_p (g
))
2778 tree rhs1
= gimple_assign_rhs1 (g
);
2779 if (TREE_CODE (rhs1
) != SSA_NAME
2780 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
2781 || TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2782 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2787 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g
)) != tcc_comparison
)
2794 /* Find the basic block with return expression and look up for possible
2795 return value trying to apply RETURN_PREDICTION heuristics. */
2797 apply_return_prediction (void)
2799 greturn
*return_stmt
= NULL
;
2803 int phi_num_args
, i
;
2804 enum br_predictor pred
;
2805 enum prediction direction
;
2808 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2810 gimple
*last
= last_stmt (e
->src
);
2812 && gimple_code (last
) == GIMPLE_RETURN
)
2814 return_stmt
= as_a
<greturn
*> (last
);
2820 return_val
= gimple_return_retval (return_stmt
);
2823 if (TREE_CODE (return_val
) != SSA_NAME
2824 || !SSA_NAME_DEF_STMT (return_val
)
2825 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2827 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2828 phi_num_args
= gimple_phi_num_args (phi
);
2829 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2831 /* Avoid the case where the function returns -1, 0 and 1 values and
2832 nothing else. Those could be qsort etc. comparison functions
2833 where the negative return isn't less probable than positive.
2834 For this require that the function returns at least -1 or 1
2835 or -1 and a boolean value or comparison result, so that functions
2836 returning just -1 and 0 are treated as if -1 represents error value. */
2837 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val
))
2838 && !TYPE_UNSIGNED (TREE_TYPE (return_val
))
2839 && TYPE_PRECISION (TREE_TYPE (return_val
)) > 1)
2840 if (int r
= zero_one_minusone (phi
, 3))
2841 if ((r
& (1 | 4)) == (1 | 4))
2844 /* Avoid the degenerate case where all return values form the function
2845 belongs to same category (ie they are all positive constants)
2846 so we can hardly say something about them. */
2847 for (i
= 1; i
< phi_num_args
; i
++)
2848 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2850 if (i
!= phi_num_args
)
2851 for (i
= 0; i
< phi_num_args
; i
++)
2853 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2854 if (pred
!= PRED_NO_PREDICTION
)
2855 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2860 /* Look for basic block that contains unlikely to happen events
2861 (such as noreturn calls) and mark all paths leading to execution
2862 of this basic blocks as unlikely. */
2865 tree_bb_level_predictions (void)
2868 bool has_return_edges
= false;
2872 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2873 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2875 has_return_edges
= true;
2879 apply_return_prediction ();
2881 FOR_EACH_BB_FN (bb
, cfun
)
2883 gimple_stmt_iterator gsi
;
2885 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2887 gimple
*stmt
= gsi_stmt (gsi
);
2890 if (is_gimple_call (stmt
))
2892 if (gimple_call_noreturn_p (stmt
)
2894 && !is_exit_with_zero_arg (stmt
))
2895 predict_paths_leading_to (bb
, PRED_NORETURN
,
2897 decl
= gimple_call_fndecl (stmt
);
2899 && lookup_attribute ("cold",
2900 DECL_ATTRIBUTES (decl
)))
2901 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2903 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2904 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2907 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2909 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2910 gimple_predict_outcome (stmt
));
2911 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2912 hints to callers. */
2918 /* Callback for hash_map::traverse, asserts that the pointer map is
2922 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2925 gcc_assert (!value
);
2929 /* Predict branch probabilities and estimate profile for basic block BB.
2930 When LOCAL_ONLY is set do not use any global properties of CFG. */
2933 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
2938 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2940 /* Look for block we are guarding (ie we dominate it,
2941 but it doesn't postdominate us). */
2942 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2944 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2945 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2947 gimple_stmt_iterator bi
;
2949 /* The call heuristic claims that a guarded function call
2950 is improbable. This is because such calls are often used
2951 to signal exceptional situations such as printing error
2953 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2956 gimple
*stmt
= gsi_stmt (bi
);
2957 if (is_gimple_call (stmt
)
2958 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
2959 /* Constant and pure calls are hardly used to signalize
2960 something exceptional. */
2961 && gimple_has_side_effects (stmt
))
2963 if (gimple_call_fndecl (stmt
))
2964 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2965 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
2966 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
2968 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
2974 tree_predict_by_opcode (bb
);
2977 /* Predict branch probabilities and estimate profile of the tree CFG.
2978 This function can be called from the loop optimizers to recompute
2979 the profile information.
2980 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2983 tree_estimate_probability (bool dry_run
)
2987 add_noreturn_fake_exit_edges ();
2988 connect_infinite_loops_to_exit ();
2989 /* We use loop_niter_by_eval, which requires that the loops have
2991 create_preheaders (CP_SIMPLE_PREHEADERS
);
2992 calculate_dominance_info (CDI_POST_DOMINATORS
);
2994 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2995 tree_bb_level_predictions ();
2996 record_loop_exits ();
2998 if (number_of_loops (cfun
) > 1)
3001 FOR_EACH_BB_FN (bb
, cfun
)
3002 tree_estimate_probability_bb (bb
, false);
3004 FOR_EACH_BB_FN (bb
, cfun
)
3005 combine_predictions_for_bb (bb
, dry_run
);
3008 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3010 delete bb_predictions
;
3011 bb_predictions
= NULL
;
3014 estimate_bb_frequencies (false);
3015 free_dominance_info (CDI_POST_DOMINATORS
);
3016 remove_fake_exit_edges ();
3019 /* Set edge->probability for each successor edge of BB. */
3021 tree_guess_outgoing_edge_probabilities (basic_block bb
)
3023 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
3024 tree_estimate_probability_bb (bb
, true);
3025 combine_predictions_for_bb (bb
, false);
3027 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
3028 delete bb_predictions
;
3029 bb_predictions
= NULL
;
3032 /* Predict edges to successors of CUR whose sources are not postdominated by
3033 BB by PRED and recurse to all postdominators. */
3036 predict_paths_for_bb (basic_block cur
, basic_block bb
,
3037 enum br_predictor pred
,
3038 enum prediction taken
,
3039 bitmap visited
, struct loop
*in_loop
= NULL
)
3045 /* If we exited the loop or CUR is unconditional in the loop, there is
3048 && (!flow_bb_inside_loop_p (in_loop
, cur
)
3049 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
3052 /* We are looking for all edges forming edge cut induced by
3053 set of all blocks postdominated by BB. */
3054 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
3055 if (e
->src
->index
>= NUM_FIXED_BLOCKS
3056 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
3062 /* Ignore fake edges and eh, we predict them as not taken anyway. */
3063 if (unlikely_executed_edge_p (e
))
3065 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
3067 /* See if there is an edge from e->src that is not abnormal
3068 and does not lead to BB and does not exit the loop. */
3069 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
3071 && !unlikely_executed_edge_p (e2
)
3072 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
3073 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
3079 /* If there is non-abnormal path leaving e->src, predict edge
3080 using predictor. Otherwise we need to look for paths
3083 The second may lead to infinite loop in the case we are predicitng
3084 regions that are only reachable by abnormal edges. We simply
3085 prevent visiting given BB twice. */
3088 if (!edge_predicted_by_p (e
, pred
, taken
))
3089 predict_edge_def (e
, pred
, taken
);
3091 else if (bitmap_set_bit (visited
, e
->src
->index
))
3092 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
3094 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
3096 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
3097 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
3100 /* Sets branch probabilities according to PREDiction and
3104 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
3105 enum prediction taken
, struct loop
*in_loop
)
3107 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3110 /* Like predict_paths_leading_to but take edge instead of basic block. */
3113 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
3114 enum prediction taken
, struct loop
*in_loop
)
3116 bool has_nonloop_edge
= false;
3120 basic_block bb
= e
->src
;
3121 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
3122 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
3123 && !unlikely_executed_edge_p (e
)
3124 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
3126 has_nonloop_edge
= true;
3129 if (!has_nonloop_edge
)
3131 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3134 predict_edge_def (e
, pred
, taken
);
3137 /* This is used to carry information about basic blocks. It is
3138 attached to the AUX field of the standard CFG block. */
3142 /* Estimated frequency of execution of basic_block. */
3145 /* To keep queue of basic blocks to process. */
3148 /* Number of predecessors we need to visit first. */
3152 /* Similar information for edges. */
3153 struct edge_prob_info
3155 /* In case edge is a loopback edge, the probability edge will be reached
3156 in case header is. Estimated number of iterations of the loop can be
3157 then computed as 1 / (1 - back_edge_prob). */
3158 sreal back_edge_prob
;
3159 /* True if the edge is a loopback edge in the natural loop. */
3160 unsigned int back_edge
:1;
3163 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3165 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3167 /* Helper function for estimate_bb_frequencies.
3168 Propagate the frequencies in blocks marked in
3169 TOVISIT, starting in HEAD. */
3172 propagate_freq (basic_block head
, bitmap tovisit
)
3181 /* For each basic block we need to visit count number of his predecessors
3182 we need to visit first. */
3183 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
3188 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3190 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3192 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3194 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3196 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3198 "Irreducible region hit, ignoring edge to %i->%i\n",
3199 e
->src
->index
, bb
->index
);
3201 BLOCK_INFO (bb
)->npredecessors
= count
;
3202 /* When function never returns, we will never process exit block. */
3203 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3204 bb
->count
= profile_count::zero ();
3207 BLOCK_INFO (head
)->frequency
= 1;
3209 for (bb
= head
; bb
; bb
= nextbb
)
3212 sreal cyclic_probability
= 0;
3213 sreal frequency
= 0;
3215 nextbb
= BLOCK_INFO (bb
)->next
;
3216 BLOCK_INFO (bb
)->next
= NULL
;
3218 /* Compute frequency of basic block. */
3222 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3223 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3224 || (e
->flags
& EDGE_DFS_BACK
));
3226 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3227 if (EDGE_INFO (e
)->back_edge
)
3229 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3231 else if (!(e
->flags
& EDGE_DFS_BACK
))
3233 /* frequency += (e->probability
3234 * BLOCK_INFO (e->src)->frequency /
3235 REG_BR_PROB_BASE); */
3237 /* FIXME: Graphite is producing edges with no profile. Once
3238 this is fixed, drop this. */
3239 sreal tmp
= e
->probability
.initialized_p () ?
3240 e
->probability
.to_reg_br_prob_base () : 0;
3241 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
3242 tmp
*= real_inv_br_prob_base
;
3246 if (cyclic_probability
== 0)
3248 BLOCK_INFO (bb
)->frequency
= frequency
;
3252 if (cyclic_probability
> real_almost_one
)
3253 cyclic_probability
= real_almost_one
;
3255 /* BLOCK_INFO (bb)->frequency = frequency
3256 / (1 - cyclic_probability) */
3258 cyclic_probability
= sreal (1) - cyclic_probability
;
3259 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
3263 bitmap_clear_bit (tovisit
, bb
->index
);
3265 e
= find_edge (bb
, head
);
3268 /* EDGE_INFO (e)->back_edge_prob
3269 = ((e->probability * BLOCK_INFO (bb)->frequency)
3270 / REG_BR_PROB_BASE); */
3272 /* FIXME: Graphite is producing edges with no profile. Once
3273 this is fixed, drop this. */
3274 sreal tmp
= e
->probability
.initialized_p () ?
3275 e
->probability
.to_reg_br_prob_base () : 0;
3276 tmp
*= BLOCK_INFO (bb
)->frequency
;
3277 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
3280 /* Propagate to successor blocks. */
3281 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3282 if (!(e
->flags
& EDGE_DFS_BACK
)
3283 && BLOCK_INFO (e
->dest
)->npredecessors
)
3285 BLOCK_INFO (e
->dest
)->npredecessors
--;
3286 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3291 BLOCK_INFO (last
)->next
= e
->dest
;
3299 /* Estimate frequencies in loops at same nest level. */
3302 estimate_loops_at_level (struct loop
*first_loop
)
3306 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3311 auto_bitmap tovisit
;
3313 estimate_loops_at_level (loop
->inner
);
3315 /* Find current loop back edge and mark it. */
3316 e
= loop_latch_edge (loop
);
3317 EDGE_INFO (e
)->back_edge
= 1;
3319 bbs
= get_loop_body (loop
);
3320 for (i
= 0; i
< loop
->num_nodes
; i
++)
3321 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3323 propagate_freq (loop
->header
, tovisit
);
3327 /* Propagates frequencies through structure of loops. */
3330 estimate_loops (void)
3332 auto_bitmap tovisit
;
3335 /* Start by estimating the frequencies in the loops. */
3336 if (number_of_loops (cfun
) > 1)
3337 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3339 /* Now propagate the frequencies through all the blocks. */
3340 FOR_ALL_BB_FN (bb
, cfun
)
3342 bitmap_set_bit (tovisit
, bb
->index
);
3344 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3347 /* Drop the profile for NODE to guessed, and update its frequency based on
3348 whether it is expected to be hot given the CALL_COUNT. */
3351 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3353 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3354 /* In the case where this was called by another function with a
3355 dropped profile, call_count will be 0. Since there are no
3356 non-zero call counts to this function, we don't know for sure
3357 whether it is hot, and therefore it will be marked normal below. */
3358 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3362 "Dropping 0 profile for %s. %s based on calls.\n",
3364 hot
? "Function is hot" : "Function is normal");
3365 /* We only expect to miss profiles for functions that are reached
3366 via non-zero call edges in cases where the function may have
3367 been linked from another module or library (COMDATs and extern
3368 templates). See the comments below for handle_missing_profiles.
3369 Also, only warn in cases where the missing counts exceed the
3370 number of training runs. In certain cases with an execv followed
3371 by a no-return call the profile for the no-return call is not
3372 dumped and there can be a mismatch. */
3373 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3374 && call_count
> profile_info
->runs
)
3376 if (flag_profile_correction
)
3380 "Missing counts for called function %s\n",
3381 node
->dump_name ());
3384 warning (0, "Missing counts for called function %s",
3385 node
->dump_name ());
3389 if (opt_for_fn (node
->decl
, flag_guess_branch_prob
))
3392 = !ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
.nonzero_p ();
3393 FOR_ALL_BB_FN (bb
, fn
)
3394 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3395 bb
->count
= bb
->count
.guessed_local ();
3396 fn
->cfg
->count_max
= fn
->cfg
->count_max
.guessed_local ();
3400 FOR_ALL_BB_FN (bb
, fn
)
3401 bb
->count
= profile_count::uninitialized ();
3402 fn
->cfg
->count_max
= profile_count::uninitialized ();
3405 struct cgraph_edge
*e
;
3406 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3407 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3408 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3409 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3410 node
->count
= ENTRY_BLOCK_PTR_FOR_FN (fn
)->count
;
3412 profile_status_for_fn (fn
)
3413 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3415 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3418 /* In the case of COMDAT routines, multiple object files will contain the same
3419 function and the linker will select one for the binary. In that case
3420 all the other copies from the profile instrument binary will be missing
3421 profile counts. Look for cases where this happened, due to non-zero
3422 call counts going to 0-count functions, and drop the profile to guessed
3423 so that we can use the estimated probabilities and avoid optimizing only
3426 The other case where the profile may be missing is when the routine
3427 is not going to be emitted to the object file, e.g. for "extern template"
3428 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3429 all other cases of non-zero calls to 0-count functions. */
3432 handle_missing_profiles (void)
3434 struct cgraph_node
*node
;
3435 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3436 auto_vec
<struct cgraph_node
*, 64> worklist
;
3438 /* See if 0 count function has non-0 count callers. In this case we
3439 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3440 FOR_EACH_DEFINED_FUNCTION (node
)
3442 struct cgraph_edge
*e
;
3443 profile_count call_count
= profile_count::zero ();
3444 gcov_type max_tp_first_run
= 0;
3445 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3447 if (node
->count
.ipa ().nonzero_p ())
3449 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3450 if (e
->count
.ipa ().initialized_p () && e
->count
.ipa () > 0)
3452 call_count
= call_count
+ e
->count
.ipa ();
3454 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3455 max_tp_first_run
= e
->caller
->tp_first_run
;
3458 /* If time profile is missing, let assign the maximum that comes from
3459 caller functions. */
3460 if (!node
->tp_first_run
&& max_tp_first_run
)
3461 node
->tp_first_run
= max_tp_first_run
+ 1;
3465 && (call_count
.apply_scale (unlikely_count_fraction
, 1)
3466 >= profile_info
->runs
))
3468 drop_profile (node
, call_count
);
3469 worklist
.safe_push (node
);
3473 /* Propagate the profile dropping to other 0-count COMDATs that are
3474 potentially called by COMDATs we already dropped the profile on. */
3475 while (worklist
.length () > 0)
3477 struct cgraph_edge
*e
;
3479 node
= worklist
.pop ();
3480 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3482 struct cgraph_node
*callee
= e
->callee
;
3483 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3485 if (!(e
->count
.ipa () == profile_count::zero ())
3486 && callee
->count
.ipa ().nonzero_p ())
3488 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3490 && profile_status_for_fn (fn
) == PROFILE_READ
)
3492 drop_profile (node
, profile_count::zero ());
3493 worklist
.safe_push (callee
);
3499 /* Convert counts measured by profile driven feedback to frequencies.
3500 Return nonzero iff there was any nonzero execution count. */
3503 update_max_bb_count (void)
3505 profile_count true_count_max
= profile_count::uninitialized ();
3508 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3509 true_count_max
= true_count_max
.max (bb
->count
);
3511 cfun
->cfg
->count_max
= true_count_max
;
3513 return true_count_max
.ipa ().nonzero_p ();
3516 /* Return true if function is likely to be expensive, so there is no point to
3517 optimize performance of prologue, epilogue or do inlining at the expense
3518 of code size growth. THRESHOLD is the limit of number of instructions
3519 function can execute at average to be still considered not expensive. */
3522 expensive_function_p (int threshold
)
3526 /* If profile was scaled in a way entry block has count 0, then the function
3527 is deifnitly taking a lot of time. */
3528 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3531 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN
3532 (cfun
)->count
.apply_scale (threshold
, 1);
3533 profile_count sum
= profile_count::zero ();
3534 FOR_EACH_BB_FN (bb
, cfun
)
3538 if (!bb
->count
.initialized_p ())
3541 fprintf (dump_file
, "Function is considered expensive because"
3542 " count of bb %i is not initialized\n", bb
->index
);
3546 FOR_BB_INSNS (bb
, insn
)
3547 if (active_insn_p (insn
))
3558 /* All basic blocks that are reachable only from unlikely basic blocks are
3562 propagate_unlikely_bbs_forward (void)
3564 auto_vec
<basic_block
, 64> worklist
;
3569 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3571 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3572 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3574 while (worklist
.length () > 0)
3576 bb
= worklist
.pop ();
3577 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3578 if (!(e
->count () == profile_count::zero ())
3579 && !(e
->dest
->count
== profile_count::zero ())
3582 e
->dest
->aux
= (void *)(size_t) 1;
3583 worklist
.safe_push (e
->dest
);
3588 FOR_ALL_BB_FN (bb
, cfun
)
3592 if (!(bb
->count
== profile_count::zero ())
3593 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3595 "Basic block %i is marked unlikely by forward prop\n",
3597 bb
->count
= profile_count::zero ();
3604 /* Determine basic blocks/edges that are known to be unlikely executed and set
3605 their counters to zero.
3606 This is done with first identifying obviously unlikely BBs/edges and then
3607 propagating in both directions. */
3610 determine_unlikely_bbs ()
3613 auto_vec
<basic_block
, 64> worklist
;
3617 FOR_EACH_BB_FN (bb
, cfun
)
3619 if (!(bb
->count
== profile_count::zero ())
3620 && unlikely_executed_bb_p (bb
))
3622 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3623 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3625 bb
->count
= profile_count::zero ();
3628 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3629 if (!(e
->probability
== profile_probability::never ())
3630 && unlikely_executed_edge_p (e
))
3632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3633 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3634 bb
->index
, e
->dest
->index
);
3635 e
->probability
= profile_probability::never ();
3638 gcc_checking_assert (!bb
->aux
);
3640 propagate_unlikely_bbs_forward ();
3642 auto_vec
<int, 64> nsuccs
;
3643 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
3644 FOR_ALL_BB_FN (bb
, cfun
)
3645 if (!(bb
->count
== profile_count::zero ())
3646 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3648 nsuccs
[bb
->index
] = 0;
3649 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3650 if (!(e
->probability
== profile_probability::never ())
3651 && !(e
->dest
->count
== profile_count::zero ()))
3652 nsuccs
[bb
->index
]++;
3653 if (!nsuccs
[bb
->index
])
3654 worklist
.safe_push (bb
);
3656 while (worklist
.length () > 0)
3658 bb
= worklist
.pop ();
3659 if (bb
->count
== profile_count::zero ())
3661 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3664 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3665 !gsi_end_p (gsi
); gsi_next (&gsi
))
3666 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3667 /* stmt_can_terminate_bb_p special cases noreturns because it
3668 assumes that fake edges are created. We want to know that
3669 noreturn alone does not imply BB to be unlikely. */
3670 || (is_gimple_call (gsi_stmt (gsi
))
3671 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3679 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3681 "Basic block %i is marked unlikely by backward prop\n",
3683 bb
->count
= profile_count::zero ();
3684 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3685 if (!(e
->probability
== profile_probability::never ()))
3687 if (!(e
->src
->count
== profile_count::zero ()))
3689 gcc_checking_assert (nsuccs
[e
->src
->index
] > 0);
3690 nsuccs
[e
->src
->index
]--;
3691 if (!nsuccs
[e
->src
->index
])
3692 worklist
.safe_push (e
->src
);
3696 /* Finally all edges from non-0 regions to 0 are unlikely. */
3697 FOR_ALL_BB_FN (bb
, cfun
)
3698 if (!(bb
->count
== profile_count::zero ()))
3699 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3700 if (!(e
->probability
== profile_probability::never ())
3701 && e
->dest
->count
== profile_count::zero ())
3703 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3704 fprintf (dump_file
, "Edge %i->%i is unlikely because "
3705 "it enters unlikely block\n",
3706 bb
->index
, e
->dest
->index
);
3707 e
->probability
= profile_probability::never ();
3709 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3710 cgraph_node::get (current_function_decl
)->count
= profile_count::zero ();
3713 /* Estimate and propagate basic block frequencies using the given branch
3714 probabilities. If FORCE is true, the frequencies are used to estimate
3715 the counts even when there are already non-zero profile counts. */
3718 estimate_bb_frequencies (bool force
)
3723 determine_unlikely_bbs ();
3725 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3726 || !update_max_bb_count ())
3728 static int real_values_initialized
= 0;
3730 if (!real_values_initialized
)
3732 real_values_initialized
= 1;
3733 real_br_prob_base
= REG_BR_PROB_BASE
;
3734 /* Scaling frequencies up to maximal profile count may result in
3735 frequent overflows especially when inlining loops.
3736 Small scalling results in unnecesary precision loss. Stay in
3737 the half of the (exponential) range. */
3738 real_bb_freq_max
= (uint64_t)1 << (profile_count::n_bits
/ 2);
3739 real_one_half
= sreal (1, -1);
3740 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3741 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3744 mark_dfs_back_edges ();
3746 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3747 profile_probability::always ();
3749 /* Set up block info for each basic block. */
3750 alloc_aux_for_blocks (sizeof (block_info
));
3751 alloc_aux_for_edges (sizeof (edge_prob_info
));
3752 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3757 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3759 /* FIXME: Graphite is producing edges with no profile. Once
3760 this is fixed, drop this. */
3761 if (e
->probability
.initialized_p ())
3762 EDGE_INFO (e
)->back_edge_prob
3763 = e
->probability
.to_reg_br_prob_base ();
3765 EDGE_INFO (e
)->back_edge_prob
= REG_BR_PROB_BASE
/ 2;
3766 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3770 /* First compute frequencies locally for each loop from innermost
3771 to outermost to examine frequencies for back edges. */
3775 FOR_EACH_BB_FN (bb
, cfun
)
3776 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3777 freq_max
= BLOCK_INFO (bb
)->frequency
;
3779 freq_max
= real_bb_freq_max
/ freq_max
;
3782 profile_count ipa_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ();
3783 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3784 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3786 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3787 profile_count count
= profile_count::from_gcov_type (tmp
.to_int ());
3789 /* If we have profile feedback in which this function was never
3790 executed, then preserve this info. */
3791 if (!(bb
->count
== profile_count::zero ()))
3792 bb
->count
= count
.guessed_local ().combine_with_ipa_count (ipa_count
);
3793 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3796 free_aux_for_blocks ();
3797 free_aux_for_edges ();
3799 compute_function_frequency ();
3802 /* Decide whether function is hot, cold or unlikely executed. */
3804 compute_function_frequency (void)
3807 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3809 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3810 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3811 node
->only_called_at_startup
= true;
3812 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3813 node
->only_called_at_exit
= true;
3815 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3817 int flags
= flags_from_decl_or_type (current_function_decl
);
3818 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ()
3819 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3820 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3823 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3824 warn_function_cold (current_function_decl
);
3826 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3828 node
->frequency
= NODE_FREQUENCY_HOT
;
3829 else if (flags
& ECF_NORETURN
)
3830 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3831 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3832 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3833 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3834 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3835 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3839 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3840 warn_function_cold (current_function_decl
);
3841 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3843 FOR_EACH_BB_FN (bb
, cfun
)
3845 if (maybe_hot_bb_p (cfun
, bb
))
3847 node
->frequency
= NODE_FREQUENCY_HOT
;
3850 if (!probably_never_executed_bb_p (cfun
, bb
))
3851 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3855 /* Build PREDICT_EXPR. */
3857 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3859 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3860 build_int_cst (integer_type_node
, predictor
));
3861 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3866 predictor_name (enum br_predictor predictor
)
3868 return predictor_info
[predictor
].name
;
3871 /* Predict branch probabilities and estimate profile of the tree CFG. */
3875 const pass_data pass_data_profile
=
3877 GIMPLE_PASS
, /* type */
3878 "profile_estimate", /* name */
3879 OPTGROUP_NONE
, /* optinfo_flags */
3880 TV_BRANCH_PROB
, /* tv_id */
3881 PROP_cfg
, /* properties_required */
3882 0, /* properties_provided */
3883 0, /* properties_destroyed */
3884 0, /* todo_flags_start */
3885 0, /* todo_flags_finish */
3888 class pass_profile
: public gimple_opt_pass
3891 pass_profile (gcc::context
*ctxt
)
3892 : gimple_opt_pass (pass_data_profile
, ctxt
)
3895 /* opt_pass methods: */
3896 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3897 virtual unsigned int execute (function
*);
3899 }; // class pass_profile
3902 pass_profile::execute (function
*fun
)
3906 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3909 loop_optimizer_init (LOOPS_NORMAL
);
3910 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3911 flow_loops_dump (dump_file
, NULL
, 0);
3913 mark_irreducible_loops ();
3915 nb_loops
= number_of_loops (fun
);
3919 tree_estimate_probability (false);
3924 loop_optimizer_finalize ();
3925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3926 gimple_dump_cfg (dump_file
, dump_flags
);
3927 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3928 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3929 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3932 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3933 if (loop
->header
->count
.initialized_p ())
3934 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
3936 (int)expected_loop_iterations_unbounded (loop
));
3944 make_pass_profile (gcc::context
*ctxt
)
3946 return new pass_profile (ctxt
);
3949 /* Return true when PRED predictor should be removed after early
3950 tree passes. Most of the predictors are beneficial to survive
3951 as early inlining can also distribute then into caller's bodies. */
3954 strip_predictor_early (enum br_predictor pred
)
3958 case PRED_TREE_EARLY_RETURN
:
3965 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3966 we no longer need. EARLY is set to true when called from early
3970 strip_predict_hints (function
*fun
, bool early
)
3975 bool changed
= false;
3977 FOR_EACH_BB_FN (bb
, fun
)
3979 gimple_stmt_iterator bi
;
3980 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3982 gimple
*stmt
= gsi_stmt (bi
);
3984 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3987 || strip_predictor_early (gimple_predict_predictor (stmt
)))
3989 gsi_remove (&bi
, true);
3994 else if (is_gimple_call (stmt
))
3996 tree fndecl
= gimple_call_fndecl (stmt
);
3999 && ((fndecl
!= NULL_TREE
4000 && fndecl_built_in_p (fndecl
, BUILT_IN_EXPECT
)
4001 && gimple_call_num_args (stmt
) == 2)
4002 || (fndecl
!= NULL_TREE
4003 && fndecl_built_in_p (fndecl
,
4004 BUILT_IN_EXPECT_WITH_PROBABILITY
)
4005 && gimple_call_num_args (stmt
) == 3)
4006 || (gimple_call_internal_p (stmt
)
4007 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
)))
4009 var
= gimple_call_lhs (stmt
);
4014 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
4015 gsi_replace (&bi
, ass_stmt
, true);
4019 gsi_remove (&bi
, true);
4027 return changed
? TODO_cleanup_cfg
: 0;
4032 const pass_data pass_data_strip_predict_hints
=
4034 GIMPLE_PASS
, /* type */
4035 "*strip_predict_hints", /* name */
4036 OPTGROUP_NONE
, /* optinfo_flags */
4037 TV_BRANCH_PROB
, /* tv_id */
4038 PROP_cfg
, /* properties_required */
4039 0, /* properties_provided */
4040 0, /* properties_destroyed */
4041 0, /* todo_flags_start */
4042 0, /* todo_flags_finish */
4045 class pass_strip_predict_hints
: public gimple_opt_pass
4048 pass_strip_predict_hints (gcc::context
*ctxt
)
4049 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
4052 /* opt_pass methods: */
4053 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
4054 void set_pass_param (unsigned int n
, bool param
)
4056 gcc_assert (n
== 0);
4060 virtual unsigned int execute (function
*);
4065 }; // class pass_strip_predict_hints
4068 pass_strip_predict_hints::execute (function
*fun
)
4070 return strip_predict_hints (fun
, early_p
);
4076 make_pass_strip_predict_hints (gcc::context
*ctxt
)
4078 return new pass_strip_predict_hints (ctxt
);
4081 /* Rebuild function frequencies. Passes are in general expected to
4082 maintain profile by hand, however in some cases this is not possible:
4083 for example when inlining several functions with loops freuqencies might run
4084 out of scale and thus needs to be recomputed. */
4087 rebuild_frequencies (void)
4089 timevar_push (TV_REBUILD_FREQUENCIES
);
4091 /* When the max bb count in the function is small, there is a higher
4092 chance that there were truncation errors in the integer scaling
4093 of counts by inlining and other optimizations. This could lead
4094 to incorrect classification of code as being cold when it isn't.
4095 In that case, force the estimation of bb counts/frequencies from the
4096 branch probabilities, rather than computing frequencies from counts,
4097 which may also lead to frequencies incorrectly reduced to 0. There
4098 is less precision in the probabilities, so we only do this for small
4100 cfun
->cfg
->count_max
= profile_count::uninitialized ();
4102 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
4103 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
4105 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
4107 loop_optimizer_init (0);
4108 add_noreturn_fake_exit_edges ();
4109 mark_irreducible_loops ();
4110 connect_infinite_loops_to_exit ();
4111 estimate_bb_frequencies (true);
4112 remove_fake_exit_edges ();
4113 loop_optimizer_finalize ();
4115 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
4116 update_max_bb_count ();
4117 else if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
4118 && !flag_guess_branch_prob
)
4122 timevar_pop (TV_REBUILD_FREQUENCIES
);
4125 /* Perform a dry run of the branch prediction pass and report comparsion of
4126 the predicted and real profile into the dump file. */
4129 report_predictor_hitrates (void)
4133 loop_optimizer_init (LOOPS_NORMAL
);
4134 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4135 flow_loops_dump (dump_file
, NULL
, 0);
4137 mark_irreducible_loops ();
4139 nb_loops
= number_of_loops (cfun
);
4143 tree_estimate_probability (true);
4148 loop_optimizer_finalize ();
4151 /* Force edge E to be cold.
4152 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4153 keep low probability to represent possible error in a guess. This is used
4154 i.e. in case we predict loop to likely iterate given number of times but
4155 we are not 100% sure.
4157 This function locally updates profile without attempt to keep global
4158 consistency which can not be reached in full generality without full profile
4159 rebuild from probabilities alone. Doing so is not necessarily a good idea
4160 because frequencies and counts may be more realistic then probabilities.
4162 In some cases (such as for elimination of early exits during full loop
4163 unrolling) the caller can ensure that profile will get consistent
4167 force_edge_cold (edge e
, bool impossible
)
4169 profile_count count_sum
= profile_count::zero ();
4170 profile_probability prob_sum
= profile_probability::never ();
4173 bool uninitialized_exit
= false;
4175 /* When branch probability guesses are not known, then do nothing. */
4176 if (!impossible
&& !e
->count ().initialized_p ())
4179 profile_probability goal
= (impossible
? profile_probability::never ()
4180 : profile_probability::very_unlikely ());
4182 /* If edge is already improbably or cold, just return. */
4183 if (e
->probability
<= goal
4184 && (!impossible
|| e
->count () == profile_count::zero ()))
4186 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4189 if (e
->flags
& EDGE_FAKE
)
4191 if (e2
->count ().initialized_p ())
4192 count_sum
+= e2
->count ();
4193 if (e2
->probability
.initialized_p ())
4194 prob_sum
+= e2
->probability
;
4196 uninitialized_exit
= true;
4199 /* If we are not guessing profiles but have some other edges out,
4200 just assume the control flow goes elsewhere. */
4201 if (uninitialized_exit
)
4202 e
->probability
= goal
;
4203 /* If there are other edges out of e->src, redistribute probabilitity
4205 else if (prob_sum
> profile_probability::never ())
4207 if (!(e
->probability
< goal
))
4208 e
->probability
= goal
;
4210 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
4212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4213 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
4214 "probability to other edges.\n",
4215 e
->src
->index
, e
->dest
->index
,
4216 impossible
? "impossible" : "cold");
4217 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4220 e2
->probability
/= prob_comp
;
4222 if (current_ir_type () != IR_GIMPLE
4223 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4224 update_br_prob_note (e
->src
);
4226 /* If all edges out of e->src are unlikely, the basic block itself
4230 if (prob_sum
== profile_probability::never ())
4231 e
->probability
= profile_probability::always ();
4235 e
->probability
= profile_probability::never ();
4236 /* If BB has some edges out that are not impossible, we can not
4237 assume that BB itself is. */
4240 if (current_ir_type () != IR_GIMPLE
4241 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4242 update_br_prob_note (e
->src
);
4243 if (e
->src
->count
== profile_count::zero ())
4245 if (count_sum
== profile_count::zero () && impossible
)
4248 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4250 else if (current_ir_type () == IR_GIMPLE
)
4251 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4252 !gsi_end_p (gsi
); gsi_next (&gsi
))
4254 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4260 /* FIXME: Implement RTL path. */
4265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4267 "Making bb %i impossible and dropping count to 0.\n",
4269 e
->src
->count
= profile_count::zero ();
4270 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4271 force_edge_cold (e2
, impossible
);
4276 /* If we did not adjusting, the source basic block has no likely edeges
4277 leaving other direction. In that case force that bb cold, too.
4278 This in general is difficult task to do, but handle special case when
4279 BB has only one predecestor. This is common case when we are updating
4280 after loop transforms. */
4281 if (!(prob_sum
> profile_probability::never ())
4282 && count_sum
== profile_count::zero ()
4283 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4284 > (impossible
? 0 : 1))
4286 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4288 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4289 impossible
? "impossible" : "cold");
4290 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4291 impossible
? 0 : 1);
4293 e
->src
->count
= profile_count::zero ();
4295 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4297 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4299 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4300 && maybe_hot_bb_p (cfun
, e
->src
))
4301 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4302 impossible
? "impossible" : "cold");
4308 namespace selftest
{
4310 /* Test that value range of predictor values defined in predict.def is
4311 within range (50, 100]. */
4313 struct branch_predictor
4319 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4322 test_prediction_value_range ()
4324 branch_predictor predictors
[] = {
4325 #include "predict.def"
4326 { NULL
, PROB_UNINITIALIZED
}
4329 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4331 if (predictors
[i
].probability
== PROB_UNINITIALIZED
)
4334 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4335 ASSERT_TRUE (p
>= 50 && p
<= 100);
4339 #undef DEF_PREDICTOR
4341 /* Run all of the selfests within this file. */
4346 test_prediction_value_range ();
4349 } // namespace selftest
4350 #endif /* CHECKING_P. */