开源应用架构（第1卷）
LLVM

11.1.1. 此设计的含义

这种经典设计的最大优势在于，当编译器决定支持多种源语言或目标架构时。如果编译器在其优化器中使用通用的代码表示，那么可以为任何可以编译到它的语言编写前端，并且可以为任何可以从中编译的目标编写后端，如图 11.2所示。

使用此设计，将编译器移植以支持新的源语言（例如，Algol 或 BASIC）需要实现新的前端，但可以重用现有的优化器和后端。如果这些部分没有分开，那么实现新的源语言将需要从头开始，因此支持N个目标和M个源语言将需要 N*M 个编译器。

三阶段设计的另一个优点（直接源于可重定向性）是，编译器为比仅支持一种源语言和一个目标的编译器更广泛的程序员群体提供服务。对于开源项目而言，这意味着有更大的潜在贡献者社区可以从中汲取，这自然会导致对编译器进行更多增强和改进。这就是为什么服务于许多社区的开源编译器（如 GCC）往往比 FreePASCAL 等范围更窄的编译器生成优化更好的机器代码的原因。对于专有编译器来说情况并非如此，其质量与项目的预算直接相关。例如，英特尔 ICC 编译器以其生成的代码质量而闻名，即使它服务于范围较窄的用户群体。

三阶段设计的最后一个主要优点是，实现前端所需的技能与优化器和后端所需的技能不同。将它们分开使“前端人员”更容易增强和维护他们负责的编译器部分。虽然这是一个社会问题，而不是技术问题，但在实践中它非常重要，特别是对于希望尽可能降低贡献门槛的开源项目而言。

define i32 @add1(i32 %a, i32 %b) {
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
}

unsigned add1(unsigned a, unsigned b) {
  return a+b;
}

// Perhaps not the most efficient way to add two numbers.
unsigned add2(unsigned a, unsigned b) {
  if (a == 0) return b;
  return add2(a-1, b+1);
}

11.3.1. 编写 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
⋮    ⋮    ⋮

对于这些类型的“窥孔”转换，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;  // Nothing matched, return null to indicate no transformation.

在此代码中，Op0 和 Op1 分别绑定到整数减法指令的左操作数和右操作数（重要的是，这些恒等式不一定适用于 IEEE 浮点数！）。LLVM 是用 C++ 实现的，C++ 的模式匹配能力并不为人所知（与 Objective Caml 等函数式语言相比），但它确实提供了一个非常通用的模板系统，使我们能够实现类似的功能。match 函数和 m_ 函数允许我们对 LLVM IR 代码执行声明式模式匹配操作。例如，m_Specific 谓词仅在乘法的左侧与 Op1 相同的情况下才匹配。

这三种情况都进行了模式匹配，并且该函数如果可以则返回替换，或者如果无法替换则返回空指针。此函数的调用者（SimplifyInstruction）是一个调度程序，它根据指令操作码进行切换，并分派到每个操作码的辅助函数。它被各种优化器调用。一个简单的驱动程序如下所示

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
  if (Value *V = SimplifyInstruction(I))
    I->replaceAllUsesWith(V);

此代码简单地循环遍历块中的每个指令，检查它们是否可以简化。如果是（因为 SimplifyInstruction 返回非空值），它将使用 replaceAllUsesWith 方法使用更简单的形式更新代码中使用可简化操作的任何内容。

11.4.1. LLVM IR 是完整的代码表示

特别是，LLVM IR 既有良好的规范，又是优化器的唯一接口。此属性意味着编写 LLVM 前端所需了解的只是 LLVM IR 是什么、它是如何工作的以及它期望的不变式。由于 LLVM IR 具有第一类文本形式，因此可以并且合理地构建一个前端，该前端将 LLVM IR 作为文本输出，然后使用 Unix 管道将其发送到您选择的优化器序列和代码生成器。

这可能令人惊讶，但实际上这是 LLVM 的一个非常新颖的特性，也是其在广泛不同应用中取得成功的关键原因之一。即使是广泛成功且架构良好的 GCC 编译器也没有此属性：其 GIMPLE 中级表示不是一个自包含的表示。例如，当 GCC 代码生成器准备发出 DWARF 调试信息时，它会回溯并遍历源级“树”形式。GIMPLE 本身使用代码中操作的“元组”表示，但（至少在 GCC 4.5 中）仍然将操作数表示为对源级树形式的引用。

这意味着前端作者需要了解并生成 GCC 的树数据结构以及 GIMPLE 才能编写 GCC 前端。GCC 后端存在类似的问题，因此它们还需要了解 RTL 后端的工作原理的一些细节。最后，GCC 无法转储“表示我所有代码的内容”，也无法以文本形式读取和写入 GIMPLE（以及构成代码表示的相关数据结构）。结果是，使用 GCC 进行实验比较困难，因此它拥有相对较少的端。

11.4.2. LLVM 是一个库的集合

在 LLVM IR 设计之后，LLVM 的下一个最重要的方面是它被设计为一组库，而不是像 GCC 这样的单片命令行编译器或像 JVM 或 .NET 虚拟机这样的不透明虚拟机。LLVM 是一种基础架构，是一组有用的编译器技术，可以应用于特定问题（例如构建 C 编译器或特效流水线中的优化器）。虽然它是其最强大的功能之一，但它也是其最不为人理解的设计要点之一。

让我们以优化器的设计为例：它读取 LLVM IR，对其进行一些处理，然后发出 LLVM IR，希望它可以更快地执行。在 LLVM（以及许多其他编译器）中，优化器被组织成一个由不同的优化过程组成的流水线，每个过程都在输入上运行，并有机会做一些事情。常见的过程示例包括内联器（将函数的主体替换为调用站点）、表达式重关联、循环不变代码移动等。根据优化级别，将运行不同的过程：例如，在 -O0（无优化）下，Clang 编译器不运行任何过程，在 -O3 下，它在其优化器中运行一系列 67 个过程（截至 LLVM 2.8）。

每个 LLVM 过程都写成一个 C++ 类，该类（间接地）派生自 Pass 类。大多数过程都写在一个 .cpp 文件中，并且它们对 Pass 类的子类是在匿名命名空间中定义的（这使其完全对定义文件私有）。为了使该过程有用，文件外部的代码必须能够获取它，因此从该文件中导出了一个单一函数（用于创建该过程）。以下是一个稍微简化的过程示例，使问题具体化。⁶

namespace {
  class Hello : public FunctionPass {
  public:
    // Print out the names of functions in the LLVM IR being optimized.
    virtual bool runOnFunction(Function &F) {
      cerr << "Hello: " << F.getName() << "\n";
      return false;
    }
  };
}

FunctionPass *createHelloPass() { return new Hello(); }

如前所述，LLVM 优化器提供了数十种不同的过程，每种过程的编写风格都类似。这些过程被编译成一个或多个 .o 文件，然后构建成一系列归档库（Unix 系统上的 .a 文件）。这些库提供了各种分析和转换功能，并且这些过程尽可能地松散耦合：它们应该能够独立运行，或者如果它们依赖于其他一些分析来完成其工作，则明确声明它们之间的依赖关系。当给定一系列要运行的过程时，LLVM PassManager 会使用显式依赖信息来满足这些依赖关系并优化过程的执行。

库和抽象功能很棒，但它们实际上并不能解决问题。有趣的部分是当有人想要构建一个可以从编译器技术中受益的新工具时，也许是一个用于图像处理语言的 JIT 编译器。此 JIT 编译器的实现者心中有一组约束：例如，也许图像处理语言对编译时延迟高度敏感，并且具有一些习惯用法语言属性，这些属性对于提高性能至关重要。

LLVM 优化器的基于库的设计允许我们的实现者选择和确定过程执行的顺序以及哪些过程对图像处理领域有意义：如果所有内容都定义为一个大型函数，那么在内联上浪费时间是没有意义的。如果指针很少，则别名分析和内存优化不值得考虑。但是，尽管我们尽了最大努力，但 LLVM 并不能神奇地解决所有优化问题！由于过程子系统是模块化的，并且 PassManager 本身不了解过程的内部细节，因此实现者可以自由地实现自己的特定于语言的过程来弥补 LLVM 优化器的不足或利用特定于语言的优化机会。图 11.4 显示了我们假设的 XYZ 图像处理系统的简单示例

