控制流图
复习
- 基本块：单入口、单出口的顺序指令段
- 图：有向图表示节点之间的连接
- 三地址码：常见的中间表示
TL;DR
- 控制流图（CFG）用有向图表示基本块之间的执行流向
- 节点是基本块，边是可能的跳转
- 它刻画了程序所有可能的执行路径
- 很多分析与优化都建立在控制流图之上
正文
基本块切好了，接下来把它们的“流向”画出来——用一张有向图。这张图叫控制流图（control-flow graph，也缩写为 CFG）。
（提醒一句：这里的 CFG 和前面语法分析里的“上下文无关文法”缩写相同，但完全是两回事，别混淆。）
块是节点，跳转是边
控制流图的构造很自然：
- 节点：每个基本块
- 边：从一个块到另一个块的跳转可能。块最后如果是跳转，就画到目标块的边；如果是顺序执行，就画到下个块的边；条件跳转则两条边都画
再额外指定入口节点（程序开始处）和出口节点（程序结束处），整张图就成了。
比如一个 if ... else ...，在控制流图里会呈“一个块分叉成两条边、再汇合到一个块”的形状；一个循环，则会出现一条指回前面某个块的边（形成环）。用图来看，程序的过程控制结构一目了然。
它描述了“程序可能怎么走”
控制流图最大的价值，是把程序所有可能的执行路径，压缩成一张图。
于是很多关于程序的问题，都能转化成图上的问题：
- 某个块是否可达？（这里会不会执行到）
- 有没有环？（是否存在循环）
- 哪些路径能到出口？（有没有“走到一半回不来”的情况）
这些问题，都能用前面数据结构部分学过的图算法（可达性、找环等）来回答。不知不觉，我们又用回了图和图的遍历。
为什么它是基础
控制流图是编译器中端和后端的地基：
- 数据流分析在它上面传播信息
- 很多优化（常量传播、死代码删除等）依赖它判断“什么情况下会执行到这里”
- 寄存器分配等后端步骤也离不开它
可以说，一旦有了控制流图，编译器分析程序就有了“地图”。下一章，我们就用这张地图做第一件大事——数据流分析。
思考题 1
控制流图的节点和边，分别代表什么？
思考题 2
控制流图为什么能帮助分析“程序可能怎么执行”？
小结
知识点
- 控制流图用有向图表示基本块之间的流向
- 节点是基本块，边是可能的跳转
- 它压缩表示程序所有可能的执行路径
- 数据流分析与许多优化都以它为基础
参考资料
- Wikipedia(zh)：控制流图：以基本块为节点的有向图
- Wikipedia(zh)：基本块：控制流图的节点
思考题答案（仅供参考）
思考题 1
节点表示一个基本块（一段顺序执行的指令），边表示从当前块可能跳转或顺序到达的下一个块，也就是执行流可能从哪个块走向哪个块。
思考题 2
因为程序所有可能的执行路径，都能用图中的节点和边表示出来。于是“会不会执行到这里”“有没有循环”等问题，都可以转化为图上的可达性、找环等问题来分析。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