[LLVMdev] Crash in PBQP register allocator

[Sebastian Buchwald]

Lang Hames wrote:
> Hi Sebastian,
>
>   
> 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.
>   
You can consider infinite vector options and ignore the corresponding
rows/columns during normalization.
This would fix the ordering problem for infinite options:

After the normalization of the rows:
node0 [ label="0: [ 1.875000e-02, inf ]" ]
node4 [ label="4: [ 5.357143e-02, 0]" ]
node0 -- node4 [ label="[ 0, inf ]\n[0, 0 ]\n" ]

After the normalization of the columns:
node0 [ label="0: [ 1.875000e-02, inf ]" ]
node4 [ label="4: [ 5.357143e-02, inf]" ]
node0 -- node4 [ label="[ 0, 0 ]\n[0, 0 ]\n" ] (consider second row as
deleted)

> Bernhard and I devised a stronger normalization scheme for matrices
> containing infinities which would fix this problem in the one-register
> (two option) case.
Is that the one described above?
> 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.
>   
Yes, please.

Best regards,
Sebastian