第 09 篇用 alloca/load/store 把可变变量映射到栈内存。这种做法能让代码生成跑起来，但优化器看到的是一堆内存操作，无法直接判断哪些 load 读的是同一个值。常量传播要穿透内存别名分析，复杂度远超必要。

SSA（Static Single Assignment）要求每个变量恰好被定义一次。当同一个变量在不同路径上获得不同值时，合流处放一个 phi 节点完成合并。优化器只需沿定义-使用链就能追踪值的流动。本篇从第 10–11 篇的 CFG 和支配关系出发，构造 SSA 并替换掉第 09 篇的临时内存形式。

数据结构变化：从变量到值

第 10 篇的 Block 只存储无类型的指令列表和终结符，块参数用 (VarId, Ty) 表示——还是以变量为中心的视角：

// 第 10 篇的 Block
pub struct Block {
    pub id: BlockId,
    pub params: Vec<(VarId, Ty)>,
    pub body: Vec<Inst>,
    pub terminator: Term,
}

引入 SSA 后，每次赋值产生一个全局唯一的 Value，不再有"变量被多次赋值"的概念。Block 随之演变：

// 本篇的 Block（SSA 形式）
pub struct Block {
    params: Vec<(Value, Type)>,   // VarId → Value，Ty → Type
    insts: Vec<Inst>,             // body → insts
    terminator: Terminator,       // Term → Terminator，携带 Vec<Value> 参数
}

三处关键变化：(1) 块参数从 (VarId, Ty) 变成 (Value, Type) 对——每个参数本身就是一个 SSA 值，而不是一个可被多次赋值的变量；(2) 终结指令 Terminator 的跳转和分支都携带 Vec<Value> 参数，显式传递 SSA 值到目标块；(3) BlockId 字段不再出现在结构体中，改由外部容器管理。这些变化让"定义-使用"关系在类型层面就可追踪，为后续的常量传播和无用代码删除打下基础。

SSA 的核心性质

普通程序里一个变量可以被多次赋值。SSA 把每次赋值看作产生了一个新版本：

源程序:                SSA 形式:
x = 1                 x.1 = 1
x = x + 2             x.2 = x.1 + 2
print(x)              print(x.2)

每个版本只有一个定义点，使用处直接引用那个版本。问题出在控制流分叉再合并的地方——if 的两个分支各自给 x 赋了不同值，合流后用哪个？phi 节点按前驱块选择对应的值：

entry:
    br cond, then, else
then:
    x.1 = 1
    jmp merge
else:
    x.2 = 2
    jmp merge
merge:
    x.3 = φ(x.1 from then, x.2 from else)

phi 不是一条真正执行的指令。它表达的是"到达 merge 时，根据实际走过的路径选择值"。后端生成代码时，phi 被消解为前驱块末尾的拷贝。

在哪些块放置 phi

不是每个合流块都需要 phi。只有当一个变量在某个块被定义，且另一个块处于该定义的支配边界上时，那个边界块才需要 phi。

算法（Cytron et al. 1991）：

对每个变量 v，收集所有包含 v 定义的块，记为 defs(v)。
对 defs(v) 中的每个块 d，遍历 d 的支配边界 DF(d) 中的每个块 f。
若 f 还没有 v 的 phi，插入一个。这个 phi 本身也是 v 的一个新定义，把 f 加入 defs(v)。
重复直到没有新的 phi 产生。

用第 11 篇的菱形 CFG 演示。设 entry 中定义了 x，then 和 else 各重新定义 x：

      entry (def x.0)
      /           \
then (def x.1)  else (def x.2)
      \           /
      merge ← DF(then) ∩ DF(else)

merge 在 then 和 else 的支配边界上，所以 merge 得到一个 phi。entry 的支配边界为空集，不产生 phi。

变量重命名

phi 放好之后，需要把原始变量名替换成带版本号的 SSA 名字。按支配树前序遍历：

每个变量维护一个栈，栈顶是当前有效版本。
遇到定义（包括 phi），生成新版本并压栈。
遇到使用，读取栈顶版本。
对当前块的每个后继块，填充后继块中 phi 节点对应当前块的操作数。
离开当前块时，弹出本块压入的版本。

这个过程保证了 SSA 的关键不变式：每个使用都被其定义所支配。

块参数就是 phi

第 10 篇的 IR 用块参数（block parameter）替代传统 phi 记法。跳转指令携带参数，目标块的参数列表接收它们：

/// SSA 中的值，全局唯一
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct Value(u32);

/// 基本块，参数列表等价于 phi 节点
pub struct Block {
    params: Vec<(Value, Type)>,   // 块参数 = phi 的结果
    insts: Vec<Inst>,
    terminator: Terminator,
}

pub enum Terminator {
    Return(Value),
    Jump { target: BlockId, args: Vec<Value> },
    Branch {
        cond: Value,
        then_target: BlockId, then_args: Vec<Value>,
        else_target: BlockId, else_args: Vec<Value>,
    },
}

Jump { target: merge, args: [x.1] } 从 then 跳到 merge 时，把 x.1 传给 merge 的第一个块参数。从 else 跳过来时传 x.2。merge 的块参数 x.3 就是两者的 phi 合并结果。这种表示比在块头部列一排 φ(...) 更容易维护——参数和前驱的对应关系由跳转指令的参数位置天然保证。

SSA verifier

构造完成后，verifier 检查四条性质：

定义支配使用：对每个 Value 的每处使用，其定义所在的块必须支配使用所在的块（同块内定义须在使用之前）。
phi 来源匹配前驱：每个块参数收到的实参数量等于前驱块数量，且每个前驱恰好提供一份。
类型一致：所有传给同一块参数的值，类型必须与参数声明一致。
无残留内存操作：alloca、load、store 已全部消除——第 09 篇的过渡形式到此结束。

sum_to 的 SSA 形式

第 09 篇的 sum_to(10) 输出 55。转成 SSA 后，循环变量成为 loop 块的参数：

fn sum_to(n.0: i64) -> i64:
  entry:
    jmp loop(0, 1)            // sum.0=0, i.0=1

  loop(sum.1: i64, i.1: i64):
    cond.0 = le i.1, n.0
    br cond.0, body, exit

  body:
    sum.2 = add sum.1, i.1
    i.2   = add i.1, 1
    jmp loop(sum.2, i.2)

  exit:
    ret sum.1

--emit=ssa 输出上述文本。循环回边 jmp loop(sum.2, i.2) 把新版本的 sum 和 i 传回 loop 的块参数，完成 phi 合并。entry 提供初始值 0 和 1。

错误注入

交换 body 中跳转的两个参数：jmp loop(i.2, sum.2)。verifier 在类型检查阶段不会报错（两个都是 i64），但语义已经错误——sum 和 i 的角色被互换。运行 sum_to(10) 不再输出 55。

如果把传给 loop 的参数从两个改成一个，verifier 立即报错：块 loop 期望 2 个参数，实际收到 1 个，来源与前驱数量不匹配。

替换完成

所有第 09 篇的测试程序——常量返回、算术表达式、条件分支、循环累加——现在走 SSA 路径生成 LLVM IR。alloca/load/store 不再出现在 --emit=ssa 输出中。verifier 在每次编译时自动运行，任何违反 SSA 性质的变换都会在进入后端之前被拦截。

练习

为以下函数手工构造 SSA。先画 CFG，标出支配边界，放置 phi，再重命名：

fn f(a: i64) -> i64 {
    let mut x: i64 = a;
    if a > 0 {
        x = x + 1;
        if a > 10 {
            x = x * 2;
        }
    }
    return x;
}