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.
getBoundsCheckCond(Value * Ptr,Value * InstVal,const DataLayout & DL,TargetLibraryInfo & TLI,ObjectSizeOffsetEvaluator & ObjSizeEval,BuilderTy & IRB,ScalarEvolution & SE)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>
insertBoundsCheck(Value * Or,BuilderTy & IRB,GetTrapBBT GetTrapBB)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
addBoundsChecking(Function & F,TargetLibraryInfo & TLI,ScalarEvolution & SE)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
run(Function & F,FunctionAnalysisManager & AM)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
BoundsCheckingLegacyPass__anon376f97280211::BoundsCheckingLegacyPass229 BoundsCheckingLegacyPass() : FunctionPass(ID) {
230 initializeBoundsCheckingLegacyPassPass(*PassRegistry::getPassRegistry());
231 }
232
runOnFunction__anon376f97280211::BoundsCheckingLegacyPass233 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
getAnalysisUsage__anon376f97280211::BoundsCheckingLegacyPass239 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)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)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