[译]LLVM如何优化函数

作者： John Regehr

原文地址： https://blog.regehr.org/archives/1603

一个优化的、领先的编译器通常被组织为：

1. 一个将源代码翻译为一个中间表示（ IR ）的前端。
2. 一个目标无关的优化流水线：一系列遍，它们持续重写 IR ，以消除低效性以及不能容易翻译为机器码的形式。有时称之为“中端（ middle end ）”。
3. 一个目标相关的后端，生成汇编代码或机器码。

在某些编译器中，在整个优化流水线中 IR 格式保持不变，在其他编译器里，格式或语义改变。在 LLVM 里，格式与语义是固定的，因此，在不引入错误编译或导致编译器崩溃的情况下，应该可以运行任何你希望的遍序列。

优化流水线中的遍序列由编译器开发者设计；其目标是在合理的时间内完成相当好的工作。它不时会被调整，当然，在每个优化级别，运行着不同的遍集合。编译器研究中的一个长期存在的话题是，使用机器学习或其他方法来提供更好的优化流水线，无论在一般的还是特定的应用领域，缺省流水线都不能出色工作。

遍设计的一些原则是最小性与正交性：每个遍应该做好一件事，在功能上不应该有太多的重叠。在实践中，有时会做出妥协。例如，当两个遍倾向于重复为彼此生成工作，它们可能被整合为单个、更大的遍。同样，某些 IR 层面的功能，比如常量折叠是如此广泛使用，作为一个遍是不合理的；例如， LLVM 在创建指令时隐含折叠掉常量操作。

在本文中，我们将看一下某些 LLVM 优化遍如何工作。我将假设你已经看过了 这篇 关于 Clang 如何编译一个函数或者你或多或少知道 LLVM IR 怎么工作。理解 SSA （静态单赋值）形式特别有用： Wikipedia 将是很好的起点， 这本书 包含了比你可能希望知道的更多的信息。另外，参考 LLVM语言参考 与 优化遍列表 。

我们将研究 Clang/LLVM 6.0.1 如何优化这个 C++ 代码：

1 2 3 4 5 6

bool is_sorted(int *a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; }

记住优化流水线是一个忙碌的地方，我们将略过许多有趣的东西，比如：

• 内联，一个容易但超级重要的优化，它不会在这里出现，因为我们只看一个函数
• 基本上相对 C ，特定于 C++ 的所有东西
• 自动向量化，它被早期循环退出所挫败

在下面我将跳过不改变代码的每个遍。同样，我们不会看后端，在那里也有很多遍。即使这样，这将是一个有点艰难的过程！（抱歉在下面使用图形，但它看起来是避免格式难题的最好方式，我讨厌与 WP 主题斗争。点击图形获取更大的版本。我使用 icdiff ）。

这里是Clang发布的IR文件格式 （我手动删除了 Clang 放入的“ optnone ”属性），下面是我们可以用于查看每个优化遍效果的命令行：

opt -O2 -print-before-all -print-after-all is_sorted2.ll

第一个遍是“ 简化CFG （控制流图）”。因为 Clang 不进行优化，它发布的 IR 通常包含清除的机会：

这里，基本块 26 只是跳转到块 27 。这类块可以被消除，到它的跳转将被转发到目标块。 Diff 更令人困惑，因为由 LLVM 执行的隐含的块重编码。 SimplifyCFG 执行的整组转换列出在遍头部的注释里：

这个文件实现死代码消除与基本块合并，连同一组其他窥孔控制流优化。例如：

• 删除没有前驱的基本块。
• 如果仅有一个前驱且该前驱仅有一个后继，将基本块与且前驱合并。
• 消除只有一个前驱的基本块的 PHI 节点。
• 消除仅包含无条件分支的基本块。
• 将 invoke 指令改为调用 nounwind 函数。
• 把形如“ if (x) if (y) ”的情形改为“ if (x&y) ”。

CFG 清理的大多数机会是其他 LLVM 遍的结果。例如，死代码消除与循环不变代码移动可以容易地创建空基本块。

下一个运行的遍， SROA （聚集对象的标量替换， scalar replacement of aggregate ），是我们其中一个重量级击打者。这个名字有点误导，因为 SROA 仅是它其中一个功能。这个遍消除每条 alloca 指令（函数域的内存分配）并尝试把它提升到 SSA 寄存器。在 alloca 被多次静态分配，或者是一个可以被分解为其组成的 class 或 struct 时（这个分解就是这个遍名字中提到的“标量替换”），单个 alloc 将被转换为多个寄存器。 SROA 的一个简单版本会放弃地址被获取的栈变量，但 LLVM 的版本与别名分析相互作用，是相当智能的（虽然在我们的例子里这个智能是不需要的）。

