2025/04/25 by Jørgen Kvalsvik, Kvalsvik, Jørgen · 1 voice
Computer Science · #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2505.14694
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.