2018-23-01 Paul Thomas <pault@gcc.gnu.org>
[official-gcc.git] / gcc / predict.c
blob2d932e9fd11645d3ebeee9b2cdeb2742a10f0e7f
1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
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
14 for more details.
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/>. */
20 /* References:
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. */
30 #include "config.h"
31 #include "system.h"
32 #include "coretypes.h"
33 #include "backend.h"
34 #include "rtl.h"
35 #include "tree.h"
36 #include "gimple.h"
37 #include "cfghooks.h"
38 #include "tree-pass.h"
39 #include "ssa.h"
40 #include "memmodel.h"
41 #include "emit-rtl.h"
42 #include "cgraph.h"
43 #include "coverage.h"
44 #include "diagnostic-core.h"
45 #include "gimple-predict.h"
46 #include "fold-const.h"
47 #include "calls.h"
48 #include "cfganal.h"
49 #include "profile.h"
50 #include "sreal.h"
51 #include "params.h"
52 #include "cfgloop.h"
53 #include "gimple-iterator.h"
54 #include "tree-cfg.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-scalar-evolution.h"
58 #include "ipa-utils.h"
59 #include "gimple-pretty-print.h"
60 #include "selftest.h"
61 #include "cfgrtl.h"
62 #include "stringpool.h"
63 #include "attribs.h"
65 /* Enum with reasons why a predictor is ignored. */
67 enum predictor_reason
69 REASON_NONE,
70 REASON_IGNORED,
71 REASON_SINGLE_EDGE_DUPLICATE,
72 REASON_EDGE_PAIR_DUPLICATE
75 /* String messages for the aforementioned enum. */
77 static const char *reason_messages[] = {"", " (ignored)",
78 " (single edge duplicate)", " (edge pair duplicate)"};
80 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
81 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
82 static sreal real_almost_one, real_br_prob_base,
83 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
85 static void combine_predictions_for_insn (rtx_insn *, basic_block);
86 static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
87 enum predictor_reason, edge);
88 static void predict_paths_leading_to (basic_block, enum br_predictor,
89 enum prediction,
90 struct loop *in_loop = NULL);
91 static void predict_paths_leading_to_edge (edge, enum br_predictor,
92 enum prediction,
93 struct loop *in_loop = NULL);
94 static bool can_predict_insn_p (const rtx_insn *);
96 /* Information we hold about each branch predictor.
97 Filled using information from predict.def. */
99 struct predictor_info
101 const char *const name; /* Name used in the debugging dumps. */
102 const int hitrate; /* Expected hitrate used by
103 predict_insn_def call. */
104 const int flags;
107 /* Use given predictor without Dempster-Shaffer theory if it matches
108 using first_match heuristics. */
109 #define PRED_FLAG_FIRST_MATCH 1
111 /* Recompute hitrate in percent to our representation. */
113 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
115 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
116 static const struct predictor_info predictor_info[]= {
117 #include "predict.def"
119 /* Upper bound on predictors. */
120 {NULL, 0, 0}
122 #undef DEF_PREDICTOR
124 static gcov_type min_count = -1;
126 /* Determine the threshold for hot BB counts. */
128 gcov_type
129 get_hot_bb_threshold ()
131 gcov_working_set_t *ws;
132 if (min_count == -1)
134 ws = find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE));
135 gcc_assert (ws);
136 min_count = ws->min_counter;
138 return min_count;
141 /* Set the threshold for hot BB counts. */
143 void
144 set_hot_bb_threshold (gcov_type min)
146 min_count = min;
149 /* Return TRUE if frequency FREQ is considered to be hot. */
151 bool
152 maybe_hot_count_p (struct function *fun, profile_count count)
154 if (!count.initialized_p ())
155 return true;
156 if (count.ipa () == profile_count::zero ())
157 return false;
158 if (!count.ipa_p ())
160 struct cgraph_node *node = cgraph_node::get (fun->decl);
161 if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
163 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
164 return false;
165 if (node->frequency == NODE_FREQUENCY_HOT)
166 return true;
168 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
169 return true;
170 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
171 && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
172 return false;
173 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
174 return false;
175 if (count.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION), 1)
176 < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
177 return false;
178 return true;
180 /* Code executed at most once is not hot. */
181 if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
182 return false;
183 return (count.to_gcov_type () >= get_hot_bb_threshold ());
186 /* Return true in case BB can be CPU intensive and should be optimized
187 for maximal performance. */
189 bool
190 maybe_hot_bb_p (struct function *fun, const_basic_block bb)
192 gcc_checking_assert (fun);
193 return maybe_hot_count_p (fun, bb->count);
196 /* Return true in case BB can be CPU intensive and should be optimized
197 for maximal performance. */
199 bool
200 maybe_hot_edge_p (edge e)
202 return maybe_hot_count_p (cfun, e->count ());
205 /* Return true if profile COUNT and FREQUENCY, or function FUN static
206 node frequency reflects never being executed. */
208 static bool
209 probably_never_executed (struct function *fun,
210 profile_count count)
212 gcc_checking_assert (fun);
213 if (count == profile_count::zero ())
214 return true;
215 /* Do not trust adjusted counts. This will make us to drop int cold section
216 code with low execution count as a result of inlining. These low counts
217 are not safe even with read profile and may lead us to dropping
218 code which actually gets executed into cold section of binary that is not
219 desirable. */
220 if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
222 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
223 if (count.apply_scale (unlikely_count_fraction, 1) >= profile_info->runs)
224 return false;
225 return true;
227 if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
228 && (cgraph_node::get (fun->decl)->frequency
229 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
230 return true;
231 return false;
235 /* Return true in case BB is probably never executed. */
237 bool
238 probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
240 return probably_never_executed (fun, bb->count);
244 /* Return true if E is unlikely executed for obvious reasons. */
246 static bool
247 unlikely_executed_edge_p (edge e)
249 return (e->count () == profile_count::zero ()
250 || e->probability == profile_probability::never ())
251 || (e->flags & (EDGE_EH | EDGE_FAKE));
254 /* Return true in case edge E is probably never executed. */
256 bool
257 probably_never_executed_edge_p (struct function *fun, edge e)
259 if (unlikely_executed_edge_p (e))
260 return true;
261 return probably_never_executed (fun, e->count ());
264 /* Return true when current function should always be optimized for size. */
266 bool
267 optimize_function_for_size_p (struct function *fun)
269 if (!fun || !fun->decl)
270 return optimize_size;
271 cgraph_node *n = cgraph_node::get (fun->decl);
272 return n && n->optimize_for_size_p ();
275 /* Return true when current function should always be optimized for speed. */
277 bool
278 optimize_function_for_speed_p (struct function *fun)
280 return !optimize_function_for_size_p (fun);
283 /* Return the optimization type that should be used for the function FUN. */
285 optimization_type
286 function_optimization_type (struct function *fun)
288 return (optimize_function_for_speed_p (fun)
289 ? OPTIMIZE_FOR_SPEED
290 : OPTIMIZE_FOR_SIZE);
293 /* Return TRUE when BB should be optimized for size. */
295 bool
296 optimize_bb_for_size_p (const_basic_block bb)
298 return (optimize_function_for_size_p (cfun)
299 || (bb && !maybe_hot_bb_p (cfun, bb)));
302 /* Return TRUE when BB should be optimized for speed. */
304 bool
305 optimize_bb_for_speed_p (const_basic_block bb)
307 return !optimize_bb_for_size_p (bb);
310 /* Return the optimization type that should be used for block BB. */
312 optimization_type
313 bb_optimization_type (const_basic_block bb)
315 return (optimize_bb_for_speed_p (bb)
316 ? OPTIMIZE_FOR_SPEED
317 : OPTIMIZE_FOR_SIZE);
320 /* Return TRUE when BB should be optimized for size. */
322 bool
323 optimize_edge_for_size_p (edge e)
325 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
328 /* Return TRUE when BB should be optimized for speed. */
330 bool
331 optimize_edge_for_speed_p (edge e)
333 return !optimize_edge_for_size_p (e);
336 /* Return TRUE when BB should be optimized for size. */
338 bool
339 optimize_insn_for_size_p (void)
341 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
344 /* Return TRUE when BB should be optimized for speed. */
346 bool
347 optimize_insn_for_speed_p (void)
349 return !optimize_insn_for_size_p ();
352 /* Return TRUE when LOOP should be optimized for size. */
354 bool
355 optimize_loop_for_size_p (struct loop *loop)
357 return optimize_bb_for_size_p (loop->header);
360 /* Return TRUE when LOOP should be optimized for speed. */
362 bool
363 optimize_loop_for_speed_p (struct loop *loop)
365 return optimize_bb_for_speed_p (loop->header);
368 /* Return TRUE when LOOP nest should be optimized for speed. */
370 bool
371 optimize_loop_nest_for_speed_p (struct loop *loop)
373 struct loop *l = loop;
374 if (optimize_loop_for_speed_p (loop))
375 return true;
376 l = loop->inner;
377 while (l && l != loop)
379 if (optimize_loop_for_speed_p (l))
380 return true;
381 if (l->inner)
382 l = l->inner;
383 else if (l->next)
384 l = l->next;
385 else
387 while (l != loop && !l->next)
388 l = loop_outer (l);
389 if (l != loop)
390 l = l->next;
393 return false;
396 /* Return TRUE when LOOP nest should be optimized for size. */
398 bool
399 optimize_loop_nest_for_size_p (struct loop *loop)
401 return !optimize_loop_nest_for_speed_p (loop);
404 /* Return true when edge E is likely to be well predictable by branch
405 predictor. */
407 bool
408 predictable_edge_p (edge e)
410 if (!e->probability.initialized_p ())
411 return false;
412 if ((e->probability.to_reg_br_prob_base ()
413 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
414 || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
415 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
416 return true;
417 return false;
421 /* Set RTL expansion for BB profile. */
423 void
424 rtl_profile_for_bb (basic_block bb)
426 crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
429 /* Set RTL expansion for edge profile. */
431 void
432 rtl_profile_for_edge (edge e)
434 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
437 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
438 void
439 default_rtl_profile (void)
441 crtl->maybe_hot_insn_p = true;
444 /* Return true if the one of outgoing edges is already predicted by
445 PREDICTOR. */
447 bool
448 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
450 rtx note;
451 if (!INSN_P (BB_END (bb)))
452 return false;
453 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
454 if (REG_NOTE_KIND (note) == REG_BR_PRED
455 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
456 return true;
457 return false;
460 /* Structure representing predictions in tree level. */
462 struct edge_prediction {
463 struct edge_prediction *ep_next;
464 edge ep_edge;
465 enum br_predictor ep_predictor;
466 int ep_probability;
469 /* This map contains for a basic block the list of predictions for the
470 outgoing edges. */
472 static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
474 /* Return true if the one of outgoing edges is already predicted by
475 PREDICTOR. */
477 bool
478 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
480 struct edge_prediction *i;
481 edge_prediction **preds = bb_predictions->get (bb);
483 if (!preds)
484 return false;
486 for (i = *preds; i; i = i->ep_next)
487 if (i->ep_predictor == predictor)
488 return true;
489 return false;
492 /* Return true if the one of outgoing edges is already predicted by
493 PREDICTOR for edge E predicted as TAKEN. */
495 bool
496 edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
498 struct edge_prediction *i;
499 basic_block bb = e->src;
500 edge_prediction **preds = bb_predictions->get (bb);
501 if (!preds)
502 return false;
504 int probability = predictor_info[(int) predictor].hitrate;
506 if (taken != TAKEN)
507 probability = REG_BR_PROB_BASE - probability;
509 for (i = *preds; i; i = i->ep_next)
510 if (i->ep_predictor == predictor
511 && i->ep_edge == e
512 && i->ep_probability == probability)
513 return true;
514 return false;
517 /* Same predicate as above, working on edges. */
518 bool
519 edge_probability_reliable_p (const_edge e)
521 return e->probability.probably_reliable_p ();
524 /* Same predicate as edge_probability_reliable_p, working on notes. */
525 bool
526 br_prob_note_reliable_p (const_rtx note)
528 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
529 return profile_probability::from_reg_br_prob_note
530 (XINT (note, 0)).probably_reliable_p ();
533 static void
534 predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
536 gcc_assert (any_condjump_p (insn));
537 if (!flag_guess_branch_prob)
538 return;
540 add_reg_note (insn, REG_BR_PRED,
541 gen_rtx_CONCAT (VOIDmode,
542 GEN_INT ((int) predictor),
543 GEN_INT ((int) probability)));
546 /* Predict insn by given predictor. */
548 void
549 predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
550 enum prediction taken)
552 int probability = predictor_info[(int) predictor].hitrate;
553 gcc_assert (probability != PROB_UNINITIALIZED);
555 if (taken != TAKEN)
556 probability = REG_BR_PROB_BASE - probability;
558 predict_insn (insn, predictor, probability);
561 /* Predict edge E with given probability if possible. */
563 void
564 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
566 rtx_insn *last_insn;
567 last_insn = BB_END (e->src);
569 /* We can store the branch prediction information only about
570 conditional jumps. */
571 if (!any_condjump_p (last_insn))
572 return;
574 /* We always store probability of branching. */
575 if (e->flags & EDGE_FALLTHRU)
576 probability = REG_BR_PROB_BASE - probability;
578 predict_insn (last_insn, predictor, probability);
581 /* Predict edge E with the given PROBABILITY. */
582 void
583 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
585 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
586 && EDGE_COUNT (e->src->succs) > 1
587 && flag_guess_branch_prob
588 && optimize)
590 struct edge_prediction *i = XNEW (struct edge_prediction);
591 edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
593 i->ep_next = preds;
594 preds = i;
595 i->ep_probability = probability;
596 i->ep_predictor = predictor;
597 i->ep_edge = e;
601 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
602 to the filter function. */
604 void
605 filter_predictions (edge_prediction **preds,
606 bool (*filter) (edge_prediction *, void *), void *data)
608 if (!bb_predictions)
609 return;
611 if (preds)
613 struct edge_prediction **prediction = preds;
614 struct edge_prediction *next;
616 while (*prediction)
618 if ((*filter) (*prediction, data))
619 prediction = &((*prediction)->ep_next);
620 else
622 next = (*prediction)->ep_next;
623 free (*prediction);
624 *prediction = next;
630 /* Filter function predicate that returns true for a edge predicate P
631 if its edge is equal to DATA. */
633 bool
634 equal_edge_p (edge_prediction *p, void *data)
636 return p->ep_edge == (edge)data;
639 /* Remove all predictions on given basic block that are attached
640 to edge E. */
641 void
642 remove_predictions_associated_with_edge (edge e)
644 if (!bb_predictions)
645 return;
647 edge_prediction **preds = bb_predictions->get (e->src);
648 filter_predictions (preds, equal_edge_p, e);
651 /* Clears the list of predictions stored for BB. */
653 static void
654 clear_bb_predictions (basic_block bb)
656 edge_prediction **preds = bb_predictions->get (bb);
657 struct edge_prediction *pred, *next;
659 if (!preds)
660 return;
662 for (pred = *preds; pred; pred = next)
664 next = pred->ep_next;
665 free (pred);
667 *preds = NULL;
670 /* Return true when we can store prediction on insn INSN.
671 At the moment we represent predictions only on conditional
672 jumps, not at computed jump or other complicated cases. */
673 static bool
674 can_predict_insn_p (const rtx_insn *insn)
676 return (JUMP_P (insn)
677 && any_condjump_p (insn)
678 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
681 /* Predict edge E by given predictor if possible. */
683 void
684 predict_edge_def (edge e, enum br_predictor predictor,
685 enum prediction taken)
687 int probability = predictor_info[(int) predictor].hitrate;
689 if (taken != TAKEN)
690 probability = REG_BR_PROB_BASE - probability;
692 predict_edge (e, predictor, probability);
695 /* Invert all branch predictions or probability notes in the INSN. This needs
696 to be done each time we invert the condition used by the jump. */
698 void
699 invert_br_probabilities (rtx insn)
701 rtx note;
703 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
704 if (REG_NOTE_KIND (note) == REG_BR_PROB)
705 XINT (note, 0) = profile_probability::from_reg_br_prob_note
706 (XINT (note, 0)).invert ().to_reg_br_prob_note ();
707 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
708 XEXP (XEXP (note, 0), 1)
709 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
712 /* Dump information about the branch prediction to the output file. */
714 static void
715 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
716 basic_block bb, enum predictor_reason reason = REASON_NONE,
717 edge ep_edge = NULL)
719 edge e = ep_edge;
720 edge_iterator ei;
722 if (!file)
723 return;
725 if (e == NULL)
726 FOR_EACH_EDGE (e, ei, bb->succs)
727 if (! (e->flags & EDGE_FALLTHRU))
728 break;
730 char edge_info_str[128];
731 if (ep_edge)
732 sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
733 ep_edge->dest->index);
734 else
735 edge_info_str[0] = '\0';
737 fprintf (file, " %s heuristics%s%s: %.1f%%",
738 predictor_info[predictor].name,
739 edge_info_str, reason_messages[reason],
740 probability * 100.0 / REG_BR_PROB_BASE);
742 if (bb->count.initialized_p ())
744 fprintf (file, " exec ");
745 bb->count.dump (file);
746 if (e)
748 fprintf (file, " hit ");
749 e->count ().dump (file);
750 fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
751 / bb->count.to_gcov_type ());
755 fprintf (file, "\n");
757 /* Print output that be easily read by analyze_brprob.py script. We are
758 interested only in counts that are read from GCDA files. */
759 if (dump_file && (dump_flags & TDF_DETAILS)
760 && bb->count.precise_p ()
761 && reason == REASON_NONE)
763 gcc_assert (e->count ().precise_p ());
764 fprintf (file, ";;heuristics;%s;%" PRId64 ";%" PRId64 ";%.1f;\n",
765 predictor_info[predictor].name,
766 bb->count.to_gcov_type (), e->count ().to_gcov_type (),
767 probability * 100.0 / REG_BR_PROB_BASE);
771 /* Return true if STMT is known to be unlikely executed. */
773 static bool
774 unlikely_executed_stmt_p (gimple *stmt)
776 if (!is_gimple_call (stmt))
777 return false;
778 /* NORETURN attribute alone is not strong enough: exit() may be quite
779 likely executed once during program run. */
780 if (gimple_call_fntype (stmt)
781 && lookup_attribute ("cold",
782 TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
783 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
784 return true;
785 tree decl = gimple_call_fndecl (stmt);
786 if (!decl)
787 return false;
788 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
789 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
790 return true;
792 cgraph_node *n = cgraph_node::get (decl);
793 if (!n)
794 return false;
796 availability avail;
797 n = n->ultimate_alias_target (&avail);
798 if (avail < AVAIL_AVAILABLE)
799 return false;
800 if (!n->analyzed
801 || n->decl == current_function_decl)
802 return false;
803 return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
806 /* Return true if BB is unlikely executed. */
808 static bool
809 unlikely_executed_bb_p (basic_block bb)
811 if (bb->count == profile_count::zero ())
812 return true;
813 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
814 return false;
815 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
816 !gsi_end_p (gsi); gsi_next (&gsi))
818 if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
819 return true;
820 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
821 return false;
823 return false;
826 /* We can not predict the probabilities of outgoing edges of bb. Set them
827 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
828 even probability for all edges not mentioned in the set. These edges
829 are given PROB_VERY_UNLIKELY probability. */
831 static void
832 set_even_probabilities (basic_block bb,
833 hash_set<edge> *unlikely_edges = NULL)
835 unsigned nedges = 0, unlikely_count = 0;
836 edge e = NULL;
837 edge_iterator ei;
838 profile_probability all = profile_probability::always ();
840 FOR_EACH_EDGE (e, ei, bb->succs)
841 if (e->probability.initialized_p ())
842 all -= e->probability;
843 else if (!unlikely_executed_edge_p (e))
845 nedges ++;
846 if (unlikely_edges != NULL && unlikely_edges->contains (e))
848 all -= profile_probability::very_unlikely ();
849 unlikely_count++;
853 /* Make the distribution even if all edges are unlikely. */
854 if (unlikely_count == nedges)
856 unlikely_edges = NULL;
857 unlikely_count = 0;
860 unsigned c = nedges - unlikely_count;
862 FOR_EACH_EDGE (e, ei, bb->succs)
863 if (e->probability.initialized_p ())
865 else if (!unlikely_executed_edge_p (e))
867 if (unlikely_edges != NULL && unlikely_edges->contains (e))
868 e->probability = profile_probability::very_unlikely ();
869 else
870 e->probability = all.apply_scale (1, c).guessed ();
872 else
873 e->probability = profile_probability::never ();
876 /* Add REG_BR_PROB note to JUMP with PROB. */
878 void
879 add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
881 gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
882 add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
885 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
886 note if not already present. Remove now useless REG_BR_PRED notes. */
888 static void
889 combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
891 rtx prob_note;
892 rtx *pnote;
893 rtx note;
894 int best_probability = PROB_EVEN;
895 enum br_predictor best_predictor = END_PREDICTORS;
896 int combined_probability = REG_BR_PROB_BASE / 2;
897 int d;
898 bool first_match = false;
899 bool found = false;
901 if (!can_predict_insn_p (insn))
903 set_even_probabilities (bb);
904 return;
907 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
908 pnote = &REG_NOTES (insn);
909 if (dump_file)
910 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
911 bb->index);
913 /* We implement "first match" heuristics and use probability guessed
914 by predictor with smallest index. */
915 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
916 if (REG_NOTE_KIND (note) == REG_BR_PRED)
918 enum br_predictor predictor = ((enum br_predictor)
919 INTVAL (XEXP (XEXP (note, 0), 0)));
920 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
922 found = true;
923 if (best_predictor > predictor
924 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
925 best_probability = probability, best_predictor = predictor;
927 d = (combined_probability * probability
928 + (REG_BR_PROB_BASE - combined_probability)
929 * (REG_BR_PROB_BASE - probability));
931 /* Use FP math to avoid overflows of 32bit integers. */
932 if (d == 0)
933 /* If one probability is 0% and one 100%, avoid division by zero. */
934 combined_probability = REG_BR_PROB_BASE / 2;
935 else
936 combined_probability = (((double) combined_probability) * probability
937 * REG_BR_PROB_BASE / d + 0.5);
940 /* Decide which heuristic to use. In case we didn't match anything,
941 use no_prediction heuristic, in case we did match, use either
942 first match or Dempster-Shaffer theory depending on the flags. */
944 if (best_predictor != END_PREDICTORS)
945 first_match = true;
947 if (!found)
948 dump_prediction (dump_file, PRED_NO_PREDICTION,
949 combined_probability, bb);
950 else
952 if (!first_match)
953 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
954 bb, !first_match ? REASON_NONE : REASON_IGNORED);
955 else
956 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
957 bb, first_match ? REASON_NONE : REASON_IGNORED);
960 if (first_match)
961 combined_probability = best_probability;
962 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
964 while (*pnote)
966 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
968 enum br_predictor predictor = ((enum br_predictor)
969 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
970 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
972 dump_prediction (dump_file, predictor, probability, bb,
973 (!first_match || best_predictor == predictor)
974 ? REASON_NONE : REASON_IGNORED);
975 *pnote = XEXP (*pnote, 1);
977 else
978 pnote = &XEXP (*pnote, 1);
981 if (!prob_note)
983 profile_probability p
984 = profile_probability::from_reg_br_prob_base (combined_probability);
985 add_reg_br_prob_note (insn, p);
987 /* Save the prediction into CFG in case we are seeing non-degenerated
988 conditional jump. */
989 if (!single_succ_p (bb))
991 BRANCH_EDGE (bb)->probability = p;
992 FALLTHRU_EDGE (bb)->probability
993 = BRANCH_EDGE (bb)->probability.invert ();
996 else if (!single_succ_p (bb))
998 profile_probability prob = profile_probability::from_reg_br_prob_note
999 (XINT (prob_note, 0));
1001 BRANCH_EDGE (bb)->probability = prob;
1002 FALLTHRU_EDGE (bb)->probability = prob.invert ();
1004 else
1005 single_succ_edge (bb)->probability = profile_probability::always ();
1008 /* Edge prediction hash traits. */
1010 struct predictor_hash: pointer_hash <edge_prediction>
1013 static inline hashval_t hash (const edge_prediction *);
1014 static inline bool equal (const edge_prediction *, const edge_prediction *);
1017 /* Calculate hash value of an edge prediction P based on predictor and
1018 normalized probability. */
1020 inline hashval_t
1021 predictor_hash::hash (const edge_prediction *p)
1023 inchash::hash hstate;
1024 hstate.add_int (p->ep_predictor);
1026 int prob = p->ep_probability;
1027 if (prob > REG_BR_PROB_BASE / 2)
1028 prob = REG_BR_PROB_BASE - prob;
1030 hstate.add_int (prob);
1032 return hstate.end ();
1035 /* Return true whether edge predictions P1 and P2 use the same predictor and
1036 have equal (or opposed probability). */
1038 inline bool
1039 predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1041 return (p1->ep_predictor == p2->ep_predictor
1042 && (p1->ep_probability == p2->ep_probability
1043 || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1046 struct predictor_hash_traits: predictor_hash,
1047 typed_noop_remove <edge_prediction *> {};
1049 /* Return true if edge prediction P is not in DATA hash set. */
1051 static bool
1052 not_removed_prediction_p (edge_prediction *p, void *data)
1054 hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1055 return !remove->contains (p);
1058 /* Prune predictions for a basic block BB. Currently we do following
1059 clean-up steps:
1061 1) remove duplicate prediction that is guessed with the same probability
1062 (different than 1/2) to both edge
1063 2) remove duplicates for a prediction that belongs with the same probability
1064 to a single edge
1068 static void
1069 prune_predictions_for_bb (basic_block bb)
1071 edge_prediction **preds = bb_predictions->get (bb);
1073 if (preds)
1075 hash_table <predictor_hash_traits> s (13);
1076 hash_set <edge_prediction *> remove;
1078 /* Step 1: identify predictors that should be removed. */
1079 for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1081 edge_prediction *existing = s.find (pred);
1082 if (existing)
1084 if (pred->ep_edge == existing->ep_edge
1085 && pred->ep_probability == existing->ep_probability)
1087 /* Remove a duplicate predictor. */
1088 dump_prediction (dump_file, pred->ep_predictor,
1089 pred->ep_probability, bb,
1090 REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1092 remove.add (pred);
1094 else if (pred->ep_edge != existing->ep_edge
1095 && pred->ep_probability == existing->ep_probability
1096 && pred->ep_probability != REG_BR_PROB_BASE / 2)
1098 /* Remove both predictors as they predict the same
1099 for both edges. */
1100 dump_prediction (dump_file, existing->ep_predictor,
1101 pred->ep_probability, bb,
1102 REASON_EDGE_PAIR_DUPLICATE,
1103 existing->ep_edge);
1104 dump_prediction (dump_file, pred->ep_predictor,
1105 pred->ep_probability, bb,
1106 REASON_EDGE_PAIR_DUPLICATE,
1107 pred->ep_edge);
1109 remove.add (existing);
1110 remove.add (pred);
1114 edge_prediction **slot2 = s.find_slot (pred, INSERT);
1115 *slot2 = pred;
1118 /* Step 2: Remove predictors. */
1119 filter_predictions (preds, not_removed_prediction_p, &remove);
1123 /* Combine predictions into single probability and store them into CFG.
1124 Remove now useless prediction entries.
1125 If DRY_RUN is set, only produce dumps and do not modify profile. */
1127 static void
1128 combine_predictions_for_bb (basic_block bb, bool dry_run)
1130 int best_probability = PROB_EVEN;
1131 enum br_predictor best_predictor = END_PREDICTORS;
1132 int combined_probability = REG_BR_PROB_BASE / 2;
1133 int d;
1134 bool first_match = false;
1135 bool found = false;
1136 struct edge_prediction *pred;
1137 int nedges = 0;
1138 edge e, first = NULL, second = NULL;
1139 edge_iterator ei;
1140 int nzero = 0;
1141 int nunknown = 0;
1143 FOR_EACH_EDGE (e, ei, bb->succs)
1145 if (!unlikely_executed_edge_p (e))
1147 nedges ++;
1148 if (first && !second)
1149 second = e;
1150 if (!first)
1151 first = e;
1153 else if (!e->probability.initialized_p ())
1154 e->probability = profile_probability::never ();
1155 if (!e->probability.initialized_p ())
1156 nunknown++;
1157 else if (e->probability == profile_probability::never ())
1158 nzero++;
1161 /* When there is no successor or only one choice, prediction is easy.
1163 When we have a basic block with more than 2 successors, the situation
1164 is more complicated as DS theory cannot be used literally.
1165 More precisely, let's assume we predicted edge e1 with probability p1,
1166 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1167 need to find probability of e.g. m1({b2}), which we don't know.
1168 The only approximation is to equally distribute 1-p1 to all edges
1169 different from b1.
1171 According to numbers we've got from SPEC2006 benchark, there's only
1172 one interesting reliable predictor (noreturn call), which can be
1173 handled with a bit easier approach. */
1174 if (nedges != 2)
1176 hash_set<edge> unlikely_edges (4);
1178 /* Identify all edges that have a probability close to very unlikely.
1179 Doing the approach for very unlikely doesn't worth for doing as
1180 there's no such probability in SPEC2006 benchmark. */
1181 edge_prediction **preds = bb_predictions->get (bb);
1182 if (preds)
1183 for (pred = *preds; pred; pred = pred->ep_next)
1184 if (pred->ep_probability <= PROB_VERY_UNLIKELY)
1185 unlikely_edges.add (pred->ep_edge);
1187 if (!dry_run)
1188 set_even_probabilities (bb, &unlikely_edges);
1189 clear_bb_predictions (bb);
1190 if (dump_file)
1192 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1193 if (unlikely_edges.elements () == 0)
1194 fprintf (dump_file,
1195 "%i edges in bb %i predicted to even probabilities\n",
1196 nedges, bb->index);
1197 else
1199 fprintf (dump_file,
1200 "%i edges in bb %i predicted with some unlikely edges\n",
1201 nedges, bb->index);
1202 FOR_EACH_EDGE (e, ei, bb->succs)
1203 if (!unlikely_executed_edge_p (e))
1204 dump_prediction (dump_file, PRED_COMBINED,
1205 e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
1208 return;
1211 if (dump_file)
1212 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1214 prune_predictions_for_bb (bb);
1216 edge_prediction **preds = bb_predictions->get (bb);
1218 if (preds)
1220 /* We implement "first match" heuristics and use probability guessed
1221 by predictor with smallest index. */
1222 for (pred = *preds; pred; pred = pred->ep_next)
1224 enum br_predictor predictor = pred->ep_predictor;
1225 int probability = pred->ep_probability;
1227 if (pred->ep_edge != first)
1228 probability = REG_BR_PROB_BASE - probability;
1230 found = true;
1231 /* First match heuristics would be widly confused if we predicted
1232 both directions. */
1233 if (best_predictor > predictor
1234 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1236 struct edge_prediction *pred2;
1237 int prob = probability;
1239 for (pred2 = (struct edge_prediction *) *preds;
1240 pred2; pred2 = pred2->ep_next)
1241 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1243 int probability2 = pred2->ep_probability;
1245 if (pred2->ep_edge != first)
1246 probability2 = REG_BR_PROB_BASE - probability2;
1248 if ((probability < REG_BR_PROB_BASE / 2) !=
1249 (probability2 < REG_BR_PROB_BASE / 2))
1250 break;
1252 /* If the same predictor later gave better result, go for it! */
1253 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1254 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1255 prob = probability2;
1257 if (!pred2)
1258 best_probability = prob, best_predictor = predictor;
1261 d = (combined_probability * probability
1262 + (REG_BR_PROB_BASE - combined_probability)
1263 * (REG_BR_PROB_BASE - probability));
1265 /* Use FP math to avoid overflows of 32bit integers. */
1266 if (d == 0)
1267 /* If one probability is 0% and one 100%, avoid division by zero. */
1268 combined_probability = REG_BR_PROB_BASE / 2;
1269 else
1270 combined_probability = (((double) combined_probability)
1271 * probability
1272 * REG_BR_PROB_BASE / d + 0.5);
1276 /* Decide which heuristic to use. In case we didn't match anything,
1277 use no_prediction heuristic, in case we did match, use either
1278 first match or Dempster-Shaffer theory depending on the flags. */
1280 if (best_predictor != END_PREDICTORS)
1281 first_match = true;
1283 if (!found)
1284 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1285 else
1287 if (!first_match)
1288 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1289 !first_match ? REASON_NONE : REASON_IGNORED);
1290 else
1291 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1292 first_match ? REASON_NONE : REASON_IGNORED);
1295 if (first_match)
1296 combined_probability = best_probability;
1297 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1299 if (preds)
1301 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1303 enum br_predictor predictor = pred->ep_predictor;
1304 int probability = pred->ep_probability;
1306 dump_prediction (dump_file, predictor, probability, bb,
1307 (!first_match || best_predictor == predictor)
1308 ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1311 clear_bb_predictions (bb);
1314 /* If we have only one successor which is unknown, we can compute missing
1315 probablity. */
1316 if (nunknown == 1)
1318 profile_probability prob = profile_probability::always ();
1319 edge missing = NULL;
1321 FOR_EACH_EDGE (e, ei, bb->succs)
1322 if (e->probability.initialized_p ())
1323 prob -= e->probability;
1324 else if (missing == NULL)
1325 missing = e;
1326 else
1327 gcc_unreachable ();
1328 missing->probability = prob;
1330 /* If nothing is unknown, we have nothing to update. */
1331 else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1333 else if (!dry_run)
1335 first->probability
1336 = profile_probability::from_reg_br_prob_base (combined_probability);
1337 second->probability = first->probability.invert ();
1341 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1342 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1344 T1 and T2 should be one of the following cases:
1345 1. T1 is SSA_NAME, T2 is NULL
1346 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1347 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1349 static tree
1350 strips_small_constant (tree t1, tree t2)
1352 tree ret = NULL;
1353 int value = 0;
1355 if (!t1)
1356 return NULL;
1357 else if (TREE_CODE (t1) == SSA_NAME)
1358 ret = t1;
1359 else if (tree_fits_shwi_p (t1))
1360 value = tree_to_shwi (t1);
1361 else
1362 return NULL;
1364 if (!t2)
1365 return ret;
1366 else if (tree_fits_shwi_p (t2))
1367 value = tree_to_shwi (t2);
1368 else if (TREE_CODE (t2) == SSA_NAME)
1370 if (ret)
1371 return NULL;
1372 else
1373 ret = t2;
1376 if (value <= 4 && value >= -4)
1377 return ret;
1378 else
1379 return NULL;
1382 /* Return the SSA_NAME in T or T's operands.
1383 Return NULL if SSA_NAME cannot be found. */
1385 static tree
1386 get_base_value (tree t)
1388 if (TREE_CODE (t) == SSA_NAME)
1389 return t;
1391 if (!BINARY_CLASS_P (t))
1392 return NULL;
1394 switch (TREE_OPERAND_LENGTH (t))
1396 case 1:
1397 return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1398 case 2:
1399 return strips_small_constant (TREE_OPERAND (t, 0),
1400 TREE_OPERAND (t, 1));
1401 default:
1402 return NULL;
1406 /* Check the compare STMT in LOOP. If it compares an induction
1407 variable to a loop invariant, return true, and save
1408 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1409 Otherwise return false and set LOOP_INVAIANT to NULL. */
1411 static bool
1412 is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
1413 tree *loop_invariant,
1414 enum tree_code *compare_code,
1415 tree *loop_step,
1416 tree *loop_iv_base)
1418 tree op0, op1, bound, base;
1419 affine_iv iv0, iv1;
1420 enum tree_code code;
1421 tree step;
1423 code = gimple_cond_code (stmt);
1424 *loop_invariant = NULL;
1426 switch (code)
1428 case GT_EXPR:
1429 case GE_EXPR:
1430 case NE_EXPR:
1431 case LT_EXPR:
1432 case LE_EXPR:
1433 case EQ_EXPR:
1434 break;
1436 default:
1437 return false;
1440 op0 = gimple_cond_lhs (stmt);
1441 op1 = gimple_cond_rhs (stmt);
1443 if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1444 || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1445 return false;
1446 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1447 return false;
1448 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1449 return false;
1450 if (TREE_CODE (iv0.step) != INTEGER_CST
1451 || TREE_CODE (iv1.step) != INTEGER_CST)
1452 return false;
1453 if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1454 || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1455 return false;
1457 if (integer_zerop (iv0.step))
1459 if (code != NE_EXPR && code != EQ_EXPR)
1460 code = invert_tree_comparison (code, false);
1461 bound = iv0.base;
1462 base = iv1.base;
1463 if (tree_fits_shwi_p (iv1.step))
1464 step = iv1.step;
1465 else
1466 return false;
1468 else
1470 bound = iv1.base;
1471 base = iv0.base;
1472 if (tree_fits_shwi_p (iv0.step))
1473 step = iv0.step;
1474 else
1475 return false;
1478 if (TREE_CODE (bound) != INTEGER_CST)
1479 bound = get_base_value (bound);
1480 if (!bound)
1481 return false;
1482 if (TREE_CODE (base) != INTEGER_CST)
1483 base = get_base_value (base);
1484 if (!base)
1485 return false;
1487 *loop_invariant = bound;
1488 *compare_code = code;
1489 *loop_step = step;
1490 *loop_iv_base = base;
1491 return true;
1494 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1496 static bool
1497 expr_coherent_p (tree t1, tree t2)
1499 gimple *stmt;
1500 tree ssa_name_1 = NULL;
1501 tree ssa_name_2 = NULL;
1503 gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1504 gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1506 if (t1 == t2)
1507 return true;
1509 if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1510 return true;
1511 if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1512 return false;
1514 /* Check to see if t1 is expressed/defined with t2. */
1515 stmt = SSA_NAME_DEF_STMT (t1);
1516 gcc_assert (stmt != NULL);
1517 if (is_gimple_assign (stmt))
1519 ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1520 if (ssa_name_1 && ssa_name_1 == t2)
1521 return true;
1524 /* Check to see if t2 is expressed/defined with t1. */
1525 stmt = SSA_NAME_DEF_STMT (t2);
1526 gcc_assert (stmt != NULL);
1527 if (is_gimple_assign (stmt))
1529 ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1530 if (ssa_name_2 && ssa_name_2 == t1)
1531 return true;
1534 /* Compare if t1 and t2's def_stmts are identical. */
1535 if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1536 return true;
1537 else
1538 return false;
1541 /* Return true if E is predicted by one of loop heuristics. */
1543 static bool
1544 predicted_by_loop_heuristics_p (basic_block bb)
1546 struct edge_prediction *i;
1547 edge_prediction **preds = bb_predictions->get (bb);
1549 if (!preds)
1550 return false;
1552 for (i = *preds; i; i = i->ep_next)
1553 if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1554 || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1555 || i->ep_predictor == PRED_LOOP_ITERATIONS
1556 || i->ep_predictor == PRED_LOOP_EXIT
1557 || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1558 || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1559 return true;
1560 return false;
1563 /* Predict branch probability of BB when BB contains a branch that compares
1564 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1565 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1567 E.g.
1568 for (int i = 0; i < bound; i++) {
1569 if (i < bound - 2)
1570 computation_1();
1571 else
1572 computation_2();
1575 In this loop, we will predict the branch inside the loop to be taken. */
1577 static void
1578 predict_iv_comparison (struct loop *loop, basic_block bb,
1579 tree loop_bound_var,
1580 tree loop_iv_base_var,
1581 enum tree_code loop_bound_code,
1582 int loop_bound_step)
1584 gimple *stmt;
1585 tree compare_var, compare_base;
1586 enum tree_code compare_code;
1587 tree compare_step_var;
1588 edge then_edge;
1589 edge_iterator ei;
1591 if (predicted_by_loop_heuristics_p (bb))
1592 return;
1594 stmt = last_stmt (bb);
1595 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1596 return;
1597 if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
1598 loop, &compare_var,
1599 &compare_code,
1600 &compare_step_var,
1601 &compare_base))
1602 return;
1604 /* Find the taken edge. */
1605 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1606 if (then_edge->flags & EDGE_TRUE_VALUE)
1607 break;
1609 /* When comparing an IV to a loop invariant, NE is more likely to be
1610 taken while EQ is more likely to be not-taken. */
1611 if (compare_code == NE_EXPR)
1613 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1614 return;
1616 else if (compare_code == EQ_EXPR)
1618 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1619 return;
1622 if (!expr_coherent_p (loop_iv_base_var, compare_base))
1623 return;
1625 /* If loop bound, base and compare bound are all constants, we can
1626 calculate the probability directly. */
1627 if (tree_fits_shwi_p (loop_bound_var)
1628 && tree_fits_shwi_p (compare_var)
1629 && tree_fits_shwi_p (compare_base))
1631 int probability;
1632 bool overflow, overall_overflow = false;
1633 widest_int compare_count, tem;
1635 /* (loop_bound - base) / compare_step */
1636 tem = wi::sub (wi::to_widest (loop_bound_var),
1637 wi::to_widest (compare_base), SIGNED, &overflow);
1638 overall_overflow |= overflow;
1639 widest_int loop_count = wi::div_trunc (tem,
1640 wi::to_widest (compare_step_var),
1641 SIGNED, &overflow);
1642 overall_overflow |= overflow;
1644 if (!wi::neg_p (wi::to_widest (compare_step_var))
1645 ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1647 /* (loop_bound - compare_bound) / compare_step */
1648 tem = wi::sub (wi::to_widest (loop_bound_var),
1649 wi::to_widest (compare_var), SIGNED, &overflow);
1650 overall_overflow |= overflow;
1651 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1652 SIGNED, &overflow);
1653 overall_overflow |= overflow;
1655 else
1657 /* (compare_bound - base) / compare_step */
1658 tem = wi::sub (wi::to_widest (compare_var),
1659 wi::to_widest (compare_base), SIGNED, &overflow);
1660 overall_overflow |= overflow;
1661 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1662 SIGNED, &overflow);
1663 overall_overflow |= overflow;
1665 if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1666 ++compare_count;
1667 if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1668 ++loop_count;
1669 if (wi::neg_p (compare_count))
1670 compare_count = 0;
1671 if (wi::neg_p (loop_count))
1672 loop_count = 0;
1673 if (loop_count == 0)
1674 probability = 0;
1675 else if (wi::cmps (compare_count, loop_count) == 1)
1676 probability = REG_BR_PROB_BASE;
1677 else
1679 tem = compare_count * REG_BR_PROB_BASE;
1680 tem = wi::udiv_trunc (tem, loop_count);
1681 probability = tem.to_uhwi ();
1684 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1685 if (!overall_overflow)
1686 predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1688 return;
1691 if (expr_coherent_p (loop_bound_var, compare_var))
1693 if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1694 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1695 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1696 else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1697 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1698 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1699 else if (loop_bound_code == NE_EXPR)
1701 /* If the loop backedge condition is "(i != bound)", we do
1702 the comparison based on the step of IV:
1703 * step < 0 : backedge condition is like (i > bound)
1704 * step > 0 : backedge condition is like (i < bound) */
1705 gcc_assert (loop_bound_step != 0);
1706 if (loop_bound_step > 0
1707 && (compare_code == LT_EXPR
1708 || compare_code == LE_EXPR))
1709 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1710 else if (loop_bound_step < 0
1711 && (compare_code == GT_EXPR
1712 || compare_code == GE_EXPR))
1713 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1714 else
1715 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1717 else
1718 /* The branch is predicted not-taken if loop_bound_code is
1719 opposite with compare_code. */
1720 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1722 else if (expr_coherent_p (loop_iv_base_var, compare_var))
1724 /* For cases like:
1725 for (i = s; i < h; i++)
1726 if (i > s + 2) ....
1727 The branch should be predicted taken. */
1728 if (loop_bound_step > 0
1729 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1730 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1731 else if (loop_bound_step < 0
1732 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1733 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1734 else
1735 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1739 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1740 exits are resulted from short-circuit conditions that will generate an
1741 if_tmp. E.g.:
1743 if (foo() || global > 10)
1744 break;
1746 This will be translated into:
1748 BB3:
1749 loop header...
1750 BB4:
1751 if foo() goto BB6 else goto BB5
1752 BB5:
1753 if global > 10 goto BB6 else goto BB7
1754 BB6:
1755 goto BB7
1756 BB7:
1757 iftmp = (PHI 0(BB5), 1(BB6))
1758 if iftmp == 1 goto BB8 else goto BB3
1759 BB8:
1760 outside of the loop...
1762 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1763 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1764 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1765 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1767 static void
1768 predict_extra_loop_exits (edge exit_edge)
1770 unsigned i;
1771 bool check_value_one;
1772 gimple *lhs_def_stmt;
1773 gphi *phi_stmt;
1774 tree cmp_rhs, cmp_lhs;
1775 gimple *last;
1776 gcond *cmp_stmt;
1778 last = last_stmt (exit_edge->src);
1779 if (!last)
1780 return;
1781 cmp_stmt = dyn_cast <gcond *> (last);
1782 if (!cmp_stmt)
1783 return;
1785 cmp_rhs = gimple_cond_rhs (cmp_stmt);
1786 cmp_lhs = gimple_cond_lhs (cmp_stmt);
1787 if (!TREE_CONSTANT (cmp_rhs)
1788 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1789 return;
1790 if (TREE_CODE (cmp_lhs) != SSA_NAME)
1791 return;
1793 /* If check_value_one is true, only the phi_args with value '1' will lead
1794 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1795 loop exit. */
1796 check_value_one = (((integer_onep (cmp_rhs))
1797 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1798 ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1800 lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1801 if (!lhs_def_stmt)
1802 return;
1804 phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1805 if (!phi_stmt)
1806 return;
1808 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1810 edge e1;
1811 edge_iterator ei;
1812 tree val = gimple_phi_arg_def (phi_stmt, i);
1813 edge e = gimple_phi_arg_edge (phi_stmt, i);
1815 if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1816 continue;
1817 if ((check_value_one ^ integer_onep (val)) == 1)
1818 continue;
1819 if (EDGE_COUNT (e->src->succs) != 1)
1821 predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1822 continue;
1825 FOR_EACH_EDGE (e1, ei, e->src->preds)
1826 predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1831 /* Predict edge probabilities by exploiting loop structure. */
1833 static void
1834 predict_loops (void)
1836 struct loop *loop;
1837 basic_block bb;
1838 hash_set <struct loop *> with_recursion(10);
1840 FOR_EACH_BB_FN (bb, cfun)
1842 gimple_stmt_iterator gsi;
1843 tree decl;
1845 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1846 if (is_gimple_call (gsi_stmt (gsi))
1847 && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1848 && recursive_call_p (current_function_decl, decl))
1850 loop = bb->loop_father;
1851 while (loop && !with_recursion.add (loop))
1852 loop = loop_outer (loop);
1856 /* Try to predict out blocks in a loop that are not part of a
1857 natural loop. */
1858 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1860 basic_block bb, *bbs;
1861 unsigned j, n_exits = 0;
1862 vec<edge> exits;
1863 struct tree_niter_desc niter_desc;
1864 edge ex;
1865 struct nb_iter_bound *nb_iter;
1866 enum tree_code loop_bound_code = ERROR_MARK;
1867 tree loop_bound_step = NULL;
1868 tree loop_bound_var = NULL;
1869 tree loop_iv_base = NULL;
1870 gcond *stmt = NULL;
1871 bool recursion = with_recursion.contains (loop);
1873 exits = get_loop_exit_edges (loop);
1874 FOR_EACH_VEC_ELT (exits, j, ex)
1875 if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
1876 n_exits ++;
1877 if (!n_exits)
1879 exits.release ();
1880 continue;
1883 if (dump_file && (dump_flags & TDF_DETAILS))
1884 fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
1885 loop->num, recursion ? " (with recursion)":"", n_exits);
1886 if (dump_file && (dump_flags & TDF_DETAILS)
1887 && max_loop_iterations_int (loop) >= 0)
1889 fprintf (dump_file,
1890 "Loop %d iterates at most %i times.\n", loop->num,
1891 (int)max_loop_iterations_int (loop));
1893 if (dump_file && (dump_flags & TDF_DETAILS)
1894 && likely_max_loop_iterations_int (loop) >= 0)
1896 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1897 loop->num, (int)likely_max_loop_iterations_int (loop));
1900 FOR_EACH_VEC_ELT (exits, j, ex)
1902 tree niter = NULL;
1903 HOST_WIDE_INT nitercst;
1904 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
1905 int probability;
1906 enum br_predictor predictor;
1907 widest_int nit;
1909 if (unlikely_executed_edge_p (ex)
1910 || (ex->flags & EDGE_ABNORMAL_CALL))
1911 continue;
1912 /* Loop heuristics do not expect exit conditional to be inside
1913 inner loop. We predict from innermost to outermost loop. */
1914 if (predicted_by_loop_heuristics_p (ex->src))
1916 if (dump_file && (dump_flags & TDF_DETAILS))
1917 fprintf (dump_file, "Skipping exit %i->%i because "
1918 "it is already predicted.\n",
1919 ex->src->index, ex->dest->index);
1920 continue;
1922 predict_extra_loop_exits (ex);
1924 if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
1925 niter = niter_desc.niter;
1926 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
1927 niter = loop_niter_by_eval (loop, ex);
1928 if (dump_file && (dump_flags & TDF_DETAILS)
1929 && TREE_CODE (niter) == INTEGER_CST)
1931 fprintf (dump_file, "Exit %i->%i %d iterates ",
1932 ex->src->index, ex->dest->index,
1933 loop->num);
1934 print_generic_expr (dump_file, niter, TDF_SLIM);
1935 fprintf (dump_file, " times.\n");
1938 if (TREE_CODE (niter) == INTEGER_CST)
1940 if (tree_fits_uhwi_p (niter)
1941 && max
1942 && compare_tree_int (niter, max - 1) == -1)
1943 nitercst = tree_to_uhwi (niter) + 1;
1944 else
1945 nitercst = max;
1946 predictor = PRED_LOOP_ITERATIONS;
1948 /* If we have just one exit and we can derive some information about
1949 the number of iterations of the loop from the statements inside
1950 the loop, use it to predict this exit. */
1951 else if (n_exits == 1
1952 && estimated_stmt_executions (loop, &nit))
1954 if (wi::gtu_p (nit, max))
1955 nitercst = max;
1956 else
1957 nitercst = nit.to_shwi ();
1958 predictor = PRED_LOOP_ITERATIONS_GUESSED;
1960 /* If we have likely upper bound, trust it for very small iteration
1961 counts. Such loops would otherwise get mispredicted by standard
1962 LOOP_EXIT heuristics. */
1963 else if (n_exits == 1
1964 && likely_max_stmt_executions (loop, &nit)
1965 && wi::ltu_p (nit,
1966 RDIV (REG_BR_PROB_BASE,
1967 REG_BR_PROB_BASE
1968 - predictor_info
1969 [recursion
1970 ? PRED_LOOP_EXIT_WITH_RECURSION
1971 : PRED_LOOP_EXIT].hitrate)))
1973 nitercst = nit.to_shwi ();
1974 predictor = PRED_LOOP_ITERATIONS_MAX;
1976 else
1978 if (dump_file && (dump_flags & TDF_DETAILS))
1979 fprintf (dump_file, "Nothing known about exit %i->%i.\n",
1980 ex->src->index, ex->dest->index);
1981 continue;
1984 if (dump_file && (dump_flags & TDF_DETAILS))
1985 fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
1986 (int)nitercst, predictor_info[predictor].name);
1987 /* If the prediction for number of iterations is zero, do not
1988 predict the exit edges. */
1989 if (nitercst == 0)
1990 continue;
1992 probability = RDIV (REG_BR_PROB_BASE, nitercst);
1993 predict_edge (ex, predictor, probability);
1995 exits.release ();
1997 /* Find information about loop bound variables. */
1998 for (nb_iter = loop->bounds; nb_iter;
1999 nb_iter = nb_iter->next)
2000 if (nb_iter->stmt
2001 && gimple_code (nb_iter->stmt) == GIMPLE_COND)
2003 stmt = as_a <gcond *> (nb_iter->stmt);
2004 break;
2006 if (!stmt && last_stmt (loop->header)
2007 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
2008 stmt = as_a <gcond *> (last_stmt (loop->header));
2009 if (stmt)
2010 is_comparison_with_loop_invariant_p (stmt, loop,
2011 &loop_bound_var,
2012 &loop_bound_code,
2013 &loop_bound_step,
2014 &loop_iv_base);
2016 bbs = get_loop_body (loop);
2018 for (j = 0; j < loop->num_nodes; j++)
2020 edge e;
2021 edge_iterator ei;
2023 bb = bbs[j];
2025 /* Bypass loop heuristics on continue statement. These
2026 statements construct loops via "non-loop" constructs
2027 in the source language and are better to be handled
2028 separately. */
2029 if (predicted_by_p (bb, PRED_CONTINUE))
2031 if (dump_file && (dump_flags & TDF_DETAILS))
2032 fprintf (dump_file, "BB %i predicted by continue.\n",
2033 bb->index);
2034 continue;
2037 /* If we already used more reliable loop exit predictors, do not
2038 bother with PRED_LOOP_EXIT. */
2039 if (!predicted_by_loop_heuristics_p (bb))
2041 /* For loop with many exits we don't want to predict all exits
2042 with the pretty large probability, because if all exits are
2043 considered in row, the loop would be predicted to iterate
2044 almost never. The code to divide probability by number of
2045 exits is very rough. It should compute the number of exits
2046 taken in each patch through function (not the overall number
2047 of exits that might be a lot higher for loops with wide switch
2048 statements in them) and compute n-th square root.
2050 We limit the minimal probability by 2% to avoid
2051 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2052 as this was causing regression in perl benchmark containing such
2053 a wide loop. */
2055 int probability = ((REG_BR_PROB_BASE
2056 - predictor_info
2057 [recursion
2058 ? PRED_LOOP_EXIT_WITH_RECURSION
2059 : PRED_LOOP_EXIT].hitrate)
2060 / n_exits);
2061 if (probability < HITRATE (2))
2062 probability = HITRATE (2);
2063 FOR_EACH_EDGE (e, ei, bb->succs)
2064 if (e->dest->index < NUM_FIXED_BLOCKS
2065 || !flow_bb_inside_loop_p (loop, e->dest))
2067 if (dump_file && (dump_flags & TDF_DETAILS))
2068 fprintf (dump_file,
2069 "Predicting exit %i->%i with prob %i.\n",
2070 e->src->index, e->dest->index, probability);
2071 predict_edge (e,
2072 recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2073 : PRED_LOOP_EXIT, probability);
2076 if (loop_bound_var)
2077 predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2078 loop_bound_code,
2079 tree_to_shwi (loop_bound_step));
2082 /* In the following code
2083 for (loop1)
2084 if (cond)
2085 for (loop2)
2086 body;
2087 guess that cond is unlikely. */
2088 if (loop_outer (loop)->num)
2090 basic_block bb = NULL;
2091 edge preheader_edge = loop_preheader_edge (loop);
2093 if (single_pred_p (preheader_edge->src)
2094 && single_succ_p (preheader_edge->src))
2095 preheader_edge = single_pred_edge (preheader_edge->src);
2097 gimple *stmt = last_stmt (preheader_edge->src);
2098 /* Pattern match fortran loop preheader:
2099 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2100 _17 = (logical(kind=4)) _16;
2101 if (_17 != 0)
2102 goto <bb 11>;
2103 else
2104 goto <bb 13>;
2106 Loop guard branch prediction says nothing about duplicated loop
2107 headers produced by fortran frontend and in this case we want
2108 to predict paths leading to this preheader. */
2110 if (stmt
2111 && gimple_code (stmt) == GIMPLE_COND
2112 && gimple_cond_code (stmt) == NE_EXPR
2113 && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2114 && integer_zerop (gimple_cond_rhs (stmt)))
2116 gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2117 if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2118 && gimple_expr_code (call_stmt) == NOP_EXPR
2119 && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2120 call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2121 if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
2122 && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2123 && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
2124 && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
2125 == PRED_FORTRAN_LOOP_PREHEADER)
2126 bb = preheader_edge->src;
2128 if (!bb)
2130 if (!dominated_by_p (CDI_DOMINATORS,
2131 loop_outer (loop)->latch, loop->header))
2132 predict_paths_leading_to_edge (loop_preheader_edge (loop),
2133 recursion
2134 ? PRED_LOOP_GUARD_WITH_RECURSION
2135 : PRED_LOOP_GUARD,
2136 NOT_TAKEN,
2137 loop_outer (loop));
2139 else
2141 if (!dominated_by_p (CDI_DOMINATORS,
2142 loop_outer (loop)->latch, bb))
2143 predict_paths_leading_to (bb,
2144 recursion
2145 ? PRED_LOOP_GUARD_WITH_RECURSION
2146 : PRED_LOOP_GUARD,
2147 NOT_TAKEN,
2148 loop_outer (loop));
2152 /* Free basic blocks from get_loop_body. */
2153 free (bbs);
2157 /* Attempt to predict probabilities of BB outgoing edges using local
2158 properties. */
2159 static void
2160 bb_estimate_probability_locally (basic_block bb)
2162 rtx_insn *last_insn = BB_END (bb);
2163 rtx cond;
2165 if (! can_predict_insn_p (last_insn))
2166 return;
2167 cond = get_condition (last_insn, NULL, false, false);
2168 if (! cond)
2169 return;
2171 /* Try "pointer heuristic."
2172 A comparison ptr == 0 is predicted as false.
2173 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2174 if (COMPARISON_P (cond)
2175 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2176 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2178 if (GET_CODE (cond) == EQ)
2179 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2180 else if (GET_CODE (cond) == NE)
2181 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2183 else
2185 /* Try "opcode heuristic."
2186 EQ tests are usually false and NE tests are usually true. Also,
2187 most quantities are positive, so we can make the appropriate guesses
2188 about signed comparisons against zero. */
2189 switch (GET_CODE (cond))
2191 case CONST_INT:
2192 /* Unconditional branch. */
2193 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2194 cond == const0_rtx ? NOT_TAKEN : TAKEN);
2195 break;
2197 case EQ:
2198 case UNEQ:
2199 /* Floating point comparisons appears to behave in a very
2200 unpredictable way because of special role of = tests in
2201 FP code. */
2202 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2204 /* Comparisons with 0 are often used for booleans and there is
2205 nothing useful to predict about them. */
2206 else if (XEXP (cond, 1) == const0_rtx
2207 || XEXP (cond, 0) == const0_rtx)
2209 else
2210 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2211 break;
2213 case NE:
2214 case LTGT:
2215 /* Floating point comparisons appears to behave in a very
2216 unpredictable way because of special role of = tests in
2217 FP code. */
2218 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2220 /* Comparisons with 0 are often used for booleans and there is
2221 nothing useful to predict about them. */
2222 else if (XEXP (cond, 1) == const0_rtx
2223 || XEXP (cond, 0) == const0_rtx)
2225 else
2226 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2227 break;
2229 case ORDERED:
2230 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2231 break;
2233 case UNORDERED:
2234 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2235 break;
2237 case LE:
2238 case LT:
2239 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2240 || XEXP (cond, 1) == constm1_rtx)
2241 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2242 break;
2244 case GE:
2245 case GT:
2246 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2247 || XEXP (cond, 1) == constm1_rtx)
2248 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2249 break;
2251 default:
2252 break;
2256 /* Set edge->probability for each successor edge of BB. */
2257 void
2258 guess_outgoing_edge_probabilities (basic_block bb)
2260 bb_estimate_probability_locally (bb);
2261 combine_predictions_for_insn (BB_END (bb), bb);
2264 static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
2266 /* Helper function for expr_expected_value. */
2268 static tree
2269 expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2270 tree op1, bitmap visited, enum br_predictor *predictor)
2272 gimple *def;
2274 if (predictor)
2275 *predictor = PRED_UNCONDITIONAL;
2277 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2279 if (TREE_CONSTANT (op0))
2280 return op0;
2282 if (code == IMAGPART_EXPR)
2284 if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2286 def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2287 if (is_gimple_call (def)
2288 && gimple_call_internal_p (def)
2289 && (gimple_call_internal_fn (def)
2290 == IFN_ATOMIC_COMPARE_EXCHANGE))
2292 /* Assume that any given atomic operation has low contention,
2293 and thus the compare-and-swap operation succeeds. */
2294 if (predictor)
2295 *predictor = PRED_COMPARE_AND_SWAP;
2296 return build_one_cst (TREE_TYPE (op0));
2301 if (code != SSA_NAME)
2302 return NULL_TREE;
2304 def = SSA_NAME_DEF_STMT (op0);
2306 /* If we were already here, break the infinite cycle. */
2307 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
2308 return NULL;
2310 if (gimple_code (def) == GIMPLE_PHI)
2312 /* All the arguments of the PHI node must have the same constant
2313 length. */
2314 int i, n = gimple_phi_num_args (def);
2315 tree val = NULL, new_val;
2317 for (i = 0; i < n; i++)
2319 tree arg = PHI_ARG_DEF (def, i);
2320 enum br_predictor predictor2;
2322 /* If this PHI has itself as an argument, we cannot
2323 determine the string length of this argument. However,
2324 if we can find an expected constant value for the other
2325 PHI args then we can still be sure that this is
2326 likely a constant. So be optimistic and just
2327 continue with the next argument. */
2328 if (arg == PHI_RESULT (def))
2329 continue;
2331 new_val = expr_expected_value (arg, visited, &predictor2);
2333 /* It is difficult to combine value predictors. Simply assume
2334 that later predictor is weaker and take its prediction. */
2335 if (predictor && *predictor < predictor2)
2336 *predictor = predictor2;
2337 if (!new_val)
2338 return NULL;
2339 if (!val)
2340 val = new_val;
2341 else if (!operand_equal_p (val, new_val, false))
2342 return NULL;
2344 return val;
2346 if (is_gimple_assign (def))
2348 if (gimple_assign_lhs (def) != op0)
2349 return NULL;
2351 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2352 gimple_assign_rhs1 (def),
2353 gimple_assign_rhs_code (def),
2354 gimple_assign_rhs2 (def),
2355 visited, predictor);
2358 if (is_gimple_call (def))
2360 tree decl = gimple_call_fndecl (def);
2361 if (!decl)
2363 if (gimple_call_internal_p (def)
2364 && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2366 gcc_assert (gimple_call_num_args (def) == 3);
2367 tree val = gimple_call_arg (def, 0);
2368 if (TREE_CONSTANT (val))
2369 return val;
2370 if (predictor)
2372 tree val2 = gimple_call_arg (def, 2);
2373 gcc_assert (TREE_CODE (val2) == INTEGER_CST
2374 && tree_fits_uhwi_p (val2)
2375 && tree_to_uhwi (val2) < END_PREDICTORS);
2376 *predictor = (enum br_predictor) tree_to_uhwi (val2);
2378 return gimple_call_arg (def, 1);
2380 return NULL;
2382 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2383 switch (DECL_FUNCTION_CODE (decl))
2385 case BUILT_IN_EXPECT:
2387 tree val;
2388 if (gimple_call_num_args (def) != 2)
2389 return NULL;
2390 val = gimple_call_arg (def, 0);
2391 if (TREE_CONSTANT (val))
2392 return val;
2393 if (predictor)
2394 *predictor = PRED_BUILTIN_EXPECT;
2395 return gimple_call_arg (def, 1);
2398 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2399 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2400 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2401 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2402 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2403 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2404 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2405 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2406 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2407 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2408 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2409 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2410 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2411 /* Assume that any given atomic operation has low contention,
2412 and thus the compare-and-swap operation succeeds. */
2413 if (predictor)
2414 *predictor = PRED_COMPARE_AND_SWAP;
2415 return boolean_true_node;
2416 default:
2417 break;
2421 return NULL;
2424 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2426 tree res;
2427 enum br_predictor predictor2;
2428 op0 = expr_expected_value (op0, visited, predictor);
2429 if (!op0)
2430 return NULL;
2431 op1 = expr_expected_value (op1, visited, &predictor2);
2432 if (predictor && *predictor < predictor2)
2433 *predictor = predictor2;
2434 if (!op1)
2435 return NULL;
2436 res = fold_build2 (code, type, op0, op1);
2437 if (TREE_CONSTANT (res))
2438 return res;
2439 return NULL;
2441 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2443 tree res;
2444 op0 = expr_expected_value (op0, visited, predictor);
2445 if (!op0)
2446 return NULL;
2447 res = fold_build1 (code, type, op0);
2448 if (TREE_CONSTANT (res))
2449 return res;
2450 return NULL;
2452 return NULL;
2455 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2456 The function is used by builtin_expect branch predictor so the evidence
2457 must come from this construct and additional possible constant folding.
2459 We may want to implement more involved value guess (such as value range
2460 propagation based prediction), but such tricks shall go to new
2461 implementation. */
2463 static tree
2464 expr_expected_value (tree expr, bitmap visited,
2465 enum br_predictor *predictor)
2467 enum tree_code code;
2468 tree op0, op1;
2470 if (TREE_CONSTANT (expr))
2472 if (predictor)
2473 *predictor = PRED_UNCONDITIONAL;
2474 return expr;
2477 extract_ops_from_tree (expr, &code, &op0, &op1);
2478 return expr_expected_value_1 (TREE_TYPE (expr),
2479 op0, code, op1, visited, predictor);
2482 /* Predict using opcode of the last statement in basic block. */
2483 static void
2484 tree_predict_by_opcode (basic_block bb)
2486 gimple *stmt = last_stmt (bb);
2487 edge then_edge;
2488 tree op0, op1;
2489 tree type;
2490 tree val;
2491 enum tree_code cmp;
2492 edge_iterator ei;
2493 enum br_predictor predictor;
2495 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
2496 return;
2497 FOR_EACH_EDGE (then_edge, ei, bb->succs)
2498 if (then_edge->flags & EDGE_TRUE_VALUE)
2499 break;
2500 op0 = gimple_cond_lhs (stmt);
2501 op1 = gimple_cond_rhs (stmt);
2502 cmp = gimple_cond_code (stmt);
2503 type = TREE_TYPE (op0);
2504 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
2505 &predictor);
2506 if (val && TREE_CODE (val) == INTEGER_CST)
2508 if (predictor == PRED_BUILTIN_EXPECT)
2510 int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
2512 gcc_assert (percent >= 0 && percent <= 100);
2513 if (integer_zerop (val))
2514 percent = 100 - percent;
2515 predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
2517 else
2518 predict_edge_def (then_edge, predictor,
2519 integer_zerop (val) ? NOT_TAKEN : TAKEN);
2521 /* Try "pointer heuristic."
2522 A comparison ptr == 0 is predicted as false.
2523 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2524 if (POINTER_TYPE_P (type))
2526 if (cmp == EQ_EXPR)
2527 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2528 else if (cmp == NE_EXPR)
2529 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2531 else
2533 /* Try "opcode heuristic."
2534 EQ tests are usually false and NE tests are usually true. Also,
2535 most quantities are positive, so we can make the appropriate guesses
2536 about signed comparisons against zero. */
2537 switch (cmp)
2539 case EQ_EXPR:
2540 case UNEQ_EXPR:
2541 /* Floating point comparisons appears to behave in a very
2542 unpredictable way because of special role of = tests in
2543 FP code. */
2544 if (FLOAT_TYPE_P (type))
2546 /* Comparisons with 0 are often used for booleans and there is
2547 nothing useful to predict about them. */
2548 else if (integer_zerop (op0) || integer_zerop (op1))
2550 else
2551 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2552 break;
2554 case NE_EXPR:
2555 case LTGT_EXPR:
2556 /* Floating point comparisons appears to behave in a very
2557 unpredictable way because of special role of = tests in
2558 FP code. */
2559 if (FLOAT_TYPE_P (type))
2561 /* Comparisons with 0 are often used for booleans and there is
2562 nothing useful to predict about them. */
2563 else if (integer_zerop (op0)
2564 || integer_zerop (op1))
2566 else
2567 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2568 break;
2570 case ORDERED_EXPR:
2571 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2572 break;
2574 case UNORDERED_EXPR:
2575 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2576 break;
2578 case LE_EXPR:
2579 case LT_EXPR:
2580 if (integer_zerop (op1)
2581 || integer_onep (op1)
2582 || integer_all_onesp (op1)
2583 || real_zerop (op1)
2584 || real_onep (op1)
2585 || real_minus_onep (op1))
2586 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2587 break;
2589 case GE_EXPR:
2590 case GT_EXPR:
2591 if (integer_zerop (op1)
2592 || integer_onep (op1)
2593 || integer_all_onesp (op1)
2594 || real_zerop (op1)
2595 || real_onep (op1)
2596 || real_minus_onep (op1))
2597 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2598 break;
2600 default:
2601 break;
2605 /* Returns TRUE if the STMT is exit(0) like statement. */
2607 static bool
2608 is_exit_with_zero_arg (const gimple *stmt)
2610 /* This is not exit, _exit or _Exit. */
2611 if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2612 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2613 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2614 return false;
2616 /* Argument is an interger zero. */
2617 return integer_zerop (gimple_call_arg (stmt, 0));
2620 /* Try to guess whether the value of return means error code. */
2622 static enum br_predictor
2623 return_prediction (tree val, enum prediction *prediction)
2625 /* VOID. */
2626 if (!val)
2627 return PRED_NO_PREDICTION;
2628 /* Different heuristics for pointers and scalars. */
2629 if (POINTER_TYPE_P (TREE_TYPE (val)))
2631 /* NULL is usually not returned. */
2632 if (integer_zerop (val))
2634 *prediction = NOT_TAKEN;
2635 return PRED_NULL_RETURN;
2638 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2640 /* Negative return values are often used to indicate
2641 errors. */
2642 if (TREE_CODE (val) == INTEGER_CST
2643 && tree_int_cst_sgn (val) < 0)
2645 *prediction = NOT_TAKEN;
2646 return PRED_NEGATIVE_RETURN;
2648 /* Constant return values seems to be commonly taken.
2649 Zero/one often represent booleans so exclude them from the
2650 heuristics. */
2651 if (TREE_CONSTANT (val)
2652 && (!integer_zerop (val) && !integer_onep (val)))
2654 *prediction = NOT_TAKEN;
2655 return PRED_CONST_RETURN;
2658 return PRED_NO_PREDICTION;
2661 /* Return zero if phi result could have values other than -1, 0 or 1,
2662 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2663 values are used or likely. */
2665 static int
2666 zero_one_minusone (gphi *phi, int limit)
2668 int phi_num_args = gimple_phi_num_args (phi);
2669 int ret = 0;
2670 for (int i = 0; i < phi_num_args; i++)
2672 tree t = PHI_ARG_DEF (phi, i);
2673 if (TREE_CODE (t) != INTEGER_CST)
2674 continue;
2675 wide_int w = wi::to_wide (t);
2676 if (w == -1)
2677 ret |= 1;
2678 else if (w == 0)
2679 ret |= 2;
2680 else if (w == 1)
2681 ret |= 4;
2682 else
2683 return 0;
2685 for (int i = 0; i < phi_num_args; i++)
2687 tree t = PHI_ARG_DEF (phi, i);
2688 if (TREE_CODE (t) == INTEGER_CST)
2689 continue;
2690 if (TREE_CODE (t) != SSA_NAME)
2691 return 0;
2692 gimple *g = SSA_NAME_DEF_STMT (t);
2693 if (gimple_code (g) == GIMPLE_PHI && limit > 0)
2694 if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
2696 ret |= r;
2697 continue;
2699 if (!is_gimple_assign (g))
2700 return 0;
2701 if (gimple_assign_cast_p (g))
2703 tree rhs1 = gimple_assign_rhs1 (g);
2704 if (TREE_CODE (rhs1) != SSA_NAME
2705 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2706 || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2707 || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2708 return 0;
2709 ret |= (2 | 4);
2710 continue;
2712 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
2713 return 0;
2714 ret |= (2 | 4);
2716 return ret;
2719 /* Find the basic block with return expression and look up for possible
2720 return value trying to apply RETURN_PREDICTION heuristics. */
2721 static void
2722 apply_return_prediction (void)
2724 greturn *return_stmt = NULL;
2725 tree return_val;
2726 edge e;
2727 gphi *phi;
2728 int phi_num_args, i;
2729 enum br_predictor pred;
2730 enum prediction direction;
2731 edge_iterator ei;
2733 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2735 gimple *last = last_stmt (e->src);
2736 if (last
2737 && gimple_code (last) == GIMPLE_RETURN)
2739 return_stmt = as_a <greturn *> (last);
2740 break;
2743 if (!e)
2744 return;
2745 return_val = gimple_return_retval (return_stmt);
2746 if (!return_val)
2747 return;
2748 if (TREE_CODE (return_val) != SSA_NAME
2749 || !SSA_NAME_DEF_STMT (return_val)
2750 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2751 return;
2752 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2753 phi_num_args = gimple_phi_num_args (phi);
2754 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
2756 /* Avoid the case where the function returns -1, 0 and 1 values and
2757 nothing else. Those could be qsort etc. comparison functions
2758 where the negative return isn't less probable than positive.
2759 For this require that the function returns at least -1 or 1
2760 or -1 and a boolean value or comparison result, so that functions
2761 returning just -1 and 0 are treated as if -1 represents error value. */
2762 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
2763 && !TYPE_UNSIGNED (TREE_TYPE (return_val))
2764 && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
2765 if (int r = zero_one_minusone (phi, 3))
2766 if ((r & (1 | 4)) == (1 | 4))
2767 return;
2769 /* Avoid the degenerate case where all return values form the function
2770 belongs to same category (ie they are all positive constants)
2771 so we can hardly say something about them. */
2772 for (i = 1; i < phi_num_args; i++)
2773 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
2774 break;
2775 if (i != phi_num_args)
2776 for (i = 0; i < phi_num_args; i++)
2778 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
2779 if (pred != PRED_NO_PREDICTION)
2780 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
2781 direction);
2785 /* Look for basic block that contains unlikely to happen events
2786 (such as noreturn calls) and mark all paths leading to execution
2787 of this basic blocks as unlikely. */
2789 static void
2790 tree_bb_level_predictions (void)
2792 basic_block bb;
2793 bool has_return_edges = false;
2794 edge e;
2795 edge_iterator ei;
2797 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2798 if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
2800 has_return_edges = true;
2801 break;
2804 apply_return_prediction ();
2806 FOR_EACH_BB_FN (bb, cfun)
2808 gimple_stmt_iterator gsi;
2810 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2812 gimple *stmt = gsi_stmt (gsi);
2813 tree decl;
2815 if (is_gimple_call (stmt))
2817 if (gimple_call_noreturn_p (stmt)
2818 && has_return_edges
2819 && !is_exit_with_zero_arg (stmt))
2820 predict_paths_leading_to (bb, PRED_NORETURN,
2821 NOT_TAKEN);
2822 decl = gimple_call_fndecl (stmt);
2823 if (decl
2824 && lookup_attribute ("cold",
2825 DECL_ATTRIBUTES (decl)))
2826 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
2827 NOT_TAKEN);
2828 if (decl && recursive_call_p (current_function_decl, decl))
2829 predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
2830 NOT_TAKEN);
2832 else if (gimple_code (stmt) == GIMPLE_PREDICT)
2834 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
2835 gimple_predict_outcome (stmt));
2836 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2837 hints to callers. */
2843 /* Callback for hash_map::traverse, asserts that the pointer map is
2844 empty. */
2846 bool
2847 assert_is_empty (const_basic_block const &, edge_prediction *const &value,
2848 void *)
2850 gcc_assert (!value);
2851 return false;
2854 /* Predict branch probabilities and estimate profile for basic block BB.
2855 When LOCAL_ONLY is set do not use any global properties of CFG. */
2857 static void
2858 tree_estimate_probability_bb (basic_block bb, bool local_only)
2860 edge e;
2861 edge_iterator ei;
2863 FOR_EACH_EDGE (e, ei, bb->succs)
2865 /* Look for block we are guarding (ie we dominate it,
2866 but it doesn't postdominate us). */
2867 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
2868 && !local_only
2869 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
2870 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
2872 gimple_stmt_iterator bi;
2874 /* The call heuristic claims that a guarded function call
2875 is improbable. This is because such calls are often used
2876 to signal exceptional situations such as printing error
2877 messages. */
2878 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
2879 gsi_next (&bi))
2881 gimple *stmt = gsi_stmt (bi);
2882 if (is_gimple_call (stmt)
2883 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
2884 /* Constant and pure calls are hardly used to signalize
2885 something exceptional. */
2886 && gimple_has_side_effects (stmt))
2888 if (gimple_call_fndecl (stmt))
2889 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
2890 else if (virtual_method_call_p (gimple_call_fn (stmt)))
2891 predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
2892 else
2893 predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
2894 break;
2899 tree_predict_by_opcode (bb);
2902 /* Predict branch probabilities and estimate profile of the tree CFG.
2903 This function can be called from the loop optimizers to recompute
2904 the profile information.
2905 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2907 void
2908 tree_estimate_probability (bool dry_run)
2910 basic_block bb;
2912 add_noreturn_fake_exit_edges ();
2913 connect_infinite_loops_to_exit ();
2914 /* We use loop_niter_by_eval, which requires that the loops have
2915 preheaders. */
2916 create_preheaders (CP_SIMPLE_PREHEADERS);
2917 calculate_dominance_info (CDI_POST_DOMINATORS);
2919 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2920 tree_bb_level_predictions ();
2921 record_loop_exits ();
2923 if (number_of_loops (cfun) > 1)
2924 predict_loops ();
2926 FOR_EACH_BB_FN (bb, cfun)
2927 tree_estimate_probability_bb (bb, false);
2929 FOR_EACH_BB_FN (bb, cfun)
2930 combine_predictions_for_bb (bb, dry_run);
2932 if (flag_checking)
2933 bb_predictions->traverse<void *, assert_is_empty> (NULL);
2935 delete bb_predictions;
2936 bb_predictions = NULL;
2938 if (!dry_run)
2939 estimate_bb_frequencies (false);
2940 free_dominance_info (CDI_POST_DOMINATORS);
2941 remove_fake_exit_edges ();
2944 /* Set edge->probability for each successor edge of BB. */
2945 void
2946 tree_guess_outgoing_edge_probabilities (basic_block bb)
2948 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2949 tree_estimate_probability_bb (bb, true);
2950 combine_predictions_for_bb (bb, false);
2951 if (flag_checking)
2952 bb_predictions->traverse<void *, assert_is_empty> (NULL);
2953 delete bb_predictions;
2954 bb_predictions = NULL;
2957 /* Predict edges to successors of CUR whose sources are not postdominated by
2958 BB by PRED and recurse to all postdominators. */
2960 static void
2961 predict_paths_for_bb (basic_block cur, basic_block bb,
2962 enum br_predictor pred,
2963 enum prediction taken,
2964 bitmap visited, struct loop *in_loop = NULL)
2966 edge e;
2967 edge_iterator ei;
2968 basic_block son;
2970 /* If we exited the loop or CUR is unconditional in the loop, there is
2971 nothing to do. */
2972 if (in_loop
2973 && (!flow_bb_inside_loop_p (in_loop, cur)
2974 || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
2975 return;
2977 /* We are looking for all edges forming edge cut induced by
2978 set of all blocks postdominated by BB. */
2979 FOR_EACH_EDGE (e, ei, cur->preds)
2980 if (e->src->index >= NUM_FIXED_BLOCKS
2981 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
2983 edge e2;
2984 edge_iterator ei2;
2985 bool found = false;
2987 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2988 if (unlikely_executed_edge_p (e))
2989 continue;
2990 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
2992 /* See if there is an edge from e->src that is not abnormal
2993 and does not lead to BB and does not exit the loop. */
2994 FOR_EACH_EDGE (e2, ei2, e->src->succs)
2995 if (e2 != e
2996 && !unlikely_executed_edge_p (e2)
2997 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
2998 && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
3000 found = true;
3001 break;
3004 /* If there is non-abnormal path leaving e->src, predict edge
3005 using predictor. Otherwise we need to look for paths
3006 leading to e->src.
3008 The second may lead to infinite loop in the case we are predicitng
3009 regions that are only reachable by abnormal edges. We simply
3010 prevent visiting given BB twice. */
3011 if (found)
3013 if (!edge_predicted_by_p (e, pred, taken))
3014 predict_edge_def (e, pred, taken);
3016 else if (bitmap_set_bit (visited, e->src->index))
3017 predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
3019 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3020 son;
3021 son = next_dom_son (CDI_POST_DOMINATORS, son))
3022 predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
3025 /* Sets branch probabilities according to PREDiction and
3026 FLAGS. */
3028 static void
3029 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3030 enum prediction taken, struct loop *in_loop)
3032 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3035 /* Like predict_paths_leading_to but take edge instead of basic block. */
3037 static void
3038 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3039 enum prediction taken, struct loop *in_loop)
3041 bool has_nonloop_edge = false;
3042 edge_iterator ei;
3043 edge e2;
3045 basic_block bb = e->src;
3046 FOR_EACH_EDGE (e2, ei, bb->succs)
3047 if (e2->dest != e->src && e2->dest != e->dest
3048 && !unlikely_executed_edge_p (e)
3049 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3051 has_nonloop_edge = true;
3052 break;
3054 if (!has_nonloop_edge)
3056 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3058 else
3059 predict_edge_def (e, pred, taken);
3062 /* This is used to carry information about basic blocks. It is
3063 attached to the AUX field of the standard CFG block. */
3065 struct block_info
3067 /* Estimated frequency of execution of basic_block. */
3068 sreal frequency;
3070 /* To keep queue of basic blocks to process. */
3071 basic_block next;
3073 /* Number of predecessors we need to visit first. */
3074 int npredecessors;
3077 /* Similar information for edges. */
3078 struct edge_prob_info
3080 /* In case edge is a loopback edge, the probability edge will be reached
3081 in case header is. Estimated number of iterations of the loop can be
3082 then computed as 1 / (1 - back_edge_prob). */
3083 sreal back_edge_prob;
3084 /* True if the edge is a loopback edge in the natural loop. */
3085 unsigned int back_edge:1;
3088 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3089 #undef EDGE_INFO
3090 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3092 /* Helper function for estimate_bb_frequencies.
3093 Propagate the frequencies in blocks marked in
3094 TOVISIT, starting in HEAD. */
3096 static void
3097 propagate_freq (basic_block head, bitmap tovisit)
3099 basic_block bb;
3100 basic_block last;
3101 unsigned i;
3102 edge e;
3103 basic_block nextbb;
3104 bitmap_iterator bi;
3106 /* For each basic block we need to visit count number of his predecessors
3107 we need to visit first. */
3108 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3110 edge_iterator ei;
3111 int count = 0;
3113 bb = BASIC_BLOCK_FOR_FN (cfun, i);
3115 FOR_EACH_EDGE (e, ei, bb->preds)
3117 bool visit = bitmap_bit_p (tovisit, e->src->index);
3119 if (visit && !(e->flags & EDGE_DFS_BACK))
3120 count++;
3121 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3122 fprintf (dump_file,
3123 "Irreducible region hit, ignoring edge to %i->%i\n",
3124 e->src->index, bb->index);
3126 BLOCK_INFO (bb)->npredecessors = count;
3127 /* When function never returns, we will never process exit block. */
3128 if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3129 bb->count = profile_count::zero ();
3132 BLOCK_INFO (head)->frequency = 1;
3133 last = head;
3134 for (bb = head; bb; bb = nextbb)
3136 edge_iterator ei;
3137 sreal cyclic_probability = 0;
3138 sreal frequency = 0;
3140 nextbb = BLOCK_INFO (bb)->next;
3141 BLOCK_INFO (bb)->next = NULL;
3143 /* Compute frequency of basic block. */
3144 if (bb != head)
3146 if (flag_checking)
3147 FOR_EACH_EDGE (e, ei, bb->preds)
3148 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3149 || (e->flags & EDGE_DFS_BACK));
3151 FOR_EACH_EDGE (e, ei, bb->preds)
3152 if (EDGE_INFO (e)->back_edge)
3154 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3156 else if (!(e->flags & EDGE_DFS_BACK))
3158 /* frequency += (e->probability
3159 * BLOCK_INFO (e->src)->frequency /
3160 REG_BR_PROB_BASE); */
3162 /* FIXME: Graphite is producing edges with no profile. Once
3163 this is fixed, drop this. */
3164 sreal tmp = e->probability.initialized_p () ?
3165 e->probability.to_reg_br_prob_base () : 0;
3166 tmp *= BLOCK_INFO (e->src)->frequency;
3167 tmp *= real_inv_br_prob_base;
3168 frequency += tmp;
3171 if (cyclic_probability == 0)
3173 BLOCK_INFO (bb)->frequency = frequency;
3175 else
3177 if (cyclic_probability > real_almost_one)
3178 cyclic_probability = real_almost_one;
3180 /* BLOCK_INFO (bb)->frequency = frequency
3181 / (1 - cyclic_probability) */
3183 cyclic_probability = sreal (1) - cyclic_probability;
3184 BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
3188 bitmap_clear_bit (tovisit, bb->index);
3190 e = find_edge (bb, head);
3191 if (e)
3193 /* EDGE_INFO (e)->back_edge_prob
3194 = ((e->probability * BLOCK_INFO (bb)->frequency)
3195 / REG_BR_PROB_BASE); */
3197 /* FIXME: Graphite is producing edges with no profile. Once
3198 this is fixed, drop this. */
3199 sreal tmp = e->probability.initialized_p () ?
3200 e->probability.to_reg_br_prob_base () : 0;
3201 tmp *= BLOCK_INFO (bb)->frequency;
3202 EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
3205 /* Propagate to successor blocks. */
3206 FOR_EACH_EDGE (e, ei, bb->succs)
3207 if (!(e->flags & EDGE_DFS_BACK)
3208 && BLOCK_INFO (e->dest)->npredecessors)
3210 BLOCK_INFO (e->dest)->npredecessors--;
3211 if (!BLOCK_INFO (e->dest)->npredecessors)
3213 if (!nextbb)
3214 nextbb = e->dest;
3215 else
3216 BLOCK_INFO (last)->next = e->dest;
3218 last = e->dest;
3224 /* Estimate frequencies in loops at same nest level. */
3226 static void
3227 estimate_loops_at_level (struct loop *first_loop)
3229 struct loop *loop;
3231 for (loop = first_loop; loop; loop = loop->next)
3233 edge e;
3234 basic_block *bbs;
3235 unsigned i;
3236 auto_bitmap tovisit;
3238 estimate_loops_at_level (loop->inner);
3240 /* Find current loop back edge and mark it. */
3241 e = loop_latch_edge (loop);
3242 EDGE_INFO (e)->back_edge = 1;
3244 bbs = get_loop_body (loop);
3245 for (i = 0; i < loop->num_nodes; i++)
3246 bitmap_set_bit (tovisit, bbs[i]->index);
3247 free (bbs);
3248 propagate_freq (loop->header, tovisit);
3252 /* Propagates frequencies through structure of loops. */
3254 static void
3255 estimate_loops (void)
3257 auto_bitmap tovisit;
3258 basic_block bb;
3260 /* Start by estimating the frequencies in the loops. */
3261 if (number_of_loops (cfun) > 1)
3262 estimate_loops_at_level (current_loops->tree_root->inner);
3264 /* Now propagate the frequencies through all the blocks. */
3265 FOR_ALL_BB_FN (bb, cfun)
3267 bitmap_set_bit (tovisit, bb->index);
3269 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
3272 /* Drop the profile for NODE to guessed, and update its frequency based on
3273 whether it is expected to be hot given the CALL_COUNT. */
3275 static void
3276 drop_profile (struct cgraph_node *node, profile_count call_count)
3278 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3279 /* In the case where this was called by another function with a
3280 dropped profile, call_count will be 0. Since there are no
3281 non-zero call counts to this function, we don't know for sure
3282 whether it is hot, and therefore it will be marked normal below. */
3283 bool hot = maybe_hot_count_p (NULL, call_count);
3285 if (dump_file)
3286 fprintf (dump_file,
3287 "Dropping 0 profile for %s. %s based on calls.\n",
3288 node->dump_name (),
3289 hot ? "Function is hot" : "Function is normal");
3290 /* We only expect to miss profiles for functions that are reached
3291 via non-zero call edges in cases where the function may have
3292 been linked from another module or library (COMDATs and extern
3293 templates). See the comments below for handle_missing_profiles.
3294 Also, only warn in cases where the missing counts exceed the
3295 number of training runs. In certain cases with an execv followed
3296 by a no-return call the profile for the no-return call is not
3297 dumped and there can be a mismatch. */
3298 if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3299 && call_count > profile_info->runs)
3301 if (flag_profile_correction)
3303 if (dump_file)
3304 fprintf (dump_file,
3305 "Missing counts for called function %s\n",
3306 node->dump_name ());
3308 else
3309 warning (0, "Missing counts for called function %s",
3310 node->dump_name ());
3313 basic_block bb;
3314 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3315 if (flag_guess_branch_prob)
3317 bool clear_zeros
3318 = ENTRY_BLOCK_PTR_FOR_FN
3319 (DECL_STRUCT_FUNCTION (node->decl))->count.nonzero_p ();
3320 FOR_ALL_BB_FN (bb, fn)
3321 if (clear_zeros || !(bb->count == profile_count::zero ()))
3322 bb->count = bb->count.guessed_local ();
3323 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max =
3324 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max.guessed_local ();
3326 else
3328 FOR_ALL_BB_FN (bb, fn)
3329 bb->count = profile_count::uninitialized ();
3330 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max
3331 = profile_count::uninitialized ();
3333 pop_cfun ();
3335 struct cgraph_edge *e;
3336 for (e = node->callees; e; e = e->next_callee)
3337 e->count = gimple_bb (e->call_stmt)->count;
3338 for (e = node->indirect_calls; e; e = e->next_callee)
3339 e->count = gimple_bb (e->call_stmt)->count;
3341 profile_status_for_fn (fn)
3342 = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3343 node->frequency
3344 = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3347 /* In the case of COMDAT routines, multiple object files will contain the same
3348 function and the linker will select one for the binary. In that case
3349 all the other copies from the profile instrument binary will be missing
3350 profile counts. Look for cases where this happened, due to non-zero
3351 call counts going to 0-count functions, and drop the profile to guessed
3352 so that we can use the estimated probabilities and avoid optimizing only
3353 for size.
3355 The other case where the profile may be missing is when the routine
3356 is not going to be emitted to the object file, e.g. for "extern template"
3357 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3358 all other cases of non-zero calls to 0-count functions. */
3360 void
3361 handle_missing_profiles (void)
3363 struct cgraph_node *node;
3364 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
3365 auto_vec<struct cgraph_node *, 64> worklist;
3367 /* See if 0 count function has non-0 count callers. In this case we
3368 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3369 FOR_EACH_DEFINED_FUNCTION (node)
3371 struct cgraph_edge *e;
3372 profile_count call_count = profile_count::zero ();
3373 gcov_type max_tp_first_run = 0;
3374 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3376 if (!(node->count == profile_count::zero ()))
3377 continue;
3378 for (e = node->callers; e; e = e->next_caller)
3379 if (e->count.initialized_p () && e->count > 0)
3381 call_count = call_count + e->count;
3383 if (e->caller->tp_first_run > max_tp_first_run)
3384 max_tp_first_run = e->caller->tp_first_run;
3387 /* If time profile is missing, let assign the maximum that comes from
3388 caller functions. */
3389 if (!node->tp_first_run && max_tp_first_run)
3390 node->tp_first_run = max_tp_first_run + 1;
3392 if (call_count > 0
3393 && fn && fn->cfg
3394 && (call_count.apply_scale (unlikely_count_fraction, 1)
3395 >= profile_info->runs))
3397 drop_profile (node, call_count);
3398 worklist.safe_push (node);
3402 /* Propagate the profile dropping to other 0-count COMDATs that are
3403 potentially called by COMDATs we already dropped the profile on. */
3404 while (worklist.length () > 0)
3406 struct cgraph_edge *e;
3408 node = worklist.pop ();
3409 for (e = node->callees; e; e = e->next_caller)
3411 struct cgraph_node *callee = e->callee;
3412 struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3414 if (callee->count > 0)
3415 continue;
3416 if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3417 && fn && fn->cfg
3418 && profile_status_for_fn (fn) == PROFILE_READ)
3420 drop_profile (node, profile_count::zero ());
3421 worklist.safe_push (callee);
3427 /* Convert counts measured by profile driven feedback to frequencies.
3428 Return nonzero iff there was any nonzero execution count. */
3430 bool
3431 update_max_bb_count (void)
3433 profile_count true_count_max = profile_count::uninitialized ();
3434 basic_block bb;
3436 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3437 true_count_max = true_count_max.max (bb->count);
3439 cfun->cfg->count_max = true_count_max;
3441 return true_count_max.ipa ().nonzero_p ();
3444 /* Return true if function is likely to be expensive, so there is no point to
3445 optimize performance of prologue, epilogue or do inlining at the expense
3446 of code size growth. THRESHOLD is the limit of number of instructions
3447 function can execute at average to be still considered not expensive. */
3449 bool
3450 expensive_function_p (int threshold)
3452 basic_block bb;
3454 /* If profile was scaled in a way entry block has count 0, then the function
3455 is deifnitly taking a lot of time. */
3456 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3457 return true;
3459 profile_count limit = ENTRY_BLOCK_PTR_FOR_FN
3460 (cfun)->count.apply_scale (threshold, 1);
3461 profile_count sum = profile_count::zero ();
3462 FOR_EACH_BB_FN (bb, cfun)
3464 rtx_insn *insn;
3466 if (!bb->count.initialized_p ())
3468 if (dump_file)
3469 fprintf (dump_file, "Function is considered expensive because"
3470 " count of bb %i is not initialized\n", bb->index);
3471 return true;
3474 FOR_BB_INSNS (bb, insn)
3475 if (active_insn_p (insn))
3477 sum += bb->count;
3478 if (sum > limit)
3479 return true;
3483 return false;
3486 /* All basic blocks that are reachable only from unlikely basic blocks are
3487 unlikely. */
3489 void
3490 propagate_unlikely_bbs_forward (void)
3492 auto_vec<basic_block, 64> worklist;
3493 basic_block bb;
3494 edge_iterator ei;
3495 edge e;
3497 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3499 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3500 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3502 while (worklist.length () > 0)
3504 bb = worklist.pop ();
3505 FOR_EACH_EDGE (e, ei, bb->succs)
3506 if (!(e->count () == profile_count::zero ())
3507 && !(e->dest->count == profile_count::zero ())
3508 && !e->dest->aux)
3510 e->dest->aux = (void *)(size_t) 1;
3511 worklist.safe_push (e->dest);
3516 FOR_ALL_BB_FN (bb, cfun)
3518 if (!bb->aux)
3520 if (!(bb->count == profile_count::zero ())
3521 && (dump_file && (dump_flags & TDF_DETAILS)))
3522 fprintf (dump_file,
3523 "Basic block %i is marked unlikely by forward prop\n",
3524 bb->index);
3525 bb->count = profile_count::zero ();
3527 else
3528 bb->aux = NULL;
3532 /* Determine basic blocks/edges that are known to be unlikely executed and set
3533 their counters to zero.
3534 This is done with first identifying obviously unlikely BBs/edges and then
3535 propagating in both directions. */
3537 static void
3538 determine_unlikely_bbs ()
3540 basic_block bb;
3541 auto_vec<basic_block, 64> worklist;
3542 edge_iterator ei;
3543 edge e;
3545 FOR_EACH_BB_FN (bb, cfun)
3547 if (!(bb->count == profile_count::zero ())
3548 && unlikely_executed_bb_p (bb))
3550 if (dump_file && (dump_flags & TDF_DETAILS))
3551 fprintf (dump_file, "Basic block %i is locally unlikely\n",
3552 bb->index);
3553 bb->count = profile_count::zero ();
3556 FOR_EACH_EDGE (e, ei, bb->succs)
3557 if (!(e->probability == profile_probability::never ())
3558 && unlikely_executed_edge_p (e))
3560 if (dump_file && (dump_flags & TDF_DETAILS))
3561 fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
3562 bb->index, e->dest->index);
3563 e->probability = profile_probability::never ();
3566 gcc_checking_assert (!bb->aux);
3568 propagate_unlikely_bbs_forward ();
3570 auto_vec<int, 64> nsuccs;
3571 nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun));
3572 FOR_ALL_BB_FN (bb, cfun)
3573 if (!(bb->count == profile_count::zero ())
3574 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3576 nsuccs[bb->index] = 0;
3577 FOR_EACH_EDGE (e, ei, bb->succs)
3578 if (!(e->probability == profile_probability::never ())
3579 && !(e->dest->count == profile_count::zero ()))
3580 nsuccs[bb->index]++;
3581 if (!nsuccs[bb->index])
3582 worklist.safe_push (bb);
3584 while (worklist.length () > 0)
3586 bb = worklist.pop ();
3587 if (bb->count == profile_count::zero ())
3588 continue;
3589 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3591 bool found = false;
3592 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
3593 !gsi_end_p (gsi); gsi_next (&gsi))
3594 if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
3595 /* stmt_can_terminate_bb_p special cases noreturns because it
3596 assumes that fake edges are created. We want to know that
3597 noreturn alone does not imply BB to be unlikely. */
3598 || (is_gimple_call (gsi_stmt (gsi))
3599 && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
3601 found = true;
3602 break;
3604 if (found)
3605 continue;
3607 if (dump_file && (dump_flags & TDF_DETAILS))
3608 fprintf (dump_file,
3609 "Basic block %i is marked unlikely by backward prop\n",
3610 bb->index);
3611 bb->count = profile_count::zero ();
3612 FOR_EACH_EDGE (e, ei, bb->preds)
3613 if (!(e->probability == profile_probability::never ()))
3615 if (!(e->src->count == profile_count::zero ()))
3617 gcc_checking_assert (nsuccs[e->src->index] > 0);
3618 nsuccs[e->src->index]--;
3619 if (!nsuccs[e->src->index])
3620 worklist.safe_push (e->src);
3624 /* Finally all edges from non-0 regions to 0 are unlikely. */
3625 FOR_ALL_BB_FN (bb, cfun)
3626 if (!(bb->count == profile_count::zero ()))
3627 FOR_EACH_EDGE (e, ei, bb->succs)
3628 if (!(e->probability == profile_probability::never ())
3629 && e->dest->count == profile_count::zero ())
3631 if (dump_file && (dump_flags & TDF_DETAILS))
3632 fprintf (dump_file, "Edge %i->%i is unlikely because "
3633 "it enters unlikely block\n",
3634 bb->index, e->dest->index);
3635 e->probability = profile_probability::never ();
3637 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
3638 cgraph_node::get (current_function_decl)->count = profile_count::zero ();
3641 /* Estimate and propagate basic block frequencies using the given branch
3642 probabilities. If FORCE is true, the frequencies are used to estimate
3643 the counts even when there are already non-zero profile counts. */
3645 void
3646 estimate_bb_frequencies (bool force)
3648 basic_block bb;
3649 sreal freq_max;
3651 determine_unlikely_bbs ();
3653 if (force || profile_status_for_fn (cfun) != PROFILE_READ
3654 || !update_max_bb_count ())
3656 static int real_values_initialized = 0;
3658 if (!real_values_initialized)
3660 real_values_initialized = 1;
3661 real_br_prob_base = REG_BR_PROB_BASE;
3662 /* Scaling frequencies up to maximal profile count may result in
3663 frequent overflows especially when inlining loops.
3664 Small scalling results in unnecesary precision loss. Stay in
3665 the half of the (exponential) range. */
3666 real_bb_freq_max = (uint64_t)1 << (profile_count::n_bits / 2);
3667 real_one_half = sreal (1, -1);
3668 real_inv_br_prob_base = sreal (1) / real_br_prob_base;
3669 real_almost_one = sreal (1) - real_inv_br_prob_base;
3672 mark_dfs_back_edges ();
3674 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
3675 profile_probability::always ();
3677 /* Set up block info for each basic block. */
3678 alloc_aux_for_blocks (sizeof (block_info));
3679 alloc_aux_for_edges (sizeof (edge_prob_info));
3680 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3682 edge e;
3683 edge_iterator ei;
3685 FOR_EACH_EDGE (e, ei, bb->succs)
3687 /* FIXME: Graphite is producing edges with no profile. Once
3688 this is fixed, drop this. */
3689 if (e->probability.initialized_p ())
3690 EDGE_INFO (e)->back_edge_prob
3691 = e->probability.to_reg_br_prob_base ();
3692 else
3693 EDGE_INFO (e)->back_edge_prob = REG_BR_PROB_BASE / 2;
3694 EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
3698 /* First compute frequencies locally for each loop from innermost
3699 to outermost to examine frequencies for back edges. */
3700 estimate_loops ();
3702 freq_max = 0;
3703 FOR_EACH_BB_FN (bb, cfun)
3704 if (freq_max < BLOCK_INFO (bb)->frequency)
3705 freq_max = BLOCK_INFO (bb)->frequency;
3707 freq_max = real_bb_freq_max / freq_max;
3708 if (freq_max < 16)
3709 freq_max = 16;
3710 profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
3711 cfun->cfg->count_max = profile_count::uninitialized ();
3712 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3714 sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
3715 profile_count count = profile_count::from_gcov_type (tmp.to_int ());
3717 /* If we have profile feedback in which this function was never
3718 executed, then preserve this info. */
3719 if (!(bb->count == profile_count::zero ()))
3720 bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
3721 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
3724 free_aux_for_blocks ();
3725 free_aux_for_edges ();
3727 compute_function_frequency ();
3730 /* Decide whether function is hot, cold or unlikely executed. */
3731 void
3732 compute_function_frequency (void)
3734 basic_block bb;
3735 struct cgraph_node *node = cgraph_node::get (current_function_decl);
3737 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3738 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
3739 node->only_called_at_startup = true;
3740 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
3741 node->only_called_at_exit = true;
3743 if (profile_status_for_fn (cfun) != PROFILE_READ)
3745 int flags = flags_from_decl_or_type (current_function_decl);
3746 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ()
3747 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3748 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
3749 != NULL)
3751 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3752 warn_function_cold (current_function_decl);
3754 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
3755 != NULL)
3756 node->frequency = NODE_FREQUENCY_HOT;
3757 else if (flags & ECF_NORETURN)
3758 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3759 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
3760 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3761 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3762 || DECL_STATIC_DESTRUCTOR (current_function_decl))
3763 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3764 return;
3767 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3768 warn_function_cold (current_function_decl);
3769 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3770 return;
3771 FOR_EACH_BB_FN (bb, cfun)
3773 if (maybe_hot_bb_p (cfun, bb))
3775 node->frequency = NODE_FREQUENCY_HOT;
3776 return;
3778 if (!probably_never_executed_bb_p (cfun, bb))
3779 node->frequency = NODE_FREQUENCY_NORMAL;
3783 /* Build PREDICT_EXPR. */
3784 tree
3785 build_predict_expr (enum br_predictor predictor, enum prediction taken)
3787 tree t = build1 (PREDICT_EXPR, void_type_node,
3788 build_int_cst (integer_type_node, predictor));
3789 SET_PREDICT_EXPR_OUTCOME (t, taken);
3790 return t;
3793 const char *
3794 predictor_name (enum br_predictor predictor)
3796 return predictor_info[predictor].name;
3799 /* Predict branch probabilities and estimate profile of the tree CFG. */
3801 namespace {
3803 const pass_data pass_data_profile =
3805 GIMPLE_PASS, /* type */
3806 "profile_estimate", /* name */
3807 OPTGROUP_NONE, /* optinfo_flags */
3808 TV_BRANCH_PROB, /* tv_id */
3809 PROP_cfg, /* properties_required */
3810 0, /* properties_provided */
3811 0, /* properties_destroyed */
3812 0, /* todo_flags_start */
3813 0, /* todo_flags_finish */
3816 class pass_profile : public gimple_opt_pass
3818 public:
3819 pass_profile (gcc::context *ctxt)
3820 : gimple_opt_pass (pass_data_profile, ctxt)
3823 /* opt_pass methods: */
3824 virtual bool gate (function *) { return flag_guess_branch_prob; }
3825 virtual unsigned int execute (function *);
3827 }; // class pass_profile
3829 unsigned int
3830 pass_profile::execute (function *fun)
3832 unsigned nb_loops;
3834 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3835 return 0;
3837 loop_optimizer_init (LOOPS_NORMAL);
3838 if (dump_file && (dump_flags & TDF_DETAILS))
3839 flow_loops_dump (dump_file, NULL, 0);
3841 mark_irreducible_loops ();
3843 nb_loops = number_of_loops (fun);
3844 if (nb_loops > 1)
3845 scev_initialize ();
3847 tree_estimate_probability (false);
3849 if (nb_loops > 1)
3850 scev_finalize ();
3852 loop_optimizer_finalize ();
3853 if (dump_file && (dump_flags & TDF_DETAILS))
3854 gimple_dump_cfg (dump_file, dump_flags);
3855 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
3856 profile_status_for_fn (fun) = PROFILE_GUESSED;
3857 if (dump_file && (dump_flags & TDF_DETAILS))
3859 struct loop *loop;
3860 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3861 if (loop->header->count.initialized_p ())
3862 fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
3863 loop->num,
3864 (int)expected_loop_iterations_unbounded (loop));
3866 return 0;
3869 } // anon namespace
3871 gimple_opt_pass *
3872 make_pass_profile (gcc::context *ctxt)
3874 return new pass_profile (ctxt);
3877 namespace {
3879 const pass_data pass_data_strip_predict_hints =
3881 GIMPLE_PASS, /* type */
3882 "*strip_predict_hints", /* name */
3883 OPTGROUP_NONE, /* optinfo_flags */
3884 TV_BRANCH_PROB, /* tv_id */
3885 PROP_cfg, /* properties_required */
3886 0, /* properties_provided */
3887 0, /* properties_destroyed */
3888 0, /* todo_flags_start */
3889 0, /* todo_flags_finish */
3892 class pass_strip_predict_hints : public gimple_opt_pass
3894 public:
3895 pass_strip_predict_hints (gcc::context *ctxt)
3896 : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
3899 /* opt_pass methods: */
3900 opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
3901 virtual unsigned int execute (function *);
3903 }; // class pass_strip_predict_hints
3905 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3906 we no longer need. */
3907 unsigned int
3908 pass_strip_predict_hints::execute (function *fun)
3910 basic_block bb;
3911 gimple *ass_stmt;
3912 tree var;
3913 bool changed = false;
3915 FOR_EACH_BB_FN (bb, fun)
3917 gimple_stmt_iterator bi;
3918 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
3920 gimple *stmt = gsi_stmt (bi);
3922 if (gimple_code (stmt) == GIMPLE_PREDICT)
3924 gsi_remove (&bi, true);
3925 changed = true;
3926 continue;
3928 else if (is_gimple_call (stmt))
3930 tree fndecl = gimple_call_fndecl (stmt);
3932 if ((fndecl
3933 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
3934 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
3935 && gimple_call_num_args (stmt) == 2)
3936 || (gimple_call_internal_p (stmt)
3937 && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
3939 var = gimple_call_lhs (stmt);
3940 changed = true;
3941 if (var)
3943 ass_stmt
3944 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
3945 gsi_replace (&bi, ass_stmt, true);
3947 else
3949 gsi_remove (&bi, true);
3950 continue;
3954 gsi_next (&bi);
3957 return changed ? TODO_cleanup_cfg : 0;
3960 } // anon namespace
3962 gimple_opt_pass *
3963 make_pass_strip_predict_hints (gcc::context *ctxt)
3965 return new pass_strip_predict_hints (ctxt);
3968 /* Rebuild function frequencies. Passes are in general expected to
3969 maintain profile by hand, however in some cases this is not possible:
3970 for example when inlining several functions with loops freuqencies might run
3971 out of scale and thus needs to be recomputed. */
3973 void
3974 rebuild_frequencies (void)
3976 timevar_push (TV_REBUILD_FREQUENCIES);
3978 /* When the max bb count in the function is small, there is a higher
3979 chance that there were truncation errors in the integer scaling
3980 of counts by inlining and other optimizations. This could lead
3981 to incorrect classification of code as being cold when it isn't.
3982 In that case, force the estimation of bb counts/frequencies from the
3983 branch probabilities, rather than computing frequencies from counts,
3984 which may also lead to frequencies incorrectly reduced to 0. There
3985 is less precision in the probabilities, so we only do this for small
3986 max counts. */
3987 cfun->cfg->count_max = profile_count::uninitialized ();
3988 basic_block bb;
3989 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3990 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
3992 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3994 loop_optimizer_init (0);
3995 add_noreturn_fake_exit_edges ();
3996 mark_irreducible_loops ();
3997 connect_infinite_loops_to_exit ();
3998 estimate_bb_frequencies (true);
3999 remove_fake_exit_edges ();
4000 loop_optimizer_finalize ();
4002 else if (profile_status_for_fn (cfun) == PROFILE_READ)
4003 update_max_bb_count ();
4004 else
4005 gcc_unreachable ();
4006 timevar_pop (TV_REBUILD_FREQUENCIES);
4009 /* Perform a dry run of the branch prediction pass and report comparsion of
4010 the predicted and real profile into the dump file. */
4012 void
4013 report_predictor_hitrates (void)
4015 unsigned nb_loops;
4017 loop_optimizer_init (LOOPS_NORMAL);
4018 if (dump_file && (dump_flags & TDF_DETAILS))
4019 flow_loops_dump (dump_file, NULL, 0);
4021 mark_irreducible_loops ();
4023 nb_loops = number_of_loops (cfun);
4024 if (nb_loops > 1)
4025 scev_initialize ();
4027 tree_estimate_probability (true);
4029 if (nb_loops > 1)
4030 scev_finalize ();
4032 loop_optimizer_finalize ();
4035 /* Force edge E to be cold.
4036 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4037 keep low probability to represent possible error in a guess. This is used
4038 i.e. in case we predict loop to likely iterate given number of times but
4039 we are not 100% sure.
4041 This function locally updates profile without attempt to keep global
4042 consistency which can not be reached in full generality without full profile
4043 rebuild from probabilities alone. Doing so is not necessarily a good idea
4044 because frequencies and counts may be more realistic then probabilities.
4046 In some cases (such as for elimination of early exits during full loop
4047 unrolling) the caller can ensure that profile will get consistent
4048 afterwards. */
4050 void
4051 force_edge_cold (edge e, bool impossible)
4053 profile_count count_sum = profile_count::zero ();
4054 profile_probability prob_sum = profile_probability::never ();
4055 edge_iterator ei;
4056 edge e2;
4057 bool uninitialized_exit = false;
4059 /* When branch probability guesses are not known, then do nothing. */
4060 if (!impossible && !e->count ().initialized_p ())
4061 return;
4063 profile_probability goal = (impossible ? profile_probability::never ()
4064 : profile_probability::very_unlikely ());
4066 /* If edge is already improbably or cold, just return. */
4067 if (e->probability <= goal
4068 && (!impossible || e->count () == profile_count::zero ()))
4069 return;
4070 FOR_EACH_EDGE (e2, ei, e->src->succs)
4071 if (e2 != e)
4073 if (e->flags & EDGE_FAKE)
4074 continue;
4075 if (e2->count ().initialized_p ())
4076 count_sum += e2->count ();
4077 if (e2->probability.initialized_p ())
4078 prob_sum += e2->probability;
4079 else
4080 uninitialized_exit = true;
4083 /* If we are not guessing profiles but have some other edges out,
4084 just assume the control flow goes elsewhere. */
4085 if (uninitialized_exit)
4086 e->probability = goal;
4087 /* If there are other edges out of e->src, redistribute probabilitity
4088 there. */
4089 else if (prob_sum > profile_probability::never ())
4091 if (!(e->probability < goal))
4092 e->probability = goal;
4094 profile_probability prob_comp = prob_sum / e->probability.invert ();
4096 if (dump_file && (dump_flags & TDF_DETAILS))
4097 fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4098 "probability to other edges.\n",
4099 e->src->index, e->dest->index,
4100 impossible ? "impossible" : "cold");
4101 FOR_EACH_EDGE (e2, ei, e->src->succs)
4102 if (e2 != e)
4104 e2->probability /= prob_comp;
4106 if (current_ir_type () != IR_GIMPLE
4107 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4108 update_br_prob_note (e->src);
4110 /* If all edges out of e->src are unlikely, the basic block itself
4111 is unlikely. */
4112 else
4114 if (prob_sum == profile_probability::never ())
4115 e->probability = profile_probability::always ();
4116 else
4118 if (impossible)
4119 e->probability = profile_probability::never ();
4120 /* If BB has some edges out that are not impossible, we can not
4121 assume that BB itself is. */
4122 impossible = false;
4124 if (current_ir_type () != IR_GIMPLE
4125 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4126 update_br_prob_note (e->src);
4127 if (e->src->count == profile_count::zero ())
4128 return;
4129 if (count_sum == profile_count::zero () && impossible)
4131 bool found = false;
4132 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4134 else if (current_ir_type () == IR_GIMPLE)
4135 for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4136 !gsi_end_p (gsi); gsi_next (&gsi))
4138 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
4140 found = true;
4141 break;
4144 /* FIXME: Implement RTL path. */
4145 else
4146 found = true;
4147 if (!found)
4149 if (dump_file && (dump_flags & TDF_DETAILS))
4150 fprintf (dump_file,
4151 "Making bb %i impossible and dropping count to 0.\n",
4152 e->src->index);
4153 e->src->count = profile_count::zero ();
4154 FOR_EACH_EDGE (e2, ei, e->src->preds)
4155 force_edge_cold (e2, impossible);
4156 return;
4160 /* If we did not adjusting, the source basic block has no likely edeges
4161 leaving other direction. In that case force that bb cold, too.
4162 This in general is difficult task to do, but handle special case when
4163 BB has only one predecestor. This is common case when we are updating
4164 after loop transforms. */
4165 if (!(prob_sum > profile_probability::never ())
4166 && count_sum == profile_count::zero ()
4167 && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4168 > (impossible ? 0 : 1))
4170 int old_frequency = e->src->count.to_frequency (cfun);
4171 if (dump_file && (dump_flags & TDF_DETAILS))
4172 fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
4173 impossible ? "impossible" : "cold");
4174 int new_frequency = MIN (e->src->count.to_frequency (cfun),
4175 impossible ? 0 : 1);
4176 if (impossible)
4177 e->src->count = profile_count::zero ();
4178 else
4179 e->src->count = e->count ().apply_scale (new_frequency,
4180 old_frequency);
4181 force_edge_cold (single_pred_edge (e->src), impossible);
4183 else if (dump_file && (dump_flags & TDF_DETAILS)
4184 && maybe_hot_bb_p (cfun, e->src))
4185 fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
4186 impossible ? "impossible" : "cold");
4190 #if CHECKING_P
4192 namespace selftest {
4194 /* Test that value range of predictor values defined in predict.def is
4195 within range (50, 100]. */
4197 struct branch_predictor
4199 const char *name;
4200 int probability;
4203 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4205 static void
4206 test_prediction_value_range ()
4208 branch_predictor predictors[] = {
4209 #include "predict.def"
4210 {NULL, -1U}
4213 for (unsigned i = 0; predictors[i].name != NULL; i++)
4215 if (predictors[i].probability == PROB_UNINITIALIZED)
4216 continue;
4218 unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4219 ASSERT_TRUE (p >= 50 && p <= 100);
4223 #undef DEF_PREDICTOR
4225 /* Run all of the selfests within this file. */
4227 void
4228 predict_c_tests ()
4230 test_prediction_value_range ();
4233 } // namespace selftest
4234 #endif /* CHECKING_P. */