【LLVM】LLVM架构介绍

LLVM架构介绍

本文主要介绍了LLVM的架构设计。LLVM命名源自于底层虚拟机(Low Level Virtual Machine)的缩写。它并不是针对于某一种语言的编译器工具，它是一种提供支持与保护的一系列底层的工具链程序集合。让LLVM与其它编译器不同的是它的内部架构。下面就介绍LLVM的内部架构。

从2000年的11月开始，LLVM被设计为一系列拥有清晰接口并且可重用的库，在那时候，开源的编程语言的实现被用作特别目的，而且经常是进行庞大的独立执行。这样的话，复用静态库（例如GCC）做静态分析或者代码重构时就会变得特别困难。而且脚本语言经常是通过动态解释嵌入到即将运行的大型应用程序中。这种动态运行时使得代码臃肿。复用其中的某一模块几乎不可能，而且丝毫没有共享精神。

抛开编译器本身实现不谈，各个流行语言之间实现方式的交流也是极端分化的：某一种语言实现通常要么采用传统的编译器（如GCC、Free Pascal...），要么采用运行时的编译方式。同时提供两种编译方式的可不常见。

LLVM从本质上改变了这一切，LLVM被用来作为同时支持静态和动态运行时编译器的基础框架。它同时也代替了各种实现特殊目的的编译器，例如Apple OpenGL stack 的运行时特殊引擎和Adobe After Effects 的图片处理库。目前，LLVM已经被用于创造各种新的产品。

传统的编译器设计

传统的静态编译器（例如大多数C编译器）采用三段式设计：前端，优化组件和后端。前端组件解析程序源代码，检查语法错误，生成一个基于语言特性的AST（Abstract Syntax Tree）来表示输入代码。AST将代码转换为具有新的表达语法的代码提供给优化器，然后优化器和后端程序执行转换后的代码翻译成机器能识别的语言。

三段式

优化器作用是采用各种方式使得代码运行得更快，例如删除不必要的计算。后端（又叫代码生成器）将代码与任务指令一一对应起来。除了生成正确的代码以外，也要与机器设备的特性结合以保证生成代码的质量。通常编译器后端包括指令选择，寄存器分配和指令安排表等功能。

JVM也是采用这种模式实现的，它是使用Java字节码作为前端与优化器的接口。

传统编译器模式的实现

这种模式的优点在于当编译器决定支持多种语言或者多种目标设备的时候，如果编译器在优化器这里采用普通的代码表示时，前端可以使用任意的语言来进行编译，后端也可以使用任意的目标设备来汇编。如下图：

实现

使用这种设计，使编译器支持一种新的语言需要实现一个新的前端，但是优化器以及后端都是可以复用，不用改变的。那么实现支持新的语言需要从最初的前端设计开始，支持N种设备和M种源代码语言一共需要N*M种编译方式。

这种三段式设计的另一优点是编译器提供了一个非常宽泛的语法集，即对于开源编译器项目来说，这意味着会有更多的人参与进来，自然而然地就提升了项目的质量。这也是为什么一些开源的编译器通常更为流行。

最后一个优点是实现一个编译器前端相对于优化器与后端来说是完全不同的。将他们分离开来对于专注于设计前端来提升编译器的多用性（支持多种语言）来说相对容易点。它降低了开源编译器项目的参与要求。

LLVM's Code Representation：LLVM IR

LLVM中最重要的设计模块：LLVM IR（LLVM Intermediate Representation），它是在编译器中用来表示代码的一种形式。它被设计用来在编译器的优化模块中，作为主导中间层的分析与转换。它是经过特殊设计的，包括支持轻量级的运行时优化、过程函数的优化，整个程序的分析和代码完全重构和翻译等等。其中最重要的是，它定义了清晰的语义。参考如下的.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
}

上述这段代码对应的是下面这段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指令集一样，它提供了一系列线性的简单指令：加、减、比较以及分支结构。这些指令在三种地址形式中：即通过对一些输入的计算，得出的结果存在不同的寄存器中。LLVM IR提供了标签支持，它通常看起来像是一种奇怪的汇编语言一样。

和大多数RISC指令集不同的是，LLVM使用一种简单的类型系统来标记强类型（i32表示32位整型，i32**表示指向32位整型的指针），而一些机器层面的细节都被抽象出去了。例如函数调用使用call作标记，而返回使用ret标记。此外还有个不同是LLVM IR不直接像汇编语言那样直接使用寄存器，它使用无限的临时存储单元，使用%符号来标记这些临时存储单元。

不仅仅是语言层面的实现那么简单，LLVM IR实际上定义了定义了三种同型的形式：在代码格式的检查之上——内存中数据结构检查、自身最优化修正以及一种高效率密集型的二进制代码格式——bitcode。当然LLVM也提供了将代码文本转为二进制文件格式的工具：llvm-as，它将.ll文件转为.bc格式文件，llvm-dis将.bc文件转为.ll文件。

