[Bug tree-optimization/15993] New: Compiler hangs at -O3

["dalej at apple dot com" <gcc-bugzilla at gcc dot gnu dot org>]

The following (derived from the gnu "go" program) hangs at compile time in
lno-branch with -O3.  Partial analysis follows.


extern unsigned char baz[421];
int 
foo(int i1, int i2, int j1, int j2)
{
  int x, y;

  if (i1 > i2)
    return foo(i2, i1, j1, j2);
  if (j1 > j2)
    return foo(i1, i2, j2, j1);

  for (x = i1; x <= i2; x++)
    for (y = j1; y <= j2; y++)
      if (baz[21 + x*20 + y] != 0)
        return 0;
  return 1;
}

1) the tree inliner does exactly the right thing, eliminating all recursion and making 4 copies of the 
bottom loop, exactly one of which gets executed.
2) well maybe not quite the right thing, because there's a 5th loop in the trees, at the top, with 4
exits, one that leads to each of the 4 copeis of the loop.  None of the paths that lead to the
bottom of the 5th loop can actually get executed because, for example, i1<j1 and i1>j1 would
both have to be true.  Something like this happens on each possible path to the loopback.
This is peculiar but I don't think the trees are wrong at this point; i.e. they're a semantically
equivalent representation of the input program.
3) the loop code figures out correctly that all the tests inside the top loop are invariant, and
pulls them out.  This leaves the top loop with no exit, but it cannot be reached, so while
this is even more peculiar I don't think the trees are wrong here either.
4) the (3rd pass of) the dominator opts go into a loop dealing with this cfg.  It changes the cfg on
each pass, but then deletes what it inserted (it also adds some additional copying around of i1
and j1 on each pass which doesn't get deleted, at least not yet). The steady state is reached the 2nd 
time through.  I suspect this is where the problem is; thus, it's in mainline, but I don't know how to 
tickle the bug there, it depends on the loop optimizer producing this cfg.

If somebody can say for sure which phase is wrong and why, I can look further.

-- 
           Summary: Compiler hangs at -O3
           Product: gcc
           Version: lno
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dalej at apple dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: powerpc-apple-darwin7.3.0
  GCC host triplet: powerpc-apple-darwin7.3.0
GCC target triplet: powerpc-apple-darwin7.3.0


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