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 #include "llvm/Transforms/Instrumentation/BoundsChecking.h" 11 #include "llvm/ADT/Statistic.h" 12 #include "llvm/ADT/Twine.h" 13 #include "llvm/Analysis/MemoryBuiltins.h" 14 #include "llvm/Analysis/ScalarEvolution.h" 15 #include "llvm/Analysis/TargetFolder.h" 16 #include "llvm/Analysis/TargetLibraryInfo.h" 17 #include "llvm/IR/BasicBlock.h" 18 #include "llvm/IR/Constants.h" 19 #include "llvm/IR/DataLayout.h" 20 #include "llvm/IR/Function.h" 21 #include "llvm/IR/IRBuilder.h" 22 #include "llvm/IR/InstIterator.h" 23 #include "llvm/IR/InstrTypes.h" 24 #include "llvm/IR/Instruction.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/IR/Intrinsics.h" 27 #include "llvm/IR/Value.h" 28 #include "llvm/Pass.h" 29 #include "llvm/Support/Casting.h" 30 #include "llvm/Support/CommandLine.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Support/ErrorHandling.h" 33 #include "llvm/Support/raw_ostream.h" 34 #include <cstdint> 35 #include <vector> 36 37 using namespace llvm; 38 39 #define DEBUG_TYPE "bounds-checking" 40 41 static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap", 42 cl::desc("Use one trap block per function")); 43 44 STATISTIC(ChecksAdded, "Bounds checks added"); 45 STATISTIC(ChecksSkipped, "Bounds checks skipped"); 46 STATISTIC(ChecksUnable, "Bounds checks unable to add"); 47 48 using BuilderTy = IRBuilder<TargetFolder>; 49 50 /// Gets the conditions under which memory accessing instructions will overflow. 51 /// 52 /// \p Ptr is the pointer that will be read/written, and \p InstVal is either 53 /// the result from the load or the value being stored. It is used to determine 54 /// the size of memory block that is touched. 55 /// 56 /// Returns the condition under which the access will overflow. 57 static Value *getBoundsCheckCond(Value *Ptr, Value *InstVal, 58 const DataLayout &DL, TargetLibraryInfo &TLI, 59 ObjectSizeOffsetEvaluator &ObjSizeEval, 60 BuilderTy &IRB, ScalarEvolution &SE) { 61 uint64_t NeededSize = DL.getTypeStoreSize(InstVal->getType()); 62 LLVM_DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize) 63 << " bytes\n"); 64 65 SizeOffsetEvalType SizeOffset = ObjSizeEval.compute(Ptr); 66 67 if (!ObjSizeEval.bothKnown(SizeOffset)) { 68 ++ChecksUnable; 69 return nullptr; 70 } 71 72 Value *Size = SizeOffset.first; 73 Value *Offset = SizeOffset.second; 74 ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size); 75 76 Type *IntTy = DL.getIntPtrType(Ptr->getType()); 77 Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize); 78 79 auto SizeRange = SE.getUnsignedRange(SE.getSCEV(Size)); 80 auto OffsetRange = SE.getUnsignedRange(SE.getSCEV(Offset)); 81 auto NeededSizeRange = SE.getUnsignedRange(SE.getSCEV(NeededSizeVal)); 82 83 // three checks are required to ensure safety: 84 // . Offset >= 0 (since the offset is given from the base ptr) 85 // . Size >= Offset (unsigned) 86 // . Size - Offset >= NeededSize (unsigned) 87 // 88 // optimization: if Size >= 0 (signed), skip 1st check 89 // FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows 90 Value *ObjSize = IRB.CreateSub(Size, Offset); 91 Value *Cmp2 = SizeRange.getUnsignedMin().uge(OffsetRange.getUnsignedMax()) 92 ? ConstantInt::getFalse(Ptr->getContext()) 93 : IRB.CreateICmpULT(Size, Offset); 94 Value *Cmp3 = SizeRange.sub(OffsetRange) 95 .getUnsignedMin() 96 .uge(NeededSizeRange.getUnsignedMax()) 97 ? ConstantInt::getFalse(Ptr->getContext()) 98 : IRB.CreateICmpULT(ObjSize, NeededSizeVal); 99 Value *Or = IRB.CreateOr(Cmp2, Cmp3); 100 if ((!SizeCI || SizeCI->getValue().slt(0)) && 101 !SizeRange.getSignedMin().isNonNegative()) { 102 Value *Cmp1 = IRB.CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0)); 103 Or = IRB.CreateOr(Cmp1, Or); 104 } 105 106 return Or; 107 } 108 109 /// Adds run-time bounds checks to memory accessing instructions. 110 /// 111 /// \p Or is the condition that should guard the trap. 112 /// 113 /// \p GetTrapBB is a callable that returns the trap BB to use on failure. 114 template <typename GetTrapBBT> 115 static void insertBoundsCheck(Value *Or, BuilderTy IRB, GetTrapBBT GetTrapBB) { 116 // check if the comparison is always false 117 ConstantInt *C = dyn_cast_or_null<ConstantInt>(Or); 118 if (C) { 119 ++ChecksSkipped; 120 // If non-zero, nothing to do. 121 if (!C->getZExtValue()) 122 return; 123 } 124 ++ChecksAdded; 125 126 BasicBlock::iterator SplitI = IRB.GetInsertPoint(); 127 BasicBlock *OldBB = SplitI->getParent(); 128 BasicBlock *Cont = OldBB->splitBasicBlock(SplitI); 129 OldBB->getTerminator()->eraseFromParent(); 130 131 if (C) { 132 // If we have a constant zero, unconditionally branch. 133 // FIXME: We should really handle this differently to bypass the splitting 134 // the block. 135 BranchInst::Create(GetTrapBB(IRB), OldBB); 136 return; 137 } 138 139 // Create the conditional branch. 140 BranchInst::Create(GetTrapBB(IRB), Cont, Or, OldBB); 141 } 142 143 static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI, 144 ScalarEvolution &SE) { 145 const DataLayout &DL = F.getParent()->getDataLayout(); 146 ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), 147 /*RoundToAlign=*/true); 148 149 // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory 150 // touching instructions 151 SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo; 152 for (Instruction &I : instructions(F)) { 153 Value *Or = nullptr; 154 BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL)); 155 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 156 Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI, 157 ObjSizeEval, IRB, SE); 158 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) { 159 Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(), 160 DL, TLI, ObjSizeEval, IRB, SE); 161 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) { 162 Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(), 163 DL, TLI, ObjSizeEval, IRB, SE); 164 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) { 165 Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(), DL, 166 TLI, ObjSizeEval, IRB, SE); 167 } 168 if (Or) 169 TrapInfo.push_back(std::make_pair(&I, Or)); 170 } 171 172 // Create a trapping basic block on demand using a callback. Depending on 173 // flags, this will either create a single block for the entire function or 174 // will create a fresh block every time it is called. 175 BasicBlock *TrapBB = nullptr; 176 auto GetTrapBB = [&TrapBB](BuilderTy &IRB) { 177 if (TrapBB && SingleTrapBB) 178 return TrapBB; 179 180 Function *Fn = IRB.GetInsertBlock()->getParent(); 181 // FIXME: This debug location doesn't make a lot of sense in the 182 // `SingleTrapBB` case. 183 auto DebugLoc = IRB.getCurrentDebugLocation(); 184 IRBuilder<>::InsertPointGuard Guard(IRB); 185 TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn); 186 IRB.SetInsertPoint(TrapBB); 187 188 auto *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap); 189 CallInst *TrapCall = IRB.CreateCall(F, {}); 190 TrapCall->setDoesNotReturn(); 191 TrapCall->setDoesNotThrow(); 192 TrapCall->setDebugLoc(DebugLoc); 193 IRB.CreateUnreachable(); 194 195 return TrapBB; 196 }; 197 198 // Add the checks. 199 for (const auto &Entry : TrapInfo) { 200 Instruction *Inst = Entry.first; 201 BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL)); 202 insertBoundsCheck(Entry.second, IRB, GetTrapBB); 203 } 204 205 return !TrapInfo.empty(); 206 } 207 208 PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) { 209 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 210 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 211 212 if (!addBoundsChecking(F, TLI, SE)) 213 return PreservedAnalyses::all(); 214 215 return PreservedAnalyses::none(); 216 } 217 218 namespace { 219 struct BoundsCheckingLegacyPass : public FunctionPass { 220 static char ID; 221 222 BoundsCheckingLegacyPass() : FunctionPass(ID) { 223 initializeBoundsCheckingLegacyPassPass(*PassRegistry::getPassRegistry()); 224 } 225 226 bool runOnFunction(Function &F) override { 227 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 228 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 229 return addBoundsChecking(F, TLI, SE); 230 } 231 232 void getAnalysisUsage(AnalysisUsage &AU) const override { 233 AU.addRequired<TargetLibraryInfoWrapperPass>(); 234 AU.addRequired<ScalarEvolutionWrapperPass>(); 235 } 236 }; 237 } // namespace 238 239 char BoundsCheckingLegacyPass::ID = 0; 240 INITIALIZE_PASS_BEGIN(BoundsCheckingLegacyPass, "bounds-checking", 241 "Run-time bounds checking", false, false) 242 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 243 INITIALIZE_PASS_END(BoundsCheckingLegacyPass, "bounds-checking", 244 "Run-time bounds checking", false, false) 245 246 FunctionPass *llvm::createBoundsCheckingLegacyPass() { 247 return new BoundsCheckingLegacyPass(); 248 } 249