5.1 局部与全局优化

5.1 局部与全局优化

本节摘要：局部优化在基本块内重写指令——不需要任何分析，代价近零，收益看运气；全局优化跨块推理——依赖第4章的数据流分析，能证明"这个值一定是常量""这段代码一定死"。本节先用一个基本块展示常量折叠、代数化简、块内公共子表达式消除的三连改写，再演示全局常量传播与死代码删除如何吃掉跨块的机会，最后交代稀疏条件常量传播（SCCP）为什么在 SSA 上如鱼得水。读完你应当能对一段 IR 手工执行两档优化，并说清每一笔收益背后的"证据"是什么。

第4章攒下的分析，从本节开始兑换成更快的代码。兑换有两个档次：不花分析成本的"顺手赚"（局部），与花分析成本换跨块收益的"推理赚"（全局）。前者是流水线的清洁工，后者才是主力部队。

一、局部优化：基本块内的三连改写

看一个基本块（x 入块时非常量，a 为常量 4）：

t1 = 4 * 2          常量折叠 →  t1 = 8
t2 = x * 1          代数化简 →  t2 = x
t3 = x * 0          代数化简 →  t3 = 0        （注意：x 含副作用的读法要先保住）
t4 = a + t1         常量折叠 →  t4 = 12
t5 = x * x          ┐
t6 = x * x          ┘ 块内 CSE → t6 = t5
t7 = 12 + 0         折叠+化简 →  t7 = 12
​

三个回合下来，7 条算术指令压到 4 条。规则本身平淡无奇，要点全在边界上：

• 代数化简要过活脑子。x * 0 → 0 对整数成立，对浮点不成立（x = NaN 或 ±Inf 时乘 0 仍是 NaN/Inf）；x + 1 - 1 → x 对浮点也不总是合法（舍入）。浮点版本的化简必须确认 fast-math 标志，这是数值代码"开了优化结果变了"的经典来源。
• 常量折叠管"编译期算得出"，跟运行期无关的纯计算能在编译期算掉；折叠的深度受值域分析影响——这正是局部与全局的分界线。
• 块内 CSE 的实现就是 3.4 提过的值编号：给表达式算个"指纹"塞哈希表，第二次出现直接复用。块内做这个零风险（无控制流分岔），出了块就要靠全局分析背书。

局部档的天然局限：基本块是直线代码，块与块之间的机会一个也看不到。跨块的机会是全局档的猎物。

二、全局优化：让分析背书的跨块改写

全局常量传播把 4.1 的常量格（⊤/常量/⊥）配上第4章的不动点引擎：

B0: flag = 1
    x = 17
    if flag goto B1 else goto B2      # flag 是常量 → 分支定一死一
B1: y = x + 5                         # y = 22
    goto B3
B2: y = 99                            # 死代码：永远到不了
B3: use y                             # y = 22（两路汇合后仍是常量）
​

到达定值与常量传播联手证明三件事：flag 恒为 1（分支可折叠）、B2 整块死亡、y 在 B3 恒为 22。注意 B3 能"确定 y=22"靠的是 meet(22, 22)=22——两条路径值一致，常量身份穿越了汇合点。这就是全局档与局部档的本质差距：局部优化在 B3 只知道"y 来自某条 phi"，全局优化知道"phi 的两个输入是同一个常量"。

全局死代码删除消费 4.2 的活跃变量：定值后变量立刻不活跃 → 删除，删除使其他定值失活 → 级联。SSA 上这个判定退化成"数引用"（def-use 计数为零即死），3.2 的第三项红利在此兑现——SSA 版的 DCE 不需要迭代分析，一遍收工。

**稀疏条件常量传播（SCCP）**是全局常量传播的加强版：它额外沿控制流的可行路径传播，能把"分支两边各定义一个常量、条件恰好吃其中一边"的情形也算准。SSA 的 phi 让"路径分歧"显式化，SCCP 的工作表算法直接在 SSA 图上做格运算——表示与分析的匹配度，决定了优化的成本曲线，这是本册反复出现的主题。

三、证据链与取舍：优化为什么"宁缺毋滥"

每个全局优化 pass 的合法性都挂在一条证据链上：改写保义（变换封闭性）← 分析过近似（may/must 方向正确）← 格有穷（迭代收敛）。三环任何一环松了，优化就从"加速"变成"变错"。工程上的三条推论值得记住：

1. 别名是内存优化的天敌。死存储删除看到 *p = 1; *q = 2 不敢删前者，除非 4.5 的别名分析断言 p、q 不同址。指针一多，全局优化的单子大面积缩水。
2. 编译期开销也是成本。全局 pass 的分析代价与函数规模成正比，JIT 场景下会精挑"性价比 pass"；AOT 编译则可以豪横些。优化不是免费的午餐，是预算分配。
3. 多轮迭代是常态。DCE 删掉的代码可能让常量传播看到新事实，常量传播折叠的分支又暴露新死代码——产品编译器的优化流水线把 pass 排成循环，直到"改无可改"。7.3 的 pass 分类表里会看到这种"clean-up pass 群"的编排。

💡 关键直觉：判断一个优化"敢不敢做"，永远问两个问题——它的证据是什么分析给的？证据被打破时（别名、副作用、浮点、溢出）它退到哪里？答得上来，你就理解了这个 pass。

本节要点回顾：

• 局部三件套：常量折叠、代数化简、块内 CSE，零分析成本，浮点语义是雷区；
• 全局双主力：常量传播（不动点 + 格）、死代码删除（活跃性或 SSA 引用计数）；
• SCCP：沿可行路径传播常量，SSA 的 phi 让路径显式，分析成本大幅稀疏化；
• 证据链：变换封闭 + 过近似方向正确 + 格有穷收敛，三环缺一就是 bug；
• 预算意识：别名精度、编译时间、多轮迭代，全局优化的每个单子都标着价。

基本块与跨块的机会都扫过了，但程序的大头时间在循环里——那是另一套专门武器的战场。下一节进循环。

变式演练：一段代码的优化清单

检验学的最好方式是把一个例子从头吃到尾。给定：

B0: x = 5
    y = x * 2          # 全局常量传播的靶
    if x > 0 goto B1 else goto B2
B1: z = y + 1          # y 恒 10 → z 恒 11
    goto B3
B2: z = 0              # 不可达：分支被折叠后整块死亡
B3: w = z * 1          # 代数化简的靶
    return w
​

按依赖顺序列出能用到的优化：常量传播证明 x=5 → y=10；**分支折叠**（SCCP 的本领）把 if x > 0 定为恒真，B2 失去全部来路；**死代码删除**清掉 B2 整块与相关的 phi；**代数化简**把 z * 1 折叠为 z；最后一轮**常量传播**把 w 定为 11，return 11。全程没有任何一个 pass 单独做完这件事——常量传播喂分支折叠，分支折叠喂死代码删除，代数化简再扫尾。这个链式反应解释了 7.3 那句"收益不可加"：单独关掉任何一个 pass，终点都到不了 return 11。

顺手自测两个判断：为什么 B2 的 z=0 不能"留着防万一"？（分支折叠已证明不可达，留着只添干扰。）为什么 w = z * 1 不能在 B1 折叠前化简？（可以——代数化简不依赖常量性，任何时候都能做；它的产出只是恰好等折叠后再确认一遍。）