This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][LTO] Speed up gimple_type_hash
On Thu, 16 Jul 2009, Diego Novillo wrote:
> On Thu, Jul 16, 2009 at 09:54, Richard Guenther<rguenther@suse.de> wrote:
>
> > 2009-07-16 ÂRichard Guenther Â<rguenther@suse.de>
> >
> > Â Â Â Â* gimple.c (iterative_hash_gimple_type): Remove the level argument,
> > Â Â Â Âadd a stack argument for tracking cycles.
> > Â Â Â ÂQuery the pointer-map with the pre-computed hashes and update it
> > Â Â Â Âfor types not in a cycle.
> > Â Â Â Â(gimple_type_hash): Assign all types in a cycle the same hash value.
>
> OK. Thanks for speeding this up.
I just noticed that it was still broken (even though it passed the
testsuite). The following implements the theoretically sound variant
of doing proper SCC finding and hashing the SCC at once. To guarantee
the same hash values for SCC members independent on how we enter the
SCC (and without a need to define a total ordering for types) the
members of the SCC are ignored when computing the hash for a member
of the SCC. We could use a communtative hash function like XOR for
the SCC members and mix them in at SCC processing time, but I
doubt it would change anything and it at least sounds more complicated.
I bootstrapped and tested a uglier version ok on x86_64-unknown-linux-gnu
and am now re-bootstrapping and testing the properly cleaned version
below.
Ok for lto if it passes?
Thanks,
Richard.
2009-07-17 Richard Guenther <rguenther@suse.de>
* gimple.c (struct sccs): New structure for the SCC finding state.
(next_dfs_num): New static global.
(visit): New helper function for iterative_hash_gimple_type.
(iterative_hash_gimple_type): Rewrite to do a DFS walk to properly
hash SCCs.
(gimple_type_hash): Adjust accordingly.
Index: gcc/gimple.c
===================================================================
*** gcc/gimple.c.orig 2009-07-17 12:45:38.000000000 +0200
--- gcc/gimple.c 2009-07-17 14:34:46.000000000 +0200
*************** gimple_types_compatible_p (tree t1, tree
*** 3538,3555 ****
}
! /* Returning a hash value for gimple type TYPE combined with VAL. */
static hashval_t
! iterative_hash_gimple_type (const_tree type, hashval_t val, unsigned level)
{
hashval_t v;
/* 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_hashval_t (TREE_CODE (type), val);
v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
v = iterative_hash_expr (TYPE_SIZE (type), v);
v = iterative_hash_expr (TYPE_SIZE_UNIT (type), v);
--- 3538,3670 ----
}
! /* 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 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;
! 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. */
! if ((slot = pointer_map_contains (type_hash_cache, t)))
! {
! #ifdef ENABLE_CHECKING
! void **slot2;
! /* If we have visited the type during the DFS walk then it
! should not be on the SCC stack anymore. */
! if ((slot2 = pointer_map_contains (sccstate, t)) != NULL)
! gcc_assert (!((struct sccs *)*slot2)->on_sccstack);
! #endif
! return iterative_hash_hashval_t ((hashval_t) (size_t) *slot, 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)
! {
! #ifdef ENABLE_CHECKING
! /* If we are not on the stack we should have a hash value
! recorded. */
! gcc_assert (pointer_map_contains (type_hash_cache, t));
! #endif
! return tem;
! }
! }
! if (cstate->dfsnum < state->dfsnum
! && cstate->on_sccstack)
! state->low = MIN (cstate->dfsnum, state->low);
!
! #ifdef ENABLE_CHECKING
! /* As we are part of an SCC that is still in processing we should
! not have a hash value recorded. */
! gcc_assert (!pointer_map_contains (type_hash_cache, t));
! #endif
!
! /* We are part of our parents SCC, skip this type during hashing
! and return the unaltered hash value. */
! return v;
! }
!
! /* 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;
+
+ #ifdef ENABLE_CHECKING
+ /* Not visited during this DFS walk nor during previous walks. */
+ gcc_assert (!pointer_map_contains (type_hash_cache, type)
+ && !pointer_map_contains (sccstate, type));
+ #endif
+ 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_hashval_t (TREE_CODE (type), 0);
v = iterative_hash_hashval_t (TYPE_QUALS (type), v);
v = iterative_hash_expr (TYPE_SIZE (type), v);
v = iterative_hash_expr (TYPE_SIZE_UNIT (type), v);
*************** iterative_hash_gimple_type (const_tree t
*** 3568,3592 ****
/* Incorporate function return and argument types. */
if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
{
tree p;
/* For method types also incorporate their parent class. */
if (TREE_CODE (type) == METHOD_TYPE)
! v = iterative_hash_gimple_type (TYPE_METHOD_BASETYPE (type), v, level);
! v = iterative_hash_gimple_type (TREE_TYPE (type), v, level);
! for (p = TYPE_ARG_TYPES (type); p; p = TREE_CHAIN (p))
! v = iterative_hash_gimple_type (TREE_VALUE (p), v, level);
}
/* For pointer and reference types, fold in information about the type
pointed to. */
if (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
! v = iterative_hash_gimple_type (TREE_TYPE (type), v, level);
- /* For aggregate types, incorporate types signatures up to 5 levels
- (to prevent infinite recursion in self-referential types). */
if (TREE_CODE (type) == RECORD_TYPE
|| TREE_CODE (type) == UNION_TYPE
|| TREE_CODE (type) == QUAL_UNION_TYPE)
--- 3683,3713 ----
/* 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)
! visit (TYPE_METHOD_BASETYPE (type), state, v,
! sccstack, sccstate, sccstate_obstack);
! visit (TREE_TYPE (type), state, v, sccstack, sccstate, sccstate_obstack);
!
! for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
! {
! visit (TREE_VALUE (p), state, v,
! sccstack, sccstate, sccstate_obstack);
! na++;
! }
! v = iterative_hash_hashval_t (na, v);
}
/* For pointer and reference types, fold in information about the type
pointed to. */
if (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
! visit (TREE_TYPE (type), state, v, sccstack, sccstate, sccstate_obstack);
if (TREE_CODE (type) == RECORD_TYPE
|| TREE_CODE (type) == UNION_TYPE
|| TREE_CODE (type) == QUAL_UNION_TYPE)
*************** iterative_hash_gimple_type (const_tree t
*** 3596,3610 ****
for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
{
! if (level < 5)
! v = iterative_hash_gimple_type (TREE_TYPE (f), v, level + 1);
nf++;
}
v = iterative_hash_hashval_t (nf, v);
}
! return v;
}
--- 3717,3752 ----
for (f = TYPE_FIELDS (type), nf = 0; f; f = TREE_CHAIN (f))
{
! visit (TREE_TYPE (f), state, v, sccstack, sccstate, sccstate_obstack);
nf++;
}
v = iterative_hash_hashval_t (nf, v);
}
! /* Record hash for us. */
! state->hash = v;
!
! /* See if we found an SCC. */
! if (state->low == state->dfsnum)
! {
! tree x;
!
! /* Pop off the SCC and set its hash values. */
! do
! {
! struct sccs *cstate;
! x = VEC_pop (tree, *sccstack);
! gcc_assert (!pointer_map_contains (type_hash_cache, x));
! cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
! cstate->on_sccstack = false;
! slot = pointer_map_insert (type_hash_cache, x);
! *slot = (void *) (size_t) cstate->hash;
! }
! while (x != type);
! }
!
! return iterative_hash_hashval_t (v, val);
}
*************** iterative_hash_gimple_type (const_tree t
*** 3619,3647 ****
static hashval_t
gimple_type_hash (const void *p)
{
! const_tree type;
void **slot;
- hashval_t v;
-
- type = (const_tree) p;
if (type_hash_cache == NULL)
! {
! type_hash_cache = pointer_map_create ();
! slot = NULL;
! }
! else
! slot = pointer_map_contains (type_hash_cache, type);
! if (slot)
! v = (hashval_t) (size_t) *slot;
! else
! {
! v = iterative_hash_gimple_type (type, 0, 0);
! *pointer_map_insert (type_hash_cache, type) = (void *) (size_t) v;
! }
! return v;
}
--- 3761,3789 ----
static hashval_t
gimple_type_hash (const void *p)
{
! VEC(tree, heap) *sccstack = NULL;
! struct pointer_map_t *sccstate;
! struct obstack sccstate_obstack;
! hashval_t val;
void **slot;
if (type_hash_cache == NULL)
! type_hash_cache = pointer_map_create ();
! if ((slot = pointer_map_contains (type_hash_cache, p)) != NULL)
! return iterative_hash_hashval_t ((hashval_t) (size_t) *slot, 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_CAST2 (tree, const void *, p), 0,
! &sccstack, sccstate, &sccstate_obstack);
! VEC_free (tree, heap, sccstack);
! pointer_map_destroy (sccstate);
! obstack_free (&sccstate_obstack, NULL);
!
! return val;
}