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