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

[Andrew MacLeod <amacleod at redhat dot com>]

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.

We reference and operand by pointing to the SSA_NAME if the defining
stmt. there is no allocation involved for a reference.

> 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.

> (1+2); Y = X+X;", which is following LLVM instructions:
> 
>   %X = add int 1, 2
>   %Y = add int %X, %X
> 
> Ignoring types, which every value has, the following are the memory
> objects we have to allocate and process:
> 
>    CONST1     CONST2
>         \     /
>           ADD
>           | |
>           ADD
> 
> ie, there are _4_ memory allocation, ones for each instruction, and one
> for the two constants being referenced.  There are no intermediate objects
> used to represent "SSA_NAME"s or variables being declared, etc.  An
> instruction which computes a value is directly pointed to by operands.
> There is no need to go through an auxillary symbol table to traverse
> def-use or use-def chains.

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.

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

 Example Diego? You added the multiple def support...

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.

> 
> 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.


  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.

Yes, perhaps the MODIFY_EXPR's could be considered superfluous, but
thats really the only significant difference. We maintain the root
variable in the SSA_NAMEs so we can map the epressions back to the
original variables in the program:

Its not much of a stretch to say that we would have exactly the same
thing as you if we rolled all the SSA_NAME information into our
MODIFY_EXPR node. I happen to like it explicit a little better
personally.


I presume you keep information about the original defining variable in
the operation node, like your ADD, which is the same information we are
keeping in our SSA_NAME by pointing at a DECL. Otherwise you would have
a hard time generating debug information. So the amount of information
hanging around is not significantly different, you just have slightly
less duplication and pointers.


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

Andrew