Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- SanitizerCoverage.cpp - coverage instrumentation for sanitizers ---===//
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
// Coverage instrumentation done on LLVM IR level, works with Sanitizers.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/ADT/ArrayRef.h"
15
#include "llvm/ADT/SmallVector.h"
16
#include "llvm/Analysis/EHPersonalities.h"
17
#include "llvm/Analysis/PostDominators.h"
18
#include "llvm/IR/CFG.h"
19
#include "llvm/IR/CallSite.h"
20
#include "llvm/IR/Constant.h"
21
#include "llvm/IR/DataLayout.h"
22
#include "llvm/IR/DebugInfo.h"
23
#include "llvm/IR/Dominators.h"
24
#include "llvm/IR/Function.h"
25
#include "llvm/IR/GlobalVariable.h"
26
#include "llvm/IR/IRBuilder.h"
27
#include "llvm/IR/InlineAsm.h"
28
#include "llvm/IR/IntrinsicInst.h"
29
#include "llvm/IR/Intrinsics.h"
30
#include "llvm/IR/LLVMContext.h"
31
#include "llvm/IR/MDBuilder.h"
32
#include "llvm/IR/Module.h"
33
#include "llvm/IR/Type.h"
34
#include "llvm/Support/CommandLine.h"
35
#include "llvm/Support/Debug.h"
36
#include "llvm/Support/raw_ostream.h"
37
#include "llvm/Transforms/Instrumentation.h"
38
#include "llvm/Transforms/Scalar.h"
39
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
40
#include "llvm/Transforms/Utils/ModuleUtils.h"
41
42
using namespace llvm;
43
44
#define DEBUG_TYPE "sancov"
45
46
static const char *const SanCovTracePCIndirName =
47
    "__sanitizer_cov_trace_pc_indir";
48
static const char *const SanCovTracePCName = "__sanitizer_cov_trace_pc";
49
static const char *const SanCovTraceCmp1 = "__sanitizer_cov_trace_cmp1";
50
static const char *const SanCovTraceCmp2 = "__sanitizer_cov_trace_cmp2";
51
static const char *const SanCovTraceCmp4 = "__sanitizer_cov_trace_cmp4";
52
static const char *const SanCovTraceCmp8 = "__sanitizer_cov_trace_cmp8";
53
static const char *const SanCovTraceConstCmp1 =
54
    "__sanitizer_cov_trace_const_cmp1";
55
static const char *const SanCovTraceConstCmp2 =
56
    "__sanitizer_cov_trace_const_cmp2";
57
static const char *const SanCovTraceConstCmp4 =
58
    "__sanitizer_cov_trace_const_cmp4";
59
static const char *const SanCovTraceConstCmp8 =
60
    "__sanitizer_cov_trace_const_cmp8";
61
static const char *const SanCovTraceDiv4 = "__sanitizer_cov_trace_div4";
62
static const char *const SanCovTraceDiv8 = "__sanitizer_cov_trace_div8";
63
static const char *const SanCovTraceGep = "__sanitizer_cov_trace_gep";
64
static const char *const SanCovTraceSwitchName = "__sanitizer_cov_trace_switch";
65
static const char *const SanCovModuleCtorName = "sancov.module_ctor";
66
static const uint64_t SanCtorAndDtorPriority = 2;
67
68
static const char *const SanCovTracePCGuardName =
69
    "__sanitizer_cov_trace_pc_guard";
70
static const char *const SanCovTracePCGuardInitName =
71
    "__sanitizer_cov_trace_pc_guard_init";
72
static const char *const SanCov8bitCountersInitName =
73
    "__sanitizer_cov_8bit_counters_init";
74
static const char *const SanCovPCsInitName = "__sanitizer_cov_pcs_init";
75
76
static const char *const SanCovGuardsSectionName = "sancov_guards";
77
static const char *const SanCovCountersSectionName = "sancov_cntrs";
78
static const char *const SanCovPCsSectionName = "sancov_pcs";
79
80
static const char *const SanCovLowestStackName = "__sancov_lowest_stack";
81
82
static cl::opt<int> ClCoverageLevel(
83
    "sanitizer-coverage-level",
84
    cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
85
             "3: all blocks and critical edges"),
86
    cl::Hidden, cl::init(0));
87
88
static cl::opt<bool> ClTracePC("sanitizer-coverage-trace-pc",
89
                               cl::desc("Experimental pc tracing"), cl::Hidden,
90
                               cl::init(false));
91
92
static cl::opt<bool> ClTracePCGuard("sanitizer-coverage-trace-pc-guard",
93
                                    cl::desc("pc tracing with a guard"),
94
                                    cl::Hidden, cl::init(false));
95
96
// If true, we create a global variable that contains PCs of all instrumented
97
// BBs, put this global into a named section, and pass this section's bounds
98
// to __sanitizer_cov_pcs_init.
99
// This way the coverage instrumentation does not need to acquire the PCs
100
// at run-time. Works with trace-pc-guard and inline-8bit-counters.
101
static cl::opt<bool> ClCreatePCTable("sanitizer-coverage-pc-table",
102
                                     cl::desc("create a static PC table"),
103
                                     cl::Hidden, cl::init(false));
104
105
static cl::opt<bool>
106
    ClInline8bitCounters("sanitizer-coverage-inline-8bit-counters",
107
                         cl::desc("increments 8-bit counter for every edge"),
108
                         cl::Hidden, cl::init(false));
109
110
static cl::opt<bool>
111
    ClCMPTracing("sanitizer-coverage-trace-compares",
112
                 cl::desc("Tracing of CMP and similar instructions"),
113
                 cl::Hidden, cl::init(false));
114
115
static cl::opt<bool> ClDIVTracing("sanitizer-coverage-trace-divs",
116
                                  cl::desc("Tracing of DIV instructions"),
117
                                  cl::Hidden, cl::init(false));
118
119
static cl::opt<bool> ClGEPTracing("sanitizer-coverage-trace-geps",
120
                                  cl::desc("Tracing of GEP instructions"),
121
                                  cl::Hidden, cl::init(false));
122
123
static cl::opt<bool>
124
    ClPruneBlocks("sanitizer-coverage-prune-blocks",
125
                  cl::desc("Reduce the number of instrumented blocks"),
126
                  cl::Hidden, cl::init(true));
127
128
static cl::opt<bool> ClStackDepth("sanitizer-coverage-stack-depth",
129
                                  cl::desc("max stack depth tracing"),
130
                                  cl::Hidden, cl::init(false));
131
132
namespace {
133
134
31
SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) {
135
31
  SanitizerCoverageOptions Res;
136
31
  switch (LegacyCoverageLevel) {
137
1
  case 0:
138
1
    Res.CoverageType = SanitizerCoverageOptions::SCK_None;
139
1
    break;
140
11
  case 1:
141
11
    Res.CoverageType = SanitizerCoverageOptions::SCK_Function;
142
11
    break;
143
2
  case 2:
144
2
    Res.CoverageType = SanitizerCoverageOptions::SCK_BB;
145
2
    break;
146
11
  case 3:
147
11
    Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
148
11
    break;
149
6
  case 4:
150
6
    Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
151
6
    Res.IndirectCalls = true;
152
6
    break;
153
31
  }
154
31
  return Res;
155
31
}
156
157
31
SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) {
158
31
  // Sets CoverageType and IndirectCalls.
159
31
  SanitizerCoverageOptions CLOpts = getOptions(ClCoverageLevel);
160
31
  Options.CoverageType = std::max(Options.CoverageType, CLOpts.CoverageType);
161
31
  Options.IndirectCalls |= CLOpts.IndirectCalls;
162
31
  Options.TraceCmp |= ClCMPTracing;
163
31
  Options.TraceDiv |= ClDIVTracing;
164
31
  Options.TraceGep |= ClGEPTracing;
165
31
  Options.TracePC |= ClTracePC;
166
31
  Options.TracePCGuard |= ClTracePCGuard;
167
31
  Options.Inline8bitCounters |= ClInline8bitCounters;
168
31
  Options.PCTable |= ClCreatePCTable;
169
31
  Options.NoPrune |= !ClPruneBlocks;
170
31
  Options.StackDepth |= ClStackDepth;
171
31
  if (
!Options.TracePCGuard && 31
!Options.TracePC22
&&
172
31
      
!Options.Inline8bitCounters16
&&
!Options.StackDepth14
)
173
13
    Options.TracePCGuard = true; // TracePCGuard is default.
174
31
  return Options;
175
31
}
176
177
class SanitizerCoverageModule : public ModulePass {
178
public:
179
  SanitizerCoverageModule(
180
      const SanitizerCoverageOptions &Options = SanitizerCoverageOptions())
181
31
      : ModulePass(ID), Options(OverrideFromCL(Options)) {
182
31
    initializeSanitizerCoverageModulePass(*PassRegistry::getPassRegistry());
183
31
  }
184
  bool runOnModule(Module &M) override;
185
  bool runOnFunction(Function &F);
186
  static char ID; // Pass identification, replacement for typeid
187
0
  StringRef getPassName() const override { return "SanitizerCoverageModule"; }
188
189
31
  void getAnalysisUsage(AnalysisUsage &AU) const override {
190
31
    AU.addRequired<DominatorTreeWrapperPass>();
191
31
    AU.addRequired<PostDominatorTreeWrapperPass>();
192
31
  }
193
194
private:
195
  void InjectCoverageForIndirectCalls(Function &F,
196
                                      ArrayRef<Instruction *> IndirCalls);
197
  void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
198
  void InjectTraceForDiv(Function &F,
199
                         ArrayRef<BinaryOperator *> DivTraceTargets);
200
  void InjectTraceForGep(Function &F,
201
                         ArrayRef<GetElementPtrInst *> GepTraceTargets);
202
  void InjectTraceForSwitch(Function &F,
203
                            ArrayRef<Instruction *> SwitchTraceTargets);
204
  bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks,
205
                      bool IsLeafFunc = true);
206
  GlobalVariable *CreateFunctionLocalArrayInSection(size_t NumElements,
207
                                                    Function &F, Type *Ty,
208
                                                    const char *Section);
209
  GlobalVariable *CreatePCArray(Function &F, ArrayRef<BasicBlock *> AllBlocks);
210
  void CreateFunctionLocalArrays(Function &F, ArrayRef<BasicBlock *> AllBlocks);
211
  void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx,
212
                             bool IsLeafFunc = true);
213
  Function *CreateInitCallsForSections(Module &M, const char *InitFunctionName,
214
                                       Type *Ty, const char *Section);
215
  std::pair<GlobalVariable *, GlobalVariable *>
216
  CreateSecStartEnd(Module &M, const char *Section, Type *Ty);
