This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
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