汇编层次的数据表示

LLVM IR是最接近汇编语言的一层抽象，所以我们首先需要了解在计算机底层，汇编语言的层次中，数据是怎样表示的

谈到汇编层次的数据表示，一个老生常谈的程序就是

#include <stdlib.h>

int global_data = 0;

int main() {
    int stack_data = 0;
    int *heap_pointer = (int *)malloc(16 * sizeof(int));
    return 0;
}

我们知道，一个C语言从代码到执行的过程是代码–>硬盘上的二进制程序–>内存中的进程。在代码被编译到二进制程序的时候，global_data本身就写在了二进制程序中。在操作系统将二进制程序载入内存时，就会在特定的区域（数据区）初始化这些值。而stack_data代表的局部变量，则是在程序执行其所在的函数时，在栈上初始化，类似地，heap_pointer这个指针也是在栈上，而其指向的内容，则是操作系统分配在堆上的。

用一个图可以简单地表示：

+------------------------------+
|          stack_data          |
|         heap_pointer         |  <------------- stack(堆栈)
+------------------------------+
|                              |
|                              |  <------------- available memory space(可用内存空间)
|                              |
+------------------------------+
| data pointed by heap_pointer |  <------------- heap(堆内存)
+------------------------------|
|          global_data         |  <------------- .data section(数据栈)
+------------------------------+

这就是一个简化后的进程的内存模型。也就是说，一共有三种数据：

• 栈上的数据
• 堆中的数据
• 数据区里的数据

但是，我们仔细考虑一下，在堆中的数据，能否独立存在。操作系统提供的在堆上创建数据的接口如malloc等，都是返回一个指针，那么这个指针会存在哪里呢？寄存器里，栈上，数据区里，或者是另一个被分配在堆上的指针。也就是说，可能会是：

#include <stdlib.h>

int *global_pointer = (int *)malloc(16 * sizeof(int));

int main() {
    int *stack_pointer = (int *)malloc(16 * sizeof(int));
    int **heap_pointer = (int **)malloc(sizeof(int *));
    *heap_pointer = (int *)malloc(16 * sizeof(int));
    return 0;
}

但不管怎样，堆中的数据都不可能独立存在，一定会有一个位于其他位置的引用。所以，在内存中的数据按其表示来说，一共分为两类：

• 栈上的数据
• 数据区里的数据

除了内存之外，还有一个存储数据的地方，那就是寄存器。因此，我们在程序中可以用来表示的数据，一共分为三类：

• 寄存器中的数据
• 栈上的数据
• 数据区里的数据

数据区与符号表

我们知道，数据区里的数据，其最大的特点就是，能够给整个程序的任何一个地方使用。同时，数据区里的数据也是占静态的二进制可执行程序的体积的。所以，我们应该只将需要全程序使用的变量放在数据区中。而现代编程语言的经验告诉我们，这类全局静态变量应该越少越好。

同时，由于LLVM是面向多平台的，所以我们还需要考虑的是该怎么处理这些数据。一般来说，大多数平台的可执行程序格式中都会包含.data分区，用来存储这类的数据。但除此之外，每个平台还有专门的更加细致的分区，比如说，Linux的ELF格式中就有.rodata来存储只读的数据。因此，LLVM的策略是，让我们尽可能细致地定义一个全局变量，比如说注明其是否只读等，然后依据各个平台，如果平台的可执行程序格式支持相应的特性，就可以进行优化。

一般来说，在LLVM IR中定义一个存储在数据区中的全局变量，其格式为：

@global_variable = global i32 0

这个语句定义了一个i32类型的全局变量@global_variable，并且将其初始化为0。
如果是只读的全局变量，也就是常量，我们可以用constant来代替global：

@global_constant = constant i32 0

这个语句定义了一个i32类型的全局常量@global_constant，并将其初始化为0。

符号与符号表

讲到了数据区，就顺便讲讲符号表。在LLVM IR中，所有的全局变量的名称都需要用@开头。我们有一个这样的LLVM IR：

; global_variable_test.ll
@global_variable = global i32 0

define i32 @main() {
    ret i32 0
}

