第 10–13 篇从零构建了 CFG、SSA、常量传播和无用代码删除。这些 pass 足够说明数据流分析的核心思路，但它们只覆盖了产品级优化器的极小一角。LLVM 经过二十余年的迭代，包含指令组合、循环展开、向量化、寄存器分配、指令选择等数百个 pass。本篇把自制 SSA 翻译成 LLVM IR 文本，接入这条管线，让 Sprout 程序获得真正的优化与本机代码生成。

从自制 SSA 到 LLVM IR

翻译的核心映射并不复杂。自制 SSA 里的每个值对应 LLVM IR 中一个 % 命名的虚拟寄存器；基本块参数翻译成 LLVM 的 phi 节点；Sprout 的 i64 直接映射为 LLVM 的 i64，bool 映射为 i1；函数签名翻译成 define 声明。

以 sum_to 为例，--emit=llvm 输出：

define i64 @sum_to(i64 %n) {
entry:
  br label %loop

loop:
  %sum = phi i64 [0, %entry], [%sum.next, %loop]
  %i   = phi i64 [1, %entry], [%i.next, %loop]
  %cmp = icmp sle i64 %i, %n
  br i1 %cmp, label %body, label %exit

body:
  %sum.next = add i64 %sum, %i
  %i.next   = add i64 %i, 1
  br label %loop

exit:
  ret i64 %sum
}

注意 add 指令没有任何标志。这是本篇最关键的翻译决策。

整数语义：为什么不加 nsw

LLVM 的 add nsw i64 %a, %b 表示"有符号溢出是未定义行为"。编译器可以假设这种溢出永远不会发生，并据此做出推理。如果运行时确实溢出了，结果是 poison 值——它不是陷阱，不是异常，而是一种无声的毒药，会沿着数据流扩散，最终可能让整条分支被删掉。

Sprout 明确定义整数加减乘按二进制补码回绕。9223372036854775807 + 1 的结果是 -9223372036854775808，这在语言规范里是合法行为，不是错误。如果翻译时加上 nsw，LLVM 有权认为这个加法不会溢出，于是把依赖这个结果的分支优化成别的东西。

一个具体的例子。假设有这样的程序：

fn wrap_check(x: i64) -> i64 {
    let y: i64 = x + 1;
    if y < x {       // 只在回绕时为真
        return -1;
    }
    return y;
}

用 add nsw 时，LLVM 推理：有符号加一不可能溢出，因此 y 不可能小于 x，于是把整个 if 分支删掉。传入 i64 最大值时，正确结果应该返回 -1，优化后却返回了回绕值。这不是 LLVM 的 bug，而是我们通过 nsw 向它撒了谎。

翻译规则：Sprout 的 add、sub、mul 一律使用不带标志的 LLVM 指令，获得二进制补码的自然回绕语义。

这里存在一个明确的取舍：nsw 标志能让 LLVM 做更多优化——归纳变量的范围推断、循环迭代次数计算、溢出检查消除都依赖于"不会溢出"的假设。放弃 nsw 意味着放弃这些优化机会。但对于 Sprout 这种定义了回绕语义的语言，正确性优先于性能——nsw 带来的未定义行为会无声地破坏程序逻辑，而少做几个优化只是让代码慢一点。

除法需要额外检查

Sprout 要求除零和 MIN / -1 产生运行时错误。LLVM 的 sdiv 在这两种情况下是未定义行为。如果不在 IR 层面做保护，LLVM 可能删除或移动除法指令，导致本该触发的错误被吞掉。

翻译时，每个 sdiv 前面插入分支：

  %is_zero = icmp eq i64 %divisor, 0
  br i1 %is_zero, label %trap_divzero, label %check_min

check_min:
  %is_min  = icmp eq i64 %dividend, -9223372036854775808
  %is_neg1 = icmp eq i64 %divisor, -1
  %is_ovf  = and i1 %is_min, %is_neg1
  br i1 %is_ovf, label %trap_overflow, label %do_div

do_div:
  %result = sdiv i64 %dividend, %divisor

trap_divzero 和 trap_overflow 调用运行时的错误报告函数后终止。经过这组检查，到达 sdiv 时除数一定非零且不会触发 MIN/-1，LLVM 可以安全地优化剩余路径。

取模运算 srem 需要相同的保护。LLVM 的 srem 在除数为零时同样是未定义行为，MIN srem -1 虽然数学结果为 0，但在某些硬件上与 sdiv 共用同一条指令（x86 的 idiv 同时产生商和余数），仍可能触发陷阱。Sprout 对 % 运算符生成与 sdiv 完全相同的前置检查分支，确保到达 srem 指令时除数非零且不会触发 MIN/-1 溢出。

Bool 与短路

Sprout 的 bool 翻译为 LLVM 的 i1。当 i1 值需要传给运行时的 i64 参数时，用 zext i1 %b to i64 做零扩展。

短路求值在 CFG 构建阶段已经降低成了分支。a && b 变成"先求 a，为假则跳过 b"的控制流。到翻译 LLVM IR 时，这些分支直接输出，不需要额外处理。

LLVM 管线：O0 与 O2

生成 .ll 文件后，通过 opt 和 llc 驱动 LLVM：

# 无优化：验证 IR 并直接编译
opt -O0 -verify sum.ll -o sum-O0.bc
llc -O0 sum-O0.bc -o sum-O0.s

# 标准优化
opt -O2 sum.ll -o sum-O2.bc
llc -O2 sum-O2.bc -o sum-O2.s

-verify 让 LLVM 检查 IR 的结构合法性：类型是否匹配、phi 的来边是否对应前驱、每个块是否有终结指令。如果翻译阶段生成了错误的 IR，这一步就会报错，不必等到运行时才发现问题。

O2 对 sum_to 的优化效果可以通过 opt -O2 -S 观察。LLVM 可能把循环识别为等差数列求和，用封闭公式替换整个循环体。这正是接入成熟优化器的价值——我们不需要自己实现循环归纳变量分析。

验证：O0 和 O2 的输出必须一致

对全部测试程序，分别在 O0 和 O2 下编译运行，比较 stdout 和退出状态。如果某个程序在两个优化级别下行为不同，要么翻译引入了 LLVM 不允许的假设（比如误加了 nsw），要么自制 SSA 保留了不确定行为。

for f in programs/*.spr; do
    sproutc build "$f" -O0 -o /tmp/t0 && /tmp/t0 > /tmp/out0
    sproutc build "$f" -O2 -o /tmp/t2 && /tmp/t2 > /tmp/out2
    diff /tmp/out0 /tmp/out2 || echo "MISMATCH: $f"
done

本篇所有测试程序 O0/O2 输出一致。

练习与资料

在 sum_to 的 add i64 %sum, %i 上手动加上 nsw，用 opt -O2 -S 查看 LLVM 做了哪些额外优化。构造一个输入使回绕发生，对比有无 nsw 时的运行结果。移除 nsw 后确认行为恢复正确。
阅读 LLVM Language Reference 的 Poison Values 章节，追踪 poison 如何从一条 add nsw 传播到 select、phi 和 br。
在除法检查中故意去掉 MIN/-1 的分支，用 i64::MIN / -1 作为输入，观察 O0 和 O2 是否产生不同行为。