<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)">
<style><!--
/* Font Definitions */
@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;}
/* 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:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
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;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1333336431;
mso-list-type:hybrid;
mso-list-template-ids:980057034 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1
{mso-list-id:1361517614;
mso-list-type:hybrid;
mso-list-template-ids:2093364110 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l1:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2
{mso-list-id:1528906733;
mso-list-type:hybrid;
mso-list-template-ids:199755004 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l2:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l2:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
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="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal">Hi all,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Here are some examples for cases in which nops can improve performance:<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo3"><![if !supportLists]><span style="mso-list:Ignore">1.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>DSB (Decoded Stream Buffer) Thrashing.<o:p></o:p></p>
<p class="MsoListParagraph">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:
http://schd.ws/hosted_files/llvmdevelopersmeetingbay2016/d9/LLVM-Conference-US-2016-Code-Alignment.pdf<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo3"><![if !supportLists]><span style="mso-list:Ignore">2.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>Two or more branches with the same target in a single instruction window may cause poor branch prediction.<o:p></o:p></p>
<p class="MsoListParagraph">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.”<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Let’s see an example for the second case. Consider the following code:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int y;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int x;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">int foo(int i, int m, int p, int q, int *p1, int *p2)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">{<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> if (<span style="background:lime;mso-highlight:lime">i+*p1 == p</span> ||
<span style="background:aqua;mso-highlight:aqua">i-*p2 > m</span> || <span style="background:silver;mso-highlight:silver">
i == q</span>) {<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> y++;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> x++;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> }<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> return 0;<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">foo:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 0: 48 8b 44 24 28 movq 40(%rsp), %rax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 5: 8b 00 movl (%rax), %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 7: 01 c8 addl %ecx, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 9: 44 39 c0 cmpl %r8d, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> <span style="background:lime;mso-highlight:lime">
c: 75 0f jne 15 <foo+0x1D></span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> e: ff 05 00 00 00 00 incl (%rip)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 14: ff 05 00 00 00 00 incl (%rip)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 1a: 31 c0 xorl %eax, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 1c: c3 retq<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 1d: 44 39 c9 cmpl %r9d, %ecx<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> <span style="background:silver;mso-highlight:silver">
20: 74 ec je -20 <foo+0xE></span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 22: 48 8b 44 24 30 movq 48(%rsp), %rax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 27: 2b 08 subl (%rax), %ecx<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 29: 39 d1 cmpl %edx, %ecx<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> <span style="background:aqua;mso-highlight:aqua">
2b: 7f e1 jg -31 <foo+0xE></span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 2d: 31 c0 xorl %eax, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 2f: c3 retq<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The generated code after my changes will look like so:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-family:"Courier New"">foo:<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 0: 48 8b 44 24 28 movq 40(%rsp), %rax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 5: 8b 00 movl (%rax), %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 7: 01 c8 addl %ecx, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 9: 44 39 c0 cmpl %r8d, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> c: 75 0f jne 15 <foo+0x1D><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> e: ff 05 00 00 00 00 incl (%rip)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 14: ff 05 00 00 00 00 incl (%rip)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 1a: 31 c0 xorl %eax, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 1c: c3 retq<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 1d: 44 39 c9 cmpl %r9d, %ecx<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 20: 74 ec je -20 <foo+0xE><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 22: 48 8b 44 24 30 movq 48(%rsp), %rax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 27: 2b 08 subl (%rax), %ecx<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 29: 39 d1 cmpl %edx, %ecx<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> <span style="background:yellow;mso-highlight:yellow">
2b: 0f 1f 40 00 nopl (%rax)</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 2f: 7f dd jg -35 <foo+0xE><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 31: 31 c0 xorl %eax, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New""> 33: c3 retq<o:p></o:p></span></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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:<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l2 level1 lfo1"><![if !supportLists]><span style="mso-list:Ignore">1.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>Marking "suspicious" places while encoding, i.e. hotspots that may cause a performance penalty, during the encoding.<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l2 level1 lfo1"><![if !supportLists]><span style="mso-list:Ignore">2.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>Computing the actual number (zero or greater) of required nops in order to avoid a performance penalty.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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:<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo2"><![if !supportLists]><span style="mso-list:Ignore">1.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>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.<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l1 level1 lfo2"><![if !supportLists]><span style="mso-list:Ignore">2.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>During the assembly phase:<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:72.0pt;text-indent:-18.0pt;mso-list:l1 level2 lfo2">
<![if !supportLists]><span style="mso-list:Ignore">a.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>When computing the fragment size in MCAssembler::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.<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:72.0pt;text-indent:-18.0pt;mso-list:l1 level2 lfo2">
<![if !supportLists]><span style="mso-list:Ignore">b.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]><span dir="LTR"></span>When writing the fragment the assembler will again use the backend in order to write the required number of nops.<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">Comments and questions are welcome.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal">Omer<o:p></o:p></p>
</div>
<p>---------------------------------------------------------------------<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></body>
</html>