Bug 1687 - [3.4 regression] Exponential time behavior with -O -finline-functions (compile time regression from 3.2, 3.3)
Summary: [3.4 regression] Exponential time behavior with -O -finline-functions (compil...
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: c (show other bugs)
Version: 3.4.0
: P1 normal
Target Milestone: 3.4.0
Assignee: Steven Bosscher
URL:
Keywords: compile-time-hog
: 10316 (view as bug list)
Depends on:
Blocks:
 
Reported: 2001-01-17 12:06 UTC by kcook34
Modified: 2004-01-17 04:22 UTC (History)
6 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2003-05-25 11:35:38


Attachments
mux32.cc (386 bytes, text/plain)
2003-05-21 15:16 UTC, kcook34
Details

Note You need to log in before you can comment on or make changes to this bug.
Description kcook34 2001-01-17 12:06:00 UTC
This simple program takes has been compiling for well over a day when optimization is enabled.  This is on a 500Mhz PIII.

The same file compilied with optimization under C instead of C++ compiles in under a second.  Ditto for either C or C++ under GCC 2.95.2.

A 16-bit version of the same program, was semi-corrected earlier, but only in the non-optimized version.  See http://gcc.gnu.org/ml/gcc-bugs/2000-08/msg00684.html

That original test case still takes about 1 minute when compiled with -O.  Since a little checking shows that the time approximately doubles with each bit added, I am spectulating that this would take 6 weeks to compile.  A 64 bit version would take a half-billion years.

Release:
gcc version 2.97 20010115 (experimental)

Environment:
CYGWIN_NT-5.0 KELLEY 1.1.7(0.31/3/2) 2000-12-25 12:39 i686 unknown

How-To-Repeat:
gcc -O mux32.cc
Comment 1 Zack Weinberg 2001-02-06 11:02:30 UTC
From: "Zack Weinberg" <zackw@stanford.edu>
To: Kelley Cook <kelley.cook@home.com>
Cc: gcc-gnats@gcc.gnu.org, gcc-bugs@gcc.gnu.org
Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
Date: Tue, 6 Feb 2001 11:02:30 -0800

 On Tue, Feb 06, 2001 at 12:57:26PM -0500, Kelley Cook wrote:
 > I don't see a way to add onto the GNATs item I opened, so I shall just 
 > post it here and hope someone with access can add onto PR c++/1687
 
 You do it by cc:ing gcc-gnats and leaving the bug tag in the subject
 line.  Also note bug discussion belongs on gcc-bugs, not gcc-patches.
 
 > The geometric regression that occurs only happens when "-finline" is 
 > enabled (which happens with -O1)
 
 This is the same sort of problem as the last time you had trouble with
 this test case, but in a different place.  -O1 with a 16-input mux():
 
  68.47     40.14    40.14        54   743.33  1082.78  walk_tree
  16.09     49.57     9.43 236756969     0.00     0.00  expand_call_inline
   7.93     54.22     4.65 143489477     0.00     0.00  statement_code_p
   4.67     56.96     2.74 143489445     0.00     0.00  cp_statement_code_p
   2.58     58.47     1.51  71745291     0.00     0.00  first_rtl_op
 
 We've got the messy tree structure, with tons of pointers to the same
 few nodes, same as last time.  We're trying to walk over it, again,
 and visiting the same few nodes over and over, again.  It's just
 happening in a different place.  walk_tree(expand_call_inline) is
 responsible for finding call sites and expanding them inline, should
 this be feasible.  There are no call sites in your test function, but
 it doesn't know that and it's got to grovel through 236,756,969 tree
 nodes to find out.
 
 I am not sure what to do about this.  Unlike in RTL, there is no handy tag
 on the statement nodes to indicate "this one performs a function call."
 (Perhaps there should be.)  So using walk_stmt_tree is not practical.  Also
 there are strange things going on with TARGET_EXPRs which I do not
 understand.  We could go for walk_tree_without_duplicates, but not fully
 understanding the logic here I am not confident that would work. Maybe a
 walk_expr_tree that doesn't visit type and decl nodes would be enough of a
 performance improvement?
 
 zw

Comment 2 Zack Weinberg 2001-02-06 12:43:21 UTC
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.  */

Comment 3 Zack Weinberg 2001-02-07 10:36:51 UTC
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: Wed, 7 Feb 2001 10:36:51 -0800

 On Tue, Feb 06, 2001 at 12:43:21PM -0800, Zack Weinberg wrote:
 > 
 > 	* 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.
 
 This survived an x86-linux bootstrap and reports the following test
 suite failures.  I do not know if they are regressions or not.
 
 FAIL: g++.dg/vtgc1.C scan-assembler (about 30 of these)
 FAIL: g++.ext/instantiate1.C not instantiated (test for errors, line 18)
 FAIL: g++.ext/instantiate1.C not instantiated (test for errors, line 20)
 FAIL: g++.jason/2371.C (test for excess errors)
 FAIL: g++.other/crash32.C (test for excess errors)
 FAIL: g++.other/loop2.C caused compiler crash
 
 zw

Comment 4 crosby 2001-02-14 06:07:08 UTC
From: Scott A Crosby <crosby@qwes.math.cmu.edu>
To: Zack Weinberg <zackw@Stanford.EDU>
Cc: Kelley Cook <kelley.cook@home.com>, gcc-gnats@gcc.gnu.org,
        gcc-bugs@gcc.gnu.org
Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
Date: Wed, 14 Feb 2001 06:07:08 -0500 (EST)

 On Tue, 6 Feb 2001, Zack Weinberg wrote:
 
 > 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().
 
 > 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.
 
 
 Could you workaround this by walking the tree normally, and try to inline
 at all of the nodes, but if you find out that you are scanning too many
 nodes, you abort and use a workaround strategy, say, walk-each-node once?
 
 Catch the pathalogical cases and shunt them elsewhere, and behave normally
 otherwise?
 
 Scott
 

Comment 5 Zack Weinberg 2001-02-14 13:00:49 UTC
From: "Zack Weinberg" <zackw@Stanford.EDU>
To: Scott A Crosby <crosby@qwes.math.cmu.edu>
Cc: Kelley Cook <kelley.cook@home.com>, gcc-gnats@gcc.gnu.org,
   gcc-bugs@gcc.gnu.org
Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
Date: Wed, 14 Feb 2001 13:00:49 -0800

 On Wed, Feb 14, 2001 at 06:07:08AM -0500, Scott A Crosby wrote:
 > On Tue, 6 Feb 2001, Zack Weinberg wrote:
 > 
 > > 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().
 > 
 > > 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.
 > 
 > 
 > Could you workaround this by walking the tree normally, and try to inline
 > at all of the nodes, but if you find out that you are scanning too many
 > nodes, you abort and use a workaround strategy, say, walk-each-node once?
 > 
 > Catch the pathalogical cases and shunt them elsewhere, and behave normally
 > otherwise?
 
 Let's find out if always walking each node once is safe, first.  It
 doesn't cause any C++ regressions, but I still don't know if it
 inhibits optimizations.  Paging C++ team...
 
 zw
Comment 6 Peter Bienstman 2001-03-07 03:52:24 UTC
State-Changed-From-To: open->analyzed
State-Changed-Why: Problem has been analysed, patch waiting for review
Comment 7 Peter Bienstman 2001-03-07 11:52:26 UTC
From: pbienst@gcc.gnu.org
To: gcc-gnats@gcc.gnu.org, kelley.cook@home.com, nobody@gcc.gnu.org
Cc:  
Subject: Re: c++/1687
Date: 7 Mar 2001 11:52:26 -0000

 Synopsis: Extreme compile time regression from 2.95.2
 
 State-Changed-From-To: open->analyzed
 State-Changed-By: pbienst
 State-Changed-When: Wed Mar  7 03:52:24 2001
 State-Changed-Why:
     Problem has been analysed, patch waiting for review
 
 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view&pr=1687&database=gcc

Comment 8 Zack Weinberg 2002-11-10 14:14:13 UTC
From: Zack Weinberg <zack@codesourcery.com>
To: Wolfgang Bangerth <bangerth@ticam.utexas.edu>
Cc: gcc-gnats@gcc.gnu.org, kelley.cook@home.com, gcc-bugs@gcc.gnu.org,
	pbienst@gcc.gnu.org, Zack Weinberg <zack@codesourcery.com>
Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
Date: Sun, 10 Nov 2002 14:14:13 -0800

 On Sun, Nov 10, 2002 at 03:51:12PM -0600, Wolfgang Bangerth wrote:
 > 
 > Zack,
 > you had a patch for this problem, as mentioned in the audit. Do you know 
 > whether it was applied? I cannot find it in the ChangeLogs.
 
 Yes, the patch was applied.  It's in cp/ChangeLog:
 
 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.
 
 This code is now in tree-inline.c, by the way
 
 > However, at -O3 it still takes forever, now with both C and C++, which 
 > seems a further regression (since previously this held only for C++). I 
 > don't trust this for various reasons, so maybe someone can confirm this 
 > with -O3?
 
 C being slow is a consequence of its using the tree-based inliner
 (previously only C++ did).  I don't know why -O3 would cause further
 trouble.  You could build cc1plus profiled (make clean in both
 libiberty and gcc, make all in libiberty with CFLAGS="-g -O2 -profile",
 make cc1plus in gcc with CFLAGS="-g -O2 -profile"), run it on the test
 case, and take a look at the gprof output.
 
 zw

Comment 9 Wolfgang Bangerth 2002-11-10 15:51:12 UTC
From: Wolfgang Bangerth <bangerth@ticam.utexas.edu>
To: gcc-gnats@gcc.gnu.org, <kelley.cook@home.com>, <gcc-bugs@gcc.gnu.org>,
   <pbienst@gcc.gnu.org>, Zack Weinberg <zack@codesourcery.com>
Cc:  
Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
Date: Sun, 10 Nov 2002 15:51:12 -0600 (CST)

 Zack,
 you had a patch for this problem, as mentioned in the audit. Do you know 
 whether it was applied? I cannot find it in the ChangeLogs.
 
 At any rate, I get reasonable compile times with -O2:
 tmp/g> time /home/bangerth/bin/gcc-3.3x-pre/bin/gcc -O2 -c x.cc
 real    0m0.168s
 user    0m0.150s
 sys     0m0.010s
 tmp/g> time /home/bangerth/bin/gcc-3.3x-pre/bin/gcc -O2 -c x.cc
 real    0m0.261s
 user    0m0.150s
 sys     0m0.000s
 
 However, at -O3 it still takes forever, now with both C and C++, which 
 seems a further regression (since previously this held only for C++). I 
 don't trust this for various reasons, so maybe someone can confirm this 
 with -O3?
 
 Regards
   Wolfgang
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth              email:           bangerth@ticam.utexas.edu
                                www: http://www.ticam.utexas.edu/~bangerth
 
 

Comment 10 Wolfgang Bangerth 2002-11-14 14:35:15 UTC
From: Wolfgang Bangerth <bangerth@apex68.ticam.utexas.edu>
To: gcc-gnats@gcc.gnu.org
Cc:  
Subject: c++/1687: Extreme compile time regression from 2.95.2
Date: Thu, 14 Nov 2002 14:35:15 -0600

 Re-confirmed with 3.3 CVS from 2002-11-10 and 3.2.1 pre from the same date.

Comment 11 Wolfgang Bangerth 2003-04-11 14:31:05 UTC
From: Wolfgang Bangerth <bangerth@ices.utexas.edu>
To: Steven Bosscher <s.bosscher@student.tudelft.nl>
Cc: gcc-gnats@gcc.gnu.org, <kelley.cook@home.com>, <gcc-bugs@gcc.gnu.org>,
   <nobody@gcc.gnu.org>, <gcc-prs@gcc.gnu.org>
Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
Date: Fri, 11 Apr 2003 14:31:05 -0500 (CDT)

 > Wolfgang, you were the last to re-confirm the PR, do you still
 > see it?
 
 I see long compile times for the C front-end, but it compiles 
 instantaneously with the C++ front end. Don't know whether that's just a 
 problem on my side or true -- can you check this (sorry, don't have time 
 right now...).
 
 W.
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth              email:            bangerth@ices.utexas.edu
                                www: http://www.ices.utexas.edu/~bangerth/
 
 

Comment 12 s.bosscher 2003-04-11 20:57:21 UTC
From: Steven Bosscher <s.bosscher@student.tudelft.nl>
To: gcc-gnats@gcc.gnu.org, kelley.cook@home.com,
	gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org, gcc-prs@gcc.gnu.org,
	bangerth <bangerth@ticam.utexas.edu>
Cc:  
Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
Date: Fri, 11 Apr 2003 20:57:21 +0200

 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=1687
 
 I cannot reproduce this with:
 - gcc-3.3 (GCC) 3.3 20030407 (prerelease) or
 - gcc-3.4 (GCC) 3.4 20030411 (experimental).
 
 Both give subsecond compile times.  Which is particularly nice
 because it means that we can say at least one positive thing about
 compile time performance of 3.3 (this is a regression that is not
 marked as one for some reason...).
 
 Wolfgang, you were the last to re-confirm the PR, do you still
 see it?
 
 Greetz
 Steven
 
 
 

Comment 13 s.bosscher 2003-04-11 23:37:47 UTC
From: Steven Bosscher <s.bosscher@student.tudelft.nl>
To: Wolfgang Bangerth <bangerth@ices.utexas.edu>
Cc: gcc-gnats@gcc.gnu.org, gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org,
	gcc-prs@gcc.gnu.org
Subject: Re: c++/1687: Extreme compile time regression from 2.95.2
Date: 11 Apr 2003 23:37:47 +0200

 Op vr 11-04-2003, om 21:31 schreef Wolfgang Bangerth:
 > 
 > > Wolfgang, you were the last to re-confirm the PR, do you still
 > > see it?
 > 
 > I see long compile times for the C front-end, but it compiles 
 > instantaneously with the C++ front end. Don't know whether that's just a 
 > problem on my side or true -- can you check this (sorry, don't have time 
 > right now...).
 
 You are right. C++ takes a fraction of a second, C just dies.
 

Comment 14 s.bosscher 2003-04-17 15:11:21 UTC
From: Steven Bosscher <s.bosscher@student.tudelft.nl>
To: gcc-gnats@gcc.gnu.org, kelley.cook@home.com,
	gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org, gcc-prs@gcc.gnu.org,
	mark@codesourcery.com
Cc:  
Subject: Re: c/1687: [3.3/3.4 regression] Extreme compile time regression
 from 2.95.3
Date: Thu, 17 Apr 2003 15:11:21 +0200

 Hi,
 
 The GCC C front end shows exponential behavior in time for this
 code with -finline-functions.  The time is spent in walk_tree but
 the problem may be elsewhere, I haven't looked at that yet.
 
 --------------------------------
 typedef int bool;
 bool in0, in1, in2, in3, in4, in5, in6, in7, in8, in9;
 unsigned long output;
 
 void mux(void)
 {
   output =
       (in0   ?  0x00000001 : 0) | (in1   ?  0x00000008 : 0) |
       (in2   ?  0x00000001 : 0) | (in3   ?  0x00000008 : 0) |
       (in4   ?  0x00000001 : 0) | (in5   ?  0x00000008 : 0) |
       (in6   ?  0x00000001 : 0) | (in7   ?  0x00000008 : 0) |
       (in8   ?  0x00000001 : 0) | (in9   ?  0x00000008 : 0)
   ;
 }
 --------------------------------
 
 This function has 10 variables "int ii??".  I have similair programs
 with 11, 12, 13, 14 and 15 "int ii??" variables (I started with 32,
 like the original test case, but it ate memory until it died).
 
 Here is the output for "time cc1 -quiet -O -finline-functions":
 
 # of in??      log(user+sys)   user+sys    user    sys
 10                -0.284         0.52      0.49    0.03
 11                 0.130         1.35      1.35    0
 12                 0.590         3.89      3.87    0.02
 13                 1.059        11.47     11.47    0
 14                 1.534        34.23     34.21    0.02
 15                 2.012       102.92    102.88    0.04
 
 GNU C version 3.4 20030417 (experimental) (i586-pc-linux-gnu)
     compiled by GNU C version 2.95.3 20010315 (SuSE).
 GGC heuristics: --param ggc-min-expand=42 --param ggc-min-heapsize=23891
 
 The C++ front end does not show this behavior.
 
 Greetz
 Steven
 
 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=1687 
 
 

Comment 15 s.bosscher 2003-05-02 01:52:13 UTC
From: Steven Bosscher <s.bosscher@student.tudelft.nl>
To: gcc-gnats@gcc.gnu.org, kcook34@ford.com, gcc-bugs@gcc.gnu.org,
	nobody@gcc.gnu.org, gcc-prs@gcc.gnu.org, mark@codesourcery.com
Cc:  
Subject: Re: c/1687: [3.3/3.4 regression] Exponential time behavior with -O
 -finline-functions (compile time regression from 2.95.3)
Date: Fri, 02 May 2003 01:52:13 +0200

 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=1687
 
 This bug exists for at least '+', '-', '&', '|' as operators in the 
 attached test case, i.e.
 
 int in0 ;  int in1 ;
 int in2 ;  int in3 ;
 int in4 ;  int in5 ;
 int in6 ;  int in7 ;
 int in8 ;  int in9 ;
 int in10; int in11;
 int in12; int in13;
 int in14; int in15;
 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) ;
 }
 
 also triggers the bug.  But '||' and '&&' do not.  Maybe a bug
 somewhere in convert?
 
 Greetz
 Steven
 

