[LLVMdev] Crash in PBQP register allocator

[Lang Hames]

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.