Compiler -- Opt

发表于 分类于 ，

概述

代码优化通过对代码进行改写以寻找正确且更优的代码。这里的 “更优” 通常指的是运行时间更短，有时也会优化可执行文件大小，耗电量等方面。

通常在现代编译器中，代码优化部分的代码量占比最大。

中间表示

通常来讲，中间表示（Intermediate Representation, abbr. IR）是一种介于源语言与汇编语言之间的用于进行代码优化的语言。相较于源语言和 AST，它包含了更多程序运行时的细节，因此能够挖掘出更多可供优化的地方；相较于汇编语言，它省略了许多与机器架构相关的细节，因此在 IR 上进行的优化不受架构限制。

各个编译器的中间表示可能是不同的，但通常都是某种三地址码（three-address code）。三地址码中每条指令最多包含一个操作两个操作地址以及一个结果地址，例如表达式 x + y * 2 翻译成三地址码即为：

1
2
t1 = y * 2
t2 = x + t1

三地址码中的 “地址” 可以是常量（2）、源代码中的变量名（x, y）、以及生成的临时变量（t1, t2），其中临时变量可以看成是汇编语言中的寄存器。

控制流图

代码优化的重点在于对控制流（control flow）的分析，控制流图是控制流分析的重要工具。

具体来说，控制流图是由基础块（basic block）为结点组成的图，基础块是一个以标签开始，以跳转语句结束，中间不包含其它标签与跳转语句的一系列指令，因此控制流将会从基础块的第一条语句执行到最后一条语句；控制流图中的边代表了每个基础块后续的基础块。

根据改写的范围可以将代码优化的手段分为三类：

  • 局部优化：对一个控制块中的代码进行改写；
  • 全局优化：对整个控制流图进行改写；
  • 跨过程优化：对子过程进入与返回的边界进行优化。

局部优化

局部优化主要是对指令的简单修改，例如：

  • 简化算术：对于某些算术指令例如 x = x + 0、x = x * 1 可以利用数学方法简化或消除；
  • 常量折叠：对于某些算术指令，若操作数两边都是整数则可以直接在编译器计算出结果，需要注意不同架构可能位数不同导致常量的表示不同；
  • 相同子表达式约分：对于某些指令如 x = y + z; ...; w = y + z，若 x、y 和 z 在中间没有改动，则可以将后面的的指令改为 w = x；
  • 复制传播：若有指令 w = x，可以将 w 改动前的指令中的 w 改为 x（若 x 为常量称作常量传播）；
  • 消除死代码：若某变量赋值后没有被引用，则称该赋值指令为死代码，可以消去；

有时将代码改写成单赋值形式更好处理局部优化，即每个变量在等号左边仅出现一次，这样变量在赋值后即为定值。

需要注意的是每种优化方法本身并不会带来很大的作用，往往需要多种方法同时作用才能有较好的优化效果。编译器优化时通常是反复运用多种优化方法，直至无法进行优化或迭代次数达到上限。

窥孔优化

窥孔（peephole）是指基础块中的一段指令，窥孔优化就是将一小段指令替换成作用相同但是更优的另外一段指令，例如两段指令： 

1
2
addiu $a $a x
addiu $a $a y
可以替换成一段指令： 
1
addiu $a $a x+y
大多数局部优化的方法都可以表达为窥孔优化的形式。

数据流分析

某些在局部优化中使用的优化方法同样可以在全局优化中使用，例如死代码消除和常量传播。但是对于全局优化来说需要分析变量在整个控制流图中的状态才能进行优化。例如对于死代码消除，需要确定在后续的结点中该变量都不会被使用才能进行消除。这类分析便称为数据流分析（data-flow analysis）。

通常来讲，对程序的数据流分析都可以表述为对每条语句通过其相邻语句执行某些规则来更新其中与特定优化方式相关的信息。

常量传播

对于语句 \(s\) 和变量 \(x\)，可以在语句前后定义状态函数 \(C_\mathrm{in}(s, x)\) 和 \(C_\mathrm{out}(s, x)\)，一共有三种状态：

  • 语句未执行或未知，用 \(\bot\) 表示；
  • 变量值为一常数 \(c\)；
  • 变量值不是常数，用 \(\top\) 表示。

对于语句 \(s\) 和变量 \(x\)，若其有前驱语句 \(p_1,\cdots,p_n\)，则有如下规则：

  1. \((\exists i . C_\mathrm{out}(p_i,x) = \top) \Rightarrow (C_\mathrm{in}(s, x) = \top)\)
  2. \((\exists (i,j). C_\mathrm{out}(p_i,x) = c \neq d = C_\mathrm{out}(p_j,x))\) \(\Rightarrow (C_\mathrm{in}(s, x) = \top)\)
  3. \((\exists i. C_\mathrm{out}(p_i,x) = c) \land\) \((\forall j \neq i.C_\mathrm{out}(p_j,x) = c \lor C_\mathrm{out}(p_j,x) = \bot)\) \(\Rightarrow (C_\mathrm{in}(s, x) = c)\)
  4. $(i.C_(p_i,x) = ) (C_(s, x) = ) $
  5. \(C_\mathrm{in}(s,x) = \bot \Rightarrow C_\mathrm{out}(s,x) = \bot\)
  6. \(C_\mathrm{out}(\{x = c\},x) = c\)
  7. \(f(\cdots)\notin c \Rightarrow C_\mathrm{out}(\{x = f(\cdots)\},x) = \top\)
  8. \(x\neq y \Rightarrow C_\mathrm{out}(\{y = \cdots\}, x) = C_\mathrm{in}(\{y = \cdots\}, x)\)

