.\\]
因此可以根据 Rebuild 可以构造出 `%3` 的 IR 类似
```lisp
;; LLVM IR
%1 = add nsw i32 %b, 17
%t3 = add nsw i32 %1, %a
```
最终可以得到平衡后的树
{{< figure src="/images/tree-height-balance-second-balanced-example.svg" >}}
```lisp
;; LLVM IR
%1 = add nsw i32 %b, 17
%t3 = add nsw i32 %1, %a
%t7 = add nsw i32 %e, %f
%2 = add nsw i32 %h, %g
%3 = add nsw i32 %2, %t7
%t11 = add nsw i32 %3, %t3
%t10 = mul nsw i32 %t7, %t3
%4 = mul nsw i32 %c, 3
%5 = mul nsw i32 %4, %d
%t6 = mul nsw i32 %5, %t3
```
---
## 区域优化 {#区域优化}
低效性不止出现在单个 BB 中,一个 BB 可能为改进另一个 BB 提供上下文环境。因此大多数优化也会考察多个 BB 的上下文,这也就是区域优化。
### 超局部值编号 {#超局部值编号}
命名一直是编译器中的一个重点项目,LVN 是在单个 BB 内的命名方法,超局部值编号
(SVN, Superlocal Value Numbering) 则是扩展到 EBB 中进行命名的方法。
回到[优化的范围](#优化的范围)所提到的 EBB 示例,先聚焦到第一个 EBB \\(\\{B\_{0}, B\_{1}, B\_{2},
B\_{3}, B\_{4}\\}\\) 上,SVN 可以将 3 条路径中的每一条路径都当作一个单个 BB 进行处理,也就是说,在处理时 \\(\\{B\_{0}, B\_{1}\\}\\)、\\(\\{B\_{0}, B\_{2}, B\_{3}\\}\\) 和
\\(\\{B\_{0}, B\_{2}, B\_{4}\\}\\) 都被当作线性代码。比如在处理 \\(\\{B\_{0}, B\_{1}\\}\\) 时,编译器先将 LVN 算法应用到 \\(B\_{0}\\) 上,然后将生成的散列表按 BB 顺序用 LVN 算法应用到 \\(B\_{1}\\) 上。
{{< admonition type="warning" >}}
因此考虑,为何 EBB 只允许第一个 BB 可以有多个前驱,而其他 BB 只允许有一个前驱。
{{< /admonition >}}
SVN 可以发现 LVN 可能错过的冗余和常量表达式。但对于分支上的 BB 来说,SVN 算法可能会将一个 BB 分析多次,例如 EBB \\(\\{B\_{0}, B\_{1}, B\_{2}, B\_{3}, B\_{4}\\}\\) 的 3
个分支,会将 \\(B\_{0}\\) 分析 3 次,将 \\(B\_{2}\\) 分析 2 次。
为了 SVN 的高效运行,算法必须有一种重用分析结果的方法,比如处理分支 \\(\\{B\_{0},
B\_{2}, B\_{4}\\}\\) 时,需要重用 \\(\\{B\_{0}, B\_{2}\\}\\) 结束时的状态来处理 \\(B\_{4}\\)。而在重用之前,必须撤销 \\(\\{B\_{0}, B\_{2}, B\_{3}\\}\\) 所带来的影响。为了高效的撤销,使用作用域化散列表可以有效解决这个问题。在处理每个 BB 时为其分配一个值表,将其连接到前驱程序块的值表 (将前驱块的值表当作外层作用域),并用这个新的值表与程序块 b
作为参数使用 LVN 算法。
WorkList = { entry block }
Empty = new table
while WorkList is not empty do
remove b from WorkList
SVN(b, Empty)
end
SVN(BB, Table)
t = new table for BB
link Table as the surrounding scope for t
LVN(BB, t)
for each successor s of BB do
if s has only 1 predecessor then
SVN(s, t)
else if s has not been processed then
add s to WorkList
end
end
end
还有一个问题,就是名字的值编号是由 EBB 中定义该名字的第一个操作相关联的值表记录的,那么在[优化的范围](#优化的范围)示例中的 CFG,如果 \\(B\_{0}\\)、\\(B\_{3}\\) 和 \\(B\_{4}\\) 中都定义了名字 x,那么其值编号将记录在 \\(B\_{0}\\) 中的作用域化值表中。在处理 \\(B\_{3}\\)
时,会将它的 x 的新的值编号记录到对应于 \\(B\_{0}\\) 的表中,删除对应于 \\(B\_{3}\\)
的表并开始处理 \\(B\_{4}\\) 时,由 \\(B\_{3}\\) 定义的值编号依然保留在 \\(B\_{0}\\) 的表中。为了避免这种复杂的情况,编译器可以使用只定义每个名字一次的表示法,也就是 SSA
所具有的性质。使用 SSA 时可以撤销一个程序块值表的所有影响,恢复到前驱程序块退出时的状态,并且 SSA 还可以使 LVN 更加高效。
需要注意的是,SVN 虽然可以发现 EBB 中的冗余,但也有局限,例如当一个 BB 有多个前驱时,SVN 无法将上下文信息传入其中。
### 循环展开 {#循环展开}
循环展开时最古老、最著名的循环变换,展开一个循环,复制循环体并调整迭代执行数目的逻辑。
```lua
for j = 1, n2, 1 do
for i = 1, n1, 1 do
y[i] = y[i] + x[j] * m[i][j]
end
end
```
编译器可以展开内层循环或外层循环,例如展开内层循环会复制循环体,而展开外层循环时会复制多次内层循环。如果编译器之后合并这些内层循环 (循环融合,loop fusion),先展开外层循环再融合内层循环的变换组合被称为 **展开-轧挤** (unroll-and-jam)。
循环展开对编译器为给定循环生成的代码有着直接或间接的影响。展开循环可以减少完成循环所需操作的数目,控制流的改变减少了判断和分支代码序列的总数。展开还可以在循环体内部产生重用,减少内存访问。最后,如果循环包含一个复制操作的有环链,那么展开可以消除这些复制。但展开会增大程序的长度,这样可能会增加编译时间,但展开的循环体内部可能影响 Cache,从而导致性能降低。
循环展开的关键副效应时增加了循环内部的操作数目,一些优化可以利用这些
- 增加循环体中独立操作的数目,可以生成更好的指令调度。在操作更多的情况下,指令调度器有更高的几率使多个功能单元保持忙碌,并隐藏长耗时操作 (如分支和访存) 的延迟。
- 循环展开可以将连续的内存访问移动到同一迭代中,编译器可以调度这些操作一同执行。这可以提高内存访问的局部性,或利用多字操作进行内存访问。
- 展开可以暴露跨迭代的冗余,而这在原来的代码中可能是难以发现的。展开循环后 LVN
算法可以找到这些冗余并消除。
- 与原来的循环相比,展开后的循环能以不同的方式进行优化。如增加一个变量在循环内部出现的次数,可以改变寄存器分配器内部逐出代码选择中使用的权重。改变寄存器逐出的模式,可能在根本上影响到为循环生成的最终代码的速度。
- 与原来的循环体相比,展开后的循环体可能会对寄存器有更大的需求。如果对寄存器增加的需求会导致额外的寄存器逐出 (存储到内存和从内存重新加载),那么由此导致的内存访问代价可能会超出循环展开带来的收益。
---
## 全局优化 {#全局优化}
全局优化处理整个过程或方法,其作用域包括有环的控制流结构 (如循环),全局优化在修改代码前通常会有一个分析阶段。
### 利用活动信息查找未初始化变量 {#利用活动信息查找未初始化变量}
如果过程 p 在为某个变量 v 分配一个值之前能够使用 v 的值,那么就说 v 在这次使用时是为初始化的。通过计算**活动情况**的信息,可以找到对未初始化变量的潜在使用。当且仅当
CFG 中存在一条从 p 到使用 v 的某个位置之间的路径,且 v 在该路径中没有被重新定义,变量 v 在位置 p 处是活动的。通过计算将过程中的每个 BB 对应的活动信息编码到集合
`LiveOut(bb)` 中,该集合包含在 BB 退出时的所有活动的变量。
给定 CFG 入口结点 \\(n\_{0}\\) 的 LiveOut 集合,\\(LiveOut(n\_{0})\\) 中的每个变量都有一次潜在的未初始化使用。
#### 定义数据流问题 {#定义数据流问题}
为了计算 CFG 中结点 n 的 LiveOut,需要使用其后继结点的 LiveOut,以及另外两个集合
`UEVar` 和 `VarKill`。定义 LiveOut 的方程如下:
\\[LiveOut(n) = \cup\_{m\in{}succ(n)} \left( UEVar(m) \cup \left( LiveOut(m) \cap
\overline{VarKill(m)} \right) \right).\\]
`UEVar(m)` 包含了 m 中向上展现的变量,即那些在 m 中重新定义之前就开始使用的变量。`VarKill(m)` 包含了 m 中定义的所有变量,\\(\overline{VarKill(m)}\\) 则是其补集,即未在 m 中定义的变量的集合。由于 `LiveOut(n)` 是利用 n 的后继结点来定义的,因此该方程描述了一个**反向数据流问题**。
#### 解决这个数据流问题 {#解决这个数据流问题}
对一个过程及其 CFG 计算各个结点的 LiveOut 集合,编译器可以使用一个三步算法
1. **构建 CFG**,这个步骤在概念上很简单
2. **收集初始信息**,分析程序在一趟简单的遍历中分别为每个程序块 b 计算一个 `UEVar`
和 `VarKill` 集合
为了计算 LiveOut 集合,分析程序需要每个程序块的 UEVar 和 VarKill 集合。一趟处理即可计算出这两个集合。对于每个程序块,分析程序将两个集合都初始化为
\\(\emptyset\\)。接下来按从上到下顺序遍历,并适当地更新 UEVar 和 VarKill 集合,以反映程序块的每个操作的影响。
// x = y op z
for each block b do
Init(b)
end
Init(b)
UEVar(b) = \\(\emptyset\\)
VarKill(b) = \\(\emptyset\\)
for i in range(1, k) do
if y \\(\notin\\) VarKill(b) then
add y to UEVar(b)
end
if z \\(\notin\\) VarKill(b) then
add z to UEVar(b)
end
add x to VarKill(b)
end
end
3. **求解方程式,为每个程序块生成 LiveOut 集合**
求解过程需要反复进行,直到所有 LiveOut 集合不再改变为止
for i in range(0, N - 1), LiveOut(i) = \\(\emptyset\\) do
changed = true
while changed do
changed = false
for i in range(0, N - 1) do
recompute LiveOut(i)
if LiveOut(i) changed then
changed = true
end
end
end
end
比如对于一个控制流图
```lisp
;; IR
b0:
%i = i32 1
b1:
br i32 %i, label %b3, label %b2
b2:
%s = i32 0
b3:
%s = add nsw i32 %s, %i
%i = add nsw i32 %i, 1
br i32 %i, label %b1, label %b4
b4:
print i32 %s
```
根据控制流信息可以轻松计算出 VarKill 和 UEVar
| | UEVar | VarKill |
|----|-----------------|-----------------|
| b0 | \\(\emptyset\\) | {i} |
| b1 | {i} | \\(\emptyset\\) |
| b2 | \\(\emptyset\\) | {s} |
| b3 | {s, i} | {s, i} |
| b4 | {s} | \\(\emptyset\\) |
在这个例子中,开始计算每个程序块的 LiveOut。
| 迭代次数 | LiveOut(b0) | LiveOut(b1) | LiveOut(b2) | LiveOut(b3) | LiveOut(b4) |
|------|-----------------|-----------------|-----------------|-----------------|-----------------|
| 初始 | \\(\emptyset\\) | \\(\emptyset\\) | \\(\emptyset\\) | \\(\emptyset\\) | \\(\emptyset\\) |
| 1 | {i} | {s, i} | {s, i} | {s, i} | \\(\emptyset\\) |
| 2 | {s, i} | {s, i} | {s, i} | {s, i} | \\(\emptyset\\) |
| 3 | {s, i} | {s, i} | {s, i} | {s, i} | \\(\emptyset\\) |
#### 查找未初始化的变量 {#查找未初始化的变量}
计算出 CFG 的每个结点的 LiveOut 集合后,查找未初始化变量的使用就变得简单了。如果有一个变量 v,且 \\(v \in LiveOut(n\_{0})\\),\\(n\_{0}\\) 为 CFG 的入口结点,那么一定存在一条从 \\(n\_{0}\\) 到 v 的某个使用之处的路径,v 在该路径上未被定义。因此编译器可以识别处其中未被初始化的变量。但也有几种可能导致编译器错误的识别。
- v 通过另一个名字初始化
- v 在当前过程被调用之前就已存在
- v 在路径上没有被初始化,但实际上该路径总是不会出现
如果过程包含对另一过程的调用,且 v 通过允许修改的方式传递给后者,那么分析程序必须考虑调用可能带来的副效应。在缺少被调用者的具体信息时,就需要假定其总是被修改。
#### 对活动变量的其他使用 {#对活动变量的其他使用}
除了查找未初始化变量外,编译器还可以在许多上下文中使用活动变量
- 全局寄存器分配中,活动变量会发挥关键作用,除非值是活动的,否则寄存器分配器不必将其保持在寄存器中;当值从活动转变为不活动时,分配器可以因其他用途重用该寄存器。
- 活动变量可以用于改进 SSA 构建:对一个值来说,它不活动的任何程序块中都不需要
\\(\phi\\) 函数。用活动变量信息可以显著减少编译器构建程序 SSA 时必须插入 \\(\phi\\) 函数的数目。
- 编译器可以使用活动变量信息发现无用的 store 操作。如果一个操作将 v 存在内从中,如果 v 是不活动的,那么该 store 操作是无用的。
### 全局代码置放 {#全局代码置放}
很多处理器对分支处理的代价是不对称的:落空分支 (fall-through branch) 的代价要小于采纳分支 (taken branch)。比如一个条件跳转语句,其真条件分支执行频率比假条件分支高得多,那将真条件分支设置为落空分支性能更高。
为了全局代码置放优化,编译器应该将可能性最高的执行路径置放在落空分支上。其次编译器应该将执行得较不频繁的代码移动到过程末尾。这样可以尽可能生成更长的代码序列。
1. 获取路径剖析数据
对于全局代码置放优化,编译器需要预估 CFG 中各条边的相对执行频度。从代码的剖析运行 (profiling run) 获取所需的信息。简单地说,就是统计 CFG 中各条边的执行次数,从而获得剖析数据。
2. 以链的形式在 CFG 中构建热路径
编译器为判断如何设置代码布局而构建一个执行最频繁的边的集合,即热路径 (hot
path)。编译器可以使用贪心算法查找热路径。
首先为每个程序块创建一条退化的链,其中只包含块本身。接下来遍历 CFG 的各个边,按执行频度的顺序采用各边,使得最频繁的边优先。对于边 \\(\\),只有当 x 是所在链的最后一个结点,而 y 是所在链的第一个结点时,才会合并这两条链。
E = edges
for each block b do
make a degenerate chain, d, for b
priority(d) = E
end
p = 0
for each CFG edge <x, y>, x != y, in decreasing frequency order do
if x is the tail of chain a and y is the head of chain b then
t = priority(a)
append b onto a
priority(a) = min(t, priority(b), p++)
end
end
3. 进行代码布局
为生成最终的汇编代码,编译器必须将所有 BB 按一个固定的线性顺序置放。可以根据链集合计算出一个线性布局:
1. 一个链内部的各 BB 按顺序置放,使链中的边能够通过落空分支实现
2. 在多个链之间,根据链的优先级选择
t = chain headed by the CFG entry node
WorkList = {(t, priority(t))}
while WorkList != \\(\emptyset\\) do
remove a chain c of lowest priority from WorkList
for each block x in c in chain order do
place x at the end of the executable code
end
for each block x in c do
for each edge <x, y> where y is unplaced do
t = chain containing <x, y>
if (t, priority(t)) \\(\notin\\) WorkList then
WorkList = WorkList \\(\cup\\) { (t, priority(t)) }
end
end
end
end
---
## 过程间优化 {#过程间优化}
将一个程序划分为多个过程,可以有效抽象出基础功能的代码,得以复用和抽象功能。但是从负面来看,程序划分限制了编译器理解调用过程内部行为的能力,比如编译器不能假定一个引用传递不会产生副作用。而另一点,过程调用需要转存当前上下文,这是代价巨大的。
### 内联替换 {#内联替换}
那编译器可以通过将被调用过程的副本替换到调用位置上,并根据调用位置的上下文调整代码,这种变换称为内联替换 (inline subsitution)。
在每个调用位置上,编译器必须决定是否内联该调用。一个调用位置上所做的决策可能会影响到其他调用位置上的决策。如 a 调用 b、b 调用 c 的过程,如果内联过程 c,可能会改变内联到 a 中的特征。因此在内联替换时需要一些准则来考察。
- **被调用者的规模**,如果被调用者的代码长度小于进行上下文保存、恢复的长度,那么内联替换可以减少代码长度
- **调用者的规模**,如果希望生成的代码足够的小
- **动态调用计数**,对频繁调用位置上的改进可以提供更大的收益
- **常数值实参**,调用时使用常数值实参,可能产生潜在的代码改进
- **静态调用计数**,编译器跟踪一个过程在不同位置的调用次数
- **参数计数**,参数的数目可以充当过程链接代价的一种表示
- **过程中的调用**,检查调用图的叶结点,通常这是良好的候选内联对象
编译器会根据一些准则,然后应用一条或一组相应的启发式规则,来决定一个调用是否被内联替换。
### 过程置放 {#过程置放}
与[全局代码置放](#全局代码置放)类似,根据调用图试图将有调用关系的过程尽可能置放在相邻的位置。
### 针对过程间优化的编译器组织结构 {#针对过程间优化的编译器组织结构}
对于传统编译器来说,编译单元可能是单个过程、单个类或单个代码文件,编译器生成的目标代码完全取决于编译单元的内容。到达编译单元边界时,编译器无法链接另一个编译单元中的行为,通常只能使用最坏的结果进行假设优化。
人们提出了针对过程间优化的不同编译器组织结构:
- **扩大编译单元**,这是最简单的一种解决方法
- **链接时优化** (Link-Time Optimization),直接地将过程间优化移动到链接器中,其中可以访问所有的静态链接代码。