https://gcc.gnu.org/g:cd025cb953ff9bc23bb348be9e9658b572bb6ebf
commit r17-4998-gcd025cb953ff9bc23bb348be9e9658b572bb6ebf Author: Jørgen Kvalsvik <[email protected]> Date: Thu Oct 8 14:53:12 2026 +0200 Insert with suffixes to subsume non-maximal paths I found that for some very specific graphs we would erroneously preserve non-simple paths. For this to happen then we need this sequence of events: 1. scc_exit_prime_paths produces the largest set of path candidates. 2. This causes it to be base trie the other tries are merged into. 3. A path in scc_exit_prime_paths is a subpath of some path in the other tries. 4. The insert_suffix terminates early because no new nodes are created. This assumes that the remaining suffixes have been inserted already, which is not the case if the path is in (1). The use if insert over insert_with_suffix was an optimization (insert is O(n), insert_with_suffix O(n^2), where n is the length of the path). Because of the structure of the SCCs and the shape of paths we generate there will be reasonably little overlap and few paths will be subsumed, so we don't get get much value from the suffix inserts. Unfortunately, the merge process assumes that suffixes have been inserted to be corrected, and so we must pay the suffix insertion tax. From what I can tell we need the noreturn exit block, and the extra path was the last block before the function end. We happened to prune this path before instrumentation, so the .gcno file reported the correct number of paths - it's gcov that got it wrong. Another viable fix is to never use the scc_exit_prime_paths as our base for insertions, as it is the only one with this problem. This is probably faster on average, but it makes merge() very surprising and sensitive to which of the tries goes where. The compile time cost of prime path instrumentation is dominated by later phases, and this fix is conceptually the right one as insert_with_suffix is the "correct" operation. gcc/ChangeLog: * prime-paths.cc (scc_exit_prime_paths): Call insert_with_suffix. gcc/testsuite/ChangeLog: * gcc.misc-tests/gcov-44.c: New test. Diff: --- gcc/prime-paths.cc | 8 +---- gcc/testsuite/gcc.misc-tests/gcov-44.c | 60 ++++++++++++++++++++++++++++++++++ 2 files changed, 61 insertions(+), 7 deletions(-) diff --git a/gcc/prime-paths.cc b/gcc/prime-paths.cc index f111c72ca3a1..b87cb390f5bd 100644 --- a/gcc/prime-paths.cc +++ b/gcc/prime-paths.cc @@ -1040,13 +1040,7 @@ scc_exit_prime_paths (const struct graph *cfg, const trie &scc_exit_paths, path.reserve (q.length () + r.length ()); path.splice (q); path.splice (r); - /* This can probably insert without subpath elimination because: - 1. Conflicts are *really* rare (see patmatch in tree.c), but they - do happen. - 2. The output of this function is "filtered" through another trie - anyway so the redundant paths generated here will be eliminated - in the consumers at a very low extra cost. */ - trie.insert (path); + trie.insert_with_suffix (path); if (limit_exceed_p (trie.size ())) return trie; } diff --git a/gcc/testsuite/gcc.misc-tests/gcov-44.c b/gcc/testsuite/gcc.misc-tests/gcov-44.c new file mode 100644 index 000000000000..efd761be4d35 --- /dev/null +++ b/gcc/testsuite/gcc.misc-tests/gcov-44.c @@ -0,0 +1,60 @@ +/* { dg-options "-fpath-coverage" } */ +/* { dg-do compile } */ + +extern void abort (void); + +/* We need function calls at specific places to ensure block creation and + construct the right paths. The implementation itself is meaningless. */ +unsigned do1 (unsigned n) { return n; } +unsigned do2 (unsigned n) { return n > 0 ? n - 1 : n; } + +/* Distilled from basenc.c in GNU Coreutils 9.1. + + This targets a bug that would happen when the exit paths would be the most + numerous and be the basis for merge. This could leave non-prime paths in + the final set of prime paths. For this specific example it would be the + last block, just before the function ends, which is clearly not a prime path + on its own. + + This extra path happened to be filtered when writing the .gcno/.gcda entry, + so there was a mismatch between the number of paths in the .gcno file and + what gcov would report (30 paths): + + $ gcov-dump gcov-44.gcno + 11 /gcov-44.gcno: 01000000: 105:FUNCTION [...] `do_decode' gcov-44.c:33:1-53:1 + 12 ./gcov-44.gcno: 01410000: 4:BLOCKS 14 blocks + ... + 38 ./gcov-44.gcno: 01490000: 4:PATHS 29 paths + + BEGIN paths + summary: 0/29 +*/ +void +do_decode() +/* END */ +{ + unsigned n = do1 (100); + do + { + while (do2 (n) > 1500) + { + if (n > 1000) + abort (); + if (n > 100) + break; + n -= 1; + } + + n -= 1; + } + while (do1 (n) > 0); +} + +int +main() +{ + do_decode(); + return 0; +} + +/* { dg-final { run-gcov prime-paths { --prime-paths gcov-44.c } } } */
