[llvm-cov gcov] Replace Donald B. Johnson's cycle enumeration with iterative cycle finding

[MaskRay]

Summary

gcov computes the line execution count as the sum of (a) counts from
predecessors on other lines and (b) the sum of loop execution counts of blocks
on the same line (think of loops on one line).

For (b), we use Donald B. Johnson's cycle enumeration algorithm and perform
cycle cancelling for each cycle. This number of candidate cycles were
exponential and D93036 made it polynomial by skipping zero count cycles. The
time complexity is high (O(V*E^2) (it could be O(E^2) but the linear Blocks
check made it higher) and the implementation is complex.

We could just find all back edges (each corresponds to a natural loop) and sum
their counts. However, this requires a dominator tree construction which is more
complex. The time complexity can be almost linear, though.

This patch just performs cycle cancelling iteratively. Add two members
traversable and incoming to GCOVArc. There are 3 states:

• !traversable: blocks not on this line or explored blocks
• traversable && incoming == nullptr: unexplored blocks
• traversable && incoming != nullptr: blocks which are being explored (on the stack)

If an arc points to a block being explored, a cycle has been found.

Let E be the number of arcs. Every time a cycle is found, at least one arc is
saturated (edgeCount reduced to 0), so there are at most E cycles. Finding one
cycle takes O(E) time, so the overall time complexity is O(E^2). Note that we
always augment through a back edge and never need to augment its reverse edge so
reverse edges in traditional flow networks are not needed.

[xinhaoyuan]

llvm/lib/ProfileData/GCOV.cpp

445

nitnit: without the context of network-flow it looks like the function is "reducing" or "cancelling" a cycle. maybe fine to keep it.

450

Is it possible to have self-arc? If so this pointer would be de-referenced below.

452

nit: maybe not reuse the argument variable? it would also help avoid de-referencing the special pointer value by matching block pointer with the start block.

463–468

nit: maybe MinCount? this seems a bit off without the context of network-flow.

463–471

the control flow of the loops seems duplicated yet tricky. would it be more readable to first extract the path into a vector and apply simple loops on it?

477

when returned with a cycle found. "incoming" of the blocks on the cycle would not be cleared. can it lead to undefined behaviors in the subsequent traversal?

[MaskRay]

Address comments

Improve description

llvm/lib/ProfileData/GCOV.cpp

450

Neither GCC nor Clang can produce self arcs. gcov instrumentation splits critical edges. With a self arc, the from-vertex will have more than one outgoing arcs and the to-vertex will have more than one incoming arcs. Such edges must have been split.

But thanks for the reminder: we should guard against bad input. So I added a self arc check.

477

Good catch! I'll set the visited bits for these blocks.

[xinhaoyuan]

LGTM. Left some style nitpicks.

llvm/lib/ProfileData/GCOV.cpp

429

nit: you can define stack as a local variable. e.g.

std::vector<std::pair<GCOVBlock *, size_t>> stack = {{src, 0}};

making it an argument probably is more efficient, but I think the performance benefit is marginal - leaving it to you.

446

saturated

477

On second thought, I think "traversable" of the blocks should be be all false at L495, since the loop exits only when all blocks are traversed with no loop found. but I think it is fine to keep the cleanup as a safe guard.

[MaskRay]

Fix typo

llvm/lib/ProfileData/GCOV.cpp

429

Yeah: to reduce memory allocations. I'll keep it.

477

Blocks which haven't been fully explored may have their traversable bits set. L495 is needed.

[MaskRay]

Add a function comment. Delete unneeded traversable clearing.

llvm/include/llvm/ProfileData/GCOV.h

public:
 
   iterator_range<EdgeIterator> dsts() const {
     return make_range(succ.begin(), succ.end());
   }
 
   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
+  augmentOneCycle(GCOVBlock *src,
+                  std::vector<std::pair<GCOVBlock *, size_t>> &stack);
+  static uint64_t getCyclesCount(const BlockVector &blocks);
   static uint64_t getLineCount(const BlockVector &Blocks);
 
 public:
   uint32_t number;
   uint64_t count = 0;
   SmallVector<GCOVArc *, 2> pred;
   SmallVector<GCOVArc *, 2> succ;
   SmallVector<uint32_t, 4> lines;
+  bool traversable = false;
+  GCOVArc *incoming = nullptr;
 };
 
 void gcovOneInput(const GCOV::Options &options, StringRef filename,
                   StringRef gcno, StringRef gcda, GCOVFile &file);
 
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_GCOV_H

llvm/lib/ProfileData/GCOV.cpp

 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 /// dump - Dump GCOVBlock content to dbgs() for debugging purposes.
 LLVM_DUMP_METHOD void GCOVBlock::dump() const { print(dbgs()); }
 #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) {
