This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
__builtin_expect refinement
- To: gcc-patches at gcc dot gnu dot org
- Subject: __builtin_expect refinement
- From: Richard Henderson <rth at cygnus dot com>
- Date: Mon, 17 Apr 2000 12:30:19 -0700
Canonicalize_condition intuits past scc instructions. When we
walk right past the register for which we had expected value
information, this results in a canonicalization that we can't
do anything with.
This showed up in tests on Alpha, but I'd special cased that in
expected_value_to_br_prob before. It also showed up on Sparc,
but differently. Now there's no more special case.
r~
* loop.c (canonicalize_condition): Add WANT_REG argument.
Stop the search if we match it.
* expr.h (canonicalize_condition): Update decl.
* predict.c (expected_value_to_br_prob): Use it. Track last
expected value note.
(find_expected_value): Remove.
* reorg.c (mostly_true_jump): Always use BR_PROB if present.
Index: expr.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/expr.h,v
retrieving revision 1.61
diff -c -p -d -r1.61 expr.h
*** expr.h 2000/03/30 11:47:06 1.61
--- expr.h 2000/04/17 19:16:29
*************** extern rtx emit_store_flag_force PARAMS
*** 894,900 ****
/* Given an insn and condition, return a canonical description of
the test being made. */
! extern rtx canonicalize_condition PARAMS ((rtx, rtx, int, rtx *));
/* Given a JUMP_INSN, return a canonical description of the test
being made. */
--- 894,900 ----
/* Given an insn and condition, return a canonical description of
the test being made. */
! extern rtx canonicalize_condition PARAMS ((rtx, rtx, int, rtx *, rtx));
/* Given a JUMP_INSN, return a canonical description of the test
being made. */
Index: loop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.c,v
retrieving revision 1.233
diff -c -p -d -r1.233 loop.c
*** loop.c 2000/03/25 18:34:03 1.233
--- loop.c 2000/04/17 19:16:29
*************** update_reg_last_use (x, insn)
*** 9013,9026 ****
If EARLIEST is non-zero, it is a pointer to a place where the earliest
insn used in locating the condition was found. If a replacement test
of the condition is desired, it should be placed in front of that
! insn and we will be sure that the inputs are still valid. */
rtx
! canonicalize_condition (insn, cond, reverse, earliest)
rtx insn;
rtx cond;
int reverse;
rtx *earliest;
{
enum rtx_code code;
rtx prev = insn;
--- 9013,9031 ----
If EARLIEST is non-zero, it is a pointer to a place where the earliest
insn used in locating the condition was found. If a replacement test
of the condition is desired, it should be placed in front of that
! insn and we will be sure that the inputs are still valid.
!
! If WANT_REG is non-zero, we wish the condition to be relative to that
! register, if possible. Therefore, do not canonicalize the condition
! further. */
rtx
! canonicalize_condition (insn, cond, reverse, earliest, want_reg)
rtx insn;
rtx cond;
int reverse;
rtx *earliest;
+ rtx want_reg;
{
enum rtx_code code;
rtx prev = insn;
*************** canonicalize_condition (insn, cond, reve
*** 9050,9056 ****
the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
in cse.c */
! while (GET_RTX_CLASS (code) == '<' && op1 == CONST0_RTX (GET_MODE (op0)))
{
/* Set non-zero when we find something of interest. */
rtx x = 0;
--- 9055,9063 ----
the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
in cse.c */
! while (GET_RTX_CLASS (code) == '<'
! && op1 == CONST0_RTX (GET_MODE (op0))
! && op0 != want_reg)
{
/* Set non-zero when we find something of interest. */
rtx x = 0;
*************** get_condition (jump, earliest)
*** 9291,9297 ****
= GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 2)) == LABEL_REF
&& XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump);
! return canonicalize_condition (jump, cond, reverse, earliest);
}
/* Similar to above routine, except that we also put an invariant last
--- 9298,9304 ----
= GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 2)) == LABEL_REF
&& XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump);
! return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
}
/* Similar to above routine, except that we also put an invariant last
Index: predict.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/predict.c,v
retrieving revision 1.4
diff -c -p -d -r1.4 predict.c
*** predict.c 2000/04/17 16:49:00 1.4
--- predict.c 2000/04/17 19:16:29
*************** static rtx find_expected_value PARAMS (
*** 190,218 ****
void
expected_value_to_br_prob ()
{
! rtx insn, cond, earliest, ev;
for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
{
! /* Look for simple conditional branches. */
! if (GET_CODE (insn) != JUMP_INSN)
! continue;
! if (! condjump_p (insn) || simplejump_p (insn))
! continue;
! /* Collect the branch condition. Some machines can branch on
! user values directly, others need a compare instruction. If
! the branch condition involves a MODE_INT register, try that
! expression first. Otherwise use get_condition. */
cond = XEXP (SET_SRC (PATTERN (insn)), 0);
! if (GET_RTX_CLASS (GET_CODE (cond)) != '<')
! abort ();
! if (GET_CODE (XEXP (cond, 0)) == REG
! && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_INT
! && (ev = find_expected_value (cond, insn)) != NULL_RTX)
! ;
! else if ((cond = get_condition (insn, &earliest)) == NULL_RTX
! || (ev = find_expected_value (cond, earliest)) == NULL_RTX)
continue;
/* Substitute and simplify. Given that the expression we're
--- 190,235 ----
void
expected_value_to_br_prob ()
{
! rtx insn, cond, ev = NULL_RTX, ev_reg;
for (insn = get_insns (); insn ; insn = NEXT_INSN (insn))
{
! switch (GET_CODE (insn))
! {
! case NOTE:
! /* Look for expected value notes. */
! if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE)
! {
! ev = NOTE_EXPECTED_VALUE (insn);
! ev_reg = XEXP (ev, 0);
! }
! continue;
! case CODE_LABEL:
! /* Never propagate across labels. */
! ev = NULL_RTX;
! continue;
!
! default:
! /* Look for insns that clobber the EV register. */
! if (ev && reg_set_p (ev_reg, insn))
! ev = NULL_RTX;
! continue;
!
! case JUMP_INSN:
! /* Look for simple conditional branches. If we havn't got an
! expected value yet, no point going further. */
! if (GET_CODE (insn) != JUMP_INSN || ev == NULL_RTX)
! continue;
! if (! condjump_p (insn) || simplejump_p (insn))
! continue;
! break;
! }
!
! /* Collect the branch condition, hopefully relative to EV_REG. */
cond = XEXP (SET_SRC (PATTERN (insn)), 0);
! cond = canonicalize_condition (insn, cond, 0, NULL, ev_reg);
! if (! cond || XEXP (cond, 0) != ev_reg)
continue;
/* Substitute and simplify. Given that the expression we're
*************** expected_value_to_br_prob ()
*** 223,270 ****
cond = simplify_rtx (cond);
/* Turn the condition into a scaled branch probability. */
! if (cond == const0_rtx)
! cond = const1_rtx;
! else if (cond == const1_rtx)
! cond = GEN_INT (REG_BR_PROB_BASE - 1);
! else
abort ();
REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn));
}
- }
-
- /* Search backwards for a NOTE_INSN_EXPECTED_VALUE note with a register
- that matches the condition. */
-
- static rtx
- find_expected_value (cond, earliest)
- rtx cond, earliest;
- {
- rtx insn, reg = XEXP (cond, 0);
- int timeout;
-
- /* The condition should be (op (reg) (const_int)), otherwise we
- won't be able to intuit anything about it. */
- if (GET_CODE (reg) != REG
- || GET_CODE (XEXP (cond, 1)) != CONST_INT
- || GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
- return NULL_RTX;
-
- /* Assuming the user wrote something like `if (__builtin_expect(...))',
- we shouldn't have to search too far. Also stop if we reach a code
- label or if REG is modified. */
- for (insn = earliest, timeout = 10;
- insn && timeout > 0;
- insn = PREV_INSN (insn), --timeout)
- {
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_EXPECTED_VALUE
- && XEXP (NOTE_EXPECTED_VALUE (insn), 0) == reg)
- return NOTE_EXPECTED_VALUE (insn);
-
- if (GET_CODE (insn) == CODE_LABEL || reg_set_p (reg, insn))
- break;
- }
-
- return NULL_RTX;
}
--- 240,249 ----
cond = simplify_rtx (cond);
/* Turn the condition into a scaled branch probability. */
! if (cond == const1_rtx)
! cond = GEN_INT (REG_BR_PROB_BASE);
! else if (cond != const0_rtx)
abort ();
REG_NOTES (insn) = alloc_EXPR_LIST (REG_BR_PROB, cond, REG_NOTES (insn));
}
}
Index: reorg.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/reorg.c,v
retrieving revision 1.50
diff -c -p -d -r1.50 reorg.c
*** reorg.c 2000/04/12 20:46:22 1.50
--- reorg.c 2000/04/17 19:16:30
*************** mostly_true_jump (jump_insn, condition)
*** 900,928 ****
rtx jump_insn, condition;
{
rtx target_label = JUMP_LABEL (jump_insn);
! rtx insn;
int rare_dest = rare_destination (target_label);
int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
/* If branch probabilities are available, then use that number since it
always gives a correct answer. */
! if (flag_branch_probabilities)
{
! rtx note = find_reg_note (jump_insn, REG_BR_PROB, 0);
! if (note)
! {
! int prob = XINT (note, 0);
! if (prob >= REG_BR_PROB_BASE * 9 / 10)
! return 2;
! else if (prob >= REG_BR_PROB_BASE / 2)
! return 1;
! else if (prob >= REG_BR_PROB_BASE / 10)
! return 0;
! else
! return -1;
! }
}
/* If this is a branch outside a loop, it is highly unlikely. */
if (GET_CODE (PATTERN (jump_insn)) == SET
--- 900,927 ----
rtx jump_insn, condition;
{
rtx target_label = JUMP_LABEL (jump_insn);
! rtx insn, note;
int rare_dest = rare_destination (target_label);
int rare_fallthrough = rare_destination (NEXT_INSN (jump_insn));
/* If branch probabilities are available, then use that number since it
always gives a correct answer. */
! note = find_reg_note (jump_insn, REG_BR_PROB, 0);
! if (note)
{
! int prob = INTVAL (XEXP (note, 0));
! if (prob >= REG_BR_PROB_BASE * 9 / 10)
! return 2;
! else if (prob >= REG_BR_PROB_BASE / 2)
! return 1;
! else if (prob >= REG_BR_PROB_BASE / 10)
! return 0;
! else
! return -1;
}
+
+ /* ??? Ought to use estimate_probability instead. */
/* If this is a branch outside a loop, it is highly unlikely. */
if (GET_CODE (PATTERN (jump_insn)) == SET