[LLVMdev] Crash in PBQP register allocator

[Sebastian Buchwald]

On Sun, 2010-01-31 at 13:28 +1100, Lang Hames wrote:
> 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?

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