Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
9
#include "llvm/Transforms/Instrumentation/BoundsChecking.h"
10
#include "llvm/ADT/Statistic.h"
11
#include "llvm/ADT/Twine.h"
12
#include "llvm/Analysis/MemoryBuiltins.h"
13
#include "llvm/Analysis/ScalarEvolution.h"
14
#include "llvm/Analysis/TargetFolder.h"
15
#include "llvm/Analysis/TargetLibraryInfo.h"
16
#include "llvm/IR/BasicBlock.h"
17
#include "llvm/IR/Constants.h"
18
#include "llvm/IR/DataLayout.h"
19
#include "llvm/IR/Function.h"
20
#include "llvm/IR/IRBuilder.h"
21
#include "llvm/IR/InstIterator.h"
22
#include "llvm/IR/InstrTypes.h"
23
#include "llvm/IR/Instruction.h"
24
#include "llvm/IR/Instructions.h"
25
#include "llvm/IR/Intrinsics.h"
26
#include "llvm/IR/Value.h"
27
#include "llvm/Pass.h"
28
#include "llvm/Support/Casting.h"
29
#include "llvm/Support/CommandLine.h"
30
#include "llvm/Support/Debug.h"
31
#include "llvm/Support/ErrorHandling.h"
32
#include "llvm/Support/raw_ostream.h"
33
#include <cstdint>
34
#include <vector>
35
36
using namespace llvm;
37
38
#define DEBUG_TYPE "bounds-checking"
39
40
static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap",
41
                                  cl::desc("Use one trap block per function"));
42
43
STATISTIC(ChecksAdded, "Bounds checks added");
44
STATISTIC(ChecksSkipped, "Bounds checks skipped");
45
STATISTIC(ChecksUnable, "Bounds checks unable to add");
46
47
using BuilderTy = IRBuilder<TargetFolder>;
48
49
/// Gets the conditions under which memory accessing instructions will overflow.
50
///
51
/// \p Ptr is the pointer that will be read/written, and \p InstVal is either
52
/// the result from the load or the value being stored. It is used to determine
53
/// the size of memory block that is touched.
54
///
55
/// Returns the condition under which the access will overflow.
56
static Value *getBoundsCheckCond(Value *Ptr, Value *InstVal,
57
                                 const DataLayout &DL, TargetLibraryInfo &TLI,
58
                                 ObjectSizeOffsetEvaluator &ObjSizeEval,
59
91
                                 BuilderTy &IRB, ScalarEvolution &SE) {
60
91
  uint64_t NeededSize = DL.getTypeStoreSize(InstVal->getType());
61
91
  LLVM_DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize)
62
91
                    << " bytes\n");
63
91
64
91
  SizeOffsetEvalType SizeOffset = ObjSizeEval.compute(Ptr);
65
91
66
91
  if (!ObjSizeEval.bothKnown(SizeOffset)) {
67
13
    ++ChecksUnable;
68
13
    return nullptr;
69
13
  }
70
78
71
78
  Value *Size   = SizeOffset.first;
72
78
  Value *Offset = SizeOffset.second;
73
78
  ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size);
74
78
75
78
  Type *IntTy = DL.getIntPtrType(Ptr->getType());
76
78
  Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize);
77
78
78
78
  auto SizeRange = SE.getUnsignedRange(SE.getSCEV(Size));
79
78
  auto OffsetRange = SE.getUnsignedRange(SE.getSCEV(Offset));
80
78
  auto NeededSizeRange = SE.getUnsignedRange(SE.getSCEV(NeededSizeVal));
81
78
82
78
  // three checks are required to ensure safety:
83
78
  // . Offset >= 0  (since the offset is given from the base ptr)
84
78
  // . Size >= Offset  (unsigned)
85
78
  // . Size - Offset >= NeededSize  (unsigned)
86
78
  //
87
78
  // optimization: if Size >= 0 (signed), skip 1st check
