[LLVMdev] choice between SSAPRE and bitvector aporach

[Vikram S. Adve]

On Apr 4, 2008, at 8:28 PM, Daniel Berlin wrote:

> On Fri, Apr 4, 2008 at 5:58 PM, Vikram S. Adve <vadve at cs.uiuc.edu>  
> wrote:
>>
>>
>> Dan,
>>
>> Doesn't the paper also assume the invariant that phi operands are
>> effectively dead after the Phi, which is true right after SSA is
>> constructed, but potentially not after transformations?
> I do not recall this being *required*. It certainly will miss
> optimizations if you have a pruned form (there are still testcases in
> gcc bugzilla i believe), but i do not believe it will generate
> incorrect code.
> I could be misremembering.
> The main annoying invariant i recall is that it requires SSA live
> ranges of original program variables do not overlap in order for ESSA
> renaming to come out correct.    Even simple optimizations on renaming
> forms will generate destroy this invariant.

Actually, what I was describing was equivalent to this.

>
> It certainly can be made true as a pre-pass through further renaming.

Yes, but that would just undo the benefits of some of the  
optimizations that can make such live ranges overlap, e.g., GVN.  So  
it seems undesirable to do this.


> It is also trivially true of all non-renaming FUD chain variants of  
> SSA

I'm not sure what you mean by 'FUD' here.  In any case, I think the  
problem is non-trivial.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/