<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=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Aug 28, 2020, at 21:49, Florian Hahn <<a href="mailto:florian_hahn@apple.com" class="">florian_hahn@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta charset="UTF-8" class=""><div style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; 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=""><br class="Apple-interchange-newline"><br class=""><blockquote type="cite" class=""><div class="">On Aug 26, 2020, at 16:40, Florian Hahn via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;"><div class=""><div class=""><blockquote type="cite" class=""><div class="">On Aug 25, 2020, at 23:06, John McCall <<a href="mailto:rjmccall@apple.com" class="">rjmccall@apple.com</a>> wrote:</div><div class=""><div class=""><div class="" style="font-family: sans-serif;"><div class="" style="white-space: normal;"><p dir="auto" class="">C allows overlapping assignments only when the overlap is exact, i.e. the addresses are exactly the same. I agree that just emitting memcpy isn’t strictly legal, because neither C nor LLVM allows even exact overlap. On the other hand, Clang would really like to avoid emitting extra control flow here, because exact overlap is uncommon enough that emitting a no-op memcpy (if it were indeed a no-op) is definitely the right trade-off in practice; and LLVM probably won’t reliably remove branches around a memcpy call if we add them. And it’s very hard to imagine a memcpy implementation that actually wouldn’t work with exact overlap (maybe something that tried to just remap pages?).</p><p dir="auto" class="">I think we have are four options:</p><ol class=""><li value="1" class="">We can relax<span class="Apple-converted-space"> </span><code bgcolor="#F7F7F7" class="" style="background-color: rgb(247, 247, 247); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; margin: 0px; padding: 0px 0.4em;">llvm.memcpy</code><span class="Apple-converted-space"> </span>to allow exact overlap. Practically, this would depend on memcpy being a no-op on exact overlap; we definitely wouldn’t want<span class="Apple-converted-space"> </span><em class="">LLVM</em><span class="Apple-converted-space"> </span>to have to start inserting control flow around memcpy calls.</li><li value="2" class="">We can make Clang emit assignments with<span class="Apple-converted-space"> </span><code bgcolor="#F7F7F7" class="" style="background-color: rgb(247, 247, 247); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; margin: 0px; padding: 0px 0.4em;">llvm.memmove</code>. This would make assignment work even with non-exact overlap, which is unnecessary; I’m not sure the cost is that high.</li><li value="3" class="">We can make Clang emit an explicit check and control flow around memcpy when there might be overlap. Clang IRGen should already maintain the right information to avoid doing this when e.g. initializing a variable.</li><li value="4" class="">We can add a new intrinsic — or some sort of decoration of the existing one — that does a memcpy but allows exact overlap.</li></ol></div></div></div></div></blockquote><br class=""></div><div class="">Thanks for summarizing the options! I think 4. would probably the safest option, because we won’t have to track down the places that use the non-overlapping assumption. There might also be such cases somewhere downstream, which might be broken silently. If Clang already has the information when the operands cannot overlap (as mentioned in 3.), we only have to emit the non-overlapping version for those cases, causing the least amount of change for the generated IR.</div><div class=""><br class=""></div><div class="">1. Also seems possible (there probably are not too many places in LLVM that use the non-overlapping assumption), but I think in some cases the non-overlapping info can be a useful property to convey for frontends.</div></div></div></div></blockquote><br class=""></div><div style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; 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=""><br class=""></div><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; 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="">I took a look at the places in LLVM that make use of the non-overlapping guarantee and it appears BasicAliasAnalysis is the only place. I put up a patch </span><a href="https://reviews.llvm.org/D86815" class="" style="font-family: Helvetica; font-size: 12px; 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;">https://reviews.llvm.org/D86815</a><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; 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 class="Apple-converted-space"> </span>to illustrate the impact on the code & tests. It seems quite manageable. It might be feasible to start with removing the guarantee and re-introduce a variant with the additional guarantee.</span><div class="" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; 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;"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; 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;">What do you think? Alternatively I can also put up a patch to add a new variant without the guarantee. In that case, I would appreciate some pointers on how to tell whether arguments are guaranteed to not overlap in Clang.</div></div></blockquote><br class=""></div><div><br class=""></div>Just a quick update. The behavior of llvm.memcpy has been adjusted and the alias analysis code has been updated: <a href="https://reviews.llvm.org/rG1ddb3a369f7ebdf738486cd60261c3143658c0e6" style="white-space: pre-wrap; color: rgb(102, 51, 102);" class="">https://reviews.llvm.org/rG1ddb3a369f7ebdf738486cd60261c3143658c0e6</a><div class=""><br class=""></div></body></html>