Insert denominator zero checks for NaCl

This IR pass for ARM inserts a comparison and a branch to trap if the
denominator of a DIV or REM instruction is zero.  This makes ARM fault
identically to x86 in this case.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=2833
R=eliben@chromium.org

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

8 files changed, 320 insertions, 0 deletions

diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h
index 9bcc8bf2a0..1f81c9770e 100644
--- a/include/llvm/InitializePasses.h
+++ b/include/llvm/InitializePasses.h
@@ -286,6 +286,7 @@ void initializeExpandTlsPass(PassRegistry&);
 void initializeExpandVarArgsPass(PassRegistry&);
 void initializeFlattenGlobalsPass(PassRegistry&);
 void initializeGlobalCleanupPass(PassRegistry&);
+void initializeInsertDivideCheckPass(PassRegistry&);
 void initializeNaClCcRewritePass(PassRegistry&);
 void initializePNaClABIVerifyModulePass(PassRegistry&);
 void initializePNaClABIVerifyFunctionsPass(PassRegistry&);
diff --git a/include/llvm/Transforms/NaCl.h b/include/llvm/Transforms/NaCl.h
index ba765c1c21..edd641e901 100644
--- a/include/llvm/Transforms/NaCl.h
+++ b/include/llvm/Transforms/NaCl.h
@@ -30,6 +30,7 @@ ModulePass *createFlattenGlobalsPass();
 ModulePass *createGlobalCleanupPass();
 ModulePass *createResolveAliasesPass();
 ModulePass *createStripMetadataPass();
+FunctionPass *createInsertDivideCheckPass();
 
 Instruction *PhiSafeInsertPt(Use *U);
 void PhiSafeReplaceUses(Use *U, Value *NewVal);
diff --git a/lib/Target/ARM/ARMTargetMachine.cpp b/lib/Target/ARM/ARMTargetMachine.cpp
index c02e981e54..499f974b96 100644
--- a/lib/Target/ARM/ARMTargetMachine.cpp
+++ b/lib/Target/ARM/ARMTargetMachine.cpp
@@ -20,6 +20,9 @@
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Target/TargetOptions.h"
+// @LOCALMOD-START
+#include "llvm/Transforms/NaCl.h"
+// @LOCALMOD-END
 #include "llvm/Transforms/Scalar.h"
 using namespace llvm;
 
@@ -141,6 +144,9 @@ public:
   virtual bool addPreRegAlloc();
   virtual bool addPreSched2();
   virtual bool addPreEmitPass();
+// @LOCALMOD-START
+  virtual void addIRPasses();
+// @LOCALMOD-END
 };
 } // namespace
 
@@ -229,6 +235,15 @@ bool ARMPassConfig::addPreEmitPass() {
   return true;
 }
 
