1 //===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a pass that instruments the code to perform run-time
11 // bounds checking on loads, stores, and other memory intrinsics.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/Transforms/Instrumentation.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/MemoryBuiltins.h"
18 #include "llvm/Analysis/TargetFolder.h"
19 #include "llvm/Analysis/TargetLibraryInfo.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/IRBuilder.h"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Intrinsics.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28 using namespace llvm;
29
30 #define DEBUG_TYPE "bounds-checking"
31
32 static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap",
33 cl::desc("Use one trap block per function"));
34
35 STATISTIC(ChecksAdded, "Bounds checks added");
36 STATISTIC(ChecksSkipped, "Bounds checks skipped");
37 STATISTIC(ChecksUnable, "Bounds checks unable to add");
38
39 typedef IRBuilder<TargetFolder> BuilderTy;
40
41 namespace {
42 struct BoundsChecking : public FunctionPass {
43 static char ID;
44
BoundsChecking__anon69fbb5430111::BoundsChecking45 BoundsChecking() : FunctionPass(ID) {
46 initializeBoundsCheckingPass(*PassRegistry::getPassRegistry());
47 }
48
49 bool runOnFunction(Function &F) override;
50
getAnalysisUsage__anon69fbb5430111::BoundsChecking51 void getAnalysisUsage(AnalysisUsage &AU) const override {
52 AU.addRequired<TargetLibraryInfoWrapperPass>();
53 }
54
55 private:
56 const TargetLibraryInfo *TLI;
57 ObjectSizeOffsetEvaluator *ObjSizeEval;
58 BuilderTy *Builder;
59 Instruction *Inst;
60 BasicBlock *TrapBB;
61
62 BasicBlock *getTrapBB();
63 void emitBranchToTrap(Value *Cmp = nullptr);
64 bool instrument(Value *Ptr, Value *Val, const DataLayout &DL);
65 };
66 }
67
68 char BoundsChecking::ID = 0;
69 INITIALIZE_PASS(BoundsChecking, "bounds-checking", "Run-time bounds checking",
70 false, false)
71
72
73 /// getTrapBB - create a basic block that traps. All overflowing conditions
74 /// branch to this block. There's only one trap block per function.
getTrapBB()75 BasicBlock *BoundsChecking::getTrapBB() {
76 if (TrapBB && SingleTrapBB)
77 return TrapBB;
78
79 Function *Fn = Inst->getParent()->getParent();
80 IRBuilder<>::InsertPointGuard Guard(*Builder);
81 TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
82 Builder->SetInsertPoint(TrapBB);
83
84 llvm::Value *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap);
85 CallInst *TrapCall = Builder->CreateCall(F, {});
86 TrapCall->setDoesNotReturn();
87 TrapCall->setDoesNotThrow();
88 TrapCall->setDebugLoc(Inst->getDebugLoc());
89 Builder->CreateUnreachable();
90
91 return TrapBB;
92 }
93
94
95 /// emitBranchToTrap - emit a branch instruction to a trap block.
96 /// If Cmp is non-null, perform a jump only if its value evaluates to true.
emitBranchToTrap(Value * Cmp)97 void BoundsChecking::emitBranchToTrap(Value *Cmp) {
98 // check if the comparison is always false
99 ConstantInt *C = dyn_cast_or_null<ConstantInt>(Cmp);
100 if (C) {
101 ++ChecksSkipped;
102 if (!C->getZExtValue())
103 return;
104 else
105 Cmp = nullptr; // unconditional branch
106 }
107 ++ChecksAdded;
108
109 BasicBlock::iterator Inst = Builder->GetInsertPoint();
110 BasicBlock *OldBB = Inst->getParent();
111 BasicBlock *Cont = OldBB->splitBasicBlock(Inst);
112 OldBB->getTerminator()->eraseFromParent();
113
114 if (Cmp)
115 BranchInst::Create(getTrapBB(), Cont, Cmp, OldBB);
116 else
117 BranchInst::Create(getTrapBB(), OldBB);
118 }
119
120
121 /// instrument - adds run-time bounds checks to memory accessing instructions.
122 /// Ptr is the pointer that will be read/written, and InstVal is either the
123 /// result from the load or the value being stored. It is used to determine the
124 /// size of memory block that is touched.
125 /// Returns true if any change was made to the IR, false otherwise.
instrument(Value * Ptr,Value * InstVal,const DataLayout & DL)126 bool BoundsChecking::instrument(Value *Ptr, Value *InstVal,
127 const DataLayout &DL) {
128 uint64_t NeededSize = DL.getTypeStoreSize(InstVal->getType());
129 DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize)
130 << " bytes\n");
131
132 SizeOffsetEvalType SizeOffset = ObjSizeEval->compute(Ptr);
133
134 if (!ObjSizeEval->bothKnown(SizeOffset)) {
135 ++ChecksUnable;
136 return false;
137 }
138
139 Value *Size = SizeOffset.first;
140 Value *Offset = SizeOffset.second;
141 ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size);
142
143 Type *IntTy = DL.getIntPtrType(Ptr->getType());
144 Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize);
145
146 // three checks are required to ensure safety:
147 // . Offset >= 0 (since the offset is given from the base ptr)
148 // . Size >= Offset (unsigned)
149 // . Size - Offset >= NeededSize (unsigned)
150 //
151 // optimization: if Size >= 0 (signed), skip 1st check
152 // FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows
153 Value *ObjSize = Builder->CreateSub(Size, Offset);
154 Value *Cmp2 = Builder->CreateICmpULT(Size, Offset);
155 Value *Cmp3 = Builder->CreateICmpULT(ObjSize, NeededSizeVal);
156 Value *Or = Builder->CreateOr(Cmp2, Cmp3);
157 if (!SizeCI || SizeCI->getValue().slt(0)) {
158 Value *Cmp1 = Builder->CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0));
159 Or = Builder->CreateOr(Cmp1, Or);
160 }
161 emitBranchToTrap(Or);
162
163 return true;
164 }
165
runOnFunction(Function & F)166 bool BoundsChecking::runOnFunction(Function &F) {
167 const DataLayout &DL = F.getParent()->getDataLayout();
168 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
169
170 TrapBB = nullptr;
171 BuilderTy TheBuilder(F.getContext(), TargetFolder(DL));
172 Builder = &TheBuilder;
173 ObjectSizeOffsetEvaluator TheObjSizeEval(DL, TLI, F.getContext(),
174 /*RoundToAlign=*/true);
175 ObjSizeEval = &TheObjSizeEval;
176
177 // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
178 // touching instructions
179 std::vector<Instruction*> WorkList;
180 for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
181 Instruction *I = &*i;
182 if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<AtomicCmpXchgInst>(I) ||
183 isa<AtomicRMWInst>(I))
184 WorkList.push_back(I);
185 }
186
187 bool MadeChange = false;
188 for (Instruction *i : WorkList) {
189 Inst = i;
190
191 Builder->SetInsertPoint(Inst);
192 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
193 MadeChange |= instrument(LI->getPointerOperand(), LI, DL);
194 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
195 MadeChange |=
196 instrument(SI->getPointerOperand(), SI->getValueOperand(), DL);
197 } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) {
198 MadeChange |=
199 instrument(AI->getPointerOperand(), AI->getCompareOperand(), DL);
200 } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) {
201 MadeChange |=
202 instrument(AI->getPointerOperand(), AI->getValOperand(), DL);
203 } else {
204 llvm_unreachable("unknown Instruction type");
205 }
206 }
207 return MadeChange;
208 }
209
createBoundsCheckingPass()210 FunctionPass *llvm::createBoundsCheckingPass() {
211 return new BoundsChecking();
212 }
213