1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 [1] "Branch Prediction for Free"
23 Ball and Larus; PLDI '93.
24 [2] "Static Branch Frequency and Program Profile Analysis"
25 Wu and Larus; MICRO-27.
26 [3] "Corpus-based Static Branch Prediction"
27 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
32 #include "coretypes.h"
38 #include "tree-pass.h"
44 #include "diagnostic-core.h"
45 #include "gimple-predict.h"
46 #include "fold-const.h"
53 #include "gimple-iterator.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-scalar-evolution.h"
58 #include "ipa-utils.h"
59 #include "gimple-pretty-print.h"
62 /* Enum with reasons why a predictor is ignored. */
68 REASON_SINGLE_EDGE_DUPLICATE
,
69 REASON_EDGE_PAIR_DUPLICATE
72 /* String messages for the aforementioned enum. */
74 static const char *reason_messages
[] = {"", " (ignored)",
75 " (single edge duplicate)", " (edge pair duplicate)"};
77 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
78 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
79 static sreal real_almost_one
, real_br_prob_base
,
80 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
82 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
83 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
,
84 enum predictor_reason
, edge
);
85 static void predict_paths_leading_to (basic_block
, enum br_predictor
,
87 struct loop
*in_loop
= NULL
);
88 static void predict_paths_leading_to_edge (edge
, enum br_predictor
,
90 struct loop
*in_loop
= NULL
);
91 static bool can_predict_insn_p (const rtx_insn
*);
93 /* Information we hold about each branch predictor.
94 Filled using information from predict.def. */
98 const char *const name
; /* Name used in the debugging dumps. */
99 const int hitrate
; /* Expected hitrate used by
100 predict_insn_def call. */
104 /* Use given predictor without Dempster-Shaffer theory if it matches
105 using first_match heuristics. */
106 #define PRED_FLAG_FIRST_MATCH 1
108 /* Recompute hitrate in percent to our representation. */
110 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
112 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
113 static const struct predictor_info predictor_info
[]= {
114 #include "predict.def"
116 /* Upper bound on predictors. */
121 /* Return TRUE if frequency FREQ is considered to be hot. */
124 maybe_hot_frequency_p (struct function
*fun
, int freq
)
126 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
127 if (!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
129 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
131 if (node
->frequency
== NODE_FREQUENCY_HOT
)
134 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
136 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
137 && freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
* 2 / 3))
139 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
141 if (freq
* PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)
142 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
147 static gcov_type min_count
= -1;
149 /* Determine the threshold for hot BB counts. */
152 get_hot_bb_threshold ()
154 gcov_working_set_t
*ws
;
157 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
159 min_count
= ws
->min_counter
;
164 /* Set the threshold for hot BB counts. */
167 set_hot_bb_threshold (gcov_type min
)
172 /* Return TRUE if frequency FREQ is considered to be hot. */
175 maybe_hot_count_p (struct function
*, profile_count count
)
177 if (!count
.initialized_p ())
179 /* Code executed at most once is not hot. */
180 if (count
<= MAX (profile_info
? profile_info
->runs
: 1, 1))
182 return (count
.to_gcov_type () >= get_hot_bb_threshold ());
185 /* Return true in case BB can be CPU intensive and should be optimized
186 for maximal performance. */
189 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
191 gcc_checking_assert (fun
);
192 if (!maybe_hot_count_p (fun
, bb
->count
))
194 return maybe_hot_frequency_p (fun
, bb
->frequency
);
197 /* Return true in case BB can be CPU intensive and should be optimized
198 for maximal performance. */
201 maybe_hot_edge_p (edge e
)
203 if (!maybe_hot_count_p (cfun
, e
->count
))
205 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
208 /* Return true if profile COUNT and FREQUENCY, or function FUN static
209 node frequency reflects never being executed. */
212 probably_never_executed (struct function
*fun
,
213 profile_count count
, int)
215 gcc_checking_assert (fun
);
216 if (count
== profile_count::zero ())
218 if (count
.initialized_p () && profile_status_for_fn (fun
) == PROFILE_READ
)
220 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
221 if (count
.apply_scale (unlikely_count_fraction
, 1) >= profile_info
->runs
)
225 if ((!profile_info
|| profile_status_for_fn (fun
) != PROFILE_READ
)
226 && (cgraph_node::get (fun
->decl
)->frequency
227 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
233 /* Return true in case BB is probably never executed. */
236 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
238 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
242 /* Return true if E is unlikely executed for obvious reasons. */
245 unlikely_executed_edge_p (edge e
)
247 return e
->count
== profile_count::zero ()
248 || (e
->flags
& (EDGE_EH
| EDGE_FAKE
));
251 /* Return true in case edge E is probably never executed. */
254 probably_never_executed_edge_p (struct function
*fun
, edge e
)
256 if (e
->count
.initialized_p ())
257 unlikely_executed_edge_p (e
);
258 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
261 /* Return true when current function should always be optimized for size. */
264 optimize_function_for_size_p (struct function
*fun
)
266 if (!fun
|| !fun
->decl
)
267 return optimize_size
;
268 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
269 return n
&& n
->optimize_for_size_p ();
272 /* Return true when current function should always be optimized for speed. */
275 optimize_function_for_speed_p (struct function
*fun
)
277 return !optimize_function_for_size_p (fun
);
280 /* Return the optimization type that should be used for the function FUN. */
283 function_optimization_type (struct function
*fun
)
285 return (optimize_function_for_speed_p (fun
)
287 : OPTIMIZE_FOR_SIZE
);
290 /* Return TRUE when BB should be optimized for size. */
293 optimize_bb_for_size_p (const_basic_block bb
)
295 return (optimize_function_for_size_p (cfun
)
296 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
299 /* Return TRUE when BB should be optimized for speed. */
302 optimize_bb_for_speed_p (const_basic_block bb
)
304 return !optimize_bb_for_size_p (bb
);
307 /* Return the optimization type that should be used for block BB. */
310 bb_optimization_type (const_basic_block bb
)
312 return (optimize_bb_for_speed_p (bb
)
314 : OPTIMIZE_FOR_SIZE
);
317 /* Return TRUE when BB should be optimized for size. */
320 optimize_edge_for_size_p (edge e
)
322 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
325 /* Return TRUE when BB should be optimized for speed. */
328 optimize_edge_for_speed_p (edge e
)
330 return !optimize_edge_for_size_p (e
);
333 /* Return TRUE when BB should be optimized for size. */
336 optimize_insn_for_size_p (void)
338 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
341 /* Return TRUE when BB should be optimized for speed. */
344 optimize_insn_for_speed_p (void)
346 return !optimize_insn_for_size_p ();
349 /* Return TRUE when LOOP should be optimized for size. */
352 optimize_loop_for_size_p (struct loop
*loop
)
354 return optimize_bb_for_size_p (loop
->header
);
357 /* Return TRUE when LOOP should be optimized for speed. */
360 optimize_loop_for_speed_p (struct loop
*loop
)
362 return optimize_bb_for_speed_p (loop
->header
);
365 /* Return TRUE when LOOP nest should be optimized for speed. */
368 optimize_loop_nest_for_speed_p (struct loop
*loop
)
370 struct loop
*l
= loop
;
371 if (optimize_loop_for_speed_p (loop
))
374 while (l
&& l
!= loop
)
376 if (optimize_loop_for_speed_p (l
))
384 while (l
!= loop
&& !l
->next
)
393 /* Return TRUE when LOOP nest should be optimized for size. */
396 optimize_loop_nest_for_size_p (struct loop
*loop
)
398 return !optimize_loop_nest_for_speed_p (loop
);
401 /* Return true when edge E is likely to be well predictable by branch
405 predictable_edge_p (edge e
)
407 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
410 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
411 || (REG_BR_PROB_BASE
- e
->probability
412 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
418 /* Set RTL expansion for BB profile. */
421 rtl_profile_for_bb (basic_block bb
)
423 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
426 /* Set RTL expansion for edge profile. */
429 rtl_profile_for_edge (edge e
)
431 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
434 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
436 default_rtl_profile (void)
438 crtl
->maybe_hot_insn_p
= true;
441 /* Return true if the one of outgoing edges is already predicted by
445 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
448 if (!INSN_P (BB_END (bb
)))
450 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
451 if (REG_NOTE_KIND (note
) == REG_BR_PRED
452 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
457 /* Structure representing predictions in tree level. */
459 struct edge_prediction
{
460 struct edge_prediction
*ep_next
;
462 enum br_predictor ep_predictor
;
466 /* This map contains for a basic block the list of predictions for the
469 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
471 /* Return true if the one of outgoing edges is already predicted by
475 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
477 struct edge_prediction
*i
;
478 edge_prediction
**preds
= bb_predictions
->get (bb
);
483 for (i
= *preds
; i
; i
= i
->ep_next
)
484 if (i
->ep_predictor
== predictor
)
489 /* Return true if the one of outgoing edges is already predicted by
490 PREDICTOR for edge E predicted as TAKEN. */
493 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
495 struct edge_prediction
*i
;
496 basic_block bb
= e
->src
;
497 edge_prediction
**preds
= bb_predictions
->get (bb
);
501 int probability
= predictor_info
[(int) predictor
].hitrate
;
504 probability
= REG_BR_PROB_BASE
- probability
;
506 for (i
= *preds
; i
; i
= i
->ep_next
)
507 if (i
->ep_predictor
== predictor
509 && i
->ep_probability
== probability
)
514 /* Return true when the probability of edge is reliable.
516 The profile guessing code is good at predicting branch outcome (ie.
517 taken/not taken), that is predicted right slightly over 75% of time.
518 It is however notoriously poor on predicting the probability itself.
519 In general the profile appear a lot flatter (with probabilities closer
520 to 50%) than the reality so it is bad idea to use it to drive optimization
521 such as those disabling dynamic branch prediction for well predictable
524 There are two exceptions - edges leading to noreturn edges and edges
525 predicted by number of iterations heuristics are predicted well. This macro
526 should be able to distinguish those, but at the moment it simply check for
527 noreturn heuristic that is only one giving probability over 99% or bellow
528 1%. In future we might want to propagate reliability information across the
529 CFG if we find this information useful on multiple places. */
531 probability_reliable_p (int prob
)
533 return (profile_status_for_fn (cfun
) == PROFILE_READ
534 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
535 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
538 /* Same predicate as above, working on edges. */
540 edge_probability_reliable_p (const_edge e
)
542 return probability_reliable_p (e
->probability
);
545 /* Same predicate as edge_probability_reliable_p, working on notes. */
547 br_prob_note_reliable_p (const_rtx note
)
549 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
550 return probability_reliable_p (XINT (note
, 0));
554 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
556 gcc_assert (any_condjump_p (insn
));
557 if (!flag_guess_branch_prob
)
560 add_reg_note (insn
, REG_BR_PRED
,
561 gen_rtx_CONCAT (VOIDmode
,
562 GEN_INT ((int) predictor
),
563 GEN_INT ((int) probability
)));
566 /* Predict insn by given predictor. */
569 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
570 enum prediction taken
)
572 int probability
= predictor_info
[(int) predictor
].hitrate
;
575 probability
= REG_BR_PROB_BASE
- probability
;
577 predict_insn (insn
, predictor
, probability
);
580 /* Predict edge E with given probability if possible. */
583 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
586 last_insn
= BB_END (e
->src
);
588 /* We can store the branch prediction information only about
589 conditional jumps. */
590 if (!any_condjump_p (last_insn
))
593 /* We always store probability of branching. */
594 if (e
->flags
& EDGE_FALLTHRU
)
595 probability
= REG_BR_PROB_BASE
- probability
;
597 predict_insn (last_insn
, predictor
, probability
);
600 /* Predict edge E with the given PROBABILITY. */
602 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
604 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
605 && EDGE_COUNT (e
->src
->succs
) > 1
606 && flag_guess_branch_prob
609 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
610 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
614 i
->ep_probability
= probability
;
615 i
->ep_predictor
= predictor
;
620 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
621 to the filter function. */
624 filter_predictions (edge_prediction
**preds
,
625 bool (*filter
) (edge_prediction
*, void *), void *data
)
632 struct edge_prediction
**prediction
= preds
;
633 struct edge_prediction
*next
;
637 if ((*filter
) (*prediction
, data
))
638 prediction
= &((*prediction
)->ep_next
);
641 next
= (*prediction
)->ep_next
;
649 /* Filter function predicate that returns true for a edge predicate P
650 if its edge is equal to DATA. */
653 equal_edge_p (edge_prediction
*p
, void *data
)
655 return p
->ep_edge
== (edge
)data
;
658 /* Remove all predictions on given basic block that are attached
661 remove_predictions_associated_with_edge (edge e
)
666 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
667 filter_predictions (preds
, equal_edge_p
, e
);
670 /* Clears the list of predictions stored for BB. */
673 clear_bb_predictions (basic_block bb
)
675 edge_prediction
**preds
= bb_predictions
->get (bb
);
676 struct edge_prediction
*pred
, *next
;
681 for (pred
= *preds
; pred
; pred
= next
)
683 next
= pred
->ep_next
;
689 /* Return true when we can store prediction on insn INSN.
690 At the moment we represent predictions only on conditional
691 jumps, not at computed jump or other complicated cases. */
693 can_predict_insn_p (const rtx_insn
*insn
)
695 return (JUMP_P (insn
)
696 && any_condjump_p (insn
)
697 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
700 /* Predict edge E by given predictor if possible. */
703 predict_edge_def (edge e
, enum br_predictor predictor
,
704 enum prediction taken
)
706 int probability
= predictor_info
[(int) predictor
].hitrate
;
709 probability
= REG_BR_PROB_BASE
- probability
;
711 predict_edge (e
, predictor
, probability
);
714 /* Invert all branch predictions or probability notes in the INSN. This needs
715 to be done each time we invert the condition used by the jump. */
718 invert_br_probabilities (rtx insn
)
722 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
723 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
724 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
725 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
726 XEXP (XEXP (note
, 0), 1)
727 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
730 /* Dump information about the branch prediction to the output file. */
733 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
734 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
744 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
745 if (! (e
->flags
& EDGE_FALLTHRU
))
748 char edge_info_str
[128];
750 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
751 ep_edge
->dest
->index
);
753 edge_info_str
[0] = '\0';
755 fprintf (file
, " %s heuristics%s%s: %.1f%%",
756 predictor_info
[predictor
].name
,
757 edge_info_str
, reason_messages
[reason
],
758 probability
* 100.0 / REG_BR_PROB_BASE
);
760 if (bb
->count
.initialized_p ())
762 fprintf (file
, " exec ");
763 bb
->count
.dump (file
);
766 fprintf (file
, " hit ");
767 e
->count
.dump (file
);
768 fprintf (file
, " (%.1f%%)", e
->count
.to_gcov_type() * 100.0
769 / bb
->count
.to_gcov_type ());
773 fprintf (file
, "\n");
776 /* Return true if STMT is known to be unlikely executed. */
779 unlikely_executed_stmt_p (gimple
*stmt
)
781 if (!is_gimple_call (stmt
))
783 /* NORETURN attribute alone is not strong enough: exit() may be quite
784 likely executed once during program run. */
785 if (gimple_call_fntype (stmt
)
786 && lookup_attribute ("cold",
787 TYPE_ATTRIBUTES (gimple_call_fntype (stmt
)))
788 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
790 tree decl
= gimple_call_fndecl (stmt
);
793 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
))
794 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
)))
797 cgraph_node
*n
= cgraph_node::get (decl
);
802 n
= n
->ultimate_alias_target (&avail
);
803 if (avail
< AVAIL_AVAILABLE
)
806 || n
->decl
== current_function_decl
)
808 return n
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
;
811 /* Return true if BB is unlikely executed. */
814 unlikely_executed_bb_p (basic_block bb
)
816 if (bb
->count
== profile_count::zero ())
818 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
820 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
821 !gsi_end_p (gsi
); gsi_next (&gsi
))
823 if (unlikely_executed_stmt_p (gsi_stmt (gsi
)))
825 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
831 /* We can not predict the probabilities of outgoing edges of bb. Set them
832 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
833 even probability for all edges not mentioned in the set. These edges
834 are given PROB_VERY_UNLIKELY probability. */
837 set_even_probabilities (basic_block bb
,
838 hash_set
<edge
> *unlikely_edges
= NULL
)
844 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
845 if (!unlikely_executed_edge_p (e
))
848 /* Make the distribution even if all edges are unlikely. */
849 unsigned unlikely_count
= unlikely_edges
? unlikely_edges
->elements () : 0;
850 if (unlikely_count
== nedges
)
852 unlikely_edges
= NULL
;
856 unsigned c
= nedges
- unlikely_count
;
858 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
859 if (!unlikely_executed_edge_p (e
))
861 if (unlikely_edges
!= NULL
&& unlikely_edges
->contains (e
))
862 e
->probability
= PROB_VERY_UNLIKELY
;
864 e
->probability
= (REG_BR_PROB_BASE
+ c
/ 2) / c
;
870 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
871 note if not already present. Remove now useless REG_BR_PRED notes. */
874 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
879 int best_probability
= PROB_EVEN
;
880 enum br_predictor best_predictor
= END_PREDICTORS
;
881 int combined_probability
= REG_BR_PROB_BASE
/ 2;
883 bool first_match
= false;
886 if (!can_predict_insn_p (insn
))
888 set_even_probabilities (bb
);
892 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
893 pnote
= ®_NOTES (insn
);
895 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
898 /* We implement "first match" heuristics and use probability guessed
899 by predictor with smallest index. */
900 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
901 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
903 enum br_predictor predictor
= ((enum br_predictor
)
904 INTVAL (XEXP (XEXP (note
, 0), 0)));
905 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
908 if (best_predictor
> predictor
909 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
910 best_probability
= probability
, best_predictor
= predictor
;
912 d
= (combined_probability
* probability
913 + (REG_BR_PROB_BASE
- combined_probability
)
914 * (REG_BR_PROB_BASE
- probability
));
916 /* Use FP math to avoid overflows of 32bit integers. */
918 /* If one probability is 0% and one 100%, avoid division by zero. */
919 combined_probability
= REG_BR_PROB_BASE
/ 2;
921 combined_probability
= (((double) combined_probability
) * probability
922 * REG_BR_PROB_BASE
/ d
+ 0.5);
925 /* Decide which heuristic to use. In case we didn't match anything,
926 use no_prediction heuristic, in case we did match, use either
927 first match or Dempster-Shaffer theory depending on the flags. */
929 if (best_predictor
!= END_PREDICTORS
)
933 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
934 combined_probability
, bb
);
938 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
939 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
941 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
942 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
946 combined_probability
= best_probability
;
947 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
951 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
953 enum br_predictor predictor
= ((enum br_predictor
)
954 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
955 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
957 dump_prediction (dump_file
, predictor
, probability
, bb
,
958 (!first_match
|| best_predictor
== predictor
)
959 ? REASON_NONE
: REASON_IGNORED
);
960 *pnote
= XEXP (*pnote
, 1);
963 pnote
= &XEXP (*pnote
, 1);
968 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
970 /* Save the prediction into CFG in case we are seeing non-degenerated
972 if (!single_succ_p (bb
))
974 BRANCH_EDGE (bb
)->probability
= combined_probability
;
975 FALLTHRU_EDGE (bb
)->probability
976 = REG_BR_PROB_BASE
- combined_probability
;
979 else if (!single_succ_p (bb
))
981 int prob
= XINT (prob_note
, 0);
983 BRANCH_EDGE (bb
)->probability
= prob
;
984 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
987 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
990 /* Edge prediction hash traits. */
992 struct predictor_hash
: pointer_hash
<edge_prediction
>
995 static inline hashval_t
hash (const edge_prediction
*);
996 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
999 /* Calculate hash value of an edge prediction P based on predictor and
1000 normalized probability. */
1003 predictor_hash::hash (const edge_prediction
*p
)
1005 inchash::hash hstate
;
1006 hstate
.add_int (p
->ep_predictor
);
1008 int prob
= p
->ep_probability
;
1009 if (prob
> REG_BR_PROB_BASE
/ 2)
1010 prob
= REG_BR_PROB_BASE
- prob
;
1012 hstate
.add_int (prob
);
1014 return hstate
.end ();
1017 /* Return true whether edge predictions P1 and P2 use the same predictor and
1018 have equal (or opposed probability). */
1021 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
1023 return (p1
->ep_predictor
== p2
->ep_predictor
1024 && (p1
->ep_probability
== p2
->ep_probability
1025 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
1028 struct predictor_hash_traits
: predictor_hash
,
1029 typed_noop_remove
<edge_prediction
*> {};
1031 /* Return true if edge prediction P is not in DATA hash set. */
1034 not_removed_prediction_p (edge_prediction
*p
, void *data
)
1036 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
1037 return !remove
->contains (p
);
1040 /* Prune predictions for a basic block BB. Currently we do following
1043 1) remove duplicate prediction that is guessed with the same probability
1044 (different than 1/2) to both edge
1045 2) remove duplicates for a prediction that belongs with the same probability
1051 prune_predictions_for_bb (basic_block bb
)
1053 edge_prediction
**preds
= bb_predictions
->get (bb
);
1057 hash_table
<predictor_hash_traits
> s (13);
1058 hash_set
<edge_prediction
*> remove
;
1060 /* Step 1: identify predictors that should be removed. */
1061 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
1063 edge_prediction
*existing
= s
.find (pred
);
1066 if (pred
->ep_edge
== existing
->ep_edge
1067 && pred
->ep_probability
== existing
->ep_probability
)
1069 /* Remove a duplicate predictor. */
1070 dump_prediction (dump_file
, pred
->ep_predictor
,
1071 pred
->ep_probability
, bb
,
1072 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1076 else if (pred
->ep_edge
!= existing
->ep_edge
1077 && pred
->ep_probability
== existing
->ep_probability
1078 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1080 /* Remove both predictors as they predict the same
1082 dump_prediction (dump_file
, existing
->ep_predictor
,
1083 pred
->ep_probability
, bb
,
1084 REASON_EDGE_PAIR_DUPLICATE
,
1086 dump_prediction (dump_file
, pred
->ep_predictor
,
1087 pred
->ep_probability
, bb
,
1088 REASON_EDGE_PAIR_DUPLICATE
,
1091 remove
.add (existing
);
1096 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1100 /* Step 2: Remove predictors. */
1101 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1105 /* Combine predictions into single probability and store them into CFG.
1106 Remove now useless prediction entries.
1107 If DRY_RUN is set, only produce dumps and do not modify profile. */
1110 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1112 int best_probability
= PROB_EVEN
;
1113 enum br_predictor best_predictor
= END_PREDICTORS
;
1114 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1116 bool first_match
= false;
1118 struct edge_prediction
*pred
;
1120 edge e
, first
= NULL
, second
= NULL
;
1123 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1124 if (!unlikely_executed_edge_p (e
))
1127 if (first
&& !second
)
1133 /* When there is no successor or only one choice, prediction is easy.
1135 When we have a basic block with more than 2 successors, the situation
1136 is more complicated as DS theory cannot be used literally.
1137 More precisely, let's assume we predicted edge e1 with probability p1,
1138 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1139 need to find probability of e.g. m1({b2}), which we don't know.
1140 The only approximation is to equally distribute 1-p1 to all edges
1143 According to numbers we've got from SPEC2006 benchark, there's only
1144 one interesting reliable predictor (noreturn call), which can be
1145 handled with a bit easier approach. */
1148 hash_set
<edge
> unlikely_edges (4);
1150 /* Identify all edges that have a probability close to very unlikely.
1151 Doing the approach for very unlikely doesn't worth for doing as
1152 there's no such probability in SPEC2006 benchmark. */
1153 edge_prediction
**preds
= bb_predictions
->get (bb
);
1155 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1156 if (pred
->ep_probability
<= PROB_VERY_UNLIKELY
)
1157 unlikely_edges
.add (pred
->ep_edge
);
1159 if (!bb
->count
.initialized_p () && !dry_run
)
1160 set_even_probabilities (bb
, &unlikely_edges
);
1161 clear_bb_predictions (bb
);
1164 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1165 if (unlikely_edges
.elements () == 0)
1167 "%i edges in bb %i predicted to even probabilities\n",
1172 "%i edges in bb %i predicted with some unlikely edges\n",
1174 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1175 if (!unlikely_executed_edge_p (e
))
1176 dump_prediction (dump_file
, PRED_COMBINED
, e
->probability
,
1177 bb
, REASON_NONE
, e
);
1184 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1186 prune_predictions_for_bb (bb
);
1188 edge_prediction
**preds
= bb_predictions
->get (bb
);
1192 /* We implement "first match" heuristics and use probability guessed
1193 by predictor with smallest index. */
1194 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1196 enum br_predictor predictor
= pred
->ep_predictor
;
1197 int probability
= pred
->ep_probability
;
1199 if (pred
->ep_edge
!= first
)
1200 probability
= REG_BR_PROB_BASE
- probability
;
1203 /* First match heuristics would be widly confused if we predicted
1205 if (best_predictor
> predictor
1206 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1208 struct edge_prediction
*pred2
;
1209 int prob
= probability
;
1211 for (pred2
= (struct edge_prediction
*) *preds
;
1212 pred2
; pred2
= pred2
->ep_next
)
1213 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1215 int probability2
= pred2
->ep_probability
;
1217 if (pred2
->ep_edge
!= first
)
1218 probability2
= REG_BR_PROB_BASE
- probability2
;
1220 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1221 (probability2
< REG_BR_PROB_BASE
/ 2))
1224 /* If the same predictor later gave better result, go for it! */
1225 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1226 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1227 prob
= probability2
;
1230 best_probability
= prob
, best_predictor
= predictor
;
1233 d
= (combined_probability
* probability
1234 + (REG_BR_PROB_BASE
- combined_probability
)
1235 * (REG_BR_PROB_BASE
- probability
));
1237 /* Use FP math to avoid overflows of 32bit integers. */
1239 /* If one probability is 0% and one 100%, avoid division by zero. */
1240 combined_probability
= REG_BR_PROB_BASE
/ 2;
1242 combined_probability
= (((double) combined_probability
)
1244 * REG_BR_PROB_BASE
/ d
+ 0.5);
1248 /* Decide which heuristic to use. In case we didn't match anything,
1249 use no_prediction heuristic, in case we did match, use either
1250 first match or Dempster-Shaffer theory depending on the flags. */
1252 if (best_predictor
!= END_PREDICTORS
)
1256 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1260 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1261 !first_match
? REASON_NONE
: REASON_IGNORED
);
1263 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1264 first_match
? REASON_NONE
: REASON_IGNORED
);
1268 combined_probability
= best_probability
;
1269 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1273 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1275 enum br_predictor predictor
= pred
->ep_predictor
;
1276 int probability
= pred
->ep_probability
;
1278 dump_prediction (dump_file
, predictor
, probability
, bb
,
1279 (!first_match
|| best_predictor
== predictor
)
1280 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1283 clear_bb_predictions (bb
);
1285 if (!bb
->count
.initialized_p () && !dry_run
)
1287 first
->probability
= combined_probability
;
1288 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1292 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1293 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1295 T1 and T2 should be one of the following cases:
1296 1. T1 is SSA_NAME, T2 is NULL
1297 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1298 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1301 strips_small_constant (tree t1
, tree t2
)
1308 else if (TREE_CODE (t1
) == SSA_NAME
)
1310 else if (tree_fits_shwi_p (t1
))
1311 value
= tree_to_shwi (t1
);
1317 else if (tree_fits_shwi_p (t2
))
1318 value
= tree_to_shwi (t2
);
1319 else if (TREE_CODE (t2
) == SSA_NAME
)
1327 if (value
<= 4 && value
>= -4)
1333 /* Return the SSA_NAME in T or T's operands.
1334 Return NULL if SSA_NAME cannot be found. */
1337 get_base_value (tree t
)
1339 if (TREE_CODE (t
) == SSA_NAME
)
1342 if (!BINARY_CLASS_P (t
))
1345 switch (TREE_OPERAND_LENGTH (t
))
1348 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1350 return strips_small_constant (TREE_OPERAND (t
, 0),
1351 TREE_OPERAND (t
, 1));
1357 /* Check the compare STMT in LOOP. If it compares an induction
1358 variable to a loop invariant, return true, and save
1359 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1360 Otherwise return false and set LOOP_INVAIANT to NULL. */
1363 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1364 tree
*loop_invariant
,
1365 enum tree_code
*compare_code
,
1369 tree op0
, op1
, bound
, base
;
1371 enum tree_code code
;
1374 code
= gimple_cond_code (stmt
);
1375 *loop_invariant
= NULL
;
1391 op0
= gimple_cond_lhs (stmt
);
1392 op1
= gimple_cond_rhs (stmt
);
1394 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1395 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1397 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1399 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1401 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1402 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1404 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1405 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1408 if (integer_zerop (iv0
.step
))
1410 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1411 code
= invert_tree_comparison (code
, false);
1414 if (tree_fits_shwi_p (iv1
.step
))
1423 if (tree_fits_shwi_p (iv0
.step
))
1429 if (TREE_CODE (bound
) != INTEGER_CST
)
1430 bound
= get_base_value (bound
);
1433 if (TREE_CODE (base
) != INTEGER_CST
)
1434 base
= get_base_value (base
);
1438 *loop_invariant
= bound
;
1439 *compare_code
= code
;
1441 *loop_iv_base
= base
;
1445 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1448 expr_coherent_p (tree t1
, tree t2
)
1451 tree ssa_name_1
= NULL
;
1452 tree ssa_name_2
= NULL
;
1454 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1455 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1460 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1462 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1465 /* Check to see if t1 is expressed/defined with t2. */
1466 stmt
= SSA_NAME_DEF_STMT (t1
);
1467 gcc_assert (stmt
!= NULL
);
1468 if (is_gimple_assign (stmt
))
1470 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1471 if (ssa_name_1
&& ssa_name_1
== t2
)
1475 /* Check to see if t2 is expressed/defined with t1. */
1476 stmt
= SSA_NAME_DEF_STMT (t2
);
1477 gcc_assert (stmt
!= NULL
);
1478 if (is_gimple_assign (stmt
))
1480 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1481 if (ssa_name_2
&& ssa_name_2
== t1
)
1485 /* Compare if t1 and t2's def_stmts are identical. */
1486 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1492 /* Return true if E is predicted by one of loop heuristics. */
1495 predicted_by_loop_heuristics_p (basic_block bb
)
1497 struct edge_prediction
*i
;
1498 edge_prediction
**preds
= bb_predictions
->get (bb
);
1503 for (i
= *preds
; i
; i
= i
->ep_next
)
1504 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1505 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1506 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1507 || i
->ep_predictor
== PRED_LOOP_EXIT
1508 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1509 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1514 /* Predict branch probability of BB when BB contains a branch that compares
1515 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1516 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1519 for (int i = 0; i < bound; i++) {
1526 In this loop, we will predict the branch inside the loop to be taken. */
1529 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1530 tree loop_bound_var
,
1531 tree loop_iv_base_var
,
1532 enum tree_code loop_bound_code
,
1533 int loop_bound_step
)
1536 tree compare_var
, compare_base
;
1537 enum tree_code compare_code
;
1538 tree compare_step_var
;
1542 if (predicted_by_loop_heuristics_p (bb
))
1545 stmt
= last_stmt (bb
);
1546 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1548 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1555 /* Find the taken edge. */
1556 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1557 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1560 /* When comparing an IV to a loop invariant, NE is more likely to be
1561 taken while EQ is more likely to be not-taken. */
1562 if (compare_code
== NE_EXPR
)
1564 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1567 else if (compare_code
== EQ_EXPR
)
1569 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1573 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1576 /* If loop bound, base and compare bound are all constants, we can
1577 calculate the probability directly. */
1578 if (tree_fits_shwi_p (loop_bound_var
)
1579 && tree_fits_shwi_p (compare_var
)
1580 && tree_fits_shwi_p (compare_base
))
1583 bool overflow
, overall_overflow
= false;
1584 widest_int compare_count
, tem
;
1586 /* (loop_bound - base) / compare_step */
1587 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1588 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1589 overall_overflow
|= overflow
;
1590 widest_int loop_count
= wi::div_trunc (tem
,
1591 wi::to_widest (compare_step_var
),
1593 overall_overflow
|= overflow
;
1595 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1596 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1598 /* (loop_bound - compare_bound) / compare_step */
1599 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1600 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1601 overall_overflow
|= overflow
;
1602 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1604 overall_overflow
|= overflow
;
1608 /* (compare_bound - base) / compare_step */
1609 tem
= wi::sub (wi::to_widest (compare_var
),
1610 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1611 overall_overflow
|= overflow
;
1612 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1614 overall_overflow
|= overflow
;
1616 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1618 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1620 if (wi::neg_p (compare_count
))
1622 if (wi::neg_p (loop_count
))
1624 if (loop_count
== 0)
1626 else if (wi::cmps (compare_count
, loop_count
) == 1)
1627 probability
= REG_BR_PROB_BASE
;
1630 tem
= compare_count
* REG_BR_PROB_BASE
;
1631 tem
= wi::udiv_trunc (tem
, loop_count
);
1632 probability
= tem
.to_uhwi ();
1635 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1636 if (!overall_overflow
)
1637 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1642 if (expr_coherent_p (loop_bound_var
, compare_var
))
1644 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1645 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1646 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1647 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1648 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1649 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1650 else if (loop_bound_code
== NE_EXPR
)
1652 /* If the loop backedge condition is "(i != bound)", we do
1653 the comparison based on the step of IV:
1654 * step < 0 : backedge condition is like (i > bound)
1655 * step > 0 : backedge condition is like (i < bound) */
1656 gcc_assert (loop_bound_step
!= 0);
1657 if (loop_bound_step
> 0
1658 && (compare_code
== LT_EXPR
1659 || compare_code
== LE_EXPR
))
1660 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1661 else if (loop_bound_step
< 0
1662 && (compare_code
== GT_EXPR
1663 || compare_code
== GE_EXPR
))
1664 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1666 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1669 /* The branch is predicted not-taken if loop_bound_code is
1670 opposite with compare_code. */
1671 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1673 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1676 for (i = s; i < h; i++)
1678 The branch should be predicted taken. */
1679 if (loop_bound_step
> 0
1680 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1681 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1682 else if (loop_bound_step
< 0
1683 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1684 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1686 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1690 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1691 exits are resulted from short-circuit conditions that will generate an
1694 if (foo() || global > 10)
1697 This will be translated into:
1702 if foo() goto BB6 else goto BB5
1704 if global > 10 goto BB6 else goto BB7
1708 iftmp = (PHI 0(BB5), 1(BB6))
1709 if iftmp == 1 goto BB8 else goto BB3
1711 outside of the loop...
1713 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1714 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1715 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1716 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1719 predict_extra_loop_exits (edge exit_edge
)
1722 bool check_value_one
;
1723 gimple
*lhs_def_stmt
;
1725 tree cmp_rhs
, cmp_lhs
;
1729 last
= last_stmt (exit_edge
->src
);
1732 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1736 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1737 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1738 if (!TREE_CONSTANT (cmp_rhs
)
1739 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1741 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1744 /* If check_value_one is true, only the phi_args with value '1' will lead
1745 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1747 check_value_one
= (((integer_onep (cmp_rhs
))
1748 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1749 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1751 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1755 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1759 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1763 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1764 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1766 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1768 if ((check_value_one
^ integer_onep (val
)) == 1)
1770 if (EDGE_COUNT (e
->src
->succs
) != 1)
1772 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1776 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1777 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1782 /* Predict edge probabilities by exploiting loop structure. */
1785 predict_loops (void)
1789 hash_set
<struct loop
*> with_recursion(10);
1791 FOR_EACH_BB_FN (bb
, cfun
)
1793 gimple_stmt_iterator gsi
;
1796 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1797 if (is_gimple_call (gsi_stmt (gsi
))
1798 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1799 && recursive_call_p (current_function_decl
, decl
))
1801 loop
= bb
->loop_father
;
1802 while (loop
&& !with_recursion
.add (loop
))
1803 loop
= loop_outer (loop
);
1807 /* Try to predict out blocks in a loop that are not part of a
1809 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1811 basic_block bb
, *bbs
;
1812 unsigned j
, n_exits
= 0;
1814 struct tree_niter_desc niter_desc
;
1816 struct nb_iter_bound
*nb_iter
;
1817 enum tree_code loop_bound_code
= ERROR_MARK
;
1818 tree loop_bound_step
= NULL
;
1819 tree loop_bound_var
= NULL
;
1820 tree loop_iv_base
= NULL
;
1822 bool recursion
= with_recursion
.contains (loop
);
1824 exits
= get_loop_exit_edges (loop
);
1825 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1826 if (!unlikely_executed_edge_p (ex
) && !(ex
->flags
& EDGE_ABNORMAL_CALL
))
1834 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1835 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1836 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1837 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1838 && max_loop_iterations_int (loop
) >= 0)
1841 "Loop %d iterates at most %i times.\n", loop
->num
,
1842 (int)max_loop_iterations_int (loop
));
1844 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1845 && likely_max_loop_iterations_int (loop
) >= 0)
1847 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1848 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1851 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1854 HOST_WIDE_INT nitercst
;
1855 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1857 enum br_predictor predictor
;
1860 if (unlikely_executed_edge_p (ex
)
1861 || (ex
->flags
& EDGE_ABNORMAL_CALL
))
1863 /* Loop heuristics do not expect exit conditional to be inside
1864 inner loop. We predict from innermost to outermost loop. */
1865 if (predicted_by_loop_heuristics_p (ex
->src
))
1867 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1868 fprintf (dump_file
, "Skipping exit %i->%i because "
1869 "it is already predicted.\n",
1870 ex
->src
->index
, ex
->dest
->index
);
1873 predict_extra_loop_exits (ex
);
1875 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1876 niter
= niter_desc
.niter
;
1877 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1878 niter
= loop_niter_by_eval (loop
, ex
);
1879 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1880 && TREE_CODE (niter
) == INTEGER_CST
)
1882 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1883 ex
->src
->index
, ex
->dest
->index
,
1885 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1886 fprintf (dump_file
, " times.\n");
1889 if (TREE_CODE (niter
) == INTEGER_CST
)
1891 if (tree_fits_uhwi_p (niter
)
1893 && compare_tree_int (niter
, max
- 1) == -1)
1894 nitercst
= tree_to_uhwi (niter
) + 1;
1897 predictor
= PRED_LOOP_ITERATIONS
;
1899 /* If we have just one exit and we can derive some information about
1900 the number of iterations of the loop from the statements inside
1901 the loop, use it to predict this exit. */
1902 else if (n_exits
== 1
1903 && estimated_stmt_executions (loop
, &nit
))
1905 if (wi::gtu_p (nit
, max
))
1908 nitercst
= nit
.to_shwi ();
1909 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1911 /* If we have likely upper bound, trust it for very small iteration
1912 counts. Such loops would otherwise get mispredicted by standard
1913 LOOP_EXIT heuristics. */
1914 else if (n_exits
== 1
1915 && likely_max_stmt_executions (loop
, &nit
)
1917 RDIV (REG_BR_PROB_BASE
,
1921 ? PRED_LOOP_EXIT_WITH_RECURSION
1922 : PRED_LOOP_EXIT
].hitrate
)))
1924 nitercst
= nit
.to_shwi ();
1925 predictor
= PRED_LOOP_ITERATIONS_MAX
;
1929 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1930 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
1931 ex
->src
->index
, ex
->dest
->index
);
1935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1936 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
1937 (int)nitercst
, predictor_info
[predictor
].name
);
1938 /* If the prediction for number of iterations is zero, do not
1939 predict the exit edges. */
1943 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
1944 predict_edge (ex
, predictor
, probability
);
1948 /* Find information about loop bound variables. */
1949 for (nb_iter
= loop
->bounds
; nb_iter
;
1950 nb_iter
= nb_iter
->next
)
1952 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1954 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1957 if (!stmt
&& last_stmt (loop
->header
)
1958 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1959 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1961 is_comparison_with_loop_invariant_p (stmt
, loop
,
1967 bbs
= get_loop_body (loop
);
1969 for (j
= 0; j
< loop
->num_nodes
; j
++)
1976 /* Bypass loop heuristics on continue statement. These
1977 statements construct loops via "non-loop" constructs
1978 in the source language and are better to be handled
1980 if (predicted_by_p (bb
, PRED_CONTINUE
))
1982 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1983 fprintf (dump_file
, "BB %i predicted by continue.\n",
1988 /* If we already used more reliable loop exit predictors, do not
1989 bother with PRED_LOOP_EXIT. */
1990 if (!predicted_by_loop_heuristics_p (bb
))
1992 /* For loop with many exits we don't want to predict all exits
1993 with the pretty large probability, because if all exits are
1994 considered in row, the loop would be predicted to iterate
1995 almost never. The code to divide probability by number of
1996 exits is very rough. It should compute the number of exits
1997 taken in each patch through function (not the overall number
1998 of exits that might be a lot higher for loops with wide switch
1999 statements in them) and compute n-th square root.
2001 We limit the minimal probability by 2% to avoid
2002 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2003 as this was causing regression in perl benchmark containing such
2006 int probability
= ((REG_BR_PROB_BASE
2009 ? PRED_LOOP_EXIT_WITH_RECURSION
2010 : PRED_LOOP_EXIT
].hitrate
)
2012 if (probability
< HITRATE (2))
2013 probability
= HITRATE (2);
2014 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2015 if (e
->dest
->index
< NUM_FIXED_BLOCKS
2016 || !flow_bb_inside_loop_p (loop
, e
->dest
))
2018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2020 "Predicting exit %i->%i with prob %i.\n",
2021 e
->src
->index
, e
->dest
->index
, probability
);
2023 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
2024 : PRED_LOOP_EXIT
, probability
);
2028 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
2030 tree_to_shwi (loop_bound_step
));
2033 /* In the following code
2038 guess that cond is unlikely. */
2039 if (loop_outer (loop
)->num
)
2041 basic_block bb
= NULL
;
2042 edge preheader_edge
= loop_preheader_edge (loop
);
2044 if (single_pred_p (preheader_edge
->src
)
2045 && single_succ_p (preheader_edge
->src
))
2046 preheader_edge
= single_pred_edge (preheader_edge
->src
);
2048 gimple
*stmt
= last_stmt (preheader_edge
->src
);
2049 /* Pattern match fortran loop preheader:
2050 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2051 _17 = (logical(kind=4)) _16;
2057 Loop guard branch prediction says nothing about duplicated loop
2058 headers produced by fortran frontend and in this case we want
2059 to predict paths leading to this preheader. */
2062 && gimple_code (stmt
) == GIMPLE_COND
2063 && gimple_cond_code (stmt
) == NE_EXPR
2064 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
2065 && integer_zerop (gimple_cond_rhs (stmt
)))
2067 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2068 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
2069 && gimple_expr_code (call_stmt
) == NOP_EXPR
2070 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
2071 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
2072 if (gimple_call_internal_p (call_stmt
, IFN_BUILTIN_EXPECT
)
2073 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
2074 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
2075 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
2076 == PRED_FORTRAN_LOOP_PREHEADER
)
2077 bb
= preheader_edge
->src
;
2081 if (!dominated_by_p (CDI_DOMINATORS
,
2082 loop_outer (loop
)->latch
, loop
->header
))
2083 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
2085 ? PRED_LOOP_GUARD_WITH_RECURSION
2092 if (!dominated_by_p (CDI_DOMINATORS
,
2093 loop_outer (loop
)->latch
, bb
))
2094 predict_paths_leading_to (bb
,
2096 ? PRED_LOOP_GUARD_WITH_RECURSION
2103 /* Free basic blocks from get_loop_body. */
2108 /* Attempt to predict probabilities of BB outgoing edges using local
2111 bb_estimate_probability_locally (basic_block bb
)
2113 rtx_insn
*last_insn
= BB_END (bb
);
2116 if (! can_predict_insn_p (last_insn
))
2118 cond
= get_condition (last_insn
, NULL
, false, false);
2122 /* Try "pointer heuristic."
2123 A comparison ptr == 0 is predicted as false.
2124 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2125 if (COMPARISON_P (cond
)
2126 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2127 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2129 if (GET_CODE (cond
) == EQ
)
2130 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2131 else if (GET_CODE (cond
) == NE
)
2132 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2136 /* Try "opcode heuristic."
2137 EQ tests are usually false and NE tests are usually true. Also,
2138 most quantities are positive, so we can make the appropriate guesses
2139 about signed comparisons against zero. */
2140 switch (GET_CODE (cond
))
2143 /* Unconditional branch. */
2144 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2145 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2150 /* Floating point comparisons appears to behave in a very
2151 unpredictable way because of special role of = tests in
2153 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2155 /* Comparisons with 0 are often used for booleans and there is
2156 nothing useful to predict about them. */
2157 else if (XEXP (cond
, 1) == const0_rtx
2158 || XEXP (cond
, 0) == const0_rtx
)
2161 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2166 /* Floating point comparisons appears to behave in a very
2167 unpredictable way because of special role of = tests in
2169 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2171 /* Comparisons with 0 are often used for booleans and there is
2172 nothing useful to predict about them. */
2173 else if (XEXP (cond
, 1) == const0_rtx
2174 || XEXP (cond
, 0) == const0_rtx
)
2177 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2181 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2185 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2190 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2191 || XEXP (cond
, 1) == constm1_rtx
)
2192 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2197 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2198 || XEXP (cond
, 1) == constm1_rtx
)
2199 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2207 /* Set edge->probability for each successor edge of BB. */
2209 guess_outgoing_edge_probabilities (basic_block bb
)
2211 bb_estimate_probability_locally (bb
);
2212 combine_predictions_for_insn (BB_END (bb
), bb
);
2215 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
2217 /* Helper function for expr_expected_value. */
2220 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2221 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
2226 *predictor
= PRED_UNCONDITIONAL
;
2228 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2230 if (TREE_CONSTANT (op0
))
2233 if (code
== IMAGPART_EXPR
)
2235 if (TREE_CODE (TREE_OPERAND (op0
, 0)) == SSA_NAME
)
2237 def
= SSA_NAME_DEF_STMT (TREE_OPERAND (op0
, 0));
2238 if (is_gimple_call (def
)
2239 && gimple_call_internal_p (def
)
2240 && (gimple_call_internal_fn (def
)
2241 == IFN_ATOMIC_COMPARE_EXCHANGE
))
2243 /* Assume that any given atomic operation has low contention,
2244 and thus the compare-and-swap operation succeeds. */
2246 *predictor
= PRED_COMPARE_AND_SWAP
;
2247 return build_one_cst (TREE_TYPE (op0
));
2252 if (code
!= SSA_NAME
)
2255 def
= SSA_NAME_DEF_STMT (op0
);
2257 /* If we were already here, break the infinite cycle. */
2258 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2261 if (gimple_code (def
) == GIMPLE_PHI
)
2263 /* All the arguments of the PHI node must have the same constant
2265 int i
, n
= gimple_phi_num_args (def
);
2266 tree val
= NULL
, new_val
;
2268 for (i
= 0; i
< n
; i
++)
2270 tree arg
= PHI_ARG_DEF (def
, i
);
2271 enum br_predictor predictor2
;
2273 /* If this PHI has itself as an argument, we cannot
2274 determine the string length of this argument. However,
2275 if we can find an expected constant value for the other
2276 PHI args then we can still be sure that this is
2277 likely a constant. So be optimistic and just
2278 continue with the next argument. */
2279 if (arg
== PHI_RESULT (def
))
2282 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
2284 /* It is difficult to combine value predictors. Simply assume
2285 that later predictor is weaker and take its prediction. */
2286 if (predictor
&& *predictor
< predictor2
)
2287 *predictor
= predictor2
;
2292 else if (!operand_equal_p (val
, new_val
, false))
2297 if (is_gimple_assign (def
))
2299 if (gimple_assign_lhs (def
) != op0
)
2302 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2303 gimple_assign_rhs1 (def
),
2304 gimple_assign_rhs_code (def
),
2305 gimple_assign_rhs2 (def
),
2306 visited
, predictor
);
2309 if (is_gimple_call (def
))
2311 tree decl
= gimple_call_fndecl (def
);
2314 if (gimple_call_internal_p (def
)
2315 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2317 gcc_assert (gimple_call_num_args (def
) == 3);
2318 tree val
= gimple_call_arg (def
, 0);
2319 if (TREE_CONSTANT (val
))
2323 tree val2
= gimple_call_arg (def
, 2);
2324 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2325 && tree_fits_uhwi_p (val2
)
2326 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2327 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2329 return gimple_call_arg (def
, 1);
2333 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2334 switch (DECL_FUNCTION_CODE (decl
))
2336 case BUILT_IN_EXPECT
:
2339 if (gimple_call_num_args (def
) != 2)
2341 val
= gimple_call_arg (def
, 0);
2342 if (TREE_CONSTANT (val
))
2345 *predictor
= PRED_BUILTIN_EXPECT
;
2346 return gimple_call_arg (def
, 1);
2349 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2350 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2351 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2352 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2353 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2354 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2355 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2356 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2357 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2358 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2359 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2360 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2361 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2362 /* Assume that any given atomic operation has low contention,
2363 and thus the compare-and-swap operation succeeds. */
2365 *predictor
= PRED_COMPARE_AND_SWAP
;
2366 return boolean_true_node
;
2375 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2378 enum br_predictor predictor2
;
2379 op0
= expr_expected_value (op0
, visited
, predictor
);
2382 op1
= expr_expected_value (op1
, visited
, &predictor2
);
2383 if (predictor
&& *predictor
< predictor2
)
2384 *predictor
= predictor2
;
2387 res
= fold_build2 (code
, type
, op0
, op1
);
2388 if (TREE_CONSTANT (res
))
2392 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2395 op0
= expr_expected_value (op0
, visited
, predictor
);
2398 res
= fold_build1 (code
, type
, op0
);
2399 if (TREE_CONSTANT (res
))
2406 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2407 The function is used by builtin_expect branch predictor so the evidence
2408 must come from this construct and additional possible constant folding.
2410 We may want to implement more involved value guess (such as value range
2411 propagation based prediction), but such tricks shall go to new
2415 expr_expected_value (tree expr
, bitmap visited
,
2416 enum br_predictor
*predictor
)
2418 enum tree_code code
;
2421 if (TREE_CONSTANT (expr
))
2424 *predictor
= PRED_UNCONDITIONAL
;
2428 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2429 return expr_expected_value_1 (TREE_TYPE (expr
),
2430 op0
, code
, op1
, visited
, predictor
);
2433 /* Predict using opcode of the last statement in basic block. */
2435 tree_predict_by_opcode (basic_block bb
)
2437 gimple
*stmt
= last_stmt (bb
);
2444 enum br_predictor predictor
;
2446 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2448 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2449 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2451 op0
= gimple_cond_lhs (stmt
);
2452 op1
= gimple_cond_rhs (stmt
);
2453 cmp
= gimple_cond_code (stmt
);
2454 type
= TREE_TYPE (op0
);
2455 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, auto_bitmap (),
2457 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2459 if (predictor
== PRED_BUILTIN_EXPECT
)
2461 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2463 gcc_assert (percent
>= 0 && percent
<= 100);
2464 if (integer_zerop (val
))
2465 percent
= 100 - percent
;
2466 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2469 predict_edge_def (then_edge
, predictor
,
2470 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2472 /* Try "pointer heuristic."
2473 A comparison ptr == 0 is predicted as false.
2474 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2475 if (POINTER_TYPE_P (type
))
2478 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2479 else if (cmp
== NE_EXPR
)
2480 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2484 /* Try "opcode heuristic."
2485 EQ tests are usually false and NE tests are usually true. Also,
2486 most quantities are positive, so we can make the appropriate guesses
2487 about signed comparisons against zero. */
2492 /* Floating point comparisons appears to behave in a very
2493 unpredictable way because of special role of = tests in
2495 if (FLOAT_TYPE_P (type
))
2497 /* Comparisons with 0 are often used for booleans and there is
2498 nothing useful to predict about them. */
2499 else if (integer_zerop (op0
) || integer_zerop (op1
))
2502 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2507 /* Floating point comparisons appears to behave in a very
2508 unpredictable way because of special role of = tests in
2510 if (FLOAT_TYPE_P (type
))
2512 /* Comparisons with 0 are often used for booleans and there is
2513 nothing useful to predict about them. */
2514 else if (integer_zerop (op0
)
2515 || integer_zerop (op1
))
2518 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2522 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2525 case UNORDERED_EXPR
:
2526 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2531 if (integer_zerop (op1
)
2532 || integer_onep (op1
)
2533 || integer_all_onesp (op1
)
2536 || real_minus_onep (op1
))
2537 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2542 if (integer_zerop (op1
)
2543 || integer_onep (op1
)
2544 || integer_all_onesp (op1
)
2547 || real_minus_onep (op1
))
2548 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2556 /* Returns TRUE if the STMT is exit(0) like statement. */
2559 is_exit_with_zero_arg (const gimple
*stmt
)
2561 /* This is not exit, _exit or _Exit. */
2562 if (!gimple_call_builtin_p (stmt
, BUILT_IN_EXIT
)
2563 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT
)
2564 && !gimple_call_builtin_p (stmt
, BUILT_IN__EXIT2
))
2567 /* Argument is an interger zero. */
2568 return integer_zerop (gimple_call_arg (stmt
, 0));
2571 /* Try to guess whether the value of return means error code. */
2573 static enum br_predictor
2574 return_prediction (tree val
, enum prediction
*prediction
)
2578 return PRED_NO_PREDICTION
;
2579 /* Different heuristics for pointers and scalars. */
2580 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2582 /* NULL is usually not returned. */
2583 if (integer_zerop (val
))
2585 *prediction
= NOT_TAKEN
;
2586 return PRED_NULL_RETURN
;
2589 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2591 /* Negative return values are often used to indicate
2593 if (TREE_CODE (val
) == INTEGER_CST
2594 && tree_int_cst_sgn (val
) < 0)
2596 *prediction
= NOT_TAKEN
;
2597 return PRED_NEGATIVE_RETURN
;
2599 /* Constant return values seems to be commonly taken.
2600 Zero/one often represent booleans so exclude them from the
2602 if (TREE_CONSTANT (val
)
2603 && (!integer_zerop (val
) && !integer_onep (val
)))
2605 *prediction
= NOT_TAKEN
;
2606 return PRED_CONST_RETURN
;
2609 return PRED_NO_PREDICTION
;
2612 /* Find the basic block with return expression and look up for possible
2613 return value trying to apply RETURN_PREDICTION heuristics. */
2615 apply_return_prediction (void)
2617 greturn
*return_stmt
= NULL
;
2621 int phi_num_args
, i
;
2622 enum br_predictor pred
;
2623 enum prediction direction
;
2626 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2628 gimple
*last
= last_stmt (e
->src
);
2630 && gimple_code (last
) == GIMPLE_RETURN
)
2632 return_stmt
= as_a
<greturn
*> (last
);
2638 return_val
= gimple_return_retval (return_stmt
);
2641 if (TREE_CODE (return_val
) != SSA_NAME
2642 || !SSA_NAME_DEF_STMT (return_val
)
2643 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2645 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2646 phi_num_args
= gimple_phi_num_args (phi
);
2647 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2649 /* Avoid the degenerate case where all return values form the function
2650 belongs to same category (ie they are all positive constants)
2651 so we can hardly say something about them. */
2652 for (i
= 1; i
< phi_num_args
; i
++)
2653 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2655 if (i
!= phi_num_args
)
2656 for (i
= 0; i
< phi_num_args
; i
++)
2658 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2659 if (pred
!= PRED_NO_PREDICTION
)
2660 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2665 /* Look for basic block that contains unlikely to happen events
2666 (such as noreturn calls) and mark all paths leading to execution
2667 of this basic blocks as unlikely. */
2670 tree_bb_level_predictions (void)
2673 bool has_return_edges
= false;
2677 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2678 if (!unlikely_executed_edge_p (e
) && !(e
->flags
& EDGE_ABNORMAL_CALL
))
2680 has_return_edges
= true;
2684 apply_return_prediction ();
2686 FOR_EACH_BB_FN (bb
, cfun
)
2688 gimple_stmt_iterator gsi
;
2690 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2692 gimple
*stmt
= gsi_stmt (gsi
);
2695 if (is_gimple_call (stmt
))
2697 if (gimple_call_noreturn_p (stmt
)
2699 && !is_exit_with_zero_arg (stmt
))
2700 predict_paths_leading_to (bb
, PRED_NORETURN
,
2702 decl
= gimple_call_fndecl (stmt
);
2704 && lookup_attribute ("cold",
2705 DECL_ATTRIBUTES (decl
)))
2706 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2708 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2709 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2712 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2714 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2715 gimple_predict_outcome (stmt
));
2716 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2717 hints to callers. */
2723 /* Callback for hash_map::traverse, asserts that the pointer map is
2727 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2730 gcc_assert (!value
);
2734 /* Predict branch probabilities and estimate profile for basic block BB.
2735 When LOCAL_ONLY is set do not use any global properties of CFG. */
2738 tree_estimate_probability_bb (basic_block bb
, bool local_only
)
2743 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2745 /* Look for block we are guarding (ie we dominate it,
2746 but it doesn't postdominate us). */
2747 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2749 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2750 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2752 gimple_stmt_iterator bi
;
2754 /* The call heuristic claims that a guarded function call
2755 is improbable. This is because such calls are often used
2756 to signal exceptional situations such as printing error
2758 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2761 gimple
*stmt
= gsi_stmt (bi
);
2762 if (is_gimple_call (stmt
)
2763 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
2764 /* Constant and pure calls are hardly used to signalize
2765 something exceptional. */
2766 && gimple_has_side_effects (stmt
))
2768 if (gimple_call_fndecl (stmt
))
2769 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2770 else if (virtual_method_call_p (gimple_call_fn (stmt
)))
2771 predict_edge_def (e
, PRED_POLYMORPHIC_CALL
, NOT_TAKEN
);
2773 predict_edge_def (e
, PRED_INDIR_CALL
, TAKEN
);
2779 tree_predict_by_opcode (bb
);
2782 /* Predict branch probabilities and estimate profile of the tree CFG.
2783 This function can be called from the loop optimizers to recompute
2784 the profile information.
2785 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2788 tree_estimate_probability (bool dry_run
)
2792 add_noreturn_fake_exit_edges ();
2793 connect_infinite_loops_to_exit ();
2794 /* We use loop_niter_by_eval, which requires that the loops have
2796 create_preheaders (CP_SIMPLE_PREHEADERS
);
2797 calculate_dominance_info (CDI_POST_DOMINATORS
);
2799 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2800 tree_bb_level_predictions ();
2801 record_loop_exits ();
2803 if (number_of_loops (cfun
) > 1)
2806 FOR_EACH_BB_FN (bb
, cfun
)
2807 tree_estimate_probability_bb (bb
, false);
2809 FOR_EACH_BB_FN (bb
, cfun
)
2810 combine_predictions_for_bb (bb
, dry_run
);
2813 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2815 delete bb_predictions
;
2816 bb_predictions
= NULL
;
2819 estimate_bb_frequencies (false);
2820 free_dominance_info (CDI_POST_DOMINATORS
);
2821 remove_fake_exit_edges ();
2824 /* Set edge->probability for each successor edge of BB. */
2826 tree_guess_outgoing_edge_probabilities (basic_block bb
)
2828 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2829 tree_estimate_probability_bb (bb
, true);
2830 combine_predictions_for_bb (bb
, false);
2832 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2833 delete bb_predictions
;
2834 bb_predictions
= NULL
;
2837 /* Predict edges to successors of CUR whose sources are not postdominated by
2838 BB by PRED and recurse to all postdominators. */
2841 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2842 enum br_predictor pred
,
2843 enum prediction taken
,
2844 bitmap visited
, struct loop
*in_loop
= NULL
)
2850 /* If we exited the loop or CUR is unconditional in the loop, there is
2853 && (!flow_bb_inside_loop_p (in_loop
, cur
)
2854 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
2857 /* We are looking for all edges forming edge cut induced by
2858 set of all blocks postdominated by BB. */
2859 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2860 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2861 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2867 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2868 if (unlikely_executed_edge_p (e
))
2870 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2872 /* See if there is an edge from e->src that is not abnormal
2873 and does not lead to BB and does not exit the loop. */
2874 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2876 && !unlikely_executed_edge_p (e2
)
2877 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
2878 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
2884 /* If there is non-abnormal path leaving e->src, predict edge
2885 using predictor. Otherwise we need to look for paths
2888 The second may lead to infinite loop in the case we are predicitng
2889 regions that are only reachable by abnormal edges. We simply
2890 prevent visiting given BB twice. */
2893 if (!edge_predicted_by_p (e
, pred
, taken
))
2894 predict_edge_def (e
, pred
, taken
);
2896 else if (bitmap_set_bit (visited
, e
->src
->index
))
2897 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
2899 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2901 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2902 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
2905 /* Sets branch probabilities according to PREDiction and
2909 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2910 enum prediction taken
, struct loop
*in_loop
)
2912 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
2915 /* Like predict_paths_leading_to but take edge instead of basic block. */
2918 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2919 enum prediction taken
, struct loop
*in_loop
)
2921 bool has_nonloop_edge
= false;
2925 basic_block bb
= e
->src
;
2926 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2927 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2928 && !unlikely_executed_edge_p (e
)
2929 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2931 has_nonloop_edge
= true;
2934 if (!has_nonloop_edge
)
2936 predict_paths_for_bb (bb
, bb
, pred
, taken
, auto_bitmap (), in_loop
);
2939 predict_edge_def (e
, pred
, taken
);
2942 /* This is used to carry information about basic blocks. It is
2943 attached to the AUX field of the standard CFG block. */
2947 /* Estimated frequency of execution of basic_block. */
2950 /* To keep queue of basic blocks to process. */
2953 /* Number of predecessors we need to visit first. */
2957 /* Similar information for edges. */
2958 struct edge_prob_info
2960 /* In case edge is a loopback edge, the probability edge will be reached
2961 in case header is. Estimated number of iterations of the loop can be
2962 then computed as 1 / (1 - back_edge_prob). */
2963 sreal back_edge_prob
;
2964 /* True if the edge is a loopback edge in the natural loop. */
2965 unsigned int back_edge
:1;
2968 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2970 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2972 /* Helper function for estimate_bb_frequencies.
2973 Propagate the frequencies in blocks marked in
2974 TOVISIT, starting in HEAD. */
2977 propagate_freq (basic_block head
, bitmap tovisit
)
2986 /* For each basic block we need to visit count number of his predecessors
2987 we need to visit first. */
2988 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2993 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2995 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2997 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2999 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
3001 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
3003 "Irreducible region hit, ignoring edge to %i->%i\n",
3004 e
->src
->index
, bb
->index
);
3006 BLOCK_INFO (bb
)->npredecessors
= count
;
3007 /* When function never returns, we will never process exit block. */
3008 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3010 bb
->count
= profile_count::zero ();
3015 BLOCK_INFO (head
)->frequency
= 1;
3017 for (bb
= head
; bb
; bb
= nextbb
)
3020 sreal cyclic_probability
= 0;
3021 sreal frequency
= 0;
3023 nextbb
= BLOCK_INFO (bb
)->next
;
3024 BLOCK_INFO (bb
)->next
= NULL
;
3026 /* Compute frequency of basic block. */
3030 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3031 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
3032 || (e
->flags
& EDGE_DFS_BACK
));
3034 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3035 if (EDGE_INFO (e
)->back_edge
)
3037 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
3039 else if (!(e
->flags
& EDGE_DFS_BACK
))
3041 /* frequency += (e->probability
3042 * BLOCK_INFO (e->src)->frequency /
3043 REG_BR_PROB_BASE); */
3045 sreal tmp
= e
->probability
;
3046 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
3047 tmp
*= real_inv_br_prob_base
;
3051 if (cyclic_probability
== 0)
3053 BLOCK_INFO (bb
)->frequency
= frequency
;
3057 if (cyclic_probability
> real_almost_one
)
3058 cyclic_probability
= real_almost_one
;
3060 /* BLOCK_INFO (bb)->frequency = frequency
3061 / (1 - cyclic_probability) */
3063 cyclic_probability
= sreal (1) - cyclic_probability
;
3064 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
3068 bitmap_clear_bit (tovisit
, bb
->index
);
3070 e
= find_edge (bb
, head
);
3073 /* EDGE_INFO (e)->back_edge_prob
3074 = ((e->probability * BLOCK_INFO (bb)->frequency)
3075 / REG_BR_PROB_BASE); */
3077 sreal tmp
= e
->probability
;
3078 tmp
*= BLOCK_INFO (bb
)->frequency
;
3079 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
3082 /* Propagate to successor blocks. */
3083 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3084 if (!(e
->flags
& EDGE_DFS_BACK
)
3085 && BLOCK_INFO (e
->dest
)->npredecessors
)
3087 BLOCK_INFO (e
->dest
)->npredecessors
--;
3088 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3093 BLOCK_INFO (last
)->next
= e
->dest
;
3101 /* Estimate frequencies in loops at same nest level. */
3104 estimate_loops_at_level (struct loop
*first_loop
)
3108 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3113 auto_bitmap tovisit
;
3115 estimate_loops_at_level (loop
->inner
);
3117 /* Find current loop back edge and mark it. */
3118 e
= loop_latch_edge (loop
);
3119 EDGE_INFO (e
)->back_edge
= 1;
3121 bbs
= get_loop_body (loop
);
3122 for (i
= 0; i
< loop
->num_nodes
; i
++)
3123 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3125 propagate_freq (loop
->header
, tovisit
);
3129 /* Propagates frequencies through structure of loops. */
3132 estimate_loops (void)
3134 auto_bitmap tovisit
;
3137 /* Start by estimating the frequencies in the loops. */
3138 if (number_of_loops (cfun
) > 1)
3139 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3141 /* Now propagate the frequencies through all the blocks. */
3142 FOR_ALL_BB_FN (bb
, cfun
)
3144 bitmap_set_bit (tovisit
, bb
->index
);
3146 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3149 /* Drop the profile for NODE to guessed, and update its frequency based on
3150 whether it is expected to be hot given the CALL_COUNT. */
3153 drop_profile (struct cgraph_node
*node
, profile_count call_count
)
3155 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3156 /* In the case where this was called by another function with a
3157 dropped profile, call_count will be 0. Since there are no
3158 non-zero call counts to this function, we don't know for sure
3159 whether it is hot, and therefore it will be marked normal below. */
3160 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3164 "Dropping 0 profile for %s. %s based on calls.\n",
3166 hot
? "Function is hot" : "Function is normal");
3167 /* We only expect to miss profiles for functions that are reached
3168 via non-zero call edges in cases where the function may have
3169 been linked from another module or library (COMDATs and extern
3170 templates). See the comments below for handle_missing_profiles.
3171 Also, only warn in cases where the missing counts exceed the
3172 number of training runs. In certain cases with an execv followed
3173 by a no-return call the profile for the no-return call is not
3174 dumped and there can be a mismatch. */
3175 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3176 && call_count
> profile_info
->runs
)
3178 if (flag_profile_correction
)
3182 "Missing counts for called function %s\n",
3183 node
->dump_name ());
3186 warning (0, "Missing counts for called function %s",
3187 node
->dump_name ());
3191 FOR_ALL_BB_FN (bb
, fn
)
3193 bb
->count
= profile_count::uninitialized ();
3197 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3198 e
->count
= profile_count::uninitialized ();
3201 struct cgraph_edge
*e
;
3202 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3204 e
->count
= profile_count::uninitialized ();
3205 e
->frequency
= compute_call_stmt_bb_frequency (e
->caller
->decl
,
3206 gimple_bb (e
->call_stmt
));
3208 node
->count
= profile_count::uninitialized ();
3210 profile_status_for_fn (fn
)
3211 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3213 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3216 /* In the case of COMDAT routines, multiple object files will contain the same
3217 function and the linker will select one for the binary. In that case
3218 all the other copies from the profile instrument binary will be missing
3219 profile counts. Look for cases where this happened, due to non-zero
3220 call counts going to 0-count functions, and drop the profile to guessed
3221 so that we can use the estimated probabilities and avoid optimizing only
3224 The other case where the profile may be missing is when the routine
3225 is not going to be emitted to the object file, e.g. for "extern template"
3226 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3227 all other cases of non-zero calls to 0-count functions. */
3230 handle_missing_profiles (void)
3232 struct cgraph_node
*node
;
3233 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3234 auto_vec
<struct cgraph_node
*, 64> worklist
;
3236 /* See if 0 count function has non-0 count callers. In this case we
3237 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3238 FOR_EACH_DEFINED_FUNCTION (node
)
3240 struct cgraph_edge
*e
;
3241 profile_count call_count
= profile_count::zero ();
3242 gcov_type max_tp_first_run
= 0;
3243 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3245 if (!(node
->count
== profile_count::zero ()))
3247 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3248 if (e
->count
.initialized_p () && e
->count
> 0)
3250 call_count
= call_count
+ e
->count
;
3252 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3253 max_tp_first_run
= e
->caller
->tp_first_run
;
3256 /* If time profile is missing, let assign the maximum that comes from
3257 caller functions. */
3258 if (!node
->tp_first_run
&& max_tp_first_run
)
3259 node
->tp_first_run
= max_tp_first_run
+ 1;
3263 && (call_count
.apply_scale (unlikely_count_fraction
, 1)
3264 >= profile_info
->runs
))
3266 drop_profile (node
, call_count
);
3267 worklist
.safe_push (node
);
3271 /* Propagate the profile dropping to other 0-count COMDATs that are
3272 potentially called by COMDATs we already dropped the profile on. */
3273 while (worklist
.length () > 0)
3275 struct cgraph_edge
*e
;
3277 node
= worklist
.pop ();
3278 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3280 struct cgraph_node
*callee
= e
->callee
;
3281 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3283 if (callee
->count
> 0)
3285 if ((DECL_COMDAT (callee
->decl
) || DECL_EXTERNAL (callee
->decl
))
3287 && profile_status_for_fn (fn
) == PROFILE_READ
)
3289 drop_profile (node
, profile_count::zero ());
3290 worklist
.safe_push (callee
);
3296 /* Convert counts measured by profile driven feedback to frequencies.
3297 Return nonzero iff there was any nonzero execution count. */
3300 counts_to_freqs (void)
3302 gcov_type count_max
;
3303 profile_count true_count_max
= profile_count::zero ();
3306 /* Don't overwrite the estimated frequencies when the profile for
3307 the function is missing. We may drop this function PROFILE_GUESSED
3308 later in drop_profile (). */
3309 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
.initialized_p ()
3310 || ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ())
3313 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3314 if (bb
->count
> true_count_max
)
3315 true_count_max
= bb
->count
;
3317 /* If we have no counts to base frequencies on, keep those that are
3319 if (!(true_count_max
> 0))
3322 count_max
= true_count_max
.to_gcov_type ();
3324 FOR_ALL_BB_FN (bb
, cfun
)
3325 if (bb
->count
.initialized_p ())
3326 bb
->frequency
= RDIV (bb
->count
.to_gcov_type () * BB_FREQ_MAX
, count_max
);
3331 /* Return true if function is likely to be expensive, so there is no point to
3332 optimize performance of prologue, epilogue or do inlining at the expense
3333 of code size growth. THRESHOLD is the limit of number of instructions
3334 function can execute at average to be still considered not expensive. */
3337 expensive_function_p (int threshold
)
3339 unsigned int sum
= 0;
3343 /* We can not compute accurately for large thresholds due to scaled
3345 gcc_assert (threshold
<= BB_FREQ_MAX
);
3347 /* Frequencies are out of range. This either means that function contains
3348 internal loop executing more than BB_FREQ_MAX times or profile feedback
3349 is available and function has not been executed at all. */
3350 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
3353 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
3354 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
3355 FOR_EACH_BB_FN (bb
, cfun
)
3359 FOR_BB_INSNS (bb
, insn
)
3360 if (active_insn_p (insn
))
3362 sum
+= bb
->frequency
;
3371 /* Determine basic blocks/edges that are known to be unlikely executed and set
3372 their counters to zero.
3373 This is done with first identifying obviously unlikely BBs/edges and then
3374 propagating in both directions. */
3377 determine_unlikely_bbs ()
3380 auto_vec
<basic_block
, 64> worklist
;
3384 FOR_EACH_BB_FN (bb
, cfun
)
3386 if (!(bb
->count
== profile_count::zero ())
3387 && unlikely_executed_bb_p (bb
))
3389 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3390 fprintf (dump_file
, "Basic block %i is locally unlikely\n",
3392 bb
->count
= profile_count::zero ();
3395 if (bb
->count
== profile_count::zero ())
3398 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3399 e
->count
= profile_count::zero ();
3402 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3403 if (!(e
->count
== profile_count::zero ())
3404 && unlikely_executed_edge_p (e
))
3406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3407 fprintf (dump_file
, "Edge %i->%i is locally unlikely\n",
3408 bb
->index
, e
->dest
->index
);
3409 e
->count
= profile_count::zero ();
3412 gcc_checking_assert (!bb
->aux
);
3415 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()))
3417 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
= (void *)(size_t) 1;
3418 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3420 while (worklist
.length () > 0)
3422 bb
= worklist
.pop ();
3423 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3424 if (!(e
->count
== profile_count::zero ())
3425 && !(e
->dest
->count
== profile_count::zero ())
3428 e
->dest
->aux
= (void *)(size_t) 1;
3429 worklist
.safe_push (e
->dest
);
3434 FOR_ALL_BB_FN (bb
, cfun
)
3438 if (!(bb
->count
== profile_count::zero ())
3439 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3441 "Basic block %i is marked unlikely by forward prop\n",
3443 bb
->count
= profile_count::zero ();
3445 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3446 e
->count
= profile_count::zero ();
3452 auto_vec
<int, 64> nsuccs
;
3453 nsuccs
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
3454 FOR_ALL_BB_FN (bb
, cfun
)
3455 if (!(bb
->count
== profile_count::zero ())
3456 && bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3458 nsuccs
[bb
->index
] = 0;
3459 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3460 if (!(e
->count
== profile_count::zero ()))
3461 nsuccs
[bb
->index
]++;
3462 if (!nsuccs
[bb
->index
])
3463 worklist
.safe_push (bb
);
3465 while (worklist
.length () > 0)
3467 bb
= worklist
.pop ();
3468 if (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
3471 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
);
3472 !gsi_end_p (gsi
); gsi_next (&gsi
))
3473 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
))
3474 /* stmt_can_terminate_bb_p special cases noreturns because it
3475 assumes that fake edges are created. We want to know that
3476 noreturn alone does not imply BB to be unlikely. */
3477 || (is_gimple_call (gsi_stmt (gsi
))
3478 && (gimple_call_flags (gsi_stmt (gsi
)) & ECF_NORETURN
)))
3486 if (!(bb
->count
== profile_count::zero ())
3487 && (dump_file
&& (dump_flags
& TDF_DETAILS
)))
3489 "Basic block %i is marked unlikely by backward prop\n",
3491 bb
->count
= profile_count::zero ();
3493 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
3494 if (!(e
->count
== profile_count::zero ()))
3496 e
->count
= profile_count::zero ();
3497 if (!(e
->src
->count
== profile_count::zero ()))
3499 nsuccs
[e
->src
->index
]--;
3500 if (!nsuccs
[e
->src
->index
])
3501 worklist
.safe_push (e
->src
);
3507 /* Estimate and propagate basic block frequencies using the given branch
3508 probabilities. If FORCE is true, the frequencies are used to estimate
3509 the counts even when there are already non-zero profile counts. */
3512 estimate_bb_frequencies (bool force
)
3517 determine_unlikely_bbs ();
3519 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
3520 || !counts_to_freqs ())
3522 static int real_values_initialized
= 0;
3524 if (!real_values_initialized
)
3526 real_values_initialized
= 1;
3527 real_br_prob_base
= REG_BR_PROB_BASE
;
3528 real_bb_freq_max
= BB_FREQ_MAX
;
3529 real_one_half
= sreal (1, -1);
3530 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3531 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3534 mark_dfs_back_edges ();
3536 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3539 /* Set up block info for each basic block. */
3540 alloc_aux_for_blocks (sizeof (block_info
));
3541 alloc_aux_for_edges (sizeof (edge_prob_info
));
3542 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3547 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3549 EDGE_INFO (e
)->back_edge_prob
= e
->probability
;
3550 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3554 /* First compute frequencies locally for each loop from innermost
3555 to outermost to examine frequencies for back edges. */
3559 FOR_EACH_BB_FN (bb
, cfun
)
3560 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3561 freq_max
= BLOCK_INFO (bb
)->frequency
;
3563 freq_max
= real_bb_freq_max
/ freq_max
;
3564 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3566 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3567 bb
->frequency
= tmp
.to_int ();
3570 free_aux_for_blocks ();
3571 free_aux_for_edges ();
3573 compute_function_frequency ();
3576 /* Decide whether function is hot, cold or unlikely executed. */
3578 compute_function_frequency (void)
3581 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3583 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3584 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3585 node
->only_called_at_startup
= true;
3586 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3587 node
->only_called_at_exit
= true;
3589 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3591 int flags
= flags_from_decl_or_type (current_function_decl
);
3592 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
== profile_count::zero ()
3593 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3595 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3596 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3598 node
->frequency
= NODE_FREQUENCY_HOT
;
3599 else if (flags
& ECF_NORETURN
)
3600 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3601 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3602 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3603 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3604 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3605 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3609 /* Only first time try to drop function into unlikely executed.
3610 After inlining the roundoff errors may confuse us.
3611 Ipa-profile pass will drop functions only called from unlikely
3612 functions to unlikely and that is most of what we care about. */
3613 if (!cfun
->after_inlining
)
3614 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3615 FOR_EACH_BB_FN (bb
, cfun
)
3617 if (maybe_hot_bb_p (cfun
, bb
))
3619 node
->frequency
= NODE_FREQUENCY_HOT
;
3622 if (!probably_never_executed_bb_p (cfun
, bb
))
3623 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3627 /* Build PREDICT_EXPR. */
3629 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3631 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3632 build_int_cst (integer_type_node
, predictor
));
3633 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3638 predictor_name (enum br_predictor predictor
)
3640 return predictor_info
[predictor
].name
;
3643 /* Predict branch probabilities and estimate profile of the tree CFG. */
3647 const pass_data pass_data_profile
=
3649 GIMPLE_PASS
, /* type */
3650 "profile_estimate", /* name */
3651 OPTGROUP_NONE
, /* optinfo_flags */
3652 TV_BRANCH_PROB
, /* tv_id */
3653 PROP_cfg
, /* properties_required */
3654 0, /* properties_provided */
3655 0, /* properties_destroyed */
3656 0, /* todo_flags_start */
3657 0, /* todo_flags_finish */
3660 class pass_profile
: public gimple_opt_pass
3663 pass_profile (gcc::context
*ctxt
)
3664 : gimple_opt_pass (pass_data_profile
, ctxt
)
3667 /* opt_pass methods: */
3668 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3669 virtual unsigned int execute (function
*);
3671 }; // class pass_profile
3674 pass_profile::execute (function
*fun
)
3678 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3681 loop_optimizer_init (LOOPS_NORMAL
);
3682 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3683 flow_loops_dump (dump_file
, NULL
, 0);
3685 mark_irreducible_loops ();
3687 nb_loops
= number_of_loops (fun
);
3691 tree_estimate_probability (false);
3696 loop_optimizer_finalize ();
3697 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3698 gimple_dump_cfg (dump_file
, dump_flags
);
3699 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3700 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3701 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3704 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3705 if (loop
->header
->frequency
)
3706 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
3708 (int)expected_loop_iterations_unbounded (loop
));
3716 make_pass_profile (gcc::context
*ctxt
)
3718 return new pass_profile (ctxt
);
3723 const pass_data pass_data_strip_predict_hints
=
3725 GIMPLE_PASS
, /* type */
3726 "*strip_predict_hints", /* name */
3727 OPTGROUP_NONE
, /* optinfo_flags */
3728 TV_BRANCH_PROB
, /* tv_id */
3729 PROP_cfg
, /* properties_required */
3730 0, /* properties_provided */
3731 0, /* properties_destroyed */
3732 0, /* todo_flags_start */
3733 0, /* todo_flags_finish */
3736 class pass_strip_predict_hints
: public gimple_opt_pass
3739 pass_strip_predict_hints (gcc::context
*ctxt
)
3740 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3743 /* opt_pass methods: */
3744 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3745 virtual unsigned int execute (function
*);
3747 }; // class pass_strip_predict_hints
3749 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3750 we no longer need. */
3752 pass_strip_predict_hints::execute (function
*fun
)
3757 bool changed
= false;
3759 FOR_EACH_BB_FN (bb
, fun
)
3761 gimple_stmt_iterator bi
;
3762 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3764 gimple
*stmt
= gsi_stmt (bi
);
3766 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3768 gsi_remove (&bi
, true);
3772 else if (is_gimple_call (stmt
))
3774 tree fndecl
= gimple_call_fndecl (stmt
);
3777 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3778 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3779 && gimple_call_num_args (stmt
) == 2)
3780 || (gimple_call_internal_p (stmt
)
3781 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3783 var
= gimple_call_lhs (stmt
);
3788 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3789 gsi_replace (&bi
, ass_stmt
, true);
3793 gsi_remove (&bi
, true);
3801 return changed
? TODO_cleanup_cfg
: 0;
3807 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3809 return new pass_strip_predict_hints (ctxt
);
3812 /* Rebuild function frequencies. Passes are in general expected to
3813 maintain profile by hand, however in some cases this is not possible:
3814 for example when inlining several functions with loops freuqencies might run
3815 out of scale and thus needs to be recomputed. */
3818 rebuild_frequencies (void)
3820 timevar_push (TV_REBUILD_FREQUENCIES
);
3822 /* When the max bb count in the function is small, there is a higher
3823 chance that there were truncation errors in the integer scaling
3824 of counts by inlining and other optimizations. This could lead
3825 to incorrect classification of code as being cold when it isn't.
3826 In that case, force the estimation of bb counts/frequencies from the
3827 branch probabilities, rather than computing frequencies from counts,
3828 which may also lead to frequencies incorrectly reduced to 0. There
3829 is less precision in the probabilities, so we only do this for small
3831 profile_count count_max
= profile_count::zero ();
3833 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3834 if (bb
->count
> count_max
)
3835 count_max
= bb
->count
;
3837 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3838 || (!flag_auto_profile
&& profile_status_for_fn (cfun
) == PROFILE_READ
3839 && count_max
< REG_BR_PROB_BASE
/ 10))
3841 loop_optimizer_init (0);
3842 add_noreturn_fake_exit_edges ();
3843 mark_irreducible_loops ();
3844 connect_infinite_loops_to_exit ();
3845 estimate_bb_frequencies (true);
3846 remove_fake_exit_edges ();
3847 loop_optimizer_finalize ();
3849 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3853 timevar_pop (TV_REBUILD_FREQUENCIES
);
3856 /* Perform a dry run of the branch prediction pass and report comparsion of
3857 the predicted and real profile into the dump file. */
3860 report_predictor_hitrates (void)
3864 loop_optimizer_init (LOOPS_NORMAL
);
3865 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3866 flow_loops_dump (dump_file
, NULL
, 0);
3868 mark_irreducible_loops ();
3870 nb_loops
= number_of_loops (cfun
);
3874 tree_estimate_probability (true);
3879 loop_optimizer_finalize ();
3882 /* Force edge E to be cold.
3883 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
3884 keep low probability to represent possible error in a guess. This is used
3885 i.e. in case we predict loop to likely iterate given number of times but
3886 we are not 100% sure.
3888 This function locally updates profile without attempt to keep global
3889 consistency which can not be reached in full generality without full profile
3890 rebuild from probabilities alone. Doing so is not necessarily a good idea
3891 because frequencies and counts may be more realistic then probabilities.
3893 In some cases (such as for elimination of early exits during full loop
3894 unrolling) the caller can ensure that profile will get consistent
3898 force_edge_cold (edge e
, bool impossible
)
3900 profile_count count_sum
= profile_count::zero ();
3904 profile_count old_count
= e
->count
;
3905 int old_probability
= e
->probability
;
3906 int prob_scale
= REG_BR_PROB_BASE
;
3907 bool uninitialized_exit
= false;
3909 /* If edge is already improbably or cold, just return. */
3910 if (e
->probability
<= (impossible
? PROB_VERY_UNLIKELY
: 0)
3911 && (!impossible
|| e
->count
== profile_count::zero ()))
3913 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3916 if (e2
->count
.initialized_p ())
3917 count_sum
+= e2
->count
;
3919 uninitialized_exit
= true;
3920 prob_sum
+= e2
->probability
;
3923 /* If there are other edges out of e->src, redistribute probabilitity
3928 = MIN (e
->probability
, impossible
? 0 : PROB_VERY_UNLIKELY
);
3930 e
->count
= profile_count::zero ();
3931 else if (old_probability
)
3932 e
->count
= e
->count
.apply_scale (e
->probability
, old_probability
);
3934 e
->count
= e
->count
.apply_scale (1, REG_BR_PROB_BASE
);
3936 prob_scale
= RDIV ((REG_BR_PROB_BASE
- e
->probability
) * REG_BR_PROB_BASE
,
3938 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3939 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
3940 "probability to other edges.\n",
3941 e
->src
->index
, e
->dest
->index
,
3942 impossible
? "impossible" : "cold");
3943 profile_count count_sum2
= count_sum
+ old_count
- e
->count
;
3944 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3948 e2
->count
.apply_scale (count_sum2
, count_sum
);
3949 e2
->probability
= RDIV (e2
->probability
* prob_scale
,
3953 /* If all edges out of e->src are unlikely, the basic block itself
3957 e
->probability
= REG_BR_PROB_BASE
;
3958 if (e
->src
->count
== profile_count::zero ())
3960 if (count_sum
== profile_count::zero () && !uninitialized_exit
3964 for (gimple_stmt_iterator gsi
= gsi_start_bb (e
->src
);
3965 !gsi_end_p (gsi
); gsi_next (&gsi
))
3967 if (stmt_can_terminate_bb_p (gsi_stmt (gsi
)))
3975 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3977 "Making bb %i impossible and dropping count to 0.\n",
3979 e
->count
= profile_count::zero ();
3980 e
->src
->count
= profile_count::zero ();
3981 FOR_EACH_EDGE (e2
, ei
, e
->src
->preds
)
3982 force_edge_cold (e2
, impossible
);
3987 /* If we did not adjusting, the source basic block has no likely edeges
3988 leaving other direction. In that case force that bb cold, too.
3989 This in general is difficult task to do, but handle special case when
3990 BB has only one predecestor. This is common case when we are updating
3991 after loop transforms. */
3992 if (!prob_sum
&& count_sum
== profile_count::zero ()
3993 && single_pred_p (e
->src
) && e
->src
->frequency
> (impossible
? 0 : 1))
3995 int old_frequency
= e
->src
->frequency
;
3996 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3997 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
3998 impossible
? "impossible" : "cold");
3999 e
->src
->frequency
= MIN (e
->src
->frequency
, impossible
? 0 : 1);
4001 e
->src
->count
= e
->count
= profile_count::zero ();
4003 e
->src
->count
= e
->count
= e
->count
.apply_scale (e
->src
->frequency
,
4005 force_edge_cold (single_pred_edge (e
->src
), impossible
);
4007 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
4008 && maybe_hot_bb_p (cfun
, e
->src
))
4009 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
4010 impossible
? "impossible" : "cold");
4016 namespace selftest
{
4018 /* Test that value range of predictor values defined in predict.def is
4019 within range (50, 100]. */
4021 struct branch_predictor
4024 unsigned probability
;
4027 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4030 test_prediction_value_range ()
4032 branch_predictor predictors
[] = {
4033 #include "predict.def"
4037 for (unsigned i
= 0; predictors
[i
].name
!= NULL
; i
++)
4039 unsigned p
= 100 * predictors
[i
].probability
/ REG_BR_PROB_BASE
;
4040 ASSERT_TRUE (p
> 50 && p
<= 100);
4044 #undef DEF_PREDICTOR
4046 /* Run all of the selfests within this file. */
4051 test_prediction_value_range ();
4054 } // namespace selftest
4055 #endif /* CHECKING_P. */