text: //===- 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/Analysis/TargetLibraryInfo.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"
  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<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<TargetLibraryInfoWrapperPass>();
      }
  
    private:
      const TargetLibraryInfo *TLI;
      ObjectSizeOffsetEvaluator *ObjSizeEval;
      BuilderTy *Builder;
      Instruction *Inst;
      BasicBlock *TrapBB;
  
      BasicBlock *getTrapBB();
      void emitBranchToTrap(Value *Cmp = nullptr);
      bool instrument(Value *Ptr, Value *Val, const DataLayout &DL);
   };
  }
  
  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;
  
    BasicBlock::iterator 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,
                                  const DataLayout &DL) {
    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) {
    const DataLayout &DL = F.getParent()->getDataLayout();
    TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
  
    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 (Instruction *i : WorkList) {
      Inst = i;
  
      Builder->SetInsertPoint(Inst);
      if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
        MadeChange |= instrument(LI->getPointerOperand(), LI, DL);
      } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
        MadeChange |=
            instrument(SI->getPointerOperand(), SI->getValueOperand(), DL);
      } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) {
        MadeChange |=
            instrument(AI->getPointerOperand(), AI->getCompareOperand(), DL);
      } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) {
        MadeChange |=
            instrument(AI->getPointerOperand(), AI->getValOperand(), DL);
      } else {
        llvm_unreachable("unknown Instruction type");
      }
    }
    return MadeChange;
  }
  
  FunctionPass *llvm::createBoundsCheckingPass() {
    return new BoundsChecking();
  }
  