也就是说，在之前最基本的程序的基础上，新增了一个全局变量@global_variable。我们将其直接编译成可执行文件：

clang global_variable_test.ll -o global_variable_test

然后，我们使用nm命令查看其符号表：

nm global_variable_test

我们可以在输出中找到一行：

000000000000402c B global_variable

我们注意到，出现了global_variable这个字段。这表明，直接定义的全局变量，其名称会出现在符号表之中。那么，怎么控制这个行为呢？首先，我们需要简单地了解一下符号与符号表。

在传统的C语言编译模型中，编译器将每个.c文件（也称为「编译单元」）编译为一个.o目标文件，然后链接器将这些.o文件链接为一个可执行文件。这么做的好处是，如果一个项目特别大，编译器就不需要将所有.c文件都读入内存中一起处理，而是可以并行地、高效地单独处理每个.c文件（这也是著名前端框架React不选择使用TypeScript的原因之一，参见为什么 React 源码不用 TypeScript 来写？ - Cat Chen的回答 - 知乎）。对于动态链接的程序而言，在程序加载、运行时，也会由动态链接器将相应的库动态链接进程序之中。

也就是说，编译器生成的结果，需要给链接器和动态链接器进行处理。在这一过程中，就需要「符号表」出马了。在上述的过程中，编译器的输入是一个编译单元，而输出是一个目标文件。那么如果我们在源代码中，在一个.c文件中调用了别的文件中实现的函数，编译器并不知道别的函数在哪。因此，编译器选择的策略是将这个函数的调用用一个符号代替，在将来链接以及动态链接的时候，再进行替换。

粗略来讲，整体的符号处理的过程为：

1. 编译器对源代码按文件进行编译。对于每个文件中的未知函数，记录其符号；对于这个文件中实现的函数，暴露其符号
2. 链接器收集所有的目标文件，对于每个文件而言，将其记录下的未知函数的符号，与其他文件中暴露出的符号相对比，如果找到匹配的，就成功地解析（resolve）了符号
3. 部分符号在程序加载、执行时，由动态链接库给出。动态链接器将在这些阶段，进行类似的符号解析
   这一流程粗粒度地来看，非常的简单。但是仔细来看，就需要更多的处理。

一个符号本身，就是一个字符串。那么我们在写一个C语言的项目时，如果希望有的函数在别的文件中被调用，按照上述过程，似乎就是暴露一下符号就行。但是，一个C语言的项目，往往会链接很多第三方库。如果我们想暴露的函数名与其他第三方库里的函数名重复了，会怎样呢？如果不加处理，链接器会直接报错。那难道我们起一个名字，需要注意与别的所有的库里的函数都不重复吗？此外，一个程序会有成千上万个符号，一些简单的，只在一个文件里用到的符号，比如说cmp、max，难道也要放在符号表中吗？

在LLVM IR中，解决这些问题，与两个概念密切相关：链接与可见性，LLVM IR也提供了Linkage Type和Visibility Styles这两个修饰符来控制相应的行为。

链接类型

对于链接类型，我们常用的主要有什么都不加（默认为external）、private和internal。

什么都不加的话，就像我们刚刚那样，直接把全局变量的名字放在了符号表中。这样的话，这个函数可以在链接时被其他编译单元看到。
用private，则代表这个变量的名字不会出现在符号表中。我们将原来的代码改写成

@global_variable = private global i32 0

那么，用nm查看其编译出的可执行文件，这个变量的名字就消失了。

用internal则表示这个变量是以局部符号的身份出现（全局变量的局部符号，可以理解成C中的static关键词）。我们将原来的代码改写成

@global_variable = internal global i32 0

那么，再次将其编译成可执行程序，并用nm查看，可以看到这个符号。但是，在链接过程中，这个符号并不会参与符号解析。

global 全局
private
internal 局部符号

可见性

可见性在实际使用中则比较少，主要分为三种default, hidden和protected，这里主要的区别在于符号能否被重载。default的符号可以被重载，而protected的符号则不可以；此外，hidden则不将变量放在动态符号表中，因此其它的模块不可以直接引用这个符号。

可抢占性

