1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 [1] "Branch Prediction for Free"
24 Ball and Larus; PLDI '93.
25 [2] "Static Branch Frequency and Program Profile Analysis"
26 Wu and Larus; MICRO-27.
27 [3] "Corpus-based Static Branch Prediction"
28 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
33 #include "coretypes.h"
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
46 #include "diagnostic-core.h"
55 #include "tree-flow.h"
57 #include "tree-dump.h"
58 #include "tree-pass.h"
60 #include "tree-scalar-evolution.h"
62 #include "pointer-set.h"
64 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
65 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
66 static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
67 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
69 /* Random guesstimation given names.
70 PROV_VERY_UNLIKELY should be small enough so basic block predicted
71 by it gets bellow HOT_BB_FREQUENCY_FRANCTION. */
72 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 2000 - 1)
73 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
74 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
75 #define PROB_ALWAYS (REG_BR_PROB_BASE)
77 static void combine_predictions_for_insn (rtx, basic_block);
78 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
79 static void predict_paths_leading_to (basic_block, enum br_predictor, enum prediction);
80 static 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. */
113 maybe_hot_frequency_p (int freq)
115 struct cgraph_node *node = cgraph_node (current_function_decl);
116 if (!profile_info || !flag_branch_probabilities)
118 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
120 if (node->frequency == NODE_FREQUENCY_HOT)
123 if (profile_status == PROFILE_ABSENT)
125 if (node->frequency == NODE_FREQUENCY_EXECUTED_ONCE
126 && freq <= (ENTRY_BLOCK_PTR->frequency * 2 / 3))
128 if (freq < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
133 /* Return TRUE if frequency FREQ is considered to be hot. */
136 maybe_hot_count_p (gcov_type count)
138 if (profile_status != PROFILE_READ)
140 /* Code executed at most once is not hot. */
141 if (profile_info->runs >= count)
144 > profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION));
147 /* Return true in case BB can be CPU intensive and should be optimized
148 for maximal performance. */
151 maybe_hot_bb_p (const_basic_block bb)
153 if (profile_status == PROFILE_READ)
154 return maybe_hot_count_p (bb->count);
155 return maybe_hot_frequency_p (bb->frequency);
158 /* Return true if the call can be hot. */
161 cgraph_maybe_hot_edge_p (struct cgraph_edge *edge)
163 if (profile_info && flag_branch_probabilities
165 <= profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
167 if (edge->caller->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED
168 || edge->callee->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
170 if (edge->caller->frequency > NODE_FREQUENCY_UNLIKELY_EXECUTED
171 && edge->callee->frequency <= NODE_FREQUENCY_EXECUTED_ONCE)
175 if (edge->caller->frequency == NODE_FREQUENCY_HOT)
177 if (edge->caller->frequency == NODE_FREQUENCY_EXECUTED_ONCE
178 && edge->frequency < CGRAPH_FREQ_BASE * 3 / 2)
180 if (flag_guess_branch_prob
181 && edge->frequency <= (CGRAPH_FREQ_BASE
182 / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION)))
187 /* Return true in case BB can be CPU intensive and should be optimized
188 for maximal performance. */
191 maybe_hot_edge_p (edge e)
193 if (profile_status == PROFILE_READ)
194 return maybe_hot_count_p (e->count);
195 return maybe_hot_frequency_p (EDGE_FREQUENCY (e));
198 /* Return true in case BB is probably never executed. */
200 probably_never_executed_bb_p (const_basic_block bb)
202 if (profile_info && flag_branch_probabilities)
203 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
204 if ((!profile_info || !flag_branch_probabilities)
205 && cgraph_node (current_function_decl)->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
210 /* Return true when current function should always be optimized for size. */
213 optimize_function_for_size_p (struct function *fun)
215 return (optimize_size
217 && (cgraph_node (fun->decl)->frequency
218 == NODE_FREQUENCY_UNLIKELY_EXECUTED)));
221 /* Return true when current function should always be optimized for speed. */
224 optimize_function_for_speed_p (struct function *fun)
226 return !optimize_function_for_size_p (fun);
229 /* Return TRUE when BB should be optimized for size. */
232 optimize_bb_for_size_p (const_basic_block bb)
234 return optimize_function_for_size_p (cfun) || !maybe_hot_bb_p (bb);
237 /* Return TRUE when BB should be optimized for speed. */
240 optimize_bb_for_speed_p (const_basic_block bb)
242 return !optimize_bb_for_size_p (bb);
245 /* Return TRUE when BB should be optimized for size. */
248 optimize_edge_for_size_p (edge e)
250 return optimize_function_for_size_p (cfun) || !maybe_hot_edge_p (e);
253 /* Return TRUE when BB should be optimized for speed. */
256 optimize_edge_for_speed_p (edge e)
258 return !optimize_edge_for_size_p (e);
261 /* Return TRUE when BB should be optimized for size. */
264 optimize_insn_for_size_p (void)
266 return optimize_function_for_size_p (cfun) || !crtl->maybe_hot_insn_p;
269 /* Return TRUE when BB should be optimized for speed. */
272 optimize_insn_for_speed_p (void)
274 return !optimize_insn_for_size_p ();
277 /* Return TRUE when LOOP should be optimized for size. */
280 optimize_loop_for_size_p (struct loop *loop)
282 return optimize_bb_for_size_p (loop->header);
285 /* Return TRUE when LOOP should be optimized for speed. */
288 optimize_loop_for_speed_p (struct loop *loop)
290 return optimize_bb_for_speed_p (loop->header);
293 /* Return TRUE when LOOP nest should be optimized for speed. */
296 optimize_loop_nest_for_speed_p (struct loop *loop)
298 struct loop *l = loop;
299 if (optimize_loop_for_speed_p (loop))
302 while (l && l != loop)
304 if (optimize_loop_for_speed_p (l))
312 while (l != loop && !l->next)
321 /* Return TRUE when LOOP nest should be optimized for size. */
324 optimize_loop_nest_for_size_p (struct loop *loop)
326 return !optimize_loop_nest_for_speed_p (loop);
329 /* Return true when edge E is likely to be well predictable by branch
333 predictable_edge_p (edge e)
335 if (profile_status == PROFILE_ABSENT)
338 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100)
339 || (REG_BR_PROB_BASE - e->probability
340 <= PARAM_VALUE (PARAM_PREDICTABLE_BRANCH_OUTCOME) * REG_BR_PROB_BASE / 100))
346 /* Set RTL expansion for BB profile. */
349 rtl_profile_for_bb (basic_block bb)
351 crtl->maybe_hot_insn_p = maybe_hot_bb_p (bb);
354 /* Set RTL expansion for edge profile. */
357 rtl_profile_for_edge (edge e)
359 crtl->maybe_hot_insn_p = maybe_hot_edge_p (e);
362 /* Set RTL expansion to default mode (i.e. when profile info is not known). */
364 default_rtl_profile (void)
366 crtl->maybe_hot_insn_p = true;
369 /* Return true if the one of outgoing edges is already predicted by
373 rtl_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
376 if (!INSN_P (BB_END (bb)))
378 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
379 if (REG_NOTE_KIND (note) == REG_BR_PRED
380 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
385 /* This map contains for a basic block the list of predictions for the
388 static struct pointer_map_t *bb_predictions;
390 /* Structure representing predictions in tree level. */
392 struct edge_prediction {
393 struct edge_prediction *ep_next;
395 enum br_predictor ep_predictor;
399 /* Return true if the one of outgoing edges is already predicted by
403 gimple_predicted_by_p (const_basic_block bb, enum br_predictor predictor)
405 struct edge_prediction *i;
406 void **preds = pointer_map_contains (bb_predictions, bb);
411 for (i = (struct edge_prediction *) *preds; i; i = i->ep_next)
412 if (i->ep_predictor == predictor)
417 /* Return true when the probability of edge is reliable.
419 The profile guessing code is good at predicting branch outcome (ie.
420 taken/not taken), that is predicted right slightly over 75% of time.
421 It is however notoriously poor on predicting the probability itself.
422 In general the profile appear a lot flatter (with probabilities closer
423 to 50%) than the reality so it is bad idea to use it to drive optimization
424 such as those disabling dynamic branch prediction for well predictable
427 There are two exceptions - edges leading to noreturn edges and edges
428 predicted by number of iterations heuristics are predicted well. This macro
429 should be able to distinguish those, but at the moment it simply check for
430 noreturn heuristic that is only one giving probability over 99% or bellow
431 1%. In future we might want to propagate reliability information across the
432 CFG if we find this information useful on multiple places. */
434 probability_reliable_p (int prob)
436 return (profile_status == PROFILE_READ
437 || (profile_status == PROFILE_GUESSED
438 && (prob <= HITRATE (1) || prob >= HITRATE (99))));
441 /* Same predicate as above, working on edges. */
443 edge_probability_reliable_p (const_edge e)
445 return probability_reliable_p (e->probability);
448 /* Same predicate as edge_probability_reliable_p, working on notes. */
450 br_prob_note_reliable_p (const_rtx note)
452 gcc_assert (REG_NOTE_KIND (note) == REG_BR_PROB);
453 return probability_reliable_p (INTVAL (XEXP (note, 0)));
457 predict_insn (rtx insn, enum br_predictor predictor, int probability)
459 gcc_assert (any_condjump_p (insn));
460 if (!flag_guess_branch_prob)
463 add_reg_note (insn, REG_BR_PRED,
464 gen_rtx_CONCAT (VOIDmode,
465 GEN_INT ((int) predictor),
466 GEN_INT ((int) probability)));
469 /* Predict insn by given predictor. */
472 predict_insn_def (rtx insn, enum br_predictor predictor,
473 enum prediction taken)
475 int probability = predictor_info[(int) predictor].hitrate;
478 probability = REG_BR_PROB_BASE - probability;
480 predict_insn (insn, predictor, probability);
483 /* Predict edge E with given probability if possible. */
486 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
489 last_insn = BB_END (e->src);
491 /* We can store the branch prediction information only about
492 conditional jumps. */
493 if (!any_condjump_p (last_insn))
496 /* We always store probability of branching. */
497 if (e->flags & EDGE_FALLTHRU)
498 probability = REG_BR_PROB_BASE - probability;
500 predict_insn (last_insn, predictor, probability);
503 /* Predict edge E with the given PROBABILITY. */
505 gimple_predict_edge (edge e, enum br_predictor predictor, int probability)
507 gcc_assert (profile_status != PROFILE_GUESSED);
508 if ((e->src != ENTRY_BLOCK_PTR && EDGE_COUNT (e->src->succs) > 1)
509 && flag_guess_branch_prob && optimize)
511 struct edge_prediction *i = XNEW (struct edge_prediction);
512 void **preds = pointer_map_insert (bb_predictions, e->src);
514 i->ep_next = (struct edge_prediction *) *preds;
516 i->ep_probability = probability;
517 i->ep_predictor = predictor;
522 /* Remove all predictions on given basic block that are attached
525 remove_predictions_associated_with_edge (edge e)
532 preds = pointer_map_contains (bb_predictions, e->src);
536 struct edge_prediction **prediction = (struct edge_prediction **) preds;
537 struct edge_prediction *next;
541 if ((*prediction)->ep_edge == e)
543 next = (*prediction)->ep_next;
548 prediction = &((*prediction)->ep_next);
553 /* Clears the list of predictions stored for BB. */
556 clear_bb_predictions (basic_block bb)
558 void **preds = pointer_map_contains (bb_predictions, bb);
559 struct edge_prediction *pred, *next;
564 for (pred = (struct edge_prediction *) *preds; pred; pred = next)
566 next = pred->ep_next;
572 /* Return true when we can store prediction on insn INSN.
573 At the moment we represent predictions only on conditional
574 jumps, not at computed jump or other complicated cases. */
576 can_predict_insn_p (const_rtx insn)
578 return (JUMP_P (insn)
579 && any_condjump_p (insn)
580 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
583 /* Predict edge E by given predictor if possible. */
586 predict_edge_def (edge e, enum br_predictor predictor,
587 enum prediction taken)
589 int probability = predictor_info[(int) predictor].hitrate;
592 probability = REG_BR_PROB_BASE - probability;
594 predict_edge (e, predictor, probability);
597 /* Invert all branch predictions or probability notes in the INSN. This needs
598 to be done each time we invert the condition used by the jump. */
601 invert_br_probabilities (rtx insn)
605 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
606 if (REG_NOTE_KIND (note) == REG_BR_PROB)
607 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
608 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
609 XEXP (XEXP (note, 0), 1)
610 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
613 /* Dump information about the branch prediction to the output file. */
616 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
617 basic_block bb, int used)
625 FOR_EACH_EDGE (e, ei, bb->succs)
626 if (! (e->flags & EDGE_FALLTHRU))
629 fprintf (file, " %s heuristics%s: %.1f%%",
630 predictor_info[predictor].name,
631 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
635 fprintf (file, " exec ");
636 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
639 fprintf (file, " hit ");
640 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
641 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
645 fprintf (file, "\n");
648 /* We can not predict the probabilities of outgoing edges of bb. Set them
649 evenly and hope for the best. */
651 set_even_probabilities (basic_block bb)
657 FOR_EACH_EDGE (e, ei, bb->succs)
658 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
660 FOR_EACH_EDGE (e, ei, bb->succs)
661 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
662 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
667 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
668 note if not already present. Remove now useless REG_BR_PRED notes. */
671 combine_predictions_for_insn (rtx insn, basic_block bb)
676 int best_probability = PROB_EVEN;
677 enum br_predictor best_predictor = END_PREDICTORS;
678 int combined_probability = REG_BR_PROB_BASE / 2;
680 bool first_match = false;
683 if (!can_predict_insn_p (insn))
685 set_even_probabilities (bb);
689 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
690 pnote = ®_NOTES (insn);
692 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
695 /* We implement "first match" heuristics and use probability guessed
696 by predictor with smallest index. */
697 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
698 if (REG_NOTE_KIND (note) == REG_BR_PRED)
700 enum br_predictor predictor = ((enum br_predictor)
701 INTVAL (XEXP (XEXP (note, 0), 0)));
702 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
705 if (best_predictor > predictor)
706 best_probability = probability, best_predictor = predictor;
708 d = (combined_probability * probability
709 + (REG_BR_PROB_BASE - combined_probability)
710 * (REG_BR_PROB_BASE - probability));
712 /* Use FP math to avoid overflows of 32bit integers. */
714 /* If one probability is 0% and one 100%, avoid division by zero. */
715 combined_probability = REG_BR_PROB_BASE / 2;
717 combined_probability = (((double) combined_probability) * probability
718 * REG_BR_PROB_BASE / d + 0.5);
721 /* Decide which heuristic to use. In case we didn't match anything,
722 use no_prediction heuristic, in case we did match, use either
723 first match or Dempster-Shaffer theory depending on the flags. */
725 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
729 dump_prediction (dump_file, PRED_NO_PREDICTION,
730 combined_probability, bb, true);
733 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
735 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
740 combined_probability = best_probability;
741 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
745 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
747 enum br_predictor predictor = ((enum br_predictor)
748 INTVAL (XEXP (XEXP (*pnote, 0), 0)));
749 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
751 dump_prediction (dump_file, predictor, probability, bb,
752 !first_match || best_predictor == predictor);
753 *pnote = XEXP (*pnote, 1);
756 pnote = &XEXP (*pnote, 1);
761 add_reg_note (insn, REG_BR_PROB, GEN_INT (combined_probability));
763 /* Save the prediction into CFG in case we are seeing non-degenerated
765 if (!single_succ_p (bb))
767 BRANCH_EDGE (bb)->probability = combined_probability;
768 FALLTHRU_EDGE (bb)->probability
769 = REG_BR_PROB_BASE - combined_probability;
772 else if (!single_succ_p (bb))
774 int prob = INTVAL (XEXP (prob_note, 0));
776 BRANCH_EDGE (bb)->probability = prob;
777 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
780 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
783 /* Combine predictions into single probability and store them into CFG.
784 Remove now useless prediction entries. */
787 combine_predictions_for_bb (basic_block bb)
789 int best_probability = PROB_EVEN;
790 enum br_predictor best_predictor = END_PREDICTORS;
791 int combined_probability = REG_BR_PROB_BASE / 2;
793 bool first_match = false;
795 struct edge_prediction *pred;
797 edge e, first = NULL, second = NULL;
801 FOR_EACH_EDGE (e, ei, bb->succs)
802 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
805 if (first && !second)
811 /* When there is no successor or only one choice, prediction is easy.
813 We are lazy for now and predict only basic blocks with two outgoing
814 edges. It is possible to predict generic case too, but we have to
815 ignore first match heuristics and do more involved combining. Implement
820 set_even_probabilities (bb);
821 clear_bb_predictions (bb);
823 fprintf (dump_file, "%i edges in bb %i predicted to even probabilities\n",
829 fprintf (dump_file, "Predictions for bb %i\n", bb->index);
831 preds = pointer_map_contains (bb_predictions, bb);
834 /* We implement "first match" heuristics and use probability guessed
835 by predictor with smallest index. */
836 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
838 enum br_predictor predictor = pred->ep_predictor;
839 int probability = pred->ep_probability;
841 if (pred->ep_edge != first)
842 probability = REG_BR_PROB_BASE - probability;
845 /* First match heuristics would be widly confused if we predicted
847 if (best_predictor > predictor)
849 struct edge_prediction *pred2;
850 int prob = probability;
852 for (pred2 = (struct edge_prediction *) *preds; pred2; pred2 = pred2->ep_next)
853 if (pred2 != pred && pred2->ep_predictor == pred->ep_predictor)
855 int probability2 = pred->ep_probability;
857 if (pred2->ep_edge != first)
858 probability2 = REG_BR_PROB_BASE - probability2;
860 if ((probability < REG_BR_PROB_BASE / 2) !=
861 (probability2 < REG_BR_PROB_BASE / 2))
864 /* If the same predictor later gave better result, go for it! */
865 if ((probability >= REG_BR_PROB_BASE / 2 && (probability2 > probability))
866 || (probability <= REG_BR_PROB_BASE / 2 && (probability2 < probability)))
870 best_probability = prob, best_predictor = predictor;
873 d = (combined_probability * probability
874 + (REG_BR_PROB_BASE - combined_probability)
875 * (REG_BR_PROB_BASE - probability));
877 /* Use FP math to avoid overflows of 32bit integers. */
879 /* If one probability is 0% and one 100%, avoid division by zero. */
880 combined_probability = REG_BR_PROB_BASE / 2;
882 combined_probability = (((double) combined_probability)
884 * REG_BR_PROB_BASE / d + 0.5);
888 /* Decide which heuristic to use. In case we didn't match anything,
889 use no_prediction heuristic, in case we did match, use either
890 first match or Dempster-Shaffer theory depending on the flags. */
892 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
896 dump_prediction (dump_file, PRED_NO_PREDICTION, combined_probability, bb, true);
899 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability, bb,
901 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability, bb,
906 combined_probability = best_probability;
907 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
911 for (pred = (struct edge_prediction *) *preds; pred; pred = pred->ep_next)
913 enum br_predictor predictor = pred->ep_predictor;
914 int probability = pred->ep_probability;
916 if (pred->ep_edge != EDGE_SUCC (bb, 0))
917 probability = REG_BR_PROB_BASE - probability;
918 dump_prediction (dump_file, predictor, probability, bb,
919 !first_match || best_predictor == predictor);
922 clear_bb_predictions (bb);
926 first->probability = combined_probability;
927 second->probability = REG_BR_PROB_BASE - combined_probability;
931 /* Predict edge probabilities by exploiting loop structure. */
939 /* Try to predict out blocks in a loop that are not part of a
941 FOR_EACH_LOOP (li, loop, 0)
943 basic_block bb, *bbs;
945 VEC (edge, heap) *exits;
946 struct tree_niter_desc niter_desc;
949 exits = get_loop_exit_edges (loop);
950 n_exits = VEC_length (edge, exits);
952 FOR_EACH_VEC_ELT (edge, exits, j, ex)
955 HOST_WIDE_INT nitercst;
956 int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS);
958 enum br_predictor predictor;
960 if (number_of_iterations_exit (loop, ex, &niter_desc, false))
961 niter = niter_desc.niter;
962 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
963 niter = loop_niter_by_eval (loop, ex);
965 if (TREE_CODE (niter) == INTEGER_CST)
967 if (host_integerp (niter, 1)
968 && compare_tree_int (niter, max-1) == -1)
969 nitercst = tree_low_cst (niter, 1) + 1;
972 predictor = PRED_LOOP_ITERATIONS;
974 /* If we have just one exit and we can derive some information about
975 the number of iterations of the loop from the statements inside
976 the loop, use it to predict this exit. */
977 else if (n_exits == 1)
979 nitercst = estimated_loop_iterations_int (loop, false);
985 predictor = PRED_LOOP_ITERATIONS_GUESSED;
990 probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst);
991 predict_edge (ex, predictor, probability);
993 VEC_free (edge, heap, exits);
995 bbs = get_loop_body (loop);
997 for (j = 0; j < loop->num_nodes; j++)
999 int header_found = 0;
1005 /* Bypass loop heuristics on continue statement. These
1006 statements construct loops via "non-loop" constructs
1007 in the source language and are better to be handled
1009 if (predicted_by_p (bb, PRED_CONTINUE))
1012 /* Loop branch heuristics - predict an edge back to a
1013 loop's head as taken. */
1014 if (bb == loop->latch)
1016 e = find_edge (loop->latch, loop->header);
1020 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
1024 /* Loop exit heuristics - predict an edge exiting the loop if the
1025 conditional has no loop header successors as not taken. */
1027 /* If we already used more reliable loop exit predictors, do not
1028 bother with PRED_LOOP_EXIT. */
1029 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED)
1030 && !predicted_by_p (bb, PRED_LOOP_ITERATIONS))
1032 /* For loop with many exits we don't want to predict all exits
1033 with the pretty large probability, because if all exits are
1034 considered in row, the loop would be predicted to iterate
1035 almost never. The code to divide probability by number of
1036 exits is very rough. It should compute the number of exits
1037 taken in each patch through function (not the overall number
1038 of exits that might be a lot higher for loops with wide switch
1039 statements in them) and compute n-th square root.
1041 We limit the minimal probability by 2% to avoid
1042 EDGE_PROBABILITY_RELIABLE from trusting the branch prediction
1043 as this was causing regression in perl benchmark containing such
1046 int probability = ((REG_BR_PROB_BASE
1047 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
1049 if (probability < HITRATE (2))
1050 probability = HITRATE (2);
1051 FOR_EACH_EDGE (e, ei, bb->succs)
1052 if (e->dest->index < NUM_FIXED_BLOCKS
1053 || !flow_bb_inside_loop_p (loop, e->dest))
1054 predict_edge (e, PRED_LOOP_EXIT, probability);
1058 /* Free basic blocks from get_loop_body. */
1063 /* Attempt to predict probabilities of BB outgoing edges using local
1066 bb_estimate_probability_locally (basic_block bb)
1068 rtx last_insn = BB_END (bb);
1071 if (! can_predict_insn_p (last_insn))
1073 cond = get_condition (last_insn, NULL, false, false);
1077 /* Try "pointer heuristic."
1078 A comparison ptr == 0 is predicted as false.
1079 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1080 if (COMPARISON_P (cond)
1081 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
1082 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
1084 if (GET_CODE (cond) == EQ)
1085 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
1086 else if (GET_CODE (cond) == NE)
1087 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
1091 /* Try "opcode heuristic."
1092 EQ tests are usually false and NE tests are usually true. Also,
1093 most quantities are positive, so we can make the appropriate guesses
1094 about signed comparisons against zero. */
1095 switch (GET_CODE (cond))
1098 /* Unconditional branch. */
1099 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
1100 cond == const0_rtx ? NOT_TAKEN : TAKEN);
1105 /* Floating point comparisons appears to behave in a very
1106 unpredictable way because of special role of = tests in
1108 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1110 /* Comparisons with 0 are often used for booleans and there is
1111 nothing useful to predict about them. */
1112 else if (XEXP (cond, 1) == const0_rtx
1113 || XEXP (cond, 0) == const0_rtx)
1116 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
1121 /* Floating point comparisons appears to behave in a very
1122 unpredictable way because of special role of = tests in
1124 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
1126 /* Comparisons with 0 are often used for booleans and there is
1127 nothing useful to predict about them. */
1128 else if (XEXP (cond, 1) == const0_rtx
1129 || XEXP (cond, 0) == const0_rtx)
1132 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
1136 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
1140 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
1145 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1146 || XEXP (cond, 1) == constm1_rtx)
1147 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
1152 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
1153 || XEXP (cond, 1) == constm1_rtx)
1154 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
1162 /* Set edge->probability for each successor edge of BB. */
1164 guess_outgoing_edge_probabilities (basic_block bb)
1166 bb_estimate_probability_locally (bb);
1167 combine_predictions_for_insn (BB_END (bb), bb);
1170 static tree expr_expected_value (tree, bitmap);
1172 /* Helper function for expr_expected_value. */
1175 expr_expected_value_1 (tree type, tree op0, enum tree_code code, tree op1, bitmap visited)
1179 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1181 if (TREE_CONSTANT (op0))
1184 if (code != SSA_NAME)
1187 def = SSA_NAME_DEF_STMT (op0);
1189 /* If we were already here, break the infinite cycle. */
1190 if (!bitmap_set_bit (visited, SSA_NAME_VERSION (op0)))
1193 if (gimple_code (def) == GIMPLE_PHI)
1195 /* All the arguments of the PHI node must have the same constant
1197 int i, n = gimple_phi_num_args (def);
1198 tree val = NULL, new_val;
1200 for (i = 0; i < n; i++)
1202 tree arg = PHI_ARG_DEF (def, i);
1204 /* If this PHI has itself as an argument, we cannot
1205 determine the string length of this argument. However,
1206 if we can find an expected constant value for the other
1207 PHI args then we can still be sure that this is
1208 likely a constant. So be optimistic and just
1209 continue with the next argument. */
1210 if (arg == PHI_RESULT (def))
1213 new_val = expr_expected_value (arg, visited);
1218 else if (!operand_equal_p (val, new_val, false))
1223 if (is_gimple_assign (def))
1225 if (gimple_assign_lhs (def) != op0)
1228 return expr_expected_value_1 (TREE_TYPE (gimple_assign_lhs (def)),
1229 gimple_assign_rhs1 (def),
1230 gimple_assign_rhs_code (def),
1231 gimple_assign_rhs2 (def),
1235 if (is_gimple_call (def))
1237 tree decl = gimple_call_fndecl (def);
1240 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
1241 && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
1245 if (gimple_call_num_args (def) != 2)
1247 val = gimple_call_arg (def, 0);
1248 if (TREE_CONSTANT (val))
1250 return gimple_call_arg (def, 1);
1257 if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
1260 op0 = expr_expected_value (op0, visited);
1263 op1 = expr_expected_value (op1, visited);
1266 res = fold_build2 (code, type, op0, op1);
1267 if (TREE_CONSTANT (res))
1271 if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
1274 op0 = expr_expected_value (op0, visited);
1277 res = fold_build1 (code, type, op0);
1278 if (TREE_CONSTANT (res))
1285 /* Return constant EXPR will likely have at execution time, NULL if unknown.
1286 The function is used by builtin_expect branch predictor so the evidence
1287 must come from this construct and additional possible constant folding.
1289 We may want to implement more involved value guess (such as value range
1290 propagation based prediction), but such tricks shall go to new
1294 expr_expected_value (tree expr, bitmap visited)
1296 enum tree_code code;
1299 if (TREE_CONSTANT (expr))
1302 extract_ops_from_tree (expr, &code, &op0, &op1);
1303 return expr_expected_value_1 (TREE_TYPE (expr),
1304 op0, code, op1, visited);
1308 /* Get rid of all builtin_expect calls and GIMPLE_PREDICT statements
1309 we no longer need. */
1311 strip_predict_hints (void)
1319 gimple_stmt_iterator bi;
1320 for (bi = gsi_start_bb (bb); !gsi_end_p (bi);)
1322 gimple stmt = gsi_stmt (bi);
1324 if (gimple_code (stmt) == GIMPLE_PREDICT)
1326 gsi_remove (&bi, true);
1329 else if (gimple_code (stmt) == GIMPLE_CALL)
1331 tree fndecl = gimple_call_fndecl (stmt);
1334 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1335 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1336 && gimple_call_num_args (stmt) == 2)
1338 var = gimple_call_lhs (stmt);
1342 = gimple_build_assign (var, gimple_call_arg (stmt, 0));
1343 gsi_replace (&bi, ass_stmt, true);
1347 gsi_remove (&bi, true);
1358 /* Predict using opcode of the last statement in basic block. */
1360 tree_predict_by_opcode (basic_block bb)
1362 gimple stmt = last_stmt (bb);
1371 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1373 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1374 if (then_edge->flags & EDGE_TRUE_VALUE)
1376 op0 = gimple_cond_lhs (stmt);
1377 op1 = gimple_cond_rhs (stmt);
1378 cmp = gimple_cond_code (stmt);
1379 type = TREE_TYPE (op0);
1380 visited = BITMAP_ALLOC (NULL);
1381 val = expr_expected_value_1 (boolean_type_node, op0, cmp, op1, visited);
1382 BITMAP_FREE (visited);
1385 if (integer_zerop (val))
1386 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1388 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1391 /* Try "pointer heuristic."
1392 A comparison ptr == 0 is predicted as false.
1393 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1394 if (POINTER_TYPE_P (type))
1397 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1398 else if (cmp == NE_EXPR)
1399 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1403 /* Try "opcode heuristic."
1404 EQ tests are usually false and NE tests are usually true. Also,
1405 most quantities are positive, so we can make the appropriate guesses
1406 about signed comparisons against zero. */
1411 /* Floating point comparisons appears to behave in a very
1412 unpredictable way because of special role of = tests in
1414 if (FLOAT_TYPE_P (type))
1416 /* Comparisons with 0 are often used for booleans and there is
1417 nothing useful to predict about them. */
1418 else if (integer_zerop (op0) || integer_zerop (op1))
1421 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1426 /* Floating point comparisons appears to behave in a very
1427 unpredictable way because of special role of = tests in
1429 if (FLOAT_TYPE_P (type))
1431 /* Comparisons with 0 are often used for booleans and there is
1432 nothing useful to predict about them. */
1433 else if (integer_zerop (op0)
1434 || integer_zerop (op1))
1437 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1441 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1444 case UNORDERED_EXPR:
1445 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1450 if (integer_zerop (op1)
1451 || integer_onep (op1)
1452 || integer_all_onesp (op1)
1455 || real_minus_onep (op1))
1456 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1461 if (integer_zerop (op1)
1462 || integer_onep (op1)
1463 || integer_all_onesp (op1)
1466 || real_minus_onep (op1))
1467 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1475 /* Try to guess whether the value of return means error code. */
1477 static enum br_predictor
1478 return_prediction (tree val, enum prediction *prediction)
1482 return PRED_NO_PREDICTION;
1483 /* Different heuristics for pointers and scalars. */
1484 if (POINTER_TYPE_P (TREE_TYPE (val)))
1486 /* NULL is usually not returned. */
1487 if (integer_zerop (val))
1489 *prediction = NOT_TAKEN;
1490 return PRED_NULL_RETURN;
1493 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1495 /* Negative return values are often used to indicate
1497 if (TREE_CODE (val) == INTEGER_CST
1498 && tree_int_cst_sgn (val) < 0)
1500 *prediction = NOT_TAKEN;
1501 return PRED_NEGATIVE_RETURN;
1503 /* Constant return values seems to be commonly taken.
1504 Zero/one often represent booleans so exclude them from the
1506 if (TREE_CONSTANT (val)
1507 && (!integer_zerop (val) && !integer_onep (val)))
1509 *prediction = TAKEN;
1510 return PRED_CONST_RETURN;
1513 return PRED_NO_PREDICTION;
1516 /* Find the basic block with return expression and look up for possible
1517 return value trying to apply RETURN_PREDICTION heuristics. */
1519 apply_return_prediction (void)
1521 gimple return_stmt = NULL;
1525 int phi_num_args, i;
1526 enum br_predictor pred;
1527 enum prediction direction;
1530 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1532 return_stmt = last_stmt (e->src);
1534 && gimple_code (return_stmt) == GIMPLE_RETURN)
1539 return_val = gimple_return_retval (return_stmt);
1542 if (TREE_CODE (return_val) != SSA_NAME
1543 || !SSA_NAME_DEF_STMT (return_val)
1544 || gimple_code (SSA_NAME_DEF_STMT (return_val)) != GIMPLE_PHI)
1546 phi = SSA_NAME_DEF_STMT (return_val);
1547 phi_num_args = gimple_phi_num_args (phi);
1548 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1550 /* Avoid the degenerate case where all return values form the function
1551 belongs to same category (ie they are all positive constants)
1552 so we can hardly say something about them. */
1553 for (i = 1; i < phi_num_args; i++)
1554 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1556 if (i != phi_num_args)
1557 for (i = 0; i < phi_num_args; i++)
1559 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1560 if (pred != PRED_NO_PREDICTION)
1561 predict_paths_leading_to (gimple_phi_arg_edge (phi, i)->src, pred,
1566 /* Look for basic block that contains unlikely to happen events
1567 (such as noreturn calls) and mark all paths leading to execution
1568 of this basic blocks as unlikely. */
1571 tree_bb_level_predictions (void)
1574 bool has_return_edges = false;
1578 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1579 if (!(e->flags & (EDGE_ABNORMAL | EDGE_FAKE | EDGE_EH)))
1581 has_return_edges = true;
1585 apply_return_prediction ();
1589 gimple_stmt_iterator gsi;
1591 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1593 gimple stmt = gsi_stmt (gsi);
1596 if (is_gimple_call (stmt))
1598 if ((gimple_call_flags (stmt) & ECF_NORETURN)
1599 && has_return_edges)
1600 predict_paths_leading_to (bb, PRED_NORETURN,
1602 decl = gimple_call_fndecl (stmt);
1604 && lookup_attribute ("cold",
1605 DECL_ATTRIBUTES (decl)))
1606 predict_paths_leading_to (bb, PRED_COLD_FUNCTION,
1609 else if (gimple_code (stmt) == GIMPLE_PREDICT)
1611 predict_paths_leading_to (bb, gimple_predict_predictor (stmt),
1612 gimple_predict_outcome (stmt));
1613 /* Keep GIMPLE_PREDICT around so early inlining will propagate
1614 hints to callers. */
1620 #ifdef ENABLE_CHECKING
1622 /* Callback for pointer_map_traverse, asserts that the pointer map is
1626 assert_is_empty (const void *key ATTRIBUTE_UNUSED, void **value,
1627 void *data ATTRIBUTE_UNUSED)
1629 gcc_assert (!*value);
1634 /* Predict branch probabilities and estimate profile for basic block BB. */
1637 tree_estimate_probability_bb (basic_block bb)
1643 FOR_EACH_EDGE (e, ei, bb->succs)
1645 /* Predict early returns to be probable, as we've already taken
1646 care for error returns and other cases are often used for
1647 fast paths through function.
1649 Since we've already removed the return statements, we are
1650 looking for CFG like:
1660 if (e->dest != bb->next_bb
1661 && e->dest != EXIT_BLOCK_PTR
1662 && single_succ_p (e->dest)
1663 && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR
1664 && (last = last_stmt (e->dest)) != NULL
1665 && gimple_code (last) == GIMPLE_RETURN)
1670 if (single_succ_p (bb))
1672 FOR_EACH_EDGE (e1, ei1, bb->preds)
1673 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1674 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1675 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN))
1676 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1679 if (!predicted_by_p (e->src, PRED_NULL_RETURN)
1680 && !predicted_by_p (e->src, PRED_CONST_RETURN)
1681 && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN))
1682 predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1685 /* Look for block we are guarding (ie we dominate it,
1686 but it doesn't postdominate us). */
1687 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1688 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1689 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1691 gimple_stmt_iterator bi;
1693 /* The call heuristic claims that a guarded function call
1694 is improbable. This is because such calls are often used
1695 to signal exceptional situations such as printing error
1697 for (bi = gsi_start_bb (e->dest); !gsi_end_p (bi);
1700 gimple stmt = gsi_stmt (bi);
1701 if (is_gimple_call (stmt)
1702 /* Constant and pure calls are hardly used to signalize
1703 something exceptional. */
1704 && gimple_has_side_effects (stmt))
1706 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1712 tree_predict_by_opcode (bb);
1715 /* Predict branch probabilities and estimate profile of the tree CFG.
1716 This function can be called from the loop optimizers to recompute
1717 the profile information. */
1720 tree_estimate_probability (void)
1724 add_noreturn_fake_exit_edges ();
1725 connect_infinite_loops_to_exit ();
1726 /* We use loop_niter_by_eval, which requires that the loops have
1728 create_preheaders (CP_SIMPLE_PREHEADERS);
1729 calculate_dominance_info (CDI_POST_DOMINATORS);
1731 bb_predictions = pointer_map_create ();
1732 tree_bb_level_predictions ();
1733 record_loop_exits ();
1735 if (number_of_loops () > 1)
1739 tree_estimate_probability_bb (bb);
1742 combine_predictions_for_bb (bb);
1744 #ifdef ENABLE_CHECKING
1745 pointer_map_traverse (bb_predictions, assert_is_empty, NULL);
1747 pointer_map_destroy (bb_predictions);
1748 bb_predictions = NULL;
1750 estimate_bb_frequencies ();
1751 free_dominance_info (CDI_POST_DOMINATORS);
1752 remove_fake_exit_edges ();
1755 /* Predict branch probabilities and estimate profile of the tree CFG.
1756 This is the driver function for PASS_PROFILE. */
1759 tree_estimate_probability_driver (void)
1763 loop_optimizer_init (0);
1764 if (dump_file && (dump_flags & TDF_DETAILS))
1765 flow_loops_dump (dump_file, NULL, 0);
1767 mark_irreducible_loops ();
1769 nb_loops = number_of_loops ();
1773 tree_estimate_probability ();
1778 loop_optimizer_finalize ();
1779 if (dump_file && (dump_flags & TDF_DETAILS))
1780 gimple_dump_cfg (dump_file, dump_flags);
1781 if (profile_status == PROFILE_ABSENT)
1782 profile_status = PROFILE_GUESSED;
1786 /* Predict edges to successors of CUR whose sources are not postdominated by
1787 BB by PRED and recurse to all postdominators. */
1790 predict_paths_for_bb (basic_block cur, basic_block bb,
1791 enum br_predictor pred,
1792 enum prediction taken)
1798 /* We are looking for all edges forming edge cut induced by
1799 set of all blocks postdominated by BB. */
1800 FOR_EACH_EDGE (e, ei, cur->preds)
1801 if (e->src->index >= NUM_FIXED_BLOCKS
1802 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, bb))
1808 /* Ignore abnormals, we predict them as not taken anyway. */
1809 if (e->flags & (EDGE_EH | EDGE_FAKE | EDGE_ABNORMAL))
1811 gcc_assert (bb == cur || dominated_by_p (CDI_POST_DOMINATORS, cur, bb));
1813 /* See if there is how many edge from e->src that is not abnormal
1814 and does not lead to BB. */
1815 FOR_EACH_EDGE (e2, ei2, e->src->succs)
1817 && !(e2->flags & (EDGE_EH | EDGE_FAKE | EDGE_ABNORMAL))
1818 && !dominated_by_p (CDI_POST_DOMINATORS, e2->dest, bb))
1824 /* If there is non-abnormal path leaving e->src, predict edge
1825 using predictor. Otherwise we need to look for paths
1826 leading to e->src. */
1828 predict_edge_def (e, pred, taken);
1830 predict_paths_for_bb (e->src, e->src, pred, taken);
1832 for (son = first_dom_son (CDI_POST_DOMINATORS, cur);
1834 son = next_dom_son (CDI_POST_DOMINATORS, son))
1835 predict_paths_for_bb (son, bb, pred, taken);
1838 /* Sets branch probabilities according to PREDiction and
1842 predict_paths_leading_to (basic_block bb, enum br_predictor pred,
1843 enum prediction taken)
1845 predict_paths_for_bb (bb, bb, pred, taken);
1848 /* This is used to carry information about basic blocks. It is
1849 attached to the AUX field of the standard CFG block. */
1851 typedef struct block_info_def
1853 /* Estimated frequency of execution of basic_block. */
1856 /* To keep queue of basic blocks to process. */
1859 /* Number of predecessors we need to visit first. */
1863 /* Similar information for edges. */
1864 typedef struct edge_info_def
1866 /* In case edge is a loopback edge, the probability edge will be reached
1867 in case header is. Estimated number of iterations of the loop can be
1868 then computed as 1 / (1 - back_edge_prob). */
1869 sreal back_edge_prob;
1870 /* True if the edge is a loopback edge in the natural loop. */
1871 unsigned int back_edge:1;
1874 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1875 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1877 /* Helper function for estimate_bb_frequencies.
1878 Propagate the frequencies in blocks marked in
1879 TOVISIT, starting in HEAD. */
1882 propagate_freq (basic_block head, bitmap tovisit)
1891 /* For each basic block we need to visit count number of his predecessors
1892 we need to visit first. */
1893 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1898 bb = BASIC_BLOCK (i);
1900 FOR_EACH_EDGE (e, ei, bb->preds)
1902 bool visit = bitmap_bit_p (tovisit, e->src->index);
1904 if (visit && !(e->flags & EDGE_DFS_BACK))
1906 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1908 "Irreducible region hit, ignoring edge to %i->%i\n",
1909 e->src->index, bb->index);
1911 BLOCK_INFO (bb)->npredecessors = count;
1912 /* When function never returns, we will never process exit block. */
1913 if (!count && bb == EXIT_BLOCK_PTR)
1914 bb->count = bb->frequency = 0;
1917 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1919 for (bb = head; bb; bb = nextbb)
1922 sreal cyclic_probability, frequency;
1924 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1925 memcpy (&frequency, &real_zero, sizeof (real_zero));
1927 nextbb = BLOCK_INFO (bb)->next;
1928 BLOCK_INFO (bb)->next = NULL;
1930 /* Compute frequency of basic block. */
1933 #ifdef ENABLE_CHECKING
1934 FOR_EACH_EDGE (e, ei, bb->preds)
1935 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1936 || (e->flags & EDGE_DFS_BACK));
1939 FOR_EACH_EDGE (e, ei, bb->preds)
1940 if (EDGE_INFO (e)->back_edge)
1942 sreal_add (&cyclic_probability, &cyclic_probability,
1943 &EDGE_INFO (e)->back_edge_prob);
1945 else if (!(e->flags & EDGE_DFS_BACK))
1949 /* frequency += (e->probability
1950 * BLOCK_INFO (e->src)->frequency /
1951 REG_BR_PROB_BASE); */
1953 sreal_init (&tmp, e->probability, 0);
1954 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1955 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1956 sreal_add (&frequency, &frequency, &tmp);
1959 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1961 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1962 sizeof (frequency));
1966 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
1968 memcpy (&cyclic_probability, &real_almost_one,
1969 sizeof (real_almost_one));
1972 /* BLOCK_INFO (bb)->frequency = frequency
1973 / (1 - cyclic_probability) */
1975 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
1976 sreal_div (&BLOCK_INFO (bb)->frequency,
1977 &frequency, &cyclic_probability);
1981 bitmap_clear_bit (tovisit, bb->index);
1983 e = find_edge (bb, head);
1988 /* EDGE_INFO (e)->back_edge_prob
1989 = ((e->probability * BLOCK_INFO (bb)->frequency)
1990 / REG_BR_PROB_BASE); */
1992 sreal_init (&tmp, e->probability, 0);
1993 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1994 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1995 &tmp, &real_inv_br_prob_base);
1998 /* Propagate to successor blocks. */
1999 FOR_EACH_EDGE (e, ei, bb->succs)
2000 if (!(e->flags & EDGE_DFS_BACK)
2001 && BLOCK_INFO (e->dest)->npredecessors)
2003 BLOCK_INFO (e->dest)->npredecessors--;
2004 if (!BLOCK_INFO (e->dest)->npredecessors)
2009 BLOCK_INFO (last)->next = e->dest;
2017 /* Estimate probabilities of loopback edges in loops at same nest level. */
2020 estimate_loops_at_level (struct loop *first_loop)
2024 for (loop = first_loop; loop; loop = loop->next)
2029 bitmap tovisit = BITMAP_ALLOC (NULL);
2031 estimate_loops_at_level (loop->inner);
2033 /* Find current loop back edge and mark it. */
2034 e = loop_latch_edge (loop);
2035 EDGE_INFO (e)->back_edge = 1;
2037 bbs = get_loop_body (loop);
2038 for (i = 0; i < loop->num_nodes; i++)
2039 bitmap_set_bit (tovisit, bbs[i]->index);
2041 propagate_freq (loop->header, tovisit);
2042 BITMAP_FREE (tovisit);
2046 /* Propagates frequencies through structure of loops. */
2049 estimate_loops (void)
2051 bitmap tovisit = BITMAP_ALLOC (NULL);
2054 /* Start by estimating the frequencies in the loops. */
2055 if (number_of_loops () > 1)
2056 estimate_loops_at_level (current_loops->tree_root->inner);
2058 /* Now propagate the frequencies through all the blocks. */
2061 bitmap_set_bit (tovisit, bb->index);
2063 propagate_freq (ENTRY_BLOCK_PTR, tovisit);
2064 BITMAP_FREE (tovisit);
2067 /* Convert counts measured by profile driven feedback to frequencies.
2068 Return nonzero iff there was any nonzero execution count. */
2071 counts_to_freqs (void)
2073 gcov_type count_max, true_count_max = 0;
2076 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2077 true_count_max = MAX (bb->count, true_count_max);
2079 count_max = MAX (true_count_max, 1);
2080 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2081 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
2083 return true_count_max;
2086 /* Return true if function is likely to be expensive, so there is no point to
2087 optimize performance of prologue, epilogue or do inlining at the expense
2088 of code size growth. THRESHOLD is the limit of number of instructions
2089 function can execute at average to be still considered not expensive. */
2092 expensive_function_p (int threshold)
2094 unsigned int sum = 0;
2098 /* We can not compute accurately for large thresholds due to scaled
2100 gcc_assert (threshold <= BB_FREQ_MAX);
2102 /* Frequencies are out of range. This either means that function contains
2103 internal loop executing more than BB_FREQ_MAX times or profile feedback
2104 is available and function has not been executed at all. */
2105 if (ENTRY_BLOCK_PTR->frequency == 0)
2108 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
2109 limit = ENTRY_BLOCK_PTR->frequency * threshold;
2114 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
2115 insn = NEXT_INSN (insn))
2116 if (active_insn_p (insn))
2118 sum += bb->frequency;
2127 /* Estimate basic blocks frequency by given branch probabilities. */
2130 estimate_bb_frequencies (void)
2135 if (profile_status != PROFILE_READ || !counts_to_freqs ())
2137 static int real_values_initialized = 0;
2139 if (!real_values_initialized)
2141 real_values_initialized = 1;
2142 sreal_init (&real_zero, 0, 0);
2143 sreal_init (&real_one, 1, 0);
2144 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
2145 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
2146 sreal_init (&real_one_half, 1, -1);
2147 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
2148 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
2151 mark_dfs_back_edges ();
2153 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
2155 /* Set up block info for each basic block. */
2156 alloc_aux_for_blocks (sizeof (struct block_info_def));
2157 alloc_aux_for_edges (sizeof (struct edge_info_def));
2158 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2163 FOR_EACH_EDGE (e, ei, bb->succs)
2165 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
2166 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
2167 &EDGE_INFO (e)->back_edge_prob,
2168 &real_inv_br_prob_base);
2172 /* First compute probabilities locally for each loop from innermost
2173 to outermost to examine probabilities for back edges. */
2176 memcpy (&freq_max, &real_zero, sizeof (real_zero));
2178 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
2179 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
2181 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
2182 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
2186 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
2187 sreal_add (&tmp, &tmp, &real_one_half);
2188 bb->frequency = sreal_to_int (&tmp);
2191 free_aux_for_blocks ();
2192 free_aux_for_edges ();
2194 compute_function_frequency ();
2197 /* Decide whether function is hot, cold or unlikely executed. */
2199 compute_function_frequency (void)
2202 struct cgraph_node *node = cgraph_node (current_function_decl);
2203 if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2204 || MAIN_NAME_P (DECL_NAME (current_function_decl)))
2205 node->only_called_at_startup = true;
2206 if (DECL_STATIC_DESTRUCTOR (current_function_decl))
2207 node->only_called_at_exit = true;
2209 if (!profile_info || !flag_branch_probabilities)
2211 int flags = flags_from_decl_or_type (current_function_decl);
2212 if (lookup_attribute ("cold", DECL_ATTRIBUTES (current_function_decl))
2214 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2215 else if (lookup_attribute ("hot", DECL_ATTRIBUTES (current_function_decl))
2217 node->frequency = NODE_FREQUENCY_HOT;
2218 else if (flags & ECF_NORETURN)
2219 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2220 else if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
2221 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2222 else if (DECL_STATIC_CONSTRUCTOR (current_function_decl)
2223 || DECL_STATIC_DESTRUCTOR (current_function_decl))
2224 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2227 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2230 if (maybe_hot_bb_p (bb))
2232 node->frequency = NODE_FREQUENCY_HOT;
2235 if (!probably_never_executed_bb_p (bb))
2236 node->frequency = NODE_FREQUENCY_NORMAL;
2241 gate_estimate_probability (void)
2243 return flag_guess_branch_prob;
2246 /* Build PREDICT_EXPR. */
2248 build_predict_expr (enum br_predictor predictor, enum prediction taken)
2250 tree t = build1 (PREDICT_EXPR, void_type_node,
2251 build_int_cst (NULL, predictor));
2252 SET_PREDICT_EXPR_OUTCOME (t, taken);
2257 predictor_name (enum br_predictor predictor)
2259 return predictor_info[predictor].name;
2262 struct gimple_opt_pass pass_profile =
2266 "profile", /* name */
2267 gate_estimate_probability, /* gate */
2268 tree_estimate_probability_driver, /* execute */
2271 0, /* static_pass_number */
2272 TV_BRANCH_PROB, /* tv_id */
2273 PROP_cfg, /* properties_required */
2274 0, /* properties_provided */
2275 0, /* properties_destroyed */
2276 0, /* todo_flags_start */
2277 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2281 struct gimple_opt_pass pass_strip_predict_hints =
2285 "*strip_predict_hints", /* name */
2287 strip_predict_hints, /* execute */
2290 0, /* static_pass_number */
2291 TV_BRANCH_PROB, /* tv_id */
2292 PROP_cfg, /* properties_required */
2293 0, /* properties_provided */
2294 0, /* properties_destroyed */
2295 0, /* todo_flags_start */
2296 TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
2300 /* Rebuild function frequencies. Passes are in general expected to
2301 maintain profile by hand, however in some cases this is not possible:
2302 for example when inlining several functions with loops freuqencies might run
2303 out of scale and thus needs to be recomputed. */
2306 rebuild_frequencies (void)
2308 timevar_push (TV_REBUILD_FREQUENCIES);
2309 if (profile_status == PROFILE_GUESSED)
2311 loop_optimizer_init (0);
2312 add_noreturn_fake_exit_edges ();
2313 mark_irreducible_loops ();
2314 connect_infinite_loops_to_exit ();
2315 estimate_bb_frequencies ();
2316 remove_fake_exit_edges ();
2317 loop_optimizer_finalize ();
2319 else if (profile_status == PROFILE_READ)
2323 timevar_pop (TV_REBUILD_FREQUENCIES);