第六章：SSA 数据流与跨过程分析
在对闭包和 OOP 的讨论结束后，我们基本可以知道现代编程语言的大部分语法和特性都是可以用 SSA 来表示的。前面的所有内容共同构成了我们后续讨论的基础。
那么，接下来我们就会进一步讨论静态分析在 SSA 视角下将会变的多简单。
基本了解 SSA 视角下的数据流分析和跨过程分析。
知道 Yak SSA 系统是如何实现数据流分析和跨过程分析，他们的表现如何。
数据流基本概念
在本章开始，我们需要重温静态分析中的两个重要且令人头疼的话题，数据流和跨过程分析。并且结合我们前面讨论的 SSA 系统，来讨论这两个话题。读者可以很容易发现这两个话题在 SSA 系统将变的非常具象。
数据流与控制流分离
定义
首先是数据流与控制流问题，一般来说数据流定义为变量和数据依赖边的组合。
-
数据流(Data Flow): 描述数据如何在程序中流动和转换
- 可以表示为:
- 其中 是变量集合
- 是数据依赖边集合
- 可以表示为:
-
控制流(Control Flow): 描述程序执行的路径和顺序
- 可以表示为:
- 其中 是基本块集合
- 是转移边集合
- 可以表示为:
上述案例结合下面代码大家可以更容易理解控制流和数据流
a = 1;
b = a + 1;
c = b + 1;
if (a > 1) {
c = c + 1;
}
e = a + b;
f = e + c;
我们把上述代码案例制作一个流程图，来同时包含控制流和数据流，也最接近人类理解的代码执行流程。
在这个图中，我们发现，数据流和控制流是混合在一起的，通过棱型来区分 IF 分支。
- 实线表示控制流
- 虚线表示数据流（变量之间直接连接）
接下来，我们尝试分离上述图中的数据流和控制流，把它分成两个图。
在用户阅读完分离图之后：
控制流和数据流是程序分析中两个基本但截然不同的概念。它们分别描述了程序的不同方面：控制流关注"程序执行的路径"，而数据流关注"数据的传播和转换"。
让我们从形式化的角度来详细解释：
- 控制流图 (Control Flow Graph, CFG)
在示例代码中：
- 包含了
a = 1; b = a + 1; c = b + 1这些顺序执行的语句 - 包含了
c = c + 1 - 包含了
e = a + b; f = e + c - 转移边 包含了条件跳转和顺序执行的边
- 数据流图 (Data Flow Graph, DFG)
在示例代码中：
- 包含了变量
{a, b, c, e, f} - 数据依赖边 表示变量间的依赖关系，如
a → b表示b的计算依赖于a
在示例代码中，我们可以观察到：
- 变量
c在控制流的不同路径上有不同的定值（c = b + 1和c = c + 1） - 最终的变量
f依赖于多个变量（a、b、c、e）的值 - 控制流决定了
c的实际值，进而影响到f的计算结果
这种控制流和数据流的交织关系，正是后续我们要讨论的 SSA 重要话题。
在很多不熟悉静态代码分析的读者眼里，他其实并不知道控制流和数据流是两个完全不同的概念，而是习惯性的把控制流和数据流混为一谈。
当然也并不是说必须去分离控制流和数据流，毕竟在 “代码属性图” 或 “节点之海” 中，控制关系和数据关系又被放在了一起。
数据流与 UD(DU) 链
由于本章主要讨论数据依赖相关内容，所以关于控制流的讨论，我们就暂时不在这里继续深入了。
在控制流中，我们一般讨论支配关系，但是在数据流中，并不适合套用支配的概念，一般讨论 SSA 形式下的使用-定义链（Use-Def Chain）后面统称为 Use-Def 链。
使用-定义链（Use-Def Chain），简称 UD 链，是 SSA 形式下，变量使用点和其定义点之间的连接关系。