optimize.c: Include hashtab.h.

	* cp/optimize.c: Include hashtab.h.
	(struct inline_data): Add tree_pruner.
	(expand_call_inline, expand_calls_inline): Use it when calling
	walk_tree.
	(optimize_function): Initialize and free tree_pruner.

	* g++.old-deja/g++.other/perf1.C: New test.

From-SVN: r41525

2 files changed, 35 insertions, 16 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 69a674d..618ba0d 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,11 @@
+2001-04-24  Zack Weinberg  <zackw@stanford.edu>
+
+	* cp/optimize.c: Include hashtab.h.
+	(struct inline_data): Add tree_pruner.
+	(expand_call_inline, expand_calls_inline): Use it when calling
+	walk_tree.
+	(optimize_function): Initialize and free tree_pruner.
+
 2001-04-24  Nathan Sidwell <nathan@codesourcery.com>
 
 	Lazy __FUNCTION__ generation.
@@ -54,7 +62,7 @@
 	* cp-tree.h (finish_enum): Change prototype.
 	* decl.c (finish_enum): Reorganize.
 	* parse.y (structsp): Adjust calls to finish_enum.
-	
+
 2001-04-20  Nathan Sidwell  <nathan@codesourcery.com>
 
 	* tree.c (cp_tree_equal): Adjust final switch formatting. Add
@@ -99,7 +107,7 @@
 	* mangle.c (mangle_decl_string): Don't mangle the names of
 	variables declared with C language linkage.
 	* semantics.c (finish_member_declaration): Use SET_DECL_LANGUAGE.
-	
+
 2001-04-18  John David Anglin  <dave@hiauly1.hia.nrc.ca>
 
 	* semantics.c (simplify_aggr_init_exprs_r): Don't restore
@@ -127,7 +135,7 @@
 	(expand_ptrmemfunc_cst): Remove idx and delta2 parameters.
 	(delta2_from_ptrmemfunc): Remove.
 	(pfn_from_ptrmemfunc): Adjust call to expand_ptrmemfunc_cst.
-	
+
 2001-04-12  Jason Merrill  <jason_merrill@redhat.com>
 
 	* cp-tree.h (decl_namespace_list): New macro.
@@ -140,7 +148,7 @@
 
 	* cp-tree.h (warn_return_type, yylex): Delete redundant
 	declarations.
-	
+
 	* decl.c (current_class_depth, global_namespace): Likewise.
 
 	* decl2.c (current_class_depth, flag_gnu_xref): Likewise
@@ -223,7 +231,7 @@
 	(import_export_decl): Likewise.
 	* method.c (implicitly_declare_fn): Likewise.
 	* optimize.c (maybe_clone_body): Likewise.
-	
+
 2001-04-05  Benjamin Kosnik  <bkoz@redhat.com>
 
 	* lang-specs.h: Add __DEPRECATED.
@@ -251,7 +259,7 @@ Thu Apr  5 16:54:29 2001  J"orn Rennecke <amylaar@redhat.com>
 
 2001-04-03  Mark Mitchell  <mark@codesourcery.com>
 
-	* decl2.c (import_export_decl): Don't call import_export_class 
+	* decl2.c (import_export_decl): Don't call import_export_class
 	when processing an inline member function.
 	* semantics.c (expand_body): Call import_export_decl before
 	emitting inline functions.
@@ -267,7 +275,7 @@ Thu Apr  5 16:54:29 2001  J"orn Rennecke <amylaar@redhat.com>
 	(struct cp_language_function): Rename x_eh_spec_try_block
 	to x_eh_spec_block.
 	(EH_SPEC_STMTS, EH_SPEC_RAISES): New.
-	* decl.c (current_binding_level): If no current function 
+	* decl.c (current_binding_level): If no current function
 	bindings, revert to scope_chain.
 	(initialize_predefined_identifiers): Remove __cp_push_exception.
 	(store_parm_decls): Use begin_eh_spec_block.
@@ -374,7 +382,7 @@ Thu Apr  5 16:54:29 2001  J"orn Rennecke <amylaar@redhat.com>
 	rest_of_compilation.  Clear DECL_RTL for local variables
 	afterwards.
 	(clear_decl_rtl): New function.
-		
+
 2001-03-26  Nathan Sidwell  <nathan@codesourcery.com>
 
 	Implement DR 209
@@ -444,7 +452,7 @@ Thu Apr  5 16:54:29 2001  J"orn Rennecke <amylaar@redhat.com>
 	* tree.c (cp_valid_lang_attribute): Handle "java_interface" attribute
 	by setting TYPE_JAVA_INTERFACE.
 	* call.c (java_iface_lookup_fn): New static.
