起重机械的新后端：指令选择

这篇文章是关于我在Mozilla的日常工作中最近在Cranelift上的工作的三部分系列中的第一部分。在第一篇文章中，我将设置一些上下文并描述指令选择问题。特别地，我将谈一谈指令选择器和后端框架的总体改进，这是我们在过去九个月左右一直在做的工作。这项工作是与我杰出的同事Julian Seward和Benjamin Bouvier共同开发的，也有来自DanGohman的重要早期投入，并得到了所有优秀的Cranelift黑客的帮助。

那么什么是Cranelift呢？该项目是一个用Rust编写的编译器框架，专为即时编译而设计(但不是针对文本)。它是一个通用编译器：它最流行的用例是编译WebAssembly，尽管其他几个领域存在性别歧视，例如cg_clif，它使Rust编译器本身适应使用Cranelift。到目前为止，Mozilla和其他几个地方的人们已经在开发编译器几年了。它是wamtime(浏览器外部的WebAssembly运行时)的默认编译器后端，也在其他几个地方的生产中使用。我们最近打开了开关，在ARM64(AArch64)机器(包括大多数智能手机)上的每晚Firefox中打开基于Cranelift的WebAssembly支持，如果一切顺利，它最终将在稳定的Firefox版本中发布。Cranelift是在BytecodeAlliance的保护伞下开发的。

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

保持所有运动部件的直立可能会让人有点困惑。以下是Cranelift在其他各种组件中的位置的简要概述，重点介绍两个主要的锈箱(Wasm前端和codegen后端)以及使用Cranelift的其他几个程序：

为了理解我们最近在起重机上所做的工作，我们需要放大上面的起重机_codegen板条箱，并讨论它过去是如何工作的。这个“Clif”输入是什么，编译器如何将其翻译成CPU可以执行的机器代码？

Cranelift使用CLIF或Cranelift IR(中间表示)格式来表示它正在编译的代码。每个执行程序优化的编译器都使用某种形式的中间表示(IR)：您可以将其视为虚拟指令集，它可以表示程序允许执行的所有操作。IR通常比真正的指令集更简单，它被设计成使用一小部分定义良好的指令，这样编译器就可以很容易地推理出程序的含义。IR也独立于编译器最终面向的CPU体系结构；这使得编译器的大部分(例如从输入编程语言生成IR的部分，以及优化IR的部分)在编译器适合于面向新的CPU体系结构时都可以重用。CLIF采用静态单赋值(SSA)形式，并使用带有基本块的传统控制流程图(尽管它以前允许扩展基本块，但这些块已被逐步淘汰)。与许多SSAIR不同，它用块参数表示φ节点，而不是显式的φ指令。

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

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

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

另一方面，许多CLIF指令没有清晰地映射。有些算术指令就属于这一类：例如，有一条CLIF指令用来计算整数的二进制表示(Popcount)中的设置位数；并不是每个CPU都有一条这样的指令，所以它可能会扩展成更长的一系列位操作。也有在更高语义级别上定义的操作，这些操作必然伴随着扩展：例如，对Wasm存储器的访问被降低为获取线性存储器基数及其大小、根据限制对Wasm地址进行边界检查、计算Wasmaddress的真实地址并执行访问的操作。

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

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

通过对单个IR的操作一直到机器代码的发送，可以在多个阶段应用相同的优化。例如，考虑将高级“access Wasm memory”指令转换为一系列加载、加法和边界检查的正规化扩展。如果在一个函数中出现许多这样的序列，我们也许能够计算出通用部分(例如：计算Wasm存储器的基数)。因此，本地化方案在尽可能多的阶段将尽可能多的代码暴露给优化机会。遗留的Cranelift流水线实际上是这样工作的：它分别在合法化之前和之后运行“选择前”和“选择后”优化通道。

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

基于扩展的合法化可能并不总是导致不理想的代码。到目前为止，我们已经看到合法化可以从具有一对一或一对多映射的Clif机器指令转换。然而，有时也存在实现多个CLIF指令的行为的单机指令，即多对一映射。为了生成高效的代码，我们希望能够使用这些指令。

