数据流分析

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

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

基本原理
数据流分析试图获得程序中每一点的特定信息。通常，在基本块的界限内就可以获得这些信息，因为很容易计算基本块中的信息。在前向流分析(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 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，那么在条件不满足的分支，分析会假设x0确实成立。
一个上下文敏感的分析是一个交互过程分析，在分析目标函数的调用时它将考虑调用的信息。特别的，使用上下文信息，可以回退到原始的调用点，而如果没有这种信息，分析时就必须回退到所有可能的调用点，而丧失潜在的精度。

评论 (0)