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

[Andrew MacLeod <amacleod at redhat dot com>]

On Fri, 2003-12-12 at 15:01, Chris Lattner wrote:
> On 12 Dec 2003, Andrew MacLeod wrote:
> > On Fri, 2003-12-12 at 14:46, Chris Lattner wrote:
> > > > > hardly; you still must scan all statements to find the uses, so I don't
> > > > > see where you would want to get the extra efficiency.
> > > > >
> > > > Scanning stmts is very cheap.
> > >
> > > You must not have run across programs that have PHI nodes with thousands
> > > of operands...
> >
> > 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.  The code is in the
sources :-)
> 
> I have said it before (http://gcc.gnu.org/ml/gcc/2002-08/msg01555.html),
> but I still think that the reason that GCC & tree-ssa have all of these
> memory problems is the insistence on using "tree" structures for something
> that should be _much_ simpler and lighter-weight.  LLVM is very efficient,
> has a small memory footprint, and all of the allocation/deallocation is
> explicit (no GC), which is made possible by a trivial ownership model.  I
> don't see how you can do these things with a tree representation.
> 

There is a longer term plan to compress trees into a more rational
memory consumption format, none has gotten to it yet. We are far more
likely to make trees more efficient than we are to throw them away to
replace them with something equivilent. 


> > > > And if you do need it over a chain of optimizations, do it once, and
> > > > then keep the info up to date/.  You'll be a lot better off I think
> > >
> > > Isn't that the whole idea?
> 
> > Yes, but I am suggesting we dont keep it around all the time since many
> > optimizations do not need it, and it costs memory. The ones that do need
> > it can build that info for the variables it cares about more
> > efficiently.  CCP cares about a different set of variables than the loop
> > optimizer likely does.
> 
> I'm really confused by all of this talk about memory footprint.  How are
> you guys representing def-use chains?
> 
Thats not the issue. Its not that memeory inefficient, it just takes
memory, and there is enough being consumed at the moment that we're
being careful when we allocate memory. Even mainline has some problems
now on larger programs, we use a bit more memory, partially due to
GIMPLE, and then SSA uasea bit more. It means we trigger the memory
problems earlier than mainline does.  

Memory inefficiancy of trees is known, and since its becoming an issue,
it will have to get visited and fixed. 

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.

Andrew