1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 [1] "Branch Prediction for Free"
25 Ball and Larus; PLDI '93.
26 [2] "Static Branch Frequency and Program Profile Analysis"
27 Wu and Larus; MICRO-27.
28 [3] "Corpus-based Static Branch Prediction"
29 Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95. */
34 #include "coretypes.h"
39 #include "hard-reg-set.h"
40 #include "basic-block.h"
41 #include "insn-config.h"
56 #include "tree-flow.h"
58 #include "tree-dump.h"
59 #include "tree-pass.h"
61 #include "tree-scalar-evolution.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 estimate_loops_at_level (struct loop *, bitmap);
78 static void propagate_freq (struct loop *, bitmap);
79 static void estimate_bb_frequencies (struct loops *);
80 static void predict_paths_leading_to (basic_block, int *, enum br_predictor, enum prediction);
81 static bool last_basic_block_p (basic_block);
82 static void compute_function_frequency (void);
83 static void choose_function_section (void);
84 static bool can_predict_insn_p (rtx);
86 /* Information we hold about each branch predictor.
87 Filled using information from predict.def. */
91 const char *const name; /* Name used in the debugging dumps. */
92 const int hitrate; /* Expected hitrate used by
93 predict_insn_def call. */
97 /* Use given predictor without Dempster-Shaffer theory if it matches
98 using first_match heuristics. */
99 #define PRED_FLAG_FIRST_MATCH 1
101 /* Recompute hitrate in percent to our representation. */
103 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
105 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
106 static const struct predictor_info predictor_info[]= {
107 #include "predict.def"
109 /* Upper bound on predictors. */
114 /* Return true in case BB can be CPU intensive and should be optimized
115 for maximal performance. */
118 maybe_hot_bb_p (basic_block bb)
120 if (profile_info && flag_branch_probabilities
122 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
124 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
129 /* Return true in case BB is cold and should be optimized for size. */
132 probably_cold_bb_p (basic_block bb)
134 if (profile_info && flag_branch_probabilities
136 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
138 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
143 /* Return true in case BB is probably never executed. */
145 probably_never_executed_bb_p (basic_block bb)
147 if (profile_info && flag_branch_probabilities)
148 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
152 /* Return true if the one of outgoing edges is already predicted by
156 rtl_predicted_by_p (basic_block bb, enum br_predictor predictor)
159 if (!INSN_P (BB_END (bb)))
161 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
162 if (REG_NOTE_KIND (note) == REG_BR_PRED
163 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
168 /* Return true if the one of outgoing edges is already predicted by
172 tree_predicted_by_p (basic_block bb, enum br_predictor predictor)
174 struct edge_prediction *i;
175 for (i = bb->predictions; i; i = i->next)
176 if (i->predictor == predictor)
182 predict_insn (rtx insn, enum br_predictor predictor, int probability)
184 gcc_assert (any_condjump_p (insn));
185 if (!flag_guess_branch_prob)
189 = gen_rtx_EXPR_LIST (REG_BR_PRED,
190 gen_rtx_CONCAT (VOIDmode,
191 GEN_INT ((int) predictor),
192 GEN_INT ((int) probability)),
196 /* Predict insn by given predictor. */
199 predict_insn_def (rtx insn, enum br_predictor predictor,
200 enum prediction taken)
202 int probability = predictor_info[(int) predictor].hitrate;
205 probability = REG_BR_PROB_BASE - probability;
207 predict_insn (insn, predictor, probability);
210 /* Predict edge E with given probability if possible. */
213 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
216 last_insn = BB_END (e->src);
218 /* We can store the branch prediction information only about
219 conditional jumps. */
220 if (!any_condjump_p (last_insn))
223 /* We always store probability of branching. */
224 if (e->flags & EDGE_FALLTHRU)
225 probability = REG_BR_PROB_BASE - probability;
227 predict_insn (last_insn, predictor, probability);
230 /* Predict edge E with the given PROBABILITY. */
232 tree_predict_edge (edge e, enum br_predictor predictor, int probability)
234 struct edge_prediction *i = ggc_alloc (sizeof (struct edge_prediction));
236 i->next = e->src->predictions;
237 e->src->predictions = i;
238 i->probability = probability;
239 i->predictor = predictor;
243 /* Remove all predictions on given basic block that are attached
246 remove_predictions_associated_with_edge (edge e)
248 if (e->src->predictions)
250 struct edge_prediction **prediction = &e->src->predictions;
253 if ((*prediction)->edge == e)
254 *prediction = (*prediction)->next;
256 prediction = &((*prediction)->next);
261 /* Return true when we can store prediction on insn INSN.
262 At the moment we represent predictions only on conditional
263 jumps, not at computed jump or other complicated cases. */
265 can_predict_insn_p (rtx insn)
267 return (JUMP_P (insn)
268 && any_condjump_p (insn)
269 && EDGE_COUNT (BLOCK_FOR_INSN (insn)->succs) >= 2);
272 /* Predict edge E by given predictor if possible. */
275 predict_edge_def (edge e, enum br_predictor predictor,
276 enum prediction taken)
278 int probability = predictor_info[(int) predictor].hitrate;
281 probability = REG_BR_PROB_BASE - probability;
283 predict_edge (e, predictor, probability);
286 /* Invert all branch predictions or probability notes in the INSN. This needs
287 to be done each time we invert the condition used by the jump. */
290 invert_br_probabilities (rtx insn)
294 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
295 if (REG_NOTE_KIND (note) == REG_BR_PROB)
296 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
297 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
298 XEXP (XEXP (note, 0), 1)
299 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
302 /* Dump information about the branch prediction to the output file. */
305 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
306 basic_block bb, int used)
314 FOR_EACH_EDGE (e, ei, bb->succs)
315 if (! (e->flags & EDGE_FALLTHRU))
318 fprintf (file, " %s heuristics%s: %.1f%%",
319 predictor_info[predictor].name,
320 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
324 fprintf (file, " exec ");
325 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
328 fprintf (file, " hit ");
329 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
330 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
334 fprintf (file, "\n");
337 /* We can not predict the probabilities of outgoing edges of bb. Set them
338 evenly and hope for the best. */
340 set_even_probabilities (basic_block bb)
346 FOR_EACH_EDGE (e, ei, bb->succs)
347 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
349 FOR_EACH_EDGE (e, ei, bb->succs)
350 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
351 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
356 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
357 note if not already present. Remove now useless REG_BR_PRED notes. */
360 combine_predictions_for_insn (rtx insn, basic_block bb)
365 int best_probability = PROB_EVEN;
366 int best_predictor = END_PREDICTORS;
367 int combined_probability = REG_BR_PROB_BASE / 2;
369 bool first_match = false;
372 if (!can_predict_insn_p (insn))
374 set_even_probabilities (bb);
378 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
379 pnote = ®_NOTES (insn);
381 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
384 /* We implement "first match" heuristics and use probability guessed
385 by predictor with smallest index. */
386 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
387 if (REG_NOTE_KIND (note) == REG_BR_PRED)
389 int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
390 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
393 if (best_predictor > predictor)
394 best_probability = probability, best_predictor = predictor;
396 d = (combined_probability * probability
397 + (REG_BR_PROB_BASE - combined_probability)
398 * (REG_BR_PROB_BASE - probability));
400 /* Use FP math to avoid overflows of 32bit integers. */
402 /* If one probability is 0% and one 100%, avoid division by zero. */
403 combined_probability = REG_BR_PROB_BASE / 2;
405 combined_probability = (((double) combined_probability) * probability
406 * REG_BR_PROB_BASE / d + 0.5);
409 /* Decide which heuristic to use. In case we didn't match anything,
410 use no_prediction heuristic, in case we did match, use either
411 first match or Dempster-Shaffer theory depending on the flags. */
413 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
417 dump_prediction (dump_file, PRED_NO_PREDICTION,
418 combined_probability, bb, true);
421 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
423 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
428 combined_probability = best_probability;
429 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
433 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
435 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
436 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
438 dump_prediction (dump_file, predictor, probability, bb,
439 !first_match || best_predictor == predictor);
440 *pnote = XEXP (*pnote, 1);
443 pnote = &XEXP (*pnote, 1);
449 = gen_rtx_EXPR_LIST (REG_BR_PROB,
450 GEN_INT (combined_probability), REG_NOTES (insn));
452 /* Save the prediction into CFG in case we are seeing non-degenerated
454 if (!single_succ_p (bb))
456 BRANCH_EDGE (bb)->probability = combined_probability;
457 FALLTHRU_EDGE (bb)->probability
458 = REG_BR_PROB_BASE - combined_probability;
461 else if (!single_succ_p (bb))
463 int prob = INTVAL (XEXP (prob_note, 0));
465 BRANCH_EDGE (bb)->probability = prob;
466 FALLTHRU_EDGE (bb)->probability = REG_BR_PROB_BASE - prob;
469 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
472 /* Combine predictions into single probability and store them into CFG.
473 Remove now useless prediction entries. */
476 combine_predictions_for_bb (FILE *file, basic_block bb)
478 int best_probability = PROB_EVEN;
479 int best_predictor = END_PREDICTORS;
480 int combined_probability = REG_BR_PROB_BASE / 2;
482 bool first_match = false;
484 struct edge_prediction *pred;
486 edge e, first = NULL, second = NULL;
489 FOR_EACH_EDGE (e, ei, bb->succs)
490 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
493 if (first && !second)
499 /* When there is no successor or only one choice, prediction is easy.
501 We are lazy for now and predict only basic blocks with two outgoing
502 edges. It is possible to predict generic case too, but we have to
503 ignore first match heuristics and do more involved combining. Implement
508 set_even_probabilities (bb);
509 bb->predictions = NULL;
511 fprintf (file, "%i edges in bb %i predicted to even probabilities\n",
517 fprintf (file, "Predictions for bb %i\n", bb->index);
519 /* We implement "first match" heuristics and use probability guessed
520 by predictor with smallest index. */
521 for (pred = bb->predictions; pred; pred = pred->next)
523 int predictor = pred->predictor;
524 int probability = pred->probability;
526 if (pred->edge != first)
527 probability = REG_BR_PROB_BASE - probability;
530 if (best_predictor > predictor)
531 best_probability = probability, best_predictor = predictor;
533 d = (combined_probability * probability
534 + (REG_BR_PROB_BASE - combined_probability)
535 * (REG_BR_PROB_BASE - probability));
537 /* Use FP math to avoid overflows of 32bit integers. */
539 /* If one probability is 0% and one 100%, avoid division by zero. */
540 combined_probability = REG_BR_PROB_BASE / 2;
542 combined_probability = (((double) combined_probability) * probability
543 * REG_BR_PROB_BASE / d + 0.5);
546 /* Decide which heuristic to use. In case we didn't match anything,
547 use no_prediction heuristic, in case we did match, use either
548 first match or Dempster-Shaffer theory depending on the flags. */
550 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
554 dump_prediction (file, PRED_NO_PREDICTION, combined_probability, bb, true);
557 dump_prediction (file, PRED_DS_THEORY, combined_probability, bb,
559 dump_prediction (file, PRED_FIRST_MATCH, best_probability, bb,
564 combined_probability = best_probability;
565 dump_prediction (file, PRED_COMBINED, combined_probability, bb, true);
567 for (pred = bb->predictions; pred; pred = pred->next)
569 int predictor = pred->predictor;
570 int probability = pred->probability;
572 if (pred->edge != EDGE_SUCC (bb, 0))
573 probability = REG_BR_PROB_BASE - probability;
574 dump_prediction (file, predictor, probability, bb,
575 !first_match || best_predictor == predictor);
577 bb->predictions = NULL;
581 first->probability = combined_probability;
582 second->probability = REG_BR_PROB_BASE - combined_probability;
586 /* Predict edge probabilities by exploiting loop structure.
587 When RTLSIMPLELOOPS is set, attempt to count number of iterations by analyzing
588 RTL otherwise use tree based approach. */
590 predict_loops (struct loops *loops_info, bool rtlsimpleloops)
595 scev_initialize (loops_info);
597 /* Try to predict out blocks in a loop that are not part of a
599 for (i = 1; i < loops_info->num; i++)
601 basic_block bb, *bbs;
604 struct loop *loop = loops_info->parray[i];
605 struct niter_desc desc;
606 unsigned HOST_WIDE_INT niter;
609 exits = get_loop_exit_edges (loop, &n_exits);
613 iv_analysis_loop_init (loop);
614 find_simple_exit (loop, &desc);
616 if (desc.simple_p && desc.const_iter)
619 niter = desc.niter + 1;
620 if (niter == 0) /* We might overflow here. */
623 prob = (REG_BR_PROB_BASE
624 - (REG_BR_PROB_BASE + niter /2) / niter);
625 /* Branch prediction algorithm gives 0 frequency for everything
626 after the end of loop for loop having 0 probability to finish. */
627 if (prob == REG_BR_PROB_BASE)
628 prob = REG_BR_PROB_BASE - 1;
629 predict_edge (desc.in_edge, PRED_LOOP_ITERATIONS,
635 struct tree_niter_desc niter_desc;
637 for (j = 0; j < n_exits; j++)
641 if (number_of_iterations_exit (loop, exits[j], &niter_desc))
642 niter = niter_desc.niter;
643 if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
644 niter = loop_niter_by_eval (loop, exits[j]);
646 if (TREE_CODE (niter) == INTEGER_CST)
649 if (host_integerp (niter, 1)
650 && tree_int_cst_lt (niter,
651 build_int_cstu (NULL_TREE,
652 REG_BR_PROB_BASE - 1)))
654 HOST_WIDE_INT nitercst = tree_low_cst (niter, 1) + 1;
655 probability = (REG_BR_PROB_BASE + nitercst / 2) / nitercst;
660 predict_edge (exits[j], PRED_LOOP_ITERATIONS, probability);
667 bbs = get_loop_body (loop);
669 for (j = 0; j < loop->num_nodes; j++)
671 int header_found = 0;
677 /* Bypass loop heuristics on continue statement. These
678 statements construct loops via "non-loop" constructs
679 in the source language and are better to be handled
681 if ((rtlsimpleloops && !can_predict_insn_p (BB_END (bb)))
682 || predicted_by_p (bb, PRED_CONTINUE))
685 /* Loop branch heuristics - predict an edge back to a
686 loop's head as taken. */
687 if (bb == loop->latch)
689 e = find_edge (loop->latch, loop->header);
693 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
697 /* Loop exit heuristics - predict an edge exiting the loop if the
698 conditional has no loop header successors as not taken. */
700 FOR_EACH_EDGE (e, ei, bb->succs)
701 if (e->dest->index < 0
702 || !flow_bb_inside_loop_p (loop, e->dest))
706 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
710 /* Free basic blocks from get_loop_body. */
717 current_loops = NULL;
721 /* Attempt to predict probabilities of BB outgoing edges using local
724 bb_estimate_probability_locally (basic_block bb)
726 rtx last_insn = BB_END (bb);
729 if (! can_predict_insn_p (last_insn))
731 cond = get_condition (last_insn, NULL, false, false);
735 /* Try "pointer heuristic."
736 A comparison ptr == 0 is predicted as false.
737 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
738 if (COMPARISON_P (cond)
739 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
740 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
742 if (GET_CODE (cond) == EQ)
743 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
744 else if (GET_CODE (cond) == NE)
745 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
749 /* Try "opcode heuristic."
750 EQ tests are usually false and NE tests are usually true. Also,
751 most quantities are positive, so we can make the appropriate guesses
752 about signed comparisons against zero. */
753 switch (GET_CODE (cond))
756 /* Unconditional branch. */
757 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
758 cond == const0_rtx ? NOT_TAKEN : TAKEN);
763 /* Floating point comparisons appears to behave in a very
764 unpredictable way because of special role of = tests in
766 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
768 /* Comparisons with 0 are often used for booleans and there is
769 nothing useful to predict about them. */
770 else if (XEXP (cond, 1) == const0_rtx
771 || XEXP (cond, 0) == const0_rtx)
774 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
779 /* Floating point comparisons appears to behave in a very
780 unpredictable way because of special role of = tests in
782 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
784 /* Comparisons with 0 are often used for booleans and there is
785 nothing useful to predict about them. */
786 else if (XEXP (cond, 1) == const0_rtx
787 || XEXP (cond, 0) == const0_rtx)
790 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
794 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
798 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
803 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
804 || XEXP (cond, 1) == constm1_rtx)
805 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
810 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
811 || XEXP (cond, 1) == constm1_rtx)
812 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
820 /* Statically estimate the probability that a branch will be taken and produce
821 estimated profile. When profile feedback is present never executed portions
822 of function gets estimated. */
825 estimate_probability (struct loops *loops_info)
829 connect_infinite_loops_to_exit ();
830 calculate_dominance_info (CDI_DOMINATORS);
831 calculate_dominance_info (CDI_POST_DOMINATORS);
833 predict_loops (loops_info, true);
837 /* Attempt to predict conditional jumps using a number of heuristics. */
840 rtx last_insn = BB_END (bb);
844 if (! can_predict_insn_p (last_insn))
847 FOR_EACH_EDGE (e, ei, bb->succs)
849 /* Predict early returns to be probable, as we've already taken
850 care for error returns and other are often used for fast paths
852 if ((e->dest == EXIT_BLOCK_PTR
853 || (single_succ_p (e->dest)
854 && single_succ (e->dest) == EXIT_BLOCK_PTR))
855 && !predicted_by_p (bb, PRED_NULL_RETURN)
856 && !predicted_by_p (bb, PRED_CONST_RETURN)
857 && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
858 && !last_basic_block_p (e->dest))
859 predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
861 /* Look for block we are guarding (i.e. we dominate it,
862 but it doesn't postdominate us). */
863 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
864 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
865 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
869 /* The call heuristic claims that a guarded function call
870 is improbable. This is because such calls are often used
871 to signal exceptional situations such as printing error
873 for (insn = BB_HEAD (e->dest); insn != NEXT_INSN (BB_END (e->dest));
874 insn = NEXT_INSN (insn))
876 /* Constant and pure calls are hardly used to signalize
877 something exceptional. */
878 && ! CONST_OR_PURE_CALL_P (insn))
880 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
885 bb_estimate_probability_locally (bb);
888 /* Attach the combined probability to each conditional jump. */
890 combine_predictions_for_insn (BB_END (bb), bb);
892 remove_fake_edges ();
893 estimate_bb_frequencies (loops_info);
894 free_dominance_info (CDI_POST_DOMINATORS);
895 if (profile_status == PROFILE_ABSENT)
896 profile_status = PROFILE_GUESSED;
899 /* Set edge->probability for each successor edge of BB. */
901 guess_outgoing_edge_probabilities (basic_block bb)
903 bb_estimate_probability_locally (bb);
904 combine_predictions_for_insn (BB_END (bb), bb);
907 /* Return constant EXPR will likely have at execution time, NULL if unknown.
908 The function is used by builtin_expect branch predictor so the evidence
909 must come from this construct and additional possible constant folding.
911 We may want to implement more involved value guess (such as value range
912 propagation based prediction), but such tricks shall go to new
916 expr_expected_value (tree expr, bitmap visited)
918 if (TREE_CONSTANT (expr))
920 else if (TREE_CODE (expr) == SSA_NAME)
922 tree def = SSA_NAME_DEF_STMT (expr);
924 /* If we were already here, break the infinite cycle. */
925 if (bitmap_bit_p (visited, SSA_NAME_VERSION (expr)))
927 bitmap_set_bit (visited, SSA_NAME_VERSION (expr));
929 if (TREE_CODE (def) == PHI_NODE)
931 /* All the arguments of the PHI node must have the same constant
934 tree val = NULL, new_val;
936 for (i = 0; i < PHI_NUM_ARGS (def); i++)
938 tree arg = PHI_ARG_DEF (def, i);
940 /* If this PHI has itself as an argument, we cannot
941 determine the string length of this argument. However,
942 if we can find an expected constant value for the other
943 PHI args then we can still be sure that this is
944 likely a constant. So be optimistic and just
945 continue with the next argument. */
946 if (arg == PHI_RESULT (def))
949 new_val = expr_expected_value (arg, visited);
954 else if (!operand_equal_p (val, new_val, false))
959 if (TREE_CODE (def) != MODIFY_EXPR || TREE_OPERAND (def, 0) != expr)
961 return expr_expected_value (TREE_OPERAND (def, 1), visited);
963 else if (TREE_CODE (expr) == CALL_EXPR)
965 tree decl = get_callee_fndecl (expr);
968 if (DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL
969 && DECL_FUNCTION_CODE (decl) == BUILT_IN_EXPECT)
971 tree arglist = TREE_OPERAND (expr, 1);
974 if (arglist == NULL_TREE
975 || TREE_CHAIN (arglist) == NULL_TREE)
977 val = TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr, 1)));
978 if (TREE_CONSTANT (val))
980 return TREE_VALUE (TREE_CHAIN (TREE_OPERAND (expr, 1)));
983 if (BINARY_CLASS_P (expr) || COMPARISON_CLASS_P (expr))
986 op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
989 op1 = expr_expected_value (TREE_OPERAND (expr, 1), visited);
992 res = fold (build (TREE_CODE (expr), TREE_TYPE (expr), op0, op1));
993 if (TREE_CONSTANT (res))
997 if (UNARY_CLASS_P (expr))
1000 op0 = expr_expected_value (TREE_OPERAND (expr, 0), visited);
1003 res = fold (build1 (TREE_CODE (expr), TREE_TYPE (expr), op0));
1004 if (TREE_CONSTANT (res))
1011 /* Get rid of all builtin_expect calls we no longer need. */
1013 strip_builtin_expect (void)
1018 block_stmt_iterator bi;
1019 for (bi = bsi_start (bb); !bsi_end_p (bi); bsi_next (&bi))
1021 tree stmt = bsi_stmt (bi);
1025 if (TREE_CODE (stmt) == MODIFY_EXPR
1026 && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR
1027 && (fndecl = get_callee_fndecl (TREE_OPERAND (stmt, 1)))
1028 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
1029 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_EXPECT
1030 && (arglist = TREE_OPERAND (TREE_OPERAND (stmt, 1), 1))
1031 && TREE_CHAIN (arglist))
1033 TREE_OPERAND (stmt, 1) = TREE_VALUE (arglist);
1040 /* Predict using opcode of the last statement in basic block. */
1042 tree_predict_by_opcode (basic_block bb)
1044 tree stmt = last_stmt (bb);
1053 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
1055 FOR_EACH_EDGE (then_edge, ei, bb->succs)
1056 if (then_edge->flags & EDGE_TRUE_VALUE)
1058 cond = TREE_OPERAND (stmt, 0);
1059 if (!COMPARISON_CLASS_P (cond))
1061 op0 = TREE_OPERAND (cond, 0);
1062 type = TREE_TYPE (op0);
1063 visited = BITMAP_ALLOC (NULL);
1064 val = expr_expected_value (cond, visited);
1065 BITMAP_FREE (visited);
1068 if (integer_zerop (val))
1069 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, NOT_TAKEN);
1071 predict_edge_def (then_edge, PRED_BUILTIN_EXPECT, TAKEN);
1074 /* Try "pointer heuristic."
1075 A comparison ptr == 0 is predicted as false.
1076 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
1077 if (POINTER_TYPE_P (type))
1079 if (TREE_CODE (cond) == EQ_EXPR)
1080 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
1081 else if (TREE_CODE (cond) == NE_EXPR)
1082 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
1086 /* Try "opcode heuristic."
1087 EQ tests are usually false and NE tests are usually true. Also,
1088 most quantities are positive, so we can make the appropriate guesses
1089 about signed comparisons against zero. */
1090 switch (TREE_CODE (cond))
1094 /* Floating point comparisons appears to behave in a very
1095 unpredictable way because of special role of = tests in
1097 if (FLOAT_TYPE_P (type))
1099 /* Comparisons with 0 are often used for booleans and there is
1100 nothing useful to predict about them. */
1101 else if (integer_zerop (op0)
1102 || integer_zerop (TREE_OPERAND (cond, 1)))
1105 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
1110 /* Floating point comparisons appears to behave in a very
1111 unpredictable way because of special role of = tests in
1113 if (FLOAT_TYPE_P (type))
1115 /* Comparisons with 0 are often used for booleans and there is
1116 nothing useful to predict about them. */
1117 else if (integer_zerop (op0)
1118 || integer_zerop (TREE_OPERAND (cond, 1)))
1121 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
1125 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
1128 case UNORDERED_EXPR:
1129 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
1134 if (integer_zerop (TREE_OPERAND (cond, 1))
1135 || integer_onep (TREE_OPERAND (cond, 1))
1136 || integer_all_onesp (TREE_OPERAND (cond, 1))
1137 || real_zerop (TREE_OPERAND (cond, 1))
1138 || real_onep (TREE_OPERAND (cond, 1))
1139 || real_minus_onep (TREE_OPERAND (cond, 1)))
1140 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
1145 if (integer_zerop (TREE_OPERAND (cond, 1))
1146 || integer_onep (TREE_OPERAND (cond, 1))
1147 || integer_all_onesp (TREE_OPERAND (cond, 1))
1148 || real_zerop (TREE_OPERAND (cond, 1))
1149 || real_onep (TREE_OPERAND (cond, 1))
1150 || real_minus_onep (TREE_OPERAND (cond, 1)))
1151 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
1159 /* Try to guess whether the value of return means error code. */
1160 static enum br_predictor
1161 return_prediction (tree val, enum prediction *prediction)
1165 return PRED_NO_PREDICTION;
1166 /* Different heuristics for pointers and scalars. */
1167 if (POINTER_TYPE_P (TREE_TYPE (val)))
1169 /* NULL is usually not returned. */
1170 if (integer_zerop (val))
1172 *prediction = NOT_TAKEN;
1173 return PRED_NULL_RETURN;
1176 else if (INTEGRAL_TYPE_P (TREE_TYPE (val)))
1178 /* Negative return values are often used to indicate
1180 if (TREE_CODE (val) == INTEGER_CST
1181 && tree_int_cst_sgn (val) < 0)
1183 *prediction = NOT_TAKEN;
1184 return PRED_NEGATIVE_RETURN;
1186 /* Constant return values seems to be commonly taken.
1187 Zero/one often represent booleans so exclude them from the
1189 if (TREE_CONSTANT (val)
1190 && (!integer_zerop (val) && !integer_onep (val)))
1192 *prediction = TAKEN;
1193 return PRED_NEGATIVE_RETURN;
1196 return PRED_NO_PREDICTION;
1199 /* Find the basic block with return expression and look up for possible
1200 return value trying to apply RETURN_PREDICTION heuristics. */
1202 apply_return_prediction (int *heads)
1208 int phi_num_args, i;
1209 enum br_predictor pred;
1210 enum prediction direction;
1213 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1215 return_stmt = last_stmt (e->src);
1216 if (TREE_CODE (return_stmt) == RETURN_EXPR)
1221 return_val = TREE_OPERAND (return_stmt, 0);
1224 if (TREE_CODE (return_val) == MODIFY_EXPR)
1225 return_val = TREE_OPERAND (return_val, 1);
1226 if (TREE_CODE (return_val) != SSA_NAME
1227 || !SSA_NAME_DEF_STMT (return_val)
1228 || TREE_CODE (SSA_NAME_DEF_STMT (return_val)) != PHI_NODE)
1230 for (phi = SSA_NAME_DEF_STMT (return_val); phi; phi = PHI_CHAIN (phi))
1231 if (PHI_RESULT (phi) == return_val)
1235 phi_num_args = PHI_NUM_ARGS (phi);
1236 pred = return_prediction (PHI_ARG_DEF (phi, 0), &direction);
1238 /* Avoid the degenerate case where all return values form the function
1239 belongs to same category (ie they are all positive constants)
1240 so we can hardly say something about them. */
1241 for (i = 1; i < phi_num_args; i++)
1242 if (pred != return_prediction (PHI_ARG_DEF (phi, i), &direction))
1244 if (i != phi_num_args)
1245 for (i = 0; i < phi_num_args; i++)
1247 pred = return_prediction (PHI_ARG_DEF (phi, i), &direction);
1248 if (pred != PRED_NO_PREDICTION)
1249 predict_paths_leading_to (PHI_ARG_EDGE (phi, i)->src, heads, pred,
1254 /* Look for basic block that contains unlikely to happen events
1255 (such as noreturn calls) and mark all paths leading to execution
1256 of this basic blocks as unlikely. */
1259 tree_bb_level_predictions (void)
1264 heads = xmalloc (sizeof (int) * last_basic_block);
1265 memset (heads, -1, sizeof (int) * last_basic_block);
1266 heads[ENTRY_BLOCK_PTR->next_bb->index] = last_basic_block;
1268 apply_return_prediction (heads);
1272 block_stmt_iterator bsi = bsi_last (bb);
1274 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1276 tree stmt = bsi_stmt (bsi);
1277 switch (TREE_CODE (stmt))
1280 if (TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
1282 stmt = TREE_OPERAND (stmt, 1);
1288 if (call_expr_flags (stmt) & ECF_NORETURN)
1289 predict_paths_leading_to (bb, heads, PRED_NORETURN,
1301 /* Predict branch probabilities and estimate profile of the tree CFG. */
1303 tree_estimate_probability (void)
1306 struct loops loops_info;
1308 flow_loops_find (&loops_info);
1309 if (dump_file && (dump_flags & TDF_DETAILS))
1310 flow_loops_dump (&loops_info, dump_file, NULL, 0);
1312 add_noreturn_fake_exit_edges ();
1313 connect_infinite_loops_to_exit ();
1314 calculate_dominance_info (CDI_DOMINATORS);
1315 calculate_dominance_info (CDI_POST_DOMINATORS);
1317 tree_bb_level_predictions ();
1319 mark_irreducible_loops (&loops_info);
1320 predict_loops (&loops_info, false);
1327 FOR_EACH_EDGE (e, ei, bb->succs)
1329 /* Predict early returns to be probable, as we've already taken
1330 care for error returns and other cases are often used for
1331 fast paths trought function. */
1332 if (e->dest == EXIT_BLOCK_PTR
1333 && TREE_CODE (last_stmt (bb)) == RETURN_EXPR
1334 && !single_pred_p (bb))
1339 FOR_EACH_EDGE (e1, ei1, bb->preds)
1340 if (!predicted_by_p (e1->src, PRED_NULL_RETURN)
1341 && !predicted_by_p (e1->src, PRED_CONST_RETURN)
1342 && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN)
1343 && !last_basic_block_p (e1->src))
1344 predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN);
1347 /* Look for block we are guarding (ie we dominate it,
1348 but it doesn't postdominate us). */
1349 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1350 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1351 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1353 block_stmt_iterator bi;
1355 /* The call heuristic claims that a guarded function call
1356 is improbable. This is because such calls are often used
1357 to signal exceptional situations such as printing error
1359 for (bi = bsi_start (e->dest); !bsi_end_p (bi);
1362 tree stmt = bsi_stmt (bi);
1363 if ((TREE_CODE (stmt) == CALL_EXPR
1364 || (TREE_CODE (stmt) == MODIFY_EXPR
1365 && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
1366 /* Constant and pure calls are hardly used to signalize
1367 something exceptional. */
1368 && TREE_SIDE_EFFECTS (stmt))
1370 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1376 tree_predict_by_opcode (bb);
1379 combine_predictions_for_bb (dump_file, bb);
1381 if (0) /* FIXME: Enable once we are pass down the profile to RTL level. */
1382 strip_builtin_expect ();
1383 estimate_bb_frequencies (&loops_info);
1384 free_dominance_info (CDI_POST_DOMINATORS);
1385 remove_fake_exit_edges ();
1386 flow_loops_free (&loops_info);
1387 if (dump_file && (dump_flags & TDF_DETAILS))
1388 dump_tree_cfg (dump_file, dump_flags);
1389 if (profile_status == PROFILE_ABSENT)
1390 profile_status = PROFILE_GUESSED;
1393 /* __builtin_expect dropped tokens into the insn stream describing expected
1394 values of registers. Generate branch probabilities based off these
1398 expected_value_to_br_prob (void)
1400 rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
1402 for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
1404 switch (GET_CODE (insn))
1407 /* Look for expected value notes. */
1408 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
1410 ev = NOTE_EXPECTED_VALUE (insn);
1411 ev_reg = XEXP (ev, 0);
1417 /* Never propagate across labels. */
1422 /* Look for simple conditional branches. If we haven't got an
1423 expected value yet, no point going further. */
1424 if (!JUMP_P (insn) || ev == NULL_RTX
1425 || ! any_condjump_p (insn))
1430 /* Look for insns that clobber the EV register. */
1431 if (ev && reg_set_p (ev_reg, insn))
1436 /* Collect the branch condition, hopefully relative to EV_REG. */
1437 /* ??? At present we'll miss things like
1438 (expected_value (eq r70 0))
1440 (set r80 (lt r70 r71))
1441 (set pc (if_then_else (ne r80 0) ...))
1442 as canonicalize_condition will render this to us as
1444 Could use cselib to try and reduce this further. */
1445 cond = XEXP (SET_SRC (pc_set (insn)), 0);
1446 cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg,
1448 if (! cond || XEXP (cond, 0) != ev_reg
1449 || GET_CODE (XEXP (cond, 1)) != CONST_INT)
1452 /* Substitute and simplify. Given that the expression we're
1453 building involves two constants, we should wind up with either
1455 cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
1456 XEXP (ev, 1), XEXP (cond, 1));
1457 cond = simplify_rtx (cond);
1459 /* Turn the condition into a scaled branch probability. */
1460 gcc_assert (cond == const_true_rtx || cond == const0_rtx);
1461 predict_insn_def (insn, PRED_BUILTIN_EXPECT,
1462 cond == const_true_rtx ? TAKEN : NOT_TAKEN);
1466 /* Check whether this is the last basic block of function. Commonly
1467 there is one extra common cleanup block. */
1469 last_basic_block_p (basic_block bb)
1471 if (bb == EXIT_BLOCK_PTR)
1474 return (bb->next_bb == EXIT_BLOCK_PTR
1475 || (bb->next_bb->next_bb == EXIT_BLOCK_PTR
1476 && single_succ_p (bb)
1477 && single_succ (bb)->next_bb == EXIT_BLOCK_PTR));
1480 /* Sets branch probabilities according to PREDiction and
1481 FLAGS. HEADS[bb->index] should be index of basic block in that we
1482 need to alter branch predictions (i.e. the first of our dominators
1483 such that we do not post-dominate it) (but we fill this information
1484 on demand, so -1 may be there in case this was not needed yet). */
1487 predict_paths_leading_to (basic_block bb, int *heads, enum br_predictor pred,
1488 enum prediction taken)
1494 if (heads[bb->index] < 0)
1496 /* This is first time we need this field in heads array; so
1497 find first dominator that we do not post-dominate (we are
1498 using already known members of heads array). */
1499 basic_block ai = bb;
1500 basic_block next_ai = get_immediate_dominator (CDI_DOMINATORS, bb);
1503 while (heads[next_ai->index] < 0)
1505 if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
1507 heads[next_ai->index] = ai->index;
1509 next_ai = get_immediate_dominator (CDI_DOMINATORS, next_ai);
1511 if (!dominated_by_p (CDI_POST_DOMINATORS, next_ai, bb))
1512 head = next_ai->index;
1514 head = heads[next_ai->index];
1515 while (next_ai != bb)
1518 if (heads[ai->index] == ENTRY_BLOCK)
1519 ai = ENTRY_BLOCK_PTR;
1521 ai = BASIC_BLOCK (heads[ai->index]);
1522 heads[next_ai->index] = head;
1525 y = heads[bb->index];
1527 /* Now find the edge that leads to our branch and aply the prediction. */
1529 if (y == last_basic_block)
1531 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (y)->succs)
1532 if (e->dest->index >= 0
1533 && dominated_by_p (CDI_POST_DOMINATORS, e->dest, bb))
1534 predict_edge_def (e, pred, taken);
1537 /* This is used to carry information about basic blocks. It is
1538 attached to the AUX field of the standard CFG block. */
1540 typedef struct block_info_def
1542 /* Estimated frequency of execution of basic_block. */
1545 /* To keep queue of basic blocks to process. */
1548 /* Number of predecessors we need to visit first. */
1552 /* Similar information for edges. */
1553 typedef struct edge_info_def
1555 /* In case edge is an loopback edge, the probability edge will be reached
1556 in case header is. Estimated number of iterations of the loop can be
1557 then computed as 1 / (1 - back_edge_prob). */
1558 sreal back_edge_prob;
1559 /* True if the edge is an loopback edge in the natural loop. */
1560 unsigned int back_edge:1;
1563 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1564 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1566 /* Helper function for estimate_bb_frequencies.
1567 Propagate the frequencies for LOOP. */
1570 propagate_freq (struct loop *loop, bitmap tovisit)
1572 basic_block head = loop->header;
1580 /* For each basic block we need to visit count number of his predecessors
1581 we need to visit first. */
1582 EXECUTE_IF_SET_IN_BITMAP (tovisit, 0, i, bi)
1587 /* The outermost "loop" includes the exit block, which we can not
1588 look up via BASIC_BLOCK. Detect this and use EXIT_BLOCK_PTR
1589 directly. Do the same for the entry block. */
1590 if (i == (unsigned)ENTRY_BLOCK)
1591 bb = ENTRY_BLOCK_PTR;
1592 else if (i == (unsigned)EXIT_BLOCK)
1593 bb = EXIT_BLOCK_PTR;
1595 bb = BASIC_BLOCK (i);
1597 FOR_EACH_EDGE (e, ei, bb->preds)
1599 bool visit = bitmap_bit_p (tovisit, e->src->index);
1601 if (visit && !(e->flags & EDGE_DFS_BACK))
1603 else if (visit && dump_file && !EDGE_INFO (e)->back_edge)
1605 "Irreducible region hit, ignoring edge to %i->%i\n",
1606 e->src->index, bb->index);
1608 BLOCK_INFO (bb)->npredecessors = count;
1611 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1613 for (bb = head; bb; bb = nextbb)
1616 sreal cyclic_probability, frequency;
1618 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1619 memcpy (&frequency, &real_zero, sizeof (real_zero));
1621 nextbb = BLOCK_INFO (bb)->next;
1622 BLOCK_INFO (bb)->next = NULL;
1624 /* Compute frequency of basic block. */
1627 #ifdef ENABLE_CHECKING
1628 FOR_EACH_EDGE (e, ei, bb->preds)
1629 gcc_assert (!bitmap_bit_p (tovisit, e->src->index)
1630 || (e->flags & EDGE_DFS_BACK));
1633 FOR_EACH_EDGE (e, ei, bb->preds)
1634 if (EDGE_INFO (e)->back_edge)
1636 sreal_add (&cyclic_probability, &cyclic_probability,
1637 &EDGE_INFO (e)->back_edge_prob);
1639 else if (!(e->flags & EDGE_DFS_BACK))
1643 /* frequency += (e->probability
1644 * BLOCK_INFO (e->src)->frequency /
1645 REG_BR_PROB_BASE); */
1647 sreal_init (&tmp, e->probability, 0);
1648 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1649 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1650 sreal_add (&frequency, &frequency, &tmp);
1653 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1655 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1656 sizeof (frequency));
1660 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
1662 memcpy (&cyclic_probability, &real_almost_one,
1663 sizeof (real_almost_one));
1666 /* BLOCK_INFO (bb)->frequency = frequency
1667 / (1 - cyclic_probability) */
1669 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
1670 sreal_div (&BLOCK_INFO (bb)->frequency,
1671 &frequency, &cyclic_probability);
1675 bitmap_clear_bit (tovisit, bb->index);
1677 e = find_edge (bb, head);
1682 /* EDGE_INFO (e)->back_edge_prob
1683 = ((e->probability * BLOCK_INFO (bb)->frequency)
1684 / REG_BR_PROB_BASE); */
1686 sreal_init (&tmp, e->probability, 0);
1687 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1688 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1689 &tmp, &real_inv_br_prob_base);
1692 /* Propagate to successor blocks. */
1693 FOR_EACH_EDGE (e, ei, bb->succs)
1694 if (!(e->flags & EDGE_DFS_BACK)
1695 && BLOCK_INFO (e->dest)->npredecessors)
1697 BLOCK_INFO (e->dest)->npredecessors--;
1698 if (!BLOCK_INFO (e->dest)->npredecessors)
1703 BLOCK_INFO (last)->next = e->dest;
1711 /* Estimate probabilities of loopback edges in loops at same nest level. */
1714 estimate_loops_at_level (struct loop *first_loop, bitmap tovisit)
1718 for (loop = first_loop; loop; loop = loop->next)
1724 estimate_loops_at_level (loop->inner, tovisit);
1726 /* Do not do this for dummy function loop. */
1727 if (EDGE_COUNT (loop->latch->succs) > 0)
1729 /* Find current loop back edge and mark it. */
1730 e = loop_latch_edge (loop);
1731 EDGE_INFO (e)->back_edge = 1;
1734 bbs = get_loop_body (loop);
1735 for (i = 0; i < loop->num_nodes; i++)
1736 bitmap_set_bit (tovisit, bbs[i]->index);
1738 propagate_freq (loop, tovisit);
1742 /* Convert counts measured by profile driven feedback to frequencies.
1743 Return nonzero iff there was any nonzero execution count. */
1746 counts_to_freqs (void)
1748 gcov_type count_max, true_count_max = 0;
1752 true_count_max = MAX (bb->count, true_count_max);
1754 count_max = MAX (true_count_max, 1);
1755 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1756 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1757 return true_count_max;
1760 /* Return true if function is likely to be expensive, so there is no point to
1761 optimize performance of prologue, epilogue or do inlining at the expense
1762 of code size growth. THRESHOLD is the limit of number of instructions
1763 function can execute at average to be still considered not expensive. */
1766 expensive_function_p (int threshold)
1768 unsigned int sum = 0;
1772 /* We can not compute accurately for large thresholds due to scaled
1774 gcc_assert (threshold <= BB_FREQ_MAX);
1776 /* Frequencies are out of range. This either means that function contains
1777 internal loop executing more than BB_FREQ_MAX times or profile feedback
1778 is available and function has not been executed at all. */
1779 if (ENTRY_BLOCK_PTR->frequency == 0)
1782 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1783 limit = ENTRY_BLOCK_PTR->frequency * threshold;
1788 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1789 insn = NEXT_INSN (insn))
1790 if (active_insn_p (insn))
1792 sum += bb->frequency;
1801 /* Estimate basic blocks frequency by given branch probabilities. */
1804 estimate_bb_frequencies (struct loops *loops)
1809 if (!flag_branch_probabilities || !counts_to_freqs ())
1811 static int real_values_initialized = 0;
1814 if (!real_values_initialized)
1816 real_values_initialized = 1;
1817 sreal_init (&real_zero, 0, 0);
1818 sreal_init (&real_one, 1, 0);
1819 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
1820 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
1821 sreal_init (&real_one_half, 1, -1);
1822 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
1823 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
1826 mark_dfs_back_edges ();
1828 single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
1830 /* Set up block info for each basic block. */
1831 tovisit = BITMAP_ALLOC (NULL);
1832 alloc_aux_for_blocks (sizeof (struct block_info_def));
1833 alloc_aux_for_edges (sizeof (struct edge_info_def));
1834 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1839 FOR_EACH_EDGE (e, ei, bb->succs)
1841 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
1842 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1843 &EDGE_INFO (e)->back_edge_prob,
1844 &real_inv_br_prob_base);
1848 /* First compute probabilities locally for each loop from innermost
1849 to outermost to examine probabilities for back edges. */
1850 estimate_loops_at_level (loops->tree_root, tovisit);
1852 memcpy (&freq_max, &real_zero, sizeof (real_zero));
1854 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
1855 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
1857 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
1858 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1862 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
1863 sreal_add (&tmp, &tmp, &real_one_half);
1864 bb->frequency = sreal_to_int (&tmp);
1867 free_aux_for_blocks ();
1868 free_aux_for_edges ();
1869 BITMAP_FREE (tovisit);
1871 compute_function_frequency ();
1872 if (flag_reorder_functions)
1873 choose_function_section ();
1876 /* Decide whether function is hot, cold or unlikely executed. */
1878 compute_function_frequency (void)
1882 if (!profile_info || !flag_branch_probabilities)
1884 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1887 if (maybe_hot_bb_p (bb))
1889 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1892 if (!probably_never_executed_bb_p (bb))
1893 cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
1897 /* Choose appropriate section for the function. */
1899 choose_function_section (void)
1901 if (DECL_SECTION_NAME (current_function_decl)
1902 || !targetm.have_named_sections
1903 /* Theoretically we can split the gnu.linkonce text section too,
1904 but this requires more work as the frequency needs to match
1905 for all generated objects so we need to merge the frequency
1906 of all instances. For now just never set frequency for these. */
1907 || DECL_ONE_ONLY (current_function_decl))
1910 /* If we are doing the partitioning optimization, let the optimization
1911 choose the correct section into which to put things. */
1913 if (flag_reorder_blocks_and_partition)
1916 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
1917 DECL_SECTION_NAME (current_function_decl) =
1918 build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
1919 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
1920 DECL_SECTION_NAME (current_function_decl) =
1921 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
1922 UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
1926 struct tree_opt_pass pass_profile =
1928 "profile", /* name */
1930 tree_estimate_probability, /* execute */
1933 0, /* static_pass_number */
1934 TV_BRANCH_PROB, /* tv_id */
1935 PROP_cfg, /* properties_required */
1936 0, /* properties_provided */
1937 0, /* properties_destroyed */
1938 0, /* todo_flags_start */
1939 TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */