Loop Optimization in Compiler

0. 概览

之前，我们已经讨论过常量传播、死代码消除等优化算法。这可以帮助我们在写出“不好的”代码时进行充分的优化。但是，如果一个人的代码确实是“好”的（在SCCP/ADCE）的角度下，那我们应该如何优化？

这个时候，我们便必须考虑循环优化。可以想见，一份代码中耗费时间最长的部分可能就是循环，那么显然优化循环是非常有价值的。

这里讨论的循环优化主要包含循环不变量外提/归纳变量强度削弱/循环展开等算法。（如果高编讲了的话，或许会更新一下多面体模型）

1. 如何识别循环

直观上来说，循环就是一个基本块序列，其末尾能跳回开头。这里我们给出更加准确/形式化的定义，即循环是一个包含满足以下性质的头结点 $h$ 的结点集合 $S$：

• $S$ 中每个结点都能到达 $h$。
• $h$ 能到达任何 $S$ 中的每个结点
• 没有 $S$ 外的结点到 $S$ 中非头结点的边。

但按照这种定义来构建循环是较为困难的。这个时候我们考虑必经结点树。

考虑这张图，我们发现循环的另一个根本元素是一条回到头结点的边，称为回边。显然，头结点一定是循环内任何结点的必经结点，因而我们可以通过“指向必经结点的边”来识别出所有头结点和回边。进而根据上面的定义

2. 循环不变量计算

3. 归纳变量/强度削弱

直观来说，归纳变量说的是，如果循环中有一个以 $t$ 递增的变量 $i$，和一个等于 $i\cdot b + c$ 的变量 $j$。如果 $b, c$ 均为循环不变量，那么就可以用 $t\cdot b$ 来递增 $j$。

举个例子：考虑这么一段代码。

int main() {
    int a = getInt(), b = getInt(), c = getInt(), d = getInt();

    int sum = 0, j = 0;

    for (int i = 0; i < 10; ++i) {
        j = 4 * i + 2;
        sum = sum + j;
    }

    printlnInt(sum);
}

我们可以发现，我们完全不需要每次在循环中进行乘法，只要每次以 $4$ 递增变量 $j$ 就行了。

归纳变量变形的优化主要分为这么几步：第一，我们要从像 $i$ 这样的基础归纳变量 (basic induction variable) 开始发现导出归纳变量 (derived induction variable)，接着通过强度削弱 (strength reduction) 把原来的乘法变为加法。

3.1 发现基本归纳变量

正如之前所说，如果在循环 $L$ 中，变量 $i$ 只有一个 $i \leftarrow i +c$ 的定值，其中 $c$ 是一个循环不变量，那么 $i$ 就是循环 $L$ 的基本归纳变量。

由于 llvm 是 SSA 的，我们可以注意到这样的 $i$ 的定值一定具有这样的形式：

%i_phi_0 = phi i32 [ %inc_0, %for.inc_0 ], [ 0, %enter_main_0 ]
%inc_0 = add i32 %i_phi_0, 1

这样的话，我们只需要找到循环头结点中所有的 $\phi$ 指令，考察其是否有两个分支，且其中一个在循环外，另一个再循环内且是循环外的那个来源加上一个循环不变量即可。

3.2 发现导出归纳变量