Home | History | Annotate | Download | only in Instrumentation 
      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/Transforms/Instrumentation.h"
     17 #include "llvm/ADT/Statistic.h"
     18 #include "llvm/Analysis/MemoryBuiltins.h"
     19 #include "llvm/IR/DataLayout.h"
     20 #include "llvm/IR/IRBuilder.h"
     21 #include "llvm/IR/Intrinsics.h"
     22 #include "llvm/Pass.h"
     23 #include "llvm/Support/CommandLine.h"
     24 #include "llvm/Support/Debug.h"
     25 #include "llvm/Support/InstIterator.h"
     26 #include "llvm/Support/TargetFolder.h"
     27 #include "llvm/Support/raw_ostream.h"
     28 #include "llvm/Target/TargetLibraryInfo.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() : FunctionPass(ID) {
     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 
     63     BasicBlock *getTrapBB();
     64     void emitBranchToTrap(Value *Cmp = 0);
     65     bool computeAllocSize(Value *Ptr, APInt &Offset, Value* &OffsetValue,
     66                           APInt &Size, Value* &SizeValue);
     67     bool instrument(Value *Ptr, Value *Val);
     68  };
     69 }
     70 
     71 char BoundsChecking::ID = 0;
     72 INITIALIZE_PASS(BoundsChecking, "bounds-checking", "Run-time bounds checking",
     73                 false, false)
     74 
     75 
     76 /// getTrapBB - create a basic block that traps. All overflowing conditions
     77 /// branch to this block. There's only one trap block per function.
     78 BasicBlock *BoundsChecking::getTrapBB() {
     79   if (TrapBB && SingleTrapBB)
     80     return TrapBB;
     81 
     82   Function *Fn = Inst->getParent()->getParent();
     83   BasicBlock::iterator PrevInsertPoint = Builder->GetInsertPoint();
     84   TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
     85   Builder->SetInsertPoint(TrapBB);
     86 
     87   llvm::Value *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap);
     88   CallInst *TrapCall = Builder->CreateCall(F);
     89   TrapCall->setDoesNotReturn();
     90   TrapCall->setDoesNotThrow();
     91   TrapCall->setDebugLoc(Inst->getDebugLoc());
     92   Builder->CreateUnreachable();
     93 
     94   Builder->SetInsertPoint(PrevInsertPoint);
     95   return TrapBB;
     96 }
     97 
     98 
     99 /// emitBranchToTrap - emit a branch instruction to a trap block.
    100 /// If Cmp is non-null, perform a jump only if its value evaluates to true.
    101 void BoundsChecking::emitBranchToTrap(Value *Cmp) {
    102   // check if the comparison is always false
    103   ConstantInt *C = dyn_cast_or_null<ConstantInt>(Cmp);
    104   if (C) {
    105     ++ChecksSkipped;
    106     if (!C->getZExtValue())
    107       return;
    108     else
    109       Cmp = 0; // unconditional branch
    110   }
    111   ++ChecksAdded;
    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   return true;
    167 }
    168 
    169 bool BoundsChecking::runOnFunction(Function &F) {
    170   TD = &getAnalysis<DataLayout>();
    171   TLI = &getAnalysis<TargetLibraryInfo>();
    172 
    173   TrapBB = 0;
    174   BuilderTy TheBuilder(F.getContext(), TargetFolder(TD));
    175   Builder = &TheBuilder;
    176   ObjectSizeOffsetEvaluator TheObjSizeEval(TD, TLI, F.getContext());
    177   ObjSizeEval = &TheObjSizeEval;
    178 
    179   // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
    180   // touching instructions
    181   std::vector<Instruction*> WorkList;
    182   for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
    183     Instruction *I = &*i;
    184     if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<AtomicCmpXchgInst>(I) ||
    185         isa<AtomicRMWInst>(I))
    186         WorkList.push_back(I);
    187   }
    188 
    189   bool MadeChange = false;
    190   for (std::vector<Instruction*>::iterator i = WorkList.begin(),
    191        e = WorkList.end(); i != e; ++i) {
    192     Inst = *i;
    193 
    194     Builder->SetInsertPoint(Inst);
    195     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
    196       MadeChange |= instrument(LI->getPointerOperand(), LI);
    197     } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
    198       MadeChange |= instrument(SI->getPointerOperand(), SI->getValueOperand());
    199     } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) {
    200       MadeChange |= instrument(AI->getPointerOperand(),AI->getCompareOperand());
    201     } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) {
    202       MadeChange |= instrument(AI->getPointerOperand(), AI->getValOperand());
    203     } else {
    204       llvm_unreachable("unknown Instruction type");
    205     }
    206   }
    207   return MadeChange;
    208 }
    209 
    210 FunctionPass *llvm::createBoundsCheckingPass() {
    211   return new BoundsChecking();
    212 }
    213