Cranelift 的新后端，第一部分：指令选择

这篇文章将描述我最近在 Cranelift 上的工作，作为我在 Mozilla 的日常工作的一部分。在这篇文章中，我将设置一些上下文并描述指令选择问题。特别地，我将讨论我们过去九个月左右一直在进行的后端框架的改进。这项工作是与我优秀的同事 Julian Seward 和 Benjamin Bouvier 共同开发的，并得到了 Dan Gohman 的大量早期输入，以及所有优秀的 Cranelift 黑客的帮助。

背景：Cranelift

那么什么是 Cranelift 呢？

该项目是一个用 Rust 编写的编译器框架，专门（但并不完全）为即时编译设计。它是一个通用编译器：它最流行的用例是编译 WebAssembly，尽管存在几个其他前端，例如，cg_clif，它使 Rust 编译器本身能够使用 Cranelift。Mozilla 和其他地方的人们已经开发了几年的编译器。它是 wasmtime 的默认编译器后端，wasmtime 是 WebAssembly 的浏览器外部运行时，它也在其他几个地方用于生产环境。

我们最近切换到在 ARM64 (AArch64) 机器（包括大多数智能手机）上的 nightly Firefox 中启用基于 Cranelift 的 WebAssembly 支持，如果一切顺利，它最终将在稳定的 Firefox 版本中发布。Cranelift 是在字节码联盟的支持下开发的。

在过去的九个月中，我们在 Cranelift 中构建了一个新的框架，用于“机器后端”，或者编译器中支持特定 CPU 指令集的部分。我们还为上面提到的 AArch64 添加了一个新的后端，并根据需要填充功能，直到 Cranelift 准备好用于 Firefox 的生产环境。这篇博文将设置一些上下文并描述后端框架改进的设计过程。

旧后端设计：指令合法化

要了解我们最近在 Cranelift 上所做的工作，我们需要深入到上面的 cranelift_codegen crate 中，并讨论它是如何以前工作的。什么是这个“CLIF”输入，编译器如何将其转换为 CPU 可以执行的机器代码？

Cranelift 使用 CLIF 或 Cranelift IR（中间表示）格式来表示它正在编译的代码。每个执行程序优化的编译器都使用某种形式的中间表示 (IR)：您可以将其视为一个虚拟指令集，它可以表示程序允许执行的所有操作。IR 通常比实际指令集更简单，旨在使用一小组定义明确的指令，以便编译器可以轻松地推断出程序的含义。

IR 也独立于编译器最终目标的 CPU 架构；这使得编译器的大部分（例如从输入编程语言生成 IR 的部分以及优化 IR 的部分）可以在编译器适应新的 CPU 架构时重复使用。CLIF 采用静态单赋值 (SSA) 形式，并使用传统的控制流图，包含基本块（尽管它以前允许扩展基本块，但这些基本块已被逐步淘汰）。与许多 SSA IR 不同，它使用块参数而不是显式 φ 指令来表示 φ 节点。

在 cranelift_codegen 中，在我们改进后端设计之前，程序在整个编译过程中一直保留在 CLIF 中，直到编译器发出最终的机器代码。这似乎与我们刚才说的相矛盾：IR 如何能够机器无关，但同时也是我们发出机器代码的最终形式？

答案是旧的后端是围绕“合法化”和“编码”的概念构建的。从高层次上讲，这个想法是每个Cranelift 指令要么对应于一个机器指令，要么可以被其他Cranelift 指令的序列替换。给定这样的映射，我们可以逐步细化 CLIF，从早期编译阶段的任意机器无关指令开始，进行编辑，直到 CLIF 与机器代码一一对应。让我们可视化这个过程

Figure: legalization by repeated instruction expansion

一个非常简单的 CLIF 指令示例，它具有直接的“编码”到机器指令，是 iadd，它只是将两个整数相加。在几乎所有现代架构上，这都应该映射到一个简单的 ALU 指令，该指令将两个寄存器相加。

另一方面，许多 CLIF 指令不能干净地映射。一些算术指令属于此类：例如，存在一个 CLIF 指令来计算整数二进制表示中设置位的数量 (popcount)；并非每个 CPU 都为此提供单个指令，因此它可能扩展为一系列更长的位操作。

