[llvm-dev] PBQP register allocation and copy propagation

[Sebastian Buchwald via llvm-dev]

On 06/02/2016 07:22 PM, James Molloy via llvm-dev wrote:
> Hi Lang and Arnaud,
>
> I've been testing out the PBQP allocator for Thumb-2 and have ran into 
> a problem I'd love to get your input on.
>
> The problem is exemplfied in the codegen for the function @bar in the 
> attached IR file:
>
> bar:
>         push    {r4, lr}
>         sub     sp, #12
>  (1)    movw    r2, :lower16:.L_MergedGlobals
>  (1)    movt    r2, :upper16:.L_MergedGlobals
>         ldm.w   r2, {r0, r1, r3, r12, lr}
>         ldrd    r4, r2, [r2, #20]
>         strd    lr, r4, [sp]
>         str     r2, [sp, #8]
>  (2)    mov     r2, r3         ****
>         mov     r3, r12        ****
>         bl      baz
>         add     sp, #12
>         pop     {r4, pc}
>
> The two moves marked with **** are unnecessary. Especially the first, 
> which could be removed simply by swapping r2 and r3. This becomes even 
> more pronounced when I teach PBQP about how best to use registers to 
> allow LDM/STM formation; the codegen is perfect apart from those two 
> moves that just won't go.
>
> I've discovered that the underlying problem is that line (1) is 
> reduced after line (2). During the backpropagation phase (1) is 
> allocated r2 which means (2) cannot, as they interfere.
>
> Interestingly they're both reduced by rule RN and as the spill cost is 
> the same between them (and they're both conservatively allocatable), 
> it's pure luck which gets allocated first. I have a patch to account 
> for the opportunity cost of allocating r2 to (1) instead of (2) by 
> assigning a cost to r2 in (1)'s affinity matrix; this seems to work. 
> However I don't really know what's the right approach here - dealing 
> with this problem purely by propagating opportunity costs through 
> affinity matrices or doing something better with the reduction order.
>
> This ties in with another problem I'm seeing with a prototype 
> live-range splitter for PBQP. Obviously when pre-splitting around 
> every instruction, many copies are inserted. But the above problem 
> rears its head again! Consider this:
>
> %vregB = COPY %R0
> %vregA = COPY %vregB
>
>       COPY
>   A <------> B
>
> Node B has an affinity for register R0. The affinity edge between A 
> and B is a simple coalescing affinity (identity matrix). If B is 
> assigned first, it will get R0 and then A will also select R0. However 
> if A is selected first then it doesn't know anything about node B's 
> affinities and could thus get any register, causing a MOV.
>
> The above trivial example would be reduced by rule R1, so would 
> actually work optimally (because the reduction would account for B's 
> costs in A). However it is trivial to add two or more interfering defs 
> that cause the reduction rule to change to RN:
>
> %vregC = def...
> %vregD = def...
> %vregB = COPY %R0
> %vregA = COPY %vregB
>        = use %vregC, %vregD
I think one idea to improve the situation is to consider the cost vector 
of adjacent nodes during RN. Let's say you decided to do a RN for node A 
and want to compute the costs for choosing register %Ri. The current 
implementation does this by computing min(row/column i of edge A <--> B) 
but you can do better by adding B's cost vector to the row/column before 
computing the minimum. This way you also consider B's affinitiy for %R0.

>
> Now the reduction order is arbitrary and local costs aren't propagated 
> unlike R1 and R2. In fact, there is a rule "RM" proposed by Buchwald 
> [1] that seeks to fix a very similar case to this.
Porting RM to that situation would basically say "always fulfill this 
affinity" (beween A and B). Of course that's the wrong choice, if you 
really need the copy.

Best regards,
Sebastian

>
> What do you think?
>
> Cheers,
>
> James
>
> [1] SSA-based Register Allocation with PBQP, Buchwald et al, 
> https://pp.info.uni-karlsruhe.de/uploads/publikationen/buchwald11cc.pdf
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160602/ce77e5e8/attachment.html>