编译器优化：归纳变量与循环依赖

编译器优化中最反直觉的一个结论是：把”昂贵”的操作替换成更便宜的操作，有时反而会让循环变慢。当替换在迭代之间引入了原本不存在的依赖时，这种情况就会发生。编译器理解这一点。而了解它何时适用，对任何需要推理循环性能的人都很有用。

什么是归纳变量？

归纳变量是一个在每次迭代中按固定量变化的循环变量。循环计数器自身就是一个典型例子，但这一术语适用于任何具有该性质的派生量。

考虑一个将数组填充为某常数倍数的循环：

for (int i = 0; i < N; ++i)
    out[i] = i * table;

每次迭代都要从头计算 i * table。一个叫”归纳变量替换”的编译器优化 pass 可以把它变成：

int acc = 0;
for (int i = 0; i < N; ++i) {
    out[i] = acc;
    acc += table;
}

乘法消失，被加法取代。这就是强度削减（strength reduction）：把”强”操作（乘法）替换为”弱”操作（加法）。对于固定延迟的乘法器来说，这通常是有益的。

生成平方序列 —— out[i] = i * i —— 好像也适用同样的处理。数学恒等式 (n+1)^2 = n^2 + 2n + 1 说明连续平方之间相差一个递增的奇数。整个序列可以完全用加法计算出来：

int sq = 0, step = 1;
for (int i = 0; i < N; ++i) {
    out[i] = sq;
    sq += step;
    step += 2;
}

一个乘法都没有。看起来严格更优。但编译器通常不会生成这样的代码。相反，它会生成等价于下面这样的代码：

for (int i = 0; i < N; ++i)
    out[i] = i * i;

每次迭代都使用一条真正的 imul 指令。

问题出在依赖链。

在归纳变量版本中，每次迭代都依赖于上一次迭代的结果。第 k 次迭代的 sq 依赖于第 k-1 次的 sq 和 step。这是一个循环携带依赖（loop-carried dependency）：下一次迭代在前一次完成算术之前不能开始。

在乘法版本中，每一次 i * i 只依赖于 i，而 i 在迭代开始时就已知、与上一次迭代发生了什么无关。现代乱序执行的处理器在找不到迭代间数据依赖时，可以同时执行多次迭代。

下面是用 llvm-mca 在 Haswell 级处理器上的吞吐量对比：

版本	每次迭代周期数	瓶颈
归纳变量（加法）	约 1.5	sq 与 step 的依赖链
直接乘法（imul）	约 1.5	乘法单元的吞吐量

数字接近，但背后的原因很重要。乘法版本触顶，是因为乘法单元每周期只能发射有限数量的操作；迭代之间没有依赖：一个超标量处理器可以让来自不同迭代的多个乘法同时在途中执行。归纳变量版本触顶，是因为依赖链：step 依赖前一次的 step，sq 依赖前一次的 sq 和当前的 step。

在实践中，乘法版本往往更稳健。它的指令更少、不需要维护第二个状态变量、吞吐量的极限相当。在更复杂、执行资源被其他操作争用的循环中，归纳变量版本可能进一步落后，因为依赖链把工作串行化了。

每一个”用 A 替换 B”的优化都必须考虑完整的代价模型，包括：

当被替换的操作开销昂贵、且替换没有引入新依赖时，强度削减是有益的。当替换创造出此前不存在的依赖链时，收益可能为负。

现代编译器会显式建模这一点。归纳变量优化 pass 知道某次替换是否会引入循环携带依赖，以及目标 CPU 的乱序执行能否隐藏这个依赖。对于 x86 上的平方情形，分析的结论是：乘法版本至少一样快，而且结构更简单。于是不进行这种替换。

这是”更便宜的操作 = 更快”这种直觉失效的场景之一。imul 指令的延迟比 add 高 —— 三个周期对一个周期 —— 但循环使用它依然一样快，因为多个 imul 的实例可以在执行流水中重叠。

在把一个循环手工改写为”用加法代替乘法”之前，值得问问：这个变换是否创造了原本不存在的依赖？如果是，正确的工具是用真实数据在目标硬件上做基准测试，而不是假设”操作开销下降”就等于”运行时间下降”。

编译器在平方那个例子中保留乘法，并不是保守、也不是漏掉了某个优化。在对”硬件如何执行循环”有准确建模的前提下，这是正确的决定。