编译器循环优化技术

可视化演示

循环是程序执行的热点，循环优化对性能提升至关重要。本文详解循环不变量外提、归纳变量消除、循环展开与强度削弱等经... 切换模式查看不同维度。

一、循环不变量外提：把不动的东西请出流水线

整理工位时有个规律：如果一杯水从上班到下班都放在同一个位置，你绝不会每处理一份文件就把它端起来重新放一次。可惜很多程序就是这么写的——循环体里明明有一句“把水杯端到左边”的操作，而水杯从来没动过，于是每轮迭代都白白重复一次。

编译器把这种“每次迭代都一样、与循环变量无关”的表达式称为循环不变量。外提（Hoisting）就是把它从循环体搬到循环外面，只计算一次。看似简单，编译器却要谨慎：外提必须保证不会改变程序语义。比如循环可能一次都不执行，那么被外提的表达式也不能执行；又比如表达式可能触发除零错误，若把它提前到循环前执行，就会在原本不该出错的地方炸掉。因此编译器要用支配关系（Dominance）来确认：被外提的表达式所在的块，必须支配循环的所有出口，且目的块真正支配循环头。

以一个累加为例，若 $c$ 在循环内不随 $i$ 变化：

回到工位的比喻：外提好比把永远固定的台灯从“每次弯腰调整”改成“一开始就摆好”。优化的是频率最高的动作，收益随迭代次数放大，这也是它稳居所有循环优化之首的原因。

二、归纳变量消除：用计数器代替翻字典

假设你的工作是按名单依次叫人，名单每隔 4 行才有一个名字，你每次都要从第 1 行开始数到当前行，才能找到下一个名字——这显然荒唐。聪明的做法是口袋里放一个计数器，每叫完一个人就加 4，永远不用重新数。

循环里的归纳变量就是这种“从第 1 行数起”的变量。设 $i$ 是循环变量（基本归纳变量），$t = 4i$ 由它线性派生而来（派生归纳变量）。编译器发现 $t$ 的值严格随 $i$ 推进后，会引入一个新变量 $t'$，让它在每个迭代自增 4，从而消灭乘法：

工位顾问的视角下，这就是“与其每次重新数，不如记住上次的位置”。归纳变量消除削减的不只是几条乘法指令，它让循环体更扁平，也为后续的循环展开和寄存器分配铺平了道路。

三、循环展开：一把抱起四箱快递

快递员送快递，如果每送到一栋楼就要跑回三轮车取一件，那么 100 栋楼他要折返 100 次。聪明的做法是一次抱上 4 箱，沿路放下。循环展开（Loop Unrolling）就是这个道理：把原来迭代一次的循环体复制多份，然后一次迭代执行多次循环体的内容，从而减少“是否继续循环”的判断与跳转次数。

以展开因子 4 为例，将原本 $n$ 次迭代的循环改写为每轮处理 4 个元素：

展开不是越猛越好：代码体积膨胀会撑爆指令缓存，寄存器分配也会更紧张。这好比一次抱 50 箱快递，未到楼下先把自己累垮。编译器的展开因子通常由代价模型综合指令缓存容量、寄存器数量与数据依赖深度后决定。

四、强度削弱：用加法代替代价高昂的乘法

老花眼的人查词典时，要查“第 5 个词”得从第 1 个词数起，每次都做一次“从头数”的昂贵操作。更聪明的做法是记住上一次查到的位置，下一次只往后挪一格。强度削弱（Strength Reduction）做的正是这件事：把循环中昂贵的运算（乘法、除法、取模）替换为等价的、更廉价的增量运算。

典型的场景是数组寻址。设某次循环体内有 $i \times 2$，虽然它看似简单，但乘法在低端 CPU 上比加法慢 3-5 倍。编译器将其改写为增量变量 $t$：

强度削弱与归纳变量消除是孪生技术，常协同出现。从工位视角看，它是把“搬整箱水”换成“拧开龙头接一杯”——同样的结果，力气省了不止一点。现代 LLVM 的优化管线会在 SSA 形式下自动完成这一类重写，这也是为什么手写汇编往往跑不过 -O2。

五、依赖与并行：先看谁等谁，再决定同时开工

一个人搬砖快，一群人搬砖更快——但前提是大家手里的活互不牵制。如果第二个人必须等第一个人砌好墙角才能递砖，那并行就无从谈起。编译器想并行化循环，第一件事就是做循环依赖分析：判断不同迭代之间是否存在数据上的先后关系。

最常用的刻画工具是距离向量。对于循环：

第 $i$ 次迭代读写 $A[i]$ 与 $A[i-1]$，而 $A[i-1]$ 恰好是上一迭代（$i-1$）写的，因此迭代之间存在“等前一迭代”的依赖，距离为 1：

反过来，如果每个迭代只读写自己的 $A[i]$，距离向量为 $0$ 或相互独立，编译器就会放心地做多核并行或 SIMD。依赖分析是整个循环优化的“安全检查员”——它决定了并行与向量化的合法边界。

for (i = 1; i < n; i++)    A[i] = A[i-1] + 1;

六、向量化与融合：盖一个章代替盖一排章

批量盖章时，逐张盖 100 个章费时费力，换成定制一个大印章一次盖一排，效率立升。循环向量化（Vectorization）就是让 CPU 用一条 SIMD（单指令多数据）指令同时对多个数据执行同一操作。它的前提依然是依赖分析：迭代之间互不干扰，才能把多个标量迭代打包：

除向量化外，循环融合（Fusion）与循环分裂（Fission）也是整理工位的好手段：两个循环遍历同一数组时，融合成一个循环能减少一次整趟内存搬运，提升数据局部性；反过来，一个循环体过于臃肿或存在部分依赖时，拆成多个循环反而能暴露并行机会。现代编译器像一位精准的工位规划师，反复权衡“哪些工序该合并、哪些该拆开、哪些该打包批量处理”。

AI 应用场景

Python 演示

import time N = 10_000_000 def baseline(n):    total = 0    for i in range(n):        total += i * 2 + 1000    return total def hoist_invariant(n):    total = 0    for i in range(n):        total += i * 2    return total + n * 1000 def strength_reduce(n):    total = 0    t = 0    for i in range(n):        total += t        t += 2    return total + n * 1000 def unroll4(n):    total = 0    t = 0    for i in range(0, n, 4):        total += t        t += 2        total += t        t += 2        total += t        t += 2        total += t        t += 2    return total + n * 1000 def time_it(fn):    t0 = time.perf_counter()    r = fn()    return time.perf_counter() - t0, r if __name__ == '__main__':    ans = baseline(N)    for fn in [baseline, hoist_invariant, strength_reduce, unroll4]:        dt, res = time_it(fn)        print(f"{fn.__name__:>16}  {dt*1000:7.2f} ms  result={res}")        assert res == ans, fn.__name__

1. for i in range(n):朴素的循环骨架，每次迭代都执行完整计算。
2. total += i * 2 + 1000原始写法，1000 是不变量，每轮迭代都重复加法。
3. return total + n * 1000不变量外提：循环内不再计算 1000，循环结束后一次性加上。
4. t += 2强度削弱：用增量加法替代 i * 2 的乘法运算。
5. for i in range(0, n, 4):循环展开：步长 4，一次迭代做 4 份工作，减少分支判断。
6. assert res == ans, fn.__name__验证优化后的结果与朴素版本完全一致，保证不改变语义。

常见误区

面试题