gcov与LLVM中的实现

微信扫一扫,分享到朋友圈

gcov与LLVM中的实现

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

gcov

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

在gcov的模型中,一个源文件包含若干函数,一个函数包含若干基本块,一个基本块占据若干行。

Instrument程序,在基本块间转移时记录边的执行次数。根据边的执行次数可以计算基本块的执行次数,进而计算行的执行次数。

使用流程:

  • gcc --coverage a.c b.c
    生成 a.gcno
    b.gcno
    ,instrument(记录边执行次数)并链接 libgcov.a
  • ./a.out
    程序退出时输出 a.gcda
    b.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-arcs
instrument程序。这两个选项在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,其实是良性的:

# 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实现的基本流程:

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会显示多个函数:

------------------
| _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.gcno
    b.gcno
    ,instrument(记录边执行次数)
  • clang --coverage a.o b.o
    链接 libclang_rt.profile-$arch.a
    (实现在compiler-rt)
  • ./a.out
    程序退出时输出 a.gcda
    b.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。多线程并发执行可能会有部分计数丢失。

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

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

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很有可能没有行执行次数:

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++的函数默认都会抛异常:joy_cat:。为了计数器精确,GCC似乎会拆分基本块,添加fake arcs,使得一个外部函数调用和下一条语句可以有不同的计数。

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/.gcda
    A93*
    则是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实现。

微信扫一扫,分享到朋友圈

gcov与LLVM中的实现

iPhone SE Plus爆料:或是刘海尺寸最小的全面屏iPhone

上一篇

为丹佛野马队助威:《南方公园》动画角色佩戴口罩现身赛场

下一篇

你也可能喜欢

gcov与LLVM中的实现

长按储存图像,分享给朋友