[LLVMdev] Crash in PBQP register allocator

[Lang Hames]

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.