[PATCH] Re: Canonical type nodes, or, comptypes considered harmful

["Doug Gregor" <doug dot gregor at gmail dot com>]

On 09 Nov 2006 23:09:07 -0800, Ian Lance Taylor <iant@google.com> wrote:
> 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.

I've gone through and implemented this in the C++ front end. The
general idea is to add two new fields to every _TYPE in GCC:

TYPE_CANONICAL(t) refers to the "canonical" type associated with the
type t, which might be t itself. The "canonical" type is defined by
the language's type equivalence rules, so, e.g., "int" and "typedef
int foo" would both refer to the canonical type "int".

TYPE_STRUCTURAL_EQUALITY(t) is a flag that is set when the type t
needs to use structural equality checks. This happens when we can't
trust TYPE_CANONICAL to tell us for certain when two types are
equivalent, e.g., because we weren't able to maintain canonical types.

The basic approach to the attached patch is simple: find every place
in the C++ front end (and the parts of the C front end that it relies
on) where one duplicates a type node. For each of those places,
propagate canonical type and structural equality information.

Hwo do we find these places? Grep finds most of them (calls to
build_variant_type_copy are the main culprits). To find the rest, the
patch has a canonical types verification mode (lamely enabled/disabled
by a #define in cp/typeck.c) where it performs the structural check
and then checks if using TYPE_CANONICAL would come to the same
conclusion. If not, it errors out. By running the test suites under
this mode, I was able to find the places where we duplicate type nodes
and fix the TYPE_CANONICAL field. No types have actually been
eliminated, so error messages haven't changed, and we probably haven't
saved any memory... but type comparison is very fast, and the cost of
maintaining these new fields doesn't seem to be too ridiculous.

Some brief performance numbers when running "make check-g++" on GCC
with --enable-checking=tree:
 + Without my patch: 5m57.451s
 + Canonical types verification mode: 5m54.356s
 + Canonical types (no verification): 5m36.943s

I can't quite explain why the verification mode is 3s faster than the
unpatched GCC, but it's less than a percent and I'm on a noisy system.
Still, canonical types give us an 18-second improvement (about 5%),
which is promising. Note that I haven't canonicalized function types
yet (they're always structural), which might help improve performance
further; see the latter part of this message for more information
about "troublemaker" type nodes in GCC.

Some brief performance numbers when running "make check" on
libstdc++-v3 testsuite, again with --enable-checking=tree:
 + Without my patch: 17m41.156s
 + Canonical types verification mode: 17m26.116s
 + Canonical types (no verification): 17m12.235s

Only about a 3% speedup here. If I try out some more template-heavy
code (e.g., some of the tests in the Boost Graph Library), I've seen
some speedups up in the 9.6% range. I imagine I could do better with
more sophisticated template libraries.

The attached patch introduces no new regressions on i686-pc-linux-gnu,
in either the canonical types verification mode or the "full-speed"
mode. ChangeLogs for the C and C++ parts follow, although only the C++
front end uses the canonical types right now.

I won't even ask about committing this patch, because it is a straw
man. Despite my testing, this is a risky patch... if we missed a case
where we need to canonicalize types, we will break code until we fix
that case. Most of them are easy, some are not quite as easy. At a
minimum, I'd want to bootstrap/test the C, C++, Objective C++, and
Java front ends, try some template-heavy code in the C++ compiler
(e.g., Boost), and test more platforms before even considering this
patch. That said, I think this is a promising direction. We don't seem
to lose out on performance, and we can see some wins... but it's a big
change.

So, are we interested in pursing this further? If so, several other
questions pop up:

 1) What about the C, Objective-C, Objective-C++ front ends?
 2) Should the canonical types verification mode be a configure-time
switch (--enable-checking=canonical-types)? Or a compiler flag
(-fcheck-canonical-types)? The latter might be a greater help to us,
because we can ask bug submitters to add the flag and provide the
resulting output.
 3) Anyone interested in helping?

 Cheers,
 Doug Gregor
 Open Systems Lab @ Indiana University


     FUNCTION_TYPE, METHOD_TYPE:
       - Default arguments should not be a part of the type
       - Throw specifiers should not be part of the type
       - Many attributes should not be part of the type
       - We can still canonicalize these.

     TYPENAME_TYPE:
       - This node poses some interesting problems, because we can't
     	  result TYPENAME_TYPEs that occur in the return type or type
     	  of out-of-line member definitions until we've seen that they
     	  are, in fact, member definitions. Worse, we might end up
     	  comparing TYPENAME_TYPEs in different contexts, where the
     	  currently open classes differ. Thus, the "canonical" type
     	  for a TYPENAME_TYPE is dependent on the context, so we must
     	  always perform structural comparisons.

     TEMPLATE_TEMPLATE_PARM:
       - When we reduce the level of a template template parameter
         node, we don't also reduce the level of its template
         parameters. This makes it impossible to match the new,
         level-reduced template template parameter to its canonical
         template template parameter type, because the canonical
         template template parameter will have its template
         parameters at a different level. So, when we reduce the
         level of a TEMPLATE_TEMPLATE_PARM, we mark is as requiring
         structural equality.

     UNBOUND_CLASS_TEMPLATE:
       - These nodes always require structural equality checks,
         because they are not hashed. We could add a hash table for
         these nodes.

     INTEGER_TYPE:
       - We force this node to use structural equality when building
         the index type for an array type with value-dependent bounds
         inside a template, because we don't have an effective way to
         hash on expressions. See compute_array_index_type.

     ARRAY_TYPE:
       - We try to layout array types when we build them, even if
         they refer to incomplete types. In this case, we compute the
         alignments incorrectly, creating duplicate ARRAY_TYPE nodes
         that are not easily placed together again. Ideally, we would
         have some kind of "no computed yet" alignment value, that
         gets filled in when necessary.



