1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 [1] "Branch Prediction for Free"
23 Ball and Larus; PLDI '93.
24 [2] "Static Branch Frequency and Program Profile Analysis"
25 Wu and Larus; MICRO-27.
26 [3] "Corpus-based Static Branch Prediction"
27 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
32 #include "coretypes.h"
38 #include "tree-pass.h"
44 #include "diagnostic-core.h"
45 #include "gimple-predict.h"
46 #include "fold-const.h"
53 #include "gimple-iterator.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-scalar-evolution.h"
58 #include "ipa-utils.h"
59 #include "gimple-pretty-print.h"
62 #include "stringpool.h"
65 /* Enum with reasons why a predictor is ignored. */
71 REASON_SINGLE_EDGE_DUPLICATE
,
72 REASON_EDGE_PAIR_DUPLICATE
75 /* String messages for the aforementioned enum. */
77 static const char *reason_messages
[] = {"", " (ignored)",
78 " (single edge duplicate)", " (edge pair duplicate)"};
80 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
81 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
82 static sreal real_almost_one
, real_br_prob_base
,
83 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
85 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
86 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
,
87 enum predictor_reason
, edge
);
88 static void predict_paths_leading_to (basic_block
, enum br_predictor
,
90 struct loop
*in_loop
= NULL
);
91 static void predict_paths_leading_to_edge (edge
, enum br_predictor
,
93 struct loop
*in_loop
= NULL
);
94 static bool can_predict_insn_p (const rtx_insn
*);
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");
751 /* Print output that be easily read by analyze_brprob.py script. We are
752 interested only in counts that are read from GCDA files. */
753 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
754 && bb
->count
.precise_p ()
755 && reason
== REASON_NONE
)
757 gcc_assert (e
->count ().precise_p ());
758 fprintf (file
, ";;heuristics;%s;%" PRId64
";%" PRId64
";%.1f;\n",
759 predictor_info
[predictor
].name
,
760 bb
->count
.to_gcov_type (), e
->count ().to_gcov_type (),
761 probability
* 100.0 / REG_BR_PROB_BASE
);
765 /* Return true if STMT is known to be unlikely executed. */
768 unlikely_executed_stmt_p (gimple
*stmt
)
770 if (!is_gimple_call (stmt
))
772 /* NORETURN attribute alone is not strong enough: exit() may be quite
773 likely executed once during program run. */
774 if (gimple_call_fntype (stmt
)
775 && lookup_attribute ("cold",
776 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
777 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
779 tree decl
= gimple_call_fndecl (stmt
);
782 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
783 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
786 cgraph_node
*n
= cgraph_node::get (decl
);
791 n
= n
->ultimate_alias_target (&avail
);
792 if (avail
< AVAIL_AVAILABLE
)
795 || n
->decl
== current_function_decl
)
797 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
800 /* Return true if BB is unlikely executed. */
803 unlikely_executed_bb_p (basic_block bb
)
805 if (bb
->count
== profile_count::zero ())
807 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
809 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
810 !gsi_end_p (gsi
); gsi_next (&gsi
))
812 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
814 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
820 /* We can not predict the probabilities of outgoing edges of bb. Set them
821 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
822 even probability for all edges not mentioned in the set. These edges
823 are given PROB_VERY_UNLIKELY probability. */
826 set_even_probabilities (basic_block bb
,
827 hash_set
<edge
> *unlikely_edges
= NULL
)
829 unsigned nedges
= 0, unlikely_count
= 0;
832 profile_probability all
= profile_probability::always ();
834 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
835 if (e
->probability
.initialized_p ())
836 all
-= e
->probability
;
837 else if (!unlikely_executed_edge_p (e
))
840 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
842 all
-= profile_probability::very_unlikely ();
847 /* Make the distribution even if all edges are unlikely. */
848 if (unlikely_count
== nedges
)
850 unlikely_edges
= NULL
;
854 unsigned c
= nedges
- unlikely_count
;
856 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
857 if (e
->probability
.initialized_p ())
859 else if (!unlikely_executed_edge_p (e
))
861 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
862 e
->probability
= profile_probability::very_unlikely ();
864 e
->probability
= all
.apply_scale (1, c
).guessed ();
867 e
->probability
= profile_probability::never ();
870 /* Add REG_BR_PROB note to JUMP with PROB. */
873 add_reg_br_prob_note (rtx_insn
*jump
, profile_probability prob
)
875 gcc_checking_assert (JUMP_P (jump
) && !find_reg_note (jump
, REG_BR_PROB
, 0));
876 add_int_reg_note (jump
, REG_BR_PROB
, prob
.to_reg_br_prob_note ());
879 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
880 note if not already present. Remove now useless REG_BR_PRED notes. */
883 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
888 int best_probability
= PROB_EVEN
;
889 enum br_predictor best_predictor
= END_PREDICTORS
;
890 int combined_probability
= REG_BR_PROB_BASE
/ 2;
892 bool first_match
= false;
895 if (!can_predict_insn_p (insn
))
897 set_even_probabilities (bb
);
901 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
902 pnote
= ®_NOTES (insn
);
904 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
907 /* We implement "first match" heuristics and use probability guessed
908 by predictor with smallest index. */
909 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
910 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
912 enum br_predictor predictor
= ((enum br_predictor
)
913 INTVAL (XEXP (XEXP (note
, 0), 0)));
914 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
917 if (best_predictor
> predictor
918 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
919 best_probability
= probability
, best_predictor
= predictor
;
921 d
= (combined_probability
* probability
922 + (REG_BR_PROB_BASE
- combined_probability
)
923 * (REG_BR_PROB_BASE
- probability
));
925 /* Use FP math to avoid overflows of 32bit integers. */
927 /* If one probability is 0% and one 100%, avoid division by zero. */
928 combined_probability
= REG_BR_PROB_BASE
/ 2;
930 combined_probability
= (((double) combined_probability
) * probability
931 * REG_BR_PROB_BASE
/ d
+ 0.5);
934 /* Decide which heuristic to use. In case we didn't match anything,
935 use no_prediction heuristic, in case we did match, use either
936 first match or Dempster-Shaffer theory depending on the flags. */
938 if (best_predictor
!= END_PREDICTORS
)
942 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
943 combined_probability
, bb
);
947 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
948 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
950 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
951 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
955 combined_probability
= best_probability
;
956 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
960 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
962 enum br_predictor predictor
= ((enum br_predictor
)
963 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
964 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
966 dump_prediction (dump_file
, predictor
, probability
, bb
,
967 (!first_match
|| best_predictor
== predictor
)
968 ? REASON_NONE
: REASON_IGNORED
);
969 *pnote
= XEXP (*pnote
, 1);
972 pnote
= &XEXP (*pnote
, 1);
977 profile_probability p
978 = profile_probability::from_reg_br_prob_base (combined_probability
);
979 add_reg_br_prob_note (insn
, p
);
981 /* Save the prediction into CFG in case we are seeing non-degenerated
983 if (!single_succ_p (bb
))
985 BRANCH_EDGE (bb
)->probability
= p
;
986 FALLTHRU_EDGE (bb
)->probability
987 = BRANCH_EDGE (bb
)->probability
.invert ();
990 else if (!single_succ_p (bb
))
992 profile_probability prob
= profile_probability::from_reg_br_prob_note
993 (XINT (prob_note
, 0));
995 BRANCH_EDGE (bb
)->probability
= prob
;
996 FALLTHRU_EDGE (bb
)->probability
= prob
.invert ();
999 single_succ_edge (bb
)->probability
= profile_probability::always ();
1002 /* Edge prediction hash traits. */
1004 struct predictor_hash
: pointer_hash
<edge_prediction
>
1007 static inline hashval_t
hash (const edge_prediction
*);
1008 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
1011 /* Calculate hash value of an edge prediction P based on predictor and
1012 normalized probability. */
1015 predictor_hash::hash (const edge_prediction
*p
)
1017 inchash::hash hstate
;
1018 hstate
.add_int (p
->ep_predictor
);
1020 int prob
= p
->ep_probability
;
1021 if (prob
> REG_BR_PROB_BASE
/ 2)
1022 prob
= REG_BR_PROB_BASE
- prob
;
1024 hstate
.add_int (prob
);
1026 return hstate
.end ();
1029 /* Return true whether edge predictions P1 and P2 use the same predictor and
1030 have equal (or opposed probability). */
1033 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1035 return (p1
->ep_predictor
== p2
->ep_predictor
1036 && (p1
->ep_probability
== p2
->ep_probability
1037 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1040 struct predictor_hash_traits
: predictor_hash
,
1041 typed_noop_remove
<edge_prediction
*> {};
1043 /* Return true if edge prediction P is not in DATA hash set. */
1046 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1048 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1049 return !remove
->contains (p
);
1052 /* Prune predictions for a basic block BB. Currently we do following
1055 1) remove duplicate prediction that is guessed with the same probability
1056 (different than 1/2) to both edge
1057 2) remove duplicates for a prediction that belongs with the same probability
1063 prune_predictions_for_bb (basic_block bb
)
1065 edge_prediction
**preds
= bb_predictions
->get (bb
);
1069 hash_table
<predictor_hash_traits
> s (13);
1070 hash_set
<edge_prediction
*> remove
;
1072 /* Step 1: identify predictors that should be removed. */
1073 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1075 edge_prediction
*existing
= s
.find (pred
);
1078 if (pred
->ep_edge
== existing
->ep_edge
1079 && pred
->ep_probability
== existing
->ep_probability
)
1081 /* Remove a duplicate predictor. */
1082 dump_prediction (dump_file
, pred
->ep_predictor
,
1083 pred
->ep_probability
, bb
,
1084 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1088 else if (pred
->ep_edge
!= existing
->ep_edge
1089 && pred
->ep_probability
== existing
->ep_probability
1090 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1092 /* Remove both predictors as they predict the same
1094 dump_prediction (dump_file
, existing
->ep_predictor
,
1095 pred
->ep_probability
, bb
,
1096 REASON_EDGE_PAIR_DUPLICATE
,
1098 dump_prediction (dump_file
, pred
->ep_predictor
,
1099 pred
->ep_probability
, bb
,
1100 REASON_EDGE_PAIR_DUPLICATE
,
1103 remove
.add (existing
);
1108 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1112 /* Step 2: Remove predictors. */
1113 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1117 /* Combine predictions into single probability and store them into CFG.
1118 Remove now useless prediction entries.
1119 If DRY_RUN is set, only produce dumps and do not modify profile. */
1122 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1124 int best_probability
= PROB_EVEN
;
1125 enum br_predictor best_predictor
= END_PREDICTORS
;
1126 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1128 bool first_match
= false;
1130 struct edge_prediction
*pred
;
1132 edge e
, first
= NULL
, second
= NULL
;
1137 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1139 if (!unlikely_executed_edge_p (e
))
1142 if (first
&& !second
)
1147 else if (!e
->probability
.initialized_p ())
1148 e
->probability
= profile_probability::never ();
1149 if (!e
->probability
.initialized_p ())
1151 else if (e
->probability
== profile_probability::never ())
1155 /* When there is no successor or only one choice, prediction is easy.
1157 When we have a basic block with more than 2 successors, the situation
1158 is more complicated as DS theory cannot be used literally.
1159 More precisely, let's assume we predicted edge e1 with probability p1,
1160 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1161 need to find probability of e.g. m1({b2}), which we don't know.
1162 The only approximation is to equally distribute 1-p1 to all edges
1165 According to numbers we've got from SPEC2006 benchark, there's only
1166 one interesting reliable predictor (noreturn call), which can be
1167 handled with a bit easier approach. */
1170 hash_set
<edge
> unlikely_edges (4);
1172 /* Identify all edges that have a probability close to very unlikely.
1173 Doing the approach for very unlikely doesn't worth for doing as
1174 there's no such probability in SPEC2006 benchmark. */
1175 edge_prediction
**preds
= bb_predictions
->get (bb
);
1177 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1178 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
)
1179 unlikely_edges
.add (pred
->ep_edge
);
1182 set_even_probabilities (bb
, &unlikely_edges
);
1183 clear_bb_predictions (bb
);
1186 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1187 if (unlikely_edges
.elements () == 0)
1189 "%i edges in bb %i predicted to even probabilities\n",
1194 "%i edges in bb %i predicted with some unlikely edges\n",
1196 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1197 if (!unlikely_executed_edge_p (e
))
1198 dump_prediction (dump_file
, PRED_COMBINED
,
1199 e
->probability
.to_reg_br_prob_base (), bb
, REASON_NONE
, e
);
1206 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1208 prune_predictions_for_bb (bb
);
1210 edge_prediction
**preds
= bb_predictions
->get (bb
);
1214 /* We implement "first match" heuristics and use probability guessed
1215 by predictor with smallest index. */
1216 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1218 enum br_predictor predictor
= pred
->ep_predictor
;
1219 int probability
= pred
->ep_probability
;
1221 if (pred
->ep_edge
!= first
)
1222 probability
= REG_BR_PROB_BASE
- probability
;
1225 /* First match heuristics would be widly confused if we predicted
1227 if (best_predictor
> predictor
1228 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1230 struct edge_prediction
*pred2
;
1231 int prob
= probability
;
1233 for (pred2
= (struct edge_prediction
*) *preds
;
1234 pred2
; pred2
= pred2
->ep_next
)
1235 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1237 int probability2
= pred2
->ep_probability
;
1239 if (pred2
->ep_edge
!= first
)
1240 probability2
= REG_BR_PROB_BASE
- probability2
;
1242 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1243 (probability2
< REG_BR_PROB_BASE
/ 2))
1246 /* If the same predictor later gave better result, go for it! */
1247 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1248 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1249 prob
= probability2
;
1252 best_probability
= prob
, best_predictor
= predictor
;
1255 d
= (combined_probability
* probability
1256 + (REG_BR_PROB_BASE
- combined_probability
)
1257 * (REG_BR_PROB_BASE
- probability
));
1259 /* Use FP math to avoid overflows of 32bit integers. */
1261 /* If one probability is 0% and one 100%, avoid division by zero. */
1262 combined_probability
= REG_BR_PROB_BASE
/ 2;
1264 combined_probability
= (((double) combined_probability
)
1266 * REG_BR_PROB_BASE
/ d
+ 0.5);
1270 /* Decide which heuristic to use. In case we didn't match anything,
1271 use no_prediction heuristic, in case we did match, use either
1272 first match or Dempster-Shaffer theory depending on the flags. */
1274 if (best_predictor
!= END_PREDICTORS
)
1278 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1282 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1283 !first_match
? REASON_NONE
: REASON_IGNORED
);
1285 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1286 first_match
? REASON_NONE
: REASON_IGNORED
);
1290 combined_probability
= best_probability
;
1291 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1295 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1297 enum br_predictor predictor
= pred
->ep_predictor
;
1298 int probability
= pred
->ep_probability
;
1300 dump_prediction (dump_file
, predictor
, probability
, bb
,
1301 (!first_match
|| best_predictor
== predictor
)
1302 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1305 clear_bb_predictions (bb
);
1308 /* If we have only one successor which is unknown, we can compute missing
1312 profile_probability prob
= profile_probability::always ();
1313 edge missing
= NULL
;
1315 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1316 if (e
->probability
.initialized_p ())
1317 prob
-= e
->probability
;
1318 else if (missing
== NULL
)
1322 missing
->probability
= prob
;
1324 /* If nothing is unknown, we have nothing to update. */
1325 else if (!nunknown
&& nzero
!= (int)EDGE_COUNT (bb
->succs
))
1330 = profile_probability::from_reg_br_prob_base (combined_probability
);
1331 second
->probability
= first
->probability
.invert ();
1335 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1336 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1338 T1 and T2 should be one of the following cases:
1339 1. T1 is SSA_NAME, T2 is NULL
1340 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1341 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1344 strips_small_constant (tree t1
, tree t2
)
1351 else if (TREE_CODE (t1
) == SSA_NAME
)
1353 else if (tree_fits_shwi_p (t1
))
1354 value
= tree_to_shwi (t1
);
1360 else if (tree_fits_shwi_p (t2
))
1361 value
= tree_to_shwi (t2
);
1362 else if (TREE_CODE (t2
) == SSA_NAME
)
1370 if (value
<= 4 && value
>= -4)
1376 /* Return the SSA_NAME in T or T's operands.
1377 Return NULL if SSA_NAME cannot be found. */
1380 get_base_value (tree t
)
1382 if (TREE_CODE (t
) == SSA_NAME
)
1385 if (!BINARY_CLASS_P (t
))
1388 switch (TREE_OPERAND_LENGTH (t
))
1391 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1393 return strips_small_constant (TREE_OPERAND (t
, 0),
1394 TREE_OPERAND (t
, 1));
1400 /* Check the compare STMT in LOOP. If it compares an induction
1401 variable to a loop invariant, return true, and save
1402 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1403 Otherwise return false and set LOOP_INVAIANT to NULL. */
1406 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1407 tree
*loop_invariant
,
1408 enum tree_code
*compare_code
,
1412 tree op0
, op1
, bound
, base
;
1414 enum tree_code code
;
1417 code
= gimple_cond_code (stmt
);
1418 *loop_invariant
= NULL
;
1434 op0
= gimple_cond_lhs (stmt
);
1435 op1
= gimple_cond_rhs (stmt
);
1437 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1438 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1440 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1442 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1444 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1445 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1447 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1448 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1451 if (integer_zerop (iv0
.step
))
1453 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1454 code
= invert_tree_comparison (code
, false);
1457 if (tree_fits_shwi_p (iv1
.step
))
1466 if (tree_fits_shwi_p (iv0
.step
))
1472 if (TREE_CODE (bound
) != INTEGER_CST
)
1473 bound
= get_base_value (bound
);
1476 if (TREE_CODE (base
) != INTEGER_CST
)
1477 base
= get_base_value (base
);
1481 *loop_invariant
= bound
;
1482 *compare_code
= code
;
1484 *loop_iv_base
= base
;
1488 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1491 expr_coherent_p (tree t1
, tree t2
)
1494 tree ssa_name_1
= NULL
;
1495 tree ssa_name_2
= NULL
;
1497 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1498 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1503 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1505 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1508 /* Check to see if t1 is expressed/defined with t2. */
1509 stmt
= SSA_NAME_DEF_STMT (t1
);
1510 gcc_assert (stmt
!= NULL
);
1511 if (is_gimple_assign (stmt
))
1513 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1514 if (ssa_name_1
&& ssa_name_1
== t2
)
1518 /* Check to see if t2 is expressed/defined with t1. */
1519 stmt
= SSA_NAME_DEF_STMT (t2
);
1520 gcc_assert (stmt
!= NULL
);
1521 if (is_gimple_assign (stmt
))
1523 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1524 if (ssa_name_2
&& ssa_name_2
== t1
)
1528 /* Compare if t1 and t2's def_stmts are identical. */
1529 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1535 /* Return true if E is predicted by one of loop heuristics. */
1538 predicted_by_loop_heuristics_p (basic_block bb
)
1540 struct edge_prediction
*i
;
1541 edge_prediction
**preds
= bb_predictions
->get (bb
);
1546 for (i
= *preds
; i
; i
= i
->ep_next
)
1547 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1548 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1549 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1550 || i
->ep_predictor
== PRED_LOOP_EXIT
1551 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1552 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1557 /* Predict branch probability of BB when BB contains a branch that compares
1558 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1559 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1562 for (int i = 0; i < bound; i++) {
1569 In this loop, we will predict the branch inside the loop to be taken. */
1572 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1573 tree loop_bound_var
,
1574 tree loop_iv_base_var
,
1575 enum tree_code loop_bound_code
,
1576 int loop_bound_step
)
1579 tree compare_var
, compare_base
;
1580 enum tree_code compare_code
;
1581 tree compare_step_var
;
1585 if (predicted_by_loop_heuristics_p (bb
))
1588 stmt
= last_stmt (bb
);
1589 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1591 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1598 /* Find the taken edge. */
1599 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1600 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1603 /* When comparing an IV to a loop invariant, NE is more likely to be
1604 taken while EQ is more likely to be not-taken. */
1605 if (compare_code
== NE_EXPR
)
1607 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1610 else if (compare_code
== EQ_EXPR
)
1612 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1616 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1619 /* If loop bound, base and compare bound are all constants, we can
1620 calculate the probability directly. */
1621 if (tree_fits_shwi_p (loop_bound_var
)
1622 && tree_fits_shwi_p (compare_var
)
1623 && tree_fits_shwi_p (compare_base
))
1626 bool overflow
, overall_overflow
= false;
1627 widest_int compare_count
, tem
;
1629 /* (loop_bound - base) / compare_step */
1630 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1631 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1632 overall_overflow
|= overflow
;
1633 widest_int loop_count
= wi::div_trunc (tem
,
1634 wi::to_widest (compare_step_var
),
1636 overall_overflow
|= overflow
;
1638 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1639 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1641 /* (loop_bound - compare_bound) / compare_step */
1642 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1643 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1644 overall_overflow
|= overflow
;
1645 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1647 overall_overflow
|= overflow
;
1651 /* (compare_bound - base) / compare_step */
1652 tem
= wi::sub (wi::to_widest (compare_var
),
1653 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1654 overall_overflow
|= overflow
;
1655 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1657 overall_overflow
|= overflow
;
1659 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1661 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1663 if (wi::neg_p (compare_count
))
1665 if (wi::neg_p (loop_count
))
1667 if (loop_count
== 0)
1669 else if (wi::cmps (compare_count
, loop_count
) == 1)
1670 probability
= REG_BR_PROB_BASE
;
1673 tem
= compare_count
* REG_BR_PROB_BASE
;
1674 tem
= wi::udiv_trunc (tem
, loop_count
);
1675 probability
= tem
.to_uhwi ();
1678 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1679 if (!overall_overflow
)
1680 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1685 if (expr_coherent_p (loop_bound_var
, compare_var
))
1687 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1688 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1689 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1690 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1691 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1692 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1693 else if (loop_bound_code
== NE_EXPR
)
1695 /* If the loop backedge condition is "(i != bound)", we do
1696 the comparison based on the step of IV:
1697 * step < 0 : backedge condition is like (i > bound)
1698 * step > 0 : backedge condition is like (i < bound) */
1699 gcc_assert (loop_bound_step
!= 0);
1700 if (loop_bound_step
> 0
1701 && (compare_code
== LT_EXPR
1702 || compare_code
== LE_EXPR
))
1703 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1704 else if (loop_bound_step
< 0
1705 && (compare_code
== GT_EXPR
1706 || compare_code
== GE_EXPR
))
1707 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1709 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1712 /* The branch is predicted not-taken if loop_bound_code is
1713 opposite with compare_code. */
1714 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1716 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1719 for (i = s; i < h; i++)
1721 The branch should be predicted taken. */
1722 if (loop_bound_step
> 0
1723 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1724 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1725 else if (loop_bound_step
< 0
1726 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1727 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1729 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1733 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1734 exits are resulted from short-circuit conditions that will generate an
1737 if (foo() || global > 10)
1740 This will be translated into:
1745 if foo() goto BB6 else goto BB5
1747 if global > 10 goto BB6 else goto BB7
1751 iftmp = (PHI 0(BB5), 1(BB6))
1752 if iftmp == 1 goto BB8 else goto BB3
1754 outside of the loop...
1756 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1757 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1758 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1759 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1762 predict_extra_loop_exits (edge exit_edge
)
1765 bool check_value_one
;
1766 gimple
*lhs_def_stmt
;
1768 tree cmp_rhs
, cmp_lhs
;
1772 last
= last_stmt (exit_edge
->src
);
1775 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1779 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1780 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1781 if (!TREE_CONSTANT (cmp_rhs
)
1782 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1784 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1787 /* If check_value_one is true, only the phi_args with value '1' will lead
1788 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1790 check_value_one
= (((integer_onep (cmp_rhs
))
1791 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1792 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1794 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1798 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1802 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1806 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1807 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1809 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1811 if ((check_value_one
^ integer_onep (val
)) == 1)
1813 if (EDGE_COUNT (e
->src
->succs
) != 1)
1815 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1819 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1820 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1825 /* Predict edge probabilities by exploiting loop structure. */
1828 predict_loops (void)
1832 hash_set
<struct loop
*> with_recursion(10);
1834 FOR_EACH_BB_FN (bb
, cfun
)
1836 gimple_stmt_iterator gsi
;
1839 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1840 if (is_gimple_call (gsi_stmt (gsi
))
1841 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1842 && recursive_call_p (current_function_decl
, decl
))
1844 loop
= bb
->loop_father
;
1845 while (loop
&& !with_recursion
.add (loop
))
1846 loop
= loop_outer (loop
);
1850 /* Try to predict out blocks in a loop that are not part of a
1852 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1854 basic_block bb
, *bbs
;
1855 unsigned j
, n_exits
= 0;
1857 struct tree_niter_desc niter_desc
;
1859 struct nb_iter_bound
*nb_iter
;
1860 enum tree_code loop_bound_code
= ERROR_MARK
;
1861 tree loop_bound_step
= NULL
;
1862 tree loop_bound_var
= NULL
;
1863 tree loop_iv_base
= NULL
;
1865 bool recursion
= with_recursion
.contains (loop
);
1867 exits
= get_loop_exit_edges (loop
);
1868 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1869 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1877 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1878 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1879 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1880 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1881 && max_loop_iterations_int (loop
) >= 0)
1884 "Loop %d iterates at most %i times.\n", loop
->num
,
1885 (int)max_loop_iterations_int (loop
));
1887 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1888 && likely_max_loop_iterations_int (loop
) >= 0)
1890 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1891 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1894 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1897 HOST_WIDE_INT nitercst
;
1898 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1900 enum br_predictor predictor
;
1903 if (unlikely_executed_edge_p (ex
)
1904 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
1906 /* Loop heuristics do not expect exit conditional to be inside
1907 inner loop. We predict from innermost to outermost loop. */
1908 if (predicted_by_loop_heuristics_p (ex
->src
))
1910 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1911 fprintf (dump_file
, "Skipping exit %i->%i because "
1912 "it is already predicted.\n",
1913 ex
->src
->index
, ex
->dest
->index
);
1916 predict_extra_loop_exits (ex
);
1918 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1919 niter
= niter_desc
.niter
;
1920 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1921 niter
= loop_niter_by_eval (loop
, ex
);
1922 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1923 && TREE_CODE (niter
) == INTEGER_CST
)
1925 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1926 ex
->src
->index
, ex
->dest
->index
,
1928 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1929 fprintf (dump_file
, " times.\n");
1932 if (TREE_CODE (niter
) == INTEGER_CST
)
1934 if (tree_fits_uhwi_p (niter
)
1936 && compare_tree_int (niter
, max
- 1) == -1)
1937 nitercst
= tree_to_uhwi (niter
) + 1;
1940 predictor
= PRED_LOOP_ITERATIONS
;
1942 /* If we have just one exit and we can derive some information about
1943 the number of iterations of the loop from the statements inside
1944 the loop, use it to predict this exit. */
1945 else if (n_exits
== 1
1946 && estimated_stmt_executions (loop
, &nit
))
1948 if (wi::gtu_p (nit
, max
))
1951 nitercst
= nit
.to_shwi ();
1952 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1954 /* If we have likely upper bound, trust it for very small iteration
1955 counts. Such loops would otherwise get mispredicted by standard
1956 LOOP_EXIT heuristics. */
1957 else if (n_exits
== 1
1958 && likely_max_stmt_executions (loop
, &nit
)
1960 RDIV (REG_BR_PROB_BASE
,
1964 ? PRED_LOOP_EXIT_WITH_RECURSION
1965 : PRED_LOOP_EXIT
].hitrate
)))
1967 nitercst
= nit
.to_shwi ();
1968 predictor
= PRED_LOOP_ITERATIONS_MAX
;
1972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1973 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
1974 ex
->src
->index
, ex
->dest
->index
);
1978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1979 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
1980 (int)nitercst
, predictor_info
[predictor
].name
);
1981 /* If the prediction for number of iterations is zero, do not
1982 predict the exit edges. */
1986 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
1987 predict_edge (ex
, predictor
, probability
);
1991 /* Find information about loop bound variables. */
1992 for (nb_iter
= loop
->bounds
; nb_iter
;
1993 nb_iter
= nb_iter
->next
)
1995 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1997 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
2000 if (!stmt
&& last_stmt (loop
->header
)
2001 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
2002 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2004 is_comparison_with_loop_invariant_p (stmt
, loop
,
2010 bbs
= get_loop_body (loop
);
2012 for (j
= 0; j
< loop
->num_nodes
; j
++)
2019 /* Bypass loop heuristics on continue statement. These
2020 statements construct loops via "non-loop" constructs
2021 in the source language and are better to be handled
2023 if (predicted_by_p (bb
, PRED_CONTINUE
))
2025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2026 fprintf (dump_file
, "BB %i predicted by continue.\n",
2031 /* If we already used more reliable loop exit predictors, do not
2032 bother with PRED_LOOP_EXIT. */
2033 if (!predicted_by_loop_heuristics_p (bb
))
2035 /* For loop with many exits we don't want to predict all exits
2036 with the pretty large probability, because if all exits are
2037 considered in row, the loop would be predicted to iterate
2038 almost never. The code to divide probability by number of
2039 exits is very rough. It should compute the number of exits
2040 taken in each patch through function (not the overall number
2041 of exits that might be a lot higher for loops with wide switch
2042 statements in them) and compute n-th square root.
2044 We limit the minimal probability by 2% to avoid
2045 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2046 as this was causing regression in perl benchmark containing such
2049 int probability
= ((REG_BR_PROB_BASE
2052 ? PRED_LOOP_EXIT_WITH_RECURSION
2053 : PRED_LOOP_EXIT
].hitrate
)
2055 if (probability
< HITRATE (2))
2056 probability
= HITRATE (2);
2057 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2058 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2059 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2061 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2063 "Predicting exit %i->%i with prob %i.\n",
2064 e
->src
->index
, e
->dest
->index
, probability
);
2066 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2067 : PRED_LOOP_EXIT
, probability
);
2071 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2073 tree_to_shwi (loop_bound_step
));
2076 /* In the following code
2081 guess that cond is unlikely. */
2082 if (loop_outer (loop
)->num
)
2084 basic_block bb
= NULL
;
2085 edge preheader_edge
= loop_preheader_edge (loop
);
2087 if (single_pred_p (preheader_edge
->src
)
2088 && single_succ_p (preheader_edge
->src
))
2089 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2091 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2092 /* Pattern match fortran loop preheader:
2093 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2094 _17 = (logical(kind=4)) _16;
2100 Loop guard branch prediction says nothing about duplicated loop
2101 headers produced by fortran frontend and in this case we want
2102 to predict paths leading to this preheader. */
2105 && gimple_code (stmt
) == GIMPLE_COND
2106 && gimple_cond_code (stmt
) == NE_EXPR
2107 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2108 && integer_zerop (gimple_cond_rhs (stmt
)))
2110 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2111 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2112 && gimple_expr_code (call_stmt
) == NOP_EXPR
2113 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2114 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2115 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2116 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2117 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2118 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2119 == PRED_FORTRAN_LOOP_PREHEADER
)
2120 bb
= preheader_edge
->src
;
2124 if (!dominated_by_p (CDI_DOMINATORS
,
2125 loop_outer (loop
)->latch
, loop
->header
))
2126 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2128 ? PRED_LOOP_GUARD_WITH_RECURSION
2135 if (!dominated_by_p (CDI_DOMINATORS
,
2136 loop_outer (loop
)->latch
, bb
))
2137 predict_paths_leading_to (bb
,
2139 ? PRED_LOOP_GUARD_WITH_RECURSION
2146 /* Free basic blocks from get_loop_body. */
2151 /* Attempt to predict probabilities of BB outgoing edges using local
2154 bb_estimate_probability_locally (basic_block bb
)
2156 rtx_insn
*last_insn
= BB_END (bb
);
2159 if (! can_predict_insn_p (last_insn
))
2161 cond
= get_condition (last_insn
, NULL
, false, false);
2165 /* Try "pointer heuristic."
2166 A comparison ptr == 0 is predicted as false.
2167 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2168 if (COMPARISON_P (cond
)
2169 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2170 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2172 if (GET_CODE (cond
) == EQ
)
2173 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2174 else if (GET_CODE (cond
) == NE
)
2175 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2179 /* Try "opcode heuristic."
2180 EQ tests are usually false and NE tests are usually true. Also,
2181 most quantities are positive, so we can make the appropriate guesses
2182 about signed comparisons against zero. */
2183 switch (GET_CODE (cond
))
2186 /* Unconditional branch. */
2187 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2188 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2193 /* Floating point comparisons appears to behave in a very
2194 unpredictable way because of special role of = tests in
2196 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2198 /* Comparisons with 0 are often used for booleans and there is
2199 nothing useful to predict about them. */
2200 else if (XEXP (cond
, 1) == const0_rtx
2201 || XEXP (cond
, 0) == const0_rtx
)
2204 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2209 /* Floating point comparisons appears to behave in a very
2210 unpredictable way because of special role of = tests in
2212 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2214 /* Comparisons with 0 are often used for booleans and there is
2215 nothing useful to predict about them. */
2216 else if (XEXP (cond
, 1) == const0_rtx
2217 || XEXP (cond
, 0) == const0_rtx
)
2220 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2224 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2228 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2233 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2234 || XEXP (cond
, 1) == constm1_rtx
)
2235 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2240 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2241 || XEXP (cond
, 1) == constm1_rtx
)
2242 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2250 /* Set edge->probability for each successor edge of BB. */
2252 guess_outgoing_edge_probabilities (basic_block bb
)
2254 bb_estimate_probability_locally (bb
);
2255 combine_predictions_for_insn (BB_END (bb
), bb
);
2258 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
2260 /* Helper function for expr_expected_value. */
2263 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2264 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
2269 *predictor
= PRED_UNCONDITIONAL
;
2271 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2273 if (TREE_CONSTANT (op0
))
2276 if (code
== IMAGPART_EXPR
)
2278 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2280 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2281 if (is_gimple_call (def
)
2282 && gimple_call_internal_p (def
)
2283 && (gimple_call_internal_fn (def
)
2284 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2286 /* Assume that any given atomic operation has low contention,
2287 and thus the compare-and-swap operation succeeds. */
2289 *predictor
= PRED_COMPARE_AND_SWAP
;
2290 return build_one_cst (TREE_TYPE (op0
));
2295 if (code
!= SSA_NAME
)
2298 def
= SSA_NAME_DEF_STMT (op0
);
2300 /* If we were already here, break the infinite cycle. */
2301 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2304 if (gimple_code (def
) == GIMPLE_PHI
)
2306 /* All the arguments of the PHI node must have the same constant
2308 int i
, n
= gimple_phi_num_args (def
);
2309 tree val
= NULL
, new_val
;
2311 for (i
= 0; i
< n
; i
++)
2313 tree arg
= PHI_ARG_DEF (def
, i
);
2314 enum br_predictor predictor2
;
2316 /* If this PHI has itself as an argument, we cannot
2317 determine the string length of this argument. However,
2318 if we can find an expected constant value for the other
2319 PHI args then we can still be sure that this is
2320 likely a constant. So be optimistic and just
2321 continue with the next argument. */
2322 if (arg
== PHI_RESULT (def
))
2325 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
2327 /* It is difficult to combine value predictors. Simply assume
2328 that later predictor is weaker and take its prediction. */
2329 if (predictor
&& *predictor
< predictor2
)
2330 *predictor
= predictor2
;
2335 else if (!operand_equal_p (val
, new_val
, false))
2340 if (is_gimple_assign (def
))
2342 if (gimple_assign_lhs (def
) != op0
)
2345 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2346 gimple_assign_rhs1 (def
),
2347 gimple_assign_rhs_code (def
),
2348 gimple_assign_rhs2 (def
),
2349 visited
, predictor
);
2352 if (is_gimple_call (def
))
2354 tree decl
= gimple_call_fndecl (def
);
2357 if (gimple_call_internal_p (def
)
2358 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2360 gcc_assert (gimple_call_num_args (def
) == 3);
2361 tree val
= gimple_call_arg (def
, 0);
2362 if (TREE_CONSTANT (val
))
2366 tree val2
= gimple_call_arg (def
, 2);
2367 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2368 && tree_fits_uhwi_p (val2
)
2369 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2370 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2372 return gimple_call_arg (def
, 1);
2376 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2377 switch (DECL_FUNCTION_CODE (decl
))
2379 case BUILT_IN_EXPECT
:
2382 if (gimple_call_num_args (def
) != 2)
2384 val
= gimple_call_arg (def
, 0);
2385 if (TREE_CONSTANT (val
))
2388 *predictor
= PRED_BUILTIN_EXPECT
;
2389 return gimple_call_arg (def
, 1);
2392 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2393 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2394 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2395 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2396 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2397 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2398 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2399 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2400 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2401 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2402 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2403 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2404 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2405 /* Assume that any given atomic operation has low contention,
2406 and thus the compare-and-swap operation succeeds. */
2408 *predictor
= PRED_COMPARE_AND_SWAP
;
2409 return boolean_true_node
;
2418 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2421 enum br_predictor predictor2
;
2422 op0
= expr_expected_value (op0
, visited
, predictor
);
2425 op1
= expr_expected_value (op1
, visited
, &predictor2
);
2426 if (predictor
&& *predictor
< predictor2
)
2427 *predictor
= predictor2
;
2430 res
= fold_build2 (code
, type
, op0
, op1
);
2431 if (TREE_CONSTANT (res
))
2435 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2438 op0
= expr_expected_value (op0
, visited
, predictor
);
2441 res
= fold_build1 (code
, type
, op0
);
2442 if (TREE_CONSTANT (res
))
2449 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2450 The function is used by builtin_expect branch predictor so the evidence
2451 must come from this construct and additional possible constant folding.
2453 We may want to implement more involved value guess (such as value range
2454 propagation based prediction), but such tricks shall go to new
2458 expr_expected_value (tree expr
, bitmap visited
,
2459 enum br_predictor
*predictor
)
2461 enum tree_code code
;
2464 if (TREE_CONSTANT (expr
))
2467 *predictor
= PRED_UNCONDITIONAL
;
2471 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2472 return expr_expected_value_1 (TREE_TYPE (expr
),
2473 op0
, code
, op1
, visited
, predictor
);
2476 /* Predict using opcode of the last statement in basic block. */
2478 tree_predict_by_opcode (basic_block bb
)
2480 gimple
*stmt
= last_stmt (bb
);
2487 enum br_predictor predictor
;
2489 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2491 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2492 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2494 op0
= gimple_cond_lhs (stmt
);
2495 op1
= gimple_cond_rhs (stmt
);
2496 cmp
= gimple_cond_code (stmt
);
2497 type
= TREE_TYPE (op0
);
2498 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2500 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2502 if (predictor
== PRED_BUILTIN_EXPECT
)
2504 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2506 gcc_assert (percent
>= 0 && percent
<= 100);
2507 if (integer_zerop (val
))
2508 percent
= 100 - percent
;
2509 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2512 predict_edge_def (then_edge
, predictor
,
2513 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2515 /* Try "pointer heuristic."
2516 A comparison ptr == 0 is predicted as false.
2517 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2518 if (POINTER_TYPE_P (type
))
2521 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2522 else if (cmp
== NE_EXPR
)
2523 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2527 /* Try "opcode heuristic."
2528 EQ tests are usually false and NE tests are usually true. Also,
2529 most quantities are positive, so we can make the appropriate guesses
2530 about signed comparisons against zero. */
2535 /* Floating point comparisons appears to behave in a very
2536 unpredictable way because of special role of = tests in
2538 if (FLOAT_TYPE_P (type
))
2540 /* Comparisons with 0 are often used for booleans and there is
2541 nothing useful to predict about them. */
2542 else if (integer_zerop (op0
) || integer_zerop (op1
))
2545 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2550 /* Floating point comparisons appears to behave in a very
2551 unpredictable way because of special role of = tests in
2553 if (FLOAT_TYPE_P (type
))
2555 /* Comparisons with 0 are often used for booleans and there is
2556 nothing useful to predict about them. */
2557 else if (integer_zerop (op0
)
2558 || integer_zerop (op1
))
2561 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2565 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2568 case UNORDERED_EXPR
:
2569 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2574 if (integer_zerop (op1
)
2575 || integer_onep (op1
)
2576 || integer_all_onesp (op1
)
2579 || real_minus_onep (op1
))
2580 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2585 if (integer_zerop (op1
)
2586 || integer_onep (op1
)
2587 || integer_all_onesp (op1
)
2590 || real_minus_onep (op1
))
2591 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2599 /* Returns TRUE if the STMT is exit(0) like statement. */
2602 is_exit_with_zero_arg (const gimple
*stmt
)
2604 /* This is not exit, _exit or _Exit. */
2605 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2606 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2607 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2610 /* Argument is an interger zero. */
2611 return integer_zerop (gimple_call_arg (stmt
, 0));
2614 /* Try to guess whether the value of return means error code. */
2616 static enum br_predictor
2617 return_prediction (tree val
, enum prediction
*prediction
)
2621 return PRED_NO_PREDICTION
;
2622 /* Different heuristics for pointers and scalars. */
2623 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2625 /* NULL is usually not returned. */
2626 if (integer_zerop (val
))
2628 *prediction
= NOT_TAKEN
;
2629 return PRED_NULL_RETURN
;
2632 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2634 /* Negative return values are often used to indicate
2636 if (TREE_CODE (val
) == INTEGER_CST
2637 && tree_int_cst_sgn (val
) < 0)
2639 *prediction
= NOT_TAKEN
;
2640 return PRED_NEGATIVE_RETURN
;
2642 /* Constant return values seems to be commonly taken.
2643 Zero/one often represent booleans so exclude them from the
2645 if (TREE_CONSTANT (val
)
2646 && (!integer_zerop (val
) && !integer_onep (val
)))
2648 *prediction
= NOT_TAKEN
;
2649 return PRED_CONST_RETURN
;
2652 return PRED_NO_PREDICTION
;
2655 /* Return zero if phi result could have values other than -1, 0 or 1,
2656 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2657 values are used or likely. */
2660 zero_one_minusone (gphi
*phi
, int limit
)
2662 int phi_num_args
= gimple_phi_num_args (phi
);
2664 for (int i
= 0; i
< phi_num_args
; i
++)
2666 tree t
= PHI_ARG_DEF (phi
, i
);
2667 if (TREE_CODE (t
) != INTEGER_CST
)
2669 wide_int w
= wi::to_wide (t
);
2679 for (int i
= 0; i
< phi_num_args
; i
++)
2681 tree t
= PHI_ARG_DEF (phi
, i
);
2682 if (TREE_CODE (t
) == INTEGER_CST
)
2684 if (TREE_CODE (t
) != SSA_NAME
)
2686 gimple
*g
= SSA_NAME_DEF_STMT (t
);
2687 if (gimple_code (g
) == GIMPLE_PHI
&& limit
> 0)
2688 if (int r
= zero_one_minusone (as_a
<gphi
*> (g
), limit
- 1))
2693 if (!is_gimple_assign (g
))
2695 if (gimple_assign_cast_p (g
))
2697 tree rhs1
= gimple_assign_rhs1 (g
);
2698 if (TREE_CODE (rhs1
) != SSA_NAME
2699 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1
))
2700 || TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2701 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2706 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g
)) != tcc_comparison
)
2713 /* Find the basic block with return expression and look up for possible
2714 return value trying to apply RETURN_PREDICTION heuristics. */
2716 apply_return_prediction (void)
2718 greturn
*return_stmt
= NULL
;
2722 int phi_num_args
, i
;
2723 enum br_predictor pred
;
2724 enum prediction direction
;
2727 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2729 gimple
*last
= last_stmt (e
->src
);
2731 && gimple_code (last
) == GIMPLE_RETURN
)
2733 return_stmt
= as_a
<greturn
*> (last
);
2739 return_val
= gimple_return_retval (return_stmt
);
2742 if (TREE_CODE (return_val
) != SSA_NAME
2743 || !SSA_NAME_DEF_STMT (return_val
)
2744 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2746 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2747 phi_num_args
= gimple_phi_num_args (phi
);
2748 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2750 /* Avoid the case where the function returns -1, 0 and 1 values and
2751 nothing else. Those could be qsort etc. comparison functions
2752 where the negative return isn't less probable than positive.
2753 For this require that the function returns at least -1 or 1
2754 or -1 and a boolean value or comparison result, so that functions
2755 returning just -1 and 0 are treated as if -1 represents error value. */
2756 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val
))
2757 && !TYPE_UNSIGNED (TREE_TYPE (return_val
))
2758 && TYPE_PRECISION (TREE_TYPE (return_val
)) > 1)
2759 if (int r
= zero_one_minusone (phi
, 3))
2760 if ((r
& (1 | 4)) == (1 | 4))
2763 /* Avoid the degenerate case where all return values form the function
2764 belongs to same category (ie they are all positive constants)
2765 so we can hardly say something about them. */
2766 for (i
= 1; i
< phi_num_args
; i
++)
2767 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2769 if (i
!= phi_num_args
)
2770 for (i
= 0; i
< phi_num_args
; i
++)
2772 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2773 if (pred
!= PRED_NO_PREDICTION
)
2774 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2779 /* Look for basic block that contains unlikely to happen events
2780 (such as noreturn calls) and mark all paths leading to execution
2781 of this basic blocks as unlikely. */
2784 tree_bb_level_predictions (void)
2787 bool has_return_edges
= false;
2791 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2792 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2794 has_return_edges
= true;
2798 apply_return_prediction ();
2800 FOR_EACH_BB_FN (bb
, cfun
)
2802 gimple_stmt_iterator gsi
;
2804 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2806 gimple
*stmt
= gsi_stmt (gsi
);
2809 if (is_gimple_call (stmt
))
2811 if (gimple_call_noreturn_p (stmt
)
2813 && !is_exit_with_zero_arg (stmt
))
2814 predict_paths_leading_to (bb
, PRED_NORETURN
,
2816 decl
= gimple_call_fndecl (stmt
);
2818 && lookup_attribute ("cold",
2819 DECL_ATTRIBUTES (decl
)))
2820 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2822 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2823 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2826 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2828 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2829 gimple_predict_outcome (stmt
));
2830 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2831 hints to callers. */
2837 /* Callback for hash_map::traverse, asserts that the pointer map is
2841 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2844 gcc_assert (!value
);
2848 /* Predict branch probabilities and estimate profile for basic block BB.
2849 When LOCAL_ONLY is set do not use any global properties of CFG. */
2852 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
2857 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2859 /* Look for block we are guarding (ie we dominate it,
2860 but it doesn't postdominate us). */
2861 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2863 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2864 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2866 gimple_stmt_iterator bi
;
2868 /* The call heuristic claims that a guarded function call
2869 is improbable. This is because such calls are often used
2870 to signal exceptional situations such as printing error
2872 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2875 gimple
*stmt
= gsi_stmt (bi
);
2876 if (is_gimple_call (stmt
)
2877 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
2878 /* Constant and pure calls are hardly used to signalize
2879 something exceptional. */
2880 && gimple_has_side_effects (stmt
))
2882 if (gimple_call_fndecl (stmt
))
2883 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2884 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
2885 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
2887 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
2893 tree_predict_by_opcode (bb
);
2896 /* Predict branch probabilities and estimate profile of the tree CFG.
2897 This function can be called from the loop optimizers to recompute
2898 the profile information.
2899 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2902 tree_estimate_probability (bool dry_run
)
2906 add_noreturn_fake_exit_edges ();
2907 connect_infinite_loops_to_exit ();
2908 /* We use loop_niter_by_eval, which requires that the loops have
2910 create_preheaders (CP_SIMPLE_PREHEADERS
);
2911 calculate_dominance_info (CDI_POST_DOMINATORS
);
2913 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2914 tree_bb_level_predictions ();
2915 record_loop_exits ();
2917 if (number_of_loops (cfun
) > 1)
2920 FOR_EACH_BB_FN (bb
, cfun
)
2921 tree_estimate_probability_bb (bb
, false);
2923 FOR_EACH_BB_FN (bb
, cfun
)
2924 combine_predictions_for_bb (bb
, dry_run
);
2927 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2929 delete bb_predictions
;
2930 bb_predictions
= NULL
;
2933 estimate_bb_frequencies (false);
2934 free_dominance_info (CDI_POST_DOMINATORS
);
2935 remove_fake_exit_edges ();
2938 /* Set edge->probability for each successor edge of BB. */
2940 tree_guess_outgoing_edge_probabilities (basic_block bb
)
2942 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2943 tree_estimate_probability_bb (bb
, true);
2944 combine_predictions_for_bb (bb
, false);
2946 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2947 delete bb_predictions
;
2948 bb_predictions
= NULL
;
2951 /* Predict edges to successors of CUR whose sources are not postdominated by
2952 BB by PRED and recurse to all postdominators. */
2955 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2956 enum br_predictor pred
,
2957 enum prediction taken
,
2958 bitmap visited
, struct loop
*in_loop
= NULL
)
2964 /* If we exited the loop or CUR is unconditional in the loop, there is
2967 && (!flow_bb_inside_loop_p (in_loop
, cur
)
2968 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
2971 /* We are looking for all edges forming edge cut induced by
2972 set of all blocks postdominated by BB. */
2973 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2974 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2975 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2981 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2982 if (unlikely_executed_edge_p (e
))
2984 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2986 /* See if there is an edge from e->src that is not abnormal
2987 and does not lead to BB and does not exit the loop. */
2988 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2990 && !unlikely_executed_edge_p (e2
)
2991 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
2992 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
2998 /* If there is non-abnormal path leaving e->src, predict edge
2999 using predictor. Otherwise we need to look for paths
3002 The second may lead to infinite loop in the case we are predicitng
3003 regions that are only reachable by abnormal edges. We simply
3004 prevent visiting given BB twice. */
3007 if (!edge_predicted_by_p (e
, pred
, taken
))
3008 predict_edge_def (e
, pred
, taken
);
3010 else if (bitmap_set_bit (visited
, e
->src
->index
))
3011 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
3013 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
3015 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
3016 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
3019 /* Sets branch probabilities according to PREDiction and
3023 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
3024 enum prediction taken
, struct loop
*in_loop
)
3026 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3029 /* Like predict_paths_leading_to but take edge instead of basic block. */
3032 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
3033 enum prediction taken
, struct loop
*in_loop
)
3035 bool has_nonloop_edge
= false;
3039 basic_block bb
= e
->src
;
3040 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
3041 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
3042 && !unlikely_executed_edge_p (e
)
3043 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
3045 has_nonloop_edge
= true;
3048 if (!has_nonloop_edge
)
3050 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
3053 predict_edge_def (e
, pred
, taken
);
3056 /* This is used to carry information about basic blocks. It is
3057 attached to the AUX field of the standard CFG block. */
3061 /* Estimated frequency of execution of basic_block. */
3064 /* To keep queue of basic blocks to process. */
3067 /* Number of predecessors we need to visit first. */
3071 /* Similar information for edges. */
3072 struct edge_prob_info
3074 /* In case edge is a loopback edge, the probability edge will be reached
3075 in case header is. Estimated number of iterations of the loop can be
3076 then computed as 1 / (1 - back_edge_prob). */
3077 sreal back_edge_prob
;
3078 /* True if the edge is a loopback edge in the natural loop. */
3079 unsigned int back_edge
:1;
3082 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3084 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3086 /* Helper function for estimate_bb_frequencies.
3087 Propagate the frequencies in blocks marked in
3088 TOVISIT, starting in HEAD. */
3091 propagate_freq (basic_block head
, bitmap tovisit
)
3100 /* For each basic block we need to visit count number of his predecessors
3101 we need to visit first. */
3102 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
3107 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
3109 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3111 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
3113 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3115 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3117 "Irreducible region hit, ignoring edge to %i->%i\n",
3118 e
->src
->index
, bb
->index
);
3120 BLOCK_INFO (bb
)->npredecessors
= count
;
3121 /* When function never returns, we will never process exit block. */
3122 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3123 bb
->count
= profile_count::zero ();
3126 BLOCK_INFO (head
)->frequency
= 1;
3128 for (bb
= head
; bb
; bb
= nextbb
)
3131 sreal cyclic_probability
= 0;
3132 sreal frequency
= 0;
3134 nextbb
= BLOCK_INFO (bb
)->next
;
3135 BLOCK_INFO (bb
)->next
= NULL
;
3137 /* Compute frequency of basic block. */
3141 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3142 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3143 || (e
->flags
& EDGE_DFS_BACK
));
3145 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3146 if (EDGE_INFO (e
)->back_edge
)
3148 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3150 else if (!(e
->flags
& EDGE_DFS_BACK
))
3152 /* frequency += (e->probability
3153 * BLOCK_INFO (e->src)->frequency /
3154 REG_BR_PROB_BASE); */
3156 /* FIXME: Graphite is producing edges with no profile. Once
3157 this is fixed, drop this. */
3158 sreal tmp
= e
->probability
.initialized_p () ?
3159 e
->probability
.to_reg_br_prob_base () : 0;
3160 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
3161 tmp
*= real_inv_br_prob_base
;
3165 if (cyclic_probability
== 0)
3167 BLOCK_INFO (bb
)->frequency
= frequency
;
3171 if (cyclic_probability
> real_almost_one
)
3172 cyclic_probability
= real_almost_one
;
3174 /* BLOCK_INFO (bb)->frequency = frequency
3175 / (1 - cyclic_probability) */
3177 cyclic_probability
= sreal (1) - cyclic_probability
;
3178 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
3182 bitmap_clear_bit (tovisit
, bb
->index
);
3184 e
= find_edge (bb
, head
);
3187 /* EDGE_INFO (e)->back_edge_prob
3188 = ((e->probability * BLOCK_INFO (bb)->frequency)
3189 / REG_BR_PROB_BASE); */
3191 /* FIXME: Graphite is producing edges with no profile. Once
3192 this is fixed, drop this. */
3193 sreal tmp
= e
->probability
.initialized_p () ?
3194 e
->probability
.to_reg_br_prob_base () : 0;
3195 tmp
*= BLOCK_INFO (bb
)->frequency
;
3196 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
3199 /* Propagate to successor blocks. */
3200 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3201 if (!(e
->flags
& EDGE_DFS_BACK
)
3202 && BLOCK_INFO (e
->dest
)->npredecessors
)
3204 BLOCK_INFO (e
->dest
)->npredecessors
--;
3205 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3210 BLOCK_INFO (last
)->next
= e
->dest
;
3218 /* Estimate frequencies in loops at same nest level. */
3221 estimate_loops_at_level (struct loop
*first_loop
)
3225 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3230 auto_bitmap tovisit
;
3232 estimate_loops_at_level (loop
->inner
);
3234 /* Find current loop back edge and mark it. */
3235 e
= loop_latch_edge (loop
);
3236 EDGE_INFO (e
)->back_edge
= 1;
3238 bbs
= get_loop_body (loop
);
3239 for (i
= 0; i
< loop
->num_nodes
; i
++)
3240 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3242 propagate_freq (loop
->header
, tovisit
);
3246 /* Propagates frequencies through structure of loops. */
3249 estimate_loops (void)
3251 auto_bitmap tovisit
;
3254 /* Start by estimating the frequencies in the loops. */
3255 if (number_of_loops (cfun
) > 1)
3256 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3258 /* Now propagate the frequencies through all the blocks. */
3259 FOR_ALL_BB_FN (bb
, cfun
)
3261 bitmap_set_bit (tovisit
, bb
->index
);
3263 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3266 /* Drop the profile for NODE to guessed, and update its frequency based on
3267 whether it is expected to be hot given the CALL_COUNT. */
3270 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3272 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3273 /* In the case where this was called by another function with a
3274 dropped profile, call_count will be 0. Since there are no
3275 non-zero call counts to this function, we don't know for sure
3276 whether it is hot, and therefore it will be marked normal below. */
3277 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3281 "Dropping 0 profile for %s. %s based on calls.\n",
3283 hot
? "Function is hot" : "Function is normal");
3284 /* We only expect to miss profiles for functions that are reached
3285 via non-zero call edges in cases where the function may have
3286 been linked from another module or library (COMDATs and extern
3287 templates). See the comments below for handle_missing_profiles.
3288 Also, only warn in cases where the missing counts exceed the
3289 number of training runs. In certain cases with an execv followed
3290 by a no-return call the profile for the no-return call is not
3291 dumped and there can be a mismatch. */
3292 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3293 && call_count
> profile_info
->runs
)
3295 if (flag_profile_correction
)
3299 "Missing counts for called function %s\n",
3300 node
->dump_name ());
3303 warning (0, "Missing counts for called function %s",
3304 node
->dump_name ());
3308 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
3309 if (flag_guess_branch_prob
)
3312 = ENTRY_BLOCK_PTR_FOR_FN
3313 (DECL_STRUCT_FUNCTION (node
->decl
))->count
.nonzero_p ();
3314 FOR_ALL_BB_FN (bb
, fn
)
3315 if (clear_zeros
|| !(bb
->count
== profile_count::zero ()))
3316 bb
->count
= bb
->count
.guessed_local ();
3317 DECL_STRUCT_FUNCTION (node
->decl
)->cfg
->count_max
=
3318 DECL_STRUCT_FUNCTION (node
->decl
)->cfg
->count_max
.guessed_local ();
3322 FOR_ALL_BB_FN (bb
, fn
)
3323 bb
->count
= profile_count::uninitialized ();
3324 DECL_STRUCT_FUNCTION (node
->decl
)->cfg
->count_max
3325 = profile_count::uninitialized ();
3329 struct cgraph_edge
*e
;
3330 for (e
= node
->callees
; e
; e
= e
->next_callee
)
3331 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3332 for (e
= node
->indirect_calls
; e
; e
= e
->next_callee
)
3333 e
->count
= gimple_bb (e
->call_stmt
)->count
;
3335 profile_status_for_fn (fn
)
3336 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3338 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3341 /* In the case of COMDAT routines, multiple object files will contain the same
3342 function and the linker will select one for the binary. In that case
3343 all the other copies from the profile instrument binary will be missing
3344 profile counts. Look for cases where this happened, due to non-zero
3345 call counts going to 0-count functions, and drop the profile to guessed
3346 so that we can use the estimated probabilities and avoid optimizing only
3349 The other case where the profile may be missing is when the routine
3350 is not going to be emitted to the object file, e.g. for "extern template"
3351 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3352 all other cases of non-zero calls to 0-count functions. */
3355 handle_missing_profiles (void)
3357 struct cgraph_node
*node
;
3358 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3359 auto_vec
<struct cgraph_node
*, 64> worklist
;
3361 /* See if 0 count function has non-0 count callers. In this case we
3362 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3363 FOR_EACH_DEFINED_FUNCTION (node
)
3365 struct cgraph_edge
*e
;
3366 profile_count call_count
= profile_count::zero ();
3367 gcov_type max_tp_first_run
= 0;
3368 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3370 if (!(node
->count
== profile_count::zero ()))
3372 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3373 if (e
->count
.initialized_p () && e
->count
> 0)
3375 call_count
= call_count
+ e
->count
;
3377 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3378 max_tp_first_run
= e
->caller
->tp_first_run
;
3381 /* If time profile is missing, let assign the maximum that comes from
3382 caller functions. */
3383 if (!node
->tp_first_run
&& max_tp_first_run
)
3384 node
->tp_first_run
= max_tp_first_run
+ 1;
3388 && (call_count
.apply_scale (unlikely_count_fraction
, 1)
3389 >= profile_info
->runs
))
3391 drop_profile (node
, call_count
);
3392 worklist
.safe_push (node
);
3396 /* Propagate the profile dropping to other 0-count COMDATs that are
3397 potentially called by COMDATs we already dropped the profile on. */
3398 while (worklist
.length () > 0)
3400 struct cgraph_edge
*e
;
3402 node
= worklist
.pop ();
3403 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3405 struct cgraph_node
*callee
= e
->callee
;
3406 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3408 if (callee
->count
> 0)
3410 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3412 && profile_status_for_fn (fn
) == PROFILE_READ
)
3414 drop_profile (node
, profile_count::zero ());
3415 worklist
.safe_push (callee
);
3421 /* Convert counts measured by profile driven feedback to frequencies.
3422 Return nonzero iff there was any nonzero execution count. */
3425 update_max_bb_count (void)
3427 profile_count true_count_max
= profile_count::uninitialized ();
3430 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3431 true_count_max
= true_count_max
.max (bb
->count
);
3433 cfun
->cfg
->count_max
= true_count_max
;
3435 return true_count_max
.ipa ().nonzero_p ();
3438 /* Return true if function is likely to be expensive, so there is no point to
3439 optimize performance of prologue, epilogue or do inlining at the expense
3440 of code size growth. THRESHOLD is the limit of number of instructions
3441 function can execute at average to be still considered not expensive. */
3444 expensive_function_p (int threshold
)
3448 /* If profile was scaled in a way entry block has count 0, then the function
3449 is deifnitly taking a lot of time. */
3450 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.nonzero_p ())
3453 profile_count limit
= ENTRY_BLOCK_PTR_FOR_FN
3454 (cfun
)->count
.apply_scale (threshold
, 1);
3455 profile_count sum
= profile_count::zero ();
3456 FOR_EACH_BB_FN (bb
, cfun
)
3460 if (!bb
->count
.initialized_p ())
3463 fprintf (dump_file
, "Function is considered expensive because"
3464 " count of bb %i is not initialized\n", bb
->index
);
3468 FOR_BB_INSNS (bb
, insn
)
3469 if (active_insn_p (insn
))
3480 /* All basic blocks that are reachable only from unlikely basic blocks are
3484 propagate_unlikely_bbs_forward (void)
3486 auto_vec
<basic_block
, 64> worklist
;
3491 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3493 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3494 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3496 while (worklist
.length () > 0)
3498 bb
= worklist
.pop ();
3499 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3500 if (!(e
->count () == profile_count::zero ())
3501 && !(e
->dest
->count
== profile_count::zero ())
3504 e
->dest
->aux
= (void *)(size_t) 1;
3505 worklist
.safe_push (e
->dest
);
3510 FOR_ALL_BB_FN (bb
, cfun
)
3514 if (!(bb
->count
== profile_count::zero ())
3515 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3517 "Basic block %i is marked unlikely by forward prop\n",
3519 bb
->count
= profile_count::zero ();
3526 /* Determine basic blocks/edges that are known to be unlikely executed and set
3527 their counters to zero.
3528 This is done with first identifying obviously unlikely BBs/edges and then
3529 propagating in both directions. */
3532 determine_unlikely_bbs ()
3535 auto_vec
<basic_block
, 64> worklist
;
3539 FOR_EACH_BB_FN (bb
, cfun
)
3541 if (!(bb
->count
== profile_count::zero ())
3542 && unlikely_executed_bb_p (bb
))
3544 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3545 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3547 bb
->count
= profile_count::zero ();
3550 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3551 if (!(e
->probability
== profile_probability::never ())
3552 && unlikely_executed_edge_p (e
))
3554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3555 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3556 bb
->index
, e
->dest
->index
);
3557 e
->probability
= profile_probability::never ();
3560 gcc_checking_assert (!bb
->aux
);
3562 propagate_unlikely_bbs_forward ();
3564 auto_vec
<int, 64> nsuccs
;
3565 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
3566 FOR_ALL_BB_FN (bb
, cfun
)
3567 if (!(bb
->count
== profile_count::zero ())
3568 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3570 nsuccs
[bb
->index
] = 0;
3571 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3572 if (!(e
->probability
== profile_probability::never ())
3573 && !(e
->dest
->count
== profile_count::zero ()))
3574 nsuccs
[bb
->index
]++;
3575 if (!nsuccs
[bb
->index
])
3576 worklist
.safe_push (bb
);
3578 while (worklist
.length () > 0)
3580 bb
= worklist
.pop ();
3581 if (bb
->count
== profile_count::zero ())
3583 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3586 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3587 !gsi_end_p (gsi
); gsi_next (&gsi
))
3588 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3589 /* stmt_can_terminate_bb_p special cases noreturns because it
3590 assumes that fake edges are created. We want to know that
3591 noreturn alone does not imply BB to be unlikely. */
3592 || (is_gimple_call (gsi_stmt (gsi
))
3593 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3601 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3603 "Basic block %i is marked unlikely by backward prop\n",
3605 bb
->count
= profile_count::zero ();
3606 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3607 if (!(e
->probability
== profile_probability::never ()))
3609 if (!(e
->src
->count
== profile_count::zero ()))
3611 gcc_checking_assert (nsuccs
[e
->src
->index
] > 0);
3612 nsuccs
[e
->src
->index
]--;
3613 if (!nsuccs
[e
->src
->index
])
3614 worklist
.safe_push (e
->src
);
3618 /* Finally all edges from non-0 regions to 0 are unlikely. */
3619 FOR_ALL_BB_FN (bb
, cfun
)
3620 if (!(bb
->count
== profile_count::zero ()))
3621 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3622 if (!(e
->probability
== profile_probability::never ())
3623 && e
->dest
->count
== profile_count::zero ())
3625 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3626 fprintf (dump_file
, "Edge %i->%i is unlikely because "
3627 "it enters unlikely block\n",
3628 bb
->index
, e
->dest
->index
);
3629 e
->probability
= profile_probability::never ();
3631 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3632 cgraph_node::get (current_function_decl
)->count
= profile_count::zero ();
3635 /* Estimate and propagate basic block frequencies using the given branch
3636 probabilities. If FORCE is true, the frequencies are used to estimate
3637 the counts even when there are already non-zero profile counts. */
3640 estimate_bb_frequencies (bool force
)
3645 determine_unlikely_bbs ();
3647 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3648 || !update_max_bb_count ())
3650 static int real_values_initialized
= 0;
3652 if (!real_values_initialized
)
3654 real_values_initialized
= 1;
3655 real_br_prob_base
= REG_BR_PROB_BASE
;
3656 /* Scaling frequencies up to maximal profile count may result in
3657 frequent overflows especially when inlining loops.
3658 Small scalling results in unnecesary precision loss. Stay in
3659 the half of the (exponential) range. */
3660 real_bb_freq_max
= (uint64_t)1 << (profile_count::n_bits
/ 2);
3661 real_one_half
= sreal (1, -1);
3662 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3663 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3666 mark_dfs_back_edges ();
3668 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3669 profile_probability::always ();
3671 /* Set up block info for each basic block. */
3672 alloc_aux_for_blocks (sizeof (block_info
));
3673 alloc_aux_for_edges (sizeof (edge_prob_info
));
3674 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3679 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3681 /* FIXME: Graphite is producing edges with no profile. Once
3682 this is fixed, drop this. */
3683 if (e
->probability
.initialized_p ())
3684 EDGE_INFO (e
)->back_edge_prob
3685 = e
->probability
.to_reg_br_prob_base ();
3687 EDGE_INFO (e
)->back_edge_prob
= REG_BR_PROB_BASE
/ 2;
3688 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3692 /* First compute frequencies locally for each loop from innermost
3693 to outermost to examine frequencies for back edges. */
3697 FOR_EACH_BB_FN (bb
, cfun
)
3698 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3699 freq_max
= BLOCK_INFO (bb
)->frequency
;
3701 freq_max
= real_bb_freq_max
/ freq_max
;
3704 profile_count ipa_count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa ();
3705 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3706 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3708 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3709 profile_count count
= profile_count::from_gcov_type (tmp
.to_int ());
3711 /* If we have profile feedback in which this function was never
3712 executed, then preserve this info. */
3713 if (!(bb
->count
== profile_count::zero ()))
3714 bb
->count
= count
.guessed_local ().combine_with_ipa_count (ipa_count
);
3715 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3718 free_aux_for_blocks ();
3719 free_aux_for_edges ();
3721 compute_function_frequency ();
3724 /* Decide whether function is hot, cold or unlikely executed. */
3726 compute_function_frequency (void)
3729 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3731 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3732 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3733 node
->only_called_at_startup
= true;
3734 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3735 node
->only_called_at_exit
= true;
3737 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3739 int flags
= flags_from_decl_or_type (current_function_decl
);
3740 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa_p ()
3741 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.ipa() == profile_count::zero ())
3742 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3745 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3746 warn_function_cold (current_function_decl
);
3748 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3750 node
->frequency
= NODE_FREQUENCY_HOT
;
3751 else if (flags
& ECF_NORETURN
)
3752 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3753 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3754 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3755 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3756 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3757 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3761 /* Only first time try to drop function into unlikely executed.
3762 After inlining the roundoff errors may confuse us.
3763 Ipa-profile pass will drop functions only called from unlikely
3764 functions to unlikely and that is most of what we care about. */
3765 if (!cfun
->after_inlining
)
3767 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3768 warn_function_cold (current_function_decl
);
3770 FOR_EACH_BB_FN (bb
, cfun
)
3772 if (maybe_hot_bb_p (cfun
, bb
))
3774 node
->frequency
= NODE_FREQUENCY_HOT
;
3777 if (!probably_never_executed_bb_p (cfun
, bb
))
3778 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3782 /* Build PREDICT_EXPR. */
3784 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3786 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3787 build_int_cst (integer_type_node
, predictor
));
3788 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3793 predictor_name (enum br_predictor predictor
)
3795 return predictor_info
[predictor
].name
;
3798 /* Predict branch probabilities and estimate profile of the tree CFG. */
3802 const pass_data pass_data_profile
=
3804 GIMPLE_PASS
, /* type */
3805 "profile_estimate", /* name */
3806 OPTGROUP_NONE
, /* optinfo_flags */
3807 TV_BRANCH_PROB
, /* tv_id */
3808 PROP_cfg
, /* properties_required */
3809 0, /* properties_provided */
3810 0, /* properties_destroyed */
3811 0, /* todo_flags_start */
3812 0, /* todo_flags_finish */
3815 class pass_profile
: public gimple_opt_pass
3818 pass_profile (gcc::context
*ctxt
)
3819 : gimple_opt_pass (pass_data_profile
, ctxt
)
3822 /* opt_pass methods: */
3823 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3824 virtual unsigned int execute (function
*);
3826 }; // class pass_profile
3829 pass_profile::execute (function
*fun
)
3833 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3836 loop_optimizer_init (LOOPS_NORMAL
);
3837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3838 flow_loops_dump (dump_file
, NULL
, 0);
3840 mark_irreducible_loops ();
3842 nb_loops
= number_of_loops (fun
);
3846 tree_estimate_probability (false);
3851 loop_optimizer_finalize ();
3852 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3853 gimple_dump_cfg (dump_file
, dump_flags
);
3854 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3855 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3856 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3859 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3860 if (loop
->header
->count
.initialized_p ())
3861 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
3863 (int)expected_loop_iterations_unbounded (loop
));
3871 make_pass_profile (gcc::context
*ctxt
)
3873 return new pass_profile (ctxt
);
3878 const pass_data pass_data_strip_predict_hints
=
3880 GIMPLE_PASS
, /* type */
3881 "*strip_predict_hints", /* name */
3882 OPTGROUP_NONE
, /* optinfo_flags */
3883 TV_BRANCH_PROB
, /* tv_id */
3884 PROP_cfg
, /* properties_required */
3885 0, /* properties_provided */
3886 0, /* properties_destroyed */
3887 0, /* todo_flags_start */
3888 0, /* todo_flags_finish */
3891 class pass_strip_predict_hints
: public gimple_opt_pass
3894 pass_strip_predict_hints (gcc::context
*ctxt
)
3895 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3898 /* opt_pass methods: */
3899 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3900 virtual unsigned int execute (function
*);
3902 }; // class pass_strip_predict_hints
3904 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3905 we no longer need. */
3907 pass_strip_predict_hints::execute (function
*fun
)
3912 bool changed
= false;
3914 FOR_EACH_BB_FN (bb
, fun
)
3916 gimple_stmt_iterator bi
;
3917 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3919 gimple
*stmt
= gsi_stmt (bi
);
3921 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3923 gsi_remove (&bi
, true);
3927 else if (is_gimple_call (stmt
))
3929 tree fndecl
= gimple_call_fndecl (stmt
);
3932 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3933 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3934 && gimple_call_num_args (stmt
) == 2)
3935 || (gimple_call_internal_p (stmt
)
3936 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3938 var
= gimple_call_lhs (stmt
);
3943 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3944 gsi_replace (&bi
, ass_stmt
, true);
3948 gsi_remove (&bi
, true);
3956 return changed
? TODO_cleanup_cfg
: 0;
3962 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3964 return new pass_strip_predict_hints (ctxt
);
3967 /* Rebuild function frequencies. Passes are in general expected to
3968 maintain profile by hand, however in some cases this is not possible:
3969 for example when inlining several functions with loops freuqencies might run
3970 out of scale and thus needs to be recomputed. */
3973 rebuild_frequencies (void)
3975 timevar_push (TV_REBUILD_FREQUENCIES
);
3977 /* When the max bb count in the function is small, there is a higher
3978 chance that there were truncation errors in the integer scaling
3979 of counts by inlining and other optimizations. This could lead
3980 to incorrect classification of code as being cold when it isn't.
3981 In that case, force the estimation of bb counts/frequencies from the
3982 branch probabilities, rather than computing frequencies from counts,
3983 which may also lead to frequencies incorrectly reduced to 0. There
3984 is less precision in the probabilities, so we only do this for small
3986 cfun
->cfg
->count_max
= profile_count::uninitialized ();
3988 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3989 cfun
->cfg
->count_max
= cfun
->cfg
->count_max
.max (bb
->count
);
3991 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3993 loop_optimizer_init (0);
3994 add_noreturn_fake_exit_edges ();
3995 mark_irreducible_loops ();
3996 connect_infinite_loops_to_exit ();
3997 estimate_bb_frequencies (true);
3998 remove_fake_exit_edges ();
3999 loop_optimizer_finalize ();
4001 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
4002 update_max_bb_count ();
4005 timevar_pop (TV_REBUILD_FREQUENCIES
);
4008 /* Perform a dry run of the branch prediction pass and report comparsion of
4009 the predicted and real profile into the dump file. */
4012 report_predictor_hitrates (void)
4016 loop_optimizer_init (LOOPS_NORMAL
);
4017 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4018 flow_loops_dump (dump_file
, NULL
, 0);
4020 mark_irreducible_loops ();
4022 nb_loops
= number_of_loops (cfun
);
4026 tree_estimate_probability (true);
4031 loop_optimizer_finalize ();
4034 /* Force edge E to be cold.
4035 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4036 keep low probability to represent possible error in a guess. This is used
4037 i.e. in case we predict loop to likely iterate given number of times but
4038 we are not 100% sure.
4040 This function locally updates profile without attempt to keep global
4041 consistency which can not be reached in full generality without full profile
4042 rebuild from probabilities alone. Doing so is not necessarily a good idea
4043 because frequencies and counts may be more realistic then probabilities.
4045 In some cases (such as for elimination of early exits during full loop
4046 unrolling) the caller can ensure that profile will get consistent
4050 force_edge_cold (edge e
, bool impossible
)
4052 profile_count count_sum
= profile_count::zero ();
4053 profile_probability prob_sum
= profile_probability::never ();
4056 bool uninitialized_exit
= false;
4058 /* When branch probability guesses are not known, then do nothing. */
4059 if (!impossible
&& !e
->count ().initialized_p ())
4062 profile_probability goal
= (impossible
? profile_probability::never ()
4063 : profile_probability::very_unlikely ());
4065 /* If edge is already improbably or cold, just return. */
4066 if (e
->probability
<= goal
4067 && (!impossible
|| e
->count () == profile_count::zero ()))
4069 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4072 if (e
->flags
& EDGE_FAKE
)
4074 if (e2
->count ().initialized_p ())
4075 count_sum
+= e2
->count ();
4076 if (e2
->probability
.initialized_p ())
4077 prob_sum
+= e2
->probability
;
4079 uninitialized_exit
= true;
4082 /* If we are not guessing profiles but have some other edges out,
4083 just assume the control flow goes elsewhere. */
4084 if (uninitialized_exit
)
4085 e
->probability
= goal
;
4086 /* If there are other edges out of e->src, redistribute probabilitity
4088 else if (prob_sum
> profile_probability::never ())
4090 if (!(e
->probability
< goal
))
4091 e
->probability
= goal
;
4093 profile_probability prob_comp
= prob_sum
/ e
->probability
.invert ();
4095 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4096 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
4097 "probability to other edges.\n",
4098 e
->src
->index
, e
->dest
->index
,
4099 impossible
? "impossible" : "cold");
4100 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
4103 e2
->probability
/= prob_comp
;
4105 if (current_ir_type () != IR_GIMPLE
4106 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4107 update_br_prob_note (e
->src
);
4109 /* If all edges out of e->src are unlikely, the basic block itself
4113 if (prob_sum
== profile_probability::never ())
4114 e
->probability
= profile_probability::always ();
4118 e
->probability
= profile_probability::never ();
4119 /* If BB has some edges out that are not impossible, we can not
4120 assume that BB itself is. */
4123 if (current_ir_type () != IR_GIMPLE
4124 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4125 update_br_prob_note (e
->src
);
4126 if (e
->src
->count
== profile_count::zero ())
4128 if (count_sum
== profile_count::zero () && impossible
)
4131 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
4133 else if (current_ir_type () == IR_GIMPLE
)
4134 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
4135 !gsi_end_p (gsi
); gsi_next (&gsi
))
4137 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
4143 /* FIXME: Implement RTL path. */
4148 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4150 "Making bb %i impossible and dropping count to 0.\n",
4152 e
->src
->count
= profile_count::zero ();
4153 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
4154 force_edge_cold (e2
, impossible
);
4159 /* If we did not adjusting, the source basic block has no likely edeges
4160 leaving other direction. In that case force that bb cold, too.
4161 This in general is difficult task to do, but handle special case when
4162 BB has only one predecestor. This is common case when we are updating
4163 after loop transforms. */
4164 if (!(prob_sum
> profile_probability::never ())
4165 && count_sum
== profile_count::zero ()
4166 && single_pred_p (e
->src
) && e
->src
->count
.to_frequency (cfun
)
4167 > (impossible
? 0 : 1))
4169 int old_frequency
= e
->src
->count
.to_frequency (cfun
);
4170 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4171 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
4172 impossible
? "impossible" : "cold");
4173 int new_frequency
= MIN (e
->src
->count
.to_frequency (cfun
),
4174 impossible
? 0 : 1);
4176 e
->src
->count
= profile_count::zero ();
4178 e
->src
->count
= e
->count ().apply_scale (new_frequency
,
4180 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4182 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4183 && maybe_hot_bb_p (cfun
, e
->src
))
4184 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4185 impossible
? "impossible" : "cold");
4191 namespace selftest
{
4193 /* Test that value range of predictor values defined in predict.def is
4194 within range (50, 100]. */
4196 struct branch_predictor
4199 unsigned probability
;
4202 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4205 test_prediction_value_range ()
4207 branch_predictor predictors
[] = {
4208 #include "predict.def"
4212 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4214 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4215 ASSERT_TRUE (p
> 50 && p
<= 100);
4219 #undef DEF_PREDICTOR
4221 /* Run all of the selfests within this file. */
4226 test_prediction_value_range ();
4229 } // namespace selftest
4230 #endif /* CHECKING_P. */