什么是寄存器分配器编译器生成机器码时要决定将值存放在何处这些值通常以函数中的变量形式存在编译器也会计算中间值。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 等同于 av2 是值为 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-threshold2 --zjit-dump-lirlive_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 的寄存器将在真分支中被保留即使它实际上并未被使用。表示这些空洞可以让在这些间隙中更积极地重用寄存器减少溢出。对这个基础感到兴奋并期待在此基础上继续发展Shopify 工程Shopify 的 Ruby 和 Rails 基础设施团队致力于确保 Ruby 和 Rails 成为可持续使用 100 年的工具继续成为首选的工具链。