数据流分析基础：控制流图（CFG）构建、到达定值分析、活跃变量分析、可用表达式分析、在静态分析中的应用

各位同学，今天我们来聊聊数据流分析。说实话，这玩意儿是静态分析的核心中的核心。我做了十几年嵌入式开发，见过太多因为数据流没分析清楚导致的bug——有些甚至是在产品发布后才被发现，那叫一个惨痛。

数据流分析，说白了就是回答一个问题：程序里的数据是怎么流动的？ 变量在哪儿被赋值？在哪儿被使用？哪些计算可以省掉？这些问题，编译器优化需要回答，静态分析工具也需要回答。

嗯，我们先从最基础的东西说起——控制流图。

控制流图（CFG）构建

控制流图，简称CFG。它是数据流分析的骨架。没有CFG，后面的一切都无从谈起。

CFG的构建其实不复杂。每个基本块是一个节点，控制流跳转是一条有向边。基本块是什么？就是一段顺序执行、没有分支的代码。

我给你们看个例子：

int foo(int x, int y) {
    int z = 0;          // 基本块B1开始
    if (x > 0) {        // 条件分支
        z = x + y;      // 基本块B2
    } else {
        z = x - y;      // 基本块B3
    }
    return z;           // 基本块B4
}

这段代码的CFG长这样：

你看，B1根据条件跳转到B2或B3，然后汇合到B4。这就是一个完整的CFG。构建CFG的时候，有几个坑要注意：

• 不可达代码：有些基本块可能永远执行不到，比如return后面的语句。这些块在CFG里是孤岛，分析时要排除。
• 循环结构：循环会产生回边，CFG里会出现环。处理环的时候要小心，迭代分析需要保证收敛。
• 间接跳转：函数指针、switch-case的大表，这些会让CFG构建变得复杂。我建议先用保守策略——把所有可能的目标都加上。

到达定值分析

到达定值分析，英文叫Reaching Definitions。它回答的问题是：在程序的某个点，每个变量可能来自哪个赋值语句？

举个例子：

int a = 1;    // d1: a被赋值
int b = a;    // d2: b被赋值，使用a
a = 2;        // d3: a被重新赋值
int c = a;    // d4: c被赋值，使用a

在d4这个点，a的到达定值是d3，不是d1。因为d3覆盖了d1。但在d2这个点，a的到达定值是d1。

到达定值分析怎么算？核心是数据流方程：

IN[B] = ∪ OUT[p]  (p是B的所有前驱)
OUT[B] = GEN[B] ∪ (IN[B] - KILL[B])

其中：

• GEN[B]：基本块B内产生的定值（即B内对变量的赋值）
• KILL[B]：被B覆盖的定值（即B外对同一变量的其他赋值）
• IN[B]：进入B时有效的定值集合
• OUT[B]：离开B时有效的定值集合

这个方程要迭代求解，直到所有IN和OUT不再变化。嗯，这里要注意：迭代顺序很重要。我一般按逆后序（Reverse Postorder）遍历CFG，这样收敛快。

活跃变量分析

活跃变量分析，Live Variable Analysis。它回答：在程序的某个点，哪些变量将来还会被用到？

如果一个变量在某个点之后不再被使用，那它就是死变量。死变量的赋值可以安全地删除——这就是编译器做死代码消除的依据。

活跃变量分析的数据流方程是逆向的，从后往前分析：

OUT[B] = ∪ IN[s]  (s是B的所有后继)
IN[B] = USE[B] ∪ (OUT[B] - DEF[B])

其中：

• USE[B]：在B中被使用但之前未定义的变量
• DEF[B]：在B中被定义的变量

我给你们看个例子：

int x = 1;    // 点1: x被定义
int y = 2;    // 点2: y被定义
x = x + y;    // 点3: x被使用，然后重新定义
y = 3;        // 点4: y被重新定义
return x;     // 点5: x被使用

在点4，y被赋值3。但y之后再也没有被使用——它是死变量。所以点4的赋值可以删掉。但点2的赋值不能删，因为y在点3被使用了。

可用表达式分析

可用表达式分析，Available Expressions。它回答：在程序的某个点，哪些表达式已经被计算过，且结果仍然有效？

这个分析主要用于公共子表达式消除。如果一个表达式之前算过，且涉及的变量没变，那就不用再算一遍，直接用之前的结果就行。

数据流方程是正向的：

IN[B] = ∩ OUT[p]  (p是B的所有前驱)
OUT[B] = GEN[B] ∪ (IN[B] - KILL[B])

注意这里用的是交集∩，不是并集。因为一个表达式要在所有路径上都可用，才算可用。这是和安全属性（must analysis）对应的。

举个例子：

int a = b + c;    // 表达式 b+c 被计算
int d = b + c;    // 这里 b+c 是公共子表达式，可以直接用a的值
int e = b + c;    // 同上

如果b和c在中间没有被修改，那b+c就是可用表达式，后面两行可以直接复用a的值。

在静态分析中的应用

好了，前面讲了三种基本的数据流分析。它们在实际的静态分析工具里是怎么用的？我挑几个典型的场景说说。

分析类型	检测的问题	实际案例
到达定值	未初始化变量、冗余赋值	检测到变量在条件分支中未赋值就使用
活跃变量	死代码、无用赋值	发现某个全局变量在函数末尾被赋值但从未被读取
可用表达式	公共子表达式、计算冗余	循环内重复计算不变的表达式，可以提到循环外面
组合分析	缓冲区溢出、空指针解引用	结合到达定值和活跃变量，追踪指针的赋值和使用

我个人觉得，数据流分析最强大的地方在于组合使用。比如你要检测一个缓冲区溢出：

• 先用到达定值分析，找到所有对缓冲区索引变量的赋值
• 再用活跃变量分析，确定哪些赋值会影响后续的访问
• 最后结合区间分析，判断索引是否越界

我曾经在一个航空电子设备的代码里，用这套组合拳找到了一个隐藏了三年多的bug。那个bug只有在特定条件下才会触发——两个任务交替执行，导致一个全局变量的值在某个点被错误地覆盖了。到达定值分析清楚地显示，在那个使用点，有两个不同的定值都可能到达，而其中一个是不正确的。

嗯，今天就讲到这里。数据流分析的内容其实很深，我们后面还会讲到更高级的指针分析、过程间分析等等。但先把今天这些基础打牢，后面的内容就好理解了。