<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=iso-8859-1">
<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;}
/* 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.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:937715657;
mso-list-type:hybrid;
mso-list-template-ids:1390700444 19925306 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-start-at:5;
mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;
mso-fareast-font-family:Calibri;
mso-bidi-font-family:"Times New Roman";}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:\F0A7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></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">Hi,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have encountered a test case where InlineSpiller generates bad code. A register is reloaded but never spilled, and I suspect a bug in InlineSpiller.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">A register is live over a loop that also have two inner loops. It is not used or defined over the inner loops. It is split into two sibling registers, where one covers just the inner loops interval, which is then spilled.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In spill(), analyzeSiblingValues() is called, which calls traceSiblingValue(). It traces in several iterations strangely back to the same register (inside a loop), finds it marked to be spilled, and the spill is cancelled:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span lang="SV" style="font-family:"Courier New"">Inline spilling %vreg86 [1396r,2276r:0) 0@1396r<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">>From original %vreg76<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">Tracing value %vreg86:0@1396r<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %vreg86:0@1396r: copy of %vreg87:6@1168r kill=1<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %vreg87:6@1168r: copy of %vreg87:5@1120B kill=1<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %vreg87:5@1120B: split phi value, checking 1 phi-defs, and 2 non-phi/orig defs<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> %vreg87:7@2276r: copy of %vreg86:0@1396r kill=1<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> traced to: spill %vreg86:0@1396r all-reloads kill deps[ 7@2276r ]<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">Merged spilled regs: SS#1 [1396r,2276r:0) 0@x<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I am guessing that traceSiblingValue() should have stopped at a PHI ValNo by recognizing it as ‘original’, meaning it was not inserted by splitting. It does not although it is clear that this PHI ValNo is part of OrigLI.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">This is how it looked, roughly:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Original LiveInterval:<o:p></o:p></p>
<p class="MsoNormal">5 0 --- inner loops --- // last valno in interval<o:p></o:p></p>
<p class="MsoNormal">PHI COPY of valno 5<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">After splitting:<o:p></o:p></p>
<p class="MsoNormal">5 6 7 8<o:p></o:p></p>
<p class="MsoNormal">PHI COPY of valno 5 COPY of valno 0 PHI<o:p></o:p></p>
<p class="MsoNormal"> 0<o:p></o:p></p>
<p class="MsoNormal"> COPY of valno 6<o:p></o:p></p>
<p class="MsoNormal"> /\<o:p></o:p></p>
<p class="MsoNormal"> OrigVNI<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Tracing sibling values, valno 6 is the original valno:<o:p></o:p></p>
<p class="MsoNormal">Valno 0 is a copy from 6.<o:p></o:p></p>
<p class="MsoNormal">Valno 6 is a copy from 5.<o:p></o:p></p>
<p class="MsoNormal">Valno 5 is a phi. Is it OrigVNI? NO! ‘Therefore it is not an original phi.’ WRONG! The search continues past it, assuming that it is a newly inserted PHI, done during splitting.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">My conlusion is that either the line<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">if (VNI->def == OrigVNI->def)<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">is wrong, because it doesn’t really check that VNI was not a phi in OrigLI, because it assumes that if VNI is a phi which was part of the original LI, then OrigVNI must be that PHI. This is not the case here.<o:p></o:p></p>
<p class="MsoNormal">The algorithm has iterated past OrigVNI and VNI is at this point a phi that was part of the original LI, which is the copy source of OrigVNI.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Or, it is assumed that splitting is always done at PHI ValNos somehow, and not as in this case, by a COPY of a PHI ValNo.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I would very much appreciate assistance in resolving this problem. As explained above, it is not clear to me why this error occurs, or what is the appropriate fix. I can provide more details if needed for some reason.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Best regards,<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>
</body>
</html>