LLVM系统体系架构介绍

本文讨论形成LLVM的某些设计决定,一个承载及开发了一套严密的低级工具组件(比如,汇编器,编译器,调试器等)的综合项目,它被设计为与通常用在Unix系统上现存的工具兼容。名字“LLVM”过去是一个首字母缩略词,但现在只是这个综合项目的一个标签。虽然LLVM提供了某些唯一的功能,并因某些很好的工具而闻名(比如Clang编译器,一个在GCC编译器上提供了若干好处的C/C++/Objective-C编译器),把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编译器)最流行的设计是3阶段的设计,其中主要组件是前端,优化器及后端(如下图)。前端解析源代码,检查错误,并构建一个特定于语言的抽象语法树(AST)来代表输入的代码。可选地AST被转换到一个新的用于优化的表示,优化器及后端可以运行这个代码。

优化器负责进行各种转换尝试改进代码的运行时间,比如重复计算消除,通常或多或少与语言及目标无关。然后后端(也被称为代码产生器)把代码映射入目标指令集。除了制作正确的代码,它负责产生利用所支持架构不寻常功能的好代码。一个编译器后端的通用部分包括指令选择,寄存器分配,及指令调度。

这个模型同样适用于解释器及JIT编译器。Java性能机(JVM)也是这个模型的一个实现,它使用Java字节码作为前端及优化器间的接口。

这种设计的启示

当一个编译器决定支持多个源语言或目标架构时,这种经典设计最重要的收益出现了。如果编译器在其优化器中使用一个通用的代码表示,那么可以任何可以编译到这个表示的语言编写一个前端,且可以为任何可以从这个表示编译得到的目标编写一个后端,如下图所示。

使用这个设计,移植编译器来支持一个新的源语言(比如Algol或BASIC)要求实现一个新的前端,但现有的优化器及后端可以重用。如果这些部分不是分开的,实现一个新源语言将要求从头开始,因此支持N个目标及M个源语言将需要N*M种编译器。

这个3阶段设计(它是可重定目标性直接的结果)的另一个好处是,相比如果仅支持一种源语言、一个目标,编译器服务更广大的程序员。对于一个开源项目,这意味着从中会得到一个更大的潜在贡献者社区,自然导致对编译器更多的增强与改进。这是为什么服务许多社区的开源编译器(像GCC)比应用范围更窄的编译器,像FreePASCAL,往往会产生更好的优化的机器码的原因。这不是私有编译器的情形,其质量与项目经费直接相关。例如,Intel ICC编译器以产生代码的质量而著称,虽然它服务于一个小众群体。

3阶段设计最好一个主要收益是,要求实现一个前端的技能与实现优化器与后端要求的技能不同。分开这些使得一个“前端家伙”更容易增强及维护编译器他们的部分。虽然这是一个社会问题,不是一个技术问题,在实践中它关系重大,特别对于希望减少阻碍得到尽可能多贡献的开源项目。

现存语言的实现

虽然3阶段设计的好处引人注目,而且在编译器教科书中有充分的记载,在实践中它几乎没有被完整实现。看看开源语言实现(回到LLVM开始时),你会发现Perl,Python,Ruby及Java的实现没有共享代码。另外,像Glasgow Haskell编译器(GHC)及FreeBASIC的项目是可重定目标到不同CPU,但它们的实现是非常特定于它们支持的一个源语言。还有各种各样特殊用途的编译技术部署来为图形处理,正则表达式,显卡驱动及其它要求密集CPU工作的子领域实现JIT编译器。

这就是说,对于这个模型有3个主要的成功的故事,第一个是Java与.NET虚拟机。这些系统提供了一个JIT编译器,运行时支持,及一个定义得非常好的字节码格式。这意味着可以编译到这个字节码格式(它们有数十个)的任何语言可以利用投入优化器与JIT以及运行时努力的成果。权衡是这些实现在运行时选择方面提供了极少的灵活性:它们都有效地推行JIT编译,垃圾收集,及一个非常特别的目标模型的使用。当编译不是严格匹配这个模型的语言,像C时,这导致次优的性能(比如使用LLJVM项目)。

第二个成功的故事可能是最不幸的,但也是重用编译器技术流行的方式:把输入源代码翻译为C代码(或某些其它语言),并把它送入现存的C编译器。这允许重用优化器及代码生成器,给出好的灵活性,运行时控制,并且确实容易为前端实现者理解、实现及维护。不幸的是,这样做阻止了异常处理的高效实现,提供了一个差劲的调试体验,拖慢了编译,对于要求确保尾调用(tail call)(或其它C不支持的特性)的语言会问题重重。

