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

[law at redhat dot com]

In message <Pine.LNX.4.44.0312121357450.16876-100000@nondot.org>, Chris Lattner
 writes:
 >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 believe the core problem was that the computed jumps resulted in 
insanely large PHIs and an insanely large number of PHIs.  The resulting
use-def information was correspondingly large.


 >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.
In this particular case, I don't think that the problem is using the
tree structures.

Given infinite time and resources we might not have started with trees.
However, starting with trees gave us somewhere to stand while we dealt
with a lot of other issues and got us to a point where we could actually
do some interesting things a lot faster.

It may be the case that we won't always use trees.  Then again, someone
may come along and significantly rework trees to make them reasonably
efficient.



Jeff