第 12 篇完成了 SSA 构造。每个值只有一个定义点，优化器可以沿定义链追踪数据流。程序已经具备了被分析的结构基础，但结构本身不减少指令数量。本篇实现第一批真正的优化：常量传播和无用代码删除，把 SSA 从"可分析的中间表示"变成"更精简的中间表示"。

常量折叠：编译期完成的算术

最直接的优化是常量折叠（constant folding）。如果一条算术指令的两个操作数都是编译期已知的常量，编译器直接计算结果，用一个常量值替换这条指令。

优化前的 SSA 片段：

v1 = const 3
v2 = const 5
v3 = add v1, v2
v4 = mul v3, v3
return v4

v1 和 v2 都是常量，add 的结果在编译期可以确定为 8。替换后 v3 变成 const 8，接着 mul v3, v3 的两个操作数也是常量，折叠为 64。三条算术指令最终变成一个常量返回。

SSA 的单定义性质让替换可靠——v1 在整个函数里只有一个定义点，所有使用 v1 的地方看到的值都是 3，不存在"某条路径上 v1 被重新赋值"的可能。这正是第 12 篇花力气构建 SSA 的回报。

折叠必须遵守语言语义。Sprout 的整数加减乘按补码回绕，除法向零截断，除零产生运行时错误。编译期折叠除法时必须先检查除数：除数为零不能折叠，因为这条指令在运行时应当触发错误，错误本身是程序语义的一部分。类似地，i64 最小值除以 -1 在补码表示下会溢出，Sprout 把它定义为运行时错误，编译器同样不能擅自折叠。

常量传播：穿越 phi 节点

折叠只处理单条指令内部的运算。常量传播（constant propagation）把已知的常量值向下游推送，让更多指令的操作数变成常量，从而触发更多折叠。

传播也适用于 phi 节点。回忆第 12 篇的定义：phi 节点在控制流合并点选择来自不同前驱的值。如果 phi 的所有操作数都相同且为常量，phi 的结果也是该常量。

entry:
  v1 = const 10
  br cond, left, right

left:
  br merge

right:
  br merge

merge:
  v2 = phi [v1, left], [v1, right]
  return v2

v2 的 phi 有两个操作数，都来自 v1，而 v1 恒为 10。无论控制流走 left 还是 right，合并后的值都是 10。替换 phi 为常量后：

1 2	`merge: return const 10`

phi 消失了，merge 块变得更短。传播算法反复扫描所有指令，每发现一个新常量就更新使用它的指令，直到一轮扫描没有产生任何新常量为止。这个不动点迭代在有限程序上必然终止——每个值的状态只能从"未知"变为"某个常量"或"非常量"，不会回退。

稀疏条件常量传播

简单传播有一个盲区。考虑这种情况：

entry:
  v1 = const true
  br v1, then_bb, else_bb

then_bb:
  v2 = const 42
  br merge

else_bb:
  v3 = const 99
  br merge

merge:
  v4 = phi [v2, then_bb], [v3, else_bb]
  return v4

简单传播看见 phi 的两个操作数是两个不同的常量（42 和 99），判定 v4 为"非常量"，放弃折叠。但是 v1 恒为 true，else_bb 在运行时永远不会被执行——v3 的 99 根本不会流入 phi。

稀疏条件常量传播（Sparse Conditional Constant Propagation, SCCP）把常量传播与可达性分析合在一起做，解决上述问题。算法维护两个工作表：

值工作表：每个 SSA 值的状态，三种可能——未确定、已知为某常量、已确定为非常量。
块工作表：每个基本块的可达状态。初始只有入口块可达。

处理分支指令时，如果条件是已知常量，只把目标分支的后继标记为可达，另一条分支不标记。处理 phi 时，只考虑来自已标记为可达的前驱块的操作数，忽略不可达前驱带来的值。

回到上面的例子：SCCP 发现 v1 恒为 true，只标记 then_bb 可达，else_bb 保持不可达。v4 的 phi 只剩一个有效操作数 v2 = 42，折叠为常量 42。整个 else_bb 块后续被删除。

两个工作表交替推进，直到同时稳定。SCCP 严格优于简单常量传播——它能发现的常量集合是简单传播结果的超集。实际编译器中，SCCP 几乎总是取代简单常量传播，因为它的实现复杂度只增加了可达性标记，但能消除的冗余显著增多。在循环体内，如果循环条件能被证明恒为 false，SCCP 可以把整个循环体标记为不可达，连同其中所有 phi 节点和计算一并清除。

无用代码删除

常量传播消除了多余的计算，但程序中还可能残留结果从未被使用的指令。无用代码删除（Dead Code Elimination, DCE）处理这种情况：一条指令的结果没有任何使用者，且指令本身没有副作用，就可以安全移除。

判断"没有使用者"在 SSA 里很简单——检查值的使用者列表是否为空。困难在于副作用分类。不是所有"结果未使用"的指令都能删除，副作用分类决定了 DCE 的正确性边界。

