1 //===-- SanitizerCoverage.cpp - coverage instrumentation for sanitizers ---===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Coverage instrumentation done on LLVM IR level, works with Sanitizers.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/Transforms/Instrumentation/SanitizerCoverage.h"
14 #include "llvm/ADT/ArrayRef.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/Analysis/GlobalsModRef.h"
17 #include "llvm/Analysis/PostDominators.h"
18 #include "llvm/IR/Constant.h"
19 #include "llvm/IR/DataLayout.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/IR/EHPersonalities.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/GlobalVariable.h"
24 #include "llvm/IR/IRBuilder.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/Intrinsics.h"
27 #include "llvm/IR/LLVMContext.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/IR/Type.h"
30 #include "llvm/Support/CommandLine.h"
31 #include "llvm/Support/SpecialCaseList.h"
32 #include "llvm/Support/VirtualFileSystem.h"
33 #include "llvm/TargetParser/Triple.h"
34 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
35 #include "llvm/Transforms/Utils/ModuleUtils.h"
36 
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "sancov"
40 
41 const char SanCovTracePCIndirName[] = "__sanitizer_cov_trace_pc_indir";
42 const char SanCovTracePCName[] = "__sanitizer_cov_trace_pc";
43 const char SanCovTraceCmp1[] = "__sanitizer_cov_trace_cmp1";
44 const char SanCovTraceCmp2[] = "__sanitizer_cov_trace_cmp2";
45 const char SanCovTraceCmp4[] = "__sanitizer_cov_trace_cmp4";
46 const char SanCovTraceCmp8[] = "__sanitizer_cov_trace_cmp8";
47 const char SanCovTraceConstCmp1[] = "__sanitizer_cov_trace_const_cmp1";
48 const char SanCovTraceConstCmp2[] = "__sanitizer_cov_trace_const_cmp2";
49 const char SanCovTraceConstCmp4[] = "__sanitizer_cov_trace_const_cmp4";
50 const char SanCovTraceConstCmp8[] = "__sanitizer_cov_trace_const_cmp8";
51 const char SanCovLoad1[] = "__sanitizer_cov_load1";
52 const char SanCovLoad2[] = "__sanitizer_cov_load2";
53 const char SanCovLoad4[] = "__sanitizer_cov_load4";
54 const char SanCovLoad8[] = "__sanitizer_cov_load8";
55 const char SanCovLoad16[] = "__sanitizer_cov_load16";
56 const char SanCovStore1[] = "__sanitizer_cov_store1";
57 const char SanCovStore2[] = "__sanitizer_cov_store2";
58 const char SanCovStore4[] = "__sanitizer_cov_store4";
59 const char SanCovStore8[] = "__sanitizer_cov_store8";
60 const char SanCovStore16[] = "__sanitizer_cov_store16";
61 const char SanCovTraceDiv4[] = "__sanitizer_cov_trace_div4";
62 const char SanCovTraceDiv8[] = "__sanitizer_cov_trace_div8";
63 const char SanCovTraceGep[] = "__sanitizer_cov_trace_gep";
64 const char SanCovTraceSwitchName[] = "__sanitizer_cov_trace_switch";
65 const char SanCovModuleCtorTracePcGuardName[] =
66     "sancov.module_ctor_trace_pc_guard";
67 const char SanCovModuleCtor8bitCountersName[] =
68     "sancov.module_ctor_8bit_counters";
69 const char SanCovModuleCtorBoolFlagName[] = "sancov.module_ctor_bool_flag";
70 static const uint64_t SanCtorAndDtorPriority = 2;
71 
72 const char SanCovTracePCGuardName[] = "__sanitizer_cov_trace_pc_guard";
73 const char SanCovTracePCGuardInitName[] = "__sanitizer_cov_trace_pc_guard_init";
74 const char SanCov8bitCountersInitName[] = "__sanitizer_cov_8bit_counters_init";
75 const char SanCovBoolFlagInitName[] = "__sanitizer_cov_bool_flag_init";
76 const char SanCovPCsInitName[] = "__sanitizer_cov_pcs_init";
77 const char SanCovCFsInitName[] = "__sanitizer_cov_cfs_init";
78 
79 const char SanCovGuardsSectionName[] = "sancov_guards";
80 const char SanCovCountersSectionName[] = "sancov_cntrs";
81 const char SanCovBoolFlagSectionName[] = "sancov_bools";
82 const char SanCovPCsSectionName[] = "sancov_pcs";
83 const char SanCovCFsSectionName[] = "sancov_cfs";
84 
85 const char SanCovLowestStackName[] = "__sancov_lowest_stack";
86 
87 static cl::opt<int> ClCoverageLevel(
88     "sanitizer-coverage-level",
89     cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
90              "3: all blocks and critical edges"),
91     cl::Hidden, cl::init(0));
92 
93 static cl::opt<bool> ClTracePC("sanitizer-coverage-trace-pc",
94                                cl::desc("Experimental pc tracing"), cl::Hidden,
95                                cl::init(false));
96 
97 static cl::opt<bool> ClTracePCGuard("sanitizer-coverage-trace-pc-guard",
98                                     cl::desc("pc tracing with a guard"),
99                                     cl::Hidden, cl::init(false));
100 
101 // If true, we create a global variable that contains PCs of all instrumented
102 // BBs, put this global into a named section, and pass this section's bounds
103 // to __sanitizer_cov_pcs_init.
104 // This way the coverage instrumentation does not need to acquire the PCs
105 // at run-time. Works with trace-pc-guard, inline-8bit-counters, and
106 // inline-bool-flag.
107 static cl::opt<bool> ClCreatePCTable("sanitizer-coverage-pc-table",
108                                      cl::desc("create a static PC table"),
109                                      cl::Hidden, cl::init(false));
110 
111 static cl::opt<bool>
112     ClInline8bitCounters("sanitizer-coverage-inline-8bit-counters",
113                          cl::desc("increments 8-bit counter for every edge"),
114                          cl::Hidden, cl::init(false));
115 
116 static cl::opt<bool>
117     ClInlineBoolFlag("sanitizer-coverage-inline-bool-flag",
118                      cl::desc("sets a boolean flag for every edge"), cl::Hidden,
119                      cl::init(false));
120 
121 static cl::opt<bool>
122     ClCMPTracing("sanitizer-coverage-trace-compares",
123                  cl::desc("Tracing of CMP and similar instructions"),
124                  cl::Hidden, cl::init(false));
125 
126 static cl::opt<bool> ClDIVTracing("sanitizer-coverage-trace-divs",
127                                   cl::desc("Tracing of DIV instructions"),
128                                   cl::Hidden, cl::init(false));
129 
130 static cl::opt<bool> ClLoadTracing("sanitizer-coverage-trace-loads",
131                                    cl::desc("Tracing of load instructions"),
132                                    cl::Hidden, cl::init(false));
133 
134 static cl::opt<bool> ClStoreTracing("sanitizer-coverage-trace-stores",
135                                     cl::desc("Tracing of store instructions"),
136                                     cl::Hidden, cl::init(false));
137 
138 static cl::opt<bool> ClGEPTracing("sanitizer-coverage-trace-geps",
139                                   cl::desc("Tracing of GEP instructions"),
140                                   cl::Hidden, cl::init(false));
141 
142 static cl::opt<bool>
143     ClPruneBlocks("sanitizer-coverage-prune-blocks",
144                   cl::desc("Reduce the number of instrumented blocks"),
145                   cl::Hidden, cl::init(true));
146 
147 static cl::opt<bool> ClStackDepth("sanitizer-coverage-stack-depth",
148                                   cl::desc("max stack depth tracing"),
149                                   cl::Hidden, cl::init(false));
150 
151 static cl::opt<bool>
152     ClCollectCF("sanitizer-coverage-control-flow",
153                 cl::desc("collect control flow for each function"), cl::Hidden,
154                 cl::init(false));
155 
156 namespace {
157 
158 SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) {
159   SanitizerCoverageOptions Res;
160   switch (LegacyCoverageLevel) {
161   case 0:
162     Res.CoverageType = SanitizerCoverageOptions::SCK_None;
163     break;
164   case 1:
165     Res.CoverageType = SanitizerCoverageOptions::SCK_Function;
166     break;
167   case 2:
168     Res.CoverageType = SanitizerCoverageOptions::SCK_BB;
169     break;
170   case 3:
171     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
172     break;
173   case 4:
174     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
175     Res.IndirectCalls = true;
176     break;
177   }
178   return Res;
179 }
180 
181 SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) {
182   // Sets CoverageType and IndirectCalls.
183   SanitizerCoverageOptions CLOpts = getOptions(ClCoverageLevel);
184   Options.CoverageType = std::max(Options.CoverageType, CLOpts.CoverageType);
185   Options.IndirectCalls |= CLOpts.IndirectCalls;
186   Options.TraceCmp |= ClCMPTracing;
187   Options.TraceDiv |= ClDIVTracing;
188   Options.TraceGep |= ClGEPTracing;
189   Options.TracePC |= ClTracePC;
190   Options.TracePCGuard |= ClTracePCGuard;
191   Options.Inline8bitCounters |= ClInline8bitCounters;
192   Options.InlineBoolFlag |= ClInlineBoolFlag;
193   Options.PCTable |= ClCreatePCTable;
194   Options.NoPrune |= !ClPruneBlocks;
195   Options.StackDepth |= ClStackDepth;
196   Options.TraceLoads |= ClLoadTracing;
197   Options.TraceStores |= ClStoreTracing;
198   if (!Options.TracePCGuard && !Options.TracePC &&
199       !Options.Inline8bitCounters && !Options.StackDepth &&
200       !Options.InlineBoolFlag && !Options.TraceLoads && !Options.TraceStores)
201     Options.TracePCGuard = true; // TracePCGuard is default.
202   Options.CollectControlFlow |= ClCollectCF;
203   return Options;
204 }
205 
206 using DomTreeCallback = function_ref<const DominatorTree *(Function &F)>;
207 using PostDomTreeCallback =
208     function_ref<const PostDominatorTree *(Function &F)>;
209 
210 class ModuleSanitizerCoverage {
211 public:
212   ModuleSanitizerCoverage(
213       const SanitizerCoverageOptions &Options = SanitizerCoverageOptions(),
214       const SpecialCaseList *Allowlist = nullptr,
215       const SpecialCaseList *Blocklist = nullptr)
216       : Options(OverrideFromCL(Options)), Allowlist(Allowlist),
217         Blocklist(Blocklist) {}
218   bool instrumentModule(Module &M, DomTreeCallback DTCallback,
219                         PostDomTreeCallback PDTCallback);
220 
221 private:
222   void createFunctionControlFlow(Function &F);
223   void instrumentFunction(Function &F, DomTreeCallback DTCallback,
224                           PostDomTreeCallback PDTCallback);
225   void InjectCoverageForIndirectCalls(Function &F,
226                                       ArrayRef<Instruction *> IndirCalls);
227   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
228   void InjectTraceForDiv(Function &F,
229                          ArrayRef<BinaryOperator *> DivTraceTargets);
230   void InjectTraceForGep(Function &F,
231                          ArrayRef<GetElementPtrInst *> GepTraceTargets);
232   void InjectTraceForLoadsAndStores(Function &F, ArrayRef<LoadInst *> Loads,
233                                     ArrayRef<StoreInst *> Stores);
234   void InjectTraceForSwitch(Function &F,
235                             ArrayRef<Instruction *> SwitchTraceTargets);
236   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks,
237                       bool IsLeafFunc = true);
238   GlobalVariable *CreateFunctionLocalArrayInSection(size_t NumElements,
239                                                     Function &F, Type *Ty,
240                                                     const char *Section);
241   GlobalVariable *CreatePCArray(Function &F, ArrayRef<BasicBlock *> AllBlocks);
242   void CreateFunctionLocalArrays(Function &F, ArrayRef<BasicBlock *> AllBlocks);
243   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx,
244                              bool IsLeafFunc = true);
245   Function *CreateInitCallsForSections(Module &M, const char *CtorName,
246                                        const char *InitFunctionName, Type *Ty,
247                                        const char *Section);
248   std::pair<Value *, Value *> CreateSecStartEnd(Module &M, const char *Section,
249                                                 Type *Ty);
250 
251   std::string getSectionName(const std::string &Section) const;
252   std::string getSectionStart(const std::string &Section) const;
253   std::string getSectionEnd(const std::string &Section) const;
254   FunctionCallee SanCovTracePCIndir;
255   FunctionCallee SanCovTracePC, SanCovTracePCGuard;
256   std::array<FunctionCallee, 4> SanCovTraceCmpFunction;
257   std::array<FunctionCallee, 4> SanCovTraceConstCmpFunction;
258   std::array<FunctionCallee, 5> SanCovLoadFunction;
259   std::array<FunctionCallee, 5> SanCovStoreFunction;
260   std::array<FunctionCallee, 2> SanCovTraceDivFunction;
261   FunctionCallee SanCovTraceGepFunction;
262   FunctionCallee SanCovTraceSwitchFunction;
263   GlobalVariable *SanCovLowestStack;
264   Type *Int128PtrTy, *IntptrTy, *IntptrPtrTy, *Int64Ty, *Int64PtrTy, *Int32Ty,
265       *Int32PtrTy, *Int16PtrTy, *Int16Ty, *Int8Ty, *Int8PtrTy, *Int1Ty,
266       *Int1PtrTy;
267   Module *CurModule;
268   std::string CurModuleUniqueId;
269   Triple TargetTriple;
270   LLVMContext *C;
271   const DataLayout *DL;
272 
273   GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
274   GlobalVariable *Function8bitCounterArray;  // for inline-8bit-counters.
275   GlobalVariable *FunctionBoolArray;         // for inline-bool-flag.
276   GlobalVariable *FunctionPCsArray;  // for pc-table.
277   GlobalVariable *FunctionCFsArray;  // for control flow table
278   SmallVector<GlobalValue *, 20> GlobalsToAppendToUsed;
279   SmallVector<GlobalValue *, 20> GlobalsToAppendToCompilerUsed;
280 
281   SanitizerCoverageOptions Options;
282 
283   const SpecialCaseList *Allowlist;
284   const SpecialCaseList *Blocklist;
285 };
286 } // namespace
287 
288 PreservedAnalyses SanitizerCoveragePass::run(Module &M,
289                                              ModuleAnalysisManager &MAM) {
290   ModuleSanitizerCoverage ModuleSancov(Options, Allowlist.get(),
291                                        Blocklist.get());
292   auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
293   auto DTCallback = [&FAM](Function &F) -> const DominatorTree * {
294     return &FAM.getResult<DominatorTreeAnalysis>(F);
295   };
296   auto PDTCallback = [&FAM](Function &F) -> const PostDominatorTree * {
297     return &FAM.getResult<PostDominatorTreeAnalysis>(F);
298   };
299   if (!ModuleSancov.instrumentModule(M, DTCallback, PDTCallback))
300     return PreservedAnalyses::all();
301 
302   PreservedAnalyses PA = PreservedAnalyses::none();
303   // GlobalsAA is considered stateless and does not get invalidated unless
304   // explicitly invalidated; PreservedAnalyses::none() is not enough. Sanitizers
305   // make changes that require GlobalsAA to be invalidated.
306   PA.abandon<GlobalsAA>();
307   return PA;
308 }
309 
310 std::pair<Value *, Value *>
311 ModuleSanitizerCoverage::CreateSecStartEnd(Module &M, const char *Section,
312                                            Type *Ty) {
313   // Use ExternalWeak so that if all sections are discarded due to section
314   // garbage collection, the linker will not report undefined symbol errors.
315   // Windows defines the start/stop symbols in compiler-rt so no need for
316   // ExternalWeak.
317   GlobalValue::LinkageTypes Linkage = TargetTriple.isOSBinFormatCOFF()
318                                           ? GlobalVariable::ExternalLinkage
319                                           : GlobalVariable::ExternalWeakLinkage;
320   GlobalVariable *SecStart =
321       new GlobalVariable(M, Ty, false, Linkage, nullptr,
322                          getSectionStart(Section));
323   SecStart->setVisibility(GlobalValue::HiddenVisibility);
324   GlobalVariable *SecEnd =
325       new GlobalVariable(M, Ty, false, Linkage, nullptr,
326                          getSectionEnd(Section));
327   SecEnd->setVisibility(GlobalValue::HiddenVisibility);
328   IRBuilder<> IRB(M.getContext());
329   if (!TargetTriple.isOSBinFormatCOFF())
330     return std::make_pair(SecStart, SecEnd);
331 
332   // Account for the fact that on windows-msvc __start_* symbols actually
333   // point to a uint64_t before the start of the array.
334   auto SecStartI8Ptr = IRB.CreatePointerCast(SecStart, Int8PtrTy);
335   auto GEP = IRB.CreateGEP(Int8Ty, SecStartI8Ptr,
336                            ConstantInt::get(IntptrTy, sizeof(uint64_t)));
337   return std::make_pair(IRB.CreatePointerCast(GEP, PointerType::getUnqual(Ty)),
338                         SecEnd);
339 }
340 
341 Function *ModuleSanitizerCoverage::CreateInitCallsForSections(
342     Module &M, const char *CtorName, const char *InitFunctionName, Type *Ty,
343     const char *Section) {
344   auto SecStartEnd = CreateSecStartEnd(M, Section, Ty);
345   auto SecStart = SecStartEnd.first;
346   auto SecEnd = SecStartEnd.second;
347   Function *CtorFunc;
348   Type *PtrTy = PointerType::getUnqual(Ty);
349   std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
350       M, CtorName, InitFunctionName, {PtrTy, PtrTy}, {SecStart, SecEnd});
351   assert(CtorFunc->getName() == CtorName);
352 
353   if (TargetTriple.supportsCOMDAT()) {
354     // Use comdat to dedup CtorFunc.
355     CtorFunc->setComdat(M.getOrInsertComdat(CtorName));
356     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc);
357   } else {
358     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
359   }
360 
361   if (TargetTriple.isOSBinFormatCOFF()) {
362     // In COFF files, if the contructors are set as COMDAT (they are because
363     // COFF supports COMDAT) and the linker flag /OPT:REF (strip unreferenced
364     // functions and data) is used, the constructors get stripped. To prevent
365     // this, give the constructors weak ODR linkage and ensure the linker knows
366     // to include the sancov constructor. This way the linker can deduplicate
367     // the constructors but always leave one copy.
368     CtorFunc->setLinkage(GlobalValue::WeakODRLinkage);
369   }
370   return CtorFunc;
371 }
372 
373 bool ModuleSanitizerCoverage::instrumentModule(
374     Module &M, DomTreeCallback DTCallback, PostDomTreeCallback PDTCallback) {
375   if (Options.CoverageType == SanitizerCoverageOptions::SCK_None)
376     return false;
377   if (Allowlist &&
378       !Allowlist->inSection("coverage", "src", M.getSourceFileName()))
379     return false;
380   if (Blocklist &&
381       Blocklist->inSection("coverage", "src", M.getSourceFileName()))
382     return false;
383   C = &(M.getContext());
384   DL = &M.getDataLayout();
385   CurModule = &M;
386   CurModuleUniqueId = getUniqueModuleId(CurModule);
387   TargetTriple = Triple(M.getTargetTriple());
388   FunctionGuardArray = nullptr;
389   Function8bitCounterArray = nullptr;
390   FunctionBoolArray = nullptr;
391   FunctionPCsArray = nullptr;
392   FunctionCFsArray = nullptr;
393   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
394   IntptrPtrTy = PointerType::getUnqual(IntptrTy);
395   Type *VoidTy = Type::getVoidTy(*C);
396   IRBuilder<> IRB(*C);
397   Int128PtrTy = PointerType::getUnqual(IRB.getInt128Ty());
398   Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
399   Int16PtrTy = PointerType::getUnqual(IRB.getInt16Ty());
400   Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
401   Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty());
402   Int1PtrTy = PointerType::getUnqual(IRB.getInt1Ty());
403   Int64Ty = IRB.getInt64Ty();
404   Int32Ty = IRB.getInt32Ty();
405   Int16Ty = IRB.getInt16Ty();
406   Int8Ty = IRB.getInt8Ty();
407   Int1Ty = IRB.getInt1Ty();
408 
409   SanCovTracePCIndir =
410       M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy);
411   // Make sure smaller parameters are zero-extended to i64 if required by the
412   // target ABI.
413   AttributeList SanCovTraceCmpZeroExtAL;
414   SanCovTraceCmpZeroExtAL =
415       SanCovTraceCmpZeroExtAL.addParamAttribute(*C, 0, Attribute::ZExt);
416   SanCovTraceCmpZeroExtAL =
417       SanCovTraceCmpZeroExtAL.addParamAttribute(*C, 1, Attribute::ZExt);
418 
419   SanCovTraceCmpFunction[0] =
420       M.getOrInsertFunction(SanCovTraceCmp1, SanCovTraceCmpZeroExtAL, VoidTy,
421                             IRB.getInt8Ty(), IRB.getInt8Ty());
422   SanCovTraceCmpFunction[1] =
423       M.getOrInsertFunction(SanCovTraceCmp2, SanCovTraceCmpZeroExtAL, VoidTy,
424                             IRB.getInt16Ty(), IRB.getInt16Ty());
425   SanCovTraceCmpFunction[2] =
426       M.getOrInsertFunction(SanCovTraceCmp4, SanCovTraceCmpZeroExtAL, VoidTy,
427                             IRB.getInt32Ty(), IRB.getInt32Ty());
428   SanCovTraceCmpFunction[3] =
429       M.getOrInsertFunction(SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty);
430 
431   SanCovTraceConstCmpFunction[0] = M.getOrInsertFunction(
432       SanCovTraceConstCmp1, SanCovTraceCmpZeroExtAL, VoidTy, Int8Ty, Int8Ty);
433   SanCovTraceConstCmpFunction[1] = M.getOrInsertFunction(
434       SanCovTraceConstCmp2, SanCovTraceCmpZeroExtAL, VoidTy, Int16Ty, Int16Ty);
435   SanCovTraceConstCmpFunction[2] = M.getOrInsertFunction(
436       SanCovTraceConstCmp4, SanCovTraceCmpZeroExtAL, VoidTy, Int32Ty, Int32Ty);
437   SanCovTraceConstCmpFunction[3] =
438       M.getOrInsertFunction(SanCovTraceConstCmp8, VoidTy, Int64Ty, Int64Ty);
439 
440   // Loads.
441   SanCovLoadFunction[0] = M.getOrInsertFunction(SanCovLoad1, VoidTy, Int8PtrTy);
442   SanCovLoadFunction[1] =
443       M.getOrInsertFunction(SanCovLoad2, VoidTy, Int16PtrTy);
444   SanCovLoadFunction[2] =
445       M.getOrInsertFunction(SanCovLoad4, VoidTy, Int32PtrTy);
446   SanCovLoadFunction[3] =
447       M.getOrInsertFunction(SanCovLoad8, VoidTy, Int64PtrTy);
448   SanCovLoadFunction[4] =
449       M.getOrInsertFunction(SanCovLoad16, VoidTy, Int128PtrTy);
450   // Stores.
451   SanCovStoreFunction[0] =
452       M.getOrInsertFunction(SanCovStore1, VoidTy, Int8PtrTy);
453   SanCovStoreFunction[1] =
454       M.getOrInsertFunction(SanCovStore2, VoidTy, Int16PtrTy);
455   SanCovStoreFunction[2] =
456       M.getOrInsertFunction(SanCovStore4, VoidTy, Int32PtrTy);
457   SanCovStoreFunction[3] =
458       M.getOrInsertFunction(SanCovStore8, VoidTy, Int64PtrTy);
459   SanCovStoreFunction[4] =
460       M.getOrInsertFunction(SanCovStore16, VoidTy, Int128PtrTy);
461 
462   {
463     AttributeList AL;
464     AL = AL.addParamAttribute(*C, 0, Attribute::ZExt);
465     SanCovTraceDivFunction[0] =
466         M.getOrInsertFunction(SanCovTraceDiv4, AL, VoidTy, IRB.getInt32Ty());
467   }
468   SanCovTraceDivFunction[1] =
469       M.getOrInsertFunction(SanCovTraceDiv8, VoidTy, Int64Ty);
470   SanCovTraceGepFunction =
471       M.getOrInsertFunction(SanCovTraceGep, VoidTy, IntptrTy);
472   SanCovTraceSwitchFunction =
473       M.getOrInsertFunction(SanCovTraceSwitchName, VoidTy, Int64Ty, Int64PtrTy);
474 
475   Constant *SanCovLowestStackConstant =
476       M.getOrInsertGlobal(SanCovLowestStackName, IntptrTy);
477   SanCovLowestStack = dyn_cast<GlobalVariable>(SanCovLowestStackConstant);
478   if (!SanCovLowestStack || SanCovLowestStack->getValueType() != IntptrTy) {
479     C->emitError(StringRef("'") + SanCovLowestStackName +
480                  "' should not be declared by the user");
481     return true;
482   }
483   SanCovLowestStack->setThreadLocalMode(
484       GlobalValue::ThreadLocalMode::InitialExecTLSModel);
485   if (Options.StackDepth && !SanCovLowestStack->isDeclaration())
486     SanCovLowestStack->setInitializer(Constant::getAllOnesValue(IntptrTy));
487 
488   SanCovTracePC = M.getOrInsertFunction(SanCovTracePCName, VoidTy);
489   SanCovTracePCGuard =
490       M.getOrInsertFunction(SanCovTracePCGuardName, VoidTy, Int32PtrTy);
491 
492   for (auto &F : M)
493     instrumentFunction(F, DTCallback, PDTCallback);
494 
495   Function *Ctor = nullptr;
496 
497   if (FunctionGuardArray)
498     Ctor = CreateInitCallsForSections(M, SanCovModuleCtorTracePcGuardName,
499                                       SanCovTracePCGuardInitName, Int32Ty,
500                                       SanCovGuardsSectionName);
501   if (Function8bitCounterArray)
502     Ctor = CreateInitCallsForSections(M, SanCovModuleCtor8bitCountersName,
503                                       SanCov8bitCountersInitName, Int8Ty,
504                                       SanCovCountersSectionName);
505   if (FunctionBoolArray) {
506     Ctor = CreateInitCallsForSections(M, SanCovModuleCtorBoolFlagName,
507                                       SanCovBoolFlagInitName, Int1Ty,
508                                       SanCovBoolFlagSectionName);
509   }
510   if (Ctor && Options.PCTable) {
511     auto SecStartEnd = CreateSecStartEnd(M, SanCovPCsSectionName, IntptrTy);
512     FunctionCallee InitFunction = declareSanitizerInitFunction(
513         M, SanCovPCsInitName, {IntptrPtrTy, IntptrPtrTy});
514     IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
515     IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second});
516   }
517 
518   if (Ctor && Options.CollectControlFlow) {
519     auto SecStartEnd = CreateSecStartEnd(M, SanCovCFsSectionName, IntptrTy);
520     FunctionCallee InitFunction = declareSanitizerInitFunction(
521         M, SanCovCFsInitName, {IntptrPtrTy, IntptrPtrTy});
522     IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
523     IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second});
524   }
525 
526   appendToUsed(M, GlobalsToAppendToUsed);
527   appendToCompilerUsed(M, GlobalsToAppendToCompilerUsed);
528   return true;
529 }
530 
531 // True if block has successors and it dominates all of them.
532 static bool isFullDominator(const BasicBlock *BB, const DominatorTree *DT) {
533   if (succ_empty(BB))
534     return false;
535 
536   return llvm::all_of(successors(BB), [&](const BasicBlock *SUCC) {
537     return DT->dominates(BB, SUCC);
538   });
539 }
540 
541 // True if block has predecessors and it postdominates all of them.
542 static bool isFullPostDominator(const BasicBlock *BB,
543                                 const PostDominatorTree *PDT) {
544   if (pred_empty(BB))
545     return false;
546 
547   return llvm::all_of(predecessors(BB), [&](const BasicBlock *PRED) {
548     return PDT->dominates(BB, PRED);
549   });
550 }
551 
552 static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB,
553                                   const DominatorTree *DT,
554                                   const PostDominatorTree *PDT,
555                                   const SanitizerCoverageOptions &Options) {
556   // Don't insert coverage for blocks containing nothing but unreachable: we
557   // will never call __sanitizer_cov() for them, so counting them in
558   // NumberOfInstrumentedBlocks() might complicate calculation of code coverage
559   // percentage. Also, unreachable instructions frequently have no debug
560   // locations.
561   if (isa<UnreachableInst>(BB->getFirstNonPHIOrDbgOrLifetime()))
562     return false;
563 
564   // Don't insert coverage into blocks without a valid insertion point
565   // (catchswitch blocks).
566   if (BB->getFirstInsertionPt() == BB->end())
567     return false;
568 
569   if (Options.NoPrune || &F.getEntryBlock() == BB)
570     return true;
571 
572   if (Options.CoverageType == SanitizerCoverageOptions::SCK_Function &&
573       &F.getEntryBlock() != BB)
574     return false;
575 
576   // Do not instrument full dominators, or full post-dominators with multiple
577   // predecessors.
578   return !isFullDominator(BB, DT)
579     && !(isFullPostDominator(BB, PDT) && !BB->getSinglePredecessor());
580 }
581 
582 
583 // Returns true iff From->To is a backedge.
584 // A twist here is that we treat From->To as a backedge if
585 //   * To dominates From or
586 //   * To->UniqueSuccessor dominates From
587 static bool IsBackEdge(BasicBlock *From, BasicBlock *To,
588                        const DominatorTree *DT) {
589   if (DT->dominates(To, From))
590     return true;
591   if (auto Next = To->getUniqueSuccessor())
592     if (DT->dominates(Next, From))
593       return true;
594   return false;
595 }
596 
597 // Prunes uninteresting Cmp instrumentation:
598 //   * CMP instructions that feed into loop backedge branch.
599 //
600 // Note that Cmp pruning is controlled by the same flag as the
601 // BB pruning.
602 static bool IsInterestingCmp(ICmpInst *CMP, const DominatorTree *DT,
603                              const SanitizerCoverageOptions &Options) {
604   if (!Options.NoPrune)
605     if (CMP->hasOneUse())
606       if (auto BR = dyn_cast<BranchInst>(CMP->user_back()))
607         for (BasicBlock *B : BR->successors())
608           if (IsBackEdge(BR->getParent(), B, DT))
609             return false;
610   return true;
611 }
612 
613 void ModuleSanitizerCoverage::instrumentFunction(
614     Function &F, DomTreeCallback DTCallback, PostDomTreeCallback PDTCallback) {
615   if (F.empty())
616     return;
617   if (F.getName().find(".module_ctor") != std::string::npos)
618     return; // Should not instrument sanitizer init functions.
619   if (F.getName().startswith("__sanitizer_"))
620     return; // Don't instrument __sanitizer_* callbacks.
621   // Don't touch available_externally functions, their actual body is elewhere.
622   if (F.getLinkage() == GlobalValue::AvailableExternallyLinkage)
623     return;
624   // Don't instrument MSVC CRT configuration helpers. They may run before normal
625   // initialization.
626   if (F.getName() == "__local_stdio_printf_options" ||
627       F.getName() == "__local_stdio_scanf_options")
628     return;
629   if (isa<UnreachableInst>(F.getEntryBlock().getTerminator()))
630     return;
631   // Don't instrument functions using SEH for now. Splitting basic blocks like
632   // we do for coverage breaks WinEHPrepare.
633   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
634   if (F.hasPersonalityFn() &&
635       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
636     return;
637   if (Allowlist && !Allowlist->inSection("coverage", "fun", F.getName()))
638     return;
639   if (Blocklist && Blocklist->inSection("coverage", "fun", F.getName()))
640     return;
641   if (F.hasFnAttribute(Attribute::NoSanitizeCoverage))
642     return;
643   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge)
644     SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions().setIgnoreUnreachableDests());
645   SmallVector<Instruction *, 8> IndirCalls;
646   SmallVector<BasicBlock *, 16> BlocksToInstrument;
647   SmallVector<Instruction *, 8> CmpTraceTargets;
648   SmallVector<Instruction *, 8> SwitchTraceTargets;
649   SmallVector<BinaryOperator *, 8> DivTraceTargets;
650   SmallVector<GetElementPtrInst *, 8> GepTraceTargets;
651   SmallVector<LoadInst *, 8> Loads;
652   SmallVector<StoreInst *, 8> Stores;
653 
654   const DominatorTree *DT = DTCallback(F);
655   const PostDominatorTree *PDT = PDTCallback(F);
656   bool IsLeafFunc = true;
657 
658   for (auto &BB : F) {
659     if (shouldInstrumentBlock(F, &BB, DT, PDT, Options))
660       BlocksToInstrument.push_back(&BB);
661     for (auto &Inst : BB) {
662       if (Options.IndirectCalls) {
663         CallBase *CB = dyn_cast<CallBase>(&Inst);
664         if (CB && CB->isIndirectCall())
665           IndirCalls.push_back(&Inst);
666       }
667       if (Options.TraceCmp) {
668         if (ICmpInst *CMP = dyn_cast<ICmpInst>(&Inst))
669           if (IsInterestingCmp(CMP, DT, Options))
670             CmpTraceTargets.push_back(&Inst);
671         if (isa<SwitchInst>(&Inst))
672           SwitchTraceTargets.push_back(&Inst);
673       }
674       if (Options.TraceDiv)
675         if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst))
676           if (BO->getOpcode() == Instruction::SDiv ||
677               BO->getOpcode() == Instruction::UDiv)
678             DivTraceTargets.push_back(BO);
679       if (Options.TraceGep)
680         if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst))
681           GepTraceTargets.push_back(GEP);
682       if (Options.TraceLoads)
683         if (LoadInst *LI = dyn_cast<LoadInst>(&Inst))
684           Loads.push_back(LI);
685       if (Options.TraceStores)
686         if (StoreInst *SI = dyn_cast<StoreInst>(&Inst))
687           Stores.push_back(SI);
688       if (Options.StackDepth)
689         if (isa<InvokeInst>(Inst) ||
690             (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst)))
691           IsLeafFunc = false;
692     }
693   }
694 
695   if (Options.CollectControlFlow)
696     createFunctionControlFlow(F);
697 
698   InjectCoverage(F, BlocksToInstrument, IsLeafFunc);
699   InjectCoverageForIndirectCalls(F, IndirCalls);
700   InjectTraceForCmp(F, CmpTraceTargets);
701   InjectTraceForSwitch(F, SwitchTraceTargets);
702   InjectTraceForDiv(F, DivTraceTargets);
703   InjectTraceForGep(F, GepTraceTargets);
704   InjectTraceForLoadsAndStores(F, Loads, Stores);
705 }
706 
707 GlobalVariable *ModuleSanitizerCoverage::CreateFunctionLocalArrayInSection(
708     size_t NumElements, Function &F, Type *Ty, const char *Section) {
709   ArrayType *ArrayTy = ArrayType::get(Ty, NumElements);
710   auto Array = new GlobalVariable(
711       *CurModule, ArrayTy, false, GlobalVariable::PrivateLinkage,
712       Constant::getNullValue(ArrayTy), "__sancov_gen_");
713 
714   if (TargetTriple.supportsCOMDAT() &&
715       (TargetTriple.isOSBinFormatELF() || !F.isInterposable()))
716     if (auto Comdat = getOrCreateFunctionComdat(F, TargetTriple))
717       Array->setComdat(Comdat);
718   Array->setSection(getSectionName(Section));
719   Array->setAlignment(Align(DL->getTypeStoreSize(Ty).getFixedValue()));
720 
721   // sancov_pcs parallels the other metadata section(s). Optimizers (e.g.
722   // GlobalOpt/ConstantMerge) may not discard sancov_pcs and the other
723   // section(s) as a unit, so we conservatively retain all unconditionally in
724   // the compiler.
725   //
726   // With comdat (COFF/ELF), the linker can guarantee the associated sections
727   // will be retained or discarded as a unit, so llvm.compiler.used is
728   // sufficient. Otherwise, conservatively make all of them retained by the
729   // linker.
730   if (Array->hasComdat())
731     GlobalsToAppendToCompilerUsed.push_back(Array);
732   else
733     GlobalsToAppendToUsed.push_back(Array);
734 
735   return Array;
736 }
737 
738 GlobalVariable *
739 ModuleSanitizerCoverage::CreatePCArray(Function &F,
740                                        ArrayRef<BasicBlock *> AllBlocks) {
741   size_t N = AllBlocks.size();
742   assert(N);
743   SmallVector<Constant *, 32> PCs;
744   IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
745   for (size_t i = 0; i < N; i++) {
746     if (&F.getEntryBlock() == AllBlocks[i]) {
747       PCs.push_back((Constant *)IRB.CreatePointerCast(&F, IntptrPtrTy));
748       PCs.push_back((Constant *)IRB.CreateIntToPtr(
749           ConstantInt::get(IntptrTy, 1), IntptrPtrTy));
750     } else {
751       PCs.push_back((Constant *)IRB.CreatePointerCast(
752           BlockAddress::get(AllBlocks[i]), IntptrPtrTy));
753       PCs.push_back(Constant::getNullValue(IntptrPtrTy));
754     }
755   }
756   auto *PCArray = CreateFunctionLocalArrayInSection(N * 2, F, IntptrPtrTy,
757                                                     SanCovPCsSectionName);
758   PCArray->setInitializer(
759       ConstantArray::get(ArrayType::get(IntptrPtrTy, N * 2), PCs));
760   PCArray->setConstant(true);
761 
762   return PCArray;
763 }
764 
765 void ModuleSanitizerCoverage::CreateFunctionLocalArrays(
766     Function &F, ArrayRef<BasicBlock *> AllBlocks) {
767   if (Options.TracePCGuard)
768     FunctionGuardArray = CreateFunctionLocalArrayInSection(
769         AllBlocks.size(), F, Int32Ty, SanCovGuardsSectionName);
770 
771   if (Options.Inline8bitCounters)
772     Function8bitCounterArray = CreateFunctionLocalArrayInSection(
773         AllBlocks.size(), F, Int8Ty, SanCovCountersSectionName);
774   if (Options.InlineBoolFlag)
775     FunctionBoolArray = CreateFunctionLocalArrayInSection(
776         AllBlocks.size(), F, Int1Ty, SanCovBoolFlagSectionName);
777 
778   if (Options.PCTable)
779     FunctionPCsArray = CreatePCArray(F, AllBlocks);
780 }
781 
782 bool ModuleSanitizerCoverage::InjectCoverage(Function &F,
783                                              ArrayRef<BasicBlock *> AllBlocks,
784                                              bool IsLeafFunc) {
785   if (AllBlocks.empty()) return false;
786   CreateFunctionLocalArrays(F, AllBlocks);
787   for (size_t i = 0, N = AllBlocks.size(); i < N; i++)
788     InjectCoverageAtBlock(F, *AllBlocks[i], i, IsLeafFunc);
789   return true;
790 }
791 
792 // On every indirect call we call a run-time function
793 // __sanitizer_cov_indir_call* with two parameters:
794 //   - callee address,
795 //   - global cache array that contains CacheSize pointers (zero-initialized).
796 //     The cache is used to speed up recording the caller-callee pairs.
797 // The address of the caller is passed implicitly via caller PC.
798 // CacheSize is encoded in the name of the run-time function.
799 void ModuleSanitizerCoverage::InjectCoverageForIndirectCalls(
800     Function &F, ArrayRef<Instruction *> IndirCalls) {
801   if (IndirCalls.empty())
802     return;
803   assert(Options.TracePC || Options.TracePCGuard ||
804          Options.Inline8bitCounters || Options.InlineBoolFlag);
805   for (auto *I : IndirCalls) {
806     InstrumentationIRBuilder IRB(I);
807     CallBase &CB = cast<CallBase>(*I);
808     Value *Callee = CB.getCalledOperand();
809     if (isa<InlineAsm>(Callee))
810       continue;
811     IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy));
812   }
813 }
814 
815 // For every switch statement we insert a call:
816 // __sanitizer_cov_trace_switch(CondValue,
817 //      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
818 
819 void ModuleSanitizerCoverage::InjectTraceForSwitch(
820     Function &, ArrayRef<Instruction *> SwitchTraceTargets) {
821   for (auto *I : SwitchTraceTargets) {
822     if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
823       InstrumentationIRBuilder IRB(I);
824       SmallVector<Constant *, 16> Initializers;
825       Value *Cond = SI->getCondition();
826       if (Cond->getType()->getScalarSizeInBits() >
827           Int64Ty->getScalarSizeInBits())
828         continue;
829       Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
830       Initializers.push_back(
831           ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
832       if (Cond->getType()->getScalarSizeInBits() <
833           Int64Ty->getScalarSizeInBits())
834         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
835       for (auto It : SI->cases()) {
836         Constant *C = It.getCaseValue();
837         if (C->getType()->getScalarSizeInBits() <
838             Int64Ty->getScalarSizeInBits())
839           C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
840         Initializers.push_back(C);
841       }
842       llvm::sort(drop_begin(Initializers, 2),
843                  [](const Constant *A, const Constant *B) {
844                    return cast<ConstantInt>(A)->getLimitedValue() <
845                           cast<ConstantInt>(B)->getLimitedValue();
846                  });
847       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
848       GlobalVariable *GV = new GlobalVariable(
849           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
850           ConstantArray::get(ArrayOfInt64Ty, Initializers),
851           "__sancov_gen_cov_switch_values");
852       IRB.CreateCall(SanCovTraceSwitchFunction,
853                      {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
854     }
855   }
856 }
857 
858 void ModuleSanitizerCoverage::InjectTraceForDiv(
859     Function &, ArrayRef<BinaryOperator *> DivTraceTargets) {
860   for (auto *BO : DivTraceTargets) {
861     InstrumentationIRBuilder IRB(BO);
862     Value *A1 = BO->getOperand(1);
863     if (isa<ConstantInt>(A1)) continue;
864     if (!A1->getType()->isIntegerTy())
865       continue;
866     uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType());
867     int CallbackIdx = TypeSize == 32 ? 0 :
868         TypeSize == 64 ? 1 : -1;
869     if (CallbackIdx < 0) continue;
870     auto Ty = Type::getIntNTy(*C, TypeSize);
871     IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx],
872                    {IRB.CreateIntCast(A1, Ty, true)});
873   }
874 }
875 
876 void ModuleSanitizerCoverage::InjectTraceForGep(
877     Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) {
878   for (auto *GEP : GepTraceTargets) {
879     InstrumentationIRBuilder IRB(GEP);
880     for (Use &Idx : GEP->indices())
881       if (!isa<ConstantInt>(Idx) && Idx->getType()->isIntegerTy())
882         IRB.CreateCall(SanCovTraceGepFunction,
883                        {IRB.CreateIntCast(Idx, IntptrTy, true)});
884   }
885 }
886 
887 void ModuleSanitizerCoverage::InjectTraceForLoadsAndStores(
888     Function &, ArrayRef<LoadInst *> Loads, ArrayRef<StoreInst *> Stores) {
889   auto CallbackIdx = [&](Type *ElementTy) -> int {
890     uint64_t TypeSize = DL->getTypeStoreSizeInBits(ElementTy);
891     return TypeSize == 8     ? 0
892            : TypeSize == 16  ? 1
893            : TypeSize == 32  ? 2
894            : TypeSize == 64  ? 3
895            : TypeSize == 128 ? 4
896                              : -1;
897   };
898   Type *PointerType[5] = {Int8PtrTy, Int16PtrTy, Int32PtrTy, Int64PtrTy,
899                           Int128PtrTy};
900   for (auto *LI : Loads) {
901     InstrumentationIRBuilder IRB(LI);
902     auto Ptr = LI->getPointerOperand();
903     int Idx = CallbackIdx(LI->getType());
904     if (Idx < 0)
905       continue;
906     IRB.CreateCall(SanCovLoadFunction[Idx],
907                    IRB.CreatePointerCast(Ptr, PointerType[Idx]));
908   }
909   for (auto *SI : Stores) {
910     InstrumentationIRBuilder IRB(SI);
911     auto Ptr = SI->getPointerOperand();
912     int Idx = CallbackIdx(SI->getValueOperand()->getType());
913     if (Idx < 0)
914       continue;
915     IRB.CreateCall(SanCovStoreFunction[Idx],
916                    IRB.CreatePointerCast(Ptr, PointerType[Idx]));
917   }
918 }
919 
920 void ModuleSanitizerCoverage::InjectTraceForCmp(
921     Function &, ArrayRef<Instruction *> CmpTraceTargets) {
922   for (auto *I : CmpTraceTargets) {
923     if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
924       InstrumentationIRBuilder IRB(ICMP);
925       Value *A0 = ICMP->getOperand(0);
926       Value *A1 = ICMP->getOperand(1);
927       if (!A0->getType()->isIntegerTy())
928         continue;
929       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
930       int CallbackIdx = TypeSize == 8 ? 0 :
931                         TypeSize == 16 ? 1 :
932                         TypeSize == 32 ? 2 :
933                         TypeSize == 64 ? 3 : -1;
934       if (CallbackIdx < 0) continue;
935       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
936       auto CallbackFunc = SanCovTraceCmpFunction[CallbackIdx];
937       bool FirstIsConst = isa<ConstantInt>(A0);
938       bool SecondIsConst = isa<ConstantInt>(A1);
939       // If both are const, then we don't need such a comparison.
940       if (FirstIsConst && SecondIsConst) continue;
941       // If only one is const, then make it the first callback argument.
942       if (FirstIsConst || SecondIsConst) {
943         CallbackFunc = SanCovTraceConstCmpFunction[CallbackIdx];
944         if (SecondIsConst)
945           std::swap(A0, A1);
946       }
947 
948       auto Ty = Type::getIntNTy(*C, TypeSize);
949       IRB.CreateCall(CallbackFunc, {IRB.CreateIntCast(A0, Ty, true),
950               IRB.CreateIntCast(A1, Ty, true)});
951     }
952   }
953 }
954 
955 void ModuleSanitizerCoverage::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
956                                                     size_t Idx,
957                                                     bool IsLeafFunc) {
958   BasicBlock::iterator IP = BB.getFirstInsertionPt();
959   bool IsEntryBB = &BB == &F.getEntryBlock();
960   DebugLoc EntryLoc;
961   if (IsEntryBB) {
962     if (auto SP = F.getSubprogram())
963       EntryLoc = DILocation::get(SP->getContext(), SP->getScopeLine(), 0, SP);
964     // Keep static allocas and llvm.localescape calls in the entry block.  Even
965     // if we aren't splitting the block, it's nice for allocas to be before
966     // calls.
967     IP = PrepareToSplitEntryBlock(BB, IP);
968   }
969 
970   InstrumentationIRBuilder IRB(&*IP);
971   if (EntryLoc)
972     IRB.SetCurrentDebugLocation(EntryLoc);
973   if (Options.TracePC) {
974     IRB.CreateCall(SanCovTracePC)
975         ->setCannotMerge(); // gets the PC using GET_CALLER_PC.
976   }
977   if (Options.TracePCGuard) {
978     auto GuardPtr = IRB.CreateIntToPtr(
979         IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy),
980                       ConstantInt::get(IntptrTy, Idx * 4)),
981         Int32PtrTy);
982     IRB.CreateCall(SanCovTracePCGuard, GuardPtr)->setCannotMerge();
983   }
984   if (Options.Inline8bitCounters) {
985     auto CounterPtr = IRB.CreateGEP(
986         Function8bitCounterArray->getValueType(), Function8bitCounterArray,
987         {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)});
988     auto Load = IRB.CreateLoad(Int8Ty, CounterPtr);
989     auto Inc = IRB.CreateAdd(Load, ConstantInt::get(Int8Ty, 1));
990     auto Store = IRB.CreateStore(Inc, CounterPtr);
991     Load->setNoSanitizeMetadata();
992     Store->setNoSanitizeMetadata();
993   }
994   if (Options.InlineBoolFlag) {
995     auto FlagPtr = IRB.CreateGEP(
996         FunctionBoolArray->getValueType(), FunctionBoolArray,
997         {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)});
998     auto Load = IRB.CreateLoad(Int1Ty, FlagPtr);
999     auto ThenTerm =
1000         SplitBlockAndInsertIfThen(IRB.CreateIsNull(Load), &*IP, false);
1001     IRBuilder<> ThenIRB(ThenTerm);
1002     auto Store = ThenIRB.CreateStore(ConstantInt::getTrue(Int1Ty), FlagPtr);
1003     Load->setNoSanitizeMetadata();
1004     Store->setNoSanitizeMetadata();
1005   }
1006   if (Options.StackDepth && IsEntryBB && !IsLeafFunc) {
1007     // Check stack depth.  If it's the deepest so far, record it.
1008     Module *M = F.getParent();
1009     Function *GetFrameAddr = Intrinsic::getDeclaration(
1010         M, Intrinsic::frameaddress,
1011         IRB.getInt8PtrTy(M->getDataLayout().getAllocaAddrSpace()));
1012     auto FrameAddrPtr =
1013         IRB.CreateCall(GetFrameAddr, {Constant::getNullValue(Int32Ty)});
1014     auto FrameAddrInt = IRB.CreatePtrToInt(FrameAddrPtr, IntptrTy);
1015     auto LowestStack = IRB.CreateLoad(IntptrTy, SanCovLowestStack);
1016     auto IsStackLower = IRB.CreateICmpULT(FrameAddrInt, LowestStack);
1017     auto ThenTerm = SplitBlockAndInsertIfThen(IsStackLower, &*IP, false);
1018     IRBuilder<> ThenIRB(ThenTerm);
1019     auto Store = ThenIRB.CreateStore(FrameAddrInt, SanCovLowestStack);
1020     LowestStack->setNoSanitizeMetadata();
1021     Store->setNoSanitizeMetadata();
1022   }
1023 }
1024 
1025 std::string
1026 ModuleSanitizerCoverage::getSectionName(const std::string &Section) const {
1027   if (TargetTriple.isOSBinFormatCOFF()) {
1028     if (Section == SanCovCountersSectionName)
1029       return ".SCOV$CM";
1030     if (Section == SanCovBoolFlagSectionName)
1031       return ".SCOV$BM";
1032     if (Section == SanCovPCsSectionName)
1033       return ".SCOVP$M";
1034     return ".SCOV$GM"; // For SanCovGuardsSectionName.
1035   }
1036   if (TargetTriple.isOSBinFormatMachO())
1037     return "__DATA,__" + Section;
1038   return "__" + Section;
1039 }
1040 
1041 std::string
1042 ModuleSanitizerCoverage::getSectionStart(const std::string &Section) const {
1043   if (TargetTriple.isOSBinFormatMachO())
1044     return "\1section$start$__DATA$__" + Section;
1045   return "__start___" + Section;
1046 }
1047 
1048 std::string
1049 ModuleSanitizerCoverage::getSectionEnd(const std::string &Section) const {
1050   if (TargetTriple.isOSBinFormatMachO())
1051     return "\1section$end$__DATA$__" + Section;
1052   return "__stop___" + Section;
1053 }
1054 
1055 void ModuleSanitizerCoverage::createFunctionControlFlow(Function &F) {
1056   SmallVector<Constant *, 32> CFs;
1057   IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
1058 
1059   for (auto &BB : F) {
1060     // blockaddress can not be used on function's entry block.
1061     if (&BB == &F.getEntryBlock())
1062       CFs.push_back((Constant *)IRB.CreatePointerCast(&F, IntptrPtrTy));
1063     else
1064       CFs.push_back((Constant *)IRB.CreatePointerCast(BlockAddress::get(&BB),
1065                                                       IntptrPtrTy));
1066 
1067     for (auto SuccBB : successors(&BB)) {
1068       assert(SuccBB != &F.getEntryBlock());
1069       CFs.push_back((Constant *)IRB.CreatePointerCast(BlockAddress::get(SuccBB),
1070                                                       IntptrPtrTy));
1071     }
1072 
1073     CFs.push_back((Constant *)Constant::getNullValue(IntptrPtrTy));
1074 
1075     for (auto &Inst : BB) {
1076       if (CallBase *CB = dyn_cast<CallBase>(&Inst)) {
1077         if (CB->isIndirectCall()) {
1078           // TODO(navidem): handle indirect calls, for now mark its existence.
1079           CFs.push_back((Constant *)IRB.CreateIntToPtr(
1080               ConstantInt::get(IntptrTy, -1), IntptrPtrTy));
1081         } else {
1082           auto CalledF = CB->getCalledFunction();
1083           if (CalledF && !CalledF->isIntrinsic())
1084             CFs.push_back(
1085                 (Constant *)IRB.CreatePointerCast(CalledF, IntptrPtrTy));
1086         }
1087       }
1088     }
1089 
1090     CFs.push_back((Constant *)Constant::getNullValue(IntptrPtrTy));
1091   }
1092 
1093   FunctionCFsArray = CreateFunctionLocalArrayInSection(
1094       CFs.size(), F, IntptrPtrTy, SanCovCFsSectionName);
1095   FunctionCFsArray->setInitializer(
1096       ConstantArray::get(ArrayType::get(IntptrPtrTy, CFs.size()), CFs));
1097   FunctionCFsArray->setConstant(true);
1098 }
1099