Page MenuHomePhabricator

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

Authored by MaskRay on Dec 10 2020, 3:11 PM.



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.

Diff Detail

Event Timeline

MaskRay created this revision.Dec 10 2020, 3:11 PM
MaskRay requested review of this revision.Dec 10 2020, 3:11 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 10 2020, 3:11 PM
MaskRay edited the summary of this revision. (Show Details)Dec 10 2020, 3:46 PM
xinhaoyuan added inline comments.Dec 10 2020, 6:17 PM

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


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


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.


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


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?


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 updated this revision to Diff 311095.Dec 10 2020, 7:26 PM
MaskRay marked 4 inline comments as done.
MaskRay edited the summary of this revision. (Show Details)

Address comments

Improve description


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.


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

MaskRay marked an inline comment as done.Dec 10 2020, 7:27 PM
MaskRay edited the summary of this revision. (Show Details)Dec 10 2020, 9:09 PM
xinhaoyuan accepted this revision.Dec 11 2020, 5:53 PM

LGTM. Left some style nitpicks.


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.




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.

This revision is now accepted and ready to land.Dec 11 2020, 5:53 PM
MaskRay updated this revision to Diff 311349.Dec 11 2020, 6:05 PM
MaskRay marked 3 inline comments as done.
MaskRay edited the summary of this revision. (Show Details)

Fix typo


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


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

MaskRay edited the summary of this revision. (Show Details)Dec 11 2020, 6:06 PM
MaskRay updated this revision to Diff 311353.Dec 11 2020, 6:24 PM

Add a function comment. Delete unneeded traversable clearing.

This revision was landed with ongoing or failed builds.Dec 11 2020, 6:28 PM
This revision was automatically updated to reflect the committed changes.