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   // Do not instrument full dominators, or full post-dominators with multiple
 405   // predecessors.
 406   return !isFullDominator(BB, DT)
 407     && !(isFullPostDominator(BB, PDT) && !BB->getSinglePredecessor());
 408 }
 409
 410 bool SanitizerCoverageModule::runOnFunction(Function &F) {
 411   if (F.empty())
 412     return false;
 413   if (F.getName().find(".module_ctor") != std::string::npos)
 414     return false; // Should not instrument sanitizer init functions.
 415   if (F.getName().startswith("__sanitizer_"))
 416     return false;  // Don't instrument __sanitizer_* callbacks.
 417   // Don't instrument MSVC CRT configuration helpers. They may run before normal
 418   // initialization.
 419   if (F.getName() == "__local_stdio_printf_options" ||
 420       F.getName() == "__local_stdio_scanf_options")
 421     return false;
 422   // Don't instrument functions using SEH for now. Splitting basic blocks like
 423   // we do for coverage breaks WinEHPrepare.
 424   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
 425   if (F.hasPersonalityFn() &&
 426       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
 427     return false;
 428   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge)
 429     SplitAllCriticalEdges(F);
 430   SmallVector<Instruction *, 8> IndirCalls;
 431   SmallVector<BasicBlock *, 16> BlocksToInstrument;
 432   SmallVector<Instruction *, 8> CmpTraceTargets;
 433   SmallVector<Instruction *, 8> SwitchTraceTargets;
 434   SmallVector<BinaryOperator *, 8> DivTraceTargets;
 435   SmallVector<GetElementPtrInst *, 8> GepTraceTargets;
 436
 437   const DominatorTree *DT =
 438       &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
 439   const PostDominatorTree *PDT =
 440       &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree();
 441
 442   for (auto &BB : F) {
 443     if (shouldInstrumentBlock(F, &BB, DT, PDT, Options))
 444       BlocksToInstrument.push_back(&BB);
 445     for (auto &Inst : BB) {
 446       if (Options.IndirectCalls) {
 447         CallSite CS(&Inst);
 448         if (CS && !CS.getCalledFunction())
 449           IndirCalls.push_back(&Inst);
 450       }
 451       if (Options.TraceCmp) {
 452         if (isa<ICmpInst>(&Inst))
 453           CmpTraceTargets.push_back(&Inst);
 454         if (isa<SwitchInst>(&Inst))
 455           SwitchTraceTargets.push_back(&Inst);
 456       }
 457       if (Options.TraceDiv)
 458         if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst))
 459           if (BO->getOpcode() == Instruction::SDiv ||
 460               BO->getOpcode() == Instruction::UDiv)
 461             DivTraceTargets.push_back(BO);
 462       if (Options.TraceGep)
 463         if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst))
 464           GepTraceTargets.push_back(GEP);
 465    }
 466   }
 467
 468   InjectCoverage(F, BlocksToInstrument);
 469   InjectCoverageForIndirectCalls(F, IndirCalls);
 470   InjectTraceForCmp(F, CmpTraceTargets);
 471   InjectTraceForSwitch(F, SwitchTraceTargets);
 472   InjectTraceForDiv(F, DivTraceTargets);
 473   InjectTraceForGep(F, GepTraceTargets);
 474   return true;
 475 }
 476 void SanitizerCoverageModule::CreateFunctionGuardArray(size_t NumGuards,
 477                                                        Function &F) {
 478   if (!Options.TracePCGuard) return;
 479   HasSancovGuardsSection = true;
 480   ArrayType *ArrayOfInt32Ty = ArrayType::get(Int32Ty, NumGuards);
 481   FunctionGuardArray = new GlobalVariable(
 482       *CurModule, ArrayOfInt32Ty, false, GlobalVariable::PrivateLinkage,
 483       Constant::getNullValue(ArrayOfInt32Ty), "__sancov_gen_");
 484   if (auto Comdat = F.getComdat())
 485     FunctionGuardArray->setComdat(Comdat);
 486   FunctionGuardArray->setSection(getSanCovTracePCGuardSection());
 487 }
 488
 489 bool SanitizerCoverageModule::InjectCoverage(Function &F,
 490                                              ArrayRef<BasicBlock *> AllBlocks) {
 491   if (AllBlocks.empty()) return false;
 492   switch (Options.CoverageType) {
 493   case SanitizerCoverageOptions::SCK_None:
 494     return false;
 495   case SanitizerCoverageOptions::SCK_Function:
 496     CreateFunctionGuardArray(1, F);
 497     InjectCoverageAtBlock(F, F.getEntryBlock(), 0, false);
 498     return true;
 499   default: {
 500     bool UseCalls = ClCoverageBlockThreshold < AllBlocks.size();
 501     CreateFunctionGuardArray(AllBlocks.size(), F);
 502     for (size_t i = 0, N = AllBlocks.size(); i < N; i++)
 503       InjectCoverageAtBlock(F, *AllBlocks[i], i, UseCalls);
 504     return true;
 505   }
 506   }
 507 }
 508
 509 // On every indirect call we call a run-time function
 510 // __sanitizer_cov_indir_call* with two parameters:
 511 //   - callee address,
 512 //   - global cache array that contains CacheSize pointers (zero-initialized).
 513 //     The cache is used to speed up recording the caller-callee pairs.
 514 // The address of the caller is passed implicitly via caller PC.
 515 // CacheSize is encoded in the name of the run-time function.
 516 void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
 517     Function &F, ArrayRef<Instruction *> IndirCalls) {
 518   if (IndirCalls.empty())
 519     return;
 520   if (!Options.TracePC && !Options.TracePCGuard)
 521     return;
 522   for (auto I : IndirCalls) {
 523     IRBuilder<> IRB(I);
 524     CallSite CS(I);
 525     Value *Callee = CS.getCalledValue();
 526     if (isa<InlineAsm>(Callee))
 527       continue;
 528     IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy));
 529   }
 530 }
 531
 532 // For every switch statement we insert a call:
 533 // __sanitizer_cov_trace_switch(CondValue,
 534 //      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
 535
 536 void SanitizerCoverageModule::InjectTraceForSwitch(
 537     Function &, ArrayRef<Instruction *> SwitchTraceTargets) {
 538   for (auto I : SwitchTraceTargets) {
 539     if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
 540       IRBuilder<> IRB(I);
 541       SmallVector<Constant *, 16> Initializers;
 542       Value *Cond = SI->getCondition();
 543       if (Cond->getType()->getScalarSizeInBits() >
 544           Int64Ty->getScalarSizeInBits())
 545         continue;
 546       Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
 547       Initializers.push_back(
 548           ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
 549       if (Cond->getType()->getScalarSizeInBits() <
 550           Int64Ty->getScalarSizeInBits())
 551         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
 552       for (auto It : SI->cases()) {
 553         Constant *C = It.getCaseValue();
 554         if (C->getType()->getScalarSizeInBits() <
 555             Int64Ty->getScalarSizeInBits())
 556           C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
 557         Initializers.push_back(C);
 558       }
 559       std::sort(Initializers.begin() + 2, Initializers.end(),
 560                 [](const Constant *A, const Constant *B) {
 561                   return cast<ConstantInt>(A)->getLimitedValue() <
 562                          cast<ConstantInt>(B)->getLimitedValue();
 563                 });
 564       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
 565       GlobalVariable *GV = new GlobalVariable(
 566           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
 567           ConstantArray::get(ArrayOfInt64Ty, Initializers),
 568           "__sancov_gen_cov_switch_values");
 569       IRB.CreateCall(SanCovTraceSwitchFunction,
 570                      {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
 571     }
 572   }
 573 }
 574
 575 void SanitizerCoverageModule::InjectTraceForDiv(
 576     Function &, ArrayRef<BinaryOperator *> DivTraceTargets) {
 577   for (auto BO : DivTraceTargets) {
 578     IRBuilder<> IRB(BO);
 579     Value *A1 = BO->getOperand(1);
 580     if (isa<ConstantInt>(A1)) continue;
 581     if (!A1->getType()->isIntegerTy())
 582       continue;
 583     uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType());
 584     int CallbackIdx = TypeSize == 32 ? 0 :
 585         TypeSize == 64 ? 1 : -1;
 586     if (CallbackIdx < 0) continue;
 587     auto Ty = Type::getIntNTy(*C, TypeSize);
 588     IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx],
 589                    {IRB.CreateIntCast(A1, Ty, true)});
 590   }
 591 }
 592
 593 void SanitizerCoverageModule::InjectTraceForGep(
 594     Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) {
 595   for (auto GEP : GepTraceTargets) {
 596     IRBuilder<> IRB(GEP);
 597     for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
 598       if (!isa<ConstantInt>(*I) && (*I)->getType()->isIntegerTy())
 599         IRB.CreateCall(SanCovTraceGepFunction,
 600                        {IRB.CreateIntCast(*I, IntptrTy, true)});
 601   }
 602 }
 603
 604 void SanitizerCoverageModule::InjectTraceForCmp(
 605     Function &, ArrayRef<Instruction *> CmpTraceTargets) {
 606   for (auto I : CmpTraceTargets) {
 607     if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
 608       IRBuilder<> IRB(ICMP);
 609       Value *A0 = ICMP->getOperand(0);
 610       Value *A1 = ICMP->getOperand(1);
 611       if (!A0->getType()->isIntegerTy())
 612         continue;
 613       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
 614       int CallbackIdx = TypeSize == 8 ? 0 :
 615                         TypeSize == 16 ? 1 :
 616                         TypeSize == 32 ? 2 :
 617                         TypeSize == 64 ? 3 : -1;
 618       if (CallbackIdx < 0) continue;
 619       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
 620       auto Ty = Type::getIntNTy(*C, TypeSize);
 621       IRB.CreateCall(
 622           SanCovTraceCmpFunction[CallbackIdx],
 623           {IRB.CreateIntCast(A0, Ty, true), IRB.CreateIntCast(A1, Ty, true)});
 624     }
 625   }
 626 }
 627
 628 void SanitizerCoverageModule::SetNoSanitizeMetadata(Instruction *I) {
 629   I->setMetadata(I->getModule()->getMDKindID("nosanitize"),
 630                  MDNode::get(*C, None));
 631 }
 632
 633 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
 634                                                     size_t Idx, bool UseCalls) {
 635   BasicBlock::iterator IP = BB.getFirstInsertionPt();
 636   bool IsEntryBB = &BB == &F.getEntryBlock();
 637   DebugLoc EntryLoc;
 638   if (IsEntryBB) {
 639     if (auto SP = F.getSubprogram())
 640       EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP);
 641     // Keep static allocas and llvm.localescape calls in the entry block.  Even
 642     // if we aren't splitting the block, it's nice for allocas to be before
 643     // calls.
 644     IP = PrepareToSplitEntryBlock(BB, IP);
 645   } else {
 646     EntryLoc = IP->getDebugLoc();
 647   }
 648
 649   IRBuilder<> IRB(&*IP);
 650   IRB.SetCurrentDebugLocation(EntryLoc);
 651   if (Options.TracePC) {
 652     IRB.CreateCall(SanCovTracePC); // gets the PC using GET_CALLER_PC.
 653     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 654   } else if (Options.TracePCGuard) {
 655     auto GuardPtr = IRB.CreateIntToPtr(
 656         IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy),
 657                       ConstantInt::get(IntptrTy, Idx * 4)),
 658         Int32PtrTy);
 659     if (!UseCalls) {
 660       auto GuardLoad = IRB.CreateLoad(GuardPtr);
 661       GuardLoad->setAtomic(AtomicOrdering::Monotonic);
 662       GuardLoad->setAlignment(8);
 663       SetNoSanitizeMetadata(GuardLoad);  // Don't instrument with e.g. asan.
 664       auto Cmp = IRB.CreateICmpNE(
 665           GuardLoad, Constant::getNullValue(GuardLoad->getType()));
 666       auto Ins = SplitBlockAndInsertIfThen(
 667           Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
 668       IRB.SetInsertPoint(Ins);
 669       IRB.SetCurrentDebugLocation(EntryLoc);
 670     }
 671     IRB.CreateCall(SanCovTracePCGuard, GuardPtr);
 672     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 673   } else {
 674     Value *GuardP = IRB.CreateAdd(
 675         IRB.CreatePointerCast(GuardArray, IntptrTy),
 676         ConstantInt::get(IntptrTy, (1 + NumberOfInstrumentedBlocks()) * 4));
 677     GuardP = IRB.CreateIntToPtr(GuardP, Int32PtrTy);
 678     if (UseCalls) {
 679       IRB.CreateCall(SanCovWithCheckFunction, GuardP);
 680     } else {
 681       LoadInst *Load = IRB.CreateLoad(GuardP);
 682       Load->setAtomic(AtomicOrdering::Monotonic);
 683       Load->setAlignment(4);
 684       SetNoSanitizeMetadata(Load);
 685       Value *Cmp =
 686           IRB.CreateICmpSGE(Constant::getNullValue(Load->getType()), Load);
 687       Instruction *Ins = SplitBlockAndInsertIfThen(
 688           Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
 689       IRB.SetInsertPoint(Ins);
 690       IRB.SetCurrentDebugLocation(EntryLoc);
 691       // __sanitizer_cov gets the PC of the instruction using GET_CALLER_PC.
 692       IRB.CreateCall(SanCovFunction, GuardP);
 693       IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 694     }
 695   }
 696 }
 697
 698 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSection() const {
 699   if (TargetTriple.getObjectFormat() == Triple::COFF)
 700     return ".SCOV$M";
 701   if (TargetTriple.isOSBinFormatMachO())
 702     return "__DATA,__sancov_guards";
 703   return "__sancov_guards";
 704 }
 705
 706 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSectionStart() const {
 707   if (TargetTriple.isOSBinFormatMachO())
 708     return "\1section$start$__DATA$__sancov_guards";
 709   return "__start___sancov_guards";
 710 }
 711
 712 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSectionEnd() const {
 713   if (TargetTriple.isOSBinFormatMachO())
 714     return "\1section$end$__DATA$__sancov_guards";
 715   return "__stop___sancov_guards";
 716 }
 717
 718
 719 char SanitizerCoverageModule::ID = 0;
 720 INITIALIZE_PASS_BEGIN(SanitizerCoverageModule, "sancov",
 721                       "SanitizerCoverage: TODO."
 722                       "ModulePass",
 723                       false, false)
 724 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 725 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 726 INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov",
 727                     "SanitizerCoverage: TODO."
 728                     "ModulePass",
 729                     false, false)
 730 ModulePass *llvm::createSanitizerCoverageModulePass(
 731     const SanitizerCoverageOptions &Options) {
 732   return new SanitizerCoverageModule(Options);
 733 }