[LLVMdev] PBQP & register pairing

[Lang Hames]

Hi Arnaud,

The patch looks good. I've committed it in r133249.

>
>
> I noticed an unexpected --- to me at least --- behaviour of the allocator.
>
> I have some instructions using 2 pairs of registers, say “mpra R_x, R_x+1,
> R_y, R_y+1”, and setting the pairing constraints R_x -> R_x+1 and R_y ->
> R_y+1 could silently produce wrong code like “mpra %R0, %R2, %R1, %R3”. I
> add to explicitly add another constraint  to describe that y must differ
> from x, x-1 and x+1 to make the allocator build valid pairs, i.e “mpra %R0,
> %R1, %R2, %R3”. Is there anything I missed ?
>
>
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)

If that's accurate then you will need four constraints to represent it. Two
to enforce the pairing, which you've already described, and two to enforce
the distinction. Without constraint enforcing the R_x != R_y distinction the
PBQP allocator is free to allocate mpra %R0, %R1, %R0, %R1. You'll also need
(R_x+1 != R_y) to ensure that you don't get something like mpra %R0, %R1,
%R1, %R2.

>
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.


> Now, 99% of my users’ codebase is compiling. J
>
> The last issue I have is an assert during regalloc in LiveIntervalAnalysis
> : “attempt to spill already spilled interval!”, and I do not know where to
> start looking. Any hint would be welcome.
>
>
The data structure you want to keep your eye on is the set vregsToAlloc to
RegAllocPBQP. This set holds the virtual registers which PBQP must allocate
for on its next round. Once a virtual register has been spilled it should be
erased from this set (see RegAllocPBQP::mapPBQPToRegAlloc), and it should
never re-enter it, and thus never be considered again by the PBQP allocator.
At a guess it sounds like one of your vregs may be being added to this set a
2nd time, but I'm not sure how that could be happening.

Is your backend public? Are you able to share a test case with me? I'm very
busy with my PhD write-up at the moment, but I will try to find time for a
quick look at this.

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