[LLVMdev] choice between SSAPRE and bitvector aporach
dberlin at dberlin.org
Thu Apr 10 23:08:45 PDT 2008
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.
> > 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.
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.
More information about the llvm-dev