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

[Daniel Berlin <dberlin at dberlin dot org>]

On Dec 15, 2003, at 5:07 PM, Chris Lattner wrote:

> On Mon, 15 Dec 2003, Daniel Berlin wrote:
> > > There are ways around this, but the SSAPRE papers have several fairly
> > > severe bugs and ommissions in them.  This information is not really
> > > needed
> > > for implementing PRE on SSA form.
> >
> > 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.
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.

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):

"
  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);
"