Groups | Search | Server Info | Login | Register

Groups > comp.compilers > #3657

Paper: Prime Path Coverage in the GNU Compiler Collection

Show all headers | View raw

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

Back to comp.compilers | Previous | Next | Find similar

Thread

Paper: Prime Path Coverage in the GNU Compiler Collection John R Levine <johnl@taugh.com> - 2025-05-22 12:59 -0400

csiph-web