Re: Canonical type nodes, or, comptypes considered harmful

[Mark Mitchell <mark at codesourcery dot com>]

Dale Johannesen wrote:
> On Nov 7, 2006, at 11:47 AM, Douglas Gregor wrote:
>
> > 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.
>
> One difficulty is that compatibility of types in C is not transitive, 
> especially when you're compiling more than one translation unit at a time.
> See the thread "IMA vs tree-ssa" in Feb-Mar 2004.  Geoff Keating and 
> Joseph Myers give good examples.

For example:

  http://gcc.gnu.org/ml/gcc/2004-02/msg01462.html

However, I still doubt that this is what the C committee actually 
intended.

Transitivity of type equivalence is fundamental in every type system 
(real and theoretical) with which I'm familiar.  In C++, these examples 
are not valid because the ODR, and, IIRC, in C you cannot produce them 
in a single translation unit -- which is the case that most C 
programmers think about.  So, I'm of the opinion that we should discount 
this issue.

I do think that canonical types (with equivalence classes, as Doug 
suggests) would be a big win, for all of the reasons he suggests.  We 
have known for a long time that comptypes is a bottleneck in the C++ 
front end, and while some of that could be solved in other ways, making 
it a near-free operation would be a huge benefit.

--
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713