数据流分析基础

数据流分析指的是一组用来获取有关数据如何沿着程序执行路径流动的相关信息的技术。

程序的执行可以看作是对程序状态的一系列转换。程序状态由程序中的所有变量的值组成，同时包括运行时刻栈的栈顶之下各个栈帧的相关值。一个中间代码语句的每次执行都会把一个输入状态转换成一个新的输出状态。这个输入状态和处于该语句之前的程序点相关联，而输出状态和该语句之后的程序点相关联。

当我们分析一个程序的行为时，我们必须考虑程序执行时可能采取的各种通过程序的流图的程序点序列（“路径”）。然后我们从各个程序点上可能的程序状态中抽取出需要的信息，用以解决特定数据流分析问题。在更加复杂的分析中，我们必须考虑调用和返回执行时会形成在不同过程的流图之间跳转的路径。

流图给出的可能执行路径的信息如下：

• 在一个基本块内部，一个语句之后的程序点和它的下一个语句之前的程序点相同。

• 如果一个从基本块 $B_1$ 到 基本块 $B_2$ 的边，那么 $B_2$ 的第一个语句之前的程序点可能紧跟在 $B_1$ 的最后一个语句后的程序点之后。

我们可以把从点 $p_1$ 到点 $p_2$ 的一个执行路径定义为满足下列条件的点的序列 $p_1, p_2, ... , p_n$：对于每个 $i = 1, 2, ... , n - 1$ ：

1. 要么 $p_1$ 是紧靠在一个语句前面的点，且 $p_{i+1}$ 是紧跟在该语句后面的点。

2. 要么 $p_i$ 是某个基本块的结尾，且 $p_{i+1}$ 是该基本块的一个后继基本块的开头。

一般来说，一个程序可能有无穷多条可能的执行路径（特别是对于循环结构），执行路径的长度并没有上界。程序分析把可能出现在某个程序点上的所有程序状态总结为有穷的特性集合。不同的分析技术可以选择抽象掉不同的信息，并且一般来说，没有哪个分析会给出状态的完全表示。

数据流分析模式

在所有的数据流分析应用中，我们都会把每个程序点和一个 数据流值 (data-flow value) 关联起来。这个值是在该点可能观察到的所有程序状态的集合的抽象表示。所有可能的数据流值的集合称为这个数据流应用的域。比如，到达定值 的数据流值的域是程序的定值集合的所有子集的集合。某个数据流值是一个定值的集合，而我们希望把程序中的每个点和可能到达该点的定值的精确集合关联起来。对于抽象方式的选择依赖与分析的目标。我们只跟踪相关的信息。

我们把每个语句 $s$ 之前和之后的数据流分别记为 $IN[s]$ 和 $OUT[s]$。数据流问题(data-flow problem) 就是要对一组约束求解。这组约束对所有的语句 $s$ 限定了 $IN[s]$ 和 $OUT[s]$ 之间的关系。约束分为两种，基于语句语义（传递函数）的约束和基于控制流的约束。

传递函数

在一个语句之前和之后的数据流值受该语句的语义的约束。比如，假设我们的数据流分析涉及确定各个程序点上各变量的常量值。如果变量 $a$ 在执行语句 $b \leftarrow a$ 之前的值为 $v$，那么在该语句之后 $a$ 和 $b$ 的值都是 $v$。一个赋值语句之前和之后的数据流值的关系被成为传递函数(transfer function)。

信息可能沿着执行路径向前传播，或者沿着执行路径逆向流动。在一个前向数据流问题中，一个语句 $s$ 的传递函数（通常被记为 $f_s$）以语句前的数据流值作为输入，并产生语句之后的新数据流值。也就是

$$OUT[s] = f_s(IN[s])$$

反过来，在一个逆向数据流问题中，语句 $s$ 的传递函数 $f_s$ 把第一个语句之后的数据流值转变成为语句之前的新数据流值。也就是

$$IN[s] = f_s(OUT[s])$$

控制流约束

基本块中的控制流很简单。如果一个基本块 $B$ 由语句 $s_1, s_2, ..., s_n$ 顺序组成，那么 $s_i$ 输出的控制流值和输入 $s_{i+1}$ 的控制流值相同。也就是

$$IN[s_{i+1}] = OUT[s_i] \quad i = 1, 2, ..., n - 1$$

对于基本块之间的控制流，一个基本块的首语句的定值的集合就是到达它的各个前驱基本块的最后一个语句之后的定值集合的并集。

基本块上的数据流模式