这个模型最后一个成功的实现是GCC。GCC支持许多前端与后端,并有一个活跃和广泛的贡献者社区。GCC作为一个支持多个目标C编译器有长的历史,对固定在它身上其它几个语言有业余支持。随着岁月的流逝,GCC社区缓慢地演进出另一个更清晰的设计。自GCC 4.4起,对优化器它有一个新的表示(称为“GIMPLE Tuples”),比之前更进一步从前端的表示分开。同样,其Fortran与Ada前端使用一个清晰的AST。

虽然非常成功,这3个做法在用途上有很强的局限,因为它们被设计为单一应用程序。作为一个例子,把GCC嵌入到另一个应用,把GCC用作运行时、JIT编译器,或提取、重用GCC的代码片段而不带出该编译器的大部分,没有切实的可能。希望把GCC前端用于文前端用于文档生成,代码索引、重构,以及静态分析工具的人们不得不把GCC用作一个把感兴趣信息输出为XML的单一应用程序,或者编写插件向GCC过程注入务必代码。

为什么GCC的代码片段不能作为库重用,有多个原因,包括全局变量猖獗的使用,软弱推行的不变量,设计不佳的数据结构,庞大缺少规划的代码库,防止代码库被一次编译来支持多个前端/目标对的宏的使用。不过最难修正的问题是源自其早期设计和阶段固有的架构问题。特别地,GCC饱受分层问题与抽象遗漏之苦:后端遍历前端AST来生成调试信息,前端产生后端数据结构,而整个编译器依赖于由命令行接口设置的全局数据结构。

LLVM的代码表示:LLVM IR

带着偏离主题的历史背景和上下文,让我们深入LLVM:其设计最重要的方面是LLVM中间表示(IR),它是LLVM用于在编译器中表示代码的形式。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指令集,它支持简单指令的线性序列,像add,subtract,compare与branch。这些指令是3地址形式,这意味着它们接受几个输入并在一个不同的寄存器中产生一个结果。LLVM IR支持标号,并且通常看起来像汇编语言的一个怪异形式。

不像大多数的RISC指令集,LLVM是使用一个简单类型系统强类型化的(比如,i32是一个32位整数,i32**是一个指向32位整数指针)并抽象掉了机器的某些细节。例如,调用约定通过callret指令及明确的实参来抽象。与机器码的另一个重要差异是,LLVM IR不使用具名寄存器的一个固定集合,它使用带有一个%字符的临时寄存器的一个无限集。

除了实现为一个语言,LLVM IR实际上被定义为3个同构的形式:上面的文本格式,一个内存中由优化自己来检查与修改的数据结构,以及一个高效、紧密的硬盘上二进制“比特码”格式。LLVM项目还提供了工具把硬盘上格式从文本转化为二进制:llvm-as把.ll文本文件汇编成一个包含比特码粘糊的.bc文件,而llvm-dis把一个.bc文件变成一个.ll文件。

一个编译器的中间表示是有趣的,因为对于编译器优化器它可以是一个“完美世界”:不像编译器的前端与后端,优化器不受一个特定源语言或一个特定目标机器的限制。另一方面,它必须服务好两者:它必须设计为容易为一个前端产生,同时有足够的表达能力以允许对真实目标进行重要的优化。

编写一个LLVMIR优化

为了给出优化如何工作的某些直觉,浏览一些例子是有用的。有许多不同类型的编译器优化,因此很难提供一个如何解决一个任意问题的处方。也就是说,大多数优化遵循一个简单的3部分结构:

  • 查找一个要转换的模式。
  • 对匹配的实例,验证这个转换是安全/正确。
  • 进行转换,更新代码。

最琐碎的优化是匹配算术标识符的模式,比如:对于任意整数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++实现,其模式匹配能力不为人熟知(对比函数化语言,像Objective Caml),但它提供了一个非常通用的模板系统,允许我们实现类似的东西。match函数与m_函数允许我们在LLVMIR代码上执行陈述性的模式匹配操作。例如,m_Specific谓语仅在乘法的左手侧与Op1相同时匹配。

总之,这3个情形都是模式匹配,函数返回替代如果可以,否则返回一个空指针。这个函数的调用者(SimplifyInstruction)是一个分发者,它在指令opcode执行一个切换,分发到每个opcode的辅助函数。它从各个优化调用。一个简单的驱动看起来像这样:

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

这个代码只是遍历一个块中的每条指令,检查是否有可以简化的。如果是(因为SimplifyInstruction返回非空),它使用replaceAllUsesWith方法把使用可简化操作的代码更新为更简单形式。

3阶段设计的LLVM实现

