12.2 公共子表达式消除

公共子表达式消除（Common Subexpression Elimination，CSE）会复用已经可用的计算结果。若 %v1 = add %a, %b 已执行，且操作数及相关语义事实没有变化，后面相同的 add 就可以直接使用 %v1。

%v1 = add %a, %b
%v2 = mul %v1, 4
%v3 = add %a, %b   ; 替换为 %v1
%v4 = sub %v3, 1   ; 变成 sub %v1, 1

真正困难的部分藏在“相同表达式”几个字里：编译器必须证明，在每条能到达第二条指令的路径上，两次计算都产生相同值。

表达式键与值编号

局部 CSE 可以扫描一个基本块，并维护“表达式键 → 旧结果”的表。整数加法的键可以包含 opcode、类型、语义标志和操作数值编号：

key = (add, i32, no_signed_wrap=false, VN(a), VN(b))

对满足交换律的运算，规范化操作数顺序可让 a + b 匹配 b + a。但要让 (a + b) + c 匹配 a + (b + c)，需要更强的结合律许可：有符号溢出规则与浮点舍入都可能让两种写法不同。

全局值编号（Global Value Numbering，GVN）会让跨基本块但已证明等价的表达式获得同一编号。在 SSA 形式中，操作数天然指向清晰定义；支配关系则回答旧结果是否真的可用：旧定义必须支配替换后的使用点。只在某个分支中计算的值，通常不能直接替换汇合点后的计算。

调用、trap 与语义标志

两次 random() 不是公共子表达式。函数可能读取时间、分配对象、执行 I/O、抛异常或观察可变内存。只有被可靠标记为 pure 的调用，才可能在实参相同时复用；readonly 调用虽然不写内存，仍依赖它读取的内存状态。

潜在 trap 也很重要。复用一条支配当前位置的除法通常是合法的，因为若它会 trap，所有到达使用点的路径上都已经发生过；为了制造公共表达式而把除法向前移动则不同，它可能在源程序原本不会求值的路径上引入 trap。

感知内存的 CSE

load 不能只用地址文本作为键。下面第二次读取可能看到新值：

%v1 = load p
store 7, q
%v2 = load p

若 p 与 q 可能别名（alias），store 会让 p 的可用值失效；若别名分析证明二者绝不重叠，%v2 才可以复用 %v1。可能写内存的函数调用也是类似屏障。volatile 与 atomic load 还带有顺序语义，不能像普通读取那样删除。

真实编译器会使用 alias set、内存依赖、Memory SSA 或显式内存值编号。概念上，load 的键同时包含地址与内存版本：

(load, p, memory-version M0) != (load, p, memory-version M1)

合法不等于值得做

CSE 通常有收益，却并非自动有利。复用旧值会延长其 live range，可能增加寄存器压力；省下一条便宜指令，有时反而引发昂贵 spill。在托管运行时中，还可能让大对象或指针存活更久。

生产级 pass 因此要分开判断 legality 与 profitability。前者检查类型、值、副作用、异常和支配；后者估算指令成本、活跃区间增长、代码体积与目标机器行为。测试应覆盖分支汇合、交换操作数、不同 effect 的调用、别名 store、volatile 内存和可能 trap 的表达式。