控制流分析实战：CFG、支配树、数据流与循环优化-开发者社区

做静态分析或者编译器后端的人，大概都遇到过这种场面：一条自己觉得逻辑很清楚的检查规则，丢到真实项目里一跑，误报多到自己都不信；或者写了一个本地小例子跑得飞起的优化 pass，到了大工程上就开始把程序逻辑改坏。这些问题往回追，十有八九会落到同一个地方——底层那套控制流分析做得不够扎实。

控制流分析（Control Flow Analysis，常缩写为 CFA）是程序分析里最基础、也最容易被低估的一环。它要回答的问题听起来很朴素：一段代码执行时，控制流到底可能从哪儿走到哪儿。就这么一件"看路"的事，往上撑着编译器一大半的优化能力，往下是各种静态检查、漏洞扫描、代码理解的命根子。这篇文章不打算把它讲成教科书式的概念罗列，而是按我实际落地时的顺序，从基本块怎么切、图怎么建，一路讲到支配树、数据流方程的不动点求解、循环识别，最后把踩过的坑摊开。适合写过解析器、想做分析工具但不知道从哪下手的同学，也适合已经写过分析但对某些结论"知其然不知其所以然"的人。

1. 控制流分析到底在哪一层，为什么绕不过去

很多人做分析一开始的直觉是：把源码解析成抽象语法树（AST）就够了。AST 确实把代码的结构、嵌套、表达式关系都记下来了，但它有一个致命短板——它记录的是"文本上谁包含谁"，而不是"运行时谁先到谁"。这两件事在顺序代码里看起来一样，一旦出现if、while、goto、switch，就彻底分家了。

举个特别小的例子，你就能体会到差在哪：

int f(int x) { int y; if (x > 0) { y = 1; } return y; }

从 AST 上看，return y这个节点的祖先里有那条赋值y = 1，很容易让人误以为y被定义了。可实际运行的时候，只要x <= 0，就不会走那个分支，return y返回的是一个没被初始化的值。要判断"到return y这一行，y是不是一定被赋过值"，动作里必须把所有可能的执行路径都枚举出来，看每条路径上y是否都被覆盖。这正是控制流分析在干的事：它把代码的执行可达关系抽象成一张图，让"有没有某条路径绕过了赋值"这种问题变成图上的可达性问题。

所以控制流分析在程序分析体系里的位置是底座。往上看，它的下游应用长得一长串：

死代码消除：某个基本块没有任何入口能到达，直接删掉。
常量传播：某个变量在某点只有一个确定的定值能够到达，就能把常量糊进去。
寄存器分配：需要先做活跃变量分析，知道变量在哪几点还"活着"。
SSA 构建：得靠支配边界决定在哪些节点插入 φ 函数。
静态检查：空指针、未初始化变量、资源泄漏、不可达分支，全都依赖 CFG 上的路径信息。

值得注意的是，这些下游能力的上限，几乎完全由控制流分析的精度决定。CFG 少连了一条边，常量传播就会给出错误的结论；异常边、函数指针调用没处理好，误报就会雪崩。我见过太多团队在规则层反复补丁，其实问题在更下面。所以这一层的正确性和完整性，值得花时间抠。

1.1 CFG 能表达什么，又不能表达什么

先给 CFG 一个准确的说法：它是一个有向图，节点是基本块，有向边表示控制流可能的一种转移。它是"may"的世界——一条边只要可能被执行到，就该连上。这里的关键词是"可能"，理解这一点能省掉后面一大半的纠结。

CFG 能表达的：路径是否可达、某点是否在循环里、哪些分支会汇合、哪些代码永远走不到。CFG 表达不了的：具体的取值、循环跑几次、输入相关的分支走向。你要是想在上面算这些，得叠数据流分析或者符号执行。

提示：判断一张 CFG 建得对不对，一个很实用的自检是——所有死代码是不是真的没有入边，所有正常出口是不是都能反向到达入口。这两条随便错一条，上层分析全崩。

1.2 从"看结构"切换到"看路径"的思维转变

新手最容易卡住的，其实不是算法，而是思维方式。你写解析器的时候，脑子里想的是树；一旦进入控制流分析，你就得强迫自己把同样的代码想成一张网。同一条赋值语句，在树里是某个父节点的孩子，在网里是一个块里的一条指令，它可能被多条入边"从不同方向走到"。这种视角切换，练几次就顺了，但它决定你能不能写对后面的算法。

2. 基本块怎么切，图怎么连：控制流图搭建的完整过程

建 CFG 分两步走：先切基本块，再连边。基本块（basic block）的定义很干脆——一段顺序执行、只有唯一入口和唯一出口的指令序列。这句话里的"顺序执行"是关键：块内部除了最后一条指令，前面任何一条都不能是跳转；块内一旦执行，就必须一路执行到最后一条。

那怎么切？靠识别leader（首领指令），规则也是三条，非常经典：

整个函数的第一条指令是 leader；
任何跳转指令的目标是 leader；
任何跳转指令之后的下一条指令是 leader。

找齐所有 leader 之后，一个基本块就是从某个 leader 开始，一直到下一个 leader 之前的全部指令（或者到函数结束）。这三条规则背后的道理其实很直白：跳转目标能被多条路径进入，天然是入口；跳转之后的下一条，说明上一条会打断顺序流，它自己就是新起点。

拿之前那个max函数，写成简化中间表示（三地址码）来看：

B1: t1 = a > b if t1 goto B2 else B3 B2: r = a goto B4 B3: r = b goto B4 B4: return r

对照规则看：第一条是 leader，所以 B1 从这里起；if的两个目标r=a和r=b都是 leader，分别起 B2、B3；if、goto之后的下一条也都是 leader，于是自然切出 B4。四条边分别是 B1→B2、B1→B3、B2→B4、B3→B4，一个分叉再汇合的菱形结构就出来了。

2.1 switch、goto 与 fallthrough 的连边陷阱

真正的代码里，跳转远不止if和while。switch语句会一次产生一堆边，每个case标签是一个目标；goto可以跳到离得很远的块，直接拉一条长边。这里最容易漏的，是switch的fallthrough：某个case块末尾没有break，控制流会自然落到下一个case块里，这必须补一条边。我第一版实现的时候就吃过这个亏，case之间全都当成独立分支，结果后面活跃变量分析在该变量"其实还活着"的地方判成死了，优化直接把值改没了。

goto还有个变种问题：向前跳（逆序）和向后跳（顺带构成循环）在连边时本质上一样，但向后跳会引入回边，影响后面循环识别，所以不能等到循环分析再处理，建图阶段就要如实连上。

2.2 一个可落地的建图流程

把上面这套整理成可执行的步骤，大致是：

遍历函数内所有指令，按三条 leader 规则标记 leader；
顺序扫描，把 leader 之间的指令归到同一个基本块；
对每个块的最后一条指令判断出口：若是条件跳转，连向目标块和顺序后继块；若是无条件跳转，只连目标块；若是返回/抛异常，不连（作为出口）；
处理形如switch的多目标跳转，逐个目标连边，注意 fallthrough；
建完后做一次反向可达遍历，从所有出口块倒推，标记"能到达出口"的块，剩下的就是初步的死代码候选。

第 3 步里"顺序后继"这个词要特别解释一下。它指的是：当跳转指令没有发生时，控制流会走到下一条指令所在的那个块。哪怕这条跳转是无条件的，它也可能有隐式的顺序后继——只不过那种情况下顺序后继不可达，连不连要看实现选的是"保守多连"还是"精确少连"。我的建议是建图阶段宁可保守多连，精确性留到后面的分析去修，因为漏连比多连更难排查。

提示：第 5 步的反向可达遍历，是我每次写完建图都要跑的验证。如果它标记出来的死代码明显不对，基本能确定是连边遗漏，而不是分析算法的问题。

3. 支配关系、支配树与支配边界：所有高效优化的地基

图建好了，接下来要研究的是图上的"路权"。支配关系（dominance）是控制流分析里最重要的结构性关系之一，定义是：节点 d 支配节点 n，当且仅当从入口到 n 的每一条路径都必须经过 d。也就是说，只要你想从函数入口走到 n，绕不开 d。

定义里有两个细节值得抠。第一，每个节点支配自己——这条通常作为约定写进算法，能让公式更整齐。第二，注意是"每一条路径"，这跟上一节讲的 CFG 是 "may" 世界形成对照：CFG 连边是"可能"，支配是"必然"，两者刚好互补。

支配关系为什么重要？因为它把图里"必然经过"的骨架抽了出来，让很多优化能在有保证的前提下动手。比如某节点 d 支配 n，那 d 里算出来的常量、确立的 invariants，到 n 处一定还成立。没有支配关系，你就不敢做任何跨块的假设。

3.1 直接支配者与支配树的迭代求解

在所有支配 n 的节点里，离 n 最近的那个叫直接支配者（immediate dominator，idom）。把每个节点连到它的 idom，就得到一棵支配树。这棵树很有用：它把"必然经过"关系压缩成了路径关系，查支配、做 SSA 都在这上面走。

求解 idom 的朴素迭代算法思路如下，输入是已经建好的 CFG：

Dom(entry) = {entry} 对除 entry 外的每个节点 n：Dom(n) = 全集（所有节点） 重复： for 每个节点 n （除 entry）: newDom = {n} ∪ ( ∩ Dom(p) ) // p 遍历 n 的所有前驱 if newDom != Dom(n): Dom(n) = newDom changed = true 直到 changed == false

这段代码的直觉是：一个节点被哪些点支配，取决于它所有前驱被哪些点支配——所有前驱都支配的点，才可能支配它，所以取交集。反复迭代直到不再变化（也就是不动点）。落地的优化点是：把节点按逆后序遍历，迭代次数会少很多；节点规模大时，可以换成 Lengauer-Tarjan 那套近似线性的算法。

3.2 支配边界：SSA 里插 φ 函数的坐标

比支配树再抽象一层的，是支配边界（dominance frontier，DF）。它的定义稍微绕：节点 n 在 d 的支配边界里，当且仅当 d 支配 n 的某个前驱，但 d不（严格）支配 n 本身。用大白话说，DF(d) 就是 d 的"支配力刚刚失效"的那一圈节点。

这个定义看着别扭，但它恰好就是 SSA 里 φ 函数该出现的位置。想一下：某变量在 d 这个块里有个定义，它要传播到 n；如果 d 支配 n，那 n 处用到的就是这个定义，不需要 φ；如果 d 支配 n 的某条入边的来源，却支配不了 n，说明有另一条路径带着别的定义也到了 n，两条流汇合，必须在 n 插 φ。所以标准做法是：对每个变量，从它的定义块出发，求 DF，在 DF 节点插 φ，重复这个闭包直到不再新增——也就是著名的"迭代支配边界"。

概念	一句话定义	典型用途
支配	入口到 n 的每条路径都过 d	跨块不变式、常量传播前提
直接支配者	支配 n 的节点里离 n 最近的	构建支配树
支配树	每个节点连 idom 形成的树	SSA、查询支配关系
支配边界	支配力刚好失效的一圈节点	SSA 插入 φ 函数

我个人的经验是，支配树和支配边界这两块，光看定义很容易"以为懂了"，真正自己从零手写一遍才能踏实。写完之后拿几个带嵌套分支、带循环的小例子跑一跑，对着输出人工验几个节点，比看十遍书都管用。

4. 数据流方程的构建与不动点求解：从"能走到"到"值是什么"

有了 CFG，很多问题就能转化成"沿图传播信息"。这类问题的统一处理方式叫数据流分析，核心是给每个基本块定义一组方程，然后迭代到不动点。这里的关键是理解每个分析"朝哪个方向传"以及"汇合时怎么合并"。