在 SROA 后，所有 alloca 指令（以及它们对应的 load 与 store ）都消失了，代码变得干净得多，更适合后续的优化（当然， SROA 通常不能消除所有的 alloca—— 仅在指针分析可以完全消除别名二义性时，这才能工作）。作为这个过程的部分， SROA 必须插入某些 phi 指令。 Phi 是 SSA 表示的核心，由 Clang 发布代码缺少 phi 告诉我们， Clang 发布 SSA 的一个平凡类型，其中基本块间的通信是通过内存，而不是通过 SSA 寄存器。

接下来是“ 早期公共子表达式消除 ”（ CSE ）。 CSE 尝试消除人们编写的代码和部分优化的代码中出现的冗余子计算。“早期 CSE ”是快速的，一种查找平凡冗余计算的简单 CSE 。

这里 %10 与 %17 做相同的事情，因此其中一个值的使用可以被重写为另一个值的使用，然后消除了冗余指令。这让我了解一下的 SSA 的优点：因为每个寄存器仅分配一次，没有寄存器多个版本这样的东西。因此，可以使用语法等价检测冗余计算，不依赖更深入的程序分析（对内存位置不成立，它在 SSA 世界之外）。

接着，运行几个没有影响的遍，然后是“ 全局变量优化器 ”，它自述为：

这个遍将改变简单的、地址没有被获取的全局变量。如果显然成立，它将读 / 写全局全局标记为常量，删除仅写入的变量等。

它进行了这个改变：

添加的东西是一个函数属性：由编译器一部分用来向另一个部分保存可能有用的事实的元数据。你可以在 这里 读到关于属性的基本原理。

不像我们已经看过的其他优化，全局变量优化器是过程间的，它查看整个 LLVM 模块。模块或多或少等价于 C 或 C++ 中的编译单元。相反过程内优化一次仅查看一个函数。

下一个遍是“ 指令合并器 ”： InstCombine 。它是一大组多种多样的“窥孔优化”，它们（通常）将一组由数据流连接的指令重写为更高效的形式。 InstCombine 将不改变函数的控制流。在这个例子中，它没有太多事情可做：

这里不是从 %1 减去 1 来计算 %4 ，我们决定加上 -1 。这是一个规范化而不是优化。当有多种方式表示一个计算时， LLVM 尝试规范化到一个形式（通常任意选择），这个形式是 LLVM 遍与后端期望看到的。由 InstCombine 进行的第二个改变是将计算 %7 与 %11 的两个符号扩展操作规范化为零扩展（ zext ）。在编译器可以证明 sext 的操作数是非负时，这是一个安全的或转换。这里就是这个情形，因为循环归纳变量从零开始，在到达 n 之前停止（如果 n 是负的，循环永远不会执行）。最后的改变是向产生 %10 的指令添加“ nuw ”（没有无符号回绕）标记。我们可以看到这是安全，通过观察到（ 1 ）归纳变量总是递增的，（ 2 ）如果一个变量从零开始且递增，在到达仅次于 UINT_MAX 的无符号回绕边界前，穿过仅次于 INT_MAX 的有符号回绕边界，它将变成未定义的。这个标记可用于证明后续优化的合理性。

接着， SimplifyCFG 第二次运行，删除两个空的基本块：

“ 推导函数属性 ” 一步修饰函数：

“Norecurse” 表示该函数没有涉及在任何递归循环中，而一个 “readonly” 函数不改变全局状态。在函数返回后，不保存“ nocapture ”参数，而“ readonly ”参数援引没有被函数修改的储存对象。参考 完整函数属性集 与 完整的参数属性集 。

接着，“ 偏转循环 ”移动代码，尝试改进后续优化的条件：

虽然这个 diff 看起来有点令人担忧，但发生的事情并不多。通过要求 LLVM 绘制循环偏转前后的控制流图，我们可以更容易看到发生了什么。下面是前（左）后（右）的视图：

原始的代码仍然匹配由 Clang 发布的循环结构：

initializer

goto COND

COND:

if (condition)

goto BODY

else

goto EXIT

BODY:

body

modifier

goto COND

EXIT:

而偏转循环是这样的：

initializer

if (condition)

goto BODY

else

goto EXIT

BODY:

body

modifier

if (condition)

goto BODY

else

goto EXIT

EXIT:

（以下是 Johannes Doerfert 提出的更正——感谢！）

循环偏转的要点是删除一个分支并激活后续优化。我在网上没有找到这个转换的更好的描述（看起来介绍了这个术语的 论文 似乎完全不相关）。

