On 23/07/2025 17:29, Alexander Monakov wrote:
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?
If I understand it correctly, the compiler instruments edges (arcs,
branches), not blocks. There are more edges than blocks, but if you
want to test all code paths then you need to know how you got to the
block. The algorithm tries to minimize the number of counters while
still preserving knowledge of the paths.
Actually, I'm unsure what to do about this since gcov primarily just
reports how many times a line has been visited. Probably many users
don't care about the edges, and I could have it simply record visited
blocks, but a really thorough code coverage report would also include
edges not taken (gcov -g). I need to ask my user what they expect. My
intuition is to keep it as is, unless it's expensive (not obviously so)
and more extreme savings are required.
Andrew
