Re: REG_USERVAR_P and GCSE

[Geoff Keating <geoffk at ozemail dot com dot au>]

> cc: egcs-patches@cygnus.com
> Date: Sun, 18 Oct 1998 23:47:06 -0600
> From: Jeffrey A Law <law@cygnus.com>

>   > 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:
> You really should have explained this a little more.  I spent about an
> hour starting at dumps to find out what was wrong.

Sorry about that.  I should have mentioned that the fastest way to
find the bug is to trace the generated assembler, only about 10
instructions actually get executed before abort() is hit.

> At the least you should have indicated more clearly:
> 
> 	* The code after gcse is correct
> 
> 	* A bad transformation is made by loop
> 
> 	* The path by which bad things happen.  ie, what path through the
> 	cfg needs to be taken for reg94 to have the wrong value.  This is
> 	critical for analyzing any kind of global optimization problem.
>
> The path in question is block 0 -> block 3 -> block 4.
> 
> At the end of block 4 after global cse reg94 will have the value
> (compare (reg83) (const_int 0)), which is correct.
> 
> After loop opts at the same location via the same path reg94 wiil have the
> value (compare (reg82) (const_int 0)), which is incorrect.
> 
> REG_USERVAR_P should definitely not be set for reg94.  reg94 is a compiler
> generated temporary.

Then it is loop.c that is wrong, not GCSE.

>   > and setting it in basic blocks 1, 3, and 9. (I don't know why it
>   > doesn't create it in bb 0 instead of bb 1 and 3, it might be
>   > worthwhile adding a little code to fix this).
> PRE is doing the right thing.  It tries to minimize the number of computations
> on every path through the cfg.  It does not try to do code hoisting into
> dominator blocks (aka unification).  Do not change gcse to do this.

OK, but it would be a nice thing to have, to keep code size down.

>   > Then loop.c is assuming that all non-user registers are only used
>   > in a loop after they are set, and this is not true in this case (it's
>   > used in block 5 after being set in block 3).
> But every path leading to block 5 has a set of reg 94.  And since reg94 is
> not set in the loop, it is a loop invariant and can be moved.

But the moving is being done from "outside" the loop!

To be (less) precise, although technically reg 94 is not set in the
actual looping bit of the loop, there is a set which is physically
inside the loop.  This set is moved by loop.c to (physically) before
the loop.  This would be OK, except that there is a use of the
variable before the set.  It is this use that goes wrong.

It's like changing

int x;
x = 1;
for (;;)
  if (x > 1) { x = 2; break; }

to

int x;
x = 1;
x = 2;
for (;;)
  if (x > 1) break;

>   > My patch is attached.  Another possibility is to set REG_USERVAR_P in
>   > GCSE when it creates new registers, in which case I strongly recommend
>   > changing the name to something like REG_LONGLIFE_P.
> Right now, I think your're just papering over the problem.  I also worry about
> the performance impacts of that change.

OK, I clearly mis-explained the patch.

The problem, in the most general terms, is this:

- GCSE can now move the SETs of variables, even non-user variables,
  between blocks and even out of loops.
- loop.c assumes that a non-user variable (that is not used in a loop
  exit condition) is not used in a loop before it is set.

These two things are mutually exclusive.  If it is possible to move a
SET of a variable out of a loop, then perhaps that SET is the one that
was setting the variable in a loop before it was used.  So loop.c's
assumption is wrong.

loop.c documents this as follows:

          /* In order to move a register, we need to have one of three cases:
             (1) it is used only in the same basic block as the set
             (2) it is not a user variable and it is not used in the
                 exit test (this can cause the variable to be used
                 before it is set just like a user-variable).
             (3) the set is guaranteed to be executed once the loop starts,
                 and the reg is not used until after that.  */

where (2) is the one that causes the problem.

So I deleted (2), since it is wrong.  The compiler can now create
non-user variables that are used in as complex a way as user
variables, so it is now not valid to make this kind of distinction
between user and non-user variables (I'm not sure that it was ever
valid).

This does have a performance impact, possibly a severe one.  Now
loop.c has to look at all variables, not just user variables, to see
whether they are used in a loop before they are set.

I don't see any way of avoiding this unless we want to keep track of
more information about which variables are born and die inside the
same basic block.  Of course, this is useful information, and it has
to be generated for local-alloc eventually anyway.

-- 
Geoffrey Keating <geoffk@ozemail.com.au>