1 //===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Transforms/Instrumentation/BoundsChecking.h" 10 #include "llvm/ADT/Statistic.h" 11 #include "llvm/ADT/Twine.h" 12 #include "llvm/Analysis/MemoryBuiltins.h" 13 #include "llvm/Analysis/ScalarEvolution.h" 14 #include "llvm/Analysis/TargetFolder.h" 15 #include "llvm/Analysis/TargetLibraryInfo.h" 16 #include "llvm/IR/BasicBlock.h" 17 #include "llvm/IR/Constants.h" 18 #include "llvm/IR/DataLayout.h" 19 #include "llvm/IR/Function.h" 20 #include "llvm/IR/IRBuilder.h" 21 #include "llvm/IR/InstIterator.h" 22 #include "llvm/IR/InstrTypes.h" 23 #include "llvm/IR/Instruction.h" 24 #include "llvm/IR/Instructions.h" 25 #include "llvm/IR/Intrinsics.h" 26 #include "llvm/IR/Value.h" 27 #include "llvm/InitializePasses.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 ObjectSizeOpts EvalOpts; 147 EvalOpts.RoundToAlign = true; 148 ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts); 149 150 // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory 151 // touching instructions 152 SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo; 153 for (Instruction &I : instructions(F)) { 154 Value *Or = nullptr; 155 BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL)); 156 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 157 Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI, 158 ObjSizeEval, IRB, SE); 159 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) { 160 Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(), 161 DL, TLI, ObjSizeEval, IRB, SE); 162 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) { 163 Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(), 164 DL, TLI, ObjSizeEval, IRB, SE); 165 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) { 166 Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(), DL, 167 TLI, ObjSizeEval, IRB, SE); 168 } 169 if (Or) 170 TrapInfo.push_back(std::make_pair(&I, Or)); 171 } 172 173 // Create a trapping basic block on demand using a callback. Depending on 174 // flags, this will either create a single block for the entire function or 175 // will create a fresh block every time it is called. 176 BasicBlock *TrapBB = nullptr; 177 auto GetTrapBB = [&TrapBB](BuilderTy &IRB) { 178 if (TrapBB && SingleTrapBB) 179 return TrapBB; 180 181 Function *Fn = IRB.GetInsertBlock()->getParent(); 182 // FIXME: This debug location doesn't make a lot of sense in the 183 // `SingleTrapBB` case. 184 auto DebugLoc = IRB.getCurrentDebugLocation(); 185 IRBuilder<>::InsertPointGuard Guard(IRB); 186 TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn); 187 IRB.SetInsertPoint(TrapBB); 188 189 auto *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap); 190 CallInst *TrapCall = IRB.CreateCall(F, {}); 191 TrapCall->setDoesNotReturn(); 192 TrapCall->setDoesNotThrow(); 193 TrapCall->setDebugLoc(DebugLoc); 194 IRB.CreateUnreachable(); 195 196 return TrapBB; 197 }; 198 199 // Add the checks. 200 for (const auto &Entry : TrapInfo) { 201 Instruction *Inst = Entry.first; 202 BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL)); 203 insertBoundsCheck(Entry.second, IRB, GetTrapBB); 204 } 205 206 return !TrapInfo.empty(); 207 } 208 209 PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) { 210 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 211 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 212 213 if (!addBoundsChecking(F, TLI, SE)) 214 return PreservedAnalyses::all(); 215 216 return PreservedAnalyses::none(); 217 } 218 219 namespace { 220 struct BoundsCheckingLegacyPass : public FunctionPass { 221 static char ID; 222 223 BoundsCheckingLegacyPass() : FunctionPass(ID) { 224 initializeBoundsCheckingLegacyPassPass(*PassRegistry::getPassRegistry()); 225 } 226 227 bool runOnFunction(Function &F) override { 228 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 229 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 230 return addBoundsChecking(F, TLI, SE); 231 } 232 233 void getAnalysisUsage(AnalysisUsage &AU) const override { 234 AU.addRequired<TargetLibraryInfoWrapperPass>(); 235 AU.addRequired<ScalarEvolutionWrapperPass>(); 236 } 237 }; 238 } // namespace 239 240 char BoundsCheckingLegacyPass::ID = 0; 241 INITIALIZE_PASS_BEGIN(BoundsCheckingLegacyPass, "bounds-checking", 242 "Run-time bounds checking", false, false) 243 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 244 INITIALIZE_PASS_END(BoundsCheckingLegacyPass, "bounds-checking", 245 "Run-time bounds checking", false, false) 246 247 FunctionPass *llvm::createBoundsCheckingLegacyPass() { 248 return new BoundsCheckingLegacyPass(); 249 } 250