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

[Chris Lattner <sabre at nondot dot org>]

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?

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.

> > > The uses/defs are all cached.
> > Don't caches take space?

> Yeah, but thats already consumed. If you are suggesting we replace our
> entire operand implemenation with FUDs, I'm pretty sure thats not going
> to happen :-)

LLVM doesn't use FUD chains, nor would tree-ssa.

> So our operand cache takes up space. Adding def->use chains takes up
> even more space

The point is that the cache would be irrelevant if you representation had
the information you needed directly in it...

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

-Chris

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