1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2016 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"
43 #include "diagnostic-core.h"
44 #include "gimple-predict.h"
45 #include "fold-const.h"
52 #include "gimple-iterator.h"
54 #include "tree-ssa-loop-niter.h"
55 #include "tree-ssa-loop.h"
56 #include "tree-scalar-evolution.h"
57 #include "ipa-utils.h"
58 #include "gimple-pretty-print.h"
60 /* Enum with reasons why a predictor is ignored. */
66 REASON_SINGLE_EDGE_DUPLICATE
,
67 REASON_EDGE_PAIR_DUPLICATE
70 /* String messages for the aforementioned enum. */
72 static const char *reason_messages
[] = {"", " (ignored)",
73 " (single edge duplicate)", " (edge pair duplicate)"};
75 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
76 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
77 static sreal real_almost_one
, real_br_prob_base
,
78 real_inv_br_prob_base
, real_one_half
, real_bb_freq_max
;
80 static void combine_predictions_for_insn (rtx_insn
*, basic_block
);
81 static void dump_prediction (FILE *, enum br_predictor
, int, basic_block
,
82 enum predictor_reason
, edge
);
83 static void predict_paths_leading_to (basic_block
, enum br_predictor
,
85 struct loop
*in_loop
= NULL
);
86 static void predict_paths_leading_to_edge (edge
, enum br_predictor
,
88 struct loop
*in_loop
= NULL
);
89 static bool can_predict_insn_p (const rtx_insn
*);
91 /* Information we hold about each branch predictor.
92 Filled using information from predict.def. */
96 const char *const name
; /* Name used in the debugging dumps. */
97 const int hitrate
; /* Expected hitrate used by
98 predict_insn_def call. */
102 /* Use given predictor without Dempster-Shaffer theory if it matches
103 using first_match heuristics. */
104 #define PRED_FLAG_FIRST_MATCH 1
106 /* Recompute hitrate in percent to our representation. */
108 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
110 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
111 static const struct predictor_info predictor_info
[]= {
112 #include "predict.def"
114 /* Upper bound on predictors. */
119 /* Return TRUE if frequency FREQ is considered to be hot. */
122 maybe_hot_frequency_p (struct function
*fun
, int freq
)
124 struct cgraph_node
*node
= cgraph_node::get (fun
->decl
);
126 || !opt_for_fn (fun
->decl
, flag_branch_probabilities
))
128 if (node
->frequency
== NODE_FREQUENCY_UNLIKELY_EXECUTED
)
130 if (node
->frequency
== NODE_FREQUENCY_HOT
)
133 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
135 if (node
->frequency
== NODE_FREQUENCY_EXECUTED_ONCE
136 && freq
< (ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
* 2 / 3))
138 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
) == 0)
140 if (freq
* PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION
)
141 < ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
146 static gcov_type min_count
= -1;
148 /* Determine the threshold for hot BB counts. */
151 get_hot_bb_threshold ()
153 gcov_working_set_t
*ws
;
156 ws
= find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE
));
158 min_count
= ws
->min_counter
;
163 /* Set the threshold for hot BB counts. */
166 set_hot_bb_threshold (gcov_type min
)
171 /* Return TRUE if frequency FREQ is considered to be hot. */
174 maybe_hot_count_p (struct function
*fun
, gcov_type count
)
176 if (fun
&& profile_status_for_fn (fun
) != PROFILE_READ
)
178 /* Code executed at most once is not hot. */
179 if (profile_info
->runs
>= count
)
181 return (count
>= get_hot_bb_threshold ());
184 /* Return true in case BB can be CPU intensive and should be optimized
185 for maximal performance. */
188 maybe_hot_bb_p (struct function
*fun
, const_basic_block bb
)
190 gcc_checking_assert (fun
);
191 if (profile_status_for_fn (fun
) == PROFILE_READ
)
192 return maybe_hot_count_p (fun
, bb
->count
);
193 return maybe_hot_frequency_p (fun
, bb
->frequency
);
196 /* Return true in case BB can be CPU intensive and should be optimized
197 for maximal performance. */
200 maybe_hot_edge_p (edge e
)
202 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
203 return maybe_hot_count_p (cfun
, e
->count
);
204 return maybe_hot_frequency_p (cfun
, EDGE_FREQUENCY (e
));
207 /* Return true if profile COUNT and FREQUENCY, or function FUN static
208 node frequency reflects never being executed. */
211 probably_never_executed (struct function
*fun
,
212 gcov_type count
, int frequency
)
214 gcc_checking_assert (fun
);
215 if (profile_status_for_fn (fun
) == PROFILE_READ
)
217 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
218 if (count
* unlikely_count_fraction
>= profile_info
->runs
)
222 if (!ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
)
224 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
)
226 gcov_type computed_count
;
227 /* Check for possibility of overflow, in which case entry bb count
228 is large enough to do the division first without losing much
230 if (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
< REG_BR_PROB_BASE
*
233 gcov_type scaled_count
234 = frequency
* ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
*
235 unlikely_count_fraction
;
236 computed_count
= RDIV (scaled_count
,
237 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
241 computed_count
= RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun
)->count
,
242 ENTRY_BLOCK_PTR_FOR_FN (fun
)->frequency
);
243 computed_count
*= frequency
* unlikely_count_fraction
;
245 if (computed_count
>= profile_info
->runs
)
250 if ((!profile_info
|| !(opt_for_fn (fun
->decl
, flag_branch_probabilities
)))
251 && (cgraph_node::get (fun
->decl
)->frequency
252 == NODE_FREQUENCY_UNLIKELY_EXECUTED
))
258 /* Return true in case BB is probably never executed. */
261 probably_never_executed_bb_p (struct function
*fun
, const_basic_block bb
)
263 return probably_never_executed (fun
, bb
->count
, bb
->frequency
);
267 /* Return true in case edge E is probably never executed. */
270 probably_never_executed_edge_p (struct function
*fun
, edge e
)
272 return probably_never_executed (fun
, e
->count
, EDGE_FREQUENCY (e
));
275 /* Return true when current function should always be optimized for size. */
278 optimize_function_for_size_p (struct function
*fun
)
280 if (!fun
|| !fun
->decl
)
281 return optimize_size
;
282 cgraph_node
*n
= cgraph_node::get (fun
->decl
);
283 return n
&& n
->optimize_for_size_p ();
286 /* Return true when current function should always be optimized for speed. */
289 optimize_function_for_speed_p (struct function
*fun
)
291 return !optimize_function_for_size_p (fun
);
294 /* Return the optimization type that should be used for the function FUN. */
297 function_optimization_type (struct function
*fun
)
299 return (optimize_function_for_speed_p (fun
)
301 : OPTIMIZE_FOR_SIZE
);
304 /* Return TRUE when BB should be optimized for size. */
307 optimize_bb_for_size_p (const_basic_block bb
)
309 return (optimize_function_for_size_p (cfun
)
310 || (bb
&& !maybe_hot_bb_p (cfun
, bb
)));
313 /* Return TRUE when BB should be optimized for speed. */
316 optimize_bb_for_speed_p (const_basic_block bb
)
318 return !optimize_bb_for_size_p (bb
);
321 /* Return the optimization type that should be used for block BB. */
324 bb_optimization_type (const_basic_block bb
)
326 return (optimize_bb_for_speed_p (bb
)
328 : OPTIMIZE_FOR_SIZE
);
331 /* Return TRUE when BB should be optimized for size. */
334 optimize_edge_for_size_p (edge e
)
336 return optimize_function_for_size_p (cfun
) || !maybe_hot_edge_p (e
);
339 /* Return TRUE when BB should be optimized for speed. */
342 optimize_edge_for_speed_p (edge e
)
344 return !optimize_edge_for_size_p (e
);
347 /* Return TRUE when BB should be optimized for size. */
350 optimize_insn_for_size_p (void)
352 return optimize_function_for_size_p (cfun
) || !crtl
->maybe_hot_insn_p
;
355 /* Return TRUE when BB should be optimized for speed. */
358 optimize_insn_for_speed_p (void)
360 return !optimize_insn_for_size_p ();
363 /* Return TRUE when LOOP should be optimized for size. */
366 optimize_loop_for_size_p (struct loop
*loop
)
368 return optimize_bb_for_size_p (loop
->header
);
371 /* Return TRUE when LOOP should be optimized for speed. */
374 optimize_loop_for_speed_p (struct loop
*loop
)
376 return optimize_bb_for_speed_p (loop
->header
);
379 /* Return TRUE when LOOP nest should be optimized for speed. */
382 optimize_loop_nest_for_speed_p (struct loop
*loop
)
384 struct loop
*l
= loop
;
385 if (optimize_loop_for_speed_p (loop
))
388 while (l
&& l
!= loop
)
390 if (optimize_loop_for_speed_p (l
))
398 while (l
!= loop
&& !l
->next
)
407 /* Return TRUE when LOOP nest should be optimized for size. */
410 optimize_loop_nest_for_size_p (struct loop
*loop
)
412 return !optimize_loop_nest_for_speed_p (loop
);
415 /* Return true when edge E is likely to be well predictable by branch
419 predictable_edge_p (edge e
)
421 if (profile_status_for_fn (cfun
) == PROFILE_ABSENT
)
424 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100)
425 || (REG_BR_PROB_BASE
- e
->probability
426 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME
) * REG_BR_PROB_BASE
/ 100))
432 /* Set RTL expansion for BB profile. */
435 rtl_profile_for_bb (basic_block bb
)
437 crtl
->maybe_hot_insn_p
= maybe_hot_bb_p (cfun
, bb
);
440 /* Set RTL expansion for edge profile. */
443 rtl_profile_for_edge (edge e
)
445 crtl
->maybe_hot_insn_p
= maybe_hot_edge_p (e
);
448 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
450 default_rtl_profile (void)
452 crtl
->maybe_hot_insn_p
= true;
455 /* Return true if the one of outgoing edges is already predicted by
459 rtl_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
462 if (!INSN_P (BB_END (bb
)))
464 for (note
= REG_NOTES (BB_END (bb
)); note
; note
= XEXP (note
, 1))
465 if (REG_NOTE_KIND (note
) == REG_BR_PRED
466 && INTVAL (XEXP (XEXP (note
, 0), 0)) == (int)predictor
)
471 /* Structure representing predictions in tree level. */
473 struct edge_prediction
{
474 struct edge_prediction
*ep_next
;
476 enum br_predictor ep_predictor
;
480 /* This map contains for a basic block the list of predictions for the
483 static hash_map
<const_basic_block
, edge_prediction
*> *bb_predictions
;
485 /* Return true if the one of outgoing edges is already predicted by
489 gimple_predicted_by_p (const_basic_block bb
, enum br_predictor predictor
)
491 struct edge_prediction
*i
;
492 edge_prediction
**preds
= bb_predictions
->get (bb
);
497 for (i
= *preds
; i
; i
= i
->ep_next
)
498 if (i
->ep_predictor
== predictor
)
503 /* Return true if the one of outgoing edges is already predicted by
504 PREDICTOR for edge E predicted as TAKEN. */
507 edge_predicted_by_p (edge e
, enum br_predictor predictor
, bool taken
)
509 struct edge_prediction
*i
;
510 basic_block bb
= e
->src
;
511 edge_prediction
**preds
= bb_predictions
->get (bb
);
515 int probability
= predictor_info
[(int) predictor
].hitrate
;
518 probability
= REG_BR_PROB_BASE
- probability
;
520 for (i
= *preds
; i
; i
= i
->ep_next
)
521 if (i
->ep_predictor
== predictor
523 && i
->ep_probability
== probability
)
528 /* Return true when the probability of edge is reliable.
530 The profile guessing code is good at predicting branch outcome (ie.
531 taken/not taken), that is predicted right slightly over 75% of time.
532 It is however notoriously poor on predicting the probability itself.
533 In general the profile appear a lot flatter (with probabilities closer
534 to 50%) than the reality so it is bad idea to use it to drive optimization
535 such as those disabling dynamic branch prediction for well predictable
538 There are two exceptions - edges leading to noreturn edges and edges
539 predicted by number of iterations heuristics are predicted well. This macro
540 should be able to distinguish those, but at the moment it simply check for
541 noreturn heuristic that is only one giving probability over 99% or bellow
542 1%. In future we might want to propagate reliability information across the
543 CFG if we find this information useful on multiple places. */
545 probability_reliable_p (int prob
)
547 return (profile_status_for_fn (cfun
) == PROFILE_READ
548 || (profile_status_for_fn (cfun
) == PROFILE_GUESSED
549 && (prob
<= HITRATE (1) || prob
>= HITRATE (99))));
552 /* Same predicate as above, working on edges. */
554 edge_probability_reliable_p (const_edge e
)
556 return probability_reliable_p (e
->probability
);
559 /* Same predicate as edge_probability_reliable_p, working on notes. */
561 br_prob_note_reliable_p (const_rtx note
)
563 gcc_assert (REG_NOTE_KIND (note
) == REG_BR_PROB
);
564 return probability_reliable_p (XINT (note
, 0));
568 predict_insn (rtx_insn
*insn
, enum br_predictor predictor
, int probability
)
570 gcc_assert (any_condjump_p (insn
));
571 if (!flag_guess_branch_prob
)
574 add_reg_note (insn
, REG_BR_PRED
,
575 gen_rtx_CONCAT (VOIDmode
,
576 GEN_INT ((int) predictor
),
577 GEN_INT ((int) probability
)));
580 /* Predict insn by given predictor. */
583 predict_insn_def (rtx_insn
*insn
, enum br_predictor predictor
,
584 enum prediction taken
)
586 int probability
= predictor_info
[(int) predictor
].hitrate
;
589 probability
= REG_BR_PROB_BASE
- probability
;
591 predict_insn (insn
, predictor
, probability
);
594 /* Predict edge E with given probability if possible. */
597 rtl_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
600 last_insn
= BB_END (e
->src
);
602 /* We can store the branch prediction information only about
603 conditional jumps. */
604 if (!any_condjump_p (last_insn
))
607 /* We always store probability of branching. */
608 if (e
->flags
& EDGE_FALLTHRU
)
609 probability
= REG_BR_PROB_BASE
- probability
;
611 predict_insn (last_insn
, predictor
, probability
);
614 /* Predict edge E with the given PROBABILITY. */
616 gimple_predict_edge (edge e
, enum br_predictor predictor
, int probability
)
618 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
619 && EDGE_COUNT (e
->src
->succs
) > 1
620 && flag_guess_branch_prob
623 struct edge_prediction
*i
= XNEW (struct edge_prediction
);
624 edge_prediction
*&preds
= bb_predictions
->get_or_insert (e
->src
);
628 i
->ep_probability
= probability
;
629 i
->ep_predictor
= predictor
;
634 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
635 to the filter function. */
638 filter_predictions (edge_prediction
**preds
,
639 bool (*filter
) (edge_prediction
*, void *), void *data
)
646 struct edge_prediction
**prediction
= preds
;
647 struct edge_prediction
*next
;
651 if ((*filter
) (*prediction
, data
))
652 prediction
= &((*prediction
)->ep_next
);
655 next
= (*prediction
)->ep_next
;
663 /* Filter function predicate that returns true for a edge predicate P
664 if its edge is equal to DATA. */
667 equal_edge_p (edge_prediction
*p
, void *data
)
669 return p
->ep_edge
== (edge
)data
;
672 /* Remove all predictions on given basic block that are attached
675 remove_predictions_associated_with_edge (edge e
)
680 edge_prediction
**preds
= bb_predictions
->get (e
->src
);
681 filter_predictions (preds
, equal_edge_p
, e
);
684 /* Clears the list of predictions stored for BB. */
687 clear_bb_predictions (basic_block bb
)
689 edge_prediction
**preds
= bb_predictions
->get (bb
);
690 struct edge_prediction
*pred
, *next
;
695 for (pred
= *preds
; pred
; pred
= next
)
697 next
= pred
->ep_next
;
703 /* Return true when we can store prediction on insn INSN.
704 At the moment we represent predictions only on conditional
705 jumps, not at computed jump or other complicated cases. */
707 can_predict_insn_p (const rtx_insn
*insn
)
709 return (JUMP_P (insn
)
710 && any_condjump_p (insn
)
711 && EDGE_COUNT (BLOCK_FOR_INSN (insn
)->succs
) >= 2);
714 /* Predict edge E by given predictor if possible. */
717 predict_edge_def (edge e
, enum br_predictor predictor
,
718 enum prediction taken
)
720 int probability
= predictor_info
[(int) predictor
].hitrate
;
723 probability
= REG_BR_PROB_BASE
- probability
;
725 predict_edge (e
, predictor
, probability
);
728 /* Invert all branch predictions or probability notes in the INSN. This needs
729 to be done each time we invert the condition used by the jump. */
732 invert_br_probabilities (rtx insn
)
736 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
737 if (REG_NOTE_KIND (note
) == REG_BR_PROB
)
738 XINT (note
, 0) = REG_BR_PROB_BASE
- XINT (note
, 0);
739 else if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
740 XEXP (XEXP (note
, 0), 1)
741 = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (XEXP (note
, 0), 1)));
744 /* Dump information about the branch prediction to the output file. */
747 dump_prediction (FILE *file
, enum br_predictor predictor
, int probability
,
748 basic_block bb
, enum predictor_reason reason
= REASON_NONE
,
758 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
759 if (! (e
->flags
& EDGE_FALLTHRU
))
762 char edge_info_str
[128];
764 sprintf (edge_info_str
, " of edge %d->%d", ep_edge
->src
->index
,
765 ep_edge
->dest
->index
);
767 edge_info_str
[0] = '\0';
769 fprintf (file
, " %s heuristics%s%s: %.1f%%",
770 predictor_info
[predictor
].name
,
771 edge_info_str
, reason_messages
[reason
],
772 probability
* 100.0 / REG_BR_PROB_BASE
);
776 fprintf (file
, " exec %" PRId64
, bb
->count
);
779 fprintf (file
, " hit %" PRId64
, e
->count
);
780 fprintf (file
, " (%.1f%%)", e
->count
* 100.0 / bb
->count
);
784 fprintf (file
, "\n");
787 /* We can not predict the probabilities of outgoing edges of bb. Set them
788 evenly and hope for the best. */
790 set_even_probabilities (basic_block bb
)
796 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
797 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
799 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
800 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
801 e
->probability
= (REG_BR_PROB_BASE
+ nedges
/ 2) / nedges
;
806 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
807 note if not already present. Remove now useless REG_BR_PRED notes. */
810 combine_predictions_for_insn (rtx_insn
*insn
, basic_block bb
)
815 int best_probability
= PROB_EVEN
;
816 enum br_predictor best_predictor
= END_PREDICTORS
;
817 int combined_probability
= REG_BR_PROB_BASE
/ 2;
819 bool first_match
= false;
822 if (!can_predict_insn_p (insn
))
824 set_even_probabilities (bb
);
828 prob_note
= find_reg_note (insn
, REG_BR_PROB
, 0);
829 pnote
= ®_NOTES (insn
);
831 fprintf (dump_file
, "Predictions for insn %i bb %i\n", INSN_UID (insn
),
834 /* We implement "first match" heuristics and use probability guessed
835 by predictor with smallest index. */
836 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
837 if (REG_NOTE_KIND (note
) == REG_BR_PRED
)
839 enum br_predictor predictor
= ((enum br_predictor
)
840 INTVAL (XEXP (XEXP (note
, 0), 0)));
841 int probability
= INTVAL (XEXP (XEXP (note
, 0), 1));
844 if (best_predictor
> predictor
845 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
846 best_probability
= probability
, best_predictor
= predictor
;
848 d
= (combined_probability
* probability
849 + (REG_BR_PROB_BASE
- combined_probability
)
850 * (REG_BR_PROB_BASE
- probability
));
852 /* Use FP math to avoid overflows of 32bit integers. */
854 /* If one probability is 0% and one 100%, avoid division by zero. */
855 combined_probability
= REG_BR_PROB_BASE
/ 2;
857 combined_probability
= (((double) combined_probability
) * probability
858 * REG_BR_PROB_BASE
/ d
+ 0.5);
861 /* Decide which heuristic to use. In case we didn't match anything,
862 use no_prediction heuristic, in case we did match, use either
863 first match or Dempster-Shaffer theory depending on the flags. */
865 if (best_predictor
!= END_PREDICTORS
)
869 dump_prediction (dump_file
, PRED_NO_PREDICTION
,
870 combined_probability
, bb
);
874 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
,
875 bb
, !first_match
? REASON_NONE
: REASON_IGNORED
);
877 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
,
878 bb
, first_match
? REASON_NONE
: REASON_IGNORED
);
882 combined_probability
= best_probability
;
883 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
887 if (REG_NOTE_KIND (*pnote
) == REG_BR_PRED
)
889 enum br_predictor predictor
= ((enum br_predictor
)
890 INTVAL (XEXP (XEXP (*pnote
, 0), 0)));
891 int probability
= INTVAL (XEXP (XEXP (*pnote
, 0), 1));
893 dump_prediction (dump_file
, predictor
, probability
, bb
,
894 (!first_match
|| best_predictor
== predictor
)
895 ? REASON_NONE
: REASON_IGNORED
);
896 *pnote
= XEXP (*pnote
, 1);
899 pnote
= &XEXP (*pnote
, 1);
904 add_int_reg_note (insn
, REG_BR_PROB
, combined_probability
);
906 /* Save the prediction into CFG in case we are seeing non-degenerated
908 if (!single_succ_p (bb
))
910 BRANCH_EDGE (bb
)->probability
= combined_probability
;
911 FALLTHRU_EDGE (bb
)->probability
912 = REG_BR_PROB_BASE
- combined_probability
;
915 else if (!single_succ_p (bb
))
917 int prob
= XINT (prob_note
, 0);
919 BRANCH_EDGE (bb
)->probability
= prob
;
920 FALLTHRU_EDGE (bb
)->probability
= REG_BR_PROB_BASE
- prob
;
923 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
926 /* Edge prediction hash traits. */
928 struct predictor_hash
: pointer_hash
<edge_prediction
>
931 static inline hashval_t
hash (const edge_prediction
*);
932 static inline bool equal (const edge_prediction
*, const edge_prediction
*);
935 /* Calculate hash value of an edge prediction P based on predictor and
936 normalized probability. */
939 predictor_hash::hash (const edge_prediction
*p
)
941 inchash::hash hstate
;
942 hstate
.add_int (p
->ep_predictor
);
944 int prob
= p
->ep_probability
;
945 if (prob
> REG_BR_PROB_BASE
/ 2)
946 prob
= REG_BR_PROB_BASE
- prob
;
948 hstate
.add_int (prob
);
950 return hstate
.end ();
953 /* Return true whether edge predictions P1 and P2 use the same predictor and
954 have equal (or opposed probability). */
957 predictor_hash::equal (const edge_prediction
*p1
, const edge_prediction
*p2
)
959 return (p1
->ep_predictor
== p2
->ep_predictor
960 && (p1
->ep_probability
== p2
->ep_probability
961 || p1
->ep_probability
== REG_BR_PROB_BASE
- p2
->ep_probability
));
964 struct predictor_hash_traits
: predictor_hash
,
965 typed_noop_remove
<edge_prediction
*> {};
967 /* Return true if edge prediction P is not in DATA hash set. */
970 not_removed_prediction_p (edge_prediction
*p
, void *data
)
972 hash_set
<edge_prediction
*> *remove
= (hash_set
<edge_prediction
*> *) data
;
973 return !remove
->contains (p
);
976 /* Prune predictions for a basic block BB. Currently we do following
979 1) remove duplicate prediction that is guessed with the same probability
980 (different than 1/2) to both edge
981 2) remove duplicates for a prediction that belongs with the same probability
987 prune_predictions_for_bb (basic_block bb
)
989 edge_prediction
**preds
= bb_predictions
->get (bb
);
993 hash_table
<predictor_hash_traits
> s (13);
994 hash_set
<edge_prediction
*> remove
;
996 /* Step 1: identify predictors that should be removed. */
997 for (edge_prediction
*pred
= *preds
; pred
; pred
= pred
->ep_next
)
999 edge_prediction
*existing
= s
.find (pred
);
1002 if (pred
->ep_edge
== existing
->ep_edge
1003 && pred
->ep_probability
== existing
->ep_probability
)
1005 /* Remove a duplicate predictor. */
1006 dump_prediction (dump_file
, pred
->ep_predictor
,
1007 pred
->ep_probability
, bb
,
1008 REASON_SINGLE_EDGE_DUPLICATE
, pred
->ep_edge
);
1012 else if (pred
->ep_edge
!= existing
->ep_edge
1013 && pred
->ep_probability
== existing
->ep_probability
1014 && pred
->ep_probability
!= REG_BR_PROB_BASE
/ 2)
1016 /* Remove both predictors as they predict the same
1018 dump_prediction (dump_file
, existing
->ep_predictor
,
1019 pred
->ep_probability
, bb
,
1020 REASON_EDGE_PAIR_DUPLICATE
,
1022 dump_prediction (dump_file
, pred
->ep_predictor
,
1023 pred
->ep_probability
, bb
,
1024 REASON_EDGE_PAIR_DUPLICATE
,
1027 remove
.add (existing
);
1032 edge_prediction
**slot2
= s
.find_slot (pred
, INSERT
);
1036 /* Step 2: Remove predictors. */
1037 filter_predictions (preds
, not_removed_prediction_p
, &remove
);
1041 /* Combine predictions into single probability and store them into CFG.
1042 Remove now useless prediction entries.
1043 If DRY_RUN is set, only produce dumps and do not modify profile. */
1046 combine_predictions_for_bb (basic_block bb
, bool dry_run
)
1048 int best_probability
= PROB_EVEN
;
1049 enum br_predictor best_predictor
= END_PREDICTORS
;
1050 int combined_probability
= REG_BR_PROB_BASE
/ 2;
1052 bool first_match
= false;
1054 struct edge_prediction
*pred
;
1056 edge e
, first
= NULL
, second
= NULL
;
1059 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1060 if (!(e
->flags
& (EDGE_EH
| EDGE_FAKE
)))
1063 if (first
&& !second
)
1069 /* When there is no successor or only one choice, prediction is easy.
1071 We are lazy for now and predict only basic blocks with two outgoing
1072 edges. It is possible to predict generic case too, but we have to
1073 ignore first match heuristics and do more involved combining. Implement
1077 if (!bb
->count
&& !dry_run
)
1078 set_even_probabilities (bb
);
1079 clear_bb_predictions (bb
);
1081 fprintf (dump_file
, "%i edges in bb %i predicted to even probabilities\n",
1087 fprintf (dump_file
, "Predictions for bb %i\n", bb
->index
);
1089 prune_predictions_for_bb (bb
);
1091 edge_prediction
**preds
= bb_predictions
->get (bb
);
1095 /* We implement "first match" heuristics and use probability guessed
1096 by predictor with smallest index. */
1097 for (pred
= *preds
; pred
; pred
= pred
->ep_next
)
1099 enum br_predictor predictor
= pred
->ep_predictor
;
1100 int probability
= pred
->ep_probability
;
1102 if (pred
->ep_edge
!= first
)
1103 probability
= REG_BR_PROB_BASE
- probability
;
1106 /* First match heuristics would be widly confused if we predicted
1108 if (best_predictor
> predictor
1109 && predictor_info
[predictor
].flags
& PRED_FLAG_FIRST_MATCH
)
1111 struct edge_prediction
*pred2
;
1112 int prob
= probability
;
1114 for (pred2
= (struct edge_prediction
*) *preds
;
1115 pred2
; pred2
= pred2
->ep_next
)
1116 if (pred2
!= pred
&& pred2
->ep_predictor
== pred
->ep_predictor
)
1118 int probability2
= pred2
->ep_probability
;
1120 if (pred2
->ep_edge
!= first
)
1121 probability2
= REG_BR_PROB_BASE
- probability2
;
1123 if ((probability
< REG_BR_PROB_BASE
/ 2) !=
1124 (probability2
< REG_BR_PROB_BASE
/ 2))
1127 /* If the same predictor later gave better result, go for it! */
1128 if ((probability
>= REG_BR_PROB_BASE
/ 2 && (probability2
> probability
))
1129 || (probability
<= REG_BR_PROB_BASE
/ 2 && (probability2
< probability
)))
1130 prob
= probability2
;
1133 best_probability
= prob
, best_predictor
= predictor
;
1136 d
= (combined_probability
* probability
1137 + (REG_BR_PROB_BASE
- combined_probability
)
1138 * (REG_BR_PROB_BASE
- probability
));
1140 /* Use FP math to avoid overflows of 32bit integers. */
1142 /* If one probability is 0% and one 100%, avoid division by zero. */
1143 combined_probability
= REG_BR_PROB_BASE
/ 2;
1145 combined_probability
= (((double) combined_probability
)
1147 * REG_BR_PROB_BASE
/ d
+ 0.5);
1151 /* Decide which heuristic to use. In case we didn't match anything,
1152 use no_prediction heuristic, in case we did match, use either
1153 first match or Dempster-Shaffer theory depending on the flags. */
1155 if (best_predictor
!= END_PREDICTORS
)
1159 dump_prediction (dump_file
, PRED_NO_PREDICTION
, combined_probability
, bb
);
1163 dump_prediction (dump_file
, PRED_DS_THEORY
, combined_probability
, bb
,
1164 !first_match
? REASON_NONE
: REASON_IGNORED
);
1166 dump_prediction (dump_file
, PRED_FIRST_MATCH
, best_probability
, bb
,
1167 first_match
? REASON_NONE
: REASON_IGNORED
);
1171 combined_probability
= best_probability
;
1172 dump_prediction (dump_file
, PRED_COMBINED
, combined_probability
, bb
);
1176 for (pred
= (struct edge_prediction
*) *preds
; pred
; pred
= pred
->ep_next
)
1178 enum br_predictor predictor
= pred
->ep_predictor
;
1179 int probability
= pred
->ep_probability
;
1181 dump_prediction (dump_file
, predictor
, probability
, bb
,
1182 (!first_match
|| best_predictor
== predictor
)
1183 ? REASON_NONE
: REASON_IGNORED
, pred
->ep_edge
);
1186 clear_bb_predictions (bb
);
1188 if (!bb
->count
&& !dry_run
)
1190 first
->probability
= combined_probability
;
1191 second
->probability
= REG_BR_PROB_BASE
- combined_probability
;
1195 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1196 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1198 T1 and T2 should be one of the following cases:
1199 1. T1 is SSA_NAME, T2 is NULL
1200 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1201 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1204 strips_small_constant (tree t1
, tree t2
)
1211 else if (TREE_CODE (t1
) == SSA_NAME
)
1213 else if (tree_fits_shwi_p (t1
))
1214 value
= tree_to_shwi (t1
);
1220 else if (tree_fits_shwi_p (t2
))
1221 value
= tree_to_shwi (t2
);
1222 else if (TREE_CODE (t2
) == SSA_NAME
)
1230 if (value
<= 4 && value
>= -4)
1236 /* Return the SSA_NAME in T or T's operands.
1237 Return NULL if SSA_NAME cannot be found. */
1240 get_base_value (tree t
)
1242 if (TREE_CODE (t
) == SSA_NAME
)
1245 if (!BINARY_CLASS_P (t
))
1248 switch (TREE_OPERAND_LENGTH (t
))
1251 return strips_small_constant (TREE_OPERAND (t
, 0), NULL
);
1253 return strips_small_constant (TREE_OPERAND (t
, 0),
1254 TREE_OPERAND (t
, 1));
1260 /* Check the compare STMT in LOOP. If it compares an induction
1261 variable to a loop invariant, return true, and save
1262 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1263 Otherwise return false and set LOOP_INVAIANT to NULL. */
1266 is_comparison_with_loop_invariant_p (gcond
*stmt
, struct loop
*loop
,
1267 tree
*loop_invariant
,
1268 enum tree_code
*compare_code
,
1272 tree op0
, op1
, bound
, base
;
1274 enum tree_code code
;
1277 code
= gimple_cond_code (stmt
);
1278 *loop_invariant
= NULL
;
1294 op0
= gimple_cond_lhs (stmt
);
1295 op1
= gimple_cond_rhs (stmt
);
1297 if ((TREE_CODE (op0
) != SSA_NAME
&& TREE_CODE (op0
) != INTEGER_CST
)
1298 || (TREE_CODE (op1
) != SSA_NAME
&& TREE_CODE (op1
) != INTEGER_CST
))
1300 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, true))
1302 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, true))
1304 if (TREE_CODE (iv0
.step
) != INTEGER_CST
1305 || TREE_CODE (iv1
.step
) != INTEGER_CST
)
1307 if ((integer_zerop (iv0
.step
) && integer_zerop (iv1
.step
))
1308 || (!integer_zerop (iv0
.step
) && !integer_zerop (iv1
.step
)))
1311 if (integer_zerop (iv0
.step
))
1313 if (code
!= NE_EXPR
&& code
!= EQ_EXPR
)
1314 code
= invert_tree_comparison (code
, false);
1317 if (tree_fits_shwi_p (iv1
.step
))
1326 if (tree_fits_shwi_p (iv0
.step
))
1332 if (TREE_CODE (bound
) != INTEGER_CST
)
1333 bound
= get_base_value (bound
);
1336 if (TREE_CODE (base
) != INTEGER_CST
)
1337 base
= get_base_value (base
);
1341 *loop_invariant
= bound
;
1342 *compare_code
= code
;
1344 *loop_iv_base
= base
;
1348 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1351 expr_coherent_p (tree t1
, tree t2
)
1354 tree ssa_name_1
= NULL
;
1355 tree ssa_name_2
= NULL
;
1357 gcc_assert (TREE_CODE (t1
) == SSA_NAME
|| TREE_CODE (t1
) == INTEGER_CST
);
1358 gcc_assert (TREE_CODE (t2
) == SSA_NAME
|| TREE_CODE (t2
) == INTEGER_CST
);
1363 if (TREE_CODE (t1
) == INTEGER_CST
&& TREE_CODE (t2
) == INTEGER_CST
)
1365 if (TREE_CODE (t1
) == INTEGER_CST
|| TREE_CODE (t2
) == INTEGER_CST
)
1368 /* Check to see if t1 is expressed/defined with t2. */
1369 stmt
= SSA_NAME_DEF_STMT (t1
);
1370 gcc_assert (stmt
!= NULL
);
1371 if (is_gimple_assign (stmt
))
1373 ssa_name_1
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1374 if (ssa_name_1
&& ssa_name_1
== t2
)
1378 /* Check to see if t2 is expressed/defined with t1. */
1379 stmt
= SSA_NAME_DEF_STMT (t2
);
1380 gcc_assert (stmt
!= NULL
);
1381 if (is_gimple_assign (stmt
))
1383 ssa_name_2
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1384 if (ssa_name_2
&& ssa_name_2
== t1
)
1388 /* Compare if t1 and t2's def_stmts are identical. */
1389 if (ssa_name_2
!= NULL
&& ssa_name_1
== ssa_name_2
)
1395 /* Return true if E is predicted by one of loop heuristics. */
1398 predicted_by_loop_heuristics_p (basic_block bb
)
1400 struct edge_prediction
*i
;
1401 edge_prediction
**preds
= bb_predictions
->get (bb
);
1406 for (i
= *preds
; i
; i
= i
->ep_next
)
1407 if (i
->ep_predictor
== PRED_LOOP_ITERATIONS_GUESSED
1408 || i
->ep_predictor
== PRED_LOOP_ITERATIONS_MAX
1409 || i
->ep_predictor
== PRED_LOOP_ITERATIONS
1410 || i
->ep_predictor
== PRED_LOOP_EXIT
1411 || i
->ep_predictor
== PRED_LOOP_EXIT_WITH_RECURSION
1412 || i
->ep_predictor
== PRED_LOOP_EXTRA_EXIT
)
1417 /* Predict branch probability of BB when BB contains a branch that compares
1418 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1419 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1422 for (int i = 0; i < bound; i++) {
1429 In this loop, we will predict the branch inside the loop to be taken. */
1432 predict_iv_comparison (struct loop
*loop
, basic_block bb
,
1433 tree loop_bound_var
,
1434 tree loop_iv_base_var
,
1435 enum tree_code loop_bound_code
,
1436 int loop_bound_step
)
1439 tree compare_var
, compare_base
;
1440 enum tree_code compare_code
;
1441 tree compare_step_var
;
1445 if (predicted_by_loop_heuristics_p (bb
))
1448 stmt
= last_stmt (bb
);
1449 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1451 if (!is_comparison_with_loop_invariant_p (as_a
<gcond
*> (stmt
),
1458 /* Find the taken edge. */
1459 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
1460 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
1463 /* When comparing an IV to a loop invariant, NE is more likely to be
1464 taken while EQ is more likely to be not-taken. */
1465 if (compare_code
== NE_EXPR
)
1467 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1470 else if (compare_code
== EQ_EXPR
)
1472 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1476 if (!expr_coherent_p (loop_iv_base_var
, compare_base
))
1479 /* If loop bound, base and compare bound are all constants, we can
1480 calculate the probability directly. */
1481 if (tree_fits_shwi_p (loop_bound_var
)
1482 && tree_fits_shwi_p (compare_var
)
1483 && tree_fits_shwi_p (compare_base
))
1486 bool overflow
, overall_overflow
= false;
1487 widest_int compare_count
, tem
;
1489 /* (loop_bound - base) / compare_step */
1490 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1491 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1492 overall_overflow
|= overflow
;
1493 widest_int loop_count
= wi::div_trunc (tem
,
1494 wi::to_widest (compare_step_var
),
1496 overall_overflow
|= overflow
;
1498 if (!wi::neg_p (wi::to_widest (compare_step_var
))
1499 ^ (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1501 /* (loop_bound - compare_bound) / compare_step */
1502 tem
= wi::sub (wi::to_widest (loop_bound_var
),
1503 wi::to_widest (compare_var
), SIGNED
, &overflow
);
1504 overall_overflow
|= overflow
;
1505 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1507 overall_overflow
|= overflow
;
1511 /* (compare_bound - base) / compare_step */
1512 tem
= wi::sub (wi::to_widest (compare_var
),
1513 wi::to_widest (compare_base
), SIGNED
, &overflow
);
1514 overall_overflow
|= overflow
;
1515 compare_count
= wi::div_trunc (tem
, wi::to_widest (compare_step_var
),
1517 overall_overflow
|= overflow
;
1519 if (compare_code
== LE_EXPR
|| compare_code
== GE_EXPR
)
1521 if (loop_bound_code
== LE_EXPR
|| loop_bound_code
== GE_EXPR
)
1523 if (wi::neg_p (compare_count
))
1525 if (wi::neg_p (loop_count
))
1527 if (loop_count
== 0)
1529 else if (wi::cmps (compare_count
, loop_count
) == 1)
1530 probability
= REG_BR_PROB_BASE
;
1533 tem
= compare_count
* REG_BR_PROB_BASE
;
1534 tem
= wi::udiv_trunc (tem
, loop_count
);
1535 probability
= tem
.to_uhwi ();
1538 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1539 if (!overall_overflow
)
1540 predict_edge (then_edge
, PRED_LOOP_IV_COMPARE
, probability
);
1545 if (expr_coherent_p (loop_bound_var
, compare_var
))
1547 if ((loop_bound_code
== LT_EXPR
|| loop_bound_code
== LE_EXPR
)
1548 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1549 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1550 else if ((loop_bound_code
== GT_EXPR
|| loop_bound_code
== GE_EXPR
)
1551 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1552 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1553 else if (loop_bound_code
== NE_EXPR
)
1555 /* If the loop backedge condition is "(i != bound)", we do
1556 the comparison based on the step of IV:
1557 * step < 0 : backedge condition is like (i > bound)
1558 * step > 0 : backedge condition is like (i < bound) */
1559 gcc_assert (loop_bound_step
!= 0);
1560 if (loop_bound_step
> 0
1561 && (compare_code
== LT_EXPR
1562 || compare_code
== LE_EXPR
))
1563 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1564 else if (loop_bound_step
< 0
1565 && (compare_code
== GT_EXPR
1566 || compare_code
== GE_EXPR
))
1567 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1569 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1572 /* The branch is predicted not-taken if loop_bound_code is
1573 opposite with compare_code. */
1574 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1576 else if (expr_coherent_p (loop_iv_base_var
, compare_var
))
1579 for (i = s; i < h; i++)
1581 The branch should be predicted taken. */
1582 if (loop_bound_step
> 0
1583 && (compare_code
== GT_EXPR
|| compare_code
== GE_EXPR
))
1584 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1585 else if (loop_bound_step
< 0
1586 && (compare_code
== LT_EXPR
|| compare_code
== LE_EXPR
))
1587 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, TAKEN
);
1589 predict_edge_def (then_edge
, PRED_LOOP_IV_COMPARE_GUESS
, NOT_TAKEN
);
1593 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1594 exits are resulted from short-circuit conditions that will generate an
1597 if (foo() || global > 10)
1600 This will be translated into:
1605 if foo() goto BB6 else goto BB5
1607 if global > 10 goto BB6 else goto BB7
1611 iftmp = (PHI 0(BB5), 1(BB6))
1612 if iftmp == 1 goto BB8 else goto BB3
1614 outside of the loop...
1616 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1617 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1618 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1619 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1622 predict_extra_loop_exits (edge exit_edge
)
1625 bool check_value_one
;
1626 gimple
*lhs_def_stmt
;
1628 tree cmp_rhs
, cmp_lhs
;
1632 last
= last_stmt (exit_edge
->src
);
1635 cmp_stmt
= dyn_cast
<gcond
*> (last
);
1639 cmp_rhs
= gimple_cond_rhs (cmp_stmt
);
1640 cmp_lhs
= gimple_cond_lhs (cmp_stmt
);
1641 if (!TREE_CONSTANT (cmp_rhs
)
1642 || !(integer_zerop (cmp_rhs
) || integer_onep (cmp_rhs
)))
1644 if (TREE_CODE (cmp_lhs
) != SSA_NAME
)
1647 /* If check_value_one is true, only the phi_args with value '1' will lead
1648 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1650 check_value_one
= (((integer_onep (cmp_rhs
))
1651 ^ (gimple_cond_code (cmp_stmt
) == EQ_EXPR
))
1652 ^ ((exit_edge
->flags
& EDGE_TRUE_VALUE
) != 0));
1654 lhs_def_stmt
= SSA_NAME_DEF_STMT (cmp_lhs
);
1658 phi_stmt
= dyn_cast
<gphi
*> (lhs_def_stmt
);
1662 for (i
= 0; i
< gimple_phi_num_args (phi_stmt
); i
++)
1666 tree val
= gimple_phi_arg_def (phi_stmt
, i
);
1667 edge e
= gimple_phi_arg_edge (phi_stmt
, i
);
1669 if (!TREE_CONSTANT (val
) || !(integer_zerop (val
) || integer_onep (val
)))
1671 if ((check_value_one
^ integer_onep (val
)) == 1)
1673 if (EDGE_COUNT (e
->src
->succs
) != 1)
1675 predict_paths_leading_to_edge (e
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1679 FOR_EACH_EDGE (e1
, ei
, e
->src
->preds
)
1680 predict_paths_leading_to_edge (e1
, PRED_LOOP_EXTRA_EXIT
, NOT_TAKEN
);
1685 /* Predict edge probabilities by exploiting loop structure. */
1688 predict_loops (void)
1692 hash_set
<struct loop
*> with_recursion(10);
1694 FOR_EACH_BB_FN (bb
, cfun
)
1696 gimple_stmt_iterator gsi
;
1699 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1700 if (is_gimple_call (gsi_stmt (gsi
))
1701 && (decl
= gimple_call_fndecl (gsi_stmt (gsi
))) != NULL
1702 && recursive_call_p (current_function_decl
, decl
))
1704 loop
= bb
->loop_father
;
1705 while (loop
&& !with_recursion
.add (loop
))
1706 loop
= loop_outer (loop
);
1710 /* Try to predict out blocks in a loop that are not part of a
1712 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1714 basic_block bb
, *bbs
;
1715 unsigned j
, n_exits
= 0;
1717 struct tree_niter_desc niter_desc
;
1719 struct nb_iter_bound
*nb_iter
;
1720 enum tree_code loop_bound_code
= ERROR_MARK
;
1721 tree loop_bound_step
= NULL
;
1722 tree loop_bound_var
= NULL
;
1723 tree loop_iv_base
= NULL
;
1725 bool recursion
= with_recursion
.contains (loop
);
1727 exits
= get_loop_exit_edges (loop
);
1728 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1729 if (!(ex
->flags
& (EDGE_EH
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
)))
1737 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1738 fprintf (dump_file
, "Predicting loop %i%s with %i exits.\n",
1739 loop
->num
, recursion
? " (with recursion)":"", n_exits
);
1740 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1741 && max_loop_iterations_int (loop
) >= 0)
1744 "Loop %d iterates at most %i times.\n", loop
->num
,
1745 (int)max_loop_iterations_int (loop
));
1747 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1748 && likely_max_loop_iterations_int (loop
) >= 0)
1750 fprintf (dump_file
, "Loop %d likely iterates at most %i times.\n",
1751 loop
->num
, (int)likely_max_loop_iterations_int (loop
));
1754 FOR_EACH_VEC_ELT (exits
, j
, ex
)
1757 HOST_WIDE_INT nitercst
;
1758 int max
= PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS
);
1760 enum br_predictor predictor
;
1763 if (ex
->flags
& (EDGE_EH
| EDGE_ABNORMAL_CALL
| EDGE_FAKE
))
1765 /* Loop heuristics do not expect exit conditional to be inside
1766 inner loop. We predict from innermost to outermost loop. */
1767 if (predicted_by_loop_heuristics_p (ex
->src
))
1769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1770 fprintf (dump_file
, "Skipping exit %i->%i because "
1771 "it is already predicted.\n",
1772 ex
->src
->index
, ex
->dest
->index
);
1775 predict_extra_loop_exits (ex
);
1777 if (number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
1778 niter
= niter_desc
.niter
;
1779 if (!niter
|| TREE_CODE (niter_desc
.niter
) != INTEGER_CST
)
1780 niter
= loop_niter_by_eval (loop
, ex
);
1781 if (dump_file
&& (dump_flags
& TDF_DETAILS
)
1782 && TREE_CODE (niter
) == INTEGER_CST
)
1784 fprintf (dump_file
, "Exit %i->%i %d iterates ",
1785 ex
->src
->index
, ex
->dest
->index
,
1787 print_generic_expr (dump_file
, niter
, TDF_SLIM
);
1788 fprintf (dump_file
, " times.\n");
1791 if (TREE_CODE (niter
) == INTEGER_CST
)
1793 if (tree_fits_uhwi_p (niter
)
1795 && compare_tree_int (niter
, max
- 1) == -1)
1796 nitercst
= tree_to_uhwi (niter
) + 1;
1799 predictor
= PRED_LOOP_ITERATIONS
;
1801 /* If we have just one exit and we can derive some information about
1802 the number of iterations of the loop from the statements inside
1803 the loop, use it to predict this exit. */
1804 else if (n_exits
== 1
1805 && estimated_stmt_executions (loop
, &nit
))
1807 if (wi::gtu_p (nit
, max
))
1810 nitercst
= nit
.to_shwi ();
1811 predictor
= PRED_LOOP_ITERATIONS_GUESSED
;
1813 /* If we have likely upper bound, trust it for very small iteration
1814 counts. Such loops would otherwise get mispredicted by standard
1815 LOOP_EXIT heuristics. */
1816 else if (n_exits
== 1
1817 && likely_max_stmt_executions (loop
, &nit
)
1819 RDIV (REG_BR_PROB_BASE
,
1823 ? PRED_LOOP_EXIT_WITH_RECURSION
1824 : PRED_LOOP_EXIT
].hitrate
)))
1826 nitercst
= nit
.to_shwi ();
1827 predictor
= PRED_LOOP_ITERATIONS_MAX
;
1831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1832 fprintf (dump_file
, "Nothing known about exit %i->%i.\n",
1833 ex
->src
->index
, ex
->dest
->index
);
1837 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1838 fprintf (dump_file
, "Recording prediction to %i iterations by %s.\n",
1839 (int)nitercst
, predictor_info
[predictor
].name
);
1840 /* If the prediction for number of iterations is zero, do not
1841 predict the exit edges. */
1845 probability
= RDIV (REG_BR_PROB_BASE
, nitercst
);
1846 predict_edge (ex
, predictor
, probability
);
1850 /* Find information about loop bound variables. */
1851 for (nb_iter
= loop
->bounds
; nb_iter
;
1852 nb_iter
= nb_iter
->next
)
1854 && gimple_code (nb_iter
->stmt
) == GIMPLE_COND
)
1856 stmt
= as_a
<gcond
*> (nb_iter
->stmt
);
1859 if (!stmt
&& last_stmt (loop
->header
)
1860 && gimple_code (last_stmt (loop
->header
)) == GIMPLE_COND
)
1861 stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
1863 is_comparison_with_loop_invariant_p (stmt
, loop
,
1869 bbs
= get_loop_body (loop
);
1871 for (j
= 0; j
< loop
->num_nodes
; j
++)
1878 /* Bypass loop heuristics on continue statement. These
1879 statements construct loops via "non-loop" constructs
1880 in the source language and are better to be handled
1882 if (predicted_by_p (bb
, PRED_CONTINUE
))
1884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1885 fprintf (dump_file
, "BB %i predicted by continue.\n",
1890 /* If we already used more reliable loop exit predictors, do not
1891 bother with PRED_LOOP_EXIT. */
1892 if (!predicted_by_loop_heuristics_p (bb
))
1894 /* For loop with many exits we don't want to predict all exits
1895 with the pretty large probability, because if all exits are
1896 considered in row, the loop would be predicted to iterate
1897 almost never. The code to divide probability by number of
1898 exits is very rough. It should compute the number of exits
1899 taken in each patch through function (not the overall number
1900 of exits that might be a lot higher for loops with wide switch
1901 statements in them) and compute n-th square root.
1903 We limit the minimal probability by 2% to avoid
1904 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1905 as this was causing regression in perl benchmark containing such
1908 int probability
= ((REG_BR_PROB_BASE
1911 ? PRED_LOOP_EXIT_WITH_RECURSION
1912 : PRED_LOOP_EXIT
].hitrate
)
1914 if (probability
< HITRATE (2))
1915 probability
= HITRATE (2);
1916 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1917 if (e
->dest
->index
< NUM_FIXED_BLOCKS
1918 || !flow_bb_inside_loop_p (loop
, e
->dest
))
1920 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1922 "Predicting exit %i->%i with prob %i.\n",
1923 e
->src
->index
, e
->dest
->index
, probability
);
1925 recursion
? PRED_LOOP_EXIT_WITH_RECURSION
1926 : PRED_LOOP_EXIT
, probability
);
1930 predict_iv_comparison (loop
, bb
, loop_bound_var
, loop_iv_base
,
1932 tree_to_shwi (loop_bound_step
));
1935 /* In the following code
1940 guess that cond is unlikely. */
1941 if (loop_outer (loop
)->num
)
1943 basic_block bb
= NULL
;
1944 edge preheader_edge
= loop_preheader_edge (loop
);
1946 if (single_pred_p (preheader_edge
->src
)
1947 && single_succ_p (preheader_edge
->src
))
1948 preheader_edge
= single_pred_edge (preheader_edge
->src
);
1950 gimple
*stmt
= last_stmt (preheader_edge
->src
);
1951 /* Pattern match fortran loop preheader:
1952 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
1953 _17 = (logical(kind=4)) _16;
1959 Loop guard branch prediction says nothing about duplicated loop
1960 headers produced by fortran frontend and in this case we want
1961 to predict paths leading to this preheader. */
1964 && gimple_code (stmt
) == GIMPLE_COND
1965 && gimple_cond_code (stmt
) == NE_EXPR
1966 && TREE_CODE (gimple_cond_lhs (stmt
)) == SSA_NAME
1967 && integer_zerop (gimple_cond_rhs (stmt
)))
1969 gimple
*call_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
1970 if (gimple_code (call_stmt
) == GIMPLE_ASSIGN
1971 && gimple_expr_code (call_stmt
) == NOP_EXPR
1972 && TREE_CODE (gimple_assign_rhs1 (call_stmt
)) == SSA_NAME
)
1973 call_stmt
= SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt
));
1974 if (gimple_code (call_stmt
) == GIMPLE_CALL
1975 && gimple_call_internal_p (call_stmt
)
1976 && gimple_call_internal_fn (call_stmt
) == IFN_BUILTIN_EXPECT
1977 && TREE_CODE (gimple_call_arg (call_stmt
, 2)) == INTEGER_CST
1978 && tree_fits_uhwi_p (gimple_call_arg (call_stmt
, 2))
1979 && tree_to_uhwi (gimple_call_arg (call_stmt
, 2))
1980 == PRED_FORTRAN_LOOP_PREHEADER
)
1981 bb
= preheader_edge
->src
;
1985 if (!dominated_by_p (CDI_DOMINATORS
,
1986 loop_outer (loop
)->latch
, loop
->header
))
1987 predict_paths_leading_to_edge (loop_preheader_edge (loop
),
1989 ? PRED_LOOP_GUARD_WITH_RECURSION
1996 if (!dominated_by_p (CDI_DOMINATORS
,
1997 loop_outer (loop
)->latch
, bb
))
1998 predict_paths_leading_to (bb
,
2000 ? PRED_LOOP_GUARD_WITH_RECURSION
2007 /* Free basic blocks from get_loop_body. */
2012 /* Attempt to predict probabilities of BB outgoing edges using local
2015 bb_estimate_probability_locally (basic_block bb
)
2017 rtx_insn
*last_insn
= BB_END (bb
);
2020 if (! can_predict_insn_p (last_insn
))
2022 cond
= get_condition (last_insn
, NULL
, false, false);
2026 /* Try "pointer heuristic."
2027 A comparison ptr == 0 is predicted as false.
2028 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2029 if (COMPARISON_P (cond
)
2030 && ((REG_P (XEXP (cond
, 0)) && REG_POINTER (XEXP (cond
, 0)))
2031 || (REG_P (XEXP (cond
, 1)) && REG_POINTER (XEXP (cond
, 1)))))
2033 if (GET_CODE (cond
) == EQ
)
2034 predict_insn_def (last_insn
, PRED_POINTER
, NOT_TAKEN
);
2035 else if (GET_CODE (cond
) == NE
)
2036 predict_insn_def (last_insn
, PRED_POINTER
, TAKEN
);
2040 /* Try "opcode heuristic."
2041 EQ tests are usually false and NE tests are usually true. Also,
2042 most quantities are positive, so we can make the appropriate guesses
2043 about signed comparisons against zero. */
2044 switch (GET_CODE (cond
))
2047 /* Unconditional branch. */
2048 predict_insn_def (last_insn
, PRED_UNCONDITIONAL
,
2049 cond
== const0_rtx
? NOT_TAKEN
: TAKEN
);
2054 /* Floating point comparisons appears to behave in a very
2055 unpredictable way because of special role of = tests in
2057 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2059 /* Comparisons with 0 are often used for booleans and there is
2060 nothing useful to predict about them. */
2061 else if (XEXP (cond
, 1) == const0_rtx
2062 || XEXP (cond
, 0) == const0_rtx
)
2065 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, NOT_TAKEN
);
2070 /* Floating point comparisons appears to behave in a very
2071 unpredictable way because of special role of = tests in
2073 if (FLOAT_MODE_P (GET_MODE (XEXP (cond
, 0))))
2075 /* Comparisons with 0 are often used for booleans and there is
2076 nothing useful to predict about them. */
2077 else if (XEXP (cond
, 1) == const0_rtx
2078 || XEXP (cond
, 0) == const0_rtx
)
2081 predict_insn_def (last_insn
, PRED_OPCODE_NONEQUAL
, TAKEN
);
2085 predict_insn_def (last_insn
, PRED_FPOPCODE
, TAKEN
);
2089 predict_insn_def (last_insn
, PRED_FPOPCODE
, NOT_TAKEN
);
2094 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2095 || XEXP (cond
, 1) == constm1_rtx
)
2096 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, NOT_TAKEN
);
2101 if (XEXP (cond
, 1) == const0_rtx
|| XEXP (cond
, 1) == const1_rtx
2102 || XEXP (cond
, 1) == constm1_rtx
)
2103 predict_insn_def (last_insn
, PRED_OPCODE_POSITIVE
, TAKEN
);
2111 /* Set edge->probability for each successor edge of BB. */
2113 guess_outgoing_edge_probabilities (basic_block bb
)
2115 bb_estimate_probability_locally (bb
);
2116 combine_predictions_for_insn (BB_END (bb
), bb
);
2119 static tree
expr_expected_value (tree
, bitmap
, enum br_predictor
*predictor
);
2121 /* Helper function for expr_expected_value. */
2124 expr_expected_value_1 (tree type
, tree op0
, enum tree_code code
,
2125 tree op1
, bitmap visited
, enum br_predictor
*predictor
)
2130 *predictor
= PRED_UNCONDITIONAL
;
2132 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2134 if (TREE_CONSTANT (op0
))
2137 if (code
!= SSA_NAME
)
2140 def
= SSA_NAME_DEF_STMT (op0
);
2142 /* If we were already here, break the infinite cycle. */
2143 if (!bitmap_set_bit (visited
, SSA_NAME_VERSION (op0
)))
2146 if (gimple_code (def
) == GIMPLE_PHI
)
2148 /* All the arguments of the PHI node must have the same constant
2150 int i
, n
= gimple_phi_num_args (def
);
2151 tree val
= NULL
, new_val
;
2153 for (i
= 0; i
< n
; i
++)
2155 tree arg
= PHI_ARG_DEF (def
, i
);
2156 enum br_predictor predictor2
;
2158 /* If this PHI has itself as an argument, we cannot
2159 determine the string length of this argument. However,
2160 if we can find an expected constant value for the other
2161 PHI args then we can still be sure that this is
2162 likely a constant. So be optimistic and just
2163 continue with the next argument. */
2164 if (arg
== PHI_RESULT (def
))
2167 new_val
= expr_expected_value (arg
, visited
, &predictor2
);
2169 /* It is difficult to combine value predictors. Simply assume
2170 that later predictor is weaker and take its prediction. */
2171 if (predictor
&& *predictor
< predictor2
)
2172 *predictor
= predictor2
;
2177 else if (!operand_equal_p (val
, new_val
, false))
2182 if (is_gimple_assign (def
))
2184 if (gimple_assign_lhs (def
) != op0
)
2187 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def
)),
2188 gimple_assign_rhs1 (def
),
2189 gimple_assign_rhs_code (def
),
2190 gimple_assign_rhs2 (def
),
2191 visited
, predictor
);
2194 if (is_gimple_call (def
))
2196 tree decl
= gimple_call_fndecl (def
);
2199 if (gimple_call_internal_p (def
)
2200 && gimple_call_internal_fn (def
) == IFN_BUILTIN_EXPECT
)
2202 gcc_assert (gimple_call_num_args (def
) == 3);
2203 tree val
= gimple_call_arg (def
, 0);
2204 if (TREE_CONSTANT (val
))
2208 tree val2
= gimple_call_arg (def
, 2);
2209 gcc_assert (TREE_CODE (val2
) == INTEGER_CST
2210 && tree_fits_uhwi_p (val2
)
2211 && tree_to_uhwi (val2
) < END_PREDICTORS
);
2212 *predictor
= (enum br_predictor
) tree_to_uhwi (val2
);
2214 return gimple_call_arg (def
, 1);
2218 if (DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
2219 switch (DECL_FUNCTION_CODE (decl
))
2221 case BUILT_IN_EXPECT
:
2224 if (gimple_call_num_args (def
) != 2)
2226 val
= gimple_call_arg (def
, 0);
2227 if (TREE_CONSTANT (val
))
2230 *predictor
= PRED_BUILTIN_EXPECT
;
2231 return gimple_call_arg (def
, 1);
2234 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N
:
2235 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1
:
2236 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2
:
2237 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4
:
2238 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8
:
2239 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16
:
2240 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE
:
2241 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
:
2242 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1
:
2243 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2
:
2244 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4
:
2245 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8
:
2246 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16
:
2247 /* Assume that any given atomic operation has low contention,
2248 and thus the compare-and-swap operation succeeds. */
2250 *predictor
= PRED_COMPARE_AND_SWAP
;
2251 return boolean_true_node
;
2260 if (get_gimple_rhs_class (code
) == GIMPLE_BINARY_RHS
)
2263 enum br_predictor predictor2
;
2264 op0
= expr_expected_value (op0
, visited
, predictor
);
2267 op1
= expr_expected_value (op1
, visited
, &predictor2
);
2268 if (predictor
&& *predictor
< predictor2
)
2269 *predictor
= predictor2
;
2272 res
= fold_build2 (code
, type
, op0
, op1
);
2273 if (TREE_CONSTANT (res
))
2277 if (get_gimple_rhs_class (code
) == GIMPLE_UNARY_RHS
)
2280 op0
= expr_expected_value (op0
, visited
, predictor
);
2283 res
= fold_build1 (code
, type
, op0
);
2284 if (TREE_CONSTANT (res
))
2291 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2292 The function is used by builtin_expect branch predictor so the evidence
2293 must come from this construct and additional possible constant folding.
2295 We may want to implement more involved value guess (such as value range
2296 propagation based prediction), but such tricks shall go to new
2300 expr_expected_value (tree expr
, bitmap visited
,
2301 enum br_predictor
*predictor
)
2303 enum tree_code code
;
2306 if (TREE_CONSTANT (expr
))
2309 *predictor
= PRED_UNCONDITIONAL
;
2313 extract_ops_from_tree (expr
, &code
, &op0
, &op1
);
2314 return expr_expected_value_1 (TREE_TYPE (expr
),
2315 op0
, code
, op1
, visited
, predictor
);
2318 /* Predict using opcode of the last statement in basic block. */
2320 tree_predict_by_opcode (basic_block bb
)
2322 gimple
*stmt
= last_stmt (bb
);
2330 enum br_predictor predictor
;
2332 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2334 FOR_EACH_EDGE (then_edge
, ei
, bb
->succs
)
2335 if (then_edge
->flags
& EDGE_TRUE_VALUE
)
2337 op0
= gimple_cond_lhs (stmt
);
2338 op1
= gimple_cond_rhs (stmt
);
2339 cmp
= gimple_cond_code (stmt
);
2340 type
= TREE_TYPE (op0
);
2341 visited
= BITMAP_ALLOC (NULL
);
2342 val
= expr_expected_value_1 (boolean_type_node
, op0
, cmp
, op1
, visited
,
2344 BITMAP_FREE (visited
);
2345 if (val
&& TREE_CODE (val
) == INTEGER_CST
)
2347 if (predictor
== PRED_BUILTIN_EXPECT
)
2349 int percent
= PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY
);
2351 gcc_assert (percent
>= 0 && percent
<= 100);
2352 if (integer_zerop (val
))
2353 percent
= 100 - percent
;
2354 predict_edge (then_edge
, PRED_BUILTIN_EXPECT
, HITRATE (percent
));
2357 predict_edge_def (then_edge
, predictor
,
2358 integer_zerop (val
) ? NOT_TAKEN
: TAKEN
);
2360 /* Try "pointer heuristic."
2361 A comparison ptr == 0 is predicted as false.
2362 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2363 if (POINTER_TYPE_P (type
))
2366 predict_edge_def (then_edge
, PRED_TREE_POINTER
, NOT_TAKEN
);
2367 else if (cmp
== NE_EXPR
)
2368 predict_edge_def (then_edge
, PRED_TREE_POINTER
, TAKEN
);
2372 /* Try "opcode heuristic."
2373 EQ tests are usually false and NE tests are usually true. Also,
2374 most quantities are positive, so we can make the appropriate guesses
2375 about signed comparisons against zero. */
2380 /* Floating point comparisons appears to behave in a very
2381 unpredictable way because of special role of = tests in
2383 if (FLOAT_TYPE_P (type
))
2385 /* Comparisons with 0 are often used for booleans and there is
2386 nothing useful to predict about them. */
2387 else if (integer_zerop (op0
) || integer_zerop (op1
))
2390 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, NOT_TAKEN
);
2395 /* Floating point comparisons appears to behave in a very
2396 unpredictable way because of special role of = tests in
2398 if (FLOAT_TYPE_P (type
))
2400 /* Comparisons with 0 are often used for booleans and there is
2401 nothing useful to predict about them. */
2402 else if (integer_zerop (op0
)
2403 || integer_zerop (op1
))
2406 predict_edge_def (then_edge
, PRED_TREE_OPCODE_NONEQUAL
, TAKEN
);
2410 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, TAKEN
);
2413 case UNORDERED_EXPR
:
2414 predict_edge_def (then_edge
, PRED_TREE_FPOPCODE
, NOT_TAKEN
);
2419 if (integer_zerop (op1
)
2420 || integer_onep (op1
)
2421 || integer_all_onesp (op1
)
2424 || real_minus_onep (op1
))
2425 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, NOT_TAKEN
);
2430 if (integer_zerop (op1
)
2431 || integer_onep (op1
)
2432 || integer_all_onesp (op1
)
2435 || real_minus_onep (op1
))
2436 predict_edge_def (then_edge
, PRED_TREE_OPCODE_POSITIVE
, TAKEN
);
2444 /* Try to guess whether the value of return means error code. */
2446 static enum br_predictor
2447 return_prediction (tree val
, enum prediction
*prediction
)
2451 return PRED_NO_PREDICTION
;
2452 /* Different heuristics for pointers and scalars. */
2453 if (POINTER_TYPE_P (TREE_TYPE (val
)))
2455 /* NULL is usually not returned. */
2456 if (integer_zerop (val
))
2458 *prediction
= NOT_TAKEN
;
2459 return PRED_NULL_RETURN
;
2462 else if (INTEGRAL_TYPE_P (TREE_TYPE (val
)))
2464 /* Negative return values are often used to indicate
2466 if (TREE_CODE (val
) == INTEGER_CST
2467 && tree_int_cst_sgn (val
) < 0)
2469 *prediction
= NOT_TAKEN
;
2470 return PRED_NEGATIVE_RETURN
;
2472 /* Constant return values seems to be commonly taken.
2473 Zero/one often represent booleans so exclude them from the
2475 if (TREE_CONSTANT (val
)
2476 && (!integer_zerop (val
) && !integer_onep (val
)))
2478 *prediction
= NOT_TAKEN
;
2479 return PRED_CONST_RETURN
;
2482 return PRED_NO_PREDICTION
;
2485 /* Find the basic block with return expression and look up for possible
2486 return value trying to apply RETURN_PREDICTION heuristics. */
2488 apply_return_prediction (void)
2490 greturn
*return_stmt
= NULL
;
2494 int phi_num_args
, i
;
2495 enum br_predictor pred
;
2496 enum prediction direction
;
2499 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2501 gimple
*last
= last_stmt (e
->src
);
2503 && gimple_code (last
) == GIMPLE_RETURN
)
2505 return_stmt
= as_a
<greturn
*> (last
);
2511 return_val
= gimple_return_retval (return_stmt
);
2514 if (TREE_CODE (return_val
) != SSA_NAME
2515 || !SSA_NAME_DEF_STMT (return_val
)
2516 || gimple_code (SSA_NAME_DEF_STMT (return_val
)) != GIMPLE_PHI
)
2518 phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (return_val
));
2519 phi_num_args
= gimple_phi_num_args (phi
);
2520 pred
= return_prediction (PHI_ARG_DEF (phi
, 0), &direction
);
2522 /* Avoid the degenerate case where all return values form the function
2523 belongs to same category (ie they are all positive constants)
2524 so we can hardly say something about them. */
2525 for (i
= 1; i
< phi_num_args
; i
++)
2526 if (pred
!= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
))
2528 if (i
!= phi_num_args
)
2529 for (i
= 0; i
< phi_num_args
; i
++)
2531 pred
= return_prediction (PHI_ARG_DEF (phi
, i
), &direction
);
2532 if (pred
!= PRED_NO_PREDICTION
)
2533 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi
, i
), pred
,
2538 /* Look for basic block that contains unlikely to happen events
2539 (such as noreturn calls) and mark all paths leading to execution
2540 of this basic blocks as unlikely. */
2543 tree_bb_level_predictions (void)
2546 bool has_return_edges
= false;
2550 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
2551 if (!(e
->flags
& (EDGE_ABNORMAL
| EDGE_FAKE
| EDGE_EH
)))
2553 has_return_edges
= true;
2557 apply_return_prediction ();
2559 FOR_EACH_BB_FN (bb
, cfun
)
2561 gimple_stmt_iterator gsi
;
2563 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2565 gimple
*stmt
= gsi_stmt (gsi
);
2568 if (is_gimple_call (stmt
))
2570 if ((gimple_call_flags (stmt
) & ECF_NORETURN
)
2571 && has_return_edges
)
2572 predict_paths_leading_to (bb
, PRED_NORETURN
,
2574 decl
= gimple_call_fndecl (stmt
);
2576 && lookup_attribute ("cold",
2577 DECL_ATTRIBUTES (decl
)))
2578 predict_paths_leading_to (bb
, PRED_COLD_FUNCTION
,
2580 if (decl
&& recursive_call_p (current_function_decl
, decl
))
2581 predict_paths_leading_to (bb
, PRED_RECURSIVE_CALL
,
2584 else if (gimple_code (stmt
) == GIMPLE_PREDICT
)
2586 predict_paths_leading_to (bb
, gimple_predict_predictor (stmt
),
2587 gimple_predict_outcome (stmt
));
2588 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2589 hints to callers. */
2595 /* Callback for hash_map::traverse, asserts that the pointer map is
2599 assert_is_empty (const_basic_block
const &, edge_prediction
*const &value
,
2602 gcc_assert (!value
);
2606 /* Predict branch probabilities and estimate profile for basic block BB. */
2609 tree_estimate_probability_bb (basic_block bb
)
2615 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2617 /* Predict edges to user labels with attributes. */
2618 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2620 gimple_stmt_iterator gi
;
2621 for (gi
= gsi_start_bb (e
->dest
); !gsi_end_p (gi
); gsi_next (&gi
))
2623 glabel
*label_stmt
= dyn_cast
<glabel
*> (gsi_stmt (gi
));
2628 decl
= gimple_label_label (label_stmt
);
2629 if (DECL_ARTIFICIAL (decl
))
2632 /* Finally, we have a user-defined label. */
2633 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl
)))
2634 predict_edge_def (e
, PRED_COLD_LABEL
, NOT_TAKEN
);
2635 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl
)))
2636 predict_edge_def (e
, PRED_HOT_LABEL
, TAKEN
);
2640 /* Predict early returns to be probable, as we've already taken
2641 care for error returns and other cases are often used for
2642 fast paths through function.
2644 Since we've already removed the return statements, we are
2645 looking for CFG like:
2655 if (e
->dest
!= bb
->next_bb
2656 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
2657 && single_succ_p (e
->dest
)
2658 && single_succ_edge (e
->dest
)->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2659 && (last
= last_stmt (e
->dest
)) != NULL
2660 && gimple_code (last
) == GIMPLE_RETURN
)
2665 if (single_succ_p (bb
))
2667 FOR_EACH_EDGE (e1
, ei1
, bb
->preds
)
2668 if (!predicted_by_p (e1
->src
, PRED_NULL_RETURN
)
2669 && !predicted_by_p (e1
->src
, PRED_CONST_RETURN
)
2670 && !predicted_by_p (e1
->src
, PRED_NEGATIVE_RETURN
))
2671 predict_edge_def (e1
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2674 if (!predicted_by_p (e
->src
, PRED_NULL_RETURN
)
2675 && !predicted_by_p (e
->src
, PRED_CONST_RETURN
)
2676 && !predicted_by_p (e
->src
, PRED_NEGATIVE_RETURN
))
2677 predict_edge_def (e
, PRED_TREE_EARLY_RETURN
, NOT_TAKEN
);
2680 /* Look for block we are guarding (ie we dominate it,
2681 but it doesn't postdominate us). */
2682 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
) && e
->dest
!= bb
2683 && dominated_by_p (CDI_DOMINATORS
, e
->dest
, e
->src
)
2684 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e
->dest
))
2686 gimple_stmt_iterator bi
;
2688 /* The call heuristic claims that a guarded function call
2689 is improbable. This is because such calls are often used
2690 to signal exceptional situations such as printing error
2692 for (bi
= gsi_start_bb (e
->dest
); !gsi_end_p (bi
);
2695 gimple
*stmt
= gsi_stmt (bi
);
2696 if (is_gimple_call (stmt
)
2697 && !gimple_inexpensive_call_p (as_a
<gcall
*> (stmt
))
2698 /* Constant and pure calls are hardly used to signalize
2699 something exceptional. */
2700 && gimple_has_side_effects (stmt
))
2702 predict_edge_def (e
, PRED_CALL
, NOT_TAKEN
);
2708 tree_predict_by_opcode (bb
);
2711 /* Predict branch probabilities and estimate profile of the tree CFG.
2712 This function can be called from the loop optimizers to recompute
2713 the profile information.
2714 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2717 tree_estimate_probability (bool dry_run
)
2721 add_noreturn_fake_exit_edges ();
2722 connect_infinite_loops_to_exit ();
2723 /* We use loop_niter_by_eval, which requires that the loops have
2725 create_preheaders (CP_SIMPLE_PREHEADERS
);
2726 calculate_dominance_info (CDI_POST_DOMINATORS
);
2728 bb_predictions
= new hash_map
<const_basic_block
, edge_prediction
*>;
2729 tree_bb_level_predictions ();
2730 record_loop_exits ();
2732 if (number_of_loops (cfun
) > 1)
2735 FOR_EACH_BB_FN (bb
, cfun
)
2736 tree_estimate_probability_bb (bb
);
2738 FOR_EACH_BB_FN (bb
, cfun
)
2739 combine_predictions_for_bb (bb
, dry_run
);
2742 bb_predictions
->traverse
<void *, assert_is_empty
> (NULL
);
2744 delete bb_predictions
;
2745 bb_predictions
= NULL
;
2748 estimate_bb_frequencies (false);
2749 free_dominance_info (CDI_POST_DOMINATORS
);
2750 remove_fake_exit_edges ();
2753 /* Predict edges to successors of CUR whose sources are not postdominated by
2754 BB by PRED and recurse to all postdominators. */
2757 predict_paths_for_bb (basic_block cur
, basic_block bb
,
2758 enum br_predictor pred
,
2759 enum prediction taken
,
2760 bitmap visited
, struct loop
*in_loop
= NULL
)
2766 /* If we exited the loop or CUR is unconditional in the loop, there is
2769 && (!flow_bb_inside_loop_p (in_loop
, cur
)
2770 || dominated_by_p (CDI_DOMINATORS
, in_loop
->latch
, cur
)))
2773 /* We are looking for all edges forming edge cut induced by
2774 set of all blocks postdominated by BB. */
2775 FOR_EACH_EDGE (e
, ei
, cur
->preds
)
2776 if (e
->src
->index
>= NUM_FIXED_BLOCKS
2777 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, bb
))
2783 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2784 if (e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2786 gcc_assert (bb
== cur
|| dominated_by_p (CDI_POST_DOMINATORS
, cur
, bb
));
2788 /* See if there is an edge from e->src that is not abnormal
2789 and does not lead to BB and does not exit the loop. */
2790 FOR_EACH_EDGE (e2
, ei2
, e
->src
->succs
)
2792 && !(e2
->flags
& (EDGE_EH
| EDGE_FAKE
))
2793 && !dominated_by_p (CDI_POST_DOMINATORS
, e2
->dest
, bb
)
2794 && (!in_loop
|| !loop_exit_edge_p (in_loop
, e2
)))
2800 /* If there is non-abnormal path leaving e->src, predict edge
2801 using predictor. Otherwise we need to look for paths
2804 The second may lead to infinite loop in the case we are predicitng
2805 regions that are only reachable by abnormal edges. We simply
2806 prevent visiting given BB twice. */
2809 if (!edge_predicted_by_p (e
, pred
, taken
))
2810 predict_edge_def (e
, pred
, taken
);
2812 else if (bitmap_set_bit (visited
, e
->src
->index
))
2813 predict_paths_for_bb (e
->src
, e
->src
, pred
, taken
, visited
, in_loop
);
2815 for (son
= first_dom_son (CDI_POST_DOMINATORS
, cur
);
2817 son
= next_dom_son (CDI_POST_DOMINATORS
, son
))
2818 predict_paths_for_bb (son
, bb
, pred
, taken
, visited
, in_loop
);
2821 /* Sets branch probabilities according to PREDiction and
2825 predict_paths_leading_to (basic_block bb
, enum br_predictor pred
,
2826 enum prediction taken
, struct loop
*in_loop
)
2828 bitmap visited
= BITMAP_ALLOC (NULL
);
2829 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
, in_loop
);
2830 BITMAP_FREE (visited
);
2833 /* Like predict_paths_leading_to but take edge instead of basic block. */
2836 predict_paths_leading_to_edge (edge e
, enum br_predictor pred
,
2837 enum prediction taken
, struct loop
*in_loop
)
2839 bool has_nonloop_edge
= false;
2843 basic_block bb
= e
->src
;
2844 FOR_EACH_EDGE (e2
, ei
, bb
->succs
)
2845 if (e2
->dest
!= e
->src
&& e2
->dest
!= e
->dest
2846 && !(e
->flags
& (EDGE_EH
| EDGE_FAKE
))
2847 && !dominated_by_p (CDI_POST_DOMINATORS
, e
->src
, e2
->dest
))
2849 has_nonloop_edge
= true;
2852 if (!has_nonloop_edge
)
2854 bitmap visited
= BITMAP_ALLOC (NULL
);
2855 predict_paths_for_bb (bb
, bb
, pred
, taken
, visited
, in_loop
);
2856 BITMAP_FREE (visited
);
2859 predict_edge_def (e
, pred
, taken
);
2862 /* This is used to carry information about basic blocks. It is
2863 attached to the AUX field of the standard CFG block. */
2867 /* Estimated frequency of execution of basic_block. */
2870 /* To keep queue of basic blocks to process. */
2873 /* Number of predecessors we need to visit first. */
2877 /* Similar information for edges. */
2878 struct edge_prob_info
2880 /* In case edge is a loopback edge, the probability edge will be reached
2881 in case header is. Estimated number of iterations of the loop can be
2882 then computed as 1 / (1 - back_edge_prob). */
2883 sreal back_edge_prob
;
2884 /* True if the edge is a loopback edge in the natural loop. */
2885 unsigned int back_edge
:1;
2888 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2890 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2892 /* Helper function for estimate_bb_frequencies.
2893 Propagate the frequencies in blocks marked in
2894 TOVISIT, starting in HEAD. */
2897 propagate_freq (basic_block head
, bitmap tovisit
)
2906 /* For each basic block we need to visit count number of his predecessors
2907 we need to visit first. */
2908 EXECUTE_IF_SET_IN_BITMAP (tovisit
, 0, i
, bi
)
2913 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2915 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2917 bool visit
= bitmap_bit_p (tovisit
, e
->src
->index
);
2919 if (visit
&& !(e
->flags
& EDGE_DFS_BACK
))
2921 else if (visit
&& dump_file
&& !EDGE_INFO (e
)->back_edge
)
2923 "Irreducible region hit, ignoring edge to %i->%i\n",
2924 e
->src
->index
, bb
->index
);
2926 BLOCK_INFO (bb
)->npredecessors
= count
;
2927 /* When function never returns, we will never process exit block. */
2928 if (!count
&& bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
2929 bb
->count
= bb
->frequency
= 0;
2932 BLOCK_INFO (head
)->frequency
= 1;
2934 for (bb
= head
; bb
; bb
= nextbb
)
2937 sreal cyclic_probability
= 0;
2938 sreal frequency
= 0;
2940 nextbb
= BLOCK_INFO (bb
)->next
;
2941 BLOCK_INFO (bb
)->next
= NULL
;
2943 /* Compute frequency of basic block. */
2947 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2948 gcc_assert (!bitmap_bit_p (tovisit
, e
->src
->index
)
2949 || (e
->flags
& EDGE_DFS_BACK
));
2951 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2952 if (EDGE_INFO (e
)->back_edge
)
2954 cyclic_probability
+= EDGE_INFO (e
)->back_edge_prob
;
2956 else if (!(e
->flags
& EDGE_DFS_BACK
))
2958 /* frequency += (e->probability
2959 * BLOCK_INFO (e->src)->frequency /
2960 REG_BR_PROB_BASE); */
2962 sreal tmp
= e
->probability
;
2963 tmp
*= BLOCK_INFO (e
->src
)->frequency
;
2964 tmp
*= real_inv_br_prob_base
;
2968 if (cyclic_probability
== 0)
2970 BLOCK_INFO (bb
)->frequency
= frequency
;
2974 if (cyclic_probability
> real_almost_one
)
2975 cyclic_probability
= real_almost_one
;
2977 /* BLOCK_INFO (bb)->frequency = frequency
2978 / (1 - cyclic_probability) */
2980 cyclic_probability
= sreal (1) - cyclic_probability
;
2981 BLOCK_INFO (bb
)->frequency
= frequency
/ cyclic_probability
;
2985 bitmap_clear_bit (tovisit
, bb
->index
);
2987 e
= find_edge (bb
, head
);
2990 /* EDGE_INFO (e)->back_edge_prob
2991 = ((e->probability * BLOCK_INFO (bb)->frequency)
2992 / REG_BR_PROB_BASE); */
2994 sreal tmp
= e
->probability
;
2995 tmp
*= BLOCK_INFO (bb
)->frequency
;
2996 EDGE_INFO (e
)->back_edge_prob
= tmp
* real_inv_br_prob_base
;
2999 /* Propagate to successor blocks. */
3000 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3001 if (!(e
->flags
& EDGE_DFS_BACK
)
3002 && BLOCK_INFO (e
->dest
)->npredecessors
)
3004 BLOCK_INFO (e
->dest
)->npredecessors
--;
3005 if (!BLOCK_INFO (e
->dest
)->npredecessors
)
3010 BLOCK_INFO (last
)->next
= e
->dest
;
3018 /* Estimate frequencies in loops at same nest level. */
3021 estimate_loops_at_level (struct loop
*first_loop
)
3025 for (loop
= first_loop
; loop
; loop
= loop
->next
)
3030 bitmap tovisit
= BITMAP_ALLOC (NULL
);
3032 estimate_loops_at_level (loop
->inner
);
3034 /* Find current loop back edge and mark it. */
3035 e
= loop_latch_edge (loop
);
3036 EDGE_INFO (e
)->back_edge
= 1;
3038 bbs
= get_loop_body (loop
);
3039 for (i
= 0; i
< loop
->num_nodes
; i
++)
3040 bitmap_set_bit (tovisit
, bbs
[i
]->index
);
3042 propagate_freq (loop
->header
, tovisit
);
3043 BITMAP_FREE (tovisit
);
3047 /* Propagates frequencies through structure of loops. */
3050 estimate_loops (void)
3052 bitmap tovisit
= BITMAP_ALLOC (NULL
);
3055 /* Start by estimating the frequencies in the loops. */
3056 if (number_of_loops (cfun
) > 1)
3057 estimate_loops_at_level (current_loops
->tree_root
->inner
);
3059 /* Now propagate the frequencies through all the blocks. */
3060 FOR_ALL_BB_FN (bb
, cfun
)
3062 bitmap_set_bit (tovisit
, bb
->index
);
3064 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun
), tovisit
);
3065 BITMAP_FREE (tovisit
);
3068 /* Drop the profile for NODE to guessed, and update its frequency based on
3069 whether it is expected to be hot given the CALL_COUNT. */
3072 drop_profile (struct cgraph_node
*node
, gcov_type call_count
)
3074 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3075 /* In the case where this was called by another function with a
3076 dropped profile, call_count will be 0. Since there are no
3077 non-zero call counts to this function, we don't know for sure
3078 whether it is hot, and therefore it will be marked normal below. */
3079 bool hot
= maybe_hot_count_p (NULL
, call_count
);
3083 "Dropping 0 profile for %s/%i. %s based on calls.\n",
3084 node
->name (), node
->order
,
3085 hot
? "Function is hot" : "Function is normal");
3086 /* We only expect to miss profiles for functions that are reached
3087 via non-zero call edges in cases where the function may have
3088 been linked from another module or library (COMDATs and extern
3089 templates). See the comments below for handle_missing_profiles.
3090 Also, only warn in cases where the missing counts exceed the
3091 number of training runs. In certain cases with an execv followed
3092 by a no-return call the profile for the no-return call is not
3093 dumped and there can be a mismatch. */
3094 if (!DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
)
3095 && call_count
> profile_info
->runs
)
3097 if (flag_profile_correction
)
3101 "Missing counts for called function %s/%i\n",
3102 node
->name (), node
->order
);
3105 warning (0, "Missing counts for called function %s/%i",
3106 node
->name (), node
->order
);
3109 profile_status_for_fn (fn
)
3110 = (flag_guess_branch_prob
? PROFILE_GUESSED
: PROFILE_ABSENT
);
3112 = hot
? NODE_FREQUENCY_HOT
: NODE_FREQUENCY_NORMAL
;
3115 /* In the case of COMDAT routines, multiple object files will contain the same
3116 function and the linker will select one for the binary. In that case
3117 all the other copies from the profile instrument binary will be missing
3118 profile counts. Look for cases where this happened, due to non-zero
3119 call counts going to 0-count functions, and drop the profile to guessed
3120 so that we can use the estimated probabilities and avoid optimizing only
3123 The other case where the profile may be missing is when the routine
3124 is not going to be emitted to the object file, e.g. for "extern template"
3125 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3126 all other cases of non-zero calls to 0-count functions. */
3129 handle_missing_profiles (void)
3131 struct cgraph_node
*node
;
3132 int unlikely_count_fraction
= PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION
);
3133 vec
<struct cgraph_node
*> worklist
;
3134 worklist
.create (64);
3136 /* See if 0 count function has non-0 count callers. In this case we
3137 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3138 FOR_EACH_DEFINED_FUNCTION (node
)
3140 struct cgraph_edge
*e
;
3141 gcov_type call_count
= 0;
3142 gcov_type max_tp_first_run
= 0;
3143 struct function
*fn
= DECL_STRUCT_FUNCTION (node
->decl
);
3147 for (e
= node
->callers
; e
; e
= e
->next_caller
)
3149 call_count
+= e
->count
;
3151 if (e
->caller
->tp_first_run
> max_tp_first_run
)
3152 max_tp_first_run
= e
->caller
->tp_first_run
;
3155 /* If time profile is missing, let assign the maximum that comes from
3156 caller functions. */
3157 if (!node
->tp_first_run
&& max_tp_first_run
)
3158 node
->tp_first_run
= max_tp_first_run
+ 1;
3162 && (call_count
* unlikely_count_fraction
>= profile_info
->runs
))
3164 drop_profile (node
, call_count
);
3165 worklist
.safe_push (node
);
3169 /* Propagate the profile dropping to other 0-count COMDATs that are
3170 potentially called by COMDATs we already dropped the profile on. */
3171 while (worklist
.length () > 0)
3173 struct cgraph_edge
*e
;
3175 node
= worklist
.pop ();
3176 for (e
= node
->callees
; e
; e
= e
->next_caller
)
3178 struct cgraph_node
*callee
= e
->callee
;
3179 struct function
*fn
= DECL_STRUCT_FUNCTION (callee
->decl
);
3181 if (callee
->count
> 0)
3183 if (DECL_COMDAT (callee
->decl
) && fn
&& fn
->cfg
3184 && profile_status_for_fn (fn
) == PROFILE_READ
)
3186 drop_profile (node
, 0);
3187 worklist
.safe_push (callee
);
3191 worklist
.release ();
3194 /* Convert counts measured by profile driven feedback to frequencies.
3195 Return nonzero iff there was any nonzero execution count. */
3198 counts_to_freqs (void)
3200 gcov_type count_max
, true_count_max
= 0;
3203 /* Don't overwrite the estimated frequencies when the profile for
3204 the function is missing. We may drop this function PROFILE_GUESSED
3205 later in drop_profile (). */
3206 if (!flag_auto_profile
&& !ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
)
3209 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3210 true_count_max
= MAX (bb
->count
, true_count_max
);
3212 count_max
= MAX (true_count_max
, 1);
3213 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3214 bb
->frequency
= (bb
->count
* BB_FREQ_MAX
+ count_max
/ 2) / count_max
;
3216 return true_count_max
;
3219 /* Return true if function is likely to be expensive, so there is no point to
3220 optimize performance of prologue, epilogue or do inlining at the expense
3221 of code size growth. THRESHOLD is the limit of number of instructions
3222 function can execute at average to be still considered not expensive. */
3225 expensive_function_p (int threshold
)
3227 unsigned int sum
= 0;
3231 /* We can not compute accurately for large thresholds due to scaled
3233 gcc_assert (threshold
<= BB_FREQ_MAX
);
3235 /* Frequencies are out of range. This either means that function contains
3236 internal loop executing more than BB_FREQ_MAX times or profile feedback
3237 is available and function has not been executed at all. */
3238 if (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
== 0)
3241 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
3242 limit
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->frequency
* threshold
;
3243 FOR_EACH_BB_FN (bb
, cfun
)
3247 FOR_BB_INSNS (bb
, insn
)
3248 if (active_insn_p (insn
))
3250 sum
+= bb
->frequency
;
3259 /* Estimate and propagate basic block frequencies using the given branch
3260 probabilities. If FORCE is true, the frequencies are used to estimate
3261 the counts even when there are already non-zero profile counts. */
3264 estimate_bb_frequencies (bool force
)
3269 if (force
|| profile_status_for_fn (cfun
) != PROFILE_READ
|| !counts_to_freqs ())
3271 static int real_values_initialized
= 0;
3273 if (!real_values_initialized
)
3275 real_values_initialized
= 1;
3276 real_br_prob_base
= REG_BR_PROB_BASE
;
3277 real_bb_freq_max
= BB_FREQ_MAX
;
3278 real_one_half
= sreal (1, -1);
3279 real_inv_br_prob_base
= sreal (1) / real_br_prob_base
;
3280 real_almost_one
= sreal (1) - real_inv_br_prob_base
;
3283 mark_dfs_back_edges ();
3285 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
))->probability
=
3288 /* Set up block info for each basic block. */
3289 alloc_aux_for_blocks (sizeof (block_info
));
3290 alloc_aux_for_edges (sizeof (edge_prob_info
));
3291 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3296 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3298 EDGE_INFO (e
)->back_edge_prob
= e
->probability
;
3299 EDGE_INFO (e
)->back_edge_prob
*= real_inv_br_prob_base
;
3303 /* First compute frequencies locally for each loop from innermost
3304 to outermost to examine frequencies for back edges. */
3308 FOR_EACH_BB_FN (bb
, cfun
)
3309 if (freq_max
< BLOCK_INFO (bb
)->frequency
)
3310 freq_max
= BLOCK_INFO (bb
)->frequency
;
3312 freq_max
= real_bb_freq_max
/ freq_max
;
3313 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3315 sreal tmp
= BLOCK_INFO (bb
)->frequency
* freq_max
+ real_one_half
;
3316 bb
->frequency
= tmp
.to_int ();
3319 free_aux_for_blocks ();
3320 free_aux_for_edges ();
3322 compute_function_frequency ();
3325 /* Decide whether function is hot, cold or unlikely executed. */
3327 compute_function_frequency (void)
3330 struct cgraph_node
*node
= cgraph_node::get (current_function_decl
);
3332 if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3333 || MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3334 node
->only_called_at_startup
= true;
3335 if (DECL_STATIC_DESTRUCTOR (current_function_decl
))
3336 node
->only_called_at_exit
= true;
3338 if (profile_status_for_fn (cfun
) != PROFILE_READ
)
3340 int flags
= flags_from_decl_or_type (current_function_decl
);
3341 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl
))
3343 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3344 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl
))
3346 node
->frequency
= NODE_FREQUENCY_HOT
;
3347 else if (flags
& ECF_NORETURN
)
3348 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3349 else if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
3350 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3351 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl
)
3352 || DECL_STATIC_DESTRUCTOR (current_function_decl
))
3353 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
3357 /* Only first time try to drop function into unlikely executed.
3358 After inlining the roundoff errors may confuse us.
3359 Ipa-profile pass will drop functions only called from unlikely
3360 functions to unlikely and that is most of what we care about. */
3361 if (!cfun
->after_inlining
)
3362 node
->frequency
= NODE_FREQUENCY_UNLIKELY_EXECUTED
;
3363 FOR_EACH_BB_FN (bb
, cfun
)
3365 if (maybe_hot_bb_p (cfun
, bb
))
3367 node
->frequency
= NODE_FREQUENCY_HOT
;
3370 if (!probably_never_executed_bb_p (cfun
, bb
))
3371 node
->frequency
= NODE_FREQUENCY_NORMAL
;
3375 /* Build PREDICT_EXPR. */
3377 build_predict_expr (enum br_predictor predictor
, enum prediction taken
)
3379 tree t
= build1 (PREDICT_EXPR
, void_type_node
,
3380 build_int_cst (integer_type_node
, predictor
));
3381 SET_PREDICT_EXPR_OUTCOME (t
, taken
);
3386 predictor_name (enum br_predictor predictor
)
3388 return predictor_info
[predictor
].name
;
3391 /* Predict branch probabilities and estimate profile of the tree CFG. */
3395 const pass_data pass_data_profile
=
3397 GIMPLE_PASS
, /* type */
3398 "profile_estimate", /* name */
3399 OPTGROUP_NONE
, /* optinfo_flags */
3400 TV_BRANCH_PROB
, /* tv_id */
3401 PROP_cfg
, /* properties_required */
3402 0, /* properties_provided */
3403 0, /* properties_destroyed */
3404 0, /* todo_flags_start */
3405 0, /* todo_flags_finish */
3408 class pass_profile
: public gimple_opt_pass
3411 pass_profile (gcc::context
*ctxt
)
3412 : gimple_opt_pass (pass_data_profile
, ctxt
)
3415 /* opt_pass methods: */
3416 virtual bool gate (function
*) { return flag_guess_branch_prob
; }
3417 virtual unsigned int execute (function
*);
3419 }; // class pass_profile
3422 pass_profile::execute (function
*fun
)
3426 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
3429 loop_optimizer_init (LOOPS_NORMAL
);
3430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3431 flow_loops_dump (dump_file
, NULL
, 0);
3433 mark_irreducible_loops ();
3435 nb_loops
= number_of_loops (fun
);
3439 tree_estimate_probability (false);
3444 loop_optimizer_finalize ();
3445 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3446 gimple_dump_cfg (dump_file
, dump_flags
);
3447 if (profile_status_for_fn (fun
) == PROFILE_ABSENT
)
3448 profile_status_for_fn (fun
) = PROFILE_GUESSED
;
3449 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3452 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
3453 if (loop
->header
->frequency
)
3454 fprintf (dump_file
, "Loop got predicted %d to iterate %i times.\n",
3456 (int)expected_loop_iterations_unbounded (loop
));
3464 make_pass_profile (gcc::context
*ctxt
)
3466 return new pass_profile (ctxt
);
3471 const pass_data pass_data_strip_predict_hints
=
3473 GIMPLE_PASS
, /* type */
3474 "*strip_predict_hints", /* name */
3475 OPTGROUP_NONE
, /* optinfo_flags */
3476 TV_BRANCH_PROB
, /* tv_id */
3477 PROP_cfg
, /* properties_required */
3478 0, /* properties_provided */
3479 0, /* properties_destroyed */
3480 0, /* todo_flags_start */
3481 0, /* todo_flags_finish */
3484 class pass_strip_predict_hints
: public gimple_opt_pass
3487 pass_strip_predict_hints (gcc::context
*ctxt
)
3488 : gimple_opt_pass (pass_data_strip_predict_hints
, ctxt
)
3491 /* opt_pass methods: */
3492 opt_pass
* clone () { return new pass_strip_predict_hints (m_ctxt
); }
3493 virtual unsigned int execute (function
*);
3495 }; // class pass_strip_predict_hints
3497 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3498 we no longer need. */
3500 pass_strip_predict_hints::execute (function
*fun
)
3505 bool changed
= false;
3507 FOR_EACH_BB_FN (bb
, fun
)
3509 gimple_stmt_iterator bi
;
3510 for (bi
= gsi_start_bb (bb
); !gsi_end_p (bi
);)
3512 gimple
*stmt
= gsi_stmt (bi
);
3514 if (gimple_code (stmt
) == GIMPLE_PREDICT
)
3516 gsi_remove (&bi
, true);
3520 else if (is_gimple_call (stmt
))
3522 tree fndecl
= gimple_call_fndecl (stmt
);
3525 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
3526 && DECL_FUNCTION_CODE (fndecl
) == BUILT_IN_EXPECT
3527 && gimple_call_num_args (stmt
) == 2)
3528 || (gimple_call_internal_p (stmt
)
3529 && gimple_call_internal_fn (stmt
) == IFN_BUILTIN_EXPECT
))
3531 var
= gimple_call_lhs (stmt
);
3536 = gimple_build_assign (var
, gimple_call_arg (stmt
, 0));
3537 gsi_replace (&bi
, ass_stmt
, true);
3541 gsi_remove (&bi
, true);
3549 return changed
? TODO_cleanup_cfg
: 0;
3555 make_pass_strip_predict_hints (gcc::context
*ctxt
)
3557 return new pass_strip_predict_hints (ctxt
);
3560 /* Rebuild function frequencies. Passes are in general expected to
3561 maintain profile by hand, however in some cases this is not possible:
3562 for example when inlining several functions with loops freuqencies might run
3563 out of scale and thus needs to be recomputed. */
3566 rebuild_frequencies (void)
3568 timevar_push (TV_REBUILD_FREQUENCIES
);
3570 /* When the max bb count in the function is small, there is a higher
3571 chance that there were truncation errors in the integer scaling
3572 of counts by inlining and other optimizations. This could lead
3573 to incorrect classification of code as being cold when it isn't.
3574 In that case, force the estimation of bb counts/frequencies from the
3575 branch probabilities, rather than computing frequencies from counts,
3576 which may also lead to frequencies incorrectly reduced to 0. There
3577 is less precision in the probabilities, so we only do this for small
3579 gcov_type count_max
= 0;
3581 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), NULL
, next_bb
)
3582 count_max
= MAX (bb
->count
, count_max
);
3584 if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
3585 || (!flag_auto_profile
&& profile_status_for_fn (cfun
) == PROFILE_READ
3586 && count_max
< REG_BR_PROB_BASE
/10))
3588 loop_optimizer_init (0);
3589 add_noreturn_fake_exit_edges ();
3590 mark_irreducible_loops ();
3591 connect_infinite_loops_to_exit ();
3592 estimate_bb_frequencies (true);
3593 remove_fake_exit_edges ();
3594 loop_optimizer_finalize ();
3596 else if (profile_status_for_fn (cfun
) == PROFILE_READ
)
3600 timevar_pop (TV_REBUILD_FREQUENCIES
);
3603 /* Perform a dry run of the branch prediction pass and report comparsion of
3604 the predicted and real profile into the dump file. */
3607 report_predictor_hitrates (void)
3611 loop_optimizer_init (LOOPS_NORMAL
);
3612 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3613 flow_loops_dump (dump_file
, NULL
, 0);
3615 mark_irreducible_loops ();
3617 nb_loops
= number_of_loops (cfun
);
3621 tree_estimate_probability (true);
3626 loop_optimizer_finalize ();
3629 /* Force edge E to be cold.
3630 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
3631 keep low probability to represent possible error in a guess. This is used
3632 i.e. in case we predict loop to likely iterate given number of times but
3633 we are not 100% sure.
3635 This function locally updates profile without attempt to keep global
3636 consistency which can not be reached in full generality without full profile
3637 rebuild from probabilities alone. Doing so is not necessarily a good idea
3638 because frequencies and counts may be more realistic then probabilities.
3640 In some cases (such as for elimination of early exits during full loop
3641 unrolling) the caller can ensure that profile will get consistent
3645 force_edge_cold (edge e
, bool impossible
)
3647 gcov_type count_sum
= 0;
3651 gcov_type old_count
= e
->count
;
3652 int old_probability
= e
->probability
;
3653 gcov_type gcov_scale
= REG_BR_PROB_BASE
;
3654 int prob_scale
= REG_BR_PROB_BASE
;
3656 /* If edge is already improbably or cold, just return. */
3657 if (e
->probability
<= impossible
? PROB_VERY_UNLIKELY
: 0
3658 && (!impossible
|| !e
->count
))
3660 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3663 count_sum
+= e2
->count
;
3664 prob_sum
+= e2
->probability
;
3667 /* If there are other edges out of e->src, redistribute probabilitity
3672 = MIN (e
->probability
, impossible
? 0 : PROB_VERY_UNLIKELY
);
3673 if (old_probability
)
3674 e
->count
= RDIV (e
->count
* e
->probability
, old_probability
);
3676 e
->count
= MIN (e
->count
, impossible
? 0 : 1);
3679 gcov_scale
= RDIV ((count_sum
+ old_count
- e
->count
) * REG_BR_PROB_BASE
,
3681 prob_scale
= RDIV ((REG_BR_PROB_BASE
- e
->probability
) * REG_BR_PROB_BASE
,
3683 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3684 fprintf (dump_file
, "Making edge %i->%i %s by redistributing "
3685 "probability to other edges.\n",
3686 e
->src
->index
, e
->dest
->index
,
3687 impossible
? "impossible" : "cold");
3688 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
3691 e2
->count
= RDIV (e2
->count
* gcov_scale
, REG_BR_PROB_BASE
);
3692 e2
->probability
= RDIV (e2
->probability
* prob_scale
,
3696 /* If all edges out of e->src are unlikely, the basic block itself
3700 e
->probability
= REG_BR_PROB_BASE
;
3702 /* If we did not adjusting, the source basic block has no likely edeges
3703 leaving other direction. In that case force that bb cold, too.
3704 This in general is difficult task to do, but handle special case when
3705 BB has only one predecestor. This is common case when we are updating
3706 after loop transforms. */
3707 if (!prob_sum
&& !count_sum
&& single_pred_p (e
->src
)
3708 && e
->src
->frequency
> (impossible
? 0 : 1))
3710 int old_frequency
= e
->src
->frequency
;
3711 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3712 fprintf (dump_file
, "Making bb %i %s.\n", e
->src
->index
,
3713 impossible
? "impossible" : "cold");
3714 e
->src
->frequency
= MIN (e
->src
->frequency
, impossible
? 0 : 1);
3715 e
->src
->count
= e
->count
= RDIV (e
->src
->count
* e
->src
->frequency
,
3717 force_edge_cold (single_pred_edge (e
->src
), impossible
);
3719 else if (dump_file
&& (dump_flags
& TDF_DETAILS
)
3720 && maybe_hot_bb_p (cfun
, e
->src
))
3721 fprintf (dump_file
, "Giving up on making bb %i %s.\n", e
->src
->index
,
3722 impossible
? "impossible" : "cold");