[LLVMdev] PBQP & register pairing

[Lang Hames]

Hi Arnaud,

> Hmm. Let me make sure I'm reading this right. The constraints are that:
> > a) All four operands have distinct registers.****
>
> > b) The first two are in a consecutive pair (second > first)****
>
> > c) The second two are in a consecutive pair (fourth > third)****
>
> Constraints b & c are OK, but a is too strict : “mpra %R0, %R1, %R0, %R1”
> is OK. But I though, may be wrongly, that “mpra %vreg1, %vreg2, %vreg3,
> %vreg4” meant %vreg1 and %vreg3 will be allocated to different physical
> registers, or they would have been coalesced. For example, the pass I added
> after the coalescer ensures that instructions like “mpra %vreg1, %vreg2,
> %vreg1, %vreg4” (impossible for pbqp to solve) is transformed to “mpra
> %vreg1, %vreg2, %vreg3, %vreg4” with the proper copy of  %vreg1 to %vreg3
> inserted.
>

“mpra %vreg1, %vreg2, %vreg3, %vreg4” does not imply that vreg1 and vreg3
will be allocated different physical registers. It only says that they
*can*(subject to constraints) be allocated different registers.

“mpra %vreg1, %vreg2, %vreg1, %vreg4” is not impossible for PBQP to solve.
Provided you have added the pairing constraint between vreg1 & vreg2, and
between vreg1 & vreg4, this simply means that the constraints will force
vreg2 and vreg4 to be allocated the same physical register. The PBQP
allocator will always generate something like "mpra RX, RY, RX, RY" for this
set of vreg operands.

By inserting the copy from %vreg1 to %vreg3 you have relaxed the problem for
PBQP: It can allocate the same register to %vreg1 and %vreg3, or it can
allocate different ones.

>That said my understanding of your pairing constraints would definitely
> prohibit mpra %R0, %R2, %R1, %R3 under any circumstances, even with out
> the****
>
> > distinction constraint. Either I've misunderstood your constraints, or
> there is a bug somewhere.****
>
> You got the contraints right. I was surprised to have to add a “safety net”
> to prevent the impossible case; at first I though pbqp could “backtrack”
>  once it discovers it gets to an impossible case… My backend is private, so
> I can not share it.
>

The PBQP allocator currently does not do any backtracking. The
"backpropagation" phase, which some people mistake for backtracking, is
actually just the graph reconstruction/coloring phase (equivalent to the
"select" phase of a graph coloring allocator).

I am very surprised to hear that the allocator does generate cases like "mpra
%R0, %R2, %R1, %R3". It is possible that there is a bug in the solver, but
in my experience the source of most bugs is the constraint matrices. Have
you put infinite costs on the spill option of the pairing constraint? E.g.

   SP R0 R1 R2 R3
SP I  I  I  I  I
R0 I  I  0  I  I
R1 I  I  I  0  I
R2 I  I  I  I  0
R3 I  0  I  I  I

If that's the case then an unfortunate combination of vreg uses in more than
on mpra instruction could cause the situation you're seeing. Consider:

mpra %vreg0, %vreg1, %vreg2, %vreg3
mpra %vreg0, %vreg2, %vreg1, %vreg3

With this sequence there is no way the PBQP allocator can construct a
correct solution (i.e one with finite costs).

The solution is to remove the infinities from the spill option on the
pairing matrix:

   SP R0 R1 R2 R3
SP 0  0  0  0  0
R0 0  I  0  I  I
R1 0  I  I  0  I
R2 0  I  I  I  0
R3 0  0  I  I  I

This will allow the allocator to spill as necessary in order to find a
correct allocation.


> I will trace what’s happening with vregsToAlloc and keep you updated.
>

Thank you. I will be interested to know what your investigations turn up.

Regards,
Lang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110621/fd2d0329/attachment.html>