Index: lib/Transforms/Instrumentation/SanitizerCoverage.cpp =================================================================== --- lib/Transforms/Instrumentation/SanitizerCoverage.cpp +++ lib/Transforms/Instrumentation/SanitizerCoverage.cpp @@ -29,6 +29,8 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SCCIterator.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/PostDominators.h" @@ -435,8 +437,10 @@ return true; } -static bool shouldInstrumentBlock(const Function& F, const BasicBlock *BB, const DominatorTree *DT, - const PostDominatorTree *PDT) { +static bool +shouldInstrumentBlock(const Function &F, const BasicBlock *BB, + const DominatorTree *DT, const PostDominatorTree *PDT, + const SmallSet &SkippedBlocks) { // Don't insert coverage for unreachable blocks: we will never call // __sanitizer_cov() for them, so counting them in // NumberOfInstrumentedBlocks() might complicate calculation of code coverage @@ -448,7 +452,24 @@ if (!ClPruneBlocks || &F.getEntryBlock() == BB) return true; - return !(isFullDominator(BB, DT) || isFullPostDominator(BB, PDT)); + // If a block is full post dominator, then all paths through any of its + // preds pass through the block. + if (isFullPostDominator(BB, PDT)) + return false; + + // It is tempting to skip all pre dominators as well, but the argument + // doesn't work anymore, because some successors might already be skipped. + // This is a conservative solution of finding minimum set of + // independent coverage points. + if (isFullDominator(BB, DT)) { + for (const BasicBlock *SUCC : make_range(succ_begin(BB), succ_end(BB))) + if (SkippedBlocks.find(SUCC) != SkippedBlocks.end()) + return true; + + return false; + } + + return true; } bool SanitizerCoverageModule::runOnFunction(Function &F) { @@ -473,6 +494,7 @@ SplitAllCriticalEdges(F); SmallVector IndirCalls; SmallVector BlocksToInstrument; + SmallSet SkippedBlocks; SmallVector CmpTraceTargets; SmallVector SwitchTraceTargets; SmallVector DivTraceTargets; @@ -483,30 +505,36 @@ const PostDominatorTree *PDT = &getAnalysis(F).getPostDomTree(); - for (auto &BB : F) { - if (shouldInstrumentBlock(F, &BB, DT, PDT)) - 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(&Inst)) - CmpTraceTargets.push_back(&Inst); - if (isa(&Inst)) - SwitchTraceTargets.push_back(&Inst); + // Traverse blocks in reverse topological order wrt DominatorTree. + for (auto SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI) { + for (BasicBlock *BB : *SCCI) { + if (shouldInstrumentBlock(F, BB, DT, PDT, SkippedBlocks)) + BlocksToInstrument.push_back(BB); + else + SkippedBlocks.insert(BB); + + for (auto &Inst : *BB) { + if (Options.IndirectCalls) { + CallSite CS(&Inst); + if (CS && !CS.getCalledFunction()) + IndirCalls.push_back(&Inst); + } + if (Options.TraceCmp) { + if (isa(&Inst)) + CmpTraceTargets.push_back(&Inst); + if (isa(&Inst)) + SwitchTraceTargets.push_back(&Inst); + } + if (Options.TraceDiv) + if (BinaryOperator *BO = dyn_cast(&Inst)) + if (BO->getOpcode() == Instruction::SDiv || + BO->getOpcode() == Instruction::UDiv) + DivTraceTargets.push_back(BO); + if (Options.TraceGep) + if (GetElementPtrInst *GEP = dyn_cast(&Inst)) + GepTraceTargets.push_back(GEP); } - if (Options.TraceDiv) - if (BinaryOperator *BO = dyn_cast(&Inst)) - if (BO->getOpcode() == Instruction::SDiv || - BO->getOpcode() == Instruction::UDiv) - DivTraceTargets.push_back(BO); - if (Options.TraceGep) - if (GetElementPtrInst *GEP = dyn_cast(&Inst)) - GepTraceTargets.push_back(GEP); - } + } } InjectCoverage(F, BlocksToInstrument); @@ -517,6 +545,7 @@ InjectTraceForGep(F, GepTraceTargets); return true; } + void SanitizerCoverageModule::CreateFunctionGuardArray(size_t NumGuards, Function &F) { if (!Options.TracePCGuard) return; Index: test/Instrumentation/SanitizerCoverage/prune-blocks.ll =================================================================== --- /dev/null +++ test/Instrumentation/SanitizerCoverage/prune-blocks.ll @@ -0,0 +1,130 @@ +; First example from https://github.com/google/sanitizers/issues/783 +; RUN: opt < %s -sancov -sanitizer-coverage-level=4 -sanitizer-coverage-trace-pc -sanitizer-coverage-prune-blocks=1 -S | FileCheck %s --check-prefix=CHECK + +source_filename = "reduced.c" +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: noinline nounwind uwtable +define i32 @foo(i8 signext %c, i32 %state, i32 %threshold) #0 { +entry: + %c.addr = alloca i8, align 1 + %state.addr = alloca i32, align 4 + %threshold.addr = alloca i32, align 4 + store i8 %c, i8* %c.addr, align 1 + store i32 %state, i32* %state.addr, align 4 + store i32 %threshold, i32* %threshold.addr, align 4 + br label %while.cond + +; CHECK-LABEL: entry: +; CHECK: call void @__sanitizer_cov_trace_pc() + +while.cond: ; preds = %sw.epilog, %entry + %0 = load i32, i32* %state.addr, align 4 + %1 = load i32, i32* %threshold.addr, align 4 + %cmp = icmp slt i32 %0, %1 + br i1 %cmp, label %while.body, label %while.end + +; CHECK-LABEL: while.cond: +; CHECK-NOT: call void @__sanitizer_cov_trace_pc() + +while.body: ; preds = %while.cond + %2 = load i32, i32* %state.addr, align 4 + switch i32 %2, label %sw.epilog [ + i32 1, label %sw.bb + i32 2, label %sw.bb9 + ] + +; CHECK-LABEL: while.body: +; CHECK-NOT: call void @__sanitizer_cov_trace_pc() +; CHECK-LABEL: while.body.sw.epilog_crit_edge: +; CHECK: call void @__sanitizer_cov_trace_pc() + +sw.bb: ; preds = %while.body + call void @clobber1(i32* %state.addr) + %3 = load i8, i8* %c.addr, align 1 + %conv = sext i8 %3 to i32 + %cmp1 = icmp eq i32 %conv, 42 + br i1 %cmp1, label %if.then, label %if.else + +; CHECK-LABEL: sw.bb: +; CHECK: call void @__sanitizer_cov_trace_pc() + +if.then: ; preds = %sw.bb + %4 = load i32, i32* %state.addr, align 4 + %inc = add nsw i32 %4, 1 + store i32 %inc, i32* %state.addr, align 4 + br label %if.end8 + +; CHECK-LABEL: if.then: +; CHECK: call void @__sanitizer_cov_trace_pc() + +if.else: ; preds = %sw.bb + %5 = load i8, i8* %c.addr, align 1 + %conv3 = sext i8 %5 to i32 + %cmp4 = icmp eq i32 %conv3, 47 + br i1 %cmp4, label %if.then6, label %if.else7 + +; CHECK-LABEL: if.else: +; CHECK-NOT: call void @__sanitizer_cov_trace_pc() + +if.then6: ; preds = %if.else + %6 = load i32, i32* %state.addr, align 4 + %dec = add nsw i32 %6, -1 + store i32 %dec, i32* %state.addr, align 4 + br label %if.end + +; CHECK-LABEL: if.then6: +; CHECK: call void @__sanitizer_cov_trace_pc() + +if.else7: ; preds = %if.else + call void @clobber1(i32* %state.addr) + br label %out + +; CHECK-LABEL: if.else7: +; CHECK: call void @__sanitizer_cov_trace_pc() + +if.end: ; preds = %if.then6 + br label %if.end8 + +; CHECK-LABEL: if.end: +; CHECK-NOT: call void @__sanitizer_cov_trace_pc() + +if.end8: ; preds = %if.end, %if.then + call void @clobber2(i32* %state.addr) + br label %sw.epilog + +; CHECK-LABEL: if.end8: +; CHECK-NOT: call void @__sanitizer_cov_trace_pc() + +sw.bb9: ; preds = %while.body + call void @clobber3(i32* %state.addr) + br label %sw.epilog + +; CHECK-LABEL: sw.bb9: +; CHECK: call void @__sanitizer_cov_trace_pc() + +sw.epilog: ; preds = %while.body, %sw.bb9, %if.end8 + br label %while.cond + +; CHECK-LABEL: sw.epilog: +; CHECK-NOT: call void @__sanitizer_cov_trace_pc() + +while.end: ; preds = %while.cond + br label %out + +; CHECK-LABEL: while.end: +; CHECK: call void @__sanitizer_cov_trace_pc() + +out: ; preds = %while.end, %if.else7 + %7 = load i32, i32* %state.addr, align 4 + ret i32 %7 + +; CHECK-LABEL: out: +; CHECK-NOT: call void @__sanitizer_cov_trace_pc() +} + +declare void @clobber1(i32*) #1 +declare void @clobber2(i32*) #1 +declare void @clobber3(i32*) #1 +