控制流图

程序点上的有向图 ​

过程内控制流图写作

其中 $(V,E)$ 是有向图公理库有向图Directed graph · Digraph边具有方向、可表示为顶点有序对集合的图。，$v_{entry}$ 是唯一入口，$v_{exit}$ 是统一出口；若源程序有多处返回，可连接到人工出口节点。节点表示基本块或更细的程序点，边 $(u,v)$ 表示执行完 $u$ 后可能立即进入 $v$。

基本块是具有单入口、单出口的最大直线代码序列：控制只能从首条指令进入，除末条外不会跳出。把每条指令都建成节点也合法，只是图更大；任何数据流方程都必须与所选节点粒度一致。

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

从语法树到控制流 ​

抽象语法树公理库抽象语法树Abstract syntax tree · AST以树结构保留程序构造层次而省略表面语法细节的表示。保留语法嵌套，例如 while 节点拥有条件和循环体子树。CFG 改为展示执行的可能后继：循环体末端有回边指向条件，条件为假时有边离开循环。

考虑程序：

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)$ 可配一个转移关系

赋值边改变环境，条件真边筛选满足 guard 的状态，纯跳转边保持状态。CFG 本身只给控制骨架；这些边语义来自语言的操作语义公理库操作语义Operational semantics用执行判断、转移规则或抽象机定义程序如何运行。。

在例子中，从初始化后的状态 $x=0$ 到循环头是一条控制边；走 input=true 分支后状态变为 $x=1$，走另一分支则变为 $x=2$。仅看到节点邻接无法知道变量值如何变化，必须结合 ${\tau }_e$。

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

调用、异常与并发边界 ​

过程内 CFG 常把调用视作一条带摘要的边。若做 interprocedural analysis，可建立调用图并增加 call/return edges；递归会产生图上的循环，但调用栈仍可能使具体状态空间无限。单纯把调用者返回点直接连到被调函数所有出口，若不匹配调用上下文，会制造不可实现路径。

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

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

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

图结构提供的分析接口 ​

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

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

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