LLVM后端与工具链技术探索
底层探索LLVM
在介绍 LLVM 之前，先来认识一下解释型语言和编译型语言。
解释型语言
有的编程语言可以一边执行一边转换，不会生成可执行文件再去执行，这种编程语言称为解释型语言，使用的转换工具称为解释器，比如 Python、JavaScript、PHP等。
编译型语言
有的编程语言要转换成二进制指令，也就是生成一个可执行程序这种编程语言称为编译型语言，使用的转换工具称为编译器，比如C语言、C++、OC等。
总结
解释型语言：读到相应代码就直接执行。
编译型语言：先将代码编译成计算机可以识别的二进制文件，才能执行。
LLVM简介
LLVM是构架编译器(compiler)的框架系统，以C++编写而成，用于优化以任意程序语言编写的程序的编译时间(compile-time)、链接时间(link-time)、运行时间(run-time)以及空闲时间(idle-time)，对开发者保持开放，并兼容已有脚本。
LLVM计划启动于2000年，最初由美国UIUC大学的 ChrisLattner博士主持开展。2006年ChrisLattner加盟AppleInc并致力于LLVM在Apple开发体系中的应用。 Apple也是LLVM计划的主要资助者。目前LLVM已经被苹果IOS开发工具、Xilinx Vivado、Facebook、Google等各大公司采用。
iOS的编译器架构
ObjectiveC/C/C++使用的编译器前端是Clang，Swift是Swift，后端都是LLVM。
当编译器决定支持多种源语言或多种硬件架构时，LLVM最重要的地方就来了。
其他的编译器如GCC是非常成功的一款编译器，但由于它是作为整体应用程序设计的，因此它的用途受到了很大的限制。
LLVM设计的最重要方面是，使用通用的代码表示形式(IR)，它是用来在编译器中表示代码的形式。所以LLVM可以为任何编程语言独立编写前端，并且可以为任意硬件架构独立编写后端。
Clang
对于我们的开发人员来说，看得见摸得着的，接触最多的就是我们的Clang。
Clang是LLVM项目中的一个子项目。它是基于LLVM架构的轻量级编译器，诞生之初是为了替代GCC，提供更快的编译速度。它是负责编译C、C++、Objecte- C语言的编译器，它属于整个LLVM架构中的，编译器前端。对于开发者来说，研究Clang可以给我们带来很多好处。
编译流程
接下来通过一段代码，具体了解一下编译流程：
int main(int argc, const char * argv[]) {
@autoreleasepool {
}
return 0;
}
通过一下命令，可以打印源码的编译阶段：
clang -ccc-print-phases main.m
- 0:输入文件:找到源文件。
- 1:预处理阶段:这个过程处理包括宏的替换，头文件的导入。
- 2:编译阶段:进行词法分析、语法分析、检测语法是否正确，最终生成IR。
- 3:后端:这里LLVM会通过一个一个的Pass(可以理解为一个节点)去优化，每个Pass做一些事情，最终生成汇编代码。
- 4:汇编代码生成目标文件。
- 5:链接:链接需要的动态库和静态库，生成相应的镜像可执行文件。
- 6:根据不同的系统架构，生成对应的可执行文件。
#import <stdio.h>
#define B 50
int main(int argc, const char * argv[]) {
int a = 10;
int c = 20;
printf("%d",a + c + B);
return 0;
}预处理阶段
执行如下命令：
clang -E main.m >> main1.m
执行完毕后，我们可以在 main1.m 的文件中，可以看到头文件的导入和宏的替换。
编译阶段-词法分析
预处理完成后就会进行词法分析，这里会把代码切成一个个Token，比如大小括号，等于号还有字符串等。
#import <stdio.h>
#define B 50
typedef int JP_INT;
int main(int argc, const char * argv[]) {
JP_INT a = 10;
JP_INT c = 20;
printf("%d",a + c + B);
return 0;
}
命令运行之后，进行了词法分析，每一行的代码都分开了，切成一个个Token。
语法分析
词法分析完成之后就是语法分析，它的任务是验证语法是否正确。在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等，然后将所有节点组成抽象语法树(AbstractSyntaxTree，AST)。语法分析其目的就是对源程序进行分析判断，在结构上是否正确。
中间代码IR
完成以上步骤后就开始生成中间代码IR(intermediate representation)了，代码生成器(Code Generation)会将语法树自顶向下遍历逐步翻译成LLVM IR。
ObjectiveC代码在这一步会进行runtime的桥接:property合成，ARC处理等。
IR的基本语法
@: 全局标识
% : 局部标识
alloca: 开辟空间
align: 内存对齐
i32: 32个bit，4个字节
store: 写入内存
load: 读取数据
call: 调用函数
ret: 返回LLVM的优化级别分别是-O0-O1-O2-O3-Os(第一个是大写英文字母O)
编译流程：首先是预处理，对输入代码的宏进行展开；然后是词法分析，会分成一个一个的 token；再是语法分析，会生成 AST语法树；再就会生成IR代码，交给优化器去处理优化代码。
生成目标文件(汇编器)
目标文件的生成，是汇编器以汇编代码作为输入，将汇编代码转换为机器代码，最后输出目标文件(object-file)，这个阶段就是属于编译器后端的工作了。
生成可执行文件(链接)
连接器把编译产生的.o文件和(dylib .a)文件，生成一个mach-o文件(可执行文件)。
dyld_stub_binder是在 dyld里面，当我们的执行文件 mach-o 进入的内存之后，外部的符号就会立刻马上和dyld_stub_binder进行绑定，这个过程是 dyld 强制绑定的。
链接和绑定是两个概念：链接是我要知道你外部的符号在哪个动态库里面，就是做个标记，我要知道去哪个动态库里面找到你。
绑定是在执行的时候，把动态库libSystem里面的和你这个外部调用的_printf进行绑定，绑定是在执行期，链接是在编译期。
bpf工具链 - LLVM篇
LLVM 是目前唯一提供 BPF 后端的编译器套件。gcc 目前不支持 BPF。
BPF 后端被合并到 LLVM 的 3.7 版本中。主要发行版在打包 LLVM 时默认启用 BPF 后端，因此在最近的发行版上安装 clang 和 llvm 足以开始将 C 编译为 BPF 目标文件。
典型的工作流程是 BPF 程序用 C 语言编写，通过 LLVM 编译成object/ELF 文件，由用户空间 BPF ELF 加载器（如 iproute2 或其他）解析，并通过 BPF 系统调用推送到内核中。内核验证 BPF 指令并对它们进行 JIT，为程序返回一个新的文件描述符，然后可以将其附加到子系统（例如网络），子系统可以进一步将 BPF 程序卸载到硬件（例如 NIC）。可参考前面bpf架构篇来了解各个模块。
对于 LLVM，可以检查 BPF 目标支持与否，例如，通过以下方式：
$ llc --versionLLVM (http://llvm.org/):LLVM version 3.8.1Optimized build.Default target: x86_64-unknown-linux-gnuHost CPU: skylakeRegistered Targets: [...] bpf - BPF (host endian) bpfeb - BPF (big endian) bpfel - BPF (little endian) [...]
默认情况下，bpf目标使用 CPU 的字节序进行编译，这意味着如果 CPU 的字节序是小端字节序，则程序也以小端字节序格式表示，如果 CPU 的字节序为大端字节序，则程序表示为大端。这也与 BPF 的运行时行为相匹配，它是通用的并使用它运行的 CPU 字节序，以便不损害任何格式的架构。
对于交叉编译，引入了两个目标bpfeb和bpfel，这要归功于 BPF 程序可以在以一种字节序运行的节点上编译（例如 x86 上的小字节序）并在以另一种字节序格式（例如 arm 上的大字节序）的节点上运行. 请注意，前端（clang）也需要以目标字节序运行。
在没有混合字节序的情况下使用bpf目标作为是首选方式。例如，对x86_64目标进行编译会产生相同的输出，bpf并且bpfel由于是小端，因此触发编译的脚本也不必是端感知的。
一个最小的、独立的 XDP 放置程序可能类似于以下示例 ( xdp-example.c)：
#include <linux/bpf.h>#ifndef __section# define __section(NAME) \ __attribute__((section(NAME), used))#endif__section("prog")int xdp_drop(struct xdp_md *ctx){ return XDP_DROP;}char __license[] __section("license") = "GPL";
然后可以按如下方式编译并加载到内核中：
$ clang -O2 -Wall -target bpf -c xdp-example.c -o xdp-example.o
# ip link set dev em1 xdp obj xdp-example.o
注意：将 XDP BPF 程序附加到上述网络设备需要 Linux 4.11 和支持 XDP 的设备，或者 Linux 4.12 或更高版本。
对于生成的目标文件 LLVM (>= 3.9) 使用官方的 BPF 机器值，即EM_BPF（十进制：247/十六进制：）0xf7。在此示例中，程序已使用 下的bpf目标进行编译x86_64，因此LSB（相对于MSB）显示关于字节序：
$ file xdp-example.o
xdp-example.o: ELF 64-bit LSB relocatable, *unknown arch 0xf7* version 1 (SYSV), not stripped
readelf -a xdp-example.o将转储有关 ELF 文件的更多信息，这些信息有时可用于内省生成的节标题、重定位条目和符号表。
在不太可能需要从头开始编译 clang 和 LLVM 的情况下，可以使用以下命令：
$ git clone https://github.com/llvm/llvm-project.git
$ cd llvm-project
$ mkdir build
$ cd build
$ cmake -DLLVM_ENABLE_PROJECTS=clang -DLLVM_TARGETS_TO_BUILD="BPF;X86" -DBUILD_SHARED_LIBS=OFF -DCMAKE_BUILD_TYPE=Release -DLLVM_BUILD_RUNTIME=OFF -G "Unix Makefiles" ../llvm
$ make -j $(getconf _NPROCESSORS_ONLN)
$ ./bin/llc --version
LLVM (http://llvm.org/):
LLVM version x.y.zsvn
Optimized build.
Default target: x86_64-unknown-linux-gnu
Host CPU: skylake
Registered Targets:
bpf - BPF (host endian)
bpfeb - BPF (big endian)
bpfel - BPF (little endian)
x86 - 32-bit X86: Pentium-Pro and above
x86-64 - 64-bit X86: EM64T and AMD64
$ export PATH=$PWD/bin:$PATH # add to ~/.bashrc
确保--version使用了Optimized build否则当 LLVM 处于调试模式时，程序的编译时间将显着增加（例如，增加 10 倍或更多）。
对于调试，clang 可以生成汇编器输出如下：
$ clang -O2 -S -Wall -target bpf -c xdp-example.c -o xdp-example.S
$ cat xdp-example.S
.text
.section prog,"ax",@progbits
.globl xdp_drop
.p2align 3
xdp_drop: # @xdp_drop
# BB#0:
r0 = 1
exit
.section license,"aw",@progbits
.globl __license # @__license
__license:
.asciz "GPL"
从 LLVM 的 6.0 版开始，会有汇编器解析器的支持。您可以直接使用 BPF 汇编器进行编程，然后使用 llvm-mc 将其组装成目标文件。例如，您可以使用以下命令将上面列出的 xdp-example.S 组装回目标文件：
llvm-mc -triple bpf -filetype=obj -o xdp-example.o xdp-example.S
此外，更新的 LLVM 版本 (>= 4.0) 还可以将调试信息以 dwarf 格式存储到目标文件中。这可以通过通常的工作流程通过添加-g编译来完成。
$ clang -O2 -g -Wall -target bpf -c xdp-example.c -o xdp-example.o
$ llvm-objdump -S --no-show-raw-insn xdp-example.o
xdp-example.o: file format ELF64-BPF
Disassembly of section prog:
xdp_drop:
; {
0: r0 = 1
; return XDP_DROP;
1: exit
然后，该llvm-objdump工具可以使用编译中使用的原始 C 代码对汇编器输出进行注释。本例中的简单示例不包含太多 C 代码，但是，显示为0: 和的行号1:直接对应于内核的验证程序日志。
这意味着，如果 BPF 程序被验证者拒绝，llvm-objdump 可以帮助将指令关联回原始 C 代码，这对于分析非常有用。
# ip link set dev em1 xdp obj xdp-example.o verb
Prog section 'prog' loaded (5)!
- Type: 6
- Instructions: 2 (0 over limit)
- License: GPL
Verifier analysis:
0: (b7) r0 = 1
1: (95) exit
processed 2 insns
从验证器分析中可以看出，llvm-objdump输出转储了与内核相同的 BPF 汇编代码。
省略该--no-show-raw-insn选项也会将原始数据 作为十六进制转储到程序集前面：struct bpf_insn
$ llvm-objdump -S xdp-example.o
xdp-example.o: file format ELF64-BPF
Disassembly of section prog:
xdp_drop:
; {
0: b7 00 00 00 01 00 00 00 r0 = 1
; return foo();
1: 95 00 00 00 00 00 00 00 exit
对于 LLVM IR 调试，BPF 的编译过程可以分为两个步骤，生成二进制 LLVM IR 中间文件xdp-example.bc，然后可以将其传递给 llc：
$ clang -O2 -Wall -target bpf -emit-llvm -c xdp-example.c -o xdp-example.bc
$ llc xdp-example.bc -march=bpf -filetype=obj -o xdp-example.o
生成的 LLVM IR 也可以通过以下方式以用户可读的格式转储：
clang -O2 -Wall -emit-llvm -S -c xdp-example.c -o -
LLVM 能够将调试信息（例如程序中使用的数据类型的描述）附加到生成的 BPF 目标文件中。默认情况下，这是 DWARF 格式。
BPF 使用的一个高度简化的版本称为 BTF（BPF 类型格式）。生成的 DWARF 可以转换为 BTF，然后通过 BPF 对象加载器加载到内核中。然后内核将验证 BTF 数据的正确性并跟踪 BTF 数据包含的数据类型。
然后可以使用 BTF 数据中的键和值类型对 BPF 映射进行注释，以便稍后的映射转储导出映射数据以及相关的类型信息。这允许更好的调试和打印。请注意，BTF 数据是一种通用调试数据格式，因此可以加载任何 DWARF 到 BTF 转换的数据（例如，内核的 vmlinux DWARF 数据可以转换为 BTF 并加载）。后者对于将来的 BPF 跟踪特别有用。
为了从 DWARF 调试信息生成 BTF，需要 elfutils (>= 0.173)。如果这不可用，则需要在编译期间将-mattr=dwarfris选项添加到llc命令中：
$ llc -march=bpf -mattr=help |& grep dwarfris
dwarfris - Disable MCAsmInfo DwarfUsesRelocationsAcrossSections.
[...]
使用-mattr=dwarfris的原因是因为标志dwarfris(dwarf relocation in section）禁用 DWARF 和 ELF 符号表之间的 DWARF 横截面重定位，因为 libdw 没有适当的 BPF 重定位支持，因此像这样的工具 pahole 将无法从对象中正确转储结构。
lfutils (>= 0.173) 实现了适当的 BPF 重定位支持，因此没有该-mattr=dwarfris选项也可以实现相同的功能。从目标文件中转储结构可以通过 DWARF 或 BTF 信息来完成。pahole此时使用 LLVM 发出的 DWARF 信息，但是，pahole如果可用，未来的版本可能会依赖 BTF。
要将 DWARF 转换为 BTF，需要最新的 pahole 版本 (>= 1.12)。如果无法从其中一个分发包中获得最新的 pahole 版本，也可以从其官方 git 存储库获得：
git clone https://git.kernel.org/pub/scm/devel/pahole/pahole.git
pahole附带-J将 DWARF 从目标文件转换为 BTF 的选项。pahole可以按如下方式探测 BTF 支持（请注意，该llvm-objcopy工具也是必需的pahole，因此也要检查它的存在）：
$ pahole --help | grep BTF
-J, --btf_encode Encode as BTF
生成调试信息还需要前端通过传递-g到clang命令行来生成源级调试信息。请注意，这-g与是否使用llc' dwarfris选项无关。生成目标文件的完整示例：
$ clang -O2 -g -Wall -target bpf -emit-llvm -c xdp-example.c -o xdp-example.bc
$ llc xdp-example.bc -march=bpf -mattr=dwarfris -filetype=obj -o xdp-example.o
或者，通过仅使用 clang 构建带有调试信息的 BPF 程序（同样，当具有正确的 elfutils 版本时，可以省略 dwarfris 标志）：
clang -target bpf -O2 -g -c -Xclang -target-feature -Xclang +dwarfris -c xdp-example.c -o xdp-example.o
编译成功后pahole，可以根据 DWARF 信息正确转储 BPF 程序的结构：
$ pahole xdp-example.o
struct xdp_md {
__u32 data; /* 0 4 */
__u32 data_end; /* 4 4 */
__u32 data_meta; /* 8 4 */
/* size: 12, cachelines: 1, members: 3 */
/* last cacheline: 12 bytes */
};
通过该选项-J pahole最终可以从 DWARF 生成 BTF。在对象文件中，DWARF 数据仍将与新添加的 BTF 数据一起保留。完整clang和pahole示例结合：
$ clang -target bpf -O2 -Wall -g -c -Xclang -target-feature -Xclang +dwarfris -c xdp-example.c -o xdp-example.o
$ pahole -J xdp-example.o
通过工具readelf可以看到.BTF的一部分的存在：
$ readelf -a xdp-example.o
[...]
[18] .BTF PROGBITS 0000000000000000 00000671
[...]
iproute2 等 BPF 加载器将检测并加载 BTF 部分，以便 BPF 映射可以使用类型信息进行注释。
LLVM 默认使用 BPF 基本指令集来生成代码，以确保生成的目标文件也可以加载旧内核，例如长期稳定的内核（例如 4.9+）。
但是，LLVM 有一个-mcpu用于 BPF 后端的选择器，以便选择不同版本的 BPF 指令集，即在 BPF 基本指令集之上的指令集扩展，以便生成更高效和更小的代码。
可用-mcpu选项可通过以下方式查询：
$ llc -march bpf -mcpu=help
Available CPUs for this target:
generic - Select the generic processor.
probe - Select the probe processor.
v1 - Select the v1 processor.
v2 - Select the v2 processor.
[...]
generic处理器是默认处理器，也是 BPF 的基本指令集v1。选项v1和v2通常在 BPF 程序被交叉编译并且加载程序的目标主机与编译它的目标主机不同的环境中很有用（因此可用的 BPF 内核特性也可能不同）。
Cilium 内部也使用的推荐-mcpu选项是 -mcpu=probe！在这里，LLVM BPF 后端向内核查询 BPF 指令集扩展的可用性，当发现可用时，LLVM 将在适当的时候使用它们来编译 BPF 程序。
带有 llc 的-mcpu=probe完整命令行示例：
$ clang -O2 -Wall -target bpf -emit-llvm -c xdp-example.c -o xdp-example.bc
$ llc xdp-example.bc -march=bpf -mcpu=probe -filetype=obj -o xdp-example.o
通常，LLVM IR 生成与架构无关。然而，使用clang -target bpf与省略-target bpf时存在一些差异，因此使用 clang 的默认目标，取决于底层架构，可能是 x86_64arm64或其他。
引用内核的Documentation/bpf/bpf_devel_QA.txt：
BPF 程序可以递归地包含带有文件范围内联汇编代码的头文件。默认目标可以很好地处理这个问题，而如果 bpf 后端汇编器不理解这些汇编代码，则 bpf 目标可能会失败，这在大多数情况下是正确的。
在没有 -g 的情况下编译时，附加的 elf 部分，例如.eh_frame 和.rela.eh_frame，可能会出现在具有默认目标的目标文件中，但不会出现在 bpf 目标中。
默认目标可能会将 C switch 语句转换为 switch 表查找和跳转操作。由于切换表放在全局只读部分，bpf程序将无法加载。bpf 目标不支持切换表优化。clang 选项-fno-jump-tables可用于禁用切换表生成。
对于 clang -target bpf，无论底层 clang 二进制文件还是默认目标（或内核）是 32 位，都可以保证指针或 long / unsigned long 类型的宽度始终为 64 位。但是，当使用原生 clang 目标时，它将根据底层架构的约定编译这些类型，这意味着在 32 位架构的情况下，指针或长 / 无符号长类型（例如 BPF 上下文结构中）将具有 32 位的宽度，而BPF LLVM 后端仍然以 64 位运行。
在跟踪映射 CPU 寄存器的内核struct pt_regs或其他 CPU 寄存器宽度很重要的内核结构的情况下，最需要本机目标。在所有其他情况下（例如联网），使用clang -target bpf是首选。
此外，自 LLVM 7.0 版以来，LLVM 开始支持 32 位子寄存器和 BPF ALU32 指令。添加了一个新的代码生成属性alu32。启用后，LLVM 将尽可能尝试使用 32 位子寄存器，通常是在对 32 位类型进行操作时。与 32 位子寄存器相关的 ALU 指令将成为 ALU32 指令。例如，对于以下示例代码：
$ cat 32-bit-example.c
void cal(unsigned int *a, unsigned int *b, unsigned int *c)
{
unsigned int sum = *a + *b;
*c = sum;
}
在默认代码生成时，汇编器将如下所示：
$ clang -target bpf -emit-llvm -S 32-bit-example.c
$ llc -march=bpf 32-bit-example.ll
$ cat 32-bit-example.s
cal:
r1 = *(u32 *)(r1 + 0)
r2 = *(u32 *)(r2 + 0)
r2 += r1
*(u32 *)(r3 + 0) = r2
exit
使用 64 位寄存器，因此加法意味着 64 位加法。现在，如果您通过指定启用新的 32 位子寄存器支持-mattr=+alu32，那么汇编器将如下所示：
$ llc -march=bpf -mattr=+alu32 32-bit-example.ll
$ cat 32-bit-example.s
cal:
w1 = *(u32 *)(r1 + 0)
w2 = *(u32 *)(r2 + 0)
w2 += w1
*(u32 *)(r3 + 0) = w2
exit
w寄存器，意思是 32 位子寄存器，将被用来代替 64 位r 寄存器。
启用 32 位子寄存器可能有助于减少类型扩展指令序列。它还可以帮助内核 eBPF JIT 编译器用于 32 位架构，其中寄存器对用于对 64 位 eBPF 寄存器进行建模，并且需要额外的指令来操作高 32 位。给定从 32 位子寄存器读取保证仅从低 32 位读取，即使写入仍需要清除高 32 位，如果 JIT 编译器知道一个寄存器的定义只有子寄存器读取，则设置指令可以消除目标的高 32 位。
参考文献链接
https://mp.weixin.qq.com/s/Gt_D5GPlQdOjUVnAMSRn9Q
https://mp.weixin.qq.com/s/AFwzC5wDXAsRa1V_Y03Y_A