[tree-ssa] Memory usage in compute_immediate_uses

[Daniel Jacobowitz <drow at mvista dot com>]

This grew out of a conversation with Daniel Berlin about SSA-PRE's memory
usage.  It turns out PRE doesn't need compute_immediate_uses after all and
he's removed the call in a later snapshot than I had on disk.  But other
passes (CCP at least, right now) use this, so I'm writing it out anyway.

Here's a couple of calls to compute_immediate_uses that I instrumented:

Start allocated is now 9986284
compute_immediate_uses: 9 bbs, 16 uses, max of 7 uses per bb
compute_immediate_uses: max uses for one statement was 1
Allocated is now 9987392

Start allocated is now 9896764
compute_immediate_uses: 6 bbs, 11 uses, max of 7 uses per bb
compute_immediate_uses: max uses for one statement was 4
Allocated is now 9896848

Start allocated is now 11256992
compute_immediate_uses: 219 bbs, 884 uses, max of 52 uses per bb
compute_immediate_uses: max uses for one statement was 10
Allocated is now 11261968

Start allocated is now 71906876
compute_immediate_uses: 1554 bbs, 5402554 uses, max of 99990 uses per bb
compute_immediate_uses: max uses for one statement was 1
Allocated is now 168254664

The absolute maximum on the size of the varray for any block in my test
(interpret.cc from libjava) was ten.  The vast bulk were one.  We allocate a
varray with an initial size of ten elements.  The memory waste in that is
criminal...

Of course, we don't want to undershoot too far.  ggc_realloc a couple of
times and you're hurting.  But if someone could sample a larger set of code,
I suspect we could cut it at least in half.

And just a question.  Sometimes all the immediate_uses varrays are already
allocated.  Nothing ever removes from the immediate_uses list.  So...
doesn't any call to compute_immediate_uses after they've already been
computed put duplicates on the list?  It's not a problem now that CCP is the
only thing using it, but while SSA-PRE was using it that must have hurt
performance elsewhere.

-- 
Daniel Jacobowitz
MontaVista Software                         Debian GNU/Linux Developer