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