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 ↗

(On Diff #145646)

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 ↗

(On Diff #145646)

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?

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, "v.", "t")
+ATOMIC_BUILTIN(__atomic_fetch_max, "v.", "t")
+ATOMIC_BUILTIN(__atomic_fetch_umin, "v.", "t")
+ATOMIC_BUILTIN(__atomic_fetch_umax, "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")

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:
+  case AO__atomic_fetch_umin:
+  case AO__atomic_fetch_umax:
     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_fetch_xor:
     break;
 
   case AtomicExpr::AO__atomic_nand_fetch:
     PostOp = llvm::Instruction::And; // the NOT is special cased below
     LLVM_FALLTHROUGH;
   case AtomicExpr::AO__atomic_fetch_nand:
     Op = llvm::AtomicRMWInst::Nand;
     break;
+  case AtomicExpr::AO__atomic_fetch_min:
+    Op = llvm::AtomicRMWInst::Min;
+    break;
+  case AtomicExpr::AO__atomic_fetch_max:
+    Op = llvm::AtomicRMWInst::Max;
+    break;
+  case AtomicExpr::AO__atomic_fetch_umin:
+    Op = llvm::AtomicRMWInst::UMin;
+    break;
+  case AtomicExpr::AO__atomic_fetch_umax:
+    Op = llvm::AtomicRMWInst::UMax;
+    break;
   }
 
   llvm::Value *LoadVal1 = CGF.Builder.CreateLoad(Val1);
   llvm::AtomicRMWInst *RMWI =
       CGF.Builder.CreateAtomicRMW(Op, Ptr.getPointer(), LoadVal1, Order, Scope);
   RMWI->setVolatile(E->isVolatile());
 
   // For __atomic_*_fetch operations, perform the operation again to
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:
+  case AtomicExpr::AO__atomic_fetch_umin:
+  case AtomicExpr::AO__atomic_fetch_umax:
     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:
+    case AtomicExpr::AO__atomic_fetch_umin:
+    case AtomicExpr::AO__atomic_fetch_umax:
       // 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__atomic_fetch_umin:
     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__atomic_fetch_umax:
     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:
+  case AtomicExpr::AO__atomic_fetch_umin:
+  case AtomicExpr::AO__atomic_fetch_umax:
+    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 || IsMinMax) && !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 (!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/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 integer or pointer}}
 
   __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_fetch_umin(p, val, memory_order_relaxed);
+  (void)__atomic_fetch_umin(p, val, memory_order_acquire);
+  (void)__atomic_fetch_umin(p, val, memory_order_consume);
+  (void)__atomic_fetch_umin(p, val, memory_order_release);
+  (void)__atomic_fetch_umin(p, val, memory_order_acq_rel);
+  (void)__atomic_fetch_umin(p, val, memory_order_seq_cst);
+
+  (void)__atomic_fetch_umax(p, val, memory_order_relaxed);
+  (void)__atomic_fetch_umax(p, val, memory_order_acquire);
+  (void)__atomic_fetch_umax(p, val, memory_order_consume);
+  (void)__atomic_fetch_umax(p, val, memory_order_release);
+  (void)__atomic_fetch_umax(p, val, memory_order_acq_rel);
+  (void)__atomic_fetch_umax(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);