数据流分析 Data Flow Analysis¶

作者: 杨广亮
更新日期: 2026-01-05
版权声明: 本文档遵循 CC BY-NC-SA 4.0 协议

数据流分析（Data Flow Analysis）是程序分析领域中核心技术，旨在刻画数据是如何沿着控制流CFG传播和演变的。早在上世纪70年代，数据流分析算法就被提出来了，可追溯到Kildall在1973年的工作"A Unified Approach to Global Program Optimization"，围绕In/Out和Gen/Kill等重要概念，使用不动点(fixed point)迭代求解。

不动点是指随着算法的运行，程序分析的结果会不断地迭代，最终趋于收敛、稳定、结束。我们称达到收敛的点为“不动点”（fixed point）。不动点理论可追溯至Tarski在1955年的工作“A Lattice-Theoretical Fixpoint Theorem”，通过应用偏序集合上的完备格(complete lattice)的概念,证明在完备格上的单调函数必然存在最小不动点和最大不动点,且可以通过迭代在有限步内计算得到。这对程序分析理论的发展至关重要，包括数据流、指针分析等很多算法都依赖于不动点理论，证明当前算法都可以收敛结束。

本章将围绕数据流分析的算法，讲解def/use和in/out等基本概念，并介绍基于worklist的数据流算法。

1. 指令级 def/use¶

定义def和使用use是数据流分析的基本概念，它描述了数据在程序中的修改和引用情况。对于一条指令而言，def可以指这一指令修改的数据，而use可以指这一指令使用的数据。需要注意的是，本章中的def/use均指变量级的语法定义与使用，不涉及别名、指针或内存精化建模。

从指令的语义出发，指令级def/use往往是静态的，即数据在指令中的修改和引用往往是固定的。

指令类型	指令内容	修改 def	使用 use	备注
variable_decl	var name	∅ (或 {name})	∅	def也可以是{name}，取决于分析策略
assign	target = operand1 \<op> operand2	{target}	{operand1, operand2}
array_write	array[index] = source	{array[index]}	{array, index, source}	是否将array[index]视为独立定义单元，取决于分析是否区分内存位置
array_read	target = array[index]	{target}	{array, index}
field_write	receiver_object.field = source	{receiver.field}	{receiver_object, source}	field是个静态字面量，可以不算是use；在字段不敏感（field-insensitive）分析中，可退化为对receiver弱更新
field_read	target = receiver_object.field	{target}	{receiver_object}
call	target = func(param1, param2, ...)	{target}	{func, param1, param2, ...}	函数调用的def和use往往比较复杂，可能存在副作用，需要作为跨函数单独谨慎处理
return	return value	∅	{value}	value的值可能被传递到caller，同call指令一样，需要放到跨函数分析中单独处理
if	if condition	∅	{condition}

∅：表示空集,即该指令不修改或使用任何变量
赋值指令(assign)：左值被修改,右值被使用
变量声明：不使用或修改任何值；也有的分析框架会把被声明的变量当作被修改以便于分析，因此这主要取决于分析策略
数组操作：array_write中数组本身被修改,同时需要使用数组引用、索引和源值；array_read中目标变量被修改,需要使用数组引用和索引
对象字段操作： field_write中对象被修改,需要使用对象引用和源值；field_read中目标变量被修改,需要使用对象引用和字段
函数调用：有返回值时,目标变量被修改；所有参数和函数引用都被使用；函数调用可能有副作用,影响全局变量或堆对象,需在跨函数分析中特别处理
控制流指令：return不修改变量,使用返回值(如果有)；if等指令不会修改变量，会使用值

其中，对于复杂指令的def/use建模，需要根据分析的精度决定建模方式:

强更新（Strong Update）:当能够精确确定被修改的元素时,可以精确建模。例如,a[0] = 1只修改索引0处的元素。
弱更新（Weak Update）:当无法精确确定被修改的元素时(如索引是变量),需要保守地假设整个数据结构可能被修改。例如,a[i] = 1可能修改数组的任意元素。

在具体分析中，若无法精确区分array[index]或receiver.field，则可退化为弱更新，以保证分析的健全性soundness。

健全性等重要指标

健全性 Soundness 是程序分析中非常重要的概念和指标，与此相关的还有一个Completeness：

健全性 Soundness：指凡是实际发生的问题，都包含在分析结果中，即分析报告包含了实际发生的所有情况，对应的是“健全性和保守性 = 不漏报（False Negative）”。
Completeness：指凡是分析出的结果，就一定是实际发生的，即分析报告是实际发生问题的子集，对应的是“不误报（False Positive）”。

很多程序分析框架追求的是Soundness。如果说一个分析是Sound的，那么意味着“凡是实际发生的都已经在分析报告中了”，这时候，可以说分析结果是安全的Safe。

但是这两个概念过于学术，加上Completeness中文翻译问题，非常导致混乱和误解。为了避免混淆，往往用误报和漏报来描述，更加准确，也更加常用：

