<div dir="ltr"><div>Hi Lang and Arnaud,</div><div><br></div><div>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.</div><div><br></div><div>The problem is exemplfied in the codegen for the function @bar in the attached IR file:</div><div><br></div><div>bar:</div><div>        push    {r4, lr}</div><div>        sub     sp, #12</div><div> (1)    movw    r2, :lower16:.L_MergedGlobals</div><div> (1)    movt    r2, :upper16:.L_MergedGlobals</div><div>        ldm.w   r2, {r0, r1, r3, r12, lr}</div><div>        ldrd    r4, r2, [r2, #20]</div><div>        strd    lr, r4, [sp]</div><div>        str     r2, [sp, #8]</div><div> (2)    mov     r2, r3         ****</div><div>        mov     r3, r12        ****</div><div>        bl      baz</div><div>        add     sp, #12</div><div>        pop     {r4, pc}</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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:</div><div><br></div><div>%vregB = COPY %R0</div><div>%vregA = COPY %vregB</div><div><br></div><div>      COPY</div><div>  A <------> B</div><div><br></div><div>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.</div><div><br></div><div>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:</div><div><br></div><div>%vregC = def...</div><div>%vregD = def...</div><div>%vregB = COPY %R0</div><div>%vregA = COPY %vregB</div><div>       = use %vregC, %vregD</div><div><br></div><div>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.</div><div><br></div><div>What do you think?</div><div><br></div><div>Cheers,</div><div><br></div><div>James</div><div><br></div><div>[1] SSA-based Register Allocation with PBQP, Buchwald et al, <a href="https://pp.info.uni-karlsruhe.de/uploads/publikationen/buchwald11cc.pdf">https://pp.info.uni-karlsruhe.de/uploads/publikationen/buchwald11cc.pdf</a></div></div>