LLVM编译器框架介绍

作者 Lucyyang 日期 2020-03-13
CS
LLVM编译器框架介绍

本文摘自LLVM项目的创始者Chris Lattner的介绍:The Architecture of Open Source Applications: LLVM

什么是LLVM?

LLVM是一种编译器基础设施,以C++写成,包含一系列模块化的编译器组件和工具链,用来开发编译器前端和后端。它与其他编译器的主要不同在于内部采用的架构。

LLVM产生的背景

在2000年前,开源的语言执行工具工呈现两级分化:要么是传统的静态编译器,例如GCC、Free Pascal、FreeBASIC,是一种较为庞大的执行工具,很难重用这些静态编译器的的语法分析器(parser)作为静态分析或者重构;另外一种则以解释器或者Just-In-Time (JIT) compiler的方式提供动态编译。但很少有语言实现工具可以同时支持这两种,即使有也很少开源。

LLVM的提出就是为了改变这样的情况,LLVM现在被广泛用作一种常见的基础架构用来实现大量的不同语言的动态或者静态编译器(例如GCC, Java, .NET, python, Ruby, Scheme, Haskell等等)。此外,LLVM还取代了大量的用于特殊目的的编译器,例如Apple的OpenGL Stack中的动态专门化引擎以及Adobe产品中的图像处理库。LLVM还被用于创建大量的新产品,最著名的是用于OpenCL GPU编程语言和runtime。

传统经典编译器的简单介绍

最常见的对传统静态语言编译器(例如大部分的C编译器)一般采用的是三段设计:前端、优化器、后段,参考下图。前端用于解析用户输入的源码,检查错误,建立特定语言的抽象语法树(Abstract Syntax Tree, AST)用于表示输入代码。AST可以选择性的转换为用于优化的新代码,优化器和后段会作用于这个代码。 三段设计

优化器一般会做大量的转换用于提高代码的实时性,例如减少不必要的计算,它多多少少是独立于语言和生成目标饿。后端(也被称为代码生成器,code generator)将代码映射到目标架构的指令集上。后端需要尽可能生成处能够利用目标架构的特殊优势的良好代码。编译器后端一般包括指令选择,寄存器分配和指令时序分配等。

这个三段模型通用适用于动态解释器和JIT编译器。Java虚拟机(Java Virtual Machine, JVM)也是这种模型的一种是心啊,其中Java bytecode用于前端和优化器的中间连接。

三段式设计的优势

这种经典的传统三段式设计方法最大的优势在于编译器可以支持多种语言和架构。如果编译器使用一种常见的编码作为优化器的表征,那么前端可以采用任意的编程语言,后端可以作用于任意的目标架构,参见下图。 RetargetableCompiler

在这种设计下,如果编译器要支持一种新的语言(例如BASIC)需要重新实现一个新的前端,但是当前的优化器和后端可以被重新使用。如果不采用这种三段模式,那么这些部分就无法被分割,实现一个对新编程语言的执行就需要从头做起,需要支持N个目标架构和M种编程语言将会需要N乘M个编译器。

另一个三段式设计方法的优点在于编译器可以服务于采用不同编程语言的各类程序员。对于一个开源项目来说,这意味着这将会有一个更大的群体和更多的贡献,能够进一步提高和增强现有的编译器。这也是为什么一些开源编译器服务于许多社区(例如GCC)都在尝试生成更好的机器码而不是单一化编译器(例如FreePASCAL)。

最后一个优点是这种分割方式能让前后端的开发人员很好的维护和增进自己的部分,属于松耦合。对于开源软件来说,松耦合可以帮助减少其他人员开发时的障碍。

现有编程语言的实现

尽管三段式设计的优势巨大,但在实际中基本不可能被完全实现。回顾从LLVM之前的开源语言实现,你会发现对Perl,Python,Ruby和Java的实现没有共享任何代码。更进一步,Glasgow Haskeel COmpiler (GHC)和FreeBASIC等项目可以重映射在不同的CPU上,但他们只能支持一种编程语言。

之前提到过,这里有三种成功实现了这种模型,第一种是个Java和.NET虚拟机。他们的系统提供了一种JIT编译器,支持runtime和一种定义好的bytecode格式。这意味着任何语言都可以编译成bytecode的格式并且在运行时利用优化器和JIT的优势。作为代价的是,这些实现基本无法提供对runtime的选择上的灵活性:他们都采用JIT编译,垃圾回收和专门的面向对象模型。这导致了当编译的语言不是很符合该模型时(例如C)只有部分优化后的性能。

另一个成功的案例可以说是最不幸的,但是也是一种重新使用编译器技术的常见方式:将输入的源代码翻译成C代码然后送入已有的C代码编译器。这允许重新使用优化器和代码生成器,有很好的灵活性来控制runtime,这种方式也非常方便前端执行者理解和维护。但不幸的是,采用这种方式会阻止有效的异常处理的实现,并且只提供了非常糟糕的debug过程,减慢了编译速度,并且当新的语言想要加入其他特点(C语言没有的)时容易出现问题。

最后一个对三段式模型的成功实现是GCC。GCC支持许多的前端和后端,并且有非常活跃和广泛的社区贡献者。GCC有一段很长的成为C编译器的历史,并且支持了多种架构,一些其他语言也依赖于GCC。渐渐的,GCC社区慢慢衍化出了一个更清晰的设计。GCC4.4,拥有一种对优化器的新的表示方式,与提到的三段式模型更加接近。

尽管上述三个案例都非常成功,但这三个方式都拥有非常大的使用局限性,因为他们被设计用于单个且庞大的应用。举个例子,现实中将GCC嵌入到其他应用,比如将GCC用作一个runtime/JIT编译器或者提取并重新使用GCC中的一部分基本是不可能的。想要使用GCC中C++的前端用于文件生成、重构、静态分析工具的开发者不得不将GCC用作一个巨大单一的应用来实现他们的想法,即很难抽取GCC中一部分用作他用。

这里有一些对GCC为什么很难被重新用做库的解释,包括GCC中对全局变量的滥用,没有仔细设计的数据结构,宏的应用等。最难以修复的问题是它最早被设计时产生的内部架构的问题。具体来说,GCC存在layering和抽象泄露(leaky abstractions)的问题:后端需要使用前端的AST来生成debug信息,而前端生成了后端的数据结构,因此整个编译器以来于许多全局结构。

总结:三段式设计有重要的优势,但现实中三种成功实现并没有完全达到当初的目标。其中,GCC已经拥有了尽可能的前后端分离模式的设计,但依然存在前后端的大量耦合,因此给其他开发者的重用带来了极大的不便。

LLVM的代码表示:LLVM IR

在了解了历史背景后,现在让我们来探究LLVM吧!LLVM最重要的设计就是中间层表示,LLVM Intermediate Representation (IR), 这是一种在编译器中用来代表代码的形式。LLVM IR被设计用于处理中间层的表示和优化器中的转化。它最初设计时有许多特定的目标,包括支持轻量级的运行时优化,过程优化,全代码分析以及强大的重构转换等等。最重要的一个方面是它本身被定义为一流的语言(a first class language)拥有经过很好定义的语义符号。下面用一个例子来具体说明,这一个非常简单的.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指令集很像,它支持一些简单的线性序列质量例如:加、减、比较、分支。这些指令有三种形式,意味着他们采用一定数量的输入并生成结果放入一个不同的寄存器中。LLVM IR支持labels并且看起来很像一种汇编语言的变体。

与大部分的RISC指令集不同,LLVM强调类型,拥有一种简单的类型系统(例如,i32时一种32bit的整型,i32**是一个指针,指向32bit的整形),还有一些机器的细节被抽象了。例如calling被抽象为call和ret指令和明确的参数。另一种与机器码明显的不同在于LLVM IR不会使用一个固定的寄存器集合,它可以使用无限的寄存器,用一个%开头表示。

不只是被当作一种语言实现,LLVM IR实际上被定义为三种同构的形式:上述的文本形式,可以被优化器修订的可审查的内存数据格式,一种有效密集型的二进制"bitcode"格式。LLVM项目也提供了工具将从文本格式转为二进制格式:llvm-as汇编文本格式.ll文件为.bc文件,.bc文件包含bitcode编码;而llvm-dis将.bc文件转为.ll文件。

LLVM IR,编译器的中间表示层是非常有意思的,因为它可以为编译器的优化器提供一个完美的世界:不像编译器的前端和后端,优化器不会被一种特定的语言或者架构所约束。另一方面,IR也必须服务好前后端:它必须设计的能够被前端很好的生成,也必须能够足够强大到让优化器针对现实中的架构去优化。

