在编译器优化的过程中，我们希望得知不同指令进行的顺序，从而进行优化。一个直观的想法是我们将各个基本块抽象为一个个节点，构建有向图。可以说，后面几乎所有的优化都是基于CFG实现的。幸运的是，无论是在IR阶段还是在ASM阶段，我们都已经设计了基本块，那么构建CFG的过程就非常简单了。
我们同时可以注意到CFG的一些性质：
br，在ASM阶段是beqz + j）在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;
支配树的构建是为了解决插入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应该插在哪里，又应该如何消除，这将会是我们接下来讨论的话题。
支配(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\)，那么我们需要将这个过程不断迭代。
这里我直接和编译器指导手册一样，使用了数据流迭代的方法。它的思想如下：
这其实就是在说，如果一个点同时支配了\(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)
继续迭代
}
这里就直接按照我刚刚说的定义就行，伪代码如下（可以看到在这种情况下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;
}
}
算法大致如上图所示。首先，如果一个节点\(b\)只有一个前驱，那么它必然不可能是任何其他节点的支配边界。如果它有多个前驱，我们给定其中某一个前驱\(p\)。我们将其赋给\(runner\)，当然，如果\(runner\)迭代到了\(idom[b]\)，那么之后迭代的节点肯定就可以支配\(b\)了。那么，为什么我们迭代的步骤是\(runner = idom[runner]\)。因为在这中间的节点\(s\)，一定会出现\(s\)不能支配\(runner\)的情况，自然支配边界也不可能是\(b\)了。这个算法实现之后，基本我们进行Mem2Reg优化的所有前置工具就都已经准备好了。
[1] 支配树 - OI Wiki (oi-wiki.org)(辩证看待，里面的源代码实现细节可能有问题)
[2] 支配边界及其构建算法
[3] A Simple. Fast Dominance Algorithm