在我们日常看到的LLVM IR中，会经常见到dso_local这样的修饰符，在LLVM中被称作运行时抢占性修饰符。如果需要深入理解这个概念，可以参考国人大神写的ELF interposition and -Bsymbolic、-fno-semantic-interposition。简单来说，dso_local保证了程序像我们想象中的一样运行。

// interposition1.c
void f(void) {
    printf("From interposition1\n");
}

// interposition2.c
void f(void) {
    printf("From interposition2\n");
}

void g(void) {
    f();
}

// interposition-main.c
void g();

int main() {
    g();
    return 0;
}

我们想把interposition1.c和interposition2.c分别编译为动态链接库，并给main来调用。最简单的做法是：

clang -fPIC interposition1.c --shared -o libinterposition1.so
clang -fPIC interposition2.c --shared -o libinterposition2.so
clang -L. -linterposition1 -linterposition2 interposition-main.c -o interposition

• -fPIC

  生成位置无关代码（Position-Independent Code）。动态库必须加这个参数，代码段可以加载到虚拟地址任意位置，没有硬编码地址。Linux 编译 .so 必备。

• --shared

  生成动态共享库（.so），而不是可执行程序。

• -o libinterposition1.so

  指定输出文件名，Linux 动态库规范命名：libxxx.so。

• -L.

  指定动态库搜索路径：. 当前目录，让链接器能找到 libinterposition1.so / libinterposition2.so。

• -linterposition1

  -lname 规则：自动补全 libname.so，也就是链接 libinterposition1.so

• -linterposition2

  链接 libinterposition2.so

• interposition-main.c：主程序源码

• -o interposition：输出可执行文件名为 interposition

这两个动态库和这个.c文件进行链接

我们运行这个程序，常理告诉我们，正常来说，得是输出“From interposition2“吧？但是，我们真正运行这个程序，会输出“From interposition1“。

我们如果看interposition2的汇编代码，会发现，g函数的实现为

g:
    pushq    %rbp
    movq     %rsp, %rbp
    callq    f@PLT
    popq     %rbp
    retq

这不仅极其愚蠢（可能仅仅对通过LD_PRELOAD来hook API有帮助），而且效率还低。

但如果我们这样子来编译：
虽然f在同一个文件内，但它居然默认是去PLT表找实现！！

clang -fPIC interposition1.c --shared -o libinterposition1.so
clang -fPIC -fno-semantic-interposition interposition2.c --shared -o libinterposition2.so
clang -L. -linterposition1 -linterposition2 interposition-main.c -o interposition

仅仅在编译libinterposition2.so时增加了-fno-semantic-interposition这个选项，再运行程序，输出就对了！

如果我们查看生成的interposition2.ll，可以发现：

define dso_local void @f() {
  %1 = call i32 (ptr, ...) @printf(ptr noundef @.str)
  ret void
}

define dso_local void @g() {
  call void @f()
  ret void
}

f和g都有了dso_local的修饰符。dso_local就是告诉链接器，这个不许抢占，在生成动态链接库的时候，直接调用，别去PLT表找了。

当我们使用clang -O3等级别进行优化编译时，不需要加-fno-semantic-interposition就可以达成一样的效果。

根据Fedora社区的尝试Changes/PythonNoSemanticInterpositionSpeedup和cpython对应的issue Compile libpython with -fno-semantic-interposition，仅仅是增加这个选项，就可以让cpython快1.3倍。

C的例子

关于符号和符号表，这些还是挺抽象的，我们不如用一个具体的C语言的例子来看看效果：

int a;
extern int b;
static int c;
void d(void);
void e(void) {}
static void f(void) {}

首先我们先理解一下这个C语言代码各个符号的含义：

• a

  定义在当前文件中的全局变量，别的文件也可以使用这个符号

• b

  定义在别的文件中的全局变量，当前文件需要使用这个符号

• c

  定义在当前文件中的全局变量，别的文件不可以使用这个符号

• d

  定义在别的文件中的函数，当前文件需要使用这个符号

• e

  定义在当前文件中的函数，别的文件也可以使用这个符号

• f

  定义在当前文件中的函数，别的文件不可以使用这个符号

以上六种，是我们在C语言编程中最常见的符号形式。

我们使用Clang将其编译为LLVM IR，是什么样子的呢？

@a = dso_local global i32 0, align 4
@b = external global i32, align 4
@c = internal global i32 0, align 4

declare void @d()

define dso_local void @e() {
  ret void
}

define internal void @f() {
  ret void
}

我们可以发现几件事（在默认的编译选项下）：

• C语言中的static，也就是当前文件中定义，别的文件不可以用的，都会加上internal修饰符
• C语言中的extern，也就是别的文件中定义的，全局变量会加上external修饰符，函数会使用declare
• C语言中定义的，可以给别的文件使用的全局变量或函数，不会加上链接类型修饰符，并且会加上dso_local保证不会被抢占

寄存器和栈

这两种数据我选择放在一起讲。我们知道，大多数对数据的操作，如加减乘除、比大小等，都需要操作的是寄存器内的数据。那么，我们为什么需要把数据放在栈上呢？主要有两个原因：

• 寄存器数量不够
• 需要操作内存地址

如果我们一个函数内有三四十个局部变量，但是家用型CPU最多也就十几个通用寄存器，所以我们不可能把所有变量都放在寄存器中。因此我们需要把一部分数据放在内存中，栈就是一个很好的存储数据的地方；此外，有时候我们需要直接操作内存地址，但是寄存器并没有通用的地址表示，所以只能把数据放在栈上来完成对地址的操作。

因此，在不操作内存地址的前提下，栈只是寄存器的一个替代品。有一个很简单的例子可以解释这个概念。我们有一个很简单的C程序：

// max.c
int max(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

int main() {
    int a = max(1, 2);
    return 0;
}

我们将其编译成汇编文件。我们首先来看max(1, 2)是如何调用的：

movl    $1, %edi
movl    $2, %esi
callq   max

将参数1和2分别放到了寄存器edi和esi里。那么，max函数又是如何操作的呢？

    pushq   %rbp
    movq    %rsp, %rbp
    movl    %edi, -8(%rbp)        # Move data stored in %edi to stack at -8(%rbp)
    movl    %esi, -12(%rbp)       # Move data stored in %esi to stack at -12(%rbp)
    movl    -8(%rbp), %eax        # Move data stored in stack at -8(%rbp) to register %eax
    cmpl    -12(%rbp), %eax       # Compare data stored in stack at -12(%rbp) with data stored in %eax
    jle     .LBB0_2               # If compare result is less than or equal to, then go to label LBB0_2
    movl    -8(%rbp), %eax        # Move data stored in stack at -8(%rbp) to register %eax
    movl    %eax, -4(%rbp)        # Move data stored in %eax to stack at -4(%rbp)
    jmp     .LBB0_3               # Go to label LBB0_3
.LBB0_2:
    movl    -12(%rbp), %eax       # Move data stored in stack at -12(%rbp) to register %eax
    movl    %eax, -4(%rbp)        # Move data stored in %eax to stack at -4(%rbp)
.LBB0_3:
    movl    -4(%rbp), %eax        # Move data stored in stack at -4(%rbp) to register %eax
    popq    %rbp
    retq

考虑到篇幅，我将这个汇编每一个重要步骤所做的事都以注释形式写在了代码里面。这个看上去很复杂，但实际上做的是这样的事：

1. 把int a和int b看作局部变量，分别存储在栈上的-8(%rbp)和-12(%rbp)上
2. 为了比较这两个局部变量，将一个由栈上导入寄存器eax中
3. 比较eax寄存器中的值和另一个局部变量
4. 将两者中比较大的那个局部变量存储在栈上的-4(%rbp)上（由于x86_64架构不允许直接将内存中的一个值拷贝到另一个内存区域中，所以得先把内存区域中的值拷贝到eax寄存器里，再从eax寄存器里拷贝到目标内存中）
5. 将栈上-4(%rbp)这个用来存储返回值的区域的值拷贝到eax中，并返回

这看上去真是太费事了。但是，这也是无可奈何之举。这是因为，在不开优化的情况下，一个C的函数中的局部变量（包括传入参数）和返回值都应该存储在函数本身的栈帧中，所以，我们得把这简单的两个值在不同的内存区域和寄存器里来回拷贝。

那么，如果我们优化一下会怎样呢？我们使用

clang -O1 -S max.c

之后，我们的max函数的汇编代码是：

movl    %esi, %eax
cmpl    %esi, %edi
cmovgl  %edi, %eax
retq

那么长的一串代码竟然变的如此简洁了。这个代码翻译成伪代码就是
很简单的事，并且把所有的操作都从对内存的操作变成了对寄存器的操作。

因此，由这个简单的例子我们可以看出来，如果寄存器的数量足够，并且代码中没有需要操作内存地址的时候，寄存器是足够胜任的，并且更加高效的。

寄存器

正因为如此，LLVM IR引入了虚拟寄存器的概念。在LLVM IR中，一个函数的局部变量可以是寄存器或者栈上的变量。对于寄存器而言，我们只需要像普通的赋值语句一样操作，但需要注意名字必须以%开头：

%local_variable = add i32 1, 2

此时，%local_variable这个变量就代表一个寄存器，它此时的值就是1和2相加的结果。我们可以写一个简单的程序验证这一点：

; register_test.ll
define i32 @main() {
    %local_variable = add i32 1, 2
    ret i32 %local_variable
}

我们查看其编译出的汇编代码，其主函数为：

main:
    movl    $2, %eax
    addl    $1, %eax
    retq

确实这个局部变量%local_variable变成了寄存器eax。
关于寄存器，我们还需了解一点。在不同的ABI下，会有一些callee-saved register（被调用者保存的寄存器）和caller-saved register（呼叫者保存的寄存器）。简单来说，就是在函数内部，某些寄存器的值不能改变。或者说，在函数返回时，某些寄存器的值要和进入函数前相同。比如，在System V的ABI下，rbp, rbx, r12, r13, r14, r15都需要满足这一条件，这在System V的ABI下被称作callee-saved registe。由于LLVM IR是面向多平台的，所以我们需要一份代码适用于多种ABI。因此，LLVM IR内部自动帮我们做了这些事。如果我们把所有没有被保留的寄存器都用光了，那么LLVM IR会帮我们把这些被保留的寄存器放在栈上，然后继续使用这些被保留寄存器。当函数退出时，会帮我们自动从栈上获取到相应的值放回寄存器内。

• Caller-saved（调用者保存寄存器 / 易失寄存器 volatile）
• Callee-saved（被调用者保存寄存器 / 非易失寄存器 non-volatile）

Caller = 发起调用的函数 A

Callee = 被调用的函数 B

A() → B()：A 是 caller，B 是 callee

1）Caller-saved register（调用者保存）

规则：

B 函数可以随便覆盖、篡改这些寄存器，不需要恢复！

如果 A 函数在调用 B 之后，还需要寄存器里原来的数据 → A 自己在调用 B 之前把值压栈保存，调用返回后恢复。

通俗一句话：

被调用函数想改就改，后果由调用者自己负责。

x86-64 System V 例子：rax, rdi, rsi, rdx, rcx, r8, r9, r10, r11

2）Callee-saved register（被调用者保存）

规则：

B 函数如果要使用这类寄存器，必须先把原有值保存到栈，函数返回前原样恢复！

A 函数放心调用 B，不需要预先保存这些寄存器；调用完值一定不变。

通俗一句话：

被调用函数想用就得先备份，临走还原，不能坑调用方。

x86-64 System V 例子：rbx, rbp, r12, r13, r14, r15

void A() 
{ 
	int x = 10; 
	B(); // 我还需要使用x 
}

场景 1：x 放在 caller-saved 寄存器

A 知道 B 可能毁掉这个寄存器，调用 B 之前，主动把 x 存入栈，B 返回后再读回来。

场景 2：x 放在 callee-saved 寄存器

A 完全不用管；就算 B 要用这个寄存器，B 内部会主动保存恢复，回来 x 完好无损。
那么，如果所有通用寄存器都用光了，该怎么办？LLVM IR会帮我们把剩余的值放在栈上，但是对我们用户而言，实际上都是虚拟寄存器，用户是感觉不到差别的。

因此，我们可以粗略地理解LLVM IR对寄存器的使用：

• 当所需寄存器数量较少时，直接使用caller-saved register，即不需要保留的寄存器

• 当caller-saved register不够时，将callee-saved register原本的值压栈，然后使用callee-saved register

• 当寄存器用光以后，就把多的虚拟寄存器的值压栈

• Caller-saved：调用者操心，被调用者随便造

• Callee-saved：被调用者操心，用完必须复原

我们可以写一个简单的程序验证。对于x86_64架构下，我们只需要使用15个虚拟寄存器就可以验证这件事。鉴于篇幅，我就不把代码放在文章中了，如果想看详细代码可以去我的GitHub仓库中查看many_registers_test.ll。我们将其编译成汇编语言之后，可以看到在函数开头就有

pushq    %r15
pushq    %r14
pushq    %r13
pushq    %r12
pushq    %rbx

也就是把那些需要保留的寄存器压栈。然后随着寄存器用光，第15个虚拟寄存器就会使用栈：

movl    $2, %eax
addl    $1, %eax
movl    %eax, -4(%rsp)

栈

我们之前说过，当不需要操作地址并且寄存器数量足够时，我们可以直接使用寄存器。而LLVM IR的策略保证了我们可以使用无数的虚拟寄存器。那么，在需要操作地址以及需要可变变量（之后会提到为什么）时，我们就需要使用栈。

LLVM IR对栈的使用十分简单，直接使用alloca指令即可。如：

%local_variable = alloca i32

就可以声明一个在栈上的变量了。关于栈上变量的操作，我会在之后提到，目前我们对栈上变量的了解只需这么多。

数据的使用

在之前的两篇文章中，我们解释了LLVM中是如何对应数据区、寄存器和栈上的数据的。那么，这些数据定义了以后，该如何使用呢？

全局变量和栈上变量皆指针

下面，我们就需要讲怎样使用全局变量和栈上的变量。这两种变量实际上是类似的，LLVM IR把它们都看作指针。也就是说，对于全局变量：

@global_variable = global i32 0

和栈上变量(alloca)

%local_variable = alloca i32    # 栈上局部变量

这两个变量实际上都是ptr指针，指向它们所处的一个i32大小的内存区域。所以，我们不能这样：

%1 = add i32 1, @global_variable ; Wrong!   因为类型不匹配

@global_variable 是 ptr 指针，add 需要 i32 数值类型，类型不匹配，不能直接拿来运算。
因为@global_variable只是一个指针。
如果要操作这些值，必须使用load和store这两个命令。如果我们要获取@global_variable的值，就需要

%1 = load i32, ptr @global_variable
# load：从指针指向内存读取数值 

#含义：

#从 `@global_variable` 这个指针指向的内存，取出里面的 `i32` 值，存入虚拟寄存器 `%1`。

#此时 `%1` 才是真正的整数，可以参与运算：

这个指令的意思是，把一个ptr指针@global_variable的i32类型的值赋给虚拟寄存器%1，然后我们就能愉快地

%2 = add i32 1, %1

这样了。

类似地，如果我们要将值存储到全局变量或栈上变量里，会需要store命令：

store i32 1, ptr @global_variable

这个代表将i32类型的值1赋给ptr类型的全局变量@global_variable所指的内存区域中。

SSA

LLVM IR是一个严格遵守SSA(Static Single Assignment)策略的语言。SSA的要求很简单：每个变量只被赋值一次。也就是说，你不能

%1 = add i32 1, 2
%1 = add i32 3, 4

对%1同时赋值两次是不被允许的。

SSA作为一个历史悠久的概念，已经有了相当成熟的相关技术。通过使用SSA，编译器可以进行更好的优化，应用更成熟的算法，得到更好的结果。这里因为个人能力有限，就不再多对SSA进行介绍。我们只需要知道，通过约束每个变量只被赋值一次，可以让LLVM更好地优化。

上面这个例子好做，直接把3加4的结果赋值给一个新的虚拟寄存器就好了。但是，并非所有的情况都这么简单。在一些复杂情况下，将值存储在栈上再取出来，或者使用phi指令（见之后控制语句一章），也是一个更好的选择。