数据流分析（进阶）
复习
- 控制流图：基本块之间的执行流向
- 集合与映射：分析中常用的工具
- 图：在图上传播信息
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 数据流分析追踪某个信息在程序各点上的状态
- 它沿控制流传播，反复迭代直到稳定
- 常见问题：可达定义、活跃变量、常量传播
- 它是许多优化的分析基础
正文
有了控制流图，就可以在它上面“跑”信息了。数据流分析（data-flow analysis）要做的，就是追踪某个信息在程序的每一个点上处于什么状态。
一个信息，沿着控制流传播
数据流分析的基本套路是：
- 为每个程序点（基本块的入口／出口），维护一个“当前已知的信息集合”
- 沿着控制流图的边，把这些信息传播到相邻的块
- 每传播一轮，就可能更新某些块的信息
- 反复迭代，直到所有块的信息都不再变化为止（这叫到达“不动点”）
为什么要反复迭代？因为程序里有循环、有分叉汇合，信息可能“绕一圈”又传回来。只有一直传到稳定，才算把所有路径都考虑周全。这和我们在图上反复遍历、直到没有新节点可访问，是一个思路。
它想回答什么
数据流分析能回答的问题很多，举几个典型的：
- 可达定义：某个程序点上，变量
x的值可能是从哪里来的 - 活跃变量：某个程序点之后，变量
x还会不会被用到 - 常量传播：某个点上，变量
x是否一定是某个固定值
这些问题听起来抽象，却是后面优化的“情报来源”。比如，知道了“这个变量以后再也不用了”，才敢把它相关的计算删掉。
为什么它是优化的基础
很多优化，本质上都是“先用数据流分析摸清情况，再据此改写程序”：
- 知道某处变量一定是常量，就能把计算提前算掉
- 知道某段代码的结果没人用，就能删掉
- 知道某两个计算其实一样，就能只算一次
所以，数据流分析虽然自己不直接改程序，却是优化的“眼睛”。下一章要讲的 SSA，则是让这双眼睛看得更清楚的又一项利器。
思考题 1
数据流分析为什么要在控制流图上“反复迭代直到稳定”？
思考题 2
数据流分析的结果，通常被用来做什么？
小结
知识点
- 数据流分析追踪信息在各程序点上的状态
- 它沿控制流传播并迭代到不动点
- 常见问题包括可达定义、活跃变量、常量传播
- 它是许多优化赖以进行的分析基础
参考资料
- Wikipedia(zh)：数据流分析：在控制流图上追踪信息
- Wikipedia(zh)：控制流图：数据流分析的载体
思考题答案（仅供参考）
思考题 1
因为程序中有循环和分叉汇合，信息可能沿着环再次传回某处，改变原先的判断。只有不断传播、更新，直到所有块的信息都不再变化（到达不动点），才能保证考虑到了所有可能的执行路径。
思考题 2
通常被用作优化的依据：例如判断某处变量是否为常量、某个计算的结果是否还会被使用、两个计算是否等价等，从而指导常量传播、死代码删除、公共子表达式消除等优化。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