88
78
  // FIXME: add NSW/NUW here?  -- we dont care if the subtraction overflows
89
78
  Value *ObjSize = IRB.CreateSub(Size, Offset);
90
78
  Value *Cmp2 = SizeRange.getUnsignedMin().uge(OffsetRange.getUnsignedMax())
91
78
                    ? 
ConstantInt::getFalse(Ptr->getContext())53
92
78
                    : 
IRB.CreateICmpULT(Size, Offset)25
;
93
78
  Value *Cmp3 = SizeRange.sub(OffsetRange)
94
78
                        .getUnsignedMin()
95
78
                        .uge(NeededSizeRange.getUnsignedMax())
96
78
                    ? 
ConstantInt::getFalse(Ptr->getContext())36
97
78
                    : 
IRB.CreateICmpULT(ObjSize, NeededSizeVal)42
;
98
78
  Value *Or = IRB.CreateOr(Cmp2, Cmp3);
99
78
  if ((!SizeCI || 
SizeCI->getValue().slt(0)62
) &&
100
78
      
!SizeRange.getSignedMin().isNonNegative()16
) {
101
14
    Value *Cmp1 = IRB.CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0));
102
14
    Or = IRB.CreateOr(Cmp1, Or);
103
14
  }
104
78
105
78
  return Or;
106
78
}
107
108
/// Adds run-time bounds checks to memory accessing instructions.
109
///
110
/// \p Or is the condition that should guard the trap.
111
///
112
/// \p GetTrapBB is a callable that returns the trap BB to use on failure.
113
template <typename GetTrapBBT>
114
78
static void insertBoundsCheck(Value *Or, BuilderTy IRB, GetTrapBBT GetTrapBB) {
115
78
  // check if the comparison is always false
116
78
  ConstantInt *C = dyn_cast_or_null<ConstantInt>(Or);
117
78
  if (C) {
118
45
    ++ChecksSkipped;
119
45
    // If non-zero, nothing to do.
120
45
    if (!C->getZExtValue())
121
34
      return;
122
44
  }
123
44
  ++ChecksAdded;
124
44
125
44
  BasicBlock::iterator SplitI = IRB.GetInsertPoint();
126
44
  BasicBlock *OldBB = SplitI->getParent();
127
44
  BasicBlock *Cont = OldBB->splitBasicBlock(SplitI);
128
44
  OldBB->getTerminator()->eraseFromParent();
129
44
130
44
  if (C) {
131
11
    // If we have a constant zero, unconditionally branch.
132
11
    // FIXME: We should really handle this differently to bypass the splitting
133
11
    // the block.
134
11
    BranchInst::Create(GetTrapBB(IRB), OldBB);
135
11
    return;
136
11
  }
137
33
138
33
  // Create the conditional branch.
139
33
  BranchInst::Create(GetTrapBB(IRB), Cont, Or, OldBB);
140
33
}
141
142
static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI,
143
56
                              ScalarEvolution &SE) {
144
56
  const DataLayout &DL = F.getParent()->getDataLayout();
145
56
  ObjectSizeOpts EvalOpts;
146
56
  EvalOpts.RoundToAlign = true;
147
56
  ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(), EvalOpts);
148
56
149
56
  // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory
150
56
  // touching instructions
151
56
  SmallVector<std::pair<Instruction *, Value *>, 4> TrapInfo;
152
489
  for (Instruction &I : instructions(F)) {
153
489
    Value *Or = nullptr;
154
489
    BuilderTy IRB(I.getParent(), BasicBlock::iterator(&I), TargetFolder(DL));
155
489
    if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
156
64
      Or = getBoundsCheckCond(LI->getPointerOperand(), LI, DL, TLI,
157
64
                              ObjSizeEval, IRB, SE);
158
425
    } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
159
27
      Or = getBoundsCheckCond(SI->getPointerOperand(), SI->getValueOperand(),
160
27
                              DL, TLI, ObjSizeEval, IRB, SE);