拿最经典的两个分析来看。到达定值（reaching definitions）问的是：到程序某一点，哪些定义可能还没被覆盖，能到达这里。它是前向分析，信息沿控制流方向从入口往出口传。活跃变量（live variables）问的是：某点之后某变量的值还会不会被用到。它是后向分析，信息从出口往入口传。

4.1 到达定值的方程与求解释义

对每个基本块 B，定义两个集合：

GEN[B]：在 B 里生成、并且到 B 结尾仍然有效的定义；
KILL[B]：被 B 里新定义"杀掉"的那些旧定义。

然后方程是：

OUT[B] = GEN[B] ∪ ( IN[B] − KILL[B] ) IN[B] = ∪ OUT[P] // P 遍历 B 的所有前驱

这里有个必须讲清楚的选择：为什么 IN 是对所有前驱取并集？因为到达定值问的是"这个定义可能到达吗"，只要存在一条路径把它带过来，答案就是"可能"。这是典型的 may 分析，所以用并集。你要是把它写成交集，语义就全错了。

迭代过程就是反复代入方程：从IN = 空集、OUT = GEN起步，一轮轮算 IN、OUT，直到整张图不再变化。因为可能的定义集合是有限的，而方程又是单调的（每次只会让集合变大，不会变小），所以一定能在有限步内收敛。这个"集合有限 + 单调收敛"是几乎所有数据流分析能跑通的底层保证，面试也爱问。

4.2 活跃变量与"must/may"的对称性

活跃变量反过来：对块 B，USE[B]是在 B 里被用到、且在 B 内先于任何重定义出现的变量；DEF[B]是在 B 里被定义、且定义先于使用的变量。方程是：

IN[B] = USE[B] ∪ ( OUT[B] − DEF[B] ) OUT[B] = ∪ IN[S] // S 遍历 B 的所有后继

到了这里你会发现一个很有味道的对称：前向分析用前驱的 OUT 推自己的 IN，后向分析用后继的 IN 推自己的 OUT。写实现的时候，前向分析按逆后序迭代更省轮数，后向分析按后序迭代更省轮数。

还有一个常被搞混的点是 must 和 may。可用表达式（available expressions）是 must 分析，说的是"表达式在所有路径上都已算过且没被改写"，所以它汇合时用交集，同时它的方向是前向的。may 用并集，must 用交集，这条口诀我在很多场合都验证过。搞反一次，优化结果就会朝着危险的方向偏。

提示：写分析之前先在纸上把方向、GEN/KILL/USE/DEF 的语义、还是 may/must、汇合用并集还是交集，这几项列清楚。这几项一旦定错，后面调多少轮都是错的。

5. 回边、自然循环和循环不变量外提

前四节把图和传播的框架搭好了，但图里最肥的一块还没动——循环。绝大多数程序的热点都在循环上，优化收益也集中在这里，所以循环识别是控制流分析必须拿下的一环。

5.1 回边与自然循环的判定

循环识别的一个优雅做法，是从回边（back edge）入手。一条边 n→h 是回边，当且仅当h 支配 n。直觉上很好理解：如果你从 n 有一条边回到 h，而 h 又支配 n（想到 n 必须经过 h），那就说明这条边把控制流"卷"回了前上方，是循环的闭合边。h 叫循环头（header），它是循环的唯一入口。

找到回边之后，自然循环的集合就是：循环头 h，加上所有能到达回边尾部 n、但路径上不经过 h 的节点。注意"路径上不经过 h"这个限定，它保证循环不被外部的旁路干扰，也保证了自然循环有唯一入口——这正是后面优化敢动手的前提。

5.2 循环不变量外提为什么依赖控制流分析

循环里最值钱的一类机会，是循环不变量外提（loop-invariant code motion）：某条计算在循环里每次结果都一样，就可以搬到循环前面只算一次。但这里有个反直觉的坑：当循环存在多条出口、而且这个计算还可能在执行过程中抛异常时，直接外提会改变异常发生的时机——本来可能循环跑几次才抛，外提后一次都不跑就抛了，语义就变了。所以严格的外提，必须先分析循环的出口结构、计算的安全性（是否可能触发副作用），确认无副作用再搬。

