Bug 12454 - large number of if ();else if cause
Summary: large number of if ();else if cause
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: tree-ssa
: P2 minor
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: ice-on-valid-code
: 14228 21898 (view as bug list)
Depends on: 14472
Blocks: 10349
  Show dependency treegraph
 
Reported: 2003-09-30 06:57 UTC by Richard Henderson
Modified: 2006-10-15 17:21 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-12-24 19:47:34


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Henderson 2003-09-30 06:57:17 UTC
This test case has 11,000 chained else if's.  We fail because gimplify_cond_expr
isn't written to allow tail-calling, and exhaust stack space.  There's enough
complexity in that function that the transformation would be non-trivial.

The test will be xfailed on the branch, but must be fixed before merging.
Comment 1 Steven Bosscher 2003-10-11 16:51:32 UTC
This test case works for me, and is even faster with tree-ssa than with mainline
(both with checking enabled):

$ ./cc1plus --version
GNU C++ version 3.5-tree-ssa 20031010 (merged 20031005) (i686-pc-linux-gnu)
        compiled by GNU C version 3.5-tree-ssa 20031010 (merged 20031005).
GGC heuristics: --param ggc-min-expand=30 --param ggc-min-heapsize=4096
$ time ./cc1plus -O stack1.C
 void foo()
 {GC 9203k -> 482k}
Execution times (seconds)
 garbage collection    :   0.02 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall
 preprocessing         :   0.08 ( 0%) usr   0.01 (12%) sys   0.10 ( 0%) wall
 parser                :   0.40 ( 1%) usr   0.04 (50%) sys   0.44 ( 1%) wall
 name lookup           :  54.70 (99%) usr   0.02 (25%) sys  54.81 (99%) wall
 integration           :   0.04 ( 0%) usr   0.00 ( 0%) sys   0.04 ( 0%) wall
 tree gimplify         :   0.16 ( 0%) usr   0.00 ( 0%) sys   0.16 ( 0%) wall
 expand                :   0.02 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall
 branch prediction     :   0.00 ( 0%) usr   0.01 (12%) sys   0.01 ( 0%) wall
 TOTAL                 :  55.44             0.08            55.62
 
real    0m55.644s
user    0m55.440s
sys     0m0.100s


$ ./cc1plus --version
GNU C++ version 3.4 20031005 (experimental) (i686-pc-linux-gnu)
        compiled by GNU C version 3.4 20031005 (experimental).
GGC heuristics: --param ggc-min-expand=30 --param ggc-min-heapsize=4096
$ time ./cc1plus -O stack1.C
 void foo()
 {GC 14967k -> 6215k}
Execution times (seconds)
 garbage collection    :   0.08 ( 0%) usr   0.00 ( 0%) sys   0.08 ( 0%) wall
 cfg construction      :  10.26 ( 9%) usr   0.00 ( 0%) sys  10.26 ( 9%) wall
 cfg cleanup           :  43.11 (36%) usr   0.00 ( 0%) sys  43.14 (36%) wall
 trivially dead code   :   0.01 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall
 rebuild jump labels   :   0.03 ( 0%) usr   0.00 ( 0%) sys   0.03 ( 0%) wall
 preprocessing         :   0.02 ( 0%) usr   0.01 (25%) sys   0.03 ( 0%) wall
 parser                :   0.50 ( 0%) usr   0.03 (75%) sys   0.53 ( 0%) wall
 name lookup           :  54.49 (46%) usr   0.00 ( 0%) sys  54.51 (46%) wall
 expand                :   0.08 ( 0%) usr   0.00 ( 0%) sys   0.08 ( 0%) wall
 integration           :   0.12 ( 0%) usr   0.00 ( 0%) sys   0.12 ( 0%) wall
 jump                  :  10.10 ( 8%) usr   0.00 ( 0%) sys  10.10 ( 8%) wall
 branch prediction     :   0.16 ( 0%) usr   0.00 ( 0%) sys   0.20 ( 0%) wall
 local alloc           :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall
 global alloc          :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall
 flow 2                :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall
 rename registers      :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall
 shorten branches      :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.02 ( 0%) wall
 final                 :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall
 symout                :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 ( 0%) wall
 rest of compilation   :   0.08 ( 0%) usr   0.00 ( 0%) sys   0.10 ( 0%) wall
 TOTAL                 : 119.05             0.04           119.38
 
real    1m59.478s
user    1m59.050s
sys     0m0.050s