-	(build_over_call): If calling a method declared in a 
+	(build_over_call): If calling a method declared in a
 	TYPE_JAVA_INTERFACE, call build_java_interface_fn_ref to generate the
 	expression which resolves the function address.
 	(build_java_interface_fn_ref): New function.
@@ -577,7 +585,7 @@ Thu Apr  5 16:54:29 2001  J"orn Rennecke <amylaar@redhat.com>
 	* search.c (looup_field_1): Likewise.
 	* semantics.c (finish_named_return_value): Likewise.
 	* tree.c (init_tree): Set lang_set_decl_assembler_name.
-	
+
 2001-03-15  Gabriel Dos Reis  <gdr@codesourcery.com>
 
 	Correct semantics restrictions checking in throw-expression.
@@ -612,7 +620,7 @@ Thu Apr  5 16:54:29 2001  J"orn Rennecke <amylaar@redhat.com>
 	(expand_body): Likewise.
 	(genrtl_finish_function): Likewise.
 	* tree.c (cp_tree_equal): Likewise.
-	
+
 2001-03-12  Nathan Sidwell  <nathan@codesourcery.com>
 
 	* call.c (convert_like_real): Add extra semantics to INNER
@@ -713,7 +721,7 @@ Thu Apr  5 16:54:29 2001  J"orn Rennecke <amylaar@redhat.com>
 	(build_rtt_vtbl_entries): Lose RTTI_BINFO parameter.
 	(get_matching_base): Remove.
 	(get_original_base): New function.
-	(build_vtbl_initializer): Initialize vid.rtti_binfo. 
+	(build_vtbl_initializer): Initialize vid.rtti_binfo.
 	Use a virtual thunk for a ctor vtable with an index
 	(add_vcall_offset_vtbl_entries_1): Check if binfo has lost a
 	primary base within a constructor vtable. Only set
@@ -729,7 +737,7 @@ Thu Apr  5 16:54:29 2001  J"orn Rennecke <amylaar@redhat.com>
 2001-02-26  Nathan Sidwell  <nathan@codesourcery.com>
 
 	* except.c (call_eh_info): Cleanup generation of cp_eh_info struct.
-	
+
 	* decl.c (mark_inlined_fns): Prototype.
 
 2001-02-22  Mark Mitchell  <mark@codesourcery.com>
diff --git a/gcc/cp/optimize.c b/gcc/cp/optimize.c
index 2ed10ea..096bd5d 100644
--- a/gcc/cp/optimize.c
+++ b/gcc/cp/optimize.c
@@ -31,6 +31,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "varray.h"
 #include "ggc.h"
 #include "params.h"
+#include "hashtab.h"
 
 /* To Do:
 
@@ -80,6 +81,9 @@ typedef struct inline_data
      distinguish between those two situations.  This flag is true nif
      we are cloning, rather than inlining.  */
   bool cloning_p;
+  /* Hash table used to prevent walk_tree from visiting the same node
+     umpteen million times.  */
+  htab_t tree_pruner;
 } inline_data;
 
 /* Prototypes.  */
@@ -706,7 +710,7 @@ 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,
-		     NULL);
+		     id->tree_pruner);
 	  if (i == 2)
 	    --id->in_target_cleanup_p;
 	}
@@ -889,8 +893,12 @@ expand_calls_inline (tp, id)
      inline_data *id;
 {
   /* Search through *TP, replacing all calls to inline functions by
-     appropriate equivalents.  */
-  walk_tree (tp, expand_call_inline, id, NULL);
+     appropriate equivalents.  Use walk_tree in no-duplicates mode
+     to avoid exponential time complexity.  (We can't just use
+     walk_tree_without_duplicates, because of the special TARGET_EXPR
+     handling in expand_calls.  The hash table is set up in
+     optimize_function.  */
+  walk_tree (tp, expand_call_inline, id, id->tree_pruner);
 }
 
 /* Optimize the body of FN.  */
@@ -949,9 +957,12 @@ optimize_function (fn)
 
       /* Replace all calls to inline functions with the bodies of those
 	 functions.  */
+      id.tree_pruner = htab_create (37, htab_hash_pointer,
+				    htab_eq_pointer, NULL);
       expand_calls_inline (&DECL_SAVED_TREE (fn), &id);
 
       /* Clean up.  */
+      htab_delete (id.tree_pruner);
       VARRAY_FREE (id.fns);
       VARRAY_FREE (id.target_exprs);
       if (DECL_LANG_SPECIFIC (fn))