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