第3章
数据流分析基础知识

数据流分析是编译优化、代码生成中重要的理论基础之一，最早由Jack Dennis和他的学生在1960年左右引入。数据流分析的数学基础是离散数学中的半格（Semi-Lattices）、格。离散数学中一个研究重点是集合上定义的关系，这些关系有一些良好的数学特性。例如，如果找到满足一定条件的集合关系，则可以证明通过这些关系进行的仿射变换一定有解。本章探讨的半格、格就是这样的一些集合和关系组成的二元组。半格、格等不仅仅是编译优化、代码生成的重要理论基础，也是程序分析、验证、自动化测试等系统理论的基础。本章首先介绍半格、格与不动点相关理论，然后介绍数据流分析，最后通过例子演示如何构造和使用数据流方程。

3.1 半格、格与不动点

本节介绍半格、格和不动点的相关定义、性质和定理。

3.1.1 半格和偏序集

1.半格

半格 是一个二元组记为< S ,∩>。其中， S 表示集合，∩表示集合 S 上的一个二元关系，并且满足以下特性。

1） 幂等性 ：对集合 S 中任意的元素 x ，有 x ∩ x = x 。

2） 交换性 ：对集合 S 中任意的元素 x 和 y ，有 x ∩ y = y ∩ x 。

3） 结合性 ：对集合 S 中任意的元素 x 、 y 和 z ，有 x ∩( y ∩ z )=( x ∩ y )∩ z 。

半格中最大下界（Greatest Lower Bound，GLB）：假设有半格< S ,∪>，且集合 S 中存在元素 x 、 y 和 g ，如果满足 g < x ， g < y ，则称 g 为 x 和 y 的一个下界。如果对于 x 和 y 的任意下界 z ，都有 z < g ，则称 g 为 x 和 y 的最大下界。

半格中最小上界（Least Upper Bound，LUB）：假设有半格< S ,∪>，且集合 S 中存在元素 x 、 y 和 g ，如果满足 x < g ， y < g ，则称 g 为 x 和 y 的一个上界。如果对于 x 和 y 的任意上界 z ，都有 g < z ，则称 g 为 x 和 y 的最小上界。

对于半格< S ,∩>， x ∩ y 是 x 和 y 的唯一最大下界。对于半格< S ,∪>， x ∪ y 是 x 和 y 的唯一最小上界。进一步，假如半格< S ,∩>有上界元素 ⊤ （最大元素）或者下界元素 ⊥ （最小元素），则有以下结论：

1）对于集合 S 中任意元素 x ，有 ⊤ ∩ x = x 。

2）对于集合 S 中任意元素 x ，有 ⊥ ∩ x = ⊥ 。

2.偏序集

集合论中“偏序集”也是一个非常有用的概念，它具有一些良好的数学特性。 偏序集 对应的二元组记为< S ,≼>，其中 S 表示集合、≼是集合S上的一个偏序关系对，满足以下性质：

1） 自反性 ：对于集合 S 中任意的元素 x ，有 x ≼ x 。

2） 反对称性 ：对于集合 S 中任意的元素 x 和 y ，有 x ≼ y 和 y ≼ x ，则 x = y 。

3） 传递性 ：对于集合 S 中任意的元素 x 、 y 和 z ，有 x ≼ y 和 y ≼ z ，则 x ≼ z 。

假设< S ,≼>是一个偏序集，对于任意子集 X 属于 S ：如果集合 X 存在最小上界（记为 ），则 是唯一的；如果集合 X 存在最大下界（记为 ），则 是唯一的。

偏序集由于其传递性特征，能充分表达集合 S 中元素的前后关系。根据定义可以知道，半格和偏序集都有自己的约束，那么对于一个已知的半格，能否在这个半格定义的集合 S 中，寻找一个二元关系，使得这个二元关系构成半格中集合 S 上的一个偏序关系？这样就可以先定义半格，然后对半格定义一个二元关系，使得半格可以通过二元关系定义元素的前后关系。经研究发现通过以下定理即可满足诉求。

定理： 半格< S ,∩>定义一个二元关系≼，对于集合 S 中所有的元素 x 和 y ，如果 x ≼ y ，当且仅当 x ∩ y = x 时，则关系≼是一个偏序关系。

证明如下：半格上的二元关系满足自反性、反对称性和传递性。

1） 自反性 ：因为 x ∩ x = x ，所以 x ≼ x 。

2） 反对称性 ： x ≼ y ，则意味着 x ∩ y = x ； y ≼ x ，则意味着 y ∩ x = y 。由∩的交换性可以得到 x = x ∩ y = y ∩ x = y 。

3） 传递性 ：由 x ≼ y 、 y ≼ z ，有 x ∩ y = x ， y ∩ z = y 。由∩的结合律可以得到 x ∩ z =( x ∩ y )∩ z = x ∩( y ∩ z )= x ∩ y = x ，因此有 x ∩ z = x ，所以 x ≼ z 。

