PR middle-end/66867
[official-gcc.git] / gcc / predict.c
blob66a88ab70bf0801a869b3b7ad7d8ad13bfacb781
1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000-2016 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
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 "emit-rtl.h"
41 #include "cgraph.h"
42 #include "coverage.h"
43 #include "diagnostic-core.h"
44 #include "gimple-predict.h"
45 #include "fold-const.h"
46 #include "calls.h"
47 #include "cfganal.h"
48 #include "profile.h"
49 #include "sreal.h"
50 #include "params.h"
51 #include "cfgloop.h"
52 #include "gimple-iterator.h"
53 #include "tree-cfg.h"
54 #include "tree-ssa-loop-niter.h"
55 #include "tree-ssa-loop.h"
56 #include "tree-scalar-evolution.h"
57 #include "ipa-utils.h"
58 #include "gimple-pretty-print.h"
60 /* Enum with reasons why a predictor is ignored. */
62 enum predictor_reason
64 REASON_NONE,
65 REASON_IGNORED,
66 REASON_SINGLE_EDGE_DUPLICATE,
67 REASON_EDGE_PAIR_DUPLICATE
70 /* String messages for the aforementioned enum. */
72 static const char *reason_messages[] = {"", " (ignored)",
73 " (single edge duplicate)", " (edge pair duplicate)"};
75 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
76 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
77 static sreal real_almost_one, real_br_prob_base,
78 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
80 static void combine_predictions_for_insn (rtx_insn *, basic_block);
81 static void dump_prediction (FILE *, enum br_predictor, int, basic_block,
82 enum predictor_reason, edge);
83 static void predict_paths_leading_to (basic_block, enum br_predictor,
84 enum prediction,
85 struct loop *in_loop = NULL);
86 static void predict_paths_leading_to_edge (edge, enum br_predictor,
87 enum prediction,
88 struct loop *in_loop = NULL);
89 static bool can_predict_insn_p (const rtx_insn *);
91 /* Information we hold about each branch predictor.
92 Filled using information from predict.def. */
94 struct predictor_info
96 const char *const name; /* Name used in the debugging dumps. */
97 const int hitrate; /* Expected hitrate used by
98 predict_insn_def call. */
99 const int flags;
102 /* Use given predictor without Dempster-Shaffer theory if it matches
103 using first_match heuristics. */
104 #define PRED_FLAG_FIRST_MATCH 1
106 /* Recompute hitrate in percent to our representation. */
108 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
110 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
111 static const struct predictor_info predictor_info[]= {
112 #include "predict.def"
114 /* Upper bound on predictors. */
115 {NULL, 0, 0}
117 #undef DEF_PREDICTOR
119 /* Return TRUE if frequency FREQ is considered to be hot. */
121 static inline bool
122 maybe_hot_frequency_p (struct function *fun, int freq)
124 struct cgraph_node *node = cgraph_node::get (fun->decl);
125 if (!profile_info
126 || !opt_for_fn (fun->decl, flag_branch_probabilities))
128 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
129 return false;
130 if (node->frequency == NODE_FREQUENCY_HOT)
131 return true;
133 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
134 return true;
135 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
136 && freq < (ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency * 2 / 3))
137 return false;
138 if (PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION) == 0)
139 return false;
140 if (freq * PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)
141 < ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency)
142 return false;
143 return true;
146 static gcov_type min_count = -1;
148 /* Determine the threshold for hot BB counts. */
150 gcov_type
151 get_hot_bb_threshold ()
153 gcov_working_set_t *ws;
154 if (min_count == -1)
156 ws = find_working_set (PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE));
157 gcc_assert (ws);
158 min_count = ws->min_counter;
160 return min_count;
163 /* Set the threshold for hot BB counts. */
165 void
166 set_hot_bb_threshold (gcov_type min)
168 min_count = min;
171 /* Return TRUE if frequency FREQ is considered to be hot. */
173 bool
174 maybe_hot_count_p (struct function *fun, gcov_type count)
176 if (fun && profile_status_for_fn (fun) != PROFILE_READ)
177 return true;
178 /* Code executed at most once is not hot. */
179 if (profile_info->runs >= count)
180 return false;
181 return (count >= get_hot_bb_threshold ());
184 /* Return true in case BB can be CPU intensive and should be optimized
185 for maximal performance. */
187 bool
188 maybe_hot_bb_p (struct function *fun, const_basic_block bb)
190 gcc_checking_assert (fun);
191 if (profile_status_for_fn (fun) == PROFILE_READ)
192 return maybe_hot_count_p (fun, bb->count);
193 return maybe_hot_frequency_p (fun, bb->frequency);
196 /* Return true in case BB can be CPU intensive and should be optimized
197 for maximal performance. */
199 bool
200 maybe_hot_edge_p (edge e)
202 if (profile_status_for_fn (cfun) == PROFILE_READ)
203 return maybe_hot_count_p (cfun, e->count);
204 return maybe_hot_frequency_p (cfun, EDGE_FREQUENCY (e));
207 /* Return true if profile COUNT and FREQUENCY, or function FUN static
208 node frequency reflects never being executed. */
210 static bool
211 probably_never_executed (struct function *fun,
212 gcov_type count, int frequency)
214 gcc_checking_assert (fun);
215 if (profile_status_for_fn (fun) == PROFILE_READ)
217 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
218 if (count * unlikely_count_fraction >= profile_info->runs)
219 return false;
220 if (!frequency)
221 return true;
222 if (!ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency)
223 return false;
224 if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count)
226 gcov_type computed_count;
227 /* Check for possibility of overflow, in which case entry bb count
228 is large enough to do the division first without losing much
229 precision. */
230 if (ENTRY_BLOCK_PTR_FOR_FN (fun)->count < REG_BR_PROB_BASE *
231 REG_BR_PROB_BASE)
233 gcov_type scaled_count
234 = frequency * ENTRY_BLOCK_PTR_FOR_FN (fun)->count *
235 unlikely_count_fraction;
236 computed_count = RDIV (scaled_count,
237 ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
239 else
241 computed_count = RDIV (ENTRY_BLOCK_PTR_FOR_FN (fun)->count,
242 ENTRY_BLOCK_PTR_FOR_FN (fun)->frequency);
243 computed_count *= frequency * unlikely_count_fraction;
245 if (computed_count >= profile_info->runs)
246 return false;
248 return true;
250 if ((!profile_info || !(opt_for_fn (fun->decl, flag_branch_probabilities)))
251 && (cgraph_node::get (fun->decl)->frequency
252 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
253 return true;
254 return false;
258 /* Return true in case BB is probably never executed. */
260 bool
261 probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
263 return probably_never_executed (fun, bb->count, bb->frequency);
267 /* Return true in case edge E is probably never executed. */
269 bool
270 probably_never_executed_edge_p (struct function *fun, edge e)
272 return probably_never_executed (fun, e->count, EDGE_FREQUENCY (e));
275 /* Return true when current function should always be optimized for size. */
277 bool
278 optimize_function_for_size_p (struct function *fun)
280 if (!fun || !fun->decl)
281 return optimize_size;
282 cgraph_node *n = cgraph_node::get (fun->decl);
283 return n && n->optimize_for_size_p ();
286 /* Return true when current function should always be optimized for speed. */
288 bool
289 optimize_function_for_speed_p (struct function *fun)
291 return !optimize_function_for_size_p (fun);
294 /* Return the optimization type that should be used for the function FUN. */
296 optimization_type
297 function_optimization_type (struct function *fun)
299 return (optimize_function_for_speed_p (fun)
300 ? OPTIMIZE_FOR_SPEED
301 : OPTIMIZE_FOR_SIZE);
304 /* Return TRUE when BB should be optimized for size. */
306 bool
307 optimize_bb_for_size_p (const_basic_block bb)
309 return (optimize_function_for_size_p (cfun)
310 || (bb && !maybe_hot_bb_p (cfun, bb)));
313 /* Return TRUE when BB should be optimized for speed. */
315 bool
316 optimize_bb_for_speed_p (const_basic_block bb)
318 return !optimize_bb_for_size_p (bb);
321 /* Return the optimization type that should be used for block BB. */
323 optimization_type
324 bb_optimization_type (const_basic_block bb)
326 return (optimize_bb_for_speed_p (bb)
327 ? OPTIMIZE_FOR_SPEED
328 : OPTIMIZE_FOR_SIZE);
331 /* Return TRUE when BB should be optimized for size. */
333 bool
334 optimize_edge_for_size_p (edge e)
336 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
339 /* Return TRUE when BB should be optimized for speed. */
341 bool
342 optimize_edge_for_speed_p (edge e)
344 return !optimize_edge_for_size_p (e);
347 /* Return TRUE when BB should be optimized for size. */
349 bool
350 optimize_insn_for_size_p (void)
352 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
355 /* Return TRUE when BB should be optimized for speed. */
357 bool
358 optimize_insn_for_speed_p (void)
360 return !optimize_insn_for_size_p ();
363 /* Return TRUE when LOOP should be optimized for size. */
365 bool
366 optimize_loop_for_size_p (struct loop *loop)
368 return optimize_bb_for_size_p (loop->header);
371 /* Return TRUE when LOOP should be optimized for speed. */
373 bool
374 optimize_loop_for_speed_p (struct loop *loop)
376 return optimize_bb_for_speed_p (loop->header);
379 /* Return TRUE when LOOP nest should be optimized for speed. */
381 bool
382 optimize_loop_nest_for_speed_p (struct loop *loop)
384 struct loop *l = loop;
385 if (optimize_loop_for_speed_p (loop))
386 return true;
387 l = loop->inner;
388 while (l && l != loop)
390 if (optimize_loop_for_speed_p (l))
391 return true;
392 if (l->inner)
393 l = l->inner;
394 else if (l->next)
395 l = l->next;
396 else
398 while (l != loop && !l->next)
399 l = loop_outer (l);
400 if (l != loop)
401 l = l->next;
404 return false;
407 /* Return TRUE when LOOP nest should be optimized for size. */
409 bool
410 optimize_loop_nest_for_size_p (struct loop *loop)
412 return !optimize_loop_nest_for_speed_p (loop);
415 /* Return true when edge E is likely to be well predictable by branch
416 predictor. */
418 bool
419 predictable_edge_p (edge e)
421 if (profile_status_for_fn (cfun) == PROFILE_ABSENT)
422 return false;
423 if ((e->probability
424 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
425 || (REG_BR_PROB_BASE - e->probability
426 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
427 return true;
428 return false;
432 /* Set RTL expansion for BB profile. */
434 void
435 rtl_profile_for_bb (basic_block bb)
437 crtl->maybe_hot_insn_p = maybe_hot_bb_p (cfun, bb);
440 /* Set RTL expansion for edge profile. */
442 void
443 rtl_profile_for_edge (edge e)
445 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
448 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
449 void
450 default_rtl_profile (void)
452 crtl->maybe_hot_insn_p = true;
455 /* Return true if the one of outgoing edges is already predicted by
456 PREDICTOR. */
458 bool
459 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
461 rtx note;
462 if (!INSN_P (BB_END (bb)))
463 return false;
464 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
465 if (REG_NOTE_KIND (note) == REG_BR_PRED
466 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
467 return true;
468 return false;
471 /* Structure representing predictions in tree level. */
473 struct edge_prediction {
474 struct edge_prediction *ep_next;
475 edge ep_edge;
476 enum br_predictor ep_predictor;
477 int ep_probability;
480 /* This map contains for a basic block the list of predictions for the
481 outgoing edges. */
483 static hash_map<const_basic_block, edge_prediction *> *bb_predictions;
485 /* Return true if the one of outgoing edges is already predicted by
486 PREDICTOR. */
488 bool
489 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
491 struct edge_prediction *i;
492 edge_prediction **preds = bb_predictions->get (bb);
494 if (!preds)
495 return false;
497 for (i = *preds; i; i = i->ep_next)
498 if (i->ep_predictor == predictor)
499 return true;
500 return false;
503 /* Return true if the one of outgoing edges is already predicted by
504 PREDICTOR for edge E predicted as TAKEN. */
506 bool
507 edge_predicted_by_p (edge e, enum br_predictor predictor, bool taken)
509 struct edge_prediction *i;
510 basic_block bb = e->src;
511 edge_prediction **preds = bb_predictions->get (bb);
512 if (!preds)
513 return false;
515 int probability = predictor_info[(int) predictor].hitrate;
517 if (taken != TAKEN)
518 probability = REG_BR_PROB_BASE - probability;
520 for (i = *preds; i; i = i->ep_next)
521 if (i->ep_predictor == predictor
522 && i->ep_edge == e
523 && i->ep_probability == probability)
524 return true;
525 return false;
528 /* Return true when the probability of edge is reliable.
530 The profile guessing code is good at predicting branch outcome (ie.
531 taken/not taken), that is predicted right slightly over 75% of time.
532 It is however notoriously poor on predicting the probability itself.
533 In general the profile appear a lot flatter (with probabilities closer
534 to 50%) than the reality so it is bad idea to use it to drive optimization
535 such as those disabling dynamic branch prediction for well predictable
536 branches.
538 There are two exceptions - edges leading to noreturn edges and edges
539 predicted by number of iterations heuristics are predicted well. This macro
540 should be able to distinguish those, but at the moment it simply check for
541 noreturn heuristic that is only one giving probability over 99% or bellow
542 1%. In future we might want to propagate reliability information across the
543 CFG if we find this information useful on multiple places. */
544 static bool
545 probability_reliable_p (int prob)
547 return (profile_status_for_fn (cfun) == PROFILE_READ
548 || (profile_status_for_fn (cfun) == PROFILE_GUESSED
549 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
552 /* Same predicate as above, working on edges. */
553 bool
554 edge_probability_reliable_p (const_edge e)
556 return probability_reliable_p (e->probability);
559 /* Same predicate as edge_probability_reliable_p, working on notes. */
560 bool
561 br_prob_note_reliable_p (const_rtx note)
563 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
564 return probability_reliable_p (XINT (note, 0));
567 static void
568 predict_insn (rtx_insn *insn, enum br_predictor predictor, int probability)
570 gcc_assert (any_condjump_p (insn));
571 if (!flag_guess_branch_prob)
572 return;
574 add_reg_note (insn, REG_BR_PRED,
575 gen_rtx_CONCAT (VOIDmode,
576 GEN_INT ((int) predictor),
577 GEN_INT ((int) probability)));
580 /* Predict insn by given predictor. */
582 void
583 predict_insn_def (rtx_insn *insn, enum br_predictor predictor,
584 enum prediction taken)
586 int probability = predictor_info[(int) predictor].hitrate;
588 if (taken != TAKEN)
589 probability = REG_BR_PROB_BASE - probability;
591 predict_insn (insn, predictor, probability);
594 /* Predict edge E with given probability if possible. */
596 void
597 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
599 rtx_insn *last_insn;
600 last_insn = BB_END (e->src);
602 /* We can store the branch prediction information only about
603 conditional jumps. */
604 if (!any_condjump_p (last_insn))
605 return;
607 /* We always store probability of branching. */
608 if (e->flags & EDGE_FALLTHRU)
609 probability = REG_BR_PROB_BASE - probability;
611 predict_insn (last_insn, predictor, probability);
614 /* Predict edge E with the given PROBABILITY. */
615 void
616 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
618 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
619 && EDGE_COUNT (e->src->succs) > 1
620 && flag_guess_branch_prob
621 && optimize)
623 struct edge_prediction *i = XNEW (struct edge_prediction);
624 edge_prediction *&preds = bb_predictions->get_or_insert (e->src);
626 i->ep_next = preds;
627 preds = i;
628 i->ep_probability = probability;
629 i->ep_predictor = predictor;
630 i->ep_edge = e;
634 /* Filter edge predictions PREDS by a function FILTER. DATA are passed
635 to the filter function. */
637 void
638 filter_predictions (edge_prediction **preds,
639 bool (*filter) (edge_prediction *, void *), void *data)
641 if (!bb_predictions)
642 return;
644 if (preds)
646 struct edge_prediction **prediction = preds;
647 struct edge_prediction *next;
649 while (*prediction)
651 if ((*filter) (*prediction, data))
652 prediction = &((*prediction)->ep_next);
653 else
655 next = (*prediction)->ep_next;
656 free (*prediction);
657 *prediction = next;
663 /* Filter function predicate that returns true for a edge predicate P
664 if its edge is equal to DATA. */
666 bool
667 equal_edge_p (edge_prediction *p, void *data)
669 return p->ep_edge == (edge)data;
672 /* Remove all predictions on given basic block that are attached
673 to edge E. */
674 void
675 remove_predictions_associated_with_edge (edge e)
677 if (!bb_predictions)
678 return;
680 edge_prediction **preds = bb_predictions->get (e->src);
681 filter_predictions (preds, equal_edge_p, e);
684 /* Clears the list of predictions stored for BB. */
686 static void
687 clear_bb_predictions (basic_block bb)
689 edge_prediction **preds = bb_predictions->get (bb);
690 struct edge_prediction *pred, *next;
692 if (!preds)
693 return;
695 for (pred = *preds; pred; pred = next)
697 next = pred->ep_next;
698 free (pred);
700 *preds = NULL;
703 /* Return true when we can store prediction on insn INSN.
704 At the moment we represent predictions only on conditional
705 jumps, not at computed jump or other complicated cases. */
706 static bool
707 can_predict_insn_p (const rtx_insn *insn)
709 return (JUMP_P (insn)
710 && any_condjump_p (insn)
711 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
714 /* Predict edge E by given predictor if possible. */
716 void
717 predict_edge_def (edge e, enum br_predictor predictor,
718 enum prediction taken)
720 int probability = predictor_info[(int) predictor].hitrate;
722 if (taken != TAKEN)
723 probability = REG_BR_PROB_BASE - probability;
725 predict_edge (e, predictor, probability);
728 /* Invert all branch predictions or probability notes in the INSN. This needs
729 to be done each time we invert the condition used by the jump. */
731 void
732 invert_br_probabilities (rtx insn)
734 rtx note;
736 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
737 if (REG_NOTE_KIND (note) == REG_BR_PROB)
738 XINT (note, 0) = REG_BR_PROB_BASE - XINT (note, 0);
739 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
740 XEXP (XEXP (note, 0), 1)
741 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
744 /* Dump information about the branch prediction to the output file. */
746 static void
747 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
748 basic_block bb, enum predictor_reason reason = REASON_NONE,
749 edge ep_edge = NULL)
751 edge e = ep_edge;
752 edge_iterator ei;
754 if (!file)
755 return;
757 if (e == NULL)
758 FOR_EACH_EDGE (e, ei, bb->succs)
759 if (! (e->flags & EDGE_FALLTHRU))
760 break;
762 char edge_info_str[128];
763 if (ep_edge)
764 sprintf (edge_info_str, " of edge %d->%d", ep_edge->src->index,
765 ep_edge->dest->index);
766 else
767 edge_info_str[0] = '\0';
769 fprintf (file, " %s heuristics%s%s: %.1f%%",
770 predictor_info[predictor].name,
771 edge_info_str, reason_messages[reason],
772 probability * 100.0 / REG_BR_PROB_BASE);
774 if (bb->count)
776 fprintf (file, " exec %" PRId64, bb->count);
777 if (e)
779 fprintf (file, " hit %" PRId64, e->count);
780 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
784 fprintf (file, "\n");
787 /* We can not predict the probabilities of outgoing edges of bb. Set them
788 evenly and hope for the best. */
789 static void
790 set_even_probabilities (basic_block bb)
792 int nedges = 0;
793 edge e;
794 edge_iterator ei;
796 FOR_EACH_EDGE (e, ei, bb->succs)
797 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
798 nedges ++;
799 FOR_EACH_EDGE (e, ei, bb->succs)
800 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
801 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
802 else
803 e->probability = 0;
806 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
807 note if not already present. Remove now useless REG_BR_PRED notes. */
809 static void
810 combine_predictions_for_insn (rtx_insn *insn, basic_block bb)
812 rtx prob_note;
813 rtx *pnote;
814 rtx note;
815 int best_probability = PROB_EVEN;
816 enum br_predictor best_predictor = END_PREDICTORS;
817 int combined_probability = REG_BR_PROB_BASE / 2;
818 int d;
819 bool first_match = false;
820 bool found = false;
822 if (!can_predict_insn_p (insn))
824 set_even_probabilities (bb);
825 return;
828 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
829 pnote = &REG_NOTES (insn);
830 if (dump_file)
831 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
832 bb->index);
834 /* We implement "first match" heuristics and use probability guessed
835 by predictor with smallest index. */
836 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
837 if (REG_NOTE_KIND (note) == REG_BR_PRED)
839 enum br_predictor predictor = ((enum br_predictor)
840 INTVAL (XEXP (XEXP (note, 0), 0)));
841 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
843 found = true;
844 if (best_predictor > predictor
845 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
846 best_probability = probability, best_predictor = predictor;
848 d = (combined_probability * probability
849 + (REG_BR_PROB_BASE - combined_probability)
850 * (REG_BR_PROB_BASE - probability));
852 /* Use FP math to avoid overflows of 32bit integers. */
853 if (d == 0)
854 /* If one probability is 0% and one 100%, avoid division by zero. */
855 combined_probability = REG_BR_PROB_BASE / 2;
856 else
857 combined_probability = (((double) combined_probability) * probability
858 * REG_BR_PROB_BASE / d + 0.5);
861 /* Decide which heuristic to use. In case we didn't match anything,
862 use no_prediction heuristic, in case we did match, use either
863 first match or Dempster-Shaffer theory depending on the flags. */
865 if (best_predictor != END_PREDICTORS)
866 first_match = true;
868 if (!found)
869 dump_prediction (dump_file, PRED_NO_PREDICTION,
870 combined_probability, bb);
871 else
873 if (!first_match)
874 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
875 bb, !first_match ? REASON_NONE : REASON_IGNORED);
876 else
877 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
878 bb, first_match ? REASON_NONE : REASON_IGNORED);
881 if (first_match)
882 combined_probability = best_probability;
883 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
885 while (*pnote)
887 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
889 enum br_predictor predictor = ((enum br_predictor)
890 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
891 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
893 dump_prediction (dump_file, predictor, probability, bb,
894 (!first_match || best_predictor == predictor)
895 ? REASON_NONE : REASON_IGNORED);
896 *pnote = XEXP (*pnote, 1);
898 else
899 pnote = &XEXP (*pnote, 1);
902 if (!prob_note)
904 add_int_reg_note (insn, REG_BR_PROB, combined_probability);
906 /* Save the prediction into CFG in case we are seeing non-degenerated
907 conditional jump. */
908 if (!single_succ_p (bb))
910 BRANCH_EDGE (bb)->probability = combined_probability;
911 FALLTHRU_EDGE (bb)->probability
912 = REG_BR_PROB_BASE - combined_probability;
915 else if (!single_succ_p (bb))
917 int prob = XINT (prob_note, 0);
919 BRANCH_EDGE (bb)->probability = prob;
920 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
922 else
923 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
926 /* Edge prediction hash traits. */
928 struct predictor_hash: pointer_hash <edge_prediction>
931 static inline hashval_t hash (const edge_prediction *);
932 static inline bool equal (const edge_prediction *, const edge_prediction *);
935 /* Calculate hash value of an edge prediction P based on predictor and
936 normalized probability. */
938 inline hashval_t
939 predictor_hash::hash (const edge_prediction *p)
941 inchash::hash hstate;
942 hstate.add_int (p->ep_predictor);
944 int prob = p->ep_probability;
945 if (prob > REG_BR_PROB_BASE / 2)
946 prob = REG_BR_PROB_BASE - prob;
948 hstate.add_int (prob);
950 return hstate.end ();
953 /* Return true whether edge predictions P1 and P2 use the same predictor and
954 have equal (or opposed probability). */
956 inline bool
957 predictor_hash::equal (const edge_prediction *p1, const edge_prediction *p2)
959 return (p1->ep_predictor == p2->ep_predictor
960 && (p1->ep_probability == p2->ep_probability
961 || p1->ep_probability == REG_BR_PROB_BASE - p2->ep_probability));
964 struct predictor_hash_traits: predictor_hash,
965 typed_noop_remove <edge_prediction *> {};
967 /* Return true if edge prediction P is not in DATA hash set. */
969 static bool
970 not_removed_prediction_p (edge_prediction *p, void *data)
972 hash_set<edge_prediction *> *remove = (hash_set<edge_prediction *> *) data;
973 return !remove->contains (p);
976 /* Prune predictions for a basic block BB. Currently we do following
977 clean-up steps:
979 1) remove duplicate prediction that is guessed with the same probability
980 (different than 1/2) to both edge
981 2) remove duplicates for a prediction that belongs with the same probability
982 to a single edge
986 static void
987 prune_predictions_for_bb (basic_block bb)
989 edge_prediction **preds = bb_predictions->get (bb);
991 if (preds)
993 hash_table <predictor_hash_traits> s (13);
994 hash_set <edge_prediction *> remove;
996 /* Step 1: identify predictors that should be removed. */
997 for (edge_prediction *pred = *preds; pred; pred = pred->ep_next)
999 edge_prediction *existing = s.find (pred);
1000 if (existing)
1002 if (pred->ep_edge == existing->ep_edge
1003 && pred->ep_probability == existing->ep_probability)
1005 /* Remove a duplicate predictor. */
1006 dump_prediction (dump_file, pred->ep_predictor,
1007 pred->ep_probability, bb,
1008 REASON_SINGLE_EDGE_DUPLICATE, pred->ep_edge);
1010 remove.add (pred);
1012 else if (pred->ep_edge != existing->ep_edge
1013 && pred->ep_probability == existing->ep_probability
1014 && pred->ep_probability != REG_BR_PROB_BASE / 2)
1016 /* Remove both predictors as they predict the same
1017 for both edges. */
1018 dump_prediction (dump_file, existing->ep_predictor,
1019 pred->ep_probability, bb,
1020 REASON_EDGE_PAIR_DUPLICATE,
1021 existing->ep_edge);
1022 dump_prediction (dump_file, pred->ep_predictor,
1023 pred->ep_probability, bb,
1024 REASON_EDGE_PAIR_DUPLICATE,
1025 pred->ep_edge);
1027 remove.add (existing);
1028 remove.add (pred);
1032 edge_prediction **slot2 = s.find_slot (pred, INSERT);
1033 *slot2 = pred;
1036 /* Step 2: Remove predictors. */
1037 filter_predictions (preds, not_removed_prediction_p, &remove);
1041 /* Combine predictions into single probability and store them into CFG.
1042 Remove now useless prediction entries.
1043 If DRY_RUN is set, only produce dumps and do not modify profile. */
1045 static void
1046 combine_predictions_for_bb (basic_block bb, bool dry_run)
1048 int best_probability = PROB_EVEN;
1049 enum br_predictor best_predictor = END_PREDICTORS;
1050 int combined_probability = REG_BR_PROB_BASE / 2;
1051 int d;
1052 bool first_match = false;
1053 bool found = false;
1054 struct edge_prediction *pred;
1055 int nedges = 0;
1056 edge e, first = NULL, second = NULL;
1057 edge_iterator ei;
1059 FOR_EACH_EDGE (e, ei, bb->succs)
1060 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
1062 nedges ++;
1063 if (first && !second)
1064 second = e;
1065 if (!first)
1066 first = e;
1069 /* When there is no successor or only one choice, prediction is easy.
1071 We are lazy for now and predict only basic blocks with two outgoing
1072 edges. It is possible to predict generic case too, but we have to
1073 ignore first match heuristics and do more involved combining. Implement
1074 this later. */
1075 if (nedges != 2)
1077 if (!bb->count && !dry_run)
1078 set_even_probabilities (bb);
1079 clear_bb_predictions (bb);
1080 if (dump_file)
1081 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
1082 nedges, bb->index);
1083 return;
1086 if (dump_file)
1087 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
1089 prune_predictions_for_bb (bb);
1091 edge_prediction **preds = bb_predictions->get (bb);
1093 if (preds)
1095 /* We implement "first match" heuristics and use probability guessed
1096 by predictor with smallest index. */
1097 for (pred = *preds; pred; pred = pred->ep_next)
1099 enum br_predictor predictor = pred->ep_predictor;
1100 int probability = pred->ep_probability;
1102 if (pred->ep_edge != first)
1103 probability = REG_BR_PROB_BASE - probability;
1105 found = true;
1106 /* First match heuristics would be widly confused if we predicted
1107 both directions. */
1108 if (best_predictor > predictor
1109 && predictor_info[predictor].flags & PRED_FLAG_FIRST_MATCH)
1111 struct edge_prediction *pred2;
1112 int prob = probability;
1114 for (pred2 = (struct edge_prediction *) *preds;
1115 pred2; pred2 = pred2->ep_next)
1116 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
1118 int probability2 = pred2->ep_probability;
1120 if (pred2->ep_edge != first)
1121 probability2 = REG_BR_PROB_BASE - probability2;
1123 if ((probability < REG_BR_PROB_BASE / 2) !=
1124 (probability2 < REG_BR_PROB_BASE / 2))
1125 break;
1127 /* If the same predictor later gave better result, go for it! */
1128 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
1129 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
1130 prob = probability2;
1132 if (!pred2)
1133 best_probability = prob, best_predictor = predictor;
1136 d = (combined_probability * probability
1137 + (REG_BR_PROB_BASE - combined_probability)
1138 * (REG_BR_PROB_BASE - probability));
1140 /* Use FP math to avoid overflows of 32bit integers. */
1141 if (d == 0)
1142 /* If one probability is 0% and one 100%, avoid division by zero. */
1143 combined_probability = REG_BR_PROB_BASE / 2;
1144 else
1145 combined_probability = (((double) combined_probability)
1146 * probability
1147 * REG_BR_PROB_BASE / d + 0.5);
1151 /* Decide which heuristic to use. In case we didn't match anything,
1152 use no_prediction heuristic, in case we did match, use either
1153 first match or Dempster-Shaffer theory depending on the flags. */
1155 if (best_predictor != END_PREDICTORS)
1156 first_match = true;
1158 if (!found)
1159 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb);
1160 else
1162 if (!first_match)
1163 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
1164 !first_match ? REASON_NONE : REASON_IGNORED);
1165 else
1166 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
1167 first_match ? REASON_NONE : REASON_IGNORED);
1170 if (first_match)
1171 combined_probability = best_probability;
1172 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb);
1174 if (preds)
1176 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
1178 enum br_predictor predictor = pred->ep_predictor;
1179 int probability = pred->ep_probability;
1181 dump_prediction (dump_file, predictor, probability, bb,
1182 (!first_match || best_predictor == predictor)
1183 ? REASON_NONE : REASON_IGNORED, pred->ep_edge);
1186 clear_bb_predictions (bb);
1188 if (!bb->count && !dry_run)
1190 first->probability = combined_probability;
1191 second->probability = REG_BR_PROB_BASE - combined_probability;
1195 /* Check if T1 and T2 satisfy the IV_COMPARE condition.
1196 Return the SSA_NAME if the condition satisfies, NULL otherwise.
1198 T1 and T2 should be one of the following cases:
1199 1. T1 is SSA_NAME, T2 is NULL
1200 2. T1 is SSA_NAME, T2 is INTEGER_CST between [-4, 4]
1201 3. T2 is SSA_NAME, T1 is INTEGER_CST between [-4, 4] */
1203 static tree
1204 strips_small_constant (tree t1, tree t2)
1206 tree ret = NULL;
1207 int value = 0;
1209 if (!t1)
1210 return NULL;
1211 else if (TREE_CODE (t1) == SSA_NAME)
1212 ret = t1;
1213 else if (tree_fits_shwi_p (t1))
1214 value = tree_to_shwi (t1);
1215 else
1216 return NULL;
1218 if (!t2)
1219 return ret;
1220 else if (tree_fits_shwi_p (t2))
1221 value = tree_to_shwi (t2);
1222 else if (TREE_CODE (t2) == SSA_NAME)
1224 if (ret)
1225 return NULL;
1226 else
1227 ret = t2;
1230 if (value <= 4 && value >= -4)
1231 return ret;
1232 else
1233 return NULL;
1236 /* Return the SSA_NAME in T or T's operands.
1237 Return NULL if SSA_NAME cannot be found. */
1239 static tree
1240 get_base_value (tree t)
1242 if (TREE_CODE (t) == SSA_NAME)
1243 return t;
1245 if (!BINARY_CLASS_P (t))
1246 return NULL;
1248 switch (TREE_OPERAND_LENGTH (t))
1250 case 1:
1251 return strips_small_constant (TREE_OPERAND (t, 0), NULL);
1252 case 2:
1253 return strips_small_constant (TREE_OPERAND (t, 0),
1254 TREE_OPERAND (t, 1));
1255 default:
1256 return NULL;
1260 /* Check the compare STMT in LOOP. If it compares an induction
1261 variable to a loop invariant, return true, and save
1262 LOOP_INVARIANT, COMPARE_CODE and LOOP_STEP.
1263 Otherwise return false and set LOOP_INVAIANT to NULL. */
1265 static bool
1266 is_comparison_with_loop_invariant_p (gcond *stmt, struct loop *loop,
1267 tree *loop_invariant,
1268 enum tree_code *compare_code,
1269 tree *loop_step,
1270 tree *loop_iv_base)
1272 tree op0, op1, bound, base;
1273 affine_iv iv0, iv1;
1274 enum tree_code code;
1275 tree step;
1277 code = gimple_cond_code (stmt);
1278 *loop_invariant = NULL;
1280 switch (code)
1282 case GT_EXPR:
1283 case GE_EXPR:
1284 case NE_EXPR:
1285 case LT_EXPR:
1286 case LE_EXPR:
1287 case EQ_EXPR:
1288 break;
1290 default:
1291 return false;
1294 op0 = gimple_cond_lhs (stmt);
1295 op1 = gimple_cond_rhs (stmt);
1297 if ((TREE_CODE (op0) != SSA_NAME && TREE_CODE (op0) != INTEGER_CST)
1298 || (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op1) != INTEGER_CST))
1299 return false;
1300 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, true))
1301 return false;
1302 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, true))
1303 return false;
1304 if (TREE_CODE (iv0.step) != INTEGER_CST
1305 || TREE_CODE (iv1.step) != INTEGER_CST)
1306 return false;
1307 if ((integer_zerop (iv0.step) && integer_zerop (iv1.step))
1308 || (!integer_zerop (iv0.step) && !integer_zerop (iv1.step)))
1309 return false;
1311 if (integer_zerop (iv0.step))
1313 if (code != NE_EXPR && code != EQ_EXPR)
1314 code = invert_tree_comparison (code, false);
1315 bound = iv0.base;
1316 base = iv1.base;
1317 if (tree_fits_shwi_p (iv1.step))
1318 step = iv1.step;
1319 else
1320 return false;
1322 else
1324 bound = iv1.base;
1325 base = iv0.base;
1326 if (tree_fits_shwi_p (iv0.step))
1327 step = iv0.step;
1328 else
1329 return false;
1332 if (TREE_CODE (bound) != INTEGER_CST)
1333 bound = get_base_value (bound);
1334 if (!bound)
1335 return false;
1336 if (TREE_CODE (base) != INTEGER_CST)
1337 base = get_base_value (base);
1338 if (!base)
1339 return false;
1341 *loop_invariant = bound;
1342 *compare_code = code;
1343 *loop_step = step;
1344 *loop_iv_base = base;
1345 return true;
1348 /* Compare two SSA_NAMEs: returns TRUE if T1 and T2 are value coherent. */
1350 static bool
1351 expr_coherent_p (tree t1, tree t2)
1353 gimple *stmt;
1354 tree ssa_name_1 = NULL;
1355 tree ssa_name_2 = NULL;
1357 gcc_assert (TREE_CODE (t1) == SSA_NAME || TREE_CODE (t1) == INTEGER_CST);
1358 gcc_assert (TREE_CODE (t2) == SSA_NAME || TREE_CODE (t2) == INTEGER_CST);
1360 if (t1 == t2)
1361 return true;
1363 if (TREE_CODE (t1) == INTEGER_CST && TREE_CODE (t2) == INTEGER_CST)
1364 return true;
1365 if (TREE_CODE (t1) == INTEGER_CST || TREE_CODE (t2) == INTEGER_CST)
1366 return false;
1368 /* Check to see if t1 is expressed/defined with t2. */
1369 stmt = SSA_NAME_DEF_STMT (t1);
1370 gcc_assert (stmt != NULL);
1371 if (is_gimple_assign (stmt))
1373 ssa_name_1 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1374 if (ssa_name_1 && ssa_name_1 == t2)
1375 return true;
1378 /* Check to see if t2 is expressed/defined with t1. */
1379 stmt = SSA_NAME_DEF_STMT (t2);
1380 gcc_assert (stmt != NULL);
1381 if (is_gimple_assign (stmt))
1383 ssa_name_2 = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1384 if (ssa_name_2 && ssa_name_2 == t1)
1385 return true;
1388 /* Compare if t1 and t2's def_stmts are identical. */
1389 if (ssa_name_2 != NULL && ssa_name_1 == ssa_name_2)
1390 return true;
1391 else
1392 return false;
1395 /* Return true if E is predicted by one of loop heuristics. */
1397 static bool
1398 predicted_by_loop_heuristics_p (basic_block bb)
1400 struct edge_prediction *i;
1401 edge_prediction **preds = bb_predictions->get (bb);
1403 if (!preds)
1404 return false;
1406 for (i = *preds; i; i = i->ep_next)
1407 if (i->ep_predictor == PRED_LOOP_ITERATIONS_GUESSED
1408 || i->ep_predictor == PRED_LOOP_ITERATIONS_MAX
1409 || i->ep_predictor == PRED_LOOP_ITERATIONS
1410 || i->ep_predictor == PRED_LOOP_EXIT
1411 || i->ep_predictor == PRED_LOOP_EXIT_WITH_RECURSION
1412 || i->ep_predictor == PRED_LOOP_EXTRA_EXIT)
1413 return true;
1414 return false;
1417 /* Predict branch probability of BB when BB contains a branch that compares
1418 an induction variable in LOOP with LOOP_IV_BASE_VAR to LOOP_BOUND_VAR. The
1419 loop exit is compared using LOOP_BOUND_CODE, with step of LOOP_BOUND_STEP.
1421 E.g.
1422 for (int i = 0; i < bound; i++) {
1423 if (i < bound - 2)
1424 computation_1();
1425 else
1426 computation_2();
1429 In this loop, we will predict the branch inside the loop to be taken. */
1431 static void
1432 predict_iv_comparison (struct loop *loop, basic_block bb,
1433 tree loop_bound_var,
1434 tree loop_iv_base_var,
1435 enum tree_code loop_bound_code,
1436 int loop_bound_step)
1438 gimple *stmt;
1439 tree compare_var, compare_base;
1440 enum tree_code compare_code;
1441 tree compare_step_var;
1442 edge then_edge;
1443 edge_iterator ei;
1445 if (predicted_by_loop_heuristics_p (bb))
1446 return;
1448 stmt = last_stmt (bb);
1449 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1450 return;
1451 if (!is_comparison_with_loop_invariant_p (as_a <gcond *> (stmt),
1452 loop, &compare_var,
1453 &compare_code,
1454 &compare_step_var,
1455 &compare_base))
1456 return;
1458 /* Find the taken edge. */
1459 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1460 if (then_edge->flags & EDGE_TRUE_VALUE)
1461 break;
1463 /* When comparing an IV to a loop invariant, NE is more likely to be
1464 taken while EQ is more likely to be not-taken. */
1465 if (compare_code == NE_EXPR)
1467 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1468 return;
1470 else if (compare_code == EQ_EXPR)
1472 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1473 return;
1476 if (!expr_coherent_p (loop_iv_base_var, compare_base))
1477 return;
1479 /* If loop bound, base and compare bound are all constants, we can
1480 calculate the probability directly. */
1481 if (tree_fits_shwi_p (loop_bound_var)
1482 && tree_fits_shwi_p (compare_var)
1483 && tree_fits_shwi_p (compare_base))
1485 int probability;
1486 bool overflow, overall_overflow = false;
1487 widest_int compare_count, tem;
1489 /* (loop_bound - base) / compare_step */
1490 tem = wi::sub (wi::to_widest (loop_bound_var),
1491 wi::to_widest (compare_base), SIGNED, &overflow);
1492 overall_overflow |= overflow;
1493 widest_int loop_count = wi::div_trunc (tem,
1494 wi::to_widest (compare_step_var),
1495 SIGNED, &overflow);
1496 overall_overflow |= overflow;
1498 if (!wi::neg_p (wi::to_widest (compare_step_var))
1499 ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
1501 /* (loop_bound - compare_bound) / compare_step */
1502 tem = wi::sub (wi::to_widest (loop_bound_var),
1503 wi::to_widest (compare_var), SIGNED, &overflow);
1504 overall_overflow |= overflow;
1505 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1506 SIGNED, &overflow);
1507 overall_overflow |= overflow;
1509 else
1511 /* (compare_bound - base) / compare_step */
1512 tem = wi::sub (wi::to_widest (compare_var),
1513 wi::to_widest (compare_base), SIGNED, &overflow);
1514 overall_overflow |= overflow;
1515 compare_count = wi::div_trunc (tem, wi::to_widest (compare_step_var),
1516 SIGNED, &overflow);
1517 overall_overflow |= overflow;
1519 if (compare_code == LE_EXPR || compare_code == GE_EXPR)
1520 ++compare_count;
1521 if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
1522 ++loop_count;
1523 if (wi::neg_p (compare_count))
1524 compare_count = 0;
1525 if (wi::neg_p (loop_count))
1526 loop_count = 0;
1527 if (loop_count == 0)
1528 probability = 0;
1529 else if (wi::cmps (compare_count, loop_count) == 1)
1530 probability = REG_BR_PROB_BASE;
1531 else
1533 tem = compare_count * REG_BR_PROB_BASE;
1534 tem = wi::udiv_trunc (tem, loop_count);
1535 probability = tem.to_uhwi ();
1538 /* FIXME: The branch prediction seems broken. It has only 20% hitrate. */
1539 if (!overall_overflow)
1540 predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
1542 return;
1545 if (expr_coherent_p (loop_bound_var, compare_var))
1547 if ((loop_bound_code == LT_EXPR || loop_bound_code == LE_EXPR)
1548 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1549 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1550 else if ((loop_bound_code == GT_EXPR || loop_bound_code == GE_EXPR)
1551 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1552 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1553 else if (loop_bound_code == NE_EXPR)
1555 /* If the loop backedge condition is "(i != bound)", we do
1556 the comparison based on the step of IV:
1557 * step < 0 : backedge condition is like (i > bound)
1558 * step > 0 : backedge condition is like (i < bound) */
1559 gcc_assert (loop_bound_step != 0);
1560 if (loop_bound_step > 0
1561 && (compare_code == LT_EXPR
1562 || compare_code == LE_EXPR))
1563 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1564 else if (loop_bound_step < 0
1565 && (compare_code == GT_EXPR
1566 || compare_code == GE_EXPR))
1567 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1568 else
1569 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1571 else
1572 /* The branch is predicted not-taken if loop_bound_code is
1573 opposite with compare_code. */
1574 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1576 else if (expr_coherent_p (loop_iv_base_var, compare_var))
1578 /* For cases like:
1579 for (i = s; i < h; i++)
1580 if (i > s + 2) ....
1581 The branch should be predicted taken. */
1582 if (loop_bound_step > 0
1583 && (compare_code == GT_EXPR || compare_code == GE_EXPR))
1584 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1585 else if (loop_bound_step < 0
1586 && (compare_code == LT_EXPR || compare_code == LE_EXPR))
1587 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, TAKEN);
1588 else
1589 predict_edge_def (then_edge, PRED_LOOP_IV_COMPARE_GUESS, NOT_TAKEN);
1593 /* Predict for extra loop exits that will lead to EXIT_EDGE. The extra loop
1594 exits are resulted from short-circuit conditions that will generate an
1595 if_tmp. E.g.:
1597 if (foo() || global > 10)
1598 break;
1600 This will be translated into:
1602 BB3:
1603 loop header...
1604 BB4:
1605 if foo() goto BB6 else goto BB5
1606 BB5:
1607 if global > 10 goto BB6 else goto BB7
1608 BB6:
1609 goto BB7
1610 BB7:
1611 iftmp = (PHI 0(BB5), 1(BB6))
1612 if iftmp == 1 goto BB8 else goto BB3
1613 BB8:
1614 outside of the loop...
1616 The edge BB7->BB8 is loop exit because BB8 is outside of the loop.
1617 From the dataflow, we can infer that BB4->BB6 and BB5->BB6 are also loop
1618 exits. This function takes BB7->BB8 as input, and finds out the extra loop
1619 exits to predict them using PRED_LOOP_EXTRA_EXIT. */
1621 static void
1622 predict_extra_loop_exits (edge exit_edge)
1624 unsigned i;
1625 bool check_value_one;
1626 gimple *lhs_def_stmt;
1627 gphi *phi_stmt;
1628 tree cmp_rhs, cmp_lhs;
1629 gimple *last;
1630 gcond *cmp_stmt;
1632 last = last_stmt (exit_edge->src);
1633 if (!last)
1634 return;
1635 cmp_stmt = dyn_cast <gcond *> (last);
1636 if (!cmp_stmt)
1637 return;
1639 cmp_rhs = gimple_cond_rhs (cmp_stmt);
1640 cmp_lhs = gimple_cond_lhs (cmp_stmt);
1641 if (!TREE_CONSTANT (cmp_rhs)
1642 || !(integer_zerop (cmp_rhs) || integer_onep (cmp_rhs)))
1643 return;
1644 if (TREE_CODE (cmp_lhs) != SSA_NAME)
1645 return;
1647 /* If check_value_one is true, only the phi_args with value '1' will lead
1648 to loop exit. Otherwise, only the phi_args with value '0' will lead to
1649 loop exit. */
1650 check_value_one = (((integer_onep (cmp_rhs))
1651 ^ (gimple_cond_code (cmp_stmt) == EQ_EXPR))
1652 ^ ((exit_edge->flags & EDGE_TRUE_VALUE) != 0));
1654 lhs_def_stmt = SSA_NAME_DEF_STMT (cmp_lhs);
1655 if (!lhs_def_stmt)
1656 return;
1658 phi_stmt = dyn_cast <gphi *> (lhs_def_stmt);
1659 if (!phi_stmt)
1660 return;
1662 for (i = 0; i < gimple_phi_num_args (phi_stmt); i++)
1664 edge e1;
1665 edge_iterator ei;
1666 tree val = gimple_phi_arg_def (phi_stmt, i);
1667 edge e = gimple_phi_arg_edge (phi_stmt, i);
1669 if (!TREE_CONSTANT (val) || !(integer_zerop (val) || integer_onep (val)))
1670 continue;
1671 if ((check_value_one ^ integer_onep (val)) == 1)
1672 continue;
1673 if (EDGE_COUNT (e->src->succs) != 1)
1675 predict_paths_leading_to_edge (e, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1676 continue;
1679 FOR_EACH_EDGE (e1, ei, e->src->preds)
1680 predict_paths_leading_to_edge (e1, PRED_LOOP_EXTRA_EXIT, NOT_TAKEN);
1685 /* Predict edge probabilities by exploiting loop structure. */
1687 static void
1688 predict_loops (void)
1690 struct loop *loop;
1691 basic_block bb;
1692 hash_set <struct loop *> with_recursion(10);
1694 FOR_EACH_BB_FN (bb, cfun)
1696 gimple_stmt_iterator gsi;
1697 tree decl;
1699 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1700 if (is_gimple_call (gsi_stmt (gsi))
1701 && (decl = gimple_call_fndecl (gsi_stmt (gsi))) != NULL
1702 && recursive_call_p (current_function_decl, decl))
1704 loop = bb->loop_father;
1705 while (loop && !with_recursion.add (loop))
1706 loop = loop_outer (loop);
1710 /* Try to predict out blocks in a loop that are not part of a
1711 natural loop. */
1712 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1714 basic_block bb, *bbs;
1715 unsigned j, n_exits = 0;
1716 vec<edge> exits;
1717 struct tree_niter_desc niter_desc;
1718 edge ex;
1719 struct nb_iter_bound *nb_iter;
1720 enum tree_code loop_bound_code = ERROR_MARK;
1721 tree loop_bound_step = NULL;
1722 tree loop_bound_var = NULL;
1723 tree loop_iv_base = NULL;
1724 gcond *stmt = NULL;
1725 bool recursion = with_recursion.contains (loop);
1727 exits = get_loop_exit_edges (loop);
1728 FOR_EACH_VEC_ELT (exits, j, ex)
1729 if (!(ex->flags & (EDGE_EH | EDGE_ABNORMAL_CALL | EDGE_FAKE)))
1730 n_exits ++;
1731 if (!n_exits)
1733 exits.release ();
1734 continue;
1737 if (dump_file && (dump_flags & TDF_DETAILS))
1738 fprintf (dump_file, "Predicting loop %i%s with %i exits.\n",
1739 loop->num, recursion ? " (with recursion)":"", n_exits);
1740 if (dump_file && (dump_flags & TDF_DETAILS)
1741 && max_loop_iterations_int (loop) >= 0)
1743 fprintf (dump_file,
1744 "Loop %d iterates at most %i times.\n", loop->num,
1745 (int)max_loop_iterations_int (loop));
1747 if (dump_file && (dump_flags & TDF_DETAILS)
1748 && likely_max_loop_iterations_int (loop) >= 0)
1750 fprintf (dump_file, "Loop %d likely iterates at most %i times.\n",
1751 loop->num, (int)likely_max_loop_iterations_int (loop));
1754 FOR_EACH_VEC_ELT (exits, j, ex)
1756 tree niter = NULL;
1757 HOST_WIDE_INT nitercst;
1758 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
1759 int probability;
1760 enum br_predictor predictor;
1761 widest_int nit;
1763 if (ex->flags & (EDGE_EH | EDGE_ABNORMAL_CALL | EDGE_FAKE))
1764 continue;
1765 /* Loop heuristics do not expect exit conditional to be inside
1766 inner loop. We predict from innermost to outermost loop. */
1767 if (predicted_by_loop_heuristics_p (ex->src))
1769 if (dump_file && (dump_flags & TDF_DETAILS))
1770 fprintf (dump_file, "Skipping exit %i->%i because "
1771 "it is already predicted.\n",
1772 ex->src->index, ex->dest->index);
1773 continue;
1775 predict_extra_loop_exits (ex);
1777 if (number_of_iterations_exit (loop, ex, &niter_desc, false, false))
1778 niter = niter_desc.niter;
1779 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
1780 niter = loop_niter_by_eval (loop, ex);
1781 if (dump_file && (dump_flags & TDF_DETAILS)
1782 && TREE_CODE (niter) == INTEGER_CST)
1784 fprintf (dump_file, "Exit %i->%i %d iterates ",
1785 ex->src->index, ex->dest->index,
1786 loop->num);
1787 print_generic_expr (dump_file, niter, TDF_SLIM);
1788 fprintf (dump_file, " times.\n");
1791 if (TREE_CODE (niter) == INTEGER_CST)
1793 if (tree_fits_uhwi_p (niter)
1794 && max
1795 && compare_tree_int (niter, max - 1) == -1)
1796 nitercst = tree_to_uhwi (niter) + 1;
1797 else
1798 nitercst = max;
1799 predictor = PRED_LOOP_ITERATIONS;
1801 /* If we have just one exit and we can derive some information about
1802 the number of iterations of the loop from the statements inside
1803 the loop, use it to predict this exit. */
1804 else if (n_exits == 1
1805 && estimated_stmt_executions (loop, &nit))
1807 if (wi::gtu_p (nit, max))
1808 nitercst = max;
1809 else
1810 nitercst = nit.to_shwi ();
1811 predictor = PRED_LOOP_ITERATIONS_GUESSED;
1813 /* If we have likely upper bound, trust it for very small iteration
1814 counts. Such loops would otherwise get mispredicted by standard
1815 LOOP_EXIT heuristics. */
1816 else if (n_exits == 1
1817 && likely_max_stmt_executions (loop, &nit)
1818 && wi::ltu_p (nit,
1819 RDIV (REG_BR_PROB_BASE,
1820 REG_BR_PROB_BASE
1821 - predictor_info
1822 [recursion
1823 ? PRED_LOOP_EXIT_WITH_RECURSION
1824 : PRED_LOOP_EXIT].hitrate)))
1826 nitercst = nit.to_shwi ();
1827 predictor = PRED_LOOP_ITERATIONS_MAX;
1829 else
1831 if (dump_file && (dump_flags & TDF_DETAILS))
1832 fprintf (dump_file, "Nothing known about exit %i->%i.\n",
1833 ex->src->index, ex->dest->index);
1834 continue;
1837 if (dump_file && (dump_flags & TDF_DETAILS))
1838 fprintf (dump_file, "Recording prediction to %i iterations by %s.\n",
1839 (int)nitercst, predictor_info[predictor].name);
1840 /* If the prediction for number of iterations is zero, do not
1841 predict the exit edges. */
1842 if (nitercst == 0)
1843 continue;
1845 probability = RDIV (REG_BR_PROB_BASE, nitercst);
1846 predict_edge (ex, predictor, probability);
1848 exits.release ();
1850 /* Find information about loop bound variables. */
1851 for (nb_iter = loop->bounds; nb_iter;
1852 nb_iter = nb_iter->next)
1853 if (nb_iter->stmt
1854 && gimple_code (nb_iter->stmt) == GIMPLE_COND)
1856 stmt = as_a <gcond *> (nb_iter->stmt);
1857 break;
1859 if (!stmt && last_stmt (loop->header)
1860 && gimple_code (last_stmt (loop->header)) == GIMPLE_COND)
1861 stmt = as_a <gcond *> (last_stmt (loop->header));
1862 if (stmt)
1863 is_comparison_with_loop_invariant_p (stmt, loop,
1864 &loop_bound_var,
1865 &loop_bound_code,
1866 &loop_bound_step,
1867 &loop_iv_base);
1869 bbs = get_loop_body (loop);
1871 for (j = 0; j < loop->num_nodes; j++)
1873 edge e;
1874 edge_iterator ei;
1876 bb = bbs[j];
1878 /* Bypass loop heuristics on continue statement. These
1879 statements construct loops via "non-loop" constructs
1880 in the source language and are better to be handled
1881 separately. */
1882 if (predicted_by_p (bb, PRED_CONTINUE))
1884 if (dump_file && (dump_flags & TDF_DETAILS))
1885 fprintf (dump_file, "BB %i predicted by continue.\n",
1886 bb->index);
1887 continue;
1890 /* If we already used more reliable loop exit predictors, do not
1891 bother with PRED_LOOP_EXIT. */
1892 if (!predicted_by_loop_heuristics_p (bb))
1894 /* For loop with many exits we don't want to predict all exits
1895 with the pretty large probability, because if all exits are
1896 considered in row, the loop would be predicted to iterate
1897 almost never. The code to divide probability by number of
1898 exits is very rough. It should compute the number of exits
1899 taken in each patch through function (not the overall number
1900 of exits that might be a lot higher for loops with wide switch
1901 statements in them) and compute n-th square root.
1903 We limit the minimal probability by 2% to avoid
1904 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1905 as this was causing regression in perl benchmark containing such
1906 a wide loop. */
1908 int probability = ((REG_BR_PROB_BASE
1909 - predictor_info
1910 [recursion
1911 ? PRED_LOOP_EXIT_WITH_RECURSION
1912 : PRED_LOOP_EXIT].hitrate)
1913 / n_exits);
1914 if (probability < HITRATE (2))
1915 probability = HITRATE (2);
1916 FOR_EACH_EDGE (e, ei, bb->succs)
1917 if (e->dest->index < NUM_FIXED_BLOCKS
1918 || !flow_bb_inside_loop_p (loop, e->dest))
1920 if (dump_file && (dump_flags & TDF_DETAILS))
1921 fprintf (dump_file,
1922 "Predicting exit %i->%i with prob %i.\n",
1923 e->src->index, e->dest->index, probability);
1924 predict_edge (e,
1925 recursion ? PRED_LOOP_EXIT_WITH_RECURSION
1926 : PRED_LOOP_EXIT, probability);
1929 if (loop_bound_var)
1930 predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
1931 loop_bound_code,
1932 tree_to_shwi (loop_bound_step));
1935 /* In the following code
1936 for (loop1)
1937 if (cond)
1938 for (loop2)
1939 body;
1940 guess that cond is unlikely. */
1941 if (loop_outer (loop)->num)
1943 basic_block bb = NULL;
1944 edge preheader_edge = loop_preheader_edge (loop);
1946 if (single_pred_p (preheader_edge->src)
1947 && single_succ_p (preheader_edge->src))
1948 preheader_edge = single_pred_edge (preheader_edge->src);
1950 gimple *stmt = last_stmt (preheader_edge->src);
1951 /* Pattern match fortran loop preheader:
1952 _16 = BUILTIN_EXPECT (_15, 1, PRED_FORTRAN_LOOP_PREHEADER);
1953 _17 = (logical(kind=4)) _16;
1954 if (_17 != 0)
1955 goto <bb 11>;
1956 else
1957 goto <bb 13>;
1959 Loop guard branch prediction says nothing about duplicated loop
1960 headers produced by fortran frontend and in this case we want
1961 to predict paths leading to this preheader. */
1963 if (stmt
1964 && gimple_code (stmt) == GIMPLE_COND
1965 && gimple_cond_code (stmt) == NE_EXPR
1966 && TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
1967 && integer_zerop (gimple_cond_rhs (stmt)))
1969 gimple *call_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
1970 if (gimple_code (call_stmt) == GIMPLE_ASSIGN
1971 && gimple_expr_code (call_stmt) == NOP_EXPR
1972 && TREE_CODE (gimple_assign_rhs1 (call_stmt)) == SSA_NAME)
1973 call_stmt = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (call_stmt));
1974 if (gimple_code (call_stmt) == GIMPLE_CALL
1975 && gimple_call_internal_p (call_stmt)
1976 && gimple_call_internal_fn (call_stmt) == IFN_BUILTIN_EXPECT
1977 && TREE_CODE (gimple_call_arg (call_stmt, 2)) == INTEGER_CST
1978 && tree_fits_uhwi_p (gimple_call_arg (call_stmt, 2))
1979 && tree_to_uhwi (gimple_call_arg (call_stmt, 2))
1980 == PRED_FORTRAN_LOOP_PREHEADER)
1981 bb = preheader_edge->src;
1983 if (!bb)
1985 if (!dominated_by_p (CDI_DOMINATORS,
1986 loop_outer (loop)->latch, loop->header))
1987 predict_paths_leading_to_edge (loop_preheader_edge (loop),
1988 recursion
1989 ? PRED_LOOP_GUARD_WITH_RECURSION
1990 : PRED_LOOP_GUARD,
1991 NOT_TAKEN,
1992 loop_outer (loop));
1994 else
1996 if (!dominated_by_p (CDI_DOMINATORS,
1997 loop_outer (loop)->latch, bb))
1998 predict_paths_leading_to (bb,
1999 recursion
2000 ? PRED_LOOP_GUARD_WITH_RECURSION
2001 : PRED_LOOP_GUARD,
2002 NOT_TAKEN,
2003 loop_outer (loop));
2007 /* Free basic blocks from get_loop_body. */
2008 free (bbs);
2012 /* Attempt to predict probabilities of BB outgoing edges using local
2013 properties. */
2014 static void
2015 bb_estimate_probability_locally (basic_block bb)
2017 rtx_insn *last_insn = BB_END (bb);
2018 rtx cond;
2020 if (! can_predict_insn_p (last_insn))
2021 return;
2022 cond = get_condition (last_insn, NULL, false, false);
2023 if (! cond)
2024 return;
2026 /* Try "pointer heuristic."
2027 A comparison ptr == 0 is predicted as false.
2028 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2029 if (COMPARISON_P (cond)
2030 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
2031 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
2033 if (GET_CODE (cond) == EQ)
2034 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
2035 else if (GET_CODE (cond) == NE)
2036 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
2038 else
2040 /* Try "opcode heuristic."
2041 EQ tests are usually false and NE tests are usually true. Also,
2042 most quantities are positive, so we can make the appropriate guesses
2043 about signed comparisons against zero. */
2044 switch (GET_CODE (cond))
2046 case CONST_INT:
2047 /* Unconditional branch. */
2048 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
2049 cond == const0_rtx ? NOT_TAKEN : TAKEN);
2050 break;
2052 case EQ:
2053 case UNEQ:
2054 /* Floating point comparisons appears to behave in a very
2055 unpredictable way because of special role of = tests in
2056 FP code. */
2057 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2059 /* Comparisons with 0 are often used for booleans and there is
2060 nothing useful to predict about them. */
2061 else if (XEXP (cond, 1) == const0_rtx
2062 || XEXP (cond, 0) == const0_rtx)
2064 else
2065 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
2066 break;
2068 case NE:
2069 case LTGT:
2070 /* Floating point comparisons appears to behave in a very
2071 unpredictable way because of special role of = tests in
2072 FP code. */
2073 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
2075 /* Comparisons with 0 are often used for booleans and there is
2076 nothing useful to predict about them. */
2077 else if (XEXP (cond, 1) == const0_rtx
2078 || XEXP (cond, 0) == const0_rtx)
2080 else
2081 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
2082 break;
2084 case ORDERED:
2085 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
2086 break;
2088 case UNORDERED:
2089 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
2090 break;
2092 case LE:
2093 case LT:
2094 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2095 || XEXP (cond, 1) == constm1_rtx)
2096 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
2097 break;
2099 case GE:
2100 case GT:
2101 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
2102 || XEXP (cond, 1) == constm1_rtx)
2103 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
2104 break;
2106 default:
2107 break;
2111 /* Set edge->probability for each successor edge of BB. */
2112 void
2113 guess_outgoing_edge_probabilities (basic_block bb)
2115 bb_estimate_probability_locally (bb);
2116 combine_predictions_for_insn (BB_END (bb), bb);
2119 static tree expr_expected_value (tree, bitmap, enum br_predictor *predictor);
2121 /* Helper function for expr_expected_value. */
2123 static tree
2124 expr_expected_value_1 (tree type, tree op0, enum tree_code code,
2125 tree op1, bitmap visited, enum br_predictor *predictor)
2127 gimple *def;
2129 if (predictor)
2130 *predictor = PRED_UNCONDITIONAL;
2132 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
2134 if (TREE_CONSTANT (op0))
2135 return op0;
2137 if (code == IMAGPART_EXPR)
2139 if (TREE_CODE (TREE_OPERAND (op0, 0)) == SSA_NAME)
2141 def = SSA_NAME_DEF_STMT (TREE_OPERAND (op0, 0));
2142 if (is_gimple_call (def)
2143 && gimple_call_internal_p (def)
2144 && (gimple_call_internal_fn (def)
2145 == IFN_ATOMIC_COMPARE_EXCHANGE))
2147 /* Assume that any given atomic operation has low contention,
2148 and thus the compare-and-swap operation succeeds. */
2149 if (predictor)
2150 *predictor = PRED_COMPARE_AND_SWAP;
2151 return build_one_cst (TREE_TYPE (op0));
2156 if (code != SSA_NAME)
2157 return NULL_TREE;
2159 def = SSA_NAME_DEF_STMT (op0);
2161 /* If we were already here, break the infinite cycle. */
2162 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
2163 return NULL;
2165 if (gimple_code (def) == GIMPLE_PHI)
2167 /* All the arguments of the PHI node must have the same constant
2168 length. */
2169 int i, n = gimple_phi_num_args (def);
2170 tree val = NULL, new_val;
2172 for (i = 0; i < n; i++)
2174 tree arg = PHI_ARG_DEF (def, i);
2175 enum br_predictor predictor2;
2177 /* If this PHI has itself as an argument, we cannot
2178 determine the string length of this argument. However,
2179 if we can find an expected constant value for the other
2180 PHI args then we can still be sure that this is
2181 likely a constant. So be optimistic and just
2182 continue with the next argument. */
2183 if (arg == PHI_RESULT (def))
2184 continue;
2186 new_val = expr_expected_value (arg, visited, &predictor2);
2188 /* It is difficult to combine value predictors. Simply assume
2189 that later predictor is weaker and take its prediction. */
2190 if (predictor && *predictor < predictor2)
2191 *predictor = predictor2;
2192 if (!new_val)
2193 return NULL;
2194 if (!val)
2195 val = new_val;
2196 else if (!operand_equal_p (val, new_val, false))
2197 return NULL;
2199 return val;
2201 if (is_gimple_assign (def))
2203 if (gimple_assign_lhs (def) != op0)
2204 return NULL;
2206 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
2207 gimple_assign_rhs1 (def),
2208 gimple_assign_rhs_code (def),
2209 gimple_assign_rhs2 (def),
2210 visited, predictor);
2213 if (is_gimple_call (def))
2215 tree decl = gimple_call_fndecl (def);
2216 if (!decl)
2218 if (gimple_call_internal_p (def)
2219 && gimple_call_internal_fn (def) == IFN_BUILTIN_EXPECT)
2221 gcc_assert (gimple_call_num_args (def) == 3);
2222 tree val = gimple_call_arg (def, 0);
2223 if (TREE_CONSTANT (val))
2224 return val;
2225 if (predictor)
2227 tree val2 = gimple_call_arg (def, 2);
2228 gcc_assert (TREE_CODE (val2) == INTEGER_CST
2229 && tree_fits_uhwi_p (val2)
2230 && tree_to_uhwi (val2) < END_PREDICTORS);
2231 *predictor = (enum br_predictor) tree_to_uhwi (val2);
2233 return gimple_call_arg (def, 1);
2235 return NULL;
2237 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
2238 switch (DECL_FUNCTION_CODE (decl))
2240 case BUILT_IN_EXPECT:
2242 tree val;
2243 if (gimple_call_num_args (def) != 2)
2244 return NULL;
2245 val = gimple_call_arg (def, 0);
2246 if (TREE_CONSTANT (val))
2247 return val;
2248 if (predictor)
2249 *predictor = PRED_BUILTIN_EXPECT;
2250 return gimple_call_arg (def, 1);
2253 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_N:
2254 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_1:
2255 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_2:
2256 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_4:
2257 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_8:
2258 case BUILT_IN_SYNC_BOOL_COMPARE_AND_SWAP_16:
2259 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE:
2260 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N:
2261 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
2262 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
2263 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
2264 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
2265 case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
2266 /* Assume that any given atomic operation has low contention,
2267 and thus the compare-and-swap operation succeeds. */
2268 if (predictor)
2269 *predictor = PRED_COMPARE_AND_SWAP;
2270 return boolean_true_node;
2271 default:
2272 break;
2276 return NULL;
2279 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
2281 tree res;
2282 enum br_predictor predictor2;
2283 op0 = expr_expected_value (op0, visited, predictor);
2284 if (!op0)
2285 return NULL;
2286 op1 = expr_expected_value (op1, visited, &predictor2);
2287 if (predictor && *predictor < predictor2)
2288 *predictor = predictor2;
2289 if (!op1)
2290 return NULL;
2291 res = fold_build2 (code, type, op0, op1);
2292 if (TREE_CONSTANT (res))
2293 return res;
2294 return NULL;
2296 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
2298 tree res;
2299 op0 = expr_expected_value (op0, visited, predictor);
2300 if (!op0)
2301 return NULL;
2302 res = fold_build1 (code, type, op0);
2303 if (TREE_CONSTANT (res))
2304 return res;
2305 return NULL;
2307 return NULL;
2310 /* Return constant EXPR will likely have at execution time, NULL if unknown.
2311 The function is used by builtin_expect branch predictor so the evidence
2312 must come from this construct and additional possible constant folding.
2314 We may want to implement more involved value guess (such as value range
2315 propagation based prediction), but such tricks shall go to new
2316 implementation. */
2318 static tree
2319 expr_expected_value (tree expr, bitmap visited,
2320 enum br_predictor *predictor)
2322 enum tree_code code;
2323 tree op0, op1;
2325 if (TREE_CONSTANT (expr))
2327 if (predictor)
2328 *predictor = PRED_UNCONDITIONAL;
2329 return expr;
2332 extract_ops_from_tree (expr, &code, &op0, &op1);
2333 return expr_expected_value_1 (TREE_TYPE (expr),
2334 op0, code, op1, visited, predictor);
2337 /* Predict using opcode of the last statement in basic block. */
2338 static void
2339 tree_predict_by_opcode (basic_block bb)
2341 gimple *stmt = last_stmt (bb);
2342 edge then_edge;
2343 tree op0, op1;
2344 tree type;
2345 tree val;
2346 enum tree_code cmp;
2347 bitmap visited;
2348 edge_iterator ei;
2349 enum br_predictor predictor;
2351 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
2352 return;
2353 FOR_EACH_EDGE (then_edge, ei, bb->succs)
2354 if (then_edge->flags & EDGE_TRUE_VALUE)
2355 break;
2356 op0 = gimple_cond_lhs (stmt);
2357 op1 = gimple_cond_rhs (stmt);
2358 cmp = gimple_cond_code (stmt);
2359 type = TREE_TYPE (op0);
2360 visited = BITMAP_ALLOC (NULL);
2361 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited,
2362 &predictor);
2363 BITMAP_FREE (visited);
2364 if (val && TREE_CODE (val) == INTEGER_CST)
2366 if (predictor == PRED_BUILTIN_EXPECT)
2368 int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
2370 gcc_assert (percent >= 0 && percent <= 100);
2371 if (integer_zerop (val))
2372 percent = 100 - percent;
2373 predict_edge (then_edge, PRED_BUILTIN_EXPECT, HITRATE (percent));
2375 else
2376 predict_edge_def (then_edge, predictor,
2377 integer_zerop (val) ? NOT_TAKEN : TAKEN);
2379 /* Try "pointer heuristic."
2380 A comparison ptr == 0 is predicted as false.
2381 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
2382 if (POINTER_TYPE_P (type))
2384 if (cmp == EQ_EXPR)
2385 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
2386 else if (cmp == NE_EXPR)
2387 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
2389 else
2391 /* Try "opcode heuristic."
2392 EQ tests are usually false and NE tests are usually true. Also,
2393 most quantities are positive, so we can make the appropriate guesses
2394 about signed comparisons against zero. */
2395 switch (cmp)
2397 case EQ_EXPR:
2398 case UNEQ_EXPR:
2399 /* Floating point comparisons appears to behave in a very
2400 unpredictable way because of special role of = tests in
2401 FP code. */
2402 if (FLOAT_TYPE_P (type))
2404 /* Comparisons with 0 are often used for booleans and there is
2405 nothing useful to predict about them. */
2406 else if (integer_zerop (op0) || integer_zerop (op1))
2408 else
2409 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
2410 break;
2412 case NE_EXPR:
2413 case LTGT_EXPR:
2414 /* Floating point comparisons appears to behave in a very
2415 unpredictable way because of special role of = tests in
2416 FP code. */
2417 if (FLOAT_TYPE_P (type))
2419 /* Comparisons with 0 are often used for booleans and there is
2420 nothing useful to predict about them. */
2421 else if (integer_zerop (op0)
2422 || integer_zerop (op1))
2424 else
2425 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
2426 break;
2428 case ORDERED_EXPR:
2429 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
2430 break;
2432 case UNORDERED_EXPR:
2433 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
2434 break;
2436 case LE_EXPR:
2437 case LT_EXPR:
2438 if (integer_zerop (op1)
2439 || integer_onep (op1)
2440 || integer_all_onesp (op1)
2441 || real_zerop (op1)
2442 || real_onep (op1)
2443 || real_minus_onep (op1))
2444 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
2445 break;
2447 case GE_EXPR:
2448 case GT_EXPR:
2449 if (integer_zerop (op1)
2450 || integer_onep (op1)
2451 || integer_all_onesp (op1)
2452 || real_zerop (op1)
2453 || real_onep (op1)
2454 || real_minus_onep (op1))
2455 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
2456 break;
2458 default:
2459 break;
2463 /* Try to guess whether the value of return means error code. */
2465 static enum br_predictor
2466 return_prediction (tree val, enum prediction *prediction)
2468 /* VOID. */
2469 if (!val)
2470 return PRED_NO_PREDICTION;
2471 /* Different heuristics for pointers and scalars. */
2472 if (POINTER_TYPE_P (TREE_TYPE (val)))
2474 /* NULL is usually not returned. */
2475 if (integer_zerop (val))
2477 *prediction = NOT_TAKEN;
2478 return PRED_NULL_RETURN;
2481 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
2483 /* Negative return values are often used to indicate
2484 errors. */
2485 if (TREE_CODE (val) == INTEGER_CST
2486 && tree_int_cst_sgn (val) < 0)
2488 *prediction = NOT_TAKEN;
2489 return PRED_NEGATIVE_RETURN;
2491 /* Constant return values seems to be commonly taken.
2492 Zero/one often represent booleans so exclude them from the
2493 heuristics. */
2494 if (TREE_CONSTANT (val)
2495 && (!integer_zerop (val) && !integer_onep (val)))
2497 *prediction = NOT_TAKEN;
2498 return PRED_CONST_RETURN;
2501 return PRED_NO_PREDICTION;
2504 /* Find the basic block with return expression and look up for possible
2505 return value trying to apply RETURN_PREDICTION heuristics. */
2506 static void
2507 apply_return_prediction (void)
2509 greturn *return_stmt = NULL;
2510 tree return_val;
2511 edge e;
2512 gphi *phi;
2513 int phi_num_args, i;
2514 enum br_predictor pred;
2515 enum prediction direction;
2516 edge_iterator ei;
2518 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2520 gimple *last = last_stmt (e->src);
2521 if (last
2522 && gimple_code (last) == GIMPLE_RETURN)
2524 return_stmt = as_a <greturn *> (last);
2525 break;
2528 if (!e)
2529 return;
2530 return_val = gimple_return_retval (return_stmt);
2531 if (!return_val)
2532 return;
2533 if (TREE_CODE (return_val) != SSA_NAME
2534 || !SSA_NAME_DEF_STMT (return_val)
2535 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
2536 return;
2537 phi = as_a <gphi *> (SSA_NAME_DEF_STMT (return_val));
2538 phi_num_args = gimple_phi_num_args (phi);
2539 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
2541 /* Avoid the degenerate case where all return values form the function
2542 belongs to same category (ie they are all positive constants)
2543 so we can hardly say something about them. */
2544 for (i = 1; i < phi_num_args; i++)
2545 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
2546 break;
2547 if (i != phi_num_args)
2548 for (i = 0; i < phi_num_args; i++)
2550 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
2551 if (pred != PRED_NO_PREDICTION)
2552 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
2553 direction);
2557 /* Look for basic block that contains unlikely to happen events
2558 (such as noreturn calls) and mark all paths leading to execution
2559 of this basic blocks as unlikely. */
2561 static void
2562 tree_bb_level_predictions (void)
2564 basic_block bb;
2565 bool has_return_edges = false;
2566 edge e;
2567 edge_iterator ei;
2569 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
2570 if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
2572 has_return_edges = true;
2573 break;
2576 apply_return_prediction ();
2578 FOR_EACH_BB_FN (bb, cfun)
2580 gimple_stmt_iterator gsi;
2582 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2584 gimple *stmt = gsi_stmt (gsi);
2585 tree decl;
2587 if (is_gimple_call (stmt))
2589 if ((gimple_call_flags (stmt) & ECF_NORETURN)
2590 && has_return_edges)
2591 predict_paths_leading_to (bb, PRED_NORETURN,
2592 NOT_TAKEN);
2593 decl = gimple_call_fndecl (stmt);
2594 if (decl
2595 && lookup_attribute ("cold",
2596 DECL_ATTRIBUTES (decl)))
2597 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
2598 NOT_TAKEN);
2599 if (decl && recursive_call_p (current_function_decl, decl))
2600 predict_paths_leading_to (bb, PRED_RECURSIVE_CALL,
2601 NOT_TAKEN);
2603 else if (gimple_code (stmt) == GIMPLE_PREDICT)
2605 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
2606 gimple_predict_outcome (stmt));
2607 /* Keep GIMPLE_PREDICT around so early inlining will propagate
2608 hints to callers. */
2614 /* Callback for hash_map::traverse, asserts that the pointer map is
2615 empty. */
2617 bool
2618 assert_is_empty (const_basic_block const &, edge_prediction *const &value,
2619 void *)
2621 gcc_assert (!value);
2622 return false;
2625 /* Predict branch probabilities and estimate profile for basic block BB. */
2627 static void
2628 tree_estimate_probability_bb (basic_block bb)
2630 edge e;
2631 edge_iterator ei;
2632 gimple *last;
2634 FOR_EACH_EDGE (e, ei, bb->succs)
2636 /* Predict edges to user labels with attributes. */
2637 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2639 gimple_stmt_iterator gi;
2640 for (gi = gsi_start_bb (e->dest); !gsi_end_p (gi); gsi_next (&gi))
2642 glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (gi));
2643 tree decl;
2645 if (!label_stmt)
2646 break;
2647 decl = gimple_label_label (label_stmt);
2648 if (DECL_ARTIFICIAL (decl))
2649 continue;
2651 /* Finally, we have a user-defined label. */
2652 if (lookup_attribute ("cold", DECL_ATTRIBUTES (decl)))
2653 predict_edge_def (e, PRED_COLD_LABEL, NOT_TAKEN);
2654 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (decl)))
2655 predict_edge_def (e, PRED_HOT_LABEL, TAKEN);
2659 /* Predict early returns to be probable, as we've already taken
2660 care for error returns and other cases are often used for
2661 fast paths through function.
2663 Since we've already removed the return statements, we are
2664 looking for CFG like:
2666 if (conditional)
2669 goto return_block
2671 some other blocks
2672 return_block:
2673 return_stmt. */
2674 if (e->dest != bb->next_bb
2675 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
2676 && single_succ_p (e->dest)
2677 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2678 && (last = last_stmt (e->dest)) != NULL
2679 && gimple_code (last) == GIMPLE_RETURN)
2681 edge e1;
2682 edge_iterator ei1;
2684 if (single_succ_p (bb))
2686 FOR_EACH_EDGE (e1, ei1, bb->preds)
2687 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
2688 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
2689 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
2690 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
2692 else
2693 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
2694 && !predicted_by_p (e->src, PRED_CONST_RETURN)
2695 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
2696 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
2699 /* Look for block we are guarding (ie we dominate it,
2700 but it doesn't postdominate us). */
2701 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb
2702 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
2703 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
2705 gimple_stmt_iterator bi;
2707 /* The call heuristic claims that a guarded function call
2708 is improbable. This is because such calls are often used
2709 to signal exceptional situations such as printing error
2710 messages. */
2711 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
2712 gsi_next (&bi))
2714 gimple *stmt = gsi_stmt (bi);
2715 if (is_gimple_call (stmt)
2716 && !gimple_inexpensive_call_p (as_a <gcall *> (stmt))
2717 /* Constant and pure calls are hardly used to signalize
2718 something exceptional. */
2719 && gimple_has_side_effects (stmt))
2721 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
2722 break;
2727 tree_predict_by_opcode (bb);
2730 /* Predict branch probabilities and estimate profile of the tree CFG.
2731 This function can be called from the loop optimizers to recompute
2732 the profile information.
2733 If DRY_RUN is set, do not modify CFG and only produce dump files. */
2735 void
2736 tree_estimate_probability (bool dry_run)
2738 basic_block bb;
2740 add_noreturn_fake_exit_edges ();
2741 connect_infinite_loops_to_exit ();
2742 /* We use loop_niter_by_eval, which requires that the loops have
2743 preheaders. */
2744 create_preheaders (CP_SIMPLE_PREHEADERS);
2745 calculate_dominance_info (CDI_POST_DOMINATORS);
2747 bb_predictions = new hash_map<const_basic_block, edge_prediction *>;
2748 tree_bb_level_predictions ();
2749 record_loop_exits ();
2751 if (number_of_loops (cfun) > 1)
2752 predict_loops ();
2754 FOR_EACH_BB_FN (bb, cfun)
2755 tree_estimate_probability_bb (bb);
2757 FOR_EACH_BB_FN (bb, cfun)
2758 combine_predictions_for_bb (bb, dry_run);
2760 if (flag_checking)
2761 bb_predictions->traverse<void *, assert_is_empty> (NULL);
2763 delete bb_predictions;
2764 bb_predictions = NULL;
2766 if (!dry_run)
2767 estimate_bb_frequencies (false);
2768 free_dominance_info (CDI_POST_DOMINATORS);
2769 remove_fake_exit_edges ();
2772 /* Predict edges to successors of CUR whose sources are not postdominated by
2773 BB by PRED and recurse to all postdominators. */
2775 static void
2776 predict_paths_for_bb (basic_block cur, basic_block bb,
2777 enum br_predictor pred,
2778 enum prediction taken,
2779 bitmap visited, struct loop *in_loop = NULL)
2781 edge e;
2782 edge_iterator ei;
2783 basic_block son;
2785 /* If we exited the loop or CUR is unconditional in the loop, there is
2786 nothing to do. */
2787 if (in_loop
2788 && (!flow_bb_inside_loop_p (in_loop, cur)
2789 || dominated_by_p (CDI_DOMINATORS, in_loop->latch, cur)))
2790 return;
2792 /* We are looking for all edges forming edge cut induced by
2793 set of all blocks postdominated by BB. */
2794 FOR_EACH_EDGE (e, ei, cur->preds)
2795 if (e->src->index >= NUM_FIXED_BLOCKS
2796 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
2798 edge e2;
2799 edge_iterator ei2;
2800 bool found = false;
2802 /* Ignore fake edges and eh, we predict them as not taken anyway. */
2803 if (e->flags & (EDGE_EH | EDGE_FAKE))
2804 continue;
2805 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
2807 /* See if there is an edge from e->src that is not abnormal
2808 and does not lead to BB and does not exit the loop. */
2809 FOR_EACH_EDGE (e2, ei2, e->src->succs)
2810 if (e2 != e
2811 && !(e2->flags & (EDGE_EH | EDGE_FAKE))
2812 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb)
2813 && (!in_loop || !loop_exit_edge_p (in_loop, e2)))
2815 found = true;
2816 break;
2819 /* If there is non-abnormal path leaving e->src, predict edge
2820 using predictor. Otherwise we need to look for paths
2821 leading to e->src.
2823 The second may lead to infinite loop in the case we are predicitng
2824 regions that are only reachable by abnormal edges. We simply
2825 prevent visiting given BB twice. */
2826 if (found)
2828 if (!edge_predicted_by_p (e, pred, taken))
2829 predict_edge_def (e, pred, taken);
2831 else if (bitmap_set_bit (visited, e->src->index))
2832 predict_paths_for_bb (e->src, e->src, pred, taken, visited, in_loop);
2834 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
2835 son;
2836 son = next_dom_son (CDI_POST_DOMINATORS, son))
2837 predict_paths_for_bb (son, bb, pred, taken, visited, in_loop);
2840 /* Sets branch probabilities according to PREDiction and
2841 FLAGS. */
2843 static void
2844 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
2845 enum prediction taken, struct loop *in_loop)
2847 bitmap visited = BITMAP_ALLOC (NULL);
2848 predict_paths_for_bb (bb, bb, pred, taken, visited, in_loop);
2849 BITMAP_FREE (visited);
2852 /* Like predict_paths_leading_to but take edge instead of basic block. */
2854 static void
2855 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
2856 enum prediction taken, struct loop *in_loop)
2858 bool has_nonloop_edge = false;
2859 edge_iterator ei;
2860 edge e2;
2862 basic_block bb = e->src;
2863 FOR_EACH_EDGE (e2, ei, bb->succs)
2864 if (e2->dest != e->src && e2->dest != e->dest
2865 && !(e->flags & (EDGE_EH | EDGE_FAKE))
2866 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
2868 has_nonloop_edge = true;
2869 break;
2871 if (!has_nonloop_edge)
2873 bitmap visited = BITMAP_ALLOC (NULL);
2874 predict_paths_for_bb (bb, bb, pred, taken, visited, in_loop);
2875 BITMAP_FREE (visited);
2877 else
2878 predict_edge_def (e, pred, taken);
2881 /* This is used to carry information about basic blocks. It is
2882 attached to the AUX field of the standard CFG block. */
2884 struct block_info
2886 /* Estimated frequency of execution of basic_block. */
2887 sreal frequency;
2889 /* To keep queue of basic blocks to process. */
2890 basic_block next;
2892 /* Number of predecessors we need to visit first. */
2893 int npredecessors;
2896 /* Similar information for edges. */
2897 struct edge_prob_info
2899 /* In case edge is a loopback edge, the probability edge will be reached
2900 in case header is. Estimated number of iterations of the loop can be
2901 then computed as 1 / (1 - back_edge_prob). */
2902 sreal back_edge_prob;
2903 /* True if the edge is a loopback edge in the natural loop. */
2904 unsigned int back_edge:1;
2907 #define BLOCK_INFO(B) ((block_info *) (B)->aux)
2908 #undef EDGE_INFO
2909 #define EDGE_INFO(E) ((edge_prob_info *) (E)->aux)
2911 /* Helper function for estimate_bb_frequencies.
2912 Propagate the frequencies in blocks marked in
2913 TOVISIT, starting in HEAD. */
2915 static void
2916 propagate_freq (basic_block head, bitmap tovisit)
2918 basic_block bb;
2919 basic_block last;
2920 unsigned i;
2921 edge e;
2922 basic_block nextbb;
2923 bitmap_iterator bi;
2925 /* For each basic block we need to visit count number of his predecessors
2926 we need to visit first. */
2927 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
2929 edge_iterator ei;
2930 int count = 0;
2932 bb = BASIC_BLOCK_FOR_FN (cfun, i);
2934 FOR_EACH_EDGE (e, ei, bb->preds)
2936 bool visit = bitmap_bit_p (tovisit, e->src->index);
2938 if (visit && !(e->flags & EDGE_DFS_BACK))
2939 count++;
2940 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
2941 fprintf (dump_file,
2942 "Irreducible region hit, ignoring edge to %i->%i\n",
2943 e->src->index, bb->index);
2945 BLOCK_INFO (bb)->npredecessors = count;
2946 /* When function never returns, we will never process exit block. */
2947 if (!count && bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
2948 bb->count = bb->frequency = 0;
2951 BLOCK_INFO (head)->frequency = 1;
2952 last = head;
2953 for (bb = head; bb; bb = nextbb)
2955 edge_iterator ei;
2956 sreal cyclic_probability = 0;
2957 sreal frequency = 0;
2959 nextbb = BLOCK_INFO (bb)->next;
2960 BLOCK_INFO (bb)->next = NULL;
2962 /* Compute frequency of basic block. */
2963 if (bb != head)
2965 if (flag_checking)
2966 FOR_EACH_EDGE (e, ei, bb->preds)
2967 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
2968 || (e->flags & EDGE_DFS_BACK));
2970 FOR_EACH_EDGE (e, ei, bb->preds)
2971 if (EDGE_INFO (e)->back_edge)
2973 cyclic_probability += EDGE_INFO (e)->back_edge_prob;
2975 else if (!(e->flags & EDGE_DFS_BACK))
2977 /* frequency += (e->probability
2978 * BLOCK_INFO (e->src)->frequency /
2979 REG_BR_PROB_BASE); */
2981 sreal tmp = e->probability;
2982 tmp *= BLOCK_INFO (e->src)->frequency;
2983 tmp *= real_inv_br_prob_base;
2984 frequency += tmp;
2987 if (cyclic_probability == 0)
2989 BLOCK_INFO (bb)->frequency = frequency;
2991 else
2993 if (cyclic_probability > real_almost_one)
2994 cyclic_probability = real_almost_one;
2996 /* BLOCK_INFO (bb)->frequency = frequency
2997 / (1 - cyclic_probability) */
2999 cyclic_probability = sreal (1) - cyclic_probability;
3000 BLOCK_INFO (bb)->frequency = frequency / cyclic_probability;
3004 bitmap_clear_bit (tovisit, bb->index);
3006 e = find_edge (bb, head);
3007 if (e)
3009 /* EDGE_INFO (e)->back_edge_prob
3010 = ((e->probability * BLOCK_INFO (bb)->frequency)
3011 / REG_BR_PROB_BASE); */
3013 sreal tmp = e->probability;
3014 tmp *= BLOCK_INFO (bb)->frequency;
3015 EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base;
3018 /* Propagate to successor blocks. */
3019 FOR_EACH_EDGE (e, ei, bb->succs)
3020 if (!(e->flags & EDGE_DFS_BACK)
3021 && BLOCK_INFO (e->dest)->npredecessors)
3023 BLOCK_INFO (e->dest)->npredecessors--;
3024 if (!BLOCK_INFO (e->dest)->npredecessors)
3026 if (!nextbb)
3027 nextbb = e->dest;
3028 else
3029 BLOCK_INFO (last)->next = e->dest;
3031 last = e->dest;
3037 /* Estimate frequencies in loops at same nest level. */
3039 static void
3040 estimate_loops_at_level (struct loop *first_loop)
3042 struct loop *loop;
3044 for (loop = first_loop; loop; loop = loop->next)
3046 edge e;
3047 basic_block *bbs;
3048 unsigned i;
3049 bitmap tovisit = BITMAP_ALLOC (NULL);
3051 estimate_loops_at_level (loop->inner);
3053 /* Find current loop back edge and mark it. */
3054 e = loop_latch_edge (loop);
3055 EDGE_INFO (e)->back_edge = 1;
3057 bbs = get_loop_body (loop);
3058 for (i = 0; i < loop->num_nodes; i++)
3059 bitmap_set_bit (tovisit, bbs[i]->index);
3060 free (bbs);
3061 propagate_freq (loop->header, tovisit);
3062 BITMAP_FREE (tovisit);
3066 /* Propagates frequencies through structure of loops. */
3068 static void
3069 estimate_loops (void)
3071 bitmap tovisit = BITMAP_ALLOC (NULL);
3072 basic_block bb;
3074 /* Start by estimating the frequencies in the loops. */
3075 if (number_of_loops (cfun) > 1)
3076 estimate_loops_at_level (current_loops->tree_root->inner);
3078 /* Now propagate the frequencies through all the blocks. */
3079 FOR_ALL_BB_FN (bb, cfun)
3081 bitmap_set_bit (tovisit, bb->index);
3083 propagate_freq (ENTRY_BLOCK_PTR_FOR_FN (cfun), tovisit);
3084 BITMAP_FREE (tovisit);
3087 /* Drop the profile for NODE to guessed, and update its frequency based on
3088 whether it is expected to be hot given the CALL_COUNT. */
3090 static void
3091 drop_profile (struct cgraph_node *node, gcov_type call_count)
3093 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3094 /* In the case where this was called by another function with a
3095 dropped profile, call_count will be 0. Since there are no
3096 non-zero call counts to this function, we don't know for sure
3097 whether it is hot, and therefore it will be marked normal below. */
3098 bool hot = maybe_hot_count_p (NULL, call_count);
3100 if (dump_file)
3101 fprintf (dump_file,
3102 "Dropping 0 profile for %s/%i. %s based on calls.\n",
3103 node->name (), node->order,
3104 hot ? "Function is hot" : "Function is normal");
3105 /* We only expect to miss profiles for functions that are reached
3106 via non-zero call edges in cases where the function may have
3107 been linked from another module or library (COMDATs and extern
3108 templates). See the comments below for handle_missing_profiles.
3109 Also, only warn in cases where the missing counts exceed the
3110 number of training runs. In certain cases with an execv followed
3111 by a no-return call the profile for the no-return call is not
3112 dumped and there can be a mismatch. */
3113 if (!DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl)
3114 && call_count > profile_info->runs)
3116 if (flag_profile_correction)
3118 if (dump_file)
3119 fprintf (dump_file,
3120 "Missing counts for called function %s/%i\n",
3121 node->name (), node->order);
3123 else
3124 warning (0, "Missing counts for called function %s/%i",
3125 node->name (), node->order);
3128 profile_status_for_fn (fn)
3129 = (flag_guess_branch_prob ? PROFILE_GUESSED : PROFILE_ABSENT);
3130 node->frequency
3131 = hot ? NODE_FREQUENCY_HOT : NODE_FREQUENCY_NORMAL;
3134 /* In the case of COMDAT routines, multiple object files will contain the same
3135 function and the linker will select one for the binary. In that case
3136 all the other copies from the profile instrument binary will be missing
3137 profile counts. Look for cases where this happened, due to non-zero
3138 call counts going to 0-count functions, and drop the profile to guessed
3139 so that we can use the estimated probabilities and avoid optimizing only
3140 for size.
3142 The other case where the profile may be missing is when the routine
3143 is not going to be emitted to the object file, e.g. for "extern template"
3144 class methods. Those will be marked DECL_EXTERNAL. Emit a warning in
3145 all other cases of non-zero calls to 0-count functions. */
3147 void
3148 handle_missing_profiles (void)
3150 struct cgraph_node *node;
3151 int unlikely_count_fraction = PARAM_VALUE (UNLIKELY_BB_COUNT_FRACTION);
3152 vec<struct cgraph_node *> worklist;
3153 worklist.create (64);
3155 /* See if 0 count function has non-0 count callers. In this case we
3156 lost some profile. Drop its function profile to PROFILE_GUESSED. */
3157 FOR_EACH_DEFINED_FUNCTION (node)
3159 struct cgraph_edge *e;
3160 gcov_type call_count = 0;
3161 gcov_type max_tp_first_run = 0;
3162 struct function *fn = DECL_STRUCT_FUNCTION (node->decl);
3164 if (node->count)
3165 continue;
3166 for (e = node->callers; e; e = e->next_caller)
3168 call_count += e->count;
3170 if (e->caller->tp_first_run > max_tp_first_run)
3171 max_tp_first_run = e->caller->tp_first_run;
3174 /* If time profile is missing, let assign the maximum that comes from
3175 caller functions. */
3176 if (!node->tp_first_run && max_tp_first_run)
3177 node->tp_first_run = max_tp_first_run + 1;
3179 if (call_count
3180 && fn && fn->cfg
3181 && (call_count * unlikely_count_fraction >= profile_info->runs))
3183 drop_profile (node, call_count);
3184 worklist.safe_push (node);
3188 /* Propagate the profile dropping to other 0-count COMDATs that are
3189 potentially called by COMDATs we already dropped the profile on. */
3190 while (worklist.length () > 0)
3192 struct cgraph_edge *e;
3194 node = worklist.pop ();
3195 for (e = node->callees; e; e = e->next_caller)
3197 struct cgraph_node *callee = e->callee;
3198 struct function *fn = DECL_STRUCT_FUNCTION (callee->decl);
3200 if (callee->count > 0)
3201 continue;
3202 if (DECL_COMDAT (callee->decl) && fn && fn->cfg
3203 && profile_status_for_fn (fn) == PROFILE_READ)
3205 drop_profile (node, 0);
3206 worklist.safe_push (callee);
3210 worklist.release ();
3213 /* Convert counts measured by profile driven feedback to frequencies.
3214 Return nonzero iff there was any nonzero execution count. */
3217 counts_to_freqs (void)
3219 gcov_type count_max, true_count_max = 0;
3220 basic_block bb;
3222 /* Don't overwrite the estimated frequencies when the profile for
3223 the function is missing. We may drop this function PROFILE_GUESSED
3224 later in drop_profile (). */
3225 if (!flag_auto_profile && !ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
3226 return 0;
3228 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3229 true_count_max = MAX (bb->count, true_count_max);
3231 count_max = MAX (true_count_max, 1);
3232 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3233 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
3235 return true_count_max;
3238 /* Return true if function is likely to be expensive, so there is no point to
3239 optimize performance of prologue, epilogue or do inlining at the expense
3240 of code size growth. THRESHOLD is the limit of number of instructions
3241 function can execute at average to be still considered not expensive. */
3243 bool
3244 expensive_function_p (int threshold)
3246 unsigned int sum = 0;
3247 basic_block bb;
3248 unsigned int limit;
3250 /* We can not compute accurately for large thresholds due to scaled
3251 frequencies. */
3252 gcc_assert (threshold <= BB_FREQ_MAX);
3254 /* Frequencies are out of range. This either means that function contains
3255 internal loop executing more than BB_FREQ_MAX times or profile feedback
3256 is available and function has not been executed at all. */
3257 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency == 0)
3258 return true;
3260 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
3261 limit = ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency * threshold;
3262 FOR_EACH_BB_FN (bb, cfun)
3264 rtx_insn *insn;
3266 FOR_BB_INSNS (bb, insn)
3267 if (active_insn_p (insn))
3269 sum += bb->frequency;
3270 if (sum > limit)
3271 return true;
3275 return false;
3278 /* Estimate and propagate basic block frequencies using the given branch
3279 probabilities. If FORCE is true, the frequencies are used to estimate
3280 the counts even when there are already non-zero profile counts. */
3282 void
3283 estimate_bb_frequencies (bool force)
3285 basic_block bb;
3286 sreal freq_max;
3288 if (force || profile_status_for_fn (cfun) != PROFILE_READ || !counts_to_freqs ())
3290 static int real_values_initialized = 0;
3292 if (!real_values_initialized)
3294 real_values_initialized = 1;
3295 real_br_prob_base = REG_BR_PROB_BASE;
3296 real_bb_freq_max = BB_FREQ_MAX;
3297 real_one_half = sreal (1, -1);
3298 real_inv_br_prob_base = sreal (1) / real_br_prob_base;
3299 real_almost_one = sreal (1) - real_inv_br_prob_base;
3302 mark_dfs_back_edges ();
3304 single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->probability =
3305 REG_BR_PROB_BASE;
3307 /* Set up block info for each basic block. */
3308 alloc_aux_for_blocks (sizeof (block_info));
3309 alloc_aux_for_edges (sizeof (edge_prob_info));
3310 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3312 edge e;
3313 edge_iterator ei;
3315 FOR_EACH_EDGE (e, ei, bb->succs)
3317 EDGE_INFO (e)->back_edge_prob = e->probability;
3318 EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base;
3322 /* First compute frequencies locally for each loop from innermost
3323 to outermost to examine frequencies for back edges. */
3324 estimate_loops ();
3326 freq_max = 0;
3327 FOR_EACH_BB_FN (bb, cfun)
3328 if (freq_max < BLOCK_INFO (bb)->frequency)
3329 freq_max = BLOCK_INFO (bb)->frequency;
3331 freq_max = real_bb_freq_max / freq_max;
3332 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3334 sreal tmp = BLOCK_INFO (bb)->frequency * freq_max + real_one_half;
3335 bb->frequency = tmp.to_int ();
3338 free_aux_for_blocks ();
3339 free_aux_for_edges ();
3341 compute_function_frequency ();
3344 /* Decide whether function is hot, cold or unlikely executed. */
3345 void
3346 compute_function_frequency (void)
3348 basic_block bb;
3349 struct cgraph_node *node = cgraph_node::get (current_function_decl);
3351 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3352 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
3353 node->only_called_at_startup = true;
3354 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
3355 node->only_called_at_exit = true;
3357 if (profile_status_for_fn (cfun) != PROFILE_READ)
3359 int flags = flags_from_decl_or_type (current_function_decl);
3360 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
3361 != NULL)
3362 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3363 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
3364 != NULL)
3365 node->frequency = NODE_FREQUENCY_HOT;
3366 else if (flags & ECF_NORETURN)
3367 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3368 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
3369 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3370 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
3371 || DECL_STATIC_DESTRUCTOR (current_function_decl))
3372 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
3373 return;
3376 /* Only first time try to drop function into unlikely executed.
3377 After inlining the roundoff errors may confuse us.
3378 Ipa-profile pass will drop functions only called from unlikely
3379 functions to unlikely and that is most of what we care about. */
3380 if (!cfun->after_inlining)
3381 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
3382 FOR_EACH_BB_FN (bb, cfun)
3384 if (maybe_hot_bb_p (cfun, bb))
3386 node->frequency = NODE_FREQUENCY_HOT;
3387 return;
3389 if (!probably_never_executed_bb_p (cfun, bb))
3390 node->frequency = NODE_FREQUENCY_NORMAL;
3394 /* Build PREDICT_EXPR. */
3395 tree
3396 build_predict_expr (enum br_predictor predictor, enum prediction taken)
3398 tree t = build1 (PREDICT_EXPR, void_type_node,
3399 build_int_cst (integer_type_node, predictor));
3400 SET_PREDICT_EXPR_OUTCOME (t, taken);
3401 return t;
3404 const char *
3405 predictor_name (enum br_predictor predictor)
3407 return predictor_info[predictor].name;
3410 /* Predict branch probabilities and estimate profile of the tree CFG. */
3412 namespace {
3414 const pass_data pass_data_profile =
3416 GIMPLE_PASS, /* type */
3417 "profile_estimate", /* name */
3418 OPTGROUP_NONE, /* optinfo_flags */
3419 TV_BRANCH_PROB, /* tv_id */
3420 PROP_cfg, /* properties_required */
3421 0, /* properties_provided */
3422 0, /* properties_destroyed */
3423 0, /* todo_flags_start */
3424 0, /* todo_flags_finish */
3427 class pass_profile : public gimple_opt_pass
3429 public:
3430 pass_profile (gcc::context *ctxt)
3431 : gimple_opt_pass (pass_data_profile, ctxt)
3434 /* opt_pass methods: */
3435 virtual bool gate (function *) { return flag_guess_branch_prob; }
3436 virtual unsigned int execute (function *);
3438 }; // class pass_profile
3440 unsigned int
3441 pass_profile::execute (function *fun)
3443 unsigned nb_loops;
3445 if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
3446 return 0;
3448 loop_optimizer_init (LOOPS_NORMAL);
3449 if (dump_file && (dump_flags & TDF_DETAILS))
3450 flow_loops_dump (dump_file, NULL, 0);
3452 mark_irreducible_loops ();
3454 nb_loops = number_of_loops (fun);
3455 if (nb_loops > 1)
3456 scev_initialize ();
3458 tree_estimate_probability (false);
3460 if (nb_loops > 1)
3461 scev_finalize ();
3463 loop_optimizer_finalize ();
3464 if (dump_file && (dump_flags & TDF_DETAILS))
3465 gimple_dump_cfg (dump_file, dump_flags);
3466 if (profile_status_for_fn (fun) == PROFILE_ABSENT)
3467 profile_status_for_fn (fun) = PROFILE_GUESSED;
3468 if (dump_file && (dump_flags & TDF_DETAILS))
3470 struct loop *loop;
3471 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3472 if (loop->header->frequency)
3473 fprintf (dump_file, "Loop got predicted %d to iterate %i times.\n",
3474 loop->num,
3475 (int)expected_loop_iterations_unbounded (loop));
3477 return 0;
3480 } // anon namespace
3482 gimple_opt_pass *
3483 make_pass_profile (gcc::context *ctxt)
3485 return new pass_profile (ctxt);
3488 namespace {
3490 const pass_data pass_data_strip_predict_hints =
3492 GIMPLE_PASS, /* type */
3493 "*strip_predict_hints", /* name */
3494 OPTGROUP_NONE, /* optinfo_flags */
3495 TV_BRANCH_PROB, /* tv_id */
3496 PROP_cfg, /* properties_required */
3497 0, /* properties_provided */
3498 0, /* properties_destroyed */
3499 0, /* todo_flags_start */
3500 0, /* todo_flags_finish */
3503 class pass_strip_predict_hints : public gimple_opt_pass
3505 public:
3506 pass_strip_predict_hints (gcc::context *ctxt)
3507 : gimple_opt_pass (pass_data_strip_predict_hints, ctxt)
3510 /* opt_pass methods: */
3511 opt_pass * clone () { return new pass_strip_predict_hints (m_ctxt); }
3512 virtual unsigned int execute (function *);
3514 }; // class pass_strip_predict_hints
3516 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
3517 we no longer need. */
3518 unsigned int
3519 pass_strip_predict_hints::execute (function *fun)
3521 basic_block bb;
3522 gimple *ass_stmt;
3523 tree var;
3524 bool changed = false;
3526 FOR_EACH_BB_FN (bb, fun)
3528 gimple_stmt_iterator bi;
3529 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
3531 gimple *stmt = gsi_stmt (bi);
3533 if (gimple_code (stmt) == GIMPLE_PREDICT)
3535 gsi_remove (&bi, true);
3536 changed = true;
3537 continue;
3539 else if (is_gimple_call (stmt))
3541 tree fndecl = gimple_call_fndecl (stmt);
3543 if ((fndecl
3544 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
3545 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
3546 && gimple_call_num_args (stmt) == 2)
3547 || (gimple_call_internal_p (stmt)
3548 && gimple_call_internal_fn (stmt) == IFN_BUILTIN_EXPECT))
3550 var = gimple_call_lhs (stmt);
3551 changed = true;
3552 if (var)
3554 ass_stmt
3555 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
3556 gsi_replace (&bi, ass_stmt, true);
3558 else
3560 gsi_remove (&bi, true);
3561 continue;
3565 gsi_next (&bi);
3568 return changed ? TODO_cleanup_cfg : 0;
3571 } // anon namespace
3573 gimple_opt_pass *
3574 make_pass_strip_predict_hints (gcc::context *ctxt)
3576 return new pass_strip_predict_hints (ctxt);
3579 /* Rebuild function frequencies. Passes are in general expected to
3580 maintain profile by hand, however in some cases this is not possible:
3581 for example when inlining several functions with loops freuqencies might run
3582 out of scale and thus needs to be recomputed. */
3584 void
3585 rebuild_frequencies (void)
3587 timevar_push (TV_REBUILD_FREQUENCIES);
3589 /* When the max bb count in the function is small, there is a higher
3590 chance that there were truncation errors in the integer scaling
3591 of counts by inlining and other optimizations. This could lead
3592 to incorrect classification of code as being cold when it isn't.
3593 In that case, force the estimation of bb counts/frequencies from the
3594 branch probabilities, rather than computing frequencies from counts,
3595 which may also lead to frequencies incorrectly reduced to 0. There
3596 is less precision in the probabilities, so we only do this for small
3597 max counts. */
3598 gcov_type count_max = 0;
3599 basic_block bb;
3600 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), NULL, next_bb)
3601 count_max = MAX (bb->count, count_max);
3603 if (profile_status_for_fn (cfun) == PROFILE_GUESSED
3604 || (!flag_auto_profile && profile_status_for_fn (cfun) == PROFILE_READ
3605 && count_max < REG_BR_PROB_BASE/10))
3607 loop_optimizer_init (0);
3608 add_noreturn_fake_exit_edges ();
3609 mark_irreducible_loops ();
3610 connect_infinite_loops_to_exit ();
3611 estimate_bb_frequencies (true);
3612 remove_fake_exit_edges ();
3613 loop_optimizer_finalize ();
3615 else if (profile_status_for_fn (cfun) == PROFILE_READ)
3616 counts_to_freqs ();
3617 else
3618 gcc_unreachable ();
3619 timevar_pop (TV_REBUILD_FREQUENCIES);
3622 /* Perform a dry run of the branch prediction pass and report comparsion of
3623 the predicted and real profile into the dump file. */
3625 void
3626 report_predictor_hitrates (void)
3628 unsigned nb_loops;
3630 loop_optimizer_init (LOOPS_NORMAL);
3631 if (dump_file && (dump_flags & TDF_DETAILS))
3632 flow_loops_dump (dump_file, NULL, 0);
3634 mark_irreducible_loops ();
3636 nb_loops = number_of_loops (cfun);
3637 if (nb_loops > 1)
3638 scev_initialize ();
3640 tree_estimate_probability (true);
3642 if (nb_loops > 1)
3643 scev_finalize ();
3645 loop_optimizer_finalize ();
3648 /* Force edge E to be cold.
3649 If IMPOSSIBLE is true, for edge to have count and probability 0 otherwise
3650 keep low probability to represent possible error in a guess. This is used
3651 i.e. in case we predict loop to likely iterate given number of times but
3652 we are not 100% sure.
3654 This function locally updates profile without attempt to keep global
3655 consistency which can not be reached in full generality without full profile
3656 rebuild from probabilities alone. Doing so is not necessarily a good idea
3657 because frequencies and counts may be more realistic then probabilities.
3659 In some cases (such as for elimination of early exits during full loop
3660 unrolling) the caller can ensure that profile will get consistent
3661 afterwards. */
3663 void
3664 force_edge_cold (edge e, bool impossible)
3666 gcov_type count_sum = 0;
3667 int prob_sum = 0;
3668 edge_iterator ei;
3669 edge e2;
3670 gcov_type old_count = e->count;
3671 int old_probability = e->probability;
3672 gcov_type gcov_scale = REG_BR_PROB_BASE;
3673 int prob_scale = REG_BR_PROB_BASE;
3675 /* If edge is already improbably or cold, just return. */
3676 if (e->probability <= impossible ? PROB_VERY_UNLIKELY : 0
3677 && (!impossible || !e->count))
3678 return;
3679 FOR_EACH_EDGE (e2, ei, e->src->succs)
3680 if (e2 != e)
3682 count_sum += e2->count;
3683 prob_sum += e2->probability;
3686 /* If there are other edges out of e->src, redistribute probabilitity
3687 there. */
3688 if (prob_sum)
3690 e->probability
3691 = MIN (e->probability, impossible ? 0 : PROB_VERY_UNLIKELY);
3692 if (old_probability)
3693 e->count = RDIV (e->count * e->probability, old_probability);
3694 else
3695 e->count = MIN (e->count, impossible ? 0 : 1);
3697 if (count_sum)
3698 gcov_scale = RDIV ((count_sum + old_count - e->count) * REG_BR_PROB_BASE,
3699 count_sum);
3700 prob_scale = RDIV ((REG_BR_PROB_BASE - e->probability) * REG_BR_PROB_BASE,
3701 prob_sum);
3702 if (dump_file && (dump_flags & TDF_DETAILS))
3703 fprintf (dump_file, "Making edge %i->%i %s by redistributing "
3704 "probability to other edges.\n",
3705 e->src->index, e->dest->index,
3706 impossible ? "impossible" : "cold");
3707 FOR_EACH_EDGE (e2, ei, e->src->succs)
3708 if (e2 != e)
3710 e2->count = RDIV (e2->count * gcov_scale, REG_BR_PROB_BASE);
3711 e2->probability = RDIV (e2->probability * prob_scale,
3712 REG_BR_PROB_BASE);
3715 /* If all edges out of e->src are unlikely, the basic block itself
3716 is unlikely. */
3717 else
3719 e->probability = REG_BR_PROB_BASE;
3721 /* If we did not adjusting, the source basic block has no likely edeges
3722 leaving other direction. In that case force that bb cold, too.
3723 This in general is difficult task to do, but handle special case when
3724 BB has only one predecestor. This is common case when we are updating
3725 after loop transforms. */
3726 if (!prob_sum && !count_sum && single_pred_p (e->src)
3727 && e->src->frequency > (impossible ? 0 : 1))
3729 int old_frequency = e->src->frequency;
3730 if (dump_file && (dump_flags & TDF_DETAILS))
3731 fprintf (dump_file, "Making bb %i %s.\n", e->src->index,
3732 impossible ? "impossible" : "cold");
3733 e->src->frequency = MIN (e->src->frequency, impossible ? 0 : 1);
3734 e->src->count = e->count = RDIV (e->src->count * e->src->frequency,
3735 old_frequency);
3736 force_edge_cold (single_pred_edge (e->src), impossible);
3738 else if (dump_file && (dump_flags & TDF_DETAILS)
3739 && maybe_hot_bb_p (cfun, e->src))
3740 fprintf (dump_file, "Giving up on making bb %i %s.\n", e->src->index,
3741 impossible ? "impossible" : "cold");