开发者分享为 purple-garden 语言实现寄存器分配的活跃性分析

为活跃性分析而作的颂歌；从 SSA 到寄存器

或者是一封情书？读这篇文章时请听着《欢乐颂》，也看看我专门为这篇文章画的超棒的像素画： 我目前正在为我的基于寄存器的字节码虚拟机和 x86 即时编译器做寄存器分配，两者都是为我的编程语言 purple-garden 服务的。 寄存器分配就是把数量无限的虚拟寄存器分配到硬件有限的存储资源上，具体来说就是 gprs（通用寄存器）、fprs（浮点寄存器）和栈（参见 CPU Registers x86 了解一个示例概览）。这出颂歌的第一步是活跃性分析。 最简单、但又有点不那么平凡的例子是： 1fn f(a:Int n:Int acc:Int) Int { 2 match { 3 n < 1 { a + acc } 4 { f(a n-1 acc*n) } 5 } 6} 这等价于下面这段 c 代码，我是从 Max Bernstein1 那篇写得很好的《Linear scan register allocation on SSA》文章中“反汇编”出来的，当时我并没真正看懂里面的 IR 展示，于是先把它翻译成 c，再翻译成我自己的语言（purple garden 没有循环 🤓，所以只有在以 f(a n 1) 调用时才等价）： 1long f(long a, long n) { 2 long acc = 1; 3 while (n >= 1) { 4 acc = acc * n; 5 n = n - 1; 6 } 7 return a + acc; 8} 把 f(a,n,acc: Int): Int 输入 purple garden 的流水线，会生成下面这个优化后的中间表示（使用 -I），这意味着有些值是死值，因而被删除了2： 1fn f1(%v0:Int, %v1:Int, %v2:Int) -> Int { 2 b0(%v0, %v1, %v2): 3 %v4:Bool = ILt %v1, 1 4 br %v4, b1(%v0, %v1, %v2), b2(%v0, %v1, %v2) 5 b1(%v5, %v6, %v7): 6 %v8:Int = IAdd %v5, %v7 7 ret %v8 8 b2(%v9, %v10, %v11): 9 %v13:Int = ISub %v10, 1 10 %v14:Int = IMul %v11, %v10 11 tail f1(%v9, %v13, %v14) 12} purple garden 的 IR 结构与记法 purple garden 的中间表示基于静态单赋值（SSA）形式， 意味着每个值 / 虚拟寄存器都恰好被赋值一次，且全部不可变。它们记作 %vN，代表 virtual register 或 value，随你（读者）喜欢。 与许多其他 ssa ir 相比，pgir 不使用 phi 节点。我改为选择了块参数和终止符。它由块组成，每个块有一个参数列表、一个终止符和一组指令体，其中每条指令都处于 ssa 形式。所有值都是块局部的，块间唯一的数据流通过块参数和块终止符来实现。 1; 块的 id 为 N 2; | 3; v 4 b2(%v0, %v1, %v2): 5; ^^^^^^^^^^^^^ 参数 0..2 6 7; 值 / 虚拟寄存器定义 8; | 指令种类 9; | | 10; v v 11 %v7:Int = ISub %v1, 1 ; <-- 立即数 12; ^ ^ 参数 13; | 14; 指令结果类型 15 16; 带参数的终止符 17 tail f1(%v0, %v7, %v8) 或者用 rust 的写法： 1pub struct Block<'b, A: Allocator = Global> { 2 pub id: Id, 3 pub instructions: Vec<Instr<'b>, A>, 4 pub params: ParamsId, 5 pub term: Option<Terminator>, 6 // [...] 7} 8 9pub enum Instr<'i> { 10 BinImm { 11 op: BinOp, 12 dst: TypeId<'i>, 13 lhs: Id, 14 imm: i32, 15 }, 16 // [...] 17 Noop, 18} 19 20pub enum Terminator { 21 Return { 22 value: Option<Id>, 23 }, 24 // [...] 25 Tail { 26 func: Id, 27 args: ParamsId, 28 }, 29 // [...] 30} 很简单，对吧？ 让我们看看之前的 IR 示例，不过这次带上虚拟寄存器的生命周期标注（当 cli 以 -II 调用时）： 1fn f1(%v0:Int, %v1:Int, %v2:Int) -> Int { %v0 %v1 %v2 %v4 %v5 %v7 %v8 %v9 %v10 %v11 %v13 %v14 2 b0(%v0, %v1, %v2): | | | 3 %v4:Bool = ILt %v1, 1 | | | | 4 br %v4, b1(%v0, %v1, %v2), b2(%v0, %v1, %v2) | | | | 5 b1(%v5, %v6, %v7): | | 6 %v8:Int = IAdd %v5, %v7 | | | 7 ret %v8 | 8 b2(%v9, %v10, %v11): | | | 9 %v13:Int = ISub %v10, 1 | | | | 10 %v14:Int = IMul %v11, %v10 | | | | | 11 tail f1(%v9, %v13, %v14) | | | 12} 这个展示能让每个值的存活期在视觉上变得直观，用 lo 编码起点，用 hi 编码终点，下面这种展示则让理解不用靠视觉：（位置是线性化的：块参数位于块的基址，块指令位于块基址+1+指令位置，终止符位于块基址+指令数+1） 把这些撇开之后，算法就归结为一个简单的： 1/// 观察器 Id := (lo,hi)，总是更新 lo，只有当 hi 之前未设置时才填充 hi 2fn observe<V: Allocator>(out: &mut Vec<(u32, u32), V>, id: Id, pos: u32) { 3 let idx = id.0 as usize; 4 let e = &mut out[idx]; 5 if e.1 == 0 { 6 e.1 = pos; 7 } 8 e.0 = pos; 9} 用来帮助处理定义和使用的辅助函数： 查询指令和终止符中的定义与使用： 顾名思义，Func::def_of 返回一个虚拟寄存器的定义，如果该指令有定义的话： 1impl Func<'> { 2 #[must_use] 3 pub fn def_of(instr: &Instr<'>) -> Option<Id> { 4 match instr { 5 Instr::Alloc { dst, .. } 6 | Instr::Load { dst, .. } 7 | Instr::AddrOf { dst, .. } 8 | Instr::Bin { dst, .. } 9 | Instr::BinImm { dst, .. } 10 | Instr::LoadConst { dst, .. } 11 | Instr::Call { dst, .. } 12 | Instr::Sys { dst, .. } 13 | Instr::Cast { dst, .. } 14 | Instr::Lookup { dst, .. } 15 | Instr::Assert { dst, .. } => Some(dst.id), 16 Instr::Store { .. } | Instr::Noop => None, 17 } 18 } 19} 对指令中值的每次使用调用 f 顾名思义，对指令中值的每次使用调用 f 1pub fn for_each_use_of_instr(&self, instr: &Instr<'_>, mut f: impl FnMut(Id)) { 2 match instr { 3 Instr::Bin { lhs, rhs, .. } => { 4 f(*lhs); 5 f(*rhs); 6 } 7 Instr::BinImm { lhs, .. } => f(*lhs), 8 Instr::Call { args, .. } | Instr::Sys { args, .. } => { 9 for &a in self.params(*args) { 10 f(a); 11 } 12 } 13 Instr::Cast { from, .. } => f(from.id), 14 Instr::Lookup { subject, .. } => f(*subject), 15 Instr::Store { src, base, .. } => { 16 f(*src); 17 f(*base); 18 } 19 Instr::Assert { cond, .. } => f(*cond), 20 Instr::Load { base, .. } | Instr::AddrOf { base, .. } => f(*base), 21 Instr::LoadConst { .. } | Instr::Noop | Instr::Alloc { .. } => {} 22 } 23} 对终止符中值的每次使用调用 f

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）