@@ -2639,7 +2639,7 @@ internal-fn.o : internal-fn.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
gimple.o : gimple.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TREE_H) \
$(GGC_H) $(GIMPLE_H) $(DIAGNOSTIC_CORE_H) $(DIAGNOSTIC_H) gt-gimple.h \
$(TREE_FLOW_H) value-prof.h $(FLAGS_H) $(DEMANGLE_H) \
- $(TARGET_H) $(ALIAS_H)
+ $(TARGET_H) $(ALIAS_H) murmurhash.h
gimple-pretty-print.o : gimple-pretty-print.c $(CONFIG_H) $(SYSTEM_H) \
coretypes.h $(DUMPFILE_H) \
$(TREE_H) $(DIAGNOSTIC_H) $(HASHTAB_H) $(TREE_FLOW_H) \
@@ -85,7 +85,7 @@ lto/lto.o: lto/lto.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(OPTS_H) \
langhooks.h $(VEC_H) $(BITMAP_H) pointer-set.h $(IPA_PROP_H) \
$(COMMON_H) debug.h $(GIMPLE_H) $(LTO_H) $(LTO_TREE_H) \
$(LTO_TAGS_H) $(LTO_STREAMER_H) $(SPLAY_TREE_H) gt-lto-lto.h \
- $(TREE_STREAMER_H) lto/lto-partition.h
+ $(TREE_STREAMER_H) lto/lto-partition.h murmurhash.h
lto/lto-partition.o: lto/lto-partition.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
toplev.h $(TREE_H) $(TM_H) \
$(CGRAPH_H) $(TIMEVAR_H) \
@@ -45,6 +45,9 @@ along with GCC; see the file COPYING3. If not see
#include "tree-streamer.h"
#include "splay-tree.h"
#include "lto-partition.h"
+#include "murmurhash.h"
+
+typedef cmurmurhash2A type_incr_hash;
static GTY(()) tree first_personality_decl;
@@ -975,17 +978,17 @@ gimple_types_compatible_p (tree t1, tree t2)
return res;
}
-static hashval_t
-iterative_hash_gimple_type (tree, hashval_t, vec<tree> *,
+static void
+iterative_hash_gimple_type (tree, type_incr_hash &ihstate, vec<tree> *,
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
+ Update the callers type hash HSTATE 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,
+static void
+visit (tree t, struct sccs *state, type_incr_hash &hstate,
vec<tree> *sccstack,
struct pointer_map_t *sccstate,
struct obstack *sccstate_obstack)
@@ -999,15 +1002,18 @@ visit (tree t, struct sccs *state, hashval_t v,
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);
+ {
+ hstate.add_int (((struct tree_int_map *) *slot)->to);
+ return;
+ }
if ((slot = pointer_map_contains (sccstate, t)) != NULL)
cstate = (struct sccs *)*slot;
if (!cstate)
{
- hashval_t tem;
+ type_incr_hash tem = hstate;
/* Not yet visited. DFS recurse. */
- tem = iterative_hash_gimple_type (t, v,
+ iterative_hash_gimple_type (t, tem,
sccstack, sccstate, sccstate_obstack);
if (!cstate)
cstate = (struct sccs *)* pointer_map_contains (sccstate, t);
@@ -1017,7 +1023,10 @@ visit (tree t, struct sccs *state, hashval_t v,
ignore the type for hashing purposes and return the unaltered
hash value. */
if (!cstate->on_sccstack)
- return tem;
+ {
+ hstate = tem;
+ return;
+ }
}
if (cstate->dfsnum < state->dfsnum
&& cstate->on_sccstack)
@@ -1025,23 +1034,22 @@ visit (tree t, struct sccs *state, hashval_t v,
/* 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. */
+/* Update HSTATE with NAME */
-static hashval_t
-iterative_hash_name (tree name, hashval_t v)
+static void
+iterative_hash_name (tree name, type_incr_hash &hstate)
{
if (!name)
- return v;
- v = iterative_hash_hashval_t (TREE_CODE (name), v);
+ return;
+ hstate.add_int (TREE_CODE (name));
if (TREE_CODE (name) == TYPE_DECL)
name = DECL_NAME (name);
if (!name)
- return v;
+ return;
gcc_assert (TREE_CODE (name) == IDENTIFIER_NODE);
- return iterative_hash_object (IDENTIFIER_HASH_VALUE (name), v);
+ hstate.add_int (IDENTIFIER_HASH_VALUE (name));
}
/* A type, hashvalue pair for sorting SCC members. */
@@ -1065,7 +1073,7 @@ type_hash_pair_compare (const void *p1_, const void *p2_)
return 0;
}
-/* Returning a hash value for gimple type TYPE combined with VAL.
+/* Update IHSTATE for gimple type TYPE
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.
@@ -1077,15 +1085,17 @@ type_hash_pair_compare (const void *p1_, const void *p2_)
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,
+static void
+iterative_hash_gimple_type (tree type, type_incr_hash &ihstate,
vec<tree> *sccstack,
struct pointer_map_t *sccstate,
struct obstack *sccstate_obstack)
{
- hashval_t v;
void **slot;
struct sccs *state;
+ type_incr_hash hstate;
+
+ hstate.begin ();
/* Not visited during this DFS walk. */
gcc_checking_assert (!pointer_map_contains (sccstate, type));
@@ -1101,22 +1111,21 @@ iterative_hash_gimple_type (tree type, hashval_t val,
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);
+ iterative_hash_name (TYPE_NAME (type), hstate);
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,
+ visit (DECL_CONTEXT (TYPE_NAME (type)), state, hstate,
sccstack, sccstate, sccstate_obstack);
/* Factor in the variant structure. */
if (TYPE_MAIN_VARIANT (type) != type)
- v = visit (TYPE_MAIN_VARIANT (type), state, v,
+ visit (TYPE_MAIN_VARIANT (type), state, hstate,
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);
+ hstate.add_int (TREE_CODE (type) | (TREE_ADDRESSABLE (type) << 24));
+ hstate.add_int (TYPE_QUALS (type));
/* Do not hash the types size as this will cause differences in
hash values for the complete vs. the incomplete type variant. */
@@ -1126,15 +1135,15 @@ iterative_hash_gimple_type (tree type, hashval_t val,
|| 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);
+ hstate.add_int (TYPE_MODE (type)
+ | (TYPE_UNSIGNED (type) << 16)
+ | (TYPE_PRECISION (type) << 17));
}
/* 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,
+ visit (TREE_TYPE (type), state, hstate,
sccstack, sccstate, sccstate_obstack);
/* For integer types hash the types min/max values and the string flag. */
@@ -1143,17 +1152,17 @@ iterative_hash_gimple_type (tree type, hashval_t val,
/* 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);
+ hstate.add_int (iterative_hash_expr (TYPE_MIN_VALUE (type), 0));
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);
+ hstate.add_int (iterative_hash_expr (TYPE_MAX_VALUE (type), 0));
+ hstate.add_int (TYPE_STRING_FLAG (type));
}
/* 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,
+ hstate.add_int (TYPE_STRING_FLAG (type));
+ visit (TYPE_DOMAIN (type), state, hstate,
sccstack, sccstate, sccstate_obstack);
}
@@ -1161,7 +1170,7 @@ iterative_hash_gimple_type (tree type, hashval_t val,
if (TREE_CODE (type) == ARRAY_TYPE
|| TREE_CODE (type) == COMPLEX_TYPE
|| TREE_CODE (type) == VECTOR_TYPE)
- v = visit (TREE_TYPE (type), state, v,
+ visit (TREE_TYPE (type), state, hstate,
sccstack, sccstate, sccstate_obstack);
/* Incorporate function return and argument types. */
@@ -1172,20 +1181,20 @@ iterative_hash_gimple_type (tree type, hashval_t val,
/* For method types also incorporate their parent class. */
if (TREE_CODE (type) == METHOD_TYPE)
- v = visit (TYPE_METHOD_BASETYPE (type), state, v,
+ visit (TYPE_METHOD_BASETYPE (type), state, hstate,
sccstack, sccstate, sccstate_obstack);
/* Check result and argument types. */
- v = visit (TREE_TYPE (type), state, v,
+ visit (TREE_TYPE (type), state, hstate,
sccstack, sccstate, sccstate_obstack);
for (p = TYPE_ARG_TYPES (type), na = 0; p; p = TREE_CHAIN (p))
{
- v = visit (TREE_VALUE (p), state, v,
+ visit (TREE_VALUE (p), state, hstate,
sccstack, sccstate, sccstate_obstack);
na++;
}
- v = iterative_hash_hashval_t (na, v);
+ hstate.add_int (na);
}
if (RECORD_OR_UNION_TYPE_P (type))
@@ -1195,17 +1204,17 @@ iterative_hash_gimple_type (tree type, hashval_t val,
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,
+ iterative_hash_name (DECL_NAME (f), hstate);
+ visit (TREE_TYPE (f), state, hstate,
sccstack, sccstate, sccstate_obstack);
nf++;
}
- v = iterative_hash_hashval_t (nf, v);
+ hstate.add_int (nf);
}
/* Record hash for us. */
- state->u.hash = v;
+ state->u.hash = hstate.end ();
/* See if we found an SCC. */
if (state->low == state->dfsnum)
@@ -1221,7 +1230,7 @@ iterative_hash_gimple_type (tree type, hashval_t val,
state->on_sccstack = false;
m = ggc_alloc_cleared_tree_int_map ();
m->base.from = x;
- m->to = v;
+ m->to = state->u.hash;
slot = htab_find_slot (type_hash_cache, m, INSERT);
gcc_assert (!*slot);
*slot = (void *) m;
@@ -1262,28 +1271,28 @@ iterative_hash_gimple_type (tree type, hashval_t val,
type_hash_pair_compare);
for (i = 0; i < size; ++i)
{
- hashval_t hash;
+ type_incr_hash hs;
m = ggc_alloc_cleared_tree_int_map ();
m->base.from = pairs[i].type;
- hash = pairs[i].hash;
+ hs.begin (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);
+ hs.add_int (pairs[j].hash);
for (j = 0; pairs[j].hash != pairs[i].hash; ++j)
- hash = iterative_hash_hashval_t (pairs[j].hash, hash);
- m->to = hash;
+ hs.add_int (pairs[j].hash);
+ m->to = hs.end();
if (pairs[i].type == type)
- v = hash;
+ hstate = hs;
slot = htab_find_slot (type_hash_cache, m, INSERT);
gcc_assert (!*slot);
*slot = (void *) m;
}
}
}
-
- return iterative_hash_hashval_t (v, val);
+
+ ihstate.merge (hstate);
}
/* Returns a hash value for P (assumed to be a type). The hash value
@@ -1301,26 +1310,27 @@ gimple_type_hash (const void *p)
vec<tree> sccstack = vNULL;
struct pointer_map_t *sccstate;
struct obstack sccstate_obstack;
- hashval_t val;
+ type_incr_hash hstate;
void **slot;
struct tree_int_map m;
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);
+ return ((struct tree_int_map *) *slot)->to;
/* 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,
+ hstate.begin ();
+ iterative_hash_gimple_type (CONST_CAST_TREE (t), hstate,
&sccstack, sccstate, &sccstate_obstack);
sccstack.release ();
pointer_map_destroy (sccstate);
obstack_free (&sccstate_obstack, NULL);
- return val;
+ return hstate.end ();
}
/* Returns nonzero if P1 and P2 are equal. */
From: Andi Kleen <ak@linux.intel.com> The type merging operation in LTO WPA is very expensive and can create multi GB hash tables. Use murmurhash2A for the type merging hash. Improves LTO build performance on a large project by 3.2% This both comes from less collisions and somewhat faster hashing. Use the expanded hash state to add additional bits, instead of always compressing the hash before adding new bits. Also tweak the hashing a bit to be slightly more efficient and not rerun the full hash to add a single bit. gcc/: 2013-04-18 Andi Kleen <ak@linux.intel.com> * Makefile.in (gimple.o): Add murmurhash.h dependency. * lto/Make-lang.in (lto/lto.o): dito. * lto/lto.c (gimple_types_compatible_p): Use murmurhash to hash. (visit): dito. (iterative_hash_name): dito. (type_hash_pair_compare): dito. (iterative_hash_gimple_type): dito. (gimple_type_hash): dito. --- gcc/Makefile.in | 2 +- gcc/lto/Make-lang.in | 2 +- gcc/lto/lto.c | 126 +++++++++++++++++++++++++++------------------------ 3 files changed, 70 insertions(+), 60 deletions(-)