659 lines · plain
1==============================================2LLVM Atomic Instructions and Concurrency Guide3==============================================4 5.. contents::6 :local:7 8Introduction9============10 11LLVM supports instructions which are well-defined in the presence of threads and12asynchronous signals.13 14The atomic instructions are designed specifically to provide readable IR and15optimized code generation for the following:16 17* The C++ ``<atomic>`` header and C ``<stdatomic.h>`` headers. These18 were originally added in C++11 and C11. The memory model has been19 subsequently adjusted to correct errors in the initial20 specification, so LLVM currently intends to implement the version21 specified by C++20. (See the `C++20 draft standard22 <https://isocpp.org/files/papers/N4860.pdf>`_ or the unofficial23 `latest C++ draft <https://eel.is/c++draft/>`_. A `C2x draft24 <https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3047.pdf>`_ is25 also available, though the text has not yet been updated with the26 errata corrected by C++20.)27 28* Proper semantics for Java-style memory, for both ``volatile`` and regular29 shared variables. (`Java Specification30 <http://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html>`_)31 32* gcc-compatible ``__sync_*`` builtins. (`Description33 <https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html>`_)34 35* Other scenarios with atomic semantics, including ``static`` variables with36 non-trivial constructors in C++.37 38Atomic and volatile in the IR are orthogonal; "volatile" is the C/C++ volatile,39which ensures that every volatile load and store happens and is performed in the40stated order. A couple examples: if a SequentiallyConsistent store is41immediately followed by another SequentiallyConsistent store to the same42address, the first store can be erased. This transformation is not allowed for a43pair of volatile stores. On the other hand, a non-volatile non-atomic load can44be moved across a volatile load freely, but not an Acquire load.45 46This document is intended to guide anyone writing a frontend47for LLVM or working on optimization passes for LLVM on how to deal48with instructions with special semantics in the presence of concurrency. This49is not intended to be a precise guide to the semantics; the details can get50extremely complicated and unreadable, and are not usually necessary.51 52.. _Optimization outside atomic:53 54Optimization outside atomic55===========================56 57The basic ``'load'`` and ``'store'`` allow a variety of optimizations, but can58lead to undefined results in a concurrent environment; see `NotAtomic`_. This59section specifically goes into the one optimizer restriction which applies in60concurrent environments, which gets a bit more of an extended description61because any optimization dealing with stores needs to be aware of it.62 63From the optimizer's point of view, the rule is that if there are not any64instructions with atomic ordering involved, concurrency does not matter, with65one exception: if a variable might be visible to another thread or signal66handler, a store cannot be inserted along a path where it might not execute67otherwise. Take the following example:68 69.. code-block:: c70 71 /* C code, for readability; run through clang -O2 -S -emit-llvm to get72 equivalent IR */73 int x;74 void f(int* a) {75 for (int i = 0; i < 100; i++) {76 if (a[i])77 x += 1;78 }79 }80 81The following is equivalent in non-concurrent situations:82 83.. code-block:: c84 85 int x;86 void f(int* a) {87 int xtemp = x;88 for (int i = 0; i < 100; i++) {89 if (a[i])90 xtemp += 1;91 }92 x = xtemp;93 }94 95However, LLVM is not allowed to transform the former to the latter: it could96indirectly introduce undefined behavior if another thread can access ``x`` at97the same time. That thread would read ``undef`` instead of the value it was98expecting, which can lead to undefined behavior down the line. (This example is99particularly of interest because before the concurrency model was implemented,100LLVM would perform this transformation.)101 102Note that speculative loads are allowed; a load which is part of a race returns103``undef``, but does not have undefined behavior.104 105Atomic instructions106===================107 108For cases where simple loads and stores are not sufficient, LLVM provides109various atomic instructions. The exact guarantees provided depend on the110ordering; see `Atomic orderings`_.111 112``load atomic`` and ``store atomic`` provide the same basic functionality as113non-atomic loads and stores, but provide additional guarantees in situations114where threads and signals are involved.115 116``cmpxchg`` and ``atomicrmw`` are essentially like an atomic load followed by an117atomic store (where the store is conditional for ``cmpxchg``), but no other118memory operation can happen on any thread between the load and store.119 120A ``fence`` provides Acquire and/or Release ordering which is not part121of another operation; it is normally used along with Monotonic memory122operations. A Monotonic load followed by an Acquire fence is roughly123equivalent to an Acquire load, and a Monotonic store following a124Release fence is roughly equivalent to a Release125store. SequentiallyConsistent fences behave as both an Acquire and a126Release fence, and additionally provide a total ordering with some127complicated guarantees, see the C++ standard for details.128 129Frontends generating atomic instructions generally need to be aware of the130target to some degree; atomic instructions are guaranteed to be lock-free, and131therefore an instruction which is wider than the target natively supports can be132impossible to generate.133 134.. _Atomic orderings:135 136Atomic orderings137================138 139In order to achieve a balance between performance and necessary guarantees,140there are six levels of atomicity. They are listed in order of strength; each141level includes all the guarantees of the previous level except for142Acquire/Release. (See also `LangRef Ordering <LangRef.html#ordering>`_.)143 144.. _NotAtomic:145 146NotAtomic147---------148 149NotAtomic is the obvious, a load or store which is not atomic. (This isn't150really a level of atomicity, but is listed here for comparison.) This is151essentially a regular load or store. If there is a race on a given memory152location, loads from that location return ``undef``.153 154Relevant standard155 This is intended to match shared variables in C/C++, and to be used in any156 other context where memory access is necessary, and a race is impossible. (The157 precise definition is in `LangRef Memory Model <LangRef.html#memmodel>`_.)158 159Notes for frontends160 The rule is essentially that all memory accessed with basic loads and stores161 by multiple threads should be protected by a lock or other synchronization;162 otherwise, you are likely to run into undefined behavior. If your frontend is163 for a "safe" language like Java, use Unordered to load and store any shared164 variable. Note that NotAtomic volatile loads and stores are not properly165 atomic; do not try to use them as a substitute. (Per the C/C++ standards,166 volatile does provide some limited guarantees around asynchronous signals, but167 atomics are generally a better solution.)168 169Notes for optimizers170 Introducing loads to shared variables along a codepath where they would not171 otherwise exist is allowed; introducing stores to shared variables is not. See172 `Optimization outside atomic`_.173 174Notes for code generation175 The one interesting restriction here is that it is not allowed to write to176 bytes outside of the bytes relevant to a store. This is mostly relevant to177 unaligned stores: it is not allowed in general to convert an unaligned store178 into two aligned stores of the same width as the unaligned store. Backends are179 also expected to generate an i8 store as an i8 store, and not an instruction180 which writes to surrounding bytes. (If you are writing a backend for an181 architecture which cannot satisfy these restrictions and cares about182 concurrency, please send an email to llvm-dev.)183 184Unordered185---------186 187Unordered is the lowest level of atomicity. It essentially guarantees that races188produce somewhat sane results instead of having undefined behavior. It also189guarantees the operation to be lock-free, so it does not depend on the data190being part of a special atomic structure or depend on a separate per-process191global lock. Note that code generation will fail for unsupported atomic192operations; if you need such an operation, use explicit locking.193 194Relevant standard195 This is intended to match the Java memory model for shared variables.196 197Notes for frontends198 This cannot be used for synchronization, but is useful for Java and other199 "safe" languages which need to guarantee that the generated code never200 exhibits undefined behavior. Note that this guarantee is cheap on common201 platforms for loads of a native width, but can be expensive or unavailable for202 wider loads, like a 64-bit store on ARM. (A frontend for Java or other "safe"203 languages would normally split a 64-bit store on ARM into two 32-bit unordered204 stores.)205 206Notes for optimizers207 In terms of the optimizer, this prohibits any transformation that transforms a208 single load into multiple loads, transforms a store into multiple stores,209 narrows a store, or stores a value which would not be stored otherwise. Some210 examples of unsafe optimizations are narrowing an assignment into a bitfield,211 rematerializing a load, and turning loads and stores into a memcpy212 call. Reordering unordered operations is safe, though, and optimizers should213 take advantage of that because unordered operations are common in languages214 that need them.215 216Notes for code generation217 These operations are required to be atomic in the sense that if you use218 unordered loads and unordered stores, a load cannot see a value which was219 never stored. A normal load or store instruction is usually sufficient, but220 note that an unordered load or store cannot be split into multiple221 instructions (or an instruction which does multiple memory operations, like222 ``LDRD`` on ARM without LPAE, or not naturally-aligned ``LDRD`` on LPAE ARM).223 224Monotonic225---------226 227Monotonic is the weakest level of atomicity that can be used in synchronization228primitives, although it does not provide any general synchronization. It229essentially guarantees that if you take all the operations affecting a specific230address, a consistent ordering exists.231 232Relevant standard233 This corresponds to the C++/C ``memory_order_relaxed``; see those234 standards for the exact definition.235 236Notes for frontends237 If you are writing a frontend which uses this directly, use with caution. The238 guarantees in terms of synchronization are very weak, so make sure these are239 only used in a pattern which you know is correct. Generally, these would240 either be used for atomic operations which do not protect other memory (like241 an atomic counter), or along with a ``fence``.242 243Notes for optimizers244 In terms of the optimizer, this can be treated as a read+write on the relevant245 memory location (and alias analysis will take advantage of that). In addition,246 it is legal to reorder non-atomic and Unordered loads around Monotonic247 loads. CSE/DSE and a few other optimizations are allowed, but Monotonic248 operations are unlikely to be used in ways which would make those249 optimizations useful.250 251Notes for code generation252 Code generation is essentially the same as that for unordered for loads and253 stores. No fences are required. ``cmpxchg`` and ``atomicrmw`` are required254 to appear as a single operation.255 256Acquire257-------258 259Acquire provides a barrier of the sort necessary to acquire a lock to access260other memory with normal loads and stores.261 262Relevant standard263 This corresponds to the C++/C ``memory_order_acquire``. It should also be264 used for C++/C ``memory_order_consume``.265 266Notes for frontends267 If you are writing a frontend which uses this directly, use with caution.268 Acquire only provides a semantic guarantee when paired with a Release269 operation.270 271Notes for optimizers272 Optimizers not aware of atomics can treat this like a nothrow call. It is273 also possible to move stores from before an Acquire load or read-modify-write274 operation to after it, and move non-Acquire loads from before an Acquire275 operation to after it.276 277Notes for code generation278 Architectures with weak memory ordering (essentially everything relevant today279 except x86 and SPARC) require some sort of fence to maintain the Acquire280 semantics. The precise fences required varies widely by architecture, but for281 a simple implementation, most architectures provide a barrier which is strong282 enough for everything (``dmb`` on ARM, ``sync`` on PowerPC, etc.). Putting283 such a fence after the equivalent Monotonic operation is sufficient to284 maintain Acquire semantics for a memory operation.285 286Release287-------288 289Release is similar to Acquire, but with a barrier of the sort necessary to290release a lock.291 292Relevant standard293 This corresponds to the C++/C ``memory_order_release``.294 295Notes for frontends296 If you are writing a frontend which uses this directly, use with caution.297 Release only provides a semantic guarantee when paired with an Acquire298 operation.299 300Notes for optimizers301 Optimizers not aware of atomics can treat this like a nothrow call. It is302 also possible to move loads from after a Release store or read-modify-write303 operation to before it, and move non-Release stores from after a Release304 operation to before it.305 306Notes for code generation307 See the section on Acquire; a fence before the relevant operation is usually308 sufficient for Release. Note that a store-store fence is not sufficient to309 implement Release semantics; store-store fences are generally not exposed to310 IR because they are extremely difficult to use correctly.311 312AcquireRelease313--------------314 315AcquireRelease (``acq_rel`` in IR) provides both an Acquire and a Release316barrier (for fences and operations which both read and write memory).317 318Relevant standard319 This corresponds to the C++/C ``memory_order_acq_rel``.320 321Notes for frontends322 If you are writing a frontend which uses this directly, use with caution.323 Acquire only provides a semantic guarantee when paired with a Release324 operation, and vice versa.325 326Notes for optimizers327 In general, optimizers should treat this like a nothrow call; the possible328 optimizations are usually not interesting.329 330Notes for code generation331 This operation has Acquire and Release semantics; see the sections on Acquire332 and Release.333 334SequentiallyConsistent335----------------------336 337SequentiallyConsistent (``seq_cst`` in IR) provides Acquire semantics for loads338and Release semantics for stores. Additionally, it guarantees that a total339ordering exists between all SequentiallyConsistent operations.340 341Relevant standard342 This corresponds to the C++/C ``memory_order_seq_cst``, Java volatile, and343 the gcc-compatible ``__sync_*`` builtins which do not specify otherwise.344 345Notes for frontends346 If a frontend is exposing atomic operations, these are much easier to reason347 about for the programmer than other kinds of operations, and using them is348 generally a practical performance tradeoff.349 350Notes for optimizers351 Optimizers not aware of atomics can treat this like a nothrow call. For352 SequentiallyConsistent loads and stores, the same reorderings are allowed as353 for Acquire loads and Release stores, except that SequentiallyConsistent354 operations may not be reordered.355 356Notes for code generation357 SequentiallyConsistent loads minimally require the same barriers as Acquire358 operations and SequentiallyConsistent stores require Release359 barriers. Additionally, the code generator must enforce ordering between360 SequentiallyConsistent stores followed by SequentiallyConsistent loads. This361 is usually done by emitting either a full fence before the loads or a full362 fence after the stores; which is preferred varies by architecture.363 364Atomics and IR optimization365===========================366 367Predicates for optimizer writers to query:368 369* ``isSimple()``: A load or store which is not volatile or atomic. This is370 what, for example, memcpyopt would check for operations it might transform.371 372* ``isUnordered()``: A load or store which is not volatile and at most373 Unordered. This would be checked, for example, by LICM before hoisting an374 operation.375 376* ``mayReadFromMemory()``/``mayWriteToMemory()``: Existing predicate, but note377 that they return true for any operation which is volatile or at least378 Monotonic.379 380* ``isStrongerThan`` / ``isAtLeastOrStrongerThan``: These are predicates on381 orderings. They can be useful for passes that are aware of atomics, for382 example to do DSE across a single atomic access, but not across a383 release-acquire pair (see MemoryDependencyAnalysis for an example of this)384 385* Alias analysis: Note that AA will return ModRef for anything Acquire or386 Release, and for the address accessed by any Monotonic operation.387 388To support optimizing around atomic operations, make sure you are using the389right predicates; everything should work if that is done. If your pass should390optimize some atomic operations (Unordered operations in particular), make sure391it doesn't replace an atomic load or store with a non-atomic operation.392 393Some examples of how optimizations interact with various kinds of atomic394operations:395 396* ``memcpyopt``: An atomic operation cannot be optimized into part of a397 memcpy/memset, including unordered loads/stores. It can pull operations398 across some atomic operations.399 400* LICM: Unordered loads/stores can be moved out of a loop. It just treats401 monotonic operations like a read+write to a memory location, and anything402 stricter than that like a nothrow call.403 404* DSE: Unordered stores can be DSE'ed like normal stores. Monotonic stores can405 be DSE'ed in some cases, but it's tricky to reason about, and not especially406 important. It is possible in some case for DSE to operate across a stronger407 atomic operation, but it is fairly tricky. DSE delegates this reasoning to408 MemoryDependencyAnalysis (which is also used by other passes like GVN).409 410* Folding a load: Any atomic load from a constant global can be constant-folded,411 because it cannot be observed. Similar reasoning allows SROA with412 atomic loads and stores.413 414Atomics and Codegen415===================416 417Atomic operations are represented in the SelectionDAG with ``ATOMIC_*`` opcodes.418On architectures which use barrier instructions for all atomic ordering (like419ARM), appropriate fences can be emitted by the AtomicExpand Codegen pass if420``shouldInsertFencesForAtomic()`` returns true.421 422The MachineMemOperand for all atomic operations is currently marked as volatile;423this is not correct in the IR sense of volatile, but CodeGen handles anything424marked volatile very conservatively. This should get fixed at some point.425 426One very important property of the atomic operations is that if your backend427supports any inline lock-free atomic operations of a given size, you should428support *ALL* operations of that size in a lock-free manner.429 430When the target implements atomic ``cmpxchg`` or LL/SC instructions (as most do)431this is trivial: all the other operations can be implemented on top of those432primitives. However, on many older CPUs (e.g. ARMv5, Sparc V8, Intel 80386) there433are atomic load and store instructions, but no ``cmpxchg`` or LL/SC. As it is434invalid to implement ``atomic load`` using the native instruction, but435``cmpxchg`` using a library call to a function that uses a mutex, ``atomic436load`` must *also* expand to a library call on such architectures, so that it437can remain atomic with regards to a simultaneous ``cmpxchg``, by using the same438mutex.439 440AtomicExpandPass can help with that: it will expand all atomic operations to the441proper ``__atomic_*`` libcalls for any size above the maximum set by442``setMaxAtomicSizeInBitsSupported`` (which defaults to 0).443 444On x86, all atomic loads generate a ``MOV``. SequentiallyConsistent stores445generate an ``XCHG``, other stores generate a ``MOV``. SequentiallyConsistent446fences generate an ``MFENCE``, other fences do not cause any code to be447generated. ``cmpxchg`` uses the ``LOCK CMPXCHG`` instruction. ``atomicrmw xchg``448uses ``XCHG``, ``atomicrmw add`` and ``atomicrmw sub`` use ``XADD``, and all449other ``atomicrmw`` operations generate a loop with ``LOCK CMPXCHG``. Depending450on the users of the result, some ``atomicrmw`` operations can be translated into451operations like ``LOCK AND``, but that does not work in general.452 453On ARM (before v8), MIPS, and many other RISC architectures, Acquire, Release,454and SequentiallyConsistent semantics require barrier instructions for every such455operation. Loads and stores generate normal instructions. ``cmpxchg`` and456``atomicrmw`` can be represented using a loop with LL/SC-style instructions457which take some sort of exclusive lock on a cache line (``LDREX`` and ``STREX``458on ARM, etc.).459 460It is often easiest for backends to use AtomicExpandPass to lower some of the461atomic constructs. Here are some lowerings it can do:462 463* cmpxchg -> loop with load-linked/store-conditional464 by overriding ``shouldExpandAtomicCmpXchgInIR()``, ``emitLoadLinked()``,465 ``emitStoreConditional()``466* large loads/stores -> ll-sc/cmpxchg467 by overriding ``shouldExpandAtomicStoreInIR()``/``shouldExpandAtomicLoadInIR()``468* strong atomic accesses -> monotonic accesses + fences by overriding469 ``shouldInsertFencesForAtomic()``, ``emitLeadingFence()``, and470 ``emitTrailingFence()``471* atomic rmw -> loop with cmpxchg or load-linked/store-conditional472 by overriding ``expandAtomicRMWInIR()``473* expansion to __atomic_* libcalls for unsupported sizes.474* part-word atomicrmw/cmpxchg -> target-specific intrinsic by overriding475 ``shouldExpandAtomicRMWInIR``, ``emitMaskedAtomicRMWIntrinsic``,476 ``shouldExpandAtomicCmpXchgInIR``, and ``emitMaskedAtomicCmpXchgIntrinsic``.477 478For an example of these, look at the ARM (first five lowerings) or RISC-V (last479lowering) backend.480 481AtomicExpandPass supports two strategies for lowering atomicrmw/cmpxchg to482load-linked/store-conditional (LL/SC) loops. The first expands the LL/SC loop483in IR, calling target lowering hooks to emit intrinsics for the LL and SC484operations. However, many architectures have strict requirements for LL/SC485loops to ensure forward progress, such as restrictions on the number and type486of instructions in the loop. It isn't possible to enforce these restrictions487when the loop is expanded in LLVM IR, and so affected targets may prefer to488expand to LL/SC loops at a very late stage (i.e. after register allocation).489AtomicExpandPass can help support lowering of part-word atomicrmw or cmpxchg490using this strategy by producing IR for any shifting and masking that can be491performed outside of the LL/SC loop.492 493Libcalls: __atomic_*494====================495 496There are two kinds of atomic library calls that are generated by LLVM. Please497note that both sets of library functions somewhat confusingly share the names of498builtin functions defined by clang. Despite this, the library functions are499not directly related to the builtins: it is *not* the case that ``__atomic_*``500builtins lower to ``__atomic_*`` library calls and ``__sync_*`` builtins lower501to ``__sync_*`` library calls.502 503The first set of library functions are named ``__atomic_*``. This set has been504"standardized" by GCC, and is described below. (See also `GCC's documentation505<https://gcc.gnu.org/wiki/Atomic/GCCMM/LIbrary>`_)506 507LLVM's AtomicExpandPass will translate atomic operations on data sizes above508``MaxAtomicSizeInBitsSupported`` into calls to these functions.509 510There are four generic functions, which can be called with data of any size or511alignment::512 513 void __atomic_load(size_t size, void *ptr, void *ret, int ordering)514 void __atomic_store(size_t size, void *ptr, void *val, int ordering)515 void __atomic_exchange(size_t size, void *ptr, void *val, void *ret, int ordering)516 bool __atomic_compare_exchange(size_t size, void *ptr, void *expected, void *desired, int success_order, int failure_order)517 518There are also size-specialized versions of the above functions, which can only519be used with *naturally-aligned* pointers of the appropriate size. In the520signatures below, "N" is one of 1, 2, 4, 8, and 16, and "iN" is the appropriate521integer type of that size; if no such integer type exists, the specialization522cannot be used::523 524 iN __atomic_load_N(iN *ptr, iN val, int ordering)525 void __atomic_store_N(iN *ptr, iN val, int ordering)526 iN __atomic_exchange_N(iN *ptr, iN val, int ordering)527 bool __atomic_compare_exchange_N(iN *ptr, iN *expected, iN desired, int success_order, int failure_order)528 529Finally there are some read-modify-write functions, which are only available in530the size-specific variants (any other sizes use a ``__atomic_compare_exchange``531loop)::532 533 iN __atomic_fetch_add_N(iN *ptr, iN val, int ordering)534 iN __atomic_fetch_sub_N(iN *ptr, iN val, int ordering)535 iN __atomic_fetch_and_N(iN *ptr, iN val, int ordering)536 iN __atomic_fetch_or_N(iN *ptr, iN val, int ordering)537 iN __atomic_fetch_xor_N(iN *ptr, iN val, int ordering)538 iN __atomic_fetch_nand_N(iN *ptr, iN val, int ordering)539 540This set of library functions have some interesting implementation requirements541to take note of:542 543- They support all sizes and alignments -- including those which cannot be544 implemented natively on any existing hardware. Therefore, they will certainly545 use mutexes for some sizes/alignments.546 547- As a consequence, they cannot be shipped in a statically linked548 compiler-support library, as they have state which must be shared amongst all549 DSOs loaded in the program. They must be provided in a shared library used by550 all objects.551 552- The set of atomic sizes supported lock-free must be a superset of the sizes553 any compiler can emit. That is: if a new compiler introduces support for554 inline-lock-free atomics of size N, the ``__atomic_*`` functions must also have a555 lock-free implementation for size N. This is a requirement so that code556 produced by an old compiler (which will have called the ``__atomic_*`` function)557 interoperates with code produced by the new compiler (which will use native558 the atomic instruction).559 560Note that it's possible to write an entirely target-independent implementation561of these library functions by using the compiler atomic builtins themselves to562implement the operations on naturally-aligned pointers of supported sizes, and a563generic mutex implementation otherwise.564 565Libcalls: __sync_*566==================567 568Some targets or OS/target combinations can support lock-free atomics, but for569various reasons, it is not practical to emit the instructions inline.570 571There are two typical examples of this.572 573Some CPUs support multiple instruction sets which can be switched back and forth574on function-call boundaries. For example, MIPS supports the MIPS16 ISA, which575has a smaller instruction encoding than the usual MIPS32 ISA. ARM, similarly,576has the Thumb ISA. In MIPS16 and earlier versions of Thumb, the atomic577instructions are not encodable. However, those instructions are available via a578function call to a function with the longer encoding.579 580Additionally, a few OS/target pairs provide kernel-supported lock-free581atomics. ARM/Linux is an example of this: the kernel `provides582<https://www.kernel.org/doc/Documentation/arm/kernel_user_helpers.txt>`_ a583function which on older CPUs contains a "magically-restartable" atomic sequence584(which looks atomic so long as there's only one CPU), and contains actual atomic585instructions on newer multicore models. This sort of functionality can typically586be provided on any architecture, if all CPUs which are missing atomic587compare-and-swap support are uniprocessor (no SMP). This is almost always the588case. The only common architecture without that property is SPARC -- SPARCV8 SMP589systems were common, yet it doesn't support any sort of compare-and-swap590operation.591 592Some targets (like RISC-V) support a ``+forced-atomics`` target feature, which593enables the use of lock-free atomics even if LLVM is not aware of any specific594OS support for them. In this case, the user is responsible for ensuring that595necessary ``__sync_*`` implementations are available. Code using596``+forced-atomics`` is ABI-incompatible with code not using the feature, if597atomic variables cross the ABI boundary.598 599In either of these cases, the Target in LLVM can claim support for atomics of an600appropriate size, and then implement some subset of the operations via libcalls601to a ``__sync_*`` function. Such functions *must* not use locks in their602implementation, because unlike the ``__atomic_*`` routines used by603AtomicExpandPass, these may be mixed-and-matched with native instructions by the604target lowering.605 606Further, these routines do not need to be shared, as they are stateless. So,607there is no issue with having multiple copies included in one binary. Thus,608typically these routines are implemented by the statically-linked compiler609runtime support library.610 611LLVM will emit a call to an appropriate ``__sync_*`` routine if the target612ISelLowering code has set the corresponding ``ATOMIC_CMPXCHG``, ``ATOMIC_SWAP``,613or ``ATOMIC_LOAD_*`` operation to "Expand", and if it has opted-into the614availability of those library functions via a call to ``initSyncLibcalls()``.615 616The full set of functions that may be called by LLVM is (for ``N`` being 1, 2,6174, 8, or 16)::618 619 iN __sync_val_compare_and_swap_N(iN *ptr, iN expected, iN desired)620 iN __sync_lock_test_and_set_N(iN *ptr, iN val)621 iN __sync_fetch_and_add_N(iN *ptr, iN val)622 iN __sync_fetch_and_sub_N(iN *ptr, iN val)623 iN __sync_fetch_and_and_N(iN *ptr, iN val)624 iN __sync_fetch_and_or_N(iN *ptr, iN val)625 iN __sync_fetch_and_xor_N(iN *ptr, iN val)626 iN __sync_fetch_and_nand_N(iN *ptr, iN val)627 iN __sync_fetch_and_max_N(iN *ptr, iN val)628 iN __sync_fetch_and_umax_N(iN *ptr, iN val)629 iN __sync_fetch_and_min_N(iN *ptr, iN val)630 iN __sync_fetch_and_umin_N(iN *ptr, iN val)631 632This list doesn't include any function for atomic load or store; all known633architectures support atomic loads and stores directly (possibly by emitting a634fence on either side of a normal load or store.)635 636There's also, somewhat separately, the possibility to lower ``ATOMIC_FENCE`` to637``__sync_synchronize()``. This may happen or not happen independent of all the638above, controlled purely by ``setOperationAction(ISD::ATOMIC_FENCE, ...)``.639 640On AArch64, a variant of the __sync_* routines is used which contain the memory641order as part of the function name. These routines may determine at runtime642whether the single-instruction atomic operations which were introduced as part643of AArch64 Large System Extensions "LSE" instruction set are available, or if644it needs to fall back to an LL/SC loop. The following helper functions are645implemented in both ``compiler-rt`` and ``libgcc`` libraries646(``N`` is one of 1, 2, 4, 8, and ``M`` is one of 1, 2, 4, 8 and 16, and647``ORDER`` is one of 'relax', 'acq', 'rel', 'acq_rel')::648 649 iM __aarch64_casM_ORDER(iM expected, iM desired, iM *ptr)650 iN __aarch64_swpN_ORDER(iN val, iN *ptr)651 iN __aarch64_ldaddN_ORDER(iN val, iN *ptr)652 iN __aarch64_ldclrN_ORDER(iN val, iN *ptr)653 iN __aarch64_ldeorN_ORDER(iN val, iN *ptr)654 iN __aarch64_ldsetN_ORDER(iN val, iN *ptr)655 656Please note, if LSE instruction set is specified for AArch64 target, then657out-of-line atomics calls are not generated and single-instruction atomic658operations are used in place.659