From ff03048c1350fcc4fda1ef6d6c57252f3a950854 Mon Sep 17 00:00:00 2001 From: Eli Friedman Date: Thu, 28 Jul 2011 21:48:00 +0000 Subject: LangRef and basic memory-representation/reading/writing for 'cmpxchg' and 'atomicrmw' instructions, which allow representing all the current atomic rmw intrinsics. The allowed operands for these instructions are heavily restricted at the moment; we can probably loosen it a bit, but supporting general first-class types (where it makes sense) might get a bit complicated, given how SelectionDAG works. As an initial cut, these operations do not support specifying an alignment, but it would be possible to add if we think it's useful. Specifying an alignment lower than the natural alignment would be essentially impossible to support on anything other than x86, but specifying a greater alignment would be possible. I can't think of any useful optimizations which would use that information, but maybe someone else has ideas. Optimizer/codegen support coming soon. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136404 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/LangRef.html | 249 ++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 241 insertions(+), 8 deletions(-) (limited to 'docs/LangRef.html') diff --git a/docs/LangRef.html b/docs/LangRef.html index 40affb7..0c07f12 100644 --- a/docs/LangRef.html +++ b/docs/LangRef.html @@ -54,6 +54,7 @@
  • Pointer Aliasing Rules
  • Volatile Memory Accesses
  • Memory Model for Concurrent Operations
    • +
  • Atomic Memory Ordering Constraints
  • Type System @@ -168,10 +169,12 @@
  • Memory Access and Addressing Operations
      -
    1. 'alloca' Instruction
      2. -
    2. 'load' Instruction
      3. -
    3. 'store' Instruction
      4. -
    4. 'fence' Instruction
      5. +
    5. 'alloca' Instruction
      6. +
    6. 'load' Instruction
      7. +
    7. 'store' Instruction
      8. +
    8. 'fence' Instruction
      9. +
    9. 'cmpxchg' Instruction
      10. +
    10. 'atomicrmw' Instruction
    11. 'getelementptr' Instruction
    • @@ -1500,8 +1503,9 @@ that

  • When a synchronizes-with b, includes an edge from a to b. Synchronizes-with pairs are introduced by platform-specific techniques, like pthread locks, thread - creation, thread joining, etc., and by the atomic operations described - in the Atomic intrinsics section.
    • + creation, thread joining, etc., and by atomic instructions. + (See also Atomic Memory Ordering Constraints). +

    Note that program order does not introduce happens-before edges @@ -1536,8 +1540,9 @@ any write to the same byte, except:

    write.
  • Otherwise, if R is atomic, and all the writes Rbyte may see are atomic, it chooses one of the - values written. See the Atomic intrinsics - section for additional guarantees on how the choice is made. + values written. See the Atomic Memory Ordering + Constraints section for additional constraints on how the choice + is made.
  • Otherwise Rbyte returns undef.
    • @@ -1569,6 +1574,82 @@ as if it writes to the relevant surrounding bytes. + +
    + Atomic Memory Ordering Constraints +
    + +
    + +

    Atomic instructions (cmpxchg, +atomicrmw, and +fence) take an ordering parameter +that determines which other atomic instructions on the same address they +synchronize with. These semantics are borrowed from Java and C++0x, +but are somewhat more colloquial. If these descriptions aren't precise enough, +check those specs. fence instructions +treat these orderings somewhat differently since they don't take an address. +See that instruction's documentation for details.

    + + + +
    + +
    unordered
    +
    The set of values that can be read is governed by the happens-before +partial order. A value cannot be read unless some operation wrote it. +This is intended to provide a guarantee strong enough to model Java's +non-volatile shared variables. This ordering cannot be specified for +read-modify-write operations; it is not strong enough to make them atomic +in any interesting way.
    +
    monotonic
    +
    In addition to the guarantees of unordered, there is a single +total order for modifications by monotonic operations on each +address. All modification orders must be compatible with the happens-before +order. There is no guarantee that the modification orders can be combined to +a global total order for the whole program (and this often will not be +possible). The read in an atomic read-modify-write operation +(cmpxchg and +atomicrmw) +reads the value in the modification order immediately before the value it +writes. If one atomic read happens before another atomic read of the same +address, the later read must see the same value or a later value in the +address's modification order. This disallows reordering of +monotonic (or stronger) operations on the same address. If an +address is written monotonically by one thread, and other threads +monotonically read that address repeatedly, the other threads must +eventually see the write. This is intended to model C++'s relaxed atomic +variables.
    +
    acquire
    +
    In addition to the guarantees of monotonic, if this operation +reads a value written by a release atomic operation, it +synchronizes-with that operation.
    +
    release
    +
    In addition to the guarantees of monotonic, +a synchronizes-with edge may be formed by an acquire +operation.
    +
    acq_rel (acquire+release)
    Acts as both an +acquire and release operation on its address.
    +
    seq_cst (sequentially consistent)
    +
    In addition to the guarantees of acq_rel +(acquire for an operation which only reads, release +for an operation which only writes), there is a global total order on all +sequentially-consistent operations on all addresses, which is consistent with +the happens-before partial order and with the modification orders of +all the affected addresses. Each sequentially-consistent read sees the last +preceding write to the same address in this global order. This is intended +to model C++'s sequentially-consistent atomic variables and Java's volatile +shared variables.
    +
    + +

    If an atomic operation is marked singlethread, +it only synchronizes with or participates in modification and seq_cst +total orderings with other operations running in the same thread (for example, +in signal handlers).

    + +
    + @@ -4642,6 +4723,158 @@ thread. (This is useful for interacting with signal handlers.)

    +
    'cmpxchg' +Instruction
    + +
    + +
    Syntax:
    +
    +  [volatile] cmpxchg <ty>* <pointer>, <ty> <cmp>, <ty> <new> [singlethread] <ordering>                   ; yields {ty}