还有一些在更高语义级别定义的操作，这些操作将不可避免地通过扩展降低：例如，对 Wasm 内存的访问被降低为操作，这些操作获取线性内存基址及其大小，将 Wasm 地址与限制进行边界检查，计算 Wasm 地址的实际地址，并执行访问。

那么，要编译一个函数，我们需要遍历 CLIF 并找到没有直接机器编码的指令；对于每个指令，我们只需将其扩展为合法化序列，然后递归地考虑该序列中的指令。我们循环，直到所有指令都有机器编码。在那一点上，我们可以发出与每个指令编码相对应的字节。

成长的烦恼，以及新的后端框架？

传统的 Cranelift 后端设计有很多优点，它使用单个 IR 执行基于扩展的合法化，一直到机器代码的生成。不过，正如预期的那样，它也有一些缺点。让我们讨论一下每个的几个方面。

单个 IR 和合法化：优点

通过在整个过程中对单个 IR 进行操作，相同的优化可以在多个阶段应用。
如果大多数 Cranelift 指令成为一个机器指令，并且很少需要合法化，那么这种方案可能非常快：它只是遍历一次来填充“编码”，这些编码由指向表的较小索引表示。

单个 IR 和合法化：缺点

基于扩展的合法化可能并不总是生成最佳代码。有时单个机器指令可以实现多个 CLIF 指令的行为，即一对多映射。为了生成有效的代码，我们希望能够使用这些指令；基于扩展的合法化做不到。
基于扩展的合法化规则必须遵守指令之间的部分顺序：如果 A 扩展为包括 B 的序列，那么 B 以后不能扩展为 A。这对机器后端作者来说可能会成为一个难以理解的问题。
基于扩展的合法化存在效率问题。在算法级别上，我们希望尽可能避免不动点循环（在本例中为“继续扩展，直到没有更多扩展”）。运行时间是有限的，但该界限有点难以推断，因为它取决于链式扩展的最大深度。允许就地编辑的数据结构也比我们希望的慢得多。通常，编译器将 IR 指令存储在链接列表中，以允许就地编辑。虽然这在渐进意义上与基于数组的解决方案一样快（我们永远不需要执行随机访问），但它在现代 CPU 上的缓存友好性或 ILP 友好性要差得多。我们更希望改为存储指令数组，并在可能的情况下对其进行单次遍历。
随着时间的推移，我们对合法化方案的特定实现变得有点笨拙（例如，参见 GitHub 问题 #1141：用火消灭食谱）。添加新的指令需要学习“食谱”、“编码”和“合法化”，以及仅仅是指令和操作码；更传统的代码降低方法将避免其中大部分复杂性。
单层 IR 存在一个根本性的矛盾：为了使分析和优化能够良好地工作，IR 应该只有一种方式来表示任何特定操作。另一方面，机器级表示应该表示目标 ISA 的所有相关细节。单个 IR 无法在这两个方面都得到很好的满足，随着 CLIF 偏离任何一个方面，就会出现困难。

出于所有这些原因，作为我们 Cranelift 改进的一部分，也是我们新的 AArch64 后端的一个先决条件，我们构建了一个新的机器后端和指令选择框架。该框架允许机器后端定义自己的指令，与 CLIF 分开；我们没有通过扩展进行合法化并运行直到达到不动点，而是定义了一个单一的降低传递；一切都建立在更高效的数据结构之上，仔细地优化了数据上的传递，完全避免了链表。我们现在将描述这种新的设计！

一种新的 IR：VCode

新的 Cranelift 后端的核心思想是添加一个特定于机器的 IR，它具有几个专门为良好表示机器代码而选择的属性。我们将其称为 VCode，它来自“虚拟寄存器代码”，VCode 包含 MachInst，即机器指令。我们做出的关键设计选择是

