assembly编译器性能

老鼠的寄存器分配器

一个小型寄存器分配器的逐步讲解，从活跃区间和冲突到固定寄存器与溢出。该设计更注重清晰性而非吞吐量，意在作为一份配方来阅读，而不是一个库。

hexrathexrat10 分钟阅读

中文
中文日本語
复制

2026 年 10 月 7 日

rat 是我写的一个小型编译器后端（附带一个半可用的 C99 前端）。它的 x86-64 代码生成器把中间表示（IR）翻译成 x86-64 指令。这些指令使用数量不限的虚拟寄存器（vreg）。寄存器分配器负责把每个 vreg 映射到物理寄存器：通用寄存器（可用 12 个）或 xmm 寄存器（Linux 上 14 个 1）。没有空闲寄存器时，就把它映射到栈槽。

很长一段时间里，rat 用的是线性扫描分配器，按程序顺序遍历活跃区间。它能用，但靠一次次打补丁长大，最后到了 1392 行。于是我测了测其中哪些部分真正有用，把其余的扔掉，用 584 行写了一个优先级装箱分配器。它按重要程度遍历活跃区间，把每个区间放进第一个装得下它的寄存器。它和 LLVM 的贪心分配器属于同一类，只是砍掉了大部分难点，而且生成的代码更好。

一个值从被写入的地方到被最后读取的地方之间是活跃的。两个值只有在活跃期不重叠时才能共用同一个寄存器。

某个点上活跃的值太多时，有些就得放进内存：它们被溢出了。一次溢出要付出一条 store 和一条 load 的代价。最优分配是 NP-hard 的 2，所以所有实用的分配器都用启发式方法。

调用约定又加了两条规则。函数调用可以覆盖调用者保存的寄存器（Linux 上是 rax rcx rdx rsi rdi r8-r11 和所有 xmm 寄存器）。函数返回前必须恢复被调用者保存的寄存器（rbx rbp r12-r15）。举个例子，下面这个函数要让 y 在调用前后保持活跃：

long g(long);
long h(long x, long y) {
	long t = g(x);
	return t + y;
}

分配之前，rdi、rsi 和 rax 由调用约定固定，v1-v4 是 vreg：

0  v1 = copy rdi      ; x
1  v2 = copy rsi      ; y
2  rdi = copy v1      ; argument of g
3  call g             ; clobbers caller-saved
4  v3 = copy rax      ; t
5  v4 = copy v3
6  v4 = add v4, v2
7  rax = copy v4
8  ret

x86 的 add 会覆盖它的第一个操作数（双地址），所以指令 5 先复制 t。在 -O1 下分配之后：

push rbp
mov  rbp, rsp
sub  rsp, 0x8
push rbx              ; rbx is callee-saved: save it
mov  rbx, rsi         ; y
call g                ; x is already in rdi
add  rax, rbx         ; t stays in rax
pop  rbx
leave
ret

六次复制里有五次消失了，y 进了被调用者保存的寄存器。分配器里没有任何代码写着“把跨调用的值放进被调用者保存的寄存器”。这是设计自然带出来的结果，也是我最喜欢的一点。

五个步骤

分配器对每个函数执行五个步骤：

  1. 活跃区间：给指令编号，找出每个 vreg 在哪些位置活跃。
  2. 固定寄存器：标出代码直接使用物理寄存器的位置。
  3. 合并：把由一条复制指令连接的 vreg 并成一组（一个 bundle3），这样复制指令就能消失。
  4. 分配寄存器：给每个 bundle 分配一个寄存器，最重要的先分。
  5. 溢出：给没分到寄存器的 bundle 分配栈槽，然后重写代码。

每个 bundle 在其整个生命周期内始终持有自己的寄存器或栈槽。分配器从不：

  • 从 bundle 手里收回寄存器（没有驱逐）
  • 把一个区间拆分到寄存器和内存两边
  • 把某个步骤跑两遍

正是这些部分让真正的分配器变得庞大。我的测量表明 rat 在这方面的缺失影响不大。

活跃区间

槽位

指令 i 有两个槽位：它在 2i 读取操作数，在 2i+1 写入结果。活跃区间是一串排好序的 [start, end] 槽位段。

源操作数在哪里结束取决于指令：

  • 复制指令： 源在读取槽位结束，目标在写入槽位开始。在指令 2 中，rdi = copy v1，v1 在槽位 4 结束，rdi 在槽位 5 开始。两者不重叠，因此可以共用同一个寄存器，复制指令变成空操作。
  • 其他指令： 源操作数一直活跃到写入槽位，这样结果永远不会覆盖另一个操作数。v2 由指令 1 写入，最后一次被指令 6 的 add 读取，因此它活跃于 [3, 13]。

活跃出口集合

