contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp

   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 }