VCode 是一个线性指令序列。存在控制流信息，允许遍历基本块，但数据结构并非旨在轻松地允许插入或删除指令或重新排序代码。相反，我们通过单次传递降低到 VCode，以最终（或接近最终）顺序生成指令。
VCode不是基于 SSA 的；相反，它的指令对寄存器进行操作。在降低过程中，我们分配虚拟寄存器。在生成 VCode 后，寄存器分配器计算合适的寄存器分配，并就地编辑指令，用真实寄存器替换虚拟寄存器。（两者都打包到一个 32 位表示空间中，使用最高位来区分虚拟寄存器和真实寄存器。）在这个级别上放弃 SSA 使我们能够避免维护其不变性的开销，并且更接近于实际机器。

VCode 指令只是存储在一个数组中，基本块作为数组（指令）索引的范围单独记录。我们设计了这种数据结构来快速迭代，但不是为了编辑。

从 VCode 容器的角度来看，每个指令在很大程度上都是不透明的，只有几个例外：每个指令都公开其（i）寄存器引用和（ii）基本块目标（如果是分支）。寄存器引用被归类为通常的“使用”和“定义”（读和写）。

还要注意，指令可以引用虚拟寄存器（此处表示为 v0..vN）或真实机器寄存器（此处表示为 r0..rN）。这种设计选择允许机器后端在特定指令或 ABI（参数传递约定）要求时使用特定寄存器。

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

enum Inst {
    /// An ALU operation with two register sources and a register destination.
    AluRRR {
        alu_op: ALUOp,
        rd: Writable,
        rn: Reg,
        rm: Reg,
    },

    /// An ALU operation with a register source and an immediate-12 source, and a register
    /// destination.
    AluRRImm12 {
        alu_op: ALUOp,
        rd: Writable,
        rn: Reg,
        imm12: Imm12,
    },

    /// A two-way conditional branch. Contains two targets; at emission time, a conditional
    /// branch instruction followed by an unconditional branch instruction is emitted, but
    /// the emission buffer will usually collapse this to just one branch.
    CondBr {
        taken: BranchTarget,
        not_taken: BranchTarget,
        kind: CondBrKind,
    },

    // ...

这些枚举分支可以被认为类似于旧后端中的“编码”，只是它们是使用类型安全且易于使用的 Rust 数据结构以更直接的方式定义的。

从 CLIF 到 VCode 的降低

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

我们对 CLIF 指令执行单次传递，并且在每个指令处，我们调用机器后端提供的函数将 CLIF 指令降低为 VCode 指令。后端将获得一个“降低上下文”，通过该上下文它可以检查指令和流入它的值，根据需要执行“树匹配”（见下文）。这自然允许 1 对 1、1 对多或多对 1 的转换。我们将引用计数方案纳入此传递，以确保仅在实际使用其值时才生成指令；当出现多对 1 匹配时，这对于消除死代码是必要的。

树匹配

回想一下，旧设计允许从 CLIF 指令到机器指令进行 1 对 1 和 1 对多映射，但不允许多对 1 映射。当涉及到像寻址模式这样的模式匹配时，这尤其成问题，在这种情况下，我们希望识别特定操作的组合并选择一个涵盖所有这些操作的特定指令。

让我们先定义一个以特定 CLIF 指令为根的“树”。对于指令的每个参数，我们可以“向上”查看程序以找到其生成器（定义）。由于 CLIF 采用 SSA 形式，因此指令参数要么是普通值（必须恰好有一个定义），要么是块参数（在传统的 SSA 公式中为 φ 节点），它表示多个可能的定义。我们将说，如果我们到达一个块参数（φ 节点），我们只是在树叶处结束——在树是真实数据流的子集的情况下进行模式匹配是完全可以的（我们可能会得到次优代码，但它仍然是正确的）。例如，给定以下 CLIF 代码：

block0(v0: i64, v1: i64):
  brnz v0, block1(v0)
  jump block1(v1)

block1(v2: i64):
  v3 = iconst.i64 64
  v4 = iadd.i64 v2, v3
  v5 = iadd.i64 v4, v0
  v6 = load.i64 v5
  return v6

让我们考虑加载指令：v6 = load.i64 v5。一个简单的代码生成器可以将其 1 对 1 映射到 CPU 的普通加载指令，使用保存 v5 的寄存器作为地址。这当然会是正确的。但是，我们也许可以做得更好：例如，在 AArch64 上，可用的寻址模式包括一个双寄存器求和 ldr x0, [x1, x2] 或一个带有常量偏移量的寄存器 ldr x0, [x1, #64]。

“操作数树”可以这样绘制

Figure: operand tree for load instruction

我们停止在 v2 和 v0 处，因为它们是块参数；我们不能确定地知道哪个指令将生成这些值。我们可以用常数 64 替换 v3。鉴于这种视图，加载指令的降低过程可以相当容易地选择寻址模式。（在 AArch64 上，进行此选择的代码是此处；在这种情况下，它将选择寄存器 + 常量立即数形式，为 v0 + v2 生成单独的加法指令。）

请注意，我们在降低过程中实际上并没有显式地构建操作数树。相反，机器后端可以查询每个指令输入，并且降低框架将提供一个结构，该结构给出已知的情况下生成的指令、已知的情况下常数值以及在需要的情况下将保存值的寄存器。

后端可以根据需要遍历树向上（通过“生成指令”）。如果它无法将进一步向上树的操作合并到根指令中，它可以简单地使用该点寄存器中的值；始终是安全的（尽管可能是次优的）仅对根指令生成机器指令。

降低指令

鉴于这种匹配策略，那么我们如何真正进行转换呢？基本上，后端提供了一个函数，该函数在操作数树的“根”处针对每个 CLIF 指令调用一次，并且可以生成任意数量的机器指令。该函数本质上只是一个针对根 CLIF 指令的操作码的大型 match 语句，其匹配分支根据需要更深入地查看。

这是一个降低到 AArch64 的整数加法操作匹配分支的简化版本（完整版本是此处）

<span class="k">match</span> <span class="n">op</span> <span class="p">{</span>
<span class="c">    // ...</span>
<span class="nn">    Opcode</span><span class="p">::</span><span class="n">Iadd</span> <span class="k">=></span> <span class="p">{</span>
<span class="k">        let</span> <span class="n">rd</span> <span class="o">=</span> <span class="nf">get_output_reg</span><span class="p">(</span><span class="n">ctx</span><span class="p">,</span> <span class="n">outputs</span><span class="p">[</span><span class="mi">0</span><span class="p">]);</span>
<span class="k">        let</span> <span class="n">rn</span> <span class="o">=</span> <span class="nf">put_input_in_reg</span><span class="p">(</span><span class="n">ctx</span><span class="p">,</span> <span class="n">inputs</span><span class="p">[</span><span class="mi">0</span><span class="p">]);</span>
<span class="k">        let</span> <span class="n">rm</span> <span class="o">=</span> <span class="nf">put_input_in_rse_imm12</span><span class="p">(</span><span class="n">ctx</span><span class="p">,</span> <span class="n">inputs</span><span class="p">[</span><span class="mi">1</span><span class="p">]);</span>
<span class="k">        let</span> <span class="n">alu_op</span> <span class="o">=</span> <span class="nf">choose_32_64</span><span class="p">(</span><span class="n">ty</span><span class="p">,</span> <span class="nn">ALUOp</span><span class="p">::</span><span class="n">Add32</span><span class="p">,</span> <span class="nn">ALUOp</span><span class="p">::</span><span class="n">Add64</span><span class="p">);</span>
<span class="n">        ctx</span><span class="nf">.emit</span><span class="p">(</span><span class="nf">alu_inst_imm12</span><span class="p">(</span><span class="n">alu_op</span><span class="p">,</span> <span class="n">rd</span><span class="p">,</span> <span class="n">rn</span><span class="p">,</span> <span class="n">rm</span><span class="p">));</span>
<span class="p">    }</span>
<span class="c">    // ...</span>
<span class="p">}</span>

这里在几个辅助函数中发生了一些魔法。put_input_in_reg() 调用 ctx 上的适当方法来查找保存输入值的寄存器。put_input_in_rse_imm12() 更有趣：它返回一个 ResultRSEImm12，它是一个“寄存器、移位寄存器、扩展寄存器或 12 位立即数”。这组选择包含了我们在 AArch64 上对加法指令的第二个参数的所有选项。

辅助函数查看操作数树中的节点，并尝试匹配移位运算符或零/符号扩展运算符，这些运算符可以直接合并到加法中。它还会检查操作数是否为常数，如果是，则可以适合 12 位立即数字段。如果不是，它会回退到简单地使用寄存器输入。alu_inst_imm12() 然后分解此枚举并选择适当的 Inst 分支（分别是 AluRRR、AluRRRShift、AluRRRExtend 或 AluRRImm12）。

就是这样！无需进行合法化和重复的代码编辑来匹配多个操作并生成机器指令。我们发现这种编写降低逻辑的方式非常简单直观。

具有使用计数的向后传递

既然我们可以降低单个指令，我们如何降低具有许多指令的函数体？这不像循环遍历指令并调用上面描述的操作码匹配函数那样简单（尽管这实际上会起作用）。特别是，我们希望更有效地处理多对 1 的情况。考虑当上面的加法指令逻辑能够合并，例如，左移运算符到加法指令中时会发生什么。

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

我们实现了一种引用计数来解决这个问题。特别是，我们跟踪任何给定的 SSA 值是否实际上被使用，并且我们只为 CLIF 指令生成代码，如果它的任何结果被使用（或者如果它具有必须发生的副作用）。这是一种死代码消除形式，但它被集成到单一的降低传递中。

为了使此方法起作用，我们必须在定义之前查看使用情况。因此，我们“向后”迭代函数体。具体来说，我们以后序进行迭代；这样，所有指令都将在支配它们的指令之前被查看，因此给定 SSA 形式，我们会在定义之前查看使用情况。

示例

让我们看看这在现实生活中是如何工作的！考虑以下 CLIF 代码

function %f25(i32, i32) -> i32 {
block0(v0: i32, v1: i32):
  v2 = iconst.i32 21
  v3 = ishl.i32 v0, v2
  v4 = isub.i32 v1, v3
  return v4
}

我们预计左移（ishl）操作应该在 AArch64 上合并到减法操作中，使用 ALU 指令的 reg-reg-shift 形式，实际上确实发生了这种情况（这里我显示了使用 RUST_LOG=debug 运行 clif-util compile -d --target aarch64 时可以看到的调试转储格式）

VCode {
  Entry block: 0
Block 0:
  (original IR block: block0)
  (instruction range: 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
}

然后它通过寄存器分配器，附加了序言和尾声（在我们知道哪些寄存器被覆盖之前，我们无法生成它们），消除了冗余移动，并变为

stp fp, lr, [sp, #-16]!
mov fp, sp
sub w0, w1, w0, LSL 21
mov sp, fp
ldp fp, lr, [sp], #16
ret

这是一个完全有效的函数，在 AArch64 上是正确的并且可以从 C 调用！（如果我们知道这是一个叶函数，并且避免了堆栈帧的设置和拆卸，我们可以做得更好！遗憾的是，许多优化机会仍然存在。）

在本文中，我们只触及了 Cranelift 设计的表面。但是，我希望本文能让大家了解到今天编译器领域中正在进行的令人兴奋的工作！

本文是一个缩减版本；更多技术细节，请参阅完整版本。

感谢 Julian Seward 和 Benjamin Bouvier 的审阅，并提出了一些补充和修改建议。

更多 Chris Fallin 的文章…

Hacks

由 Chris Fallin

背景：Cranelift

旧后端设计：指令合法化

成长的烦恼，以及新的后端框架？

单个 IR 和合法化：优点

单个 IR 和合法化：缺点

一种新的 IR：VCode

从 CLIF 到 VCode 的降低

树匹配

降低指令

具有使用计数的向后传递

示例

关于 Chris Fallin

Cranelift 的新后端，第一部分：指令选择

由 Chris Fallin

背景：Cranelift

旧后端设计：指令合法化

成长的烦恼，以及新的后端框架？

单个 IR 和合法化：优点

单个 IR 和合法化：缺点

一种新的 IR：VCode

从 CLIF 到 VCode 的降低

树匹配

降低指令

具有使用计数的向后传递

示例

关于 Chris Fallin

发现 Web 开发的优秀资源

谢谢！请检查您的收件箱以确认您的订阅。