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