This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
non convergence of GCSE
- To: gcc-patches at gcc dot gnu dot org
- Subject: non convergence of GCSE
- From: grahams <grahams at rcp dot co dot uk>
- Date: Sun, 31 Oct 1999 21:10:04 +0000
Jeff
First a little history
======================
Many moons ago probably back in egcs 1.x days I instrumented GCSE
to determine the typical convergence when running multiple passes.
I modified MAX_PASSES to 10 and modified the gcse.c to output
the # of GCSE passes required for each routine.
When I examined the gcse dump file I found that for the majority
of routines GCSE converged within 3 passes, with the odd routine
taking 5 passes. No routines failed to converge.
Repeated on latest gcc from CVS
================================
I just tried this on the latest gcc and found that a very significant
number routines were not converging after 10 passes.
I changed MAX_PASSES to 100 and found that routines were either
converging after 2/3 passes or never converged.
I investigated why convergence wasn't occurring and
tt turned out that the failure to converge was an
interaction the following two blocks of code between
pass N and pass N+1.
the first block of code is from cprop_insn()
/* Handle normal insns first. */
if (GET_CODE (insn) == INSN
&& try_replace_reg (reg_used->reg_rtx, src, insn))
{
changed = 1;
const_prop_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
regno, INSN_UID (insn));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
/* The original insn setting reg_used may or may not now be
deletable. We leave the deletion to flow. */
}
and the seconed block of code is from pre_delete().
if (TEST_BIT (temp_bitmap[bb], indx))
{
set = single_set (insn);
if (! set)
abort ();
/* Create a pseudo-reg to store the result of reaching
expressions into. Get the mode for the new pseudo
from the mode of the original destination pseudo. */
if (expr->reaching_reg == NULL)
expr->reaching_reg
= gen_reg_rtx (GET_MODE (SET_DEST (set)));
/* In theory this should never fail since we're creating
a reg->reg copy.
However, on the x86 some of the movXX patterns actually
contain clobbers of scratch regs. This may cause the
insn created by validate_change to not match any pattern
and thus cause validate_change to fail. */
if (validate_change (insn, &SET_SRC (set),
expr->reaching_reg, 0))
{
occr->deleted_p = 1;
SET_BIT (pre_redundant_insns, INSN_CUID (insn));
changed = 1;
gcse_subst_count++;
}
The scenario was as following
GCSE pass N
Block 1 - replaces the use of register R1 in insn I
with its equivalent constant (i.e. SYMBOL_REF)
Block 2 - creates a new reg R2 which also uses the
same SYMBOL_REF
in pass N+1
Block 1 - replaces the use of register R2 in insn I
with its equivalent constant (i.e. SYMBOL_REF)
Block 2 - creates a new reg R3 which also uses the
same SYMBOL_REF
in pass N+2
Block 1 - replaces the use of register R3 in insn I
with its equivalent constant (i.e SYMBOL_REF)
Block 2 - creates a new reg R4 which also uses the
same SYMBOL_REF
This sequence continues until GCSE gives up when it
has reached MAX_PASSES.
I have identified a fix which restores convergence.
==================================================
The following comment and code from code cprop_insn ()
hints that cprop_insn() shouldn't be looking at any
registers created by GCSE.
/* Ignore registers created by GCSE.
We do this because ... */
if (regno >= max_gcse_regno)
continue;
Unfortunately this test is useless because at the
start of EACH pass max_gcse_regno is updated via
max_num_regs() and will thus include all the registers
created in any previous passes of GCSE and hence
regno will always be < max_gcse_regno.
My fix introduces a new variable first_gcse_regno which
is initialized to max_num_regs () prior to the first GCSE
pass and then in cprop_insn() the test is modified to test
against this new variable and not max_gcse_regno.
/* Ignore registers created by GCSE.
We do this because ... */
if (regno >= first_gcse_regno)
continue;
I have these changes to my local tree and performed
a boottsrap. The GCSE convergence is now back to as
it was in egcs-1.x.
Graham