在一个基于LLVM的编译器中,一个前端负责对输入代码解析,验证及诊断错误,然后把解析的代码转换到LLVM IR(通常,但不总是,通过构建一棵AST,然后把这个AST转换为LLVM IR)。这个IR可选地通过一系列改进代码的分析及优化遍,然后发送到一个代码生成器来产生本地机器码,如图所示。这是3阶段设计的一个非常直接的实现,但这个简单的描述掩盖了LLVM架构源自LLVM IR的某些能力与灵活性。

LLVM IR是一个完整的代码表示

特别的,LLVM IR既是具体定义的,又仅是到优化器的接口。这个性质意味着为LLVM编写一个前端你需要知道的一切是,LLVM IR是什么,它如何工作,及它期望的不变量。因为LLVM IR有一个第一流的文本形式,构建一个把LLVM IR输出为文本的前端是可能的,也是合理的,然后使用Unix管道按你意愿把它送过优化器序列及代码生成器。

可能是令人惊奇的,但对LLVM这实际上是一个相当新奇的属性,并且是它在范围广泛的不同的应用中成功的一个主要原因。即使广泛成功的并且相对良好构建的GCC编译器也没有这个属性:其GIMPLE中级表示不是一个自包含的表示。一个简单例子,当GCC代码生成器输出DWARF调试信息时,它回顾并遍历源级别的“树”形式。GIMPLE本身对代码中的操作使用一个“元组(tuple)”表示,但(至少到GCC 4.5)仍然把操作数表示为回到源级别树形式的引用。

这个的启示是,前端的作者需要知道并制作GCC的树数据结构连同GIMPLE来编写一个GCC前端。GCC后端有类似的问题,因此它们也需要零星知道RTL后端如何工作。最后,GCC没有办法倾卸“表示我代码一切事物”,或一个方法以文本格式读入及编写GIMPLE(及构成代码表示的相关数据结构)。结果是,实验GCC相对困难些,因此它有相对少的前端。

LLVM是一个库的集合

除了LLVM IR设计,LLVM下一个最重要的方面是,它被设计为一组库,而不是作为一个整体命令行编译器,像GCC,或一个不透明的虚拟机,像JVM或.NET虚拟机。LLVM是一个基础设施,一个可以应用在特定问题(像构建一个C编译器,或在一个特殊效果管道中的一个优化器)的,有用的编译器技术。虽然是其最强大的特性之一,但也是最少为人了解的设计点。

让我们看优化器的设计作为一个例子:它读入LLVM IR,稍微处理一下,然后给出有望将执行得更快一些的LLVM。在LLVM中(就像在其它许多编译器中),优化器被组织为一个不同优化遍组成的管道,每个遍运行在输入上,并有机会做一些事。这些遍的常见例子是内联器(它把一个函数体替换入调用点),表达式重组,循环不变量移动等。依赖优化的级别,不同的遍被运行:例如在-O0(没有优化)Clang编译器不运行遍,在-O3它在优化器中运行67个遍的系列(自LLVM2.8)。

每个LLVM遍被写作一个从类Pass(间接)派生的C++ 类。大多数遍被写在一个.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编译能力,它不意味着每个客户要使用它。

可重定目标的LLVM代码生成器的设计

LLVM代码生成器负责把LLVM IR转换为目标特定的机器代码。一方面,为任何给定的目标产生尽可能好的机器码是代码生成器的任务。理想地,每个代码生成器应该完全为目标定制,但另一方面,每个目标的代码生成器需要解决非常类似的问题。例如,每个目标需要向寄存器分配值,虽然每个目标有不同的寄存器文件,使用的算法应尽可能共享。

类似于优化器中的做法,LLVM的代码生成器把代码生成问题分解为独立的遍——指令选择,寄存器分配,调度,代码布局优化,及汇编发布——并提供许多默认运行的内置遍。向目标作者给出在默认遍中选择,改写默认设置,及按要求实现完全定制目标特定遍的机会。例如,x86后端使用一个寄存器减压(register-pressure-reducing)调度器,因为它有非常少的寄存器,但PowerPC后端使用一个延迟优化调度器,因为它有许多寄存器。x86后端使用一个定制的遍来处理x87浮点栈,而ARM后端使用一个定制遍在需要的函数里放置常量池。这个灵活性允许目标作者产生优良的代码,而不需要为目标从头编写整个代码生成器。

LLVM目标描述文件

