This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lto] Fix gimple type comparison
- From: Diego Novillo <dnovillo at google dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 9 Mar 2009 09:03:14 -0400
- Subject: [lto] Fix gimple type comparison
This patch is another in the series of patches towards type
merging. I am still running into some odd corners and I will
likely do some reorganization on how we read types from disk.
This patch unifies gimple_same_type_p into gimple_types_compatible_p.
The bulk of the change is in the comparison of structures. It
introduces a hash table of type pairs found during structure
comparison to avoid infinite recursion when dealing with
self-referential types.
It also fixes several comparison cases for failures I found
during testing of type merging.
Bootstrapped and tested on x86_64.
Diego.
2009-03-09 Diego Novillo <dnovillo@google.com>
* tree.c (free_lang_data_in_type): Remove all variants
except the main variant of TYPE.
* gimple.c (struct type_pair_d): Define.
(type_pair_t): Define.
(type_pair_hash): New.
(type_pair_eq): New.
(lookup_type_pair): New.
(gimple_compare_types): Factor out of gimple_types_compatible_p.
Compare type sizes, alignment, precision, mode and sign.
Compare values for enumeral types.
Compare all fields of structures and unions.
Fix comparison of TYPE_QUALS.
Compare TYPE_IS_SIZETYPE for integer types.
(gimple_types_compatible_p): Call gimple_compare_types.
(gimple_same_type_p): Remove. Update all callers.
* gimple.h (gimple_same_type_p): Remove.
testsuite/ChangeLog.lto
* gcc.c-torture/execute/builtins/strlen-3.c: Fix ODR issue
for inside_main.
* gcc.dg/lto/20081204-1_0.c: Fix ODR issue for i.
2009-02-20 Simon Baldwin <simonb@google.com>
* g++.dg/lto/20090302_0.C: New.
* g++.dg/lto/20090302_1.C: New.
Index: lto-symtab.c
===================================================================
--- lto-symtab.c (revision 144643)
+++ lto-symtab.c (working copy)
@@ -182,7 +182,7 @@ lto_merge_types (tree type_1, tree type_
&& TREE_CODE (type_2) == ARRAY_TYPE
&& !TYPE_ATTRIBUTES (type_1)
&& !TYPE_ATTRIBUTES (type_2)
- && gimple_same_type_p (TREE_TYPE (type_1), TREE_TYPE (type_2)))
+ && gimple_types_compatible_p (TREE_TYPE (type_1), TREE_TYPE (type_2)))
{
lto_merge_qualifiers (type_1, type_2);
@@ -255,7 +255,7 @@ lto_symtab_compatible (tree old_decl, tr
}
}
- if (!gimple_same_type_p (TREE_TYPE (old_decl), TREE_TYPE (new_decl)))
+ if (!gimple_types_compatible_p (TREE_TYPE (old_decl), TREE_TYPE (new_decl)))
{
/* Allow an array type with unspecified bounds to
be merged with an array type whose bounds are specified, so
Index: tree.c
===================================================================
--- tree.c (revision 144643)
+++ tree.c (working copy)
@@ -3895,26 +3895,13 @@ free_lang_data_in_type (tree type)
FIXME lto: This will break debug info generation. */
TYPE_CONTEXT (type) = NULL_TREE;
- /* Remove type variants that are the same gimple type as the main
- variant. This is both wasteful and it may introduce infinite
- loops when the types are read from disk (since the variant will
- be the same type as the main variant, traversing type variants
- will get into an infinite loop). */
- if (TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (type)))
- {
- tree main_variant = TYPE_MAIN_VARIANT (type);
- tree *tp = &TYPE_NEXT_VARIANT (main_variant);
-
- while (*tp)
- {
- /* If *TP is the same GIMPLE type as MAIN_VARIANT, then it's
- not necessary to have it in the list of variants. */
- if (gimple_same_type_p (*tp, main_variant))
- *tp = TYPE_NEXT_VARIANT (*tp);
- else
- tp = &TYPE_NEXT_VARIANT (*tp);
- }
- }
+ /* Remove type variants other than the main variant. This is both
+ wasteful and it may introduce infinite loops when the types are
+ read from disk and merged (since the variant will be the same
+ type as the main variant, traversing type variants will get into
+ an infinite loop). */
+ if (TYPE_MAIN_VARIANT (type))
+ TYPE_NEXT_VARIANT (TYPE_MAIN_VARIANT (type)) = NULL_TREE;
}
Index: testsuite/gcc.c-torture/execute/builtins/strlen-3.c
===================================================================
--- testsuite/gcc.c-torture/execute/builtins/strlen-3.c (revision 144643)
+++ testsuite/gcc.c-torture/execute/builtins/strlen-3.c (working copy)
@@ -10,7 +10,7 @@ extern char *strcpy (char *, const char
static const char bar[] = "Hello, World!";
static const char baz[] = "hello, world?";
static const char larger[20] = "short string";
-extern volatile int inside_main;
+extern int inside_main;
int l1 = 1;
int x = 6;
Index: testsuite/gcc.dg/lto/20081204-1_0.c
===================================================================
--- testsuite/gcc.dg/lto/20081204-1_0.c (revision 144643)
+++ testsuite/gcc.dg/lto/20081204-1_0.c (working copy)
@@ -4,4 +4,4 @@
/* Tests for the absence during linking of:
lto1: error: type of 'i' does not match original declaration */
-int i[1];
+const int i[1];
Index: testsuite/g++.dg/lto/20090302_1.C
===================================================================
--- testsuite/g++.dg/lto/20090302_1.C (revision 0)
+++ testsuite/g++.dg/lto/20090302_1.C (revision 0)
@@ -0,0 +1,7 @@
+struct Foo {
+ bool Mumble();
+ static void Bar() { if (foo_->Mumble()) foo_ = 0; }
+ static void Baz() { Bar(); }
+ static Foo *foo_;
+};
+Foo *Foo::foo_;
Index: testsuite/g++.dg/lto/20090302_0.C
===================================================================
--- testsuite/g++.dg/lto/20090302_0.C (revision 0)
+++ testsuite/g++.dg/lto/20090302_0.C (revision 0)
@@ -0,0 +1,9 @@
+/* { dg-do "link" } */
+/* { dg-options "{-fPIC -fwhopr -shared}" } */
+struct Foo {
+ bool Mumble();
+ static void Bar() { if (foo_->Mumble()) foo_ = 0; }
+ static void Baz() { Bar(); }
+ static Foo *foo_;
+};
+void Unused() { Foo::Bar(); Foo::Baz(); }
Index: gimple.c
===================================================================
--- gimple.c (revision 144643)
+++ gimple.c (working copy)
@@ -3193,102 +3193,169 @@ gimple_call_copy_skip_args (gimple stmt,
}
-/* Return 1 if TYPE1 and TYPE2 are structurally compatible. */
+/* Structure used to maintain a cache of some type pairs compared by
+ gimple_compare_types when comparing aggregate types. There are
+ four possible values for SAME_P:
-int
-gimple_types_compatible_p (tree type1, tree type2)
+ -2: The pair (T1, T2) has just been inserted in the table.
+ -1: The pair (T1, T2) is currently being compared.
+ 0: T1 and T2 are different types.
+ 1: T1 and T2 are the same type.
+
+ This table is only used when comparing aggregate types to avoid
+ infinite recursion due to self-referential types. */
+struct type_pair_d
{
- /* Types are trivially compatible with themselves. */
- if (type1 == type2)
- return 1;
+ tree t1;
+ tree t2;
+ int same_p;
+};
+typedef struct type_pair_d *type_pair_t;
- /* Only types with the same code can be compatible. */
- if (TREE_CODE (type1) != TREE_CODE (type2))
- return 0;
+/* Return a hash value for the type pair pointed-to by P. */
- /* If the main variants or their canonical type are the same, then
- they are compatible. */
- if (TYPE_MAIN_VARIANT (type1) == TYPE_MAIN_VARIANT (type2)
- || TYPE_CANONICAL (type1) == TYPE_CANONICAL (type2))
- return 1;
+static hashval_t
+type_pair_hash (const void *p)
+{
+ const struct type_pair_d *pair = (const struct type_pair_d *) p;
+ hashval_t val = iterative_hash_hashval_t (htab_hash_pointer (pair->t1), 0);
+ return iterative_hash_hashval_t (htab_hash_pointer (pair->t2), val);
+}
- /* In the case of aggregates, check structural equality. Note that
- at this point, TYPE1 and TYPE2 are guaranteed to have the same
- code already. */
- if (TREE_CODE (type1) == RECORD_TYPE
- || TREE_CODE (type1) == UNION_TYPE
- || TREE_CODE (type1) == QUAL_UNION_TYPE)
- {
- tree f1, f2;
+/* Compare two type pairs pointed-to by P1 and P2. */
- for (f1 = TYPE_FIELDS (type1), f2 = TYPE_FIELDS (type2);
- f1 && f2;
- f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
- if (!gimple_types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
- return 0;
+static int
+type_pair_eq (const void *p1, const void *p2)
+{
+ const struct type_pair_d *pair1 = (const struct type_pair_d *) p1;
+ const struct type_pair_d *pair2 = (const struct type_pair_d *) p2;
+ return (pair1->t1 == pair2->t1 && pair1->t2 == pair2->t2);
+}
- /* If one aggregate is bigger than the other, then they are not
- compatible. */
- return f1 || f2 ? 0 : 1;
+
+/* Lookup the pair of types T1 and T2 in *VISITED_P. Insert a new
+ entry if none existed. */
+
+static type_pair_t
+lookup_type_pair (tree t1, tree t2, htab_t *visited_p)
+{
+ struct type_pair_d pair;
+ type_pair_t p;
+ void **slot;
+
+ if (*visited_p == NULL)
+ *visited_p = htab_create (13, type_pair_hash, type_pair_eq, free);
+
+ pair.t1 = t1;
+ pair.t2 = t2;
+ pair.same_p = -2;
+ slot = htab_find_slot (*visited_p, &pair, INSERT);
+
+ if (*slot)
+ p = *((type_pair_t *) slot);
+ else
+ {
+ p = XCNEW (struct type_pair_d);
+ p->t1 = t1;
+ p->t2 = t2;
+ p->same_p = -2;
+ *slot = (void *) p;
}
- /* In any other case, the two types are not compatible. */
- return 0;
+ return p;
}
-/* Returns true iff T1 and T2 are the same type. */
+/* Recursive helper for gimple_types_compatible_p. Return 1 iff T1
+ and T2 are structurally identical. Otherwise, return 0.
+ VISITED_P points to a hash table of type pairs that have been
+ visited while comparing aggregate types. This prevents infinite
+ recursion when comparing aggregates with self-referential fields. */
-bool
-gimple_same_type_p (tree t1, tree t2)
+static int
+gimple_compare_types (tree t1, tree t2, htab_t *visited_p)
{
/* Check first for the obvious case of pointer identity. */
if (t1 == t2)
- return true;
+ return 1;
/* Check that we have two types to compare. */
if (t1 == NULL_TREE || t2 == NULL_TREE)
- return false;
+ return 0;
/* Can't be the same type if the types don't have the same code. */
if (TREE_CODE (t1) != TREE_CODE (t2))
- return false;
+ return 0;
+
+ /* Void types are always the same. */
+ if (TREE_CODE (t1) == VOID_TYPE)
+ return 1;
+
+ /* Can't be the same type if they have different size, alignment,
+ sign, precision or mode. Note that from now on, comparisons
+ between *_CST nodes must be done using tree_int_cst_equal because
+ we cannot assume that constants from T1 and T2 will be shared
+ since T1 and T2 are distinct pointers. */
+ if (!tree_int_cst_equal (TYPE_SIZE (t1), TYPE_SIZE (t2))
+ || !tree_int_cst_equal (TYPE_SIZE_UNIT (t1), TYPE_SIZE_UNIT (t2))
+ || TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
+ || TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
+ || TYPE_MODE (t1) != TYPE_MODE (t2)
+ || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
+ return 0;
/* Can't be the same type if they have different CV qualifiers. */
- if (TYPE_QUALS (t1) != TYPE_QUALS (t1))
- return false;
+ if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
+ return 0;
/* If their attributes are not the same they can't be the same type. */
if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
- return false;
+ return 0;
- switch (TREE_CODE (t1))
+ /* For numerical types, the bounds must coincide. */
+ if (INTEGRAL_TYPE_P (t1)
+ || SCALAR_FLOAT_TYPE_P (t1)
+ || FIXED_POINT_TYPE_P (t1))
{
- case VOID_TYPE:
- /* Void types are the same in all translation units. */
- return true;
+ /* If either type has a minimum value, the other type must have
+ the same. */
+ if (TYPE_MIN_VALUE (t1) && TYPE_MIN_VALUE (t2))
+ {
+ if (!tree_int_cst_equal (TYPE_MIN_VALUE (t1), TYPE_MIN_VALUE (t2)))
+ return 0;
+ }
+ else if (TYPE_MIN_VALUE (t1) || TYPE_MIN_VALUE (t2))
+ return 0;
+ /* Likewise, if either type has a maximum value, the other type
+ must have the same. */
+ if (TYPE_MAX_VALUE (t1) && TYPE_MAX_VALUE (t2))
+ {
+ if (!tree_int_cst_equal (TYPE_MAX_VALUE (t1), TYPE_MAX_VALUE (t2)))
+ return 0;
+ }
+ else if (TYPE_MAX_VALUE (t1) || TYPE_MAX_VALUE (t2))
+ return 0;
+ }
+
+ /* Do type-specific comparisons. */
+ switch (TREE_CODE (t1))
+ {
case INTEGER_TYPE:
case BOOLEAN_TYPE:
- /* Corresponding integral types are the same. */
- return (TYPE_PRECISION (t1) == TYPE_PRECISION (t2)
- && TYPE_UNSIGNED (t1) == TYPE_UNSIGNED (t2)
- && tree_int_cst_equal (TYPE_SIZE (t1), TYPE_SIZE (t2))
- && TYPE_ALIGN (t1) == TYPE_ALIGN (t2)
+ return (TYPE_IS_SIZETYPE (t1) == TYPE_IS_SIZETYPE (t2)
&& TYPE_STRING_FLAG (t1) == TYPE_STRING_FLAG (t2));
case REAL_TYPE:
- /* Corresponding float types are the same. */
- return (TYPE_PRECISION (t1) == TYPE_PRECISION (t2)
- && tree_int_cst_equal (TYPE_SIZE (t1), TYPE_SIZE (t2))
- && TYPE_ALIGN (t1) == TYPE_ALIGN (t2));
+ /* We've checked every other important attribute already. */
+ return 1;
case ARRAY_TYPE:
/* Array types are the same if the element types are the same and
the number of elements are the same. */
- if (!gimple_same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
+ if (!gimple_compare_types (TREE_TYPE (t1), TREE_TYPE (t2), visited_p)
|| TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
- return false;
+ return 0;
else
{
tree i1 = TYPE_DOMAIN (t1);
@@ -3306,20 +3373,19 @@ gimple_same_type_p (tree t1, tree t2)
tree max2 = TYPE_MAX_VALUE (i2);
/* If the array types both have unspecified bounds, then
- MAX_{1,2} will be NULL_TREE. */
+ MAX{1,2} will be NULL_TREE. */
if (min1 && min2 && !max1 && !max2)
- return (integer_zerop (min1)
- && integer_zerop (min2));
+ return (integer_zerop (min1) && integer_zerop (min2));
/* Otherwise, we need the bounds to be fully
specified. */
if (!min1 || !min2 || !max1 || !max2)
- return false;
+ return 0;
else if (TREE_CODE (min1) != INTEGER_CST
- || TREE_CODE (min2) != INTEGER_CST
- || TREE_CODE (max1) != INTEGER_CST
- || TREE_CODE (max2) != INTEGER_CST)
- return false;
+ || TREE_CODE (min2) != INTEGER_CST
+ || TREE_CODE (max1) != INTEGER_CST
+ || TREE_CODE (max2) != INTEGER_CST)
+ return 0;
else if (tree_int_cst_equal (min1, min2))
return tree_int_cst_equal (max1, max2);
else
@@ -3328,11 +3394,11 @@ gimple_same_type_p (tree t1, tree t2)
tree nelts2 = array_type_nelts (t2);
if (!nelts1 || !nelts2)
- return false;
+ return 0;
if (TREE_CODE (nelts1) != INTEGER_CST
|| TREE_CODE (nelts2) != INTEGER_CST)
- return false;
+ return 0;
return tree_int_cst_equal (nelts1, nelts2);
}
@@ -3342,21 +3408,22 @@ gimple_same_type_p (tree t1, tree t2)
case FUNCTION_TYPE:
/* Function types are the same if the return type and arguments types
are the same. */
- if (!gimple_same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
- return false;
+ if (!gimple_compare_types (TREE_TYPE (t1), TREE_TYPE (t2), visited_p))
+ return 0;
else
{
tree parms1 = TYPE_ARG_TYPES (t1);
tree parms2 = TYPE_ARG_TYPES (t2);
if (parms1 == parms2)
- return true;
+ return 1;
else
{
while (parms1 && parms2)
{
- if (!gimple_same_type_p (TREE_VALUE (parms1),
- TREE_VALUE (parms2)))
- return false;
+ if (!gimple_compare_types (TREE_VALUE (parms1),
+ TREE_VALUE (parms2),
+ visited_p))
+ return 0;
parms1 = TREE_CHAIN (parms1);
parms2 = TREE_CHAIN (parms2);
}
@@ -3366,61 +3433,130 @@ gimple_same_type_p (tree t1, tree t2)
case POINTER_TYPE:
case REFERENCE_TYPE:
- /* Pointer and reference types are the same if the pointed-to types are
- the same. */
- return gimple_same_type_p (TREE_TYPE (t1), TREE_TYPE (t2));
+ {
+ /* If the two pointers have different ref-all attributes,
+ they can't be the same type. */
+ if (TYPE_REF_CAN_ALIAS_ALL (t1) != TYPE_REF_CAN_ALIAS_ALL (t2))
+ return 0;
+
+ /* Otherwise, pointer and reference types are the same if the
+ pointed-to types are the same. */
+ return gimple_compare_types (TREE_TYPE (t1), TREE_TYPE (t2),
+ visited_p);
+ }
case ENUMERAL_TYPE:
+ {
+ /* For enumeral types, all the values must be the same. */
+ tree v1, v2;
+
+ for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
+ v1 && v2;
+ v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
+ {
+ tree c1 = TREE_VALUE (v1);
+ tree c2 = TREE_VALUE (v2);
+
+ if (TREE_CODE (c1) == CONST_DECL)
+ c1 = DECL_INITIAL (c1);
+
+ if (TREE_CODE (c2) == CONST_DECL)
+ c2 = DECL_INITIAL (c2);
+
+ if (tree_int_cst_equal (c1, c2) != 1)
+ return 0;
+ }
+
+ /* If one enumeration has more values than the other, they
+ are not the same. */
+ return v1 || v2 ? 0 : 1;
+ }
+
case RECORD_TYPE:
case UNION_TYPE:
case QUAL_UNION_TYPE:
- /* Enumeration and class types are the same if they have the same
- name. */
- {
- tree variant1 = TYPE_MAIN_VARIANT (t1);
- tree variant2 = TYPE_MAIN_VARIANT (t2);
- tree name1 = TYPE_NAME (t1);
- tree name2 = TYPE_NAME (t2);
- if (!name1 || !name2)
- /* Presumably, anonymous types are all unique. */
- return false;
+ {
+ /* For aggregate types, all the fields must be the same.
+ Use *VISITED_P to mark pairs of fields visited to
+ avoid infinite loops due to self-referential types. */
+ tree f1, f2;
+ type_pair_t p;
- if (TREE_CODE (name1) == TYPE_DECL)
- {
- name1 = DECL_NAME (name1);
- if (!name1)
- return false;
- }
- gcc_assert (TREE_CODE (name1) == IDENTIFIER_NODE);
+ p = lookup_type_pair (t1, t2, visited_p);
+ if (p->same_p == 0 || p->same_p == 1)
+ {
+ /* We have already decided whether T1 and T2 are the
+ same, return the cached result. */
+ return p->same_p == 1;
+ }
+ else if (p->same_p == -1)
+ {
+ /* We are currently comparing this pair of types, assume
+ that they are the same and let the caller decide. */
+ return 1;
+ }
- if (TREE_CODE (name2) == TYPE_DECL)
- {
- name2 = DECL_NAME (name2);
- if (!name2)
- return false;
- }
- gcc_assert (TREE_CODE (name2) == IDENTIFIER_NODE);
+ gcc_assert (p->same_p == -2);
- /* Identifiers can be compared with pointer equality rather
- than a string comparison. */
- if (name1 == name2)
- return true;
+ /* Mark the (T1, T2) comparison in progress. */
+ p->same_p = -1;
- /* If either type has a variant type, compare that. This finds
- the case where a struct is typedef'ed in one module but referred
- to as 'struct foo' in the other; here, the main type for one is
- 'foo', and for the other 'foo_t', but the variants have the same
- name 'foo'. */
- if (variant1 != t1 || variant2 != t2)
- return gimple_same_type_p (variant1, variant2);
- else
- return false;
- }
+ for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
+ f1 && f2;
+ f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
+ {
+ /* The fields must have the same name, offset and type. */
+ if (DECL_NAME (f1) != DECL_NAME (f2)
+ || !tree_int_cst_equal (DECL_FIELD_OFFSET (f1),
+ DECL_FIELD_OFFSET (f2))
+ || !gimple_compare_types (TREE_TYPE (f1),
+ TREE_TYPE (f2),
+ visited_p))
+ {
+ p->same_p = 0;
+ return 0;
+ }
+ }
+
+ if (f1 == NULL && f2 == NULL)
+ {
+ /* If we reached the end of both aggregates, T1 and T2
+ are the same. */
+ p->same_p = 1;
+ return 1;
+ }
+ else
+ {
+ /* Otherwise, they are different. */
+ p->same_p = 0;
+ return 0;
+ }
+ }
- /* FIXME: add pointer to member types. */
default:
- return false;
+ break;
}
+
+ /* The types are different. */
+ return 0;
}
+
+/* Return 1 iff T1 and T2 are the structurally identical. Otherwise,
+ return 0. */
+
+int
+gimple_types_compatible_p (tree t1, tree t2)
+{
+ int same_p;
+ htab_t visited = NULL;
+
+ same_p = gimple_compare_types (t1, t2, &visited);
+
+ if (visited)
+ htab_delete (visited);
+
+ return same_p;
+}
+
#include "gt-gimple.h"
Index: gimple.h
===================================================================
--- gimple.h (revision 144643)
+++ gimple.h (working copy)
@@ -916,7 +916,6 @@ extern tree get_call_expr_in (tree t);
extern void recalculate_side_effects (tree);
extern int gimple_types_compatible_p (tree, tree);
-extern bool gimple_same_type_p (tree, tree);
/* In gimplify.c */
extern tree create_tmp_var_raw (tree, const char *);