# 公共表达式提取

## 背景

一般而言程序员不会有意地编写重复的表达式，但是中间代码生成的过程中，因为是直接把源语言的各种高层特性翻译成中间代码，所以中间代码中可能会产生一些冗余，例如在decaf中，如果连续多次在一个对象上调用虚函数：

```java
  obj.foo();
  obj.bar();
```

大致的中间代码可能为(只是大概表示一下意思)：

```
  a = *(obj + 0)
  b = *(a + offset_foo)
  parm obj
  call b
  c = *(obj + 0) # 公共表达式!
  d = *(b + offset_bar)
  parm obj
  call d
```

这样的公共表达式并非程序员主动写出来的，程序员也不可能通过目前的任何decaf语言特性来消除这样的重复计算，这样的优化只适合交给编译器来做。

公共表达式提取的优化目标是减少这样重复的计算，对于某个计算的右端项，如果它已经在**前面**出现过，那么就**可能**不用再计算一次，可以直接复用之前的结果。

值得注意的是，有一种优化手段叫做[部分冗余消除](https://en.wikipedia.org/wiki/Partial_redundancy_elimination)(pre, partial redundancy elimination)，公共表达式提取可以看作部分冗余消除的一种特殊情况。在实际的编译器中，往往直接实现了部分冗余消除，而不会有专门的公共表达式提取的优化。然而部分冗余消除的实现也更复杂，总共涉及四种数据流分析，感兴趣的同学可以自行阅读龙书的相关章节，我们这个简单的编译器就不去做这么复杂的优化了。

## 算法

公共表达式提取中的"前面"如何定义?从流图的角度来说就是从起始语句到这条语句中，**任意**一条路径都会做这个计算。为什么"前面"有了计算结果后还只是"可能"不用再计算一次?因为这个计算的operand可能在中途被改变了，从而导致这里的计算会产生和前面的计算不同的结果。

还有一点需要考虑的是，即使看起来operand没有改变，也不能证明之前的结果就仍然有效，这主要与访存指令相关：两条load指令即使基址和偏移都一样，也很难保证中途这个地址没有被别人修改过。幸运的是decaf不允许对于任意变量取地址，所以store指令并不会影响任何一条对虚拟寄存器进行的"纯运算"。

除此之外，框架还对decaf的类型系统做了很简单的利用来尝试减小store指令能够杀死的公共表达式。大家在pa3中应该已经注意到了`MemHint`和`CallHint`的存在：

```rust
pub enum MemHint { Immutable, Obj, Arr }

pub struct CallHint {
  pub arg_obj: bool,
  pub arg_arr: bool,
}
```

`CallHint`表示函数的参数中有没有数组或者对象，只要有就保守地认为它会被写。`MemHint`非常简单地把访存划分成了对于对象和数组的访存，这两种访存是不可能相互干扰的。还有一类访存是"不可变"的，例如对于对象的虚函数表的读取和对虚函数表内容的读取，还有对数组长度的读取，它们不会受到其它store指令的影响。事实上还有更多可以利用的信息：例如对于两种没有继承关系的对象的访存一定不会相互影响，对于任何对象的偏移量不同的访存一定不会相互影响(当然，这些规则在c/c++中不一定成立)...再往下深入涉及到了**别名分析**的知识，这超出了这门课的要求，所以我们对于访存的优化也就到此为止了。

> 正如之前的文档中说的，这的确很幼稚，也不可能期望它达到太好的优化效果，大家就把它当成是我的一点小小的尝试就好了，不用太认真

回到公共表达式提取上来，它基于可用表达式(available expression)分析。可用表达式的定义基本上就与我们上面描述的一样：从起点处任何一条路径都会计算且不会被杀死。可用表达式分析是一种前向数据流分析，它的值集是我们关心的所有右端项，例如在实验框架中包括：

```rust
enum TacRhs {
  Bin(BinOp, [Operand; 2]),
  Un(UnOp, [Operand; 1]),
  Load([Operand; 1], i32),
}
```

列举一下一些语句的$$Gen$$和$$Kill$$集合，更完整的表可以参考龙书：

| 语句              | $$Gen$$                    | $$Kill$$            |
| --------------- | -------------------------- | ------------------- |
| a = b op c      | { b op c } - $$Kill$$      | 包含a的右端项             |
| a = \*(b + imm) | { \*(b + imm) } - $$Kill$$ | 包含a的右端项             |
| \*(b + imm) = a | $$\emptyset$$              | 所有形如\*(b + imm)的右端项 |
| call a          | $$\emptyset$$              | 所有形如\*(b + imm)的右端项 |

其中"所有形如\*(b + imm)的右端项"是最简单的实现方法，是没有把`CallHint`和`MemHint`考虑在内的。如果把它们考虑在内，则应该只是一部分形如\*(b + imm)的右端项。

关于表格中的"$$- Kill$$"，其意义是类似于`x = x + y`之类的语句**不能生成**`x + y`，注意是不能生成，而不是既生成又杀死，大家应该能理解这个区别。

有了语句级别的$$Gen$$和$$Kill$$集合后，容易计算出算出基本块级别的$$Gen$$和$$Kill$$集合，然后就可以进行方程求解了，但是还有两个地方需要注意：一是使用的交汇运算符是`And`而不是`Or`，这体现了**所有**路径都有这个计算；二是$$out$$集合的初值应该设置成：

$$
out(Entry) = \emptyset\\
out(B) = U(B \ne Entry)\\
$$

其中$$Entry$$是一个虚拟的起始节点，我们的实现中`bb`数组里并没有它，不过在数据流分析的时候可以假装有它存在，具体细节可以参考代码。赋的初值看起来和其它数据流分析不太一样，其它数据流一般是以空集作为初值，而这里是以全集$$U$$(一般对于虚拟的起始节点/终止节点的赋值不称为初值，而称为**边界条件**，这是因为这个值并不会在迭代中发生改变)。本质上这个初值是半格的顶元素，迭代的过程就是值在半格中不断下降的过程，而$$\cap$$的顶元素是全集，所以这里以全集为初值。

如果暂时不能理解这个初值的话也不用深究，可以大致理解成：在这个初值下我们最初假定所有表达式都是可用表达式，所以赋值为全集$$U$$，然后一步步剔除不是可用表达式的部分，这样就不会漏过任何可用表达式，错过优化机会(相反，在活跃变量分析中我们最初假定所有变量都不活跃，然后一步步增加活跃变量，这样就不会误认为某些变量活跃而错过优化机会)。

得到基本块级别的可用表达式后，再计算每个语句的可用表达式。如果在一个语句处，它的右端项是可用表达式，那么一定可以把这次计算消除，用前面的计算结果来代替，具体做法是：**向前搜索**，找到**最近的所有**可用表达式，然后对每一个都做如下修改：

```
  c = a + b       tmp = a + b
  ...       ----> c = tmp
  d = a + b       ...
                  d = tmp
```

其中`tmp`是一个新的虚拟寄存器，对于"最近的所有"可用表达式所做的修改用的都是同一个`tmp`。"向前搜索"的含义是，从本条语句前一条开始逆向搜索本基本块，然后反向沿着流图继续递归搜索别的基本块。"最近的所有"的含义是，在向前搜索某个基本块的过程中，一旦遇到相同的表达式就停下来，这个基本块的搜索宣告结束，也不再递归搜索它的前驱；否则，如果这个基本块内没有找到，则需要递归搜索它的前驱。