<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=utf-8">
<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:"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.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.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;}
--></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">Thanks again for helping enlighten me for a portion of the backend I’ve yet to completely grok. I’ll see about running a pass to modify the LiveIntervals before allocation. I see other targets doing this by inserting a pass just after the
TwoAddress pass in either its own addFast/OptimizedRegalloc or as part of addPreRegAlloc.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">As for how we’re modeling the delay slots, I feel the decision was made due to a number of complicating factors. To that end, I believe that bundling the two instructions together would be insufficient, since the spill will still occur,
and will just move from in between the branch to after the occurs. In addition, our target already utilizes bundles to represent VLIW ILP, so there would be some inconsistencies in representation. However, this is all certainly problems on our end, and not
something with which to continue pestering the list, so I’ll leave it there (until we’re looking to upstream of course
<span style="font-family:"Segoe UI Emoji",sans-serif">😊</span> ).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Regards,<o:p></o:p></p>
<p class="MsoNormal">JB<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> Quentin Colombet <qcolombet@apple.com> <br>
<b>Sent:</b> Friday, July 9, 2021 2:26 PM<br>
<b>To:</b> Nagurne, James <j-nagurne@ti.com><br>
<b>Cc:</b> llvm-dev@lists.llvm.org<br>
<b>Subject:</b> Re: [EXTERNAL] [llvm-dev] Marking a particular virtual register (or live interval) as unspillable<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Hi James,<o:p></o:p></p>
<div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On Jul 9, 2021, at 11:51 AM, Nagurne, James <<a href="mailto:j-nagurne@ti.com">j-nagurne@ti.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;font-family:"Helvetica",sans-serif">Thanks for the response, Quentin.</span><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;font-family:"Helvetica",sans-serif"> </span><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;font-family:"Helvetica",sans-serif">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?</span><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><o:p></o:p></span></p>
</div>
</blockquote>
<div>
<p class="MsoNormal">Yes, you can run your own machine pass and set this “flag” yourself. Just make sure you do it in the middle of where LiveIntervals are set and preserved (e.g., right before the register coalescer.) <o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;font-family:"Helvetica",sans-serif">I was under the assumption that the LiveInterval information was calculated immediately preceding the allocator,
and that the target couldn’t easily influence that.</span><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><o:p></o:p></span></p>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal">No, you can actually modify the LiveIntervals essentially between right before register coalescer and right after register allocation (i.e., that includes before and after the scheduler).<br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;font-family:"Helvetica",sans-serif"> </span><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">“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.”</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">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.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">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.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">With that said, I believe block 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.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">So it looks like the way forward might be:</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">- Find a way to mark the live interval from the branch register def as unspillable</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">- Attempt to mimic how Sparc/Lanai/Mips fills delay slots</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Mimicking what the other targets are doing is probably your safest bet since it has been extensively tested and thus is supported.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">One thing you could try as well is create a bundle with the initiate branch and actual branch so that it is impossible to insert anything between the two instructions. Using bundles may be tricky though.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Cheers,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">-Quentin<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">Regards,</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">JB</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-size:12.0pt">
<hr size="2" width="98%" align="center">
</span></div>
<div id="divRplyFwdMsg">
<div>
<p class="MsoNormal"><b>From:</b><span class="apple-converted-space"> </span>Quentin Colombet <<a href="mailto:qcolombet@apple.com">qcolombet@apple.com</a>><br>
<b>Sent:</b><span class="apple-converted-space"> </span>Thursday, July 8, 2021 7:48 PM<br>
<b>To:</b><span class="apple-converted-space"> </span>Nagurne, James<br>
<b>Cc:</b><span class="apple-converted-space"> </span><a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b><span class="apple-converted-space"> </span>[EXTERNAL] Re: [llvm-dev] Marking a particular virtual register (or live interval) as unspillable<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">Hi James,<span class="apple-converted-space"> </span></span><o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">If you want to make a particular live-interval unspillable, you can use </span><span style="font-size:8.5pt;font-family:"Menlo",serif">LiveInterval::markNotSpillable.</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">Please be aware that this may not cover all your use cases:</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">- An unspillable live-interval can still be split (i.e., moved around), but all the newly created intervals would spill be unspillable.</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">- The unspillable information is lost if you have a pass that doesn’t preserve the LiveIntervals analysis and thus this analysis has to rerun.</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">Now, I am not entirely sure I understand the problem.</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">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.</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">The thing I am not sure though is are you allowed to have instructions between the initiate and the branch?</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">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.</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">Cheers,</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">-Quentin</span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"><br>
<br>
<br>
</span><o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt">On Jul 8, 2021, at 3:48 PM, Nagurne, James via llvm-dev <</span><a href="mailto:llvm-dev@lists.llvm.org"><span style="font-size:12.0pt;color:purple">llvm-dev@lists.llvm.org</span></a><span style="font-size:12.0pt">>
wrote:</span><o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
</div>
<div>
<div>
<div>
<div>
<p class="MsoNormal">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></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">MBB:<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> $r0 = Branch $r0 (tied def 0)<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> Occurs<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> ; $r0 is live-out of MBB<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">However, spilling is occurring, causing a store to appear between the initiation and the branch occurs.<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">MBB:<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> $r0 = Branch $r0 (tied def 0)<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> Store $r0 to memory<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> Occurs<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">MBB:<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> Store $r0 to memory<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> $r0 = Branch $r0 (tied def 0)<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> Occurs<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">I’m hoping I’ve just missed something and someone knows enough to point me in the right direction.<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">J.B. Nagurne<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">Code Generation<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">Texas Instruments<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">_______________________________________________<br>
LLVM Developers mailing list<br>
</span><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 style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><br>
</span><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></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>