数据流分析简介

article/2025/10/1 8:02:26

文章目录

0. 前言
1. 数据流分析简介
- 1.1 数据流分析基本概念
- 1.2 数据流分析结构简述
2. 数据流分析应用
- 2.1 定义可达性分析(Reaching Definitions Analysis)
- - 2.1.1 定义可达描述
  - 2.1.2 定义可达算法
  - 2.1.3 定义可达算法示例
- 2.2 活变量分析(Live Variables Analysis)
- - 2.2.1 活变量描述
  - 2.2.2 活变量算法
- 2.3 可用表达式分析(Available Expressions Analysis)
- - 2.3.1 可用表达式描述
  - 2.3.2 可用表达式算法
  - 2.3.3 可用表达式算法示例
- 2.4 小结
数据流分析基础

0. 前言

下面为静态分析课程的粗浅笔记。

南京大学数据流应用和基础：课件|视频

北京大学数据流基础和性质：课件|视频

个人偏向于喜欢南大的课程介绍方式。先介绍三种数据流分析的应用，再用给出数据流分析框架，并进行相关的证明。

课程中介绍的是流敏感&路径不敏感的数据流分析，它建立在控制流程图之上。建议先了解下三地址码转换成控制流程图。

注明：由于博客采用的是CC 4.0 BY-SA协议，但文中图片来自与课件截图。所以这些图片版权归课程老师所有。

1. 数据流分析简介

1.1 数据流分析基本概念

我尝试找一篇数据流分析的中文论文，好把论文中数据流分析的基本介绍搬运过来。但是没找见特别合适的论文。所以，这里，我们搬运下数据流分析-wiki：

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

进行数据流分析的最简单的一种形式就是对控制流图的某个节点建立数据流方程，然后通过迭代计算，反复求解，直到到达不动点。

程序静态分析介绍中已经说明了，静态分析无法做出准确判断。根据不同的情况选择误报或漏报：

may analysis：输出可能正确的信息（需做over-approximation优化，才能成为Safe-approximation安全的近似，可以有误报-completeness），注意大多数静态分析都是may analysis。
must analysis：输出必须正确的信息（需做under-approximation优化，才能成为Safe-approximation安全的近似，可以有漏报-soundness）。

1.2 数据流分析结构简述

在基本块内部，数据流三地址码指令上传递。

在基本块之前，基本块使用前驱基本块的输出作为输入。如果有多个前驱，将它们输出进行may/mus合并。数据流在基本块上传递。

根据需要，数据流可以从上向下，也可以从下向上。

在这里插入图片描述

2. 数据流分析应用

2.1 定义可达性分析(Reaching Definitions Analysis)

2.1.1 定义可达描述

在这里插入图片描述

这里，简单翻译下上面的描述。在d点定义的变量v，可以到达q点。其中p->q的路径中，v没有被重新定义。

这里搬运下定义可达性-wiki中的示例说明。

d1 : y := 3
d2 : x := y
# d1点的变量y,可以到达d2点位置。

d1 : y := 3
d2 : y := 4
d3 : x := y
# d1点中的变量y,不可以到达d3。因为d1点的y在d2点，被重新赋值。

定义可达分析，可用于检测可能的未定义变量。

2.1.2 定义可达算法

第一步定义最上面的虚拟Entry块的OUT为空集。

第二步对所有除了Entry之外的基本块，将其OUT设置为空集。

接下来是一个while循环，一轮循环下来只要有一个BB的OUT改变了，这个循环就不会终止。在这个while循环内部有一个for循环遍历所有的除了Entry之外的BB。然后里面的第一行是：忽略掉程序的条件判断，认为所有分支都有可能到达。执行may分析，将所有的前驱使用并集进行合并。里面的第二行是：B结束后的定义=B中能到达结尾的定义 + (B开始前的定义−由于B中的重新定义而使得失效的那些定义)。。直到所有的OUT都不变了，结果就收敛了，程序就终止了。

在这里插入图片描述

2.1.3 定义可达算法示例

可以参考Data Flow Analysis I-视频的算法迭代过程。

比如对于下面的程序而言，达到不动点之后。我们可以知道，在B5中可达的变量为(0011 1011)向量表示的变量。

在这里插入图片描述

2.2 活变量分析(Live Variables Analysis)

2.2.1 活变量描述

在这里插入图片描述

翻译下上面。活变量分析，判断在程序点p处变量v的值是否能在CFG中由p起始的某条路径中被使用，如果被使用了，那么v在p处存活，否则v就在p处死亡。

活变量分析，可以被用于寄存器分配，如果在过程中寄存器满了，我们倾向于替换一个包含死变量的寄存器（也是一种编译优化）

这里搬运下Live variable analysis-wiki中的示例。

b = 3
c = 5
a = f(b * c)

The set of live variables between lines 2 and 3 is {b, c} because both are used in the multiplication on line 3. But the set of live variables after line 1 is only {b}, since variable c is updated later, on line 2. The value of variable a is not used in this code.

2.2.2 活变量算法

对于程序来说，我们顺着路径正向查找的成本会比较高，因为每一个地方都要递归地查找后面路径、记录信息，直到最后才能判断v是否存活。反向的话，我们可以将存活信息逆着路径传播，把算法变为迭代，成本就会降低。

在这里插入图片描述

其中循环内部，最重要的合并过程和转换函数示例如下。详细见视频：Data Flow Analysis II

在这里插入图片描述

2.3 可用表达式分析(Available Expressions Analysis)

2.3.1 可用表达式描述

一个表达式x op y在程序点p是可用的(可替换)(available)，如果满足：

所有从entry到p的路径都必通过x op y语句。
最后一次使用x op y之后，没有重定义操作数x、y。(如果重定义了x 或 y，则原来的表达式x op y中的x或y就需要被替代)

好处是，一个表达式如果多次出现，但一直没变，则不需要重复计算。

在这里插入图片描述

Available expression-wiki描述了与上面相同的含义：

在编译器优化领域，可用表达式是一种分析算法，它为程序中的每个点确定不需要重新计算的表达式集。据说在这种情况下可以使用这些表达式。要在程序点上可用，不应在从该表达式出现到程序点的任何路径上修改表达式的操作数。

该分析是正向数据流分析问题的一个示例。维护一组可用的表达式。分析每个语句以查看它是否更改了一个或多个可用表达式的操作数。这会在每个基本块的末尾生成一组可用的表达式，在数据流分析术语中称为开头。如果表达式在每个基本块的前辈的末尾可用，则该表达式在基本块的开头可用。这给出了一组可用集合的方程，可以通过迭代算法求解。