c-common.c (c_common_nodes_and_builtins): Since variants of void_type_node get built before it is given a name...

2007-01-02  Douglas Gregor  <doug.gregor@gmail.com>

	* 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. 
	(complete_array_type): We need to work with the canonical main
	type of the array, from which we will build the qualified version.
	* params.def (PARAM_VERIFY_CANONICAL_TYPES): New.
	* print-tree.c (print_node): Display canonical type information
	for each type.
	* 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. However,
	if the attributes are target-dependent and they differ, we need to
	use structural equality checks for this type.
	(build_qualified_type): A qualified type is not equivalent to its
	unqualified variant; set the canonical type appropriately.
	(build_distinct_type_copy): When building a distinct type from
	another type, the new type is its own canonical type.
	(build_variant_type_copy): When building a new type variant, we
	assume that it is equivalent to the original 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.
	(make_vector_type): Build the canonical vector type.
	* tree.h (TYPE_CANONICAL): New.
	(TYPE_STRUCTURAL_EQUALITY_P): New.
	(SET_TYPE_STRUCTURAL_EQUALITY): New.
	(struct tree_type): Added "canonical" field.
	* params.h (VERIFY_CANONICAL_TYPES): New.
	* doc/c-tree.texi (TYPE_CANONICAL): Document.
	(TYPE_STRUCTURAL_EQUALITY_P): Document.
	(SET_TYPE_STRUCTURAL_EQUALITY): Document.
	* doc/invoke.texi (verify-canonical-types): Document --param
	parameter for verifying canonical types.
	
2007-01-02  Douglas Gregor  <doug.gregor@gmail.com>

	* typeck.c (structural_comptypes): Renamed from "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.

2007-01-02  Douglas Gregor  <doug.gregor@gmail.com>
	
	* objc-act.c (objc_build_volatilized_type): Keep track of
	canonical types.
	(objc_get_protocol_qualified_type): Ditto.

From-SVN: r120341

1 files changed, 124 insertions, 5 deletions

diff --git a/gcc/tree.c b/gcc/tree.c
index 8591b35..5abd6f3 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -605,6 +605,7 @@ make_node_stat (enum tree_code code MEM_STAT_DECL)
       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;
@@ -3620,6 +3621,12 @@ build_type_attribute_qual_variant (tree ttype, tree attribute, int quals)
       TYPE_REFERENCE_TO (ntype) = 0;
       TYPE_ATTRIBUTES (ntype) = attribute;
 
+      if (TYPE_STRUCTURAL_EQUALITY_P (ttype))
+	SET_TYPE_STRUCTURAL_EQUALITY (ntype);
+      else
+	TYPE_CANONICAL (ntype)
+	  = build_qualified_type (TYPE_CANONICAL (ttype), quals);
+
       /* Create a new main variant of TYPE.  */
       TYPE_MAIN_VARIANT (ntype) = ntype;
       TYPE_NEXT_VARIANT (ntype) = 0;
@@ -3657,6 +3664,13 @@ build_type_attribute_qual_variant (tree ttype, tree attribute, int quals)
 	}
 
       ntype = type_hash_canon (hashcode, ntype);
+
+      /* If the target-dependent attributes make NTYPE different from
+	 its canonical type, we will need to use structural equality
+	 checks for this qualified type. */
+      if (!targetm.comp_type_attributes (ntype, ttype))
+	SET_TYPE_STRUCTURAL_EQUALITY (ntype);
+
       ttype = build_qualified_type (ntype, quals);
     }
 
