[RFC] type safe trees

[Geoffrey Keating]

Nathan Sidwell <nathan@codesourcery.com> writes:

> Hi,
> I've been thinking more about type safe trees.  At the summit Zack & I
> showed y'all a two level hierarchy implemented with macros.  (The
> slides are at http://www.codesourcery.com/publications.html.)
> 
> We talked about language dependent derivations and such like, plus
> how much of this could be automatically generated.  Some responses
> from the floor were along the lines of 'can we use C++?'
> 
> Whilst avoiding the C++ route, I've come to the conclusion that a
> two level scheme is too restrictive.  And anything more than two
> levels would be a maintainance nightmare, unless it was automatically
> generated.
> 
> Why do we need more than two levels? Consider a DECL hierarchy. We
> need to represent, in approximately increasing complexity
> unnamed decls (maybe as an expression adaptor, maybe for constants)
> variables - adds a name
> parameters - adds a pass-as type?
> functions - adds a function body
> methods - adds a class context
> thunks (in C++ land) - adds a target method

I think this is the wrong approach.  It's been tried here at Apple:
"let's try removing just this field from the structure".  It produced
disappointing results, because:

- Removing one field at a time doesn't have much effect on these
  50-field structures.
- The overhead (tree_code checking, dynamic_cast, vtables) reduces the benefit
- The real problem is the underlying design of the structures, not the
  number of pointers in each structure.

As an example of this, we once measured that

extern int bar (struct foo *, bool);

takes about 1k of memory for the FUNCTION_DECL, PARAM_DECLs,
TREE_LISTs, and so on; but the textual representation takes 36 bytes,
which is about 1/30th of that size, and you can easily imagine a
representation that would be even smaller.

So this leads to some suggestions that I think should be tried first,
before we go the dramatic route of rewriting all the tree structures:

- So, why can't a FUNCTION_DECL be variable-length and have the
  parameter information in an array at the end?  That would be about a
  factor-of-two by itself.  When the function was actually
  being defined, they could be created as PARAM_DECLs in an appropriate
  scope, but only a tiny fraction of declared functions are ever defined
  in each compilation.  (I am thinking of one pointer per parameter,
  to represent the type, not more.)

- I think the TREE_LIST-ectomy should happen before we try these more
  complicated approaches.

- I believe that many of the fields we have are actually redundant, and
  that if we looked at what they're really used for we'd find
  other ways of representing or generating that information.

Don't get seduced by the 'big problem requires big change' mentality!
At Apple, we've found that there is no correlation between the size
of the change and the performance benefit it gives, except that it seems
that very large changes are more likely to produce no benefit at all
because either they can't be made to work or they were aimed at the wrong
problem.