xref: /llvm-project/llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp (revision 602f79275dcb5a65a0bd0e5917763b4f5b1eb904)
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 SanCovTraceCmpName = "__sanitizer_cov_trace_cmp";
71 static const char *const SanCovTraceSwitchName = "__sanitizer_cov_trace_switch";
72 static const char *const SanCovModuleCtorName = "sancov.module_ctor";
73 static const uint64_t SanCtorAndDtorPriority = 2;
74 
75 static cl::opt<int> ClCoverageLevel(
76     "sanitizer-coverage-level",
77     cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
78              "3: all blocks and critical edges, "
79              "4: above plus indirect calls"),
80     cl::Hidden, cl::init(0));
81 
82 static cl::opt<unsigned> ClCoverageBlockThreshold(
83     "sanitizer-coverage-block-threshold",
84     cl::desc("Use a callback with a guard check inside it if there are"
85              " more than this number of blocks."),
86     cl::Hidden, cl::init(500));
87 
88 static cl::opt<bool>
89     ClExperimentalTracing("sanitizer-coverage-experimental-tracing",
90                           cl::desc("Experimental basic-block tracing: insert "
91                                    "callbacks at every basic block"),
92                           cl::Hidden, cl::init(false));
93 
94 static cl::opt<bool> ClExperimentalTracePC("sanitizer-coverage-trace-pc",
95                                            cl::desc("Experimental pc tracing"),
96                                            cl::Hidden, cl::init(false));
97 
98 static cl::opt<bool>
99     ClExperimentalCMPTracing("sanitizer-coverage-experimental-trace-compares",
100                              cl::desc("Experimental tracing of CMP and similar "
101                                       "instructions"),
102                              cl::Hidden, cl::init(false));
103 
104 static cl::opt<bool> ClPruneBlocks(
105     "sanitizer-coverage-prune-blocks",
106     cl::desc("Reduce the number of instrumented blocks (experimental)"),
107     cl::Hidden, cl::init(false));
108 
109 // Experimental 8-bit counters used as an additional search heuristic during
110 // coverage-guided fuzzing.
111 // The counters are not thread-friendly:
112 //   - contention on these counters may cause significant slowdown;
113 //   - the counter updates are racy and the results may be inaccurate.
114 // They are also inaccurate due to 8-bit integer overflow.
115 static cl::opt<bool> ClUse8bitCounters("sanitizer-coverage-8bit-counters",
116                                        cl::desc("Experimental 8-bit counters"),
117                                        cl::Hidden, cl::init(false));
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.TraceBB |= ClExperimentalTracing;
150   Options.TraceCmp |= ClExperimentalCMPTracing;
151   Options.Use8bitCounters |= ClUse8bitCounters;
152   Options.TracePC |= ClExperimentalTracePC;
153   return Options;
154 }
155 
156 class SanitizerCoverageModule : public ModulePass {
157 public:
158   SanitizerCoverageModule(
159       const SanitizerCoverageOptions &Options = SanitizerCoverageOptions())
160       : ModulePass(ID), Options(OverrideFromCL(Options)) {
161     initializeSanitizerCoverageModulePass(*PassRegistry::getPassRegistry());
162   }
163   bool runOnModule(Module &M) override;
164   bool runOnFunction(Function &F);
165   static char ID; // Pass identification, replacement for typeid
166   const char *getPassName() const override { return "SanitizerCoverageModule"; }
167 
168   void getAnalysisUsage(AnalysisUsage &AU) const override {
169     AU.addRequired<DominatorTreeWrapperPass>();
170     AU.addRequired<PostDominatorTreeWrapperPass>();
171   }
172 
173 private:
174   void InjectCoverageForIndirectCalls(Function &F,
175                                       ArrayRef<Instruction *> IndirCalls);
176   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
177   void InjectTraceForSwitch(Function &F,
178                             ArrayRef<Instruction *> SwitchTraceTargets);
179   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks);
180   void SetNoSanitizeMetadata(Instruction *I);
181   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, bool UseCalls);
182   unsigned NumberOfInstrumentedBlocks() {
183     return SanCovFunction->getNumUses() +
184            SanCovWithCheckFunction->getNumUses() + SanCovTraceBB->getNumUses() +
185            SanCovTraceEnter->getNumUses();
186   }
187   Function *SanCovFunction;
188   Function *SanCovWithCheckFunction;
189   Function *SanCovIndirCallFunction, *SanCovTracePCIndir;
190   Function *SanCovTraceEnter, *SanCovTraceBB, *SanCovTracePC;
191   Function *SanCovTraceCmpFunction;
192   Function *SanCovTraceSwitchFunction;
193   InlineAsm *EmptyAsm;
194   Type *IntptrTy, *Int64Ty, *Int64PtrTy;
195   Module *CurModule;
196   LLVMContext *C;
197   const DataLayout *DL;
198 
199   GlobalVariable *GuardArray;
200   GlobalVariable *EightBitCounterArray;
201 
202   SanitizerCoverageOptions Options;
203 };
204 
205 } // namespace
206 
207 bool SanitizerCoverageModule::runOnModule(Module &M) {
208   if (Options.CoverageType == SanitizerCoverageOptions::SCK_None)
209     return false;
210   C = &(M.getContext());
211   DL = &M.getDataLayout();
212   CurModule = &M;
213   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
214   Type *VoidTy = Type::getVoidTy(*C);
215   IRBuilder<> IRB(*C);
216   Type *Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty());
217   Type *Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
218   Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
219   Int64Ty = IRB.getInt64Ty();
220 
221   SanCovFunction = checkSanitizerInterfaceFunction(
222       M.getOrInsertFunction(SanCovName, VoidTy, Int32PtrTy, nullptr));
223   SanCovWithCheckFunction = checkSanitizerInterfaceFunction(
224       M.getOrInsertFunction(SanCovWithCheckName, VoidTy, Int32PtrTy, nullptr));
225   SanCovTracePCIndir = checkSanitizerInterfaceFunction(
226       M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy, nullptr));
227   SanCovIndirCallFunction =
228       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
229           SanCovIndirCallName, VoidTy, IntptrTy, IntptrTy, nullptr));
230   SanCovTraceCmpFunction =
231       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
232           SanCovTraceCmpName, VoidTy, Int64Ty, Int64Ty, Int64Ty, nullptr));
233   SanCovTraceSwitchFunction =
234       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
235           SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy, nullptr));
236 
237   // We insert an empty inline asm after cov callbacks to avoid callback merge.
238   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
239                             StringRef(""), StringRef(""),
240                             /*hasSideEffects=*/true);
241 
242   SanCovTracePC = checkSanitizerInterfaceFunction(
243       M.getOrInsertFunction(SanCovTracePCName, VoidTy, nullptr));
244   SanCovTraceEnter = checkSanitizerInterfaceFunction(
245       M.getOrInsertFunction(SanCovTraceEnterName, VoidTy, Int32PtrTy, nullptr));
246   SanCovTraceBB = checkSanitizerInterfaceFunction(
247       M.getOrInsertFunction(SanCovTraceBBName, VoidTy, Int32PtrTy, nullptr));
248 
249   // At this point we create a dummy array of guards because we don't
250   // know how many elements we will need.
251   Type *Int32Ty = IRB.getInt32Ty();
252   Type *Int8Ty = IRB.getInt8Ty();
253 
254   GuardArray =
255       new GlobalVariable(M, Int32Ty, false, GlobalValue::ExternalLinkage,
256                          nullptr, "__sancov_gen_cov_tmp");
257   if (Options.Use8bitCounters)
258     EightBitCounterArray =
259         new GlobalVariable(M, Int8Ty, false, GlobalVariable::ExternalLinkage,
260                            nullptr, "__sancov_gen_cov_tmp");
261 
262   for (auto &F : M)
263     runOnFunction(F);
264 
265   auto N = NumberOfInstrumentedBlocks();
266 
267   // Now we know how many elements we need. Create an array of guards
268   // with one extra element at the beginning for the size.
269   Type *Int32ArrayNTy = ArrayType::get(Int32Ty, N + 1);
270   GlobalVariable *RealGuardArray = new GlobalVariable(
271       M, Int32ArrayNTy, false, GlobalValue::PrivateLinkage,
272       Constant::getNullValue(Int32ArrayNTy), "__sancov_gen_cov");
273 
274   // Replace the dummy array with the real one.
275   GuardArray->replaceAllUsesWith(
276       IRB.CreatePointerCast(RealGuardArray, Int32PtrTy));
277   GuardArray->eraseFromParent();
278 
279   GlobalVariable *RealEightBitCounterArray;
280   if (Options.Use8bitCounters) {
281     // Make sure the array is 16-aligned.
282     static const int CounterAlignment = 16;
283     Type *Int8ArrayNTy = ArrayType::get(Int8Ty, alignTo(N, CounterAlignment));
284     RealEightBitCounterArray = new GlobalVariable(
285         M, Int8ArrayNTy, false, GlobalValue::PrivateLinkage,
286         Constant::getNullValue(Int8ArrayNTy), "__sancov_gen_cov_counter");
287     RealEightBitCounterArray->setAlignment(CounterAlignment);
288     EightBitCounterArray->replaceAllUsesWith(
289         IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy));
290     EightBitCounterArray->eraseFromParent();
291   }
292 
293   // Create variable for module (compilation unit) name
294   Constant *ModNameStrConst =
295       ConstantDataArray::getString(M.getContext(), M.getName(), true);
296   GlobalVariable *ModuleName =
297       new GlobalVariable(M, ModNameStrConst->getType(), true,
298                          GlobalValue::PrivateLinkage, ModNameStrConst);
299 
300   if (!Options.TracePC) {
301     Function *CtorFunc;
302     std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
303         M, SanCovModuleCtorName, SanCovModuleInitName,
304         {Int32PtrTy, IntptrTy, Int8PtrTy, Int8PtrTy},
305         {IRB.CreatePointerCast(RealGuardArray, Int32PtrTy),
306          ConstantInt::get(IntptrTy, N),
307          Options.Use8bitCounters
308              ? IRB.CreatePointerCast(RealEightBitCounterArray, Int8PtrTy)
309              : Constant::getNullValue(Int8PtrTy),
310          IRB.CreatePointerCast(ModuleName, Int8PtrTy)});
311 
312     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
313   }
314 
315   return true;
316 }
317 
318 static bool shouldInstrumentBlock(const BasicBlock *BB, const DominatorTree *DT,
319                                   const PostDominatorTree *PDT) {
320   if (!ClPruneBlocks)
321     return true;
322 
323   // Check if BB dominates all its successors.
324   bool DominatesAll = succ_begin(BB) != succ_end(BB);
325   for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) {
326     DominatesAll &= DT->dominates(BB, SUCC);
327   }
328 
329   // Check if BB pre-dominates all predecessors.
330   bool PreDominatesAll = pred_begin(BB) != pred_end(BB);
331   for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) {
332     PreDominatesAll &= PDT->dominates(BB, PRED);
333   }
334 
335   return !(DominatesAll || PreDominatesAll);
336 }
337 
338 bool SanitizerCoverageModule::runOnFunction(Function &F) {
339   if (F.empty())
340     return false;
341   if (F.getName().find(".module_ctor") != std::string::npos)
342     return false; // Should not instrument sanitizer init functions.
343   // Don't instrument functions using SEH for now. Splitting basic blocks like
344   // we do for coverage breaks WinEHPrepare.
345   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
346   if (F.hasPersonalityFn() &&
347       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
348     return false;
349   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge)
350     SplitAllCriticalEdges(F);
351   SmallVector<Instruction *, 8> IndirCalls;
352   SmallVector<BasicBlock *, 16> BlocksToInstrument;
353   SmallVector<Instruction *, 8> CmpTraceTargets;
354   SmallVector<Instruction *, 8> SwitchTraceTargets;
355 
356   const DominatorTree *DT =
357       &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
358   const PostDominatorTree *PDT =
359       &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree();
360 
361   for (auto &BB : F) {
362     if (shouldInstrumentBlock(&BB, DT, PDT))
363       BlocksToInstrument.push_back(&BB);
364     for (auto &Inst : BB) {
365       if (Options.IndirectCalls) {
366         CallSite CS(&Inst);
367         if (CS && !CS.getCalledFunction())
368           IndirCalls.push_back(&Inst);
369       }
370       if (Options.TraceCmp) {
371         if (isa<ICmpInst>(&Inst))
372           CmpTraceTargets.push_back(&Inst);
373         if (isa<SwitchInst>(&Inst))
374           SwitchTraceTargets.push_back(&Inst);
375       }
376     }
377   }
378 
379   InjectCoverage(F, BlocksToInstrument);
380   InjectCoverageForIndirectCalls(F, IndirCalls);
381   InjectTraceForCmp(F, CmpTraceTargets);
382   InjectTraceForSwitch(F, SwitchTraceTargets);
383   return true;
384 }
385 
386 bool SanitizerCoverageModule::InjectCoverage(Function &F,
387                                              ArrayRef<BasicBlock *> AllBlocks) {
388   switch (Options.CoverageType) {
389   case SanitizerCoverageOptions::SCK_None:
390     return false;
391   case SanitizerCoverageOptions::SCK_Function:
392     InjectCoverageAtBlock(F, F.getEntryBlock(), false);
393     return true;
394   default: {
395     bool UseCalls = ClCoverageBlockThreshold < AllBlocks.size();
396     for (auto BB : AllBlocks)
397       InjectCoverageAtBlock(F, *BB, UseCalls);
398     return true;
399   }
400   }
401 }
402 
403 // On every indirect call we call a run-time function
404 // __sanitizer_cov_indir_call* with two parameters:
405 //   - callee address,
406 //   - global cache array that contains CacheSize pointers (zero-initialized).
407 //     The cache is used to speed up recording the caller-callee pairs.
408 // The address of the caller is passed implicitly via caller PC.
409 // CacheSize is encoded in the name of the run-time function.
410 void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
411     Function &F, ArrayRef<Instruction *> IndirCalls) {
412   if (IndirCalls.empty())
413     return;
414   const int CacheSize = 16;
415   const int CacheAlignment = 64; // Align for better performance.
416   Type *Ty = ArrayType::get(IntptrTy, CacheSize);
417   for (auto I : IndirCalls) {
418     IRBuilder<> IRB(I);
419     CallSite CS(I);
420     Value *Callee = CS.getCalledValue();
421     if (isa<InlineAsm>(Callee))
422       continue;
423     GlobalVariable *CalleeCache = new GlobalVariable(
424         *F.getParent(), Ty, false, GlobalValue::PrivateLinkage,
425         Constant::getNullValue(Ty), "__sancov_gen_callee_cache");
426     CalleeCache->setAlignment(CacheAlignment);
427     if (Options.TracePC)
428       IRB.CreateCall(SanCovTracePCIndir,
429                      IRB.CreatePointerCast(Callee, IntptrTy));
430     else
431       IRB.CreateCall(SanCovIndirCallFunction,
432                      {IRB.CreatePointerCast(Callee, IntptrTy),
433                       IRB.CreatePointerCast(CalleeCache, IntptrTy)});
434   }
435 }
436 
437 // For every switch statement we insert a call:
438 // __sanitizer_cov_trace_switch(CondValue,
439 //      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
440 
441 void SanitizerCoverageModule::InjectTraceForSwitch(
442     Function &, ArrayRef<Instruction *> SwitchTraceTargets) {
443   for (auto I : SwitchTraceTargets) {
444     if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
445       IRBuilder<> IRB(I);
446       SmallVector<Constant *, 16> Initializers;
447       Value *Cond = SI->getCondition();
448       if (Cond->getType()->getScalarSizeInBits() >
449           Int64Ty->getScalarSizeInBits())
450         continue;
451       Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
452       Initializers.push_back(
453           ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
454       if (Cond->getType()->getScalarSizeInBits() <
455           Int64Ty->getScalarSizeInBits())
456         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
457       for (auto It : SI->cases()) {
458         Constant *C = It.getCaseValue();
459         if (C->getType()->getScalarSizeInBits() <
460             Int64Ty->getScalarSizeInBits())
461           C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
462         Initializers.push_back(C);
463       }
464       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
465       GlobalVariable *GV = new GlobalVariable(
466           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
467           ConstantArray::get(ArrayOfInt64Ty, Initializers),
468           "__sancov_gen_cov_switch_values");
469       IRB.CreateCall(SanCovTraceSwitchFunction,
470                      {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
471     }
472   }
473 }
474 
475 void SanitizerCoverageModule::InjectTraceForCmp(
476     Function &, ArrayRef<Instruction *> CmpTraceTargets) {
477   for (auto I : CmpTraceTargets) {
478     if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
479       IRBuilder<> IRB(ICMP);
480       Value *A0 = ICMP->getOperand(0);
481       Value *A1 = ICMP->getOperand(1);
482       if (!A0->getType()->isIntegerTy())
483         continue;
484       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
485       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
486       IRB.CreateCall(
487           SanCovTraceCmpFunction,
488           {ConstantInt::get(Int64Ty, (TypeSize << 32) | ICMP->getPredicate()),
489            IRB.CreateIntCast(A0, Int64Ty, true),
490            IRB.CreateIntCast(A1, Int64Ty, true)});
491     }
492   }
493 }
494 
495 void SanitizerCoverageModule::SetNoSanitizeMetadata(Instruction *I) {
496   I->setMetadata(I->getModule()->getMDKindID("nosanitize"),
497                  MDNode::get(*C, None));
498 }
499 
500 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
501                                                     bool UseCalls) {
502   // Don't insert coverage for unreachable blocks: we will never call
503   // __sanitizer_cov() for them, so counting them in
504   // NumberOfInstrumentedBlocks() might complicate calculation of code coverage
505   // percentage. Also, unreachable instructions frequently have no debug
506   // locations.
507   if (isa<UnreachableInst>(BB.getTerminator()))
508     return;
509   BasicBlock::iterator IP = BB.getFirstInsertionPt();
510 
511   bool IsEntryBB = &BB == &F.getEntryBlock();
512   DebugLoc EntryLoc;
513   if (IsEntryBB) {
514     if (auto SP = F.getSubprogram())
515       EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP);
516     // Keep static allocas and llvm.localescape calls in the entry block.  Even
517     // if we aren't splitting the block, it's nice for allocas to be before
518     // calls.
519     IP = PrepareToSplitEntryBlock(BB, IP);
520   } else {
521     EntryLoc = IP->getDebugLoc();
522   }
523 
524   IRBuilder<> IRB(&*IP);
525   IRB.SetCurrentDebugLocation(EntryLoc);
526   Value *GuardP = IRB.CreateAdd(
527       IRB.CreatePointerCast(GuardArray, IntptrTy),
528       ConstantInt::get(IntptrTy, (1 + NumberOfInstrumentedBlocks()) * 4));
529   Type *Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
530   GuardP = IRB.CreateIntToPtr(GuardP, Int32PtrTy);
531   if (Options.TracePC) {
532     IRB.CreateCall(SanCovTracePC);
533   } else if (Options.TraceBB) {
534     IRB.CreateCall(IsEntryBB ? SanCovTraceEnter : SanCovTraceBB, GuardP);
535   } else if (UseCalls) {
536     IRB.CreateCall(SanCovWithCheckFunction, GuardP);
537   } else {
538     LoadInst *Load = IRB.CreateLoad(GuardP);
539     Load->setAtomic(Monotonic);
540     Load->setAlignment(4);
541     SetNoSanitizeMetadata(Load);
542     Value *Cmp =
543         IRB.CreateICmpSGE(Constant::getNullValue(Load->getType()), Load);
544     Instruction *Ins = SplitBlockAndInsertIfThen(
545         Cmp, &*IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
546     IRB.SetInsertPoint(Ins);
547     IRB.SetCurrentDebugLocation(EntryLoc);
548     // __sanitizer_cov gets the PC of the instruction using GET_CALLER_PC.
549     IRB.CreateCall(SanCovFunction, GuardP);
550     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
551   }
552 
553   if (Options.Use8bitCounters) {
554     IRB.SetInsertPoint(&*IP);
555     Value *P = IRB.CreateAdd(
556         IRB.CreatePointerCast(EightBitCounterArray, IntptrTy),
557         ConstantInt::get(IntptrTy, NumberOfInstrumentedBlocks() - 1));
558     P = IRB.CreateIntToPtr(P, IRB.getInt8PtrTy());
559     LoadInst *LI = IRB.CreateLoad(P);
560     Value *Inc = IRB.CreateAdd(LI, ConstantInt::get(IRB.getInt8Ty(), 1));
561     StoreInst *SI = IRB.CreateStore(Inc, P);
562     SetNoSanitizeMetadata(LI);
563     SetNoSanitizeMetadata(SI);
564   }
565 }
566 
567 char SanitizerCoverageModule::ID = 0;
568 INITIALIZE_PASS_BEGIN(SanitizerCoverageModule, "sancov",
569                       "SanitizerCoverage: TODO."
570                       "ModulePass",
571                       false, false)
572 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
573 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
574 INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov",
575                     "SanitizerCoverage: TODO."
576                     "ModulePass",
577                     false, false)
578 ModulePass *llvm::createSanitizerCoverageModulePass(
579     const SanitizerCoverageOptions &Options) {
580   return new SanitizerCoverageModule(Options);
581 }
582