<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">
<div dir="auto" class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">
<div class=""><br class="">
</div>
<div class="">Hi all,</div>
<div class=""> We somewhat recently created/updated element-wise unordered-atomic versions of the memcpy, memmove, and memset memory intrinsics:</div>
<div class="">Memcpy: <a href="https://reviews.llvm.org/rL305558" class="">https://reviews.llvm.org/rL305558</a></div>
<div class="">Memmove: <a href="https://reviews.llvm.org/rL307796" class="">https://reviews.llvm.org/rL307796</a></div>
<div class="">Memset: <a href="https://reviews.llvm.org/rL307854" class="">https://reviews.llvm.org/rL307854</a></div>
<div class=""><br class="">
</div>
<div class=""> These intrinsics are semantically similar to the regular versions. The main difference is that the underlying operation is performed entirely with unordered atomic loads & stores of a given size. </div>
<div class=""><br class="">
</div>
<div class=""> Our ultimate purpose is to enable exploitation of the memory intrinsic idioms and optimizations in languages like Java that make extensive use of unordered-atomic loads & stores. To this end, we will eventually have to add these new intrinsics
to the instruction class hierarchy, and teach passes how to deal with them; talking about how to do this is the purpose of this RFC.</div>
<div class=""><br class="">
</div>
<div class=""> We have started adding canary tests to some passes, and will continue to do so in preparation for adding the element atomic intrinsics to the instruction class hierarchy. These canary tests are simply placeholders that show that the pass in question
currently does nothing with the new element atomic memory instrinics, and could/should generally start failing once the unordered-atomic memory intrinsics are added to the instruction class hierarchy — telling us which passes need to be updated. For example: <a href="https://reviews.llvm.org/rL308247" class="">https://reviews.llvm.org/rL308247</a></div>
<div class=""><br class="">
</div>
<div class=""> For adding the new intrinsics to the instruction class hierarchy, the plan will be to add them one at a time — add the intrinsic to the hierarchy, and flush out all problems before adding the next. We’re thinking that it would be best to start
with memset, then memcpy, then memmove; memset is kind of it’s own thing, and there are some passes that change memcpy/memmove into a memset so it would be beneficial to have that in place before memcpy/memmove, and there are also passes that change memmove
into memcpy but I haven’t found any that go the other way (I can’t imagine why you’d want to) so it would be good to have memcpy squared away before doing memmove.</div>
<div class=""><br class="">
</div>
<div class=""> There are a few options that we have thought of for adding the new memory intrinsics to the instruction class hierarchy. We have a preference for the first option, but would appreciate thoughts/opinions/discussion on the best way to insert the
element atomic intrinsics into the hierarchy. For background, the relevant portion of the current hierarchy looks like:</div>
<div class=""><br class="">
</div>
<div class="">MemIntrinsic</div>
<div class="">* MemSetInst</div>
<div class="">* MemTransferInst</div>
<div class=""> ** MemCpyInst</div>
<div class=""> ** MemMoveInst </div>
<div class=""><br class="">
</div>
<div class="">Option 1)</div>
<div class="">-------------</div>
<div class=""> Do not add any new classes to the hierarchy. Instead, teach each class to recognize the unordered-atomic variant as belonging to the class (ex: element unordered-atomic memcpy is recognized as a MemCpyInst, MemTransferInst, and a MemIntrinsic),
and add a query method like ‘isUnorderedAtomic’ that will tell you whether the underlying intrinsic is one of the element atomic variants. Alternatively, the method could be a more generic ‘getOrdering()’ that would return an AtomicOrdering; though a memory
intrinsic that is required to be implemented with ordered-atomic instructions strikes me as unlikely to ever be desired.</div>
<div class=""><br class="">
</div>
<div class=""> There is precedent for encoding the intrinsic property as a query method both within the current memory intrinsic hierarchy itself (the isVolatile() method) and the load/store instruction classes.</div>
<div class=""><br class="">
</div>
<div class=""> The way forward with this option would be to: </div>
<div class=""> (i) add the method to MemInstrinsic (returning false); then</div>
<div class=""> (ii) update all passes, one at a time, to bail-out if isUnorderedAtomic() is true; then</div>
<div class=""> (iii) add an intrinsic to the class hierarchy; then</div>
<div class=""> (iv) update passes to exploit isUnorderedAtomic() one at a time</div>
<div class=""> (v) repeat (iii) & (iv) for each unordered-atomic intrinsic</div>
<div class=""><br class="">
</div>
<div class="">Pros:</div>
<div class=""> Significant reduction in copy/paste code over other options; passes that use visitors would require some refactoring or some copy/paste to mirror behaviour if the unordered-atomic intrinsics are separate classes.</div>
<div class=""> Lends itself to a clear & simple incremental path-forward; each pass can be updated independently of the others which will make reviews more achievable due to not requiring people with working knowledge much beyond the single pass.</div>
<div class=""> Easy to leverage new work on memory intrinsic optimization for the unordered-atomic variants; even near-zero cost for passes that won’t be affected by unordered-atomicity.</div>
<div class="">Cons:</div>
<div class=""> One more attribute to check when implementing a pass that handles a memory intrinsic; could lead to some unexpected bugs where we change an unordered-atomic intrinsic into a regular intrinsic.</div>
<div class=""><br class="">
</div>
<div class=""> The con here is pretty concerning. We risk making it easy for a developer to forget about the element-atomic variants when introducing an optimization that converts a memmove/memcpy/memset. Such an optimization could, conceivably, result in an
unordered-atomic intrinsic being erroneously converted to drop its atomicity; such a bug would only exhibit as a race condition in the resulting program, and could be an absolute beast to debug. The only way to prevent such bugs would be very careful code
reviews.</div>
<div class=""><br class="">
</div>
<div class="">Option 2)</div>
<div class="">-------------</div>
<div class=""> Add separate classes to the hierarchy for each intrinsic. There are a few different ways that this could be organized (note: UA* = unordered-atomic version of intrinsic, to save typing):</div>
<div class=""><br class="">
</div>
<div class="">a) Completely disjoint hierarchy</div>
<div class="">
<div class="">UAMemIntrinsic</div>
<div class="">* UAMemSetInst</div>
<div class="">* UAMemTransferInst</div>
<div class=""> ** UAMemCpyInst</div>
<div class=""> ** UAMemMoveInst</div>
</div>
<div class="">
<div class="">MemIntrinsic</div>
<div class="">* MemSetInst</div>
<div class="">* MemTransferInst</div>
<div class=""> ** MemCpyInst</div>
<div class=""> ** MemMoveInst </div>
</div>
<div class=""><br class="">
</div>
<div class=""> This organization has the benefit of not interacting/interfering with the regular memory intrinsics in any way. That’s also a big downside; most/many passes are going to be able to function on unordered-atomic memory intrinsics the same as they
do for the regular memory intrinsics. In some cases this will just mean adding another few isa<> checks at strategic positions, but in many cases this will mean code clones and/or clever refactoring (ex: for passes that incorporate visitors). </div>
<div class=""> Being completely disjoint also makes this option super easy to add in incrementally; no pass will know what to do with an unordered-atomic intrinsic until explicitly taught. Of course that’s also a downside as it means that optimizing the unordered-atomic
memory intrinsics always has to be explicitly added — nothing comes for free from the regular memory intrinsic work.</div>
<div class=""><br class="">
</div>
<div class="">b) Disjoint sub-hierarchy of MemIntrinsic</div>
<div class="">MemIntrinsic</div>
<div class="">* MemSetInst</div>
<div class="">* UAMemSetInst</div>
<div class="">* MemTransferInst</div>
<div class=""> ** MemCpyInst</div>
<div class=""> ** MemMoveInst</div>
<div class="">* UAMemTransferInst</div>
<div class=""> ** UAMemCpyInst</div>
<div class=""> ** UAMemMoveInst</div>
<div class=""><br class="">
</div>
<div class=""> Similar to the (2a) option in a lot of ways, but with some added complications for even the regular memory intrinsics. The hierarchy immediately below MemIntrinsic becomes much wider, so it is no longer sufficient to check isa<MemTransferInst>
to narrow down memcpy/memmove vs memset. Also, similar to (2a), there’s the potential for a lot of code clones in passes that incorporate visitors.</div>
<div class=""><br class="">
</div>
<div class=""> The way forward with this option would be similar to 2a with the exception that we’d have to go through the whole codebase to make sure that "if (! isa<MemTransferInst>) then Inst is memset” and equivalent checks resolve correctly.</div>
<div class=""><br class="">
</div>
<div class="">c) Child classes of the regular intrinsics</div>
<div class="">MemIntrinsic</div>
<div class="">* MemSetInst</div>
<div class=""> ** UAMemSetInst</div>
<div class="">* MemTransferInst</div>
<div class=""> ** MemCpyInst</div>
<div class=""> *** UAMemCpyInst</div>
<div class=""> ** MemMoveInst</div>
<div class=""> *** UAMemMoveInst</div>
<div class=""><br class="">
</div>
<div class=""> There’s not a tonne of difference between this option and option (1), above. All of the existing visitors would recognize unordered-atomic and regular memory intrinsics, so there wouldn’t need to be any code clones to support the new intrinsics. </div>
<div class=""> However, passes that care about the atomicity of the intrinsic would have to add isa<> checks to ensure that they’re not acting on the unordered-atomic memory intrinsic when they don’t want to be. It would also be trickier than option (1) to
check, at the level of MemIntrinsic/MemTransferInst, whether the intrinsic we have is unordered-atomic; we’d have to explicitly check all of the isa<>’s rather than querying the isUnorderedAtomic() property. We could add the isUnorderedAtomic() query method
to this option, but then it’s not much different from option (1).</div>
<div class=""><br class="">
</div>
<div class=""> The way forward for this option would be very similar to that for option 1.</div>
<div class=""><br class="">
</div>
<div class="">d) Direct parent classes of the regular intrinsics</div>
<div class="">MemIntrinsic</div>
<div class="">* UAMemSetInst</div>
<div class=""> ** MemSetInst</div>
<div class="">* MemTransferInst</div>
<div class=""> ** UAMemCpyInst</div>
<div class=""> *** MemCpyInst</div>
<div class=""> ** UAMemMoveInst</div>
<div class=""> *** MemMoveInst</div>
<div class=""><br class="">
</div>
<div class=""> This is an idea that came up in our discussions. A benefit is that it leaves the existing regular memory intrinsics as leaf classes in the hierarchy; so, if we currently check for, say, isa<MemCpyInst> then we don’t have to change that code
because it can’t be unordered-atomic and have that test be true. The benefit is that it would make it harder for a pass to accidentally convert an unordered-atomic intrinsic into a non-atomic intrinsic. It does complicate code that checks whether an intrinsic
is a memset by checking for not isa<MemTransferInst>, and other code like that.</div>
<div class=""><br class="">
</div>
<div class="">e) Multiple inheritance</div>
<div class=""><br class="">
</div>
<div class=""> This is a variant on options 2b to 2d. To make it possible to easily use isa<> to query for whether or not a memory intrinsic is unordered-atomic or not we could add an interface-like class that all unordered-atomic memory intrinsic classes would
multiply inherit from. I’m not sure if there is precedence for this sort of thing in the instruction class hierarchy, though; I haven’t reviewed the entire hierarchy, but all of the parts that I have looked at appear to be single inheritance.</div>
<div class=""><br class="">
</div>
<div class="">===</div>
<div class=""><br class="">
</div>
<div class=""><b class="">Note about the align parameter attribute.</b></div>
<div class=""><br class="">
</div>
<div class=""> When creating the unordered-atomic memory intrinsics we decided to use the align attribute on pointer parameters, rather than supplying a single alignment parameter. This adheres to the way that LLVM wants to move going forward, but is different
from the way that the memcpy, memmove, and memset intrinsics are currently implemented. This could, potentially, be a complication when integrating the unordered-atomic memory intrinsics into the class hierarchy. Ideally, it would be good to resurrect the
2.5 yr old work to remove the alignment parameter from memcpy, memmove, and memset: </div>
<div class="">commit 8b170f7f290843dc3849eaa75b6f74a87a7a2de6<br class="">
Author: Pete Cooper <<a href="mailto:peter_cooper@apple.com" class="">peter_cooper@apple.com</a>><br class="">
Date: Wed Nov 18 22:17:24 2015 +0000</div>
<div class=""><br class="">
</div>
<div class="">That was reverted due to bot failures, but the history on exactly what those failures are appears, to me, to be lost:</div>
<div class=""><br class="">
</div>
<div class="">commit 6d024c616a2a4959f8dfe5c64d27f89b394cf042<br class="">
Author: Pete Cooper <<a href="mailto:peter_cooper@apple.com" class="">peter_cooper@apple.com</a>><br class="">
Date: Thu Nov 19 05:56:52 2015 +0000<br class="">
<br class="">
</div>
<div class=""> Baring that, there is still a way forward for integrating the unordered-atomic memory intrinsics into the class hierarchy. The getAlignment() method of MemIntrinsic would have to return the minimum of the pointer-arg alignment attributes for
unordered-atomic intrinsics, and the setAlignment() method would have to set both parameter attributes to the given value.</div>
<div class=""><br class="">
</div>
<div class="">===</div>
<div class=""><br class="">
</div>
<div class=""> Thoughts? Opinions?</div>
<div class=""><br class="">
</div>
<div class="">Thanks,</div>
<div class=""> Daniel</div>
</div>
</div>
<br class="">
<div class="">
<div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">
<div class="">---</div>
<div class="">Daniel Neilson, Ph.D.</div>
<div class="">Azul Systems</div>
</div>
</div>
</body>
</html>