Re: Question re: SSA Aggressive Dead Code Elimination

[Daniel Berlin <dan at cgsoftware dot com>]

Michael Matz <matzmich@cs.tu-berlin.de> writes:

> Hi,
> 
> On Wed, 27 Jun 2001, Daniel Berlin wrote:
> 
>> The initial removing of the edge isn't strictly wrong, as long as you
>> update the phi nodes accordingly.
> 
> Well, suppose, you initially had this code:
> a=b+c;
> if (a>d) { b=b+c; }
> return b;
> 
> which is the back-translated RTL.  If you in this situation remove any
> edge resulting from the compare, there is no way, that you still have the
> same semantic as the above code.

D'oh. Your right.

I see what happens now that I see the C code.

We notice that b=b+c is pointless, iff the compare is pointless.

The dead code elimination must be deciding that since a==b
iff (a>d), it can delete the b=b+c, and replace it with b=a.
It then decides that a>d all the time (through an incorrect decision)
and rewrites the code as:

a=b+c;
return a;

Or, I think what we ended up with is:

a=b+c
if (a>d) { }
return a;
Or something like this.
I think it's really:
a=b+c
goto next;
next:
return a;
to account for the unconditional jump.

So you are completely correct, it's been transformed incorrectly.


>   That is why the removing of the edge
> really was wrong from the beginning.
> SSA-transformed and optimized this should be:
> a=b1+c;
> if (a>d) {;}
> b2 = phi[b1, a];
> return b2;
> 
> which translated back from SSA (and useless copies coalesced away) will
> get:
> a=b+c;
> if (a>d) b=a;
> return b;
> 
> I.e. you really need that edge up to the end (because that is the one on
> which you insert a copy insn to eliminate the phi node, which because of
> the non-criticality of that edge gets placed into the empty block).  If
> you remove the edge, there is exactly one path from ENTRY to EXIT, whereas
> originally there were two, doing different things, clearly not the same.
> So my point is, that even if you fiddle with the PHI node, to make
> everything correct SSA again, it nevertheless will not produce code having
> the same semantic as the original one, which kind of breaks conservative
> optimization approach ;-)

Don't you just  love accidental aggressive optimization?

However, of course note that we don't need the edge if we can prove d is
constant, but IIRC Jeff said it was live on entry, which tells me it
was an argument.

> 
> 
>> Right.
>> In no case can you just remove edges. You either have to update the
>> phi nodes approriately, or not remove the edges.
> 
> Right too ;)  In this case not removing the edge.

> 
> 
> Ciao,
> Michael.

-- 
"Four years ago...  No, it was yesterday.
Today I...  No, that wasn't me.
Sometimes I...  No, I don't.
"-Steven Wright