经典优化

优化有两个独立问题：变换是否合法，合法变换是否值得。少一条指令、少一次调用或更少源码都不自动回答这两个问题。正确性依赖源语言与 IR 的语义，收益则依赖目标和工作负载。

这些优化并非只能在 SSA 上实现，也不都具有统一的线性复杂度。SSA 提供显式 def-use 等便利，实际算法还涉及控制流、别名、成本和编译时间预算。

常量折叠与传播

折叠在编译时求出已知表达式的值，例如整数 2+3 得 5；传播把已知常量带到使用位置，继而触发更多折叠。SCCP 还同时跟踪可执行控制流边，利用常量条件排除不可能分支。

x*0→0 是代数化简，不是所有操作数都为常量的折叠。其合法性取决于语义：IEEE 浮点里的 NaN、无穷和有符号零会破坏某些实数代数恒等式；如果 x 来自有副作用的表达式，删除其求值也需证明。LLVM IR 的 poison、undef 和相关标志也有独立规则。LLVM UB 手册

SSA 中唯一的静态定义不代表值一定是常量，φ 与循环仍然需要分析。条件传播也不意味着被删分支在语言前端永远无需语法或类型检查。

CSE 与 GVN：找到可复用的值

两次 b+c 若操作语义、操作数与可见状态一致，后一次可能复用前一次结果。已有值必须在需要它的路径上可用；一个只在 if 左分支算出的值，不能直接替换右分支里的计算。

GVN 用值编号识别等价关系，可能比逐字匹配表达式更强。处理 load 时还要证明期间没有可能别名的写入或调用改变内存。两条指令文本相同，但读到的状态不同，就不是可替换的值。

复用也可能延长某个结果的活跃范围，增加寄存器压力，因此合法的 CSE 不保证总能加速。

相同的 load，隔着一次可能别名的 store

下面两次读取的源码都是 *p，但 q 可能指向同一对象。若 p=q 且初值为 3，第一次读到 3，写入 7 后第二次读到 7，结果是 10；直接复用第一次读取会错误地算成 6。

/* alias.c */
static int original(int *p, int *q) {
    int before = *p;
    *q = 7;
    return before + *p;
}
static int wrong_reuse(int *p, int *q) {
    int before = *p;
    *q = 7;
    return before + before;
}
int main(void) {
    int a = 3, b = 3;
    if (original(&a, &a) != 10) return 1;
    if (wrong_reuse(&b, &b) != 6) return 2;
    a = 3; b = 0;
    if (original(&a, &b) != 6 || b != 7) return 3;
    return 0;
}

这个反例没有违反别名约定，两种指针关系都属于函数允许的输入。若接口额外采用 restrict 等承诺，优化器可能利用更强事实，但调用方也必须满足相应规则；不能给函数随手加上承诺，再把原本允许的别名调用继续当作等价性测试。

两次相同的 load，读到的还是同一份状态吗？

这一变换需要的是不会被中间写入影响的证据，不是某一次数值碰巧相同。让 q 指向 A 并把写入值也设为 3，两种程序会同样得到 6，但别名风险并未消失。再改成 7，反例立即出现。若 q 指向独立 B，则该 store 不改变 A，本例中的后一次 load 才有可复用的依据。

DCE 与 DSE：结果不用，不等于行为可删

纯计算结果没有使用者时，可以递归删除；其操作数定义也可能随之变成死代码。副作用、异常、同步和控制流语义则需要保留或单独证明。

Store 不能仅因为没有 SSA 使用者就删除，但若后续完全覆盖且中间无观察，DSE 可以移除死写。函数调用也并非永远不可删：若已知相关效果、终止及异常属性允许，未使用结果的调用可能被消除。反之，“看起来只是读内存”也不自动表示可删除。

内联：暴露上下文，而不只是去掉 call

把被调函数体引入调用点，可让常量参数、别名关系和控制流条件参与后续优化。成本包括代码膨胀、编译工作、指令缓存与寄存器压力。

只调用一次的函数可能很适合内联，但原定义是否能删除还受导出、地址逃逸等影响。递归也需要限制展开。实际决策以调用点为单位结合成本模型，而不是“一定内联所有小函数”。

LICM：值不变与提前执行安全分开证明

