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<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 (Instruction *i : WorkList) { 189 Inst = i; 190 191 Builder->SetInsertPoint(Inst); 192 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 193 MadeChange |= instrument(LI->getPointerOperand(), LI, DL); 194 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 195 MadeChange |= 196 instrument(SI->getPointerOperand(), SI->getValueOperand(), DL); 197 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) { 198 MadeChange |= 199 instrument(AI->getPointerOperand(), AI->getCompareOperand(), DL); 200 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) { 201 MadeChange |= 202 instrument(AI->getPointerOperand(), AI->getValOperand(), DL); 203 } else { 204 llvm_unreachable("unknown Instruction type"); 205 } 206 } 207 return MadeChange; 208 } 209 210 FunctionPass *llvm::createBoundsCheckingPass() { 211 return new BoundsChecking(); 212 } 213