This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[C++ PATCH] Canonical types (2/3)
- From: "Doug Gregor" <doug dot gregor at gmail dot com>
- To: gcc at gcc dot gnu dot org, "GCC Patches" <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 28 Nov 2006 10:56:07 -0500
- Subject: [C++ PATCH] Canonical types (2/3)
This patch introduces canonical types into GCC; see the first part of
this patch for a complete description.
This is part two of three, containing changes to the C++ front end.
Okay for mainline?
Cheers,
Doug Gregor
Open Systems Lab @ Indiana University
2006-11-28 Douglas Gregor <doug.gregor@gmail.com>
* typeck.c (structural_comptypes): Renamed from "comptypes".
(comptypes): Use canonical type information to perform fast type
comparison. When flag_check_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).
(handle_java_interface_attribute): Keep track of the canonical
type.
* 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: typeck.c
===================================================================
--- typeck.c (revision 119271)
+++ 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,65 @@ 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)
+{
+ if (strict == COMPARE_STRICT)
+ {
+ bool result;
+
+ 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);
+
+ if (flag_check_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.*/
+ warning(0,
+ "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. */
+ warning (0,
+ "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);
+ }
+ 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: decl.c
===================================================================
--- decl.c (revision 119271)
+++ 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: tree.c
===================================================================
--- tree.c (revision 119271)
+++ 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,46 @@ 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) =
+ TYPE_CANONICAL
+ (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 +588,55 @@ 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;
+ }
+
+ TYPE_CANONICAL (t) =
+ TYPE_CANONICAL
+ (build_array_type (TYPE_CANONICAL (TREE_TYPE (t)),
+ TYPE_DOMAIN (t)?
+ TYPE_CANONICAL (TYPE_DOMAIN(t))
+ : TYPE_DOMAIN (t)));
}
/* Even if we already had this variant, we update
@@ -1003,6 +1128,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;
}
@@ -1810,7 +1936,12 @@ handle_java_interface_attribute (tree* n
return NULL_TREE;
}
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_JAVA_INTERFACE (*node) = 1;
return NULL_TREE;
Index: cp-tree.h
===================================================================
--- cp-tree.h (revision 119271)
+++ cp-tree.h (working copy)
@@ -3509,6 +3509,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: pt.c
===================================================================
--- pt.c (revision 119271)
+++ 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
@@ -7426,6 +7474,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,
@@ -13108,6 +13168,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: name-lookup.c
===================================================================
--- name-lookup.c (revision 119271)
+++ 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