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

[Andrew MacLeod <amacleod at redhat dot com>]

On Sat, 2003-12-13 at 22:41, Chris Lattner wrote:
> On 13 Dec 2003, Andrew MacLeod wrote:
> > > > Yes, thats why CCP had to trim down its def->use chains to just the
> > > > variables it cared about rather than all of them. It was a large memory
> > > > savings to do that.
> > >
> > > How were you representing the information before?  Why was it taking so
> > > much space?
> >
> > memory and time spent constructing. The current representation is
> > reasonably efficient, but its still unneccessary space when you have
> > 45000 ssa versions and a list of uses for each one.
> 
> 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.


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

> compiler, this would not be a problem.  Instead it appears that you would
> rather "fix" the little, easy, "problems", even if that makes the compiler
> harder to work on and less efficient in the future.  Besides, mainline has
> it's own memory consumption problems.  It doesn't seem like that should be
> the ultimate target (an intermediate target is fine, but you should be
> aiming to do much better).

Appearences can be misleading :-) Everything we are doing is making the
compiler easier to maintain and more efficient in the future. Many of
them are a far cry from easy little fixes.  What we have is quite
flexible.

> 
> > None of this is really related to the issue that, for the moment, I dont
> > see a need to maintain def->use chains across the entire function for
> > all variables through all optimization passes.   Down the road, once
> > trees have been fixed and are more efficient, perhaps it wont be as much
> > an issue, but right now we are attempting to get the branch into shape
> > to make it compete with mainline, we can't afford to exacerbate the
> > situation.
> 
> 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. 

> savings.  Coupled with the fact that you claim def-use chains to not
> consume much memory, you are sending a confusing message.  If you are

They consume enough to cause an increase in memory usage, and time
required to calculate/keep up to date.  The confusion is probably due,
in part, to the fact that I do think we will eventually be keeping them
around for at least part of the compilation phase. I simply can't see
justification for it until we tackle the tree issue. Perhaps my opinion
will change before that, Zdenek is starting to run into cases where he
need immediate uses, which would bump the priority.

Our memory problems are not as bad as they were, and the immediate uses
data will probably not have the significant impact it did back when I
did the original work in august, or whenever it was. That has not been
verified tho.  I may take a look at it next now that everyone seems so
interested in it :-)

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

Andrew