Comment 16 s.bosscher 2003-05-02 12:24:34 UTC
From: Steven Bosscher <s.bosscher@student.tudelft.nl>
To: gcc-gnats@gcc.gnu.org, kcook34@ford.com, gcc-bugs@gcc.gnu.org,
	nobody@gcc.gnu.org, gcc-prs@gcc.gnu.org
Cc:  
Subject: Re: c/1687: [3.3/3.4 regression] Exponential time behavior with -O
 -finline-functions (compile time regression from 2.95.3)
Date: Fri, 02 May 2003 12:24:34 +0200

 http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=1687
 
 Proposed a patch:
 http://gcc.gnu.org/ml/gcc-patches/2003-05/msg00179.html
 
 Gr.,
 Steven
 
 
Comment 17 Steven Bosscher 2003-05-09 22:45:40 UTC
Responsible-Changed-From-To: unassigned->steven
Responsible-Changed-Why: Fixed it for 3.3, working on a fix for mainline
Comment 18 s.bosscher 2003-06-19 21:43:07 UTC
Subject: Re:  [3.4 regression] Exponential time behavior with
 -O -finline-functions (compile time regression from 3.2, 3.3)

pinskia at physics dot uc dot edu wrote:

>PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.
>
>http://gcc.gnu.org/bugzilla/show_bug.cgi?id=1687
>
>
>pinskia at physics dot uc dot edu changed:
>
>           What    |Removed                     |Added
>----------------------------------------------------------------------------
>OtherBugsDependingO|                            |8361
>              nThis|                            |
>  
>
Eh?  Please undo this.

