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

Authored by MaskRay on Dec 11 2020, 6:28 PM.


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

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 identify loops and sum all back edges. However, this requires a
dominator tree construction which is more complex. The time complexity can be
decreased to 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.

Reviewed By: xinhaoyuan

Differential Revision: https://reviews.llvm.org/D93073