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