死代码删除（DCE，Dead Code Elimination）和激进的死代码删除（ADCE，Aggressive DCE）

介绍一下DCE和ADCE基本算法。

死代码删除（DCE，Dead Code Elimination）

DCE简介

DCE用于删除对程序结果没有任何影响的代码。Dead code主要包括：

• 一个变量从其定值的代码位置开始直到出口的任何路径都不会被使用
• 一条指令它仅计算那种从该指令开始的任何路径都不会被使用的值
• 将一个死变量赋值给一个局部变量，如果通向程序出口的任何路径都不会使用这个局部变量，则这个局部变量及其赋值的指令都是Dead

Dead Code的来源：

• 源代码中本来就存在的
• 其他优化pass产生的（例如强度削弱）

DCE基本算法

一种乐观的方法（来源于《高级编译器设计与实现》）：

• 首先，标识所有计算必要值的指令。比如在过程中要返回或输出的值，或者它可能会对从过程外访问的存储单元有影响
• 然后，以迭代的方式逐步标记对这种对计算必要值有贡献的指令
• 当以上迭代过程稳定不变时，所有未标记的指令都可以认为是Dead Code，可以删除

具体实现上，可以借助工作表（worklist）和du/ud链来实现：

• 用必要指令的基本块索引偶对的集合初始化worklist。mark[i][j] = true，并加入到worklist中（这里的<i,j>为基本块索引和指令位置的偶对）
• 从worklist中删除一个偶对，对于这条指令中使用的每个变量v，标识它ud链上的每条指令，并将这些指令的基本块索引偶对加入到worklist中
• 如果指令是一个赋值（比如v<–exp），则对它du链中每条指令位置<k,l>，如果指令<k,l>是一个if，则标识它，并将<k,l>加入到worklist中
• 重复上述两个步骤，直到worklist为空
• 删除未标识的指令和已经为空的基本块

激进的死代码删除（ADCE，Aggressive DCE）

ADCE简介

ADCE激进的死代码删除，相较于DCE，ADCE会删除冗余的控制流结构（Control Flow Structure）。

ADCE基本算法

• 标记必要指令语句为有效语句。比如输入/输出、存储至存储器等有副作用（side effect）语句
• 使用数据流信息（du链）信息标记那些对有效语句有贡献的语句为有效语句
• 对于条件分支语句，其他有效语句控制依赖于该条件分支语句也标记为有效语句
• 最后删除无效语句

相较于DCE，ADCE对于条件分支语句需要根据控制依赖关系决定其是否有效。

信息维护

DCE和ADCE后，需要对du链、phi函数、CFG等信息进行维护。

参考

• 高级编译器设计与实现
• 现代编译原理C语言描述