LLVM IR对于优化器来说非常友好，正是由于它的存在，优化器可以不受某一种特定语言或者特定设备的约束。因为使用LLVM 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
⋮    ⋮    ⋮

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分别绑定到操作式的左右两边，

LLVM的三段式实现

在基于LLVM的编译器中，前端的作用是解析、验证和诊断代码错误，将解析后的代码翻译为LLVM IR（通常是这么做，通过生成AST然后将AST转为LLVM IR）。翻译后的IR代码经过一系列的优化过程与分析后，代码得到改善，并将其送到代码生成器去产生原生的机器码。过程如下图所示。这是非常直观的三段式设计的实现过程，但是这简单的描述当然是省去了一些细节的实现。

LLVM的实现

LLVM IR就是完全的代码“代理”

LLVM IR可以说是提供给优化器的接口。这么说的意思是你只需要了解为LLVM编译器写前端就是搞清楚LLVM IR是什么，它是怎么工作的。既然LLVM IR拥有生成特定的代码文本形式，那么我们设计的编译器前端的功能就是产生LLVM IR文本代码，将其发送给优化器和代码生成器。那么和传统的三段式不同的是后端生成机器代码的时候不需要知道前端的AST的格式是什么，省去了一些工作。

LLVM是一些库的集合

介绍完LLVM IR之后，LLVM的另一个重要方面是它是由一系列库所组件成的。相比于庞大的命令行编译器GCC、晦涩的虚拟机JVM、.NET等，LLVM是一个基础框架，它是一些可用的编译技术的集合并且可以忍受特殊的问题。

让我们从优化器的设计开始：优化器从读入LLVM IR代码开始，经过优化后产生的LLVM IR 可能会运行的快一点，在LLVM中，优化器有很多种不同的优化通道(optimization passes)，根据输入的不同，我们可以针对性地进行一些改变(do sth here)，

每一个pass都被写成了一个C++类，它是由Pass类继承来的。大多数的pass都是写在一个单独的类文件(.cpp)中的。Pass类的子类被定义在一个匿名空间中（保证完全私有），为了使得pass可用，文件外的代码必须可以访问到此pass类文件，因此单独把创建pass的函数暴露出来就很有必要了。这里是一个小型的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的优化器提供了非常多不同的pass，每种pass的写法都是类似的。这些pass文件都被编译成为.o文件，接着会被链接打包成为一系列库文件(.a文件)，这些库文件提供了很多的分析与翻译的功能。pass之间都尽可能地宽松地结合：相互之间尽可能保持独立，或者时明确地定义pass之间的依赖关系。如果给了许多的pass文件，那么pass管理器就可以通过pass之间的文件依赖关系正确地执行这些pass。

LLVM优化器允许挑选指定的pass文件并将它们链接到一起执行，以此来完成指定的一些功能。当然在优化时，也只会由指定的pass完成优化，而不是整个优化器。如下图所示：

pass优化

这种基于库的实现方式允许LLVM提供大量的功能，如果你只是需要LLVM中的一些简单的功能，那么只需要指定运行的pass文件而不需要管所有的优化pass。

LLVM代码生成器的设计

代码生成器的任务是将LLVM IR翻译为机器可识别的代码。理论上说，每个代码生成器都要针对不同的任务定制不同的机器代码，但是另一方面，对于每个任务，代码生成器所做的工作又有很多类似的，例如将变量分配到寄存器。

和优化器采用的方式类似，LLVM的代码生成器将代码生成的问题分离成独立的pass，例如指令选择，寄存器分配，建表，代码布局优化以及提供默认的内建pass等等。通过选用内建的默认pass，重写这些默认pass实现针对特定设备的自定制pass。例如x86后端使用寄存器调度是因为机器上的寄存器较少，而PowerPC后端使用潜在优化寄存器调度是因为机器上有很多寄存器。因此对于这两种机器，必须有不同的pass代码生成器去解决。这种灵活的方式允许根据机器的不同采用不同的解决办法而不是完全重写默认的解决方式。

LLVM 任务描述文件

这种方式带来了新的问题:每个共享的pass组件应该有能力去识别对应的任务所需要的文件以及相应指令之间的约束关系。LLVM的做法是对于每一个任务，都有对应的任务描述文件(.ed文件)，x86的生成过程如下：

简化版的描述

不同的子系统提供了不同的.td文件，例如x86后端定义了一个寄存器类，它记录了所有的32位寄存器，名称为GR32：

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

这个定义列出了此类中的寄存器可以保存32位的整型数。

未完待续...