Varray memory consumption strikes back

[Jeffrey A Law]

On Sat, 2004-09-04 at 15:33, Jan Hubicka wrote:
> > On Sat, 2004-09-04 at 03:59, Jan Hubicka wrote:
> > > and the proposed patch to make varrays allocatable either in GGC and
> > > memory flag has been rejected and you mentioned to have better sollution
> > > in prototype stage (moving away from varrays to sane datastructures and
> > > improving them at the same time).
> > Well, I haven't had time to pick it up, but it wouldn't be terribly
> > hard for you to do so.  I would prefer reducing the amount of
> > varrays we carry around as opposed to bypassing our memory allocation
> > system design.
> 
> Yes, this is my prefference too and I did some work on this already too.
> However it is depressing to see that the amount of varrays in the code
> is increasing very quickly and consistently.
The varrays are a natural way of building unwindable state into
the optimizer, which in turn avoids the horrible path following
behaviors found in CSE.  However, there are ways to reduce the
number of varrays we allocate.

One such way is to recycle them as I've already suggested.

ggc_free-ing them may be a solution as well, but I have my
reservations given my experience with this code already.

Another would be to have a single varray for expressions rather
than having a varray per block for expressions.  Each element in
that varray would have the expression and the block associated
with the expression.

In the finalizer, you pop elements off that varray as long as
their block matches the block we are leaving.  Remove each
of the popped elements from the available expression hash
table.

The advantage of that scheme is that we allocate fewer block
local varrays.  However, the one varray we do allocate will
tend to be large and we have to allocate a two word element
for each entry in that varray (pointer for the expression
and a pointer for the block containing the expression).  It's
not clear if that will be a notable win over what we've got
or what has been proposed.

I haven't prototyped that code, but I don't think it would be
terribly hard to do so and run some experiments to see if it's
a worthwhile direction.

I believe you would do something similar with block local
stmts_to_rescan and vrp_variables.  You might even use a 
bitmap for vrp_variables.

block_defs ought to go away in the future.  The only reason we
track the current definition of a variable is for the old style
of jump threading.  It should be possible to rewrite the code
which determines when a block has a threadable COND_EXPR which
does not rely on maintaining the current definition of any variable.

The block local const_and_copies and nonzero_vars are trickier to
make go away.

 
> > What needs to happen now is to expand that simple table of SSA_NAMEs
> > to be a table of SSA_NAMEs and their global properties (for example
> > their equivalences and nonzero status indicators).
> 
> How this is different from putting this directly into SSA_NAMEs?
Not significantly so.  Though in general I don't like the idea of
stuffing more crap into the tree structures.  


> 
> If you don't like varrays in the normal memory, would turning the
> stack-like datastructures above to obstacks (or newly invented
> friendlier stack datastructure perhaps with fixed object size)
> and array-like datastructures to simple C arrays (where we would lose
> bounds checking) or newly invented bound checked arrays without growing
> facility make any sense to you?
Again, the fundamental problem is definable lifetime and the fact
that most objects in GCC do not have a definable lifetime.  Hell,
one could even make the claim that no objects in GCC have a
definable lifetime because of the rats nest of pointers we have.

jeff