This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Jump bypassing and improved constant propagation
- From: Roger Sayle <roger at eyesopen dot com>
- To: <gcc-patches at gcc dot gnu dot org>
- Date: Sat, 25 May 2002 13:02:21 -0600 (MDT)
- Subject: [PATCH] Jump bypassing and improved constant propagation
This patch implements the "jump bypass" optimization pass that I recently
described on the gcc mailing list. Traditional constant propagation is
able to convert conditional jumps into unconditional jumps using the
available expressions calculated by PRE. For the common case, of jumps
at the start of a basic block, cprop_jump is able to perform this conversion
is the value one which the jump depends is known and has the same value
on all incoming edges. The jump bypass optimization below is an extension
of this, that is redirects the incoming edges for which the value is known.
[For details see http://gcc.gnu.org/ml/gcc/2002-05/msg01658.html]
As an example, consider the following function abstracted from the classic
whetstone benchmark
int
foo (int j)
{
if (j == 1) j = 2;
else j = 3;
if (j > 2) j = 0;
else j = 1;
if (j < 1) j = 1;
else j = 0;
return j;
}
With current mainline, we generate the following instructions on i686
with the compiler flags "-O2 -fno-if-conversion -fomit-frame-pointer".
foo: cmpl $1, 4(%esp)
movl $2, %eax
je .L3
movl $3, %eax
.L3: cmpl $2, %eax
jle .L4
xorl %eax, %eax
.L5: testl %eax, %eax
jle .L8
xorl %eax, %eax
ret
.L8: movl $1, %eax
ret
.L4: movl $1, %eax
jmp .L5
With the jump bypass patch below, we now generate the much simpler
foo: cmpl $1, 4(%esp)
je .L9
movl $1, %eax
ret
.L9: xorl %eax, %eax
ret
Which is equivalent to the C source code:
int
foo (int j)
{
return (j == 1)? 0 : 1;
}
Analysis of a GCC bootstrap on i686-pc-cygwin reveals that the jump
bypass optimization is sucessfully applied over 5000 times during a
bootstrap of the compiler. An additional 1,500 opportunities are
available if redirect_edge_and_branch_force were used instead of the
current redirect_edge_and_branch. The hold-up is that the former
may introduce new basic blocks, which renumbers the existing basic
block indices, invalidating all of the PRE data-flow analysis. This
will be fixed as soon as Zdenek's "Avoid basic block renumbering"
fixes are finished.
Many thanks to Andreas for performing SPEC2000 benchmarking. Alas
I was a bit disappointed in the numbers. Although the overall numbers
improve, it wasn't the dramatic performance improvement I was expecting.
One significant winner was 176.gcc (a 2% improvement). This is actually
enough to reduce the time to bootstrap the compiler with this optimization
enabled, saving a few seconds.
I suspect that the less than expected performance increases are caused
by interactions with other GCC optimizations. For example, in the
statement "for (i=0; i<10; i++)", it is now the jump bypassing pass
that realizes the loop is always executed atleast once, redirecting
the loop entry to after the loop condition. I can imagine this may
interfere with GCC's other loop transformations. Another example is
the effect of "-fno-if-conversion" in the example above. Without this
flag GCC actually generates:
foo: xorl %eax, %eax
cmpl $1, 4(%esp)
setne %al
addl $2, %eax
cmpl $2, %eax
setg %al
movzbl %al, %eax
ret
Being a single block by the time this reaches GCSE, there's nothing
that the jump bypass optimization can do to reduce it. I'm currently
investigating why "-fif-conversion2" isn't able to perform these
clever transformations after GCSE. In which case we'd get the near
perfect:
foo: xorl %eax, %eax
cmpl $1, 4(%esp)
setne %al
ret
As I've also explained in a recent posting to the gcc-patches mailing
list, http://gcc.gnu.org/ml/gcc-patches/2002-05/msg01990.html, GCC's
current cprop implementation isn't as effective as it could be on
targets that use condition code registers, including x86. As both
"cprop_jump" and "bypass_block" are related I've taken the opportunity
to fix the former at the same time as developing the latter. Using
the same idiom, i.e. passing both the cc-setter (possibly NULL) and
the jump insn, avoids "#ifdef HAVE_cc0" code and applies to more
platforms. With the recent change to simplify_replace_rtx, we can
now propagate constants into more conditional jumps than previously.
This patch has been tested with "make bootstrap" and "make -k check"
on i686-pc-linux-gnu with all languages except Ada (and treelang)
with no new regressions. As an added benefit, this patch even fixes
two XFAILs; gcc.dg/uninit-A.c uninitialized variable warnings on lines
52 and 53. The simplification of the CFG from jump bypassing makes
the flow of control clear enough for GCC to see that these variables
are actually always assigned before they're used.
Ok for mainline?
2002-05-25 Roger Sayle <roger@eyesopen.com>
* gcse.c (cprop_cc0_jump): Function deleted.
(cprop_jump): Take an additional argument which is the possibly
NULL cc setting insn immediately before the conditional jump.
When a MODE_CC set is present, substitute it into the JUMP_INSN
before attempting the constant propagation.
(cprop_insn): Recognize cc setters followed by conditional jumps
as a special case. Use cprop_jump instead of cprop_cc0_jump.
(cprop_one_pass): Call bypass_conditional_jumps if altering jumps.
(find_bypass_set): New function based upon find_avail_set used by
cprop, but finds constant expressions available at the end of
basic blocks.
(bypass_block): New function. Given a basic block that begins
with a conditional jump and multiple incoming edges, perform
the jump bypass optimization.
(bypass_conditional_jumps): New function. Call bypass_block with
each suitable basic block in the CFG using a simple single pass.
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.190
diff -c -3 -p -r1.190 gcse.c
*** gcse.c 23 May 2002 19:23:40 -0000 1.190
--- gcse.c 25 May 2002 17:19:04 -0000
*************** static void compute_cprop_data PARAMS ((
*** 609,624 ****
static void find_used_regs PARAMS ((rtx *, void *));
static int try_replace_reg PARAMS ((rtx, rtx, rtx));
static struct expr *find_avail_set PARAMS ((int, rtx));
! static int cprop_jump PARAMS ((basic_block, rtx, rtx, rtx));
! #ifdef HAVE_cc0
! static int cprop_cc0_jump PARAMS ((basic_block, rtx, struct reg_use *, rtx));
! #endif
static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
static int load_killed_in_block_p PARAMS ((basic_block, int, rtx, int));
static void canon_list_insert PARAMS ((rtx, rtx, void *));
static int cprop_insn PARAMS ((basic_block, rtx, int));
static int cprop PARAMS ((int));
static int one_cprop_pass PARAMS ((int, int));
static void alloc_pre_mem PARAMS ((int, int));
static void free_pre_mem PARAMS ((void));
static void compute_pre_data PARAMS ((void));
--- 609,624 ----
static void find_used_regs PARAMS ((rtx *, void *));
static int try_replace_reg PARAMS ((rtx, rtx, rtx));
static struct expr *find_avail_set PARAMS ((int, rtx));
! static int cprop_jump PARAMS ((basic_block, rtx, rtx, rtx, rtx));
static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
static int load_killed_in_block_p PARAMS ((basic_block, int, rtx, int));
static void canon_list_insert PARAMS ((rtx, rtx, void *));
static int cprop_insn PARAMS ((basic_block, rtx, int));
static int cprop PARAMS ((int));
static int one_cprop_pass PARAMS ((int, int));
+ static struct expr *find_bypass_set PARAMS ((int, int));
+ static int bypass_block PARAMS ((basic_block, rtx, rtx));
+ static int bypass_conditional_jumps PARAMS ((void));
static void alloc_pre_mem PARAMS ((int, int));
static void free_pre_mem PARAMS ((void));
static void compute_pre_data PARAMS ((void));
*************** find_avail_set (regno, insn)
*** 4076,4115 ****
}
/* Subroutine of cprop_insn that tries to propagate constants into
! JUMP_INSNS. INSN must be a conditional jump. FROM is what we will try to
! replace, SRC is the constant we will try to substitute for it. Returns
! nonzero if a change was made. We know INSN has just a SET. */
static int
! cprop_jump (bb, insn, from, src)
! rtx insn;
rtx from;
rtx src;
- basic_block bb;
{
! rtx set = PATTERN (insn);
! rtx new = simplify_replace_rtx (SET_SRC (set), from, src);
/* If no simplification can be made, then try the next
register. */
! if (rtx_equal_p (new, SET_SRC (set)))
return 0;
/* If this is now a no-op delete it, otherwise this must be a valid insn. */
if (new == pc_rtx)
! delete_insn (insn);
else
{
! if (! validate_change (insn, &SET_SRC (set), new, 0))
return 0;
/* If this has turned into an unconditional jump,
then put a barrier after it so that the unreachable
code will be deleted. */
if (GET_CODE (SET_SRC (set)) == LABEL_REF)
! emit_barrier_after (insn);
}
run_jump_opt_after_gcse = 1;
const_prop_count++;
--- 4076,4133 ----
}
/* Subroutine of cprop_insn that tries to propagate constants into
! JUMP_INSNS. JUMP must be a conditional jump. If SETCC is non-NULL
! it is the instruction that immediately preceeds JUMP, and must be a
! single SET of a CC_MODE register. FROM is what we will try to replace,
! SRC is the constant we will try to substitute for it. Returns nonzero
! if a change was made. */
static int
! cprop_jump (bb, setcc, jump, from, src)
! basic_block bb;
! rtx setcc;
! rtx jump;
rtx from;
rtx src;
{
! rtx new, new_set;
! rtx set = PATTERN (jump);
!
! /* First substitute in the INSN condition as the SET_SRC of the JUMP,
! then substitute that given values in this expanded JUMP. */
! if (setcc != NULL)
! new_set = simplify_replace_rtx (SET_SRC (set),
! SET_DEST (PATTERN (setcc)),
! SET_SRC (PATTERN (setcc)));
! else
! new_set = set;
!
! new = simplify_replace_rtx (new_set, from, src);
/* If no simplification can be made, then try the next
register. */
! if (rtx_equal_p (new, new_set))
return 0;
/* If this is now a no-op delete it, otherwise this must be a valid insn. */
if (new == pc_rtx)
! delete_insn (jump);
else
{
! if (! validate_change (jump, &SET_SRC (set), new, 0))
return 0;
/* If this has turned into an unconditional jump,
then put a barrier after it so that the unreachable
code will be deleted. */
if (GET_CODE (SET_SRC (set)) == LABEL_REF)
! emit_barrier_after (jump);
}
+ /* Delete the cc mode setter. */
+ if (setcc != NULL)
+ delete_insn (setcc);
+
run_jump_opt_after_gcse = 1;
const_prop_count++;
*************** cprop_jump (bb, insn, from, src)
*** 4117,4123 ****
{
fprintf (gcse_file,
"CONST-PROP: Replacing reg %d in insn %d with constant ",
! REGNO (from), INSN_UID (insn));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
--- 4135,4141 ----
{
fprintf (gcse_file,
"CONST-PROP: Replacing reg %d in insn %d with constant ",
! REGNO (from), INSN_UID (jump));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
*************** cprop_jump (bb, insn, from, src)
*** 4126,4162 ****
return 1;
}
- #ifdef HAVE_cc0
-
- /* Subroutine of cprop_insn that tries to propagate constants into JUMP_INSNS
- for machines that have CC0. INSN is a single set that stores into CC0;
- the insn following it is a conditional jump. REG_USED is the use we will
- try to replace, SRC is the constant we will try to substitute for it.
- Returns nonzero if a change was made. */
-
- static int
- cprop_cc0_jump (bb, insn, reg_used, src)
- basic_block bb;
- rtx insn;
- struct reg_use *reg_used;
- rtx src;
- {
- /* First substitute in the SET_SRC of INSN, then substitute that for
- CC0 in JUMP. */
- rtx jump = NEXT_INSN (insn);
- rtx new_src = simplify_replace_rtx (SET_SRC (PATTERN (insn)),
- reg_used->reg_rtx, src);
-
- if (! cprop_jump (bb, jump, cc0_rtx, new_src))
- return 0;
-
- /* If we succeeded, delete the cc0 setter. */
- delete_insn (insn);
-
- return 1;
- }
- #endif
-
/* Perform constant and copy propagation on INSN.
The result is non-zero if a change was made. */
--- 4144,4149 ----
*************** cprop_insn (bb, insn, alter_jumps)
*** 4215,4221 ****
/* Constant propagation. */
if (CONSTANT_P (src))
{
! /* Handle normal insns first. */
if (GET_CODE (insn) == INSN
&& try_replace_reg (reg_used->reg_rtx, src, insn))
{
--- 4202,4226 ----
/* Constant propagation. */
if (CONSTANT_P (src))
{
! /* Check for MODE_CC setting instructions followed by
! conditional branch instructions first. */
! if (alter_jumps
! && GET_CODE (PATTERN (insn)) == SET
! && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
! && condjump_p (NEXT_INSN (insn))
! && ! simplejump_p (NEXT_INSN (insn)))
! {
! rtx dest = SET_DEST (PATTERN (insn));
! if (GET_MODE_CLASS (GET_MODE (dest)) == MODE_CC
! && cprop_jump (bb, insn, NEXT_INSN (insn),
! reg_used->reg_rtx, src))
! {
! changed = 1;
! break;
! }
! }
!
! /* Handle normal insns next. */
if (GET_CODE (insn) == INSN
&& try_replace_reg (reg_used->reg_rtx, src, insn))
{
*************** cprop_insn (bb, insn, alter_jumps)
*** 4245,4267 ****
&& GET_CODE (insn) == JUMP_INSN
&& condjump_p (insn)
&& ! simplejump_p (insn))
! changed |= cprop_jump (bb, insn, reg_used->reg_rtx, src);
- #ifdef HAVE_cc0
- /* Similar code for machines that use a pair of CC0 setter and
- conditional jump insn. */
- else if (alter_jumps
- && GET_CODE (PATTERN (insn)) == SET
- && SET_DEST (PATTERN (insn)) == cc0_rtx
- && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
- && condjump_p (NEXT_INSN (insn))
- && ! simplejump_p (NEXT_INSN (insn))
- && cprop_cc0_jump (bb, insn, reg_used, src))
- {
- changed = 1;
- break;
- }
- #endif
}
else if (GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
--- 4250,4257 ----
&& GET_CODE (insn) == JUMP_INSN
&& condjump_p (insn)
&& ! simplejump_p (insn))
! changed |= cprop_jump (bb, NULL, insn, reg_used->reg_rtx, src);
}
else if (GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
*************** one_cprop_pass (pass, alter_jumps)
*** 4361,4366 ****
--- 4351,4358 ----
alloc_cprop_mem (n_basic_blocks, n_sets);
compute_cprop_data ();
changed = cprop (alter_jumps);
+ if (alter_jumps)
+ changed |= bypass_conditional_jumps ();
free_cprop_mem ();
}
*************** one_cprop_pass (pass, alter_jumps)
*** 4374,4379 ****
--- 4366,4546 ----
const_prop_count, copy_prop_count);
}
+ return changed;
+ }
+
+ /* Bypass conditional jumps. */
+
+ /* Find a set of REGNO to a constant that is available at the end of basic
+ block BB. Returns NULL if no such set is found. Based heavily upon
+ find_avail_set. */
+
+ static struct expr *
+ find_bypass_set (regno, bb)
+ int regno;
+ int bb;
+ {
+ struct expr *result = 0;
+
+ for (;;)
+ {
+ rtx src;
+ struct expr *set = lookup_set (regno, NULL_RTX);
+
+ while (set)
+ {
+ if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
+ break;
+ set = next_set (regno, set);
+ }
+
+ if (set == 0)
+ break;
+
+ if (GET_CODE (set->expr) != SET)
+ abort ();
+
+ src = SET_SRC (set->expr);
+ if (CONSTANT_P (src))
+ result = set;
+
+ if (GET_CODE (src) != REG)
+ break;
+
+ regno = REGNO (src);
+ }
+ return result;
+ }
+
+
+ /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
+ basic block BB which has more than one predecessor. If not NULL, SETCC
+ is the first instruction of BB, which is immediately followed by JUMP_INSN
+ JUMP. Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
+ Returns nonzero if a change was made. */
+
+ static int
+ bypass_block (bb, setcc, jump)
+ basic_block bb;
+ rtx setcc, jump;
+ {
+ rtx insn, note;
+ edge e, enext;
+ int i,change;
+
+ insn = (setcc != NULL) ? setcc : jump;
+
+ /* Determine set of register uses in INSN. */
+ reg_use_count = 0;
+ note_uses (&PATTERN (insn), find_used_regs, NULL);
+ note = find_reg_equal_equiv_note (insn);
+ if (note)
+ find_used_regs (&XEXP (note, 0), NULL);
+
+ change = 0;
+ for (e = bb->pred; e; e = enext)
+ {
+ enext = e->pred_next;
+ for (i = 0; i < reg_use_count; i++)
+ {
+ struct reg_use *reg_used = ®_use_table[i];
+ unsigned int regno = REGNO (reg_used->reg_rtx);
+ basic_block dest;
+ struct expr *set;
+ rtx src, new;
+
+ if (regno >= max_gcse_regno)
+ continue;
+
+ set = find_bypass_set (regno, e->src->index);
+
+ if (! set)
+ continue;
+
+ src = SET_SRC (PATTERN (jump));
+
+ if (setcc != NULL)
+ src = simplify_replace_rtx (src,
+ SET_DEST (PATTERN (setcc)),
+ SET_SRC (PATTERN (setcc)));
+
+ new = simplify_replace_rtx (src, reg_used->reg_rtx,
+ SET_SRC (set->expr));
+
+ if (new == pc_rtx)
+ dest = FALLTHRU_EDGE (bb)->dest;
+ else if (GET_CODE (new) == LABEL_REF)
+ dest = BRANCH_EDGE (bb)->dest;
+ else
+ dest = NULL;
+
+ /* Once basic block indices are stable, we should be able
+ to use redirect_edge_and_branch_force instead. */
+ if ((dest != NULL) && redirect_edge_and_branch (e, dest))
+ {
+ if (gcse_file != NULL)
+ {
+ fprintf (gcse_file, "JUMP-BYPASS: Replacing reg %d in ",
+ regno);
+ fprintf (gcse_file, "insn %d with constant ",
+ INSN_UID (jump));
+ print_rtl (gcse_file, SET_SRC (set->expr));
+ fprintf (gcse_file, "\nBypass edge from %d->%d to %d\n",
+ e->src->index, e->dest->index, dest->index);
+ }
+ change = 1;
+ break;
+ }
+ }
+ }
+ return change;
+ }
+
+ /* Find basic blocks with more than one predecessor that only contain a
+ single conditional jump. If the result of the comparison is known at
+ compile-time from any incoming edge, redirect that edge to the
+ appropriate target. Returns nonzero if a change was made. */
+
+ static int
+ bypass_conditional_jumps ()
+ {
+ basic_block bb;
+ int changed;
+ rtx insn;
+
+ /* Note we start at block 1. */
+ if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
+ return 0;
+
+ changed = 0;
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
+ EXIT_BLOCK_PTR, next_bb)
+ {
+ /* Check for more than one predecessor. */
+ if (bb->pred && bb->pred->pred_next)
+ for (insn = bb->head;
+ insn != NULL && insn != NEXT_INSN (bb->end);
+ insn = NEXT_INSN (insn))
+ if (INSN_P (insn))
+ {
+ if (GET_CODE (insn) == JUMP_INSN
+ && condjump_p (insn)
+ && ! simplejump_p (insn))
+ changed |= bypass_block (bb, NULL_RTX, insn);
+ else if (GET_CODE (PATTERN (insn)) == SET
+ && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
+ && condjump_p (NEXT_INSN (insn))
+ && ! simplejump_p (NEXT_INSN (insn)))
+ {
+ rtx dest = SET_DEST (PATTERN (insn));
+ if (GET_MODE_CLASS (GET_MODE (dest)) == MODE_CC)
+ changed |= bypass_block (bb, insn, NEXT_INSN (insn));
+ }
+
+ /* Only consider first instruction of each basic block. */
+ break;
+ }
+ }
return changed;
}
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833