Concurrency support for PNaCl ABI

Add portable support for concurrency in PNaCl's ABI:
 - Promote volatile to atomic.
 - Promote all memory ordering to sequential consistency.
 - Rewrite all atomic operations to frozen NaCl intrinsics for pexe.
 - Rewrite atomic intrinsics to LLVM instructions for translation.

This change also adds documentation to the PNaCl language reference, as
well as tests where it makes sense.

A future CL could clean up more of our code which mentions atomics,
volatiles, memory orderings.

Multiple reviewers because this is a big patch:
 - eliben: LLVM-fu and ResolvePNaClIntrinsics.
 - dschuff: ABI stability.
 - mseaborn: ABI stability.
 - sehr: Tron-duty (fight for the user's programs to work).

BUG= https://code.google.com/p/nativeclient/issues/detail?id=3475
R=dschuff@chromium.org, eliben@chromium.org, sehr@google.com
TEST= (cd ./pnacl/build/llvm_x86_64; ninja check-all) && ./pnacl/test.sh test-x86-32 && ./pnacl/test.sh test-x86-64 && ./pnacl/test.sh test-arm && ./pnacl/test.sh test-x86-32-sbtc && ./pnacl/test.sh test-x86-64-sbtc && ./pnacl/test.sh test-arm-sbtc

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

4 files changed, 149 insertions, 9 deletions

diff --git a/include/llvm/IR/Intrinsics.td b/include/llvm/IR/Intrinsics.td
index 3e49620435..ef15ceb158 100644
--- a/include/llvm/IR/Intrinsics.td
+++ b/include/llvm/IR/Intrinsics.td
@@ -498,6 +498,34 @@ def int_nacl_tp_tdb_offset : Intrinsic<[llvm_i32_ty], [llvm_i32_ty]>,
 // pnaclintrin.h.
 def int_nacl_target_arch : Intrinsic<[llvm_i32_ty], []>,
                             GCCBuiltin<"__builtin_nacl_target_arch">;
+
+// Atomic intrinsics.
+//
+// Volatiles and atomics are encoded through these intrinsics to make
+// them platform-independent, remove some of LLVM's legacy, and isolate
+// PNaCl from future changes to IR. The intrinsics allow user code to
+// use `__sync_*` builtins as well as C11/C++11 atomics.
+//
+// These are further documented in docs/PNaClLangRef.rst.
+//
+// Note that IntrReadWriteArgMem is used in all cases to prevent
+// reordering.
+def int_nacl_atomic_load : Intrinsic<[llvm_anyint_ty],
+    [LLVMPointerType<LLVMMatchType<0>>, llvm_i32_ty],
+    [IntrReadWriteArgMem]>;
+def int_nacl_atomic_store : Intrinsic<[],
+    [llvm_anyint_ty, LLVMPointerType<LLVMMatchType<0>>, llvm_i32_ty],
+    [IntrReadWriteArgMem]>;
+def int_nacl_atomic_rmw : Intrinsic<[llvm_anyint_ty],
+    [llvm_i32_ty, LLVMPointerType<LLVMMatchType<0>>, LLVMMatchType<0>,
+     llvm_i32_ty],
+    [IntrReadWriteArgMem]>;
+def int_nacl_atomic_cmpxchg : Intrinsic<[llvm_anyint_ty],
+    [LLVMPointerType<LLVMMatchType<0>>, LLVMMatchType<0>, LLVMMatchType<0>,
+     llvm_i32_ty, llvm_i32_ty],
+    [IntrReadWriteArgMem]>;
+def int_nacl_atomic_fence : Intrinsic<[], [llvm_i32_ty],
+    [IntrReadWriteArgMem]>;
 // @LOCALMOD-END
 
 //===----------------------------------------------------------------------===//
diff --git a/include/llvm/IR/NaClAtomicIntrinsics.h b/include/llvm/IR/NaClAtomicIntrinsics.h
new file mode 100644
index 0000000000..680c644024
--- /dev/null
+++ b/include/llvm/IR/NaClAtomicIntrinsics.h
@@ -0,0 +1,110 @@
+//===-- llvm/IR/NaClAtomicIntrinsics.h - NaCl Atomic Intrinsics -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file describes atomic intrinsic functions that are specific to NaCl.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_NACL_ATOMIC_INTRINSICS_H
+#define LLVM_IR_NACL_ATOMIC_INTRINSICS_H
+
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/Support/Compiler.h"
+#include <cstddef>
+
+namespace llvm {
+
+namespace NaCl {
+
+static const size_t NumAtomicIntrinsics = 5;
+static const size_t NumAtomicIntrinsicOverloadTypes = 4;
+static const size_t MaxAtomicIntrinsicsParameters = 5;
+
+/// Describe all the atomic intrinsics and their type signature. Most
+/// can be overloaded on a type.
+class AtomicIntrinsics {
+public:
+  enum ParamType {
+    NoP, /// No parameter.
+    Int, /// Overloaded.
+    Ptr, /// Overloaded.
+    RMW, /// Atomic RMW operation type.
+    Mem  /// Memory order.
+  };
+
+  struct AtomicIntrinsic {
+    Type *OverloadedType;
+    Intrinsic::ID ID : 16;
+    uint8_t Overloaded : 1;
+    uint8_t NumParams : 7;
+    uint8_t ParamType[MaxAtomicIntrinsicsParameters];
+
+    Function *getDeclaration(Module *M) const {
+      // The atomic intrinsic can be overloaded on zero or one type,
+      // which is needed to create the function's declaration.
+      return Intrinsic::getDeclaration(
+          M, ID, ArrayRef<Type *>(&OverloadedType, Overloaded ? 1 : 0));
+    }
+  };
+
+  AtomicIntrinsics(LLVMContext &C);
+  ~AtomicIntrinsics() {}
+
+  typedef ArrayRef<AtomicIntrinsic> View;
+
+  /// The following three methods give access to atomic intrinsics, or a
+  /// subset of them, and allows iteration through them.
+  View allIntrinsicsAndOverloads() const;
+  View overloadsFor(Intrinsic::ID ID) const;
+  const AtomicIntrinsic *find(Intrinsic::ID ID, Type *OverloadedType) const;
+
+private:
+  AtomicIntrinsic I[NumAtomicIntrinsics][NumAtomicIntrinsicOverloadTypes];
+
+  AtomicIntrinsics() LLVM_DELETED_FUNCTION;
+  AtomicIntrinsics(const AtomicIntrinsics &) LLVM_DELETED_FUNCTION;
+  AtomicIntrinsics &operator=(const AtomicIntrinsics &) LLVM_DELETED_FUNCTION;
+};
+
+/// Operations that can be represented by the @llvm.nacl.atomic.rmw
+/// intrinsic.
+///
+/// Do not reorder these values: their order offers forward
+/// compatibility of bitcode targeted to NaCl.
+enum AtomicRMWOperation {
+  AtomicInvalid = 0, // Invalid, keep first.
+  AtomicAdd,
+  AtomicSub,
+  AtomicOr,
+  AtomicAnd,
+  AtomicXor,
+  AtomicExchange,
+  AtomicNum // Invalid, keep last.
+};
+
+/// Memory orderings supported by C11/C++11.
+///
+/// Do not reorder these values: their order offers forward
+/// compatibility of bitcode targeted to NaCl.
+enum MemoryOrder {
+  MemoryOrderInvalid = 0, // Invalid, keep first.
+  MemoryOrderRelaxed,
+  MemoryOrderConsume,
+  MemoryOrderAcquire,
+  MemoryOrderRelease,
+  MemoryOrderAcquireRelease,
+  MemoryOrderSequentiallyConsistent,
+  MemoryOrderNum // Invalid, keep last.
+};
+
+} // End NaCl namespace
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index 73622fa7c0..e17bfa5947 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -293,13 +293,14 @@ void initializeFlattenGlobalsPass(PassRegistry&);
 void initializeGlobalCleanupPass(PassRegistry&);
 void initializeInsertDivideCheckPass(PassRegistry&);
 void initializeNaClCcRewritePass(PassRegistry&);
-void initializePNaClABIVerifyModulePass(PassRegistry&);
 void initializePNaClABIVerifyFunctionsPass(PassRegistry&);
+void initializePNaClABIVerifyModulePass(PassRegistry&);
 void initializePromoteI1OpsPass(PassRegistry&);
 void initializePromoteIntegersPass(PassRegistry&);
 void initializeReplacePtrsWithIntsPass(PassRegistry&);
 void initializeResolveAliasesPass(PassRegistry&);
 void initializeResolvePNaClIntrinsicsPass(PassRegistry&);
+void initializeRewriteAtomicsPass(PassRegistry&);
 void initializeRewriteLLVMIntrinsicsPass(PassRegistry&);
 void initializeRewritePNaClLibraryCallsPass(PassRegistry&);
 void initializeStripAttributesPass(PassRegistry&);
diff --git a/include/llvm/Transforms/NaCl.h b/include/llvm/Transforms/NaCl.h
index 43adb237dd..ec1a54aaa8 100644
--- a/include/llvm/Transforms/NaCl.h
+++ b/include/llvm/Transforms/NaCl.h
@@ -22,30 +22,31 @@ class PassManager;
 class Use;
 class Value;
 
+BasicBlockPass *createExpandGetElementPtrPass();
+BasicBlockPass *createPromoteI1OpsPass();
+FunctionPass *createExpandConstantExprPass();
+FunctionPass *createExpandStructRegsPass();
+FunctionPass *createInsertDivideCheckPass();
+FunctionPass *createPromoteIntegersPass();
+FunctionPass *createResolvePNaClIntrinsicsPass();
 ModulePass *createAddPNaClExternalDeclsPass();
 ModulePass *createCanonicalizeMemIntrinsicsPass();
 ModulePass *createExpandArithWithOverflowPass();
 ModulePass *createExpandByValPass();
-FunctionPass *createExpandConstantExprPass();
 ModulePass *createExpandCtorsPass();
-BasicBlockPass *createExpandGetElementPtrPass();
 ModulePass *createExpandSmallArgumentsPass();
-FunctionPass *createExpandStructRegsPass();
-ModulePass *createExpandTlsPass();
 ModulePass *createExpandTlsConstantExprPass();
+ModulePass *createExpandTlsPass();
 ModulePass *createExpandVarArgsPass();
 ModulePass *createFlattenGlobalsPass();
 ModulePass *createGlobalCleanupPass();
-BasicBlockPass *createPromoteI1OpsPass();
-FunctionPass *createPromoteIntegersPass();
 ModulePass *createReplacePtrsWithIntsPass();
 ModulePass *createResolveAliasesPass();
-FunctionPass *createResolvePNaClIntrinsicsPass();
+ModulePass *createRewriteAtomicsPass();
 ModulePass *createRewriteLLVMIntrinsicsPass();
 ModulePass *createRewritePNaClLibraryCallsPass();
 ModulePass *createStripAttributesPass();
 ModulePass *createStripMetadataPass();
-FunctionPass *createInsertDivideCheckPass();
 
 void PNaClABISimplifyAddPreOptPasses(PassManager &PM);
 void PNaClABISimplifyAddPostOptPasses(PassManager &PM);