总结:LLVM IR类似于RISC的虚拟指令,是编译器的中间层表示,服务于优化器。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用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方法来更新代码中的指令,将其转化为更简单的形式。

总结:LLVM IR优化器中会在SimplifySubInst函数中列出可简化的表达式,SimplifyInstruction用于对每一条指令检测,如果返回非空,则进行替换

LLVM对三段式设计的实现

在基于LLV吗的编译器中,一个前端负责解析,验证和诊断输入代码的错误,接着将解析后的代码转为LLVM IR(一般情况下,但并不总是,通过建立AST然后将AST转为LLVM IR)。IR可以选择性的通过一系列的分析和优化来提高代码质量,然后送入代码生成器来产生原始的机器码,整体过程参见下图。这是一种非常直接的三段式设计的执行方式,但这个简单的描述掩盖了许多重要、强大并且灵活的LLVM IR中的架构。

LLVMCompiler1

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

具体来说,LLVM IR是一种特定并且是唯一的优化器接口。这个特点意味着,如果你想写一个LLVM的前端,你所唯一需要知道的是LLVM IR是什么,它是如何工作的,和它所期望的不变式。既然LLVM IR具有一流的文本结构形式,那么构建一个前端输出LLVM IR作为文本也是可能以及合理的,接着我们可以通过Unix pipes来将它输入到优化器序列以及代码生成器中。

上述可能会使你感到惊讶,但其实这是LLVM的一个新颖的特性,也是LLVM成功地被广泛应用的一个主要原因。甚至是另一个成功并且非常成熟的架构GCC编译器也没有这个特性:它的GIMPLE中间层并不是一个完整独立的表示。作为一个简单的例子,当GCC代码生成器产生DWARF 调试信息时,它需要接触到源代码的树状结构。GIMPLE本身使用元祖作为代码运行的表示,但(至少在GCC4.5中)它依然需要参考source level tree的形式。

这意味着前端开发者需要知道并生成GCC的树数据结构以及使用GIMPLE来写GCC前端。GCC的后端也有相似的问题,因此他们也需要知道后端的RTL如何工作。最终,GCC并没有一个方式来解决"everything representing my code"或者一种方式在文本中读和写GIMPLE。这个问题导致GCC只有相对较少的前端。

总结:LLVM IR的优势是它是一种完全的代码表示,可以将前端和后端完全切开,并且是唯一的接口,相比GCC,给前端开发带来极大的优势。

LLVM是库的集合

在设计了LLVM IR之后,接下来LLVM最重要的一部分就是它是被设计为库的集合,而不是类似GCC的单一庞大的命令行编译器或者不透明的虚拟机类似JVM和.NET虚拟机。LLVM是一个基础架构,一系列有用的编译器技术的集合,可以用来解决一些列特定的问题(类似建立一个C的编译器,或者一个特定领域的优化器)。这个他最强大的特点,但却是鲜为人知的一个设计。

然我们将优化器的设计作为一个例子:它读取LLVM IR的输入,将其按bit分割,然后再输出能够更快执行的LLVM IR。在LLVM以及其他许多编译器,优化器被组织为不同优化passes的流水线,passes作用在输入然后决定是否要做一些优化。取决于优化的程度,会有不同的passes运行,例如在 -O0(无优化)下,Clang编译器不会运行passes,在-O3时会在优化器中运行67个passes(LLVM 2.8中)。

每一个LLVM pass被写作一个C++类,从Pass类中衍生。大部分的pass都写在一个单个的.cpp文件中,而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优化器提供了非常多的不同的passes,其中的每一个都用相似的风格写成。这些passes被编译为一个或多个.O文件,接着被编译为一系列archive libraries(Unix系统上的.a文件)。这些库提供了各种分析和转换的能力,这些passes则尽可能的松耦合:它们被期望只负责自己的部分,或者和其他passes独立开来。当有一系列passes要运行时,LLVM Pass管理器使用依赖信息来满足这些依赖以及优化passes的传输。

