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.