数据流分析

数据流量分析是一种用于收集有关计算机程序中各个点计算的可能值集的信息的技术。程序的控制流图（CFG）用于确定程序的那些部分可能传播到变量的特定值。在优化程序时，编译器通常会使用收集的信息。数据流分析的规范示例正在达到定义。

对程序进行数据流分析的一种简单方法是为控制流图的每个节点设置数据流程，并通过在每个节点上反复从本地输入计算输出来解决它们，直到整个系统稳定下来，即，它达到了一个固定点。这种通用方法，也称为基尔代尔的方法，是由加里·基尔德尔（Gary Kildall）在海军研究生院任教时开发的。

基本原则

数据流分析是收集有关变量在程序中定义和使用方式的信息的过程。它试图在过程中的每个点获取特定信息。通常，足以在基本块的边界获得此信息，因为从中可以轻松计算基本块中点的信息。在正向流量分析中，块的退出状态是块的进入状态的函数。此功能是块中语句效应的组成。块的进入状态是其前辈出口状态的函数。这产生了一组数据流程：

对于每个块b：

在这上是块的传输函数 。它在入口状态下起作用，产生出口状态。联接操作结合前辈的出口状态的，产生进入状态。

求解这组方程后，可以使用块的条目和/或出口状态在块边界处得出程序的属性。可以单独应用每个语句的传输功能，以在基本块内的某个点获取信息。

每种特定类型的数据流分析都有其自己的特定传输功能和加入操作。一些数据流问题需要向后流分析。这遵循相同的计划，只是将传输功能应用于产生进入状态的退出状态，并且联接操作在继任者的进入状态下行动以产生退出状态。

入口点（向前流）起着重要作用：由于它没有前辈，因此在分析开始时，其进入状态得到了很好的定义。例如，具有已知值的本地变量集为空。如果控制流图不包含周期（过程中没有明确或隐式循环），则求解方程式很简单。然后可以将控制流图按拓扑排序；按照此类顺序运行，可以在每个块的开头计算入口状态，因为该块的所有前身已经处理过，因此可以使用其退出状态。如果控制流图确实包含周期，则需要更高级的算法。

迭代算法

解决数据流程方程的最常见方法是使用迭代算法。它以每个块的状态的近似开始。然后，通过在州内应用传输函数来计算外观。从这些情况下，通过应用JOIN操作来更新状态。重复后两个步骤，直到我们到达所谓的Fixpoint ：在州内（以及随之而来的州内）不会改变的情况。

用于求解数据流程的基本算法是旋转蛋白迭代算法：

因为我←1到n

初始化节点i

而（集合仍在改变）

因为我←1到n

在节点I上重新计算集合

收敛

为了使用，迭代方法实际上应达到解决点。可以通过对状态的价值域，传输功能和联接操作的组合施加约束来保证这一点。

价值域应为有限高度的部分订单（即，没有无限上升链 < <...）。相对于此部分顺序，传输函数和联接操作的组合应单调。单调性可确保在每次迭代中，值要幺保持不变，要幺会变得更大，而有限的高度可确保其不能无限期地生长。因此，我们最终将达到所有X的t（x）= x，这是fixpoint。

工作清单方法

通过注意到，如果块的状态不变，则很容易改进上面的算法。因此，我们介绍了一个工作清单：仍然需要处理的块列表。每当块的外州更改时，我们都会将其继任者添加到工作列表中。在每次迭代中，从工作列表中删除一个块。它的外州是计算的。如果外州发生了变化，则块的后继者将添加到工作列表中。为了效率，一个块不应在工作列表中不止一次。

该算法是通过将信息生成块放入工作列表中开始的。当工作列表为空时，它将终止。

订购

迭代求解数据流程的效率受访问本地节点的顺序影响。此外，这取决于数据流程是否用于CFG上的向前或向后数据流分析。直观地，在向前流问题中，如果在块本身之前对块的所有前辈进行处理，那将是最快的，从那以后，迭代将使用最新信息。在没有循环的情况下，可以以仅处理每个块来计算正确的外观的方式订购块。

在下文中，讨论了解决数据流程方程的一些迭代顺序（ CFG的迭代顺序相关的概念是树的树遍历）。

随机订单- 此迭代顺序不知道数据流程是否解决了向前还是向后数据流问题。因此，与专门的迭代顺序相比，性能相对较差。
Postorder-这是向后数据流问题的典型迭代顺序。在后订单迭代中，访问了所有后继节点后访问了一个节点。通常，以深度优先的策略实施后订单迭代。
反向帖子- 这是用于远期数据流问题的典型迭代顺序。在反向稳定的迭代中，在访问其任何后继节点之前，访问了一个节点，除非后边缘达到后继。（请注意，反向帖子与预订不同。）

初始化

国家内部的初始值对于获得正确和准确的结果很重要。如果结果用于编译器优化，则应提供保守的信息，即应用信息时，该程序不应更改语义。 FIXPOINT算法的迭代将以最大元素的方向为方向。因此，用最大元素初始化所有块是无用的。至少一个块以小于最大值的状态开始。详细信息取决于数据流问题。如果最小元素代表完全保守的信息，则即使在数据流迭代期间也可以安全地使用结果。如果代表最准确的信息，则应在应用结果之前达到FIXPOINT。

例子

以下是可以通过数据流分析计算的计算机程序属性的示例。请注意，通过数据流分析计算出的属性通常仅是真实属性的近似值。这是因为数据流分析在CFG的句法结构上运行，而无需模拟程序的确切控制流。但是，为了在实践中仍然有用，数据流分析算法通常旨在分别计算出实际程序属性的较低近似值。

正向分析

