# 数据流分析概述

原理课上讲解了两种数据流分析的方法：前向的到达-定值分析和后向的活跃变量分析，公式分别如下：

到达-定值分析：

$$
Out(B) = Gen(B) \cup (In(B) - Kill(B))\\
In(B) = \cup\_{B' \text{ is predecessor of } B} Out(B')\\
$$

活跃变量分析：

$$
LiveIn(B) = LiveUse(B) \cup (LiveOut(B) - Def(B))\\
LiveOut(B) = \cup\_{B' \text{ is successor of } B} LiveIn(B')\\
$$

> 前向的数据流分析是从前**向后**流的，后向的数据流分析是从后**向前**流的。所谓的向前和向后指的是与控制流的方向相同和相反，而从前向后和从后向前指的是绝对方向。

大家也许注意到了，如果进行如下的替换：$$Out \leftrightarrow LiveIn$$，$$Gen \leftrightarrow LiveUse$$，$$In \leftrightarrow LiveOut$$，$$Kill \leftrightarrow Def$$，并且逻辑上将控制流图中的边反向，这两个公式就完全一样了。正因如此，虽然框架中的`flow.rs`内的计算逻辑是前向数据流，但是它也可以用于计算后向数据流，如活跃变量分析。

数据流分析并不只有到达-定值分析和活跃变量分析这两种，我们进行的四种分析/优化中，公共表达式提取，复写传播和常量传播都对应于自己的数据流分析方法，而死代码消除是基于活跃变量分析的。前面三个属于前向的数据流分析，后面一个属于后向的数据流分析。

数据流分析有自己的一套通用的框架：

$$(D, V, \land, F)$$

其中$$D$$表示数据流分析的方向，分为前向和后向两种；$$V$$表示数据流分析的值集，也就是在基本块间"流动"的东西，比如对于到达-定值分析是定值语句，对于活跃变量分析是变量；$$F$$是一个函数集合，表示传递函数，也就是信息流过基本块后会发生什么变化，对应于上面给出的两个方程组中的第一行。

而$$\land$$表示交半格上的交汇运算符，对应于上面给出的两个方程组中的第二行，它刻画的是多个基本块的信息流入一个基本块时的交汇方式。到达-定值分析和活跃变量分析中，交汇方式都是对集合取并集(即$$\land = \cup$$)，但也还有其它的交汇方式，比如对于公共表达式提取，复写传播和用到的数据流分析方法，采用的交汇方式都是集合取交集(即$$\land = \cap$$)；对于常量传播用到的数据流分析，交汇运算符的定义还会更复杂一些。

关于半格的更深入的知识可以参考[wiki](https://en.wikipedia.org/wiki/Semilattice)，关于传递函数自身的性质对于数据流分析的结果的影响可以参考龙书的对应章节，包括数据流方程的收敛性，收敛速度等。这些东西在编译原理这门课上不要求精确的理解，有个大概的印象即可。

对于前向的数据流，通用的公式为：

$$
out(B) = f\_B(in(B))\\
in(B) = \land\_{B' \text{ is predecessor of } B} out(B')\\
$$

对于后向的数据流，通用的公式为：

$$
in(B) = f\_B(out(B))\\
out(B) = \land\_{B' \text{ is successor of } B} in(B')\\
$$

其中$$f\_B \in F$$。一般不会直接定义$$f\_B$$，而是定义$$f\_S$$，用于表示信息流过单条语句后会发生什么变化。设基本块$$B$$的语句依次为$$S\_1, S\_2, ..., S\_{n - 1}, S\_n$$，对于前向数据流，显然有$$f\_B(x) = f\_{S\_n}(f\_{S\_{n - 1}}(...f\_{S\_2}(f\_{S\_1}(x))))$$，即$$f\_B = f\_{S\_n} \circ f\_{S\_{n - 1}} \circ ... \circ f\_{S\_2} \circ f\_{S\_1}$$，其中$$\circ$$是函数组合运算符。对于后向数据流结果是类似的，只是函数组合的顺序要颠倒过来。

> 在数据流分析相关的资料中一般只用$$in$$和$$out$$，很少用$$LiveIn$$和$$LiveOut$$这一对名字，它们应该是特别为活跃变量分析特别起的名字。

为了保证灵活性，实验框架中没有对不同的数据流分析进行更高层次的抽象，只是提供了一些基础组件。`flow.rs`中提供了struct `Flow`，它负责用bitset的形式存储各个集合和迭代计算，这样计算的效率会很高，但是它也只能适用于各种运算都是基于集合运算的数据流分析。这个策略对于公共表达式提取，复写传播和死代码消除都适用，但是对于常量传播并不适用，它需要自己的求解方法，不过大致的思想是类似的。在填写了$$Gen$$，$$Kill$$(或者是$$LiveUse$$，$$Def$$)后，调用`solve(graph)`函数即可迭代解出数据流方程，其中`graph`是用来描述基本块间连接关系的迭代器。

`flow.rs`中提供了一个trait `Meet`，它表示交汇运算符，提供了`Or`和`And`两个实现，分别对应于集合(bitset)的并和交。