This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH 1/4] Add an abstract incremental hash data type


From: Andi Kleen <ak@linux.intel.com>

Some files in gcc, like lto or tree, do large scale incremential hashing.
The current jhash implementation of this could be likely improved
by using an incremential hash that does not do a full rehashing
for every new value added.

This patch adds a new "inchash" class that abstracts the internal
state of the hash. This makes it easier to plug in new hashes
and also cleans up the code a bit.

Right now it is just implemented in the same way as the old
iterative hash in tree.c. The previous iterative hash code
from tree.c moved into a new separate file. Also I fixed up all
users to include the new header.

It should not really change any hashing by itself, it's just
a cleanup at this point.

gcc/:

2014-07-10  Andi Kleen  <ak@linux.intel.com>

	* Makefile.in (OBJS): Add inchash.o.
	(PLUGIN_HEADERS): Add inchash.h.
	* ipa-devirt.c: Include inchash.h.
	* lto-streamer-out.c: Dito.
	* tree-ssa-dom.c: Dito.
	* tree-ssa-pre.c: Dito.
	* tree-ssa-sccvn.c: Dito.
	* tree-ssa-tail-merge.c: Dito.
	* asan.c: Dito.
	* tree.c (iterative_hash_hashval_t): Move to ...
	(iterative_hash_host_wide_int): Move to ...
	* inchash.c: Here. New file.
	* tree.h (iterative_hash_hashval_t): Move to ...
	(iterative_hash_host_wide_int): Move to ...
	* inchash.h: Here. New file.

gcc/lto/:

2014-07-10  Andi Kleen  <ak@linux.intel.com>

	* lto.c: Include inchash.h
---
 gcc/Makefile.in           |  3 +-
 gcc/asan.c                |  1 +
 gcc/inchash.c             | 75 +++++++++++++++++++++++++++++++++++++++++
 gcc/inchash.h             | 86 +++++++++++++++++++++++++++++++++++++++++++++++
 gcc/ipa-devirt.c          |  1 +
 gcc/lto-streamer-out.c    |  1 +
 gcc/lto/lto.c             |  1 +
 gcc/tree-ssa-dom.c        |  1 +
 gcc/tree-ssa-pre.c        |  1 +
 gcc/tree-ssa-sccvn.c      |  1 +
 gcc/tree-ssa-tail-merge.c |  1 +
 gcc/tree.c                | 51 +---------------------------
 gcc/tree.h                |  3 --
 13 files changed, 172 insertions(+), 54 deletions(-)
 create mode 100644 gcc/inchash.c
 create mode 100644 gcc/inchash.h

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 187e6b6..4c578b3 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1268,6 +1268,7 @@ OBJS = \
 	hwint.o \
 	ifcvt.o \
 	ree.o \
+	inchash.o \
 	incpath.o \
 	init-regs.o \
 	internal-fn.o \
@@ -3162,7 +3163,7 @@ PLUGIN_HEADERS = $(TREE_H) $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
   tree-parloops.h tree-ssa-address.h tree-ssa-coalesce.h tree-ssa-dom.h \
   tree-ssa-loop.h tree-ssa-loop-ivopts.h tree-ssa-loop-manip.h \
   tree-ssa-loop-niter.h tree-ssa-ter.h tree-ssa-threadedge.h \
-  tree-ssa-threadupdate.h
+  tree-ssa-threadupdate.h inchash.h
 
 # generate the 'build fragment' b-header-vars
 s-header-vars: Makefile
diff --git a/gcc/asan.c b/gcc/asan.c
index b9a4a91..b5c8f91 100644
--- a/gcc/asan.c
+++ b/gcc/asan.c
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "internal-fn.h"
 #include "gimple-expr.h"
 #include "is-a.h"
+#include "inchash.h"
 #include "gimple.h"
 #include "gimplify.h"
 #include "gimple-iterator.h"
