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