Speed up walk_tree by introducing a special-purpose hash table.

	* pointer-set.c: New file, special-purpose hash table.
	* pointer-set.h: New file.
	* tree.h (struct pointer_set_t): Declare as opaque type.
	(tree_walk): Last argument is pointer_set_t* now.
	* tree-inline.c (WALK_SUBTREE): Convert from htab to pset.
	(walk_type_fields):
	(walk_tree): Convert from htab_t to pointer_set_t for keeping
	track of which nodes have already been visited.
	(walk_tree_without_duplicates): Convert from htab_t to pointer_set_t.
	* cgraphunit.c (cgraph_create_edges): Likewise.
	(cgraph_characterize_statics_local): Likewise.
	* tree-dfa.c (collect_dfa_stats): Likewise.
	* langhooks-def.h (lhd_tree_inlining_walk_subtrees): Last arg is
	pointer_set_t* now.
	* langhooks.c (lhd_tree_inlining_walk_subtrees): Likewise.
	* langhooks.h (struct lang_hooks_for_tree_inlining): Last arg type
	of walk_subtrees is pointer_set_t* now.
	* Makefile.in (OBJS-common): add pointer-set.o
	(tree-inline.o): Depends on pointer-set.h
	(tree-dfa.o): Likewise
	(cgraphunit.o): Likewise
	* cp/Make-lang.in (pt.o): depends on pointer-set.h
	* cp/cp-tree.h (cp_walk_subtrees): Last argument is pointer_set_t* now.
	* cp/pt.c (struct pair_fn_data): Use pointer_set_t, not htab_t
	(for_each_template_parm): Convert from htab_t to pointer_set_t.
	* cp/tree.c (cp_walk_subtrees): Last argument is pointer_set_t* now.
	* java/lang.c (java_tree_inlining_walk_subtrees): Last arg is struct
	pointer_set_t* now.


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

1 files changed, 167 insertions, 0 deletions

diff --git a/gcc/pointer-set.c b/gcc/pointer-set.c
new file mode 100644
index 00000000000..510ae430d30
--- /dev/null
+++ b/gcc/pointer-set.c
@@ -0,0 +1,167 @@
+/* Set operations on pointers
+   Copyright (C) 2004 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 2, 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 COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "pointer-set.h"
+
+/* A pointer sets is represented as a simple open-addressing hash
+   table.  Simplifications: The hash code is based on the value of the
+   pointer, not what it points to.  The number of buckets is always a
+   power of 2.  Null pointers are a reserved value.  Deletion is not
+   supported.  There is no mechanism for user control of hash
+   function, equality comparison, initial size, or resizing policy.
+*/
+
+struct pointer_set_t
+{
+  size_t log_slots;
+  size_t n_slots;		/* n_slots = 2^log_slots */
+  size_t n_elements;
+
+  void **slots;
+};
+
+/* Use the multiplicative method, as described in Knuth 6.4, to obtain
+   a hash code for P in the range [0, MAX).  MAX == 2^LOGMAX.
+
+   Summary of this method: Multiply p by some number A that's
+   relatively prime to 2^sizeof(size_t).  The result is two words.
+   Discard the most significant word, and return the most significant
+   N bits of the least significant word.  As suggested by Knuth, our
+   choice for A is the integer part of 2^32 / phi, where phi is the
+   golden ratio.
+
+   We don't need to do anything special for full-width multiplication
+   because we're only interested in the least significant word of the
+   product, and unsigned arithmetic in C is modulo the word size. */
+
+static inline size_t
+hash1 (const void *p, unsigned long max, unsigned long logmax)
+{
+  const unsigned long A = 0x9e3779b9u;
+  const unsigned long shift = sizeof(unsigned long) * CHAR_BIT - logmax;
+
+  return ((A * (unsigned long) p) >> shift) & (max - 1);
+}
+
+/* Allocate an empty pointer set. */
+struct pointer_set_t *
+pointer_set_create (void)
+{
+  struct pointer_set_t *result = XNEW (struct pointer_set_t);
+
+  result->n_elements = 0;
+  result->log_slots = 8;
+  result->n_slots = (size_t) 1 << result->log_slots;
+
+  result->slots = XCNEWVEC (void *, result->n_slots);
+  return result;
+}
+
+/* Reclaims all memory associated with PSET. */
+void pointer_set_destroy (struct pointer_set_t *pset)
+{
+  XDELETEVEC (pset->slots);
+  XDELETE (pset);
+}
+
+/* Returns nonzero if PSET contains P.  P must be nonnull.
+
+   Collisions are resolved by linear probing.  More complicated
+   collision management schemes are only useful when the load factor
+   significatly exceeds 0.5, and we never let that happen. */
+int
+pointer_set_contains (struct pointer_set_t *pset, void *p)
+{
+  size_t n = hash1 (p, pset->n_slots, pset->log_slots);
+
+  while (true)
+    {
+      if (pset->slots[n] == p)
+	return 1;
+      else if (pset->slots[n] == 0)
+	return 0;
+      else
+	{
+	  ++n;
+	  if (n == pset->n_slots)
+	    n = 0;
+	}
+    }
+}
+
+/* Subroutine of pointer_set_insert.  Inserts P into an empty
+   element of SLOTS, an array of length N_SLOTS.  Returns nonzero
+   if P was already present in N_SLOTS. */
+static int
+insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
+{
+  size_t n = hash1 (p, n_slots, log_slots);
+  while (true)
+    {
+      if (slots[n] == p)
+	return 1;
+      else if (slots[n] == 0)
+	{
+	  slots[n] = p;
+	  return 0;
+	}
+      else
+	{
+	  ++n;
+	  if (n == n_slots)
+	    n = 0;
+	}
+    }
+}
+
+/* Inserts P into PSET if it wasn't already there.  Returns nonzero
+   if it was already there. P must be nonnull. */
+int
+pointer_set_insert (struct pointer_set_t *pset, void *p)
+{
+  if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
+    return 1;
+      
+  /* We've inserted a new element.  Expand the table if necessary to keep
+     the load factor small. */
+  ++pset->n_elements;
+  if (pset->n_elements > pset->n_slots / 4)
+    {
+      size_t new_log_slots = pset->log_slots + 1;
+      size_t new_n_slots = pset->n_slots * 2;
+      void **new_slots = XCNEWVEC (void *, new_n_slots);
+      size_t i;
+
+      for (i = 0; i < pset->n_slots; ++i)
+	{
+	  if (pset->slots[i])
+	    insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
+	}
+
+      XDELETEVEC (pset->slots);
+      pset->n_slots = new_n_slots;
+      pset->log_slots = new_log_slots;
+      pset->slots = new_slots;
+    }
+
+  return 0;
+}