llvm dev - May 2020 - gcov vs llvm coverage mapping on line execution counts

(Quick example: gcc a.c --coverage; ./a.out; gcov a. => a.c.gcov)
gcov computes line execution counts with this approach:

https://github.com/gcc-mirror/gcc/blob/master/gcc/gcov.c#L2684-L2690
       /* The user expects the line count to be the number of times
	 a line has been executed.  Simply summing the block count
	 will give an artificially high number.  The Right Thing
	 is to sum the entry counts to the graph of blocks on this
	 line, then find the elementary cycles of the local graph
	 and add the transition counts of those cycles.  */

i.e. count from blocks outside the line + cycle count

cycle count is convoluted:

* enumerate cycles using "Finding all the elementary circuits of a directed
graph." (Donald B. Johnson)
   (gcov.c:circuit); O((V+E)*c) (unfortunately the implementation is slower:
O((V+E)*V*c) where V: vertices; E: edges; c: cycles
* for each cycle, handle_cycle() computes the minimum edge and add that to the
cycle count
   (I don't fully understand its cs_count.)
* (For the curious, its path_contains_zero_or_negative_cycle_arc is strange:
http://gcc.gnu.org/PR91601)


llvm coverage mapping uses a very different approach
(https://github.com/llvm/llvm-project/blob/master/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp#L769)
How do we compute ExecutionCount?

The coverage mapping for a function contains a list of nested regions that bears
a rough resemblance to the AST. Each region has a counter expression: the
expression is either a reference to a counter from the profile, or an arithmetic
expression which recursively references other expressions. During IRGen for a
statement, the compiler looks up the counter for the statements AST node and
emits an increment for it. In effect, after profile collection, all counter
expressions which transitively reference that underlying counter are updated at
once.

vedant

> On May 13, 2020, at 10:30 PM, Fangrui Song via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> (Quick example: gcc a.c --coverage; ./a.out; gcov a. => a.c.gcov)
> gcov computes line execution counts with this approach:
> 
> https://github.com/gcc-mirror/gcc/blob/master/gcc/gcov.c#L2684-L2690
>      /* The user expects the line count to be the number of times
>     a line has been executed.  Simply summing the block count
>     will give an artificially high number.  The Right Thing
>     is to sum the entry counts to the graph of blocks on this
>     line, then find the elementary cycles of the local graph
>     and add the transition counts of those cycles.  */
> 
> i.e. count from blocks outside the line + cycle count
> 
> cycle count is convoluted:
> 
> * enumerate cycles using "Finding all the elementary circuits of a
directed graph." (Donald B. Johnson)
>  (gcov.c:circuit); O((V+E)*c) (unfortunately the implementation is slower:
O((V+E)*V*c) where V: vertices; E: edges; c: cycles
> * for each cycle, handle_cycle() computes the minimum edge and add that to
the cycle count
>  (I don't fully understand its cs_count.)
> * (For the curious, its path_contains_zero_or_negative_cycle_arc is
strange: http://gcc.gnu.org/PR91601)
> 
> 
> llvm coverage mapping uses a very different approach
(https://github.com/llvm/llvm-project/blob/master/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp#L769)
> How do we compute ExecutionCount?
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev