gcov与LLVM中的实现

打算以后不定期写一点LLVM的学习(开发)笔记。写作上不想过多花时间(加语文水平所限…),所以字句不作过多斟酌。

gcov

https://gcc.gnu.org/onlinedocs/gcc/Gcov.html

在gcov的模型中,一个源文件包含若干函数,一个函数包含若干基本块,一个基本块占据若干行。
Instrument程序,在基本块间转移时记录边的执行次数。根据边的执行次数可以计算基本块的执行次数,进而计算行的执行次数。

使用流程:

  • gcc --coverage a.c b.c 生成a.gcnob.gcno,instrument(记录边执行次数)并链接libgcov.a
  • ./a.out 程序退出时输出a.gcdab.gcda
  • gcov -t a. b. 生成coverage报告

有两个主要GCC选项:

  • -ftest-profile: 输出notes file (.gcno),描述GCC版本、函数基本信息(名称、起始行列号、结束行列号(GCC 8添加)、校验码(源文件更新后可以判断.gcno/.gcda是否过期))、基本块 (flags (是否树边、是否异常控制流添加的)、包含的行)
  • -fprofile-arcs: instrument程序,程序执行后更新data files (.gcda),描述程序执行次数和边执行次数

.gcno/.gcda均由一串uint32组成,文件格式参见gcc/gcov-io.h。编码简单,但是空间使用有点浪费。
简单说来,-ftest-profile描述控制流图而-fprofile-arcsinstrument程序。这两个选项在GCC 3.4定形,之前版本用.bb{,g}.da

-fprofile-arcs亦可用作链接选项,链接libgcov.{a,so}。通常-ftest-profile -fprofile-arcs同时指定,可以简写为--coverage。(目前为止我唯一的CPython commit就是把-lgcov换成了--coverage)

gcov有个经典前端lcov,为Linux kernel开发,现已用在了很多地方。Bazel的coverage功能就是用lcov作为所有程序设计语言的中间格式。

gcov常用的命令行选项:

  • -i: GCC 4.9~8生成一个近似lcov的intermediate format。GCC 9之后生成.json.gz。有点讨厌的上游改动~如果只是想单纯看行执行次数,从JSON提取信息比提取intermediate format麻烦多了
  • -r: 只输出编译时(源文件使用相对路径名)的.gcno/.gcda的信息。可跳过系统头文件
  • -s prefix: 若源文件路径名前缀为prefix,去除后变为相对路径,可使-r生效
  • -t: 输出到stdout,而非.gcov文件

GCC 4.7、4.8、8、9有打破backward compatibility的改动。如果编译程序用的GCC版本和gcov版本不一致会得到warning,如果没有breaking changes,其实是良性的:

1
2
3
4
5
# gcov removes the extension name, so you can use any of a. a.c a.gcno a.gcda
% gcc-9 --coverage a.c; gcov-10 -t a.
a.gcno:version 'A93*', prefer 'B01*'
a.gcda:version 'A93*', prefer version 'B01*'
...

行执行次数的计算

源文件和函数的summary info都会输出Lines executed
对于某个基本块占据的一行,标记该基本块所在的函数包含该行。若该基本块执行次数大于0,则给所在的函数的lines_executed计数器+1。

GCC 10的gcov statistics实现的基本流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
add_line_counts(coverage_info *coverage, function_info *fn)
// Accmulate info for one function
for each block
for every location (a pair of (source file index, lines))
for every line
if fn is grouped && line belongs to the range of fn
set line to the line_info of the function
line->exists = 1
increment line->count
else
set line to the line_info of the file
line->exists = 1
increment function's lines & lines_executed if necessary
increment line->count

accumulate_line_info(line_info *line, source_info *src, bool add_coverage)
// Accumulate info for one line
for each outgoing arc
arc->cs_count = arc->count
compute cycle counts
line count = incoming counts + cycle counts
if line->exists && add_coverage
src->coverage.lines++
if line->count
src->coverage.lines_executed++

