GCov space optimization

[Alexander Monakov]

On Wed, 23 Jul 2025, Jan Hubicka via Gcc wrote:

> > > 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.
> > 
> > I think you can work on the instrumentation part by keeping the counter format and just changing the update to set bit zero.
> 
> we build minimum spaning tree of the CFG and then instrument all
> non-spanning edges.  Since typical out-degree of a basic block is 2 you
> get approximately as many counters as basic blocks.  The counts on the
> spaning tree are then determined by Kirhoff law.
> https://dl.acm.org/doi/pdf/10.1145/183432.183527
> 
> If you want to track bits, you may simply instrument all edges and the
> data size would be still approx 32times smaller at the expense of more
> work in code segment.  You can optimize this. If BB has only one
> sucessor S you know that if BB is executed, S is also executed. Not sure
> if you can do much better.

Isn't it the case that if a given BB is executed, then *all* its dominators
were executed, and some of its post-dominators too, except when a call could
terminate the program? So instrumenting the entry BB is necessary only if it's
the only block in a function, or contains a possible-terminating call. And
this can be generalized to BBs of the dominator tree?

Alexander