217
218
12
  void SetNoSanitizeMetadata(Instruction *I) {
219
12
    I->setMetadata(I->getModule()->getMDKindID("nosanitize"),
220
12
                   MDNode::get(*C, None));
221
12
  }
222
223
  std::string getSectionName(const std::string &Section) const;
224
  std::string getSectionStart(const std::string &Section) const;
225
  std::string getSectionEnd(const std::string &Section) const;
226
  Function *SanCovTracePCIndir;
227
  Function *SanCovTracePC, *SanCovTracePCGuard;
228
  Function *SanCovTraceCmpFunction[4];
229
  Function *SanCovTraceConstCmpFunction[4];
230
  Function *SanCovTraceDivFunction[2];
231
  Function *SanCovTraceGepFunction;
232
  Function *SanCovTraceSwitchFunction;
233
  GlobalVariable *SanCovLowestStack;
234
  InlineAsm *EmptyAsm;
235
  Type *IntptrTy, *IntptrPtrTy, *Int64Ty, *Int64PtrTy, *Int32Ty, *Int32PtrTy,
236
      *Int16Ty, *Int8Ty, *Int8PtrTy;
237
  Module *CurModule;
238
  Triple TargetTriple;
239
  LLVMContext *C;
240
  const DataLayout *DL;
241
242
  GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
243
  GlobalVariable *Function8bitCounterArray;  // for inline-8bit-counters.
244
  GlobalVariable *FunctionPCsArray;  // for pc-table.
245
  SmallVector<GlobalValue *, 20> GlobalsToAppendToUsed;
246
247
  SanitizerCoverageOptions Options;
248
};
249
250
} // namespace
251
252
std::pair<GlobalVariable *, GlobalVariable *>
253
SanitizerCoverageModule::CreateSecStartEnd(Module &M, const char *Section,
254
24
                                           Type *Ty) {
255
24
  GlobalVariable *SecStart =
256
24
      new GlobalVariable(M, Ty, false, GlobalVariable::ExternalLinkage, nullptr,
257
24
                         getSectionStart(Section));
258
24
  SecStart->setVisibility(GlobalValue::HiddenVisibility);
259
24
  GlobalVariable *SecEnd =
260
24
      new GlobalVariable(M, Ty, false, GlobalVariable::ExternalLinkage,
261
24
                         nullptr, getSectionEnd(Section));
262
24
  SecEnd->setVisibility(GlobalValue::HiddenVisibility);
263
24
264
24
  return std::make_pair(SecStart, SecEnd);
265
24
}
266
267
268
Function *SanitizerCoverageModule::CreateInitCallsForSections(
269
    Module &M, const char *InitFunctionName, Type *Ty,
270
22
    const char *Section) {
271
22
  IRBuilder<> IRB(M.getContext());
272
22
  auto SecStartEnd = CreateSecStartEnd(M, Section, Ty);
273
22
  auto SecStart = SecStartEnd.first;
274
22
  auto SecEnd = SecStartEnd.second;
275
22
  Function *CtorFunc;
276
22
  std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
277
22
      M, SanCovModuleCtorName, InitFunctionName, {Ty, Ty},
278
22
      {IRB.CreatePointerCast(SecStart, Ty), IRB.CreatePointerCast(SecEnd, Ty)});
279
22
280
22
  if (
TargetTriple.supportsCOMDAT()22
) {
281
20
    // Use comdat to dedup CtorFunc.
282
20
    CtorFunc->setComdat(M.getOrInsertComdat(SanCovModuleCtorName));
283
20
    appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc);
284
22
  } else {
285
2
    appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
286
2
  }
287
22
  return CtorFunc;
288
22
}
289
290
31
bool SanitizerCoverageModule::runOnModule(Module &M) {
291
31
  if (Options.CoverageType == SanitizerCoverageOptions::SCK_None)
292
1
    return false;
293
30
  C = &(M.getContext());
294
30
  DL = &M.getDataLayout();
295
30
  CurModule = &M;
296
30
  TargetTriple = Triple(M.getTargetTriple());
297
30
  FunctionGuardArray = nullptr;
298
30
  Function8bitCounterArray = nullptr;
299
30
  FunctionPCsArray = nullptr;
300
30
  IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
301
30
  IntptrPtrTy = PointerType::getUnqual(IntptrTy);
302
30
  Type *VoidTy = Type::getVoidTy(*C);
303
30
  IRBuilder<> IRB(*C);
304
30
  Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
305
30
  Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
306
30
  Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty());
307
30
  Int64Ty = IRB.getInt64Ty();
308
30
  Int32Ty = IRB.getInt32Ty();
309
30
  Int16Ty = IRB.getInt16Ty();
310
30
  Int8Ty = IRB.getInt8Ty();
311
30
312
30
  SanCovTracePCIndir = checkSanitizerInterfaceFunction(
313
30
      M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy));
314
30
  SanCovTraceCmpFunction[0] =
315
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
316
30
          SanCovTraceCmp1, VoidTy, IRB.getInt8Ty(), IRB.getInt8Ty()));
317
30
  SanCovTraceCmpFunction[1] = checkSanitizerInterfaceFunction(
318
30
      M.getOrInsertFunction(SanCovTraceCmp2, VoidTy, IRB.getInt16Ty(),
319
30
                            IRB.getInt16Ty()));
320
30
  SanCovTraceCmpFunction[2] = checkSanitizerInterfaceFunction(
321
30
      M.getOrInsertFunction(SanCovTraceCmp4, VoidTy, IRB.getInt32Ty(),
322
30
                            IRB.getInt32Ty()));
