<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: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:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
@font-face
{font-family:"Lucida Sans Unicode";
panose-1:2 11 6 2 3 5 4 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
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;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
span.pre
{mso-style-name:pre;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:2.0cm 42.5pt 2.0cm 3.0cm;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:393360406;
mso-list-template-ids:-828888450;}
@list l0:level1
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:\F0B7;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1
{mso-list-id:548227413;
mso-list-type:hybrid;
mso-list-template-ids:185657094 68747265 68747267 68747269 68747265 68747267 68747269 68747265 68747267 68747269;}
@list l1:level1
{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 l1: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 l1: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 l1: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 l1: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 l1: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 l1: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 l1: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 l1: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="RU" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US">Hi everyone,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Recently I started to work on optimization of @llvm.memcpy.element.unordered.atomic intrinsics to make them available and widely usable. Currently, LLVM provides a langref description for it, but no baked-in lowering.
To change this situation, some steps need to be taken.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">The obvious way to lower @llvm.memcpy.element.unordered.atomic is smth like<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New"">for (i = 0; i < len; i++) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New""> v = load atomic src[i]<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New""> store atomic v, dest[i]<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">But this code itself is awkwardly slow, compared to efficient implementations of regular memcpy. What we would really want to do is<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New"">for (i = 0; i < len; i += stride) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New""> vector_v = load element atomic <stride x i32><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New""> store element atomic vector_v, dest[i]<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">However, currently there is no way to express this concept in LLVM. What we can do is<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New"">for (i = 0; i < len; i += stride) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New""> vector_v = load <stride x i32><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New""> store vector_v, dest[i]<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:"Courier New"">}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">When max vector size is supported on the platform, we can hope (but just hope!) that it will lower into corresponding vector load/stores, such as ymm/xmm load/stores in X86. But:<o:p></o:p></span></p>
<ul style="margin-top:0cm" type="disc">
<li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo3"><span lang="EN-US">There is no guarantee of that. Some IR pass theoretically may break the vectors as it pleases because there is no atomicity demand.<o:p></o:p></span></li><ul style="margin-top:0cm" type="circle">
<li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level2 lfo3"><span lang="EN-US">I don’t think any pass does it in reality, but they have a right to.<o:p></o:p></span></li></ul>
<li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo3"><span lang="EN-US">Even if it is lowered into ymm/xmm/smth like this, yhere is no guarantee of atomicity of xmm or ymm registers. So even if this code is lowered into corresponding
ymm stores, the whole store might not be atomic (especially if it crosses the boundary of cache line).<o:p></o:p></span></li><li class="MsoListParagraph" style="margin-left:0cm;mso-list:l1 level1 lfo3"><span lang="EN-US">In codegen level, ymm load/store may be torn. For example, I find this pass that says:<o:p></o:p></span></li></ul>
<p class="MsoNormal" style="margin-left:70.8pt"><span lang="EN-US"><a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Target/X86/X86AvoidStoreForwardingBlocks.cpp">https://github.com/llvm-mirror/llvm/blob/master/lib/Target/X86/X86AvoidStoreForwardingBlocks.cpp</a><o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:3.0pt;margin-right:0cm;margin-bottom:3.0pt;margin-left:70.8pt">
<span lang="EN-US" style="font-size:9.0pt;font-family:"Courier New";color:#1D1C1D;mso-fareast-language:RU">// The pass currently only handles cases where memcpy is lowered to<o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:3.0pt;margin-right:0cm;margin-bottom:3.0pt;margin-left:70.8pt">
<span lang="EN-US" style="font-size:9.0pt;font-family:"Courier New";color:#1D1C1D;mso-fareast-language:RU">// XMM/YMM registers, it tries to break the memcpy into smaller copies.<o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:3.0pt;margin-right:0cm;margin-bottom:3.0pt;margin-left:70.8pt">
<span lang="EN-US" style="font-size:9.0pt;font-family:"Courier New";color:#1D1C1D;mso-fareast-language:RU">// breaking the memcpy should be possible since there is no atomicity<o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:3.0pt;margin-right:0cm;margin-bottom:3.0pt;margin-left:70.8pt">
<span lang="EN-US" style="font-size:9.0pt;font-family:"Courier New";color:#1D1C1D;mso-fareast-language:RU">// guarantee for loads and stores to XMM/YMM.<o:p></o:p></span></p>
<p class="MsoNormal" style="mso-margin-top-alt:3.0pt;margin-right:0cm;margin-bottom:3.0pt;margin-left:45.8pt">
<span lang="EN-US">So breakedge of non-atomic xmm/ymm loads is a real thing that should be accounted for.</span><span lang="EN-US" style="font-size:9.0pt;font-family:"Courier New";color:#1D1C1D;mso-fareast-language:RU"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">However, there is a bit of a positive moment. Specification of @llvm.memcpy.element.unordered.atomic says:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p style="mso-margin-top-alt:9.6pt;margin-right:0cm;margin-bottom:6.0pt;margin-left:0cm;background:white">
<span lang="EN-US" style="font-size:10.5pt;font-family:"Lucida Sans Unicode",sans-serif;color:black">> For each of the input pointers </span><span class="pre"><span lang="EN-US" style="font-size:10.0pt;font-family:Consolas;color:black">align</span></span><span lang="EN-US" style="font-size:10.5pt;font-family:"Lucida Sans Unicode",sans-serif;color:black"> parameter
attribute must be specified. It must be a power of two no less than the </span><span class="pre"><span lang="EN-US" style="font-size:10.0pt;font-family:Consolas;color:black">element_size</span></span><span lang="EN-US" style="font-size:10.5pt;font-family:"Lucida Sans Unicode",sans-serif;color:black">.
Caller guarantees that both the source and destination pointers are aligned to that boundary.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">So if we somehow enforce lowering of the vector stores into hardware supported operations and prohibit other passes from tearing it apart, we’ll have ymm loads aligned by some basic type (say i32). It’s a widely known
that on X86, despite xmm/ymm stores are not atomic, they don’t tear words if they are aligned by the width of the word
<b>(please correct me if it’s not true!)</b>. So by just enforcing straightforward lowering of such loads into ymm/xmm loads, and prohibit all passes (including codegen) to touch it, we should have the desired atomic behavior on X86.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">This might not be true for other platforms, but we should start somewhere.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US">Proposition<o:p></o:p></span></b></p>
<p class="MsoNormal"><span lang="EN-US">We could have another flag in load/store instructions, similar to atomic, being element-atomic which only matters for vector loads and stores. We can guarantee that these loads only survive till codegen on platforms that
support it. We can also go and update all passes that potentially tear vectors (I don’t think there is many) and prohibit them from touching these loads and stores. And we’ll also need an assert (on X86) that the pointers are aligned properly.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">It doesn’t look a very hard task (the only hard thing is to detect all such places), but maybe there are some pitfalls I don’t know about.
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Please discuss if you have an opinion on how to do it best, and what possible problems do you anticipate.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Max<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
</div>
</body>
</html>