中端优化：数据流分析

数据流事实（或称为数据流值）是对所有可能具体程序行为的抽象。例如，一个变量 $v$ 可能有具体的取值集合 $\{1, 2, 4, 5, 6, \ldots\}$ 。由于所有可能的取值情况太多，无法一一枚举，所以需要用抽象的方式来表示：用 $v = NAC$ 来表示变量 $v$ 可能有很多不同的值（NAC = Not A Constant，表示“不是常量”）。NAC 是 $\{1, 2, 4, 5, 6, \ldots\}$ 这些具体值的一个抽象表示。

流程
#

数据流方程
#

上图是一个简单程序的控制流图（CFG），每个方框代表一个基本块 $B_1$ , $B_2$ , $B_3$ , $B_4$ ，箭头表示基本块之间的跳转关系。每个基本块的入口和出口都标记了 $IN[B]$ 和 $OUT[B]$ .

$IN[B]$ 和 $OUT[B]$ 表示在基本块 B 之前和之后的数据流事实的集合。
约束条件（Constraints）如下：
- $OUT[B] = f_B(IN[B])$ ，即基本块 B 的出口数据流信息由其入口信息通过传递函数 $f_B$ 计算得到。 $f_B$ 是每个语句的传递函数的复合，即 $f_B = f_n \circ f_{n-1} \circ \cdots \circ f_1$
- $IN[B] = \bigcap_{P \in preds(B)} OUT[P]$ ，即基本块 B 的入口数据流信息是所有前驱基本块出口信息的交集。如图中蓝色部分， $B_2$ 的前驱是 $B_1$ 和 $B_3$ ， $IN[B_2] = OUT[B_1] \cap OUT[B_3]$

这些约束条件共同构成了数据流方程（Data Flow Equations），通过迭代求解这些方程，可以得到每个基本块在程序执行过程中可能的数据流信息。

分析组成与输出
#

首先，为了进行数据流分析，需要定义以下内容：

transfer: 对每个语句或基本块，定义传递函数 $f$ ，用于描述数据流信息如何在该块内变化。
meet: 在多条路径汇合的地方，定义合并函数 $\wedge$ ，用于将不同路径上的数据流信息合并起来（如取并集或交集）。
initial: 为每个基本块设定初始的数据流信息集合（initial set），作为分析的起点。

通过这些定义，数据流分析可以计算出每个基本块入口（ $IN[B]$ ）和出口（ $OUT[B]$ ）处的数据流信息。这些信息反映了在程序执行过程中，在特定点上始终成立的数据流事实。换句话说，分析的结果是对程序所有可能执行路径都成立的静态属性。

`worklist`算法
#

// 初始化每个基本块的IN和OUT
for (each basic block B) {                  
    IN[B] = initial_value;                   // 初始化IN[B]
    OUT[B] = initial_value;                  // 初始化OUT[B]
}

worklist = set_of_all_basic_blocks;          // 初始化工作列表，包含所有基本块

while (!worklist.empty()) {                 
    B = worklist.pop();                      // 取出一个基本块B

    // 计算B的入口信息：合并所有前驱的OUT
    IN[B] = merge_function(OUT[P] for all P in preds(B)); 

    // 计算B的出口信息：应用传递函数
    new_OUT = transfer_function_B(IN[B]);   

    if (new_OUT != OUT[B]) {                 // 如果OUT[B]发生变化
        OUT[B] = new_OUT;                    // 更新OUT[B]
        worklist.push(all_successors_of(B)); // 将B的所有后继加入工作列表
    }
}

后面会介绍几种常见的数据流分析，每种分析的约束条件和传递函数 $f$ 不同，但分析的流程是相同的。

可达定义, Reaching Definitions
#

A definition $d$ may reach a program point, if there is a path from $d$ to the program point such that $d$ is not killed along the path.

如果有一条路径从定义 $d$ 到某个程序点，并且在这条路径上 $d$ 没有被覆盖（kill），那么 $d$ 就可以到达这个程序点。

数据流方程如下：
- $\text{OUT}[B] = f_B(\text{IN}[B]) = \text{gen}_B \cup (\text{IN}[B] - \text{kill}_B)$ 也就是说，基本块 $B$ 的出口可达定义集合等于：
  1. 在 $B$ 内新生成的定义（gen），和
  2. 入口处的定义，去掉在 $B$ 内被覆盖（kill）的那些定义。
- $\text{IN}[B] = \bigcup_{P \in \text{preds}(B)} \text{OUT}[P]$
  即， $B$ 的入口可达定义集合是所有前驱块出口可达定义的并集。

通过上述的数据流方程，可以套用worklist算法迭代地计算出每个基本块入口和出口的可达定义集合，从而分析出程序中每个变量的定义在何处可能被使用。

可用表达式, Available Expressions
#

表达式 $x ~ op ~ y$ 在某点 $p$ 可用，当且仅当：

从入口到 $p$ 的每一条路径都计算了 $x ~ op ~ y$ ；
在到达 $p$ 之前，最后一次计算 $x ~ op ~ y$ 之后，没有对 $x$ 或 $y$ 进行过赋值。

数据流方程
#

$\text{OUT}[B] = e\_gen_B \cup (\text{IN}[B] - e\_kill_B)$
表示基本块 $B$ 出口处的可用表达式集合等于：在 $B$ 内新生成的表达式，加上入口处可用但未被杀死（即未被相关变量赋值覆盖）的表达式。
$\text{IN}[B] = \bigcap_{P \text{ is a predecessor of } B} \text{OUT}[P]$
表示 $B$ 入口处的可用表达式集合是所有前驱块出口可用表达式的交集。只有所有路径都可用的表达式，才算可用。

活跃变量分析, Live Variable Analysis
#

如果p点定义的一个变量在到达exit之前被使用，且被使用之前没有被重新定义，那这个变量就认为是活的。如下图，判断每个变量在每个块的出口是不是活的：

应用场景
#

寄存器分配。编译器需要决定哪些变量放在寄存器里，哪些放在内存里。

dead value（死值）：
当一个变量被重新赋值后，它之前在寄存器中的值就“死了”，不再有用。如果之后还需要用到这个变量的旧值，就必须从内存重新加载到寄存器。
live value（活值）：
如果一个变量还没有被重新赋值（即还“活着”），那么它在寄存器中的值就是有效的。只要已经加载到寄存器，就可以直接使用，无需再从内存加载。

数据流方程
#

活跃变量分析的目标是：判断在程序的某个点 $p$ ，变量 $x$ 的值是否会在从 $p$ 出发的某条路径上被使用。如果会被使用，说明 $x$ 在该点是“活跃的”。

活跃变量分析是反向的，也就是说，信息的传播方向是从程序的出口向入口传播，而不是像可达定义那样从入口向出口传播。这是因为我们关心的是“将来”某个变量是否会被用到，而不是“过去”它是否被定义。如果变量在后续路径上会被用到，那么它现在就是活跃的；如果不会被用到，就是死的。

$\text{IN}[B] = \text{use}_B \cup (\text{OUT}[B] - \text{def}_B)$
表示基本块 $B$ 入口处活跃的变量集合等于：在 $B$ 内被使用的变量，加上出口处活跃但在 $B$ 内没有被重新定义的变量。
$\text{OUT}[B] = \bigcup_{S \text{ is a successor of } B} \text{IN}[S]$
表示 $B$ 出口处活跃的变量集合是所有后继块入口处活跃变量的并集。