Concurrency support for PNaCl ABI

lib/Analysis/NaCl/PNaClABIVerifyFunctions.cpp

 //===- PNaClABIVerifyFunctions.cpp - Verify PNaCl ABI rules ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Verify function-level PNaCl ABI requirements.
 //
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/NaCl.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/NaClAtomicIntrinsics.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include "PNaClABITypeChecker.h"
 using namespace llvm;
 
 namespace {
 
 // Checks that examine anything in the function body should be in
 // FunctionPasses to make them streaming-friendly
 class PNaClABIVerifyFunctions : public FunctionPass {
  public:
   static char ID;
   PNaClABIVerifyFunctions() :
       FunctionPass(ID),
       Reporter(new PNaClABIErrorReporter),
-      ReporterIsOwned(true) {
+      ReporterIsOwned(true),
+      AI(NULL) {
     initializePNaClABIVerifyFunctionsPass(*PassRegistry::getPassRegistry());
   }
   explicit PNaClABIVerifyFunctions(PNaClABIErrorReporter *Reporter_) :
       FunctionPass(ID),
       Reporter(Reporter_),
-      ReporterIsOwned(false) {
+      ReporterIsOwned(false),
+      AI(NULL) {
     initializePNaClABIVerifyFunctionsPass(*PassRegistry::getPassRegistry());
   }
   ~PNaClABIVerifyFunctions() {
     if (ReporterIsOwned)
       delete Reporter;
   }
+  virtual bool doInitialization(Module &M) {
+    AI = new NaCl::AtomicIntrinsics(M.getContext());
+    return false;
+  }
+  virtual bool doFinalization(Module &M) {
+    delete AI;
+    return false;
+  }
   bool runOnFunction(Function &F);
   virtual void print(raw_ostream &O, const Module *M) const;
  private:
   bool IsWhitelistedMetadata(unsigned MDKind);
   const char *checkInstruction(const Instruction *Inst);
   PNaClABIErrorReporter *Reporter;
   bool ReporterIsOwned;
+  NaCl::AtomicIntrinsics *AI;

[eliben, 2013/07/09 17:17:19]

Name this member more descriptively. Also, use one of LLVM's smart pointers
instead of manual memory management.

[JF, 2013/07/11 00:17:18]

Done.

 };
 
 } // and anonymous namespace
 
 // There's no built-in way to get the name of an MDNode, so use a
 // string ostream to print it.
 static std::string getMDNodeString(unsigned Kind,
                                    const SmallVectorImpl<StringRef> &MDNames) {
   std::string MDName;
   raw_string_ostream N(MDName);
@@ skipping 68 matching lines @@
   if (isa<Instruction>(Val) || isa<Argument>(Val) || isa<BasicBlock>(Val))
     return true;
 
   // Allow some Constants.  Note that this excludes ConstantExprs.
   return PNaClABITypeChecker::isValidScalarType(Val->getType()) &&
          (isa<ConstantInt>(Val) ||
           isa<ConstantFP>(Val) ||
           isa<UndefValue>(Val));
 }
 
-static bool isAllowedAlignment(unsigned Alignment, Type *Ty, bool IsAtomic) {
-  if (IsAtomic) {
-    // For atomic operations, the alignment must match the size of the type.
-    if (Ty->isIntegerTy()) {
-      unsigned Bits = Ty->getIntegerBitWidth();
-      return Bits % 8 == 0 && Alignment == Bits / 8;
-    }
-    return (Ty->isDoubleTy() && Alignment == 8) ||
-           (Ty->isFloatTy() && Alignment == 4);
-  }
+static bool isAllowedAlignment(unsigned Alignment, Type *Ty) {
   // Non-atomic integer operations must always use "align 1", since we
   // do not want the backend to generate code with non-portable
   // undefined behaviour (such as misaligned access faults) if user
   // code specifies "align 4" but uses a misaligned pointer.  As a
   // concession to performance, we allow larger alignment values for
   // floating point types.
   //
   // To reduce the set of alignment values that need to be encoded in
   // pexes, we disallow other alignment values.  We require alignments
   // to be explicit by disallowing Alignment == 0.
   return Alignment == 1 ||
          (Ty->isDoubleTy() && Alignment == 8) ||
          (Ty->isFloatTy() && Alignment == 4);
 }
 
+static bool hasAllowedAtomicRMWOperation(
+    const NaCl::AtomicIntrinsics::AtomicIntrinsic *I, const CallInst *Call) {
+  for (size_t P = 0; P != I->NumParams; ++P) {
+    if (I->ParamType[P] != NaCl::AtomicIntrinsics::RMW)
+      continue;
+
+    const Value *Operation = Call->getOperand(P);
+    if (!Operation)
+      return false;
+    const Constant *C = dyn_cast<Constant>(Operation);
+    if (!C)
+      return false;
+    const APInt &I = C->getUniqueInteger();
+    if (I.ule(NaCl::AtomicInvalid) || I.uge(NaCl::AtomicNum))
+      return false;
+  }
+  return true;
+}
+
+static bool hasAllowedAtomicMemoryOrder(
+    const NaCl::AtomicIntrinsics::AtomicIntrinsic *I, const CallInst *Call) {
+  for (size_t P = 0; P != I->NumParams; ++P) {
+    if (I->ParamType[P] != NaCl::AtomicIntrinsics::Mem)
+      continue;
+
+    const Value *MemoryOrder = Call->getOperand(P);
+    if (!MemoryOrder)
+      return false;
+    const Constant *C = dyn_cast<Constant>(MemoryOrder);
+    if (!C)
+      return false;
+    const APInt &I = C->getUniqueInteger();
+    if (I.ule(NaCl::MemoryOrderInvalid) || I.uge(NaCl::MemoryOrderNum))
+      return false;
+    // TODO For now only sequential consistency is allowed. When more
+    //      are allowed we need to validate that the memory order is
+    //      allowed on the specific atomic operation (e.g. no store
+    //      acquire, and relationship between success/failure memory
+    //      order on compare exchange).
+    if (I != NaCl::MemoryOrderSequentiallyConsistent)
+      return false;
+  }
+  return true;
+}
+
 // Check the instruction's opcode and its operands.  The operands may
 // require opcode-specific checking.
 //
 // This returns an error string if the instruction is rejected, or
 // NULL if the instruction is allowed.
 const char *PNaClABIVerifyFunctions::checkInstruction(const Instruction *Inst) {
   // If the instruction has a single pointer operand, PtrOperandIndex is
   // set to its operand index.
   unsigned PtrOperandIndex = -1;
 
   switch (Inst->getOpcode()) {
     // Disallowed instructions. Default is to disallow.
     // We expand GetElementPtr out into arithmetic.
     case Instruction::GetElementPtr:
     // VAArg is expanded out by ExpandVarArgs.
     case Instruction::VAArg:
     // Zero-cost C++ exception handling is not supported yet.
     case Instruction::Invoke:
     case Instruction::LandingPad:
     case Instruction::Resume:
     // indirectbr may interfere with streaming
     case Instruction::IndirectBr:
     // No vector instructions yet
     case Instruction::ExtractElement:
     case Instruction::InsertElement:
     case Instruction::ShuffleVector:
     // ExtractValue and InsertValue operate on struct values.
     case Instruction::ExtractValue:
     case Instruction::InsertValue:
+    // Atomics should become NaCl intrinsics.
+    case Instruction::AtomicCmpXchg:
+    case Instruction::AtomicRMW:
+    case Instruction::Fence:
       return "bad instruction opcode";
     default:
       return "unknown instruction opcode";
 
     // Terminator instructions
     case Instruction::Ret:
     case Instruction::Br:
     case Instruction::Unreachable:
     // Binary operations
     case Instruction::FAdd:
     case Instruction::FSub:
     case Instruction::FMul:
     case Instruction::FDiv:
     case Instruction::FRem:
     // Bitwise binary operations
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor:
-    // Memory instructions
-    case Instruction::Fence:
     // Conversion operations
     case Instruction::Trunc:
     case Instruction::ZExt:
     case Instruction::SExt:
     case Instruction::FPTrunc:
     case Instruction::FPExt:
     case Instruction::FPToUI:
     case Instruction::FPToSI:
     case Instruction::UIToFP:
     case Instruction::SIToFP:
@@ skipping 18 matching lines @@
     case Instruction::Shl:
     case Instruction::LShr:
     case Instruction::AShr:
       if (Inst->getOperand(0)->getType()->isIntegerTy(1))
         return "arithmetic on i1";
       break;
 
     // Memory accesses.
     case Instruction::Load: {
       const LoadInst *Load = cast<LoadInst>(Inst);
+      PtrOperandIndex = Load->getPointerOperandIndex();
+      if (Load->isAtomic())
+        return "atomic load";
+      if (Load->isVolatile())
+        return "volatile load";
       if (!isAllowedAlignment(Load->getAlignment(),
-                              Load->getType(),
-                              Load->isAtomic()))
+                              Load->getType()))
         return "bad alignment";
-      PtrOperandIndex = 0;
       if (!isNormalizedPtr(Inst->getOperand(PtrOperandIndex)))
         return "bad pointer";
       break;
     }
     case Instruction::Store: {
       const StoreInst *Store = cast<StoreInst>(Inst);
+      PtrOperandIndex = Store->getPointerOperandIndex();
+      if (Store->isAtomic())
+        return "atomic store";
+      if (Store->isVolatile())
+        return "volatile store";
       if (!isAllowedAlignment(Store->getAlignment(),
-                              Store->getValueOperand()->getType(),
-                              Store->isAtomic()))
+                              Store->getValueOperand()->getType()))
         return "bad alignment";
-      PtrOperandIndex = 1;
       if (!isNormalizedPtr(Inst->getOperand(PtrOperandIndex)))
         return "bad pointer";
       break;
     }
-    case Instruction::AtomicCmpXchg:
-    case Instruction::AtomicRMW:
-      PtrOperandIndex = 0;
-      if (!isNormalizedPtr(Inst->getOperand(PtrOperandIndex)))
-        return "bad pointer";
-      break;
 
     // Casts.
     case Instruction::BitCast:
       if (Inst->getType()->isPointerTy()) {
         PtrOperandIndex = 0;
         if (!isInherentPtr(Inst->getOperand(PtrOperandIndex)))
           return "operand not InherentPtr";
       }
       break;
     case Instruction::IntToPtr:
@@ skipping 30 matching lines @@
       // metadata arguments, so handle them specially.
       if (const IntrinsicInst *Call = dyn_cast<IntrinsicInst>(Inst)) {
         for (unsigned ArgNum = 0, E = Call->getNumArgOperands();
              ArgNum < E; ++ArgNum) {
           const Value *Arg = Call->getArgOperand(ArgNum);
           if (!(isValidScalarOperand(Arg) ||
                 isNormalizedPtr(Arg) ||
                 isa<MDNode>(Arg)))
             return "bad intrinsic operand";
         }
+
         // Disallow alignments other than 1 on memcpy() etc., for the
         // same reason that we disallow them on integer loads and
         // stores.
         if (const MemIntrinsic *MemOp = dyn_cast<MemIntrinsic>(Call)) {
           // Avoid the getAlignment() method here because it aborts if
           // the alignment argument is not a Constant.
           Value *AlignArg = MemOp->getArgOperand(3);
           if (!isa<ConstantInt>(AlignArg) ||
               cast<ConstantInt>(AlignArg)->getZExtValue() != 1) {
             return "bad alignment";
           }
         }
+
+        // Disallow NaCl atomic intrinsics which don't have valid
+        // constant NaCl::AtomicOperation and NaCl::MemoryOrder
+        // parameters.
+        switch (Call->getIntrinsicID()) {
+          default: break;  // Non-atomic intrinsic.
+          case Intrinsic::nacl_atomic_load:
+          case Intrinsic::nacl_atomic_store:
+          case Intrinsic::nacl_atomic_rmw:
+          case Intrinsic::nacl_atomic_cmpxchg:
+          case Intrinsic::nacl_atomic_fence: {
+            // All overloads have memory order and RMW operation in the
+            // same parameter, arbitrarily use the I32 overload.
+            Type *T = Type::getInt32Ty(
+                Inst->getParent()->getParent()->getContext());
+            const NaCl::AtomicIntrinsics::AtomicIntrinsic *I =
+                AI->find(Call->getIntrinsicID(), T);
+            if (!hasAllowedAtomicMemoryOrder(I, Call))
+              return "invalid memory order";
+            if (!hasAllowedAtomicRMWOperation(I, Call))
+              return "invalid atomicRMW operation";
+          } break;
+        }
+
         // Allow the instruction and skip the later checks.
         return NULL;
       }
 
       // The callee is the last operand.
       PtrOperandIndex = Inst->getNumOperands() - 1;
       if (!isNormalizedPtr(Inst->getOperand(PtrOperandIndex)))
         return "bad function callee operand";
       break;
     }
@@ skipping 109 matching lines @@
 }
 
 char PNaClABIVerifyFunctions::ID = 0;
 INITIALIZE_PASS(PNaClABIVerifyFunctions, "verify-pnaclabi-functions",
                 "Verify functions for PNaCl", false, true)
 
 FunctionPass *llvm::createPNaClABIVerifyFunctionsPass(
     PNaClABIErrorReporter *Reporter) {
   return new PNaClABIVerifyFunctions(Reporter);
 }