1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 [1] "Branch Prediction for Free"
24 Ball and Larus; PLDI '93.
25 [2] "Static Branch Frequency and Program Profile Analysis"
26 Wu and Larus; MICRO-27.
27 [3] "Corpus-based Static Branch Prediction"
28 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
33 #include "coretypes.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
46 #include "diagnostic-core.h"
55 #include "tree-flow.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
60 #include "tree-scalar-evolution.h"
62 #include "pointer-set.h"
64 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
65 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
66 static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
67 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
69 /* Random guesstimation given names.
70 PROV_VERY_UNLIKELY should be small enough so basic block predicted
71 by it gets bellow HOT_BB_FREQUENCY_FRANCTION. */
72 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
73 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
74 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
75 #define PROB_ALWAYS (REG_BR_PROB_BASE)
77 static void combine_predictions_for_insn (rtx, basic_block);
78 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
79 static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
80 static void predict_paths_leading_to_edge (edge, enum br_predictor, enum prediction);
81 static bool can_predict_insn_p (const_rtx);
83 /* Information we hold about each branch predictor.
84 Filled using information from predict.def. */
88 const char *const name; /* Name used in the debugging dumps. */
89 const int hitrate; /* Expected hitrate used by
90 predict_insn_def call. */
94 /* Use given predictor without Dempster-Shaffer theory if it matches
95 using first_match heuristics. */
96 #define PRED_FLAG_FIRST_MATCH 1
98 /* Recompute hitrate in percent to our representation. */
100 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
102 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
103 static const struct predictor_info predictor_info[]= {
104 #include "predict.def"
106 /* Upper bound on predictors. */
111 /* Return TRUE if frequency FREQ is considered to be hot. */
114 maybe_hot_frequency_p (int freq)
116 struct cgraph_node *node = cgraph_node (current_function_decl);
117 if (!profile_info || !flag_branch_probabilities)
119 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
121 if (node->frequency == NODE_FREQUENCY_HOT)
124 if (profile_status == PROFILE_ABSENT)
126 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
127 && freq <= (ENTRY_BLOCK_PTR->frequency * 2 / 3))
129 if (freq < ENTRY_BLOCK_PTR->frequency / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
134 /* Return TRUE if frequency FREQ is considered to be hot. */
137 maybe_hot_count_p (gcov_type count)
139 if (profile_status != PROFILE_READ)
141 /* Code executed at most once is not hot. */
142 if (profile_info->runs >= count)
145 > profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION));
148 /* Return true in case BB can be CPU intensive and should be optimized
149 for maximal performance. */
152 maybe_hot_bb_p (const_basic_block bb)
154 if (profile_status == PROFILE_READ)
155 return maybe_hot_count_p (bb->count);
156 return maybe_hot_frequency_p (bb->frequency);
159 /* Return true if the call can be hot. */
162 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
164 if (profile_info && flag_branch_probabilities
166 <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
168 if (edge->caller->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED
169 || edge->callee->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
171 if (edge->caller->frequency > NODE_FREQUENCY_UNLIKELY_EXECUTED
172 && edge->callee->frequency <= NODE_FREQUENCY_EXECUTED_ONCE)
176 if (edge->caller->frequency == NODE_FREQUENCY_HOT)
178 if (edge->caller->frequency == NODE_FREQUENCY_EXECUTED_ONCE
179 && edge->frequency < CGRAPH_FREQ_BASE * 3 / 2)
181 if (flag_guess_branch_prob
182 && edge->frequency <= (CGRAPH_FREQ_BASE
183 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
188 /* Return true in case BB can be CPU intensive and should be optimized
189 for maximal performance. */
192 maybe_hot_edge_p (edge e)
194 if (profile_status == PROFILE_READ)
195 return maybe_hot_count_p (e->count);
196 return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
199 /* Return true in case BB is probably never executed. */
201 probably_never_executed_bb_p (const_basic_block bb)
203 if (profile_info && flag_branch_probabilities)
204 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
205 if ((!profile_info || !flag_branch_probabilities)
206 && cgraph_node (current_function_decl)->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
211 /* Return true when current function should always be optimized for size. */
214 optimize_function_for_size_p (struct function *fun)
216 return (optimize_size
218 && (cgraph_node (fun->decl)->frequency
219 == NODE_FREQUENCY_UNLIKELY_EXECUTED)));
222 /* Return true when current function should always be optimized for speed. */
225 optimize_function_for_speed_p (struct function *fun)
227 return !optimize_function_for_size_p (fun);
230 /* Return TRUE when BB should be optimized for size. */
233 optimize_bb_for_size_p (const_basic_block bb)
235 return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (bb);
238 /* Return TRUE when BB should be optimized for speed. */
241 optimize_bb_for_speed_p (const_basic_block bb)
243 return !optimize_bb_for_size_p (bb);
246 /* Return TRUE when BB should be optimized for size. */
249 optimize_edge_for_size_p (edge e)
251 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
254 /* Return TRUE when BB should be optimized for speed. */
257 optimize_edge_for_speed_p (edge e)
259 return !optimize_edge_for_size_p (e);
262 /* Return TRUE when BB should be optimized for size. */
265 optimize_insn_for_size_p (void)
267 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
270 /* Return TRUE when BB should be optimized for speed. */
273 optimize_insn_for_speed_p (void)
275 return !optimize_insn_for_size_p ();
278 /* Return TRUE when LOOP should be optimized for size. */
281 optimize_loop_for_size_p (struct loop *loop)
283 return optimize_bb_for_size_p (loop->header);
286 /* Return TRUE when LOOP should be optimized for speed. */
289 optimize_loop_for_speed_p (struct loop *loop)
291 return optimize_bb_for_speed_p (loop->header);
294 /* Return TRUE when LOOP nest should be optimized for speed. */
297 optimize_loop_nest_for_speed_p (struct loop *loop)
299 struct loop *l = loop;
300 if (optimize_loop_for_speed_p (loop))
303 while (l && l != loop)
305 if (optimize_loop_for_speed_p (l))
313 while (l != loop && !l->next)
322 /* Return TRUE when LOOP nest should be optimized for size. */
325 optimize_loop_nest_for_size_p (struct loop *loop)
327 return !optimize_loop_nest_for_speed_p (loop);
330 /* Return true when edge E is likely to be well predictable by branch
334 predictable_edge_p (edge e)
336 if (profile_status == PROFILE_ABSENT)
339 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
340 || (REG_BR_PROB_BASE - e->probability
341 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
347 /* Set RTL expansion for BB profile. */
350 rtl_profile_for_bb (basic_block bb)
352 crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
355 /* Set RTL expansion for edge profile. */
358 rtl_profile_for_edge (edge e)
360 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
363 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
365 default_rtl_profile (void)
367 crtl->maybe_hot_insn_p = true;
370 /* Return true if the one of outgoing edges is already predicted by
374 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
377 if (!INSN_P (BB_END (bb)))
379 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
380 if (REG_NOTE_KIND (note) == REG_BR_PRED
381 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
386 /* This map contains for a basic block the list of predictions for the
389 static struct pointer_map_t *bb_predictions;
391 /* Structure representing predictions in tree level. */
393 struct edge_prediction {
394 struct edge_prediction *ep_next;
396 enum br_predictor ep_predictor;
400 /* Return true if the one of outgoing edges is already predicted by
404 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
406 struct edge_prediction *i;
407 void **preds = pointer_map_contains (bb_predictions, bb);
412 for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
413 if (i->ep_predictor == predictor)
418 /* Return true when the probability of edge is reliable.
420 The profile guessing code is good at predicting branch outcome (ie.
421 taken/not taken), that is predicted right slightly over 75% of time.
422 It is however notoriously poor on predicting the probability itself.
423 In general the profile appear a lot flatter (with probabilities closer
424 to 50%) than the reality so it is bad idea to use it to drive optimization
425 such as those disabling dynamic branch prediction for well predictable
428 There are two exceptions - edges leading to noreturn edges and edges
429 predicted by number of iterations heuristics are predicted well. This macro
430 should be able to distinguish those, but at the moment it simply check for
431 noreturn heuristic that is only one giving probability over 99% or bellow
432 1%. In future we might want to propagate reliability information across the
433 CFG if we find this information useful on multiple places. */
435 probability_reliable_p (int prob)
437 return (profile_status == PROFILE_READ
438 || (profile_status == PROFILE_GUESSED
439 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
442 /* Same predicate as above, working on edges. */
444 edge_probability_reliable_p (const_edge e)
446 return probability_reliable_p (e->probability);
449 /* Same predicate as edge_probability_reliable_p, working on notes. */
451 br_prob_note_reliable_p (const_rtx note)
453 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
454 return probability_reliable_p (INTVAL (XEXP (note, 0)));
458 predict_insn (rtx insn, enum br_predictor predictor, int probability)
460 gcc_assert (any_condjump_p (insn));
461 if (!flag_guess_branch_prob)
464 add_reg_note (insn, REG_BR_PRED,
465 gen_rtx_CONCAT (VOIDmode,
466 GEN_INT ((int) predictor),
467 GEN_INT ((int) probability)));
470 /* Predict insn by given predictor. */
473 predict_insn_def (rtx insn, enum br_predictor predictor,
474 enum prediction taken)
476 int probability = predictor_info[(int) predictor].hitrate;
479 probability = REG_BR_PROB_BASE - probability;
481 predict_insn (insn, predictor, probability);
484 /* Predict edge E with given probability if possible. */
487 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
490 last_insn = BB_END (e->src);
492 /* We can store the branch prediction information only about
493 conditional jumps. */
494 if (!any_condjump_p (last_insn))
497 /* We always store probability of branching. */
498 if (e->flags & EDGE_FALLTHRU)
499 probability = REG_BR_PROB_BASE - probability;
501 predict_insn (last_insn, predictor, probability);
504 /* Predict edge E with the given PROBABILITY. */
506 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
508 gcc_assert (profile_status != PROFILE_GUESSED);
509 if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
510 && flag_guess_branch_prob && optimize)
512 struct edge_prediction *i = XNEW (struct edge_prediction);
513 void **preds = pointer_map_insert (bb_predictions, e->src);
515 i->ep_next = (struct edge_prediction *) *preds;
517 i->ep_probability = probability;
518 i->ep_predictor = predictor;
523 /* Remove all predictions on given basic block that are attached
526 remove_predictions_associated_with_edge (edge e)
533 preds = pointer_map_contains (bb_predictions, e->src);
537 struct edge_prediction **prediction = (struct edge_prediction **) preds;
538 struct edge_prediction *next;
542 if ((*prediction)->ep_edge == e)
544 next = (*prediction)->ep_next;
549 prediction = &((*prediction)->ep_next);
554 /* Clears the list of predictions stored for BB. */
557 clear_bb_predictions (basic_block bb)
559 void **preds = pointer_map_contains (bb_predictions, bb);
560 struct edge_prediction *pred, *next;
565 for (pred = (struct edge_prediction *) *preds; pred; pred = next)
567 next = pred->ep_next;
573 /* Return true when we can store prediction on insn INSN.
574 At the moment we represent predictions only on conditional
575 jumps, not at computed jump or other complicated cases. */
577 can_predict_insn_p (const_rtx insn)
579 return (JUMP_P (insn)
580 && any_condjump_p (insn)
581 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
584 /* Predict edge E by given predictor if possible. */
587 predict_edge_def (edge e, enum br_predictor predictor,
588 enum prediction taken)
590 int probability = predictor_info[(int) predictor].hitrate;
593 probability = REG_BR_PROB_BASE - probability;
595 predict_edge (e, predictor, probability);
598 /* Invert all branch predictions or probability notes in the INSN. This needs
599 to be done each time we invert the condition used by the jump. */
602 invert_br_probabilities (rtx insn)
606 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
607 if (REG_NOTE_KIND (note) == REG_BR_PROB)
608 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
609 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
610 XEXP (XEXP (note, 0), 1)
611 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
614 /* Dump information about the branch prediction to the output file. */
617 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
618 basic_block bb, int used)
626 FOR_EACH_EDGE (e, ei, bb->succs)
627 if (! (e->flags & EDGE_FALLTHRU))
630 fprintf (file, " %s heuristics%s: %.1f%%",
631 predictor_info[predictor].name,
632 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
636 fprintf (file, " exec ");
637 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
640 fprintf (file, " hit ");
641 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
642 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
646 fprintf (file, "\n");
649 /* We can not predict the probabilities of outgoing edges of bb. Set them
650 evenly and hope for the best. */
652 set_even_probabilities (basic_block bb)
658 FOR_EACH_EDGE (e, ei, bb->succs)
659 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
661 FOR_EACH_EDGE (e, ei, bb->succs)
662 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
663 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
668 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
669 note if not already present. Remove now useless REG_BR_PRED notes. */
672 combine_predictions_for_insn (rtx insn, basic_block bb)
677 int best_probability = PROB_EVEN;
678 enum br_predictor best_predictor = END_PREDICTORS;
679 int combined_probability = REG_BR_PROB_BASE / 2;
681 bool first_match = false;
684 if (!can_predict_insn_p (insn))
686 set_even_probabilities (bb);
690 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
691 pnote = ®_NOTES (insn);
693 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
696 /* We implement "first match" heuristics and use probability guessed
697 by predictor with smallest index. */
698 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
699 if (REG_NOTE_KIND (note) == REG_BR_PRED)
701 enum br_predictor predictor = ((enum br_predictor)
702 INTVAL (XEXP (XEXP (note, 0), 0)));
703 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
706 if (best_predictor > predictor)
707 best_probability = probability, best_predictor = predictor;
709 d = (combined_probability * probability
710 + (REG_BR_PROB_BASE - combined_probability)
711 * (REG_BR_PROB_BASE - probability));
713 /* Use FP math to avoid overflows of 32bit integers. */
715 /* If one probability is 0% and one 100%, avoid division by zero. */
716 combined_probability = REG_BR_PROB_BASE / 2;
718 combined_probability = (((double) combined_probability) * probability
719 * REG_BR_PROB_BASE / d + 0.5);
722 /* Decide which heuristic to use. In case we didn't match anything,
723 use no_prediction heuristic, in case we did match, use either
724 first match or Dempster-Shaffer theory depending on the flags. */
726 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
730 dump_prediction (dump_file, PRED_NO_PREDICTION,
731 combined_probability, bb, true);
734 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
736 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
741 combined_probability = best_probability;
742 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
746 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
748 enum br_predictor predictor = ((enum br_predictor)
749 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
750 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
752 dump_prediction (dump_file, predictor, probability, bb,
753 !first_match || best_predictor == predictor);
754 *pnote = XEXP (*pnote, 1);
757 pnote = &XEXP (*pnote, 1);
762 add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
764 /* Save the prediction into CFG in case we are seeing non-degenerated
766 if (!single_succ_p (bb))
768 BRANCH_EDGE (bb)->probability = combined_probability;
769 FALLTHRU_EDGE (bb)->probability
770 = REG_BR_PROB_BASE - combined_probability;
773 else if (!single_succ_p (bb))
775 int prob = INTVAL (XEXP (prob_note, 0));
777 BRANCH_EDGE (bb)->probability = prob;
778 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
781 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
784 /* Combine predictions into single probability and store them into CFG.
785 Remove now useless prediction entries. */
788 combine_predictions_for_bb (basic_block bb)
790 int best_probability = PROB_EVEN;
791 enum br_predictor best_predictor = END_PREDICTORS;
792 int combined_probability = REG_BR_PROB_BASE / 2;
794 bool first_match = false;
796 struct edge_prediction *pred;
798 edge e, first = NULL, second = NULL;
802 FOR_EACH_EDGE (e, ei, bb->succs)
803 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
806 if (first && !second)
812 /* When there is no successor or only one choice, prediction is easy.
814 We are lazy for now and predict only basic blocks with two outgoing
815 edges. It is possible to predict generic case too, but we have to
816 ignore first match heuristics and do more involved combining. Implement
821 set_even_probabilities (bb);
822 clear_bb_predictions (bb);
824 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
830 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
832 preds = pointer_map_contains (bb_predictions, bb);
835 /* We implement "first match" heuristics and use probability guessed
836 by predictor with smallest index. */
837 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
839 enum br_predictor predictor = pred->ep_predictor;
840 int probability = pred->ep_probability;
842 if (pred->ep_edge != first)
843 probability = REG_BR_PROB_BASE - probability;
846 /* First match heuristics would be widly confused if we predicted
848 if (best_predictor > predictor)
850 struct edge_prediction *pred2;
851 int prob = probability;
853 for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 = pred2->ep_next)
854 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
856 int probability2 = pred->ep_probability;
858 if (pred2->ep_edge != first)
859 probability2 = REG_BR_PROB_BASE - probability2;
861 if ((probability < REG_BR_PROB_BASE / 2) !=
862 (probability2 < REG_BR_PROB_BASE / 2))
865 /* If the same predictor later gave better result, go for it! */
866 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
867 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
871 best_probability = prob, best_predictor = predictor;
874 d = (combined_probability * probability
875 + (REG_BR_PROB_BASE - combined_probability)
876 * (REG_BR_PROB_BASE - probability));
878 /* Use FP math to avoid overflows of 32bit integers. */
880 /* If one probability is 0% and one 100%, avoid division by zero. */
881 combined_probability = REG_BR_PROB_BASE / 2;
883 combined_probability = (((double) combined_probability)
885 * REG_BR_PROB_BASE / d + 0.5);
889 /* Decide which heuristic to use. In case we didn't match anything,
890 use no_prediction heuristic, in case we did match, use either
891 first match or Dempster-Shaffer theory depending on the flags. */
893 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
897 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
900 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
902 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
907 combined_probability = best_probability;
908 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
912 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
914 enum br_predictor predictor = pred->ep_predictor;
915 int probability = pred->ep_probability;
917 if (pred->ep_edge != EDGE_SUCC (bb, 0))
918 probability = REG_BR_PROB_BASE - probability;
919 dump_prediction (dump_file, predictor, probability, bb,
920 !first_match || best_predictor == predictor);
923 clear_bb_predictions (bb);
927 first->probability = combined_probability;
928 second->probability = REG_BR_PROB_BASE - combined_probability;
932 /* Predict edge probabilities by exploiting loop structure. */
940 /* Try to predict out blocks in a loop that are not part of a
942 FOR_EACH_LOOP (li, loop, 0)
944 basic_block bb, *bbs;
946 VEC (edge, heap) *exits;
947 struct tree_niter_desc niter_desc;
950 exits = get_loop_exit_edges (loop);
951 n_exits = VEC_length (edge, exits);
953 FOR_EACH_VEC_ELT (edge, exits, j, ex)
956 HOST_WIDE_INT nitercst;
957 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
959 enum br_predictor predictor;
961 if (number_of_iterations_exit (loop, ex, &niter_desc, false))
962 niter = niter_desc.niter;
963 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
964 niter = loop_niter_by_eval (loop, ex);
966 if (TREE_CODE (niter) == INTEGER_CST)
968 if (host_integerp (niter, 1)
969 && compare_tree_int (niter, max-1) == -1)
970 nitercst = tree_low_cst (niter, 1) + 1;
973 predictor = PRED_LOOP_ITERATIONS;
975 /* If we have just one exit and we can derive some information about
976 the number of iterations of the loop from the statements inside
977 the loop, use it to predict this exit. */
978 else if (n_exits == 1)
980 nitercst = estimated_loop_iterations_int (loop, false);
986 predictor = PRED_LOOP_ITERATIONS_GUESSED;
991 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
992 predict_edge (ex, predictor, probability);
994 VEC_free (edge, heap, exits);
996 bbs = get_loop_body (loop);
998 for (j = 0; j < loop->num_nodes; j++)
1000 int header_found = 0;
1006 /* Bypass loop heuristics on continue statement. These
1007 statements construct loops via "non-loop" constructs
1008 in the source language and are better to be handled
1010 if (predicted_by_p (bb, PRED_CONTINUE))
1013 /* Loop branch heuristics - predict an edge back to a
1014 loop's head as taken. */
1015 if (bb == loop->latch)
1017 e = find_edge (loop->latch, loop->header);
1021 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
1025 /* Loop exit heuristics - predict an edge exiting the loop if the
1026 conditional has no loop header successors as not taken. */
1028 /* If we already used more reliable loop exit predictors, do not
1029 bother with PRED_LOOP_EXIT. */
1030 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1031 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
1033 /* For loop with many exits we don't want to predict all exits
1034 with the pretty large probability, because if all exits are
1035 considered in row, the loop would be predicted to iterate
1036 almost never. The code to divide probability by number of
1037 exits is very rough. It should compute the number of exits
1038 taken in each patch through function (not the overall number
1039 of exits that might be a lot higher for loops with wide switch
1040 statements in them) and compute n-th square root.
1042 We limit the minimal probability by 2% to avoid
1043 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1044 as this was causing regression in perl benchmark containing such
1047 int probability = ((REG_BR_PROB_BASE
1048 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
1050 if (probability < HITRATE (2))
1051 probability = HITRATE (2);
1052 FOR_EACH_EDGE (e, ei, bb->succs)
1053 if (e->dest->index < NUM_FIXED_BLOCKS
1054 || !flow_bb_inside_loop_p (loop, e->dest))
1055 predict_edge (e, PRED_LOOP_EXIT, probability);
1059 /* Free basic blocks from get_loop_body. */
1064 /* Attempt to predict probabilities of BB outgoing edges using local
1067 bb_estimate_probability_locally (basic_block bb)
1069 rtx last_insn = BB_END (bb);
1072 if (! can_predict_insn_p (last_insn))
1074 cond = get_condition (last_insn, NULL, false, false);
1078 /* Try "pointer heuristic."
1079 A comparison ptr == 0 is predicted as false.
1080 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1081 if (COMPARISON_P (cond)
1082 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
1083 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1085 if (GET_CODE (cond) == EQ)
1086 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1087 else if (GET_CODE (cond) == NE)
1088 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1092 /* Try "opcode heuristic."
1093 EQ tests are usually false and NE tests are usually true. Also,
1094 most quantities are positive, so we can make the appropriate guesses
1095 about signed comparisons against zero. */
1096 switch (GET_CODE (cond))
1099 /* Unconditional branch. */
1100 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1101 cond == const0_rtx ? NOT_TAKEN : TAKEN);
1106 /* Floating point comparisons appears to behave in a very
1107 unpredictable way because of special role of = tests in
1109 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1111 /* Comparisons with 0 are often used for booleans and there is
1112 nothing useful to predict about them. */
1113 else if (XEXP (cond, 1) == const0_rtx
1114 || XEXP (cond, 0) == const0_rtx)
1117 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1122 /* Floating point comparisons appears to behave in a very
1123 unpredictable way because of special role of = tests in
1125 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1127 /* Comparisons with 0 are often used for booleans and there is
1128 nothing useful to predict about them. */
1129 else if (XEXP (cond, 1) == const0_rtx
1130 || XEXP (cond, 0) == const0_rtx)
1133 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1137 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1141 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1146 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1147 || XEXP (cond, 1) == constm1_rtx)
1148 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1153 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1154 || XEXP (cond, 1) == constm1_rtx)
1155 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1163 /* Set edge->probability for each successor edge of BB. */
1165 guess_outgoing_edge_probabilities (basic_block bb)
1167 bb_estimate_probability_locally (bb);
1168 combine_predictions_for_insn (BB_END (bb), bb);
1171 static tree expr_expected_value (tree, bitmap);
1173 /* Helper function for expr_expected_value. */
1176 expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited)
1180 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1182 if (TREE_CONSTANT (op0))
1185 if (code != SSA_NAME)
1188 def = SSA_NAME_DEF_STMT (op0);
1190 /* If we were already here, break the infinite cycle. */
1191 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
1194 if (gimple_code (def) == GIMPLE_PHI)
1196 /* All the arguments of the PHI node must have the same constant
1198 int i, n = gimple_phi_num_args (def);
1199 tree val = NULL, new_val;
1201 for (i = 0; i < n; i++)
1203 tree arg = PHI_ARG_DEF (def, i);
1205 /* If this PHI has itself as an argument, we cannot
1206 determine the string length of this argument. However,
1207 if we can find an expected constant value for the other
1208 PHI args then we can still be sure that this is
1209 likely a constant. So be optimistic and just
1210 continue with the next argument. */
1211 if (arg == PHI_RESULT (def))
1214 new_val = expr_expected_value (arg, visited);
1219 else if (!operand_equal_p (val, new_val, false))
1224 if (is_gimple_assign (def))
1226 if (gimple_assign_lhs (def) != op0)
1229 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1230 gimple_assign_rhs1 (def),
1231 gimple_assign_rhs_code (def),
1232 gimple_assign_rhs2 (def),
1236 if (is_gimple_call (def))
1238 tree decl = gimple_call_fndecl (def);
1241 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
1242 && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
1246 if (gimple_call_num_args (def) != 2)
1248 val = gimple_call_arg (def, 0);
1249 if (TREE_CONSTANT (val))
1251 return gimple_call_arg (def, 1);
1258 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1261 op0 = expr_expected_value (op0, visited);
1264 op1 = expr_expected_value (op1, visited);
1267 res = fold_build2 (code, type, op0, op1);
1268 if (TREE_CONSTANT (res))
1272 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1275 op0 = expr_expected_value (op0, visited);
1278 res = fold_build1 (code, type, op0);
1279 if (TREE_CONSTANT (res))
1286 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1287 The function is used by builtin_expect branch predictor so the evidence
1288 must come from this construct and additional possible constant folding.
1290 We may want to implement more involved value guess (such as value range
1291 propagation based prediction), but such tricks shall go to new
1295 expr_expected_value (tree expr, bitmap visited)
1297 enum tree_code code;
1300 if (TREE_CONSTANT (expr))
1303 extract_ops_from_tree (expr, &code, &op0, &op1);
1304 return expr_expected_value_1 (TREE_TYPE (expr),
1305 op0, code, op1, visited);
1309 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1310 we no longer need. */
1312 strip_predict_hints (void)
1320 gimple_stmt_iterator bi;
1321 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
1323 gimple stmt = gsi_stmt (bi);
1325 if (gimple_code (stmt) == GIMPLE_PREDICT)
1327 gsi_remove (&bi, true);
1330 else if (gimple_code (stmt) == GIMPLE_CALL)
1332 tree fndecl = gimple_call_fndecl (stmt);
1335 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1336 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1337 && gimple_call_num_args (stmt) == 2)
1339 var = gimple_call_lhs (stmt);
1343 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
1344 gsi_replace (&bi, ass_stmt, true);
1348 gsi_remove (&bi, true);
1359 /* Predict using opcode of the last statement in basic block. */
1361 tree_predict_by_opcode (basic_block bb)
1363 gimple stmt = last_stmt (bb);
1372 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1374 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1375 if (then_edge->flags & EDGE_TRUE_VALUE)
1377 op0 = gimple_cond_lhs (stmt);
1378 op1 = gimple_cond_rhs (stmt);
1379 cmp = gimple_cond_code (stmt);
1380 type = TREE_TYPE (op0);
1381 visited = BITMAP_ALLOC (NULL);
1382 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
1383 BITMAP_FREE (visited);
1386 if (integer_zerop (val))
1387 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1389 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1392 /* Try "pointer heuristic."
1393 A comparison ptr == 0 is predicted as false.
1394 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1395 if (POINTER_TYPE_P (type))
1398 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1399 else if (cmp == NE_EXPR)
1400 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1404 /* Try "opcode heuristic."
1405 EQ tests are usually false and NE tests are usually true. Also,
1406 most quantities are positive, so we can make the appropriate guesses
1407 about signed comparisons against zero. */
1412 /* Floating point comparisons appears to behave in a very
1413 unpredictable way because of special role of = tests in
1415 if (FLOAT_TYPE_P (type))
1417 /* Comparisons with 0 are often used for booleans and there is
1418 nothing useful to predict about them. */
1419 else if (integer_zerop (op0) || integer_zerop (op1))
1422 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1427 /* Floating point comparisons appears to behave in a very
1428 unpredictable way because of special role of = tests in
1430 if (FLOAT_TYPE_P (type))
1432 /* Comparisons with 0 are often used for booleans and there is
1433 nothing useful to predict about them. */
1434 else if (integer_zerop (op0)
1435 || integer_zerop (op1))
1438 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1442 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1445 case UNORDERED_EXPR:
1446 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1451 if (integer_zerop (op1)
1452 || integer_onep (op1)
1453 || integer_all_onesp (op1)
1456 || real_minus_onep (op1))
1457 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1462 if (integer_zerop (op1)
1463 || integer_onep (op1)
1464 || integer_all_onesp (op1)
1467 || real_minus_onep (op1))
1468 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1476 /* Try to guess whether the value of return means error code. */
1478 static enum br_predictor
1479 return_prediction (tree val, enum prediction *prediction)
1483 return PRED_NO_PREDICTION;
1484 /* Different heuristics for pointers and scalars. */
1485 if (POINTER_TYPE_P (TREE_TYPE (val)))
1487 /* NULL is usually not returned. */
1488 if (integer_zerop (val))
1490 *prediction = NOT_TAKEN;
1491 return PRED_NULL_RETURN;
1494 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1496 /* Negative return values are often used to indicate
1498 if (TREE_CODE (val) == INTEGER_CST
1499 && tree_int_cst_sgn (val) < 0)
1501 *prediction = NOT_TAKEN;
1502 return PRED_NEGATIVE_RETURN;
1504 /* Constant return values seems to be commonly taken.
1505 Zero/one often represent booleans so exclude them from the
1507 if (TREE_CONSTANT (val)
1508 && (!integer_zerop (val) && !integer_onep (val)))
1510 *prediction = TAKEN;
1511 return PRED_CONST_RETURN;
1514 return PRED_NO_PREDICTION;
1517 /* Find the basic block with return expression and look up for possible
1518 return value trying to apply RETURN_PREDICTION heuristics. */
1520 apply_return_prediction (void)
1522 gimple return_stmt = NULL;
1526 int phi_num_args, i;
1527 enum br_predictor pred;
1528 enum prediction direction;
1531 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1533 return_stmt = last_stmt (e->src);
1535 && gimple_code (return_stmt) == GIMPLE_RETURN)
1540 return_val = gimple_return_retval (return_stmt);
1543 if (TREE_CODE (return_val) != SSA_NAME
1544 || !SSA_NAME_DEF_STMT (return_val)
1545 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
1547 phi = SSA_NAME_DEF_STMT (return_val);
1548 phi_num_args = gimple_phi_num_args (phi);
1549 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1551 /* Avoid the degenerate case where all return values form the function
1552 belongs to same category (ie they are all positive constants)
1553 so we can hardly say something about them. */
1554 for (i = 1; i < phi_num_args; i++)
1555 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1557 if (i != phi_num_args)
1558 for (i = 0; i < phi_num_args; i++)
1560 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1561 if (pred != PRED_NO_PREDICTION)
1562 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
1567 /* Look for basic block that contains unlikely to happen events
1568 (such as noreturn calls) and mark all paths leading to execution
1569 of this basic blocks as unlikely. */
1572 tree_bb_level_predictions (void)
1575 bool has_return_edges = false;
1579 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1580 if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
1582 has_return_edges = true;
1586 apply_return_prediction ();
1590 gimple_stmt_iterator gsi;
1592 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1594 gimple stmt = gsi_stmt (gsi);
1597 if (is_gimple_call (stmt))
1599 if ((gimple_call_flags (stmt) & ECF_NORETURN)
1600 && has_return_edges)
1601 predict_paths_leading_to (bb, PRED_NORETURN,
1603 decl = gimple_call_fndecl (stmt);
1605 && lookup_attribute ("cold",
1606 DECL_ATTRIBUTES (decl)))
1607 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
1610 else if (gimple_code (stmt) == GIMPLE_PREDICT)
1612 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
1613 gimple_predict_outcome (stmt));
1614 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1615 hints to callers. */
1621 #ifdef ENABLE_CHECKING
1623 /* Callback for pointer_map_traverse, asserts that the pointer map is
1627 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1628 void *data ATTRIBUTE_UNUSED)
1630 gcc_assert (!*value);
1635 /* Predict branch probabilities and estimate profile for basic block BB. */
1638 tree_estimate_probability_bb (basic_block bb)
1644 FOR_EACH_EDGE (e, ei, bb->succs)
1646 /* Predict early returns to be probable, as we've already taken
1647 care for error returns and other cases are often used for
1648 fast paths through function.
1650 Since we've already removed the return statements, we are
1651 looking for CFG like:
1661 if (e->dest != bb->next_bb
1662 && e->dest != EXIT_BLOCK_PTR
1663 && single_succ_p (e->dest)
1664 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1665 && (last = last_stmt (e->dest)) != NULL
1666 && gimple_code (last) == GIMPLE_RETURN)
1671 if (single_succ_p (bb))
1673 FOR_EACH_EDGE (e1, ei1, bb->preds)
1674 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1675 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1676 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1677 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1680 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1681 && !predicted_by_p (e->src, PRED_CONST_RETURN)
1682 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1683 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1686 /* Look for block we are guarding (ie we dominate it,
1687 but it doesn't postdominate us). */
1688 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1689 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1690 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1692 gimple_stmt_iterator bi;
1694 /* The call heuristic claims that a guarded function call
1695 is improbable. This is because such calls are often used
1696 to signal exceptional situations such as printing error
1698 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
1701 gimple stmt = gsi_stmt (bi);
1702 if (is_gimple_call (stmt)
1703 /* Constant and pure calls are hardly used to signalize
1704 something exceptional. */
1705 && gimple_has_side_effects (stmt))
1707 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1713 tree_predict_by_opcode (bb);
1716 /* Predict branch probabilities and estimate profile of the tree CFG.
1717 This function can be called from the loop optimizers to recompute
1718 the profile information. */
1721 tree_estimate_probability (void)
1725 add_noreturn_fake_exit_edges ();
1726 connect_infinite_loops_to_exit ();
1727 /* We use loop_niter_by_eval, which requires that the loops have
1729 create_preheaders (CP_SIMPLE_PREHEADERS);
1730 calculate_dominance_info (CDI_POST_DOMINATORS);
1732 bb_predictions = pointer_map_create ();
1733 tree_bb_level_predictions ();
1734 record_loop_exits ();
1736 if (number_of_loops () > 1)
1740 tree_estimate_probability_bb (bb);
1743 combine_predictions_for_bb (bb);
1745 #ifdef ENABLE_CHECKING
1746 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1748 pointer_map_destroy (bb_predictions);
1749 bb_predictions = NULL;
1751 estimate_bb_frequencies ();
1752 free_dominance_info (CDI_POST_DOMINATORS);
1753 remove_fake_exit_edges ();
1756 /* Predict branch probabilities and estimate profile of the tree CFG.
1757 This is the driver function for PASS_PROFILE. */
1760 tree_estimate_probability_driver (void)
1764 loop_optimizer_init (0);
1765 if (dump_file && (dump_flags & TDF_DETAILS))
1766 flow_loops_dump (dump_file, NULL, 0);
1768 mark_irreducible_loops ();
1770 nb_loops = number_of_loops ();
1774 tree_estimate_probability ();
1779 loop_optimizer_finalize ();
1780 if (dump_file && (dump_flags & TDF_DETAILS))
1781 gimple_dump_cfg (dump_file, dump_flags);
1782 if (profile_status == PROFILE_ABSENT)
1783 profile_status = PROFILE_GUESSED;
1787 /* Predict edges to successors of CUR whose sources are not postdominated by
1788 BB by PRED and recurse to all postdominators. */
1791 predict_paths_for_bb (basic_block cur, basic_block bb,
1792 enum br_predictor pred,
1793 enum prediction taken,
1800 /* We are looking for all edges forming edge cut induced by
1801 set of all blocks postdominated by BB. */
1802 FOR_EACH_EDGE (e, ei, cur->preds)
1803 if (e->src->index >= NUM_FIXED_BLOCKS
1804 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
1810 /* Ignore fake edges and eh, we predict them as not taken anyway. */
1811 if (e->flags & (EDGE_EH | EDGE_FAKE))
1813 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
1815 /* See if there is an edge from e->src that is not abnormal
1816 and does not lead to BB. */
1817 FOR_EACH_EDGE (e2, ei2, e->src->succs)
1819 && !(e2->flags & (EDGE_EH | EDGE_FAKE))
1820 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
1826 /* If there is non-abnormal path leaving e->src, predict edge
1827 using predictor. Otherwise we need to look for paths
1830 The second may lead to infinite loop in the case we are predicitng
1831 regions that are only reachable by abnormal edges. We simply
1832 prevent visiting given BB twice. */
1834 predict_edge_def (e, pred, taken);
1835 else if (bitmap_set_bit (visited, e->src->index))
1836 predict_paths_for_bb (e->src, e->src, pred, taken, visited);
1838 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
1840 son = next_dom_son (CDI_POST_DOMINATORS, son))
1841 predict_paths_for_bb (son, bb, pred, taken, visited);
1844 /* Sets branch probabilities according to PREDiction and
1848 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
1849 enum prediction taken)
1851 bitmap visited = BITMAP_ALLOC (NULL);
1852 predict_paths_for_bb (bb, bb, pred, taken, visited);
1853 BITMAP_FREE (visited);
1856 /* Like predict_paths_leading_to but take edge instead of basic block. */
1859 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
1860 enum prediction taken)
1862 bool has_nonloop_edge = false;
1866 basic_block bb = e->src;
1867 FOR_EACH_EDGE (e2, ei, bb->succs)
1868 if (e2->dest != e->src && e2->dest != e->dest
1869 && !(e->flags & (EDGE_EH | EDGE_FAKE))
1870 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
1872 has_nonloop_edge = true;
1875 if (!has_nonloop_edge)
1877 bitmap visited = BITMAP_ALLOC (NULL);
1878 predict_paths_for_bb (bb, bb, pred, taken, visited);
1879 BITMAP_FREE (visited);
1882 predict_edge_def (e, pred, taken);
1885 /* This is used to carry information about basic blocks. It is
1886 attached to the AUX field of the standard CFG block. */
1888 typedef struct block_info_def
1890 /* Estimated frequency of execution of basic_block. */
1893 /* To keep queue of basic blocks to process. */
1896 /* Number of predecessors we need to visit first. */
1900 /* Similar information for edges. */
1901 typedef struct edge_info_def
1903 /* In case edge is a loopback edge, the probability edge will be reached
1904 in case header is. Estimated number of iterations of the loop can be
1905 then computed as 1 / (1 - back_edge_prob). */
1906 sreal back_edge_prob;
1907 /* True if the edge is a loopback edge in the natural loop. */
1908 unsigned int back_edge:1;
1911 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1912 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1914 /* Helper function for estimate_bb_frequencies.
1915 Propagate the frequencies in blocks marked in
1916 TOVISIT, starting in HEAD. */
1919 propagate_freq (basic_block head, bitmap tovisit)
1928 /* For each basic block we need to visit count number of his predecessors
1929 we need to visit first. */
1930 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1935 bb = BASIC_BLOCK (i);
1937 FOR_EACH_EDGE (e, ei, bb->preds)
1939 bool visit = bitmap_bit_p (tovisit, e->src->index);
1941 if (visit && !(e->flags & EDGE_DFS_BACK))
1943 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1945 "Irreducible region hit, ignoring edge to %i->%i\n",
1946 e->src->index, bb->index);
1948 BLOCK_INFO (bb)->npredecessors = count;
1949 /* When function never returns, we will never process exit block. */
1950 if (!count && bb == EXIT_BLOCK_PTR)
1951 bb->count = bb->frequency = 0;
1954 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1956 for (bb = head; bb; bb = nextbb)
1959 sreal cyclic_probability, frequency;
1961 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1962 memcpy (&frequency, &real_zero, sizeof (real_zero));
1964 nextbb = BLOCK_INFO (bb)->next;
1965 BLOCK_INFO (bb)->next = NULL;
1967 /* Compute frequency of basic block. */
1970 #ifdef ENABLE_CHECKING
1971 FOR_EACH_EDGE (e, ei, bb->preds)
1972 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1973 || (e->flags & EDGE_DFS_BACK));
1976 FOR_EACH_EDGE (e, ei, bb->preds)
1977 if (EDGE_INFO (e)->back_edge)
1979 sreal_add (&cyclic_probability, &cyclic_probability,
1980 &EDGE_INFO (e)->back_edge_prob);
1982 else if (!(e->flags & EDGE_DFS_BACK))
1986 /* frequency += (e->probability
1987 * BLOCK_INFO (e->src)->frequency /
1988 REG_BR_PROB_BASE); */
1990 sreal_init (&tmp, e->probability, 0);
1991 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1992 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1993 sreal_add (&frequency, &frequency, &tmp);
1996 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1998 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1999 sizeof (frequency));
2003 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
2005 memcpy (&cyclic_probability, &real_almost_one,
2006 sizeof (real_almost_one));
2009 /* BLOCK_INFO (bb)->frequency = frequency
2010 / (1 - cyclic_probability) */
2012 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
2013 sreal_div (&BLOCK_INFO (bb)->frequency,
2014 &frequency, &cyclic_probability);
2018 bitmap_clear_bit (tovisit, bb->index);
2020 e = find_edge (bb, head);
2025 /* EDGE_INFO (e)->back_edge_prob
2026 = ((e->probability * BLOCK_INFO (bb)->frequency)
2027 / REG_BR_PROB_BASE); */
2029 sreal_init (&tmp, e->probability, 0);
2030 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
2031 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2032 &tmp, &real_inv_br_prob_base);
2035 /* Propagate to successor blocks. */
2036 FOR_EACH_EDGE (e, ei, bb->succs)
2037 if (!(e->flags & EDGE_DFS_BACK)
2038 && BLOCK_INFO (e->dest)->npredecessors)
2040 BLOCK_INFO (e->dest)->npredecessors--;
2041 if (!BLOCK_INFO (e->dest)->npredecessors)
2046 BLOCK_INFO (last)->next = e->dest;
2054 /* Estimate probabilities of loopback edges in loops at same nest level. */
2057 estimate_loops_at_level (struct loop *first_loop)
2061 for (loop = first_loop; loop; loop = loop->next)
2066 bitmap tovisit = BITMAP_ALLOC (NULL);
2068 estimate_loops_at_level (loop->inner);
2070 /* Find current loop back edge and mark it. */
2071 e = loop_latch_edge (loop);
2072 EDGE_INFO (e)->back_edge = 1;
2074 bbs = get_loop_body (loop);
2075 for (i = 0; i < loop->num_nodes; i++)
2076 bitmap_set_bit (tovisit, bbs[i]->index);
2078 propagate_freq (loop->header, tovisit);
2079 BITMAP_FREE (tovisit);
2083 /* Propagates frequencies through structure of loops. */
2086 estimate_loops (void)
2088 bitmap tovisit = BITMAP_ALLOC (NULL);
2091 /* Start by estimating the frequencies in the loops. */
2092 if (number_of_loops () > 1)
2093 estimate_loops_at_level (current_loops->tree_root->inner);
2095 /* Now propagate the frequencies through all the blocks. */
2098 bitmap_set_bit (tovisit, bb->index);
2100 propagate_freq (ENTRY_BLOCK_PTR, tovisit);
2101 BITMAP_FREE (tovisit);
2104 /* Convert counts measured by profile driven feedback to frequencies.
2105 Return nonzero iff there was any nonzero execution count. */
2108 counts_to_freqs (void)
2110 gcov_type count_max, true_count_max = 0;
2113 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2114 true_count_max = MAX (bb->count, true_count_max);
2116 count_max = MAX (true_count_max, 1);
2117 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2118 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
2120 return true_count_max;
2123 /* Return true if function is likely to be expensive, so there is no point to
2124 optimize performance of prologue, epilogue or do inlining at the expense
2125 of code size growth. THRESHOLD is the limit of number of instructions
2126 function can execute at average to be still considered not expensive. */
2129 expensive_function_p (int threshold)
2131 unsigned int sum = 0;
2135 /* We can not compute accurately for large thresholds due to scaled
2137 gcc_assert (threshold <= BB_FREQ_MAX);
2139 /* Frequencies are out of range. This either means that function contains
2140 internal loop executing more than BB_FREQ_MAX times or profile feedback
2141 is available and function has not been executed at all. */
2142 if (ENTRY_BLOCK_PTR->frequency == 0)
2145 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2146 limit = ENTRY_BLOCK_PTR->frequency * threshold;
2151 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2152 insn = NEXT_INSN (insn))
2153 if (active_insn_p (insn))
2155 sum += bb->frequency;
2164 /* Estimate basic blocks frequency by given branch probabilities. */
2167 estimate_bb_frequencies (void)
2172 if (profile_status != PROFILE_READ || !counts_to_freqs ())
2174 static int real_values_initialized = 0;
2176 if (!real_values_initialized)
2178 real_values_initialized = 1;
2179 sreal_init (&real_zero, 0, 0);
2180 sreal_init (&real_one, 1, 0);
2181 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
2182 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
2183 sreal_init (&real_one_half, 1, -1);
2184 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
2185 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
2188 mark_dfs_back_edges ();
2190 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
2192 /* Set up block info for each basic block. */
2193 alloc_aux_for_blocks (sizeof (struct block_info_def));
2194 alloc_aux_for_edges (sizeof (struct edge_info_def));
2195 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2200 FOR_EACH_EDGE (e, ei, bb->succs)
2202 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
2203 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2204 &EDGE_INFO (e)->back_edge_prob,
2205 &real_inv_br_prob_base);
2209 /* First compute probabilities locally for each loop from innermost
2210 to outermost to examine probabilities for back edges. */
2213 memcpy (&freq_max, &real_zero, sizeof (real_zero));
2215 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
2216 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
2218 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
2219 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2223 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
2224 sreal_add (&tmp, &tmp, &real_one_half);
2225 bb->frequency = sreal_to_int (&tmp);
2228 free_aux_for_blocks ();
2229 free_aux_for_edges ();
2231 compute_function_frequency ();
2234 /* Decide whether function is hot, cold or unlikely executed. */
2236 compute_function_frequency (void)
2239 struct cgraph_node *node = cgraph_node (current_function_decl);
2240 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2241 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
2242 node->only_called_at_startup = true;
2243 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
2244 node->only_called_at_exit = true;
2246 if (!profile_info || !flag_branch_probabilities)
2248 int flags = flags_from_decl_or_type (current_function_decl);
2249 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2251 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2252 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2254 node->frequency = NODE_FREQUENCY_HOT;
2255 else if (flags & ECF_NORETURN)
2256 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2257 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
2258 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2259 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2260 || DECL_STATIC_DESTRUCTOR (current_function_decl))
2261 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2264 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2267 if (maybe_hot_bb_p (bb))
2269 node->frequency = NODE_FREQUENCY_HOT;
2272 if (!probably_never_executed_bb_p (bb))
2273 node->frequency = NODE_FREQUENCY_NORMAL;
2278 gate_estimate_probability (void)
2280 return flag_guess_branch_prob;
2283 /* Build PREDICT_EXPR. */
2285 build_predict_expr (enum br_predictor predictor, enum prediction taken)
2287 tree t = build1 (PREDICT_EXPR, void_type_node,
2288 build_int_cst (NULL, predictor));
2289 SET_PREDICT_EXPR_OUTCOME (t, taken);
2294 predictor_name (enum br_predictor predictor)
2296 return predictor_info[predictor].name;
2299 struct gimple_opt_pass pass_profile =
2303 "profile", /* name */
2304 gate_estimate_probability, /* gate */
2305 tree_estimate_probability_driver, /* execute */
2308 0, /* static_pass_number */
2309 TV_BRANCH_PROB, /* tv_id */
2310 PROP_cfg, /* properties_required */
2311 0, /* properties_provided */
2312 0, /* properties_destroyed */
2313 0, /* todo_flags_start */
2314 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2318 struct gimple_opt_pass pass_strip_predict_hints =
2322 "*strip_predict_hints", /* name */
2324 strip_predict_hints, /* execute */
2327 0, /* static_pass_number */
2328 TV_BRANCH_PROB, /* tv_id */
2329 PROP_cfg, /* properties_required */
2330 0, /* properties_provided */
2331 0, /* properties_destroyed */
2332 0, /* todo_flags_start */
2333 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2337 /* Rebuild function frequencies. Passes are in general expected to
2338 maintain profile by hand, however in some cases this is not possible:
2339 for example when inlining several functions with loops freuqencies might run
2340 out of scale and thus needs to be recomputed. */
2343 rebuild_frequencies (void)
2345 timevar_push (TV_REBUILD_FREQUENCIES);
2346 if (profile_status == PROFILE_GUESSED)
2348 loop_optimizer_init (0);
2349 add_noreturn_fake_exit_edges ();
2350 mark_irreducible_loops ();
2351 connect_infinite_loops_to_exit ();
2352 estimate_bb_frequencies ();
2353 remove_fake_exit_edges ();
2354 loop_optimizer_finalize ();
2356 else if (profile_status == PROFILE_READ)
2360 timevar_pop (TV_REBUILD_FREQUENCIES);