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

   1 //===-- SanitizerCoverage.cpp - coverage instrumentation for sanitizers ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Coverage instrumentation that works with AddressSanitizer
  11 // and potentially with other Sanitizers.
  12 //
  13 // We create a Guard variable with the same linkage
  14 // as the function and inject this code into the entry block (SCK_Function)
  15 // or all blocks (SCK_BB):
  16 // if (Guard < 0) {
  17 //    __sanitizer_cov(&Guard);
  18 // }
  19 // The accesses to Guard are atomic. The rest of the logic is
  20 // in __sanitizer_cov (it's fine to call it more than once).
  21 //
  22 // With SCK_Edge we also split critical edges this effectively
  23 // instrumenting all edges.
  24 //
  25 // This coverage implementation provides very limited data:
  26 // it only tells if a given function (block) was ever executed. No counters.
  27 // But for many use cases this is what we need and the added slowdown small.
  28 //
  29 //===----------------------------------------------------------------------===//
  30
  31 #include "llvm/ADT/ArrayRef.h"
  32 #include "llvm/ADT/SmallVector.h"
  33 #include "llvm/Analysis/EHPersonalities.h"
  34 #include "llvm/Analysis/PostDominators.h"
  35 #include "llvm/IR/CFG.h"
  36 #include "llvm/IR/CallSite.h"
  37 #include "llvm/IR/DataLayout.h"
  38 #include "llvm/IR/DebugInfo.h"
  39 #include "llvm/IR/Dominators.h"
  40 #include "llvm/IR/Function.h"
  41 #include "llvm/IR/IRBuilder.h"
  42 #include "llvm/IR/InlineAsm.h"
  43 #include "llvm/IR/LLVMContext.h"
  44 #include "llvm/IR/MDBuilder.h"
  45 #include "llvm/IR/Module.h"
  46 #include "llvm/IR/Type.h"
  47 #include "llvm/Support/CommandLine.h"
  48 #include "llvm/Support/Debug.h"
  49 #include "llvm/Support/raw_ostream.h"
  50 #include "llvm/Transforms/Instrumentation.h"
  51 #include "llvm/Transforms/Scalar.h"
  52 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  53 #include "llvm/Transforms/Utils/ModuleUtils.h"
  54
  55 using namespace llvm;
  56
  57 #define DEBUG_TYPE "sancov"
  58
  59 static const char *const SanCovModuleInitName = "__sanitizer_cov_module_init";
  60 static const char *const SanCovName = "__sanitizer_cov";
  61 static const char *const SanCovWithCheckName = "__sanitizer_cov_with_check";
  62 static const char *const SanCovTracePCIndirName =
  63     "__sanitizer_cov_trace_pc_indir";
  64 static const char *const SanCovTracePCName = "__sanitizer_cov_trace_pc";
  65 static const char *const SanCovTraceCmp1 = "__sanitizer_cov_trace_cmp1";
  66 static const char *const SanCovTraceCmp2 = "__sanitizer_cov_trace_cmp2";
  67 static const char *const SanCovTraceCmp4 = "__sanitizer_cov_trace_cmp4";
  68 static const char *const SanCovTraceCmp8 = "__sanitizer_cov_trace_cmp8";
  69 static const char *const SanCovTraceDiv4 = "__sanitizer_cov_trace_div4";
  70 static const char *const SanCovTraceDiv8 = "__sanitizer_cov_trace_div8";
  71 static const char *const SanCovTraceGep = "__sanitizer_cov_trace_gep";
  72 static const char *const SanCovTraceSwitchName = "__sanitizer_cov_trace_switch";
  73 static const char *const SanCovModuleCtorName = "sancov.module_ctor";
  74 static const uint64_t SanCtorAndDtorPriority = 2;
  75
  76 static const char *const SanCovTracePCGuardName =
  77     "__sanitizer_cov_trace_pc_guard";
  78 static const char *const SanCovTracePCGuardInitName =
  79     "__sanitizer_cov_trace_pc_guard_init";
  80
  81 static cl::opt<int> ClCoverageLevel(
  82     "sanitizer-coverage-level",
  83     cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
  84              "3: all blocks and critical edges"),
  85     cl::Hidden, cl::init(0));
  86
  87 static cl::opt<unsigned> ClCoverageBlockThreshold(
  88     "sanitizer-coverage-block-threshold",
  89     cl::desc("Use a callback with a guard check inside it if there are"
  90              " more than this number of blocks."),
  91     cl::Hidden, cl::init(0));
  92
  93 static cl::opt<bool> ClExperimentalTracePC("sanitizer-coverage-trace-pc",
  94                                            cl::desc("Experimental pc tracing"),
  95                                            cl::Hidden, cl::init(false));
  96
  97 static cl::opt<bool> ClTracePCGuard("sanitizer-coverage-trace-pc-guard",
  98                                     cl::desc("pc tracing with a guard"),
  99                                     cl::Hidden, cl::init(false));
 100
 101 static cl::opt<bool>
 102     ClCMPTracing("sanitizer-coverage-trace-compares",
 103                  cl::desc("Tracing of CMP and similar instructions"),
 104                  cl::Hidden, cl::init(false));
 105
 106 static cl::opt<bool> ClDIVTracing("sanitizer-coverage-trace-divs",
 107                                   cl::desc("Tracing of DIV instructions"),
 108                                   cl::Hidden, cl::init(false));
 109
 110 static cl::opt<bool> ClGEPTracing("sanitizer-coverage-trace-geps",
 111                                   cl::desc("Tracing of GEP instructions"),
 112                                   cl::Hidden, cl::init(false));
 113
 114 static cl::opt<bool>
 115     ClPruneBlocks("sanitizer-coverage-prune-blocks",
 116                   cl::desc("Reduce the number of instrumented blocks"),
 117                   cl::Hidden, cl::init(true));
 118
 119 namespace {
 120
 121 SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) {
 122   SanitizerCoverageOptions Res;
 123   switch (LegacyCoverageLevel) {
 124   case 0:
 125     Res.CoverageType = SanitizerCoverageOptions::SCK_None;
 126     break;
 127   case 1:
 128     Res.CoverageType = SanitizerCoverageOptions::SCK_Function;
 129     break;
 130   case 2:
 131     Res.CoverageType = SanitizerCoverageOptions::SCK_BB;
 132     break;
 133   case 3:
 134     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
 135     break;
 136   case 4:
 137     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
 138     Res.IndirectCalls = true;
 139     break;
 140   }
 141   return Res;
 142 }
 143
 144 SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) {
 145   // Sets CoverageType and IndirectCalls.
 146   SanitizerCoverageOptions CLOpts = getOptions(ClCoverageLevel);
 147   Options.CoverageType = std::max(Options.CoverageType, CLOpts.CoverageType);
 148   Options.IndirectCalls |= CLOpts.IndirectCalls;
 149   Options.TraceCmp |= ClCMPTracing;
 150   Options.TraceDiv |= ClDIVTracing;
 151   Options.TraceGep |= ClGEPTracing;
 152   Options.TracePC |= ClExperimentalTracePC;
 153   Options.TracePCGuard |= ClTracePCGuard;
 154   Options.NoPrune |= !ClPruneBlocks;
 155   return Options;
 156 }
 157
 158 class SanitizerCoverageModule : public ModulePass {
 159 public:
 160   SanitizerCoverageModule(
 161       const SanitizerCoverageOptions &Options = SanitizerCoverageOptions())
 162       : ModulePass(ID), Options(OverrideFromCL(Options)) {
 163     initializeSanitizerCoverageModulePass(*PassRegistry::getPassRegistry());
 164   }
 165   bool runOnModule(Module &M) override;
 166   bool runOnFunction(Function &F);
 167   static char ID; // Pass identification, replacement for typeid
 168   StringRef getPassName() const override { return "SanitizerCoverageModule"; }
 169
 170   void getAnalysisUsage(AnalysisUsage &AU) const override {
 171     AU.addRequired<DominatorTreeWrapperPass>();
 172     AU.addRequired<PostDominatorTreeWrapperPass>();
 173   }
 174
 175 private:
 176   void InjectCoverageForIndirectCalls(Function &F,
 177                                       ArrayRef<Instruction *> IndirCalls);
 178   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
 179   void InjectTraceForDiv(Function &F,
 180                          ArrayRef<BinaryOperator *> DivTraceTargets);
 181   void InjectTraceForGep(Function &F,
 182                          ArrayRef<GetElementPtrInst *> GepTraceTargets);
 183   void InjectTraceForSwitch(Function &F,
 184                             ArrayRef<Instruction *> SwitchTraceTargets);
 185   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks);
 186   void CreateFunctionGuardArray(size_t NumGuards, Function &F);
 187   void SetNoSanitizeMetadata(Instruction *I);
 188   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx,
 189                              bool UseCalls);
 190   unsigned NumberOfInstrumentedBlocks() {
 191     return SanCovFunction->getNumUses() +
 192            SanCovWithCheckFunction->getNumUses();
 193   }
 194   StringRef getSanCovTracePCGuardSection() const;
 195   StringRef getSanCovTracePCGuardSectionStart() const;
 196   StringRef getSanCovTracePCGuardSectionEnd() const;
 197   Function *SanCovFunction;
 198   Function *SanCovWithCheckFunction;
 199   Function *SanCovTracePCIndir;
 200   Function *SanCovTracePC, *SanCovTracePCGuard;
 201   Function *SanCovTraceCmpFunction[4];
 202   Function *SanCovTraceDivFunction[2];
 203   Function *SanCovTraceGepFunction;
 204   Function *SanCovTraceSwitchFunction;
 205   InlineAsm *EmptyAsm;
 206   Type *IntptrTy, *IntptrPtrTy, *Int64Ty, *Int64PtrTy, *Int32Ty, *Int32PtrTy;
 207   Module *CurModule;
 208   Triple TargetTriple;
 209   LLVMContext *C;
 210   const DataLayout *DL;
 211
 212   GlobalVariable *GuardArray;
 213   GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
 214   bool HasSancovGuardsSection;
 215
 216   SanitizerCoverageOptions Options;
 217 };
 218
 219 } // namespace
 220
 221 bool SanitizerCoverageModule::runOnModule(Module &M) {
 222   if (Options.CoverageType == SanitizerCoverageOptions::SCK_None)
 223     return false;
 224   C = &(M.getContext());
 225   DL = &M.getDataLayout();
 226   CurModule = &M;
 227   TargetTriple = Triple(M.getTargetTriple());
 228   HasSancovGuardsSection = false;
 229   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
 230   IntptrPtrTy = PointerType::getUnqual(IntptrTy);
 231   Type *VoidTy = Type::getVoidTy(*C);
 232   IRBuilder<> IRB(*C);
 233   Type *Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty());
 234   Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
 235   Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
 236   Int64Ty = IRB.getInt64Ty();
 237   Int32Ty = IRB.getInt32Ty();
 238
 239   SanCovFunction = checkSanitizerInterfaceFunction(
 240       M.getOrInsertFunction(SanCovName, VoidTy, Int32PtrTy));
 241   SanCovWithCheckFunction = checkSanitizerInterfaceFunction(
 242       M.getOrInsertFunction(SanCovWithCheckName, VoidTy, Int32PtrTy));
 243   SanCovTracePCIndir = checkSanitizerInterfaceFunction(
 244       M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy));
 245   SanCovTraceCmpFunction[0] =
 246       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 247           SanCovTraceCmp1, VoidTy, IRB.getInt8Ty(), IRB.getInt8Ty()));
 248   SanCovTraceCmpFunction[1] = checkSanitizerInterfaceFunction(
 249       M.getOrInsertFunction(SanCovTraceCmp2, VoidTy, IRB.getInt16Ty(),
 250                             IRB.getInt16Ty()));
 251   SanCovTraceCmpFunction[2] = checkSanitizerInterfaceFunction(
 252       M.getOrInsertFunction(SanCovTraceCmp4, VoidTy, IRB.getInt32Ty(),
 253                             IRB.getInt32Ty()));
 254   SanCovTraceCmpFunction[3] =
 255       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 256           SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty));
 257
 258   SanCovTraceDivFunction[0] =
 259       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 260           SanCovTraceDiv4, VoidTy, IRB.getInt32Ty()));
 261   SanCovTraceDivFunction[1] =
 262       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 263           SanCovTraceDiv8, VoidTy, Int64Ty));
 264   SanCovTraceGepFunction =
 265       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 266           SanCovTraceGep, VoidTy, IntptrTy));
 267   SanCovTraceSwitchFunction =
 268       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 269           SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy));
 270
 271   // We insert an empty inline asm after cov callbacks to avoid callback merge.
 272   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
 273                             StringRef(""), StringRef(""),
 274                             /*hasSideEffects=*/true);
 275
 276   SanCovTracePC = checkSanitizerInterfaceFunction(
 277       M.getOrInsertFunction(SanCovTracePCName, VoidTy));
 278   SanCovTracePCGuard = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 279       SanCovTracePCGuardName, VoidTy, Int32PtrTy));
 280
 281   // At this point we create a dummy array of guards because we don't
 282   // know how many elements we will need.
 283   Type *Int32Ty = IRB.getInt32Ty();
 284
 285   if (!Options.TracePCGuard)
 286     GuardArray =
 287         new GlobalVariable(M, Int32Ty, false, GlobalValue::ExternalLinkage,
 288                            nullptr, "__sancov_gen_cov_tmp");
 289
 290   for (auto &F : M)
 291     runOnFunction(F);
 292
 293   auto N = NumberOfInstrumentedBlocks();
 294
 295   GlobalVariable *RealGuardArray = nullptr;
 296   if (!Options.TracePCGuard) {
 297     // Now we know how many elements we need. Create an array of guards
 298     // with one extra element at the beginning for the size.
 299     Type *Int32ArrayNTy = ArrayType::get(Int32Ty, N + 1);
 300     RealGuardArray = new GlobalVariable(
 301         M, Int32ArrayNTy, false, GlobalValue::PrivateLinkage,
 302         Constant::getNullValue(Int32ArrayNTy), "__sancov_gen_cov");
 303
 304     // Replace the dummy array with the real one.
 305     GuardArray->replaceAllUsesWith(
 306         IRB.CreatePointerCast(RealGuardArray, Int32PtrTy));
 307     GuardArray->eraseFromParent();
 308   }
 309
 310   // Create variable for module (compilation unit) name
 311   Constant *ModNameStrConst =
 312       ConstantDataArray::getString(M.getContext(), M.getName(), true);
 313   GlobalVariable *ModuleName = new GlobalVariable(
 314       M, ModNameStrConst->getType(), true, GlobalValue::PrivateLinkage,
 315       ModNameStrConst, "__sancov_gen_modname");
 316   if (Options.TracePCGuard) {
 317     if (HasSancovGuardsSection) {
 318       Function *CtorFunc;
 319       GlobalVariable *SecStart = new GlobalVariable(
 320           M, Int32PtrTy, false, GlobalVariable::ExternalLinkage, nullptr,
 321           getSanCovTracePCGuardSectionStart());
 322       SecStart->setVisibility(GlobalValue::HiddenVisibility);
 323       GlobalVariable *SecEnd = new GlobalVariable(
 324           M, Int32PtrTy, false, GlobalVariable::ExternalLinkage, nullptr,
 325           getSanCovTracePCGuardSectionEnd());
 326       SecEnd->setVisibility(GlobalValue::HiddenVisibility);
 327
 328       std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
 329           M, SanCovModuleCtorName, SanCovTracePCGuardInitName,
 330           {Int32PtrTy, Int32PtrTy},
 331           {IRB.CreatePointerCast(SecStart, Int32PtrTy),
 332             IRB.CreatePointerCast(SecEnd, Int32PtrTy)});
 333
 334       if (TargetTriple.supportsCOMDAT()) {
 335         // Use comdat to dedup CtorFunc.
 336         CtorFunc->setComdat(M.getOrInsertComdat(SanCovModuleCtorName));
 337         appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc);
 338       } else {
 339         appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
 340       }
 341     }
 342   } else if (!Options.TracePC) {
 343     Function *CtorFunc;
 344     std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
 345         M, SanCovModuleCtorName, SanCovModuleInitName,
 346         {Int32PtrTy, IntptrTy, Int8PtrTy, Int8PtrTy},
 347         {IRB.CreatePointerCast(RealGuardArray, Int32PtrTy),
 348          ConstantInt::get(IntptrTy, N), Constant::getNullValue(Int8PtrTy),
 349          IRB.CreatePointerCast(ModuleName, Int8PtrTy)});
 350
 351     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
 352   }
 353
 354   return true;
 355 }
 356
 357 // True if block has successors and it dominates all of them.
 358 static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) {
 359   if (succ_begin(BB) == succ_end(BB))
 360     return false;
 361
 362   for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) {
 363     if (!DT->dominates(BB, SUCC))
 364       return false;
 365   }
 366
 367   return true;
 368 }
 369
 370 // True if block has predecessors and it postdominates all of them.
 371 static bool isFullPostDominator(const BasicBlock *BB,
 372                                 const PostDominatorTree *PDT) {
 373   if (pred_begin(BB) == pred_end(BB))
 374     return false;
 375
 376   for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) {
 377     if (!PDT->dominates(BB, PRED))
 378       return false;
 379   }
 380
 381   return true;
 382 }
 383
 384 static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB,
 385                                   const DominatorTree *DT,
 386                                   const PostDominatorTree *PDT,
 387                                   const SanitizerCoverageOptions &Options) {
 388   // Don't insert coverage for unreachable blocks: we will never call
 389   // __sanitizer_cov() for them, so counting them in
 390   // NumberOfInstrumentedBlocks() might complicate calculation of code coverage
 391   // percentage. Also, unreachable instructions frequently have no debug
 392   // locations.
 393   if (isa<UnreachableInst>(BB->getTerminator()))
 394     return false;
 395
 396   // Don't insert coverage into blocks without a valid insertion point
 397   // (catchswitch blocks).
 398   if (BB->getFirstInsertionPt() == BB->end())
 399     return false;
 400
 401   if (Options.NoPrune || &F.getEntryBlock() == BB)
 402     return true;
 403
 404   return !(isFullDominator(BB, DT) || isFullPostDominator(BB, PDT));
 405 }
 406
 407 bool SanitizerCoverageModule::runOnFunction(Function &F) {
 408   if (F.empty())
 409     return false;
 410   if (F.getName().find(".module_ctor") != std::string::npos)
 411     return false; // Should not instrument sanitizer init functions.
 412   if (F.getName().startswith("__sanitizer_"))
 413     return false;  // Don't instrument __sanitizer_* callbacks.
 414   // Don't instrument MSVC CRT configuration helpers. They may run before normal
 415   // initialization.
 416   if (F.getName() == "__local_stdio_printf_options" ||
 417       F.getName() == "__local_stdio_scanf_options")
 418     return false;
 419   // Don't instrument functions using SEH for now. Splitting basic blocks like
 420   // we do for coverage breaks WinEHPrepare.
 421   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
 422   if (F.hasPersonalityFn() &&
 423       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
 424     return false;
 425   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge)
 426     SplitAllCriticalEdges(F);
 427   SmallVector<Instruction *, 8> IndirCalls;
 428   SmallVector<BasicBlock *, 16> BlocksToInstrument;
 429   SmallVector<Instruction *, 8> CmpTraceTargets;
 430   SmallVector<Instruction *, 8> SwitchTraceTargets;
 431   SmallVector<BinaryOperator *, 8> DivTraceTargets;
 432   SmallVector<GetElementPtrInst *, 8> GepTraceTargets;
 433
 434   const DominatorTree *DT =
 435       &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
 436   const PostDominatorTree *PDT =
 437       &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree();
 438
 439   for (auto &BB : F) {
 440     if (shouldInstrumentBlock(F, &BB, DT, PDT, Options))
 441       BlocksToInstrument.push_back(&BB);
 442     for (auto &Inst : BB) {
 443       if (Options.IndirectCalls) {
 444         CallSite CS(&Inst);
 445         if (CS && !CS.getCalledFunction())
 446           IndirCalls.push_back(&Inst);
 447       }
 448       if (Options.TraceCmp) {
 449         if (isa<ICmpInst>(&Inst))
 450           CmpTraceTargets.push_back(&Inst);
 451         if (isa<SwitchInst>(&Inst))
 452           SwitchTraceTargets.push_back(&Inst);
 453       }
 454       if (Options.TraceDiv)
 455         if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst))
 456           if (BO->getOpcode() == Instruction::SDiv ||
 457               BO->getOpcode() == Instruction::UDiv)
 458             DivTraceTargets.push_back(BO);
 459       if (Options.TraceGep)
 460         if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst))
 461           GepTraceTargets.push_back(GEP);
 462    }
 463   }
 464
 465   InjectCoverage(F, BlocksToInstrument);
 466   InjectCoverageForIndirectCalls(F, IndirCalls);
 467   InjectTraceForCmp(F, CmpTraceTargets);
 468   InjectTraceForSwitch(F, SwitchTraceTargets);
 469   InjectTraceForDiv(F, DivTraceTargets);
 470   InjectTraceForGep(F, GepTraceTargets);
 471   return true;
 472 }
 473 void SanitizerCoverageModule::CreateFunctionGuardArray(size_t NumGuards,
 474                                                        Function &F) {
 475   if (!Options.TracePCGuard) return;
 476   HasSancovGuardsSection = true;
 477   ArrayType *ArrayOfInt32Ty = ArrayType::get(Int32Ty, NumGuards);
 478   FunctionGuardArray = new GlobalVariable(
 479       *CurModule, ArrayOfInt32Ty, false, GlobalVariable::PrivateLinkage,
 480       Constant::getNullValue(ArrayOfInt32Ty), "__sancov_gen_");
 481   if (auto Comdat = F.getComdat())
 482     FunctionGuardArray->setComdat(Comdat);
 483   FunctionGuardArray->setSection(getSanCovTracePCGuardSection());
 484 }
 485
 486 bool SanitizerCoverageModule::InjectCoverage(Function &F,
 487                                              ArrayRef<BasicBlock *> AllBlocks) {
 488   if (AllBlocks.empty()) return false;
 489   switch (Options.CoverageType) {
 490   case SanitizerCoverageOptions::SCK_None:
 491     return false;
 492   case SanitizerCoverageOptions::SCK_Function:
 493     CreateFunctionGuardArray(1, F);
 494     InjectCoverageAtBlock(F, F.getEntryBlock(), 0, false);
 495     return true;
 496   default: {
 497     bool UseCalls = ClCoverageBlockThreshold < AllBlocks.size();
 498     CreateFunctionGuardArray(AllBlocks.size(), F);
 499     for (size_t i = 0, N = AllBlocks.size(); i < N; i++)
 500       InjectCoverageAtBlock(F, *AllBlocks[i], i, UseCalls);
 501     return true;
 502   }
 503   }
 504 }
 505
 506 // On every indirect call we call a run-time function
 507 // __sanitizer_cov_indir_call* with two parameters:
 508 //   - callee address,
 509 //   - global cache array that contains CacheSize pointers (zero-initialized).
 510 //     The cache is used to speed up recording the caller-callee pairs.
 511 // The address of the caller is passed implicitly via caller PC.
 512 // CacheSize is encoded in the name of the run-time function.
 513 void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
 514     Function &F, ArrayRef<Instruction *> IndirCalls) {
 515   if (IndirCalls.empty())
 516     return;
 517   if (!Options.TracePC && !Options.TracePCGuard)
 518     return;
 519   for (auto I : IndirCalls) {
 520     IRBuilder<> IRB(I);
 521     CallSite CS(I);
 522     Value *Callee = CS.getCalledValue();
 523     if (isa<InlineAsm>(Callee))
 524       continue;
 525     IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy));
 526   }
 527 }
 528
 529 // For every switch statement we insert a call:
 530 // __sanitizer_cov_trace_switch(CondValue,
 531 //      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
 532
 533 void SanitizerCoverageModule::InjectTraceForSwitch(
 534     Function &, ArrayRef<Instruction *> SwitchTraceTargets) {
 535   for (auto I : SwitchTraceTargets) {
 536     if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
 537       IRBuilder<> IRB(I);
 538       SmallVector<Constant *, 16> Initializers;
 539       Value *Cond = SI->getCondition();
 540       if (Cond->getType()->getScalarSizeInBits() >
 541           Int64Ty->getScalarSizeInBits())
 542         continue;
 543       Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
 544       Initializers.push_back(
 545           ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
 546       if (Cond->getType()->getScalarSizeInBits() <
 547           Int64Ty->getScalarSizeInBits())
 548         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
 549       for (auto It : SI->cases()) {
 550         Constant *C = It.getCaseValue();
 551         if (C->getType()->getScalarSizeInBits() <
 552             Int64Ty->getScalarSizeInBits())
 553           C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
 554         Initializers.push_back(C);
 555       }
 556       std::sort(Initializers.begin() + 2, Initializers.end(),
 557                 [](const Constant *A, const Constant *B) {
 558                   return cast<ConstantInt>(A)->getLimitedValue() <
 559                          cast<ConstantInt>(B)->getLimitedValue();
 560                 });
 561       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
 562       GlobalVariable *GV = new GlobalVariable(
 563           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
 564           ConstantArray::get(ArrayOfInt64Ty, Initializers),
 565           "__sancov_gen_cov_switch_values");
 566       IRB.CreateCall(SanCovTraceSwitchFunction,
 567                      {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
 568     }
 569   }
 570 }
 571
 572 void SanitizerCoverageModule::InjectTraceForDiv(
 573     Function &, ArrayRef<BinaryOperator *> DivTraceTargets) {
 574   for (auto BO : DivTraceTargets) {
 575     IRBuilder<> IRB(BO);
 576     Value *A1 = BO->getOperand(1);
 577     if (isa<ConstantInt>(A1)) continue;
 578     if (!A1->getType()->isIntegerTy())
 579       continue;
 580     uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType());
 581     int CallbackIdx = TypeSize == 32 ? 0 :
 582         TypeSize == 64 ? 1 : -1;
 583     if (CallbackIdx < 0) continue;
 584     auto Ty = Type::getIntNTy(*C, TypeSize);
 585     IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx],
 586                    {IRB.CreateIntCast(A1, Ty, true)});
 587   }
 588 }
 589
 590 void SanitizerCoverageModule::InjectTraceForGep(
 591     Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) {
 592   for (auto GEP : GepTraceTargets) {
 593     IRBuilder<> IRB(GEP);
 594     for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
 595       if (!isa<ConstantInt>(*I) && (*I)->getType()->isIntegerTy())
 596         IRB.CreateCall(SanCovTraceGepFunction,
 597                        {IRB.CreateIntCast(*I, IntptrTy, true)});
 598   }
 599 }
 600
 601 void SanitizerCoverageModule::InjectTraceForCmp(
 602     Function &, ArrayRef<Instruction *> CmpTraceTargets) {
 603   for (auto I : CmpTraceTargets) {
 604     if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
 605       IRBuilder<> IRB(ICMP);
 606       Value *A0 = ICMP->getOperand(0);
 607       Value *A1 = ICMP->getOperand(1);
 608       if (!A0->getType()->isIntegerTy())
 609         continue;
 610       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
 611       int CallbackIdx = TypeSize == 8 ? 0 :
 612                         TypeSize == 16 ? 1 :
 613                         TypeSize == 32 ? 2 :
 614                         TypeSize == 64 ? 3 : -1;
 615       if (CallbackIdx < 0) continue;
 616       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
 617       auto Ty = Type::getIntNTy(*C, TypeSize);
 618       IRB.CreateCall(
 619           SanCovTraceCmpFunction[CallbackIdx],
 620           {IRB.CreateIntCast(A0, Ty, true), IRB.CreateIntCast(A1, Ty, true)});
 621     }
 622   }
 623 }
 624
 625 void SanitizerCoverageModule::SetNoSanitizeMetadata(Instruction *I) {
 626   I->setMetadata(I->getModule()->getMDKindID("nosanitize"),
 627                  MDNode::get(*C, None));
 628 }
 629
 630 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
 631                                                     size_t Idx, bool UseCalls) {
 632   BasicBlock::iterator IP = BB.getFirstInsertionPt();
 633   bool IsEntryBB = &BB == &F.getEntryBlock();
 634   DebugLoc EntryLoc;
 635   if (IsEntryBB) {
 636     if (auto SP = F.getSubprogram())
 637       EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP);
 638     // Keep static allocas and llvm.localescape calls in the entry block.  Even
 639     // if we aren't splitting the block, it's nice for allocas to be before
 640     // calls.
 641     IP = PrepareToSplitEntryBlock(BB, IP);
 642   } else {
 643     EntryLoc = IP->getDebugLoc();
 644   }
 645
 646   IRBuilder<> IRB(&*IP);
 647   IRB.SetCurrentDebugLocation(EntryLoc);
 648   if (Options.TracePC) {
 649     IRB.CreateCall(SanCovTracePC); // gets the PC using GET_CALLER_PC.
 650     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 651   } else if (Options.TracePCGuard) {
 652     auto GuardPtr = IRB.CreateIntToPtr(
 653         IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy),
 654                       ConstantInt::get(IntptrTy, Idx * 4)),
 655         Int32PtrTy);
 656     if (!UseCalls) {
 657       auto GuardLoad = IRB.CreateLoad(GuardPtr);
 658       GuardLoad->setAtomic(AtomicOrdering::Monotonic);
 659       GuardLoad->setAlignment(8);
 660       SetNoSanitizeMetadata(GuardLoad);  // Don't instrument with e.g. asan.
 661       auto Cmp = IRB.CreateICmpNE(
 662           GuardLoad, Constant::getNullValue(GuardLoad->getType()));
 663       auto Ins = SplitBlockAndInsertIfThen(
 664           Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
 665       IRB.SetInsertPoint(Ins);
 666       IRB.SetCurrentDebugLocation(EntryLoc);
 667     }
 668     IRB.CreateCall(SanCovTracePCGuard, GuardPtr);
 669     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 670   } else {
 671     Value *GuardP = IRB.CreateAdd(
 672         IRB.CreatePointerCast(GuardArray, IntptrTy),
 673         ConstantInt::get(IntptrTy, (1 + NumberOfInstrumentedBlocks()) * 4));
 674     GuardP = IRB.CreateIntToPtr(GuardP, Int32PtrTy);
 675     if (UseCalls) {
 676       IRB.CreateCall(SanCovWithCheckFunction, GuardP);
 677     } else {
 678       LoadInst *Load = IRB.CreateLoad(GuardP);
 679       Load->setAtomic(AtomicOrdering::Monotonic);
 680       Load->setAlignment(4);
 681       SetNoSanitizeMetadata(Load);
 682       Value *Cmp =
 683           IRB.CreateICmpSGE(Constant::getNullValue(Load->getType()), Load);
 684       Instruction *Ins = SplitBlockAndInsertIfThen(
 685           Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
 686       IRB.SetInsertPoint(Ins);
 687       IRB.SetCurrentDebugLocation(EntryLoc);
 688       // __sanitizer_cov gets the PC of the instruction using GET_CALLER_PC.
 689       IRB.CreateCall(SanCovFunction, GuardP);
 690       IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 691     }
 692   }
 693 }
 694
 695 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSection() const {
 696   if (TargetTriple.getObjectFormat() == Triple::COFF)
 697     return ".SCOV$M";
 698   if (TargetTriple.isOSBinFormatMachO())
 699     return "__DATA,__sancov_guards";
 700   return "__sancov_guards";
 701 }
 702
 703 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSectionStart() const {
 704   if (TargetTriple.isOSBinFormatMachO())
 705     return "\1section$start$__DATA$__sancov_guards";
 706   return "__start___sancov_guards";
 707 }
 708
 709 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSectionEnd() const {
 710   if (TargetTriple.isOSBinFormatMachO())
 711     return "\1section$end$__DATA$__sancov_guards";
 712   return "__stop___sancov_guards";
 713 }
 714
 715
 716 char SanitizerCoverageModule::ID = 0;
 717 INITIALIZE_PASS_BEGIN(SanitizerCoverageModule, "sancov",
 718                       "SanitizerCoverage: TODO."
 719                       "ModulePass",
 720                       false, false)
 721 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 722 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 723 INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov",
 724                     "SanitizerCoverage: TODO."
 725                     "ModulePass",
 726                     false, false)
 727 ModulePass *llvm::createSanitizerCoverageModulePass(
 728     const SanitizerCoverageOptions &Options) {
 729   return new SanitizerCoverageModule(Options);
 730 }