LLVM 概述一：编译器背景及 LLVM 初探

前言

本文较长，部分翻译自《The Architecture of Open Source Applications: LLVM》 。

此文章介绍前半部分，即编译器的背景及 LLVM 初探，后半部分主要说明 LLVM 项目的设计原理和主要优势。

LLVM [1] 是一个包含和开发一组紧密结合的低级工具链组件（例如，汇编器，编译器，调试器等）的大型项目，旨在与 Unix 系统上使用的现有工具兼容。 “LLVM”这个名字曾经是一个缩写词，但现在只是 umbrella 项目的一个子集。LLVM 提供了一些独特的功能，并且以其一些出色的工具而闻名（例如，Clang compiler [2]，一个 C / C ++ / Objective-C 编译器，它具备许多优于 GCC 编译器的优点），也就是说 LLVM 的主要功能除了其他编译​​器已有的功能外，还有它可扩展的内部架构，为解决其他任务提供很好的基础。

从 2000 年 12 月开始，LLVM 被设计为一组具有良好定义接口的可重用库。当时，开源编程语言实现被设计为通常具有单一可执行文件的专用工具。例如，从静态编译器（例如，GCC）重用解析器以进行静态分析或重构是非常困难的。虽然脚本语言通常提供了将运行时和解释器嵌入到更大的应用程序中的方法，但是这个运行时是包含或排除的单个整体代码块，没有办法重复使用碎片，并且很少在跨语言语言实现项目中共享。

除了编译器本身的组成之外，编程语言实现的社区通常是强烈的两极化：一个实现通常提供传统的静态编译器，如 GCC，Free Pascal 和 FreeBASIC，再者就是它提供了一个解释器形式的运行时编译器或即时（JIT）编译器。看到两者同时支持的编译器非常少见，也很难实现多种语言之间的分析和重构。

在过去的十年中，LLVM 已经彻底改变了这种状况。 LLVM 现在被用作实现各种静态和运行时编译语言的通用基础结构（例如，由 GCC，Java，.NET，Python，Ruby，Scheme，Haskell，D 支持的语言系列，以及无数使用较少的编程语言）。它还取代了各种各样的专用编译器，例如 Apple 的 OpenGL 堆栈中的运行时专用引擎和 Adobe After Effects 产品中的图像处理库。最后，LLVM 还被用于创建各种各样的新产品，其中最着名的可能是 OpenCL GPU 编程语言和运行时编译器。

经典编译器设计简介

传统静态编译器（如大多数 C 编译器）最流行的设计是三阶段设计，其主要构成有前端，优化器和后端（图 1）。 前端解析源代码，检查它是否有错误，并构建一个特定于语言的抽象语法树（AST）来表示输入代码。 AST 可选地转换为新的表示以进行优化，优化器和后端在转化后的代码上运行。

优化器负责进行各种各样的转换以尝试提高代码的质量，例如消除冗余计算，优化过程通常或多或少地独立于语言和目标。 然后，后端（也称为代码生成器）将代码映射到目标指令集。 除了生成正确的代码外，它还负责生成代码质量尽可能好的代码。 编译器后端的公共部分包括指令选择，寄存器分配和指令调度。

该三阶段模型同样适用于解释器和 JIT 编译器。 Java 虚拟机（JVM）也是此模型的一个实现，它使用 Java 字节码作为前端和优化器之间的接口。

这种设计的含义

当编译器决定支持多种源语言或目标体系结构时，这种经典设计最重要的优势就体现出来了。 如果编译器在其优化器中使用公共代码表示，则可以为任何可以编译的语言编写前端，并且可以为任何架构的目标机器编写后端，如图 2 所示。

使用上图设计，移植编译器以支持新的源语言（例如，Algol 或 BASIC）只需要实现新的前端，现有的优化器和后端可以重用。如果这些部分没有分开，那么实现新的源语言需要从头开始，因此支持 N 个目标和 M 个源语言需要 N * M 个编译器。
三阶段设计的另一个优点（直接来自可重定向性）是编译器服务于更广泛的程序员集合，而不是仅支持一种源语言和一种目标。对于一个开源项目，这意味着有一个更大的潜在贡献者社区可以从中抽取，这自然会导致编译器存在更多增强和改进的功能。这就是为什么服务于许多社区的开源编译器（如 GCC）倾向于生成比 FreePASCAL 等较窄的编译器更好的优化机器代码。专有编译器的情况并非如此，其质量与项目预算直接相关。例如，英特尔 ICC 编译器因其生成的代码质量而广为人知，即使它服务于狭隘的受众。

三阶段设计的一个主要优势是实现前端所需的技术与优化器和后端所需的技术不同。将这些技术分开使得“前端人员”更容易增强和维护他们的编译器部分。虽然这是一个社会问题，而不是技术问题，但在实践中它很重要，特别是对于希望尽可能服务大众的开源项目。

现有的语言实现

虽然三阶段设计的好处在编译器教科书中引人注目并且有详细记载，但实际上它几乎从未完全实现。查看开源语言实现（当 LLVM 项目启动时），你会发现 Perl，Python，Ruby 和 Java 的实现不共享代码。此外，像 Glasgow Haskell 编译器（GHC）和 FreeBASIC 这样的项目虽然可以重新定位到多个不同的 CPU，但是它们的实现非常特定于它们支持的一种源语言，其中还部署了各种各样的专用编译器技术来实现 JIT 编译器，用于图像处理，正则表达式，图形卡驱动程序以及需要 CPU 密集型工作的其他子域。