323
30
  SanCovTraceCmpFunction[3] =
324
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
325
30
          SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty));
326
30
327
30
  SanCovTraceConstCmpFunction[0] =
328
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
329
30
          SanCovTraceConstCmp1, VoidTy, Int8Ty, Int8Ty));
330
30
  SanCovTraceConstCmpFunction[1] =
331
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
332
30
          SanCovTraceConstCmp2, VoidTy, Int16Ty, Int16Ty));
333
30
  SanCovTraceConstCmpFunction[2] =
334
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
335
30
          SanCovTraceConstCmp4, VoidTy, Int32Ty, Int32Ty));
336
30
  SanCovTraceConstCmpFunction[3] =
337
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
338
30
          SanCovTraceConstCmp8, VoidTy, Int64Ty, Int64Ty));
339
30
340
30
  SanCovTraceDivFunction[0] =
341
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
342
30
          SanCovTraceDiv4, VoidTy, IRB.getInt32Ty()));
343
30
  SanCovTraceDivFunction[1] =
344
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
345
30
          SanCovTraceDiv8, VoidTy, Int64Ty));
346
30
  SanCovTraceGepFunction =
347
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
348
30
          SanCovTraceGep, VoidTy, IntptrTy));
349
30
  SanCovTraceSwitchFunction =
350
30
      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
351
30
          SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy));
352
30
353
30
  Constant *SanCovLowestStackConstant =
354
30
      M.getOrInsertGlobal(SanCovLowestStackName, IntptrTy);
355
30
  SanCovLowestStack = cast<GlobalVariable>(SanCovLowestStackConstant);
356
30
  SanCovLowestStack->setThreadLocalMode(
357
30
      GlobalValue::ThreadLocalMode::InitialExecTLSModel);
358
30
  if (
Options.StackDepth && 30
!SanCovLowestStack->isDeclaration()2
)
359
2
    SanCovLowestStack->setInitializer(Constant::getAllOnesValue(IntptrTy));
360
30
361
30
  // Make sure smaller parameters are zero-extended to i64 as required by the
362
30
  // x86_64 ABI.
363
30
  if (
TargetTriple.getArch() == Triple::x86_6430
) {
364
96
    for (int i = 0; 
i < 396
;
i++72
) {
365
72
      SanCovTraceCmpFunction[i]->addParamAttr(0, Attribute::ZExt);
366
72
      SanCovTraceCmpFunction[i]->addParamAttr(1, Attribute::ZExt);
367
72
      SanCovTraceConstCmpFunction[i]->addParamAttr(0, Attribute::ZExt);
368
72
      SanCovTraceConstCmpFunction[i]->addParamAttr(1, Attribute::ZExt);
369
72
    }
370
24
    SanCovTraceDivFunction[0]->addParamAttr(0, Attribute::ZExt);
371
24
  }
372
30
373
30
374
30
  // We insert an empty inline asm after cov callbacks to avoid callback merge.
375
30
  EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
376
30
                            StringRef(""), StringRef(""),
377
30
                            /*hasSideEffects=*/true);
378
30
379
30
  SanCovTracePC = checkSanitizerInterfaceFunction(
380
30
      M.getOrInsertFunction(SanCovTracePCName, VoidTy));
381
30
  SanCovTracePCGuard = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
382
30
      SanCovTracePCGuardName, VoidTy, Int32PtrTy));
383
30
384
30
  for (auto &F : M)
385
530
    runOnFunction(F);
386
30
387
30
  Function *Ctor = nullptr;
388
30
389
30
  if (FunctionGuardArray)
390
20
    Ctor = CreateInitCallsForSections(M, SanCovTracePCGuardInitName, Int32PtrTy,
391
20
                                      SanCovGuardsSectionName);
392
30
  if (Function8bitCounterArray)
393
2
    Ctor = CreateInitCallsForSections(M, SanCov8bitCountersInitName, Int8PtrTy,
394
2
                                      SanCovCountersSectionName);
395
30
  if (
Ctor && 30
Options.PCTable22
) {
396
2
    auto SecStartEnd = CreateSecStartEnd(M, SanCovPCsSectionName, IntptrPtrTy);
397
2
    Function *InitFunction = declareSanitizerInitFunction(
398
2
        M, SanCovPCsInitName, {IntptrPtrTy, IntptrPtrTy});
399
2
    IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
400
2
    IRBCtor.CreateCall(InitFunction,
401
2
                       {IRB.CreatePointerCast(SecStartEnd.first, IntptrPtrTy),
402
2
                        IRB.CreatePointerCast(SecStartEnd.second, IntptrPtrTy)});
403
2
  }
404
30
  // We don't reference these arrays directly in any of our runtime functions,
405
30
  // so we need to prevent them from being dead stripped.
406
30
  if (TargetTriple.isOSBinFormatMachO())
407
2
    appendToUsed(M, GlobalsToAppendToUsed);
408
31
  return true;
409
31
}
410
411
// True if block has successors and it dominates all of them.
412
51
static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) {
413
51
  if (succ_begin(BB) == succ_end(BB))
414
15
    return false;
415
36
416
36
  
for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) 36
{
417
41
    if (!DT->dominates(BB, SUCC))
418
30
      return false;
419
6
  }
420
6
421
6
  return true;
