<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 11 (filtered medium)">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]--><style>
<!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:monospace;
panose-1:0 0 0 0 0 0 0 0 0 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:#606420;
text-decoration:underline;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:Arial;
color:navy;}
@page Section1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.Section1
{page:Section1;}
-->
</style>
</head>
<body lang="EN-US" link="blue" vlink="#606420">
<div class="Section1">
<p class="MsoNormal"><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">Hi Lang,<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="navy" face="Arial"><span style="font-size:
10.0pt;font-family:Arial;color:navy"><o:p> </o:p></span></font></p>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">> Hmm. Let me make sure I'm reading this right. The constraints are that:<br>
> a) All four operands have distinct registers.<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">> b) The first two are in a consecutive pair (second > first)<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">> c) The second two are in a consecutive pair (fourth > third)<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">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.
<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="navy" face="Arial"><span style="font-size:
10.0pt;font-family:Arial;color:navy"><o:p> </o:p></span></font></p>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">>That said my understanding of your pairing constraints would definitely prohibit </span></font><span class="apple-style-span"><font size="2" face="Arial"><span style="font-size:10.0pt;font-family:Arial">mpra
%R0, %R2, %R1, %R3 under any circumstances, even with out the<o:p></o:p></span></font></span></p>
<p class="MsoNormal"><span class="apple-style-span"><font size="2" face="Arial"><span style="font-size:10.0pt;font-family:Arial">> distinction constraint. Either I've misunderstood your constraints, or there is a bug somewhere.</span></font></span><font size="2" color="navy" face="Arial"><span style="font-size:10.0pt;font-family:Arial;
color:navy"><o:p></o:p></span></font></p>
<div>
<p class="MsoNormal"><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">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.<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366"><o:p> </o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">I will trace what’s happening with
</span></font><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">vregsToAlloc and keep you updated.<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="#003366" face="Courier New"><span style="font-size:10.0pt;font-family:"Courier New";color:#003366"><o:p> </o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="#003366" face="Courier New"><span style="font-size:10.0pt;font-family:"Courier New";color:#003366">Regards,<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="navy" face="Courier New"><span style="font-size:10.0pt;font-family:"Courier New";color:navy">--
<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="2" color="navy" face="Courier New"><span style="font-size:10.0pt;font-family:"Courier New";color:navy">Arnaud de Grandmaison
<o:p></o:p></span></font></p>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
</div>
<div>
<div class="MsoNormal" align="center" style="text-align:center"><font size="3" face="Times New Roman"><span style="font-size:12.0pt">
<hr size="2" width="100%" align="center" tabindex="-1">
</span></font></div>
<p class="MsoNormal"><b><font size="2" face="Tahoma"><span style="font-size:10.0pt;
font-family:Tahoma;font-weight:bold">From:</span></font></b><font size="2" face="Tahoma"><span style="font-size:10.0pt;font-family:Tahoma"> Lang Hames [mailto:lhames@gmail.com]
<br>
<b><span style="font-weight:bold">Sent:</span></b> Friday, June 17, 2011 9:37 AM<br>
<b><span style="font-weight:bold">To:</span></b> Arnaud Allard de Grandmaison<br>
<b><span style="font-weight:bold">Cc:</span></b> llvmdev@cs.uiuc.edu<br>
<b><span style="font-weight:bold">Subject:</span></b> Re: [LLVMdev] PBQP & register pairing</span></font><o:p></o:p></p>
</div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">Hi Arnaud,<o:p></o:p></span></font></p>
<div>
<div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">The patch looks good. I've committed it in r133249.<o:p></o:p></span></font></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;
margin-left:4.8pt;margin-right:0cm">
<div link="blue" vlink="blue">
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><font size="2" color="navy" face="Arial"><span style="font-size:10.0pt;font-family:Arial;
color:navy"> </span></font><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><font size="2" color="navy" face="Arial"><span style="font-size:10.0pt;font-family:Arial;
color:navy">I noticed an unexpected --- to me at least --- behaviour of the allocator.</span></font><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><font size="2" color="navy" face="Arial"><span style="font-size:10.0pt;font-family:Arial;
color:navy">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 ?</span></font><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
</div>
<div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">Hmm. Let me make sure I'm reading this right. The constraints are that:<br>
a) All four operands have distinct registers.<o:p></o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">b) The first two are in a consecutive pair (second > first)<o:p></o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">c) The second two are in a consecutive pair (fourth > third)<o:p></o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">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
</span></font><font face="monospace"><span style="font-family:monospace">mpra %R0, %R1, %R0, %R1</span></font>. You'll also need (R_x+1 != R_y) to ensure that you don't get something like
<font face="monospace"><span style="font-family:monospace">mpra %R0, %R1, %R1, %R2</span></font>. <o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"> <o:p></o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">That said my understanding of your pairing constraints would definitely prohibit </span></font><span class="apple-style-span"><font size="2" face="Arial"><span style="font-size:10.0pt;font-family:Arial">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.</span></font></span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span class="apple-style-span"><font size="2" color="navy" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:navy"> </span></font></span><o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;
margin-left:4.8pt;margin-right:0cm">
<div link="blue" vlink="blue">
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><font size="2" color="navy" face="Arial"><span style="font-size:10.0pt;font-family:Arial;
color:navy">Now, 99% of my users’ codebase is compiling.
</span></font><font size="2" color="navy" face="Wingdings"><span style="font-size:10.0pt;font-family:
Wingdings;color:navy">J</span></font><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><font size="2" color="navy" face="Arial"><span style="font-size:10.0pt;font-family:Arial;
color:navy">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.</span></font><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">The data structure you want to keep your eye on is the set </span></font><font face="monospace"><span style="font-family:monospace">vregsToAlloc</span></font> 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 <font face="monospace"><span style="font-family:
monospace">RegAllocPBQP::mapPBQPToRegAlloc</span></font>),
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.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">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.<o:p></o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">Regards,<o:p></o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt">Lang.<o:p></o:p></span></font></p>
</div>
<div>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:
12.0pt"><o:p> </o:p></span></font></p>
</div>
</div>
</div>
</div>
<br>
<hr>
<font face="Arial" color="Gray" size="-2">CONFIDENTIAL NOTICE: The contents of this message, including any attachments, are confidential and are intended solely for the use of the person or entity to whom the message was addressed. If you are not the intended
recipient of this message, please be advised that any dissemination, distribution, or use of the contents of this message is strictly prohibited. If you received this message in error, please notify the sender. Please also permanently delete all copies of
the original message and any attached documentation. Thank you.<br>
</font>
</body>
</html>