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