PR libstdc++/87308 adjust regex used in std::any pretty printer
[official-gcc.git] / gcc / predict.c
blob8482737ab2722dcbda186146d7209def3dc0ae2c
1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* References:
22 [1] "Branch Prediction for Free"
23 Ball and Larus; PLDI '93.
24 [2] "Static Branch Frequency and Program Profile Analysis"
25 Wu and Larus; MICRO-27.
26 [3] "Corpus-based Static Branch Prediction"
27 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
30 #include "config.h"
31 #include "system.h"
32 #include "coretypes.h"
33 #include "backend.h"
34 #include "rtl.h"
35 #include "tree.h"
36 #include "gimple.h"
37 #include "cfghooks.h"
38 #include "tree-pass.h"
39 #include "ssa.h"
40 #include "memmodel.h"
41 #include "emit-rtl.h"
42 #include "cgraph.h"
43 #include "coverage.h"
44 #include "diagnostic-core.h"
45 #include "gimple-predict.h"
46 #include "fold-const.h"
47 #include "calls.h"
48 #include "cfganal.h"
49 #include "profile.h"
50 #include "sreal.h"
51 #include "params.h"
52 #include "cfgloop.h"
53 #include "gimple-iterator.h"
54 #include "tree-cfg.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-scalar-evolution.h"
58 #include "ipa-utils.h"
59 #include "gimple-pretty-print.h"
60 #include "selftest.h"
61 #include "cfgrtl.h"
62 #include "stringpool.h"
63 #include "attribs.h"
65 /* Enum with reasons why a predictor is ignored. */
67 enum predictor_reason
69 REASON_NONE,
70 REASON_IGNORED,
71 REASON_SINGLE_EDGE_DUPLICATE,
72 REASON_EDGE_PAIR_DUPLICATE
75 /* String messages for the aforementioned enum. */
77 static const char *reason_messages[] = {"", " (ignored)",
78 " (single edge duplicate)", " (edge pair duplicate)"};
80 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
81 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
82 static sreal real_almost_one, real_br_prob_base,
83 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
85 static void combine_predictions_for_insn (rtx_insn *, basic_block);
86 static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
87 enum predictor_reason, edge);
88 static void predict_paths_leading_to (basic_block, enum br_predictor,
89 enum prediction,
90 struct loop *in_loop = NULL);
91 static void predict_paths_leading_to_edge (edge, enum br_predictor,
92 enum prediction,
93 struct loop *in_loop = NULL);
94 static bool can_predict_insn_p (const rtx_insn *);
95 static HOST_WIDE_INT get_predictor_value (br_predictor, HOST_WIDE_INT);
97 /* Information we hold about each branch predictor.
98 Filled using information from predict.def. */
100 struct predictor_info
102 const char *const name; /* Name used in the debugging dumps. */
103 const int hitrate; /* Expected hitrate used by
104 predict_insn_def call. */
105 const int flags;
108 /* Use given predictor without Dempster-Shaffer theory if it matches
109 using first_match heuristics. */
110 #define PRED_FLAG_FIRST_MATCH 1
112 /* Recompute hitrate in percent to our representation. */
114 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
116 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
117 static const struct predictor_info predictor_info[]= {
118 #include "predict.def"
120 /* Upper bound on predictors. */
121 {NULL, 0, 0}
123 #undef DEF_PREDICTOR
125 static gcov_type min_count = -1;
127 /* Determine the threshold for hot BB counts. */
129 gcov_type
130 get_hot_bb_threshold ()
132 if (min_count == -1)
134 min_count
135 = profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION);
136 if (dump_file)
137 fprintf (dump_file, "Setting hotness threshold to %" PRId64 ".\n",
138 min_count);
140 return min_count;
143 /* Set the threshold for hot BB counts. */
145 void
146 set_hot_bb_threshold (gcov_type min)
148 min_count = min;
151 /* Return TRUE if frequency FREQ is considered to be hot. */
153 bool
154 maybe_hot_count_p (struct function *fun, profile_count count)
156 if (!count.initialized_p ())
157 return true;
158 if (count.ipa () == profile_count::zero ())
159 return false;
160 if (!count.ipa_p ())
162 struct cgraph_node *node = cgraph_node::get (fun->decl);
163 if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
165 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
166 return false;
167 if (node->frequency == NODE_FREQUENCY_HOT)
168 return true;
170 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
171 return true;
172 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
173 && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
174 return false;
175 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
176 return false;
177 if (count.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION), 1)
178 < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
179 return false;
180 return true;
182 /* Code executed at most once is not hot. */
183 if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
184 return false;
185 return (count.to_gcov_type () >= get_hot_bb_threshold ());
188 /* Return true in case BB can be CPU intensive and should be optimized
189 for maximal performance. */
191 bool
192 maybe_hot_bb_p (struct function *fun, const_basic_block bb)
194 gcc_checking_assert (fun);
195 return maybe_hot_count_p (fun, bb->count);
198 /* Return true in case BB can be CPU intensive and should be optimized
199 for maximal performance. */
201 bool
202 maybe_hot_edge_p (edge e)
204 return maybe_hot_count_p (cfun, e->count ());
207 /* Return true if profile COUNT and FREQUENCY, or function FUN static
208 node frequency reflects never being executed. */
210 static bool
211 probably_never_executed (struct function *fun,
212 profile_count count)
214 gcc_checking_assert (fun);
215 if (count.ipa () == profile_count::zero ())
216 return true;
217 /* Do not trust adjusted counts. This will make us to drop int cold section
218 code with low execution count as a result of inlining. These low counts
219 are not safe even with read profile and may lead us to dropping
220 code which actually gets executed into cold section of binary that is not
221 desirable. */
222 if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
224 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
225 if (count.apply_scale (unlikely_count_fraction, 1) >= profile_info->runs)
226 return false;
227 return true;
229 if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
230 && (cgraph_node::get (fun->decl)->frequency
231 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
232 return true;
233 return false;
237 /* Return true in case BB is probably never executed. */
239 bool
240 probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
242 return probably_never_executed (fun, bb->count);
246 /* Return true if E is unlikely executed for obvious reasons. */
248 static bool
249 unlikely_executed_edge_p (edge e)
251 return (e->count () == profile_count::zero ()
252 || e->probability == profile_probability::never ())
253 || (e->flags & (EDGE_EH | EDGE_FAKE));
256 /* Return true in case edge E is probably never executed. */
258 bool
259 probably_never_executed_edge_p (struct function *fun, edge e)
261 if (unlikely_executed_edge_p (e))
262 return true;
263 return probably_never_executed (fun, e->count ());
266 /* Return true when current function should always be optimized for size. */
268 bool
269 optimize_function_for_size_p (struct function *fun)
271 if (!fun || !fun->decl)
272 return optimize_size;
273 cgraph_node *n = cgraph_node::get (fun->decl);
274 return n && n->optimize_for_size_p ();
277 /* Return true when current function should always be optimized for speed. */
279 bool
280 optimize_function_for_speed_p (struct function *fun)
282 return !optimize_function_for_size_p (fun);
285 /* Return the optimization type that should be used for the function FUN. */
287 optimization_type
288 function_optimization_type (struct function *fun)
290 return (optimize_function_for_speed_p (fun)
291 ? OPTIMIZE_FOR_SPEED
292 : OPTIMIZE_FOR_SIZE);
295 /* Return TRUE when BB should be optimized for size. */
297 bool
298 optimize_bb_for_size_p (const_basic_block bb)
300 return (optimize_function_for_size_p (cfun)
301 || (bb && !maybe_hot_bb_p (cfun, bb)));
304 /* Return TRUE when BB should be optimized for speed. */
306 bool
307 optimize_bb_for_speed_p (const_basic_block bb)
309 return !optimize_bb_for_size_p (bb);
312 /* Return the optimization type that should be used for block BB. */
314 optimization_type
315 bb_optimization_type (const_basic_block bb)
317 return (optimize_bb_for_speed_p (bb)
318 ? OPTIMIZE_FOR_SPEED
319 : OPTIMIZE_FOR_SIZE);
322 /* Return TRUE when BB should be optimized for size. */
324 bool
325 optimize_edge_for_size_p (edge e)
327 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
330 /* Return TRUE when BB should be optimized for speed. */
332 bool
333 optimize_edge_for_speed_p (edge e)
335 return !optimize_edge_for_size_p (e);
338 /* Return TRUE when BB should be optimized for size. */
340 bool
341 optimize_insn_for_size_p (void)
343 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
346 /* Return TRUE when BB should be optimized for speed. */
348 bool
349 optimize_insn_for_speed_p (void)
351 return !optimize_insn_for_size_p ();
354 /* Return TRUE when LOOP should be optimized for size. */
356 bool
357 optimize_loop_for_size_p (struct loop *loop)
359 return optimize_bb_for_size_p (loop->header);
362 /* Return TRUE when LOOP should be optimized for speed. */
364 bool
365 optimize_loop_for_speed_p (struct loop *loop)
367 return optimize_bb_for_speed_p (loop->header);
370 /* Return TRUE when LOOP nest should be optimized for speed. */
372 bool
373 optimize_loop_nest_for_speed_p (struct loop *loop)
375 struct loop *l = loop;
376 if (optimize_loop_for_speed_p (loop))
377 return true;
378 l = loop->inner;
379 while (l && l != loop)
381 if (optimize_loop_for_speed_p (l))
382 return true;
383 if (l->inner)
384 l = l->inner;
385 else if (l->next)
386 l = l->next;
387 else
389 while (l != loop && !l->next)
390 l = loop_outer (l);
391 if (l != loop)
392 l = l->next;
395 return false;
398 /* Return TRUE when LOOP nest should be optimized for size. */
400 bool
401 optimize_loop_nest_for_size_p (struct loop *loop)
403 return !optimize_loop_nest_for_speed_p (loop);
406 /* Return true when edge E is likely to be well predictable by branch
407 predictor. */
409 bool
410 predictable_edge_p (edge e)
412 if (!e->probability.initialized_p ())
413 return false;
414 if ((e->probability.to_reg_br_prob_base ()
415 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
416 || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
417 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
418 return true;
419 return false;
423 /* Set RTL expansion for BB profile. */
425 void
426 rtl_profile_for_bb (basic_block bb)
428 crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
431 /* Set RTL expansion for edge profile. */
433 void
434 rtl_profile_for_edge (edge e)
436 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
439 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
440 void
441 default_rtl_profile (void)
443 crtl->maybe_hot_insn_p = true;
446 /* Return true if the one of outgoing edges is already predicted by
447 PREDICTOR. */
449 bool
450 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
452 rtx note;
453 if (!INSN_P (BB_END (bb)))
454 return false;
455 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
456 if (REG_NOTE_KIND (note) == REG_BR_PRED
457 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
458 return true;
459 return false;
462 /* Structure representing predictions in tree level. */
464 struct edge_prediction {
465 struct edge_prediction *ep_next;
466 edge ep_edge;
467 enum br_predictor ep_predictor;
468 int ep_probability;
471 /* This map contains for a basic block the list of predictions for the
472 outgoing edges. */
474 static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
476 /* Return true if the one of outgoing edges is already predicted by
477 PREDICTOR. */
479 bool
480 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
482 struct edge_prediction *i;
483 edge_prediction **preds = bb_predictions->get (bb);
485 if (!preds)
486 return false;
488 for (i = *preds; i; i = i->ep_next)
489 if (i->ep_predictor == predictor)
490 return true;
491 return false;
494 /* Return true if the one of outgoing edges is already predicted by
495 PREDICTOR for edge E predicted as TAKEN. */
497 bool
498 edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
500 struct edge_prediction *i;
501 basic_block bb = e->src;
502 edge_prediction **preds = bb_predictions->get (bb);
503 if (!preds)
504 return false;
506 int probability = predictor_info[(int) predictor].hitrate;
508 if (taken != TAKEN)
509 probability = REG_BR_PROB_BASE - probability;
511 for (i = *preds; i; i = i->ep_next)
512 if (i->ep_predictor == predictor
513 && i->ep_edge == e
514 && i->ep_probability == probability)
515 return true;
516 return false;
519 /* Same predicate as above, working on edges. */
520 bool
521 edge_probability_reliable_p (const_edge e)
523 return e->probability.probably_reliable_p ();
526 /* Same predicate as edge_probability_reliable_p, working on notes. */
527 bool
528 br_prob_note_reliable_p (const_rtx note)
530 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
531 return profile_probability::from_reg_br_prob_note
532 (XINT (note, 0)).probably_reliable_p ();
535 static void
536 predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
538 gcc_assert (any_condjump_p (insn));
539 if (!flag_guess_branch_prob)
540 return;
542 add_reg_note (insn, REG_BR_PRED,
543 gen_rtx_CONCAT (VOIDmode,
544 GEN_INT ((int) predictor),
545 GEN_INT ((int) probability)));
548 /* Predict insn by given predictor. */
550 void
551 predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
552 enum prediction taken)
554 int probability = predictor_info[(int) predictor].hitrate;
555 gcc_assert (probability != PROB_UNINITIALIZED);
557 if (taken != TAKEN)
558 probability = REG_BR_PROB_BASE - probability;
560 predict_insn (insn, predictor, probability);
563 /* Predict edge E with given probability if possible. */
565 void
566 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
568 rtx_insn *last_insn;
569 last_insn = BB_END (e->src);
571 /* We can store the branch prediction information only about
572 conditional jumps. */
573 if (!any_condjump_p (last_insn))
574 return;
576 /* We always store probability of branching. */
577 if (e->flags & EDGE_FALLTHRU)
578 probability = REG_BR_PROB_BASE - probability;
580 predict_insn (last_insn, predictor, probability);
583 /* Predict edge E with the given PROBABILITY. */
584 void
585 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
587 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
588 && EDGE_COUNT (e->src->succs) > 1
589 && flag_guess_branch_prob
590 && optimize)
592 struct edge_prediction *i = XNEW (struct edge_prediction);
593 edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
595 i->ep_next = preds;
596 preds = i;
597 i->ep_probability = probability;
598 i->ep_predictor = predictor;
599 i->ep_edge = e;
603 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
604 to the filter function. */
606 void
607 filter_predictions (edge_prediction **preds,
608 bool (*filter) (edge_prediction *, void *), void *data)
610 if (!bb_predictions)
611 return;
613 if (preds)
615 struct edge_prediction **prediction = preds;
616 struct edge_prediction *next;
618 while (*prediction)
620 if ((*filter) (*prediction, data))
621 prediction = &((*prediction)->ep_next);
622 else
624 next = (*prediction)->ep_next;
625 free (*prediction);
626 *prediction = next;
632 /* Filter function predicate that returns true for a edge predicate P
633 if its edge is equal to DATA. */
635 bool
636 equal_edge_p (edge_prediction *p, void *data)
638 return p->ep_edge == (edge)data;
641 /* Remove all predictions on given basic block that are attached
642 to edge E. */
643 void
644 remove_predictions_associated_with_edge (edge e)
646 if (!bb_predictions)
647 return;
649 edge_prediction **preds = bb_predictions->get (e->src);
650 filter_predictions (preds, equal_edge_p, e);
653 /* Clears the list of predictions stored for BB. */
655 static void
656 clear_bb_predictions (basic_block bb)
658 edge_prediction **preds = bb_predictions->get (bb);
659 struct edge_prediction *pred, *next;
661 if (!preds)
662 return;
664 for (pred = *preds; pred; pred = next)
666 next = pred->ep_next;
667 free (pred);
669 *preds = NULL;
672 /* Return true when we can store prediction on insn INSN.
673 At the moment we represent predictions only on conditional
674 jumps, not at computed jump or other complicated cases. */
675 static bool
676 can_predict_insn_p (const rtx_insn *insn)
678 return (JUMP_P (insn)
679 && any_condjump_p (insn)
680 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
683 /* Predict edge E by given predictor if possible. */
685 void
686 predict_edge_def (edge e, enum br_predictor predictor,
687 enum prediction taken)
689 int probability = predictor_info[(int) predictor].hitrate;
691 if (taken != TAKEN)
692 probability = REG_BR_PROB_BASE - probability;
694 predict_edge (e, predictor, probability);
697 /* Invert all branch predictions or probability notes in the INSN. This needs
698 to be done each time we invert the condition used by the jump. */
700 void
701 invert_br_probabilities (rtx insn)
703 rtx note;
705 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
706 if (REG_NOTE_KIND (note) == REG_BR_PROB)
707 XINT (note, 0) = profile_probability::from_reg_br_prob_note
708 (XINT (note, 0)).invert ().to_reg_br_prob_note ();
709 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
710 XEXP (XEXP (note, 0), 1)
711 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
714 /* Dump information about the branch prediction to the output file. */
716 static void
717 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
718 basic_block bb, enum predictor_reason reason = REASON_NONE,
719 edge ep_edge = NULL)
721 edge e = ep_edge;
722 edge_iterator ei;
724 if (!file)
725 return;
727 if (e == NULL)
728 FOR_EACH_EDGE (e, ei, bb->succs)
729 if (! (e->flags & EDGE_FALLTHRU))
730 break;
732 char edge_info_str[128];
733 if (ep_edge)
734 sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
735 ep_edge->dest->index);
736 else
737 edge_info_str[0] = '\0';
739 fprintf (file, " %s heuristics%s%s: %.2f%%",
740 predictor_info[predictor].name,
741 edge_info_str, reason_messages[reason],
742 probability * 100.0 / REG_BR_PROB_BASE);
744 if (bb->count.initialized_p ())
746 fprintf (file, " exec ");
747 bb->count.dump (file);
748 if (e)
750 fprintf (file, " hit ");
751 e->count ().dump (file);
752 fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
753 / bb->count.to_gcov_type ());
757 fprintf (file, "\n");
759 /* Print output that be easily read by analyze_brprob.py script. We are
760 interested only in counts that are read from GCDA files. */
761 if (dump_file && (dump_flags & TDF_DETAILS)
762 && bb->count.precise_p ()
763 && reason == REASON_NONE)
765 gcc_assert (e->count ().precise_p ());
766 fprintf (file, ";;heuristics;%s;%" PRId64 ";%" PRId64 ";%.1f;\n",
767 predictor_info[predictor].name,
768 bb->count.to_gcov_type (), e->count ().to_gcov_type (),
769 probability * 100.0 / REG_BR_PROB_BASE);
773 /* Return true if STMT is known to be unlikely executed. */
775 static bool
776 unlikely_executed_stmt_p (gimple *stmt)
778 if (!is_gimple_call (stmt))
779 return false;
780 /* NORETURN attribute alone is not strong enough: exit() may be quite
781 likely executed once during program run. */
782 if (gimple_call_fntype (stmt)
783 && lookup_attribute ("cold",
784 TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
785 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
786 return true;
787 tree decl = gimple_call_fndecl (stmt);
788 if (!decl)
789 return false;
790 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
791 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
792 return true;
794 cgraph_node *n = cgraph_node::get (decl);
795 if (!n)
796 return false;
798 availability avail;
799 n = n->ultimate_alias_target (&avail);
800 if (avail < AVAIL_AVAILABLE)
801 return false;
802 if (!n->analyzed
803 || n->decl == current_function_decl)
804 return false;
805 return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
808 /* Return true if BB is unlikely executed. */
810 static bool
811 unlikely_executed_bb_p (basic_block bb)
813 if (bb->count == profile_count::zero ())
814 return true;
815 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
816 return false;
817 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
818 !gsi_end_p (gsi); gsi_next (&gsi))
820 if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
821 return true;
822 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
823 return false;
825 return false;
828 /* We can not predict the probabilities of outgoing edges of bb. Set them
829 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
830 even probability for all edges not mentioned in the set. These edges
831 are given PROB_VERY_UNLIKELY probability. Similarly for LIKELY_EDGES,
832 if we have exactly one likely edge, make the other edges predicted
833 as not probable. */
835 static void
836 set_even_probabilities (basic_block bb,
837 hash_set<edge> *unlikely_edges = NULL,
838 hash_set<edge_prediction *> *likely_edges = NULL)
840 unsigned nedges = 0, unlikely_count = 0;
841 edge e = NULL;
842 edge_iterator ei;
843 profile_probability all = profile_probability::always ();
845 FOR_EACH_EDGE (e, ei, bb->succs)
846 if (e->probability.initialized_p ())
847 all -= e->probability;
848 else if (!unlikely_executed_edge_p (e))
850 nedges++;
851 if (unlikely_edges != NULL && unlikely_edges->contains (e))
853 all -= profile_probability::very_unlikely ();
854 unlikely_count++;
858 /* Make the distribution even if all edges are unlikely. */
859 unsigned likely_count = likely_edges ? likely_edges->elements () : 0;
860 if (unlikely_count == nedges)
862 unlikely_edges = NULL;
863 unlikely_count = 0;
866 /* If we have one likely edge, then use its probability and distribute
867 remaining probabilities as even. */
868 if (likely_count == 1)
870 FOR_EACH_EDGE (e, ei, bb->succs)
871 if (e->probability.initialized_p ())
873 else if (!unlikely_executed_edge_p (e))
875 edge_prediction *prediction = *likely_edges->begin ();
876 int p = prediction->ep_probability;
877 profile_probability prob
878 = profile_probability::from_reg_br_prob_base (p);
879 profile_probability remainder = prob.invert ();
881 if (prediction->ep_edge == e)
882 e->probability = prob;
883 else
884 e->probability = remainder.apply_scale (1, nedges - 1);
886 else
887 e->probability = profile_probability::never ();
889 else
891 /* Make all unlikely edges unlikely and the rest will have even
892 probability. */
893 unsigned scale = nedges - unlikely_count;
894 FOR_EACH_EDGE (e, ei, bb->succs)
895 if (e->probability.initialized_p ())
897 else if (!unlikely_executed_edge_p (e))
899 if (unlikely_edges != NULL && unlikely_edges->contains (e))
900 e->probability = profile_probability::very_unlikely ();
901 else
902 e->probability = all.apply_scale (1, scale);
904 else
905 e->probability = profile_probability::never ();
909 /* Add REG_BR_PROB note to JUMP with PROB. */
911 void
912 add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
914 gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
915 add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
918 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
919 note if not already present. Remove now useless REG_BR_PRED notes. */
921 static void
922 combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
924 rtx prob_note;
925 rtx *pnote;
926 rtx note;
927 int best_probability = PROB_EVEN;
928 enum br_predictor best_predictor = END_PREDICTORS;
929 int combined_probability = REG_BR_PROB_BASE / 2;
930 int d;
931 bool first_match = false;
932 bool found = false;
934 if (!can_predict_insn_p (insn))
936 set_even_probabilities (bb);
937 return;
940 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
941 pnote = &REG_NOTES (insn);
942 if (dump_file)
943 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
944 bb->index);
946 /* We implement "first match" heuristics and use probability guessed
947 by predictor with smallest index. */
948 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
949 if (REG_NOTE_KIND (note) == REG_BR_PRED)
951 enum br_predictor predictor = ((enum br_predictor)
952 INTVAL (XEXP (XEXP (note, 0), 0)));
953 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
955 found = true;
956 if (best_predictor > predictor
957 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
958 best_probability = probability, best_predictor = predictor;
960 d = (combined_probability * probability
961 + (REG_BR_PROB_BASE - combined_probability)
962 * (REG_BR_PROB_BASE - probability));
964 /* Use FP math to avoid overflows of 32bit integers. */
965 if (d == 0)
966 /* If one probability is 0% and one 100%, avoid division by zero. */
967 combined_probability = REG_BR_PROB_BASE / 2;
968 else
969 combined_probability = (((double) combined_probability) * probability
970 * REG_BR_PROB_BASE / d + 0.5);
973 /* Decide which heuristic to use. In case we didn't match anything,
974 use no_prediction heuristic, in case we did match, use either
975 first match or Dempster-Shaffer theory depending on the flags. */
977 if (best_predictor != END_PREDICTORS)
978 first_match = true;
980 if (!found)
981 dump_prediction (dump_file, PRED_NO_PREDICTION,
982 combined_probability, bb);
983 else
985 if (!first_match)
986 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
987 bb, !first_match ? REASON_NONE : REASON_IGNORED);
988 else
989 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
990 bb, first_match ? REASON_NONE : REASON_IGNORED);
993 if (first_match)
994 combined_probability = best_probability;
995 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
997 while (*pnote)
999 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
1001 enum br_predictor predictor = ((enum br_predictor)
1002 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
1003 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
1005 dump_prediction (dump_file, predictor, probability, bb,
1006 (!first_match || best_predictor == predictor)
1007 ? REASON_NONE : REASON_IGNORED);
1008 *pnote = XEXP (*pnote, 1);
1010 else
1011 pnote = &XEXP (*pnote, 1);
1014 if (!prob_note)
1016 profile_probability p
1017 = profile_probability::from_reg_br_prob_base (combined_probability);
1018 add_reg_br_prob_note (insn, p);
1020 /* Save the prediction into CFG in case we are seeing non-degenerated
1021 conditional jump. */
1022 if (!single_succ_p (bb))
1024 BRANCH_EDGE (bb)->probability = p;
1025 FALLTHRU_EDGE (bb)->probability
1026 = BRANCH_EDGE (bb)->probability.invert ();
1029 else if (!single_succ_p (bb))
1031 profile_probability prob = profile_probability::from_reg_br_prob_note
1032 (XINT (prob_note, 0));
1034 BRANCH_EDGE (bb)->probability = prob;
1035 FALLTHRU_EDGE (bb)->probability = prob.invert ();
1037 else
1038 single_succ_edge (bb)->probability = profile_probability::always ();
1041 /* Edge prediction hash traits. */
1043 struct predictor_hash: pointer_hash <edge_prediction>
1046 static inline hashval_t hash (const edge_prediction *);
1047 static inline bool equal (const edge_prediction *, const edge_prediction *);
1050 /* Calculate hash value of an edge prediction P based on predictor and
1051 normalized probability. */
1053 inline hashval_t
1054 predictor_hash::hash (const edge_prediction *p)
1056 inchash::hash hstate;
1057 hstate.add_int (p->ep_predictor);
1059 int prob = p->ep_probability;
1060 if (prob > REG_BR_PROB_BASE / 2)
1061 prob = REG_BR_PROB_BASE - prob;
1063 hstate.add_int (prob);
1065 return hstate.end ();
1068 /* Return true whether edge predictions P1 and P2 use the same predictor and
1069 have equal (or opposed probability). */
1071 inline bool
1072 predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1074 return (p1->ep_predictor == p2->ep_predictor
1075 && (p1->ep_probability == p2->ep_probability
1076 || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1079 struct predictor_hash_traits: predictor_hash,
1080 typed_noop_remove <edge_prediction *> {};
1082 /* Return true if edge prediction P is not in DATA hash set. */
1084 static bool
1085 not_removed_prediction_p (edge_prediction *p, void *data)
1087 hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1088 return !remove->contains (p);
1091 /* Prune predictions for a basic block BB. Currently we do following
1092 clean-up steps:
1094 1) remove duplicate prediction that is guessed with the same probability
1095 (different than 1/2) to both edge
1096 2) remove duplicates for a prediction that belongs with the same probability
1097 to a single edge
1101 static void
1102 prune_predictions_for_bb (basic_block bb)
1104 edge_prediction **preds = bb_predictions->get (bb);
1106 if (preds)
1108 hash_table <predictor_hash_traits> s (13);
1109 hash_set <edge_prediction *> remove;
1111 /* Step 1: identify predictors that should be removed. */
1112 for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1114 edge_prediction *existing = s.find (pred);
1115 if (existing)
1117 if (pred->ep_edge == existing->ep_edge
1118 && pred->ep_probability == existing->ep_probability)
1120 /* Remove a duplicate predictor. */
1121 dump_prediction (dump_file, pred->ep_predictor,
1122 pred->ep_probability, bb,
1123 REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1125 remove.add (pred);
1127 else if (pred->ep_edge != existing->ep_edge
1128 && pred->ep_probability == existing->ep_probability
1129 && pred->ep_probability != REG_BR_PROB_BASE / 2)
1131 /* Remove both predictors as they predict the same
1132 for both edges. */
1133 dump_prediction (dump_file, existing->ep_predictor,
1134 pred->ep_probability, bb,
1135 REASON_EDGE_PAIR_DUPLICATE,
1136 existing->ep_edge);
1137 dump_prediction (dump_file, pred->ep_predictor,
1138 pred->ep_probability, bb,
1139 REASON_EDGE_PAIR_DUPLICATE,
1140 pred->ep_edge);
1142 remove.add (existing);
1143 remove.add (pred);
1147 edge_prediction **slot2 = s.find_slot (pred, INSERT);
1148 *slot2 = pred;
1151 /* Step 2: Remove predictors. */
1152 filter_predictions (preds, not_removed_prediction_p, &remove);
1156 /* Combine predictions into single probability and store them into CFG.
1157 Remove now useless prediction entries.
1158 If DRY_RUN is set, only produce dumps and do not modify profile. */
1160 static void
1161 combine_predictions_for_bb (basic_block bb, bool dry_run)
1163 int best_probability = PROB_EVEN;
1164 enum br_predictor best_predictor = END_PREDICTORS;
1165 int combined_probability = REG_BR_PROB_BASE / 2;
1166 int d;
1167 bool first_match = false;
1168 bool found = false;
1169 struct edge_prediction *pred;
1170 int nedges = 0;
1171 edge e, first = NULL, second = NULL;
1172 edge_iterator ei;
1173 int nzero = 0;
1174 int nunknown = 0;
1176 FOR_EACH_EDGE (e, ei, bb->succs)
1178 if (!unlikely_executed_edge_p (e))
1180 nedges ++;
1181 if (first && !second)
1182 second = e;
1183 if (!first)
1184 first = e;
1186 else if (!e->probability.initialized_p ())
1187 e->probability = profile_probability::never ();
1188 if (!e->probability.initialized_p ())
1189 nunknown++;
1190 else if (e->probability == profile_probability::never ())
1191 nzero++;
1194 /* When there is no successor or only one choice, prediction is easy.
1196 When we have a basic block with more than 2 successors, the situation
1197 is more complicated as DS theory cannot be used literally.
1198 More precisely, let's assume we predicted edge e1 with probability p1,
1199 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1200 need to find probability of e.g. m1({b2}), which we don't know.
1201 The only approximation is to equally distribute 1-p1 to all edges
1202 different from b1.
1204 According to numbers we've got from SPEC2006 benchark, there's only
1205 one interesting reliable predictor (noreturn call), which can be
1206 handled with a bit easier approach. */
1207 if (nedges != 2)
1209 hash_set<edge> unlikely_edges (4);
1210 hash_set<edge_prediction *> likely_edges (4);
1212 /* Identify all edges that have a probability close to very unlikely.
1213 Doing the approach for very unlikely doesn't worth for doing as
1214 there's no such probability in SPEC2006 benchmark. */
1215 edge_prediction **preds = bb_predictions->get (bb);
1216 if (preds)
1217 for (pred = *preds; pred; pred = pred->ep_next)
1219 if (pred->ep_probability <= PROB_VERY_UNLIKELY)
1220 unlikely_edges.add (pred->ep_edge);
1221 if (pred->ep_probability >= PROB_VERY_LIKELY
1222 || pred->ep_predictor == PRED_BUILTIN_EXPECT)
1223 likely_edges.add (pred);
1226 if (!dry_run)
1227 set_even_probabilities (bb, &unlikely_edges, &likely_edges);
1228 clear_bb_predictions (bb);
1229 if (dump_file)
1231 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1232 if (unlikely_edges.elements () == 0)
1233 fprintf (dump_file,
1234 "%i edges in bb %i predicted to even probabilities\n",
1235 nedges, bb->index);
1236 else
1238 fprintf (dump_file,
1239 "%i edges in bb %i predicted with some unlikely edges\n",
1240 nedges, bb->index);
1241 FOR_EACH_EDGE (e, ei, bb->succs)
1242 if (!unlikely_executed_edge_p (e))
1243 dump_prediction (dump_file, PRED_COMBINED,
1244 e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
1247 return;
1250 if (dump_file)
1251 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1253 prune_predictions_for_bb (bb);
1255 edge_prediction **preds = bb_predictions->get (bb);
1257 if (preds)
1259 /* We implement "first match" heuristics and use probability guessed
1260 by predictor with smallest index. */
1261 for (pred = *preds; pred; pred = pred->ep_next)
1263 enum br_predictor predictor = pred->ep_predictor;
1264 int probability = pred->ep_probability;
1266 if (pred->ep_edge != first)
1267 probability = REG_BR_PROB_BASE - probability;
1269 found = true;
1270 /* First match heuristics would be widly confused if we predicted
1271 both directions. */
1272 if (best_predictor > predictor
1273 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1275 struct edge_prediction *pred2;
1276 int prob = probability;
1278 for (pred2 = (struct edge_prediction *) *preds;
1279 pred2; pred2 = pred2->ep_next)
1280 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1282 int probability2 = pred2->ep_probability;
1284 if (pred2->ep_edge != first)
1285 probability2 = REG_BR_PROB_BASE - probability2;
1287 if ((probability < REG_BR_PROB_BASE / 2) !=
1288 (probability2 < REG_BR_PROB_BASE / 2))
1289 break;
1291 /* If the same predictor later gave better result, go for it! */
1292 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1293 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1294 prob = probability2;
1296 if (!pred2)
1297 best_probability = prob, best_predictor = predictor;
1300 d = (combined_probability * probability
1301 + (REG_BR_PROB_BASE - combined_probability)
1302 * (REG_BR_PROB_BASE - probability));
1304 /* Use FP math to avoid overflows of 32bit integers. */
1305 if (d == 0)
1306 /* If one probability is 0% and one 100%, avoid division by zero. */
1307 combined_probability = REG_BR_PROB_BASE / 2;
1308 else
1309 combined_probability = (((double) combined_probability)
1310 * probability
1311 * REG_BR_PROB_BASE / d + 0.5);
1315 /* Decide which heuristic to use. In case we didn't match anything,
1316 use no_prediction heuristic, in case we did match, use either
1317 first match or Dempster-Shaffer theory depending on the flags. */
1319 if (best_predictor != END_PREDICTORS)
1320 first_match = true;
1322 if (!found)
1323 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1324 else
1326 if (!first_match)
1327 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1328 !first_match ? REASON_NONE : REASON_IGNORED);
1329 else
1330 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1331 first_match ? REASON_NONE : REASON_IGNORED);
1334 if (first_match)
1335 combined_probability = best_probability;
1336 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1338 if (preds)
1340 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1342 enum br_predictor predictor = pred->ep_predictor;
1343 int probability = pred->ep_probability;
1345 dump_prediction (dump_file, predictor, probability, bb,
1346 (!first_match || best_predictor == predictor)
1347 ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1350 clear_bb_predictions (bb);
1353 /* If we have only one successor which is unknown, we can compute missing
1354 probablity. */
1355 if (nunknown == 1)
1357 profile_probability prob = profile_probability::always ();
1358 edge missing = NULL;
1360 FOR_EACH_EDGE (e, ei, bb->succs)
1361 if (e->probability.initialized_p ())
1362 prob -= e->probability;
1363 else if (missing == NULL)
1364 missing = e;
1365 else
1366 gcc_unreachable ();
1367 missing->probability = prob;
1369 /* If nothing is unknown, we have nothing to update. */
1370 else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1372 else if (!dry_run)
1374 first->probability
1375 = profile_probability::from_reg_br_prob_base (combined_probability);
1376 second->probability = first->probability.invert ();
1380 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1381 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1383 T1 and T2 should be one of the following cases:
1384 1. T1 is SSA_NAME, T2 is NULL
1385 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1386 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1388 static tree
1389 strips_small_constant (tree t1, tree t2)
1391 tree ret = NULL;
1392 int value = 0;
1394 if (!t1)
1395 return NULL;
1396 else if (TREE_CODE (t1) == SSA_NAME)
1397 ret = t1;
1398 else if (tree_fits_shwi_p (t1))
1399 value = tree_to_shwi (t1);
1400 else
1401 return NULL;
1403 if (!t2)
1404 return ret;
1405 else if (tree_fits_shwi_p (t2))
1406 value = tree_to_shwi (t2);
1407 else if (TREE_CODE (t2) == SSA_NAME)
1409 if (ret)
1410 return NULL;
1411 else
1412 ret = t2;
1415 if (value <= 4 && value >= -4)
1416 return ret;
1417 else
1418 return NULL;
1421 /* Return the SSA_NAME in T or T's operands.
1422 Return NULL if SSA_NAME cannot be found. */
1424 static tree
1425 get_base_value (tree t)
1427 if (TREE_CODE (t) == SSA_NAME)
1428 return t;
1430 if (!BINARY_CLASS_P (t))
1431 return NULL;
1433 switch (TREE_OPERAND_LENGTH (t))
1435 case 1:
1436 return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1437 case 2:
1438 return strips_small_constant (TREE_OPERAND (t, 0),
1439 TREE_OPERAND (t, 1));
1440 default:
1441 return NULL;
1445 /* Check the compare STMT in LOOP. If it compares an induction
1446 variable to a loop invariant, return true, and save
1447 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1448 Otherwise return false and set LOOP_INVAIANT to NULL. */
1450 static bool
1451 is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
1452 tree *loop_invariant,
1453 enum tree_code *compare_code,
1454 tree *loop_step,
1455 tree *loop_iv_base)
1457 tree op0, op1, bound, base;
1458 affine_iv iv0, iv1;
1459 enum tree_code code;
1460 tree step;
1462 code = gimple_cond_code (stmt);
1463 *loop_invariant = NULL;
1465 switch (code)
1467 case GT_EXPR:
1468 case GE_EXPR:
1469 case NE_EXPR:
1470 case LT_EXPR:
1471 case LE_EXPR:
1472 case EQ_EXPR:
1473 break;
1475 default:
1476 return false;
1479 op0 = gimple_cond_lhs (stmt);
1480 op1 = gimple_cond_rhs (stmt);
1482 if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1483 || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1484 return false;
1485 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1486 return false;
1487 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1488 return false;
1489 if (TREE_CODE (iv0.step) != INTEGER_CST
1490 || TREE_CODE (iv1.step) != INTEGER_CST)
1491 return false;
1492 if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1493 || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1494 return false;
1496 if (integer_zerop (iv0.step))
1498 if (code != NE_EXPR && code != EQ_EXPR)
1499 code = invert_tree_comparison (code, false);
1500 bound = iv0.base;
1501 base = iv1.base;
1502 if (tree_fits_shwi_p (iv1.step))
1503 step = iv1.step;
1504 else
1505 return false;
1507 else
1509 bound = iv1.base;
1510 base = iv0.base;
1511 if (tree_fits_shwi_p (iv0.step))
1512 step = iv0.step;
1513 else
1514 return false;
1517 if (TREE_CODE (bound) != INTEGER_CST)
1518 bound = get_base_value (bound);
1519 if (!bound)
1520 return false;
1521 if (TREE_CODE (base) != INTEGER_CST)
1522 base = get_base_value (base);
1523 if (!base)
1524 return false;
1526 *loop_invariant = bound;
1527 *compare_code = code;
1528 *loop_step = step;
1529 *loop_iv_base = base;
1530 return true;
1533 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1535 static bool
1536 expr_coherent_p (tree t1, tree t2)
1538 gimple *stmt;
1539 tree ssa_name_1 = NULL;
1540 tree ssa_name_2 = NULL;
1542 gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1543 gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1545 if (t1 == t2)
1546 return true;
1548 if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1549 return true;
1550 if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1551 return false;
1553 /* Check to see if t1 is expressed/defined with t2. */
1554 stmt = SSA_NAME_DEF_STMT (t1);
1555 gcc_assert (stmt != NULL);
1556 if (is_gimple_assign (stmt))
1558 ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1559 if (ssa_name_1 && ssa_name_1 == t2)
1560 return true;
1563 /* Check to see if t2 is expressed/defined with t1. */
1564 stmt = SSA_NAME_DEF_STMT (t2);
1565 gcc_assert (stmt != NULL);
1566 if (is_gimple_assign (stmt))
1568 ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1569 if (ssa_name_2 && ssa_name_2 == t1)
1570 return true;
1573 /* Compare if t1 and t2's def_stmts are identical. */
1574 if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1575 return true;
1576 else
1577 return false;
1580 /* Return true if E is predicted by one of loop heuristics. */
1582 static bool
1583 predicted_by_loop_heuristics_p (basic_block bb)
1585 struct edge_prediction *i;
1586 edge_prediction **preds = bb_predictions->get (bb);
1588 if (!preds)
1589 return false;
1591 for (i = *preds; i; i = i->ep_next)
1592 if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1593 || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1594 || i->ep_predictor == PRED_LOOP_ITERATIONS
1595 || i->ep_predictor == PRED_LOOP_EXIT
1596 || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1597 || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1598 return true;
1599 return false;
1602 /* Predict branch probability of BB when BB contains a branch that compares
1603 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1604 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1606 E.g.
1607 for (int i = 0; i < bound; i++) {
1608 if (i < bound - 2)
1609 computation_1();
1610 else
1611 computation_2();
1614 In this loop, we will predict the branch inside the loop to be taken. */
1616 static void
1617 predict_iv_comparison (struct loop *loop, basic_block bb,
1618 tree loop_bound_var,
1619 tree loop_iv_base_var,
1620 enum tree_code loop_bound_code,
1621 int loop_bound_step)
1623 gimple *stmt;
1624 tree compare_var, compare_base;
1625 enum tree_code compare_code;
1626 tree compare_step_var;
1627 edge then_edge;
1628 edge_iterator ei;
1630 if (predicted_by_loop_heuristics_p (bb))
1631 return;
1633 stmt = last_stmt (bb);
1634 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1635 return;
1636 if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
1637 loop, &compare_var,
1638 &compare_code,
1639 &compare_step_var,
1640 &compare_base))
1641 return;
1643 /* Find the taken edge. */
1644 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1645 if (then_edge->flags & EDGE_TRUE_VALUE)
1646 break;
1648 /* When comparing an IV to a loop invariant, NE is more likely to be
1649 taken while EQ is more likely to be not-taken. */
1650 if (compare_code == NE_EXPR)
1652 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1653 return;
1655 else if (compare_code == EQ_EXPR)
1657 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1658 return;
1661 if (!expr_coherent_p (loop_iv_base_var, compare_base))
1662 return;
1664 /* If loop bound, base and compare bound are all constants, we can
1665 calculate the probability directly. */
1666 if (tree_fits_shwi_p (loop_bound_var)
1667 && tree_fits_shwi_p (compare_var)
1668 && tree_fits_shwi_p (compare_base))
1670 int probability;
1671 wi::overflow_type overflow;
1672 bool overall_overflow = false;
1673 widest_int compare_count, tem;
1675 /* (loop_bound - base) / compare_step */
1676 tem = wi::sub (wi::to_widest (loop_bound_var),
1677 wi::to_widest (compare_base), SIGNED, &overflow);
1678 overall_overflow |= overflow;
1679 widest_int loop_count = wi::div_trunc (tem,
1680 wi::to_widest (compare_step_var),
1681 SIGNED, &overflow);
1682 overall_overflow |= overflow;
1684 if (!wi::neg_p (wi::to_widest (compare_step_var))
1685 ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1687 /* (loop_bound - compare_bound) / compare_step */
1688 tem = wi::sub (wi::to_widest (loop_bound_var),
1689 wi::to_widest (compare_var), SIGNED, &overflow);
1690 overall_overflow |= overflow;
1691 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1692 SIGNED, &overflow);
1693 overall_overflow |= overflow;
1695 else
1697 /* (compare_bound - base) / compare_step */
1698 tem = wi::sub (wi::to_widest (compare_var),
1699 wi::to_widest (compare_base), SIGNED, &overflow);
1700 overall_overflow |= overflow;
1701 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1702 SIGNED, &overflow);
1703 overall_overflow |= overflow;
1705 if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1706 ++compare_count;
1707 if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1708 ++loop_count;
1709 if (wi::neg_p (compare_count))
1710 compare_count = 0;
1711 if (wi::neg_p (loop_count))
1712 loop_count = 0;
1713 if (loop_count == 0)
1714 probability = 0;
1715 else if (wi::cmps (compare_count, loop_count) == 1)
1716 probability = REG_BR_PROB_BASE;
1717 else
1719 tem = compare_count * REG_BR_PROB_BASE;
1720 tem = wi::udiv_trunc (tem, loop_count);
1721 probability = tem.to_uhwi ();
1724 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1725 if (!overall_overflow)
1726 predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1728 return;
1731 if (expr_coherent_p (loop_bound_var, compare_var))
1733 if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1734 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1735 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1736 else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1737 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1738 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1739 else if (loop_bound_code == NE_EXPR)
1741 /* If the loop backedge condition is "(i != bound)", we do
1742 the comparison based on the step of IV:
1743 * step < 0 : backedge condition is like (i > bound)
1744 * step > 0 : backedge condition is like (i < bound) */
1745 gcc_assert (loop_bound_step != 0);
1746 if (loop_bound_step > 0
1747 && (compare_code == LT_EXPR
1748 || compare_code == LE_EXPR))
1749 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1750 else if (loop_bound_step < 0
1751 && (compare_code == GT_EXPR
1752 || compare_code == GE_EXPR))
1753 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1754 else
1755 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1757 else
1758 /* The branch is predicted not-taken if loop_bound_code is
1759 opposite with compare_code. */
1760 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1762 else if (expr_coherent_p (loop_iv_base_var, compare_var))
1764 /* For cases like:
1765 for (i = s; i < h; i++)
1766 if (i > s + 2) ....
1767 The branch should be predicted taken. */
1768 if (loop_bound_step > 0
1769 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1770 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1771 else if (loop_bound_step < 0
1772 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1773 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1774 else
1775 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1779 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1780 exits are resulted from short-circuit conditions that will generate an
1781 if_tmp. E.g.:
1783 if (foo() || global > 10)
1784 break;
1786 This will be translated into:
1788 BB3:
1789 loop header...
1790 BB4:
1791 if foo() goto BB6 else goto BB5
1792 BB5:
1793 if global > 10 goto BB6 else goto BB7
1794 BB6:
1795 goto BB7
1796 BB7:
1797 iftmp = (PHI 0(BB5), 1(BB6))
1798 if iftmp == 1 goto BB8 else goto BB3
1799 BB8:
1800 outside of the loop...
1802 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1803 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1804 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1805 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1807 static void
1808 predict_extra_loop_exits (edge exit_edge)
1810 unsigned i;
1811 bool check_value_one;
1812 gimple *lhs_def_stmt;
1813 gphi *phi_stmt;
1814 tree cmp_rhs, cmp_lhs;
1815 gimple *last;
1816 gcond *cmp_stmt;
1818 last = last_stmt (exit_edge->src);
1819 if (!last)
1820 return;
1821 cmp_stmt = dyn_cast <gcond *> (last);
1822 if (!cmp_stmt)
1823 return;
1825 cmp_rhs = gimple_cond_rhs (cmp_stmt);
1826 cmp_lhs = gimple_cond_lhs (cmp_stmt);
1827 if (!TREE_CONSTANT (cmp_rhs)
1828 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1829 return;
1830 if (TREE_CODE (cmp_lhs) != SSA_NAME)
1831 return;
1833 /* If check_value_one is true, only the phi_args with value '1' will lead
1834 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1835 loop exit. */
1836 check_value_one = (((integer_onep (cmp_rhs))
1837 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1838 ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1840 lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1841 if (!lhs_def_stmt)
1842 return;
1844 phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1845 if (!phi_stmt)
1846 return;
1848 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1850 edge e1;
1851 edge_iterator ei;
1852 tree val = gimple_phi_arg_def (phi_stmt, i);
1853 edge e = gimple_phi_arg_edge (phi_stmt, i);
1855 if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1856 continue;
1857 if ((check_value_one ^ integer_onep (val)) == 1)
1858 continue;
1859 if (EDGE_COUNT (e->src->succs) != 1)
1861 predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1862 continue;
1865 FOR_EACH_EDGE (e1, ei, e->src->preds)
1866 predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1871 /* Predict edge probabilities by exploiting loop structure. */
1873 static void
1874 predict_loops (void)
1876 struct loop *loop;
1877 basic_block bb;
1878 hash_set <struct loop *> with_recursion(10);
1880 FOR_EACH_BB_FN (bb, cfun)
1882 gimple_stmt_iterator gsi;
1883 tree decl;
1885 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1886 if (is_gimple_call (gsi_stmt (gsi))
1887 && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1888 && recursive_call_p (current_function_decl, decl))
1890 loop = bb->loop_father;
1891 while (loop && !with_recursion.add (loop))
1892 loop = loop_outer (loop);
1896 /* Try to predict out blocks in a loop that are not part of a
1897 natural loop. */
1898 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1900 basic_block bb, *bbs;
1901 unsigned j, n_exits = 0;
1902 vec<edge> exits;
1903 struct tree_niter_desc niter_desc;
1904 edge ex;
1905 struct nb_iter_bound *nb_iter;
1906 enum tree_code loop_bound_code = ERROR_MARK;
1907 tree loop_bound_step = NULL;
1908 tree loop_bound_var = NULL;
1909 tree loop_iv_base = NULL;
1910 gcond *stmt = NULL;
1911 bool recursion = with_recursion.contains (loop);
1913 exits = get_loop_exit_edges (loop);
1914 FOR_EACH_VEC_ELT (exits, j, ex)
1915 if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
1916 n_exits ++;
1917 if (!n_exits)
1919 exits.release ();
1920 continue;
1923 if (dump_file && (dump_flags & TDF_DETAILS))
1924 fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
1925 loop->num, recursion ? " (with recursion)":"", n_exits);
1926 if (dump_file && (dump_flags & TDF_DETAILS)
1927 && max_loop_iterations_int (loop) >= 0)
1929 fprintf (dump_file,
1930 "Loop %d iterates at most %i times.\n", loop->num,
1931 (int)max_loop_iterations_int (loop));
1933 if (dump_file && (dump_flags & TDF_DETAILS)
1934 && likely_max_loop_iterations_int (loop) >= 0)
1936 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1937 loop->num, (int)likely_max_loop_iterations_int (loop));
1940 FOR_EACH_VEC_ELT (exits, j, ex)
1942 tree niter = NULL;
1943 HOST_WIDE_INT nitercst;
1944 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
1945 int probability;
1946 enum br_predictor predictor;
1947 widest_int nit;
1949 if (unlikely_executed_edge_p (ex)
1950 || (ex->flags & EDGE_ABNORMAL_CALL))
1951 continue;
1952 /* Loop heuristics do not expect exit conditional to be inside
1953 inner loop. We predict from innermost to outermost loop. */
1954 if (predicted_by_loop_heuristics_p (ex->src))
1956 if (dump_file && (dump_flags & TDF_DETAILS))
1957 fprintf (dump_file, "Skipping exit %i->%i because "
1958 "it is already predicted.\n",
1959 ex->src->index, ex->dest->index);
1960 continue;
1962 predict_extra_loop_exits (ex);
1964 if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
1965 niter = niter_desc.niter;
1966 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
1967 niter = loop_niter_by_eval (loop, ex);
1968 if (dump_file && (dump_flags & TDF_DETAILS)
1969 && TREE_CODE (niter) == INTEGER_CST)
1971 fprintf (dump_file, "Exit %i->%i %d iterates ",
1972 ex->src->index, ex->dest->index,
1973 loop->num);
1974 print_generic_expr (dump_file, niter, TDF_SLIM);
1975 fprintf (dump_file, " times.\n");
1978 if (TREE_CODE (niter) == INTEGER_CST)
1980 if (tree_fits_uhwi_p (niter)
1981 && max
1982 && compare_tree_int (niter, max - 1) == -1)
1983 nitercst = tree_to_uhwi (niter) + 1;
1984 else
1985 nitercst = max;
1986 predictor = PRED_LOOP_ITERATIONS;
1988 /* If we have just one exit and we can derive some information about
1989 the number of iterations of the loop from the statements inside
1990 the loop, use it to predict this exit. */
1991 else if (n_exits == 1
1992 && estimated_stmt_executions (loop, &nit))
1994 if (wi::gtu_p (nit, max))
1995 nitercst = max;
1996 else
1997 nitercst = nit.to_shwi ();
1998 predictor = PRED_LOOP_ITERATIONS_GUESSED;
2000 /* If we have likely upper bound, trust it for very small iteration
2001 counts. Such loops would otherwise get mispredicted by standard
2002 LOOP_EXIT heuristics. */
2003 else if (n_exits == 1
2004 && likely_max_stmt_executions (loop, &nit)
2005 && wi::ltu_p (nit,
2006 RDIV (REG_BR_PROB_BASE,
2007 REG_BR_PROB_BASE
2008 - predictor_info
2009 [recursion
2010 ? PRED_LOOP_EXIT_WITH_RECURSION
2011 : PRED_LOOP_EXIT].hitrate)))
2013 nitercst = nit.to_shwi ();
2014 predictor = PRED_LOOP_ITERATIONS_MAX;
2016 else
2018 if (dump_file && (dump_flags & TDF_DETAILS))
2019 fprintf (dump_file, "Nothing known about exit %i->%i.\n",
2020 ex->src->index, ex->dest->index);
2021 continue;
2024 if (dump_file && (dump_flags & TDF_DETAILS))
2025 fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
2026 (int)nitercst, predictor_info[predictor].name);
2027 /* If the prediction for number of iterations is zero, do not
2028 predict the exit edges. */
2029 if (nitercst == 0)
2030 continue;
2032 probability = RDIV (REG_BR_PROB_BASE, nitercst);
2033 predict_edge (ex, predictor, probability);
2035 exits.release ();
2037 /* Find information about loop bound variables. */
2038 for (nb_iter = loop->bounds; nb_iter;
2039 nb_iter = nb_iter->next)
2040 if (nb_iter->stmt
2041 && gimple_code (nb_iter->stmt) == GIMPLE_COND)
2043 stmt = as_a <gcond *> (nb_iter->stmt);
2044 break;
2046 if (!stmt && last_stmt (loop->header)
2047 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
2048 stmt = as_a <gcond *> (last_stmt (loop->header));
2049 if (stmt)
2050 is_comparison_with_loop_invariant_p (stmt, loop,
2051 &loop_bound_var,
2052 &loop_bound_code,
2053 &loop_bound_step,
2054 &loop_iv_base);
2056 bbs = get_loop_body (loop);
2058 for (j = 0; j < loop->num_nodes; j++)
2060 edge e;
2061 edge_iterator ei;
2063 bb = bbs[j];
2065 /* Bypass loop heuristics on continue statement. These
2066 statements construct loops via "non-loop" constructs
2067 in the source language and are better to be handled
2068 separately. */
2069 if (predicted_by_p (bb, PRED_CONTINUE))
2071 if (dump_file && (dump_flags & TDF_DETAILS))
2072 fprintf (dump_file, "BB %i predicted by continue.\n",
2073 bb->index);
2074 continue;
2077 /* If we already used more reliable loop exit predictors, do not
2078 bother with PRED_LOOP_EXIT. */
2079 if (!predicted_by_loop_heuristics_p (bb))
2081 /* For loop with many exits we don't want to predict all exits
2082 with the pretty large probability, because if all exits are
2083 considered in row, the loop would be predicted to iterate
2084 almost never. The code to divide probability by number of
2085 exits is very rough. It should compute the number of exits
2086 taken in each patch through function (not the overall number
2087 of exits that might be a lot higher for loops with wide switch
2088 statements in them) and compute n-th square root.
2090 We limit the minimal probability by 2% to avoid
2091 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2092 as this was causing regression in perl benchmark containing such
2093 a wide loop. */
2095 int probability = ((REG_BR_PROB_BASE
2096 - predictor_info
2097 [recursion
2098 ? PRED_LOOP_EXIT_WITH_RECURSION
2099 : PRED_LOOP_EXIT].hitrate)
2100 / n_exits);
2101 if (probability < HITRATE (2))
2102 probability = HITRATE (2);
2103 FOR_EACH_EDGE (e, ei, bb->succs)
2104 if (e->dest->index < NUM_FIXED_BLOCKS
2105 || !flow_bb_inside_loop_p (loop, e->dest))
2107 if (dump_file && (dump_flags & TDF_DETAILS))
2108 fprintf (dump_file,
2109 "Predicting exit %i->%i with prob %i.\n",
2110 e->src->index, e->dest->index, probability);
2111 predict_edge (e,
2112 recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2113 : PRED_LOOP_EXIT, probability);
2116 if (loop_bound_var)
2117 predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2118 loop_bound_code,
2119 tree_to_shwi (loop_bound_step));
2122 /* In the following code
2123 for (loop1)
2124 if (cond)
2125 for (loop2)
2126 body;
2127 guess that cond is unlikely. */
2128 if (loop_outer (loop)->num)
2130 basic_block bb = NULL;
2131 edge preheader_edge = loop_preheader_edge (loop);
2133 if (single_pred_p (preheader_edge->src)
2134 && single_succ_p (preheader_edge->src))
2135 preheader_edge = single_pred_edge (preheader_edge->src);
2137 gimple *stmt = last_stmt (preheader_edge->src);
2138 /* Pattern match fortran loop preheader:
2139 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2140 _17 = (logical(kind=4)) _16;
2141 if (_17 != 0)
2142 goto <bb 11>;
2143 else
2144 goto <bb 13>;
2146 Loop guard branch prediction says nothing about duplicated loop
2147 headers produced by fortran frontend and in this case we want
2148 to predict paths leading to this preheader. */
2150 if (stmt
2151 && gimple_code (stmt) == GIMPLE_COND
2152 && gimple_cond_code (stmt) == NE_EXPR
2153 && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2154 && integer_zerop (gimple_cond_rhs (stmt)))
2156 gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2157 if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2158 && gimple_expr_code (call_stmt) == NOP_EXPR
2159 && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2160 call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2161 if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
2162 && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2163 && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
2164 && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
2165 == PRED_FORTRAN_LOOP_PREHEADER)
2166 bb = preheader_edge->src;
2168 if (!bb)
2170 if (!dominated_by_p (CDI_DOMINATORS,
2171 loop_outer (loop)->latch, loop->header))
2172 predict_paths_leading_to_edge (loop_preheader_edge (loop),
2173 recursion
2174 ? PRED_LOOP_GUARD_WITH_RECURSION
2175 : PRED_LOOP_GUARD,
2176 NOT_TAKEN,
2177 loop_outer (loop));
2179 else
2181 if (!dominated_by_p (CDI_DOMINATORS,
2182 loop_outer (loop)->latch, bb))
2183 predict_paths_leading_to (bb,
2184 recursion
2185 ? PRED_LOOP_GUARD_WITH_RECURSION
2186 : PRED_LOOP_GUARD,
2187 NOT_TAKEN,
2188 loop_outer (loop));
2192 /* Free basic blocks from get_loop_body. */
2193 free (bbs);
2197 /* Attempt to predict probabilities of BB outgoing edges using local
2198 properties. */
2199 static void
2200 bb_estimate_probability_locally (basic_block bb)
2202 rtx_insn *last_insn = BB_END (bb);
2203 rtx cond;
2205 if (! can_predict_insn_p (last_insn))
2206 return;
2207 cond = get_condition (last_insn, NULL, false, false);
2208 if (! cond)
2209 return;
2211 /* Try "pointer heuristic."
2212 A comparison ptr == 0 is predicted as false.
2213 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2214 if (COMPARISON_P (cond)
2215 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2216 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2218 if (GET_CODE (cond) == EQ)
2219 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2220 else if (GET_CODE (cond) == NE)
2221 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2223 else
2225 /* Try "opcode heuristic."
2226 EQ tests are usually false and NE tests are usually true. Also,
2227 most quantities are positive, so we can make the appropriate guesses
2228 about signed comparisons against zero. */
2229 switch (GET_CODE (cond))
2231 case CONST_INT:
2232 /* Unconditional branch. */
2233 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2234 cond == const0_rtx ? NOT_TAKEN : TAKEN);
2235 break;
2237 case EQ:
2238 case UNEQ:
2239 /* Floating point comparisons appears to behave in a very
2240 unpredictable way because of special role of = tests in
2241 FP code. */
2242 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2244 /* Comparisons with 0 are often used for booleans and there is
2245 nothing useful to predict about them. */
2246 else if (XEXP (cond, 1) == const0_rtx
2247 || XEXP (cond, 0) == const0_rtx)
2249 else
2250 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2251 break;
2253 case NE:
2254 case LTGT:
2255 /* Floating point comparisons appears to behave in a very
2256 unpredictable way because of special role of = tests in
2257 FP code. */
2258 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2260 /* Comparisons with 0 are often used for booleans and there is
2261 nothing useful to predict about them. */
2262 else if (XEXP (cond, 1) == const0_rtx
2263 || XEXP (cond, 0) == const0_rtx)
2265 else
2266 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2267 break;
2269 case ORDERED:
2270 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2271 break;
2273 case UNORDERED:
2274 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2275 break;
2277 case LE:
2278 case LT:
2279 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2280 || XEXP (cond, 1) == constm1_rtx)
2281 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2282 break;
2284 case GE:
2285 case GT:
2286 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2287 || XEXP (cond, 1) == constm1_rtx)
2288 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2289 break;
2291 default:
2292 break;
2296 /* Set edge->probability for each successor edge of BB. */
2297 void
2298 guess_outgoing_edge_probabilities (basic_block bb)
2300 bb_estimate_probability_locally (bb);
2301 combine_predictions_for_insn (BB_END (bb), bb);
2304 static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
2305 HOST_WIDE_INT *probability);
2307 /* Helper function for expr_expected_value. */
2309 static tree
2310 expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2311 tree op1, bitmap visited, enum br_predictor *predictor,
2312 HOST_WIDE_INT *probability)
2314 gimple *def;
2316 /* Reset returned probability value. */
2317 *probability = -1;
2318 *predictor = PRED_UNCONDITIONAL;
2320 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2322 if (TREE_CONSTANT (op0))
2323 return op0;
2325 if (code == IMAGPART_EXPR)
2327 if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2329 def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2330 if (is_gimple_call (def)
2331 && gimple_call_internal_p (def)
2332 && (gimple_call_internal_fn (def)
2333 == IFN_ATOMIC_COMPARE_EXCHANGE))
2335 /* Assume that any given atomic operation has low contention,
2336 and thus the compare-and-swap operation succeeds. */
2337 *predictor = PRED_COMPARE_AND_SWAP;
2338 return build_one_cst (TREE_TYPE (op0));
2343 if (code != SSA_NAME)
2344 return NULL_TREE;
2346 def = SSA_NAME_DEF_STMT (op0);
2348 /* If we were already here, break the infinite cycle. */
2349 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
2350 return NULL;
2352 if (gimple_code (def) == GIMPLE_PHI)
2354 /* All the arguments of the PHI node must have the same constant
2355 length. */
2356 int i, n = gimple_phi_num_args (def);
2357 tree val = NULL, new_val;
2359 for (i = 0; i < n; i++)
2361 tree arg = PHI_ARG_DEF (def, i);
2362 enum br_predictor predictor2;
2364 /* If this PHI has itself as an argument, we cannot
2365 determine the string length of this argument. However,
2366 if we can find an expected constant value for the other
2367 PHI args then we can still be sure that this is
2368 likely a constant. So be optimistic and just
2369 continue with the next argument. */
2370 if (arg == PHI_RESULT (def))
2371 continue;
2373 HOST_WIDE_INT probability2;
2374 new_val = expr_expected_value (arg, visited, &predictor2,
2375 &probability2);
2377 /* It is difficult to combine value predictors. Simply assume
2378 that later predictor is weaker and take its prediction. */
2379 if (*predictor < predictor2)
2381 *predictor = predictor2;
2382 *probability = probability2;
2384 if (!new_val)
2385 return NULL;
2386 if (!val)
2387 val = new_val;
2388 else if (!operand_equal_p (val, new_val, false))
2389 return NULL;
2391 return val;
2393 if (is_gimple_assign (def))
2395 if (gimple_assign_lhs (def) != op0)
2396 return NULL;
2398 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2399 gimple_assign_rhs1 (def),
2400 gimple_assign_rhs_code (def),
2401 gimple_assign_rhs2 (def),
2402 visited, predictor, probability);
2405 if (is_gimple_call (def))
2407 tree decl = gimple_call_fndecl (def);
2408 if (!decl)
2410 if (gimple_call_internal_p (def)
2411 && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2413 gcc_assert (gimple_call_num_args (def) == 3);
2414 tree val = gimple_call_arg (def, 0);
2415 if (TREE_CONSTANT (val))
2416 return val;
2417 tree val2 = gimple_call_arg (def, 2);
2418 gcc_assert (TREE_CODE (val2) == INTEGER_CST
2419 && tree_fits_uhwi_p (val2)
2420 && tree_to_uhwi (val2) < END_PREDICTORS);
2421 *predictor = (enum br_predictor) tree_to_uhwi (val2);
2422 if (*predictor == PRED_BUILTIN_EXPECT)
2423 *probability
2424 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY));
2425 return gimple_call_arg (def, 1);
2427 return NULL;
2430 if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW (decl))
2432 if (predictor)
2433 *predictor = PRED_MALLOC_NONNULL;
2434 return boolean_true_node;
2437 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2438 switch (DECL_FUNCTION_CODE (decl))
2440 case BUILT_IN_EXPECT:
2442 tree val;
2443 if (gimple_call_num_args (def) != 2)
2444 return NULL;
2445 val = gimple_call_arg (def, 0);
2446 if (TREE_CONSTANT (val))
2447 return val;
2448 *predictor = PRED_BUILTIN_EXPECT;
2449 *probability
2450 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY));
2451 return gimple_call_arg (def, 1);
2453 case BUILT_IN_EXPECT_WITH_PROBABILITY:
2455 tree val;
2456 if (gimple_call_num_args (def) != 3)
2457 return NULL;
2458 val = gimple_call_arg (def, 0);
2459 if (TREE_CONSTANT (val))
2460 return val;
2461 /* Compute final probability as:
2462 probability * REG_BR_PROB_BASE. */
2463 tree prob = gimple_call_arg (def, 2);
2464 tree t = TREE_TYPE (prob);
2465 tree base = build_int_cst (integer_type_node,
2466 REG_BR_PROB_BASE);
2467 base = build_real_from_int_cst (t, base);
2468 tree r = fold_build2_initializer_loc (UNKNOWN_LOCATION,
2469 MULT_EXPR, t, prob, base);
2470 if (TREE_CODE (r) != REAL_CST)
2472 error_at (gimple_location (def),
2473 "probability %qE must be "
2474 "constant floating-point expression", prob);
2475 return NULL;
2477 HOST_WIDE_INT probi
2478 = real_to_integer (TREE_REAL_CST_PTR (r));
2479 if (probi >= 0 && probi <= REG_BR_PROB_BASE)
2481 *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
2482 *probability = probi;
2484 else
2485 error_at (gimple_location (def),
2486 "probability %qE is outside "
2487 "the range [0.0, 1.0]", prob);
2489 return gimple_call_arg (def, 1);
2492 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2493 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2494 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2495 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2496 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2497 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2498 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2499 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2500 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2501 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2502 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2503 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2504 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2505 /* Assume that any given atomic operation has low contention,
2506 and thus the compare-and-swap operation succeeds. */
2507 *predictor = PRED_COMPARE_AND_SWAP;
2508 return boolean_true_node;
2509 case BUILT_IN_REALLOC:
2510 if (predictor)
2511 *predictor = PRED_MALLOC_NONNULL;
2512 return boolean_true_node;
2513 default:
2514 break;
2518 return NULL;
2521 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2523 tree res;
2524 enum br_predictor predictor2;
2525 HOST_WIDE_INT probability2;
2526 op0 = expr_expected_value (op0, visited, predictor, probability);
2527 if (!op0)
2528 return NULL;
2529 op1 = expr_expected_value (op1, visited, &predictor2, &probability2);
2530 if (!op1)
2531 return NULL;
2532 res = fold_build2 (code, type, op0, op1);
2533 if (TREE_CODE (res) == INTEGER_CST
2534 && TREE_CODE (op0) == INTEGER_CST
2535 && TREE_CODE (op1) == INTEGER_CST)
2537 /* Combine binary predictions. */
2538 if (*probability != -1 || probability2 != -1)
2540 HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
2541 HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
2542 *probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
2545 if (*predictor < predictor2)
2546 *predictor = predictor2;
2548 return res;
2550 return NULL;
2552 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2554 tree res;
2555 op0 = expr_expected_value (op0, visited, predictor, probability);
2556 if (!op0)
2557 return NULL;
2558 res = fold_build1 (code, type, op0);
2559 if (TREE_CONSTANT (res))
2560 return res;
2561 return NULL;
2563 return NULL;
2566 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2567 The function is used by builtin_expect branch predictor so the evidence
2568 must come from this construct and additional possible constant folding.
2570 We may want to implement more involved value guess (such as value range
2571 propagation based prediction), but such tricks shall go to new
2572 implementation. */
2574 static tree
2575 expr_expected_value (tree expr, bitmap visited,
2576 enum br_predictor *predictor,
2577 HOST_WIDE_INT *probability)
2579 enum tree_code code;
2580 tree op0, op1;
2582 if (TREE_CONSTANT (expr))
2584 *predictor = PRED_UNCONDITIONAL;
2585 *probability = -1;
2586 return expr;
2589 extract_ops_from_tree (expr, &code, &op0, &op1);
2590 return expr_expected_value_1 (TREE_TYPE (expr),
2591 op0, code, op1, visited, predictor,
2592 probability);
2596 /* Return probability of a PREDICTOR. If the predictor has variable
2597 probability return passed PROBABILITY. */
2599 static HOST_WIDE_INT
2600 get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2602 switch (predictor)
2604 case PRED_BUILTIN_EXPECT:
2605 case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2606 gcc_assert (probability != -1);
2607 return probability;
2608 default:
2609 gcc_assert (probability == -1);
2610 return predictor_info[(int) predictor].hitrate;
2614 /* Predict using opcode of the last statement in basic block. */
2615 static void
2616 tree_predict_by_opcode (basic_block bb)
2618 gimple *stmt = last_stmt (bb);
2619 edge then_edge;
2620 tree op0, op1;
2621 tree type;
2622 tree val;
2623 enum tree_code cmp;
2624 edge_iterator ei;
2625 enum br_predictor predictor;
2626 HOST_WIDE_INT probability;
2628 if (!stmt)
2629 return;
2631 if (gswitch *sw = dyn_cast <gswitch *> (stmt))
2633 tree index = gimple_switch_index (sw);
2634 tree val = expr_expected_value (index, auto_bitmap (),
2635 &predictor, &probability);
2636 if (val && TREE_CODE (val) == INTEGER_CST)
2638 edge e = find_taken_edge_switch_expr (sw, val);
2639 if (predictor == PRED_BUILTIN_EXPECT)
2641 int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
2642 gcc_assert (percent >= 0 && percent <= 100);
2643 predict_edge (e, PRED_BUILTIN_EXPECT,
2644 HITRATE (percent));
2646 else
2647 predict_edge_def (e, predictor, TAKEN);
2651 if (gimple_code (stmt) != GIMPLE_COND)
2652 return;
2653 FOR_EACH_EDGE (then_edge, ei, bb->succs)
2654 if (then_edge->flags & EDGE_TRUE_VALUE)
2655 break;
2656 op0 = gimple_cond_lhs (stmt);
2657 op1 = gimple_cond_rhs (stmt);
2658 cmp = gimple_cond_code (stmt);
2659 type = TREE_TYPE (op0);
2660 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
2661 &predictor, &probability);
2662 if (val && TREE_CODE (val) == INTEGER_CST)
2664 HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2665 if (integer_zerop (val))
2666 prob = REG_BR_PROB_BASE - prob;
2667 predict_edge (then_edge, predictor, prob);
2669 /* Try "pointer heuristic."
2670 A comparison ptr == 0 is predicted as false.
2671 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2672 if (POINTER_TYPE_P (type))
2674 if (cmp == EQ_EXPR)
2675 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2676 else if (cmp == NE_EXPR)
2677 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2679 else
2681 /* Try "opcode heuristic."
2682 EQ tests are usually false and NE tests are usually true. Also,
2683 most quantities are positive, so we can make the appropriate guesses
2684 about signed comparisons against zero. */
2685 switch (cmp)
2687 case EQ_EXPR:
2688 case UNEQ_EXPR:
2689 /* Floating point comparisons appears to behave in a very
2690 unpredictable way because of special role of = tests in
2691 FP code. */
2692 if (FLOAT_TYPE_P (type))
2694 /* Comparisons with 0 are often used for booleans and there is
2695 nothing useful to predict about them. */
2696 else if (integer_zerop (op0) || integer_zerop (op1))
2698 else
2699 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2700 break;
2702 case NE_EXPR:
2703 case LTGT_EXPR:
2704 /* Floating point comparisons appears to behave in a very
2705 unpredictable way because of special role of = tests in
2706 FP code. */
2707 if (FLOAT_TYPE_P (type))
2709 /* Comparisons with 0 are often used for booleans and there is
2710 nothing useful to predict about them. */
2711 else if (integer_zerop (op0)
2712 || integer_zerop (op1))
2714 else
2715 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2716 break;
2718 case ORDERED_EXPR:
2719 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2720 break;
2722 case UNORDERED_EXPR:
2723 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2724 break;
2726 case LE_EXPR:
2727 case LT_EXPR:
2728 if (integer_zerop (op1)
2729 || integer_onep (op1)
2730 || integer_all_onesp (op1)
2731 || real_zerop (op1)
2732 || real_onep (op1)
2733 || real_minus_onep (op1))
2734 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2735 break;
2737 case GE_EXPR:
2738 case GT_EXPR:
2739 if (integer_zerop (op1)
2740 || integer_onep (op1)
2741 || integer_all_onesp (op1)
2742 || real_zerop (op1)
2743 || real_onep (op1)
2744 || real_minus_onep (op1))
2745 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2746 break;
2748 default:
2749 break;
2753 /* Returns TRUE if the STMT is exit(0) like statement. */
2755 static bool
2756 is_exit_with_zero_arg (const gimple *stmt)
2758 /* This is not exit, _exit or _Exit. */
2759 if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2760 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2761 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2762 return false;
2764 /* Argument is an interger zero. */
2765 return integer_zerop (gimple_call_arg (stmt, 0));
2768 /* Try to guess whether the value of return means error code. */
2770 static enum br_predictor
2771 return_prediction (tree val, enum prediction *prediction)
2773 /* VOID. */
2774 if (!val)
2775 return PRED_NO_PREDICTION;
2776 /* Different heuristics for pointers and scalars. */
2777 if (POINTER_TYPE_P (TREE_TYPE (val)))
2779 /* NULL is usually not returned. */
2780 if (integer_zerop (val))
2782 *prediction = NOT_TAKEN;
2783 return PRED_NULL_RETURN;
2786 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2788 /* Negative return values are often used to indicate
2789 errors. */
2790 if (TREE_CODE (val) == INTEGER_CST
2791 && tree_int_cst_sgn (val) < 0)
2793 *prediction = NOT_TAKEN;
2794 return PRED_NEGATIVE_RETURN;
2796 /* Constant return values seems to be commonly taken.
2797 Zero/one often represent booleans so exclude them from the
2798 heuristics. */
2799 if (TREE_CONSTANT (val)
2800 && (!integer_zerop (val) && !integer_onep (val)))
2802 *prediction = NOT_TAKEN;
2803 return PRED_CONST_RETURN;
2806 return PRED_NO_PREDICTION;
2809 /* Return zero if phi result could have values other than -1, 0 or 1,
2810 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2811 values are used or likely. */
2813 static int
2814 zero_one_minusone (gphi *phi, int limit)
2816 int phi_num_args = gimple_phi_num_args (phi);
2817 int ret = 0;
2818 for (int i = 0; i < phi_num_args; i++)
2820 tree t = PHI_ARG_DEF (phi, i);
2821 if (TREE_CODE (t) != INTEGER_CST)
2822 continue;
2823 wide_int w = wi::to_wide (t);
2824 if (w == -1)
2825 ret |= 1;
2826 else if (w == 0)
2827 ret |= 2;
2828 else if (w == 1)
2829 ret |= 4;
2830 else
2831 return 0;
2833 for (int i = 0; i < phi_num_args; i++)
2835 tree t = PHI_ARG_DEF (phi, i);
2836 if (TREE_CODE (t) == INTEGER_CST)
2837 continue;
2838 if (TREE_CODE (t) != SSA_NAME)
2839 return 0;
2840 gimple *g = SSA_NAME_DEF_STMT (t);
2841 if (gimple_code (g) == GIMPLE_PHI && limit > 0)
2842 if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
2844 ret |= r;
2845 continue;
2847 if (!is_gimple_assign (g))
2848 return 0;
2849 if (gimple_assign_cast_p (g))
2851 tree rhs1 = gimple_assign_rhs1 (g);
2852 if (TREE_CODE (rhs1) != SSA_NAME
2853 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2854 || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2855 || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2856 return 0;
2857 ret |= (2 | 4);
2858 continue;
2860 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
2861 return 0;
2862 ret |= (2 | 4);
2864 return ret;
2867 /* Find the basic block with return expression and look up for possible
2868 return value trying to apply RETURN_PREDICTION heuristics. */
2869 static void
2870 apply_return_prediction (void)
2872 greturn *return_stmt = NULL;
2873 tree return_val;
2874 edge e;
2875 gphi *phi;
2876 int phi_num_args, i;
2877 enum br_predictor pred;
2878 enum prediction direction;
2879 edge_iterator ei;
2881 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2883 gimple *last = last_stmt (e->src);
2884 if (last
2885 && gimple_code (last) == GIMPLE_RETURN)
2887 return_stmt = as_a <greturn *> (last);
2888 break;
2891 if (!e)
2892 return;
2893 return_val = gimple_return_retval (return_stmt);
2894 if (!return_val)
2895 return;
2896 if (TREE_CODE (return_val) != SSA_NAME
2897 || !SSA_NAME_DEF_STMT (return_val)
2898 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2899 return;
2900 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2901 phi_num_args = gimple_phi_num_args (phi);
2902 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
2904 /* Avoid the case where the function returns -1, 0 and 1 values and
2905 nothing else. Those could be qsort etc. comparison functions
2906 where the negative return isn't less probable than positive.
2907 For this require that the function returns at least -1 or 1
2908 or -1 and a boolean value or comparison result, so that functions
2909 returning just -1 and 0 are treated as if -1 represents error value. */
2910 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
2911 && !TYPE_UNSIGNED (TREE_TYPE (return_val))
2912 && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
2913 if (int r = zero_one_minusone (phi, 3))
2914 if ((r & (1 | 4)) == (1 | 4))
2915 return;
2917 /* Avoid the degenerate case where all return values form the function
2918 belongs to same category (ie they are all positive constants)
2919 so we can hardly say something about them. */
2920 for (i = 1; i < phi_num_args; i++)
2921 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
2922 break;
2923 if (i != phi_num_args)
2924 for (i = 0; i < phi_num_args; i++)
2926 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
2927 if (pred != PRED_NO_PREDICTION)
2928 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
2929 direction);
2933 /* Look for basic block that contains unlikely to happen events
2934 (such as noreturn calls) and mark all paths leading to execution
2935 of this basic blocks as unlikely. */
2937 static void
2938 tree_bb_level_predictions (void)
2940 basic_block bb;
2941 bool has_return_edges = false;
2942 edge e;
2943 edge_iterator ei;
2945 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2946 if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
2948 has_return_edges = true;
2949 break;
2952 apply_return_prediction ();
2954 FOR_EACH_BB_FN (bb, cfun)
2956 gimple_stmt_iterator gsi;
2958 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2960 gimple *stmt = gsi_stmt (gsi);
2961 tree decl;
2963 if (is_gimple_call (stmt))
2965 if (gimple_call_noreturn_p (stmt)
2966 && has_return_edges
2967 && !is_exit_with_zero_arg (stmt))
2968 predict_paths_leading_to (bb, PRED_NORETURN,
2969 NOT_TAKEN);
2970 decl = gimple_call_fndecl (stmt);
2971 if (decl
2972 && lookup_attribute ("cold",
2973 DECL_ATTRIBUTES (decl)))
2974 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
2975 NOT_TAKEN);
2976 if (decl && recursive_call_p (current_function_decl, decl))
2977 predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
2978 NOT_TAKEN);
2980 else if (gimple_code (stmt) == GIMPLE_PREDICT)
2982 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
2983 gimple_predict_outcome (stmt));
2984 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2985 hints to callers. */
2991 /* Callback for hash_map::traverse, asserts that the pointer map is
2992 empty. */
2994 bool
2995 assert_is_empty (const_basic_block const &, edge_prediction *const &value,
2996 void *)
2998 gcc_assert (!value);
2999 return false;
3002 /* Predict branch probabilities and estimate profile for basic block BB.
3003 When LOCAL_ONLY is set do not use any global properties of CFG. */
3005 static void
3006 tree_estimate_probability_bb (basic_block bb, bool local_only)
3008 edge e;
3009 edge_iterator ei;
3011 FOR_EACH_EDGE (e, ei, bb->succs)
3013 /* Look for block we are guarding (ie we dominate it,
3014 but it doesn't postdominate us). */
3015 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
3016 && !local_only
3017 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
3018 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
3020 gimple_stmt_iterator bi;
3022 /* The call heuristic claims that a guarded function call
3023 is improbable. This is because such calls are often used
3024 to signal exceptional situations such as printing error
3025 messages. */
3026 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
3027 gsi_next (&bi))
3029 gimple *stmt = gsi_stmt (bi);
3030 if (is_gimple_call (stmt)
3031 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
3032 /* Constant and pure calls are hardly used to signalize
3033 something exceptional. */
3034 && gimple_has_side_effects (stmt))
3036 if (gimple_call_fndecl (stmt))
3037 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
3038 else if (virtual_method_call_p (gimple_call_fn (stmt)))
3039 predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
3040 else
3041 predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
3042 break;
3047 tree_predict_by_opcode (bb);
3050 /* Predict branch probabilities and estimate profile of the tree CFG.
3051 This function can be called from the loop optimizers to recompute
3052 the profile information.
3053 If DRY_RUN is set, do not modify CFG and only produce dump files. */
3055 void
3056 tree_estimate_probability (bool dry_run)
3058 basic_block bb;
3060 add_noreturn_fake_exit_edges ();
3061 connect_infinite_loops_to_exit ();
3062 /* We use loop_niter_by_eval, which requires that the loops have
3063 preheaders. */
3064 create_preheaders (CP_SIMPLE_PREHEADERS);
3065 calculate_dominance_info (CDI_POST_DOMINATORS);
3067 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3068 tree_bb_level_predictions ();
3069 record_loop_exits ();
3071 if (number_of_loops (cfun) > 1)
3072 predict_loops ();
3074 FOR_EACH_BB_FN (bb, cfun)
3075 tree_estimate_probability_bb (bb, false);
3077 FOR_EACH_BB_FN (bb, cfun)
3078 combine_predictions_for_bb (bb, dry_run);
3080 if (flag_checking)
3081 bb_predictions->traverse<void *, assert_is_empty> (NULL);
3083 delete bb_predictions;
3084 bb_predictions = NULL;
3086 if (!dry_run)
3087 estimate_bb_frequencies (false);
3088 free_dominance_info (CDI_POST_DOMINATORS);
3089 remove_fake_exit_edges ();
3092 /* Set edge->probability for each successor edge of BB. */
3093 void
3094 tree_guess_outgoing_edge_probabilities (basic_block bb)
3096 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3097 tree_estimate_probability_bb (bb, true);
3098 combine_predictions_for_bb (bb, false);
3099 if (flag_checking)
3100 bb_predictions->traverse<void *, assert_is_empty> (NULL);
3101 delete bb_predictions;
3102 bb_predictions = NULL;
3105 /* Predict edges to successors of CUR whose sources are not postdominated by
3106 BB by PRED and recurse to all postdominators. */
3108 static void
3109 predict_paths_for_bb (basic_block cur, basic_block bb,
3110 enum br_predictor pred,
3111 enum prediction taken,
3112 bitmap visited, struct loop *in_loop = NULL)
3114 edge e;
3115 edge_iterator ei;
3116 basic_block son;
3118 /* If we exited the loop or CUR is unconditional in the loop, there is
3119 nothing to do. */
3120 if (in_loop
3121 && (!flow_bb_inside_loop_p (in_loop, cur)
3122 || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3123 return;
3125 /* We are looking for all edges forming edge cut induced by
3126 set of all blocks postdominated by BB. */
3127 FOR_EACH_EDGE (e, ei, cur->preds)
3128 if (e->src->index >= NUM_FIXED_BLOCKS
3129 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3131 edge e2;
3132 edge_iterator ei2;
3133 bool found = false;
3135 /* Ignore fake edges and eh, we predict them as not taken anyway. */
3136 if (unlikely_executed_edge_p (e))
3137 continue;
3138 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
3140 /* See if there is an edge from e->src that is not abnormal
3141 and does not lead to BB and does not exit the loop. */
3142 FOR_EACH_EDGE (e2, ei2, e->src->succs)
3143 if (e2 != e
3144 && !unlikely_executed_edge_p (e2)
3145 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3146 && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
3148 found = true;
3149 break;
3152 /* If there is non-abnormal path leaving e->src, predict edge
3153 using predictor. Otherwise we need to look for paths
3154 leading to e->src.
3156 The second may lead to infinite loop in the case we are predicitng
3157 regions that are only reachable by abnormal edges. We simply
3158 prevent visiting given BB twice. */
3159 if (found)
3161 if (!edge_predicted_by_p (e, pred, taken))
3162 predict_edge_def (e, pred, taken);
3164 else if (bitmap_set_bit (visited, e->src->index))
3165 predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
3167 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3168 son;
3169 son = next_dom_son (CDI_POST_DOMINATORS, son))
3170 predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
3173 /* Sets branch probabilities according to PREDiction and
3174 FLAGS. */
3176 static void
3177 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3178 enum prediction taken, struct loop *in_loop)
3180 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3183 /* Like predict_paths_leading_to but take edge instead of basic block. */
3185 static void
3186 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3187 enum prediction taken, struct loop *in_loop)
3189 bool has_nonloop_edge = false;
3190 edge_iterator ei;
3191 edge e2;
3193 basic_block bb = e->src;
3194 FOR_EACH_EDGE (e2, ei, bb->succs)
3195 if (e2->dest != e->src && e2->dest != e->dest
3196 && !unlikely_executed_edge_p (e)
3197 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3199 has_nonloop_edge = true;
3200 break;
3202 if (!has_nonloop_edge)
3204 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3206 else
3207 predict_edge_def (e, pred, taken);
3210 /* This is used to carry information about basic blocks. It is
3211 attached to the AUX field of the standard CFG block. */
3213 struct block_info
3215 /* Estimated frequency of execution of basic_block. */
3216 sreal frequency;
3218 /* To keep queue of basic blocks to process. */
3219 basic_block next;
3221 /* Number of predecessors we need to visit first. */
3222 int npredecessors;
3225 /* Similar information for edges. */
3226 struct edge_prob_info
3228 /* In case edge is a loopback edge, the probability edge will be reached
3229 in case header is. Estimated number of iterations of the loop can be
3230 then computed as 1 / (1 - back_edge_prob). */
3231 sreal back_edge_prob;
3232 /* True if the edge is a loopback edge in the natural loop. */
3233 unsigned int back_edge:1;
3236 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3237 #undef EDGE_INFO
3238 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3240 /* Helper function for estimate_bb_frequencies.
3241 Propagate the frequencies in blocks marked in
3242 TOVISIT, starting in HEAD. */
3244 static void
3245 propagate_freq (basic_block head, bitmap tovisit)
3247 basic_block bb;
3248 basic_block last;
3249 unsigned i;
3250 edge e;
3251 basic_block nextbb;
3252 bitmap_iterator bi;
3254 /* For each basic block we need to visit count number of his predecessors
3255 we need to visit first. */
3256 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3258 edge_iterator ei;
3259 int count = 0;
3261 bb = BASIC_BLOCK_FOR_FN (cfun, i);
3263 FOR_EACH_EDGE (e, ei, bb->preds)
3265 bool visit = bitmap_bit_p (tovisit, e->src->index);
3267 if (visit && !(e->flags & EDGE_DFS_BACK))
3268 count++;
3269 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3270 fprintf (dump_file,
3271 "Irreducible region hit, ignoring edge to %i->%i\n",
3272 e->src->index, bb->index);
3274 BLOCK_INFO (bb)->npredecessors = count;
3275 /* When function never returns, we will never process exit block. */
3276 if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3277 bb->count = profile_count::zero ();
3280 BLOCK_INFO (head)->frequency = 1;
3281 last = head;
3282 for (bb = head; bb; bb = nextbb)
3284 edge_iterator ei;
3285 sreal cyclic_probability = 0;
3286 sreal frequency = 0;
3288 nextbb = BLOCK_INFO (bb)->next;
3289 BLOCK_INFO (bb)->next = NULL;
3291 /* Compute frequency of basic block. */
3292 if (bb != head)
3294 if (flag_checking)
3295 FOR_EACH_EDGE (e, ei, bb->preds)
3296 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3297 || (e->flags & EDGE_DFS_BACK));
3299 FOR_EACH_EDGE (e, ei, bb->preds)
3300 if (EDGE_INFO (e)->back_edge)
3302 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3304 else if (!(e->flags & EDGE_DFS_BACK))
3306 /* frequency += (e->probability
3307 * BLOCK_INFO (e->src)->frequency /
3308 REG_BR_PROB_BASE); */
3310 /* FIXME: Graphite is producing edges with no profile. Once
3311 this is fixed, drop this. */
3312 sreal tmp = e->probability.initialized_p () ?
3313 e->probability.to_reg_br_prob_base () : 0;
3314 tmp *= BLOCK_INFO (e->src)->frequency;
3315 tmp *= real_inv_br_prob_base;
3316 frequency += tmp;
3319 if (cyclic_probability == 0)
3321 BLOCK_INFO (bb)->frequency = frequency;
3323 else
3325 if (cyclic_probability > real_almost_one)
3326 cyclic_probability = real_almost_one;
3328 /* BLOCK_INFO (bb)->frequency = frequency
3329 / (1 - cyclic_probability) */
3331 cyclic_probability = sreal (1) - cyclic_probability;
3332 BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
3336 bitmap_clear_bit (tovisit, bb->index);
3338 e = find_edge (bb, head);
3339 if (e)
3341 /* EDGE_INFO (e)->back_edge_prob
3342 = ((e->probability * BLOCK_INFO (bb)->frequency)
3343 / REG_BR_PROB_BASE); */
3345 /* FIXME: Graphite is producing edges with no profile. Once
3346 this is fixed, drop this. */
3347 sreal tmp = e->probability.initialized_p () ?
3348 e->probability.to_reg_br_prob_base () : 0;
3349 tmp *= BLOCK_INFO (bb)->frequency;
3350 EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
3353 /* Propagate to successor blocks. */
3354 FOR_EACH_EDGE (e, ei, bb->succs)
3355 if (!(e->flags & EDGE_DFS_BACK)
3356 && BLOCK_INFO (e->dest)->npredecessors)
3358 BLOCK_INFO (e->dest)->npredecessors--;
3359 if (!BLOCK_INFO (e->dest)->npredecessors)
3361 if (!nextbb)
3362 nextbb = e->dest;
3363 else
3364 BLOCK_INFO (last)->next = e->dest;
3366 last = e->dest;
3372 /* Estimate frequencies in loops at same nest level. */
3374 static void
3375 estimate_loops_at_level (struct loop *first_loop)
3377 struct loop *loop;
3379 for (loop = first_loop; loop; loop = loop->next)
3381 edge e;
3382 basic_block *bbs;
3383 unsigned i;
3384 auto_bitmap tovisit;
3386 estimate_loops_at_level (loop->inner);
3388 /* Find current loop back edge and mark it. */
3389 e = loop_latch_edge (loop);
3390 EDGE_INFO (e)->back_edge = 1;
3392 bbs = get_loop_body (loop);
3393 for (i = 0; i < loop->num_nodes; i++)
3394 bitmap_set_bit (tovisit, bbs[i]->index);
3395 free (bbs);
3396 propagate_freq (loop->header, tovisit);
3400 /* Propagates frequencies through structure of loops. */
3402 static void
3403 estimate_loops (void)
3405 auto_bitmap tovisit;
3406 basic_block bb;
3408 /* Start by estimating the frequencies in the loops. */
3409 if (number_of_loops (cfun) > 1)
3410 estimate_loops_at_level (current_loops->tree_root->inner);
3412 /* Now propagate the frequencies through all the blocks. */
3413 FOR_ALL_BB_FN (bb, cfun)
3415 bitmap_set_bit (tovisit, bb->index);
3417 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
3420 /* Drop the profile for NODE to guessed, and update its frequency based on
3421 whether it is expected to be hot given the CALL_COUNT. */
3423 static void
3424 drop_profile (struct cgraph_node *node, profile_count call_count)
3426 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3427 /* In the case where this was called by another function with a
3428 dropped profile, call_count will be 0. Since there are no
3429 non-zero call counts to this function, we don't know for sure
3430 whether it is hot, and therefore it will be marked normal below. */
3431 bool hot = maybe_hot_count_p (NULL, call_count);
3433 if (dump_file)
3434 fprintf (dump_file,
3435 "Dropping 0 profile for %s. %s based on calls.\n",
3436 node->dump_name (),
3437 hot ? "Function is hot" : "Function is normal");
3438 /* We only expect to miss profiles for functions that are reached
3439 via non-zero call edges in cases where the function may have
3440 been linked from another module or library (COMDATs and extern
3441 templates). See the comments below for handle_missing_profiles.
3442 Also, only warn in cases where the missing counts exceed the
3443 number of training runs. In certain cases with an execv followed
3444 by a no-return call the profile for the no-return call is not
3445 dumped and there can be a mismatch. */
3446 if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3447 && call_count > profile_info->runs)
3449 if (flag_profile_correction)
3451 if (dump_file)
3452 fprintf (dump_file,
3453 "Missing counts for called function %s\n",
3454 node->dump_name ());
3456 else
3457 warning (0, "Missing counts for called function %s",
3458 node->dump_name ());
3461 basic_block bb;
3462 if (opt_for_fn (node->decl, flag_guess_branch_prob))
3464 bool clear_zeros
3465 = !ENTRY_BLOCK_PTR_FOR_FN (fn)->count.nonzero_p ();
3466 FOR_ALL_BB_FN (bb, fn)
3467 if (clear_zeros || !(bb->count == profile_count::zero ()))
3468 bb->count = bb->count.guessed_local ();
3469 fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
3471 else
3473 FOR_ALL_BB_FN (bb, fn)
3474 bb->count = profile_count::uninitialized ();
3475 fn->cfg->count_max = profile_count::uninitialized ();
3478 struct cgraph_edge *e;
3479 for (e = node->callees; e; e = e->next_callee)
3480 e->count = gimple_bb (e->call_stmt)->count;
3481 for (e = node->indirect_calls; e; e = e->next_callee)
3482 e->count = gimple_bb (e->call_stmt)->count;
3483 node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)->count;
3485 profile_status_for_fn (fn)
3486 = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3487 node->frequency
3488 = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3491 /* In the case of COMDAT routines, multiple object files will contain the same
3492 function and the linker will select one for the binary. In that case
3493 all the other copies from the profile instrument binary will be missing
3494 profile counts. Look for cases where this happened, due to non-zero
3495 call counts going to 0-count functions, and drop the profile to guessed
3496 so that we can use the estimated probabilities and avoid optimizing only
3497 for size.
3499 The other case where the profile may be missing is when the routine
3500 is not going to be emitted to the object file, e.g. for "extern template"
3501 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3502 all other cases of non-zero calls to 0-count functions. */
3504 void
3505 handle_missing_profiles (void)
3507 struct cgraph_node *node;
3508 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
3509 auto_vec<struct cgraph_node *, 64> worklist;
3511 /* See if 0 count function has non-0 count callers. In this case we
3512 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3513 FOR_EACH_DEFINED_FUNCTION (node)
3515 struct cgraph_edge *e;
3516 profile_count call_count = profile_count::zero ();
3517 gcov_type max_tp_first_run = 0;
3518 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3520 if (node->count.ipa ().nonzero_p ())
3521 continue;
3522 for (e = node->callers; e; e = e->next_caller)
3523 if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
3525 call_count = call_count + e->count.ipa ();
3527 if (e->caller->tp_first_run > max_tp_first_run)
3528 max_tp_first_run = e->caller->tp_first_run;
3531 /* If time profile is missing, let assign the maximum that comes from
3532 caller functions. */
3533 if (!node->tp_first_run && max_tp_first_run)
3534 node->tp_first_run = max_tp_first_run + 1;
3536 if (call_count > 0
3537 && fn && fn->cfg
3538 && (call_count.apply_scale (unlikely_count_fraction, 1)
3539 >= profile_info->runs))
3541 drop_profile (node, call_count);
3542 worklist.safe_push (node);
3546 /* Propagate the profile dropping to other 0-count COMDATs that are
3547 potentially called by COMDATs we already dropped the profile on. */
3548 while (worklist.length () > 0)
3550 struct cgraph_edge *e;
3552 node = worklist.pop ();
3553 for (e = node->callees; e; e = e->next_caller)
3555 struct cgraph_node *callee = e->callee;
3556 struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3558 if (!(e->count.ipa () == profile_count::zero ())
3559 && callee->count.ipa ().nonzero_p ())
3560 continue;
3561 if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3562 && fn && fn->cfg
3563 && profile_status_for_fn (fn) == PROFILE_READ)
3565 drop_profile (node, profile_count::zero ());
3566 worklist.safe_push (callee);
3572 /* Convert counts measured by profile driven feedback to frequencies.
3573 Return nonzero iff there was any nonzero execution count. */
3575 bool
3576 update_max_bb_count (void)
3578 profile_count true_count_max = profile_count::uninitialized ();
3579 basic_block bb;
3581 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3582 true_count_max = true_count_max.max (bb->count);
3584 cfun->cfg->count_max = true_count_max;
3586 return true_count_max.ipa ().nonzero_p ();
3589 /* Return true if function is likely to be expensive, so there is no point to
3590 optimize performance of prologue, epilogue or do inlining at the expense
3591 of code size growth. THRESHOLD is the limit of number of instructions
3592 function can execute at average to be still considered not expensive. */
3594 bool
3595 expensive_function_p (int threshold)
3597 basic_block bb;
3599 /* If profile was scaled in a way entry block has count 0, then the function
3600 is deifnitly taking a lot of time. */
3601 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3602 return true;
3604 profile_count limit = ENTRY_BLOCK_PTR_FOR_FN
3605 (cfun)->count.apply_scale (threshold, 1);
3606 profile_count sum = profile_count::zero ();
3607 FOR_EACH_BB_FN (bb, cfun)
3609 rtx_insn *insn;
3611 if (!bb->count.initialized_p ())
3613 if (dump_file)
3614 fprintf (dump_file, "Function is considered expensive because"
3615 " count of bb %i is not initialized\n", bb->index);
3616 return true;
3619 FOR_BB_INSNS (bb, insn)
3620 if (active_insn_p (insn))
3622 sum += bb->count;
3623 if (sum > limit)
3624 return true;
3628 return false;
3631 /* All basic blocks that are reachable only from unlikely basic blocks are
3632 unlikely. */
3634 void
3635 propagate_unlikely_bbs_forward (void)
3637 auto_vec<basic_block, 64> worklist;
3638 basic_block bb;
3639 edge_iterator ei;
3640 edge e;
3642 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3644 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3645 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3647 while (worklist.length () > 0)
3649 bb = worklist.pop ();
3650 FOR_EACH_EDGE (e, ei, bb->succs)
3651 if (!(e->count () == profile_count::zero ())
3652 && !(e->dest->count == profile_count::zero ())
3653 && !e->dest->aux)
3655 e->dest->aux = (void *)(size_t) 1;
3656 worklist.safe_push (e->dest);
3661 FOR_ALL_BB_FN (bb, cfun)
3663 if (!bb->aux)
3665 if (!(bb->count == profile_count::zero ())
3666 && (dump_file && (dump_flags & TDF_DETAILS)))
3667 fprintf (dump_file,
3668 "Basic block %i is marked unlikely by forward prop\n",
3669 bb->index);
3670 bb->count = profile_count::zero ();
3672 else
3673 bb->aux = NULL;
3677 /* Determine basic blocks/edges that are known to be unlikely executed and set
3678 their counters to zero.
3679 This is done with first identifying obviously unlikely BBs/edges and then
3680 propagating in both directions. */
3682 static void
3683 determine_unlikely_bbs ()
3685 basic_block bb;
3686 auto_vec<basic_block, 64> worklist;
3687 edge_iterator ei;
3688 edge e;
3690 FOR_EACH_BB_FN (bb, cfun)
3692 if (!(bb->count == profile_count::zero ())
3693 && unlikely_executed_bb_p (bb))
3695 if (dump_file && (dump_flags & TDF_DETAILS))
3696 fprintf (dump_file, "Basic block %i is locally unlikely\n",
3697 bb->index);
3698 bb->count = profile_count::zero ();
3701 FOR_EACH_EDGE (e, ei, bb->succs)
3702 if (!(e->probability == profile_probability::never ())
3703 && unlikely_executed_edge_p (e))
3705 if (dump_file && (dump_flags & TDF_DETAILS))
3706 fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
3707 bb->index, e->dest->index);
3708 e->probability = profile_probability::never ();
3711 gcc_checking_assert (!bb->aux);
3713 propagate_unlikely_bbs_forward ();
3715 auto_vec<int, 64> nsuccs;
3716 nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun));
3717 FOR_ALL_BB_FN (bb, cfun)
3718 if (!(bb->count == profile_count::zero ())
3719 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3721 nsuccs[bb->index] = 0;
3722 FOR_EACH_EDGE (e, ei, bb->succs)
3723 if (!(e->probability == profile_probability::never ())
3724 && !(e->dest->count == profile_count::zero ()))
3725 nsuccs[bb->index]++;
3726 if (!nsuccs[bb->index])
3727 worklist.safe_push (bb);
3729 while (worklist.length () > 0)
3731 bb = worklist.pop ();
3732 if (bb->count == profile_count::zero ())
3733 continue;
3734 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3736 bool found = false;
3737 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
3738 !gsi_end_p (gsi); gsi_next (&gsi))
3739 if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
3740 /* stmt_can_terminate_bb_p special cases noreturns because it
3741 assumes that fake edges are created. We want to know that
3742 noreturn alone does not imply BB to be unlikely. */
3743 || (is_gimple_call (gsi_stmt (gsi))
3744 && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
3746 found = true;
3747 break;
3749 if (found)
3750 continue;
3752 if (dump_file && (dump_flags & TDF_DETAILS))
3753 fprintf (dump_file,
3754 "Basic block %i is marked unlikely by backward prop\n",
3755 bb->index);
3756 bb->count = profile_count::zero ();
3757 FOR_EACH_EDGE (e, ei, bb->preds)
3758 if (!(e->probability == profile_probability::never ()))
3760 if (!(e->src->count == profile_count::zero ()))
3762 gcc_checking_assert (nsuccs[e->src->index] > 0);
3763 nsuccs[e->src->index]--;
3764 if (!nsuccs[e->src->index])
3765 worklist.safe_push (e->src);
3769 /* Finally all edges from non-0 regions to 0 are unlikely. */
3770 FOR_ALL_BB_FN (bb, cfun)
3771 if (!(bb->count == profile_count::zero ()))
3772 FOR_EACH_EDGE (e, ei, bb->succs)
3773 if (!(e->probability == profile_probability::never ())
3774 && e->dest->count == profile_count::zero ())
3776 if (dump_file && (dump_flags & TDF_DETAILS))
3777 fprintf (dump_file, "Edge %i->%i is unlikely because "
3778 "it enters unlikely block\n",
3779 bb->index, e->dest->index);
3780 e->probability = profile_probability::never ();
3782 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
3783 cgraph_node::get (current_function_decl)->count = profile_count::zero ();
3786 /* Estimate and propagate basic block frequencies using the given branch
3787 probabilities. If FORCE is true, the frequencies are used to estimate
3788 the counts even when there are already non-zero profile counts. */
3790 void
3791 estimate_bb_frequencies (bool force)
3793 basic_block bb;
3794 sreal freq_max;
3796 determine_unlikely_bbs ();
3798 if (force || profile_status_for_fn (cfun) != PROFILE_READ
3799 || !update_max_bb_count ())
3801 static int real_values_initialized = 0;
3803 if (!real_values_initialized)
3805 real_values_initialized = 1;
3806 real_br_prob_base = REG_BR_PROB_BASE;
3807 /* Scaling frequencies up to maximal profile count may result in
3808 frequent overflows especially when inlining loops.
3809 Small scalling results in unnecesary precision loss. Stay in
3810 the half of the (exponential) range. */
3811 real_bb_freq_max = (uint64_t)1 << (profile_count::n_bits / 2);
3812 real_one_half = sreal (1, -1);
3813 real_inv_br_prob_base = sreal (1) / real_br_prob_base;
3814 real_almost_one = sreal (1) - real_inv_br_prob_base;
3817 mark_dfs_back_edges ();
3819 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
3820 profile_probability::always ();
3822 /* Set up block info for each basic block. */
3823 alloc_aux_for_blocks (sizeof (block_info));
3824 alloc_aux_for_edges (sizeof (edge_prob_info));
3825 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3827 edge e;
3828 edge_iterator ei;
3830 FOR_EACH_EDGE (e, ei, bb->succs)
3832 /* FIXME: Graphite is producing edges with no profile. Once
3833 this is fixed, drop this. */
3834 if (e->probability.initialized_p ())
3835 EDGE_INFO (e)->back_edge_prob
3836 = e->probability.to_reg_br_prob_base ();
3837 else
3838 EDGE_INFO (e)->back_edge_prob = REG_BR_PROB_BASE / 2;
3839 EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
3843 /* First compute frequencies locally for each loop from innermost
3844 to outermost to examine frequencies for back edges. */
3845 estimate_loops ();
3847 freq_max = 0;
3848 FOR_EACH_BB_FN (bb, cfun)
3849 if (freq_max < BLOCK_INFO (bb)->frequency)
3850 freq_max = BLOCK_INFO (bb)->frequency;
3852 freq_max = real_bb_freq_max / freq_max;
3853 if (freq_max < 16)
3854 freq_max = 16;
3855 profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
3856 cfun->cfg->count_max = profile_count::uninitialized ();
3857 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3859 sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
3860 profile_count count = profile_count::from_gcov_type (tmp.to_int ());
3862 /* If we have profile feedback in which this function was never
3863 executed, then preserve this info. */
3864 if (!(bb->count == profile_count::zero ()))
3865 bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
3866 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
3869 free_aux_for_blocks ();
3870 free_aux_for_edges ();
3872 compute_function_frequency ();
3875 /* Decide whether function is hot, cold or unlikely executed. */
3876 void
3877 compute_function_frequency (void)
3879 basic_block bb;
3880 struct cgraph_node *node = cgraph_node::get (current_function_decl);
3882 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3883 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
3884 node->only_called_at_startup = true;
3885 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
3886 node->only_called_at_exit = true;
3888 if (profile_status_for_fn (cfun) != PROFILE_READ)
3890 int flags = flags_from_decl_or_type (current_function_decl);
3891 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ()
3892 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3893 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
3894 != NULL)
3896 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3897 warn_function_cold (current_function_decl);
3899 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
3900 != NULL)
3901 node->frequency = NODE_FREQUENCY_HOT;
3902 else if (flags & ECF_NORETURN)
3903 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3904 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
3905 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3906 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3907 || DECL_STATIC_DESTRUCTOR (current_function_decl))
3908 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3909 return;
3912 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3913 warn_function_cold (current_function_decl);
3914 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3915 return;
3916 FOR_EACH_BB_FN (bb, cfun)
3918 if (maybe_hot_bb_p (cfun, bb))
3920 node->frequency = NODE_FREQUENCY_HOT;
3921 return;
3923 if (!probably_never_executed_bb_p (cfun, bb))
3924 node->frequency = NODE_FREQUENCY_NORMAL;
3928 /* Build PREDICT_EXPR. */
3929 tree
3930 build_predict_expr (enum br_predictor predictor, enum prediction taken)
3932 tree t = build1 (PREDICT_EXPR, void_type_node,
3933 build_int_cst (integer_type_node, predictor));
3934 SET_PREDICT_EXPR_OUTCOME (t, taken);
3935 return t;
3938 const char *
3939 predictor_name (enum br_predictor predictor)
3941 return predictor_info[predictor].name;
3944 /* Predict branch probabilities and estimate profile of the tree CFG. */
3946 namespace {
3948 const pass_data pass_data_profile =
3950 GIMPLE_PASS, /* type */
3951 "profile_estimate", /* name */
3952 OPTGROUP_NONE, /* optinfo_flags */
3953 TV_BRANCH_PROB, /* tv_id */
3954 PROP_cfg, /* properties_required */
3955 0, /* properties_provided */
3956 0, /* properties_destroyed */
3957 0, /* todo_flags_start */
3958 0, /* todo_flags_finish */
3961 class pass_profile : public gimple_opt_pass
3963 public:
3964 pass_profile (gcc::context *ctxt)
3965 : gimple_opt_pass (pass_data_profile, ctxt)
3968 /* opt_pass methods: */
3969 virtual bool gate (function *) { return flag_guess_branch_prob; }
3970 virtual unsigned int execute (function *);
3972 }; // class pass_profile
3974 unsigned int
3975 pass_profile::execute (function *fun)
3977 unsigned nb_loops;
3979 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3980 return 0;
3982 loop_optimizer_init (LOOPS_NORMAL);
3983 if (dump_file && (dump_flags & TDF_DETAILS))
3984 flow_loops_dump (dump_file, NULL, 0);
3986 mark_irreducible_loops ();
3988 nb_loops = number_of_loops (fun);
3989 if (nb_loops > 1)
3990 scev_initialize ();
3992 tree_estimate_probability (false);
3994 if (nb_loops > 1)
3995 scev_finalize ();
3997 loop_optimizer_finalize ();
3998 if (dump_file && (dump_flags & TDF_DETAILS))
3999 gimple_dump_cfg (dump_file, dump_flags);
4000 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
4001 profile_status_for_fn (fun) = PROFILE_GUESSED;
4002 if (dump_file && (dump_flags & TDF_DETAILS))
4004 struct loop *loop;
4005 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
4006 if (loop->header->count.initialized_p ())
4007 fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
4008 loop->num,
4009 (int)expected_loop_iterations_unbounded (loop));
4011 return 0;
4014 } // anon namespace
4016 gimple_opt_pass *
4017 make_pass_profile (gcc::context *ctxt)
4019 return new pass_profile (ctxt);
4022 /* Return true when PRED predictor should be removed after early
4023 tree passes. Most of the predictors are beneficial to survive
4024 as early inlining can also distribute then into caller's bodies. */
4026 static bool
4027 strip_predictor_early (enum br_predictor pred)
4029 switch (pred)
4031 case PRED_TREE_EARLY_RETURN:
4032 return true;
4033 default:
4034 return false;
4038 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
4039 we no longer need. EARLY is set to true when called from early
4040 optimizations. */
4042 unsigned int
4043 strip_predict_hints (function *fun, bool early)
4045 basic_block bb;
4046 gimple *ass_stmt;
4047 tree var;
4048 bool changed = false;
4050 FOR_EACH_BB_FN (bb, fun)
4052 gimple_stmt_iterator bi;
4053 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
4055 gimple *stmt = gsi_stmt (bi);
4057 if (gimple_code (stmt) == GIMPLE_PREDICT)
4059 if (!early
4060 || strip_predictor_early (gimple_predict_predictor (stmt)))
4062 gsi_remove (&bi, true);
4063 changed = true;
4064 continue;
4067 else if (is_gimple_call (stmt))
4069 tree fndecl = gimple_call_fndecl (stmt);
4071 if (!early
4072 && ((fndecl != NULL_TREE
4073 && fndecl_built_in_p (fndecl, BUILT_IN_EXPECT)
4074 && gimple_call_num_args (stmt) == 2)
4075 || (fndecl != NULL_TREE
4076 && fndecl_built_in_p (fndecl,
4077 BUILT_IN_EXPECT_WITH_PROBABILITY)
4078 && gimple_call_num_args (stmt) == 3)
4079 || (gimple_call_internal_p (stmt)
4080 && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
4082 var = gimple_call_lhs (stmt);
4083 changed = true;
4084 if (var)
4086 ass_stmt
4087 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
4088 gsi_replace (&bi, ass_stmt, true);
4090 else
4092 gsi_remove (&bi, true);
4093 continue;
4097 gsi_next (&bi);
4100 return changed ? TODO_cleanup_cfg : 0;
4103 namespace {
4105 const pass_data pass_data_strip_predict_hints =
4107 GIMPLE_PASS, /* type */
4108 "*strip_predict_hints", /* name */
4109 OPTGROUP_NONE, /* optinfo_flags */
4110 TV_BRANCH_PROB, /* tv_id */
4111 PROP_cfg, /* properties_required */
4112 0, /* properties_provided */
4113 0, /* properties_destroyed */
4114 0, /* todo_flags_start */
4115 0, /* todo_flags_finish */
4118 class pass_strip_predict_hints : public gimple_opt_pass
4120 public:
4121 pass_strip_predict_hints (gcc::context *ctxt)
4122 : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4125 /* opt_pass methods: */
4126 opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
4127 void set_pass_param (unsigned int n, bool param)
4129 gcc_assert (n == 0);
4130 early_p = param;
4133 virtual unsigned int execute (function *);
4135 private:
4136 bool early_p;
4138 }; // class pass_strip_predict_hints
4140 unsigned int
4141 pass_strip_predict_hints::execute (function *fun)
4143 return strip_predict_hints (fun, early_p);
4146 } // anon namespace
4148 gimple_opt_pass *
4149 make_pass_strip_predict_hints (gcc::context *ctxt)
4151 return new pass_strip_predict_hints (ctxt);
4154 /* Rebuild function frequencies. Passes are in general expected to
4155 maintain profile by hand, however in some cases this is not possible:
4156 for example when inlining several functions with loops freuqencies might run
4157 out of scale and thus needs to be recomputed. */
4159 void
4160 rebuild_frequencies (void)
4162 timevar_push (TV_REBUILD_FREQUENCIES);
4164 /* When the max bb count in the function is small, there is a higher
4165 chance that there were truncation errors in the integer scaling
4166 of counts by inlining and other optimizations. This could lead
4167 to incorrect classification of code as being cold when it isn't.
4168 In that case, force the estimation of bb counts/frequencies from the
4169 branch probabilities, rather than computing frequencies from counts,
4170 which may also lead to frequencies incorrectly reduced to 0. There
4171 is less precision in the probabilities, so we only do this for small
4172 max counts. */
4173 cfun->cfg->count_max = profile_count::uninitialized ();
4174 basic_block bb;
4175 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4176 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
4178 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4180 loop_optimizer_init (0);
4181 add_noreturn_fake_exit_edges ();
4182 mark_irreducible_loops ();
4183 connect_infinite_loops_to_exit ();
4184 estimate_bb_frequencies (true);
4185 remove_fake_exit_edges ();
4186 loop_optimizer_finalize ();
4188 else if (profile_status_for_fn (cfun) == PROFILE_READ)
4189 update_max_bb_count ();
4190 else if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4191 && !flag_guess_branch_prob)
4193 else
4194 gcc_unreachable ();
4195 timevar_pop (TV_REBUILD_FREQUENCIES);
4198 /* Perform a dry run of the branch prediction pass and report comparsion of
4199 the predicted and real profile into the dump file. */
4201 void
4202 report_predictor_hitrates (void)
4204 unsigned nb_loops;
4206 loop_optimizer_init (LOOPS_NORMAL);
4207 if (dump_file && (dump_flags & TDF_DETAILS))
4208 flow_loops_dump (dump_file, NULL, 0);
4210 mark_irreducible_loops ();
4212 nb_loops = number_of_loops (cfun);
4213 if (nb_loops > 1)
4214 scev_initialize ();
4216 tree_estimate_probability (true);
4218 if (nb_loops > 1)
4219 scev_finalize ();
4221 loop_optimizer_finalize ();
4224 /* Force edge E to be cold.
4225 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4226 keep low probability to represent possible error in a guess. This is used
4227 i.e. in case we predict loop to likely iterate given number of times but
4228 we are not 100% sure.
4230 This function locally updates profile without attempt to keep global
4231 consistency which can not be reached in full generality without full profile
4232 rebuild from probabilities alone. Doing so is not necessarily a good idea
4233 because frequencies and counts may be more realistic then probabilities.
4235 In some cases (such as for elimination of early exits during full loop
4236 unrolling) the caller can ensure that profile will get consistent
4237 afterwards. */
4239 void
4240 force_edge_cold (edge e, bool impossible)
4242 profile_count count_sum = profile_count::zero ();
4243 profile_probability prob_sum = profile_probability::never ();
4244 edge_iterator ei;
4245 edge e2;
4246 bool uninitialized_exit = false;
4248 /* When branch probability guesses are not known, then do nothing. */
4249 if (!impossible && !e->count ().initialized_p ())
4250 return;
4252 profile_probability goal = (impossible ? profile_probability::never ()
4253 : profile_probability::very_unlikely ());
4255 /* If edge is already improbably or cold, just return. */
4256 if (e->probability <= goal
4257 && (!impossible || e->count () == profile_count::zero ()))
4258 return;
4259 FOR_EACH_EDGE (e2, ei, e->src->succs)
4260 if (e2 != e)
4262 if (e->flags & EDGE_FAKE)
4263 continue;
4264 if (e2->count ().initialized_p ())
4265 count_sum += e2->count ();
4266 if (e2->probability.initialized_p ())
4267 prob_sum += e2->probability;
4268 else
4269 uninitialized_exit = true;
4272 /* If we are not guessing profiles but have some other edges out,
4273 just assume the control flow goes elsewhere. */
4274 if (uninitialized_exit)
4275 e->probability = goal;
4276 /* If there are other edges out of e->src, redistribute probabilitity
4277 there. */
4278 else if (prob_sum > profile_probability::never ())
4280 if (!(e->probability < goal))
4281 e->probability = goal;
4283 profile_probability prob_comp = prob_sum / e->probability.invert ();
4285 if (dump_file && (dump_flags & TDF_DETAILS))
4286 fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4287 "probability to other edges.\n",
4288 e->src->index, e->dest->index,
4289 impossible ? "impossible" : "cold");
4290 FOR_EACH_EDGE (e2, ei, e->src->succs)
4291 if (e2 != e)
4293 e2->probability /= prob_comp;
4295 if (current_ir_type () != IR_GIMPLE
4296 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4297 update_br_prob_note (e->src);
4299 /* If all edges out of e->src are unlikely, the basic block itself
4300 is unlikely. */
4301 else
4303 if (prob_sum == profile_probability::never ())
4304 e->probability = profile_probability::always ();
4305 else
4307 if (impossible)
4308 e->probability = profile_probability::never ();
4309 /* If BB has some edges out that are not impossible, we can not
4310 assume that BB itself is. */
4311 impossible = false;
4313 if (current_ir_type () != IR_GIMPLE
4314 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4315 update_br_prob_note (e->src);
4316 if (e->src->count == profile_count::zero ())
4317 return;
4318 if (count_sum == profile_count::zero () && impossible)
4320 bool found = false;
4321 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4323 else if (current_ir_type () == IR_GIMPLE)
4324 for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4325 !gsi_end_p (gsi); gsi_next (&gsi))
4327 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
4329 found = true;
4330 break;
4333 /* FIXME: Implement RTL path. */
4334 else
4335 found = true;
4336 if (!found)
4338 if (dump_file && (dump_flags & TDF_DETAILS))
4339 fprintf (dump_file,
4340 "Making bb %i impossible and dropping count to 0.\n",
4341 e->src->index);
4342 e->src->count = profile_count::zero ();
4343 FOR_EACH_EDGE (e2, ei, e->src->preds)
4344 force_edge_cold (e2, impossible);
4345 return;
4349 /* If we did not adjusting, the source basic block has no likely edeges
4350 leaving other direction. In that case force that bb cold, too.
4351 This in general is difficult task to do, but handle special case when
4352 BB has only one predecestor. This is common case when we are updating
4353 after loop transforms. */
4354 if (!(prob_sum > profile_probability::never ())
4355 && count_sum == profile_count::zero ()
4356 && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4357 > (impossible ? 0 : 1))
4359 int old_frequency = e->src->count.to_frequency (cfun);
4360 if (dump_file && (dump_flags & TDF_DETAILS))
4361 fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
4362 impossible ? "impossible" : "cold");
4363 int new_frequency = MIN (e->src->count.to_frequency (cfun),
4364 impossible ? 0 : 1);
4365 if (impossible)
4366 e->src->count = profile_count::zero ();
4367 else
4368 e->src->count = e->count ().apply_scale (new_frequency,
4369 old_frequency);
4370 force_edge_cold (single_pred_edge (e->src), impossible);
4372 else if (dump_file && (dump_flags & TDF_DETAILS)
4373 && maybe_hot_bb_p (cfun, e->src))
4374 fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
4375 impossible ? "impossible" : "cold");
4379 #if CHECKING_P
4381 namespace selftest {
4383 /* Test that value range of predictor values defined in predict.def is
4384 within range (50, 100]. */
4386 struct branch_predictor
4388 const char *name;
4389 int probability;
4392 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4394 static void
4395 test_prediction_value_range ()
4397 branch_predictor predictors[] = {
4398 #include "predict.def"
4399 { NULL, PROB_UNINITIALIZED }
4402 for (unsigned i = 0; predictors[i].name != NULL; i++)
4404 if (predictors[i].probability == PROB_UNINITIALIZED)
4405 continue;
4407 unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4408 ASSERT_TRUE (p >= 50 && p <= 100);
4412 #undef DEF_PREDICTOR
4414 /* Run all of the selfests within this file. */
4416 void
4417 predict_c_tests ()
4419 test_prediction_value_range ();
4422 } // namespace selftest
4423 #endif /* CHECKING_P. */