Add an abstract incremental hash data type

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 significantly change any hashing by itself,
it's mostly a cleanup at this point.

v2: Remove begin. Add commutative interface.
Add merge hash interface.  Add add_flag.

gcc/:

2014-07-25  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-25  Andi Kleen  <ak@linux.intel.com>

	* lto.c: Include inchash.h

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@213054 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 129 insertions, 0 deletions

diff --git a/gcc/inchash.h b/gcc/inchash.h
new file mode 100644
index 00000000000..7af0baaddbd
--- /dev/null
+++ b/gcc/inchash.h
@@ -0,0 +1,129 @@
+/* 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
+{
+ public:
+
+  /* Start incremential hashing, optionally with SEED.  */
+  inchash (hashval_t seed = 0)
+  {
+    val = seed;
+    bits = 0;
+  }
+
+  /* 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);
+  }
+
+  /* Merge hash value OTHER.  */
+  void merge_hash (hashval_t other)
+  {
+    val = iterative_hash_hashval_t (other, val);
+  }
+
+  /* Hash in state from other inchash OTHER.  */
+  void merge (inchash &other)
+  {
+    merge_hash (other.val);
+  }
+
+  /* Support for accumulating boolean flags */
+
+  void add_flag (bool flag)
+  {
+    bits = (bits << 1) | flag;
+  }
+
+  void commit_flag ()
+  {
+    add_int (bits);
+    bits = 0;
+  }
+
+  /* Support for commutative hashing. Add A and B in a defined order
+     based on their value. This is useful for hashing commutative
+     expressions, so that A+B and B+A get the same hash.  */
+
+  void add_commutative (inchash &a, inchash &b)
+  {
+    if (a.end() > b.end())
+      {
+        merge (b);
+	merge (a);
+      }
+    else
+      {
+        merge (a);
+        merge (b);
+      }
+  }
+
+ private:
+  hashval_t val;
+  unsigned bits;
+};
+
+#define add_object(o) add (&(o), sizeof (o))
+
+#endif