LLVM API Documentation

BoundsChecking.cpp
Go to the documentation of this file.
00001 //===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a pass that instruments the code to perform run-time
00011 // bounds checking on loads, stores, and other memory intrinsics.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Transforms/Instrumentation.h"
00016 #include "llvm/ADT/Statistic.h"
00017 #include "llvm/Analysis/MemoryBuiltins.h"
00018 #include "llvm/Analysis/TargetFolder.h"
00019 #include "llvm/IR/DataLayout.h"
00020 #include "llvm/IR/IRBuilder.h"
00021 #include "llvm/IR/InstIterator.h"
00022 #include "llvm/IR/Intrinsics.h"
00023 #include "llvm/Pass.h"
00024 #include "llvm/Support/CommandLine.h"
00025 #include "llvm/Support/Debug.h"
00026 #include "llvm/Support/raw_ostream.h"
00027 #include "llvm/Target/TargetLibraryInfo.h"
00028 using namespace llvm;
00029 
00030 #define DEBUG_TYPE "bounds-checking"
00031 
00032 static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap",
00033                                   cl::desc("Use one trap block per function"));
00034 
00035 STATISTIC(ChecksAdded, "Bounds checks added");
00036 STATISTIC(ChecksSkipped, "Bounds checks skipped");
00037 STATISTIC(ChecksUnable, "Bounds checks unable to add");
00038 
00039 typedef IRBuilder<true, TargetFolder> BuilderTy;
00040 
00041 namespace {
00042   struct BoundsChecking : public FunctionPass {
00043     static char ID;
00044 
00045     BoundsChecking() : FunctionPass(ID) {
00046       initializeBoundsCheckingPass(*PassRegistry::getPassRegistry());
00047     }
00048 
00049     bool runOnFunction(Function &F) override;
00050 
00051     void getAnalysisUsage(AnalysisUsage &AU) const override {
00052       AU.addRequired<DataLayoutPass>();
00053       AU.addRequired<TargetLibraryInfo>();
00054     }
00055 
00056   private:
00057     const DataLayout *DL;
00058     const TargetLibraryInfo *TLI;
00059     ObjectSizeOffsetEvaluator *ObjSizeEval;
00060     BuilderTy *Builder;
00061     Instruction *Inst;
00062     BasicBlock *TrapBB;
00063 
00064     BasicBlock *getTrapBB();
00065     void emitBranchToTrap(Value *Cmp = 0);
00066     bool instrument(Value *Ptr, Value *Val);
00067  };
00068 }
00069 
00070 char BoundsChecking::ID = 0;
00071 INITIALIZE_PASS(BoundsChecking, "bounds-checking", "Run-time bounds checking",
00072                 false, false)
00073 
00074 
00075 /// getTrapBB - create a basic block that traps. All overflowing conditions
00076 /// branch to this block. There's only one trap block per function.
00077 BasicBlock *BoundsChecking::getTrapBB() {
00078   if (TrapBB && SingleTrapBB)
00079     return TrapBB;
00080 
00081   Function *Fn = Inst->getParent()->getParent();
00082   IRBuilder<>::InsertPointGuard Guard(*Builder);
00083   TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
00084   Builder->SetInsertPoint(TrapBB);
00085 
00086   llvm::Value *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap);
00087   CallInst *TrapCall = Builder->CreateCall(F);
00088   TrapCall->setDoesNotReturn();
00089   TrapCall->setDoesNotThrow();
00090   TrapCall->setDebugLoc(Inst->getDebugLoc());
00091   Builder->CreateUnreachable();
00092 
00093   return TrapBB;
00094 }
00095 
00096 
00097 /// emitBranchToTrap - emit a branch instruction to a trap block.
00098 /// If Cmp is non-null, perform a jump only if its value evaluates to true.
00099 void BoundsChecking::emitBranchToTrap(Value *Cmp) {
00100   // check if the comparison is always false
00101   ConstantInt *C = dyn_cast_or_null<ConstantInt>(Cmp);
00102   if (C) {
00103     ++ChecksSkipped;
00104     if (!C->getZExtValue())
00105       return;
00106     else
00107       Cmp = 0; // unconditional branch
00108   }
00109   ++ChecksAdded;
00110 
00111   Instruction *Inst = Builder->GetInsertPoint();
00112   BasicBlock *OldBB = Inst->getParent();
00113   BasicBlock *Cont = OldBB->splitBasicBlock(Inst);
00114   OldBB->getTerminator()->eraseFromParent();
00115 
00116   if (Cmp)
00117     BranchInst::Create(getTrapBB(), Cont, Cmp, OldBB);
00118   else
00119     BranchInst::Create(getTrapBB(), OldBB);
00120 }
00121 
00122 
00123 /// instrument - adds run-time bounds checks to memory accessing instructions.
00124 /// Ptr is the pointer that will be read/written, and InstVal is either the
00125 /// result from the load or the value being stored. It is used to determine the
00126 /// size of memory block that is touched.
00127 /// Returns true if any change was made to the IR, false otherwise.
00128 bool BoundsChecking::instrument(Value *Ptr, Value *InstVal) {
00129   uint64_t NeededSize = DL->getTypeStoreSize(InstVal->getType());
00130   DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize)
00131               << " bytes\n");
00132 
00133   SizeOffsetEvalType SizeOffset = ObjSizeEval->compute(Ptr);
00134 
00135   if (!ObjSizeEval->bothKnown(SizeOffset)) {
00136     ++ChecksUnable;
00137     return false;
00138   }
00139 
00140   Value *Size   = SizeOffset.first;
00141   Value *Offset = SizeOffset.second;
00142   ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size);
00143 
00144   Type *IntTy = DL->getIntPtrType(Ptr->getType());
00145   Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize);
00146 
00147   // three checks are required to ensure safety:
00148   // . Offset >= 0  (since the offset is given from the base ptr)
00149   // . Size >= Offset  (unsigned)
00150   // . Size - Offset >= NeededSize  (unsigned)
00151   //
00152   // optimization: if Size >= 0 (signed), skip 1st check
00153   // FIXME: add NSW/NUW here?  -- we dont care if the subtraction overflows
00154   Value *ObjSize = Builder->CreateSub(Size, Offset);
00155   Value *Cmp2 = Builder->CreateICmpULT(Size, Offset);
00156   Value *Cmp3 = Builder->CreateICmpULT(ObjSize, NeededSizeVal);
00157   Value *Or = Builder->CreateOr(Cmp2, Cmp3);
00158   if (!SizeCI || SizeCI->getValue().slt(0)) {
00159     Value *Cmp1 = Builder->CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0));
00160     Or = Builder->CreateOr(Cmp1, Or);
00161   }
00162   emitBranchToTrap(Or);
00163 
00164   return true;
00165 }
00166 
00167 bool BoundsChecking::runOnFunction(Function &F) {
00168   DL = &getAnalysis<DataLayoutPass>().getDataLayout();
00169   TLI = &getAnalysis<TargetLibraryInfo>();
00170 
00171   TrapBB = 0;
00172   BuilderTy TheBuilder(F.getContext(), TargetFolder(DL));
00173   Builder = &TheBuilder;
00174   ObjectSizeOffsetEvaluator TheObjSizeEval(DL, TLI, F.getContext(),
00175                                            /*RoundToAlign=*/true);
00176   ObjSizeEval = &TheObjSizeEval;
00177 
00178   // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
00179   // touching instructions
00180   std::vector<Instruction*> WorkList;
00181   for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
00182     Instruction *I = &*i;
00183     if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<AtomicCmpXchgInst>(I) ||
00184         isa<AtomicRMWInst>(I))
00185         WorkList.push_back(I);
00186   }
00187 
00188   bool MadeChange = false;
00189   for (std::vector<Instruction*>::iterator i = WorkList.begin(),
00190        e = WorkList.end(); i != e; ++i) {
00191     Inst = *i;
00192 
00193     Builder->SetInsertPoint(Inst);
00194     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
00195       MadeChange |= instrument(LI->getPointerOperand(), LI);
00196     } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00197       MadeChange |= instrument(SI->getPointerOperand(), SI->getValueOperand());
00198     } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) {
00199       MadeChange |= instrument(AI->getPointerOperand(),AI->getCompareOperand());
00200     } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) {
00201       MadeChange |= instrument(AI->getPointerOperand(), AI->getValOperand());
00202     } else {
00203       llvm_unreachable("unknown Instruction type");
00204     }
00205   }
00206   return MadeChange;
00207 }
00208 
00209 FunctionPass *llvm::createBoundsCheckingPass() {
00210   return new BoundsChecking();
00211 }