[Bug middle-end/54838] New: [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -O2 -ftracer -fno-tree-dce -fno-tree-sra

[Bug middle-end/54838] New: [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -O2 -ftracer -fno-tree-dce -fno-tree-sra

[zsojka at seznam dot cz]

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

             Bug #: 54838
           Summary: [4.8 Regression] ICE: in merge_latch_edges, at
                    cfgloop.c:678 with -O2 -ftracer -fno-tree-dce
                    -fno-tree-sra
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: zsojka@seznam.cz


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

Compiler output:
$ gcc -O2 -ftracer -fno-tree-dce -fno-tree-sra testcase.C
testcase.C: In function '_ForwardIterator1 search(_ForwardIterator1,
_ForwardIterator1)':
testcase.C:113:3: internal compiler error: in merge_latch_edges, at
cfgloop.c:678
   }
   ^
0x840a29 merge_latch_edges
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:678
0x840a29 disambiguate_multiple_latches
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:741
0x840a29 disambiguate_loops_with_multiple_latches()
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:755
0xa49ed4 loop_optimizer_init(unsigned int)
        /mnt/svn/gcc-trunk/gcc/loop-init.c:78
0x12084de fwprop_init
        /mnt/svn/gcc-trunk/gcc/fwprop.c:1412
0x120869a fwprop
        /mnt/svn/gcc-trunk/gcc/fwprop.c:1459
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

Tested revisions:
r192080 - crash
r191586 - crash
4.7 r191640 - OK

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -O2 -ftracer -fno-tree-dce -fno-tree-sra

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-10-07
                 CC|                            |mpolacek at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #1 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-10-07 12:41:57 UTC ---
Confirmed.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -O2 -ftracer -fno-tree-dce -fno-tree-sra

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #2 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-10-07 12:44:53 UTC ---
Started with http://gcc.gnu.org/viewcvs?view=revision&revision=185913

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -O2 -ftracer -fno-tree-dce -fno-tree-sra

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.8.0

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -O2 -ftracer -fno-tree-dce -fno-tree-sra

[zsojka at seznam dot cz]

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

--- Comment #3 from Zdenek Sojka <zsojka at seznam dot cz> 2012-10-18 18:24:42 UTC ---
Created attachment 28486
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28486
another testcase

This ICE seems to happen quite often when testing with 'random' flags...
-ftracer seems to be the common denominator.

$ gcc -O2 -fno-forward-propagate -ftracer testcase.c
testcase.c: In function 'foo':
testcase.c:20:1: internal compiler error: in merge_latch_edges, at
cfgloop.c:678
 }
 ^
linux-vdso.so.1: No such file or directory
0x6a7028 merge_latch_edges
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:678
0x6a7028 disambiguate_multiple_latches
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:741
0x6a7028 disambiguate_loops_with_multiple_latches()
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:755
0x8b2794 loop_optimizer_init(unsigned int)
        /mnt/svn/gcc-trunk/gcc/loop-init.c:78
0x8b285a rtl_loop_initgcc -O2 -fno-forward-propagate -ftracer testcase.c
testcase.c: In function 'foo':
testcase.c:20:1: internal compiler error: in merge_latch_edges, at
cfgloop.c:678
 }
 ^
linux-vdso.so.1: No such file or directory
0x6a7028 merge_latch_edges
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:678
0x6a7028 disambiguate_multiple_latches
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:741
0x6a7028 disambiguate_loops_with_multiple_latches()
        /mnt/svn/gcc-trunk/gcc/cfgloop.c:755
0x8b2794 loop_optimizer_init(unsigned int)
        /mnt/svn/gcc-trunk/gcc/loop-init.c:78
0x8b285a rtl_loop_init
        /mnt/svn/gcc-trunk/gcc/loop-init.c:219
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

        /mnt/svn/gcc-trunk/gcc/loop-init.c:219
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

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

--- Comment #4 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-11-04 02:33:36 UTC ---
Looking into it.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

--- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-11-04 12:49:27 UTC ---
I think the problem is that we somehow arrive at this:
  loop_1 (header = 2, multiple latches, niter = )
  {
    bb_2 (preds = {bb_0 }, succs = {bb_4 bb_3 })
    {
(note 5 0 2 2 [bb 2] NOTE_INSN_BASIC_BLOCK)
(insn 2 5 3 2 (set (reg/v/f:DI 60 [ b ])
        (reg:DI 5 di [ b ])) ./pr54838.c:5 63 {*movdi_internal_rex64}
     (nil))
(insn 3 2 4 2 (set (reg/v/f:DI 61 [ c ])
        (reg:DI 4 si [ c ])) ./pr54838.c:5 63 {*movdi_internal_rex64}
     (nil))
(note 4 3 7 2 NOTE_INSN_FUNCTION_BEG)
(insn 7 4 14 2 (set (reg:SI 59 [ D.1735 ])
        (mem:SI (reg/v/f:DI 61 [ c ]) [2 *c_3(D)+0 S4 A32])) 65
{*movsi_internal}
     (nil))
(insn 14 7 15 2 (set (reg:CCZ 17 flags)
        (compare:CCZ (reg:SI 59 [ D.1735 ])
            (const_int 1 [0x1]))) ./pr54838.c:7 7 {*cmpsi_1}
     (nil))
(jump_insn 15 14 38 2 (set (pc)
        (if_then_else (eq (reg:CCZ 17 flags)
                (const_int 0 [0]))
            (label_ref:DI 20)
            (pc))) ./pr54838.c:7 595 {*jcc_1}
     (expr_list:REG_BR_PROB (const_int 3333 [0xd05])
        (nil))
 -> 20)

    }
  }
, i.e. we have a loop which contains only the header.  The rest of BBs are
there, but in loop_0.  When we call disambiguate_loops_with_multiple_latches,
loop->latch is NULL on that loop, so we end up calling merge_latch_edges, but
that ICEs because VEC_length (edge, latches) is of course 0.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

--- Comment #6 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-11-08 09:12:01 UTC ---
And I'd say that something in bypass_block from cprop.c is the culprit.  Not
calling bypass_block -> no ICE, and compilation proceeds fine.  Working on a
patch.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

--- Comment #7 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-11-24 11:53:19 UTC ---
So, in .cse1 we have:

            ENTRY    
             |   
             |   
             2   
             |   
             |   
   +-------- 4 ----------+
   |        / \          |   
   |       /   \         |   
   |      6     5        |   
   |     /\     |\       |   
   |    /  \    | \      |   
   |   7    3   |  8     |   
   |   |    |   |  /\    /   
   +---|----|   | /  \  /
       |      --10    9/  
       |    -/  
      EXIT-/

(3->4 and 9->4 are back edges).  Now, in bypass_block, when we're trying to
bypass BB 4, we iterate over BB 4's incoming edges.  We skip certain edges
(e.g. complex), then we're iterating over reg_use_table (registers used in
insn).  Here we call
set = find_bypass_set (regno, e->src->index);
If set == NULL, we skip to another iteration.  But in this case the set is not
NULL, and we end up with this:
Redirecting fallthru edge 3->4 to 6
JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 1 [0x1])
Bypass edge from 3->4 to 6
Redirecting fallthru edge 9->4 to 5
JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3 [0x3])
Bypass edge from 9->4 to 5
but how can be two different constants in one reg?  The hash table is:
SET hash table (11 buckets, 3 entries)
Index 0 (hash value 4)
  (reg:SI 59 [ D.1735 ]) := (const_int 1 [0x1])
Index 1 (hash value 5)
  (reg/v/f:DI 60 [ b ]) := (const_int 0 [0])
Index 2 (hash value 4)
  (reg:SI 59 [ D.1735 ]) := (const_int 3 [0x3])

redirect_edge_and_branch_force then redirect edges and BB 4 is gone.

I'd say we cannot redirect edges of BBs which have 2 and more incoming back
edges if in the hash table there are more entries with the same hash values,
but the SRC rtx's differ.  I'll post something to ML.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

--- Comment #8 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-11-26 14:29:59 UTC ---
Patch posted: http://gcc.gnu.org/ml/gcc-patches/2012-11/msg02095.html

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

--- Comment #9 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-12-02 20:17:16 UTC ---
Author: mpolacek
Date: Sun Dec  2 20:16:09 2012
New Revision: 194060

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=194060
Log:
PR54838

Added:
    trunk/gcc/testsuite/gcc.dg/pr54838.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cprop.c
    trunk/gcc/testsuite/ChangeLog

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

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

--- Comment #10 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-12-02 20:17:54 UTC ---
Fixed.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

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

--- Comment #11 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-12-03 09:28:38 UTC ---
Oh, but the C++ testcase still ICEs...

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-12-14 14:58:41 UTC ---
I see the same ICE also during bootstrap if ada/targparm.adb is built with
-fstack-protector (I have -fstack-protector in CFLAGS/CXXFLAGS/XCFLAGS/TCFLAGS
during configure among other things):

