[Bug rtl-optimization/56181] [4.8 Regression] ICE in verify_loop_structure, at cfgloop.c:1581 with -ftracer

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> 2013-02-06 10:45:35 UTC ---
I think the issue is that we are duplicating a loop header.  Yes, we somehow
lost (or did not detect) this loop - we don't discover new loops after we
start preserving them - and if we do duplicate a loop header the loop
fixup machinery is confused (I suppose it is confused anyway if there are
un-detected loops in the CFG).

If I force re-detection of loops tracer won't duplicate the block because
it's a loop header.  Thus I suppose removing that check would somehow trigger
the real issue with fixup.

Ah, what happens is that duplicating bb4 causes loop 3 to become nested
in loop 2.  The fixup machinery does not support that:

  /* Rescan the bodies of loops, starting from the outermost ones.  We assume
     that no optimization interchanges the order of the loops, i.e., it cannot
     happen that L1 was superloop of L2 before and it is subloop of L2 now
     (without explicitly updating loop information).  At the same time, we also
     determine the new loop structure.  */

even though it does not explicitely mention the insert.

Thus,

"So, what happens here is that tracer performs tail-duplication.  That is per
se
of course fine, but when we're re-scanning bodies in fix_loop_structure, we
correctly mark BBs in the loop 1, then the loop 3, but then when processing the
loop 2, in flow_loop_nodes_find, we mark tail-duplicated BB as belonging into
the loop 2, because
  FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
    {    
      if (latch->src->loop_father == loop 
          || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
        continue;
doesn't notice that the BB is in fact outside of the loop.  Which is bad - we
then process predecessors of that BB and mark the BBs in loop 3 as belonging
into loop 2.  Oops."

is correct after all.  What we fail to realize is that loop nesting changed,
because we visit loops in order 1, 3, 2 in

  FOR_EACH_LOOP (li, loop, 0)
    {
      superloop[loop->num] = loop->header->loop_father;
      loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
    }

and thus superloop[loop->num] is wrong and flow_loop_nodes_find overrides
loop 3 children.  To deal with arbitrary nesting changes we'd have to
visit loop headers in reverse completion order as flow_loops_find does.

There are three ways to fix this
  1. make tracer detect it is in fact duplicating a loop header
  2. make this loop discovered in the first place
  3. make fixup_loop_structure deal with arbitrary nesting changes

We probably should work towards 2. anyway (which would need a verification
part).  Then 1. would be naturally handled.  I don't like 3. too much - we'd
move more and more towards a full flow_loops_find with simply preserving
existing loop members.

So I suggest to tackle 2. by first implementing in the verifier the
search for loop headers (simply factor that out from flow_loops_find,
the loop that populates the headers sbitmap, and verify that each
header is it's own header - header->loop_father->header == header).