From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Zack Weinberg" To: nobody@gcc.gnu.org Cc: gcc-prs@gcc.gnu.org Subject: Re: c++/1687: Extreme compile time regression from 2.95.2 Date: Sun, 01 Apr 2001 00:00:00 -0000 Message-id: <20010206204600.15154.qmail@sourceware.cygnus.com> X-SW-Source: 2001-q1/msg01003.html List-Id: The following reply was made to PR c++/1687; it has been noted by GNATS. From: "Zack Weinberg" To: Kelley Cook Cc: gcc-gnats@gcc.gnu.org, gcc-bugs@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: Re: c++/1687: Extreme compile time regression from 2.95.2 Date: Tue, 6 Feb 2001 12:43:21 -0800 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 and report. zw * 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 no-duplicates mode. (optimize_function): Create and destroy a hash table for duplicate pruning, store it in id.tree_pruner. =================================================================== Index: cp/optimize.c --- 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 #include "input.h" #include "integrate.h" #include "varray.h" +#include "hashtab.h" /* To Do: @@ -62,6 +63,10 @@ typedef struct inline_data int in_target_cleanup_p; /* A stack of the TARGET_EXPRs that we are currently processing. */ varray_type target_exprs; + + /* Hash table used to prevent walk_tree from visiting the same node + umpteen million times. */ + htab_t tree_pruner; } inline_data; /* Prototypes. */ @@ -655,7 +660,7 @@ expand_call_inline (tp, walk_subtrees, d 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; } @@ -810,8 +815,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. */ @@ -863,11 +872,14 @@ 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. */ VARRAY_FREE (id.fns); VARRAY_FREE (id.target_exprs); + htab_delete (id.tree_pruner); } /* Undo the call to ggc_push_context above. */ >>From gdr@gcc.gnu.org Sun Apr 01 00:00:00 2001 From: gdr@gcc.gnu.org To: gdr@gcc.gnu.org Cc: gcc-prs@gcc.gnu.org Subject: Re: libstdc++/1767 Date: Sun, 01 Apr 2001 00:00:00 -0000 Message-id: <20010125123601.5206.qmail@sourceware.cygnus.com> X-SW-Source: 2001-q1/msg00710.html Content-length: 795 The following reply was made to PR libstdc++/1767; it has been noted by GNATS. From: gdr@gcc.gnu.org To: gcc-gnats@gcc.gnu.org, gdr@gcc.gnu.org, m.duflot@ulg.ac.be, nobody@gcc.gnu.org Cc: Subject: Re: libstdc++/1767 Date: 25 Jan 2001 12:26:31 -0000 Synopsis: bug with std::deque::const_iterator::operator->() Responsible-Changed-From-To: unassigned->gdr Responsible-Changed-By: gdr Responsible-Changed-When: Thu Jan 25 04:26:31 2001 Responsible-Changed-Why: Analyzed State-Changed-From-To: open->closed State-Changed-By: gdr State-Changed-When: Thu Jan 25 04:26:31 2001 State-Changed-Why: This bug is fixed in V3 (after the last merge from SGI-STL) so it is likely to be fixed in GCC-3.0 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view&pr=1767&database=gcc >>From rodrigc@mediaone.net Sun Apr 01 00:00:00 2001 From: Craig Rodrigues To: nobody@gcc.gnu.org Cc: gcc-prs@gcc.gnu.org Subject: Re: c++/1709 Date: Sun, 01 Apr 2001 00:00:00 -0000 Message-id: <20010210190600.10563.qmail@sourceware.cygnus.com> X-SW-Source: 2001-q1/msg01115.html Content-length: 572 The following reply was made to PR c++/1709; it has been noted by GNATS. From: Craig Rodrigues To: rodrigc@mediaone.net, gcc-gnats@gcc.gnu.org, nobody@gcc.gnu.org Cc: Subject: Re: c++/1709 Date: Sat, 10 Feb 2001 14:00:04 -0500 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view&pr=1709&database=gcc If I change the -O3 flag to -O2 the compiler crash goes away. There is a bug with -O3. I tested with this gcc version: gcc version 2.97 20010210 (experimental) -- Craig Rodrigues http://www.gis.net/~craigr rodrigc@mediaone.net