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