Makefile.in (CXX_TREE_H): Add dependency on HTAB_H.

	* Makefile.in (CXX_TREE_H): Add dependency on HTAB_H.
	(pt.o): Remove dependency on HTAB_H.
	* cp-tree.h: Include hashtab.h.
	(walk_tree): Change prototype.
	(walk_tree_without_duplicates): New function.
	* decl.c (check_default_argument): Use it.
	* optimize.c (remap_decl): Adjust calls to walk_tree.
	(copy_body): Likewise.
	(expand_calls_inline): Likewise.
	(calls_setjmp_p): Use walk_tree_without_duplicates.
	* pt.c: Don't include hashtab.h.
	(for_each_template_parm): Use walk_tree_without_duplicates.
	* semantics.c (finish-stmt_tree): Likewise.
	(expand_body): Likewise.
	* tree.c (walk_tree): Add additional parameter.
	(walk_tree_without_duplicates): New function.
	(count_trees): Use it.
	(verify_stmt_tree): Adjust call to walk_tree.
	(find_tree): Use walk_tree_without_duplicates.
	(no_linkage_check): Likewise.
	(break_out_target_exprs): Adjust call to walk_tree.
	(cp_unsave): Likewise.

From-SVN: r36155

8 files changed, 103 insertions, 34 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index d4388fc..32b7c08 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,28 @@
+2000-09-05  Mark Mitchell  <mark@codesourcery.com>
+
+	* Makefile.in (CXX_TREE_H): Add dependency on HTAB_H.
+	(pt.o): Remove dependency on HTAB_H.
+	* cp-tree.h: Include hashtab.h.
+	(walk_tree): Change prototype.
+	(walk_tree_without_duplicates): New function.
+	* decl.c (check_default_argument): Use it.
+	* optimize.c (remap_decl): Adjust calls to walk_tree.
+	(copy_body): Likewise.
+	(expand_calls_inline): Likewise.
+	(calls_setjmp_p): Use walk_tree_without_duplicates.
+	* pt.c: Don't include hashtab.h.
+	(for_each_template_parm): Use walk_tree_without_duplicates.
+	* semantics.c (finish-stmt_tree): Likewise.
+	(expand_body): Likewise.
+	* tree.c (walk_tree): Add additional parameter.
+	(walk_tree_without_duplicates): New function.
+	(count_trees): Use it.
+	(verify_stmt_tree): Adjust call to walk_tree.
+	(find_tree): Use walk_tree_without_duplicates.
+	(no_linkage_check): Likewise.
+	(break_out_target_exprs): Adjust call to walk_tree.
+	(cp_unsave): Likewise.
+
 2000-09-04  Kriang Lerdsuwanakij  <lerdsuwa@users.sourceforge.net>
 
 	* cp-tree.def (BOUND_TEMPLATE_TEMPLATE_PARM): New tree code.
diff --git a/gcc/cp/Makefile.in b/gcc/cp/Makefile.in
index 9a1f39b..025ae06 100644
--- a/gcc/cp/Makefile.in
+++ b/gcc/cp/Makefile.in
@@ -208,7 +208,7 @@ TREE_H = $(srcdir)/../tree.h $(srcdir)/../real.h $(srcdir)/../tree.def \
 CXX_TREE_H = $(TREE_H) cp-tree.h $(srcdir)/../c-common.h cp-tree.def \
 	$(srcdir)/../c-common.def $(srcdir)/../function.h $(srcdir)/../varray.h \
 	$(srcdir)/../../include/splay-tree.h \
-	$(srcdir)/../system.h $(CONFIG_H)
+	$(srcdir)/../system.h $(CONFIG_H) $(HTAB_H)
 PARSE_H = $(srcdir)/parse.h
 PARSE_C = $(srcdir)/parse.c
 EXPR_H = $(srcdir)/../expr.h ../insn-codes.h
