xref: /llvm-project/llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp (revision b75d002f159f0d1f4392bd9e849dfc55eee1bba7) 
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 done on LLVM IR level, works with Sanitizers.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/ArrayRef.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/Analysis/EHPersonalities.h"
17 #include "llvm/Analysis/PostDominators.h"
18 #include "llvm/IR/CFG.h"
19 #include "llvm/IR/CallSite.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/IRBuilder.h"
25 #include "llvm/IR/InlineAsm.h"
26 #include "llvm/IR/LLVMContext.h"
27 #include "llvm/IR/MDBuilder.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/IR/Type.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include "llvm/Transforms/Instrumentation.h"
34 #include "llvm/Transforms/Scalar.h"
35 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
36 #include "llvm/Transforms/Utils/ModuleUtils.h"
37 
38 using namespace llvm;
39 
40 #define DEBUG_TYPE "sancov"
41 
42 static const char *const SanCovTracePCIndirName =
43     "__sanitizer_cov_trace_pc_indir";
44 static const char *const SanCovTracePCName = "__sanitizer_cov_trace_pc";
45 static const char *const SanCovTraceCmp1 = "__sanitizer_cov_trace_cmp1";
46 static const char *const SanCovTraceCmp2 = "__sanitizer_cov_trace_cmp2";
47 static const char *const SanCovTraceCmp4 = "__sanitizer_cov_trace_cmp4";
48 static const char *const SanCovTraceCmp8 = "__sanitizer_cov_trace_cmp8";
49 static const char *const SanCovTraceDiv4 = "__sanitizer_cov_trace_div4";
50 static const char *const SanCovTraceDiv8 = "__sanitizer_cov_trace_div8";
51 static const char *const SanCovTraceGep = "__sanitizer_cov_trace_gep";
52 static const char *const SanCovTraceSwitchName = "__sanitizer_cov_trace_switch";
53 static const char *const SanCovModuleCtorName = "sancov.module_ctor";
54 static const uint64_t SanCtorAndDtorPriority = 2;
55 
56 static const char *const SanCovTracePCGuardName =
57     "__sanitizer_cov_trace_pc_guard";
58 static const char *const SanCovTracePCGuardInitName =
59     "__sanitizer_cov_trace_pc_guard_init";
60 static const char *const SanCov8bitCountersInitName =
61     "__sanitizer_cov_8bit_counters_init";
62 static const char *const SanCovPCsInitName = "__sanitizer_cov_pcs_init";
63 
64 static const char *const SanCovGuardsSectionName = "sancov_guards";
65 static const char *const SanCovCountersSectionName = "sancov_cntrs";
66 static const char *const SanCovPCsSectionName = "sancov_pcs";
67 
68 static cl::opt<int> ClCoverageLevel(
69     "sanitizer-coverage-level",
70     cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
71              "3: all blocks and critical edges"),
72     cl::Hidden, cl::init(0));
73 
74 static cl::opt<bool> ClTracePC("sanitizer-coverage-trace-pc",
75                                cl::desc("Experimental pc tracing"), cl::Hidden,
76                                cl::init(false));
77 
78 static cl::opt<bool> ClTracePCGuard("sanitizer-coverage-trace-pc-guard",
79                                     cl::desc("pc tracing with a guard"),
80                                     cl::Hidden, cl::init(false));
81 
82 // If true, we create a global variable that contains PCs of all instrumented
83 // BBs, put this global into a named section, and pass this section's bounds
84 // to __sanitizer_cov_pcs_init.
85 // This way the coverage instrumentation does not need to acquire the PCs
86 // at run-time. Works with trace-pc-guard and inline-8bit-counters.
87 static cl::opt<bool> ClCreatePCTable("sanitizer-coverage-create-pc-table",
88                                      cl::desc("create a static PC table"),
89                                      cl::Hidden, cl::init(false));
90 
91 static cl::opt<bool>
92     ClInline8bitCounters("sanitizer-coverage-inline-8bit-counters",
93                          cl::desc("increments 8-bit counter for every edge"),
94                          cl::Hidden, cl::init(false));
95 
96 static cl::opt<bool>
97     ClCMPTracing("sanitizer-coverage-trace-compares",
98                  cl::desc("Tracing of CMP and similar instructions"),
99                  cl::Hidden, cl::init(false));
100 
101 static cl::opt<bool> ClDIVTracing("sanitizer-coverage-trace-divs",
102                                   cl::desc("Tracing of DIV instructions"),
103                                   cl::Hidden, cl::init(false));
104 
105 static cl::opt<bool> ClGEPTracing("sanitizer-coverage-trace-geps",
106                                   cl::desc("Tracing of GEP instructions"),
107                                   cl::Hidden, cl::init(false));
108 
109 static cl::opt<bool>
110     ClPruneBlocks("sanitizer-coverage-prune-blocks",
111                   cl::desc("Reduce the number of instrumented blocks"),
112                   cl::Hidden, cl::init(true));
113 
114 namespace {
115 
116 SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) {
117   SanitizerCoverageOptions Res;
118   switch (LegacyCoverageLevel) {
119   case 0:
120     Res.CoverageType = SanitizerCoverageOptions::SCK_None;
121     break;
122   case 1:
123     Res.CoverageType = SanitizerCoverageOptions::SCK_Function;
124     break;
125   case 2:
126     Res.CoverageType = SanitizerCoverageOptions::SCK_BB;
127     break;
128   case 3:
129     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
130     break;
131   case 4:
132     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
133     Res.IndirectCalls = true;
134     break;
135   }
136   return Res;
137 }
138 
139 SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) {
140   // Sets CoverageType and IndirectCalls.
141   SanitizerCoverageOptions CLOpts = getOptions(ClCoverageLevel);
142   Options.CoverageType = std::max(Options.CoverageType, CLOpts.CoverageType);
143   Options.IndirectCalls |= CLOpts.IndirectCalls;
144   Options.TraceCmp |= ClCMPTracing;
145   Options.TraceDiv |= ClDIVTracing;
146   Options.TraceGep |= ClGEPTracing;
147   Options.TracePC |= ClTracePC;
148   Options.TracePCGuard |= ClTracePCGuard;
149   Options.Inline8bitCounters |= ClInline8bitCounters;
150   if (!Options.TracePCGuard && !Options.TracePC && !Options.Inline8bitCounters)
151     Options.TracePCGuard = true; // TracePCGuard is default.
152   Options.NoPrune |= !ClPruneBlocks;
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   StringRef 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 InjectTraceForDiv(Function &F,
178                          ArrayRef<BinaryOperator *> DivTraceTargets);
179   void InjectTraceForGep(Function &F,
180                          ArrayRef<GetElementPtrInst *> GepTraceTargets);
181   void InjectTraceForSwitch(Function &F,
182                             ArrayRef<Instruction *> SwitchTraceTargets);
183   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks);
184   GlobalVariable *CreateFunctionLocalArrayInSection(size_t NumElements,
185                                                     Function &F, Type *Ty,
186                                                     const char *Section);
187   void CreateFunctionLocalArrays(Function &F, ArrayRef<BasicBlock *> AllBlocks);
188   void CreatePCArray(Function &F, ArrayRef<BasicBlock *> AllBlocks);
189   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx);
190   Function *CreateInitCallsForSections(Module &M, const char *InitFunctionName,
191                                        Type *Ty, const char *Section);
192   std::pair<GlobalVariable *, GlobalVariable *>
193   CreateSecStartEnd(Module &M, const char *Section, Type *Ty);
194 
195   void SetNoSanitizeMetadata(Instruction *I) {
196     I->setMetadata(I->getModule()->getMDKindID("nosanitize"),
197                    MDNode::get(*C, None));
198   }
199 
200   std::string getSectionName(const std::string &Section) const;
201   std::string getSectionStart(const std::string &Section) const;
202   std::string getSectionEnd(const std::string &Section) const;
203   Function *SanCovTracePCIndir;
204   Function *SanCovTracePC, *SanCovTracePCGuard;
205   Function *SanCovTraceCmpFunction[4];
206   Function *SanCovTraceDivFunction[2];
207   Function *SanCovTraceGepFunction;
208   Function *SanCovTraceSwitchFunction;
209   InlineAsm *EmptyAsm;
210   Type *IntptrTy, *IntptrPtrTy, *Int64Ty, *Int64PtrTy, *Int32Ty, *Int32PtrTy,
211       *Int8Ty, *Int8PtrTy;
212   Module *CurModule;
213   Triple TargetTriple;
214   LLVMContext *C;
215   const DataLayout *DL;
216 
217   GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
218   GlobalVariable *Function8bitCounterArray;  // for inline-8bit-counters.
219   GlobalVariable *FunctionPCsArray;  // for create-pc-table.
220 
221   SanitizerCoverageOptions Options;
222 };
223 
224 } // namespace
225 
226 std::pair<GlobalVariable *, GlobalVariable *>
227 SanitizerCoverageModule::CreateSecStartEnd(Module &M, const char *Section,
228                                            Type *Ty) {
229   GlobalVariable *SecStart =
230       new GlobalVariable(M, Ty, false, GlobalVariable::ExternalLinkage, nullptr,
231                          getSectionStart(Section));
232   SecStart->setVisibility(GlobalValue::HiddenVisibility);
233   GlobalVariable *SecEnd =
234       new GlobalVariable(M, Ty, false, GlobalVariable::ExternalLinkage,
235                          nullptr, getSectionEnd(Section));
236   SecEnd->setVisibility(GlobalValue::HiddenVisibility);
237 
238   return std::make_pair(SecStart, SecEnd);
239 }
240 
241 
242 Function *SanitizerCoverageModule::CreateInitCallsForSections(
243     Module &M, const char *InitFunctionName, Type *Ty,
244     const char *Section) {
245   IRBuilder<> IRB(M.getContext());
246   auto SecStartEnd = CreateSecStartEnd(M, Section, Ty);
247   auto SecStart = SecStartEnd.first;
248   auto SecEnd = SecStartEnd.second;
249   Function *CtorFunc;
250   std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
251       M, SanCovModuleCtorName, InitFunctionName, {Ty, Ty},
252       {IRB.CreatePointerCast(SecStart, Ty), IRB.CreatePointerCast(SecEnd, Ty)});
253 
254   if (TargetTriple.supportsCOMDAT()) {
255     // Use comdat to dedup CtorFunc.
256     CtorFunc->setComdat(M.getOrInsertComdat(SanCovModuleCtorName));
257     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc);
258   } else {
259     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
260   }
261   return CtorFunc;
262 }
263 
264 bool SanitizerCoverageModule::runOnModule(Module &M) {
265   if (Options.CoverageType == SanitizerCoverageOptions::SCK_None)
266     return false;
267   C = &(M.getContext());
268   DL = &M.getDataLayout();
269   CurModule = &M;
270   TargetTriple = Triple(M.getTargetTriple());
271   FunctionGuardArray = nullptr;
272   Function8bitCounterArray = nullptr;
273   FunctionPCsArray = nullptr;
274   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
275   IntptrPtrTy = PointerType::getUnqual(IntptrTy);
276   Type *VoidTy = Type::getVoidTy(*C);
277   IRBuilder<> IRB(*C);
278   Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
279   Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
280   Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty());
281   Int64Ty = IRB.getInt64Ty();
282   Int32Ty = IRB.getInt32Ty();
283   Int8Ty = IRB.getInt8Ty();
284 
285   SanCovTracePCIndir = checkSanitizerInterfaceFunction(
286       M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy));
287   SanCovTraceCmpFunction[0] =
288       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
289           SanCovTraceCmp1, VoidTy, IRB.getInt8Ty(), IRB.getInt8Ty()));
290   SanCovTraceCmpFunction[1] = checkSanitizerInterfaceFunction(
291       M.getOrInsertFunction(SanCovTraceCmp2, VoidTy, IRB.getInt16Ty(),
292                             IRB.getInt16Ty()));
293   SanCovTraceCmpFunction[2] = checkSanitizerInterfaceFunction(
294       M.getOrInsertFunction(SanCovTraceCmp4, VoidTy, IRB.getInt32Ty(),
295                             IRB.getInt32Ty()));
296   SanCovTraceCmpFunction[3] =
297       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
298           SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty));
299 
300   SanCovTraceDivFunction[0] =
301       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
302           SanCovTraceDiv4, VoidTy, IRB.getInt32Ty()));
303   SanCovTraceDivFunction[1] =
304       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
305           SanCovTraceDiv8, VoidTy, Int64Ty));
306   SanCovTraceGepFunction =
307       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
308           SanCovTraceGep, VoidTy, IntptrTy));
309   SanCovTraceSwitchFunction =
310       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
311           SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy));
312   // Make sure smaller parameters are zero-extended to i64 as required by the
313   // x86_64 ABI.
314   if (TargetTriple.getArch() == Triple::x86_64) {
315     for (int i = 0; i < 3; i++) {
316       SanCovTraceCmpFunction[i]->addParamAttr(0, Attribute::ZExt);
317       SanCovTraceCmpFunction[i]->addParamAttr(1, Attribute::ZExt);
318     }
319     SanCovTraceDivFunction[0]->addParamAttr(0, Attribute::ZExt);
320   }
321 
322 
323   // We insert an empty inline asm after cov callbacks to avoid callback merge.
324   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
325                             StringRef(""), StringRef(""),
326                             /*hasSideEffects=*/true);
327 
328   SanCovTracePC = checkSanitizerInterfaceFunction(
329       M.getOrInsertFunction(SanCovTracePCName, VoidTy));
330   SanCovTracePCGuard = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
331       SanCovTracePCGuardName, VoidTy, Int32PtrTy));
332 
333   for (auto &F : M)
334     runOnFunction(F);
335 
336   Function *Ctor = nullptr;
337 
338   if (FunctionGuardArray)
339     Ctor = CreateInitCallsForSections(M, SanCovTracePCGuardInitName, Int32PtrTy,
340                                       SanCovGuardsSectionName);
341   if (Function8bitCounterArray)
342     Ctor = CreateInitCallsForSections(M, SanCov8bitCountersInitName, Int8PtrTy,
343                                       SanCovCountersSectionName);
344   if (Ctor && ClCreatePCTable) {
345     auto SecStartEnd = CreateSecStartEnd(M, SanCovPCsSectionName, Int8PtrTy);
346     Function *InitFunction = declareSanitizerInitFunction(
347         M, SanCovPCsInitName, {Int8PtrTy, Int8PtrTy});
348     IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
349     IRBCtor.CreateCall(InitFunction,
350                        {IRB.CreatePointerCast(SecStartEnd.first, Int8PtrTy),
351                         IRB.CreatePointerCast(SecStartEnd.second, Int8PtrTy)});
352   }
353   return true;
354 }
355 
356 // True if block has successors and it dominates all of them.
357 static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) {
358   if (succ_begin(BB) == succ_end(BB))
359     return false;
360 
361   for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) {
362     if (!DT->dominates(BB, SUCC))
363       return false;
364   }
365 
366   return true;
367 }
368 
369 // True if block has predecessors and it postdominates all of them.
370 static bool isFullPostDominator(const BasicBlock *BB,
371                                 const PostDominatorTree *PDT) {
372   if (pred_begin(BB) == pred_end(BB))
373     return false;
374 
375   for (const BasicBlock *PRED : make_range(pred_begin(BB), pred_end(BB))) {
376     if (!PDT->dominates(BB, PRED))
377       return false;
378   }
379 
380   return true;
381 }
382 
383 static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB,
384                                   const DominatorTree *DT,
385                                   const PostDominatorTree *PDT,
386                                   const SanitizerCoverageOptions &Options) {
387   // Don't insert coverage for unreachable blocks: we will never call
388   // __sanitizer_cov() for them, so counting them in
389   // NumberOfInstrumentedBlocks() might complicate calculation of code coverage
390   // percentage. Also, unreachable instructions frequently have no debug
391   // locations.
392   if (isa<UnreachableInst>(BB->getTerminator()))
393     return false;
394 
395   // Don't insert coverage into blocks without a valid insertion point
396   // (catchswitch blocks).
397   if (BB->getFirstInsertionPt() == BB->end())
398     return false;
399 
400   if (Options.NoPrune || &F.getEntryBlock() == BB)
401     return true;
402 
403   if (Options.CoverageType == SanitizerCoverageOptions::SCK_Function &&
404       &F.getEntryBlock() != BB)
405     return false;
406 
407   // Do not instrument full dominators, or full post-dominators with multiple
408   // predecessors.
409   return !isFullDominator(BB, DT)
410     && !(isFullPostDominator(BB, PDT) && !BB->getSinglePredecessor());
411 }
412 
413 bool SanitizerCoverageModule::runOnFunction(Function &F) {
414   if (F.empty())
415     return false;
416   if (F.getName().find(".module_ctor") != std::string::npos)
417     return false; // Should not instrument sanitizer init functions.
418   if (F.getName().startswith("__sanitizer_"))
419     return false;  // Don't instrument __sanitizer_* callbacks.
420   // Don't instrument MSVC CRT configuration helpers. They may run before normal
421   // initialization.
422   if (F.getName() == "__local_stdio_printf_options" ||
423       F.getName() == "__local_stdio_scanf_options")
424     return false;
425   // Don't instrument functions using SEH for now. Splitting basic blocks like
426   // we do for coverage breaks WinEHPrepare.
427   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
428   if (F.hasPersonalityFn() &&
429       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
430     return false;
431   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge)
432     SplitAllCriticalEdges(F);
433   SmallVector<Instruction *, 8> IndirCalls;
434   SmallVector<BasicBlock *, 16> BlocksToInstrument;
435   SmallVector<Instruction *, 8> CmpTraceTargets;
436   SmallVector<Instruction *, 8> SwitchTraceTargets;
437   SmallVector<BinaryOperator *, 8> DivTraceTargets;
438   SmallVector<GetElementPtrInst *, 8> GepTraceTargets;
439 
440   const DominatorTree *DT =
441       &getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
442   const PostDominatorTree *PDT =
443       &getAnalysis<PostDominatorTreeWrapperPass>(F).getPostDomTree();
444 
445   for (auto &BB : F) {
446     if (shouldInstrumentBlock(F, &BB, DT, PDT, Options))
447       BlocksToInstrument.push_back(&BB);
448     for (auto &Inst : BB) {
449       if (Options.IndirectCalls) {
450         CallSite CS(&Inst);
451         if (CS && !CS.getCalledFunction())
452           IndirCalls.push_back(&Inst);
453       }
454       if (Options.TraceCmp) {
455         if (isa<ICmpInst>(&Inst))
456           CmpTraceTargets.push_back(&Inst);
457         if (isa<SwitchInst>(&Inst))
458           SwitchTraceTargets.push_back(&Inst);
459       }
460       if (Options.TraceDiv)
461         if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst))
462           if (BO->getOpcode() == Instruction::SDiv ||
463               BO->getOpcode() == Instruction::UDiv)
464             DivTraceTargets.push_back(BO);
465       if (Options.TraceGep)
466         if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst))
467           GepTraceTargets.push_back(GEP);
468    }
469   }
470 
471   InjectCoverage(F, BlocksToInstrument);
472   InjectCoverageForIndirectCalls(F, IndirCalls);
473   InjectTraceForCmp(F, CmpTraceTargets);
474   InjectTraceForSwitch(F, SwitchTraceTargets);
475   InjectTraceForDiv(F, DivTraceTargets);
476   InjectTraceForGep(F, GepTraceTargets);
477   return true;
478 }
479 
480 GlobalVariable *SanitizerCoverageModule::CreateFunctionLocalArrayInSection(
481     size_t NumElements, Function &F, Type *Ty, const char *Section) {
482   ArrayType *ArrayTy = ArrayType::get(Ty, NumElements);
483   auto Array = new GlobalVariable(
484       *CurModule, ArrayTy, false, GlobalVariable::PrivateLinkage,
485       Constant::getNullValue(ArrayTy), "__sancov_gen_");
486   if (auto Comdat = F.getComdat())
487     Array->setComdat(Comdat);
488   Array->setSection(getSectionName(Section));
489   return Array;
490 }
491 
492 void SanitizerCoverageModule::CreatePCArray(Function &F,
493                                             ArrayRef<BasicBlock *> AllBlocks) {
494   size_t N = AllBlocks.size();
495   assert(N);
496   assert(&F.getEntryBlock() == AllBlocks[0]);
497   SmallVector<Constant *, 16> PCs;
498   IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
499   PCs.push_back((Constant *)IRB.CreatePointerCast(&F, Int8PtrTy));
500   for (size_t i = 1; i < N; i++)
501     PCs.push_back(BlockAddress::get(AllBlocks[i]));
502   FunctionPCsArray =
503       CreateFunctionLocalArrayInSection(N, F, Int8PtrTy, SanCovPCsSectionName);
504   FunctionPCsArray->setInitializer(
505       ConstantArray::get(ArrayType::get(Int8PtrTy, N), PCs));
506   FunctionPCsArray->setConstant(true);
507   FunctionPCsArray->setAlignment(DL->getPointerSize());
508 }
509 
510 void SanitizerCoverageModule::CreateFunctionLocalArrays(
511     Function &F, ArrayRef<BasicBlock *> AllBlocks) {
512   if (Options.TracePCGuard)
513     FunctionGuardArray = CreateFunctionLocalArrayInSection(
514         AllBlocks.size(), F, Int32Ty, SanCovGuardsSectionName);
515   if (Options.Inline8bitCounters)
516     Function8bitCounterArray = CreateFunctionLocalArrayInSection(
517         AllBlocks.size(), F, Int8Ty, SanCovCountersSectionName);
518   if (ClCreatePCTable)
519     CreatePCArray(F, AllBlocks);
520 }
521 
522 bool SanitizerCoverageModule::InjectCoverage(Function &F,
523                                              ArrayRef<BasicBlock *> AllBlocks) {
524   if (AllBlocks.empty()) return false;
525   CreateFunctionLocalArrays(F, AllBlocks);
526   for (size_t i = 0, N = AllBlocks.size(); i < N; i++)
527     InjectCoverageAtBlock(F, *AllBlocks[i], i);
528   return true;
529 }
530 
531 // On every indirect call we call a run-time function
532 // __sanitizer_cov_indir_call* with two parameters:
533 //   - callee address,
534 //   - global cache array that contains CacheSize pointers (zero-initialized).
535 //     The cache is used to speed up recording the caller-callee pairs.
536 // The address of the caller is passed implicitly via caller PC.
537 // CacheSize is encoded in the name of the run-time function.
538 void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
539     Function &F, ArrayRef<Instruction *> IndirCalls) {
540   if (IndirCalls.empty())
541     return;
542   assert(Options.TracePC || Options.TracePCGuard || Options.Inline8bitCounters);
543   for (auto I : IndirCalls) {
544     IRBuilder<> IRB(I);
545     CallSite CS(I);
546     Value *Callee = CS.getCalledValue();
547     if (isa<InlineAsm>(Callee))
548       continue;
549     IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy));
550   }
551 }
552 
553 // For every switch statement we insert a call:
554 // __sanitizer_cov_trace_switch(CondValue,
555 //      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
556 
557 void SanitizerCoverageModule::InjectTraceForSwitch(
558     Function &, ArrayRef<Instruction *> SwitchTraceTargets) {
559   for (auto I : SwitchTraceTargets) {
560     if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
561       IRBuilder<> IRB(I);
562       SmallVector<Constant *, 16> Initializers;
563       Value *Cond = SI->getCondition();
564       if (Cond->getType()->getScalarSizeInBits() >
565           Int64Ty->getScalarSizeInBits())
566         continue;
567       Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
568       Initializers.push_back(
569           ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
570       if (Cond->getType()->getScalarSizeInBits() <
571           Int64Ty->getScalarSizeInBits())
572         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
573       for (auto It : SI->cases()) {
574         Constant *C = It.getCaseValue();
575         if (C->getType()->getScalarSizeInBits() <
576             Int64Ty->getScalarSizeInBits())
577           C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
578         Initializers.push_back(C);
579       }
580       std::sort(Initializers.begin() + 2, Initializers.end(),
581                 [](const Constant *A, const Constant *B) {
582                   return cast<ConstantInt>(A)->getLimitedValue() <
583                          cast<ConstantInt>(B)->getLimitedValue();
584                 });
585       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
586       GlobalVariable *GV = new GlobalVariable(
587           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
588           ConstantArray::get(ArrayOfInt64Ty, Initializers),
589           "__sancov_gen_cov_switch_values");
590       IRB.CreateCall(SanCovTraceSwitchFunction,
591                      {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
592     }
593   }
594 }
595 
596 void SanitizerCoverageModule::InjectTraceForDiv(
597     Function &, ArrayRef<BinaryOperator *> DivTraceTargets) {
598   for (auto BO : DivTraceTargets) {
599     IRBuilder<> IRB(BO);
600     Value *A1 = BO->getOperand(1);
601     if (isa<ConstantInt>(A1)) continue;
602     if (!A1->getType()->isIntegerTy())
603       continue;
604     uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType());
605     int CallbackIdx = TypeSize == 32 ? 0 :
606         TypeSize == 64 ? 1 : -1;
607     if (CallbackIdx < 0) continue;
608     auto Ty = Type::getIntNTy(*C, TypeSize);
609     IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx],
610                    {IRB.CreateIntCast(A1, Ty, true)});
611   }
612 }
613 
614 void SanitizerCoverageModule::InjectTraceForGep(
615     Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) {
616   for (auto GEP : GepTraceTargets) {
617     IRBuilder<> IRB(GEP);
618     for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
619       if (!isa<ConstantInt>(*I) && (*I)->getType()->isIntegerTy())
620         IRB.CreateCall(SanCovTraceGepFunction,
621                        {IRB.CreateIntCast(*I, IntptrTy, true)});
622   }
623 }
624 
625 void SanitizerCoverageModule::InjectTraceForCmp(
626     Function &, ArrayRef<Instruction *> CmpTraceTargets) {
627   for (auto I : CmpTraceTargets) {
628     if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
629       IRBuilder<> IRB(ICMP);
630       Value *A0 = ICMP->getOperand(0);
631       Value *A1 = ICMP->getOperand(1);
632       if (!A0->getType()->isIntegerTy())
633         continue;
634       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
635       int CallbackIdx = TypeSize == 8 ? 0 :
636                         TypeSize == 16 ? 1 :
637                         TypeSize == 32 ? 2 :
638                         TypeSize == 64 ? 3 : -1;
639       if (CallbackIdx < 0) continue;
640       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
641       auto Ty = Type::getIntNTy(*C, TypeSize);
642       IRB.CreateCall(
643           SanCovTraceCmpFunction[CallbackIdx],
644           {IRB.CreateIntCast(A0, Ty, true), IRB.CreateIntCast(A1, Ty, true)});
645     }
646   }
647 }
648 
649 void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
650                                                     size_t Idx) {
651   BasicBlock::iterator IP = BB.getFirstInsertionPt();
652   bool IsEntryBB = &BB == &F.getEntryBlock();
653   DebugLoc EntryLoc;
654   if (IsEntryBB) {
655     if (auto SP = F.getSubprogram())
656       EntryLoc = DebugLoc::get(SP->getScopeLine(), 0, SP);
657     // Keep static allocas and llvm.localescape calls in the entry block.  Even
658     // if we aren't splitting the block, it's nice for allocas to be before
659     // calls.
660     IP = PrepareToSplitEntryBlock(BB, IP);
661   } else {
662     EntryLoc = IP->getDebugLoc();
663   }
664 
665   IRBuilder<> IRB(&*IP);
666   IRB.SetCurrentDebugLocation(EntryLoc);
667   if (Options.TracePC) {
668     IRB.CreateCall(SanCovTracePC); // gets the PC using GET_CALLER_PC.
669     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
670   }
671   if (Options.TracePCGuard) {
672     auto GuardPtr = IRB.CreateIntToPtr(
673         IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy),
674                       ConstantInt::get(IntptrTy, Idx * 4)),
675         Int32PtrTy);
676     IRB.CreateCall(SanCovTracePCGuard, GuardPtr);
677     IRB.CreateCall(EmptyAsm, {}); // Avoids callback merge.
678   }
679   if (Options.Inline8bitCounters) {
680     auto CounterPtr = IRB.CreateGEP(
681         Function8bitCounterArray,
682         {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)});
683     auto Load = IRB.CreateLoad(CounterPtr);
684     auto Inc = IRB.CreateAdd(Load, ConstantInt::get(Int8Ty, 1));
685     auto Store = IRB.CreateStore(Inc, CounterPtr);
686     SetNoSanitizeMetadata(Load);
687     SetNoSanitizeMetadata(Store);
688   }
689 }
690 
691 std::string
692 SanitizerCoverageModule::getSectionName(const std::string &Section) const {
693   if (TargetTriple.getObjectFormat() == Triple::COFF)
694     return ".SCOV$M";
695   if (TargetTriple.isOSBinFormatMachO())
696     return "__DATA,__" + Section;
697   return "__" + Section;
698 }
699 
700 std::string
701 SanitizerCoverageModule::getSectionStart(const std::string &Section) const {
702   if (TargetTriple.isOSBinFormatMachO())
703     return "\1section$start$__DATA$__" + Section;
704   return "__start___" + Section;
705 }
706 
707 std::string
708 SanitizerCoverageModule::getSectionEnd(const std::string &Section) const {
709   if (TargetTriple.isOSBinFormatMachO())
710     return "\1section$end$__DATA$__" + Section;
711   return "__stop___" + Section;
712 }
713 
714 
715 char SanitizerCoverageModule::ID = 0;
716 INITIALIZE_PASS_BEGIN(SanitizerCoverageModule, "sancov",
717                       "SanitizerCoverage: TODO."
718                       "ModulePass",
719                       false, false)
720 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
721 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
722 INITIALIZE_PASS_END(SanitizerCoverageModule, "sancov",
723                     "SanitizerCoverage: TODO."
724                     "ModulePass",
725                     false, false)
726 ModulePass *llvm::createSanitizerCoverageModulePass(
727     const SanitizerCoverageOptions &Options) {
728   return new SanitizerCoverageModule(Options);
729 }
730