1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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"
56 #include "tree-flow.h"
58 #include "tree-dump.h"
59 #include "tree-pass.h"
62 /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
63 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
64 static sreal real_zero, real_one, real_almost_one, real_br_prob_base,
65 real_inv_br_prob_base, real_one_half, real_bb_freq_max;
67 /* Random guesstimation given names. */
68 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
69 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
70 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
71 #define PROB_ALWAYS (REG_BR_PROB_BASE)
73 static void combine_predictions_for_insn (rtx, basic_block);
74 static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
75 static void estimate_loops_at_level (struct loop *loop);
76 static void propagate_freq (struct loop *);
77 static void estimate_bb_frequencies (struct loops *);
78 static int counts_to_freqs (void);
79 static bool last_basic_block_p (basic_block);
80 static void compute_function_frequency (void);
81 static void choose_function_section (void);
82 static bool can_predict_insn_p (rtx);
84 /* Information we hold about each branch predictor.
85 Filled using information from predict.def. */
89 const char *const name; /* Name used in the debugging dumps. */
90 const int hitrate; /* Expected hitrate used by
91 predict_insn_def call. */
95 /* Use given predictor without Dempster-Shaffer theory if it matches
96 using first_match heuristics. */
97 #define PRED_FLAG_FIRST_MATCH 1
99 /* Recompute hitrate in percent to our representation. */
101 #define HITRATE(VAL) ((int) ((VAL) * REG_BR_PROB_BASE + 50) / 100)
103 #define DEF_PREDICTOR(ENUM, NAME, HITRATE, FLAGS) {NAME, HITRATE, FLAGS},
104 static const struct predictor_info predictor_info[]= {
105 #include "predict.def"
107 /* Upper bound on predictors. */
112 /* Return true in case BB can be CPU intensive and should be optimized
113 for maximal performance. */
116 maybe_hot_bb_p (basic_block bb)
118 if (profile_info && flag_branch_probabilities
120 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
122 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
127 /* Return true in case BB is cold and should be optimized for size. */
130 probably_cold_bb_p (basic_block bb)
132 if (profile_info && flag_branch_probabilities
134 < profile_info->sum_max / PARAM_VALUE (HOT_BB_COUNT_FRACTION)))
136 if (bb->frequency < BB_FREQ_MAX / PARAM_VALUE (HOT_BB_FREQUENCY_FRACTION))
141 /* Return true in case BB is probably never executed. */
143 probably_never_executed_bb_p (basic_block bb)
145 if (profile_info && flag_branch_probabilities)
146 return ((bb->count + profile_info->runs / 2) / profile_info->runs) == 0;
150 /* Return true if the one of outgoing edges is already predicted by
154 rtl_predicted_by_p (basic_block bb, enum br_predictor predictor)
157 if (!INSN_P (BB_END (bb)))
159 for (note = REG_NOTES (BB_END (bb)); note; note = XEXP (note, 1))
160 if (REG_NOTE_KIND (note) == REG_BR_PRED
161 && INTVAL (XEXP (XEXP (note, 0), 0)) == (int)predictor)
166 /* Return true if the one of outgoing edges is already predicted by
170 tree_predicted_by_p (basic_block bb, enum br_predictor predictor)
172 struct edge_prediction *i = bb_ann (bb)->predictions;
173 for (i = bb_ann (bb)->predictions; i; i = i->next)
174 if (i->predictor == predictor)
180 predict_insn (rtx insn, enum br_predictor predictor, int probability)
182 gcc_assert (any_condjump_p (insn));
183 if (!flag_guess_branch_prob)
187 = gen_rtx_EXPR_LIST (REG_BR_PRED,
188 gen_rtx_CONCAT (VOIDmode,
189 GEN_INT ((int) predictor),
190 GEN_INT ((int) probability)),
194 /* Predict insn by given predictor. */
197 predict_insn_def (rtx insn, enum br_predictor predictor,
198 enum prediction taken)
200 int probability = predictor_info[(int) predictor].hitrate;
203 probability = REG_BR_PROB_BASE - probability;
205 predict_insn (insn, predictor, probability);
208 /* Predict edge E with given probability if possible. */
211 rtl_predict_edge (edge e, enum br_predictor predictor, int probability)
214 last_insn = BB_END (e->src);
216 /* We can store the branch prediction information only about
217 conditional jumps. */
218 if (!any_condjump_p (last_insn))
221 /* We always store probability of branching. */
222 if (e->flags & EDGE_FALLTHRU)
223 probability = REG_BR_PROB_BASE - probability;
225 predict_insn (last_insn, predictor, probability);
228 /* Predict edge E with the given PROBABILITY. */
230 tree_predict_edge (edge e, enum br_predictor predictor, int probability)
232 struct edge_prediction *i = ggc_alloc (sizeof (struct edge_prediction));
234 i->next = bb_ann (e->src)->predictions;
235 bb_ann (e->src)->predictions = i;
236 i->probability = probability;
237 i->predictor = predictor;
241 /* Return true when we can store prediction on insn INSN.
242 At the moment we represent predictions only on conditional
243 jumps, not at computed jump or other complicated cases. */
245 can_predict_insn_p (rtx insn)
247 return (JUMP_P (insn)
248 && any_condjump_p (insn)
249 && BLOCK_FOR_INSN (insn)->succ->succ_next);
252 /* Predict edge E by given predictor if possible. */
255 predict_edge_def (edge e, enum br_predictor predictor,
256 enum prediction taken)
258 int probability = predictor_info[(int) predictor].hitrate;
261 probability = REG_BR_PROB_BASE - probability;
263 predict_edge (e, predictor, probability);
266 /* Invert all branch predictions or probability notes in the INSN. This needs
267 to be done each time we invert the condition used by the jump. */
270 invert_br_probabilities (rtx insn)
274 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
275 if (REG_NOTE_KIND (note) == REG_BR_PROB)
276 XEXP (note, 0) = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (note, 0)));
277 else if (REG_NOTE_KIND (note) == REG_BR_PRED)
278 XEXP (XEXP (note, 0), 1)
279 = GEN_INT (REG_BR_PROB_BASE - INTVAL (XEXP (XEXP (note, 0), 1)));
282 /* Dump information about the branch prediction to the output file. */
285 dump_prediction (FILE *file, enum br_predictor predictor, int probability,
286 basic_block bb, int used)
293 while (e && (e->flags & EDGE_FALLTHRU))
296 fprintf (file, " %s heuristics%s: %.1f%%",
297 predictor_info[predictor].name,
298 used ? "" : " (ignored)", probability * 100.0 / REG_BR_PROB_BASE);
302 fprintf (file, " exec ");
303 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
306 fprintf (file, " hit ");
307 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
308 fprintf (file, " (%.1f%%)", e->count * 100.0 / bb->count);
312 fprintf (file, "\n");
315 /* We can not predict the probabilities of outgoing edges of bb. Set them
316 evenly and hope for the best. */
318 set_even_probabilities (basic_block bb)
323 for (e = bb->succ; e; e = e->succ_next)
324 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
326 for (e = bb->succ; e; e = e->succ_next)
327 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
328 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
333 /* Combine all REG_BR_PRED notes into single probability and attach REG_BR_PROB
334 note if not already present. Remove now useless REG_BR_PRED notes. */
337 combine_predictions_for_insn (rtx insn, basic_block bb)
342 int best_probability = PROB_EVEN;
343 int best_predictor = END_PREDICTORS;
344 int combined_probability = REG_BR_PROB_BASE / 2;
346 bool first_match = false;
349 if (!can_predict_insn_p (insn))
351 set_even_probabilities (bb);
355 prob_note = find_reg_note (insn, REG_BR_PROB, 0);
356 pnote = ®_NOTES (insn);
358 fprintf (dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn),
361 /* We implement "first match" heuristics and use probability guessed
362 by predictor with smallest index. */
363 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
364 if (REG_NOTE_KIND (note) == REG_BR_PRED)
366 int predictor = INTVAL (XEXP (XEXP (note, 0), 0));
367 int probability = INTVAL (XEXP (XEXP (note, 0), 1));
370 if (best_predictor > predictor)
371 best_probability = probability, best_predictor = predictor;
373 d = (combined_probability * probability
374 + (REG_BR_PROB_BASE - combined_probability)
375 * (REG_BR_PROB_BASE - probability));
377 /* Use FP math to avoid overflows of 32bit integers. */
379 /* If one probability is 0% and one 100%, avoid division by zero. */
380 combined_probability = REG_BR_PROB_BASE / 2;
382 combined_probability = (((double) combined_probability) * probability
383 * REG_BR_PROB_BASE / d + 0.5);
386 /* Decide which heuristic to use. In case we didn't match anything,
387 use no_prediction heuristic, in case we did match, use either
388 first match or Dempster-Shaffer theory depending on the flags. */
390 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
394 dump_prediction (dump_file, PRED_NO_PREDICTION,
395 combined_probability, bb, true);
398 dump_prediction (dump_file, PRED_DS_THEORY, combined_probability,
400 dump_prediction (dump_file, PRED_FIRST_MATCH, best_probability,
405 combined_probability = best_probability;
406 dump_prediction (dump_file, PRED_COMBINED, combined_probability, bb, true);
410 if (REG_NOTE_KIND (*pnote) == REG_BR_PRED)
412 int predictor = INTVAL (XEXP (XEXP (*pnote, 0), 0));
413 int probability = INTVAL (XEXP (XEXP (*pnote, 0), 1));
415 dump_prediction (dump_file, predictor, probability, bb,
416 !first_match || best_predictor == predictor);
417 *pnote = XEXP (*pnote, 1);
420 pnote = &XEXP (*pnote, 1);
426 = gen_rtx_EXPR_LIST (REG_BR_PROB,
427 GEN_INT (combined_probability), REG_NOTES (insn));
429 /* Save the prediction into CFG in case we are seeing non-degenerated
431 if (bb->succ->succ_next)
433 BRANCH_EDGE (bb)->probability = combined_probability;
434 FALLTHRU_EDGE (bb)->probability
435 = REG_BR_PROB_BASE - combined_probability;
440 /* Combine predictions into single probability and store them into CFG.
441 Remove now useless prediction entries. */
444 combine_predictions_for_bb (FILE *file, basic_block bb)
446 int best_probability = PROB_EVEN;
447 int best_predictor = END_PREDICTORS;
448 int combined_probability = REG_BR_PROB_BASE / 2;
450 bool first_match = false;
452 struct edge_prediction *pred;
454 edge e, first = NULL, second = NULL;
456 for (e = bb->succ; e; e = e->succ_next)
457 if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
460 if (first && !second)
466 /* When there is no successor or only one choice, prediction is easy.
468 We are lazy for now and predict only basic blocks with two outgoing
469 edges. It is possible to predict generic case too, but we have to
470 ignore first match heuristics and do more involved combining. Implement
475 set_even_probabilities (bb);
476 bb_ann (bb)->predictions = NULL;
478 fprintf (file, "%i edges in bb %i predicted to even probabilities\n",
484 fprintf (file, "Predictions for bb %i\n", bb->index);
486 /* We implement "first match" heuristics and use probability guessed
487 by predictor with smallest index. */
488 for (pred = bb_ann (bb)->predictions; pred; pred = pred->next)
490 int predictor = pred->predictor;
491 int probability = pred->probability;
493 if (pred->edge != first)
494 probability = REG_BR_PROB_BASE - probability;
497 if (best_predictor > predictor)
498 best_probability = probability, best_predictor = predictor;
500 d = (combined_probability * probability
501 + (REG_BR_PROB_BASE - combined_probability)
502 * (REG_BR_PROB_BASE - probability));
504 /* Use FP math to avoid overflows of 32bit integers. */
506 /* If one probability is 0% and one 100%, avoid division by zero. */
507 combined_probability = REG_BR_PROB_BASE / 2;
509 combined_probability = (((double) combined_probability) * probability
510 * REG_BR_PROB_BASE / d + 0.5);
513 /* Decide which heuristic to use. In case we didn't match anything,
514 use no_prediction heuristic, in case we did match, use either
515 first match or Dempster-Shaffer theory depending on the flags. */
517 if (predictor_info [best_predictor].flags & PRED_FLAG_FIRST_MATCH)
521 dump_prediction (file, PRED_NO_PREDICTION, combined_probability, bb, true);
524 dump_prediction (file, PRED_DS_THEORY, combined_probability, bb,
526 dump_prediction (file, PRED_FIRST_MATCH, best_probability, bb,
531 combined_probability = best_probability;
532 dump_prediction (file, PRED_COMBINED, combined_probability, bb, true);
534 for (pred = bb_ann (bb)->predictions; pred; pred = pred->next)
536 int predictor = pred->predictor;
537 int probability = pred->probability;
539 if (pred->edge != bb->succ)
540 probability = REG_BR_PROB_BASE - probability;
541 dump_prediction (file, predictor, probability, bb,
542 !first_match || best_predictor == predictor);
544 bb_ann (bb)->predictions = NULL;
548 first->probability = combined_probability;
549 second->probability = REG_BR_PROB_BASE - combined_probability;
553 /* Predict edge probabilities by exploiting loop structure.
554 When SIMPLELOOPS is set, attempt to count number of iterations by analyzing
557 predict_loops (struct loops *loops_info, bool simpleloops)
561 /* Try to predict out blocks in a loop that are not part of a
563 for (i = 1; i < loops_info->num; i++)
565 basic_block bb, *bbs;
568 struct loop *loop = loops_info->parray[i];
569 struct niter_desc desc;
570 unsigned HOST_WIDE_INT niter;
572 flow_loop_scan (loop, LOOP_EXIT_EDGES);
573 exits = loop->num_exits;
577 iv_analysis_loop_init (loop);
578 find_simple_exit (loop, &desc);
580 if (desc.simple_p && desc.const_iter)
583 niter = desc.niter + 1;
584 if (niter == 0) /* We might overflow here. */
587 prob = (REG_BR_PROB_BASE
588 - (REG_BR_PROB_BASE + niter /2) / niter);
589 /* Branch prediction algorithm gives 0 frequency for everything
590 after the end of loop for loop having 0 probability to finish. */
591 if (prob == REG_BR_PROB_BASE)
592 prob = REG_BR_PROB_BASE - 1;
593 predict_edge (desc.in_edge, PRED_LOOP_ITERATIONS,
598 bbs = get_loop_body (loop);
600 for (j = 0; j < loop->num_nodes; j++)
602 int header_found = 0;
607 /* Bypass loop heuristics on continue statement. These
608 statements construct loops via "non-loop" constructs
609 in the source language and are better to be handled
611 if ((simpleloops && !can_predict_insn_p (BB_END (bb)))
612 || predicted_by_p (bb, PRED_CONTINUE))
615 /* Loop branch heuristics - predict an edge back to a
616 loop's head as taken. */
617 for (e = bb->succ; e; e = e->succ_next)
618 if (e->dest == loop->header
619 && e->src == loop->latch)
622 predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
625 /* Loop exit heuristics - predict an edge exiting the loop if the
626 conditional has no loop header successors as not taken. */
628 for (e = bb->succ; e; e = e->succ_next)
629 if (e->dest->index < 0
630 || !flow_bb_inside_loop_p (loop, e->dest))
634 - predictor_info [(int) PRED_LOOP_EXIT].hitrate)
638 /* Free basic blocks from get_loop_body. */
643 /* Attempt to predict probabilities of BB outgoing edges using local
646 bb_estimate_probability_locally (basic_block bb)
648 rtx last_insn = BB_END (bb);
651 if (! can_predict_insn_p (last_insn))
653 cond = get_condition (last_insn, NULL, false, false);
657 /* Try "pointer heuristic."
658 A comparison ptr == 0 is predicted as false.
659 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
660 if (COMPARISON_P (cond)
661 && ((REG_P (XEXP (cond, 0)) && REG_POINTER (XEXP (cond, 0)))
662 || (REG_P (XEXP (cond, 1)) && REG_POINTER (XEXP (cond, 1)))))
664 if (GET_CODE (cond) == EQ)
665 predict_insn_def (last_insn, PRED_POINTER, NOT_TAKEN);
666 else if (GET_CODE (cond) == NE)
667 predict_insn_def (last_insn, PRED_POINTER, TAKEN);
671 /* Try "opcode heuristic."
672 EQ tests are usually false and NE tests are usually true. Also,
673 most quantities are positive, so we can make the appropriate guesses
674 about signed comparisons against zero. */
675 switch (GET_CODE (cond))
678 /* Unconditional branch. */
679 predict_insn_def (last_insn, PRED_UNCONDITIONAL,
680 cond == const0_rtx ? NOT_TAKEN : TAKEN);
685 /* Floating point comparisons appears to behave in a very
686 unpredictable way because of special role of = tests in
688 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
690 /* Comparisons with 0 are often used for booleans and there is
691 nothing useful to predict about them. */
692 else if (XEXP (cond, 1) == const0_rtx
693 || XEXP (cond, 0) == const0_rtx)
696 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, NOT_TAKEN);
701 /* Floating point comparisons appears to behave in a very
702 unpredictable way because of special role of = tests in
704 if (FLOAT_MODE_P (GET_MODE (XEXP (cond, 0))))
706 /* Comparisons with 0 are often used for booleans and there is
707 nothing useful to predict about them. */
708 else if (XEXP (cond, 1) == const0_rtx
709 || XEXP (cond, 0) == const0_rtx)
712 predict_insn_def (last_insn, PRED_OPCODE_NONEQUAL, TAKEN);
716 predict_insn_def (last_insn, PRED_FPOPCODE, TAKEN);
720 predict_insn_def (last_insn, PRED_FPOPCODE, NOT_TAKEN);
725 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
726 || XEXP (cond, 1) == constm1_rtx)
727 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, NOT_TAKEN);
732 if (XEXP (cond, 1) == const0_rtx || XEXP (cond, 1) == const1_rtx
733 || XEXP (cond, 1) == constm1_rtx)
734 predict_insn_def (last_insn, PRED_OPCODE_POSITIVE, TAKEN);
742 /* Statically estimate the probability that a branch will be taken and produce
743 estimated profile. When profile feedback is present never executed portions
744 of function gets estimated. */
747 estimate_probability (struct loops *loops_info)
751 connect_infinite_loops_to_exit ();
752 calculate_dominance_info (CDI_DOMINATORS);
753 calculate_dominance_info (CDI_POST_DOMINATORS);
755 predict_loops (loops_info, true);
759 /* Attempt to predict conditional jumps using a number of heuristics. */
762 rtx last_insn = BB_END (bb);
765 if (! can_predict_insn_p (last_insn))
768 for (e = bb->succ; e; e = e->succ_next)
770 /* Predict early returns to be probable, as we've already taken
771 care for error returns and other are often used for fast paths
773 if ((e->dest == EXIT_BLOCK_PTR
774 || (e->dest->succ && !e->dest->succ->succ_next
775 && e->dest->succ->dest == EXIT_BLOCK_PTR))
776 && !predicted_by_p (bb, PRED_NULL_RETURN)
777 && !predicted_by_p (bb, PRED_CONST_RETURN)
778 && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
779 && !last_basic_block_p (e->dest))
780 predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
782 /* Look for block we are guarding (ie we dominate it,
783 but it doesn't postdominate us). */
784 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
785 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
786 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
790 /* The call heuristic claims that a guarded function call
791 is improbable. This is because such calls are often used
792 to signal exceptional situations such as printing error
794 for (insn = BB_HEAD (e->dest); insn != NEXT_INSN (BB_END (e->dest));
795 insn = NEXT_INSN (insn))
797 /* Constant and pure calls are hardly used to signalize
798 something exceptional. */
799 && ! CONST_OR_PURE_CALL_P (insn))
801 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
806 bb_estimate_probability_locally (bb);
809 /* Attach the combined probability to each conditional jump. */
811 if (JUMP_P (BB_END (bb))
812 && any_condjump_p (BB_END (bb))
813 && bb->succ->succ_next != NULL)
814 combine_predictions_for_insn (BB_END (bb), bb);
816 remove_fake_exit_edges ();
817 /* Fill in the probability values in flowgraph based on the REG_BR_PROB
821 rtx last_insn = BB_END (bb);
823 if (!can_predict_insn_p (last_insn))
825 /* We can predict only conditional jumps at the moment.
826 Expect each edge to be equally probable.
827 ?? In the future we want to make abnormal edges improbable. */
831 for (e = bb->succ; e; e = e->succ_next)
834 if (e->probability != 0)
838 for (e = bb->succ; e; e = e->succ_next)
839 e->probability = (REG_BR_PROB_BASE + nedges / 2) / nedges;
842 estimate_bb_frequencies (loops_info);
843 free_dominance_info (CDI_POST_DOMINATORS);
844 if (profile_status == PROFILE_ABSENT)
845 profile_status = PROFILE_GUESSED;
848 /* Set edge->probability for each successor edge of BB. */
850 guess_outgoing_edge_probabilities (basic_block bb)
852 bb_estimate_probability_locally (bb);
853 combine_predictions_for_insn (BB_END (bb), bb);
857 /* Predict using opcode of the last statement in basic block. */
859 tree_predict_by_opcode (basic_block bb)
861 tree stmt = last_stmt (bb);
867 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
869 for (then_edge = bb->succ; then_edge; then_edge = then_edge->succ_next)
870 if (then_edge->flags & EDGE_TRUE_VALUE)
872 cond = TREE_OPERAND (stmt, 0);
873 if (TREE_CODE_CLASS (TREE_CODE (cond)) != '<')
875 op0 = TREE_OPERAND (cond, 0);
876 type = TREE_TYPE (op0);
877 /* Try "pointer heuristic."
878 A comparison ptr == 0 is predicted as false.
879 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
880 if (POINTER_TYPE_P (type))
882 if (TREE_CODE (cond) == EQ_EXPR)
883 predict_edge_def (then_edge, PRED_TREE_POINTER, NOT_TAKEN);
884 else if (TREE_CODE (cond) == NE_EXPR)
885 predict_edge_def (then_edge, PRED_TREE_POINTER, TAKEN);
889 /* Try "opcode heuristic."
890 EQ tests are usually false and NE tests are usually true. Also,
891 most quantities are positive, so we can make the appropriate guesses
892 about signed comparisons against zero. */
893 switch (TREE_CODE (cond))
897 /* Floating point comparisons appears to behave in a very
898 unpredictable way because of special role of = tests in
900 if (FLOAT_TYPE_P (type))
902 /* Comparisons with 0 are often used for booleans and there is
903 nothing useful to predict about them. */
904 else if (integer_zerop (op0)
905 || integer_zerop (TREE_OPERAND (cond, 1)))
908 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, NOT_TAKEN);
913 /* Floating point comparisons appears to behave in a very
914 unpredictable way because of special role of = tests in
916 if (FLOAT_TYPE_P (type))
918 /* Comparisons with 0 are often used for booleans and there is
919 nothing useful to predict about them. */
920 else if (integer_zerop (op0)
921 || integer_zerop (TREE_OPERAND (cond, 1)))
924 predict_edge_def (then_edge, PRED_TREE_OPCODE_NONEQUAL, TAKEN);
928 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, TAKEN);
932 predict_edge_def (then_edge, PRED_TREE_FPOPCODE, NOT_TAKEN);
937 if (integer_zerop (TREE_OPERAND (cond, 1))
938 || integer_onep (TREE_OPERAND (cond, 1))
939 || integer_all_onesp (TREE_OPERAND (cond, 1))
940 || real_zerop (TREE_OPERAND (cond, 1))
941 || real_onep (TREE_OPERAND (cond, 1))
942 || real_minus_onep (TREE_OPERAND (cond, 1)))
943 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, NOT_TAKEN);
948 if (integer_zerop (TREE_OPERAND (cond, 1))
949 || integer_onep (TREE_OPERAND (cond, 1))
950 || integer_all_onesp (TREE_OPERAND (cond, 1))
951 || real_zerop (TREE_OPERAND (cond, 1))
952 || real_onep (TREE_OPERAND (cond, 1))
953 || real_minus_onep (TREE_OPERAND (cond, 1)))
954 predict_edge_def (then_edge, PRED_TREE_OPCODE_POSITIVE, TAKEN);
962 /* Predict branch probabilities and estimate profile of the tree CFG. */
964 tree_estimate_probability (void)
967 struct loops loops_info;
969 flow_loops_find (&loops_info, LOOP_TREE);
970 if (dump_file && (dump_flags & TDF_DETAILS))
971 flow_loops_dump (&loops_info, dump_file, NULL, 0);
973 connect_infinite_loops_to_exit ();
974 calculate_dominance_info (CDI_DOMINATORS);
975 calculate_dominance_info (CDI_POST_DOMINATORS);
977 predict_loops (&loops_info, false);
983 for (e = bb->succ; e; e = e->succ_next)
985 /* Predict early returns to be probable, as we've already taken
986 care for error returns and other are often used for fast paths
988 if ((e->dest == EXIT_BLOCK_PTR
989 || (e->dest->succ && !e->dest->succ->succ_next
990 && e->dest->succ->dest == EXIT_BLOCK_PTR))
991 && !predicted_by_p (bb, PRED_NULL_RETURN)
992 && !predicted_by_p (bb, PRED_CONST_RETURN)
993 && !predicted_by_p (bb, PRED_NEGATIVE_RETURN)
994 && !last_basic_block_p (e->dest))
995 predict_edge_def (e, PRED_EARLY_RETURN, TAKEN);
997 /* Look for block we are guarding (ie we dominate it,
998 but it doesn't postdominate us). */
999 if (e->dest != EXIT_BLOCK_PTR && e->dest != bb
1000 && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
1001 && !dominated_by_p (CDI_POST_DOMINATORS, e->src, e->dest))
1003 block_stmt_iterator bi;
1005 /* The call heuristic claims that a guarded function call
1006 is improbable. This is because such calls are often used
1007 to signal exceptional situations such as printing error
1009 for (bi = bsi_start (e->dest); !bsi_end_p (bi);
1012 tree stmt = bsi_stmt (bi);
1013 if ((TREE_CODE (stmt) == CALL_EXPR
1014 || (TREE_CODE (stmt) == MODIFY_EXPR
1015 && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
1016 /* Constant and pure calls are hardly used to signalize
1017 something exceptional. */
1018 && TREE_SIDE_EFFECTS (stmt))
1020 predict_edge_def (e, PRED_CALL, NOT_TAKEN);
1026 tree_predict_by_opcode (bb);
1029 combine_predictions_for_bb (dump_file, bb);
1031 estimate_bb_frequencies (&loops_info);
1032 free_dominance_info (CDI_POST_DOMINATORS);
1033 remove_fake_exit_edges ();
1034 flow_loops_free (&loops_info);
1035 if (dump_file && (dump_flags & TDF_DETAILS))
1036 dump_tree_cfg (dump_file, dump_flags);
1037 if (profile_status == PROFILE_ABSENT)
1038 profile_status = PROFILE_GUESSED;
1041 /* __builtin_expect dropped tokens into the insn stream describing expected
1042 values of registers. Generate branch probabilities based off these
1046 expected_value_to_br_prob (void)
1048 rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
1050 for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
1052 switch (GET_CODE (insn))
1055 /* Look for expected value notes. */
1056 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
1058 ev = NOTE_EXPECTED_VALUE (insn);
1059 ev_reg = XEXP (ev, 0);
1065 /* Never propagate across labels. */
1070 /* Look for simple conditional branches. If we haven't got an
1071 expected value yet, no point going further. */
1072 if (!JUMP_P (insn) || ev == NULL_RTX
1073 || ! any_condjump_p (insn))
1078 /* Look for insns that clobber the EV register. */
1079 if (ev && reg_set_p (ev_reg, insn))
1084 /* Collect the branch condition, hopefully relative to EV_REG. */
1085 /* ??? At present we'll miss things like
1086 (expected_value (eq r70 0))
1088 (set r80 (lt r70 r71))
1089 (set pc (if_then_else (ne r80 0) ...))
1090 as canonicalize_condition will render this to us as
1092 Could use cselib to try and reduce this further. */
1093 cond = XEXP (SET_SRC (pc_set (insn)), 0);
1094 cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg,
1096 if (! cond || XEXP (cond, 0) != ev_reg
1097 || GET_CODE (XEXP (cond, 1)) != CONST_INT)
1100 /* Substitute and simplify. Given that the expression we're
1101 building involves two constants, we should wind up with either
1103 cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
1104 XEXP (ev, 1), XEXP (cond, 1));
1105 cond = simplify_rtx (cond);
1107 /* Turn the condition into a scaled branch probability. */
1108 gcc_assert (cond == const_true_rtx || cond == const0_rtx);
1109 predict_insn_def (insn, PRED_BUILTIN_EXPECT,
1110 cond == const_true_rtx ? TAKEN : NOT_TAKEN);
1114 /* Check whether this is the last basic block of function. Commonly
1115 there is one extra common cleanup block. */
1117 last_basic_block_p (basic_block bb)
1119 if (bb == EXIT_BLOCK_PTR)
1122 return (bb->next_bb == EXIT_BLOCK_PTR
1123 || (bb->next_bb->next_bb == EXIT_BLOCK_PTR
1124 && bb->succ && !bb->succ->succ_next
1125 && bb->succ->dest->next_bb == EXIT_BLOCK_PTR));
1128 /* This is used to carry information about basic blocks. It is
1129 attached to the AUX field of the standard CFG block. */
1131 typedef struct block_info_def
1133 /* Estimated frequency of execution of basic_block. */
1136 /* To keep queue of basic blocks to process. */
1139 /* True if block needs to be visited in propagate_freq. */
1140 unsigned int tovisit:1;
1142 /* Number of predecessors we need to visit first. */
1146 /* Similar information for edges. */
1147 typedef struct edge_info_def
1149 /* In case edge is an loopback edge, the probability edge will be reached
1150 in case header is. Estimated number of iterations of the loop can be
1151 then computed as 1 / (1 - back_edge_prob). */
1152 sreal back_edge_prob;
1153 /* True if the edge is an loopback edge in the natural loop. */
1154 unsigned int back_edge:1;
1157 #define BLOCK_INFO(B) ((block_info) (B)->aux)
1158 #define EDGE_INFO(E) ((edge_info) (E)->aux)
1160 /* Helper function for estimate_bb_frequencies.
1161 Propagate the frequencies for LOOP. */
1164 propagate_freq (struct loop *loop)
1166 basic_block head = loop->header;
1172 /* For each basic block we need to visit count number of his predecessors
1173 we need to visit first. */
1174 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1176 if (BLOCK_INFO (bb)->tovisit)
1180 for (e = bb->pred; e; e = e->pred_next)
1181 if (BLOCK_INFO (e->src)->tovisit && !(e->flags & EDGE_DFS_BACK))
1183 else if (BLOCK_INFO (e->src)->tovisit
1184 && dump_file && !EDGE_INFO (e)->back_edge)
1186 "Irreducible region hit, ignoring edge to %i->%i\n",
1187 e->src->index, bb->index);
1188 BLOCK_INFO (bb)->npredecessors = count;
1192 memcpy (&BLOCK_INFO (head)->frequency, &real_one, sizeof (real_one));
1194 for (bb = head; bb; bb = nextbb)
1196 sreal cyclic_probability, frequency;
1198 memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
1199 memcpy (&frequency, &real_zero, sizeof (real_zero));
1201 nextbb = BLOCK_INFO (bb)->next;
1202 BLOCK_INFO (bb)->next = NULL;
1204 /* Compute frequency of basic block. */
1207 #ifdef ENABLE_CHECKING
1208 for (e = bb->pred; e; e = e->pred_next)
1209 gcc_assert (!BLOCK_INFO (e->src)->tovisit
1210 || (e->flags & EDGE_DFS_BACK));
1213 for (e = bb->pred; e; e = e->pred_next)
1214 if (EDGE_INFO (e)->back_edge)
1216 sreal_add (&cyclic_probability, &cyclic_probability,
1217 &EDGE_INFO (e)->back_edge_prob);
1219 else if (!(e->flags & EDGE_DFS_BACK))
1223 /* frequency += (e->probability
1224 * BLOCK_INFO (e->src)->frequency /
1225 REG_BR_PROB_BASE); */
1227 sreal_init (&tmp, e->probability, 0);
1228 sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
1229 sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
1230 sreal_add (&frequency, &frequency, &tmp);
1233 if (sreal_compare (&cyclic_probability, &real_zero) == 0)
1235 memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
1236 sizeof (frequency));
1240 if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
1242 memcpy (&cyclic_probability, &real_almost_one,
1243 sizeof (real_almost_one));
1246 /* BLOCK_INFO (bb)->frequency = frequency
1247 / (1 - cyclic_probability) */
1249 sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
1250 sreal_div (&BLOCK_INFO (bb)->frequency,
1251 &frequency, &cyclic_probability);
1255 BLOCK_INFO (bb)->tovisit = 0;
1257 /* Compute back edge frequencies. */
1258 for (e = bb->succ; e; e = e->succ_next)
1259 if (e->dest == head)
1263 /* EDGE_INFO (e)->back_edge_prob
1264 = ((e->probability * BLOCK_INFO (bb)->frequency)
1265 / REG_BR_PROB_BASE); */
1267 sreal_init (&tmp, e->probability, 0);
1268 sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
1269 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1270 &tmp, &real_inv_br_prob_base);
1273 /* Propagate to successor blocks. */
1274 for (e = bb->succ; e; e = e->succ_next)
1275 if (!(e->flags & EDGE_DFS_BACK)
1276 && BLOCK_INFO (e->dest)->npredecessors)
1278 BLOCK_INFO (e->dest)->npredecessors--;
1279 if (!BLOCK_INFO (e->dest)->npredecessors)
1284 BLOCK_INFO (last)->next = e->dest;
1292 /* Estimate probabilities of loopback edges in loops at same nest level. */
1295 estimate_loops_at_level (struct loop *first_loop)
1299 for (loop = first_loop; loop; loop = loop->next)
1305 estimate_loops_at_level (loop->inner);
1307 if (loop->latch->succ) /* Do not do this for dummy function loop. */
1309 /* Find current loop back edge and mark it. */
1310 e = loop_latch_edge (loop);
1311 EDGE_INFO (e)->back_edge = 1;
1314 bbs = get_loop_body (loop);
1315 for (i = 0; i < loop->num_nodes; i++)
1316 BLOCK_INFO (bbs[i])->tovisit = 1;
1318 propagate_freq (loop);
1322 /* Convert counts measured by profile driven feedback to frequencies.
1323 Return nonzero iff there was any nonzero execution count. */
1326 counts_to_freqs (void)
1328 gcov_type count_max, true_count_max = 0;
1332 true_count_max = MAX (bb->count, true_count_max);
1334 count_max = MAX (true_count_max, 1);
1335 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1336 bb->frequency = (bb->count * BB_FREQ_MAX + count_max / 2) / count_max;
1337 return true_count_max;
1340 /* Return true if function is likely to be expensive, so there is no point to
1341 optimize performance of prologue, epilogue or do inlining at the expense
1342 of code size growth. THRESHOLD is the limit of number of instructions
1343 function can execute at average to be still considered not expensive. */
1346 expensive_function_p (int threshold)
1348 unsigned int sum = 0;
1352 /* We can not compute accurately for large thresholds due to scaled
1354 gcc_assert (threshold < BB_FREQ_MAX);
1356 /* Frequencies are out of range. This either means that function contains
1357 internal loop executing more than BB_FREQ_MAX times or profile feedback
1358 is available and function has not been executed at all. */
1359 if (ENTRY_BLOCK_PTR->frequency == 0)
1362 /* Maximally BB_FREQ_MAX^2 so overflow won't happen. */
1363 limit = ENTRY_BLOCK_PTR->frequency * threshold;
1368 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1369 insn = NEXT_INSN (insn))
1370 if (active_insn_p (insn))
1372 sum += bb->frequency;
1381 /* Estimate basic blocks frequency by given branch probabilities. */
1384 estimate_bb_frequencies (struct loops *loops)
1389 if (!flag_branch_probabilities || !counts_to_freqs ())
1391 static int real_values_initialized = 0;
1393 if (!real_values_initialized)
1395 real_values_initialized = 1;
1396 sreal_init (&real_zero, 0, 0);
1397 sreal_init (&real_one, 1, 0);
1398 sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
1399 sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
1400 sreal_init (&real_one_half, 1, -1);
1401 sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
1402 sreal_sub (&real_almost_one, &real_one, &real_inv_br_prob_base);
1405 mark_dfs_back_edges ();
1407 ENTRY_BLOCK_PTR->succ->probability = REG_BR_PROB_BASE;
1409 /* Set up block info for each basic block. */
1410 alloc_aux_for_blocks (sizeof (struct block_info_def));
1411 alloc_aux_for_edges (sizeof (struct edge_info_def));
1412 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1416 BLOCK_INFO (bb)->tovisit = 0;
1417 for (e = bb->succ; e; e = e->succ_next)
1419 sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
1420 sreal_mul (&EDGE_INFO (e)->back_edge_prob,
1421 &EDGE_INFO (e)->back_edge_prob,
1422 &real_inv_br_prob_base);
1426 /* First compute probabilities locally for each loop from innermost
1427 to outermost to examine probabilities for back edges. */
1428 estimate_loops_at_level (loops->tree_root);
1430 memcpy (&freq_max, &real_zero, sizeof (real_zero));
1432 if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
1433 memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
1435 sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
1436 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1440 sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
1441 sreal_add (&tmp, &tmp, &real_one_half);
1442 bb->frequency = sreal_to_int (&tmp);
1445 free_aux_for_blocks ();
1446 free_aux_for_edges ();
1448 compute_function_frequency ();
1449 if (flag_reorder_functions)
1450 choose_function_section ();
1453 /* Decide whether function is hot, cold or unlikely executed. */
1455 compute_function_frequency (void)
1459 if (!profile_info || !flag_branch_probabilities)
1461 cfun->function_frequency = FUNCTION_FREQUENCY_UNLIKELY_EXECUTED;
1464 if (maybe_hot_bb_p (bb))
1466 cfun->function_frequency = FUNCTION_FREQUENCY_HOT;
1469 if (!probably_never_executed_bb_p (bb))
1470 cfun->function_frequency = FUNCTION_FREQUENCY_NORMAL;
1474 /* Choose appropriate section for the function. */
1476 choose_function_section (void)
1478 if (DECL_SECTION_NAME (current_function_decl)
1479 || !targetm.have_named_sections
1480 /* Theoretically we can split the gnu.linkonce text section too,
1481 but this requires more work as the frequency needs to match
1482 for all generated objects so we need to merge the frequency
1483 of all instances. For now just never set frequency for these. */
1484 || DECL_ONE_ONLY (current_function_decl))
1487 /* If we are doing the partitioning optimization, let the optimization
1488 choose the correct section into which to put things. */
1490 if (flag_reorder_blocks_and_partition)
1493 if (cfun->function_frequency == FUNCTION_FREQUENCY_HOT)
1494 DECL_SECTION_NAME (current_function_decl) =
1495 build_string (strlen (HOT_TEXT_SECTION_NAME), HOT_TEXT_SECTION_NAME);
1496 if (cfun->function_frequency == FUNCTION_FREQUENCY_UNLIKELY_EXECUTED)
1497 DECL_SECTION_NAME (current_function_decl) =
1498 build_string (strlen (UNLIKELY_EXECUTED_TEXT_SECTION_NAME),
1499 UNLIKELY_EXECUTED_TEXT_SECTION_NAME);
1503 struct tree_opt_pass pass_profile =
1505 "profile", /* name */
1507 tree_estimate_probability, /* execute */
1510 0, /* static_pass_number */
1511 TV_BRANCH_PROB, /* tv_id */
1512 PROP_cfg, /* properties_required */
1513 0, /* properties_provided */
1514 0, /* properties_destroyed */
1515 0, /* todo_flags_start */
1516 TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */