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 EvalOpts.EvalMode = ObjectSizeOpts::Mode::ExactUnderlyingSizeAndOffset;
150 ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts);
151
152 // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
153 // touching instructions
154 SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo;
155 for (Instruction &I : instructions(F)) {
156 Value *Or = nullptr;
157 BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));
158 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
159 if (!LI->isVolatile())
160 Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI,
161 ObjSizeEval, IRB, SE);
162 } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
163 if (!SI->isVolatile())
164 Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(),
165 DL, TLI, ObjSizeEval, IRB, SE);
166 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) {
167 if (!AI->isVolatile())
168 Or =
169 getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(),
170 DL, TLI, ObjSizeEval, IRB, SE);
171 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) {
172 if (!AI->isVolatile())
173 Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(),
174 DL, TLI, ObjSizeEval, IRB, SE);
175 }
176 if (Or)
177 TrapInfo.push_back(std::make_pair(&I, Or));
178 }
179
180 // Create a trapping basic block on demand using a callback. Depending on
181 // flags, this will either create a single block for the entire function or
182 // will create a fresh block every time it is called.
183 BasicBlock *TrapBB = nullptr;
184 auto GetTrapBB = [&TrapBB](BuilderTy &IRB) {
185 if (TrapBB && SingleTrapBB)
186 return TrapBB;
187
188 Function *Fn = IRB.GetInsertBlock()->getParent();
189 // FIXME: This debug location doesn't make a lot of sense in the
190 // `SingleTrapBB` case.
191 auto DebugLoc = IRB.getCurrentDebugLocation();
192 IRBuilder<>::InsertPointGuard Guard(IRB);
193 TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
194 IRB.SetInsertPoint(TrapBB);
195
196 auto *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap);
197 CallInst *TrapCall = IRB.CreateCall(F, {});
198 TrapCall->setDoesNotReturn();
199 TrapCall->setDoesNotThrow();
200 TrapCall->setDebugLoc(DebugLoc);
201 IRB.CreateUnreachable();
202
203 return TrapBB;
204 };
205
206 // Add the checks.
207 for (const auto &Entry : TrapInfo) {
208 Instruction *Inst = Entry.first;
209 BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL));
210 insertBoundsCheck(Entry.second, IRB, GetTrapBB);
211 }
212
213 return !TrapInfo.empty();
214 }
215
run(Function & F,FunctionAnalysisManager & AM)216 PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) {
217 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
218 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
219
220 if (!addBoundsChecking(F, TLI, SE))
221 return PreservedAnalyses::all();
222
223 return PreservedAnalyses::none();
224 }
225