Concurrency support for PNaCl ABI

lib/Analysis/NaCl/PNaClABIVerifyModule.cpp

Index: lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
diff --git a/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp b/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
index 7836484c2f868e02590d9507e11c6dd72c69ac33..48fe8baeeb7b722d604e1a817234febd01c9e0dc 100644
--- a/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
+++ b/lib/Analysis/NaCl/PNaClABIVerifyModule.cpp
@@ -13,13 +13,15 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Pass.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/NaCl.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/NaCl.h"
+#include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
@@ -181,12 +183,81 @@ static bool isWhitelistedCountBits(const Function *F, unsigned num_params) {
   return TypeAcceptable(ParamType, AcceptableTypes);
 }
 
+// The signature for atomics is:
+// T nacl.atomic.<size>(int32_t operation, T *location, T value,
+//                      T old_value, int32_t memory_order);
+// With:
+//  - T in {i8, i16, i32, i64}.
+//  - operation as a valid NaCl::AtomicOperation.
+//  - memory_order as a valid NaCl::MemoryOrder.
+static bool isWhitelistedAtomic(const Function *F, unsigned ID) {
+  LLVMContext &C = F->getContext();
+  FunctionType *FT = F->getFunctionType();
+
+  Type *ReturnType = FT->getReturnType();
+  switch (ID) {
+    default: llvm_unreachable("unhandled atomic intrinsic");
+    case Intrinsic::nacl_atomic_8:
+      if (ReturnType != Type::getInt8Ty(C)) return false;

[eliben, 2013/06/26 16:20:57]

Let's separate type checking from an intrinsic being allowed. If this intrinsic
is used incorrectly by passing a 32-bit thingie into the 8-bit intrinsic, the
error now will be:

"Function XXX is a disallowed LLVM intrinsics"

Which is sure to cause head scratching.

These intrinsics are allowed. They are whitelisted. But we want to type-check
them. The first line of defense is Intrinsics.td which allows to define argument
types and will reject wrong ones. If code still reaches here, we should pop a
different error message and die (report_fatal_error).

[JF, 2013/06/26 22:23:12]

Done.

+      break;
+    case Intrinsic::nacl_atomic_16:

[Mark Seaborn, 2013/06/26 14:33:41]

I don't think we have validator support for 16-bit atomics on all architectures,
so we should omit this for the first release.  We don't have any users of 16-bit
atomics in the PNaCl toolchain libraries.

[JF, 2013/06/26 15:52:29]

Vlad thinks it can be in for M30. Presumably this would fail at validation-time
instead of compile-time (which the SDK should do), which is still acceptable if
unused, but at least it gives us the option to emulate, which we don't have
otherwise.

[Mark Seaborn, 2013/06/26 16:47:01]

I don't think we should block PNaCl ABI stability on validator changes.
That's not really acceptable if it makes a pexe fail on one architecture but
work on another.  It breaks portability.
If you want to emulate, you could do that as a user-toolchain-side IR pass which
adds a cmpxchg loop.  No need for 16-bit atomics to be in the stable ABI for
now.

[JF, 2013/06/26 22:56:36]

Agreed, and this in no way blocks PNaCl ABI stability.
This is also true of all validation failures on one platform and not another.
16-bit atomics in no way increase the "surface area" of unacceptability, and
this is a moot point anyways because the translator can emulate on x86-32.
If we emulate then that should be determined by the translator. I don't see why
the validator issue wouldn't be fixed soon, and why we should permanently
penalize pexes for it.

[Mark Seaborn, 2013/06/27 01:04:33]

I'm not suggesting *permanently* penalizing pexes.  16-bit atomics can be added
to the set of operations allowed by the ABI later when they're supported on all
architectures.

The current situation is that this program works on x86-64 and ARM, but not on
x86-32:

volatile short int gvar;
int main() {
  __sync_fetch_and_add(&gvar, 1);
  return 0;
}

We need to remove the inconsistency before M30.  It would be easier if the
inconsistency is resolved by this change, but I suppose it could be resolved in
a later change.

[JF, 2013/06/27 01:31:39]

16-bit atomics are supported on all architectures. I fail to see your point.
Banning 16-bit atomics from the ABI won't make the program work either, and
that's what you were originally proposing. We need one of:
 1- Fix the validator.
 2- Rewrite the 16-bit atomics in the translator only for x86-32.
 3- Rewrite the 16-bit atomics for all pexes.

I think this is pretty clearly in order of desirability. Vlad thinks he can make
it for M30, and I don't think implementing 2 is hard. I don't see a need to 3,
ever: it permanently penalizes pexes generated this way, on all platforms.
Agreed, and as I explain above I think we should proceed with 2 only if 1 fails.

+      if (ReturnType != Type::getInt16Ty(C)) return false;
+      break;
+    case Intrinsic::nacl_atomic_32:
+      if (ReturnType != Type::getInt32Ty(C)) return false;
+      break;
+    case Intrinsic::nacl_atomic_64:

[Mark Seaborn, 2013/06/26 14:33:41]

I think we should omit 64-bit atomics, because MIPS does not support them.  We
don't have any users of 64-bit atomics in the PNaCl toolchain libraries.

[JF, 2013/06/26 15:52:29]

Our users will, and atomic support through locks is explicitly called out in the
C11/C++11 standards.

+      if (ReturnType != Type::getInt64Ty(C)) return false;
+      break;
+  }
+
+  if ((FT->getNumParams() != 5) ||
+      (FT->getParamType(0) != Type::getInt32Ty(C)) ||
+      (!FT->getParamType(1)->isPointerTy()) ||
+      (FT->getParamType(1)->getPointerElementType() != ReturnType) ||
+      (FT->getParamType(2) != ReturnType) ||
+      (FT->getParamType(3) != ReturnType) ||
+      (FT->getParamType(4) != Type::getInt32Ty(C)))
+    return false;

[eliben, 2013/06/26 16:20:57]

Ditto. 

[JF, 2013/06/26 22:23:12]

Moved to a separate function, with the above too.

+
+  // Validate the operation and memory_order arguments have whitelisted values.
+  for (Value::const_use_iterator Call(F->use_begin()), CallEnd(F->use_end());

[eliben, 2013/06/26 16:20:57]

Is there a reason here to use constructor syntax for Call/CallEnd? It's not the
LLVM style

[JF, 2013/06/26 22:23:12]

Done.

+       Call != CallEnd; ++Call) {
+    if (const CallInst *C = dyn_cast<CallInst>(*Call)) {
+      assert(C->getNumArgOperands() == 5 && "call should have as many "

[eliben, 2013/06/26 16:20:57]

Should this not be caught by LLVM's normal verification / type checking?

[JF, 2013/06/26 22:23:12]

Yes, that's why I used an assert.

+             "arguments as the corresponding intrinsic");
+      const Value *Operation = C->getArgOperand(0);
+      const Value *MemoryOrder = C->getArgOperand(4);
+      const Constant *OperationC = dyn_cast<Constant>(Operation);
+      const Constant *MemoryOrderC = dyn_cast<Constant>(MemoryOrder);
+      if (!Operation || !MemoryOrder)

[eliben, 2013/06/26 16:20:57]

This is even worse :) You're type checking calls to intrinsics, and if some call
is invalid you will just say the intrinsic is not allowed. but why is the call
invalid? IMHO calls should be verified together with other instructions in
PNaClABIVerifyFunctions, not here. And they should have descriptive error
messages.

[JF, 2013/06/26 22:23:12]

I don't agree: it's part of the intrinsic's requirements that the operation and
the memory order be compile-time constants. It's effectively in the signature of
the function, but there's no way to have a "constexpr" type in the declaration.
I added a note to that effect in the language reference, I do agree it wasn't
explained.

+        return false;
+      const APInt &OperationI = OperationC->getUniqueInteger();
+      const APInt &MemoryOrderI = MemoryOrderC->getUniqueInteger();
+      if (OperationI.ule(NaCl::AtomicInvalid) ||
+          OperationI.uge(NaCl::AtomicNum))
+        return false;
+      if (MemoryOrderI.ule(NaCl::MemoryOrderInvalid) ||
+          MemoryOrderI.uge(NaCl::MemoryOrderNum))
+        return false;
+      // TODO For now only sequential consistency is allowed.
+      if (MemoryOrderI != NaCl::MemoryOrderSequentiallyConsistent)
+        return false;
+    } else {
+      return false;
+    }
+  }
+
+  return true;
+}
+
 bool PNaClABIVerifyModule::isWhitelistedIntrinsic(const Function *F,
                                                   unsigned ID) {
   // Keep 3 categories of intrinsics for now.

[eliben, 2013/06/26 16:20:57]

I don't think the distinction between "always allowed" and "with restrictions"
adds clarity. The "with restrictions" intrinsics *are* allowed, but we just do
some further type checking on them.

So the 3 on this line should stay really 3, IMHO :)

