Move asan-coverage into a separate phase.

[kcc]

Summary

This change moves asan-coverage instrumentation
into a separate Module pass.
The other part of the change in clang introduces a new flag
-fsanitize-coverage=N.
Another small patch will update tests in compiler-rt.

With this patch no functionality change is expected except for the flag name.
The following changes will make the coverage instrumentation work with tsan/msan

[samsonov]

Looks reasonable to me, coverage certainly deserves a separate pass. Nick, any comments?

lib/Transforms/Instrumentation/SanitizerCoverage.cpp

105

Looks like this can be LLVMContext&

[kcc]

lib/Transforms/Instrumentation/SanitizerCoverage.cpp

105

I can't initialize reference in the CTOR as there is no context available at that time.

[nlewycky]

lib/Transforms/Instrumentation/SanitizerCoverage.cpp

115

Please roll this into the report_fatal_error string. (LLVM is a library, may not have stdout, etc.)

122–124

DataLayoutPass *DLP = &getAnalysis<DataLayoutPass>();

142

Space before the colon.

191

Typo: initialed -> initialized

[kcc]

Addressed Nick's comments.

lib/Transforms/Instrumentation/SanitizerCoverage.cpp

115

done

std::string Err;                                                               
raw_string_ostream Stream(Err);                                                
Stream << "SanitizerCoverage interface function redefined: "                   
       << *FuncOrBitcast;                                                      
report_fatal_error(Err);

122–124

done.
Also added

AU.addRequired<DataLayoutPass>();

to
getAnalysisUsage()

142

done

191

done

[nlewycky]

LGTM

include/llvm/InitializePasses.h

 void initializeEarlyIfConverterPass(PassRegistry&);
 void initializeEdgeBundlesPass(PassRegistry&);
 void initializeExpandPostRAPass(PassRegistry&);
 void initializeGCOVProfilerPass(PassRegistry&);
 void initializeAddressSanitizerPass(PassRegistry&);
 void initializeAddressSanitizerModulePass(PassRegistry&);
 void initializeMemorySanitizerPass(PassRegistry&);
 void initializeThreadSanitizerPass(PassRegistry&);
+void initializeSanitizerCoverageModulePass(PassRegistry&);
 void initializeDataFlowSanitizerPass(PassRegistry&);
 void initializeScalarizerPass(PassRegistry&);
 void initializeEarlyCSEPass(PassRegistry&);
 void initializeExpandISelPseudosPass(PassRegistry&);
 void initializeFindUsedTypesPass(PassRegistry&);
 void initializeFunctionAttrsPass(PassRegistry&);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);
 void initializeGCModuleInfoPass(PassRegistry&);

include/llvm/Transforms/Instrumentation.h

 // Insert ThreadSanitizer (race detection) instrumentation
 FunctionPass *createThreadSanitizerPass();
 
 // Insert DataFlowSanitizer (dynamic data flow analysis) instrumentation
 ModulePass *createDataFlowSanitizerPass(StringRef ABIListFile = StringRef(),
                                         void *(*getArgTLS)() = nullptr,
                                         void *(*getRetValTLS)() = nullptr);
 
+// Insert SanitizerCoverage instrumentation.
+ModulePass *createSanitizerCoverageModulePass(int CoverageLevel);
+
 #if defined(__GNUC__) && defined(__linux__) && !defined(ANDROID)
 inline ModulePass *createDataFlowSanitizerPassForJIT(StringRef ABIListFile =
                                                          StringRef()) {
   return createDataFlowSanitizerPass(ABIListFile, getDFSanArgTLSPtrForJIT,
                                      getDFSanRetValTLSPtrForJIT);
 }
 #endif
 

lib/Transforms/Instrumentation/AddressSanitizer.cpp

 static const char *const kAsanReportLoadN = "__asan_report_load_n";
 static const char *const kAsanReportStoreN = "__asan_report_store_n";
 static const char *const kAsanRegisterGlobalsName = "__asan_register_globals";
 static const char *const kAsanUnregisterGlobalsName =
     "__asan_unregister_globals";
 static const char *const kAsanPoisonGlobalsName = "__asan_before_dynamic_init";
 static const char *const kAsanUnpoisonGlobalsName = "__asan_after_dynamic_init";
 static const char *const kAsanInitName = "__asan_init_v4";
-static const char *const kAsanCovModuleInitName = "__sanitizer_cov_module_init";
-static const char *const kAsanCovName = "__sanitizer_cov";
-static const char *const kAsanCovIndirCallName = "__sanitizer_cov_indir_call16";
 static const char *const kAsanPtrCmp = "__sanitizer_ptr_cmp";
 static const char *const kAsanPtrSub = "__sanitizer_ptr_sub";
 static const char *const kAsanHandleNoReturnName = "__asan_handle_no_return";
 static const int         kMaxAsanStackMallocSizeClass = 10;
 static const char *const kAsanStackMallocNameTemplate = "__asan_stack_malloc_";
 static const char *const kAsanStackFreeNameTemplate = "__asan_stack_free_";
 static const char *const kAsanGenPrefix = "__asan_gen_";
 static const char *const kAsanPoisonStackMemoryName =

 // This flag may need to be replaced with -f[no]asan-stack.
 static cl::opt<bool> ClStack("asan-stack",
        cl::desc("Handle stack memory"), cl::Hidden, cl::init(true));
 static cl::opt<bool> ClUseAfterReturn("asan-use-after-return",
        cl::desc("Check return-after-free"), cl::Hidden, cl::init(true));
 // This flag may need to be replaced with -f[no]asan-globals.
 static cl::opt<bool> ClGlobals("asan-globals",
        cl::desc("Handle global objects"), cl::Hidden, cl::init(true));
-static cl::opt<int> ClCoverage("asan-coverage",
-       cl::desc("ASan coverage. 0: none, 1: entry block, 2: all blocks, "
-                "3: all blocks and critical edges, "
-                "4: above plus indirect calls"),
-       cl::Hidden, cl::init(false));
-static cl::opt<int> ClCoverageBlockThreshold("asan-coverage-block-threshold",
-       cl::desc("Add coverage instrumentation only to the entry block if there "
-                "are more than this number of blocks."),
-       cl::Hidden, cl::init(1500));
 static cl::opt<bool> ClInitializers("asan-initialization-order",
        cl::desc("Handle C++ initializer order"), cl::Hidden, cl::init(true));
 static cl::opt<bool> ClInvalidPointerPairs("asan-detect-invalid-pointer-pair",
        cl::desc("Instrument <, <=, >, >=, - with pointer operands"),
        cl::Hidden, cl::init(false));
 static cl::opt<unsigned> ClRealignStack("asan-realign-stack",
        cl::desc("Realign stack to the value of this flag (power of two)"),
        cl::Hidden, cl::init(32));

 static size_t RedzoneSizeForScale(int MappingScale) {
   // Redzone used for stack and globals is at least 32 bytes.
   // For scales 6 and 7, the redzone has to be 64 and 128 bytes respectively.
   return std::max(32U, 1U << MappingScale);
 }
 
 /// AddressSanitizer: instrument the code in module to find memory bugs.
 struct AddressSanitizer : public FunctionPass {
-  AddressSanitizer() : FunctionPass(ID) {
-    initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
-  }
+  AddressSanitizer() : FunctionPass(ID) {}
   const char *getPassName() const override {
     return "AddressSanitizerFunctionPass";
   }
   void instrumentMop(Instruction *I, bool UseCalls);
   void instrumentPointerComparisonOrSubtraction(Instruction *I);
   void instrumentAddress(Instruction *OrigIns, Instruction *InsertBefore,
                          Value *Addr, uint32_t TypeSize, bool IsWrite,
                          Value *SizeArgument, bool UseCalls);
   Value *createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
                            Value *ShadowValue, uint32_t TypeSize);
   Instruction *generateCrashCode(Instruction *InsertBefore, Value *Addr,
                                  bool IsWrite, size_t AccessSizeIndex,
                                  Value *SizeArgument);
   void instrumentMemIntrinsic(MemIntrinsic *MI);
   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
   bool runOnFunction(Function &F) override;
   bool maybeInsertAsanInitAtFunctionEntry(Function &F);
   bool doInitialization(Module &M) override;
   static char ID;  // Pass identification, replacement for typeid
 
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    if (ClCoverage >= 3)
-      AU.addRequiredID(BreakCriticalEdgesID);
-  }
-
  private:
   void initializeCallbacks(Module &M);
 
   bool LooksLikeCodeInBug11395(Instruction *I);
   bool GlobalIsLinkerInitialized(GlobalVariable *G);
-  void InjectCoverageForIndirectCalls(Function &F,
-                                      ArrayRef<Instruction *> IndirCalls);
-  bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks,
-                      ArrayRef<Instruction *> IndirCalls);
-  void InjectCoverageAtBlock(Function &F, BasicBlock &BB);
 
   LLVMContext *C;
   const DataLayout *DL;
   int LongSize;
   Type *IntptrTy;
   ShadowMapping Mapping;
   Function *AsanCtorFunction;
   Function *AsanInitFunction;
   Function *AsanHandleNoReturnFunc;
-  Function *AsanCovFunction;
-  Function *AsanCovIndirCallFunction;
   Function *AsanPtrCmpFunction, *AsanPtrSubFunction;
   // This array is indexed by AccessIsWrite and log2(AccessSize).
   Function *AsanErrorCallback[2][kNumberOfAccessSizes];
   Function *AsanMemoryAccessCallback[2][kNumberOfAccessSizes];
   // This array is indexed by AccessIsWrite.
   Function *AsanErrorCallbackSized[2],
            *AsanMemoryAccessCallbackSized[2];
   Function *AsanMemmove, *AsanMemcpy, *AsanMemset;
private:
   Type *IntptrTy;
   LLVMContext *C;
   const DataLayout *DL;
   ShadowMapping Mapping;
   Function *AsanPoisonGlobals;
   Function *AsanUnpoisonGlobals;
   Function *AsanRegisterGlobals;
   Function *AsanUnregisterGlobals;
