[LLVMdev] [PBQP] applyR2() spill cost calculations

[Lang Hames]

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.


On Thu, Feb 12, 2015 at 3:07 AM, Jonas Paulsson <jonas.paulsson at ericsson.com
> wrote:

>  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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150212/498e0033/attachment.html>