<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 15 (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:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Menlo;
panose-1:0 0 0 0 0 0 0 0 0 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
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:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle19
{mso-style-type:personal-compose;
color:black;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:697776586;
mso-list-type:hybrid;
mso-list-template-ids:1934648582 67698689 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;
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:-.25in;
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:-.25in;
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:-.25in;
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:-.25in;
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:-.25in;
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:-.25in;
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:-.25in;
font-family:Wingdings;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></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><span style="font-size:12.0pt;color:black">Thanks for the response, Quentin.<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p><span style="font-size:12.0pt;color:black">I'm aware of markNotSpillable, but it looks like the only use of that function is for the aforementioned unspillable terminators and for very particular live ranges in ‘generic’ code. Are you suggesting that there’s
a way to modify the LiveIntervals analysis before the allocator/spiller uses them? I was under the assumption that the LiveInterval information was calculated immediately preceding the allocator, and that the target couldn’t easily influence that.<o:p></o:p></span></p>
<p><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">“</span><span style="font-size:12.0pt;color:black">From what you’re describing, it feels to me that the bug is in the block placement since it’s moving the store above the intended definition and
that marking the LI not spillable is just a workaround.”<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">It’s not so much moving the store as it is removing the terminators and then replacing them at the end of the block, which is where terminators are required to exist. It just so happens that the
initiate has a gap which contains a dependent instruction that gets re-ordered on the call to insertBranch.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">For background: the pair of instructions models branch delay slots, a branch and its associated discontinuity which occurs on a different cycle. By separating the branch instruction and the actual
discontinuity into separate instructions, it becomes possible to use an instruction scheduler to fill the delay slots, rather than using a separate pre-emit pass that Lanai, Mips, and Sparc uses.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">With that said, I believe b</span><span style="font-size:12.0pt;color:black">lock placement is certainly doing something that should be 'ok' with regards to the IR semantics. Specifically, the
pass uses the target’s removeBranch and insertBranch implementations, which should be guaranteed not to affect the execution behavior of a block. Our target has a further requirement that no instruction can exist between the initiate and the actual discontinuity
for insertBranch to ensure that the program has not changed. The spill being created breaks that rule, and so removeBranch/insertBranch do not work as desired.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">So it looks like the way forward might be:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">- Find a way to mark the live interval from the branch register def as unspillable<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">- Attempt to mimic how Sparc/Lanai/Mips fills delay slots<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Regards,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">JB<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-size:12.0pt;color:black">
<hr size="2" width="98%" align="center">
</span></div>
<div id="divRplyFwdMsg">
<p class="MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> Quentin Colombet <qcolombet@apple.com><br>
<b>Sent:</b> Thursday, July 8, 2021 7:48 PM<br>
<b>To:</b> Nagurne, James<br>
<b>Cc:</b> llvm-dev@lists.llvm.org<br>
<b>Subject:</b> [EXTERNAL] Re: [llvm-dev] Marking a particular virtual register (or live interval) as unspillable</span><span style="font-size:12.0pt;color:black">
<o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"> <o:p></o:p></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Hi James, <o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">If you want to make a particular live-interval unspillable, you can use </span><span style="font-size:8.5pt;font-family:"Menlo",serif;color:black">LiveInterval::markNotSpillable.</span><span style="font-size:12.0pt;color:black"><o:p></o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Please be aware that this may not cover all your use cases:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">- An unspillable live-interval can still be split (i.e., moved around), but all the newly created intervals would spill be unspillable.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">- The unspillable information is lost if you have a pass that doesn’t preserve the LiveIntervals analysis and thus this analysis has to rerun.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Now, I am not entirely sure I understand the problem.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">From what you’re describing, it feels to me that the bug is in the block placement since it’s moving the store above the intended definition and that marking the LI not spillable is just a workaround.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">The thing I am not sure though is are you allowed to have instructions between the initiate and the branch?<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">If you do not, then it sounds to me that you could mark the initiate as a terminator as well. I don’t guarantee that doing that would solve the problem out of the box, but if it doesn’t we should
just fix whatever introduce the issue because in theory, we are not allowed to insert code after the first terminator.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Cheers,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">-Quentin<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><br>
<br>
<o:p></o:p></span></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">On Jul 8, 2021, at 3:48 PM, Nagurne, James via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
<div>
<div>
<div>
<p class="MsoNormal"><span style="color:black">Hi all, I have a question regarding spills that I’ve been unable to find a satisfactory answer for in my perusal of the source.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">I have a downstream target which contains an instruction that defines a register and is very closely associated with a terminator, but is not itself a terminator. Specifically, the first instruction is effectively
‘initiate the branch’, and the actual terminator is ‘branch occurs’.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">The expectation is that the ‘initiate the branch’ instruction occurs as the last non-terminator instruction if it’s present at all due to the aforementioned association with terminators.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">MBB:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> $r0 = Branch $r0 (tied def 0)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> Occurs<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> ; $r0 is live-out of MBB<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">However, spilling is occurring, causing a store to appear between the initiation and the branch occurs.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">MBB:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> $r0 = Branch $r0 (tied def 0)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> Store $r0 to memory<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> Occurs<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">When block placement occurs, the branches are removed from the block and then re-inserted. This affects the branch and the occurs, but not the store, leading to a change in execution behavior:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">MBB:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> Store $r0 to memory<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> $r0 = Branch $r0 (tied def 0)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> Occurs<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">One potential solution I believed would have worked is to combine the branch and its occurs into a single terminator, but this causes the three-address instruction pass to insert a COPY just after the combined
instruction for the tied def, leading to a similar problem where a non-terminator occurs after a terminator.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">I found the concept of an ‘unspillable terminator’ added in commit 0447f350 for ARM, but the problematic instruction isn’t a terminator. I had thought to generalize the concept to consider a virtual register unspillable
regardless of being a terminator or not, but ran into issues in the verifier that made me reconsider (The value is live across the backedge of the loop as well out live-out of the loop, which runs across an expectation that unspillable terminators have 1 use).
I thought that controlling spilling seemed like an important concept for a target to have some level of control over, but could not find anything in the spill or LiveInterval code that seemed to allow a target to mark a register/interval as unspillable.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">I’m hoping I’ve just missed something and someone knows enough to point me in the right direction.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">Thanks,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">J.B. Nagurne<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">Code Generation<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black">Texas Instruments<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="color:black"> <o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:black">_______________________________________________<br>
LLVM Developers mailing list<br>
</span><span style="font-size:12.0pt;color:black"><a href="mailto:llvm-dev@lists.llvm.org"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:purple">llvm-dev@lists.llvm.org</span></a></span><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:black"><br>
</span><span style="font-size:12.0pt;color:black"><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif;color:purple">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></a><o:p></o:p></span></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
</div>
</div>
</body>
</html>