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

[Chris Lattner <sabre at nondot dot org>]

> > That is my point.  There is no reason to have an extra SSA_NAME memory
> > allocation at all.  If SSA is properly integrated into the representation
> > (ie, not something tacked onto an existing representation designed for
> > something else), then the expression implicitly defines the computed
> > value.

> An SSA_NAME is a decl, just like a variable declaration.
> so in non ssa LAND, we have
>  a = 10
>
> thats a tree:
>   MODIFY_EXPR
>   /      \
> VAR_DECL  CONST
>    A        10
>
> in ssa land we have
>
> a_2 = 10
>
>     MODIFY_EXPR
>     /         \
>   SSA_NAME    CONST
>   /       \      10
> VAR_DECL   2
>    A
>
> so the expression does implicitly define the computed value. Its really
> no different than  variable except we can associate the version number
> with a var_decl.

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.

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

This is what I mean by integrating SSA as a first-class feature in your
representation.  How would this be represented in tree-ssa?

> Its not much different than duplicating the var_decl for A and adding an
> integer field for the version number.  We chose this way because there
> is a ton of variable specific information like type, etc etc that we
> dont need to duplicate, and it doesnt impact any non-ssa parts of the
> compiler. It also makes it trivial to look at a cariable and tell if its
> in SSA form or not.

I understand why you chose to use the existing tree representation as the
basis of tree-ssa, but you have to admit that it has some serious
overheads and costs.  I am not at all convinced that you can eliminate all
of them, even if substantial effort is put towards slimming them down.

> > > > Adding capabilities like this at a late date will mean that a lot of code
> > > > will need to be rewritten.
> >
> > > I think virtually nothing will have to be rewritten to add this
> > > capability. I have to make a minor change to the way immediate uses is
> > > currently calculated/stored, but its pretty minor. And we'll have the
> > > capability to calculate/maintain def->use links without a lot of
> > > trouble.
> >
> > Ok, that makes sense.  :)
>
> We just cant do everything up front. We implement additional
> features/requirements things as we need them, and attempt to keep the
> architecture well enough designed to let us add these things, hopefully,
> without much trouble. Its just not worth spending time on something that
> someone might need in the future.

Ok, sounds good.  Also, you have a much better chance designing a _good_
interface if you have several use cases.  Your approach makes sense.

-Chris

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