编译器优化那些事儿（4）：归纳变量

作者：openEuler

2022 年 7 月 12 日
本文字数：2003 字
阅读完需：约 7 分钟

本文来源公众号毕昇编译

作者孔荔

0. 基础知识盘点

0.1 循环（loop）

定义

loop（llvm 里理解为 natural loop）是定义在 CFG 中的一个结点集合 L，并具有以下属性 [1] [2]：

有单一的入口结点（称为 header），该结点支配 loop 中的所有结点；
存在一条进入循环头的回边。

相关术语

entering block：一个非 loop 内的结点有一条边连接到 loop。当只有一个 entering block 且其只有一条边连接到 header，称之为 preheader；作为非 loop 结点的 peheader 支配整个 loop；
latch：有一条边连接到 header；
backedge：称为回边，一条从 latch 到 header 的边；
exiting edge：一条边从 loop 内到 loop 外，边的出发结点称之为 exiting block，目标结点称之为 exit block；

上面右图中，黄色区域是一个 loop，而红色区域不是，为什么呢？因为红色区域 a 和 c 都是入口结点，不满足单一入口结点的性质。

0.2 Scalar Evolution（SCEV）

定义

SCEV 是编译器对变量进行分析的优化（往往只针对整数类型），且主要用于分析循环中变量是如何被更新的，然后根据这个信息来进行优化。

循环链

如图所示，循环中归纳变量 var 的起始值为 start，迭代的方式为ϕ，步长为 step；

它的循环链（chrec，Chains of Recurrences）如下：

var = {start, ϕ , step}// ϕ∈{+,∗}// start: starting value// step: step in each iteration

复制代码

举个例子：

int m = 0;for (int i = 0; i < n; i++) {  m = m + n;  *res = m;}

复制代码

那么 m 的循环链为：m = {0,+,n}。

1. Induction Variable（归纳变量）

1.1 定义

for (i = 0; i < 10; ++i) {    j = 17 * i;}

复制代码

1.2 益处

归纳变量优化的好处，有但不局限于以下几点：

用更简单的指令替换原来的计算方式。比如，上面的例子中识别到归纳变量，将对应的乘法替换为代价更小的加法。

j = -17;for (i = 0; i < 10; ++i) {    j = j + 17;}

复制代码

减少归纳变量的数目，降低寄存器压力。

extern int sum;int foo(int n) {    int i, j;    j = 5;    for (i = 0; i < n; ++i) {        j += 2;        sum += j;    }    return sum;}

复制代码

当前的 loop 有两个归纳变量：i、j，用其中一个变量表达另外一个后，如下：

extern int sum;int foo(int n) {    int i;    for (i = 0; i < n; ++i) {        sum += 5 + 2 * (i + 1);    }    return sum;}

复制代码

归纳变量替换，使变量和循环索引之间的关系变得明确，便于其他优化分析（如依赖性分析）。举例如下，将 c 表示为循环索引相关的函数：

int c, i;c = 10;for (i = 0; i < 10; i++) {    c = c + 5; // c is incremented by 5 for each loop iteration}

复制代码

转换为：

int c, i;c = 10;for (i = 0; i < 10; i++) {    c = 10 + 5 * (i + 1);  // c is explicitly expressed as a function of loop index}

复制代码

2. 实践

2.1 相关编译选项

2.2 优化用例

归纳变量的优化（ivs）在 llvm 中的位置是：llvm\lib\Transforms\Scalar\IndVarSimplify.cpp让我们通过一个用例，看看毕昇编译器的优化过程。如下图，假设上面 func 里面的部分就是要优化的代码，下面 func 里面就是预期生成的结果：

它的 IR 用例test.ll是：

当前的例子中，header、latch和exiting block都是同一个 BB，即 bb5。

步骤一：依据def-use 关系，遍历loop的 ExitBlock中phi结点的操作数的来源，计算出最终值同时替换它，继而替换该 phi 结点的使用。例子中，计算%tmp2.lcssa ，其唯一的操作数是%tmp2 = add nuw nsw i32 %i.01.0, 3 ，该表达式所在的loop是 bb5，此时%tmp2的循环链为

%tmp2 = {3,+,3}<nuw><nsw><%bb5>

复制代码

获取当前loop的不退出循环的最大值是 199999，那当前%tmp2=add(3, mul(3,199999))=600000；接下来会看当前的替换不是高代价（代价的计算会依据不同架构有所不同），同时在phi结点的user中替换该值。优化结果如下：

步骤二：遍历ExitingBlock，对其跳转条件进行计算，依据def-use的关系，删除相应的指令。例子中，计算出br i1 %0, label %bb5, label %bb7的%0是 false，跳转指令替换后，%0 = icmp ult i32 %tmp4，200000 不存在 user，将其加入到“死指令”中。优化结果如下：