haifa infinite loop

haifa infinite loop

[Richard Henderson]

The following hunk o code on Alpha results in an infinite loop in haifa
beginning with line 1765:

1762          /* Remove blocks from queue[] when their in degree becomes1763                     zero.  Repeat until no blocks are left on the list.  This
1764             produces a topological list of blocks in the region.  */
1765          while (tail >= 0)
1766            {
1767              int_list_ptr ps;
1768
1769              if (head < 0)

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.

OTOH, I suppose checking for an infinite loop and aborting wouldn't
be a bad thing...


r~

Re: haifa infinite loop

[Jeffrey A Law]

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


  > (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.
Correct, it shouldn't have happened :-)

There's a backedge in the loop, with I know causes haifa some problems,
though I thought I'd managed to keep such code from being identified
as a schedulable region.

It's probably a situation similar to the one mentioned in the comment
above the code which adds all the block from the loop into the block
queue.

I'll try to look at it tomorrow.

  > OTOH, I suppose checking for an infinite loop and aborting
  > wouldn't be a bad thing...
Agreed.

jeff

Re: haifa infinite loop

[Jeffrey A Law]

  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

Re: haifa infinite loop

[Jeffrey A Law]

  In message <19980419163604.00189@twiddle.rth.home>you write:
  > 
  > --CE+1k2dSO48ffgeK
  > Content-Type: text/plain; charset=us-ascii
  > 
  > The following hunk o code on Alpha results in an infinite loop in haifa
  > beginning with line 1765:
  > 
  > 1762          /* Remove blocks from queue[] when their in degree becomes176
  > 3                     zero.  Repeat until no blocks are left on the list.  
  > This
  > 1764             produces a topological list of blocks in the region.  */
  > 1765          while (tail >= 0)
  > 1766            {
  > 1767              int_list_ptr ps;
  > 1768
  > 1769              if (head < 0)
[ ... ]
This should be fixed now.

I've also added your testcase to the testsuite.

jeff