24|中间代码：兼容不同的语言和硬件

前几节课，我带你尝试不通过 IR，直接生成汇编代码，这是为了帮你快速破冰，建立直觉。在这个过程中，你也遇到了一些挑战，比如：

• 你要对生成的代码进行优化，才有可能更好地使用寄存器和内存，同时也能减少代码量；
• 另外，针对不同的 CPU 和操作系统，你需要调整生成汇编代码的逻辑。

这些实际体验，都进一步验证了20 讲中，IR 的作用：我们能基于 IR 对接不同语言的前端，也能对接不同的硬件架构，还能做很多的优化。

既然 IR 有这些作用，那你可能会问，IR 都是什么样子的呢？有什么特点？如何生成 IR 呢？

本节课，我就带你了解 IR 的特点，认识常见的三地址代码，学会如何把高级语言的代码翻译成 IR。然后，我还会特别介绍 LLVM 的 IR，以便后面使用 LLVM 这个工具。

首先，来看看 IR 的特征。

介于中间的语言

IR 的意思是中间表达方式，它在高级语言和汇编语言的中间，这意味着，它的特征也是处于二者之间的。

与高级语言相比，IR 丢弃了大部分高级语言的语法特征和语义特征，比如循环语句、if 语句、作用域、面向对象等等，它更像高层次的汇编语言；而相比真正的汇编语言，它又不会有那么多琐碎的、与具体硬件相关的细节。

相信你在学习汇编语言的时候，会发现汇编语言的细节特别多。比如，你要知道很多指令的名字和用法，还要记住很多不同的寄存器。在 22 讲，我提到，如果你想完整地掌握 x86-64 架构，还需要接触很多指令集，以及调用约定的细节、内存使用的细节等等（参见 Intel 的手册）。

仅仅拿指令的数量来说，据有人统计，Intel 指令的助记符有 981 个之多！都记住怎么可能啊。所以说，汇编语言并不难，而是麻烦。

IR 不会像 x86-64 汇编语言那么繁琐，但它却包含了足够的细节信息，能方便我们实现优化算法，以及生成针对目标机器的汇编代码。

另外，我在 20 讲提到，IR 有很多种类（AST 也是一种 IR），每种 IR 都有不同的特点和用途，有的编译器，甚至要用到几种不同的 IR。

我们在后端部分所讲的 IR，目的是方便执行各种优化算法，并有利于生成汇编。这种 IR，可以看做是一种高层次的汇编语言，主要体现在：

• 它可以使用寄存器，但寄存器的数量没有限制；
• 控制结构也跟汇编语言比较像，比如有跳转语句，分成多个程序块，用标签来标识程序块等；
• 使用相当于汇编指令的操作码。这些操作码可以一对一地翻译成汇编代码，但有时一个操作码会对应多个汇编指令。

下面来看看一个典型 IR：三地址代码，简称 TAC。

认识典型的 IR：三地址代码（TAC）

下面是一种常见的 IR 的格式，它叫做三地址代码（Three Address Code, TAC），它的优点是很简洁，所以适合用来讨论算法：

1
2
3
4

x := y op z   // 二元操作

x := op y     // 一元操作

每条三地址代码最多有三个地址，其中两个是源地址（比如第一行代码的 y 和 z），一个是目的地址（也就是 x），每条代码最多有一个操作（op）。

我来举几个例子，带你熟悉一下三地址代码，这样，你能掌握三地址代码的特点，从高级语言的代码转换生成三地址代码。

1. 基本的算术运算：

1
2
3
4

int a, b, c, d;

a = b + c * d;

TAC：

1
2
3
4

t1 := c * d

a  := b + t1

t1 是新产生的临时变量。当源代码的表达式中包含一个以上的操作符时，就需要引入临时变量，并把原来的一条代码拆成多条代码。

2. 布尔值的计算：

1
2
3
4
5
6
7
8

int a, b;

bool x, y;

x = a * 2 < b;

y = a + 3 == b;

TAC：

1
2
3
4
5
6
7
8

t1 := a * 2;

x  := t1 < b;

t2 := a + 3;

y  := t2 == b;

布尔值实际上是用整数表示的，0 代表 false，非 0 值代表 true。

3. 条件语句：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int a, b c;

if (a < b )

    c = b;

else

    c = a;  

c = c * 2;      

TAC：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

  t1 := a < b;

  IfZ t1 Goto L1;

  c := a;

  Goto L2;

L1:

  c := b;

L2:

  c := c * 2;  

IfZ 是检查后面的操作数是否是 0，“Z”就是“Zero”的意思。这里使用了标签和 Goto 语句来进行指令的跳转（Goto 相当于 x86-64 的汇编指令 jmp）。

4. 循环语句：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int a, b;

while (a < b){

  a = a + 1;

}

a = a + b;

TAC：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

L1:

  t1 := a < b;

  IfZ t1 Goto L2;

  a := a + 1;

  Goto L1;

L2:

  a := a + b;  

三地址代码的规则相当简单，我们可以通过比较简单的转换规则，就能从 AST 生成 TAC。

在课程中，三地址代码主要用来描述优化算法，因为它比较简洁易读，操作（指令）的类型很少，书写方式也符合我们的日常习惯。**不过，我并不用它来生成汇编代码，因为它含有的细节信息还是比较少，**比如，整数是 16 位的、32 位的还是 64 位的？目标机器的架构和操作系统是什么？生成二进制文件的布局是怎样的等等？

**我会用 LLVM 的 IR 来承担生成汇编的任务，**因为它有能力描述与目标机器（CPU、操作系统）相关的更加具体的信息，准确地生成目标代码，从而真正能够用于生产环境。

**在讲这个问题之前，我想先延伸一下，讲讲另外几种 IR 的格式，**主要想帮你开拓思维，如果你的项目需求，恰好能用这种 IR 实现，到时不妨拿来用一下：

• 首先是四元式。它是与三地址代码等价的另一种表达方式，格式是：（OP，arg1，arg2，result）所以，“a := b + c”就等价于（+，b，c，a）。
• 另一种常用的格式是逆波兰表达式。它把操作符放到后面，所以也叫做后缀表达式。“b + c”对应的逆波兰表达式是“b c +”；而“a = b + c”对应的逆波兰表达式是“a b c + =”。

**逆波兰表达式特别适合用栈来做计算。**比如计算“b c +”，先从栈里弹出加号，知道要做加法操作，然后从栈里弹出两个操作数，执行加法运算即可。这个计算过程，跟深度优先的遍历 AST 是等价的。所以，采用逆波兰表达式，有可能让你用一个很简单的方式就实现公式计算功能，**如果你编写带有公式功能的软件时可以考虑使用它。**而且，从 AST 生成逆波兰表达式也非常容易。

三地址代码主要是学习算法的工具，或者用于实现比较简单的后端，要实现工业级的后端，充分发挥硬件的性能，你还要学习 LLVM 的 IR。

认识 LLVM 汇编码

**LLVM 汇编码（LLVM Assembly），是 LLVM 的 IR。**有的时候，我们就简单地称呼它为 LLVM 语言，因此我们可以把用 LLVM 汇编码书写的一个程序文件叫做 LLVM 程序。

我会在下一讲，详细讲解 LLVM 这个开源项目。本节课作为铺垫，告诉我们在使用 LLVM 之前，要先了解它的核心——IR。

首先，LLVM 汇编码是采用静态单赋值代码形式的。

在三地址代码上再加一些限制，就能得到另一种重要的代码，即静态单赋值代码（Static Single Assignment, SSA），在静态单赋值代码中，一个变量只能被赋值一次，来看个例子。

“y = x1 + x2 + x3 + x4”的普通三地址代码如下：

1
2
3
4
5
6

y := x1 + x2;

y := y + x3;

y := y + x4;

其中，y 被赋值了三次，如果写成 SSA 的形式，就只能写成下面的样子：

1
2
3
4
5
6

t1 := x1 + x2;

t2 := t1 + x3;

y  := t2 + x4; 

为什么要费力写成这种形式呢，还要为此多添加 t1 和 t2 两个临时变量？原因是 SSA 的形式，体现了精确的“使用 - 定义”关系。

每个变量很确定地只会被定义一次，然后可以多次使用。这种特点使得基于 SSA 更容易做数据流分析，而数据流分析又是很多代码优化技术的基础，所以，几乎所有语言的编译器、解释器或虚拟机中都使用了 SSA，因为有利于做代码优化。而 LLVM 的 IR，也是采用 SSA 的形式，也是因为 SSA 方便做代码优化。

**其次，LLVM IR 比起三地址代码，有更多的细节信息。**比如整型变量的字长、内存对齐方式等等，所以使用 LLVM IR 能够更准确地翻译成汇编码。

看看下面这段 C 语言代码：

1
2
3
4
5
6
7
8

int fun1(int a, int b){

  int c = 10;

  return a + b + c;

}

对应的 LLLM 汇编码如下（这是我在 macOS 上生成的）：

 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
44
45
46
47
48
49
50
51
52

; ModuleID = 'fun1.c'

source_filename = "fun1.c"

target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"

target triple = "x86_64-apple-macosx10.14.0"

; Function Attrs: noinline nounwind optnone ssp uwtable

define i32 @fun1(i32, i32) #0 {

  %3 = alloca i32, align 4        // 为 3 个变量申请空间

  %4 = alloca i32, align 4     

  %5 = alloca i32, align 4

  store i32 %0, i32* %3, align 4  // 参数 1 赋值给变量 1

  store i32 %1, i32* %4, align 4  // 参数 2 赋值给变量 2

  store i32 10, i32* %5, align 4  // 常量 10 赋值给变量 3

  %6 = load i32, i32* %3, align 4 //

  %7 = load i32, i32* %4, align 4

  %8 = add nsw i32 %6, %7

  %9 = load i32, i32* %5, align 4

  %10 = add nsw i32 %8, %9

  ret i32 %10

}

attributes #0 = { noinline nounwind optnone ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

 !llvm.module.flags = !{!0, !1, !2}

!llvm.ident = !{!3}

 !0 = !{i32 2, !"SDK Version", [2 x i32] [i32 10, i32 14]}

!1 = !{i32 1, !"wchar_size", i32 4}

!2 = !{i32 7, !"PIC Level", i32 2}

!3 = !{!"Apple LLVM version 10.0.1 (clang-1001.0.46.4)"}

这些代码看上去确实比三地址代码复杂，但还是比汇编精简多了，比如 LLVM IR 的指令数量连 x86-64 汇编的十分之一都不到。

我们来熟悉一下里面的元素：

• 模块

LLVM 程序是由模块构成的，这个文件就是一个模块。模块里可以包括函数、全局变量和符号表中的条目。链接的时候，会把各个模块拼接到一起，形成可执行文件或库文件。

在模块中，你可以定义目标数据布局（target datalayout）。例如，开头的小写“e”是低字节序（Little Endian）的意思，对于超过一个字节的数据来说，低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。

1
2

target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"

“target triple”用来定义模块的目标主机，它包括架构、厂商、操作系统三个部分。

1
2

target triple = "x86_64-apple-macosx10.14.0"

• 函数

在示例代码中有一个以 define 开头的函数的声明，还带着花括号。这有点儿像 C 语言的写法，比汇编用采取标签来表示一个函数的可读性更好。

函数声明时可以带很多修饰成分，比如链接类型、调用约定等。如果不写，缺省的链接类型是 external 的，也就是可以像23 讲中做链接练习的那样，暴露出来被其他模块链接。调用约定也有很多种选择，缺省是“ccc”，也就是 C 语言的调用约定（C Calling Convention），而“swiftcc”则是 swift 语言的调用约定。这些信息都是生成汇编时所需要的。

示例中函数 fun1 还带有“#0”的属性值，定义了许多属性。这些也是生成汇编时所需要的。

• 标识符

分为全局的（Glocal）和本地的（Local）：全局标识符以 @开头，包括函数和全局变量，前面代码中的 @fun1 就是；本地标识符以 % 开头。

有的标识符是有名字的，比如 @fun1 或 %a，有的是没有名字的，用数字表示就可以了，如 %1。

• 操作码

alloca、store、load、add、ret 这些，都是操作码。它们的含义是：

它们跟我们之前学到的汇编很相似。但是似乎函数体中的代码有点儿长。怎么一个简单的“a+b+c”就翻译成了 10 多行代码，还用到了那么多临时变量？不要担心，**这只是完全没经过优化的格式，**带上优化参数稍加优化以后，它就会被精简成下面的样子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

define i32 @fun1(i32, i32) local_unnamed_addr #0 {

  %3 = add i32 %0, 10

  %4 = add i32 %3, %1

  ret i32 %4

}

• 类型系统

汇编是无类型的。如果你用 add 指令，它就认为你操作的是整数。而用 fadd（或 addss）指令，就认为你操作的是浮点数。这样会有类型不安全的风险，把整型当浮点数用了，造成的后果是计算结果完全错误。

LLVM 汇编则带有一个类型系统。它能避免不安全的数据操作，并且有助于优化算法。这个类型系统包括基础数据类型、函数类型和 void 类型。

函数类型是包括对返回值和参数的定义，比如：i32 (i32)；

void 类型不代表任何值，也没有长度。

• 全局变量和常量

在 LLVM 汇编中可以声明全局变量。全局变量所定义的内存，是在编译时就分配好了的，而不是在运行时，例如下面这句定义了一个全局变量 C：

1
2

@c = global i32 100, align 4

你也可以声明常量，它的值在运行时不会被修改：

1
2

@c = constant i32 100, align 4

• 元数据

在代码中你还看到以“!”开头的一些句子，这些是元数据。这些元数据定义了一些额外的信息，提供给优化器和代码生成器使用。

• 基本块

函数中的代码会分成一个个的基本块，可以用标签（Label）来标记一个基本块。下面这段代码有 4 个基本块，其中第一个块有一个缺省的名字“entry”，也就是作为入口的基本块，这个基本块你不给它标签也可以。

 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

define i32 @bb(i32) #0 {

  %2 = alloca i32, align 4

  %3 = alloca i32, align 4

  store i32 %0, i32* %3, align 4

  %4 = load i32, i32* %3, align 4

  %5 = icmp sgt i32 %4, 0

  br i1 %5, label %6, label %9

 ; <label>:6:                                      ; preds = %1

  %7 = load i32, i32* %3, align 4

  %8 = mul nsw i32 %7, 2

  store i32 %8, i32* %2, align 4

  br label %12

 ; <label>:9:                                      ; preds = %1

  %10 = load i32, i32* %3, align 4

  %11 = add nsw i32 %10, 3

  store i32 %11, i32* %2, align 4

  br label %12

 ; <label>:12:                                     ; preds = %9, %6

  %13 = load i32, i32* %2, align 4

  ret i32 %13

}

这段代码实际上相当于下面这段 C 语言的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int bb(int b){

    if (b > 0)

        return b * 2;

    else

        return b + 3;

}

每个基本块是一系列的指令。我们分析一下标签为 9 的基本块，让你熟悉一下基本块和 LLVM 指令的特点：

第一行（%10 = load i32, i32* %3, align 4）的含义是：把 3 号变量（32 位整型）从内存加载到寄存器，叫做 10 号变量，其中，内存对齐是 4 字节。

**我在这里延伸一下，**我们在内存里存放数据的时候，有时会从 2、4、8 个字节的整数倍地址开始存。有些汇编指令要求必须从这样对齐的地址来取数据。另一些指令没做要求，但如果是不对齐的，比如是从 0x03 地址取数据，就要花费更多的时钟周期。但缺点是，内存对齐会浪费内存空间。

第一行是整个基本块的唯一入口，从其他基本块跳转过来的时候，只能跳转到这个入口行，不能跳转到基本块中的其他行。

第二行（%11 = add nsw i32 %10, 3）的含义是：把 10 号变量（32 位整型）加上 3，保存到 11 号变量，其中 nsw 是加法计算时没有符号环绕（No Signed Wrap）的意思。它的细节你可以查阅“LLVM 语言参考手册”。

第三行（store i32 %11, i32* %2, align 4）的含义是：把 11 号变量（32 位整型）存入内存中的 2 号变量，内存对齐 4 字节。

第四行（br label %12）的含义是：跳转到标签为 12 的代码块。其中，br 指令是一条终结指令。终结指令要么是跳转到另一个基本块，要么是从函数中返回（ret 指令），基本块的最后一行必须是一条终结指令。

最后我要强调，从其他基本块不可以跳转到入口基本块，也就是函数中的第一个基本块。这个规定也是有利于做数据优化。

以上就是对 LLVM 汇编码的概要介绍（更详细的信息了解可以参见“LLVM 语言参考手册”）。

这样，你实际上就可以用 LLVM 汇编码来编写程序了，或者将 AST 翻译成 LLVM 汇编码。听上去有点让人犯怵，因为 LLVM 汇编码的细节也相当不少，好在，LLVM 提供了一个 IR 生成的 API（应用编程接口），可以让我们更高效、更准确地生成 IR。

课程小结

IR 是我们后续做代码优化、汇编代码生成的基础，在本节课中，我想让你明确的要点如下：

1. 三地址代码是很常见的一种 IR，包含一个目的地址、一个操作符和至多两个源地址。它等价于四元式。我们在 27 讲和 28 讲中的优化算法，会用三地址代码来讲解，这样比较易于阅读。

2.LLVM IR 的第一个特点是静态单赋值（SSA），也就是每个变量（地址）最多被赋值一次，它这种特性有利于运行代码优化算法；第二个特点是带有比较多的细节，方便我们做优化和生成高质量的汇编代码。

通过本节课，你应该对于编译器后端中常常提到的 IR 建立了直观的认识，相信通过接下来的练习，你一定会消除对 IR 的陌生感，让它成为你得心应手的好工具！

一课一思

我们介绍了 IR 的特点和几种基本的 IR，在你的领域，比如人工智能领域，你了解其他的 IR 吗？它带来了什么好处？欢迎分享你的经验和观点。

最后，感谢你的阅读，如果这篇文章让你有所收获，也欢迎你将它分享给更多的人。