CFG 简化折叠掉了两个仅包含退化（单输入） phi 节点的基本块：

指令合并器将“ %4 = 0 s< (%1 – 1) ”重写为“ %4 = %1 s> 1 ”，这种操作很有用，因为它减少了依赖链的长度，还可能创建死指令（参考使得这发生的 补丁 ）。这个遍还消除了另一个在循环偏转期间增加的平凡 phi 节点：

接着，运行“ 规范化自然循环 ”，它自述为：

这个遍执行几个转换将自然循环转换为更简单的形式，这使得后续分析与转换更简单、高效。循环头前（ pre-header ）插入确保从循环外部到循环头有单个非关键入口边。这简化了若干分析与转换，比如 LICM 。

循环退出块插入确保循环的所有退出块（前驱在循环内的循环外部块）仅有来自循环内部的前驱（因而由循环头支配）。这简化了构建在 LICM 里诸如储存下沉（ store-sinking ）的转换。

这个遍还保证循环将仅有一条回边。

间接 br 指令引入几个复杂性。如果该循环包含一条间接 br 指令，或由一条间接 br 指令进入，转换该循环并得到这些保证可能是不可能的。在依赖它们之前，客户代码应该检查这些条件成立。

注意 simplifycfg 遍将清除被拆分出但最终无用的块，因此使用这个遍不应该对生成的代码感到悲观。

这个遍显然修改了 CFG ，但更新了循环信息与支配者信息。

下面我们可以看到插入了循环退出块：

接下来是“ 归纳变量简化 ”：

这个转换分析并把归纳变量（以及从它们导出的计算）转换为适合后续分析与转换的更简单形式。

如果循环的行程计数是可计算的，这个遍也进行下面的改变：

1. 循环的退出条件被规范化为将归纳变量与退出值比较。这将像“ for (i = 7; i*I < 1000; ++i) ”的循环转换为“ for (i = 0; i != 25; ++i) ”
2. 从归纳变量推导的表达式在循环外的任意使用被改变为计算循环外的推导值，消除了对归纳变量推导值的依赖。如果循环的仅有目的是计算某个推导表达式的退出值，这个转换将使得这个循环死亡。

这个遍的效果只是将 32 位归纳变量重写为 64 位：

我不知道为什么 zext—— 之前从 sext 规范化的——被转换回 sext 。

现在“ 全局值编号 ”执行一个非常聪明的优化。展示它基本上是我决定写这个博客的整个原因。看你是否能通过这个 diff 找出它：

找到了吗？左边循环里的两个 load 对应 a[i] 与 a[i+1] 。这里 GVN 断定载入 a[i] 是不必要的，因为来自一次循环迭代的 a[i+1] 可以转发到下一次迭代作为 a[i] 。这个简单的技巧将这个函数发出的载入数减半。 LLVM 与 GCC 都是最近得到这个转换的。

你可能问自己，如果比较 a[i] 与 a[i+2] 这个技巧是否仍然奏效。事实证明， LLVM 不愿意或不能够这样做，但对这个问题 GCC愿意丢弃最多4个寄存器 。

现在运行“ 比特追踪死代码消除 ”：

这个文件实现了比特追踪死代码消除遍。某些指令（偏转，某些 and 、 or 等）终结某些输入比特。我们追踪这些死比特并删除仅计算这些死比特的指令。

但事实证明这个额外的清理是不需要的，因为仅有的死代码是 GEP ，它是明显死的（ GVN 删除了之前使用它计算的地址的 load ）：

现在指令合并器将一个 add 下沉到另一个基本块。将这个转换放入 InstCombine 背后的基本原理我不清楚；也许没有比这更明显的地方了：

现在事情有点奇怪了，“ 跳转线程化 ”撤销了“规范化自然循环”之前做的事情：

然后我们规范化它回来：

CFG 简化又把它翻过来了：

又回来：

又回去：

又回来：

又回去：

哦，我们终于完成了中端（ middle end ）！右边的代码是（在这个情形里）传递给 x86-64 后端的代码。你可能想知道在遍流水线末尾的震荡行为是否是编译器的缺陷，但记住这个函数真的是简单，在翻来覆去中混合了一大群遍，但我没有提到它们，因为它们没有改变代码。就中端优化流水线的后半部分而言，我们基本上在这里看到的是一个退化的执行。

致谢 ：这个秋天在我先进编译器课程里的一些学生，对本文的初稿提供了反馈（我也将这个材料作为一个任务）。我在这篇关于循环优化的 优秀课堂讲稿 里偶然碰到了这个函数。