5.3 循环优化：热点上的投资

5.3 循环优化：热点上的投资

本节摘要：程序九成时间耗在一成代码上，循环是这成一成的大本营。本节学习三台循环专用手术：不变式外提（把循环不变的计算挪到入口）、强度削弱与归纳变量替换（把循环内的乘法降成加法）、循环展开（用体积换并行度），并用主线语句演示外提的完整安全性论证。

阅读完本节，你应当能够：

1. 用回边识别自然循环，判定循环不变式
2. 论证一条指令外提的三个安全性条件
3. 执行强度削弱与归纳变量替换并写出前后对照
4. 说明循环展开的收益条件与代价

找到循环：回边与自然循环

流图上，支配关系是关键：若从入口到 n 的每条路径都必经 d，则 d 支配 n。若 n 支配着它的前驱 m（即存在边 m → n 且 n 支配 m），这条边是回边，回边的自然循环是"能不经过 n 到达 m 的所有节点加 n"。说得直白：循环就是从里面绕回头的部分。主线语句放进一个循环后：

循环（ qty 为每圈递增的计数，n 为圈数上界）：
i = 0
L1: if i >= n goto L2        ← 循环头
    t1 = cvt_float(qty)       ← qty 循环内不变？设不变
    t2 = price * t1           ← price 也设为不变
    t3 = t2 - discount        ← discount 不变
    total = total + t3
    i = i + 2                 ← i 每圈加 2
    goto L1
L2: ...
​

六条指令在循环体里，每圈都白算一遍前三条——手术台已经备好。

手术一：不变式外提

判定"不变式"：操作数在循环内不改（或本身是常量、或定值都在循环外）。t1、t2、t3 三条全符合。外提还要过三道安全门：

外提 x = y op z 到循环入口前的条件：
一、该指令所在块支配循环的所有出口（否则有的圈根本没执行它，外提反而多算）
二、循环内没有对 x 的其他定值（否则提走的是错的那次）
三、循环内对 x 的唯一引用就是这条指令自己（引用别处的 x 可能在等循环内的值）
外加：指令不会触发循环内本不发生的异常（除法挪出循环要小心除零）

本例验证：三条定值块是循环头之后唯一路径上的块，支配出口；t1、t2、t3 各只有一次定值、一次引用；无除法。三门全过。

外提后：
t1 = cvt_float(qty)
t2 = price * t1
t3 = t2 - discount           ← 三条挪到循环入口之前
i = 0
L1: if i >= n goto L2
    total = total + t3       ← 循环体只剩两件事
    i = i + 2
    goto L1
​

每圈省三条指令，n 圈省 3n 条——循环越大，外提的杠杆越长。

手术二：强度削弱与归纳变量

i 每圈加 2，是基本归纳变量；任何形如 j = c 乘 i 加 d 的变量与 i 线性同步，是派生归纳变量。派生变量的乘法可以降级成加法：j 每圈只需加 2c，乘法彻底消失。

设循环里还有 j = 4 * i（用于索引数组）：

强度削弱：在循环入口算一次 j0 = 4 * 0 = 0
循环体内把 j = 4 * i 替换为 j = j + 8     ← 乘法变加法

归纳变量替换：i 的唯一用途若是比较 i >= n 和自增，
则可引入新比较 j >= 4*n（出口测试同步改写），i 整个删除

i 被删后的循环体：
L1: if j >= bound goto L2    ← bound = 4*n 在入口算好
    total = total + t3
    j = j + 8
    goto L1
​

三条指令的循环体，无乘法、无冗余比较。真实编译器对数组下标的处理基本都走过这条路——下标 a[i] 的地址计算原本每次都是乘加混合，削弱后每圈只做一次加法。

手术三：循环展开

展开把循环体复制 k 份、步长乘 k，圈数除 k。收益有三：跳转指令减少（每圈一次变每 k 圈一次）、指令间并行机会增多（多份计算可流水）、为向量化铺路。代价同样三条：代码体积膨胀（指令缓存压力）、k 的选择依赖微架构、循环次数非 k 倍数时要留收尾代码。

展开 k=2 的示意（配合常量圈数 n 为偶数）：
L1: total = total + t3       ← 第一份
    total = total + t3       ← 第二份
    j = j + 16               ← 步长翻倍
    if j < bound goto L1     ← 判定减半
​

图 三台循环手术的前后对照

⚠️ 常见坑：外提条件一（支配所有出口）最常被忽视。若 t2 的计算在"循环走捷径"的分支上，某些圈根本不执行它，外提后每圈都算，白白做了功；更糟的是若该指令有副作用（如可能的异常），外提直接改变可观察行为。教科书上"代码提升必须支配出口"的定理，条款一就是为这个立的。

💡 关键直觉：循环优化的共同思想是"把每圈做的事搬到只做一次的地方"。外提搬计算，削弱把乘法序列降为加法序列（预付一次乘法），展开把判定摊薄。识别"圈与圈之间不变的东西"，是读懂一切循环优化的钥匙。

热点之外的冷思考

问：外提会不会让程序变慢？ 会。极端情形：循环一次都不执行时，外提的指令纯属白算——若外提的指令代价高（函数调用、除法）且循环经常零次执行，性能净亏。工业编译器会评估循环执行概率（用分支预测或运行时档案），低概率入口的外提会更谨慎，这是优化启发式里少见的带概率决策。

问：编译器自动展开还是手写展开？ 通用循环交给编译器，形态特殊的循环（尾处理复杂、需要部分展开配合访存对齐）手工干预仍有价值。现代写法倾向于用编译指令提示展开因子，把循环本体保持可读——手写展开的老代码迁到新编译器上，常因干扰向量化判断而变慢，这提醒我们：给优化器留空间，有时比自己动手更划算。

补一问：怎么知道循环里哪个变量是不变的？ 形式化做法：对循环的每个变量求到达定值集合，若某变量的所有定值点都在循环外，它在循环内不变。工程做法：保守假设一切可变，只对能证明的（常量赋值、外层输入且无写入指令）标不变。证明责任在编译器，证明不了的优化只能放弃——这条规则贯穿全章。

本节要点回顾

• 回边找循环：支配关系识别回边，回边圈出自然循环
• 外提三门：支配所有出口、循环内唯一定值、唯一引用；外加无异常风险
• 强度削弱：派生归纳变量的乘法降级为加法，索引计算的通例
• 归纳变量替换：出口测试同步改写后，基本归纳变量可整体删除
• 展开的价目表：减跳转、增并行、铺向量化；换体积膨胀与收尾复杂度

单循环的账算完了，下一节升空看全局：数据流分析如何给跨块优化发通行证。