Crash in PBQP register allocator

Hi,

Please see the two “.ll’ files attached.

Command line used

llc –march=pic16 –pre-RA-sched=list-burr –regalloc=pbqp new.obc

The above test case crashes only when I use the combination of list-burr scheduler and pbqp register allocator. If any of them (scheduler or register allocator) is replaced with some alternate then I don’t see the crash.

I could not figure out the reason. Please provide some pointers to reasons of the crash.

Regards

Sachin

new.obc.ll.pass (551 Bytes)

new.obc.ll.crash (679 Bytes)

This looks like a bug in the PBQP solver. I'm currently investigating.

Cheers,
Lang.

Hi Sachin,

Confirmed: This is being caused by a subtle issue in the heuristic
PBQP solver. Specifically: R1/R2 reductions as currently implemented
can, on rare occasions, lead to the heuristic solver failing to find a
finite cost solution, even though one exists. The infinite cost
solution will always be in violation of some rule of register
allocation (failing to handle an interference, or spilling an infinite
cost node for instance).

There are several ways to fix the issue with the solver, but most
would pesimmize allocation quality in the general case. I will look
for a better solution when I return to the University of Sydney in a
couple of weeks. In the mean time I have added an assert to the
allocator to ensure that infinite cost solutions do not produce
miscompilations. For programs which trigger the assert you'll just
have to fall back on linear scan I'm afraid.

(If you particularly want PBQP to work in the short term you could
apply the following fix: Simply pre-color all infinite cost intervals
and remove the register option from any live intervals with which they
interfere).

Cheers,
Lang.

Thanks Lang!

I think we can use linear scan as work around for short term.

Thanks for your help.

Regards
Sachin

Hi Lang,

Thanks for your inputs on the problem. I was just curious to know if you got any opportunity to work on the solution for this.

Regards
Sachin

Hi Sachin,

Yes. Bernhard Scholz and I have just discussed a fix for this. I hope to commit it in the next few days. I will let you know as soon as it goes in to the mainline.

Regards,
Lang.

Hi Sachin, llvm-dev,

I've just committed a new PBQP solver which, among other things,
should take care of this bug.

Please let me know how it works out for you.

Cheers,
Lang.

Hi Lang,

I’m surprised about the fact that you omit R1/R2 reductions in some cases.
Can you give a more detailed description of the bug (e.g. a PBQP dump)?

Best regards,
Sebastian

Lang Hames wrote:

Hi Sachin, llvm-dev,

I've just committed a new PBQP solver which, among other things,
should take care of this bug.

Please let me know how it works out for you.

Hi Lang,
I haven't got it to test on trunk yet, as I am on 2.6.
Will let you know soon.

- Sanjiv

Hi Sebastian,

It boils down to this: The previous heuristic solver could return
infinite cost solutions in some rare cases (despite finite-cost
solutions existing). The new solver is still heuristic, but it should
always return a finite cost solution if one exists. It does this by
avoiding early reduction of infinite spill cost nodes via R1 or R2.

To illustrate why the early reductions can be a problem here is some
output from the original test case which started this thread:

graph {
  node0 [ label="0: [ 1.875000e-02, 0.000000e+00 ]" ]
  node1 [ label="1: [ inf, 0.000000e+00 ]" ]
  node2 [ label="2: [ inf, 0.000000e+00 ]" ]
  node3 [ label="3: [ inf, 0.000000e+00 ]" ]
  node4 [ label="4: [ 5.357143e-02, 0.000000e+00 ]" ]
  node5 [ label="5: [ inf, 0.000000e+00 ]" ]
  node6 [ label="6: [ 6.250000e-02, 0.000000e+00 ]" ]
  node7 [ label="7: [ 7.500000e-02, 0.000000e+00 ]" ]
  node8 [ label="8: [ inf, 0.000000e+00 ]" ]
  node9 [ label="9: [ inf, 0.000000e+00 ]" ]
  node10 [ label="10: [ inf, 0.000000e+00 ]" ]
  node11 [ label="11: [ inf, 0.000000e+00 ]" ]
  node12 [ label="12: [ 3.750000e-01, 0.000000e+00 ]" ]
  edge [ len=13 ]
  node0 -- node1 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node0 -- node2 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node0 -- node3 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node0 -- node4 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node0 -- node5 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node0 -- node6 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node0 -- node7 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node0 -- node8 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node4 -- node5 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node4 -- node6 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node4 -- node7 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node6 -- node7 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node6 -- node8 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
  node7 -- node8 [ label="[ 0.000000e+00, 0.000000e+00 ]\n[
0.000000e+00, inf ]\n" ]
}
Applying R1 to 1
Applying R1 to 2
Applying R1 to 3
Applying R2 to 5
Applying RN (unsafe) to 0 safe = { }, unsafe = { 0 6 4 7 8 }
Applying R2 to 8
Applying R2 to 4
Applying R1 to 6
Selected 1 for node 9 (cost = 0.000000e+00)
Selected 1 for node 10 (cost = 0.000000e+00)
Selected 1 for node 11 (cost = 0.000000e+00)
Selected 1 for node 12 (cost = 0.000000e+00)
Selected 0 for node 7 (cost = 1.375000e-01)
Reduction stack is: [ 1 2 3 5 0 8 4 6 ]
Selected 0 for node 6 (cost = 6.250000e-02)
Selected 1 for node 4 (cost = 0.000000e+00)
Selected 1 for node 8 (cost = 0.000000e+00)
Selected 0 for node 0 (cost = 1.875000e-02)
Selected 0 for node 5 (cost = inf)
Selected 1 for node 3 (cost = 0.000000e+00)
Selected 1 for node 2 (cost = 0.000000e+00)
Selected 1 for node 1 (cost = 0.000000e+00)
llc: /home/lhames/Projects/llvm/llvm-broken-pbqp/llvm/lib/CodeGen/RegAllocPBQP.cpp:701:
bool<unnamed>::PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution&):
Assertion `solution.getCost() !=
std::numeric_limits<PBQP::PBQPNum>::infinity() && "Invalid (infinite
cost) solution for PBQP problem."' failed.

The problem is that node 5 is being allocated an infinite cost option
(which implies that all its options have infinite cost). The following
steps lead to this situation:

-> Applying R2 to 5

Node 5 is pushed to the reduction stack and costs are pushed onto edge
(0, 4), ensuring that neither Node 0 nor Node 4 can be stored in a
register.

-> Applying RN (unsafe) to 0 safe = { }, unsafe = { 0 6 4 7 8 }

Node 0 is pushed to the reduction stack and all of its edges are
removed, including (0,4), throwing away the restriction that 4 must
not be stored in a register.

Node 4 is later reduced via R2, then assigned the cheaper register
option during backpropagation. This eliminates all finite cost options
for Node 5. This is our problem.

In the PIC16 case where there are only two options, spill or register,
I believe it should be possible to have RN preserve the constraints
when it reduces a node. This is not possible when 3 or more options
are present however, and we wanted a general solution. By forcing
nodes with infinite spill cost to be reduced via RN (even when R1 or
R2 could be applied) the problem is easily solved. The infinite spill
costs of such nodes mean that they will only be reduced at the end of
the reduction process (and thus will be colored first), unless they
are proven colorable, in which case it is safe to reduce them earlier.

I have not had a good look at the extent to which this policy impacts
allocation quality, but from the experimental results I've seen so far
it seems to work well.

Hope that answers your question?

Cheers,
Lang.

Hi Lang,

yes, the example helps a lot.

I think the crucial point is that node4 isn't aware of its own
restriction (after the first R2 reduction).
If you normalize the new matrix (shifting costs in the adjacent vector
until each row/column has minima 0) after a R2 reduction of a node with
infinite spill cost the problem should disappear.

For instance, normalization of (0,4) transform

node0 [ label="0: [ 1.875000e-02, inf ]" ]
node4 [ label="4: [ 5.357143e-02, 0.000000e+00 ]" ]
node0 -- node4 [ label="[ 0.000000e+00, inf ]\n[inf, inf ]\n" ]

into

node0 [ label="0: [ 1.875000e-02, inf ]" ]
node4 [ label="4: [ 5.357143e-02, inf ]" ]
node0 -- node4 [ label="[ 0.000000e+00, 0 ]\n[inf, 0 ]\n" ] (node0
selects the matrix row).

Did you consider this option?

For R1 reductions, i don't see the problem.

Best regards,
Sebastian

Hi Sebastian,

I think the crucial point is that node4 isn't aware of its own
restriction (after the first R2 reduction).
If you normalize the new matrix (shifting costs in the adjacent vector
until each row/column has minima 0) after a R2 reduction of a node with
infinite spill cost the problem should disappear.

<snip>

Did you consider this option?

We did. The success of normalization in this case depends on whether
you attempt to normalize rows first, then columns, or the other way
around.

Currently rows are normalized first, then columns. In your example the
infinite costs are thus propagated onto element 1 of node 0, rather
than node 4, which leaves us where we started.

Switching the normalization order would fix this example, but not the
general issue.

Bernhard and I devised a stronger normalization scheme for matrices
containing infinities which would fix this problem in the one-register
(two option) case. For problems with two or more registers however
normalization will not help us, and even R1 can be dangerous*, hence
our current approach: Do not apply R1 or R2 to a node with infinite
costs unless you can prove it's colorable.

Cheers,
Lang.

*I've got an example around here somewhere. It's more involved, but I
can dig it up if you'd like.

Lang Hames wrote:

Hi Sebastian,

We did. The success of normalization in this case depends on whether
you attempt to normalize rows first, then columns, or the other way
around.

Currently rows are normalized first, then columns. In your example the
infinite costs are thus propagated onto element 1 of node 0, rather
than node 4, which leaves us where we started.

Switching the normalization order would fix this example, but not the
general issue.
  

You can consider infinite vector options and ignore the corresponding
rows/columns during normalization.
This would fix the ordering problem for infinite options:

After the normalization of the rows:
node0 [ label="0: [ 1.875000e-02, inf ]" ]
node4 [ label="4: [ 5.357143e-02, 0]" ]
node0 -- node4 [ label="[ 0, inf ]\n[0, 0 ]\n" ]

After the normalization of the columns:
node0 [ label="0: [ 1.875000e-02, inf ]" ]
node4 [ label="4: [ 5.357143e-02, inf]" ]
node0 -- node4 [ label="[ 0, 0 ]\n[0, 0 ]\n" ] (consider second row as
deleted)

Bernhard and I devised a stronger normalization scheme for matrices
containing infinities which would fix this problem in the one-register
(two option) case.

Is that the one described above?

For problems with two or more registers however
normalization will not help us, and even R1 can be dangerous*, hence
our current approach: Do not apply R1 or R2 to a node with infinite
costs unless you can prove it's colorable.

Cheers,
Lang.

*I've got an example around here somewhere. It's more involved, but I
can dig it up if you'd like.
  

Yes, please.

Best regards,
Sebastian

Bernhard and I devised a stronger normalization scheme...

Is that the one described above?

Yes.

*I've got an example around here somewhere. It's more involved, but I
can dig it up if you'd like.

Yes, please.

Ahh it looks like my example was wrong. You're quite right - with the
stronger normalization scheme R1 and R2 should be safe for all nodes.
I'll update the PBQP solver to reflect this.

- Lang.