数据流分析

数据流分析 是一种用于收集计算机程序在不同点计算的值的信息的技术。一个程序的控制流圖（control flow graph, CFG）被用来确定对变量的一次赋值可能传播到程序中的哪些部分。这些信息通常被编译器用来优化程序。数据流分析的一个典型的例子就是可到达定义的计算。

进行数据流分析的最简单的一种形式就是对控制流图的某个节点建立数据流方程，然后通过迭代计算，反复求解，直到到达不动点。这個方法是由蓋瑞·基爾多在海军研究生院任教时发明的。^[1]

基本原理[编辑]

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

对于每一个块b:

out_{b}=trans_{b}(in_{b})

in_{b}=join_{p\in pred_{b}}(out_{p})

在这里， $trans_{b}$ 是块 $b$ 的 转移函数。它作用于入口状态 $in_{b}$ ，并产生出口状态 $out_{b}$ 。连接运算符 $join$ 将块 $b$ 的前驱节点 $p\in pred_{b}$ 的出口状态联合起来，产生入口状态 $b$ 。

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

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

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

迭代算法[编辑]

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

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

for i ← 1 to N

初始化节点i

while (有集合发生了改变)

for i ← 1 to N

重新计算节点i处的集合

收敛性分析[编辑]

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

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

后向分析[编辑]

活性变量

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

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

// out: {} b1: a = 3; b = 5; d = 4; if a > b then // in: {a,b,d}

// out: {a,b} b2: c = a + b; d = 2; // in: {b,d}

// out: {b,d} b3: endif c = 4; return b * d + c; // in:{}

其它方法[编辑]

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

位向量问题[编辑]

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

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

$out_{b}=(in_{b}-kill_{b})\cup gen_{b}$

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

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)

敏感性分析讨论[编辑]

数据流分析本质上是流分析。数据流分析是典型的路径不敏感的，尽管可以定义数据流方程产生路径敏感的分析是可能的。

以下介绍的内容并不特定于数据流分析。

一个流敏感的分析会考虑程序中语句的顺序。举例来说，一个流不敏感的指针分析可能认为"变量x和y可能指向了同一位置"，而一个流敏感分析会认为"在语句20后，变量x和y可能指向了同一位置"。
一个路径敏感的分析计算了依赖于分支条件的谓词的不同的信息。比如，如果一个分支条件是x>0，那么在条件不满足的分支，分析会假设x<=0；而在满足条件的分支，会假设x>0确实成立。
一个上下文敏感的分析是一个交互过程分析，在分析目标函数的调用时它将考虑调用的信息。特别的，使用上下文信息，可以回退到原始的调用点，而如果没有这种信息，分析时就必须回退到所有可能的调用点，而丧失潜在的精度。

备注[编辑]

^ Kildall, Gary. A Unified Approach to Global Program Optimization. Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. 1973 [2006-11-20].
^ Mohnen, Markus. A Graph-Free Approach to Data-Flow Analysis. Lecture Notes in Computer Science. 2002, 2304: 185–213 [2008-12-02]. （原始内容存档于2011-01-02）.

补充书目、地址及网址[编辑]

Aho, Alfred V. Sethi, Ravi. Ullman, Jeffrey D. Compilers: Principles, Techniques and Tools. Addison Wesley. 1986.
Appel, Andrew W. Modern Compiler Implementation in ML. Cambridge University Press. 1999.
Cooper, Keith D. and Torczon, Linda. Engineering a Compiler. Morgan Kaufmann. 2005.
Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.
Hecht, Matthew S. Flow Analysis of Computer Programs. Elsevier North-Holland Inc. 1977.

[1] Kildall, Gary. A Unified Approach to Global Program Optimization. Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. 1973 [2006-11-20].

[2] Mohnen, Markus. A Graph-Free Approach to Data-Flow Analysis. Lecture Notes in Computer Science. 2002, 2304: 185–213 [2008-12-02]. （原始内容存档于2011-01-02）.

[1]

[2]