gcov与LLVM中的实现
2020-09-27 16:00:00 Author: maskray.me(查看原文) 阅读量:281 收藏

打算以后不定期写一点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-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.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。多线程并发执行可能会有部分计数丢失。

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() {   
  puts("0"); 
  f();       
  puts("1"); 
}

如果没有异常、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/.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实现。


文章来源: http://maskray.me/blog/2020-09-27-gcov-and-llvm
如有侵权请联系:admin#unsafe.sh