# 死代码消除

死代码消除即无用代码消除，和不可达代码消除是两个概念。前者指的是消除执行之后没有任何作用的代码，后者指的是消除永远无法被执行到的代码。现在框架中有不可达代码消除的优化，是在构造流图和常量传播的时候进行的。

我们要求基于活跃变量分析进行死代码消除，不要求基于Faint Variables Analysis。理论上来说Faint Variables Analysis的效果应该是一定不会更差的，但是实现也一定会更复杂，不建议大家做它(做了也不会有额外加分)。

本来这一节应该是这几种优化中最简单的一个的(从结果代码行数可以直接看出)，不过因为这是大家的实验任务，所以这里还是讲解的详细一些。首先来推导活跃变量分析的几个集合是怎么来的，这个推导对于到达-定值分析也基本上适用，可以帮助大家理解那几个集合的意义。

活跃变量分析为每个程序点计算出所有变量的集合的子集，用于表示该点处活跃的变量，所以数据流分析的值集为所有变量的集合的幂集。"活跃"的含义是在程序执行过这一点**之后**，这个变量**当前的值**会被使用到，所以数据流分析是后向的。对于单个语句$$S$$，传递函数要根据$$S$$之后活跃的变量计算$$S$$之前活跃的变量，计算方法为：所有$$S$$用到的变量在$$S$$之前都是活跃的，所有$$S$$之后活跃的变量，如果没有在$$S$$中被定值，证明未来的那次使用用的还是$$S$$之前的值，所以也是活跃的。

综合得，传递函数定义为：$$f\_S(x) = (x - def\_S) \cup use\_S$$。其中$$def\_S$$是$$S$$中定值的所有变量的集合，$$use\_S$$是$$S$$中使用的所有变量的集合。

基本块$$B$$的传递函数定义为：

$$
f\_B(x) = f\_{S\_1}(...f\_{S\_{n - 1}}(f\_{S\_n}(x))) \\
\= (((((x - def\_{S\_n}) \cup use\_{S\_n}) - def\_{S\_{n - 1}}) \cup use\_{S\_{n - 1}} ...) - def\_{S\_1}) \cup use\_{S\_1}\\
\overset{\mathrm{数学归纳法}}{=} (x - \bigcup\_{i = 1}^n def\_{S\_i}) \cup \bigcup\_{i = 1}^n (use\_{S\_i} - \bigcup\_{j = 1}^{i - 1} def\_{S\_j})
$$

最后一个等号使用数学归纳法来证明，读者自证不难。

定义$$def\_B = \bigcup\_{i = 1}^n def\_{S\_i}$$，$$use\_B = \bigcup\_{i = 1}^n (use\_{S\_i} - \bigcup\_{j = 1}^{i - 1} def\_{S\_j})$$，这样上面的式子就是大家熟悉的形式了。那么这个形式和课堂上定义的$$LiveUse$$和$$Def$$是一致的吗？

![](https://4087992577-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lou3DbfyBoOQZrPRxUB%2F-LwEMDh02q3f6cwNTu3o%2F-LwEiluFuzskLezK4CTo%2Faliveness.png?generation=1576518416193867\&alt=media)

先看$$use\_B$$和$$LiveUse$$，$$LiveUse$$为$$B$$中定值之前被引用的变量的集合，而$$use\_B$$定义中每一个求并项都是一条语句的$$use$$集合减去在这条语句前面的所有$$def$$集，也就是说如果一个变量在某条语句中被使用了，而且没有在这条语句之前的任何一条语句被定值，那么它属于$$use\_B$$，此外都不属于。显然，这与$$LiveUse$$的定义是符合的。

再看$$def\_B$$和$$Def$$，其实很容易可以看出这两个集合并不相同，$$def\_B$$包含了被定值的所有变量，而$$Def$$要求定值之前没有引用过，所以$$Def \subseteq def\_B$$。然而这个区别不会影响任何计算结果：如果变量$$x$$满足$$x \in def\_B, x \notin Def$$，则意味着它定值之前被引用过，则$$x \in use\_B, x \in LiveUse$$，则它一定在这一步的结果集合中。

> 所以，$$Def$$这样的定义是冗余的，只会加大计算$$Def$$时的计算量，使用$$def\_B$$的定义就会简单一些，而且不会影响最终结果。

在实验框架中为了实现死代码消除，大致流程是首先计算每个$$def\_B$$和$$use\_B$$，以此解出每个$$in\_B$$和$$out\_B$$，然后利用它们来计算每个$$out\_S$$，边计算$$out\_S$$边执行死代码删除。**具体每一步怎样做，可以参考其它几个数据流分析的实现。**这里讲一下几个常见的需要注意的点：

1. 计算$$def\_B$$和$$use\_B$$的时候不用像定义式一样算，而是(反向)遍历一遍基本块中的每个语句并同时维护这两个集合。计算$$out\_S$$也是类似的。如果你阅读了其他几个数据流分析的实现代码，会发现它们也都是类似这样做的
2. 对于方程的求解，`Flow`已经提供了求解的工具。它是基于前向数据流的。根据之前的讲解大家应该知道怎么利用它来求解后向数据流。如果你觉得现有的的代码很难理解，也完全可以自己手动实现数据流方程的求解，我们并不强制使用`Flow`
3. 进行死代码删除的时候，如果一条语句**没有副作用**，而且它的赋值目标(如果有的话)不在$$out\_S$$中，那么这条语句就可以删去
   * 所谓的副作用，其实就是除了"改变赋值目标变量"之外，其他所有的作用。显然，tac中没有既没有副作用，同时也没有赋值目标的语句
   * 你在实现的时候可以认为除了`a = call b`之外的所有有赋值目标的语句都是没有副作用的，对于`a = call b`，如果$$a \notin out\_S$$，要求将它优化为`call b`

其实还有一些语句的"副作用"不是很明确，比如load指令`a = *(b + imm)`和一部分计算指令，如除0，有符号整数溢出等(依平台而定)，可能会导致程序崩溃，但是**优化的时候可以不把这当成是副作用**：按照c/c++常用的说法这叫未定义行为，这可以减轻编译器作者的负担，编译器可以假定程序永远没有未定义行为，并以此为依据来优化。

目前decaf并没有这方面的严格的语言标准，为了让大家的实现尽量简单，我们姑且认为不合法的访存和运算都是未定义行为，所以这样的指令是可以优化掉的。