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.
---
Bootstrapped and tested on x86_64-linux-gnu. The change itself is rather
low risk (insert -> insert_with_suffix just strengthens GCC, really, at
the cost of some performance). I hope pushing this fix as almost obvious
was not out of line; the fix is trivial and reasonable, I think, but it
is backed by hours of debugging and tracing.
If you would rather have merge() tuned, let me know and I can implement
it.
This fix should maybe be backported to GCC 15-16 releases as gcov in
those cases will produce slightly off reports, but even then the risk
feels low.
---
gcc/ChangeLog:
* prime-paths.cc (scc_exit_prime_paths): Call
insert_with_suffix.
gcc/testsuite/ChangeLog:
* gcc.misc-tests/gcov-44.c: New test.
---
gcc/prime-paths.cc | 8 +---
gcc/testsuite/gcc.misc-tests/gcov-44.c | 60 ++++++++++++++++++++++++++
2 files changed, 61 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-44.c
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 } } } */
--
2.47.3
