Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner <sabre at nondot dot org>]

On Mon, 15 Dec 2003, Daniel Berlin wrote:
> On Dec 15, 2003, at 5:07 PM, Chris Lattner wrote:
> >> Yes, you could do E-Path PRE, but it's harder to extend it to perform
> >> strength reduction or load speculation.
> >
> > Yup, and FWIW, LLVM uses an e-path based formulation of PRE on SSA
> > form.
> I remember looking at it.
> Did I mention we can do LFTR too :P.

Something I've never understood about the SSAPRE paper and subsequent
extensions: why does it make sense to incorporate things like LFTR into
PRE?  I understand the idea of integrating load/store motion into it, but
LFTR?  It seems like a simplish problem.  What am I missing?

> The only thing that really bothers me about SSAPRE is that you have to
> look at working implementations to figure out the algorithm, because of
> the bugs and "left out" pieces of the papers.  After about a year, i've
> got it pretty much down.

Yeah.  We had a group of people that tried to reimplement it from first
principles in LLVM, and they made a valiant effort, but never got it
working 100% robustly (largely due to time contraints), and it was never
integrated into the LLVM tree.  If you're interested in reading their
experiences, the report is here:
http://llvm.cs.uiuc.edu/ProjectsWithLLVM/2002-Fall-CS426-SSAPRE.pdf

> I should note that E-Path PRE doesn't really solve Zdenek's "problem"
> (that it requires variable names) with SSAPRE either.  You still need
> to determine equivalence of the expressions, you guys just do it with
> value numbers instead of variable names, (which we could do as well,
> given the information):

Yup.  Another issue is that PHI nodes can cause two non "lexically
identical" expressions to have dynamically equal values that PRE should be
aware of.  The current LLVM implementation of PRE doesn't handle this case
yet, so it's not as aggressive as it could be.  I need to get some time to
finish that missing piece up.  24 hour days are so limiting. :)

>
> "
>    ValueNumbering *VN;
>    // Ok, this is the first time we have seen the expression.  Build a
> set of
>    // equivalent expressions using SSA def/use information.  We consider
>    // expressions to be equivalent if they are the same opcode and have
>    // equivalent operands.  As a special case for SSA, values produced
> by PHI
>    // nodes are considered to be equivalent to all of their operands.
>    //
>    std::vector<Value*> Values;
>    VN->getEqualNumberNodes(Expr, Values);
> "

Exactly.  Note that in LLVM, the -load-vn pass automatically provides
value number information for loads too (using an arbitrary implementation
of the AliasAnalysis interface), allowing for load motion.  :)

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/