Re: haifa infinite loop

[Jeffrey A Law <law at cygnus dot com>]

  In message <19980419163604.00189@twiddle.rth.home>you write:
  > The problem is that we make no progress if there is not some member
  > of degree[] that is zero.  The relevant variables at the time are:
  > 
  > (gdb) p tail
  > $1 = 4
  > (gdb) p queue[0]@tail+1
  > $2 = {7, 6, 4, 3, 2}
  > (gdb) p degree[0]@7+1
  > $3 = {1, -1, 1, 1, 1, 1, 1, 1}
  > 
  > I'm pretty sure this case never should have arisen, so there should
  > be no point in checking for the loop not making progress, but I'm 
  > not sure yet where to look for the correct code.
As suspected, this is due to a backedge in the loop.  Basically we
have something like this (simplified since I don't need to show all
the blocks in the loop):

A succeeded by B & C
B succeeded by C
C succeeded by B & D
D succeeded by A and is also a loop exit node.

The natural loop is defined by the edge from D to A.

The edges between B & C define an inner loop, but it is not a
natural loop as there are multiple entry points (A -> B and A->C).

The old code would mark B & C as an inner loop, which prevented
processing of the outer A, B, C, D loop (which is the natural
loop and the one we'd want to region schedule).

The old code would later reject the B & C loop for region scheduling
because it was not a natural loop.

Stopping the infinite loop in haifa is easy -- just decrease the
degree of a node which is the target of a backedge.  We would want
to do this when an interation through the loop extracted no nodes
from the queue.

The problem is I do not think the rest of the haifa scheduler will
handle the resulting region correctly.  Just a gut feeling, it's
not based on any real analysis of the code, but instead the general
design of haifa leads me to believe it will not handle this kind of
loop for region scheduling.

So, what I think we want to do is reject loops with backedges which
are not loop latches (ie a back edge that does not go to the loop
header).

Let me think on it a little more, but I suspect that's the approach
we'll take for now.

jeff