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