3.1.2 格

格< S ,∩,∪>是一个三元组，其中 S 表示集合、∩和∪是集合 S 上的两个二元关系，对于集合 S 中的任意 x 、 y 和 z ，有以下性质：

1） 交换律 ： x ∩ y = y ∩ x ， x ∪ y = y ∪ x 。

2） 结合律 ： x ∩( y ∩ z )=( x ∩ y )∩ z ， x ∪( y ∪ z )=( x ∪ y )∪ z 。

3） 吸收律 ：x∪(x∩y)=x，x∩(x∪y)=x。

同样，偏序关系≼可以扩展到格中。对于格< S ,∩,∪>，如果集合 S 中任意的x和y，有x≼y且x∩y=x、x∪y=y，则≼构成格中的一个偏序关系。

格< S ,∩,∪>中的∩和∪运算对确定的偏序关系≼来说是单调的，即对于集合 S 中任意的x ₁ 、y ₁ 、x ₂ 和y ₂ ，如果x ₁ ≼x ₂ ，y ₁ ≼y ₂ ，则有(x ₁ ∩y ₁ )≼(x ₂ ∩y ₂ )，(x ₁ ∪y ₁ )≼(x ₂ ∪y2)。

在实际工作更为常见的一个概念是完备格。当且仅当集合 S 中的任何一个子集都有最小上界和最大下界时，格< S ,∩,∪>称为完备格（英文为complete lattice，也称完全格）。可以证明：

有限个元素的格都是完备格。（可以通过数学归纳法证明，此处省略。）

该结论最大的用处在于， 通过完备格定义一个偏序关系，则该偏序关系一定可以收敛，并收敛于最大下界或者最小上界处。

另外，格或者半格还有一些运算属性，例如两个格或者半格在满足一定条件的情况下，通过加、乘后仍然是格或者半格；格或者半格通过函数映射后仍然是格或者半格。这些方法在实际工作中非常有用，比如可以通过它们的运算属性有效地提高程序分析的精度。

假设有一个集合 S 包含三个元素： s 1、 s 2、 s 3。在该集合上定义一个幂关系，生成的结果称为幂集（英文是power set，是由集合中所有元素构成的子集），那么该幂集包含的元素有{},{ s 1},{ s 2},{ s 3},{ s 1, s 2},{ s 1, s 3},{ s 2, s 3},{ s 1, s 2, s 3}，将{}记为 ⊥ 、{ s 1, s 2, s 3}记为 ⊤ 。在幂集上再定义一个关系：包含关系（即一个元素包含另外一个元素，例如元素{ s 1, s 3}包含 s 1和 s 3），它是一个偏序关系（满足偏序关系所有条件），那么该幂集和包含关系构成一个完备格。假设幂集记为 Ps ，包含关系记为⊆，则三元关系< Ps ,∩,∪>和偏序关系⊆构成一个完备格，记为< Ps ,⊆>。 Ps 中任意的 x 、 y ，对于包含关系都满足交换律、结合律和吸收律，同时 Ps 中任何一个子集都存在最小上界和最大下界，因此它是一个完备格。该完备格的示意图如图3-1所示。

图3-1也称为Hasse图（哈斯图），满足完备格的所有特性，其中的箭头方向表示被包含关系。

3.1.3 不动点

假设函数 f 是从定义域 Χ 到值域 Χ 的一个映射（ f 可以简单表示为 f ( x _i )= x _j ），由于定义域和值域集合相同，都使用 X 表示。如果 X 中存在一个元素 x ，满足方程 f ( x )= x ，则称 x 是函数 f 的不动点。泛函分析和拓扑学研究的主要方向之一就是不动点理论，其主要研究为：是否存在不动点？如果函数存在不动点，不动点的个数、性质是什么以及如何求解？

函数可以有0、1或者多个不动点。从直观上理解，函数的不动点就是那些函数映射到自身的点。从图形上看，可以认为函数和直线 y = x 的交点就是不动点。

当函数有多个不动点时，可能存在最大不动点和最小不动点。假设< S ,≼>是一个偏序集， f 是 S 上的一个函数，且有 f ( S )= S 以及 x 是 f 的一个不动点，如果对于任意的 y ，有 f ( y )= y ，且 x ≤ y ，则 x 是 f 的最小不动点。同样假设< S ,≼>是一个偏序集， f 是 S 上的一个函数，且有 f ( S )= S ，假设 x 是 f 的一个不动点，如果对于任意的 y ，有 f ( y )= y ，且 x ≥ y ，则 x 是 f 的最大不动点。

对于函数 f ( S )= S ，某个 x 属于 S ，则对 f ( x )再应用 f 得到的结果为 f ( f ( x ))，称为对 x 的迭代操作，记为 f ₂ ( x )。依此类推，则有以下记法。

1） f _{n +1} = f ( f _n ( x ))= f _n * f

2） f _{n + m} = f _n * f _m

3） f ( f _n ) m = f _{n * m}

有些函数可以通过迭代求解不动点。给定一个函数 f ，以及一个初值 x ₀ ，通过反复迭代计算 f ( x ₀ )， f ( f ( x ₀ ))， f ( f ( f ( x ₀ )))，...，如果函数最终收敛（函数迭代的值不再变化），必定收敛于一个函数的不动点。

离散数学中的不动点理论有几个重要的应用，其中一个就是在编译优化中求解数据流方程。Knaster-Tarski不动点定理指出， 完备格上的任何单调函数都有一个不动点 。这意味着定义一个格，然后寻找一个可处理格中元素的单调函数 f ，就可以到达函数 f 的不动点。到达不动点意味函数计算的结果不会发生变化， 即计算可以终止，此时的解就是一个稳定的解 。

Knaster-Tarski不动点定理指的是，对于一个完备格< S ,∩,∪, ⊤ , ⊥ >，满足函数 f ( S )= S ，且 f 是单调函数，则 f 存在一个最大和最小不动点，同时 f 的所有不动点集合构成一个完备格。

Kleene不动点定理则证明了如何在完备格中求解不动点。该定理引入了上升链条件和下降链条件。

1） 上升链条件 指，当且仅当 S 中任何无穷序列 x ₀ ≼ x ₁ ≼…≼ x _n ≼…都不是严格递增（即存在 k > 0，对于任意 j > k ，都有 x _k = x _j ）时，< S ,≼>是一个满足上升链的偏序集。

2） 下降链条件 指，当且仅当 S 中任何无穷序列 x ₀ ≽ x ₁ ≽ … ≽ x _n ≽ …都不是严格递减（即存在 k > 0，对于任意 j > k ，都有 x _k = x _j ）时，< S ,≼>是一个满足下降链条件的偏序集。

Kleene不动点定理是指，对于一个完备格< S ,∩,∪, ⊤ , ⊥ >，如果有二元组< S ,≼>满足上升链条件，且 f ( S )= S 是 S 上的单调函数，则 f 存在一个唯一的最小不动点。如果二元组< S ,≼>满足下降链条件，且 f ( S )= S 是 S 上的单调函数，则 f 存在一个唯一的最大不动点。

Knaster-Tarski不动点定理证明了单调函数在完备格上至少存在一个最大和最小不动点。Kleene不动点定理给出了求解单调函数在满足上升链或者下降链的完备格中最小或者最大不动点，即从 ⊤ 或者 ⊥ 出发，可通过不断迭代收敛到不动点。

3.2 数据流分析原理及描述

数据流分析是一种基于格和不动点理论的技术，该技术能获取目标数据沿着程序执行路径流动后的最终数据。数据流分析获得的数据可以用在后续的编译优化等工作中。例如，某一个赋值语句的结果在任何后续的执行路径中都没有被使用，则可以把这个赋值语句当作死代码消除。而分析赋值语句是否被使用则可以通过数据流分析完成，数据流分析的第一项工作则是建立数据流方程。

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

当分析一个程序的行为时，首先将行为转化为程序执行过程中某一个状态的变化序列，这个变化序列可以通过程序语句执行过程中的输入、输出信息描述；其次要考虑程序执行时所有可能的执行序列（也称为路径），通常路径可以通过程序的CFG分析得到（执行路径可以看作程序点的集合），并根据所有可能执行路径迭代更新程序语句的输入/输出信息，最后得到一个稳定的结果。这个过程称为数据流分析，其步骤可以总结为：

1）基于CFG建立数据流方程（包含节点的输入/输出和转移函数），并根据分析目标来构造一个高度有限的格。

2）迭代计算每个节点的值，直到达到格的一个不动点（只有格才能保证程序在迭代过程中实现终止）。

注意

数据流分析是一种流敏感、路径不敏感的分析技术。流敏感指的是，分析时考虑程序中的语句顺序；路径不敏感指的是，分析时不考虑路径实际的执行情况，认为路径都可以执行。在LLVM中除了传统的数据流分析外，还有流敏感、路径敏感的分析方法。

下面以程序的执行为例对转移函数进行说明。程序的执行本质上是由变量的输入值以及执行的路径决定的输出，故程序的执行可以抽象为程序状态的一系列转换过程，即一条执行语句把程序从一个状态转换到另一个状态。那么可以把程序的语句看作程序状态的转移函数，其输入状态和该语句之前（即程序点）的程序关联，输出状态和该语句后的程序关联。

但是程序的执行路径是不确定的，可能存在很多条执行路径，而且路径的长度也是不固定的，可能是无穷大的。数据流分析过程不可能覆盖所有路径以及所有路径长度，所以实际操作是以CFG节点的所有可能出现的状态信息作为基础进行静态分析，以避免路径爆炸问题。这样的分析过程也意味着信息可能是冗余的（例如动态执行时并不会真正执行某些节点），导致计算结果不够精确（会导致本来可以进行的优化操作无法被执行）。但是和路径爆炸问题相比，计算结果精度稍差是比较容易被接受的。