其中的省略号代表其它与变量 \(x\) 无关的语句。

对于某个程序，按如下步骤即可求出某个变量在每个位置的状态：

  1. 对于程序的入口 \(e\)，设置 \(C_\mathrm{in}(e, x) = \top\)，其它位置设为 \(\bot\)；
  2. 重复运用如上的规则直至所有位置都符合如上规则。

同时对于三种状态，有 \(\bot < c < \top\)，小的状态只能变为大的状态，因此每个位置的状态最多只会变两次，由此即可证明如上的算法最终总会结束。

生存期分析

对于一个变量 \(x\)，当满足如下条件时称该变量在语句 \(s\) 处存活：

  • 存在一个使用了变量 \(x\) 的语句 \(s'\)；
  • 存在一条从 \(s\) 到 \(s'\) 的路径，且路径上没有对 \(x\) 赋值的语句；

一个变量在程序中存活的所有位置即为该变量的生存期。需要注意与前面所述的作用域的区别：作用域是变量在编译期的特征，而生存期时变量在运行时的特征。

同样地，对于语句 \(s\) 和变量 \(x\)，可以定义函数 \(L_\mathrm{in}(s, x)\) 和 \(L_\mathrm{out}(s, x)\) 来分析变量 \(x\) 的生存期，其取值为布尔值，且对于语句 \(p\) 及其后继语句 \(s_1,\cdots,s_n\) 和变量 \(x\) 有如下规则：

  1. \(L_\mathrm{out}(p, x) \Leftrightarrow \exists i.L_\mathrm{in}(s_i, x)\)；
  2. \(L_\mathrm{in}(\{\cdots = f(x)\}, x)\)；
  3. \(e \notin f(x) \Rightarrow \neg L_\mathrm{in}(\{x = e\}, x)\)
  4. \(L_\mathrm{in}(\{\cdots\}, x) \Leftrightarrow L_\mathrm{out}(\{\cdots\}, x)\)

对于某个程序，按如下步骤即可求出某个变量在每个位置的状态：

  1. 所有位置初始均设为 false；
  2. 重复运用如上的规则直至所有位置都符合如上规则。

同样地，每个位置状态只会改变一次，因此算法总会结束。

寄存器分配

IR 中的临时变量的数量是无限制的，然而与其对应的各平台上的寄存器数量是有限制的，因此需要为临时变量分配寄存器使多个临时变量对应同一个寄存器并且互不干扰。

如果将每个临时变量视作一个结点，在每个生存期重叠的临时变量间连接一条边，可以生成一个寄存器干涉图（Register Interference Graph, abbr. RIG），图中每条边的端点不能被分配在同一个寄存器中。这样便将寄存器分配的问题转化为了一个图着色问题，每种颜色便代表了一个寄存器。

然而图着色问题是一个 NP 困难问题，因此几乎只能使用启发式方法来寻找近似的方案。其中一种寻找 k 着色的启发式的算法如下：

  1. 寻找一个邻边数量少于 k 的结点，将其放入栈中并在图中删去该结点与其相连的边；
  2. 重复该过程直至图为空图；
  3. 从栈中重复将其中的结点出栈，还原并为结点选择颜色。

算法运行当中可能无法删除结点，此时可认为原图无法进行 k 着色，需要将临时变量溢出（spill）到内存当中。将某一临时变量 \(t\) 溢出到内存的方法如下：

  • 为临时变量开辟一个内存空间，假设地址为 ta；
  • 对于每个读取变量 \(t\) 的指令，新建一个临时变量 \(t_i\) 并将 \(t\) 改为 \(t_i\)，在指令前面添加一条指令 ti = load ta；
  • 对于每个写入变量 \(t\) 的指令，新建一个临时变量 \(t_i\) 并将 \(t\) 改为 \(t_i\)，在指令后面添加一条指令 store ti, ta；

此时临时变量 \(t\) 被分为了许多的新的临时变量 \(t_i\)，且每个 \(t_i\) 的生存期都很短，更有机会成功进行寄存器分配。

选择合适的临时变量溢出使得溢出代价最小化同样是一个 NP 问题，因此只能使用启发式方法来寻找近似的最优方案。

缓存优化

对于如下的程序： 

1
2
3
4
5
for (int j = 1; j <= 100; ++j) {
  for (int i = 0; i < 1000000; ++i) {
    a[i] *= b[i];
  }
}
如果缓存不能将数组 a 和 b 全部存下可能会造成大量的缓存失效，导致运行速度缓慢。

若将两层循环调换： 

1
2
3
4
5
for (int i = 0; i < 1000000; ++i) {
  for (int j = 1; j <= 100; ++j) {
    a[i] *= b[i];
  }
}
可以避免大部分的缓存失效从而提升运行速度。

一部分编译器可以进行如上的循环调换优化从而使程序更加地缓存友好，但大多数的缓存优化仍需要程序员手动进行。