A simple coverage optimization

[george.karpenkov]

Summary

A simple coverage optimization: if the node has no successors, but multiple predecessors, do not instrument, as predecessors would be instrumented.
Landing this commit would allow us to revert the changes done to tests in https://github.com/llvm-mirror/llvm/commit/1f57bbafaf2dd66752e859d523f941c0b035ec8d

[kcc]

Hm... I keep not liking this...
A very simple test case will get too many extra edges instrumented if we get rid of PDOMs, even with your extra optimization.
I have such test, but would you like to come up with a test of your own?
If you give up, I'll send mine.

[george.karpenkov]

too many extra edges instrumented

weren't the benchmarks showing ~15%?

I have such test

yes please, do send it.

but would you like to come up with a test of your own?

I have a very artificial one, see attached. I am not sure that it counts, and the fact that "too many" is not formally defined makes it more difficult.

[kcc]

void foo(int *a, int *b) {

if (*a > 0) {
  b[1] = 0;
  if (*a > 10) {
    b[3] = 0;
  } else {
    b[4] = 0;
  }
} else {
  if (*a < -10) {
    b[5] = 0;
  } else {
    b[6] = 0;
  }
  b[2] = 0;
}

}

[george.karpenkov]

@kcc, right, missed that entirely.
What about "is a full post-dominator AND has more than one predecessors" ?
Solves these issues, and ensures that predecessor nodes are not full dominators, yet becomes close to the initial solution in D31266.
Alternatively, I can just take D31266 and add shorter tests.

[kcc]

What about "is a full post-dominator AND has more than one predecessors" ?

Yes, I was thinking about this, or, maybe actually
"is a full post-dominator AND has more than one *different* predecessor"
(I don't know if it's possible to have one block to be listed twice in the pred list)

[george.karpenkov]

(I don't know if it's possible to have one block to be listed twice in the pred list)

Almost certainly not, from a brief glance quite a lot of code in LLVM codebase relies on getSinglePredecessor check, including dominator tree calculation.

[george.karpenkov]

so can I make this change + use your test case to verify that we don't end up with extra instrumentation?

[kcc]

In D33472#762849, @george.karpenkov wrote:

so can I make this change + use your test case to verify that we don't end up with extra instrumentation?

Yes, let's try that (except that the test should be .ll, not .cc)

[george.karpenkov]

let's drop this in favor of a better optimization.

lib/Transforms/Instrumentation/SanitizerCoverage.cpp

static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB,
   // Don't insert coverage into blocks without a valid insertion point
   // (catchswitch blocks).
   if (BB->getFirstInsertionPt() == BB->end())
     return false;
 
   if (Options.NoPrune || &F.getEntryBlock() == BB)
     return true;
 
+  // Do not instrument blocks with no successors and multiple predecessors.
+  if (succ_begin(BB) == succ_end(BB)
+      && BB->getSinglePredecessor() == nullptr)
+    return false;
+
   return !isFullDominator(BB, DT);
 }
 
 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.

