Re: Target FUNCTION_{PRO,EPI}LOGUE question

[Fergus Henderson <fjh at cs dot mu dot oz dot au>]

On 28-Jun-2001, Neil Booth <neil@daikokuya.demon.co.uk> wrote:
> Currently our "tree" shares a common part, and then
> various data depending upon what it is.  Different tree types contain
> a lot of information that they don't use, simply because it's
> convenient that everything share a common structure.  This has the
> problem that many things are misnamed.  For example, from tree.h:-
> 
>    public_flag:
> 
>        TREE_OVERFLOW in
>            INTEGER_CST, REAL_CST, COMPLEX_CST
>        TREE_PUBLIC in
>            VAR_DECL or FUNCTION_DECL or IDENTIFIER_NODE
>        TREE_VIA_PUBLIC in
>            TREE_LIST or TREE_VEC
>        EXPR_WFL_EMIT_LINE_NOTE in
>            EXPR_WITH_FILE_LOCATION
> 
> I think it would be nice if this "public" flag were named "overflow"
> for INTEGER_CST, REAL_CST and COMPLEX_CST, and named "public" for
> VAR_DECL etc. etc.  In other words, named what it really is.

But the name `public_flag' is only used in five lines of code
(and one comment) in tree.h.  It isn't used anywhere else.
The names used elsewhere are TREE_OVERFLOW, TREE_PUBLIC, etc.
It could easily be renamed `flag_11', but the name used in tree.h
doesn't really matter much, since it's private to tree.h.
So while I agree that the current design is not as elegant as
one could hope for, I think it works OK in practice, at least
with regard to these flag bits.

> Why isn't it at present?  Because they all share the same base
> structure.  It's also a waste of space - as Zack has pointed out many
> times, IDENTIFIER_NODEs care for almost nothing in their tree_common
> part, which bloats them and quite possibly pushes them into the next
> GC allocation size.

This is a more serious issue.

But the tree_common struct only uses 2 pointers plus 32 bits for the tree_code
and flags.  There's not a huge amount of bloat there.
What you're proposing would add at least one pointer for the
vtable, and the cost of that may well outweigh any gains you get
from saving a pointer or two in certain node types.

> Another consequence is we get enormous switch statements switching on
> a tree's TREE_CODE or TREE_CLASS.  I think most of those switch
> statements should be replaced by virtual function calls.

I'm very skeptical about that.
What would be the advantage?

As explained in more detail below, I think the routines should continue
to be grouped by function, rather than grouped by data type.  So I don't
see what using indirection here would buy you.  I'm all for breaking
long and complicated functions into smaller ones.  But you don't need
to use virtual function calls to do that.

> If our "tree" became more like a C++ class
> hierarchy, with different types deriving from each other, then each
> type could carry around just the baggage it needs.
...
> One immediate and large beneficiary of this would be (tree) garbage
> collection.  This is currently quite inefficient - we push trees onto
> a hand-coded stack, and then pop them off later to garbage collect
> their children, recursively.  We also do a lot of redundant NULL_TREE
> checking, since we can't in general know whether something's a
> NULL_TREE or not: see ggc_test_and_set_mark().  Each child is garbage
> collected through a switch statement on the TREE_CODE, with various
> exceptional cases.
> 
> Wouldn't something like something like this be much nicer and more
> efficient:-
> 
>    for (each root in all_ggc_roots)
> 	root->vtable->gc_collect ();

(The virtual function should be called gc_mark() not gc_collect(), I think.)

I'm not convinced that this approach would be significantly more efficient.

The optimization of avoiding unnecessary checks for NULL_TREE is
orthogonal, isn't it?  That could be done even with the current
switch-based infrastructure.  Just add macros ggc_mark_nonnull_tree(),
etc., which are like ggc_mark_tree(), etc., except that they call
ggc_set_mark() rather than ggc_test_and_set_mark().  Then call them
from the appropriate places.  The switch on tree class in ggc_mark_trees()
could be changed to a switch on tree code if you need finer granularity
of type information in order to do this optimization.  The calls to
mark the two pointers in tree_common could be moved into the individual
cases and omitted for tree codes where those fields are never used.

The cost of switch versus indirect functional call is going to be
pretty much a wash.  So I think the main benefit of this proposed
approach would be avoiding the range checks when pushing stuff
onto our hand-coded stacks.  And there may be other ways of achieving that.

> More importantly, it's extensible - each time we add a new type of
> tree, we don't need to update code in ggc-common.c.  At present if we
> add any kind of new tree, we have to check code literally everywhere
> for in-built assumptions about what values of TREE_CODE are possible,
> what the default: case does in the switch statement, etc.  It's a
> nightmare.

If you organize things by function, then adding a new type will require
adding code everywhere.  If you organize things by data type, then
adding a new function will require adding code everywhere.
I think that for compilers in general and gcc in particular
it is better to organize things by function rather than by
data type, since adding a new compiler pass is a more common
operation than adding a new kind of node to your abstract syntax tree.

So the only remaining issue is how much compiler help you get when adding
the new code.  Compiler warnings (e.g. -Wswitch) and avoiding the use of
"default:" cases can help here.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.