数据流分析

数据流分析试图获得程序中每一点的特定信息。通常，在基本块(basic blocks)的界限内就可以获得这些信息，因为很容易计算基本块中的信息。在前向流分析(forward flow analysis)中，一个块的结束状态是这个块起始状态的一个函数。函数由块内的语句的影响信息组成。一个块的开始状态是它的前驱的结束状态的函数。这就产生了一系列的数据流方程：

对于每一个块b:

在这里， 是块的 转移函数。它作用于入口状态，并产生出口状态。连接运算符 将块的前驱节点的出口状态联合起来，产生入口状态。

在求解这一系列方程之后，块的入口和出口状态可以被用来获得程序在块内的属性。每条语句的转移函数可以被分别的用于获得在一个基本块内的某一点的信息。

每一个特定类型的数据流分析都有它自己的特定的转移函数和连接运算符。一些数据流问题需要后向数据流分析。和前向数据流分析类型相比，后向数据流分析使用的转移函数使用出口状态来产生入口状态，连接运算符作用于后继节点的入口状态以产生出口状态。

(在前向流分析中的)入口点起着重要的作用：因为它没有前驱节点，它的入口信息在分析开始时是明确的。比如，可以确定的局部变量的值的集合此时为空。如果控制流图并不包含循环(在程序中显性的或隐性的循环)，只需直接求解数据流方程即可。此时可以对控制流图的基本块进行拓扑排序；按照排序后的结果依次计算，则每个块的入口状态都可以在块起始处计算，因为此时块的所有前驱节点都已经计算过了，所以它们的出口状态是可以获得的。如果控制流图包含循环，那么就需要一个更高级的算法。

最常用的用于求解数据流方程的方法是使用迭代算法。它由每个块的近似入口状态信息出发。然后应用转移函数基于这些入口状态信息计算出口状态信息。然后，使用连接运算符更新入口状态信息。最后两步将一直进行下去直至到达不动点: 即此时入口状态信息和出口状态信息都不再改变。

一个基本的求解数据流方程的算法是循环迭代算法:

for i ← 1 to N

初始化节点i

while (有集合发生了改变)

for i ← 1 to N

重新计算节点i处的集合

为了可用性的要求，迭代算法应该可以真正到达不动点。这可以通过对状态的值域的联合，转移函数以及连接运算符加上限制条件来保证。

值域应该是有界的 且有序。(比如，不存在一个无限的递增链 < < ...)。转移函数和连接运算符应该是单调的。单调性保持了对值的每次迭代操作要么与之前一致，要么会变大，而有界性保证了它不会无限增大下去。因此最终我们会到达一个状态对于所有的x，有T(x) = x，此时即是不动点。

活性变量

活性变量分析 计算每个程序点上的那些在重新定义前可以被潜在的使用的变量。这个的典型应用是用于死码删除，移除那些给变量赋值但之后变量未被使用的语句。

块的入口状态是在上个块的末端仍然具有活性的变量的集合。

在2002年，Mohnen描述了数据流分析的一个新方法，这种方法不需要显式的构造数据流图,取代了依赖于程序的抽象解释，并保持程序计数器工作列表集合的方法。在每个条件分支，对应的两条路径的目标都被加入工作列表中。每一条路径被尽可能多的指令跟随（直到程序结束点或直到没有变化），然后从工作列表中被移除并取回下一个程序计数。

上述例子中的问题是数据流的值是一个集合，比如可到达定义集(使用比特位来表示程序中定义的位置)，或是活性变量的集合。这些集合可以通过位向量有效的表示，向量中的每一位表示一个特定元素是否属于集合。使用这种表示，连接运算和转移函数就可以通过按位逻辑运算实现。连接运算符是一个典型的取并集或取交集操作，可以通过位运算符逻辑或和逻辑与实现。每个块的转移函数可以被分解为产生集和杀死集。

举例来说，在活性变量分析中，连接运算符是取并集操作。杀死集就是那些在当前块中被重新定义的变量的集合，而产生集就是当前块中在重新定义变量值之前使用的变量的集合。数据流方程因此变为

在逻辑运算中，这可以看做是

in(b) = 0

for s in succ(b)

in(b) = in(b) or out(s)

out(b) = (in(b) and not kill(b)) or gen(b)