Wu and Larus; MICRO-27.
[3] "Corpus-based Static Branch Prediction"
Calder, Grunwald, Lindsay, Martin, Mozer, and Zorn; PLDI '95.
+
*/
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
+#include "hard-reg-set.h"
#include "basic-block.h"
#include "insn-config.h"
#include "regs.h"
-#include "hard-reg-set.h"
#include "flags.h"
#include "output.h"
#include "function.h"
#include "expr.h"
+/* Random guesstimation given names. */
+#define PROB_NEVER (0)
+#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
+#define PROB_UNLIKELY (REG_BR_PROB_BASE * 4 / 10 - 1)
+#define PROB_EVEN (REG_BR_PROB_BASE / 2)
+#define PROB_LIKELY (REG_BR_PROB_BASE - PROB_UNLIKELY)
+#define PROB_VERY_LIKELY (REG_BR_PROB_BASE - PROB_VERY_UNLIKELY)
+#define PROB_ALWAYS (REG_BR_PROB_BASE)
/* Statically estimate the probability that a branch will be taken.
??? In the next revision there will be a number of other predictors added
if (! find_reg_note (last_insn, REG_BR_PROB, 0))
REG_NOTES (last_insn)
= gen_rtx_EXPR_LIST (REG_BR_PROB,
- GEN_INT (REG_BR_PROB_BASE),
+ GEN_INT (PROB_VERY_LIKELY),
REG_NOTES (last_insn));
}
}
{
rtx last_insn = BLOCK_END (i);
rtx cond, earliest;
- int prob = 0;
+ int prob;
edge e;
if (GET_CODE (last_insn) != JUMP_INSN
|| ! condjump_p (last_insn) || simplejump_p (last_insn))
continue;
+
if (find_reg_note (last_insn, REG_BR_PROB, 0))
continue;
+
cond = get_condition (last_insn, &earliest);
if (! cond)
continue;
- /* If the jump branches around a block with no successors,
- predict it to be taken. */
- prob = 0;
+ /* If one of the successor blocks has no successors, predict
+ that side not taken. */
+ /* ??? Ought to do the same for any subgraph with no exit. */
for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
- if ((e->flags & EDGE_FALLTHRU) && e->dest->succ == NULL)
+ if (e->dest->succ == NULL)
{
- prob = REG_BR_PROB_BASE;
- break;
+ if (e->flags & EDGE_FALLTHRU)
+ prob = PROB_ALWAYS;
+ else
+ prob = PROB_NEVER;
+ goto emitnote;
}
- if (prob)
- {
- REG_NOTES (last_insn)
- = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
- REG_NOTES (last_insn));
- continue;
- }
/* Try "pointer heuristic."
A comparison ptr == 0 is predicted as false.
{
case EQ:
if (GET_CODE (XEXP (cond, 0)) == REG
- && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 0)))
+ && REG_POINTER (XEXP (cond, 0))
&& (XEXP (cond, 1) == const0_rtx
|| (GET_CODE (XEXP (cond, 1)) == REG
- && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
- prob = REG_BR_PROB_BASE / 10;
+ && REG_POINTER (XEXP (cond, 1)))))
+ {
+ prob = PROB_UNLIKELY;
+ goto emitnote;
+ }
break;
case NE:
if (GET_CODE (XEXP (cond, 0)) == REG
- && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 0)))
+ && REG_POINTER (XEXP (cond, 0))
&& (XEXP (cond, 1) == const0_rtx
|| (GET_CODE (XEXP (cond, 1)) == REG
- && REGNO_POINTER_FLAG (REGNO (XEXP (cond, 1))))))
- prob = REG_BR_PROB_BASE / 2;
+ && REG_POINTER (XEXP (cond, 1)))))
+ {
+ prob = PROB_LIKELY;
+ goto emitnote;
+ }
break;
+
default:
- prob = 0;
- }
- if (prob)
- {
- REG_NOTES (last_insn)
- = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
- REG_NOTES (last_insn));
- continue;
+ break;
}
/* Try "opcode heuristic."
{
case CONST_INT:
/* Unconditional branch. */
- prob = REG_BR_PROB_BASE / 2;
- break;
+ prob = (cond == const0_rtx ? PROB_NEVER : PROB_ALWAYS);
+ goto emitnote;
+
case EQ:
- prob = REG_BR_PROB_BASE / 10;
- break;
+ prob = PROB_UNLIKELY;
+ goto emitnote;
case NE:
- prob = REG_BR_PROB_BASE / 2;
- break;
+ prob = PROB_LIKELY;
+ goto emitnote;
case LE:
case LT:
if (XEXP (cond, 1) == const0_rtx)
- prob = REG_BR_PROB_BASE / 10;
+ {
+ prob = PROB_UNLIKELY;
+ goto emitnote;
+ }
break;
case GE:
case GT:
if (XEXP (cond, 1) == const0_rtx
|| (GET_CODE (XEXP (cond, 1)) == CONST_INT
&& INTVAL (XEXP (cond, 1)) == -1))
- prob = REG_BR_PROB_BASE / 2;
+ {
+ prob = PROB_LIKELY;
+ goto emitnote;
+ }
break;
default:
- prob = 0;
+ break;
}
+
+ /* If we havn't chosen something by now, predict 50-50. */
+ prob = PROB_EVEN;
+
+ emitnote:
REG_NOTES (last_insn)
= gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
REG_NOTES (last_insn));
expected values of registers. Generate branch probabilities
based off these values. */
-static rtx find_expected_value PARAMS ((rtx, rtx));
-
void
expected_value_to_br_prob ()
{
- rtx insn, cond, ev = NULL_RTX, ev_reg;
+ rtx insn, cond, ev = NULL_RTX, ev_reg = NULL_RTX;
for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
{
}
/* Collect the branch condition, hopefully relative to EV_REG. */
+ /* ??? At present we'll miss things like
+ (expected_value (eq r70 0))
+ (set r71 -1)
+ (set r80 (lt r70 r71))
+ (set pc (if_then_else (ne r80 0) ...))
+ as canonicalize_condition will render this to us as
+ (lt r70, r71)
+ Could use cselib to try and reduce this further. */
cond = XEXP (SET_SRC (PATTERN (insn)), 0);
cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
- if (! cond || XEXP (cond, 0) != ev_reg)
+ if (! cond
+ || XEXP (cond, 0) != ev_reg
+ || GET_CODE (XEXP (cond, 1)) != CONST_INT)
continue;
/* Substitute and simplify. Given that the expression we're
/* Turn the condition into a scaled branch probability. */
if (cond == const1_rtx)
- cond = GEN_INT (REG_BR_PROB_BASE);
- else if (cond != const0_rtx)
+ cond = GEN_INT (PROB_VERY_LIKELY);
+ else if (cond == const0_rtx)
+ cond = GEN_INT (PROB_VERY_UNLIKELY);
+ else
abort ();
REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn));
}
OSDN Git Service
