Paper: Prime Path Coverage in the GNU Compiler Collection

How GCC tries to test all the code paths efficiently.


Abstract


We describe the implementation of the prime path coverage support
introduced the GNU Compiler Collection 15, a structural coverage metric
that focuses on paths of execution through the program. Prime path
coverage strikes a good balance between the number of tests and coverage,
and requires that loops are taken, taken more than once, and skipped. We
show that prime path coverage subsumes modified condition/decision
coverage (MC/DC). We improve on the current state-of-the-art algorithms
for enumerating prime paths by using a suffix tree for efficient pruning
of duplicated and redundant subpaths, reducing it to O(n2m) from O(n2m2),
where n is the length of the longest path and m is the number of candidate
paths. We can efficiently track candidate paths using a few bitwise
operations based on a compact representation of the indices of the ordered
prime paths. By analyzing the control flow graph, GCC can observe and
instrument paths in a language-agnostic manner, and accurately report what
code must be run in what order to achieve coverage.


https://arxiv.org/abs/2505.14694


Regards,
John Levine, johnl@taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

Return to the comp.compilers page.
Search the comp.compilers archives again.