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

18 files changed, 296 insertions, 57 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 2475f9f2c27..55ba8886994 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,27 @@
+2004-10-14  Matt Austern  <austern@apple.com>
+
+	* 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
+	
 2004-10-14  Geoffrey Keating  <geoffk@apple.com>
 
 	* config/rs6000/darwin.h (ASM_SPEC): Delete.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 622ecd2ef15..432ce8fe010 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -914,7 +914,7 @@ OBJS-common = \
  params.o postreload.o postreload-gcse.o predict.o			   \
  insn-preds.o integrate.o intl.o jump.o langhooks.o lcm.o lists.o 	   \
  local-alloc.o loop.o modulo-sched.o optabs.o options.o opts.o		   \
- params.o postreload.o postreload-gcse.o predict.o			   \
+ params.o pointer-set.o postreload.o postreload-gcse.o predict.o 	   \
  print-rtl.o print-tree.o value-prof.o var-tracking.o			   \
  profile.o ra.o ra-build.o ra-colorize.o ra-debug.o ra-rewrite.o	   \
  real.o recog.o reg-stack.o regclass.o regmove.o regrename.o		   \
@@ -1592,7 +1592,7 @@ tree-inline.o : tree-inline.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TREE_H) $(RTL_H) $(EXPR_H) $(FLAGS_H) $(PARAMS_H) input.h insn-config.h \
    $(INTEGRATE_H) $(VARRAY_H) $(HASHTAB_H) $(SPLAY_TREE_H) toplev.h \
    langhooks.h $(C_COMMON_H) tree-inline.h $(CGRAPH_H) intl.h function.h \
-   $(TREE_GIMPLE_H)
+   pointer-set.h $(TREE_GIMPLE_H)
 print-tree.o : print-tree.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
    $(GGC_H) langhooks.h real.h
 stor-layout.o : stor-layout.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
@@ -1686,7 +1686,7 @@ tree-iterator.o : tree-iterator.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
    coretypes.h $(GGC_H) tree-iterator.h tree-gimple.h gt-tree-iterator.h
 tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h diagnostic.h \
-   errors.h tree-inline.h $(HASHTAB_H) $(FLAGS_H) function.h $(TIMEVAR_H) \
+   errors.h tree-inline.h $(HASHTAB_H) pointer-set.h $(FLAGS_H) function.h $(TIMEVAR_H) \
    convert.h $(TM_H) coretypes.h langhooks.h \
    $(TREE_DUMP_H) tree-pass.h params.h $(CGRAPH_H)
 tree-ssa-operands.o : tree-ssa-operands.c $(TREE_FLOW_H) $(CONFIG_H) \
@@ -1923,7 +1923,7 @@ cgraph.o : cgraph.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
    output.h intl.h
 cgraphunit.o : cgraphunit.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
    langhooks.h tree-inline.h toplev.h $(FLAGS_H) $(GGC_H)  $(TARGET_H) $(CGRAPH_H) intl.h \
-   function.h $(TREE_GIMPLE_H) $(TREE_FLOW_H)
+   pointer-set.h function.h $(TREE_GIMPLE_H) $(TREE_FLOW_H)
 coverage.o : coverage.c gcov-io.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) function.h \
    toplev.h $(GGC_H) $(TARGET_H) langhooks.h $(COVERAGE_H) libfuncs.h \
@@ -2172,6 +2172,7 @@ lambda-code.o: lambda-code.c $(LAMBDA_H) $(GGC_H) $(SYSTEM_H) $(CONFIG_H) \
    $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h \
    $(TREE_DATA_REF_H) $(SCEV_H)
 params.o : params.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(PARAMS_H) toplev.h
+pointer-set.o: pointer-set.c pointer-set.h $(CONFIG_H) $(SYSTEM_H)
 hooks.o: hooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(HOOKS_H)
 pretty-print.o: $(CONFIG_H) $(SYSTEM_H) coretypes.h intl.h $(PRETTY_PRINT_H) \
    $(TREE_H)
diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c
index 5d0a32faad6..e942aada193 100644
--- a/gcc/cgraphunit.c
+++ b/gcc/cgraphunit.c
@@ -186,7 +186,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "tree-flow.h"
 #include "tree-inline.h"
 #include "langhooks.h"
-#include "hashtab.h"
+#include "pointer-set.h"
 #include "toplev.h"
 #include "flags.h"
 #include "ggc.h"
@@ -223,7 +223,7 @@ static int overall_insns;
    walk_tree_without_duplicates doesn't guarantee each node is visited
    once because it gets a new htab upon each recursive call from
    record_calls_1.  */
