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

["steven at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

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

--- Comment #6 from Steven Bosscher <steven at gcc dot gnu.org> 2012-08-22 19:26:03 UTC ---
(In reply to comment #4)

Wouldn't this patch disable all loop detection for loops with exceptions and so
on in them? That seems a rather big hammer to this problem. It should be enough
to check only for EH_ABNORMAL.

What caused the ICE to appear anyway? There is a problem I can see in
dfs_enumerate_from that could cause it to ICE.

At the point of the ICE, we have the following CFG (cc1 -O2 -ftracer):

(gdb) p current_pass->name
$5 = 0x13195b0 "local-pure-const"
(gdb) p brief_dump_cfg(stderr,-1)
;; basic block 2, loop depth 0, count 0, freq 6667, maybe hot
;;  prev block 0, next block 3, flags: (NEW, REACHABLE)
;;  pred:       ENTRY [100.0%]  (FALLTHRU,EXECUTABLE)
;;  succ:       3 [100.0%]  (FALLTHRU,EXECUTABLE)
;; basic block 3, loop depth 0, count 0, freq 6667, maybe hot
;;  prev block 2, next block 4, flags: (NEW, REACHABLE, IRREDUCIBLE_LOOP)
;;  pred:       2 [100.0%]  (FALLTHRU,EXECUTABLE)
;;  succ:       5 [100.0%]  (FALLTHRU,IRREDUCIBLE_LOOP,EXECUTABLE)
;; basic block 4, loop depth 0, count 0, freq 0
;; Invalid sum of incoming frequencies 3333, should be 0
;;  prev block 3, next block 5, flags: (NEW, REACHABLE, IRREDUCIBLE_LOOP)
;;  pred:       5 [33.3%]  (ABNORMAL,IRREDUCIBLE_LOOP,EXECUTABLE)
;;  succ:       5 [100.0%]  (FALLTHRU,DFS_BACK,IRREDUCIBLE_LOOP,EXECUTABLE)
;; basic block 5, loop depth 1, count 0, freq 10000, maybe hot
;;  prev block 4, next block 6, flags: (NEW, REACHABLE)
;;  pred:       4 [100.0%]  (FALLTHRU,DFS_BACK,IRREDUCIBLE_LOOP,EXECUTABLE)
;;              6 [100.0%]  (FALLTHRU,DFS_BACK,EXECUTABLE)
;;              3 [100.0%]  (FALLTHRU,IRREDUCIBLE_LOOP,EXECUTABLE)
;;  succ:       4 [33.3%]  (ABNORMAL,IRREDUCIBLE_LOOP,EXECUTABLE)
;;              6 [33.3%]  (ABNORMAL,EXECUTABLE)
;;              7 [33.3%]  (ABNORMAL,EXECUTABLE)
;; basic block 6, loop depth 1, count 0, freq 3333, maybe hot
;;  prev block 5, next block 7, flags: (NEW, REACHABLE)
;;  pred:       5 [33.3%]  (ABNORMAL,EXECUTABLE)
;;  succ:       5 [100.0%]  (FALLTHRU,DFS_BACK,EXECUTABLE)
;; basic block 7, loop depth 0, count 0, freq 3333, maybe hot
;;  prev block 6, next block 1, flags: (NEW, REACHABLE)
;;  pred:       5 [33.3%]  (ABNORMAL,EXECUTABLE)
;;  succ:       EXIT [100.0%]

Or in human-readable form:

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

where "(a)" denotes abnormal edge, of course, and (0) or (1) is the loop depth
at this point.

The loop detected here is the region with the abnormal edges, for blocks 4, 5,
and 6. The detected "loop" has header bb 5 and latch bb 6, which is not clearly
wrong: this is just two loops with the same header. But this confuses
dfs_enumerate_from, which does a reverse DFS from basic block 5 with predicate
glb_enum_p. The DFS visits block 5, 4, and 6, but dfs_enumerate_from is told to
expect to visit only 2 basic blocks, not 3. The reason it sees 3 is that
glb_enum_p is this:

/* Enumeration predicate for get_loop_body_with_size.  */
static bool
glb_enum_p (const_basic_block bb, const void *glb_loop)
{
  const struct loop *const loop = (const struct loop *) glb_loop;
  return (bb != loop->header
          && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
}

called with loop->header == bb5, and called with bb==4 and bb==6. And since bb5
dominates both bb4 and bb6, the predicate returns true for both, and
dfs_enumerate_from ends up visiting 3 basic blocks. So why is it told to expect
two blocks in the first place, instead of 3?

dfs_enumerate_from is called, via get_loop_body_with_size, from get_loop_body:

    tv = get_loop_body_with_size (loop, body, loop->num_nodes);

The natural loop 1 has only two nodes, namely bb5 and bb6. So where does bb4
come from? That's tracer at work.

So the root cause here, is that tracer should either update the loop tree or
refrain from duplicating blocks if it results in a single loop header
dominating two separate loops.

Irreducibility and updating the loop tree are the key to fixing this bug, not
the big hammer patch of comment #4.