[LLVMdev] choice between SSAPRE and bitvector aporach

[Daniel Berlin]

On Fri, Apr 11, 2008 at 12:02 AM, Vikram S. Adve <vadve at cs.uiuc.edu> wrote:
>
>  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.
yes

>
>
>
>  > 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.
Factored Use-Def.

See, e.g., http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=323280

Because of how they work (phi nodes but no renaming of variables) they
do not allow overlapping live ranges.
Most also avoid the need to do out-of-ssa, they can just drop their
chains and phi nodes.