@@ -4104,13 +4118,28 @@ build_qualified_type (tree type, int type_quals)
     {
       t = build_variant_type_copy (type);
       set_type_quals (t, type_quals);
+
+      if (TYPE_STRUCTURAL_EQUALITY_P (type))
+	/* Propagate structural equality. */
+	SET_TYPE_STRUCTURAL_EQUALITY (t);
+      else if (TYPE_CANONICAL (type) != type)
+	/* Build the underlying canonical type, since it is different
+	   from TYPE. */
+	TYPE_CANONICAL (t) = build_qualified_type (TYPE_CANONICAL (type),
+						   type_quals);
+      else
+	/* T is its own canonical type. */
+	TYPE_CANONICAL (t) = t;
+      
     }
 
   return t;
 }
 
 /* Create a new distinct copy of TYPE.  The new type is made its own
-   MAIN_VARIANT.  */
+   MAIN_VARIANT. If TYPE requires structural equality checks, the
+   resulting type requires structural equality checks; otherwise, its
+   TYPE_CANONICAL points to itself. */
 
 tree
 build_distinct_type_copy (tree type)
@@ -4120,6 +4149,13 @@ build_distinct_type_copy (tree type)
   TYPE_POINTER_TO (t) = 0;
   TYPE_REFERENCE_TO (t) = 0;
 
+  /* Set the canonical type either to a new equivalence class, or
+     propagate the need for structural equality checks. */
+  if (TYPE_STRUCTURAL_EQUALITY_P (type))
+    SET_TYPE_STRUCTURAL_EQUALITY (t);
+  else
+    TYPE_CANONICAL (t) = t;
+
   /* Make it its own variant.  */
   TYPE_MAIN_VARIANT (t) = t;
   TYPE_NEXT_VARIANT (t) = 0;
@@ -4127,8 +4163,11 @@ build_distinct_type_copy (tree type)
   return t;
 }
 
-/* Create a new variant of TYPE, equivalent but distinct.
-   This is so the caller can modify it.  */
+/* Create a new variant of TYPE, equivalent but distinct.  This is so
+   the caller can modify it. TYPE_CANONICAL for the return type will
+   be equivalent to TYPE_CANONICAL of TYPE, indicating that the types
+   are considered equal by the language itself (or that both types
+   require structural equality checks). */
 
 tree
 build_variant_type_copy (tree type)
@@ -4136,6 +4175,10 @@ build_variant_type_copy (tree type)
   tree t, m = TYPE_MAIN_VARIANT (type);
 
   t = build_distinct_type_copy (type);
+
+  /* Since we're building a variant, assume that it is a non-semantic
+     variant. This also propagates TYPE_STRUCTURAL_EQUALITY_P. */
+  TYPE_CANONICAL (t) = TYPE_CANONICAL (type);
   
   /* Add the new type to the chain of variants of TYPE.  */
   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
@@ -5237,6 +5280,13 @@ build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
   TYPE_POINTER_TO (to_type) = t;
 
+  if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
+    SET_TYPE_STRUCTURAL_EQUALITY (t);
+  else if (TYPE_CANONICAL (to_type) != to_type)
+    TYPE_CANONICAL (t)
+      = build_pointer_type_for_mode (TYPE_CANONICAL (to_type),
+				     mode, can_alias_all);
+
   /* Lay out the type.  This function has many callers that are concerned
      with expression-construction, and this simplifies them all.  */
   layout_type (t);