把所有CFG节点中出现的状态信息构成的集合称为 域 ，域通常是一个格。根据格的理论，只要设计单调的转移函数，经过迭代就一定能保证到达一个不动点，这就意味着经过迭代后，数据流分析一定是可以终止的。

3.2.1 数据流方程形式化描述

在所有的数据流分析应用中，会把每个程序点和一个数据流值（data-flow value）关联起来。数据流值是在程序点可能观察到的所有程序状态的集合的抽象表示。所有可能的数据流值的集合称为这个数据流应用的域。

把每个语句（记为 s ）执行之前和之后的数据流值分别记为In[ s ]和Out[ s ]。把整个程序语句都转换为数据流值，并且根据语句执行的可能性建立约束。约束分为两种，具体如下。

1）基于语句语义（转移函数）的约束：一条语句执行前后的数据流值受该语句的语义约束。假设语句 s 对应的输入状态信息使用In[ s ]表示、对应的输出状态信息使用Out[ s ]表示。数据流分析就是基于In[ s ]或Out[ s ]使用转移函数对语句求解，并更新Out[ s ]或In[ s ]，转移函数是根据输入对语句的信息进行求解获得输出。举一个简单的例子，假设分析目标是收集程序中变量所有可能的值。那么对语句 x =10来说，转移函数就是将值10添加到变量 x 的可能输出中。

2）基于控制流的约束：因为CFG中存在顺序、分支和汇聚节点，所以转移函数还需要考虑不同类型的节点是如何处理转换的。

然后对这些约束求解（这组约束限定了所有语句 s 的In[ s ]和Out[ s ]间的关系），得到的结果就是数据流问题的解。

实际上数据流分析过程是有方向的，也就是说转移函数根据求解目标的不同可以沿着控制流的方向前向传播，也可以沿着数据流逆向传播，分别称为前向分析（或者正向传播）和后向分析（或者逆向传播）。

对于前向分析，转移函数的输入是In[ s ]，输出是Out[ s ]，故有Out[ s ]= f (In[ s ])。还是以收集变量所有可能值为例，这是一个典型的前向分析，从程序的入口开始执行，对每个变量的可能值进行收集，依次处理程序的语句，直到收集完变量所有可能的值，收集过程是沿着CFG方向的。假设收集过程执行到语句 x =10时，In[ s ]中已经包含了 x 的一个初始值（比如1），那么执行完 x =10后，Out[ s ]中应该只会包含 x 的重定义的值10。对于后向分析，转移函数的输入是Out[ s ]，输出是In[ s ]，故有In[ s ]= f (Out[ s ])。

后向分析一般是程序的出口有明确的信息，然后沿着CFG逆向依次计算得到最终的结果，例如计算程序中的活跃变量就是典型的后向分析。原因是程序中最终活跃的变量只有在程序的出口才能确定，只有语句中使用了变量，才能说明变量是活跃的 。所以从最后一条语句开始，根据变量的引用关系逆向分析计算得到最后的结果。3.3.1节会详细讨论活跃变量分析的问题。

CFG中存在三种结构，如图3-2所示。

根据CFG控制流的结构，不同节点之间数据可以相互影响。在前向分析中，前驱节点的输出影响后继节点的输入；在后向分析中，后续节点的输入影响前驱节点的输出。这种因控制结构导致数据间的影响也称为控制流约束。控制流的3种结构对应的前向分析和后向分析的控制流约束如表3-1所示。

控制流约束主要描述的是控制结构对数据流的影响，而转移函数描述的是单个语句对数据流的影响，把转移函数和控制流约束统一后就是数据流方程，如表3-2所示。

根据不动点理论和格理论，最大不动点和最小不动点可以通过迭代计算得到。假设F表示转移函数集合，在计算最小不动点时，数据流方程流动的方向是向上（见图3-1）的，所以初值设置为 ⊥ （表示格中最底部的元素），通过迭代计算最小不动点。在计算最大不动点时，数据流方程流动的方向是向下的，所以初值设置为 ⊤ （表示格中最顶部的元素），通过迭代计算得到最大不动点。最小不动点伪代码如代码清单3-1所示。

代码清单3-1 最小不动点伪代码

最大不动点的计算方式和最小不动点方式相同，唯一的区别就是其初始值设置为 v =（ ⊤ , ⊤ ,... , ⊤ ,..., ⊤ ,... , ⊤ ）。

接下来的一个问题是，上述迭代算法是否正确？算法能否终止？本质上算法的正确性和终止是由数据流方程决定的，那么什么样的数据流方程能保证算法正确且能被终止？

