1 /* Branch prediction routines for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
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.
37 #include "basic-block.h"
38 #include "insn-config.h"
40 #include "hard-reg-set.h"
47 #include "insn-flags.h"
52 /* Statically estimate the probability that a branch will be taken.
53 ??? In the next revision there will be a number of other predictors added
54 from the above references. Further, each heuristic will be factored out
55 into its own function for clarity (and to facilitate the combination of
59 estimate_probability (loops_info)
60 struct loops *loops_info;
64 /* Try to predict out blocks in a loop that are not part of a
66 for (i = 0; i < loops_info->num; i++)
70 for (j = loops_info->array[i].first->index;
71 j <= loops_info->array[i].last->index;
76 if (! TEST_BIT (loops_info->array[i].nodes, j))
77 for (e = BASIC_BLOCK(j)->pred; e; e = e->pred_next)
78 if (TEST_BIT (loops_info->array[i].nodes, e->src->index))
80 rtx last_insn = BLOCK_END (e->src->index);
83 if (GET_CODE (last_insn) != JUMP_INSN
84 || ! condjump_p (last_insn) || simplejump_p (last_insn))
86 cond = get_condition (last_insn, &earliest);
89 if (! find_reg_note (last_insn, REG_BR_PROB, 0))
91 = gen_rtx_EXPR_LIST (REG_BR_PROB,
92 GEN_INT (REG_BR_PROB_BASE),
93 REG_NOTES (last_insn));
98 /* Attempt to predict conditional jumps using a number of heuristics.
99 For each conditional jump, we try each heuristic in a fixed order.
100 If more than one heuristic applies to a particular branch, the first
101 is used as the prediction for the branch. */
102 for (i = 0; i < n_basic_blocks - 1; i++)
104 rtx last_insn = BLOCK_END (i);
109 if (GET_CODE (last_insn) != JUMP_INSN
110 || ! condjump_p (last_insn) || simplejump_p (last_insn))
113 if (find_reg_note (last_insn, REG_BR_PROB, 0))
116 cond = get_condition (last_insn, &earliest);
120 /* If one of the successor blocks has no successors, predict
121 that side not taken. */
122 /* ??? Ought to do the same for any subgraph with no exit. */
123 for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
124 if (e->dest->succ == NULL)
126 if (e->flags & EDGE_FALLTHRU)
127 prob = REG_BR_PROB_BASE;
133 /* Try "pointer heuristic."
134 A comparison ptr == 0 is predicted as false.
135 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
136 switch (GET_CODE (cond))
139 if (GET_CODE (XEXP (cond, 0)) == REG
140 && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 0)))
141 && (XEXP (cond, 1) == const0_rtx
142 || (GET_CODE (XEXP (cond, 1)) == REG
143 && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
145 prob = REG_BR_PROB_BASE / 10;
150 if (GET_CODE (XEXP (cond, 0)) == REG
151 && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 0)))
152 && (XEXP (cond, 1) == const0_rtx
153 || (GET_CODE (XEXP (cond, 1)) == REG
154 && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
156 prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
165 /* Try "opcode heuristic."
166 EQ tests are usually false and NE tests are usually true. Also,
167 most quantities are positive, so we can make the appropriate guesses
168 about signed comparisons against zero. */
169 switch (GET_CODE (cond))
172 /* Unconditional branch. */
173 prob = (cond == const0_rtx ? 0 : REG_BR_PROB_BASE);
177 prob = REG_BR_PROB_BASE / 10;
180 prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
184 if (XEXP (cond, 1) == const0_rtx)
186 prob = REG_BR_PROB_BASE / 10;
192 if (XEXP (cond, 1) == const0_rtx
193 || (GET_CODE (XEXP (cond, 1)) == CONST_INT
194 && INTVAL (XEXP (cond, 1)) == -1))
196 prob = REG_BR_PROB_BASE - (REG_BR_PROB_BASE / 10);
205 /* If we havn't chosen something by now, predict 50-50. */
206 prob = REG_BR_PROB_BASE / 2;
209 REG_NOTES (last_insn)
210 = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
211 REG_NOTES (last_insn));
215 /* __builtin_expect dropped tokens into the insn stream describing
216 expected values of registers. Generate branch probabilities
217 based off these values. */
219 static rtx find_expected_value PARAMS ((rtx, rtx));
222 expected_value_to_br_prob ()
224 rtx insn, cond, ev = NULL_RTX, ev_reg;
226 for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
228 switch (GET_CODE (insn))
231 /* Look for expected value notes. */
232 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
234 ev = NOTE_EXPECTED_VALUE (insn);
235 ev_reg = XEXP (ev, 0);
240 /* Never propagate across labels. */
245 /* Look for insns that clobber the EV register. */
246 if (ev && reg_set_p (ev_reg, insn))
251 /* Look for simple conditional branches. If we havn't got an
252 expected value yet, no point going further. */
253 if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
255 if (! condjump_p (insn) || simplejump_p (insn))
260 /* Collect the branch condition, hopefully relative to EV_REG. */
261 /* ??? At present we'll miss things like
262 (expected_value (eq r70 0))
264 (set r80 (lt r70 r71))
265 (set pc (if_then_else (ne r80 0) ...))
266 as canonicalize_condition will render this to us as
268 Could use cselib to try and reduce this further. */
269 cond = XEXP (SET_SRC (PATTERN (insn)), 0);
270 cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
272 || XEXP (cond, 0) != ev_reg
273 || GET_CODE (XEXP (cond, 1)) != CONST_INT)
276 /* Substitute and simplify. Given that the expression we're
277 building involves two constants, we should wind up with either
279 cond = gen_rtx_fmt_ee (GET_CODE (cond), VOIDmode,
280 XEXP (ev, 1), XEXP (cond, 1));
281 cond = simplify_rtx (cond);
283 /* Turn the condition into a scaled branch probability. */
284 if (cond == const1_rtx)
285 cond = GEN_INT (REG_BR_PROB_BASE);
286 else if (cond != const0_rtx)
288 REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn));