Add Intrinsic::nacl_atomic_is_lock_free

This is part of a bigger CL to fix C++11 in PNaCl, to commit in the following order:
 - https://codereview.chromium.org/20552002
 - https://codereview.chromium.org/20554002
 - https://codereview.chromium.org/20560002
 - https://codereview.chromium.org/20561002

This should be the last PNaCl ABI change for C11/C+11 atomic support.

Note that Clang already has a builtin for lock-free, but it's partly resolved by Clang's ExprConstant.cpp and CGBuiltin.cpp, whereas what we want is a call that becomes a constant at translation-time. I made the translation part fairly general so it's easy to support architectures where ``true`` isn't always the right answer.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=3475
TEST= ./scons run_synchronization_cpp11_test --verbose bitcode=1 platform=x86-64
TEST= ninja check-all
R=dschuff@chromium.org

Review URL: https://codereview.chromium.org/20554002

8 files changed, 172 insertions, 25 deletions

diff --git a/docs/PNaClDeveloperGuide.rst b/docs/PNaClDeveloperGuide.rst
index b0a47423e3..9c27ae5c14 100644
--- a/docs/PNaClDeveloperGuide.rst
+++ b/docs/PNaClDeveloperGuide.rst
@@ -53,7 +53,7 @@ relates memory locations to each other as the C11/C++11 standards do.
 As in C11/C++11 some atomic accesses may be implemented with locks on certain
 platforms. The ``ATOMIC_*_LOCK_FREE`` macros will always be ``1``, signifying
 that all types are sometimes lock-free. The ``is_lock_free`` methods will return
-the current platform's implementation at runtime.
+the current platform's implementation at translation time.
 
 The PNaCl toolchain supports concurrent memory accesses through legacy GCC-style
 ``__sync_*`` builtins, as well as through C11/C++11 atomic primitives.
diff --git a/docs/PNaClLangRef.rst b/docs/PNaClLangRef.rst
index 027f33ac92..75218a0c02 100644
--- a/docs/PNaClLangRef.rst
+++ b/docs/PNaClLangRef.rst
@@ -488,3 +488,15 @@ in ``"llvm/IR/NaClAtomicIntrinsics.h"``.
     operations as well as some legacy GCC-style ``__sync_*`` builtins
     while remaining stable as the LLVM codebase changes. The user
     isn't expected to use these intrinsics directly.
+
+.. code-block:: llvm
+
+  declare i1 @llvm.nacl.atomic.is.lock.free(i32 <byte_size>, i8* <address>)
+
+  The ``llvm.nacl.atomic.is.lock.free`` intrinsic is designed to
+  determine at translation time whether atomic operations of a certain
+  ``byte_size`` (a compile-time constant), at a particular ``address``,
+  are lock-free or not. This reflects the C11 ``atomic_is_lock_free``
+  function from header ``<stdatomic.h>`` and the C++11 ``is_lock_free``
+  member function in header ``<atomic>``. It can be used through the
+  ``__nacl_atomic_is_lock_free`` builtin.
diff --git a/include/llvm/IR/Intrinsics.td b/include/llvm/IR/Intrinsics.td
index ef15ceb158..15567eb2db 100644
--- a/include/llvm/IR/Intrinsics.td
+++ b/include/llvm/IR/Intrinsics.td
@@ -526,6 +526,9 @@ def int_nacl_atomic_cmpxchg : Intrinsic<[llvm_anyint_ty],
     [IntrReadWriteArgMem]>;
 def int_nacl_atomic_fence : Intrinsic<[], [llvm_i32_ty],
     [IntrReadWriteArgMem]>;
+def int_nacl_atomic_is_lock_free : Intrinsic<[llvm_i1_ty],
+    [llvm_i32_ty, llvm_ptr_ty], [IntrNoMem]>,
+    GCCBuiltin<"__nacl_atomic_is_lock_free">;
 // @LOCALMOD-END
 
 //===----------------------------------------------------------------------===//
diff --git a/lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp b/lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp
index 5318fc8af0..e55a9f0df4 100644
--- a/lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp
+++ b/lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp
@@ -213,6 +213,24 @@ static bool hasAllowedAtomicMemoryOrder(
   return true;
 }
 
+static bool hasAllowedLockFreeByteSize(const CallInst *Call) {
+  if (!Call->getType()->isIntegerTy())
+    return false;
+  const Value *Operation = Call->getOperand(0);
+  if (!Operation)
+    return false;
+  const Constant *C = dyn_cast<Constant>(Operation);
+  if (!C)
+    return false;
+  const APInt &I = C->getUniqueInteger();
+  // PNaCl currently only supports atomics of byte size {1,2,4,8} (which
+  // may or may not be lock-free). These values coincide with
+  // C11/C++11's supported atomic types.
+  if (I == 1 || I == 2 || I == 4 || I == 8)
+    return true;
+  return false;
+}
+
 // Check the instruction's opcode and its operands.  The operands may
 // require opcode-specific checking.
 //
@@ -392,11 +410,11 @@ const char *PNaClABIVerifyFunctions::checkInstruction(const Instruction *Inst) {
           }
         }
 
-        // Disallow NaCl atomic intrinsics which don't have valid
-        // constant NaCl::AtomicOperation and NaCl::MemoryOrder
-        // parameters.
         switch (Call->getIntrinsicID()) {
-          default: break;  // Non-atomic intrinsic.
+          default: break;  // Other intrinsics don't require checks.
+          // Disallow NaCl atomic intrinsics which don't have valid
+          // constant NaCl::AtomicOperation and NaCl::MemoryOrder
+          // parameters.
           case Intrinsic::nacl_atomic_load:
           case Intrinsic::nacl_atomic_store:
           case Intrinsic::nacl_atomic_rmw:
@@ -413,6 +431,12 @@ const char *PNaClABIVerifyFunctions::checkInstruction(const Instruction *Inst) {
             if (!hasAllowedAtomicRMWOperation(I, Call))
               return "invalid atomicRMW operation";
           } break;
+          // Disallow NaCl atomic_is_lock_free intrinsics which don't
+          // have valid constant size type.
+          case Intrinsic::nacl_atomic_is_lock_free:
+            if (!hasAllowedLockFreeByteSize(Call))
+              return "invalid atomic lock-free byte size";
+            break;
         }
 
         // Allow the instruction and skip the later checks.
diff --git a/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp b/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
index f1359866bd..e781680f3f 100644
--- a/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
+++ b/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
@@ -215,6 +215,8 @@ AllowedIntrinsics::AllowedIntrinsics(LLVMContext *Context) : Context(Context) {
   }
   addIntrinsic(Intrinsic::nacl_atomic_fence);
 
+  addIntrinsic(Intrinsic::nacl_atomic_is_lock_free);
+
   // Stack save and restore are used to support C99 VLAs.
   addIntrinsic(Intrinsic::stacksave);
   addIntrinsic(Intrinsic::stackrestore);
diff --git a/lib/Transforms/NaCl/ResolvePNaClIntrinsics.cpp b/lib/Transforms/NaCl/ResolvePNaClIntrinsics.cpp
index 9b526a102a..d3e107f5f7 100644
--- a/lib/Transforms/NaCl/ResolvePNaClIntrinsics.cpp
+++ b/lib/Transforms/NaCl/ResolvePNaClIntrinsics.cpp
@@ -85,26 +85,28 @@ private:
 };
 
 /// Rewrite intrinsic calls to another function.