误报 FP（False Positive）：指在分析结果中，有些不会实际发生的问题，还是被报告了；对应着，误报率 FPR（False Positive Rate）= 误报数/总报告数量
漏报 FN（False Negative）：指在分析结果中，有些实际发生的问题，但是被遗漏了，没有被报告；对应着，漏报率 FNR（False Negative Rate）= 漏报数/实际发生问题数量

与此对应地，还有两个常见的指标：精确率（Precision）就是1-FPR，召回率（Recall）就是1-FNR。

2. 指令级 In/Out¶

def/use很好地反映一条指令对变量静态地修改和使用情况，但是无法刻画指令与指令之间的动态数据依赖关系。为了解决这个问题，引入了In/Out概念：In是指在进入该指令之前数据流状态，Out是指该指令执行结束后的数据流状态。

“状态”是个非常重要的概念，但是它是完全由数据流的任务来决定，不同数据流分析任务下，对状态的定义是完全不同的。也就是说，在不同的场景下，对状态的定义也是不同的。为了方便，我们以“定义可达性”这一经典的任务为例子来进行解释。所谓的定义可达性是指，给定任意一条指令，能够分析出哪些指令修改后的变量还是可以访问的、可以使用的。例如，

[01] a=1
[02] a=3
[03] b=a

[01]和[02]指令都修改变量a，但是对于[03]指令来说，只有[02]修改a的值是可以使用的，因为[01]修改a的值已经被[02]给覆盖了，因此对于[03]指令执行之前，该指令的状态集合就是{[02] a}。这一状态表示，只有[02]修改了的a是可达的。

基于状态的概念，就可以完整刻画In和Out了。

In 状态集合¶

给定一条指令stmt，它的In状态集合是由控制流图CFG中该指令的所有前驱指令的Out状态集合汇合而成，可以表示为:

In_stmt = ∪(Out_P) for all P ∈ pred(stmt)

其中pred(stmt)表示该指令在控制流图CFG上所有前驱指令

Out 状态集合¶

对于一条指令stmt，它的Out状态集合则是完全有该指令的In状态集合，加上该指令的def/use叠加而成:

Out_stmt = Gen_stmt ∪ (In_stmt - Kill_stmt)

这里面，引入了两个非常重要的函数Gen_stmt和Kill_stmt。Gen是该指令新产生的def，而kill是所有其他语句对相同变量的def。

示例¶

还是以下列代码为例:

[01] a=1
[02] a=3
[03] b=a

来说明[02]指令In和Out状态集合的计算过程:

对于[02]指令，它的In状态集合为[01]指令的Out状态集合，即{[01] a}
```
In_2 = {[01] a}
```
对于[02]指令，它的Out状态集合为[02]指令的In状态集合，加上[02]指令的def/use。它的Gen函数是[02]指令的def集合，即{[02]a}，Kill函数是指在[02]指令之前所有该变量的定义集合，即{[01] a}。

那么[02]的Out状态集合为:

Out_2 = Gen_2 ∪ (In_2 - Kill_2)
      = {[02] a} ∪ ({[01] a} - {[01] a})
      = {[02] a} ∪ ∅
      = {[02] a}

那么[02]指令的Out状态集合为{[02] a}。

3. 定义可达性分析（Reaching Definitions Analysis）¶

定义可达性分析（Reaching Definitions Analysis）是数据流分析中一个重要的任务，旨在分析和计算变量def的可达性。这节介绍一个非常经典的Worklist算法，完成基于In/Out状态的变量def可达性分析。

Worklist算法非常契合基于不动点原理衍生出的算法，通过不断迭代分析结果，直到达到稳定为止。程序分析中很多算法都是基于Worklist算法实现。

以下是基于Worklist算法的定义可达性分析的实现伪代码：

算法: 定义可达性分析（Reaching Definitions Analysis）
输入: 控制流图 CFG（Control Flow Graph，表示每条语句的执行流）
输出: 每一条指令的In和Out状态集合

1. 初始化:
    // 对于每条指令stmt，初始化Out集合为空
    for each stmt:
        In_stmt = ∅
        Out_stmt = ∅

    // 初始化Worklist
    Worklist = {CFG的第一条指令}

2. 迭代:
    // 如果Worklist为空，则结束迭代，到达了不动点
    while Worklist ≠ ∅:
        // 从Worklist中取出一条指令
        stmt = pop Worklist

        // 从CFG中找到stmt所有前驱pred，收集前驱的Out集合，就是stmt的In集合
        In_stmt = ∪(Out_P) for all P ∈ pred(stmt)

        // 计算该指令的Out集合
        Out_stmt_new = Gen_stmt ∪ (In_stmt - Kill_stmt)

        // 检查该指令的Out集合是否改变
        if Out_stmt_new ≠ Out_stmt_old:
            // 如果改变，则更新Out集合
            Out_stmt = Out_stmt_new

            // 把stmt在CFG中所有的后驱指令添加到Worklist中开始迭代
            Worklist = Worklist ∪ succ(stmt)

