On 23/07/2025 15:22, Michael Matz wrote:
Hello,
On Tue, 22 Jul 2025, Andrew Stubbs wrote:
Don’t you need to instrument more (or at least different) edges when
only having visited bits ? With counters you can derive coverage of
related edges by diffing counters (consider a simple diamond).
I have not yet got this deep into the analysis (apparently). In my
head, if I just reduced every counter to a single bit (using saturated
add) then gcov would just present a report with "1" or "#####" all down
the left side.
Are you saying that it might actually report "2" (or more) for some
cases where the result is derived from multiple counters? If so, this
is probably acceptable for a first implementation, but we might want to
do something about it.
No, it will have to say "unknown" for some of the non-instrumented edges.
For instance, in a branch:
-- e1 --> if (cond) -- e2 --> ...
\-- e3 --> ...
We will only instrument a subset of all edges, as c(e1)==c(e2)+c(e3). The
subset we select will be a minimal-cost edge graph cover of the CFG.
Depending on surrounding code we may select (for demostrations sake) to
instrument e1 and e2 (or perhaps we know c(e1) from still other edges).
So we know c(e1) and c(e2), and can compute c(e3)=c(e1)-c(e2) correctly.
With visited flags you loose that because the meeting operation
(logical or) isn't invertible: if you know that e1 was visited, and you
know that e2 was visited, you still don't know anything about e3. It may,
or may not, have been visited. You won't know unless you do instrument
e3. Or select a different subset of edge (here, v(e1) could be computed
from v(e2)|v(e3)).
So, that need to instrument more edges offsets the storage savings. I
have no gut feeling for how bad that is, though. You'd have to try :)
Perhaps it still comes out positive.
Thank you for the careful explanation. It seems like all the "innermost"
blocks would need to be instrumented, and in most cases the rest can be
assumed. Unfortunately, that probably means instrumenting the hottest
blocks, but hopefully/maybe/possibly there's no so many of them. I'll
take a look at the selection algorithm and figure out how it's working,
but I assume I will end up needing a matching gcov to go with the new
instrumentation.
Thanks again
Andrew
Ciao,
Michael.
