This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Canonical types (1/3)
On 12/5/06, Mark Mitchell <mark@codesourcery.com> wrote:
OK, that's great. Unfortunately, I think you should to do that again
with the final patch, which I know takes a while. Feel free to post a
more casually tested patch for me to provisionally review, if you like.
Okay. I have attached the revised patch. As before, it is separated
into 3 different parts: -gcc for the C/common bits, -cp for the C++
front end, -objc for the Objective-C(++) front end. ChangeLog follows.
I have made the following changes to this patch:
- Switched from -f(no-)check-canonical-types to --param
verify-canonical-types=(0|1); documented in invoke.texi.
- Add documentation for the new macros, both in tree.h and c-tree.texi.
- Switched the behavior of build_variant_type_copy to propagate
canonical type information (the common case); this shrunk the patch
quite a bit, because fewer callers have to patch up TYPE_CANONICAL.
- Removed the structural equality bit (+ padding) from the _TYPE
nodes, using TYPE_CANONICAL == NULL_TREE instead. We now only
introduce one extra pointer into every _TYPE node.
- Don't build canonical types when we're constructing a type that
requires structural equality.
This patch has been "lightly" tested, by which I mean that it
bootstraps with C, C++, Objective-C, Objective-C++, and Java; "make
check"s for C, C++, Objective-C, Objective-C++, and libstdc++. No
canonical-type warnings or new failures anywhere on i686-pc-linux-gnu.
Before committing, I also need to run the same tests with
"--disable-checking" (to turn off canonical-type verification
throughout), and repeat the whole suite of tests on
powerpc-apple-darwin8.8.0.
Assuming there are no failures from any of these tests, okay to commit?
Cheers,
Doug
2006-12-06 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.
2006-12-06 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-06 Douglas Gregor <doug.gregor@gmail.com>
* objc-act.c (objc_build_volatilized_type): Keep track of
canonical types.
(objc_get_protocol_qualified_type): Ditto.
Index: c-common.c
===================================================================
--- c-common.c (revision 119580)
+++ c-common.c (working copy)
@@ -3379,6 +3379,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;
@@ -6284,6 +6294,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)
@@ -6360,6 +6371,12 @@ complete_array_type (tree *ptype, tree i
TYPE_DOMAIN (main_type) = build_index_type (maxindex);
layout_type (main_type);
+ /* Make sure we have the canonical MAIN_TYPE. */
+ hashcode = iterative_hash_object (TYPE_HASH (unqual_elt), hashcode);
+ hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (main_type)),
+ hashcode);
+ main_type = type_hash_canon (hashcode, main_type);
+
if (quals == 0)
type = main_type;
else
Index: params.def
===================================================================
--- params.def (revision 119580)
+++ params.def (working copy)
@@ -633,6 +633,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
Index: params.h
===================================================================
--- params.h (revision 119580)
+++ params.h (working copy)
@@ -166,4 +166,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 */
Index: print-tree.c
===================================================================
--- print-tree.c (revision 119580)
+++ print-tree.c (working copy)
@@ -604,6 +604,11 @@ print_node (FILE *file, const char *pref
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)
Index: stor-layout.c
===================================================================
--- stor-layout.c (revision 119580)
+++ 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. */
+ SET_TYPE_STRUCTURAL_EQUALITY (type);
TYPE_USER_ALIGN (type) = TYPE_USER_ALIGN (element);
TYPE_MODE (type) = BLKmode;
if (TYPE_SIZE (type) != 0
Index: tree.c
===================================================================
--- tree.c (revision 119580)
+++ tree.c (working copy)
@@ -566,6 +566,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;
@@ -3580,6 +3581,12 @@ build_type_attribute_qual_variant (tree
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;
@@ -3617,6 +3624,13 @@ build_type_attribute_qual_variant (tree
}
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);
}
@@ -4064,13 +4078,28 @@ build_qualified_type (tree type, int typ
{
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)
@@ -4080,6 +4109,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;
@@ -4087,8 +4123,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)
@@ -4096,6 +4135,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);
@@ -5197,6 +5240,13 @@ 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_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);
@@ -5246,6 +5296,13 @@ 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_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;
@@ -5312,7 +5369,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.
@@ -5404,6 +5466,16 @@ 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_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;
}
@@ -5413,6 +5485,19 @@ build_array_type (tree elt_type, tree in
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;
}
@@ -5454,6 +5539,9 @@ build_function_type (tree value_type, tr
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);
@@ -5521,6 +5609,9 @@ build_method_type_directly (tree basetyp
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);
@@ -5572,6 +5663,18 @@ build_offset_type (tree basetype, tree t
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;
}
@@ -5595,6 +5698,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)
@@ -6613,6 +6725,13 @@ make_vector_type (tree innertype, int nu
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);
{
@@ -6826,7 +6945,7 @@ build_common_tree_nodes_2 (int short_dou
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;
}
}
Index: tree.h
===================================================================
--- tree.h (revision 119580)
+++ tree.h (working copy)
@@ -1989,6 +1989,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
@@ -2189,6 +2210,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: doc/c-tree.texi
===================================================================
--- doc/c-tree.texi (revision 119580)
+++ doc/c-tree.texi (working copy)
@@ -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
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
Index: doc/invoke.texi
===================================================================
--- doc/invoke.texi (revision 119580)
+++ doc/invoke.texi (working copy)
@@ -6365,6 +6365,13 @@ The size of cache line in L1 cache, in b
@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
Index: typeck.c
===================================================================
--- typeck.c (revision 119580)
+++ typeck.c (working copy)
@@ -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
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
Index: decl.c
===================================================================
--- decl.c (revision 119580)
+++ decl.c (working copy)
@@ -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
/* 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 contex
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, tre
{
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, 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));
+ 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, 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 119580)
+++ 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,47 @@ 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_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, tre
TYPE_NAME (t2) = decl;
TYPE_STUB_DECL (t2) = decl;
TYPE_SIZE (t2) = 0;
+ SET_TYPE_STRUCTURAL_EQUALITY (t2);
return t2;
}
Index: cp-tree.h
===================================================================
--- cp-tree.h (revision 119580)
+++ 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 119580)
+++ 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. */
+ SET_TYPE_STRUCTURAL_EQUALITY (t);
}
/* If we called start_enum or pushtag above, this information
@@ -7462,6 +7510,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. */
+ 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,
@@ -13144,6 +13204,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
Index: objc-act.c
===================================================================
--- objc-act.c (revision 119580)
+++ objc-act.c (working copy)
@@ -908,6 +908,10 @@ 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) && TYPE_CANONICAL (type) != type)
+ TYPE_CANONICAL (t) = objc_build_volatilized_type (TYPE_CANONICAL (type));
+
return t;
}
@@ -1370,7 +1374,13 @@ objc_get_protocol_qualified_type (tree i
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);
}