根据格的理论，只要保证迭代算法按照格定义的Hasse图沿着一个方向传播，则理论上就存在最大和最小不动点。沿着一个方向传播意味着转移函数是单调的，所以只要设计一个单调的转移函数就存在最大和最小不动点。

然而理论上的最大和最小不动点是否能够通过迭代得到，还需要另一个约束，那就是格的高度是有限的。如果格的高度无限，意味着虽然存在理论上的MFP（Maximal/Minimal Fixed Point，最大/最小不动点），但循环无法终止（因为需要无限的计算）。所以循环能终止，格的高度必须是有限的。

仍然以求整数变量可能取值为例，来看看如何设计格。示例如代码清单3-2所示。

代码清单3-2 格示例源码

如代码清单3-2所示，变量 x 的取值范围为[0,1,... ,+ ∞ ]，一个自然的想法是，把所有的整数都作为格的元组，然后再通过两两组合构成第二层格元组，再由三个元素构造第三层格元组，依此类推，直到最后一层，得到一个包含了所有整数（包含正数和负数）的元组，格对应的Hasse图如图3-3所示。

这样一个格可以得到整数变量x的所有可能取值，但是这个格高度无限，所以迭代无法终止。那如何构造一个高度有限的格？一种常见的处理思路是将格中的集合元素进行合并。例如可以按元素数进行元组划分，格中元组分别是0个元素、1个元素和任意一个元素。用 ⊥ 表示0个元素的元组，用 ⊤ 表示任意一个元素的元组，此时格对应的Hasse图如图3-4所示。

这个格的高度为3，所以迭代一定会终止。但是这个方程求解的结果不够精确，仅仅能分析该整数变量x是否为空（通常是指变量未初始化），结果为一个确定的值（仅被赋值一次，或者被赋值多次但是多次赋值的结果相同）或者为不确定的值（被赋值多次，且多次产生的输出不同）。

3.2.2 数据流分析的理论描述

以下将通过迭代得到的最大或者最小不动点简称为MFP。那么通过MFP求得的解是否就是最优的结果？

给定一个CFG图，假设图中节点为entry， n 1， n 2，…， nk ，节点对应的转移函数为 f ₁ ， f ₂ ，…， f _k 。如果路径 p 经过节点 n 1， n 2，…， nm ，则该路径的转移函数可以使用 表示；对于空路径， f _p 记为null。

达到节点 n 的 所有执行路径 记为∩ f _p ，我们把这个解称为理想解，记为Ideal=∩ f _p (entry)。 p 是从entry（entry是CFG的入口节点）到节点 n 的一个 可执行路径 。

现实中的程序往往都非常复杂，常会由于组合爆炸原因导致无法静态求解所有执行路径，如循环的实际执行路径可能非常多（本质上可以认为循环的CFG中存在环）。所以存在一些近似处理方法，只考虑所有路径静态可达的情况，而不考虑实际的执行情况，即MOP（Meet Over Path，全路径汇合解），MOP=∩ f _p (entry)， p 是从entry到节点 n 的一条CFG中的 静态路径 。

注意

在计算MOP时仍然要处理循环这样的路径，只不过处理方法与动态执行不同，通常是放松循环执行的边界，认为路径都会被执行。

因为MOP只考虑静态可达路径，所以MOP获得实际执行路径可能比Ideal路径要多，即MOP包含了一部分实际不会执行的路径，记为MOP=Ideal∩Unexecuted Paths（注意：这里∩表示路径组合，不是数学中的交操作）。在精度上来看，MOP的精度低于Ideal，同时MOP更为保守，它没有丢失任何应该包含的解，所以MOP是安全的。

下面通过一段代码演示理想解、MOP的区别，示例如代码清单3-3所示。

代码清单3-3 数据流分析示意源码

该代码片段执行时，因为只有if分支可以执行，else分支不会执行，所以x的值只能为0，这就是理想解。

对于MOP来说，暂时先不考虑实际执行路径，在代码片段执行结束时if分支和else分支都可以到达结束点，所以x的值可能是0或者1。这个例子也直观地说明MOP的精度更差。

而迭代算法求解的方程（以前向分析为例）为：

其解是最大不动点或者最小不动点，都记为MFP。和MOP相比，MFP会考虑在每一个聚合点都对路径进行聚合，而MOP只在路径的终点才对路径进行聚合。以图3-5为例进行说明。

图3-5中存在一条不可达路径，所以理想解Ideal仅仅为 f ( y )，记为Out _{I deal} ；MOP在所有路径的末端进行聚合，所以解为 f ( x )∩ f ( y )，记为Out _MOP ；而MFP在所有的汇聚点都进行聚合操作，所以解为 f ( x ∩ y )，记为Out _M FP。

因为我们设计数据域是格（或者半格），同时选择了单调转移函数 f ，所以 f ( x )∩ f ( y )≼ f ( y )（∩操作导致更多的路径并和，所以后者是前者的子集，用≼表示这个关系），即MOP≼Ideal。

