From patchwork Wed Jul 21 16:15:44 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 59455 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id B8189B70AF for ; Thu, 22 Jul 2010 02:16:02 +1000 (EST) Received: (qmail 16727 invoked by alias); 21 Jul 2010 16:16:00 -0000 Received: (qmail 16695 invoked by uid 22791); 21 Jul 2010 16:15:54 -0000 X-SWARE-Spam-Status: No, hits=-3.4 required=5.0 tests=AWL, BAYES_00, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 21 Jul 2010 16:15:47 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.221.2]) by mx2.suse.de (Postfix) with ESMTP id 7E36587D82; Wed, 21 Jul 2010 18:15:44 +0200 (CEST) Date: Wed, 21 Jul 2010 18:15:44 +0200 (CEST) From: Richard Guenther To: gcc-patches@gcc.gnu.org Cc: Diego Novillo Subject: [PATCH][LTO] Fix PR45018 Message-ID: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org This fixes PR45018 by introducing proper DFS walking to type merging, properly handling SCCs and caching of intermediate comparison results. It actually speeds up type merging and fixes the last issue I know of (fingers crossing ...). Bootstrapped and tested on x86_64-unknown-linux-gnu, SPEC 2k6 is happy with that version now. Ok? Thanks, Richard. 2010-07-21 Richard Guenther PR lto/42451 * gimple.c (gtc_next_dfs_num): New global. (gtc_visit): New function. (gimple_types_compatible_p_1): New function, split out from ... (gimple_types_compatible_p): ... here. Start a DFS walk here. * gcc.dg/lto/20100720-3_0.c: New testcase. * gcc.dg/lto/20100720-3_1.c: Likewise. Index: gcc/testsuite/gcc.dg/lto/20100720-3_0.c =================================================================== *** gcc/testsuite/gcc.dg/lto/20100720-3_0.c (revision 0) --- gcc/testsuite/gcc.dg/lto/20100720-3_0.c (revision 0) *************** *** 0 **** --- 1,24 ---- + /* { dg-lto-do run } */ + + struct X { + int a; + }; + + struct link { + struct list_node *next; + }; + + struct list_node { + struct link lnk; + struct X *value; + }; + + void f(struct list_node *lst) + { + lst->lnk.next = 0; + } + + int main(void) + { + return 0; + } Index: gcc/testsuite/gcc.dg/lto/20100720-3_1.c =================================================================== *** gcc/testsuite/gcc.dg/lto/20100720-3_1.c (revision 0) --- gcc/testsuite/gcc.dg/lto/20100720-3_1.c (revision 0) *************** *** 0 **** --- 1,17 ---- + struct X { + int b; + }; + + struct link { + struct list_node *next; + }; + + struct list_node { + struct link lnk; + struct X *value; + }; + + void g(struct list_node *lst) + { + lst->lnk.next = 0; + } Index: gcc/gimple.c =================================================================== --- gcc/gimple.c (revision 162371) +++ gcc/gimple.c (working copy) @@ -3174,6 +3174,9 @@ struct type_pair_d }; typedef struct type_pair_d *type_pair_t; +DEF_VEC_P(type_pair_t); +DEF_VEC_ALLOC_P(type_pair_t,heap); + /* Return a hash value for the type pair pointed-to by P. */ static hashval_t @@ -3231,6 +3234,21 @@ lookup_type_pair (tree t1, tree t2, htab return p; } +/* 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; + hashval_t hash; +}; + +static unsigned int next_dfs_num; +static unsigned int gtc_next_dfs_num; /* 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 @@ -3344,13 +3362,20 @@ gimple_compatible_complete_and_incomplet return false; } -/* Return 1 iff T1 and T2 are structurally identical. - Otherwise, return 0. */ +static bool +gimple_types_compatible_p_1 (tree, tree, bool, VEC(type_pair_t, heap) **, + struct pointer_map_t *, struct obstack *); -bool -gimple_types_compatible_p (tree t1, tree t2, bool for_merging_p) +static bool +gtc_visit (tree t1, tree t2, bool for_merging_p, + struct sccs *state, + VEC(type_pair_t, heap) **sccstack, + struct pointer_map_t *sccstate, + struct obstack *sccstate_obstack) { - type_pair_t p = NULL; + struct sccs *cstate = NULL; + type_pair_t p; + void **slot; /* Check first for the obvious case of pointer identity. */ if (t1 == t2) @@ -3404,12 +3429,6 @@ gimple_types_compatible_p (tree t1, tree || FIXED_POINT_TYPE_P (t1)) return 1; - /* Perform cheap tail-recursion for vector and complex types. */ - if (TREE_CODE (t1) == VECTOR_TYPE - || TREE_CODE (t1) == COMPLEX_TYPE) - return gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2), - for_merging_p); - /* For integral types fall thru to more complex checks. */ } @@ -3427,8 +3446,7 @@ gimple_types_compatible_p (tree t1, tree if (gimple_type_hash (t1) != gimple_type_hash (t2)) return 0; - /* If we've visited this type pair before (in the case of aggregates - with self-referential types), and we made a decision, return it. */ + /* Allocate a new cache entry for this comparison. */ p = lookup_type_pair (t1, t2, for_merging_p ? >c_visited : >c_visited2, for_merging_p ? >c_ob : >c_ob2); @@ -3438,17 +3456,60 @@ gimple_types_compatible_p (tree t1, tree same, return the cached result. */ return p->same_p == 1; } - else if (p->same_p == -1) + + gcc_assert (p->same_p == -2); + + if ((slot = pointer_map_contains (sccstate, p)) != NULL) + cstate = (struct sccs *)*slot; + if (!cstate) { - /* We are currently comparing this pair of types, assume - that they are the same and let the caller decide. */ - return 1; + int res; + /* Not yet visited. DFS recurse. */ + res = gimple_types_compatible_p_1 (t1, t2, for_merging_p, + sccstack, sccstate, sccstate_obstack); + if (!cstate) + cstate = (struct sccs *)* pointer_map_contains (sccstate, p); + 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 res; } + if (cstate->dfsnum < state->dfsnum + && cstate->on_sccstack) + state->low = MIN (cstate->dfsnum, state->low); + + /* We are part of our parents SCC, skip this entry and return true. */ + return 1; +} + +/* Return 1 iff T1 and T2 are structurally identical. + Otherwise, return 0. */ + +static bool +gimple_types_compatible_p_1 (tree t1, tree t2, bool for_merging_p, + VEC(type_pair_t, heap) **sccstack, + struct pointer_map_t *sccstate, + struct obstack *sccstate_obstack) +{ + type_pair_t p; + struct sccs *state; + /* Allocate a new cache entry for this comparison. */ + p = lookup_type_pair (t1, t2, + for_merging_p ? >c_visited : >c_visited2, + for_merging_p ? >c_ob : >c_ob2); gcc_assert (p->same_p == -2); - /* Mark the (T1, T2) comparison in progress. */ - p->same_p = -1; + 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; /* If their attributes are not the same they can't be the same type. */ if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2))) @@ -3457,11 +3518,18 @@ gimple_types_compatible_p (tree t1, tree /* Do type-specific comparisons. */ switch (TREE_CODE (t1)) { + case VECTOR_TYPE: + case COMPLEX_TYPE: + if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p, + 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 (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2), - for_merging_p) + if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p, + state, sccstack, sccstate, sccstate_obstack) || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2) || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2)) goto different_types; @@ -3509,8 +3577,9 @@ gimple_types_compatible_p (tree t1, tree case METHOD_TYPE: /* Method types should belong to the same class. */ - if (!gimple_types_compatible_p (TYPE_METHOD_BASETYPE (t1), - TYPE_METHOD_BASETYPE (t2), for_merging_p)) + if (!gtc_visit (TYPE_METHOD_BASETYPE (t1), TYPE_METHOD_BASETYPE (t2), + for_merging_p, + state, sccstack, sccstate, sccstate_obstack)) goto different_types; /* Fallthru */ @@ -3521,8 +3590,8 @@ gimple_types_compatible_p (tree t1, tree if ((for_merging_p || !gimple_compatible_complete_and_incomplete_subtype_p (TREE_TYPE (t1), TREE_TYPE (t2))) - && !gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2), - for_merging_p)) + && !gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p, + state, sccstack, sccstate, sccstate_obstack)) goto different_types; if (!targetm.comp_type_attributes (t1, t2)) @@ -3541,9 +3610,9 @@ gimple_types_compatible_p (tree t1, tree if ((for_merging_p || !gimple_compatible_complete_and_incomplete_subtype_p (TREE_VALUE (parms1), TREE_VALUE (parms2))) - && !gimple_types_compatible_p (TREE_VALUE (parms1), - TREE_VALUE (parms2), - for_merging_p)) + && !gtc_visit (TREE_VALUE (parms1), TREE_VALUE (parms2), + for_merging_p, + state, sccstack, sccstate, sccstate_obstack)) goto different_types; } @@ -3555,11 +3624,11 @@ gimple_types_compatible_p (tree t1, tree case OFFSET_TYPE: { - if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2), - for_merging_p) - || !gimple_types_compatible_p (TYPE_OFFSET_BASETYPE (t1), - TYPE_OFFSET_BASETYPE (t2), - for_merging_p)) + if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p, + state, sccstack, sccstate, sccstate_obstack) + || !gtc_visit (TYPE_OFFSET_BASETYPE (t1), + TYPE_OFFSET_BASETYPE (t2), for_merging_p, + state, sccstack, sccstate, sccstate_obstack)) goto different_types; goto same_types; @@ -3582,8 +3651,8 @@ gimple_types_compatible_p (tree t1, tree /* Otherwise, pointer and reference types are the same if the pointed-to types are the same. */ - if (gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2), - for_merging_p)) + if (gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p, + state, sccstack, sccstate, sccstate_obstack)) goto same_types; goto different_types; @@ -3678,8 +3747,8 @@ gimple_types_compatible_p (tree t1, tree if (DECL_NAME (f1) != DECL_NAME (f2) || DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2) || !gimple_compare_field_offset (f1, f2) - || !gimple_types_compatible_p (TREE_TYPE (f1), - TREE_TYPE (f2), for_merging_p)) + || !gtc_visit (TREE_TYPE (f1), TREE_TYPE (f2), for_merging_p, + state, sccstack, sccstate, sccstate_obstack)) goto different_types; } @@ -3697,32 +3766,139 @@ gimple_types_compatible_p (tree t1, tree /* Common exit path for types that are not compatible. */ different_types: - p->same_p = 0; - return 0; + state->hash/*same_p*/ = 0; + goto pop; /* Common exit path for types that are compatible. */ same_types: - p->same_p = 1; - return 1; + state->hash/*same_p*/ = 1; + goto pop; + +pop: + if (state->low == state->dfsnum) + { + type_pair_t x; + + /* Pop off the SCC and set its cache values. */ + 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 = cstate->hash/*same_p*/; + } + while (x != p); + } + + return state->hash/*same_p*/; } +bool +gimple_types_compatible_p (tree t1, tree t2, bool for_merging_p) +{ + VEC(type_pair_t, heap) *sccstack = NULL; + struct pointer_map_t *sccstate; + struct obstack sccstate_obstack; + type_pair_t p = NULL; + bool res; + /* Before starting to set up the SCC machinery handle simple cases. */ + /* Check first for the obvious case of pointer identity. */ + if (t1 == t2) + return 1; -/* 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. */ + /* Check that we have two types to compare. */ + if (t1 == NULL_TREE || t2 == NULL_TREE) + return 0; -struct sccs -{ - unsigned int dfsnum; - unsigned int low; - bool on_sccstack; - hashval_t hash; -}; + /* If the types have been previously registered and found equal + they still are. */ + if (TYPE_CANONICAL (t1) + && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2)) + return 1; + + /* Can't be the same type if the types don't have the same code. */ + if (TREE_CODE (t1) != TREE_CODE (t2)) + return 0; + + /* Can't be the same type if they have different CV qualifiers. */ + if (TYPE_QUALS (t1) != TYPE_QUALS (t2)) + return 0; + + /* Void types are always the same. */ + if (TREE_CODE (t1) == VOID_TYPE) + return 1; + + /* 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) + { + /* Can't be the same type if they have different alignment, + sign, precision or mode. */ + if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2) + || TYPE_PRECISION (t1) != TYPE_PRECISION (t2) + || TYPE_MODE (t1) != TYPE_MODE (t2) + || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2)) + return 0; + + if (TREE_CODE (t1) == INTEGER_TYPE + && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2) + || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))) + return 0; + + /* 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 1; + + /* For integral types fall thru to more complex checks. */ + } + + else if (AGGREGATE_TYPE_P (t1) || POINTER_TYPE_P (t1)) + { + /* 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 0; + } + + /* 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 0; + + /* 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, + for_merging_p ? >c_visited : >c_visited2, + for_merging_p ? >c_ob : >c_ob2); + if (p->same_p == 0 || p->same_p == 1) + { + /* We have already decided whether T1 and T2 are the + same, return the cached result. */ + return p->same_p == 1; + } + + /* 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, for_merging_p, + &sccstack, sccstate, &sccstate_obstack); + VEC_free (type_pair_t, heap, sccstack); + pointer_map_destroy (sccstate); + obstack_free (&sccstate_obstack, NULL); + + return res; +} -static unsigned int next_dfs_num; static hashval_t iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,