test/Instrumentation/SanitizerCoverage/coverage.ll

 ; CHECK1: call void @__sanitizer_cov_module_init({{.*}}, i64 2, {{.*}}@__sancov_gen_modname
 ; CHECK1: ret
 
 ; CHECK_WITH_CHECK-LABEL: define void @foo
 ; CHECK_WITH_CHECK: __sanitizer_cov_with_check
 ; CHECK_WITH_CHECK: ret void
 ; CHECK_WITH_CHECK-LABEL: define internal void @sancov.module_ctor
 ; CHECK_WITH_CHECK-NOT: ret
-; CHECK_WITH_CHECK: call void @__sanitizer_cov_module_init({{.*}}, i64 4,
+; CHECK_WITH_CHECK: call void @__sanitizer_cov_module_init({{.*}}, i64 3,
 ; CHECK_WITH_CHECK: ret
 
 ; CHECK2-LABEL: define void @foo
 ; CHECK2: call void @__sanitizer_cov
 ; CHECK2: call void asm sideeffect "", ""()
 ; CHECK2: call void @__sanitizer_cov
 ; CHECK2: call void asm sideeffect "", ""()
 ; CHECK2: call void asm sideeffect "", ""()
 ; CHECK2-NOT: call void @__sanitizer_cov
 ; CHECK2: ret void
 
 ; CHECK2-LABEL: define internal void @sancov.module_ctor
 ; CHECK2-NOT: ret
-; CHECK2: call void @__sanitizer_cov_module_init({{.*}}, i64 4,
+; CHECK2: call void @__sanitizer_cov_module_init({{.*}}, i64 3,
 ; CHECK2: ret
 
 ; CHECK3-LABEL: define void @foo
 ; CHECK3: call void @__sanitizer_cov
 ; CHECK3: call void @__sanitizer_cov
 ; CHECK3-NOT: ret void
 ; CHECK3: call void @__sanitizer_cov
-; CHECK3: call void @__sanitizer_cov
 ; CHECK3-NOT: call void @__sanitizer_cov
 ; CHECK3: ret void
 
 %struct.StructWithVptr = type { i32 (...)** }
 
 define void @CallViaVptr(%struct.StructWithVptr* %foo) uwtable sanitize_address {
 entry:
   %0 = bitcast %struct.StructWithVptr* %foo to void (%struct.StructWithVptr*)***

 entry:
   unreachable
 }
 
 ; CHECKPRUNE-LABEL: define void @foo
 ; CHECKPRUNE: call void @__sanitizer_cov
 ; CHECKPRUNE: call void @__sanitizer_cov
 ; CHECKPRUNE: call void @__sanitizer_cov
-; CHECKPRUNE: call void @__sanitizer_cov
 ; CHECKPRUNE-NOT: call void @__sanitizer_cov
 ; CHECKPRUNE: ret void

test/Instrumentation/SanitizerCoverage/tracing.ll

entry:
   if.end:                                           ; preds = %entry, %if.then
   ret void
 }
 
 ; CHECK_PC-LABEL: define void @foo
 ; CHECK_PC: call void @__sanitizer_cov_trace_pc
 ; CHECK_PC: call void @__sanitizer_cov_trace_pc
 ; CHECK_PC: call void @__sanitizer_cov_trace_pc
-; CHECK_PC: call void @__sanitizer_cov_trace_pc
 ; CHECK_PC-NOT: call void @__sanitizer_cov_trace_pc
 ; CHECK_PC: ret void
 ; CHECK_PC-NOT: call void @__sanitizer_cov_module_init
 
 ; CHECK_PC_GUARD-LABEL: define void @foo
 ; CHECK_PC_GUARD: call void @__sanitizer_cov_trace_pc_guard
 ; CHECK_PC_GUARD: call void @__sanitizer_cov_trace_pc_guard
 ; CHECK_PC_GUARD: call void @__sanitizer_cov_trace_pc_guard
-; CHECK_PC_GUARD: call void @__sanitizer_cov_trace_pc_guard
 ; CHECK_PC_GUARD-NOT: call void @__sanitizer_cov_trace_pc
 ; CHECK_PC_GUARD: ret void
 ; CHECK_PC_GUARD: call void @__sanitizer_cov_trace_pc_guard_init(i32* bitcast (i32** @__start___sancov_guards to i32*), i32* bitcast (i32** @__stop___sancov_guards to i32*))
 
 ; CHECK_PC_GUARD_DARWIN-LABEL: define void @foo
 ; CHECK_PC_GUARD_DARWIN: call void @__sanitizer_cov_trace_pc_guard
 ; CHECK_PC_GUARD_DARWIN: call void @__sanitizer_cov_trace_pc_guard
 ; CHECK_PC_GUARD_DARWIN: call void @__sanitizer_cov_trace_pc_guard
-; CHECK_PC_GUARD_DARWIN: call void @__sanitizer_cov_trace_pc_guard
 ; CHECK_PC_GUARD_DARWIN-NOT: call void @__sanitizer_cov_trace_pc
 ; CHECK_PC_GUARD_DARWIN: ret void
 ; CHECK_PC_GUARD_DARWIN: call void @__sanitizer_cov_trace_pc_guard_init(i32* bitcast (i32** @"\01section$start$__DATA$__sancov_guards" to i32*), i32* bitcast (i32** @"\01section$end$__DATA$__sancov_guards" to i32*))