一旦选择了优化集（并对代码生成器做出了类似的决策），图像处理编译器就会构建成可执行文件或动态库。由于对 LLVM 优化过程的唯一引用是每个 .o 文件中定义的简单 create 函数，并且由于优化器位于 .a 归档库中，因此只有实际使用的优化过程会被链接到最终应用程序中，而不是整个 LLVM 优化器。在上面的示例中，由于存在对 PassA 和 PassB 的引用，因此它们将被链接进来。由于 PassB 使用 PassD 进行一些分析，因此 PassD 也被链接进来。但是，由于 PassC（以及数十种其他优化）未使用，因此其代码不会链接到图像处理应用程序中。

这就是 LLVM 基于库的设计发挥作用的地方。这种简单的设计方法允许 LLVM 提供大量功能，其中一些功能可能仅对特定受众有用，而不会惩罚那些只想做简单事情的库客户端。相比之下，传统的编译器优化器被构建为一个紧密互连的代码块，这使得对其进行子集化、推理和快速上手变得更加困难。使用 LLVM，您可以理解各个优化器，而无需了解整个系统是如何组合在一起的。

这种基于库的设计也是许多人误解 LLVM 的原因：LLVM 库具有许多功能，但它们本身不做任何事情。库客户端（例如 Clang C 编译器）的设计者需要决定如何最好地利用这些组件。这种细致的分层、分解和对子集能力的关注也是 LLVM 优化器能够在不同上下文中用于如此广泛的不同应用的原因。此外，仅仅因为 LLVM 提供了 JIT 编译功能，并不意味着每个客户端都使用它。

11.5.1. LLVM 目标描述文件

“混合匹配”方法允许目标作者选择适合其架构的内容，并允许在不同目标之间进行大量的代码重用。这带来了另一个挑战：每个共享组件都需要能够以通用的方式推断目标特定属性。例如，共享寄存器分配器需要知道每个目标的寄存器文件以及指令与其寄存器操作数之间存在的约束。LLVM 对此的解决方案是让每个目标在声明式领域特定语言（一组.td文件）中提供目标描述，并由 tblgen 工具进行处理。x86 目标的（简化）构建过程如图 11.5所示。

.td文件支持的不同子系统允许目标作者构建目标的不同部分。例如，x86 后端定义了一个名为“GR32”的寄存器类，该类包含其所有 32 位寄存器（在.td文件中，目标特定定义全部大写），如下所示

def GR32 : RegisterClass<[i32], 32,
  [EAX, ECX, EDX, ESI, EDI, EBX, EBP, ESP,
   R8D, R9D, R10D, R11D, R14D, R15D, R12D, R13D]> { … }

此定义表示此类中的寄存器可以保存 32 位整数值（“i32”），首选 32 位对齐，具有指定的 16 个寄存器（在.td文件的其他位置定义）以及一些其他信息来指定首选分配顺序和其他内容。给定此定义，特定指令可以引用它，将其用作操作数。例如，“对 32 位寄存器求反”指令定义如下

let Constraints = "$src = $dst" in
def NOT32r : I<0xF7, MRM2r,
               (outs GR32:$dst), (ins GR32:$src),
               "not{l}\t$dst",
               [(set GR32:$dst, (not GR32:$src))]>;

此定义表示 NOT32r 是一个指令（它使用I tblgen 类），指定编码信息（0xF7, MRM2r），指定它定义了一个“输出”32 位寄存器$dst，并具有一个名为$src的 32 位寄存器“输入”（上面定义的GR32寄存器类定义了哪些寄存器对操作数有效），指定指令的汇编语法（使用{}语法来处理 AT&T 和 Intel 语法），指定指令的效果，并在最后一行提供它应该匹配的模式。“let”约束在第一行告诉寄存器分配器输入和输出寄存器必须分配到同一个物理寄存器。