@@ -299,7 +299,7 @@ xref.o : xref.c $(CXX_TREE_H) $(srcdir)/../input.h \
   $(srcdir)/../toplev.h
 pt.o : pt.c $(CXX_TREE_H) decl.h $(PARSE_H) lex.h \
   $(srcdir)/../toplev.h $(GGC_H) $(RTL_H) \
-  $(srcdir)/../except.h $(HTAB_H)
+  $(srcdir)/../except.h
 error.o : error.c $(CXX_TREE_H) \
   $(srcdir)/../toplev.h $(srcdir)/../diagnostic.h
 errfn.o : errfn.c $(CXX_TREE_H) \
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 2da46de..44c7168 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -21,6 +21,7 @@ the Free Software Foundation, 59 Temple Place - Suite 330,
 Boston, MA 02111-1307, USA.  */
 
 #include "function.h"
+#include "hashtab.h"
 #include "splay-tree.h"
 #include "varray.h"
 
@@ -4535,7 +4536,13 @@ extern tree build_dummy_object			PARAMS ((tree));
 extern tree maybe_dummy_object			PARAMS ((tree, tree *));
 extern int is_dummy_object			PARAMS ((tree));
 typedef tree (*walk_tree_fn)                    PARAMS ((tree *, int *, void *));
-extern tree walk_tree                           PARAMS ((tree *, walk_tree_fn, void *));
+extern tree walk_tree                           PARAMS ((tree *,
+							 walk_tree_fn,
+							 void *, 
+							 htab_t));
+extern tree walk_tree_without_duplicates        PARAMS ((tree *,
+							 walk_tree_fn,
+							 void *));
 extern tree copy_tree_r                         PARAMS ((tree *, int *, void *));
 extern int cp_valid_lang_attribute		PARAMS ((tree, tree, tree, tree));
 extern tree make_ptrmem_cst                     PARAMS ((tree, tree));
diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c
index 664d125..63c2ea8 100644
--- a/gcc/cp/decl.c
+++ b/gcc/cp/decl.c
@@ -11946,7 +11946,8 @@ check_default_argument (decl, arg)
 
      The keyword `this' shall not be used in a default argument of a
      member function.  */
-  var = walk_tree (&arg, local_variable_p_walkfn, NULL);
+  var = walk_tree_without_duplicates (&arg, local_variable_p_walkfn, 
+				      NULL);
   if (var)
     {
       cp_error ("default argument `%E' uses local variable `%D'",
diff --git a/gcc/cp/optimize.c b/gcc/cp/optimize.c
index c9898b8..d80877c 100644
--- a/gcc/cp/optimize.c
+++ b/gcc/cp/optimize.c
@@ -109,8 +109,8 @@ remap_decl (decl, id)
       /* The decl T could be a dynamic array or other variable size type,
 	 in which case some fields need to be remapped because they may
 	 contain SAVE_EXPRs.  */
-      walk_tree (&DECL_SIZE (t), copy_body_r, id);
-      walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id);
+      walk_tree (&DECL_SIZE (t), copy_body_r, id, NULL);
+      walk_tree (&DECL_SIZE_UNIT (t), copy_body_r, id, NULL);
       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == ARRAY_TYPE
 	  && TYPE_DOMAIN (TREE_TYPE (t)))
 	{
@@ -118,7 +118,7 @@ remap_decl (decl, id)
 	  TYPE_DOMAIN (TREE_TYPE (t)) 
 	    = copy_node (TYPE_DOMAIN (TREE_TYPE (t)));
 	  walk_tree (&TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (t))),
