控制流图 | Codeboy's Blog

形式陈述

程序点上的有向图

过程内控制流图写作

G=(V,E,v_{entry},v_{exit}),

这里选择有向图页中允许环的有限变体，并以端点对标识控制边： $E\subseteq V\times V$ ，同一端点对只记录一次后继关系。单个块跳回自身时保留 $(v,v)$ ；若实现还需区分相同端点间的不同分支，可另给弧身份和标签。 $v_{entry}$ 是唯一入口， $v_{exit}$ 是统一出口；若源程序有多处返回，可连接到人工出口节点。节点表示基本块或更细的程序点，边 $(u,v)$ 表示执行完 $u$ 后可能立即进入 $v$ 。

基本块是具有单入口、单出口的最大直线代码序列：控制只能从首条指令进入，除末条外不会跳出。这里“单出口”指控制只在块末端离开，并不要求末端只有一个后继；以条件跳转结尾的块通常有真、假两个后继。把每条指令都建成节点也合法，只是图更大；任何数据流方程都必须与所选节点粒度一致。

边可以带 true、false、异常、调用或返回等标签。标签说明控制为何转移，不等于该条件已经可满足；静态 CFG 常保守地保留语法上可能的两条分支，即使后续分析能证明其中一条不可达。

直觉

从语法树到控制流

抽象语法保留语法嵌套；在编译器中它通常由AST承载，例如 while 节点拥有条件和循环体子树。CFG 改为展示执行的可能后继：循环体末端有回边指向条件，条件为假时有边离开循环。

考虑程序：

text

x := 0
while x < 3:
    if input:
        x := x + 1
    else:
        x := x + 2
return x

入口块初始化 x，随后进入循环头 x < 3。真边到 if input，再分成加一和加二两个块；二者汇合后沿回边回到循环头。假边进入返回块并通向出口。

AST 中两个赋值是 if 的子节点，循环头是它们的祖先；CFG 中关键关系却是两条赋值路径在回边前汇合。语法父子关系不能替代可能后继关系，反向也无法仅从 CFG 恢复所有表达式结构。

循环与条件分支程序的控制流图，两条赋值分支汇合并沿回边返回循环条件 — 控制流图：分支、汇合与回边

例子与边界

程序点与状态转移

若把具体程序状态记作 $\sigma$ ，CFG 边 $e=(u,v)$ 可配一个转移关系

\tau_e\subseteq\Sigma\times\Sigma.

赋值边改变变量或存储状态，条件真边筛选满足 guard 的状态，纯跳转边保持状态。CFG 本身只给控制骨架；这些边语义来自语言的操作语义。

在例子中，从初始化后的状态 $x=0$ 到循环头是一条控制边；走 input=true 分支后状态变为 $x=1$ ，走另一分支则变为 $x=2$ 。若先加二再加二，循环头依次看到 $0,2,4$ ，最后沿假边返回 $4$ ；循环条件并不保证退出值恰为 $3$ 。

图上还可以任意多次沿回边绕行，但这不表示每条图路径都能由具体状态实现。例如要求从 $x=4$ 再沿 $x<3$ 的真边进入循环体，对应的状态转移关系为空。判断路径是否可行，要顺序组合赋值与条件约束，不能只检查各条边是否存在。

程序点可以放在语句前、语句后或基本块边界。写 C(v) 表示在 $v$ 处可能出现的状态集合时，要说明是执行节点前还是后；差一条赋值边会使数据流事实整体错位。

调用、异常与并发边界

过程内CFG常把调用视作一条带摘要的边。跨过程分析先用调用图构造确定各调用点的可能目标，再增加调用边和返回边。递归会产生图上的循环，调用栈仍可能使具体状态空间无限。上下文敏感过程间分析进一步要求出口返回栈顶那次调用的后继；共享出口若任意连向所有返回点，会制造“从c₁进入、从c₂返回”的不可实现路径。

异常控制必须显式加入。可能抛出异常的指令除了正常后继，还可能跳到最近 handler 或过程异常出口；忽略异常边会让“所有路径”证明漏掉真实执行。

并发程序不能仅把每个线程 CFG 并在一起就得到全局行为。共享内存交错、同步和内存模型决定跨线程状态转移；单线程 CFG 是组件骨架，不是完整并发语义。

间接跳转、函数指针与动态派发往往只能保守解析。边集过少会漏行为、破坏可靠性；边集过多会引入不可行路径、降低精度。CFG 的构造本身就是后续分析的信任前提。

推论与应用

图结构提供的分析接口

前驱、后继、回边、强连通分量和支配关系都在 CFG 上定义。worklist 分析沿边传播事实，在汇合节点组合不同前驱的信息；循环造成方程递归，需要不动点迭代。

收集语义把每个程序点映射为所有可达具体状态，单调数据流分析则在较小性质格上近似这些集合。CFG 负责“信息沿哪里流”，transfer function 负责“经过语句时怎样变”，二者不能塞进一个含混的节点标签。

这里的 CFG 是 control-flow graph，不是形式语言中的 context-free grammar。两者共享缩写，却有不同对象、前置和算法；正文首次出现时应写出全称，链接也应指向精确页面。

SSA构造与消解固定一张四块循环图，逐边比较原变量与版本值，并说明为什么关键边上的复制不能提前执行；有限无环IR验证器则以拓扑顺序证明执行终止，再穷举全部位向量输入检查本次翻译。两页分别展示图结构与状态语义怎样形成可核查的证明。

参考资料

Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Pearson, 2007, §§8.4, 9.1–9.3。
Andrew W. Appel, Modern Compiler Implementation in ML, Cambridge University Press, 1998, Chs. 10, 17。
Flemming Nielson, Hanne Riis Nielson, and Chris Hankin, Principles of Program Analysis, Springer, 1999, Chs. 1–2。

形式陈述 ​

程序点上的有向图 ​

从语法树到控制流 ​

程序点与状态转移 ​

调用、异常与并发边界 ​