diff --git a/gcc/inchash.c b/gcc/inchash.c
new file mode 100644
index 0000000..0f8583e
--- /dev/null
+++ b/gcc/inchash.c
@@ -0,0 +1,75 @@
+/* Incremential hashing for jhash.
+   Copyright (C) 2014 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "hashtab.h"
+#include "inchash.h"
+
+/* Borrowed from hashtab.c iterative_hash implementation.  */
+#define mix(a,b,c) \
+{ \
+  a -= b; a -= c; a ^= (c>>13); \
+  b -= c; b -= a; b ^= (a<< 8); \
+  c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
+  a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
+  b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
+  c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
+  a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
+  b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
+  c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
+}
+
+
+/* Produce good hash value combining VAL and VAL2.  */
+hashval_t
+iterative_hash_hashval_t (hashval_t val, hashval_t val2)
+{
+  /* the golden ratio; an arbitrary value.  */
+  hashval_t a = 0x9e3779b9;
+
+  mix (a, val, val2);
+  return val2;
+}
+
+/* Produce good hash value combining VAL and VAL2.  */
+
+hashval_t
+iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
+{
+  if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
+    return iterative_hash_hashval_t (val, val2);
+  else
+    {
+      hashval_t a = (hashval_t) val;
+      /* Avoid warnings about shifting of more than the width of the type on
+         hosts that won't execute this path.  */
+      int zero = 0;
+      hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
+      mix (a, b, val2);
+      if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
+	{
+	  hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
+	  hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
+	  mix (a, b, val2);
+	}
+      return val2;
+    }
+}
diff --git a/gcc/inchash.h b/gcc/inchash.h
new file mode 100644
index 0000000..071cf92
--- /dev/null
+++ b/gcc/inchash.h
@@ -0,0 +1,86 @@
+/* An incremental hash abstract data type.
+   Copyright (C) 2014 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef INCHASH_H
+#define INCHASH_H 1
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "hashtab.h"
+
+/* This file implements an incremential hash function ADT, to be used
+   by code that incrementially hashes a lot of unrelated data
+   (not in a single memory block) into a single value. The goal
+   is to make it easy to plug in efficient hash algorithms.
+   Currently it just implements the plain old jhash based
+   incremental hash from gcc's tree.c.  */
+
+extern hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t);
+extern hashval_t iterative_hash_hashval_t (hashval_t, hashval_t);
+
+class inchash
+{
+  hashval_t val;
+ public:
+
+  /* Start incremential hashing, optionally with SEED.  */
+  void begin (hashval_t seed = 0)
+  {
+    val = seed;
+  }
+
+  /* End incremential hashing and provide the final value.  */
+  hashval_t end ()
+  {
+    return val;
+  }
+
+  /* Add unsigned value V.  */
+  void add_int (unsigned v)
+  {
+    val = iterative_hash_hashval_t (v, val);
+  }
+
+  /* Add HOST_WIDE_INT value V.  */
+  void add_wide_int (HOST_WIDE_INT v)
+  {
+    val = iterative_hash_host_wide_int (v, val);
+  }
+
+  /* Hash in pointer PTR.  */
+  void add_ptr (void *ptr)
+  {
+    add (&ptr, sizeof (ptr));
+  }
+
+  /* Add a memory block DATA with size LEN.  */
+  void add (const void *data, size_t len)
+  {
+    val = iterative_hash (data, len, val);
+  }
+
+  /* Hash in state from other inchash OTHER.  */
+  void merge (inchash &other)
+  {
+    val = iterative_hash_hashval_t (other.val, val);
+  }
+};
+
+#endif
diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c
index 59781a1..f3d35d6 100644
--- a/gcc/ipa-devirt.c
+++ b/gcc/ipa-devirt.c
@@ -118,6 +118,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "pointer-set.h"
 #include "target.h"
 #include "hash-table.h"
+#include "inchash.h"
 #include "tree-pretty-print.h"
 #include "ipa-utils.h"
 #include "tree-ssa-alias.h"
diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c
index ccb85b6..cf2e9a8 100644
--- a/gcc/lto-streamer-out.c
+++ b/gcc/lto-streamer-out.c
@@ -44,6 +44,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-pass.h"
 #include "function.h"
 #include "diagnostic-core.h"
+#include "inchash.h"
 #include "except.h"
 #include "lto-symtab.h"
 #include "lto-streamer.h"
diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c
index dc30884..300f569 100644
--- a/gcc/lto/lto.c
+++ b/gcc/lto/lto.c
@@ -33,6 +33,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "langhooks.h"
 #include "bitmap.h"
 #include "hash-map.h"
+#include "inchash.h"
 #include "ipa-prop.h"
 #include "common.h"
 #include "debug.h"
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index c4ec4e5..08fd2fa 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tm_p.h"
 #include "basic-block.h"
 #include "cfgloop.h"
+#include "inchash.h"
 #include "function.h"
 #include "gimple-pretty-print.h"
 #include "tree-ssa-alias.h"
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index b01ad28..8abf68a 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -27,6 +27,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "basic-block.h"
 #include "gimple-pretty-print.h"
 #include "tree-inline.h"
+#include "inchash.h"
 #include "hash-table.h"
 #include "tree-ssa-alias.h"
 #include "internal-fn.h"
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 139ac3b..93314fc 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -30,6 +30,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "hash-table.h"
 #include "tree-ssa-alias.h"
 #include "internal-fn.h"
+#include "inchash.h"
 #include "gimple-fold.h"
 #include "tree-eh.h"
 #include "gimple-expr.h"
diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
index 7245223..9600e28 100644
--- a/gcc/tree-ssa-tail-merge.c
+++ b/gcc/tree-ssa-tail-merge.c
@@ -192,6 +192,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree.h"
 #include "stor-layout.h"
 #include "trans-mem.h"
+#include "inchash.h"
 #include "tm_p.h"
 #include "basic-block.h"
 #include "flags.h"
diff --git a/gcc/tree.c b/gcc/tree.c
index 46f8963..6de3835 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -42,6 +42,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "obstack.h"
 #include "toplev.h" /* get_random_seed */
 #include "hashtab.h"
+#include "inchash.h"
 #include "filenames.h"
 #include "output.h"
 #include "target.h"
@@ -4576,56 +4577,6 @@ build_decl_attribute_variant (tree ddecl, tree attribute)
   return ddecl;
 }
 
-/* Borrowed from hashtab.c iterative_hash implementation.  */
-#define mix(a,b,c) \
-{ \
-  a -= b; a -= c; a ^= (c>>13); \
-  b -= c; b -= a; b ^= (a<< 8); \
-  c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
-  a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
-  b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
-  c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
-  a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
-  b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
-  c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
-}
-
-
-/* Produce good hash value combining VAL and VAL2.  */
-hashval_t
-iterative_hash_hashval_t (hashval_t val, hashval_t val2)
-{
-  /* the golden ratio; an arbitrary value.  */
-  hashval_t a = 0x9e3779b9;
-
-  mix (a, val, val2);
-  return val2;
-}
-
-/* Produce good hash value combining VAL and VAL2.  */
-hashval_t
-iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
-{
-  if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
-    return iterative_hash_hashval_t (val, val2);
-  else
-    {
-      hashval_t a = (hashval_t) val;
-      /* Avoid warnings about shifting of more than the width of the type on
-         hosts that won't execute this path.  */
-      int zero = 0;
-      hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
-      mix (a, b, val2);
-      if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
-	{
-	  hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
-	  hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
-	  mix (a, b, val2);
-	}
-      return val2;
-    }
-}
-
 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
    is ATTRIBUTE and its qualifiers are QUALS.
 
diff --git a/gcc/tree.h b/gcc/tree.h
index 8fa928b..e454e2d 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -4288,9 +4288,6 @@ extern int tree_floor_log2 (const_tree);
 extern unsigned int tree_ctz (const_tree);
 extern int simple_cst_equal (const_tree, const_tree);
 extern hashval_t iterative_hash_expr (const_tree, hashval_t);
-extern hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t);
-extern hashval_t iterative_hash_hashval_t (hashval_t, hashval_t);
-extern hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t);
 extern int compare_tree_int (const_tree, unsigned HOST_WIDE_INT);
 extern int type_list_equal (const_tree, const_tree);
 extern int chain_member (const_tree, const_tree);
-- 
2.0.1


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]