Over-eager code elimination?

Over-eager code elimination?

[Dan Sheridan]

Running test-linearize on some of my code, I seem to be losing an
assignment after a break.

In this minimal test code, y should have the previous iteration's value
of x, so the value returned is the difference between the final two
values from fetch():

int fetch(int);
int test(int v) {
  int x, y;
  for (int i=0; ; i++) {
    x = fetch(i);
    if (v < x) break;
    y = x;
  }
  return x-y;
}

test-linearize produces:
test:
.L0xb7db300c:
        <entry-point>
        br          .L0xb7db3034

.L0xb7db3034:
        call.32     %r2 <- fetch, $0
        setlt.32    %r5 <- %arg1, %r2
        dead        %r5
        br          %r5, .L0xb7db3084, .L0xb7db3034

.L0xb7db3084:
        dead        %r2
        sub.32      %r11 <- %r2, %r2
        dead        %r11
        ret.32      %r11

So it thinks that both x and y are in %r2. However, if y is initialised,
the assignment happens as expected.

Any ideas?

	Dan.

Re: Over-eager code elimination?

[Linus Torvalds]

On Tue, 20 Feb 2007, Dan Sheridan wrote:
> 
> So it thinks that both x and y are in %r2. However, if y is initialised,
> the assignment happens as expected.
> 
> Any ideas?

Heh. I think you found a nasty nasty bug.

I didn't look very closely, but using "-vv" shows the loads of 'y' have 
been turned into lnop's, which means that the dominance analysis decided 
that it could just replace all uses of 'y' with the (single) assignment to 
it. Basically, it decides that the 

	y = x;

assignment always dominates the use ("return x-y"), so it will happily 
have turned it into "return x-x" (and then it *should* have simplified 
that, but didn't - it's not a simplification pattern I ever added).

Looks like some totally nasty, and probably very fundamental dominance 
analysis bug. I *suspect* that what happens is simply that we create a 
phi-node for the load (rewrite_load_instruction), but then since there is 
only a single phi source associated with it, we simplify it to just use 
the pseudo directly.

Which is why adding the initialization hides the bug: suddenly there is 
more than one dominator, and the bogus optimization goes away.

(It's possible that the optimization happened even before the PHI node was 
even created: we have several layers of this, and I think you may even be 
hitting the "we have a single def for this variable, so replace all loads 
with that def even without doing any dominance analysis AT ALL" case)

I'll try to look at it, but I may not have the time. It looks like a 
fairly fundamental thinko, though.

		Linus

Re: Over-eager code elimination?

[Christopher Li]

On Tue, Feb 20, 2007 at 09:30:53AM -0800, Linus Torvalds wrote:
> 
> Looks like some totally nasty, and probably very fundamental dominance 
> analysis bug. I *suspect* that what happens is simply that we create a 
> phi-node for the load (rewrite_load_instruction), but then since there is 
> only a single phi source associated with it, we simplify it to just use 
> the pseudo directly.
> 
> Which is why adding the initialization hides the bug: suddenly there is 
> more than one dominator, and the bogus optimization goes away.

I think there is two problem here:

The first one is minor, 'y' can be used without initialized. 
We always give the 'y' the value as its last defined value.
Since not initialized value is not defined, I guess use the last
define one should be fine.

The second one is the bigger issue:

In simplify_one_symbol, we find out that the address of 'y' is not
taken, and y has only one store. So we happily go ahead replace
all the load with the define pseudo.

	/*
	 * Goodie, we have a single store (if even that) in the whole
	 * thing. Replace all loads with moves from the pseudo,
	 * replace the store with a def.
	 */

Notice that in this path, it uses convert_load_instruction instead
of rewrite_load_instruction. It does not do the phi stuff.

> (It's possible that the optimization happened even before the PHI node was 
> even created: we have several layers of this, and I think you may even be 
> hitting the "we have a single def for this variable, so replace all loads 
> with that def even without doing any dominance analysis AT ALL" case)

That is exactly what happened. But even if we use phi node here, it is
not correct. Because when it using the value of 'y', it is not using the latest
value of the phi node 'x'. It is using a old version of 'x' when "y = x;" happens.

It seems that we have to use a copy instruction here to save the old value of 'x'.

> I'll try to look at it, but I may not have the time. It looks like a 
> fairly fundamental thinko, though.

I take that as "I hope somebody else fix this so I don't have to." ;-)

Chris