纯算术——add、sub、mul、比较运算没有可观察的副作用。它们只计算一个值，不修改内存，不产生输出，不触发错误（除法除外）。结果未使用就可以安全删除。

输出操作——print_i64 向 stdout 写数据。即使调用的返回值没人用，打印行为本身是程序语义的一部分。删除它就把"输出 42"变成了"什么都不输出"。

除法与取模——div 和 mod 在除数为零时触发运行时错误。一条看似"无用"的除法，如果除数可能为零，删除它就吞掉了一个该发生的错误。只有当编译器能证明除数不为零时（比如除数是非零常量），才可以把没有使用者的除法删除。

函数调用——被调函数可能打印内容、修改全局状态、触发运行时错误。除非编译器能证明一个函数是纯函数，否则保守地保留调用。Sprout 目前没有纯函数标注机制，所以所有函数调用一律保留。

DCE 的实现遍历所有指令，检查使用者列表。使用者为空且标记为无副作用的指令被删除。删除后，该指令原来引用的操作数可能也失去了最后一个使用者，变得可以删除——因此需要把它们加入待检查队列，递归执行直到没有新的删除发生。这个级联删除效果在常量传播之后尤其明显：大量指令的操作数被替换为常量后，原来提供操作数的那些定义指令可能就不再被任何人引用了。

不可达块清理

SCCP 和分支折叠会让某些基本块变得不可达——所有前驱要么被删除，要么分支目标改向了别处。清理方法是从入口块做一次可达性遍历，没有被访问到的块直接删除。

删除不可达块时要注意一个细节：后继块中的 phi 节点可能引用了被删块作为前驱。必须同时清理这些 phi 操作数，否则 phi 会引用一个不存在的前驱，第 12 篇建立的 SSA verifier 会拒绝这份 IR。

如果清理 phi 操作数后 phi 只剩一个操作数，它可以直接替换为那个值——这又可能触发新一轮的常量传播。实际实现中，SCCP、DCE 和块清理通常在一个 pass 内交替执行，或者按固定顺序迭代直到 IR 不再变化。

块清理也有助于减小最终生成代码的体积。不可达块中的指令虽然运行时不会执行，但如果不清理，它们仍然占据 IR 空间，后续翻译到 LLVM IR 时会生成无用的机器码。尽早删除这些块，后续每个 pass 需要遍历的指令数量都会减少。

不能删的反例

两个反例说明副作用分类不是可选项，而是正确性的核心。

反例一：短路求值中的除零。

Sprout 规定 && 短路求值——左操作数为 false 时，右操作数不执行。

1	`false && (1 / 0 > 0)`

运行时 1 / 0 永远不会被求值，程序正常结束。如果优化器尝试在编译期折叠 1 / 0，就会产生一个运行时本不该发生的除零错误。正确做法：SCCP 发现 && 的左操作数恒为 false，把右侧分支标记为不可达。不可达块里的 1 / 0 不参与任何传播或折叠，最终连同整个块一起被删除。关键在于不可达的代码不应该在编译期被求值。

反例二：未使用返回值的输出调用。

1 2	`let x: i64 = print_i64(42); // x 之后没有被使用`

x 的使用者列表为空。一个不小心的 DCE 会认为 print_i64(42) 是"无用指令"而删除它。但是删除后程序不再输出 42，行为被改变了。正确做法：print_i64 被标记为有副作用，DCE 遇到有副作用的指令直接跳过，不管返回值是否被使用。

这两个反例的共同教训是：编译器优化的正确性条件是"优化前后程序的可观察行为不变"。可观察行为包括输出、运行时错误和程序的终止性。只有证明不影响这些，优化才成立。

完整优化前后对照

一个综合示例展示 SCCP + DCE 的效果。

优化前：

entry:
  v1 = const 3
  v2 = const 5
  v3 = add v1, v2          ; → 8
  v4 = const true
  br v4, bb1, bb2

bb1:
  v5 = mul v3, v3           ; → 64
  call print_i64(v5)
  br exit

bb2:                        ; 不可达
  v6 = sub v3, v1
  v7 = div v6, v2
  br exit

exit:
  v8 = const 0
  return v8

SCCP 确定 v4 = true，bb2 不可达。v1 到 v5 的算术全部折叠为常量。DCE 删除无使用者的中间值。print_i64 有副作用，保留。优化后：

1
2
3

entry:
  call print_i64(const 64)
  return const 0

六条算术指令、一个条件分支、一个不可达块，全部消除。剩下的两条指令——一条输出调用和一条返回——是程序可观察行为的全部。

练习

给定以下 SSA 程序，手工执行 SCCP。对每个值写出最终状态（未确定 / 某常量 / 非常量），对每个块写出可达性。标出 DCE 后哪些指令存活。

entry:
  v1 = const 0
  v2 = const 1
  v3 = eq v1, v1
  br v3, bb_t, bb_f

bb_t:
  v4 = add v1, v2
  v5 = mul v4, v4
  br bb_end

bb_f:
  v6 = const 999
  call print_i64(v6)
  br bb_end

bb_end:
  v7 = phi [v5, bb_t], [v6, bb_f]
  return v7