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.

From-SVN: r89062

5 files changed, 23 insertions, 10 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 270a4eb..bb8678e 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 27ef4f2..891d271 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 6f777b1..2350ab0 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 36ff89b..18e3c0a 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 b4ced9b..134da23 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)