+// @LOCALMOD-START
+void ARMPassConfig::addIRPasses() {
+  if (getARMSubtarget().isTargetNaCl()) {
+    addPass(createInsertDivideCheckPass());
+  }
+  TargetPassConfig::addIRPasses();
+}
+// @LOCALMOD-END
+
 bool ARMBaseTargetMachine::addCodeEmitter(PassManagerBase &PM,
                                           JITCodeEmitter &JCE) {
   // Machine code emitter pass for ARM.
diff --git a/lib/Transforms/NaCl/CMakeLists.txt b/lib/Transforms/NaCl/CMakeLists.txt
index 47d51f2940..103c4920e7 100644
--- a/lib/Transforms/NaCl/CMakeLists.txt
+++ b/lib/Transforms/NaCl/CMakeLists.txt
@@ -7,6 +7,7 @@ add_llvm_library(LLVMNaClTransforms
   ExpandTlsConstantExpr.cpp
   ExpandUtils.cpp
   ExpandVarArgs.cpp
+  InsertDivideCheck.cpp
   FlattenGlobals.cpp
   GlobalCleanup.cpp
   StripMetadata.cpp
diff --git a/lib/Transforms/NaCl/InsertDivideCheck.cpp b/lib/Transforms/NaCl/InsertDivideCheck.cpp
new file mode 100644
index 0000000000..f1deae618f
--- /dev/null
+++ b/lib/Transforms/NaCl/InsertDivideCheck.cpp
@@ -0,0 +1,112 @@
+//===- InsertDivideCheck.cpp - Add divide by zero checks ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass adds a check for divide by zero before every integer DIV or REM.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "add-divide-check"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Transforms/NaCl.h"
+
+using namespace llvm;
+
+namespace {
+  class InsertDivideCheck : public FunctionPass {
+  public:
+    static char ID;
+    InsertDivideCheck() : FunctionPass(ID) {
+      initializeInsertDivideCheckPass(*PassRegistry::getPassRegistry());
+    }
+
+    bool runOnFunction(Function &F);
+  };
+}
+
+static BasicBlock *CreateTrapBlock(Function &F, DebugLoc dl) {
+  BasicBlock *TrapBlock = BasicBlock::Create(F.getContext(), "divrem.by.zero",
+                                             &F);
+  Value *TrapFn = Intrinsic::getDeclaration(F.getParent(), Intrinsic::trap);
+  CallInst::Create(TrapFn, "", TrapBlock)->setDebugLoc(dl);
+  (new UnreachableInst(F.getContext(), TrapBlock))->setDebugLoc(dl);
+  return TrapBlock;
+}
+
+bool InsertDivideCheck::runOnFunction(Function &F) {
+  SmallPtrSet<Instruction*, 8> GuardedDivs;
+  // If the pass finds a DIV/REM that needs to be checked for zero denominator,
+  // it will insert a new "trap" block, and split the block that contains the
+  // DIV/REM into two blocks.  The new BasicBlocks are added after the current
+  // BasicBlock, so that if there is more than one DIV/REM in the same block,
+  // all are visited.
+  for (Function::iterator I = F.begin(); I != F.end(); I++) {
+    BasicBlock *BB = I;
+
+    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
+         BI != BE; BI++) {
+      BinaryOperator *DivInst = dyn_cast<BinaryOperator>(BI);
+      if (!DivInst || (GuardedDivs.count(DivInst) != 0))
+        continue;
+      unsigned Opcode = DivInst->getOpcode();
+      if (Opcode != Instruction::SDiv && Opcode != Instruction::UDiv &&
+          Opcode != Instruction::SRem && Opcode != Instruction::URem)
+        continue;
+      Value *Denominator = DivInst->getOperand(1);
+      if (!Denominator->getType()->isIntegerTy())
+        continue;
+      DebugLoc dl = DivInst->getDebugLoc();
+      if (ConstantInt *DenomConst = dyn_cast<ConstantInt>(Denominator)) {
+        // Divides by constants do not need a denominator test.
+        if (DenomConst->isZero()) {
+          // For explicit divides by zero, insert a trap before DIV/REM
+          Value *TrapFn = Intrinsic::getDeclaration(F.getParent(),
+                                                    Intrinsic::trap);
+          CallInst::Create(TrapFn, "", DivInst)->setDebugLoc(dl);
+        }
+        continue;
+      }
+      // Create a trap block.
+      BasicBlock *TrapBlock = CreateTrapBlock(F, dl);
+      // Move instructions in BB from DivInst to BB's end to a new block.
+      BasicBlock *Successor = BB->splitBasicBlock(BI, "guarded.divrem");
+      // Remove the unconditional branch inserted by splitBasicBlock.
+      BB->getTerminator()->eraseFromParent();
+      // Remember that DivInst was already processed, so that when we process
+      // inserted blocks later, we do not attempt to again guard it.
+      GuardedDivs.insert(DivInst);
+      // Compare the denominator with zero.
+      Value *Zero = ConstantInt::get(Denominator->getType(), 0);
+      Value *DenomIsZero = new ICmpInst(*BB, ICmpInst::ICMP_EQ, Denominator,
+                                        Zero, "");
+      // Put in a condbranch to the trap block.
+      BranchInst::Create(TrapBlock, Successor, DenomIsZero, BB);
+      // BI is invalidated when we split.  Stop the BasicBlock iterator.
+      break;
+    }
+  }
+
+  return false;
+}
+
+char InsertDivideCheck::ID = 0;
+INITIALIZE_PASS(InsertDivideCheck, "insert-divide-check",
+                "Insert divide by zero checks", false, false)
+
+FunctionPass *llvm::createInsertDivideCheckPass() {
+  return new InsertDivideCheck();
+}
diff --git a/test/NaCl/ARM/divrem-guards-complex.ll b/test/NaCl/ARM/divrem-guards-complex.ll
new file mode 100644
index 0000000000..ba66ab4b31
--- /dev/null
+++ b/test/NaCl/ARM/divrem-guards-complex.ll
@@ -0,0 +1,85 @@
+; RUN: opt < %s -insert-divide-check -S | FileCheck -check-prefix=OPT %s
+
+declare void @foo()
+
+; Check for multiple divs that occur one block.
+define i32 @twodivs_one_block(i32 %x, i32 %y) #0 {
+entry:
+  call void @foo()
+  br label %divblock
+divblock:
+  %div1 = sdiv i32 %x, %y
+  %div2 = sdiv i32 %x, %y
+; OPT: %0 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %0, label %divrem.by.zero, label %guarded.divrem
+; OPT: guarded.divrem:
+; OPT-NEXT: sdiv
+; OPT: %1 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %1, label %divrem.by.zero1, label %guarded.divrem2
+; OPT: guarded.divrem2:
+; OPT-NEXT: sdiv
+; OPT-NEXT: add
+; OPT: divrem.by.zero:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+; OPT: divrem.by.zero1:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+  %sum = add i32 %div1, %div2
+  ret i32 %sum
+}
+
+define i32 @twodivs_three_blocks(i32 %x, i32 %y) #0 {
+entry:
+  call void @foo()
+  br label %divblock
+divblock:
+  %div1 = sdiv i32 %x, %y
+; OPT: %0 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %0, label %divrem.by.zero, label %guarded.divrem
+; OPT: guarded.divrem:
+; OPT-NEXT: sdiv
+; OPT-NEXT: br label %exitblock
+  br label %exitblock
+exitblock:
+  call void @foo()
+  %div2 = sdiv i32 %x, %y
+; OPT: %1 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %1, label %divrem.by.zero1, label %guarded.divrem2
+; OPT: guarded.divrem2:
+; OPT-NEXT: sdiv
+; OPT-NEXT: add
+; OPT: divrem.by.zero:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+; OPT: divrem.by.zero1:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+  %sum = add i32 %div1, %div2
+  ret i32 %sum
+}
+
+; Check for divs that occur in blocks with multiple predecessors.
+define i32 @onediv_two_predecessors(i32 %x, i32 %y) #0 {
+entry:
+  call void @foo()
+  br label %divblock
+divblock:
+  %x1 = phi i32 [%x, %entry], [%x2, %divblock]
+  %div1 = sdiv i32 %x, %y
+; OPT: %0 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %0, label %divrem.by.zero, label %guarded.divrem
+; OPT: guarded.divrem:
+; OPT-NEXT: sdiv
+; OPT-NEXT: sub
+; OPT: divrem.by.zero:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+  %x2 = sub i32 %x1, 1
+  %p = icmp ne i32 %x2, 0
+  br i1 %p, label %divblock, label %exitblock
+exitblock:
+  call void @foo()
+  ret i32 %div1
+}
+
diff --git a/test/NaCl/ARM/divrem-guards.ll b/test/NaCl/ARM/divrem-guards.ll
new file mode 100644
index 0000000000..822ae848d4
--- /dev/null
+++ b/test/NaCl/ARM/divrem-guards.ll
@@ -0,0 +1,104 @@
+; RUN: opt < %s -insert-divide-check -S | FileCheck -check-prefix=OPT %s
+; RUN: llc -mtriple=armv7-unknown-nacl -sfi-branch -filetype=obj %s -o - \
+; RUN:  | llvm-objdump -disassemble -triple armv7 -mattr=+nacl-trap - \
+; RUN:  | FileCheck -check-prefix=ARM %s
+
+
+; Check for all four operators that need guards.
+define i32 @mysdiv(i32 %x, i32 %y) #0 {
+entry:
+  %div1 = sdiv i32 %x, %y
+; OPT: %0 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %0, label %divrem.by.zero, label %guarded.divrem
+; OPT: guarded.divrem:
+; OPT-NEXT: sdiv
+; OPT-NEXT: ret
+; OPT: divrem.by.zero:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+; ARM: cmp r1, #0
+; ARM-NEXT: beq
+  ret i32 %div1
+; ARM: f0 de fe e7
+}
+
+define i32 @myudiv(i32 %x, i32 %y) #0 {
+entry:
+  %div1 = udiv i32 %x, %y
+; OPT: %0 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %0, label %divrem.by.zero, label %guarded.divrem
+; OPT: guarded.divrem:
+; OPT-NEXT: udiv
+; OPT-NEXT: ret
+; OPT: divrem.by.zero:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+; ARM: cmp r1, #0
+; ARM-NEXT: beq
+  ret i32 %div1
+; ARM: f0 de fe e7
+}
+
+define i32 @mysrem(i32 %x, i32 %y) #0 {
+entry:
+  %rem1 = srem i32 %x, %y
+; OPT: %0 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %0, label %divrem.by.zero, label %guarded.divrem
+; OPT: guarded.divrem:
+; OPT-NEXT: srem
+; OPT-NEXT: ret
+; OPT: divrem.by.zero:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+; ARM: cmp r1, #0
+; ARM-NEXT: beq
+  ret i32 %rem1
+; ARM: f0 de fe e7
+}
+
+define i32 @myurem(i32 %x, i32 %y) #0 {
+entry:
+  %rem1 = urem i32 %x, %y
+; OPT: %0 = icmp eq i32 %y, 0
+; OPT-NEXT: br i1 %0, label %divrem.by.zero, label %guarded.divrem
+; OPT: guarded.divrem:
+; OPT-NEXT: urem
+; OPT-NEXT: ret
+; OPT: divrem.by.zero:
+; OPT-NEXT: call void @llvm.trap()
+; OPT-NEXT: unreachable
+; ARM: cmp r1, #0
+; ARM-NEXT: beq
+  ret i32 %rem1
+; ARM: f0 de fe e7
+}
+
+; Divides by non-zero constants should not be guarded.
+define i32 @mysdiv_const(i32 %x) #0 {
+entry:
+  %div1 = sdiv i32 %x, 10
+; OPT-NOT: icmp
+; OPT-NOT: br
+; OPT-NOT: guarded.divrem:
+; OPT-NOT: divrem.by.zero:
+; OPT-NOT: call void @llvm.trap()
+; OPT-NOT: unreachable
+; ARM-NOT: cmp r1, #0
+; ARM-NOT: f0 de fe e7
+  ret i32 %div1
+}
+
+; Divides by explicit zero should prefixed by a trap.
+define i32 @mysdiv_zero(i32 %x) #0 {
+entry:
+  %div1 = sdiv i32 %x, 0
+; OPT-NOT: guarded.divrem:
+; OPT-NOT: divrem.by.zero:
+; OPT: call void @llvm.trap()
+; OPT-NEXT: sdiv
+; ARM-NOT: cmp r1, #0
+; ARM: f0 de fe e7
+  ret i32 %div1
+}
+
+attributes #0 = { nounwind }
diff --git a/tools/opt/opt.cpp b/tools/opt/opt.cpp
index 26a5e4a3c1..6932cb8b0f 100644
--- a/tools/opt/opt.cpp
+++ b/tools/opt/opt.cpp
@@ -586,6 +586,7 @@ int main(int argc, char **argv) {
   initializeExpandVarArgsPass(Registry);
   initializeFlattenGlobalsPass(Registry);
   initializeGlobalCleanupPass(Registry);
+  initializeInsertDivideCheckPass(Registry);
   initializePNaClABIVerifyFunctionsPass(Registry);
   initializePNaClABIVerifyModulePass(Registry);
   initializeResolveAliasesPass(Registry);