编译器优化记录(1)
0. 为啥要写这个记录
- 我感觉自己平时整理自己想法的机会实在是太少了。即便是对于自己花了很多时间想、或是花了很多时间学的东西,同样如此。
- 写编译器优化的阶段学了很多方法,也看到了很多人类智慧,我希望能从头梳理一下认识它们的过程,来更好地体悟。
- 我身边有几位好朋友一直保持着记录(博客/日记)的好习惯,我总是在生活中发现自己的表达能力较高中时候差了很多,尤其是在发表看法的时候总是显得缺乏底气,可能也是我缺少深度思考的机会。
- 在写编译器的时候,我受到了几位学长和同学的帮助,我觉得如果我也能为大家写编译器的时候提供一些思路,一些insight,应当是很好的。
1. 构建CFG(控制流图)
在编译器优化的过程中,我们希望得知不同指令进行的顺序,从而进行优化。一个直观的想法是我们将各个基本块抽象为一个个节点,构建有向图。可以说,后面几乎所有的优化都是基于CFG实现的。幸运的是,无论是在IR阶段还是在ASM阶段,我们都已经设计了基本块,那么构建CFG的过程就非常简单了。
我们同时可以注意到CFG的一些性质:
- 如果对它进行拓扑排序,头节点是固定的,也即每个函数的起始块(记作enterBlock)
- 每个节点的后继至多只有两个(在IR阶段是
br
,在ASM阶段是beqz
+j
) - (猜测)一个程序的CFG应该是连通的
在IR中,我们注意到基本块的最后一条指令只可能是以下三种:jump
, branch
, ret
。那么我们可以轻易地找到每个节点的前驱和后继。
在实践的过程中,我发现对于我之前生成的IR代码,上面的第三条性质不一定成立(见testcases/codegen/t67.mx
)。那么我们采用这样一种策略来消除那些enterBlock不能到达的节点。
LinkedList<BasicBlock> ans = new LinkedList<>(); // ans的设置是因为如果在遍历的时候删除会导致concurrent modification error
for (var block : func.blockList) {
if (block.pred.size() == 0 && block != func.enterBlock) {
for (var succ : block.succ) {
succ.pred.remove(block);
succ.anti_succ.remove(block);
}
} else {
ans.add(block);
block.anti_pred.addAll(block.succ);
block.anti_succ.addAll(block.pred);
}
}
func.blockList = ans;
2. 支配树构建
2.1 为什么需要构建支配树
支配树的构建是为了解决插入phi指令的问题。而关于phi指令的使用,我们可以看这样一个例子:
int main() {
int x = 1;
for (int i = 0; i < 10; ++i) {
x = x + 1; // %add_0 = add i32 %x_1, 1
}
return x;
}
如果不经优化,我们会在第四行中,反复地从%x中取出x的值,然后进行计算,并把%add_0存入%x。但是,实际上我们注意到,如果我们是刚进入循环,那么%x_1的值就是1,如果我们已经进入,那么%x_1的值就是刚刚一轮算出来的%add_0。基于这个想法,我们可以获得这样的llvm-ir代码:
define dso_local i32 @main() {
enter_main_0:
br label %for.cond_0
for.cond_0:
%i_phi_0 = phi i32 [ %inc_0, %for.inc_0 ], [ 0, %enter_main_0 ]
%x_phi_0 = phi i32 [ %add_0, %for.inc_0 ], [ 1, %enter_main_0 ]
%slt_0 = icmp slt i32 %i_phi_0, 10
br i1 %slt_0, label %for.body_0, label %for.end_0
for.inc_0:
%inc_0 = add i32 %i_phi_0, 1
br label %for.cond_0
for.body_0:
%add_0 = add i32 %x_phi_0, 1
br label %for.inc_0
for.end_0:
br label %exit_main_0
exit_main_0:
ret i32 %x_phi_0
}
当然,关于phi应该插在哪里,又应该如何消除,这将会是我们接下来讨论的话题。
2.2 支配树的一些概念
支配(dominate):对于CFG上的节点\(A\)和\(B\),如果从enterBlock到\(B\)的每一条路径都经过了\(A\),我们就称\(A\)支配\(B\)。进一步地,如果我们构建\(Dom[n][n]\)来表示节点之间的支配关系,那么\(Dom[A.id][B.id] = true\)。同时我们也注意到,这个二维数组的对角线上肯定都是true。
直接支配节点(idom):对于所有支配节点\(n\)的节点\(dom[n]\),存在\(i\)使得\(\forall j \in dom[n], Dom[j][i] = true,i \neq n\)。那么就称这样的\(i\)为\(n\)的直接支配节点,记为\(idom[n] = i\)
支配树:根据直接支配节点的定义,可以看出支配节点有且仅有一个(我们预先定义\(idom[enterBlock] = enterBlock\)),那么就可以建出支配树。
我们不禁思考,为什么这支配树一定建的出来呢?我们应当证明直接支配节点一定存在。(直觉上这个可以归纳)
支配边界(dominance frontier):对于节点\(X\)和\(Y\),我们称\(Y \in domFrontier[X]\)当且仅当\(X\)支配\(Y\)的某个CFG上的前驱且\(X\)不直接支配\(Y\)(注意,这意味着可能出现\(X\in domFrontier[X]\),这浪费了我大概两个小时的时间)
支配边界几乎是我们插入phi指令的核心,假设\(X\)中出现了对于变量\(x\)的定义\(def\)(通常是一个store指令),那么对于那些\(X\)可以支配的节点,如果其中没有出现其它定义,那么我们可以在使用\(x\)的时候直接使用\(def\)中给\(x\)赋的值。但是,如果进入到了\(X\)的支配边界\(F\),就可能有其他导向\(F\)的路径,而这些路径上也出现了对于变量\(x\)的\(def\)。根据支配边界的定义,我们会发现\(F\)就是这几条路径的第一个交汇点。
由此我们可以得到插入phi指令的简单思路:如果我们发现了某个对于变量的\(def\),那么就找到它所在块的支配边界,在那里插入一条phi指令(如果已经插入,那么就为phi指令增加一条分支)。同时我们注意到,phi指令本质上也算是一种\(def\),那么我们需要将这个过程不断迭代。
2.3 支配树的构建方法
2.3.1 得到支配关系
这里我直接和编译器指导手册一样,使用了数据流迭代的方法。它的思想如下:
\[Dom(u) = \{u\}\cup(\bigcap_{v\in pred(u)}Dom(v)) \]这其实就是在说,如果一个点同时支配了\(u\)的所有前驱,那么就说明它是\(u\)的支配节点。经过不断迭代,我们可以获得支配点集。
为了提高效率,我们希望对于每一个迭代的节点,它的前驱最好都已经完成了这一轮迭代,所以我们希望用逆后序来完成这个迭代。
由此我们可以得到构建支配树的步骤
-
在CFG上采用后序遍历的DFS,最后把访问顺序反过来
-
将\(Dom[n][n]\)(我开了一个Bitset数组来记录)设为全是true,然后进行迭代。迭代的伪代码为:
BitSet tmp = new Bitset(n); tmp初始每位都是true for (每个前驱pred) { tmp = tmp && dom.get(pred.index); } if (!tmp.equals(dom.get(id))) { 更新 Dom.get(id) 继续迭代 }
2.3.2 得到直接支配节点,构建支配树
这里就直接按照我刚刚说的定义就行,伪代码如下(可以看到在这种情况下Bitset对程序运行还是有很大帮助的)
for (var u : blocks) {
for (var i : Dom[u]) {
BitSet tmp = new BitSet(n);
tmp = (dom.get(i) & dom.get(u)) ^ dom.get(u);
}
if (tmp.cardinality() === 1 && Dom[u] contains i) {
u.idom = i;
}
}
2.3.3 找到支配边界
算法大致如上图所示。首先,如果一个节点\(b\)只有一个前驱,那么它必然不可能是任何其他节点的支配边界。如果它有多个前驱,我们给定其中某一个前驱\(p\)。我们将其赋给\(runner\),当然,如果\(runner\)迭代到了\(idom[b]\),那么之后迭代的节点肯定就可以支配\(b\)了。那么,为什么我们迭代的步骤是\(runner = idom[runner]\)。因为在这中间的节点\(s\),一定会出现\(s\)不能支配\(runner\)的情况,自然支配边界也不可能是\(b\)了。这个算法实现之后,基本我们进行Mem2Reg优化的所有前置工具就都已经准备好了。
3 参考资料
[1] 支配树 - OI Wiki (oi-wiki.org)(辩证看待,里面的源代码实现细节可能有问题)
[2] 支配边界及其构建算法
[3] A Simple. Fast Dominance Algorithm
标签:phi,迭代,控制流,支配,我们,节点,block From: https://www.cnblogs.com/lixingyang/p/17720098.html