REG_USERVAR_P and GCSE

Jeffrey A Law law@cygnus.com
Mon Oct 19 11:58:00 GMT 1998


  In message < 199810170757.RAA02250@geoffk.wattle.id.au >you write:
  > 
  > The attached test program, compiled with egcs 1.1b (and my previous
  > GCSE fix) under powerpc-linux, with 'gcc -O2 x.c -o x', abort()s in
  > f2, when it should not.
  > 
  > I'll save everyone the long discussion of what GCSE is doing to the
  > program (although this is a great example of how GCSE works).  The
  > problem is that GCSE is creating a new register, register 94 when I
  > run it, which does not have REG_USERVAR_P set:
I spent some more time looking at this.  It's an interesting problem.

For a while I pondered separating out the two uses of REG_USERVAR_P -- in
some places we use it to determine if we should give warnings about
uninitialized variables.  In others it controls how we perform some
optimizations.

But further consideration led me to believe this won't really fix our problem
either.  Setting this magic bit on reg94 during copy propagation would just
paper over the problem.


I also looked into why loop didn't move blocks 7, 8 & 9 out of the loop.  It's
an old problem -- when we find block 9 (ends with a branch out of the loop) we
walk backwards to the first label, which happens to be just before block 9
(block 9 is a joiner for blocks 7 & 8).  The insn before the label does not
jump around block 9 which prevents us from moving the blocks out of the loop.
(project for someone, fix this.  Contact me for details).

And thinking about this more I'm convinced this would just paper over the
problem too.



The fundamental problem I see is for a reg with REG_USERVAR not set we seem
to be assuming that it can't be referenced in the loop before the assignment
we want to move.  The more I think about it, that seems wrong.

Let's pretend we have a register, 94, which is used as a source in a insn
which is not computing a loop invariant.  Assume that a definition of reg94
from outside the loop reaches this use of reg94.  This insn can not be moved
out of the loop (because it does not compute a loop invariant expression).

Then later in the loop, in a "maybe never" hunk of code we have an assignment
to reg94 from a loop invariant expression.

In that case I don't see what prevents that assignment from being moved out
of the loop.  Which is wrong.  It's a variation of fig 13.20 (a) from
Muchnick's book.

I'm also not convinced that loop_reg_used_before_p is really correct either.
I bet I could construct some goto infested loops to spoof
loop_reg_used_before_p.

Arggh!

I've never thought much of our loop invariant code motion (LICM) support, and
now I'm disgusted.

The real solution is to revamp loop.c to work on natrual loops found by
dominance analysis.  Then also use dominance analysis to avoid incorrect
LICM (see Muchnick).  Or perform LICM on an SSA representation of the loop.
per the algorithms in Morgan's book.

This would probably clean up other parts of loop.  find_and_verify_loops
becomes a shared routine with haifa-sched.c.  The maybe_never and related
stuff disappears (in favor of using dominance relationships).  Maybe more.
But this is probably not going to happen soon.


So, I think I'll install your patch until we can get loop rewritten.

jeff



More information about the Gcc-patches mailing list