rat 找出每个基本块活跃出口（live-out）的 vreg：后面的基本块仍可能读取它们。许多编译器用每块一个位集加不动点循环来做这件事。rat 则一次处理一个 vreg：

  1. 如果某个基本块在写入该 vreg 之前读取它，那么该 vreg 在这个块的入口是活跃的。
  2. 从每个这样的块出发，一个工作表沿前驱回溯，把该 vreg 标记为在每个前驱的活跃出口。
  3. 回溯在定义该 vreg 的块处停止。

vreg 的存活成本取决于它活跃的块，而不是 blocks * vregs。4

段与权重

接着 rat 从每个块的 live-out 集合出发反向遍历，切出段。同一次遍历还会为每个 vreg 累加一个权重：它的溢出代价。

每个 def 和每个 use 都加上 3d，其中 d 是循环深度（最大到 11）：

def 或 use 所在位置加值
直线代码1
一层循环3
两层嵌套循环9

空洞

一个 live range 可以有空洞，也就是 vreg 已死的间隙。块按代码顺序编号，所以跳过一个块的 range 在那里就有一个空洞：

long f(long* a, long n) {
	for(long i = 0; i < n; ++i)
		if(a[i] < 0)
			a[i] = 0;
	return n * 3;
}

exit 块夹在循环块之间：

mov  eax, 0x0         ; offset 8*i, rax in the loop
cmp  rdx, rdi
jl   loop
exit:
lea  rax, [rdi+rdi*2] ; n*3 in the hole of rax
ret
loop:
mov  rcx, r8
add  rcx, rax
...
add  rax, 0x8
cmp  rdx, rdi
jl   loop
jmp  exit

rax 里的偏移量在 exit 块中是死的，所以 n*3（一个 lea）可以用 rax，而它同时也是返回寄存器。这是块顺序白送的好处。

固定寄存器

rat 把自己的寄存器编号为 1 到 40，所以一个 U64 就能装下一组寄存器。每个槽位对应一个掩码 busy[slot]。某位被置上，表示该寄存器在那个槽位被占用。

同一次反向遍历还会标出代码直接使用的物理寄存器：

用途寄存器占用区间
传入参数参数寄存器直到读取它的那次拷贝
调用参数参数寄存器从设置它的那次拷贝到调用
调用所有 caller-saved调用的两个槽位
返回值rax从调用到读取它的那次拷贝
除法rax rcx rdx读 rax rcx，写 rax rdx

h 的掩码与 range：

instr   0  1  2  3  4  5  6  7  8
slot    rw rw rw rw rw rw rw rw rw
rdi     #. .. .#### .. .. .. .. ..
rsi     ####. .. ## .. .. .. .. ..
rax     .. .. .. ####. .. .. .####
others  .. .. .. ## .. .. .. .. ..
v1 x    .======. .. .. .. .. .. ..
v2 y    .. .================ .. ..
v3+v4 t .. .. .. .. .=========. ..

r 和 w 分别是读槽位和写槽位。# 被占用，= 是一个 live range，. 空闲。竖线会跨过指令之间的间隙延续下去。"others" 指其余所有 caller-saved 寄存器。

当一个 bundle 拿到寄存器时，rat 会在它 live range 的每个槽位里置上该寄存器对应的位。此后，vreg 和固定寄存器就是同一批掩码里的位。每 64 个槽位还有一份汇总掩码，即这 64 个掩码的 OR，这样一个很长的 range 就能一次跳过 64 个槽位。

合并

同一类别两个 vreg 之间的拷贝是合并的候选。这些拷贝来自：

  • 二地址指令
  • phi 节点：在汇合点来自不同基本块的值

如果两个活跃区间不重叠，对应的 vreg 就合并成一个 bundle，它拥有合并后的片段和累加后的权重。rat 会删除同一个 bundle 内部的复制。在 h 中，v3 是 [9, 10]，而 v4 是 [11, 14]，所以它们合并。

  • rat 按循环深度对复制排序，最深的排在最前。热复制先合并，免得被冷复制挡住。
  • bundle 用并查集维护。
  • 合并前先遍历两个片段列表检查是否重叠。如果两个 bundle 加起来超过 256 个片段，rat 就跳过这次合并。

vreg 与物理寄存器之间的复制则改为设置一个 hint：如果那个寄存器空闲，bundle 就优先选它。

选择寄存器

每个 bundle 有一个优先级：

priority = weight / sqrt(length in slots)
  • 短而热的区间排前面：它们最重要，也最好安排。
  • 长而冷的区间排后面，会被溢出到栈上。
  • sqrt 让循环计数器这类长区间不至于损失太多优先级。

rat 按优先级顺序对每个 bundle 调用 pick：

// cls: register class, gp or xmm
PhysReg pick(VReg v) {
	U64 blocked = ~allocatable[cls];
	for(auto [start, end] : segs[v])
		for(I32 s = start; s <= end; ++s)
			blocked |= busy[s]; // or 64 at a time
	if(hint[v] != kNoReg && !(blocked >> hint[v] & 1))
		return hint[v];
	// caller-saved first, callee-saved last
	return firstFree(order[cls], blocked);
}

在 h 中选择

bundlehint得到
v1rdirdi
v3+v4raxrax
v2rsirbx

图中 rdi 只在 v1 前后忙，所以 v1 拿到了它。两个复制都变成 mov rdi, rdi，窥孔优化会在分配之后把它们删掉。

v2 跨越了调用。调用槽位里所有 caller-saved 寄存器都忙，所以第一个空闲寄存器是 rbx，也就是第一个 callee-saved 寄存器。序言只保存 rat 用到的 callee-saved 寄存器。

在 Linux 上，没有 xmm 寄存器是 callee-saved 的，所以跨越调用的浮点值总是走栈。

溢出

找不到空闲寄存器的 bundle 会在整个生命周期内被溢出。接下来：

  1. rat 按起始位置对溢出的 bundle 排序。如果栈槽里最后一个 bundle 已经结束，就复用它。
  2. rat 重写代码。bundle 拿到寄存器的 vreg 就替换成那个寄存器。
  3. 每条指令之前，rat 把每个溢出的操作数加载到临时寄存器；指令之后，再把每个溢出的结果存回去。

临时寄存器是 r10 或 r11（浮点则是 xmm14 或 xmm15）。任何 bundle 都拿不到它们。如果两个都被占用，rat 就取该指令处第一个空闲的寄存器。

有两种情况不需要临时寄存器。寄存器与已溢出的 bundle 之间的复制，直接变成 load 或 store 本身。调用读取已溢出的栈参数时，直接从它的栈槽读。

在 p 中，同时有 14 个值活跃：

void p(long* a) {
	long x0 = a[0], x1 = a[1], ..., x13 = a[13];
	a[0] = x0 * x13; a[1] = x1 * x12; a[2] = x2 * x11;
	a[3] = x3 * x10; a[4] = x4 * x9;  a[5] = x5 * x8;
	a[6] = x6 * x7;
}

16 个寄存器减去 rsp、rbp、r10、r11 和 rdi（它持有 a），剩下 11 个给 14 个值。x0-x6 还持有乘积（二地址 imul），所以它们的使用更多。x7-x13 中，区间最长的三个进栈。

peephole 处理之前：

mov  r12, [rdi+0x30]  ; x6, in a register
mov  r10, [rdi+0x38]  ; x7, spilled
mov  [rbp-0x8], r10
mov  r10, [rdi+0x40]  ; x8, spilled
mov  [rbp-0x10], r10
mov  r10, [rdi+0x48]  ; x9, spilled
mov  [rbp-0x18], r10
...
mov  r10, [rbp-0x18]  ; reload x9
imul r9, r10
mov  r10, [rbp-0x10]  ; reload x8
imul rbx, r10
mov  r10, [rbp-0x8]   ; reload x7
imul r12, r10

从 x9 的 store 到它的 reload 之间，没有指令写 r10。于是 peephole 处理删掉了 reload。之后没有东西读那个栈槽，所以它把 store 也删了。

它可能很蠢

没有驱逐，早期的决定就是最终决定。下面这个例子最让我恼火：

long sum(long* a, long n) {
	long s = 0;
	for(long i = 0; i < n; ++i)
		s += a[i];
	return s;
}

rat 把它编译成：

mov  r9, rdi          ; a: rdi was taken by a[i]
mov  r8, rsi          ; n: rsi was taken by s
...
exit:
mov  rax, rsi         ; s: rax was taken by a+8*i
ret
loop:
mov  rax, r9
add  rax, rcx         ; rax = a + 8*i
mov  rdi, [rax]       ; rdi = a[i]
add  rsi, rdi
...

循环里的值区间短且热，所以先分配：

  1. 地址 a+8*i 拿到 rax。
  2. s 丢掉它的提示 rax，拿到 rsi。
  3. a[i] 拿到 rdi。
  4. a 和 n 排在最后，也丢掉了各自的提示。

结果是三条 mov，全在循环外。5 带驱逐的分配器能修好这条链。我判断三条冷 mov 不值得多写那些代码。

数字

对比旧分配器：

指标变化
分配器源码-58%
生成的指令-3.6%
生成的 store-22%
分配器耗时，sqlite 在 -O0 下-77%
总编译时间，sqlite 在 -O0 下-43%

每个功能值多少

重写之前，我依次关掉每个旧功能并测量代码。这是整个项目里最有价值的一小时：

功能节省的指令新分配器
复制合并与复制提示约三分之一保留
活跃区间空洞10%保留
按使用权重选择溢出5.5%保留
指向物理寄存器的提示1%保留
对已溢出区间的乐观二次尝试（占分配器耗时 37%）0.01%去掉
重物化（重算而非重载）无法测量去掉
溢出槽缓存无法测量去掉

收尾

没有驱逐，没有分裂，没有第二轮处理，新的分配器依然胜过旧的。质量提升大多来自那些廉价的手段：合并、提示、空洞和权重。

我得到的教训是：在移植旧代码之前，先测量它。旧分配器的大部分工作其实什么都没做。

完整参考文献列表见原论文。

来源: hexrat← 返回首页