Comment 2 Andrew Pinski 2003-10-11 17:16:46 UTC
Looks like his stack limit is high.  The reason why it is faster on the tree-ssa branch is because all 
the if's are gone when converting from trees to rtl.
Comment 3 Andrew Pinski 2003-12-07 07:44:09 UTC
XPASS's on i386-unknown-freebsd4.9, alphaev67-unknown-linux-gnu, i686-pc-linux-gnu 
(depends on the stacksize).
Comment 4 Andrew Pinski 2004-02-20 18:41:53 UTC
*** Bug 14228 has been marked as a duplicate of this bug. ***
Comment 5 Andrew Pinski 2004-03-08 01:32:55 UTC
Note now (with sibling call on the tree level, some functions are not sibcalled, already 
filed another bug for it): the backtrace looks like this:
#1  0x0013daec in c_gimplify_expr (expr_p=0x74, pre_p=0x410d3400, post_p=
0x410c4a80) at /Users/pinskia/src/gcc-tree-ssa/gcc/gcc/c-simplify.c:1015
#2  0x0013daec in c_gimplify_expr (expr_p=0xbf80030c, pre_p=0x410d3400, post_p=
0x410c4a80) at /Users/pinskia/src/gcc-tree-ssa/gcc/gcc/c-simplify.c:1015
#3  0x00108bc4 in cp_gimplify_expr (expr_p=0xbf80030c, pre_p=0xbf800218, post_p=
0xbf80021c) at /Users/pinskia/src/gcc-tree-ssa/gcc/gcc/cp/cp-simplify.c:163
#4  0x0024373c in gimplify_expr (expr_p=0xbf80030c, pre_p=0x1, post_p=0x0, 
gimple_test_f=0xf, fallback=fb_none) at /Users/pinskia/src/gcc-tree-ssa/gcc/gcc/
gimplify.c:3030
#5  0x00246e88 in gimplify_stmt (stmt_p=0x7b4c80) at /Users/pinskia/src/gcc-tree-ssa/
gcc/gcc/gimplify.c:2912
#6  0x0013bc0c in c_gimplify_stmt (stmt_p=0xbf80030c) at /Users/pinskia/src/gcc-tree-
ssa/gcc/gcc/c-simplify.c:325
#7  0x0013daec in c_gimplify_expr (expr_p=0xbf800218, pre_p=0x410d3400, post_p=
0x410c4a80) at /Users/pinskia/src/gcc-tree-ssa/gcc/gcc/c-simplify.c:1015
#8  0x00108bc4 in cp_gimplify_expr (expr_p=0xe337c8, pre_p=0xbf800488, post_p=
0xbf80048c) at /Users/pinskia/src/gcc-tree-ssa/gcc/gcc/cp/cp-simplify.c:163
#9  0x0024373c in gimplify_expr (expr_p=0xe337c8, pre_p=0x1, post_p=0x0, 
gimple_test_f=0xf, fallback=fb_none) at /Users/pinskia/src/gcc-tree-ssa/gcc/gcc/
gimplify.c:3030

Another way to fix this part of the back trace is define the LANGHOOK to return the enum, 
I am testing a patch for that.
Comment 6 Andrew Pinski 2004-11-28 21:11:37 UTC
Hmm (at least on ppc-darwin), with --disable-checking this works but without we get a stack overflow.
Comment 7 CVS Commits 2004-12-12 22:33:08 UTC
Subject: Bug 12454

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	sayle@gcc.gnu.org	2004-12-12 22:33:00

Modified files:
	gcc/cp         : ChangeLog cp-gimplify.c 

Log message:
	PR middle-end/12454
	* cp-gimplify.c (gimplify_if_stmt): Optimize the case where the
	condition is a constant and the unexecuted clause is empty.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/ChangeLog.diff?cvsroot=gcc&r1=1.4528&r2=1.4529
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/cp-gimplify.c.diff?cvsroot=gcc&r1=1.14&r2=1.15

Comment 8 Steven Bosscher 2004-12-20 23:26:40 UTC
Is this still an issue, and if so, is it fixable for GCC 4.0? 
Comment 9 Andrew Pinski 2004-12-21 05:02:57 UTC
The testcase is now fixed but the fundamental problem with the gimplifier still exists.  So this is no 
longer a regression.
Comment 10 Kazu Hirata 2006-05-20 20:10:14 UTC
*** Bug 21898 has been marked as a duplicate of this bug. ***