起重机起重的新后端

2020-10-11 16:19:08

这篇文章将我最近在Cranelift上的工作描述为我在Mozilla的日常工作的一部分。在这篇文章中,我将设置一些上下文并描述指令选择问题。特别地,我将谈一谈指令选择器和后端框架的总体改造,这是我们在过去九个月左右一直致力于的工作。这项工作是与我杰出的同事朱利安·苏厄德(Julian Seward)和本杰明·布维尔(Benjamin Bouvier)共同开发的,丹·戈曼(Dan Gohman)也提供了重要的早期投入,并得到了所有优秀的Cranelift黑客的帮助。

该项目是一个用Rust编写的编译器框架,专为即时编译而设计(但不是排他性的)。它是一个通用编译器:它最流行的用例是编译WebAssembly,尽管还有其他几个前端,例如cg_clif,它使Rust编译器本身适应使用Cranelift。到目前为止,Mozilla和其他几个地方的人们已经在开发编译器几年了。它是wamtime(浏览器外部的WebAssembly运行时)的默认编译器后端,也在其他几个地方的生产中使用。

我们最近打开了开关,在ARM64(AArch64)机器(包括大多数智能手机)上的夜间Firefox中打开了基于Cranelift的WebAssembly支持,如果一切顺利,它最终将在稳定的Firefox版本中发布。Cranelift是在字节码联盟的保护伞下开发的。

在过去的9个月里,我们在Cranelift中为“机器后端”(即编译器中支持特定CPU指令集的部分)构建了一个新的框架。如上所述,我们还为AArch64添加了一个新的后端,并根据需要填充了功能,直到Cranelift准备好在Firefox中投入生产使用。这篇博客文章设置了一些背景,并描述了进入后端框架改造的设计过程。

为了理解我们最近在Cranelift上所做的工作,我们需要放大上面的Cranelift_codegen箱子,并讨论它过去是如何工作的。这个“Clif”输入是什么,编译器如何将其转换为CPU可以执行的机器码?

Cranelift使用CLIF或Cranelift IR(中间表示)格式来表示它正在编译的代码。每个执行程序优化的编译器都使用某种形式的中间表示(IR):您可以将其视为虚拟指令集,它可以表示程序被允许执行的所有操作。IR通常比实际指令集简单,设计为使用一小部分定义良好的指令,以便编译器可以很容易地推理出程序的含义。

IR还独立于编译器最终面向的CPU体系结构;这使得只要编译器适合于面向新的CPU体系结构,就可以重用大部分编译器(例如,从输入编程语言生成IR的部分,以及优化IR的部分)。CLIF采用静态单赋值(SSA)形式,并使用带有基本块的传统控制流图(尽管它以前允许扩展基本块,但这些块已被逐步淘汰)。与许多SSAIR不同,它用块参数表示φ节点,而不是显式的φ指令。

在creenelift_codegen中,在我们修改后端设计之前,程序在整个编译过程中一直保留在Clif中,直到编译器发出最终的机器码。这似乎与我们刚才所说的相矛盾:IR怎么可能是独立于机器的,但又是我们发出机器代码的最终形式呢?

答案是,旧的后端是围绕“合法化”和“编码”的概念构建的。从更高的层次来看,想法是每条Cranelift指令要么对应于一条机器指令,要么可以被一系列其他Cranelift指令所取代。有了这样的映射,我们可以分步细化Clif,从来自早期编译器阶段的与机器无关的任意指令开始,执行编辑,直到Clif与机器代码一一对应。让我们可视化一下这个过程:

对机器指令进行直接“编码”的Clif指令的一个非常简单的例子是iadd,它只将两个整数相加。在基本上任何现代架构上,这应该映射到一个简单的ALU指令,该指令将两个寄存器相加。

另一方面,许多CLIF指令没有清晰地映射。有些算术指令就属于这一类:例如,有一条CLIF指令用来计算整数的二进制表示(Popcount)中的设置位数;并不是每个CPU都有一条这样的指令,所以它可能会扩展成更长的位操作序列。

也存在在更高语义级别上定义的操作,这些操作必须随着扩展而降低:例如,对WASM存储器的访问被降低为获取线性存储器基数及其大小、对照限制检查WASM地址的界限、计算WASM地址的真实地址并执行访问的操作。

