Add register allocation note series

1 files changed, 443 insertions, 0 deletions

diff --git a/content/notes/register-allocation/ssa/index.md b/content/notes/register-allocation/ssa/index.md
new file mode 100644
index 0000000..443f2b1
--- /dev/null
+++ b/content/notes/register-allocation/ssa/index.md
@@ -0,0 +1,443 @@
+---
+title: "第七部分: SSA 与寄存器分配"
+slug: "ssa"
+lang: zh-Hans
+series: register-allocation
+weight: 80
+created: 2026-08-17
+updated: 2026-09-09
+license: CC-BY-SA-4.0
+---
+
+前面几部分讨论寄存器分配时, 我们一直从一般的 live range 出发. 一个机器级虚拟寄存器可能经历多次 definition, allocator 再通过 liveness 判断某一个 definition 产生的值在什么区域有效. SSA, 即 Static Single Assignment, 把这个关系整理得更规整: 每个 SSA value 只有一个 definition, 每个 use 都明确引用这个 definition 产生的值. 这种结构首先简化了 def-use 关系, 随后又影响 live range 的形状, interference graph 的性质, phi 的处理方式以及 SSA destruction.
+
+SSA 对寄存器分配的意义不只是 "变量改了名字". 对一个 allocator 来说, single assignment 带来的真正收益是每个 value 都有唯一的生命周期起点. 如果再结合 dominance, 很多在一般 live range 上需要额外分析的关系会获得比较严格的结构.
+
+## 1 Single Definition, Dominance 与 Live Range
+
+先看普通命令式形式:
+
+```text
+x = a + b
+use x
+
+x = c + d
+use x
+```
+
+如果把 `x` 当作同一个名字, 它在这里显然有两个不同 definition. SSA 会把它们拆成两个 values:
+
+```text
+x1 = a + b
+use x1
+
+x2 = c + d
+use x2
+```
+
+现在 `x1` 的所有 uses 都属于第一个 definition, `x2` 的所有 uses 都属于第二个 definition. 对 liveness 来说, allocator 不再需要询问 "这里使用的是 `x` 的哪一次定义"; SSA name 已经把这个问题编码进 IR.
+
+SSA 还要求一个 value 的 definition dominate 它的普通 uses. 假设 `v` 在 basic block `D` 中定义, 并在 basic block `U` 中使用, 那么从函数入口到达这个 use 的每一条控制流路径都必须经过 `D`. 例如:
+
+```text
+        B1
+        |
+      v = ...
+       / \
+      /   \
+     B2   B3
+     |     |
+   use v   |
+      \   /
+       \ /
+        B4
+        |
+      use v
+```
+
+这里 `B1` 位于到达两个 uses 的所有控制流路径上. 因此 `v` 的生命周期有一个明确的根, 就是 `B1` 中的唯一 definition.
+
+如果从 dominance tree 上观察一个 SSA value 的 live region, 它通常可以表示成一棵连通子树. 一个 use 要求 value 从 definition 一直沿相应的 dominance 路径保持有效, 多个 uses 对应的这些路径合起来仍然保持连通. 这条性质后面会直接导出 SSA interference graph 的 chordal structure.
+
+需要注意 source variable 和 SSA value 的区别. 一个源语言变量可能在 SSA 中变成很多 names, 每个 name 都是独立 value. Register allocator 更关心这些 values 的 live ranges, 而不会试图让所有来自同一个源变量的 SSA names 永远使用同一个物理寄存器.
+
+## 2 Phi 的 Use 发生在 CFG Edge 上
+
+SSA 在控制流汇合处使用 phi. 例如:
+
+```text
+B1:
+    x1 = ...
+    goto B3
+
+B2:
+    x2 = ...
+    goto B3
+
+B3:
+    x3 = phi(x1 from B1, x2 from B2)
+    use x3
+```
+
+Phi 的 operand 和普通指令 operand 有一个根本区别. `x1` 的 use 属于 edge `B1 -> B3`, `x2` 的 use 属于 edge `B2 -> B3`. 程序从 `B1` 进入 `B3` 时选择 `x1`, 从 `B2` 进入时选择 `x2`.
+
+```text
+B1 ---- x1 ----\
+                \
+                 >---- B3: x3 = phi(...)
+                /
+B2 ---- x2 ----/
+```
+
+因此不能把 `x1` 和 `x2` 简单地都加入 `LIVE_IN[B3]`. 这样做会让两个来自互斥 predecessor edges 的 operands 在 `B3` 入口处看起来同时 live, 进而制造虚假的 interference.
+
+Block-level liveness 在处理 phi 时通常需要保留 edge-specific 信息. 假设 successor `S` 中有一个 phi, predecessor `B` 只应该把属于 `B -> S` 这条 edge 的 phi operand 加入自己的 live-out. 来自其他 predecessors 的 operands 与 `B` 无关.
+
+Phi result `x3` 则在 `B3` 入口处产生. 所以从数据流的角度看, 可以把 phi 想象成多条 predecessor edges 上发生的 value transfer, 最终在 successor 入口得到一个新的 SSA value.
+
+这种语义对寄存器分配很有利. 如果 `x1`, `x2`, `x3` 没有其他 interference 阻止它们共享寄存器, allocator 可以安排 $x_1 \mapsto R_0$, $x_2 \mapsto R_0$, $x_3 \mapsto R_0$. SSA destruction 以后, 两条 edge 上都不需要实际的数据移动.
+
+如果得到 $x_1 \mapsto R_0$, $x_2 \mapsto R_1$, $x_3 \mapsto R_0$, 那么只有 `B2 -> B3` 需要一次从 `R1` 到 `R0` 的 copy. 因此 phi 会自然形成 coalescing preference: incoming value 和 phi result 倾向于使用相同的物理寄存器.
+
+这里同样不能只根据 phi 自身判断两个 operands 是否 interfere. `x1` 和 `x2` 可能因为程序其他位置的 liveness 而发生冲突, 也可能完全没有冲突. Phi 的 edge semantics 只是保证 allocator 不会因为 phi 这一条指令本身凭空制造冲突.
+
+## 3 SSA Interference Graph 为什么是 Chordal Graph
+
+SSA 给 graph coloring 带来的理论优势, 来自前面提到的 dominance structure.
+
+把 dominance tree 看成一棵真正的树. 每个 SSA value 的 live region可以对应其中的一棵连通子树. 两个 values 发生 interference, 意味着它们的 live regions 在某个程序位置相交. 因此 SSA interference graph 可以理解为一组 dominance-tree subtrees 的 intersection graph.
+
+例如 dominance tree 为:
+
+```text
+          A
+        /   \
+       B     C
+      / \     \
+     D   E     F
+```
+
+假设几个 values 的 live regions 大致为:
+
+```text
+v1: A - B - D
+
+v2:     B - D - E
+
+v3:             C - F
+```
+
+`v1` 和 `v2` 的 live regions 相交, 因此在 interference graph 中存在边. `v3` 所在的区域与前两者分离, 因而这组 live regions 本身不会生成 `v1-v3` 或 `v2-v3` 的 interference.
+
+树的连通子树所形成的 intersection graph 是 chordal graph. 因此, 在保持 strict SSA liveness 结构的条件下, SSA interference graph 具有 chordal property.
+
+Chordal graph 中, 所有长度至少为 4 的无弦环都会被排除. 例如:
+
+```text
+a ----- b
+|       |
+|       |
+d ----- c
+```
+
+这是一个没有 chord 的四边形. 如果加入 `a-c`:
+
+```text
+a ----- b
+|  \    |
+|    \  |
+d ----- c
+```
+
+环上出现了一条连接非相邻顶点的 chord.
+
+Chordal graph 存在 perfect elimination ordering. 按这种顺序逐个删除节点时, 每个被删除节点当前的邻居都会形成 clique. 反过来按照这个顺序进行 greedy coloring, 可以得到最优 coloring. 因而对于 chordal graph 有:
+
+$$  
+\chi(G)=\omega(G)  
+$$
+
+这里 $\chi(G)$ 是 chromatic number, $\omega(G)$ 是最大 clique 大小.
+
+这个等式和第三, 四部分讨论的一般 interference graph 差别很大. 对一般图, $\omega(G)$ 只是 $\chi(G)$ 的下界. 最大 clique 只需要 3 种颜色, 整张图仍然可能需要 4 种甚至更多颜色. 对 chordal graph, 最大 clique 已经决定了最少颜色数.
+
+如果当前 register class 有 $K$ 个完全等价的物理寄存器, 并且 SSA interference graph 满足 $\omega(G)\le K$, 那么单纯从 graph coloring 的角度看, 存在合法的 $K$-coloring, 而且可以高效找到.
+
+这里的限制条件需要保留. 真实 RA 还有 register classes, pre-colored nodes, physical register aliasing, fixed constraints 和 register tuples. 这些约束加入以后, "最大 clique 不超过 $K$" 已经不能单独保证最终 machine assignment 成功. Chordal property 解决的是基础 interference coloring 问题.
+
+## 4 SSA 把很多困难推向了 Spilling
+
+假设一个 register class 只有 $K$ 个物理寄存器, 某个位置却有 $K+2$ 个 SSA values 同时 live. 这些 values 在 interference graph 中形成至少大小为 $K+2$ 的 clique. 即使 graph 是 chordal, coloring 也不可能把 $K+2$ 个互相冲突的 values 塞进 $K$ 个寄存器.
+
+所以在 SSA-based register allocation 中, spilling 和 coloring 可以形成比较清晰的分工. Spilling 或 splitting 负责降低某些位置的 register pressure, 随后的 coloring 再利用 SSA interference graph 的结构完成 assignment.
+
+这一点和 Chaitin-Briggs 的组织方式有所区别. Chaitin-style algorithm 在 simplify 过程中遇到 high-degree structure 时选择 potential spill, coloring 和 spill decision 彼此交织. SSA-based allocator可以先研究哪些 values 需要从高压力区域移走, 在压力满足要求以后再利用 chordal graph 进行 coloring.
+
+SSA 也方便 spill rewrite 保持 single-definition property. 假设:
+
+```text
+v1 = ...
+...
+use v1
+...
+use v1
+```
+
+如果 `v1` 被 spill, 可以写成:
+
+```text
+v1 = ...
+store [slot], v1
+
+...
+
+t1 = load [slot]
+use t1
+
+...
+
+t2 = load [slot]
+use t2
+```
+
+`t1` 和 `t2` 各自只有一个 definition, 因而仍然可以作为新的 SSA values. 原来的长 live range 被分解成多个短 live ranges, allocator 可以继续对这些新 values 使用 SSA liveness.
+
+Reload 放在哪里会影响新的 register pressure. 假设一个 spilled value 在两个分支中都有 use:
+
+```text
+        B1
+       /  \
+      B2  B3
+      |    |
+    use   use
+```
+
+一种方案是在 `B1` 中 reload 一次:
+
+```text
+        load t
+          |
+         / \
+        B2 B3
+        |   |
+      use  use
+```
+
+这样两个分支共享一个 reload, 但 `t` 从 `B1` 开始就保持 live, 生命周期比较长. 另一种方案是在 `B2` 和 `B3` 中分别 reload, 产生两个较短的 SSA values. 后者可能增加动态 memory operations, 同时降低寄存器压力.
+
+Spill placement 因而同时涉及 execution frequency 和 live range length. SSA 使新 definitions 和 uses 的关系更清楚, 却没有消除这种 cost trade-off.
+
+## 5 Live Range Splitting 在 SSA 中如何表示
+
+Live range splitting 在 SSA 里可以理解成主动创建新的 definitions.
+
+假设原来:
+
+```text
+v1:
+|-----------------------------------|
+```
+
+allocator 希望把它拆成三个 fragments:
+
+```text
+v1:
+|-----------|
+
+v2:
+             |-----------|
+
+v3:
+                          |--------|
+```
+
+那么 `v2` 和 `v3` 可以成为新的 SSA values. 后续 uses 根据程序位置重新命名, 分别引用对应 fragment. Fragments 之间通过 copy, spill/reload 或 phi 传递值.
+
+在直线代码里可能得到:
+
+```text
+v1 = ...
+...
+v2 = COPY v1
+...
+v3 = COPY v2
+...
+```
+
+如果最后三个 fragments 都分配到同一个 physical register, 这些 copies 可以被消除. 如果中间 fragment需要进入 memory, transfer 就可能转化成 store 和 reload.
+
+带控制流的 splitting 会更接近 SSA construction. 例如两个分支分别产生新的 fragments, 在汇合以后需要继续使用同一个逻辑值:
+
+```text
+          v1
+         /  \
+        /    \
+      v2      v3
+        \    /
+         \  /
+      v4 = phi(v2, v3)
+```
+
+这里 `v2` 和 `v3` 分别是不同路径上的 definitions, `v4` 在 join block 中重新把它们合并成一个 SSA value. 所以 SSA-based splitting 往往需要 dominance, renaming 和 phi placement 协同工作.
+
+从 allocator 的角度看, splitting 的收益仍然是缩短 allocation object. 原来一个 value 跨越多个高压力区域, 拆开以后每个 fragment 可以分别选择 physical register 或 memory location, 不需要整个生命周期保持同一种 allocation decision.
+
+## 6 Coalescing 与 SSA Structure 的关系
+
+Phi destruction 会产生 copy, allocator 又希望通过 coalescing 删除这些 copies. 但 coalescing 会改变 SSA value 原本整齐的 live-range structure.
+
+考虑:
+
+```text
+x3 = phi(x1, x2)
+```
+
+`x1`, `x2`, `x3` 分别拥有自己的唯一 definition. 如果 allocator 把它们全部合并为一个 allocation object, 这个联合对象会包含多个 definitions. 从物理寄存器分配角度看这完全可能是理想结果, 因为三个 values 可以共享一个 physical register; 从 SSA structural analysis 的角度看, 联合对象已经不再对应一个单一 definition 支配的 live subtree.
+
+任意识别两个不相邻节点进行 coalescing, 还可能破坏原来的 chordal interference structure. 因此某些 SSA-based allocators 会尽量在利用完 SSA coloring 性质之后再进行更激进的 coalescing, 或者只允许满足特定条件的合并.
+
+这里和第五部分的 IRC 有相似的问题背景. IRC 从一般 interference graph 出发, 使用 Briggs 或 George criterion 控制 coalescing 风险. SSA-based RA 拥有更规整的初始图, 因而更加有理由保护这份结构, 至少在需要利用 chordal coloring 的阶段不要随意破坏它.
+
+Phi 本身仍然提供了很强的 coalescing preference. 因此实际设计需要在两件事之间选择时机: 一方面希望保留 SSA structure 方便 allocation, 另一方面希望尽量让 phi related values 获得同一 physical register.
+
+## 7 SSA Destruction 与 Parallel Copy
+
+最终机器代码不能保留抽象 phi, 因此在某个阶段需要进行 SSA destruction.
+
+对于:
+
+```text
+B1:
+    ...
+    goto B3
+
+B2:
+    ...
+    goto B3
+
+B3:
+    x3 = phi(x1 from B1, x2 from B2)
+```
+
+可以把它展开成两条 edge-specific transfers:
+
+```text
+B1 -> B3:
+    x3 <- x1
+
+B2 -> B3:
+    x3 <- x2
+```
+
+如果 `x1` 和 `x3` 已经分配到同一寄存器, 第一条 transfer 无需生成真正的 move. `x2` 和 `x3` 同理.
+
+一个 block 同时存在多个 phi 时, 某条 predecessor edge 上会出现一组同时发生的 assignments:
+
+```text
+a3 <- a1
+b3 <- b1
+c3 <- c1
+```
+
+这里需要使用 parallel copy semantics. 所有右侧值都按照 assignment 开始前的状态读取.
+
+假设物理寄存器分配以后出现:
+
+```text
+R0 <- R1
+R1 <- R0
+```
+
+如果先执行 `R0 <- R1`, 原来 `R0` 中的值已经丢失. 因此需要 temporary:
+
+```text
+TMP <- R0
+R0  <- R1
+R1  <- TMP
+```
+
+对于没有 cycle 的 copy dependencies, compiler 可以安排一个安全顺序. 例如:
+
+```text
+R0 <- R1
+R2 <- R0
+```
+
+如果两个 source 都表示旧寄存器值, 应该先执行:
+
+```text
+R2 <- R0
+R0 <- R1
+```
+
+这样旧 `R0` 在被覆盖之前已经保存到 `R2`.
+
+因此 SSA destruction 通常先把 phi 转换成 edge-specific parallel copies, 再由 parallel-copy resolver 把它们变成串行机器指令. Coalescing 做得越好, 真正需要 resolver 处理的 copies 就越少.
+
+## 8 Critical Edge 与 Copy Placement
+
+Phi 的 transfers 属于 CFG edges, 所以 copy placement 还会遇到 critical edge.
+
+假设:
+
+```text
+        B
+       / \
+      v   v
+      S   X
+      ^
+      |
+      P
+```
+
+`B` 有两个 successors, `S` 也有多个 predecessors, 因而 `B -> S` 是 critical edge. 如果某条 phi transfer 只属于 `B -> S`, 那么不能直接放在 `B` 末尾, 因为走 `B -> X` 时也会执行; 放到 `S` 开头也会影响从 `P -> S` 进入的路径.
+
+常见做法是 split 这条 edge:
+
+```text
+        B
+       / \
+      v   v
+      E   X
+      |
+      v
+      S
+      ^
+      |
+      P
+```
+
+新的 block `E` 只会在原来的 `B -> S` 路径上执行, 因而可以安全放置对应 copies.
+
+这会说明 SSA destruction 在 compiler pipeline 中并不是一个纯粹的语法转换. 它可能修改 CFG, 引入 copies, 改变 liveness, 进而影响寄存器分配. 如果很早 destruction, 后面的 allocator 要处理更多 ordinary copies; 如果延迟 destruction, allocator 本身就需要理解 phi operands 的 edge semantics.
+
+## 9 Machine SSA 与工业寄存器分配
+
+SSA-based RA 并不等于工业编译器一定使用某一种专门的 "SSA coloring algorithm". SSA 也可以只是寄存器分配之前维持的一种 machine-level invariant.
+
+LLVM 就很适合说明这一点. Instruction selection 以后, Machine IR 中的 virtual registers 在相当一段 pipeline 内仍然保持 SSA 性质. 一个 virtual register 通常具有唯一 definition, machine passes 可以沿 def-use chains 查询它的数据来源和使用位置.
+
+寄存器分配逐渐改变这种状态. Coalescing 可能把多个 values 连接起来, splitting 会生成新的 fragments, spilling 会插入 stores 和 reloads, 最终 virtual registers 被改写成 physical registers. 一个 physical register 如 `RAX` 在整个函数中会反复被不同指令定义, 自然不再满足 SSA.
+
+所以工业 allocator 经常会经历这样的变化:
+
+```text
+Machine SSA
+    |
+    | virtual registers with single defs
+    v
+Coalescing / splitting / spilling
+    |
+    v
+General live ranges
+    |
+    v
+Physical register assignment
+    |
+    v
+Non-SSA physical-register code
+```
+
+LLVM 的 `LiveIntervals` 之所以需要 `VNInfo` 一类结构, 也与这种变化有关. 一旦一个 register live range 中出现多个 definitions, allocator 就需要区分不同 definitions 产生的 value numbers, 单纯依赖最初的 SSA name 已经不够.
+
+SSA 给寄存器分配提供了一块结构比较规整的起点. Definition 和 use 的关系清楚, phi operands 具有 edge semantics, live regions 与 dominance tree 联系紧密, interference graph 也因此具有 chordal structure. 进入下一部分以后, 我们会开始把这里相对抽象的 "颜色" 逐步替换成真实 CPU 的寄存器资源, 讨论 register class, calling convention, pre-colored register, fixed operand, subregister aliasing, two-address constraint 和 register pair 等机器约束.