Canonical type nodes, or, comptypes considered harmful

[Douglas Gregor <doug dot gregor at gmail dot com>]

I just read Nathan's discussion [1] on changing GCC's type system to  
use canonical type nodes, where the comparison between two types  
requires only a pointer comparison. Right now, we use "comptypes",  
which typically needs to do deep structural checks to determine if  
two types are equivalent, because we often clone _TYPE nodes.

For the last year and a half, I have been working on-and-off on a  
version of GCC [2] that implements "concepts" for C++, which are  
likely to be included in C++0x [2]. Concepts provide complete type- 
checking for templates, and as such rely heavily on the type system.

I have come to the conclusion that it is nearly impossible to  
implement concepts without a canonical type system. In ConceptGCC, I  
use some hideous hacks to work around the lack of a canonical type  
system, but these hacks are both incomplete and horrible for  
performance. Some quick tests show that the ConceptGCC compiler  
spends over half its time in type comparisons. I have added some  
details about the interaction between concepts and the type system on  
the wiki page Nathan started [1].

The ideal type system for concepts would have canonical type nodes  
for all types, but with support for equivalence classes of types.  
Equivalence classes make it possible to produce diagnostics that  
include proper typedef names. For instance, consider:

	typedef int foo;
	typedef foo* foo_p;

In a truly canonical type-node environment, "foo" would have the same  
type node as "int" (so we couldn't produce the name "foo" in  
diagnostics), and "foo_p" would have the same type node as "int*".

With equivalence classes in the type system, "foo" becomes its own  
type node whose representative is "int", while "foo_p" becomes its  
own type node whose representative is "int*". Before doing any type  
comparisons, one will typically request the representative of each  
type (which is a relatively quick operation); if there is an error,  
diagnostics can use the original node to print the error, so the user  
can see her typedef names. Equivalence classes also make it possible  
to join two equivalence classes, which is crucial for concepts.

Having canonical type nodes in GCC would:

	1) Improve memory use (since we don't clone so many type nodes)
	2) Improve compilation performance (comptypes shows up in the top 5  
routines in profiles of C++ compiles)
	3) Make a complete implementation of concepts possible (which will  
likely be important for C++0x support)

What would it take to get canonical type nodes in GCC? Nathan has  
experimented with some pieces of it, and I have experimented with  
others. It will likely be a large effort, but the payoff will be  
worth it in the end. Is the GCC community interested in working on  
this, and how would we go about doing it?

	Doug Gregor	
	Open Systems Lab @ Indiana University

[1] http://gcc.gnu.org/wiki/TypeSystem
[2] http://www.generic-programming.org/software/ConceptGCC/
[3] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2081.pdf