PR c++/86728 - C variadic generic lambda.
[official-gcc.git] / gcc / predict.c
blob3fbe3b704b318f46c8b65add32d19dc478795b7a
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 gcov_working_set_t *ws;
133 if (min_count == -1)
135 ws = find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE));
136 gcc_assert (ws);
137 min_count = ws->min_counter;
139 return min_count;
142 /* Set the threshold for hot BB counts. */
144 void
145 set_hot_bb_threshold (gcov_type min)
147 min_count = min;
150 /* Return TRUE if frequency FREQ is considered to be hot. */
152 bool
153 maybe_hot_count_p (struct function *fun, profile_count count)
155 if (!count.initialized_p ())
156 return true;
157 if (count.ipa () == profile_count::zero ())
158 return false;
159 if (!count.ipa_p ())
161 struct cgraph_node *node = cgraph_node::get (fun->decl);
162 if (!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
164 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
165 return false;
166 if (node->frequency == NODE_FREQUENCY_HOT)
167 return true;
169 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
170 return true;
171 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
172 && count < (ENTRY_BLOCK_PTR_FOR_FN (fun)->count.apply_scale (2, 3)))
173 return false;
174 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
175 return false;
176 if (count.apply_scale (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION), 1)
177 < ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
178 return false;
179 return true;
181 /* Code executed at most once is not hot. */
182 if (count <= MAX (profile_info ? profile_info->runs : 1, 1))
183 return false;
184 return (count.to_gcov_type () >= get_hot_bb_threshold ());
187 /* Return true in case BB can be CPU intensive and should be optimized
188 for maximal performance. */
190 bool
191 maybe_hot_bb_p (struct function *fun, const_basic_block bb)
193 gcc_checking_assert (fun);
194 return maybe_hot_count_p (fun, bb->count);
197 /* Return true in case BB can be CPU intensive and should be optimized
198 for maximal performance. */
200 bool
201 maybe_hot_edge_p (edge e)
203 return maybe_hot_count_p (cfun, e->count ());
206 /* Return true if profile COUNT and FREQUENCY, or function FUN static
207 node frequency reflects never being executed. */
209 static bool
210 probably_never_executed (struct function *fun,
211 profile_count count)
213 gcc_checking_assert (fun);
214 if (count.ipa () == profile_count::zero ())
215 return true;
216 /* Do not trust adjusted counts. This will make us to drop int cold section
217 code with low execution count as a result of inlining. These low counts
218 are not safe even with read profile and may lead us to dropping
219 code which actually gets executed into cold section of binary that is not
220 desirable. */
221 if (count.precise_p () && profile_status_for_fn (fun) == PROFILE_READ)
223 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
224 if (count.apply_scale (unlikely_count_fraction, 1) >= profile_info->runs)
225 return false;
226 return true;
228 if ((!profile_info || profile_status_for_fn (fun) != PROFILE_READ)
229 && (cgraph_node::get (fun->decl)->frequency
230 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
231 return true;
232 return false;
236 /* Return true in case BB is probably never executed. */
238 bool
239 probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
241 return probably_never_executed (fun, bb->count);
245 /* Return true if E is unlikely executed for obvious reasons. */
247 static bool
248 unlikely_executed_edge_p (edge e)
250 return (e->count () == profile_count::zero ()
251 || e->probability == profile_probability::never ())
252 || (e->flags & (EDGE_EH | EDGE_FAKE));
255 /* Return true in case edge E is probably never executed. */
257 bool
258 probably_never_executed_edge_p (struct function *fun, edge e)
260 if (unlikely_executed_edge_p (e))
261 return true;
262 return probably_never_executed (fun, e->count ());
265 /* Return true when current function should always be optimized for size. */
267 bool
268 optimize_function_for_size_p (struct function *fun)
270 if (!fun || !fun->decl)
271 return optimize_size;
272 cgraph_node *n = cgraph_node::get (fun->decl);
273 return n && n->optimize_for_size_p ();
276 /* Return true when current function should always be optimized for speed. */
278 bool
279 optimize_function_for_speed_p (struct function *fun)
281 return !optimize_function_for_size_p (fun);
284 /* Return the optimization type that should be used for the function FUN. */
286 optimization_type
287 function_optimization_type (struct function *fun)
289 return (optimize_function_for_speed_p (fun)
290 ? OPTIMIZE_FOR_SPEED
291 : OPTIMIZE_FOR_SIZE);
294 /* Return TRUE when BB should be optimized for size. */
296 bool
297 optimize_bb_for_size_p (const_basic_block bb)
299 return (optimize_function_for_size_p (cfun)
300 || (bb && !maybe_hot_bb_p (cfun, bb)));
303 /* Return TRUE when BB should be optimized for speed. */
305 bool
306 optimize_bb_for_speed_p (const_basic_block bb)
308 return !optimize_bb_for_size_p (bb);
311 /* Return the optimization type that should be used for block BB. */
313 optimization_type
314 bb_optimization_type (const_basic_block bb)
316 return (optimize_bb_for_speed_p (bb)
317 ? OPTIMIZE_FOR_SPEED
318 : OPTIMIZE_FOR_SIZE);
321 /* Return TRUE when BB should be optimized for size. */
323 bool
324 optimize_edge_for_size_p (edge e)
326 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
329 /* Return TRUE when BB should be optimized for speed. */
331 bool
332 optimize_edge_for_speed_p (edge e)
334 return !optimize_edge_for_size_p (e);
337 /* Return TRUE when BB should be optimized for size. */
339 bool
340 optimize_insn_for_size_p (void)
342 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
345 /* Return TRUE when BB should be optimized for speed. */
347 bool
348 optimize_insn_for_speed_p (void)
350 return !optimize_insn_for_size_p ();
353 /* Return TRUE when LOOP should be optimized for size. */
355 bool
356 optimize_loop_for_size_p (struct loop *loop)
358 return optimize_bb_for_size_p (loop->header);
361 /* Return TRUE when LOOP should be optimized for speed. */
363 bool
364 optimize_loop_for_speed_p (struct loop *loop)
366 return optimize_bb_for_speed_p (loop->header);
369 /* Return TRUE when LOOP nest should be optimized for speed. */
371 bool
372 optimize_loop_nest_for_speed_p (struct loop *loop)
374 struct loop *l = loop;
375 if (optimize_loop_for_speed_p (loop))
376 return true;
377 l = loop->inner;
378 while (l && l != loop)
380 if (optimize_loop_for_speed_p (l))
381 return true;
382 if (l->inner)
383 l = l->inner;
384 else if (l->next)
385 l = l->next;
386 else
388 while (l != loop && !l->next)
389 l = loop_outer (l);
390 if (l != loop)
391 l = l->next;
394 return false;
397 /* Return TRUE when LOOP nest should be optimized for size. */
399 bool
400 optimize_loop_nest_for_size_p (struct loop *loop)
402 return !optimize_loop_nest_for_speed_p (loop);
405 /* Return true when edge E is likely to be well predictable by branch
406 predictor. */
408 bool
409 predictable_edge_p (edge e)
411 if (!e->probability.initialized_p ())
412 return false;
413 if ((e->probability.to_reg_br_prob_base ()
414 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
415 || (REG_BR_PROB_BASE - e->probability.to_reg_br_prob_base ()
416 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
417 return true;
418 return false;
422 /* Set RTL expansion for BB profile. */
424 void
425 rtl_profile_for_bb (basic_block bb)
427 crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
430 /* Set RTL expansion for edge profile. */
432 void
433 rtl_profile_for_edge (edge e)
435 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
438 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
439 void
440 default_rtl_profile (void)
442 crtl->maybe_hot_insn_p = true;
445 /* Return true if the one of outgoing edges is already predicted by
446 PREDICTOR. */
448 bool
449 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
451 rtx note;
452 if (!INSN_P (BB_END (bb)))
453 return false;
454 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
455 if (REG_NOTE_KIND (note) == REG_BR_PRED
456 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
457 return true;
458 return false;
461 /* Structure representing predictions in tree level. */
463 struct edge_prediction {
464 struct edge_prediction *ep_next;
465 edge ep_edge;
466 enum br_predictor ep_predictor;
467 int ep_probability;
470 /* This map contains for a basic block the list of predictions for the
471 outgoing edges. */
473 static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
475 /* Return true if the one of outgoing edges is already predicted by
476 PREDICTOR. */
478 bool
479 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
481 struct edge_prediction *i;
482 edge_prediction **preds = bb_predictions->get (bb);
484 if (!preds)
485 return false;
487 for (i = *preds; i; i = i->ep_next)
488 if (i->ep_predictor == predictor)
489 return true;
490 return false;
493 /* Return true if the one of outgoing edges is already predicted by
494 PREDICTOR for edge E predicted as TAKEN. */
496 bool
497 edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
499 struct edge_prediction *i;
500 basic_block bb = e->src;
501 edge_prediction **preds = bb_predictions->get (bb);
502 if (!preds)
503 return false;
505 int probability = predictor_info[(int) predictor].hitrate;
507 if (taken != TAKEN)
508 probability = REG_BR_PROB_BASE - probability;
510 for (i = *preds; i; i = i->ep_next)
511 if (i->ep_predictor == predictor
512 && i->ep_edge == e
513 && i->ep_probability == probability)
514 return true;
515 return false;
518 /* Same predicate as above, working on edges. */
519 bool
520 edge_probability_reliable_p (const_edge e)
522 return e->probability.probably_reliable_p ();
525 /* Same predicate as edge_probability_reliable_p, working on notes. */
526 bool
527 br_prob_note_reliable_p (const_rtx note)
529 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
530 return profile_probability::from_reg_br_prob_note
531 (XINT (note, 0)).probably_reliable_p ();
534 static void
535 predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
537 gcc_assert (any_condjump_p (insn));
538 if (!flag_guess_branch_prob)
539 return;
541 add_reg_note (insn, REG_BR_PRED,
542 gen_rtx_CONCAT (VOIDmode,
543 GEN_INT ((int) predictor),
544 GEN_INT ((int) probability)));
547 /* Predict insn by given predictor. */
549 void
550 predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
551 enum prediction taken)
553 int probability = predictor_info[(int) predictor].hitrate;
554 gcc_assert (probability != PROB_UNINITIALIZED);
556 if (taken != TAKEN)
557 probability = REG_BR_PROB_BASE - probability;
559 predict_insn (insn, predictor, probability);
562 /* Predict edge E with given probability if possible. */
564 void
565 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
567 rtx_insn *last_insn;
568 last_insn = BB_END (e->src);
570 /* We can store the branch prediction information only about
571 conditional jumps. */
572 if (!any_condjump_p (last_insn))
573 return;
575 /* We always store probability of branching. */
576 if (e->flags & EDGE_FALLTHRU)
577 probability = REG_BR_PROB_BASE - probability;
579 predict_insn (last_insn, predictor, probability);
582 /* Predict edge E with the given PROBABILITY. */
583 void
584 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
586 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
587 && EDGE_COUNT (e->src->succs) > 1
588 && flag_guess_branch_prob
589 && optimize)
591 struct edge_prediction *i = XNEW (struct edge_prediction);
592 edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
594 i->ep_next = preds;
595 preds = i;
596 i->ep_probability = probability;
597 i->ep_predictor = predictor;
598 i->ep_edge = e;
602 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
603 to the filter function. */
605 void
606 filter_predictions (edge_prediction **preds,
607 bool (*filter) (edge_prediction *, void *), void *data)
609 if (!bb_predictions)
610 return;
612 if (preds)
614 struct edge_prediction **prediction = preds;
615 struct edge_prediction *next;
617 while (*prediction)
619 if ((*filter) (*prediction, data))
620 prediction = &((*prediction)->ep_next);
621 else
623 next = (*prediction)->ep_next;
624 free (*prediction);
625 *prediction = next;
631 /* Filter function predicate that returns true for a edge predicate P
632 if its edge is equal to DATA. */
634 bool
635 equal_edge_p (edge_prediction *p, void *data)
637 return p->ep_edge == (edge)data;
640 /* Remove all predictions on given basic block that are attached
641 to edge E. */
642 void
643 remove_predictions_associated_with_edge (edge e)
645 if (!bb_predictions)
646 return;
648 edge_prediction **preds = bb_predictions->get (e->src);
649 filter_predictions (preds, equal_edge_p, e);
652 /* Clears the list of predictions stored for BB. */
654 static void
655 clear_bb_predictions (basic_block bb)
657 edge_prediction **preds = bb_predictions->get (bb);
658 struct edge_prediction *pred, *next;
660 if (!preds)
661 return;
663 for (pred = *preds; pred; pred = next)
665 next = pred->ep_next;
666 free (pred);
668 *preds = NULL;
671 /* Return true when we can store prediction on insn INSN.
672 At the moment we represent predictions only on conditional
673 jumps, not at computed jump or other complicated cases. */
674 static bool
675 can_predict_insn_p (const rtx_insn *insn)
677 return (JUMP_P (insn)
678 && any_condjump_p (insn)
679 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
682 /* Predict edge E by given predictor if possible. */
684 void
685 predict_edge_def (edge e, enum br_predictor predictor,
686 enum prediction taken)
688 int probability = predictor_info[(int) predictor].hitrate;
690 if (taken != TAKEN)
691 probability = REG_BR_PROB_BASE - probability;
693 predict_edge (e, predictor, probability);
696 /* Invert all branch predictions or probability notes in the INSN. This needs
697 to be done each time we invert the condition used by the jump. */
699 void
700 invert_br_probabilities (rtx insn)
702 rtx note;
704 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
705 if (REG_NOTE_KIND (note) == REG_BR_PROB)
706 XINT (note, 0) = profile_probability::from_reg_br_prob_note
707 (XINT (note, 0)).invert ().to_reg_br_prob_note ();
708 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
709 XEXP (XEXP (note, 0), 1)
710 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
713 /* Dump information about the branch prediction to the output file. */
715 static void
716 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
717 basic_block bb, enum predictor_reason reason = REASON_NONE,
718 edge ep_edge = NULL)
720 edge e = ep_edge;
721 edge_iterator ei;
723 if (!file)
724 return;
726 if (e == NULL)
727 FOR_EACH_EDGE (e, ei, bb->succs)
728 if (! (e->flags & EDGE_FALLTHRU))
729 break;
731 char edge_info_str[128];
732 if (ep_edge)
733 sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
734 ep_edge->dest->index);
735 else
736 edge_info_str[0] = '\0';
738 fprintf (file, " %s heuristics%s%s: %.2f%%",
739 predictor_info[predictor].name,
740 edge_info_str, reason_messages[reason],
741 probability * 100.0 / REG_BR_PROB_BASE);
743 if (bb->count.initialized_p ())
745 fprintf (file, " exec ");
746 bb->count.dump (file);
747 if (e)
749 fprintf (file, " hit ");
750 e->count ().dump (file);
751 fprintf (file, " (%.1f%%)", e->count ().to_gcov_type() * 100.0
752 / bb->count.to_gcov_type ());
756 fprintf (file, "\n");
758 /* Print output that be easily read by analyze_brprob.py script. We are
759 interested only in counts that are read from GCDA files. */
760 if (dump_file && (dump_flags & TDF_DETAILS)
761 && bb->count.precise_p ()
762 && reason == REASON_NONE)
764 gcc_assert (e->count ().precise_p ());
765 fprintf (file, ";;heuristics;%s;%" PRId64 ";%" PRId64 ";%.1f;\n",
766 predictor_info[predictor].name,
767 bb->count.to_gcov_type (), e->count ().to_gcov_type (),
768 probability * 100.0 / REG_BR_PROB_BASE);
772 /* Return true if STMT is known to be unlikely executed. */
774 static bool
775 unlikely_executed_stmt_p (gimple *stmt)
777 if (!is_gimple_call (stmt))
778 return false;
779 /* NORETURN attribute alone is not strong enough: exit() may be quite
780 likely executed once during program run. */
781 if (gimple_call_fntype (stmt)
782 && lookup_attribute ("cold",
783 TYPE_ATTRIBUTES (gimple_call_fntype (stmt)))
784 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
785 return true;
786 tree decl = gimple_call_fndecl (stmt);
787 if (!decl)
788 return false;
789 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl))
790 && !lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl)))
791 return true;
793 cgraph_node *n = cgraph_node::get (decl);
794 if (!n)
795 return false;
797 availability avail;
798 n = n->ultimate_alias_target (&avail);
799 if (avail < AVAIL_AVAILABLE)
800 return false;
801 if (!n->analyzed
802 || n->decl == current_function_decl)
803 return false;
804 return n->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED;
807 /* Return true if BB is unlikely executed. */
809 static bool
810 unlikely_executed_bb_p (basic_block bb)
812 if (bb->count == profile_count::zero ())
813 return true;
814 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
815 return false;
816 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
817 !gsi_end_p (gsi); gsi_next (&gsi))
819 if (unlikely_executed_stmt_p (gsi_stmt (gsi)))
820 return true;
821 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
822 return false;
824 return false;
827 /* We can not predict the probabilities of outgoing edges of bb. Set them
828 evenly and hope for the best. If UNLIKELY_EDGES is not null, distribute
829 even probability for all edges not mentioned in the set. These edges
830 are given PROB_VERY_UNLIKELY probability. */
832 static void
833 set_even_probabilities (basic_block bb,
834 hash_set<edge> *unlikely_edges = NULL)
836 unsigned nedges = 0, unlikely_count = 0;
837 edge e = NULL;
838 edge_iterator ei;
839 profile_probability all = profile_probability::always ();
841 FOR_EACH_EDGE (e, ei, bb->succs)
842 if (e->probability.initialized_p ())
843 all -= e->probability;
844 else if (!unlikely_executed_edge_p (e))
846 nedges ++;
847 if (unlikely_edges != NULL && unlikely_edges->contains (e))
849 all -= profile_probability::very_unlikely ();
850 unlikely_count++;
854 /* Make the distribution even if all edges are unlikely. */
855 if (unlikely_count == nedges)
857 unlikely_edges = NULL;
858 unlikely_count = 0;
861 unsigned c = nedges - unlikely_count;
863 FOR_EACH_EDGE (e, ei, bb->succs)
864 if (e->probability.initialized_p ())
866 else if (!unlikely_executed_edge_p (e))
868 if (unlikely_edges != NULL && unlikely_edges->contains (e))
869 e->probability = profile_probability::very_unlikely ();
870 else
871 e->probability = all.apply_scale (1, c).guessed ();
873 else
874 e->probability = profile_probability::never ();
877 /* Add REG_BR_PROB note to JUMP with PROB. */
879 void
880 add_reg_br_prob_note (rtx_insn *jump, profile_probability prob)
882 gcc_checking_assert (JUMP_P (jump) && !find_reg_note (jump, REG_BR_PROB, 0));
883 add_int_reg_note (jump, REG_BR_PROB, prob.to_reg_br_prob_note ());
886 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
887 note if not already present. Remove now useless REG_BR_PRED notes. */
889 static void
890 combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
892 rtx prob_note;
893 rtx *pnote;
894 rtx note;
895 int best_probability = PROB_EVEN;
896 enum br_predictor best_predictor = END_PREDICTORS;
897 int combined_probability = REG_BR_PROB_BASE / 2;
898 int d;
899 bool first_match = false;
900 bool found = false;
902 if (!can_predict_insn_p (insn))
904 set_even_probabilities (bb);
905 return;
908 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
909 pnote = &REG_NOTES (insn);
910 if (dump_file)
911 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
912 bb->index);
914 /* We implement "first match" heuristics and use probability guessed
915 by predictor with smallest index. */
916 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
917 if (REG_NOTE_KIND (note) == REG_BR_PRED)
919 enum br_predictor predictor = ((enum br_predictor)
920 INTVAL (XEXP (XEXP (note, 0), 0)));
921 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
923 found = true;
924 if (best_predictor > predictor
925 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
926 best_probability = probability, best_predictor = predictor;
928 d = (combined_probability * probability
929 + (REG_BR_PROB_BASE - combined_probability)
930 * (REG_BR_PROB_BASE - probability));
932 /* Use FP math to avoid overflows of 32bit integers. */
933 if (d == 0)
934 /* If one probability is 0% and one 100%, avoid division by zero. */
935 combined_probability = REG_BR_PROB_BASE / 2;
936 else
937 combined_probability = (((double) combined_probability) * probability
938 * REG_BR_PROB_BASE / d + 0.5);
941 /* Decide which heuristic to use. In case we didn't match anything,
942 use no_prediction heuristic, in case we did match, use either
943 first match or Dempster-Shaffer theory depending on the flags. */
945 if (best_predictor != END_PREDICTORS)
946 first_match = true;
948 if (!found)
949 dump_prediction (dump_file, PRED_NO_PREDICTION,
950 combined_probability, bb);
951 else
953 if (!first_match)
954 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
955 bb, !first_match ? REASON_NONE : REASON_IGNORED);
956 else
957 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
958 bb, first_match ? REASON_NONE : REASON_IGNORED);
961 if (first_match)
962 combined_probability = best_probability;
963 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
965 while (*pnote)
967 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
969 enum br_predictor predictor = ((enum br_predictor)
970 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
971 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
973 dump_prediction (dump_file, predictor, probability, bb,
974 (!first_match || best_predictor == predictor)
975 ? REASON_NONE : REASON_IGNORED);
976 *pnote = XEXP (*pnote, 1);
978 else
979 pnote = &XEXP (*pnote, 1);
982 if (!prob_note)
984 profile_probability p
985 = profile_probability::from_reg_br_prob_base (combined_probability);
986 add_reg_br_prob_note (insn, p);
988 /* Save the prediction into CFG in case we are seeing non-degenerated
989 conditional jump. */
990 if (!single_succ_p (bb))
992 BRANCH_EDGE (bb)->probability = p;
993 FALLTHRU_EDGE (bb)->probability
994 = BRANCH_EDGE (bb)->probability.invert ();
997 else if (!single_succ_p (bb))
999 profile_probability prob = profile_probability::from_reg_br_prob_note
1000 (XINT (prob_note, 0));
1002 BRANCH_EDGE (bb)->probability = prob;
1003 FALLTHRU_EDGE (bb)->probability = prob.invert ();
1005 else
1006 single_succ_edge (bb)->probability = profile_probability::always ();
1009 /* Edge prediction hash traits. */
1011 struct predictor_hash: pointer_hash <edge_prediction>
1014 static inline hashval_t hash (const edge_prediction *);
1015 static inline bool equal (const edge_prediction *, const edge_prediction *);
1018 /* Calculate hash value of an edge prediction P based on predictor and
1019 normalized probability. */
1021 inline hashval_t
1022 predictor_hash::hash (const edge_prediction *p)
1024 inchash::hash hstate;
1025 hstate.add_int (p->ep_predictor);
1027 int prob = p->ep_probability;
1028 if (prob > REG_BR_PROB_BASE / 2)
1029 prob = REG_BR_PROB_BASE - prob;
1031 hstate.add_int (prob);
1033 return hstate.end ();
1036 /* Return true whether edge predictions P1 and P2 use the same predictor and
1037 have equal (or opposed probability). */
1039 inline bool
1040 predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
1042 return (p1->ep_predictor == p2->ep_predictor
1043 && (p1->ep_probability == p2->ep_probability
1044 || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
1047 struct predictor_hash_traits: predictor_hash,
1048 typed_noop_remove <edge_prediction *> {};
1050 /* Return true if edge prediction P is not in DATA hash set. */
1052 static bool
1053 not_removed_prediction_p (edge_prediction *p, void *data)
1055 hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
1056 return !remove->contains (p);
1059 /* Prune predictions for a basic block BB. Currently we do following
1060 clean-up steps:
1062 1) remove duplicate prediction that is guessed with the same probability
1063 (different than 1/2) to both edge
1064 2) remove duplicates for a prediction that belongs with the same probability
1065 to a single edge
1069 static void
1070 prune_predictions_for_bb (basic_block bb)
1072 edge_prediction **preds = bb_predictions->get (bb);
1074 if (preds)
1076 hash_table <predictor_hash_traits> s (13);
1077 hash_set <edge_prediction *> remove;
1079 /* Step 1: identify predictors that should be removed. */
1080 for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
1082 edge_prediction *existing = s.find (pred);
1083 if (existing)
1085 if (pred->ep_edge == existing->ep_edge
1086 && pred->ep_probability == existing->ep_probability)
1088 /* Remove a duplicate predictor. */
1089 dump_prediction (dump_file, pred->ep_predictor,
1090 pred->ep_probability, bb,
1091 REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1093 remove.add (pred);
1095 else if (pred->ep_edge != existing->ep_edge
1096 && pred->ep_probability == existing->ep_probability
1097 && pred->ep_probability != REG_BR_PROB_BASE / 2)
1099 /* Remove both predictors as they predict the same
1100 for both edges. */
1101 dump_prediction (dump_file, existing->ep_predictor,
1102 pred->ep_probability, bb,
1103 REASON_EDGE_PAIR_DUPLICATE,
1104 existing->ep_edge);
1105 dump_prediction (dump_file, pred->ep_predictor,
1106 pred->ep_probability, bb,
1107 REASON_EDGE_PAIR_DUPLICATE,
1108 pred->ep_edge);
1110 remove.add (existing);
1111 remove.add (pred);
1115 edge_prediction **slot2 = s.find_slot (pred, INSERT);
1116 *slot2 = pred;
1119 /* Step 2: Remove predictors. */
1120 filter_predictions (preds, not_removed_prediction_p, &remove);
1124 /* Combine predictions into single probability and store them into CFG.
1125 Remove now useless prediction entries.
1126 If DRY_RUN is set, only produce dumps and do not modify profile. */
1128 static void
1129 combine_predictions_for_bb (basic_block bb, bool dry_run)
1131 int best_probability = PROB_EVEN;
1132 enum br_predictor best_predictor = END_PREDICTORS;
1133 int combined_probability = REG_BR_PROB_BASE / 2;
1134 int d;
1135 bool first_match = false;
1136 bool found = false;
1137 struct edge_prediction *pred;
1138 int nedges = 0;
1139 edge e, first = NULL, second = NULL;
1140 edge_iterator ei;
1141 int nzero = 0;
1142 int nunknown = 0;
1144 FOR_EACH_EDGE (e, ei, bb->succs)
1146 if (!unlikely_executed_edge_p (e))
1148 nedges ++;
1149 if (first && !second)
1150 second = e;
1151 if (!first)
1152 first = e;
1154 else if (!e->probability.initialized_p ())
1155 e->probability = profile_probability::never ();
1156 if (!e->probability.initialized_p ())
1157 nunknown++;
1158 else if (e->probability == profile_probability::never ())
1159 nzero++;
1162 /* When there is no successor or only one choice, prediction is easy.
1164 When we have a basic block with more than 2 successors, the situation
1165 is more complicated as DS theory cannot be used literally.
1166 More precisely, let's assume we predicted edge e1 with probability p1,
1167 thus: m1({b1}) = p1. As we're going to combine more than 2 edges, we
1168 need to find probability of e.g. m1({b2}), which we don't know.
1169 The only approximation is to equally distribute 1-p1 to all edges
1170 different from b1.
1172 According to numbers we've got from SPEC2006 benchark, there's only
1173 one interesting reliable predictor (noreturn call), which can be
1174 handled with a bit easier approach. */
1175 if (nedges != 2)
1177 hash_set<edge> unlikely_edges (4);
1179 /* Identify all edges that have a probability close to very unlikely.
1180 Doing the approach for very unlikely doesn't worth for doing as
1181 there's no such probability in SPEC2006 benchmark. */
1182 edge_prediction **preds = bb_predictions->get (bb);
1183 if (preds)
1184 for (pred = *preds; pred; pred = pred->ep_next)
1185 if (pred->ep_probability <= PROB_VERY_UNLIKELY)
1186 unlikely_edges.add (pred->ep_edge);
1188 if (!dry_run)
1189 set_even_probabilities (bb, &unlikely_edges);
1190 clear_bb_predictions (bb);
1191 if (dump_file)
1193 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1194 if (unlikely_edges.elements () == 0)
1195 fprintf (dump_file,
1196 "%i edges in bb %i predicted to even probabilities\n",
1197 nedges, bb->index);
1198 else
1200 fprintf (dump_file,
1201 "%i edges in bb %i predicted with some unlikely edges\n",
1202 nedges, bb->index);
1203 FOR_EACH_EDGE (e, ei, bb->succs)
1204 if (!unlikely_executed_edge_p (e))
1205 dump_prediction (dump_file, PRED_COMBINED,
1206 e->probability.to_reg_br_prob_base (), bb, REASON_NONE, e);
1209 return;
1212 if (dump_file)
1213 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1215 prune_predictions_for_bb (bb);
1217 edge_prediction **preds = bb_predictions->get (bb);
1219 if (preds)
1221 /* We implement "first match" heuristics and use probability guessed
1222 by predictor with smallest index. */
1223 for (pred = *preds; pred; pred = pred->ep_next)
1225 enum br_predictor predictor = pred->ep_predictor;
1226 int probability = pred->ep_probability;
1228 if (pred->ep_edge != first)
1229 probability = REG_BR_PROB_BASE - probability;
1231 found = true;
1232 /* First match heuristics would be widly confused if we predicted
1233 both directions. */
1234 if (best_predictor > predictor
1235 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1237 struct edge_prediction *pred2;
1238 int prob = probability;
1240 for (pred2 = (struct edge_prediction *) *preds;
1241 pred2; pred2 = pred2->ep_next)
1242 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1244 int probability2 = pred2->ep_probability;
1246 if (pred2->ep_edge != first)
1247 probability2 = REG_BR_PROB_BASE - probability2;
1249 if ((probability < REG_BR_PROB_BASE / 2) !=
1250 (probability2 < REG_BR_PROB_BASE / 2))
1251 break;
1253 /* If the same predictor later gave better result, go for it! */
1254 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1255 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1256 prob = probability2;
1258 if (!pred2)
1259 best_probability = prob, best_predictor = predictor;
1262 d = (combined_probability * probability
1263 + (REG_BR_PROB_BASE - combined_probability)
1264 * (REG_BR_PROB_BASE - probability));
1266 /* Use FP math to avoid overflows of 32bit integers. */
1267 if (d == 0)
1268 /* If one probability is 0% and one 100%, avoid division by zero. */
1269 combined_probability = REG_BR_PROB_BASE / 2;
1270 else
1271 combined_probability = (((double) combined_probability)
1272 * probability
1273 * REG_BR_PROB_BASE / d + 0.5);
1277 /* Decide which heuristic to use. In case we didn't match anything,
1278 use no_prediction heuristic, in case we did match, use either
1279 first match or Dempster-Shaffer theory depending on the flags. */
1281 if (best_predictor != END_PREDICTORS)
1282 first_match = true;
1284 if (!found)
1285 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1286 else
1288 if (!first_match)
1289 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1290 !first_match ? REASON_NONE : REASON_IGNORED);
1291 else
1292 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1293 first_match ? REASON_NONE : REASON_IGNORED);
1296 if (first_match)
1297 combined_probability = best_probability;
1298 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1300 if (preds)
1302 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1304 enum br_predictor predictor = pred->ep_predictor;
1305 int probability = pred->ep_probability;
1307 dump_prediction (dump_file, predictor, probability, bb,
1308 (!first_match || best_predictor == predictor)
1309 ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1312 clear_bb_predictions (bb);
1315 /* If we have only one successor which is unknown, we can compute missing
1316 probablity. */
1317 if (nunknown == 1)
1319 profile_probability prob = profile_probability::always ();
1320 edge missing = NULL;
1322 FOR_EACH_EDGE (e, ei, bb->succs)
1323 if (e->probability.initialized_p ())
1324 prob -= e->probability;
1325 else if (missing == NULL)
1326 missing = e;
1327 else
1328 gcc_unreachable ();
1329 missing->probability = prob;
1331 /* If nothing is unknown, we have nothing to update. */
1332 else if (!nunknown && nzero != (int)EDGE_COUNT (bb->succs))
1334 else if (!dry_run)
1336 first->probability
1337 = profile_probability::from_reg_br_prob_base (combined_probability);
1338 second->probability = first->probability.invert ();
1342 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1343 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1345 T1 and T2 should be one of the following cases:
1346 1. T1 is SSA_NAME, T2 is NULL
1347 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1348 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1350 static tree
1351 strips_small_constant (tree t1, tree t2)
1353 tree ret = NULL;
1354 int value = 0;
1356 if (!t1)
1357 return NULL;
1358 else if (TREE_CODE (t1) == SSA_NAME)
1359 ret = t1;
1360 else if (tree_fits_shwi_p (t1))
1361 value = tree_to_shwi (t1);
1362 else
1363 return NULL;
1365 if (!t2)
1366 return ret;
1367 else if (tree_fits_shwi_p (t2))
1368 value = tree_to_shwi (t2);
1369 else if (TREE_CODE (t2) == SSA_NAME)
1371 if (ret)
1372 return NULL;
1373 else
1374 ret = t2;
1377 if (value <= 4 && value >= -4)
1378 return ret;
1379 else
1380 return NULL;
1383 /* Return the SSA_NAME in T or T's operands.
1384 Return NULL if SSA_NAME cannot be found. */
1386 static tree
1387 get_base_value (tree t)
1389 if (TREE_CODE (t) == SSA_NAME)
1390 return t;
1392 if (!BINARY_CLASS_P (t))
1393 return NULL;
1395 switch (TREE_OPERAND_LENGTH (t))
1397 case 1:
1398 return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1399 case 2:
1400 return strips_small_constant (TREE_OPERAND (t, 0),
1401 TREE_OPERAND (t, 1));
1402 default:
1403 return NULL;
1407 /* Check the compare STMT in LOOP. If it compares an induction
1408 variable to a loop invariant, return true, and save
1409 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1410 Otherwise return false and set LOOP_INVAIANT to NULL. */
1412 static bool
1413 is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
1414 tree *loop_invariant,
1415 enum tree_code *compare_code,
1416 tree *loop_step,
1417 tree *loop_iv_base)
1419 tree op0, op1, bound, base;
1420 affine_iv iv0, iv1;
1421 enum tree_code code;
1422 tree step;
1424 code = gimple_cond_code (stmt);
1425 *loop_invariant = NULL;
1427 switch (code)
1429 case GT_EXPR:
1430 case GE_EXPR:
1431 case NE_EXPR:
1432 case LT_EXPR:
1433 case LE_EXPR:
1434 case EQ_EXPR:
1435 break;
1437 default:
1438 return false;
1441 op0 = gimple_cond_lhs (stmt);
1442 op1 = gimple_cond_rhs (stmt);
1444 if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1445 || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1446 return false;
1447 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1448 return false;
1449 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1450 return false;
1451 if (TREE_CODE (iv0.step) != INTEGER_CST
1452 || TREE_CODE (iv1.step) != INTEGER_CST)
1453 return false;
1454 if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1455 || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1456 return false;
1458 if (integer_zerop (iv0.step))
1460 if (code != NE_EXPR && code != EQ_EXPR)
1461 code = invert_tree_comparison (code, false);
1462 bound = iv0.base;
1463 base = iv1.base;
1464 if (tree_fits_shwi_p (iv1.step))
1465 step = iv1.step;
1466 else
1467 return false;
1469 else
1471 bound = iv1.base;
1472 base = iv0.base;
1473 if (tree_fits_shwi_p (iv0.step))
1474 step = iv0.step;
1475 else
1476 return false;
1479 if (TREE_CODE (bound) != INTEGER_CST)
1480 bound = get_base_value (bound);
1481 if (!bound)
1482 return false;
1483 if (TREE_CODE (base) != INTEGER_CST)
1484 base = get_base_value (base);
1485 if (!base)
1486 return false;
1488 *loop_invariant = bound;
1489 *compare_code = code;
1490 *loop_step = step;
1491 *loop_iv_base = base;
1492 return true;
1495 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1497 static bool
1498 expr_coherent_p (tree t1, tree t2)
1500 gimple *stmt;
1501 tree ssa_name_1 = NULL;
1502 tree ssa_name_2 = NULL;
1504 gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1505 gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1507 if (t1 == t2)
1508 return true;
1510 if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1511 return true;
1512 if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1513 return false;
1515 /* Check to see if t1 is expressed/defined with t2. */
1516 stmt = SSA_NAME_DEF_STMT (t1);
1517 gcc_assert (stmt != NULL);
1518 if (is_gimple_assign (stmt))
1520 ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1521 if (ssa_name_1 && ssa_name_1 == t2)
1522 return true;
1525 /* Check to see if t2 is expressed/defined with t1. */
1526 stmt = SSA_NAME_DEF_STMT (t2);
1527 gcc_assert (stmt != NULL);
1528 if (is_gimple_assign (stmt))
1530 ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1531 if (ssa_name_2 && ssa_name_2 == t1)
1532 return true;
1535 /* Compare if t1 and t2's def_stmts are identical. */
1536 if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1537 return true;
1538 else
1539 return false;
1542 /* Return true if E is predicted by one of loop heuristics. */
1544 static bool
1545 predicted_by_loop_heuristics_p (basic_block bb)
1547 struct edge_prediction *i;
1548 edge_prediction **preds = bb_predictions->get (bb);
1550 if (!preds)
1551 return false;
1553 for (i = *preds; i; i = i->ep_next)
1554 if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1555 || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1556 || i->ep_predictor == PRED_LOOP_ITERATIONS
1557 || i->ep_predictor == PRED_LOOP_EXIT
1558 || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1559 || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1560 return true;
1561 return false;
1564 /* Predict branch probability of BB when BB contains a branch that compares
1565 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1566 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1568 E.g.
1569 for (int i = 0; i < bound; i++) {
1570 if (i < bound - 2)
1571 computation_1();
1572 else
1573 computation_2();
1576 In this loop, we will predict the branch inside the loop to be taken. */
1578 static void
1579 predict_iv_comparison (struct loop *loop, basic_block bb,
1580 tree loop_bound_var,
1581 tree loop_iv_base_var,
1582 enum tree_code loop_bound_code,
1583 int loop_bound_step)
1585 gimple *stmt;
1586 tree compare_var, compare_base;
1587 enum tree_code compare_code;
1588 tree compare_step_var;
1589 edge then_edge;
1590 edge_iterator ei;
1592 if (predicted_by_loop_heuristics_p (bb))
1593 return;
1595 stmt = last_stmt (bb);
1596 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1597 return;
1598 if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
1599 loop, &compare_var,
1600 &compare_code,
1601 &compare_step_var,
1602 &compare_base))
1603 return;
1605 /* Find the taken edge. */
1606 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1607 if (then_edge->flags & EDGE_TRUE_VALUE)
1608 break;
1610 /* When comparing an IV to a loop invariant, NE is more likely to be
1611 taken while EQ is more likely to be not-taken. */
1612 if (compare_code == NE_EXPR)
1614 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1615 return;
1617 else if (compare_code == EQ_EXPR)
1619 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1620 return;
1623 if (!expr_coherent_p (loop_iv_base_var, compare_base))
1624 return;
1626 /* If loop bound, base and compare bound are all constants, we can
1627 calculate the probability directly. */
1628 if (tree_fits_shwi_p (loop_bound_var)
1629 && tree_fits_shwi_p (compare_var)
1630 && tree_fits_shwi_p (compare_base))
1632 int probability;
1633 wi::overflow_type overflow;
1634 bool overall_overflow = false;
1635 widest_int compare_count, tem;
1637 /* (loop_bound - base) / compare_step */
1638 tem = wi::sub (wi::to_widest (loop_bound_var),
1639 wi::to_widest (compare_base), SIGNED, &overflow);
1640 overall_overflow |= overflow;
1641 widest_int loop_count = wi::div_trunc (tem,
1642 wi::to_widest (compare_step_var),
1643 SIGNED, &overflow);
1644 overall_overflow |= overflow;
1646 if (!wi::neg_p (wi::to_widest (compare_step_var))
1647 ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1649 /* (loop_bound - compare_bound) / compare_step */
1650 tem = wi::sub (wi::to_widest (loop_bound_var),
1651 wi::to_widest (compare_var), SIGNED, &overflow);
1652 overall_overflow |= overflow;
1653 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1654 SIGNED, &overflow);
1655 overall_overflow |= overflow;
1657 else
1659 /* (compare_bound - base) / compare_step */
1660 tem = wi::sub (wi::to_widest (compare_var),
1661 wi::to_widest (compare_base), SIGNED, &overflow);
1662 overall_overflow |= overflow;
1663 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1664 SIGNED, &overflow);
1665 overall_overflow |= overflow;
1667 if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1668 ++compare_count;
1669 if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1670 ++loop_count;
1671 if (wi::neg_p (compare_count))
1672 compare_count = 0;
1673 if (wi::neg_p (loop_count))
1674 loop_count = 0;
1675 if (loop_count == 0)
1676 probability = 0;
1677 else if (wi::cmps (compare_count, loop_count) == 1)
1678 probability = REG_BR_PROB_BASE;
1679 else
1681 tem = compare_count * REG_BR_PROB_BASE;
1682 tem = wi::udiv_trunc (tem, loop_count);
1683 probability = tem.to_uhwi ();
1686 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1687 if (!overall_overflow)
1688 predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1690 return;
1693 if (expr_coherent_p (loop_bound_var, compare_var))
1695 if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1696 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1697 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1698 else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1699 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1700 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1701 else if (loop_bound_code == NE_EXPR)
1703 /* If the loop backedge condition is "(i != bound)", we do
1704 the comparison based on the step of IV:
1705 * step < 0 : backedge condition is like (i > bound)
1706 * step > 0 : backedge condition is like (i < bound) */
1707 gcc_assert (loop_bound_step != 0);
1708 if (loop_bound_step > 0
1709 && (compare_code == LT_EXPR
1710 || compare_code == LE_EXPR))
1711 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1712 else if (loop_bound_step < 0
1713 && (compare_code == GT_EXPR
1714 || compare_code == GE_EXPR))
1715 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1716 else
1717 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1719 else
1720 /* The branch is predicted not-taken if loop_bound_code is
1721 opposite with compare_code. */
1722 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1724 else if (expr_coherent_p (loop_iv_base_var, compare_var))
1726 /* For cases like:
1727 for (i = s; i < h; i++)
1728 if (i > s + 2) ....
1729 The branch should be predicted taken. */
1730 if (loop_bound_step > 0
1731 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1732 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1733 else if (loop_bound_step < 0
1734 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1735 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1736 else
1737 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1741 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1742 exits are resulted from short-circuit conditions that will generate an
1743 if_tmp. E.g.:
1745 if (foo() || global > 10)
1746 break;
1748 This will be translated into:
1750 BB3:
1751 loop header...
1752 BB4:
1753 if foo() goto BB6 else goto BB5
1754 BB5:
1755 if global > 10 goto BB6 else goto BB7
1756 BB6:
1757 goto BB7
1758 BB7:
1759 iftmp = (PHI 0(BB5), 1(BB6))
1760 if iftmp == 1 goto BB8 else goto BB3
1761 BB8:
1762 outside of the loop...
1764 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1765 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1766 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1767 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1769 static void
1770 predict_extra_loop_exits (edge exit_edge)
1772 unsigned i;
1773 bool check_value_one;
1774 gimple *lhs_def_stmt;
1775 gphi *phi_stmt;
1776 tree cmp_rhs, cmp_lhs;
1777 gimple *last;
1778 gcond *cmp_stmt;
1780 last = last_stmt (exit_edge->src);
1781 if (!last)
1782 return;
1783 cmp_stmt = dyn_cast <gcond *> (last);
1784 if (!cmp_stmt)
1785 return;
1787 cmp_rhs = gimple_cond_rhs (cmp_stmt);
1788 cmp_lhs = gimple_cond_lhs (cmp_stmt);
1789 if (!TREE_CONSTANT (cmp_rhs)
1790 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1791 return;
1792 if (TREE_CODE (cmp_lhs) != SSA_NAME)
1793 return;
1795 /* If check_value_one is true, only the phi_args with value '1' will lead
1796 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1797 loop exit. */
1798 check_value_one = (((integer_onep (cmp_rhs))
1799 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1800 ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1802 lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1803 if (!lhs_def_stmt)
1804 return;
1806 phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1807 if (!phi_stmt)
1808 return;
1810 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1812 edge e1;
1813 edge_iterator ei;
1814 tree val = gimple_phi_arg_def (phi_stmt, i);
1815 edge e = gimple_phi_arg_edge (phi_stmt, i);
1817 if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1818 continue;
1819 if ((check_value_one ^ integer_onep (val)) == 1)
1820 continue;
1821 if (EDGE_COUNT (e->src->succs) != 1)
1823 predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1824 continue;
1827 FOR_EACH_EDGE (e1, ei, e->src->preds)
1828 predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1833 /* Predict edge probabilities by exploiting loop structure. */
1835 static void
1836 predict_loops (void)
1838 struct loop *loop;
1839 basic_block bb;
1840 hash_set <struct loop *> with_recursion(10);
1842 FOR_EACH_BB_FN (bb, cfun)
1844 gimple_stmt_iterator gsi;
1845 tree decl;
1847 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1848 if (is_gimple_call (gsi_stmt (gsi))
1849 && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1850 && recursive_call_p (current_function_decl, decl))
1852 loop = bb->loop_father;
1853 while (loop && !with_recursion.add (loop))
1854 loop = loop_outer (loop);
1858 /* Try to predict out blocks in a loop that are not part of a
1859 natural loop. */
1860 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1862 basic_block bb, *bbs;
1863 unsigned j, n_exits = 0;
1864 vec<edge> exits;
1865 struct tree_niter_desc niter_desc;
1866 edge ex;
1867 struct nb_iter_bound *nb_iter;
1868 enum tree_code loop_bound_code = ERROR_MARK;
1869 tree loop_bound_step = NULL;
1870 tree loop_bound_var = NULL;
1871 tree loop_iv_base = NULL;
1872 gcond *stmt = NULL;
1873 bool recursion = with_recursion.contains (loop);
1875 exits = get_loop_exit_edges (loop);
1876 FOR_EACH_VEC_ELT (exits, j, ex)
1877 if (!unlikely_executed_edge_p (ex) && !(ex->flags & EDGE_ABNORMAL_CALL))
1878 n_exits ++;
1879 if (!n_exits)
1881 exits.release ();
1882 continue;
1885 if (dump_file && (dump_flags & TDF_DETAILS))
1886 fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
1887 loop->num, recursion ? " (with recursion)":"", n_exits);
1888 if (dump_file && (dump_flags & TDF_DETAILS)
1889 && max_loop_iterations_int (loop) >= 0)
1891 fprintf (dump_file,
1892 "Loop %d iterates at most %i times.\n", loop->num,
1893 (int)max_loop_iterations_int (loop));
1895 if (dump_file && (dump_flags & TDF_DETAILS)
1896 && likely_max_loop_iterations_int (loop) >= 0)
1898 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1899 loop->num, (int)likely_max_loop_iterations_int (loop));
1902 FOR_EACH_VEC_ELT (exits, j, ex)
1904 tree niter = NULL;
1905 HOST_WIDE_INT nitercst;
1906 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
1907 int probability;
1908 enum br_predictor predictor;
1909 widest_int nit;
1911 if (unlikely_executed_edge_p (ex)
1912 || (ex->flags & EDGE_ABNORMAL_CALL))
1913 continue;
1914 /* Loop heuristics do not expect exit conditional to be inside
1915 inner loop. We predict from innermost to outermost loop. */
1916 if (predicted_by_loop_heuristics_p (ex->src))
1918 if (dump_file && (dump_flags & TDF_DETAILS))
1919 fprintf (dump_file, "Skipping exit %i->%i because "
1920 "it is already predicted.\n",
1921 ex->src->index, ex->dest->index);
1922 continue;
1924 predict_extra_loop_exits (ex);
1926 if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
1927 niter = niter_desc.niter;
1928 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
1929 niter = loop_niter_by_eval (loop, ex);
1930 if (dump_file && (dump_flags & TDF_DETAILS)
1931 && TREE_CODE (niter) == INTEGER_CST)
1933 fprintf (dump_file, "Exit %i->%i %d iterates ",
1934 ex->src->index, ex->dest->index,
1935 loop->num);
1936 print_generic_expr (dump_file, niter, TDF_SLIM);
1937 fprintf (dump_file, " times.\n");
1940 if (TREE_CODE (niter) == INTEGER_CST)
1942 if (tree_fits_uhwi_p (niter)
1943 && max
1944 && compare_tree_int (niter, max - 1) == -1)
1945 nitercst = tree_to_uhwi (niter) + 1;
1946 else
1947 nitercst = max;
1948 predictor = PRED_LOOP_ITERATIONS;
1950 /* If we have just one exit and we can derive some information about
1951 the number of iterations of the loop from the statements inside
1952 the loop, use it to predict this exit. */
1953 else if (n_exits == 1
1954 && estimated_stmt_executions (loop, &nit))
1956 if (wi::gtu_p (nit, max))
1957 nitercst = max;
1958 else
1959 nitercst = nit.to_shwi ();
1960 predictor = PRED_LOOP_ITERATIONS_GUESSED;
1962 /* If we have likely upper bound, trust it for very small iteration
1963 counts. Such loops would otherwise get mispredicted by standard
1964 LOOP_EXIT heuristics. */
1965 else if (n_exits == 1
1966 && likely_max_stmt_executions (loop, &nit)
1967 && wi::ltu_p (nit,
1968 RDIV (REG_BR_PROB_BASE,
1969 REG_BR_PROB_BASE
1970 - predictor_info
1971 [recursion
1972 ? PRED_LOOP_EXIT_WITH_RECURSION
1973 : PRED_LOOP_EXIT].hitrate)))
1975 nitercst = nit.to_shwi ();
1976 predictor = PRED_LOOP_ITERATIONS_MAX;
1978 else
1980 if (dump_file && (dump_flags & TDF_DETAILS))
1981 fprintf (dump_file, "Nothing known about exit %i->%i.\n",
1982 ex->src->index, ex->dest->index);
1983 continue;
1986 if (dump_file && (dump_flags & TDF_DETAILS))
1987 fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
1988 (int)nitercst, predictor_info[predictor].name);
1989 /* If the prediction for number of iterations is zero, do not
1990 predict the exit edges. */
1991 if (nitercst == 0)
1992 continue;
1994 probability = RDIV (REG_BR_PROB_BASE, nitercst);
1995 predict_edge (ex, predictor, probability);
1997 exits.release ();
1999 /* Find information about loop bound variables. */
2000 for (nb_iter = loop->bounds; nb_iter;
2001 nb_iter = nb_iter->next)
2002 if (nb_iter->stmt
2003 && gimple_code (nb_iter->stmt) == GIMPLE_COND)
2005 stmt = as_a <gcond *> (nb_iter->stmt);
2006 break;
2008 if (!stmt && last_stmt (loop->header)
2009 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
2010 stmt = as_a <gcond *> (last_stmt (loop->header));
2011 if (stmt)
2012 is_comparison_with_loop_invariant_p (stmt, loop,
2013 &loop_bound_var,
2014 &loop_bound_code,
2015 &loop_bound_step,
2016 &loop_iv_base);
2018 bbs = get_loop_body (loop);
2020 for (j = 0; j < loop->num_nodes; j++)
2022 edge e;
2023 edge_iterator ei;
2025 bb = bbs[j];
2027 /* Bypass loop heuristics on continue statement. These
2028 statements construct loops via "non-loop" constructs
2029 in the source language and are better to be handled
2030 separately. */
2031 if (predicted_by_p (bb, PRED_CONTINUE))
2033 if (dump_file && (dump_flags & TDF_DETAILS))
2034 fprintf (dump_file, "BB %i predicted by continue.\n",
2035 bb->index);
2036 continue;
2039 /* If we already used more reliable loop exit predictors, do not
2040 bother with PRED_LOOP_EXIT. */
2041 if (!predicted_by_loop_heuristics_p (bb))
2043 /* For loop with many exits we don't want to predict all exits
2044 with the pretty large probability, because if all exits are
2045 considered in row, the loop would be predicted to iterate
2046 almost never. The code to divide probability by number of
2047 exits is very rough. It should compute the number of exits
2048 taken in each patch through function (not the overall number
2049 of exits that might be a lot higher for loops with wide switch
2050 statements in them) and compute n-th square root.
2052 We limit the minimal probability by 2% to avoid
2053 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
2054 as this was causing regression in perl benchmark containing such
2055 a wide loop. */
2057 int probability = ((REG_BR_PROB_BASE
2058 - predictor_info
2059 [recursion
2060 ? PRED_LOOP_EXIT_WITH_RECURSION
2061 : PRED_LOOP_EXIT].hitrate)
2062 / n_exits);
2063 if (probability < HITRATE (2))
2064 probability = HITRATE (2);
2065 FOR_EACH_EDGE (e, ei, bb->succs)
2066 if (e->dest->index < NUM_FIXED_BLOCKS
2067 || !flow_bb_inside_loop_p (loop, e->dest))
2069 if (dump_file && (dump_flags & TDF_DETAILS))
2070 fprintf (dump_file,
2071 "Predicting exit %i->%i with prob %i.\n",
2072 e->src->index, e->dest->index, probability);
2073 predict_edge (e,
2074 recursion ? PRED_LOOP_EXIT_WITH_RECURSION
2075 : PRED_LOOP_EXIT, probability);
2078 if (loop_bound_var)
2079 predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
2080 loop_bound_code,
2081 tree_to_shwi (loop_bound_step));
2084 /* In the following code
2085 for (loop1)
2086 if (cond)
2087 for (loop2)
2088 body;
2089 guess that cond is unlikely. */
2090 if (loop_outer (loop)->num)
2092 basic_block bb = NULL;
2093 edge preheader_edge = loop_preheader_edge (loop);
2095 if (single_pred_p (preheader_edge->src)
2096 && single_succ_p (preheader_edge->src))
2097 preheader_edge = single_pred_edge (preheader_edge->src);
2099 gimple *stmt = last_stmt (preheader_edge->src);
2100 /* Pattern match fortran loop preheader:
2101 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
2102 _17 = (logical(kind=4)) _16;
2103 if (_17 != 0)
2104 goto <bb 11>;
2105 else
2106 goto <bb 13>;
2108 Loop guard branch prediction says nothing about duplicated loop
2109 headers produced by fortran frontend and in this case we want
2110 to predict paths leading to this preheader. */
2112 if (stmt
2113 && gimple_code (stmt) == GIMPLE_COND
2114 && gimple_cond_code (stmt) == NE_EXPR
2115 && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
2116 && integer_zerop (gimple_cond_rhs (stmt)))
2118 gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2119 if (gimple_code (call_stmt) == GIMPLE_ASSIGN
2120 && gimple_expr_code (call_stmt) == NOP_EXPR
2121 && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
2122 call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
2123 if (gimple_call_internal_p (call_stmt, IFN_BUILTIN_EXPECT)
2124 && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
2125 && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
2126 && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
2127 == PRED_FORTRAN_LOOP_PREHEADER)
2128 bb = preheader_edge->src;
2130 if (!bb)
2132 if (!dominated_by_p (CDI_DOMINATORS,
2133 loop_outer (loop)->latch, loop->header))
2134 predict_paths_leading_to_edge (loop_preheader_edge (loop),
2135 recursion
2136 ? PRED_LOOP_GUARD_WITH_RECURSION
2137 : PRED_LOOP_GUARD,
2138 NOT_TAKEN,
2139 loop_outer (loop));
2141 else
2143 if (!dominated_by_p (CDI_DOMINATORS,
2144 loop_outer (loop)->latch, bb))
2145 predict_paths_leading_to (bb,
2146 recursion
2147 ? PRED_LOOP_GUARD_WITH_RECURSION
2148 : PRED_LOOP_GUARD,
2149 NOT_TAKEN,
2150 loop_outer (loop));
2154 /* Free basic blocks from get_loop_body. */
2155 free (bbs);
2159 /* Attempt to predict probabilities of BB outgoing edges using local
2160 properties. */
2161 static void
2162 bb_estimate_probability_locally (basic_block bb)
2164 rtx_insn *last_insn = BB_END (bb);
2165 rtx cond;
2167 if (! can_predict_insn_p (last_insn))
2168 return;
2169 cond = get_condition (last_insn, NULL, false, false);
2170 if (! cond)
2171 return;
2173 /* Try "pointer heuristic."
2174 A comparison ptr == 0 is predicted as false.
2175 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2176 if (COMPARISON_P (cond)
2177 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2178 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2180 if (GET_CODE (cond) == EQ)
2181 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2182 else if (GET_CODE (cond) == NE)
2183 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2185 else
2187 /* Try "opcode heuristic."
2188 EQ tests are usually false and NE tests are usually true. Also,
2189 most quantities are positive, so we can make the appropriate guesses
2190 about signed comparisons against zero. */
2191 switch (GET_CODE (cond))
2193 case CONST_INT:
2194 /* Unconditional branch. */
2195 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2196 cond == const0_rtx ? NOT_TAKEN : TAKEN);
2197 break;
2199 case EQ:
2200 case UNEQ:
2201 /* Floating point comparisons appears to behave in a very
2202 unpredictable way because of special role of = tests in
2203 FP code. */
2204 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2206 /* Comparisons with 0 are often used for booleans and there is
2207 nothing useful to predict about them. */
2208 else if (XEXP (cond, 1) == const0_rtx
2209 || XEXP (cond, 0) == const0_rtx)
2211 else
2212 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2213 break;
2215 case NE:
2216 case LTGT:
2217 /* Floating point comparisons appears to behave in a very
2218 unpredictable way because of special role of = tests in
2219 FP code. */
2220 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2222 /* Comparisons with 0 are often used for booleans and there is
2223 nothing useful to predict about them. */
2224 else if (XEXP (cond, 1) == const0_rtx
2225 || XEXP (cond, 0) == const0_rtx)
2227 else
2228 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2229 break;
2231 case ORDERED:
2232 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2233 break;
2235 case UNORDERED:
2236 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2237 break;
2239 case LE:
2240 case LT:
2241 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2242 || XEXP (cond, 1) == constm1_rtx)
2243 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2244 break;
2246 case GE:
2247 case GT:
2248 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2249 || XEXP (cond, 1) == constm1_rtx)
2250 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2251 break;
2253 default:
2254 break;
2258 /* Set edge->probability for each successor edge of BB. */
2259 void
2260 guess_outgoing_edge_probabilities (basic_block bb)
2262 bb_estimate_probability_locally (bb);
2263 combine_predictions_for_insn (BB_END (bb), bb);
2266 static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor,
2267 HOST_WIDE_INT *probability);
2269 /* Helper function for expr_expected_value. */
2271 static tree
2272 expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2273 tree op1, bitmap visited, enum br_predictor *predictor,
2274 HOST_WIDE_INT *probability)
2276 gimple *def;
2278 /* Reset returned probability value. */
2279 *probability = -1;
2280 *predictor = PRED_UNCONDITIONAL;
2282 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2284 if (TREE_CONSTANT (op0))
2285 return op0;
2287 if (code == IMAGPART_EXPR)
2289 if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2291 def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2292 if (is_gimple_call (def)
2293 && gimple_call_internal_p (def)
2294 && (gimple_call_internal_fn (def)
2295 == IFN_ATOMIC_COMPARE_EXCHANGE))
2297 /* Assume that any given atomic operation has low contention,
2298 and thus the compare-and-swap operation succeeds. */
2299 *predictor = PRED_COMPARE_AND_SWAP;
2300 return build_one_cst (TREE_TYPE (op0));
2305 if (code != SSA_NAME)
2306 return NULL_TREE;
2308 def = SSA_NAME_DEF_STMT (op0);
2310 /* If we were already here, break the infinite cycle. */
2311 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
2312 return NULL;
2314 if (gimple_code (def) == GIMPLE_PHI)
2316 /* All the arguments of the PHI node must have the same constant
2317 length. */
2318 int i, n = gimple_phi_num_args (def);
2319 tree val = NULL, new_val;
2321 for (i = 0; i < n; i++)
2323 tree arg = PHI_ARG_DEF (def, i);
2324 enum br_predictor predictor2;
2326 /* If this PHI has itself as an argument, we cannot
2327 determine the string length of this argument. However,
2328 if we can find an expected constant value for the other
2329 PHI args then we can still be sure that this is
2330 likely a constant. So be optimistic and just
2331 continue with the next argument. */
2332 if (arg == PHI_RESULT (def))
2333 continue;
2335 new_val = expr_expected_value (arg, visited, &predictor2,
2336 probability);
2338 /* It is difficult to combine value predictors. Simply assume
2339 that later predictor is weaker and take its prediction. */
2340 if (*predictor < predictor2)
2341 *predictor = predictor2;
2342 if (!new_val)
2343 return NULL;
2344 if (!val)
2345 val = new_val;
2346 else if (!operand_equal_p (val, new_val, false))
2347 return NULL;
2349 return val;
2351 if (is_gimple_assign (def))
2353 if (gimple_assign_lhs (def) != op0)
2354 return NULL;
2356 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2357 gimple_assign_rhs1 (def),
2358 gimple_assign_rhs_code (def),
2359 gimple_assign_rhs2 (def),
2360 visited, predictor, probability);
2363 if (is_gimple_call (def))
2365 tree decl = gimple_call_fndecl (def);
2366 if (!decl)
2368 if (gimple_call_internal_p (def)
2369 && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2371 gcc_assert (gimple_call_num_args (def) == 3);
2372 tree val = gimple_call_arg (def, 0);
2373 if (TREE_CONSTANT (val))
2374 return val;
2375 tree val2 = gimple_call_arg (def, 2);
2376 gcc_assert (TREE_CODE (val2) == INTEGER_CST
2377 && tree_fits_uhwi_p (val2)
2378 && tree_to_uhwi (val2) < END_PREDICTORS);
2379 *predictor = (enum br_predictor) tree_to_uhwi (val2);
2380 if (*predictor == PRED_BUILTIN_EXPECT)
2381 *probability
2382 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY));
2383 return gimple_call_arg (def, 1);
2385 return NULL;
2388 if (DECL_IS_MALLOC (decl) || DECL_IS_OPERATOR_NEW (decl))
2390 if (predictor)
2391 *predictor = PRED_MALLOC_NONNULL;
2392 return boolean_true_node;
2395 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2396 switch (DECL_FUNCTION_CODE (decl))
2398 case BUILT_IN_EXPECT:
2400 tree val;
2401 if (gimple_call_num_args (def) != 2)
2402 return NULL;
2403 val = gimple_call_arg (def, 0);
2404 if (TREE_CONSTANT (val))
2405 return val;
2406 *predictor = PRED_BUILTIN_EXPECT;
2407 *probability
2408 = HITRATE (PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY));
2409 return gimple_call_arg (def, 1);
2411 case BUILT_IN_EXPECT_WITH_PROBABILITY:
2413 tree val;
2414 if (gimple_call_num_args (def) != 3)
2415 return NULL;
2416 val = gimple_call_arg (def, 0);
2417 if (TREE_CONSTANT (val))
2418 return val;
2419 /* Compute final probability as:
2420 probability * REG_BR_PROB_BASE. */
2421 tree prob = gimple_call_arg (def, 2);
2422 tree t = TREE_TYPE (prob);
2423 tree base = build_int_cst (integer_type_node,
2424 REG_BR_PROB_BASE);
2425 base = build_real_from_int_cst (t, base);
2426 tree r = fold_build2 (MULT_EXPR, t, prob, base);
2427 HOST_WIDE_INT probi
2428 = real_to_integer (TREE_REAL_CST_PTR (r));
2429 if (probi >= 0 && probi <= REG_BR_PROB_BASE)
2431 *predictor = PRED_BUILTIN_EXPECT_WITH_PROBABILITY;
2432 *probability = probi;
2434 return gimple_call_arg (def, 1);
2437 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2438 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2439 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2440 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2441 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2442 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2443 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2444 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2445 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2446 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2447 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2448 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2449 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2450 /* Assume that any given atomic operation has low contention,
2451 and thus the compare-and-swap operation succeeds. */
2452 *predictor = PRED_COMPARE_AND_SWAP;
2453 return boolean_true_node;
2454 case BUILT_IN_REALLOC:
2455 if (predictor)
2456 *predictor = PRED_MALLOC_NONNULL;
2457 return boolean_true_node;
2458 default:
2459 break;
2463 return NULL;
2466 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2468 tree res;
2469 enum br_predictor predictor2;
2470 HOST_WIDE_INT probability2;
2471 op0 = expr_expected_value (op0, visited, predictor, probability);
2472 if (!op0)
2473 return NULL;
2474 op1 = expr_expected_value (op1, visited, &predictor2, &probability2);
2475 if (!op1)
2476 return NULL;
2477 res = fold_build2 (code, type, op0, op1);
2478 if (TREE_CODE (res) == INTEGER_CST
2479 && TREE_CODE (op0) == INTEGER_CST
2480 && TREE_CODE (op1) == INTEGER_CST)
2482 /* Combine binary predictions. */
2483 if (*probability != -1 || probability2 != -1)
2485 HOST_WIDE_INT p1 = get_predictor_value (*predictor, *probability);
2486 HOST_WIDE_INT p2 = get_predictor_value (predictor2, probability2);
2487 *probability = RDIV (p1 * p2, REG_BR_PROB_BASE);
2490 if (*predictor < predictor2)
2491 *predictor = predictor2;
2493 return res;
2495 return NULL;
2497 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2499 tree res;
2500 op0 = expr_expected_value (op0, visited, predictor, probability);
2501 if (!op0)
2502 return NULL;
2503 res = fold_build1 (code, type, op0);
2504 if (TREE_CONSTANT (res))
2505 return res;
2506 return NULL;
2508 return NULL;
2511 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2512 The function is used by builtin_expect branch predictor so the evidence
2513 must come from this construct and additional possible constant folding.
2515 We may want to implement more involved value guess (such as value range
2516 propagation based prediction), but such tricks shall go to new
2517 implementation. */
2519 static tree
2520 expr_expected_value (tree expr, bitmap visited,
2521 enum br_predictor *predictor,
2522 HOST_WIDE_INT *probability)
2524 enum tree_code code;
2525 tree op0, op1;
2527 if (TREE_CONSTANT (expr))
2529 *predictor = PRED_UNCONDITIONAL;
2530 *probability = -1;
2531 return expr;
2534 extract_ops_from_tree (expr, &code, &op0, &op1);
2535 return expr_expected_value_1 (TREE_TYPE (expr),
2536 op0, code, op1, visited, predictor,
2537 probability);
2541 /* Return probability of a PREDICTOR. If the predictor has variable
2542 probability return passed PROBABILITY. */
2544 static HOST_WIDE_INT
2545 get_predictor_value (br_predictor predictor, HOST_WIDE_INT probability)
2547 switch (predictor)
2549 case PRED_BUILTIN_EXPECT:
2550 case PRED_BUILTIN_EXPECT_WITH_PROBABILITY:
2551 gcc_assert (probability != -1);
2552 return probability;
2553 default:
2554 gcc_assert (probability == -1);
2555 return predictor_info[(int) predictor].hitrate;
2559 /* Predict using opcode of the last statement in basic block. */
2560 static void
2561 tree_predict_by_opcode (basic_block bb)
2563 gimple *stmt = last_stmt (bb);
2564 edge then_edge;
2565 tree op0, op1;
2566 tree type;
2567 tree val;
2568 enum tree_code cmp;
2569 edge_iterator ei;
2570 enum br_predictor predictor;
2571 HOST_WIDE_INT probability;
2573 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
2574 return;
2575 FOR_EACH_EDGE (then_edge, ei, bb->succs)
2576 if (then_edge->flags & EDGE_TRUE_VALUE)
2577 break;
2578 op0 = gimple_cond_lhs (stmt);
2579 op1 = gimple_cond_rhs (stmt);
2580 cmp = gimple_cond_code (stmt);
2581 type = TREE_TYPE (op0);
2582 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, auto_bitmap (),
2583 &predictor, &probability);
2584 if (val && TREE_CODE (val) == INTEGER_CST)
2586 HOST_WIDE_INT prob = get_predictor_value (predictor, probability);
2587 if (integer_zerop (val))
2588 prob = REG_BR_PROB_BASE - prob;
2589 predict_edge (then_edge, predictor, prob);
2591 /* Try "pointer heuristic."
2592 A comparison ptr == 0 is predicted as false.
2593 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2594 if (POINTER_TYPE_P (type))
2596 if (cmp == EQ_EXPR)
2597 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2598 else if (cmp == NE_EXPR)
2599 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2601 else
2603 /* Try "opcode heuristic."
2604 EQ tests are usually false and NE tests are usually true. Also,
2605 most quantities are positive, so we can make the appropriate guesses
2606 about signed comparisons against zero. */
2607 switch (cmp)
2609 case EQ_EXPR:
2610 case UNEQ_EXPR:
2611 /* Floating point comparisons appears to behave in a very
2612 unpredictable way because of special role of = tests in
2613 FP code. */
2614 if (FLOAT_TYPE_P (type))
2616 /* Comparisons with 0 are often used for booleans and there is
2617 nothing useful to predict about them. */
2618 else if (integer_zerop (op0) || integer_zerop (op1))
2620 else
2621 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2622 break;
2624 case NE_EXPR:
2625 case LTGT_EXPR:
2626 /* Floating point comparisons appears to behave in a very
2627 unpredictable way because of special role of = tests in
2628 FP code. */
2629 if (FLOAT_TYPE_P (type))
2631 /* Comparisons with 0 are often used for booleans and there is
2632 nothing useful to predict about them. */
2633 else if (integer_zerop (op0)
2634 || integer_zerop (op1))
2636 else
2637 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2638 break;
2640 case ORDERED_EXPR:
2641 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2642 break;
2644 case UNORDERED_EXPR:
2645 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2646 break;
2648 case LE_EXPR:
2649 case LT_EXPR:
2650 if (integer_zerop (op1)
2651 || integer_onep (op1)
2652 || integer_all_onesp (op1)
2653 || real_zerop (op1)
2654 || real_onep (op1)
2655 || real_minus_onep (op1))
2656 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2657 break;
2659 case GE_EXPR:
2660 case GT_EXPR:
2661 if (integer_zerop (op1)
2662 || integer_onep (op1)
2663 || integer_all_onesp (op1)
2664 || real_zerop (op1)
2665 || real_onep (op1)
2666 || real_minus_onep (op1))
2667 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2668 break;
2670 default:
2671 break;
2675 /* Returns TRUE if the STMT is exit(0) like statement. */
2677 static bool
2678 is_exit_with_zero_arg (const gimple *stmt)
2680 /* This is not exit, _exit or _Exit. */
2681 if (!gimple_call_builtin_p (stmt, BUILT_IN_EXIT)
2682 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT)
2683 && !gimple_call_builtin_p (stmt, BUILT_IN__EXIT2))
2684 return false;
2686 /* Argument is an interger zero. */
2687 return integer_zerop (gimple_call_arg (stmt, 0));
2690 /* Try to guess whether the value of return means error code. */
2692 static enum br_predictor
2693 return_prediction (tree val, enum prediction *prediction)
2695 /* VOID. */
2696 if (!val)
2697 return PRED_NO_PREDICTION;
2698 /* Different heuristics for pointers and scalars. */
2699 if (POINTER_TYPE_P (TREE_TYPE (val)))
2701 /* NULL is usually not returned. */
2702 if (integer_zerop (val))
2704 *prediction = NOT_TAKEN;
2705 return PRED_NULL_RETURN;
2708 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2710 /* Negative return values are often used to indicate
2711 errors. */
2712 if (TREE_CODE (val) == INTEGER_CST
2713 && tree_int_cst_sgn (val) < 0)
2715 *prediction = NOT_TAKEN;
2716 return PRED_NEGATIVE_RETURN;
2718 /* Constant return values seems to be commonly taken.
2719 Zero/one often represent booleans so exclude them from the
2720 heuristics. */
2721 if (TREE_CONSTANT (val)
2722 && (!integer_zerop (val) && !integer_onep (val)))
2724 *prediction = NOT_TAKEN;
2725 return PRED_CONST_RETURN;
2728 return PRED_NO_PREDICTION;
2731 /* Return zero if phi result could have values other than -1, 0 or 1,
2732 otherwise return a bitmask, with bits 0, 1 and 2 set if -1, 0 and 1
2733 values are used or likely. */
2735 static int
2736 zero_one_minusone (gphi *phi, int limit)
2738 int phi_num_args = gimple_phi_num_args (phi);
2739 int ret = 0;
2740 for (int i = 0; i < phi_num_args; i++)
2742 tree t = PHI_ARG_DEF (phi, i);
2743 if (TREE_CODE (t) != INTEGER_CST)
2744 continue;
2745 wide_int w = wi::to_wide (t);
2746 if (w == -1)
2747 ret |= 1;
2748 else if (w == 0)
2749 ret |= 2;
2750 else if (w == 1)
2751 ret |= 4;
2752 else
2753 return 0;
2755 for (int i = 0; i < phi_num_args; i++)
2757 tree t = PHI_ARG_DEF (phi, i);
2758 if (TREE_CODE (t) == INTEGER_CST)
2759 continue;
2760 if (TREE_CODE (t) != SSA_NAME)
2761 return 0;
2762 gimple *g = SSA_NAME_DEF_STMT (t);
2763 if (gimple_code (g) == GIMPLE_PHI && limit > 0)
2764 if (int r = zero_one_minusone (as_a <gphi *> (g), limit - 1))
2766 ret |= r;
2767 continue;
2769 if (!is_gimple_assign (g))
2770 return 0;
2771 if (gimple_assign_cast_p (g))
2773 tree rhs1 = gimple_assign_rhs1 (g);
2774 if (TREE_CODE (rhs1) != SSA_NAME
2775 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
2776 || TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2777 || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2778 return 0;
2779 ret |= (2 | 4);
2780 continue;
2782 if (TREE_CODE_CLASS (gimple_assign_rhs_code (g)) != tcc_comparison)
2783 return 0;
2784 ret |= (2 | 4);
2786 return ret;
2789 /* Find the basic block with return expression and look up for possible
2790 return value trying to apply RETURN_PREDICTION heuristics. */
2791 static void
2792 apply_return_prediction (void)
2794 greturn *return_stmt = NULL;
2795 tree return_val;
2796 edge e;
2797 gphi *phi;
2798 int phi_num_args, i;
2799 enum br_predictor pred;
2800 enum prediction direction;
2801 edge_iterator ei;
2803 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2805 gimple *last = last_stmt (e->src);
2806 if (last
2807 && gimple_code (last) == GIMPLE_RETURN)
2809 return_stmt = as_a <greturn *> (last);
2810 break;
2813 if (!e)
2814 return;
2815 return_val = gimple_return_retval (return_stmt);
2816 if (!return_val)
2817 return;
2818 if (TREE_CODE (return_val) != SSA_NAME
2819 || !SSA_NAME_DEF_STMT (return_val)
2820 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2821 return;
2822 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2823 phi_num_args = gimple_phi_num_args (phi);
2824 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
2826 /* Avoid the case where the function returns -1, 0 and 1 values and
2827 nothing else. Those could be qsort etc. comparison functions
2828 where the negative return isn't less probable than positive.
2829 For this require that the function returns at least -1 or 1
2830 or -1 and a boolean value or comparison result, so that functions
2831 returning just -1 and 0 are treated as if -1 represents error value. */
2832 if (INTEGRAL_TYPE_P (TREE_TYPE (return_val))
2833 && !TYPE_UNSIGNED (TREE_TYPE (return_val))
2834 && TYPE_PRECISION (TREE_TYPE (return_val)) > 1)
2835 if (int r = zero_one_minusone (phi, 3))
2836 if ((r & (1 | 4)) == (1 | 4))
2837 return;
2839 /* Avoid the degenerate case where all return values form the function
2840 belongs to same category (ie they are all positive constants)
2841 so we can hardly say something about them. */
2842 for (i = 1; i < phi_num_args; i++)
2843 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
2844 break;
2845 if (i != phi_num_args)
2846 for (i = 0; i < phi_num_args; i++)
2848 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
2849 if (pred != PRED_NO_PREDICTION)
2850 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
2851 direction);
2855 /* Look for basic block that contains unlikely to happen events
2856 (such as noreturn calls) and mark all paths leading to execution
2857 of this basic blocks as unlikely. */
2859 static void
2860 tree_bb_level_predictions (void)
2862 basic_block bb;
2863 bool has_return_edges = false;
2864 edge e;
2865 edge_iterator ei;
2867 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2868 if (!unlikely_executed_edge_p (e) && !(e->flags & EDGE_ABNORMAL_CALL))
2870 has_return_edges = true;
2871 break;
2874 apply_return_prediction ();
2876 FOR_EACH_BB_FN (bb, cfun)
2878 gimple_stmt_iterator gsi;
2880 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2882 gimple *stmt = gsi_stmt (gsi);
2883 tree decl;
2885 if (is_gimple_call (stmt))
2887 if (gimple_call_noreturn_p (stmt)
2888 && has_return_edges
2889 && !is_exit_with_zero_arg (stmt))
2890 predict_paths_leading_to (bb, PRED_NORETURN,
2891 NOT_TAKEN);
2892 decl = gimple_call_fndecl (stmt);
2893 if (decl
2894 && lookup_attribute ("cold",
2895 DECL_ATTRIBUTES (decl)))
2896 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
2897 NOT_TAKEN);
2898 if (decl && recursive_call_p (current_function_decl, decl))
2899 predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
2900 NOT_TAKEN);
2902 else if (gimple_code (stmt) == GIMPLE_PREDICT)
2904 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
2905 gimple_predict_outcome (stmt));
2906 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2907 hints to callers. */
2913 /* Callback for hash_map::traverse, asserts that the pointer map is
2914 empty. */
2916 bool
2917 assert_is_empty (const_basic_block const &, edge_prediction *const &value,
2918 void *)
2920 gcc_assert (!value);
2921 return false;
2924 /* Predict branch probabilities and estimate profile for basic block BB.
2925 When LOCAL_ONLY is set do not use any global properties of CFG. */
2927 static void
2928 tree_estimate_probability_bb (basic_block bb, bool local_only)
2930 edge e;
2931 edge_iterator ei;
2933 FOR_EACH_EDGE (e, ei, bb->succs)
2935 /* Look for block we are guarding (ie we dominate it,
2936 but it doesn't postdominate us). */
2937 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
2938 && !local_only
2939 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
2940 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
2942 gimple_stmt_iterator bi;
2944 /* The call heuristic claims that a guarded function call
2945 is improbable. This is because such calls are often used
2946 to signal exceptional situations such as printing error
2947 messages. */
2948 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
2949 gsi_next (&bi))
2951 gimple *stmt = gsi_stmt (bi);
2952 if (is_gimple_call (stmt)
2953 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
2954 /* Constant and pure calls are hardly used to signalize
2955 something exceptional. */
2956 && gimple_has_side_effects (stmt))
2958 if (gimple_call_fndecl (stmt))
2959 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
2960 else if (virtual_method_call_p (gimple_call_fn (stmt)))
2961 predict_edge_def (e, PRED_POLYMORPHIC_CALL, NOT_TAKEN);
2962 else
2963 predict_edge_def (e, PRED_INDIR_CALL, TAKEN);
2964 break;
2969 tree_predict_by_opcode (bb);
2972 /* Predict branch probabilities and estimate profile of the tree CFG.
2973 This function can be called from the loop optimizers to recompute
2974 the profile information.
2975 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2977 void
2978 tree_estimate_probability (bool dry_run)
2980 basic_block bb;
2982 add_noreturn_fake_exit_edges ();
2983 connect_infinite_loops_to_exit ();
2984 /* We use loop_niter_by_eval, which requires that the loops have
2985 preheaders. */
2986 create_preheaders (CP_SIMPLE_PREHEADERS);
2987 calculate_dominance_info (CDI_POST_DOMINATORS);
2989 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2990 tree_bb_level_predictions ();
2991 record_loop_exits ();
2993 if (number_of_loops (cfun) > 1)
2994 predict_loops ();
2996 FOR_EACH_BB_FN (bb, cfun)
2997 tree_estimate_probability_bb (bb, false);
2999 FOR_EACH_BB_FN (bb, cfun)
3000 combine_predictions_for_bb (bb, dry_run);
3002 if (flag_checking)
3003 bb_predictions->traverse<void *, assert_is_empty> (NULL);
3005 delete bb_predictions;
3006 bb_predictions = NULL;
3008 if (!dry_run)
3009 estimate_bb_frequencies (false);
3010 free_dominance_info (CDI_POST_DOMINATORS);
3011 remove_fake_exit_edges ();
3014 /* Set edge->probability for each successor edge of BB. */
3015 void
3016 tree_guess_outgoing_edge_probabilities (basic_block bb)
3018 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
3019 tree_estimate_probability_bb (bb, true);
3020 combine_predictions_for_bb (bb, false);
3021 if (flag_checking)
3022 bb_predictions->traverse<void *, assert_is_empty> (NULL);
3023 delete bb_predictions;
3024 bb_predictions = NULL;
3027 /* Predict edges to successors of CUR whose sources are not postdominated by
3028 BB by PRED and recurse to all postdominators. */
3030 static void
3031 predict_paths_for_bb (basic_block cur, basic_block bb,
3032 enum br_predictor pred,
3033 enum prediction taken,
3034 bitmap visited, struct loop *in_loop = NULL)
3036 edge e;
3037 edge_iterator ei;
3038 basic_block son;
3040 /* If we exited the loop or CUR is unconditional in the loop, there is
3041 nothing to do. */
3042 if (in_loop
3043 && (!flow_bb_inside_loop_p (in_loop, cur)
3044 || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
3045 return;
3047 /* We are looking for all edges forming edge cut induced by
3048 set of all blocks postdominated by BB. */
3049 FOR_EACH_EDGE (e, ei, cur->preds)
3050 if (e->src->index >= NUM_FIXED_BLOCKS
3051 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
3053 edge e2;
3054 edge_iterator ei2;
3055 bool found = false;
3057 /* Ignore fake edges and eh, we predict them as not taken anyway. */
3058 if (unlikely_executed_edge_p (e))
3059 continue;
3060 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
3062 /* See if there is an edge from e->src that is not abnormal
3063 and does not lead to BB and does not exit the loop. */
3064 FOR_EACH_EDGE (e2, ei2, e->src->succs)
3065 if (e2 != e
3066 && !unlikely_executed_edge_p (e2)
3067 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
3068 && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
3070 found = true;
3071 break;
3074 /* If there is non-abnormal path leaving e->src, predict edge
3075 using predictor. Otherwise we need to look for paths
3076 leading to e->src.
3078 The second may lead to infinite loop in the case we are predicitng
3079 regions that are only reachable by abnormal edges. We simply
3080 prevent visiting given BB twice. */
3081 if (found)
3083 if (!edge_predicted_by_p (e, pred, taken))
3084 predict_edge_def (e, pred, taken);
3086 else if (bitmap_set_bit (visited, e->src->index))
3087 predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
3089 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
3090 son;
3091 son = next_dom_son (CDI_POST_DOMINATORS, son))
3092 predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
3095 /* Sets branch probabilities according to PREDiction and
3096 FLAGS. */
3098 static void
3099 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
3100 enum prediction taken, struct loop *in_loop)
3102 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3105 /* Like predict_paths_leading_to but take edge instead of basic block. */
3107 static void
3108 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
3109 enum prediction taken, struct loop *in_loop)
3111 bool has_nonloop_edge = false;
3112 edge_iterator ei;
3113 edge e2;
3115 basic_block bb = e->src;
3116 FOR_EACH_EDGE (e2, ei, bb->succs)
3117 if (e2->dest != e->src && e2->dest != e->dest
3118 && !unlikely_executed_edge_p (e)
3119 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
3121 has_nonloop_edge = true;
3122 break;
3124 if (!has_nonloop_edge)
3126 predict_paths_for_bb (bb, bb, pred, taken, auto_bitmap (), in_loop);
3128 else
3129 predict_edge_def (e, pred, taken);
3132 /* This is used to carry information about basic blocks. It is
3133 attached to the AUX field of the standard CFG block. */
3135 struct block_info
3137 /* Estimated frequency of execution of basic_block. */
3138 sreal frequency;
3140 /* To keep queue of basic blocks to process. */
3141 basic_block next;
3143 /* Number of predecessors we need to visit first. */
3144 int npredecessors;
3147 /* Similar information for edges. */
3148 struct edge_prob_info
3150 /* In case edge is a loopback edge, the probability edge will be reached
3151 in case header is. Estimated number of iterations of the loop can be
3152 then computed as 1 / (1 - back_edge_prob). */
3153 sreal back_edge_prob;
3154 /* True if the edge is a loopback edge in the natural loop. */
3155 unsigned int back_edge:1;
3158 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
3159 #undef EDGE_INFO
3160 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
3162 /* Helper function for estimate_bb_frequencies.
3163 Propagate the frequencies in blocks marked in
3164 TOVISIT, starting in HEAD. */
3166 static void
3167 propagate_freq (basic_block head, bitmap tovisit)
3169 basic_block bb;
3170 basic_block last;
3171 unsigned i;
3172 edge e;
3173 basic_block nextbb;
3174 bitmap_iterator bi;
3176 /* For each basic block we need to visit count number of his predecessors
3177 we need to visit first. */
3178 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
3180 edge_iterator ei;
3181 int count = 0;
3183 bb = BASIC_BLOCK_FOR_FN (cfun, i);
3185 FOR_EACH_EDGE (e, ei, bb->preds)
3187 bool visit = bitmap_bit_p (tovisit, e->src->index);
3189 if (visit && !(e->flags & EDGE_DFS_BACK))
3190 count++;
3191 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
3192 fprintf (dump_file,
3193 "Irreducible region hit, ignoring edge to %i->%i\n",
3194 e->src->index, bb->index);
3196 BLOCK_INFO (bb)->npredecessors = count;
3197 /* When function never returns, we will never process exit block. */
3198 if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
3199 bb->count = profile_count::zero ();
3202 BLOCK_INFO (head)->frequency = 1;
3203 last = head;
3204 for (bb = head; bb; bb = nextbb)
3206 edge_iterator ei;
3207 sreal cyclic_probability = 0;
3208 sreal frequency = 0;
3210 nextbb = BLOCK_INFO (bb)->next;
3211 BLOCK_INFO (bb)->next = NULL;
3213 /* Compute frequency of basic block. */
3214 if (bb != head)
3216 if (flag_checking)
3217 FOR_EACH_EDGE (e, ei, bb->preds)
3218 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
3219 || (e->flags & EDGE_DFS_BACK));
3221 FOR_EACH_EDGE (e, ei, bb->preds)
3222 if (EDGE_INFO (e)->back_edge)
3224 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
3226 else if (!(e->flags & EDGE_DFS_BACK))
3228 /* frequency += (e->probability
3229 * BLOCK_INFO (e->src)->frequency /
3230 REG_BR_PROB_BASE); */
3232 /* FIXME: Graphite is producing edges with no profile. Once
3233 this is fixed, drop this. */
3234 sreal tmp = e->probability.initialized_p () ?
3235 e->probability.to_reg_br_prob_base () : 0;
3236 tmp *= BLOCK_INFO (e->src)->frequency;
3237 tmp *= real_inv_br_prob_base;
3238 frequency += tmp;
3241 if (cyclic_probability == 0)
3243 BLOCK_INFO (bb)->frequency = frequency;
3245 else
3247 if (cyclic_probability > real_almost_one)
3248 cyclic_probability = real_almost_one;
3250 /* BLOCK_INFO (bb)->frequency = frequency
3251 / (1 - cyclic_probability) */
3253 cyclic_probability = sreal (1) - cyclic_probability;
3254 BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
3258 bitmap_clear_bit (tovisit, bb->index);
3260 e = find_edge (bb, head);
3261 if (e)
3263 /* EDGE_INFO (e)->back_edge_prob
3264 = ((e->probability * BLOCK_INFO (bb)->frequency)
3265 / REG_BR_PROB_BASE); */
3267 /* FIXME: Graphite is producing edges with no profile. Once
3268 this is fixed, drop this. */
3269 sreal tmp = e->probability.initialized_p () ?
3270 e->probability.to_reg_br_prob_base () : 0;
3271 tmp *= BLOCK_INFO (bb)->frequency;
3272 EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
3275 /* Propagate to successor blocks. */
3276 FOR_EACH_EDGE (e, ei, bb->succs)
3277 if (!(e->flags & EDGE_DFS_BACK)
3278 && BLOCK_INFO (e->dest)->npredecessors)
3280 BLOCK_INFO (e->dest)->npredecessors--;
3281 if (!BLOCK_INFO (e->dest)->npredecessors)
3283 if (!nextbb)
3284 nextbb = e->dest;
3285 else
3286 BLOCK_INFO (last)->next = e->dest;
3288 last = e->dest;
3294 /* Estimate frequencies in loops at same nest level. */
3296 static void
3297 estimate_loops_at_level (struct loop *first_loop)
3299 struct loop *loop;
3301 for (loop = first_loop; loop; loop = loop->next)
3303 edge e;
3304 basic_block *bbs;
3305 unsigned i;
3306 auto_bitmap tovisit;
3308 estimate_loops_at_level (loop->inner);
3310 /* Find current loop back edge and mark it. */
3311 e = loop_latch_edge (loop);
3312 EDGE_INFO (e)->back_edge = 1;
3314 bbs = get_loop_body (loop);
3315 for (i = 0; i < loop->num_nodes; i++)
3316 bitmap_set_bit (tovisit, bbs[i]->index);
3317 free (bbs);
3318 propagate_freq (loop->header, tovisit);
3322 /* Propagates frequencies through structure of loops. */
3324 static void
3325 estimate_loops (void)
3327 auto_bitmap tovisit;
3328 basic_block bb;
3330 /* Start by estimating the frequencies in the loops. */
3331 if (number_of_loops (cfun) > 1)
3332 estimate_loops_at_level (current_loops->tree_root->inner);
3334 /* Now propagate the frequencies through all the blocks. */
3335 FOR_ALL_BB_FN (bb, cfun)
3337 bitmap_set_bit (tovisit, bb->index);
3339 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
3342 /* Drop the profile for NODE to guessed, and update its frequency based on
3343 whether it is expected to be hot given the CALL_COUNT. */
3345 static void
3346 drop_profile (struct cgraph_node *node, profile_count call_count)
3348 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3349 /* In the case where this was called by another function with a
3350 dropped profile, call_count will be 0. Since there are no
3351 non-zero call counts to this function, we don't know for sure
3352 whether it is hot, and therefore it will be marked normal below. */
3353 bool hot = maybe_hot_count_p (NULL, call_count);
3355 if (dump_file)
3356 fprintf (dump_file,
3357 "Dropping 0 profile for %s. %s based on calls.\n",
3358 node->dump_name (),
3359 hot ? "Function is hot" : "Function is normal");
3360 /* We only expect to miss profiles for functions that are reached
3361 via non-zero call edges in cases where the function may have
3362 been linked from another module or library (COMDATs and extern
3363 templates). See the comments below for handle_missing_profiles.
3364 Also, only warn in cases where the missing counts exceed the
3365 number of training runs. In certain cases with an execv followed
3366 by a no-return call the profile for the no-return call is not
3367 dumped and there can be a mismatch. */
3368 if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3369 && call_count > profile_info->runs)
3371 if (flag_profile_correction)
3373 if (dump_file)
3374 fprintf (dump_file,
3375 "Missing counts for called function %s\n",
3376 node->dump_name ());
3378 else
3379 warning (0, "Missing counts for called function %s",
3380 node->dump_name ());
3383 basic_block bb;
3384 if (opt_for_fn (node->decl, flag_guess_branch_prob))
3386 bool clear_zeros
3387 = !ENTRY_BLOCK_PTR_FOR_FN (fn)->count.nonzero_p ();
3388 FOR_ALL_BB_FN (bb, fn)
3389 if (clear_zeros || !(bb->count == profile_count::zero ()))
3390 bb->count = bb->count.guessed_local ();
3391 fn->cfg->count_max = fn->cfg->count_max.guessed_local ();
3393 else
3395 FOR_ALL_BB_FN (bb, fn)
3396 bb->count = profile_count::uninitialized ();
3397 fn->cfg->count_max = profile_count::uninitialized ();
3400 struct cgraph_edge *e;
3401 for (e = node->callees; e; e = e->next_callee)
3402 e->count = gimple_bb (e->call_stmt)->count;
3403 for (e = node->indirect_calls; e; e = e->next_callee)
3404 e->count = gimple_bb (e->call_stmt)->count;
3405 node->count = ENTRY_BLOCK_PTR_FOR_FN (fn)->count;
3407 profile_status_for_fn (fn)
3408 = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3409 node->frequency
3410 = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3413 /* In the case of COMDAT routines, multiple object files will contain the same
3414 function and the linker will select one for the binary. In that case
3415 all the other copies from the profile instrument binary will be missing
3416 profile counts. Look for cases where this happened, due to non-zero
3417 call counts going to 0-count functions, and drop the profile to guessed
3418 so that we can use the estimated probabilities and avoid optimizing only
3419 for size.
3421 The other case where the profile may be missing is when the routine
3422 is not going to be emitted to the object file, e.g. for "extern template"
3423 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3424 all other cases of non-zero calls to 0-count functions. */
3426 void
3427 handle_missing_profiles (void)
3429 struct cgraph_node *node;
3430 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
3431 auto_vec<struct cgraph_node *, 64> worklist;
3433 /* See if 0 count function has non-0 count callers. In this case we
3434 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3435 FOR_EACH_DEFINED_FUNCTION (node)
3437 struct cgraph_edge *e;
3438 profile_count call_count = profile_count::zero ();
3439 gcov_type max_tp_first_run = 0;
3440 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3442 if (node->count.ipa ().nonzero_p ())
3443 continue;
3444 for (e = node->callers; e; e = e->next_caller)
3445 if (e->count.ipa ().initialized_p () && e->count.ipa () > 0)
3447 call_count = call_count + e->count.ipa ();
3449 if (e->caller->tp_first_run > max_tp_first_run)
3450 max_tp_first_run = e->caller->tp_first_run;
3453 /* If time profile is missing, let assign the maximum that comes from
3454 caller functions. */
3455 if (!node->tp_first_run && max_tp_first_run)
3456 node->tp_first_run = max_tp_first_run + 1;
3458 if (call_count > 0
3459 && fn && fn->cfg
3460 && (call_count.apply_scale (unlikely_count_fraction, 1)
3461 >= profile_info->runs))
3463 drop_profile (node, call_count);
3464 worklist.safe_push (node);
3468 /* Propagate the profile dropping to other 0-count COMDATs that are
3469 potentially called by COMDATs we already dropped the profile on. */
3470 while (worklist.length () > 0)
3472 struct cgraph_edge *e;
3474 node = worklist.pop ();
3475 for (e = node->callees; e; e = e->next_caller)
3477 struct cgraph_node *callee = e->callee;
3478 struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3480 if (!(e->count.ipa () == profile_count::zero ())
3481 && callee->count.ipa ().nonzero_p ())
3482 continue;
3483 if ((DECL_COMDAT (callee->decl) || DECL_EXTERNAL (callee->decl))
3484 && fn && fn->cfg
3485 && profile_status_for_fn (fn) == PROFILE_READ)
3487 drop_profile (node, profile_count::zero ());
3488 worklist.safe_push (callee);
3494 /* Convert counts measured by profile driven feedback to frequencies.
3495 Return nonzero iff there was any nonzero execution count. */
3497 bool
3498 update_max_bb_count (void)
3500 profile_count true_count_max = profile_count::uninitialized ();
3501 basic_block bb;
3503 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3504 true_count_max = true_count_max.max (bb->count);
3506 cfun->cfg->count_max = true_count_max;
3508 return true_count_max.ipa ().nonzero_p ();
3511 /* Return true if function is likely to be expensive, so there is no point to
3512 optimize performance of prologue, epilogue or do inlining at the expense
3513 of code size growth. THRESHOLD is the limit of number of instructions
3514 function can execute at average to be still considered not expensive. */
3516 bool
3517 expensive_function_p (int threshold)
3519 basic_block bb;
3521 /* If profile was scaled in a way entry block has count 0, then the function
3522 is deifnitly taking a lot of time. */
3523 if (!ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.nonzero_p ())
3524 return true;
3526 profile_count limit = ENTRY_BLOCK_PTR_FOR_FN
3527 (cfun)->count.apply_scale (threshold, 1);
3528 profile_count sum = profile_count::zero ();
3529 FOR_EACH_BB_FN (bb, cfun)
3531 rtx_insn *insn;
3533 if (!bb->count.initialized_p ())
3535 if (dump_file)
3536 fprintf (dump_file, "Function is considered expensive because"
3537 " count of bb %i is not initialized\n", bb->index);
3538 return true;
3541 FOR_BB_INSNS (bb, insn)
3542 if (active_insn_p (insn))
3544 sum += bb->count;
3545 if (sum > limit)
3546 return true;
3550 return false;
3553 /* All basic blocks that are reachable only from unlikely basic blocks are
3554 unlikely. */
3556 void
3557 propagate_unlikely_bbs_forward (void)
3559 auto_vec<basic_block, 64> worklist;
3560 basic_block bb;
3561 edge_iterator ei;
3562 edge e;
3564 if (!(ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ()))
3566 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(size_t) 1;
3567 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3569 while (worklist.length () > 0)
3571 bb = worklist.pop ();
3572 FOR_EACH_EDGE (e, ei, bb->succs)
3573 if (!(e->count () == profile_count::zero ())
3574 && !(e->dest->count == profile_count::zero ())
3575 && !e->dest->aux)
3577 e->dest->aux = (void *)(size_t) 1;
3578 worklist.safe_push (e->dest);
3583 FOR_ALL_BB_FN (bb, cfun)
3585 if (!bb->aux)
3587 if (!(bb->count == profile_count::zero ())
3588 && (dump_file && (dump_flags & TDF_DETAILS)))
3589 fprintf (dump_file,
3590 "Basic block %i is marked unlikely by forward prop\n",
3591 bb->index);
3592 bb->count = profile_count::zero ();
3594 else
3595 bb->aux = NULL;
3599 /* Determine basic blocks/edges that are known to be unlikely executed and set
3600 their counters to zero.
3601 This is done with first identifying obviously unlikely BBs/edges and then
3602 propagating in both directions. */
3604 static void
3605 determine_unlikely_bbs ()
3607 basic_block bb;
3608 auto_vec<basic_block, 64> worklist;
3609 edge_iterator ei;
3610 edge e;
3612 FOR_EACH_BB_FN (bb, cfun)
3614 if (!(bb->count == profile_count::zero ())
3615 && unlikely_executed_bb_p (bb))
3617 if (dump_file && (dump_flags & TDF_DETAILS))
3618 fprintf (dump_file, "Basic block %i is locally unlikely\n",
3619 bb->index);
3620 bb->count = profile_count::zero ();
3623 FOR_EACH_EDGE (e, ei, bb->succs)
3624 if (!(e->probability == profile_probability::never ())
3625 && unlikely_executed_edge_p (e))
3627 if (dump_file && (dump_flags & TDF_DETAILS))
3628 fprintf (dump_file, "Edge %i->%i is locally unlikely\n",
3629 bb->index, e->dest->index);
3630 e->probability = profile_probability::never ();
3633 gcc_checking_assert (!bb->aux);
3635 propagate_unlikely_bbs_forward ();
3637 auto_vec<int, 64> nsuccs;
3638 nsuccs.safe_grow_cleared (last_basic_block_for_fn (cfun));
3639 FOR_ALL_BB_FN (bb, cfun)
3640 if (!(bb->count == profile_count::zero ())
3641 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3643 nsuccs[bb->index] = 0;
3644 FOR_EACH_EDGE (e, ei, bb->succs)
3645 if (!(e->probability == profile_probability::never ())
3646 && !(e->dest->count == profile_count::zero ()))
3647 nsuccs[bb->index]++;
3648 if (!nsuccs[bb->index])
3649 worklist.safe_push (bb);
3651 while (worklist.length () > 0)
3653 bb = worklist.pop ();
3654 if (bb->count == profile_count::zero ())
3655 continue;
3656 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
3658 bool found = false;
3659 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
3660 !gsi_end_p (gsi); gsi_next (&gsi))
3661 if (stmt_can_terminate_bb_p (gsi_stmt (gsi))
3662 /* stmt_can_terminate_bb_p special cases noreturns because it
3663 assumes that fake edges are created. We want to know that
3664 noreturn alone does not imply BB to be unlikely. */
3665 || (is_gimple_call (gsi_stmt (gsi))
3666 && (gimple_call_flags (gsi_stmt (gsi)) & ECF_NORETURN)))
3668 found = true;
3669 break;
3671 if (found)
3672 continue;
3674 if (dump_file && (dump_flags & TDF_DETAILS))
3675 fprintf (dump_file,
3676 "Basic block %i is marked unlikely by backward prop\n",
3677 bb->index);
3678 bb->count = profile_count::zero ();
3679 FOR_EACH_EDGE (e, ei, bb->preds)
3680 if (!(e->probability == profile_probability::never ()))
3682 if (!(e->src->count == profile_count::zero ()))
3684 gcc_checking_assert (nsuccs[e->src->index] > 0);
3685 nsuccs[e->src->index]--;
3686 if (!nsuccs[e->src->index])
3687 worklist.safe_push (e->src);
3691 /* Finally all edges from non-0 regions to 0 are unlikely. */
3692 FOR_ALL_BB_FN (bb, cfun)
3693 if (!(bb->count == profile_count::zero ()))
3694 FOR_EACH_EDGE (e, ei, bb->succs)
3695 if (!(e->probability == profile_probability::never ())
3696 && e->dest->count == profile_count::zero ())
3698 if (dump_file && (dump_flags & TDF_DETAILS))
3699 fprintf (dump_file, "Edge %i->%i is unlikely because "
3700 "it enters unlikely block\n",
3701 bb->index, e->dest->index);
3702 e->probability = profile_probability::never ();
3704 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count == profile_count::zero ())
3705 cgraph_node::get (current_function_decl)->count = profile_count::zero ();
3708 /* Estimate and propagate basic block frequencies using the given branch
3709 probabilities. If FORCE is true, the frequencies are used to estimate
3710 the counts even when there are already non-zero profile counts. */
3712 void
3713 estimate_bb_frequencies (bool force)
3715 basic_block bb;
3716 sreal freq_max;
3718 determine_unlikely_bbs ();
3720 if (force || profile_status_for_fn (cfun) != PROFILE_READ
3721 || !update_max_bb_count ())
3723 static int real_values_initialized = 0;
3725 if (!real_values_initialized)
3727 real_values_initialized = 1;
3728 real_br_prob_base = REG_BR_PROB_BASE;
3729 /* Scaling frequencies up to maximal profile count may result in
3730 frequent overflows especially when inlining loops.
3731 Small scalling results in unnecesary precision loss. Stay in
3732 the half of the (exponential) range. */
3733 real_bb_freq_max = (uint64_t)1 << (profile_count::n_bits / 2);
3734 real_one_half = sreal (1, -1);
3735 real_inv_br_prob_base = sreal (1) / real_br_prob_base;
3736 real_almost_one = sreal (1) - real_inv_br_prob_base;
3739 mark_dfs_back_edges ();
3741 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
3742 profile_probability::always ();
3744 /* Set up block info for each basic block. */
3745 alloc_aux_for_blocks (sizeof (block_info));
3746 alloc_aux_for_edges (sizeof (edge_prob_info));
3747 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3749 edge e;
3750 edge_iterator ei;
3752 FOR_EACH_EDGE (e, ei, bb->succs)
3754 /* FIXME: Graphite is producing edges with no profile. Once
3755 this is fixed, drop this. */
3756 if (e->probability.initialized_p ())
3757 EDGE_INFO (e)->back_edge_prob
3758 = e->probability.to_reg_br_prob_base ();
3759 else
3760 EDGE_INFO (e)->back_edge_prob = REG_BR_PROB_BASE / 2;
3761 EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
3765 /* First compute frequencies locally for each loop from innermost
3766 to outermost to examine frequencies for back edges. */
3767 estimate_loops ();
3769 freq_max = 0;
3770 FOR_EACH_BB_FN (bb, cfun)
3771 if (freq_max < BLOCK_INFO (bb)->frequency)
3772 freq_max = BLOCK_INFO (bb)->frequency;
3774 freq_max = real_bb_freq_max / freq_max;
3775 if (freq_max < 16)
3776 freq_max = 16;
3777 profile_count ipa_count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ();
3778 cfun->cfg->count_max = profile_count::uninitialized ();
3779 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3781 sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
3782 profile_count count = profile_count::from_gcov_type (tmp.to_int ());
3784 /* If we have profile feedback in which this function was never
3785 executed, then preserve this info. */
3786 if (!(bb->count == profile_count::zero ()))
3787 bb->count = count.guessed_local ().combine_with_ipa_count (ipa_count);
3788 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
3791 free_aux_for_blocks ();
3792 free_aux_for_edges ();
3794 compute_function_frequency ();
3797 /* Decide whether function is hot, cold or unlikely executed. */
3798 void
3799 compute_function_frequency (void)
3801 basic_block bb;
3802 struct cgraph_node *node = cgraph_node::get (current_function_decl);
3804 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3805 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
3806 node->only_called_at_startup = true;
3807 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
3808 node->only_called_at_exit = true;
3810 if (profile_status_for_fn (cfun) != PROFILE_READ)
3812 int flags = flags_from_decl_or_type (current_function_decl);
3813 if ((ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa_p ()
3814 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3815 || lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
3816 != NULL)
3818 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3819 warn_function_cold (current_function_decl);
3821 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
3822 != NULL)
3823 node->frequency = NODE_FREQUENCY_HOT;
3824 else if (flags & ECF_NORETURN)
3825 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3826 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
3827 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3828 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3829 || DECL_STATIC_DESTRUCTOR (current_function_decl))
3830 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3831 return;
3834 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3835 warn_function_cold (current_function_decl);
3836 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa() == profile_count::zero ())
3837 return;
3838 FOR_EACH_BB_FN (bb, cfun)
3840 if (maybe_hot_bb_p (cfun, bb))
3842 node->frequency = NODE_FREQUENCY_HOT;
3843 return;
3845 if (!probably_never_executed_bb_p (cfun, bb))
3846 node->frequency = NODE_FREQUENCY_NORMAL;
3850 /* Build PREDICT_EXPR. */
3851 tree
3852 build_predict_expr (enum br_predictor predictor, enum prediction taken)
3854 tree t = build1 (PREDICT_EXPR, void_type_node,
3855 build_int_cst (integer_type_node, predictor));
3856 SET_PREDICT_EXPR_OUTCOME (t, taken);
3857 return t;
3860 const char *
3861 predictor_name (enum br_predictor predictor)
3863 return predictor_info[predictor].name;
3866 /* Predict branch probabilities and estimate profile of the tree CFG. */
3868 namespace {
3870 const pass_data pass_data_profile =
3872 GIMPLE_PASS, /* type */
3873 "profile_estimate", /* name */
3874 OPTGROUP_NONE, /* optinfo_flags */
3875 TV_BRANCH_PROB, /* tv_id */
3876 PROP_cfg, /* properties_required */
3877 0, /* properties_provided */
3878 0, /* properties_destroyed */
3879 0, /* todo_flags_start */
3880 0, /* todo_flags_finish */
3883 class pass_profile : public gimple_opt_pass
3885 public:
3886 pass_profile (gcc::context *ctxt)
3887 : gimple_opt_pass (pass_data_profile, ctxt)
3890 /* opt_pass methods: */
3891 virtual bool gate (function *) { return flag_guess_branch_prob; }
3892 virtual unsigned int execute (function *);
3894 }; // class pass_profile
3896 unsigned int
3897 pass_profile::execute (function *fun)
3899 unsigned nb_loops;
3901 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3902 return 0;
3904 loop_optimizer_init (LOOPS_NORMAL);
3905 if (dump_file && (dump_flags & TDF_DETAILS))
3906 flow_loops_dump (dump_file, NULL, 0);
3908 mark_irreducible_loops ();
3910 nb_loops = number_of_loops (fun);
3911 if (nb_loops > 1)
3912 scev_initialize ();
3914 tree_estimate_probability (false);
3916 if (nb_loops > 1)
3917 scev_finalize ();
3919 loop_optimizer_finalize ();
3920 if (dump_file && (dump_flags & TDF_DETAILS))
3921 gimple_dump_cfg (dump_file, dump_flags);
3922 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
3923 profile_status_for_fn (fun) = PROFILE_GUESSED;
3924 if (dump_file && (dump_flags & TDF_DETAILS))
3926 struct loop *loop;
3927 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3928 if (loop->header->count.initialized_p ())
3929 fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
3930 loop->num,
3931 (int)expected_loop_iterations_unbounded (loop));
3933 return 0;
3936 } // anon namespace
3938 gimple_opt_pass *
3939 make_pass_profile (gcc::context *ctxt)
3941 return new pass_profile (ctxt);
3944 /* Return true when PRED predictor should be removed after early
3945 tree passes. Most of the predictors are beneficial to survive
3946 as early inlining can also distribute then into caller's bodies. */
3948 static bool
3949 strip_predictor_early (enum br_predictor pred)
3951 switch (pred)
3953 case PRED_TREE_EARLY_RETURN:
3954 return true;
3955 default:
3956 return false;
3960 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3961 we no longer need. EARLY is set to true when called from early
3962 optimizations. */
3964 unsigned int
3965 strip_predict_hints (function *fun, bool early)
3967 basic_block bb;
3968 gimple *ass_stmt;
3969 tree var;
3970 bool changed = false;
3972 FOR_EACH_BB_FN (bb, fun)
3974 gimple_stmt_iterator bi;
3975 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
3977 gimple *stmt = gsi_stmt (bi);
3979 if (gimple_code (stmt) == GIMPLE_PREDICT)
3981 if (!early
3982 || strip_predictor_early (gimple_predict_predictor (stmt)))
3984 gsi_remove (&bi, true);
3985 changed = true;
3986 continue;
3989 else if (is_gimple_call (stmt))
3991 tree fndecl = gimple_call_fndecl (stmt);
3993 if (!early
3994 && ((DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL, BUILT_IN_EXPECT)
3995 && gimple_call_num_args (stmt) == 2)
3996 || (DECL_BUILT_IN_P (fndecl, BUILT_IN_NORMAL,
3997 BUILT_IN_EXPECT_WITH_PROBABILITY)
3998 && gimple_call_num_args (stmt) == 3)
3999 || (gimple_call_internal_p (stmt)
4000 && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT)))
4002 var = gimple_call_lhs (stmt);
4003 changed = true;
4004 if (var)
4006 ass_stmt
4007 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
4008 gsi_replace (&bi, ass_stmt, true);
4010 else
4012 gsi_remove (&bi, true);
4013 continue;
4017 gsi_next (&bi);
4020 return changed ? TODO_cleanup_cfg : 0;
4023 namespace {
4025 const pass_data pass_data_strip_predict_hints =
4027 GIMPLE_PASS, /* type */
4028 "*strip_predict_hints", /* name */
4029 OPTGROUP_NONE, /* optinfo_flags */
4030 TV_BRANCH_PROB, /* tv_id */
4031 PROP_cfg, /* properties_required */
4032 0, /* properties_provided */
4033 0, /* properties_destroyed */
4034 0, /* todo_flags_start */
4035 0, /* todo_flags_finish */
4038 class pass_strip_predict_hints : public gimple_opt_pass
4040 public:
4041 pass_strip_predict_hints (gcc::context *ctxt)
4042 : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
4045 /* opt_pass methods: */
4046 opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
4047 void set_pass_param (unsigned int n, bool param)
4049 gcc_assert (n == 0);
4050 early_p = param;
4053 virtual unsigned int execute (function *);
4055 private:
4056 bool early_p;
4058 }; // class pass_strip_predict_hints
4060 unsigned int
4061 pass_strip_predict_hints::execute (function *fun)
4063 return strip_predict_hints (fun, early_p);
4066 } // anon namespace
4068 gimple_opt_pass *
4069 make_pass_strip_predict_hints (gcc::context *ctxt)
4071 return new pass_strip_predict_hints (ctxt);
4074 /* Rebuild function frequencies. Passes are in general expected to
4075 maintain profile by hand, however in some cases this is not possible:
4076 for example when inlining several functions with loops freuqencies might run
4077 out of scale and thus needs to be recomputed. */
4079 void
4080 rebuild_frequencies (void)
4082 timevar_push (TV_REBUILD_FREQUENCIES);
4084 /* When the max bb count in the function is small, there is a higher
4085 chance that there were truncation errors in the integer scaling
4086 of counts by inlining and other optimizations. This could lead
4087 to incorrect classification of code as being cold when it isn't.
4088 In that case, force the estimation of bb counts/frequencies from the
4089 branch probabilities, rather than computing frequencies from counts,
4090 which may also lead to frequencies incorrectly reduced to 0. There
4091 is less precision in the probabilities, so we only do this for small
4092 max counts. */
4093 cfun->cfg->count_max = profile_count::uninitialized ();
4094 basic_block bb;
4095 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
4096 cfun->cfg->count_max = cfun->cfg->count_max.max (bb->count);
4098 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
4100 loop_optimizer_init (0);
4101 add_noreturn_fake_exit_edges ();
4102 mark_irreducible_loops ();
4103 connect_infinite_loops_to_exit ();
4104 estimate_bb_frequencies (true);
4105 remove_fake_exit_edges ();
4106 loop_optimizer_finalize ();
4108 else if (profile_status_for_fn (cfun) == PROFILE_READ)
4109 update_max_bb_count ();
4110 else if (profile_status_for_fn (cfun) == PROFILE_ABSENT
4111 && !flag_guess_branch_prob)
4113 else
4114 gcc_unreachable ();
4115 timevar_pop (TV_REBUILD_FREQUENCIES);
4118 /* Perform a dry run of the branch prediction pass and report comparsion of
4119 the predicted and real profile into the dump file. */
4121 void
4122 report_predictor_hitrates (void)
4124 unsigned nb_loops;
4126 loop_optimizer_init (LOOPS_NORMAL);
4127 if (dump_file && (dump_flags & TDF_DETAILS))
4128 flow_loops_dump (dump_file, NULL, 0);
4130 mark_irreducible_loops ();
4132 nb_loops = number_of_loops (cfun);
4133 if (nb_loops > 1)
4134 scev_initialize ();
4136 tree_estimate_probability (true);
4138 if (nb_loops > 1)
4139 scev_finalize ();
4141 loop_optimizer_finalize ();
4144 /* Force edge E to be cold.
4145 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
4146 keep low probability to represent possible error in a guess. This is used
4147 i.e. in case we predict loop to likely iterate given number of times but
4148 we are not 100% sure.
4150 This function locally updates profile without attempt to keep global
4151 consistency which can not be reached in full generality without full profile
4152 rebuild from probabilities alone. Doing so is not necessarily a good idea
4153 because frequencies and counts may be more realistic then probabilities.
4155 In some cases (such as for elimination of early exits during full loop
4156 unrolling) the caller can ensure that profile will get consistent
4157 afterwards. */
4159 void
4160 force_edge_cold (edge e, bool impossible)
4162 profile_count count_sum = profile_count::zero ();
4163 profile_probability prob_sum = profile_probability::never ();
4164 edge_iterator ei;
4165 edge e2;
4166 bool uninitialized_exit = false;
4168 /* When branch probability guesses are not known, then do nothing. */
4169 if (!impossible && !e->count ().initialized_p ())
4170 return;
4172 profile_probability goal = (impossible ? profile_probability::never ()
4173 : profile_probability::very_unlikely ());
4175 /* If edge is already improbably or cold, just return. */
4176 if (e->probability <= goal
4177 && (!impossible || e->count () == profile_count::zero ()))
4178 return;
4179 FOR_EACH_EDGE (e2, ei, e->src->succs)
4180 if (e2 != e)
4182 if (e->flags & EDGE_FAKE)
4183 continue;
4184 if (e2->count ().initialized_p ())
4185 count_sum += e2->count ();
4186 if (e2->probability.initialized_p ())
4187 prob_sum += e2->probability;
4188 else
4189 uninitialized_exit = true;
4192 /* If we are not guessing profiles but have some other edges out,
4193 just assume the control flow goes elsewhere. */
4194 if (uninitialized_exit)
4195 e->probability = goal;
4196 /* If there are other edges out of e->src, redistribute probabilitity
4197 there. */
4198 else if (prob_sum > profile_probability::never ())
4200 if (!(e->probability < goal))
4201 e->probability = goal;
4203 profile_probability prob_comp = prob_sum / e->probability.invert ();
4205 if (dump_file && (dump_flags & TDF_DETAILS))
4206 fprintf (dump_file, "Making edge %i->%i %s by redistributing "
4207 "probability to other edges.\n",
4208 e->src->index, e->dest->index,
4209 impossible ? "impossible" : "cold");
4210 FOR_EACH_EDGE (e2, ei, e->src->succs)
4211 if (e2 != e)
4213 e2->probability /= prob_comp;
4215 if (current_ir_type () != IR_GIMPLE
4216 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4217 update_br_prob_note (e->src);
4219 /* If all edges out of e->src are unlikely, the basic block itself
4220 is unlikely. */
4221 else
4223 if (prob_sum == profile_probability::never ())
4224 e->probability = profile_probability::always ();
4225 else
4227 if (impossible)
4228 e->probability = profile_probability::never ();
4229 /* If BB has some edges out that are not impossible, we can not
4230 assume that BB itself is. */
4231 impossible = false;
4233 if (current_ir_type () != IR_GIMPLE
4234 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
4235 update_br_prob_note (e->src);
4236 if (e->src->count == profile_count::zero ())
4237 return;
4238 if (count_sum == profile_count::zero () && impossible)
4240 bool found = false;
4241 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
4243 else if (current_ir_type () == IR_GIMPLE)
4244 for (gimple_stmt_iterator gsi = gsi_start_bb (e->src);
4245 !gsi_end_p (gsi); gsi_next (&gsi))
4247 if (stmt_can_terminate_bb_p (gsi_stmt (gsi)))
4249 found = true;
4250 break;
4253 /* FIXME: Implement RTL path. */
4254 else
4255 found = true;
4256 if (!found)
4258 if (dump_file && (dump_flags & TDF_DETAILS))
4259 fprintf (dump_file,
4260 "Making bb %i impossible and dropping count to 0.\n",
4261 e->src->index);
4262 e->src->count = profile_count::zero ();
4263 FOR_EACH_EDGE (e2, ei, e->src->preds)
4264 force_edge_cold (e2, impossible);
4265 return;
4269 /* If we did not adjusting, the source basic block has no likely edeges
4270 leaving other direction. In that case force that bb cold, too.
4271 This in general is difficult task to do, but handle special case when
4272 BB has only one predecestor. This is common case when we are updating
4273 after loop transforms. */
4274 if (!(prob_sum > profile_probability::never ())
4275 && count_sum == profile_count::zero ()
4276 && single_pred_p (e->src) && e->src->count.to_frequency (cfun)
4277 > (impossible ? 0 : 1))
4279 int old_frequency = e->src->count.to_frequency (cfun);
4280 if (dump_file && (dump_flags & TDF_DETAILS))
4281 fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
4282 impossible ? "impossible" : "cold");
4283 int new_frequency = MIN (e->src->count.to_frequency (cfun),
4284 impossible ? 0 : 1);
4285 if (impossible)
4286 e->src->count = profile_count::zero ();
4287 else
4288 e->src->count = e->count ().apply_scale (new_frequency,
4289 old_frequency);
4290 force_edge_cold (single_pred_edge (e->src), impossible);
4292 else if (dump_file && (dump_flags & TDF_DETAILS)
4293 && maybe_hot_bb_p (cfun, e->src))
4294 fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
4295 impossible ? "impossible" : "cold");
4299 #if CHECKING_P
4301 namespace selftest {
4303 /* Test that value range of predictor values defined in predict.def is
4304 within range (50, 100]. */
4306 struct branch_predictor
4308 const char *name;
4309 int probability;
4312 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) { NAME, HITRATE },
4314 static void
4315 test_prediction_value_range ()
4317 branch_predictor predictors[] = {
4318 #include "predict.def"
4319 { NULL, PROB_UNINITIALIZED }
4322 for (unsigned i = 0; predictors[i].name != NULL; i++)
4324 if (predictors[i].probability == PROB_UNINITIALIZED)
4325 continue;
4327 unsigned p = 100 * predictors[i].probability / REG_BR_PROB_BASE;
4328 ASSERT_TRUE (p >= 50 && p <= 100);
4332 #undef DEF_PREDICTOR
4334 /* Run all of the selfests within this file. */
4336 void
4337 predict_c_tests ()
4339 test_prediction_value_range ();
4342 } // namespace selftest
4343 #endif /* CHECKING_P. */