此定义是对指令的非常密集的描述，并且常见的 LLVM 代码可以利用从中派生的许多信息（由tblgen工具）。此定义足以使指令选择通过对编译器的输入 IR 代码进行模式匹配来形成此指令。它还告诉寄存器分配器如何处理它，足以将指令编码和解码为机器码字节，并且足以以文本形式解析和打印指令。这些功能允许 x86 目标支持从目标描述生成独立的 x86 汇编程序（它是“gas”GNU 汇编程序的替代品）和反汇编程序，以及处理 JIT 的指令编码。

除了提供有用的功能外，从相同的“真相”生成多条信息还有其他原因。这种方法使得汇编程序和反汇编程序几乎不可能在汇编语法或二进制编码方面存在分歧。它还使目标描述易于测试：指令编码可以进行单元测试，而无需涉及整个代码生成器。

虽然我们的目标是将尽可能多的目标信息以良好的声明式形式放入.td文件中，但我们仍然没有所有信息。相反，我们要求目标作者为各种支持例程编写一些 C++ 代码，并实现他们可能需要的任何目标特定 Pass（例如X86FloatingPoint.cpp，它处理 x87 浮点栈）。随着 LLVM 不断为新目标增长，增加可以在.td文件中表达的目标数量变得越来越重要，并且我们继续提高.td文件的表达能力来处理这种情况。一个很大的好处是，随着时间的推移，在 LLVM 中编写目标变得越来越容易。

11.6.1. 选择每个阶段何时何地运行

如前所述，LLVM IR 可以有效地（反）序列化到/从称为 LLVM 位代码的二进制格式。由于 LLVM IR 是自包含的，并且序列化是一个无损过程，因此我们可以执行部分编译，将我们的进度保存到磁盘，然后在将来的某个时间继续工作。此功能提供了许多有趣的功能，包括对链接时和安装时优化的支持，这两者都将代码生成延迟到“编译时”。

链接时优化 (LTO) 解决了编译器传统上一次只看到一个翻译单元（例如，一个.c文件及其所有头文件）的问题，因此无法跨文件边界进行优化（例如内联）。LLVM 编译器（如 Clang）通过-flto或-O4命令行选项支持此功能。此选项指示编译器将 LLVM 位代码输出到.o文件而不是写入本机目标文件，并将代码生成延迟到链接时，如图 11.6所示。

具体细节因您使用的操作系统而异，但重要的是链接器检测到它在.o文件中具有 LLVM 位代码而不是本机目标文件。当它看到这一点时，它会将所有位代码文件读入内存，将它们链接在一起，然后在聚合上运行 LLVM 优化器。由于优化器现在可以查看更大一部分代码，因此它可以跨文件边界进行内联、传播常量、进行更积极的死代码消除等等。虽然许多现代编译器都支持 LTO，但其中大多数（例如 GCC、Open64、英特尔编译器等）都是通过昂贵且缓慢的序列化过程来实现的。在 LLVM 中，LTO 自然地源于系统的设计，并且可以在不同的源语言之间工作（与许多其他编译器不同），因为 IR 确实是源语言中立的。

安装时优化是指将代码生成延迟到比链接时更晚的时间，一直到安装时，如图 11.7所示。安装时是一个非常有趣的时间（在软件装在盒子里、下载、上传到移动设备等情况下），因为这是您了解目标设备的具体信息的时候。例如，在 x86 系列中，芯片和特性种类繁多。通过延迟指令选择、调度和代码生成的其它方面，您可以为应用程序最终运行的特定硬件选择最佳答案。

11.6.2. 优化器的单元测试

编译器非常复杂，质量很重要，因此测试至关重要。例如，在修复导致优化器崩溃的错误后，应添加回归测试以确保它不会再次发生。对此进行测试的传统方法是编写一个.c文件（例如），将其通过编译器运行，并使用测试程序验证编译器不会崩溃。例如，GCC 测试套件使用这种方法。

