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

[Chris Lattner <sabre at nondot dot org>]

On 15 Dec 2003, Andrew MacLeod wrote:
> On Mon, 2003-12-15 at 15:06, Chris Lattner wrote:
> > What you are saying is that instead of _one_ memory allocation to
> > represent a logical operation, you are uisng 4 (VAR_DECL, SSA_NAME, "2",
> > MODIFY_EXPR).  Even if some of these are shared, doesn't this make
> > traversing the representation really expensive and cache unfriendly.  You
> > also didn't show how a variable is referenced as an operand.

> The number of memory allocations isnt the point when we are talking
> about how well integrated something is. the VAR_DECL, SSA_NAME. "2",
> MODIFY *could* be implemented as a single allcoation if we so chose, but
> it wouldnt take much less memory, and it wouldnt make anything else
> better or easier. We still need all the information in those various
> nodes.  There is a minor amount of duplication (ie, MODIFY and VAR_DECL
> both have types), but thats not where we have siginificant memory
> lossage. SSA_NAMES themselves are fairly efficient and only exist once.

Ok.  I was just trying to point out a deficiency in your system that I
perceived.  If you don't agree, then I certainly will not try to force the
point.  I'm just trying to point out stuff that might become a problem
down the line as early as possible, as opposed to letting you discover the
problem later when it may be harder to recover.  I'm truly not trying to
start a pointless flamewar. :)

> > When I said that the SSA form wasn't integrated as a first-class entity,
> > this is _exactly_ what I meant: your SSA form is added on top of the
> > existing trees.  Contrast this with LLVM.  Consider the expression: "X =
>
> Is no more a second class citizen than any other decl tree element we
> add like a var_decl or a parm_decl.

Uhm, exactly. :)

> we keep our expressions shorter. we use temporaries to define the result
> of a MODIFY.  When you boil away all the minor detail crap, The single
> thing of significance which is different between what you are doing and
> what we are doing is that you don't have the equivient of a
> MODIFY_EXPR.  You make the modify implicit in the defining operation.

Uhm.  Ok, if you boil away everything but that, then yes, you're right.

> How do you deal with a stmt which has more than once DEF?  We have
> precious few, but they do exist.

We don't.  They don't exist in SSA form.  The only feature we have not
implemented yet is inline assembly, and for that I plan to use lvalues
("by reference parameters") to represent the multiple outputs possible
from a single "asm statement". Everything else is fully implemented in
LLVM, and we have not had a problem so far.

> We also deal with virtual definitions and uses to handle non-scalar or
> non-ssa interactions/side-effects, and there can be multiple virtual
> definitions on a given stmt.

LLVM does not have this complication.

> > This is what I mean by integrating SSA as a first-class feature in your
> > representation.  How would this be represented in tree-ssa?
>
> a_2 = 1 + 2
> a_3 = a_2 + a_2
>
> we have 2 SSA_NAMES, allocated once.
>
>    SSA_NAME   and     SSA_NAME
>     /    \             /   \
>    a      3           a     2
>
> both of which could have been a single allocation if we chose, but it
> turns out to be less memory to allocate them as SSA_NAMEs as Diego has
> already pointed out.

So, you're saying that it's better than using VAR_DECL's directly, which,
of course, carry a lot of baggage that you're not interested in.  Why use
them at all?

>
>   MODIFY_EXPR
>    /      \
>  a_2      PLUS
>           /   \
>          1     2
>
>   MODIFY_EXPR
>    /       \
>   a_3      PLUS
>           /    \
>         a_2    a_2
>
> So we have a total of 8 allocations. a_2, a_3, 2 MODIFY_EXPRS, 2 PLUS
> and 1, and 2.

Don't forget the VARDECL for A.  Also note that you changed the expression
that I gave you.  In LLVM, there is no memory difference at all between "X
=(1+2); Y = X+X;" and "X = (1+2); X = X+X;", but in tree-ssa you just
elided an extra VARDECL and SSANAME, so your count is off.

> I presume you keep information about the original defining variable in
> the operation node,

No, we don't.  We don't have any concept of "defining variable" or
"versions" at all.  Though all SSA construction papers talk about building
versions of source variables, once you start doing transformations, that
idea becomes quickly meaningless.  I think you guys have already run into
this in your "out-of-ssa" pass.

> Ultimately, I dont see much difference other than implementation
> details...

I really do not want to start a flamewar here or step on people's toes.
The reason this thread started is because I think that use-def and def-use
information are both _critical_ to SSA optimizers, and it seemed at that
point that you were avoiding building this information due to unrelated
memory problems elsewhere in tree-ssa.  That's all!

-Chris

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