根据格的性质， x ∩ y ≼ y ， f 单调，所以 f ( x ∩ y )≼ f ( x )， f ( x ∩ y )≼ f ( y )，且 f ( x ∩ y )∩ f ( x ∩ y )≼ f ( x )∩ f ( y )，即 f ( x ∩ y )≼ f ( x )∩ f ( y )，也就是说MFP≼MOP。

当转移函数f满足分配律时， f ( x ∩ y )= f ( x )∩ f ( y )。此时MFP=MOP。但是实际工作中一些优化设计的转移函数并不满足分配律，例如常量传播。常量传播的CFG如图3-6a所示。

MFP计算得到的结果为（ ⊤ , ⊤ , ⊤ ），如图3-6b所示；而MOP在最后才聚合，得到的结果为（ ⊤ , ⊤ ,5），如图3-6c所示。常量传播的数据流方程以及求解计算过程将在3.3节详细介绍。

注意

由于理想解中需要判断所有可以执行的路径，因此实际上无法求解。那么为什么 不使用 MOP的方式来计算解？MOP通常也是不可计算的，因为MOP的计算方法蕴含了MPCP（Modified Post Correspondence Problem，修改后的邮局通信问题），而MPCP是不可判定的，所以MOP也是不可计算的。关于MOP的不可计算问题可以参考相关论文。因为Ideal和MOP都不可计算，而MFP总是可以计算的（因为格的特性），所以使用MFP进行计算。

最后看一下MFP算法的复杂度。由前可知，迭代算法是单调递增或者递降的，并最终可以终止。假设CFG中基本块的个数为 n ，则迭代算法每次计算一个基本块后最多传播 n - 1个基本块，那么最坏的情况是每个基本块都需要传播 n - 1次，因此时间复杂度为 O ( n ² )。

3.3 数据流方程示例

本节通过3个例子演示如何使用数据流解决实际问题：活跃变量、到达定值（reaching definition）、常量传播。

3.3.1 活跃变量

活跃变量指的是一个变量从定义点到使用点之间的区间都是活跃的。假设有一个代码片段中定义了变量x，并给出x的活跃信息，如代码清单3-4所示。

代码清单3-4 活跃变量示意源码

活跃变量信息是编译优化、代码生成中最为基础的信息。例如寄存器分配时，只有活跃变量才真正需要被分配寄存器，当变量不再活跃后，意味着已经分配给该变量的寄存器可以重用，从而大大提高寄存器分配效率。

求解程序的活跃变量采用后向分析更为合适，从后向前依次分析每一条语句，得到使用的变量，然后向上找到定义点，从定义点到最后的使用点之间就是变量活跃区间。求解程序活跃变量问题是一个典型的数据流分析问题，下面以基本块为粒度计算每个基本块的活跃变量。先来了解4种与基本块相关的变量集合。

1）Def集合：是指基本块内所有被定值（definition）的变量。所谓的定值可以理解为给变量定义或者赋值，例如加法语句给目标变量定值（store语句不给任何变量定值，load语句则会给对应目标变量定值）。

2）LiveUse集合：是指基本块中所有在定值前就被引用过的变量，包括在这个基本块中被引用到但是没有被定值的变量。

3）LiveIn集合：在进入基本块入口之前是活跃的变量。

4）LiveOut集合：在离开基本块出口的时候是活跃的变量。

其中Def和LiveUse集合依赖于基本块中的指令，基本块从后往前遍历指令便可以求出。

有了这4个基本块集合的概念，每个基本块中活跃变量的数据流方程如下。

该方程的含义是，一个基本块 B 的LiveOut集合是其所有后继基本块 B _i 的LiveIn集合的并集，而且 B 的LiveIn集合是 B 的LiveUse集合与去掉Def集合后的LiveOut集合的并集。

下面通过一个例子简单演示如何求解活跃变量。假设程序对应的CFG如图3-7所示。

因为计算活跃变量是后向分析，所以是从下往上分析，先计算图3-7中最下面基本块G对应的LiveIn和LiveOut，然后沿着CFG向上传播，分别计算LiveOut和LiveIn，最后计算基本块A的LiveOut和LiveIn。因为CFG存在循环，所以需要重复计算直到所有基本块的LiveOut和LiveIn都不再变化，经过迭代三次后发现，第三次迭代和第二次迭代结果一致，可以停止计算。计算结果如表3-3所示（第三次迭代结果和第二次相同，在表中忽略）。

注意

迭代计算过程需要从下往上计算，为了阅读方便，表3-3中基本块顺序也是自下向上的顺序。最终每个基本块的LiveOut就是基本块的活跃变量。

3.3.2 到达定值

到达定值分析是指为程序中使用的变量寻找其定义点（即查找使用的变量是在哪里定义的）。假设示例代码片段如代码清单3-5所示。