2006-11-20	Douglas Gregor  <doug.gregor@gmail.com>

	* builtins.c (std_gimplify_va_arg_expr): Keep track of the
	canonical type when building a variant with a different alignment.
	* c-common.c (c_common_nodes_and_builtins): Since variants of
	void_type_node get built before it is given a name, we need to
	give those variants the name, too.
	(handle_packed_attribute): When building the type variant, set the
	canonical type appropriately.
	(handle_unused_attribute): When building the type variant, set the
	canonical type appropriately.
	(handle_aligned_attribute): Ditto.
	(handle_deprecated_attribute): Ditto.
	(complete_array_type): We need to work with the canonical main
	type of the array, from which we will build the qualified version.
	* stor-layout.c (layout_type): When we don't know the
	alignment of a type for which we're building an array, we end up
	guessing wrong, so make the type require structural equality.
	* tree.c (make_node_stat): When we build a new type, it is its
	own canonical type.
	(build_type_attribute_qual_variant): When building an attribute
	variant, its canonical type is the non-attribute variant.
	(build_qualified_type): Ditto.
	(build_distinct_type_copy): When building a distinct type from
	another type, the new type is its own canonical type.
	(build_pointer_type_for_mode): When building a pointer type, also
	build a canonical type pointer.
	(build_reference_type_for_mode): When building a reference type,
	also build a canonical type reference.
	(build_index_type): When we can't hash an index type (e.g.,
	because its maximum value is negative), the index type requires
	structural equality tests.
	(build_array_type): Build the canonical form of an array type.
	(build_function_type): Function types require structural equality,
	because they contain default arguments, attributes, etc.
	(build_method_type_directly): Ditto for method types.
	(build_offset_type): Build the canonical offset type.
	(build_complex_type): Build the canonical vector type.
	* tree.h (TYPE_CANONICAL): New.
	(TYPE_STRUCTURAL_EQUALITY): New.
	(struct tree_type): Added structural_equality, unused_bits,
	canonical fields.

2006-11-20	Douglas Gregor  <doug.gregor@gmail.com>

	* typeck.c (structural_comptypes): Was "comptypes".
	(comptypes): Use canonical type information to perform fast type
	comparison. When VERIFY_CANONICAL_TYPES, verify that the canonical
	type comparison returns the same results as we would see from the
	current, structural check. Support COMPARE_STRUCTURAL when we need
	structural checks.
	* decl.c (typename_compare): Fix comment.
	(build_typename_type): TYPENAME_TYPE nodes require structural
	equality checks, because they resolve different based on the
	current class type.
	(make_unbound_class_template): UNBOUND_CLASS_TEMPLATE nodes
	require structural equality checks (for now).
	(build_ptrmemfunc_type): Build the canonical pointer to member
	function type.
	(compute_array_index_type): Whenever we build a new index type
	to represent the size of an array in a template, we need to mark
	this index type as requiring structural equality. This goes for
	arrays with value-dependent sizes with the current ABI, or all
	arrays with ABI-1.
	* tree.c (cplus_array_hash): New.
	(struct cplus_array_info): New.
	(cplus_array_compare): New.
	(cplus_array_htab): New.
	(build_cplus_array_type_1): Use a hash table to cache the array
	types we build. Build the canonical array type for each array
	type.
	(cp_build_qualified_type_real): When building a cv-qualified array
	type, use the hash table of array types and build canonical array
	types as necessary.
	(bind_template_template_parm): BOUND_TEMPLATE_TEMPLATE_PARM nodes
	use structural equality (for now).
	* cp-tree.h (COMPARE_STRUCTURAL): New.
	* pt.c (canonical_template_parms): New.
	(canonical_type_parameter): New.
	(process_template_parm): Find the canonical type parameter.
	(lookup_template_class): When we have named the primary template
	type, set the canonical type for our template class to the primary
	template type. If any of the template arguments need structural
	equality checks, the template class needs structural equality
	checks.
	(tsubst): When reducing the level of a template template
	parameter, we require structural equality tests for the resulting
	parameter because its template parameters have not had their types
	canonicalized. When reducing a template type parameter, find the
	canonical reduced type parameter.
	(any_template_arguments_need_structural_equality_p): New.
	* name-lookup.c (pushdecl_maybe_friend): When creating a new type
	for a TYPE_DECL, make its canonical type the original type.

