From 97260ab4786f87211b8553b56fd0600016b1d6fa Mon Sep 17 00:00:00 2001
From: Xinhao Yuan <xinhaoyuan@gmail.com>
Date: Thu, 10 Dec 2020 15:22:29 -0800
Subject: [PATCH] [llvm-cov][gcov] Optimize the cycle counting algorithm by
 skipping zero count cycles

This change is similar to http://gcc.gnu.org/PR90380

This reduces the complexity from exponential to polynomial of the arcs.

Reviewed By: MaskRay

Differential Revision: https://reviews.llvm.org/D93036
---
 compiler-rt/test/profile/gcov-complex-line.c | 55 ++++++++++++++++++++++++++++
 llvm/include/llvm/ProfileData/GCOV.h         |  1 +
 llvm/lib/ProfileData/GCOV.cpp                | 25 +++++++++++--
 3 files changed, 78 insertions(+), 3 deletions(-)
 create mode 100644 compiler-rt/test/profile/gcov-complex-line.c

diff --git a/compiler-rt/test/profile/gcov-complex-line.c b/compiler-rt/test/profile/gcov-complex-line.c
new file mode 100644
index 0000000..86286c4
--- /dev/null
+++ b/compiler-rt/test/profile/gcov-complex-line.c
@@ -0,0 +1,55 @@
+// This test checks that the cycle detection algorithm in llvm-cov is able to
+// handle complex block graphs by skipping zero count cycles.
+//
+// RUN: mkdir -p %t.dir && cd %t.dir
+// RUN: %clang --coverage %s -o %t
+// RUN: rm -f gcov-complex-line.gcda && %run %t
+// RUN: llvm-cov gcov -t gcov-complex-line.c | FileCheck %s
+
+#define M_0     \
+  do {          \
+    if (x == 0) \
+      x = 0;    \
+    else        \
+      x = 1;    \
+  } while (0)
+#define M_1 \
+  do {      \
+    M_0;    \
+    M_0;    \
+    M_0;    \
+    M_0;    \
+  } while (0)
+#define M_2 \
+  do {      \
+    M_1;    \
+    M_1;    \
+    M_1;    \
+    M_1;    \
+  } while (0)
+#define M_3 \
+  do {      \
+    M_2;    \
+    M_2;    \
+    M_2;    \
+    M_2;    \
+  } while (0)
+#define M_4 \
+  do {      \
+    M_3;    \
+    M_3;    \
+    M_3;    \
+    M_3;    \
+  } while (0)
+#define COMPLEX_LINE              \
+  do {                            \
+    for (int i = 0; i < 100; ++i) \
+      M_4;                        \
+  } while (0)
+
+int main() {
+  volatile int x = 0;
+  // In the following line, the number of cycles in the block graph is at least
+  // 2^256, where 256 is the number of expansions of M_0.
+  COMPLEX_LINE; // CHECK: 101: [[#@LINE]]: COMPLEX_LINE;
+}
diff --git a/llvm/include/llvm/ProfileData/GCOV.h b/llvm/include/llvm/ProfileData/GCOV.h
index 2766ff5..b15c5a6 100644
--- a/llvm/include/llvm/ProfileData/GCOV.h
+++ b/llvm/include/llvm/ProfileData/GCOV.h
@@ -295,6 +295,7 @@ public:
   static uint64_t getCycleCount(const Edges &Path);
   static void unblock(const GCOVBlock *U, BlockVector &Blocked,
                       BlockVectorLists &BlockLists);
+  static void trimZeroCountSuffix(Edges &Path);
   static bool lookForCircuit(const GCOVBlock *V, const GCOVBlock *Start,
                              Edges &Path, BlockVector &Blocked,
                              BlockVectorLists &BlockLists,
diff --git a/llvm/lib/ProfileData/GCOV.cpp b/llvm/lib/ProfileData/GCOV.cpp
index c073525..b8bc0cc 100644
--- a/llvm/lib/ProfileData/GCOV.cpp
+++ b/llvm/lib/ProfileData/GCOV.cpp
@@ -427,6 +427,11 @@ LLVM_DUMP_METHOD void GCOVBlock::dump() const { print(dbgs()); }
 // The algorithm in GCC is based on the algorithm by Hawick & James:
 //   "Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs"
 //   http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf.
+//
+// An optimization is to skip any arc with zero count and to backtrack if the
+// current path has such arcs: any cycle with such arc makes no contribution to
+// the final cycle count. This reduces the complexity from exponential to
+// polynomial of the arcs.
 
 /// Get the count for the detected cycle.
 uint64_t GCOVBlock::getCycleCount(const Edges &Path) {
@@ -458,6 +463,15 @@ void GCOVBlock::unblock(const GCOVBlock *U, BlockVector &Blocked,
   }
 }
 
+void GCOVBlock::trimZeroCountSuffix(Edges &Path) {
+  for (size_t index = 0; index < Path.size(); ++index) {
+    if (Path[index]->cycleCount == 0) {
+      Path.resize(index);
+      return;
+    }
+  }
+}
+
 bool GCOVBlock::lookForCircuit(const GCOVBlock *V, const GCOVBlock *Start,
                                Edges &Path, BlockVector &Blocked,
                                BlockVectorLists &BlockLists,
@@ -465,10 +479,11 @@ bool GCOVBlock::lookForCircuit(const GCOVBlock *V, const GCOVBlock *Start,
   Blocked.push_back(V);
   BlockLists.emplace_back(BlockVector());
   bool FoundCircuit = false;
+  const size_t PrefixLength = Path.size();
 
   for (auto E : V->dsts()) {
     const GCOVBlock *W = &E->dst;
-    if (W < Start || find(Blocks, W) == Blocks.end()) {
+    if (E->cycleCount == 0 || W < Start || find(Blocks, W) == Blocks.end()) {
       continue;
     }
 
@@ -477,6 +492,7 @@ bool GCOVBlock::lookForCircuit(const GCOVBlock *V, const GCOVBlock *Start,
     if (W == Start) {
       // We've a cycle.
       Count += GCOVBlock::getCycleCount(Path);
+      trimZeroCountSuffix(Path);
       FoundCircuit = true;
     } else if (find(Blocked, W) == Blocked.end() && // W is not blocked.
                GCOVBlock::lookForCircuit(W, Start, Path, Blocked, BlockLists,
@@ -484,7 +500,10 @@ bool GCOVBlock::lookForCircuit(const GCOVBlock *V, const GCOVBlock *Start,
       FoundCircuit = true;
     }
 
-    Path.pop_back();
+    if (Path.size() > PrefixLength)
+      Path.pop_back();
+    else if (Path.size() < PrefixLength)
+      break;
   }
 
   if (FoundCircuit) {
@@ -492,7 +511,7 @@ bool GCOVBlock::lookForCircuit(const GCOVBlock *V, const GCOVBlock *Start,
   } else {
     for (auto E : V->dsts()) {
       const GCOVBlock *W = &E->dst;
-      if (W < Start || find(Blocks, W) == Blocks.end()) {
+      if (E->cycleCount == 0 || W < Start || find(Blocks, W) == Blocks.end()) {
         continue;
       }
       const size_t index = find(Blocked, W) - Blocked.begin();
-- 
2.7.4