[JF, 2013/06/26 22:23:12]

If it's allowed always then it should always be allowed, i.e. ``return true``.
Maybe this can be phrase better? I'll update the number for now, but I do think
the comment should be technically correct, though maybe not in the proposed
form.

   // (1) Allowed always
-  // (2) Never allowed
-  // (3) "Dev" intrinsics, which may or may not be allowed.
+  // (2) Allowed with certain restrictions.
+  // (3) Never allowed
+  // (4) "Dev" intrinsics, which may or may not be allowed.
   // "Dev" intrinsics are controlled by the PNaClABIAllowDevIntrinsics flag.
   // Please keep these sorted or grouped in a sensible way, within
   // each category.
@@ -194,10 +265,6 @@ bool PNaClABIVerifyModule::isWhitelistedIntrinsic(const Function *F,
     // Disallow by default.
     default: return false;
     // (1) Always allowed.
-    case Intrinsic::bswap: return isWhitelistedBswap(F);
-    case Intrinsic::ctlz:
-    case Intrinsic::cttz: return isWhitelistedCountBits(F, 2);
-    case Intrinsic::ctpop: return isWhitelistedCountBits(F, 1);
     case Intrinsic::memcpy:
     case Intrinsic::memmove:
     case Intrinsic::memset:
@@ -207,7 +274,17 @@ bool PNaClABIVerifyModule::isWhitelistedIntrinsic(const Function *F,
     case Intrinsic::trap:
       return true;
 
-    // (2) Known to be never allowed.
+    // (2) Allowed with certain restrictions.
+    case Intrinsic::bswap: return isWhitelistedBswap(F);
+    case Intrinsic::ctlz:
+    case Intrinsic::cttz: return isWhitelistedCountBits(F, 2);
+    case Intrinsic::ctpop: return isWhitelistedCountBits(F, 1);
+    case Intrinsic::nacl_atomic_8:
+    case Intrinsic::nacl_atomic_16:
+    case Intrinsic::nacl_atomic_32:
+    case Intrinsic::nacl_atomic_64: return isWhitelistedAtomic(F, ID);
+
+    // (3) Known to be never allowed.
     case Intrinsic::not_intrinsic:
     // Trampolines depend on a target-specific-sized/aligned buffer.
     case Intrinsic::adjust_trampoline:
@@ -269,7 +346,7 @@ bool PNaClABIVerifyModule::isWhitelistedIntrinsic(const Function *F,
     case Intrinsic::flt_rounds:
       return false;
 
-    // (3) Dev intrinsics.
+    // (4) Dev intrinsics.
     case Intrinsic::dbg_declare:
     case Intrinsic::dbg_value:
       return PNaClABIAllowDevIntrinsics || PNaClABIAllowDebugMetadata;