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_get_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_get_node (current_function_decl)->frequency
207 == NODE_FREQUENCY_UNLIKELY_EXECUTED))
212 /* Return true when current function should always be optimized for size. */
215 optimize_function_for_size_p (struct function *fun)
217 struct cgraph_node *node;
221 if (!fun || !fun->decl)
223 node = cgraph_get_node (fun->decl);
224 if (node && (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED))
230 /* Return true when current function should always be optimized for speed. */
233 optimize_function_for_speed_p (struct function *fun)
235 return !optimize_function_for_size_p (fun);
238 /* Return TRUE when BB should be optimized for size. */
241 optimize_bb_for_size_p (const_basic_block bb)
243 return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (bb);
246 /* Return TRUE when BB should be optimized for speed. */
249 optimize_bb_for_speed_p (const_basic_block bb)
251 return !optimize_bb_for_size_p (bb);
254 /* Return TRUE when BB should be optimized for size. */
257 optimize_edge_for_size_p (edge e)
259 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
262 /* Return TRUE when BB should be optimized for speed. */
265 optimize_edge_for_speed_p (edge e)
267 return !optimize_edge_for_size_p (e);
270 /* Return TRUE when BB should be optimized for size. */
273 optimize_insn_for_size_p (void)
275 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
278 /* Return TRUE when BB should be optimized for speed. */
281 optimize_insn_for_speed_p (void)
283 return !optimize_insn_for_size_p ();
286 /* Return TRUE when LOOP should be optimized for size. */
289 optimize_loop_for_size_p (struct loop *loop)
291 return optimize_bb_for_size_p (loop->header);
294 /* Return TRUE when LOOP should be optimized for speed. */
297 optimize_loop_for_speed_p (struct loop *loop)
299 return optimize_bb_for_speed_p (loop->header);
302 /* Return TRUE when LOOP nest should be optimized for speed. */
305 optimize_loop_nest_for_speed_p (struct loop *loop)
307 struct loop *l = loop;
308 if (optimize_loop_for_speed_p (loop))
311 while (l && l != loop)
313 if (optimize_loop_for_speed_p (l))
321 while (l != loop && !l->next)
330 /* Return TRUE when LOOP nest should be optimized for size. */
333 optimize_loop_nest_for_size_p (struct loop *loop)
335 return !optimize_loop_nest_for_speed_p (loop);
338 /* Return true when edge E is likely to be well predictable by branch
342 predictable_edge_p (edge e)
344 if (profile_status == PROFILE_ABSENT)
347 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
348 || (REG_BR_PROB_BASE - e->probability
349 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
355 /* Set RTL expansion for BB profile. */
358 rtl_profile_for_bb (basic_block bb)
360 crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
363 /* Set RTL expansion for edge profile. */
366 rtl_profile_for_edge (edge e)
368 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
371 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
373 default_rtl_profile (void)
375 crtl->maybe_hot_insn_p = true;
378 /* Return true if the one of outgoing edges is already predicted by
382 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
385 if (!INSN_P (BB_END (bb)))
387 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
388 if (REG_NOTE_KIND (note) == REG_BR_PRED
389 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
394 /* This map contains for a basic block the list of predictions for the
397 static struct pointer_map_t *bb_predictions;
399 /* Structure representing predictions in tree level. */
401 struct edge_prediction {
402 struct edge_prediction *ep_next;
404 enum br_predictor ep_predictor;
408 /* Return true if the one of outgoing edges is already predicted by
412 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
414 struct edge_prediction *i;
415 void **preds = pointer_map_contains (bb_predictions, bb);
420 for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
421 if (i->ep_predictor == predictor)
426 /* Return true when the probability of edge is reliable.
428 The profile guessing code is good at predicting branch outcome (ie.
429 taken/not taken), that is predicted right slightly over 75% of time.
430 It is however notoriously poor on predicting the probability itself.
431 In general the profile appear a lot flatter (with probabilities closer
432 to 50%) than the reality so it is bad idea to use it to drive optimization
433 such as those disabling dynamic branch prediction for well predictable
436 There are two exceptions - edges leading to noreturn edges and edges
437 predicted by number of iterations heuristics are predicted well. This macro
438 should be able to distinguish those, but at the moment it simply check for
439 noreturn heuristic that is only one giving probability over 99% or bellow
440 1%. In future we might want to propagate reliability information across the
441 CFG if we find this information useful on multiple places. */
443 probability_reliable_p (int prob)
445 return (profile_status == PROFILE_READ
446 || (profile_status == PROFILE_GUESSED
447 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
450 /* Same predicate as above, working on edges. */
452 edge_probability_reliable_p (const_edge e)
454 return probability_reliable_p (e->probability);
457 /* Same predicate as edge_probability_reliable_p, working on notes. */
459 br_prob_note_reliable_p (const_rtx note)
461 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
462 return probability_reliable_p (INTVAL (XEXP (note, 0)));
466 predict_insn (rtx insn, enum br_predictor predictor, int probability)
468 gcc_assert (any_condjump_p (insn));
469 if (!flag_guess_branch_prob)
472 add_reg_note (insn, REG_BR_PRED,
473 gen_rtx_CONCAT (VOIDmode,
474 GEN_INT ((int) predictor),
475 GEN_INT ((int) probability)));
478 /* Predict insn by given predictor. */
481 predict_insn_def (rtx insn, enum br_predictor predictor,
482 enum prediction taken)
484 int probability = predictor_info[(int) predictor].hitrate;
487 probability = REG_BR_PROB_BASE - probability;
489 predict_insn (insn, predictor, probability);
492 /* Predict edge E with given probability if possible. */
495 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
498 last_insn = BB_END (e->src);
500 /* We can store the branch prediction information only about
501 conditional jumps. */
502 if (!any_condjump_p (last_insn))
505 /* We always store probability of branching. */
506 if (e->flags & EDGE_FALLTHRU)
507 probability = REG_BR_PROB_BASE - probability;
509 predict_insn (last_insn, predictor, probability);
512 /* Predict edge E with the given PROBABILITY. */
514 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
516 gcc_assert (profile_status != PROFILE_GUESSED);
517 if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
518 && flag_guess_branch_prob && optimize)
520 struct edge_prediction *i = XNEW (struct edge_prediction);
521 void **preds = pointer_map_insert (bb_predictions, e->src);
523 i->ep_next = (struct edge_prediction *) *preds;
525 i->ep_probability = probability;
526 i->ep_predictor = predictor;
531 /* Remove all predictions on given basic block that are attached
534 remove_predictions_associated_with_edge (edge e)
541 preds = pointer_map_contains (bb_predictions, e->src);
545 struct edge_prediction **prediction = (struct edge_prediction **) preds;
546 struct edge_prediction *next;
550 if ((*prediction)->ep_edge == e)
552 next = (*prediction)->ep_next;
557 prediction = &((*prediction)->ep_next);
562 /* Clears the list of predictions stored for BB. */
565 clear_bb_predictions (basic_block bb)
567 void **preds = pointer_map_contains (bb_predictions, bb);
568 struct edge_prediction *pred, *next;
573 for (pred = (struct edge_prediction *) *preds; pred; pred = next)
575 next = pred->ep_next;
581 /* Return true when we can store prediction on insn INSN.
582 At the moment we represent predictions only on conditional
583 jumps, not at computed jump or other complicated cases. */
585 can_predict_insn_p (const_rtx insn)
587 return (JUMP_P (insn)
588 && any_condjump_p (insn)
589 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
592 /* Predict edge E by given predictor if possible. */
595 predict_edge_def (edge e, enum br_predictor predictor,
596 enum prediction taken)
598 int probability = predictor_info[(int) predictor].hitrate;
601 probability = REG_BR_PROB_BASE - probability;
603 predict_edge (e, predictor, probability);
606 /* Invert all branch predictions or probability notes in the INSN. This needs
607 to be done each time we invert the condition used by the jump. */
610 invert_br_probabilities (rtx insn)
614 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
615 if (REG_NOTE_KIND (note) == REG_BR_PROB)
616 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
617 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
618 XEXP (XEXP (note, 0), 1)
619 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
622 /* Dump information about the branch prediction to the output file. */
625 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
626 basic_block bb, int used)
634 FOR_EACH_EDGE (e, ei, bb->succs)
635 if (! (e->flags & EDGE_FALLTHRU))
638 fprintf (file, " %s heuristics%s: %.1f%%",
639 predictor_info[predictor].name,
640 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
644 fprintf (file, " exec ");
645 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
648 fprintf (file, " hit ");
649 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
650 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
654 fprintf (file, "\n");
657 /* We can not predict the probabilities of outgoing edges of bb. Set them
658 evenly and hope for the best. */
660 set_even_probabilities (basic_block bb)
666 FOR_EACH_EDGE (e, ei, bb->succs)
667 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
669 FOR_EACH_EDGE (e, ei, bb->succs)
670 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
671 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
676 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
677 note if not already present. Remove now useless REG_BR_PRED notes. */
680 combine_predictions_for_insn (rtx insn, basic_block bb)
685 int best_probability = PROB_EVEN;
686 enum br_predictor best_predictor = END_PREDICTORS;
687 int combined_probability = REG_BR_PROB_BASE / 2;
689 bool first_match = false;
692 if (!can_predict_insn_p (insn))
694 set_even_probabilities (bb);
698 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
699 pnote = ®_NOTES (insn);
701 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
704 /* We implement "first match" heuristics and use probability guessed
705 by predictor with smallest index. */
706 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
707 if (REG_NOTE_KIND (note) == REG_BR_PRED)
709 enum br_predictor predictor = ((enum br_predictor)
710 INTVAL (XEXP (XEXP (note, 0), 0)));
711 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
714 if (best_predictor > predictor)
715 best_probability = probability, best_predictor = predictor;
717 d = (combined_probability * probability
718 + (REG_BR_PROB_BASE - combined_probability)
719 * (REG_BR_PROB_BASE - probability));
721 /* Use FP math to avoid overflows of 32bit integers. */
723 /* If one probability is 0% and one 100%, avoid division by zero. */
724 combined_probability = REG_BR_PROB_BASE / 2;
726 combined_probability = (((double) combined_probability) * probability
727 * REG_BR_PROB_BASE / d + 0.5);
730 /* Decide which heuristic to use. In case we didn't match anything,
731 use no_prediction heuristic, in case we did match, use either
732 first match or Dempster-Shaffer theory depending on the flags. */
734 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
738 dump_prediction (dump_file, PRED_NO_PREDICTION,
739 combined_probability, bb, true);
742 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
744 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
749 combined_probability = best_probability;
750 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
754 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
756 enum br_predictor predictor = ((enum br_predictor)
757 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
758 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
760 dump_prediction (dump_file, predictor, probability, bb,
761 !first_match || best_predictor == predictor);
762 *pnote = XEXP (*pnote, 1);
765 pnote = &XEXP (*pnote, 1);
770 add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
772 /* Save the prediction into CFG in case we are seeing non-degenerated
774 if (!single_succ_p (bb))
776 BRANCH_EDGE (bb)->probability = combined_probability;
777 FALLTHRU_EDGE (bb)->probability
778 = REG_BR_PROB_BASE - combined_probability;
781 else if (!single_succ_p (bb))
783 int prob = INTVAL (XEXP (prob_note, 0));
785 BRANCH_EDGE (bb)->probability = prob;
786 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
789 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
792 /* Combine predictions into single probability and store them into CFG.
793 Remove now useless prediction entries. */
796 combine_predictions_for_bb (basic_block bb)
798 int best_probability = PROB_EVEN;
799 enum br_predictor best_predictor = END_PREDICTORS;
800 int combined_probability = REG_BR_PROB_BASE / 2;
802 bool first_match = false;
804 struct edge_prediction *pred;
806 edge e, first = NULL, second = NULL;
810 FOR_EACH_EDGE (e, ei, bb->succs)
811 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
814 if (first && !second)
820 /* When there is no successor or only one choice, prediction is easy.
822 We are lazy for now and predict only basic blocks with two outgoing
823 edges. It is possible to predict generic case too, but we have to
824 ignore first match heuristics and do more involved combining. Implement
829 set_even_probabilities (bb);
830 clear_bb_predictions (bb);
832 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
838 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
840 preds = pointer_map_contains (bb_predictions, bb);
843 /* We implement "first match" heuristics and use probability guessed
844 by predictor with smallest index. */
845 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
847 enum br_predictor predictor = pred->ep_predictor;
848 int probability = pred->ep_probability;
850 if (pred->ep_edge != first)
851 probability = REG_BR_PROB_BASE - probability;
854 /* First match heuristics would be widly confused if we predicted
856 if (best_predictor > predictor)
858 struct edge_prediction *pred2;
859 int prob = probability;
861 for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 = pred2->ep_next)
862 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
864 int probability2 = pred->ep_probability;
866 if (pred2->ep_edge != first)
867 probability2 = REG_BR_PROB_BASE - probability2;
869 if ((probability < REG_BR_PROB_BASE / 2) !=
870 (probability2 < REG_BR_PROB_BASE / 2))
873 /* If the same predictor later gave better result, go for it! */
874 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
875 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
879 best_probability = prob, best_predictor = predictor;
882 d = (combined_probability * probability
883 + (REG_BR_PROB_BASE - combined_probability)
884 * (REG_BR_PROB_BASE - probability));
886 /* Use FP math to avoid overflows of 32bit integers. */
888 /* If one probability is 0% and one 100%, avoid division by zero. */
889 combined_probability = REG_BR_PROB_BASE / 2;
891 combined_probability = (((double) combined_probability)
893 * REG_BR_PROB_BASE / d + 0.5);
897 /* Decide which heuristic to use. In case we didn't match anything,
898 use no_prediction heuristic, in case we did match, use either
899 first match or Dempster-Shaffer theory depending on the flags. */
901 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
905 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
908 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
910 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
915 combined_probability = best_probability;
916 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
920 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
922 enum br_predictor predictor = pred->ep_predictor;
923 int probability = pred->ep_probability;
925 if (pred->ep_edge != EDGE_SUCC (bb, 0))
926 probability = REG_BR_PROB_BASE - probability;
927 dump_prediction (dump_file, predictor, probability, bb,
928 !first_match || best_predictor == predictor);
931 clear_bb_predictions (bb);
935 first->probability = combined_probability;
936 second->probability = REG_BR_PROB_BASE - combined_probability;
940 /* Predict edge probabilities by exploiting loop structure. */
948 /* Try to predict out blocks in a loop that are not part of a
950 FOR_EACH_LOOP (li, loop, 0)
952 basic_block bb, *bbs;
954 VEC (edge, heap) *exits;
955 struct tree_niter_desc niter_desc;
958 exits = get_loop_exit_edges (loop);
959 n_exits = VEC_length (edge, exits);
961 FOR_EACH_VEC_ELT (edge, exits, j, ex)
964 HOST_WIDE_INT nitercst;
965 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
967 enum br_predictor predictor;
969 if (number_of_iterations_exit (loop, ex, &niter_desc, false))
970 niter = niter_desc.niter;
971 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
972 niter = loop_niter_by_eval (loop, ex);
974 if (TREE_CODE (niter) == INTEGER_CST)
976 if (host_integerp (niter, 1)
977 && compare_tree_int (niter, max-1) == -1)
978 nitercst = tree_low_cst (niter, 1) + 1;
981 predictor = PRED_LOOP_ITERATIONS;
983 /* If we have just one exit and we can derive some information about
984 the number of iterations of the loop from the statements inside
985 the loop, use it to predict this exit. */
986 else if (n_exits == 1)
988 nitercst = estimated_loop_iterations_int (loop, false);
994 predictor = PRED_LOOP_ITERATIONS_GUESSED;
999 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
1000 predict_edge (ex, predictor, probability);
1002 VEC_free (edge, heap, exits);
1004 bbs = get_loop_body (loop);
1006 for (j = 0; j < loop->num_nodes; j++)
1008 int header_found = 0;
1014 /* Bypass loop heuristics on continue statement. These
1015 statements construct loops via "non-loop" constructs
1016 in the source language and are better to be handled
1018 if (predicted_by_p (bb, PRED_CONTINUE))
1021 /* Loop branch heuristics - predict an edge back to a
1022 loop's head as taken. */
1023 if (bb == loop->latch)
1025 e = find_edge (loop->latch, loop->header);
1029 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
1033 /* Loop exit heuristics - predict an edge exiting the loop if the
1034 conditional has no loop header successors as not taken. */
1036 /* If we already used more reliable loop exit predictors, do not
1037 bother with PRED_LOOP_EXIT. */
1038 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1039 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
1041 /* For loop with many exits we don't want to predict all exits
1042 with the pretty large probability, because if all exits are
1043 considered in row, the loop would be predicted to iterate
1044 almost never. The code to divide probability by number of
1045 exits is very rough. It should compute the number of exits
1046 taken in each patch through function (not the overall number
1047 of exits that might be a lot higher for loops with wide switch
1048 statements in them) and compute n-th square root.
1050 We limit the minimal probability by 2% to avoid
1051 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1052 as this was causing regression in perl benchmark containing such
1055 int probability = ((REG_BR_PROB_BASE
1056 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
1058 if (probability < HITRATE (2))
1059 probability = HITRATE (2);
1060 FOR_EACH_EDGE (e, ei, bb->succs)
1061 if (e->dest->index < NUM_FIXED_BLOCKS
1062 || !flow_bb_inside_loop_p (loop, e->dest))
1063 predict_edge (e, PRED_LOOP_EXIT, probability);
1067 /* Free basic blocks from get_loop_body. */
1072 /* Attempt to predict probabilities of BB outgoing edges using local
1075 bb_estimate_probability_locally (basic_block bb)
1077 rtx last_insn = BB_END (bb);
1080 if (! can_predict_insn_p (last_insn))
1082 cond = get_condition (last_insn, NULL, false, false);
1086 /* Try "pointer heuristic."
1087 A comparison ptr == 0 is predicted as false.
1088 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1089 if (COMPARISON_P (cond)
1090 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
1091 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1093 if (GET_CODE (cond) == EQ)
1094 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1095 else if (GET_CODE (cond) == NE)
1096 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1100 /* Try "opcode heuristic."
1101 EQ tests are usually false and NE tests are usually true. Also,
1102 most quantities are positive, so we can make the appropriate guesses
1103 about signed comparisons against zero. */
1104 switch (GET_CODE (cond))
1107 /* Unconditional branch. */
1108 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1109 cond == const0_rtx ? NOT_TAKEN : TAKEN);
1114 /* Floating point comparisons appears to behave in a very
1115 unpredictable way because of special role of = tests in
1117 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1119 /* Comparisons with 0 are often used for booleans and there is
1120 nothing useful to predict about them. */
1121 else if (XEXP (cond, 1) == const0_rtx
1122 || XEXP (cond, 0) == const0_rtx)
1125 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1130 /* Floating point comparisons appears to behave in a very
1131 unpredictable way because of special role of = tests in
1133 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1135 /* Comparisons with 0 are often used for booleans and there is
1136 nothing useful to predict about them. */
1137 else if (XEXP (cond, 1) == const0_rtx
1138 || XEXP (cond, 0) == const0_rtx)
1141 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1145 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1149 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1154 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1155 || XEXP (cond, 1) == constm1_rtx)
1156 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1161 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1162 || XEXP (cond, 1) == constm1_rtx)
1163 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1171 /* Set edge->probability for each successor edge of BB. */
1173 guess_outgoing_edge_probabilities (basic_block bb)
1175 bb_estimate_probability_locally (bb);
1176 combine_predictions_for_insn (BB_END (bb), bb);
1179 static tree expr_expected_value (tree, bitmap);
1181 /* Helper function for expr_expected_value. */
1184 expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited)
1188 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1190 if (TREE_CONSTANT (op0))
1193 if (code != SSA_NAME)
1196 def = SSA_NAME_DEF_STMT (op0);
1198 /* If we were already here, break the infinite cycle. */
1199 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
1202 if (gimple_code (def) == GIMPLE_PHI)
1204 /* All the arguments of the PHI node must have the same constant
1206 int i, n = gimple_phi_num_args (def);
1207 tree val = NULL, new_val;
1209 for (i = 0; i < n; i++)
1211 tree arg = PHI_ARG_DEF (def, i);
1213 /* If this PHI has itself as an argument, we cannot
1214 determine the string length of this argument. However,
1215 if we can find an expected constant value for the other
1216 PHI args then we can still be sure that this is
1217 likely a constant. So be optimistic and just
1218 continue with the next argument. */
1219 if (arg == PHI_RESULT (def))
1222 new_val = expr_expected_value (arg, visited);
1227 else if (!operand_equal_p (val, new_val, false))
1232 if (is_gimple_assign (def))
1234 if (gimple_assign_lhs (def) != op0)
1237 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1238 gimple_assign_rhs1 (def),
1239 gimple_assign_rhs_code (def),
1240 gimple_assign_rhs2 (def),
1244 if (is_gimple_call (def))
1246 tree decl = gimple_call_fndecl (def);
1249 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
1250 && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
1254 if (gimple_call_num_args (def) != 2)
1256 val = gimple_call_arg (def, 0);
1257 if (TREE_CONSTANT (val))
1259 return gimple_call_arg (def, 1);
1266 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1269 op0 = expr_expected_value (op0, visited);
1272 op1 = expr_expected_value (op1, visited);
1275 res = fold_build2 (code, type, op0, op1);
1276 if (TREE_CONSTANT (res))
1280 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1283 op0 = expr_expected_value (op0, visited);
1286 res = fold_build1 (code, type, op0);
1287 if (TREE_CONSTANT (res))
1294 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1295 The function is used by builtin_expect branch predictor so the evidence
1296 must come from this construct and additional possible constant folding.
1298 We may want to implement more involved value guess (such as value range
1299 propagation based prediction), but such tricks shall go to new
1303 expr_expected_value (tree expr, bitmap visited)
1305 enum tree_code code;
1308 if (TREE_CONSTANT (expr))
1311 extract_ops_from_tree (expr, &code, &op0, &op1);
1312 return expr_expected_value_1 (TREE_TYPE (expr),
1313 op0, code, op1, visited);
1317 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1318 we no longer need. */
1320 strip_predict_hints (void)
1328 gimple_stmt_iterator bi;
1329 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
1331 gimple stmt = gsi_stmt (bi);
1333 if (gimple_code (stmt) == GIMPLE_PREDICT)
1335 gsi_remove (&bi, true);
1338 else if (gimple_code (stmt) == GIMPLE_CALL)
1340 tree fndecl = gimple_call_fndecl (stmt);
1343 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1344 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1345 && gimple_call_num_args (stmt) == 2)
1347 var = gimple_call_lhs (stmt);
1351 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
1352 gsi_replace (&bi, ass_stmt, true);
1356 gsi_remove (&bi, true);
1367 /* Predict using opcode of the last statement in basic block. */
1369 tree_predict_by_opcode (basic_block bb)
1371 gimple stmt = last_stmt (bb);
1380 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1382 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1383 if (then_edge->flags & EDGE_TRUE_VALUE)
1385 op0 = gimple_cond_lhs (stmt);
1386 op1 = gimple_cond_rhs (stmt);
1387 cmp = gimple_cond_code (stmt);
1388 type = TREE_TYPE (op0);
1389 visited = BITMAP_ALLOC (NULL);
1390 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
1391 BITMAP_FREE (visited);
1394 if (integer_zerop (val))
1395 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1397 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1400 /* Try "pointer heuristic."
1401 A comparison ptr == 0 is predicted as false.
1402 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1403 if (POINTER_TYPE_P (type))
1406 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1407 else if (cmp == NE_EXPR)
1408 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1412 /* Try "opcode heuristic."
1413 EQ tests are usually false and NE tests are usually true. Also,
1414 most quantities are positive, so we can make the appropriate guesses
1415 about signed comparisons against zero. */
1420 /* Floating point comparisons appears to behave in a very
1421 unpredictable way because of special role of = tests in
1423 if (FLOAT_TYPE_P (type))
1425 /* Comparisons with 0 are often used for booleans and there is
1426 nothing useful to predict about them. */
1427 else if (integer_zerop (op0) || integer_zerop (op1))
1430 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1435 /* Floating point comparisons appears to behave in a very
1436 unpredictable way because of special role of = tests in
1438 if (FLOAT_TYPE_P (type))
1440 /* Comparisons with 0 are often used for booleans and there is
1441 nothing useful to predict about them. */
1442 else if (integer_zerop (op0)
1443 || integer_zerop (op1))
1446 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1450 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1453 case UNORDERED_EXPR:
1454 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1459 if (integer_zerop (op1)
1460 || integer_onep (op1)
1461 || integer_all_onesp (op1)
1464 || real_minus_onep (op1))
1465 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1470 if (integer_zerop (op1)
1471 || integer_onep (op1)
1472 || integer_all_onesp (op1)
1475 || real_minus_onep (op1))
1476 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1484 /* Try to guess whether the value of return means error code. */
1486 static enum br_predictor
1487 return_prediction (tree val, enum prediction *prediction)
1491 return PRED_NO_PREDICTION;
1492 /* Different heuristics for pointers and scalars. */
1493 if (POINTER_TYPE_P (TREE_TYPE (val)))
1495 /* NULL is usually not returned. */
1496 if (integer_zerop (val))
1498 *prediction = NOT_TAKEN;
1499 return PRED_NULL_RETURN;
1502 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1504 /* Negative return values are often used to indicate
1506 if (TREE_CODE (val) == INTEGER_CST
1507 && tree_int_cst_sgn (val) < 0)
1509 *prediction = NOT_TAKEN;
1510 return PRED_NEGATIVE_RETURN;
1512 /* Constant return values seems to be commonly taken.
1513 Zero/one often represent booleans so exclude them from the
1515 if (TREE_CONSTANT (val)
1516 && (!integer_zerop (val) && !integer_onep (val)))
1518 *prediction = TAKEN;
1519 return PRED_CONST_RETURN;
1522 return PRED_NO_PREDICTION;
1525 /* Find the basic block with return expression and look up for possible
1526 return value trying to apply RETURN_PREDICTION heuristics. */
1528 apply_return_prediction (void)
1530 gimple return_stmt = NULL;
1534 int phi_num_args, i;
1535 enum br_predictor pred;
1536 enum prediction direction;
1539 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1541 return_stmt = last_stmt (e->src);
1543 && gimple_code (return_stmt) == GIMPLE_RETURN)
1548 return_val = gimple_return_retval (return_stmt);
1551 if (TREE_CODE (return_val) != SSA_NAME
1552 || !SSA_NAME_DEF_STMT (return_val)
1553 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
1555 phi = SSA_NAME_DEF_STMT (return_val);
1556 phi_num_args = gimple_phi_num_args (phi);
1557 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1559 /* Avoid the degenerate case where all return values form the function
1560 belongs to same category (ie they are all positive constants)
1561 so we can hardly say something about them. */
1562 for (i = 1; i < phi_num_args; i++)
1563 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1565 if (i != phi_num_args)
1566 for (i = 0; i < phi_num_args; i++)
1568 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1569 if (pred != PRED_NO_PREDICTION)
1570 predict_paths_leading_to_edge (gimple_phi_arg_edge (phi, i), pred,
1575 /* Look for basic block that contains unlikely to happen events
1576 (such as noreturn calls) and mark all paths leading to execution
1577 of this basic blocks as unlikely. */
1580 tree_bb_level_predictions (void)
1583 bool has_return_edges = false;
1587 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1588 if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
1590 has_return_edges = true;
1594 apply_return_prediction ();
1598 gimple_stmt_iterator gsi;
1600 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1602 gimple stmt = gsi_stmt (gsi);
1605 if (is_gimple_call (stmt))
1607 if ((gimple_call_flags (stmt) & ECF_NORETURN)
1608 && has_return_edges)
1609 predict_paths_leading_to (bb, PRED_NORETURN,
1611 decl = gimple_call_fndecl (stmt);
1613 && lookup_attribute ("cold",
1614 DECL_ATTRIBUTES (decl)))
1615 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
1618 else if (gimple_code (stmt) == GIMPLE_PREDICT)
1620 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
1621 gimple_predict_outcome (stmt));
1622 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1623 hints to callers. */
1629 #ifdef ENABLE_CHECKING
1631 /* Callback for pointer_map_traverse, asserts that the pointer map is
1635 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1636 void *data ATTRIBUTE_UNUSED)
1638 gcc_assert (!*value);
1643 /* Predict branch probabilities and estimate profile for basic block BB. */
1646 tree_estimate_probability_bb (basic_block bb)
1652 FOR_EACH_EDGE (e, ei, bb->succs)
1654 /* Predict early returns to be probable, as we've already taken
1655 care for error returns and other cases are often used for
1656 fast paths through function.
1658 Since we've already removed the return statements, we are
1659 looking for CFG like:
1669 if (e->dest != bb->next_bb
1670 && e->dest != EXIT_BLOCK_PTR
1671 && single_succ_p (e->dest)
1672 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1673 && (last = last_stmt (e->dest)) != NULL
1674 && gimple_code (last) == GIMPLE_RETURN)
1679 if (single_succ_p (bb))
1681 FOR_EACH_EDGE (e1, ei1, bb->preds)
1682 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1683 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1684 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1685 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1688 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1689 && !predicted_by_p (e->src, PRED_CONST_RETURN)
1690 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1691 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1694 /* Look for block we are guarding (ie we dominate it,
1695 but it doesn't postdominate us). */
1696 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1697 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1698 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1700 gimple_stmt_iterator bi;
1702 /* The call heuristic claims that a guarded function call
1703 is improbable. This is because such calls are often used
1704 to signal exceptional situations such as printing error
1706 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
1709 gimple stmt = gsi_stmt (bi);
1710 if (is_gimple_call (stmt)
1711 /* Constant and pure calls are hardly used to signalize
1712 something exceptional. */
1713 && gimple_has_side_effects (stmt))
1715 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1721 tree_predict_by_opcode (bb);
1724 /* Predict branch probabilities and estimate profile of the tree CFG.
1725 This function can be called from the loop optimizers to recompute
1726 the profile information. */
1729 tree_estimate_probability (void)
1733 add_noreturn_fake_exit_edges ();
1734 connect_infinite_loops_to_exit ();
1735 /* We use loop_niter_by_eval, which requires that the loops have
1737 create_preheaders (CP_SIMPLE_PREHEADERS);
1738 calculate_dominance_info (CDI_POST_DOMINATORS);
1740 bb_predictions = pointer_map_create ();
1741 tree_bb_level_predictions ();
1742 record_loop_exits ();
1744 if (number_of_loops () > 1)
1748 tree_estimate_probability_bb (bb);
1751 combine_predictions_for_bb (bb);
1753 #ifdef ENABLE_CHECKING
1754 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1756 pointer_map_destroy (bb_predictions);
1757 bb_predictions = NULL;
1759 estimate_bb_frequencies ();
1760 free_dominance_info (CDI_POST_DOMINATORS);
1761 remove_fake_exit_edges ();
1764 /* Predict branch probabilities and estimate profile of the tree CFG.
1765 This is the driver function for PASS_PROFILE. */
1768 tree_estimate_probability_driver (void)
1772 loop_optimizer_init (0);
1773 if (dump_file && (dump_flags & TDF_DETAILS))
1774 flow_loops_dump (dump_file, NULL, 0);
1776 mark_irreducible_loops ();
1778 nb_loops = number_of_loops ();
1782 tree_estimate_probability ();
1787 loop_optimizer_finalize ();
1788 if (dump_file && (dump_flags & TDF_DETAILS))
1789 gimple_dump_cfg (dump_file, dump_flags);
1790 if (profile_status == PROFILE_ABSENT)
1791 profile_status = PROFILE_GUESSED;
1795 /* Predict edges to successors of CUR whose sources are not postdominated by
1796 BB by PRED and recurse to all postdominators. */
1799 predict_paths_for_bb (basic_block cur, basic_block bb,
1800 enum br_predictor pred,
1801 enum prediction taken)
1807 /* We are looking for all edges forming edge cut induced by
1808 set of all blocks postdominated by BB. */
1809 FOR_EACH_EDGE (e, ei, cur->preds)
1810 if (e->src->index >= NUM_FIXED_BLOCKS
1811 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
1817 /* Ignore fake edges and eh, we predict them as not taken anyway. */
1818 if (e->flags & (EDGE_EH | EDGE_FAKE))
1820 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
1822 /* See if there is how many edge from e->src that is not abnormal
1823 and does not lead to BB. */
1824 FOR_EACH_EDGE (e2, ei2, e->src->succs)
1826 && !(e2->flags & (EDGE_EH | EDGE_FAKE))
1827 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
1833 /* If there is non-abnormal path leaving e->src, predict edge
1834 using predictor. Otherwise we need to look for paths
1835 leading to e->src. */
1837 predict_edge_def (e, pred, taken);
1839 predict_paths_for_bb (e->src, e->src, pred, taken);
1841 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
1843 son = next_dom_son (CDI_POST_DOMINATORS, son))
1844 predict_paths_for_bb (son, bb, pred, taken);
1847 /* Sets branch probabilities according to PREDiction and
1851 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
1852 enum prediction taken)
1854 predict_paths_for_bb (bb, bb, pred, taken);
1857 /* Like predict_paths_leading_to but take edge instead of basic block. */
1860 predict_paths_leading_to_edge (edge e, enum br_predictor pred,
1861 enum prediction taken)
1863 bool has_nonloop_edge = false;
1867 basic_block bb = e->src;
1868 FOR_EACH_EDGE (e2, ei, bb->succs)
1869 if (e2->dest != e->src && e2->dest != e->dest
1870 && !(e->flags & (EDGE_EH | EDGE_FAKE))
1871 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->dest))
1873 has_nonloop_edge = true;
1876 if (!has_nonloop_edge)
1877 predict_paths_for_bb (bb, bb, pred, taken);
1879 predict_edge_def (e, pred, taken);
1882 /* This is used to carry information about basic blocks. It is
1883 attached to the AUX field of the standard CFG block. */
1885 typedef struct block_info_def
1887 /* Estimated frequency of execution of basic_block. */
1890 /* To keep queue of basic blocks to process. */
1893 /* Number of predecessors we need to visit first. */
1897 /* Similar information for edges. */
1898 typedef struct edge_info_def
1900 /* In case edge is a loopback edge, the probability edge will be reached
1901 in case header is. Estimated number of iterations of the loop can be
1902 then computed as 1 / (1 - back_edge_prob). */
1903 sreal back_edge_prob;
1904 /* True if the edge is a loopback edge in the natural loop. */
1905 unsigned int back_edge:1;
1908 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1909 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1911 /* Helper function for estimate_bb_frequencies.
1912 Propagate the frequencies in blocks marked in
1913 TOVISIT, starting in HEAD. */
1916 propagate_freq (basic_block head, bitmap tovisit)
1925 /* For each basic block we need to visit count number of his predecessors
1926 we need to visit first. */
1927 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1932 bb = BASIC_BLOCK (i);
1934 FOR_EACH_EDGE (e, ei, bb->preds)
1936 bool visit = bitmap_bit_p (tovisit, e->src->index);
1938 if (visit && !(e->flags & EDGE_DFS_BACK))
1940 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1942 "Irreducible region hit, ignoring edge to %i->%i\n",
1943 e->src->index, bb->index);
1945 BLOCK_INFO (bb)->npredecessors = count;
1946 /* When function never returns, we will never process exit block. */
1947 if (!count && bb == EXIT_BLOCK_PTR)
1948 bb->count = bb->frequency = 0;
1951 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1953 for (bb = head; bb; bb = nextbb)
1956 sreal cyclic_probability, frequency;
1958 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1959 memcpy (&frequency, &real_zero, sizeof (real_zero));
1961 nextbb = BLOCK_INFO (bb)->next;
1962 BLOCK_INFO (bb)->next = NULL;
1964 /* Compute frequency of basic block. */
1967 #ifdef ENABLE_CHECKING
1968 FOR_EACH_EDGE (e, ei, bb->preds)
1969 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1970 || (e->flags & EDGE_DFS_BACK));
1973 FOR_EACH_EDGE (e, ei, bb->preds)
1974 if (EDGE_INFO (e)->back_edge)
1976 sreal_add (&cyclic_probability, &cyclic_probability,
1977 &EDGE_INFO (e)->back_edge_prob);
1979 else if (!(e->flags & EDGE_DFS_BACK))
1983 /* frequency += (e->probability
1984 * BLOCK_INFO (e->src)->frequency /
1985 REG_BR_PROB_BASE); */
1987 sreal_init (&tmp, e->probability, 0);
1988 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1989 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1990 sreal_add (&frequency, &frequency, &tmp);
1993 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1995 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1996 sizeof (frequency));
2000 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
2002 memcpy (&cyclic_probability, &real_almost_one,
2003 sizeof (real_almost_one));
2006 /* BLOCK_INFO (bb)->frequency = frequency
2007 / (1 - cyclic_probability) */
2009 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
2010 sreal_div (&BLOCK_INFO (bb)->frequency,
2011 &frequency, &cyclic_probability);
2015 bitmap_clear_bit (tovisit, bb->index);
2017 e = find_edge (bb, head);
2022 /* EDGE_INFO (e)->back_edge_prob
2023 = ((e->probability * BLOCK_INFO (bb)->frequency)
2024 / REG_BR_PROB_BASE); */
2026 sreal_init (&tmp, e->probability, 0);
2027 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
2028 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2029 &tmp, &real_inv_br_prob_base);
2032 /* Propagate to successor blocks. */
2033 FOR_EACH_EDGE (e, ei, bb->succs)
2034 if (!(e->flags & EDGE_DFS_BACK)
2035 && BLOCK_INFO (e->dest)->npredecessors)
2037 BLOCK_INFO (e->dest)->npredecessors--;
2038 if (!BLOCK_INFO (e->dest)->npredecessors)
2043 BLOCK_INFO (last)->next = e->dest;
2051 /* Estimate probabilities of loopback edges in loops at same nest level. */
2054 estimate_loops_at_level (struct loop *first_loop)
2058 for (loop = first_loop; loop; loop = loop->next)
2063 bitmap tovisit = BITMAP_ALLOC (NULL);
2065 estimate_loops_at_level (loop->inner);
2067 /* Find current loop back edge and mark it. */
2068 e = loop_latch_edge (loop);
2069 EDGE_INFO (e)->back_edge = 1;
2071 bbs = get_loop_body (loop);
2072 for (i = 0; i < loop->num_nodes; i++)
2073 bitmap_set_bit (tovisit, bbs[i]->index);
2075 propagate_freq (loop->header, tovisit);
2076 BITMAP_FREE (tovisit);
2080 /* Propagates frequencies through structure of loops. */
2083 estimate_loops (void)
2085 bitmap tovisit = BITMAP_ALLOC (NULL);
2088 /* Start by estimating the frequencies in the loops. */
2089 if (number_of_loops () > 1)
2090 estimate_loops_at_level (current_loops->tree_root->inner);
2092 /* Now propagate the frequencies through all the blocks. */
2095 bitmap_set_bit (tovisit, bb->index);
2097 propagate_freq (ENTRY_BLOCK_PTR, tovisit);
2098 BITMAP_FREE (tovisit);
2101 /* Convert counts measured by profile driven feedback to frequencies.
2102 Return nonzero iff there was any nonzero execution count. */
2105 counts_to_freqs (void)
2107 gcov_type count_max, true_count_max = 0;
2110 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2111 true_count_max = MAX (bb->count, true_count_max);
2113 count_max = MAX (true_count_max, 1);
2114 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2115 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
2117 return true_count_max;
2120 /* Return true if function is likely to be expensive, so there is no point to
2121 optimize performance of prologue, epilogue or do inlining at the expense
2122 of code size growth. THRESHOLD is the limit of number of instructions
2123 function can execute at average to be still considered not expensive. */
2126 expensive_function_p (int threshold)
2128 unsigned int sum = 0;
2132 /* We can not compute accurately for large thresholds due to scaled
2134 gcc_assert (threshold <= BB_FREQ_MAX);
2136 /* Frequencies are out of range. This either means that function contains
2137 internal loop executing more than BB_FREQ_MAX times or profile feedback
2138 is available and function has not been executed at all. */
2139 if (ENTRY_BLOCK_PTR->frequency == 0)
2142 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2143 limit = ENTRY_BLOCK_PTR->frequency * threshold;
2148 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2149 insn = NEXT_INSN (insn))
2150 if (active_insn_p (insn))
2152 sum += bb->frequency;
2161 /* Estimate basic blocks frequency by given branch probabilities. */
2164 estimate_bb_frequencies (void)
2169 if (profile_status != PROFILE_READ || !counts_to_freqs ())
2171 static int real_values_initialized = 0;
2173 if (!real_values_initialized)
2175 real_values_initialized = 1;
2176 sreal_init (&real_zero, 0, 0);
2177 sreal_init (&real_one, 1, 0);
2178 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
2179 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
2180 sreal_init (&real_one_half, 1, -1);
2181 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
2182 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
2185 mark_dfs_back_edges ();
2187 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
2189 /* Set up block info for each basic block. */
2190 alloc_aux_for_blocks (sizeof (struct block_info_def));
2191 alloc_aux_for_edges (sizeof (struct edge_info_def));
2192 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2197 FOR_EACH_EDGE (e, ei, bb->succs)
2199 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
2200 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2201 &EDGE_INFO (e)->back_edge_prob,
2202 &real_inv_br_prob_base);
2206 /* First compute probabilities locally for each loop from innermost
2207 to outermost to examine probabilities for back edges. */
2210 memcpy (&freq_max, &real_zero, sizeof (real_zero));
2212 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
2213 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
2215 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
2216 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2220 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
2221 sreal_add (&tmp, &tmp, &real_one_half);
2222 bb->frequency = sreal_to_int (&tmp);
2225 free_aux_for_blocks ();
2226 free_aux_for_edges ();
2228 compute_function_frequency ();
2231 /* Decide whether function is hot, cold or unlikely executed. */
2233 compute_function_frequency (void)
2236 struct cgraph_node *node = cgraph_get_node (current_function_decl);
2237 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2238 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
2239 node->only_called_at_startup = true;
2240 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
2241 node->only_called_at_exit = true;
2243 if (!profile_info || !flag_branch_probabilities)
2245 int flags = flags_from_decl_or_type (current_function_decl);
2246 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2248 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2249 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2251 node->frequency = NODE_FREQUENCY_HOT;
2252 else if (flags & ECF_NORETURN)
2253 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2254 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
2255 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2256 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2257 || DECL_STATIC_DESTRUCTOR (current_function_decl))
2258 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2261 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2264 if (maybe_hot_bb_p (bb))
2266 node->frequency = NODE_FREQUENCY_HOT;
2269 if (!probably_never_executed_bb_p (bb))
2270 node->frequency = NODE_FREQUENCY_NORMAL;
2275 gate_estimate_probability (void)
2277 return flag_guess_branch_prob;
2280 /* Build PREDICT_EXPR. */
2282 build_predict_expr (enum br_predictor predictor, enum prediction taken)
2284 tree t = build1 (PREDICT_EXPR, void_type_node,
2285 build_int_cst (NULL, predictor));
2286 SET_PREDICT_EXPR_OUTCOME (t, taken);
2291 predictor_name (enum br_predictor predictor)
2293 return predictor_info[predictor].name;
2296 struct gimple_opt_pass pass_profile =
2300 "profile", /* name */
2301 gate_estimate_probability, /* gate */
2302 tree_estimate_probability_driver, /* execute */
2305 0, /* static_pass_number */
2306 TV_BRANCH_PROB, /* tv_id */
2307 PROP_cfg, /* properties_required */
2308 0, /* properties_provided */
2309 0, /* properties_destroyed */
2310 0, /* todo_flags_start */
2311 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2315 struct gimple_opt_pass pass_strip_predict_hints =
2319 "*strip_predict_hints", /* name */
2321 strip_predict_hints, /* execute */
2324 0, /* static_pass_number */
2325 TV_BRANCH_PROB, /* tv_id */
2326 PROP_cfg, /* properties_required */
2327 0, /* properties_provided */
2328 0, /* properties_destroyed */
2329 0, /* todo_flags_start */
2330 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2334 /* Rebuild function frequencies. Passes are in general expected to
2335 maintain profile by hand, however in some cases this is not possible:
2336 for example when inlining several functions with loops freuqencies might run
2337 out of scale and thus needs to be recomputed. */
2340 rebuild_frequencies (void)
2342 timevar_push (TV_REBUILD_FREQUENCIES);
2343 if (profile_status == PROFILE_GUESSED)
2345 loop_optimizer_init (0);
2346 add_noreturn_fake_exit_edges ();
2347 mark_irreducible_loops ();
2348 connect_infinite_loops_to_exit ();
2349 estimate_bb_frequencies ();
2350 remove_fake_exit_edges ();
2351 loop_optimizer_finalize ();
2353 else if (profile_status == PROFILE_READ)
2357 timevar_pop (TV_REBUILD_FREQUENCIES);