3. 返回每条指令的In和Out状态集合

根据Tarski不动点定理，状态空间是有限的(所有可能的定义是有限的)，传递函数是单调的(Out集合只增不减)，因此必然在有限步达到不动点，该算法必然收敛。通俗一点，道理也很简单，就是Out_stmt = Gen_stmt ∪ (In_stmt - Kill_stmt)中，只要有kill，那么就意味着会有Gen，即“覆灭意味着新生”，而整个状态集合又是有上限的，上限是所有stmt的def都是可达的，因此，整个迭代过程必然会收敛结束。

4. 示例¶

以下列C源代码中f函数为例：

[01] int x = 1;
[02]
[03] int f(int y) {
[04]     int z;
[05]     if (y > 0) {
[06]         z = x + y;
[07]     } else {
[08]         z = x - y;
[09]     }
[10]     return z;
[11] }

分析函数f中的定义可达性，如果初始状态为{[01]x, [03]y}，那么得到以下结果：

指令编号	指令	def	use	In	Out
[04]	`int z;`	∅	∅	{[01]x, [03]y}	{[01]x, [03]y}
[05]	`if (y > 0)`	∅	y	{[01]x, [03]y}	{[01]x, [03]y}
[06]	`z = x + y;`	z	x, y	{[01]x, [03]y}	{[01]x, [03]y, [06]z}
[08]	`z = x - y;`	z	x, y	{[01]x, [03]y}	{[01]x, [03]y, [08]z}
[10]	`return z;`	∅	z	{[01]x, [03]y, [06]z, [08]z}	{[01]x, [03]y, [06]z, [08]z}

注意，return指令的Out状态表示函数执行结束时的状态，该状态将传递给调用者。在仅进行函数内分析时，也可将return的Out定义为空集。

5. 经典数据流分析任务¶

除了定义可达性分析以外，数据流分析还有用来做很多任务。根据任务和目标不同，在下面对分析方向、分析类型、状态元素、Meet运算、初始值等维度上选择不同的分析策略，达成最终目的。下列表格对几个典型的任务场景进行了总结。

分析任务	任务解释	分析方向	分析类型	状态元素	Meet 运算	初始值
定义可达性(Reaching Definitions)	对于stmt还有哪些变量def可用	前向	May	变量def(stmt, var)	∪（并集）	∅
活跃变量(Live Variables)	对于stmt有哪些变量在未来还会被使用use	后向	May	变量	∪（并集）	∅
到达使用(Reaching Uses)	use被哪些def到达	后向	May	使用点	∪（并集）	∅
可用表达式(Available Expressions)	对于stmt有哪些表达式可用	前向	Must	表达式	∩（交集）	全集
必忙表达式(Very Busy / Anticipated)	对于stmt有哪些表达式在未来还会被使用use	后向	Must	表达式	∩（交集）	全集

下面对不同分析策略予以解释和总结：

（1）分析方向（Forward / Backward）¶

分析方向决定了，数据流信息沿着控制流图（CFG）传播的方向

前向分析（Forward Analysis）：从CFG的入口开始，沿着CFG进行遍历，直到CFG的出口结束

后向分析（Backward Analysis）：从CFG的出口开始，沿着CFG进行逆向遍历，直到CFG的入口结束

定义可达性分析是前向分析。总的来说，和def有关通常是前向，和use有关通常是后向。

（2）分析类型（May / Must）¶

分析类型决定了，状态集合表示的是“可能发生”还是“一定发生”。在May分析中，只要存在一条路径成立，就认为成立，因此，该分析偏保守；在Must分析中，必须所有路径都成立，才认为成立，只要一条路径不成立，就认为不成立，因此，该分析偏严格。

因此，要想取得安全safe的分析结果常用May分析，如果是优化分析的话，则常用Must。

（3）状态含义（State Meaning）¶

状态是In/Out集合中一个元素在语义上代表的含义。例如，对于定义可达性，一个状态代表当前stmt可用的一个def。

（4） Meet运算（∪ / ∩）¶

Meet运算是指当一条指令有多个前驱（或后继）时，如何合并状态。主要有两种方式

并集（∪）：只要有一条路径满足即可（May）

交集（∩）：必须所有路径都满足（Must）

因此，May ⇔ 并集，Must ⇔ 交集

（5）初始值（Initial Value）¶

初始值是指算法开始时，In/Out的默认状态。

总的来说，May分析时，从“什么都不确定”开始，初始值为空集；而Must分析时，从“所有的假设都成立”开始，再逐步否定，初始值为全集。

6. 跨函数分析¶

以上的数据流分析都是单函数的，对于跨函数的数据流分析，通常需要引入函数调用和返回指令，并定义函数的In和Out状态集合。对于经典分析来说，数据流的跨函数分析非常依赖于ICFG（Interprocedural Control Flow Graph，跨函数控制流图）。有了ICFG后，就可以平移整个函数内的数据流分析算法为跨函数分析版本了。

ICFG概念可以参照2-1.程序分析基础。