accumulate_line_counts(source_info *src)
// Accumulate info for one file
for each grouped function
for each line
call accumulate_line_info with add_coverage=false
for each line
call accumulate_line_info with add_coverage=true
for each grouped function
for each fn_line where fn_line->exists
increment src's lines and lines_executed if necessary

generate_results(const char *filename)
for each function
call add_line_counts
for each source file
call accumulate_line_counts
call file_summary

得到lines和lines_executed后,Lines executed的百分比就是简单的lines和lines_executed的商。

行执行次数有个我感觉很迷的地方:incoming counts+cycle counts。
Incoming counts勉强可以理解,不在同一行的前驱进入该基本块的执行次数和
Cycle counts是为了计算在循环中的行执行次数。这个就很迷了:用1975年Donald B. Johnson的算法枚举基本圈,然后消圈???
(Boost把该算法归功于K. A. Hawick and H. A. James。gcov继承了这一名字。但实际上这篇论文并没有对Johnson的算法进行改进)

is_group概念是用于处理在同一位置的多个函数的(如template; https://gcc.gnu.org/PR48463)。gcov -f会显示多个函数:

1
2
3
4
5
6
7
8
9
10
11
------------------
| _ZN3FooIfEC2Ev:
| 6| 2| {
| 7| 2| b = 123;
| 8| 2| }
------------------
| _ZN3FooIiEC2Ev:
| 6| 1| {
| 7| 1| b = 123;
| 8| 1| }
------------------

gcov in LLVM

最早由Nick Lewycky在2011年贡献。

使用流程示意:

  • clang --coverage -c a.c b.c 生成a.gcnob.gcno,instrument(记录边执行次数)
  • clang --coverage a.o b.o 链接libclang_rt.profile-$arch.a (实现在compiler-rt)
  • ./a.out 程序退出时输出a.gcdab.gcda
  • llvm-cov gcov -t a. b. 生成coverage报告

llvm-cov gcov接口模拟gcov。在Clang 11之前(我施工之前),Clang吐出的.gcno/.gcda是一种伪GCC 4.2格式,实际上没有办法用任何gcov版本阅读:(

Instrumentation

Instrument一条边的指令非常简单,给一个计数器加一。多线程程序同时操作一个计数器就会有data race。
GCC追求精确,如果编译时指定-pthread,计数器会用atomic operation,多线程竞争带来的性能损失可能很大(https://gcc.gnu.org/PR97065)。
Clang -fprofile-generate-fprofile-arcs没有用atomic operation。多线程并发执行可能会有部分计数丢失。

1
2
3
4
// g++
addq $1, __gcov0._Z3fooRSt6vectorIiSaIiEE(%rip)
// g++ -pthread
lock addq $1, __gcov0._Z3fooRSt6vectorIiSaIiEE(%rip)

Clang的PGO会检测循环,把计数器+1转换为+N,在性能提升的同时可以大幅改善多线程冲突导致计数丢失的问题(https://reviews.llvm.org/D34085)。

替代atomic operation的一种思路是在function prologue处获取CPU id(可惜没有移植性好的函数),获得一个per-cpu counter array。
函数内的所有计数器都相对于该array,假设不发生process migration。
Linux上若有rseq倒是可以访问__rseq_abi.cpu_id,但使用seq需要runtime在每个新建thread上执行rseq系统调用……
(假如要保护process migration,每个计数器增加都用rseq会消耗过多__rseq_cs)
这种方法还有一个缺点是一个寄存器被固定用作计数器用途。

PGO/coverage选项可以参阅https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html
GCC的profile guided optimization -fprofile-generate隐含-fprofile-arcs,亦即PGO和coverage复用同一套instrument模块和runtime。
这么做也有缺点,因为PGO和coverage取舍上有所不同。比如coverage用户可能会更在意行执行次数的准确性,假如三个计时器有A=B+C的关系而实际上不成立,会给用户造成困惑。
而对于PGO来说,损失10%的边执行次数未尝不可接受。

Clang其实还有另一套coverage机制,在2014年开发:-fprofile-instr-generate -fcoverage-mapping
clangCodeGen实现了-fprofile-instr-generate,既用于Clang的PGO instrumentation,也用于coverage。
假如你用llvm-cov导出coverage信息,可以发现它有非常精确的列号和覆盖区间信息,因为它能直接操作AST,知道每一个语句的起始和结束位置。
--coverage则用了调试信息,大部分时候只有点信息,而没有区间信息,甚至有些时候没有列号信息。

-fprofile-instr-generate instrument一个函数时记录所有边的执行次数。假如你学过电路,可能知道Kirchhoff’s circuit law。
若一个顶点有E条边,那么记录E-1条边的执行次数,即可计算剩下一条边的执行次数。
对于一个V个基本块、E条边的图,只需要测量E-V+1条边即可计算所有边的执行次数。
在控制流图中添加一个单个后继的basic block,不需要instrument新边。在控制流图中添加一个两个后继的basic block,只需要instrument一条新边。
这一优化可以少instrument超过一半的边。我最近给Clang 12添加了这一优化,可能有10%~30%的性能提升,性能和关闭value profiling的-fprofile-generate类似,比-fprofile-instr-generate快。

当然这么做并非没有缺陷:对于异常控制流,如fork/execve,少instrument一些边可以导致计数不准确。

2015年Clang添加了-fprofile-generate(选项名模拟GCC,实际上并不兼容),IR-level PGO。作为一个IR pass,它在优化管线内的位置比较灵活,而且可以方便地用于其他语言前端(ldc、Rust)。
比如,在instrument前添加一个inliner可以大幅减少记录的边数。GCC也有类似优化。对于下面的程序,bar很有可能没有行执行次数:

1
2
3
4
5
6
7
8
int bar() {
return 1;
}

__attribute__((noinline))
int foo() {
return bar() + 2;
}

clang --coverage目前没有在instrument前添加inliner,因此bar的执行次数被准确地保留下来。
你可以把bar替换成一个/usr/include/c++/里的某个C++ STL,先执行inling的好处就更加明显了:
很多时候你不想了解C++ STL里复杂实现的各个部分的行执行次数,然而他们却占据了好多计数器。

还有一个有意思的地方,如果用了--coverage -fsanitize=thread,thread sanitizer会添加在优化管线非常靠后的地方。
计数器应该用atomic operation,否则会触发data race报告。我在Clang 12中修复了这个问题。

C++的函数默认都会抛异常😹。为了计数器精确,GCC会拆分基本块,添加fake arcs,使得一个外部函数调用和下一条语句的计数可能不同。对于下面的程序,bb 0和bb 1分别表示entry block/exit block,bb 2~5之间有边。

1
2
3
4
5
6
extern void f();
void g() { // bb 2
puts("0"); // bb 2
f(); // bb 3
puts("1"); // bb 4
} // bb 5

如果没有异常、dxit、execve、fork等干涉控制流的函数,函数g只需要一个计数器,让所有语句共享。而GCC从bb 2~4各引一条边到bb 1,导致了三个新的计数器。Clang没有实现fake arcs。

我的gcov in LLVM贡献

大部分修改会出现在LLVM 11中。

  • 几乎重写了llvm-cov gcov的所有统计代码,支持读取GCC 3.4~10 .gcno/.gcda
  • llvm-cov gcov实现了-i -r -s -t
  • 让Clang和libclang_rt.profile-支持GCC 4.7~9所有instrument改动。可以用-Xclang -coverage-version='409*'生成GCC 4.9兼容的.gcno/.gcdaA93*则是GCC 9.3,B01*则是GCC 10.1
  • 添加了big-endian实现

gcov in Linux kernel

有意思的是libgcov在Linux kernel中也有实现:https://github.com/torvalds/linux/blob/master/kernel/gcov/gcc_4_7.c
“关机输出.gcda文件”显然不是好的用户体验~.gcno/.gcda实际上是用debugfs提供的。
kernel/gcov/clang.c是Android提供的用于Clang的runtime实现。