422
6
}
423
424
// True if block has predecessors and it postdominates all of them.
425
static bool isFullPostDominator(const BasicBlock *BB,
426
45
                                const PostDominatorTree *PDT) {
427
45
  if (pred_begin(BB) == pred_end(BB))
428
0
    return false;
429
45
430
45
  
for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) 45
{
431
60
    if (!PDT->dominates(BB, PRED))
432
30
      return false;
433
15
  }
434
15
435
15
  return true;
436
15
}
437
438
static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB,
439
                                  const DominatorTree *DT,
440
                                  const PostDominatorTree *PDT,
441
119
                                  const SanitizerCoverageOptions &Options) {
442
119
  // Don't insert coverage for unreachable blocks: we will never call
443
119
  // __sanitizer_cov() for them, so counting them in
444
119
  // NumberOfInstrumentedBlocks() might complicate calculation of code coverage
445
119
  // percentage. Also, unreachable instructions frequently have no debug
446
119
  // locations.
447
119
  if (isa<UnreachableInst>(BB->getTerminator()))
448
2
    return false;
449
117
450
117
  // Don't insert coverage into blocks without a valid insertion point
451
117
  // (catchswitch blocks).
452
117
  
if (117
BB->getFirstInsertionPt() == BB->end()117
)
453
1
    return false;
454
116
455
116
  
if (116
Options.NoPrune || 116
&F.getEntryBlock() == BB106
)
456
57
    return true;
457
59
458
59
  
if (59
Options.CoverageType == SanitizerCoverageOptions::SCK_Function &&
459
8
      &F.getEntryBlock() != BB)
460
8
    return false;
461
51
462
51
  // Do not instrument full dominators, or full post-dominators with multiple
463
51
  // predecessors.
464
51
  return !isFullDominator(BB, DT)
465
45
    && 
!(isFullPostDominator(BB, PDT) && 45
!BB->getSinglePredecessor()15
);
466
119
}
467
468
530
bool SanitizerCoverageModule::runOnFunction(Function &F) {
469
530
  if (F.empty())
470
475
    return false;
471
55
  
if (55
F.getName().find(".module_ctor") != std::string::npos55
)
472
0
    return false; // Should not instrument sanitizer init functions.
473
55
  
if (55
F.getName().startswith("__sanitizer_")55
)
474
0
    return false;  // Don't instrument __sanitizer_* callbacks.
475
55
  // Don't touch available_externally functions, their actual body is elewhere.
476
55
  
if (55
F.getLinkage() == GlobalValue::AvailableExternallyLinkage55
)
477
3
    return false;
478
52
  // Don't instrument MSVC CRT configuration helpers. They may run before normal
479
52
  // initialization.
480
52
  
if (52
F.getName() == "__local_stdio_printf_options" ||
481
52
      F.getName() == "__local_stdio_scanf_options")
482
0
    return false;
483
52
  // Don't instrument functions using SEH for now. Splitting basic blocks like
484
52
  // we do for coverage breaks WinEHPrepare.
485
52
  // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
486
52
  
if (52
F.hasPersonalityFn() &&
487
3
      isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
488
2
    return false;
489
50
  
if (50
Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge50
)
490
26
    SplitAllCriticalEdges(F);
491
50
  SmallVector<Instruction *, 8> IndirCalls;
492
50
  SmallVector<BasicBlock *, 16> BlocksToInstrument;
493
50
  SmallVector<Instruction *, 8> CmpTraceTargets;
494
50
  SmallVector<Instruction *, 8> SwitchTraceTargets;
495
50
  SmallVector<BinaryOperator *, 8> DivTraceTargets;
496
50
  SmallVector<GetElementPtrInst *, 8> GepTraceTargets;
497
50
498
50
  const DominatorTree *DT =
499
50
      &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
500
50
  const PostDominatorTree *PDT =
501
50
      &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree();
502
50
  bool IsLeafFunc = true;
503
50
504
119
  for (auto &BB : F) {
505
119
    if (shouldInstrumentBlock(F, &BB, DT, PDT, Options))
506
88
      BlocksToInstrument.push_back(&BB);
507
249
    for (auto &Inst : BB) {
508
249
      if (
Options.IndirectCalls249
) {
509
73
        CallSite CS(&Inst);
510
73
        if (
CS && 73
!CS.getCalledFunction()9
)
511
9
          IndirCalls.push_back(&Inst);
512
73
      }
513
249
      if (
Options.TraceCmp249
) {
514
36
        if (isa<ICmpInst>(&Inst))
515
11
          CmpTraceTargets.push_back(&Inst);
516
36
        if (isa<SwitchInst>(&Inst))
517
2
          SwitchTraceTargets.push_back(&Inst);
518
36
      }
519
249
      if (Options.TraceDiv)
520
6
        
if (BinaryOperator *6
BO6
= dyn_cast<BinaryOperator>(&Inst))
521
3
          
if (3
BO->getOpcode() == Instruction::SDiv ||
522
1
              BO->getOpcode() == Instruction::UDiv)
523
3
            DivTraceTargets.push_back(BO);
524
249
      if (Options.TraceGep)
525
11
        
if (GetElementPtrInst *11
GEP11
= dyn_cast<GetElementPtrInst>(&Inst))
526
3
          GepTraceTargets.push_back(GEP);
527
249
      if (Options.StackDepth)
528
8
        
if (8
isa<InvokeInst>(Inst) ||
529
8
            
(isa<CallInst>(Inst) && 8
!isa<IntrinsicInst>(Inst)2
))
530
2
          IsLeafFunc = false;
531
249
    }
532
119
  }
533
530
534
530
  InjectCoverage(F, BlocksToInstrument, IsLeafFunc);
535
530
  InjectCoverageForIndirectCalls(F, IndirCalls);
536
530
  InjectTraceForCmp(F, CmpTraceTargets);
537
530
  InjectTraceForSwitch(F, SwitchTraceTargets);
538
530
  InjectTraceForDiv(F, DivTraceTargets);
539
530
  InjectTraceForGep(F, GepTraceTargets);
540
530
  return true;
541
530
}
542
543
GlobalVariable *SanitizerCoverageModule::CreateFunctionLocalArrayInSection(
544
40
    size_t NumElements, Function &F, Type *Ty, const char *Section) {
545
40
  ArrayType *ArrayTy = ArrayType::get(Ty, NumElements);
546
40
  auto Array = new GlobalVariable(
547
40
      *CurModule, ArrayTy, false, GlobalVariable::PrivateLinkage,
548
40
      Constant::getNullValue(ArrayTy), "__sancov_gen_");
549
40
  if (auto Comdat = F.getComdat())
550
2
    Array->setComdat(Comdat);
551
40
  Array->setSection(getSectionName(Section));
552
2
  Array->setAlignment(Ty->isPointerTy() ? DL->getPointerSize()
553
38
                                        : Ty->getPrimitiveSizeInBits() / 8);
554
40
  return Array;
555
40
}
556
557
GlobalVariable *
558
SanitizerCoverageModule::CreatePCArray(Function &F,
559
2
                                       ArrayRef<BasicBlock *> AllBlocks) {
560
2
  size_t N = AllBlocks.size();
561
2
  assert(N);
562
2
  SmallVector<Constant *, 32> PCs;
563
2
  IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
564
8
  for (size_t i = 0; 
i < N8
;
i++6
) {
565
6
    if (
&F.getEntryBlock() == AllBlocks[i]6
) {
566
2
      PCs.push_back((Constant *)IRB.CreatePointerCast(&F, IntptrPtrTy));
567
2
      PCs.push_back((Constant *)IRB.CreateIntToPtr(
568
2
          ConstantInt::get(IntptrTy, 1), IntptrPtrTy));
569
6
    } else {
570
4
      PCs.push_back((Constant *)IRB.CreatePointerCast(
571
4
          BlockAddress::get(AllBlocks[i]), IntptrPtrTy));
572
4
      PCs.push_back((Constant *)IRB.CreateIntToPtr(
573
4
          ConstantInt::get(IntptrTy, 0), IntptrPtrTy));
574
4
    }
575
6
  }
576
2
  auto *PCArray = CreateFunctionLocalArrayInSection(N * 2, F, IntptrPtrTy,
577
2
                                                    SanCovPCsSectionName);
578
2
  PCArray->setInitializer(
579
2
      ConstantArray::get(ArrayType::get(IntptrPtrTy, N * 2), PCs));
580
2
  PCArray->setConstant(true);
581
2
582
2
  return PCArray;
583
2
}
584
585
void SanitizerCoverageModule::CreateFunctionLocalArrays(
586
48
    Function &F, ArrayRef<BasicBlock *> AllBlocks) {
587
48
  if (
Options.TracePCGuard48
) {
588
36
    FunctionGuardArray = CreateFunctionLocalArrayInSection(
589
36
        AllBlocks.size(), F, Int32Ty, SanCovGuardsSectionName);
590
36
    GlobalsToAppendToUsed.push_back(FunctionGuardArray);
591
36
  }
592
48
  if (
Options.Inline8bitCounters48
) {
593
2
    Function8bitCounterArray = CreateFunctionLocalArrayInSection(
594
2
        AllBlocks.size(), F, Int8Ty, SanCovCountersSectionName);
595
2
    GlobalsToAppendToUsed.push_back(Function8bitCounterArray);
596
2
  }
597
48
  if (
Options.PCTable48
) {
598
2
    FunctionPCsArray = CreatePCArray(F, AllBlocks);
599
2
    GlobalsToAppendToUsed.push_back(FunctionPCsArray);
600
2
  }
601
48
}
602
603
bool SanitizerCoverageModule::InjectCoverage(Function &F,
604
                                             ArrayRef<BasicBlock *> AllBlocks,
605
50
                                             bool IsLeafFunc) {
606
50
  if (
AllBlocks.empty()50
)
return false2
;
607
48
  CreateFunctionLocalArrays(F, AllBlocks);
608
136
  for (size_t i = 0, N = AllBlocks.size(); 
i < N136
;
i++88
)
609
88
    InjectCoverageAtBlock(F, *AllBlocks[i], i, IsLeafFunc);
610
50
  return true;
611
50
}
612
613
// On every indirect call we call a run-time function
614
// __sanitizer_cov_indir_call* with two parameters:
615
//   - callee address,
616
//   - global cache array that contains CacheSize pointers (zero-initialized).
617
//     The cache is used to speed up recording the caller-callee pairs.
618
// The address of the caller is passed implicitly via caller PC.
619
// CacheSize is encoded in the name of the run-time function.
620
void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
621
50
    Function &F, ArrayRef<Instruction *> IndirCalls) {
622
50
  if (IndirCalls.empty())
623
47
    return;
624
50
  assert(Options.TracePC || Options.TracePCGuard || Options.Inline8bitCounters);
625
9
  for (auto I : IndirCalls) {
626
9
    IRBuilder<> IRB(I);
627
9
    CallSite CS(I);
628
9
    Value *Callee = CS.getCalledValue();
629
9
    if (isa<InlineAsm>(Callee))
630
3
      continue;
631
6
    IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy));
