[Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[Bug middle-end/35204] New: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[marcus at jet dot franken dot de]

gcc -m32 -O2 -c menu.i -o menu.o
gcc: Internal error: Segmentation fault (program cc1)
Please submit a full bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

gdb ...cc1
(gdb) r -fpreprocessed menu.i -dumpbase menu.i -m32 -mtune=generic
-auxbase-strip menu.o -g -O2 -Wdeclaration-after-statement -Wwrite-strings
-Wtype-limits -Wpointer-arith -Wall -version -fPIC -fno-strict-aliasing
-fstack-protector -o menu.s

....

Program received signal SIGSEGV, Segmentation fault.
DFS (name=0x2afc53f324e0) at
/home/marcus/projects/gcc/gcc/tree-ssa-sccvn.c:1875
1875      VN_INFO (name)->dfsnum = next_dfs_num++;
(gdb) bt
#0  DFS (name=0x2afc53f324e0) at
/home/marcus/projects/gcc/gcc/tree-ssa-sccvn.c:1875
#1  0x00000000007f41be in DFS (name=0x2afc53f365a0) at
/home/marcus/projects/gcc/gcc/tree-ssa-sccvn.c:1898
#2  0x00000000007f41be in DFS (name=0x2afc53f3a5a0) at
/home/marcus/projects/gcc/gcc/tree-ssa-sccvn.c:1898
#3  0x00000000007f41be in DFS (name=0x2afc53f3ea20) at
/home/marcus/projects/gcc/gcc/tree-ssa-sccvn.c:1898
#4  0x00000000007f41be in DFS (name=0x2afc53f42a80) at
/home/marcus/projects/gcc/gcc/tree-ssa-sccvn.c:1898
#5  0x00000000007f41be in DFS (name=0x2afc53f46ae0) at
/home/marcus/projects/gcc/gcc/tree-ssa-sccvn.c:1898
....


-- 
           Summary: crash by too deep recursion in DFS tree-ssa-sccvn.c:1898
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: marcus at jet dot franken dot de
 GCC build triplet: x86_64-unknown-linux-gnu
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: x86_64-unknown-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35204

[Bug middle-end/35204] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[marcus at jet dot franken dot de]

------- 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

[Bug middle-end/35204] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[marcus at jet dot franken dot de]

------- 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

[Bug middle-end/35204] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[marcus at jet dot franken dot de]

------- 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

[Bug middle-end/35204] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[marcus at jet dot franken dot de]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[steven at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[steven at gcc dot gnu dot org]

-- 

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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenther at suse dot de]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[steven at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[marcus at jet dot franken dot de]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[steven at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[steven at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[dberlin at dberlin dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

-- 

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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[jakub at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[rguenth at gcc dot gnu dot org]

------- 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

[Bug middle-end/35204] [4.3/4.4 Regression] crash by too deep recursion in DFS tree-ssa-sccvn.c:1898

[marion dot deveaud at siemens dot com]

------- 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