[sanitizer-coverage] prune trace-cmp instrumentation for CMP isntructions that feed into the backedge branch. Instrumenting these CMP instructions is almost always useless (and harmful) for fuzzing

llvm-svn: 352818

3 files changed, 69 insertions, 2 deletions

diff --git a/clang/docs/SanitizerCoverage.rst b/clang/docs/SanitizerCoverage.rst
index 728aa2f77fc..c5c50a5dd96 100644
--- a/clang/docs/SanitizerCoverage.rst
+++ b/clang/docs/SanitizerCoverage.rst
@@ -248,6 +248,9 @@ and with  ``-fsanitize-coverage=trace-gep`` --
 the `LLVM GEP instructions <https://llvm.org/docs/GetElementPtr.html>`_
 (to capture array indices).
 
+Unless ``no-prune`` option is provided, some of the comparison instructions
+will not be instrumented.
+
 .. code-block:: c++
 
   // Called before a comparison instruction.
diff --git a/llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp b/llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp
index 6d98c66ee68..c96c5928881 100644
--- a/llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp
+++ b/llvm/lib/Transforms/Instrumentation/SanitizerCoverage.cpp
@@ -483,6 +483,37 @@ static bool shouldInstrumentBlock(const Function &F, const BasicBlock *BB,
     && !(isFullPostDominator(BB, PDT) && !BB->getSinglePredecessor());
 }
 
+
+// Returns true iff From->To is a backedge.
+// A twist here is that we treat From->To as a backedge if
+//   * To dominates From or
+//   * To->UniqueSuccessor dominates From
+static bool IsBackEdge(BasicBlock *From, BasicBlock *To,
+                       const DominatorTree *DT) {
+  if (DT->dominates(To, From))
+    return true;
+  if (auto Next = To->getUniqueSuccessor())
+    if (DT->dominates(Next, From))
+      return true;
+  return false;
+}
+
+// Prunes uninteresting Cmp instrumentation:
+//   * CMP instructions that feed into loop backedge branch.
+//
+// Note that Cmp pruning is controlled by the same flag as the
+// BB pruning.
+static bool IsInterestingCmp(ICmpInst *CMP, const DominatorTree *DT,
+                             const SanitizerCoverageOptions &Options) {
+  if (!Options.NoPrune)
+    if (CMP->hasOneUse())
+      if (auto BR = dyn_cast<BranchInst>(CMP->user_back()))
+        for (BasicBlock *B : BR->successors())
+          if (IsBackEdge(BR->getParent(), B, DT))
+            return false;
+  return true;
+}
+
 bool SanitizerCoverageModule::runOnFunction(Function &F) {
   if (F.empty())
     return false;
@@ -531,8 +562,9 @@ bool SanitizerCoverageModule::runOnFunction(Function &F) {
           IndirCalls.push_back(&Inst);
       }
       if (Options.TraceCmp) {
-        if (isa<ICmpInst>(&Inst))
-          CmpTraceTargets.push_back(&Inst);
+        if (ICmpInst *CMP = dyn_cast<ICmpInst>(&Inst))
+          if (IsInterestingCmp(CMP, DT, Options))
+            CmpTraceTargets.push_back(&Inst);
         if (isa<SwitchInst>(&Inst))
           SwitchTraceTargets.push_back(&Inst);
       }
diff --git a/llvm/test/Instrumentation/SanitizerCoverage/backedge-pruning.ll b/llvm/test/Instrumentation/SanitizerCoverage/backedge-pruning.ll
new file mode 100644
index 00000000000..10319831127
--- /dev/null
+++ b/llvm/test/Instrumentation/SanitizerCoverage/backedge-pruning.ll
@@ -0,0 +1,32 @@
+; Test -sanitizer-coverage-trace-compares=1 and how it prunes backedge compares.
+; RUN: opt < %s -sancov -sanitizer-coverage-level=1 -sanitizer-coverage-trace-compares=1  -sanitizer-coverage-prune-blocks=1 -S | FileCheck %s --check-prefix=PRUNE
+; RUN: opt < %s -sancov -sanitizer-coverage-level=1 -sanitizer-coverage-trace-compares=1  -sanitizer-coverage-prune-blocks=0 -S | FileCheck %s --check-prefix=NOPRUNE
+
+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 dso_local void @foo(i32* nocapture readnone %a, i32 %n) local_unnamed_addr {
+entry:
+  br label %do.body
+
+do.body:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %do.body ]
+  tail call void (...) @bar()
+  %inc = add nuw nsw i32 %i.0, 1
+  %cmp = icmp slt i32 %inc, %n
+;PRUNE-LABEL: foo
+;PRUNE-NOT: __sanitizer_cov_trace_cmp4
+;PRUNE: ret void
+
+;NOPRUNE-LABEL: foo
+;NOPRUNE: call void @__sanitizer_cov_trace_cmp4
+;NOPRUNE-NEXT: icmp
+;NOPRUNE: ret void
+
+  br i1 %cmp, label %do.body, label %do.end
+
+do.end:
+  ret void
+}
+
+declare dso_local void @bar(...) local_unnamed_addr