632
6
  }
633
50
}
634
635
// For every switch statement we insert a call:
636
// __sanitizer_cov_trace_switch(CondValue,
637
//      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
638
639
void SanitizerCoverageModule::InjectTraceForSwitch(
640
50
    Function &, ArrayRef<Instruction *> SwitchTraceTargets) {
641
2
  for (auto I : SwitchTraceTargets) {
642
2
    if (SwitchInst *
SI2
= dyn_cast<SwitchInst>(I)) {
643
2
      IRBuilder<> IRB(I);
644
2
      SmallVector<Constant *, 16> Initializers;
645
2
      Value *Cond = SI->getCondition();
646
2
      if (Cond->getType()->getScalarSizeInBits() >
647
2
          Int64Ty->getScalarSizeInBits())
648
1
        continue;
649
1
      Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
650
1
      Initializers.push_back(
651
1
          ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
652
1
      if (Cond->getType()->getScalarSizeInBits() <
653
1
          Int64Ty->getScalarSizeInBits())
654
1
        Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
655
3
      for (auto It : SI->cases()) {
656
3
        Constant *C = It.getCaseValue();
657
3
        if (C->getType()->getScalarSizeInBits() <
658
3
            Int64Ty->getScalarSizeInBits())
659
3
          C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
660
3
        Initializers.push_back(C);
661
3
      }
662
1
      std::sort(Initializers.begin() + 2, Initializers.end(),
663
3
                [](const Constant *A, const Constant *B) {
664
3
                  return cast<ConstantInt>(A)->getLimitedValue() <
665
3
                         cast<ConstantInt>(B)->getLimitedValue();
666
3
                });
667
2
      ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
668
2
      GlobalVariable *GV = new GlobalVariable(
669
2
          *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
670
2
          ConstantArray::get(ArrayOfInt64Ty, Initializers),
671
2
          "__sancov_gen_cov_switch_values");
672
2
      IRB.CreateCall(SanCovTraceSwitchFunction,
673
2
                     {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
674
2
    }
675
2
  }
676
50
}
677
678
void SanitizerCoverageModule::InjectTraceForDiv(
679
50
    Function &, ArrayRef<BinaryOperator *> DivTraceTargets) {
680
3
  for (auto BO : DivTraceTargets) {
681
3
    IRBuilder<> IRB(BO);
682
3
    Value *A1 = BO->getOperand(1);
683
3
    if (
isa<ConstantInt>(A1)3
)
continue1
;
684
2
    
if (2
!A1->getType()->isIntegerTy()2
)
685
0
      continue;
686
2
    uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType());
687
1
    int CallbackIdx = TypeSize == 32 ? 0 :
688
1
        
TypeSize == 64 ? 1
11
:
-10
;
689
2
    if (
CallbackIdx < 02
)
continue0
;
690
2
    auto Ty = Type::getIntNTy(*C, TypeSize);
691
2
    IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx],
692
2
                   {IRB.CreateIntCast(A1, Ty, true)});
693
2
  }
694
50
}
695
696
void SanitizerCoverageModule::InjectTraceForGep(
697
50
    Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) {
698
3
  for (auto GEP : GepTraceTargets) {
699
3
    IRBuilder<> IRB(GEP);
700
7
    for (auto I = GEP->idx_begin(); 
I != GEP->idx_end()7
;
++I4
)
701
4
      
if (4
!isa<ConstantInt>(*I) && 4
(*I)->getType()->isIntegerTy()4
)
702
3
        IRB.CreateCall(SanCovTraceGepFunction,
703
3
                       {IRB.CreateIntCast(*I, IntptrTy, true)});
704
3
  }
705
50
}
706
707
void SanitizerCoverageModule::InjectTraceForCmp(
708
50
    Function &, ArrayRef<Instruction *> CmpTraceTargets) {
709
11
  for (auto I : CmpTraceTargets) {
710
11
    if (ICmpInst *
ICMP11
= dyn_cast<ICmpInst>(I)) {
711
11
      IRBuilder<> IRB(ICMP);
712
11
      Value *A0 = ICMP->getOperand(0);
713
11
      Value *A1 = ICMP->getOperand(1);
714
11
      if (!A0->getType()->isIntegerTy())
715
0
        continue;
716
11
      uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
717
2
      int CallbackIdx = TypeSize == 8 ? 0 :
718
9
                        
TypeSize == 16 ? 9
12
:
719
7
                        
TypeSize == 32 ? 7
25
:
720
2
                        
TypeSize == 64 ? 2
32
:
-10
;
721
11
      if (
CallbackIdx < 011
)
continue0
;
722
11
      // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
723
11
      auto CallbackFunc = SanCovTraceCmpFunction[CallbackIdx];
724
11
      bool FirstIsConst = isa<ConstantInt>(A0);
725
11
      bool SecondIsConst = isa<ConstantInt>(A1);
726
11
      // If both are const, then we don't need such a comparison.
727
11
      if (
FirstIsConst && 11
SecondIsConst5
)
continue1
;
728
10
      // If only one is const, then make it the first callback argument.
729
10
      
if (10
FirstIsConst || 10
SecondIsConst6
) {
730
8
        CallbackFunc = SanCovTraceConstCmpFunction[CallbackIdx];
731
8
        if (SecondIsConst)
732
4
          std::swap(A0, A1);
733
8
      }
734
11
735
11
      auto Ty = Type::getIntNTy(*C, TypeSize);
736
11
      IRB.CreateCall(CallbackFunc, {IRB.CreateIntCast(A0, Ty, true),
737
11
              IRB.CreateIntCast(A1, Ty, true)});
738
11
    }
739
11
  }
740
50
}
741
742
void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
743
                                                    size_t Idx,
