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