<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
I guess there are two separate questions here.
<div class=""><br class="">
</div>
<div class="">1) Currently element atomic memcpys are lowered to calls to predefined symbols. If we want to provide an efficient lowering instead, how do we do this?</div>
<div class=""><br class="">
</div>
<div class="">We can follow the same scheme as the regular memcpy. There is a target-specific hook in SelectionDAGTargetInfo::EmitTargetCodeForMemcpy. We can introduce a similar hook for element-atomic memcpy. I’m not sure though how hard it would be to emit
a vectorized loop in SelectionDAG representation.</div>
<div class=""><br class="">
</div>
<div class="">We can have a middle-end pass which does the lowering instead. We can either emit a hand-rolled vectorized loop or we can emit a naive loop and rely on the vectorizer to optimize it.</div>
<div class=""><br class="">
</div>
<div class="">If we do the middle-end lowering we would need to think about interactions with the backed optimizations for element atomic memcpys. E.g. an element atomic memcpy with a small constant length is currently converted into a series of loads and stores
in the backed. If you rewrite all element atomic memcpys into vectorized loops in the middle-end you might obscure this optimization.</div>
<div class=""><br class="">
</div>
<div class="">2) If we decide to do the middle-end lowering we would need to solve the element atomic vector problem. If we emit a naive loop today, it won’t be vectorized because an element-wise atomic vector can’t be represented in the IR. If we decide to
write a hand-rolled vectorized loop we will have the same issue.</div>
<div class=""><br class="">
</div>
<div class="">Here is some previous discussion on the topic of introducing element-wise atomic vectors.</div>
<div class=""><a href="https://lists.llvm.org/pipermail/llvm-dev/2015-December/093237.html" class="">https://lists.llvm.org/pipermail/llvm-dev/2015-December/093237.html</a></div>
<div class=""><br class="">
</div>
<div class="">Philip might have better insight on what it will take to introduce this construct, since he attempted it back then.</div>
<div class=""><br class="">
</div>
<div class="">Artur</div>
<div class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">On Aug 6, 2021, at 3:16 AM, Max Kazantsev via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div class="WordSection1" style="page: WordSection1; caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;">
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">Hi everyone,<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">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 class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">The obvious way to lower @llvm.memcpy.element.unordered.atomic is smth like<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class="">for (i = 0; i < len; i++) {<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class=""> v = load atomic src[i]<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class=""> store atomic v, dest[i]<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class="">}<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">But this code itself is awkwardly slow, compared to efficient implementations of regular memcpy. What we would really want to do is<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class="">for (i = 0; i < len; i += stride) {<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class=""> vector_v = load element atomic <stride x i32><o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class=""> store element atomic vector_v, dest[i]<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class="">}<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">However, currently there is no way to express this concept in LLVM. What we can do is<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class="">for (i = 0; i < len; i += stride) {<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class=""> vector_v = load <stride x i32><o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class=""> store vector_v, dest[i]<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" style="font-family: "Courier New";" class="">}<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">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 class=""></o:p></span></div>
<ul type="disc" style="margin-bottom: 0cm; margin-top: 0cm;" class="">
<li class="MsoListParagraph" style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" class="">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 class=""></o:p></span></li><ul type="circle" style="margin-bottom: 0cm; margin-top: 0cm;" class="">
<li class="MsoListParagraph" style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" class="">I don’t think any pass does it in reality, but they have a right to.<o:p class=""></o:p></span></li></ul>
<li class="MsoListParagraph" style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" class="">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 class=""></o:p></span></li><li class="MsoListParagraph" style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" class="">In codegen level, ymm load/store may be torn. For example, I find this pass that says:<o:p class=""></o:p></span></li></ul>
<div style="margin: 0cm 0cm 0cm 70.8pt; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Target/X86/X86AvoidStoreForwardingBlocks.cpp" style="color: rgb(5, 99, 193); text-decoration: underline;" class="">https://github.com/llvm-mirror/llvm/blob/master/lib/Target/X86/X86AvoidStoreForwardingBlocks.cpp</a><o:p class=""></o:p></span></div>
<p class="MsoNormal" style="margin: 0cm 0cm 3pt 70.8pt; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" style="font-size: 9pt; font-family: "Courier New"; color: rgb(29, 28, 29);" class="">// The pass currently only handles cases where memcpy is lowered to<o:p class=""></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 3pt 70.8pt; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" style="font-size: 9pt; font-family: "Courier New"; color: rgb(29, 28, 29);" class="">// XMM/YMM registers, it tries to break the memcpy into smaller copies.<o:p class=""></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 3pt 70.8pt; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" style="font-size: 9pt; font-family: "Courier New"; color: rgb(29, 28, 29);" class="">// breaking the memcpy should be possible since there is no atomicity<o:p class=""></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 3pt 70.8pt; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" style="font-size: 9pt; font-family: "Courier New"; color: rgb(29, 28, 29);" class="">// guarantee for loads and stores to XMM/YMM.<o:p class=""></o:p></span></p>
<p class="MsoNormal" style="margin: 0cm 0cm 3pt 45.8pt; font-size: 11pt; font-family: Calibri, sans-serif;">
<span lang="EN-US" class="">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: 9pt; font-family: "Courier New"; color: rgb(29, 28, 29);" class=""><o:p class=""></o:p></span></p>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">However, there is a bit of a positive moment. Specification of @llvm.memcpy.element.unordered.atomic says:<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<p style="margin-right: 0cm; margin-bottom: 6pt; margin-left: 0cm; background-color: white; background-position: initial initial; background-repeat: initial initial;" class="">
<span lang="EN-US" style="font-size: 10.5pt; font-family: "Lucida Sans Unicode", sans-serif;" class="">> For each of the input pointers </span><span class="pre"><span lang="EN-US" style="font-size: 10pt; font-family: Consolas;" class="">align</span></span><span lang="EN-US" style="font-size: 10.5pt; font-family: "Lucida Sans Unicode", sans-serif;" class=""> 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: 10pt; font-family: Consolas;" class="">element_size</span></span><span lang="EN-US" style="font-size: 10.5pt; font-family: "Lucida Sans Unicode", sans-serif;" class="">.
Caller guarantees that both the source and destination pointers are aligned to that boundary.<o:p class=""></o:p></span></p>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">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<span class="Apple-converted-space"> </span><b class="">(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 class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">This might not be true for other platforms, but we should start somewhere.<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<b class=""><span lang="EN-US" class="">Proposition<o:p class=""></o:p></span></b></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">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 class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">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 class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">Please discuss if you have an opinion on how to do it best, and what possible problems do you anticipate.<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">Thanks,<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class="">Max<o:p class=""></o:p></span></div>
<div style="margin: 0cm; font-size: 11pt; font-family: Calibri, sans-serif;" class="">
<span lang="EN-US" class=""><o:p class=""> </o:p></span></div>
</div>
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">_______________________________________________</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">LLVM
Developers mailing list</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<a href="mailto:llvm-dev@lists.llvm.org" style="color: rgb(5, 99, 193); text-decoration: underline; font-family: Helvetica; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">llvm-dev@lists.llvm.org</a><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="color: rgb(5, 99, 193); text-decoration: underline; font-family: Helvetica; font-size: 14px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></div>
</blockquote>
</div>
<br class="">
</div>
</body>
</html>