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   return Options;
 155 }
 156
 157 class SanitizerCoverageModule : public ModulePass {
 158 public:
 159   SanitizerCoverageModule(
 160       const SanitizerCoverageOptions &Options = SanitizerCoverageOptions())
 161       : ModulePass(ID), Options(OverrideFromCL(Options)) {
 162     initializeSanitizerCoverageModulePass(*PassRegistry::getPassRegistry());
 163   }
 164   bool runOnModule(Module &M) override;
 165   bool runOnFunction(Function &F);
 166   static char ID; // Pass identification, replacement for typeid
 167   StringRef getPassName() const override { return "SanitizerCoverageModule"; }
 168
 169   void getAnalysisUsage(AnalysisUsage &AU) const override {
 170     AU.addRequired<DominatorTreeWrapperPass>();
 171     AU.addRequired<PostDominatorTreeWrapperPass>();
 172   }
 173
 174 private:
 175   void InjectCoverageForIndirectCalls(Function &F,
 176                                       ArrayRef<Instruction *> IndirCalls);
 177   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
 178   void InjectTraceForDiv(Function &F,
 179                          ArrayRef<BinaryOperator *> DivTraceTargets);
 180   void InjectTraceForGep(Function &F,
 181                          ArrayRef<GetElementPtrInst *> GepTraceTargets);
 182   void InjectTraceForSwitch(Function &F,
 183                             ArrayRef<Instruction *> SwitchTraceTargets);
 184   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks);
 185   void CreateFunctionGuardArray(size_t NumGuards, Function &F);
 186   void SetNoSanitizeMetadata(Instruction *I);
 187   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx,
 188                              bool UseCalls);
 189   unsigned NumberOfInstrumentedBlocks() {
 190     return SanCovFunction->getNumUses() +
 191            SanCovWithCheckFunction->getNumUses();
 192   }
 193   StringRef getSanCovTracePCGuardSection() const;
 194   StringRef getSanCovTracePCGuardSectionStart() const;
 195   StringRef getSanCovTracePCGuardSectionEnd() const;
 196   Function *SanCovFunction;
 197   Function *SanCovWithCheckFunction;
 198   Function *SanCovTracePCIndir;
 199   Function *SanCovTracePC, *SanCovTracePCGuard;
 200   Function *SanCovTraceCmpFunction[4];
 201   Function *SanCovTraceDivFunction[2];
 202   Function *SanCovTraceGepFunction;
 203   Function *SanCovTraceSwitchFunction;
 204   InlineAsm *EmptyAsm;
 205   Type *IntptrTy, *IntptrPtrTy, *Int64Ty, *Int64PtrTy, *Int32Ty, *Int32PtrTy;
 206   Module *CurModule;
 207   Triple TargetTriple;
 208   LLVMContext *C;
 209   const DataLayout *DL;
 210
 211   GlobalVariable *GuardArray;
 212   GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
 213   bool HasSancovGuardsSection;
 214
 215   SanitizerCoverageOptions Options;
 216 };
 217
 218 } // namespace
 219
 220 bool SanitizerCoverageModule::runOnModule(Module &M) {
 221   if (Options.CoverageType == SanitizerCoverageOptions::SCK_None)
 222     return false;
 223   C = &(M.getContext());
 224   DL = &M.getDataLayout();
 225   CurModule = &M;
 226   TargetTriple = Triple(M.getTargetTriple());
 227   HasSancovGuardsSection = false;
 228   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
 229   IntptrPtrTy = PointerType::getUnqual(IntptrTy);
 230   Type *VoidTy = Type::getVoidTy(*C);
 231   IRBuilder<> IRB(*C);
 232   Type *Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty());
 233   Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
 234   Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
 235   Int64Ty = IRB.getInt64Ty();
 236   Int32Ty = IRB.getInt32Ty();
 237
 238   SanCovFunction = checkSanitizerInterfaceFunction(
 239       M.getOrInsertFunction(SanCovName, VoidTy, Int32PtrTy));
 240   SanCovWithCheckFunction = checkSanitizerInterfaceFunction(
 241       M.getOrInsertFunction(SanCovWithCheckName, VoidTy, Int32PtrTy));
 242   SanCovTracePCIndir = checkSanitizerInterfaceFunction(
 243       M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy));
 244   SanCovTraceCmpFunction[0] =
 245       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 246           SanCovTraceCmp1, VoidTy, IRB.getInt8Ty(), IRB.getInt8Ty()));
 247   SanCovTraceCmpFunction[1] = checkSanitizerInterfaceFunction(
 248       M.getOrInsertFunction(SanCovTraceCmp2, VoidTy, IRB.getInt16Ty(),
 249                             IRB.getInt16Ty()));
 250   SanCovTraceCmpFunction[2] = checkSanitizerInterfaceFunction(
 251       M.getOrInsertFunction(SanCovTraceCmp4, VoidTy, IRB.getInt32Ty(),
 252                             IRB.getInt32Ty()));
 253   SanCovTraceCmpFunction[3] =
 254       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 255           SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty));
 256
 257   SanCovTraceDivFunction[0] =
 258       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 259           SanCovTraceDiv4, VoidTy, IRB.getInt32Ty()));
 260   SanCovTraceDivFunction[1] =
 261       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 262           SanCovTraceDiv8, VoidTy, Int64Ty));
 263   SanCovTraceGepFunction =
 264       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 265           SanCovTraceGep, VoidTy, IntptrTy));
 266   SanCovTraceSwitchFunction =
 267       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 268           SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy));
 269
 270   // We insert an empty inline asm after cov callbacks to avoid callback merge.
 271   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
 272                             StringRef(""), StringRef(""),
 273                             /*hasSideEffects=*/true);
 274
 275   SanCovTracePC = checkSanitizerInterfaceFunction(
 276       M.getOrInsertFunction(SanCovTracePCName, VoidTy));
 277   SanCovTracePCGuard = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
 278       SanCovTracePCGuardName, VoidTy, Int32PtrTy));
 279
 280   // At this point we create a dummy array of guards because we don't
 281   // know how many elements we will need.
 282   Type *Int32Ty = IRB.getInt32Ty();
 283
 284   if (!Options.TracePCGuard)
 285     GuardArray =
 286         new GlobalVariable(M, Int32Ty, false, GlobalValue::ExternalLinkage,
 287                            nullptr, "__sancov_gen_cov_tmp");
 288
 289   for (auto &F : M)
 290     runOnFunction(F);
 291
 292   auto N = NumberOfInstrumentedBlocks();
 293
 294   GlobalVariable *RealGuardArray = nullptr;
 295   if (!Options.TracePCGuard) {
 296     // Now we know how many elements we need. Create an array of guards
 297     // with one extra element at the beginning for the size.
 298     Type *Int32ArrayNTy = ArrayType::get(Int32Ty, N + 1);
 299     RealGuardArray = new GlobalVariable(
 300         M, Int32ArrayNTy, false, GlobalValue::PrivateLinkage,
 301         Constant::getNullValue(Int32ArrayNTy), "__sancov_gen_cov");
 302
 303     // Replace the dummy array with the real one.
 304     GuardArray->replaceAllUsesWith(
 305         IRB.CreatePointerCast(RealGuardArray, Int32PtrTy));
 306     GuardArray->eraseFromParent();
 307   }
 308
 309   // Create variable for module (compilation unit) name
 310   Constant *ModNameStrConst =
 311       ConstantDataArray::getString(M.getContext(), M.getName(), true);
 312   GlobalVariable *ModuleName = new GlobalVariable(
 313       M, ModNameStrConst->getType(), true, GlobalValue::PrivateLinkage,
 314       ModNameStrConst, "__sancov_gen_modname");
 315   if (Options.TracePCGuard) {
 316     if (HasSancovGuardsSection) {
 317       Function *CtorFunc;
 318       GlobalVariable *SecStart = new GlobalVariable(
 319           M, Int32PtrTy, false, GlobalVariable::ExternalLinkage, nullptr,
 320           getSanCovTracePCGuardSectionStart());
 321       SecStart->setVisibility(GlobalValue::HiddenVisibility);
 322       GlobalVariable *SecEnd = new GlobalVariable(
 323           M, Int32PtrTy, false, GlobalVariable::ExternalLinkage, nullptr,
 324           getSanCovTracePCGuardSectionEnd());
 325       SecEnd->setVisibility(GlobalValue::HiddenVisibility);
 326
 327       std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
 328           M, SanCovModuleCtorName, SanCovTracePCGuardInitName,
 329           {Int32PtrTy, Int32PtrTy},
 330           {IRB.CreatePointerCast(SecStart, Int32PtrTy),
 331             IRB.CreatePointerCast(SecEnd, Int32PtrTy)});
 332
 333       if (TargetTriple.supportsCOMDAT()) {
 334         // Use comdat to dedup CtorFunc.
 335         CtorFunc->setComdat(M.getOrInsertComdat(SanCovModuleCtorName));
 336         appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc);
 337       } else {
 338         appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
 339       }
 340     }
 341   } else if (!Options.TracePC) {
 342     Function *CtorFunc;
 343     std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
 344         M, SanCovModuleCtorName, SanCovModuleInitName,
 345         {Int32PtrTy, IntptrTy, Int8PtrTy, Int8PtrTy},
 346         {IRB.CreatePointerCast(RealGuardArray, Int32PtrTy),
 347          ConstantInt::get(IntptrTy, N), Constant::getNullValue(Int8PtrTy),
 348          IRB.CreatePointerCast(ModuleName, Int8PtrTy)});
 349
 350     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
 351   }
 352
 353   return true;
 354 }
 355
 356 // True if block has successors and it dominates all of them.
 357 static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) {
 358   if (succ_begin(BB) == succ_end(BB))
 359     return false;
 360
 361   for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) {
 362     if (!DT->dominates(BB, SUCC))
 363       return false;
 364   }
 365
 366   return true;
 367 }
 368
 369 // True if block has predecessors and it postdominates all of them.
 370 static bool isFullPostDominator(const BasicBlock *BB,
 371                                 const PostDominatorTree *PDT) {
 372   if (pred_begin(BB) == pred_end(BB))
 373     return false;
 374
 375   for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) {
 376     if (!PDT->dominates(BB, PRED))
 377       return false;
 378   }
 379
 380   return true;
 381 }
 382
 383 static bool shouldInstrumentBlock(const Function& F, const BasicBlock *BB, const DominatorTree *DT,
 384                                   const PostDominatorTree *PDT) {
 385   // Don't insert coverage for unreachable blocks: we will never call
 386   // __sanitizer_cov() for them, so counting them in
 387   // NumberOfInstrumentedBlocks() might complicate calculation of code coverage
 388   // percentage. Also, unreachable instructions frequently have no debug
 389   // locations.
 390   if (isa<UnreachableInst>(BB->getTerminator()))
 391     return false;
 392
 393   // Don't insert coverage into blocks without a valid insertion point
 394   // (catchswitch blocks).
 395   if (BB->getFirstInsertionPt() == BB->end())
 396     return false;
 397
 398   if (!ClPruneBlocks || &F.getEntryBlock() == BB)
 399     return true;
 400
 401   return !(isFullDominator(BB, DT) || isFullPostDominator(BB, PDT));
 402 }
 403
 404 bool SanitizerCoverageModule::runOnFunction(Function &F) {
 405   if (F.empty())
 406     return false;
 407   if (F.getName().find(".module_ctor") != std::string::npos)
 408     return false; // Should not instrument sanitizer init functions.
 409   if (F.getName().startswith("__sanitizer_"))
 410     return false;  // Don't instrument __sanitizer_* callbacks.
 411   // Don't instrument MSVC CRT configuration helpers. They may run before normal
 412   // initialization.
 413   if (F.getName() == "__local_stdio_printf_options" ||
 414       F.getName() == "__local_stdio_scanf_options")
 415     return false;
 416   // Don't instrument functions using SEH for now. Splitting basic blocks like
 417   // we do for coverage breaks WinEHPrepare.
 418   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
 419   if (F.hasPersonalityFn() &&
 420       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
 421     return false;
 422   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge)
 423     SplitAllCriticalEdges(F);
 424   SmallVector<Instruction *, 8> IndirCalls;
 425   SmallVector<BasicBlock *, 16> BlocksToInstrument;
 426   SmallVector<Instruction *, 8> CmpTraceTargets;
 427   SmallVector<Instruction *, 8> SwitchTraceTargets;
 428   SmallVector<BinaryOperator *, 8> DivTraceTargets;
 429   SmallVector<GetElementPtrInst *, 8> GepTraceTargets;
 430
 431   const DominatorTree *DT =
 432       &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
 433   const PostDominatorTree *PDT =
 434       &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree();
 435
 436   for (auto &BB : F) {
 437     if (shouldInstrumentBlock(F, &BB, DT, PDT))
 438       BlocksToInstrument.push_back(&BB);
 439     for (auto &Inst : BB) {
 440       if (Options.IndirectCalls) {
 441         CallSite CS(&Inst);
 442         if (CS && !CS.getCalledFunction())
 443           IndirCalls.push_back(&Inst);
 444       }
 445       if (Options.TraceCmp) {
 446         if (isa<ICmpInst>(&Inst))
 447           CmpTraceTargets.push_back(&Inst);
 448         if (isa<SwitchInst>(&Inst))
 449           SwitchTraceTargets.push_back(&Inst);
 450       }
 451       if (Options.TraceDiv)
 452         if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst))
 453           if (BO->getOpcode() == Instruction::SDiv ||
 454               BO->getOpcode() == Instruction::UDiv)
 455             DivTraceTargets.push_back(BO);
 456       if (Options.TraceGep)
 457         if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst))
 458           GepTraceTargets.push_back(GEP);
 459    }
 460   }
 461
 462   InjectCoverage(F, BlocksToInstrument);
 463   InjectCoverageForIndirectCalls(F, IndirCalls);
 464   InjectTraceForCmp(F, CmpTraceTargets);
 465   InjectTraceForSwitch(F, SwitchTraceTargets);
 466   InjectTraceForDiv(F, DivTraceTargets);
 467   InjectTraceForGep(F, GepTraceTargets);
 468   return true;
 469 }
 470 void SanitizerCoverageModule::CreateFunctionGuardArray(size_t NumGuards,
 471                                                        Function &F) {
 472   if (!Options.TracePCGuard) return;
 473   HasSancovGuardsSection = true;
 474   ArrayType *ArrayOfInt32Ty = ArrayType::get(Int32Ty, NumGuards);
 475   FunctionGuardArray = new GlobalVariable(
 476       *CurModule, ArrayOfInt32Ty, false, GlobalVariable::PrivateLinkage,
 477       Constant::getNullValue(ArrayOfInt32Ty), "__sancov_gen_");
 478   if (auto Comdat = F.getComdat())
 479     FunctionGuardArray->setComdat(Comdat);
 480   FunctionGuardArray->setSection(getSanCovTracePCGuardSection());
 481 }
 482
 483 bool SanitizerCoverageModule::InjectCoverage(Function &F,
 484                                              ArrayRef<BasicBlock *> AllBlocks) {
 485   if (AllBlocks.empty()) return false;
 486   switch (Options.CoverageType) {
 487   case SanitizerCoverageOptions::SCK_None:
 488     return false;
 489   case SanitizerCoverageOptions::SCK_Function:
 490     CreateFunctionGuardArray(1, F);
 491     InjectCoverageAtBlock(F, F.getEntryBlock(), 0, false);
 492     return true;
 493   default: {
 494     bool UseCalls = ClCoverageBlockThreshold < AllBlocks.size();
 495     CreateFunctionGuardArray(AllBlocks.size(), F);
 496     for (size_t i = 0, N = AllBlocks.size(); i < N; i++)
 497       InjectCoverageAtBlock(F, *AllBlocks[i], i, UseCalls);
 498     return true;
 499   }
 500   }
 501 }
 502
 503 // On every indirect call we call a run-time function
 504 // __sanitizer_cov_indir_call* with two parameters:
 505 //   - callee address,
 506 //   - global cache array that contains CacheSize pointers (zero-initialized).
 507 //     The cache is used to speed up recording the caller-callee pairs.
 508 // The address of the caller is passed implicitly via caller PC.
 509 // CacheSize is encoded in the name of the run-time function.
 510 void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
 511     Function &F, ArrayRef<Instruction *> IndirCalls) {
 512   if (IndirCalls.empty())
 513     return;
 514   if (!Options.TracePC && !Options.TracePCGuard)
 515     return;
 516   for (auto I : IndirCalls) {
 517     IRBuilder<> IRB(I);
 518     CallSite CS(I);
 519     Value *Callee = CS.getCalledValue();
 520     if (isa<InlineAsm>(Callee))
 521       continue;
 522     IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy));
 523   }
 524 }
 525
 526 // For every switch statement we insert a call:
 527 // __sanitizer_cov_trace_switch(CondValue,
 528 //      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
 529
 530 void SanitizerCoverageModule::InjectTraceForSwitch(
 531     Function &, ArrayRef<Instruction *> SwitchTraceTargets) {
 532   for (auto I : SwitchTraceTargets) {
 533     if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
 534       IRBuilder<> IRB(I);
 535       SmallVector<Constant *, 16> Initializers;
 536       Value *Cond = SI->getCondition();
 537       if (Cond->getType()->getScalarSizeInBits() >
 538           Int64Ty->getScalarSizeInBits())
 539         continue;
 540       Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
 541       Initializers.push_back(
 542           ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
 543       if (Cond->getType()->getScalarSizeInBits() <
 544           Int64Ty->getScalarSizeInBits())
 545         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
 546       for (auto It : SI->cases()) {
 547         Constant *C = It.getCaseValue();
 548         if (C->getType()->getScalarSizeInBits() <
 549             Int64Ty->getScalarSizeInBits())
 550           C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
 551         Initializers.push_back(C);
 552       }
 553       std::sort(Initializers.begin() + 2, Initializers.end(),
 554                 [](const Constant *A, const Constant *B) {
 555                   return cast<ConstantInt>(A)->getLimitedValue() <
 556                          cast<ConstantInt>(B)->getLimitedValue();
 557                 });
 558       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
 559       GlobalVariable *GV = new GlobalVariable(
 560           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
 561           ConstantArray::get(ArrayOfInt64Ty, Initializers),
 562           "__sancov_gen_cov_switch_values");
 563       IRB.CreateCall(SanCovTraceSwitchFunction,
 564                      {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
 565     }
 566   }
 567 }
 568
 569 void SanitizerCoverageModule::InjectTraceForDiv(
 570     Function &, ArrayRef<BinaryOperator *> DivTraceTargets) {
 571   for (auto BO : DivTraceTargets) {
 572     IRBuilder<> IRB(BO);
 573     Value *A1 = BO->getOperand(1);
 574     if (isa<ConstantInt>(A1)) continue;
 575     if (!A1->getType()->isIntegerTy())
 576       continue;
 577     uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType());
 578     int CallbackIdx = TypeSize == 32 ? 0 :
 579         TypeSize == 64 ? 1 : -1;
 580     if (CallbackIdx < 0) continue;
 581     auto Ty = Type::getIntNTy(*C, TypeSize);
 582     IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx],
 583                    {IRB.CreateIntCast(A1, Ty, true)});
 584   }
 585 }
 586
 587 void SanitizerCoverageModule::InjectTraceForGep(
 588     Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) {
 589   for (auto GEP : GepTraceTargets) {
 590     IRBuilder<> IRB(GEP);
 591     for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
 592       if (!isa<ConstantInt>(*I) && (*I)->getType()->isIntegerTy())
 593         IRB.CreateCall(SanCovTraceGepFunction,
 594                        {IRB.CreateIntCast(*I, IntptrTy, true)});
 595   }
 596 }
 597
 598 void SanitizerCoverageModule::InjectTraceForCmp(
 599     Function &, ArrayRef<Instruction *> CmpTraceTargets) {
 600   for (auto I : CmpTraceTargets) {
 601     if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
 602       IRBuilder<> IRB(ICMP);
 603       Value *A0 = ICMP->getOperand(0);
 604       Value *A1 = ICMP->getOperand(1);
 605       if (!A0->getType()->isIntegerTy())
 606         continue;
 607       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
 608       int CallbackIdx = TypeSize == 8 ? 0 :
 609                         TypeSize == 16 ? 1 :
 610                         TypeSize == 32 ? 2 :
 611                         TypeSize == 64 ? 3 : -1;
 612       if (CallbackIdx < 0) continue;
 613       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
 614       auto Ty = Type::getIntNTy(*C, TypeSize);
 615       IRB.CreateCall(
 616           SanCovTraceCmpFunction[CallbackIdx],
 617           {IRB.CreateIntCast(A0, Ty, true), IRB.CreateIntCast(A1, Ty, true)});
 618     }
 619   }
 620 }
 621
 622 void SanitizerCoverageModule::SetNoSanitizeMetadata(Instruction *I) {
 623   I->setMetadata(I->getModule()->getMDKindID("nosanitize"),
 624                  MDNode::get(*C, None));
 625 }
 626
 627 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
 628                                                     size_t Idx, bool UseCalls) {
 629   BasicBlock::iterator IP = BB.getFirstInsertionPt();
 630   bool IsEntryBB = &BB == &F.getEntryBlock();
 631   DebugLoc EntryLoc;
 632   if (IsEntryBB) {
 633     if (auto SP = F.getSubprogram())
 634       EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP);
 635     // Keep static allocas and llvm.localescape calls in the entry block.  Even
 636     // if we aren't splitting the block, it's nice for allocas to be before
 637     // calls.
 638     IP = PrepareToSplitEntryBlock(BB, IP);
 639   } else {
 640     EntryLoc = IP->getDebugLoc();
 641   }
 642
 643   IRBuilder<> IRB(&*IP);
 644   IRB.SetCurrentDebugLocation(EntryLoc);
 645   if (Options.TracePC) {
 646     IRB.CreateCall(SanCovTracePC); // gets the PC using GET_CALLER_PC.
 647     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 648   } else if (Options.TracePCGuard) {
 649     auto GuardPtr = IRB.CreateIntToPtr(
 650         IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy),
 651                       ConstantInt::get(IntptrTy, Idx * 4)),
 652         Int32PtrTy);
 653     if (!UseCalls) {
 654       auto GuardLoad = IRB.CreateLoad(GuardPtr);
 655       GuardLoad->setAtomic(AtomicOrdering::Monotonic);
 656       GuardLoad->setAlignment(8);
 657       SetNoSanitizeMetadata(GuardLoad);  // Don't instrument with e.g. asan.
 658       auto Cmp = IRB.CreateICmpNE(
 659           GuardLoad, Constant::getNullValue(GuardLoad->getType()));
 660       auto Ins = SplitBlockAndInsertIfThen(
 661           Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
 662       IRB.SetInsertPoint(Ins);
 663       IRB.SetCurrentDebugLocation(EntryLoc);
 664     }
 665     IRB.CreateCall(SanCovTracePCGuard, GuardPtr);
 666     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 667   } else {
 668     Value *GuardP = IRB.CreateAdd(
 669         IRB.CreatePointerCast(GuardArray, IntptrTy),
 670         ConstantInt::get(IntptrTy, (1 + NumberOfInstrumentedBlocks()) * 4));
 671     GuardP = IRB.CreateIntToPtr(GuardP, Int32PtrTy);
 672     if (UseCalls) {
 673       IRB.CreateCall(SanCovWithCheckFunction, GuardP);
 674     } else {
 675       LoadInst *Load = IRB.CreateLoad(GuardP);
 676       Load->setAtomic(AtomicOrdering::Monotonic);
 677       Load->setAlignment(4);
 678       SetNoSanitizeMetadata(Load);
 679       Value *Cmp =
 680           IRB.CreateICmpSGE(Constant::getNullValue(Load->getType()), Load);
 681       Instruction *Ins = SplitBlockAndInsertIfThen(
 682           Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
 683       IRB.SetInsertPoint(Ins);
 684       IRB.SetCurrentDebugLocation(EntryLoc);
 685       // __sanitizer_cov gets the PC of the instruction using GET_CALLER_PC.
 686       IRB.CreateCall(SanCovFunction, GuardP);
 687       IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
 688     }
 689   }
 690 }
 691
 692 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSection() const {
 693   if (TargetTriple.getObjectFormat() == Triple::COFF)
 694     return ".SCOV$M";
 695   if (TargetTriple.isOSBinFormatMachO())
 696     return "__DATA,__sancov_guards";
 697   return "__sancov_guards";
 698 }
 699
 700 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSectionStart() const {
 701   if (TargetTriple.isOSBinFormatMachO())
 702     return "\1section$start$__DATA$__sancov_guards";
 703   return "__start___sancov_guards";
 704 }
 705
 706 StringRef SanitizerCoverageModule::getSanCovTracePCGuardSectionEnd() const {
 707   if (TargetTriple.isOSBinFormatMachO())
 708     return "\1section$end$__DATA$__sancov_guards";
 709   return "__stop___sancov_guards";
 710 }
 711
 712
 713 char SanitizerCoverageModule::ID = 0;
 714 INITIALIZE_PASS_BEGIN(SanitizerCoverageModule, "sancov",
 715                       "SanitizerCoverage: TODO."
 716                       "ModulePass",
 717                       false, false)
 718 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 719 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 720 INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov",
 721                     "SanitizerCoverage: TODO."
 722                     "ModulePass",
 723                     false, false)
 724 ModulePass *llvm::createSanitizerCoverageModulePass(
 725     const SanitizerCoverageOptions &Options) {
 726   return new SanitizerCoverageModule(Options);
 727 }