-static htab_t visited_nodes;
+static struct pointer_set_t *visited_nodes;
 
 static FILE *cgraph_dump_file;
 
@@ -698,10 +698,9 @@ cgraph_create_edges (struct cgraph_node *node, tree body)
 {
   /* The nodes we're interested in are never shared, so walk
      the tree ignoring duplicates.  */
-  visited_nodes = htab_create (37, htab_hash_pointer,
-				    htab_eq_pointer, NULL);
+  visited_nodes = pointer_set_create ();
   walk_tree (&body, record_call_1, node, visited_nodes);
-  htab_delete (visited_nodes);
+  pointer_set_destroy (visited_nodes);
   visited_nodes = NULL;
 }
 
@@ -2288,8 +2287,7 @@ cgraph_characterize_statics_local (struct cgraph_node *fn)
 
   /* The nodes we're interested in are never shared, so walk
      the tree ignoring duplicates.  */
-  visited_nodes = htab_create (37, htab_hash_pointer,
-			       htab_eq_pointer, NULL);
+  visited_nodes = pointer_set_create ();
   
   /* FIXME -- PROFILE-RESTRUCTURE: Remove creation of _decl_uid vars.  */
   l->statics_read_by_decl_uid = BITMAP_GGC_ALLOC ();
@@ -2299,7 +2297,7 @@ cgraph_characterize_statics_local (struct cgraph_node *fn)
     fprintf (cgraph_dump_file, "\n local analysis of %s", cgraph_node_name (fn));
   
   walk_tree (&DECL_SAVED_TREE (decl), scan_for_static_refs, fn, visited_nodes);
-  htab_delete (visited_nodes);
+  pointer_set_destroy (visited_nodes);
   visited_nodes = NULL;
 }
 
diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 270a4ebe2bd..bb8678e774a 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,11 @@
+2004-10-14  Matt Austern  <austern@apple.com>
+
+	* Make-lang.in (pt.o): depends on pointer-set.h
+	* cp-tree.h (cp_walk_subtrees): Last argument is pointer_set_t* now.
+	* 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.
+	* tree.c (cp_walk_subtrees): Last argument is pointer_set_t* now.
+	
 2004-10-13  Andrew Pinski  <pinskia@physics.uc.edu>
 
 	PR c++/17661
diff --git a/gcc/cp/Make-lang.in b/gcc/cp/Make-lang.in
index 27ef4f28f6e..891d27120af 100644
--- a/gcc/cp/Make-lang.in
+++ b/gcc/cp/Make-lang.in
@@ -260,7 +260,7 @@ cp/except.o: cp/except.c $(CXX_TREE_H) $(TM_H) flags.h $(RTL_H) except.h toplev.
 cp/expr.o: cp/expr.c $(CXX_TREE_H) $(TM_H) $(RTL_H) flags.h $(EXPR_H) toplev.h \
   except.h $(TM_P_H)
 cp/pt.o: cp/pt.c $(CXX_TREE_H) $(TM_H) cp/decl.h \
-  toplev.h $(RTL_H) except.h tree-inline.h gt-cp-pt.h
+  toplev.h $(RTL_H) except.h tree-inline.h pointer-set.h gt-cp-pt.h
 cp/error.o: cp/error.c $(CXX_TREE_H) $(TM_H) toplev.h $(DIAGNOSTIC_H) \
   flags.h real.h $(LANGHOOKS_DEF_H) $(CXX_PRETTY_PRINT_H)
 cp/repo.o: cp/repo.c $(CXX_TREE_H) $(TM_H) toplev.h diagnostic.h \
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 6f777b195ef..2350ab0d60f 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -4215,7 +4215,7 @@ extern void verify_stmt_tree                    (tree);
 extern tree find_tree                           (tree, tree);
 extern linkage_kind decl_linkage                (tree);
 extern tree cp_walk_subtrees (tree*, int*, walk_tree_fn,
-				      void*, void*);
+				      void*, struct pointer_set_t*);
 extern int cp_cannot_inline_tree_fn (tree*);
 extern tree cp_add_pending_fn_decls (void*,tree);
 extern int cp_is_overload_p (tree);
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 36ff89b2679..18e3c0a057d 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -32,6 +32,7 @@ Boston, MA 02111-1307, USA.  */
 #include "tm.h"
 #include "obstack.h"
 #include "tree.h"
+#include "pointer-set.h"
 #include "flags.h"
 #include "cp-tree.h"
 #include "tree-inline.h"
@@ -113,7 +114,8 @@ static tree convert_nontype_argument (tree, tree);
 static tree convert_template_argument (tree, tree, tree,
 				       tsubst_flags_t, int, tree);
 static tree get_bindings_overload (tree, tree, tree);