Last time I checked, this made virtually no difference for this PR, and 
PR 8361 most certainly does not depend on this one (in fact the test 
case for this PR always compiled fine with g++, only the C front end got 
stuck on something.  I haven't figured out what the difference is 
unfortunately).


Comment 19 Steven Bosscher 2003-07-03 21:02:10 UTC
A patch for 3.4 has been posted in:
http://gcc.gnu.org/ml/gcc-patches/2003-07/msg00378.html
Comment 20 CVS Commits 2003-07-08 19:44:23 UTC
Subject: Bug 1687

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	steven@gcc.gnu.org	2003-07-08 19:44:17

Modified files:
	gcc            : ChangeLog tree-inline.c c-semantics.c 
	                 c-objc-common.c 

Log message:
	2003-07-08  Steven Bosscher  <steven@gcc.gnu.org>
	
	PR c/1687
	* tree-inline.c (find_alloca_call): Use
	walk_tree_without_duplicates, instead of walk_tree.
	(find_builtin_longjmp_call): Likewise.
	* c-objc-common.c (c_cannot_inline_fn): Likewise.
	* c-semantics.c (find_reachable_label): Likewise.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.400&r2=2.401
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-inline.c.diff?cvsroot=gcc&r1=1.65&r2=1.66
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-semantics.c.diff?cvsroot=gcc&r1=1.67&r2=1.68
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-objc-common.c.diff?cvsroot=gcc&r1=1.25&r2=1.26

Comment 22 Andrew Pinski 2003-07-15 18:42:54 UTC
*** Bug 10316 has been marked as a duplicate of this bug. ***
Comment 23 Steven Bosscher 2003-07-20 17:03:27 UTC
Andrew I'm not sure why you keep modifying this resolved bug...