当前位置：首页 > news >正文

2026 年 ZJIT 引入新寄存器分配器：全局分配优势大，方法内联正推进！

news 2026/5/30 23:08:40

什么是寄存器分配器？

编译器生成机器码时，要决定将值存放在何处，这些值通常以函数中的变量形式存在，编译器也会计算中间值。CPU 计算输出时，需要知道如何找到该值。CPU 通常基于寄存器中的输入计算输出，有些架构（如 x86）允许对存储在内存中的值进行计算，但读写寄存器的速度比内存快得多，所以编译器应尽量将值保留在寄存器中。程序中的特定函数可能有大量变量，但可用寄存器数量有限，且因架构而异。这时寄存器分配器就发挥作用了，它会查看所有变量，确定应放入哪些寄存器，若寄存器不足，还会将变量“溢出”到内存中。

它是如何工作的？

寄存器分配有几种广为人知的方法，每种在编译时间和代码质量之间都有不同权衡。对于 ZJIT，选择实现一个基于 [Christian Wimmer 题为“SSA 形式的线性扫描寄存器分配”的论文](https://bernsteinbear.com/assets/img/wimmer-linear-scan-ssa.pdf)简化版本的线性扫描寄存器分配器。这篇论文不长，建议有时间读一读！另外，Max Bernstein [也写了一篇博客文章对该论文进行了剖析](https://bernsteinbear.com/blog/linear-scan/)。

ZJIT 在其后端使用 [静态单赋值形式](https://en.wikipedia.org/wiki/Static_single-assignment_form)（SSA 形式），“SSA 形式”是一种代码表示方式，只允许对变量进行一次赋值。例如这段 Ruby 代码：ruby a = 123 a += 1 a在后端低级中间表示（“LIR”）中会类似这样表示：v1 = Const(123) v2 = Const(1) v3 = Add v1, v2 CRet v3在上述伪代码（与后端使用的 IR 并不完全相同，但非常接近）中，`v1`、`v2` 和 `v3` 都是不同的变量，不允许像对应的 Ruby 代码那样对变量进行重新赋值。生成的中间表示与 Ruby 代码具有完全相同的语义，但增加了变量只能写入一次的限制。ZJIT 生成 Ruby 代码的中间表示时，会将所有变量转换为这些数字形式的 SSA 变量，也会为临时值使用 SSA 变量。在上面的示例转换中，可以认为 `v1` 等同于 `a`，`v2` 是值为 1 的临时变量，`v3` 是 `a` 加上 `v2` 后的“新版本”。变量可以写入一次，但可以多次读取。将变量写入的位置称为“定义”，将变量读取的位置称为“使用”。

生命周期

寄存器分配器首先要了解每个值何时处于活动状态以及持续多长时间，这段持续时间称为“生命周期”或“存活范围”。值的生命周期从其定义点开始，到其最后一次使用的位置结束。如果两个值的生命周期重叠，它们就不能共享同一个寄存器。如果重叠的生命周期数量超过寄存器数量，就需要将一个值溢出到内存中。由于这些范围指的是变量的“生命周期”，所以通常会说变量在其定义处“诞生”，在其最后使用处“死亡”。

看一个例子，考虑这个已经是 SSA 形式的 Ruby 方法：ruby def add_twice(a, b, c) d = a + b e = d + c e end每个值的生命周期如下：# 指令 | a | b | c | d | e -------------------+-----+-----+-----+-----+---- 1 d = a + b | x | x | . | . | 2 e = d + c | | | x | x | . 3 return e | | | | | x`.` 字符表示变量在该指令处处于活动状态，`x` 字符表示变量在该指令处“死亡”，但仍被使用。也可以将这些生命周期表示为范围，每个值的存活范围是 `[定义, 最后使用]`：a: [0, 1] b: [0, 1] c: [0, 2] d: [1, 2] e: [2, 3]其中指令 0 表示函数入口（参数定义）。参数 `a`、`b` 和 `c` 在指令 1 处都处于活动状态，因为它们在方法体之前就已定义。`a` 和 `b` 在指令 1 处最后被使用，之后就“死亡”了。`c` 在指令 2 之前一直处于活动状态，因为那是它最后被使用的地方。`d` 在指令 1 处定义，在指令 2 处最后被使用，所以在这两个指令处都处于活动状态。`e` 在指令 2 处定义，在指令 3 处最后被使用。在指令 1 处，`a` 和 `b` “死亡”，`d` “诞生”。由于知道 `a` 和 `b` 不会再被使用，所以可以将它们的一个寄存器重新用于 `d`。因此，在指令 1 处只需要三个寄存器：分别用于 `a`/`d`、`b` 和 `c`。同样，在指令 2 处，`c` 和 `d` “死亡”，`e` “诞生”，所以可以再次重用一个寄存器。

计算生命周期需要对控制流图进行反向数据流分析，按逆序遍历指令，跟踪当前哪些值处于活动状态。当看到一个值的定义或使用时，就知道它在该指令处处于活动状态。ZJIT 有一个调试选项，可以输出这样的存活范围图：$ ruby --zjit-call-threshold=2 --zjit-dump-lir=live_intervals ../test.rb以下是一个较大函数中许多基本块的摘录，展示了一个基本块的输出图示例：v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 --- --- --- --- --- --- --- --- --- --- --- --- i0 : . . . . . . . . . . . . FrameSetup i2 : v . . . . . . . . . . . v0 = Load [x21 - 0x28] i4 : █ v . . . . . . . . . . v1 = Load [x21 - 0x20] i6 : █ █ . . . . . . . . . . Jmp bb3_l2([x19 + 0x18], v0, v1)如前所述，在 ZJIT 中，SSA 变量名只是数字。在上面的块中，有 12 个编号从 0 到 11 的变量，这些变量列在图顶部的第一行，编号为 `v0` 到 `v11`。第一列列出了指令编号，在这种情况下，有 4 条指令（`i0` 到 `i6`），出于本文范围之外的原因，它们被编号为偶数。图的最后一列列出了实际的 LIR 指令，不会详细解释这些指令的具体含义，但可以看到，有些指令定义了变量（如 `i2` 和 `i4` 定义了 `v0` 和 `v1`），有些指令使用了变量（如 `i6` 使用了 `v0` 和 `v1`）。在图表中间，`v` 字符表示变量何时“诞生”，实心块表示变量“存活”，`^` 字符表示最后使用（不过在这个例子中没有“最后使用”）。

冲突图

知道所有值的生命周期后，需要确定有多少范围重叠以及在哪里重叠。一种方法是构建一个“冲突图”，冲突图是一种简单的图数据结构，图中的每个节点代表一个存活范围，图中的每条边代表与另一个存活范围的“重叠”或“冲突”。有了冲突图后，可以将分配问题视为一个 [图着色问题](https://en.wikipedia.org/wiki/Graph_coloring)，其中每种颜色代表该 CPU 上可用的一个物理寄存器。如果有 _k_ 个物理寄存器，就需要对冲突图进行有效的 _k_ 着色。一般情况下，这是一个 NP 完全问题，但启发式方法可以帮助简化问题。虽然图着色能产生很好的结果，但构建和操作冲突图在时间和内存方面都可能很昂贵，尤其是对于大型函数。JIT 编译器需要快速，所以选择了另一种算法：线性扫描。

线性扫描

使用的是基于 [Christian Wimmer 的论文](https://bernsteinbear.com/assets/img/wimmer-linear-scan-ssa.pdf)的线性扫描寄存器分配器。该算法相当简单，计算出存活范围后，按顺序遍历这些存活范围。当到达一个存活范围开始的指令时，从寄存器池中“取出”一个空闲寄存器，并将该寄存器分配给该存活范围。当到达一个存活范围结束的指令时，将该寄存器放回池中。如果在某个时刻，寄存器池中的寄存器用完了，就将新的存活范围或现有的存活范围溢出到内存中。

局部分配与全局分配

到目前为止讨论的技术，如生命周期、冲突图和线性扫描，都可以在不同的作用域中应用。在寄存器分配器领域，有两种主要类型，它们的区别在于如何处理程序的控制流图。第一种是“局部”寄存器分配器，每个函数被分解为多个基本块，程序控制流通过这些块，局部寄存器分配器一次只能“看到”一个基本块。第二种分配器是“全局”寄存器分配器，全局寄存器分配器会一次性处理函数的整个图。这里的“全局”并不是指程序中的“全局变量”，而是指它一次性分析整个函数，而不是一个基本块。

ZJIT 之前的寄存器分配器是从 YJIT 继承而来的局部分配器，它只跟踪单个基本块内的生命周期。这意味着在每个块边界处，所有活动值都必须移动到已知位置（如栈或固定寄存器），以便下一个块可以获取它们。对于像 YJIT 这样非常“懒惰”的逐块编译器来说，这是一个合理的权衡。YJIT 一次编译一个基本块，所以它无论如何都无法获得函数的完整信息。使用 YJIT 的分配器帮助快速启动了 ZJIT。但 ZJIT 会编译整个方法，所以有足够的信息来做得更好。

全局分配器可以让变量在块边界处保持在同一个寄存器中。如果一个值在一个块中定义，在后面的块中使用，分配器可以让它的存活范围跨越两个块，并为整个持续时间分配一个寄存器。这避免了在块边界处进行不必要的存储和加载，这在紧密循环中会有很大的不同。全局分配器还开启了一些使用局部分配器难以或无法实现的功能。例如，在各种优化过程中拆分和添加新的基本块非常棘手，因为需要跟踪变量的位置。现在可以轻松操作基本块，而不必担心哪些块使用了哪些变量。这也是方法内联的先决条件，内联被调用者的代码会成为调用者控制流图的一部分，其值需要参与相同的分配。

目前的进展

新的寄存器分配器 [已经合并](https://github.com/ruby/ruby/pull/16295)，并且运行良好，现在正在在此基础上进行开发！方法内联 [正在积极进行中](https://github.com/ruby/ruby/pull/16966)，并且严重依赖现在拥有的全局分配。

分配器本身仍有改进的空间，一个重要的方面是生命周期空洞。目前，一个值的存活范围是从其定义到最后使用的单个连续区间，但实际上，一个值在其范围中间可能是“死亡”的。例如，如果一个值在 `if` 语句的一个分支中使用，而在另一个分支中不使用，寄存器分配器可能会意外地让该值在一个分支中“存活”。这可能会成为一个问题，因为该值最终会占用宝贵的资源（物理寄存器），而这些资源应该用于当时实际存活的值。下面的 Ruby 程序大致展示了这个问题：ruby def example(cond, a, b) x = a + b if cond y = a * 2 use(y) else use(x) end end根据代码的线性化方式，即使可以清楚地看到 `x` 在 `if` 语句的真分支中未被使用，它也可能被认为是“存活”的。换句话说，分配给值 `x` 的寄存器将在真分支中被保留，即使它实际上并未被使用。表示这些空洞可以让在这些间隙中更积极地重用寄存器，减少溢出。

对这个基础感到兴奋，并期待在此基础上继续发展！