-static int for_each_template_parm (tree, tree_fn_t, void*, htab_t);
+static int for_each_template_parm (tree, tree_fn_t, void*,
+				   struct pointer_set_t*);
 static tree build_template_parm_index (int, int, int, tree, tree);
 static int inline_needs_template_parms (tree);
 static void push_inline_template_parms_recursive (tree, int);
@@ -4683,7 +4685,7 @@ struct pair_fn_data
 {
   tree_fn_t fn;
   void *data;
-  htab_t visited;
+  struct pointer_set_t *visited;
 };
 
 /* Called from for_each_template_parm via walk_tree.  */
@@ -4865,7 +4867,8 @@ for_each_template_parm_r (tree *tp, int *walk_subtrees, void *d)
    considered to be the function which always returns 1.  */
 
 static int
-for_each_template_parm (tree t, tree_fn_t fn, void* data, htab_t visited)
+for_each_template_parm (tree t, tree_fn_t fn, void* data,
+			struct pointer_set_t *visited)
 {
   struct pair_fn_data pfd;
   int result;
@@ -4882,8 +4885,7 @@ for_each_template_parm (tree t, tree_fn_t fn, void* data, htab_t visited)
   if (visited)
     pfd.visited = visited;
   else
-    pfd.visited = htab_create (37, htab_hash_pointer, htab_eq_pointer, 
-			       NULL);
+    pfd.visited = pointer_set_create ();
   result = walk_tree (&t, 
 		      for_each_template_parm_r, 
 		      &pfd,
@@ -4891,7 +4893,10 @@ for_each_template_parm (tree t, tree_fn_t fn, void* data, htab_t visited)
 
   /* Clean up.  */
   if (!visited)
-    htab_delete (pfd.visited);
+    {
+      pointer_set_destroy (pfd.visited);
+      pfd.visited = 0;
+    }
 
   return result;
 }
diff --git a/gcc/cp/tree.c b/gcc/cp/tree.c
index b4ced9bc22c..134da23ffd5 100644
--- a/gcc/cp/tree.c
+++ b/gcc/cp/tree.c
@@ -1929,7 +1929,7 @@ cp_build_type_attribute_variant (tree type, tree attributes)
 
 tree
 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
-		  void *data, void *htab)
+		  void *data, struct pointer_set_t *pset)
 {
   enum tree_code code = TREE_CODE (*tp);
   location_t save_locus;
@@ -1938,7 +1938,7 @@ cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
 #define WALK_SUBTREE(NODE)				\
   do							\
     {							\
-      result = walk_tree (&(NODE), func, data, htab);	\
+      result = walk_tree (&(NODE), func, data, pset);	\
       if (result) goto out;				\
     }							\
   while (0)
diff --git a/gcc/java/ChangeLog b/gcc/java/ChangeLog
index d599add7f66..126041a0ffa 100644
--- a/gcc/java/ChangeLog
+++ b/gcc/java/ChangeLog
@@ -1,3 +1,8 @@
+2004-10-14  Matt Austern  <austern@apple.com>
+
+	* lang.c (java_tree_inlining_walk_subtrees): Last arg is struct
+	pointer_set_t* now.
+	
 2004-10-13  Tom Tromey  <tromey@redhat.com>
 
 	PR java/15578:
diff --git a/gcc/java/lang.c b/gcc/java/lang.c
index 3e4ba4933fc..eae51a2a689 100644
--- a/gcc/java/lang.c
+++ b/gcc/java/lang.c
@@ -58,7 +58,7 @@ static void put_decl_string (const char *, int);
 static void put_decl_node (tree);
 static void java_print_error_function (diagnostic_context *, const char *);
 static tree java_tree_inlining_walk_subtrees (tree *, int *, walk_tree_fn,
-					      void *, void *);
+					      void *, struct pointer_set_t *);
 static int merge_init_test_initialization (void * *, void *);
 static int inline_init_test_initialization (void * *, void *);
 static bool java_can_use_bit_fields_p (void);
