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]
[2]