[Bug tree-optimization/55833] New: ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[Bug tree-optimization/55833] New: ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[antoine.balestrat at gmail dot com]

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

             Bug #: 55833
           Summary: ICE in verify_loop_structure, at cfgloop.c:1582 (BB
                    should be marked irreducible !)
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: antoine.balestrat@gmail.com


Using GCC 4.8.0 as of 20121231 :

$ cat bb.c
int a, b, c;

void foo()
{
    unsigned d, l, *p, k = 1;

    if(bar())
    {
label:
        if((a = a <= 0))
        {
            if(c)
                d = b;

            if (b || d ? l : k ? : 0)
                a = d = 0;

            goto label;
        }
    }

    while(*p++)
        goto label;
}

$ xgcc -w -O3 bb.c
bb.c: In function ‘foo’:
bb.c:24:1: error: edge from 27 to 29 should be marked irreducible
 }
 ^
bb.c:24:1: error: basic block 29 should be marked irreducible
bb.c:24:1: error: edge from 29 to 7 should be marked irreducible
bb.c:24:1: internal compiler error: in verify_loop_structure, at cfgloop.c:1582
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

[Bug tree-optimization/55833] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.5.4, 4.6.3, 4.8.0

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-31 16:39:39 UTC ---
Confirmed.  Also happens with 4.5 and 4.6 at least.

[Bug tree-optimization/55833] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[mpolacek at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-01-02
                 CC|                            |mpolacek at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #2 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-01-02 10:33:06 UTC ---
Thus marking as NEW.  Related to PR52996.

[Bug tree-optimization/55833] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[mpolacek at gcc dot gnu.org]

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

--- Comment #3 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-01-02 11:22:00 UTC ---
Cannot reproduce with xgcc (GCC) 4.6.4 20130102 (prerelease).

[Bug tree-optimization/55833] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-02 11:30:37 UTC ---
(In reply to comment #3)
> Cannot reproduce with xgcc (GCC) 4.6.4 20130102 (prerelease).

Make sure to have checking enabled.

[Bug rtl-optimization/55833] [4.6/4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|tree-optimization           |rtl-optimization
      Known to work|                            |4.1.2, 4.7.2
   Target Milestone|---                         |4.6.4
            Summary|ICE in                      |[4.6/4.8 Regression] ICE in
                   |verify_loop_structure, at   |verify_loop_structure, at
                   |cfgloop.c:1582 (BB should   |cfgloop.c:1582 (BB should
                   |be marked irreducible !)    |be marked irreducible !)
      Known to fail|                            |4.3.6

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-02 11:33:28 UTC ---
Also fails with 4.3.6, works with 4.1.2 though.  Thus, technically a
regression.
Seems to work with 4.7 as well.

RTL unswitching.

[Bug rtl-optimization/55833] [4.6/4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug rtl-optimization/55833] [4.6/4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-10 15:02:37 UTC ---
By unswitching on an exit test that exits to the enclosing loop we create
an unswitched loop that is now reached by what looks like an exit test
of the outer loop which is part of an irreducible region.

I'm not sure we can reliably detect all cases we need to manually mark
the entry edge for.  So ... re-mark_irreducible_loops () after each
transform?

And cheaper checking by

Index: loop-unswitch.c
===================================================================
--- loop-unswitch.c     (revision 195085)
+++ loop-unswitch.c     (working copy)
@@ -145,12 +145,7 @@ unswitch_loops (void)
   /* Go through inner loops (only original ones).  */

   FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
-    {
-      unswitch_single_loop (loop, NULL_RTX, 0);
-#ifdef ENABLE_CHECKING
-      verify_loop_structure ();
-#endif
-    }
+    unswitch_single_loop (loop, NULL_RTX, 0);

   iv_analysis_done ();
 }
@@ -370,6 +365,10 @@ unswitch_single_loop (struct loop *loop,
   nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
   gcc_assert (nloop);

+#ifdef ENABLE_CHECKING
+  verify_loop_structure ();
+#endif
+
   /* Invoke itself on modified loops.  */
   unswitch_single_loop (nloop, rconds, num + 1);
   unswitch_single_loop (loop, conds, num + 1);

[Bug rtl-optimization/55833] [4.6/4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[mpolacek at gcc dot gnu.org]

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

--- Comment #7 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-01-10 15:11:34 UTC ---
(In reply to comment #6)
> By unswitching on an exit test that exits to the enclosing loop we create
> an unswitched loop that is now reached by what looks like an exit test
> of the outer loop which is part of an irreducible region.
> 
> I'm not sure we can reliably detect all cases we need to manually mark
> the entry edge for.  So ... re-mark_irreducible_loops () after each
> transform?

Yeah, I'm looking into this for quite some time now and this occurred me too. 
I'm going to prepare some patch (together with your version of cheaper
checking).

[Bug rtl-optimization/55833] [4.6/4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[mpolacek at gcc dot gnu.org]

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

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 #8 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-01-10 15:18:33 UTC ---
BTW, here is the CFG right before the verify_loops_structure (), which fails:
http://people.redhat.com/mpolacek/src/pr55833.png

[Bug rtl-optimization/55833] [4.6/4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-10 15:22:46 UTC ---
Zdenek may also have an idea here.

[Bug rtl-optimization/55833] [4.6/4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[mpolacek at gcc dot gnu.org]

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

--- Comment #10 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-01-17 19:20:27 UTC ---
Author: mpolacek
Date: Thu Jan 17 19:19:37 2013
New Revision: 195280

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=195280
Log:
Fix PR55833.

Added:
    trunk/gcc/testsuite/gcc.dg/pr55833.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/cfgloopmanip.c
    trunk/gcc/loop-unswitch.c
    trunk/gcc/testsuite/ChangeLog

[Bug rtl-optimization/55833] [4.6/4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[mpolacek at gcc dot gnu.org]

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

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

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

--- Comment #11 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-01-17 19:22:11 UTC ---
Fixed.

[Bug rtl-optimization/55833] [4.6 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[mpolacek at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |ASSIGNED
         Resolution|FIXED                       |
      Known to fail|4.8.0                       |

--- Comment #12 from Marek Polacek <mpolacek at gcc dot gnu.org> 2013-01-17 19:44:10 UTC ---
Considering backporting to 4.6.

[Bug rtl-optimization/55833] [4.6 Regression] ICE in verify_loop_structure, at cfgloop.c:1582 (BB should be marked irreducible !)

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ice-checking
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |4.8.0
         Resolution|                            |FIXED
   Target Milestone|4.6.4                       |4.8.0

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-18 10:20:00 UTC ---
(In reply to comment #12)
> Considering backporting to 4.6.

It's a checking verification failure only, also it's likely latent on the
4.7 branch.

RM says FIXED in 4.8, not to be backported.