-		     copy_body_r, id);
+		     copy_body_r, id, NULL);
 	}
 
       /* Remember it, so that if we encounter this local entity
@@ -356,7 +356,7 @@ copy_body (id)
   tree body;
 
   body = DECL_SAVED_TREE (VARRAY_TOP_TREE (id->fns));
-  walk_tree (&body, copy_body_r, id);
+  walk_tree (&body, copy_body_r, id, NULL);
 
   return body;
 }
@@ -636,7 +636,8 @@ expand_call_inline (tp, walk_subtrees, data)
 	{
 	  if (i == 2)
 	    ++id->in_target_cleanup_p;
-	  walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data);
+	  walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
+		     NULL);
 	  if (i == 2)
 	    --id->in_target_cleanup_p;
 	}
@@ -792,7 +793,7 @@ expand_calls_inline (tp, id)
 {
   /* Search through *TP, replacing all calls to inline functions by
      appropriate equivalents.  */
-  walk_tree (tp, expand_call_inline, id);
+  walk_tree (tp, expand_call_inline, id, NULL);
 }
 
 /* Optimize the body of FN.  */
@@ -879,8 +880,9 @@ int
 calls_setjmp_p (fn)
      tree fn;
 {
-  return (walk_tree (&DECL_SAVED_TREE (fn), calls_setjmp_r, NULL) 
-	  != NULL_TREE);
+  return walk_tree_without_duplicates (&DECL_SAVED_TREE (fn), 
+				       calls_setjmp_r, 
+				       NULL) != NULL_TREE;
 }
 
 /* FN is a function that has a complete body.  Clone the body as
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index cddf0f9..b50f79f 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -43,7 +43,6 @@ Boston, MA 02111-1307, USA.  */
 #include "rtl.h"
 #include "defaults.h"
 #include "ggc.h"
-#include "hashtab.h"
 #include "timevar.h"
 
 /* The type of functions taking a tree, and some additional data, and
@@ -4276,7 +4275,9 @@ for_each_template_parm (t, fn, data)
   pfd.data = data;
 
   /* Walk the tree.  */
-  return walk_tree (&t, for_each_template_parm_r, &pfd) != NULL_TREE;
+  return walk_tree_without_duplicates (&t, 
+				       for_each_template_parm_r, 
+				       &pfd) != NULL_TREE;
 }
 
 int
diff --git a/gcc/cp/semantics.c b/gcc/cp/semantics.c
index 6584a42..7c46d1d 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -2324,7 +2324,7 @@ finish_stmt_tree (t)
   /* Remove unused decls from the stmt tree.  walk_tree messes with
      the line number, so save/restore it.  */
   old_lineno = lineno;
-  walk_tree (t, prune_unused_decls, 0);
+  walk_tree_without_duplicates (t, prune_unused_decls, NULL);
   lineno = old_lineno;
 
   if (cfun)
@@ -2639,7 +2639,9 @@ expand_body (fn)
     }
 
   /* Replace AGGR_INIT_EXPRs with appropriate CALL_EXPRs.  */
-  walk_tree (&DECL_SAVED_TREE (fn), simplify_aggr_init_exprs_r, NULL);
+  walk_tree_without_duplicates (&DECL_SAVED_TREE (fn),
+				simplify_aggr_init_exprs_r,
+				NULL);
 
   /* If this is a constructor or destructor body, we have to clone it
      under the new ABI.  */
diff --git a/gcc/cp/tree.c b/gcc/cp/tree.c
index be2459a..0c51f54 100644
--- a/gcc/cp/tree.c
+++ b/gcc/cp/tree.c
@@ -26,7 +26,6 @@ Boston, MA 02111-1307, USA.  */
 #include "tree.h"
 #include "cp-tree.h"
 #include "flags.h"
-#include "hashtab.h"
 #include "rtl.h"
 #include "toplev.h"
 #include "ggc.h"
@@ -1224,31 +1223,45 @@ copy_template_template_parm (t, newargs)
 /* 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.  */
+   value returned by FUNC is returned.  The FLAGS govern the way in
+   which nodes are walked.  If HTAB is non-NULL it is used to record
+   the nodes visited, and to avoid visiting a node more than once.  */
 
 tree 
-walk_tree (tp, func, data)
+walk_tree (tp, func, data, htab)
      tree *tp;
      walk_tree_fn func;
      void *data;
