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