“混合及匹配”的做法允许目标作者选择对他们的架构什么是合理的,并在不同的目标上允许大量的代码重用。这带来另一个挑战:每个共享的组件需要能够以一个通用的方式推理目标特定的属性。例如,一个共享缓冲器分配器需要知道每个目标的寄存器文件,以及在指令及它们的寄存器操作数之间的限制。LLVM对此解决方案是,对于每个目标以一个声明性的领域特定语言提供一个由tblgen工具管理的目标描述(一组.td文件)。对x86目标(简化的)构建过程显示在下图中。

.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++代码,并实现任何它们可能需要的目标特定的遍(像X86FloatingPoint.cpp,它处理x87浮点栈)。随着LLVM持续增加新目标,增加能以.td文件表示的目标变得越来越重要,并且我们持续增加.td文件对此处理的表现力。一个大的好处是,随着时间推移编写LLVM里的目标变得越来越容易。

由模块化设计提供的有趣的能力

除了作为一个总体上优雅的设计,模块化为LLVM客户提供了有几个有趣能力的库。这些能力出自,LLVM提供功能,但让客户决定如何使用它的大多数策略,这个事实。

选择何时与何地运行每个遍

就像之前提及的,LLVM IR可以高效地(反)序列化至/自一个称为LLVM比特码的二进制格式。因为LLVM IR是自包含的,并且序列化是一个无损过程,我们可以进行部分编译,把我们的进展保存入硬盘,然后在将来某个时候继续。这个特性提供了若干有趣的能力,包括对链接时及安装时优化的支持,两者从“编译时”延迟代码生成。

链接时优化(LTO)解决这样的问题,编译器传统上一次只能看到一个翻译单元(比如,一个带有其头文件的.c文件),因此不能跨越文件边界进行优化(像内联)。LLVM编译器,像Clang,使用-flto或-O4命令行选项支持这。这个选项指示编译器向.o文件发出LLVM比特码,而不是写出一个本机目标文件,并把代码生成延迟到链接时刻,如下图所示。

细节依赖于你所在的操作系统而不同,但最重要的是,链接器检测到在.o文件里是LLVM比特码,而不是本机目标文件。当它看到这个时,它把所有的比特码文件读入内存,把它们链接起来,然后在这个聚合体上运行LLVM优化器。因为优化器现在看到代码大得多的部分,它可以跨文件边界进行内联、常量传播,更激进的死代码消除等等虽然许多现代编译器支持LTO,它们大多数(比如GCC,Open64,Intel编译器等)通过一个昂贵且缓慢的序列化过程来进行。在LLVM中,LTO自然地从系统设计中脱离,并跨越不同的源语言工作(不像许多其它编译器),因为IR是真正源语言中性的。

安装时优化是把代码生成甚至延迟到链接时刻以后,一直到安装时刻的想法,如图11.7所示。安装时刻是一个非常有趣的时间(在软件以在一个盒子里、下载、上传到一个移动设备等方式推出的情形中),因为这是你发现你目标设备细节的时刻。以x86家族为例,有各种各样的芯片和特性。通过延迟指令选择、调度,以及代码生成的其它方面,对于一个应用最终运行的特定硬件,你可以挑选最好的答案。

安装时优化

优化器的单元测试

编译器是非常复杂的,而且质量很重要,因此测试是关键的。例如,在修正了一个在一个优化器中导致崩溃的bug后,应该添加一个回归测试来确保它不会再发生。测试这的传统做法是编写一个贯穿这个编译器,并有一个测试工具验证编译器不会崩溃的.c文件(例如)。比如,这是GCC测试集使用的做法。

这个做法的问题是,编译器包含许多不同的子系统,在优化器中甚至有许多不同的遍,所有这一切在接触到讨论中的、之前就有问题的代码时,都有机会改变输入代码的外观。如果在前端或一个更早的优化器中发生了某些改变,一个测试用例很容易测试不到它被期望测试的内容。

通过使用文本形式的LLVM IR和模块化的优化器,LLVM测试集有高度集中的、可从硬盘载入LLVM IR的回归测试,运行它通过只一个优化遍,并验证期望的行为。除了崩溃,一个更复杂的行为测试想要验证一个优化实际发生了。这里是一个简单的测试用例,检查常量传播遍是否对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遍管理器的一个简单封装,它链入所有标准遍(并可以动态载入包含其它遍的插件),并把它们公开给命令行。FileCheck工具验证其标准输入匹配一系列CHECK指示。在这个情形里,这个简单测试是验证constprop遍把4与5的add折叠为9。

虽然这可能看上去像一个极其微不足道的例子,这是非常难通过编写.c文件来测试的:前端通常在解析时进行常量折叠,因此编写代码使它下游到一个常量折叠优化遍是非常困难且脆弱的。因为我们可以把LLVM IR作为文本载入,并把它送过特定的、我们感兴趣的优化遍,然后把结果生成为另一个文本文件,对测试我们真正想要的,不管回归还是功能测试,这确实简单明了。

