Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.14694 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908372731691008 |
|---|---|
| author | Kvalsvik, Jørgen |
| author_facet | Kvalsvik, Jørgen |
| contents | 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(n^2m)$ from $O(n^2m^2)$, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14694 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Prime Path Coverage in the GNU Compiler Collection Kvalsvik, Jørgen Programming Languages 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(n^2m)$ from $O(n^2m^2)$, 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. |
| title | Prime Path Coverage in the GNU Compiler Collection |
| topic | Programming Languages |
| url | https://arxiv.org/abs/2505.14694 |