代码清单3-5 到达定值分析示例1

对s2而言，s1是y的到达定值。再看一个例子，如代码清单3-6所示。

代码清单3-6 到达定值分析示例2

对s3而言，s1不是到达定值，因为s2“杀死”了y：在s1中定义的值无法到达s3。

在SSA形式的IR中包含了Def-Use和Use-Def信息，所以不需要额外的到达定值分析，但是在非SSA形式的IR中，到达定值分析可以用在很多编译优化工作中。例如在LLVM进行寄存器分配后可以再次进行指令调度，在调度过程中需要分析指令依赖，并消除假依赖，在分析指令依赖过程中就要用到达定值分析，具体可以参考BreakFalseDeps和ReachingDefAnalysis算法。

求解到达定值变量采用前向分析更为合适，从前向后依次分析每一条语句，先得到定义的变量，然后向下找到使用点。对应的数据流方程如下所示：

其中Gen( B )指的是基本块 B 中新定义的变量（包含定义、重定义和赋值操作产生的变量）；而Kill( B )指的是基本块 B 因为重定义而“杀死”原来的变量；In和Out分别指基本块 B 入口、出口到达定值的变量。

下面通过一个例子计算每个基本块中到达定值的变量，假设程序片段对应的CFG如图3-8所示。

因为计算到达定值是前向分析，所以是从上往下分析。先计算图3-8中最上面基本块 A 对应的In和Out，然后沿着CFG向下传播，分别计算In和Out，最后计算基本块 E 的In和Out。因为CFG存在循环，所以需要重复计算直到所有基本块的In和Out都不再变化。经过迭代三次后发现，第三次迭代和第二次迭代结果一致，可以停止计算，计算结果如表3-4所示（第三次迭代结果和第二次相同，在表3-4中忽略）。

最后得到每个基本块的Out信息就是所求结果。

3.3.3 常量传播

常量传播是一种最为基础的编译优化手段，它涉及识别并处理形如int x =5这样的变量定义，在后续代码中又以x指代该常量值的情况，正如代码清单3-7所示的那样。

代码清单3-7 常量传播示例1

在编译阶段需要为x、y分配内存或者寄存器，而x、y在编译器处理时就可以确定它们是常量（分别是5、15），如果遍历整个代码，将x、y直接替换为常量，则不再需要为它们分配内存或者寄存器。在代码清单3-7中，将x等于5这样的事实传播到其他表达式中（本例为y=x + 10），从而减少执行的指令、分配的内存或者寄存器，达到程序优化的效果，这一过程称为常量传播。

首先可以判断常量传播是前向数据流分析，因为常量或者变量总是先定义后使用，即定义在前，使用在后。根据变量的定义可以确定其常量值从前向后传播，所以这是一个前向数据流分析。

变量取值可能有三种，分别是常量（用 C 表示）、非常量（用 ⊥ 表示）、不确定量（用 ⊤ 表示），其中不确定状态也称为未初始化状态，一般是变量的初始状态，例如变量的初始状态为T，当它被赋值一个常量后，它的状态就变成了常量。定义格作为常量传播的值域，假设定义了偏序关系 ⊥ ≼ C ∩ C ≼ ⊤ ，其Hasse图如图3-4所示。

由于常量传播是前向数据流分析，可以对顺序语句和分支转移函数进行如下定义：

1）如果用常量对变量赋值，如x= C ，则把常数 C 添加到x的值中，有Gen={x, C }。

2）如果用变量对变量赋值，如x=y，则把变量y对应的常量添加到x的值中，有Gen={x,{y}}。

3）如果用表达式为x赋值，如x=y op z，有：

①对于可计算的数学运算，如果y、z都是常量，则将y和z运算的结果添加到x的值中，有Gen={x,{y op z}}；如果y和z有一个是 ⊥ ，则x也是 ⊥ ；否则x是 ⊤ 。

②对于不可计算的表达式，则x是 ⊥ 。

交汇语句转移函数的定义如下：

1）如果两个基本块末尾处都是常量，且两个常量值相等，则交汇结果为这个常量。

2）如果一个基本块末尾处是常量，另一个基本块结尾处是 ⊤ ，则交汇结果为这个常量。

3）如果两个基本块末尾处都是 ⊤ ，则交汇结果为 ⊤ ；否则，交汇结果为 ⊥ 。

假设有如代码清单3-8所示的常量传播示例。

代码清单3-8 常量传播示例2

针对代码清单3-8计算程序中变量的常量传播情况如下。

首先根据程序得到CFG图如图3-9所示，为了简单，图中用 S 1、 S 2、…、 S 7表示每一条语句。

在本例中，根据活跃变量分析，变量i、flag都是活跃的，使用二元组（ C 1, C 2）表示i和flag的常量状态。针对每一条语句 S 1、 S 2、…、 S 7，需要先计算Gen和Kill。因为常量传播并不会“重新定义”任何常量，所以Kill全部为空。而分支语句并不会生成常量，所以变量的Gen都是 T ，而 S 4针对变量i进行了自增，所以i不可能是常量，因此i是非常量，记为 ⊥ 。

