[Bug middle-end/53695] [4.8 Regression] ICE: in dfs_enumerate_from, at cfganal.c:1221 with -O2 -ftracer and labels/gotos

["stevenb.gcc at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #15 from stevenb.gcc at gmail dot com <stevenb.gcc at gmail dot com> 2012-08-23 08:49:32 UTC ---
On Thu, Aug 23, 2012 at 10:07 AM, rguenther at suse dot de
<gcc-bugzilla@gcc.gnu.org> wrote:
> Already the input to tracer is "wrong" in that we have "lost"
> a loop, the one with abnormal path from latch to header (which
> we _do_ reject during loop discovery!).

But this isn't a natural loop. It's an irreducible loop with loop
entries in basic block 3 and basic block 4 (in the pre-tracer CFG from
comment #7) and loop discovery doesn't record irreducible loop.

What tracer does here is known as "node splitting" to make an
irreducible region reducible. I don't think it's a
intentional/conscious node splitting but tracer does have the effect
of node splitting. After tracer, the loop with bbs {4,5,3} is a
natural loop and the CFG is reducible.


>  So what happens is
> that we turn this "loop" into one that would have been recognized,
> swap header and latch and thus get the abnormal edge to a tolerated
> place (header to latch).  That inconsistency is what my patch tries
> to address (another way would be to simply allow EH/abnormal
> latch -> header edges as well).

But with your patch we'd also reject all already reducible loops if
there are only paths with one or more abnormal edges from the loop
header to the latch. That is more conservative than necessary. Also,
AFAIU, with your patch we'd reduce loops with a finally block
(something like
"for(;;){try{...maybe_throw;...;if(...)break;}finally{...}}") because
all paths to the loop latch would go through the finally block via EH
edges.


> but it does not add bb3 to loop1, nor zero out its latch
> and setting may-have-multiple-latches.

That, to me, is the bug we should try to solve here.

>  The cfghook
> only takes care of updating the loop structure with
> respect to the _new_ basic block but does not consider
> that the old one magically becomes part of a loop.

I think it may be possible to construct a test case just like this one
with an initially irreducible CFG that tracer makes reducible.

Anyway, consider this test case, which is the pre-tracer CFG but
without abnormal edges:

void do_something_1 (void);
void do_something_2 (void);
int some_cond (void);
void make_bb_non_empty ();

void
foo (void)
{
bb2:
  make_bb_non_empty ();
  goto bb3;

bb4:
  switch (some_cond ())
    {
    case 1:
      goto bb3;
    case 2:
      goto bb5;
    default:
      goto bb6;
    }

bb3:
  do_something_1 ();
  goto bb4;

bb5:
  do_something_2 ();
  goto bb4;

bb6:
  return;
}

This gives the following CFG in the .129t.cddce2 dump:

; 3 loops found
;;
;; Loop 0
;;  header 0, latch 1
;;  depth 0, outer -1
;;  nodes: 0 1 2 3 4 5 6 7
;;
;; Loop 1
;;  header 5, latch 4
;;  depth 1, outer 0
;;  nodes: 5 4 3 6
;;
;; Loop 2
;;  header 3, latch 6
;;  depth 2, outer 1
;;  nodes: 3 6

   ENTRY
     |
     V
     |
    2(0)
     |
     |
     V
     |
     | +--4(1)-+
     | |       |
     | V       ^
     | |       |
     | |       +
     | +      /
     | |     /
     5(1)->-3(2)->-6(2)-+
           /\           |
          /  +-----<----+
         /
        |
        V
        |
       7(0)
        |
       EXIT

So now the loop {5,4,3,6} is detected, even though the CFG is
basically the same as the pre-tracer one from comment #7 (only
difference is that the critical edge <3,5> in the above CFG is split
to give basic block 4.

Makes me wonder why the loop isn't recognized in the original test case...