* [Bug middle-end/35204] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
@ 2008-02-14 23:14 ` marcus at jet dot franken dot de
2008-02-14 23:16 ` marcus at jet dot franken dot de
` (30 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: marcus at jet dot franken dot de @ 2008-02-14 23:14 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from marcus at jet dot franken dot de 2008-02-14 23:13 -------
Created an attachment (id=15153)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15153&action=view)
menu.i.gz
menu.i.gz (extract from Wine)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
2008-02-14 23:14 ` [Bug middle-end/35204] " marcus at jet dot franken dot de
@ 2008-02-14 23:16 ` marcus at jet dot franken dot de
2008-02-14 23:18 ` marcus at jet dot franken dot de
` (29 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: marcus at jet dot franken dot de @ 2008-02-14 23:16 UTC (permalink / raw)
To: gcc-bugs
------- Comment #2 from marcus at jet dot franken dot de 2008-02-14 23:15 -------
(gcc 4.2.1 seems to survive)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
2008-02-14 23:14 ` [Bug middle-end/35204] " marcus at jet dot franken dot de
2008-02-14 23:16 ` marcus at jet dot franken dot de
@ 2008-02-14 23:18 ` marcus at jet dot franken dot de
2008-02-14 23:21 ` marcus at jet dot franken dot de
` (28 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: marcus at jet dot franken dot de @ 2008-02-14 23:18 UTC (permalink / raw)
To: gcc-bugs
------- Comment #3 from marcus at jet dot franken dot de 2008-02-14 23:17 -------
my stacksize is limited to 8MB
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (2 preceding siblings ...)
2008-02-14 23:18 ` marcus at jet dot franken dot de
@ 2008-02-14 23:21 ` marcus at jet dot franken dot de
2008-02-14 23:22 ` [Bug middle-end/35204] [4.3 Regression] " rguenth at gcc dot gnu dot org
` (27 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: marcus at jet dot franken dot de @ 2008-02-14 23:21 UTC (permalink / raw)
To: gcc-bugs
------- Comment #4 from marcus at jet dot franken dot de 2008-02-14 23:20 -------
wit ulimit -s unlimited the test survives.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (3 preceding siblings ...)
2008-02-14 23:21 ` marcus at jet dot franken dot de
@ 2008-02-14 23:22 ` rguenth at gcc dot gnu dot org
2008-02-14 23:25 ` steven at gcc dot gnu dot org
` (26 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-14 23:22 UTC (permalink / raw)
To: gcc-bugs
------- Comment #5 from rguenth at gcc dot gnu dot org 2008-02-14 23:22 -------
x86_64-linux has a default stack limit of 8MB.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |rguenth at gcc dot gnu dot
| |org
Keywords| |ice-on-valid-code
Summary|crash by too deep recursion |[4.3 Regression] crash by
|in DFS tree-ssa-sccvn.c:1898|too deep recursion in DFS
| |tree-ssa-sccvn.c:1898
Target Milestone|--- |4.3.0
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (4 preceding siblings ...)
2008-02-14 23:22 ` [Bug middle-end/35204] [4.3 Regression] " rguenth at gcc dot gnu dot org
@ 2008-02-14 23:25 ` steven at gcc dot gnu dot org
2008-02-14 23:26 ` steven at gcc dot gnu dot org
` (25 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: steven at gcc dot gnu dot org @ 2008-02-14 23:25 UTC (permalink / raw)
To: gcc-bugs
------- Comment #6 from steven at gcc dot gnu dot org 2008-02-14 23:25 -------
Should be P1.
This bug is shows an intrinsic scalability problem with SCC-VN as it is
implemented right now (and presented in the literature).
The key issue is, SCC-VN should use a non-recursive SCC finding algorithm, but
one that still pops the SCCs in topological order. I tried once to write
SCC-VN's DFS in a non-recursive way, but I never succeeded. I also tried to
find a substitute for Tarjan's algorithm that possesses the properties required
for SCC-VN, but also failed there.
CCing Danny on this one for advice.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (5 preceding siblings ...)
2008-02-14 23:25 ` steven at gcc dot gnu dot org
@ 2008-02-14 23:26 ` steven at gcc dot gnu dot org
2008-02-15 9:09 ` rguenther at suse dot de
` (24 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: steven at gcc dot gnu dot org @ 2008-02-14 23:26 UTC (permalink / raw)
To: gcc-bugs
--
steven at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |dberlin at gcc dot gnu dot
| |org
Status|UNCONFIRMED |NEW
Ever Confirmed|0 |1
Last reconfirmed|0000-00-00 00:00:00 |2008-02-14 23:25:17
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (6 preceding siblings ...)
2008-02-14 23:26 ` steven at gcc dot gnu dot org
@ 2008-02-15 9:09 ` rguenther at suse dot de
2008-02-15 13:32 ` rguenth at gcc dot gnu dot org
` (23 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenther at suse dot de @ 2008-02-15 9:09 UTC (permalink / raw)
To: gcc-bugs
------- Comment #7 from rguenther at suse dot de 2008-02-15 09:08 -------
Subject: Re: [4.3 Regression] crash by too deep
recursion in DFS tree-ssa-sccvn.c:1898
On Thu, 14 Feb 2008, steven at gcc dot gnu dot org wrote:
> ------- Comment #6 from steven at gcc dot gnu dot org 2008-02-14 23:25 -------
> Should be P1.
P1 are bugs that block the release. With your reasoning below, this
is not going to work out.
Marcus, did you have checking enabled for your gcc build?
Richard.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (7 preceding siblings ...)
2008-02-15 9:09 ` rguenther at suse dot de
@ 2008-02-15 13:32 ` rguenth at gcc dot gnu dot org
2008-02-15 13:36 ` rguenth at gcc dot gnu dot org
` (22 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-15 13:32 UTC (permalink / raw)
To: gcc-bugs
------- Comment #8 from rguenth at gcc dot gnu dot org 2008-02-15 13:32 -------
We can, similarly to limiting the overall SCC size, limit the depth to where
we search. This testcase hits the stack limit on x86_64 with an unoptimized
cc1 built with gcc 4.2 with
(gdb) print *sccstack
$2 = {base = {num = 25069, alloc = 35065, vec = {0x2b201c6f8c60}}}
as we limit the SCC size to 10000 we might as well limit the SCC stack size
to some magic number.
Or gcc could simply upper the (soft) stack limit with setrlimit...
Note that DFS in a bootstrapped compiler with release checking enabled doesn't
use an excessive amount of stack, but only pushes 6 registers (which are of
course 64bit wide) and allocates room for 56 extra bytes, which makes the
stack space used per recursion 110 bytes.
All big structures (in particular the ssa_op_iter) are scalarized though,
at least if VN_INFO is not inlined (if marked with always_inline ssa_op_iter
is not scalarized because then op_iter_next_use is not inlined). So we
may run into some inlining issues here (all of op_iter_* in tree-flow-inline.h
_are_ big, so they definitely get defered to the final inlining phase while
VN_INFO is (w/o checking) inlined by the early inliner). But at least
I don't see traces of op_iter_* calls in a bootstrapped compiler.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (8 preceding siblings ...)
2008-02-15 13:32 ` rguenth at gcc dot gnu dot org
@ 2008-02-15 13:36 ` rguenth at gcc dot gnu dot org
2008-02-15 16:21 ` steven at gcc dot gnu dot org
` (21 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-15 13:36 UTC (permalink / raw)
To: gcc-bugs
------- Comment #9 from rguenth at gcc dot gnu dot org 2008-02-15 13:35 -------
Shouldn't we make sure, eventually by an ALWAYS_INLINE macro, that all of our
iterator functions are inlined so they definitely can be scalarized?
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |dnovillo at gcc dot gnu dot
| |org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (9 preceding siblings ...)
2008-02-15 13:36 ` rguenth at gcc dot gnu dot org
@ 2008-02-15 16:21 ` steven at gcc dot gnu dot org
2008-02-15 16:30 ` rguenth at gcc dot gnu dot org
` (20 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: steven at gcc dot gnu dot org @ 2008-02-15 16:21 UTC (permalink / raw)
To: gcc-bugs
------- Comment #10 from steven at gcc dot gnu dot org 2008-02-15 16:20 -------
Re. comment #7, sure this can be P1 and block the release. SCC-VN doesn't have
to be fixed for the release. This bug can be worked around.
Not making a bug P1 because you want a release out the door is not a good
readon. And unless I'm mistaken, a ICE-on-valid-code bug in C or C++ is always
release-blocking anyway.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (10 preceding siblings ...)
2008-02-15 16:21 ` steven at gcc dot gnu dot org
@ 2008-02-15 16:30 ` rguenth at gcc dot gnu dot org
2008-02-16 8:46 ` marcus at jet dot franken dot de
` (19 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-15 16:30 UTC (permalink / raw)
To: gcc-bugs
------- Comment #11 from rguenth at gcc dot gnu dot org 2008-02-15 16:29 -------
Well "always" is to be taken with a grain of salt. The testcase doesn't look
common, but is a huge machine-generated piece of cr*p :P
Otherwise this "always" also applies to wrong-code and rejects-valid bugs.
If primary/secondary platforms are affected.
Also there's a workaround available for this bug, -fno-tree-fre -fno-tree-pre.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (11 preceding siblings ...)
2008-02-15 16:30 ` rguenth at gcc dot gnu dot org
@ 2008-02-16 8:46 ` marcus at jet dot franken dot de
2008-02-16 9:34 ` steven at gcc dot gnu dot org
` (18 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: marcus at jet dot franken dot de @ 2008-02-16 8:46 UTC (permalink / raw)
To: gcc-bugs
------- Comment #12 from marcus at jet dot franken dot de 2008-02-16 08:45 -------
i configure gcc with just --enable-languages=c so whatever is currently the
default.
btw, today it builds without too deep recursion again :(
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (12 preceding siblings ...)
2008-02-16 8:46 ` marcus at jet dot franken dot de
@ 2008-02-16 9:34 ` steven at gcc dot gnu dot org
2008-02-16 9:40 ` steven at gcc dot gnu dot org
` (17 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: steven at gcc dot gnu dot org @ 2008-02-16 9:34 UTC (permalink / raw)
To: gcc-bugs
------- Comment #13 from steven at gcc dot gnu dot org 2008-02-16 09:33 -------
Re. comment #8
You can't terminate the DFS before a complete SCC is found, it will break the
correctness of the SCC-VN algorithm. You'd start another DFS from a
not-yet-marked SSA name that is in the SCC's DFS subtree, but you won't find
the comoplete SCC. I have no idea exactly what would happen, but I'm sure it
would be something bad ;-)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (13 preceding siblings ...)
2008-02-16 9:34 ` steven at gcc dot gnu dot org
@ 2008-02-16 9:40 ` steven at gcc dot gnu dot org
2008-02-16 10:41 ` rguenth at gcc dot gnu dot org
` (16 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: steven at gcc dot gnu dot org @ 2008-02-16 9:40 UTC (permalink / raw)
To: gcc-bugs
------- Comment #14 from steven at gcc dot gnu dot org 2008-02-16 09:40 -------
For those who have no idea what we're talking about, check out these links.
The first link is Tarjan's algorithm, which is what the tree-ssa-sccvn.c
SCC-finder is based on. The second link is Pearce's improved algorithm. Ref.
6 from that paper is also of interest.
http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
http://www.mcs.vuw.ac.nz/~djp/files/P05.pdf
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (14 preceding siblings ...)
2008-02-16 9:40 ` steven at gcc dot gnu dot org
@ 2008-02-16 10:41 ` rguenth at gcc dot gnu dot org
2008-02-16 11:24 ` rguenth at gcc dot gnu dot org
` (15 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-16 10:41 UTC (permalink / raw)
To: gcc-bugs
------- Comment #15 from rguenth at gcc dot gnu dot org 2008-02-16 10:41 -------
re comment #13 - limiting the DFS walk depth will of course only work if we
then abort SCCVN completely (like we do for the SCC size limit). But still
finding a magic number that fixes only the case where we blow the stack is
hard ;)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (15 preceding siblings ...)
2008-02-16 10:41 ` rguenth at gcc dot gnu dot org
@ 2008-02-16 11:24 ` rguenth at gcc dot gnu dot org
2008-02-16 12:12 ` rguenth at gcc dot gnu dot org
` (14 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-16 11:24 UTC (permalink / raw)
To: gcc-bugs
------- Comment #16 from rguenth at gcc dot gnu dot org 2008-02-16 11:23 -------
The problem with doing a non-recursive version of DFS as for GCC SCCVN is to
"split" the FOR_EACH_PHI_OR_STMT_USE walk. You would need to open-code this
and keep a stack of ssa_op_iters, ugly but certainly not impossible.
Steven, did you try something along this route?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (16 preceding siblings ...)
2008-02-16 11:24 ` rguenth at gcc dot gnu dot org
@ 2008-02-16 12:12 ` rguenth at gcc dot gnu dot org
2008-02-16 12:49 ` rguenth at gcc dot gnu dot org
` (13 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-16 12:12 UTC (permalink / raw)
To: gcc-bugs
------- Comment #17 from rguenth at gcc dot gnu dot org 2008-02-16 12:11 -------
Created an attachment (id=15167)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15167&action=view)
patch that still needs some love
Something like this?
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |rguenth at gcc dot gnu dot
|dot org |org
Status|NEW |ASSIGNED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (17 preceding siblings ...)
2008-02-16 12:12 ` rguenth at gcc dot gnu dot org
@ 2008-02-16 12:49 ` rguenth at gcc dot gnu dot org
2008-02-16 12:52 ` rguenth at gcc dot gnu dot org
` (12 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-16 12:49 UTC (permalink / raw)
To: gcc-bugs
------- Comment #18 from rguenth at gcc dot gnu dot org 2008-02-16 12:49 -------
Created an attachment (id=15168)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15168&action=view)
patch
Patch which got some minimal testing and love.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #15167|0 |1
is obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (18 preceding siblings ...)
2008-02-16 12:49 ` rguenth at gcc dot gnu dot org
@ 2008-02-16 12:52 ` rguenth at gcc dot gnu dot org
2008-02-16 14:57 ` dberlin at dberlin dot org
` (11 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-16 12:52 UTC (permalink / raw)
To: gcc-bugs
------- Comment #19 from rguenth at gcc dot gnu dot org 2008-02-16 12:51 -------
Note that while it definitely improves stack usage, the total memory usage is
likely to go up (vectors allocate some extra heap, the iters are now
addressable
and thus consume full memory) and as the ssa_op_iter is now pinned to memory
it is likely the algorithm is slower as well.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (19 preceding siblings ...)
2008-02-16 12:52 ` rguenth at gcc dot gnu dot org
@ 2008-02-16 14:57 ` dberlin at dberlin dot org
2008-02-16 15:23 ` rguenth at gcc dot gnu dot org
` (10 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: dberlin at dberlin dot org @ 2008-02-16 14:57 UTC (permalink / raw)
To: gcc-bugs
------- Comment #20 from dberlin at gcc dot gnu dot org 2008-02-16 14:56 -------
Subject: Re: [4.3 Regression] crash by too deep recursion in DFS
tree-ssa-sccvn.c:1898
So, there are better SCC algorithms.
In particular, Nuutilla's algorithm will avoid placing a bunch of
nodes on the stack (pearce's is a modification of this).
This is what structalias uses.
You can also certainly make the algorithm non-recursive, but it is a
bunch of work.
See http://www.cise.ufl.edu/research/sparse/btf/BTF/Source/btf_strongcomp.c
for an example of a non-recursive SCC finder.
In essence, you have to keep stacks for each variable.
On 16 Feb 2008 12:51:44 -0000, rguenth at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> ------- Comment #19 from rguenth at gcc dot gnu dot org 2008-02-16 12:51 -------
> Note that while it definitely improves stack usage, the total memory usage is
> likely to go up (vectors allocate some extra heap, the iters are now
> addressable
> and thus consume full memory) and as the ssa_op_iter is now pinned to memory
> it is likely the algorithm is slower as well.
>
>
> --
>
>
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
>
> ------- You are receiving this mail because: -------
> You are on the CC list for the bug, or are watching someone who is.
>
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (20 preceding siblings ...)
2008-02-16 14:57 ` dberlin at dberlin dot org
@ 2008-02-16 15:23 ` rguenth at gcc dot gnu dot org
2008-02-17 16:25 ` rguenth at gcc dot gnu dot org
` (9 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-16 15:23 UTC (permalink / raw)
To: gcc-bugs
------- Comment #21 from rguenth at gcc dot gnu dot org 2008-02-16 15:22 -------
The patch only avoids using the stack in favor of maintaining heap allocated
stacks. The algorithm is still recursively walking the graph.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (21 preceding siblings ...)
2008-02-16 15:23 ` rguenth at gcc dot gnu dot org
@ 2008-02-17 16:25 ` rguenth at gcc dot gnu dot org
2008-03-14 17:11 ` [Bug middle-end/35204] [4.3/4.4 " rguenth at gcc dot gnu dot org
` (8 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-02-17 16:25 UTC (permalink / raw)
To: gcc-bugs
------- Comment #22 from rguenth at gcc dot gnu dot org 2008-02-17 16:24 -------
The patch was successfully bootstrapped and tested on x86_64-unknown-linux-gnu
and doesn't show overall negative effects on compile-time or memory-usage on
our daily testers. I am considering it for 4.3.1 after putting it to trunk.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Priority|P3 |P2
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (22 preceding siblings ...)
2008-02-17 16:25 ` rguenth at gcc dot gnu dot org
@ 2008-03-14 17:11 ` rguenth at gcc dot gnu dot org
2008-04-03 9:54 ` rguenth at gcc dot gnu dot org
` (7 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-03-14 17:11 UTC (permalink / raw)
To: gcc-bugs
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Known to fail| |4.3.0
Target Milestone|4.3.0 |4.3.1
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (23 preceding siblings ...)
2008-03-14 17:11 ` [Bug middle-end/35204] [4.3/4.4 " rguenth at gcc dot gnu dot org
@ 2008-04-03 9:54 ` rguenth at gcc dot gnu dot org
2008-04-03 10:03 ` rguenth at gcc dot gnu dot org
` (6 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-04-03 9:54 UTC (permalink / raw)
To: gcc-bugs
------- Comment #23 from rguenth at gcc dot gnu dot org 2008-04-03 09:53 -------
*** Bug 35811 has been marked as a duplicate of this bug. ***
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |jakub at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (24 preceding siblings ...)
2008-04-03 9:54 ` rguenth at gcc dot gnu dot org
@ 2008-04-03 10:03 ` rguenth at gcc dot gnu dot org
2008-05-20 16:33 ` jakub at gcc dot gnu dot org
` (5 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-04-03 10:03 UTC (permalink / raw)
To: gcc-bugs
------- Comment #24 from rguenth at gcc dot gnu dot org 2008-04-03 10:02 -------
"It looks ugly as hell, but i have no problem with it because i'm not
sure you can do better without completely replacing the algorithm :)"
as it seems only wine is affected (and there is the -fno-tree-fre -fno-tree-pre
workaround) I didn't yet bother to apply this patch.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
URL| |http://gcc.gnu.org/ml/gcc-
| |patches/2008-
| |02/msg00759.html
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (25 preceding siblings ...)
2008-04-03 10:03 ` rguenth at gcc dot gnu dot org
@ 2008-05-20 16:33 ` jakub at gcc dot gnu dot org
2008-05-20 18:29 ` rguenth at gcc dot gnu dot org
` (4 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: jakub at gcc dot gnu dot org @ 2008-05-20 16:33 UTC (permalink / raw)
To: gcc-bugs
------- Comment #25 from jakub at gcc dot gnu dot org 2008-05-20 16:32 -------
Richard, could you reconsider that? I know it only affects Wine, but given how
popular Wine is and there many people who compile it on their own, we have many
dups for this in our bugzilla.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (26 preceding siblings ...)
2008-05-20 16:33 ` jakub at gcc dot gnu dot org
@ 2008-05-20 18:29 ` rguenth at gcc dot gnu dot org
2008-05-20 20:41 ` rguenth at gcc dot gnu dot org
` (3 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-05-20 18:29 UTC (permalink / raw)
To: gcc-bugs
------- Comment #26 from rguenth at gcc dot gnu dot org 2008-05-20 18:28 -------
Ok, I'll give it an updated round of testing. Even though it is still ugly as
hell ;)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (27 preceding siblings ...)
2008-05-20 18:29 ` rguenth at gcc dot gnu dot org
@ 2008-05-20 20:41 ` rguenth at gcc dot gnu dot org
2008-05-20 20:58 ` rguenth at gcc dot gnu dot org
` (2 subsequent siblings)
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-05-20 20:41 UTC (permalink / raw)
To: gcc-bugs
------- Comment #27 from rguenth at gcc dot gnu dot org 2008-05-20 20:41 -------
Subject: Bug 35204
Author: rguenth
Date: Tue May 20 20:40:23 2008
New Revision: 135676
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=135676
Log:
2008-05-20 Richard Guenther <rguenther@suse.de>
PR tree-optimization/35204
* tree-ssa-sccvn.c (extract_and_process_scc_for_name): New
helper, split out from ...
(DFS): ... here. Make the DFS walk non-recursive.
Modified:
trunk/gcc/ChangeLog
trunk/gcc/tree-ssa-sccvn.c
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (28 preceding siblings ...)
2008-05-20 20:41 ` rguenth at gcc dot gnu dot org
@ 2008-05-20 20:58 ` rguenth at gcc dot gnu dot org
2008-05-20 20:59 ` rguenth at gcc dot gnu dot org
2008-07-11 11:01 ` marion dot deveaud at siemens dot com
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-05-20 20:58 UTC (permalink / raw)
To: gcc-bugs
------- Comment #28 from rguenth at gcc dot gnu dot org 2008-05-20 20:58 -------
Subject: Bug 35204
Author: rguenth
Date: Tue May 20 20:57:12 2008
New Revision: 135678
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=135678
Log:
2008-05-20 Richard Guenther <rguenther@suse.de>
PR tree-optimization/35204
* tree-ssa-sccvn.c (extract_and_process_scc_for_name): New
helper, split out from ...
(DFS): ... here. Make the DFS walk non-recursive.
Modified:
branches/gcc-4_3-branch/gcc/ChangeLog
branches/gcc-4_3-branch/gcc/tree-ssa-sccvn.c
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (29 preceding siblings ...)
2008-05-20 20:58 ` rguenth at gcc dot gnu dot org
@ 2008-05-20 20:59 ` rguenth at gcc dot gnu dot org
2008-07-11 11:01 ` marion dot deveaud at siemens dot com
31 siblings, 0 replies; 33+ messages in thread
From: rguenth at gcc dot gnu dot org @ 2008-05-20 20:59 UTC (permalink / raw)
To: gcc-bugs
------- Comment #29 from rguenth at gcc dot gnu dot org 2008-05-20 20:58 -------
Fixed.
--
rguenth at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution| |FIXED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread* [Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
2008-02-14 23:13 [Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898 marcus at jet dot franken dot de
` (30 preceding siblings ...)
2008-05-20 20:59 ` rguenth at gcc dot gnu dot org
@ 2008-07-11 11:01 ` marion dot deveaud at siemens dot com
31 siblings, 0 replies; 33+ messages in thread
From: marion dot deveaud at siemens dot com @ 2008-07-11 11:01 UTC (permalink / raw)
To: gcc-bugs
------- Comment #30 from marion dot deveaud at siemens dot com 2008-07-11 11:00 -------
*** Bug 36650 has been marked as a duplicate of this bug. ***
--
marion dot deveaud at siemens dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |marion dot deveaud at
| |siemens dot com
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204
^ permalink raw reply [flat|nested] 33+ messages in thread