这个模型有三个主要的成功案例。第一个是 Java 和.NET 虚拟机。这些系统提供 JIT 编译器，运行时支持和定义良好的字节码格式。这意味着任何可以编译为字节码格式的语言（以及其中的几十种）都可以利用优化器和 JIT 以及运行时的工作量。但是需要注意的是这些实现在运行时灵活性很小：它们都有效地强制 JIT 编译，垃圾收集以及使用非常特定的对象模型。当编译与该模型不匹配的语言（例如 C）时，这会导致性能欠佳。

第二个成功案例可能是最不幸的，也是最常用的重用编译器技术的方法：将输入源转换为 C 代码（或其他语言 [3]）并通过现有的 C 编译器进行编译。这允许重用优化器和代码生成器，提供良好的灵活性，对运行时的控制，并且前端实现者很容易理解，实现和维护。不幸的是，这样做会妨碍异常处理的有效实现，提供糟糕的调试体验，减慢编译速度，并且对于需要保证其他功能的语言（或 C 不支持的其他功能）可能会出现问题。

该模型的第三个最终成功实施是 GCC [4]。 GCC 支持许多前端和后端，并且拥有活跃且广泛的贡献者社区。 GCC 作为一个 C 编译器有着悠久的历史，它支持多个目标，并且支持其他几种语言。随着岁月的流逝，GCC 社区正逐渐发展出更简介的设计。从 GCC 4.4 开始，它为优化器（称为“GIMPLE Tuples”）提供了一个新的表示形式，它比前面更接近于与前端表示分离。此外，它的 Fortran 和 Ada 前端使用干净的 AST。

虽然非常成功，但这三个阶段的实现对它们的用途有很大限制，因为它们被设计为单一的应用程序。作为一个示例，将 GCC 嵌入到其他应用程序中，将 GCC 用作运行时/ JIT 编译器，或者在不拉入大部分编译器的情况下提取和重用 GCC 片段是不现实的。想要使用 GCC 的 C ++ 前端进行文档生成，代码索引，重构和静态分析工具的人不得不将 GCC 用作以 XML 形式发布有趣信息的单一应用程序，或编写插件以将外部代码注入 GCC 流程。

GCC 片段不能作为库重用的原因有很多，包括全局变量的泛滥使用，设计不良的数据结构，庞大的代码库以及使用宏来阻止代码库被编译以支持更多的超过的前端/目标机器代码。但是，最难解决的问题是其早期设计和时代所固有的架构问题。具体来说，GCC 会遇到分层问题和漏洞抽象：后端走前端 AST 生成调试信息，前端生成后端数据结构，整个编译器依赖于命令行界面设置的全局数据结构。

LLVM 的中间代码表示：LLVM IR

有了历史背景和背景，让我们深入研究 LLVM：其设计中最重要的方面是 LLVM 中间表示（IR），它是用于表示编译器中代码的形式。 LLVM IR 旨在为编译器的优化器部分提供基础。 它的设计考虑了许多具体目标，包括支持轻量级运行时优化，跨功能/过程间优化，整个程序分析和积极的重组转换等。但最重要的是，它本身定义为具有明确定义的语义的第一类语言。 为了具体说明，以下是一个简单的 .ll 文件示例：

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
}

此 LLVM IR 对应于如下 C 代码，它提供了两种不同的方法来表示整数相加：

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);
}

从这个例子中可以看出，LLVM IR 是一种类似 RISC 的低级虚拟指令集。与真正的 RISC 指令集一样，它支持简单指令的线性序列，如加，减，比较和分支。这些指令有三种地址形式，这意味着它们需要一些输入并在不同的寄存器中产生结果
[5] LLVM IR 支持标签，通常看起来像一种奇怪的汇编语言形式。

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

除了作为一种语言实现之外，LLVM IR 实际上以三种同构形式定义：一种是在内存中的编译中间语言；一种是硬盘上存储的二进制中间语言（以.bc 结尾），最后一种是可读的中间格式（以.ll 结尾）。这三种中间格式是完全等价的。 LLVM 项目还提供了将磁盘格式从文本转换为二进制的工具：llvm-as 将文本 .ll 文件组装成包含 bitcode goop 的 .bc 文件，llvm-dis 将 .bc 文件转换为 .ll 文件。

编译器的中间表示很有意思，因为它可以是编译器优化器的“完美世界”：与编译器的前端和后端不同，优化器不受特定源语言或特定目标机器的约束。另一方面，它必须具有如下优点：必须被设计成易于前端生成并且足够易于后端使用优化功能。

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

对于这些类型的“ peephole”转换，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 ++ 实现的，它的模式匹配功能并不为人所熟知（与 Objective Caml 等功能语言相比），但它提供了一个非常通用的模板系统，允许我们实现类似的功能。match 函数和 m_ 函数允许我们对 LLVM IR 代码执行声明性模式匹配操作。例如，如果乘法的左侧与 Op1 相同，则谓词仅匹配。

总之，这三种情况都是模式匹配的，如果可以，函数返回替换，如果不可能替换，则返回空指针。此函数的调用者（SimplifyInstruction）是一个调度程序，它对指令操作码进行切换，调度到每操作码辅助函数。它是从各种优化中调用的。一个简单的驱动程序如下所示：

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

这段代码简单地循环遍历块中的每条指令，检查它们是否有任何简化。 如果是这样（因为 SimplifyInstruction 返回非 null），它使用 replaceAllUsesWith 方法可简化更新代码中任何内容的操作过程。

下半部分：LLVM 概述二：LLVM 设计精髓及其优势

Footnotes

1. http://llvm.org
2. http://clang.llvm.org
3. http://en.wikipedia.org/wiki/List_of_JVM_languages
4. A backronym that now stands for "GNU Compiler Collection".
5. This is in contrast to a two-address instruction set, like X86, which destructively updates an input register, or one-address machines which take one explicit operand and operate on an accumulator or the top of the stack on a stack machine.