Adding __atomic_fetch_min/max intrinsics to clang

[delena]

Summary

Added atomic_fetch_min, max, umin, umax intrinsics to clang.
These intrinsics work exactly as all other atomic_fetch_* intrinsics and allow to create *atomicrmw* with ordering.
The similar set __sync_fetch_and_min* sets the sequentially-consistent ordering.

We use them for OpenCL 1.2, which supports atomic operations with "relaxed" ordering.

[jfb]

lib/Sema/SemaChecking.cpp

3098

Should __sync_fetch_and_min and others also set IsMinMax?

[delena]

lib/Sema/SemaChecking.cpp

3098

sync_fetch_and_min is not variadic and not overloaded. The types of arguments are defined with the builtin itself in the def file.
BUILTIN(sync_fetch_and_min, "iiD*i", "n"). So it is checked automatically.

The other __sync_fetch* functions are overloaded and checked in SemaBuiltinAtomicOverloaded()

[rjmccall]

Given that these are overloaded builtins, why are there separate builtins for min and umin?

If this is a Clang extension, it needs to be documented in our extensions documentation.

The documentation should describe the exact ordering semantics, to the extent we want to guarantee them. For example, does __atomic_fetch_max order this operation with later operations even if the new value is in fact less than the current value of the variable, or does it use some treatment more like the failure case of a compare-exchange?

The documentation should describe the set of allowed types. If the builtins work on pointer types, the documentation should describe the semantics of the pointer comparison; for example, is it undefined behavior if an ordinary pointer comparison would be? Also, your test case should actually check the well-formedness conditions more completely, e.g. verifying that the value type is convertible to the atomic type.

[Anastasia]

Is this some sort of a vendor extension then? OpenCL 1.2 atomic builtins don't have ordering parameter.

[delena]

In D46386#1087533, @Anastasia wrote:

Is this some sort of a vendor extension then? OpenCL 1.2 atomic builtins don't have ordering parameter.

OpenCL 1.2 atomic builtins have relaxed semantics. Always, it is not parameter, it is defined behavior. I want to translate them to atomicrmw instruction and use one of clang intrinsics for this.
I can't use _sync_fetch_*, due to the different semantics. The __atomic_* allow to specify semantics, but min/max is missing in this set.

[delena]

Removed the unsigned version of atomics. Enhanced semantics check.
Added more tests.
Added documentation.

[rjmccall]

docs/LanguageExtensions.rst

1998

Thank you for adding this documentation. Please do clarify what the memory ordering semantics actually are when the atomic object does not need to be updated, though, and verify that target code generation actually obeys that ordering. For example, if the memory ordering makes this a release operation, __atomic_fetch_min must always store the result back to the atomic object, even if the new value was actually greater than the stored value; I believe that would not be required with a relaxed operation.

[delena]

Given more clarification about memory model of atomic operations.

[rjmccall]

docs/LanguageExtensions.rst

1998

Okay, that's not what I was asking for. It's okay to assume that people understand the basic memory orderings; you don't need to copy/paste generic descriptions of them here. There is something special about min/max vs. the rest of these atomic update operations, however, which is that min and max don't always change the value of the variable. (Technically this is true of corner cases of many of the other operations — for example, you could atomically add 0 to a variable or multiply a variable by 1 — but the basic operation of min/max makes this corner case a lot more important.) I am just asking you to state definitively whether the atomic operation is still appropriately ordered if the object's value does not change.

If you don't understand what I'm getting at here, maybe you should just add the relaxed ordering for now.

[delena]

Added a line about *load-store* semantics of these two intrinsics.
Removed the common description of memory modeling.

[rjmccall]

Thanks, that works for me.

The actual semantic parts of the diff seem to have disappeared from the patch posted to Phabricator, for what it's worth.

[delena]

In D46386#1096833, @rjmccall wrote:

The actual semantic parts of the diff seem to have disappeared from the patch posted to Phabricator, for what it's worth.

It is not disappeared by itself, I removed it. I understood that you don't see any added value in the entire memory model description inside.
Thank you.

[algrant]

There is a (stalled) proposal to add atomic integer max/min to C++: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0493r0.pdf . The proposal has memory semantics similar to these builtins, i.e. unconditional RMW. There is no limitation to 32-bit types though, what's the motivation for that? Is it a limitation of a particular target?

docs/LanguageExtensions.rst

 ``__builtin_char_memchr(a, b, c)`` is identical to
 ``(char*)__builtin_memchr(a, b, c)`` except that its use is permitted within
 constant expressions in C++11 onwards (where a cast from ``void*`` to ``char*``
 is disallowed in general).
 
 Support for constant expression evaluation for the above builtins be detected
 with ``__has_feature(cxx_constexpr_string_builtins)``.
 
+Atomic Min/Max builtins with memory ordering
+--------------------------------------------
+
+There are two atomic builtins with min/max in-memory comparison and swap.
+The syntax and semantics are similar to GCC-compatible __atomic_* builtins.
+
+* ``__atomic_fetch_min`` 
+* ``__atomic_fetch_max`` 
+
+The builtins work with signed and unsigned integers and require to specify memory ordering.
+The return value is the original value that was stored in memory before comparison.
+
+Example:
+
+.. code-block:: c
+
+  unsigned int val = __atomic_fetch_min(unsigned int *pi, unsigned int ui, __ATOMIC_RELAXED);
+  
+The third argument is one of the memory ordering specifiers ``__ATOMIC_RELAXED``,
+``__ATOMIC_CONSUME``, ``__ATOMIC_ACQUIRE``, ``__ATOMIC_RELEASE``,
+``__ATOMIC_ACQ_REL``, or ``__ATOMIC_SEQ_CST`` following C++11 memory model semantics.
+
 .. _langext-__c11_atomic:
 
 __c11_atomic builtins
 ---------------------
 
 Clang provides a set of builtins which are intended to be used to implement
 C11's ``<stdatomic.h>`` header.  These builtins provide the semantics of the
 ``_explicit`` form of the corresponding C11 operation, and are named with a

include/clang/Basic/Builtins.def

 ATOMIC_BUILTIN(__opencl_atomic_fetch_add, "v.", "t")
 ATOMIC_BUILTIN(__opencl_atomic_fetch_sub, "v.", "t")
 ATOMIC_BUILTIN(__opencl_atomic_fetch_and, "v.", "t")
 ATOMIC_BUILTIN(__opencl_atomic_fetch_or, "v.", "t")
 ATOMIC_BUILTIN(__opencl_atomic_fetch_xor, "v.", "t")
 ATOMIC_BUILTIN(__opencl_atomic_fetch_min, "v.", "t")
 ATOMIC_BUILTIN(__opencl_atomic_fetch_max, "v.", "t")
 
+// GCC does not support these, they are a Clang extension.
+ATOMIC_BUILTIN(__atomic_fetch_min, "iiD*i.", "t")
+ATOMIC_BUILTIN(__atomic_fetch_max, "v.", "t")
+
 #undef ATOMIC_BUILTIN
 
 // Non-overloaded atomic builtins.
 BUILTIN(__sync_synchronize, "v", "n")
 // GCC does not support these, they are a Clang extension.
 BUILTIN(__sync_fetch_and_min, "iiD*i", "n")
 BUILTIN(__sync_fetch_and_max, "iiD*i", "n")
 BUILTIN(__sync_fetch_and_umin, "UiUiD*Ui", "n")

include/clang/Basic/DiagnosticSemaKinds.td

