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

[Chris Lattner <sabre at nondot dot org>]

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.

> > The point is that you are trading off a fundamental part of SSA form for a
> > temporary space efficiency issue.  If you fixed the basic problems with
> > your representation, and treated SSA like a first class citizen in the
>
> Fixing the "basic problem" (which is probably memory usage of trees at
> this point) is an expansive task that will be tackled in due time, when
> either its significance rises to the point where one of us *has* to take
> care of it, or when somone else is motivated to take on the task. That
> is unlikely until we manage a merge with mainline, (or mainline takes
> care of it :-). We're doing a pretty decent job now at keeping the
> tree-ssa branch from being much worse than mainline is. And we're still
> doing more.  None of the things we are doing are at the expense of the
> implementation.

My point is basically that if it is such a big problem that it prevents
you from using important data structures, maybe it should be looked into
_now_ instead of waiting for someone else to fix it.  That said, I
understand how it's not reasonable to expect someone to pick it up in a
volunteer project, unless it's an extremely pressing need.

> > This is related insofar as you are deciding that you need to save memory
> > by not representing a fundamental part of SSA form, to provide a memory
>
> 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...

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

-Chris

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