PNaCl: Impl the other atomicrmw operations: nand, max, min, umax, and umin.

lib/Transforms/NaCl/RewriteAtomics.cpp

 //===- RewriteAtomics.cpp - Stabilize instructions used for concurrency ---===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass encodes atomics, volatiles and fences using NaCl intrinsics
 // instead of LLVM's regular IR instructions.
 //
 // All of the above are transformed into one of the
 // @llvm.nacl.atomic.* intrinsics.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Twine.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/NaClAtomicIntrinsics.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/NaCl.h"
 #include <climits>
 #include <string>
 
@@ skipping 40 matching lines @@
         ModifiedModule(false) {}
   ~AtomicVisitor() {}
   bool modifiedModule() const { return ModifiedModule; }
 
   void visitLoadInst(LoadInst &I);
   void visitStoreInst(StoreInst &I);
   void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I);
   void visitAtomicRMWInst(AtomicRMWInst &I);
   void visitFenceInst(FenceInst &I);
 
+  void rewriteDelayedAtomics();
+  void rewriteDelayedRMWNandInst(AtomicRMWInst *I);
+
 private:
   Module &M;
   LLVMContext &C;
   const DataLayout TD;
   NaCl::AtomicIntrinsics AI;
   bool ModifiedModule;
 
+  /// We can't modify the CFG whilst visiting the instructions within.
+  /// Thus we collect all of those that need such to rewrite, waiting until
+  /// after we've finished visiting the whole module. After InstVisitor::visit
+  /// completes, RewriteAtomics calls rewriteDelayedAtomics to rewrite these
+  /// instructions.
+  SmallVector<AtomicRMWInst*, 64> DelayedAtomics;
+
   AtomicVisitor() LLVM_DELETED_FUNCTION;
   AtomicVisitor(const AtomicVisitor &) LLVM_DELETED_FUNCTION;
   AtomicVisitor &operator=(const AtomicVisitor &) LLVM_DELETED_FUNCTION;
 
   /// Create an integer constant holding a NaCl::MemoryOrder that can be
   /// passed as an argument to one of the @llvm.nacl.atomic.*
   /// intrinsics. This function may strengthen the ordering initially
   /// specified by the instruction \p I for stability purpose.
   template <class Instruction>
   ConstantInt *freezeMemoryOrder(const Instruction &I, AtomicOrdering O) const;
   std::pair<ConstantInt *, ConstantInt *>
   freezeMemoryOrder(const AtomicCmpXchgInst &I, AtomicOrdering S,
                     AtomicOrdering F) const;
 
   /// Sanity-check that instruction \p I which has pointer and value
   /// parameters have matching sizes \p BitSize for the type-pointed-to
   /// and the value's type \p T.
   void checkSizeMatchesType(const Instruction &I, unsigned BitSize,
                             const Type *T) const;
 
   /// Verify that loads and stores are at least naturally aligned. Use
   /// byte alignment because converting to bits could truncate the
   /// value.
   void checkAlignment(const Instruction &I, unsigned ByteAlignment,
                       unsigned ByteSize) const;
 
   /// Create a cast before Instruction \p I from \p Src to \p Dst with \p Name.
   CastInst *createCast(Instruction &I, Value *Src, Type *Dst, Twine Name) const;
+  /// Get the cast operation needed to cast Instruction \p I from \p Src to \p Dst
+  Instruction::CastOps castOp(Instruction &I, Value *Src, Type *Dst, Twine Name) const;

[JF, 2015/02/13 17:14:26]

Lines > 80.

 
   /// Try to find the atomic intrinsic of with its \p ID and \OverloadedType.
   /// Report fatal error on failure.
   const NaCl::AtomicIntrinsics::AtomicIntrinsic *
   findAtomicIntrinsic(const Instruction &I, Intrinsic::ID ID,
                       Type *OverloadedType) const;
 
   /// Helper function which rewrites a single instruction \p I to a
   /// particular \p intrinsic with overloaded type \p OverloadedType,
   /// and argument list \p Args. Will perform a bitcast to the proper \p
