1. 数据流分析到底在回答什么问题数据流分析是软件分析课程里最硬核、也最容易被低估的一讲。我刚接触这门经典公开课时听完到达定值分析的整套定义、传递函数和迭代算法觉得自己理解得差不多了等学到活跃变量分析方向从前往后翻成从后往前我整个人是懵的。直到后来真的在编译器里写优化 pass、查那些明明做了公共子表达式消除却没生效的诡异问题才回头把这部分内容重新啃了一遍越啃越觉得当初上课时只记住了公式没记住公式背后的思考方式。这门课的第 3 讲《数据流分析-应用Ⅰ》只干一件事把数据分析这四个字落到三个具体的分析实例上分别是到达定值分析、活跃变量分析和可用表达式分析。看起来是三个独立的算法实际上它们共用一套骨架在控制流图上定义数据流事实、指定传递函数和汇合运算、初始化边界条件然后迭代到不动点。先把这套骨架弄明白后面的数据流分析-应用Ⅱ、过程间分析、指针分析都会顺很多。这篇内容适合正在上软件分析、编译原理进阶课程的同学也适合想理解编译器底层优化原理的工程人员。我会把每个公式为什么长这样、每个初始化为什么是空集或全集都讲透再配上完整的手算例子。最后还会聊聊这些理想化分析到了真实编译器里会遭遇什么。1.1 这一讲在软件分析全景里的位置软件分析的目标是在不运行程序的前提下回答关于程序的问题。数据流分析是其中最经典的家族它把程序抽象成控制流图把程序执行到某个点时的状态抽象成一个数据流事实集合然后通过图上的传播来推断事实。第 3 讲属于通过具体例子建立直觉的一讲它不追求算法的复杂度分析而是先把三个最基础的实例讲明白。这三个实例分别代表了两类极其重要的分野may 分析和 must 分析前向分析和后向分析。把它们搞定了相当于把数据流分析的四维坐标系都踩了一遍。1.2 may 和 must两种结论类型的直觉先记住一个最重要的直觉。may 分析回答的问题是有没有可能可能存在到达定值、变量可能活跃。这类分析的结论是过近似宁可多报不能漏报。must 分析回答的问题是一定是表达式一定被计算过。这类分析的结论是欠近似宁可少报也不能错报。这个区别直接决定了汇合运算用并集还是交集。may 分析在路径汇合处取并集只要有一条路径上事实成立汇合处就认为它成立。must 分析取交集必须所有路径都成立汇合处才认为它成立。后面三个例子会把这条线彻底走通。2. 起手式CFG、程序点与四个要素在展开三个分析之前最好先把公用的底层设施讲清楚。这部分如果只看课程讲义会觉得是废话但实际写代码时这些细节恰恰是容易翻车的地方。2.1 CFG 和基本块所有分析的共同底盘控制流图CFG的节点可以是单条语句也可以是基本块。基本块是一条只能从入口进、从出口出、中间没有跳转的直线指令序列。构造 CFG 时基本块还会配上一个 entry 和一个 exit 作为虚拟的入口和出口节点。为什么要有基本块因为分析粒度可以随需求调整。单语句节点最精确但迭代慢基本块节点信息密度高、迭代快绝大部分编译器这个层级做分析。课程里为了推导方便通常先假设一个节点对应一条语句或一个简单块。程序点就是基本块边界上的位置每个基本块 B 都有一个入口点 IN[B] 和一个出口点 OUT[B]。数据流分析的全部工作就是算出每个程序点上的数据流事实集合。2.2 每个分析都要回答的四个要素任何数据流分析动手之前都要先把四个问题答清楚这是这门课最实用的一套框架方向事实顺着控制流从前向后传播还是从后向前传播前向分析算 OUT f(IN)后向分析算 IN f(OUT)。传递函数一个基本块对数据流事实做什么变换经典形态是 OUT[B] gen[B] ∪ (IN[B] − kill[B])其中 gen 是块产生的事实kill 是块杀死的事实。汇合运算多个前驱或后继的事实汇合时怎么合并may 分析用并集 ∪must 分析用交集 ∩。初始化边界节点和所有内部节点的初始集合是什么may 分析通常从空集出发must 分析往往从全集出发。这一讲的三个分析本质上只是这四个问题的四组不同答案。记住这一点后面就不会在三个算法之间迷失。2.3 迭代到不动点分析为什么能算完给定 CFG 和初始集合后从入口或出口开始反复应用传递函数和汇合运算每次迭代 IN/OUT 都会更新。因为每个集合都是某个有限全集定值集合、变量集合、表达式集合的子集may 分析的集合只会单调增大must 分析只会单调减小所以有限步之后必然到达不再变化的不动点。理解终止性关键看单调二字。初始赋值给了分析一个最保守的起点然后信息沿着图流动每次更新都在向更精确的方向靠近但永远不会越过全集边界。这保证了算法的有界性也是后面所有静态分析理论的基础。3. 到达定值分析前向 may 分析的完整推演先看最标准的前向 may 分析。这个分析也承担了第一次介绍四个要素的教学任务所以它的每个设计决定都值得反复体会。3.1 什么是到达为什么要关心程序里一条形如v x op y的赋值语句产生一个定值definition记作 d变量 v 在某个程序点被赋了值。如果说定值 d 到达另一个程序点 p意味着存在一条从 d 到 p 的执行路径路径上没有再对 v 赋值。注意存在一条路径这个条件这是典型的 may 语义。只要有可能我们就认为它可能到达。它关心的是数据可能从哪来这恰好是变量是否被使用前赋值这个问题的答案来源。3.2 gen/kill 的落地细节对单条定值d: v x op y它的 gen 集合就是 {d}kill 集合是整个程序里所有对变量 v 的其他定值。原因是一个新的定值一旦执行之前对 v 的所有定值就全部失效。对基本块 Bgen[B] 是块内所有能存活到块尾的定值也就是在块内没有被后续覆盖的定值。kill[B] 是块内每条语句 kill 的并集凡是在 B 里被赋过值的变量它在全程序中的所有定值都会被 B 杀掉。这里有个新手容易纠结的点gen 和 kill 可以有重叠。比如块内连续两条x 1; x 2gen 只包含第二个定值kill 却包含程序里所有对 x 的定值包括第一个。传递函数 OUT gen ∪ (IN − kill) 之所以这样写就是为了保证块内存活的定值不会被自己的 kill 误伤。3.3 手算一个完整例子用经典的分支汇合结构来看程序如下------- | entry | ------- | v -------------------------- | B1: d1: x 5 | -------------------------- | cond?| / \ v v ------------- ------------- | B2: d2: yx | | B3: d3:x2 | ------------- ------------- \ / \ / vv -------------------------- | B4: d4: z x y | -------------------------- | v ------- | exit | -------每个块的 gen、kill 如下基本块genkillB1{d1}{d3}B2{d2}∅B3{d3}{d1}B4{d4}∅初始化入口 OUT[entry] ∅其余各块 OUT 也从 ∅ 开始。迭代时 B 的 IN 等于所有前驱 OUT 的并集然后再算 OUT gen ∪ (IN − kill)。B1IN ∅OUT {d1}B2IN {d1}OUT {d1, d2}B3IN {d1}OUT {d3} d1 被 kill 掉B4IN {d1, d2} ∪ {d3} {d1, d2, d3}OUT {d1, d2, d3, d4}所以在 B4 入口x 可能来自 d1 也可能来自 d3y 来自 d2。如果 d1 给 x 赋常数 5、d3 给 x 赋常数 2那么这里不能断定 x 是常量因为两个可能定值都到达了。这种多条路径汇合的处理方式会贯穿所有数据流分析。3.4 派上用场未初始化变量与常量传播到达定值最直接的应用是检测未初始化变量如果某个使用变量 v 的程序点它的 IN 集合里没有任何对 v 的定值那么必然存在一条执行路径让 v 在使用前没有被赋值必须报警。常量传播的推理也用到达定值做底子如果一个变量的所有到达定值都给同一个常数那这个变量在当前点可以安全替换成该常数。反过来只要有一个非常量的定值到达结论就不成立。这种推理方式说明了一件事may 分析的结论服务于保守的安全判断宁可放弃优化机会也不能做出错误优化。4. 活跃变量分析从后往前读程序刚习惯前向分析课程立刻扔来一个反向例子。活跃变量分析的每个环节都把上一节的分析镜像了一遍但思维方向完全相反。4.1 倒着走的动机一个变量 v 在程序点 p 是活跃的live如果存在一条从 p 出发到某个使用 v 的路径且路径上 v 没有被重新赋值。换句话说从当前点往后看v 的值还有可能被读到所以还活着。这个语义天然是后向的我们要从未来对 v 的读取倒推现在谁需要保留 v。寄存器分配就是最好的应用场景——如果某条指令执行完后变量就不再活跃说明它的值在当前寄存器里已经是废的这个寄存器可以被回收。4.2 同一个例子的后向计算仍然用分支汇合结构换个例子B1: d1: x 5 B2: d2: y x B3: d3: x 2 B4: d4: z x y后向分析的入口从出口开始。先初始化 IN[exit] ∅其余所有块的 IN 也都是 ∅。每轮迭代先算 OUT后继 IN 的并集再算 IN gen ∪ (OUT − kill)。各块的 gen、kill 如下基本块gen块内被使用的变量kill块内被赋值的变量B1∅{x}B2{x}{y}B3∅{x}B4{x, y}{z}从 B4 倒推B4OUT IN[exit] ∅IN {x, y} ∪ (∅ − {z}) {x, y}B3OUT IN[B4] {x, y}IN ∅ ∪ ({x, y} − {x}) {y}B2OUT IN[B3] ∪ IN[B4] {y} ∪ {x, y} {x, y}IN {x} ∪ ({x, y} − {y}) {x}B1OUT IN[B2] ∪ IN[B3] {x} ∪ {y} {x, y}IN ∅ ∪ ({x, y} − {x}) {y}结论很反直觉程序入口处活跃的只有 yx 反而在入口处不活跃。原因是 B1 会对 x 赋值赋值前的 x 值无论来自哪里都没人再读而 y 是 B2 赋值后要到 B4 才被读所以一路倒推y 从入口开始就必须活跃。这个例子特别适合用来检验自己有没有真的理解后向分析不要顺着程序往前猜每一步都问这个变量在后面的某处会不会被读到、中间有没有被改写。4.3 寄存器分配和死代码消除活跃变量最经典的应用是寄存器分配。线性扫描和图着色分配都依赖某一点的活跃变量集合不能超过可用寄存器数量如果一个点在某一时刻需要同时活跃的变量超出寄存器数就必须把某些值溢出到内存。死代码消除也建立在活跃变量的基础上如果一条赋值语句v ...之后 v 不再活跃并且这条语句没有任何副作用比如不调用函数、不写全局变量那么整条语句可以安全删掉。注意这里用的是之后不活跃本质是看这条语句出口处的活跃集合。实际写优化 pass 时还有个经验活跃变量分析要和副作用分析配合使用。一个纯本地赋值确实可以随便删但一旦语句有隐式副作用哪怕变量不活跃也不能删。这是课堂例题不会强调、工程里天天踩的地方。5. 可用表达式分析must 分析的初始化反直觉前两个分析都是 may 加并集第三个分析突然变成 must 加交集而且初始化不再是空集而是全集 U。这一节是最容易让人在实现时写错的地方也是最值得仔细琢磨的一节。5.1 从 may 切到 must 意味着什么表达式x op y在程序点 p 可用available当且仅当从入口到 p 的每一条路径上都计算过x op y并且在最后一次计算之后x 和 y 都没有被重新赋值。注意每一条路径这个措辞。一条路径上计算过不算数必须所有路径都计算过。这是因为可用表达式的下游消费者是优化器它想在新求值点复用之前的结果。如果只有部分路径计算过那么复用就是错的必须自己再算一次。这种必须保证正确的语义对应的就是 must 分析。5.2 为什么初始化是全集而不是空集很多人第一次接触可用表达式分析时都会觉得奇怪前两个分析从空集出发为什么这个分析要从全集出发关键在于汇合运算是交集。假设从空集开始第一次迭代时汇合点会拿前驱的 OUT 做交集由于前驱初始都是空集交出来还是空集。这个空集会一路传染下去最终结果就是没有任何表达式可用。这个结论是安全但完全没用的它等于告诉优化器所有子表达式都别想复用。如果从全集 U 出发每轮迭代交集才会把真正不可用的表达式逐步过滤掉最终得到尽可能大的可用集合。这正是 must 分析期望的结果在所有安全答案里选最精确的一个。可以这样理解并集分析的起点是什么都不知道交集分析的起点必须是假定万事皆可能然后再修正。5.3 分支合并时交集怎么起作用用一个分支例子来说明------- | entry | ------- | v ------------------------- | B1: a b c | ------------------------- | if p?| / \ v v --------- --------- | B2: | | B3: | | d bc | | e mn | --------- --------- \ / v v ----------------------------- | B4: f b c | | g m n | -----------------------------程序里的表达式全集 U {bc, mn}。初始化 OUT[B2] OUT[B3] OUT[B4] UOUT[entry] ∅。B1IN ∅OUT {bc}B2IN {bc}OUT {bc}B3IN {bc}OUT {bc, mn}B4IN OUT[B2] ∩ OUT[B3] {bc} ∩ {bc, mn} {bc}OUT {bc, mn}于是 B4 入口处bc 可用因为两条路径都算过它mn 不可用因为走 B2 那条路径时从没算过 mn。所以f bc可以复用之前的结果g mn必须老老实实重新计算。这个例子直观展示了交集在分支汇合时如何做全票通过的裁断。kill 集合的细节也要注意。可用表达式的 kill 不是杀掉一个表达式而是杀掉所有包含被赋值变量的表达式。比如块内执行c ...那么所有包含 c 的表达式如bc都失效。这和到达定值的杀掉同名变量的定值思路类似但作用范围是整个表达式集合初学时容易忘。5.4 公共子表达式消除可用表达式的经典应用就是公共子表达式消除CSE如果表达式在某个程序点可用并且该点的语句正好是求这个表达式就把这次求值替换成之前保存的结果。以 B4 为例f bc因为 bc 可用在语义上等价于f 上次算 bc 的结果编译器可以插入临时变量复用如果g mn在 B4 某条路径上不可用就不能复用否则会产生错误结果。实际编译器里的 CSE 往往做得更强会结合值编号、支配树等但可用表达式分析给出了最基础的能否安全替换的判断框架理解它对理解现代优化非常关键。6. 三个分析共用一个迭代骨架三个分析看起来各不相同实际是同一段代码换了四个参数。把骨架抽象出来不仅便于实现也便于将来设计自己的分析。6.1 统一算法与终止性以通用前向分析为例伪代码如下// 初始化 OUT[entry] 边界值 for B entry 以外的每个基本块: OUT[B] 初始值 // may 用空集must 用全集 IN[B] 初始值 // 迭代 repeat: for B entry 以外的每个基本块: IN[B] meet({ OUT[p] | p 是 B 的前驱 }) // may 用 ∪must 用 ∩ OUT[B] gen[B] ∪ (IN[B] - kill[B]) until 所有 IN/OUT 不再变化后向分析只需要把前驱换成后继把初始化从 entry 挪到 exitOUT[B] meet({ IN[s] | s 是 B 的后继 }) IN[B] gen[B] ∪ (OUT[B] - kill[B])终止性的论证很简单每次迭代may 分析的集合不减must 分析的集合不增而所有集合都是某个有限全集定值集合、变量集合、表达式集合的子集。有限且单调必然收敛。迭代次数不会超过全集元素个数 × 节点数这个量级实际往往远小于这个上界。6.2 迭代顺序RPO 和 postorder 的小手段虽然任何顺序最终都能收敛但顺序严重影响收敛速度。合理直觉是信息从哪里来就优先处理哪个节点。前向分析的信息从 entry 流向 exit因此用反向后序reverse postorder简称 RPO遍历最有利它保证在无环路径上处理一个节点之前它的前驱基本都处理过了一轮迭代能传播得更远。后向分析的信息从 exit 流向 entry因此直接用后序postorder遍历让后继先于当前节点被处理。自己实现分析时这是个特别容易忽略的优化点。用固定循环加错误的遍历顺序分析不会出错但可能要多跑好几轮迭代在函数比较大时能感受到明显差异。6.3 一张表对齐三个分析分析方向事实集合汇合运算初始化may/must典型应用到达定值前向程序中的定值 d∪∅may未初始化变量检测、常量传播活跃变量后向程序中的变量 v∪∅may寄存器分配、死代码消除可用表达式前向程序中的表达式 e∩U全集must公共子表达式消除这张表值得贴在手边。面试、笔试、做课程作业时只要把这四列背清楚基本不会犯方向错误或初始化错误。工程实现上还有两个实用建议。第一不要只做一轮复杂的两层循环就交差至少要打印每一轮的 IN/OUT和手算结果对一遍。第二真正的高性能实现用 worklist某个节点的输出一旦变化才把它影响到的下游节点重新加入待处理队列而不是每轮都扫描全部节点。课程讲双循环是为了理论清晰实际编译器里跑的都是 worklist 变体。7. 讲义之外真实编译器里的数据流分析课程讲到这里就完成了数据流分析三个应用案例的教学但真实世界要比理想模型复杂得多。把讲义里的纸上分析映射到真实工具能帮助你理解哪些是核心思想哪些只是简化假设。7.1 在 LLVM 和 GCC 里它们变成了什么现代编译器并不一定按这里三个分析的原始形态实现。活跃变量分析是底层设施LLVM 里就有专门的 LiveVariables 分析寄存器分配、栈帧布局都会消费它。死代码消除用的是更激进的变体还会结合指令副作用和可达性做整体裁剪。可用表达式分析在 GCC 里以 CSE pass 的形式出现但 LLVM 更倾向于用全局值编号GVN来做更强的替换。值编号的思路和可用表达式一脉相承只是把表达式等价抽象成值等价能识别出形式不同但结果相同的运算覆盖面更广。到达定值分析在现代编译器内部反而用得少了因为 SSA静态单赋值形式让一个变量只有一个定值点成为结构属性很多标注不需要单独分析。但 SSA 并不是凭空冒出来的它本身就可以看作把到达定值关系编码进变量名的结果。理解经典分析才能真正理解 SSA 为什么这么设计。7.2 指针与函数调用让理想假设破功课堂分析假设程序里没有指针没有堆没有函数调用。真实程序三条全破。指针会让 kill 集合变得非常难算。*p 42这一句到底杀了哪些变量的定值取决于 p 可能指向谁。如果没有别名分析只能保守地假设它可能改写任何以指针可达的变量于是 kill 集合变得很大分析精度急剧下降。这就是为什么指针分析通常要先于或联合数据流分析来做。函数调用也会破坏分析的精度。被调用函数内部的定值和副作用在调用点上是不可见的但调用点之后该活跃的变量、该可用的表达式都可能被调用改变。最简单省事的处理是采取保守假设调用可能修改所有全局可见的状态。很多生产级分析器会为每个函数做 mod/ref 摘要把摘要反映到调用点这就走向了过程间分析的领域。7.3 最后一点个人体会把这些内容重新梳理一遍之后我的最大体会是数据流分析不难难的是遇到具体问题时能不能快速定位到该用哪个方向、哪个汇合、哪个初始化。建议每个打算深入静态分析的读者都亲手实现一遍这三个分析用一个带分支、带循环的小程序做测试。你会在调试过程中真切体会到前向分析写反遍历顺序只是慢可用表达式分析忘了初始化全集则是完全错误而且错误还很隐蔽。课程第 3 讲只是数据流分析的开始后面还有过程间分析、指针分析、抽象解释这些进阶内容。但只要你把四个要素和may/must 决定集合运算这两条线牢牢记住后面每节课都可以用这套框架快速归位。
1. 数据流分析到底在回答什么问题数据流分析是软件分析课程里最硬核、也最容易被低估的一讲。我刚接触这门经典公开课时听完到达定值分析的整套定义、传递函数和迭代算法觉得自己理解得差不多了等学到活跃变量分析方向从前往后翻成从后往前我整个人是懵的。直到后来真的在编译器里写优化 pass、查那些明明做了公共子表达式消除却没生效的诡异问题才回头把这部分内容重新啃了一遍越啃越觉得当初上课时只记住了公式没记住公式背后的思考方式。这门课的第 3 讲《数据流分析-应用Ⅰ》只干一件事把数据分析这四个字落到三个具体的分析实例上分别是到达定值分析、活跃变量分析和可用表达式分析。看起来是三个独立的算法实际上它们共用一套骨架在控制流图上定义数据流事实、指定传递函数和汇合运算、初始化边界条件然后迭代到不动点。先把这套骨架弄明白后面的数据流分析-应用Ⅱ、过程间分析、指针分析都会顺很多。这篇内容适合正在上软件分析、编译原理进阶课程的同学也适合想理解编译器底层优化原理的工程人员。我会把每个公式为什么长这样、每个初始化为什么是空集或全集都讲透再配上完整的手算例子。最后还会聊聊这些理想化分析到了真实编译器里会遭遇什么。1.1 这一讲在软件分析全景里的位置软件分析的目标是在不运行程序的前提下回答关于程序的问题。数据流分析是其中最经典的家族它把程序抽象成控制流图把程序执行到某个点时的状态抽象成一个数据流事实集合然后通过图上的传播来推断事实。第 3 讲属于通过具体例子建立直觉的一讲它不追求算法的复杂度分析而是先把三个最基础的实例讲明白。这三个实例分别代表了两类极其重要的分野may 分析和 must 分析前向分析和后向分析。把它们搞定了相当于把数据流分析的四维坐标系都踩了一遍。1.2 may 和 must两种结论类型的直觉先记住一个最重要的直觉。may 分析回答的问题是有没有可能可能存在到达定值、变量可能活跃。这类分析的结论是过近似宁可多报不能漏报。must 分析回答的问题是一定是表达式一定被计算过。这类分析的结论是欠近似宁可少报也不能错报。这个区别直接决定了汇合运算用并集还是交集。may 分析在路径汇合处取并集只要有一条路径上事实成立汇合处就认为它成立。must 分析取交集必须所有路径都成立汇合处才认为它成立。后面三个例子会把这条线彻底走通。2. 起手式CFG、程序点与四个要素在展开三个分析之前最好先把公用的底层设施讲清楚。这部分如果只看课程讲义会觉得是废话但实际写代码时这些细节恰恰是容易翻车的地方。2.1 CFG 和基本块所有分析的共同底盘控制流图CFG的节点可以是单条语句也可以是基本块。基本块是一条只能从入口进、从出口出、中间没有跳转的直线指令序列。构造 CFG 时基本块还会配上一个 entry 和一个 exit 作为虚拟的入口和出口节点。为什么要有基本块因为分析粒度可以随需求调整。单语句节点最精确但迭代慢基本块节点信息密度高、迭代快绝大部分编译器这个层级做分析。课程里为了推导方便通常先假设一个节点对应一条语句或一个简单块。程序点就是基本块边界上的位置每个基本块 B 都有一个入口点 IN[B] 和一个出口点 OUT[B]。数据流分析的全部工作就是算出每个程序点上的数据流事实集合。2.2 每个分析都要回答的四个要素任何数据流分析动手之前都要先把四个问题答清楚这是这门课最实用的一套框架方向事实顺着控制流从前向后传播还是从后向前传播前向分析算 OUT f(IN)后向分析算 IN f(OUT)。传递函数一个基本块对数据流事实做什么变换经典形态是 OUT[B] gen[B] ∪ (IN[B] − kill[B])其中 gen 是块产生的事实kill 是块杀死的事实。汇合运算多个前驱或后继的事实汇合时怎么合并may 分析用并集 ∪must 分析用交集 ∩。初始化边界节点和所有内部节点的初始集合是什么may 分析通常从空集出发must 分析往往从全集出发。这一讲的三个分析本质上只是这四个问题的四组不同答案。记住这一点后面就不会在三个算法之间迷失。2.3 迭代到不动点分析为什么能算完给定 CFG 和初始集合后从入口或出口开始反复应用传递函数和汇合运算每次迭代 IN/OUT 都会更新。因为每个集合都是某个有限全集定值集合、变量集合、表达式集合的子集may 分析的集合只会单调增大must 分析只会单调减小所以有限步之后必然到达不再变化的不动点。理解终止性关键看单调二字。初始赋值给了分析一个最保守的起点然后信息沿着图流动每次更新都在向更精确的方向靠近但永远不会越过全集边界。这保证了算法的有界性也是后面所有静态分析理论的基础。3. 到达定值分析前向 may 分析的完整推演先看最标准的前向 may 分析。这个分析也承担了第一次介绍四个要素的教学任务所以它的每个设计决定都值得反复体会。3.1 什么是到达为什么要关心程序里一条形如v x op y的赋值语句产生一个定值definition记作 d变量 v 在某个程序点被赋了值。如果说定值 d 到达另一个程序点 p意味着存在一条从 d 到 p 的执行路径路径上没有再对 v 赋值。注意存在一条路径这个条件这是典型的 may 语义。只要有可能我们就认为它可能到达。它关心的是数据可能从哪来这恰好是变量是否被使用前赋值这个问题的答案来源。3.2 gen/kill 的落地细节对单条定值d: v x op y它的 gen 集合就是 {d}kill 集合是整个程序里所有对变量 v 的其他定值。原因是一个新的定值一旦执行之前对 v 的所有定值就全部失效。对基本块 Bgen[B] 是块内所有能存活到块尾的定值也就是在块内没有被后续覆盖的定值。kill[B] 是块内每条语句 kill 的并集凡是在 B 里被赋过值的变量它在全程序中的所有定值都会被 B 杀掉。这里有个新手容易纠结的点gen 和 kill 可以有重叠。比如块内连续两条x 1; x 2gen 只包含第二个定值kill 却包含程序里所有对 x 的定值包括第一个。传递函数 OUT gen ∪ (IN − kill) 之所以这样写就是为了保证块内存活的定值不会被自己的 kill 误伤。3.3 手算一个完整例子用经典的分支汇合结构来看程序如下------- | entry | ------- | v -------------------------- | B1: d1: x 5 | -------------------------- | cond?| / \ v v ------------- ------------- | B2: d2: yx | | B3: d3:x2 | ------------- ------------- \ / \ / vv -------------------------- | B4: d4: z x y | -------------------------- | v ------- | exit | -------每个块的 gen、kill 如下基本块genkillB1{d1}{d3}B2{d2}∅B3{d3}{d1}B4{d4}∅初始化入口 OUT[entry] ∅其余各块 OUT 也从 ∅ 开始。迭代时 B 的 IN 等于所有前驱 OUT 的并集然后再算 OUT gen ∪ (IN − kill)。B1IN ∅OUT {d1}B2IN {d1}OUT {d1, d2}B3IN {d1}OUT {d3} d1 被 kill 掉B4IN {d1, d2} ∪ {d3} {d1, d2, d3}OUT {d1, d2, d3, d4}所以在 B4 入口x 可能来自 d1 也可能来自 d3y 来自 d2。如果 d1 给 x 赋常数 5、d3 给 x 赋常数 2那么这里不能断定 x 是常量因为两个可能定值都到达了。这种多条路径汇合的处理方式会贯穿所有数据流分析。3.4 派上用场未初始化变量与常量传播到达定值最直接的应用是检测未初始化变量如果某个使用变量 v 的程序点它的 IN 集合里没有任何对 v 的定值那么必然存在一条执行路径让 v 在使用前没有被赋值必须报警。常量传播的推理也用到达定值做底子如果一个变量的所有到达定值都给同一个常数那这个变量在当前点可以安全替换成该常数。反过来只要有一个非常量的定值到达结论就不成立。这种推理方式说明了一件事may 分析的结论服务于保守的安全判断宁可放弃优化机会也不能做出错误优化。4. 活跃变量分析从后往前读程序刚习惯前向分析课程立刻扔来一个反向例子。活跃变量分析的每个环节都把上一节的分析镜像了一遍但思维方向完全相反。4.1 倒着走的动机一个变量 v 在程序点 p 是活跃的live如果存在一条从 p 出发到某个使用 v 的路径且路径上 v 没有被重新赋值。换句话说从当前点往后看v 的值还有可能被读到所以还活着。这个语义天然是后向的我们要从未来对 v 的读取倒推现在谁需要保留 v。寄存器分配就是最好的应用场景——如果某条指令执行完后变量就不再活跃说明它的值在当前寄存器里已经是废的这个寄存器可以被回收。4.2 同一个例子的后向计算仍然用分支汇合结构换个例子B1: d1: x 5 B2: d2: y x B3: d3: x 2 B4: d4: z x y后向分析的入口从出口开始。先初始化 IN[exit] ∅其余所有块的 IN 也都是 ∅。每轮迭代先算 OUT后继 IN 的并集再算 IN gen ∪ (OUT − kill)。各块的 gen、kill 如下基本块gen块内被使用的变量kill块内被赋值的变量B1∅{x}B2{x}{y}B3∅{x}B4{x, y}{z}从 B4 倒推B4OUT IN[exit] ∅IN {x, y} ∪ (∅ − {z}) {x, y}B3OUT IN[B4] {x, y}IN ∅ ∪ ({x, y} − {x}) {y}B2OUT IN[B3] ∪ IN[B4] {y} ∪ {x, y} {x, y}IN {x} ∪ ({x, y} − {y}) {x}B1OUT IN[B2] ∪ IN[B3] {x} ∪ {y} {x, y}IN ∅ ∪ ({x, y} − {x}) {y}结论很反直觉程序入口处活跃的只有 yx 反而在入口处不活跃。原因是 B1 会对 x 赋值赋值前的 x 值无论来自哪里都没人再读而 y 是 B2 赋值后要到 B4 才被读所以一路倒推y 从入口开始就必须活跃。这个例子特别适合用来检验自己有没有真的理解后向分析不要顺着程序往前猜每一步都问这个变量在后面的某处会不会被读到、中间有没有被改写。4.3 寄存器分配和死代码消除活跃变量最经典的应用是寄存器分配。线性扫描和图着色分配都依赖某一点的活跃变量集合不能超过可用寄存器数量如果一个点在某一时刻需要同时活跃的变量超出寄存器数就必须把某些值溢出到内存。死代码消除也建立在活跃变量的基础上如果一条赋值语句v ...之后 v 不再活跃并且这条语句没有任何副作用比如不调用函数、不写全局变量那么整条语句可以安全删掉。注意这里用的是之后不活跃本质是看这条语句出口处的活跃集合。实际写优化 pass 时还有个经验活跃变量分析要和副作用分析配合使用。一个纯本地赋值确实可以随便删但一旦语句有隐式副作用哪怕变量不活跃也不能删。这是课堂例题不会强调、工程里天天踩的地方。5. 可用表达式分析must 分析的初始化反直觉前两个分析都是 may 加并集第三个分析突然变成 must 加交集而且初始化不再是空集而是全集 U。这一节是最容易让人在实现时写错的地方也是最值得仔细琢磨的一节。5.1 从 may 切到 must 意味着什么表达式x op y在程序点 p 可用available当且仅当从入口到 p 的每一条路径上都计算过x op y并且在最后一次计算之后x 和 y 都没有被重新赋值。注意每一条路径这个措辞。一条路径上计算过不算数必须所有路径都计算过。这是因为可用表达式的下游消费者是优化器它想在新求值点复用之前的结果。如果只有部分路径计算过那么复用就是错的必须自己再算一次。这种必须保证正确的语义对应的就是 must 分析。5.2 为什么初始化是全集而不是空集很多人第一次接触可用表达式分析时都会觉得奇怪前两个分析从空集出发为什么这个分析要从全集出发关键在于汇合运算是交集。假设从空集开始第一次迭代时汇合点会拿前驱的 OUT 做交集由于前驱初始都是空集交出来还是空集。这个空集会一路传染下去最终结果就是没有任何表达式可用。这个结论是安全但完全没用的它等于告诉优化器所有子表达式都别想复用。如果从全集 U 出发每轮迭代交集才会把真正不可用的表达式逐步过滤掉最终得到尽可能大的可用集合。这正是 must 分析期望的结果在所有安全答案里选最精确的一个。可以这样理解并集分析的起点是什么都不知道交集分析的起点必须是假定万事皆可能然后再修正。5.3 分支合并时交集怎么起作用用一个分支例子来说明------- | entry | ------- | v ------------------------- | B1: a b c | ------------------------- | if p?| / \ v v --------- --------- | B2: | | B3: | | d bc | | e mn | --------- --------- \ / v v ----------------------------- | B4: f b c | | g m n | -----------------------------程序里的表达式全集 U {bc, mn}。初始化 OUT[B2] OUT[B3] OUT[B4] UOUT[entry] ∅。B1IN ∅OUT {bc}B2IN {bc}OUT {bc}B3IN {bc}OUT {bc, mn}B4IN OUT[B2] ∩ OUT[B3] {bc} ∩ {bc, mn} {bc}OUT {bc, mn}于是 B4 入口处bc 可用因为两条路径都算过它mn 不可用因为走 B2 那条路径时从没算过 mn。所以f bc可以复用之前的结果g mn必须老老实实重新计算。这个例子直观展示了交集在分支汇合时如何做全票通过的裁断。kill 集合的细节也要注意。可用表达式的 kill 不是杀掉一个表达式而是杀掉所有包含被赋值变量的表达式。比如块内执行c ...那么所有包含 c 的表达式如bc都失效。这和到达定值的杀掉同名变量的定值思路类似但作用范围是整个表达式集合初学时容易忘。5.4 公共子表达式消除可用表达式的经典应用就是公共子表达式消除CSE如果表达式在某个程序点可用并且该点的语句正好是求这个表达式就把这次求值替换成之前保存的结果。以 B4 为例f bc因为 bc 可用在语义上等价于f 上次算 bc 的结果编译器可以插入临时变量复用如果g mn在 B4 某条路径上不可用就不能复用否则会产生错误结果。实际编译器里的 CSE 往往做得更强会结合值编号、支配树等但可用表达式分析给出了最基础的能否安全替换的判断框架理解它对理解现代优化非常关键。6. 三个分析共用一个迭代骨架三个分析看起来各不相同实际是同一段代码换了四个参数。把骨架抽象出来不仅便于实现也便于将来设计自己的分析。6.1 统一算法与终止性以通用前向分析为例伪代码如下// 初始化 OUT[entry] 边界值 for B entry 以外的每个基本块: OUT[B] 初始值 // may 用空集must 用全集 IN[B] 初始值 // 迭代 repeat: for B entry 以外的每个基本块: IN[B] meet({ OUT[p] | p 是 B 的前驱 }) // may 用 ∪must 用 ∩ OUT[B] gen[B] ∪ (IN[B] - kill[B]) until 所有 IN/OUT 不再变化后向分析只需要把前驱换成后继把初始化从 entry 挪到 exitOUT[B] meet({ IN[s] | s 是 B 的后继 }) IN[B] gen[B] ∪ (OUT[B] - kill[B])终止性的论证很简单每次迭代may 分析的集合不减must 分析的集合不增而所有集合都是某个有限全集定值集合、变量集合、表达式集合的子集。有限且单调必然收敛。迭代次数不会超过全集元素个数 × 节点数这个量级实际往往远小于这个上界。6.2 迭代顺序RPO 和 postorder 的小手段虽然任何顺序最终都能收敛但顺序严重影响收敛速度。合理直觉是信息从哪里来就优先处理哪个节点。前向分析的信息从 entry 流向 exit因此用反向后序reverse postorder简称 RPO遍历最有利它保证在无环路径上处理一个节点之前它的前驱基本都处理过了一轮迭代能传播得更远。后向分析的信息从 exit 流向 entry因此直接用后序postorder遍历让后继先于当前节点被处理。自己实现分析时这是个特别容易忽略的优化点。用固定循环加错误的遍历顺序分析不会出错但可能要多跑好几轮迭代在函数比较大时能感受到明显差异。6.3 一张表对齐三个分析分析方向事实集合汇合运算初始化may/must典型应用到达定值前向程序中的定值 d∪∅may未初始化变量检测、常量传播活跃变量后向程序中的变量 v∪∅may寄存器分配、死代码消除可用表达式前向程序中的表达式 e∩U全集must公共子表达式消除这张表值得贴在手边。面试、笔试、做课程作业时只要把这四列背清楚基本不会犯方向错误或初始化错误。工程实现上还有两个实用建议。第一不要只做一轮复杂的两层循环就交差至少要打印每一轮的 IN/OUT和手算结果对一遍。第二真正的高性能实现用 worklist某个节点的输出一旦变化才把它影响到的下游节点重新加入待处理队列而不是每轮都扫描全部节点。课程讲双循环是为了理论清晰实际编译器里跑的都是 worklist 变体。7. 讲义之外真实编译器里的数据流分析课程讲到这里就完成了数据流分析三个应用案例的教学但真实世界要比理想模型复杂得多。把讲义里的纸上分析映射到真实工具能帮助你理解哪些是核心思想哪些只是简化假设。7.1 在 LLVM 和 GCC 里它们变成了什么现代编译器并不一定按这里三个分析的原始形态实现。活跃变量分析是底层设施LLVM 里就有专门的 LiveVariables 分析寄存器分配、栈帧布局都会消费它。死代码消除用的是更激进的变体还会结合指令副作用和可达性做整体裁剪。可用表达式分析在 GCC 里以 CSE pass 的形式出现但 LLVM 更倾向于用全局值编号GVN来做更强的替换。值编号的思路和可用表达式一脉相承只是把表达式等价抽象成值等价能识别出形式不同但结果相同的运算覆盖面更广。到达定值分析在现代编译器内部反而用得少了因为 SSA静态单赋值形式让一个变量只有一个定值点成为结构属性很多标注不需要单独分析。但 SSA 并不是凭空冒出来的它本身就可以看作把到达定值关系编码进变量名的结果。理解经典分析才能真正理解 SSA 为什么这么设计。7.2 指针与函数调用让理想假设破功课堂分析假设程序里没有指针没有堆没有函数调用。真实程序三条全破。指针会让 kill 集合变得非常难算。*p 42这一句到底杀了哪些变量的定值取决于 p 可能指向谁。如果没有别名分析只能保守地假设它可能改写任何以指针可达的变量于是 kill 集合变得很大分析精度急剧下降。这就是为什么指针分析通常要先于或联合数据流分析来做。函数调用也会破坏分析的精度。被调用函数内部的定值和副作用在调用点上是不可见的但调用点之后该活跃的变量、该可用的表达式都可能被调用改变。最简单省事的处理是采取保守假设调用可能修改所有全局可见的状态。很多生产级分析器会为每个函数做 mod/ref 摘要把摘要反映到调用点这就走向了过程间分析的领域。7.3 最后一点个人体会把这些内容重新梳理一遍之后我的最大体会是数据流分析不难难的是遇到具体问题时能不能快速定位到该用哪个方向、哪个汇合、哪个初始化。建议每个打算深入静态分析的读者都亲手实现一遍这三个分析用一个带分支、带循环的小程序做测试。你会在调试过程中真切体会到前向分析写反遍历顺序只是慢可用表达式分析忘了初始化全集则是完全错误而且错误还很隐蔽。课程第 3 讲只是数据流分析的开始后面还有过程间分析、指针分析、抽象解释这些进阶内容。但只要你把四个要素和may/must 决定集合运算这两条线牢牢记住后面每节课都可以用这套框架快速归位。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
