上一篇文章：（三）Datalog 和程序分析

下一篇文章：（五）过程间分析

简介

这一章是对数据流分析的拓展和补充，基本内容如下：

首先从 Def-Use 的角度对控制流图进行简化，但是发现如果变量被多次赋值或者定义，那么简化操作反而会增加更多的边。因此，引入了静态单赋值的方法，所有变量都只赋值一遍，并且再次赋值则视作新的变量。但是分支交汇处的变量，将会不知道来自于其中哪一个分支，因此引入了交汇函数，将所有分支的变量交汇。但是哪些地方需要引入交汇操作呢？探讨了最直接的每个基本块都引入教会操作，但是引入了大量的冗余操作。进而学习了基于支配边界的确定交汇操作的方法。

Def-Use

提出问题

之前的数据流分析中，每个数据节点都必须保存所有的值（抽象域），这就导致即使这个数据节点没有对其中某个值，进行任何的读取或者其他操作，也必须分配额外的存储空间。另外，我们之前假设是所有的数据节点都是有关的，要么是正向分析，要么是逆向分析。但是实际上，可能只有少数几个节点之间的变量才会存在依赖关系。

一个例子见下图：

以上的问题其实可以通过思考「Def-Use」关系来解决。

改进数据流分析

其实很容易理解：给定变量 x，如果结点 A 可能改变 x 的值，结点 B 可能使用结点 A 改变后的 x 的值，则结点 A 和结点 B 存在 Def-Use 关系。

如果只是跟踪变量 x，只要跟踪改变了变量 x 和读取了变量 x 的节点即可，中间的不涉及 x 的节点可以忽视。例如，我们分别考虑变量 x, y，那么只要把节点 0-1-3、2 分成两组即可。

虽然上图看起来更加复杂了，但是对于单独的变量，其实少了中间步骤，生成了更加「稀疏」的图，效率更加高了。总结如下：

• 每个结点只保存自己定义的变量的抽象值。
• 只沿着 Def-Use 边传递抽象值。
• 通常图上的边数大幅减少，图变得稀 疏（sparse）
• 分析速度大大高于原始数据流分析。
• 改进前后的分析结果是等价的。

建立 Def-Use

前面看起来很美好，但是这是基于已经提取了 Def-Use 关系了，但是如何建立呢？实际上这个过程叫做 reachable analysis，而这个过程也是需要静态分析的。具体的例子和程序可以见我写的 《Datalog 和程序分析》 中的应用实例中的数据流分析。复杂度可以参考下图：

另外，如果定义的变量非常多，改进后的图可能不是更稀疏，反而更加多。下面是一个例子：

静态单赋值

介绍

核心思想是：每个变量只被赋值一次，多次赋值的时候就当作不一样的变量。其实这里的「赋值」和定义，在程序分析中看起来不怎么区分。比如下面的程序，x+=y 之后的 x 和原来的 x 是不同的变量。

但是不同的分支有不同的赋值行为，比如上述的 z 的值是不确定的。那么引入了 z2=