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