Re: [tree-ssa] Lazy updating of stmt operands

[Andrew MacLeod <amacleod@redhat.com>]

On Fri, 2003-12-12 at 14:57, Chris Lattner wrote:
> > > I really can't emphasize enough how important this is.  For example, this
> > > information allows an efficient implementation of the LLVM
> > > Value::replaceAllUsesOf operation (which makes all users of a value use
> > > something else, think replacing 'add 2, 4' with '6').  The presence of
> > > this operation makes copy operations in the IR completely superfluous,
> > > along with "copy-propagation" passes (which either effectively have to be
> > > run between all transformations, or be built into all of them).  This
> > > simplifies transformations, makes code more maintainable, etc...
> >
> > Its not just maintainability that is at issue. Maintaining immediate
> > uses is not difficult.  Memory consumption rises dramatically when you
> > have a lot ssa names and uses and maintain those links. It was a
> > Significant memory win to only calculate immediate uses for the
> > ssa_names we cared about in CCP as opposed to all ssa-names.
> 
> How much memory consumption are we talking about here?  In LLVM, each
> instruction consumes space for itself (to hold the opcode, type, etc.),
> and 4 words for each operand.  The 4 words includes all use-def and def
> use information.  SSA can be a very light-weight representation.
> 

Its not the SSA space thats the memory consumption problem. gcc is now
unit at a time, so the entire program is read into memory as trees and
held there. the tree-ssa branch also uses GIMPLE, which creates more
trees. Then you add even a lightweight SSA and this simply magnifies any
additional memory that is used. Once the machine starts swapping, its
another order of magnitude on timing.  So we are trying to watch memory
very carefully.  That plus we are still working within the existing tree
data structures. I beleive our representation of SSA is quite
lightweight. It only becomes less so when you try to add a bunch of
stuff that isnt needed everywhere. 

> > We already have memory footprint problems, and maintaining def->use
> > links all the time is going to aggravate that situation even more. If
> > there are times when it is necessary, it ought not be hard to maintain
> > that information within our current framework. I see no reason to have
> > it present all the time when only some consumers need it...
> 
> If you're trying to work around the problem with caches and recomputation
> of information, I suspect that you are barking up the wrong tree.  That
> said, I don't know exactly what's going on in the tree-ssa world, so there
> may be complicating factors.
> 

The Cache isnt something we're trying to work around. Thats there to
prevent us from having to muck around in trees looking for things which
are operands. The stmt is in the form of trees, our "cache" is the
equivilent of your instruction. It consists of the operands plus looking
at the tree code(s) of the stmt. 

So we have 1 word for each operand. It points to the SSA_NAME in the
stmt tree which represents that ssa version. 

As far as Im concerned, we're not working around anything. Everything
works just fine. IF someone wants/needs the def->use inforation, it can
be built today. What we dont have is the ability to keep it up to date
for some period of time, simply because we've never needed it. If the
time comes that we do need it, it is not hard to add. 

Andrew