<div dir="ltr"><div>Hi Paparo.</div><div><br></div>I know this has been almost one year. I would like to know whether you have plan to contribute this back ? We have some performance instability that would benefit from a pass like this in Facebook. <div>Thanks.</div><div>-Xin</div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Nov 21, 2016 at 11:58 PM, Hal Finkel via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:#000000"><br><hr id="m_-4988723288261583761zwchr"><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><span class=""><b>From: </b>"Paparo Bivas, Omer" <<a href="mailto:omer.paparo.bivas@intel.com" target="_blank">omer.paparo.bivas@intel.com</a>><br><b>To: </b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br><b>Cc: </b><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br></span><b>Sent: </b>Monday, November 21, 2016 6:16:35 AM<span class=""><br><b>Subject: </b>RE: [llvm-dev] RFC: Insertion of nops for performance stability<br><br>
</span><div class="m_-4988723288261583761WordSection1">
<p class="MsoNormal"><span style="color:rgb(31,73,125)">Hi Hal,</span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)"> </span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">Thanks for the reference. I’ve looked at <a name="m_-4988723288261583761__MailEndCompose">PPCBranchSelector and the PowerPC backend. It is very different from the X86 architecture and unfortunately the way branch relaxation and alignment
related issues are handled in PPC cannot be copied to X86. This is because:</a></span></p><span class="">
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:rgb(31,73,125)"><span>1.<span style="font:7pt "Times New Roman"">
</span></span></span><span dir="LTR"></span><span style="color:rgb(31,73,125)">PPC instructions are of fixed length while X86 instructions are of variable length, and their length can change depending on features the target machine has. Not only that, but
a relaxed X86 instruction will differ in size from its non-relaxed version. The function TrargetInstrInfo::<wbr>getInstSizeInBytes is not, and can’t be, implemented for X86. It follows that:</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:rgb(31,73,125)"><span>2.<span style="font:7pt "Times New Roman"">
</span></span></span><span dir="LTR"></span><span style="color:rgb(31,73,125)">Target addresses of branches cannot be computed before the code emission in X86. That’s why X86 relies on the layout process in MCAssembler, which occurs after the encoding is
done and (amongst the rest) relaxes instructions that needs relaxation.</span></p>
<p class="MsoNormal"><span id="m_-4988723288261583761DWT1720" style="color:rgb(31,73,125)">For the same reasons, the nops insertion process also cannot occur until after the encoding phase.</span></p></span></div></blockquote>Okay, interesting. Thanks for explaining.<span class=""><br><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div class="m_-4988723288261583761WordSection1"><p class="MsoNormal"><span style="color:rgb(31,73,125)"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)"> </span></p>
<p class="MsoNormal"><span id="m_-4988723288261583761DWT1737" style="color:rgb(31,73,125)">Regarding splitting blocks of code, that is essentially what I’m proposing, but at MC level (since this is the level I’m operating in). When needed, a MCPerfNopFragment will be a separator between two MCFragments
that contain code (e.g. MCDataFragments). However, a MCPerfNopFragment is not a MCAlignFragment and a block that follows a MCDataFragments will not (necessarily) be aligned as it could be wasteful in terms of code size. Consider the example I provided. Aligning
the fragment after the nops to 16B will cost one additional byte of nops in code size, and aligning it to 32B will cost 17 additional bytes of nops in code size. There’s no benefit in this extra bytes.</span></p></div></blockquote></span>Makes sense.<span class=""><br><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div class="m_-4988723288261583761WordSection1"><p class="MsoNormal"><span style="color:rgb(31,73,125)"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">As for filling the slots with other instructions, I think it won’t be right, because</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:rgb(31,73,125)"><span>1.<span style="font:7pt "Times New Roman"">
</span></span></span><span dir="LTR"></span><span style="color:rgb(31,73,125)">It will require some sort of branch prediction unit that will work in compilation time. Branch predicting is done in run time by the machine, and involves many parameters. In
my opinion, trying to imitate such a mechanism will create either very complex code or inaccurate predictions.</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:rgb(31,73,125)"><span>2.<span style="font:7pt "Times New Roman"">
</span></span></span><span dir="LTR"></span><span id="m_-4988723288261583761DWT1739" style="color:rgb(31,73,125)">Execution of those other instructions can be very expensive compared to the execution of the nops. This means that wrong (compile-time) branch prediction will result in a performance
penalty that may even overshadow the benefit from the spacing those instructions provide.</span></p></div></blockquote></span>We do have "compile-time branch prediction" in the form of static heuristics, and even better when available, profiling data. However, speculating in between two branches to the same destination seems unlikely, so only the first situation would be relevant (DSB thrashing). There, however, just picking a different instruction ordering seems like a more-interesting option than speculation. Inserting nops, however, seems like a reasonable general strategy regardless.<span class=""><br><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div class="m_-4988723288261583761WordSection1"><p class="m_-4988723288261583761MsoListParagraph"><span style="color:rgb(31,73,125)"></span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:rgb(31,73,125)"><span>3.<span style="font:7pt "Times New Roman"">
</span></span></span><span dir="LTR"></span><span id="m_-4988723288261583761DWT1738" style="color:rgb(31,73,125)">As I mentioned, this process has to be done in the Assembler, after all the passes and the code emission. In my opinion, the Assembler phase is not a good time to change locations
of instructions.</span></p></div></blockquote></span>I agree with this. We shouldn't try to reschedule instructions in the assembler.<br><br> -Hal<div><div class="h5"><br><blockquote style="border-left:2px solid rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div class="m_-4988723288261583761WordSection1"><p class="m_-4988723288261583761MsoListParagraph"><span style="color:rgb(31,73,125)"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)"> </span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">Thanks,</span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">Omer</span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)"> </span></p>
<div>
<div style="border-right:medium none;border-width:1pt medium medium;border-style:solid none none;border-color:rgb(225,225,225) -moz-use-text-color -moz-use-text-color;padding:3pt 0cm 0cm">
<p class="MsoNormal"><a name="m_-4988723288261583761______replyseparator"></a><b>From:</b> Hal Finkel [mailto:<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>]
<br>
<b>Sent:</b> Sunday, November 20, 2016 23:26<br>
<b>To:</b> Paparo Bivas, Omer <<a href="mailto:omer.paparo.bivas@intel.com" target="_blank">omer.paparo.bivas@intel.com</a>><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [llvm-dev] RFC: Insertion of nops for performance stability</p>
</div>
</div>
<p class="MsoNormal"> </p>
<div>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black"> </span></p>
<div class="MsoNormal" style="text-align:center" align="center"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black">
<hr id="m_-4988723288261583761zwchr" align="center" size="3" width="100%">
</span></div>
<blockquote style="border-width:medium 1.5pt medium medium;border-style:none solid none none;border-color:-moz-use-text-color rgb(16,16,255) -moz-use-text-color -moz-use-text-color;padding:0cm 0cm 0cm 4pt;margin-left:3.75pt;margin-top:5pt;margin-bottom:5pt">
<p class="MsoNormal" style="margin-bottom:12pt"><b><span style="font-family:"Helvetica",sans-serif;color:black">From:
</span></b><span style="font-family:"Helvetica",sans-serif;color:black">"Paparo Bivas, Omer" <<a href="mailto:omer.paparo.bivas@intel.com" target="_blank">omer.paparo.bivas@intel.com</a>><br>
<b>To: </b>"Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>><br>
<b>Cc: </b><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<b>Sent: </b>Sunday, November 20, 2016 8:08:20 AM<br>
<b>Subject: </b>RE: [llvm-dev] RFC: Insertion of nops for performance stability</span><span style="font-size:12pt;font-family:"Helvetica",sans-serif;color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">Hi Hal,</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)"> </span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">A pre-emit pass will indeed be preferable. I originally thought of it, too, however I could not figure out how can such a pass have an access to information on instruction sizes and block alignments.</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">I know that for X86, at least, the branch relaxation is happening during the layout phase in the Assembler, where I plan to integrate the nop insertion such that the new MCPerfNopFragment will just be yet another
kind of fragment to handle when laying out all the fragments: layout for a relaxable branch is relaxing it if necessary, and layout for a MCPerfNopFragment will be computing the number of nops it will contain.</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)"> </span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">Can you please refer me to a pre-emit pass that does something similar?</span><span style="color:black"></span></p>
</blockquote>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black">Just as a quick example, the PowerPC branch relaxation pass, lib/Target/PowerPC/<wbr>PPCBranchSelector.cpp, uses TII->getInstSizeInBytes to determine instruction sizes
and calculates alignment-based padding that will be inserted based on combining instruction-size information with the alignment information from each block (MBB.getAlignment()) and the containing function (MBB.getParent()-><wbr>getAlignment()). Perhaps I'm missing
some complexity, but I'd think that nops could be inserted using a very similar algorithm.<br>
<br>
Two other thoughts:<br>
<br>
1. You can "insert nops" in some (many?) relevant cases by splitting the block and adjusting the block's alignment.<br>
2. You might want to fill the slots with other instructions which can be speculated from successor blocks.<br>
<br>
Thanks again,<br>
Hal</span></p>
<blockquote style="border-width:medium 1.5pt medium medium;border-style:none solid none none;border-color:-moz-use-text-color rgb(16,16,255) -moz-use-text-color -moz-use-text-color;padding:0cm 0cm 0cm 4pt;margin-left:3.75pt;margin-top:5pt;margin-bottom:5pt">
<p class="MsoNormal"><span style="color:rgb(31,73,125)"> </span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">Thanks,</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)">Omer</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:rgb(31,73,125)"> </span><span style="color:black"></span></p>
<div>
<div style="border-right:medium none;border-width:1pt medium medium;border-style:solid none none;padding:3pt 0cm 0cm;border-color:-moz-use-text-color">
<p class="MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> Hal Finkel [<a href="mailto:hfinkel@anl.gov" target="_blank">mailto:hfinkel@anl.gov</a>]
<br>
<b>Sent:</b> Friday, November 18, 2016 20:57<br>
<b>To:</b> Paparo Bivas, Omer <<a href="mailto:omer.paparo.bivas@intel.com" target="_blank">omer.paparo.bivas@intel.com</a>><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [llvm-dev] RFC: Insertion of nops for performance stability</span></p>
</div>
</div>
<p class="MsoNormal"><span style="color:black"> </span></p>
<div>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black"> </span><span style="color:black"></span></p>
<div class="MsoNormal" style="text-align:center" align="center"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black">
<hr align="center" size="3" width="100%">
</span></div>
<blockquote style="border-width:medium medium medium 1.5pt;border-style:none none none solid;padding:0cm;margin-left:3.75pt;margin-top:5pt;margin-bottom:5pt;border-color:-moz-use-text-color rgb(16,16,255) -moz-use-text-color -moz-use-text-color">
<p class="MsoNormal" style="margin-bottom:12pt"><b><span style="font-family:"Helvetica",sans-serif;color:black">From:
</span></b><span style="font-family:"Helvetica",sans-serif;color:black">"Paparo Bivas, Omer via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>To: </b><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<b>Sent: </b>Thursday, November 17, 2016 3:55:43 AM<br>
<b>Subject: </b>[llvm-dev] RFC: Insertion of nops for performance stability</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:black">Hi all,</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">These days I am working on a feature designed to insert nops for IA code generation that will provide performance improvements and performance stability. This feature will not affect other architectures. It will,
however, set up an infrastructure for other architectures to do the same, if ever needed.</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">Here are some examples for cases in which nops can improve performance:</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:black">1.</span><span style="font-size:7pt;font-family:"Times New Roman",serif;color:black">
</span><span style="color:black">DSB (Decoded Stream Buffer) Thrashing.</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:black">DSB is a cache for uops that have been decoded. It is limited to 3 ways per 32B window; 4 or more ways will cause a performance degradation. This can be avoided by aligning with nops. See Zia Ansari's presentation
for more information: <a href="http://schd.ws/hosted_files/llvmdevelopersmeetingbay2016/d9/LLVM-Conference-US-2016-Code-Alignment.pdf" target="_blank">
http://schd.ws/hosted_files/<wbr>llvmdevelopersmeetingbay2016/<wbr>d9/LLVM-Conference-US-2016-<wbr>Code-Alignment.pdf</a></span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:black">2.</span><span style="font-size:7pt;font-family:"Times New Roman",serif;color:black">
</span><span style="color:black">Two or more branches with the same target in a single instruction window may cause poor branch prediction.</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:black">Our recommendation to programmers is to try and keep 2 branches out of the same 16B chunk if they both go to the same target. From the manual:<br>
“Avoid putting two conditional branch instructions in a loop so that both have the same branch target address and, at the same time, belong to (i.e. have their last bytes’ addresses within) the same 16-byte aligned code block.”</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">Let’s see an example for the second case. Consider the following code:</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black">int y;</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black">int x;</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> </span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black">int foo(int i, int m, int p, int q, int *p1, int *p2)</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black">{</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> if (<span style="background:none repeat scroll 0% 0% lime">i+*p1 == p</span> ||
<span style="background:none repeat scroll 0% 0% aqua">i-*p2 > m</span> || <span style="background:none repeat scroll 0% 0% silver">
i == q</span>) {</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> y++;</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> x++;</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> }</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> </span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> return 0;</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black">}</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">The two last || clauses of the if will be translated to two conditional jumps to the same target. The generated code will look like so:</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black">foo:</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 0: 48 8b 44 24 28 movq 40(%rsp), %rax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 5: 8b 00 movl (%rax), %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 7: 01 c8 addl %ecx, %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 9: 44 39 c0 cmpl %r8d, %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> <span style="background:none repeat scroll 0% 0% lime">
c: 75 0f jne 15 <foo+0x1D></span></span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> e: ff 05 00 00 00 00 incl (%rip)</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 14: ff 05 00 00 00 00 incl (%rip)</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 1a: 31 c0 xorl %eax, %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 1c: c3 retq</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 1d: 44 39 c9 cmpl %r9d, %ecx</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> <span style="background:none repeat scroll 0% 0% silver">
20: 74 ec je -20 <foo+0xE></span></span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 22: 48 8b 44 24 30 movq 48(%rsp), %rax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 27: 2b 08 subl (%rax), %ecx</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 29: 39 d1 cmpl %edx, %ecx</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> <span style="background:none repeat scroll 0% 0% aqua">
2b: 7f e1 jg -31 <foo+0xE></span></span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 2d: 31 c0 xorl %eax, %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 2f: c3 retq</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">Note: the first if clause jump is the jne instruction at 0x0C, the second if clause jump is the jg instruction at 0x2B and the third if clause jump is the je instruction at 0x20. Also note that the jg and je share
a 16 byte window, which is exactly the situation we wish to avoid (consider the case in which foo is called from inside a loop. This will cause performance penalty).</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">The generated code after my changes will look like so:</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black">foo:</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 0: 48 8b 44 24 28 movq 40(%rsp), %rax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 5: 8b 00 movl (%rax), %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 7: 01 c8 addl %ecx, %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 9: 44 39 c0 cmpl %r8d, %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> c: 75 0f jne 15 <foo+0x1D></span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> e: ff 05 00 00 00 00 incl (%rip)</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 14: ff 05 00 00 00 00 incl (%rip)</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 1a: 31 c0 xorl %eax, %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 1c: c3 retq</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 1d: 44 39 c9 cmpl %r9d, %ecx</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 20: 74 ec je -20 <foo+0xE></span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 22: 48 8b 44 24 30 movq 48(%rsp), %rax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 27: 2b 08 subl (%rax), %ecx</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 29: 39 d1 cmpl %edx, %ecx</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> <span style="background:none repeat scroll 0% 0% yellow">
2b: 0f 1f 40 00 nopl (%rax)</span></span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 2f: 7f dd jg -35 <foo+0xE></span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 31: 31 c0 xorl %eax, %eax</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";color:black"> 33: c3 retq</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">The only change is the nopl at 0x2B, before the jg, which pushes the jg instruction to the next 16 byte window, and thus avoids the undesired situation. Note that, in this case, in order to push an instruction
to the next window it is sufficient to push its last byte to the next window.</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">Due to the nature of those performance nops, which often rely on the layout of the code (e.g. number of instructions in a 16/32B window) that is only known in assembly time, the insertion is divided to two phases:</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:black">1.</span><span style="font-size:7pt;font-family:"Times New Roman",serif;color:black">
</span><span style="color:black">Marking "suspicious" places while encoding, i.e. hotspots that may cause a performance penalty, during the encoding.</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:black">2.</span><span style="font-size:7pt;font-family:"Times New Roman",serif;color:black">
</span><span style="color:black">Computing the actual number (zero or greater) of required nops in order to avoid a performance penalty.</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">In order to achieve that, I am introducing a new kind of MCFragment named MCPerfNopFragment. It will be the connecting link between the two phases:</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:black">1.</span><span style="font-size:7pt;font-family:"Times New Roman",serif;color:black">
</span><span style="color:black">During encoding, the object streamer (MCObjectStreamer) will query the backend for the need of a MCPerfNopFragment before every encoded instruction. If required, a MCPerfNopFragment will be created and inserted to the MCSection.</span></p>
<p class="m_-4988723288261583761MsoListParagraph"><span style="color:black">2.</span><span style="font-size:7pt;font-family:"Times New Roman",serif;color:black">
</span><span style="color:black">During the assembly phase:</span></p>
<p class="m_-4988723288261583761MsoListParagraph" style="margin-left:72pt"><span style="color:black">a.</span><span style="font-size:7pt;font-family:"Times New Roman",serif;color:black">
</span><span style="color:black">When computing the fragment size in MCAssembler::<wbr>computeFragmentSize the Assembler will consult the backend and will provide it the layout in order to determine the required size of the fragment. Note that the computed size
may change from call to call, similarly to the process of computing the size of a MCAlignFragment.</span></p>
<p class="m_-4988723288261583761MsoListParagraph" style="margin-left:72pt"><span style="color:black">b.</span><span style="font-size:7pt;font-family:"Times New Roman",serif;color:black">
</span><span style="color:black">When writing the fragment the assembler will again use the backend in order to write the required number of nops.</span></p>
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal" id="m_-4988723288261583761DWT5917"><span style="color:black">Comments and questions are welcome.</span></p>
</blockquote>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black">Do you need to insert the nops as such a late stage? We have other components that insert nops during post-RA scheduling, for example. Even later, nops could be inserted
during a pre-emit pass (similar to where other backends do branch relaxation/selection). The branch relaxation process also relies on knowing the layout of the code, but gathers this information from the available information on instruction sizes, block alignments,
etc.<br>
<br>
-Hal</span><span style="color:black"></span></p>
<blockquote style="border-width:medium medium medium 1.5pt;border-style:none none none solid;padding:0cm;margin-left:3.75pt;margin-top:5pt;margin-bottom:5pt;border-color:-moz-use-text-color rgb(16,16,255) -moz-use-text-color -moz-use-text-color">
<p class="MsoNormal"><span style="color:black"> </span></p>
<p class="MsoNormal"><span style="color:black">Thanks,</span></p>
<p class="MsoNormal"><span style="color:black">Omer</span></p>
<p><span style="font-family:"Helvetica",sans-serif;color:black">------------------------------<wbr>------------------------------<wbr>---------<br>
Intel Israel (74) Limited</span><span style="color:black"></span></p>
<p><span style="font-family:"Helvetica",sans-serif;color:black">This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</span><span style="color:black"></span></p>
<p class="MsoNormal"><span style="font-size:12pt;font-family:"Helvetica",sans-serif;color:black"><br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a></span><span style="color:black"></span></p>
</blockquote>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black"><br>
<br>
<br>
-- </span><span style="color:black"></span></p>
<div>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black">Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory</span><span style="color:black"></span></p>
</div>
</div>
<p><span style="color:black">------------------------------<wbr>------------------------------<wbr>---------<br>
Intel Israel (74) Limited</span></p>
<p><span style="color:black">This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</span></p>
</blockquote>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black"><br>
<br>
<br>
-- </span></p>
<div>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Arial",sans-serif;color:black">Hal Finkel<br>
Lead, Compiler Technology and Programming Languages<br>
Leadership Computing Facility<br>
Argonne National Laboratory</span></p>
</div>
</div>
</div>
<p>------------------------------<wbr>------------------------------<wbr>---------<br>
Intel Israel (74) Limited</p>
<p>This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</p></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Lead, Compiler Technology and Programming Languages<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></div></div></div><br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">Software Engineer - Compiler Toolchain<br>Employee of Facebook Inc.</div>
</div></div>