库和抽象能力很棒,但它们实际上并不能解决问题。最有趣的部分时当开发者想要开发一个新的工具能够编译器技术中受益,例如一个用于图像处理的JIT编译器。这个JIT编译器的实现者可能在大脑里有一系列的约束:例如,这个图像处理语言对编译时间的延迟非常敏感并且有一些特有的语言特性对于性能优化非常重要。

基于库的设计的LLVM优化器可以让我们的这位实现者挑选passes执行的顺序,尤其是那些对图像处理领域真正有用的:如果所有的passes都定义在一个大的函数中,那么就会浪费大量时间内建。如果没有指针,那么化名分析(alias analysis)和内存优化并不需要考虑。不过,LLVM也无法神奇的解决所有的优化问题。既然pass子系统被模块化,并且PassManager它本身也不知道任何关于passes内部的信息,那么这位实现者可以随意的执行针对他自己的特定的语言的passes来解决LLVM优化器的缺点。下图展示了一个简单的假设的XYZ图像处理系统。

PassLinkage

一旦优化器的集合被选中(与对代码生成器相似的决定),图像处理编译器就会建立成一个可执行或动态库。既然唯一指向LLVM优化器passes的是简单的create函数,定义在每一个.o文件,但既然优化器存在于.a的archive libraries,实际上只有被用到的优化器passes会被连接到后端,而非整个LLVM优化器。在我们上述的例子中,既然用到了PassA和PassB,它们会被连接到库。既然PassB用到了PassD作为一些分析,PassD也会被连接。然后,PassC(还有许多其他的优化器)并没有被用到,它们的代码不会连接到这个图像处理应用中。

这就是基于库设计的LLVM的强大之处。这种直接的设计方式让LLVM可以提供强大的能力,对特定的使用者非常有用,而不需要让想做简单的事情的开发者使用全部的库。与之相对比,传统的优化器代码连接过于紧密,很难去进行子结构的划分以及加速。有了LLVM,你可以理解单个的优化器而不需要知道全部的系统如何一起工作。

这个基于库的设计也是让这么多的人会错误的理解LLVM是什么的一大原因:LLVM的库有许多能力,但它们实际上自己并不作任何事情。实际上,这是取决于设计者来挑选使用库中的哪一部分(例如Clang C编译器)。这也是LLVM优化器被广泛使用在不同领域的一个原因。此外,LLVM也提供了JIT编译器的能力,但这不意味着每一个使用者都要去用它。

总结:LLVM优化器是基于库集合的设计,因此只有被用到的pass才会在实际中连接到应用中,增加了极大的灵活性。

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

LLVM代码生成器用于将LLVM IR转换为特定架构的机器码。另一方面,代码生成器的工作是针对给定架构产生最好的机器码。理想情况下,每一个代码生成器都需要针对架构完全的特殊化,但另一方面,针对每一个架构的代码生成器都是在解决非常相似的问题。例如,每一个架构都需要对寄存器分配值,尽管每一个架构都有不同的寄存器文件,但采用的算法需要尽可能的通用。

与优化器的方法相似,LLVM的代码生成器将代码生成的问题划分为个体的passes——指令选择,寄存器分陪,时序安排,代码布局安排优化以及汇编,并且提供了许多内建的自动运行的passes。架构的作者接下来需要在这些默认的pass中进行挑选,使用这些默认的passes或者针对特定的架构设计一些特殊的passes。举个例子,x86的后端使用寄存器压力减少的调度器,因为它只有非常少的寄存器,但是PowerPC的后端使用的是延迟优化调度器,因为PowerPC寄存器有很多。x86的后端使用一个自定义的pass来处理x87的浮点指针栈,而ARM的后端使用一个自定义的pass来处理函数需要的大量常量。这种灵活性让架构的作者可以产生很好的代码而不需要从头书写整个代码生成器。

LLVM目标架构描述文件

混合和匹配的方法让架构作者可以选择对它们的架构最合理的部分并且允许大量的代码在不同的架构上重用。这带来了另一个挑战:每一个共享的组件都需要以一种通用的方式对特定的架构属性匹配。举例来说,一个共享的寄存器分配器需要知道每一个目标架构的寄存器文件并且知道指令和它们寄存器操作数之间的关系。LLVM对这个的解决方法是以一种公告性的特定领域语言(一系列.td文件,被tblgen工具处理)提供对特定的架构描述。这个简化的针对x86架构的处理如下图所示:

X86Target

