控制流图(CFG)

定义

控制流图(Control-Flow Graph,CFG)是程序执行路径的图表示:节点为基本块(只能从头进入、从尾离开的极大连续指令序列),有向边表示块之间可能的跳转关系。

构造

扫描中间代码,把跳转目标与跳转指令之后的位置作为基本块边界(首指令),再按分支与顺序执行关系连边;通常附加唯一入口与出口节点。

作用

CFG 是几乎所有全局优化的舞台:数据流分析在其上迭代传播;支配树由它计算,进而支撑 SSA 构造与循环识别(回边);死代码消除依赖其可达性。

延伸

过程间分析把多个函数的 CFG 通过调用图连接;二进制安全领域的控制流完整性(CFI)、模糊测试的覆盖率统计,同样以 CFG 为基础概念。