-  Function *AsanCovModuleInit;
 };
 
 // Stack poisoning does not play well with exception handling.
 // When an exception is thrown, we essentially bypass the code
 // that unpoisones the stack. This is why the run-time library has
 // to intercept __cxa_throw (as well as longjmp, etc) and unpoison the entire
 // stack in the interceptor. This however does not work inside the
 // actual function which catches the exception. Most likely because the
void AddressSanitizerModule::initializeCallbacks(Module &M) {
   AsanRegisterGlobals = checkInterfaceFunction(M.getOrInsertFunction(
       kAsanRegisterGlobalsName, IRB.getVoidTy(),
       IntptrTy, IntptrTy, NULL));
   AsanRegisterGlobals->setLinkage(Function::ExternalLinkage);
   AsanUnregisterGlobals = checkInterfaceFunction(M.getOrInsertFunction(
       kAsanUnregisterGlobalsName,
       IRB.getVoidTy(), IntptrTy, IntptrTy, NULL));
   AsanUnregisterGlobals->setLinkage(Function::ExternalLinkage);
-  AsanCovModuleInit = checkInterfaceFunction(M.getOrInsertFunction(
-      kAsanCovModuleInitName,
-      IRB.getVoidTy(), IntptrTy, NULL));
-  AsanCovModuleInit->setLinkage(Function::ExternalLinkage);
 }
 
 // This function replaces all global variables with new variables that have
 // trailing redzones. It also creates a function that poisons
 // redzones and inserts this function into llvm.global_ctors.
 bool AddressSanitizerModule::InstrumentGlobals(IRBuilder<> &IRB, Module &M) {
   GlobalsMD.init(M);
 
bool AddressSanitizerModule::runOnModule(Module &M) {
   initializeCallbacks(M);
 
   bool Changed = false;
 
   Function *CtorFunc = M.getFunction(kAsanModuleCtorName);
   assert(CtorFunc);
   IRBuilder<> IRB(CtorFunc->getEntryBlock().getTerminator());
 
-  if (ClCoverage > 0) {
-    Function *CovFunc = M.getFunction(kAsanCovName);
-    int nCov = CovFunc ? CovFunc->getNumUses() : 0;
-    IRB.CreateCall(AsanCovModuleInit, ConstantInt::get(IntptrTy, nCov));
-    Changed = true;
-  }
-
   if (ClGlobals)
     Changed |= InstrumentGlobals(IRB, M);
 
   return Changed;
 }
 
 void AddressSanitizer::initializeCallbacks(Module &M) {
   IRBuilder<> IRB(*C);
AsanMemcpy = checkInterfaceFunction(M.getOrInsertFunction(
       ClMemoryAccessCallbackPrefix + "memcpy", IRB.getInt8PtrTy(),
       IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IntptrTy, NULL));
   AsanMemset = checkInterfaceFunction(M.getOrInsertFunction(
       ClMemoryAccessCallbackPrefix + "memset", IRB.getInt8PtrTy(),
       IRB.getInt8PtrTy(), IRB.getInt32Ty(), IntptrTy, NULL));
 
   AsanHandleNoReturnFunc = checkInterfaceFunction(
       M.getOrInsertFunction(kAsanHandleNoReturnName, IRB.getVoidTy(), NULL));
-  AsanCovFunction = checkInterfaceFunction(M.getOrInsertFunction(
-      kAsanCovName, IRB.getVoidTy(), NULL));
-  AsanCovIndirCallFunction = checkInterfaceFunction(M.getOrInsertFunction(
-      kAsanCovIndirCallName, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL));
 
   AsanPtrCmpFunction = checkInterfaceFunction(M.getOrInsertFunction(
       kAsanPtrCmp, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL));
   AsanPtrSubFunction = checkInterfaceFunction(M.getOrInsertFunction(
       kAsanPtrSub, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL));
   // We insert an empty inline asm after __asan_report* to avoid callback merge.
   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
                             StringRef(""), StringRef(""),
bool AddressSanitizer::maybeInsertAsanInitAtFunctionEntry(Function &F) {
   if (F.getName().find(" load]") != std::string::npos) {
     IRBuilder<> IRB(F.begin()->begin());
     IRB.CreateCall(AsanInitFunction);
     return true;
   }
   return false;
 }
 
-void AddressSanitizer::InjectCoverageAtBlock(Function &F, BasicBlock &BB) {
-  BasicBlock::iterator IP = BB.getFirstInsertionPt(), BE = BB.end();
-  // Skip static allocas at the top of the entry block so they don't become
-  // dynamic when we split the block.  If we used our optimized stack layout,
-  // then there will only be one alloca and it will come first.
-  for (; IP != BE; ++IP) {
-    AllocaInst *AI = dyn_cast<AllocaInst>(IP);
-    if (!AI || !AI->isStaticAlloca())
-      break;
-  }
-
-  DebugLoc EntryLoc = &BB == &F.getEntryBlock()
-                          ? IP->getDebugLoc().getFnDebugLoc(*C)
-                          : IP->getDebugLoc();
-  IRBuilder<> IRB(IP);
-  IRB.SetCurrentDebugLocation(EntryLoc);
-  Type *Int8Ty = IRB.getInt8Ty();
-  GlobalVariable *Guard = new GlobalVariable(
-      *F.getParent(), Int8Ty, false, GlobalValue::PrivateLinkage,
-      Constant::getNullValue(Int8Ty), "__asan_gen_cov_" + F.getName());
-  LoadInst *Load = IRB.CreateLoad(Guard);
-  Load->setAtomic(Monotonic);
-  Load->setAlignment(1);
-  Value *Cmp = IRB.CreateICmpEQ(Constant::getNullValue(Int8Ty), Load);
-  Instruction *Ins = SplitBlockAndInsertIfThen(
-      Cmp, IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
-  IRB.SetInsertPoint(Ins);
-  IRB.SetCurrentDebugLocation(EntryLoc);
-  // __sanitizer_cov gets the PC of the instruction using GET_CALLER_PC.
-  IRB.CreateCall(AsanCovFunction);
-  StoreInst *Store = IRB.CreateStore(ConstantInt::get(Int8Ty, 1), Guard);
-  Store->setAtomic(Monotonic);
-  Store->setAlignment(1);
-}
-
-// Poor man's coverage that works with ASan.
-// We create a Guard boolean variable with the same linkage
-// as the function and inject this code into the entry block (-asan-coverage=1)
-// or all blocks (-asan-coverage=2):
-// if (*Guard) {
-//    __sanitizer_cov();
-//    *Guard = 1;
-// }
-// The accesses to Guard are atomic. The rest of the logic is
-// in __sanitizer_cov (it's fine to call it more than once).
-//
-// This coverage implementation provides very limited data:
-// it only tells if a given function (block) was ever executed.
-// No counters, no per-edge data.
-// But for many use cases this is what we need and the added slowdown
-// is negligible. This simple implementation will probably be obsoleted
-// by the upcoming Clang-based coverage implementation.
-// By having it here and now we hope to
-//  a) get the functionality to users earlier and
-//  b) collect usage statistics to help improve Clang coverage design.
-bool AddressSanitizer::InjectCoverage(Function &F,
-                                      ArrayRef<BasicBlock *> AllBlocks,
-                                      ArrayRef<Instruction*> IndirCalls) {
-  if (!ClCoverage) return false;
-
-  if (ClCoverage == 1 ||
-      (unsigned)ClCoverageBlockThreshold < AllBlocks.size()) {
-    InjectCoverageAtBlock(F, F.getEntryBlock());
-  } else {
-    for (auto BB : AllBlocks)
-      InjectCoverageAtBlock(F, *BB);
-  }
-  InjectCoverageForIndirectCalls(F, IndirCalls);
-  return true;
-}
-
-// On every indirect call we call a run-time function
-// __sanitizer_cov_indir_call* with two parameters:
-//   - callee address,
-//   - global cache array that contains kCacheSize pointers (zero-initialed).
-//     The cache is used to speed up recording the caller-callee pairs.
-// The address of the caller is passed implicitly via caller PC.
-// kCacheSize is encoded in the name of the run-time function.
-void AddressSanitizer::InjectCoverageForIndirectCalls(
-    Function &F, ArrayRef<Instruction *> IndirCalls) {
-  if (ClCoverage < 4 || IndirCalls.empty()) return;
-  const int kCacheSize = 16;
-  const int kCacheAlignment = 64;  // Align for better performance.
-  Type *Ty = ArrayType::get(IntptrTy, kCacheSize);
-  for (auto I : IndirCalls) {
-    IRBuilder<> IRB(I);
-    CallSite CS(I);
-    Value *Callee = CS.getCalledValue();
-    if (dyn_cast<InlineAsm>(Callee)) continue;
-    GlobalVariable *CalleeCache = new GlobalVariable(
-        *F.getParent(), Ty, false, GlobalValue::PrivateLinkage,
-        Constant::getNullValue(Ty), "__asan_gen_callee_cache");
-    CalleeCache->setAlignment(kCacheAlignment);
-    IRB.CreateCall2(AsanCovIndirCallFunction,
-                    IRB.CreatePointerCast(Callee, IntptrTy),
-                    IRB.CreatePointerCast(CalleeCache, IntptrTy));
-  }
-}
-
 bool AddressSanitizer::runOnFunction(Function &F) {
   if (&F == AsanCtorFunction) return false;
   if (F.getLinkage() == GlobalValue::AvailableExternallyLinkage) return false;
   DEBUG(dbgs() << "ASAN instrumenting:\n" << F << "\n");
   initializeCallbacks(*F.getParent());
 
   // If needed, insert __asan_init before checking for SanitizeAddress attr.
   maybeInsertAsanInitAtFunctionEntry(F);
 
   if (!F.hasFnAttribute(Attribute::SanitizeAddress))
     return false;
 
   if (!ClDebugFunc.empty() && ClDebugFunc != F.getName())
     return false;
 
   // We want to instrument every address only once per basic block (unless there
   // are calls between uses).
   SmallSet<Value*, 16> TempsToInstrument;
   SmallVector<Instruction*, 16> ToInstrument;
   SmallVector<Instruction*, 8> NoReturnCalls;
   SmallVector<BasicBlock*, 16> AllBlocks;
   SmallVector<Instruction*, 16> PointerComparisonsOrSubtracts;
-  SmallVector<Instruction*, 8> IndirCalls;
   int NumAllocas = 0;
   bool IsWrite;
   unsigned Alignment;
 
   // Fill the set of memory operations to instrument.
   for (auto &BB : F) {
     AllBlocks.push_back(&BB);
     TempsToInstrument.clear();
for (auto &Inst : BB) {
         if (isa<AllocaInst>(Inst))
           NumAllocas++;
         CallSite CS(&Inst);
         if (CS) {
           // A call inside BB.
           TempsToInstrument.clear();
           if (CS.doesNotReturn())
             NoReturnCalls.push_back(CS.getInstruction());
-          if (ClCoverage >= 4 && !CS.getCalledFunction())
-            IndirCalls.push_back(&Inst);
         }
         continue;
       }
       ToInstrument.push_back(&Inst);
       NumInsnsPerBB++;
       if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB)
         break;
     }
bool AddressSanitizer::runOnFunction(Function &F) {
 
   for (auto Inst : PointerComparisonsOrSubtracts) {
     instrumentPointerComparisonOrSubtraction(Inst);
     NumInstrumented++;
   }
 
   bool res = NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty();
 
-  if (InjectCoverage(F, AllBlocks, IndirCalls))
-    res = true;
-
   DEBUG(dbgs() << "ASAN done instrumenting: " << res << " " << F << "\n");
 
   if (ClKeepUninstrumented) {
     if (!res) {
       // No instrumentation is done, no need for the duplicate.
       if (UninstrumentedDuplicate)
         UninstrumentedDuplicate->eraseFromParent();
     } else {

lib/Transforms/Instrumentation/CMakeLists.txt

 add_llvm_library(LLVMInstrumentation
   AddressSanitizer.cpp
   BoundsChecking.cpp
   DataFlowSanitizer.cpp
   DebugIR.cpp
   GCOVProfiling.cpp
   MemorySanitizer.cpp
   Instrumentation.cpp
+  SanitizerCoverage.cpp
   ThreadSanitizer.cpp
   )
 
 add_dependencies(LLVMInstrumentation intrinsics_gen)

lib/Transforms/Instrumentation/Instrumentation.cpp

 /// library.
 void llvm::initializeInstrumentation(PassRegistry &Registry) {
   initializeAddressSanitizerPass(Registry);
   initializeAddressSanitizerModulePass(Registry);
   initializeBoundsCheckingPass(Registry);
   initializeGCOVProfilerPass(Registry);
   initializeMemorySanitizerPass(Registry);
   initializeThreadSanitizerPass(Registry);
+  initializeSanitizerCoverageModulePass(Registry);
   initializeDataFlowSanitizerPass(Registry);
 }
 
 /// LLVMInitializeInstrumentation - C binding for
 /// initializeInstrumentation.
 void LLVMInitializeInstrumentation(LLVMPassRegistryRef R) {
   initializeInstrumentation(*unwrap(R));
 }

lib/Transforms/Instrumentation/SanitizerCoverage.cpp

+//===-- SanitizerCoverage.cpp - coverage instrumentation for sanitizers ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Coverage instrumentation that works with AddressSanitizer
+// and potentially with other Sanitizers.
+//
+// We create a Guard boolean variable with the same linkage
+// as the function and inject this code into the entry block (CoverageLevel=1)
+// or all blocks (CoverageLevel>=2):
+// if (*Guard) {
+//    __sanitizer_cov();
+//    *Guard = 1;
+// }
+// The accesses to Guard are atomic. The rest of the logic is
+// in __sanitizer_cov (it's fine to call it more than once).
+//
+// With CoverageLevel>=3 we also split critical edges this effectively
+// instrumenting all edges.
+//
+// CoverageLevel>=4 add indirect call profiling implented as a function call.
+//
+// This coverage implementation provides very limited data:
+// it only tells if a given function (block) was ever executed. No counters.
+// But for many use cases this is what we need and the added slowdown small.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Instrumentation.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "sancov"
+
+static const char *const kSanCovModuleInitName = "__sanitizer_cov_module_init";
+static const char *const kSanCovName = "__sanitizer_cov";
+static const char *const kSanCovIndirCallName = "__sanitizer_cov_indir_call16";
+static const char *const kSanCovModuleCtorName = "sancov.module_ctor";
+static const uint64_t    kSanCtorAndDtorPriority = 1;
+
+static cl::opt<int> ClCoverageLevel("sanitizer-coverage-level",
+       cl::desc("Sanitizer Coverage. 0: none, 1: entry block, 2: all blocks, "
+                "3: all blocks and critical edges, "
+                "4: above plus indirect calls"),
+       cl::Hidden, cl::init(0));
+
+static cl::opt<int> ClCoverageBlockThreshold(
+    "sanitizer-coverage-block-threshold",
+    cl::desc("Add coverage instrumentation only to the entry block if there "
+             "are more than this number of blocks."),
+    cl::Hidden, cl::init(1500));
+
+namespace {
+
+class SanitizerCoverageModule : public ModulePass {
+ public:
+  SanitizerCoverageModule(int CoverageLevel = 0)
+       : ModulePass(ID),
+         CoverageLevel(std::max(CoverageLevel, (int)ClCoverageLevel)) {
+    initializeBreakCriticalEdgesPass(*PassRegistry::getPassRegistry());
+  }
+  bool runOnModule(Module &M) override;
+  bool runOnFunction(Function &F);
+  static char ID;  // Pass identification, replacement for typeid
+  const char *getPassName() const override {
+    return "SanitizerCoverageModule";
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    if (CoverageLevel >= 3)
+      AU.addRequiredID(BreakCriticalEdgesID);
+    AU.addRequired<DataLayoutPass>();
+  }
+
+ private:
+  void InjectCoverageForIndirectCalls(Function &F,
+                                      ArrayRef<Instruction *> IndirCalls);
+  bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks,
+                      ArrayRef<Instruction *> IndirCalls);
+  void InjectCoverageAtBlock(Function &F, BasicBlock &BB);
+  Function *SanCovFunction;
+  Function *SanCovIndirCallFunction;
+  Function *SanCovModuleInit;
+  Type *IntptrTy;
+  LLVMContext *C;
+
+  int CoverageLevel;
+};
+
+}  // namespace
+
+static Function *checkInterfaceFunction(Constant *FuncOrBitcast) {
+  if (Function *F = dyn_cast<Function>(FuncOrBitcast))
+     return F;
+  std::string Err;
+  raw_string_ostream Stream(Err);
+  Stream << "SanitizerCoverage interface function redefined: "
+         << *FuncOrBitcast;
+  report_fatal_error(Err);
+}
+
+bool SanitizerCoverageModule::runOnModule(Module &M) {
+  if (!CoverageLevel) return false;
+  C = &(M.getContext());
+  DataLayoutPass *DLP = &getAnalysis<DataLayoutPass>();
+  IntptrTy = Type::getIntNTy(*C, DLP->getDataLayout().getPointerSizeInBits());
+  Type *VoidTy = Type::getVoidTy(*C);
+
+  Function *CtorFunc =
+      Function::Create(FunctionType::get(VoidTy, false),
+                       GlobalValue::InternalLinkage, kSanCovModuleCtorName, &M);
+  ReturnInst::Create(*C, BasicBlock::Create(*C, "", CtorFunc));
+  appendToGlobalCtors(M, CtorFunc, kSanCtorAndDtorPriority);
+
+  SanCovFunction =
+      checkInterfaceFunction(M.getOrInsertFunction(kSanCovName, VoidTy, NULL));
+  SanCovIndirCallFunction = checkInterfaceFunction(M.getOrInsertFunction(
+      kSanCovIndirCallName, VoidTy, IntptrTy, IntptrTy, NULL));
+  SanCovModuleInit = checkInterfaceFunction(M.getOrInsertFunction(
+      kSanCovModuleInitName, Type::getVoidTy(*C), IntptrTy, NULL));
+  SanCovModuleInit->setLinkage(Function::ExternalLinkage);
+
+  for (auto &F : M)
+    runOnFunction(F);
+
+  IRBuilder<> IRB(CtorFunc->getEntryBlock().getTerminator());
+  IRB.CreateCall(SanCovModuleInit,
+                 ConstantInt::get(IntptrTy, SanCovFunction->getNumUses()));
+  return true;
+}
+
+bool SanitizerCoverageModule::runOnFunction(Function &F) {
+  if (F.empty()) return false;
+  // For now instrument only functions that will also be asan-instrumented.
+  if (!F.hasFnAttribute(Attribute::SanitizeAddress))
+    return false;
+  SmallVector<Instruction*, 8> IndirCalls;
+  SmallVector<BasicBlock*, 16> AllBlocks;
+  for (auto &BB : F) {
+    AllBlocks.push_back(&BB);
+    if (CoverageLevel >= 4)
+      for (auto &Inst : BB) {
+        CallSite CS(&Inst);
+        if (CS && !CS.getCalledFunction())
+          IndirCalls.push_back(&Inst);
+      }
+  }
+  InjectCoverage(F, AllBlocks, IndirCalls);
+  return true;
+}
+
+bool
+SanitizerCoverageModule::InjectCoverage(Function &F,
+                                        ArrayRef<BasicBlock *> AllBlocks,
+                                        ArrayRef<Instruction *> IndirCalls) {
+  if (!CoverageLevel) return false;
+
+  if (CoverageLevel == 1 ||
+      (unsigned)ClCoverageBlockThreshold < AllBlocks.size()) {
+    InjectCoverageAtBlock(F, F.getEntryBlock());
+  } else {
+    for (auto BB : AllBlocks)
+      InjectCoverageAtBlock(F, *BB);
+  }
+  InjectCoverageForIndirectCalls(F, IndirCalls);
+  return true;
+}
+
+// On every indirect call we call a run-time function
+// __sanitizer_cov_indir_call* with two parameters:
+//   - callee address,
+//   - global cache array that contains kCacheSize pointers (zero-initialized).
+//     The cache is used to speed up recording the caller-callee pairs.
+// The address of the caller is passed implicitly via caller PC.
+// kCacheSize is encoded in the name of the run-time function.
+void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
+    Function &F, ArrayRef<Instruction *> IndirCalls) {
+  if (IndirCalls.empty()) return;
+  const int kCacheSize = 16;
+  const int kCacheAlignment = 64;  // Align for better performance.
+  Type *Ty = ArrayType::get(IntptrTy, kCacheSize);
+  for (auto I : IndirCalls) {
+    IRBuilder<> IRB(I);
+    CallSite CS(I);
+    Value *Callee = CS.getCalledValue();
+    if (dyn_cast<InlineAsm>(Callee)) continue;
+    GlobalVariable *CalleeCache = new GlobalVariable(
+        *F.getParent(), Ty, false, GlobalValue::PrivateLinkage,
+        Constant::getNullValue(Ty), "__sancov_gen_callee_cache");
+    CalleeCache->setAlignment(kCacheAlignment);
+    IRB.CreateCall2(SanCovIndirCallFunction,
+                    IRB.CreatePointerCast(Callee, IntptrTy),
+                    IRB.CreatePointerCast(CalleeCache, IntptrTy));
+  }
+}
+
+void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F,
+                                                    BasicBlock &BB) {
+  BasicBlock::iterator IP = BB.getFirstInsertionPt(), BE = BB.end();
+  // Skip static allocas at the top of the entry block so they don't become
+  // dynamic when we split the block.  If we used our optimized stack layout,
+  // then there will only be one alloca and it will come first.
+  for (; IP != BE; ++IP) {
+    AllocaInst *AI = dyn_cast<AllocaInst>(IP);
+    if (!AI || !AI->isStaticAlloca())
+      break;
+  }
+
+  DebugLoc EntryLoc = &BB == &F.getEntryBlock()
+                          ? IP->getDebugLoc().getFnDebugLoc(*C)
+                          : IP->getDebugLoc();
+  IRBuilder<> IRB(IP);
+  IRB.SetCurrentDebugLocation(EntryLoc);
+  Type *Int8Ty = IRB.getInt8Ty();
+  GlobalVariable *Guard = new GlobalVariable(
+      *F.getParent(), Int8Ty, false, GlobalValue::PrivateLinkage,
+      Constant::getNullValue(Int8Ty), "__sancov_gen_cov_" + F.getName());
+  LoadInst *Load = IRB.CreateLoad(Guard);
+  Load->setAtomic(Monotonic);
+  Load->setAlignment(1);
+  Value *Cmp = IRB.CreateICmpEQ(Constant::getNullValue(Int8Ty), Load);
+  Instruction *Ins = SplitBlockAndInsertIfThen(
+      Cmp, IP, false, MDBuilder(*C).createBranchWeights(1, 100000));
+  IRB.SetInsertPoint(Ins);
+  IRB.SetCurrentDebugLocation(EntryLoc);
+  // __sanitizer_cov gets the PC of the instruction using GET_CALLER_PC.
+  IRB.CreateCall(SanCovFunction);
+  StoreInst *Store = IRB.CreateStore(ConstantInt::get(Int8Ty, 1), Guard);
+  Store->setAtomic(Monotonic);
+  Store->setAlignment(1);
+}
+
+char SanitizerCoverageModule::ID = 0;
+INITIALIZE_PASS(SanitizerCoverageModule, "sancov",
+    "SanitizerCoverage: TODO."
+    "ModulePass", false, false)
+ModulePass *llvm::createSanitizerCoverageModulePass(int CoverageLevel) {
+  return new SanitizerCoverageModule(CoverageLevel);
+}

test/Instrumentation/SanitizerCoverage/coverage-dbg.ll

 ; Test that coverage instrumentation does not lose debug location.
 
-; RUN: opt < %s -asan -asan-module -asan-coverage=1 -S | FileCheck %s
+; RUN: opt < %s -sancov -sanitizer-coverage-level=1 -S | FileCheck %s
 
 ; C++ source:
 ; 1: struct A {
 ; 2:  int f();
 ; 3:  int x;
 ; 4: };
 ; 5:
 ; 6: int A::f() {

test/Instrumentation/SanitizerCoverage/coverage.ll

-; RUN: opt < %s -asan -asan-module -asan-coverage=0 -S | FileCheck %s --check-prefix=CHECK0
-; RUN: opt < %s -asan -asan-module -asan-coverage=1 -S | FileCheck %s --check-prefix=CHECK1
-; RUN: opt < %s -asan -asan-module -asan-coverage=2 -S | FileCheck %s --check-prefix=CHECK2
-; RUN: opt < %s -asan -asan-module -asan-coverage=2 -asan-coverage-block-threshold=10 -S | FileCheck %s --check-prefix=CHECK2
-; RUN: opt < %s -asan -asan-module -asan-coverage=2 -asan-coverage-block-threshold=1  -S | FileCheck %s --check-prefix=CHECK1
-; RUN: opt < %s -asan -asan-module -asan-coverage=3 -asan-coverage-block-threshold=10 -S | FileCheck %s --check-prefix=CHECK3
-; RUN: opt < %s -asan -asan-module -asan-coverage=4 -S | FileCheck %s --check-prefix=CHECK4
-
-; RUN: opt < %s -asan -asan-module -asan-coverage=0 -asan-globals=0 -S | \
-; RUN:     FileCheck %s --check-prefix=CHECK0
-; RUN: opt < %s -asan -asan-module -asan-coverage=1 -asan-globals=0 -S | \
-; RUN:     FileCheck %s --check-prefix=CHECK1
-; RUN: opt < %s -asan -asan-module -asan-coverage=2 -asan-globals=0 -S | \
-; RUN:     FileCheck %s --check-prefix=CHECK2
-; RUN: opt < %s -asan -asan-module -asan-coverage=2 -asan-coverage-block-threshold=10 \
-; RUN:     -asan-globals=0 -S | FileCheck %s --check-prefix=CHECK2
-; RUN: opt < %s -asan -asan-module -asan-coverage=2 -asan-coverage-block-threshold=1 \
-; RUN:     -asan-globals=0 -S | FileCheck %s --check-prefix=CHECK1
+; RUN: opt < %s -sancov -sanitizer-coverage-level=0 -S | FileCheck %s --check-prefix=CHECK0
+; RUN: opt < %s -sancov -sanitizer-coverage-level=1 -S | FileCheck %s --check-prefix=CHECK1
+; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -S | FileCheck %s --check-prefix=CHECK2
+; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-block-threshold=10 -S | FileCheck %s --check-prefix=CHECK2
+; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-block-threshold=1  -S | FileCheck %s --check-prefix=CHECK1
+; RUN: opt < %s -sancov -sanitizer-coverage-level=3 -sanitizer-coverage-block-threshold=10 -S | FileCheck %s --check-prefix=CHECK3
+; RUN: opt < %s -sancov -sanitizer-coverage-level=4 -S | FileCheck %s --check-prefix=CHECK4
+
+; RUN: opt < %s -sancov -sanitizer-coverage-level=0  -S | FileCheck %s --check-prefix=CHECK0
+; RUN: opt < %s -sancov -sanitizer-coverage-level=1  -S | FileCheck %s --check-prefix=CHECK1
+; RUN: opt < %s -sancov -sanitizer-coverage-level=2  -S | FileCheck %s --check-prefix=CHECK2
+; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-block-threshold=10 \
+; RUN:      -S | FileCheck %s --check-prefix=CHECK2
+; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-block-threshold=1 \
+; RUN:      -S | FileCheck %s --check-prefix=CHECK1
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-unknown-linux-gnu"
 define void @foo(i32* %a) sanitize_address {
 entry:
   %tobool = icmp eq i32* %a, null
   br i1 %tobool, label %if.end, label %if.then
 
   if.then:                                          ; preds = %entry
   store i32 0, i32* %a, align 4
   br label %if.end
 
   if.end:                                           ; preds = %entry, %if.then
   ret void
 }
 
 ; CHECK0-NOT: call void @__sanitizer_cov(
 ; CHECK0-NOT: call void @__sanitizer_cov_module_init(
 
 ; CHECK1-LABEL: define void @foo
-; CHECK1: %0 = load atomic i8* @__asan_gen_cov_foo monotonic, align 1
+; CHECK1: %0 = load atomic i8* @__sancov_gen_cov_foo monotonic, align 1
 ; CHECK1: %1 = icmp eq i8 0, %0
 ; CHECK1: br i1 %1, label %2, label %3
 ; CHECK1: call void @__sanitizer_cov
 ; CHECK1-NOT: call void @__sanitizer_cov
-; CHECK1: store atomic i8 1, i8* @__asan_gen_cov_foo monotonic, align 1
+; CHECK1: store atomic i8 1, i8* @__sancov_gen_cov_foo monotonic, align 1
 
-; CHECK1-LABEL: define internal void @asan.module_ctor
+; CHECK1-LABEL: define internal void @sancov.module_ctor
 ; CHECK1-NOT: ret
 ; CHECK1: call void @__sanitizer_cov_module_init(i64 2)
 ; CHECK1: ret
 
 
 ; CHECK2-LABEL: define void @foo
 ; CHECK2: call void @__sanitizer_cov
 ; CHECK2: call void @__sanitizer_cov
 ; CHECK2: call void @__sanitizer_cov
 ; CHECK2-NOT: call void @__sanitizer_cov
 ; CHECK2: ret void
 
-; CHECK2-LABEL: define internal void @asan.module_ctor
+; CHECK2-LABEL: define internal void @sancov.module_ctor
 ; CHECK2-NOT: ret
 ; CHECK2: call void @__sanitizer_cov_module_init(i64 4)
 ; CHECK2: ret
 
 ; CHECK3-LABEL: define void @foo
 ; CHECK3: call void @__sanitizer_cov
 ; CHECK3: call void @__sanitizer_cov
 ; CHECK3: call void @__sanitizer_cov

test/Instrumentation/SanitizerCoverage/coverage2-dbg.ll

 ; Test that coverage instrumentation does not lose debug location.
 
-; RUN: opt < %s -asan -asan-module -asan-coverage=2 -S | FileCheck %s
+; RUN: opt < %s -sancov  -sanitizer-coverage-level=2 -S | FileCheck %s
 
 ; C++ source:
 ; 1: void foo(int *a) {
 ; 2:     if (a)
 ; 3:         *a = 0;
 ; 4: }
 ; clang++ if.cc -O3 -g -S -emit-llvm
 ; and add sanitize_address to @_Z3fooPi