This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Canonical type nodes, or, comptypes considered harmful


> I can dig out actual real live numbers, if you're curious. For example, when calling comptypes, the no answers are (were) 34x more likely than yes answers. If you cannot return false immediately when point_to_type1 != pointer_to_type2, you then have to run a structural equality tester, and once you do that, you spend 120ns per depth in the tree as you fault everything into cache, what's that 300 some instructions. 21,980 were fast, 336,523 were slow, the slow path dominated.

I think in order to handle the C type system with the non-transitive
type compatibility effectively, for each type we have to pre-compute
the most general variant, even if that has no direct representative in
the current program.
I.e. for an array, point to the corresponding incomplete array.
(Fortunately, C allows only one dimension to be incomplete.)
For a pointer to a struct, point to the type where the struct type is
incomplete.
If an array appears in a context of another type where an incomplete
array is not allowed, we can use the complete array for computing the
most general variant of that other type.

Types can only be compatible if their most general variants are equal.

In addition to this most generalized type, each complete type can also
have a pointer to a representative of its equivalence class, and be
flagged as complete; two complete types are compatible iff they are the
same.

If a type is not in the same equivalence class as its most general variant,
it needs to describe all the 'optional' bits, i.e. struct types pointed to,
array dimensions, cv-qualifiers.


I'm not sure if this is better done by having all the semantics there
(that can be a win if there are lots of places where cv-qualifiers could
be added without breaking type compatibility, but not many cv-qualifiers
are actually encountered),
or if it should only contain a bare data field for each item (e.g. an
integer for an array dimension), with the most general variant having
a checklist of how to compare them, and its description of the overall
type saying what the data actually means when it comes to operating on the
type.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]