@@ skipping 34 matching lines @@
 
 char RewriteAtomics::ID = 0;
 INITIALIZE_PASS(RewriteAtomics, "nacl-rewrite-atomics",
                 "rewrite atomics, volatiles and fences into stable "
                 "@llvm.nacl.atomics.* intrinsics",
                 false, false)
 
 bool RewriteAtomics::runOnModule(Module &M) {
   AtomicVisitor AV(M, *this);
   AV.visit(M);
+  AV.rewriteDelayedAtomics();
   return AV.modifiedModule();
 }
 
 template <class Instruction>
 ConstantInt *AtomicVisitor::freezeMemoryOrder(const Instruction &I,
                                               AtomicOrdering O) const {
   NaCl::MemoryOrder AO = NaCl::MemoryOrderInvalid;
 
   // TODO Volatile load/store are promoted to sequentially consistent
   //      for now. We could do something weaker.
@@ skipping 56 matching lines @@
                                    unsigned ByteSize) const {
   if (ByteAlignment < ByteSize)
     report_fatal_error("atomic load/store must be at least naturally aligned, "
                        "got " +
                        Twine(ByteAlignment) + ", bytes expected at least " +
                        Twine(ByteSize) + " bytes, in: " + ToStr(I));
 }
 
 CastInst *AtomicVisitor::createCast(Instruction &I, Value *Src, Type *Dst,
                                     Twine Name) const {
+  const auto Op = castOp(I, Src, Dst, Name);
+  return CastInst::Create(Op, Src, Dst, Name, &I);
+}
+Instruction::CastOps AtomicVisitor::castOp(Instruction &I,
+                                           Value *Src, Type *Dst,
+                                           Twine Name) const {
   Type *SrcT = Src->getType();
   Instruction::CastOps Op = SrcT->isIntegerTy() && Dst->isPointerTy()
                                 ? Instruction::IntToPtr
                                 : SrcT->isPointerTy() && Dst->isIntegerTy()
                                       ? Instruction::PtrToInt
                                       : Instruction::BitCast;
   if (!CastInst::castIsValid(Op, Src, Dst))
     report_fatal_error("cannot emit atomic instruction while converting type " +
                        ToStr(*SrcT) + " to " + ToStr(*Dst) + " for " + Name +
                        " in " + ToStr(I));
-  return CastInst::Create(Op, Src, Dst, Name, &I);
+  return Op;
 }
 
 const NaCl::AtomicIntrinsics::AtomicIntrinsic *
 AtomicVisitor::findAtomicIntrinsic(const Instruction &I, Intrinsic::ID ID,
                                    Type *OverloadedType) const {
   if (const NaCl::AtomicIntrinsics::AtomicIntrinsic *Intrinsic =
           AI.find(ID, OverloadedType))
     return Intrinsic;
   report_fatal_error("unsupported atomic instruction: " + ToStr(I));
 }
@@ skipping 83 matching lines @@
 void AtomicVisitor::visitAtomicRMWInst(AtomicRMWInst &I) {
   NaCl::AtomicRMWOperation Op;
   switch (I.getOperation()) {
   default: report_fatal_error("unsupported atomicrmw operation: " + ToStr(I));
   case AtomicRMWInst::Add: Op = NaCl::AtomicAdd; break;
   case AtomicRMWInst::Sub: Op = NaCl::AtomicSub; break;
   case AtomicRMWInst::And: Op = NaCl::AtomicAnd; break;
   case AtomicRMWInst::Or:  Op = NaCl::AtomicOr;  break;
   case AtomicRMWInst::Xor: Op = NaCl::AtomicXor; break;
   case AtomicRMWInst::Xchg: Op = NaCl::AtomicExchange; break;
+
+  // Rewrite these ops using a loop:
+  case AtomicRMWInst::Nand:
+  case AtomicRMWInst::Max:
+  case AtomicRMWInst::Min:
+  case AtomicRMWInst::UMax:
+  case AtomicRMWInst::UMin:
+    DelayedAtomics.push_back(&I);
+    return;
   }
   PointerHelper<AtomicRMWInst> PH(*this, I);
   const NaCl::AtomicIntrinsics::AtomicIntrinsic *Intrinsic =
       findAtomicIntrinsic(I, Intrinsic::nacl_atomic_rmw, PH.PET);
   checkSizeMatchesType(I, PH.BitSize, I.getValOperand()->getType());
   Value *Args[] = {ConstantInt::get(Type::getInt32Ty(C), Op), PH.P,
                    I.getValOperand(), freezeMemoryOrder(I, I.getOrdering())};
   replaceInstructionWithIntrinsicCall(I, Intrinsic, PH.OriginalPET, PH.PET,
                                       Args);
 }
@@ skipping 51 matching lines @@
         findAtomicIntrinsic(I, Intrinsic::nacl_atomic_fence_all, T);
     replaceInstructionWithIntrinsicCall(I, Intrinsic, T, T,
                                         ArrayRef<Value *>());
   } else {
     const NaCl::AtomicIntrinsics::AtomicIntrinsic *Intrinsic =
         findAtomicIntrinsic(I, Intrinsic::nacl_atomic_fence, T);
     Value *Args[] = {freezeMemoryOrder(I, I.getOrdering())};
     replaceInstructionWithIntrinsicCall(I, Intrinsic, T, T, Args);
   }
 }
+void AtomicVisitor::rewriteDelayedAtomics() {
+  for(auto& I : DelayedAtomics) {
+    rewriteDelayedRMWNandInst(I);
+    I->eraseFromParent();
+  }
+}
+
+/// Lifted from X86AtomicExpandPass:

[JF, 2015/02/13 17:14:26]

