llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

   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/GlobalsModRef.h"
  17 #include "llvm/Analysis/PostDominators.h"
  18 #include "llvm/IR/Constant.h"
  19 #include "llvm/IR/Constants.h"
  20 #include "llvm/IR/DataLayout.h"
  21 #include "llvm/IR/Dominators.h"
  22 #include "llvm/IR/EHPersonalities.h"
  23 #include "llvm/IR/Function.h"
  24 #include "llvm/IR/GlobalVariable.h"
  25 #include "llvm/IR/IRBuilder.h"
  26 #include "llvm/IR/IntrinsicInst.h"
  27 #include "llvm/IR/Intrinsics.h"
  28 #include "llvm/IR/LLVMContext.h"
  29 #include "llvm/IR/MDBuilder.h"
  30 #include "llvm/IR/Module.h"
  31 #include "llvm/IR/Type.h"
  32 #include "llvm/IR/ValueSymbolTable.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/SpecialCaseList.h"
  35 #include "llvm/Support/VirtualFileSystem.h"
  36 #include "llvm/TargetParser/Triple.h"
  37 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  38 #include "llvm/Transforms/Utils/ModuleUtils.h"
  39
  40 using namespace llvm;
  41
  42 #define DEBUG_TYPE "sancov"
  43
  44 const char SanCovTracePCIndirName[] = "__sanitizer_cov_trace_pc_indir";
  45 const char SanCovTracePCName[] = "__sanitizer_cov_trace_pc";
  46 const char SanCovTraceCmp1[] = "__sanitizer_cov_trace_cmp1";
  47 const char SanCovTraceCmp2[] = "__sanitizer_cov_trace_cmp2";
  48 const char SanCovTraceCmp4[] = "__sanitizer_cov_trace_cmp4";
  49 const char SanCovTraceCmp8[] = "__sanitizer_cov_trace_cmp8";
  50 const char SanCovTraceConstCmp1[] = "__sanitizer_cov_trace_const_cmp1";
  51 const char SanCovTraceConstCmp2[] = "__sanitizer_cov_trace_const_cmp2";
  52 const char SanCovTraceConstCmp4[] = "__sanitizer_cov_trace_const_cmp4";
  53 const char SanCovTraceConstCmp8[] = "__sanitizer_cov_trace_const_cmp8";
  54 const char SanCovLoad1[] = "__sanitizer_cov_load1";
  55 const char SanCovLoad2[] = "__sanitizer_cov_load2";
  56 const char SanCovLoad4[] = "__sanitizer_cov_load4";
  57 const char SanCovLoad8[] = "__sanitizer_cov_load8";
  58 const char SanCovLoad16[] = "__sanitizer_cov_load16";
  59 const char SanCovStore1[] = "__sanitizer_cov_store1";
  60 const char SanCovStore2[] = "__sanitizer_cov_store2";
  61 const char SanCovStore4[] = "__sanitizer_cov_store4";
  62 const char SanCovStore8[] = "__sanitizer_cov_store8";
  63 const char SanCovStore16[] = "__sanitizer_cov_store16";
  64 const char SanCovTraceDiv4[] = "__sanitizer_cov_trace_div4";
  65 const char SanCovTraceDiv8[] = "__sanitizer_cov_trace_div8";
  66 const char SanCovTraceGep[] = "__sanitizer_cov_trace_gep";
  67 const char SanCovTraceSwitchName[] = "__sanitizer_cov_trace_switch";
  68 const char SanCovModuleCtorTracePcGuardName[] =
  69     "sancov.module_ctor_trace_pc_guard";
  70 const char SanCovModuleCtor8bitCountersName[] =
  71     "sancov.module_ctor_8bit_counters";
  72 const char SanCovModuleCtorBoolFlagName[] = "sancov.module_ctor_bool_flag";
  73 static const uint64_t SanCtorAndDtorPriority = 2;
  74
  75 const char SanCovTracePCGuardName[] = "__sanitizer_cov_trace_pc_guard";
  76 const char SanCovTracePCGuardInitName[] = "__sanitizer_cov_trace_pc_guard_init";
  77 const char SanCov8bitCountersInitName[] = "__sanitizer_cov_8bit_counters_init";
  78 const char SanCovBoolFlagInitName[] = "__sanitizer_cov_bool_flag_init";
  79 const char SanCovPCsInitName[] = "__sanitizer_cov_pcs_init";
  80 const char SanCovCFsInitName[] = "__sanitizer_cov_cfs_init";
  81
  82 const char SanCovGuardsSectionName[] = "sancov_guards";
  83 const char SanCovCountersSectionName[] = "sancov_cntrs";
  84 const char SanCovBoolFlagSectionName[] = "sancov_bools";
  85 const char SanCovPCsSectionName[] = "sancov_pcs";
  86 const char SanCovCFsSectionName[] = "sancov_cfs";
  87 const char SanCovCallbackGateSectionName[] = "sancov_gate";
  88
  89 const char SanCovLowestStackName[] = "__sancov_lowest_stack";
  90 const char SanCovCallbackGateName[] = "__sancov_should_track";
  91
  92 static cl::opt<int> ClCoverageLevel(
  93     "sanitizer-coverage-level",
  94     cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
  95              "3: all blocks and critical edges"),
  96     cl::Hidden);
  97
  98 static cl::opt<bool> ClTracePC("sanitizer-coverage-trace-pc",
  99                                cl::desc("Experimental pc tracing"), cl::Hidden);
 100
 101 static cl::opt<bool> ClTracePCGuard("sanitizer-coverage-trace-pc-guard",
 102                                     cl::desc("pc tracing with a guard"),
 103                                     cl::Hidden);
 104
 105 // If true, we create a global variable that contains PCs of all instrumented
 106 // BBs, put this global into a named section, and pass this section's bounds
 107 // to __sanitizer_cov_pcs_init.
 108 // This way the coverage instrumentation does not need to acquire the PCs
 109 // at run-time. Works with trace-pc-guard, inline-8bit-counters, and
 110 // inline-bool-flag.
 111 static cl::opt<bool> ClCreatePCTable("sanitizer-coverage-pc-table",
 112                                      cl::desc("create a static PC table"),
 113                                      cl::Hidden);
 114
 115 static cl::opt<bool>
 116     ClInline8bitCounters("sanitizer-coverage-inline-8bit-counters",
 117                          cl::desc("increments 8-bit counter for every edge"),
 118                          cl::Hidden);
 119
 120 static cl::opt<bool>
 121     ClInlineBoolFlag("sanitizer-coverage-inline-bool-flag",
 122                      cl::desc("sets a boolean flag for every edge"),
 123                      cl::Hidden);
 124
 125 static cl::opt<bool>
 126     ClCMPTracing("sanitizer-coverage-trace-compares",
 127                  cl::desc("Tracing of CMP and similar instructions"),
 128                  cl::Hidden);
 129
 130 static cl::opt<bool> ClDIVTracing("sanitizer-coverage-trace-divs",
 131                                   cl::desc("Tracing of DIV instructions"),
 132                                   cl::Hidden);
 133
 134 static cl::opt<bool> ClLoadTracing("sanitizer-coverage-trace-loads",
 135                                    cl::desc("Tracing of load instructions"),
 136                                    cl::Hidden);
 137
 138 static cl::opt<bool> ClStoreTracing("sanitizer-coverage-trace-stores",
 139                                     cl::desc("Tracing of store instructions"),
 140                                     cl::Hidden);
 141
 142 static cl::opt<bool> ClGEPTracing("sanitizer-coverage-trace-geps",
 143                                   cl::desc("Tracing of GEP instructions"),
 144                                   cl::Hidden);
 145
 146 static cl::opt<bool>
 147     ClPruneBlocks("sanitizer-coverage-prune-blocks",
 148                   cl::desc("Reduce the number of instrumented blocks"),
 149                   cl::Hidden, cl::init(true));
 150
 151 static cl::opt<bool> ClStackDepth("sanitizer-coverage-stack-depth",
 152                                   cl::desc("max stack depth tracing"),
 153                                   cl::Hidden);
 154
 155 static cl::opt<bool>
 156     ClCollectCF("sanitizer-coverage-control-flow",
 157                 cl::desc("collect control flow for each function"), cl::Hidden);
 158
 159 static cl::opt<bool> ClGatedCallbacks(
 160     "sanitizer-coverage-gated-trace-callbacks",
 161     cl::desc("Gate the invocation of the tracing callbacks on a global variable"
 162              ". Currently only supported for trace-pc-guard and trace-cmp."),
 163     cl::Hidden, cl::init(false));
 164
 165 namespace {
 166
 167 SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) {
 168   SanitizerCoverageOptions Res;
 169   switch (LegacyCoverageLevel) {
 170   case 0:
 171     Res.CoverageType = SanitizerCoverageOptions::SCK_None;
 172     break;
 173   case 1:
 174     Res.CoverageType = SanitizerCoverageOptions::SCK_Function;
 175     break;
 176   case 2:
 177     Res.CoverageType = SanitizerCoverageOptions::SCK_BB;
 178     break;
 179   case 3:
 180     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
 181     break;
 182   case 4:
 183     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
 184     Res.IndirectCalls = true;
 185     break;
 186   }
 187   return Res;
 188 }
 189
 190 SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) {
 191   // Sets CoverageType and IndirectCalls.
 192   SanitizerCoverageOptions CLOpts = getOptions(ClCoverageLevel);
 193   Options.CoverageType = std::max(Options.CoverageType, CLOpts.CoverageType);
 194   Options.IndirectCalls |= CLOpts.IndirectCalls;
 195   Options.TraceCmp |= ClCMPTracing;
 196   Options.TraceDiv |= ClDIVTracing;
 197   Options.TraceGep |= ClGEPTracing;
 198   Options.TracePC |= ClTracePC;
 199   Options.TracePCGuard |= ClTracePCGuard;
 200   Options.Inline8bitCounters |= ClInline8bitCounters;
 201   Options.InlineBoolFlag |= ClInlineBoolFlag;
 202   Options.PCTable |= ClCreatePCTable;
 203   Options.NoPrune |= !ClPruneBlocks;
 204   Options.StackDepth |= ClStackDepth;
 205   Options.TraceLoads |= ClLoadTracing;
 206   Options.TraceStores |= ClStoreTracing;
 207   Options.GatedCallbacks |= ClGatedCallbacks;
 208   if (!Options.TracePCGuard && !Options.TracePC &&
 209       !Options.Inline8bitCounters && !Options.StackDepth &&
 210       !Options.InlineBoolFlag && !Options.TraceLoads && !Options.TraceStores)
 211     Options.TracePCGuard = true; // TracePCGuard is default.
 212   Options.CollectControlFlow |= ClCollectCF;
 213   return Options;
 214 }
 215
 216 class ModuleSanitizerCoverage {
 217 public:
 218   using DomTreeCallback = function_ref<const DominatorTree &(Function &F)>;
 219   using PostDomTreeCallback =
 220       function_ref<const PostDominatorTree &(Function &F)>;
 221
 222   ModuleSanitizerCoverage(Module &M, DomTreeCallback DTCallback,
 223                           PostDomTreeCallback PDTCallback,
 224                           const SanitizerCoverageOptions &Options,
 225                           const SpecialCaseList *Allowlist,
 226                           const SpecialCaseList *Blocklist)
 227       : M(M), DTCallback(DTCallback), PDTCallback(PDTCallback),
 228         Options(Options), Allowlist(Allowlist), Blocklist(Blocklist) {}
 229
 230   bool instrumentModule();
 231
 232 private:
 233   void createFunctionControlFlow(Function &F);
 234   void instrumentFunction(Function &F);
 235   void InjectCoverageForIndirectCalls(Function &F,
 236                                       ArrayRef<Instruction *> IndirCalls);
 237   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets,
 238                          Value *&FunctionGateCmp);
 239   void InjectTraceForDiv(Function &F,
 240                          ArrayRef<BinaryOperator *> DivTraceTargets);
 241   void InjectTraceForGep(Function &F,
 242                          ArrayRef<GetElementPtrInst *> GepTraceTargets);
 243   void InjectTraceForLoadsAndStores(Function &F, ArrayRef<LoadInst *> Loads,
 244                                     ArrayRef<StoreInst *> Stores);
 245   void InjectTraceForSwitch(Function &F,
 246                             ArrayRef<Instruction *> SwitchTraceTargets,
 247                             Value *&FunctionGateCmp);
 248   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks,
 249                       Value *&FunctionGateCmp, bool IsLeafFunc);
 250   GlobalVariable *CreateFunctionLocalArrayInSection(size_t NumElements,
 251                                                     Function &F, Type *Ty,
 252                                                     const char *Section);
 253   GlobalVariable *CreatePCArray(Function &F, ArrayRef<BasicBlock *> AllBlocks);
 254   void CreateFunctionLocalArrays(Function &F, ArrayRef<BasicBlock *> AllBlocks);
 255   Instruction *CreateGateBranch(Function &F, Value *&FunctionGateCmp,
 256                                 Instruction *I);
 257   Value *CreateFunctionLocalGateCmp(IRBuilder<> &IRB);
 258   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx,
 259                              Value *&FunctionGateCmp, bool IsLeafFunc);
 260   Function *CreateInitCallsForSections(Module &M, const char *CtorName,
 261                                        const char *InitFunctionName, Type *Ty,
 262                                        const char *Section);
 263   std::pair<Value *, Value *> CreateSecStartEnd(Module &M, const char *Section,
 264                                                 Type *Ty);
 265
 266   std::string getSectionName(const std::string &Section) const;
 267   std::string getSectionStart(const std::string &Section) const;
 268   std::string getSectionEnd(const std::string &Section) const;
 269
 270   Module &M;
 271   DomTreeCallback DTCallback;
 272   PostDomTreeCallback PDTCallback;
 273
 274   FunctionCallee SanCovTracePCIndir;
 275   FunctionCallee SanCovTracePC, SanCovTracePCGuard;
 276   std::array<FunctionCallee, 4> SanCovTraceCmpFunction;
 277   std::array<FunctionCallee, 4> SanCovTraceConstCmpFunction;
 278   std::array<FunctionCallee, 5> SanCovLoadFunction;
 279   std::array<FunctionCallee, 5> SanCovStoreFunction;
 280   std::array<FunctionCallee, 2> SanCovTraceDivFunction;
 281   FunctionCallee SanCovTraceGepFunction;
 282   FunctionCallee SanCovTraceSwitchFunction;
 283   GlobalVariable *SanCovLowestStack;
 284   GlobalVariable *SanCovCallbackGate;
 285   Type *PtrTy, *IntptrTy, *Int64Ty, *Int32Ty, *Int16Ty, *Int8Ty, *Int1Ty;
 286   Module *CurModule;
 287   std::string CurModuleUniqueId;
 288   Triple TargetTriple;
 289   LLVMContext *C;
 290   const DataLayout *DL;
 291
 292   GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
 293   GlobalVariable *Function8bitCounterArray;  // for inline-8bit-counters.
 294   GlobalVariable *FunctionBoolArray;         // for inline-bool-flag.
 295   GlobalVariable *FunctionPCsArray;  // for pc-table.
 296   GlobalVariable *FunctionCFsArray;  // for control flow table
 297   SmallVector<GlobalValue *, 20> GlobalsToAppendToUsed;
 298   SmallVector<GlobalValue *, 20> GlobalsToAppendToCompilerUsed;
 299
 300   SanitizerCoverageOptions Options;
 301
 302   const SpecialCaseList *Allowlist;
 303   const SpecialCaseList *Blocklist;
 304 };
 305 } // namespace
 306
 307 PreservedAnalyses SanitizerCoveragePass::run(Module &M,
 308                                              ModuleAnalysisManager &MAM) {
 309   auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 310   auto DTCallback = [&FAM](Function &F) -> const DominatorTree & {
 311     return FAM.getResult<DominatorTreeAnalysis>(F);
 312   };
 313   auto PDTCallback = [&FAM](Function &F) -> const PostDominatorTree & {
 314     return FAM.getResult<PostDominatorTreeAnalysis>(F);
 315   };
 316   ModuleSanitizerCoverage ModuleSancov(M, DTCallback, PDTCallback,
 317                                        OverrideFromCL(Options), Allowlist.get(),
 318                                        Blocklist.get());
 319   if (!ModuleSancov.instrumentModule())
 320     return PreservedAnalyses::all();
 321
 322   PreservedAnalyses PA = PreservedAnalyses::none();
 323   // GlobalsAA is considered stateless and does not get invalidated unless
 324   // explicitly invalidated; PreservedAnalyses::none() is not enough. Sanitizers
 325   // make changes that require GlobalsAA to be invalidated.
 326   PA.abandon<GlobalsAA>();
 327   return PA;
 328 }
 329
 330 std::pair<Value *, Value *>
 331 ModuleSanitizerCoverage::CreateSecStartEnd(Module &M, const char *Section,
 332                                            Type *Ty) {
 333   // Use ExternalWeak so that if all sections are discarded due to section
 334   // garbage collection, the linker will not report undefined symbol errors.
 335   // Windows defines the start/stop symbols in compiler-rt so no need for
 336   // ExternalWeak.
 337   GlobalValue::LinkageTypes Linkage = TargetTriple.isOSBinFormatCOFF()
 338                                           ? GlobalVariable::ExternalLinkage
 339                                           : GlobalVariable::ExternalWeakLinkage;
 340   GlobalVariable *SecStart =
 341       new GlobalVariable(M, Ty, false, Linkage, nullptr,
 342                          getSectionStart(Section));
 343   SecStart->setVisibility(GlobalValue::HiddenVisibility);
 344   GlobalVariable *SecEnd =
 345       new GlobalVariable(M, Ty, false, Linkage, nullptr,
 346                          getSectionEnd(Section));
 347   SecEnd->setVisibility(GlobalValue::HiddenVisibility);
 348   IRBuilder<> IRB(M.getContext());
 349   if (!TargetTriple.isOSBinFormatCOFF())
 350     return std::make_pair(SecStart, SecEnd);
 351
 352   // Account for the fact that on windows-msvc __start_* symbols actually
 353   // point to a uint64_t before the start of the array.
 354   auto GEP =
 355       IRB.CreatePtrAdd(SecStart, ConstantInt::get(IntptrTy, sizeof(uint64_t)));
 356   return std::make_pair(GEP, SecEnd);
 357 }
 358
 359 Function *ModuleSanitizerCoverage::CreateInitCallsForSections(
 360     Module &M, const char *CtorName, const char *InitFunctionName, Type *Ty,
 361     const char *Section) {
 362   auto SecStartEnd = CreateSecStartEnd(M, Section, Ty);
 363   auto SecStart = SecStartEnd.first;
 364   auto SecEnd = SecStartEnd.second;
 365   Function *CtorFunc;
 366   std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
 367       M, CtorName, InitFunctionName, {PtrTy, PtrTy}, {SecStart, SecEnd});
 368   assert(CtorFunc->getName() == CtorName);
 369
 370   if (TargetTriple.supportsCOMDAT()) {
 371     // Use comdat to dedup CtorFunc.
 372     CtorFunc->setComdat(M.getOrInsertComdat(CtorName));
 373     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc);
 374   } else {
 375     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
 376   }
 377
 378   if (TargetTriple.isOSBinFormatCOFF()) {
 379     // In COFF files, if the contructors are set as COMDAT (they are because
 380     // COFF supports COMDAT) and the linker flag /OPT:REF (strip unreferenced
 381     // functions and data) is used, the constructors get stripped. To prevent
 382     // this, give the constructors weak ODR linkage and ensure the linker knows
 383     // to include the sancov constructor. This way the linker can deduplicate
 384     // the constructors but always leave one copy.
 385     CtorFunc->setLinkage(GlobalValue::WeakODRLinkage);
 386   }
 387   return CtorFunc;
 388 }
 389
 390 bool ModuleSanitizerCoverage::instrumentModule() {
 391   if (Options.CoverageType == SanitizerCoverageOptions::SCK_None)
 392     return false;
 393   if (Allowlist &&
 394       !Allowlist->inSection("coverage", "src", M.getSourceFileName()))
 395     return false;
 396   if (Blocklist &&
 397       Blocklist->inSection("coverage", "src", M.getSourceFileName()))
 398     return false;
 399   C = &(M.getContext());
 400   DL = &M.getDataLayout();
 401   CurModule = &M;
 402   CurModuleUniqueId = getUniqueModuleId(CurModule);
 403   TargetTriple = Triple(M.getTargetTriple());
 404   FunctionGuardArray = nullptr;
 405   Function8bitCounterArray = nullptr;
 406   FunctionBoolArray = nullptr;
 407   FunctionPCsArray = nullptr;
 408   FunctionCFsArray = nullptr;
 409   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
 410   PtrTy = PointerType::getUnqual(*C);
 411   Type *VoidTy = Type::getVoidTy(*C);
 412   IRBuilder<> IRB(*C);
 413   Int64Ty = IRB.getInt64Ty();
 414   Int32Ty = IRB.getInt32Ty();
 415   Int16Ty = IRB.getInt16Ty();
 416   Int8Ty = IRB.getInt8Ty();
 417   Int1Ty = IRB.getInt1Ty();
 418
 419   SanCovTracePCIndir =
 420       M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy);
 421   // Make sure smaller parameters are zero-extended to i64 if required by the
 422   // target ABI.
 423   AttributeList SanCovTraceCmpZeroExtAL;
 424   SanCovTraceCmpZeroExtAL =
 425       SanCovTraceCmpZeroExtAL.addParamAttribute(*C, 0, Attribute::ZExt);
 426   SanCovTraceCmpZeroExtAL =
 427       SanCovTraceCmpZeroExtAL.addParamAttribute(*C, 1, Attribute::ZExt);
 428
 429   SanCovTraceCmpFunction[0] =
 430       M.getOrInsertFunction(SanCovTraceCmp1, SanCovTraceCmpZeroExtAL, VoidTy,
 431                             IRB.getInt8Ty(), IRB.getInt8Ty());
 432   SanCovTraceCmpFunction[1] =
 433       M.getOrInsertFunction(SanCovTraceCmp2, SanCovTraceCmpZeroExtAL, VoidTy,
 434                             IRB.getInt16Ty(), IRB.getInt16Ty());
 435   SanCovTraceCmpFunction[2] =
 436       M.getOrInsertFunction(SanCovTraceCmp4, SanCovTraceCmpZeroExtAL, VoidTy,
 437                             IRB.getInt32Ty(), IRB.getInt32Ty());
 438   SanCovTraceCmpFunction[3] =
 439       M.getOrInsertFunction(SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty);
 440
 441   SanCovTraceConstCmpFunction[0] = M.getOrInsertFunction(
 442       SanCovTraceConstCmp1, SanCovTraceCmpZeroExtAL, VoidTy, Int8Ty, Int8Ty);
 443   SanCovTraceConstCmpFunction[1] = M.getOrInsertFunction(
 444       SanCovTraceConstCmp2, SanCovTraceCmpZeroExtAL, VoidTy, Int16Ty, Int16Ty);
 445   SanCovTraceConstCmpFunction[2] = M.getOrInsertFunction(
 446       SanCovTraceConstCmp4, SanCovTraceCmpZeroExtAL, VoidTy, Int32Ty, Int32Ty);
 447   SanCovTraceConstCmpFunction[3] =
 448       M.getOrInsertFunction(SanCovTraceConstCmp8, VoidTy, Int64Ty, Int64Ty);
 449
 450   // Loads.
 451   SanCovLoadFunction[0] = M.getOrInsertFunction(SanCovLoad1, VoidTy, PtrTy);
 452   SanCovLoadFunction[1] =
 453       M.getOrInsertFunction(SanCovLoad2, VoidTy, PtrTy);
 454   SanCovLoadFunction[2] =
 455       M.getOrInsertFunction(SanCovLoad4, VoidTy, PtrTy);
 456   SanCovLoadFunction[3] =
 457       M.getOrInsertFunction(SanCovLoad8, VoidTy, PtrTy);
 458   SanCovLoadFunction[4] =
 459       M.getOrInsertFunction(SanCovLoad16, VoidTy, PtrTy);
 460   // Stores.
 461   SanCovStoreFunction[0] =
 462       M.getOrInsertFunction(SanCovStore1, VoidTy, PtrTy);
 463   SanCovStoreFunction[1] =
 464       M.getOrInsertFunction(SanCovStore2, VoidTy, PtrTy);
 465   SanCovStoreFunction[2] =
 466       M.getOrInsertFunction(SanCovStore4, VoidTy, PtrTy);
 467   SanCovStoreFunction[3] =
 468       M.getOrInsertFunction(SanCovStore8, VoidTy, PtrTy);
 469   SanCovStoreFunction[4] =
 470       M.getOrInsertFunction(SanCovStore16, VoidTy, PtrTy);
 471
 472   {
 473     AttributeList AL;
 474     AL = AL.addParamAttribute(*C, 0, Attribute::ZExt);
 475     SanCovTraceDivFunction[0] =
 476         M.getOrInsertFunction(SanCovTraceDiv4, AL, VoidTy, IRB.getInt32Ty());
 477   }
 478   SanCovTraceDivFunction[1] =
 479       M.getOrInsertFunction(SanCovTraceDiv8, VoidTy, Int64Ty);
 480   SanCovTraceGepFunction =
 481       M.getOrInsertFunction(SanCovTraceGep, VoidTy, IntptrTy);
 482   SanCovTraceSwitchFunction =
 483       M.getOrInsertFunction(SanCovTraceSwitchName, VoidTy, Int64Ty, PtrTy);
 484
 485   Constant *SanCovLowestStackConstant =
 486       M.getOrInsertGlobal(SanCovLowestStackName, IntptrTy);
 487   SanCovLowestStack = dyn_cast<GlobalVariable>(SanCovLowestStackConstant);
 488   if (!SanCovLowestStack || SanCovLowestStack->getValueType() != IntptrTy) {
 489     C->emitError(StringRef("'") + SanCovLowestStackName +
 490                  "' should not be declared by the user");
 491     return true;
 492   }
 493   SanCovLowestStack->setThreadLocalMode(
 494       GlobalValue::ThreadLocalMode::InitialExecTLSModel);
 495   if (Options.StackDepth && !SanCovLowestStack->isDeclaration())
 496     SanCovLowestStack->setInitializer(Constant::getAllOnesValue(IntptrTy));
 497
 498   if (Options.GatedCallbacks) {
 499     if (!Options.TracePCGuard && !Options.TraceCmp) {
 500       C->emitError(StringRef("'") + ClGatedCallbacks.ArgStr +
 501                    "' is only supported with trace-pc-guard or trace-cmp");
 502       return true;
 503     }
 504
 505     SanCovCallbackGate = cast<GlobalVariable>(
 506         M.getOrInsertGlobal(SanCovCallbackGateName, Int64Ty));
 507     SanCovCallbackGate->setSection(
 508         getSectionName(SanCovCallbackGateSectionName));
 509     SanCovCallbackGate->setInitializer(Constant::getNullValue(Int64Ty));
 510     SanCovCallbackGate->setLinkage(GlobalVariable::LinkOnceAnyLinkage);
 511     SanCovCallbackGate->setVisibility(GlobalVariable::HiddenVisibility);
 512     appendToCompilerUsed(M, SanCovCallbackGate);
 513   }
 514
 515   SanCovTracePC = M.getOrInsertFunction(SanCovTracePCName, VoidTy);
 516   SanCovTracePCGuard =
 517       M.getOrInsertFunction(SanCovTracePCGuardName, VoidTy, PtrTy);
 518
 519   for (auto &F : M)
 520     instrumentFunction(F);
 521
 522   Function *Ctor = nullptr;
 523
 524   if (FunctionGuardArray)
 525     Ctor = CreateInitCallsForSections(M, SanCovModuleCtorTracePcGuardName,
 526                                       SanCovTracePCGuardInitName, Int32Ty,
 527                                       SanCovGuardsSectionName);
 528   if (Function8bitCounterArray)
 529     Ctor = CreateInitCallsForSections(M, SanCovModuleCtor8bitCountersName,
 530                                       SanCov8bitCountersInitName, Int8Ty,
 531                                       SanCovCountersSectionName);
 532   if (FunctionBoolArray) {
 533     Ctor = CreateInitCallsForSections(M, SanCovModuleCtorBoolFlagName,
 534                                       SanCovBoolFlagInitName, Int1Ty,
 535                                       SanCovBoolFlagSectionName);
 536   }
 537   if (Ctor && Options.PCTable) {
 538     auto SecStartEnd = CreateSecStartEnd(M, SanCovPCsSectionName, IntptrTy);
 539     FunctionCallee InitFunction = declareSanitizerInitFunction(
 540         M, SanCovPCsInitName, {PtrTy, PtrTy});
 541     IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
 542     IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second});
 543   }
 544
 545   if (Ctor && Options.CollectControlFlow) {
 546     auto SecStartEnd = CreateSecStartEnd(M, SanCovCFsSectionName, IntptrTy);
 547     FunctionCallee InitFunction = declareSanitizerInitFunction(
 548         M, SanCovCFsInitName, {PtrTy, PtrTy});
 549     IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
 550     IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second});
 551   }
 552
 553   appendToUsed(M, GlobalsToAppendToUsed);
 554   appendToCompilerUsed(M, GlobalsToAppendToCompilerUsed);
 555   return true;
 556 }
 557
 558 // True if block has successors and it dominates all of them.
 559 static bool isFullDominator(const BasicBlock *BB, const DominatorTree &DT) {
 560   if (succ_empty(BB))
 561     return false;
 562
 563   return llvm::all_of(successors(BB), [&](const BasicBlock *SUCC) {
 564     return DT.dominates(BB, SUCC);
 565   });
 566 }
 567
 568 // True if block has predecessors and it postdominates all of them.
 569 static bool isFullPostDominator(const BasicBlock *BB,
 570                                 const PostDominatorTree &PDT) {
 571   if (pred_empty(BB))
 572     return false;
 573
 574   return llvm::all_of(predecessors(BB), [&](const BasicBlock *PRED) {
 575     return PDT.dominates(BB, PRED);
 576   });
 577 }
 578
 579 static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB,
 580                                   const DominatorTree &DT,
 581                                   const PostDominatorTree &PDT,
 582                                   const SanitizerCoverageOptions &Options) {
 583   // Don't insert coverage for blocks containing nothing but unreachable: we
 584   // will never call __sanitizer_cov() for them, so counting them in
 585   // NumberOfInstrumentedBlocks() might complicate calculation of code coverage
 586   // percentage. Also, unreachable instructions frequently have no debug
 587   // locations.
 588   if (isa<UnreachableInst>(BB->getFirstNonPHIOrDbgOrLifetime()))
 589     return false;
 590
 591   // Don't insert coverage into blocks without a valid insertion point
 592   // (catchswitch blocks).
 593   if (BB->getFirstInsertionPt() == BB->end())
 594     return false;
 595
 596   if (Options.NoPrune || &F.getEntryBlock() == BB)
 597     return true;
 598
 599   if (Options.CoverageType == SanitizerCoverageOptions::SCK_Function &&
 600       &F.getEntryBlock() != BB)
 601     return false;
 602
 603   // Do not instrument full dominators, or full post-dominators with multiple
 604   // predecessors.
 605   return !isFullDominator(BB, DT)
 606     && !(isFullPostDominator(BB, PDT) && !BB->getSinglePredecessor());
 607 }
 608
 609 // Returns true iff From->To is a backedge.
 610 // A twist here is that we treat From->To as a backedge if
 611 //   * To dominates From or
 612 //   * To->UniqueSuccessor dominates From
 613 static bool IsBackEdge(BasicBlock *From, BasicBlock *To,
 614                        const DominatorTree &DT) {
 615   if (DT.dominates(To, From))
 616     return true;
 617   if (auto Next = To->getUniqueSuccessor())
 618     if (DT.dominates(Next, From))
 619       return true;
 620   return false;
 621 }
 622
 623 // Prunes uninteresting Cmp instrumentation:
 624 //   * CMP instructions that feed into loop backedge branch.
 625 //
 626 // Note that Cmp pruning is controlled by the same flag as the
 627 // BB pruning.
 628 static bool IsInterestingCmp(ICmpInst *CMP, const DominatorTree &DT,
 629                              const SanitizerCoverageOptions &Options) {
 630   if (!Options.NoPrune)
 631     if (CMP->hasOneUse())
 632       if (auto BR = dyn_cast<BranchInst>(CMP->user_back()))
 633         for (BasicBlock *B : BR->successors())
 634           if (IsBackEdge(BR->getParent(), B, DT))
 635             return false;
 636   return true;
 637 }
 638
 639 void ModuleSanitizerCoverage::instrumentFunction(Function &F) {
 640   if (F.empty())
 641     return;
 642   if (F.getName().contains(".module_ctor"))
 643     return; // Should not instrument sanitizer init functions.
 644   if (F.getName().starts_with("__sanitizer_"))
 645     return; // Don't instrument __sanitizer_* callbacks.
 646   // Don't touch available_externally functions, their actual body is elewhere.
 647   if (F.getLinkage() == GlobalValue::AvailableExternallyLinkage)
 648     return;
 649   // Don't instrument MSVC CRT configuration helpers. They may run before normal
 650   // initialization.
 651   if (F.getName() == "__local_stdio_printf_options" ||
 652       F.getName() == "__local_stdio_scanf_options")
 653     return;
 654   if (isa<UnreachableInst>(F.getEntryBlock().getTerminator()))
 655     return;
 656   // Don't instrument functions using SEH for now. Splitting basic blocks like
 657   // we do for coverage breaks WinEHPrepare.
 658   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
 659   if (F.hasPersonalityFn() &&
 660       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
 661     return;
 662   if (Allowlist && !Allowlist->inSection("coverage", "fun", F.getName()))
 663     return;
 664   if (Blocklist && Blocklist->inSection("coverage", "fun", F.getName()))
 665     return;
 666   // Do not apply any instrumentation for naked functions.
 667   if (F.hasFnAttribute(Attribute::Naked))
 668     return;
 669   if (F.hasFnAttribute(Attribute::NoSanitizeCoverage))
 670     return;
 671   if (F.hasFnAttribute(Attribute::DisableSanitizerInstrumentation))
 672     return;
 673   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge) {
 674     SplitAllCriticalEdges(
 675         F, CriticalEdgeSplittingOptions().setIgnoreUnreachableDests());
 676   }
 677   SmallVector<Instruction *, 8> IndirCalls;
 678   SmallVector<BasicBlock *, 16> BlocksToInstrument;
 679   SmallVector<Instruction *, 8> CmpTraceTargets;
 680   SmallVector<Instruction *, 8> SwitchTraceTargets;
 681   SmallVector<BinaryOperator *, 8> DivTraceTargets;
 682   SmallVector<GetElementPtrInst *, 8> GepTraceTargets;
 683   SmallVector<LoadInst *, 8> Loads;
 684   SmallVector<StoreInst *, 8> Stores;
 685
 686   const DominatorTree &DT = DTCallback(F);
 687   const PostDominatorTree &PDT = PDTCallback(F);
 688   bool IsLeafFunc = true;
 689
 690   for (auto &BB : F) {
 691     if (shouldInstrumentBlock(F, &BB, DT, PDT, Options))
 692       BlocksToInstrument.push_back(&BB);
 693     for (auto &Inst : BB) {
 694       if (Options.IndirectCalls) {
 695         CallBase *CB = dyn_cast<CallBase>(&Inst);
 696         if (CB && CB->isIndirectCall())
 697           IndirCalls.push_back(&Inst);
 698       }
 699       if (Options.TraceCmp) {
 700         if (ICmpInst *CMP = dyn_cast<ICmpInst>(&Inst))
 701           if (IsInterestingCmp(CMP, DT, Options))
 702             CmpTraceTargets.push_back(&Inst);
 703         if (isa<SwitchInst>(&Inst))
 704           SwitchTraceTargets.push_back(&Inst);
 705       }
 706       if (Options.TraceDiv)
 707         if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst))
 708           if (BO->getOpcode() == Instruction::SDiv ||
 709               BO->getOpcode() == Instruction::UDiv)
 710             DivTraceTargets.push_back(BO);
 711       if (Options.TraceGep)
 712         if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst))
 713           GepTraceTargets.push_back(GEP);
 714       if (Options.TraceLoads)
 715         if (LoadInst *LI = dyn_cast<LoadInst>(&Inst))
 716           Loads.push_back(LI);
 717       if (Options.TraceStores)
 718         if (StoreInst *SI = dyn_cast<StoreInst>(&Inst))
 719           Stores.push_back(SI);
 720       if (Options.StackDepth)
 721         if (isa<InvokeInst>(Inst) ||
 722             (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst)))
 723           IsLeafFunc = false;
 724     }
 725   }
 726
 727   if (Options.CollectControlFlow)
 728     createFunctionControlFlow(F);
 729
 730   Value *FunctionGateCmp = nullptr;
 731   InjectCoverage(F, BlocksToInstrument, FunctionGateCmp, IsLeafFunc);
 732   InjectCoverageForIndirectCalls(F, IndirCalls);
 733   InjectTraceForCmp(F, CmpTraceTargets, FunctionGateCmp);
 734   InjectTraceForSwitch(F, SwitchTraceTargets, FunctionGateCmp);
 735   InjectTraceForDiv(F, DivTraceTargets);
 736   InjectTraceForGep(F, GepTraceTargets);
 737   InjectTraceForLoadsAndStores(F, Loads, Stores);
 738 }
 739
 740 GlobalVariable *ModuleSanitizerCoverage::CreateFunctionLocalArrayInSection(
 741     size_t NumElements, Function &F, Type *Ty, const char *Section) {
 742   ArrayType *ArrayTy = ArrayType::get(Ty, NumElements);
 743   auto Array = new GlobalVariable(
 744       *CurModule, ArrayTy, false, GlobalVariable::PrivateLinkage,
 745       Constant::getNullValue(ArrayTy), "__sancov_gen_");
 746
 747   if (TargetTriple.supportsCOMDAT() &&
 748       (TargetTriple.isOSBinFormatELF() || !F.isInterposable()))
 749     if (auto Comdat = getOrCreateFunctionComdat(F, TargetTriple))
 750       Array->setComdat(Comdat);
 751   Array->setSection(getSectionName(Section));
 752   Array->setAlignment(Align(DL->getTypeStoreSize(Ty).getFixedValue()));
 753
 754   // sancov_pcs parallels the other metadata section(s). Optimizers (e.g.
 755   // GlobalOpt/ConstantMerge) may not discard sancov_pcs and the other
 756   // section(s) as a unit, so we conservatively retain all unconditionally in
 757   // the compiler.
 758   //
 759   // With comdat (COFF/ELF), the linker can guarantee the associated sections
 760   // will be retained or discarded as a unit, so llvm.compiler.used is
 761   // sufficient. Otherwise, conservatively make all of them retained by the
 762   // linker.
 763   if (Array->hasComdat())
 764     GlobalsToAppendToCompilerUsed.push_back(Array);
 765   else
 766     GlobalsToAppendToUsed.push_back(Array);
 767
 768   return Array;
 769 }
 770
 771 GlobalVariable *
 772 ModuleSanitizerCoverage::CreatePCArray(Function &F,
 773                                        ArrayRef<BasicBlock *> AllBlocks) {
 774   size_t N = AllBlocks.size();
 775   assert(N);
 776   SmallVector<Constant *, 32> PCs;
 777   IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
 778   for (size_t i = 0; i < N; i++) {
 779     if (&F.getEntryBlock() == AllBlocks[i]) {
 780       PCs.push_back((Constant *)IRB.CreatePointerCast(&F, PtrTy));
 781       PCs.push_back((Constant *)IRB.CreateIntToPtr(
 782           ConstantInt::get(IntptrTy, 1), PtrTy));
 783     } else {
 784       PCs.push_back((Constant *)IRB.CreatePointerCast(
 785           BlockAddress::get(AllBlocks[i]), PtrTy));
 786       PCs.push_back(Constant::getNullValue(PtrTy));
 787     }
 788   }
 789   auto *PCArray = CreateFunctionLocalArrayInSection(N * 2, F, PtrTy,
 790                                                     SanCovPCsSectionName);
 791   PCArray->setInitializer(
 792       ConstantArray::get(ArrayType::get(PtrTy, N * 2), PCs));
 793   PCArray->setConstant(true);
 794
 795   return PCArray;
 796 }
 797
 798 void ModuleSanitizerCoverage::CreateFunctionLocalArrays(
 799     Function &F, ArrayRef<BasicBlock *> AllBlocks) {
 800   if (Options.TracePCGuard)
 801     FunctionGuardArray = CreateFunctionLocalArrayInSection(
 802         AllBlocks.size(), F, Int32Ty, SanCovGuardsSectionName);
 803
 804   if (Options.Inline8bitCounters)
 805     Function8bitCounterArray = CreateFunctionLocalArrayInSection(
 806         AllBlocks.size(), F, Int8Ty, SanCovCountersSectionName);
 807   if (Options.InlineBoolFlag)
 808     FunctionBoolArray = CreateFunctionLocalArrayInSection(
 809         AllBlocks.size(), F, Int1Ty, SanCovBoolFlagSectionName);
 810
 811   if (Options.PCTable)
 812     FunctionPCsArray = CreatePCArray(F, AllBlocks);
 813 }
 814
 815 Value *ModuleSanitizerCoverage::CreateFunctionLocalGateCmp(IRBuilder<> &IRB) {
 816   auto Load = IRB.CreateLoad(Int64Ty, SanCovCallbackGate);
 817   Load->setNoSanitizeMetadata();
 818   auto Cmp = IRB.CreateIsNotNull(Load);
 819   Cmp->setName("sancov gate cmp");
 820   return Cmp;
 821 }
 822
 823 Instruction *ModuleSanitizerCoverage::CreateGateBranch(Function &F,
 824                                                        Value *&FunctionGateCmp,
 825                                                        Instruction *IP) {
 826   if (!FunctionGateCmp) {
 827     // Create this in the entry block
 828     BasicBlock &BB = F.getEntryBlock();
 829     BasicBlock::iterator IP = BB.getFirstInsertionPt();
 830     IP = PrepareToSplitEntryBlock(BB, IP);
 831     IRBuilder<> EntryIRB(&*IP);
 832     FunctionGateCmp = CreateFunctionLocalGateCmp(EntryIRB);
 833   }
 834   // Set the branch weights in order to minimize the price paid when the
 835   // gate is turned off, allowing the default enablement of this
 836   // instrumentation with as little of a performance cost as possible
 837   auto Weights = MDBuilder(*C).createBranchWeights(1, 100000);
 838   return SplitBlockAndInsertIfThen(FunctionGateCmp, IP, false, Weights);
 839 }
 840
 841 bool ModuleSanitizerCoverage::InjectCoverage(Function &F,
 842                                              ArrayRef<BasicBlock *> AllBlocks,
 843                                              Value *&FunctionGateCmp,
 844                                              bool IsLeafFunc) {
 845   if (AllBlocks.empty()) return false;
 846   CreateFunctionLocalArrays(F, AllBlocks);
 847   for (size_t i = 0, N = AllBlocks.size(); i < N; i++)
 848     InjectCoverageAtBlock(F, *AllBlocks[i], i, FunctionGateCmp, IsLeafFunc);
 849   return true;
 850 }
 851
 852 // On every indirect call we call a run-time function
 853 // __sanitizer_cov_indir_call* with two parameters:
 854 //   - callee address,
 855 //   - global cache array that contains CacheSize pointers (zero-initialized).
 856 //     The cache is used to speed up recording the caller-callee pairs.
 857 // The address of the caller is passed implicitly via caller PC.
 858 // CacheSize is encoded in the name of the run-time function.
 859 void ModuleSanitizerCoverage::InjectCoverageForIndirectCalls(
 860     Function &F, ArrayRef<Instruction *> IndirCalls) {
 861   if (IndirCalls.empty())
 862     return;
 863   assert(Options.TracePC || Options.TracePCGuard ||
 864          Options.Inline8bitCounters || Options.InlineBoolFlag);
 865   for (auto *I : IndirCalls) {
 866     InstrumentationIRBuilder IRB(I);
 867     CallBase &CB = cast<CallBase>(*I);
 868     Value *Callee = CB.getCalledOperand();
 869     if (isa<InlineAsm>(Callee))
 870       continue;
 871     IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy));
 872   }
 873 }
 874
 875 // For every switch statement we insert a call:
 876 // __sanitizer_cov_trace_switch(CondValue,
 877 //      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
 878
 879 void ModuleSanitizerCoverage::InjectTraceForSwitch(
 880     Function &F, ArrayRef<Instruction *> SwitchTraceTargets,
 881     Value *&FunctionGateCmp) {
 882   for (auto *I : SwitchTraceTargets) {
 883     if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
 884       InstrumentationIRBuilder IRB(I);
 885       SmallVector<Constant *, 16> Initializers;
 886       Value *Cond = SI->getCondition();
 887       if (Cond->getType()->getScalarSizeInBits() >
 888           Int64Ty->getScalarSizeInBits())
 889         continue;
 890       Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
 891       Initializers.push_back(
 892           ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
 893       if (Cond->getType()->getScalarSizeInBits() <
 894           Int64Ty->getScalarSizeInBits())
 895         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
 896       for (auto It : SI->cases()) {
 897         ConstantInt *C = It.getCaseValue();
 898         if (C->getType()->getScalarSizeInBits() < 64)
 899           C = ConstantInt::get(C->getContext(), C->getValue().zext(64));
 900         Initializers.push_back(C);
 901       }
 902       llvm::sort(drop_begin(Initializers, 2),
 903                  [](const Constant *A, const Constant *B) {
 904                    return cast<ConstantInt>(A)->getLimitedValue() <
 905                           cast<ConstantInt>(B)->getLimitedValue();
 906                  });
 907       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
 908       GlobalVariable *GV = new GlobalVariable(
 909           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
 910           ConstantArray::get(ArrayOfInt64Ty, Initializers),
 911           "__sancov_gen_cov_switch_values");
 912       if (Options.GatedCallbacks) {
 913         auto GateBranch = CreateGateBranch(F, FunctionGateCmp, I);
 914         IRBuilder<> GateIRB(GateBranch);
 915         GateIRB.CreateCall(SanCovTraceSwitchFunction, {Cond, GV});
 916       } else {
 917         IRB.CreateCall(SanCovTraceSwitchFunction, {Cond, GV});
 918       }
 919     }
 920   }
 921 }
 922
 923 void ModuleSanitizerCoverage::InjectTraceForDiv(
 924     Function &, ArrayRef<BinaryOperator *> DivTraceTargets) {
 925   for (auto *BO : DivTraceTargets) {
 926     InstrumentationIRBuilder IRB(BO);
 927     Value *A1 = BO->getOperand(1);
 928     if (isa<ConstantInt>(A1)) continue;
 929     if (!A1->getType()->isIntegerTy())
 930       continue;
 931     uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType());
 932     int CallbackIdx = TypeSize == 32 ? 0 :
 933         TypeSize == 64 ? 1 : -1;
 934     if (CallbackIdx < 0) continue;
 935     auto Ty = Type::getIntNTy(*C, TypeSize);
 936     IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx],
 937                    {IRB.CreateIntCast(A1, Ty, true)});
 938   }
 939 }
 940
 941 void ModuleSanitizerCoverage::InjectTraceForGep(
 942     Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) {
 943   for (auto *GEP : GepTraceTargets) {
 944     InstrumentationIRBuilder IRB(GEP);
 945     for (Use &Idx : GEP->indices())
 946       if (!isa<ConstantInt>(Idx) && Idx->getType()->isIntegerTy())
 947         IRB.CreateCall(SanCovTraceGepFunction,
 948                        {IRB.CreateIntCast(Idx, IntptrTy, true)});
 949   }
 950 }
 951
 952 void ModuleSanitizerCoverage::InjectTraceForLoadsAndStores(
 953     Function &, ArrayRef<LoadInst *> Loads, ArrayRef<StoreInst *> Stores) {
 954   auto CallbackIdx = [&](Type *ElementTy) -> int {
 955     uint64_t TypeSize = DL->getTypeStoreSizeInBits(ElementTy);
 956     return TypeSize == 8     ? 0
 957            : TypeSize == 16  ? 1
 958            : TypeSize == 32  ? 2
 959            : TypeSize == 64  ? 3
 960            : TypeSize == 128 ? 4
 961                              : -1;
 962   };
 963   for (auto *LI : Loads) {
 964     InstrumentationIRBuilder IRB(LI);
 965     auto Ptr = LI->getPointerOperand();
 966     int Idx = CallbackIdx(LI->getType());
 967     if (Idx < 0)
 968       continue;
 969     IRB.CreateCall(SanCovLoadFunction[Idx], Ptr);
 970   }
 971   for (auto *SI : Stores) {
 972     InstrumentationIRBuilder IRB(SI);
 973     auto Ptr = SI->getPointerOperand();
 974     int Idx = CallbackIdx(SI->getValueOperand()->getType());
 975     if (Idx < 0)
 976       continue;
 977     IRB.CreateCall(SanCovStoreFunction[Idx], Ptr);
 978   }
 979 }
 980
 981 void ModuleSanitizerCoverage::InjectTraceForCmp(
 982     Function &F, ArrayRef<Instruction *> CmpTraceTargets,
 983     Value *&FunctionGateCmp) {
 984   for (auto *I : CmpTraceTargets) {
 985     if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
 986       InstrumentationIRBuilder IRB(ICMP);
 987       Value *A0 = ICMP->getOperand(0);
 988       Value *A1 = ICMP->getOperand(1);
 989       if (!A0->getType()->isIntegerTy())
 990         continue;
 991       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
 992       int CallbackIdx = TypeSize == 8 ? 0 :
 993                         TypeSize == 16 ? 1 :
 994                         TypeSize == 32 ? 2 :
 995                         TypeSize == 64 ? 3 : -1;
 996       if (CallbackIdx < 0) continue;
 997       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
 998       auto CallbackFunc = SanCovTraceCmpFunction[CallbackIdx];
 999       bool FirstIsConst = isa<ConstantInt>(A0);
1000       bool SecondIsConst = isa<ConstantInt>(A1);
1001       // If both are const, then we don't need such a comparison.
1002       if (FirstIsConst && SecondIsConst) continue;
1003       // If only one is const, then make it the first callback argument.
1004       if (FirstIsConst || SecondIsConst) {
1005         CallbackFunc = SanCovTraceConstCmpFunction[CallbackIdx];
1006         if (SecondIsConst)
1007           std::swap(A0, A1);
1008       }
1009
1010       auto Ty = Type::getIntNTy(*C, TypeSize);
1011       if (Options.GatedCallbacks) {
1012         auto GateBranch = CreateGateBranch(F, FunctionGateCmp, I);
1013         IRBuilder<> GateIRB(GateBranch);
1014         GateIRB.CreateCall(CallbackFunc, {GateIRB.CreateIntCast(A0, Ty, true),
1015                                           GateIRB.CreateIntCast(A1, Ty, true)});
1016       } else {
1017         IRB.CreateCall(CallbackFunc, {IRB.CreateIntCast(A0, Ty, true),
1018                                       IRB.CreateIntCast(A1, Ty, true)});
1019       }
1020     }
1021   }
1022 }
1023
1024 void ModuleSanitizerCoverage::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
1025                                                     size_t Idx,
1026                                                     Value *&FunctionGateCmp,
1027                                                     bool IsLeafFunc) {
1028   BasicBlock::iterator IP = BB.getFirstInsertionPt();
1029   bool IsEntryBB = &BB == &F.getEntryBlock();
1030   DebugLoc EntryLoc;
1031   if (IsEntryBB) {
1032     if (auto SP = F.getSubprogram())
1033       EntryLoc = DILocation::get(SP->getContext(), SP->getScopeLine(), 0, SP);
1034     // Keep static allocas and llvm.localescape calls in the entry block.  Even
1035     // if we aren't splitting the block, it's nice for allocas to be before
1036     // calls.
1037     IP = PrepareToSplitEntryBlock(BB, IP);
1038   }
1039
1040   InstrumentationIRBuilder IRB(&*IP);
1041   if (EntryLoc)
1042     IRB.SetCurrentDebugLocation(EntryLoc);
1043   if (Options.TracePC) {
1044     IRB.CreateCall(SanCovTracePC)
1045         ->setCannotMerge(); // gets the PC using GET_CALLER_PC.
1046   }
1047   if (Options.TracePCGuard) {
1048     auto GuardPtr = IRB.CreateConstInBoundsGEP2_64(
1049         FunctionGuardArray->getValueType(), FunctionGuardArray, 0, Idx);
1050     if (Options.GatedCallbacks) {
1051       Instruction *I = &*IP;
1052       auto GateBranch = CreateGateBranch(F, FunctionGateCmp, I);
1053       IRBuilder<> GateIRB(GateBranch);
1054       GateIRB.CreateCall(SanCovTracePCGuard, GuardPtr)->setCannotMerge();
1055     } else {
1056       IRB.CreateCall(SanCovTracePCGuard, GuardPtr)->setCannotMerge();
1057     }
1058   }
1059   if (Options.Inline8bitCounters) {
1060     auto CounterPtr = IRB.CreateGEP(
1061         Function8bitCounterArray->getValueType(), Function8bitCounterArray,
1062         {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)});
1063     auto Load = IRB.CreateLoad(Int8Ty, CounterPtr);
1064     auto Inc = IRB.CreateAdd(Load, ConstantInt::get(Int8Ty, 1));
1065     auto Store = IRB.CreateStore(Inc, CounterPtr);
1066     Load->setNoSanitizeMetadata();
1067     Store->setNoSanitizeMetadata();
1068   }
1069   if (Options.InlineBoolFlag) {
1070     auto FlagPtr = IRB.CreateGEP(
1071         FunctionBoolArray->getValueType(), FunctionBoolArray,
1072         {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)});
1073     auto Load = IRB.CreateLoad(Int1Ty, FlagPtr);
1074     auto ThenTerm = SplitBlockAndInsertIfThen(
1075         IRB.CreateIsNull(Load), &*IP, false,
1076         MDBuilder(IRB.getContext()).createUnlikelyBranchWeights());
1077     IRBuilder<> ThenIRB(ThenTerm);
1078     auto Store = ThenIRB.CreateStore(ConstantInt::getTrue(Int1Ty), FlagPtr);
1079     Load->setNoSanitizeMetadata();
1080     Store->setNoSanitizeMetadata();
1081   }
1082   if (Options.StackDepth && IsEntryBB && !IsLeafFunc) {
1083     // Check stack depth.  If it's the deepest so far, record it.
1084     Module *M = F.getParent();
1085     auto FrameAddrPtr = IRB.CreateIntrinsic(
1086         Intrinsic::frameaddress,
1087         IRB.getPtrTy(M->getDataLayout().getAllocaAddrSpace()),
1088         {Constant::getNullValue(Int32Ty)});
1089     auto FrameAddrInt = IRB.CreatePtrToInt(FrameAddrPtr, IntptrTy);
1090     auto LowestStack = IRB.CreateLoad(IntptrTy, SanCovLowestStack);
1091     auto IsStackLower = IRB.CreateICmpULT(FrameAddrInt, LowestStack);
1092     auto ThenTerm = SplitBlockAndInsertIfThen(
1093         IsStackLower, &*IP, false,
1094         MDBuilder(IRB.getContext()).createUnlikelyBranchWeights());
1095     IRBuilder<> ThenIRB(ThenTerm);
1096     auto Store = ThenIRB.CreateStore(FrameAddrInt, SanCovLowestStack);
1097     LowestStack->setNoSanitizeMetadata();
1098     Store->setNoSanitizeMetadata();
1099   }
1100 }
1101
1102 std::string
1103 ModuleSanitizerCoverage::getSectionName(const std::string &Section) const {
1104   if (TargetTriple.isOSBinFormatCOFF()) {
1105     if (Section == SanCovCountersSectionName)
1106       return ".SCOV$CM";
1107     if (Section == SanCovBoolFlagSectionName)
1108       return ".SCOV$BM";
1109     if (Section == SanCovPCsSectionName)
1110       return ".SCOVP$M";
1111     return ".SCOV$GM"; // For SanCovGuardsSectionName.
1112   }
1113   if (TargetTriple.isOSBinFormatMachO())
1114     return "__DATA,__" + Section;
1115   return "__" + Section;
1116 }
1117
1118 std::string
1119 ModuleSanitizerCoverage::getSectionStart(const std::string &Section) const {
1120   if (TargetTriple.isOSBinFormatMachO())
1121     return "\1section$start$__DATA$__" + Section;
1122   return "__start___" + Section;
1123 }
1124
1125 std::string
1126 ModuleSanitizerCoverage::getSectionEnd(const std::string &Section) const {
1127   if (TargetTriple.isOSBinFormatMachO())
1128     return "\1section$end$__DATA$__" + Section;
1129   return "__stop___" + Section;
1130 }
1131
1132 void ModuleSanitizerCoverage::createFunctionControlFlow(Function &F) {
1133   SmallVector<Constant *, 32> CFs;
1134   IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
1135
1136   for (auto &BB : F) {
1137     // blockaddress can not be used on function's entry block.
1138     if (&BB == &F.getEntryBlock())
1139       CFs.push_back((Constant *)IRB.CreatePointerCast(&F, PtrTy));
1140     else
1141       CFs.push_back((Constant *)IRB.CreatePointerCast(BlockAddress::get(&BB),
1142                                                       PtrTy));
1143
1144     for (auto SuccBB : successors(&BB)) {
1145       assert(SuccBB != &F.getEntryBlock());
1146       CFs.push_back((Constant *)IRB.CreatePointerCast(BlockAddress::get(SuccBB),
1147                                                       PtrTy));
1148     }
1149
1150     CFs.push_back((Constant *)Constant::getNullValue(PtrTy));
1151
1152     for (auto &Inst : BB) {
1153       if (CallBase *CB = dyn_cast<CallBase>(&Inst)) {
1154         if (CB->isIndirectCall()) {
1155           // TODO(navidem): handle indirect calls, for now mark its existence.
1156           CFs.push_back((Constant *)IRB.CreateIntToPtr(
1157               ConstantInt::get(IntptrTy, -1), PtrTy));
1158         } else {
1159           auto CalledF = CB->getCalledFunction();
1160           if (CalledF && !CalledF->isIntrinsic())
1161             CFs.push_back(
1162                 (Constant *)IRB.CreatePointerCast(CalledF, PtrTy));
1163         }
1164       }
1165     }
1166
1167     CFs.push_back((Constant *)Constant::getNullValue(PtrTy));
1168   }
1169
1170   FunctionCFsArray = CreateFunctionLocalArrayInSection(
1171       CFs.size(), F, PtrTy, SanCovCFsSectionName);
1172   FunctionCFsArray->setInitializer(
1173       ConstantArray::get(ArrayType::get(PtrTy, CFs.size()), CFs));
1174   FunctionCFsArray->setConstant(true);
1175 }