837f2d7f52020457e8547d439b961b6098402e22
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.
38 #include "hard-reg-set.h"
39 #include "basic-block.h"
40 #include "insn-config.h"
48 #include "insn-flags.h"
52 /* Random guesstimation given names. */
53 #define PROB_NEVER (0)
54 #define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
55 #define PROB_UNLIKELY (REG_BR_PROB_BASE * 4 / 10 - 1)
56 #define PROB_EVEN (REG_BR_PROB_BASE / 2)
57 #define PROB_LIKELY (REG_BR_PROB_BASE - PROB_UNLIKELY)
58 #define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
59 #define PROB_ALWAYS (REG_BR_PROB_BASE)
61 /* Statically estimate the probability that a branch will be taken.
62 ??? In the next revision there will be a number of other predictors added
63 from the above references. Further, each heuristic will be factored out
64 into its own function for clarity (and to facilitate the combination of
68 estimate_probability (loops_info
)
69 struct loops
*loops_info
;
73 /* Try to predict out blocks in a loop that are not part of a
75 for (i
= 0; i
< loops_info
->num
; i
++)
79 for (j
= loops_info
->array
[i
].first
->index
;
80 j
<= loops_info
->array
[i
].last
->index
;
85 if (! TEST_BIT (loops_info
->array
[i
].nodes
, j
))
86 for (e
= BASIC_BLOCK(j
)->pred
; e
; e
= e
->pred_next
)
87 if (TEST_BIT (loops_info
->array
[i
].nodes
, e
->src
->index
))
89 rtx last_insn
= BLOCK_END (e
->src
->index
);
92 if (GET_CODE (last_insn
) != JUMP_INSN
93 || ! condjump_p (last_insn
) || simplejump_p (last_insn
))
95 cond
= get_condition (last_insn
, &earliest
);
98 if (! find_reg_note (last_insn
, REG_BR_PROB
, 0))
100 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
101 GEN_INT (PROB_VERY_LIKELY
),
102 REG_NOTES (last_insn
));
107 /* Attempt to predict conditional jumps using a number of heuristics.
108 For each conditional jump, we try each heuristic in a fixed order.
109 If more than one heuristic applies to a particular branch, the first
110 is used as the prediction for the branch. */
111 for (i
= 0; i
< n_basic_blocks
- 1; i
++)
113 rtx last_insn
= BLOCK_END (i
);
118 if (GET_CODE (last_insn
) != JUMP_INSN
119 || ! condjump_p (last_insn
) || simplejump_p (last_insn
))
122 if (find_reg_note (last_insn
, REG_BR_PROB
, 0))
125 cond
= get_condition (last_insn
, &earliest
);
129 /* If one of the successor blocks has no successors, predict
130 that side not taken. */
131 /* ??? Ought to do the same for any subgraph with no exit. */
132 for (e
= BASIC_BLOCK (i
)->succ
; e
; e
= e
->succ_next
)
133 if (e
->dest
->succ
== NULL
)
135 if (e
->flags
& EDGE_FALLTHRU
)
142 /* Try "pointer heuristic."
143 A comparison ptr == 0 is predicted as false.
144 Similarly, a comparison ptr1 == ptr2 is predicted as false. */
145 switch (GET_CODE (cond
))
148 if (GET_CODE (XEXP (cond
, 0)) == REG
149 && REGNO_POINTER_FLAG (REGNO (XEXP (cond
, 0)))
150 && (XEXP (cond
, 1) == const0_rtx
151 || (GET_CODE (XEXP (cond
, 1)) == REG
152 && REGNO_POINTER_FLAG (REGNO (XEXP (cond
, 1))))))
154 prob
= PROB_UNLIKELY
;
159 if (GET_CODE (XEXP (cond
, 0)) == REG
160 && REGNO_POINTER_FLAG (REGNO (XEXP (cond
, 0)))
161 && (XEXP (cond
, 1) == const0_rtx
162 || (GET_CODE (XEXP (cond
, 1)) == REG
163 && REGNO_POINTER_FLAG (REGNO (XEXP (cond
, 1))))))
174 /* Try "opcode heuristic."
175 EQ tests are usually false and NE tests are usually true. Also,
176 most quantities are positive, so we can make the appropriate guesses
177 about signed comparisons against zero. */
178 switch (GET_CODE (cond
))
181 /* Unconditional branch. */
182 prob
= (cond
== const0_rtx
? PROB_NEVER
: PROB_ALWAYS
);
186 prob
= PROB_UNLIKELY
;
193 if (XEXP (cond
, 1) == const0_rtx
)
195 prob
= PROB_UNLIKELY
;
201 if (XEXP (cond
, 1) == const0_rtx
202 || (GET_CODE (XEXP (cond
, 1)) == CONST_INT
203 && INTVAL (XEXP (cond
, 1)) == -1))
214 /* If we havn't chosen something by now, predict 50-50. */
218 REG_NOTES (last_insn
)
219 = gen_rtx_EXPR_LIST (REG_BR_PROB
, GEN_INT (prob
),
220 REG_NOTES (last_insn
));
224 /* __builtin_expect dropped tokens into the insn stream describing
225 expected values of registers. Generate branch probabilities
226 based off these values. */
229 expected_value_to_br_prob ()
231 rtx insn
, cond
, ev
= NULL_RTX
, ev_reg
= NULL_RTX
;
233 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
235 switch (GET_CODE (insn
))
238 /* Look for expected value notes. */
239 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_EXPECTED_VALUE
)
241 ev
= NOTE_EXPECTED_VALUE (insn
);
242 ev_reg
= XEXP (ev
, 0);
247 /* Never propagate across labels. */
252 /* Look for insns that clobber the EV register. */
253 if (ev
&& reg_set_p (ev_reg
, insn
))
258 /* Look for simple conditional branches. If we havn't got an
259 expected value yet, no point going further. */
260 if (GET_CODE (insn
) != JUMP_INSN
|| ev
== NULL_RTX
)
262 if (! condjump_p (insn
) || simplejump_p (insn
))
267 /* Collect the branch condition, hopefully relative to EV_REG. */
268 /* ??? At present we'll miss things like
269 (expected_value (eq r70 0))
271 (set r80 (lt r70 r71))
272 (set pc (if_then_else (ne r80 0) ...))
273 as canonicalize_condition will render this to us as
275 Could use cselib to try and reduce this further. */
276 cond
= XEXP (SET_SRC (PATTERN (insn
)), 0);
277 cond
= canonicalize_condition (insn
, cond
, 0, NULL
, ev_reg
);
279 || XEXP (cond
, 0) != ev_reg
280 || GET_CODE (XEXP (cond
, 1)) != CONST_INT
)
283 /* Substitute and simplify. Given that the expression we're
284 building involves two constants, we should wind up with either
286 cond
= gen_rtx_fmt_ee (GET_CODE (cond
), VOIDmode
,
287 XEXP (ev
, 1), XEXP (cond
, 1));
288 cond
= simplify_rtx (cond
);
290 /* Turn the condition into a scaled branch probability. */
291 if (cond
== const1_rtx
)
292 cond
= GEN_INT (PROB_VERY_LIKELY
);
293 else if (cond
== const0_rtx
)
294 cond
= GEN_INT (PROB_VERY_UNLIKELY
);
297 REG_NOTES (insn
) = alloc_EXPR_LIST (REG_BR_PROB
, cond
, REG_NOTES (insn
));