例如，在x86上，引用内存的指令可以计算类似base+scale*index的地址，其中base和index是寄存器，scale是1、2、4或8。CLIF中没有这种地址模式的概念，因此当原始iadd(加法)和ishl(移位)或imul(乘法)操作出现在地址计算中时，我们希望对它们进行模式匹配。然后，我们会根据加载指令的输入是加法和移位/乘法的某种特定组合这一事实，以某种方式选择加载指令上的编码。这似乎打破了编码只表示指令操作的抽象。

原则上，我们可以为合法化规则实现更通用的模式匹配，以允许多对一映射。然而，这将是一个重要的解决因素；只要我们从整体上重新考虑设计，就有其他原因避免以这种方式修补问题。

单一IR方法有一个概念上的困难：没有将哪些指令扩展为其他指令的静态表示，并且很难对合法化的整体正确性和终止属性进行推理。

具体地说，基于扩展的合法化规则必须服从指令之间的部分顺序：如果A扩展成包括B的序列，那么B以后不能扩展到A。在实践中，映射大多是一对一的，对于那些不是一对一的映射，在“输入”高级指令和“机器级别”指令之间存在明显的域分离。但是，对于更复杂的机器，或者试图更好地利用目标指令集的更复杂的匹配方案，这可能会给机器后端作者保持直通带来真正的困难。

基于扩张的合法化存在效率问题。在算法层面，我们倾向于尽可能避免定点循环(在这种情况下，“继续扩展，直到不再存在扩展”)。运行时间是有限制的，但是这个限制有点难以推理，因为它取决于链式扩展的最大深度。

支持就地编辑的数据结构也比我们希望的要慢得多。通常，编译器将IR指令存储在链接列表中，以允许就地编辑。虽然这与基于数组的解决方案渐近一样快(我们永远不需要执行随机访问)，但在现代CPU上，它是无缓存友好或ILP友好的。相反，我们更喜欢存储指令数组，并在任何可能的情况下对它们执行单次遍历。

随着时间的推移，我们对合法化计划的具体实施变得非常笨拙。看看这个GitHub的问题，我的雄辩的同事本杰明·布维尔(Benjamin Bouvier)在其中描述了我们想要修复设计的所有原因：#1141：用火杀死食谱。对于构建它的工程师来说，这不是轻而易举的事；复杂性得到了尽可能好的管理，并通过一个非常好的基于DSL的代码生成步骤从高级规则规范中生成了规格化程序。然而，通过合法化和编码进行推理变得比我们希望的更麻烦，而且编译器后端对贡献者来说并不是很容易访问。添加一个新的结构需要学习“食谱”、“编码”和“合法化”，以及仅仅是指令和操作码，并通过DSL找到方法来正确地将各个部分组合在一起。一种更传统的代码降低方法将在很大程度上避免这种复杂性。

单层信息检索有一个基本的张力：为了更好地进行分析和优化，信息检索应该只有一种方式来表示任何特定的操作，即应该由一小组规范指令组成。另一方面，机器级别的表示应该表示目标ISA的所有相关细节。例如，地址计算可能在机器上以许多不同的方式发生(具有不同的寻址模式)，但我们不希望在所有分析中都必须分析特定的地址计算操作码。发射时的隐式规则(“以ADD指令作为输入的加载总是变成此寻址模式”)也不理想。

单一的IR根本不能很好地服务于这一光谱的两端，而当CLIF从任何一端偏离时，困难就出现了。要解决此冲突，最好使用由显式指令选择器连接的两级表示。它允许Clif本身尽可能简单和非规范化，同时允许在特定于机器的指令中包含我们需要的所有细节。

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

新的Cranelift后端的主要思想是添加一个特定于机器的IR，带有几个专门选择来表示机器代码的属性(即，IR非常接近机器代码)。我们称之为VCode，它来自“虚拟寄存器代码”，VCode包含机器，或机器指令。我们做出的主要设计选择是：

VCode是线性指令序列。有允许遍历基本块的控制流信息，但数据结构并不容易允许插入或删除指令或重新排序代码。取而代之的是，我们只需一次遍历就可以进入VCode，按照指令的最终(或接近最终)顺序生成指令。我将在后续的帖子中写更多关于我们如何提高效率的文章。

这一设计方面避免了链表数据结构的低效，而是允许快速传递指令数组。我们保持了相对较小的MachInst大小(对于AArch64，每条指令16字节)，这也有助于代码生成和迭代速度。

VCode不是基于SSA的；相反，它的指令在寄存器上操作。在降低的同时，我们分配虚拟寄存器。生成VCode后，寄存器分配器计算适当的寄存器分配并就地编辑指令，用真实寄存器替换虚拟寄存器。(两者都打包到32位表示空间中，使用高位来区分虚拟和真实。)。

在这个级别上避免SSA允许我们避免维护其不变量的开销，并且更接近于真实的机器。允许指令的低位例如在执行最终写入之前使用目的寄存器作为临时寄存器。如果我们需要SSA形式，我们将不得不在本例中分配一个临时的，并依赖寄存器分配器将其合并回相同的寄存器，这会增加编译时开销。

VCode是用于机器的容器，但是每个机器后端都有单独的MachInsttype。与机器无关的部分在MachInst上被参数化(这是Rust中的一个特性)，并且被静态地单形化到为其构建编译器的特定目标。

使用Rust针对强类型数据结构(如枚举)的优秀工具对机器指令进行建模可以避免混乱的结构域问题(CLIF指令是独立于机器、依赖于机器还是两者兼而有之？)。并且允许每个后端存储用于其编码的适当信息。

您可以将VCode函数体可视化为由以下信息组成(简化；下面还有一个真实示例)：

注意，指令简单地存储在数组中，并且基本块被单独记录为数组(指令)索引的范围。如上所述，我们设计此数据结构是为了快速迭代，而不是为了编辑。我们始终确保第一个块(B0)是入口块，并且连续的块索引具有连续的指令索引范围(即，彼此相邻放置)。

从VCodecontainer的观点来看，每条指令大多是不透明的，但有几个例外：每条指令公开其(I)寄存器引用和(Ii)基本块目标(如果是分支)。寄存器引用被重新分类为通常的“使用”和“定义”(读取和写入)。2个。

还要注意的是，指令可以引用任何一个虚拟寄存器(这里表示为V0.。Vn)或真实机器寄存器(这里表示为R0.。Rn)。此设计选择允许机器后端在特定指令或ABI(参数传递约定)需要时使用特定寄存器。VCode的语义是这样的，寄存器分配器从默认情况下识别真实寄存器的活动范围，并且避免将虚拟寄存器分配给那些特定的真实寄存器以获得它们的活动范围。分配后，所有机器指令都会在适当位置进行编辑，以仅引用真实寄存器。

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

Pub enum Inst{/具有两个寄存器源和一个寄存器目标的ALU操作。AluRRR{alu_op：ALUOp，RD：Writable<；reg>；，rn：reg，rm：reg，}，/带有寄存器源和立即源以及寄存器/目的地的ALU操作。AluRRImm12{alu_op：ALUOp，rd：Writable<；reg>；，rn：reg，imm12：imm12，}，/带16位立即数的MOVZ。MovZ{rd：Writable<；reg>；，imm：MoveWideConst，size：OperandSize，}，/双向条件分支。包含两个目标；在发出时，发出条件/分支指令，后跟无条件分支指令，但/发送缓冲区通常会将其折叠为只有一个分支。有关更多信息，请参阅后续/博客帖子！CondBR{Take：BranchTarget，Not_Take：BranchTarget，Kind：CondBrKind，}，//...}。

这些枚举臂可以被认为类似于旧后端中的“编码”，不同之处在于它们的定义方式要简单得多。虽然旧的Cranelift后端必须使用DSL定义指令编码，并且为这些编码分配了一个数字索引和用于附加指令参数的特殊位压缩编码，但在这里，指令只是存储在类型安全且易于使用的Rust数据结构中。

我们将不再进一步讨论VCode数据结构设计或指令接口，只是要注意，新机器后端的相关指令发送功能可以通过为一个人的指令类型提供MachInst traitimementation来实现(然后降低到其中；见下文)。我们相信，早期的经验似乎表明，与在Cranelift的旧的基于DSL的框架中开发后端相比，这是一项容易得多的任务。

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

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

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

让我们从定义一个以特定CLIFinstructions为根的“树”开始。对于指令的每个参数，我们可以“查找”程序以找到它的p。

.