This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

non convergence of GCSE


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]