This is the mail archive of the gcc-patches@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: [PATCH] Re: Canonical type nodes, or, comptypes considered harmful


On 11/21/06, Benjamin Kosnik <bkoz@redhat.com> wrote:
I would like to test some compile-time issues myself, but am having
trouble appying this patch. Was it generated off of mainline? Any
chance it could be re-generated off of r118977 or later?

I've re-generated the patch against today's Subversion revision. The new patch is attached, along with some more performance numbers... 85% speedup, anyone?

'make check-compile'

About 4.5% speedup here.


edit out libstdc++-v3/scripts/check_performance

to only compile, ie

- FLAGS=`$flags_script --cxxflags`
+ FLAGS="-g -O2 -S"

About 3% here.


I think the fact that we're using precompiled headers for most of the
libstdc++ testing means that we're not spending as much time in
parsing templates as we'd expect.

Of course, if you want to see speedup from canonical types... I played
around with Todd Veldhuizen's little compiler killer (shown at the end
of this message). At DEPTH=5, we get a 59% speedup:

 "Pure" GCC, without my patch: 0m2.555s
 Using canonical types: 0m1.603s

Make DEPTH=6, we get an 85% speedup:

 "Pure" GCC, without my patch: 3m0.383s
 Using canonical types: 1m37.256s

So, big performance gains are definitely possible, and I really
haven't seen any slowdown associated with this patch.

 Cheers,
 Doug

   /* BEGIN_DEATH */
   template<int Depth, int A, typename B>
   struct K17 {
     static const int x =
       K17<Depth+1, 0, K17<Depth,A,B> >::x
     + K17<Depth+1, 1, K17<Depth,A,B> >::x
     + K17<Depth+1, 2, K17<Depth,A,B> >::x
     + K17<Depth+1, 3, K17<Depth,A,B> >::x
     + K17<Depth+1, 4, K17<Depth,A,B> >::x;
   };

   template<int A, typename B>
   struct K17<DEPTH,A,B> {
     static const int x = 1;
   };

   static const int z = K17<0,0,int>::x;
   /* END_DEATH */
Index: tree.c
===================================================================
--- tree.c	(revision 119056)
+++ 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;
@@ -3383,6 +3384,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;
@@ -3868,6 +3871,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;
@@ -3883,6 +3891,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;
@@ -5001,6 +5010,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);
@@ -5050,6 +5064,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;
@@ -5116,7 +5136,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.
@@ -5208,6 +5233,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;
     }
 
@@ -5217,6 +5251,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;
 }
 
@@ -5257,6 +5303,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);
@@ -5324,6 +5371,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);
@@ -5376,6 +5424,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;
 }
 
@@ -5399,6 +5458,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)
@@ -6417,6 +6485,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: tree.h
===================================================================
--- tree.h	(revision 119056)
+++ 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: builtins.c
===================================================================
--- builtins.c	(revision 119056)
+++ builtins.c	(working copy)
@@ -4330,8 +4330,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: cp/typeck.c
===================================================================
--- cp/typeck.c	(revision 119056)
+++ 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: cp/decl.c
===================================================================
--- cp/decl.c	(revision 119056)
+++ 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);
@@ -6417,6 +6425,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;
 }
 
@@ -6491,6 +6503,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;
@@ -6507,14 +6520,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);
@@ -6605,7 +6630,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: cp/tree.c
===================================================================
--- cp/tree.c	(revision 119056)
+++ 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: cp/cp-tree.h
===================================================================
--- cp/cp-tree.h	(revision 119056)
+++ cp/cp-tree.h	(working copy)
@@ -3483,6 +3483,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: cp/pt.c
===================================================================
--- cp/pt.c	(revision 119056)
+++ 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);
@@ -4796,6 +4833,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
@@ -7416,6 +7464,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,
@@ -13084,6 +13144,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: cp/name-lookup.c
===================================================================
--- cp/name-lookup.c	(revision 119056)
+++ 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: stor-layout.c
===================================================================
--- stor-layout.c	(revision 119056)
+++ 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: c-common.c
===================================================================
--- c-common.c	(revision 119056)
+++ 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

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