Home | History | Annotate | Download | only in Instrumentation 
      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 #include "llvm/Transforms/Instrumentation/BoundsChecking.h"
     11 #include "llvm/ADT/Statistic.h"
     12 #include "llvm/ADT/Twine.h"
     13 #include "llvm/Analysis/MemoryBuiltins.h"
     14 #include "llvm/Analysis/ScalarEvolution.h"
     15 #include "llvm/Analysis/TargetFolder.h"
     16 #include "llvm/Analysis/TargetLibraryInfo.h"
     17 #include "llvm/IR/BasicBlock.h"
     18 #include "llvm/IR/Constants.h"
     19 #include "llvm/IR/DataLayout.h"
     20 #include "llvm/IR/Function.h"
     21 #include "llvm/IR/IRBuilder.h"
     22 #include "llvm/IR/InstIterator.h"
     23 #include "llvm/IR/InstrTypes.h"
     24 #include "llvm/IR/Instruction.h"
     25 #include "llvm/IR/Instructions.h"
     26 #include "llvm/IR/Intrinsics.h"
     27 #include "llvm/IR/Value.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 
     37 using namespace llvm;
     38 
     39 #define DEBUG_TYPE "bounds-checking"
     40 
     41 static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap",
     42                                   cl::desc("Use one trap block per function"));
     43 
     44 STATISTIC(ChecksAdded, "Bounds checks added");
     45 STATISTIC(ChecksSkipped, "Bounds checks skipped");
     46 STATISTIC(ChecksUnable, "Bounds checks unable to add");
     47 
     48 using 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.
     57 static 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.
    114 template <typename GetTrapBBT>
    115 static 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 
    143 static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI,
    144                               ScalarEvolution &SE) {
    145   const DataLayout &DL = F.getParent()->getDataLayout();
    146   ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(),
    147                                            /*RoundToAlign=*/true);
    148 
    149   // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
    150   // touching instructions
    151   SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo;
    152   for (Instruction &I : instructions(F)) {
    153     Value *Or = nullptr;
    154     BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));
    155     if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
    156       Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI,
    157                               ObjSizeEval, IRB, SE);
    158     } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
    159       Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(),
    160                               DL, TLI, ObjSizeEval, IRB, SE);
    161     } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) {
    162       Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(),
    163                               DL, TLI, ObjSizeEval, IRB, SE);
    164     } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) {
    165       Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(), DL,
    166                               TLI, ObjSizeEval, IRB, SE);
    167     }
    168     if (Or)
    169       TrapInfo.push_back(std::make_pair(&I, Or));
    170   }
    171 
    172   // Create a trapping basic block on demand using a callback. Depending on
    173   // flags, this will either create a single block for the entire function or
    174   // will create a fresh block every time it is called.
    175   BasicBlock *TrapBB = nullptr;
    176   auto GetTrapBB = [&TrapBB](BuilderTy &IRB) {
    177     if (TrapBB && SingleTrapBB)
    178       return TrapBB;
    179 
    180     Function *Fn = IRB.GetInsertBlock()->getParent();
    181     // FIXME: This debug location doesn't make a lot of sense in the
    182     // `SingleTrapBB` case.
    183     auto DebugLoc = IRB.getCurrentDebugLocation();
    184     IRBuilder<>::InsertPointGuard Guard(IRB);
    185     TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
    186     IRB.SetInsertPoint(TrapBB);
    187 
    188     auto *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap);
    189     CallInst *TrapCall = IRB.CreateCall(F, {});
    190     TrapCall->setDoesNotReturn();
    191     TrapCall->setDoesNotThrow();
    192     TrapCall->setDebugLoc(DebugLoc);
    193     IRB.CreateUnreachable();
    194 
    195     return TrapBB;
    196   };
    197 
    198   // Add the checks.
    199   for (const auto &Entry : TrapInfo) {
    200     Instruction *Inst = Entry.first;
    201     BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL));
    202     insertBoundsCheck(Entry.second, IRB, GetTrapBB);
    203   }
    204 
    205   return !TrapInfo.empty();
    206 }
    207 
    208 PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) {
    209   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
    210   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
    211 
    212   if (!addBoundsChecking(F, TLI, SE))
    213     return PreservedAnalyses::all();
    214 
    215   return PreservedAnalyses::none();
    216 }
    217 
    218 namespace {
    219 struct BoundsCheckingLegacyPass : public FunctionPass {
    220   static char ID;
    221 
    222   BoundsCheckingLegacyPass() : FunctionPass(ID) {
    223     initializeBoundsCheckingLegacyPassPass(*PassRegistry::getPassRegistry());
    224   }
    225 
    226   bool runOnFunction(Function &F) override {
    227     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
    228     auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
    229     return addBoundsChecking(F, TLI, SE);
    230   }
    231 
    232   void getAnalysisUsage(AnalysisUsage &AU) const override {
    233     AU.addRequired<TargetLibraryInfoWrapperPass>();
    234     AU.addRequired<ScalarEvolutionWrapperPass>();
    235   }
    236 };
    237 } // namespace
    238 
    239 char BoundsCheckingLegacyPass::ID = 0;
    240 INITIALIZE_PASS_BEGIN(BoundsCheckingLegacyPass, "bounds-checking",
    241                       "Run-time bounds checking", false, false)
    242 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
    243 INITIALIZE_PASS_END(BoundsCheckingLegacyPass, "bounds-checking",
    244                     "Run-time bounds checking", false, false)
    245 
    246 FunctionPass *llvm::createBoundsCheckingLegacyPass() {
    247   return new BoundsCheckingLegacyPass();
    248 }
    249