xref: /freebsd-src/contrib/llvm-project/llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
10b57cec5SDimitry Andric //===-- SanitizerCoverage.cpp - coverage instrumentation for sanitizers ---===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // Coverage instrumentation done on LLVM IR level, works with Sanitizers.
100b57cec5SDimitry Andric //
110b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
120b57cec5SDimitry Andric 
138bcb0991SDimitry Andric #include "llvm/Transforms/Instrumentation/SanitizerCoverage.h"
140b57cec5SDimitry Andric #include "llvm/ADT/ArrayRef.h"
150b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h"
16bdd1243dSDimitry Andric #include "llvm/Analysis/GlobalsModRef.h"
170b57cec5SDimitry Andric #include "llvm/Analysis/PostDominators.h"
180b57cec5SDimitry Andric #include "llvm/IR/Constant.h"
190b57cec5SDimitry Andric #include "llvm/IR/DataLayout.h"
200b57cec5SDimitry Andric #include "llvm/IR/Dominators.h"
2106c3fb27SDimitry Andric #include "llvm/IR/EHPersonalities.h"
220b57cec5SDimitry Andric #include "llvm/IR/Function.h"
230b57cec5SDimitry Andric #include "llvm/IR/GlobalVariable.h"
240b57cec5SDimitry Andric #include "llvm/IR/IRBuilder.h"
250b57cec5SDimitry Andric #include "llvm/IR/IntrinsicInst.h"
260b57cec5SDimitry Andric #include "llvm/IR/Intrinsics.h"
270b57cec5SDimitry Andric #include "llvm/IR/LLVMContext.h"
28*0fca6ea1SDimitry Andric #include "llvm/IR/MDBuilder.h"
290b57cec5SDimitry Andric #include "llvm/IR/Module.h"
300b57cec5SDimitry Andric #include "llvm/IR/Type.h"
310b57cec5SDimitry Andric #include "llvm/Support/CommandLine.h"
325ffd83dbSDimitry Andric #include "llvm/Support/SpecialCaseList.h"
335ffd83dbSDimitry Andric #include "llvm/Support/VirtualFileSystem.h"
3406c3fb27SDimitry Andric #include "llvm/TargetParser/Triple.h"
350b57cec5SDimitry Andric #include "llvm/Transforms/Utils/BasicBlockUtils.h"
360b57cec5SDimitry Andric #include "llvm/Transforms/Utils/ModuleUtils.h"
370b57cec5SDimitry Andric 
380b57cec5SDimitry Andric using namespace llvm;
390b57cec5SDimitry Andric 
400b57cec5SDimitry Andric #define DEBUG_TYPE "sancov"
410b57cec5SDimitry Andric 
42e8d8bef9SDimitry Andric const char SanCovTracePCIndirName[] = "__sanitizer_cov_trace_pc_indir";
43e8d8bef9SDimitry Andric const char SanCovTracePCName[] = "__sanitizer_cov_trace_pc";
44e8d8bef9SDimitry Andric const char SanCovTraceCmp1[] = "__sanitizer_cov_trace_cmp1";
45e8d8bef9SDimitry Andric const char SanCovTraceCmp2[] = "__sanitizer_cov_trace_cmp2";
46e8d8bef9SDimitry Andric const char SanCovTraceCmp4[] = "__sanitizer_cov_trace_cmp4";
47e8d8bef9SDimitry Andric const char SanCovTraceCmp8[] = "__sanitizer_cov_trace_cmp8";
48e8d8bef9SDimitry Andric const char SanCovTraceConstCmp1[] = "__sanitizer_cov_trace_const_cmp1";
49e8d8bef9SDimitry Andric const char SanCovTraceConstCmp2[] = "__sanitizer_cov_trace_const_cmp2";
50e8d8bef9SDimitry Andric const char SanCovTraceConstCmp4[] = "__sanitizer_cov_trace_const_cmp4";
51e8d8bef9SDimitry Andric const char SanCovTraceConstCmp8[] = "__sanitizer_cov_trace_const_cmp8";
52349cc55cSDimitry Andric const char SanCovLoad1[] = "__sanitizer_cov_load1";
53349cc55cSDimitry Andric const char SanCovLoad2[] = "__sanitizer_cov_load2";
54349cc55cSDimitry Andric const char SanCovLoad4[] = "__sanitizer_cov_load4";
55349cc55cSDimitry Andric const char SanCovLoad8[] = "__sanitizer_cov_load8";
56349cc55cSDimitry Andric const char SanCovLoad16[] = "__sanitizer_cov_load16";
57349cc55cSDimitry Andric const char SanCovStore1[] = "__sanitizer_cov_store1";
58349cc55cSDimitry Andric const char SanCovStore2[] = "__sanitizer_cov_store2";
59349cc55cSDimitry Andric const char SanCovStore4[] = "__sanitizer_cov_store4";
60349cc55cSDimitry Andric const char SanCovStore8[] = "__sanitizer_cov_store8";
61349cc55cSDimitry Andric const char SanCovStore16[] = "__sanitizer_cov_store16";
62e8d8bef9SDimitry Andric const char SanCovTraceDiv4[] = "__sanitizer_cov_trace_div4";
63e8d8bef9SDimitry Andric const char SanCovTraceDiv8[] = "__sanitizer_cov_trace_div8";
64e8d8bef9SDimitry Andric const char SanCovTraceGep[] = "__sanitizer_cov_trace_gep";
65e8d8bef9SDimitry Andric const char SanCovTraceSwitchName[] = "__sanitizer_cov_trace_switch";
66e8d8bef9SDimitry Andric const char SanCovModuleCtorTracePcGuardName[] =
670b57cec5SDimitry Andric     "sancov.module_ctor_trace_pc_guard";
68e8d8bef9SDimitry Andric const char SanCovModuleCtor8bitCountersName[] =
690b57cec5SDimitry Andric     "sancov.module_ctor_8bit_counters";
70e8d8bef9SDimitry Andric const char SanCovModuleCtorBoolFlagName[] = "sancov.module_ctor_bool_flag";
710b57cec5SDimitry Andric static const uint64_t SanCtorAndDtorPriority = 2;
720b57cec5SDimitry Andric 
73e8d8bef9SDimitry Andric const char SanCovTracePCGuardName[] = "__sanitizer_cov_trace_pc_guard";
74e8d8bef9SDimitry Andric const char SanCovTracePCGuardInitName[] = "__sanitizer_cov_trace_pc_guard_init";
75e8d8bef9SDimitry Andric const char SanCov8bitCountersInitName[] = "__sanitizer_cov_8bit_counters_init";
76e8d8bef9SDimitry Andric const char SanCovBoolFlagInitName[] = "__sanitizer_cov_bool_flag_init";
77e8d8bef9SDimitry Andric const char SanCovPCsInitName[] = "__sanitizer_cov_pcs_init";
78bdd1243dSDimitry Andric const char SanCovCFsInitName[] = "__sanitizer_cov_cfs_init";
790b57cec5SDimitry Andric 
80e8d8bef9SDimitry Andric const char SanCovGuardsSectionName[] = "sancov_guards";
81e8d8bef9SDimitry Andric const char SanCovCountersSectionName[] = "sancov_cntrs";
82e8d8bef9SDimitry Andric const char SanCovBoolFlagSectionName[] = "sancov_bools";
83e8d8bef9SDimitry Andric const char SanCovPCsSectionName[] = "sancov_pcs";
84bdd1243dSDimitry Andric const char SanCovCFsSectionName[] = "sancov_cfs";
850b57cec5SDimitry Andric 
86e8d8bef9SDimitry Andric const char SanCovLowestStackName[] = "__sancov_lowest_stack";
870b57cec5SDimitry Andric 
880b57cec5SDimitry Andric static cl::opt<int> ClCoverageLevel(
890b57cec5SDimitry Andric     "sanitizer-coverage-level",
900b57cec5SDimitry Andric     cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
910b57cec5SDimitry Andric              "3: all blocks and critical edges"),
92*0fca6ea1SDimitry Andric     cl::Hidden);
930b57cec5SDimitry Andric 
940b57cec5SDimitry Andric static cl::opt<bool> ClTracePC("sanitizer-coverage-trace-pc",
95*0fca6ea1SDimitry Andric                                cl::desc("Experimental pc tracing"), cl::Hidden);
960b57cec5SDimitry Andric 
970b57cec5SDimitry Andric static cl::opt<bool> ClTracePCGuard("sanitizer-coverage-trace-pc-guard",
980b57cec5SDimitry Andric                                     cl::desc("pc tracing with a guard"),
99*0fca6ea1SDimitry Andric                                     cl::Hidden);
1000b57cec5SDimitry Andric 
1010b57cec5SDimitry Andric // If true, we create a global variable that contains PCs of all instrumented
1020b57cec5SDimitry Andric // BBs, put this global into a named section, and pass this section's bounds
1030b57cec5SDimitry Andric // to __sanitizer_cov_pcs_init.
1040b57cec5SDimitry Andric // This way the coverage instrumentation does not need to acquire the PCs
1055ffd83dbSDimitry Andric // at run-time. Works with trace-pc-guard, inline-8bit-counters, and
1065ffd83dbSDimitry Andric // inline-bool-flag.
1070b57cec5SDimitry Andric static cl::opt<bool> ClCreatePCTable("sanitizer-coverage-pc-table",
1080b57cec5SDimitry Andric                                      cl::desc("create a static PC table"),
109*0fca6ea1SDimitry Andric                                      cl::Hidden);
1100b57cec5SDimitry Andric 
1110b57cec5SDimitry Andric static cl::opt<bool>
1120b57cec5SDimitry Andric     ClInline8bitCounters("sanitizer-coverage-inline-8bit-counters",
1130b57cec5SDimitry Andric                          cl::desc("increments 8-bit counter for every edge"),
114*0fca6ea1SDimitry Andric                          cl::Hidden);
1150b57cec5SDimitry Andric 
1160b57cec5SDimitry Andric static cl::opt<bool>
1175ffd83dbSDimitry Andric     ClInlineBoolFlag("sanitizer-coverage-inline-bool-flag",
118*0fca6ea1SDimitry Andric                      cl::desc("sets a boolean flag for every edge"),
119*0fca6ea1SDimitry Andric                      cl::Hidden);
1205ffd83dbSDimitry Andric 
1215ffd83dbSDimitry Andric static cl::opt<bool>
1220b57cec5SDimitry Andric     ClCMPTracing("sanitizer-coverage-trace-compares",
1230b57cec5SDimitry Andric                  cl::desc("Tracing of CMP and similar instructions"),
124*0fca6ea1SDimitry Andric                  cl::Hidden);
1250b57cec5SDimitry Andric 
1260b57cec5SDimitry Andric static cl::opt<bool> ClDIVTracing("sanitizer-coverage-trace-divs",
1270b57cec5SDimitry Andric                                   cl::desc("Tracing of DIV instructions"),
128*0fca6ea1SDimitry Andric                                   cl::Hidden);
1290b57cec5SDimitry Andric 
130349cc55cSDimitry Andric static cl::opt<bool> ClLoadTracing("sanitizer-coverage-trace-loads",
131349cc55cSDimitry Andric                                    cl::desc("Tracing of load instructions"),
132*0fca6ea1SDimitry Andric                                    cl::Hidden);
133349cc55cSDimitry Andric 
134349cc55cSDimitry Andric static cl::opt<bool> ClStoreTracing("sanitizer-coverage-trace-stores",
135349cc55cSDimitry Andric                                     cl::desc("Tracing of store instructions"),
136*0fca6ea1SDimitry Andric                                     cl::Hidden);
137349cc55cSDimitry Andric 
1380b57cec5SDimitry Andric static cl::opt<bool> ClGEPTracing("sanitizer-coverage-trace-geps",
1390b57cec5SDimitry Andric                                   cl::desc("Tracing of GEP instructions"),
140*0fca6ea1SDimitry Andric                                   cl::Hidden);
1410b57cec5SDimitry Andric 
1420b57cec5SDimitry Andric static cl::opt<bool>
1430b57cec5SDimitry Andric     ClPruneBlocks("sanitizer-coverage-prune-blocks",
1440b57cec5SDimitry Andric                   cl::desc("Reduce the number of instrumented blocks"),
1450b57cec5SDimitry Andric                   cl::Hidden, cl::init(true));
1460b57cec5SDimitry Andric 
1470b57cec5SDimitry Andric static cl::opt<bool> ClStackDepth("sanitizer-coverage-stack-depth",
1480b57cec5SDimitry Andric                                   cl::desc("max stack depth tracing"),
149*0fca6ea1SDimitry Andric                                   cl::Hidden);
1500b57cec5SDimitry Andric 
151bdd1243dSDimitry Andric static cl::opt<bool>
152bdd1243dSDimitry Andric     ClCollectCF("sanitizer-coverage-control-flow",
153*0fca6ea1SDimitry Andric                 cl::desc("collect control flow for each function"), cl::Hidden);
154bdd1243dSDimitry Andric 
1550b57cec5SDimitry Andric namespace {
1560b57cec5SDimitry Andric 
1570b57cec5SDimitry Andric SanitizerCoverageOptions getOptions(int LegacyCoverageLevel) {
1580b57cec5SDimitry Andric   SanitizerCoverageOptions Res;
1590b57cec5SDimitry Andric   switch (LegacyCoverageLevel) {
1600b57cec5SDimitry Andric   case 0:
1610b57cec5SDimitry Andric     Res.CoverageType = SanitizerCoverageOptions::SCK_None;
1620b57cec5SDimitry Andric     break;
1630b57cec5SDimitry Andric   case 1:
1640b57cec5SDimitry Andric     Res.CoverageType = SanitizerCoverageOptions::SCK_Function;
1650b57cec5SDimitry Andric     break;
1660b57cec5SDimitry Andric   case 2:
1670b57cec5SDimitry Andric     Res.CoverageType = SanitizerCoverageOptions::SCK_BB;
1680b57cec5SDimitry Andric     break;
1690b57cec5SDimitry Andric   case 3:
1700b57cec5SDimitry Andric     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
1710b57cec5SDimitry Andric     break;
1720b57cec5SDimitry Andric   case 4:
1730b57cec5SDimitry Andric     Res.CoverageType = SanitizerCoverageOptions::SCK_Edge;
1740b57cec5SDimitry Andric     Res.IndirectCalls = true;
1750b57cec5SDimitry Andric     break;
1760b57cec5SDimitry Andric   }
1770b57cec5SDimitry Andric   return Res;
1780b57cec5SDimitry Andric }
1790b57cec5SDimitry Andric 
1800b57cec5SDimitry Andric SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) {
1810b57cec5SDimitry Andric   // Sets CoverageType and IndirectCalls.
1820b57cec5SDimitry Andric   SanitizerCoverageOptions CLOpts = getOptions(ClCoverageLevel);
1830b57cec5SDimitry Andric   Options.CoverageType = std::max(Options.CoverageType, CLOpts.CoverageType);
1840b57cec5SDimitry Andric   Options.IndirectCalls |= CLOpts.IndirectCalls;
1850b57cec5SDimitry Andric   Options.TraceCmp |= ClCMPTracing;
1860b57cec5SDimitry Andric   Options.TraceDiv |= ClDIVTracing;
1870b57cec5SDimitry Andric   Options.TraceGep |= ClGEPTracing;
1880b57cec5SDimitry Andric   Options.TracePC |= ClTracePC;
1890b57cec5SDimitry Andric   Options.TracePCGuard |= ClTracePCGuard;
1900b57cec5SDimitry Andric   Options.Inline8bitCounters |= ClInline8bitCounters;
1915ffd83dbSDimitry Andric   Options.InlineBoolFlag |= ClInlineBoolFlag;
1920b57cec5SDimitry Andric   Options.PCTable |= ClCreatePCTable;
1930b57cec5SDimitry Andric   Options.NoPrune |= !ClPruneBlocks;
1940b57cec5SDimitry Andric   Options.StackDepth |= ClStackDepth;
195349cc55cSDimitry Andric   Options.TraceLoads |= ClLoadTracing;
196349cc55cSDimitry Andric   Options.TraceStores |= ClStoreTracing;
1970b57cec5SDimitry Andric   if (!Options.TracePCGuard && !Options.TracePC &&
1985ffd83dbSDimitry Andric       !Options.Inline8bitCounters && !Options.StackDepth &&
199349cc55cSDimitry Andric       !Options.InlineBoolFlag && !Options.TraceLoads && !Options.TraceStores)
2000b57cec5SDimitry Andric     Options.TracePCGuard = true; // TracePCGuard is default.
201bdd1243dSDimitry Andric   Options.CollectControlFlow |= ClCollectCF;
2020b57cec5SDimitry Andric   return Options;
2030b57cec5SDimitry Andric }
2040b57cec5SDimitry Andric 
2058bcb0991SDimitry Andric class ModuleSanitizerCoverage {
2068bcb0991SDimitry Andric public:
207*0fca6ea1SDimitry Andric   using DomTreeCallback = function_ref<const DominatorTree &(Function &F)>;
208*0fca6ea1SDimitry Andric   using PostDomTreeCallback =
209*0fca6ea1SDimitry Andric       function_ref<const PostDominatorTree &(Function &F)>;
210*0fca6ea1SDimitry Andric 
211*0fca6ea1SDimitry Andric   ModuleSanitizerCoverage(Module &M, DomTreeCallback DTCallback,
212*0fca6ea1SDimitry Andric                           PostDomTreeCallback PDTCallback,
213*0fca6ea1SDimitry Andric                           const SanitizerCoverageOptions &Options,
214*0fca6ea1SDimitry Andric                           const SpecialCaseList *Allowlist,
215*0fca6ea1SDimitry Andric                           const SpecialCaseList *Blocklist)
216*0fca6ea1SDimitry Andric       : M(M), DTCallback(DTCallback), PDTCallback(PDTCallback),
217*0fca6ea1SDimitry Andric         Options(Options), Allowlist(Allowlist), Blocklist(Blocklist) {}
218*0fca6ea1SDimitry Andric 
219*0fca6ea1SDimitry Andric   bool instrumentModule();
2200b57cec5SDimitry Andric 
2210b57cec5SDimitry Andric private:
222bdd1243dSDimitry Andric   void createFunctionControlFlow(Function &F);
223*0fca6ea1SDimitry Andric   void instrumentFunction(Function &F);
2240b57cec5SDimitry Andric   void InjectCoverageForIndirectCalls(Function &F,
2250b57cec5SDimitry Andric                                       ArrayRef<Instruction *> IndirCalls);
2260b57cec5SDimitry Andric   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
2270b57cec5SDimitry Andric   void InjectTraceForDiv(Function &F,
2280b57cec5SDimitry Andric                          ArrayRef<BinaryOperator *> DivTraceTargets);
2290b57cec5SDimitry Andric   void InjectTraceForGep(Function &F,
2300b57cec5SDimitry Andric                          ArrayRef<GetElementPtrInst *> GepTraceTargets);
231349cc55cSDimitry Andric   void InjectTraceForLoadsAndStores(Function &F, ArrayRef<LoadInst *> Loads,
232349cc55cSDimitry Andric                                     ArrayRef<StoreInst *> Stores);
2330b57cec5SDimitry Andric   void InjectTraceForSwitch(Function &F,
2340b57cec5SDimitry Andric                             ArrayRef<Instruction *> SwitchTraceTargets);
2350b57cec5SDimitry Andric   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks,
2360b57cec5SDimitry Andric                       bool IsLeafFunc = true);
2370b57cec5SDimitry Andric   GlobalVariable *CreateFunctionLocalArrayInSection(size_t NumElements,
2380b57cec5SDimitry Andric                                                     Function &F, Type *Ty,
2390b57cec5SDimitry Andric                                                     const char *Section);
2400b57cec5SDimitry Andric   GlobalVariable *CreatePCArray(Function &F, ArrayRef<BasicBlock *> AllBlocks);
2410b57cec5SDimitry Andric   void CreateFunctionLocalArrays(Function &F, ArrayRef<BasicBlock *> AllBlocks);
2420b57cec5SDimitry Andric   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, size_t Idx,
2430b57cec5SDimitry Andric                              bool IsLeafFunc = true);
2440b57cec5SDimitry Andric   Function *CreateInitCallsForSections(Module &M, const char *CtorName,
2450b57cec5SDimitry Andric                                        const char *InitFunctionName, Type *Ty,
2460b57cec5SDimitry Andric                                        const char *Section);
2470b57cec5SDimitry Andric   std::pair<Value *, Value *> CreateSecStartEnd(Module &M, const char *Section,
2480b57cec5SDimitry Andric                                                 Type *Ty);
2490b57cec5SDimitry Andric 
2500b57cec5SDimitry Andric   std::string getSectionName(const std::string &Section) const;
2510b57cec5SDimitry Andric   std::string getSectionStart(const std::string &Section) const;
2520b57cec5SDimitry Andric   std::string getSectionEnd(const std::string &Section) const;
253*0fca6ea1SDimitry Andric 
254*0fca6ea1SDimitry Andric   Module &M;
255*0fca6ea1SDimitry Andric   DomTreeCallback DTCallback;
256*0fca6ea1SDimitry Andric   PostDomTreeCallback PDTCallback;
257*0fca6ea1SDimitry Andric 
2580b57cec5SDimitry Andric   FunctionCallee SanCovTracePCIndir;
2590b57cec5SDimitry Andric   FunctionCallee SanCovTracePC, SanCovTracePCGuard;
260349cc55cSDimitry Andric   std::array<FunctionCallee, 4> SanCovTraceCmpFunction;
261349cc55cSDimitry Andric   std::array<FunctionCallee, 4> SanCovTraceConstCmpFunction;
262349cc55cSDimitry Andric   std::array<FunctionCallee, 5> SanCovLoadFunction;
263349cc55cSDimitry Andric   std::array<FunctionCallee, 5> SanCovStoreFunction;
264349cc55cSDimitry Andric   std::array<FunctionCallee, 2> SanCovTraceDivFunction;
2650b57cec5SDimitry Andric   FunctionCallee SanCovTraceGepFunction;
2660b57cec5SDimitry Andric   FunctionCallee SanCovTraceSwitchFunction;
2670b57cec5SDimitry Andric   GlobalVariable *SanCovLowestStack;
2685f757f3fSDimitry Andric   Type *PtrTy, *IntptrTy, *Int64Ty, *Int32Ty, *Int16Ty, *Int8Ty, *Int1Ty;
2690b57cec5SDimitry Andric   Module *CurModule;
2700b57cec5SDimitry Andric   std::string CurModuleUniqueId;
2710b57cec5SDimitry Andric   Triple TargetTriple;
2720b57cec5SDimitry Andric   LLVMContext *C;
2730b57cec5SDimitry Andric   const DataLayout *DL;
2740b57cec5SDimitry Andric 
2750b57cec5SDimitry Andric   GlobalVariable *FunctionGuardArray;  // for trace-pc-guard.
2760b57cec5SDimitry Andric   GlobalVariable *Function8bitCounterArray;  // for inline-8bit-counters.
2775ffd83dbSDimitry Andric   GlobalVariable *FunctionBoolArray;         // for inline-bool-flag.
2780b57cec5SDimitry Andric   GlobalVariable *FunctionPCsArray;  // for pc-table.
279bdd1243dSDimitry Andric   GlobalVariable *FunctionCFsArray;  // for control flow table
2800b57cec5SDimitry Andric   SmallVector<GlobalValue *, 20> GlobalsToAppendToUsed;
2810b57cec5SDimitry Andric   SmallVector<GlobalValue *, 20> GlobalsToAppendToCompilerUsed;
2820b57cec5SDimitry Andric 
2830b57cec5SDimitry Andric   SanitizerCoverageOptions Options;
2845ffd83dbSDimitry Andric 
2855ffd83dbSDimitry Andric   const SpecialCaseList *Allowlist;
2865ffd83dbSDimitry Andric   const SpecialCaseList *Blocklist;
2870b57cec5SDimitry Andric };
2880b57cec5SDimitry Andric } // namespace
2890b57cec5SDimitry Andric 
290bdd1243dSDimitry Andric PreservedAnalyses SanitizerCoveragePass::run(Module &M,
2918bcb0991SDimitry Andric                                              ModuleAnalysisManager &MAM) {
2928bcb0991SDimitry Andric   auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
293*0fca6ea1SDimitry Andric   auto DTCallback = [&FAM](Function &F) -> const DominatorTree & {
294*0fca6ea1SDimitry Andric     return FAM.getResult<DominatorTreeAnalysis>(F);
2958bcb0991SDimitry Andric   };
296*0fca6ea1SDimitry Andric   auto PDTCallback = [&FAM](Function &F) -> const PostDominatorTree & {
297*0fca6ea1SDimitry Andric     return FAM.getResult<PostDominatorTreeAnalysis>(F);
2988bcb0991SDimitry Andric   };
299*0fca6ea1SDimitry Andric   ModuleSanitizerCoverage ModuleSancov(M, DTCallback, PDTCallback,
300*0fca6ea1SDimitry Andric                                        OverrideFromCL(Options), Allowlist.get(),
301*0fca6ea1SDimitry Andric                                        Blocklist.get());
302*0fca6ea1SDimitry Andric   if (!ModuleSancov.instrumentModule())
3038bcb0991SDimitry Andric     return PreservedAnalyses::all();
304bdd1243dSDimitry Andric 
305bdd1243dSDimitry Andric   PreservedAnalyses PA = PreservedAnalyses::none();
306bdd1243dSDimitry Andric   // GlobalsAA is considered stateless and does not get invalidated unless
307bdd1243dSDimitry Andric   // explicitly invalidated; PreservedAnalyses::none() is not enough. Sanitizers
308bdd1243dSDimitry Andric   // make changes that require GlobalsAA to be invalidated.
309bdd1243dSDimitry Andric   PA.abandon<GlobalsAA>();
310bdd1243dSDimitry Andric   return PA;
3118bcb0991SDimitry Andric }
3128bcb0991SDimitry Andric 
3130b57cec5SDimitry Andric std::pair<Value *, Value *>
3148bcb0991SDimitry Andric ModuleSanitizerCoverage::CreateSecStartEnd(Module &M, const char *Section,
3150b57cec5SDimitry Andric                                            Type *Ty) {
316fe6060f1SDimitry Andric   // Use ExternalWeak so that if all sections are discarded due to section
317fe6060f1SDimitry Andric   // garbage collection, the linker will not report undefined symbol errors.
318fe6060f1SDimitry Andric   // Windows defines the start/stop symbols in compiler-rt so no need for
319fe6060f1SDimitry Andric   // ExternalWeak.
320fe6060f1SDimitry Andric   GlobalValue::LinkageTypes Linkage = TargetTriple.isOSBinFormatCOFF()
321fe6060f1SDimitry Andric                                           ? GlobalVariable::ExternalLinkage
322fe6060f1SDimitry Andric                                           : GlobalVariable::ExternalWeakLinkage;
323fe6060f1SDimitry Andric   GlobalVariable *SecStart =
324fe6060f1SDimitry Andric       new GlobalVariable(M, Ty, false, Linkage, nullptr,
325fe6060f1SDimitry Andric                          getSectionStart(Section));
3260b57cec5SDimitry Andric   SecStart->setVisibility(GlobalValue::HiddenVisibility);
327fe6060f1SDimitry Andric   GlobalVariable *SecEnd =
328fe6060f1SDimitry Andric       new GlobalVariable(M, Ty, false, Linkage, nullptr,
329fe6060f1SDimitry Andric                          getSectionEnd(Section));
3300b57cec5SDimitry Andric   SecEnd->setVisibility(GlobalValue::HiddenVisibility);
3310b57cec5SDimitry Andric   IRBuilder<> IRB(M.getContext());
3320b57cec5SDimitry Andric   if (!TargetTriple.isOSBinFormatCOFF())
333e8d8bef9SDimitry Andric     return std::make_pair(SecStart, SecEnd);
3340b57cec5SDimitry Andric 
3350b57cec5SDimitry Andric   // Account for the fact that on windows-msvc __start_* symbols actually
3360b57cec5SDimitry Andric   // point to a uint64_t before the start of the array.
3377a6dacacSDimitry Andric   auto GEP =
3387a6dacacSDimitry Andric       IRB.CreatePtrAdd(SecStart, ConstantInt::get(IntptrTy, sizeof(uint64_t)));
3395f757f3fSDimitry Andric   return std::make_pair(GEP, SecEnd);
3400b57cec5SDimitry Andric }
3410b57cec5SDimitry Andric 
3428bcb0991SDimitry Andric Function *ModuleSanitizerCoverage::CreateInitCallsForSections(
3430b57cec5SDimitry Andric     Module &M, const char *CtorName, const char *InitFunctionName, Type *Ty,
3440b57cec5SDimitry Andric     const char *Section) {
3450b57cec5SDimitry Andric   auto SecStartEnd = CreateSecStartEnd(M, Section, Ty);
3460b57cec5SDimitry Andric   auto SecStart = SecStartEnd.first;
3470b57cec5SDimitry Andric   auto SecEnd = SecStartEnd.second;
3480b57cec5SDimitry Andric   Function *CtorFunc;
3490b57cec5SDimitry Andric   std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
350fe6060f1SDimitry Andric       M, CtorName, InitFunctionName, {PtrTy, PtrTy}, {SecStart, SecEnd});
3510b57cec5SDimitry Andric   assert(CtorFunc->getName() == CtorName);
3520b57cec5SDimitry Andric 
3530b57cec5SDimitry Andric   if (TargetTriple.supportsCOMDAT()) {
3540b57cec5SDimitry Andric     // Use comdat to dedup CtorFunc.
3550b57cec5SDimitry Andric     CtorFunc->setComdat(M.getOrInsertComdat(CtorName));
3560b57cec5SDimitry Andric     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority, CtorFunc);
3570b57cec5SDimitry Andric   } else {
3580b57cec5SDimitry Andric     appendToGlobalCtors(M, CtorFunc, SanCtorAndDtorPriority);
3590b57cec5SDimitry Andric   }
3600b57cec5SDimitry Andric 
3610b57cec5SDimitry Andric   if (TargetTriple.isOSBinFormatCOFF()) {
3620b57cec5SDimitry Andric     // In COFF files, if the contructors are set as COMDAT (they are because
3630b57cec5SDimitry Andric     // COFF supports COMDAT) and the linker flag /OPT:REF (strip unreferenced
3640b57cec5SDimitry Andric     // functions and data) is used, the constructors get stripped. To prevent
3650b57cec5SDimitry Andric     // this, give the constructors weak ODR linkage and ensure the linker knows
3660b57cec5SDimitry Andric     // to include the sancov constructor. This way the linker can deduplicate
3670b57cec5SDimitry Andric     // the constructors but always leave one copy.
3680b57cec5SDimitry Andric     CtorFunc->setLinkage(GlobalValue::WeakODRLinkage);
3690b57cec5SDimitry Andric   }
3700b57cec5SDimitry Andric   return CtorFunc;
3710b57cec5SDimitry Andric }
3720b57cec5SDimitry Andric 
373*0fca6ea1SDimitry Andric bool ModuleSanitizerCoverage::instrumentModule() {
3740b57cec5SDimitry Andric   if (Options.CoverageType == SanitizerCoverageOptions::SCK_None)
3750b57cec5SDimitry Andric     return false;
3765ffd83dbSDimitry Andric   if (Allowlist &&
3775ffd83dbSDimitry Andric       !Allowlist->inSection("coverage", "src", M.getSourceFileName()))
3785ffd83dbSDimitry Andric     return false;
3795ffd83dbSDimitry Andric   if (Blocklist &&
3805ffd83dbSDimitry Andric       Blocklist->inSection("coverage", "src", M.getSourceFileName()))
3815ffd83dbSDimitry Andric     return false;
3820b57cec5SDimitry Andric   C = &(M.getContext());
3830b57cec5SDimitry Andric   DL = &M.getDataLayout();
3840b57cec5SDimitry Andric   CurModule = &M;
3850b57cec5SDimitry Andric   CurModuleUniqueId = getUniqueModuleId(CurModule);
3860b57cec5SDimitry Andric   TargetTriple = Triple(M.getTargetTriple());
3870b57cec5SDimitry Andric   FunctionGuardArray = nullptr;
3880b57cec5SDimitry Andric   Function8bitCounterArray = nullptr;
3895ffd83dbSDimitry Andric   FunctionBoolArray = nullptr;
3900b57cec5SDimitry Andric   FunctionPCsArray = nullptr;
391bdd1243dSDimitry Andric   FunctionCFsArray = nullptr;
3920b57cec5SDimitry Andric   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
3935f757f3fSDimitry Andric   PtrTy = PointerType::getUnqual(*C);
3940b57cec5SDimitry Andric   Type *VoidTy = Type::getVoidTy(*C);
3950b57cec5SDimitry Andric   IRBuilder<> IRB(*C);
3960b57cec5SDimitry Andric   Int64Ty = IRB.getInt64Ty();
3970b57cec5SDimitry Andric   Int32Ty = IRB.getInt32Ty();
3980b57cec5SDimitry Andric   Int16Ty = IRB.getInt16Ty();
3990b57cec5SDimitry Andric   Int8Ty = IRB.getInt8Ty();
4005ffd83dbSDimitry Andric   Int1Ty = IRB.getInt1Ty();
4010b57cec5SDimitry Andric 
4020b57cec5SDimitry Andric   SanCovTracePCIndir =
4030b57cec5SDimitry Andric       M.getOrInsertFunction(SanCovTracePCIndirName, VoidTy, IntptrTy);
404e8d8bef9SDimitry Andric   // Make sure smaller parameters are zero-extended to i64 if required by the
405e8d8bef9SDimitry Andric   // target ABI.
4060b57cec5SDimitry Andric   AttributeList SanCovTraceCmpZeroExtAL;
4070b57cec5SDimitry Andric   SanCovTraceCmpZeroExtAL =
4080b57cec5SDimitry Andric       SanCovTraceCmpZeroExtAL.addParamAttribute(*C, 0, Attribute::ZExt);
4090b57cec5SDimitry Andric   SanCovTraceCmpZeroExtAL =
4100b57cec5SDimitry Andric       SanCovTraceCmpZeroExtAL.addParamAttribute(*C, 1, Attribute::ZExt);
4110b57cec5SDimitry Andric 
4120b57cec5SDimitry Andric   SanCovTraceCmpFunction[0] =
4130b57cec5SDimitry Andric       M.getOrInsertFunction(SanCovTraceCmp1, SanCovTraceCmpZeroExtAL, VoidTy,
4140b57cec5SDimitry Andric                             IRB.getInt8Ty(), IRB.getInt8Ty());
4150b57cec5SDimitry Andric   SanCovTraceCmpFunction[1] =
4160b57cec5SDimitry Andric       M.getOrInsertFunction(SanCovTraceCmp2, SanCovTraceCmpZeroExtAL, VoidTy,
4170b57cec5SDimitry Andric                             IRB.getInt16Ty(), IRB.getInt16Ty());
4180b57cec5SDimitry Andric   SanCovTraceCmpFunction[2] =
4190b57cec5SDimitry Andric       M.getOrInsertFunction(SanCovTraceCmp4, SanCovTraceCmpZeroExtAL, VoidTy,
4200b57cec5SDimitry Andric                             IRB.getInt32Ty(), IRB.getInt32Ty());
4210b57cec5SDimitry Andric   SanCovTraceCmpFunction[3] =
4220b57cec5SDimitry Andric       M.getOrInsertFunction(SanCovTraceCmp8, VoidTy, Int64Ty, Int64Ty);
4230b57cec5SDimitry Andric 
4240b57cec5SDimitry Andric   SanCovTraceConstCmpFunction[0] = M.getOrInsertFunction(
4250b57cec5SDimitry Andric       SanCovTraceConstCmp1, SanCovTraceCmpZeroExtAL, VoidTy, Int8Ty, Int8Ty);
4260b57cec5SDimitry Andric   SanCovTraceConstCmpFunction[1] = M.getOrInsertFunction(
4270b57cec5SDimitry Andric       SanCovTraceConstCmp2, SanCovTraceCmpZeroExtAL, VoidTy, Int16Ty, Int16Ty);
4280b57cec5SDimitry Andric   SanCovTraceConstCmpFunction[2] = M.getOrInsertFunction(
4290b57cec5SDimitry Andric       SanCovTraceConstCmp4, SanCovTraceCmpZeroExtAL, VoidTy, Int32Ty, Int32Ty);
4300b57cec5SDimitry Andric   SanCovTraceConstCmpFunction[3] =
4310b57cec5SDimitry Andric       M.getOrInsertFunction(SanCovTraceConstCmp8, VoidTy, Int64Ty, Int64Ty);
4320b57cec5SDimitry Andric 
433349cc55cSDimitry Andric   // Loads.
4345f757f3fSDimitry Andric   SanCovLoadFunction[0] = M.getOrInsertFunction(SanCovLoad1, VoidTy, PtrTy);
435349cc55cSDimitry Andric   SanCovLoadFunction[1] =
4365f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovLoad2, VoidTy, PtrTy);
437349cc55cSDimitry Andric   SanCovLoadFunction[2] =
4385f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovLoad4, VoidTy, PtrTy);
439349cc55cSDimitry Andric   SanCovLoadFunction[3] =
4405f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovLoad8, VoidTy, PtrTy);
441349cc55cSDimitry Andric   SanCovLoadFunction[4] =
4425f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovLoad16, VoidTy, PtrTy);
443349cc55cSDimitry Andric   // Stores.
444349cc55cSDimitry Andric   SanCovStoreFunction[0] =
4455f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovStore1, VoidTy, PtrTy);
446349cc55cSDimitry Andric   SanCovStoreFunction[1] =
4475f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovStore2, VoidTy, PtrTy);
448349cc55cSDimitry Andric   SanCovStoreFunction[2] =
4495f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovStore4, VoidTy, PtrTy);
450349cc55cSDimitry Andric   SanCovStoreFunction[3] =
4515f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovStore8, VoidTy, PtrTy);
452349cc55cSDimitry Andric   SanCovStoreFunction[4] =
4535f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovStore16, VoidTy, PtrTy);
454349cc55cSDimitry Andric 
4550b57cec5SDimitry Andric   {
4560b57cec5SDimitry Andric     AttributeList AL;
4570b57cec5SDimitry Andric     AL = AL.addParamAttribute(*C, 0, Attribute::ZExt);
4580b57cec5SDimitry Andric     SanCovTraceDivFunction[0] =
4590b57cec5SDimitry Andric         M.getOrInsertFunction(SanCovTraceDiv4, AL, VoidTy, IRB.getInt32Ty());
4600b57cec5SDimitry Andric   }
4610b57cec5SDimitry Andric   SanCovTraceDivFunction[1] =
4620b57cec5SDimitry Andric       M.getOrInsertFunction(SanCovTraceDiv8, VoidTy, Int64Ty);
4630b57cec5SDimitry Andric   SanCovTraceGepFunction =
4640b57cec5SDimitry Andric       M.getOrInsertFunction(SanCovTraceGep, VoidTy, IntptrTy);
4650b57cec5SDimitry Andric   SanCovTraceSwitchFunction =
4665f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovTraceSwitchName, VoidTy, Int64Ty, PtrTy);
4670b57cec5SDimitry Andric 
4680b57cec5SDimitry Andric   Constant *SanCovLowestStackConstant =
4690b57cec5SDimitry Andric       M.getOrInsertGlobal(SanCovLowestStackName, IntptrTy);
4700b57cec5SDimitry Andric   SanCovLowestStack = dyn_cast<GlobalVariable>(SanCovLowestStackConstant);
471fe6060f1SDimitry Andric   if (!SanCovLowestStack || SanCovLowestStack->getValueType() != IntptrTy) {
4720b57cec5SDimitry Andric     C->emitError(StringRef("'") + SanCovLowestStackName +
4730b57cec5SDimitry Andric                  "' should not be declared by the user");
4740b57cec5SDimitry Andric     return true;
4750b57cec5SDimitry Andric   }
4760b57cec5SDimitry Andric   SanCovLowestStack->setThreadLocalMode(
4770b57cec5SDimitry Andric       GlobalValue::ThreadLocalMode::InitialExecTLSModel);
4780b57cec5SDimitry Andric   if (Options.StackDepth && !SanCovLowestStack->isDeclaration())
4790b57cec5SDimitry Andric     SanCovLowestStack->setInitializer(Constant::getAllOnesValue(IntptrTy));
4800b57cec5SDimitry Andric 
4810b57cec5SDimitry Andric   SanCovTracePC = M.getOrInsertFunction(SanCovTracePCName, VoidTy);
4820b57cec5SDimitry Andric   SanCovTracePCGuard =
4835f757f3fSDimitry Andric       M.getOrInsertFunction(SanCovTracePCGuardName, VoidTy, PtrTy);
4840b57cec5SDimitry Andric 
4850b57cec5SDimitry Andric   for (auto &F : M)
486*0fca6ea1SDimitry Andric     instrumentFunction(F);
4870b57cec5SDimitry Andric 
4880b57cec5SDimitry Andric   Function *Ctor = nullptr;
4890b57cec5SDimitry Andric 
4900b57cec5SDimitry Andric   if (FunctionGuardArray)
4910b57cec5SDimitry Andric     Ctor = CreateInitCallsForSections(M, SanCovModuleCtorTracePcGuardName,
492fe6060f1SDimitry Andric                                       SanCovTracePCGuardInitName, Int32Ty,
4930b57cec5SDimitry Andric                                       SanCovGuardsSectionName);
4940b57cec5SDimitry Andric   if (Function8bitCounterArray)
4950b57cec5SDimitry Andric     Ctor = CreateInitCallsForSections(M, SanCovModuleCtor8bitCountersName,
496fe6060f1SDimitry Andric                                       SanCov8bitCountersInitName, Int8Ty,
4970b57cec5SDimitry Andric                                       SanCovCountersSectionName);
4985ffd83dbSDimitry Andric   if (FunctionBoolArray) {
4995ffd83dbSDimitry Andric     Ctor = CreateInitCallsForSections(M, SanCovModuleCtorBoolFlagName,
500fe6060f1SDimitry Andric                                       SanCovBoolFlagInitName, Int1Ty,
5015ffd83dbSDimitry Andric                                       SanCovBoolFlagSectionName);
5025ffd83dbSDimitry Andric   }
5030b57cec5SDimitry Andric   if (Ctor && Options.PCTable) {
504fe6060f1SDimitry Andric     auto SecStartEnd = CreateSecStartEnd(M, SanCovPCsSectionName, IntptrTy);
5050b57cec5SDimitry Andric     FunctionCallee InitFunction = declareSanitizerInitFunction(
5065f757f3fSDimitry Andric         M, SanCovPCsInitName, {PtrTy, PtrTy});
5070b57cec5SDimitry Andric     IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
5080b57cec5SDimitry Andric     IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second});
5090b57cec5SDimitry Andric   }
510bdd1243dSDimitry Andric 
511bdd1243dSDimitry Andric   if (Ctor && Options.CollectControlFlow) {
512bdd1243dSDimitry Andric     auto SecStartEnd = CreateSecStartEnd(M, SanCovCFsSectionName, IntptrTy);
513bdd1243dSDimitry Andric     FunctionCallee InitFunction = declareSanitizerInitFunction(
5145f757f3fSDimitry Andric         M, SanCovCFsInitName, {PtrTy, PtrTy});
515bdd1243dSDimitry Andric     IRBuilder<> IRBCtor(Ctor->getEntryBlock().getTerminator());
516bdd1243dSDimitry Andric     IRBCtor.CreateCall(InitFunction, {SecStartEnd.first, SecStartEnd.second});
517bdd1243dSDimitry Andric   }
518bdd1243dSDimitry Andric 
5190b57cec5SDimitry Andric   appendToUsed(M, GlobalsToAppendToUsed);
5200b57cec5SDimitry Andric   appendToCompilerUsed(M, GlobalsToAppendToCompilerUsed);
5210b57cec5SDimitry Andric   return true;
5220b57cec5SDimitry Andric }
5230b57cec5SDimitry Andric 
5240b57cec5SDimitry Andric // True if block has successors and it dominates all of them.
525*0fca6ea1SDimitry Andric static bool isFullDominator(const BasicBlock *BB, const DominatorTree &DT) {
526e8d8bef9SDimitry Andric   if (succ_empty(BB))
5270b57cec5SDimitry Andric     return false;
5280b57cec5SDimitry Andric 
529e8d8bef9SDimitry Andric   return llvm::all_of(successors(BB), [&](const BasicBlock *SUCC) {
530*0fca6ea1SDimitry Andric     return DT.dominates(BB, SUCC);
531e8d8bef9SDimitry Andric   });
5320b57cec5SDimitry Andric }
5330b57cec5SDimitry Andric 
5340b57cec5SDimitry Andric // True if block has predecessors and it postdominates all of them.
5350b57cec5SDimitry Andric static bool isFullPostDominator(const BasicBlock *BB,
536*0fca6ea1SDimitry Andric                                 const PostDominatorTree &PDT) {
537e8d8bef9SDimitry Andric   if (pred_empty(BB))
5380b57cec5SDimitry Andric     return false;
5390b57cec5SDimitry Andric 
540e8d8bef9SDimitry Andric   return llvm::all_of(predecessors(BB), [&](const BasicBlock *PRED) {
541*0fca6ea1SDimitry Andric     return PDT.dominates(BB, PRED);
542e8d8bef9SDimitry Andric   });
5430b57cec5SDimitry Andric }
5440b57cec5SDimitry Andric 
5450b57cec5SDimitry Andric static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB,
546*0fca6ea1SDimitry Andric                                   const DominatorTree &DT,
547*0fca6ea1SDimitry Andric                                   const PostDominatorTree &PDT,
5480b57cec5SDimitry Andric                                   const SanitizerCoverageOptions &Options) {
5490b57cec5SDimitry Andric   // Don't insert coverage for blocks containing nothing but unreachable: we
5500b57cec5SDimitry Andric   // will never call __sanitizer_cov() for them, so counting them in
5510b57cec5SDimitry Andric   // NumberOfInstrumentedBlocks() might complicate calculation of code coverage
5520b57cec5SDimitry Andric   // percentage. Also, unreachable instructions frequently have no debug
5530b57cec5SDimitry Andric   // locations.
5540b57cec5SDimitry Andric   if (isa<UnreachableInst>(BB->getFirstNonPHIOrDbgOrLifetime()))
5550b57cec5SDimitry Andric     return false;
5560b57cec5SDimitry Andric 
5570b57cec5SDimitry Andric   // Don't insert coverage into blocks without a valid insertion point
5580b57cec5SDimitry Andric   // (catchswitch blocks).
5590b57cec5SDimitry Andric   if (BB->getFirstInsertionPt() == BB->end())
5600b57cec5SDimitry Andric     return false;
5610b57cec5SDimitry Andric 
5620b57cec5SDimitry Andric   if (Options.NoPrune || &F.getEntryBlock() == BB)
5630b57cec5SDimitry Andric     return true;
5640b57cec5SDimitry Andric 
5650b57cec5SDimitry Andric   if (Options.CoverageType == SanitizerCoverageOptions::SCK_Function &&
5660b57cec5SDimitry Andric       &F.getEntryBlock() != BB)
5670b57cec5SDimitry Andric     return false;
5680b57cec5SDimitry Andric 
5690b57cec5SDimitry Andric   // Do not instrument full dominators, or full post-dominators with multiple
5700b57cec5SDimitry Andric   // predecessors.
5710b57cec5SDimitry Andric   return !isFullDominator(BB, DT)
5720b57cec5SDimitry Andric     && !(isFullPostDominator(BB, PDT) && !BB->getSinglePredecessor());
5730b57cec5SDimitry Andric }
5740b57cec5SDimitry Andric 
5750b57cec5SDimitry Andric // Returns true iff From->To is a backedge.
5760b57cec5SDimitry Andric // A twist here is that we treat From->To as a backedge if
5770b57cec5SDimitry Andric //   * To dominates From or
5780b57cec5SDimitry Andric //   * To->UniqueSuccessor dominates From
5790b57cec5SDimitry Andric static bool IsBackEdge(BasicBlock *From, BasicBlock *To,
580*0fca6ea1SDimitry Andric                        const DominatorTree &DT) {
581*0fca6ea1SDimitry Andric   if (DT.dominates(To, From))
5820b57cec5SDimitry Andric     return true;
5830b57cec5SDimitry Andric   if (auto Next = To->getUniqueSuccessor())
584*0fca6ea1SDimitry Andric     if (DT.dominates(Next, From))
5850b57cec5SDimitry Andric       return true;
5860b57cec5SDimitry Andric   return false;
5870b57cec5SDimitry Andric }
5880b57cec5SDimitry Andric 
5890b57cec5SDimitry Andric // Prunes uninteresting Cmp instrumentation:
5900b57cec5SDimitry Andric //   * CMP instructions that feed into loop backedge branch.
5910b57cec5SDimitry Andric //
5920b57cec5SDimitry Andric // Note that Cmp pruning is controlled by the same flag as the
5930b57cec5SDimitry Andric // BB pruning.
594*0fca6ea1SDimitry Andric static bool IsInterestingCmp(ICmpInst *CMP, const DominatorTree &DT,
5950b57cec5SDimitry Andric                              const SanitizerCoverageOptions &Options) {
5960b57cec5SDimitry Andric   if (!Options.NoPrune)
5970b57cec5SDimitry Andric     if (CMP->hasOneUse())
5980b57cec5SDimitry Andric       if (auto BR = dyn_cast<BranchInst>(CMP->user_back()))
5990b57cec5SDimitry Andric         for (BasicBlock *B : BR->successors())
6000b57cec5SDimitry Andric           if (IsBackEdge(BR->getParent(), B, DT))
6010b57cec5SDimitry Andric             return false;
6020b57cec5SDimitry Andric   return true;
6030b57cec5SDimitry Andric }
6040b57cec5SDimitry Andric 
605*0fca6ea1SDimitry Andric void ModuleSanitizerCoverage::instrumentFunction(Function &F) {
6060b57cec5SDimitry Andric   if (F.empty())
6078bcb0991SDimitry Andric     return;
608cb14a3feSDimitry Andric   if (F.getName().contains(".module_ctor"))
6098bcb0991SDimitry Andric     return; // Should not instrument sanitizer init functions.
6105f757f3fSDimitry Andric   if (F.getName().starts_with("__sanitizer_"))
6118bcb0991SDimitry Andric     return; // Don't instrument __sanitizer_* callbacks.
6120b57cec5SDimitry Andric   // Don't touch available_externally functions, their actual body is elewhere.
6130b57cec5SDimitry Andric   if (F.getLinkage() == GlobalValue::AvailableExternallyLinkage)
6148bcb0991SDimitry Andric     return;
6150b57cec5SDimitry Andric   // Don't instrument MSVC CRT configuration helpers. They may run before normal
6160b57cec5SDimitry Andric   // initialization.
6170b57cec5SDimitry Andric   if (F.getName() == "__local_stdio_printf_options" ||
6180b57cec5SDimitry Andric       F.getName() == "__local_stdio_scanf_options")
6198bcb0991SDimitry Andric     return;
6200b57cec5SDimitry Andric   if (isa<UnreachableInst>(F.getEntryBlock().getTerminator()))
6218bcb0991SDimitry Andric     return;
6220b57cec5SDimitry Andric   // Don't instrument functions using SEH for now. Splitting basic blocks like
6230b57cec5SDimitry Andric   // we do for coverage breaks WinEHPrepare.
6240b57cec5SDimitry Andric   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
6250b57cec5SDimitry Andric   if (F.hasPersonalityFn() &&
6260b57cec5SDimitry Andric       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
6278bcb0991SDimitry Andric     return;
6285ffd83dbSDimitry Andric   if (Allowlist && !Allowlist->inSection("coverage", "fun", F.getName()))
6295ffd83dbSDimitry Andric     return;
6305ffd83dbSDimitry Andric   if (Blocklist && Blocklist->inSection("coverage", "fun", F.getName()))
6315ffd83dbSDimitry Andric     return;
632fe6060f1SDimitry Andric   if (F.hasFnAttribute(Attribute::NoSanitizeCoverage))
633fe6060f1SDimitry Andric     return;
634*0fca6ea1SDimitry Andric   if (F.hasFnAttribute(Attribute::DisableSanitizerInstrumentation))
635*0fca6ea1SDimitry Andric     return;
636*0fca6ea1SDimitry Andric   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge) {
637*0fca6ea1SDimitry Andric     SplitAllCriticalEdges(
638*0fca6ea1SDimitry Andric         F, CriticalEdgeSplittingOptions().setIgnoreUnreachableDests());
639*0fca6ea1SDimitry Andric   }
6400b57cec5SDimitry Andric   SmallVector<Instruction *, 8> IndirCalls;
6410b57cec5SDimitry Andric   SmallVector<BasicBlock *, 16> BlocksToInstrument;
6420b57cec5SDimitry Andric   SmallVector<Instruction *, 8> CmpTraceTargets;
6430b57cec5SDimitry Andric   SmallVector<Instruction *, 8> SwitchTraceTargets;
6440b57cec5SDimitry Andric   SmallVector<BinaryOperator *, 8> DivTraceTargets;
6450b57cec5SDimitry Andric   SmallVector<GetElementPtrInst *, 8> GepTraceTargets;
646349cc55cSDimitry Andric   SmallVector<LoadInst *, 8> Loads;
647349cc55cSDimitry Andric   SmallVector<StoreInst *, 8> Stores;
6480b57cec5SDimitry Andric 
649*0fca6ea1SDimitry Andric   const DominatorTree &DT = DTCallback(F);
650*0fca6ea1SDimitry Andric   const PostDominatorTree &PDT = PDTCallback(F);
6510b57cec5SDimitry Andric   bool IsLeafFunc = true;
6520b57cec5SDimitry Andric 
6530b57cec5SDimitry Andric   for (auto &BB : F) {
6540b57cec5SDimitry Andric     if (shouldInstrumentBlock(F, &BB, DT, PDT, Options))
6550b57cec5SDimitry Andric       BlocksToInstrument.push_back(&BB);
6560b57cec5SDimitry Andric     for (auto &Inst : BB) {
6570b57cec5SDimitry Andric       if (Options.IndirectCalls) {
6585ffd83dbSDimitry Andric         CallBase *CB = dyn_cast<CallBase>(&Inst);
65981ad6265SDimitry Andric         if (CB && CB->isIndirectCall())
6600b57cec5SDimitry Andric           IndirCalls.push_back(&Inst);
6610b57cec5SDimitry Andric       }
6620b57cec5SDimitry Andric       if (Options.TraceCmp) {
6630b57cec5SDimitry Andric         if (ICmpInst *CMP = dyn_cast<ICmpInst>(&Inst))
6640b57cec5SDimitry Andric           if (IsInterestingCmp(CMP, DT, Options))
6650b57cec5SDimitry Andric             CmpTraceTargets.push_back(&Inst);
6660b57cec5SDimitry Andric         if (isa<SwitchInst>(&Inst))
6670b57cec5SDimitry Andric           SwitchTraceTargets.push_back(&Inst);
6680b57cec5SDimitry Andric       }
6690b57cec5SDimitry Andric       if (Options.TraceDiv)
6700b57cec5SDimitry Andric         if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&Inst))
6710b57cec5SDimitry Andric           if (BO->getOpcode() == Instruction::SDiv ||
6720b57cec5SDimitry Andric               BO->getOpcode() == Instruction::UDiv)
6730b57cec5SDimitry Andric             DivTraceTargets.push_back(BO);
6740b57cec5SDimitry Andric       if (Options.TraceGep)
6750b57cec5SDimitry Andric         if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Inst))
6760b57cec5SDimitry Andric           GepTraceTargets.push_back(GEP);
677349cc55cSDimitry Andric       if (Options.TraceLoads)
678349cc55cSDimitry Andric         if (LoadInst *LI = dyn_cast<LoadInst>(&Inst))
679349cc55cSDimitry Andric           Loads.push_back(LI);
680349cc55cSDimitry Andric       if (Options.TraceStores)
681349cc55cSDimitry Andric         if (StoreInst *SI = dyn_cast<StoreInst>(&Inst))
682349cc55cSDimitry Andric           Stores.push_back(SI);
6830b57cec5SDimitry Andric       if (Options.StackDepth)
6840b57cec5SDimitry Andric         if (isa<InvokeInst>(Inst) ||
6850b57cec5SDimitry Andric             (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst)))
6860b57cec5SDimitry Andric           IsLeafFunc = false;
6870b57cec5SDimitry Andric     }
6880b57cec5SDimitry Andric   }
6890b57cec5SDimitry Andric 
690bdd1243dSDimitry Andric   if (Options.CollectControlFlow)
691bdd1243dSDimitry Andric     createFunctionControlFlow(F);
692bdd1243dSDimitry Andric 
6930b57cec5SDimitry Andric   InjectCoverage(F, BlocksToInstrument, IsLeafFunc);
6940b57cec5SDimitry Andric   InjectCoverageForIndirectCalls(F, IndirCalls);
6950b57cec5SDimitry Andric   InjectTraceForCmp(F, CmpTraceTargets);
6960b57cec5SDimitry Andric   InjectTraceForSwitch(F, SwitchTraceTargets);
6970b57cec5SDimitry Andric   InjectTraceForDiv(F, DivTraceTargets);
6980b57cec5SDimitry Andric   InjectTraceForGep(F, GepTraceTargets);
699349cc55cSDimitry Andric   InjectTraceForLoadsAndStores(F, Loads, Stores);
7000b57cec5SDimitry Andric }
7010b57cec5SDimitry Andric 
7028bcb0991SDimitry Andric GlobalVariable *ModuleSanitizerCoverage::CreateFunctionLocalArrayInSection(
7030b57cec5SDimitry Andric     size_t NumElements, Function &F, Type *Ty, const char *Section) {
7040b57cec5SDimitry Andric   ArrayType *ArrayTy = ArrayType::get(Ty, NumElements);
7050b57cec5SDimitry Andric   auto Array = new GlobalVariable(
7060b57cec5SDimitry Andric       *CurModule, ArrayTy, false, GlobalVariable::PrivateLinkage,
7070b57cec5SDimitry Andric       Constant::getNullValue(ArrayTy), "__sancov_gen_");
7080b57cec5SDimitry Andric 
709fe6060f1SDimitry Andric   if (TargetTriple.supportsCOMDAT() &&
710fe6060f1SDimitry Andric       (TargetTriple.isOSBinFormatELF() || !F.isInterposable()))
711fe6060f1SDimitry Andric     if (auto Comdat = getOrCreateFunctionComdat(F, TargetTriple))
7120b57cec5SDimitry Andric       Array->setComdat(Comdat);
7130b57cec5SDimitry Andric   Array->setSection(getSectionName(Section));
714bdd1243dSDimitry Andric   Array->setAlignment(Align(DL->getTypeStoreSize(Ty).getFixedValue()));
715fe6060f1SDimitry Andric 
716fe6060f1SDimitry Andric   // sancov_pcs parallels the other metadata section(s). Optimizers (e.g.
717fe6060f1SDimitry Andric   // GlobalOpt/ConstantMerge) may not discard sancov_pcs and the other
718fe6060f1SDimitry Andric   // section(s) as a unit, so we conservatively retain all unconditionally in
719fe6060f1SDimitry Andric   // the compiler.
720fe6060f1SDimitry Andric   //
721fe6060f1SDimitry Andric   // With comdat (COFF/ELF), the linker can guarantee the associated sections
722fe6060f1SDimitry Andric   // will be retained or discarded as a unit, so llvm.compiler.used is
723fe6060f1SDimitry Andric   // sufficient. Otherwise, conservatively make all of them retained by the
724fe6060f1SDimitry Andric   // linker.
725fe6060f1SDimitry Andric   if (Array->hasComdat())
7260b57cec5SDimitry Andric     GlobalsToAppendToCompilerUsed.push_back(Array);
727fe6060f1SDimitry Andric   else
728fe6060f1SDimitry Andric     GlobalsToAppendToUsed.push_back(Array);
7290b57cec5SDimitry Andric 
7300b57cec5SDimitry Andric   return Array;
7310b57cec5SDimitry Andric }
7320b57cec5SDimitry Andric 
7330b57cec5SDimitry Andric GlobalVariable *
7348bcb0991SDimitry Andric ModuleSanitizerCoverage::CreatePCArray(Function &F,
7350b57cec5SDimitry Andric                                        ArrayRef<BasicBlock *> AllBlocks) {
7360b57cec5SDimitry Andric   size_t N = AllBlocks.size();
7370b57cec5SDimitry Andric   assert(N);
7380b57cec5SDimitry Andric   SmallVector<Constant *, 32> PCs;
7390b57cec5SDimitry Andric   IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
7400b57cec5SDimitry Andric   for (size_t i = 0; i < N; i++) {
7410b57cec5SDimitry Andric     if (&F.getEntryBlock() == AllBlocks[i]) {
7425f757f3fSDimitry Andric       PCs.push_back((Constant *)IRB.CreatePointerCast(&F, PtrTy));
7430b57cec5SDimitry Andric       PCs.push_back((Constant *)IRB.CreateIntToPtr(
7445f757f3fSDimitry Andric           ConstantInt::get(IntptrTy, 1), PtrTy));
7450b57cec5SDimitry Andric     } else {
7460b57cec5SDimitry Andric       PCs.push_back((Constant *)IRB.CreatePointerCast(
7475f757f3fSDimitry Andric           BlockAddress::get(AllBlocks[i]), PtrTy));
7485f757f3fSDimitry Andric       PCs.push_back(Constant::getNullValue(PtrTy));
7490b57cec5SDimitry Andric     }
7500b57cec5SDimitry Andric   }
7515f757f3fSDimitry Andric   auto *PCArray = CreateFunctionLocalArrayInSection(N * 2, F, PtrTy,
7520b57cec5SDimitry Andric                                                     SanCovPCsSectionName);
7530b57cec5SDimitry Andric   PCArray->setInitializer(
7545f757f3fSDimitry Andric       ConstantArray::get(ArrayType::get(PtrTy, N * 2), PCs));
7550b57cec5SDimitry Andric   PCArray->setConstant(true);
7560b57cec5SDimitry Andric 
7570b57cec5SDimitry Andric   return PCArray;
7580b57cec5SDimitry Andric }
7590b57cec5SDimitry Andric 
7608bcb0991SDimitry Andric void ModuleSanitizerCoverage::CreateFunctionLocalArrays(
7610b57cec5SDimitry Andric     Function &F, ArrayRef<BasicBlock *> AllBlocks) {
7620b57cec5SDimitry Andric   if (Options.TracePCGuard)
7630b57cec5SDimitry Andric     FunctionGuardArray = CreateFunctionLocalArrayInSection(
7640b57cec5SDimitry Andric         AllBlocks.size(), F, Int32Ty, SanCovGuardsSectionName);
7650b57cec5SDimitry Andric 
7660b57cec5SDimitry Andric   if (Options.Inline8bitCounters)
7670b57cec5SDimitry Andric     Function8bitCounterArray = CreateFunctionLocalArrayInSection(
7680b57cec5SDimitry Andric         AllBlocks.size(), F, Int8Ty, SanCovCountersSectionName);
7695ffd83dbSDimitry Andric   if (Options.InlineBoolFlag)
7705ffd83dbSDimitry Andric     FunctionBoolArray = CreateFunctionLocalArrayInSection(
7715ffd83dbSDimitry Andric         AllBlocks.size(), F, Int1Ty, SanCovBoolFlagSectionName);
7720b57cec5SDimitry Andric 
7730b57cec5SDimitry Andric   if (Options.PCTable)
7740b57cec5SDimitry Andric     FunctionPCsArray = CreatePCArray(F, AllBlocks);
7750b57cec5SDimitry Andric }
7760b57cec5SDimitry Andric 
7778bcb0991SDimitry Andric bool ModuleSanitizerCoverage::InjectCoverage(Function &F,
7780b57cec5SDimitry Andric                                              ArrayRef<BasicBlock *> AllBlocks,
7790b57cec5SDimitry Andric                                              bool IsLeafFunc) {
7800b57cec5SDimitry Andric   if (AllBlocks.empty()) return false;
7810b57cec5SDimitry Andric   CreateFunctionLocalArrays(F, AllBlocks);
7820b57cec5SDimitry Andric   for (size_t i = 0, N = AllBlocks.size(); i < N; i++)
7830b57cec5SDimitry Andric     InjectCoverageAtBlock(F, *AllBlocks[i], i, IsLeafFunc);
7840b57cec5SDimitry Andric   return true;
7850b57cec5SDimitry Andric }
7860b57cec5SDimitry Andric 
7870b57cec5SDimitry Andric // On every indirect call we call a run-time function
7880b57cec5SDimitry Andric // __sanitizer_cov_indir_call* with two parameters:
7890b57cec5SDimitry Andric //   - callee address,
7900b57cec5SDimitry Andric //   - global cache array that contains CacheSize pointers (zero-initialized).
7910b57cec5SDimitry Andric //     The cache is used to speed up recording the caller-callee pairs.
7920b57cec5SDimitry Andric // The address of the caller is passed implicitly via caller PC.
7930b57cec5SDimitry Andric // CacheSize is encoded in the name of the run-time function.
7948bcb0991SDimitry Andric void ModuleSanitizerCoverage::InjectCoverageForIndirectCalls(
7950b57cec5SDimitry Andric     Function &F, ArrayRef<Instruction *> IndirCalls) {
7960b57cec5SDimitry Andric   if (IndirCalls.empty())
7970b57cec5SDimitry Andric     return;
7985ffd83dbSDimitry Andric   assert(Options.TracePC || Options.TracePCGuard ||
7995ffd83dbSDimitry Andric          Options.Inline8bitCounters || Options.InlineBoolFlag);
800bdd1243dSDimitry Andric   for (auto *I : IndirCalls) {
80106c3fb27SDimitry Andric     InstrumentationIRBuilder IRB(I);
8025ffd83dbSDimitry Andric     CallBase &CB = cast<CallBase>(*I);
8035ffd83dbSDimitry Andric     Value *Callee = CB.getCalledOperand();
8040b57cec5SDimitry Andric     if (isa<InlineAsm>(Callee))
8050b57cec5SDimitry Andric       continue;
8060b57cec5SDimitry Andric     IRB.CreateCall(SanCovTracePCIndir, IRB.CreatePointerCast(Callee, IntptrTy));
8070b57cec5SDimitry Andric   }
8080b57cec5SDimitry Andric }
8090b57cec5SDimitry Andric 
8100b57cec5SDimitry Andric // For every switch statement we insert a call:
8110b57cec5SDimitry Andric // __sanitizer_cov_trace_switch(CondValue,
8120b57cec5SDimitry Andric //      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
8130b57cec5SDimitry Andric 
8148bcb0991SDimitry Andric void ModuleSanitizerCoverage::InjectTraceForSwitch(
8150b57cec5SDimitry Andric     Function &, ArrayRef<Instruction *> SwitchTraceTargets) {
816bdd1243dSDimitry Andric   for (auto *I : SwitchTraceTargets) {
8170b57cec5SDimitry Andric     if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
81806c3fb27SDimitry Andric       InstrumentationIRBuilder IRB(I);
8190b57cec5SDimitry Andric       SmallVector<Constant *, 16> Initializers;
8200b57cec5SDimitry Andric       Value *Cond = SI->getCondition();
8210b57cec5SDimitry Andric       if (Cond->getType()->getScalarSizeInBits() >
8220b57cec5SDimitry Andric           Int64Ty->getScalarSizeInBits())
8230b57cec5SDimitry Andric         continue;
8240b57cec5SDimitry Andric       Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
8250b57cec5SDimitry Andric       Initializers.push_back(
8260b57cec5SDimitry Andric           ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
8270b57cec5SDimitry Andric       if (Cond->getType()->getScalarSizeInBits() <
8280b57cec5SDimitry Andric           Int64Ty->getScalarSizeInBits())
8290b57cec5SDimitry Andric         Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
8300b57cec5SDimitry Andric       for (auto It : SI->cases()) {
8315f757f3fSDimitry Andric         ConstantInt *C = It.getCaseValue();
8325f757f3fSDimitry Andric         if (C->getType()->getScalarSizeInBits() < 64)
8335f757f3fSDimitry Andric           C = ConstantInt::get(C->getContext(), C->getValue().zext(64));
8340b57cec5SDimitry Andric         Initializers.push_back(C);
8350b57cec5SDimitry Andric       }
836e8d8bef9SDimitry Andric       llvm::sort(drop_begin(Initializers, 2),
8370b57cec5SDimitry Andric                  [](const Constant *A, const Constant *B) {
8380b57cec5SDimitry Andric                    return cast<ConstantInt>(A)->getLimitedValue() <
8390b57cec5SDimitry Andric                           cast<ConstantInt>(B)->getLimitedValue();
8400b57cec5SDimitry Andric                  });
8410b57cec5SDimitry Andric       ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
8420b57cec5SDimitry Andric       GlobalVariable *GV = new GlobalVariable(
8430b57cec5SDimitry Andric           *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
8440b57cec5SDimitry Andric           ConstantArray::get(ArrayOfInt64Ty, Initializers),
8450b57cec5SDimitry Andric           "__sancov_gen_cov_switch_values");
8465f757f3fSDimitry Andric       IRB.CreateCall(SanCovTraceSwitchFunction, {Cond, GV});
8470b57cec5SDimitry Andric     }
8480b57cec5SDimitry Andric   }
8490b57cec5SDimitry Andric }
8500b57cec5SDimitry Andric 
8518bcb0991SDimitry Andric void ModuleSanitizerCoverage::InjectTraceForDiv(
8520b57cec5SDimitry Andric     Function &, ArrayRef<BinaryOperator *> DivTraceTargets) {
853bdd1243dSDimitry Andric   for (auto *BO : DivTraceTargets) {
85406c3fb27SDimitry Andric     InstrumentationIRBuilder IRB(BO);
8550b57cec5SDimitry Andric     Value *A1 = BO->getOperand(1);
8560b57cec5SDimitry Andric     if (isa<ConstantInt>(A1)) continue;
8570b57cec5SDimitry Andric     if (!A1->getType()->isIntegerTy())
8580b57cec5SDimitry Andric       continue;
8590b57cec5SDimitry Andric     uint64_t TypeSize = DL->getTypeStoreSizeInBits(A1->getType());
8600b57cec5SDimitry Andric     int CallbackIdx = TypeSize == 32 ? 0 :
8610b57cec5SDimitry Andric         TypeSize == 64 ? 1 : -1;
8620b57cec5SDimitry Andric     if (CallbackIdx < 0) continue;
8630b57cec5SDimitry Andric     auto Ty = Type::getIntNTy(*C, TypeSize);
8640b57cec5SDimitry Andric     IRB.CreateCall(SanCovTraceDivFunction[CallbackIdx],
8650b57cec5SDimitry Andric                    {IRB.CreateIntCast(A1, Ty, true)});
8660b57cec5SDimitry Andric   }
8670b57cec5SDimitry Andric }
8680b57cec5SDimitry Andric 
8698bcb0991SDimitry Andric void ModuleSanitizerCoverage::InjectTraceForGep(
8700b57cec5SDimitry Andric     Function &, ArrayRef<GetElementPtrInst *> GepTraceTargets) {
871bdd1243dSDimitry Andric   for (auto *GEP : GepTraceTargets) {
87206c3fb27SDimitry Andric     InstrumentationIRBuilder IRB(GEP);
873fe6060f1SDimitry Andric     for (Use &Idx : GEP->indices())
874fe6060f1SDimitry Andric       if (!isa<ConstantInt>(Idx) && Idx->getType()->isIntegerTy())
8750b57cec5SDimitry Andric         IRB.CreateCall(SanCovTraceGepFunction,
876fe6060f1SDimitry Andric                        {IRB.CreateIntCast(Idx, IntptrTy, true)});
8770b57cec5SDimitry Andric   }
8780b57cec5SDimitry Andric }
8790b57cec5SDimitry Andric 
880349cc55cSDimitry Andric void ModuleSanitizerCoverage::InjectTraceForLoadsAndStores(
881349cc55cSDimitry Andric     Function &, ArrayRef<LoadInst *> Loads, ArrayRef<StoreInst *> Stores) {
88204eeddc0SDimitry Andric   auto CallbackIdx = [&](Type *ElementTy) -> int {
883349cc55cSDimitry Andric     uint64_t TypeSize = DL->getTypeStoreSizeInBits(ElementTy);
884349cc55cSDimitry Andric     return TypeSize == 8     ? 0
885349cc55cSDimitry Andric            : TypeSize == 16  ? 1
886349cc55cSDimitry Andric            : TypeSize == 32  ? 2
887349cc55cSDimitry Andric            : TypeSize == 64  ? 3
888349cc55cSDimitry Andric            : TypeSize == 128 ? 4
889349cc55cSDimitry Andric                              : -1;
890349cc55cSDimitry Andric   };
891bdd1243dSDimitry Andric   for (auto *LI : Loads) {
89206c3fb27SDimitry Andric     InstrumentationIRBuilder IRB(LI);
893349cc55cSDimitry Andric     auto Ptr = LI->getPointerOperand();
89404eeddc0SDimitry Andric     int Idx = CallbackIdx(LI->getType());
895349cc55cSDimitry Andric     if (Idx < 0)
896349cc55cSDimitry Andric       continue;
8975f757f3fSDimitry Andric     IRB.CreateCall(SanCovLoadFunction[Idx], Ptr);
898349cc55cSDimitry Andric   }
899bdd1243dSDimitry Andric   for (auto *SI : Stores) {
90006c3fb27SDimitry Andric     InstrumentationIRBuilder IRB(SI);
901349cc55cSDimitry Andric     auto Ptr = SI->getPointerOperand();
90204eeddc0SDimitry Andric     int Idx = CallbackIdx(SI->getValueOperand()->getType());
903349cc55cSDimitry Andric     if (Idx < 0)
904349cc55cSDimitry Andric       continue;
9055f757f3fSDimitry Andric     IRB.CreateCall(SanCovStoreFunction[Idx], Ptr);
906349cc55cSDimitry Andric   }
907349cc55cSDimitry Andric }
908349cc55cSDimitry Andric 
9098bcb0991SDimitry Andric void ModuleSanitizerCoverage::InjectTraceForCmp(
9100b57cec5SDimitry Andric     Function &, ArrayRef<Instruction *> CmpTraceTargets) {
911bdd1243dSDimitry Andric   for (auto *I : CmpTraceTargets) {
9120b57cec5SDimitry Andric     if (ICmpInst *ICMP = dyn_cast<ICmpInst>(I)) {
91306c3fb27SDimitry Andric       InstrumentationIRBuilder IRB(ICMP);
9140b57cec5SDimitry Andric       Value *A0 = ICMP->getOperand(0);
9150b57cec5SDimitry Andric       Value *A1 = ICMP->getOperand(1);
9160b57cec5SDimitry Andric       if (!A0->getType()->isIntegerTy())
9170b57cec5SDimitry Andric         continue;
9180b57cec5SDimitry Andric       uint64_t TypeSize = DL->getTypeStoreSizeInBits(A0->getType());
9190b57cec5SDimitry Andric       int CallbackIdx = TypeSize == 8 ? 0 :
9200b57cec5SDimitry Andric                         TypeSize == 16 ? 1 :
9210b57cec5SDimitry Andric                         TypeSize == 32 ? 2 :
9220b57cec5SDimitry Andric                         TypeSize == 64 ? 3 : -1;
9230b57cec5SDimitry Andric       if (CallbackIdx < 0) continue;
9240b57cec5SDimitry Andric       // __sanitizer_cov_trace_cmp((type_size << 32) | predicate, A0, A1);
9250b57cec5SDimitry Andric       auto CallbackFunc = SanCovTraceCmpFunction[CallbackIdx];
9260b57cec5SDimitry Andric       bool FirstIsConst = isa<ConstantInt>(A0);
9270b57cec5SDimitry Andric       bool SecondIsConst = isa<ConstantInt>(A1);
9280b57cec5SDimitry Andric       // If both are const, then we don't need such a comparison.
9290b57cec5SDimitry Andric       if (FirstIsConst && SecondIsConst) continue;
9300b57cec5SDimitry Andric       // If only one is const, then make it the first callback argument.
9310b57cec5SDimitry Andric       if (FirstIsConst || SecondIsConst) {
9320b57cec5SDimitry Andric         CallbackFunc = SanCovTraceConstCmpFunction[CallbackIdx];
9330b57cec5SDimitry Andric         if (SecondIsConst)
9340b57cec5SDimitry Andric           std::swap(A0, A1);
9350b57cec5SDimitry Andric       }
9360b57cec5SDimitry Andric 
9370b57cec5SDimitry Andric       auto Ty = Type::getIntNTy(*C, TypeSize);
9380b57cec5SDimitry Andric       IRB.CreateCall(CallbackFunc, {IRB.CreateIntCast(A0, Ty, true),
9390b57cec5SDimitry Andric               IRB.CreateIntCast(A1, Ty, true)});
9400b57cec5SDimitry Andric     }
9410b57cec5SDimitry Andric   }
9420b57cec5SDimitry Andric }
9430b57cec5SDimitry Andric 
9448bcb0991SDimitry Andric void ModuleSanitizerCoverage::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
9450b57cec5SDimitry Andric                                                     size_t Idx,
9460b57cec5SDimitry Andric                                                     bool IsLeafFunc) {
9470b57cec5SDimitry Andric   BasicBlock::iterator IP = BB.getFirstInsertionPt();
9480b57cec5SDimitry Andric   bool IsEntryBB = &BB == &F.getEntryBlock();
9490b57cec5SDimitry Andric   DebugLoc EntryLoc;
9500b57cec5SDimitry Andric   if (IsEntryBB) {
9510b57cec5SDimitry Andric     if (auto SP = F.getSubprogram())
952e8d8bef9SDimitry Andric       EntryLoc = DILocation::get(SP->getContext(), SP->getScopeLine(), 0, SP);
9530b57cec5SDimitry Andric     // Keep static allocas and llvm.localescape calls in the entry block.  Even
9540b57cec5SDimitry Andric     // if we aren't splitting the block, it's nice for allocas to be before
9550b57cec5SDimitry Andric     // calls.
9560b57cec5SDimitry Andric     IP = PrepareToSplitEntryBlock(BB, IP);
9570b57cec5SDimitry Andric   }
9580b57cec5SDimitry Andric 
95981ad6265SDimitry Andric   InstrumentationIRBuilder IRB(&*IP);
96081ad6265SDimitry Andric   if (EntryLoc)
9610b57cec5SDimitry Andric     IRB.SetCurrentDebugLocation(EntryLoc);
9620b57cec5SDimitry Andric   if (Options.TracePC) {
9635ffd83dbSDimitry Andric     IRB.CreateCall(SanCovTracePC)
9645ffd83dbSDimitry Andric         ->setCannotMerge(); // gets the PC using GET_CALLER_PC.
9650b57cec5SDimitry Andric   }
9660b57cec5SDimitry Andric   if (Options.TracePCGuard) {
9670b57cec5SDimitry Andric     auto GuardPtr = IRB.CreateIntToPtr(
9680b57cec5SDimitry Andric         IRB.CreateAdd(IRB.CreatePointerCast(FunctionGuardArray, IntptrTy),
9690b57cec5SDimitry Andric                       ConstantInt::get(IntptrTy, Idx * 4)),
9705f757f3fSDimitry Andric         PtrTy);
9715ffd83dbSDimitry Andric     IRB.CreateCall(SanCovTracePCGuard, GuardPtr)->setCannotMerge();
9720b57cec5SDimitry Andric   }
9730b57cec5SDimitry Andric   if (Options.Inline8bitCounters) {
9740b57cec5SDimitry Andric     auto CounterPtr = IRB.CreateGEP(
9750b57cec5SDimitry Andric         Function8bitCounterArray->getValueType(), Function8bitCounterArray,
9760b57cec5SDimitry Andric         {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)});
9770b57cec5SDimitry Andric     auto Load = IRB.CreateLoad(Int8Ty, CounterPtr);
9780b57cec5SDimitry Andric     auto Inc = IRB.CreateAdd(Load, ConstantInt::get(Int8Ty, 1));
9790b57cec5SDimitry Andric     auto Store = IRB.CreateStore(Inc, CounterPtr);
98006c3fb27SDimitry Andric     Load->setNoSanitizeMetadata();
98106c3fb27SDimitry Andric     Store->setNoSanitizeMetadata();
9820b57cec5SDimitry Andric   }
9835ffd83dbSDimitry Andric   if (Options.InlineBoolFlag) {
9845ffd83dbSDimitry Andric     auto FlagPtr = IRB.CreateGEP(
9855ffd83dbSDimitry Andric         FunctionBoolArray->getValueType(), FunctionBoolArray,
9865ffd83dbSDimitry Andric         {ConstantInt::get(IntptrTy, 0), ConstantInt::get(IntptrTy, Idx)});
9875ffd83dbSDimitry Andric     auto Load = IRB.CreateLoad(Int1Ty, FlagPtr);
988*0fca6ea1SDimitry Andric     auto ThenTerm = SplitBlockAndInsertIfThen(
989*0fca6ea1SDimitry Andric         IRB.CreateIsNull(Load), &*IP, false,
990*0fca6ea1SDimitry Andric         MDBuilder(IRB.getContext()).createUnlikelyBranchWeights());
9915ffd83dbSDimitry Andric     IRBuilder<> ThenIRB(ThenTerm);
9925ffd83dbSDimitry Andric     auto Store = ThenIRB.CreateStore(ConstantInt::getTrue(Int1Ty), FlagPtr);
99306c3fb27SDimitry Andric     Load->setNoSanitizeMetadata();
99406c3fb27SDimitry Andric     Store->setNoSanitizeMetadata();
9955ffd83dbSDimitry Andric   }
9960b57cec5SDimitry Andric   if (Options.StackDepth && IsEntryBB && !IsLeafFunc) {
9970b57cec5SDimitry Andric     // Check stack depth.  If it's the deepest so far, record it.
9988bcb0991SDimitry Andric     Module *M = F.getParent();
9998bcb0991SDimitry Andric     Function *GetFrameAddr = Intrinsic::getDeclaration(
10008bcb0991SDimitry Andric         M, Intrinsic::frameaddress,
10015f757f3fSDimitry Andric         IRB.getPtrTy(M->getDataLayout().getAllocaAddrSpace()));
10020b57cec5SDimitry Andric     auto FrameAddrPtr =
10030b57cec5SDimitry Andric         IRB.CreateCall(GetFrameAddr, {Constant::getNullValue(Int32Ty)});
10040b57cec5SDimitry Andric     auto FrameAddrInt = IRB.CreatePtrToInt(FrameAddrPtr, IntptrTy);
10050b57cec5SDimitry Andric     auto LowestStack = IRB.CreateLoad(IntptrTy, SanCovLowestStack);
10060b57cec5SDimitry Andric     auto IsStackLower = IRB.CreateICmpULT(FrameAddrInt, LowestStack);
1007*0fca6ea1SDimitry Andric     auto ThenTerm = SplitBlockAndInsertIfThen(
1008*0fca6ea1SDimitry Andric         IsStackLower, &*IP, false,
1009*0fca6ea1SDimitry Andric         MDBuilder(IRB.getContext()).createUnlikelyBranchWeights());
10100b57cec5SDimitry Andric     IRBuilder<> ThenIRB(ThenTerm);
10110b57cec5SDimitry Andric     auto Store = ThenIRB.CreateStore(FrameAddrInt, SanCovLowestStack);
101206c3fb27SDimitry Andric     LowestStack->setNoSanitizeMetadata();
101306c3fb27SDimitry Andric     Store->setNoSanitizeMetadata();
10140b57cec5SDimitry Andric   }
10150b57cec5SDimitry Andric }
10160b57cec5SDimitry Andric 
10170b57cec5SDimitry Andric std::string
10188bcb0991SDimitry Andric ModuleSanitizerCoverage::getSectionName(const std::string &Section) const {
10190b57cec5SDimitry Andric   if (TargetTriple.isOSBinFormatCOFF()) {
10200b57cec5SDimitry Andric     if (Section == SanCovCountersSectionName)
10210b57cec5SDimitry Andric       return ".SCOV$CM";
10225ffd83dbSDimitry Andric     if (Section == SanCovBoolFlagSectionName)
10235ffd83dbSDimitry Andric       return ".SCOV$BM";
10240b57cec5SDimitry Andric     if (Section == SanCovPCsSectionName)
10250b57cec5SDimitry Andric       return ".SCOVP$M";
10260b57cec5SDimitry Andric     return ".SCOV$GM"; // For SanCovGuardsSectionName.
10270b57cec5SDimitry Andric   }
10280b57cec5SDimitry Andric   if (TargetTriple.isOSBinFormatMachO())
10290b57cec5SDimitry Andric     return "__DATA,__" + Section;
10300b57cec5SDimitry Andric   return "__" + Section;
10310b57cec5SDimitry Andric }
10320b57cec5SDimitry Andric 
10330b57cec5SDimitry Andric std::string
10348bcb0991SDimitry Andric ModuleSanitizerCoverage::getSectionStart(const std::string &Section) const {
10350b57cec5SDimitry Andric   if (TargetTriple.isOSBinFormatMachO())
10360b57cec5SDimitry Andric     return "\1section$start$__DATA$__" + Section;
10370b57cec5SDimitry Andric   return "__start___" + Section;
10380b57cec5SDimitry Andric }
10390b57cec5SDimitry Andric 
10400b57cec5SDimitry Andric std::string
10418bcb0991SDimitry Andric ModuleSanitizerCoverage::getSectionEnd(const std::string &Section) const {
10420b57cec5SDimitry Andric   if (TargetTriple.isOSBinFormatMachO())
10430b57cec5SDimitry Andric     return "\1section$end$__DATA$__" + Section;
10440b57cec5SDimitry Andric   return "__stop___" + Section;
10450b57cec5SDimitry Andric }
1046bdd1243dSDimitry Andric 
1047bdd1243dSDimitry Andric void ModuleSanitizerCoverage::createFunctionControlFlow(Function &F) {
1048bdd1243dSDimitry Andric   SmallVector<Constant *, 32> CFs;
1049bdd1243dSDimitry Andric   IRBuilder<> IRB(&*F.getEntryBlock().getFirstInsertionPt());
1050bdd1243dSDimitry Andric 
1051bdd1243dSDimitry Andric   for (auto &BB : F) {
1052bdd1243dSDimitry Andric     // blockaddress can not be used on function's entry block.
1053bdd1243dSDimitry Andric     if (&BB == &F.getEntryBlock())
10545f757f3fSDimitry Andric       CFs.push_back((Constant *)IRB.CreatePointerCast(&F, PtrTy));
1055bdd1243dSDimitry Andric     else
1056bdd1243dSDimitry Andric       CFs.push_back((Constant *)IRB.CreatePointerCast(BlockAddress::get(&BB),
10575f757f3fSDimitry Andric                                                       PtrTy));
1058bdd1243dSDimitry Andric 
1059bdd1243dSDimitry Andric     for (auto SuccBB : successors(&BB)) {
1060bdd1243dSDimitry Andric       assert(SuccBB != &F.getEntryBlock());
1061bdd1243dSDimitry Andric       CFs.push_back((Constant *)IRB.CreatePointerCast(BlockAddress::get(SuccBB),
10625f757f3fSDimitry Andric                                                       PtrTy));
1063bdd1243dSDimitry Andric     }
1064bdd1243dSDimitry Andric 
10655f757f3fSDimitry Andric     CFs.push_back((Constant *)Constant::getNullValue(PtrTy));
1066bdd1243dSDimitry Andric 
1067bdd1243dSDimitry Andric     for (auto &Inst : BB) {
1068bdd1243dSDimitry Andric       if (CallBase *CB = dyn_cast<CallBase>(&Inst)) {
1069bdd1243dSDimitry Andric         if (CB->isIndirectCall()) {
1070bdd1243dSDimitry Andric           // TODO(navidem): handle indirect calls, for now mark its existence.
1071bdd1243dSDimitry Andric           CFs.push_back((Constant *)IRB.CreateIntToPtr(
10725f757f3fSDimitry Andric               ConstantInt::get(IntptrTy, -1), PtrTy));
1073bdd1243dSDimitry Andric         } else {
1074bdd1243dSDimitry Andric           auto CalledF = CB->getCalledFunction();
1075bdd1243dSDimitry Andric           if (CalledF && !CalledF->isIntrinsic())
1076bdd1243dSDimitry Andric             CFs.push_back(
10775f757f3fSDimitry Andric                 (Constant *)IRB.CreatePointerCast(CalledF, PtrTy));
1078bdd1243dSDimitry Andric         }
1079bdd1243dSDimitry Andric       }
1080bdd1243dSDimitry Andric     }
1081bdd1243dSDimitry Andric 
10825f757f3fSDimitry Andric     CFs.push_back((Constant *)Constant::getNullValue(PtrTy));
1083bdd1243dSDimitry Andric   }
1084bdd1243dSDimitry Andric 
1085bdd1243dSDimitry Andric   FunctionCFsArray = CreateFunctionLocalArrayInSection(
10865f757f3fSDimitry Andric       CFs.size(), F, PtrTy, SanCovCFsSectionName);
1087bdd1243dSDimitry Andric   FunctionCFsArray->setInitializer(
10885f757f3fSDimitry Andric       ConstantArray::get(ArrayType::get(PtrTy, CFs.size()), CFs));
1089bdd1243dSDimitry Andric   FunctionCFsArray->setConstant(true);
1090bdd1243dSDimitry Andric }
1091