Re: [tree-ssa] Memory usage in compute_immediate_uses

[law at redhat dot com]

In message <20030916231447.GA2427@nevyn.them.org>, Daniel Jacobowitz writes:
 >Does this information ever live over a collection anyway? 
Not at the current time, though it might one day.  It's hard to tell
until we have more optimizers in place.  For example, it's not terribly
unusual to have CCP & DCE share def-use information.  However, our DCE
implementation doesn't use def-use chains at all.


 > Especially
 >if so, another data structure might be more efficient.  Something which
 >only supported adding and iterating; you could use a chunked array
 >which allocated new chunks instead of discarding and copying.
Well, it depends on how they get used later.  If you're simply tossing
them aside from one pass to the next, then yea, something like obstacks
might work better than garbage collected varrays.

However, if you're going to build them once for a series of optimizers,
then you're going to need the ability to keep this bloody things up
to date and potentially have them managed across GC points.

Again, it's just not clear yet if def-use chains are going to be all
that useful to use outside of CCP.  Most of the stuff you can do with
def-use chains can be done with use-def chains -- often without 
incurring a compile-time performance penalty.

 >As for size: this isn't the ideal quantity to measure, but it was the
 >quickest hack.  The distribution of
 >  max (number of uses attached to any one statement in a function)
 >with one sample per function:
 >  3223 had no statements with uses at all.
 >  27557 had a max of 1-4.
 >  14334 had a max of 5-10.
 >  7421 had a max of 11-100.
 >  236 were between 101-678.
 >  2 had 1274 (probably the same file in two stages).
 >  One greater than 2K: 4230, in interpret.cc.
 >
 >This suggests that a varray of size ten is not a good choice, but that
 >a varray of another size would not be a much better choice.
Yup.  I expected a stronger tendency to smaller numbers of uses attached
to each statement.   Ugh.  It's nowhere near as clear cut as I expected.

Jeff