+     htab_t htab;
 {
   enum tree_code code;
   int walk_subtrees;
   tree result;
   
-#define WALK_SUBTREE(NODE)			\
-  do						\
-    {						\
-      result = walk_tree (&(NODE), func, data);	\
-      if (result)				\
-	return result;				\
-    }						\
+#define WALK_SUBTREE(NODE)				\
+  do							\
+    {							\
+      result = walk_tree (&(NODE), func, data, htab);	\
+      if (result)					\
+	return result;					\
+    }							\
   while (0)
 
   /* Skip empty subtrees.  */
   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. */
+    if (htab_find (htab, *tp))
+      return NULL_TREE;
+    /* If we haven't already seen this node, add it to the table. */
+    slot = htab_find_slot (htab, *tp, INSERT);
+    *slot = *tp;
+  }
+
   /* Call the function.  */
   walk_subtrees = 1;
   result = (*func) (tp, &walk_subtrees, data);
@@ -1423,6 +1436,24 @@ walk_tree (tp, func, data)
 #undef WALK_SUBTREE
 }
 
+/* Like walk_tree, but does not walk duplicate nodes more than 
+   once.  */
+
+tree 
+walk_tree_without_duplicates (tp, func, data)
+     tree *tp;
+     walk_tree_fn func;
+     void *data;
+{
+  tree result;
+  htab_t htab;
+
+  htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+  result = walk_tree (tp, func, data, htab);
+  htab_delete (htab);
+  return result;
+}
+
 /* Called from count_trees via walk_tree.  */
 
 static tree
@@ -1443,7 +1474,7 @@ count_trees (t)
      tree t;
 {
   int n_trees = 0;
-  walk_tree (&t, count_trees_r, &n_trees);
+  walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
   return n_trees;
 }  
 
@@ -1483,7 +1514,7 @@ verify_stmt_tree (t)
 {
   htab_t statements;
   statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
-  walk_tree (&t, verify_stmt_tree_r, &statements);
+  walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
   htab_delete (statements);
 }
 
@@ -1508,7 +1539,7 @@ find_tree (t, x)
      tree t;
      tree x;
 {
-  return walk_tree (&t, find_tree_r, x);
+  return walk_tree_without_duplicates (&t, find_tree_r, x);
 }
 
 /* Passed to walk_tree.  Checks for the use of types with no linkage.  */
@@ -1541,7 +1572,7 @@ no_linkage_check (t)
   if (processing_template_decl)
     return NULL_TREE;
 
-  t = walk_tree (&t, no_linkage_helper, NULL);
+  t = walk_tree_without_duplicates (&t, no_linkage_helper, NULL);
   if (t != error_mark_node)
     return t;
   return NULL_TREE;
@@ -1736,8 +1767,8 @@ break_out_target_exprs (t)
     target_remap = splay_tree_new (splay_tree_compare_pointers, 
 				   /*splay_tree_delete_key_fn=*/NULL, 
 				   /*splay_tree_delete_value_fn=*/NULL);
-  walk_tree (&t, bot_manip, target_remap);
-  walk_tree (&t, bot_replace, target_remap);
+  walk_tree (&t, bot_manip, target_remap, NULL);
+  walk_tree (&t, bot_replace, target_remap, NULL);
 
   if (!--target_remap_count)
     {
@@ -2520,10 +2551,10 @@ cp_unsave (tp)
   st = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
 
   /* Walk the tree once figuring out what needs to be remapped.  */
-  walk_tree (tp, mark_local_for_remap_r, st);
+  walk_tree (tp, mark_local_for_remap_r, st, NULL);
 
   /* Walk the tree again, copying, remapping, and unsaving.  */
-  walk_tree (tp, cp_unsave_r, st);
+  walk_tree (tp, cp_unsave_r, st, NULL);
 
   /* Clean up.  */
   splay_tree_delete (st);