<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:m="http://schemas.microsoft.com/office/2004/12/omml" 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 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoAcetate, li.MsoAcetate, div.MsoAcetate
{mso-style-priority:99;
mso-style-link:"Balloon Text Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:8.0pt;
font-family:"Tahoma","sans-serif";}
span.EmailStyle17
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
span.BalloonTextChar
{mso-style-name:"Balloon Text Char";
mso-style-priority:99;
mso-style-link:"Balloon Text";
font-family:"Tahoma","sans-serif";}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="color:#1F497D">Hi,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D">I have worked a little on the PBQP register allocator, and it is quite clear (at least to me) that it is not even a serious alternative to RegAllocGreedy at the moment, due to the poor handling of spilling. As
Arnaud wrote below, it is not optimizing spilling at all, but rather just spills anything that does not get an assignment. The result is a lot more spill/reload instructions than needed.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D">In RegAllocBase.h it says “…Register allocation complexity, and generated code performance is determined by the effectiveness of live range splitting rather than optimal coloring…”. I would then think that any
register allocation algorithm should benefit from this, but find that only RegAllocGreedy is doing live range splitting, and that the code for doing this is local to that allocator.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D">I would like to suggest a refactoring to make RAGreedy::trySplit() and its sub functions callable from any register allocator. Perhaps part of SplitEditor?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D">What do you think about this?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D">/Jonas<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Arnaud A. de Grandmaison [mailto:arnaud.degrandmaison@arm.com]
<br>
<b>Sent:</b> den 4 mars 2015 15:43<br>
<b>To:</b> Jonas Paulsson; Lang Hames<br>
<b>Cc:</b> llvmdev@cs.uiuc.edu<br>
<b>Subject:</b> RE: PBQP spilling<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span lang="EN-GB" style="color:#1F497D">Yes, for now the spilling is done in the most basic way, i.e. it’s functionally correct --- but not efficient. The focus was on the allocator itself, not on the spilling. As you noticed, the work
still to be done in this area is live range splitting, and smarter spill code insertion. Another area is improving the reduction order, to make the allocator less sensitive to the reduction order.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="color:#1F497D">There is no official plan; we started to discuss that with Lang some time ago, but none of us had time to dive into it yet. Any help appreciated there
</span><span lang="EN-GB" style="font-family:Wingdings;color:#1F497D">J</span><span lang="EN-GB" style="color:#1F497D">.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="color:#1F497D">Cheers,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="color:#1F497D">Arnaud<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB" style="color:#1F497D"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Jonas Paulsson [<a href="mailto:jonas.paulsson@ericsson.com">mailto:jonas.paulsson@ericsson.com</a>]
<br>
<b>Sent:</b> 04 March 2015 13:51<br>
<b>To:</b> Lang Hames; Arnaud De Grandmaison<br>
<b>Cc:</b> <a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a><br>
<b>Subject:</b> PBQP spilling<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal">Hi,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I would like to ask about PBQPs use of InlineSpiller. The code output when using PBQP gets a lot bigger compared to when using RegAllocGreedy. PBQP does not split the live intervals, and a lot more (often redundant) reload instructions
are emitted as a result, it seems. I wonder why this is, and if there are any plans to improve on this point?
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">/Jonas Paulsson<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</body>
</html>