Confirmed.

Started with http://gcc.gnu.org/viewcvs?view=revision&revision=185913

Created attachment 28486 [details]
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.

Looking into it.

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.

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.

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.

Patch posted: http://gcc.gnu.org/ml/gcc-patches/2012-11/msg02095.html

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

Fixed.

Oh, but the C++ testcase still ICEs...

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

Actually it is either -fstack-protector or -fprofile-generate or both that trigger it.  Haven't tried vanilla trunk profiledbootstrap though yet.

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

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.

(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.)

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.

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

Fixed.