Re: c++/1687: Extreme compile time regression from 2.95.2

["Zack Weinberg" <zackw@Stanford.EDU>]

The following reply was made to PR c++/1687; it has been noted by GNATS.

From: "Zack Weinberg" <zackw@Stanford.EDU>
To: Kelley Cook <kelley.cook@home.com>
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<T>::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 <rodrigc@mediaone.net>
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 <rodrigc@mediaone.net>
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