@@ -706,7 +706,7 @@ java_tree_inlining_walk_subtrees (tree *tp ATTRIBUTE_UNUSED,
 				  int *subtrees ATTRIBUTE_UNUSED,
 				  walk_tree_fn func ATTRIBUTE_UNUSED,
 				  void *data ATTRIBUTE_UNUSED,
-				  void *htab ATTRIBUTE_UNUSED)
+				  struct pointer_set_t *pset ATTRIBUTE_UNUSED)
 {
   enum tree_code code;
   tree result;
@@ -714,7 +714,7 @@ java_tree_inlining_walk_subtrees (tree *tp ATTRIBUTE_UNUSED,
 #define WALK_SUBTREE(NODE)				\
   do							\
     {							\
-      result = walk_tree (&(NODE), func, data, htab);	\
+      result = walk_tree (&(NODE), func, data, pset);	\
       if (result)					\
 	return result;					\
     }							\
diff --git a/gcc/langhooks-def.h b/gcc/langhooks-def.h
index 8b57a0311ab..d036d84d481 100644
--- a/gcc/langhooks-def.h
+++ b/gcc/langhooks-def.h
@@ -73,7 +73,7 @@ extern size_t lhd_tree_size (enum tree_code);
 
 /* Declarations of default tree inlining hooks.  */
 extern tree lhd_tree_inlining_walk_subtrees (tree *, int *, walk_tree_fn,
-					     void *, void *);
+					     void *, struct pointer_set_t*);
 extern int lhd_tree_inlining_cannot_inline_tree_fn (tree *);
 extern int lhd_tree_inlining_disregard_inline_limits (tree);
 extern tree lhd_tree_inlining_add_pending_fn_decls (void *, tree);
diff --git a/gcc/langhooks.c b/gcc/langhooks.c
index 199c93e9b50..0cf31be7806 100644
--- a/gcc/langhooks.c
+++ b/gcc/langhooks.c
@@ -298,7 +298,7 @@ lhd_tree_inlining_walk_subtrees (tree *tp ATTRIBUTE_UNUSED,
 				 int *subtrees ATTRIBUTE_UNUSED,
 				 walk_tree_fn func ATTRIBUTE_UNUSED,
 				 void *data ATTRIBUTE_UNUSED,
-				 void *htab ATTRIBUTE_UNUSED)
+				 struct pointer_set_t *pset ATTRIBUTE_UNUSED)
 {
   return NULL_TREE;
 }
diff --git a/gcc/langhooks.h b/gcc/langhooks.h
index 43749a24e88..f57f14821ec 100644
--- a/gcc/langhooks.h
+++ b/gcc/langhooks.h
@@ -35,7 +35,7 @@ struct lang_hooks_for_tree_inlining
 {
   tree (*walk_subtrees) (tree *, int *,
 			 tree (*) (tree *, int *, void *),
-			 void *, void *);
+			 void *, struct pointer_set_t*);
   int (*cannot_inline_tree_fn) (tree *);
   int (*disregard_inline_limits) (tree);
   tree (*add_pending_fn_decls) (void *, tree);
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;
+}
diff --git a/gcc/pointer-set.h b/gcc/pointer-set.h
new file mode 100644
index 00000000000..65ac9ee4724
--- /dev/null
+++ b/gcc/pointer-set.h
@@ -0,0 +1,32 @@
+/* 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.  */
+
+#ifndef POINTER_SET_H
+#define POINTER_SET_H
+
+struct pointer_set_t;
+
+struct pointer_set_t *pointer_set_create (void);
+void pointer_set_destroy (struct pointer_set_t *pset);
+
+int pointer_set_contains (struct pointer_set_t *pset, void *p);
+int pointer_set_insert (struct pointer_set_t *pset, void *p);
+
+#endif  /* POINTER_SET_H  */
diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c
index 29de6704041..aa156c245dd 100644
--- a/gcc/tree-dfa.c
+++ b/gcc/tree-dfa.c
@@ -24,6 +24,7 @@ Boston, MA 02111-1307, USA.  */
 #include "coretypes.h"
 #include "tm.h"
 #include "hashtab.h"
+#include "pointer-set.h"
 #include "tree.h"
 #include "rtl.h"
 #include "tm_p.h"
@@ -759,7 +760,7 @@ debug_dfa_stats (void)
 static void
 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 {
-  htab_t htab;
+  struct pointer_set_t *pset;
   basic_block bb;
   block_stmt_iterator i;
 
@@ -769,13 +770,13 @@ collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
 
   /* Walk all the trees in the function counting references.  Start at
      basic block 0, but don't stop at block boundaries.  */
-  htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
+  pset = pointer_set_create ();
 
   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
-	       (void *) htab);
+	       pset);
 
