[RFC] type safe trees

[Nathan Sidwell]

The comments on the type safe tree proposal have split into some small
technical issues, and the language one.

The language one is why don't we do this in C++ and be done? If
we were starting from a clean slate, that'd be a nobrainer. We're not.
Anyway, there seems to be buy in from several global write maintainers
for doing this, so we need an SC descision.  I'm about to send that.

The technical points were,

Chris Lattner wrote:
 > Obviously this is a simple hierarchy, but it should illustrate the point.
 > This doesn't need layers of macros and preprocessing to implement.
Not disagreeing, however I think it necessary to make the following
work. We already have accessor macros of the form NODE_FIELD(N).  In
a heirarchy this accessor should work whether N is of static type NODE,
or of a type derived from NODE.  I could think of no other way than
doing some macro stuff inside the implementation of NODE_FIELD.

Geoffrey Keating wrote:
 > 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.
That was an example of why we definitely need more than two levels
of heirarchy.  Please don't take that as a cast in stone design.  the big
breakpoints with decls that I see are
	const_decls (we have *huge* const_decls right now)
	var_decls
	function_decls


 > - The overhead (tree_code checking, dynamic_cast, vtables) reduces the benefit
the implementation of the design I proposed would not have overheads here.
when checking is off, there's no checking or dynamic_cast.  The implementation
had no vtables.  When checking is on, the check would boil down to
	table[node->code].heirarchy[DEPTH] == CODE
(DEPTH & CODE being constants), this is a single array index.

 > - The real problem is the underlying design of the structures, not the
 >   number of pointers in each structure.
yes, I'm sure many can be made more efficient, in a similar way to what
you say about FUNCTION_DECL

 > - I think the TREE_LIST-ectomy should happen before we try these more
 >   complicated approaches.
Entirely agree. (No one's commented on my vector patch :)
When I looked for an example TREE_LIST to change, I picked
CLASSTYPE_VBASECLASSES because that vbases field was not multipurposed
(read our paper for explanation of terms), thus I could change its type
easily.  To complete the list-ectomy would require either
1) adding more union members and associated GTY gunk
2) removing all multipurposing, as Zack outlined in the talk.

It would be wise to know where we're going, before we proceed very far
down either route.

 > 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.
thanks for this insight.  Indeed, I thought 'use C++' was too big a change!
We definitely want a change that can be done incrementally.

nathan

-- 
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk