https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98257
Bug ID: 98257
Summary: Replace Donald B. Johnson's cycle enumeration with
iterative loop finding
Product: gcc
Version: 11.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: gcov-profile
Assignee: unassigned at gcc dot gnu.org
Reporter: i at maskray dot me
CC: marxin at gcc dot gnu.org
Target Milestone: ---
gcov used _J. C. Tiernan, An Efficient Search Algorithm to Find the Elementary
Circuits of a Graph, Comm ACM 1970_. The worst-case time bound is exponential
in the number of elementary circuits. It enumerated cycles (aka simple circuit,
aka elementary circuit) and performed cycle cancelling.
In 2016, the resolution to PR67992 switched to Donald B. Johnson's algorithm to
improve performance. The theoretical time complexity is $O((V+E)(c+1))$ where
$c$ is the number of cycles, which is exponential in the size of the graph.
(Boost attributed the algorithm to K. A. Hawick and H. A. James, and gcov
inherited this name. However, that paper did not improve Johnson's algorithm.)
Actually every step of cycle cancelling decreases the count of at lease one arc
to 0, so there is at most $O(E)$ cycles. The resolution to PR90380 skipped
non-positive arcs and decreased the time complexity to $O(V*E^2)$ (in theory it
could be $O(E^2)$ but the implementation has a linear scan).
This is all unnecessary. We can just iteratively find cycles (using the
classical tri-color DFS) and perform cycle cancelling. There are at most O(E)
cycles and the overall time complexity is O(E^2).
(
We are processing a reducible flow graph (there is no intuitive cycle count for
an irreducible flow graph).
Every natural loop is identified by a back edge. By constructing a dominator
tree, finding back edges, identifying natural loops and clearing the arc
counters (we will compute incoming counts so we clear counters to prevent
duplicates), the time complexity can be decreased to $O(depthOfNestedLoops*E)$.
In practice, the semi-NCA algorithm (time complexity: $O(V^2)$, but considered
faster than the almost linear Lengauer-Tarjan's algorithm) is not difficult to
implement, but identifying natural loops is troublesome. So the method is not
useful.)