从技术上来讲，数据流模式涉及程序中每个点上的数据流值。控制流从基本块的开始流动到结尾，中间没有中断或者分支。这样我们就可以用进入和离开基本块的数据流值的方式重新描述这个模式。对于每个基本块 $B$ ，我们把紧靠其前和紧随其后的数据流值分别记为 $IN[B]$ 和 $OUT[B]$。关于 $IN[B]$ 和 $OUT[B]$ 的约束可以根据关于 $B$ 中的各个语句 $s$ 的 $IN[s]$ 和 $OUT[s]$ 的约束得到。

假设基本块由语句 $s_1, s_2, ..., s_n$ 顺序组成。如果 $s_1$ 是基本块 $B$ 的第一个语句，那么 $IN[B] = IN[s]$。 类似地，如果 $s_n$ 是基本块 $B$ 的最后一个语句，那么 $OUT[B] = OUT[s_n]$。基本块 $B$ 传递函数记为 $f_B$ ，它可以通过将该基本块中各语句的传递函数组合起来获得该传递函数。也就是说，设 $f_{s_{i}}$ 是语句 $s_i$ 的传递函数，那么 $f_B = f_{s_n} \circ ... \circ f_{s_2} \circ f_{s_1}$ 。该基本块的开头和结尾处的数据流值的关系是

$$OUT[B] = f_B(IN[B])$$

因此，前向数据流问题的方程就可以表示为

$$IN[B] = \bigcup_{P是B的一个前端}OUT[P]$$

逆向数据流问题的方程是类似的，但是 $IN$ 和 $OUT$ 值的角色被调换了。也就是说

$$IN[B] = f_B(OUT[B]) \\ OUT[B] = \bigcup_{S是B的一个后继}IN[S]$$

和线性算术方程不同，数据流方程通常没有唯一解。我们的目标是寻找一个最”精确的“满足这两组约束（即控制流和传递的约束）的解。换言之，我们需要一个解，它能够支持有效的代码改进，但是又不会导致不安全的转换。这些不安全的转换改变了程序计算的内容。

数据流分析中的保守主义

实际数据流分析值是通过程序的所有可能执行路径来定义的。所有的数据流模式计算得到的都是对实际数据流值的估算。我们必须保证所有的估算误差都在”安全“的方向上。如果一个策略性决定不允许我们改变程序计算出的内容，它就被认为是”安全的“（或者说”保守的“）。遗憾的是，安全的策略导致我们错失一些能够保持程序含义的代码改进的机会。但实际上对所有优化技术而言，没有哪个安全的策略可以保证不错失任何机会。使用不安全策略就是以改变程序含义的代价来加快代码速度。一般来说，这是不可接受的。

因此在设计一个数据流模式的时候，我们必须知道这些信息将如何被使用，并保证我们做出的任何估算都是在“保守”或者说“安全”的方向上。每个模式和应用都要单独考虑。比如，如果我们把到达定值信息用于常量折叠，那么把一个实际上不可到达的定值当作可到达就是安全的（我们可能在 $x$ 实际是一个常量且可以被折叠的情况下认为 $x$ 不是一个常量），但是把一个实际可到达的定值当作不可到达就是不安全的（我们可能把 $x$ 替换为一个常量，但是实际上程序有时会赋予 $x$ 一个不同与该常量的值）。

数据流方程

传递方程

传递方程描述了基本块内部的信息转换过程，即 输入状态如何转换为输出状态。

假设一个基本块 $B$，它的语句为 $s_1, s_2, ... , s_n, n \in \mathbb{N}$ 。那么 $B$ 的传递函数可以表示为 $f_B = f_{s_n} \circ ... \circ f_{s_2} \circ f_{s_1}$ 。我们定义传递方程为

$$OUT[B] = f_B (IN[B])$$

其中 $IN[B]$ 为基本块 $B$ 入口处的数据流值，$OUT[B]$ 为基本块 $B$ 出口处的数据流值。

传递函数需要根据数据流分析问题而设计。有几种常用的传递函数模型：

1. 生成—销毁模型

   最常见的形式，适用于位向量表示的数据流问题。

   $$f_B(IN) = (IN - KILL_B) \cup GEN_B$$

2. 符号函数模型

   适用于复杂分析

   $$f_B(IN) = g(s_1(g(s_2(...g(s_n(IN))))))$$

   其中 $s_1, s_2, ... , s_n, n \in \mathbb{N}$ 是块中的语句，$g$ 是每条语句的传递函数。

3. 单调函数模型

   $$f_B(IN) = F_B(IN)$$

   其中 $F_B$ 是单调函数，满足：

   $$\text{如果 } X \sube Y \text{ , 则 } F_B(X) \sube F_B(Y)$$

控制流方程

控制流方程描述了信息如何通过控制流边在基本块之间传播，即 基本块入口状态如何由前驱/后缀决定 。控制流分析可以分为前向分析