744
88
                                                    bool IsLeafFunc) {
745
88
  BasicBlock::iterator IP = BB.getFirstInsertionPt();
746
88
  bool IsEntryBB = &BB == &F.getEntryBlock();
747
88
  DebugLoc EntryLoc;
748
88
  if (
IsEntryBB88
) {
749
48
    if (auto SP = F.getSubprogram())
750
2
      EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP);
751
48
    // Keep static allocas and llvm.localescape calls in the entry block.  Even
752
48
    // if we aren't splitting the block, it's nice for allocas to be before
753
48
    // calls.
754
48
    IP = PrepareToSplitEntryBlock(BB, IP);
755
88
  } else {
756
40
    EntryLoc = IP->getDebugLoc();
757
40
  }
758
88
759
88
  IRBuilder<> IRB(&*IP);
760
88
  IRB.SetCurrentDebugLocation(EntryLoc);
761
88
  if (
Options.TracePC88
) {
762
32
    IRB.CreateCall(SanCovTracePC); // gets the PC using GET_CALLER_PC.
763
32
    IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
764
32
  }
765
88
  if (
Options.TracePCGuard88
) {
766
49
    auto GuardPtr = IRB.CreateIntToPtr(
767
49
        IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy),
768
49
                      ConstantInt::get(IntptrTy, Idx * 4)),
