1 //===-- SanitizerCoverage.cpp - coverage instrumentation for sanitizers ---===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Coverage instrumentation done on LLVM IR level, works with Sanitizers. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/ADT/ArrayRef.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/Analysis/EHPersonalities.h" 16 #include "llvm/Analysis/PostDominators.h" 17 #include "llvm/IR/CFG.h" 18 #include "llvm/IR/CallSite.h" 19 #include "llvm/IR/Constant.h" 20 #include "llvm/IR/DataLayout.h" 21 #include "llvm/IR/DebugInfo.h" 22 #include "llvm/IR/Dominators.h" 23 #include "llvm/IR/Function.h" 24 #include "llvm/IR/GlobalVariable.h" 25 #include "llvm/IR/IRBuilder.h" 26 #include "llvm/IR/InlineAsm.h" 27 #include "llvm/IR/IntrinsicInst.h" 28 #include "llvm/IR/Intrinsics.h" 29 #include "llvm/IR/LLVMContext.h" 30 #include "llvm/IR/MDBuilder.h" 31 #include "llvm/IR/Mangler.h" 32 #include "llvm/IR/Module.h" 33 #include "llvm/IR/Type.h" 34 #include "llvm/Support/CommandLine.h" 35 #include "llvm/Support/Debug.h" 36 #include "llvm/Support/raw_ostream.h" 37 #include "llvm/Transforms/Instrumentation.h" 38 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 39 #include "llvm/Transforms/Utils/ModuleUtils.h" 40 41 using namespace llvm; 42 43 #define DEBUG_TYPE "sancov" 44 45 static const char *const SanCovTracePCIndirName = 46 "__sanitizer_cov_trace_pc_indir"; 47 static const char *const SanCovTracePCName = "__sanitizer_cov_trace_pc"; 48 static const char *const SanCovTraceCmp1 = "__sanitizer_cov_trace_cmp1"; 49 static const char *const SanCovTraceCmp2 = "__sanitizer_cov_trace_cmp2"; 50 static const char *const SanCovTraceCmp4 = "__sanitizer_cov_trace_cmp4"; 51 static const char *const SanCovTraceCmp8 = "__sanitizer_cov_trace_cmp8"; 52 static const char *const SanCovTraceConstCmp1 = 53 "__sanitizer_cov_trace_const_cmp1"; 54 static const char *const SanCovTraceConstCmp2 = 55 "__sanitizer_cov_trace_const_cmp2"; 56 static const char *const SanCovTraceConstCmp4 = 57 "__sanitizer_cov_trace_const_cmp4"; 58 static const char *const SanCovTraceConstCmp8 = 59 "__sanitizer_cov_trace_const_cmp8"; 60 static const char *const SanCovTraceDiv4 = "__sanitizer_cov_trace_div4"; 61 static const char *const SanCovTraceDiv8 = "__sanitizer_cov_trace_div8"; 62 static const char *const SanCovTraceGep = "__sanitizer_cov_trace_gep"; 63 static const char *const SanCovTraceSwitchName = "__sanitizer_cov_trace_switch"; 64 static const char *const SanCovModuleCtorTracePcGuardName = 65 "sancov.module_ctor_trace_pc_guard"; 66 static const char *const SanCovModuleCtor8bitCountersName = 67 "sancov.module_ctor_8bit_counters"; 68 static const uint64_t SanCtorAndDtorPriority = 2; 69 70 static const char *const SanCovTracePCGuardName = 71 "__sanitizer_cov_trace_pc_guard"; 72 static const char *const SanCovTracePCGuardInitName = 73 "__sanitizer_cov_trace_pc_guard_init"; 74 static const char *const SanCov8bitCountersInitName = 75 "__sanitizer_cov_8bit_counters_init"; 76 static const char *const SanCovPCsInitName = "__sanitizer_cov_pcs_init"; 77 78 static const char *const SanCovGuardsSectionName = "sancov_guards"; 79 static const char *const SanCovCountersSectionName = "sancov_cntrs"; 80 static const char *const SanCovPCsSectionName = "sancov_pcs"; 81 82 static const char *const SanCovLowestStackName = "__sancov_lowest_stack"; 83 84 static cl::opt<int> ClCoverageLevel( 85 "sanitizer-coverage-level", 86 cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, " 87 "3: all blocks and critical edges"), 88 cl::Hidden, cl::init(0)); 89 90 static cl::opt<bool> ClTracePC("sanitizer-coverage-trace-pc", 91 cl::desc("Experimental pc tracing"), cl::Hidden, 92 cl::init(false)); 93 94 static cl::opt<bool> ClTracePCGuard("sanitizer-coverage-trace-pc-guard", 95 cl::desc("pc tracing with a guard"), 96 cl::Hidden, cl::init(false)); 97 98 // If true, we create a global variable that contains PCs of all instrumented 99 // BBs, put this global into a named section, and pass this section's bounds 100 // to __sanitizer_cov_pcs_init. 101 // This way the coverage instrumentation does not need to acquire the PCs 102 // at run-time. Works with trace-pc-guard and inline-8bit-counters. 103 static cl::opt<bool> ClCreatePCTable("sanitizer-coverage-pc-table", 104 cl::desc("create a static PC table"), 105 cl::Hidden, cl::init(false)); 106 107 static cl::opt<bool> 108 ClInline8bitCounters("sanitizer-coverage-inline-8bit-counters", 109 cl::desc("increments 8-bit counter for every edge"), 110 cl::Hidden, cl::init(false)); 111 112 static cl::opt<bool> 113 ClCMPTracing("sanitizer-coverage-trace-compares", 114 cl::desc("Tracing of CMP and similar instructions"), 115 cl::Hidden, cl::init(false)); 116 117 static cl::opt<bool> ClDIVTracing("sanitizer-coverage-trace-divs", 118 cl::desc("Tracing of DIV instructions"), 119 cl::Hidden, cl::init(false)); 120 121 static cl::opt<bool> ClGEPTracing("sanitizer-coverage-trace-geps", 122 cl::desc("Tracing of GEP instructions"), 123 cl::Hidden, cl::init(false)); 124 125 static cl::opt<bool> 126 ClPruneBlocks("sanitizer-coverage-prune-blocks", 127 cl::desc("Reduce the number of instrumented blocks"), 128 cl::Hidden, cl::init(true)); 129 130 static cl::opt<bool> ClStackDepth("sanitizer-coverage-stack-depth", 131 cl::desc("max stack depth tracing"), 132 cl::Hidden, cl::init(false)); 133 134 namespace { 135 136 SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) { 137 SanitizerCoverageOptions Res; 138 switch (LegacyCoverageLevel) { 139 case 0: 140 Res.CoverageType = SanitizerCoverageOptions::SCK_None; 141 break; 142 case 1: 143 Res.CoverageType = SanitizerCoverageOptions::SCK_Function; 144 break; 145 case 2: 146 Res.CoverageType = SanitizerCoverageOptions::SCK_BB; 147 break; 148 case 3: 149 Res.CoverageType = SanitizerCoverageOptions::SCK_Edge; 150 break; 151 case 4: 152 Res.CoverageType = SanitizerCoverageOptions::SCK_Edge; 153 Res.IndirectCalls = true; 154 break; 155 } 156 return Res; 157 } 158 159 SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) { 160 // Sets CoverageType and IndirectCalls. 161 SanitizerCoverageOptions CLOpts = getOptions(ClCoverageLevel); 162 Options.CoverageType = std::max(Options.CoverageType, CLOpts.CoverageType); 163 Options.IndirectCalls |= CLOpts.IndirectCalls; 164 Options.TraceCmp |= ClCMPTracing; 165 Options.TraceDiv |= ClDIVTracing; 166 Options.TraceGep |= ClGEPTracing; 167 Options.TracePC |= ClTracePC; 168 Options.TracePCGuard |= ClTracePCGuard; 169 Options.Inline8bitCounters |= ClInline8bitCounters; 170 Options.PCTable |= ClCreatePCTable; 171 Options.NoPrune |= !ClPruneBlocks; 172 Options.StackDepth |= ClStackDepth; 173 if (!Options.TracePCGuard && !Options.TracePC && 174 !Options.Inline8bitCounters && !Options.StackDepth) 175 Options.TracePCGuard = true; // TracePCGuard is default. 176 return Options; 177 } 178 179 class SanitizerCoverageModule : public ModulePass { 180 public: 181 SanitizerCoverageModule( 182 const SanitizerCoverageOptions &Options = SanitizerCoverageOptions()) 183 : ModulePass(ID), Options(OverrideFromCL(Options)) { 184 initializeSanitizerCoverageModulePass(*PassRegistry::getPassRegistry()); 185 } 186 bool runOnModule(Module &M) override; 187 bool runOnFunction(Function &F); 188 static char ID; // Pass identification, replacement for typeid 189 StringRef getPassName() const override { return "SanitizerCoverageModule"; } 190 191 void getAnalysisUsage(AnalysisUsage &AU) const override { 192 AU.addRequired<DominatorTreeWrapperPass>(); 193 AU.addRequired<PostDominatorTreeWrapperPass>(); 194 } 195 196 private: 197 void InjectCoverageForIndirectCalls(Function &F, 198 ArrayRef<Instruction *> IndirCalls); 199 void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets); 200 void InjectTraceForDiv(Function &F, 201 ArrayRef<BinaryOperator *> DivTraceTargets); 202 void InjectTraceForGep(Function &F, 203 ArrayRef<GetElementPtrInst *> GepTraceTargets); 204 void InjectTraceForSwitch(Function &F, 205 ArrayRef<Instruction *> SwitchTraceTargets); 206 bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks, 207 bool IsLeafFunc = true); 208 GlobalVariable *CreateFunctionLocalArrayInSection(size_t NumElements, 209 Function &F, Type *Ty, 210 const char *Section); 211 GlobalVariable *CreatePCArray(Function &F, ArrayRef<BasicBlock *> AllBlocks); 212 void CreateFunctionLocalArrays(Function &F, ArrayRef<BasicBlock *> AllBlocks); 213 void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx, 214 bool IsLeafFunc = true); 215 Function *CreateInitCallsForSections(Module &M, const char *CtorName, 216 const char *InitFunctionName, Type *Ty, 217 const char *Section); 218 std::pair<Value *, Value *> CreateSecStartEnd(Module &M, const char *Section, 219 Type *Ty); 220 221 void SetNoSanitizeMetadata(Instruction *I) { 222 I->setMetadata(I->getModule()->getMDKindID("nosanitize"), 223 MDNode::get(*C, None)); 224 } 225 226 std::string getSectionName(const std::string &Section) const; 227 std::string getSectionStart(const std::string &Section) const; 228 std::string getSectionEnd(const std::string &Section) const; 229 FunctionCallee SanCovTracePCIndir; 230 FunctionCallee SanCovTracePC, SanCovTracePCGuard; 231 FunctionCallee SanCovTraceCmpFunction[4]; 232 FunctionCallee SanCovTraceConstCmpFunction[4]; 233 FunctionCallee SanCovTraceDivFunction[2]; 234 FunctionCallee SanCovTraceGepFunction; 235 FunctionCallee SanCovTraceSwitchFunction; 236 GlobalVariable *SanCovLowestStack; 237 InlineAsm *EmptyAsm; 238 Type *IntptrTy, *IntptrPtrTy, *Int64Ty, *Int64PtrTy, *Int32Ty, *Int32PtrTy, 239 *Int16Ty, *Int8Ty, *Int8PtrTy; 240 Module *CurModule; 241 std::string CurModuleUniqueId; 242 Triple TargetTriple; 243 LLVMContext *C; 244 const DataLayout *DL; 245 246 GlobalVariable *FunctionGuardArray; // for trace-pc-guard. 247 GlobalVariable *Function8bitCounterArray; // for inline-8bit-counters. 248 GlobalVariable *FunctionPCsArray; // for pc-table. 249 SmallVector<GlobalValue *, 20> GlobalsToAppendToUsed; 250 SmallVector<GlobalValue *, 20> GlobalsToAppendToCompilerUsed; 251 252 SanitizerCoverageOptions Options; 253 }; 254 255 } // namespace 256 257 std::pair<Value *, Value *> 258 SanitizerCoverageModule::CreateSecStartEnd(Module &M, const char *Section, 259 Type *Ty) { 260 GlobalVariable *SecStart = 261 new GlobalVariable(M, Ty, false, GlobalVariable::ExternalLinkage, nullptr, 262 getSectionStart(Section)); 263 SecStart->setVisibility(GlobalValue::HiddenVisibility); 264 GlobalVariable *SecEnd = 265 new GlobalVariable(M, Ty, false, GlobalVariable::ExternalLinkage, 266 nullptr, getSectionEnd(Section)); 267 SecEnd->setVisibility(GlobalValue::HiddenVisibility); 268 IRBuilder<> IRB(M.getContext()); 269 Value *SecEndPtr = IRB.CreatePointerCast(SecEnd, Ty); 270 if (!TargetTriple.isOSBinFormatCOFF()) 271 return std::make_pair(IRB.CreatePointerCast(SecStart, Ty), SecEndPtr); 272 273 // Account for the fact that on windows-msvc __start_* symbols actually 274 // point to a uint64_t before the start of the array. 275 auto SecStartI8Ptr = IRB.CreatePointerCast(SecStart, Int8PtrTy); 276 auto GEP = IRB.CreateGEP(Int8Ty, SecStartI8Ptr, 277 ConstantInt::get(IntptrTy, sizeof(uint64_t))); 278 return std::make_pair(IRB.CreatePointerCast(GEP, Ty), SecEndPtr); 279 } 280 281 Function *SanitizerCoverageModule::CreateInitCallsForSections( 282 Module &M, const char *CtorName, const char *InitFunctionName, Type *Ty, 283 const char *Section) { 284 auto SecStartEnd = CreateSecStartEnd(M, Section, Ty); 285 auto SecStart = SecStartEnd.first; 286 auto SecEnd = SecStartEnd.second; 287 Function *CtorFunc; 288 std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions( 289 M, CtorName, InitFunctionName, {Ty, Ty}, {SecStart, SecEnd}); 290 assert(CtorFunc->getName() == CtorName); 291 292 if (TargetTriple.supportsCOMDAT()) { 293 // Use comdat to dedup CtorFunc. 294 CtorFunc->setComdat(M.getOrInsertComdat(CtorName)); 295 appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc); 296 } else { 297 appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority); 298 } 299 300 if (TargetTriple.isOSBinFormatCOFF()) { 301 // In COFF files, if the contructors are set as COMDAT (they are because 302 // COFF supports COMDAT) and the linker flag /OPT:REF (strip unreferenced 303 // functions and data) is used, the constructors get stripped. To prevent 304 // this, give the constructors weak ODR linkage and ensure the linker knows 305 // to include the sancov constructor. This way the linker can deduplicate 306 // the constructors but always leave one copy. 307 CtorFunc->setLinkage(GlobalValue::WeakODRLinkage); 308 appendToUsed(M, CtorFunc); 309 } 310 return CtorFunc; 311 } 312 313 bool SanitizerCoverageModule::runOnModule(Module &M) { 314 if (Options.CoverageType == SanitizerCoverageOptions::SCK_None) 315 return false; 316 C = &(M.getContext()); 317 DL = &M.getDataLayout(); 318 CurModule = &M; 319 CurModuleUniqueId = getUniqueModuleId(CurModule); 320 TargetTriple = Triple(M.getTargetTriple()); 321 FunctionGuardArray = nullptr; 322 Function8bitCounterArray = nullptr; 323 FunctionPCsArray = nullptr; 324 IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits()); 325 IntptrPtrTy = PointerType::getUnqual(IntptrTy); 326 Type *VoidTy = Type::getVoidTy(*C); 327 IRBuilder<> IRB(*C); 328 Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty()); 329 Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty()); 330 Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty()); 331 Int64Ty = IRB.getInt64Ty(); 332 Int32Ty = IRB.getInt32Ty(); 333 Int16Ty = IRB.getInt16Ty(); 334 Int8Ty = IRB.getInt8Ty(); 335 336 SanCovTracePCIndir = 337 M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy); 338 // Make sure smaller parameters are zero-extended to i64 as required by the 339 // x86_64 ABI. 340 AttributeList SanCovTraceCmpZeroExtAL; 341 if (TargetTriple.getArch() == Triple::x86_64) { 342 SanCovTraceCmpZeroExtAL = 343 SanCovTraceCmpZeroExtAL.addParamAttribute(*C, 0, Attribute::ZExt); 344 SanCovTraceCmpZeroExtAL = 345 SanCovTraceCmpZeroExtAL.addParamAttribute(*C, 1, Attribute::ZExt); 346 } 347 348 SanCovTraceCmpFunction[0] = 349 M.getOrInsertFunction(SanCovTraceCmp1, SanCovTraceCmpZeroExtAL, VoidTy, 350 IRB.getInt8Ty(), IRB.getInt8Ty()); 351 SanCovTraceCmpFunction[1] = 352 M.getOrInsertFunction(SanCovTraceCmp2, SanCovTraceCmpZeroExtAL, VoidTy, 353 IRB.getInt16Ty(), IRB.getInt16Ty()); 354 SanCovTraceCmpFunction[2] = 355 M.getOrInsertFunction(SanCovTraceCmp4, SanCovTraceCmpZeroExtAL, VoidTy, 356 IRB.getInt32Ty(), IRB.getInt32Ty()); 357 SanCovTraceCmpFunction[3] = 358 M.getOrInsertFunction(SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty); 359 360 SanCovTraceConstCmpFunction[0] = M.getOrInsertFunction( 361 SanCovTraceConstCmp1, SanCovTraceCmpZeroExtAL, VoidTy, Int8Ty, Int8Ty); 362 SanCovTraceConstCmpFunction[1] = M.getOrInsertFunction( 363 SanCovTraceConstCmp2, SanCovTraceCmpZeroExtAL, VoidTy, Int16Ty, Int16Ty); 364 SanCovTraceConstCmpFunction[2] = M.getOrInsertFunction( 365 SanCovTraceConstCmp4, SanCovTraceCmpZeroExtAL, VoidTy, Int32Ty, Int32Ty); 366 SanCovTraceConstCmpFunction[3] = 367 M.getOrInsertFunction(SanCovTraceConstCmp8, VoidTy, Int64Ty, Int64Ty); 368 369 { 370 AttributeList AL; 371 if (TargetTriple.getArch() == Triple::x86_64) 372 AL = AL.addParamAttribute(*C, 0, Attribute::ZExt); 373 SanCovTraceDivFunction[0] = 374 M.getOrInsertFunction(SanCovTraceDiv4, AL, VoidTy, IRB.getInt32Ty()); 375 } 376 SanCovTraceDivFunction[1] = 377 M.getOrInsertFunction(SanCovTraceDiv8, VoidTy, Int64Ty); 378 SanCovTraceGepFunction = 379 M.getOrInsertFunction(SanCovTraceGep, VoidTy, IntptrTy); 380 SanCovTraceSwitchFunction = 381 M.getOrInsertFunction(SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy); 382 383 Constant *SanCovLowestStackConstant = 384 M.getOrInsertGlobal(SanCovLowestStackName, IntptrTy); 385 SanCovLowestStack = dyn_cast<GlobalVariable>(SanCovLowestStackConstant); 386 if (!SanCovLowestStack) { 387 C->emitError(StringRef("'") + SanCovLowestStackName + 388 "' should not be declared by the user"); 389 return true; 390 } 391 SanCovLowestStack->setThreadLocalMode( 392 GlobalValue::ThreadLocalMode::InitialExecTLSModel); 393 if (Options.StackDepth && !SanCovLowestStack->isDeclaration()) 394 SanCovLowestStack->setInitializer(Constant::getAllOnesValue(IntptrTy)); 395 396 // We insert an empty inline asm after cov callbacks to avoid callback merge. 397 EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false), 398 StringRef(""), StringRef(""), 399 /*hasSideEffects=*/true); 400 401 SanCovTracePC = M.getOrInsertFunction(SanCovTracePCName, VoidTy); 402 SanCovTracePCGuard = 403 M.getOrInsertFunction(SanCovTracePCGuardName, VoidTy, Int32PtrTy); 404 405 for (auto &F : M) 406 runOnFunction(F); 407 408 Function *Ctor = nullptr; 409 410 if (FunctionGuardArray) 411 Ctor = CreateInitCallsForSections(M, SanCovModuleCtorTracePcGuardName, 412 SanCovTracePCGuardInitName, Int32PtrTy, 413 SanCovGuardsSectionName); 414 if (Function8bitCounterArray) 415 Ctor = CreateInitCallsForSections(M, SanCovModuleCtor8bitCountersName, 416 SanCov8bitCountersInitName, Int8PtrTy, 417 SanCovCountersSectionName); 418 if (Ctor && Options.PCTable) { 419 auto SecStartEnd = CreateSecStartEnd(M, SanCovPCsSectionName, IntptrPtrTy); 420 FunctionCallee InitFunction = declareSanitizerInitFunction( 421 M, SanCovPCsInitName, {IntptrPtrTy, IntptrPtrTy}); 422 IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator()); 423 IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second}); 424 } 425 // We don't reference these arrays directly in any of our runtime functions, 426 // so we need to prevent them from being dead stripped. 427 if (TargetTriple.isOSBinFormatMachO()) 428 appendToUsed(M, GlobalsToAppendToUsed); 429 appendToCompilerUsed(M, GlobalsToAppendToCompilerUsed); 430 return true; 431 } 432 433 // True if block has successors and it dominates all of them. 434 static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) { 435 if (succ_begin(BB) == succ_end(BB)) 436 return false; 437 438 for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) { 439 if (!DT->dominates(BB, SUCC)) 440 return false; 441 } 442 443 return true; 444 } 445 446 // True if block has predecessors and it postdominates all of them. 447 static bool isFullPostDominator(const BasicBlock *BB, 448 const PostDominatorTree *PDT) { 449 if (pred_begin(BB) == pred_end(BB)) 450 return false; 451 452 for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) { 453 if (!PDT->dominates(BB, PRED)) 454 return false; 455 } 456 457 return true; 458 } 459 460 static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB, 461 const DominatorTree *DT, 462 const PostDominatorTree *PDT, 463 const SanitizerCoverageOptions &Options) { 464 // Don't insert coverage for blocks containing nothing but unreachable: we 465 // will never call __sanitizer_cov() for them, so counting them in 466 // NumberOfInstrumentedBlocks() might complicate calculation of code coverage 467 // percentage. Also, unreachable instructions frequently have no debug 468 // locations. 469 if (isa<UnreachableInst>(BB->getFirstNonPHIOrDbgOrLifetime())) 470 return false; 471 472 // Don't insert coverage into blocks without a valid insertion point 473 // (catchswitch blocks). 474 if (BB->getFirstInsertionPt() == BB->end()) 475 return false; 476 477 if (Options.NoPrune || &F.getEntryBlock() == BB) 478 return true; 479 480 if (Options.CoverageType == SanitizerCoverageOptions::SCK_Function && 481 &F.getEntryBlock() != BB) 482 return false; 483 484 // Do not instrument full dominators, or full post-dominators with multiple 485 // predecessors. 486 return !isFullDominator(BB, DT) 487 && !(isFullPostDominator(BB, PDT) && !BB->getSinglePredecessor()); 488 } 489 490 491 // Returns true iff From->To is a backedge. 492 // A twist here is that we treat From->To as a backedge if 493 // * To dominates From or 494 // * To->UniqueSuccessor dominates From 495 static bool IsBackEdge(BasicBlock *From, BasicBlock *To, 496 const DominatorTree *DT) { 497 if (DT->dominates(To, From)) 498 return true; 499 if (auto Next = To->getUniqueSuccessor()) 500 if (DT->dominates(Next, From)) 501 return true; 502 return false; 503 } 504 505 // Prunes uninteresting Cmp instrumentation: 506 // * CMP instructions that feed into loop backedge branch. 507 // 508 // Note that Cmp pruning is controlled by the same flag as the 509 // BB pruning. 510 static bool IsInterestingCmp(ICmpInst *CMP, const DominatorTree *DT, 511 const SanitizerCoverageOptions &Options) { 512 if (!Options.NoPrune) 513 if (CMP->hasOneUse()) 514 if (auto BR = dyn_cast<BranchInst>(CMP->user_back())) 515 for (BasicBlock *B : BR->successors()) 516 if (IsBackEdge(BR->getParent(), B, DT)) 517 return false; 518 return true; 519 } 520 521 bool SanitizerCoverageModule::runOnFunction(Function &F) { 522 if (F.empty()) 523 return false; 524 if (F.getName().find(".module_ctor") != std::string::npos) 525 return false; // Should not instrument sanitizer init functions. 526 if (F.getName().startswith("__sanitizer_")) 527 return false; // Don't instrument __sanitizer_* callbacks. 528 // Don't touch available_externally functions, their actual body is elewhere. 529 if (F.getLinkage() == GlobalValue::AvailableExternallyLinkage) 530 return false; 531 // Don't instrument MSVC CRT configuration helpers. They may run before normal 532 // initialization. 533 if (F.getName() == "__local_stdio_printf_options" || 534 F.getName() == "__local_stdio_scanf_options") 535 return false; 536 if (isa<UnreachableInst>(F.getEntryBlock().getTerminator())) 537 return false; 538 // Don't instrument functions using SEH for now. Splitting basic blocks like 539 // we do for coverage breaks WinEHPrepare. 540 // FIXME: Remove this when SEH no longer uses landingpad pattern matching. 541 if (F.hasPersonalityFn() && 542 isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn()))) 543 return false; 544 if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge) 545 SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions().setIgnoreUnreachableDests()); 546 SmallVector<Instruction *, 8> IndirCalls; 547 SmallVector<BasicBlock *, 16> BlocksToInstrument; 548 SmallVector<Instruction *, 8> CmpTraceTargets; 549 SmallVector<Instruction *, 8> SwitchTraceTargets; 550 SmallVector<BinaryOperator *, 8> DivTraceTargets; 551 SmallVector<GetElementPtrInst *, 8> GepTraceTargets; 552 553 const DominatorTree *DT = 554 &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree(); 555 const PostDominatorTree *PDT = 556 &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree(); 557 bool IsLeafFunc = true; 558 559 for (auto &BB : F) { 560 if (shouldInstrumentBlock(F, &BB, DT, PDT, Options)) 561 BlocksToInstrument.push_back(&BB); 562 for (auto &Inst : BB) { 563 if (Options.IndirectCalls) { 564 CallSite CS(&Inst); 565 if (CS && !CS.getCalledFunction()) 566 IndirCalls.push_back(&Inst); 567 } 568 if (Options.TraceCmp) { 569 if (ICmpInst *CMP = dyn_cast<ICmpInst>(&Inst)) 570 if (IsInterestingCmp(CMP, DT, Options)) 571 CmpTraceTargets.push_back(&Inst); 572 if (isa<SwitchInst>(&Inst)) 573 SwitchTraceTargets.push_back(&Inst); 574 } 575 if (Options.TraceDiv) 576 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst)) 577 if (BO->getOpcode() == Instruction::SDiv || 578 BO->getOpcode() == Instruction::UDiv) 579 DivTraceTargets.push_back(BO); 580 if (Options.TraceGep) 581 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst)) 582 GepTraceTargets.push_back(GEP); 583 if (Options.StackDepth) 584 if (isa<InvokeInst>(Inst) || 585 (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst))) 586 IsLeafFunc = false; 587 } 588 } 589 590 InjectCoverage(F, BlocksToInstrument, IsLeafFunc); 591 InjectCoverageForIndirectCalls(F, IndirCalls); 592 InjectTraceForCmp(F, CmpTraceTargets); 593 InjectTraceForSwitch(F, SwitchTraceTargets); 594 InjectTraceForDiv(F, DivTraceTargets); 595 InjectTraceForGep(F, GepTraceTargets); 596 return true; 597 } 598 599 GlobalVariable *SanitizerCoverageModule::CreateFunctionLocalArrayInSection( 600 size_t NumElements, Function &F, Type *Ty, const char *Section) { 601 ArrayType *ArrayTy = ArrayType::get(Ty, NumElements); 602 auto Array = new GlobalVariable( 603 *CurModule, ArrayTy, false, GlobalVariable::PrivateLinkage, 604 Constant::getNullValue(ArrayTy), "__sancov_gen_"); 605 606 if (TargetTriple.supportsCOMDAT() && !F.isInterposable()) 607 if (auto Comdat = 608 GetOrCreateFunctionComdat(F, TargetTriple, CurModuleUniqueId)) 609 Array->setComdat(Comdat); 610 Array->setSection(getSectionName(Section)); 611 Array->setAlignment(Ty->isPointerTy() ? DL->getPointerSize() 612 : Ty->getPrimitiveSizeInBits() / 8); 613 GlobalsToAppendToUsed.push_back(Array); 614 GlobalsToAppendToCompilerUsed.push_back(Array); 615 MDNode *MD = MDNode::get(F.getContext(), ValueAsMetadata::get(&F)); 616 Array->addMetadata(LLVMContext::MD_associated, *MD); 617 618 return Array; 619 } 620 621 GlobalVariable * 622 SanitizerCoverageModule::CreatePCArray(Function &F, 623 ArrayRef<BasicBlock *> AllBlocks) { 624 size_t N = AllBlocks.size(); 625 assert(N); 626 SmallVector<Constant *, 32> PCs; 627 IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt()); 628 for (size_t i = 0; i < N; i++) { 629 if (&F.getEntryBlock() == AllBlocks[i]) { 630 PCs.push_back((Constant *)IRB.CreatePointerCast(&F, IntptrPtrTy)); 631 PCs.push_back((Constant *)IRB.CreateIntToPtr( 632 ConstantInt::get(IntptrTy, 1), IntptrPtrTy)); 633 } else { 634 PCs.push_back((Constant *)IRB.CreatePointerCast( 635 BlockAddress::get(AllBlocks[i]), IntptrPtrTy)); 636 PCs.push_back((Constant *)IRB.CreateIntToPtr( 637 ConstantInt::get(IntptrTy, 0), IntptrPtrTy)); 638 } 639 } 640 auto *PCArray = CreateFunctionLocalArrayInSection(N * 2, F, IntptrPtrTy, 641 SanCovPCsSectionName); 642 PCArray->setInitializer( 643 ConstantArray::get(ArrayType::get(IntptrPtrTy, N * 2), PCs)); 644 PCArray->setConstant(true); 645 646 return PCArray; 647 } 648 649 void SanitizerCoverageModule::CreateFunctionLocalArrays( 650 Function &F, ArrayRef<BasicBlock *> AllBlocks) { 651 if (Options.TracePCGuard) 652 FunctionGuardArray = CreateFunctionLocalArrayInSection( 653 AllBlocks.size(), F, Int32Ty, SanCovGuardsSectionName); 654 655 if (Options.Inline8bitCounters) 656 Function8bitCounterArray = CreateFunctionLocalArrayInSection( 657 AllBlocks.size(), F, Int8Ty, SanCovCountersSectionName); 658 659 if (Options.PCTable) 660 FunctionPCsArray = CreatePCArray(F, AllBlocks); 661 } 662 663 bool SanitizerCoverageModule::InjectCoverage(Function &F, 664 ArrayRef<BasicBlock *> AllBlocks, 665 bool IsLeafFunc) { 666 if (AllBlocks.empty()) return false; 667 CreateFunctionLocalArrays(F, AllBlocks); 668 for (size_t i = 0, N = AllBlocks.size(); i < N; i++) 669 InjectCoverageAtBlock(F, *AllBlocks[i], i, IsLeafFunc); 670 return true; 671 } 672 673 // On every indirect call we call a run-time function 674 // __sanitizer_cov_indir_call* with two parameters: 675 // - callee address, 676 // - global cache array that contains CacheSize pointers (zero-initialized). 677 // The cache is used to speed up recording the caller-callee pairs. 678 // The address of the caller is passed implicitly via caller PC. 679 // CacheSize is encoded in the name of the run-time function. 680 void SanitizerCoverageModule::InjectCoverageForIndirectCalls( 681 Function &F, ArrayRef<Instruction *> IndirCalls) { 682 if (IndirCalls.empty()) 683 return; 684 assert(Options.TracePC || Options.TracePCGuard || Options.Inline8bitCounters); 685 for (auto I : IndirCalls) { 686 IRBuilder<> IRB(I); 687 CallSite CS(I); 688 Value *Callee = CS.getCalledValue(); 689 if (isa<InlineAsm>(Callee)) 690 continue; 691 IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy)); 692 } 693 } 694 695 // For every switch statement we insert a call: 696 // __sanitizer_cov_trace_switch(CondValue, 697 // {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... }) 698 699 void SanitizerCoverageModule::InjectTraceForSwitch( 700 Function &, ArrayRef<Instruction *> SwitchTraceTargets) { 701 for (auto I : SwitchTraceTargets) { 702 if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) { 703 IRBuilder<> IRB(I); 704 SmallVector<Constant *, 16> Initializers; 705 Value *Cond = SI->getCondition(); 706 if (Cond->getType()->getScalarSizeInBits() > 707 Int64Ty->getScalarSizeInBits()) 708 continue; 709 Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases())); 710 Initializers.push_back( 711 ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits())); 712 if (Cond->getType()->getScalarSizeInBits() < 713 Int64Ty->getScalarSizeInBits()) 714 Cond = IRB.CreateIntCast(Cond, Int64Ty, false); 715 for (auto It : SI->cases()) { 716 Constant *C = It.getCaseValue(); 717 if (C->getType()->getScalarSizeInBits() < 718 Int64Ty->getScalarSizeInBits()) 719 C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty); 720 Initializers.push_back(C); 721 } 722 llvm::sort(Initializers.begin() + 2, Initializers.end(), 723 [](const Constant *A, const Constant *B) { 724 return cast<ConstantInt>(A)->getLimitedValue() < 725 cast<ConstantInt>(B)->getLimitedValue(); 726 }); 727 ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size()); 728 GlobalVariable *GV = new GlobalVariable( 729 *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage, 730 ConstantArray::get(ArrayOfInt64Ty, Initializers), 731 "__sancov_gen_cov_switch_values"); 732 IRB.CreateCall(SanCovTraceSwitchFunction, 733 {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)}); 734 } 735 } 736 } 737 738 void SanitizerCoverageModule::InjectTraceForDiv( 739 Function &, ArrayRef<BinaryOperator *> DivTraceTargets) { 740 for (auto BO : DivTraceTargets) { 741 IRBuilder<> IRB(BO); 742 Value *A1 = BO->getOperand(1); 743 if (isa<ConstantInt>(A1)) continue; 744 if (!A1->getType()->isIntegerTy()) 745 continue; 746 uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType()); 747 int CallbackIdx = TypeSize == 32 ? 0 : 748 TypeSize == 64 ? 1 : -1; 749 if (CallbackIdx < 0) continue; 750 auto Ty = Type::getIntNTy(*C, TypeSize); 751 IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx], 752 {IRB.CreateIntCast(A1, Ty, true)}); 753 } 754 } 755 756 void SanitizerCoverageModule::InjectTraceForGep( 757 Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) { 758 for (auto GEP : GepTraceTargets) { 759 IRBuilder<> IRB(GEP); 760 for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) 761 if (!isa<ConstantInt>(*I) && (*I)->getType()->isIntegerTy()) 762 IRB.CreateCall(SanCovTraceGepFunction, 763 {IRB.CreateIntCast(*I, IntptrTy, true)}); 764 } 765 } 766 767 void SanitizerCoverageModule::InjectTraceForCmp( 768 Function &, ArrayRef<Instruction *> CmpTraceTargets) { 769 for (auto I : CmpTraceTargets) { 770 if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) { 771 IRBuilder<> IRB(ICMP); 772 Value *A0 = ICMP->getOperand(0); 773 Value *A1 = ICMP->getOperand(1); 774 if (!A0->getType()->isIntegerTy()) 775 continue; 776 uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType()); 777 int CallbackIdx = TypeSize == 8 ? 0 : 778 TypeSize == 16 ? 1 : 779 TypeSize == 32 ? 2 : 780 TypeSize == 64 ? 3 : -1; 781 if (CallbackIdx < 0) continue; 782 // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1); 783 auto CallbackFunc = SanCovTraceCmpFunction[CallbackIdx]; 784 bool FirstIsConst = isa<ConstantInt>(A0); 785 bool SecondIsConst = isa<ConstantInt>(A1); 786 // If both are const, then we don't need such a comparison. 787 if (FirstIsConst && SecondIsConst) continue; 788 // If only one is const, then make it the first callback argument. 789 if (FirstIsConst || SecondIsConst) { 790 CallbackFunc = SanCovTraceConstCmpFunction[CallbackIdx]; 791 if (SecondIsConst) 792 std::swap(A0, A1); 793 } 794 795 auto Ty = Type::getIntNTy(*C, TypeSize); 796 IRB.CreateCall(CallbackFunc, {IRB.CreateIntCast(A0, Ty, true), 797 IRB.CreateIntCast(A1, Ty, true)}); 798 } 799 } 800 } 801 802 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB, 803 size_t Idx, 804 bool IsLeafFunc) { 805 BasicBlock::iterator IP = BB.getFirstInsertionPt(); 806 bool IsEntryBB = &BB == &F.getEntryBlock(); 807 DebugLoc EntryLoc; 808 if (IsEntryBB) { 809 if (auto SP = F.getSubprogram()) 810 EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP); 811 // Keep static allocas and llvm.localescape calls in the entry block. Even 812 // if we aren't splitting the block, it's nice for allocas to be before 813 // calls. 814 IP = PrepareToSplitEntryBlock(BB, IP); 815 } else { 816 EntryLoc = IP->getDebugLoc(); 817 } 818 819 IRBuilder<> IRB(&*IP); 820 IRB.SetCurrentDebugLocation(EntryLoc); 821 if (Options.TracePC) { 822 IRB.CreateCall(SanCovTracePC); // gets the PC using GET_CALLER_PC. 823 IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge. 824 } 825 if (Options.TracePCGuard) { 826 auto GuardPtr = IRB.CreateIntToPtr( 827 IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy), 828 ConstantInt::get(IntptrTy, Idx * 4)), 829 Int32PtrTy); 830 IRB.CreateCall(SanCovTracePCGuard, GuardPtr); 831 IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge. 832 } 833 if (Options.Inline8bitCounters) { 834 auto CounterPtr = IRB.CreateGEP( 835 Function8bitCounterArray->getValueType(), Function8bitCounterArray, 836 {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)}); 837 auto Load = IRB.CreateLoad(Int8Ty, CounterPtr); 838 auto Inc = IRB.CreateAdd(Load, ConstantInt::get(Int8Ty, 1)); 839 auto Store = IRB.CreateStore(Inc, CounterPtr); 840 SetNoSanitizeMetadata(Load); 841 SetNoSanitizeMetadata(Store); 842 } 843 if (Options.StackDepth && IsEntryBB && !IsLeafFunc) { 844 // Check stack depth. If it's the deepest so far, record it. 845 Function *GetFrameAddr = 846 Intrinsic::getDeclaration(F.getParent(), Intrinsic::frameaddress); 847 auto FrameAddrPtr = 848 IRB.CreateCall(GetFrameAddr, {Constant::getNullValue(Int32Ty)}); 849 auto FrameAddrInt = IRB.CreatePtrToInt(FrameAddrPtr, IntptrTy); 850 auto LowestStack = IRB.CreateLoad(IntptrTy, SanCovLowestStack); 851 auto IsStackLower = IRB.CreateICmpULT(FrameAddrInt, LowestStack); 852 auto ThenTerm = SplitBlockAndInsertIfThen(IsStackLower, &*IP, false); 853 IRBuilder<> ThenIRB(ThenTerm); 854 auto Store = ThenIRB.CreateStore(FrameAddrInt, SanCovLowestStack); 855 SetNoSanitizeMetadata(LowestStack); 856 SetNoSanitizeMetadata(Store); 857 } 858 } 859 860 std::string 861 SanitizerCoverageModule::getSectionName(const std::string &Section) const { 862 if (TargetTriple.isOSBinFormatCOFF()) { 863 if (Section == SanCovCountersSectionName) 864 return ".SCOV$CM"; 865 if (Section == SanCovPCsSectionName) 866 return ".SCOVP$M"; 867 return ".SCOV$GM"; // For SanCovGuardsSectionName. 868 } 869 if (TargetTriple.isOSBinFormatMachO()) 870 return "__DATA,__" + Section; 871 return "__" + Section; 872 } 873 874 std::string 875 SanitizerCoverageModule::getSectionStart(const std::string &Section) const { 876 if (TargetTriple.isOSBinFormatMachO()) 877 return "\1section$start$__DATA$__" + Section; 878 return "__start___" + Section; 879 } 880 881 std::string 882 SanitizerCoverageModule::getSectionEnd(const std::string &Section) const { 883 if (TargetTriple.isOSBinFormatMachO()) 884 return "\1section$end$__DATA$__" + Section; 885 return "__stop___" + Section; 886 } 887 888 889 char SanitizerCoverageModule::ID = 0; 890 INITIALIZE_PASS_BEGIN(SanitizerCoverageModule, "sancov", 891 "SanitizerCoverage: TODO." 892 "ModulePass", 893 false, false) 894 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 895 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) 896 INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov", 897 "SanitizerCoverage: TODO." 898 "ModulePass", 899 false, false) 900 ModulePass *llvm::createSanitizerCoverageModulePass( 901 const SanitizerCoverageOptions &Options) { 902 return new SanitizerCoverageModule(Options); 903 } 904