This is the mail archive of the
mailing list for the GCC project.
Re: c++/1687: Extreme compile time regression from 2.95.2
- To: Kelley Cook <kelley dot cook at home dot com>
- Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
- From: "Zack Weinberg" <zackw at Stanford dot EDU>
- Date: Tue, 6 Feb 2001 12:43:21 -0800
- Cc: gcc-gnats at gcc dot gnu dot org, gcc-bugs at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- References: <3A803B06.firstname.lastname@example.org> <20010206110230.D525@wolery.stanford.edu>
Following up to myself...
I hacked up a walk_expr_tree. It improves things by a bit: a 16-input
mux() goes from 1min to 30sec on my machine (give or take).
Unfortunately, the time taken is still O(3^N) in the number of
inputs. So that won't do.
Using the 'visit each node only once' mechanism of walk_tree
thoroughly squelches the performance problem. (One can't use
walk_tree_without_duplicates blindly - slightly more cleverness is
required. It's still simple.) We get sub-second compile time all the
way up to -O2 and 32 input mux().
Before (17 inputs):
8.29 91.80 7.62 215233608 0.00 0.00 expand_call_inline
After (17 inputs):
0.00 0.14 0.00 147 0.00 0.00 expand_call_inline
After (32 inputs):
0.00 0.15 0.00 269 0.00 0.00 expand_call_inline
HOWEVER: I am not certain that the change is correct. Suppose that a
function A is a candidate for inlining, and it's called twice from the
same function B. If the two call_expr nodes are shared, we won't
inline both calls. There may be other problems as well.
Patch follows. Commentary from C++ team appreciated. Will bootstrap
* optimize.c: Include hashtab.h.
(struct inline_data): Add tree_pruner field.
(expand_call_inline, expand_calls_inline): Call walk_tree with
id->tree_pruner for fourth argument, putting it into
(optimize_function): Create and destroy a hash table for
duplicate pruning, store it in id.tree_pruner.
--- cp/optimize.c 2001/01/28 14:04:19 1.50
+++ cp/optimize.c 2001/02/06 20:40:33
@@ -28,6 +28,7 @@ Software Foundation, 59 Temple Place - S
/* To Do:
@@ -62,6 +63,10 @@ typedef struct inline_data
/* A stack of the TARGET_EXPRs that we are currently processing. */
+ /* Hash table used to prevent walk_tree from visiting the same node
+ umpteen million times. */
+ htab_t tree_pruner;
/* Prototypes. */
@@ -655,7 +660,7 @@ expand_call_inline (tp, walk_subtrees, d
if (i == 2)
walk_tree (&TREE_OPERAND (*tp, i), expand_call_inline, data,
if (i == 2)
@@ -810,8 +815,12 @@ expand_calls_inline (tp, 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. */
@@ -863,11 +872,14 @@ optimize_function (fn)
/* Replace all calls to inline functions with the bodies of those
+ 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);
/* Undo the call to ggc_push_context above. */