Dead Code Elimination in Compiler

0. 什么是死代码消除

相信大家在写 c++ 的时候，如果你定义了一个变量但是没有对其使用，大部分IDE都会对这个变量进行灰色的染色。又或者说，当你开了一个空的循环，在里面定义并使用了一堆和输出值/返回值没有关系的变量，这个时候 IDE 也会提示你这个循环没有用。这背后都是用到了死代码消除的 Pass。

1. 死代码消除（Dead Code Elimination）

1.1 算法思想

我们在死代码消除中希望去掉所有不活跃的变量。那么什么是不活跃呢？容易想到这意味着它定义的变量在接下来会被使用到。注意到，我们是在 SSA 阶段进行的这个优化，这意味着对于每个变量，它的 $def$ 是它的每个 $use$ 的必经节点。那么我们可以基于工作表算法写出伪代码：

while (存在某个没有使用点的变量 v && 定值 v 的语句没有其他副作用) {
    删除定值 v 的这条语句
} 

1.2 需要维护的信息

我们使用 HashMap<IRRegister> myMap 来维护现有的变量，并使用 WorkList。

同时，我们给出 HashMap<IRRegister, HashMap<IRBaseInst>> useMap 来记录所有变量的 use，用 HashMap<IRRegister, IRBaseInst> defMap 来记录所有变量的 use。

另外，我们注意到，函数的入参并不在我们的考量范围内（我们总不能消掉它们的 def 吧），所以我们需要用一个 HashSet 来记录当前函数的所有入参。

1.3 算法实现

大概的思路就是先把所有没有被使用到的定值语句加入工作表。接下来进行迭代，把这条语句中所有 $use$ 的定值语句都加入工作表。如果工作表中的一条指令没有被使用，就给它打上要删除的 tag，如此迭代直到工作表为空。

最后，我们只要把所有的打有 tag 的 $def$ 都删除就行了。

1.4 效果总结

其实，对于死代码消除而言，只要我们写的代码中所有 $def$ 的变量都被使用，其优化效果应该是比较差的。但是，我们注意到之前 $\text{Mem2Reg}$ 阶段对于所有的支配边界都插入了 $phi$ 指令。事实上，不是每个支配边界块之后都有对该变量的 $use$，自然，也不一定需要这么多的 move 语句。所以，一般来说，死代码消除消除的基本都是无效的 $phi$ 指令。

2. 激进的死代码消除（Aggressive Dead Code Elimination）

2.1 算法思想

它的思想和传统的死代码消除最不一样的地方就在于：它对于死代码的定义不同。

它的定义相当于是递归的：初始，我们定义所有调用函数，函数返回，对存储器的操作为有效代码。之后，我们标记一下语句为有效的：

• 对其他有效语句的 $use$ 进行定值的语句
• 其他有效语句控制依赖于的语句（至于这个是什么，我们待会儿说）

之后，我们迭代得到所有语句，并把剩下的都删除。那么接下来，我们首先展开控制依赖部分的内容，幸运的是，这一部分和支配树很像。

2.2 控制依赖

我们希望回答的问题是，控制流图上的两个节点 $x,y$ 中，$x$ 能否直接控制节点 $y$ 的执行？

那么什么是控制执行呢？应该就是节点 $x$ 有一个后继 $u$ 能直接到达程序的 $exitBlock$ 而不经过 $y$。而它同时也有一个后继 $v$ 使得 $v$ 到 $exitBlock$ 的每一条路径都经过 $y$。

那么我们很容易就能得到控制依赖的等价定义。我们考虑 CFG 对应的反图，则在这张图上，$x\in domFrontier(y)$。因为 $x$ 的前驱 $v$ 被 $y$ 直接支配，而它又能由 $u$ 到达，因而 $x$ 在 $y$ 的支配边界上。

2.3 算法实现

我们需要维护的信息如下：

1. HashSet<IRBaseInst> live：所有的活跃指令
2. HashSet<BasicBlock> liveBlock：所有有活跃指令的基本块
3. HashSet<entity> liveUse ：所有活跃指令的$use$
4. HashSet<IRBaseInst> workList：用于迭代的工作表
5. HashSet<IRRegister, IRBaseInst> defMap：所有变量的$def$语句

首先，我们需要建出控制依赖图，这部分参考之前支配树构建的那期。

接下来，我们首先扫描该函数的所有基本块，将所有 $def$ 收集到defMap中，同时把所有的 store（代表修改全局变量，可能会在其他程序中用到）、所有的 call、所有的 ret 加入 workList。

然后，我们进行迭代。代码如下：

while (!workList.isEmpty()) {
    IRBaseInst inst = workList.iterator().next();
    workList.remove(inst);
    live.add(inst);
    liveBlock.add(inst.parentBlock);
    liveUse.addAll(inst.uses());
    if (inst instanceof IRPhi irPhi) { // 对于一条phi指令，它的每一个前驱都应当被标注为活跃的
        for (var block : irPhi.blockMap) {
            if (block.terminal != null && !live.contains(block.terminal)) {
                workList.add(block.terminal);
                liveBlock.add(block);
            }
        }
    }
    for (var cdg_pred : inst.parentBlock.cdg_pred) { // 加入该块的所有控制依赖前驱
        if (cdg_pred.terminal != null && !live.contains(cdg_pred.terminal)) {
            workList.add(cdg_pred.terminal); // 注意已经加过的不用加了
        }
    }
    for (var use : inst.uses()) { // 对于其每个use的变量，将其def加入workList
        if (!(use instanceof IRRegister) || use instanceof IRGlobalVar) continue;
        IRBaseInst def = defMap.get(use);
        if (def != null && !live.contains(def)) {
            workList.add(def);
        }
    }
}

最后我们遍历所有指令，消去不活跃的 $phi$ 指令和普通指令。

这里有一个细节，就是 jump/branch 这样的 terminal 的处理。如果一个块的 terminal 被标记为不活跃的，那么这个块应该跳到哪里呢？自然，它应当跳到它的后继中第一个活跃的块上。我们要在反支配树上寻找（反支配树就是我们根据 CFG 的反图建出的支配树）。

我们断言，如果一个节点 $x$ 是不活跃的，那么说 $x$ 到 $anti\_dom(x)$ 的这些节点一定都不是活跃的如果其中有一个节点是活跃的，那么根据定义，一定能通过若干次 $dominanceFrontier$ 的迭代，推出 $x$ 是活跃的。那么我们只需要不停地迭代 target=target.anti_dom 就行了。

2.4 ADCE对程序语义的影响

它的一个弊端在于它会删除不活跃的死循环，从而改变语义（这很明显）。在许多环境下，这被认为是不可接受的。

2.5 ADCE的效果

基本与DCE类似，主要在冗余 $phi$ 的消除。它的另一个增益在于能消除掉无用的控制流语句。

3. 参考资料

[1] 现代编译原理（C语言实现）Chapter 19.5