不同子系统被.td文件支持允许架构作者来建立自己架构的不同模块。例如,x86的后端定义了一类寄存器用于控制所有的32-bit寄存器(称为GR32)如下:

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

这个定义说明这类中的寄存器可以存储32-bit的整形值("i32"),还有特定的16的寄存器(在.td文件中定义)和一些其他的信息来特定化分配顺序。给定这个定义,特定的指令可以参照于此,将其作为早错书。例如,“补充一个32bit寄存器”的指令定义如下:

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-bit寄存器$dst并且有一个32bit寄存器作为输入叫做$src(GR32寄存器类定义了什么样的寄存器才能用于操作),指明了这条指令的汇编语法(使用{}语法来处理AT&T和英特尔语法),指令了指令的效果并在最后一行提供了应该匹配的模式。 第一行的“let”约束告诉了寄存器分配器输入和输出寄存器必须被分配给同一个物理寄存器。

这个定义是一个对指令非常密集的描述,常见的LLVM可以通过该信息做很多。这个定义已经足够让指令分配器来形成这个指令,通过在输入的IR代码中进行模式匹配。它还告诉了寄存器分配器如何处理这个,这足够对机器码的比特进行编码和解码指令,也足够以文本的形式解析和打印指令。这些能力可以让x86架构支持产生一个单独的x86汇编并从架构的描述中反汇编以及处理JIT的编码指令。

除了提供有用的功能,拥有从同一个"truth"中生成多重信息也是一大优势。这个方法让汇编和反汇编 。这种方法使汇编器和反汇编器在汇编语法或二进制编码中彼此不同意几乎是不可行的。它还使目标描述易于测试:可以对指令编码进行单元测试,而不必涉及整个代码生成器。

尽管我们的目标是以一种很好的声明形式将尽可能多的目标信息存到.td文件中,但我们仍然不具备所有内容。 相反,我们要求目标作者为各种支持例程编写一些C++代码,并实现他们可能需要的任何特定于架构的传递(例如X86FloatingPoint.cpp,它处理x87浮点堆栈)。 随着LLVM继续增长新的目标,增加.td文件中可以表达的目标数量变得越来越重要,并且我们将继续提高.td文件的可表达性来处理此问题。 一个很大的好处是随着时间的推移,在LLVM中变得越来越容易写入目标架构。

模块化设计提供的强大性能

除了上述提到的优雅的设计,模块化给使用者提供了LLVM库的一些有趣的能力。这些能力来自于LLVM提供的功能,但是让使用者来决定最后如何使用的策略。

选择在何时何地运行

正如之前所提到的,LLVM IR可以有效的从一个二进制形式(LLVM bitcode)中有效的序列化或者反序列化。既然LLVM IR本身是独立自足的,序列化也是一个没有损失的过程,我们可以做一部分的编译,将我们的程序保存在disk上,之后在未来我们再继续工作。这个特点提供了一些列有趣的能力,包括支持连接时间和安装时间的优化,他们都从编译时间中延迟了代码生成。

连接时间优化解决了传统编译器一次只能看到一个转换单元(translation unit)(例如,一个.C文件和它所有的头文件),因此无法跨文件做优化的问题。 类似Clang的LLVM编译器通过-flto或者-O4的命令行选项来支持这一点。这一个选项命令编译器输出LLVM的bitcode到.o文件,而不是写一个原生的目标文件,并延迟代码的生成到连接时间,参考下图

LTO

细节上的不同取决于你所运行的系统,但最重要的bit是这个链接器在.O文件检测LLVM bitcode而非在原声的目标文件。当链接器看到这个,它会读取所有的bitcode文件到内存,将他们连接在一起,并在聚集之后接着运行LLVM优化器。既然优化器可以就看到代码的一大部分,它就可以内连,传递恒量,做一些代码消除的工作,和跨越文件的边界。尽管现在很多的编译器支持LTO,他们中的大部分(例如GCC,Open64,英特尔编译器等等)是通过一个非常慢的序列进程来完成的。在LLVM中,LTO从系统设计中脱颖而出,并且可以跨不同的源语言(不同于许多其他编译器)工作,因为IR是源语言中立的。

安装时间优化是将代码生成的时间全部延迟到安装时间,甚至是在延迟时间之后,如下图所示。安装时间是一个非常有趣的时间(将软件打包装盒,下载,上传到移动设备等等),因为这是要找到目标架构的详细信息的时候。在x86系列架构中,它们有很多芯片的不同的特性。通过延迟指令的选择,调度和代码生成的其他方面,你可以选择出软件运行在特定硬件上的最佳答案。

InstallTime

优化器的单元测试

编译器是非常复杂的,它的质量是很重要的,因此测试非常重要。例如,在修复了一个引起优化器崩溃的错误后,一个回归测试需要加入并确保这个不再发生。传统的用来测试这个的方法是一写一个.c文件来运行一下编译器,并且再次测试编译器是否还会崩溃。这个方法被GCC的测试系统所使用。

采用这个方式解决这个问题是因为编译器包含了许多不同的子系统甚至在编译器中有很多不同的passes,这些都有可能会随着时间改变输入的代码。如果有什么改变了前端或着早期的优化器,则测试案例可能很难测试到应该被测试的地方。

通过使用LLVM IR的文本形式以及模块优化器, LLVM的测试系统有很好的回归测试系统可以从硬盘上加载LLVM IR,在一个优化器pass上运行它,然后验证它是否是所期望的行为。除了崩溃,一个更复杂的行为测试需要验证优化器是否正确运行。这里有一段简单的测试案例来检查常量传递pass在加法指令下是否工作:

; 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(可以动态的加载含有其他passes的插件)并且将它们通过命令行输出。FileCheck工具验证了它标准的输入是否符合一系列的CHECK指令。在这个案例中,这个简单的测试在验证constprop pass能否完成add4和9成为9。

尽管上述是一个看起来有点繁琐的例子,这其实是非常难用.c文件去测试的:前端在它们解析的时候经常需要做常量折叠,所以编写相关代码是很难以及脆弱的。因为我们可以将LLVM IR加载为文本并且送入我们感兴趣的特定的优化器pass中,接着将结果输出到另外一个文本文件中,这是非常直接的也是我们想要的测试方式。

采用BugPoint的自动测试案例简化

当一个bug在编译器或者LLVM库的中发现,修复它的第一步要做的是生成一个能使错误复现的样例。一旦你有了这个测试样例,最好将其压缩到最小来产生这个问题,并且定位到是LLVM的哪部分产生了这个问题,例如是优化器的pass出错了。尽管最终你会知道如何操作,但是这个过程是枯燥乏味的,尤其是当编译器产生了不正确的代码但是没有崩溃时尤其麻烦。

LLVM BugPoint工具使用IR序列化和LLVM的模块设计来自动执行这个过程。例如,给定输入.ll或.bc文件以及导致优化器崩溃的优化过程列表,BugPoint将输入减少到一个小的测试用例,并确定哪个优化器出了故障。然后,它输出简化的测试用例和用于重现故障的opt命令。它是通过delta debugging类似的技术来减少输入和优化器pass的列表。因为它知道LLVM IR的结构,BugPoint不需要浪费时间来生成无效的IR作为优化器到的输入,这一点不像delta的命令行工具。

在其他更复杂的编译错误案例中,你需要检查输入,代码生成信息,pass的执行命令和输出结果。如果问题是出在优化器或者代码生成器上,BugPoint会首先定义这个问题,接着将测试案例反复分割成两部分:一个是送入已知确认没有问题的部分,一部分送入已知错误的部分。通过反复的分割和移动代码,它可以减少测试案例。

BugPoint是一个非常简单的工具并能节省大量的测试时间。其他的编译器没有这样相似的强大工具,因为它是依赖于定义好的中间层表示。这就是说,BugPoint并不完美,并且将从重写中受益。随着时间的流逝,它不断加入了新的功能(例如JIT调试)。

回顾和未来方向

LLVM的模块化最初并不是针对上述的描述的目标设计的。它是一个自卫机制:很显然我们最开始没法让所有事情都是对的。例如,模块pass的流水线,用于将隔绝pass更加简单,所以他们在之后有更好的实现之后能被取代。

另一个让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变得越来越不灵活,越来越钙化的风险不断存在。尽管没有解决这个问题的灵丹妙药,但我希望继续接触新的问题领域,重新评估先前的决定以及重新设计并丢弃代码的意愿将有所帮助。毕竟,目标并非是完美无缺,而是要随着时间的推移不断变得更好。