$$IN[B] = \bigwedge_{P \in pred(B)} OUT[P]$$

和 后向分析

$$OUT[B] = \bigwedge_{S \in succ(B)} IN[S]$$

其中 $pred(B)$ 和 $succ(B)$ 分别表示 $B$ 的前驱基本块集合和后继基本块集合，$\wedge$ 表示交汇操作。在任何数据流模式中，我们用交汇运算来汇总各条路径会合点上不同路径所作的贡献。

数据流分析框架

半格

在每一种情况中，数据流分析都是通过对一种称为 格(Lattice) 的代数结构的元素进行运算来完成的。格的元素代表变量、表达式，或一个过程所有可能执行的其他程序设计结构的抽象性质——这种性质与输入数据值无关，通常也与过程流经的控制流路径无关。多数数据流分析都不关心程序执行条件的真假，即不关心 if 是取 then 分支还是 else 分支，也不关心循环的执行次数。我们将过程中每一种可能的控制流和计算结构与一个所谓的流函数关联起来，这个流函数将每个结构的作用抽象成对应的格元素的作用。

出于理论严谨性和实际需求的平衡，通常我们在数据流分析中使用 半格(Semilattice) 而非完整的 格(Lattice) 。

"在计算机科学中，我们使用半格不是因为它们完美，而是因为它们足够好且实际可行。"

—— 引自《数据流分析基础》(Foundations of Data Flow Analysis)

在数据流分析中，只需要保证元素可以 “向上”合并（汇集信息）或 “向下”合并（分发信息），而不一定需要同时具备两种操作。这导致了半格的概念。

定义：一个半格是一个集合 $L$ 和一个二元操作 $\wedge$ 并且对于所有 $x, y, z \in L$，我们有：

$$\begin{align*} & x \wedge x = x & \text{等幂性} \\ & x \wedge y = y \wedge x & \text{可交换} \\ & x \wedge ( y \wedge z ) = (x \wedge y ) \wedge z & \text{结合律} \end{align*}$$

半格有一个顶元素，表示为 $\top$ ，使得对于 $L$ 中迭代所有 $x$， $\top \wedge x = x$。半格可能还有一个底元素，表示为 $\bot$ ，使得对于 $V$ 总的所有 $x$ ，$\bot \wedge x = \bot$。

我们为半格 $(L, \wedge)$ 定义偏序 $\preceq$ ：对于 $L$ 中的所有 $x$ 和 $y$ ，我们定义

$$x \preceq y \quad \text{当且仅当} \quad x \wedge y = x$$

因为交汇运算 $\wedge$ 是等幂的、可交换的且满足结合律，上面定义的偏序 $\preceq$ 就是自反的、反对称的和传递的。

• 自反性：对于所有的 $x$，$x \preceq x$。因为交汇运算时等幂的，因此 $x \wedge x = x$。
• 反对称性：如果 $x \preceq y$ 且 $y \preceq x$，那么 $x = y$。在证明中，$x \preceq y$ 意味着 $x \wedge y = x$，而 $y \preceq x$ 意味着 $y \wedge x = y$。根据 $\wedge$ 的可交换性， $x = (x \wedge y) = (y \wedge x) = y$。
• 传递性：如果 $x \preceq y$ 且 $y \preceq z$，那么 $x \preceq z$。证明如下：$x \preceq y$ 且 $y \preceq z$ 意味着 $x \wedge y = x$ 且 $y \wedge z = y$。根据交汇运算的结合律可得到 $(x \wedge z) = ((x \wedge y) \wedge z) = (x \wedge (y \wedge z)) = (x \wedge y) = x$。所以有 $x \preceq z$，证明完毕。

在其他文献中你可能看到 并半格(Join Semi-Lattice) 或 交半格(Meet Semi-Lattice) 这两个术语。假设一个偏序集 $(S, \preceq)$ ，按照格的运算操作将半格分为两种：

• 并半格(Join Semi-Lattice)：如果对于 $S$ 中的任意两个元素 $a$ 和 $b$ ，都存在一个最小上界 $a \vee b \in S$。
• 交半格(Meet Semi-Lattice)：如果对于 $S$ 中的任意两个元素 $a$ 和 $b$ ，都存在一个最大下界 $a \wedge b \in S$。

注：$\wedge$(Meet) 或 $\vee$(Join) 只是格的两种操作，它们只是运算的抽象符号，并不限定某一个或某一种操作方式。它们的实际操作含义需要根据格的数据对象而赋予。

需要注意的是，半格只要求一种操作（Join 或 Meet）对于任意两个元素存在。半格高度必须是有界的，半格中任意链（一个全序子集）的最大长度减一成为半格的高度。这个高度决定了迭代数据流分析算法在最坏情况下的迭代次数上限。