<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 06/02/2016 07:22 PM, James Molloy
via llvm-dev wrote:<br>
</div>
<blockquote
cite="mid:CALCTSA3kYW7+Lo=PURBUhawhQcX6H0tDNmWbEwMM7eZ3d6M3+w@mail.gmail.com"
type="cite">
<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>
</blockquote>
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.<br>
<br>
<blockquote
cite="mid:CALCTSA3kYW7+Lo=PURBUhawhQcX6H0tDNmWbEwMM7eZ3d6M3+w@mail.gmail.com"
type="cite">
<div dir="ltr">
<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>
</blockquote>
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.<br>
<br>
Best regards,<br>
Sebastian<br>
<br>
<blockquote
cite="mid:CALCTSA3kYW7+Lo=PURBUhawhQcX6H0tDNmWbEwMM7eZ3d6M3+w@mail.gmail.com"
type="cite">
<div dir="ltr">
<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 moz-do-not-send="true"
href="https://pp.info.uni-karlsruhe.de/uploads/publikationen/buchwald11cc.pdf">https://pp.info.uni-karlsruhe.de/uploads/publikationen/buchwald11cc.pdf</a></div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</body>
</html>