@@ -5286,6 +5336,13 @@ build_reference_type_for_mode (tree to_type, enum machine_mode mode,
   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
   TYPE_REFERENCE_TO (to_type) = t;
 
+  if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
+    SET_TYPE_STRUCTURAL_EQUALITY (t);
+  else if (TYPE_CANONICAL (to_type) != to_type)
+    TYPE_CANONICAL (t) 
+      = build_reference_type_for_mode (TYPE_CANONICAL (to_type),
+				       mode, can_alias_all);
+
   layout_type (t);
 
   return t;
@@ -5352,7 +5409,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. */
+      SET_TYPE_STRUCTURAL_EQUALITY (itype);
+      return itype;
+    }
 }
 
 /* Builds a signed or unsigned integer type of precision PRECISION.
@@ -5444,6 +5506,16 @@ build_array_type (tree elt_type, tree index_type)
       t = type_hash_canon (hashcode, t);
       if (save == t)
 	layout_type (t);
+
+      if (TYPE_CANONICAL (t) == t)
+	{
+	  if (TYPE_STRUCTURAL_EQUALITY_P (elt_type))
+	    SET_TYPE_STRUCTURAL_EQUALITY (t);
+	  else if (TYPE_CANONICAL (elt_type) != elt_type)
+	    TYPE_CANONICAL (t) 
+	      = build_array_type (TYPE_CANONICAL (elt_type), index_type);
+	}
+
       return t;
     }
 
@@ -5453,6 +5525,19 @@ build_array_type (tree elt_type, tree index_type)
 
   if (!COMPLETE_TYPE_P (t))
     layout_type (t);
+
+  if (TYPE_CANONICAL (t) == t)
+    {
+      if (TYPE_STRUCTURAL_EQUALITY_P (elt_type)
+	  || TYPE_STRUCTURAL_EQUALITY_P (index_type))
+	SET_TYPE_STRUCTURAL_EQUALITY (t);
+      else 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));
+    }
+
   return t;
 }
 
@@ -5494,6 +5579,9 @@ build_function_type (tree value_type, tree arg_types)
   TREE_TYPE (t) = value_type;
   TYPE_ARG_TYPES (t) = arg_types;
 
+  /* We don't have canonicalization of function types, yet. */
+  SET_TYPE_STRUCTURAL_EQUALITY (t);
+
   /* If we already have such a type, use the old one.  */
   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
   hashcode = type_hash_list (arg_types, hashcode);
@@ -5561,6 +5649,9 @@ build_method_type_directly (tree basetype,
   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
   TYPE_ARG_TYPES (t) = argtypes;
 
+  /* We don't have canonicalization of method types yet. */
+  SET_TYPE_STRUCTURAL_EQUALITY (t);
+
   /* If we already have such a type, use the old one.  */
   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
@@ -5612,6 +5703,18 @@ build_offset_type (tree basetype, tree type)
   if (!COMPLETE_TYPE_P (t))
     layout_type (t);
 
+  if (TYPE_CANONICAL (t) == t)
+    {
+      if (TYPE_STRUCTURAL_EQUALITY_P (basetype)
+	  || TYPE_STRUCTURAL_EQUALITY_P (type))
+	SET_TYPE_STRUCTURAL_EQUALITY (t);
+      else if (TYPE_CANONICAL (basetype) != basetype
+	       || TYPE_CANONICAL (type) != type)
+	TYPE_CANONICAL (t) 
+	  = build_offset_type (TYPE_CANONICAL (basetype), 
+			       TYPE_CANONICAL (type));
+    }
+
   return t;
 }
 
@@ -5635,6 +5738,15 @@ build_complex_type (tree component_type)
   if (!COMPLETE_TYPE_P (t))
     layout_type (t);
 
+  if (TYPE_CANONICAL (t) == t)
+    {
+      if (TYPE_STRUCTURAL_EQUALITY_P (component_type))
+	SET_TYPE_STRUCTURAL_EQUALITY (t);
+      else if (TYPE_CANONICAL (component_type) != component_type)
+	TYPE_CANONICAL (t) 
+	  = build_complex_type (TYPE_CANONICAL (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)
@@ -6653,6 +6765,13 @@ make_vector_type (tree innertype, int nunits, enum machine_mode mode)
   TYPE_READONLY (t) = TYPE_READONLY (innertype);
   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
 
+  if (TYPE_STRUCTURAL_EQUALITY_P (innertype))
+    SET_TYPE_STRUCTURAL_EQUALITY (t);
+  else if (TYPE_CANONICAL (innertype) != innertype
+	   || mode != VOIDmode)
+    TYPE_CANONICAL (t) 
+      = make_vector_type (TYPE_CANONICAL (innertype), nunits, VOIDmode);
+
   layout_type (t);
 
   {
@@ -6866,7 +6985,7 @@ build_common_tree_nodes_2 (int short_double)
        declare the type to be __builtin_va_list.  */
     if (TREE_CODE (t) != RECORD_TYPE)
       t = build_variant_type_copy (t);
-
+    
     va_list_type_node = t;
   }
 }