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