然后,为了编译一个函数,我们迭代Clif并找到没有直接机器编码的指令;对于每个指令,我们只需展开到合法化的序列,然后递归地考虑该序列中的指令。我们循环,直到所有指令都有机器编码。在这一点上,我们可以发出与每条指令的编码相对应的字节。

传统的Cranelift后端设计有许多优势,它在整个过程中使用单一IR执行基于扩展的合法化。然而,正如人们可能预料的那样,也有一些缺点。让我们分别讨论其中的几个。

通过对单个IR的操作一直到机器代码的发送,可以在多个阶段应用相同的优化。

如果大多数Cranelift指令变成一条机器指令,并且几乎不需要合法化,那么这个方案可以非常快:它变成了简单的一次遍历来填充“编码”,这些编码由小索引表示到一个表中。

基于扩展的合法化可能并不总是产生最佳代码。有时存在实现多个CLIF指令的行为的单机指令,即多对一映射。为了生成高效的代码,我们希望能够使用这些指令;而基于扩展的合法化则不能。

基于扩展的合法化规则必须遵守指令之间的偏序:如果A扩展为包括B的序列,则B稍后不能扩展为A。这可能会成为机器后端作者保持直通的一个困难。

基于扩张的合法化存在效率问题。在算法级别,我们倾向于尽可能避免定点循环(在这种情况下,“继续扩展,直到不再存在扩展”)。运行时是有界的,但是这个界有点难以推论,因为它依赖于链式扩展的最大深度。支持就地编辑的数据结构也比我们希望的要慢得多。通常,编译器将IR指令存储在链接列表中,以允许就地编辑。虽然这与基于数组的解决方案渐近一样快(我们永远不需要执行随机访问),但在现代CPU上,它对缓存或ILP的友好性要差得多。相反,我们更喜欢存储指令数组,并在任何可能的情况下对它们执行单次遍历。