I like the approach overall, but since LLVM already contains code to do this I'd
rather reuse it directly than copy it in. Do you think you could instead make
X86AtomicExpandPass a utility that's usable for non-x86 code?

I would do this change in LLVM itself, and PNaCl will soon contain it (we're
trying to be ~2 weeks behind top-of-tree, sync'ing at "stable" points). We can
also cherry-pick it if we want to get the change faster, but in the end it's
better for this to be in LLVM rather than PNaCl.

I'd be happy to help with the code reviews in upstream LLVM. The process is
similar, but uses Phabricator instead.

+/// Emit IR to implement the given atomicrmw operation on values in registers,
+/// returning the new value.
+static Value *performAtomicOp(AtomicRMWInst::BinOp Op, IRBuilder<> &Builder,
+                              Value *Loaded, Value *Inc) {
+  Value *NewVal;
+  switch (Op) {
+  case AtomicRMWInst::Xchg:
+  case AtomicRMWInst::Add:
+  case AtomicRMWInst::Sub:
+  case AtomicRMWInst::And:
+  case AtomicRMWInst::Or:
+    llvm_unreachable("Op not handled by AtomicVisitor::visitAtomicRMWInst!");
+  case AtomicRMWInst::Nand:
+    return Builder.CreateNot(Builder.CreateAnd(Loaded, Inc), "new");
+  case AtomicRMWInst::Max:
+    NewVal = Builder.CreateICmpSGT(Loaded, Inc);
+    return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
+  case AtomicRMWInst::Min:
+    NewVal = Builder.CreateICmpSLE(Loaded, Inc);
+    return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
+  case AtomicRMWInst::UMax:
+    NewVal = Builder.CreateICmpUGT(Loaded, Inc);
+    return  Builder.CreateSelect(NewVal, Loaded, Inc, "new");
+  case AtomicRMWInst::UMin:
+    NewVal = Builder.CreateICmpULE(Loaded, Inc);
+    return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
+  default:
+    break;
+  }
+  llvm_unreachable("Unknown atomic op");
+}
+
+void AtomicVisitor::rewriteDelayedRMWNandInst(AtomicRMWInst *I) {
+  ModifiedModule = true;
+
+  // The following was lifted from X86AtomicExpandPass and modified to create
+  // PNaCl variety atomics.
+  BasicBlock *BB = I->getParent();
+  Function *F = BB->getParent();
+  LLVMContext &Ctx = F->getContext();
+  const auto Order = freezeMemoryOrder(*I, I->getOrdering());
+
+  PointerHelper<AtomicRMWInst> PH(*this, *I);
+  // LLVM permits only integer atomicrmw, so our PH should never create a cast.
+  assert(PH.PET == PH.OriginalPET && "atomicrmw on non-integers?");
+
+  BasicBlock *ExitBB = BB->splitBasicBlock(I, "atomicrmw.end");
+  BasicBlock *LoopBB =  BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);
+
+  // Get the debug location from I:
+  IRBuilder<> Builder(I);
+
+  // The split call above "helpfully" added a branch at the end of BB (to the
+  // wrong place), but we want a load. It's easiest to just remove
+  // the branch entirely.
+  std::prev(BB->end())->eraseFromParent();
+  Builder.SetInsertPoint(BB);
+  LoadInst *InitLoaded = Builder.CreateLoad(PH.P);
+  InitLoaded->setAlignment(I->getType()->getPrimitiveSizeInBits());
+  Builder.CreateBr(LoopBB);
+  // Start the main loop block now that we've taken care of the preliminaries.
+  Builder.SetInsertPoint(LoopBB);
+  PHINode *Loaded = Builder.CreatePHI(PH.PET, 2, "loaded");
+  Loaded->addIncoming(InitLoaded, BB);
+
+  Value *NewVal =
+    performAtomicOp(I->getOperation(), Builder, Loaded, I->getValOperand());
+
+  Value *XChgArgs[] = {ConstantInt::get(Type::getInt32Ty(Ctx), NaCl::AtomicExchange),
+                       PH.P, NewVal, Order};
+  const NaCl::AtomicIntrinsics::AtomicIntrinsic *Intrinsic =
+      findAtomicIntrinsic(*I, Intrinsic::nacl_atomic_rmw, PH.PET);
+
+  CallInst *CmpXchg = Builder.CreateCall(Intrinsic->getDeclaration(&M),
+                                         XChgArgs);
+  Loaded->addIncoming(CmpXchg, LoopBB);
+  Instruction *Cmp = cast<Instruction>(Builder.CreateICmpEQ(CmpXchg, NewVal));
+  Builder.CreateCondBr(Cmp, ExitBB, LoopBB);
+  // End lift.
+
+  CmpXchg->takeName(I);
+  I->replaceAllUsesWith(CmpXchg);
+}
 
 ModulePass *llvm::createRewriteAtomicsPass() { return new RewriteAtomics(); }