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

["rguenther at suse dot de" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #10 from rguenther at suse dot de <rguenther at suse dot de> 2012-08-23 07:29:04 UTC ---
On Wed, 22 Aug 2012, steven at gcc dot gnu.org wrote:

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

Well, yes - the patch isn't really a fix for the issue but addresses
something I noticed in the loop detection code.  Namely that it happily
detects a loop like (1)

  header
   |  \
  (ab) |
   |   /
  latch

thus, a loop where there isn't a single path in the CFG that is
non-abnormal/EH.  That isn't a "useful" loop.  Loops with EH are still
handled as they look like (2)

  header ---
   |         \
  BB          \
  / \          \
(eh) (fallthru)|
 /   |         |
   latch--------

thus, EH edges should also not form loops but always act as loop
exits.

That patch masks the underlying issue of course, but I still think
loops of the form (1) are not useful (we cannot perform a reasonable
loop transform on it - we can handle abnormal / eh exits and entries
but not loop paths).

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

The patch is of couse a "big hammer" because it has a cost, but IMHO
it still makes sense.