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.
Ciao,
Michael.
