1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008
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"
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 compute_function_frequency (void);
81 static void choose_function_section (void);
82 static bool can_predict_insn_p (const_rtx);
84 /* Information we hold about each branch predictor.
85 Filled using information from predict.def. */
89 const char *const name; /* Name used in the debugging dumps. */
90 const int hitrate; /* Expected hitrate used by
91 predict_insn_def call. */
95 /* Use given predictor without Dempster-Shaffer theory if it matches
96 using first_match heuristics. */
97 #define PRED_FLAG_FIRST_MATCH 1
99 /* Recompute hitrate in percent to our representation. */
101 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
103 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
104 static const struct predictor_info predictor_info[]= {
105 #include "predict.def"
107 /* Upper bound on predictors. */
112 /* Return TRUE if frequency FREQ is considered to be hot. */
114 maybe_hot_frequency_p (int freq)
116 if (!profile_info || !flag_branch_probabilities)
118 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
120 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
123 if (profile_status == PROFILE_ABSENT)
125 if (freq < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
130 /* Return true in case BB can be CPU intensive and should be optimized
131 for maximal performance. */
134 maybe_hot_bb_p (const_basic_block bb)
136 if (profile_info && flag_branch_probabilities
138 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
140 return maybe_hot_frequency_p (bb->frequency);
143 /* Return true if the call can be hot. */
146 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
148 if (profile_info && flag_branch_probabilities
150 <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
152 if (lookup_attribute ("cold", DECL_ATTRIBUTES (edge->callee->decl))
153 || lookup_attribute ("cold", DECL_ATTRIBUTES (edge->caller->decl)))
155 if (lookup_attribute ("hot", DECL_ATTRIBUTES (edge->caller->decl)))
157 if (flag_guess_branch_prob
158 && edge->frequency < (CGRAPH_FREQ_MAX
159 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
164 /* Return true in case BB can be CPU intensive and should be optimized
165 for maximal performance. */
168 maybe_hot_edge_p (edge e)
170 if (profile_info && flag_branch_probabilities
172 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
174 return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
177 /* Return true in case BB is cold and should be optimized for size. */
180 probably_cold_bb_p (const_basic_block bb)
182 if (profile_info && flag_branch_probabilities
184 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
186 if ((!profile_info || !flag_branch_probabilities)
187 && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
189 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
194 /* Return true in case BB is probably never executed. */
196 probably_never_executed_bb_p (const_basic_block bb)
198 if (profile_info && flag_branch_probabilities)
199 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
200 if ((!profile_info || !flag_branch_probabilities)
201 && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
206 /* Return true when current function should always be optimized for size. */
209 optimize_function_for_size_p (struct function *fun)
211 return (optimize_size
212 || fun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED);
215 /* Return true when current function should always be optimized for speed. */
218 optimize_function_for_speed_p (struct function *fun)
220 return !optimize_function_for_size_p (fun);
223 /* Return TRUE when BB should be optimized for size. */
226 optimize_bb_for_size_p (const_basic_block bb)
228 return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (bb);
231 /* Return TRUE when BB should be optimized for speed. */
234 optimize_bb_for_speed_p (const_basic_block bb)
236 return !optimize_bb_for_size_p (bb);
239 /* Return TRUE when BB should be optimized for size. */
242 optimize_edge_for_size_p (edge e)
244 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
247 /* Return TRUE when BB should be optimized for speed. */
250 optimize_edge_for_speed_p (edge e)
252 return !optimize_edge_for_size_p (e);
255 /* Return TRUE when BB should be optimized for size. */
258 optimize_insn_for_size_p (void)
260 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
263 /* Return TRUE when BB should be optimized for speed. */
266 optimize_insn_for_speed_p (void)
268 return !optimize_insn_for_size_p ();
271 /* Return TRUE when LOOP should be optimized for size. */
274 optimize_loop_for_size_p (struct loop *loop)
276 return optimize_bb_for_size_p (loop->header);
279 /* Return TRUE when LOOP should be optimized for speed. */
282 optimize_loop_for_speed_p (struct loop *loop)
284 return optimize_bb_for_speed_p (loop->header);
287 /* Return TRUE when LOOP nest should be optimized for speed. */
290 optimize_loop_nest_for_speed_p (struct loop *loop)
292 struct loop *l = loop;
293 if (optimize_loop_for_speed_p (loop))
296 while (l && l != loop)
298 if (optimize_loop_for_speed_p (l))
306 while (l != loop && !l->next)
315 /* Return TRUE when LOOP nest should be optimized for size. */
318 optimize_loop_nest_for_size_p (struct loop *loop)
320 return !optimize_loop_nest_for_speed_p (loop);
323 /* Return true when edge E is likely to be well predictable by branch
327 predictable_edge_p (edge e)
329 if (profile_status == PROFILE_ABSENT)
332 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
333 || (REG_BR_PROB_BASE - e->probability
334 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
340 /* Set RTL expansion for BB profile. */
343 rtl_profile_for_bb (basic_block bb)
345 crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
348 /* Set RTL expansion for edge profile. */
351 rtl_profile_for_edge (edge e)
353 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
356 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
358 default_rtl_profile (void)
360 crtl->maybe_hot_insn_p = true;
363 /* Return true if the one of outgoing edges is already predicted by
367 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
370 if (!INSN_P (BB_END (bb)))
372 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
373 if (REG_NOTE_KIND (note) == REG_BR_PRED
374 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
379 /* This map contains for a basic block the list of predictions for the
382 static struct pointer_map_t *bb_predictions;
384 /* Return true if the one of outgoing edges is already predicted by
388 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
390 struct edge_prediction *i;
391 void **preds = pointer_map_contains (bb_predictions, bb);
396 for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
397 if (i->ep_predictor == predictor)
402 /* Return true when the probability of edge is reliable.
404 The profile guessing code is good at predicting branch outcome (ie.
405 taken/not taken), that is predicted right slightly over 75% of time.
406 It is however notoriously poor on predicting the probability itself.
407 In general the profile appear a lot flatter (with probabilities closer
408 to 50%) than the reality so it is bad idea to use it to drive optimization
409 such as those disabling dynamic branch prediction for well predictable
412 There are two exceptions - edges leading to noreturn edges and edges
413 predicted by number of iterations heuristics are predicted well. This macro
414 should be able to distinguish those, but at the moment it simply check for
415 noreturn heuristic that is only one giving probability over 99% or bellow
416 1%. In future we might want to propagate reliability information across the
417 CFG if we find this information useful on multiple places. */
419 probability_reliable_p (int prob)
421 return (profile_status == PROFILE_READ
422 || (profile_status == PROFILE_GUESSED
423 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
426 /* Same predicate as above, working on edges. */
428 edge_probability_reliable_p (const_edge e)
430 return probability_reliable_p (e->probability);
433 /* Same predicate as edge_probability_reliable_p, working on notes. */
435 br_prob_note_reliable_p (const_rtx note)
437 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
438 return probability_reliable_p (INTVAL (XEXP (note, 0)));
442 predict_insn (rtx insn, enum br_predictor predictor, int probability)
444 gcc_assert (any_condjump_p (insn));
445 if (!flag_guess_branch_prob)
448 add_reg_note (insn, REG_BR_PRED,
449 gen_rtx_CONCAT (VOIDmode,
450 GEN_INT ((int) predictor),
451 GEN_INT ((int) probability)));
454 /* Predict insn by given predictor. */
457 predict_insn_def (rtx insn, enum br_predictor predictor,
458 enum prediction taken)
460 int probability = predictor_info[(int) predictor].hitrate;
463 probability = REG_BR_PROB_BASE - probability;
465 predict_insn (insn, predictor, probability);
468 /* Predict edge E with given probability if possible. */
471 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
474 last_insn = BB_END (e->src);
476 /* We can store the branch prediction information only about
477 conditional jumps. */
478 if (!any_condjump_p (last_insn))
481 /* We always store probability of branching. */
482 if (e->flags & EDGE_FALLTHRU)
483 probability = REG_BR_PROB_BASE - probability;
485 predict_insn (last_insn, predictor, probability);
488 /* Predict edge E with the given PROBABILITY. */
490 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
492 gcc_assert (profile_status != PROFILE_GUESSED);
493 if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
494 && flag_guess_branch_prob && optimize)
496 struct edge_prediction *i = XNEW (struct edge_prediction);
497 void **preds = pointer_map_insert (bb_predictions, e->src);
499 i->ep_next = (struct edge_prediction *) *preds;
501 i->ep_probability = probability;
502 i->ep_predictor = predictor;
507 /* Remove all predictions on given basic block that are attached
510 remove_predictions_associated_with_edge (edge e)
517 preds = pointer_map_contains (bb_predictions, e->src);
521 struct edge_prediction **prediction = (struct edge_prediction **) preds;
522 struct edge_prediction *next;
526 if ((*prediction)->ep_edge == e)
528 next = (*prediction)->ep_next;
533 prediction = &((*prediction)->ep_next);
538 /* Clears the list of predictions stored for BB. */
541 clear_bb_predictions (basic_block bb)
543 void **preds = pointer_map_contains (bb_predictions, bb);
544 struct edge_prediction *pred, *next;
549 for (pred = (struct edge_prediction *) *preds; pred; pred = next)
551 next = pred->ep_next;
557 /* Return true when we can store prediction on insn INSN.
558 At the moment we represent predictions only on conditional
559 jumps, not at computed jump or other complicated cases. */
561 can_predict_insn_p (const_rtx insn)
563 return (JUMP_P (insn)
564 && any_condjump_p (insn)
565 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
568 /* Predict edge E by given predictor if possible. */
571 predict_edge_def (edge e, enum br_predictor predictor,
572 enum prediction taken)
574 int probability = predictor_info[(int) predictor].hitrate;
577 probability = REG_BR_PROB_BASE - probability;
579 predict_edge (e, predictor, probability);
582 /* Invert all branch predictions or probability notes in the INSN. This needs
583 to be done each time we invert the condition used by the jump. */
586 invert_br_probabilities (rtx insn)
590 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
591 if (REG_NOTE_KIND (note) == REG_BR_PROB)
592 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
593 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
594 XEXP (XEXP (note, 0), 1)
595 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
598 /* Dump information about the branch prediction to the output file. */
601 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
602 basic_block bb, int used)
610 FOR_EACH_EDGE (e, ei, bb->succs)
611 if (! (e->flags & EDGE_FALLTHRU))
614 fprintf (file, " %s heuristics%s: %.1f%%",
615 predictor_info[predictor].name,
616 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
620 fprintf (file, " exec ");
621 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
624 fprintf (file, " hit ");
625 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
626 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
630 fprintf (file, "\n");
633 /* We can not predict the probabilities of outgoing edges of bb. Set them
634 evenly and hope for the best. */
636 set_even_probabilities (basic_block bb)
642 FOR_EACH_EDGE (e, ei, bb->succs)
643 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
645 FOR_EACH_EDGE (e, ei, bb->succs)
646 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
647 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
652 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
653 note if not already present. Remove now useless REG_BR_PRED notes. */
656 combine_predictions_for_insn (rtx insn, basic_block bb)
661 int best_probability = PROB_EVEN;
662 int best_predictor = END_PREDICTORS;
663 int combined_probability = REG_BR_PROB_BASE / 2;
665 bool first_match = false;
668 if (!can_predict_insn_p (insn))
670 set_even_probabilities (bb);
674 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
675 pnote = ®_NOTES (insn);
677 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
680 /* We implement "first match" heuristics and use probability guessed
681 by predictor with smallest index. */
682 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
683 if (REG_NOTE_KIND (note) == REG_BR_PRED)
685 int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
686 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
689 if (best_predictor > predictor)
690 best_probability = probability, best_predictor = predictor;
692 d = (combined_probability * probability
693 + (REG_BR_PROB_BASE - combined_probability)
694 * (REG_BR_PROB_BASE - probability));
696 /* Use FP math to avoid overflows of 32bit integers. */
698 /* If one probability is 0% and one 100%, avoid division by zero. */
699 combined_probability = REG_BR_PROB_BASE / 2;
701 combined_probability = (((double) combined_probability) * probability
702 * REG_BR_PROB_BASE / d + 0.5);
705 /* Decide which heuristic to use. In case we didn't match anything,
706 use no_prediction heuristic, in case we did match, use either
707 first match or Dempster-Shaffer theory depending on the flags. */
709 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
713 dump_prediction (dump_file, PRED_NO_PREDICTION,
714 combined_probability, bb, true);
717 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
719 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
724 combined_probability = best_probability;
725 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
729 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
731 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
732 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
734 dump_prediction (dump_file, predictor, probability, bb,
735 !first_match || best_predictor == predictor);
736 *pnote = XEXP (*pnote, 1);
739 pnote = &XEXP (*pnote, 1);
744 add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
746 /* Save the prediction into CFG in case we are seeing non-degenerated
748 if (!single_succ_p (bb))
750 BRANCH_EDGE (bb)->probability = combined_probability;
751 FALLTHRU_EDGE (bb)->probability
752 = REG_BR_PROB_BASE - combined_probability;
755 else if (!single_succ_p (bb))
757 int prob = INTVAL (XEXP (prob_note, 0));
759 BRANCH_EDGE (bb)->probability = prob;
760 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
763 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
766 /* Combine predictions into single probability and store them into CFG.
767 Remove now useless prediction entries. */
770 combine_predictions_for_bb (basic_block bb)
772 int best_probability = PROB_EVEN;
773 int best_predictor = END_PREDICTORS;
774 int combined_probability = REG_BR_PROB_BASE / 2;
776 bool first_match = false;
778 struct edge_prediction *pred;
780 edge e, first = NULL, second = NULL;
784 FOR_EACH_EDGE (e, ei, bb->succs)
785 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
788 if (first && !second)
794 /* When there is no successor or only one choice, prediction is easy.
796 We are lazy for now and predict only basic blocks with two outgoing
797 edges. It is possible to predict generic case too, but we have to
798 ignore first match heuristics and do more involved combining. Implement
803 set_even_probabilities (bb);
804 clear_bb_predictions (bb);
806 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
812 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
814 preds = pointer_map_contains (bb_predictions, bb);
817 /* We implement "first match" heuristics and use probability guessed
818 by predictor with smallest index. */
819 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
821 int predictor = pred->ep_predictor;
822 int probability = pred->ep_probability;
824 if (pred->ep_edge != first)
825 probability = REG_BR_PROB_BASE - probability;
828 if (best_predictor > predictor)
829 best_probability = probability, best_predictor = predictor;
831 d = (combined_probability * probability
832 + (REG_BR_PROB_BASE - combined_probability)
833 * (REG_BR_PROB_BASE - probability));
835 /* Use FP math to avoid overflows of 32bit integers. */
837 /* If one probability is 0% and one 100%, avoid division by zero. */
838 combined_probability = REG_BR_PROB_BASE / 2;
840 combined_probability = (((double) combined_probability)
842 * REG_BR_PROB_BASE / d + 0.5);
846 /* Decide which heuristic to use. In case we didn't match anything,
847 use no_prediction heuristic, in case we did match, use either
848 first match or Dempster-Shaffer theory depending on the flags. */
850 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
854 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
857 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
859 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
864 combined_probability = best_probability;
865 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
869 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
871 int predictor = pred->ep_predictor;
872 int probability = pred->ep_probability;
874 if (pred->ep_edge != EDGE_SUCC (bb, 0))
875 probability = REG_BR_PROB_BASE - probability;
876 dump_prediction (dump_file, predictor, probability, bb,
877 !first_match || best_predictor == predictor);
880 clear_bb_predictions (bb);
884 first->probability = combined_probability;
885 second->probability = REG_BR_PROB_BASE - combined_probability;
889 /* Predict edge probabilities by exploiting loop structure. */
899 /* Try to predict out blocks in a loop that are not part of a
901 FOR_EACH_LOOP (li, loop, 0)
903 basic_block bb, *bbs;
905 VEC (edge, heap) *exits;
906 struct tree_niter_desc niter_desc;
909 exits = get_loop_exit_edges (loop);
910 n_exits = VEC_length (edge, exits);
912 for (j = 0; VEC_iterate (edge, exits, j, ex); j++)
915 HOST_WIDE_INT nitercst;
916 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
918 enum br_predictor predictor;
920 if (number_of_iterations_exit (loop, ex, &niter_desc, false))
921 niter = niter_desc.niter;
922 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
923 niter = loop_niter_by_eval (loop, ex);
925 if (TREE_CODE (niter) == INTEGER_CST)
927 if (host_integerp (niter, 1)
928 && compare_tree_int (niter, max-1) == -1)
929 nitercst = tree_low_cst (niter, 1) + 1;
932 predictor = PRED_LOOP_ITERATIONS;
934 /* If we have just one exit and we can derive some information about
935 the number of iterations of the loop from the statements inside
936 the loop, use it to predict this exit. */
937 else if (n_exits == 1)
939 nitercst = estimated_loop_iterations_int (loop, false);
945 predictor = PRED_LOOP_ITERATIONS_GUESSED;
950 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
951 predict_edge (ex, predictor, probability);
953 VEC_free (edge, heap, exits);
955 bbs = get_loop_body (loop);
957 for (j = 0; j < loop->num_nodes; j++)
959 int header_found = 0;
965 /* Bypass loop heuristics on continue statement. These
966 statements construct loops via "non-loop" constructs
967 in the source language and are better to be handled
969 if (predicted_by_p (bb, PRED_CONTINUE))
972 /* Loop branch heuristics - predict an edge back to a
973 loop's head as taken. */
974 if (bb == loop->latch)
976 e = find_edge (loop->latch, loop->header);
980 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
984 /* Loop exit heuristics - predict an edge exiting the loop if the
985 conditional has no loop header successors as not taken. */
987 /* If we already used more reliable loop exit predictors, do not
988 bother with PRED_LOOP_EXIT. */
989 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
990 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
992 /* For loop with many exits we don't want to predict all exits
993 with the pretty large probability, because if all exits are
994 considered in row, the loop would be predicted to iterate
995 almost never. The code to divide probability by number of
996 exits is very rough. It should compute the number of exits
997 taken in each patch through function (not the overall number
998 of exits that might be a lot higher for loops with wide switch
999 statements in them) and compute n-th square root.
1001 We limit the minimal probability by 2% to avoid
1002 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1003 as this was causing regression in perl benchmark containing such
1006 int probability = ((REG_BR_PROB_BASE
1007 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
1009 if (probability < HITRATE (2))
1010 probability = HITRATE (2);
1011 FOR_EACH_EDGE (e, ei, bb->succs)
1012 if (e->dest->index < NUM_FIXED_BLOCKS
1013 || !flow_bb_inside_loop_p (loop, e->dest))
1014 predict_edge (e, PRED_LOOP_EXIT, probability);
1018 /* Free basic blocks from get_loop_body. */
1025 /* Attempt to predict probabilities of BB outgoing edges using local
1028 bb_estimate_probability_locally (basic_block bb)
1030 rtx last_insn = BB_END (bb);
1033 if (! can_predict_insn_p (last_insn))
1035 cond = get_condition (last_insn, NULL, false, false);
1039 /* Try "pointer heuristic."
1040 A comparison ptr == 0 is predicted as false.
1041 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1042 if (COMPARISON_P (cond)
1043 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
1044 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1046 if (GET_CODE (cond) == EQ)
1047 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1048 else if (GET_CODE (cond) == NE)
1049 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1053 /* Try "opcode heuristic."
1054 EQ tests are usually false and NE tests are usually true. Also,
1055 most quantities are positive, so we can make the appropriate guesses
1056 about signed comparisons against zero. */
1057 switch (GET_CODE (cond))
1060 /* Unconditional branch. */
1061 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1062 cond == const0_rtx ? NOT_TAKEN : TAKEN);
1067 /* Floating point comparisons appears to behave in a very
1068 unpredictable way because of special role of = tests in
1070 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1072 /* Comparisons with 0 are often used for booleans and there is
1073 nothing useful to predict about them. */
1074 else if (XEXP (cond, 1) == const0_rtx
1075 || XEXP (cond, 0) == const0_rtx)
1078 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1083 /* Floating point comparisons appears to behave in a very
1084 unpredictable way because of special role of = tests in
1086 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1088 /* Comparisons with 0 are often used for booleans and there is
1089 nothing useful to predict about them. */
1090 else if (XEXP (cond, 1) == const0_rtx
1091 || XEXP (cond, 0) == const0_rtx)
1094 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1098 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1102 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1107 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1108 || XEXP (cond, 1) == constm1_rtx)
1109 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1114 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1115 || XEXP (cond, 1) == constm1_rtx)
1116 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1124 /* Set edge->probability for each successor edge of BB. */
1126 guess_outgoing_edge_probabilities (basic_block bb)
1128 bb_estimate_probability_locally (bb);
1129 combine_predictions_for_insn (BB_END (bb), bb);
1132 static tree expr_expected_value (tree, bitmap);
1134 /* Helper function for expr_expected_value. */
1137 expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited)
1141 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1143 if (TREE_CONSTANT (op0))
1146 if (code != SSA_NAME)
1149 def = SSA_NAME_DEF_STMT (op0);
1151 /* If we were already here, break the infinite cycle. */
1152 if (bitmap_bit_p (visited, SSA_NAME_VERSION (op0)))
1154 bitmap_set_bit (visited, SSA_NAME_VERSION (op0));
1156 if (gimple_code (def) == GIMPLE_PHI)
1158 /* All the arguments of the PHI node must have the same constant
1160 int i, n = gimple_phi_num_args (def);
1161 tree val = NULL, new_val;
1163 for (i = 0; i < n; i++)
1165 tree arg = PHI_ARG_DEF (def, i);
1167 /* If this PHI has itself as an argument, we cannot
1168 determine the string length of this argument. However,
1169 if we can find an expected constant value for the other
1170 PHI args then we can still be sure that this is
1171 likely a constant. So be optimistic and just
1172 continue with the next argument. */
1173 if (arg == PHI_RESULT (def))
1176 new_val = expr_expected_value (arg, visited);
1181 else if (!operand_equal_p (val, new_val, false))
1186 if (is_gimple_assign (def))
1188 if (gimple_assign_lhs (def) != op0)
1191 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1192 gimple_assign_rhs1 (def),
1193 gimple_assign_rhs_code (def),
1194 gimple_assign_rhs2 (def),
1198 if (is_gimple_call (def))
1200 tree decl = gimple_call_fndecl (def);
1203 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
1204 && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
1208 if (gimple_call_num_args (def) != 2)
1210 val = gimple_call_arg (def, 0);
1211 if (TREE_CONSTANT (val))
1213 return gimple_call_arg (def, 1);
1220 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1223 op0 = expr_expected_value (op0, visited);
1226 op1 = expr_expected_value (op1, visited);
1229 res = fold_build2 (code, type, op0, op1);
1230 if (TREE_CONSTANT (res))
1234 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1237 op0 = expr_expected_value (op0, visited);
1240 res = fold_build1 (code, type, op0);
1241 if (TREE_CONSTANT (res))
1248 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1249 The function is used by builtin_expect branch predictor so the evidence
1250 must come from this construct and additional possible constant folding.
1252 We may want to implement more involved value guess (such as value range
1253 propagation based prediction), but such tricks shall go to new
1257 expr_expected_value (tree expr, bitmap visited)
1259 enum tree_code code;
1262 if (TREE_CONSTANT (expr))
1265 extract_ops_from_tree (expr, &code, &op0, &op1);
1266 return expr_expected_value_1 (TREE_TYPE (expr),
1267 op0, code, op1, visited);
1271 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1272 we no longer need. */
1274 strip_predict_hints (void)
1282 gimple_stmt_iterator bi;
1283 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
1285 gimple stmt = gsi_stmt (bi);
1287 if (gimple_code (stmt) == GIMPLE_PREDICT)
1289 gsi_remove (&bi, true);
1292 else if (gimple_code (stmt) == GIMPLE_CALL)
1294 tree fndecl = gimple_call_fndecl (stmt);
1297 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1298 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1299 && gimple_call_num_args (stmt) == 2)
1301 var = gimple_call_lhs (stmt);
1302 ass_stmt = gimple_build_assign (var, gimple_call_arg (stmt, 0));
1304 gsi_replace (&bi, ass_stmt, true);
1313 /* Predict using opcode of the last statement in basic block. */
1315 tree_predict_by_opcode (basic_block bb)
1317 gimple stmt = last_stmt (bb);
1326 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1328 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1329 if (then_edge->flags & EDGE_TRUE_VALUE)
1331 op0 = gimple_cond_lhs (stmt);
1332 op1 = gimple_cond_rhs (stmt);
1333 cmp = gimple_cond_code (stmt);
1334 type = TREE_TYPE (op0);
1335 visited = BITMAP_ALLOC (NULL);
1336 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
1337 BITMAP_FREE (visited);
1340 if (integer_zerop (val))
1341 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1343 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1346 /* Try "pointer heuristic."
1347 A comparison ptr == 0 is predicted as false.
1348 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1349 if (POINTER_TYPE_P (type))
1352 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1353 else if (cmp == NE_EXPR)
1354 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1358 /* Try "opcode heuristic."
1359 EQ tests are usually false and NE tests are usually true. Also,
1360 most quantities are positive, so we can make the appropriate guesses
1361 about signed comparisons against zero. */
1366 /* Floating point comparisons appears to behave in a very
1367 unpredictable way because of special role of = tests in
1369 if (FLOAT_TYPE_P (type))
1371 /* Comparisons with 0 are often used for booleans and there is
1372 nothing useful to predict about them. */
1373 else if (integer_zerop (op0) || integer_zerop (op1))
1376 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1381 /* Floating point comparisons appears to behave in a very
1382 unpredictable way because of special role of = tests in
1384 if (FLOAT_TYPE_P (type))
1386 /* Comparisons with 0 are often used for booleans and there is
1387 nothing useful to predict about them. */
1388 else if (integer_zerop (op0)
1389 || integer_zerop (op1))
1392 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1396 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1399 case UNORDERED_EXPR:
1400 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1405 if (integer_zerop (op1)
1406 || integer_onep (op1)
1407 || integer_all_onesp (op1)
1410 || real_minus_onep (op1))
1411 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1416 if (integer_zerop (op1)
1417 || integer_onep (op1)
1418 || integer_all_onesp (op1)
1421 || real_minus_onep (op1))
1422 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1430 /* Try to guess whether the value of return means error code. */
1432 static enum br_predictor
1433 return_prediction (tree val, enum prediction *prediction)
1437 return PRED_NO_PREDICTION;
1438 /* Different heuristics for pointers and scalars. */
1439 if (POINTER_TYPE_P (TREE_TYPE (val)))
1441 /* NULL is usually not returned. */
1442 if (integer_zerop (val))
1444 *prediction = NOT_TAKEN;
1445 return PRED_NULL_RETURN;
1448 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1450 /* Negative return values are often used to indicate
1452 if (TREE_CODE (val) == INTEGER_CST
1453 && tree_int_cst_sgn (val) < 0)
1455 *prediction = NOT_TAKEN;
1456 return PRED_NEGATIVE_RETURN;
1458 /* Constant return values seems to be commonly taken.
1459 Zero/one often represent booleans so exclude them from the
1461 if (TREE_CONSTANT (val)
1462 && (!integer_zerop (val) && !integer_onep (val)))
1464 *prediction = TAKEN;
1465 return PRED_CONST_RETURN;
1468 return PRED_NO_PREDICTION;
1471 /* Find the basic block with return expression and look up for possible
1472 return value trying to apply RETURN_PREDICTION heuristics. */
1474 apply_return_prediction (void)
1476 gimple return_stmt = NULL;
1480 int phi_num_args, i;
1481 enum br_predictor pred;
1482 enum prediction direction;
1485 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1487 return_stmt = last_stmt (e->src);
1489 && gimple_code (return_stmt) == GIMPLE_RETURN)
1494 return_val = gimple_return_retval (return_stmt);
1497 if (TREE_CODE (return_val) != SSA_NAME
1498 || !SSA_NAME_DEF_STMT (return_val)
1499 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
1501 phi = SSA_NAME_DEF_STMT (return_val);
1502 phi_num_args = gimple_phi_num_args (phi);
1503 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1505 /* Avoid the degenerate case where all return values form the function
1506 belongs to same category (ie they are all positive constants)
1507 so we can hardly say something about them. */
1508 for (i = 1; i < phi_num_args; i++)
1509 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1511 if (i != phi_num_args)
1512 for (i = 0; i < phi_num_args; i++)
1514 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1515 if (pred != PRED_NO_PREDICTION)
1516 predict_paths_leading_to (gimple_phi_arg_edge (phi, i)->src, pred,
1521 /* Look for basic block that contains unlikely to happen events
1522 (such as noreturn calls) and mark all paths leading to execution
1523 of this basic blocks as unlikely. */
1526 tree_bb_level_predictions (void)
1530 apply_return_prediction ();
1534 gimple_stmt_iterator gsi;
1536 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1538 gimple stmt = gsi_stmt (gsi);
1541 if (is_gimple_call (stmt))
1543 if (gimple_call_flags (stmt) & ECF_NORETURN)
1544 predict_paths_leading_to (bb, PRED_NORETURN,
1546 decl = gimple_call_fndecl (stmt);
1548 && lookup_attribute ("cold",
1549 DECL_ATTRIBUTES (decl)))
1550 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
1553 else if (gimple_code (stmt) == GIMPLE_PREDICT)
1555 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
1556 gimple_predict_outcome (stmt));
1557 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1558 hints to callers. */
1564 #ifdef ENABLE_CHECKING
1566 /* Callback for pointer_map_traverse, asserts that the pointer map is
1570 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1571 void *data ATTRIBUTE_UNUSED)
1573 gcc_assert (!*value);
1578 /* Predict branch probabilities and estimate profile of the tree CFG. */
1580 tree_estimate_probability (void)
1584 loop_optimizer_init (0);
1585 if (dump_file && (dump_flags & TDF_DETAILS))
1586 flow_loops_dump (dump_file, NULL, 0);
1588 add_noreturn_fake_exit_edges ();
1589 connect_infinite_loops_to_exit ();
1590 /* We use loop_niter_by_eval, which requires that the loops have
1592 create_preheaders (CP_SIMPLE_PREHEADERS);
1593 calculate_dominance_info (CDI_POST_DOMINATORS);
1595 bb_predictions = pointer_map_create ();
1596 tree_bb_level_predictions ();
1598 mark_irreducible_loops ();
1599 record_loop_exits ();
1600 if (number_of_loops () > 1)
1608 FOR_EACH_EDGE (e, ei, bb->succs)
1610 /* Predict early returns to be probable, as we've already taken
1611 care for error returns and other cases are often used for
1612 fast paths through function.
1614 Since we've already removed the return statements, we are
1615 looking for CFG like:
1625 if (e->dest != bb->next_bb
1626 && e->dest != EXIT_BLOCK_PTR
1627 && single_succ_p (e->dest)
1628 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1629 && gimple_code (last_stmt (e->dest)) == GIMPLE_RETURN)
1634 if (single_succ_p (bb))
1636 FOR_EACH_EDGE (e1, ei1, bb->preds)
1637 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1638 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1639 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1640 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1643 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1644 && !predicted_by_p (e->src, PRED_CONST_RETURN)
1645 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1646 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1649 /* Look for block we are guarding (ie we dominate it,
1650 but it doesn't postdominate us). */
1651 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1652 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1653 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1655 gimple_stmt_iterator bi;
1657 /* The call heuristic claims that a guarded function call
1658 is improbable. This is because such calls are often used
1659 to signal exceptional situations such as printing error
1661 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
1664 gimple stmt = gsi_stmt (bi);
1665 if (is_gimple_call (stmt)
1666 /* Constant and pure calls are hardly used to signalize
1667 something exceptional. */
1668 && gimple_has_side_effects (stmt))
1670 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1676 tree_predict_by_opcode (bb);
1679 combine_predictions_for_bb (bb);
1681 #ifdef ENABLE_CHECKING
1682 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1684 pointer_map_destroy (bb_predictions);
1685 bb_predictions = NULL;
1687 estimate_bb_frequencies ();
1688 free_dominance_info (CDI_POST_DOMINATORS);
1689 remove_fake_exit_edges ();
1690 loop_optimizer_finalize ();
1691 if (dump_file && (dump_flags & TDF_DETAILS))
1692 gimple_dump_cfg (dump_file, dump_flags);
1693 if (profile_status == PROFILE_ABSENT)
1694 profile_status = PROFILE_GUESSED;
1698 /* Predict edges to successors of CUR whose sources are not postdominated by
1699 BB by PRED and recurse to all postdominators. */
1702 predict_paths_for_bb (basic_block cur, basic_block bb,
1703 enum br_predictor pred,
1704 enum prediction taken)
1710 /* We are looking for all edges forming edge cut induced by
1711 set of all blocks postdominated by BB. */
1712 FOR_EACH_EDGE (e, ei, cur->preds)
1713 if (e->src->index >= NUM_FIXED_BLOCKS
1714 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
1716 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
1717 predict_edge_def (e, pred, taken);
1719 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
1721 son = next_dom_son (CDI_POST_DOMINATORS, son))
1722 predict_paths_for_bb (son, bb, pred, taken);
1725 /* Sets branch probabilities according to PREDiction and
1729 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
1730 enum prediction taken)
1732 predict_paths_for_bb (bb, bb, pred, taken);
1735 /* This is used to carry information about basic blocks. It is
1736 attached to the AUX field of the standard CFG block. */
1738 typedef struct block_info_def
1740 /* Estimated frequency of execution of basic_block. */
1743 /* To keep queue of basic blocks to process. */
1746 /* Number of predecessors we need to visit first. */
1750 /* Similar information for edges. */
1751 typedef struct edge_info_def
1753 /* In case edge is a loopback edge, the probability edge will be reached
1754 in case header is. Estimated number of iterations of the loop can be
1755 then computed as 1 / (1 - back_edge_prob). */
1756 sreal back_edge_prob;
1757 /* True if the edge is a loopback edge in the natural loop. */
1758 unsigned int back_edge:1;
1761 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1762 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1764 /* Helper function for estimate_bb_frequencies.
1765 Propagate the frequencies in blocks marked in
1766 TOVISIT, starting in HEAD. */
1769 propagate_freq (basic_block head, bitmap tovisit)
1778 /* For each basic block we need to visit count number of his predecessors
1779 we need to visit first. */
1780 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1785 /* The outermost "loop" includes the exit block, which we can not
1786 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1787 directly. Do the same for the entry block. */
1788 bb = BASIC_BLOCK (i);
1790 FOR_EACH_EDGE (e, ei, bb->preds)
1792 bool visit = bitmap_bit_p (tovisit, e->src->index);
1794 if (visit && !(e->flags & EDGE_DFS_BACK))
1796 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1798 "Irreducible region hit, ignoring edge to %i->%i\n",
1799 e->src->index, bb->index);
1801 BLOCK_INFO (bb)->npredecessors = count;
1804 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1806 for (bb = head; bb; bb = nextbb)
1809 sreal cyclic_probability, frequency;
1811 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1812 memcpy (&frequency, &real_zero, sizeof (real_zero));
1814 nextbb = BLOCK_INFO (bb)->next;
1815 BLOCK_INFO (bb)->next = NULL;
1817 /* Compute frequency of basic block. */
1820 #ifdef ENABLE_CHECKING
1821 FOR_EACH_EDGE (e, ei, bb->preds)
1822 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1823 || (e->flags & EDGE_DFS_BACK));
1826 FOR_EACH_EDGE (e, ei, bb->preds)
1827 if (EDGE_INFO (e)->back_edge)
1829 sreal_add (&cyclic_probability, &cyclic_probability,
1830 &EDGE_INFO (e)->back_edge_prob);
1832 else if (!(e->flags & EDGE_DFS_BACK))
1836 /* frequency += (e->probability
1837 * BLOCK_INFO (e->src)->frequency /
1838 REG_BR_PROB_BASE); */
1840 sreal_init (&tmp, e->probability, 0);
1841 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1842 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1843 sreal_add (&frequency, &frequency, &tmp);
1846 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1848 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1849 sizeof (frequency));
1853 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
1855 memcpy (&cyclic_probability, &real_almost_one,
1856 sizeof (real_almost_one));
1859 /* BLOCK_INFO (bb)->frequency = frequency
1860 / (1 - cyclic_probability) */
1862 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
1863 sreal_div (&BLOCK_INFO (bb)->frequency,
1864 &frequency, &cyclic_probability);
1868 bitmap_clear_bit (tovisit, bb->index);
1870 e = find_edge (bb, head);
1875 /* EDGE_INFO (e)->back_edge_prob
1876 = ((e->probability * BLOCK_INFO (bb)->frequency)
1877 / REG_BR_PROB_BASE); */
1879 sreal_init (&tmp, e->probability, 0);
1880 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1881 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1882 &tmp, &real_inv_br_prob_base);
1885 /* Propagate to successor blocks. */
1886 FOR_EACH_EDGE (e, ei, bb->succs)
1887 if (!(e->flags & EDGE_DFS_BACK)
1888 && BLOCK_INFO (e->dest)->npredecessors)
1890 BLOCK_INFO (e->dest)->npredecessors--;
1891 if (!BLOCK_INFO (e->dest)->npredecessors)
1896 BLOCK_INFO (last)->next = e->dest;
1904 /* Estimate probabilities of loopback edges in loops at same nest level. */
1907 estimate_loops_at_level (struct loop *first_loop)
1911 for (loop = first_loop; loop; loop = loop->next)
1916 bitmap tovisit = BITMAP_ALLOC (NULL);
1918 estimate_loops_at_level (loop->inner);
1920 /* Find current loop back edge and mark it. */
1921 e = loop_latch_edge (loop);
1922 EDGE_INFO (e)->back_edge = 1;
1924 bbs = get_loop_body (loop);
1925 for (i = 0; i < loop->num_nodes; i++)
1926 bitmap_set_bit (tovisit, bbs[i]->index);
1928 propagate_freq (loop->header, tovisit);
1929 BITMAP_FREE (tovisit);
1933 /* Propagates frequencies through structure of loops. */
1936 estimate_loops (void)
1938 bitmap tovisit = BITMAP_ALLOC (NULL);
1941 /* Start by estimating the frequencies in the loops. */
1942 if (number_of_loops () > 1)
1943 estimate_loops_at_level (current_loops->tree_root->inner);
1945 /* Now propagate the frequencies through all the blocks. */
1948 bitmap_set_bit (tovisit, bb->index);
1950 propagate_freq (ENTRY_BLOCK_PTR, tovisit);
1951 BITMAP_FREE (tovisit);
1954 /* Convert counts measured by profile driven feedback to frequencies.
1955 Return nonzero iff there was any nonzero execution count. */
1958 counts_to_freqs (void)
1960 gcov_type count_max, true_count_max = 0;
1964 true_count_max = MAX (bb->count, true_count_max);
1966 count_max = MAX (true_count_max, 1);
1967 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1968 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1970 return true_count_max;
1973 /* Return true if function is likely to be expensive, so there is no point to
1974 optimize performance of prologue, epilogue or do inlining at the expense
1975 of code size growth. THRESHOLD is the limit of number of instructions
1976 function can execute at average to be still considered not expensive. */
1979 expensive_function_p (int threshold)
1981 unsigned int sum = 0;
1985 /* We can not compute accurately for large thresholds due to scaled
1987 gcc_assert (threshold <= BB_FREQ_MAX);
1989 /* Frequencies are out of range. This either means that function contains
1990 internal loop executing more than BB_FREQ_MAX times or profile feedback
1991 is available and function has not been executed at all. */
1992 if (ENTRY_BLOCK_PTR->frequency == 0)
1995 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1996 limit = ENTRY_BLOCK_PTR->frequency * threshold;
2001 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2002 insn = NEXT_INSN (insn))
2003 if (active_insn_p (insn))
2005 sum += bb->frequency;
2014 /* Estimate basic blocks frequency by given branch probabilities. */
2017 estimate_bb_frequencies (void)
2022 if (!flag_branch_probabilities || !counts_to_freqs ())
2024 static int real_values_initialized = 0;
2026 if (!real_values_initialized)
2028 real_values_initialized = 1;
2029 sreal_init (&real_zero, 0, 0);
2030 sreal_init (&real_one, 1, 0);
2031 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
2032 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
2033 sreal_init (&real_one_half, 1, -1);
2034 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
2035 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
2038 mark_dfs_back_edges ();
2040 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
2042 /* Set up block info for each basic block. */
2043 alloc_aux_for_blocks (sizeof (struct block_info_def));
2044 alloc_aux_for_edges (sizeof (struct edge_info_def));
2045 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2050 FOR_EACH_EDGE (e, ei, bb->succs)
2052 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
2053 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2054 &EDGE_INFO (e)->back_edge_prob,
2055 &real_inv_br_prob_base);
2059 /* First compute probabilities locally for each loop from innermost
2060 to outermost to examine probabilities for back edges. */
2063 memcpy (&freq_max, &real_zero, sizeof (real_zero));
2065 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
2066 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
2068 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
2069 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2073 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
2074 sreal_add (&tmp, &tmp, &real_one_half);
2075 bb->frequency = sreal_to_int (&tmp);
2078 free_aux_for_blocks ();
2079 free_aux_for_edges ();
2081 compute_function_frequency ();
2082 if (flag_reorder_functions)
2083 choose_function_section ();
2086 /* Decide whether function is hot, cold or unlikely executed. */
2088 compute_function_frequency (void)
2092 if (!profile_info || !flag_branch_probabilities)
2094 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2096 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
2097 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2099 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
2102 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
2105 if (maybe_hot_bb_p (bb))
2107 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
2110 if (!probably_never_executed_bb_p (bb))
2111 cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
2115 /* Choose appropriate section for the function. */
2117 choose_function_section (void)
2119 if (DECL_SECTION_NAME (current_function_decl)
2120 || !targetm.have_named_sections
2121 /* Theoretically we can split the gnu.linkonce text section too,
2122 but this requires more work as the frequency needs to match
2123 for all generated objects so we need to merge the frequency
2124 of all instances. For now just never set frequency for these. */
2125 || DECL_ONE_ONLY (current_function_decl))
2128 /* If we are doing the partitioning optimization, let the optimization
2129 choose the correct section into which to put things. */
2131 if (flag_reorder_blocks_and_partition)
2134 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
2135 DECL_SECTION_NAME (current_function_decl) =
2136 build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
2137 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
2138 DECL_SECTION_NAME (current_function_decl) =
2139 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
2140 UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
2144 gate_estimate_probability (void)
2146 return flag_guess_branch_prob;
2149 /* Build PREDICT_EXPR. */
2151 build_predict_expr (enum br_predictor predictor, enum prediction taken)
2153 tree t = build1 (PREDICT_EXPR, void_type_node,
2154 build_int_cst (NULL, predictor));
2155 PREDICT_EXPR_OUTCOME (t) = taken;
2160 predictor_name (enum br_predictor predictor)
2162 return predictor_info[predictor].name;
2165 struct gimple_opt_pass pass_profile =
2169 "profile", /* name */
2170 gate_estimate_probability, /* gate */
2171 tree_estimate_probability, /* execute */
2174 0, /* static_pass_number */
2175 TV_BRANCH_PROB, /* tv_id */
2176 PROP_cfg, /* properties_required */
2177 0, /* properties_provided */
2178 0, /* properties_destroyed */
2179 0, /* todo_flags_start */
2180 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2184 struct gimple_opt_pass pass_strip_predict_hints =
2190 strip_predict_hints, /* execute */
2193 0, /* static_pass_number */
2194 TV_BRANCH_PROB, /* tv_id */
2195 PROP_cfg, /* properties_required */
2196 0, /* properties_provided */
2197 0, /* properties_destroyed */
2198 0, /* todo_flags_start */
2199 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */