# LLVM 架构与设计上

本问详细讨论了 LLVM 的一些设计原理，LLVM是一个拥有着诸多紧密结合的底层工具链组件（例如，汇编器、编译器、调试器等）的开源项目，这些组件旨在 Unix 系统上使用，并兼容现有语言编译工具。LLVM 这个名字曾经是一组字母缩写词----Low Level Virtual Machine，但现在只是一个包含多个工具链组件的项目名。相比较其他编译工具而言，LLVM 提供了一些独特的功能，并且以其一些出色的工具而闻名（例如：Clang 编译器（ C/C++/Objective-C 编译器，它比 GCC 编译器提供了更多的编译特性和语法支持，设计也比GCC更轻量）），但是LLVM 与其他编译器最主要不同之处在于它的内部架构设计。

从 2000 年 12 月开始，LLVM 被设计为包含一组具有可扩展接口的可重用库。当时，其他开源编程语言的编译器实现通常被设计为语言专用工具，通常为一个可执行文件。例如，没有采用可扩展设计的GCC静态编译器，所以他们的代码各个功能之间互相关联，耦合性很大从而导致无法从中分离解析器来进行静态分析或重构，可谓是牵一发而动全身。虽然脚本语言通常提供一种将它们的运行时和解释器嵌入到更大的应用程序中的方法（参考下：Java语言的解释器 + JIT 编译器），但这个运行时是包含单个整体代码块，没有办法重用其中的代码片段，各个语言实现的项目之间的共享的功能模块代码也很少。

除了编译器本身的组成之外，流行编程语言的编译器实现的社区通常是分为两大阵营：

提供传统的静态编译器，如 GCC、Free Pascal 和 FreeBASIC，
提供解释器形式的运行时编译器，或者即时编译器 (JIT)

很少在市面上看到同时支持这两种形式的编译器实现，如果勉强支持，通常他们之间也很少有代码共享。在过去的十年中，LLVM 极大地改变了这种局面。到目前为止，LLVM 已经被用作实现各种静态和运行时编译语言的编译器通用基础架构（例如，GCC、Java、.NET、Python、Ruby、Scheme、Haskell、D 等语言以及其他的小众语言）。它还取代了多种特殊用途专用语言编译器，例如 Apple 公司用于 OpenGL 堆栈中的运行时专业化引擎的语言和 Adobe 公司用于 After Effects 产品中的图像处理库语言。最后，LLVM 还被用于创建各种各样的新语言和运行时，其中最著名的可能是 OpenCL GPU 编程语言和运行时。

经典编译器设计简介

传统静态编译器（如 C 的编译器GCC一样）最流行的设计是三阶段设计，这里我称之为三明治设计。其主要组件是前端、优化器和后端，如图所示。前端用于解析源代码，检查语法错误，并构建特定语言的抽象语法树 (AST) 来表示输入代码，AST 语法树可以转换为新的中间语言表示并可以对其进行优化，而优化器和后端接收来自前端输出的中间代码进行目标语言的生成（这里为目标机器码）。

图：三明治编译器的三个主要组件

优化器负责对经过语法分析的中间语言，进行各种转换以尝试提高代码的运行时间，例如：消除冗余计算，其中产生的中间语言（IR）将独立于特定架构和语言。后端（也称为代码生成器）然后将中间代码映射到目标平台指令集。除了生成正确的代码外，它还负责生成利用所支持架构的特定指令集来构建高性能的特定平台的代码。编译器后端的常见部分包括：指令选择（使用指令集的哪个指令）、寄存器分配、指令调度。

该模型同样适用于解释器和 JIT 编译器。Java 虚拟机 (JVM) 也是该模型的一个实现，它使用通过javac命令编译的 Java 字节码作为前端和优化器之间的中间代码。

当编译器支持多种源语言或目标架构时，这种经典设计的优势就非常明显了。如果编译器在其优化器中使用通用代码（中间语言）表示，那么就可以为任何可以编译到该中间语言的源语言编写前端，并且可以为任何可以从它编译的特定目标平台编写后端，如图所示。也即，我们使用中间语言IR来解耦合前端与后端。

图：三明治架构设计优势（前后端均可自行设计，两者用IR来解耦）

使用这种设计，想让编译器支持新的源语言（例如，Algol 或 BASIC）那么只需要实现新的语言前端就可以，这时我们就可以复用现有的优化器和后端。如果这几个部分没有分开，实现新的源语言将需要从头开始设计前端、优化器、后端。因此三明治的编译器架构设计若需要支持N目标语言和 M源语言，那么只需要M个前端和N个后端即可，甚至有些后端由于存在，就不需要设计，而不是像不分开的设计将需要 N * M 编译器，不能复用任何代码。

三阶段设计的另一个优点是编译器工具集可以为程序员提供更广泛的功能，而不是它只支持一种源语言和一个目标语言。对于编译器的开源项目而言，这意味着有更多开源社区进行支持并借鉴其设计开发他们自己的编译器，这自然有助于对开源的编译器的提供更多功能增强和改进。这就是为什么有许多开源社区支持的开源编译器（如 GCC）可以生成比 FreePASCAL（特地语言且应用范围很窄的编译器）更好且经过特定优化的机器代码的原因。专有编译器并非如此，其质量与项目预算直接相关。例如，英特尔 ICC 编译器因其生成的代码质量而广为人知，尽管它服务的受众范围很窄。

三阶段设计的最后一个使之脱颖而出的优点是实现前端所需的架构和语言与优化器和后端所需的架构和语言不同，换言之，只要前端生成了后端需要IR，那么你可以随便写，后端只要识别了IR，那么你也可以随便写。将这些分开使编写编译器前端和后端人员更容易的增强和维护他们的负责的编译器的那部分代码。虽然这是一个设计问题，而不是技术问题，但它在实践中非常重要，特别是对于希望尽可能减少高度耦合的开源项目。

现有的语言实现

虽然三明治设计的好处令人叹服，并且在关于编译器原理的教科书中有详细的介绍，但实际上现有的编译器几乎从未完全按照该架构实现。在LLVM 项目启动前，纵观开源语言编译器的实现，会发现 Perl、Python、Ruby 和 Java 的语言编译器的实现不共享任何代码，也即每个语言都有一个自己的专用编译器。此外，像 Glasgow Haskell Compiler (GHC) 和 FreeBASIC 这样的项目虽然可以生成到多个不同的 CPU平台的机器码，但它们只支持一种特定的源语言。当时，还使用了多种特殊用途的编译器技术来实现用于图像处理、正则表达式、显卡驱动程序和其他需要 CPU 密集型工作的 JIT 编译器。上述这些代码都不能够被公用，每个编译器的运用场景都需要重新编写代码。

当然，三明治模型有三个主要的成功案例。第一个是 Java 和 .NET 虚拟机。它们提供 JIT 编译器、运行时支持，最重要的是定义了中间语言---字节码格式。这意味着任何可以编译为字节码格式的语言（其中有几十种，参考维基百科：https://en.wikipedia.org/wiki/List_of_JVM_languages，较为出名的语言为：Java，Kotlin，Groovy，Scala，Closure）都可以利用已经存在的优化器和 JIT 以及运行时，而不用重新构建。当然，使用虚拟的一大缺点便是这些实现在选择运行时时几乎没有灵活性可言，也即它们都被强制使用 JIT 编译、垃圾回收和特定的对象模型（Klass-Oop模型），当编译与该模型不匹配的语言时，这会导致性能极度下降，例如C语言。

第二个成功案例可能走了些弯路，但也是最流行的重用编译器技术的方法：将其他源语言统统转换为 C 代码（或其他语言）并通过现有的 C 编译器生成目标代码。这允许重用现有的优化器和代码生成器，提供了良好的灵活性并可以适度选择合适的运行时，并且编译器的前端实现非常容易理解、实现和维护。不幸的是，这样做会妨碍异常处理的有效实现，因为本身C语言对于异常的处理本就不如其他语言，比如Java的try catch块（C语言只有简陋的：goto、setjump、longjump），提供糟糕的调试体验，减慢编译速度，并且对于需要保证尾调用（指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果，参考下JS的闭包）或 C 不支持的其他功能的语言可能会出现问题。

该模型的最终成功实现是 GCC 编译器。GCC 支持许多前端和后端，并拥有一个非常活跃并人数较多的贡献者社区。GCC 作为一个 C 编译器有着悠久的历史，它支持多个目标语言，并为其他一些语言提供了 hacky 支持（为其他语言提供了较多的黑科技来使GCC支持多中源语言）。随着时间的发展，GCC 社区正在慢慢演变出更加灵活性的架构设计。从 GCC 4.4 开始，它出现了一个新的优化器（称为“GIMPLE Tuples”），它比以前的设计更接近于与编译器前端表示分离。此外，它支持的 Fortran 和 Ada 源语言前端使用不增加任何属性（原文为：干净，我想应是只生成相同的AST语法树，并不对该AST添加特定语言特性）的 AST 抽象语法树。

这三种实现虽然非常成功，但这种实现对它们的用途有很大的限制，因为它们被设计为单体应用程序（各个模块之间相互耦合在一个代码中）。例如，我们不可能将 GCC 嵌入到其他应用程序中，不可能将 GCC 用作其他运行时或JIT 编译器，或者不可能在不引入大部分编译器的代码情况下提取和重用 GCC 代码片段。若人们想要使用 GCC 的 C++ 前端进行文档生成、代码索引、重构和静态分析工具，那么人们不得不将 GCC 进行修改并以平台无关化的 XML 形式生成有效信息的单体应用程序，或者编写GCC插件以将外部代码注入到 GCC 进程中。如此，非常的麻烦，为什么不设计一个编译器，它的每个功能模块都可以单独拆出来使用，具备高度可定制化呢？

GCC 的各个部分不能作为工具库重用的原因有很多。包括大量使用全局变量、强制执行的常量、设计不良的数据结构、庞大的代码库以及使用宏定义阻止代码库被编译以支持多个源语言和目标语言。然而，最难解决的问题是源于其出现时期的早期设计架构问题。具体来说，GCC 存在代码分层问题和严重的高度耦合：后端依赖前端 AST 生成的调试信息，前端与后端耦合相同的数据结构（前端需要理解后端的数据结构，按照该结构生成后端需要的中间产物），且整个编译器依赖于基于命令行的产生的全局数据结构（预处理、编译、链接）。

LLVM 中间语言表示：LLVM IR

抛开GCC和其他编译器的历史背景，让我们直接深入了解 LLVM：其设计中最重要的一部分便是 LLVM 中间表示 (IR)，这是它用于在编译器中表示源语言代码的形式。LLVM IR 的出现旨在编译器的优化器部分中对源语言进行分析和转换，同时解耦合编译器前后端。它的设计考虑了许多特定目标语言，包括：支持轻量级运行时、跨功能/跨过程优化、整个程序分析和重组转换等。不过，它最重要的方面是它本身被定义为具有明确语义的语言。为了具体说明，这里是一个简单的.ll文件示例：

define i32 @add1(i32 %a, i32 %b) { // 定义add1函数，参数：i32 表示整形32类型

entry:

 %tmp1 = add i32 %a, %b

 ret i32 %tmp1 // 注意：这里返回值只标识一个临时寄存器，而不是特定寄存器

}



define i32 @add2(i32 %a, i32 %b) {

entry:

 %tmp1 = icmp eq i32 %a, 0

 br i1 %tmp1, label %done, label %recurse



recurse:

 %tmp2 = sub i32 %a, 1

 %tmp3 = add i32 %b, 1

 %tmp4 = call i32 @add2(i32 %tmp2, i32 %tmp3)

 ret i32 %tmp4



done:

 ret i32 %b

}

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

该LLVM IR 文件表示以下C语言。它提供了两种不同的整数相加方式。

unsigned add1(unsigned a, unsigned b) {

 return a+b;

}


unsigned add2(unsigned a, unsigned b) {

 if (a == 0) return b;

 return add2(a-1, b+1);

}

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

从这个例子可以看出，LLVM IR 是一个低等级的类似 RISC 风格的指令集。像真正的 RISC 指令集一样，它支持简单指令序列，如：加法、减法、比较和分支指令。这些指令采用三地址形式表示，这意味着它们接受一定数量的输入并在不同的寄存器中产生结果。LLVM IR 支持语法标签（类似于汇编的伪指令），所以看起来像一种奇怪的汇编语言形式。