161
398
    } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I)) {
162
0
      Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getCompareOperand(),
163
0
                              DL, TLI, ObjSizeEval, IRB, SE);
164
398
    } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I)) {
165
0
      Or = getBoundsCheckCond(AI->getPointerOperand(), AI->getValOperand(), DL,
166
0
                              TLI, ObjSizeEval, IRB, SE);
167
0
    }
168
489
    if (Or)
169
78
      TrapInfo.push_back(std::make_pair(&I, Or));
170
489
  }
171
56
172
56
  // Create a trapping basic block on demand using a callback. Depending on
173
56
  // flags, this will either create a single block for the entire function or
174
56
  // will create a fresh block every time it is called.
175
56
  BasicBlock *TrapBB = nullptr;
176
56
  auto GetTrapBB = [&TrapBB](BuilderTy &IRB) {
177
44
    if (TrapBB && 
SingleTrapBB6
)
178
1
      return TrapBB;
179
43
180
43
    Function *Fn = IRB.GetInsertBlock()->getParent();
181
43
    // FIXME: This debug location doesn't make a lot of sense in the
182
43
    // `SingleTrapBB` case.
183
43
    auto DebugLoc = IRB.getCurrentDebugLocation();
184
43
    IRBuilder<>::InsertPointGuard Guard(IRB);
185
43
    TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
186
43
    IRB.SetInsertPoint(TrapBB);
187
43
188
43
    auto *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap);
189
43
    CallInst *TrapCall = IRB.CreateCall(F, {});
190
43
    TrapCall->setDoesNotReturn();
191
43
    TrapCall->setDoesNotThrow();
192
43
    TrapCall->setDebugLoc(DebugLoc);
193
43
    IRB.CreateUnreachable();
194
43
195
43
    return TrapBB;
196
43
  };
197
56
198
56
  // Add the checks.
199
78
  for (const auto &Entry : TrapInfo) {
200
78
    Instruction *Inst = Entry.first;
201
78
    BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL));
202
78
    insertBoundsCheck(Entry.second, IRB, GetTrapBB);
203
78
  }
204
56
205
56
  return !TrapInfo.empty();
206
56
}
207
208
18
PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) {
209
18
  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
210
18
  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
211
18
212
18
  if (!addBoundsChecking(F, TLI, SE))
213
2
    return PreservedAnalyses::all();
214
16
215
16
  return PreservedAnalyses::none();
216
16
}
217
218
namespace {
219
struct BoundsCheckingLegacyPass : public FunctionPass {
220
  static char ID;
221
222
8
  BoundsCheckingLegacyPass() : FunctionPass(ID) {
223
8
    initializeBoundsCheckingLegacyPassPass(*PassRegistry::getPassRegistry());
224
8
  }
225
226
38
  bool runOnFunction(Function &F) override {
227
38
    auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
228
38
    auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
229
38
    return addBoundsChecking(F, TLI, SE);
230
38
  }
231
232
8
  void getAnalysisUsage(AnalysisUsage &AU) const override {
233
8
    AU.addRequired<TargetLibraryInfoWrapperPass>();
234
8
    AU.addRequired<ScalarEvolutionWrapperPass>();
235
8
  }
236
};
237
} // namespace
238
239
char BoundsCheckingLegacyPass::ID = 0;
240
11.0k
INITIALIZE_PASS_BEGIN(BoundsCheckingLegacyPass, "bounds-checking",
241
11.0k
                      "Run-time bounds checking", false, false)
242
11.0k
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
243
11.0k
INITIALIZE_PASS_END(BoundsCheckingLegacyPass, "bounds-checking",
244
                    "Run-time bounds checking", false, false)
245
246
1
FunctionPass *llvm::createBoundsCheckingLegacyPass() {
247
1
  return new BoundsCheckingLegacyPass();
248
1
}