[Bug tree-optimization/47615] New: [4.6 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[Bug tree-optimization/47615] New: [4.6 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[zsojka at seznam dot cz]

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

           Summary: [4.6 Regression] ICE: too deep recursion in
                    phi_translate/phi_translate_1 with -ftree-pre
                    -fno-tree-fre -fno-tree-sra
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: zsojka@seznam.cz
              Host: x86_64-pc-linux-gnu
            Target: x86_64-pc-linux-gnu


Created attachment 23250
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23250
auto-reduced testcase

Compiler output:
$ gcc -O -fstrict-aliasing -ftree-pre -fno-tree-fre -fno-tree-sra testcase.C
gcc: internal compiler error: Segmentation fault (program cc1plus)
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

(gdb) bt
#0  0x00007ffff643711c in _int_malloc () from /lib/libc.so.6
#1  0x00007ffff64399d0 in malloc () from /lib/libc.so.6
#2  0x00000000011f9c40 in xrealloc (oldmem=<value optimized out>, size=152) at
/mnt/svn/gcc-trunk/libiberty/xmalloc.c:177
#3  0x0000000000bea372 in vec_heap_o_reserve_1 (vec=0x0, reserve=<value
optimized out>, vec_offset=<value optimized out>, 
    elt_size=<value optimized out>, exact=<value optimized out>) at
/mnt/svn/gcc-trunk/gcc/vec.c:321
#4  0x0000000000b1b800 in VEC_vn_reference_op_s_heap_copy (expr=0x197b120,
set1=0x197e0c8, set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-sccvn.h:86
#5  phi_translate_1 (expr=0x197b120, set1=0x197e0c8, set2=0x0,
pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1623
#6  0x0000000000b1bc8c in phi_translate (expr=0x197b120, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1858
#7  phi_translate (expr=0x197b120, set1=0x197e0c8, set2=0x0,
pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1835
#8  0x0000000000b1b8e9 in phi_translate_1 (expr=0x197c030, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1570
#9  0x0000000000b1bc8c in phi_translate (expr=0x197c030, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1858
#10 phi_translate (expr=0x197c030, set1=0x197e0c8, set2=0x0,
pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1835
#11 0x0000000000b1b8e9 in phi_translate_1 (expr=0x197b120, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1570
#12 0x0000000000b1bc8c in phi_translate (expr=0x197b120, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1858
#13 phi_translate (expr=0x197b120, set1=0x197e0c8, set2=0x0,
pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1835
#14 0x0000000000b1b8e9 in phi_translate_1 (expr=0x197c030, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1570
#15 0x0000000000b1bc8c in phi_translate (expr=0x197c030, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1858
#16 phi_translate (expr=0x197c030, set1=0x197e0c8, set2=0x0,
pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1835
#17 0x0000000000b1b8e9 in phi_translate_1 (expr=0x197b120, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1570
#18 0x0000000000b1bc8c in phi_translate (expr=0x197b120, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1858
#19 phi_translate (expr=0x197b120, set1=0x197e0c8, set2=0x0,
pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1835
#20 0x0000000000b1b8e9 in phi_translate_1 (expr=0x197c030, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1570
#21 0x0000000000b1bc8c in phi_translate (expr=0x197c030, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1858
#22 phi_translate (expr=0x197c030, set1=0x197e0c8, set2=0x0,
pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1835
#23 0x0000000000b1b8e9 in phi_translate_1 (expr=0x197b120, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)
    at /mnt/svn/gcc-trunk/gcc/tree-ssa-pre.c:1570
#24 0x0000000000b1bc8c in phi_translate (expr=0x197b120, set1=0x197e0c8,
set2=0x0, pred=0x7ffff5a484e0, phiblock=0x7ffff5a48548)

Tested revisions:
r169824 - crash
4.5.2 - OK

