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 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 100 - 1)
71 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
72 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
73 #define PROB_ALWAYS (REG_BR_PROB_BASE)
75 static void combine_predictions_for_insn (rtx, basic_block);
76 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
77 static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
78 static void compute_function_frequency (void);
79 static void choose_function_section (void);
80 static bool can_predict_insn_p (const_rtx);
82 /* Information we hold about each branch predictor.
83 Filled using information from predict.def. */
87 const char *const name; /* Name used in the debugging dumps. */
88 const int hitrate; /* Expected hitrate used by
89 predict_insn_def call. */
93 /* Use given predictor without Dempster-Shaffer theory if it matches
94 using first_match heuristics. */
95 #define PRED_FLAG_FIRST_MATCH 1
97 /* Recompute hitrate in percent to our representation. */
99 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
101 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
102 static const struct predictor_info predictor_info[]= {
103 #include "predict.def"
105 /* Upper bound on predictors. */
110 /* Return TRUE if frequency FREQ is considered to be hot. */
112 maybe_hot_frequency_p (int freq)
114 if (!profile_info || !flag_branch_probabilities)
116 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
118 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
121 if (freq < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
126 /* Return true in case BB can be CPU intensive and should be optimized
127 for maximal performance. */
130 maybe_hot_bb_p (const_basic_block bb)
132 if (profile_info && flag_branch_probabilities
134 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
136 return maybe_hot_frequency_p (bb->frequency);
139 /* Return true in case BB can be CPU intensive and should be optimized
140 for maximal performance. */
143 maybe_hot_edge_p (edge e)
145 if (profile_info && flag_branch_probabilities
147 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
149 return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
152 /* Return true in case BB is cold and should be optimized for size. */
155 probably_cold_bb_p (const_basic_block bb)
157 if (profile_info && flag_branch_probabilities
159 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
161 if ((!profile_info || !flag_branch_probabilities)
162 && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
164 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
169 /* Return true in case BB is probably never executed. */
171 probably_never_executed_bb_p (const_basic_block bb)
173 if (profile_info && flag_branch_probabilities)
174 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
175 if ((!profile_info || !flag_branch_probabilities)
176 && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
181 /* Return true when current function should always be optimized for size. */
184 always_optimize_for_size_p (void)
186 return (optimize_size
187 || cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED);
190 /* Return TRUE when BB should be optimized for size. */
193 optimize_bb_for_size_p (basic_block bb)
195 return always_optimize_for_size_p () || !maybe_hot_bb_p (bb);
198 /* Return TRUE when BB should be optimized for speed. */
201 optimize_bb_for_speed_p (basic_block bb)
203 return !optimize_bb_for_size_p (bb);
206 /* Return TRUE when BB should be optimized for size. */
209 optimize_edge_for_size_p (edge e)
211 return always_optimize_for_size_p () || !maybe_hot_edge_p (e);
214 /* Return TRUE when BB should be optimized for speed. */
217 optimize_edge_for_speed_p (edge e)
219 return !optimize_edge_for_size_p (e);
222 /* Return TRUE when BB should be optimized for size. */
225 optimize_insn_for_size_p (void)
227 return always_optimize_for_size_p () || !crtl->maybe_hot_insn_p;
230 /* Return TRUE when BB should be optimized for speed. */
233 optimize_insn_for_speed_p (void)
235 return !optimize_insn_for_size_p ();
238 /* Set RTL expansion for BB profile. */
241 rtl_profile_for_bb (basic_block bb)
243 crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
246 /* Set RTL expansion for edge profile. */
249 rtl_profile_for_edge (edge e)
251 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
254 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
256 default_rtl_profile (void)
258 crtl->maybe_hot_insn_p = true;
261 /* Return true if the one of outgoing edges is already predicted by
265 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
268 if (!INSN_P (BB_END (bb)))
270 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
271 if (REG_NOTE_KIND (note) == REG_BR_PRED
272 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
277 /* This map contains for a basic block the list of predictions for the
280 static struct pointer_map_t *bb_predictions;
282 /* Return true if the one of outgoing edges is already predicted by
286 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
288 struct edge_prediction *i;
289 void **preds = pointer_map_contains (bb_predictions, bb);
294 for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
295 if (i->ep_predictor == predictor)
300 /* Return true when the probability of edge is reliable.
302 The profile guessing code is good at predicting branch outcome (ie.
303 taken/not taken), that is predicted right slightly over 75% of time.
304 It is however notoriously poor on predicting the probability itself.
305 In general the profile appear a lot flatter (with probabilities closer
306 to 50%) than the reality so it is bad idea to use it to drive optimization
307 such as those disabling dynamic branch prediction for well predictable
310 There are two exceptions - edges leading to noreturn edges and edges
311 predicted by number of iterations heuristics are predicted well. This macro
312 should be able to distinguish those, but at the moment it simply check for
313 noreturn heuristic that is only one giving probability over 99% or bellow
314 1%. In future we might want to propagate reliability information across the
315 CFG if we find this information useful on multiple places. */
317 probability_reliable_p (int prob)
319 return (profile_status == PROFILE_READ
320 || (profile_status == PROFILE_GUESSED
321 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
324 /* Same predicate as above, working on edges. */
326 edge_probability_reliable_p (const_edge e)
328 return probability_reliable_p (e->probability);
331 /* Same predicate as edge_probability_reliable_p, working on notes. */
333 br_prob_note_reliable_p (const_rtx note)
335 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
336 return probability_reliable_p (INTVAL (XEXP (note, 0)));
340 predict_insn (rtx insn, enum br_predictor predictor, int probability)
342 gcc_assert (any_condjump_p (insn));
343 if (!flag_guess_branch_prob)
346 add_reg_note (insn, REG_BR_PRED,
347 gen_rtx_CONCAT (VOIDmode,
348 GEN_INT ((int) predictor),
349 GEN_INT ((int) probability)));
352 /* Predict insn by given predictor. */
355 predict_insn_def (rtx insn, enum br_predictor predictor,
356 enum prediction taken)
358 int probability = predictor_info[(int) predictor].hitrate;
361 probability = REG_BR_PROB_BASE - probability;
363 predict_insn (insn, predictor, probability);
366 /* Predict edge E with given probability if possible. */
369 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
372 last_insn = BB_END (e->src);
374 /* We can store the branch prediction information only about
375 conditional jumps. */
376 if (!any_condjump_p (last_insn))
379 /* We always store probability of branching. */
380 if (e->flags & EDGE_FALLTHRU)
381 probability = REG_BR_PROB_BASE - probability;
383 predict_insn (last_insn, predictor, probability);
386 /* Predict edge E with the given PROBABILITY. */
388 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
390 gcc_assert (profile_status != PROFILE_GUESSED);
391 if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
392 && flag_guess_branch_prob && optimize)
394 struct edge_prediction *i = XNEW (struct edge_prediction);
395 void **preds = pointer_map_insert (bb_predictions, e->src);
397 i->ep_next = (struct edge_prediction *) *preds;
399 i->ep_probability = probability;
400 i->ep_predictor = predictor;
405 /* Remove all predictions on given basic block that are attached
408 remove_predictions_associated_with_edge (edge e)
415 preds = pointer_map_contains (bb_predictions, e->src);
419 struct edge_prediction **prediction = (struct edge_prediction **) preds;
420 struct edge_prediction *next;
424 if ((*prediction)->ep_edge == e)
426 next = (*prediction)->ep_next;
431 prediction = &((*prediction)->ep_next);
436 /* Clears the list of predictions stored for BB. */
439 clear_bb_predictions (basic_block bb)
441 void **preds = pointer_map_contains (bb_predictions, bb);
442 struct edge_prediction *pred, *next;
447 for (pred = (struct edge_prediction *) *preds; pred; pred = next)
449 next = pred->ep_next;
455 /* Return true when we can store prediction on insn INSN.
456 At the moment we represent predictions only on conditional
457 jumps, not at computed jump or other complicated cases. */
459 can_predict_insn_p (const_rtx insn)
461 return (JUMP_P (insn)
462 && any_condjump_p (insn)
463 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
466 /* Predict edge E by given predictor if possible. */
469 predict_edge_def (edge e, enum br_predictor predictor,
470 enum prediction taken)
472 int probability = predictor_info[(int) predictor].hitrate;
475 probability = REG_BR_PROB_BASE - probability;
477 predict_edge (e, predictor, probability);
480 /* Invert all branch predictions or probability notes in the INSN. This needs
481 to be done each time we invert the condition used by the jump. */
484 invert_br_probabilities (rtx insn)
488 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
489 if (REG_NOTE_KIND (note) == REG_BR_PROB)
490 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
491 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
492 XEXP (XEXP (note, 0), 1)
493 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
496 /* Dump information about the branch prediction to the output file. */
499 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
500 basic_block bb, int used)
508 FOR_EACH_EDGE (e, ei, bb->succs)
509 if (! (e->flags & EDGE_FALLTHRU))
512 fprintf (file, " %s heuristics%s: %.1f%%",
513 predictor_info[predictor].name,
514 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
518 fprintf (file, " exec ");
519 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
522 fprintf (file, " hit ");
523 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
524 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
528 fprintf (file, "\n");
531 /* We can not predict the probabilities of outgoing edges of bb. Set them
532 evenly and hope for the best. */
534 set_even_probabilities (basic_block bb)
540 FOR_EACH_EDGE (e, ei, bb->succs)
541 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
543 FOR_EACH_EDGE (e, ei, bb->succs)
544 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
545 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
550 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
551 note if not already present. Remove now useless REG_BR_PRED notes. */
554 combine_predictions_for_insn (rtx insn, basic_block bb)
559 int best_probability = PROB_EVEN;
560 int best_predictor = END_PREDICTORS;
561 int combined_probability = REG_BR_PROB_BASE / 2;
563 bool first_match = false;
566 if (!can_predict_insn_p (insn))
568 set_even_probabilities (bb);
572 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
573 pnote = ®_NOTES (insn);
575 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
578 /* We implement "first match" heuristics and use probability guessed
579 by predictor with smallest index. */
580 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
581 if (REG_NOTE_KIND (note) == REG_BR_PRED)
583 int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
584 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
587 if (best_predictor > predictor)
588 best_probability = probability, best_predictor = predictor;
590 d = (combined_probability * probability
591 + (REG_BR_PROB_BASE - combined_probability)
592 * (REG_BR_PROB_BASE - probability));
594 /* Use FP math to avoid overflows of 32bit integers. */
596 /* If one probability is 0% and one 100%, avoid division by zero. */
597 combined_probability = REG_BR_PROB_BASE / 2;
599 combined_probability = (((double) combined_probability) * probability
600 * REG_BR_PROB_BASE / d + 0.5);
603 /* Decide which heuristic to use. In case we didn't match anything,
604 use no_prediction heuristic, in case we did match, use either
605 first match or Dempster-Shaffer theory depending on the flags. */
607 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
611 dump_prediction (dump_file, PRED_NO_PREDICTION,
612 combined_probability, bb, true);
615 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
617 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
622 combined_probability = best_probability;
623 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
627 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
629 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
630 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
632 dump_prediction (dump_file, predictor, probability, bb,
633 !first_match || best_predictor == predictor);
634 *pnote = XEXP (*pnote, 1);
637 pnote = &XEXP (*pnote, 1);
642 add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
644 /* Save the prediction into CFG in case we are seeing non-degenerated
646 if (!single_succ_p (bb))
648 BRANCH_EDGE (bb)->probability = combined_probability;
649 FALLTHRU_EDGE (bb)->probability
650 = REG_BR_PROB_BASE - combined_probability;
653 else if (!single_succ_p (bb))
655 int prob = INTVAL (XEXP (prob_note, 0));
657 BRANCH_EDGE (bb)->probability = prob;
658 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
661 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
664 /* Combine predictions into single probability and store them into CFG.
665 Remove now useless prediction entries. */
668 combine_predictions_for_bb (basic_block bb)
670 int best_probability = PROB_EVEN;
671 int best_predictor = END_PREDICTORS;
672 int combined_probability = REG_BR_PROB_BASE / 2;
674 bool first_match = false;
676 struct edge_prediction *pred;
678 edge e, first = NULL, second = NULL;
682 FOR_EACH_EDGE (e, ei, bb->succs)
683 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
686 if (first && !second)
692 /* When there is no successor or only one choice, prediction is easy.
694 We are lazy for now and predict only basic blocks with two outgoing
695 edges. It is possible to predict generic case too, but we have to
696 ignore first match heuristics and do more involved combining. Implement
701 set_even_probabilities (bb);
702 clear_bb_predictions (bb);
704 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
710 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
712 preds = pointer_map_contains (bb_predictions, bb);
715 /* We implement "first match" heuristics and use probability guessed
716 by predictor with smallest index. */
717 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
719 int predictor = pred->ep_predictor;
720 int probability = pred->ep_probability;
722 if (pred->ep_edge != first)
723 probability = REG_BR_PROB_BASE - probability;
726 if (best_predictor > predictor)
727 best_probability = probability, best_predictor = predictor;
729 d = (combined_probability * probability
730 + (REG_BR_PROB_BASE - combined_probability)
731 * (REG_BR_PROB_BASE - probability));
733 /* Use FP math to avoid overflows of 32bit integers. */
735 /* If one probability is 0% and one 100%, avoid division by zero. */
736 combined_probability = REG_BR_PROB_BASE / 2;
738 combined_probability = (((double) combined_probability)
740 * REG_BR_PROB_BASE / d + 0.5);
744 /* Decide which heuristic to use. In case we didn't match anything,
745 use no_prediction heuristic, in case we did match, use either
746 first match or Dempster-Shaffer theory depending on the flags. */
748 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
752 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
755 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
757 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
762 combined_probability = best_probability;
763 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
767 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
769 int predictor = pred->ep_predictor;
770 int probability = pred->ep_probability;
772 if (pred->ep_edge != EDGE_SUCC (bb, 0))
773 probability = REG_BR_PROB_BASE - probability;
774 dump_prediction (dump_file, predictor, probability, bb,
775 !first_match || best_predictor == predictor);
778 clear_bb_predictions (bb);
782 first->probability = combined_probability;
783 second->probability = REG_BR_PROB_BASE - combined_probability;
787 /* Predict edge probabilities by exploiting loop structure. */
797 /* Try to predict out blocks in a loop that are not part of a
799 FOR_EACH_LOOP (li, loop, 0)
801 basic_block bb, *bbs;
803 VEC (edge, heap) *exits;
804 struct tree_niter_desc niter_desc;
807 exits = get_loop_exit_edges (loop);
808 n_exits = VEC_length (edge, exits);
810 for (j = 0; VEC_iterate (edge, exits, j, ex); j++)
813 HOST_WIDE_INT nitercst;
814 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
816 enum br_predictor predictor;
818 if (number_of_iterations_exit (loop, ex, &niter_desc, false))
819 niter = niter_desc.niter;
820 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
821 niter = loop_niter_by_eval (loop, ex);
823 if (TREE_CODE (niter) == INTEGER_CST)
825 if (host_integerp (niter, 1)
826 && compare_tree_int (niter, max-1) == -1)
827 nitercst = tree_low_cst (niter, 1) + 1;
830 predictor = PRED_LOOP_ITERATIONS;
832 /* If we have just one exit and we can derive some information about
833 the number of iterations of the loop from the statements inside
834 the loop, use it to predict this exit. */
835 else if (n_exits == 1)
837 nitercst = estimated_loop_iterations_int (loop, false);
843 predictor = PRED_LOOP_ITERATIONS_GUESSED;
848 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
849 predict_edge (ex, predictor, probability);
851 VEC_free (edge, heap, exits);
853 bbs = get_loop_body (loop);
855 for (j = 0; j < loop->num_nodes; j++)
857 int header_found = 0;
863 /* Bypass loop heuristics on continue statement. These
864 statements construct loops via "non-loop" constructs
865 in the source language and are better to be handled
867 if (predicted_by_p (bb, PRED_CONTINUE))
870 /* Loop branch heuristics - predict an edge back to a
871 loop's head as taken. */
872 if (bb == loop->latch)
874 e = find_edge (loop->latch, loop->header);
878 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
882 /* Loop exit heuristics - predict an edge exiting the loop if the
883 conditional has no loop header successors as not taken. */
885 /* If we already used more reliable loop exit predictors, do not
886 bother with PRED_LOOP_EXIT. */
887 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
888 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
890 /* For loop with many exits we don't want to predict all exits
891 with the pretty large probability, because if all exits are
892 considered in row, the loop would be predicted to iterate
893 almost never. The code to divide probability by number of
894 exits is very rough. It should compute the number of exits
895 taken in each patch through function (not the overall number
896 of exits that might be a lot higher for loops with wide switch
897 statements in them) and compute n-th square root.
899 We limit the minimal probability by 2% to avoid
900 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
901 as this was causing regression in perl benchmark containing such
904 int probability = ((REG_BR_PROB_BASE
905 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
907 if (probability < HITRATE (2))
908 probability = HITRATE (2);
909 FOR_EACH_EDGE (e, ei, bb->succs)
910 if (e->dest->index < NUM_FIXED_BLOCKS
911 || !flow_bb_inside_loop_p (loop, e->dest))
912 predict_edge (e, PRED_LOOP_EXIT, probability);
916 /* Free basic blocks from get_loop_body. */
923 /* Attempt to predict probabilities of BB outgoing edges using local
926 bb_estimate_probability_locally (basic_block bb)
928 rtx last_insn = BB_END (bb);
931 if (! can_predict_insn_p (last_insn))
933 cond = get_condition (last_insn, NULL, false, false);
937 /* Try "pointer heuristic."
938 A comparison ptr == 0 is predicted as false.
939 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
940 if (COMPARISON_P (cond)
941 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
942 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
944 if (GET_CODE (cond) == EQ)
945 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
946 else if (GET_CODE (cond) == NE)
947 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
951 /* Try "opcode heuristic."
952 EQ tests are usually false and NE tests are usually true. Also,
953 most quantities are positive, so we can make the appropriate guesses
954 about signed comparisons against zero. */
955 switch (GET_CODE (cond))
958 /* Unconditional branch. */
959 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
960 cond == const0_rtx ? NOT_TAKEN : TAKEN);
965 /* Floating point comparisons appears to behave in a very
966 unpredictable way because of special role of = tests in
968 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
970 /* Comparisons with 0 are often used for booleans and there is
971 nothing useful to predict about them. */
972 else if (XEXP (cond, 1) == const0_rtx
973 || XEXP (cond, 0) == const0_rtx)
976 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
981 /* Floating point comparisons appears to behave in a very
982 unpredictable way because of special role of = tests in
984 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
986 /* Comparisons with 0 are often used for booleans and there is
987 nothing useful to predict about them. */
988 else if (XEXP (cond, 1) == const0_rtx
989 || XEXP (cond, 0) == const0_rtx)
992 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
996 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1000 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1005 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1006 || XEXP (cond, 1) == constm1_rtx)
1007 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1012 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1013 || XEXP (cond, 1) == constm1_rtx)
1014 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1022 /* Set edge->probability for each successor edge of BB. */
1024 guess_outgoing_edge_probabilities (basic_block bb)
1026 bb_estimate_probability_locally (bb);
1027 combine_predictions_for_insn (BB_END (bb), bb);
1030 static tree expr_expected_value (tree, bitmap);
1032 /* Helper function for expr_expected_value. */
1035 expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited)
1039 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1041 if (TREE_CONSTANT (op0))
1044 if (code != SSA_NAME)
1047 def = SSA_NAME_DEF_STMT (op0);
1049 /* If we were already here, break the infinite cycle. */
1050 if (bitmap_bit_p (visited, SSA_NAME_VERSION (op0)))
1052 bitmap_set_bit (visited, SSA_NAME_VERSION (op0));
1054 if (gimple_code (def) == GIMPLE_PHI)
1056 /* All the arguments of the PHI node must have the same constant
1058 int i, n = gimple_phi_num_args (def);
1059 tree val = NULL, new_val;
1061 for (i = 0; i < n; i++)
1063 tree arg = PHI_ARG_DEF (def, i);
1065 /* If this PHI has itself as an argument, we cannot
1066 determine the string length of this argument. However,
1067 if we can find an expected constant value for the other
1068 PHI args then we can still be sure that this is
1069 likely a constant. So be optimistic and just
1070 continue with the next argument. */
1071 if (arg == PHI_RESULT (def))
1074 new_val = expr_expected_value (arg, visited);
1079 else if (!operand_equal_p (val, new_val, false))
1084 if (is_gimple_assign (def))
1086 if (gimple_assign_lhs (def) != op0)
1089 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1090 gimple_assign_rhs1 (def),
1091 gimple_assign_rhs_code (def),
1092 gimple_assign_rhs2 (def),
1096 if (is_gimple_call (def))
1098 tree decl = gimple_call_fndecl (def);
1101 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
1102 && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
1106 if (gimple_call_num_args (def) != 2)
1108 val = gimple_call_arg (def, 0);
1109 if (TREE_CONSTANT (val))
1111 return gimple_call_arg (def, 1);
1118 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1121 op0 = expr_expected_value (op0, visited);
1124 op1 = expr_expected_value (op1, visited);
1127 res = fold_build2 (code, type, op0, op1);
1128 if (TREE_CONSTANT (res))
1132 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1135 op0 = expr_expected_value (op0, visited);
1138 res = fold_build1 (code, type, op0);
1139 if (TREE_CONSTANT (res))
1146 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1147 The function is used by builtin_expect branch predictor so the evidence
1148 must come from this construct and additional possible constant folding.
1150 We may want to implement more involved value guess (such as value range
1151 propagation based prediction), but such tricks shall go to new
1155 expr_expected_value (tree expr, bitmap visited)
1157 enum tree_code code;
1160 if (TREE_CONSTANT (expr))
1163 extract_ops_from_tree (expr, &code, &op0, &op1);
1164 return expr_expected_value_1 (TREE_TYPE (expr),
1165 op0, code, op1, visited);
1169 /* Get rid of all builtin_expect calls we no longer need. */
1171 strip_builtin_expect (void)
1179 gimple_stmt_iterator bi;
1180 for (bi = gsi_start_bb (bb); !gsi_end_p (bi); gsi_next (&bi))
1182 gimple stmt = gsi_stmt (bi);
1185 if (gimple_code (stmt) != GIMPLE_CALL)
1188 fndecl = gimple_call_fndecl (stmt);
1191 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1192 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1193 && gimple_call_num_args (stmt) == 2)
1195 var = gimple_call_lhs (stmt);
1196 ass_stmt = gimple_build_assign (var, gimple_call_arg (stmt, 0));
1198 gsi_replace (&bi, ass_stmt, true);
1204 /* Predict using opcode of the last statement in basic block. */
1206 tree_predict_by_opcode (basic_block bb)
1208 gimple stmt = last_stmt (bb);
1217 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1219 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1220 if (then_edge->flags & EDGE_TRUE_VALUE)
1222 op0 = gimple_cond_lhs (stmt);
1223 op1 = gimple_cond_rhs (stmt);
1224 cmp = gimple_cond_code (stmt);
1225 type = TREE_TYPE (op0);
1226 visited = BITMAP_ALLOC (NULL);
1227 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
1228 BITMAP_FREE (visited);
1231 if (integer_zerop (val))
1232 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1234 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1237 /* Try "pointer heuristic."
1238 A comparison ptr == 0 is predicted as false.
1239 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1240 if (POINTER_TYPE_P (type))
1243 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1244 else if (cmp == NE_EXPR)
1245 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1249 /* Try "opcode heuristic."
1250 EQ tests are usually false and NE tests are usually true. Also,
1251 most quantities are positive, so we can make the appropriate guesses
1252 about signed comparisons against zero. */
1257 /* Floating point comparisons appears to behave in a very
1258 unpredictable way because of special role of = tests in
1260 if (FLOAT_TYPE_P (type))
1262 /* Comparisons with 0 are often used for booleans and there is
1263 nothing useful to predict about them. */
1264 else if (integer_zerop (op0) || integer_zerop (op1))
1267 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1272 /* Floating point comparisons appears to behave in a very
1273 unpredictable way because of special role of = tests in
1275 if (FLOAT_TYPE_P (type))
1277 /* Comparisons with 0 are often used for booleans and there is
1278 nothing useful to predict about them. */
1279 else if (integer_zerop (op0)
1280 || integer_zerop (op1))
1283 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1287 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1290 case UNORDERED_EXPR:
1291 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1296 if (integer_zerop (op1)
1297 || integer_onep (op1)
1298 || integer_all_onesp (op1)
1301 || real_minus_onep (op1))
1302 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1307 if (integer_zerop (op1)
1308 || integer_onep (op1)
1309 || integer_all_onesp (op1)
1312 || real_minus_onep (op1))
1313 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1321 /* Try to guess whether the value of return means error code. */
1323 static enum br_predictor
1324 return_prediction (tree val, enum prediction *prediction)
1328 return PRED_NO_PREDICTION;
1329 /* Different heuristics for pointers and scalars. */
1330 if (POINTER_TYPE_P (TREE_TYPE (val)))
1332 /* NULL is usually not returned. */
1333 if (integer_zerop (val))
1335 *prediction = NOT_TAKEN;
1336 return PRED_NULL_RETURN;
1339 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1341 /* Negative return values are often used to indicate
1343 if (TREE_CODE (val) == INTEGER_CST
1344 && tree_int_cst_sgn (val) < 0)
1346 *prediction = NOT_TAKEN;
1347 return PRED_NEGATIVE_RETURN;
1349 /* Constant return values seems to be commonly taken.
1350 Zero/one often represent booleans so exclude them from the
1352 if (TREE_CONSTANT (val)
1353 && (!integer_zerop (val) && !integer_onep (val)))
1355 *prediction = TAKEN;
1356 return PRED_CONST_RETURN;
1359 return PRED_NO_PREDICTION;
1362 /* Find the basic block with return expression and look up for possible
1363 return value trying to apply RETURN_PREDICTION heuristics. */
1365 apply_return_prediction (void)
1367 gimple return_stmt = NULL;
1371 int phi_num_args, i;
1372 enum br_predictor pred;
1373 enum prediction direction;
1376 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1378 return_stmt = last_stmt (e->src);
1380 && gimple_code (return_stmt) == GIMPLE_RETURN)
1385 return_val = gimple_return_retval (return_stmt);
1388 if (TREE_CODE (return_val) != SSA_NAME
1389 || !SSA_NAME_DEF_STMT (return_val)
1390 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
1392 phi = SSA_NAME_DEF_STMT (return_val);
1393 phi_num_args = gimple_phi_num_args (phi);
1394 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1396 /* Avoid the degenerate case where all return values form the function
1397 belongs to same category (ie they are all positive constants)
1398 so we can hardly say something about them. */
1399 for (i = 1; i < phi_num_args; i++)
1400 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1402 if (i != phi_num_args)
1403 for (i = 0; i < phi_num_args; i++)
1405 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1406 if (pred != PRED_NO_PREDICTION)
1407 predict_paths_leading_to (gimple_phi_arg_edge (phi, i)->src, pred,
1412 /* Look for basic block that contains unlikely to happen events
1413 (such as noreturn calls) and mark all paths leading to execution
1414 of this basic blocks as unlikely. */
1417 tree_bb_level_predictions (void)
1421 apply_return_prediction ();
1425 gimple_stmt_iterator gsi;
1427 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1429 gimple stmt = gsi_stmt (gsi);
1432 if (is_gimple_call (stmt))
1434 if (gimple_call_flags (stmt) & ECF_NORETURN)
1435 predict_paths_leading_to (bb, PRED_NORETURN,
1437 decl = gimple_call_fndecl (stmt);
1439 && lookup_attribute ("cold",
1440 DECL_ATTRIBUTES (decl)))
1441 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
1444 else if (gimple_code (stmt) == GIMPLE_PREDICT)
1446 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
1447 gimple_predict_outcome (stmt));
1448 gsi_remove (&gsi, true);
1457 #ifdef ENABLE_CHECKING
1459 /* Callback for pointer_map_traverse, asserts that the pointer map is
1463 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1464 void *data ATTRIBUTE_UNUSED)
1466 gcc_assert (!*value);
1471 /* Predict branch probabilities and estimate profile of the tree CFG. */
1473 tree_estimate_probability (void)
1477 loop_optimizer_init (0);
1478 if (dump_file && (dump_flags & TDF_DETAILS))
1479 flow_loops_dump (dump_file, NULL, 0);
1481 add_noreturn_fake_exit_edges ();
1482 connect_infinite_loops_to_exit ();
1483 /* We use loop_niter_by_eval, which requires that the loops have
1485 create_preheaders (CP_SIMPLE_PREHEADERS);
1486 calculate_dominance_info (CDI_POST_DOMINATORS);
1488 bb_predictions = pointer_map_create ();
1489 tree_bb_level_predictions ();
1491 mark_irreducible_loops ();
1492 record_loop_exits ();
1493 if (number_of_loops () > 1)
1501 FOR_EACH_EDGE (e, ei, bb->succs)
1503 /* Predict early returns to be probable, as we've already taken
1504 care for error returns and other cases are often used for
1505 fast paths through function.
1507 Since we've already removed the return statements, we are
1508 looking for CFG like:
1518 if (e->dest != bb->next_bb
1519 && e->dest != EXIT_BLOCK_PTR
1520 && single_succ_p (e->dest)
1521 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1522 && gimple_code (last_stmt (e->dest)) == GIMPLE_RETURN)
1527 if (single_succ_p (bb))
1529 FOR_EACH_EDGE (e1, ei1, bb->preds)
1530 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1531 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1532 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1533 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1536 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1537 && !predicted_by_p (e->src, PRED_CONST_RETURN)
1538 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1539 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1542 /* Look for block we are guarding (ie we dominate it,
1543 but it doesn't postdominate us). */
1544 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1545 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1546 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1548 gimple_stmt_iterator bi;
1550 /* The call heuristic claims that a guarded function call
1551 is improbable. This is because such calls are often used
1552 to signal exceptional situations such as printing error
1554 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
1557 gimple stmt = gsi_stmt (bi);
1558 if (is_gimple_call (stmt)
1559 /* Constant and pure calls are hardly used to signalize
1560 something exceptional. */
1561 && gimple_has_side_effects (stmt))
1563 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1569 tree_predict_by_opcode (bb);
1572 combine_predictions_for_bb (bb);
1574 #ifdef ENABLE_CHECKING
1575 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1577 pointer_map_destroy (bb_predictions);
1578 bb_predictions = NULL;
1580 strip_builtin_expect ();
1581 estimate_bb_frequencies ();
1582 free_dominance_info (CDI_POST_DOMINATORS);
1583 remove_fake_exit_edges ();
1584 loop_optimizer_finalize ();
1585 if (dump_file && (dump_flags & TDF_DETAILS))
1586 gimple_dump_cfg (dump_file, dump_flags);
1587 if (profile_status == PROFILE_ABSENT)
1588 profile_status = PROFILE_GUESSED;
1592 /* Predict edges to successors of CUR whose sources are not postdominated by
1593 BB by PRED and recurse to all postdominators. */
1596 predict_paths_for_bb (basic_block cur, basic_block bb,
1597 enum br_predictor pred,
1598 enum prediction taken)
1604 /* We are looking for all edges forming edge cut induced by
1605 set of all blocks postdominated by BB. */
1606 FOR_EACH_EDGE (e, ei, cur->preds)
1607 if (e->src->index >= NUM_FIXED_BLOCKS
1608 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
1610 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
1611 predict_edge_def (e, pred, taken);
1613 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
1615 son = next_dom_son (CDI_POST_DOMINATORS, son))
1616 predict_paths_for_bb (son, bb, pred, taken);
1619 /* Sets branch probabilities according to PREDiction and
1623 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
1624 enum prediction taken)
1626 predict_paths_for_bb (bb, bb, pred, taken);
1629 /* This is used to carry information about basic blocks. It is
1630 attached to the AUX field of the standard CFG block. */
1632 typedef struct block_info_def
1634 /* Estimated frequency of execution of basic_block. */
1637 /* To keep queue of basic blocks to process. */
1640 /* Number of predecessors we need to visit first. */
1644 /* Similar information for edges. */
1645 typedef struct edge_info_def
1647 /* In case edge is a loopback edge, the probability edge will be reached
1648 in case header is. Estimated number of iterations of the loop can be
1649 then computed as 1 / (1 - back_edge_prob). */
1650 sreal back_edge_prob;
1651 /* True if the edge is a loopback edge in the natural loop. */
1652 unsigned int back_edge:1;
1655 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1656 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1658 /* Helper function for estimate_bb_frequencies.
1659 Propagate the frequencies in blocks marked in
1660 TOVISIT, starting in HEAD. */
1663 propagate_freq (basic_block head, bitmap tovisit)
1672 /* For each basic block we need to visit count number of his predecessors
1673 we need to visit first. */
1674 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1679 /* The outermost "loop" includes the exit block, which we can not
1680 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1681 directly. Do the same for the entry block. */
1682 bb = BASIC_BLOCK (i);
1684 FOR_EACH_EDGE (e, ei, bb->preds)
1686 bool visit = bitmap_bit_p (tovisit, e->src->index);
1688 if (visit && !(e->flags & EDGE_DFS_BACK))
1690 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1692 "Irreducible region hit, ignoring edge to %i->%i\n",
1693 e->src->index, bb->index);
1695 BLOCK_INFO (bb)->npredecessors = count;
1698 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1700 for (bb = head; bb; bb = nextbb)
1703 sreal cyclic_probability, frequency;
1705 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1706 memcpy (&frequency, &real_zero, sizeof (real_zero));
1708 nextbb = BLOCK_INFO (bb)->next;
1709 BLOCK_INFO (bb)->next = NULL;
1711 /* Compute frequency of basic block. */
1714 #ifdef ENABLE_CHECKING
1715 FOR_EACH_EDGE (e, ei, bb->preds)
1716 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1717 || (e->flags & EDGE_DFS_BACK));
1720 FOR_EACH_EDGE (e, ei, bb->preds)
1721 if (EDGE_INFO (e)->back_edge)
1723 sreal_add (&cyclic_probability, &cyclic_probability,
1724 &EDGE_INFO (e)->back_edge_prob);
1726 else if (!(e->flags & EDGE_DFS_BACK))
1730 /* frequency += (e->probability
1731 * BLOCK_INFO (e->src)->frequency /
1732 REG_BR_PROB_BASE); */
1734 sreal_init (&tmp, e->probability, 0);
1735 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1736 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1737 sreal_add (&frequency, &frequency, &tmp);
1740 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1742 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1743 sizeof (frequency));
1747 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
1749 memcpy (&cyclic_probability, &real_almost_one,
1750 sizeof (real_almost_one));
1753 /* BLOCK_INFO (bb)->frequency = frequency
1754 / (1 - cyclic_probability) */
1756 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
1757 sreal_div (&BLOCK_INFO (bb)->frequency,
1758 &frequency, &cyclic_probability);
1762 bitmap_clear_bit (tovisit, bb->index);
1764 e = find_edge (bb, head);
1769 /* EDGE_INFO (e)->back_edge_prob
1770 = ((e->probability * BLOCK_INFO (bb)->frequency)
1771 / REG_BR_PROB_BASE); */
1773 sreal_init (&tmp, e->probability, 0);
1774 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1775 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1776 &tmp, &real_inv_br_prob_base);
1779 /* Propagate to successor blocks. */
1780 FOR_EACH_EDGE (e, ei, bb->succs)
1781 if (!(e->flags & EDGE_DFS_BACK)
1782 && BLOCK_INFO (e->dest)->npredecessors)
1784 BLOCK_INFO (e->dest)->npredecessors--;
1785 if (!BLOCK_INFO (e->dest)->npredecessors)
1790 BLOCK_INFO (last)->next = e->dest;
1798 /* Estimate probabilities of loopback edges in loops at same nest level. */
1801 estimate_loops_at_level (struct loop *first_loop)
1805 for (loop = first_loop; loop; loop = loop->next)
1810 bitmap tovisit = BITMAP_ALLOC (NULL);
1812 estimate_loops_at_level (loop->inner);
1814 /* Find current loop back edge and mark it. */
1815 e = loop_latch_edge (loop);
1816 EDGE_INFO (e)->back_edge = 1;
1818 bbs = get_loop_body (loop);
1819 for (i = 0; i < loop->num_nodes; i++)
1820 bitmap_set_bit (tovisit, bbs[i]->index);
1822 propagate_freq (loop->header, tovisit);
1823 BITMAP_FREE (tovisit);
1827 /* Propagates frequencies through structure of loops. */
1830 estimate_loops (void)
1832 bitmap tovisit = BITMAP_ALLOC (NULL);
1835 /* Start by estimating the frequencies in the loops. */
1836 if (number_of_loops () > 1)
1837 estimate_loops_at_level (current_loops->tree_root->inner);
1839 /* Now propagate the frequencies through all the blocks. */
1842 bitmap_set_bit (tovisit, bb->index);
1844 propagate_freq (ENTRY_BLOCK_PTR, tovisit);
1845 BITMAP_FREE (tovisit);
1848 /* Convert counts measured by profile driven feedback to frequencies.
1849 Return nonzero iff there was any nonzero execution count. */
1852 counts_to_freqs (void)
1854 gcov_type count_max, true_count_max = 0;
1858 true_count_max = MAX (bb->count, true_count_max);
1860 count_max = MAX (true_count_max, 1);
1861 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1862 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1864 return true_count_max;
1867 /* Return true if function is likely to be expensive, so there is no point to
1868 optimize performance of prologue, epilogue or do inlining at the expense
1869 of code size growth. THRESHOLD is the limit of number of instructions
1870 function can execute at average to be still considered not expensive. */
1873 expensive_function_p (int threshold)
1875 unsigned int sum = 0;
1879 /* We can not compute accurately for large thresholds due to scaled
1881 gcc_assert (threshold <= BB_FREQ_MAX);
1883 /* Frequencies are out of range. This either means that function contains
1884 internal loop executing more than BB_FREQ_MAX times or profile feedback
1885 is available and function has not been executed at all. */
1886 if (ENTRY_BLOCK_PTR->frequency == 0)
1889 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1890 limit = ENTRY_BLOCK_PTR->frequency * threshold;
1895 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1896 insn = NEXT_INSN (insn))
1897 if (active_insn_p (insn))
1899 sum += bb->frequency;
1908 /* Estimate basic blocks frequency by given branch probabilities. */
1911 estimate_bb_frequencies (void)
1916 if (!flag_branch_probabilities || !counts_to_freqs ())
1918 static int real_values_initialized = 0;
1920 if (!real_values_initialized)
1922 real_values_initialized = 1;
1923 sreal_init (&real_zero, 0, 0);
1924 sreal_init (&real_one, 1, 0);
1925 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
1926 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
1927 sreal_init (&real_one_half, 1, -1);
1928 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
1929 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
1932 mark_dfs_back_edges ();
1934 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
1936 /* Set up block info for each basic block. */
1937 alloc_aux_for_blocks (sizeof (struct block_info_def));
1938 alloc_aux_for_edges (sizeof (struct edge_info_def));
1939 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1944 FOR_EACH_EDGE (e, ei, bb->succs)
1946 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
1947 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1948 &EDGE_INFO (e)->back_edge_prob,
1949 &real_inv_br_prob_base);
1953 /* First compute probabilities locally for each loop from innermost
1954 to outermost to examine probabilities for back edges. */
1957 memcpy (&freq_max, &real_zero, sizeof (real_zero));
1959 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
1960 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
1962 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
1963 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1967 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
1968 sreal_add (&tmp, &tmp, &real_one_half);
1969 bb->frequency = sreal_to_int (&tmp);
1972 free_aux_for_blocks ();
1973 free_aux_for_edges ();
1975 compute_function_frequency ();
1976 if (flag_reorder_functions)
1977 choose_function_section ();
1980 /* Decide whether function is hot, cold or unlikely executed. */
1982 compute_function_frequency (void)
1986 if (!profile_info || !flag_branch_probabilities)
1988 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
1990 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1991 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
1993 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1996 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1999 if (maybe_hot_bb_p (bb))
2001 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
2004 if (!probably_never_executed_bb_p (bb))
2005 cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
2009 /* Choose appropriate section for the function. */
2011 choose_function_section (void)
2013 if (DECL_SECTION_NAME (current_function_decl)
2014 || !targetm.have_named_sections
2015 /* Theoretically we can split the gnu.linkonce text section too,
2016 but this requires more work as the frequency needs to match
2017 for all generated objects so we need to merge the frequency
2018 of all instances. For now just never set frequency for these. */
2019 || DECL_ONE_ONLY (current_function_decl))
2022 /* If we are doing the partitioning optimization, let the optimization
2023 choose the correct section into which to put things. */
2025 if (flag_reorder_blocks_and_partition)
2028 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
2029 DECL_SECTION_NAME (current_function_decl) =
2030 build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
2031 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
2032 DECL_SECTION_NAME (current_function_decl) =
2033 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
2034 UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
2038 gate_estimate_probability (void)
2040 return flag_guess_branch_prob;
2043 /* Build PREDICT_EXPR. */
2045 build_predict_expr (enum br_predictor predictor, enum prediction taken)
2047 tree t = build1 (PREDICT_EXPR, void_type_node,
2048 build_int_cst (NULL, predictor));
2049 PREDICT_EXPR_OUTCOME (t) = taken;
2054 predictor_name (enum br_predictor predictor)
2056 return predictor_info[predictor].name;
2059 struct gimple_opt_pass pass_profile =
2063 "profile", /* name */
2064 gate_estimate_probability, /* gate */
2065 tree_estimate_probability, /* execute */
2068 0, /* static_pass_number */
2069 TV_BRANCH_PROB, /* tv_id */
2070 PROP_cfg, /* properties_required */
2071 0, /* properties_provided */
2072 0, /* properties_destroyed */
2073 0, /* todo_flags_start */
2074 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */