diff options
Diffstat (limited to 'content/notes/register-allocation/ssa/index.md')
| -rw-r--r-- | content/notes/register-allocation/ssa/index.md | 443 |
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 等机器约束. |