[sancov] Pruning full dominator blocks from instrumentation.

[aizatsky]

Summary

This is the first simple attempt to reduce number of coverage-
instrumented blocks.

If a basic block dominates all its successors, then its coverage
information is useless to us. Ingore such blocks if
santizer-coverage-prune-tree option is set.

[aizatsky]

nits

[kcc]

LGTM

llvm/trunk/lib/Transforms/Instrumentation/SanitizerCoverage.cpp

 // instrumenting all edges.
 //
 // 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/Analysis/EHPersonalities.h"
+#include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InlineAsm.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/Instrumentation.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 cl::opt<bool> ClExperimentalTracePC("sanitizer-coverage-trace-pc",
                                            cl::Hidden, cl::init(false));
 
 static cl::opt<bool>
     ClExperimentalCMPTracing("sanitizer-coverage-experimental-trace-compares",
                              cl::desc("Experimental tracing of CMP and similar "
                                       "instructions"),
                              cl::Hidden, cl::init(false));
 
+static cl::opt<bool> ClPruneBlocks(
+    "sanitizer-coverage-prune-blocks",
+    cl::desc("Reduce the number of instrumented blocks (experimental)"),
+    cl::Hidden, cl::init(false));
+
 // Experimental 8-bit counters used as an additional search heuristic during
 // coverage-guided fuzzing.
 // The counters are not thread-friendly:
 //   - contention on these counters may cause significant slowdown;
 //   - the counter updates are racy and the results may be inaccurate.
 // They are also inaccurate due to 8-bit integer overflow.
 static cl::opt<bool> ClUse8bitCounters("sanitizer-coverage-8bit-counters",
                                        cl::desc("Experimental 8-bit counters"),
std::tie(CtorFunc, std::ignore) = createSanitizerCtorAndInitFunctions(
            : Constant::getNullValue(Int8PtrTy),
        IRB.CreatePointerCast(ModuleName, Int8PtrTy)});
 
   appendToGlobalCtors(M, CtorFunc, kSanCtorAndDtorPriority);
 
   return true;
 }
 
+static bool shouldInstrumentBlock(const BasicBlock *BB,
+                                  const DominatorTree *DT) {
+  if (!ClPruneBlocks)
+    return true;
+  if (succ_begin(BB) == succ_end(BB))
+    return true;
+
+  // Check if BB dominates all its successors.
+  for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) {
+    if (!DT->dominates(BB, SUCC))
+      return true;
+  }
+
+  return false;
+}
+
 bool SanitizerCoverageModule::runOnFunction(Function &F) {
   if (F.empty()) return false;
   if (F.getName().find(".module_ctor") != std::string::npos)
     return false;  // Should not instrument sanitizer init functions.
   // Don't instrument functions using SEH for now. Splitting basic blocks like
   // we do for coverage breaks WinEHPrepare.
   // FIXME: Remove this when SEH no longer uses landingpad pattern matching.
   if (F.hasPersonalityFn() &&
       isAsynchronousEHPersonality(classifyEHPersonality(F.getPersonalityFn())))
     return false;
   if (Options.CoverageType >= SanitizerCoverageOptions::SCK_Edge)
     SplitAllCriticalEdges(F);
   SmallVector<Instruction*, 8> IndirCalls;
-  SmallVector<BasicBlock*, 16> AllBlocks;
+  SmallVector<BasicBlock *, 16> BlocksToInstrument;
   SmallVector<Instruction*, 8> CmpTraceTargets;
   SmallVector<Instruction*, 8> SwitchTraceTargets;
+
+  DominatorTree DT;
+  DT.recalculate(F);
   for (auto &BB : F) {
-    AllBlocks.push_back(&BB);
+    if (shouldInstrumentBlock(&BB, &DT))
+      BlocksToInstrument.push_back(&BB);
     for (auto &Inst : BB) {
       if (Options.IndirectCalls) {
         CallSite CS(&Inst);
         if (CS && !CS.getCalledFunction())
           IndirCalls.push_back(&Inst);
       }
       if (Options.TraceCmp) {
         if (isa<ICmpInst>(&Inst))
           CmpTraceTargets.push_back(&Inst);
         if (isa<SwitchInst>(&Inst))
           SwitchTraceTargets.push_back(&Inst);
       }
     }
   }
-  InjectCoverage(F, AllBlocks);
+
+  InjectCoverage(F, BlocksToInstrument);
   InjectCoverageForIndirectCalls(F, IndirCalls);
   InjectTraceForCmp(F, CmpTraceTargets);
   InjectTraceForSwitch(F, SwitchTraceTargets);
   return true;
 }
 
 bool SanitizerCoverageModule::InjectCoverage(Function &F,
                                              ArrayRef<BasicBlock *> AllBlocks) {

llvm/trunk/test/Instrumentation/SanitizerCoverage/coverage.ll

 ; 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=0  -S | FileCheck %s --check-prefix=CHECK_WITH_CHECK
 ; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-block-threshold=1  -S | FileCheck %s --check-prefix=CHECK_WITH_CHECK
 ; 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=4 -sanitizer-coverage-trace-pc  -S | FileCheck %s --check-prefix=CHECK_TRACE_PC_INDIR
 ; RUN: opt < %s -sancov -sanitizer-coverage-level=3 -sanitizer-coverage-8bit-counters=1  -S | FileCheck %s --check-prefix=CHECK-8BIT
 
 ; 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=CHECK_WITH_CHECK
+; RUN: opt < %s -sancov -sanitizer-coverage-level=2 -sanitizer-coverage-prune-blocks=1 -S | FileCheck %s --check-prefix=CHECKPRUNE
 
 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
 

 define void @call_unreachable() uwtable sanitize_address {
 entry:
   unreachable
 }
 
 ; CHECK4-LABEL: define void @call_unreachable
 ; CHECK4-NOT: __sanitizer_cov
 ; CHECK4: unreachable
+
+; CHECKPRUNE-LABEL: define void @foo
+; CHECKPRUNE: call void @__sanitizer_cov
+; CHECKPRUNE: call void asm sideeffect "", ""()
+; CHECKPRUNE: call void @__sanitizer_cov
+; CHECKPRUNE: call void asm sideeffect "", ""()
+; CHECKPRUNE-NOT: call void @__sanitizer_cov
+; CHECKPRUNE: ret void