这件事再次说明，控制流分析不是孤立的：循环识别给外提提供"循环范围"，支配关系给外提提供"搬到哪不会破坏语义"，两者缺一不可。我见过把公用子表达式随手提到循环外、结果把懒计算的异常提前触发的案例，根子就是没做异常边的控制流分析。

循环结构	特征	优化注意点
单入口单出口	结构清晰，头支配回边尾	大多数优化可放心做
多出口	有多个 break/异常退出	外提前确认无副作用
嵌套循环	循环体里套循环	逐层识别，注意内层优先
不可规约	无支配关系的回跳	优化能力受限，需保守处理

6. 从零跑通分析后，实测最容易踩的几个坑

算法原理都对了，不代表实现就能跑对。这一节把我实际做控制流分析时反复踩到的坑集中说一下，按排查链路讲，方便你对照复现。

6.1 异常边和 finally 块：漏一条边，结果全歪

有异常机制的代码，控制流的真实形态比语法结构复杂得多。任何一条可能抛异常的指令，都有一条隐式的边指向最近的异常处理块；try块里的控制流还可能先走finally再继续。这些边如果没连，CFG 就是残缺的，基于它的分析会把"其实能到达异常处理"的路径判成不可达。我遇到过最典型的症状是：资源释放的代码被判成死代码删掉，运行时泄漏。排查的切入点是先单独把异常边画出来，人眼对着try/catch/finally结构核一遍，再去看上层分析。

处理策略上，稳健的做法是保守多连：不确定有没有异常边，就先连上；等确认这条指令实际不会抛，再精确删除。多连的代价是精度下降，漏连的代价是正确性崩溃，两者完全不对等。

6.2 不动点迭代不收敛，多半是格定义错了

数据流分析按理说不该不收敛，只要格（lattice）的高度有限、传递函数单调就行。可一旦不收敛，几乎可以断定是下面两种情况之一。

第一种，并集/交集的语义搞反。前面说过，may 用并集、must 用交集。如果你把某个 must 分析写成并集，集合就永远在变大，越算越多，看起来像不收敛。第二种，方程里用了会自我放大的结构，比如把某集合同时放进 GEN 和它的目标里形成错误的依赖环。排查方式是打印每轮迭代的集合大小，正常应该是单调趋近一个上限，如果某块大小来回震荡或无限增长，回去看这块的 GEN/KILL 语义。

6.3 支配边界算错，φ 函数就乱插

支配边界错会导致 SSA 的 φ 函数插到错误的节点，或者在错误的节点缺失。一个特别隐蔽的错法是 DF 里把"d 支配自身"算进去了——严格定义里 d 是不支配它自己的边界节点的，如果实现里把"支配"和"严格支配"混用，DF 就会多出一堆节点，φ 也就多插了。多插 φ 通常不至于算错结果，只是效率差；但要命的是少插，那会让一个变量在两个定义汇合处只有一个来源，常量传播立刻给出错误结论。

定位这类问题时，我的办法是选一个只有两个分支汇合的最小例子，手工推导一遍 DF，再对实现的输出，一眼就能看出是保守多算还是漏算。

6.4 函数指针和间接跳转：只能保守处理

当调用是间接的、跳转是动态计算的（比如通过函数指针、跳转表），编译期往往无法精确知道目标是谁。这时候控制流分析必须给出一个保守但安全的近似。最粗的做法是：把所有可能被间接调用的函数当成候选目标，全部连边。精度会掉，但不会错。进阶做法是配合指针分析（points-to analysis），把候选集缩小到真正可能被指向的函数。

这里有个实践取舍：保守到什么程度，取决于下游分析的用途。如果只是做粗略的死代码消除，粗粒度保守就够了；如果是做需要高精度的常量传播，就得把指针分析一起做进来，否则永远是"宁滥勿缺"，误报下不来。