Re: Canonical type nodes, or, comptypes considered harmful

[Ian Lance Taylor <iant at google dot com>]

Mike Stump <mrs@apple.com> writes:

> On Nov 8, 2006, at 7:14 AM, Ian Lance Taylor wrote:
> > The way to canonicalize them is to have all equivalent types point to
> > a single canonical type for the equivalence set.  The comparison is
> > one memory dereference and one pointer comparison, not the current
> > procedure of checking for structural equivalence.
> 
> Once not equal addresses might mean equal types, you have to do a
> structure walk to compare types, and you're right back were we
> started.  The only way to save yourself, is to be able to say,
> different addresses, _must_ be different types.

I have no idea what you mean by this.

I meant something very simple: for every type, there is a
TYPE_CANONICAL field.  This is how you tell whether two types are
equivalent:
    TYPE_CANONICAL (a) == TYPE_CANONICAL (b)
That is what I mean when I saw one memory dereference and one pointer
comparison.

> An example, are these two types the same:
> 
> 	********************A
> 	********************B
> 
> given that A and B are the same type.  Your way, you need to walk two
> trees, hitting memory 40 times.

No.  When you create *A, you also create * (TYPE_CANONICAL (A)) (this
may be the same as *A, of course).  You set TYPE_CANONICAL (*A) to
that type.  And the same for *B.  Since TYPE_CANONICAL (A) ==
TYPE_CANONICAL (B) by assumption, you make sure that TYPE_CANONICAL
(*A) == TYPE_CANONICAL (*B).

Ian