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

[Chris Lattner <sabre at nondot dot org>]

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.

> The code is in the sources :-)

Sorry, but I already have a compiler to work on.  :)   I'm just here to
spout very opinionated ideas.  :)

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

Perhaps you should be looking into this, rather than not having def-use
chains?

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

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

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

If you are already hitting swap, the problem is here now.

> 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
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
hitting swap _now_ with such simple transformations, it does not seem
likely that more aggressive analyses and transformations will be feasible.

Adding capabilities like this at a late date will mean that a lot of code
will need to be rewritten.

-Chris

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