/home/jakub/rpmbuild/BUILD/gcc-4.8.0-20121213/obj-x86_64-redhat-linux/./prev-gcc/xgcc
-B/home/jakub/rpmbuild/BUILD/gcc-4.8.0-20121213/obj-x86_64-redhat-linux/./prev-gcc/
-isystem /usr/x86_64-redhat-linux/include -isystem
/usr/x86_64-redhat-linux/sys-include -c -O2 -fstack-protector  -gnatpg -gnata
-gnatwns -W -Wall -nostdinc -I- -I. -Iada -I../../gcc/ada
-I../../gcc/ada/gcc-interface ../../gcc/ada/targparm.adb -o ada/targparm.o
+===========================GNAT BUG DETECTED==============================+
| 4.8.0 20121213 (Red Hat 4.8.0-0.1) (x86_64-redhat-linux) GCC error:      |
| in merge_latch_edges, at cfgloop.c:678                                   |
| Error detected around ../../gcc/ada/targparm.adb:649:8                   |
| Please submit a bug report; see http://gcc.gnu.org/bugs.html.            |
...

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[jakub at gcc dot gnu.org]

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

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-12-14 15:22:37 UTC ---
Actually it is either -fstack-protector or -fprofile-generate or both that
trigger it.  Haven't tried vanilla trunk profiledbootstrap though yet.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[jakub at gcc dot gnu.org]

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

--- Comment #14 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-12-14 15:53:30 UTC ---
Ok, reproduced with vanilla trunk, starting from gcc 4.7.2:
../configure --enable-languages=all,obj-c++,ada,go --enable-checking=release
make -j48 profiledbootstrap

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

--- Comment #15 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-12-14 16:12:48 UTC ---
The issue here is that we have a loop with header and two latches, and via
delete_basic_block we delete both latches (and all edges of those two latches).
 So, we don't have a loop anymore, but the header has still loop_depth > 0,
merge_latch_edges of course ICEs on it, because there's an assert:
gcc_assert (latches.length () > 0);
but the latches are already gone.  I think that in this case we want to just
set the loop->header to NULL (or cancel_loop_tree, or unloop, or...).  What I
have in mind is basically something like:
--- a/gcc/cfghooks.c
+++ b/gcc/cfghooks.c
@@ -552,6 +552,23 @@ delete_basic_block (basic_block bb)
          loops_state_set (LOOPS_NEED_FIXUP);
        }

+      if (loop->header
+         && bb->loop_father != current_loops->tree_root)
+       {
+         edge_iterator ei;
+         edge e;
+         unsigned n_back_edges = 0;
+
+         FOR_EACH_EDGE (e, ei, loop->header->preds)
+           if (e->flags & EDGE_DFS_BACK)
+             n_back_edges++;
+
+         if (n_back_edges == 0)
+           {
+             loop->header = NULL;
+             loops_state_set (LOOPS_NEED_FIXUP);
+           }
+       }
       remove_bb_from_loops (bb);
     }
this fixes this ICE, but causes other ICEs.

I'd be really really grateful for any hints.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

--- Comment #16 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-12-14 16:14:58 UTC ---
(The reason why we don't have a loop anymore is simply that the header doesn't
have any incoming back edges after removing the latches.  There of course may
be other loops in the CFG.)

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[mpolacek at gcc dot gnu.org]

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

--- Comment #17 from Marek Polacek <mpolacek at gcc dot gnu.org> 2012-12-14 16:37:39 UTC ---
Now I don't know why we'd need that hunk, the code for handling latch/header is
just above it, only loop->latch is NULL, because there are more of them.  Sorry
for the noise, I'll be looking into it over the weekend.

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[rguenth at gcc dot gnu.org]

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

--- Comment #18 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-18 14:39:55 UTC ---
Author: rguenth
Date: Tue Dec 18 14:39:49 2012
New Revision: 194582

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=194582
Log:
2012-12-18  Richard Biener  <rguenther@suse.de>

    PR middle-end/54838
    * cfgloopmanip.c (fix_loop_structure): Re-discover latch
    edges first and mark loops for removal if no latch edges remain.
    Properly re-create LOOPS_HAVE_FALLTHRU_PREHEADERS.
    * loop-init.c (loop_optimizer_finalize): Set
    LOOPS_MAY_HAVE_MULTIPLE_LATCHES.

    * g++.dg/torture/pr54838.C: New testcase.

Added:
    trunk/gcc/testsuite/g++.dg/torture/pr54838.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cfgloopmanip.c
    trunk/gcc/loop-init.c
    trunk/gcc/testsuite/ChangeLog

[Bug middle-end/54838] [4.8 Regression] ICE: in merge_latch_edges, at cfgloop.c:678 with -ftracer

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #19 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-18 14:40:28 UTC ---
Fixed.