Insert denominator zero checks for NaCl

lib/Target/ARM/ARMNaClDivideCheck.cpp

Index: lib/Target/ARM/ARMNaClDivideCheck.cpp
diff --git a/lib/Target/ARM/ARMNaClDivideCheck.cpp b/lib/Target/ARM/ARMNaClDivideCheck.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..c163a57f35802e5f7f0041aa64bc53a5d29e5b7a
--- /dev/null
+++ b/lib/Target/ARM/ARMNaClDivideCheck.cpp
@@ -0,0 +1,119 @@
+//===- ARMNaClDivideCheck.cpp - Add divide by zero checks ----------------===//

[Mark Seaborn, 2013/05/03 21:25:36]

Add 1 more '-' to line up right-hand edge

[sehr, 2013/05/03 23:29:05]

Done.

+//
+//                     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.

[eliben, 2013/05/03 21:18:55]

Once this CL is committed, we can check the performance implication when running
spec with fastisel. If it's not negligible, we should try placing the check
*after* the div, or fixing the register allocator, whichever is easier ;-)

[sehr, 2013/05/03 23:29:05]

I know fixing it here is simpler a priori.  But on ARMs that have to use
software DIV/REM, it probably won't make any difference anyway, since we have to
call a function to do the DIV/REM, which will imply a spill-reload pair.  So I
relent.

+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "add-divide-check"
+#include "ARM.h"
+#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/Support/CFG.h"
+
+using namespace llvm;
+
+namespace llvm {
+void initializeARMNaClDivideCheckPass(PassRegistry&);
+}
+
+namespace {
+

[Mark Seaborn, 2013/05/03 21:25:36]

Remove this empty line

[sehr, 2013/05/03 23:29:05]

Done.

+  class ARMNaClDivideCheck : public FunctionPass {
+

[Mark Seaborn, 2013/05/03 21:25:36]

Remove this empty line

[sehr, 2013/05/03 23:29:05]

Done.

+  public:
+    static char ID;
+    ARMNaClDivideCheck() : FunctionPass(ID) {
+      initializeARMNaClDivideCheckPass(*PassRegistry::getPassRegistry());
+    }
+
+    bool runOnFunction(Function &F);
+  };
+}
+
+static BasicBlock *CreateTrapBlock(Function &F) {
+  BasicBlock *TrapBlock = BasicBlock::Create(F.getContext(), "divrem.by.zero",
+                                             &F);
+  Value *TrapFn = Intrinsic::getDeclaration(F.getParent(), Intrinsic::trap);
+  CallInst::Create(TrapFn, "", TrapBlock);
+  new UnreachableInst(F.getContext(), TrapBlock);
+  return TrapBlock;
+}
+
+bool ARMNaClDivideCheck::runOnFunction(Function &F) {
+  SmallPtrSet<Instruction*, 8> GuardedDivs;
+  BasicBlock *TrapBlock = NULL;
+  // 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 to the end of

[eliben, 2013/05/03 21:18:55]

I'm not sure I understand the "at the end of the function" part. You create two
types of blocks: one is the trap block which is only created once and we don't
care where it's placed. The other is the continuation block per split, but
that's decided for you by splitBasicBlock. splitBasicBlock IIUC inserts like
this:

BBA->BBB->BBC
      ^ 
   split here

BBA->BBB1->BBB2->BBC

[sehr, 2013/05/03 23:29:05]

I changed it to just emphasize the important point -- that the blocks are
created *after* the current block being processed.

+  // the function, 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;
+      ConstantInt *DenomConst = dyn_cast<ConstantInt>(Denominator);
+      if (DenomConst) {

[Mark Seaborn, 2013/05/03 21:25:36]

Write as:
  if (ConstantInt *DenomConst = dyn_cast<ConstantInt>(Denominator)) { ...

[sehr, 2013/05/03 23:29:05]

Done.

+        // 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);

[Mark Seaborn, 2013/05/03 21:25:36]

Preserve debug location:
CallInst::Create(TrapFn, "", DivInst)->setDebugLoc(DivInst->getDebugLoc());

[sehr, 2013/05/03 23:29:05]

Done.

+        }
+        continue;
+      }
+      // Create a single trap block.

[Mark Seaborn, 2013/05/03 21:25:36]

This could hinder debugging.  It would be nice to preserve debugging info if it
is present.

Maybe if DivInst.getDebugLoc() returns a location, we could create unique trap
blocks?  Or you could reuse a trap block between instructions if their debug
locations match?

Or if you're worried about speed, comment that we're not preserving debugging. 
Is there a flag we can check to see whether debugging is enabled?

[sehr, 2013/05/03 23:29:05]

I was only really interested in code size, and I guess I can go ahead and just
generate N blocks.

+      if (TrapBlock == NULL) {
+        TrapBlock = CreateTrapBlock(F);
+      }
+      // Move instructions in BB from DivInst to BB's end to a new block.
+      BasicBlock *Successor = BB->splitBasicBlock(BI, "");
+      BB->getTerminator()->eraseFromParent();

[Mark Seaborn, 2013/05/03 21:25:36]

Comment: "Remove unconditional branch"?

[sehr, 2013/05/03 23:29:05]

Done.

+      // 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 ARMNaClDivideCheck::ID = 0;
+INITIALIZE_PASS(ARMNaClDivideCheck, "arm-nacl-divide-check",
+                "Add divide by zero checks", false, false)
+
+FunctionPass *llvm::createARMNaClDivideCheckPass() {
+  return new ARMNaClDivideCheck();
+}