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/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/Target/TargetData.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<TargetData>();
     52       AU.addRequired<TargetLibraryInfo>();
     53     }
     54 
     55   private:
     56     const TargetData *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   IntegerType *IntTy = TD->getIntPtrType(Inst->getContext());
    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<TargetData>();
    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 }
    214