===================================================================
@@ -882,9 +882,8 @@ extern bool is_gimple_call_addr (tree);
extern void recalculate_side_effects (tree);
extern bool gimple_compare_field_offset (tree, tree);
-extern tree gimple_register_type (tree);
extern tree gimple_register_canonical_type (tree);
-extern void print_gimple_types_stats (void);
+extern void print_gimple_types_stats (const char *);
extern void free_gimple_type_tables (void);
extern tree gimple_unsigned_type (tree);
extern tree gimple_signed_type (tree);
===================================================================
@@ -785,7 +785,7 @@ extern const char *lto_tag_name (enum LT
extern bitmap lto_bitmap_alloc (void);
extern void lto_bitmap_free (bitmap);
extern char *lto_get_section_name (int, const char *, struct lto_file_decl_data *);
-extern void print_lto_report (void);
+extern void print_lto_report (const char *);
extern void lto_streamer_init (void);
extern bool gate_lto_out (void);
#ifdef LTO_STREAMER_DEBUG
===================================================================
@@ -180,12 +180,10 @@ lto_get_section_name (int section_type,
/* Show various memory usage statistics related to LTO. */
void
-print_lto_report (void)
+print_lto_report (const char *s)
{
- const char *s = (flag_lto) ? "LTO" : (flag_wpa) ? "WPA" : "LTRANS";
unsigned i;
- fprintf (stderr, "%s statistics\n", s);
fprintf (stderr, "[%s] # of input files: "
HOST_WIDE_INT_PRINT_UNSIGNED "\n", s, lto_stats.num_input_files);
@@ -197,9 +195,6 @@ print_lto_report (void)
HOST_WIDE_INT_PRINT_UNSIGNED "\n", s,
lto_stats.num_function_bodies);
- fprintf (stderr, "[%s] ", s);
- print_gimple_types_stats ();
-
for (i = 0; i < NUM_TREE_CODES; i++)
if (lto_stats.num_trees[i])
fprintf (stderr, "[%s] # of '%s' objects read: "
===================================================================
@@ -37,17 +37,10 @@ along with GCC; see the file COPYING3.
#include "demangle.h"
#include "langhooks.h"
-/* Global type table. FIXME lto, it should be possible to re-use some
- of the type hashing routines in tree.c (type_hash_canon, type_hash_lookup,
- etc), but those assume that types were built with the various
- build_*_type routines which is not the case with the streamer. */
-static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
- htab_t gimple_types;
+/* Global canonical type table. */
static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
htab_t gimple_canonical_types;
static GTY((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
- htab_t type_hash_cache;
-static GTY((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
htab_t canonical_type_hash_cache;
/* All the tuples have their operand vector (if present) at the very bottom
@@ -3014,159 +3007,6 @@ gimple_call_copy_skip_args (gimple stmt,
}
-enum gtc_mode { GTC_MERGE = 0, GTC_DIAG = 1 };
-
-static hashval_t gimple_type_hash (const void *);
-
-/* Structure used to maintain a cache of some type pairs compared by
- gimple_types_compatible_p when comparing aggregate types. There are
- three possible values for SAME_P:
-
- -2: The pair (T1, T2) has just been inserted in the table.
- 0: T1 and T2 are different types.
- 1: T1 and T2 are the same type.
-
- The two elements in the SAME_P array are indexed by the comparison
- mode gtc_mode. */
-
-struct type_pair_d
-{
- unsigned int uid1;
- unsigned int uid2;
- signed char same_p[2];
-};
-typedef struct type_pair_d *type_pair_t;
-DEF_VEC_P(type_pair_t);
-DEF_VEC_ALLOC_P(type_pair_t,heap);
-
-#define GIMPLE_TYPE_PAIR_SIZE 16381
-struct type_pair_d *type_pair_cache;
-
-
-/* Lookup the pair of types T1 and T2 in *VISITED_P. Insert a new
- entry if none existed. */
-
-static inline type_pair_t
-lookup_type_pair (tree t1, tree t2)
-{
- unsigned int index;
- unsigned int uid1, uid2;
-
- if (type_pair_cache == NULL)
- type_pair_cache = XCNEWVEC (struct type_pair_d, GIMPLE_TYPE_PAIR_SIZE);
-
- if (TYPE_UID (t1) < TYPE_UID (t2))
- {
- uid1 = TYPE_UID (t1);
- uid2 = TYPE_UID (t2);
- }
- else
- {
- uid1 = TYPE_UID (t2);
- uid2 = TYPE_UID (t1);
- }
- gcc_checking_assert (uid1 != uid2);
-
- /* iterative_hash_hashval_t imply an function calls.
- We know that UIDS are in limited range. */
- index = ((((unsigned HOST_WIDE_INT)uid1 << HOST_BITS_PER_WIDE_INT / 2) + uid2)
- % GIMPLE_TYPE_PAIR_SIZE);
- if (type_pair_cache [index].uid1 == uid1
- && type_pair_cache [index].uid2 == uid2)
- return &type_pair_cache[index];
-
- type_pair_cache [index].uid1 = uid1;
- type_pair_cache [index].uid2 = uid2;
- type_pair_cache [index].same_p[0] = -2;
- type_pair_cache [index].same_p[1] = -2;
-
- return &type_pair_cache[index];
-}
-
-/* Per pointer state for the SCC finding. The on_sccstack flag
- is not strictly required, it is true when there is no hash value
- recorded for the type and false otherwise. But querying that
- is slower. */
-
-struct sccs
-{
- unsigned int dfsnum;
- unsigned int low;
- bool on_sccstack;
- union {
- hashval_t hash;
- signed char same_p;
- } u;
-};
-
-static unsigned int next_dfs_num;
-static unsigned int gtc_next_dfs_num;
-
-
-/* GIMPLE type merging cache. A direct-mapped cache based on TYPE_UID. */
-
-typedef struct GTY(()) gimple_type_leader_entry_s {
- tree type;
- tree leader;
-} gimple_type_leader_entry;
-
-#define GIMPLE_TYPE_LEADER_SIZE 16381
-static GTY((deletable, length("GIMPLE_TYPE_LEADER_SIZE")))
- gimple_type_leader_entry *gimple_type_leader;
-
-/* Lookup an existing leader for T and return it or NULL_TREE, if
- there is none in the cache. */
-
-static inline tree
-gimple_lookup_type_leader (tree t)
-{
- gimple_type_leader_entry *leader;
-
- if (!gimple_type_leader)
- return NULL_TREE;
-
- leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
- if (leader->type != t)
- return NULL_TREE;
-
- return leader->leader;
-}
-
-/* Return true if T1 and T2 have the same name. If FOR_COMPLETION_P is
- true then if any type has no name return false, otherwise return
- true if both types have no names. */
-
-static bool
-compare_type_names_p (tree t1, tree t2)
-{
- tree name1 = TYPE_NAME (t1);
- tree name2 = TYPE_NAME (t2);
-
- if ((name1 != NULL_TREE) != (name2 != NULL_TREE))
- return false;
-
- if (name1 == NULL_TREE)
- return true;
-
- /* Either both should be a TYPE_DECL or both an IDENTIFIER_NODE. */
- if (TREE_CODE (name1) != TREE_CODE (name2))
- return false;
-
- if (TREE_CODE (name1) == TYPE_DECL)
- name1 = DECL_NAME (name1);
- gcc_checking_assert (!name1 || TREE_CODE (name1) == IDENTIFIER_NODE);
-
- if (TREE_CODE (name2) == TYPE_DECL)
- name2 = DECL_NAME (name2);
- gcc_checking_assert (!name2 || TREE_CODE (name2) == IDENTIFIER_NODE);
-
- /* Identifiers can be compared with pointer equality rather
- than a string comparison. */
- if (name1 == name2)
- return true;
-
- return false;
-}
/* Return true if the field decls F1 and F2 are at the same offset.
@@ -3219,892 +3059,6 @@ gimple_compare_field_offset (tree f1, tr
return false;
}
-static bool
-gimple_types_compatible_p_1 (tree, tree, type_pair_t,
- VEC(type_pair_t, heap) **,
- struct pointer_map_t *, struct obstack *);
-
-/* DFS visit the edge from the callers type pair with state *STATE to
- the pair T1, T2 while operating in FOR_MERGING_P mode.
- Update the merging status if it is not part of the SCC containing the
- callers pair and return it.
- SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done. */
-
-static bool
-gtc_visit (tree t1, tree t2,
- struct sccs *state,
- VEC(type_pair_t, heap) **sccstack,
- struct pointer_map_t *sccstate,
- struct obstack *sccstate_obstack)
-{
- struct sccs *cstate = NULL;
- type_pair_t p;
- void **slot;
- tree leader1, leader2;
-
- /* 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 (t2))
- return false;
-
- if (TREE_ADDRESSABLE (t1) != TREE_ADDRESSABLE (t2))
- return false;
-
- /* Void types and nullptr types are always the same. */
- if (TREE_CODE (t1) == VOID_TYPE
- || TREE_CODE (t1) == NULLPTR_TYPE)
- return true;
-
- /* Can't be the same type if they have different alignment or mode. */
- if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
- || TYPE_MODE (t1) != TYPE_MODE (t2))
- return false;
-
- /* Do some simple checks before doing three hashtable queries. */
- if (INTEGRAL_TYPE_P (t1)
- || SCALAR_FLOAT_TYPE_P (t1)
- || FIXED_POINT_TYPE_P (t1)
- || TREE_CODE (t1) == VECTOR_TYPE
- || TREE_CODE (t1) == COMPLEX_TYPE
- || TREE_CODE (t1) == OFFSET_TYPE
- || POINTER_TYPE_P (t1))
- {
- /* Can't be the same type if they have different sign or precision. */
- if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
- || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
- return false;
-
- if (TREE_CODE (t1) == INTEGER_TYPE
- && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
- return false;
-
- /* That's all we need to check for float and fixed-point types. */
- if (SCALAR_FLOAT_TYPE_P (t1)
- || FIXED_POINT_TYPE_P (t1))
- return true;
-
- /* For other types fall through to more complex checks. */
- }
-
- /* If the types have been previously registered and found equal
- they still are. */
- leader1 = gimple_lookup_type_leader (t1);
- leader2 = gimple_lookup_type_leader (t2);
- if (leader1 == t2
- || t1 == leader2
- || (leader1 && leader1 == leader2))
- return true;
-
- /* If the hash values of t1 and t2 are different the types can't
- possibly be the same. This helps keeping the type-pair hashtable
- small, only tracking comparisons for hash collisions. */
- if (gimple_type_hash (t1) != gimple_type_hash (t2))
- return false;
-
- /* Allocate a new cache entry for this comparison. */
- p = lookup_type_pair (t1, t2);
- if (p->same_p[GTC_MERGE] == 0 || p->same_p[GTC_MERGE] == 1)
- {
- /* We have already decided whether T1 and T2 are the
- same, return the cached result. */
- return p->same_p[GTC_MERGE] == 1;
- }
-
- if ((slot = pointer_map_contains (sccstate, p)) != NULL)
- cstate = (struct sccs *)*slot;
- /* Not yet visited. DFS recurse. */
- if (!cstate)
- {
- gimple_types_compatible_p_1 (t1, t2, p,
- sccstack, sccstate, sccstate_obstack);
- cstate = (struct sccs *)* pointer_map_contains (sccstate, p);
- state->low = MIN (state->low, cstate->low);
- }
- /* If the type is still on the SCC stack adjust the parents low. */
- if (cstate->dfsnum < state->dfsnum
- && cstate->on_sccstack)
- state->low = MIN (cstate->dfsnum, state->low);
-
- /* Return the current lattice value. We start with an equality
- assumption so types part of a SCC will be optimistically
- treated equal unless proven otherwise. */
- return cstate->u.same_p;
-}
-
-/* Worker for gimple_types_compatible.
- SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done. */
-
-static bool
-gimple_types_compatible_p_1 (tree t1, tree t2, type_pair_t p,
- VEC(type_pair_t, heap) **sccstack,
- struct pointer_map_t *sccstate,
- struct obstack *sccstate_obstack)
-{
- struct sccs *state;
-
- gcc_assert (p->same_p[GTC_MERGE] == -2);
-
- state = XOBNEW (sccstate_obstack, struct sccs);
- *pointer_map_insert (sccstate, p) = state;
-
- VEC_safe_push (type_pair_t, heap, *sccstack, p);
- state->dfsnum = gtc_next_dfs_num++;
- state->low = state->dfsnum;
- state->on_sccstack = true;
- /* Start with an equality assumption. As we DFS recurse into child
- SCCs this assumption may get revisited. */
- state->u.same_p = 1;
-
- /* The struct tags shall compare equal. */
- if (!compare_type_names_p (t1, t2))
- goto different_types;
-
- /* We may not merge typedef types to the same type in different
- contexts. */
- if (TYPE_NAME (t1)
- && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
- && DECL_CONTEXT (TYPE_NAME (t1))
- && TYPE_P (DECL_CONTEXT (TYPE_NAME (t1))))
- {
- if (!gtc_visit (DECL_CONTEXT (TYPE_NAME (t1)),
- DECL_CONTEXT (TYPE_NAME (t2)),
- state, sccstack, sccstate, sccstate_obstack))
- goto different_types;
- }
-
- /* If their attributes are not the same they can't be the same type. */
- if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
- goto different_types;
-
- /* Do type-specific comparisons. */
- switch (TREE_CODE (t1))
- {
- case VECTOR_TYPE:
- case COMPLEX_TYPE:
- if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
- state, sccstack, sccstate, sccstate_obstack))
- goto different_types;
- goto same_types;
-
- case ARRAY_TYPE:
- /* Array types are the same if the element types are the same and
- the number of elements are the same. */
- if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
- state, sccstack, sccstate, sccstate_obstack)
- || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
- || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
- goto different_types;
- 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 == NULL_TREE && i2 == NULL_TREE)
- goto same_types;
- else if (i1 == NULL_TREE || i2 == NULL_TREE)
- goto different_types;
- 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);
-
- /* The minimum/maximum values have to be the same. */
- if ((min1 == min2
- || (min1 && min2
- && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
- && TREE_CODE (min2) == PLACEHOLDER_EXPR)
- || operand_equal_p (min1, min2, 0))))
- && (max1 == max2
- || (max1 && max2
- && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
- && TREE_CODE (max2) == PLACEHOLDER_EXPR)
- || operand_equal_p (max1, max2, 0)))))
- goto same_types;
- else
- goto different_types;
- }
- }
-
- case METHOD_TYPE:
- /* Method types should belong to the same class. */
- if (!gtc_visit (TYPE_METHOD_BASETYPE (t1), TYPE_METHOD_BASETYPE (t2),
- state, sccstack, sccstate, sccstate_obstack))
- goto different_types;
-
- /* Fallthru */
-
- case FUNCTION_TYPE:
- /* Function types are the same if the return type and arguments types
- are the same. */
- if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
- state, sccstack, sccstate, sccstate_obstack))
- goto different_types;
-
- if (!comp_type_attributes (t1, t2))
- goto different_types;
-
- if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
- goto same_types;
- else
- {
- tree parms1, parms2;
-
- for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
- parms1 && parms2;
- parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
- {
- if (!gtc_visit (TREE_VALUE (parms1), TREE_VALUE (parms2),
- state, sccstack, sccstate, sccstate_obstack))
- goto different_types;
- }
-
- if (parms1 || parms2)
- goto different_types;
-
- goto same_types;
- }
-
- case OFFSET_TYPE:
- {
- if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
- state, sccstack, sccstate, sccstate_obstack)
- || !gtc_visit (TYPE_OFFSET_BASETYPE (t1),
- TYPE_OFFSET_BASETYPE (t2),
- state, sccstack, sccstate, sccstate_obstack))
- goto different_types;
-
- goto same_types;
- }
-
- case POINTER_TYPE:
- case REFERENCE_TYPE:
- {
- /* 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))
- goto different_types;
-
- /* Otherwise, pointer and reference types are the same if the
- pointed-to types are the same. */
- if (gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
- state, sccstack, sccstate, sccstate_obstack))
- goto same_types;
-
- goto different_types;
- }
-
- case INTEGER_TYPE:
- case BOOLEAN_TYPE:
- {
- tree min1 = TYPE_MIN_VALUE (t1);
- tree max1 = TYPE_MAX_VALUE (t1);
- tree min2 = TYPE_MIN_VALUE (t2);
- tree max2 = TYPE_MAX_VALUE (t2);
- bool min_equal_p = false;
- bool max_equal_p = false;
-
- /* If either type has a minimum value, the other type must
- have the same. */
- if (min1 == NULL_TREE && min2 == NULL_TREE)
- min_equal_p = true;
- else if (min1 && min2 && operand_equal_p (min1, min2, 0))
- min_equal_p = true;
-
- /* Likewise, if either type has a maximum value, the other
- type must have the same. */
- if (max1 == NULL_TREE && max2 == NULL_TREE)
- max_equal_p = true;
- else if (max1 && max2 && operand_equal_p (max1, max2, 0))
- max_equal_p = true;
-
- if (!min_equal_p || !max_equal_p)
- goto different_types;
-
- goto same_types;
- }
-
- case ENUMERAL_TYPE:
- {
- /* FIXME lto, we cannot check bounds on enumeral types because
- different front ends will produce different values.
- In C, enumeral types are integers, while in C++ each element
- will have its own symbolic value. We should decide how enums
- are to be represented in GIMPLE and have each front end lower
- to that. */
- tree v1, v2;
-
- /* For enumeral types, all the values must be the same. */
- if (TYPE_VALUES (t1) == TYPE_VALUES (t2))
- goto same_types;
-
- 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)
- goto different_types;
-
- if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
- goto different_types;
- }
-
- /* If one enumeration has more values than the other, they
- are not the same. */
- if (v1 || v2)
- goto different_types;
-
- goto same_types;
- }
-
- case RECORD_TYPE:
- case UNION_TYPE:
- case QUAL_UNION_TYPE:
- {
- tree f1, f2;
-
- /* For aggregate types, all the fields must be the same. */
- for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
- f1 && f2;
- f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
- {
- /* Different field kinds are not compatible. */
- if (TREE_CODE (f1) != TREE_CODE (f2))
- goto different_types;
- /* Field decls must have the same name and offset. */
- if (TREE_CODE (f1) == FIELD_DECL
- && (DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
- || !gimple_compare_field_offset (f1, f2)))
- goto different_types;
- /* All entities should have the same name and type. */
- if (DECL_NAME (f1) != DECL_NAME (f2)
- || !gtc_visit (TREE_TYPE (f1), TREE_TYPE (f2),
- state, sccstack, sccstate, sccstate_obstack))
- goto different_types;
- }
-
- /* If one aggregate has more fields than the other, they
- are not the same. */
- if (f1 || f2)
- goto different_types;
-
- goto same_types;
- }
-
- default:
- gcc_unreachable ();
- }
-
- /* Common exit path for types that are not compatible. */
-different_types:
- state->u.same_p = 0;
- goto pop;
-
- /* Common exit path for types that are compatible. */
-same_types:
- gcc_assert (state->u.same_p == 1);
-
-pop:
- if (state->low == state->dfsnum)
- {
- type_pair_t x;
-
- /* Pop off the SCC and set its cache values to the final
- comparison result. */
- do
- {
- struct sccs *cstate;
- x = VEC_pop (type_pair_t, *sccstack);
- cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
- cstate->on_sccstack = false;
- x->same_p[GTC_MERGE] = state->u.same_p;
- }
- while (x != p);
- }
-
- return state->u.same_p;
-}
-
-/* Return true iff T1 and T2 are structurally identical. When
- FOR_MERGING_P is true the an incomplete type and a complete type
- are considered different, otherwise they are considered compatible. */
-
-static bool
-gimple_types_compatible_p (tree t1, tree t2)
-{
- VEC(type_pair_t, heap) *sccstack = NULL;
- struct pointer_map_t *sccstate;
- struct obstack sccstate_obstack;
- type_pair_t p = NULL;
- bool res;
- tree leader1, leader2;
-
- /* Before starting to set up the SCC machinery handle simple cases. */
-
- /* 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 (t2))
- return false;
-
- if (TREE_ADDRESSABLE (t1) != TREE_ADDRESSABLE (t2))
- return false;
-
- /* Void types and nullptr types are always the same. */
- if (TREE_CODE (t1) == VOID_TYPE
- || TREE_CODE (t1) == NULLPTR_TYPE)
- return true;
-
- /* Can't be the same type if they have different alignment or mode. */
- if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
- || TYPE_MODE (t1) != TYPE_MODE (t2))
- return false;
-
- /* Do some simple checks before doing three hashtable queries. */
- if (INTEGRAL_TYPE_P (t1)
- || SCALAR_FLOAT_TYPE_P (t1)
- || FIXED_POINT_TYPE_P (t1)
- || TREE_CODE (t1) == VECTOR_TYPE
- || TREE_CODE (t1) == COMPLEX_TYPE
- || TREE_CODE (t1) == OFFSET_TYPE
- || POINTER_TYPE_P (t1))
- {
- /* Can't be the same type if they have different sign or precision. */
- if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
- || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
- return false;
-
- if (TREE_CODE (t1) == INTEGER_TYPE
- && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
- return false;
-
- /* That's all we need to check for float and fixed-point types. */
- if (SCALAR_FLOAT_TYPE_P (t1)
- || FIXED_POINT_TYPE_P (t1))
- return true;
-
- /* For other types fall through to more complex checks. */
- }
-
- /* If the types have been previously registered and found equal
- they still are. */
- leader1 = gimple_lookup_type_leader (t1);
- leader2 = gimple_lookup_type_leader (t2);
- if (leader1 == t2
- || t1 == leader2
- || (leader1 && leader1 == leader2))
- return true;
-
- /* If the hash values of t1 and t2 are different the types can't
- possibly be the same. This helps keeping the type-pair hashtable
- small, only tracking comparisons for hash collisions. */
- if (gimple_type_hash (t1) != gimple_type_hash (t2))
- return false;
-
- /* If we've visited this type pair before (in the case of aggregates
- with self-referential types), and we made a decision, return it. */
- p = lookup_type_pair (t1, t2);
- if (p->same_p[GTC_MERGE] == 0 || p->same_p[GTC_MERGE] == 1)
- {
- /* We have already decided whether T1 and T2 are the
- same, return the cached result. */
- return p->same_p[GTC_MERGE] == 1;
- }
-
- /* Now set up the SCC machinery for the comparison. */
- gtc_next_dfs_num = 1;
- sccstate = pointer_map_create ();
- gcc_obstack_init (&sccstate_obstack);
- res = gimple_types_compatible_p_1 (t1, t2, p,
- &sccstack, sccstate, &sccstate_obstack);
- VEC_free (type_pair_t, heap, sccstack);
- pointer_map_destroy (sccstate);
- obstack_free (&sccstate_obstack, NULL);
-
- return res;
-}
-
-
-static hashval_t
-iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,
- struct pointer_map_t *, struct obstack *);
-
-/* DFS visit the edge from the callers type with state *STATE to T.
- Update the callers type hash V with the hash for T if it is not part
- of the SCC containing the callers type and return it.
- SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done. */
-
-static hashval_t
-visit (tree t, struct sccs *state, hashval_t v,
- VEC (tree, heap) **sccstack,
- struct pointer_map_t *sccstate,
- struct obstack *sccstate_obstack)
-{
- struct sccs *cstate = NULL;
- struct tree_int_map m;
- void **slot;
-
- /* If there is a hash value recorded for this type then it can't
- possibly be part of our parent SCC. Simply mix in its hash. */
- m.base.from = t;
- if ((slot = htab_find_slot (type_hash_cache, &m, NO_INSERT))
- && *slot)
- return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, v);
-
- if ((slot = pointer_map_contains (sccstate, t)) != NULL)
- cstate = (struct sccs *)*slot;
- if (!cstate)
- {
- hashval_t tem;
- /* Not yet visited. DFS recurse. */
- tem = iterative_hash_gimple_type (t, v,
- sccstack, sccstate, sccstate_obstack);
- if (!cstate)
- cstate = (struct sccs *)* pointer_map_contains (sccstate, t);
- state->low = MIN (state->low, cstate->low);
- /* If the type is no longer on the SCC stack and thus is not part
- of the parents SCC mix in its hash value. Otherwise we will
- ignore the type for hashing purposes and return the unaltered
- hash value. */
- if (!cstate->on_sccstack)
- return tem;
- }
- if (cstate->dfsnum < state->dfsnum
- && cstate->on_sccstack)
- state->low = MIN (cstate->dfsnum, state->low);
-
- /* We are part of our parents SCC, skip this type during hashing
- and return the unaltered hash value. */
- return v;
-}
-
-/* Hash NAME with the previous hash value V and return it. */
-
-static hashval_t
-iterative_hash_name (tree name, hashval_t v)
-{
- if (!name)
- return v;
- v = iterative_hash_hashval_t (TREE_CODE (name), v);
- if (TREE_CODE (name) == TYPE_DECL)
- name = DECL_NAME (name);
- if (!name)
- return v;
- gcc_assert (TREE_CODE (name) == IDENTIFIER_NODE);
- return iterative_hash_object (IDENTIFIER_HASH_VALUE (name), v);
-}
-
-/* A type, hashvalue pair for sorting SCC members. */
-
-struct type_hash_pair {
- tree type;
- hashval_t hash;
-};
-
-/* Compare two type, hashvalue pairs. */
-
-static int
-type_hash_pair_compare (const void *p1_, const void *p2_)
-{
- const struct type_hash_pair *p1 = (const struct type_hash_pair *) p1_;
- const struct type_hash_pair *p2 = (const struct type_hash_pair *) p2_;
- if (p1->hash < p2->hash)
- return -1;
- else if (p1->hash > p2->hash)
- return 1;
- return 0;
-}
-
-/* Returning a hash value for gimple type TYPE combined with VAL.
- SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.
-
- To hash a type we end up hashing in types that are reachable.
- Through pointers we can end up with cycles which messes up the
- required property that we need to compute the same hash value
- for structurally equivalent types. To avoid this we have to
- hash all types in a cycle (the SCC) in a commutative way. The
- easiest way is to not mix in the hashes of the SCC members at
- all. To make this work we have to delay setting the hash
- values of the SCC until it is complete. */
-
-static hashval_t
-iterative_hash_gimple_type (tree type, hashval_t val,
- VEC(tree, heap) **sccstack,
- struct pointer_map_t *sccstate,
- struct obstack *sccstate_obstack)
-{
- hashval_t v;
- void **slot;
- struct sccs *state;
-
- /* Not visited during this DFS walk. */
- gcc_checking_assert (!pointer_map_contains (sccstate, type));
- state = XOBNEW (sccstate_obstack, struct sccs);
- *pointer_map_insert (sccstate, type) = state;
-
- VEC_safe_push (tree, heap, *sccstack, type);
- state->dfsnum = next_dfs_num++;
- state->low = state->dfsnum;
- state->on_sccstack = true;
-
- /* Combine a few common features of types so that types are grouped into
- smaller sets; when searching for existing matching types to merge,
- only existing types having the same features as the new type will be
- checked. */
- v = iterative_hash_name (TYPE_NAME (type), 0);
- if (TYPE_NAME (type)
- && TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
- && DECL_CONTEXT (TYPE_NAME (type))
- && TYPE_P (DECL_CONTEXT (TYPE_NAME (type))))
- v = visit (DECL_CONTEXT (TYPE_NAME (type)), state, v,
- sccstack, sccstate, sccstate_obstack);
- v = iterative_hash_hashval_t (TREE_CODE (type), v);
- v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
- v = iterative_hash_hashval_t (TREE_ADDRESSABLE (type), v);
-
- /* Do not hash the types size as this will cause differences in
- hash values for the complete vs. the incomplete type variant. */
-
- /* Incorporate common features of numerical types. */
- if (INTEGRAL_TYPE_P (type)
- || SCALAR_FLOAT_TYPE_P (type)
- || FIXED_POINT_TYPE_P (type))
- {
- v = iterative_hash_hashval_t (TYPE_PRECISION (type), v);
- v = iterative_hash_hashval_t (TYPE_MODE (type), v);
- v = iterative_hash_hashval_t (TYPE_UNSIGNED (type), v);
- }
-
- /* For pointer and reference types, fold in information about the type
- pointed to. */
- if (POINTER_TYPE_P (type))
- v = visit (TREE_TYPE (type), state, v,
- sccstack, sccstate, sccstate_obstack);
-
- /* For integer types hash the types min/max values and the string flag. */
- if (TREE_CODE (type) == INTEGER_TYPE)
- {
- /* OMP lowering can introduce error_mark_node in place of
- random local decls in types. */
- if (TYPE_MIN_VALUE (type) != error_mark_node)
- v = iterative_hash_expr (TYPE_MIN_VALUE (type), v);
- if (TYPE_MAX_VALUE (type) != error_mark_node)
- v = iterative_hash_expr (TYPE_MAX_VALUE (type), v);
- v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
- }
-
- /* For array types hash the domain and the string flag. */
- if (TREE_CODE (type) == ARRAY_TYPE && TYPE_DOMAIN (type))
- {
- v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
- v = visit (TYPE_DOMAIN (type), state, v,
- sccstack, sccstate, sccstate_obstack);
- }
-
- /* Recurse for aggregates with a single element type. */
- if (TREE_CODE (type) == ARRAY_TYPE
- || TREE_CODE (type) == COMPLEX_TYPE
- || TREE_CODE (type) == VECTOR_TYPE)
- v = visit (TREE_TYPE (type), state, v,
- sccstack, sccstate, sccstate_obstack);
-
- /* Incorporate function return and argument types. */
- if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
- {
- unsigned na;
- tree p;
-
- /* For method types also incorporate their parent class. */
- if (TREE_CODE (type) == METHOD_TYPE)
- v = visit (TYPE_METHOD_BASETYPE (type), state, v,
- sccstack, sccstate, sccstate_obstack);
-
- /* Check result and argument types. */
- v = visit (TREE_TYPE (type), state, v,
- sccstack, sccstate, sccstate_obstack);
- for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
- {
- v = visit (TREE_VALUE (p), state, v,
- sccstack, sccstate, sccstate_obstack);
- na++;
- }
-
- v = iterative_hash_hashval_t (na, v);
- }
-
- if (RECORD_OR_UNION_TYPE_P (type))
- {
- unsigned nf;
- tree f;
-
- for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
- {
- v = iterative_hash_name (DECL_NAME (f), v);
- v = visit (TREE_TYPE (f), state, v,
- sccstack, sccstate, sccstate_obstack);
- nf++;
- }
-
- v = iterative_hash_hashval_t (nf, v);
- }
-
- /* Record hash for us. */
- state->u.hash = v;
-
- /* See if we found an SCC. */
- if (state->low == state->dfsnum)
- {
- tree x;
- struct tree_int_map *m;
-
- /* Pop off the SCC and set its hash values. */
- x = VEC_pop (tree, *sccstack);
- /* Optimize SCC size one. */
- if (x == type)
- {
- state->on_sccstack = false;
- m = ggc_alloc_cleared_tree_int_map ();
- m->base.from = x;
- m->to = v;
- slot = htab_find_slot (type_hash_cache, m, INSERT);
- gcc_assert (!*slot);
- *slot = (void *) m;
- }
- else
- {
- struct sccs *cstate;
- unsigned first, i, size, j;
- struct type_hash_pair *pairs;
- /* Pop off the SCC and build an array of type, hash pairs. */
- first = VEC_length (tree, *sccstack) - 1;
- while (VEC_index (tree, *sccstack, first) != type)
- --first;
- size = VEC_length (tree, *sccstack) - first + 1;
- pairs = XALLOCAVEC (struct type_hash_pair, size);
- i = 0;
- cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
- cstate->on_sccstack = false;
- pairs[i].type = x;
- pairs[i].hash = cstate->u.hash;
- do
- {
- x = VEC_pop (tree, *sccstack);
- cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
- cstate->on_sccstack = false;
- ++i;
- pairs[i].type = x;
- pairs[i].hash = cstate->u.hash;
- }
- while (x != type);
- gcc_assert (i + 1 == size);
- /* Sort the arrays of type, hash pairs so that when we mix in
- all members of the SCC the hash value becomes independent on
- the order we visited the SCC. Disregard hashes equal to
- the hash of the type we mix into because we cannot guarantee
- a stable sort for those across different TUs. */
- qsort (pairs, size, sizeof (struct type_hash_pair),
- type_hash_pair_compare);
- for (i = 0; i < size; ++i)
- {
- hashval_t hash;
- m = ggc_alloc_cleared_tree_int_map ();
- m->base.from = pairs[i].type;
- hash = pairs[i].hash;
- /* Skip same hashes. */
- for (j = i + 1; j < size && pairs[j].hash == pairs[i].hash; ++j)
- ;
- for (; j < size; ++j)
- hash = iterative_hash_hashval_t (pairs[j].hash, hash);
- for (j = 0; pairs[j].hash != pairs[i].hash; ++j)
- hash = iterative_hash_hashval_t (pairs[j].hash, hash);
- m->to = hash;
- if (pairs[i].type == type)
- v = hash;
- slot = htab_find_slot (type_hash_cache, m, INSERT);
- gcc_assert (!*slot);
- *slot = (void *) m;
- }
- }
- }
-
- return iterative_hash_hashval_t (v, val);
-}
-
-
-/* Returns a hash value for P (assumed to be a type). The hash value
- is computed using some distinguishing features of the type. Note
- that we cannot use pointer hashing here as we may be dealing with
- two distinct instances of the same type.
-
- This function should produce the same hash value for two compatible
- types according to gimple_types_compatible_p. */
-
-static hashval_t
-gimple_type_hash (const void *p)
-{
- const_tree t = (const_tree) p;
- VEC(tree, heap) *sccstack = NULL;
- struct pointer_map_t *sccstate;
- struct obstack sccstate_obstack;
- hashval_t val;
- void **slot;
- struct tree_int_map m;
-
- if (type_hash_cache == NULL)
- type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
- tree_int_map_eq, NULL);
-
- m.base.from = CONST_CAST_TREE (t);
- if ((slot = htab_find_slot (type_hash_cache, &m, NO_INSERT))
- && *slot)
- return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, 0);
-
- /* Perform a DFS walk and pre-hash all reachable types. */
- next_dfs_num = 1;
- sccstate = pointer_map_create ();
- gcc_obstack_init (&sccstate_obstack);
- val = iterative_hash_gimple_type (CONST_CAST_TREE (t), 0,
- &sccstack, sccstate, &sccstate_obstack);
- VEC_free (tree, heap, sccstack);
- pointer_map_destroy (sccstate);
- obstack_free (&sccstate_obstack, NULL);
-
- return val;
-}
-
/* Returning a hash value for gimple type TYPE combined with VAL.
The hash value returned is equal for types considered compatible
@@ -4232,84 +3186,7 @@ gimple_canonical_type_hash (const void *
}
-/* Returns nonzero if P1 and P2 are equal. */
-
-static int
-gimple_type_eq (const void *p1, const void *p2)
-{
- const_tree t1 = (const_tree) p1;
- const_tree t2 = (const_tree) p2;
- return gimple_types_compatible_p (CONST_CAST_TREE (t1),
- CONST_CAST_TREE (t2));
-}
-
-
-/* Worker for gimple_register_type.
- Register type T in the global type table gimple_types.
- When REGISTERING_MV is false first recurse for the main variant of T. */
-
-static tree
-gimple_register_type_1 (tree t, bool registering_mv)
-{
- void **slot;
- gimple_type_leader_entry *leader;
-
- /* If we registered this type before return the cached result. */
- leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
- if (leader->type == t)
- return leader->leader;
-
- /* Always register the main variant first. This is important so we
- pick up the non-typedef variants as canonical, otherwise we'll end
- up taking typedef ids for structure tags during comparison.
- It also makes sure that main variants will be merged to main variants.
- As we are operating on a possibly partially fixed up type graph
- do not bother to recurse more than once, otherwise we may end up
- walking in circles.
- If we are registering a main variant it will either remain its
- own main variant or it will be merged to something else in which
- case we do not care for the main variant leader. */
- if (!registering_mv
- && TYPE_MAIN_VARIANT (t) != t)
- gimple_register_type_1 (TYPE_MAIN_VARIANT (t), true);
-
- /* See if we already have an equivalent type registered. */
- slot = htab_find_slot (gimple_types, t, INSERT);
- if (*slot
- && *(tree *)slot != t)
- {
- tree new_type = (tree) *((tree *) slot);
- leader->type = t;
- leader->leader = new_type;
- return new_type;
- }
-
- /* If not, insert it to the cache and the hash. */
- leader->type = t;
- leader->leader = t;
- *slot = (void *) t;
- return t;
-}
-
-/* Register type T in the global type table gimple_types.
- If another type T', compatible with T, already existed in
- gimple_types then return T', otherwise return T. This is used by
- LTO to merge identical types read from different TUs. */
-
-tree
-gimple_register_type (tree t)
-{
- gcc_assert (TYPE_P (t));
- if (!gimple_type_leader)
- gimple_type_leader = ggc_alloc_cleared_vec_gimple_type_leader_entry_s
- (GIMPLE_TYPE_LEADER_SIZE);
-
- if (gimple_types == NULL)
- gimple_types = htab_create_ggc (16381, gimple_type_hash, gimple_type_eq, 0);
-
- return gimple_register_type_1 (t, false);
-}
/* The TYPE_CANONICAL merging machinery. It should closely resemble
the middle-end types_compatible_p function. It needs to avoid
@@ -4583,48 +3460,28 @@ gimple_register_canonical_type (tree t)
/* Show statistics on references to the global type table gimple_types. */
void
-print_gimple_types_stats (void)
+print_gimple_types_stats (const char *pfx)
{
- if (gimple_types)
- fprintf (stderr, "GIMPLE type table: size %ld, %ld elements, "
- "%ld searches, %ld collisions (ratio: %f)\n",
- (long) htab_size (gimple_types),
- (long) htab_elements (gimple_types),
- (long) gimple_types->searches,
- (long) gimple_types->collisions,
- htab_collisions (gimple_types));
- else
- fprintf (stderr, "GIMPLE type table is empty\n");
- if (type_hash_cache)
- fprintf (stderr, "GIMPLE type hash table: size %ld, %ld elements, "
- "%ld searches, %ld collisions (ratio: %f)\n",
- (long) htab_size (type_hash_cache),
- (long) htab_elements (type_hash_cache),
- (long) type_hash_cache->searches,
- (long) type_hash_cache->collisions,
- htab_collisions (type_hash_cache));
- else
- fprintf (stderr, "GIMPLE type hash table is empty\n");
if (gimple_canonical_types)
- fprintf (stderr, "GIMPLE canonical type table: size %ld, %ld elements, "
- "%ld searches, %ld collisions (ratio: %f)\n",
+ fprintf (stderr, "[%s] GIMPLE canonical type table: size %ld, "
+ "%ld elements, %ld searches, %ld collisions (ratio: %f)\n", pfx,
(long) htab_size (gimple_canonical_types),
(long) htab_elements (gimple_canonical_types),
(long) gimple_canonical_types->searches,
(long) gimple_canonical_types->collisions,
htab_collisions (gimple_canonical_types));
else
- fprintf (stderr, "GIMPLE canonical type table is empty\n");
+ fprintf (stderr, "[%s] GIMPLE canonical type table is empty\n", pfx);
if (canonical_type_hash_cache)
- fprintf (stderr, "GIMPLE canonical type hash table: size %ld, %ld elements, "
- "%ld searches, %ld collisions (ratio: %f)\n",
+ fprintf (stderr, "[%s] GIMPLE canonical type hash table: size %ld, "
+ "%ld elements, %ld searches, %ld collisions (ratio: %f)\n", pfx,
(long) htab_size (canonical_type_hash_cache),
(long) htab_elements (canonical_type_hash_cache),
(long) canonical_type_hash_cache->searches,
(long) canonical_type_hash_cache->collisions,
htab_collisions (canonical_type_hash_cache));
else
- fprintf (stderr, "GIMPLE canonical type hash table is empty\n");
+ fprintf (stderr, "[%s] GIMPLE canonical type hash table is empty\n", pfx);
}
/* Free the gimple type hashtables used for LTO type merging. */
@@ -4632,36 +3489,16 @@ print_gimple_types_stats (void)
void
free_gimple_type_tables (void)
{
- /* Last chance to print stats for the tables. */
- if (flag_lto_report)
- print_gimple_types_stats ();
-
- if (gimple_types)
- {
- htab_delete (gimple_types);
- gimple_types = NULL;
- }
if (gimple_canonical_types)
{
htab_delete (gimple_canonical_types);
gimple_canonical_types = NULL;
}
- if (type_hash_cache)
- {
- htab_delete (type_hash_cache);
- type_hash_cache = NULL;
- }
if (canonical_type_hash_cache)
{
htab_delete (canonical_type_hash_cache);
canonical_type_hash_cache = NULL;
}
- if (type_pair_cache)
- {
- free (type_pair_cache);
- type_pair_cache = NULL;
- }
- gimple_type_leader = NULL;
}
===================================================================
@@ -276,6 +276,1139 @@ lto_read_in_decl_state (struct data_in *
return data;
}
+/* Global type table. FIXME, it should be possible to re-use some
+ of the type hashing routines in tree.c (type_hash_canon, type_hash_lookup,
+ etc), but those assume that types were built with the various
+ build_*_type routines which is not the case with the streamer. */
+static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node)))
+ htab_t gimple_types;
+static GTY((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
+ htab_t type_hash_cache;
+
+enum gtc_mode { GTC_MERGE = 0, GTC_DIAG = 1 };
+
+static hashval_t gimple_type_hash (const void *);
+
+/* Structure used to maintain a cache of some type pairs compared by
+ gimple_types_compatible_p when comparing aggregate types. There are
+ three possible values for SAME_P:
+
+ -2: The pair (T1, T2) has just been inserted in the table.
+ 0: T1 and T2 are different types.
+ 1: T1 and T2 are the same type.
+
+ The two elements in the SAME_P array are indexed by the comparison
+ mode gtc_mode. */
+
+struct type_pair_d
+{
+ unsigned int uid1;
+ unsigned int uid2;
+ signed char same_p[2];
+};
+typedef struct type_pair_d *type_pair_t;
+DEF_VEC_P(type_pair_t);
+DEF_VEC_ALLOC_P(type_pair_t,heap);
+
+#define GIMPLE_TYPE_PAIR_SIZE 16381
+struct type_pair_d *type_pair_cache;
+
+
+/* Lookup the pair of types T1 and T2 in *VISITED_P. Insert a new
+ entry if none existed. */
+
+static inline type_pair_t
+lookup_type_pair (tree t1, tree t2)
+{
+ unsigned int index;
+ unsigned int uid1, uid2;
+
+ if (type_pair_cache == NULL)
+ type_pair_cache = XCNEWVEC (struct type_pair_d, GIMPLE_TYPE_PAIR_SIZE);
+
+ if (TYPE_UID (t1) < TYPE_UID (t2))
+ {
+ uid1 = TYPE_UID (t1);
+ uid2 = TYPE_UID (t2);
+ }
+ else
+ {
+ uid1 = TYPE_UID (t2);
+ uid2 = TYPE_UID (t1);
+ }
+ gcc_checking_assert (uid1 != uid2);
+
+ /* iterative_hash_hashval_t imply an function calls.
+ We know that UIDS are in limited range. */
+ index = ((((unsigned HOST_WIDE_INT)uid1 << HOST_BITS_PER_WIDE_INT / 2) + uid2)
+ % GIMPLE_TYPE_PAIR_SIZE);
+ if (type_pair_cache [index].uid1 == uid1
+ && type_pair_cache [index].uid2 == uid2)
+ return &type_pair_cache[index];
+
+ type_pair_cache [index].uid1 = uid1;
+ type_pair_cache [index].uid2 = uid2;
+ type_pair_cache [index].same_p[0] = -2;
+ type_pair_cache [index].same_p[1] = -2;
+
+ return &type_pair_cache[index];
+}
+
+/* Per pointer state for the SCC finding. The on_sccstack flag
+ is not strictly required, it is true when there is no hash value
+ recorded for the type and false otherwise. But querying that
+ is slower. */
+
+struct sccs
+{
+ unsigned int dfsnum;
+ unsigned int low;
+ bool on_sccstack;
+ union {
+ hashval_t hash;
+ signed char same_p;
+ } u;
+};
+
+static unsigned int next_dfs_num;
+static unsigned int gtc_next_dfs_num;
+
+/* GIMPLE type merging cache. A direct-mapped cache based on TYPE_UID. */
+
+typedef struct GTY(()) gimple_type_leader_entry_s {
+ tree type;
+ tree leader;
+} gimple_type_leader_entry;
+
+#define GIMPLE_TYPE_LEADER_SIZE 16381
+static GTY((deletable, length("GIMPLE_TYPE_LEADER_SIZE")))
+ gimple_type_leader_entry *gimple_type_leader;
+
+/* Lookup an existing leader for T and return it or NULL_TREE, if
+ there is none in the cache. */
+
+static inline tree
+gimple_lookup_type_leader (tree t)
+{
+ gimple_type_leader_entry *leader;
+
+ if (!gimple_type_leader)
+ return NULL_TREE;
+
+ leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
+ if (leader->type != t)
+ return NULL_TREE;
+
+ return leader->leader;
+}
+
+
+
+/* Return true if T1 and T2 have the same name. If FOR_COMPLETION_P is
+ true then if any type has no name return false, otherwise return
+ true if both types have no names. */
+
+static bool
+compare_type_names_p (tree t1, tree t2)
+{
+ tree name1 = TYPE_NAME (t1);
+ tree name2 = TYPE_NAME (t2);
+
+ if ((name1 != NULL_TREE) != (name2 != NULL_TREE))
+ return false;
+
+ if (name1 == NULL_TREE)
+ return true;
+
+ /* Either both should be a TYPE_DECL or both an IDENTIFIER_NODE. */
+ if (TREE_CODE (name1) != TREE_CODE (name2))
+ return false;
+
+ if (TREE_CODE (name1) == TYPE_DECL)
+ name1 = DECL_NAME (name1);
+ gcc_checking_assert (!name1 || TREE_CODE (name1) == IDENTIFIER_NODE);
+
+ if (TREE_CODE (name2) == TYPE_DECL)
+ name2 = DECL_NAME (name2);
+ gcc_checking_assert (!name2 || TREE_CODE (name2) == IDENTIFIER_NODE);
+
+ /* Identifiers can be compared with pointer equality rather
+ than a string comparison. */
+ if (name1 == name2)
+ return true;
+
+ return false;
+}
+
+static bool
+gimple_types_compatible_p_1 (tree, tree, type_pair_t,
+ VEC(type_pair_t, heap) **,
+ struct pointer_map_t *, struct obstack *);
+
+/* DFS visit the edge from the callers type pair with state *STATE to
+ the pair T1, T2 while operating in FOR_MERGING_P mode.
+ Update the merging status if it is not part of the SCC containing the
+ callers pair and return it.
+ SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done. */
+
+static bool
+gtc_visit (tree t1, tree t2,
+ struct sccs *state,
+ VEC(type_pair_t, heap) **sccstack,
+ struct pointer_map_t *sccstate,
+ struct obstack *sccstate_obstack)
+{
+ struct sccs *cstate = NULL;
+ type_pair_t p;
+ void **slot;
+ tree leader1, leader2;
+
+ /* 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 (t2))
+ return false;
+
+ if (TREE_ADDRESSABLE (t1) != TREE_ADDRESSABLE (t2))
+ return false;
+
+ /* Void types and nullptr types are always the same. */
+ if (TREE_CODE (t1) == VOID_TYPE
+ || TREE_CODE (t1) == NULLPTR_TYPE)
+ return true;
+
+ /* Can't be the same type if they have different alignment or mode. */
+ if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
+ || TYPE_MODE (t1) != TYPE_MODE (t2))
+ return false;
+
+ /* Do some simple checks before doing three hashtable queries. */
+ if (INTEGRAL_TYPE_P (t1)
+ || SCALAR_FLOAT_TYPE_P (t1)
+ || FIXED_POINT_TYPE_P (t1)
+ || TREE_CODE (t1) == VECTOR_TYPE
+ || TREE_CODE (t1) == COMPLEX_TYPE
+ || TREE_CODE (t1) == OFFSET_TYPE
+ || POINTER_TYPE_P (t1))
+ {
+ /* Can't be the same type if they have different sign or precision. */
+ if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
+ || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
+ return false;
+
+ if (TREE_CODE (t1) == INTEGER_TYPE
+ && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
+ return false;
+
+ /* That's all we need to check for float and fixed-point types. */
+ if (SCALAR_FLOAT_TYPE_P (t1)
+ || FIXED_POINT_TYPE_P (t1))
+ return true;
+
+ /* For other types fall through to more complex checks. */
+ }
+
+ /* If the types have been previously registered and found equal
+ they still are. */
+ leader1 = gimple_lookup_type_leader (t1);
+ leader2 = gimple_lookup_type_leader (t2);
+ if (leader1 == t2
+ || t1 == leader2
+ || (leader1 && leader1 == leader2))
+ return true;
+
+ /* If the hash values of t1 and t2 are different the types can't
+ possibly be the same. This helps keeping the type-pair hashtable
+ small, only tracking comparisons for hash collisions. */
+ if (gimple_type_hash (t1) != gimple_type_hash (t2))
+ return false;
+
+ /* Allocate a new cache entry for this comparison. */
+ p = lookup_type_pair (t1, t2);
+ if (p->same_p[GTC_MERGE] == 0 || p->same_p[GTC_MERGE] == 1)
+ {
+ /* We have already decided whether T1 and T2 are the
+ same, return the cached result. */
+ return p->same_p[GTC_MERGE] == 1;
+ }
+
+ if ((slot = pointer_map_contains (sccstate, p)) != NULL)
+ cstate = (struct sccs *)*slot;
+ /* Not yet visited. DFS recurse. */
+ if (!cstate)
+ {
+ gimple_types_compatible_p_1 (t1, t2, p,
+ sccstack, sccstate, sccstate_obstack);
+ cstate = (struct sccs *)* pointer_map_contains (sccstate, p);
+ state->low = MIN (state->low, cstate->low);
+ }
+ /* If the type is still on the SCC stack adjust the parents low. */
+ if (cstate->dfsnum < state->dfsnum
+ && cstate->on_sccstack)
+ state->low = MIN (cstate->dfsnum, state->low);
+
+ /* Return the current lattice value. We start with an equality
+ assumption so types part of a SCC will be optimistically
+ treated equal unless proven otherwise. */
+ return cstate->u.same_p;
+}
+
+/* Worker for gimple_types_compatible.
+ SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done. */
+
+static bool
+gimple_types_compatible_p_1 (tree t1, tree t2, type_pair_t p,
+ VEC(type_pair_t, heap) **sccstack,
+ struct pointer_map_t *sccstate,
+ struct obstack *sccstate_obstack)
+{
+ struct sccs *state;
+
+ gcc_assert (p->same_p[GTC_MERGE] == -2);
+
+ state = XOBNEW (sccstate_obstack, struct sccs);
+ *pointer_map_insert (sccstate, p) = state;
+
+ VEC_safe_push (type_pair_t, heap, *sccstack, p);
+ state->dfsnum = gtc_next_dfs_num++;
+ state->low = state->dfsnum;
+ state->on_sccstack = true;
+ /* Start with an equality assumption. As we DFS recurse into child
+ SCCs this assumption may get revisited. */
+ state->u.same_p = 1;
+
+ /* The struct tags shall compare equal. */
+ if (!compare_type_names_p (t1, t2))
+ goto different_types;
+
+ /* We may not merge typedef types to the same type in different
+ contexts. */
+ if (TYPE_NAME (t1)
+ && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
+ && DECL_CONTEXT (TYPE_NAME (t1))
+ && TYPE_P (DECL_CONTEXT (TYPE_NAME (t1))))
+ {
+ if (!gtc_visit (DECL_CONTEXT (TYPE_NAME (t1)),
+ DECL_CONTEXT (TYPE_NAME (t2)),
+ state, sccstack, sccstate, sccstate_obstack))
+ goto different_types;
+ }
+
+ /* If their attributes are not the same they can't be the same type. */
+ if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
+ goto different_types;
+
+ /* Do type-specific comparisons. */
+ switch (TREE_CODE (t1))
+ {
+ case VECTOR_TYPE:
+ case COMPLEX_TYPE:
+ if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
+ state, sccstack, sccstate, sccstate_obstack))
+ goto different_types;
+ goto same_types;
+
+ case ARRAY_TYPE:
+ /* Array types are the same if the element types are the same and
+ the number of elements are the same. */
+ if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
+ state, sccstack, sccstate, sccstate_obstack)
+ || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
+ || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
+ goto different_types;
+ 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 == NULL_TREE && i2 == NULL_TREE)
+ goto same_types;
+ else if (i1 == NULL_TREE || i2 == NULL_TREE)
+ goto different_types;
+ 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);
+
+ /* The minimum/maximum values have to be the same. */
+ if ((min1 == min2
+ || (min1 && min2
+ && ((TREE_CODE (min1) == PLACEHOLDER_EXPR
+ && TREE_CODE (min2) == PLACEHOLDER_EXPR)
+ || operand_equal_p (min1, min2, 0))))
+ && (max1 == max2
+ || (max1 && max2
+ && ((TREE_CODE (max1) == PLACEHOLDER_EXPR
+ && TREE_CODE (max2) == PLACEHOLDER_EXPR)
+ || operand_equal_p (max1, max2, 0)))))
+ goto same_types;
+ else
+ goto different_types;
+ }
+ }
+
+ case METHOD_TYPE:
+ /* Method types should belong to the same class. */
+ if (!gtc_visit (TYPE_METHOD_BASETYPE (t1), TYPE_METHOD_BASETYPE (t2),
+ state, sccstack, sccstate, sccstate_obstack))
+ goto different_types;
+
+ /* Fallthru */
+
+ case FUNCTION_TYPE:
+ /* Function types are the same if the return type and arguments types
+ are the same. */
+ if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
+ state, sccstack, sccstate, sccstate_obstack))
+ goto different_types;
+
+ if (!comp_type_attributes (t1, t2))
+ goto different_types;
+
+ if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
+ goto same_types;
+ else
+ {
+ tree parms1, parms2;
+
+ for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
+ parms1 && parms2;
+ parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
+ {
+ if (!gtc_visit (TREE_VALUE (parms1), TREE_VALUE (parms2),
+ state, sccstack, sccstate, sccstate_obstack))
+ goto different_types;
+ }
+
+ if (parms1 || parms2)
+ goto different_types;
+
+ goto same_types;
+ }
+
+ case OFFSET_TYPE:
+ {
+ if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
+ state, sccstack, sccstate, sccstate_obstack)
+ || !gtc_visit (TYPE_OFFSET_BASETYPE (t1),
+ TYPE_OFFSET_BASETYPE (t2),
+ state, sccstack, sccstate, sccstate_obstack))
+ goto different_types;
+
+ goto same_types;
+ }
+
+ case POINTER_TYPE:
+ case REFERENCE_TYPE:
+ {
+ /* 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))
+ goto different_types;
+
+ /* Otherwise, pointer and reference types are the same if the
+ pointed-to types are the same. */
+ if (gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2),
+ state, sccstack, sccstate, sccstate_obstack))
+ goto same_types;
+
+ goto different_types;
+ }
+
+ case INTEGER_TYPE:
+ case BOOLEAN_TYPE:
+ {
+ tree min1 = TYPE_MIN_VALUE (t1);
+ tree max1 = TYPE_MAX_VALUE (t1);
+ tree min2 = TYPE_MIN_VALUE (t2);
+ tree max2 = TYPE_MAX_VALUE (t2);
+ bool min_equal_p = false;
+ bool max_equal_p = false;
+
+ /* If either type has a minimum value, the other type must
+ have the same. */
+ if (min1 == NULL_TREE && min2 == NULL_TREE)
+ min_equal_p = true;
+ else if (min1 && min2 && operand_equal_p (min1, min2, 0))
+ min_equal_p = true;
+
+ /* Likewise, if either type has a maximum value, the other
+ type must have the same. */
+ if (max1 == NULL_TREE && max2 == NULL_TREE)
+ max_equal_p = true;
+ else if (max1 && max2 && operand_equal_p (max1, max2, 0))
+ max_equal_p = true;
+
+ if (!min_equal_p || !max_equal_p)
+ goto different_types;
+
+ goto same_types;
+ }
+
+ case ENUMERAL_TYPE:
+ {
+ /* FIXME lto, we cannot check bounds on enumeral types because
+ different front ends will produce different values.
+ In C, enumeral types are integers, while in C++ each element
+ will have its own symbolic value. We should decide how enums
+ are to be represented in GIMPLE and have each front end lower
+ to that. */
+ tree v1, v2;
+
+ /* For enumeral types, all the values must be the same. */
+ if (TYPE_VALUES (t1) == TYPE_VALUES (t2))
+ goto same_types;
+
+ 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)
+ goto different_types;
+
+ if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
+ goto different_types;
+ }
+
+ /* If one enumeration has more values than the other, they
+ are not the same. */
+ if (v1 || v2)
+ goto different_types;
+
+ goto same_types;
+ }
+
+ case RECORD_TYPE:
+ case UNION_TYPE:
+ case QUAL_UNION_TYPE:
+ {
+ tree f1, f2;
+
+ /* For aggregate types, all the fields must be the same. */
+ for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
+ f1 && f2;
+ f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
+ {
+ /* Different field kinds are not compatible. */
+ if (TREE_CODE (f1) != TREE_CODE (f2))
+ goto different_types;
+ /* Field decls must have the same name and offset. */
+ if (TREE_CODE (f1) == FIELD_DECL
+ && (DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
+ || !gimple_compare_field_offset (f1, f2)))
+ goto different_types;
+ /* All entities should have the same name and type. */
+ if (DECL_NAME (f1) != DECL_NAME (f2)
+ || !gtc_visit (TREE_TYPE (f1), TREE_TYPE (f2),
+ state, sccstack, sccstate, sccstate_obstack))
+ goto different_types;
+ }
+
+ /* If one aggregate has more fields than the other, they
+ are not the same. */
+ if (f1 || f2)
+ goto different_types;
+
+ goto same_types;
+ }
+
+ default:
+ gcc_unreachable ();
+ }
+
+ /* Common exit path for types that are not compatible. */
+different_types:
+ state->u.same_p = 0;
+ goto pop;
+
+ /* Common exit path for types that are compatible. */
+same_types:
+ gcc_assert (state->u.same_p == 1);
+
+pop:
+ if (state->low == state->dfsnum)
+ {
+ type_pair_t x;
+
+ /* Pop off the SCC and set its cache values to the final
+ comparison result. */
+ do
+ {
+ struct sccs *cstate;
+ x = VEC_pop (type_pair_t, *sccstack);
+ cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
+ cstate->on_sccstack = false;
+ x->same_p[GTC_MERGE] = state->u.same_p;
+ }
+ while (x != p);
+ }
+
+ return state->u.same_p;
+}
+
+/* Return true iff T1 and T2 are structurally identical. When
+ FOR_MERGING_P is true the an incomplete type and a complete type
+ are considered different, otherwise they are considered compatible. */
+
+static bool
+gimple_types_compatible_p (tree t1, tree t2)
+{
+ VEC(type_pair_t, heap) *sccstack = NULL;
+ struct pointer_map_t *sccstate;
+ struct obstack sccstate_obstack;
+ type_pair_t p = NULL;
+ bool res;
+ tree leader1, leader2;
+
+ /* Before starting to set up the SCC machinery handle simple cases. */
+
+ /* 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 (t2))
+ return false;
+
+ if (TREE_ADDRESSABLE (t1) != TREE_ADDRESSABLE (t2))
+ return false;
+
+ /* Void types and nullptr types are always the same. */
+ if (TREE_CODE (t1) == VOID_TYPE
+ || TREE_CODE (t1) == NULLPTR_TYPE)
+ return true;
+
+ /* Can't be the same type if they have different alignment or mode. */
+ if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
+ || TYPE_MODE (t1) != TYPE_MODE (t2))
+ return false;
+
+ /* Do some simple checks before doing three hashtable queries. */
+ if (INTEGRAL_TYPE_P (t1)
+ || SCALAR_FLOAT_TYPE_P (t1)
+ || FIXED_POINT_TYPE_P (t1)
+ || TREE_CODE (t1) == VECTOR_TYPE
+ || TREE_CODE (t1) == COMPLEX_TYPE
+ || TREE_CODE (t1) == OFFSET_TYPE
+ || POINTER_TYPE_P (t1))
+ {
+ /* Can't be the same type if they have different sign or precision. */
+ if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
+ || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
+ return false;
+
+ if (TREE_CODE (t1) == INTEGER_TYPE
+ && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
+ return false;
+
+ /* That's all we need to check for float and fixed-point types. */
+ if (SCALAR_FLOAT_TYPE_P (t1)
+ || FIXED_POINT_TYPE_P (t1))
+ return true;
+
+ /* For other types fall through to more complex checks. */
+ }
+
+ /* If the types have been previously registered and found equal
+ they still are. */
+ leader1 = gimple_lookup_type_leader (t1);
+ leader2 = gimple_lookup_type_leader (t2);
+ if (leader1 == t2
+ || t1 == leader2
+ || (leader1 && leader1 == leader2))
+ return true;
+
+ /* If the hash values of t1 and t2 are different the types can't
+ possibly be the same. This helps keeping the type-pair hashtable
+ small, only tracking comparisons for hash collisions. */
+ if (gimple_type_hash (t1) != gimple_type_hash (t2))
+ return false;
+
+ /* If we've visited this type pair before (in the case of aggregates
+ with self-referential types), and we made a decision, return it. */
+ p = lookup_type_pair (t1, t2);
+ if (p->same_p[GTC_MERGE] == 0 || p->same_p[GTC_MERGE] == 1)
+ {
+ /* We have already decided whether T1 and T2 are the
+ same, return the cached result. */
+ return p->same_p[GTC_MERGE] == 1;
+ }
+
+ /* Now set up the SCC machinery for the comparison. */
+ gtc_next_dfs_num = 1;
+ sccstate = pointer_map_create ();
+ gcc_obstack_init (&sccstate_obstack);
+ res = gimple_types_compatible_p_1 (t1, t2, p,
+ &sccstack, sccstate, &sccstate_obstack);
+ VEC_free (type_pair_t, heap, sccstack);
+ pointer_map_destroy (sccstate);
+ obstack_free (&sccstate_obstack, NULL);
+
+ return res;
+}
+
+static hashval_t
+iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,
+ struct pointer_map_t *, struct obstack *);
+
+/* DFS visit the edge from the callers type with state *STATE to T.
+ Update the callers type hash V with the hash for T if it is not part
+ of the SCC containing the callers type and return it.
+ SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done. */
+
+static hashval_t
+visit (tree t, struct sccs *state, hashval_t v,
+ VEC (tree, heap) **sccstack,
+ struct pointer_map_t *sccstate,
+ struct obstack *sccstate_obstack)
+{
+ struct sccs *cstate = NULL;
+ struct tree_int_map m;
+ void **slot;
+
+ /* If there is a hash value recorded for this type then it can't
+ possibly be part of our parent SCC. Simply mix in its hash. */
+ m.base.from = t;
+ if ((slot = htab_find_slot (type_hash_cache, &m, NO_INSERT))
+ && *slot)
+ return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, v);
+
+ if ((slot = pointer_map_contains (sccstate, t)) != NULL)
+ cstate = (struct sccs *)*slot;
+ if (!cstate)
+ {
+ hashval_t tem;
+ /* Not yet visited. DFS recurse. */
+ tem = iterative_hash_gimple_type (t, v,
+ sccstack, sccstate, sccstate_obstack);
+ if (!cstate)
+ cstate = (struct sccs *)* pointer_map_contains (sccstate, t);
+ state->low = MIN (state->low, cstate->low);
+ /* If the type is no longer on the SCC stack and thus is not part
+ of the parents SCC mix in its hash value. Otherwise we will
+ ignore the type for hashing purposes and return the unaltered
+ hash value. */
+ if (!cstate->on_sccstack)
+ return tem;
+ }
+ if (cstate->dfsnum < state->dfsnum
+ && cstate->on_sccstack)
+ state->low = MIN (cstate->dfsnum, state->low);
+
+ /* We are part of our parents SCC, skip this type during hashing
+ and return the unaltered hash value. */
+ return v;
+}
+
+
+
+/* Hash NAME with the previous hash value V and return it. */
+
+static hashval_t
+iterative_hash_name (tree name, hashval_t v)
+{
+ if (!name)
+ return v;
+ v = iterative_hash_hashval_t (TREE_CODE (name), v);
+ if (TREE_CODE (name) == TYPE_DECL)
+ name = DECL_NAME (name);
+ if (!name)
+ return v;
+ gcc_assert (TREE_CODE (name) == IDENTIFIER_NODE);
+ return iterative_hash_object (IDENTIFIER_HASH_VALUE (name), v);
+}
+
+/* A type, hashvalue pair for sorting SCC members. */
+
+struct type_hash_pair {
+ tree type;
+ hashval_t hash;
+};
+
+/* Compare two type, hashvalue pairs. */
+
+static int
+type_hash_pair_compare (const void *p1_, const void *p2_)
+{
+ const struct type_hash_pair *p1 = (const struct type_hash_pair *) p1_;
+ const struct type_hash_pair *p2 = (const struct type_hash_pair *) p2_;
+ if (p1->hash < p2->hash)
+ return -1;
+ else if (p1->hash > p2->hash)
+ return 1;
+ return 0;
+}
+
+/* Returning a hash value for gimple type TYPE combined with VAL.
+ SCCSTACK, SCCSTATE and SCCSTATE_OBSTACK are state for the DFS walk done.
+
+ To hash a type we end up hashing in types that are reachable.
+ Through pointers we can end up with cycles which messes up the
+ required property that we need to compute the same hash value
+ for structurally equivalent types. To avoid this we have to
+ hash all types in a cycle (the SCC) in a commutative way. The
+ easiest way is to not mix in the hashes of the SCC members at
+ all. To make this work we have to delay setting the hash
+ values of the SCC until it is complete. */
+
+static hashval_t
+iterative_hash_gimple_type (tree type, hashval_t val,
+ VEC(tree, heap) **sccstack,
+ struct pointer_map_t *sccstate,
+ struct obstack *sccstate_obstack)
+{
+ hashval_t v;
+ void **slot;
+ struct sccs *state;
+
+ /* Not visited during this DFS walk. */
+ gcc_checking_assert (!pointer_map_contains (sccstate, type));
+ state = XOBNEW (sccstate_obstack, struct sccs);
+ *pointer_map_insert (sccstate, type) = state;
+
+ VEC_safe_push (tree, heap, *sccstack, type);
+ state->dfsnum = next_dfs_num++;
+ state->low = state->dfsnum;
+ state->on_sccstack = true;
+
+ /* Combine a few common features of types so that types are grouped into
+ smaller sets; when searching for existing matching types to merge,
+ only existing types having the same features as the new type will be
+ checked. */
+ v = iterative_hash_name (TYPE_NAME (type), 0);
+ if (TYPE_NAME (type)
+ && TREE_CODE (TYPE_NAME (type)) == TYPE_DECL
+ && DECL_CONTEXT (TYPE_NAME (type))
+ && TYPE_P (DECL_CONTEXT (TYPE_NAME (type))))
+ v = visit (DECL_CONTEXT (TYPE_NAME (type)), state, v,
+ sccstack, sccstate, sccstate_obstack);
+ v = iterative_hash_hashval_t (TREE_CODE (type), v);
+ v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
+ v = iterative_hash_hashval_t (TREE_ADDRESSABLE (type), v);
+
+ /* Do not hash the types size as this will cause differences in
+ hash values for the complete vs. the incomplete type variant. */
+
+ /* Incorporate common features of numerical types. */
+ if (INTEGRAL_TYPE_P (type)
+ || SCALAR_FLOAT_TYPE_P (type)
+ || FIXED_POINT_TYPE_P (type))
+ {
+ v = iterative_hash_hashval_t (TYPE_PRECISION (type), v);
+ v = iterative_hash_hashval_t (TYPE_MODE (type), v);
+ v = iterative_hash_hashval_t (TYPE_UNSIGNED (type), v);
+ }
+
+ /* For pointer and reference types, fold in information about the type
+ pointed to. */
+ if (POINTER_TYPE_P (type))
+ v = visit (TREE_TYPE (type), state, v,
+ sccstack, sccstate, sccstate_obstack);
+
+ /* For integer types hash the types min/max values and the string flag. */
+ if (TREE_CODE (type) == INTEGER_TYPE)
+ {
+ /* OMP lowering can introduce error_mark_node in place of
+ random local decls in types. */
+ if (TYPE_MIN_VALUE (type) != error_mark_node)
+ v = iterative_hash_expr (TYPE_MIN_VALUE (type), v);
+ if (TYPE_MAX_VALUE (type) != error_mark_node)
+ v = iterative_hash_expr (TYPE_MAX_VALUE (type), v);
+ v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
+ }
+
+ /* For array types hash the domain and the string flag. */
+ if (TREE_CODE (type) == ARRAY_TYPE && TYPE_DOMAIN (type))
+ {
+ v = iterative_hash_hashval_t (TYPE_STRING_FLAG (type), v);
+ v = visit (TYPE_DOMAIN (type), state, v,
+ sccstack, sccstate, sccstate_obstack);
+ }
+
+ /* Recurse for aggregates with a single element type. */
+ if (TREE_CODE (type) == ARRAY_TYPE
+ || TREE_CODE (type) == COMPLEX_TYPE
+ || TREE_CODE (type) == VECTOR_TYPE)
+ v = visit (TREE_TYPE (type), state, v,
+ sccstack, sccstate, sccstate_obstack);
+
+ /* Incorporate function return and argument types. */
+ if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
+ {
+ unsigned na;
+ tree p;
+
+ /* For method types also incorporate their parent class. */
+ if (TREE_CODE (type) == METHOD_TYPE)
+ v = visit (TYPE_METHOD_BASETYPE (type), state, v,
+ sccstack, sccstate, sccstate_obstack);
+
+ /* Check result and argument types. */
+ v = visit (TREE_TYPE (type), state, v,
+ sccstack, sccstate, sccstate_obstack);
+ for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
+ {
+ v = visit (TREE_VALUE (p), state, v,
+ sccstack, sccstate, sccstate_obstack);
+ na++;
+ }
+
+ v = iterative_hash_hashval_t (na, v);
+ }
+
+ if (RECORD_OR_UNION_TYPE_P (type))
+ {
+ unsigned nf;
+ tree f;
+
+ for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
+ {
+ v = iterative_hash_name (DECL_NAME (f), v);
+ v = visit (TREE_TYPE (f), state, v,
+ sccstack, sccstate, sccstate_obstack);
+ nf++;
+ }
+
+ v = iterative_hash_hashval_t (nf, v);
+ }
+
+ /* Record hash for us. */
+ state->u.hash = v;
+
+ /* See if we found an SCC. */
+ if (state->low == state->dfsnum)
+ {
+ tree x;
+ struct tree_int_map *m;
+
+ /* Pop off the SCC and set its hash values. */
+ x = VEC_pop (tree, *sccstack);
+ /* Optimize SCC size one. */
+ if (x == type)
+ {
+ state->on_sccstack = false;
+ m = ggc_alloc_cleared_tree_int_map ();
+ m->base.from = x;
+ m->to = v;
+ slot = htab_find_slot (type_hash_cache, m, INSERT);
+ gcc_assert (!*slot);
+ *slot = (void *) m;
+ }
+ else
+ {
+ struct sccs *cstate;
+ unsigned first, i, size, j;
+ struct type_hash_pair *pairs;
+ /* Pop off the SCC and build an array of type, hash pairs. */
+ first = VEC_length (tree, *sccstack) - 1;
+ while (VEC_index (tree, *sccstack, first) != type)
+ --first;
+ size = VEC_length (tree, *sccstack) - first + 1;
+ pairs = XALLOCAVEC (struct type_hash_pair, size);
+ i = 0;
+ cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
+ cstate->on_sccstack = false;
+ pairs[i].type = x;
+ pairs[i].hash = cstate->u.hash;
+ do
+ {
+ x = VEC_pop (tree, *sccstack);
+ cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
+ cstate->on_sccstack = false;
+ ++i;
+ pairs[i].type = x;
+ pairs[i].hash = cstate->u.hash;
+ }
+ while (x != type);
+ gcc_assert (i + 1 == size);
+ /* Sort the arrays of type, hash pairs so that when we mix in
+ all members of the SCC the hash value becomes independent on
+ the order we visited the SCC. Disregard hashes equal to
+ the hash of the type we mix into because we cannot guarantee
+ a stable sort for those across different TUs. */
+ qsort (pairs, size, sizeof (struct type_hash_pair),
+ type_hash_pair_compare);
+ for (i = 0; i < size; ++i)
+ {
+ hashval_t hash;
+ m = ggc_alloc_cleared_tree_int_map ();
+ m->base.from = pairs[i].type;
+ hash = pairs[i].hash;
+ /* Skip same hashes. */
+ for (j = i + 1; j < size && pairs[j].hash == pairs[i].hash; ++j)
+ ;
+ for (; j < size; ++j)
+ hash = iterative_hash_hashval_t (pairs[j].hash, hash);
+ for (j = 0; pairs[j].hash != pairs[i].hash; ++j)
+ hash = iterative_hash_hashval_t (pairs[j].hash, hash);
+ m->to = hash;
+ if (pairs[i].type == type)
+ v = hash;
+ slot = htab_find_slot (type_hash_cache, m, INSERT);
+ gcc_assert (!*slot);
+ *slot = (void *) m;
+ }
+ }
+ }
+
+ return iterative_hash_hashval_t (v, val);
+}
+
+/* Returns a hash value for P (assumed to be a type). The hash value
+ is computed using some distinguishing features of the type. Note
+ that we cannot use pointer hashing here as we may be dealing with
+ two distinct instances of the same type.
+
+ This function should produce the same hash value for two compatible
+ types according to gimple_types_compatible_p. */
+
+static hashval_t
+gimple_type_hash (const void *p)
+{
+ const_tree t = (const_tree) p;
+ VEC(tree, heap) *sccstack = NULL;
+ struct pointer_map_t *sccstate;
+ struct obstack sccstate_obstack;
+ hashval_t val;
+ void **slot;
+ struct tree_int_map m;
+
+ if (type_hash_cache == NULL)
+ type_hash_cache = htab_create_ggc (512, tree_int_map_hash,
+ tree_int_map_eq, NULL);
+
+ m.base.from = CONST_CAST_TREE (t);
+ if ((slot = htab_find_slot (type_hash_cache, &m, NO_INSERT))
+ && *slot)
+ return iterative_hash_hashval_t (((struct tree_int_map *) *slot)->to, 0);
+
+ /* Perform a DFS walk and pre-hash all reachable types. */
+ next_dfs_num = 1;
+ sccstate = pointer_map_create ();
+ gcc_obstack_init (&sccstate_obstack);
+ val = iterative_hash_gimple_type (CONST_CAST_TREE (t), 0,
+ &sccstack, sccstate, &sccstate_obstack);
+ VEC_free (tree, heap, sccstack);
+ pointer_map_destroy (sccstate);
+ obstack_free (&sccstate_obstack, NULL);
+
+ return val;
+}
+/* Returns nonzero if P1 and P2 are equal. */
+
+static int
+gimple_type_eq (const void *p1, const void *p2)
+{
+ const_tree t1 = (const_tree) p1;
+ const_tree t2 = (const_tree) p2;
+ return gimple_types_compatible_p (CONST_CAST_TREE (t1),
+ CONST_CAST_TREE (t2));
+}
+
+
+/* Worker for gimple_register_type.
+ Register type T in the global type table gimple_types.
+ When REGISTERING_MV is false first recurse for the main variant of T. */
+
+static tree
+gimple_register_type_1 (tree t, bool registering_mv)
+{
+ void **slot;
+ gimple_type_leader_entry *leader;
+
+ /* If we registered this type before return the cached result. */
+ leader = &gimple_type_leader[TYPE_UID (t) % GIMPLE_TYPE_LEADER_SIZE];
+ if (leader->type == t)
+ return leader->leader;
+
+ /* Always register the main variant first. This is important so we
+ pick up the non-typedef variants as canonical, otherwise we'll end
+ up taking typedef ids for structure tags during comparison.
+ It also makes sure that main variants will be merged to main variants.
+ As we are operating on a possibly partially fixed up type graph
+ do not bother to recurse more than once, otherwise we may end up
+ walking in circles.
+ If we are registering a main variant it will either remain its
+ own main variant or it will be merged to something else in which
+ case we do not care for the main variant leader. */
+ if (!registering_mv
+ && TYPE_MAIN_VARIANT (t) != t)
+ gimple_register_type_1 (TYPE_MAIN_VARIANT (t), true);
+
+ /* See if we already have an equivalent type registered. */
+ slot = htab_find_slot (gimple_types, t, INSERT);
+ if (*slot
+ && *(tree *)slot != t)
+ {
+ tree new_type = (tree) *((tree *) slot);
+ leader->type = t;
+ leader->leader = new_type;
+ return new_type;
+ }
+
+ /* If not, insert it to the cache and the hash. */
+ leader->type = t;
+ leader->leader = t;
+ *slot = (void *) t;
+ return t;
+}
+
+/* Register type T in the global type table gimple_types.
+ If another type T', compatible with T, already existed in
+ gimple_types then return T', otherwise return T. This is used by
+ LTO to merge identical types read from different TUs. */
+
+static tree
+gimple_register_type (tree t)
+{
+ gcc_assert (TYPE_P (t));
+
+ if (!gimple_type_leader)
+ gimple_type_leader = ggc_alloc_cleared_vec_gimple_type_leader_entry_s
+ (GIMPLE_TYPE_LEADER_SIZE);
+
+ if (gimple_types == NULL)
+ gimple_types = htab_create_ggc (16381, gimple_type_hash, gimple_type_eq, 0);
+
+ return gimple_register_type_1 (t, false);
+}
+
+#define GIMPLE_REGISTER_TYPE(tt) \
+ (TREE_VISITED (tt) ? gimple_register_type (tt) : tt)
+
+
+
/* A hashtable of trees that potentially refer to variables or functions
that must be replaced with their prevailing variant. */
static GTY((if_marked ("ggc_marked_p"), param_is (union tree_node))) htab_t
@@ -289,9 +1422,6 @@ remember_with_vars (tree t)
*(tree *) htab_find_slot (tree_with_vars, t, INSERT) = t;
}
-#define GIMPLE_REGISTER_TYPE(tt) \
- (TREE_VISITED (tt) ? gimple_register_type (tt) : tt)
-
#define LTO_FIXUP_TREE(tt) \
do \
{ \
@@ -1835,6 +2965,22 @@ read_cgraph_and_symbols (unsigned nfiles
lto_fixup_decls (all_file_decl_data);
htab_delete (tree_with_vars);
tree_with_vars = NULL;
+ if (gimple_types)
+ {
+ htab_delete (gimple_types);
+ gimple_types = NULL;
+ }
+ if (type_hash_cache)
+ {
+ htab_delete (type_hash_cache);
+ type_hash_cache = NULL;
+ }
+ if (type_pair_cache)
+ {
+ free (type_pair_cache);
+ type_pair_cache = NULL;
+ }
+ gimple_type_leader = NULL;
free_gimple_type_tables ();
ggc_collect ();
@@ -1936,6 +3082,38 @@ materialize_cgraph (void)
}
+/* Show various memory usage statistics related to LTO. */
+static void
+print_lto_report_1 (void)
+{
+ const char *pfx = (flag_lto) ? "LTO" : (flag_wpa) ? "WPA" : "LTRANS";
+ fprintf (stderr, "%s statistics\n", pfx);
+
+ if (gimple_types)
+ fprintf (stderr, "[%s] GIMPLE type table: size %ld, %ld elements, "
+ "%ld searches, %ld collisions (ratio: %f)\n", pfx,
+ (long) htab_size (gimple_types),
+ (long) htab_elements (gimple_types),
+ (long) gimple_types->searches,
+ (long) gimple_types->collisions,
+ htab_collisions (gimple_types));
+ else
+ fprintf (stderr, "[%s] GIMPLE type table is empty\n", pfx);
+ if (type_hash_cache)
+ fprintf (stderr, "[%s] GIMPLE type hash table: size %ld, %ld elements, "
+ "%ld searches, %ld collisions (ratio: %f)\n", pfx,
+ (long) htab_size (type_hash_cache),
+ (long) htab_elements (type_hash_cache),
+ (long) type_hash_cache->searches,
+ (long) type_hash_cache->collisions,
+ htab_collisions (type_hash_cache));
+ else
+ fprintf (stderr, "[%s] GIMPLE type hash table is empty\n", pfx);
+
+ print_gimple_types_stats (pfx);
+ print_lto_report (pfx);
+}
+
/* Perform whole program analysis (WPA) on the callgraph and write out the
optimization plan. */
@@ -2010,7 +3188,7 @@ do_whole_program_analysis (void)
/* Show the LTO report before launching LTRANS. */
if (flag_lto_report)
- print_lto_report ();
+ print_lto_report_1 ();
if (mem_report_wpa)
dump_memory_report (true);
}
@@ -2136,7 +3314,7 @@ lto_main (void)
launched directly by the driver we would not need to do
this. */
if (flag_lto_report)
- print_lto_report ();
+ print_lto_report_1 ();
}
}