根据上述转移函数，并根据前向数据流分析公式，迭代计算每一次迭代语句的输入、输出，得到常量传播结果如表3-5所示。

经过三次迭代后，除了 S 1外所有语句的In、Out都认为i和flag是 ⊥ （非常量），在第三次迭代时结果不会发生变化，迭代终止。

注意

该数据流分析还可以进一步优化。对语句 S 3来说，因为输入i等于1，不会执行假分支，即不会执行 S 4，所以i的值永远不会改变。如果基于条件执行复制传播优化，可以发现flag在 S 5、 S 6的值都是1（而非像表3-5中那样都是非常量的结果）。

3.4 扩展阅读：数据流的遍历性能分析

由于数据流方程在求解过程中需要遍历CFG，而数据流方程又分为前向数据流和后向数据流，在求解数据流方程时如何遍历CFG才能让数据流快速达到不动点？

首先研究一下图的遍历以及不同遍历顺序的特点。图的遍历通常有深度优先搜索（Depth-First-Search，DFS）和广度优先搜索（Breadth-First-Search，BFS）两种方法。相比广度优先搜索，深度优先搜索通常消耗的内存更少、性能更高，所以此处仅讨论深度优先搜索。深度优先搜索指的是沿着图的深度遍历节点，尽可能深地搜索分支。当节点所在边都已被搜索过，将回溯节点的上一层节点，直到所有节点搜索完毕。

在搜索的过程中，按照不同的顺序访问（操作）节点，由此又产生了不同的遍历顺序，常见的有两种。

1）前序遍历（pre-order）：在搜索过程，当节点第一次被搜索时，就访问（或操作）节点，构成的节点访问序列就是前序遍历。

2）后序遍历（post-order）：在搜索过程，当节点第一次被搜索时，不访问节点，而是先继续遍历节点的子节点，当所有子节点遍历完成后，回溯节点时再访问（或操作）节点，构成的节点访问序列就是后序遍历。

假定一个待遍历示意图，如图3-10所示。

按照不同的遍历算法可以得到不同的访问顺序。前序遍历得到的访问顺序为： A 、 B 、 C 、 D 、 E 、 F ；后序遍历得到的访问顺序为： C 、 B 、 E 、 F 、 D 、 A 。而在实际工作中有一个常用的顺序：逆后序遍历（Reverse Post-order）。按照该顺序，图3-10中逆后序遍历的顺序为： A 、 D 、 F 、 E 、 B 、 C 。

逆后序遍历有一个非常好的特性是，它能保证在访问节点时，对前驱节点的访问都已完成。例如在图3-10中，访问节点 E 时，已访问完节点 D 、 F ；访问节点 B 时，已访问完节点 E 和 A （而前序遍历没有这样的约束，在前序遍历中 B 节点访问在 E 节点访问之前）。在很多编译器优化实现中，都会要求访问节点时已经访问完其前驱节点，此时只能使用逆后序遍历的顺序来访问节点。

注意

因逆后序遍历特性关系，它常用在拓扑排序（第8章介绍指令调度时会详细介绍）中。

在前向数据流分析中，如果采用逆后序遍历，可以加速不动点的求解速度。原因是在前序数据流分析中，后续节点的信息来自前驱节点，如果前驱节点已经访问完毕（信息已经计算完成），那么后续节点可以直接使用，从而减少循环迭代次数。更进一步可以得到以下结论：

1）对DAG（有向无环图）来说，其实逆后序遍历就是拓扑排序。如果一个有向图没有环的话，也就是一个DAG，以拓扑排序或者逆后序遍历顺序遍历只需要一次迭代便可以收敛，从而得到不动点。

2）对CFG来说，不存在拓扑排序结果，但是深度优先排序这种类似拓扑排序依然能够减少有环图的迭代次数，因为大多数节点的访问都先于其后继节点。

由于RPO存在良好的拓扑排序属性，因此在前向数据流分析中有更好的效果。那么是否可以推广一下，尝试使用逆前序遍历（Reverse Pre-order）来处理后向数据流分析？遗憾的是，逆前序遍历天然存在一些缺点，它并不能保证访问后续节点时前驱节点都已访问完成，读者可自行证明。

3.5 本章小结

本章主要介绍数据流分析相关的基础知识，包括数据流分析的理论基础、数据流方程以及通过数据流方程求解活跃变量、到达定值、常量传播的简单应用。数据流分析是编译优化最为基础的知识，例如涉及第9章介绍的编译优化、第10章介绍的寄存器分配等。 /yIw3RUXiePMIOS8XpuozUwz5sRRbHQ/OjhHt9GGyt7ebLVtneakRI25Et8t6knQ