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/Pass.h" 28 #include "llvm/Support/Casting.h" 29 #include "llvm/Support/CommandLine.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/ErrorHandling.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include <cstdint> 34 #include <vector> 35 36 using namespace llvm; 37 38 #define DEBUG_TYPE "bounds-checking" 39 40 static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap", 41 cl::desc("Use one trap block per function")); 42 43 STATISTIC(ChecksAdded, "Bounds checks added"); 44 STATISTIC(ChecksSkipped, "Bounds checks skipped"); 45 STATISTIC(ChecksUnable, "Bounds checks unable to add"); 46 47 using BuilderTy = IRBuilder<TargetFolder>; 48 49 /// Gets the conditions under which memory accessing instructions will overflow. 50 /// 51 /// \p Ptr is the pointer that will be read/written, and \p InstVal is either 52 /// the result from the load or the value being stored. It is used to determine 53 /// the size of memory block that is touched. 54 /// 55 /// Returns the condition under which the access will overflow. 56 static Value *getBoundsCheckCond(Value *Ptr, Value *InstVal, 57 const DataLayout &DL, TargetLibraryInfo &TLI, 58 ObjectSizeOffsetEvaluator &ObjSizeEval, 59 BuilderTy &IRB, ScalarEvolution &SE) { 60 uint64_t NeededSize = DL.getTypeStoreSize(InstVal->getType()); 61 LLVM_DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize) 62 << " bytes\n"); 63 64 SizeOffsetEvalType SizeOffset = ObjSizeEval.compute(Ptr); 65 66 if (!ObjSizeEval.bothKnown(SizeOffset)) { 67 ++ChecksUnable; 68 return nullptr; 69 } 70 71 Value *Size = SizeOffset.first; 72 Value *Offset = SizeOffset.second; 73 ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size); 74 75 Type *IntTy = DL.getIntPtrType(Ptr->getType()); 76 Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize); 77 78 auto SizeRange = SE.getUnsignedRange(SE.getSCEV(Size)); 79 auto OffsetRange = SE.getUnsignedRange(SE.getSCEV(Offset)); 80 auto NeededSizeRange = SE.getUnsignedRange(SE.getSCEV(NeededSizeVal)); 81 82 // three checks are required to ensure safety: 83 // . Offset >= 0 (since the offset is given from the base ptr) 84 // . Size >= Offset (unsigned) 85 // . Size - Offset >= NeededSize (unsigned) 86 // 87 // optimization: if Size >= 0 (signed), skip 1st check 88 // FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows 89 Value *ObjSize = IRB.CreateSub(Size, Offset); 90 Value *Cmp2 = SizeRange.getUnsignedMin().uge(OffsetRange.getUnsignedMax()) 91 ? ConstantInt::getFalse(Ptr->getContext()) 92 : IRB.CreateICmpULT(Size, Offset); 93 Value *Cmp3 = SizeRange.sub(OffsetRange) 94 .getUnsignedMin() 95 .uge(NeededSizeRange.getUnsignedMax()) 96 ? ConstantInt::getFalse(Ptr->getContext()) 97 : IRB.CreateICmpULT(ObjSize, NeededSizeVal); 98 Value *Or = IRB.CreateOr(Cmp2, Cmp3); 99 if ((!SizeCI || SizeCI->getValue().slt(0)) && 100 !SizeRange.getSignedMin().isNonNegative()) { 101 Value *Cmp1 = IRB.CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0)); 102 Or = IRB.CreateOr(Cmp1, Or); 103 } 104 105 return Or; 106 } 107 108 /// Adds run-time bounds checks to memory accessing instructions. 109 /// 110 /// \p Or is the condition that should guard the trap. 111 /// 112 /// \p GetTrapBB is a callable that returns the trap BB to use on failure. 113 template <typename GetTrapBBT> 114 static void insertBoundsCheck(Value *Or, BuilderTy IRB, GetTrapBBT GetTrapBB) { 115 // check if the comparison is always false 116 ConstantInt *C = dyn_cast_or_null<ConstantInt>(Or); 117 if (C) { 118 ++ChecksSkipped; 119 // If non-zero, nothing to do. 120 if (!C->getZExtValue()) 121 return; 122 } 123 ++ChecksAdded; 124 125 BasicBlock::iterator SplitI = IRB.GetInsertPoint(); 126 BasicBlock *OldBB = SplitI->getParent(); 127 BasicBlock *Cont = OldBB->splitBasicBlock(SplitI); 128 OldBB->getTerminator()->eraseFromParent(); 129 130 if (C) { 131 // If we have a constant zero, unconditionally branch. 132 // FIXME: We should really handle this differently to bypass the splitting 133 // the block. 134 BranchInst::Create(GetTrapBB(IRB), OldBB); 135 return; 136 } 137 138 // Create the conditional branch. 139 BranchInst::Create(GetTrapBB(IRB), Cont, Or, OldBB); 140 } 141 142 static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI, 143 ScalarEvolution &SE) { 144 const DataLayout &DL = F.getParent()->getDataLayout(); 145 ObjectSizeOpts EvalOpts; 146 EvalOpts.RoundToAlign = true; 147 ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts); 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(F); 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