你写下一行赋值之后再没读过那个变量编译器却一声不吭地把它删了你写了一个 if 分支两边算出来的其实是同一个常量它直接把分支拍平成一条直线你在循环里留了个累加器只在调试打印时用过发布构建里那几行代码连影子都没剩下。头一回见到这种场面的人会有一种被偷看草稿的感觉——它凭什么这么笃定凭的就是数据流分析Data Flow Analysis。这门技术做的事情说白了很朴素把程序画成一张有方向的图然后让某个事实沿着图上的边一路流下去遇到分岔就分开流遇到汇合就把几路信息合并起来一直流到再流也不产生新信息为止。流到最后编译器就知道了在你写下某一行的时候哪些变量的值是它已经确定的、哪些代码是永远走不到的、哪些变量在这一刻还活着、哪些值可能从哪几条路径过来。它能干的事情远超多数人的想象死代码消除、常量折叠与传播、公共子表达式消除、寄存器分配、未初始化变量检查、空指针告警、资源泄漏提示背后都是同一套骨架。适合读这篇的人有三类正在写编译器、DSL、字节码虚拟机或者静态检查工具的人写业务代码但被优化后行为和预期不一致坑过、想搞清楚原因的人以及想补上程序分析这块基础的人。下面我按自己踩过的顺序讲从它到底在算什么到手写一个能跑的分析器再到真实程序里那些教科书不会提的坑。1. 编译器敢动你代码的底气从哪来1.1 一次让我重新认识优化的调试经历早些年我给一个自研的脚本引擎写优化插件第一版只做了最朴素的常量折叠看到a 1 2就换成a 3。上线之后效果惨淡性能几乎没有变化。我不服气把一段典型的热点代码的中间表示打印出来逐行看发现问题根本不在能不能算而在算了之后敢不敢用。那段代码大概是这样一个循环里反复读某个全局配置项配置项在循环外赋值循环内没有任何写入。人一眼就能看出每次读到的都是同一个值可以把它提到循环外只读一次。但我的优化器不敢——因为它只能看到相邻的两三条语句它不知道中间隔着的那些分支里有没有偷偷改过这个配置项。要回答这个位置读到的值可能来自哪几次赋值就已经不是局部窥孔能解决的事了必须把整张控制流图拉出来算。这就是分水岭。局部优化看语句全局优化看路径。而从看语句跨到看路径中间那道桥就是数据流分析。后来我把分析框架补上同一份代码的优化收益翻了将近一倍而且很多原来不敢做的变换忽然变得合法了——不是因为我变聪明了是因为我终于有了证据。1.2 把程序变成一张图控制流图与传递函数数据流分析的第一步是把线性的代码变成图。做法是把连续执行、中间没有跳转目标也没有跳转指令的那些语句打包成一个基本块Basic Block块内顺序执行、一进到底然后按照跳转关系在块之间连有向边得到的就是控制流图Control Flow GraphCFG。入口块和出口块是人为规定的两个虚拟结点方便统一起见。图建好之后每个基本块就被抽象成一个传递函数给它一组输入事实它吐出经过这个块之后的事实。比如到达定值分析里一个块的作用就是产生若干新的定值并杀掉被这些定值覆盖掉的旧定值。这个抽象非常关键——它把块里到底有多少条语句、语句长什么样这些细节统统折叠掉了只留下这个块对事实做了什么。然后是汇合点。一个块如果有两个前驱从两条路径流过来的事实要怎么合并答案取决于你想证明什么。想证明某个东西可能存在就取并集只要有一条路径带来它就认想证明某个东西一定成立就取交集所有路径都得同意才行。前者叫 may 分析后者叫 must 分析。这个区分不是学术洁癖它直接决定你的分析会不会给出错误结论。我用一个类比来解释这套流程想象你在城市地图上倒墨水墨水源头上游沿着所有可能的水路往下走每到一个汇合口几股水混在一起继续往下。数据流分析算的就是最后每条水渠里有没有墨水、墨水可能来自哪几个源头。区别只在于现实里的水只能往下流一次而程序里有环——循环会让水反复绕回来所以必须迭代到稳定为止。1.3 方向与合并方式四个象限装下大部分分析几乎所有经典数据流分析都能塞进方向 × 合并方式这个二维表里。方向分前向顺着执行顺序推和后向逆着执行顺序推合并方式分并集和交集。这张表我建议直接背下来遇到新问题先定位它在哪个象限思路立刻就清楚了。分析名称方向合并性质典型用途到达定值前向并集may常量传播、死代码、未初始化检测可用表达式前向交集must公共子表达式消除活跃变量后向并集may寄存器分配、死赋值消除必达定值后向交集must冗余赋值检测、初始化验证为什么活跃变量是后向的因为这个变量后面还有没有人用这个问题答案在语句的下游而不是上游。你站在第 10 行问x 还活着吗得看第 11 行往后有没有读它这就天然是逆流而上。而到达定值问的是我这儿拿到的值可能是谁给的答案在上游所以是前向。方向搞反是初学者最常见的错误之一写出来的分析能跑、能收敛但结果全错还特别难查。2. 到达定值把这个值可能从哪来算清楚2.1 定值、gen 与 kill一条语句对世界做了什么定值definition就是一次赋值通常记作d1: x ...。给程序里每一条赋值语句编个号是为了后面能在集合里直接放这些编号。到达定值分析要回答的问题是程序执行到某个位置时哪些定值的结果可能还没被覆盖、仍然有效。一条语句对事实的影响只有两种产生gen一个新的定值杀掉kill所有对同一个变量其他定值。比如x 1这一句产生d1 这个定值杀掉所有其他给 x 赋值的定值。注意 kill 是全局视角的——你得知道整个程序里有哪些语句给 x 赋过值才能把它们全部杀干净。这是新手最容易翻车的地方只在当前函数里扫一遍、或者只在当前基本块里扫一遍kill 集合算漏了后面所有结果都是错的而且错得很隐蔽。基本块级别的 gen 和 kill 是块内所有语句的累积效果但有个细节必须注意块内的 kill 不能杀掉块内自己 gen 出来的定值。也就是说一个块里先写x1再写x2那么出块时块内第一条赋值产生的定值已经被第二条杀掉了不应该出现在 GEN 里。标准做法是先顺着块内语句累积 gen 集合遇到新的定值就把同变量的旧定值从 gen 里移除最后再用全局的定值表算出完整的 KILL。2.2 一个能手工算完的例子加一张迭代表概念讲再多不如算一遍。拿下面这段四块的程序B1: d1: x 1 d2: y 2 goto B2 B2: d3: if (x 0) goto B3 else B4 B3: d4: y x 1 goto B4 B4: d6: z y先算每个块的 GEN 和 KILL。全局看x 只在 d1 被赋值y 在 d2 和 d4 被赋值z 只在 d6 被赋值。B1GEN {d1, d2}KILL {d4}因为 d4 也写 y进了 B1 之后原来那份 y 就废了B2GEN {}KILL {}B3GEN {d4}KILL {d2}B4GEN {d6}KILL {}z 没有别的定值方程是标准的两个OUT[B] GEN[B] ∪ (IN[B] − KILL[B])IN[B] ∪ OUT[前驱]。入口块的 IN 是空集。手算迭代过程如下轮次IN[B1]OUT[B1]IN[B2]OUT[B2]IN[B3]OUT[B3]IN[B4]OUT[B4]初始{}{}{}{}{}{}{}{}1{}{d1,d2}{d1,d2}{d1,d2}{d1,d2}{d1,d4}{d1,d2}{d1,d2,d6}2{}{d1,d2}{d1,d2}{d1,d2}{d1,d2}{d1,d4}{d1,d2,d4}{d1,d2,d4,d6}3无变化无变化无变化无变化无变化无变化无变化无变化第三轮全部不变收敛。最终 B4 的 IN 是 {d1, d2, d4}其中关于 y 的定值有两个d2 和 d4。这就是y 到达 B4 时可能来自两条路径的严谨表述。这个结果怎么用z y这一句如果编译器看到 y 的到达定值集合里同时有常量 2和表达式 x1它没法把 z 折叠成常量只能放弃。但如果 B3 里写的是y 3那么到达 B4 的 y 的定值全是常量编译器就能确定 z 一定等于某个值——当然前提是两条路径给的值相同否则还得做格上的合并。而如果某个变量的到达定值集合是空集说明走到这里之前它压根没被赋过值这就是经典的使用未初始化变量检测很多静态检查工具的核心逻辑就是这么几行。2.3 为什么这里必须用并集may 分析的保守性有人会问B4 的 IN 里把两条路径的定值都并进来是不是太贪心了真实的执行只会走其中一条另一条根本不存在。答案是编译器不知道会走哪条所以只能保守。这种保守不是缺陷而是正确性的来源。数据流分析有两条铁律宁可多报不可漏报针对 may 分析宁可少优化不可优化错。如果 B4 的 IN 里只有 d4 没有 d2编译器可能得出y 一定等于 x1的结论然后做常量传播一旦真的走了 B2→B4 这条路径程序行为就被改坏了。这种 bug 是最难查的一类——源码看起来完全正常只有特定输入下出错。所以任何一次因为分析结果而做的变换都必须能证明在分析给出的所有可能情况里这个变换都不改变语义。顺带说个实操经验写分析器的时候我习惯先用一个最保守的版本跑通比如所有集合都填全集确认框架没问题再逐步收紧。上来就追求精确往往会分不清是框架错了还是精度策略错了。3. 活跃变量分析变量什么时候算活着3.1 反过来推USE 与 DEF活跃变量分析问的是一个完全不同的问题在程序点 p 之后变量 v 的值还会不会被读到如果会v 在 p 点活跃如果不会v 就是死的它现在占着的寄存器、栈槽、甚至那条赋值语句本身都可以扔掉。这个分析是后向的。每个块有两个集合USE 表示块内先被读、且在读之前没被本块写过的变量DEF 表示块内被写过的变量。方程写起来很对称IN[B] USE[B] ∪ (OUT[B] − DEF[B])OUT[B] ∪ IN[后继块]出口块的 OUT 是空集程序结束后没有变量还有用。注意 USE 的定义里那个读之前没被写过很关键它保证了块内先写后读的情况不会被误算成用了外部传进来的值。拿上一节的同一张图算一遍活跃变量。变量层面B1 写 x、y没读B2 读 xB3 读 x、写 yB4 读 y、写 z。B1USE {}DEF {x, y}B2USE {x}DEF {}B3USE {x}DEF {y}B4USE {y}DEF {z}后向推B4 的 OUT 是 {}IN[B4] {y}。B3 的 OUT IN[B4] {y}IN[B3] {x} ∪ ({y} − {y}) {x}。B2 的 OUT IN[B3] ∪ IN[B4] {x, y}IN[B2] {x} ∪ ({x,y} − {}) {x, y}。B1 的 OUT IN[B2] {x, y}IN[B1] {} ∪ ({x,y} − {x,y}) {}。结果里有一个特别值得玩味的点IN[B3] 里没有 y。这意味着从 B1/B2 流进来的那份 y在 B3 入口就已经死了——因为 B3 马上要重写它旧值再也没人用。而 B4 用到的 y是 B3 里新写的那一份。这个区分在寄存器分配阶段非常值钱B3 里新写的 y 可以直接覆盖旧 y 占的那个寄存器不需要另开一个。3.2 冲突图把活跃信息变成寄存器分配方案活跃变量分析最经典的用途是构造冲突图Interference Graph。规则很简单如果两个变量在同一个程序点同时活跃就在它们之间连一条边表示这俩不能共用同一个寄存器。图建好之后寄存器分配就变成了图着色问题——给每个结点涂一种颜色相邻结点颜色不同颜色数量就是可用寄存器数。实际工程里没这么理想化。图着色是 NP 完全的真实规模下必须用启发式先按度数排序、优先把邻居多的结点溢出到栈上涂完色再做溢出代码的插入。但不管后面多复杂输入永远是活跃变量分析算出来的那几个集合。我见过有人跳过这一步直接按变量声明顺序分配寄存器跑小例子没问题一上真实代码就各种性能塌方——因为活跃区间重叠的变量被迫反复换出换入。还有一个容易忽略的细节活跃变量分析的结果对死赋值极其敏感。x ...之后 x 再也没被读过这条赋值就是死的可以整条删掉连带着右侧表达式的计算也可以删前提是右侧没有副作用函数调用就不能随便删。这条规则在清理被宏展开、模板实例化搞出一堆无用临时变量的代码时特别管用。3.3 may 与 must 在活跃性上的分歧点活跃变量本身是 may 分析只要有一条后继路径上会用到就算活跃。这个选择同样是出于保守。假如你按 must 来算所有路径都必须用到才算活那么一条只在某个分支里用到的变量会被判定为死寄存器被回收——那个分支一旦执行就读到了被覆盖的值。但反过来也有需要 must 信息的场景比如这个变量在这条路径上一定已经被初始化了这就要用必达定值也叫向上暴露的使用来算合并方式改成交集。同一个程序、同一张图换个方向、换个合并方式得到的就是完全不同的问题。这也是我说先定位象限的原因——很多看起来全新的分析需求其实只是把老方程的箭头反过来写。4. 格、单调性与不动点迭代为什么一定会停4.1 把分析结果放到一个格上前面所有的例子分析结果都是某个集合。把所有可能的集合按包含关系排一排就得到一个格Lattice最下面是空集最上面是全集任意两个集合都有最小上界并集和最大下界交集。前向的 may 分析从空集出发往上爬每一步都在往集合里加东西加到不能再加就停。这个抽象的价值在于它把具体算什么和怎么算分开了。不管你是算到达定值、常量传播还是类型推断只要能证明结果集构成一个有限高度的格传递函数是单调的收敛性就自动成立不用每次重新论证。常量传播的格更直观一些每个变量对应一个元素未初始化底、某个具体常量、或者不确定顶。两条路径汇合时取最小上界2 ⊔ 2 22 ⊔ 3 不确定不确定 ⊔ 任何值 不确定。所以一个变量只要在某条路径上被赋了不同的值立刻就退化成不确定这正好对应了前面说的保守性。4.2 单调性给的是不会退步的保证单调性说的是输入变大输出不会变小。形式化一点如果a ⊑ b那么f(a) ⊑ f(b)。为什么这个性质这么重要因为迭代过程中我们是一轮一轮把结果往上加的如果传递函数不单调某一轮加进去的信息可能导致下一轮结果反而变小那就可能出现加了又减、减了又加的震荡永远停不下来。我给这个性质想了个生活化的解释把传递函数想成一个诚实的会计你交给他更多的单据他只会算出不少于之前的账不会因为单据变多反而算出更少的钱。只要会计是诚实的你的账本每一轮只会单调增长而账本可能的取值是有限的格的高度有限所以最多长有限次就到头了。反过来说如果格的高度不是有限的——比如结果里可以放任意精度的整数区间——那即使单调也不保证终止得靠加宽widening之类的技巧强行截断。这一点在自己设计分析的时候必须提前想清楚别等死循环了才发现值域是无限的。4.3 worklist把每轮全扫变成只算受影响的块最笨的迭代方式是每一轮把所有基本块都重算一遍直到某一轮没有任何变化。这个做法正确、好写但浪费改了一个块的结果它的前驱/后继没变没必要重算。worklist 算法解决的就是这个维护一个待处理块的队列初始放进所有块每次取出一个块重算它的 IN/OUT如果结果变了就把它受影响的邻居重新入队前向分析放后继后向分析放前驱。加上已在队列里就不重复加的判断能砍掉大量重复计算。实测下来worklist 在真实程序上的加速比非常可观尤其在深度嵌套的循环结构里。不过我踩过一个坑队列的数据结构选错了。早期用普通列表加in判断块数量一多就退化成平方级换成双端队列加一个布尔标记数组之后速度立刻正常。还有个细节是遍历顺序——前向分析时按逆后序遍历RPO入队通常比随机顺序收敛得快得多因为信息能更快地顺着路径传下去而不是来回震荡。5. 动手实现一个能跑通的到达定值分析器5.1 数据结构指令、基本块、控制流图我倾向于用最朴素的三个类把骨架搭起来先跑通再谈优化。指令用一个元组表示(op, args, dest)比如(assign, [1], x)基本块持有指令列表、前驱列表和后继列表CFG 持有块的有序列表和入口、出口索引。关键设计决定给每条赋值指令分配全局唯一的编号这个编号就是定值分析里集合的元素。用编号而不是用变量名是因为同一个变量会对应多个定值必须能区分。至于集合的存储原型阶段直接用set就好写起来最快等要上规模了再换位向量。5.2 从线性代码到 CFG划分基本块的三条规则划分规则很固定抓住leader块首这个概念就够了第一条指令是 leader任何跳转指令的目标是 leader任何跳转指令的下一条是 leader。从每个 leader 开始一直到下一个 leader 之前就是一块。然后连边如果块的最后一条指令是无条件跳转连到目标块如果是条件跳转连到目标块和顺序的下一块如果既不是跳转也不是返回就连到顺序的下一块。这一步看着简单坑却在细节上条件跳转的两个后继要都连上漏一个活跃变量分析立刻出错返回指令没有后继循环回边不要漏while循环的块会有一条边指回条件判断块很多手写原型就在这里丢了回边导致循环内的信息传不回去。建议在划分完之后先做一次连通性检查从入口块做一次深度优先遍历把走不到的块标出来如果发现大半个程序都走不到八成是回边丢了。5.3 gen/kill 计算与 worklist 主循环下面这段是核心语言用的是 Python思路平移到任何语言都一样def compute_gen_kill(blocks): # 全局定义表变量 - 所有定义它的指令编号 defs_of {} for b in blocks: for idx, (op, args, dest) in enumerate(b.instrs): if dest is not None: defs_of.setdefault(dest, set()).add(b.def_id(idx)) gen, kill {}, {} for b in blocks: g set() for idx, (op, args, dest) in enumerate(b.instrs): if dest is None: continue did b.def_id(idx) g.add(did) # 块内后来的定义会杀掉块内先前同变量的定义 for other in list(g): if other ! did and b.dest_of(other) dest: g.discard(other) killed set() for d in g: killed | defs_of[b.dest_of(d)] kill[b.id] killed - g gen[b.id] g return gen, kill def solve_reaching_defs(blocks, entry, gen, kill): IN {b.id: set() for b in blocks} OUT {b.id: set() for b in blocks} work deque(b.id for b in blocks) in_queue {b.id: True for b in blocks} while work: bid work.popleft() in_queue[bid] False b blocks[bid] new_in set() for p in b.preds: new_in | OUT[p] new_out gen[bid] | (new_in - kill[bid]) if new_in ! IN[bid] or new_out ! OUT[bid]: IN[bid], OUT[bid] new_in, new_out for s in b.succs: # 前向分析通知后继 if not in_queue[s]: in_queue[s] True work.append(s) return IN, OUT有几个地方值得单独说。第一kill集合必须用全局定义表算绝不能只用块内的信息这是我在第二节点名强调过的那件事。第二块内 gen 的修正要在遍历块内指令的循环里做边加边清。第三主循环里判定有没有变化要同时比较 IN 和 OUT只比一个有时候会漏掉传播。5.4 验证先看不动点再看具体案子跑完之后怎么确认结果对我一般做三重验证。第一重不动点自检再跑一轮主循环如果还有块的 OUT 发生变化说明收敛逻辑写错了。这个检查便宜且极其有效。第二重构造已知答案的小用例就像本文第二节那张手工表把分析器输出和手算结果对齐。第三重看具体某条路径随便挑一个分支汇合点把 IN 集合里的定值和源码对照逐个问这个定值真的可能走到这儿吗一般挑三五个就能发现 kill 集合算漏的问题。调通之后第一件事别急着接优化先写个可视化把每个块的 IN/OUT 打印成表格或者画成文本图。我后面几乎每次遇到优化结果不对的问题第一步都是把这个 dump 打开看十次里有八次一眼就能定位。6. 从玩具到生产真实程序里的五个坑6.1 一旦出现取地址和别名就该收手了玩具程序里变量是互相独立的真实程序里到处都是别名两个不同名字的变量指向同一块内存通过一个指针改数据会影响另一个名字读到的值。只要程序里出现了取地址操作或者把对象传出当前函数保守的做法就是把那一刻涉及的所有变量全部标记为可能被任意修改也就是把它们的定值全部杀掉。这当然会损失大量优化机会但这是唯一安全的做法。我见过有人试图做聪明的别名分析按变量名首字母分组做近似结果在特定输入下产生了极难复现的错误——两个变量被误判为互不相关一个优化把一个还没被读到的值覆盖掉了。这类 bug 出在优化器里你就算抓到了现场也很难相信是编译器干的。正确的期待是分析精度决定优化空间但正确性优先级永远更高。一个保守但正确的优化器比一个激进但偶尔出错的优化器有价值一万倍。前者只是慢一点后者会让所有人失去信心。6.2 函数调用是一堵墙跨过去要付代价块内分析好做一旦遇到函数调用就麻烦被调函数改了哪些全局变量传进去的那个对象它会不会存起来改返回值是不是恒定没有过程间的信息调用点只能当成什么都可能发生把这些变量的定值全部清空。真要做过程间分析代价是分析规模从一个函数变成整个调用图还得分清上下文——同一个函数被两处调用参数不同分析结论可能完全不同按调用点做上下文敏感又会带来组合爆炸。我的建议是分阶段先把函数内分析做扎实调用点一律保守处理等整体收益瓶颈确实卡在跨函数上了再针对高频的小函数比如几百个纯计算型的辅助函数做内联内联之后它们自然就变成函数内分析了比直接上上下文敏感便宜得多。6.3 不可达块、死循环和自环带来的麻烦图一旦有环迭代次数就会明显增加如果有不可达的块那些块的分析结果会一直是初始值看起来很怪但无害。真正的问题出在死循环块上它的 IN 集合来自自己形成自环几轮之后会增长到一个不动点这个不动点可能包含一堆本不该存在的定值。如果后面基于这些信息做优化可能把循环体里的某些代码判成永远用不到而删掉——只要那个循环真的会退出行为就变了。我的处理方式是在做优化之前先跑一遍可达性分析把不可达块整块剔除死循环块则在控制流图层面上特殊标记凡是涉及它的分析结果一律按最保守处理不承接任何优化。6.4 集合实现与遍历顺序性能坑比算法坑更多原型用普通集合跑几百条指令没什么感觉一旦指令数上万集合的创建和合并就会成为热点。换位向量是标准解法每个块一个定长整数数组第 i 位表示第 i 号定值是否存在并集变成按位或差集变成与上取反再与。这个改造通常能把分析耗时压下去一个数量级代码还更短。遍历顺序的影响也很大。前向分析用逆后序入队信息能顺着执行流一路传下去往往两三趟就收敛用随机顺序可能要来回扫十几趟。后向分析则反过来用后序。这个结论我在不同规模的项目上验证过很多次几乎每次都能拿到肉眼可见的加速而且改动量只有几行。6.5 别把分析结果当真理它只是一份可信的近似最后一点也是我认为最重要的心态问题。数据流分析的输出永远是对程序行为的保守近似不是精确刻画。它说这个定值可能到达这里实际上可能到达也可能不到达它说这个变量在这里活跃实际执行路径上可能根本不读它。所有基于它的判断都必须保证在这个近似涵盖的所有真实情况里结论都成立。这也解释了为什么静态检查工具总会误报。一个未初始化变量的检查器用的是到达定值分析只要某条理论上可达、实际永远不会走的分支上存在一条未初始化的路径它就得报警。想减少误报正确方向是提升分析精度加路径敏感、加常量传播、加不可达分支剪枝而不是放宽分析的正确性要求——后者会让你漏掉真 bug而漏报比误报危险得多。我现在写任何一个要依赖数据流信息的优化 pass都会在注释里写清楚三件事用的是哪种分析、是 may 还是 must、在哪些情况下主动降级到保守。这三行注释在半年后回看代码时能省下大量重新推理的时间。另外分享一个小习惯在分析器的收敛循环外面套一个计数器打印每个程序平均迭代了几轮。一旦某次改动让这个数字突然翻倍通常意味着某个块的传递函数写错了或者回边连错了——这比等优化结果出问题再回头查要快得多。
你写下一行赋值之后再没读过那个变量编译器却一声不吭地把它删了你写了一个 if 分支两边算出来的其实是同一个常量它直接把分支拍平成一条直线你在循环里留了个累加器只在调试打印时用过发布构建里那几行代码连影子都没剩下。头一回见到这种场面的人会有一种被偷看草稿的感觉——它凭什么这么笃定凭的就是数据流分析Data Flow Analysis。这门技术做的事情说白了很朴素把程序画成一张有方向的图然后让某个事实沿着图上的边一路流下去遇到分岔就分开流遇到汇合就把几路信息合并起来一直流到再流也不产生新信息为止。流到最后编译器就知道了在你写下某一行的时候哪些变量的值是它已经确定的、哪些代码是永远走不到的、哪些变量在这一刻还活着、哪些值可能从哪几条路径过来。它能干的事情远超多数人的想象死代码消除、常量折叠与传播、公共子表达式消除、寄存器分配、未初始化变量检查、空指针告警、资源泄漏提示背后都是同一套骨架。适合读这篇的人有三类正在写编译器、DSL、字节码虚拟机或者静态检查工具的人写业务代码但被优化后行为和预期不一致坑过、想搞清楚原因的人以及想补上程序分析这块基础的人。下面我按自己踩过的顺序讲从它到底在算什么到手写一个能跑的分析器再到真实程序里那些教科书不会提的坑。1. 编译器敢动你代码的底气从哪来1.1 一次让我重新认识优化的调试经历早些年我给一个自研的脚本引擎写优化插件第一版只做了最朴素的常量折叠看到a 1 2就换成a 3。上线之后效果惨淡性能几乎没有变化。我不服气把一段典型的热点代码的中间表示打印出来逐行看发现问题根本不在能不能算而在算了之后敢不敢用。那段代码大概是这样一个循环里反复读某个全局配置项配置项在循环外赋值循环内没有任何写入。人一眼就能看出每次读到的都是同一个值可以把它提到循环外只读一次。但我的优化器不敢——因为它只能看到相邻的两三条语句它不知道中间隔着的那些分支里有没有偷偷改过这个配置项。要回答这个位置读到的值可能来自哪几次赋值就已经不是局部窥孔能解决的事了必须把整张控制流图拉出来算。这就是分水岭。局部优化看语句全局优化看路径。而从看语句跨到看路径中间那道桥就是数据流分析。后来我把分析框架补上同一份代码的优化收益翻了将近一倍而且很多原来不敢做的变换忽然变得合法了——不是因为我变聪明了是因为我终于有了证据。1.2 把程序变成一张图控制流图与传递函数数据流分析的第一步是把线性的代码变成图。做法是把连续执行、中间没有跳转目标也没有跳转指令的那些语句打包成一个基本块Basic Block块内顺序执行、一进到底然后按照跳转关系在块之间连有向边得到的就是控制流图Control Flow GraphCFG。入口块和出口块是人为规定的两个虚拟结点方便统一起见。图建好之后每个基本块就被抽象成一个传递函数给它一组输入事实它吐出经过这个块之后的事实。比如到达定值分析里一个块的作用就是产生若干新的定值并杀掉被这些定值覆盖掉的旧定值。这个抽象非常关键——它把块里到底有多少条语句、语句长什么样这些细节统统折叠掉了只留下这个块对事实做了什么。然后是汇合点。一个块如果有两个前驱从两条路径流过来的事实要怎么合并答案取决于你想证明什么。想证明某个东西可能存在就取并集只要有一条路径带来它就认想证明某个东西一定成立就取交集所有路径都得同意才行。前者叫 may 分析后者叫 must 分析。这个区分不是学术洁癖它直接决定你的分析会不会给出错误结论。我用一个类比来解释这套流程想象你在城市地图上倒墨水墨水源头上游沿着所有可能的水路往下走每到一个汇合口几股水混在一起继续往下。数据流分析算的就是最后每条水渠里有没有墨水、墨水可能来自哪几个源头。区别只在于现实里的水只能往下流一次而程序里有环——循环会让水反复绕回来所以必须迭代到稳定为止。1.3 方向与合并方式四个象限装下大部分分析几乎所有经典数据流分析都能塞进方向 × 合并方式这个二维表里。方向分前向顺着执行顺序推和后向逆着执行顺序推合并方式分并集和交集。这张表我建议直接背下来遇到新问题先定位它在哪个象限思路立刻就清楚了。分析名称方向合并性质典型用途到达定值前向并集may常量传播、死代码、未初始化检测可用表达式前向交集must公共子表达式消除活跃变量后向并集may寄存器分配、死赋值消除必达定值后向交集must冗余赋值检测、初始化验证为什么活跃变量是后向的因为这个变量后面还有没有人用这个问题答案在语句的下游而不是上游。你站在第 10 行问x 还活着吗得看第 11 行往后有没有读它这就天然是逆流而上。而到达定值问的是我这儿拿到的值可能是谁给的答案在上游所以是前向。方向搞反是初学者最常见的错误之一写出来的分析能跑、能收敛但结果全错还特别难查。2. 到达定值把这个值可能从哪来算清楚2.1 定值、gen 与 kill一条语句对世界做了什么定值definition就是一次赋值通常记作d1: x ...。给程序里每一条赋值语句编个号是为了后面能在集合里直接放这些编号。到达定值分析要回答的问题是程序执行到某个位置时哪些定值的结果可能还没被覆盖、仍然有效。一条语句对事实的影响只有两种产生gen一个新的定值杀掉kill所有对同一个变量其他定值。比如x 1这一句产生d1 这个定值杀掉所有其他给 x 赋值的定值。注意 kill 是全局视角的——你得知道整个程序里有哪些语句给 x 赋过值才能把它们全部杀干净。这是新手最容易翻车的地方只在当前函数里扫一遍、或者只在当前基本块里扫一遍kill 集合算漏了后面所有结果都是错的而且错得很隐蔽。基本块级别的 gen 和 kill 是块内所有语句的累积效果但有个细节必须注意块内的 kill 不能杀掉块内自己 gen 出来的定值。也就是说一个块里先写x1再写x2那么出块时块内第一条赋值产生的定值已经被第二条杀掉了不应该出现在 GEN 里。标准做法是先顺着块内语句累积 gen 集合遇到新的定值就把同变量的旧定值从 gen 里移除最后再用全局的定值表算出完整的 KILL。2.2 一个能手工算完的例子加一张迭代表概念讲再多不如算一遍。拿下面这段四块的程序B1: d1: x 1 d2: y 2 goto B2 B2: d3: if (x 0) goto B3 else B4 B3: d4: y x 1 goto B4 B4: d6: z y先算每个块的 GEN 和 KILL。全局看x 只在 d1 被赋值y 在 d2 和 d4 被赋值z 只在 d6 被赋值。B1GEN {d1, d2}KILL {d4}因为 d4 也写 y进了 B1 之后原来那份 y 就废了B2GEN {}KILL {}B3GEN {d4}KILL {d2}B4GEN {d6}KILL {}z 没有别的定值方程是标准的两个OUT[B] GEN[B] ∪ (IN[B] − KILL[B])IN[B] ∪ OUT[前驱]。入口块的 IN 是空集。手算迭代过程如下轮次IN[B1]OUT[B1]IN[B2]OUT[B2]IN[B3]OUT[B3]IN[B4]OUT[B4]初始{}{}{}{}{}{}{}{}1{}{d1,d2}{d1,d2}{d1,d2}{d1,d2}{d1,d4}{d1,d2}{d1,d2,d6}2{}{d1,d2}{d1,d2}{d1,d2}{d1,d2}{d1,d4}{d1,d2,d4}{d1,d2,d4,d6}3无变化无变化无变化无变化无变化无变化无变化无变化第三轮全部不变收敛。最终 B4 的 IN 是 {d1, d2, d4}其中关于 y 的定值有两个d2 和 d4。这就是y 到达 B4 时可能来自两条路径的严谨表述。这个结果怎么用z y这一句如果编译器看到 y 的到达定值集合里同时有常量 2和表达式 x1它没法把 z 折叠成常量只能放弃。但如果 B3 里写的是y 3那么到达 B4 的 y 的定值全是常量编译器就能确定 z 一定等于某个值——当然前提是两条路径给的值相同否则还得做格上的合并。而如果某个变量的到达定值集合是空集说明走到这里之前它压根没被赋过值这就是经典的使用未初始化变量检测很多静态检查工具的核心逻辑就是这么几行。2.3 为什么这里必须用并集may 分析的保守性有人会问B4 的 IN 里把两条路径的定值都并进来是不是太贪心了真实的执行只会走其中一条另一条根本不存在。答案是编译器不知道会走哪条所以只能保守。这种保守不是缺陷而是正确性的来源。数据流分析有两条铁律宁可多报不可漏报针对 may 分析宁可少优化不可优化错。如果 B4 的 IN 里只有 d4 没有 d2编译器可能得出y 一定等于 x1的结论然后做常量传播一旦真的走了 B2→B4 这条路径程序行为就被改坏了。这种 bug 是最难查的一类——源码看起来完全正常只有特定输入下出错。所以任何一次因为分析结果而做的变换都必须能证明在分析给出的所有可能情况里这个变换都不改变语义。顺带说个实操经验写分析器的时候我习惯先用一个最保守的版本跑通比如所有集合都填全集确认框架没问题再逐步收紧。上来就追求精确往往会分不清是框架错了还是精度策略错了。3. 活跃变量分析变量什么时候算活着3.1 反过来推USE 与 DEF活跃变量分析问的是一个完全不同的问题在程序点 p 之后变量 v 的值还会不会被读到如果会v 在 p 点活跃如果不会v 就是死的它现在占着的寄存器、栈槽、甚至那条赋值语句本身都可以扔掉。这个分析是后向的。每个块有两个集合USE 表示块内先被读、且在读之前没被本块写过的变量DEF 表示块内被写过的变量。方程写起来很对称IN[B] USE[B] ∪ (OUT[B] − DEF[B])OUT[B] ∪ IN[后继块]出口块的 OUT 是空集程序结束后没有变量还有用。注意 USE 的定义里那个读之前没被写过很关键它保证了块内先写后读的情况不会被误算成用了外部传进来的值。拿上一节的同一张图算一遍活跃变量。变量层面B1 写 x、y没读B2 读 xB3 读 x、写 yB4 读 y、写 z。B1USE {}DEF {x, y}B2USE {x}DEF {}B3USE {x}DEF {y}B4USE {y}DEF {z}后向推B4 的 OUT 是 {}IN[B4] {y}。B3 的 OUT IN[B4] {y}IN[B3] {x} ∪ ({y} − {y}) {x}。B2 的 OUT IN[B3] ∪ IN[B4] {x, y}IN[B2] {x} ∪ ({x,y} − {}) {x, y}。B1 的 OUT IN[B2] {x, y}IN[B1] {} ∪ ({x,y} − {x,y}) {}。结果里有一个特别值得玩味的点IN[B3] 里没有 y。这意味着从 B1/B2 流进来的那份 y在 B3 入口就已经死了——因为 B3 马上要重写它旧值再也没人用。而 B4 用到的 y是 B3 里新写的那一份。这个区分在寄存器分配阶段非常值钱B3 里新写的 y 可以直接覆盖旧 y 占的那个寄存器不需要另开一个。3.2 冲突图把活跃信息变成寄存器分配方案活跃变量分析最经典的用途是构造冲突图Interference Graph。规则很简单如果两个变量在同一个程序点同时活跃就在它们之间连一条边表示这俩不能共用同一个寄存器。图建好之后寄存器分配就变成了图着色问题——给每个结点涂一种颜色相邻结点颜色不同颜色数量就是可用寄存器数。实际工程里没这么理想化。图着色是 NP 完全的真实规模下必须用启发式先按度数排序、优先把邻居多的结点溢出到栈上涂完色再做溢出代码的插入。但不管后面多复杂输入永远是活跃变量分析算出来的那几个集合。我见过有人跳过这一步直接按变量声明顺序分配寄存器跑小例子没问题一上真实代码就各种性能塌方——因为活跃区间重叠的变量被迫反复换出换入。还有一个容易忽略的细节活跃变量分析的结果对死赋值极其敏感。x ...之后 x 再也没被读过这条赋值就是死的可以整条删掉连带着右侧表达式的计算也可以删前提是右侧没有副作用函数调用就不能随便删。这条规则在清理被宏展开、模板实例化搞出一堆无用临时变量的代码时特别管用。3.3 may 与 must 在活跃性上的分歧点活跃变量本身是 may 分析只要有一条后继路径上会用到就算活跃。这个选择同样是出于保守。假如你按 must 来算所有路径都必须用到才算活那么一条只在某个分支里用到的变量会被判定为死寄存器被回收——那个分支一旦执行就读到了被覆盖的值。但反过来也有需要 must 信息的场景比如这个变量在这条路径上一定已经被初始化了这就要用必达定值也叫向上暴露的使用来算合并方式改成交集。同一个程序、同一张图换个方向、换个合并方式得到的就是完全不同的问题。这也是我说先定位象限的原因——很多看起来全新的分析需求其实只是把老方程的箭头反过来写。4. 格、单调性与不动点迭代为什么一定会停4.1 把分析结果放到一个格上前面所有的例子分析结果都是某个集合。把所有可能的集合按包含关系排一排就得到一个格Lattice最下面是空集最上面是全集任意两个集合都有最小上界并集和最大下界交集。前向的 may 分析从空集出发往上爬每一步都在往集合里加东西加到不能再加就停。这个抽象的价值在于它把具体算什么和怎么算分开了。不管你是算到达定值、常量传播还是类型推断只要能证明结果集构成一个有限高度的格传递函数是单调的收敛性就自动成立不用每次重新论证。常量传播的格更直观一些每个变量对应一个元素未初始化底、某个具体常量、或者不确定顶。两条路径汇合时取最小上界2 ⊔ 2 22 ⊔ 3 不确定不确定 ⊔ 任何值 不确定。所以一个变量只要在某条路径上被赋了不同的值立刻就退化成不确定这正好对应了前面说的保守性。4.2 单调性给的是不会退步的保证单调性说的是输入变大输出不会变小。形式化一点如果a ⊑ b那么f(a) ⊑ f(b)。为什么这个性质这么重要因为迭代过程中我们是一轮一轮把结果往上加的如果传递函数不单调某一轮加进去的信息可能导致下一轮结果反而变小那就可能出现加了又减、减了又加的震荡永远停不下来。我给这个性质想了个生活化的解释把传递函数想成一个诚实的会计你交给他更多的单据他只会算出不少于之前的账不会因为单据变多反而算出更少的钱。只要会计是诚实的你的账本每一轮只会单调增长而账本可能的取值是有限的格的高度有限所以最多长有限次就到头了。反过来说如果格的高度不是有限的——比如结果里可以放任意精度的整数区间——那即使单调也不保证终止得靠加宽widening之类的技巧强行截断。这一点在自己设计分析的时候必须提前想清楚别等死循环了才发现值域是无限的。4.3 worklist把每轮全扫变成只算受影响的块最笨的迭代方式是每一轮把所有基本块都重算一遍直到某一轮没有任何变化。这个做法正确、好写但浪费改了一个块的结果它的前驱/后继没变没必要重算。worklist 算法解决的就是这个维护一个待处理块的队列初始放进所有块每次取出一个块重算它的 IN/OUT如果结果变了就把它受影响的邻居重新入队前向分析放后继后向分析放前驱。加上已在队列里就不重复加的判断能砍掉大量重复计算。实测下来worklist 在真实程序上的加速比非常可观尤其在深度嵌套的循环结构里。不过我踩过一个坑队列的数据结构选错了。早期用普通列表加in判断块数量一多就退化成平方级换成双端队列加一个布尔标记数组之后速度立刻正常。还有个细节是遍历顺序——前向分析时按逆后序遍历RPO入队通常比随机顺序收敛得快得多因为信息能更快地顺着路径传下去而不是来回震荡。5. 动手实现一个能跑通的到达定值分析器5.1 数据结构指令、基本块、控制流图我倾向于用最朴素的三个类把骨架搭起来先跑通再谈优化。指令用一个元组表示(op, args, dest)比如(assign, [1], x)基本块持有指令列表、前驱列表和后继列表CFG 持有块的有序列表和入口、出口索引。关键设计决定给每条赋值指令分配全局唯一的编号这个编号就是定值分析里集合的元素。用编号而不是用变量名是因为同一个变量会对应多个定值必须能区分。至于集合的存储原型阶段直接用set就好写起来最快等要上规模了再换位向量。5.2 从线性代码到 CFG划分基本块的三条规则划分规则很固定抓住leader块首这个概念就够了第一条指令是 leader任何跳转指令的目标是 leader任何跳转指令的下一条是 leader。从每个 leader 开始一直到下一个 leader 之前就是一块。然后连边如果块的最后一条指令是无条件跳转连到目标块如果是条件跳转连到目标块和顺序的下一块如果既不是跳转也不是返回就连到顺序的下一块。这一步看着简单坑却在细节上条件跳转的两个后继要都连上漏一个活跃变量分析立刻出错返回指令没有后继循环回边不要漏while循环的块会有一条边指回条件判断块很多手写原型就在这里丢了回边导致循环内的信息传不回去。建议在划分完之后先做一次连通性检查从入口块做一次深度优先遍历把走不到的块标出来如果发现大半个程序都走不到八成是回边丢了。5.3 gen/kill 计算与 worklist 主循环下面这段是核心语言用的是 Python思路平移到任何语言都一样def compute_gen_kill(blocks): # 全局定义表变量 - 所有定义它的指令编号 defs_of {} for b in blocks: for idx, (op, args, dest) in enumerate(b.instrs): if dest is not None: defs_of.setdefault(dest, set()).add(b.def_id(idx)) gen, kill {}, {} for b in blocks: g set() for idx, (op, args, dest) in enumerate(b.instrs): if dest is None: continue did b.def_id(idx) g.add(did) # 块内后来的定义会杀掉块内先前同变量的定义 for other in list(g): if other ! did and b.dest_of(other) dest: g.discard(other) killed set() for d in g: killed | defs_of[b.dest_of(d)] kill[b.id] killed - g gen[b.id] g return gen, kill def solve_reaching_defs(blocks, entry, gen, kill): IN {b.id: set() for b in blocks} OUT {b.id: set() for b in blocks} work deque(b.id for b in blocks) in_queue {b.id: True for b in blocks} while work: bid work.popleft() in_queue[bid] False b blocks[bid] new_in set() for p in b.preds: new_in | OUT[p] new_out gen[bid] | (new_in - kill[bid]) if new_in ! IN[bid] or new_out ! OUT[bid]: IN[bid], OUT[bid] new_in, new_out for s in b.succs: # 前向分析通知后继 if not in_queue[s]: in_queue[s] True work.append(s) return IN, OUT有几个地方值得单独说。第一kill集合必须用全局定义表算绝不能只用块内的信息这是我在第二节点名强调过的那件事。第二块内 gen 的修正要在遍历块内指令的循环里做边加边清。第三主循环里判定有没有变化要同时比较 IN 和 OUT只比一个有时候会漏掉传播。5.4 验证先看不动点再看具体案子跑完之后怎么确认结果对我一般做三重验证。第一重不动点自检再跑一轮主循环如果还有块的 OUT 发生变化说明收敛逻辑写错了。这个检查便宜且极其有效。第二重构造已知答案的小用例就像本文第二节那张手工表把分析器输出和手算结果对齐。第三重看具体某条路径随便挑一个分支汇合点把 IN 集合里的定值和源码对照逐个问这个定值真的可能走到这儿吗一般挑三五个就能发现 kill 集合算漏的问题。调通之后第一件事别急着接优化先写个可视化把每个块的 IN/OUT 打印成表格或者画成文本图。我后面几乎每次遇到优化结果不对的问题第一步都是把这个 dump 打开看十次里有八次一眼就能定位。6. 从玩具到生产真实程序里的五个坑6.1 一旦出现取地址和别名就该收手了玩具程序里变量是互相独立的真实程序里到处都是别名两个不同名字的变量指向同一块内存通过一个指针改数据会影响另一个名字读到的值。只要程序里出现了取地址操作或者把对象传出当前函数保守的做法就是把那一刻涉及的所有变量全部标记为可能被任意修改也就是把它们的定值全部杀掉。这当然会损失大量优化机会但这是唯一安全的做法。我见过有人试图做聪明的别名分析按变量名首字母分组做近似结果在特定输入下产生了极难复现的错误——两个变量被误判为互不相关一个优化把一个还没被读到的值覆盖掉了。这类 bug 出在优化器里你就算抓到了现场也很难相信是编译器干的。正确的期待是分析精度决定优化空间但正确性优先级永远更高。一个保守但正确的优化器比一个激进但偶尔出错的优化器有价值一万倍。前者只是慢一点后者会让所有人失去信心。6.2 函数调用是一堵墙跨过去要付代价块内分析好做一旦遇到函数调用就麻烦被调函数改了哪些全局变量传进去的那个对象它会不会存起来改返回值是不是恒定没有过程间的信息调用点只能当成什么都可能发生把这些变量的定值全部清空。真要做过程间分析代价是分析规模从一个函数变成整个调用图还得分清上下文——同一个函数被两处调用参数不同分析结论可能完全不同按调用点做上下文敏感又会带来组合爆炸。我的建议是分阶段先把函数内分析做扎实调用点一律保守处理等整体收益瓶颈确实卡在跨函数上了再针对高频的小函数比如几百个纯计算型的辅助函数做内联内联之后它们自然就变成函数内分析了比直接上上下文敏感便宜得多。6.3 不可达块、死循环和自环带来的麻烦图一旦有环迭代次数就会明显增加如果有不可达的块那些块的分析结果会一直是初始值看起来很怪但无害。真正的问题出在死循环块上它的 IN 集合来自自己形成自环几轮之后会增长到一个不动点这个不动点可能包含一堆本不该存在的定值。如果后面基于这些信息做优化可能把循环体里的某些代码判成永远用不到而删掉——只要那个循环真的会退出行为就变了。我的处理方式是在做优化之前先跑一遍可达性分析把不可达块整块剔除死循环块则在控制流图层面上特殊标记凡是涉及它的分析结果一律按最保守处理不承接任何优化。6.4 集合实现与遍历顺序性能坑比算法坑更多原型用普通集合跑几百条指令没什么感觉一旦指令数上万集合的创建和合并就会成为热点。换位向量是标准解法每个块一个定长整数数组第 i 位表示第 i 号定值是否存在并集变成按位或差集变成与上取反再与。这个改造通常能把分析耗时压下去一个数量级代码还更短。遍历顺序的影响也很大。前向分析用逆后序入队信息能顺着执行流一路传下去往往两三趟就收敛用随机顺序可能要来回扫十几趟。后向分析则反过来用后序。这个结论我在不同规模的项目上验证过很多次几乎每次都能拿到肉眼可见的加速而且改动量只有几行。6.5 别把分析结果当真理它只是一份可信的近似最后一点也是我认为最重要的心态问题。数据流分析的输出永远是对程序行为的保守近似不是精确刻画。它说这个定值可能到达这里实际上可能到达也可能不到达它说这个变量在这里活跃实际执行路径上可能根本不读它。所有基于它的判断都必须保证在这个近似涵盖的所有真实情况里结论都成立。这也解释了为什么静态检查工具总会误报。一个未初始化变量的检查器用的是到达定值分析只要某条理论上可达、实际永远不会走的分支上存在一条未初始化的路径它就得报警。想减少误报正确方向是提升分析精度加路径敏感、加常量传播、加不可达分支剪枝而不是放宽分析的正确性要求——后者会让你漏掉真 bug而漏报比误报危险得多。我现在写任何一个要依赖数据流信息的优化 pass都会在注释里写清楚三件事用的是哪种分析、是 may 还是 must、在哪些情况下主动降级到保守。这三行注释在半年后回看代码时能省下大量重新推理的时间。另外分享一个小习惯在分析器的收敛循环外面套一个计数器打印每个程序平均迭代了几轮。一旦某次改动让这个数字突然翻倍通常意味着某个块的传递函数写错了或者回边连错了——这比等优化结果出问题再回头查要快得多。
部署与MNIST手写数字识别)