-class SimpleCallResolver : public ResolvePNaClIntrinsics::CallResolver {
+class IntrinsicCallToFunctionCall :
+    public ResolvePNaClIntrinsics::CallResolver {
 public:
-  SimpleCallResolver(Function &F, Intrinsic::ID IntrinsicID,
-                     const char *TargetFunctionName)
+  IntrinsicCallToFunctionCall(Function &F, Intrinsic::ID IntrinsicID,
+                              const char *TargetFunctionName,
+                              ArrayRef<Type *> Tys = None)
       : CallResolver(F, IntrinsicID),
-        TargetFunction(M->getFunction(TargetFunctionName)) {
+        TargetFunction(M->getFunction(TargetFunctionName)), Tys(Tys) {
     // Expect to find the target function for this intrinsic already
     // declared, even if it is never used.
     if (!TargetFunction)
-      report_fatal_error(
-          std::string("Expected to find external declaration of ") +
-          TargetFunctionName);
+      report_fatal_error(std::string(
+          "Expected to find external declaration of ") + TargetFunctionName);
   }
-  virtual ~SimpleCallResolver() {}
+  virtual ~IntrinsicCallToFunctionCall() {}
 
 private:
   Function *TargetFunction;
+  ArrayRef<Type *> Tys;
 
   virtual Function *doGetDeclaration() const {
-    return Intrinsic::getDeclaration(M, IntrinsicID);
+    return Intrinsic::getDeclaration(M, IntrinsicID, Tys);
   }
 
   virtual bool doResolve(IntrinsicInst *Call) {
@@ -112,9 +114,74 @@ private:
     return true;
   }
 
-  SimpleCallResolver(const SimpleCallResolver &) LLVM_DELETED_FUNCTION;
-  SimpleCallResolver &operator=(
-      const SimpleCallResolver &) LLVM_DELETED_FUNCTION;
+  IntrinsicCallToFunctionCall(const IntrinsicCallToFunctionCall &)
+      LLVM_DELETED_FUNCTION;
+  IntrinsicCallToFunctionCall &operator=(const IntrinsicCallToFunctionCall &)
+      LLVM_DELETED_FUNCTION;
+};
+
+/// Rewrite intrinsic calls to a constant whose value is determined by a
+/// functor. This functor is called once per Call, and returns a
+/// Constant that should replace the Call.
+template <class Callable>
+class ConstantCallResolver : public ResolvePNaClIntrinsics::CallResolver {
+public:
+  ConstantCallResolver(Function &F, Intrinsic::ID IntrinsicID, Callable Functor,
+                       ArrayRef<Type *> Tys = None)
+      : CallResolver(F, IntrinsicID), Functor(Functor) {}
+  virtual ~ConstantCallResolver() {}
+
+private:
+  Callable Functor;
+  ArrayRef<Type *> Tys;
+
+  virtual Function *doGetDeclaration() const {
+    return Intrinsic::getDeclaration(M, IntrinsicID, Tys);
+  }
+
+  virtual bool doResolve(IntrinsicInst *Call) {
+    Constant *C = Functor(Call);
+    Call->replaceAllUsesWith(C);
+    Call->eraseFromParent();
+    return true;
+  }
+
+  ConstantCallResolver(const ConstantCallResolver &) LLVM_DELETED_FUNCTION;
+  ConstantCallResolver &operator=(const ConstantCallResolver &)
+      LLVM_DELETED_FUNCTION;
+};
+
+/// Resolve __nacl_atomic_is_lock_free to true/false at translation
+/// time. PNaCl's currently supported platforms all support lock-free
+/// atomics at byte sizes {1,2,4,8}, and the alignment of the pointer is
+/// always expected to be natural (as guaranteed by C11 and
+/// C++11). PNaCl's Module-level ABI verification checks that the byte
+/// size is constant and in {1,2,4,8}.
+struct IsLockFreeToConstant {
+  Constant *operator()(CallInst *Call) {
+    const uint64_t MaxLockFreeByteSize = 8;
+    const APInt &ByteSize =
+        cast<Constant>(Call->getOperand(0))->getUniqueInteger();
+
+#   if defined(__pnacl__)
+    switch (__builtin_nacl_target_arch()) {
+    case PnaclTargetArchitectureX86_32:
+    case PnaclTargetArchitectureX86_64:
+    case PnaclTargetArchitectureARM_32:
+      break;
+    default:
+      return false;
+    }
+#   elif defined(__i386__) || defined(__x86_64__) || defined(__arm__)
+    // Continue.
+#   else
+#     error "Unknown architecture"
+#   endif
+
+    bool IsLockFree = ByteSize.ule(MaxLockFreeByteSize);
+    Constant *C = ConstantInt::get(Call->getType(), IsLockFree);
+    return C;
+  }
 };
 
 /// Rewrite atomic intrinsics to LLVM IR instructions.
@@ -188,8 +255,8 @@ private:
   }
 
   AtomicOrdering thawMemoryOrder(const Value *MemoryOrder) const {
-    NaCl::MemoryOrder MO = (NaCl::MemoryOrder)cast<Constant>(MemoryOrder)
-        ->getUniqueInteger().getLimitedValue();
+    NaCl::MemoryOrder MO = (NaCl::MemoryOrder)
+        cast<Constant>(MemoryOrder)->getUniqueInteger().getLimitedValue();
     switch (MO) {
     // Only valid values should pass validation.
     default: llvm_unreachable("unknown memory order");
@@ -204,9 +271,8 @@ private:
   }
 
   AtomicRMWInst::BinOp thawRMWOperation(const Value *Operation) const {
-    NaCl::AtomicRMWOperation Op =
-        (NaCl::AtomicRMWOperation)cast<Constant>(Operation)->getUniqueInteger()
-            .getLimitedValue();
+    NaCl::AtomicRMWOperation Op = (NaCl::AtomicRMWOperation)
+        cast<Constant>(Operation)->getUniqueInteger().getLimitedValue();
     switch (Op) {
     // Only valid values should pass validation.
     default: llvm_unreachable("unknown atomic RMW operation");
@@ -248,14 +314,17 @@ bool ResolvePNaClIntrinsics::visitCalls(
 }
 
 bool ResolvePNaClIntrinsics::runOnFunction(Function &F) {
+  LLVMContext &C = F.getParent()->getContext();
   bool Changed = false;
 
-  SimpleCallResolver SetJmpResolver(F, Intrinsic::nacl_setjmp, "setjmp");
-  SimpleCallResolver LongJmpResolver(F, Intrinsic::nacl_longjmp, "longjmp");
+  IntrinsicCallToFunctionCall SetJmpResolver(F, Intrinsic::nacl_setjmp,
+                                             "setjmp");
+  IntrinsicCallToFunctionCall LongJmpResolver(F, Intrinsic::nacl_longjmp,
+                                              "longjmp");
   Changed |= visitCalls(SetJmpResolver);
   Changed |= visitCalls(LongJmpResolver);
 
-  NaCl::AtomicIntrinsics AI(F.getParent()->getContext());
+  NaCl::AtomicIntrinsics AI(C);
   NaCl::AtomicIntrinsics::View V = AI.allIntrinsicsAndOverloads();
   for (NaCl::AtomicIntrinsics::View::iterator I = V.begin(), E = V.end();
        I != E; ++I) {
@@ -263,6 +332,10 @@ bool ResolvePNaClIntrinsics::runOnFunction(Function &F) {
     Changed |= visitCalls(AtomicResolver);
   }
 
+  ConstantCallResolver<IsLockFreeToConstant> IsLockFreeResolver(
+      F, Intrinsic::nacl_atomic_is_lock_free, IsLockFreeToConstant());
+  Changed |= visitCalls(IsLockFreeResolver);
+
   return Changed;
 }
 
diff --git a/test/NaCl/PNaClABI/intrinsics.ll b/test/NaCl/PNaClABI/intrinsics.ll
index 3e9d830623..a210491823 100644
--- a/test/NaCl/PNaClABI/intrinsics.ll
+++ b/test/NaCl/PNaClABI/intrinsics.ll
@@ -54,6 +54,7 @@ declare i16 @llvm.nacl.atomic.cmpxchg.i16(i16*, i16, i16, i32, i32)
 declare i32 @llvm.nacl.atomic.cmpxchg.i32(i32*, i32, i32, i32, i32)
 declare i64 @llvm.nacl.atomic.cmpxchg.i64(i64*, i64, i64, i32, i32)
 declare void @llvm.nacl.atomic.fence(i32)
+declare i1 @llvm.nacl.atomic.is.lock.free(i32, i8*)
 
 declare i16 @llvm.bswap.i16(i16)
 declare i32 @llvm.bswap.i32(i32)
diff --git a/test/Transforms/NaCl/resolve-pnacl-intrinsics.ll b/test/Transforms/NaCl/resolve-pnacl-intrinsics.ll
index af9a38df0f..737561ee1d 100644
--- a/test/Transforms/NaCl/resolve-pnacl-intrinsics.ll
+++ b/test/Transforms/NaCl/resolve-pnacl-intrinsics.ll
@@ -29,6 +29,7 @@ declare i16 @llvm.nacl.atomic.cmpxchg.i16(i16*, i16, i16, i32, i32)
 declare i32 @llvm.nacl.atomic.cmpxchg.i32(i32*, i32, i32, i32, i32)
 declare i64 @llvm.nacl.atomic.cmpxchg.i64(i64*, i64, i64, i32, i32)
 declare void @llvm.nacl.atomic.fence(i32)
+declare i1 @llvm.nacl.atomic.is.lock.free(i32, i8*)
 
 ; These declarations must be here because the function pass expects
 ; to find them. In real life they're inserted by the translator
@@ -99,6 +100,37 @@ define void @test_synchronize() {
   ret void
 }
 
+; CHECK: @test_is_lock_free_1
+define i1 @test_is_lock_free_1(i8* %ptr) {
+  ; CHECK: ret i1 {{true|false}}
+  %res = call i1 @llvm.nacl.atomic.is.lock.free(i32 1, i8* %ptr)
+  ret i1 %res
+}
+
+; CHECK: @test_is_lock_free_2
+define i1 @test_is_lock_free_2(i16* %ptr) {
+  ; CHECK: ret i1 {{true|false}}
+  %ptr2 = bitcast i16* %ptr to i8*
+  %res = call i1 @llvm.nacl.atomic.is.lock.free(i32 2, i8* %ptr2)
+  ret i1 %res
+}
+
+; CHECK: @test_is_lock_free_4
+define i1 @test_is_lock_free_4(i32* %ptr) {
+  ; CHECK: ret i1 {{true|false}}
+  %ptr2 = bitcast i32* %ptr to i8*
+  %res = call i1 @llvm.nacl.atomic.is.lock.free(i32 4, i8* %ptr2)
+  ret i1 %res
+}
+
+; CHECK: @test_is_lock_free_8
+define i1 @test_is_lock_free_8(i64* %ptr) {
+  ; CHECK: ret i1 {{true|false}}
+  %ptr2 = bitcast i64* %ptr to i8*
+  %res = call i1 @llvm.nacl.atomic.is.lock.free(i32 8, i8* %ptr2)
+  ret i1 %res
+}
+
 ; CHECK: @test_lock_test_and_set_i32
 define i32 @test_lock_test_and_set_i32(i32* %ptr, i32 %value) {
   ; CHECK: %1 = atomicrmw xchg i32* %ptr, i32 %value seq_cst