diff options
| -rw-r--r-- | gcc/ChangeLog | 50 | ||||
| -rw-r--r-- | gcc/c-common.c | 17 | ||||
| -rw-r--r-- | gcc/cp/ChangeLog | 49 | ||||
| -rw-r--r-- | gcc/cp/cp-tree.h | 4 | ||||
| -rw-r--r-- | gcc/cp/decl.c | 52 | ||||
| -rw-r--r-- | gcc/cp/pt.c | 94 | ||||
| -rw-r--r-- | gcc/cp/tree.c | 137 | ||||
| -rw-r--r-- | gcc/cp/typeck.c | 67 | ||||
| -rw-r--r-- | gcc/doc/c-tree.texi | 49 | ||||
| -rw-r--r-- | gcc/doc/invoke.texi | 7 | ||||
| -rw-r--r-- | gcc/objc/ChangeLog | 6 | ||||
| -rw-r--r-- | gcc/objc/objc-act.c | 16 | ||||
| -rw-r--r-- | gcc/params.def | 13 | ||||
| -rw-r--r-- | gcc/params.h | 2 | ||||
| -rw-r--r-- | gcc/print-tree.c | 5 | ||||
| -rw-r--r-- | gcc/stor-layout.c | 5 | ||||
| -rw-r--r-- | gcc/tree.c | 129 | ||||
| -rw-r--r-- | gcc/tree.h | 22 |
18 files changed, 701 insertions, 23 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index aab8e25bda1..2e3e2abd9a6 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,53 @@ +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 Joseph Myers <joseph@codesourcery.com> * config.gcc (powerpc-*-eabispe*, powerpc-*-eabisimaltivec*, diff --git a/gcc/c-common.c b/gcc/c-common.c index f2e87b1db2c..0658141dadc 100644 --- a/gcc/c-common.c +++ b/gcc/c-common.c @@ -3458,6 +3458,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; @@ -6294,6 +6304,7 @@ complete_array_type (tree *ptype, tree initial_value, bool do_default) { tree maxindex, type, main_type, elt, unqual_elt; int failure = 0, quals; + hashval_t hashcode = 0; maxindex = size_zero_node; if (initial_value) @@ -6370,6 +6381,12 @@ complete_array_type (tree *ptype, tree initial_value, bool do_default) 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 diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog index ae5beb2a624..dc291d054a1 100644 --- a/gcc/cp/ChangeLog +++ b/gcc/cp/ChangeLog @@ -1,3 +1,52 @@ +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. + 2006-12-31 Simon Martin <simartin@users.sourceforge.net> PR c++/29731 diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h index 6707a20de66..1ec96655ab5 100644 --- a/gcc/cp/cp-tree.h +++ b/gcc/cp/cp-tree.h @@ -3508,6 +3508,10 @@ enum overload_flags { NO_SPECIAL = 0, DTOR_FLAG, OP_FLAG, TYPENAME_FLAG }; #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, diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c index 6a46636ea10..1ed8afc7708 100644 --- a/gcc/cp/decl.c +++ b/gcc/cp/decl.c @@ -2695,7 +2695,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) @@ -2766,6 +2767,11 @@ build_typename_type (tree context, tree name, tree fullname, /* 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. */ + SET_TYPE_STRUCTURAL_EQUALITY (t); } return t; @@ -2937,6 +2943,7 @@ make_unbound_class_template (tree context, tree name, tree parm_list, t = make_aggr_type (UNBOUND_CLASS_TEMPLATE); TYPE_CONTEXT (t) = FROB_CONTEXT (context); TREE_TYPE (t) = NULL_TREE; + SET_TYPE_STRUCTURAL_EQUALITY (t); /* Build the corresponding TEMPLATE_DECL. */ d = build_decl (TEMPLATE_DECL, name, t); @@ -6461,6 +6468,11 @@ build_ptrmemfunc_type (tree type) later. */ TYPE_SET_PTRMEMFUNC_TYPE (type, t); + if (TYPE_STRUCTURAL_EQUALITY_P (type)) + SET_TYPE_STRUCTURAL_EQUALITY (t); + else if (TYPE_CANONICAL (type) != type) + TYPE_CANONICAL (t) = build_ptrmemfunc_type (TYPE_CANONICAL (type)); + return t; } @@ -6535,6 +6547,7 @@ compute_array_index_type (tree name, tree size) { tree type; tree itype; + tree abi_1_itype = NULL_TREE; if (error_operand_p (size)) return error_mark_node; @@ -6551,14 +6564,26 @@ compute_array_index_type (tree name, tree size) 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)); + SET_TYPE_STRUCTURAL_EQUALITY (itype); + 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); @@ -6649,7 +6674,14 @@ compute_array_index_type (tree name, tree size) } /* 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 diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c index f9a728fa4b5..1e90751287c 100644 --- a/gcc/cp/pt.c +++ b/gcc/cp/pt.c @@ -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_explicit_spec_1 (tree, tree); 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); @@ -2335,6 +2342,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 @@ -2473,6 +2509,7 @@ process_template_parm (tree list, tree parm, bool is_non_type) = 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); @@ -4807,6 +4844,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. */ + SET_TYPE_STRUCTURAL_EQUALITY (t); } /* If we called start_enum or pushtag above, this information @@ -7473,6 +7521,18 @@ tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl) 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. */ + SET_TYPE_STRUCTURAL_EQUALITY (r); + else + TYPE_CANONICAL (r) = canonical_type_parameter (r); + if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM) { tree argvec = tsubst (TYPE_TI_ARGS (t), args, @@ -13168,6 +13228,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_P (arg)) + return true; + else if (!TYPE_P (arg) && TREE_TYPE (arg) + && TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (arg))) + return true; + } + } + + return false; +} + +/* Returns true if ARGS (a collection of template arguments) contains any dependent arguments. */ bool diff --git a/gcc/cp/tree.c b/gcc/cp/tree.c index 526077a43e9..ae3dc4c2786 100644 --- a/gcc/cp/tree.c +++ b/gcc/cp/tree.c @@ -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,47 @@ build_cplus_array_type_1 (tree elt_type, tree index_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_STRUCTURAL_EQUALITY_P (elt_type) + || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type))) + SET_TYPE_STRUCTURAL_EQUALITY (t); + else 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)); + + /* Store it in the hash table. */ + *e = t; + } } else t = build_array_type (elt_type, index_type); @@ -508,10 +589,59 @@ 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; + + /* This is a new type. */ + TYPE_CANONICAL (t) = t; + + 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_1 (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) + /* Save this new type. */ + *e = t; + } + + if (TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (t)) + || (TYPE_DOMAIN (t) + && TYPE_STRUCTURAL_EQUALITY_P (TYPE_DOMAIN (t)))) + SET_TYPE_STRUCTURAL_EQUALITY (t); + else + 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 +1133,7 @@ bind_template_template_parm (tree t, tree newargs) TYPE_NAME (t2) = decl; TYPE_STUB_DECL (t2) = decl; TYPE_SIZE (t2) = 0; + SET_TYPE_STRUCTURAL_EQUALITY (t2); return t2; } diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c index cb09d4c987c..7e8b785b3eb 100644 --- a/gcc/cp/typeck.c +++ b/gcc/cp/typeck.c @@ -43,6 +43,7 @@ Boston, MA 02110-1301, USA. */ #include "target.h" #include "convert.h" #include "c-common.h" +#include "params.h" static tree pfn_from_ptrmemfunc (tree); static tree convert_for_assignment (tree, tree, const char *, tree, int); @@ -927,11 +928,10 @@ comp_array_types (tree t1, tree t2, bool allow_redeclaration) 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 +1090,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_P (t1) || TYPE_STRUCTURAL_EQUALITY_P (t2)) + /* At least one of the types requires structural equality, so + perform a deep check. */ + return structural_comptypes (t1, t2, strict); + + if (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.*/ + 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 diff --git a/gcc/doc/c-tree.texi b/gcc/doc/c-tree.texi index b8a4faf0548..aa7b7e79b8d 100644 --- a/gcc/doc/c-tree.texi +++ b/gcc/doc/c-tree.texi @@ -305,6 +305,9 @@ The elements are indexed from zero. @findex TYPENAME_TYPE_FULLNAME @findex TYPE_FIELDS @findex TYPE_PTROBV_P +@findex TYPE_CANONICAL +@findex TYPE_STRUCTURAL_EQUALITY_P +@findex SET_TYPE_STRUCTURAL_EQUALITY All types have corresponding tree nodes. However, you should not assume that there is exactly one tree node corresponding to each type. There @@ -406,6 +409,52 @@ does not hold for the generic pointer to object type @code{void *}. You may use @code{TYPE_PTROBV_P} to test for a pointer to object type as well as @code{void *}. +@item TYPE_CANONICAL +This macro returns the ``canonical'' type for the given type +node. Canonical types are used to improve performance in the C++ and +Objective-C++ front ends by allowing efficient comparison between two +type nodes in @code{same_type_p}: if the @code{TYPE_CANONICAL} values +of the types are equal, the types are equivalent; otherwise, the types +are not equivalent. The notion of equivalence for canonical types is +the same as the notion of type equivalence in the language itself. For +instance, + +When @code{TYPE_CANONICAL} is @code{NULL_TREE}, there is no canonical +type for the given type node. In this case, comparison between this +type and any other type requires the compiler to perform a deep, +``structural'' comparison to see if the two type nodes have the same +form and properties. + +The canonical type for a node is always the most fundamental type in +the equivalence class of types. For instance, @code{int} is its own +canonical type. A typedef @code{I} of @code{int} will have @code{int} +as its canonical type. Similarly, @code{I*}@ and a typedef @code{IP}@ +(defined to @code{I*}) will has @code{int*} as their canonical +type. When building a new type node, be sure to set +@code{TYPE_CANONICAL} to the appropriate canonical type. If the new +type is a compound type (built from other types), and any of those +other types require structural equality, use +@code{SET_TYPE_STRUCTURAL_EQUALITY} to ensure that the new type also +requires structural equality. Finally, if for some reason you cannot +guarantee that @code{TYPE_CANONICAL} will point to the canonical type, +use @code{SET_TYPE_STRUCTURAL_EQUALITY} to make sure that the new +type--and any type constructed based on it--requires structural +equality. If you suspect that the canonical type system is +miscomparing types, pass @code{--param verify-canonical-types=1} to +the compiler or configure with @code{--enable-checking} to force the +compiler to verify its canonical-type comparisons against the +structural comparisons; the compiler will then print any warnings if +the canonical types miscompare. + +@item TYPE_STRUCTURAL_EQUALITY_P +This predicate holds when the node requires structural equality +checks, e.g., when @code{TYPE_CANONICAL} is @code{NULL_TREE}. + +@item SET_TYPE_STRUCTURAL_EQUALITY +This macro states that the type node it is given requires structural +equality checks, e.g., it sets @code{TYPE_CANONICAL} to +@code{NULL_TREE}. + @item same_type_p This predicate takes two types as input, and holds if they are the same type. For example, if one type is a @code{typedef} for the other, or diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 8fa9aa999f2..ff463c781ff 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -6383,6 +6383,13 @@ The size of cache line in L1 cache, in bytes. @item l1-cache-size The number of cache lines in L1 cache. +@item verify-canonical-types +Whether the compiler should verify the ``canonical'' types used for +type equality comparisons within the C++ and Objective-C++ front +ends. Set to 1 (the default when GCC is configured with +--enable-checking) to enable verification, 0 to disable verification +(the default when GCC is configured with --disable-checking). + @end table @end table diff --git a/gcc/objc/ChangeLog b/gcc/objc/ChangeLog index b3647d99a89..0759c8db9e0 100644 --- a/gcc/objc/ChangeLog +++ b/gcc/objc/ChangeLog @@ -1,3 +1,9 @@ +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. + 2006-11-02 Andreas Tobler <a.tobler@schweiz.org> * objc-act.c (objc_finish_file): Remove ifdef clause for OBJCPLUS and diff --git a/gcc/objc/objc-act.c b/gcc/objc/objc-act.c index d0c34475b87..bd79796df7e 100644 --- a/gcc/objc/objc-act.c +++ b/gcc/objc/objc-act.c @@ -908,6 +908,14 @@ objc_build_volatilized_type (tree type) t = build_variant_type_copy (type); TYPE_VOLATILE (t) = 1; + /* Set up the canonical type information. */ + if (TYPE_STRUCTURAL_EQUALITY_P (type)) + SET_TYPE_STRUCTURAL_EQUALITY (t); + else if (TYPE_CANONICAL (type) != type) + TYPE_CANONICAL (t) = objc_build_volatilized_type (TYPE_CANONICAL (type)); + else + TYPE_CANONICAL (t) = t; + return t; } @@ -1370,7 +1378,13 @@ objc_get_protocol_qualified_type (tree interface, tree protocols) to the pointee. */ if (is_ptr) { - TREE_TYPE (type) = build_variant_type_copy (TREE_TYPE (type)); + tree orig_pointee_type = TREE_TYPE (type); + TREE_TYPE (type) = build_variant_type_copy (orig_pointee_type); + + /* Set up the canonical type information. */ + TYPE_CANONICAL (type) + = TYPE_CANONICAL (TYPE_POINTER_TO (orig_pointee_type)); + TYPE_POINTER_TO (TREE_TYPE (type)) = type; type = TREE_TYPE (type); } diff --git a/gcc/params.def b/gcc/params.def index c24892e7611..41a4e417ccf 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -626,6 +626,19 @@ DEFPARAM (PARAM_L1_CACHE_LINE_SIZE, "The size of L1 cache line", 32, 0, 0) +#ifdef ENABLE_CHECKING +# define GCC_CANONICAL_TYPES_DEFAULT 1 +#else +# define GCC_CANONICAL_TYPES_DEFAULT 0 +#endif + +/* Whether we should verify that the canonical types in the system are + consistent with the "structural" typing. */ + +DEFPARAM (PARAM_VERIFY_CANONICAL_TYPES, + "verify-canonical-types", + "Whether to verify canonical types", + GCC_CANONICAL_TYPES_DEFAULT, 0, 1) /* Local variables: mode:c diff --git a/gcc/params.h b/gcc/params.h index b706b535fff..79a656c31e9 100644 --- a/gcc/params.h +++ b/gcc/params.h @@ -164,4 +164,6 @@ typedef enum compiler_param PARAM_VALUE (PARAM_L1_CACHE_SIZE) #define L1_CACHE_LINE_SIZE \ PARAM_VALUE (PARAM_L1_CACHE_LINE_SIZE) +#define VERIFY_CANONICAL_TYPES \ + PARAM_VALUE (PARAM_VERIFY_CANONICAL_TYPES) #endif /* ! GCC_PARAMS_H */ diff --git a/gcc/print-tree.c b/gcc/print-tree.c index 1ed17de8641..a73247d2de1 100644 --- a/gcc/print-tree.c +++ b/gcc/print-tree.c @@ -604,6 +604,11 @@ print_node (FILE *file, const char *prefix, tree node, int indent) TYPE_ALIGN (node), TYPE_SYMTAB_ADDRESS (node), TYPE_ALIAS_SET (node)); + if (TYPE_STRUCTURAL_EQUALITY_P (node)) + fprintf (file, " structural equality"); + else + dump_addr (file, " canonical type ", TYPE_CANONICAL (node)); + print_node (file, "attributes", TYPE_ATTRIBUTES (node), indent + 4); if (INTEGRAL_TYPE_P (node) || TREE_CODE (node) == REAL_TYPE) diff --git a/gcc/stor-layout.c b/gcc/stor-layout.c index 94ea457c5a5..61879a060a3 100644 --- a/gcc/stor-layout.c +++ b/gcc/stor-layout.c @@ -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. */ + SET_TYPE_STRUCTURAL_EQUALITY (type); TYPE_USER_ALIGN (type) = TYPE_USER_ALIGN (element); TYPE_MODE (type) = BLKmode; if (TYPE_SIZE (type) != 0 diff --git a/gcc/tree.c b/gcc/tree.c index 8591b35150b..5abd6f345f3 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; } } diff --git a/gcc/tree.h b/gcc/tree.h index 0c9e02e91f5..3a226287107 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -2005,6 +2005,27 @@ 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) + +/* The "canonical" type for this type node, which can be used to + compare the type for equality with another type. If two types are + equal (based on the semantics of the language), then they will have + equivalent TYPE_CANONICAL entries. + + As a special case, if TYPE_CANONICAL is NULL_TREE, then it cannot + be used for comparison against other types. Instead, the type is + said to require structural equality checks, described in + TYPE_STRUCTURAL_EQUALITY_P. */ +#define TYPE_CANONICAL(NODE) (TYPE_CHECK (NODE)->type.canonical) +/* Indicates that the type node requires structural equality + checks. The compiler will need to look at the composition of the + type to determine whether it is equal to another type, rather than + just comparing canonical type pointers. For instance, we would need + to look at the return and parameter types of a FUNCTION_TYPE + node. */ +#define TYPE_STRUCTURAL_EQUALITY_P(NODE) (TYPE_CANONICAL (NODE) == NULL_TREE) +/* Sets the TYPE_CANONICAL field to NULL_TREE, indicating that the + type node requires structural equality. */ +#define SET_TYPE_STRUCTURAL_EQUALITY(NODE) (TYPE_CANONICAL (NODE) = NULL_TREE) #define TYPE_LANG_SPECIFIC(NODE) (TYPE_CHECK (NODE)->type.lang_specific) /* For a VECTOR_TYPE node, this describes a different type which is emitted @@ -2205,6 +2226,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; |