Index: gcc/tree.c
===================================================================
--- gcc/tree.c	(revision 118723)
+++ gcc/tree.c	(working copy)
@@ -557,6 +557,7 @@ make_node_stat (enum tree_code code MEM_
       TYPE_ALIGN (t) = BITS_PER_UNIT;
       TYPE_USER_ALIGN (t) = 0;
       TYPE_MAIN_VARIANT (t) = t;
+      TYPE_CANONICAL (t) = t;
 
       /* Default to no attributes for type, but let target change that.  */
       TYPE_ATTRIBUTES (t) = NULL_TREE;
@@ -3379,6 +3380,8 @@ build_type_attribute_qual_variant (tree 
       TYPE_POINTER_TO (ntype) = 0;
       TYPE_REFERENCE_TO (ntype) = 0;
       TYPE_ATTRIBUTES (ntype) = attribute;
+      TYPE_CANONICAL (ntype) = build_qualified_type (TYPE_CANONICAL (ttype),
+						     quals);
 
       /* Create a new main variant of TYPE.  */
       TYPE_MAIN_VARIANT (ntype) = ntype;
@@ -3864,6 +3867,11 @@ build_qualified_type (tree type, int typ
     {
       t = build_variant_type_copy (type);
       set_type_quals (t, type_quals);
+
+      if (TYPE_CANONICAL (type) != type)
+	TYPE_CANONICAL (t) = build_qualified_type (TYPE_CANONICAL (type),
+						   type_quals);
+      
     }
 
   return t;
@@ -3879,6 +3887,7 @@ build_distinct_type_copy (tree type)
   
   TYPE_POINTER_TO (t) = 0;
   TYPE_REFERENCE_TO (t) = 0;
+  TYPE_CANONICAL (t) = t;
 
   /* Make it its own variant.  */
   TYPE_MAIN_VARIANT (t) = t;
@@ -4997,6 +5006,11 @@ build_pointer_type_for_mode (tree to_typ
   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
   TYPE_POINTER_TO (to_type) = t;
 
+  if (TYPE_CANONICAL (to_type) != to_type)
+    TYPE_CANONICAL (t) = build_pointer_type_for_mode (TYPE_CANONICAL (to_type),
+						      mode, can_alias_all);
+  TYPE_STRUCTURAL_EQUALITY (t) = TYPE_STRUCTURAL_EQUALITY (to_type);
+
   /* Lay out the type.  This function has many callers that are concerned
      with expression-construction, and this simplifies them all.  */
   layout_type (t);
@@ -5046,6 +5060,12 @@ build_reference_type_for_mode (tree to_t
   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
   TYPE_REFERENCE_TO (to_type) = t;
 
+  if (TYPE_CANONICAL (to_type) != to_type)
+    TYPE_CANONICAL (t) = 
+      build_reference_type_for_mode (TYPE_CANONICAL (to_type),
+				     mode, can_alias_all);
+  TYPE_STRUCTURAL_EQUALITY (t) = TYPE_STRUCTURAL_EQUALITY (to_type);
+
   layout_type (t);
 
   return t;
@@ -5112,7 +5132,12 @@ build_index_type (tree maxval)
   if (host_integerp (maxval, 1))
     return type_hash_canon (tree_low_cst (maxval, 1), itype);
   else
-    return itype;
+    {
+      /* Since we cannot hash this type, we need to compare it using
+	 structural equality checks. */
+      TYPE_STRUCTURAL_EQUALITY (itype) = 1;
+      return itype;
+    }
 }
 
 /* Builds a signed or unsigned integer type of precision PRECISION.
@@ -5204,6 +5229,15 @@ build_array_type (tree elt_type, tree in
       t = type_hash_canon (hashcode, t);
       if (save == t)
 	layout_type (t);
+
+      if (TYPE_CANONICAL (t) == t)
+	{
+	  if (TYPE_CANONICAL (elt_type) != elt_type)
+	    TYPE_CANONICAL (t) = build_array_type (TYPE_CANONICAL (elt_type),
+						   index_type);
+	  TYPE_STRUCTURAL_EQUALITY (t) = TYPE_STRUCTURAL_EQUALITY (elt_type);
+	}
+
       return t;
     }
 
@@ -5213,6 +5247,18 @@ build_array_type (tree elt_type, tree in
 
   if (!COMPLETE_TYPE_P (t))
     layout_type (t);
+
+  if (TYPE_CANONICAL (t) == t)
+    {
+      if (TYPE_CANONICAL (elt_type) != elt_type
+	  || TYPE_CANONICAL (index_type) != index_type)
+	TYPE_CANONICAL (t) = build_array_type (TYPE_CANONICAL (elt_type),
+					       TYPE_CANONICAL (index_type));
+      TYPE_STRUCTURAL_EQUALITY (t) = 
+	TYPE_STRUCTURAL_EQUALITY (elt_type) 
+	| TYPE_STRUCTURAL_EQUALITY (index_type);
+    }
+
   return t;
 }
 
@@ -5253,6 +5299,7 @@ build_function_type (tree value_type, tr
   t = make_node (FUNCTION_TYPE);
   TREE_TYPE (t) = value_type;
   TYPE_ARG_TYPES (t) = arg_types;
+  TYPE_STRUCTURAL_EQUALITY (t) = 1;
 
   /* If we already have such a type, use the old one.  */
   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
@@ -5320,6 +5367,7 @@ build_method_type_directly (tree basetyp
      which is "this".  Put it into the list of argument types.  */
   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
   TYPE_ARG_TYPES (t) = argtypes;
+  TYPE_STRUCTURAL_EQUALITY (t) = 1;
 
   /* If we already have such a type, use the old one.  */
   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
@@ -5372,6 +5420,17 @@ build_offset_type (tree basetype, tree t
   if (!COMPLETE_TYPE_P (t))
     layout_type (t);
 
+  if (TYPE_CANONICAL (t) == t)
+    {
+      if (TYPE_CANONICAL (basetype) != basetype
+	  || TYPE_CANONICAL (type) != type)
+	TYPE_CANONICAL (t) = build_offset_type (TYPE_CANONICAL (basetype),
+						TYPE_CANONICAL (type));
+      TYPE_STRUCTURAL_EQUALITY (t) = 
+	TYPE_STRUCTURAL_EQUALITY (basetype) 
+	| TYPE_STRUCTURAL_EQUALITY (type);
+    }
+
   return t;
 }
 
@@ -5395,6 +5454,15 @@ build_complex_type (tree component_type)
   if (!COMPLETE_TYPE_P (t))
     layout_type (t);
 
+  if (TYPE_CANONICAL (t) == t)
+    {
+      if (TYPE_CANONICAL (component_type) != component_type)
+	TYPE_CANONICAL (t) 
+	  = build_complex_type (TYPE_CANONICAL (component_type));
+      TYPE_STRUCTURAL_EQUALITY (t) = TYPE_STRUCTURAL_EQUALITY (component_type);
+
+    }
+
   /* If we are writing Dwarf2 output we need to create a name,
      since complex is a fundamental type.  */
   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
@@ -6413,6 +6481,12 @@ make_vector_type (tree innertype, int nu
   TYPE_READONLY (t) = TYPE_READONLY (innertype);
   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
 
+  if (TYPE_CANONICAL (innertype) != innertype
+      || mode != VOIDmode)
+    TYPE_CANONICAL (t) = make_vector_type (TYPE_CANONICAL (innertype),
+					   nunits, VOIDmode);
+  TYPE_STRUCTURAL_EQUALITY (t) = TYPE_STRUCTURAL_EQUALITY (innertype);
+
   layout_type (t);
 
   {
Index: gcc/tree.h
===================================================================
--- gcc/tree.h	(revision 118723)
+++ gcc/tree.h	(working copy)
@@ -1927,6 +1927,9 @@ struct tree_block GTY(())
 #define TYPE_NEXT_VARIANT(NODE) (TYPE_CHECK (NODE)->type.next_variant)
 #define TYPE_MAIN_VARIANT(NODE) (TYPE_CHECK (NODE)->type.main_variant)
 #define TYPE_CONTEXT(NODE) (TYPE_CHECK (NODE)->type.context)
+#define TYPE_CANONICAL(NODE) (TYPE_CHECK (NODE)->type.canonical)
+#define TYPE_STRUCTURAL_EQUALITY(NODE) \
+  (TYPE_CHECK (NODE)->type.structural_equality)
 #define TYPE_LANG_SPECIFIC(NODE) (TYPE_CHECK (NODE)->type.lang_specific)
 
 /* For a VECTOR_TYPE node, this describes a different type which is emitted
@@ -2111,6 +2114,9 @@ struct tree_type GTY(())
   unsigned lang_flag_6 : 1;
   unsigned user_align : 1;
 
+  unsigned structural_equality : 1;
+  unsigned unused_bits : 7;
+
   unsigned int align;
   tree pointer_to;
   tree reference_to;
@@ -2127,6 +2133,7 @@ struct tree_type GTY(())
   tree main_variant;
   tree binfo;
   tree context;
+  tree canonical;
   HOST_WIDE_INT alias_set;
   /* Points to a structure whose details depend on the language in use.  */
   struct lang_type *lang_specific;
Index: gcc/builtins.c
===================================================================
--- gcc/builtins.c	(revision 118723)
+++ gcc/builtins.c	(working copy)
@@ -4329,8 +4329,10 @@ std_gimplify_va_arg_expr (tree valist, t
   boundary *= BITS_PER_UNIT;
   if (boundary < TYPE_ALIGN (type))
     {
-      type = build_variant_type_copy (type);
+      tree orig_type = type;
+      type = build_variant_type_copy (orig_type);
       TYPE_ALIGN (type) = boundary;
+      TYPE_CANONICAL (type) = TYPE_CANONICAL (orig_type);
     }
 
   /* Compute the rounded size of the type.  */
Index: gcc/cp/typeck.c
===================================================================
--- gcc/cp/typeck.c	(revision 118723)
+++ gcc/cp/typeck.c	(working copy)
@@ -927,11 +927,10 @@ comp_array_types (tree t1, tree t2, bool
   return true;
 }
 
-/* Return true if T1 and T2 are related as allowed by STRICT.  STRICT
-   is a bitwise-or of the COMPARE_* flags.  */
+/* Subroutine in comptypes.  */
 
-bool
-comptypes (tree t1, tree t2, int strict)
+static bool
+structural_comptypes (tree t1, tree t2, int strict)
 {
   if (t1 == t2)
     return true;
@@ -1090,6 +1089,66 @@ comptypes (tree t1, tree t2, int strict)
   return targetm.comp_type_attributes (t1, t2);
 }
 
+/* Return true if T1 and T2 are related as allowed by STRICT.  STRICT
+   is a bitwise-or of the COMPARE_* flags.  */
+
+bool
+comptypes (tree t1, tree t2, int strict)
+{
+#define VERIFY_CANONICAL_TYPES 1
+
+  if (strict == COMPARE_STRICT)
+    {
+#ifdef VERIFY_CANONICAL_TYPES
+      bool result;
+#endif
+
+      if (t1 == t2)
+	return true;
+
+      if (t1 == error_mark_node || t2 == error_mark_node)
+	return false;
+
+      if (TYPE_STRUCTURAL_EQUALITY (t1) || TYPE_STRUCTURAL_EQUALITY (t2))
+	/* At least one of the types requires structural equality, so
+	   perform a deep check. */
+	return structural_comptypes (t1, t2, strict);
+
+#ifdef VERIFY_CANONICAL_TYPES
+      result = structural_comptypes (t1, t2, strict);
+
+      if (result && TYPE_CANONICAL (t1) != TYPE_CANONICAL (t2))
+	{
+	  /* The two types are structurally equivalent, but their
+	     canonical types were different. This is a failure of the
+	     canonical type propagation code.*/
+	  error("canonical types differ for identical types %T and %T", 
+		t1, t2);
+	  debug_tree (t1);
+	  debug_tree (t2);
+	}
+      else if (!result && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
+	{
+	  /* Two types are structurally different, but the canonical
+	     types are the same. This means we were over-eager in
+	     assigning canonical types. */
+	  error ("same canonical type node for different types %T and %T",
+		 t1, t2);
+	  debug_tree (t1);
+	  debug_tree (t2);
+	}
+
+      return result;
+#else
+      return TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2);
+#endif
+    }
+  else if (strict == COMPARE_STRUCTURAL)
+    return structural_comptypes (t1, t2, COMPARE_STRICT);
+  else
+    return structural_comptypes (t1, t2, strict);
+}
+
 /* Returns 1 if TYPE1 is at least as qualified as TYPE2.  */
 
 bool
Index: gcc/cp/decl.c
===================================================================
--- gcc/cp/decl.c	(revision 118723)
+++ gcc/cp/decl.c	(working copy)
@@ -2688,7 +2688,8 @@ typedef struct typename_info {
   bool class_p;
 } typename_info;
 
-/* Compare two TYPENAME_TYPEs.  K1 and K2 are really of type `tree'.  */
+/* Compare two TYPENAME_TYPEs.  K1 is really of type `tree', K2 is
+   really of type `typename_info*'  */
 
 static int
 typename_compare (const void * k1, const void * k2)
@@ -2749,6 +2750,7 @@ build_typename_type (tree context, tree 
       TYPENAME_TYPE_FULLNAME (t) = ti.template_id;
       TYPENAME_IS_ENUM_P (t) = ti.enum_p;
       TYPENAME_IS_CLASS_P (t) = ti.class_p;
+      TYPE_STRUCTURAL_EQUALITY (t) = TYPE_STRUCTURAL_EQUALITY (context);
 
       /* Build the corresponding TYPE_DECL.  */
       d = build_decl (TYPE_DECL, name, t);
@@ -2759,6 +2761,11 @@ build_typename_type (tree context, tree 
 
       /* Store it in the hash table.  */
       *e = t;
+
+      /* TYPENAME_TYPEs must always be compared structurally, because
+	 they may or may not resolve down to another type depending on
+	 the currently open classes. */
+      TYPE_STRUCTURAL_EQUALITY (t) = 1;
     }
 
   return t;
@@ -2930,6 +2937,7 @@ make_unbound_class_template (tree contex
   t = make_aggr_type (UNBOUND_CLASS_TEMPLATE);
   TYPE_CONTEXT (t) = FROB_CONTEXT (context);
   TREE_TYPE (t) = NULL_TREE;
+  TYPE_STRUCTURAL_EQUALITY (t) = 1;
 
   /* Build the corresponding TEMPLATE_DECL.  */
   d = build_decl (TEMPLATE_DECL, name, t);
@@ -6410,6 +6418,10 @@ build_ptrmemfunc_type (tree type)
      later.  */
   TYPE_SET_PTRMEMFUNC_TYPE (type, t);
 
+  if (TYPE_CANONICAL (type) != type)
+    TYPE_CANONICAL (t) = build_ptrmemfunc_type (TYPE_CANONICAL (type));
+  TYPE_STRUCTURAL_EQUALITY (t) = TYPE_STRUCTURAL_EQUALITY (type);
+
   return t;
 }
 
@@ -6484,6 +6496,7 @@ compute_array_index_type (tree name, tre
 {
   tree type;
   tree itype;
+  tree abi_1_itype = NULL_TREE;
 
   if (error_operand_p (size))
     return error_mark_node;
@@ -6500,14 +6513,26 @@ compute_array_index_type (tree name, tre
       type = TREE_TYPE (size);
     }
 
-  if (abi_version_at_least (2)
-      /* We should only handle value dependent expressions specially.  */
-      ? value_dependent_expression_p (size)
-      /* But for abi-1, we handled all instances in templates. This
-	 effects the manglings produced.  */
-      : processing_template_decl)
-    return build_index_type (build_min (MINUS_EXPR, sizetype,
-					size, integer_one_node));
+  if (value_dependent_expression_p (size))
+    {
+      /* We cannot do any checking for a value-dependent SIZE. Just
+	 build the index type and mark that it requires structural
+	 equality checks.  */
+      itype = build_index_type (build_min (MINUS_EXPR, sizetype,
+					   size, integer_one_node));
+      TYPE_STRUCTURAL_EQUALITY (itype) = 1;
+      return itype;
+    }
+  
+  if (!abi_version_at_least (2) && processing_template_decl)
+    /* For abi-1, we handled all instances in templates the same way,
+       even when they were non-dependent. This effects the manglings
+       produced.  So, we do the normal checking for non-dependent
+       sizes, but at the end we'll return the same type that abi-1
+       would have, but with TYPE_CANONICAL set to the "right"
+       value that the current ABI would provide. */
+    abi_1_itype = build_index_type (build_min (MINUS_EXPR, sizetype,
+					       size, integer_one_node));
 
   /* The size might be the result of a cast.  */
   STRIP_TYPE_NOPS (size);
@@ -6598,7 +6623,14 @@ compute_array_index_type (tree name, tre
     }
 
   /* Create and return the appropriate index type.  */
-  return build_index_type (itype);
+  if (abi_1_itype)
+    {
+      tree t = build_index_type (itype);
+      TYPE_CANONICAL (abi_1_itype) = TYPE_CANONICAL (t);
+      return abi_1_itype;
+    }
+  else
+    return build_index_type (itype);
 }
 
 /* Returns the scope (if any) in which the entity declared by
Index: gcc/cp/tree.c
===================================================================
--- gcc/cp/tree.c	(revision 118723)
+++ gcc/cp/tree.c	(working copy)
@@ -407,6 +407,49 @@ rvalue (tree expr)
 }
 
 
+/* Hash an ARRAY_TYPE.  K is really of type `tree'.  */
+
+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;
+}
+
+typedef struct cplus_array_info {
+  tree type;
+  tree domain;
+} cplus_array_info;
+
+/* Compare two ARRAY_TYPEs.  K1 is really of type `tree', K2 is really
+   of type `cplus_array_info*'. */
+
+static int
+cplus_array_compare (const void * k1, const void * k2)
+{
+  tree t1 = (tree) k1;
+  const cplus_array_info *t2 = (const cplus_array_info*) k2;
+
+  if (!comptypes (TREE_TYPE (t1), t2->type, COMPARE_STRUCTURAL))
+    return 0;
+
+  if (!TYPE_DOMAIN (t1))
+    return !t2->domain;
+
+  if (!t2->domain)
+    return 0;
+
+  return comptypes (TYPE_DOMAIN (t1), t2->domain, COMPARE_STRUCTURAL);
+}
+
+static GTY ((param_is (union tree_node))) htab_t cplus_array_htab;
+
+
 static tree
 build_cplus_array_type_1 (tree elt_type, tree index_type)
 {
@@ -419,9 +462,44 @@ build_cplus_array_type_1 (tree elt_type,
       || (index_type
 	  && value_dependent_expression_p (TYPE_MAX_VALUE (index_type))))
     {
-      t = make_node (ARRAY_TYPE);
-      TREE_TYPE (t) = elt_type;
-      TYPE_DOMAIN (t) = index_type;
+      void **e;
+      cplus_array_info cai;
+      hashval_t hash;
+      
+      if (cplus_array_htab == NULL)
+	cplus_array_htab = htab_create_ggc (61, &cplus_array_hash,
+					    &cplus_array_compare, NULL);
+      
+      hash = (htab_hash_pointer (elt_type)
+	      ^ htab_hash_pointer (index_type));
+      cai.type = elt_type;
+      cai.domain = index_type;
+
+      e = htab_find_slot_with_hash (cplus_array_htab, &cai, hash, INSERT); 
+      if (*e)
+	/* We have found the type: we're done. */
+	return (tree) *e;
+      else
+	{
+	  /* Build a new array type. */
+	  t = make_node (ARRAY_TYPE);
+	  TREE_TYPE (t) = elt_type;
+	  TYPE_DOMAIN (t) = index_type;
+
+	  /* Complete building the array type. */
+	  if (TYPE_CANONICAL (elt_type) != elt_type
+	      || (index_type && TYPE_CANONICAL (index_type) != index_type))
+	    TYPE_CANONICAL (t) = 
+	      build_cplus_array_type_1 (TYPE_CANONICAL (elt_type),
+					index_type? TYPE_CANONICAL (index_type)
+					: index_type);
+	  TYPE_STRUCTURAL_EQUALITY (t) =
+	    TYPE_STRUCTURAL_EQUALITY (elt_type)
+	    | (index_type? TYPE_STRUCTURAL_EQUALITY (index_type) : 0);
+
+	  /* Store it in the hash table. */
+	  *e = t;
+	}
     }
   else
     t = build_array_type (elt_type, index_type);
@@ -508,10 +586,81 @@ cp_build_qualified_type_real (tree type,
 
       if (!t)
 	{
+	  tree domain = TYPE_DOMAIN (type);
+
 	  /* Make a new array type, just like the old one, but with the
 	     appropriately qualified element type.  */
 	  t = build_variant_type_copy (type);
 	  TREE_TYPE (t) = element_type;
+
+	  if (dependent_type_p (element_type)
+	      || (domain
+		  && value_dependent_expression_p (TYPE_MAX_VALUE (domain))))
+	    {
+	      /* The new dependent array type we just created might be
+		 equivalent to an existing dependent array type, so we
+		 need to keep track of this new array type with a
+		 lookup into CPLUS_ARRAY_HTAB. Note that we cannot
+		 directly call build_cplus_array_type (that would
+		 recurse) or build_cplus_array_type (that would lose
+		 attributes). */
+	      void **e;
+	      cplus_array_info cai;
+	      hashval_t hash;
+
+	      if (cplus_array_htab == NULL)
+		cplus_array_htab = htab_create_ggc (61, &cplus_array_hash,
+						    &cplus_array_compare, 
+						    NULL);
+	  
+	      hash = (htab_hash_pointer (element_type)
+		      ^ htab_hash_pointer (domain));
+	      cai.type = element_type;
+	      cai.domain = domain;
+	  
+	      e = htab_find_slot_with_hash (cplus_array_htab, &cai, hash, 
+					    INSERT); 
+	      if (*e)
+		/* We have found the type; set our own TYPE_CANONICAL
+		   to refer to it's canonical type. */
+		TYPE_CANONICAL (t) = TYPE_CANONICAL ((tree) *e);
+	      else
+		/* Save this new type. */
+		*e = t;
+	    }
+
+#if 0
+	  if (TYPE_CANONICAL (t) == t)
+	    {
+	      if (TYPE_CANONICAL (element_type) != element_type
+		  || (domain && TYPE_CANONICAL (domain) != domain))
+		{
+		  /* Build the canonical array type, then refer to it. */
+		  TYPE_CANONICAL (t) = 
+		    build_cplus_array_type (TYPE_CANONICAL (element_type),
+					    domain? TYPE_CANONICAL (domain)
+					    : domain);
+		}
+	      else if (TYPE_CANONICAL (type) != type)
+		{
+		  /* Build the canonical array type, then refer to it. */
+		  tree canon = TYPE_CANONICAL (type);
+		  tree canon_element = 
+		    cp_build_qualified_type_real (TREE_TYPE (canon),
+						  type_quals,
+						  complain);
+		  TYPE_CANONICAL (t) =
+		    build_cplus_array_type (canon_element,
+					    TYPE_DOMAIN (canon));
+		}
+	    }
+#else
+	  TYPE_CANONICAL (t) = 
+	    build_array_type (TYPE_CANONICAL (TREE_TYPE (t)),
+			      TYPE_DOMAIN (t)? 
+			        TYPE_CANONICAL (TYPE_DOMAIN(t))
+  			        : TYPE_DOMAIN (t));
+#endif
 	}
 
       /* Even if we already had this variant, we update
@@ -1003,6 +1152,7 @@ bind_template_template_parm (tree t, tre
   TYPE_NAME (t2) = decl;
   TYPE_STUB_DECL (t2) = decl;
   TYPE_SIZE (t2) = 0;
+  TYPE_STRUCTURAL_EQUALITY (t2) = 1;
 
   return t2;
 }
Index: gcc/cp/cp-tree.h
===================================================================
--- gcc/cp/cp-tree.h	(revision 118723)
+++ gcc/cp/cp-tree.h	(working copy)
@@ -3482,6 +3482,10 @@ enum overload_flags { NO_SPECIAL = 0, DT
 #define COMPARE_REDECLARATION 4 /* The comparison is being done when
 				   another declaration of an existing
 				   entity is seen.  */
+#define COMPARE_STRUCTURAL    8 /* The comparison is intended to be
+				   structural. The actual comparison
+				   will be identical to
+				   COMPARE_STRICT.  */
 
 /* Used with push_overloaded_decl.  */
 #define PUSH_GLOBAL	     0  /* Push the DECL into namespace scope,
Index: gcc/cp/pt.c
===================================================================
--- gcc/cp/pt.c	(revision 118723)
+++ gcc/cp/pt.c	(working copy)
@@ -80,6 +80,12 @@ static tree cur_stmt_expr;
    local variables.  */
 static htab_t local_specializations;
 
+/* Contains canonical template parameter types. The vector is index by
+   the TEMPLATE_TYPE_IDX of the template parameter. Each element is a
+   TREE_LIST, whose TREE_VALUEs contain the canonical template
+   parameters of various types and levels.  */
+static GTY(()) VEC(tree,gc) *canonical_template_parms;
+
 #define UNIFY_ALLOW_NONE 0
 #define UNIFY_ALLOW_MORE_CV_QUAL 1
 #define UNIFY_ALLOW_LESS_CV_QUAL 2
@@ -157,6 +163,7 @@ static tree copy_default_args_to_explici
 static void copy_default_args_to_explicit_spec (tree);
 static int invalid_nontype_parm_type_p (tree, tsubst_flags_t);
 static int eq_local_specializations (const void *, const void *);
+static bool any_template_arguments_need_structural_equality_p (tree);
 static bool dependent_type_p_r (tree);
 static tree tsubst (tree, tree, tsubst_flags_t, tree);
 static tree tsubst_expr	(tree, tree, tsubst_flags_t, tree, bool);
@@ -2324,6 +2331,35 @@ build_template_parm_index (int index,
   return t;
 }
 
+/* Find the canonical type parameter for the given template type
+   parmaeter. Returns the canonical type parameter, which may be TYPE
+   if no such parameter existed. */
+static tree
+canonical_type_parameter (tree type)
+{
+  tree list;
+  int idx = TEMPLATE_TYPE_IDX (type);
+  if (!canonical_template_parms)
+    canonical_template_parms = VEC_alloc (tree, gc, idx+1);
+
+  while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
+    VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
+
+  list = VEC_index (tree, canonical_template_parms, idx);
+  while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
+    list = TREE_CHAIN (list);
+
+  if (list)
+    return TREE_VALUE (list);
+  else
+    {
+      VEC_replace(tree, canonical_template_parms, idx,
+		  tree_cons (NULL_TREE, type, 
+			     VEC_index (tree, canonical_template_parms, idx)));
+      return type;
+    }
+}
+
 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
@@ -2462,6 +2498,7 @@ process_template_parm (tree list, tree p
 	= build_template_parm_index (idx, processing_template_decl,
 				     processing_template_decl,
 				     decl, TREE_TYPE (parm));
+      TYPE_CANONICAL (t) = canonical_type_parameter (t);
     }
   DECL_ARTIFICIAL (decl) = 1;
   SET_DECL_TEMPLATE_PARM_P (decl);
@@ -4790,6 +4827,17 @@ lookup_template_class (tree d1,
 	  /* A local class.  Make sure the decl gets registered properly.  */
 	  if (context == current_function_decl)
 	    pushtag (DECL_NAME (template), t, /*tag_scope=*/ts_current);
+
+	  if (comp_template_args (CLASSTYPE_TI_ARGS (template_type), arglist))
+	    /* This instantiation is another name for the primary
+	       template type. Set the TYPE_CANONICAL field
+	       appropriately. */
+	    TYPE_CANONICAL (t) = template_type;
+	  else if (any_template_arguments_need_structural_equality_p (arglist))
+	    /* Some of the template arguments require structural
+	       equality testing, so this template class requires
+	       structural equality testing. */
+	    TYPE_STRUCTURAL_EQUALITY (t) = 1;
 	}
 
       /* If we called start_enum or pushtag above, this information
@@ -7411,6 +7459,18 @@ tsubst (tree t, tree args, tsubst_flags_
 		TYPE_POINTER_TO (r) = NULL_TREE;
 		TYPE_REFERENCE_TO (r) = NULL_TREE;
 
+		if (TREE_CODE (r) == TEMPLATE_TEMPLATE_PARM)
+		  /* We have reduced the level of the template
+		     template parameter, but not the levels of its
+		     template parameters, so canonical_type_parameter
+		     will not be able to find the canonical template
+		     template parameter for this level. Thus, we
+		     require structural equality checking to compare
+		     TEMPLATE_TEMPLATE_PARMs. */
+		  TYPE_STRUCTURAL_EQUALITY (r) = 1;
+		else
+		  TYPE_CANONICAL (r) = canonical_type_parameter (r);
+
 		if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)
 		  {
 		    tree argvec = tsubst (TYPE_TI_ARGS (t), args,
@@ -13079,6 +13139,40 @@ dependent_template_arg_p (tree arg)
 }
 
 /* Returns true if ARGS (a collection of template arguments) contains
+   any types that require structural equality testing.  */
+
+bool
+any_template_arguments_need_structural_equality_p (tree args)
+{
+  int i;
+  int j;
+
+  if (!args)
+    return false;
+  if (args == error_mark_node)
+    return true;
+
+  for (i = 0; i < TMPL_ARGS_DEPTH (args); ++i)
+    {
+      tree level = TMPL_ARGS_LEVEL (args, i + 1);
+      for (j = 0; j < TREE_VEC_LENGTH (level); ++j)
+	{
+	  tree arg = TREE_VEC_ELT (level, j);
+	  if (TREE_CODE (arg) == TEMPLATE_DECL
+	      || TREE_CODE (arg) == TEMPLATE_TEMPLATE_PARM)
+	    continue;
+	  else if (TYPE_P (arg) && TYPE_STRUCTURAL_EQUALITY (arg))
+	    return true;
+	  else if (!TYPE_P (arg) && TREE_TYPE (arg)
+		   && TYPE_STRUCTURAL_EQUALITY (TREE_TYPE (arg)))
+	    return true;
+	}
+    }
+
+  return false;
+}
+
+/* Returns true if ARGS (a collection of template arguments) contains
    any dependent arguments.  */
 
 bool
Index: gcc/cp/name-lookup.c
===================================================================
--- gcc/cp/name-lookup.c	(revision 118723)
+++ gcc/cp/name-lookup.c	(working copy)
@@ -821,6 +821,7 @@ pushdecl_maybe_friend (tree x, bool is_f
 	      TYPE_STUB_DECL (type) = TYPE_STUB_DECL (DECL_ORIGINAL_TYPE (x));
 	      TYPE_NAME (type) = x;
 	      TREE_TYPE (x) = type;
+	      TYPE_CANONICAL (type) = TYPE_CANONICAL (DECL_ORIGINAL_TYPE (x));
 	    }
 
 	  if (type != error_mark_node
Index: gcc/stor-layout.c
===================================================================
--- gcc/stor-layout.c	(revision 118723)
+++ gcc/stor-layout.c	(working copy)
@@ -1782,6 +1782,11 @@ layout_type (tree type)
 #else
 	TYPE_ALIGN (type) = MAX (TYPE_ALIGN (element), BITS_PER_UNIT);
 #endif
+	if (!TYPE_SIZE (element))
+	  /* We don't know the size of the underlying element type, so
+	     our alignment calculations will be wrong, forcing us to
+	     fall back on structural equality. */
+	  TYPE_STRUCTURAL_EQUALITY (type) = 1;
 	TYPE_USER_ALIGN (type) = TYPE_USER_ALIGN (element);
 	TYPE_MODE (type) = BLKmode;
 	if (TYPE_SIZE (type) != 0
Index: gcc/c-common.c
===================================================================
--- gcc/c-common.c	(revision 118723)
+++ gcc/c-common.c	(working copy)
@@ -3283,6 +3283,16 @@ c_common_nodes_and_builtins (void)
 
   record_builtin_type (RID_VOID, NULL, void_type_node);
 
+  /* Set the TYPE_NAME for any variants that were built before
+     record_builtin_type gave names to the built-in types. */
+  {
+    tree void_name = TYPE_NAME (void_type_node);
+    TYPE_NAME (void_type_node) = NULL_TREE;
+    TYPE_NAME (build_qualified_type (void_type_node, TYPE_QUAL_CONST))
+      = void_name;
+    TYPE_NAME (void_type_node) = void_name;
+  }
+
   /* This node must not be shared.  */
   void_zero_node = make_node (INTEGER_CST);
   TREE_TYPE (void_zero_node) = void_type_node;
@@ -4141,7 +4151,13 @@ handle_packed_attribute (tree *node, tre
   if (TYPE_P (*node))
     {
       if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
-	*node = build_variant_type_copy (*node);
+	{
+	  tree orig_node = *node;
+	  *node = build_variant_type_copy (orig_node);
+	  TYPE_CANONICAL (*node) = TYPE_CANONICAL (orig_node);
+	  TYPE_STRUCTURAL_EQUALITY (*node) = 
+	    TYPE_STRUCTURAL_EQUALITY (orig_node);
+	}
       TYPE_PACKED (*node) = 1;
     }
   else if (TREE_CODE (*node) == FIELD_DECL)
@@ -4367,7 +4383,13 @@ handle_unused_attribute (tree *node, tre
   else
     {
       if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
-	*node = build_variant_type_copy (*node);
+	{
+	  tree orig_node = *node;
+	  *node = build_variant_type_copy (orig_node);
+	  TYPE_CANONICAL (*node) = TYPE_CANONICAL (orig_node);
+	  TYPE_STRUCTURAL_EQUALITY (*node) = 
+	    TYPE_STRUCTURAL_EQUALITY (orig_node);
+	}
       TREE_USED (*node) = 1;
     }
 
@@ -4795,10 +4817,17 @@ handle_aligned_attribute (tree *node, tr
 	  TYPE_NAME (*type) = decl;
 	  TREE_USED (*type) = TREE_USED (decl);
 	  TREE_TYPE (decl) = *type;
+	  TYPE_CANONICAL (*type) = TYPE_CANONICAL (tt);
+	  TYPE_STRUCTURAL_EQUALITY (*type) = TYPE_STRUCTURAL_EQUALITY (tt);
 	}
       else if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
-	*type = build_variant_type_copy (*type);
-
+	{
+	  tree orig_type = *type;
+	  *type = build_variant_type_copy (orig_type);
+	  TYPE_CANONICAL (*type) = TYPE_CANONICAL (orig_type);
+	  TYPE_STRUCTURAL_EQUALITY (*type) 
+	    = TYPE_STRUCTURAL_EQUALITY (orig_type);
+	}
       TYPE_ALIGN (*type) = (1 << i) * BITS_PER_UNIT;
       TYPE_USER_ALIGN (*type) = 1;
     }
@@ -5267,7 +5296,13 @@ handle_deprecated_attribute (tree *node,
   else if (TYPE_P (*node))
     {
       if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
-	*node = build_variant_type_copy (*node);
+	{
+	  tree orig_node = *node;
+	  *node = build_variant_type_copy (orig_node);
+	  TYPE_CANONICAL (*node) = TYPE_CANONICAL (orig_node);
+	  TYPE_STRUCTURAL_EQUALITY (*node) = 
+	    TYPE_STRUCTURAL_EQUALITY (orig_node);
+	}
       TREE_DEPRECATED (*node) = 1;
       type = *node;
     }
@@ -6186,6 +6221,7 @@ complete_array_type (tree *ptype, tree i
 {
   tree maxindex, type, main_type, elt, unqual_elt;
   int failure = 0, quals;
+  hashval_t hashcode = 0;
 
   maxindex = size_zero_node;
   if (initial_value)
@@ -6262,6 +6298,12 @@ complete_array_type (tree *ptype, tree i
   TYPE_DOMAIN (main_type) = build_index_type (maxindex);
   layout_type (main_type);
 
+  /* Make sure we have the canonical MAIN_TYPE. */
+  hashcode = iterative_hash_object (TYPE_HASH (unqual_elt), hashcode);
+  hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (main_type)), 
+				    hashcode);
+  main_type = type_hash_canon (hashcode, main_type);
+
   if (quals == 0)
     type = main_type;
   else