与大多数 RISC 指令集不同，LLVM 使用简单的强类型系统（例如，i32表示一个 32 位整数，i32** 表示一个指向 32 位整数的指针），并且特定机器代码的一些细节被抽象掉了。例如，调用约定是通过指令和显式参数call抽象出来的，ret与机器代码的另一个显着区别是 LLVM IR 不使用一组固定的命名寄存器，它使用一组无限的以 % 字符命名的临时寄存器。

除了作为一种语言实现之外，LLVM IR 实际上以三种形式定义：上述的文本格式、通过优化和语法检查和并可以修改的内存结构、高效且密集的磁盘二进制位码格式。LLVM 项目还提供了将磁盘格式从文本转换为二进制的工具：llvm-as工具源语言生成文本格式的.ll文件或者磁盘二进制包含位码文件.bc，llvm-dis工具将 .bc文件进行解析并转换为.ll文本文件。

编译器的中间语言表示非常有趣且用处很大，因为它是编译器中优化器的福音，也即优化器不受特定源语言或特定目标机器的约束，只需要优化IR即可。另一方面，它也必须很好地服务于前端和后端。所以IR的设计必须易于编译器前端生成，并且具有高度的结构性和平台无关性，以允许对实际需要生成的目标语言执行重要的优化。

编写 LLVM IR 优化

为了直观地了解优化的工作原理，看一些示例将会加深理解。有许多不同种类的编译器优化技术，因此很难提供一种可以解决任意问题的做法。大多数优化都遵循简单的三部分结构：

寻找要优化的模式
验证匹配实例的转换是否安全/正确
进行优化并更新代码

最简单的优化是对算术恒等式的模式匹配，例如：对于任何整数X，X-X值为 0， X-0值为X，(X*2)-X值为X。第一个问题是这些在 LLVM IR 中是什么样子的。来看个例子：

⋮ ⋮ ⋮ 

%example1 = sub i32 %a, %a 

⋮ ⋮ ⋮ 

%example2 = sub i32 %b, 0 

⋮ ⋮ ⋮ 

%tmp = mul i32 %c, 2 

%example3 = sub i32 %tmp, %c 

⋮ ⋮ ⋮

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

对于这些类型进行的窥孔优化，LLVM 提供了一个指令简化接口，该接口被各种其他更高级别的转换用作实用程序。这些特定的转换在SimplifySubInst函数中，如下所示：

// X - 0 -> X 

if (match(Op1, m_Zero())) 

 return Op0; 



// X - X -> 0 

if (Op0 == Op1) 

 return Constant::getNullValue(Op0->getType()); 



// (X*2) - X -> X 

if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>()))) 

 return Op1; 



……



return 0；// 没有匹配，返回 null 表示没有优化

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

在此代码中，Op0 和 Op1 表示整数减法指令的左右操作数（这里不考虑IEEE浮点数，因为浮点数的计算与整数计算不一样，需要考虑精度问题）。LLVM 是用 C++ 实现的，它的模式匹配能力相较于其他语言来说较弱（与 Objective Caml 等函数式语言相比），但它确实提供了一个非常通用的模板系统，允许我们实现类似模式匹配的功能。该match函数和m_XX 函数允许我们对 LLVM IR 代码执行声明性模式匹配操作，例如：m_Specific仅当乘法的左侧的Op0与 Op1 相同时，才执行匹配。

总之，以上三种情况都是模式匹配，如果可以匹配，则调用函数优化返回替换原有指令，如果无法替换，则返回0。该函数的调用者 ( SimplifyInstruction) 是一个调度程序，它负责对指令操作码进行替换，调度每个操作码到目标函数对该操作进行优化。它将在优化器中进行调用。一个简单的调用程序如下所示：

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 

 if (Value *V = SimplifyInstruction(I)) 

  I->replaceAllUsesWith(V );

1
2
3
4
5

这段代码简单地遍历BasicBlock块中的每条指令，检查它们中的任何一条是否可以优化，如果可以优化（SimplifyInstruction 函数返回非 null），那么它使用该 replaceAllUsesWith 函数使用更简单形式的来简化操作并更新代码中对应的代码。

← Netty 核心原理十八内存池详细设计要领 LLVM 架构与设计中 →