1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2017 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
*);
96 /* Information we hold about each branch predictor.
97 Filled using information from predict.def. */
101 const char *const name
; /* Name used in the debugging dumps. */
102 const int hitrate
; /* Expected hitrate used by
103 predict_insn_def call. */
107 /* Use given predictor without Dempster-Shaffer theory if it matches
108 using first_match heuristics. */
109 #define PRED_FLAG_FIRST_MATCH 1
111 /* Recompute hitrate in percent to our representation. */
113 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
115 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
116 static const struct predictor_info predictor_info
[]= {
117 #include "predict.def"
119 /* Upper bound on predictors. */
124 static gcov_type min_count
= -1;
126 /* Determine the threshold for hot BB counts. */
129 get_hot_bb_threshold ()
131 gcov_working_set_t
*ws
;
134 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
136 min_count
= ws
->min_counter
;
141 /* Set the threshold for hot BB counts. */
144 set_hot_bb_threshold (gcov_type min
)
149 /* Return TRUE if frequency FREQ is considered to be hot. */
152 maybe_hot_count_p (struct function
*fun
, profile_count count
)
154 if (!count
.initialized_p ())
156 if (count
.ipa () == profile_count::zero ())
160 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
161 if (!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
163 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
165 if (node
->frequency
== NODE_FREQUENCY_HOT
)
168 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
170 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
171 && count
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
.apply_scale (2, 3)))
173 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
175 if (count
.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
), 1)
176 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
180 /* Code executed at most once is not hot. */
181 if (count
<= MAX (profile_info
? profile_info
->runs
: 1, 1))
183 return (count
.to_gcov_type () >= get_hot_bb_threshold ());
186 /* Return true in case BB can be CPU intensive and should be optimized
187 for maximal performance. */
190 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
192 gcc_checking_assert (fun
);
193 return maybe_hot_count_p (fun
, bb
->count
);
196 /* Return true in case BB can be CPU intensive and should be optimized
197 for maximal performance. */
200 maybe_hot_edge_p (edge e
)
202 return maybe_hot_count_p (cfun
, e
->count ());
205 /* Return true if profile COUNT and FREQUENCY, or function FUN static
206 node frequency reflects never being executed. */
209 probably_never_executed (struct function
*fun
,
212 gcc_checking_assert (fun
);
213 if (count
== profile_count::zero ())
215 if (count
.initialized_p () && profile_status_for_fn (fun
) == PROFILE_READ
)
217 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
218 if (count
.apply_scale (unlikely_count_fraction
, 1) >= profile_info
->runs
)
222 if ((!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
223 && (cgraph_node::get (fun
->decl
)->frequency
224 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
230 /* Return true in case BB is probably never executed. */
233 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
235 return probably_never_executed (fun
, bb
->count
);
239 /* Return true if E is unlikely executed for obvious reasons. */
242 unlikely_executed_edge_p (edge e
)
244 return (e
->count () == profile_count::zero ()
245 || e
->probability
== profile_probability::never ())
246 || (e
->flags
& (EDGE_EH
| EDGE_FAKE
));
249 /* Return true in case edge E is probably never executed. */
252 probably_never_executed_edge_p (struct function
*fun
, edge e
)
254 if (unlikely_executed_edge_p (e
))
256 return probably_never_executed (fun
, e
->count ());
259 /* Return true when current function should always be optimized for size. */
262 optimize_function_for_size_p (struct function
*fun
)
264 if (!fun
|| !fun
->decl
)
265 return optimize_size
;
266 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
267 return n
&& n
->optimize_for_size_p ();
270 /* Return true when current function should always be optimized for speed. */
273 optimize_function_for_speed_p (struct function
*fun
)
275 return !optimize_function_for_size_p (fun
);
278 /* Return the optimization type that should be used for the function FUN. */
281 function_optimization_type (struct function
*fun
)
283 return (optimize_function_for_speed_p (fun
)
285 : OPTIMIZE_FOR_SIZE
);
288 /* Return TRUE when BB should be optimized for size. */
291 optimize_bb_for_size_p (const_basic_block bb
)
293 return (optimize_function_for_size_p (cfun
)
294 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
297 /* Return TRUE when BB should be optimized for speed. */
300 optimize_bb_for_speed_p (const_basic_block bb
)
302 return !optimize_bb_for_size_p (bb
);
305 /* Return the optimization type that should be used for block BB. */
308 bb_optimization_type (const_basic_block bb
)
310 return (optimize_bb_for_speed_p (bb
)
312 : OPTIMIZE_FOR_SIZE
);
315 /* Return TRUE when BB should be optimized for size. */
318 optimize_edge_for_size_p (edge e
)
320 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
323 /* Return TRUE when BB should be optimized for speed. */
326 optimize_edge_for_speed_p (edge e
)
328 return !optimize_edge_for_size_p (e
);
331 /* Return TRUE when BB should be optimized for size. */
334 optimize_insn_for_size_p (void)
336 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
339 /* Return TRUE when BB should be optimized for speed. */
342 optimize_insn_for_speed_p (void)
344 return !optimize_insn_for_size_p ();
347 /* Return TRUE when LOOP should be optimized for size. */
350 optimize_loop_for_size_p (struct loop
*loop
)
352 return optimize_bb_for_size_p (loop
->header
);
355 /* Return TRUE when LOOP should be optimized for speed. */
358 optimize_loop_for_speed_p (struct loop
*loop
)
360 return optimize_bb_for_speed_p (loop
->header
);
363 /* Return TRUE when LOOP nest should be optimized for speed. */
366 optimize_loop_nest_for_speed_p (struct loop
*loop
)
368 struct loop
*l
= loop
;
369 if (optimize_loop_for_speed_p (loop
))
372 while (l
&& l
!= loop
)
374 if (optimize_loop_for_speed_p (l
))
382 while (l
!= loop
&& !l
->next
)
391 /* Return TRUE when LOOP nest should be optimized for size. */
394 optimize_loop_nest_for_size_p (struct loop
*loop
)
396 return !optimize_loop_nest_for_speed_p (loop
);
399 /* Return true when edge E is likely to be well predictable by branch
403 predictable_edge_p (edge e
)
405 if (!e
->probability
.initialized_p ())
407 if ((e
->probability
.to_reg_br_prob_base ()
408 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
409 || (REG_BR_PROB_BASE
- e
->probability
.to_reg_br_prob_base ()
410 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
416 /* Set RTL expansion for BB profile. */
419 rtl_profile_for_bb (basic_block bb
)
421 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
424 /* Set RTL expansion for edge profile. */
427 rtl_profile_for_edge (edge e
)
429 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
432 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
434 default_rtl_profile (void)
436 crtl
->maybe_hot_insn_p
= true;
439 /* Return true if the one of outgoing edges is already predicted by
443 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
446 if (!INSN_P (BB_END (bb
)))
448 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
449 if (REG_NOTE_KIND (note
) == REG_BR_PRED
450 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
455 /* Structure representing predictions in tree level. */
457 struct edge_prediction
{
458 struct edge_prediction
*ep_next
;
460 enum br_predictor ep_predictor
;
464 /* This map contains for a basic block the list of predictions for the
467 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
469 /* Return true if the one of outgoing edges is already predicted by
473 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
475 struct edge_prediction
*i
;
476 edge_prediction
**preds
= bb_predictions
->get (bb
);
481 for (i
= *preds
; i
; i
= i
->ep_next
)
482 if (i
->ep_predictor
== predictor
)
487 /* Return true if the one of outgoing edges is already predicted by
488 PREDICTOR for edge E predicted as TAKEN. */
491 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
493 struct edge_prediction
*i
;
494 basic_block bb
= e
->src
;
495 edge_prediction
**preds
= bb_predictions
->get (bb
);
499 int probability
= predictor_info
[(int) predictor
].hitrate
;
502 probability
= REG_BR_PROB_BASE
- probability
;
504 for (i
= *preds
; i
; i
= i
->ep_next
)
505 if (i
->ep_predictor
== predictor
507 && i
->ep_probability
== probability
)
512 /* Same predicate as above, working on edges. */
514 edge_probability_reliable_p (const_edge e
)
516 return e
->probability
.probably_reliable_p ();
519 /* Same predicate as edge_probability_reliable_p, working on notes. */
521 br_prob_note_reliable_p (const_rtx note
)
523 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
524 return profile_probability::from_reg_br_prob_note
525 (XINT (note
, 0)).probably_reliable_p ();
529 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
531 gcc_assert (any_condjump_p (insn
));
532 if (!flag_guess_branch_prob
)
535 add_reg_note (insn
, REG_BR_PRED
,
536 gen_rtx_CONCAT (VOIDmode
,
537 GEN_INT ((int) predictor
),
538 GEN_INT ((int) probability
)));
541 /* Predict insn by given predictor. */
544 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
545 enum prediction taken
)
547 int probability
= predictor_info
[(int) predictor
].hitrate
;
550 probability
= REG_BR_PROB_BASE
- probability
;
552 predict_insn (insn
, predictor
, probability
);
555 /* Predict edge E with given probability if possible. */
558 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
561 last_insn
= BB_END (e
->src
);
563 /* We can store the branch prediction information only about
564 conditional jumps. */
565 if (!any_condjump_p (last_insn
))
568 /* We always store probability of branching. */
569 if (e
->flags
& EDGE_FALLTHRU
)
570 probability
= REG_BR_PROB_BASE
- probability
;
572 predict_insn (last_insn
, predictor
, probability
);
575 /* Predict edge E with the given PROBABILITY. */
577 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
579 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
580 && EDGE_COUNT (e
->src
->succs
) > 1
581 && flag_guess_branch_prob
584 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
585 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
589 i
->ep_probability
= probability
;
590 i
->ep_predictor
= predictor
;
595 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
596 to the filter function. */
599 filter_predictions (edge_prediction
**preds
,
600 bool (*filter
) (edge_prediction
*, void *), void *data
)
607 struct edge_prediction
**prediction
= preds
;
608 struct edge_prediction
*next
;
612 if ((*filter
) (*prediction
, data
))
613 prediction
= &((*prediction
)->ep_next
);
616 next
= (*prediction
)->ep_next
;
624 /* Filter function predicate that returns true for a edge predicate P
625 if its edge is equal to DATA. */
628 equal_edge_p (edge_prediction
*p
, void *data
)
630 return p
->ep_edge
== (edge
)data
;
633 /* Remove all predictions on given basic block that are attached
636 remove_predictions_associated_with_edge (edge e
)
641 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
642 filter_predictions (preds
, equal_edge_p
, e
);
645 /* Clears the list of predictions stored for BB. */
648 clear_bb_predictions (basic_block bb
)
650 edge_prediction
**preds
= bb_predictions
->get (bb
);
651 struct edge_prediction
*pred
, *next
;
656 for (pred
= *preds
; pred
; pred
= next
)
658 next
= pred
->ep_next
;
664 /* Return true when we can store prediction on insn INSN.
665 At the moment we represent predictions only on conditional
666 jumps, not at computed jump or other complicated cases. */
668 can_predict_insn_p (const rtx_insn
*insn
)
670 return (JUMP_P (insn
)
671 && any_condjump_p (insn
)
672 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
675 /* Predict edge E by given predictor if possible. */
678 predict_edge_def (edge e
, enum br_predictor predictor
,
679 enum prediction taken
)
681 int probability
= predictor_info
[(int) predictor
].hitrate
;
684 probability
= REG_BR_PROB_BASE
- probability
;
686 predict_edge (e
, predictor
, probability
);
689 /* Invert all branch predictions or probability notes in the INSN. This needs
690 to be done each time we invert the condition used by the jump. */
693 invert_br_probabilities (rtx insn
)
697 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
698 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
699 XINT (note
, 0) = profile_probability::from_reg_br_prob_note
700 (XINT (note
, 0)).invert ().to_reg_br_prob_note ();
701 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
702 XEXP (XEXP (note
, 0), 1)
703 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
706 /* Dump information about the branch prediction to the output file. */
709 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
710 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
720 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
721 if (! (e
->flags
& EDGE_FALLTHRU
))
724 char edge_info_str
[128];
726 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
727 ep_edge
->dest
->index
);
729 edge_info_str
[0] = '\0';
731 fprintf (file
, " %s heuristics%s%s: %.1f%%",
732 predictor_info
[predictor
].name
,
733 edge_info_str
, reason_messages
[reason
],
734 probability
* 100.0 / REG_BR_PROB_BASE
);
736 if (bb
->count
.initialized_p ())
738 fprintf (file
, " exec ");
739 bb
->count
.dump (file
);
742 fprintf (file
, " hit ");
743 e
->count ().dump (file
);
744 fprintf (file
, " (%.1f%%)", e
->count ().to_gcov_type() * 100.0
745 / bb
->count
.to_gcov_type ());
749 fprintf (file
, "\n");
752 /* Return true if STMT is known to be unlikely executed. */
755 unlikely_executed_stmt_p (gimple
*stmt
)
757 if (!is_gimple_call (stmt
))
759 /* NORETURN attribute alone is not strong enough: exit() may be quite
760 likely executed once during program run. */
761 if (gimple_call_fntype (stmt
)
762 && lookup_attribute ("cold",
763 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
764 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
766 tree decl
= gimple_call_fndecl (stmt
);
769 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
770 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
773 cgraph_node
*n
= cgraph_node::get (decl
);
778 n
= n
->ultimate_alias_target (&avail
);
779 if (avail
< AVAIL_AVAILABLE
)
782 || n
->decl
== current_function_decl
)
784 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
787 /* Return true if BB is unlikely executed. */
790 unlikely_executed_bb_p (basic_block bb
)
792 if (bb
->count
== profile_count::zero ())
794 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
796 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
797 !gsi_end_p (gsi
); gsi_next (&gsi
))
799 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
801 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
807 /* We can not predict the probabilities of outgoing edges of bb. Set them
808 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
809 even probability for all edges not mentioned in the set. These edges
810 are given PROB_VERY_UNLIKELY probability. */
813 set_even_probabilities (basic_block bb
,
814 hash_set
<edge
> *unlikely_edges
= NULL
)
816 unsigned nedges
= 0, unlikely_count
= 0;
819 profile_probability all
= profile_probability::always ();
821 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
822 if (e
->probability
.initialized_p ())
823 all
-= e
->probability
;
824 else if (!unlikely_executed_edge_p (e
))
827 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
829 all
-= profile_probability::very_unlikely ();
834 /* Make the distribution even if all edges are unlikely. */
835 if (unlikely_count
== nedges
)
837 unlikely_edges
= NULL
;
841 unsigned c
= nedges
- unlikely_count
;
843 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
844 if (e
->probability
.initialized_p ())
846 else if (!unlikely_executed_edge_p (e
))
848 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
849 e
->probability
= profile_probability::very_unlikely ();
851 e
->probability
= all
.apply_scale (1, c
).guessed ();
854 e
->probability
= profile_probability::never ();
857 /* Add REG_BR_PROB note to JUMP with PROB. */
860 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
862 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
863 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
866 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
867 note if not already present. Remove now useless REG_BR_PRED notes. */
870 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
875 int best_probability
= PROB_EVEN
;
876 enum br_predictor best_predictor
= END_PREDICTORS
;
877 int combined_probability
= REG_BR_PROB_BASE
/ 2;
879 bool first_match
= false;
882 if (!can_predict_insn_p (insn
))
884 set_even_probabilities (bb
);
888 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
889 pnote
= ®_NOTES (insn
);
891 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
894 /* We implement "first match" heuristics and use probability guessed
895 by predictor with smallest index. */
896 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
897 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
899 enum br_predictor predictor
= ((enum br_predictor
)
900 INTVAL (XEXP (XEXP (note
, 0), 0)));
901 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
904 if (best_predictor
> predictor
905 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
906 best_probability
= probability
, best_predictor
= predictor
;
908 d
= (combined_probability
* probability
909 + (REG_BR_PROB_BASE
- combined_probability
)
910 * (REG_BR_PROB_BASE
- probability
));
912 /* Use FP math to avoid overflows of 32bit integers. */
914 /* If one probability is 0% and one 100%, avoid division by zero. */
915 combined_probability
= REG_BR_PROB_BASE
/ 2;
917 combined_probability
= (((double) combined_probability
) * probability
918 * REG_BR_PROB_BASE
/ d
+ 0.5);
921 /* Decide which heuristic to use. In case we didn't match anything,
922 use no_prediction heuristic, in case we did match, use either
923 first match or Dempster-Shaffer theory depending on the flags. */
925 if (best_predictor
!= END_PREDICTORS
)
929 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
930 combined_probability
, bb
);
934 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
935 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
937 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
938 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
942 combined_probability
= best_probability
;
943 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
947 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
949 enum br_predictor predictor
= ((enum br_predictor
)
950 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
951 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
953 dump_prediction (dump_file
, predictor
, probability
, bb
,
954 (!first_match
|| best_predictor
== predictor
)
955 ? REASON_NONE
: REASON_IGNORED
);
956 *pnote
= XEXP (*pnote
, 1);
959 pnote
= &XEXP (*pnote
, 1);
964 profile_probability p
965 = profile_probability::from_reg_br_prob_base (combined_probability
);
966 add_reg_br_prob_note (insn
, p
);
968 /* Save the prediction into CFG in case we are seeing non-degenerated
970 if (!single_succ_p (bb
))
972 BRANCH_EDGE (bb
)->probability
= p
;
973 FALLTHRU_EDGE (bb
)->probability
974 = BRANCH_EDGE (bb
)->probability
.invert ();
977 else if (!single_succ_p (bb
))
979 profile_probability prob
= profile_probability::from_reg_br_prob_note
980 (XINT (prob_note
, 0));
982 BRANCH_EDGE (bb
)->probability
= prob
;
983 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
986 single_succ_edge (bb
)->probability
= profile_probability::always ();
989 /* Edge prediction hash traits. */
991 struct predictor_hash
: pointer_hash
<edge_prediction
>
994 static inline hashval_t
hash (const edge_prediction
*);
995 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
998 /* Calculate hash value of an edge prediction P based on predictor and
999 normalized probability. */
1002 predictor_hash::hash (const edge_prediction
*p
)
1004 inchash::hash hstate
;
1005 hstate
.add_int (p
->ep_predictor
);
1007 int prob
= p
->ep_probability
;
1008 if (prob
> REG_BR_PROB_BASE
/ 2)
1009 prob
= REG_BR_PROB_BASE
- prob
;
1011 hstate
.add_int (prob
);
1013 return hstate
.end ();
1016 /* Return true whether edge predictions P1 and P2 use the same predictor and
1017 have equal (or opposed probability). */
1020 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1022 return (p1
->ep_predictor
== p2
->ep_predictor
1023 && (p1
->ep_probability
== p2
->ep_probability
1024 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1027 struct predictor_hash_traits
: predictor_hash
,
1028 typed_noop_remove
<edge_prediction
*> {};
1030 /* Return true if edge prediction P is not in DATA hash set. */
1033 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1035 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1036 return !remove
->contains (p
);
1039 /* Prune predictions for a basic block BB. Currently we do following
1042 1) remove duplicate prediction that is guessed with the same probability
1043 (different than 1/2) to both edge
1044 2) remove duplicates for a prediction that belongs with the same probability
1050 prune_predictions_for_bb (basic_block bb
)
1052 edge_prediction
**preds
= bb_predictions
->get (bb
);
1056 hash_table
<predictor_hash_traits
> s (13);
1057 hash_set
<edge_prediction
*> remove
;
1059 /* Step 1: identify predictors that should be removed. */
1060 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1062 edge_prediction
*existing
= s
.find (pred
);
1065 if (pred
->ep_edge
== existing
->ep_edge
1066 && pred
->ep_probability
== existing
->ep_probability
)
1068 /* Remove a duplicate predictor. */
1069 dump_prediction (dump_file
, pred
->ep_predictor
,
1070 pred
->ep_probability
, bb
,
1071 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1075 else if (pred
->ep_edge
!= existing
->ep_edge
1076 && pred
->ep_probability
== existing
->ep_probability
1077 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1079 /* Remove both predictors as they predict the same
1081 dump_prediction (dump_file
, existing
->ep_predictor
,
1082 pred
->ep_probability
, bb
,
1083 REASON_EDGE_PAIR_DUPLICATE
,
1085 dump_prediction (dump_file
, pred
->ep_predictor
,
1086 pred
->ep_probability
, bb
,
1087 REASON_EDGE_PAIR_DUPLICATE
,
1090 remove
.add (existing
);
1095 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1099 /* Step 2: Remove predictors. */
1100 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1104 /* Combine predictions into single probability and store them into CFG.
1105 Remove now useless prediction entries.
1106 If DRY_RUN is set, only produce dumps and do not modify profile. */
1109 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1111 int best_probability
= PROB_EVEN
;
1112 enum br_predictor best_predictor
= END_PREDICTORS
;
1113 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1115 bool first_match
= false;
1117 struct edge_prediction
*pred
;
1119 edge e
, first
= NULL
, second
= NULL
;
1122 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1123 if (!unlikely_executed_edge_p (e
))
1126 if (first
&& !second
)
1131 else if (!e
->probability
.initialized_p ())
1132 e
->probability
= profile_probability::never ();
1134 /* When there is no successor or only one choice, prediction is easy.
1136 When we have a basic block with more than 2 successors, the situation
1137 is more complicated as DS theory cannot be used literally.
1138 More precisely, let's assume we predicted edge e1 with probability p1,
1139 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1140 need to find probability of e.g. m1({b2}), which we don't know.
1141 The only approximation is to equally distribute 1-p1 to all edges
1144 According to numbers we've got from SPEC2006 benchark, there's only
1145 one interesting reliable predictor (noreturn call), which can be
1146 handled with a bit easier approach. */
1149 hash_set
<edge
> unlikely_edges (4);
1151 /* Identify all edges that have a probability close to very unlikely.
1152 Doing the approach for very unlikely doesn't worth for doing as
1153 there's no such probability in SPEC2006 benchmark. */
1154 edge_prediction
**preds
= bb_predictions
->get (bb
);
1156 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1157 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
)
1158 unlikely_edges
.add (pred
->ep_edge
);
1161 set_even_probabilities (bb
, &unlikely_edges
);
1162 clear_bb_predictions (bb
);
1165 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1166 if (unlikely_edges
.elements () == 0)
1168 "%i edges in bb %i predicted to even probabilities\n",
1173 "%i edges in bb %i predicted with some unlikely edges\n",
1175 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1176 if (!unlikely_executed_edge_p (e
))
1177 dump_prediction (dump_file
, PRED_COMBINED
,
1178 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1185 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1187 prune_predictions_for_bb (bb
);
1189 edge_prediction
**preds
= bb_predictions
->get (bb
);
1193 /* We implement "first match" heuristics and use probability guessed
1194 by predictor with smallest index. */
1195 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1197 enum br_predictor predictor
= pred
->ep_predictor
;
1198 int probability
= pred
->ep_probability
;
1200 if (pred
->ep_edge
!= first
)
1201 probability
= REG_BR_PROB_BASE
- probability
;
1204 /* First match heuristics would be widly confused if we predicted
1206 if (best_predictor
> predictor
1207 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1209 struct edge_prediction
*pred2
;
1210 int prob
= probability
;
1212 for (pred2
= (struct edge_prediction
*) *preds
;
1213 pred2
; pred2
= pred2
->ep_next
)
1214 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1216 int probability2
= pred2
->ep_probability
;
1218 if (pred2
->ep_edge
!= first
)
1219 probability2
= REG_BR_PROB_BASE
- probability2
;
1221 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1222 (probability2
< REG_BR_PROB_BASE
/ 2))
1225 /* If the same predictor later gave better result, go for it! */
1226 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1227 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1228 prob
= probability2
;
1231 best_probability
= prob
, best_predictor
= predictor
;
1234 d
= (combined_probability
* probability
1235 + (REG_BR_PROB_BASE
- combined_probability
)
1236 * (REG_BR_PROB_BASE
- probability
));
1238 /* Use FP math to avoid overflows of 32bit integers. */
1240 /* If one probability is 0% and one 100%, avoid division by zero. */
1241 combined_probability
= REG_BR_PROB_BASE
/ 2;
1243 combined_probability
= (((double) combined_probability
)
1245 * REG_BR_PROB_BASE
/ d
+ 0.5);
1249 /* Decide which heuristic to use. In case we didn't match anything,
1250 use no_prediction heuristic, in case we did match, use either
1251 first match or Dempster-Shaffer theory depending on the flags. */
1253 if (best_predictor
!= END_PREDICTORS
)
1257 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1261 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1262 !first_match
? REASON_NONE
: REASON_IGNORED
);
1264 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1265 first_match
? REASON_NONE
: REASON_IGNORED
);
1269 combined_probability
= best_probability
;
1270 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1274 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1276 enum br_predictor predictor
= pred
->ep_predictor
;
1277 int probability
= pred
->ep_probability
;
1279 dump_prediction (dump_file
, predictor
, probability
, bb
,
1280 (!first_match
|| best_predictor
== predictor
)
1281 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1284 clear_bb_predictions (bb
);
1286 if ((!bb
->count
.nonzero_p () || !first
->probability
.initialized_p ())
1290 = profile_probability::from_reg_br_prob_base (combined_probability
);
1291 second
->probability
= first
->probability
.invert ();
1295 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1296 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1298 T1 and T2 should be one of the following cases:
1299 1. T1 is SSA_NAME, T2 is NULL
1300 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1301 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1304 strips_small_constant (tree t1
, tree t2
)
1311 else if (TREE_CODE (t1
) == SSA_NAME
)
1313 else if (tree_fits_shwi_p (t1
))
1314 value
= tree_to_shwi (t1
);
1320 else if (tree_fits_shwi_p (t2
))
1321 value
= tree_to_shwi (t2
);
1322 else if (TREE_CODE (t2
) == SSA_NAME
)
1330 if (value
<= 4 && value
>= -4)
1336 /* Return the SSA_NAME in T or T's operands.
1337 Return NULL if SSA_NAME cannot be found. */
1340 get_base_value (tree t
)
1342 if (TREE_CODE (t
) == SSA_NAME
)
1345 if (!BINARY_CLASS_P (t
))
1348 switch (TREE_OPERAND_LENGTH (t
))
1351 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1353 return strips_small_constant (TREE_OPERAND (t
, 0),
1354 TREE_OPERAND (t
, 1));
1360 /* Check the compare STMT in LOOP. If it compares an induction
1361 variable to a loop invariant, return true, and save
1362 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1363 Otherwise return false and set LOOP_INVAIANT to NULL. */
1366 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1367 tree
*loop_invariant
,
1368 enum tree_code
*compare_code
,
1372 tree op0
, op1
, bound
, base
;
1374 enum tree_code code
;
1377 code
= gimple_cond_code (stmt
);
1378 *loop_invariant
= NULL
;
1394 op0
= gimple_cond_lhs (stmt
);
1395 op1
= gimple_cond_rhs (stmt
);
1397 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1398 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1400 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1402 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1404 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1405 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1407 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1408 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1411 if (integer_zerop (iv0
.step
))
1413 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1414 code
= invert_tree_comparison (code
, false);
1417 if (tree_fits_shwi_p (iv1
.step
))
1426 if (tree_fits_shwi_p (iv0
.step
))
1432 if (TREE_CODE (bound
) != INTEGER_CST
)
1433 bound
= get_base_value (bound
);
1436 if (TREE_CODE (base
) != INTEGER_CST
)
1437 base
= get_base_value (base
);
1441 *loop_invariant
= bound
;
1442 *compare_code
= code
;
1444 *loop_iv_base
= base
;
1448 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1451 expr_coherent_p (tree t1
, tree t2
)
1454 tree ssa_name_1
= NULL
;
1455 tree ssa_name_2
= NULL
;
1457 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1458 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1463 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1465 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1468 /* Check to see if t1 is expressed/defined with t2. */
1469 stmt
= SSA_NAME_DEF_STMT (t1
);
1470 gcc_assert (stmt
!= NULL
);
1471 if (is_gimple_assign (stmt
))
1473 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1474 if (ssa_name_1
&& ssa_name_1
== t2
)
1478 /* Check to see if t2 is expressed/defined with t1. */
1479 stmt
= SSA_NAME_DEF_STMT (t2
);
1480 gcc_assert (stmt
!= NULL
);
1481 if (is_gimple_assign (stmt
))
1483 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1484 if (ssa_name_2
&& ssa_name_2
== t1
)
1488 /* Compare if t1 and t2's def_stmts are identical. */
1489 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1495 /* Return true if E is predicted by one of loop heuristics. */
1498 predicted_by_loop_heuristics_p (basic_block bb
)
1500 struct edge_prediction
*i
;
1501 edge_prediction
**preds
= bb_predictions
->get (bb
);
1506 for (i
= *preds
; i
; i
= i
->ep_next
)
1507 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1508 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1509 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1510 || i
->ep_predictor
== PRED_LOOP_EXIT
1511 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1512 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1517 /* Predict branch probability of BB when BB contains a branch that compares
1518 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1519 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1522 for (int i = 0; i < bound; i++) {
1529 In this loop, we will predict the branch inside the loop to be taken. */
1532 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1533 tree loop_bound_var
,
1534 tree loop_iv_base_var
,
1535 enum tree_code loop_bound_code
,
1536 int loop_bound_step
)
1539 tree compare_var
, compare_base
;
1540 enum tree_code compare_code
;
1541 tree compare_step_var
;
1545 if (predicted_by_loop_heuristics_p (bb
))
1548 stmt
= last_stmt (bb
);
1549 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1551 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1558 /* Find the taken edge. */
1559 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1560 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1563 /* When comparing an IV to a loop invariant, NE is more likely to be
1564 taken while EQ is more likely to be not-taken. */
1565 if (compare_code
== NE_EXPR
)
1567 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1570 else if (compare_code
== EQ_EXPR
)
1572 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1576 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1579 /* If loop bound, base and compare bound are all constants, we can
1580 calculate the probability directly. */
1581 if (tree_fits_shwi_p (loop_bound_var
)
1582 && tree_fits_shwi_p (compare_var
)
1583 && tree_fits_shwi_p (compare_base
))
1586 bool overflow
, overall_overflow
= false;
1587 widest_int compare_count
, tem
;
1589 /* (loop_bound - base) / compare_step */
1590 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1591 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1592 overall_overflow
|= overflow
;
1593 widest_int loop_count
= wi::div_trunc (tem
,
1594 wi::to_widest (compare_step_var
),
1596 overall_overflow
|= overflow
;
1598 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1599 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1601 /* (loop_bound - compare_bound) / compare_step */
1602 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1603 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1604 overall_overflow
|= overflow
;
1605 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1607 overall_overflow
|= overflow
;
1611 /* (compare_bound - base) / compare_step */
1612 tem
= wi::sub (wi::to_widest (compare_var
),
1613 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1614 overall_overflow
|= overflow
;
1615 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1617 overall_overflow
|= overflow
;
1619 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1621 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1623 if (wi::neg_p (compare_count
))
1625 if (wi::neg_p (loop_count
))
1627 if (loop_count
== 0)
1629 else if (wi::cmps (compare_count
, loop_count
) == 1)
1630 probability
= REG_BR_PROB_BASE
;
1633 tem
= compare_count
* REG_BR_PROB_BASE
;
1634 tem
= wi::udiv_trunc (tem
, loop_count
);
1635 probability
= tem
.to_uhwi ();
1638 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1639 if (!overall_overflow
)
1640 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1645 if (expr_coherent_p (loop_bound_var
, compare_var
))
1647 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1648 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1649 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1650 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1651 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1652 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1653 else if (loop_bound_code
== NE_EXPR
)
1655 /* If the loop backedge condition is "(i != bound)", we do
1656 the comparison based on the step of IV:
1657 * step < 0 : backedge condition is like (i > bound)
1658 * step > 0 : backedge condition is like (i < bound) */
1659 gcc_assert (loop_bound_step
!= 0);
1660 if (loop_bound_step
> 0
1661 && (compare_code
== LT_EXPR
1662 || compare_code
== LE_EXPR
))
1663 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1664 else if (loop_bound_step
< 0
1665 && (compare_code
== GT_EXPR
1666 || compare_code
== GE_EXPR
))
1667 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1669 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1672 /* The branch is predicted not-taken if loop_bound_code is
1673 opposite with compare_code. */
1674 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1676 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1679 for (i = s; i < h; i++)
1681 The branch should be predicted taken. */
1682 if (loop_bound_step
> 0
1683 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1684 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1685 else if (loop_bound_step
< 0
1686 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1687 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1689 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1693 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1694 exits are resulted from short-circuit conditions that will generate an
1697 if (foo() || global > 10)
1700 This will be translated into:
1705 if foo() goto BB6 else goto BB5
1707 if global > 10 goto BB6 else goto BB7
1711 iftmp = (PHI 0(BB5), 1(BB6))
1712 if iftmp == 1 goto BB8 else goto BB3
1714 outside of the loop...
1716 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1717 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1718 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1719 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1722 predict_extra_loop_exits (edge exit_edge
)
1725 bool check_value_one
;
1726 gimple
*lhs_def_stmt
;
1728 tree cmp_rhs
, cmp_lhs
;
1732 last
= last_stmt (exit_edge
->src
);
1735 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1739 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1740 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1741 if (!TREE_CONSTANT (cmp_rhs
)
1742 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1744 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1747 /* If check_value_one is true, only the phi_args with value '1' will lead
1748 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1750 check_value_one
= (((integer_onep (cmp_rhs
))
1751 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1752 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1754 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1758 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1762 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1766 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1767 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1769 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1771 if ((check_value_one
^ integer_onep (val
)) == 1)
1773 if (EDGE_COUNT (e
->src
->succs
) != 1)
1775 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1779 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1780 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1785 /* Predict edge probabilities by exploiting loop structure. */
1788 predict_loops (void)
1792 hash_set
<struct loop
*> with_recursion(10);
1794 FOR_EACH_BB_FN (bb
, cfun
)
1796 gimple_stmt_iterator gsi
;
1799 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1800 if (is_gimple_call (gsi_stmt (gsi
))
1801 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1802 && recursive_call_p (current_function_decl
, decl
))
1804 loop
= bb
->loop_father
;
1805 while (loop
&& !with_recursion
.add (loop
))
1806 loop
= loop_outer (loop
);
1810 /* Try to predict out blocks in a loop that are not part of a
1812 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1814 basic_block bb
, *bbs
;
1815 unsigned j
, n_exits
= 0;
1817 struct tree_niter_desc niter_desc
;
1819 struct nb_iter_bound
*nb_iter
;
1820 enum tree_code loop_bound_code
= ERROR_MARK
;
1821 tree loop_bound_step
= NULL
;
1822 tree loop_bound_var
= NULL
;
1823 tree loop_iv_base
= NULL
;
1825 bool recursion
= with_recursion
.contains (loop
);
1827 exits
= get_loop_exit_edges (loop
);
1828 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1829 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1838 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1839 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1840 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1841 && max_loop_iterations_int (loop
) >= 0)
1844 "Loop %d iterates at most %i times.\n", loop
->num
,
1845 (int)max_loop_iterations_int (loop
));
1847 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1848 && likely_max_loop_iterations_int (loop
) >= 0)
1850 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1851 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1854 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1857 HOST_WIDE_INT nitercst
;
1858 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1860 enum br_predictor predictor
;
1863 if (unlikely_executed_edge_p (ex
)
1864 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
1866 /* Loop heuristics do not expect exit conditional to be inside
1867 inner loop. We predict from innermost to outermost loop. */
1868 if (predicted_by_loop_heuristics_p (ex
->src
))
1870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1871 fprintf (dump_file
, "Skipping exit %i->%i because "
1872 "it is already predicted.\n",
1873 ex
->src
->index
, ex
->dest
->index
);
1876 predict_extra_loop_exits (ex
);
1878 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1879 niter
= niter_desc
.niter
;
1880 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1881 niter
= loop_niter_by_eval (loop
, ex
);
1882 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1883 && TREE_CODE (niter
) == INTEGER_CST
)
1885 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1886 ex
->src
->index
, ex
->dest
->index
,
1888 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1889 fprintf (dump_file
, " times.\n");
1892 if (TREE_CODE (niter
) == INTEGER_CST
)
1894 if (tree_fits_uhwi_p (niter
)
1896 && compare_tree_int (niter
, max
- 1) == -1)
1897 nitercst
= tree_to_uhwi (niter
) + 1;
1900 predictor
= PRED_LOOP_ITERATIONS
;
1902 /* If we have just one exit and we can derive some information about
1903 the number of iterations of the loop from the statements inside
1904 the loop, use it to predict this exit. */
1905 else if (n_exits
== 1
1906 && estimated_stmt_executions (loop
, &nit
))
1908 if (wi::gtu_p (nit
, max
))
1911 nitercst
= nit
.to_shwi ();
1912 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1914 /* If we have likely upper bound, trust it for very small iteration
1915 counts. Such loops would otherwise get mispredicted by standard
1916 LOOP_EXIT heuristics. */
1917 else if (n_exits
== 1
1918 && likely_max_stmt_executions (loop
, &nit
)
1920 RDIV (REG_BR_PROB_BASE
,
1924 ? PRED_LOOP_EXIT_WITH_RECURSION
1925 : PRED_LOOP_EXIT
].hitrate
)))
1927 nitercst
= nit
.to_shwi ();
1928 predictor
= PRED_LOOP_ITERATIONS_MAX
;
1932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1933 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
1934 ex
->src
->index
, ex
->dest
->index
);
1938 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1939 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
1940 (int)nitercst
, predictor_info
[predictor
].name
);
1941 /* If the prediction for number of iterations is zero, do not
1942 predict the exit edges. */
1946 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
1947 predict_edge (ex
, predictor
, probability
);
1951 /* Find information about loop bound variables. */
1952 for (nb_iter
= loop
->bounds
; nb_iter
;
1953 nb_iter
= nb_iter
->next
)
1955 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1957 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1960 if (!stmt
&& last_stmt (loop
->header
)
1961 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1962 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1964 is_comparison_with_loop_invariant_p (stmt
, loop
,
1970 bbs
= get_loop_body (loop
);
1972 for (j
= 0; j
< loop
->num_nodes
; j
++)
1979 /* Bypass loop heuristics on continue statement. These
1980 statements construct loops via "non-loop" constructs
1981 in the source language and are better to be handled
1983 if (predicted_by_p (bb
, PRED_CONTINUE
))
1985 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1986 fprintf (dump_file
, "BB %i predicted by continue.\n",
1991 /* If we already used more reliable loop exit predictors, do not
1992 bother with PRED_LOOP_EXIT. */
1993 if (!predicted_by_loop_heuristics_p (bb
))
1995 /* For loop with many exits we don't want to predict all exits
1996 with the pretty large probability, because if all exits are
1997 considered in row, the loop would be predicted to iterate
1998 almost never. The code to divide probability by number of
1999 exits is very rough. It should compute the number of exits
2000 taken in each patch through function (not the overall number
2001 of exits that might be a lot higher for loops with wide switch
2002 statements in them) and compute n-th square root.
2004 We limit the minimal probability by 2% to avoid
2005 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2006 as this was causing regression in perl benchmark containing such
2009 int probability
= ((REG_BR_PROB_BASE
2012 ? PRED_LOOP_EXIT_WITH_RECURSION
2013 : PRED_LOOP_EXIT
].hitrate
)
2015 if (probability
< HITRATE (2))
2016 probability
= HITRATE (2);
2017 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2018 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2019 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2021 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2023 "Predicting exit %i->%i with prob %i.\n",
2024 e
->src
->index
, e
->dest
->index
, probability
);
2026 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2027 : PRED_LOOP_EXIT
, probability
);
2031 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2033 tree_to_shwi (loop_bound_step
));
2036 /* In the following code
2041 guess that cond is unlikely. */
2042 if (loop_outer (loop
)->num
)
2044 basic_block bb
= NULL
;
2045 edge preheader_edge
= loop_preheader_edge (loop
);
2047 if (single_pred_p (preheader_edge
->src
)
2048 && single_succ_p (preheader_edge
->src
))
2049 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2051 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2052 /* Pattern match fortran loop preheader:
2053 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2054 _17 = (logical(kind=4)) _16;
2060 Loop guard branch prediction says nothing about duplicated loop
2061 headers produced by fortran frontend and in this case we want
2062 to predict paths leading to this preheader. */
2065 && gimple_code (stmt
) == GIMPLE_COND
2066 && gimple_cond_code (stmt
) == NE_EXPR
2067 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2068 && integer_zerop (gimple_cond_rhs (stmt
)))
2070 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2071 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2072 && gimple_expr_code (call_stmt
) == NOP_EXPR
2073 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2074 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2075 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2076 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2077 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2078 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2079 == PRED_FORTRAN_LOOP_PREHEADER
)
2080 bb
= preheader_edge
->src
;
2084 if (!dominated_by_p (CDI_DOMINATORS
,
2085 loop_outer (loop
)->latch
, loop
->header
))
2086 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2088 ? PRED_LOOP_GUARD_WITH_RECURSION
2095 if (!dominated_by_p (CDI_DOMINATORS
,
2096 loop_outer (loop
)->latch
, bb
))
2097 predict_paths_leading_to (bb
,
2099 ? PRED_LOOP_GUARD_WITH_RECURSION
2106 /* Free basic blocks from get_loop_body. */
2111 /* Attempt to predict probabilities of BB outgoing edges using local
2114 bb_estimate_probability_locally (basic_block bb
)
2116 rtx_insn
*last_insn
= BB_END (bb
);
2119 if (! can_predict_insn_p (last_insn
))
2121 cond
= get_condition (last_insn
, NULL
, false, false);
2125 /* Try "pointer heuristic."
2126 A comparison ptr == 0 is predicted as false.
2127 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2128 if (COMPARISON_P (cond
)
2129 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2130 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2132 if (GET_CODE (cond
) == EQ
)
2133 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2134 else if (GET_CODE (cond
) == NE
)
2135 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2139 /* Try "opcode heuristic."
2140 EQ tests are usually false and NE tests are usually true. Also,
2141 most quantities are positive, so we can make the appropriate guesses
2142 about signed comparisons against zero. */
2143 switch (GET_CODE (cond
))
2146 /* Unconditional branch. */
2147 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2148 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2153 /* Floating point comparisons appears to behave in a very
2154 unpredictable way because of special role of = tests in
2156 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2158 /* Comparisons with 0 are often used for booleans and there is
2159 nothing useful to predict about them. */
2160 else if (XEXP (cond
, 1) == const0_rtx
2161 || XEXP (cond
, 0) == const0_rtx
)
2164 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2169 /* Floating point comparisons appears to behave in a very
2170 unpredictable way because of special role of = tests in
2172 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2174 /* Comparisons with 0 are often used for booleans and there is
2175 nothing useful to predict about them. */
2176 else if (XEXP (cond
, 1) == const0_rtx
2177 || XEXP (cond
, 0) == const0_rtx
)
2180 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2184 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2188 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2193 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2194 || XEXP (cond
, 1) == constm1_rtx
)
2195 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2200 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2201 || XEXP (cond
, 1) == constm1_rtx
)
2202 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2210 /* Set edge->probability for each successor edge of BB. */
2212 guess_outgoing_edge_probabilities (basic_block bb
)
2214 bb_estimate_probability_locally (bb
);
2215 combine_predictions_for_insn (BB_END (bb
), bb
);
2218 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
2220 /* Helper function for expr_expected_value. */
2223 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2224 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
2229 *predictor
= PRED_UNCONDITIONAL
;
2231 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2233 if (TREE_CONSTANT (op0
))
2236 if (code
== IMAGPART_EXPR
)
2238 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2240 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2241 if (is_gimple_call (def
)
2242 && gimple_call_internal_p (def
)
2243 && (gimple_call_internal_fn (def
)
2244 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2246 /* Assume that any given atomic operation has low contention,
2247 and thus the compare-and-swap operation succeeds. */
2249 *predictor
= PRED_COMPARE_AND_SWAP
;
2250 return build_one_cst (TREE_TYPE (op0
));
2255 if (code
!= SSA_NAME
)
2258 def
= SSA_NAME_DEF_STMT (op0
);
2260 /* If we were already here, break the infinite cycle. */
2261 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2264 if (gimple_code (def
) == GIMPLE_PHI
)
2266 /* All the arguments of the PHI node must have the same constant
2268 int i
, n
= gimple_phi_num_args (def
);
2269 tree val
= NULL
, new_val
;
2271 for (i
= 0; i
< n
; i
++)
2273 tree arg
= PHI_ARG_DEF (def
, i
);
2274 enum br_predictor predictor2
;
2276 /* If this PHI has itself as an argument, we cannot
2277 determine the string length of this argument. However,
2278 if we can find an expected constant value for the other
2279 PHI args then we can still be sure that this is
2280 likely a constant. So be optimistic and just
2281 continue with the next argument. */
2282 if (arg
== PHI_RESULT (def
))
2285 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
2287 /* It is difficult to combine value predictors. Simply assume
2288 that later predictor is weaker and take its prediction. */
2289 if (predictor
&& *predictor
< predictor2
)
2290 *predictor
= predictor2
;
2295 else if (!operand_equal_p (val
, new_val
, false))
2300 if (is_gimple_assign (def
))
2302 if (gimple_assign_lhs (def
) != op0
)
2305 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2306 gimple_assign_rhs1 (def
),
2307 gimple_assign_rhs_code (def
),
2308 gimple_assign_rhs2 (def
),
2309 visited
, predictor
);
2312 if (is_gimple_call (def
))
2314 tree decl
= gimple_call_fndecl (def
);
2317 if (gimple_call_internal_p (def
)
2318 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2320 gcc_assert (gimple_call_num_args (def
) == 3);
2321 tree val
= gimple_call_arg (def
, 0);
2322 if (TREE_CONSTANT (val
))
2326 tree val2
= gimple_call_arg (def
, 2);
2327 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2328 && tree_fits_uhwi_p (val2
)
2329 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2330 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2332 return gimple_call_arg (def
, 1);
2336 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2337 switch (DECL_FUNCTION_CODE (decl
))
2339 case BUILT_IN_EXPECT
:
2342 if (gimple_call_num_args (def
) != 2)
2344 val
= gimple_call_arg (def
, 0);
2345 if (TREE_CONSTANT (val
))
2348 *predictor
= PRED_BUILTIN_EXPECT
;
2349 return gimple_call_arg (def
, 1);
2352 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2353 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2354 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2355 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2356 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2357 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2358 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2359 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2360 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2361 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2362 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2363 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2364 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2365 /* Assume that any given atomic operation has low contention,
2366 and thus the compare-and-swap operation succeeds. */
2368 *predictor
= PRED_COMPARE_AND_SWAP
;
2369 return boolean_true_node
;
2378 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2381 enum br_predictor predictor2
;
2382 op0
= expr_expected_value (op0
, visited
, predictor
);
2385 op1
= expr_expected_value (op1
, visited
, &predictor2
);
2386 if (predictor
&& *predictor
< predictor2
)
2387 *predictor
= predictor2
;
2390 res
= fold_build2 (code
, type
, op0
, op1
);
2391 if (TREE_CONSTANT (res
))
2395 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2398 op0
= expr_expected_value (op0
, visited
, predictor
);
2401 res
= fold_build1 (code
, type
, op0
);
2402 if (TREE_CONSTANT (res
))
2409 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2410 The function is used by builtin_expect branch predictor so the evidence
2411 must come from this construct and additional possible constant folding.
2413 We may want to implement more involved value guess (such as value range
2414 propagation based prediction), but such tricks shall go to new
2418 expr_expected_value (tree expr
, bitmap visited
,
2419 enum br_predictor
*predictor
)
2421 enum tree_code code
;
2424 if (TREE_CONSTANT (expr
))
2427 *predictor
= PRED_UNCONDITIONAL
;
2431 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2432 return expr_expected_value_1 (TREE_TYPE (expr
),
2433 op0
, code
, op1
, visited
, predictor
);
2436 /* Predict using opcode of the last statement in basic block. */
2438 tree_predict_by_opcode (basic_block bb
)
2440 gimple
*stmt
= last_stmt (bb
);
2447 enum br_predictor predictor
;
2449 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2451 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2452 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2454 op0
= gimple_cond_lhs (stmt
);
2455 op1
= gimple_cond_rhs (stmt
);
2456 cmp
= gimple_cond_code (stmt
);
2457 type
= TREE_TYPE (op0
);
2458 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2460 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2462 if (predictor
== PRED_BUILTIN_EXPECT
)
2464 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2466 gcc_assert (percent
>= 0 && percent
<= 100);
2467 if (integer_zerop (val
))
2468 percent
= 100 - percent
;
2469 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2472 predict_edge_def (then_edge
, predictor
,
2473 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2475 /* Try "pointer heuristic."
2476 A comparison ptr == 0 is predicted as false.
2477 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2478 if (POINTER_TYPE_P (type
))
2481 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2482 else if (cmp
== NE_EXPR
)
2483 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2487 /* Try "opcode heuristic."
2488 EQ tests are usually false and NE tests are usually true. Also,
2489 most quantities are positive, so we can make the appropriate guesses
2490 about signed comparisons against zero. */
2495 /* Floating point comparisons appears to behave in a very
2496 unpredictable way because of special role of = tests in
2498 if (FLOAT_TYPE_P (type
))
2500 /* Comparisons with 0 are often used for booleans and there is
2501 nothing useful to predict about them. */
2502 else if (integer_zerop (op0
) || integer_zerop (op1
))
2505 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2510 /* Floating point comparisons appears to behave in a very
2511 unpredictable way because of special role of = tests in
2513 if (FLOAT_TYPE_P (type
))
2515 /* Comparisons with 0 are often used for booleans and there is
2516 nothing useful to predict about them. */
2517 else if (integer_zerop (op0
)
2518 || integer_zerop (op1
))
2521 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2525 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2528 case UNORDERED_EXPR
:
2529 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2534 if (integer_zerop (op1
)
2535 || integer_onep (op1
)
2536 || integer_all_onesp (op1
)
2539 || real_minus_onep (op1
))
2540 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2545 if (integer_zerop (op1
)
2546 || integer_onep (op1
)
2547 || integer_all_onesp (op1
)
2550 || real_minus_onep (op1
))
2551 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2559 /* Returns TRUE if the STMT is exit(0) like statement. */
2562 is_exit_with_zero_arg (const gimple
*stmt
)
2564 /* This is not exit, _exit or _Exit. */
2565 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2566 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2567 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2570 /* Argument is an interger zero. */
2571 return integer_zerop (gimple_call_arg (stmt
, 0));
2574 /* Try to guess whether the value of return means error code. */
2576 static enum br_predictor
2577 return_prediction (tree val
, enum prediction
*prediction
)
2581 return PRED_NO_PREDICTION
;
2582 /* Different heuristics for pointers and scalars. */
2583 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2585 /* NULL is usually not returned. */
2586 if (integer_zerop (val
))
2588 *prediction
= NOT_TAKEN
;
2589 return PRED_NULL_RETURN
;
2592 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2594 /* Negative return values are often used to indicate
2596 if (TREE_CODE (val
) == INTEGER_CST
2597 && tree_int_cst_sgn (val
) < 0)
2599 *prediction
= NOT_TAKEN
;
2600 return PRED_NEGATIVE_RETURN
;
2602 /* Constant return values seems to be commonly taken.
2603 Zero/one often represent booleans so exclude them from the
2605 if (TREE_CONSTANT (val
)
2606 && (!integer_zerop (val
) && !integer_onep (val
)))
2608 *prediction
= NOT_TAKEN
;
2609 return PRED_CONST_RETURN
;
2612 return PRED_NO_PREDICTION
;
2615 /* Find the basic block with return expression and look up for possible
2616 return value trying to apply RETURN_PREDICTION heuristics. */
2618 apply_return_prediction (void)
2620 greturn
*return_stmt
= NULL
;
2624 int phi_num_args
, i
;
2625 enum br_predictor pred
;
2626 enum prediction direction
;
2629 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2631 gimple
*last
= last_stmt (e
->src
);
2633 && gimple_code (last
) == GIMPLE_RETURN
)
2635 return_stmt
= as_a
<greturn
*> (last
);
2641 return_val
= gimple_return_retval (return_stmt
);
2644 if (TREE_CODE (return_val
) != SSA_NAME
2645 || !SSA_NAME_DEF_STMT (return_val
)
2646 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2648 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2649 phi_num_args
= gimple_phi_num_args (phi
);
2650 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2652 /* Avoid the degenerate case where all return values form the function
2653 belongs to same category (ie they are all positive constants)
2654 so we can hardly say something about them. */
2655 for (i
= 1; i
< phi_num_args
; i
++)
2656 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2658 if (i
!= phi_num_args
)
2659 for (i
= 0; i
< phi_num_args
; i
++)
2661 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2662 if (pred
!= PRED_NO_PREDICTION
)
2663 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2668 /* Look for basic block that contains unlikely to happen events
2669 (such as noreturn calls) and mark all paths leading to execution
2670 of this basic blocks as unlikely. */
2673 tree_bb_level_predictions (void)
2676 bool has_return_edges
= false;
2680 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2681 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2683 has_return_edges
= true;
2687 apply_return_prediction ();
2689 FOR_EACH_BB_FN (bb
, cfun
)
2691 gimple_stmt_iterator gsi
;
2693 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2695 gimple
*stmt
= gsi_stmt (gsi
);
2698 if (is_gimple_call (stmt
))
2700 if (gimple_call_noreturn_p (stmt
)
2702 && !is_exit_with_zero_arg (stmt
))
2703 predict_paths_leading_to (bb
, PRED_NORETURN
,
2705 decl
= gimple_call_fndecl (stmt
);
2707 && lookup_attribute ("cold",
2708 DECL_ATTRIBUTES (decl
)))
2709 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2711 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2712 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2715 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2717 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2718 gimple_predict_outcome (stmt
));
2719 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2720 hints to callers. */
2726 /* Callback for hash_map::traverse, asserts that the pointer map is
2730 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2733 gcc_assert (!value
);
2737 /* Predict branch probabilities and estimate profile for basic block BB.
2738 When LOCAL_ONLY is set do not use any global properties of CFG. */
2741 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
2746 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2748 /* Look for block we are guarding (ie we dominate it,
2749 but it doesn't postdominate us). */
2750 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2752 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2753 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2755 gimple_stmt_iterator bi
;
2757 /* The call heuristic claims that a guarded function call
2758 is improbable. This is because such calls are often used
2759 to signal exceptional situations such as printing error
2761 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2764 gimple
*stmt
= gsi_stmt (bi
);
2765 if (is_gimple_call (stmt
)
2766 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
2767 /* Constant and pure calls are hardly used to signalize
2768 something exceptional. */
2769 && gimple_has_side_effects (stmt
))
2771 if (gimple_call_fndecl (stmt
))
2772 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2773 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
2774 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
2776 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
2782 tree_predict_by_opcode (bb
);
2785 /* Predict branch probabilities and estimate profile of the tree CFG.
2786 This function can be called from the loop optimizers to recompute
2787 the profile information.
2788 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2791 tree_estimate_probability (bool dry_run
)
2795 add_noreturn_fake_exit_edges ();
2796 connect_infinite_loops_to_exit ();
2797 /* We use loop_niter_by_eval, which requires that the loops have
2799 create_preheaders (CP_SIMPLE_PREHEADERS
);
2800 calculate_dominance_info (CDI_POST_DOMINATORS
);
2802 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2803 tree_bb_level_predictions ();
2804 record_loop_exits ();
2806 if (number_of_loops (cfun
) > 1)
2809 FOR_EACH_BB_FN (bb
, cfun
)
2810 tree_estimate_probability_bb (bb
, false);
2812 FOR_EACH_BB_FN (bb
, cfun
)
2813 combine_predictions_for_bb (bb
, dry_run
);
2816 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2818 delete bb_predictions
;
2819 bb_predictions
= NULL
;
2822 estimate_bb_frequencies (false);
2823 free_dominance_info (CDI_POST_DOMINATORS
);
2824 remove_fake_exit_edges ();
2827 /* Set edge->probability for each successor edge of BB. */
2829 tree_guess_outgoing_edge_probabilities (basic_block bb
)
2831 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2832 tree_estimate_probability_bb (bb
, true);
2833 combine_predictions_for_bb (bb
, false);
2835 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2836 delete bb_predictions
;
2837 bb_predictions
= NULL
;
2840 /* Predict edges to successors of CUR whose sources are not postdominated by
2841 BB by PRED and recurse to all postdominators. */
2844 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2845 enum br_predictor pred
,
2846 enum prediction taken
,
2847 bitmap visited
, struct loop
*in_loop
= NULL
)
2853 /* If we exited the loop or CUR is unconditional in the loop, there is
2856 && (!flow_bb_inside_loop_p (in_loop
, cur
)
2857 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
2860 /* We are looking for all edges forming edge cut induced by
2861 set of all blocks postdominated by BB. */
2862 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2863 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2864 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2870 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2871 if (unlikely_executed_edge_p (e
))
2873 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2875 /* See if there is an edge from e->src that is not abnormal
2876 and does not lead to BB and does not exit the loop. */
2877 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2879 && !unlikely_executed_edge_p (e2
)
2880 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
2881 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
2887 /* If there is non-abnormal path leaving e->src, predict edge
2888 using predictor. Otherwise we need to look for paths
2891 The second may lead to infinite loop in the case we are predicitng
2892 regions that are only reachable by abnormal edges. We simply
2893 prevent visiting given BB twice. */
2896 if (!edge_predicted_by_p (e
, pred
, taken
))
2897 predict_edge_def (e
, pred
, taken
);
2899 else if (bitmap_set_bit (visited
, e
->src
->index
))
2900 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
2902 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2904 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2905 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
2908 /* Sets branch probabilities according to PREDiction and
2912 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2913 enum prediction taken
, struct loop
*in_loop
)
2915 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
2918 /* Like predict_paths_leading_to but take edge instead of basic block. */
2921 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2922 enum prediction taken
, struct loop
*in_loop
)
2924 bool has_nonloop_edge
= false;
2928 basic_block bb
= e
->src
;
2929 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2930 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2931 && !unlikely_executed_edge_p (e
)
2932 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2934 has_nonloop_edge
= true;
2937 if (!has_nonloop_edge
)
2939 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
2942 predict_edge_def (e
, pred
, taken
);
2945 /* This is used to carry information about basic blocks. It is
2946 attached to the AUX field of the standard CFG block. */
2950 /* Estimated frequency of execution of basic_block. */
2953 /* To keep queue of basic blocks to process. */
2956 /* Number of predecessors we need to visit first. */
2960 /* Similar information for edges. */
2961 struct edge_prob_info
2963 /* In case edge is a loopback edge, the probability edge will be reached
2964 in case header is. Estimated number of iterations of the loop can be
2965 then computed as 1 / (1 - back_edge_prob). */
2966 sreal back_edge_prob
;
2967 /* True if the edge is a loopback edge in the natural loop. */
2968 unsigned int back_edge
:1;
2971 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2973 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2975 /* Helper function for estimate_bb_frequencies.
2976 Propagate the frequencies in blocks marked in
2977 TOVISIT, starting in HEAD. */
2980 propagate_freq (basic_block head
, bitmap tovisit
)
2989 /* For each basic block we need to visit count number of his predecessors
2990 we need to visit first. */
2991 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2996 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2998 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3000 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3002 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3004 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3006 "Irreducible region hit, ignoring edge to %i->%i\n",
3007 e
->src
->index
, bb
->index
);
3009 BLOCK_INFO (bb
)->npredecessors
= count
;
3010 /* When function never returns, we will never process exit block. */
3011 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3012 bb
->count
= profile_count::zero ();
3015 BLOCK_INFO (head
)->frequency
= 1;
3017 for (bb
= head
; bb
; bb
= nextbb
)
3020 sreal cyclic_probability
= 0;
3021 sreal frequency
= 0;
3023 nextbb
= BLOCK_INFO (bb
)->next
;
3024 BLOCK_INFO (bb
)->next
= NULL
;
3026 /* Compute frequency of basic block. */
3030 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3031 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3032 || (e
->flags
& EDGE_DFS_BACK
));
3034 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3035 if (EDGE_INFO (e
)->back_edge
)
3037 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3039 else if (!(e
->flags
& EDGE_DFS_BACK
))
3041 /* frequency += (e->probability
3042 * BLOCK_INFO (e->src)->frequency /
3043 REG_BR_PROB_BASE); */
3045 /* FIXME: Graphite is producing edges with no profile. Once
3046 this is fixed, drop this. */
3047 sreal tmp
= e
->probability
.initialized_p () ?
3048 e
->probability
.to_reg_br_prob_base () : 0;
3049 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
3050 tmp
*= real_inv_br_prob_base
;
3054 if (cyclic_probability
== 0)
3056 BLOCK_INFO (bb
)->frequency
= frequency
;
3060 if (cyclic_probability
> real_almost_one
)
3061 cyclic_probability
= real_almost_one
;
3063 /* BLOCK_INFO (bb)->frequency = frequency
3064 / (1 - cyclic_probability) */
3066 cyclic_probability
= sreal (1) - cyclic_probability
;
3067 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
3071 bitmap_clear_bit (tovisit
, bb
->index
);
3073 e
= find_edge (bb
, head
);
3076 /* EDGE_INFO (e)->back_edge_prob
3077 = ((e->probability * BLOCK_INFO (bb)->frequency)
3078 / REG_BR_PROB_BASE); */
3080 /* FIXME: Graphite is producing edges with no profile. Once
3081 this is fixed, drop this. */
3082 sreal tmp
= e
->probability
.initialized_p () ?
3083 e
->probability
.to_reg_br_prob_base () : 0;
3084 tmp
*= BLOCK_INFO (bb
)->frequency
;
3085 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
3088 /* Propagate to successor blocks. */
3089 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3090 if (!(e
->flags
& EDGE_DFS_BACK
)
3091 && BLOCK_INFO (e
->dest
)->npredecessors
)
3093 BLOCK_INFO (e
->dest
)->npredecessors
--;
3094 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3099 BLOCK_INFO (last
)->next
= e
->dest
;
3107 /* Estimate frequencies in loops at same nest level. */
3110 estimate_loops_at_level (struct loop
*first_loop
)
3114 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3119 auto_bitmap tovisit
;
3121 estimate_loops_at_level (loop
->inner
);
3123 /* Find current loop back edge and mark it. */
3124 e
= loop_latch_edge (loop
);
3125 EDGE_INFO (e
)->back_edge
= 1;
3127 bbs
= get_loop_body (loop
);
3128 for (i
= 0; i
< loop
->num_nodes
; i
++)
3129 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3131 propagate_freq (loop
->header
, tovisit
);
3135 /* Propagates frequencies through structure of loops. */
3138 estimate_loops (void)
3140 auto_bitmap tovisit
;
3143 /* Start by estimating the frequencies in the loops. */
3144 if (number_of_loops (cfun
) > 1)
3145 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3147 /* Now propagate the frequencies through all the blocks. */
3148 FOR_ALL_BB_FN (bb
, cfun
)
3150 bitmap_set_bit (tovisit
, bb
->index
);
3152 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3155 /* Drop the profile for NODE to guessed, and update its frequency based on
3156 whether it is expected to be hot given the CALL_COUNT. */
3159 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3161 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3162 /* In the case where this was called by another function with a
3163 dropped profile, call_count will be 0. Since there are no
3164 non-zero call counts to this function, we don't know for sure
3165 whether it is hot, and therefore it will be marked normal below. */
3166 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3170 "Dropping 0 profile for %s. %s based on calls.\n",
3172 hot
? "Function is hot" : "Function is normal");
3173 /* We only expect to miss profiles for functions that are reached
3174 via non-zero call edges in cases where the function may have
3175 been linked from another module or library (COMDATs and extern
3176 templates). See the comments below for handle_missing_profiles.
3177 Also, only warn in cases where the missing counts exceed the
3178 number of training runs. In certain cases with an execv followed
3179 by a no-return call the profile for the no-return call is not
3180 dumped and there can be a mismatch. */
3181 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3182 && call_count
> profile_info
->runs
)
3184 if (flag_profile_correction
)
3188 "Missing counts for called function %s\n",
3189 node
->dump_name ());
3192 warning (0, "Missing counts for called function %s",
3193 node
->dump_name ());
3197 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3198 if (flag_guess_branch_prob
)
3201 = ENTRY_BLOCK_PTR_FOR_FN
3202 (DECL_STRUCT_FUNCTION (node
->decl
))->count
.nonzero_p ();
3203 FOR_ALL_BB_FN (bb
, fn
)
3204 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3205 bb
->count
= bb
->count
.guessed_local ();
3206 DECL_STRUCT_FUNCTION (node
->decl
)->cfg
->count_max
=
3207 DECL_STRUCT_FUNCTION (node
->decl
)->cfg
->count_max
.guessed_local ();
3211 FOR_ALL_BB_FN (bb
, fn
)
3212 bb
->count
= profile_count::uninitialized ();
3213 DECL_STRUCT_FUNCTION (node
->decl
)->cfg
->count_max
3214 = profile_count::uninitialized ();
3218 struct cgraph_edge
*e
;
3219 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3220 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3221 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3222 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3224 profile_status_for_fn (fn
)
3225 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3227 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3230 /* In the case of COMDAT routines, multiple object files will contain the same
3231 function and the linker will select one for the binary. In that case
3232 all the other copies from the profile instrument binary will be missing
3233 profile counts. Look for cases where this happened, due to non-zero
3234 call counts going to 0-count functions, and drop the profile to guessed
3235 so that we can use the estimated probabilities and avoid optimizing only
3238 The other case where the profile may be missing is when the routine
3239 is not going to be emitted to the object file, e.g. for "extern template"
3240 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3241 all other cases of non-zero calls to 0-count functions. */
3244 handle_missing_profiles (void)
3246 struct cgraph_node
*node
;
3247 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3248 auto_vec
<struct cgraph_node
*, 64> worklist
;
3250 /* See if 0 count function has non-0 count callers. In this case we
3251 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3252 FOR_EACH_DEFINED_FUNCTION (node
)
3254 struct cgraph_edge
*e
;
3255 profile_count call_count
= profile_count::zero ();
3256 gcov_type max_tp_first_run
= 0;
3257 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3259 if (!(node
->count
== profile_count::zero ()))
3261 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3262 if (e
->count
.initialized_p () && e
->count
> 0)
3264 call_count
= call_count
+ e
->count
;
3266 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3267 max_tp_first_run
= e
->caller
->tp_first_run
;
3270 /* If time profile is missing, let assign the maximum that comes from
3271 caller functions. */
3272 if (!node
->tp_first_run
&& max_tp_first_run
)
3273 node
->tp_first_run
= max_tp_first_run
+ 1;
3277 && (call_count
.apply_scale (unlikely_count_fraction
, 1)
3278 >= profile_info
->runs
))
3280 drop_profile (node
, call_count
);
3281 worklist
.safe_push (node
);
3285 /* Propagate the profile dropping to other 0-count COMDATs that are
3286 potentially called by COMDATs we already dropped the profile on. */
3287 while (worklist
.length () > 0)
3289 struct cgraph_edge
*e
;
3291 node
= worklist
.pop ();
3292 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3294 struct cgraph_node
*callee
= e
->callee
;
3295 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3297 if (callee
->count
> 0)
3299 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3301 && profile_status_for_fn (fn
) == PROFILE_READ
)
3303 drop_profile (node
, profile_count::zero ());
3304 worklist
.safe_push (callee
);
3310 /* Convert counts measured by profile driven feedback to frequencies.
3311 Return nonzero iff there was any nonzero execution count. */
3314 update_max_bb_count (void)
3316 profile_count true_count_max
= profile_count::uninitialized ();
3319 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3320 true_count_max
= true_count_max
.max (bb
->count
);
3322 cfun
->cfg
->count_max
= true_count_max
;
3324 return true_count_max
.ipa ().nonzero_p ();
3327 /* Return true if function is likely to be expensive, so there is no point to
3328 optimize performance of prologue, epilogue or do inlining at the expense
3329 of code size growth. THRESHOLD is the limit of number of instructions
3330 function can execute at average to be still considered not expensive. */
3333 expensive_function_p (int threshold
)
3337 /* We can not compute accurately for large thresholds due to scaled
3339 gcc_assert (threshold
<= BB_FREQ_MAX
);
3341 /* If profile was scaled in a way entry block has count 0, then the function
3342 is deifnitly taking a lot of time. */
3343 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3346 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
3347 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN
3348 (cfun
)->count
.apply_scale (threshold
, 1);
3349 profile_count sum
= profile_count::zero ();
3350 FOR_EACH_BB_FN (bb
, cfun
)
3354 if (!bb
->count
.initialized_p ())
3357 fprintf (dump_file
, "Function is considered expensive because"
3358 " count of bb %i is not initialized\n", bb
->index
);
3362 FOR_BB_INSNS (bb
, insn
)
3363 if (active_insn_p (insn
))
3374 /* All basic blocks that are reachable only from unlikely basic blocks are
3378 propagate_unlikely_bbs_forward (void)
3380 auto_vec
<basic_block
, 64> worklist
;
3385 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3387 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3388 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3390 while (worklist
.length () > 0)
3392 bb
= worklist
.pop ();
3393 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3394 if (!(e
->count () == profile_count::zero ())
3395 && !(e
->dest
->count
== profile_count::zero ())
3398 e
->dest
->aux
= (void *)(size_t) 1;
3399 worklist
.safe_push (e
->dest
);
3404 FOR_ALL_BB_FN (bb
, cfun
)
3408 if (!(bb
->count
== profile_count::zero ())
3409 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3411 "Basic block %i is marked unlikely by forward prop\n",
3413 bb
->count
= profile_count::zero ();
3420 /* Determine basic blocks/edges that are known to be unlikely executed and set
3421 their counters to zero.
3422 This is done with first identifying obviously unlikely BBs/edges and then
3423 propagating in both directions. */
3426 determine_unlikely_bbs ()
3429 auto_vec
<basic_block
, 64> worklist
;
3433 FOR_EACH_BB_FN (bb
, cfun
)
3435 if (!(bb
->count
== profile_count::zero ())
3436 && unlikely_executed_bb_p (bb
))
3438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3439 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3441 bb
->count
= profile_count::zero ();
3444 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3445 if (!(e
->probability
== profile_probability::never ())
3446 && unlikely_executed_edge_p (e
))
3448 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3449 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3450 bb
->index
, e
->dest
->index
);
3451 e
->probability
= profile_probability::never ();
3454 gcc_checking_assert (!bb
->aux
);
3457 auto_vec
<int, 64> nsuccs
;
3458 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
3459 FOR_ALL_BB_FN (bb
, cfun
)
3460 if (!(bb
->count
== profile_count::zero ())
3461 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3463 nsuccs
[bb
->index
] = 0;
3464 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3465 if (!(e
->probability
== profile_probability::never ())
3466 && !(e
->dest
->count
== profile_count::zero ()))
3467 nsuccs
[bb
->index
]++;
3468 if (!nsuccs
[bb
->index
])
3469 worklist
.safe_push (bb
);
3471 while (worklist
.length () > 0)
3473 bb
= worklist
.pop ();
3474 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3477 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3478 !gsi_end_p (gsi
); gsi_next (&gsi
))
3479 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3480 /* stmt_can_terminate_bb_p special cases noreturns because it
3481 assumes that fake edges are created. We want to know that
3482 noreturn alone does not imply BB to be unlikely. */
3483 || (is_gimple_call (gsi_stmt (gsi
))
3484 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3492 if (!(bb
->count
== profile_count::zero ())
3493 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3495 "Basic block %i is marked unlikely by backward prop\n",
3497 bb
->count
= profile_count::zero ();
3498 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3499 if (!(e
->probability
== profile_probability::never ()))
3501 e
->probability
= profile_probability::never ();
3502 if (!(e
->src
->count
== profile_count::zero ()))
3504 nsuccs
[e
->src
->index
]--;
3505 if (!nsuccs
[e
->src
->index
])
3506 worklist
.safe_push (e
->src
);
3512 /* Estimate and propagate basic block frequencies using the given branch
3513 probabilities. If FORCE is true, the frequencies are used to estimate
3514 the counts even when there are already non-zero profile counts. */
3517 estimate_bb_frequencies (bool force
)
3522 determine_unlikely_bbs ();
3524 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3525 || !update_max_bb_count ())
3527 static int real_values_initialized
= 0;
3529 if (!real_values_initialized
)
3531 real_values_initialized
= 1;
3532 real_br_prob_base
= REG_BR_PROB_BASE
;
3533 real_bb_freq_max
= BB_FREQ_MAX
;
3534 real_one_half
= sreal (1, -1);
3535 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3536 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3539 mark_dfs_back_edges ();
3541 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3542 profile_probability::always ();
3544 /* Set up block info for each basic block. */
3545 alloc_aux_for_blocks (sizeof (block_info
));
3546 alloc_aux_for_edges (sizeof (edge_prob_info
));
3547 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3552 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3554 /* FIXME: Graphite is producing edges with no profile. Once
3555 this is fixed, drop this. */
3556 if (e
->probability
.initialized_p ())
3557 EDGE_INFO (e
)->back_edge_prob
3558 = e
->probability
.to_reg_br_prob_base ();
3560 EDGE_INFO (e
)->back_edge_prob
= REG_BR_PROB_BASE
/ 2;
3561 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3565 /* First compute frequencies locally for each loop from innermost
3566 to outermost to examine frequencies for back edges. */
3569 bool global0
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.initialized_p ()
3570 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ();
3573 FOR_EACH_BB_FN (bb
, cfun
)
3574 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3575 freq_max
= BLOCK_INFO (bb
)->frequency
;
3577 freq_max
= real_bb_freq_max
/ freq_max
;
3578 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3579 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3581 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3582 profile_count count
= profile_count::from_gcov_type (tmp
.to_int ());
3584 /* If we have profile feedback in which this function was never
3585 executed, then preserve this info. */
3587 bb
->count
= count
.global0 ();
3588 else if (!(bb
->count
== profile_count::zero ()))
3589 bb
->count
= count
.guessed_local ();
3590 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3593 free_aux_for_blocks ();
3594 free_aux_for_edges ();
3596 compute_function_frequency ();
3599 /* Decide whether function is hot, cold or unlikely executed. */
3601 compute_function_frequency (void)
3604 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3606 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3607 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3608 node
->only_called_at_startup
= true;
3609 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3610 node
->only_called_at_exit
= true;
3612 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3614 int flags
= flags_from_decl_or_type (current_function_decl
);
3615 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ()
3616 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3617 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3620 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3621 warn_function_cold (current_function_decl
);
3623 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3625 node
->frequency
= NODE_FREQUENCY_HOT
;
3626 else if (flags
& ECF_NORETURN
)
3627 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3628 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3629 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3630 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3631 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3632 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3636 /* Only first time try to drop function into unlikely executed.
3637 After inlining the roundoff errors may confuse us.
3638 Ipa-profile pass will drop functions only called from unlikely
3639 functions to unlikely and that is most of what we care about. */
3640 if (!cfun
->after_inlining
)
3642 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3643 warn_function_cold (current_function_decl
);
3645 FOR_EACH_BB_FN (bb
, cfun
)
3647 if (maybe_hot_bb_p (cfun
, bb
))
3649 node
->frequency
= NODE_FREQUENCY_HOT
;
3652 if (!probably_never_executed_bb_p (cfun
, bb
))
3653 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3657 /* Build PREDICT_EXPR. */
3659 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3661 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3662 build_int_cst (integer_type_node
, predictor
));
3663 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3668 predictor_name (enum br_predictor predictor
)
3670 return predictor_info
[predictor
].name
;
3673 /* Predict branch probabilities and estimate profile of the tree CFG. */
3677 const pass_data pass_data_profile
=
3679 GIMPLE_PASS
, /* type */
3680 "profile_estimate", /* name */
3681 OPTGROUP_NONE
, /* optinfo_flags */
3682 TV_BRANCH_PROB
, /* tv_id */
3683 PROP_cfg
, /* properties_required */
3684 0, /* properties_provided */
3685 0, /* properties_destroyed */
3686 0, /* todo_flags_start */
3687 0, /* todo_flags_finish */
3690 class pass_profile
: public gimple_opt_pass
3693 pass_profile (gcc::context
*ctxt
)
3694 : gimple_opt_pass (pass_data_profile
, ctxt
)
3697 /* opt_pass methods: */
3698 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3699 virtual unsigned int execute (function
*);
3701 }; // class pass_profile
3704 pass_profile::execute (function
*fun
)
3708 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3711 loop_optimizer_init (LOOPS_NORMAL
);
3712 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3713 flow_loops_dump (dump_file
, NULL
, 0);
3715 mark_irreducible_loops ();
3717 nb_loops
= number_of_loops (fun
);
3721 tree_estimate_probability (false);
3726 loop_optimizer_finalize ();
3727 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3728 gimple_dump_cfg (dump_file
, dump_flags
);
3729 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3730 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3731 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3734 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3735 if (loop
->header
->count
.initialized_p ())
3736 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
3738 (int)expected_loop_iterations_unbounded (loop
));
3746 make_pass_profile (gcc::context
*ctxt
)
3748 return new pass_profile (ctxt
);
3753 const pass_data pass_data_strip_predict_hints
=
3755 GIMPLE_PASS
, /* type */
3756 "*strip_predict_hints", /* name */
3757 OPTGROUP_NONE
, /* optinfo_flags */
3758 TV_BRANCH_PROB
, /* tv_id */
3759 PROP_cfg
, /* properties_required */
3760 0, /* properties_provided */
3761 0, /* properties_destroyed */
3762 0, /* todo_flags_start */
3763 0, /* todo_flags_finish */
3766 class pass_strip_predict_hints
: public gimple_opt_pass
3769 pass_strip_predict_hints (gcc::context
*ctxt
)
3770 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3773 /* opt_pass methods: */
3774 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3775 virtual unsigned int execute (function
*);
3777 }; // class pass_strip_predict_hints
3779 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3780 we no longer need. */
3782 pass_strip_predict_hints::execute (function
*fun
)
3787 bool changed
= false;
3789 FOR_EACH_BB_FN (bb
, fun
)
3791 gimple_stmt_iterator bi
;
3792 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3794 gimple
*stmt
= gsi_stmt (bi
);
3796 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3798 gsi_remove (&bi
, true);
3802 else if (is_gimple_call (stmt
))
3804 tree fndecl
= gimple_call_fndecl (stmt
);
3807 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3808 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3809 && gimple_call_num_args (stmt
) == 2)
3810 || (gimple_call_internal_p (stmt
)
3811 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3813 var
= gimple_call_lhs (stmt
);
3818 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3819 gsi_replace (&bi
, ass_stmt
, true);
3823 gsi_remove (&bi
, true);
3831 return changed
? TODO_cleanup_cfg
: 0;
3837 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3839 return new pass_strip_predict_hints (ctxt
);
3842 /* Rebuild function frequencies. Passes are in general expected to
3843 maintain profile by hand, however in some cases this is not possible:
3844 for example when inlining several functions with loops freuqencies might run
3845 out of scale and thus needs to be recomputed. */
3848 rebuild_frequencies (void)
3850 timevar_push (TV_REBUILD_FREQUENCIES
);
3852 /* When the max bb count in the function is small, there is a higher
3853 chance that there were truncation errors in the integer scaling
3854 of counts by inlining and other optimizations. This could lead
3855 to incorrect classification of code as being cold when it isn't.
3856 In that case, force the estimation of bb counts/frequencies from the
3857 branch probabilities, rather than computing frequencies from counts,
3858 which may also lead to frequencies incorrectly reduced to 0. There
3859 is less precision in the probabilities, so we only do this for small
3861 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3863 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3864 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3866 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3868 loop_optimizer_init (0);
3869 add_noreturn_fake_exit_edges ();
3870 mark_irreducible_loops ();
3871 connect_infinite_loops_to_exit ();
3872 estimate_bb_frequencies (true);
3873 remove_fake_exit_edges ();
3874 loop_optimizer_finalize ();
3876 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3877 update_max_bb_count ();
3880 timevar_pop (TV_REBUILD_FREQUENCIES
);
3883 /* Perform a dry run of the branch prediction pass and report comparsion of
3884 the predicted and real profile into the dump file. */
3887 report_predictor_hitrates (void)
3891 loop_optimizer_init (LOOPS_NORMAL
);
3892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3893 flow_loops_dump (dump_file
, NULL
, 0);
3895 mark_irreducible_loops ();
3897 nb_loops
= number_of_loops (cfun
);
3901 tree_estimate_probability (true);
3906 loop_optimizer_finalize ();
3909 /* Force edge E to be cold.
3910 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
3911 keep low probability to represent possible error in a guess. This is used
3912 i.e. in case we predict loop to likely iterate given number of times but
3913 we are not 100% sure.
3915 This function locally updates profile without attempt to keep global
3916 consistency which can not be reached in full generality without full profile
3917 rebuild from probabilities alone. Doing so is not necessarily a good idea
3918 because frequencies and counts may be more realistic then probabilities.
3920 In some cases (such as for elimination of early exits during full loop
3921 unrolling) the caller can ensure that profile will get consistent
3925 force_edge_cold (edge e
, bool impossible
)
3927 profile_count count_sum
= profile_count::zero ();
3928 profile_probability prob_sum
= profile_probability::never ();
3931 bool uninitialized_exit
= false;
3933 profile_probability goal
= (impossible
? profile_probability::never ()
3934 : profile_probability::very_unlikely ());
3936 /* If edge is already improbably or cold, just return. */
3937 if (e
->probability
<= goal
3938 && (!impossible
|| e
->count () == profile_count::zero ()))
3940 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3943 if (e2
->count ().initialized_p ())
3944 count_sum
+= e2
->count ();
3946 uninitialized_exit
= true;
3947 if (e2
->probability
.initialized_p ())
3948 prob_sum
+= e2
->probability
;
3951 /* If there are other edges out of e->src, redistribute probabilitity
3953 if (prob_sum
> profile_probability::never ())
3955 if (!(e
->probability
< goal
))
3956 e
->probability
= goal
;
3958 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
3960 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3961 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
3962 "probability to other edges.\n",
3963 e
->src
->index
, e
->dest
->index
,
3964 impossible
? "impossible" : "cold");
3965 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3968 e2
->probability
/= prob_comp
;
3970 if (current_ir_type () != IR_GIMPLE
3971 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3972 update_br_prob_note (e
->src
);
3974 /* If all edges out of e->src are unlikely, the basic block itself
3978 if (prob_sum
== profile_probability::never ())
3979 e
->probability
= profile_probability::always ();
3983 e
->probability
= profile_probability::never ();
3984 /* If BB has some edges out that are not impossible, we can not
3985 assume that BB itself is. */
3988 if (current_ir_type () != IR_GIMPLE
3989 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3990 update_br_prob_note (e
->src
);
3991 if (e
->src
->count
== profile_count::zero ())
3993 if (count_sum
== profile_count::zero () && !uninitialized_exit
3997 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3999 else if (current_ir_type () == IR_GIMPLE
)
4000 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4001 !gsi_end_p (gsi
); gsi_next (&gsi
))
4003 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4009 /* FIXME: Implement RTL path. */
4014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4016 "Making bb %i impossible and dropping count to 0.\n",
4018 e
->src
->count
= profile_count::zero ();
4019 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4020 force_edge_cold (e2
, impossible
);
4025 /* If we did not adjusting, the source basic block has no likely edeges
4026 leaving other direction. In that case force that bb cold, too.
4027 This in general is difficult task to do, but handle special case when
4028 BB has only one predecestor. This is common case when we are updating
4029 after loop transforms. */
4030 if (!(prob_sum
> profile_probability::never ())
4031 && count_sum
== profile_count::zero ()
4032 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4033 > (impossible
? 0 : 1))
4035 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4037 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4038 impossible
? "impossible" : "cold");
4039 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4040 impossible
? 0 : 1);
4042 e
->src
->count
= profile_count::zero ();
4044 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4046 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4048 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4049 && maybe_hot_bb_p (cfun
, e
->src
))
4050 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4051 impossible
? "impossible" : "cold");
4057 namespace selftest
{
4059 /* Test that value range of predictor values defined in predict.def is
4060 within range (50, 100]. */
4062 struct branch_predictor
4065 unsigned probability
;
4068 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4071 test_prediction_value_range ()
4073 branch_predictor predictors
[] = {
4074 #include "predict.def"
4078 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4080 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4081 ASSERT_TRUE (p
> 50 && p
<= 100);
4085 #undef DEF_PREDICTOR
4087 /* Run all of the selfests within this file. */
4092 test_prediction_value_range ();
4095 } // namespace selftest
4096 #endif /* CHECKING_P. */