contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp

   1 //===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a pass that instruments the code to perform run-time
  11 // bounds checking on loads, stores, and other memory intrinsics.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "bounds-checking"
  16 #include "llvm/IRBuilder.h"
  17 #include "llvm/Intrinsics.h"
  18 #include "llvm/Pass.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/Analysis/MemoryBuiltins.h"
  21 #include "llvm/Support/CommandLine.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/InstIterator.h"
  24 #include "llvm/Support/TargetFolder.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include "llvm/DataLayout.h"
  27 #include "llvm/Target/TargetLibraryInfo.h"
  28 #include "llvm/Transforms/Instrumentation.h"
  29 using namespace llvm;
  30
  31 static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap",
  32                                   cl::desc("Use one trap block per function"));
  33
  34 STATISTIC(ChecksAdded, "Bounds checks added");
  35 STATISTIC(ChecksSkipped, "Bounds checks skipped");
  36 STATISTIC(ChecksUnable, "Bounds checks unable to add");
  37
  38 typedef IRBuilder<true, TargetFolder> BuilderTy;
  39
  40 namespace {
  41   struct BoundsChecking : public FunctionPass {
  42     static char ID;
  43
  44     BoundsChecking(unsigned _Penalty = 5) : FunctionPass(ID), Penalty(_Penalty){
  45       initializeBoundsCheckingPass(*PassRegistry::getPassRegistry());
  46     }
  47
  48     virtual bool runOnFunction(Function &F);
  49
  50     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  51       AU.addRequired<DataLayout>();
  52       AU.addRequired<TargetLibraryInfo>();
  53     }
  54
  55   private:
  56     const DataLayout *TD;
  57     const TargetLibraryInfo *TLI;
  58     ObjectSizeOffsetEvaluator *ObjSizeEval;
  59     BuilderTy *Builder;
  60     Instruction *Inst;
  61     BasicBlock *TrapBB;
  62     unsigned Penalty;
  63
  64     BasicBlock *getTrapBB();
  65     void emitBranchToTrap(Value *Cmp = 0);
  66     bool computeAllocSize(Value *Ptr, APInt &Offset, Value* &OffsetValue,
  67                           APInt &Size, Value* &SizeValue);
  68     bool instrument(Value *Ptr, Value *Val);
  69  };
  70 }
  71
  72 char BoundsChecking::ID = 0;
  73 INITIALIZE_PASS(BoundsChecking, "bounds-checking", "Run-time bounds checking",
  74                 false, false)
  75
  76
  77 /// getTrapBB - create a basic block that traps. All overflowing conditions
  78 /// branch to this block. There's only one trap block per function.
  79 BasicBlock *BoundsChecking::getTrapBB() {
  80   if (TrapBB && SingleTrapBB)
  81     return TrapBB;
  82
  83   Function *Fn = Inst->getParent()->getParent();
  84   BasicBlock::iterator PrevInsertPoint = Builder->GetInsertPoint();
  85   TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
  86   Builder->SetInsertPoint(TrapBB);
  87
  88   llvm::Value *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap);
  89   CallInst *TrapCall = Builder->CreateCall(F);
  90   TrapCall->setDoesNotReturn();
  91   TrapCall->setDoesNotThrow();
  92   TrapCall->setDebugLoc(Inst->getDebugLoc());
  93   Builder->CreateUnreachable();
  94
  95   Builder->SetInsertPoint(PrevInsertPoint);
  96   return TrapBB;
  97 }
  98
  99
 100 /// emitBranchToTrap - emit a branch instruction to a trap block.
 101 /// If Cmp is non-null, perform a jump only if its value evaluates to true.
 102 void BoundsChecking::emitBranchToTrap(Value *Cmp) {
 103   // check if the comparison is always false
 104   ConstantInt *C = dyn_cast_or_null<ConstantInt>(Cmp);
 105   if (C) {
 106     ++ChecksSkipped;
 107     if (!C->getZExtValue())
 108       return;
 109     else
 110       Cmp = 0; // unconditional branch
 111   }
 112
 113   Instruction *Inst = Builder->GetInsertPoint();
 114   BasicBlock *OldBB = Inst->getParent();
 115   BasicBlock *Cont = OldBB->splitBasicBlock(Inst);
 116   OldBB->getTerminator()->eraseFromParent();
 117
 118   if (Cmp)
 119     BranchInst::Create(getTrapBB(), Cont, Cmp, OldBB);
 120   else
 121     BranchInst::Create(getTrapBB(), OldBB);
 122 }
 123
 124
 125 /// instrument - adds run-time bounds checks to memory accessing instructions.
 126 /// Ptr is the pointer that will be read/written, and InstVal is either the
 127 /// result from the load or the value being stored. It is used to determine the
 128 /// size of memory block that is touched.
 129 /// Returns true if any change was made to the IR, false otherwise.
 130 bool BoundsChecking::instrument(Value *Ptr, Value *InstVal) {
 131   uint64_t NeededSize = TD->getTypeStoreSize(InstVal->getType());
 132   DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize)
 133               << " bytes\n");
 134
 135   SizeOffsetEvalType SizeOffset = ObjSizeEval->compute(Ptr);
 136
 137   if (!ObjSizeEval->bothKnown(SizeOffset)) {
 138     ++ChecksUnable;
 139     return false;
 140   }
 141
 142   Value *Size   = SizeOffset.first;
 143   Value *Offset = SizeOffset.second;
 144   ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size);
 145
 146   Type *IntTy = TD->getIntPtrType(Ptr->getType());
 147   Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize);
 148
 149   // three checks are required to ensure safety:
 150   // . Offset >= 0  (since the offset is given from the base ptr)
 151   // . Size >= Offset  (unsigned)
 152   // . Size - Offset >= NeededSize  (unsigned)
 153   //
 154   // optimization: if Size >= 0 (signed), skip 1st check
 155   // FIXME: add NSW/NUW here?  -- we dont care if the subtraction overflows
 156   Value *ObjSize = Builder->CreateSub(Size, Offset);
 157   Value *Cmp2 = Builder->CreateICmpULT(Size, Offset);
 158   Value *Cmp3 = Builder->CreateICmpULT(ObjSize, NeededSizeVal);
 159   Value *Or = Builder->CreateOr(Cmp2, Cmp3);
 160   if (!SizeCI || SizeCI->getValue().slt(0)) {
 161     Value *Cmp1 = Builder->CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0));
 162     Or = Builder->CreateOr(Cmp1, Or);
 163   }
 164   emitBranchToTrap(Or);
 165
 166   ++ChecksAdded;
 167   return true;
 168 }
 169
 170 bool BoundsChecking::runOnFunction(Function &F) {
 171   TD = &getAnalysis<DataLayout>();
 172   TLI = &getAnalysis<TargetLibraryInfo>();
 173
 174   TrapBB = 0;
 175   BuilderTy TheBuilder(F.getContext(), TargetFolder(TD));
 176   Builder = &TheBuilder;
 177   ObjectSizeOffsetEvaluator TheObjSizeEval(TD, TLI, F.getContext());
 178   ObjSizeEval = &TheObjSizeEval;
 179
 180   // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
 181   // touching instructions
 182   std::vector<Instruction*> WorkList;
 183   for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
 184     Instruction *I = &*i;
 185     if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<AtomicCmpXchgInst>(I) ||
 186         isa<AtomicRMWInst>(I))
 187         WorkList.push_back(I);
 188   }
 189
 190   bool MadeChange = false;
 191   for (std::vector<Instruction*>::iterator i = WorkList.begin(),
 192        e = WorkList.end(); i != e; ++i) {
 193     Inst = *i;
 194
 195     Builder->SetInsertPoint(Inst);
 196     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 197       MadeChange |= instrument(LI->getPointerOperand(), LI);
 198     } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 199       MadeChange |= instrument(SI->getPointerOperand(), SI->getValueOperand());
 200     } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) {
 201       MadeChange |= instrument(AI->getPointerOperand(),AI->getCompareOperand());
 202     } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) {
 203       MadeChange |= instrument(AI->getPointerOperand(), AI->getValOperand());
 204     } else {
 205       llvm_unreachable("unknown Instruction type");
 206     }
 207   }
 208   return MadeChange;
 209 }
 210
 211 FunctionPass *llvm::createBoundsCheckingPass(unsigned Penalty) {
 212   return new BoundsChecking(Penalty);
 213 }