* cgraphclones.c (cgraph_edge::clone): Rename gcov_count to prof_count.
[official-gcc.git] / gcc / predict.c
blob0f34956f699e1436a366146d499dcf30e4a948a7
1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
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 if (count.initialized_p () && profile_status_for_fn (fun) == PROFILE_READ)
217 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
218 if (count.apply_scale (unlikely_count_fraction, 1) >= profile_info->runs)
219 return false;
220 return true;
222 if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
223 && (cgraph_node::get (fun->decl)->frequency
224 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
225 return true;
226 return false;
230 /* Return true in case BB is probably never executed. */
232 bool
233 probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
235 return probably_never_executed (fun, bb->count);
239 /* Return true if E is unlikely executed for obvious reasons. */
241 static bool
242 unlikely_executed_edge_p (edge e)
244 return (e->count () == profile_count::zero ()
245 || e->probability == profile_probability::never ())
246 || (e->flags & (EDGE_EH | EDGE_FAKE));
249 /* Return true in case edge E is probably never executed. */
251 bool
252 probably_never_executed_edge_p (struct function *fun, edge e)
254 if (unlikely_executed_edge_p (e))
255 return true;
256 return probably_never_executed (fun, e->count ());
259 /* Return true when current function should always be optimized for size. */
261 bool
262 optimize_function_for_size_p (struct function *fun)
264 if (!fun || !fun->decl)
265 return optimize_size;
266 cgraph_node *n = cgraph_node::get (fun->decl);
267 return n && n->optimize_for_size_p ();
270 /* Return true when current function should always be optimized for speed. */
272 bool
273 optimize_function_for_speed_p (struct function *fun)
275 return !optimize_function_for_size_p (fun);
278 /* Return the optimization type that should be used for the function FUN. */
280 optimization_type
281 function_optimization_type (struct function *fun)
283 return (optimize_function_for_speed_p (fun)
284 ? OPTIMIZE_FOR_SPEED
285 : OPTIMIZE_FOR_SIZE);
288 /* Return TRUE when BB should be optimized for size. */
290 bool
291 optimize_bb_for_size_p (const_basic_block bb)
293 return (optimize_function_for_size_p (cfun)
294 || (bb && !maybe_hot_bb_p (cfun, bb)));
297 /* Return TRUE when BB should be optimized for speed. */
299 bool
300 optimize_bb_for_speed_p (const_basic_block bb)
302 return !optimize_bb_for_size_p (bb);
305 /* Return the optimization type that should be used for block BB. */
307 optimization_type
308 bb_optimization_type (const_basic_block bb)
310 return (optimize_bb_for_speed_p (bb)
311 ? OPTIMIZE_FOR_SPEED
312 : OPTIMIZE_FOR_SIZE);
315 /* Return TRUE when BB should be optimized for size. */
317 bool
318 optimize_edge_for_size_p (edge e)
320 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
323 /* Return TRUE when BB should be optimized for speed. */
325 bool
326 optimize_edge_for_speed_p (edge e)
328 return !optimize_edge_for_size_p (e);
331 /* Return TRUE when BB should be optimized for size. */
333 bool
334 optimize_insn_for_size_p (void)
336 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
339 /* Return TRUE when BB should be optimized for speed. */
341 bool
342 optimize_insn_for_speed_p (void)
344 return !optimize_insn_for_size_p ();
347 /* Return TRUE when LOOP should be optimized for size. */
349 bool
350 optimize_loop_for_size_p (struct loop *loop)
352 return optimize_bb_for_size_p (loop->header);
355 /* Return TRUE when LOOP should be optimized for speed. */
357 bool
358 optimize_loop_for_speed_p (struct loop *loop)
360 return optimize_bb_for_speed_p (loop->header);
363 /* Return TRUE when LOOP nest should be optimized for speed. */
365 bool
366 optimize_loop_nest_for_speed_p (struct loop *loop)
368 struct loop *l = loop;
369 if (optimize_loop_for_speed_p (loop))
370 return true;
371 l = loop->inner;
372 while (l && l != loop)
374 if (optimize_loop_for_speed_p (l))
375 return true;
376 if (l->inner)
377 l = l->inner;
378 else if (l->next)
379 l = l->next;
380 else
382 while (l != loop && !l->next)
383 l = loop_outer (l);
384 if (l != loop)
385 l = l->next;
388 return false;
391 /* Return TRUE when LOOP nest should be optimized for size. */
393 bool
394 optimize_loop_nest_for_size_p (struct loop *loop)
396 return !optimize_loop_nest_for_speed_p (loop);
399 /* Return true when edge E is likely to be well predictable by branch
400 predictor. */
402 bool
403 predictable_edge_p (edge e)
405 if (!e->probability.initialized_p ())
406 return false;
407 if ((e->probability.to_reg_br_prob_base ()
408 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
409 || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
410 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
411 return true;
412 return false;
416 /* Set RTL expansion for BB profile. */
418 void
419 rtl_profile_for_bb (basic_block bb)
421 crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
424 /* Set RTL expansion for edge profile. */
426 void
427 rtl_profile_for_edge (edge e)
429 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
432 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
433 void
434 default_rtl_profile (void)
436 crtl->maybe_hot_insn_p = true;
439 /* Return true if the one of outgoing edges is already predicted by
440 PREDICTOR. */
442 bool
443 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
445 rtx note;
446 if (!INSN_P (BB_END (bb)))
447 return false;
448 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
449 if (REG_NOTE_KIND (note) == REG_BR_PRED
450 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
451 return true;
452 return false;
455 /* Structure representing predictions in tree level. */
457 struct edge_prediction {
458 struct edge_prediction *ep_next;
459 edge ep_edge;
460 enum br_predictor ep_predictor;
461 int ep_probability;
464 /* This map contains for a basic block the list of predictions for the
465 outgoing edges. */
467 static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
469 /* Return true if the one of outgoing edges is already predicted by
470 PREDICTOR. */
472 bool
473 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
475 struct edge_prediction *i;
476 edge_prediction **preds = bb_predictions->get (bb);
478 if (!preds)
479 return false;
481 for (i = *preds; i; i = i->ep_next)
482 if (i->ep_predictor == predictor)
483 return true;
484 return false;
487 /* Return true if the one of outgoing edges is already predicted by
488 PREDICTOR for edge E predicted as TAKEN. */
490 bool
491 edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
493 struct edge_prediction *i;
494 basic_block bb = e->src;
495 edge_prediction **preds = bb_predictions->get (bb);
496 if (!preds)
497 return false;
499 int probability = predictor_info[(int) predictor].hitrate;
501 if (taken != TAKEN)
502 probability = REG_BR_PROB_BASE - probability;
504 for (i = *preds; i; i = i->ep_next)
505 if (i->ep_predictor == predictor
506 && i->ep_edge == e
507 && i->ep_probability == probability)
508 return true;
509 return false;
512 /* Same predicate as above, working on edges. */
513 bool
514 edge_probability_reliable_p (const_edge e)
516 return e->probability.probably_reliable_p ();
519 /* Same predicate as edge_probability_reliable_p, working on notes. */
520 bool
521 br_prob_note_reliable_p (const_rtx note)
523 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
524 return profile_probability::from_reg_br_prob_note
525 (XINT (note, 0)).probably_reliable_p ();
528 static void
529 predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
531 gcc_assert (any_condjump_p (insn));
532 if (!flag_guess_branch_prob)
533 return;
535 add_reg_note (insn, REG_BR_PRED,
536 gen_rtx_CONCAT (VOIDmode,
537 GEN_INT ((int) predictor),
538 GEN_INT ((int) probability)));
541 /* Predict insn by given predictor. */
543 void
544 predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
545 enum prediction taken)
547 int probability = predictor_info[(int) predictor].hitrate;
549 if (taken != TAKEN)
550 probability = REG_BR_PROB_BASE - probability;
552 predict_insn (insn, predictor, probability);
555 /* Predict edge E with given probability if possible. */
557 void
558 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
560 rtx_insn *last_insn;
561 last_insn = BB_END (e->src);
563 /* We can store the branch prediction information only about
564 conditional jumps. */
565 if (!any_condjump_p (last_insn))
566 return;
568 /* We always store probability of branching. */
569 if (e->flags & EDGE_FALLTHRU)
570 probability = REG_BR_PROB_BASE - probability;
572 predict_insn (last_insn, predictor, probability);
575 /* Predict edge E with the given PROBABILITY. */
576 void
577 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
579 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
580 && EDGE_COUNT (e->src->succs) > 1
581 && flag_guess_branch_prob
582 && optimize)
584 struct edge_prediction *i = XNEW (struct edge_prediction);
585 edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
587 i->ep_next = preds;
588 preds = i;
589 i->ep_probability = probability;
590 i->ep_predictor = predictor;
591 i->ep_edge = e;
595 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
596 to the filter function. */
598 void
599 filter_predictions (edge_prediction **preds,
600 bool (*filter) (edge_prediction *, void *), void *data)
602 if (!bb_predictions)
603 return;
605 if (preds)
607 struct edge_prediction **prediction = preds;
608 struct edge_prediction *next;
610 while (*prediction)
612 if ((*filter) (*prediction, data))
613 prediction = &((*prediction)->ep_next);
614 else
616 next = (*prediction)->ep_next;
617 free (*prediction);
618 *prediction = next;
624 /* Filter function predicate that returns true for a edge predicate P
625 if its edge is equal to DATA. */
627 bool
628 equal_edge_p (edge_prediction *p, void *data)
630 return p->ep_edge == (edge)data;
633 /* Remove all predictions on given basic block that are attached
634 to edge E. */
635 void
636 remove_predictions_associated_with_edge (edge e)
638 if (!bb_predictions)
639 return;
641 edge_prediction **preds = bb_predictions->get (e->src);
642 filter_predictions (preds, equal_edge_p, e);
645 /* Clears the list of predictions stored for BB. */
647 static void
648 clear_bb_predictions (basic_block bb)
650 edge_prediction **preds = bb_predictions->get (bb);
651 struct edge_prediction *pred, *next;
653 if (!preds)
654 return;
656 for (pred = *preds; pred; pred = next)
658 next = pred->ep_next;
659 free (pred);
661 *preds = NULL;
664 /* Return true when we can store prediction on insn INSN.
665 At the moment we represent predictions only on conditional
666 jumps, not at computed jump or other complicated cases. */
667 static bool
668 can_predict_insn_p (const rtx_insn *insn)
670 return (JUMP_P (insn)
671 && any_condjump_p (insn)
672 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
675 /* Predict edge E by given predictor if possible. */
677 void
678 predict_edge_def (edge e, enum br_predictor predictor,
679 enum prediction taken)
681 int probability = predictor_info[(int) predictor].hitrate;
683 if (taken != TAKEN)
684 probability = REG_BR_PROB_BASE - probability;
686 predict_edge (e, predictor, probability);
689 /* Invert all branch predictions or probability notes in the INSN. This needs
690 to be done each time we invert the condition used by the jump. */
692 void
693 invert_br_probabilities (rtx insn)
695 rtx note;
697 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
698 if (REG_NOTE_KIND (note) == REG_BR_PROB)
699 XINT (note, 0) = profile_probability::from_reg_br_prob_note
700 (XINT (note, 0)).invert ().to_reg_br_prob_note ();
701 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
702 XEXP (XEXP (note, 0), 1)
703 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
706 /* Dump information about the branch prediction to the output file. */
708 static void
709 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
710 basic_block bb, enum predictor_reason reason = REASON_NONE,
711 edge ep_edge = NULL)
713 edge e = ep_edge;
714 edge_iterator ei;
716 if (!file)
717 return;
719 if (e == NULL)
720 FOR_EACH_EDGE (e, ei, bb->succs)
721 if (! (e->flags & EDGE_FALLTHRU))
722 break;
724 char edge_info_str[128];
725 if (ep_edge)
726 sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
727 ep_edge->dest->index);
728 else
729 edge_info_str[0] = '\0';
731 fprintf (file, " %s heuristics%s%s: %.1f%%",
732 predictor_info[predictor].name,
733 edge_info_str, reason_messages[reason],
734 probability * 100.0 / REG_BR_PROB_BASE);
736 if (bb->count.initialized_p ())
738 fprintf (file, " exec ");
739 bb->count.dump (file);
740 if (e)
742 fprintf (file, " hit ");
743 e->count ().dump (file);
744 fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
745 / bb->count.to_gcov_type ());
749 fprintf (file, "\n");
752 /* Return true if STMT is known to be unlikely executed. */
754 static bool
755 unlikely_executed_stmt_p (gimple *stmt)
757 if (!is_gimple_call (stmt))
758 return false;
759 /* NORETURN attribute alone is not strong enough: exit() may be quite
760 likely executed once during program run. */
761 if (gimple_call_fntype (stmt)
762 && lookup_attribute ("cold",
763 TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
764 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
765 return true;
766 tree decl = gimple_call_fndecl (stmt);
767 if (!decl)
768 return false;
769 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
770 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
771 return true;
773 cgraph_node *n = cgraph_node::get (decl);
774 if (!n)
775 return false;
777 availability avail;
778 n = n->ultimate_alias_target (&avail);
779 if (avail < AVAIL_AVAILABLE)
780 return false;
781 if (!n->analyzed
782 || n->decl == current_function_decl)
783 return false;
784 return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
787 /* Return true if BB is unlikely executed. */
789 static bool
790 unlikely_executed_bb_p (basic_block bb)
792 if (bb->count == profile_count::zero ())
793 return true;
794 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
795 return false;
796 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
797 !gsi_end_p (gsi); gsi_next (&gsi))
799 if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
800 return true;
801 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
802 return false;
804 return false;
807 /* We can not predict the probabilities of outgoing edges of bb. Set them
808 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
809 even probability for all edges not mentioned in the set. These edges
810 are given PROB_VERY_UNLIKELY probability. */
812 static void
813 set_even_probabilities (basic_block bb,
814 hash_set<edge> *unlikely_edges = NULL)
816 unsigned nedges = 0, unlikely_count = 0;
817 edge e = NULL;
818 edge_iterator ei;
819 profile_probability all = profile_probability::always ();
821 FOR_EACH_EDGE (e, ei, bb->succs)
822 if (e->probability.initialized_p ())
823 all -= e->probability;
824 else if (!unlikely_executed_edge_p (e))
826 nedges ++;
827 if (unlikely_edges != NULL && unlikely_edges->contains (e))
829 all -= profile_probability::very_unlikely ();
830 unlikely_count++;
834 /* Make the distribution even if all edges are unlikely. */
835 if (unlikely_count == nedges)
837 unlikely_edges = NULL;
838 unlikely_count = 0;
841 unsigned c = nedges - unlikely_count;
843 FOR_EACH_EDGE (e, ei, bb->succs)
844 if (e->probability.initialized_p ())
846 else if (!unlikely_executed_edge_p (e))
848 if (unlikely_edges != NULL && unlikely_edges->contains (e))
849 e->probability = profile_probability::very_unlikely ();
850 else
851 e->probability = all.apply_scale (1, c).guessed ();
853 else
854 e->probability = profile_probability::never ();
857 /* Add REG_BR_PROB note to JUMP with PROB. */
859 void
860 add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
862 gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
863 add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
866 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
867 note if not already present. Remove now useless REG_BR_PRED notes. */
869 static void
870 combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
872 rtx prob_note;
873 rtx *pnote;
874 rtx note;
875 int best_probability = PROB_EVEN;
876 enum br_predictor best_predictor = END_PREDICTORS;
877 int combined_probability = REG_BR_PROB_BASE / 2;
878 int d;
879 bool first_match = false;
880 bool found = false;
882 if (!can_predict_insn_p (insn))
884 set_even_probabilities (bb);
885 return;
888 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
889 pnote = &REG_NOTES (insn);
890 if (dump_file)
891 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
892 bb->index);
894 /* We implement "first match" heuristics and use probability guessed
895 by predictor with smallest index. */
896 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
897 if (REG_NOTE_KIND (note) == REG_BR_PRED)
899 enum br_predictor predictor = ((enum br_predictor)
900 INTVAL (XEXP (XEXP (note, 0), 0)));
901 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
903 found = true;
904 if (best_predictor > predictor
905 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
906 best_probability = probability, best_predictor = predictor;
908 d = (combined_probability * probability
909 + (REG_BR_PROB_BASE - combined_probability)
910 * (REG_BR_PROB_BASE - probability));
912 /* Use FP math to avoid overflows of 32bit integers. */
913 if (d == 0)
914 /* If one probability is 0% and one 100%, avoid division by zero. */
915 combined_probability = REG_BR_PROB_BASE / 2;
916 else
917 combined_probability = (((double) combined_probability) * probability
918 * REG_BR_PROB_BASE / d + 0.5);
921 /* Decide which heuristic to use. In case we didn't match anything,
922 use no_prediction heuristic, in case we did match, use either
923 first match or Dempster-Shaffer theory depending on the flags. */
925 if (best_predictor != END_PREDICTORS)
926 first_match = true;
928 if (!found)
929 dump_prediction (dump_file, PRED_NO_PREDICTION,
930 combined_probability, bb);
931 else
933 if (!first_match)
934 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
935 bb, !first_match ? REASON_NONE : REASON_IGNORED);
936 else
937 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
938 bb, first_match ? REASON_NONE : REASON_IGNORED);
941 if (first_match)
942 combined_probability = best_probability;
943 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
945 while (*pnote)
947 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
949 enum br_predictor predictor = ((enum br_predictor)
950 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
951 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
953 dump_prediction (dump_file, predictor, probability, bb,
954 (!first_match || best_predictor == predictor)
955 ? REASON_NONE : REASON_IGNORED);
956 *pnote = XEXP (*pnote, 1);
958 else
959 pnote = &XEXP (*pnote, 1);
962 if (!prob_note)
964 profile_probability p
965 = profile_probability::from_reg_br_prob_base (combined_probability);
966 add_reg_br_prob_note (insn, p);
968 /* Save the prediction into CFG in case we are seeing non-degenerated
969 conditional jump. */
970 if (!single_succ_p (bb))
972 BRANCH_EDGE (bb)->probability = p;
973 FALLTHRU_EDGE (bb)->probability
974 = BRANCH_EDGE (bb)->probability.invert ();
977 else if (!single_succ_p (bb))
979 profile_probability prob = profile_probability::from_reg_br_prob_note
980 (XINT (prob_note, 0));
982 BRANCH_EDGE (bb)->probability = prob;
983 FALLTHRU_EDGE (bb)->probability = prob.invert ();
985 else
986 single_succ_edge (bb)->probability = profile_probability::always ();
989 /* Edge prediction hash traits. */
991 struct predictor_hash: pointer_hash <edge_prediction>
994 static inline hashval_t hash (const edge_prediction *);
995 static inline bool equal (const edge_prediction *, const edge_prediction *);
998 /* Calculate hash value of an edge prediction P based on predictor and
999 normalized probability. */
1001 inline hashval_t
1002 predictor_hash::hash (const edge_prediction *p)
1004 inchash::hash hstate;
1005 hstate.add_int (p->ep_predictor);
1007 int prob = p->ep_probability;
1008 if (prob > REG_BR_PROB_BASE / 2)
1009 prob = REG_BR_PROB_BASE - prob;
1011 hstate.add_int (prob);
1013 return hstate.end ();
1016 /* Return true whether edge predictions P1 and P2 use the same predictor and
1017 have equal (or opposed probability). */
1019 inline bool
1020 predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1022 return (p1->ep_predictor == p2->ep_predictor
1023 && (p1->ep_probability == p2->ep_probability
1024 || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1027 struct predictor_hash_traits: predictor_hash,
1028 typed_noop_remove <edge_prediction *> {};
1030 /* Return true if edge prediction P is not in DATA hash set. */
1032 static bool
1033 not_removed_prediction_p (edge_prediction *p, void *data)
1035 hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1036 return !remove->contains (p);
1039 /* Prune predictions for a basic block BB. Currently we do following
1040 clean-up steps:
1042 1) remove duplicate prediction that is guessed with the same probability
1043 (different than 1/2) to both edge
1044 2) remove duplicates for a prediction that belongs with the same probability
1045 to a single edge
1049 static void
1050 prune_predictions_for_bb (basic_block bb)
1052 edge_prediction **preds = bb_predictions->get (bb);
1054 if (preds)
1056 hash_table <predictor_hash_traits> s (13);
1057 hash_set <edge_prediction *> remove;
1059 /* Step 1: identify predictors that should be removed. */
1060 for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1062 edge_prediction *existing = s.find (pred);
1063 if (existing)
1065 if (pred->ep_edge == existing->ep_edge
1066 && pred->ep_probability == existing->ep_probability)
1068 /* Remove a duplicate predictor. */
1069 dump_prediction (dump_file, pred->ep_predictor,
1070 pred->ep_probability, bb,
1071 REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1073 remove.add (pred);
1075 else if (pred->ep_edge != existing->ep_edge
1076 && pred->ep_probability == existing->ep_probability
1077 && pred->ep_probability != REG_BR_PROB_BASE / 2)
1079 /* Remove both predictors as they predict the same
1080 for both edges. */
1081 dump_prediction (dump_file, existing->ep_predictor,
1082 pred->ep_probability, bb,
1083 REASON_EDGE_PAIR_DUPLICATE,
1084 existing->ep_edge);
1085 dump_prediction (dump_file, pred->ep_predictor,
1086 pred->ep_probability, bb,
1087 REASON_EDGE_PAIR_DUPLICATE,
1088 pred->ep_edge);
1090 remove.add (existing);
1091 remove.add (pred);
1095 edge_prediction **slot2 = s.find_slot (pred, INSERT);
1096 *slot2 = pred;
1099 /* Step 2: Remove predictors. */
1100 filter_predictions (preds, not_removed_prediction_p, &remove);
1104 /* Combine predictions into single probability and store them into CFG.
1105 Remove now useless prediction entries.
1106 If DRY_RUN is set, only produce dumps and do not modify profile. */
1108 static void
1109 combine_predictions_for_bb (basic_block bb, bool dry_run)
1111 int best_probability = PROB_EVEN;
1112 enum br_predictor best_predictor = END_PREDICTORS;
1113 int combined_probability = REG_BR_PROB_BASE / 2;
1114 int d;
1115 bool first_match = false;
1116 bool found = false;
1117 struct edge_prediction *pred;
1118 int nedges = 0;
1119 edge e, first = NULL, second = NULL;
1120 edge_iterator ei;
1121 int nzero = 0;
1122 int nunknown = 0;
1124 FOR_EACH_EDGE (e, ei, bb->succs)
1126 if (!unlikely_executed_edge_p (e))
1128 nedges ++;
1129 if (first && !second)
1130 second = e;
1131 if (!first)
1132 first = e;
1134 else if (!e->probability.initialized_p ())
1135 e->probability = profile_probability::never ();
1136 if (!e->probability.initialized_p ())
1137 nunknown++;
1138 else if (e->probability == profile_probability::never ())
1139 nzero++;
1142 /* When there is no successor or only one choice, prediction is easy.
1144 When we have a basic block with more than 2 successors, the situation
1145 is more complicated as DS theory cannot be used literally.
1146 More precisely, let's assume we predicted edge e1 with probability p1,
1147 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1148 need to find probability of e.g. m1({b2}), which we don't know.
1149 The only approximation is to equally distribute 1-p1 to all edges
1150 different from b1.
1152 According to numbers we've got from SPEC2006 benchark, there's only
1153 one interesting reliable predictor (noreturn call), which can be
1154 handled with a bit easier approach. */
1155 if (nedges != 2)
1157 hash_set<edge> unlikely_edges (4);
1159 /* Identify all edges that have a probability close to very unlikely.
1160 Doing the approach for very unlikely doesn't worth for doing as
1161 there's no such probability in SPEC2006 benchmark. */
1162 edge_prediction **preds = bb_predictions->get (bb);
1163 if (preds)
1164 for (pred = *preds; pred; pred = pred->ep_next)
1165 if (pred->ep_probability <= PROB_VERY_UNLIKELY)
1166 unlikely_edges.add (pred->ep_edge);
1168 if (!dry_run)
1169 set_even_probabilities (bb, &unlikely_edges);
1170 clear_bb_predictions (bb);
1171 if (dump_file)
1173 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1174 if (unlikely_edges.elements () == 0)
1175 fprintf (dump_file,
1176 "%i edges in bb %i predicted to even probabilities\n",
1177 nedges, bb->index);
1178 else
1180 fprintf (dump_file,
1181 "%i edges in bb %i predicted with some unlikely edges\n",
1182 nedges, bb->index);
1183 FOR_EACH_EDGE (e, ei, bb->succs)
1184 if (!unlikely_executed_edge_p (e))
1185 dump_prediction (dump_file, PRED_COMBINED,
1186 e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
1189 return;
1192 if (dump_file)
1193 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1195 prune_predictions_for_bb (bb);
1197 edge_prediction **preds = bb_predictions->get (bb);
1199 if (preds)
1201 /* We implement "first match" heuristics and use probability guessed
1202 by predictor with smallest index. */
1203 for (pred = *preds; pred; pred = pred->ep_next)
1205 enum br_predictor predictor = pred->ep_predictor;
1206 int probability = pred->ep_probability;
1208 if (pred->ep_edge != first)
1209 probability = REG_BR_PROB_BASE - probability;
1211 found = true;
1212 /* First match heuristics would be widly confused if we predicted
1213 both directions. */
1214 if (best_predictor > predictor
1215 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1217 struct edge_prediction *pred2;
1218 int prob = probability;
1220 for (pred2 = (struct edge_prediction *) *preds;
1221 pred2; pred2 = pred2->ep_next)
1222 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1224 int probability2 = pred2->ep_probability;
1226 if (pred2->ep_edge != first)
1227 probability2 = REG_BR_PROB_BASE - probability2;
1229 if ((probability < REG_BR_PROB_BASE / 2) !=
1230 (probability2 < REG_BR_PROB_BASE / 2))
1231 break;
1233 /* If the same predictor later gave better result, go for it! */
1234 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1235 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1236 prob = probability2;
1238 if (!pred2)
1239 best_probability = prob, best_predictor = predictor;
1242 d = (combined_probability * probability
1243 + (REG_BR_PROB_BASE - combined_probability)
1244 * (REG_BR_PROB_BASE - probability));
1246 /* Use FP math to avoid overflows of 32bit integers. */
1247 if (d == 0)
1248 /* If one probability is 0% and one 100%, avoid division by zero. */
1249 combined_probability = REG_BR_PROB_BASE / 2;
1250 else
1251 combined_probability = (((double) combined_probability)
1252 * probability
1253 * REG_BR_PROB_BASE / d + 0.5);
1257 /* Decide which heuristic to use. In case we didn't match anything,
1258 use no_prediction heuristic, in case we did match, use either
1259 first match or Dempster-Shaffer theory depending on the flags. */
1261 if (best_predictor != END_PREDICTORS)
1262 first_match = true;
1264 if (!found)
1265 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1266 else
1268 if (!first_match)
1269 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1270 !first_match ? REASON_NONE : REASON_IGNORED);
1271 else
1272 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1273 first_match ? REASON_NONE : REASON_IGNORED);
1276 if (first_match)
1277 combined_probability = best_probability;
1278 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1280 if (preds)
1282 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1284 enum br_predictor predictor = pred->ep_predictor;
1285 int probability = pred->ep_probability;
1287 dump_prediction (dump_file, predictor, probability, bb,
1288 (!first_match || best_predictor == predictor)
1289 ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1292 clear_bb_predictions (bb);
1295 /* If we have only one successor which is unknown, we can compute missing
1296 probablity. */
1297 if (nunknown == 1)
1299 profile_probability prob = profile_probability::always ();
1300 edge missing = NULL;
1302 FOR_EACH_EDGE (e, ei, bb->succs)
1303 if (e->probability.initialized_p ())
1304 prob -= e->probability;
1305 else if (missing == NULL)
1306 missing = e;
1307 else
1308 gcc_unreachable ();
1309 missing->probability = prob;
1311 /* If nothing is unknown, we have nothing to update. */
1312 else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1314 else if (!dry_run)
1316 first->probability
1317 = profile_probability::from_reg_br_prob_base (combined_probability);
1318 second->probability = first->probability.invert ();
1322 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1323 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1325 T1 and T2 should be one of the following cases:
1326 1. T1 is SSA_NAME, T2 is NULL
1327 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1328 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1330 static tree
1331 strips_small_constant (tree t1, tree t2)
1333 tree ret = NULL;
1334 int value = 0;
1336 if (!t1)
1337 return NULL;
1338 else if (TREE_CODE (t1) == SSA_NAME)
1339 ret = t1;
1340 else if (tree_fits_shwi_p (t1))
1341 value = tree_to_shwi (t1);
1342 else
1343 return NULL;
1345 if (!t2)
1346 return ret;
1347 else if (tree_fits_shwi_p (t2))
1348 value = tree_to_shwi (t2);
1349 else if (TREE_CODE (t2) == SSA_NAME)
1351 if (ret)
1352 return NULL;
1353 else
1354 ret = t2;
1357 if (value <= 4 && value >= -4)
1358 return ret;
1359 else
1360 return NULL;
1363 /* Return the SSA_NAME in T or T's operands.
1364 Return NULL if SSA_NAME cannot be found. */
1366 static tree
1367 get_base_value (tree t)
1369 if (TREE_CODE (t) == SSA_NAME)
1370 return t;
1372 if (!BINARY_CLASS_P (t))
1373 return NULL;
1375 switch (TREE_OPERAND_LENGTH (t))
1377 case 1:
1378 return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1379 case 2:
1380 return strips_small_constant (TREE_OPERAND (t, 0),
1381 TREE_OPERAND (t, 1));
1382 default:
1383 return NULL;
1387 /* Check the compare STMT in LOOP. If it compares an induction
1388 variable to a loop invariant, return true, and save
1389 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1390 Otherwise return false and set LOOP_INVAIANT to NULL. */
1392 static bool
1393 is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
1394 tree *loop_invariant,
1395 enum tree_code *compare_code,
1396 tree *loop_step,
1397 tree *loop_iv_base)
1399 tree op0, op1, bound, base;
1400 affine_iv iv0, iv1;
1401 enum tree_code code;
1402 tree step;
1404 code = gimple_cond_code (stmt);
1405 *loop_invariant = NULL;
1407 switch (code)
1409 case GT_EXPR:
1410 case GE_EXPR:
1411 case NE_EXPR:
1412 case LT_EXPR:
1413 case LE_EXPR:
1414 case EQ_EXPR:
1415 break;
1417 default:
1418 return false;
1421 op0 = gimple_cond_lhs (stmt);
1422 op1 = gimple_cond_rhs (stmt);
1424 if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1425 || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1426 return false;
1427 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1428 return false;
1429 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1430 return false;
1431 if (TREE_CODE (iv0.step) != INTEGER_CST
1432 || TREE_CODE (iv1.step) != INTEGER_CST)
1433 return false;
1434 if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1435 || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1436 return false;
1438 if (integer_zerop (iv0.step))
1440 if (code != NE_EXPR && code != EQ_EXPR)
1441 code = invert_tree_comparison (code, false);
1442 bound = iv0.base;
1443 base = iv1.base;
1444 if (tree_fits_shwi_p (iv1.step))
1445 step = iv1.step;
1446 else
1447 return false;
1449 else
1451 bound = iv1.base;
1452 base = iv0.base;
1453 if (tree_fits_shwi_p (iv0.step))
1454 step = iv0.step;
1455 else
1456 return false;
1459 if (TREE_CODE (bound) != INTEGER_CST)
1460 bound = get_base_value (bound);
1461 if (!bound)
1462 return false;
1463 if (TREE_CODE (base) != INTEGER_CST)
1464 base = get_base_value (base);
1465 if (!base)
1466 return false;
1468 *loop_invariant = bound;
1469 *compare_code = code;
1470 *loop_step = step;
1471 *loop_iv_base = base;
1472 return true;
1475 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1477 static bool
1478 expr_coherent_p (tree t1, tree t2)
1480 gimple *stmt;
1481 tree ssa_name_1 = NULL;
1482 tree ssa_name_2 = NULL;
1484 gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1485 gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1487 if (t1 == t2)
1488 return true;
1490 if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1491 return true;
1492 if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1493 return false;
1495 /* Check to see if t1 is expressed/defined with t2. */
1496 stmt = SSA_NAME_DEF_STMT (t1);
1497 gcc_assert (stmt != NULL);
1498 if (is_gimple_assign (stmt))
1500 ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1501 if (ssa_name_1 && ssa_name_1 == t2)
1502 return true;
1505 /* Check to see if t2 is expressed/defined with t1. */
1506 stmt = SSA_NAME_DEF_STMT (t2);
1507 gcc_assert (stmt != NULL);
1508 if (is_gimple_assign (stmt))
1510 ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1511 if (ssa_name_2 && ssa_name_2 == t1)
1512 return true;
1515 /* Compare if t1 and t2's def_stmts are identical. */
1516 if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1517 return true;
1518 else
1519 return false;
1522 /* Return true if E is predicted by one of loop heuristics. */
1524 static bool
1525 predicted_by_loop_heuristics_p (basic_block bb)
1527 struct edge_prediction *i;
1528 edge_prediction **preds = bb_predictions->get (bb);
1530 if (!preds)
1531 return false;
1533 for (i = *preds; i; i = i->ep_next)
1534 if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1535 || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1536 || i->ep_predictor == PRED_LOOP_ITERATIONS
1537 || i->ep_predictor == PRED_LOOP_EXIT
1538 || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1539 || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1540 return true;
1541 return false;
1544 /* Predict branch probability of BB when BB contains a branch that compares
1545 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1546 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1548 E.g.
1549 for (int i = 0; i < bound; i++) {
1550 if (i < bound - 2)
1551 computation_1();
1552 else
1553 computation_2();
1556 In this loop, we will predict the branch inside the loop to be taken. */
1558 static void
1559 predict_iv_comparison (struct loop *loop, basic_block bb,
1560 tree loop_bound_var,
1561 tree loop_iv_base_var,
1562 enum tree_code loop_bound_code,
1563 int loop_bound_step)
1565 gimple *stmt;
1566 tree compare_var, compare_base;
1567 enum tree_code compare_code;
1568 tree compare_step_var;
1569 edge then_edge;
1570 edge_iterator ei;
1572 if (predicted_by_loop_heuristics_p (bb))
1573 return;
1575 stmt = last_stmt (bb);
1576 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1577 return;
1578 if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
1579 loop, &compare_var,
1580 &compare_code,
1581 &compare_step_var,
1582 &compare_base))
1583 return;
1585 /* Find the taken edge. */
1586 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1587 if (then_edge->flags & EDGE_TRUE_VALUE)
1588 break;
1590 /* When comparing an IV to a loop invariant, NE is more likely to be
1591 taken while EQ is more likely to be not-taken. */
1592 if (compare_code == NE_EXPR)
1594 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1595 return;
1597 else if (compare_code == EQ_EXPR)
1599 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1600 return;
1603 if (!expr_coherent_p (loop_iv_base_var, compare_base))
1604 return;
1606 /* If loop bound, base and compare bound are all constants, we can
1607 calculate the probability directly. */
1608 if (tree_fits_shwi_p (loop_bound_var)
1609 && tree_fits_shwi_p (compare_var)
1610 && tree_fits_shwi_p (compare_base))
1612 int probability;
1613 bool overflow, overall_overflow = false;
1614 widest_int compare_count, tem;
1616 /* (loop_bound - base) / compare_step */
1617 tem = wi::sub (wi::to_widest (loop_bound_var),
1618 wi::to_widest (compare_base), SIGNED, &overflow);
1619 overall_overflow |= overflow;
1620 widest_int loop_count = wi::div_trunc (tem,
1621 wi::to_widest (compare_step_var),
1622 SIGNED, &overflow);
1623 overall_overflow |= overflow;
1625 if (!wi::neg_p (wi::to_widest (compare_step_var))
1626 ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1628 /* (loop_bound - compare_bound) / compare_step */
1629 tem = wi::sub (wi::to_widest (loop_bound_var),
1630 wi::to_widest (compare_var), SIGNED, &overflow);
1631 overall_overflow |= overflow;
1632 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1633 SIGNED, &overflow);
1634 overall_overflow |= overflow;
1636 else
1638 /* (compare_bound - base) / compare_step */
1639 tem = wi::sub (wi::to_widest (compare_var),
1640 wi::to_widest (compare_base), SIGNED, &overflow);
1641 overall_overflow |= overflow;
1642 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1643 SIGNED, &overflow);
1644 overall_overflow |= overflow;
1646 if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1647 ++compare_count;
1648 if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1649 ++loop_count;
1650 if (wi::neg_p (compare_count))
1651 compare_count = 0;
1652 if (wi::neg_p (loop_count))
1653 loop_count = 0;
1654 if (loop_count == 0)
1655 probability = 0;
1656 else if (wi::cmps (compare_count, loop_count) == 1)
1657 probability = REG_BR_PROB_BASE;
1658 else
1660 tem = compare_count * REG_BR_PROB_BASE;
1661 tem = wi::udiv_trunc (tem, loop_count);
1662 probability = tem.to_uhwi ();
1665 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1666 if (!overall_overflow)
1667 predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1669 return;
1672 if (expr_coherent_p (loop_bound_var, compare_var))
1674 if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1675 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1676 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1677 else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1678 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1679 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1680 else if (loop_bound_code == NE_EXPR)
1682 /* If the loop backedge condition is "(i != bound)", we do
1683 the comparison based on the step of IV:
1684 * step < 0 : backedge condition is like (i > bound)
1685 * step > 0 : backedge condition is like (i < bound) */
1686 gcc_assert (loop_bound_step != 0);
1687 if (loop_bound_step > 0
1688 && (compare_code == LT_EXPR
1689 || compare_code == LE_EXPR))
1690 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1691 else if (loop_bound_step < 0
1692 && (compare_code == GT_EXPR
1693 || compare_code == GE_EXPR))
1694 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1695 else
1696 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1698 else
1699 /* The branch is predicted not-taken if loop_bound_code is
1700 opposite with compare_code. */
1701 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1703 else if (expr_coherent_p (loop_iv_base_var, compare_var))
1705 /* For cases like:
1706 for (i = s; i < h; i++)
1707 if (i > s + 2) ....
1708 The branch should be predicted taken. */
1709 if (loop_bound_step > 0
1710 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1711 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1712 else if (loop_bound_step < 0
1713 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1714 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1715 else
1716 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1720 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1721 exits are resulted from short-circuit conditions that will generate an
1722 if_tmp. E.g.:
1724 if (foo() || global > 10)
1725 break;
1727 This will be translated into:
1729 BB3:
1730 loop header...
1731 BB4:
1732 if foo() goto BB6 else goto BB5
1733 BB5:
1734 if global > 10 goto BB6 else goto BB7
1735 BB6:
1736 goto BB7
1737 BB7:
1738 iftmp = (PHI 0(BB5), 1(BB6))
1739 if iftmp == 1 goto BB8 else goto BB3
1740 BB8:
1741 outside of the loop...
1743 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1744 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1745 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1746 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1748 static void
1749 predict_extra_loop_exits (edge exit_edge)
1751 unsigned i;
1752 bool check_value_one;
1753 gimple *lhs_def_stmt;
1754 gphi *phi_stmt;
1755 tree cmp_rhs, cmp_lhs;
1756 gimple *last;
1757 gcond *cmp_stmt;
1759 last = last_stmt (exit_edge->src);
1760 if (!last)
1761 return;
1762 cmp_stmt = dyn_cast <gcond *> (last);
1763 if (!cmp_stmt)
1764 return;
1766 cmp_rhs = gimple_cond_rhs (cmp_stmt);
1767 cmp_lhs = gimple_cond_lhs (cmp_stmt);
1768 if (!TREE_CONSTANT (cmp_rhs)
1769 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1770 return;
1771 if (TREE_CODE (cmp_lhs) != SSA_NAME)
1772 return;
1774 /* If check_value_one is true, only the phi_args with value '1' will lead
1775 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1776 loop exit. */
1777 check_value_one = (((integer_onep (cmp_rhs))
1778 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1779 ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1781 lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1782 if (!lhs_def_stmt)
1783 return;
1785 phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1786 if (!phi_stmt)
1787 return;
1789 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1791 edge e1;
1792 edge_iterator ei;
1793 tree val = gimple_phi_arg_def (phi_stmt, i);
1794 edge e = gimple_phi_arg_edge (phi_stmt, i);
1796 if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1797 continue;
1798 if ((check_value_one ^ integer_onep (val)) == 1)
1799 continue;
1800 if (EDGE_COUNT (e->src->succs) != 1)
1802 predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1803 continue;
1806 FOR_EACH_EDGE (e1, ei, e->src->preds)
1807 predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1812 /* Predict edge probabilities by exploiting loop structure. */
1814 static void
1815 predict_loops (void)
1817 struct loop *loop;
1818 basic_block bb;
1819 hash_set <struct loop *> with_recursion(10);
1821 FOR_EACH_BB_FN (bb, cfun)
1823 gimple_stmt_iterator gsi;
1824 tree decl;
1826 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1827 if (is_gimple_call (gsi_stmt (gsi))
1828 && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1829 && recursive_call_p (current_function_decl, decl))
1831 loop = bb->loop_father;
1832 while (loop && !with_recursion.add (loop))
1833 loop = loop_outer (loop);
1837 /* Try to predict out blocks in a loop that are not part of a
1838 natural loop. */
1839 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1841 basic_block bb, *bbs;
1842 unsigned j, n_exits = 0;
1843 vec<edge> exits;
1844 struct tree_niter_desc niter_desc;
1845 edge ex;
1846 struct nb_iter_bound *nb_iter;
1847 enum tree_code loop_bound_code = ERROR_MARK;
1848 tree loop_bound_step = NULL;
1849 tree loop_bound_var = NULL;
1850 tree loop_iv_base = NULL;
1851 gcond *stmt = NULL;
1852 bool recursion = with_recursion.contains (loop);
1854 exits = get_loop_exit_edges (loop);
1855 FOR_EACH_VEC_ELT (exits, j, ex)
1856 if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
1857 n_exits ++;
1858 if (!n_exits)
1860 exits.release ();
1861 continue;
1864 if (dump_file && (dump_flags & TDF_DETAILS))
1865 fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
1866 loop->num, recursion ? " (with recursion)":"", n_exits);
1867 if (dump_file && (dump_flags & TDF_DETAILS)
1868 && max_loop_iterations_int (loop) >= 0)
1870 fprintf (dump_file,
1871 "Loop %d iterates at most %i times.\n", loop->num,
1872 (int)max_loop_iterations_int (loop));
1874 if (dump_file && (dump_flags & TDF_DETAILS)
1875 && likely_max_loop_iterations_int (loop) >= 0)
1877 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1878 loop->num, (int)likely_max_loop_iterations_int (loop));
1881 FOR_EACH_VEC_ELT (exits, j, ex)
1883 tree niter = NULL;
1884 HOST_WIDE_INT nitercst;
1885 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
1886 int probability;
1887 enum br_predictor predictor;
1888 widest_int nit;
1890 if (unlikely_executed_edge_p (ex)
1891 || (ex->flags & EDGE_ABNORMAL_CALL))
1892 continue;
1893 /* Loop heuristics do not expect exit conditional to be inside
1894 inner loop. We predict from innermost to outermost loop. */
1895 if (predicted_by_loop_heuristics_p (ex->src))
1897 if (dump_file && (dump_flags & TDF_DETAILS))
1898 fprintf (dump_file, "Skipping exit %i->%i because "
1899 "it is already predicted.\n",
1900 ex->src->index, ex->dest->index);
1901 continue;
1903 predict_extra_loop_exits (ex);
1905 if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
1906 niter = niter_desc.niter;
1907 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
1908 niter = loop_niter_by_eval (loop, ex);
1909 if (dump_file && (dump_flags & TDF_DETAILS)
1910 && TREE_CODE (niter) == INTEGER_CST)
1912 fprintf (dump_file, "Exit %i->%i %d iterates ",
1913 ex->src->index, ex->dest->index,
1914 loop->num);
1915 print_generic_expr (dump_file, niter, TDF_SLIM);
1916 fprintf (dump_file, " times.\n");
1919 if (TREE_CODE (niter) == INTEGER_CST)
1921 if (tree_fits_uhwi_p (niter)
1922 && max
1923 && compare_tree_int (niter, max - 1) == -1)
1924 nitercst = tree_to_uhwi (niter) + 1;
1925 else
1926 nitercst = max;
1927 predictor = PRED_LOOP_ITERATIONS;
1929 /* If we have just one exit and we can derive some information about
1930 the number of iterations of the loop from the statements inside
1931 the loop, use it to predict this exit. */
1932 else if (n_exits == 1
1933 && estimated_stmt_executions (loop, &nit))
1935 if (wi::gtu_p (nit, max))
1936 nitercst = max;
1937 else
1938 nitercst = nit.to_shwi ();
1939 predictor = PRED_LOOP_ITERATIONS_GUESSED;
1941 /* If we have likely upper bound, trust it for very small iteration
1942 counts. Such loops would otherwise get mispredicted by standard
1943 LOOP_EXIT heuristics. */
1944 else if (n_exits == 1
1945 && likely_max_stmt_executions (loop, &nit)
1946 && wi::ltu_p (nit,
1947 RDIV (REG_BR_PROB_BASE,
1948 REG_BR_PROB_BASE
1949 - predictor_info
1950 [recursion
1951 ? PRED_LOOP_EXIT_WITH_RECURSION
1952 : PRED_LOOP_EXIT].hitrate)))
1954 nitercst = nit.to_shwi ();
1955 predictor = PRED_LOOP_ITERATIONS_MAX;
1957 else
1959 if (dump_file && (dump_flags & TDF_DETAILS))
1960 fprintf (dump_file, "Nothing known about exit %i->%i.\n",
1961 ex->src->index, ex->dest->index);
1962 continue;
1965 if (dump_file && (dump_flags & TDF_DETAILS))
1966 fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
1967 (int)nitercst, predictor_info[predictor].name);
1968 /* If the prediction for number of iterations is zero, do not
1969 predict the exit edges. */
1970 if (nitercst == 0)
1971 continue;
1973 probability = RDIV (REG_BR_PROB_BASE, nitercst);
1974 predict_edge (ex, predictor, probability);
1976 exits.release ();
1978 /* Find information about loop bound variables. */
1979 for (nb_iter = loop->bounds; nb_iter;
1980 nb_iter = nb_iter->next)
1981 if (nb_iter->stmt
1982 && gimple_code (nb_iter->stmt) == GIMPLE_COND)
1984 stmt = as_a <gcond *> (nb_iter->stmt);
1985 break;
1987 if (!stmt && last_stmt (loop->header)
1988 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
1989 stmt = as_a <gcond *> (last_stmt (loop->header));
1990 if (stmt)
1991 is_comparison_with_loop_invariant_p (stmt, loop,
1992 &loop_bound_var,
1993 &loop_bound_code,
1994 &loop_bound_step,
1995 &loop_iv_base);
1997 bbs = get_loop_body (loop);
1999 for (j = 0; j < loop->num_nodes; j++)
2001 edge e;
2002 edge_iterator ei;
2004 bb = bbs[j];
2006 /* Bypass loop heuristics on continue statement. These
2007 statements construct loops via "non-loop" constructs
2008 in the source language and are better to be handled
2009 separately. */
2010 if (predicted_by_p (bb, PRED_CONTINUE))
2012 if (dump_file && (dump_flags & TDF_DETAILS))
2013 fprintf (dump_file, "BB %i predicted by continue.\n",
2014 bb->index);
2015 continue;
2018 /* If we already used more reliable loop exit predictors, do not
2019 bother with PRED_LOOP_EXIT. */
2020 if (!predicted_by_loop_heuristics_p (bb))
2022 /* For loop with many exits we don't want to predict all exits
2023 with the pretty large probability, because if all exits are
2024 considered in row, the loop would be predicted to iterate
2025 almost never. The code to divide probability by number of
2026 exits is very rough. It should compute the number of exits
2027 taken in each patch through function (not the overall number
2028 of exits that might be a lot higher for loops with wide switch
2029 statements in them) and compute n-th square root.
2031 We limit the minimal probability by 2% to avoid
2032 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2033 as this was causing regression in perl benchmark containing such
2034 a wide loop. */
2036 int probability = ((REG_BR_PROB_BASE
2037 - predictor_info
2038 [recursion
2039 ? PRED_LOOP_EXIT_WITH_RECURSION
2040 : PRED_LOOP_EXIT].hitrate)
2041 / n_exits);
2042 if (probability < HITRATE (2))
2043 probability = HITRATE (2);
2044 FOR_EACH_EDGE (e, ei, bb->succs)
2045 if (e->dest->index < NUM_FIXED_BLOCKS
2046 || !flow_bb_inside_loop_p (loop, e->dest))
2048 if (dump_file && (dump_flags & TDF_DETAILS))
2049 fprintf (dump_file,
2050 "Predicting exit %i->%i with prob %i.\n",
2051 e->src->index, e->dest->index, probability);
2052 predict_edge (e,
2053 recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2054 : PRED_LOOP_EXIT, probability);
2057 if (loop_bound_var)
2058 predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2059 loop_bound_code,
2060 tree_to_shwi (loop_bound_step));
2063 /* In the following code
2064 for (loop1)
2065 if (cond)
2066 for (loop2)
2067 body;
2068 guess that cond is unlikely. */
2069 if (loop_outer (loop)->num)
2071 basic_block bb = NULL;
2072 edge preheader_edge = loop_preheader_edge (loop);
2074 if (single_pred_p (preheader_edge->src)
2075 && single_succ_p (preheader_edge->src))
2076 preheader_edge = single_pred_edge (preheader_edge->src);
2078 gimple *stmt = last_stmt (preheader_edge->src);
2079 /* Pattern match fortran loop preheader:
2080 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2081 _17 = (logical(kind=4)) _16;
2082 if (_17 != 0)
2083 goto <bb 11>;
2084 else
2085 goto <bb 13>;
2087 Loop guard branch prediction says nothing about duplicated loop
2088 headers produced by fortran frontend and in this case we want
2089 to predict paths leading to this preheader. */
2091 if (stmt
2092 && gimple_code (stmt) == GIMPLE_COND
2093 && gimple_cond_code (stmt) == NE_EXPR
2094 && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2095 && integer_zerop (gimple_cond_rhs (stmt)))
2097 gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2098 if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2099 && gimple_expr_code (call_stmt) == NOP_EXPR
2100 && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2101 call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2102 if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
2103 && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2104 && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
2105 && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
2106 == PRED_FORTRAN_LOOP_PREHEADER)
2107 bb = preheader_edge->src;
2109 if (!bb)
2111 if (!dominated_by_p (CDI_DOMINATORS,
2112 loop_outer (loop)->latch, loop->header))
2113 predict_paths_leading_to_edge (loop_preheader_edge (loop),
2114 recursion
2115 ? PRED_LOOP_GUARD_WITH_RECURSION
2116 : PRED_LOOP_GUARD,
2117 NOT_TAKEN,
2118 loop_outer (loop));
2120 else
2122 if (!dominated_by_p (CDI_DOMINATORS,
2123 loop_outer (loop)->latch, bb))
2124 predict_paths_leading_to (bb,
2125 recursion
2126 ? PRED_LOOP_GUARD_WITH_RECURSION
2127 : PRED_LOOP_GUARD,
2128 NOT_TAKEN,
2129 loop_outer (loop));
2133 /* Free basic blocks from get_loop_body. */
2134 free (bbs);
2138 /* Attempt to predict probabilities of BB outgoing edges using local
2139 properties. */
2140 static void
2141 bb_estimate_probability_locally (basic_block bb)
2143 rtx_insn *last_insn = BB_END (bb);
2144 rtx cond;
2146 if (! can_predict_insn_p (last_insn))
2147 return;
2148 cond = get_condition (last_insn, NULL, false, false);
2149 if (! cond)
2150 return;
2152 /* Try "pointer heuristic."
2153 A comparison ptr == 0 is predicted as false.
2154 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2155 if (COMPARISON_P (cond)
2156 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2157 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2159 if (GET_CODE (cond) == EQ)
2160 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2161 else if (GET_CODE (cond) == NE)
2162 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2164 else
2166 /* Try "opcode heuristic."
2167 EQ tests are usually false and NE tests are usually true. Also,
2168 most quantities are positive, so we can make the appropriate guesses
2169 about signed comparisons against zero. */
2170 switch (GET_CODE (cond))
2172 case CONST_INT:
2173 /* Unconditional branch. */
2174 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2175 cond == const0_rtx ? NOT_TAKEN : TAKEN);
2176 break;
2178 case EQ:
2179 case UNEQ:
2180 /* Floating point comparisons appears to behave in a very
2181 unpredictable way because of special role of = tests in
2182 FP code. */
2183 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2185 /* Comparisons with 0 are often used for booleans and there is
2186 nothing useful to predict about them. */
2187 else if (XEXP (cond, 1) == const0_rtx
2188 || XEXP (cond, 0) == const0_rtx)
2190 else
2191 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2192 break;
2194 case NE:
2195 case LTGT:
2196 /* Floating point comparisons appears to behave in a very
2197 unpredictable way because of special role of = tests in
2198 FP code. */
2199 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2201 /* Comparisons with 0 are often used for booleans and there is
2202 nothing useful to predict about them. */
2203 else if (XEXP (cond, 1) == const0_rtx
2204 || XEXP (cond, 0) == const0_rtx)
2206 else
2207 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2208 break;
2210 case ORDERED:
2211 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2212 break;
2214 case UNORDERED:
2215 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2216 break;
2218 case LE:
2219 case LT:
2220 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2221 || XEXP (cond, 1) == constm1_rtx)
2222 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2223 break;
2225 case GE:
2226 case GT:
2227 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2228 || XEXP (cond, 1) == constm1_rtx)
2229 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2230 break;
2232 default:
2233 break;
2237 /* Set edge->probability for each successor edge of BB. */
2238 void
2239 guess_outgoing_edge_probabilities (basic_block bb)
2241 bb_estimate_probability_locally (bb);
2242 combine_predictions_for_insn (BB_END (bb), bb);
2245 static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
2247 /* Helper function for expr_expected_value. */
2249 static tree
2250 expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2251 tree op1, bitmap visited, enum br_predictor *predictor)
2253 gimple *def;
2255 if (predictor)
2256 *predictor = PRED_UNCONDITIONAL;
2258 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2260 if (TREE_CONSTANT (op0))
2261 return op0;
2263 if (code == IMAGPART_EXPR)
2265 if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2267 def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2268 if (is_gimple_call (def)
2269 && gimple_call_internal_p (def)
2270 && (gimple_call_internal_fn (def)
2271 == IFN_ATOMIC_COMPARE_EXCHANGE))
2273 /* Assume that any given atomic operation has low contention,
2274 and thus the compare-and-swap operation succeeds. */
2275 if (predictor)
2276 *predictor = PRED_COMPARE_AND_SWAP;
2277 return build_one_cst (TREE_TYPE (op0));
2282 if (code != SSA_NAME)
2283 return NULL_TREE;
2285 def = SSA_NAME_DEF_STMT (op0);
2287 /* If we were already here, break the infinite cycle. */
2288 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
2289 return NULL;
2291 if (gimple_code (def) == GIMPLE_PHI)
2293 /* All the arguments of the PHI node must have the same constant
2294 length. */
2295 int i, n = gimple_phi_num_args (def);
2296 tree val = NULL, new_val;
2298 for (i = 0; i < n; i++)
2300 tree arg = PHI_ARG_DEF (def, i);
2301 enum br_predictor predictor2;
2303 /* If this PHI has itself as an argument, we cannot
2304 determine the string length of this argument. However,
2305 if we can find an expected constant value for the other
2306 PHI args then we can still be sure that this is
2307 likely a constant. So be optimistic and just
2308 continue with the next argument. */
2309 if (arg == PHI_RESULT (def))
2310 continue;
2312 new_val = expr_expected_value (arg, visited, &predictor2);
2314 /* It is difficult to combine value predictors. Simply assume
2315 that later predictor is weaker and take its prediction. */
2316 if (predictor && *predictor < predictor2)
2317 *predictor = predictor2;
2318 if (!new_val)
2319 return NULL;
2320 if (!val)
2321 val = new_val;
2322 else if (!operand_equal_p (val, new_val, false))
2323 return NULL;
2325 return val;
2327 if (is_gimple_assign (def))
2329 if (gimple_assign_lhs (def) != op0)
2330 return NULL;
2332 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2333 gimple_assign_rhs1 (def),
2334 gimple_assign_rhs_code (def),
2335 gimple_assign_rhs2 (def),
2336 visited, predictor);
2339 if (is_gimple_call (def))
2341 tree decl = gimple_call_fndecl (def);
2342 if (!decl)
2344 if (gimple_call_internal_p (def)
2345 && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2347 gcc_assert (gimple_call_num_args (def) == 3);
2348 tree val = gimple_call_arg (def, 0);
2349 if (TREE_CONSTANT (val))
2350 return val;
2351 if (predictor)
2353 tree val2 = gimple_call_arg (def, 2);
2354 gcc_assert (TREE_CODE (val2) == INTEGER_CST
2355 && tree_fits_uhwi_p (val2)
2356 && tree_to_uhwi (val2) < END_PREDICTORS);
2357 *predictor = (enum br_predictor) tree_to_uhwi (val2);
2359 return gimple_call_arg (def, 1);
2361 return NULL;
2363 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2364 switch (DECL_FUNCTION_CODE (decl))
2366 case BUILT_IN_EXPECT:
2368 tree val;
2369 if (gimple_call_num_args (def) != 2)
2370 return NULL;
2371 val = gimple_call_arg (def, 0);
2372 if (TREE_CONSTANT (val))
2373 return val;
2374 if (predictor)
2375 *predictor = PRED_BUILTIN_EXPECT;
2376 return gimple_call_arg (def, 1);
2379 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2380 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2381 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2382 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2383 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2384 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2385 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2386 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2387 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2388 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2389 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2390 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2391 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2392 /* Assume that any given atomic operation has low contention,
2393 and thus the compare-and-swap operation succeeds. */
2394 if (predictor)
2395 *predictor = PRED_COMPARE_AND_SWAP;
2396 return boolean_true_node;
2397 default:
2398 break;
2402 return NULL;
2405 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2407 tree res;
2408 enum br_predictor predictor2;
2409 op0 = expr_expected_value (op0, visited, predictor);
2410 if (!op0)
2411 return NULL;
2412 op1 = expr_expected_value (op1, visited, &predictor2);
2413 if (predictor && *predictor < predictor2)
2414 *predictor = predictor2;
2415 if (!op1)
2416 return NULL;
2417 res = fold_build2 (code, type, op0, op1);
2418 if (TREE_CONSTANT (res))
2419 return res;
2420 return NULL;
2422 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2424 tree res;
2425 op0 = expr_expected_value (op0, visited, predictor);
2426 if (!op0)
2427 return NULL;
2428 res = fold_build1 (code, type, op0);
2429 if (TREE_CONSTANT (res))
2430 return res;
2431 return NULL;
2433 return NULL;
2436 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2437 The function is used by builtin_expect branch predictor so the evidence
2438 must come from this construct and additional possible constant folding.
2440 We may want to implement more involved value guess (such as value range
2441 propagation based prediction), but such tricks shall go to new
2442 implementation. */
2444 static tree
2445 expr_expected_value (tree expr, bitmap visited,
2446 enum br_predictor *predictor)
2448 enum tree_code code;
2449 tree op0, op1;
2451 if (TREE_CONSTANT (expr))
2453 if (predictor)
2454 *predictor = PRED_UNCONDITIONAL;
2455 return expr;
2458 extract_ops_from_tree (expr, &code, &op0, &op1);
2459 return expr_expected_value_1 (TREE_TYPE (expr),
2460 op0, code, op1, visited, predictor);
2463 /* Predict using opcode of the last statement in basic block. */
2464 static void
2465 tree_predict_by_opcode (basic_block bb)
2467 gimple *stmt = last_stmt (bb);
2468 edge then_edge;
2469 tree op0, op1;
2470 tree type;
2471 tree val;
2472 enum tree_code cmp;
2473 edge_iterator ei;
2474 enum br_predictor predictor;
2476 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
2477 return;
2478 FOR_EACH_EDGE (then_edge, ei, bb->succs)
2479 if (then_edge->flags & EDGE_TRUE_VALUE)
2480 break;
2481 op0 = gimple_cond_lhs (stmt);
2482 op1 = gimple_cond_rhs (stmt);
2483 cmp = gimple_cond_code (stmt);
2484 type = TREE_TYPE (op0);
2485 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
2486 &predictor);
2487 if (val && TREE_CODE (val) == INTEGER_CST)
2489 if (predictor == PRED_BUILTIN_EXPECT)
2491 int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
2493 gcc_assert (percent >= 0 && percent <= 100);
2494 if (integer_zerop (val))
2495 percent = 100 - percent;
2496 predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
2498 else
2499 predict_edge_def (then_edge, predictor,
2500 integer_zerop (val) ? NOT_TAKEN : TAKEN);
2502 /* Try "pointer heuristic."
2503 A comparison ptr == 0 is predicted as false.
2504 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2505 if (POINTER_TYPE_P (type))
2507 if (cmp == EQ_EXPR)
2508 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2509 else if (cmp == NE_EXPR)
2510 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2512 else
2514 /* Try "opcode heuristic."
2515 EQ tests are usually false and NE tests are usually true. Also,
2516 most quantities are positive, so we can make the appropriate guesses
2517 about signed comparisons against zero. */
2518 switch (cmp)
2520 case EQ_EXPR:
2521 case UNEQ_EXPR:
2522 /* Floating point comparisons appears to behave in a very
2523 unpredictable way because of special role of = tests in
2524 FP code. */
2525 if (FLOAT_TYPE_P (type))
2527 /* Comparisons with 0 are often used for booleans and there is
2528 nothing useful to predict about them. */
2529 else if (integer_zerop (op0) || integer_zerop (op1))
2531 else
2532 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2533 break;
2535 case NE_EXPR:
2536 case LTGT_EXPR:
2537 /* Floating point comparisons appears to behave in a very
2538 unpredictable way because of special role of = tests in
2539 FP code. */
2540 if (FLOAT_TYPE_P (type))
2542 /* Comparisons with 0 are often used for booleans and there is
2543 nothing useful to predict about them. */
2544 else if (integer_zerop (op0)
2545 || integer_zerop (op1))
2547 else
2548 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2549 break;
2551 case ORDERED_EXPR:
2552 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2553 break;
2555 case UNORDERED_EXPR:
2556 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2557 break;
2559 case LE_EXPR:
2560 case LT_EXPR:
2561 if (integer_zerop (op1)
2562 || integer_onep (op1)
2563 || integer_all_onesp (op1)
2564 || real_zerop (op1)
2565 || real_onep (op1)
2566 || real_minus_onep (op1))
2567 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2568 break;
2570 case GE_EXPR:
2571 case GT_EXPR:
2572 if (integer_zerop (op1)
2573 || integer_onep (op1)
2574 || integer_all_onesp (op1)
2575 || real_zerop (op1)
2576 || real_onep (op1)
2577 || real_minus_onep (op1))
2578 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2579 break;
2581 default:
2582 break;
2586 /* Returns TRUE if the STMT is exit(0) like statement. */
2588 static bool
2589 is_exit_with_zero_arg (const gimple *stmt)
2591 /* This is not exit, _exit or _Exit. */
2592 if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2593 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2594 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2595 return false;
2597 /* Argument is an interger zero. */
2598 return integer_zerop (gimple_call_arg (stmt, 0));
2601 /* Try to guess whether the value of return means error code. */
2603 static enum br_predictor
2604 return_prediction (tree val, enum prediction *prediction)
2606 /* VOID. */
2607 if (!val)
2608 return PRED_NO_PREDICTION;
2609 /* Different heuristics for pointers and scalars. */
2610 if (POINTER_TYPE_P (TREE_TYPE (val)))
2612 /* NULL is usually not returned. */
2613 if (integer_zerop (val))
2615 *prediction = NOT_TAKEN;
2616 return PRED_NULL_RETURN;
2619 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2621 /* Negative return values are often used to indicate
2622 errors. */
2623 if (TREE_CODE (val) == INTEGER_CST
2624 && tree_int_cst_sgn (val) < 0)
2626 *prediction = NOT_TAKEN;
2627 return PRED_NEGATIVE_RETURN;
2629 /* Constant return values seems to be commonly taken.
2630 Zero/one often represent booleans so exclude them from the
2631 heuristics. */
2632 if (TREE_CONSTANT (val)
2633 && (!integer_zerop (val) && !integer_onep (val)))
2635 *prediction = NOT_TAKEN;
2636 return PRED_CONST_RETURN;
2639 return PRED_NO_PREDICTION;
2642 /* Find the basic block with return expression and look up for possible
2643 return value trying to apply RETURN_PREDICTION heuristics. */
2644 static void
2645 apply_return_prediction (void)
2647 greturn *return_stmt = NULL;
2648 tree return_val;
2649 edge e;
2650 gphi *phi;
2651 int phi_num_args, i;
2652 enum br_predictor pred;
2653 enum prediction direction;
2654 edge_iterator ei;
2656 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2658 gimple *last = last_stmt (e->src);
2659 if (last
2660 && gimple_code (last) == GIMPLE_RETURN)
2662 return_stmt = as_a <greturn *> (last);
2663 break;
2666 if (!e)
2667 return;
2668 return_val = gimple_return_retval (return_stmt);
2669 if (!return_val)
2670 return;
2671 if (TREE_CODE (return_val) != SSA_NAME
2672 || !SSA_NAME_DEF_STMT (return_val)
2673 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2674 return;
2675 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2676 phi_num_args = gimple_phi_num_args (phi);
2677 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
2679 /* Avoid the degenerate case where all return values form the function
2680 belongs to same category (ie they are all positive constants)
2681 so we can hardly say something about them. */
2682 for (i = 1; i < phi_num_args; i++)
2683 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
2684 break;
2685 if (i != phi_num_args)
2686 for (i = 0; i < phi_num_args; i++)
2688 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
2689 if (pred != PRED_NO_PREDICTION)
2690 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
2691 direction);
2695 /* Look for basic block that contains unlikely to happen events
2696 (such as noreturn calls) and mark all paths leading to execution
2697 of this basic blocks as unlikely. */
2699 static void
2700 tree_bb_level_predictions (void)
2702 basic_block bb;
2703 bool has_return_edges = false;
2704 edge e;
2705 edge_iterator ei;
2707 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2708 if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
2710 has_return_edges = true;
2711 break;
2714 apply_return_prediction ();
2716 FOR_EACH_BB_FN (bb, cfun)
2718 gimple_stmt_iterator gsi;
2720 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2722 gimple *stmt = gsi_stmt (gsi);
2723 tree decl;
2725 if (is_gimple_call (stmt))
2727 if (gimple_call_noreturn_p (stmt)
2728 && has_return_edges
2729 && !is_exit_with_zero_arg (stmt))
2730 predict_paths_leading_to (bb, PRED_NORETURN,
2731 NOT_TAKEN);
2732 decl = gimple_call_fndecl (stmt);
2733 if (decl
2734 && lookup_attribute ("cold",
2735 DECL_ATTRIBUTES (decl)))
2736 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
2737 NOT_TAKEN);
2738 if (decl && recursive_call_p (current_function_decl, decl))
2739 predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
2740 NOT_TAKEN);
2742 else if (gimple_code (stmt) == GIMPLE_PREDICT)
2744 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
2745 gimple_predict_outcome (stmt));
2746 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2747 hints to callers. */
2753 /* Callback for hash_map::traverse, asserts that the pointer map is
2754 empty. */
2756 bool
2757 assert_is_empty (const_basic_block const &, edge_prediction *const &value,
2758 void *)
2760 gcc_assert (!value);
2761 return false;
2764 /* Predict branch probabilities and estimate profile for basic block BB.
2765 When LOCAL_ONLY is set do not use any global properties of CFG. */
2767 static void
2768 tree_estimate_probability_bb (basic_block bb, bool local_only)
2770 edge e;
2771 edge_iterator ei;
2773 FOR_EACH_EDGE (e, ei, bb->succs)
2775 /* Look for block we are guarding (ie we dominate it,
2776 but it doesn't postdominate us). */
2777 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
2778 && !local_only
2779 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
2780 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
2782 gimple_stmt_iterator bi;
2784 /* The call heuristic claims that a guarded function call
2785 is improbable. This is because such calls are often used
2786 to signal exceptional situations such as printing error
2787 messages. */
2788 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
2789 gsi_next (&bi))
2791 gimple *stmt = gsi_stmt (bi);
2792 if (is_gimple_call (stmt)
2793 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
2794 /* Constant and pure calls are hardly used to signalize
2795 something exceptional. */
2796 && gimple_has_side_effects (stmt))
2798 if (gimple_call_fndecl (stmt))
2799 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
2800 else if (virtual_method_call_p (gimple_call_fn (stmt)))
2801 predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
2802 else
2803 predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
2804 break;
2809 tree_predict_by_opcode (bb);
2812 /* Predict branch probabilities and estimate profile of the tree CFG.
2813 This function can be called from the loop optimizers to recompute
2814 the profile information.
2815 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2817 void
2818 tree_estimate_probability (bool dry_run)
2820 basic_block bb;
2822 add_noreturn_fake_exit_edges ();
2823 connect_infinite_loops_to_exit ();
2824 /* We use loop_niter_by_eval, which requires that the loops have
2825 preheaders. */
2826 create_preheaders (CP_SIMPLE_PREHEADERS);
2827 calculate_dominance_info (CDI_POST_DOMINATORS);
2829 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2830 tree_bb_level_predictions ();
2831 record_loop_exits ();
2833 if (number_of_loops (cfun) > 1)
2834 predict_loops ();
2836 FOR_EACH_BB_FN (bb, cfun)
2837 tree_estimate_probability_bb (bb, false);
2839 FOR_EACH_BB_FN (bb, cfun)
2840 combine_predictions_for_bb (bb, dry_run);
2842 if (flag_checking)
2843 bb_predictions->traverse<void *, assert_is_empty> (NULL);
2845 delete bb_predictions;
2846 bb_predictions = NULL;
2848 if (!dry_run)
2849 estimate_bb_frequencies (false);
2850 free_dominance_info (CDI_POST_DOMINATORS);
2851 remove_fake_exit_edges ();
2854 /* Set edge->probability for each successor edge of BB. */
2855 void
2856 tree_guess_outgoing_edge_probabilities (basic_block bb)
2858 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2859 tree_estimate_probability_bb (bb, true);
2860 combine_predictions_for_bb (bb, false);
2861 if (flag_checking)
2862 bb_predictions->traverse<void *, assert_is_empty> (NULL);
2863 delete bb_predictions;
2864 bb_predictions = NULL;
2867 /* Predict edges to successors of CUR whose sources are not postdominated by
2868 BB by PRED and recurse to all postdominators. */
2870 static void
2871 predict_paths_for_bb (basic_block cur, basic_block bb,
2872 enum br_predictor pred,
2873 enum prediction taken,
2874 bitmap visited, struct loop *in_loop = NULL)
2876 edge e;
2877 edge_iterator ei;
2878 basic_block son;
2880 /* If we exited the loop or CUR is unconditional in the loop, there is
2881 nothing to do. */
2882 if (in_loop
2883 && (!flow_bb_inside_loop_p (in_loop, cur)
2884 || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
2885 return;
2887 /* We are looking for all edges forming edge cut induced by
2888 set of all blocks postdominated by BB. */
2889 FOR_EACH_EDGE (e, ei, cur->preds)
2890 if (e->src->index >= NUM_FIXED_BLOCKS
2891 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
2893 edge e2;
2894 edge_iterator ei2;
2895 bool found = false;
2897 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2898 if (unlikely_executed_edge_p (e))
2899 continue;
2900 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
2902 /* See if there is an edge from e->src that is not abnormal
2903 and does not lead to BB and does not exit the loop. */
2904 FOR_EACH_EDGE (e2, ei2, e->src->succs)
2905 if (e2 != e
2906 && !unlikely_executed_edge_p (e2)
2907 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
2908 && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
2910 found = true;
2911 break;
2914 /* If there is non-abnormal path leaving e->src, predict edge
2915 using predictor. Otherwise we need to look for paths
2916 leading to e->src.
2918 The second may lead to infinite loop in the case we are predicitng
2919 regions that are only reachable by abnormal edges. We simply
2920 prevent visiting given BB twice. */
2921 if (found)
2923 if (!edge_predicted_by_p (e, pred, taken))
2924 predict_edge_def (e, pred, taken);
2926 else if (bitmap_set_bit (visited, e->src->index))
2927 predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
2929 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
2930 son;
2931 son = next_dom_son (CDI_POST_DOMINATORS, son))
2932 predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
2935 /* Sets branch probabilities according to PREDiction and
2936 FLAGS. */
2938 static void
2939 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
2940 enum prediction taken, struct loop *in_loop)
2942 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
2945 /* Like predict_paths_leading_to but take edge instead of basic block. */
2947 static void
2948 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
2949 enum prediction taken, struct loop *in_loop)
2951 bool has_nonloop_edge = false;
2952 edge_iterator ei;
2953 edge e2;
2955 basic_block bb = e->src;
2956 FOR_EACH_EDGE (e2, ei, bb->succs)
2957 if (e2->dest != e->src && e2->dest != e->dest
2958 && !unlikely_executed_edge_p (e)
2959 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
2961 has_nonloop_edge = true;
2962 break;
2964 if (!has_nonloop_edge)
2966 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
2968 else
2969 predict_edge_def (e, pred, taken);
2972 /* This is used to carry information about basic blocks. It is
2973 attached to the AUX field of the standard CFG block. */
2975 struct block_info
2977 /* Estimated frequency of execution of basic_block. */
2978 sreal frequency;
2980 /* To keep queue of basic blocks to process. */
2981 basic_block next;
2983 /* Number of predecessors we need to visit first. */
2984 int npredecessors;
2987 /* Similar information for edges. */
2988 struct edge_prob_info
2990 /* In case edge is a loopback edge, the probability edge will be reached
2991 in case header is. Estimated number of iterations of the loop can be
2992 then computed as 1 / (1 - back_edge_prob). */
2993 sreal back_edge_prob;
2994 /* True if the edge is a loopback edge in the natural loop. */
2995 unsigned int back_edge:1;
2998 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2999 #undef EDGE_INFO
3000 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3002 /* Helper function for estimate_bb_frequencies.
3003 Propagate the frequencies in blocks marked in
3004 TOVISIT, starting in HEAD. */
3006 static void
3007 propagate_freq (basic_block head, bitmap tovisit)
3009 basic_block bb;
3010 basic_block last;
3011 unsigned i;
3012 edge e;
3013 basic_block nextbb;
3014 bitmap_iterator bi;
3016 /* For each basic block we need to visit count number of his predecessors
3017 we need to visit first. */
3018 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3020 edge_iterator ei;
3021 int count = 0;
3023 bb = BASIC_BLOCK_FOR_FN (cfun, i);
3025 FOR_EACH_EDGE (e, ei, bb->preds)
3027 bool visit = bitmap_bit_p (tovisit, e->src->index);
3029 if (visit && !(e->flags & EDGE_DFS_BACK))
3030 count++;
3031 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3032 fprintf (dump_file,
3033 "Irreducible region hit, ignoring edge to %i->%i\n",
3034 e->src->index, bb->index);
3036 BLOCK_INFO (bb)->npredecessors = count;
3037 /* When function never returns, we will never process exit block. */
3038 if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3039 bb->count = profile_count::zero ();
3042 BLOCK_INFO (head)->frequency = 1;
3043 last = head;
3044 for (bb = head; bb; bb = nextbb)
3046 edge_iterator ei;
3047 sreal cyclic_probability = 0;
3048 sreal frequency = 0;
3050 nextbb = BLOCK_INFO (bb)->next;
3051 BLOCK_INFO (bb)->next = NULL;
3053 /* Compute frequency of basic block. */
3054 if (bb != head)
3056 if (flag_checking)
3057 FOR_EACH_EDGE (e, ei, bb->preds)
3058 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3059 || (e->flags & EDGE_DFS_BACK));
3061 FOR_EACH_EDGE (e, ei, bb->preds)
3062 if (EDGE_INFO (e)->back_edge)
3064 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3066 else if (!(e->flags & EDGE_DFS_BACK))
3068 /* frequency += (e->probability
3069 * BLOCK_INFO (e->src)->frequency /
3070 REG_BR_PROB_BASE); */
3072 /* FIXME: Graphite is producing edges with no profile. Once
3073 this is fixed, drop this. */
3074 sreal tmp = e->probability.initialized_p () ?
3075 e->probability.to_reg_br_prob_base () : 0;
3076 tmp *= BLOCK_INFO (e->src)->frequency;
3077 tmp *= real_inv_br_prob_base;
3078 frequency += tmp;
3081 if (cyclic_probability == 0)
3083 BLOCK_INFO (bb)->frequency = frequency;
3085 else
3087 if (cyclic_probability > real_almost_one)
3088 cyclic_probability = real_almost_one;
3090 /* BLOCK_INFO (bb)->frequency = frequency
3091 / (1 - cyclic_probability) */
3093 cyclic_probability = sreal (1) - cyclic_probability;
3094 BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
3098 bitmap_clear_bit (tovisit, bb->index);
3100 e = find_edge (bb, head);
3101 if (e)
3103 /* EDGE_INFO (e)->back_edge_prob
3104 = ((e->probability * BLOCK_INFO (bb)->frequency)
3105 / REG_BR_PROB_BASE); */
3107 /* FIXME: Graphite is producing edges with no profile. Once
3108 this is fixed, drop this. */
3109 sreal tmp = e->probability.initialized_p () ?
3110 e->probability.to_reg_br_prob_base () : 0;
3111 tmp *= BLOCK_INFO (bb)->frequency;
3112 EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
3115 /* Propagate to successor blocks. */
3116 FOR_EACH_EDGE (e, ei, bb->succs)
3117 if (!(e->flags & EDGE_DFS_BACK)
3118 && BLOCK_INFO (e->dest)->npredecessors)
3120 BLOCK_INFO (e->dest)->npredecessors--;
3121 if (!BLOCK_INFO (e->dest)->npredecessors)
3123 if (!nextbb)
3124 nextbb = e->dest;
3125 else
3126 BLOCK_INFO (last)->next = e->dest;
3128 last = e->dest;
3134 /* Estimate frequencies in loops at same nest level. */
3136 static void
3137 estimate_loops_at_level (struct loop *first_loop)
3139 struct loop *loop;
3141 for (loop = first_loop; loop; loop = loop->next)
3143 edge e;
3144 basic_block *bbs;
3145 unsigned i;
3146 auto_bitmap tovisit;
3148 estimate_loops_at_level (loop->inner);
3150 /* Find current loop back edge and mark it. */
3151 e = loop_latch_edge (loop);
3152 EDGE_INFO (e)->back_edge = 1;
3154 bbs = get_loop_body (loop);
3155 for (i = 0; i < loop->num_nodes; i++)
3156 bitmap_set_bit (tovisit, bbs[i]->index);
3157 free (bbs);
3158 propagate_freq (loop->header, tovisit);
3162 /* Propagates frequencies through structure of loops. */
3164 static void
3165 estimate_loops (void)
3167 auto_bitmap tovisit;
3168 basic_block bb;
3170 /* Start by estimating the frequencies in the loops. */
3171 if (number_of_loops (cfun) > 1)
3172 estimate_loops_at_level (current_loops->tree_root->inner);
3174 /* Now propagate the frequencies through all the blocks. */
3175 FOR_ALL_BB_FN (bb, cfun)
3177 bitmap_set_bit (tovisit, bb->index);
3179 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
3182 /* Drop the profile for NODE to guessed, and update its frequency based on
3183 whether it is expected to be hot given the CALL_COUNT. */
3185 static void
3186 drop_profile (struct cgraph_node *node, profile_count call_count)
3188 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3189 /* In the case where this was called by another function with a
3190 dropped profile, call_count will be 0. Since there are no
3191 non-zero call counts to this function, we don't know for sure
3192 whether it is hot, and therefore it will be marked normal below. */
3193 bool hot = maybe_hot_count_p (NULL, call_count);
3195 if (dump_file)
3196 fprintf (dump_file,
3197 "Dropping 0 profile for %s. %s based on calls.\n",
3198 node->dump_name (),
3199 hot ? "Function is hot" : "Function is normal");
3200 /* We only expect to miss profiles for functions that are reached
3201 via non-zero call edges in cases where the function may have
3202 been linked from another module or library (COMDATs and extern
3203 templates). See the comments below for handle_missing_profiles.
3204 Also, only warn in cases where the missing counts exceed the
3205 number of training runs. In certain cases with an execv followed
3206 by a no-return call the profile for the no-return call is not
3207 dumped and there can be a mismatch. */
3208 if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3209 && call_count > profile_info->runs)
3211 if (flag_profile_correction)
3213 if (dump_file)
3214 fprintf (dump_file,
3215 "Missing counts for called function %s\n",
3216 node->dump_name ());
3218 else
3219 warning (0, "Missing counts for called function %s",
3220 node->dump_name ());
3223 basic_block bb;
3224 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
3225 if (flag_guess_branch_prob)
3227 bool clear_zeros
3228 = ENTRY_BLOCK_PTR_FOR_FN
3229 (DECL_STRUCT_FUNCTION (node->decl))->count.nonzero_p ();
3230 FOR_ALL_BB_FN (bb, fn)
3231 if (clear_zeros || !(bb->count == profile_count::zero ()))
3232 bb->count = bb->count.guessed_local ();
3233 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max =
3234 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max.guessed_local ();
3236 else
3238 FOR_ALL_BB_FN (bb, fn)
3239 bb->count = profile_count::uninitialized ();
3240 DECL_STRUCT_FUNCTION (node->decl)->cfg->count_max
3241 = profile_count::uninitialized ();
3243 pop_cfun ();
3245 struct cgraph_edge *e;
3246 for (e = node->callees; e; e = e->next_callee)
3247 e->count = gimple_bb (e->call_stmt)->count;
3248 for (e = node->indirect_calls; e; e = e->next_callee)
3249 e->count = gimple_bb (e->call_stmt)->count;
3251 profile_status_for_fn (fn)
3252 = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3253 node->frequency
3254 = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3257 /* In the case of COMDAT routines, multiple object files will contain the same
3258 function and the linker will select one for the binary. In that case
3259 all the other copies from the profile instrument binary will be missing
3260 profile counts. Look for cases where this happened, due to non-zero
3261 call counts going to 0-count functions, and drop the profile to guessed
3262 so that we can use the estimated probabilities and avoid optimizing only
3263 for size.
3265 The other case where the profile may be missing is when the routine
3266 is not going to be emitted to the object file, e.g. for "extern template"
3267 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3268 all other cases of non-zero calls to 0-count functions. */
3270 void
3271 handle_missing_profiles (void)
3273 struct cgraph_node *node;
3274 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
3275 auto_vec<struct cgraph_node *, 64> worklist;
3277 /* See if 0 count function has non-0 count callers. In this case we
3278 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3279 FOR_EACH_DEFINED_FUNCTION (node)
3281 struct cgraph_edge *e;
3282 profile_count call_count = profile_count::zero ();
3283 gcov_type max_tp_first_run = 0;
3284 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3286 if (!(node->count == profile_count::zero ()))
3287 continue;
3288 for (e = node->callers; e; e = e->next_caller)
3289 if (e->count.initialized_p () && e->count > 0)
3291 call_count = call_count + e->count;
3293 if (e->caller->tp_first_run > max_tp_first_run)
3294 max_tp_first_run = e->caller->tp_first_run;
3297 /* If time profile is missing, let assign the maximum that comes from
3298 caller functions. */
3299 if (!node->tp_first_run && max_tp_first_run)
3300 node->tp_first_run = max_tp_first_run + 1;
3302 if (call_count > 0
3303 && fn && fn->cfg
3304 && (call_count.apply_scale (unlikely_count_fraction, 1)
3305 >= profile_info->runs))
3307 drop_profile (node, call_count);
3308 worklist.safe_push (node);
3312 /* Propagate the profile dropping to other 0-count COMDATs that are
3313 potentially called by COMDATs we already dropped the profile on. */
3314 while (worklist.length () > 0)
3316 struct cgraph_edge *e;
3318 node = worklist.pop ();
3319 for (e = node->callees; e; e = e->next_caller)
3321 struct cgraph_node *callee = e->callee;
3322 struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3324 if (callee->count > 0)
3325 continue;
3326 if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3327 && fn && fn->cfg
3328 && profile_status_for_fn (fn) == PROFILE_READ)
3330 drop_profile (node, profile_count::zero ());
3331 worklist.safe_push (callee);
3337 /* Convert counts measured by profile driven feedback to frequencies.
3338 Return nonzero iff there was any nonzero execution count. */
3340 bool
3341 update_max_bb_count (void)
3343 profile_count true_count_max = profile_count::uninitialized ();
3344 basic_block bb;
3346 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3347 true_count_max = true_count_max.max (bb->count);
3349 cfun->cfg->count_max = true_count_max;
3351 return true_count_max.ipa ().nonzero_p ();
3354 /* Return true if function is likely to be expensive, so there is no point to
3355 optimize performance of prologue, epilogue or do inlining at the expense
3356 of code size growth. THRESHOLD is the limit of number of instructions
3357 function can execute at average to be still considered not expensive. */
3359 bool
3360 expensive_function_p (int threshold)
3362 basic_block bb;
3364 /* If profile was scaled in a way entry block has count 0, then the function
3365 is deifnitly taking a lot of time. */
3366 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3367 return true;
3369 profile_count limit = ENTRY_BLOCK_PTR_FOR_FN
3370 (cfun)->count.apply_scale (threshold, 1);
3371 profile_count sum = profile_count::zero ();
3372 FOR_EACH_BB_FN (bb, cfun)
3374 rtx_insn *insn;
3376 if (!bb->count.initialized_p ())
3378 if (dump_file)
3379 fprintf (dump_file, "Function is considered expensive because"
3380 " count of bb %i is not initialized\n", bb->index);
3381 return true;
3384 FOR_BB_INSNS (bb, insn)
3385 if (active_insn_p (insn))
3387 sum += bb->count;
3388 if (sum > limit)
3389 return true;
3393 return false;
3396 /* All basic blocks that are reachable only from unlikely basic blocks are
3397 unlikely. */
3399 void
3400 propagate_unlikely_bbs_forward (void)
3402 auto_vec<basic_block, 64> worklist;
3403 basic_block bb;
3404 edge_iterator ei;
3405 edge e;
3407 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3409 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3410 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3412 while (worklist.length () > 0)
3414 bb = worklist.pop ();
3415 FOR_EACH_EDGE (e, ei, bb->succs)
3416 if (!(e->count () == profile_count::zero ())
3417 && !(e->dest->count == profile_count::zero ())
3418 && !e->dest->aux)
3420 e->dest->aux = (void *)(size_t) 1;
3421 worklist.safe_push (e->dest);
3426 FOR_ALL_BB_FN (bb, cfun)
3428 if (!bb->aux)
3430 if (!(bb->count == profile_count::zero ())
3431 && (dump_file && (dump_flags & TDF_DETAILS)))
3432 fprintf (dump_file,
3433 "Basic block %i is marked unlikely by forward prop\n",
3434 bb->index);
3435 bb->count = profile_count::zero ();
3437 else
3438 bb->aux = NULL;
3442 /* Determine basic blocks/edges that are known to be unlikely executed and set
3443 their counters to zero.
3444 This is done with first identifying obviously unlikely BBs/edges and then
3445 propagating in both directions. */
3447 static void
3448 determine_unlikely_bbs ()
3450 basic_block bb;
3451 auto_vec<basic_block, 64> worklist;
3452 edge_iterator ei;
3453 edge e;
3455 FOR_EACH_BB_FN (bb, cfun)
3457 if (!(bb->count == profile_count::zero ())
3458 && unlikely_executed_bb_p (bb))
3460 if (dump_file && (dump_flags & TDF_DETAILS))
3461 fprintf (dump_file, "Basic block %i is locally unlikely\n",
3462 bb->index);
3463 bb->count = profile_count::zero ();
3466 FOR_EACH_EDGE (e, ei, bb->succs)
3467 if (!(e->probability == profile_probability::never ())
3468 && unlikely_executed_edge_p (e))
3470 if (dump_file && (dump_flags & TDF_DETAILS))
3471 fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
3472 bb->index, e->dest->index);
3473 e->probability = profile_probability::never ();
3476 gcc_checking_assert (!bb->aux);
3478 propagate_unlikely_bbs_forward ();
3480 auto_vec<int, 64> nsuccs;
3481 nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun));
3482 FOR_ALL_BB_FN (bb, cfun)
3483 if (!(bb->count == profile_count::zero ())
3484 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3486 nsuccs[bb->index] = 0;
3487 FOR_EACH_EDGE (e, ei, bb->succs)
3488 if (!(e->probability == profile_probability::never ())
3489 && !(e->dest->count == profile_count::zero ()))
3490 nsuccs[bb->index]++;
3491 if (!nsuccs[bb->index])
3492 worklist.safe_push (bb);
3494 while (worklist.length () > 0)
3496 bb = worklist.pop ();
3497 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3499 bool found = false;
3500 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
3501 !gsi_end_p (gsi); gsi_next (&gsi))
3502 if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
3503 /* stmt_can_terminate_bb_p special cases noreturns because it
3504 assumes that fake edges are created. We want to know that
3505 noreturn alone does not imply BB to be unlikely. */
3506 || (is_gimple_call (gsi_stmt (gsi))
3507 && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
3509 found = true;
3510 break;
3512 if (found)
3513 continue;
3515 if (!(bb->count == profile_count::zero ())
3516 && (dump_file && (dump_flags & TDF_DETAILS)))
3517 fprintf (dump_file,
3518 "Basic block %i is marked unlikely by backward prop\n",
3519 bb->index);
3520 bb->count = profile_count::zero ();
3521 FOR_EACH_EDGE (e, ei, bb->preds)
3522 if (!(e->probability == profile_probability::never ()))
3524 if (!(e->src->count == profile_count::zero ()))
3526 nsuccs[e->src->index]--;
3527 if (!nsuccs[e->src->index])
3528 worklist.safe_push (e->src);
3532 /* Finally all edges from non-0 regions to 0 are unlikely. */
3533 FOR_ALL_BB_FN (bb, cfun)
3534 if (!(bb->count == profile_count::zero ()))
3535 FOR_EACH_EDGE (e, ei, bb->succs)
3536 if (!(e->probability == profile_probability::never ())
3537 && e->dest->count == profile_count::zero ())
3539 if (dump_file && (dump_flags & TDF_DETAILS))
3540 fprintf (dump_file, "Edge %i->%i is unlikely because "
3541 "it enters unlikely block\n",
3542 bb->index, e->dest->index);
3543 e->probability = profile_probability::never ();
3545 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
3546 cgraph_node::get (current_function_decl)->count = profile_count::zero ();
3549 /* Estimate and propagate basic block frequencies using the given branch
3550 probabilities. If FORCE is true, the frequencies are used to estimate
3551 the counts even when there are already non-zero profile counts. */
3553 void
3554 estimate_bb_frequencies (bool force)
3556 basic_block bb;
3557 sreal freq_max;
3559 determine_unlikely_bbs ();
3561 if (force || profile_status_for_fn (cfun) != PROFILE_READ
3562 || !update_max_bb_count ())
3564 static int real_values_initialized = 0;
3566 if (!real_values_initialized)
3568 real_values_initialized = 1;
3569 real_br_prob_base = REG_BR_PROB_BASE;
3570 /* Scaling frequencies up to maximal profile count may result in
3571 frequent overflows especially when inlining loops.
3572 Small scalling results in unnecesary precision loss. Stay in
3573 the half of the (exponential) range. */
3574 real_bb_freq_max = (uint64_t)1 << (profile_count::n_bits / 2);
3575 real_one_half = sreal (1, -1);
3576 real_inv_br_prob_base = sreal (1) / real_br_prob_base;
3577 real_almost_one = sreal (1) - real_inv_br_prob_base;
3580 mark_dfs_back_edges ();
3582 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
3583 profile_probability::always ();
3585 /* Set up block info for each basic block. */
3586 alloc_aux_for_blocks (sizeof (block_info));
3587 alloc_aux_for_edges (sizeof (edge_prob_info));
3588 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3590 edge e;
3591 edge_iterator ei;
3593 FOR_EACH_EDGE (e, ei, bb->succs)
3595 /* FIXME: Graphite is producing edges with no profile. Once
3596 this is fixed, drop this. */
3597 if (e->probability.initialized_p ())
3598 EDGE_INFO (e)->back_edge_prob
3599 = e->probability.to_reg_br_prob_base ();
3600 else
3601 EDGE_INFO (e)->back_edge_prob = REG_BR_PROB_BASE / 2;
3602 EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
3606 /* First compute frequencies locally for each loop from innermost
3607 to outermost to examine frequencies for back edges. */
3608 estimate_loops ();
3610 freq_max = 0;
3611 FOR_EACH_BB_FN (bb, cfun)
3612 if (freq_max < BLOCK_INFO (bb)->frequency)
3613 freq_max = BLOCK_INFO (bb)->frequency;
3615 freq_max = real_bb_freq_max / freq_max;
3616 if (freq_max < 16)
3617 freq_max = 16;
3618 profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
3619 cfun->cfg->count_max = profile_count::uninitialized ();
3620 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3622 sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
3623 profile_count count = profile_count::from_gcov_type (tmp.to_int ());
3625 /* If we have profile feedback in which this function was never
3626 executed, then preserve this info. */
3627 if (!(bb->count == profile_count::zero ()))
3628 bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
3629 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
3632 free_aux_for_blocks ();
3633 free_aux_for_edges ();
3635 compute_function_frequency ();
3638 /* Decide whether function is hot, cold or unlikely executed. */
3639 void
3640 compute_function_frequency (void)
3642 basic_block bb;
3643 struct cgraph_node *node = cgraph_node::get (current_function_decl);
3645 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3646 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
3647 node->only_called_at_startup = true;
3648 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
3649 node->only_called_at_exit = true;
3651 if (profile_status_for_fn (cfun) != PROFILE_READ)
3653 int flags = flags_from_decl_or_type (current_function_decl);
3654 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ()
3655 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3656 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
3657 != NULL)
3659 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3660 warn_function_cold (current_function_decl);
3662 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
3663 != NULL)
3664 node->frequency = NODE_FREQUENCY_HOT;
3665 else if (flags & ECF_NORETURN)
3666 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3667 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
3668 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3669 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3670 || DECL_STATIC_DESTRUCTOR (current_function_decl))
3671 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3672 return;
3675 /* Only first time try to drop function into unlikely executed.
3676 After inlining the roundoff errors may confuse us.
3677 Ipa-profile pass will drop functions only called from unlikely
3678 functions to unlikely and that is most of what we care about. */
3679 if (!cfun->after_inlining)
3681 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3682 warn_function_cold (current_function_decl);
3684 FOR_EACH_BB_FN (bb, cfun)
3686 if (maybe_hot_bb_p (cfun, bb))
3688 node->frequency = NODE_FREQUENCY_HOT;
3689 return;
3691 if (!probably_never_executed_bb_p (cfun, bb))
3692 node->frequency = NODE_FREQUENCY_NORMAL;
3696 /* Build PREDICT_EXPR. */
3697 tree
3698 build_predict_expr (enum br_predictor predictor, enum prediction taken)
3700 tree t = build1 (PREDICT_EXPR, void_type_node,
3701 build_int_cst (integer_type_node, predictor));
3702 SET_PREDICT_EXPR_OUTCOME (t, taken);
3703 return t;
3706 const char *
3707 predictor_name (enum br_predictor predictor)
3709 return predictor_info[predictor].name;
3712 /* Predict branch probabilities and estimate profile of the tree CFG. */
3714 namespace {
3716 const pass_data pass_data_profile =
3718 GIMPLE_PASS, /* type */
3719 "profile_estimate", /* name */
3720 OPTGROUP_NONE, /* optinfo_flags */
3721 TV_BRANCH_PROB, /* tv_id */
3722 PROP_cfg, /* properties_required */
3723 0, /* properties_provided */
3724 0, /* properties_destroyed */
3725 0, /* todo_flags_start */
3726 0, /* todo_flags_finish */
3729 class pass_profile : public gimple_opt_pass
3731 public:
3732 pass_profile (gcc::context *ctxt)
3733 : gimple_opt_pass (pass_data_profile, ctxt)
3736 /* opt_pass methods: */
3737 virtual bool gate (function *) { return flag_guess_branch_prob; }
3738 virtual unsigned int execute (function *);
3740 }; // class pass_profile
3742 unsigned int
3743 pass_profile::execute (function *fun)
3745 unsigned nb_loops;
3747 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3748 return 0;
3750 loop_optimizer_init (LOOPS_NORMAL);
3751 if (dump_file && (dump_flags & TDF_DETAILS))
3752 flow_loops_dump (dump_file, NULL, 0);
3754 mark_irreducible_loops ();
3756 nb_loops = number_of_loops (fun);
3757 if (nb_loops > 1)
3758 scev_initialize ();
3760 tree_estimate_probability (false);
3762 if (nb_loops > 1)
3763 scev_finalize ();
3765 loop_optimizer_finalize ();
3766 if (dump_file && (dump_flags & TDF_DETAILS))
3767 gimple_dump_cfg (dump_file, dump_flags);
3768 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
3769 profile_status_for_fn (fun) = PROFILE_GUESSED;
3770 if (dump_file && (dump_flags & TDF_DETAILS))
3772 struct loop *loop;
3773 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3774 if (loop->header->count.initialized_p ())
3775 fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
3776 loop->num,
3777 (int)expected_loop_iterations_unbounded (loop));
3779 return 0;
3782 } // anon namespace
3784 gimple_opt_pass *
3785 make_pass_profile (gcc::context *ctxt)
3787 return new pass_profile (ctxt);
3790 namespace {
3792 const pass_data pass_data_strip_predict_hints =
3794 GIMPLE_PASS, /* type */
3795 "*strip_predict_hints", /* name */
3796 OPTGROUP_NONE, /* optinfo_flags */
3797 TV_BRANCH_PROB, /* tv_id */
3798 PROP_cfg, /* properties_required */
3799 0, /* properties_provided */
3800 0, /* properties_destroyed */
3801 0, /* todo_flags_start */
3802 0, /* todo_flags_finish */
3805 class pass_strip_predict_hints : public gimple_opt_pass
3807 public:
3808 pass_strip_predict_hints (gcc::context *ctxt)
3809 : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
3812 /* opt_pass methods: */
3813 opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
3814 virtual unsigned int execute (function *);
3816 }; // class pass_strip_predict_hints
3818 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3819 we no longer need. */
3820 unsigned int
3821 pass_strip_predict_hints::execute (function *fun)
3823 basic_block bb;
3824 gimple *ass_stmt;
3825 tree var;
3826 bool changed = false;
3828 FOR_EACH_BB_FN (bb, fun)
3830 gimple_stmt_iterator bi;
3831 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
3833 gimple *stmt = gsi_stmt (bi);
3835 if (gimple_code (stmt) == GIMPLE_PREDICT)
3837 gsi_remove (&bi, true);
3838 changed = true;
3839 continue;
3841 else if (is_gimple_call (stmt))
3843 tree fndecl = gimple_call_fndecl (stmt);
3845 if ((fndecl
3846 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
3847 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
3848 && gimple_call_num_args (stmt) == 2)
3849 || (gimple_call_internal_p (stmt)
3850 && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
3852 var = gimple_call_lhs (stmt);
3853 changed = true;
3854 if (var)
3856 ass_stmt
3857 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
3858 gsi_replace (&bi, ass_stmt, true);
3860 else
3862 gsi_remove (&bi, true);
3863 continue;
3867 gsi_next (&bi);
3870 return changed ? TODO_cleanup_cfg : 0;
3873 } // anon namespace
3875 gimple_opt_pass *
3876 make_pass_strip_predict_hints (gcc::context *ctxt)
3878 return new pass_strip_predict_hints (ctxt);
3881 /* Rebuild function frequencies. Passes are in general expected to
3882 maintain profile by hand, however in some cases this is not possible:
3883 for example when inlining several functions with loops freuqencies might run
3884 out of scale and thus needs to be recomputed. */
3886 void
3887 rebuild_frequencies (void)
3889 timevar_push (TV_REBUILD_FREQUENCIES);
3891 /* When the max bb count in the function is small, there is a higher
3892 chance that there were truncation errors in the integer scaling
3893 of counts by inlining and other optimizations. This could lead
3894 to incorrect classification of code as being cold when it isn't.
3895 In that case, force the estimation of bb counts/frequencies from the
3896 branch probabilities, rather than computing frequencies from counts,
3897 which may also lead to frequencies incorrectly reduced to 0. There
3898 is less precision in the probabilities, so we only do this for small
3899 max counts. */
3900 cfun->cfg->count_max = profile_count::uninitialized ();
3901 basic_block bb;
3902 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3903 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
3905 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3907 loop_optimizer_init (0);
3908 add_noreturn_fake_exit_edges ();
3909 mark_irreducible_loops ();
3910 connect_infinite_loops_to_exit ();
3911 estimate_bb_frequencies (true);
3912 remove_fake_exit_edges ();
3913 loop_optimizer_finalize ();
3915 else if (profile_status_for_fn (cfun) == PROFILE_READ)
3916 update_max_bb_count ();
3917 else
3918 gcc_unreachable ();
3919 timevar_pop (TV_REBUILD_FREQUENCIES);
3922 /* Perform a dry run of the branch prediction pass and report comparsion of
3923 the predicted and real profile into the dump file. */
3925 void
3926 report_predictor_hitrates (void)
3928 unsigned nb_loops;
3930 loop_optimizer_init (LOOPS_NORMAL);
3931 if (dump_file && (dump_flags & TDF_DETAILS))
3932 flow_loops_dump (dump_file, NULL, 0);
3934 mark_irreducible_loops ();
3936 nb_loops = number_of_loops (cfun);
3937 if (nb_loops > 1)
3938 scev_initialize ();
3940 tree_estimate_probability (true);
3942 if (nb_loops > 1)
3943 scev_finalize ();
3945 loop_optimizer_finalize ();
3948 /* Force edge E to be cold.
3949 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
3950 keep low probability to represent possible error in a guess. This is used
3951 i.e. in case we predict loop to likely iterate given number of times but
3952 we are not 100% sure.
3954 This function locally updates profile without attempt to keep global
3955 consistency which can not be reached in full generality without full profile
3956 rebuild from probabilities alone. Doing so is not necessarily a good idea
3957 because frequencies and counts may be more realistic then probabilities.
3959 In some cases (such as for elimination of early exits during full loop
3960 unrolling) the caller can ensure that profile will get consistent
3961 afterwards. */
3963 void
3964 force_edge_cold (edge e, bool impossible)
3966 profile_count count_sum = profile_count::zero ();
3967 profile_probability prob_sum = profile_probability::never ();
3968 edge_iterator ei;
3969 edge e2;
3970 bool uninitialized_exit = false;
3972 profile_probability goal = (impossible ? profile_probability::never ()
3973 : profile_probability::very_unlikely ());
3975 /* If edge is already improbably or cold, just return. */
3976 if (e->probability <= goal
3977 && (!impossible || e->count () == profile_count::zero ()))
3978 return;
3979 FOR_EACH_EDGE (e2, ei, e->src->succs)
3980 if (e2 != e)
3982 if (e2->count ().initialized_p ())
3983 count_sum += e2->count ();
3984 else
3985 uninitialized_exit = true;
3986 if (e2->probability.initialized_p ())
3987 prob_sum += e2->probability;
3990 /* If there are other edges out of e->src, redistribute probabilitity
3991 there. */
3992 if (prob_sum > profile_probability::never ())
3994 if (!(e->probability < goal))
3995 e->probability = goal;
3997 profile_probability prob_comp = prob_sum / e->probability.invert ();
3999 if (dump_file && (dump_flags & TDF_DETAILS))
4000 fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4001 "probability to other edges.\n",
4002 e->src->index, e->dest->index,
4003 impossible ? "impossible" : "cold");
4004 FOR_EACH_EDGE (e2, ei, e->src->succs)
4005 if (e2 != e)
4007 e2->probability /= prob_comp;
4009 if (current_ir_type () != IR_GIMPLE
4010 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4011 update_br_prob_note (e->src);
4013 /* If all edges out of e->src are unlikely, the basic block itself
4014 is unlikely. */
4015 else
4017 if (prob_sum == profile_probability::never ())
4018 e->probability = profile_probability::always ();
4019 else
4021 if (impossible)
4022 e->probability = profile_probability::never ();
4023 /* If BB has some edges out that are not impossible, we can not
4024 assume that BB itself is. */
4025 impossible = false;
4027 if (current_ir_type () != IR_GIMPLE
4028 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4029 update_br_prob_note (e->src);
4030 if (e->src->count == profile_count::zero ())
4031 return;
4032 if (count_sum == profile_count::zero () && !uninitialized_exit
4033 && impossible)
4035 bool found = false;