使用BugPoint减小自动化测试用例

当在一个编译器或LLVM库的其它客户中找到一个bug时,修正它的第一步是得到重现这个问题的一个测试用例。一旦你有了一个测试用例,最好把它最小化为重现这个问题的最小的例子,并把它缩小为发生这个问题的LLVM部分,比如失败的优化遍。虽然你最终会学会如何做,这个过程是乏味的,并且对于编译器产生不正确代码但不崩溃的情形特别痛苦的体力活。

LLVM BugPoint工具使用IR序列化以及LLVM的模块化设计来自动化这个过程。例如,给定一个输入的.ll或.bc文件,连同一组导致一个优化器崩溃的优化遍,BugPoint把输入减小为一个小的测试用例,并确定哪个优化器出问题。然后它输出减小的测试用例以及用于重新这个失败的opt命令。它通过使用类似于“增量调试(delta debugging)”的技术,减小输入及优化遍列表来找到。因为它知道LLVM IR的结构,BugPoint不会浪费时间产生无效的IR输入优化器,不像标准的“增量”命令行工具。

在一个误编译的更复杂的情形里,你可以指定输入,代码生成器信息,传递给可执行文件的命令行,及输出的一个引用。BugPoint将首先确定这个问题是否归咎于一个优化器或代码生成器,然后将反复把测试用例划分为两部分:一部分送入“已知好的”组件,一部分送入“已知有问题”的组件。通过反复地把越来越多的代码移出送入已知有问题的代码生成器的部分,它减小了测试用例。

BugPoint是一个非常简单的工具,并且在LLVM的生命期中节省了无数减小测试用例的时间。没有其它开源编译器有一个类似的强大工具,因为它依赖于一个良好定义的中间表示。也就是说,BugPoint不完美,并将从一次重写受益。它的时间追溯到2002年,通常仅当有人要追踪一个真正棘手的,现存工具不能很好处理的bug时,才会改进。它随着时间推移变大,添加新的功能(比如JIT调试)而没有一个一致的设计或拥有者。

回顾及未来的方向

LLVM的模块化不是一开始设计来直接实现任何这里描述的目标。它是一个自我防卫的机制:显然在第一次尝试中我们不会每一件事都对。例如,模块化遍管道存在,使得隔离遍更容易,因此在被更好的实现替换后,它们可以被丢弃。

LLVM余下灵活的另一个主要方面(且与库客户端一起的一个有争议的话题)是,我们愿意重新考虑之前的决定,并对API进行广泛的修改,而不需要担心前向兼容性。例如,对LLVM IR本身侵略性的改变要求更新所有优化遍,并导致C++ API相当程度的扰动。这样做已经几次了,虽然它对客户造成了痛苦,为了维护快速的前进,这样做是对的。为了使外部的客户更好过些(以及提供对其它语言的绑定),我们对许多流行的API提供了C封装(目的是非常稳定),并且新版本的LLVM计划继续支持旧的.ll与.bc文件。

展望未来,我们愿意继续使LLVM更加模块化,更容易提取子集。例如,代码生成器仍然太庞大:当前不可能基于功能子集化LLVM。比如,如果你想使用JIT,但不需要内联汇编,异常处理,或调试信息生成,构建没有链入这些功能支持的代码生成器应该是可能的。我们还持续改进由优化器及代码生成器产生的代码质量,添加IR功能以更好地支持新语言及目标构造,以及为在LLVM中执行高级的语言特定优化添加更好的支持。

LLVM项目以多种方式持续成长与改进。看到LLVM以若干种不同的方式用在其它项目中,以及它如何不断出现在令人惊异的,其设计者从未想到的新环境里,真是令人兴奋。新的LLDB调试器是这样的一个好的例子:它使用来自Clang的C/C++/Objective-C解析器来解析表达式,使用LLVM JIT把这些翻译为目标代码,使用LLVM反汇编器。以及使用LLVM目标来处理其他事情之间的调用约定。能够重用现存的代码允许开发调试器的人专注于编写调试器逻辑。而不是重新实现另一个(略微正确的)C++解析器。

尽管到目前为止的成功,仍有很多有待完成,连同永远存在的,LLVM将随着年龄越来越僵化的风险。虽然对这个问题没有神奇的答案,我希望持续公开到新的问题领域,重新评估之前决定然后重新设计并扔掉代码的意愿,将有所帮助。毕竟,我们的目标并不完美。随着时间推移它会越来越好。

来源:www.aosabook.org/en/llvm.html

作者:Chris Lattner