def err_atomic_op_needs_non_const_pointer : Error<
   "address argument to atomic operation must be a pointer to non-const "
   "type (%0 invalid)">;
 def err_atomic_op_needs_trivial_copy : Error<
   "address argument to atomic operation must be a pointer to a "
   "trivially-copyable type (%0 invalid)">;
 def err_atomic_op_needs_atomic_int_or_ptr : Error<
   "address argument to atomic operation must be a pointer to %select{|atomic }0"
   "integer or pointer (%1 invalid)">;
+def err_atomic_op_needs_int32_or_ptr : Error<
+  "address argument to atomic operation must be a pointer to signed or unsigned 32-bit integer">;
 def err_atomic_op_bitwise_needs_atomic_int : Error<
   "address argument to bitwise atomic operation must be a pointer to "
   "%select{|atomic }0integer (%1 invalid)">;
 def warn_atomic_op_has_invalid_memory_order : Warning<
   "memory order argument to atomic operation is invalid">,
   InGroup<DiagGroup<"atomic-memory-ordering">>;
 def err_atomic_op_has_invalid_synch_scope : Error<
   "synchronization scope argument to atomic operation is invalid">;

lib/AST/Expr.cpp

unsigned AtomicExpr::getNumSubExprs(AtomicOp Op) {
   case AO__atomic_fetch_xor:
   case AO__atomic_fetch_nand:
   case AO__atomic_add_fetch:
   case AO__atomic_sub_fetch:
   case AO__atomic_and_fetch:
   case AO__atomic_or_fetch:
   case AO__atomic_xor_fetch:
   case AO__atomic_nand_fetch:
+  case AO__atomic_fetch_min:
+  case AO__atomic_fetch_max:
     return 3;
 
   case AO__opencl_atomic_store:
   case AO__opencl_atomic_exchange:
   case AO__opencl_atomic_fetch_add:
   case AO__opencl_atomic_fetch_sub:
   case AO__opencl_atomic_fetch_and:
   case AO__opencl_atomic_fetch_or:

lib/CodeGen/CGAtomic.cpp

case AtomicExpr::AO__atomic_sub_fetch:
     LLVM_FALLTHROUGH;
   case AtomicExpr::AO__c11_atomic_fetch_sub:
   case AtomicExpr::AO__opencl_atomic_fetch_sub:
   case AtomicExpr::AO__atomic_fetch_sub:
     Op = llvm::AtomicRMWInst::Sub;
     break;
 
   case AtomicExpr::AO__opencl_atomic_fetch_min:
+  case AtomicExpr::AO__atomic_fetch_min:
     Op = E->getValueType()->isSignedIntegerType() ? llvm::AtomicRMWInst::Min
                                                   : llvm::AtomicRMWInst::UMin;
     break;
 
   case AtomicExpr::AO__opencl_atomic_fetch_max:
+  case AtomicExpr::AO__atomic_fetch_max:
     Op = E->getValueType()->isSignedIntegerType() ? llvm::AtomicRMWInst::Max
                                                   : llvm::AtomicRMWInst::UMax;
     break;
 
   case AtomicExpr::AO__atomic_and_fetch:
     PostOp = llvm::Instruction::And;
     LLVM_FALLTHROUGH;
   case AtomicExpr::AO__c11_atomic_fetch_and:
RValue CodeGenFunction::EmitAtomicExpr(AtomicExpr *E) {
   case AtomicExpr::AO__atomic_fetch_and:
   case AtomicExpr::AO__atomic_fetch_or:
   case AtomicExpr::AO__atomic_fetch_xor:
   case AtomicExpr::AO__atomic_fetch_nand:
   case AtomicExpr::AO__atomic_and_fetch:
   case AtomicExpr::AO__atomic_or_fetch:
   case AtomicExpr::AO__atomic_xor_fetch:
   case AtomicExpr::AO__atomic_nand_fetch:
+  case AtomicExpr::AO__atomic_fetch_min:
+  case AtomicExpr::AO__atomic_fetch_max:
     Val1 = EmitValToTemp(*this, E->getVal1());
     break;
   }
 
   QualType RValTy = E->getType().getUnqualifiedType();
 
   // The inlined atomics only function on iN types, where N is a power of 2. We
   // need to make sure (via temporaries if necessary) that all incoming values
if (UseLibcall) {
     case AtomicExpr::AO__opencl_atomic_fetch_max:
     case AtomicExpr::AO__atomic_fetch_xor:
     case AtomicExpr::AO__atomic_add_fetch:
     case AtomicExpr::AO__atomic_and_fetch:
     case AtomicExpr::AO__atomic_nand_fetch:
     case AtomicExpr::AO__atomic_or_fetch:
     case AtomicExpr::AO__atomic_sub_fetch:
     case AtomicExpr::AO__atomic_xor_fetch:
+    case AtomicExpr::AO__atomic_fetch_min:
+    case AtomicExpr::AO__atomic_fetch_max:
       // For these, only library calls for certain sizes exist.
       UseOptimizedLibcall = true;
       break;
 
     case AtomicExpr::AO__c11_atomic_load:
     case AtomicExpr::AO__c11_atomic_store:
     case AtomicExpr::AO__c11_atomic_exchange:
     case AtomicExpr::AO__c11_atomic_compare_exchange_weak:
case AtomicExpr::AO__atomic_xor_fetch:
       LLVM_FALLTHROUGH;
     case AtomicExpr::AO__c11_atomic_fetch_xor:
     case AtomicExpr::AO__opencl_atomic_fetch_xor:
     case AtomicExpr::AO__atomic_fetch_xor:
       LibCallName = "__atomic_fetch_xor";
       AddDirectArgument(*this, Args, UseOptimizedLibcall, Val1.getPointer(),
                         MemTy, E->getExprLoc(), sizeChars);
       break;
+    case AtomicExpr::AO__atomic_fetch_min:
     case AtomicExpr::AO__opencl_atomic_fetch_min:
       LibCallName = E->getValueType()->isSignedIntegerType()
                         ? "__atomic_fetch_min"
                         : "__atomic_fetch_umin";
       AddDirectArgument(*this, Args, UseOptimizedLibcall, Val1.getPointer(),
                         LoweredMemTy, E->getExprLoc(), sizeChars);
       break;
+    case AtomicExpr::AO__atomic_fetch_max:
     case AtomicExpr::AO__opencl_atomic_fetch_max:
       LibCallName = E->getValueType()->isSignedIntegerType()
                         ? "__atomic_fetch_max"
                         : "__atomic_fetch_umax";
       AddDirectArgument(*this, Args, UseOptimizedLibcall, Val1.getPointer(),
                         LoweredMemTy, E->getExprLoc(), sizeChars);
       break;
     // T __atomic_nand_fetch_N(T *mem, T val, int order)

lib/Sema/SemaChecking.cpp

ExprResult Sema::SemaAtomicOpsOverloaded(ExprResult TheCallResult,
   bool IsC11 = (Op >= AtomicExpr::AO__c11_atomic_init &&
                Op <= AtomicExpr::AO__c11_atomic_fetch_xor) ||
                IsOpenCL;
   bool IsN = Op == AtomicExpr::AO__atomic_load_n ||
              Op == AtomicExpr::AO__atomic_store_n ||
              Op == AtomicExpr::AO__atomic_exchange_n ||
              Op == AtomicExpr::AO__atomic_compare_exchange_n;
   bool IsAddSub = false;
+  bool IsMinMax = false;
 
   switch (Op) {
   case AtomicExpr::AO__c11_atomic_init:
   case AtomicExpr::AO__opencl_atomic_init:
     Form = Init;
     break;
 
   case AtomicExpr::AO__c11_atomic_load:
ExprResult Sema::SemaAtomicOpsOverloaded(ExprResult TheCallResult,
   case AtomicExpr::AO__atomic_fetch_nand:
   case AtomicExpr::AO__atomic_and_fetch:
   case AtomicExpr::AO__atomic_or_fetch:
   case AtomicExpr::AO__atomic_xor_fetch:
   case AtomicExpr::AO__atomic_nand_fetch:
     Form = Arithmetic;
     break;
 
+  case AtomicExpr::AO__atomic_fetch_min:
+  case AtomicExpr::AO__atomic_fetch_max:
+    IsMinMax = true;
+    Form = Arithmetic;
+    break;
+
   case AtomicExpr::AO__c11_atomic_exchange:
   case AtomicExpr::AO__opencl_atomic_exchange:
   case AtomicExpr::AO__atomic_exchange_n:
     Form = Xchg;
     break;
 
   case AtomicExpr::AO__atomic_exchange:
     Form = GNUXchg;
if (ValType.isConstQualified()) {
         << Ptr->getType() << Ptr->getSourceRange();
       return ExprError();
     }
   }
 
   // For an arithmetic operation, the implied arithmetic must be well-formed.
   if (Form == Arithmetic) {
     // gcc does not enforce these rules for GNU atomics, but we do so for sanity.
-    if (IsAddSub && !ValType->isIntegerType() && !ValType->isPointerType()) {
+    if (IsAddSub && !ValType->isIntegerType()
+        && !ValType->isPointerType()) {
       Diag(DRE->getLocStart(), diag::err_atomic_op_needs_atomic_int_or_ptr)
         << IsC11 << Ptr->getType() << Ptr->getSourceRange();
       return ExprError();
     }
-    if (!IsAddSub && !ValType->isIntegerType()) {
+    if (IsMinMax) {
+      const BuiltinType *BT = ValType->getAs<BuiltinType>();
+      if (!BT || (BT->getKind() != BuiltinType::Int &&
+                  BT->getKind() != BuiltinType::UInt)) {
+        Diag(DRE->getLocStart(), diag::err_atomic_op_needs_int32_or_ptr);
+        return ExprError();
+      }
+    }
+    if (!IsAddSub && !IsMinMax && !ValType->isIntegerType()) {
       Diag(DRE->getLocStart(), diag::err_atomic_op_bitwise_needs_atomic_int)
         << IsC11 << Ptr->getType() << Ptr->getSourceRange();
       return ExprError();
     }
     if (IsC11 && ValType->isPointerType() &&
         RequireCompleteType(Ptr->getLocStart(), ValType->getPointeeType(),
                             diag::err_incomplete_type)) {
       return ExprError();

test/CodeGen/Atomics.c

void test_lock (void)
   __sync_lock_release (&uc); // CHECK: store atomic {{.*}} release, align 1
   __sync_lock_release (&ss); // CHECK: store atomic {{.*}} release, align 2
   __sync_lock_release (&us); /// CHECK: store atomic {{.*}} release, align 2
   __sync_lock_release (&si); // CHECK: store atomic {{.*}} release, align 4
   __sync_lock_release (&ui); // CHECK: store atomic {{.*}} release, align 4
   __sync_lock_release (&sll); // CHECK: store atomic {{.*}} release, align 8
   __sync_lock_release (&ull); // CHECK: store atomic {{.*}} release, align 8
 }
+
+void test_atomic(void) {
+  ui = __atomic_fetch_min(&ui, 5, __ATOMIC_RELAXED); // CHECK: atomicrmw umin {{.*}} monotonic
+  si = __atomic_fetch_min(&si, 5, __ATOMIC_SEQ_CST); // CHECK: atomicrmw min {{.*}} seq_cst
+  ui = __atomic_fetch_max(&ui, 5, __ATOMIC_ACQUIRE); // CHECK: atomicrmw umax {{.*}} acquire
+  si = __atomic_fetch_max(&si, 5, __ATOMIC_RELEASE); // CHECK: atomicrmw max {{.*}} release
+}

test/Sema/atomic-ops.c

void f(_Atomic(int) *i, const _Atomic(int) *ci,
   __c11_atomic_fetch_add(p, 1, memory_order_seq_cst);
   __c11_atomic_fetch_add(d, 1, memory_order_seq_cst); // expected-error {{must be a pointer to atomic integer or pointer}}
 
   __atomic_fetch_add(i, 3, memory_order_seq_cst); // expected-error {{pointer to integer or pointer}}
   __atomic_fetch_sub(I, 3, memory_order_seq_cst);
   __atomic_fetch_sub(P, 3, memory_order_seq_cst);
   __atomic_fetch_sub(D, 3, memory_order_seq_cst); // expected-error {{must be a pointer to integer or pointer}}
   __atomic_fetch_sub(s1, 3, memory_order_seq_cst); // expected-error {{must be a pointer to integer or pointer}}
+  __atomic_fetch_min(D, 3, memory_order_seq_cst); // expected-error {{must be a pointer to signed or unsigned 32-bit integer}}
+  __atomic_fetch_max(P, 3, memory_order_seq_cst); // expected-error {{must be a pointer to signed or unsigned 32-bit integer}}
+  __atomic_fetch_max(p, 3);                       // expected-error {{too few arguments to function call, expected 3, have 2}}
 
   __c11_atomic_fetch_and(i, 1, memory_order_seq_cst);
   __c11_atomic_fetch_and(p, 1, memory_order_seq_cst); // expected-error {{must be a pointer to atomic integer}}
   __c11_atomic_fetch_and(d, 1, memory_order_seq_cst); // expected-error {{must be a pointer to atomic integer}}
 
   __atomic_fetch_and(i, 3, memory_order_seq_cst); // expected-error {{pointer to integer}}
   __atomic_fetch_or(I, 3, memory_order_seq_cst);
   __atomic_fetch_xor(P, 3, memory_order_seq_cst); // expected-error {{must be a pointer to integer}}
void memory_checks(_Atomic(int) *Ap, int *p, int val) {
 
   (void)__atomic_fetch_nand(p, val, memory_order_relaxed);
   (void)__atomic_fetch_nand(p, val, memory_order_acquire);
   (void)__atomic_fetch_nand(p, val, memory_order_consume);
   (void)__atomic_fetch_nand(p, val, memory_order_release);
   (void)__atomic_fetch_nand(p, val, memory_order_acq_rel);
   (void)__atomic_fetch_nand(p, val, memory_order_seq_cst);
 
+  (void)__atomic_fetch_min(p, val, memory_order_relaxed);
+  (void)__atomic_fetch_min(p, val, memory_order_acquire);
+  (void)__atomic_fetch_min(p, val, memory_order_consume);
+  (void)__atomic_fetch_min(p, val, memory_order_release);
+  (void)__atomic_fetch_min(p, val, memory_order_acq_rel);
+  (void)__atomic_fetch_min(p, val, memory_order_seq_cst);
+
+  (void)__atomic_fetch_max(p, val, memory_order_relaxed);
+  (void)__atomic_fetch_max(p, val, memory_order_acquire);
+  (void)__atomic_fetch_max(p, val, memory_order_consume);
+  (void)__atomic_fetch_max(p, val, memory_order_release);
+  (void)__atomic_fetch_max(p, val, memory_order_acq_rel);
+  (void)__atomic_fetch_max(p, val, memory_order_seq_cst);
+
   (void)__atomic_and_fetch(p, val, memory_order_relaxed);
   (void)__atomic_and_fetch(p, val, memory_order_acquire);
   (void)__atomic_and_fetch(p, val, memory_order_consume);
   (void)__atomic_and_fetch(p, val, memory_order_release);
   (void)__atomic_and_fetch(p, val, memory_order_acq_rel);
   (void)__atomic_and_fetch(p, val, memory_order_seq_cst);
 
   (void)__atomic_or_fetch(p, val, memory_order_relaxed);