GCC 15.1 released, and a paper on prime path coverage (in preprint)
GCC 15.1 was released
today, and
it comes with prime path coverage support! Try it out and build your
programs with -fpath-coverage, it truly is a brilliant metric.
I wrote another paper detailing the implementation of the prime path coverage support. You can get a copy here or from arxiv (once it is processed).
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.
I would like two emphasize two particular features of the paper; that prime path coverage subsumes MC/DC, and that suffix trees are fabulous improvement when enumerating paths. There are more details in the paper, and maybe I’ll do a separate post. One day.
Happy testing!