这种方法的问题在于编译器由许多不同的子系统甚至优化器中的许多不同的 Pass 组成，所有这些都有机会在代码到达有问题的先前错误代码之前改变输入代码的外观。如果前端或较早的优化器发生变化，测试用例很容易无法测试它应该测试的内容。

通过使用 LLVM IR 的文本形式和模块化优化器，LLVM 测试套件具有高度集中的回归测试，可以从磁盘加载 LLVM IR，通过正好一个优化 Pass 运行它，并验证预期行为。除了崩溃之外，更复杂的行为测试希望验证是否确实执行了优化。这是一个简单的测试用例，用于检查常量传播 Pass 是否与 add 指令一起工作

; RUN: opt < %s -constprop -S | FileCheck %s
define i32 @test() {
  %A = add i32 4, 5
  ret i32 %A
  ; CHECK: @test()
  ; CHECK: ret i32 9
}

RUN行指定要执行的命令：在本例中，为opt和FileCheck命令行工具。opt程序是 LLVM Pass 管理器的简单包装器，它链接所有标准 Pass（并且可以动态加载包含其他 Pass 的插件）并将它们通过命令行公开。FileCheck工具验证其标准输入是否与一系列CHECK指令匹配。在本例中，此简单测试验证constpropPass 是否将 4 和 5 的add折叠为 9。

虽然这看起来像一个非常简单的例子，但通过编写 .c 文件很难测试：前端通常在解析时进行常量折叠，因此编写代码使其下游到达常量折叠优化 Pass 非常困难且脆弱。因为我们可以将 LLVM IR 作为文本加载并将其发送到我们感兴趣的特定优化 Pass，然后将结果作为另一个文本文件转储出来，所以直接测试我们想要的内容非常简单，无论是回归测试还是特性测试。

11.6.3. 使用 BugPoint 自动减少测试用例

当在编译器或 LLVM 库的其他客户端中发现错误时，修复它的第一步是获取一个可以重现问题的测试用例。获得测试用例后，最好将其最小化到可以重现问题的最小示例，并将其缩小到 LLVM 中发生问题的部分，例如有问题的优化 Pass。虽然您最终会学会如何做到这一点，但这个过程很乏味、手动且特别痛苦，尤其是在编译器生成不正确的代码但没有崩溃的情况下。

LLVM 的 BugPoint 工具⁷ 利用 LLVM 的 IR 序列化和模块化设计来自动化此过程。例如，给定一个输入的 .ll 或 .bc 文件以及导致优化器崩溃的一系列优化 Pass，BugPoint 会将输入文件缩减为一个小的测试用例，并确定哪个优化器出现了故障。然后，它会输出缩减后的测试用例以及用于重现故障的 opt 命令。它通过使用类似于“增量调试”（delta debugging）的技术来缩减输入和优化器 Pass 列表来实现这一点。由于它了解 LLVM IR 的结构，因此 BugPoint 不会浪费时间生成无效的 IR 输入到优化器，这与标准的“delta”命令行工具不同。

在更复杂的情况下，例如误编译，您可以指定输入、代码生成器信息、传递给可执行文件的命令行以及参考输出。BugPoint 将首先确定问题是由于优化器还是代码生成器导致的，然后会反复将测试用例划分为两部分：一部分发送到“已知良好”的组件，另一部分发送到“已知有故障”的组件。通过迭代地将越来越多的代码从发送到已知有故障的代码生成器的分区中移出，它会缩减测试用例。

BugPoint 是一个非常简单的工具，在 LLVM 的整个生命周期中节省了无数个测试用例缩减的时间。没有其他开源编译器拥有类似功能强大的工具，因为它依赖于明确定义的中间表示。也就是说，BugPoint 并不完美，并且可以从重写中获益。它可以追溯到 2002 年，通常只有当有人遇到一个非常棘手的 bug 需要追踪，而现有工具无法很好地处理时，才会对其进行改进。它随着时间的推移而发展，积累了新的功能（例如 JIT 调试），但没有一致的设计或所有者。