Patchwork [5/9] Use murmurhash2A for type merging

login
register
mail settings
Submitter Andi Kleen
Date April 19, 2013, 9:31 p.m.
Message ID <1366407117-18462-6-git-send-email-andi@firstfloor.org>
Download mbox | patch
Permalink /patch/238123/
State New
Headers show

Comments

Andi Kleen - April 19, 2013, 9:31 p.m.
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(-)

Patch

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 28815a2..315a2a5 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -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) \
diff --git a/gcc/lto/Make-lang.in b/gcc/lto/Make-lang.in
index a0bdc26..2c685ea 100644
--- a/gcc/lto/Make-lang.in
+++ b/gcc/lto/Make-lang.in
@@ -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) \
diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
index 983fa03..d757be0 100644
--- a/gcc/lto/lto.c
+++ b/gcc/lto/lto.c
@@ -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.  */