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