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