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