From 11fe225ab2dbce69a345f63f4e608ab837a07703 Mon Sep 17 00:00:00 2001 From: Zack Weinberg Date: Wed, 25 Apr 2001 00:07:07 +0000 Subject: [PATCH] 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 --- gcc/cp/ChangeLog | 34 +++++---- gcc/cp/optimize.c | 17 ++++- gcc/testsuite/ChangeLog | 4 + gcc/testsuite/g++.old-deja/g++.other/perf1.C | 78 ++++++++++++++++++++ 4 files changed, 117 insertions(+), 16 deletions(-) create mode 100644 gcc/testsuite/g++.old-deja/g++.other/perf1.C diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog index 69a674d954b..618ba0d7b41 100644 --- a/gcc/cp/ChangeLog +++ b/gcc/cp/ChangeLog @@ -1,3 +1,11 @@ +2001-04-24 Zack Weinberg + + * 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 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 * 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 * 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 * 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 * lang-specs.h: Add __DEPRECATED. @@ -251,7 +259,7 @@ Thu Apr 5 16:54:29 2001 J"orn Rennecke 2001-04-03 Mark Mitchell - * 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 (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 rest_of_compilation. Clear DECL_RTL for local variables afterwards. (clear_decl_rtl): New function. - + 2001-03-26 Nathan Sidwell Implement DR 209 @@ -444,7 +452,7 @@ Thu Apr 5 16:54:29 2001 J"orn Rennecke * 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 * 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 Correct semantics restrictions checking in throw-expression. @@ -612,7 +620,7 @@ Thu Apr 5 16:54:29 2001 J"orn Rennecke (expand_body): Likewise. (genrtl_finish_function): Likewise. * tree.c (cp_tree_equal): Likewise. - + 2001-03-12 Nathan Sidwell * call.c (convert_like_real): Add extra semantics to INNER @@ -713,7 +721,7 @@ Thu Apr 5 16:54:29 2001 J"orn Rennecke (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 2001-02-26 Nathan Sidwell * except.c (call_eh_info): Cleanup generation of cp_eh_info struct. - + * decl.c (mark_inlined_fns): Prototype. 2001-02-22 Mark Mitchell diff --git a/gcc/cp/optimize.c b/gcc/cp/optimize.c index 2ed10ea0c34..096bd5d0d64 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)) diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index b93b67523ab..39abc4e4905 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2001-04-24 Zack Weinberg + + * g++.old-deja/g++.other/perf1.C: New test. + 2001-04-24 Nathan Sidwell * gcc.dg/c99-func-2.c: Remove xfail. diff --git a/gcc/testsuite/g++.old-deja/g++.other/perf1.C b/gcc/testsuite/g++.old-deja/g++.other/perf1.C new file mode 100644 index 00000000000..3f898117511 --- /dev/null +++ b/gcc/testsuite/g++.old-deja/g++.other/perf1.C @@ -0,0 +1,78 @@ +// Build don't link: + +// Test of severe performance regression from 2.95. This code generates +// a heavily self-referential tree which caused the inliner to take +// O(3**N) time to scan it for function calls. +// Reported by Kelley Cook . PR c++/1687. + +bool in0 ; +bool in1 ; +bool in2 ; +bool in3 ; +bool in4 ; +bool in5 ; +bool in6 ; +bool in7 ; +bool in8 ; +bool in9 ; +bool in10; +bool in11; +bool in12; +bool in13; +bool in14; +bool in15; +bool in16; +bool in17; +bool in18; +bool in19; +bool in20; +bool in21; +bool in22; +bool in23; +bool in24; +bool in25; +bool in26; +bool in27; +bool in28; +bool in29; +bool in30; +bool in31; +unsigned long output; + +void mux(void) +{ + output = + (in0 ? 0x00000001 : 0) | + (in1 ? 0x00000002 : 0) | + (in2 ? 0x00000004 : 0) | + (in3 ? 0x00000008 : 0) | + (in4 ? 0x00000010 : 0) | + (in5 ? 0x00000020 : 0) | + (in6 ? 0x00000040 : 0) | + (in7 ? 0x00000080 : 0) | + (in8 ? 0x00000100 : 0) | + (in9 ? 0x00000200 : 0) | + (in10 ? 0x00000400 : 0) | + (in11 ? 0x00000800 : 0) | + (in12 ? 0x00001000 : 0) | + (in13 ? 0x00002000 : 0) | + (in14 ? 0x00004000 : 0) | + (in15 ? 0x00008000 : 0) | + (in16 ? 0x00010000 : 0) | + (in17 ? 0x00020000 : 0) | + (in18 ? 0x00040000 : 0) | + (in19 ? 0x00080000 : 0) | + (in20 ? 0x00100000 : 0) | + (in21 ? 0x00200000 : 0) | + (in22 ? 0x00400000 : 0) | + (in23 ? 0x00800000 : 0) | + (in24 ? 0x01000000 : 0) | + (in25 ? 0x02000000 : 0) | + (in26 ? 0x04000000 : 0) | + (in27 ? 0x08000000 : 0) | + (in28 ? 0x10000000 : 0) | + (in29 ? 0x20000000 : 0) | + (in30 ? 0x40000000 : 0) | + (in31 ? 0x80000000 : 0) ; +} + -- 2.30.2