-    E->cycleCount -= CycleCount;
-  }
-  return CycleCount;
-}
-
-/// Unblock a vertex previously marked as blocked.
-void GCOVBlock::unblock(const GCOVBlock *U, BlockVector &Blocked,
-                        BlockVectorLists &BlockLists) {
-  auto it = find(Blocked, U);
-  if (it == Blocked.end()) {
-    return;
-  }
-
-  const size_t index = it - Blocked.begin();
-  Blocked.erase(it);
-
-  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 (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)
+uint64_t
+GCOVBlock::augmentOneCycle(GCOVBlock *src,
+                           std::vector<std::pair<GCOVBlock *, size_t>> &stack) {
+  GCOVBlock *u;
+  size_t i;
+  stack.clear();
+  stack.emplace_back(src, 0);
+  src->incoming = (GCOVArc *)1; // Mark u available for cycle detection
+  for (;;) {
+    std::tie(u, i) = stack.back();
+    if (i == u->succ.size()) {
+      u->traversable = false;
+      stack.pop_back();
+      if (stack.empty())
         break;
-  }
-
-  if (FoundCircuit) {
-    GCOVBlock::unblock(V, Blocked, BlockLists);
-  } else {
-    for (auto E : V->dsts()) {
-      const GCOVBlock *W = &E->dst;
-      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);
-      }
+    ++stack.back().second;
+    GCOVArc *succ = u->succ[i];
+    // Ignore saturated arcs (cycleCount has been reduced to 0) and visited
+    // blocks. Ignore self arcs to guard against bad input (.gcno has no
+    // self arcs).
+    if (succ->cycleCount == 0 || !succ->dst.traversable || &succ->dst == u)
+      continue;
+    if (succ->dst.incoming == nullptr) {
+      succ->dst.incoming = succ;
+      stack.emplace_back(&succ->dst, 0);
+      continue;
+    }
+    uint64_t minCount = succ->cycleCount;
+    for (GCOVBlock *v = u;;) {
+      minCount = std::min(minCount, v->incoming->cycleCount);
+      v = &v->incoming->src;
+      if (v == &succ->dst)
+        break;
+    succ->cycleCount -= minCount;
+    for (GCOVBlock *v = u;;) {
+      v->incoming->cycleCount -= minCount;
+      v = &v->incoming->src;
+      if (v == &succ->dst)
+        break;
     }
+    return minCount;
   }
-
-  return FoundCircuit;
+  return 0;
 }
 
 /// Get the count for the list of blocks which lie on the same line.
-void GCOVBlock::getCyclesCount(const BlockVector &Blocks, uint64_t &Count) {
-  for (auto Block : Blocks) {
-    Edges Path;
-    BlockVector Blocked;
-    BlockVectorLists BlockLists;
-
-    GCOVBlock::lookForCircuit(Block, Block, Path, Blocked, BlockLists, Blocks,
-                              Count);
+uint64_t GCOVBlock::getCyclesCount(const BlockVector &blocks) {
+  std::vector<std::pair<GCOVBlock *, size_t>> stack;
+  uint64_t count = 0, d;
+  for (;;) {
+    // Make blocks on the line traversable and try finding a cycle.
+    for (auto b : blocks) {
+      const_cast<GCOVBlock *>(b)->traversable = true;
+      const_cast<GCOVBlock *>(b)->incoming = nullptr;
+    }
+    d = 0;
+    for (auto block : blocks) {
+      auto *b = const_cast<GCOVBlock *>(block);
+      if (b->traversable && (d = augmentOneCycle(b, stack)) > 0)
+        break;
+    }
+    if (d == 0)
+      break;
+    // Found one cycle. Keep finding other cycles.
+    count += d;
   }
+  // Mark the blocks non-traversable for the subsequent calls.
+  for (auto b : blocks)
+    const_cast<GCOVBlock *>(b)->traversable = false;
+  return count;
 }
 
 //===----------------------------------------------------------------------===//
 // FileInfo implementation.
 
 // Format dividend/divisor as a percentage. Return 1 if the result is greater
 // than 0% and less than 1%.
 static uint32_t formatPercentage(uint64_t dividend, uint64_t divisor) {
if (b->number == 0) {
       for (const GCOVArc *arc : b->pred)
         if (!llvm::is_contained(line.blocks, &arc->src))
           count += arc->count;
     }
     for (GCOVArc *arc : b->succ)
       arc->cycleCount = arc->count;
   }
 
-  GCOVBlock::getCyclesCount(line.blocks, count);
+  count += GCOVBlock::getCyclesCount(line.blocks);
   line.count = count;
   if (line.exists) {
     ++summary->lines;
     if (line.count != 0)
       ++summary->linesExec;
   }
 
   if (options.BranchInfo)