769
49
        Int32PtrTy);
770
49
    IRB.CreateCall(SanCovTracePCGuard, GuardPtr);
771
49
    IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
772
49
  }
773
88
  if (
Options.Inline8bitCounters88
) {
774
4
    auto CounterPtr = IRB.CreateGEP(
775
4
        Function8bitCounterArray,
776
4
        {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)});
777
4
    auto Load = IRB.CreateLoad(CounterPtr);
778
4
    auto Inc = IRB.CreateAdd(Load, ConstantInt::get(Int8Ty, 1));
779
4
    auto Store = IRB.CreateStore(Inc, CounterPtr);
780
4
    SetNoSanitizeMetadata(Load);
781
4
    SetNoSanitizeMetadata(Store);
782
4
  }
783
88
  if (
Options.StackDepth && 88
IsEntryBB6
&&
!IsLeafFunc6
) {
784
2
    // Check stack depth.  If it's the deepest so far, record it.
785
2
    Function *GetFrameAddr =
786
2
        Intrinsic::getDeclaration(F.getParent(), Intrinsic::frameaddress);
787
2
    auto FrameAddrPtr =
788
2
        IRB.CreateCall(GetFrameAddr, {Constant::getNullValue(Int32Ty)});
789
2
    auto FrameAddrInt = IRB.CreatePtrToInt(FrameAddrPtr, IntptrTy);
790
2
    auto LowestStack = IRB.CreateLoad(SanCovLowestStack);
791
2
    auto IsStackLower = IRB.CreateICmpULT(FrameAddrInt, LowestStack);
792
2
    auto ThenTerm = SplitBlockAndInsertIfThen(IsStackLower, &*IP, false);
793
2
    IRBuilder<> ThenIRB(ThenTerm);
794
2
    auto Store = ThenIRB.CreateStore(FrameAddrInt, SanCovLowestStack);
795
2
    SetNoSanitizeMetadata(LowestStack);
796
2
    SetNoSanitizeMetadata(Store);
797
2
  }
798
88
}
799
800
std::string
801
40
SanitizerCoverageModule::getSectionName(const std::string &Section) const {
802
40
  if (TargetTriple.getObjectFormat() == Triple::COFF)
803
6
    return ".SCOV$M";
804
34
  
if (34
TargetTriple.isOSBinFormatMachO()34
)
805
3
    return "__DATA,__" + Section;
806
31
  return "__" + Section;
807
31
}
808
809
std::string
810
24
SanitizerCoverageModule::getSectionStart(const std::string &Section) const {
811
24
  if (TargetTriple.isOSBinFormatMachO())
812
2
    return "\1section$start$__DATA$__" + Section;
813
22
  return "__start___" + Section;
814
22
}
815
816
std::string
817
24
SanitizerCoverageModule::getSectionEnd(const std::string &Section) const {
818
24
  if (TargetTriple.isOSBinFormatMachO())
819
2
    return "\1section$end$__DATA$__" + Section;
820
22
  return "__stop___" + Section;
821
22
}
822
823
824
char SanitizerCoverageModule::ID = 0;
825
7.91k
INITIALIZE_PASS_BEGIN7.91k
(SanitizerCoverageModule, "sancov",
826
7.91k
                      "SanitizerCoverage: TODO."
827
7.91k
                      "ModulePass",
828
7.91k
                      false, false)
829
7.91k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
830
7.91k
INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
831
7.91k
INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov",
832
                    "SanitizerCoverage: TODO."
833
                    "ModulePass",
834
                    false, false)
835
ModulePass *llvm::createSanitizerCoverageModulePass(
836
0
    const SanitizerCoverageOptions &Options) {
837
0
  return new SanitizerCoverageModule(Options);
838
0
}