[PBQP] applyR2() spill cost calculations

Hi Lang,

I have a question regarding applyR2() and spill costs.

In reference (2) in RegallocPBQP.cpp (Scholz/Eckstein), the ReduceII() procedure computes a Delta matrix with the first row and column always being zero. I see that in applyR2(), this is not the case. Spill costs are also updated. This seems to contradict the fact that row/col 0 should reflect the cost of spilling a vreg, which is constant, or?

For example:

  • ApplyR2(NId 74):

XCosts: 1.000000e+01 1.000000e+00 1.000000e+00

YXECosts:

1.000000e+00 1.000000e+00 1.000000e+00

1.000000e+00 inf 1.000000e+01

1.000000e+00 1.000000e+01 inf

ZXECosts:

0.000000e+00 0.000000e+00 0.000000e+00

0.000000e+00 0.000000e+00 0.000000e+00

0.000000e+00 0.000000e+00 0.000000e+00

0.000000e+00 0.000000e+00 0.000000e+00

0.000000e+00 0.000000e+00 0.000000e+00

Delta:

2.000000e+00 2.000000e+00 2.000000e+00 2.000000e+00 2.000000e+00

1.100000e+01 1.100000e+01 1.100000e+01 1.100000e+01 1.100000e+01

1.100000e+01 1.100000e+01 1.100000e+01 1.100000e+01 1.100000e+01

/Jonas

Hi Jonas,

My reading of the ReduceII pseudocode in the Scholz/Eckstein paper (on page 7 in my copy of the paper) is that it’s computing values for all rows and columns, including the spill row and column. (Note that the indexes in the paper are all one based rather than zero based).

In any case, I believe the code in tree is correct. In your example the delta matrix is correctly capturing the fact that, for example, if you choose to spill Y, then the cheapest allocation for X will still cost an additional 2.0: 1.0 for the Y-X edge, plus 1.0 for whatever register is selected in X.

More generally, you would expect to see non-zero values in the spill rows/columns of the delta matrix whenever you RII reduce a node that has non-zero costs for all registers, because even if you spill that node’s neighbors you’ll still have to pay for a register for X.

Cheers,
Lang.