[llvm-cov][gcov] Optimize the cycle counting algorithm by skipping zero count cycles

[xinhaoyuan]

Summary

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

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

[xinhaoyuan]

Update by running git clang-format.

[xinhaoyuan]

Add a reviewer.

[xinhaoyuan]

Hi,

This is the first patch I submitted to LLVM. Please let me know if anything is missing. Thanks!

[xinhaoyuan]

Correct the test after clang-format.

[xinhaoyuan]

Non-functional change to make clang-tidy happy.

[MaskRay]

Thanks for the patch! Probably worth mentioning that this is similar to http://gcc.gnu.org/PR90380

I believe this patch essentially uses David B Johnson's cycle enumeration algorithm to perform Klein's cycle cancelling method. I'll follow up and switch to Edmonds-Karp for simplicity.

complex-line.gcno is too large (153KiB). If you name the source file a.c and use the relative filename when compiling, it can be smaller.
But I think this probably should be a runtime test: compiler-rt/test/profile/gcov-complex-line.c

[xinhaoyuan]

Move the test to compiler-rt/test/profile, and get rid of the generated files.

Also add a check to match the result count.

[xinhaoyuan]

Minor comment change.

[xinhaoyuan]

I've revised the patch according to the suggestions. Please take another look.

[MaskRay]

Thanks!

compiler-rt/test/profile/gcov-complex-line.c

7

This line can be deleted since checking the existence of .gcno is out of the scope of this patch.

56

[[@LINE]] is a deprecated FileCheck syntax. Use [[#@LINE]]

[xinhaoyuan]

Revision before submitting.

compiler-rt/test/profile/gcov-complex-line.c

+// 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;
+}

llvm/include/llvm/ProfileData/GCOV.h

public:
   }
 
   void print(raw_ostream &OS) const;
   void dump() const;
 
   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,
                              const BlockVector &Blocks, uint64_t &Count);
   static void getCyclesCount(const BlockVector &Blocks, uint64_t &Count);
   static uint64_t getLineCount(const BlockVector &Blocks);
 
 public:

llvm/lib/ProfileData/GCOV.cpp

 #endif
 
 //===----------------------------------------------------------------------===//
 // Cycles detection
 //
 // 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) {
   uint64_t CycleCount = std::numeric_limits<uint64_t>::max();
   for (auto E : Path) {
     CycleCount = std::min(E->cycleCount, CycleCount);
   }
   for (auto E : Path) {
void GCOVBlock::unblock(const GCOVBlock *U, BlockVector &Blocked,
 
   const BlockVector ToUnblock(BlockLists[index]);
   BlockLists.erase(BlockLists.begin() + index);
   for (auto GB : ToUnblock) {
     GCOVBlock::unblock(GB, Blocked, BlockLists);
   }
 }
 
+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,
                                const BlockVector &Blocks, uint64_t &Count) {
   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;
     }
 
     Path.push_back(E);
 
     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,
                                          Blocks, Count)) {
       FoundCircuit = true;
     }
 
+    if (Path.size() > PrefixLength)
       Path.pop_back();
+    else if (Path.size() < PrefixLength)
+      break;
   }
 
   if (FoundCircuit) {
     GCOVBlock::unblock(V, Blocked, BlockLists);
   } 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();
       BlockVector &List = BlockLists[index];
       if (find(List, V) == List.end()) {
         List.push_back(V);
       }
     }