随着时间的推移,我们对合法化方案的具体实现变得有些笨拙(例如,参见GitHub问题#1141:用火杀死食谱)。添加一条新指令需要学习“食谱”、“编码”和“合法化”,以及仅仅是指令和操作码;更传统的代码降低方法可以避免大部分这种复杂性。

单级IR有一个基本的张力:要使分析和优化正常工作,IR应该只有一种方式来表示任何特定的操作。另一方面,机器级别的表示应该表示目标ISA的所有相关细节。单一的IR根本不能很好地服务于这一光谱的两端,当CLIF从任何一端偏离时,困难就出现了。

出于所有这些原因,作为Cranelift改造的一部分,以及我们新的AArch64后端的先决条件,我们为机器后端和指令选择构建了一个新的框架。该框架允许机器后端独立于Clif定义它们自己的指令;我们不是通过扩展使其合法化并运行到固定点,而是定义单一的降低路径;并且一切都围绕更高效的数据结构构建,仔细地优化数据传递并完全避免链表。现在我们来介绍一下这个新设计!

新的Cranelift后端的主要思想是添加一个特定于机器的IR,它有几个专门选择的属性来很好地表示机器代码。我们称之为VCode,它来自“虚拟寄存器代码”,VCode包含机器,或机器指令。我们做出的主要设计选择是:

VCode是线性指令序列。有允许遍历基本块的控制流信息,但数据结构并不能轻松地允许插入或删除指令或重新排序代码。取而代之的是,我们只需一次遍历就可以进入VCode,按照指令的最终(或接近最终)顺序生成指令。

VCode不是基于SSA的;相反,它的指令在寄存器上操作。降低时,我们分配虚拟寄存器。生成VCode后,寄存器分配器计算适当的寄存器分配并就地编辑指令,用真实寄存器替换虚拟寄存器。(两者都打包到32位表示空间中,使用高位来区分虚拟和真实。)。在这个级别上避免SSA允许我们避免维护其不变量的开销,并且更接近于真实的机器。

VCode指令简单地存储在数组中,基本块单独记录为数组(指令)索引范围。我们设计此数据结构是为了快速迭代,而不是为了编辑。

从VCode容器的角度来看,每条指令大多是不透明的,但有几个例外:每条指令都公开其(I)寄存器引用和(Ii)基本块目标(如果是分支)。寄存器引用分为通常的“使用”和“定义”(读取和写入)。

还要注意的是,指令可以引用任何一个虚拟寄存器(这里表示为V0.。Vn)或真实机器寄存器(这里表示为R0.。Rn)。此设计选择允许机器后端在特定指令或ABI(参数传递约定)需要时使用特定寄存器。

除了寄存器和分支目标之外,VCode中包含的指令可以包含发出机器代码所需的任何其他信息。每台机器后端都定义自己的类型来存储此信息。例如,在AArch64上,以下是几种简化的指令格式:

Enum Inst{/具有两个寄存器源和一个寄存器目标的ALU操作。AluRRR{ALU_OP:ALUOp,RD:WRITABLE,Rn:REG,Rm:REG,},/带有寄存器源和立即源以及寄存器/目的地的ALU操作。AluRRImm12{alu_op:aluOp,rd:write,rn:reg,imm12:imm12,},/双向条件分支。包含两个目标;在发出时,发出条件/分支指令,后跟无条件分支指令,但/发送缓冲区通常会将其折叠为只有一个分支。CondBR{Take:BranchTarget,Not_Take:BranchTarget,Kind:CondBrKind,},//...。

这些枚举臂可以被认为类似于旧后端中的“编码”,不同之处在于它们是使用类型安全且易于使用的Rust数据结构以更简单的方式定义的。

现在我们来讨论最有趣的设计问题:如何将独立于机器的CLIF指令降低为具有适当类型CPU指令的VCode?换句话说,我们用什么取代了以扩展为基础的合法化和编码方案?

我们对CLIF指令执行一次遍历,并且在每条指令处,我们调用机器后端提供的函数将CLIF指令降低为VCode指令。后端被赋予一个“降低上下文”,通过该上下文,后端可以检查流入其中的指令和值,并根据需要执行“树匹配”(见下文)。这自然允许1对1、1对多或多对1翻译。我们将引用计数方案合并到此过程中,以确保只有在实际使用指令的值时才会生成指令;当发生多对1匹配时,这是消除死代码所必需的。

回想一下,旧的设计允许从CLIF指令到机器指令的一对一和一对多映射,但不是多对一。当涉及到寻址模式之类的事情的模式匹配时,这尤其有问题,在这些模式中,我们希望识别特定的操作组合,并选择一条同时涵盖所有这些操作的特定指令。

让我们从定义一个以特定Clif指令为根的“树”开始。对于指令的每个参数,我们可以“查找”程序以找到其生产者(Def)。因为CLIF是SSA形式的,所以指令变元是一个普通值,它必须正好有一个定义,或者它是一个表示多个可能定义的块参数(在传统的SSA公式中是φ节点)。我们会说,如果我们达到一个块参数(φ-Node),我们只是在树叶结束-在作为真实数据流的子集的树上进行模式匹配是完全可以的(我们可能会得到次优的代码,但它仍然是正确的)。例如,给定CLIF代码:

块0(v0:i64,v1:i64):brnz v0,块1(V0)跳转块1(V1)块1(v2:i64):v3=iconst.i64 64 v4=iadd.i64 v2,v3 v5=iadd.i64 v4,v0 v6=load.i64 v5返回v6。

让我们考虑加载指令:v6=load.i64v5。简单的代码生成器可以使用保存v5的寄存器作为地址,将这种1对1映射到CPU的普通加载指令。这当然是正确的。不过,我们或许可以做得更好:例如,在AArch64上,可用的寻址模式包括两个寄存器和LDR x0,[x1,x2]或具有恒定偏移量LDR x0,[x1,#64]的寄存器。

我们止步于v2和v0,因为它们是块参数;我们不确定哪条指令将生成这些值。我们可以用常数64代替v3。鉴于此观点,加载指令的降低过程可以相当容易地选择寻址模式。(在AArch64上,进行此选择的代码在此处;在本例中,它将选择寄存器+常量立即形式,为v0+v2生成单独的加法指令。)。

请注意,在降低期间,我们实际上并不显式构造操作数树。取而代之的是,机器后端可以查询每个指令输入,而降低框架将提供一个结构,在已知的情况下给出生成指令,在知道的情况下给出常量值,如果需要的话,给出保存该值的寄存器。

后端可以根据需要遍历树(通过“生成指令”)任意多次。如果它不能将树上更靠上的指令的操作合并到根指令中,则只需使用该点的寄存器中的值即可;仅为根指令生成机器指令始终是安全的(尽管可能不是最优的)。

那么,考虑到这种匹配策略,我们实际上应该如何进行翻译呢?基本上,后端提供了一个函数,每个CLIF指令在操作数树的“根”处调用一次,并且可以生成任意数量的机器指令。此函数本质上只是根Clif指令操作码上的一个大型匹配语句,匹配臂根据需要进行更深入的查找。

以下是整数加法运算降至AArch64的Match-Arm的简化版本(完整版本在此处):

匹配操作{//...。操作码::iadd=>;{let rd=get_output_reg(ctx,output[0]);let rn=put_input_in_reg(ctx,input[0]);let rm=put_input_in_rse_imm12(ctx,input[1]);let alu_op=Choose_32_64(ty,ALUOp::Add32,ALUOp::Add64);ctx.emit(alu_inst_imm12(alu_op,rd,rn,rm));}//...}。

这里的几个帮助器函数中有一些神奇之处。Put_input_in_reg()调用CTX上的正确方法来查找保存输入值的寄存器。Put_input_in_rse_imm12()更有趣:它返回一个ResultRSEImm12,它是一个“寄存器、移位寄存器、扩展寄存器或12位立即数”。这组选项捕获了我们在AArch64上为ADD指令的第二个参数提供的所有选项。

助手查看操作数树中的节点,并尝试匹配移位运算符或零/符号扩展运算符,这两个运算符可以直接合并到加法运算中。它还检查操作数是否为常量,如果是,则可以放入12位立即数字段。如果不是,则退回到简单地使用寄存器输入。Alu_inst_imm12()然后分解此枚举并选择适当的Inst臂(分别为AluRRR、AluRRShift、AluRRRExtension或AluRRImm12)。

就这样!不需要合法化和重复代码编辑来匹配几个操作并产生机器指令。我们发现这种写降低逻辑的方式相当直截了当,很容易理解。

既然我们可以降低一条指令,那么如何降低包含多条指令的函数体呢?这并不像循环遍历指令并调用上面描述的匹配操作码函数那样简单(尽管这实际上是可行的)。特别是,我们希望更高效地处理多对一的情况。考虑当上面的加法指令逻辑能够将(比方说)左移运算符合并到加法指令中时会发生什么。

然后,加法机器指令将使用移位的输入寄存器,并完全忽略移位的输出。如果移位运算符没有其他用途,我们应该避免完全进行计算;否则,将操作合并到加法中是没有意义的。

我们实现了一种引用计数来解决这个问题。具体地说,我们跟踪是否实际使用了任何给定的SSA值,并且只有在使用了CLIF指令的任何结果时(或者如果它有必须发生的副作用),才会为CLIF指令生成代码。这是一种消除死码的形式,但集成到单次降低通道中。

我们必须在Defs之前看到使用情况,这样才能起作用。因此,我们“向后”迭代函数体。具体地说,我们按后序迭代;这样,所有指令都在支配它们的指令之前看到,所以给定SSA形式,我们在defs之前看到用法。

让我们看看这在现实生活中是如何运作的!请考虑以下Clif代码:

函数%F25(I32,I32)->;I32{BLOCK 0(v0:I32,v1:I32):v2=iconst.i32 21 v3=ishl.i32 v0,v2 v4=isub.i32 v1,v3返回v4}。

我们预计左移位(Ishl)操作应该合并到AArch64上的减法操作中,使用ALU指令的reg-reg-Shift形式,确实会发生这种情况(在这里,我展示了在运行Clif-util Compile-d--target aarch64时使用RUST_LOG=DEBUG可以看到的调试转储格式):

Vcode{条目块:0块0:(原IR块:块0)(指令范围:0.。6)Inst 0:mov%v0J,X0 Inst 1:mov%v1J,x1 Inst 2:sub%v4Jw,%v1Jw,%v0Jw,LSL 21 Inst 3:mov%v5J,%v4J Inst 4:mov x0,%v5J Inst 5:Ret}。

然后,它通过寄存器分配器,附加了前言和结尾(在我们知道哪一个之前,我们不能生成它们。

.