minidecaf-tutorial

死代码消除

死代码消除（Dead code elimination, DCE）即无用代码消除，死代码和不可达代码是两个概念。前者指的是执行之后没有任何作用的代码（例如：多余的计算），后者指的是永远无法被执行到的代码。

死代码消除通常依赖于Use-Def和Def-Use数据流分析，这个数据流分析可以帮我们找到每个指令用到的变量是在哪里定义的。

这里介绍一种 DCE 的方法（来源于《高级编译器设计与实现》（鲸书））：

• 首先，标识所有计算必要值的指令。比如在函数中要返回（return）或输出（print）的值，或者它可能会对从函数外访问的存储单元有影响（全局内存访问，对函数外定义的数组访问）。
• 然后，以迭代的方式逐步标记对这种对计算必要值有贡献的指令。假如一个指令的结果是另一个必要值计算指令的输入，那么这个指令也是必要的。
• 当以上迭代函数稳定不变时，所有未标记的指令都可以认为是Dead Code，可以删除。

具体实现上，可以借助du/ud链来实现：

• 维护一个set，存储所有必要值的定义指令。
• 找出函数所有的必要值，标记这些值的定义指令。
• 对于set中的每个指令，顺着ud链找到所有使用这个指令的指令，将这些指令加入set。
• 对于上一步中新加入的指令，继续顺着ud链找到所有使用这个指令的指令，将这些指令加入set。
• 重复上一步，直到set不再变化。
• 函数中的指令，如果不在set中，就可以认为是Dead Code。

此处举个例子：

_main:
      _T0 = 1
      _T1 = 2
      _T2 = _T1 + 5
      _T3 = _T0 + 2
      _T4 = _T3 * 5 
      return _T4     # _T4 是必要值

顺着ud链，可以找到 _T4 = _T3 * 5，因此 _T3 也是必要值。继续找到 _T3 = _T0 + 2，因此 _T0 也是必要值。最终 _T0、_T3、_T4 都是必要值，而 _T1、_T2 的定义指令都可以认为是Dead Code。

因此可以优化为：

_main:
      _T0 = 1
      _T3 = _T0 + 2
      _T4 = _T3 * 5 
      return _T4