//===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements a pass that instruments the code to perform run-time // bounds checking on loads, stores, and other memory intrinsics. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Instrumentation.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/TargetFolder.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/Intrinsics.h" #include "llvm/Pass.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetLibraryInfo.h" using namespace llvm; #define DEBUG_TYPE "bounds-checking" static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap", cl::desc("Use one trap block per function")); STATISTIC(ChecksAdded, "Bounds checks added"); STATISTIC(ChecksSkipped, "Bounds checks skipped"); STATISTIC(ChecksUnable, "Bounds checks unable to add"); typedef IRBuilder<true, TargetFolder> BuilderTy; namespace { struct BoundsChecking : public FunctionPass { static char ID; BoundsChecking() : FunctionPass(ID) { initializeBoundsCheckingPass(*PassRegistry::getPassRegistry()); } bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired<DataLayoutPass>(); AU.addRequired<TargetLibraryInfo>(); } private: const DataLayout *DL; const TargetLibraryInfo *TLI; ObjectSizeOffsetEvaluator *ObjSizeEval; BuilderTy *Builder; Instruction *Inst; BasicBlock *TrapBB; BasicBlock *getTrapBB(); void emitBranchToTrap(Value *Cmp = nullptr); bool instrument(Value *Ptr, Value *Val); }; } char BoundsChecking::ID = 0; INITIALIZE_PASS(BoundsChecking, "bounds-checking", "Run-time bounds checking", false, false) /// getTrapBB - create a basic block that traps. All overflowing conditions /// branch to this block. There's only one trap block per function. BasicBlock *BoundsChecking::getTrapBB() { if (TrapBB && SingleTrapBB) return TrapBB; Function *Fn = Inst->getParent()->getParent(); IRBuilder<>::InsertPointGuard Guard(*Builder); TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn); Builder->SetInsertPoint(TrapBB); llvm::Value *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap); CallInst *TrapCall = Builder->CreateCall(F); TrapCall->setDoesNotReturn(); TrapCall->setDoesNotThrow(); TrapCall->setDebugLoc(Inst->getDebugLoc()); Builder->CreateUnreachable(); return TrapBB; } /// emitBranchToTrap - emit a branch instruction to a trap block. /// If Cmp is non-null, perform a jump only if its value evaluates to true. void BoundsChecking::emitBranchToTrap(Value *Cmp) { // check if the comparison is always false ConstantInt *C = dyn_cast_or_null<ConstantInt>(Cmp); if (C) { ++ChecksSkipped; if (!C->getZExtValue()) return; else Cmp = nullptr; // unconditional branch } ++ChecksAdded; Instruction *Inst = Builder->GetInsertPoint(); BasicBlock *OldBB = Inst->getParent(); BasicBlock *Cont = OldBB->splitBasicBlock(Inst); OldBB->getTerminator()->eraseFromParent(); if (Cmp) BranchInst::Create(getTrapBB(), Cont, Cmp, OldBB); else BranchInst::Create(getTrapBB(), OldBB); } /// instrument - adds run-time bounds checks to memory accessing instructions. /// Ptr is the pointer that will be read/written, and InstVal is either the /// result from the load or the value being stored. It is used to determine the /// size of memory block that is touched. /// Returns true if any change was made to the IR, false otherwise. bool BoundsChecking::instrument(Value *Ptr, Value *InstVal) { uint64_t NeededSize = DL->getTypeStoreSize(InstVal->getType()); DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize) << " bytes\n"); SizeOffsetEvalType SizeOffset = ObjSizeEval->compute(Ptr); if (!ObjSizeEval->bothKnown(SizeOffset)) { ++ChecksUnable; return false; } Value *Size = SizeOffset.first; Value *Offset = SizeOffset.second; ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size); Type *IntTy = DL->getIntPtrType(Ptr->getType()); Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize); // three checks are required to ensure safety: // . Offset >= 0 (since the offset is given from the base ptr) // . Size >= Offset (unsigned) // . Size - Offset >= NeededSize (unsigned) // // optimization: if Size >= 0 (signed), skip 1st check // FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows Value *ObjSize = Builder->CreateSub(Size, Offset); Value *Cmp2 = Builder->CreateICmpULT(Size, Offset); Value *Cmp3 = Builder->CreateICmpULT(ObjSize, NeededSizeVal); Value *Or = Builder->CreateOr(Cmp2, Cmp3); if (!SizeCI || SizeCI->getValue().slt(0)) { Value *Cmp1 = Builder->CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0)); Or = Builder->CreateOr(Cmp1, Or); } emitBranchToTrap(Or); return true; } bool BoundsChecking::runOnFunction(Function &F) { DL = &getAnalysis<DataLayoutPass>().getDataLayout(); TLI = &getAnalysis<TargetLibraryInfo>(); TrapBB = nullptr; BuilderTy TheBuilder(F.getContext(), TargetFolder(DL)); Builder = &TheBuilder; ObjectSizeOffsetEvaluator TheObjSizeEval(DL, TLI, F.getContext(), /*RoundToAlign=*/true); ObjSizeEval = &TheObjSizeEval; // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory // touching instructions std::vector<Instruction*> WorkList; for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { Instruction *I = &*i; if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<AtomicCmpXchgInst>(I) || isa<AtomicRMWInst>(I)) WorkList.push_back(I); } bool MadeChange = false; for (std::vector<Instruction*>::iterator i = WorkList.begin(), e = WorkList.end(); i != e; ++i) { Inst = *i; Builder->SetInsertPoint(Inst); if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { MadeChange |= instrument(LI->getPointerOperand(), LI); } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { MadeChange |= instrument(SI->getPointerOperand(), SI->getValueOperand()); } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) { MadeChange |= instrument(AI->getPointerOperand(),AI->getCompareOperand()); } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) { MadeChange |= instrument(AI->getPointerOperand(), AI->getValOperand()); } else { llvm_unreachable("unknown Instruction type"); } } return MadeChange; } FunctionPass *llvm::createBoundsCheckingPass() { return new BoundsChecking(); }