-  htab_delete (htab);
+  pointer_set_destroy (pset);
 
   FOR_EACH_BB (bb)
     {
diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c
index 0583eb42942..0e2f85a7e8a 100644
--- a/gcc/tree-inline.c
+++ b/gcc/tree-inline.c
@@ -35,6 +35,7 @@ Boston, MA 02111-1307, USA.  */
 #include "integrate.h"
 #include "varray.h"
 #include "hashtab.h"
+#include "pointer-set.h"
 #include "splay-tree.h"
 #include "langhooks.h"
 #include "cgraph.h"
@@ -1877,7 +1878,7 @@ save_body (tree fn, tree *arg_copy, tree *sc_copy)
 #define WALK_SUBTREE(NODE)				\
   do							\
     {							\
-      result = walk_tree (&(NODE), func, data, htab);	\
+      result = walk_tree (&(NODE), func, data, pset);	\
       if (result)					\
 	return result;					\
     }							\
@@ -1888,7 +1889,8 @@ save_body (tree fn, tree *arg_copy, tree *sc_copy)
    value are as for walk_tree.  */
 
 static tree
-walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab)
+walk_type_fields (tree type, walk_tree_fn func, void *data,
+		  struct pointer_set_t *pset)
 {
   tree result = NULL_TREE;
 
@@ -1906,7 +1908,7 @@ walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab)
       if (POINTER_TYPE_P (TREE_TYPE (type))
 	  && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
 	  && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
-	  && !htab)
+	  && !pset)
 	{
 	  result = walk_tree_without_duplicates (&TREE_TYPE (type),
 						 func, data);
@@ -1971,13 +1973,12 @@ walk_type_fields (tree type, walk_tree_fn func, void *data, void *htab)
 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
    called with the DATA and the address of each sub-tree.  If FUNC returns a
    non-NULL value, the traversal is aborted, and the value returned by FUNC
-   is returned.  If HTAB is non-NULL it is used to record the nodes visited,
+   is returned.  If PSET is non-NULL it is used to record the nodes visited,
    and to avoid visiting a node more than once.  */
 
 tree
-walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
+walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
 {
-  htab_t htab = (htab_t) htab_;
   enum tree_code code;
   int walk_subtrees;
   tree result;
@@ -1995,17 +1996,10 @@ walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
   if (!*tp)
     return NULL_TREE;
 
-  if (htab)
-    {
-      void **slot;
-
-      /* Don't walk the same tree twice, if the user has requested
-         that we avoid doing so.  */
-      slot = htab_find_slot (htab, *tp, INSERT);
-      if (*slot)
-	return NULL_TREE;
-      *slot = *tp;
-    }
+  /* Don't walk the same tree twice, if the user has requested
+     that we avoid doing so.  */
+  if (pset && pointer_set_insert (pset, *tp))
+    return NULL_TREE;
 
   /* Call the function.  */
   walk_subtrees = 1;
@@ -2029,7 +2023,7 @@ walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
     }
 
   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
-						   data, htab);
+						   data, pset);
   if (result || ! walk_subtrees)
     return result;
 
@@ -2053,7 +2047,7 @@ walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
       if (result || !walk_subtrees)
 	return NULL_TREE;
 
-      result = walk_type_fields (*type_p, func, data, htab_);
+      result = walk_type_fields (*type_p, func, data, pset);
       if (result)
 	return result;
 
@@ -2124,7 +2118,7 @@ walk_tree (tree *tp, walk_tree_fn func, void *data, void *htab_)
   /* If this is a type, walk the needed fields in the type.  */
   else if (TYPE_P (*tp))
     {
-      result = walk_type_fields (*tp, func, data, htab_);
+      result = walk_type_fields (*tp, func, data, pset);
       if (result)
 	return result;
     }
@@ -2227,11 +2221,11 @@ tree
 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
 {
   tree result;
-  htab_t htab;
+  struct pointer_set_t *pset;
 
-  htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
-  result = walk_tree (tp, func, data, htab);
-  htab_delete (htab);
+  pset = pointer_set_create ();
+  result = walk_tree (tp, func, data, pset);
+  pointer_set_destroy (pset);
   return result;
 }
 
diff --git a/gcc/tree.h b/gcc/tree.h
index 7bab93d478e..15cd061a6a0 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -3790,10 +3790,14 @@ extern void dwarf2out_return_reg (const char *, unsigned);
 
 /* In tree-inline.c  */
 
+/* The type of a set of already-visited pointers.  Functions for creating
+   and manipulating it are declared in pointer-set.h */
+struct pointer_set_t;
+
 /* The type of a callback function for walking over tree structure.  */
 
 typedef tree (*walk_tree_fn) (tree *, int *, void *);
-extern tree walk_tree (tree*, walk_tree_fn, void*, void*);
+extern tree walk_tree (tree*, walk_tree_fn, void*, struct pointer_set_t*);
 extern tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);
 
 /* In tree-dump.c */