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