Re: Question re: SSA Aggressive Dead Code Elimination

[Daniel Berlin <dan at cgsoftware dot com>]

Daniel Berlin <dan@cgsoftware.com> writes:

> 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.

Sigh.
I didn't meant that, the b=b+c is always pointless.
That'll teach me to reread my drafts before sending them.
> 
> 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.
Same here.
> 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

-- 
"When I woke up this morning my girlfriend asked me, "Did you
sleep good?"  I said, "No, I made a few mistakes."
"-Steven Wright