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