Language-independent functions-as-trees representation

[Jason Merrill]

On Fri, 23 Aug 2002 22:25:14 -0700, Per Bothner <per@bothner.com> wrote:

> Zack Weinberg wrote:
>> I'm a little concerned about memory consumption if we have to have a
>> COMPOUND_EXPR for (nearly) every statement, on top of whatever sort of
>> thing the statement itself is.  A two-operand EXPR node is 24 bytes,
>> which currently gets rounded up to 32 (I plan to fix that).
>
> Two possible solutions:
>
> We could have a variable-sized COMPOUND_EXPR (a la TREE_VEC).
> A chain of 20 "statements" is a single COMPOUND_EXPR with 20
> "operands".  Compact, fast, great locality, easy to traverse
> in either direction.  Not so easy to build incrementally
> - but for that a parser can use a temporary obstack, or
> temporary TREE_LIST, and then re-cycle the TREE_LIST at the
> end of the block.  Or just use 2-operand COMPOUND_EXPR, and
> recycle them at the end of the block.
>
> This may be awkward for some optimizations, but its more of a
> coding issue than a performance issue, I believe.  E.g. an
> optimization that does major re-organization should perhaps
> just copy the entire tree, and throw away the old one.  If you
> do only a few insertions, use an extra 2-operand COMPOUND_EXPR.

This does sound awkward, particularly for simplification.  In the code I've
been writing which uses 2-operand COMPOUND_EXPR, simplifying a complex
statement just means replacing it with a COMPOUND_EXPR; later, we go
through and flatten the COMPOUND_EXPRs so that they're only
right-recursive.  Of course, this last step could replace them with a
variable-sized one instead, but this would add complexity in order to avoid
doing it too early.

Allocating and then throwing away all these COMPOUND_EXPRs would use even
more memory in the short term than just using the 2-operand forms, since we
don't do GC until we're done with the function.  We might be able to reduce
the wastage by using a varray for temporary storage.

Deleting a statement could be handled by replacing it with empty_stmt_node
until we get around to compacting.

Of course, even an array involves more memory use and pointer chasing than
just using the TREE_CHAIN.

I don't see any real benefit to random access.

> Alternatively, we can just use the TREE_CHAIN of expression
> nodes to chain them  Some valid expressions, including
> constants and declaration references would need to be wrapped
> in some other expression, if they are to be chained, but
> that is any enough.

Those expressions shouldn't appear at statement context (since they have no
side-effects), so we're OK.  It does seem fragile, though, and code that
currently uses the TREE_CHAIN of other expressions (i.e. PUSH_LABELED_BLOCK
in Java) would need to be changed.

This leaves the question of how to handle double-chaining of statements.
The type of any expression at statement context isn't important (and will
usually be void), so we could reuse that field like the current code does.
Or look up backwards links in another table.

This scheme makes substitution more complicated; if we have some sort of
wrapper, we can just replace one statement with another (or with a
COMPOUND_EXPR).  If we use the TREE_CHAIN directly, we need to splice the
replacement in at both beginning and end.

This scheme provides no easy way of finding the end of a chain; walking
over the whole list each time could get expensive in large functions.

> The solution of just chaining expressions together does the
> smentic problem of when are we talking about the component
> expression, and are we talking about the chain.  Should expand_expr
> applied to an expression implicitly also expand its TREE_CHAIN?
> That appears to be what c-semantics.c does, at first glance.

Makes sense.  Or there could be a CHAINED_EXPR_LIST node wrapping the first
one, which could also have a pointer to the end of the chain.

I'm not compelled by any of the options mentioned.  Any other opinions?

Jason