Re: [PATCH] Canonical types (1/3)

[Mark Mitchell <mark at codesourcery dot com>]

Doug Gregor wrote:
> This patch introduces canonical types into GCC, which allow us to
> compare two types very efficiently and results in an overall
> compile-time performance improvement. I have been seeing 3-5%
> improvements in compile time on the G++ and libstdc++ test suites,
> 5-10% on template-heavy (but realistic) code in Boost, and up to 85%
> improvement for extremely template-heavy metaprogramming.

The new macros in tree.h (TYPE_CANONICAL and TYPE_STRUCTURAL_EQUALITY)
need documentation, at least in tree.h, and, ideally, in the ill-named
c-tree.texi as well.

I want to make sure I understand this idiom, in
build_pointer_type_for_mode, and elsewhere:

+  if (TYPE_CANONICAL (to_type) != to_type)
+    TYPE_CANONICAL (t) =
+      build_pointer_type_for_mode (TYPE_CANONICAL (to_type),
+				   mode, can_alias_all);

If there was already a pointer type to the canonical type of to_type,
then the call build_pointer_type_for_mode will return it.  If there
wasn't, then we will build a new canonical type for that pointer type.
We can't use the pointer type we're building now (i.e., "T") as the
canonical pointer type because we have would have no way to find it in
future, when creating another pointer type for the canonical version of
to_type.

So, we are actually creating more type nodes in this case.  That seems
unfortunate, though I fully understand we're intentionally trading space
for speed just by adding the new type fields.  A more dramatic version
of your change would be to put the new pointer type on the
TYPE_POINTER_TO list for the canonical to_type, make it the canonical
pointer type, and then have the build_pointer_type_for_mode always go to
the canonical to_type to search TYPE_POINTER_TO, considering types to be
an exact match only if they had more fields in common (like, TYPE_NAME
and TYPE_CONTEXT, say).  Anyhow, your approach is fine, at least for now.

+  TYPE_STRUCTURAL_EQUALITY (t) = TYPE_STRUCTURAL_EQUALITY (to_type);

Does it ever make sense to have both TYPE_CANONICAL and
TYPE_STRUCTURAL_EQUALITY set?  If we have to do the structural equality
test, then it seems to me that the canonical type isn't useful, and we
might as well not construct it.

> +      type = build_variant_type_copy (orig_type);
>        TYPE_ALIGN (type) = boundary;
> +      TYPE_CANONICAL (type) = TYPE_CANONICAL (orig_type);

Eek.  So, despite having different alignments, we consider these types
"the same"?  If that's what we already do, then it's OK to preserve that
behavior, but it sure seems worrisome.

I'm going to review patch 2/3 here too, since I don't think we should
add the fields in patch 1 until we have something that can actually take
advantage of them; otherwise, we'd just be wasting (more) memory.

+  else if (strict == COMPARE_STRUCTURAL)
+    return structural_comptypes (t1, t2, COMPARE_STRICT);

Why do we ever want the explicit COMPARE_STRUCTURAL?

+static hashval_t
+cplus_array_hash (const void* k)
+{
+  hashval_t hash;
+  tree t = (tree) k;
+
+  hash = (htab_hash_pointer (TREE_TYPE (t))
+	  ^ htab_hash_pointer (TYPE_DOMAIN (t)));
+
+  return hash;
+}

Since this hash function is dependent on pointer values, we'll get
different results on different hosts.  I was worried that will lead to
differences in generated debug information, perhaps due to different
TYPE_UIDs -- but it looks like there is only ever one matching entry in
the table, so we never have to worry about the compiler "randomly"
choosing between two equally good choices?

Have you tested with flag_check_canonical_types on, and verified that
you get no warnings?  (I agree that a --param for that would be better;
if a user ever has to turn this on, we broke the compiler.)

Thanks,

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