[Bug tree-optimization/47615] [4.6 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[hjl.tools at gmail dot com]

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

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.02.05 14:58:11
                 CC|                            |rguenth at gcc dot gnu.org
   Target Milestone|---                         |4.6.0
     Ever Confirmed|0                           |1

--- Comment #1 from H.J. Lu <hjl.tools at gmail dot com> 2011-02-05 14:58:11 UTC ---
It is caused by revision 169089:

http://gcc.gnu.org/ml/gcc-cvs/2011-01/msg00711.html

[Bug tree-optimization/47615] [4.6 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-07 10:10:04 UTC ---
Huh.  Mine.

[Bug tree-optimization/47615] [4.6 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-07 14:50:43 UTC ---
;; basic block 2, loop depth 0, count 0
;; prev block 0, next block 11
;; pred:       ENTRY [100.0%]  (fallthru,exec)
;; succ:       11 [50.0%]  (true,exec) 3 [50.0%]  (false,exec)
<bb 2>:
p_y_5 = p_nd_2(D)->m_p_parent;
p_y_5->m_p_right = p_nd_2(D);
D.3165.m_p_nd = p_nd_2(D);
node_it = D.3165;
if (D.3177_7(D) != 0)
  goto <bb 11>;
else
  goto <bb 3>;

...

;; basic block 5, loop depth 0, count 0
;; prev block 12, next block 6
;; pred:       4 [61.0%]  (false,exec)
;; succ:       6 [100.0%]  (fallthru,exec)
<bb 5>:
D.3176_15 = r_child_it.m_p_nd;
r_rank_16 = MEM[(const long unsigned int &)D.3176_15 + 16];

;; basic block 6, loop depth 0, count 0
;; prev block 5, next block 13
;; pred:       12 [100.0%]  (fallthru) 5 [100.0%]  (fallthru,exec)
;; succ:       13 [50.0%]  (true,exec) 7 [50.0%]  (false,exec)
<bb 6>:
# r_rank_19 = PHI <1(12), r_rank_16(5)>
D.3178_17 = node_it.m_p_nd;
D.3184_20 = r_rank_19 + l_rank_18;
MEM[(long unsigned int &)D.3178_17 + 16] = D.3184_20;
D.3160_6 = p_nd_2(D)->m_p_parent;
D.3189.m_p_nd = D.3160_6;
node_it = D.3189;
if (D.3201_21(D) != 0)
  goto <bb 13>;
else
  goto <bb 7>;

<bb 13>:
  goto <bb 8>;

<bb 7>:
  # VUSE <.MEM_47>
  D.3199_23 = l_child_it.m_p_nd;
  # VUSE <.MEM_47>
  l_rank_24 = MEM[(const long unsigned int &)D.3199_23 + 16];

<bb 8>:
  # l_rank_32 = PHI <1(13), l_rank_24(7)>
  # VUSE <.MEM_47>
  D.3206_25 = node_it.m_p_nd;
  # VUSE <.MEM_47>
  D.3207_26 = D.3206_25->m_p_right;


translating
  {component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35
to BB 5 results in translating
  {component_ref<m_p_parent>,mem_ref<0B>,p_nd_2(D)}@.MEM_3(D)
which is the leader for p_y_5 which results in translating
  {component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35
which is the leader for p_nd_2(D)

and we end up with a cycle.  D.3206_25 is value-numbered to p_y_5
by SCCVN which looks ok.

The problem seems to be that we have a cycle for leaders. Simply caused by

p_y_5 = p_nd_2(D)->m_p_parent;
p_y_5->m_p_right = p_nd_2(D);

what seems bogus is that p_nd_2(D) isn't the leader for itself but
p_y_5->m_p_right is.

The issue is that we look at the intersection of the current ANTIC set

{ {component_ref<m_p_parent>,mem_ref<0B>,p_nd_2(D)}@.MEM_3(D) (0005), l_rank_18
(0012), r_rank_19 (0013), {plus_expr,l_rank_18,r_rank_19} (0014),
{component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35 (0002) }

with the expression set of the value

{ p_nd_2(D) (0002), {component_ref<m_p_nd>,D.3165}@.MEM_37 (0002), D.3182_11
(0002), D.3178_17 (0002), D.3207_26 (0002),
{component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35 (0002),
{component_ref<m_p_nd>,D.3205}@.MEM_49 (0002), D.3200_29 (0002) }

and the only common one is {component_ref<m_p_right>,mem_ref<0B>,p_y_5}@.MEM_35
(0002), p_nd_2(D) isn't ANTIC itself (which is what the referenced patch
changed - previously we'd recognized that the original reference we
now try to translate is equal to p_nd_2(D)).

It looks like fixing this disparity is the easiest thing we can do ...

[Bug tree-optimization/47615] [4.6 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-07 16:58:20 UTC ---
Author: rguenth
Date: Mon Feb  7 16:58:17 2011
New Revision: 169888

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=169888
Log:
2011-02-07  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/47615
    * tree-ssa-sccvn.h (run_scc_vn): Take a vn-walk mode argument.
    * tree-ssa-sccvn.c (default_vn_walk_kind): New global.
    (run_scc_vn): Initialize it.
    (visit_reference_op_load): Use it.
    * tree-ssa-pre.c (execute_pre): Use VN_WALK if in PRE.

    * g++.dg/opt/pr47615.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/opt/pr47615.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-pre.c
    trunk/gcc/tree-ssa-sccvn.c
    trunk/gcc/tree-ssa-sccvn.h

[Bug tree-optimization/47615] [4.5 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.6.0
   Target Milestone|4.6.0                       |4.5.3
            Summary|[4.6 Regression] ICE: too   |[4.5 Regression] ICE: too
                   |deep recursion in           |deep recursion in
                   |phi_translate/phi_translate |phi_translate/phi_translate
                   |_1 with -ftree-pre          |_1 with -ftree-pre
                   |-fno-tree-fre -fno-tree-sra |-fno-tree-fre -fno-tree-sra
      Known to fail|4.6.0                       |4.5.3

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-07 16:59:44 UTC ---
Fixed on trunk, latent on the branch still.

[Bug tree-optimization/47615] [4.5 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-03-02 13:56:48 UTC ---
Author: rguenth
Date: Wed Mar  2 13:56:41 2011
New Revision: 170614

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=170614
Log:
2011-03-02  Richard Guenther  <rguenther@suse.de>

    Backport from mainline
    2011-02-07  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/47615
    * tree-ssa-sccvn.h (run_scc_vn): Take a vn-walk mode argument.
    * tree-ssa-sccvn.c (default_vn_walk_kind): New global.
    (run_scc_vn): Initialize it.
    (visit_reference_op_load): Use it.
    * tree-ssa-pre.c (execute_pre): Use VN_WALK if in PRE.

    * g++.dg/opt/pr47615.C: New testcase.

Added:
    branches/gcc-4_5-branch/gcc/testsuite/g++.dg/opt/pr47615.C
Modified:
    branches/gcc-4_5-branch/gcc/ChangeLog
    branches/gcc-4_5-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_5-branch/gcc/tree-ssa-pre.c
    branches/gcc-4_5-branch/gcc/tree-ssa-sccvn.c
    branches/gcc-4_5-branch/gcc/tree-ssa-sccvn.h

[Bug tree-optimization/47615] [4.5 Regression] ICE: too deep recursion in phi_translate/phi_translate_1 with -ftree-pre -fno-tree-fre -fno-tree-sra

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-03-02 13:57:17 UTC ---
Fixed.