到达定义分析计算每个程序点可能可能达到此程序点的定义集。

  if b == 4 then
     a = 5;
  else 
     a = 3;
  endif
 
  if a < 4 then
     ...

第7行的变量a 的到达定义是第2行的分配a = 5 ，在第4行中的a = 3 。

向后分析

实时变量分析计算每个程序点的变量可能会在下一个写入更新之前可能会读取的变量。死亡代码消除通常使用该结果来删除分配给以后不使用值的变量的语句。

一个块的状态是在其开始时生存的一组变量。最初，在应用传输函数并计算实际包含的值之前，它在块中包含所有变量（包含）。语句的传输函数是通过杀死该块中写入的变量（将其从实时变量集中删除）来应用的。一个块的外状态是在块末端生存的一组变量，并由块的后继者内部的结合进行计算。

初始代码：

b1: a = 3; 
    b = 5;
    d = 4;
    x = 100;
    if a > b then
b2:    c = a + b;
       d = 2;
b3: endif
    c = 4;
    return b * d + c;

向后分析：

// in: {}
b1: a = 3; 
    b = 5;
    d = 4;
    x = 100; //x is never being used later thus not in the out set {a,b,d}
    if a > b then
// out: {a,b,d}    //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}  
// in: {a,b}
b2: c = a + b;
    d = 2;
// out: {b,d}
// in: {b,d}
b3: endif
    c = 4;
    return b * d + c;
// out:{}

由于C已编写C，因此B3的州内仅包含B和D。 B1的外州是B2和B3州内的结合。可以删除C中C的定义，因为C在该声明之后不立即使用。

求解数据流程的开始是从初始化所有国家内部和外州到空集的。工作列表是通过将出口点（B3）插入工作列表（典型的向后流程）来初始化的。其计算的州内与上一方不同，因此插入了其前身B1和B2，并且该过程仍在继续。下表总结了进度。

加工	外面	老州内	新州内	工作清单
B3	{}	{}	{B，D}	（B1，B2）
B1	{B，D}	{}	{}	（B2）
B2	{B，D}	{}	{a，b}	（B1）
B1	{a，b，d}	{}	{}	()

请注意，B1在B2之前输入了列表，B2强迫处理B1两次（B1被重新输入为B2的前身）。在B1之前插入B2将允许较早完成。

用空套初始化是一个乐观的初始化：所有变量都以死亡为单位。请注意，尽管外州可能小于州内的国家，但外州无法从一次迭代缩小到另一种迭代。从以下事实可以看出，在第一次迭代之后，外州只能通过更改状态来改变。由于状态以空套的形式开始，因此它只能在进一步的迭代中生长。

其他方法

几个现代编译器使用静态单分配形式作为可变依赖性分析的方法。

在2002年，马库斯·莫恩（Markus Mohnen）描述了一种新的数据流分析方法，该方法不需要明确的数据流图构造，而是依靠对程序的抽象解释并保留一组程序计数器。在每个条件分支，两个目标都添加到工作组中。遵循尽可能多的说明的每条路径（直到程序结束或无需更改为止），然后从集合和下一个程序计数器中删除。

控制流量分析和数据流分析的结合已显示在识别实现系统功能（例如，功能，需求或用例）的内聚源代码区域中是有用的和互补的。

特殊类别的问题

有多种具有高效或一般解决方案的特殊类别数据流问题。

位矢量问题

上面的示例是数据流值是集合的问题，例如，达到定义的集合（使用程序中的定义位置有一些位）或一组实时变量。这些集合可以有效地表示为位向量，其中每个位代表一个特定元素的设置成员身份。使用此表示形式，可以将联接和传输功能作为位逻辑操作实现。联接操作通常是联合或交叉点，是通过位逻辑或逻辑和逻辑和逻辑实现的。每个块的传递函数可以在所谓的gen中分解并杀死集合。

例如，在实时变量分析中，联合操作是工会。杀戮集是在块中写入的一组变量，而gen集合是读取而无需首先写入的变量集。数据流程变为

在逻辑操作中，这读为

out(b) = 0
for s in succ(b)
    out(b) = out(b) or in(s)
in(b) = (out(b) and not kill(b)) or gen(b)

具有可以表示为位矢量的数据流值集的数据流问题称为位矢量问题， Gen-kill问题或局部可分开的问题。此类问题具有通用的多项式时间解决方案。

除了上面提到的到达定义和实时变量问题外，以下问题是BITVERATER问题的实例：

可用表达式
非常忙碌的表情
使用定义链

IFD问题

概要，有限，分布，子集问题或IFD问题是通用多项式时间解决方案的另一类问题。这些问题的解决方案提供了上下文敏感和流动敏感的数据流分析。

对于流行的编程语言，基于IFD的数据流分析有多种实现，例如在烟灰和WALA框架中用于Java分析。

每个BITVECTOR问题也是IFD问题，但是存在一些不是BitVector问题的重要IFD问题，包括真正的变量和可能的统一变量。

敏感性

数据流分析通常是不敏感的，尽管可以定义产生路径敏感分析的数据流程。

流敏分析考虑了程序中的语句顺序。例如，流动不敏感的指针别名分析可以确定“变量x和y可能指的是同一位置”，而流动敏感分析可以确定“在语句20之后，变量x和y可以指同一位置”。
路径敏感分析计算不同的分析信息，取决于条件分支指令处的谓词。例如，如果一个分支包含条件x>0 ，则在直通路径上，分析将假定x<=0并在分支的目标上，它将假定确实x>0保持。
上下文敏感的分析是概要分析，在分析函数调用的目标时考虑了呼叫上下文。特别是，使用上下文信息可以跳回原始呼叫站点，而没有这些信息，必须将分析信息传播回所有可能的呼叫站点，从而可能丢失精度。