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 (profile_status == PROFILE_ABSENT)
123 if (freq < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
128 /* Return true in case BB can be CPU intensive and should be optimized
129 for maximal performance. */
132 maybe_hot_bb_p (const_basic_block bb)
134 if (profile_info && flag_branch_probabilities
136 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
138 return maybe_hot_frequency_p (bb->frequency);
141 /* Return true in case BB can be CPU intensive and should be optimized
142 for maximal performance. */
145 maybe_hot_edge_p (edge e)
147 if (profile_info && flag_branch_probabilities
149 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
151 return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
154 /* Return true in case BB is cold and should be optimized for size. */
157 probably_cold_bb_p (const_basic_block bb)
159 if (profile_info && flag_branch_probabilities
161 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
163 if ((!profile_info || !flag_branch_probabilities)
164 && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
166 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
171 /* Return true in case BB is probably never executed. */
173 probably_never_executed_bb_p (const_basic_block bb)
175 if (profile_info && flag_branch_probabilities)
176 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
177 if ((!profile_info || !flag_branch_probabilities)
178 && cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
183 /* Return true when current function should always be optimized for size. */
186 optimize_function_for_size_p (struct function *fun)
188 return (optimize_size
189 || fun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED);
192 /* Return true when current function should always be optimized for speed. */
195 optimize_function_for_speed_p (struct function *fun)
197 return !optimize_function_for_size_p (fun);
200 /* Return TRUE when BB should be optimized for size. */
203 optimize_bb_for_size_p (const_basic_block bb)
205 return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (bb);
208 /* Return TRUE when BB should be optimized for speed. */
211 optimize_bb_for_speed_p (const_basic_block bb)
213 return !optimize_bb_for_size_p (bb);
216 /* Return TRUE when BB should be optimized for size. */
219 optimize_edge_for_size_p (edge e)
221 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
224 /* Return TRUE when BB should be optimized for speed. */
227 optimize_edge_for_speed_p (edge e)
229 return !optimize_edge_for_size_p (e);
232 /* Return TRUE when BB should be optimized for size. */
235 optimize_insn_for_size_p (void)
237 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
240 /* Return TRUE when BB should be optimized for speed. */
243 optimize_insn_for_speed_p (void)
245 return !optimize_insn_for_size_p ();
248 /* Return TRUE when LOOP should be optimized for size. */
251 optimize_loop_for_size_p (struct loop *loop)
253 return optimize_bb_for_size_p (loop->header);
256 /* Return TRUE when LOOP should be optimized for speed. */
259 optimize_loop_for_speed_p (struct loop *loop)
261 return optimize_bb_for_speed_p (loop->header);
264 /* Return TRUE when LOOP nest should be optimized for speed. */
267 optimize_loop_nest_for_speed_p (struct loop *loop)
269 struct loop *l = loop;
270 if (optimize_loop_for_speed_p (loop))
273 while (l && l != loop)
275 if (optimize_loop_for_speed_p (l))
287 /* Return TRUE when LOOP nest should be optimized for size. */
290 optimize_loop_nest_for_size_p (struct loop *loop)
292 return !optimize_loop_nest_for_speed_p (loop);
295 /* Set RTL expansion for BB profile. */
298 rtl_profile_for_bb (basic_block bb)
300 crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
303 /* Set RTL expansion for edge profile. */
306 rtl_profile_for_edge (edge e)
308 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
311 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
313 default_rtl_profile (void)
315 crtl->maybe_hot_insn_p = true;
318 /* Return true if the one of outgoing edges is already predicted by
322 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
325 if (!INSN_P (BB_END (bb)))
327 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
328 if (REG_NOTE_KIND (note) == REG_BR_PRED
329 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
334 /* This map contains for a basic block the list of predictions for the
337 static struct pointer_map_t *bb_predictions;
339 /* Return true if the one of outgoing edges is already predicted by
343 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
345 struct edge_prediction *i;
346 void **preds = pointer_map_contains (bb_predictions, bb);
351 for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
352 if (i->ep_predictor == predictor)
357 /* Return true when the probability of edge is reliable.
359 The profile guessing code is good at predicting branch outcome (ie.
360 taken/not taken), that is predicted right slightly over 75% of time.
361 It is however notoriously poor on predicting the probability itself.
362 In general the profile appear a lot flatter (with probabilities closer
363 to 50%) than the reality so it is bad idea to use it to drive optimization
364 such as those disabling dynamic branch prediction for well predictable
367 There are two exceptions - edges leading to noreturn edges and edges
368 predicted by number of iterations heuristics are predicted well. This macro
369 should be able to distinguish those, but at the moment it simply check for
370 noreturn heuristic that is only one giving probability over 99% or bellow
371 1%. In future we might want to propagate reliability information across the
372 CFG if we find this information useful on multiple places. */
374 probability_reliable_p (int prob)
376 return (profile_status == PROFILE_READ
377 || (profile_status == PROFILE_GUESSED
378 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
381 /* Same predicate as above, working on edges. */
383 edge_probability_reliable_p (const_edge e)
385 return probability_reliable_p (e->probability);
388 /* Same predicate as edge_probability_reliable_p, working on notes. */
390 br_prob_note_reliable_p (const_rtx note)
392 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
393 return probability_reliable_p (INTVAL (XEXP (note, 0)));
397 predict_insn (rtx insn, enum br_predictor predictor, int probability)
399 gcc_assert (any_condjump_p (insn));
400 if (!flag_guess_branch_prob)
403 add_reg_note (insn, REG_BR_PRED,
404 gen_rtx_CONCAT (VOIDmode,
405 GEN_INT ((int) predictor),
406 GEN_INT ((int) probability)));
409 /* Predict insn by given predictor. */
412 predict_insn_def (rtx insn, enum br_predictor predictor,
413 enum prediction taken)
415 int probability = predictor_info[(int) predictor].hitrate;
418 probability = REG_BR_PROB_BASE - probability;
420 predict_insn (insn, predictor, probability);
423 /* Predict edge E with given probability if possible. */
426 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
429 last_insn = BB_END (e->src);
431 /* We can store the branch prediction information only about
432 conditional jumps. */
433 if (!any_condjump_p (last_insn))
436 /* We always store probability of branching. */
437 if (e->flags & EDGE_FALLTHRU)
438 probability = REG_BR_PROB_BASE - probability;
440 predict_insn (last_insn, predictor, probability);
443 /* Predict edge E with the given PROBABILITY. */
445 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
447 gcc_assert (profile_status != PROFILE_GUESSED);
448 if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
449 && flag_guess_branch_prob && optimize)
451 struct edge_prediction *i = XNEW (struct edge_prediction);
452 void **preds = pointer_map_insert (bb_predictions, e->src);
454 i->ep_next = (struct edge_prediction *) *preds;
456 i->ep_probability = probability;
457 i->ep_predictor = predictor;
462 /* Remove all predictions on given basic block that are attached
465 remove_predictions_associated_with_edge (edge e)
472 preds = pointer_map_contains (bb_predictions, e->src);
476 struct edge_prediction **prediction = (struct edge_prediction **) preds;
477 struct edge_prediction *next;
481 if ((*prediction)->ep_edge == e)
483 next = (*prediction)->ep_next;
488 prediction = &((*prediction)->ep_next);
493 /* Clears the list of predictions stored for BB. */
496 clear_bb_predictions (basic_block bb)
498 void **preds = pointer_map_contains (bb_predictions, bb);
499 struct edge_prediction *pred, *next;
504 for (pred = (struct edge_prediction *) *preds; pred; pred = next)
506 next = pred->ep_next;
512 /* Return true when we can store prediction on insn INSN.
513 At the moment we represent predictions only on conditional
514 jumps, not at computed jump or other complicated cases. */
516 can_predict_insn_p (const_rtx insn)
518 return (JUMP_P (insn)
519 && any_condjump_p (insn)
520 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
523 /* Predict edge E by given predictor if possible. */
526 predict_edge_def (edge e, enum br_predictor predictor,
527 enum prediction taken)
529 int probability = predictor_info[(int) predictor].hitrate;
532 probability = REG_BR_PROB_BASE - probability;
534 predict_edge (e, predictor, probability);
537 /* Invert all branch predictions or probability notes in the INSN. This needs
538 to be done each time we invert the condition used by the jump. */
541 invert_br_probabilities (rtx insn)
545 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
546 if (REG_NOTE_KIND (note) == REG_BR_PROB)
547 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
548 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
549 XEXP (XEXP (note, 0), 1)
550 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
553 /* Dump information about the branch prediction to the output file. */
556 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
557 basic_block bb, int used)
565 FOR_EACH_EDGE (e, ei, bb->succs)
566 if (! (e->flags & EDGE_FALLTHRU))
569 fprintf (file, " %s heuristics%s: %.1f%%",
570 predictor_info[predictor].name,
571 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
575 fprintf (file, " exec ");
576 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
579 fprintf (file, " hit ");
580 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
581 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
585 fprintf (file, "\n");
588 /* We can not predict the probabilities of outgoing edges of bb. Set them
589 evenly and hope for the best. */
591 set_even_probabilities (basic_block bb)
597 FOR_EACH_EDGE (e, ei, bb->succs)
598 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
600 FOR_EACH_EDGE (e, ei, bb->succs)
601 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
602 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
607 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
608 note if not already present. Remove now useless REG_BR_PRED notes. */
611 combine_predictions_for_insn (rtx insn, basic_block bb)
616 int best_probability = PROB_EVEN;
617 int best_predictor = END_PREDICTORS;
618 int combined_probability = REG_BR_PROB_BASE / 2;
620 bool first_match = false;
623 if (!can_predict_insn_p (insn))
625 set_even_probabilities (bb);
629 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
630 pnote = ®_NOTES (insn);
632 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
635 /* We implement "first match" heuristics and use probability guessed
636 by predictor with smallest index. */
637 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
638 if (REG_NOTE_KIND (note) == REG_BR_PRED)
640 int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
641 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
644 if (best_predictor > predictor)
645 best_probability = probability, best_predictor = predictor;
647 d = (combined_probability * probability
648 + (REG_BR_PROB_BASE - combined_probability)
649 * (REG_BR_PROB_BASE - probability));
651 /* Use FP math to avoid overflows of 32bit integers. */
653 /* If one probability is 0% and one 100%, avoid division by zero. */
654 combined_probability = REG_BR_PROB_BASE / 2;
656 combined_probability = (((double) combined_probability) * probability
657 * REG_BR_PROB_BASE / d + 0.5);
660 /* Decide which heuristic to use. In case we didn't match anything,
661 use no_prediction heuristic, in case we did match, use either
662 first match or Dempster-Shaffer theory depending on the flags. */
664 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
668 dump_prediction (dump_file, PRED_NO_PREDICTION,
669 combined_probability, bb, true);
672 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
674 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
679 combined_probability = best_probability;
680 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
684 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
686 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
687 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
689 dump_prediction (dump_file, predictor, probability, bb,
690 !first_match || best_predictor == predictor);
691 *pnote = XEXP (*pnote, 1);
694 pnote = &XEXP (*pnote, 1);
699 add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
701 /* Save the prediction into CFG in case we are seeing non-degenerated
703 if (!single_succ_p (bb))
705 BRANCH_EDGE (bb)->probability = combined_probability;
706 FALLTHRU_EDGE (bb)->probability
707 = REG_BR_PROB_BASE - combined_probability;
710 else if (!single_succ_p (bb))
712 int prob = INTVAL (XEXP (prob_note, 0));
714 BRANCH_EDGE (bb)->probability = prob;
715 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
718 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
721 /* Combine predictions into single probability and store them into CFG.
722 Remove now useless prediction entries. */
725 combine_predictions_for_bb (basic_block bb)
727 int best_probability = PROB_EVEN;
728 int best_predictor = END_PREDICTORS;
729 int combined_probability = REG_BR_PROB_BASE / 2;
731 bool first_match = false;
733 struct edge_prediction *pred;
735 edge e, first = NULL, second = NULL;
739 FOR_EACH_EDGE (e, ei, bb->succs)
740 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
743 if (first && !second)
749 /* When there is no successor or only one choice, prediction is easy.
751 We are lazy for now and predict only basic blocks with two outgoing
752 edges. It is possible to predict generic case too, but we have to
753 ignore first match heuristics and do more involved combining. Implement
758 set_even_probabilities (bb);
759 clear_bb_predictions (bb);
761 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
767 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
769 preds = pointer_map_contains (bb_predictions, bb);
772 /* We implement "first match" heuristics and use probability guessed
773 by predictor with smallest index. */
774 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
776 int predictor = pred->ep_predictor;
777 int probability = pred->ep_probability;
779 if (pred->ep_edge != first)
780 probability = REG_BR_PROB_BASE - probability;
783 if (best_predictor > predictor)
784 best_probability = probability, best_predictor = predictor;
786 d = (combined_probability * probability
787 + (REG_BR_PROB_BASE - combined_probability)
788 * (REG_BR_PROB_BASE - probability));
790 /* Use FP math to avoid overflows of 32bit integers. */
792 /* If one probability is 0% and one 100%, avoid division by zero. */
793 combined_probability = REG_BR_PROB_BASE / 2;
795 combined_probability = (((double) combined_probability)
797 * REG_BR_PROB_BASE / d + 0.5);
801 /* Decide which heuristic to use. In case we didn't match anything,
802 use no_prediction heuristic, in case we did match, use either
803 first match or Dempster-Shaffer theory depending on the flags. */
805 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
809 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
812 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
814 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
819 combined_probability = best_probability;
820 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
824 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
826 int predictor = pred->ep_predictor;
827 int probability = pred->ep_probability;
829 if (pred->ep_edge != EDGE_SUCC (bb, 0))
830 probability = REG_BR_PROB_BASE - probability;
831 dump_prediction (dump_file, predictor, probability, bb,
832 !first_match || best_predictor == predictor);
835 clear_bb_predictions (bb);
839 first->probability = combined_probability;
840 second->probability = REG_BR_PROB_BASE - combined_probability;
844 /* Predict edge probabilities by exploiting loop structure. */
854 /* Try to predict out blocks in a loop that are not part of a
856 FOR_EACH_LOOP (li, loop, 0)
858 basic_block bb, *bbs;
860 VEC (edge, heap) *exits;
861 struct tree_niter_desc niter_desc;
864 exits = get_loop_exit_edges (loop);
865 n_exits = VEC_length (edge, exits);
867 for (j = 0; VEC_iterate (edge, exits, j, ex); j++)
870 HOST_WIDE_INT nitercst;
871 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
873 enum br_predictor predictor;
875 if (number_of_iterations_exit (loop, ex, &niter_desc, false))
876 niter = niter_desc.niter;
877 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
878 niter = loop_niter_by_eval (loop, ex);
880 if (TREE_CODE (niter) == INTEGER_CST)
882 if (host_integerp (niter, 1)
883 && compare_tree_int (niter, max-1) == -1)
884 nitercst = tree_low_cst (niter, 1) + 1;
887 predictor = PRED_LOOP_ITERATIONS;
889 /* If we have just one exit and we can derive some information about
890 the number of iterations of the loop from the statements inside
891 the loop, use it to predict this exit. */
892 else if (n_exits == 1)
894 nitercst = estimated_loop_iterations_int (loop, false);
900 predictor = PRED_LOOP_ITERATIONS_GUESSED;
905 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
906 predict_edge (ex, predictor, probability);
908 VEC_free (edge, heap, exits);
910 bbs = get_loop_body (loop);
912 for (j = 0; j < loop->num_nodes; j++)
914 int header_found = 0;
920 /* Bypass loop heuristics on continue statement. These
921 statements construct loops via "non-loop" constructs
922 in the source language and are better to be handled
924 if (predicted_by_p (bb, PRED_CONTINUE))
927 /* Loop branch heuristics - predict an edge back to a
928 loop's head as taken. */
929 if (bb == loop->latch)
931 e = find_edge (loop->latch, loop->header);
935 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
939 /* Loop exit heuristics - predict an edge exiting the loop if the
940 conditional has no loop header successors as not taken. */
942 /* If we already used more reliable loop exit predictors, do not
943 bother with PRED_LOOP_EXIT. */
944 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
945 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
947 /* For loop with many exits we don't want to predict all exits
948 with the pretty large probability, because if all exits are
949 considered in row, the loop would be predicted to iterate
950 almost never. The code to divide probability by number of
951 exits is very rough. It should compute the number of exits
952 taken in each patch through function (not the overall number
953 of exits that might be a lot higher for loops with wide switch
954 statements in them) and compute n-th square root.
956 We limit the minimal probability by 2% to avoid
957 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
958 as this was causing regression in perl benchmark containing such
961 int probability = ((REG_BR_PROB_BASE
962 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
964 if (probability < HITRATE (2))
965 probability = HITRATE (2);
966 FOR_EACH_EDGE (e, ei, bb->succs)
967 if (e->dest->index < NUM_FIXED_BLOCKS
968 || !flow_bb_inside_loop_p (loop, e->dest))
969 predict_edge (e, PRED_LOOP_EXIT, probability);
973 /* Free basic blocks from get_loop_body. */
980 /* Attempt to predict probabilities of BB outgoing edges using local
983 bb_estimate_probability_locally (basic_block bb)
985 rtx last_insn = BB_END (bb);
988 if (! can_predict_insn_p (last_insn))
990 cond = get_condition (last_insn, NULL, false, false);
994 /* Try "pointer heuristic."
995 A comparison ptr == 0 is predicted as false.
996 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
997 if (COMPARISON_P (cond)
998 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
999 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1001 if (GET_CODE (cond) == EQ)
1002 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1003 else if (GET_CODE (cond) == NE)
1004 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1008 /* Try "opcode heuristic."
1009 EQ tests are usually false and NE tests are usually true. Also,
1010 most quantities are positive, so we can make the appropriate guesses
1011 about signed comparisons against zero. */
1012 switch (GET_CODE (cond))
1015 /* Unconditional branch. */
1016 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1017 cond == const0_rtx ? NOT_TAKEN : TAKEN);
1022 /* Floating point comparisons appears to behave in a very
1023 unpredictable way because of special role of = tests in
1025 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1027 /* Comparisons with 0 are often used for booleans and there is
1028 nothing useful to predict about them. */
1029 else if (XEXP (cond, 1) == const0_rtx
1030 || XEXP (cond, 0) == const0_rtx)
1033 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1038 /* Floating point comparisons appears to behave in a very
1039 unpredictable way because of special role of = tests in
1041 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1043 /* Comparisons with 0 are often used for booleans and there is
1044 nothing useful to predict about them. */
1045 else if (XEXP (cond, 1) == const0_rtx
1046 || XEXP (cond, 0) == const0_rtx)
1049 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1053 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1057 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1062 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1063 || XEXP (cond, 1) == constm1_rtx)
1064 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1069 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1070 || XEXP (cond, 1) == constm1_rtx)
1071 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1079 /* Set edge->probability for each successor edge of BB. */
1081 guess_outgoing_edge_probabilities (basic_block bb)
1083 bb_estimate_probability_locally (bb);
1084 combine_predictions_for_insn (BB_END (bb), bb);
1087 static tree expr_expected_value (tree, bitmap);
1089 /* Helper function for expr_expected_value. */
1092 expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited)
1096 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1098 if (TREE_CONSTANT (op0))
1101 if (code != SSA_NAME)
1104 def = SSA_NAME_DEF_STMT (op0);
1106 /* If we were already here, break the infinite cycle. */
1107 if (bitmap_bit_p (visited, SSA_NAME_VERSION (op0)))
1109 bitmap_set_bit (visited, SSA_NAME_VERSION (op0));
1111 if (gimple_code (def) == GIMPLE_PHI)
1113 /* All the arguments of the PHI node must have the same constant
1115 int i, n = gimple_phi_num_args (def);
1116 tree val = NULL, new_val;
1118 for (i = 0; i < n; i++)
1120 tree arg = PHI_ARG_DEF (def, i);
1122 /* If this PHI has itself as an argument, we cannot
1123 determine the string length of this argument. However,
1124 if we can find an expected constant value for the other
1125 PHI args then we can still be sure that this is
1126 likely a constant. So be optimistic and just
1127 continue with the next argument. */
1128 if (arg == PHI_RESULT (def))
1131 new_val = expr_expected_value (arg, visited);
1136 else if (!operand_equal_p (val, new_val, false))
1141 if (is_gimple_assign (def))
1143 if (gimple_assign_lhs (def) != op0)
1146 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1147 gimple_assign_rhs1 (def),
1148 gimple_assign_rhs_code (def),
1149 gimple_assign_rhs2 (def),
1153 if (is_gimple_call (def))
1155 tree decl = gimple_call_fndecl (def);
1158 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
1159 && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
1163 if (gimple_call_num_args (def) != 2)
1165 val = gimple_call_arg (def, 0);
1166 if (TREE_CONSTANT (val))
1168 return gimple_call_arg (def, 1);
1175 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1178 op0 = expr_expected_value (op0, visited);
1181 op1 = expr_expected_value (op1, visited);
1184 res = fold_build2 (code, type, op0, op1);
1185 if (TREE_CONSTANT (res))
1189 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1192 op0 = expr_expected_value (op0, visited);
1195 res = fold_build1 (code, type, op0);
1196 if (TREE_CONSTANT (res))
1203 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1204 The function is used by builtin_expect branch predictor so the evidence
1205 must come from this construct and additional possible constant folding.
1207 We may want to implement more involved value guess (such as value range
1208 propagation based prediction), but such tricks shall go to new
1212 expr_expected_value (tree expr, bitmap visited)
1214 enum tree_code code;
1217 if (TREE_CONSTANT (expr))
1220 extract_ops_from_tree (expr, &code, &op0, &op1);
1221 return expr_expected_value_1 (TREE_TYPE (expr),
1222 op0, code, op1, visited);
1226 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1227 we no longer need. */
1229 strip_predict_hints (void)
1237 gimple_stmt_iterator bi;
1238 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
1240 gimple stmt = gsi_stmt (bi);
1242 if (gimple_code (stmt) == GIMPLE_PREDICT)
1244 gsi_remove (&bi, true);
1247 else if (gimple_code (stmt) == GIMPLE_CALL)
1249 tree fndecl = gimple_call_fndecl (stmt);
1252 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1253 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1254 && gimple_call_num_args (stmt) == 2)
1256 var = gimple_call_lhs (stmt);
1257 ass_stmt = gimple_build_assign (var, gimple_call_arg (stmt, 0));
1259 gsi_replace (&bi, ass_stmt, true);
1268 /* Predict using opcode of the last statement in basic block. */
1270 tree_predict_by_opcode (basic_block bb)
1272 gimple stmt = last_stmt (bb);
1281 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1283 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1284 if (then_edge->flags & EDGE_TRUE_VALUE)
1286 op0 = gimple_cond_lhs (stmt);
1287 op1 = gimple_cond_rhs (stmt);
1288 cmp = gimple_cond_code (stmt);
1289 type = TREE_TYPE (op0);
1290 visited = BITMAP_ALLOC (NULL);
1291 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
1292 BITMAP_FREE (visited);
1295 if (integer_zerop (val))
1296 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1298 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1301 /* Try "pointer heuristic."
1302 A comparison ptr == 0 is predicted as false.
1303 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1304 if (POINTER_TYPE_P (type))
1307 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1308 else if (cmp == NE_EXPR)
1309 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1313 /* Try "opcode heuristic."
1314 EQ tests are usually false and NE tests are usually true. Also,
1315 most quantities are positive, so we can make the appropriate guesses
1316 about signed comparisons against zero. */
1321 /* Floating point comparisons appears to behave in a very
1322 unpredictable way because of special role of = tests in
1324 if (FLOAT_TYPE_P (type))
1326 /* Comparisons with 0 are often used for booleans and there is
1327 nothing useful to predict about them. */
1328 else if (integer_zerop (op0) || integer_zerop (op1))
1331 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1336 /* Floating point comparisons appears to behave in a very
1337 unpredictable way because of special role of = tests in
1339 if (FLOAT_TYPE_P (type))
1341 /* Comparisons with 0 are often used for booleans and there is
1342 nothing useful to predict about them. */
1343 else if (integer_zerop (op0)
1344 || integer_zerop (op1))
1347 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1351 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1354 case UNORDERED_EXPR:
1355 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1360 if (integer_zerop (op1)
1361 || integer_onep (op1)
1362 || integer_all_onesp (op1)
1365 || real_minus_onep (op1))
1366 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1371 if (integer_zerop (op1)
1372 || integer_onep (op1)
1373 || integer_all_onesp (op1)
1376 || real_minus_onep (op1))
1377 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1385 /* Try to guess whether the value of return means error code. */
1387 static enum br_predictor
1388 return_prediction (tree val, enum prediction *prediction)
1392 return PRED_NO_PREDICTION;
1393 /* Different heuristics for pointers and scalars. */
1394 if (POINTER_TYPE_P (TREE_TYPE (val)))
1396 /* NULL is usually not returned. */
1397 if (integer_zerop (val))
1399 *prediction = NOT_TAKEN;
1400 return PRED_NULL_RETURN;
1403 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1405 /* Negative return values are often used to indicate
1407 if (TREE_CODE (val) == INTEGER_CST
1408 && tree_int_cst_sgn (val) < 0)
1410 *prediction = NOT_TAKEN;
1411 return PRED_NEGATIVE_RETURN;
1413 /* Constant return values seems to be commonly taken.
1414 Zero/one often represent booleans so exclude them from the
1416 if (TREE_CONSTANT (val)
1417 && (!integer_zerop (val) && !integer_onep (val)))
1419 *prediction = TAKEN;
1420 return PRED_CONST_RETURN;
1423 return PRED_NO_PREDICTION;
1426 /* Find the basic block with return expression and look up for possible
1427 return value trying to apply RETURN_PREDICTION heuristics. */
1429 apply_return_prediction (void)
1431 gimple return_stmt = NULL;
1435 int phi_num_args, i;
1436 enum br_predictor pred;
1437 enum prediction direction;
1440 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1442 return_stmt = last_stmt (e->src);
1444 && gimple_code (return_stmt) == GIMPLE_RETURN)
1449 return_val = gimple_return_retval (return_stmt);
1452 if (TREE_CODE (return_val) != SSA_NAME
1453 || !SSA_NAME_DEF_STMT (return_val)
1454 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
1456 phi = SSA_NAME_DEF_STMT (return_val);
1457 phi_num_args = gimple_phi_num_args (phi);
1458 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1460 /* Avoid the degenerate case where all return values form the function
1461 belongs to same category (ie they are all positive constants)
1462 so we can hardly say something about them. */
1463 for (i = 1; i < phi_num_args; i++)
1464 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1466 if (i != phi_num_args)
1467 for (i = 0; i < phi_num_args; i++)
1469 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1470 if (pred != PRED_NO_PREDICTION)
1471 predict_paths_leading_to (gimple_phi_arg_edge (phi, i)->src, pred,
1476 /* Look for basic block that contains unlikely to happen events
1477 (such as noreturn calls) and mark all paths leading to execution
1478 of this basic blocks as unlikely. */
1481 tree_bb_level_predictions (void)
1485 apply_return_prediction ();
1489 gimple_stmt_iterator gsi;
1491 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1493 gimple stmt = gsi_stmt (gsi);
1496 if (is_gimple_call (stmt))
1498 if (gimple_call_flags (stmt) & ECF_NORETURN)
1499 predict_paths_leading_to (bb, PRED_NORETURN,
1501 decl = gimple_call_fndecl (stmt);
1503 && lookup_attribute ("cold",
1504 DECL_ATTRIBUTES (decl)))
1505 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
1508 else if (gimple_code (stmt) == GIMPLE_PREDICT)
1510 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
1511 gimple_predict_outcome (stmt));
1512 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1513 hints to callers. */
1519 #ifdef ENABLE_CHECKING
1521 /* Callback for pointer_map_traverse, asserts that the pointer map is
1525 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1526 void *data ATTRIBUTE_UNUSED)
1528 gcc_assert (!*value);
1533 /* Predict branch probabilities and estimate profile of the tree CFG. */
1535 tree_estimate_probability (void)
1539 loop_optimizer_init (0);
1540 if (dump_file && (dump_flags & TDF_DETAILS))
1541 flow_loops_dump (dump_file, NULL, 0);
1543 add_noreturn_fake_exit_edges ();
1544 connect_infinite_loops_to_exit ();
1545 /* We use loop_niter_by_eval, which requires that the loops have
1547 create_preheaders (CP_SIMPLE_PREHEADERS);
1548 calculate_dominance_info (CDI_POST_DOMINATORS);
1550 bb_predictions = pointer_map_create ();
1551 tree_bb_level_predictions ();
1553 mark_irreducible_loops ();
1554 record_loop_exits ();
1555 if (number_of_loops () > 1)
1563 FOR_EACH_EDGE (e, ei, bb->succs)
1565 /* Predict early returns to be probable, as we've already taken
1566 care for error returns and other cases are often used for
1567 fast paths through function.
1569 Since we've already removed the return statements, we are
1570 looking for CFG like:
1580 if (e->dest != bb->next_bb
1581 && e->dest != EXIT_BLOCK_PTR
1582 && single_succ_p (e->dest)
1583 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1584 && gimple_code (last_stmt (e->dest)) == GIMPLE_RETURN)
1589 if (single_succ_p (bb))
1591 FOR_EACH_EDGE (e1, ei1, bb->preds)
1592 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1593 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1594 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1595 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1598 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1599 && !predicted_by_p (e->src, PRED_CONST_RETURN)
1600 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1601 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1604 /* Look for block we are guarding (ie we dominate it,
1605 but it doesn't postdominate us). */
1606 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1607 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1608 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1610 gimple_stmt_iterator bi;
1612 /* The call heuristic claims that a guarded function call
1613 is improbable. This is because such calls are often used
1614 to signal exceptional situations such as printing error
1616 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
1619 gimple stmt = gsi_stmt (bi);
1620 if (is_gimple_call (stmt)
1621 /* Constant and pure calls are hardly used to signalize
1622 something exceptional. */
1623 && gimple_has_side_effects (stmt))
1625 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1631 tree_predict_by_opcode (bb);
1634 combine_predictions_for_bb (bb);
1636 #ifdef ENABLE_CHECKING
1637 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1639 pointer_map_destroy (bb_predictions);
1640 bb_predictions = NULL;
1642 estimate_bb_frequencies ();
1643 free_dominance_info (CDI_POST_DOMINATORS);
1644 remove_fake_exit_edges ();
1645 loop_optimizer_finalize ();
1646 if (dump_file && (dump_flags & TDF_DETAILS))
1647 gimple_dump_cfg (dump_file, dump_flags);
1648 if (profile_status == PROFILE_ABSENT)
1649 profile_status = PROFILE_GUESSED;
1653 /* Predict edges to successors of CUR whose sources are not postdominated by
1654 BB by PRED and recurse to all postdominators. */
1657 predict_paths_for_bb (basic_block cur, basic_block bb,
1658 enum br_predictor pred,
1659 enum prediction taken)
1665 /* We are looking for all edges forming edge cut induced by
1666 set of all blocks postdominated by BB. */
1667 FOR_EACH_EDGE (e, ei, cur->preds)
1668 if (e->src->index >= NUM_FIXED_BLOCKS
1669 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
1671 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
1672 predict_edge_def (e, pred, taken);
1674 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
1676 son = next_dom_son (CDI_POST_DOMINATORS, son))
1677 predict_paths_for_bb (son, bb, pred, taken);
1680 /* Sets branch probabilities according to PREDiction and
1684 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
1685 enum prediction taken)
1687 predict_paths_for_bb (bb, bb, pred, taken);
1690 /* This is used to carry information about basic blocks. It is
1691 attached to the AUX field of the standard CFG block. */
1693 typedef struct block_info_def
1695 /* Estimated frequency of execution of basic_block. */
1698 /* To keep queue of basic blocks to process. */
1701 /* Number of predecessors we need to visit first. */
1705 /* Similar information for edges. */
1706 typedef struct edge_info_def
1708 /* In case edge is a loopback edge, the probability edge will be reached
1709 in case header is. Estimated number of iterations of the loop can be
1710 then computed as 1 / (1 - back_edge_prob). */
1711 sreal back_edge_prob;
1712 /* True if the edge is a loopback edge in the natural loop. */
1713 unsigned int back_edge:1;
1716 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1717 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1719 /* Helper function for estimate_bb_frequencies.
1720 Propagate the frequencies in blocks marked in
1721 TOVISIT, starting in HEAD. */
1724 propagate_freq (basic_block head, bitmap tovisit)
1733 /* For each basic block we need to visit count number of his predecessors
1734 we need to visit first. */
1735 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1740 /* The outermost "loop" includes the exit block, which we can not
1741 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1742 directly. Do the same for the entry block. */
1743 bb = BASIC_BLOCK (i);
1745 FOR_EACH_EDGE (e, ei, bb->preds)
1747 bool visit = bitmap_bit_p (tovisit, e->src->index);
1749 if (visit && !(e->flags & EDGE_DFS_BACK))
1751 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1753 "Irreducible region hit, ignoring edge to %i->%i\n",
1754 e->src->index, bb->index);
1756 BLOCK_INFO (bb)->npredecessors = count;
1759 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1761 for (bb = head; bb; bb = nextbb)
1764 sreal cyclic_probability, frequency;
1766 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1767 memcpy (&frequency, &real_zero, sizeof (real_zero));
1769 nextbb = BLOCK_INFO (bb)->next;
1770 BLOCK_INFO (bb)->next = NULL;
1772 /* Compute frequency of basic block. */
1775 #ifdef ENABLE_CHECKING
1776 FOR_EACH_EDGE (e, ei, bb->preds)
1777 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1778 || (e->flags & EDGE_DFS_BACK));
1781 FOR_EACH_EDGE (e, ei, bb->preds)
1782 if (EDGE_INFO (e)->back_edge)
1784 sreal_add (&cyclic_probability, &cyclic_probability,
1785 &EDGE_INFO (e)->back_edge_prob);
1787 else if (!(e->flags & EDGE_DFS_BACK))
1791 /* frequency += (e->probability
1792 * BLOCK_INFO (e->src)->frequency /
1793 REG_BR_PROB_BASE); */
1795 sreal_init (&tmp, e->probability, 0);
1796 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1797 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1798 sreal_add (&frequency, &frequency, &tmp);
1801 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1803 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1804 sizeof (frequency));
1808 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
1810 memcpy (&cyclic_probability, &real_almost_one,
1811 sizeof (real_almost_one));
1814 /* BLOCK_INFO (bb)->frequency = frequency
1815 / (1 - cyclic_probability) */
1817 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
1818 sreal_div (&BLOCK_INFO (bb)->frequency,
1819 &frequency, &cyclic_probability);
1823 bitmap_clear_bit (tovisit, bb->index);
1825 e = find_edge (bb, head);
1830 /* EDGE_INFO (e)->back_edge_prob
1831 = ((e->probability * BLOCK_INFO (bb)->frequency)
1832 / REG_BR_PROB_BASE); */
1834 sreal_init (&tmp, e->probability, 0);
1835 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1836 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1837 &tmp, &real_inv_br_prob_base);
1840 /* Propagate to successor blocks. */
1841 FOR_EACH_EDGE (e, ei, bb->succs)
1842 if (!(e->flags & EDGE_DFS_BACK)
1843 && BLOCK_INFO (e->dest)->npredecessors)
1845 BLOCK_INFO (e->dest)->npredecessors--;
1846 if (!BLOCK_INFO (e->dest)->npredecessors)
1851 BLOCK_INFO (last)->next = e->dest;
1859 /* Estimate probabilities of loopback edges in loops at same nest level. */
1862 estimate_loops_at_level (struct loop *first_loop)
1866 for (loop = first_loop; loop; loop = loop->next)
1871 bitmap tovisit = BITMAP_ALLOC (NULL);
1873 estimate_loops_at_level (loop->inner);
1875 /* Find current loop back edge and mark it. */
1876 e = loop_latch_edge (loop);
1877 EDGE_INFO (e)->back_edge = 1;
1879 bbs = get_loop_body (loop);
1880 for (i = 0; i < loop->num_nodes; i++)
1881 bitmap_set_bit (tovisit, bbs[i]->index);
1883 propagate_freq (loop->header, tovisit);
1884 BITMAP_FREE (tovisit);
1888 /* Propagates frequencies through structure of loops. */
1891 estimate_loops (void)
1893 bitmap tovisit = BITMAP_ALLOC (NULL);
1896 /* Start by estimating the frequencies in the loops. */
1897 if (number_of_loops () > 1)
1898 estimate_loops_at_level (current_loops->tree_root->inner);
1900 /* Now propagate the frequencies through all the blocks. */
1903 bitmap_set_bit (tovisit, bb->index);
1905 propagate_freq (ENTRY_BLOCK_PTR, tovisit);
1906 BITMAP_FREE (tovisit);
1909 /* Convert counts measured by profile driven feedback to frequencies.
1910 Return nonzero iff there was any nonzero execution count. */
1913 counts_to_freqs (void)
1915 gcov_type count_max, true_count_max = 0;
1919 true_count_max = MAX (bb->count, true_count_max);
1921 count_max = MAX (true_count_max, 1);
1922 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1923 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1925 return true_count_max;
1928 /* Return true if function is likely to be expensive, so there is no point to
1929 optimize performance of prologue, epilogue or do inlining at the expense
1930 of code size growth. THRESHOLD is the limit of number of instructions
1931 function can execute at average to be still considered not expensive. */
1934 expensive_function_p (int threshold)
1936 unsigned int sum = 0;
1940 /* We can not compute accurately for large thresholds due to scaled
1942 gcc_assert (threshold <= BB_FREQ_MAX);
1944 /* Frequencies are out of range. This either means that function contains
1945 internal loop executing more than BB_FREQ_MAX times or profile feedback
1946 is available and function has not been executed at all. */
1947 if (ENTRY_BLOCK_PTR->frequency == 0)
1950 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1951 limit = ENTRY_BLOCK_PTR->frequency * threshold;
1956 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1957 insn = NEXT_INSN (insn))
1958 if (active_insn_p (insn))
1960 sum += bb->frequency;
1969 /* Estimate basic blocks frequency by given branch probabilities. */
1972 estimate_bb_frequencies (void)
1977 if (!flag_branch_probabilities || !counts_to_freqs ())
1979 static int real_values_initialized = 0;
1981 if (!real_values_initialized)
1983 real_values_initialized = 1;
1984 sreal_init (&real_zero, 0, 0);
1985 sreal_init (&real_one, 1, 0);
1986 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
1987 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
1988 sreal_init (&real_one_half, 1, -1);
1989 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
1990 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
1993 mark_dfs_back_edges ();
1995 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
1997 /* Set up block info for each basic block. */
1998 alloc_aux_for_blocks (sizeof (struct block_info_def));
1999 alloc_aux_for_edges (sizeof (struct edge_info_def));
2000 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2005 FOR_EACH_EDGE (e, ei, bb->succs)
2007 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
2008 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2009 &EDGE_INFO (e)->back_edge_prob,
2010 &real_inv_br_prob_base);
2014 /* First compute probabilities locally for each loop from innermost
2015 to outermost to examine probabilities for back edges. */
2018 memcpy (&freq_max, &real_zero, sizeof (real_zero));
2020 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
2021 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
2023 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
2024 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2028 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
2029 sreal_add (&tmp, &tmp, &real_one_half);
2030 bb->frequency = sreal_to_int (&tmp);
2033 free_aux_for_blocks ();
2034 free_aux_for_edges ();
2036 compute_function_frequency ();
2037 if (flag_reorder_functions)
2038 choose_function_section ();
2041 /* Decide whether function is hot, cold or unlikely executed. */
2043 compute_function_frequency (void)
2047 if (!profile_info || !flag_branch_probabilities)
2049 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2051 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
2052 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2054 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
2057 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
2060 if (maybe_hot_bb_p (bb))
2062 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
2065 if (!probably_never_executed_bb_p (bb))
2066 cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
2070 /* Choose appropriate section for the function. */
2072 choose_function_section (void)
2074 if (DECL_SECTION_NAME (current_function_decl)
2075 || !targetm.have_named_sections
2076 /* Theoretically we can split the gnu.linkonce text section too,
2077 but this requires more work as the frequency needs to match
2078 for all generated objects so we need to merge the frequency
2079 of all instances. For now just never set frequency for these. */
2080 || DECL_ONE_ONLY (current_function_decl))
2083 /* If we are doing the partitioning optimization, let the optimization
2084 choose the correct section into which to put things. */
2086 if (flag_reorder_blocks_and_partition)
2089 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
2090 DECL_SECTION_NAME (current_function_decl) =
2091 build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
2092 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
2093 DECL_SECTION_NAME (current_function_decl) =
2094 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
2095 UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
2099 gate_estimate_probability (void)
2101 return flag_guess_branch_prob;
2104 /* Build PREDICT_EXPR. */
2106 build_predict_expr (enum br_predictor predictor, enum prediction taken)
2108 tree t = build1 (PREDICT_EXPR, void_type_node,
2109 build_int_cst (NULL, predictor));
2110 PREDICT_EXPR_OUTCOME (t) = taken;
2115 predictor_name (enum br_predictor predictor)
2117 return predictor_info[predictor].name;
2120 struct gimple_opt_pass pass_profile =
2124 "profile", /* name */
2125 gate_estimate_probability, /* gate */
2126 tree_estimate_probability, /* execute */
2129 0, /* static_pass_number */
2130 TV_BRANCH_PROB, /* tv_id */
2131 PROP_cfg, /* properties_required */
2132 0, /* properties_provided */
2133 0, /* properties_destroyed */
2134 0, /* todo_flags_start */
2135 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2139 struct gimple_opt_pass pass_strip_predict_hints =
2145 strip_predict_hints, /* execute */
2148 0, /* static_pass_number */
2149 TV_BRANCH_PROB, /* tv_id */
2150 PROP_cfg, /* properties_required */
2151 0, /* properties_provided */
2152 0, /* properties_destroyed */
2153 0, /* todo_flags_start */
2154 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */