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.