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

[Andrew MacLeod <amacleod at redhat dot com>]

On Mon, 2003-12-15 at 14:12, Chris Lattner wrote:
> On 15 Dec 2003, Andrew MacLeod wrote:
> > > It seems to me that the problem is that SSA is a second class citizen in
> > > your representation, something that is hacked onto the side.  Maybe if it
> > > were better integrated, some of the problems would go away.  There is no
> > > reason for the SSA_NAME's to be distinct memory objects from the
> > > expressions.
> >
> > Actually, SSA is very well integrated. The addition of SSA requires not
> > much more than PHI nodes and SSA_NAME tree nodes, which are
> > fundamentally the same as a variable, except they add a version number.
> > I wouldn't call SSA a second class citizen at all.
> 
> 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.

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.


> > As far as def->use chain go, the architecture is modular enough that it
> > is quite trivial to add them, and maintain them if need be. I haven't
> > seen a need to keep them around all the time yet, and since we haven't
> > gotten to the tree memory issue yet, I dont see why would try to keep
> > them around and up to date all the time when there are very few
> > consumers of it so far.
> 
> Ok, I guess its a reasonable approach just to make them available and then
> see how often it gets used, as long as the current implementation is
> efficient enough that people will not avoid using it when it makes
> sense...
> 

Well, when it does become a problem, thats when we tackle the efficiency
of the implementation :-)

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

Thats all :-)

Andrew