做静态分析或者编译器后端的人大概都遇到过这种场面一条自己觉得逻辑很清楚的检查规则丢到真实项目里一跑误报多到自己都不信或者写了一个本地小例子跑得飞起的优化 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的两个目标ra和rb都是 leader分别起 B2、B3if、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 dominatoridom。把每个节点连到它的 idom就得到一棵支配树。这棵树很有用它把必然经过关系压缩成了路径关系查支配、做 SSA 都在这上面走。求解 idom 的朴素迭代算法思路如下输入是已经建好的 CFGDom(entry) {entry} 对除 entry 外的每个节点 nDom(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 frontierDF。它的定义稍微绕节点 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的对称性活跃变量反过来对块 BUSE[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把候选集缩小到真正可能被指向的函数。这里有个实践取舍保守到什么程度取决于下游分析的用途。如果只是做粗略的死代码消除粗粒度保守就够了如果是做需要高精度的常量传播就得把指针分析一起做进来否则永远是宁滥勿缺误报下不来。提示整套控制流分析里能到达永远比精确到达更重要。任何拿不准的地方先保证 may 集合不漏再谈缩小范围。6.5 一个可复用的自检清单跑完一遍分析我一般会用下面几条快速自检基本能覆盖 80% 的低级错误入口块没有入边除非有递归或显式跳回出口块没有出边反向可达遍历能到达的块应该正好等于活的块集合支配关系满足自反每个节点支配自己和传递每个循环至少有一条回边且回边尾被对应循环头支配数据流迭代结果同一块重复计算应稳定不再变化。这套自检跑下来还稳稳当当我才会把分析结果喂给优化或者其他上层逻辑。控制流分析是那种看起来简单、做好了很难的东西它的质量不会直接显示在输出里而是悄悄体现在误报率、优化后的正确性、以及别人复现你方案时的顺利程度上。真正把这块抠清楚后面那些花哨的分析和优化才有底气往上搭。