[lto] Merge types as they are read from disk (1/3)
Diego Novillo
dnovillo@google.com
Mon Mar 2 13:27:00 GMT 2009
This patch is the first in a series of patches we've worked with
Simon last week. The basic problem is that when reading types
from disk, we instantiate new TREE_TYPE nodes without checking
for duplicates. This means that we may have the same identical
type represented by two trees T1 and T2, which may even have
different alias set numbers, so we consider them not compatible.
This can confuse optimizers and it's a significant source of
memory bloat (800Mb out of 1.5Gb in one test case).
This patch moves lto_same_type_p into gimple_same_type_p and adds
a couple of additional checks to determine if two types are
the same. Together with gimple_types_compatible_p, this
predicate forms the basis for the gimple type system.
The second change it introduces is to remove type variants that
are physically identical to the main variant. The front ends
introduce variants that only differ in that they have a different
TYPE_NAME than their main variant. This will need to be
preserved as part of the debugging information, but they're not
necessary in gimple. Furthermore, they cause infinite loops in
the main_variant->next_variant chaining because when we read them
from disk and merge identical types, we end up with an infinite
loop in that chain.
The second patch will introduce the actual type merging and the
third patch will speed up duplicate type detection.
Bootstrapped and tested on x86_64.
Diego.
* gimple.c (gimple_same_type_p): Move from lto-symtab.c.
Rename from lto_same_type_p. Update all users.
Compare TYPE_QUALS and TYPE_ATTRIBUTES.
* gimple.h (gimple_same_type_p): Declare.
* lto-tree-in.h: Fix comment.
* tree.c (free_lang_data_in_type): Remove variants that
are the same gimple type as the main variant.
* lto-symtab.c (lto_merge_qualifiers): Merge in both
directions.
(lto_merge_types): Always merge qualifiers for merged
ARRAY_TYPEs.
Index: lto-symtab.c
===================================================================
--- lto-symtab.c (revision 144476)
+++ lto-symtab.c (working copy)
@@ -143,201 +143,31 @@ lto_symtab_maybe_init_hash_tables (void)
}
}
-/* Returns true iff TYPE_1 and TYPE_2 are the same type. */
-
-static bool
-lto_same_type_p (tree type_1, tree type_2)
-{
- unsigned int code;
-
- /* Check first for the obvious case of pointer identity. */
- if (type_1 == type_2)
- return true;
-
- /* Check that we have two types to compare. */
- if (type_1 == NULL_TREE || type_2 == NULL_TREE)
- return false;
-
- /* Can't be the same type if the types don't have the same code. */
- code = TREE_CODE (type_1);
- if (code != TREE_CODE (type_2))
- return false;
-
- /* "If GNU attributes are present, types which could be the same be it not
- for their GNU attributes may in fact be different due to the use of GNU
- attributes." Hmmm. Punt on this for now and assume they're different
- if we see attributes on either type. */
- if (TYPE_ATTRIBUTES (type_1) || TYPE_ATTRIBUTES (type_2))
- return false;
-
- switch (code)
- {
- case VOID_TYPE:
- /* Void types are the same in all translation units. */
- return true;
-
- case INTEGER_TYPE:
- case BOOLEAN_TYPE:
- /* Corresponding integral types are the same. */
- return (TYPE_PRECISION (type_1) == TYPE_PRECISION (type_2)
- && TYPE_UNSIGNED (type_1) == TYPE_UNSIGNED (type_2)
- && tree_int_cst_equal (TYPE_SIZE (type_1), TYPE_SIZE (type_2))
- && TYPE_ALIGN (type_1) == TYPE_ALIGN (type_2)
- && TYPE_STRING_FLAG (type_1) == TYPE_STRING_FLAG (type_2));
-
- case REAL_TYPE:
- /* Corresponding float types are the same. */
- return (TYPE_PRECISION (type_1) == TYPE_PRECISION (type_2)
- && tree_int_cst_equal (TYPE_SIZE (type_1), TYPE_SIZE (type_2))
- && TYPE_ALIGN (type_1) == TYPE_ALIGN (type_2));
-
- case ARRAY_TYPE:
- /* Array types are the same if the element types are the same and
- the number of elements are the same. */
- if (!lto_same_type_p (TREE_TYPE (type_1), TREE_TYPE (type_2))
- || TYPE_STRING_FLAG (type_1) != TYPE_STRING_FLAG (type_2))
- return false;
- else
- {
- tree index_1 = TYPE_DOMAIN (type_1);
- tree index_2 = TYPE_DOMAIN (type_2);
- /* For an incomplete external array, the type domain can be
- NULL_TREE. Check this condition also. */
- if (!index_1 || !index_2)
- return (!index_1 && !index_2);
- else
- {
- tree min_1 = TYPE_MIN_VALUE (index_1);
- tree min_2 = TYPE_MIN_VALUE (index_2);
- tree max_1 = TYPE_MAX_VALUE (index_1);
- tree max_2 = TYPE_MAX_VALUE (index_2);
- /* If the array types both have unspecified bounds, then
- MAX_{1,2} will be NULL_TREE. */
- if (min_1 && min_2 && !max_1 && !max_2)
- return (integer_zerop (min_1)
- && integer_zerop (min_2));
- /* Otherwise, we need the bounds to be fully
- specified. */
- if (!min_1 || !min_2 || !max_1 || !max_2)
- return false;
- if (TREE_CODE (min_1) != INTEGER_CST
- || TREE_CODE (min_2) != INTEGER_CST
- || TREE_CODE (max_1) != INTEGER_CST
- || TREE_CODE (max_2) != INTEGER_CST)
- return false;
- if (tree_int_cst_equal (min_1, min_2))
- return tree_int_cst_equal (max_1, max_2);
- else
- {
- tree nelts_1 = array_type_nelts (type_1);
- tree nelts_2 = array_type_nelts (type_2);
- if (! nelts_1 || ! nelts_2)
- return false;
- if (TREE_CODE (nelts_1) != INTEGER_CST
- || TREE_CODE (nelts_2) != INTEGER_CST)
- return false;
- return tree_int_cst_equal (nelts_1, nelts_2);
- }
- }
- }
-
- case FUNCTION_TYPE:
- /* Function types are the same if the return type and arguments types
- are the same. */
- if (!lto_same_type_p (TREE_TYPE (type_1), TREE_TYPE (type_2)))
- return false;
- else
- {
- tree parms_1 = TYPE_ARG_TYPES (type_1);
- tree parms_2 = TYPE_ARG_TYPES (type_2);
- if (parms_1 == parms_2)
- return true;
- else
- {
- while (parms_1 && parms_2)
- {
- if (!lto_same_type_p (TREE_VALUE (parms_1),
- TREE_VALUE (parms_2)))
- return false;
- parms_1 = TREE_CHAIN (parms_1);
- parms_2 = TREE_CHAIN (parms_2);
- }
- return !parms_1 && !parms_2;
- }
- }
-
- case POINTER_TYPE:
- case REFERENCE_TYPE:
- /* Pointer and reference types are the same if the pointed-to types are
- the same. */
- return lto_same_type_p (TREE_TYPE (type_1), TREE_TYPE (type_2));
-
- case ENUMERAL_TYPE:
- case RECORD_TYPE:
- case UNION_TYPE:
- case QUAL_UNION_TYPE:
- /* Enumeration and class types are the same if they have the same
- name. */
- {
- tree variant_1 = TYPE_MAIN_VARIANT (type_1);
- tree variant_2 = TYPE_MAIN_VARIANT (type_2);
- tree name_1 = TYPE_NAME (type_1);
- tree name_2 = TYPE_NAME (type_2);
- if (!name_1 || !name_2)
- /* Presumably, anonymous types are all unique. */
- return false;
-
- if (TREE_CODE (name_1) == TYPE_DECL)
- {
- name_1 = DECL_NAME (name_1);
- if (! name_1)
- return false;
- }
- gcc_assert (TREE_CODE (name_1) == IDENTIFIER_NODE);
-
- if (TREE_CODE (name_2) == TYPE_DECL)
- {
- name_2 = DECL_NAME (name_2);
- if (! name_2)
- return false;
- }
- gcc_assert (TREE_CODE (name_2) == IDENTIFIER_NODE);
-
- /* Identifiers can be compared with pointer equality rather
- than a string comparison. */
- if (name_1 == name_2)
- return true;
-
- /* 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 (variant_1 != type_1 || variant_2 != type_2)
- return lto_same_type_p (variant_1, variant_2);
- else
- return false;
- }
-
- /* FIXME: add pointer to member types. */
- default:
- return false;
- }
-}
-
-/* Transfer TYPE_2 qualifiers to TYPE_1 so that TYPE_1's qualifiers are
- conservatively correct with respect to optimization done before the
- merge. */
+/* Transfer qualifiers between TYPE_1 and TYPE_2 so that qualifiers
+ for both types are conservatively correct with respect to
+ optimization done before the merge. */
static void
lto_merge_qualifiers (tree type_1, tree type_2)
{
+ /* If one is volatile, the other should also be. */
if (TYPE_VOLATILE (type_2))
- TYPE_VOLATILE (type_1) = TYPE_VOLATILE (type_2);
- if (! TYPE_READONLY (type_2))
- TYPE_READONLY (type_1) = TYPE_READONLY (type_2);
- if (! TYPE_RESTRICT (type_2))
- TYPE_RESTRICT (type_1) = TYPE_RESTRICT (type_2);
+ TYPE_VOLATILE (type_1) = 1;
+ else if (TYPE_VOLATILE (type_1))
+ TYPE_VOLATILE (type_2) = 1;
+
+ /* If one type is writable, the other should also be. */
+ if (!TYPE_READONLY (type_2))
+ TYPE_READONLY (type_1) = 0;
+ else if (!TYPE_READONLY (type_1))
+ TYPE_READONLY (type_2) = 0;
+
+ /* If one type does not have the restrict qualifier, the other
+ should not have it either. */
+ if (!TYPE_RESTRICT (type_2))
+ TYPE_RESTRICT (type_1) = 0;
+ else if (!TYPE_RESTRICT (type_1))
+ TYPE_RESTRICT (type_2) = 0;
}
/* If TYPE_1 and TYPE_2 can be merged to form a common type, do it.
@@ -349,23 +179,21 @@ static tree
lto_merge_types (tree type_1, tree type_2)
{
if (TREE_CODE (type_1) == ARRAY_TYPE
- && (TREE_CODE (type_2) == ARRAY_TYPE)
- && ! TYPE_ATTRIBUTES (type_1) && ! TYPE_ATTRIBUTES (type_2)
- && (lto_same_type_p (TREE_TYPE (type_1), TREE_TYPE (type_2))))
+ && 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)))
{
+ lto_merge_qualifiers (type_1, type_2);
+
if (COMPLETE_TYPE_P (type_1) && !COMPLETE_TYPE_P (type_2))
- {
- lto_merge_qualifiers (type_1, type_2);
- return type_1;
- }
+ return type_1;
else if (COMPLETE_TYPE_P (type_2) && !COMPLETE_TYPE_P (type_1))
- {
- lto_merge_qualifiers (type_2, type_1);
- return type_2;
- }
+ return type_2;
else
return NULL_TREE;
}
+
return NULL_TREE;
}
@@ -427,7 +255,7 @@ lto_symtab_compatible (tree old_decl, tr
}
}
- if (!lto_same_type_p (TREE_TYPE (old_decl), TREE_TYPE (new_decl)))
+ if (!gimple_same_type_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 144476)
+++ tree.c (working copy)
@@ -3894,6 +3894,27 @@ free_lang_data_in_type (tree type)
scoping and should not be part of the IR.
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);
+ }
+ }
}
Index: lto-tree-in.h
===================================================================
--- lto-tree-in.h (revision 144476)
+++ lto-tree-in.h (working copy)
@@ -98,7 +98,7 @@ lto_input_constructors_and_inits (struct
const char *data);
-/* lto-symtab.c */
+/* In lto-symtab.c. */
/* The NEW_VAR (a VAR_DECL) has just been read with resolution RESOLUTION. If
there is an existing variable with the same name, merge the declaration for
Index: gimple.c
===================================================================
--- gimple.c (revision 144476)
+++ gimple.c (working copy)
@@ -3236,4 +3236,191 @@ gimple_types_compatible_p (tree type1, t
return 0;
}
+
+/* Returns true iff T1 and T2 are the same type. */
+
+bool
+gimple_same_type_p (tree t1, tree t2)
+{
+ /* Check first for the obvious case of pointer identity. */
+ if (t1 == t2)
+ return true;
+
+ /* Check that we have two types to compare. */
+ if (t1 == NULL_TREE || t2 == NULL_TREE)
+ return false;
+
+ /* Can't be the same type if the types don't have the same code. */
+ if (TREE_CODE (t1) != TREE_CODE (t2))
+ return false;
+
+ /* Can't be the same type if they have different CV qualifiers. */
+ if (TYPE_QUALS (t1) != TYPE_QUALS (t1))
+ return false;
+
+ /* 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;
+
+ switch (TREE_CODE (t1))
+ {
+ case VOID_TYPE:
+ /* Void types are the same in all translation units. */
+ return true;
+
+ 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)
+ && 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));
+
+ 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))
+ || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
+ return false;
+ else
+ {
+ tree i1 = TYPE_DOMAIN (t1);
+ tree i2 = TYPE_DOMAIN (t2);
+
+ /* For an incomplete external array, the type domain can be
+ NULL_TREE. Check this condition also. */
+ if (!i1 || !i2)
+ return (!i1 && !i2);
+ else
+ {
+ tree min1 = TYPE_MIN_VALUE (i1);
+ tree min2 = TYPE_MIN_VALUE (i2);
+ tree max1 = TYPE_MAX_VALUE (i1);
+ tree max2 = TYPE_MAX_VALUE (i2);
+
+ /* If the array types both have unspecified bounds, then
+ MAX_{1,2} will be NULL_TREE. */
+ if (min1 && min2 && !max1 && !max2)
+ return (integer_zerop (min1)
+ && integer_zerop (min2));
+
+ /* Otherwise, we need the bounds to be fully
+ specified. */
+ if (!min1 || !min2 || !max1 || !max2)
+ return false;
+ else if (TREE_CODE (min1) != INTEGER_CST
+ || TREE_CODE (min2) != INTEGER_CST
+ || TREE_CODE (max1) != INTEGER_CST
+ || TREE_CODE (max2) != INTEGER_CST)
+ return false;
+ else if (tree_int_cst_equal (min1, min2))
+ return tree_int_cst_equal (max1, max2);
+ else
+ {
+ tree nelts1 = array_type_nelts (t1);
+ tree nelts2 = array_type_nelts (t2);
+
+ if (!nelts1 || !nelts2)
+ return false;
+
+ if (TREE_CODE (nelts1) != INTEGER_CST
+ || TREE_CODE (nelts2) != INTEGER_CST)
+ return false;
+
+ return tree_int_cst_equal (nelts1, nelts2);
+ }
+ }
+ }
+
+ 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;
+ else
+ {
+ tree parms1 = TYPE_ARG_TYPES (t1);
+ tree parms2 = TYPE_ARG_TYPES (t2);
+ if (parms1 == parms2)
+ return true;
+ else
+ {
+ while (parms1 && parms2)
+ {
+ if (!gimple_same_type_p (TREE_VALUE (parms1),
+ TREE_VALUE (parms2)))
+ return false;
+ parms1 = TREE_CHAIN (parms1);
+ parms2 = TREE_CHAIN (parms2);
+ }
+ return !parms1 && !parms2;
+ }
+ }
+
+ 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));
+
+ case ENUMERAL_TYPE:
+ 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;
+
+ if (TREE_CODE (name1) == TYPE_DECL)
+ {
+ name1 = DECL_NAME (name1);
+ if (!name1)
+ return false;
+ }
+ gcc_assert (TREE_CODE (name1) == IDENTIFIER_NODE);
+
+ if (TREE_CODE (name2) == TYPE_DECL)
+ {
+ name2 = DECL_NAME (name2);
+ if (!name2)
+ return false;
+ }
+ gcc_assert (TREE_CODE (name2) == IDENTIFIER_NODE);
+
+ /* Identifiers can be compared with pointer equality rather
+ than a string comparison. */
+ if (name1 == name2)
+ return true;
+
+ /* 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;
+ }
+
+ /* FIXME: add pointer to member types. */
+ default:
+ return false;
+ }
+}
+
#include "gt-gimple.h"
Index: gimple.h
===================================================================
--- gimple.h (revision 144476)
+++ gimple.h (working copy)
@@ -916,6 +916,7 @@ 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 *);
More information about the Gcc-patches
mailing list