循环不变量的操作数在循环迭代中不变，相关内存也不能被循环写入改变。但移到 preheader 还改变了执行条件：循环可能一次都不执行，原指令也可能位于条件分支。

合法外提需要证明指令可安全推测执行，或通过必经执行条件及其他约束证明提前不会改变行为。Load 要考虑地址有效性和别名，除法要考虑异常语义，调用要考虑效果。不是“无副作用加操作数不变”就完整覆盖所有限制。

外提后还要保留原来使用者所需的值。把原来的赋值直接删掉却不连接后续 use，是错误的教学变换。

用明确异常语义验证零次循环，再补上执行守卫

为避免依赖 C 除零的未定义行为，下面用 Python 的整数除法与异常语义构造教学模型。只考虑非负循环次数；原版与带守卫的外提版应在结果和异常上相同。无守卫版在 n=0、d=0 时额外抛错，构成反例。

def original(n, d):
    total = 0
    for _ in range(n):
        total += 10 // d
    return total


def hoisted(n, d):
    if n == 0:
        return 0
    value = 10 // d
    total = 0
    for _ in range(n):
        total += value
    return total


def wrong(n, d):
    value = 10 // d
    return sum(value for _ in range(n))


def outcome(fn, n, d):
    try:
        return ("value", fn(n, d))
    except ZeroDivisionError:
        return ("error", "division by zero")


for n in range(5):
    for d in (-2, 0, 2, 3):
        assert outcome(original, n, d) == outcome(hoisted, n, d)
assert outcome(original, 0, 0) == ("value", 0)
assert outcome(wrong, 0, 0) == ("error", "division by zero")

守卫有效还依赖本例的具体结构：除法是每次进入循环后必经的纯计算，d 不变，之前没有必须先发生的效果。若除法藏在循环内的另一个条件分支，只证明 n>0 仍不足以外提；若其他操作可能先抛异常，还需保留语言要求的异常先后关系。不能把这段修复推广成任意 LICM 的统一模板。

操作数不变，为什么还不能直接移到循环外？

将结果、异常和除法次数分别列出，是为了先判断合法性，再讨论节省了多少工作。n=0、d=0 是关键反例：原版不执行除法，无守卫版却提前抛错。带守卫版在这个受限循环中恢复了原执行条件。表中的次数只数除法尝试，不是总指令数或实际耗时。

循环展开：用代码大小换控制与并行机会

部分展开复制若干迭代体，并处理剩余迭代；完全展开需要可确定的有限迭代或相应专门化条件。未知次数也可以做带尾部处理的部分展开。

展开可能减少回边开销、暴露指令级并行或帮助向量化，但也可能增加代码体积和 spill。没有所有 LLVM 目标都固定展开两到四次的规则，连续标量 load 也不自动变成合法 SIMD load：边界、对齐、依赖与目标能力仍需检查。

SROA 与 mem2reg：让局部内存状态更容易分析

一个局部聚合对象若地址不逃逸、访问可理解，可以按使用区间等拆解，减少不必要的聚合内存操作。适合的局部槽位还可以提升为 SSA 值，控制流汇合处用 φ 表达。

SROA 不必机械地“一字段对应一个变量”，有些使用会妨碍拆分，有些实现还能直接完成提升。mem2reg 也可处理本来就是标量的合适 alloca，不需要所有场景先经过 SROA。LLVM Pass 说明

Pass 顺序：机会与失效一起产生

内联暴露常量，常量传播删分支，删分支使更多代码无用；展开改变循环结构，后续清理又简化表达式。重复某些变换可以有价值，但编译器不会无限追求饱和，还需控制时间、大小和分析失效。

修改 CFG 后，支配树、循环信息或内存分析可能不再有效。变换必须正确维护或宣布失效相关分析，不能只让输出 IR 表面上看起来合法。

验证与速查

可以结合 IR verifier、反例测试、变换前后差分以及特定范围内的等价性验证。测试应包含边界路径，而不是仅让一个正常输入输出相同。测性能则应观察完整优化流水线后的目标代码。

参考

• LLVM Analysis and Transform Passes。
• LLVM IR Undefined Behavior。

Keywords: optimization, constant propagation, SCCP, CSE, GVN, DCE, DSE, inlining, LICM, unrolling, SROA, mem2reg