+
    + +
    Overview:
    +

    The 'cmpxchg' instruction is used to atomically modify memory. +It loads a value in memory and compares it to a given value. If they are +equal, it stores a new value into the memory.

    + +
    Arguments:
    +

    There are three arguments to the 'cmpxchg' instruction: an +address to operate on, a value to compare to the value currently be at that +address, and a new value to place at that address if the compared values are +equal. The type of '<cmp>' must be an integer type whose +bit width is a power of two greater than or equal to eight and less than +or equal to a target-specific size limit. '<cmp>' and +'<new>' must have the same type, and the type of +'<pointer>' must be a pointer to that type. If the +cmpxchg is marked as volatile, then the +optimizer is not allowed to modify the number or order of execution +of this cmpxchg with other volatile +operations.

    + + + +

    The ordering argument specifies how this +cmpxchg synchronizes with other atomic operations.

    + +

    The optional "singlethread" argument declares that the +cmpxchg is only atomic with respect to code (usually signal +handlers) running in the same thread as the cmpxchg. Otherwise the +cmpxchg is atomic with respect to all other code in the system.

    + +

    The pointer passed into cmpxchg must have alignment greater than or equal to +the size in memory of the operand. + +

    Semantics:
    +

    The contents of memory at the location specified by the +'<pointer>' operand is read and compared to +'<cmp>'; if the read value is the equal, +'<new>' is written. The original value at the location +is returned. + +

    A successful cmpxchg is a read-modify-write instruction for the +purpose of identifying release sequences. A +failed cmpxchg is equivalent to an atomic load with an ordering +parameter determined by dropping any release part of the +cmpxchg's ordering.

    + + + +
    Example:
    +
    +entry:
+  %orig = atomic load i32* %ptr unordered                       ; yields {i32}
+  br label %loop
+
+loop:
+  %cmp = phi i32 [ %orig, %entry ], [%old, %loop]
+  %squared = mul i32 %cmp, %cmp
+  %old = cmpxchg i32* %ptr, i32 %cmp, i32 %squared                       ; yields {i32}
+  %success = icmp eq i32 %cmp, %old
+  br i1 %success, label %done, label %loop
+
+done:
+  ...
+
    + +
    + + +
    'atomicrmw' +Instruction
    + +
    + +
    Syntax:
    +
    +  [volatile] atomicrmw <operation> <ty>* <pointer>, <ty> <value> [singlethread] <ordering>                   ; yields {ty}
+
    + +
    Overview:
    +

    The 'atomicrmw' instruction is used to atomically modify memory.

    + +
    Arguments:
    +

    There are three arguments to the 'atomicrmw' instruction: an +operation to apply, an address whose value to modify, an argument to the +operation. The operation must be one of the following keywords:

    + + +

    The type of '<value>' must be an integer type whose +bit width is a power of two greater than or equal to eight and less than +or equal to a target-specific size limit. The type of the +'<pointer>' operand must be a pointer to that type. +If the atomicrmw is marked as volatile, then the +optimizer is not allowed to modify the number or order of execution of this +atomicrmw with other volatile + operations.

    + + + +
    Semantics:
    +

    The contents of memory at the location specified by the +'<pointer>' operand are atomically read, modified, and written +back. The original value at the location is returned. The modification is +specified by the operation argument:

    + + + +
    Example:
    +
    +  %old = atomicrmw add i32* %ptr, i32 1 acquire                        ; yields {i32}
+
    + +
    + +

    'getelementptr' Instruction

    -- cgit v1.1