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