数据流分析三大经典应用：到达定值、活跃变量与可用表达式详解

软件分析这门课很多人是到了研究生阶段才第一次系统接触静态分析。数据流分析Data Flow Analysis是所有编译器优化、代码缺陷检测和程序验证工具的共同底座听起来只是在程序里算点信息流真用起来才知道里面的门道有多少。某高校《软件分析》课程的第三讲主题正好是数据流分析的应用Ⅰ集中讲了三个最经典的实例到达定值分析Reaching Definitions、活跃变量分析Live Variables和可用表达式分析Available Expressions。这篇文章就跟课程主线走一遍把我自己啃课、手算和动手写小型分析器时的理解都整理出来适合刚开始接触静态分析、或者想系统补一补编译器基础的同学。1. 数据流分析是怎么看程序的1.1 抽象状态不是执行而是归纳动态执行程序时我们关心的是某个输入下的具体值静态分析恰恰相反它不运行程序却要回答所有可能的输入、所有可能的执行路径下程序是否满足某个性质。直接枚举路径是不现实的因为循环、分支、函数调用组合起来的路径数量是无限的。于是数据流分析采用了一个非常朴素但有效的思路把每个程序点上的信息抽象成一个有限的集合比如哪些变量的定义可能到达这里哪些变量还活着哪些表达式已经被计算过。这些集合就是抽象状态。程序被切成一个个基本块基本块之间用控制流图CFG连接。分析的过程就是沿着 CFG 上的边不断用传递函数计算每个块的入口状态 IN 和出口状态 OUT直到整个图上的状态不再变化为止。可以这样类比你不需要把一条河从源头到入海的每一滴水都追踪一遍只需要在每个观测站记录当前有哪些泥沙、水量多少然后根据上下游关系推算。程序里的泥沙就是我们要追踪的数据信息CFG 上的节点就是观测站。1.2 两个坐标轴方向与交汇运算每个数据流分析都要先回答两个问题沿着什么方向走多个前驱或后继的信息汇聚时怎么合并这两个问题看似简单却是所有分析差异的根源。方向存在前向分析和后向分析。前向分析由程序入口往出口推比如到达定值、可用表达式后向分析由出口往入口推比如活跃变量。选择方向不是随意的它取决于你要回答的问题本质上是从过去看现在还是从现在看未来。信息交汇时有两种基本运算并集∪和交集∩。用并集的分析只要存在一条路径能带来这个信息就保留它这类分析叫 may analysis可能分析用交集的分析必须所有路径都带来这个信息才算数这类分析叫 must analysis必然分析。记住这一条后面所有公式都不会搞混。提示方向决定往哪走交汇运算决定多条路汇合时取什么。二者合起来基本就确定了一个数据流分析的骨架。2. 第一个经典应用到达定值分析2.1 定义与直觉一个赋值能传到哪里到达定值分析回答的问题是在程序的某个点 p哪些对变量的赋值定义definition可能沿着某条执行路径到达这里且在路径上没有再次被同一个变量的赋值覆盖。这里定义通常指给变量赋值的语句比如m a b就是对m的一次定义。这个性质有什么用最典型的场景是检测未初始化变量。如果程序在某处使用了变量m而被使用之前没有任何对m的定义能够到达这个使用点那么m就可能是未初始化的。反过来如果能到达的定义不止一个说明这个变量的值在到达时是不确定的后续做常量传播等优化时就要小心翼翼。直觉上这就是一个 may analysis一个定义只要存在一条路径能到达目标点就认为它到达了。多个路径汇合时信息要取并集。为什么因为我们是保守估计只要某条路径有可能就不能排除这种可能性。2.2 方程与传递函数gen、kill、IN、OUT怎么用每个基本块 B 需要先算出两个集合gen[B] 表示块内新产生的定义kill[B] 表示块内定义的变量在程序其他地方的所有定义因为一旦这个变量被重新赋值原来的定义就被覆盖了到达不了更远的地方。传递函数是OUT[B] gen[B] ∪ (IN[B] − kill[B])意思很直白从 B 出口流出去的信息等于块内新产生的定义加上入口带进来的、没有被块内覆盖的定义。IN[B] 则是所有前驱块 OUT 的并集IN[B] ∪ OUT[pred(B)]整个分析从前向后算。初始化时入口块的 IN 是空集其他块的 OUT 也可以从空集开始因为并集运算从空集出发不断累积最终会收敛到正确的解。2.3 手算完整示例以一个带分支的小程序为例B1: d1: m a b d2: n m B2: if (cond) d3: m c d B3: else d4: m e f B4: d5: n m全集是 {d1, d2, d3, d4, d5}。各块的 gen/kill基本块genkillB1{d1, d2}{d3, d4, d5}B2{d3}{d1, d4}B3{d4}{d1, d3}B4{d5}{d2}用迭代算法第一轮从空集开始B1 的 IN 为空OUT {d1, d2}B2 的 IN 来自 B1等于 {d1, d2}OUT {d3} ∪ ({d1, d2} − {d1, d4}) {d2, d3}B3 的 IN 也来自 B1等于 {d1, d2}OUT {d4} ∪ ({d1, d2} − {d1, d3}) {d2, d4}B4 的 IN 来自 B2 和 B3 的 OUT 的并集等于 {d2, d3, d4}OUT {d5} ∪ ({d2, d3, d4} − {d2}) {d3, d4, d5}第二轮继续算结果不再变化迭代停止。最后可以看到B4 的入口处 d1 已经到不了也就是说在 B4 使用 m 时m 的值只可能来自 d3 或 d4 这两条分支中的某一条而不可能来自 d1。这个结论对检测m 是否被两条不同路径赋予不同值很有用。2.4 工程价值与常见坑到达定值分析是很多优化算法的基础常量传播、复制传播、循环不变量外提都离不开它。实际做的时候有几个地方容易翻车一个块内如果有多条赋值例如m 1; m 2;第一条到块出口时已经被第二条覆盖kill 时要考虑这种块内自我覆盖。处理数组元素或指针变量时a[i] x到底算不算对a的定义算的话 kill 什么这个问题静态分析很难精确回答通常要做保守估计宁可多算几个可能定义。分支条件的真假没有参与分析。路径虽然分叉了但分析不考虑分支条件本身的取值这是流敏感但路径不敏感分析的典型特点后面讲到路径敏感分析时才会改进。注意教材和课程里的例子通常都假设程序没有别名问题。一旦引入指针别名kill 集合就变得不精确最常见的做法是先用指针分析拿到别名信息再喂给数据流分析这也是后续课程的重要内容。3. 第二个经典应用活跃变量分析3.1 逆向思考程序分析为什么要倒流活跃变量分析回答的问题是在程序点 p变量 v 的值是否可能沿着某条路径在将来被使用并且在被使用之前没有被重新定义如果可能就说 v 在 p 点是活跃的live。这个分析和到达定值正好是两个方向。到达定值是从过去的定义往前看活跃变量是从未来的使用往后看。所以要沿 CFG 反向传播出口处的信息往回流向入口传递函数是IN[B] use[B] ∪ (OUT[B] − def[B])其中use[B]是块内在任何定义之前被使用的变量集合def[B]是块内被定义过的变量集合。为什么出口的 OUT 要先减掉 def因为一旦变量在块内被重新定义从更远地方流回来的活跃状态就被打断了这个变量在该块的定义点之前是否活跃取决于块内的使用而不是取决于出口处的情况。3.2 use和def块级信息的正确切分很多人第一次写活跃变量分析时容易把use[B]理解成块内所有被使用的变量这是不对的。比如一个块内有m a b n m如果简单把 use 写成 {a, b, m}又在 def 里写 {m, n}最后算出的 IN 会多出很多不精确的信息。正确的做法是m虽然在第二行被使用了但它在该块第一行就已被定义属于先定义后使用所以m不能进use[B]。这个块的 use 应该是 {a, b}def 是 {m, n}。换句话说use 是被使用且没有被本块抢先定义过的变量。这个细节在期末考试和工程实现里都是高频扣分点。3.3 用前面那个例子做反向迭代还是用到达定值例子的 CFG各块的 use/def基本块usedefB1{a, b}{m, n}B2{c, d}{m}B3{e, f}{m}B4{m}{n}出口边界条件是空集。从 B4 往回推OUT[B4] ∅IN[B4] {m} ∪ (∅ − {n}) {m}OUT[B2] IN[B4] {m}IN[B2] {c, d} ∪ ({m} − {m}) {c, d}OUT[B3] IN[B4] {m}IN[B3] {e, f} ∪ ({m} − {m}) {e, f}OUT[B1] IN[B2] ∪ IN[B3] {c, d} ∪ {e, f} {c, d, e, f}IN[B1] {a, b} ∪ ({c, d, e, f} − {m, n}) {a, b, c, d, e, f}所以 B1 入口处所有变量的状态都是可能是活跃的说明程序一开始就需要这些变量的值。而在 B1 出口处活跃变量变成了 {c, d, e, f}说明执行完 B1 后m 和 n 是否活跃取决于走哪条分支——如果走 B2则活跃的是 c 和 d如果走 B3则是 e 和 f。这个结果在寄存器分配里非常有用。如果一个变量在某个程序点上不活跃说明它之后不会再被使用那么它占用的寄存器可以被其他变量复用。3.4 这个分析在真实编译器里的位置寄存器分配是活跃变量分析最经典的应用场景之一。现代编译器里静态单赋值形式SSA出现后活跃变量分析的形式会有所变化但思想没有变。另外死代码删除也可以借助活跃变量信息如果一条赋值语句的左侧变量在赋值之后不再活跃并且这条赋值没有副作用就可以安全删除。实现时要注意活跃变量分析是后向分析遍历顺序一般用逆后序。如果顺序不对迭代收敛会变慢但不会错。还有一个细节是函数调用边如果分析的是整个程序调用一个函数后哪些变量仍会被使用这涉及跨过程分析大部分入门课程先从过程内分析讲起我自己做实验时也建议先把单函数的分析写对再想怎么扩展。经验写后向分析时最容易写错的是把 def 集合用块内定义的变量和从入口流出的变量混淆。建议每写完一个块的 use/def先照着 3.2 的小例子手推一遍再写代码。4. 第三个经典应用可用表达式分析4.1 从公共子表达式消除说起可用表达式分析问的问题是在程序点 p表达式 x y 的值是否已经在所有到达 p 的路径上计算过而且从计算之后到现在x 和 y 都没有被重新赋值如果答案是肯定的就称 x y 在 p 点是可用的。这个分析是编译器做公共子表达式消除CSE的地基。比如一个表达式在循环里重复出现如果它在进入循环前已经算过而且期间相关变量没变就可以把重复计算替换成复用省掉一次运算。举个例子程序里有B1: a b c B2: if (cond) d a b B3: else a e f B4: x a b我们希望知道 B4 里的a b能否直接用之前的结果。如果它可用就不用再算如果不可用就只能老老实实再算一次。4.2 必须分析所有路径都成立才算数和前面两个分析不同可用表达式是一个 must analysis。一个表达式要在某个点可用必须是所有能到达该点的路径都计算过它。只要有一条路径没有计算哪怕其他路径都计算了也不能说它可用否则把表达式替换成旧值就可能改变程序语义。正因为如此多条前驱路径汇合时可用表达式要取交集而不是并集IN[B] ∩ OUT[pred(B)] OUT[B] gen[B] ∪ (IN[B] − kill[B])gen[B]是块内新计算的表达式kill[B]是块内所有对变量赋值的操作所杀死的表达式——即那些包含被赋值变量的表达式。注意这里的包含是指语法上出现该变量例如a e f会杀死所有包含a的可用表达式。4.3 求交分析的一个致命初值陷阱取交集的分析初始化时不能简简单单把所有块的 OUT 设成空集。如果入口 OUT 设成空集和空集求交集所有块入口的可用表达式都永远是空集整个分析直接失效——不是不安全而是没有任何优化价值。对 must 分析来说要从全集所有出现在程序中的表达式出发让迭代过程不断把不满足条件的表达式筛掉最后剩下的才是真正在所有路径上都可用的。这一点和 may 分析正好相反may 分析从空集出发信息不断累积must 分析从全集出发信息不断被裁剪。为什么因为 may 分析只要存在即可空集起步不会漏掉候选must 分析要求所有如果从空集起步就当所有表达式都不可用虽然安全但等于没分析。所以初值不是拍脑袋定的是由交汇运算的性质决定的。经验凡是遇到用交集的向前/向后分析先问自己边界初值应该是什么。空集起步通常意味着什么都没算出来这往往是错的。4.4 一个带杀的手算例子回到 4.1 的例子。程序中的全部表达式是 {b c, a b, e f}。各块的 gen/kill基本块genkillB1{b c}∅b、c 未被重新定义也不会影响其他表达式B2{a b}∅B3{e f}{a b}因为给 a 赋值了B4∅∅这里只是使用 a b没有新的表达式产生从全集的 OUT[entry] {b c, a b, e f} 开始迭代IN[B1] {b c, a b, e f}OUT[B1] {b c}IN[B2] OUT[B1] {b c}OUT[B2] {b c, a b}IN[B3] OUT[B1] {b c}OUT[B3] {e f} ∪ ({b c} − {a b}) {b c, e f}IN[B4] OUT[B2] ∩ OUT[B3] {b c, a b} ∩ {b c, e f} {b c}所以到 B4 入口a b并不可用。原因很直观走 B3 这条路径时a被重新赋值成 e f原来的a b已经不具有相同含义了。如果编译器在这里还要做公共子表达式消除就必须先确认a没有在这条路径上被改过——现在结果告诉你不可以。5. 把三种分析放进同一套框架5.1 数据流分析框架四要素学完三个例子回头看它们其实长得非常像。每种数据流分析都可以用四个要素描述清楚方向、传递函数、交汇运算、初值。整理成表格分析任务方向交汇运算边界初值类型到达定值前向∪OUT[entry] ∅may活跃变量后向∪IN[exit] ∅may可用表达式前向∩OUT[entry] 全集must这个视角极其重要。因为在编译原理和程序分析的任何一本教材里数据流分析框架都会以统一的形式出现程序上的每个点是一个节点每个节点的状态属于一个有限集合组成的格lattice传递函数是格之间的单调函数交汇运算就是格上的 meet 或 join。一旦你接受了这个抽象再去看别的数据流分析比如常量传播、区间分析、指针分析会发现都是在填这四个要素。前三个例子是填空题的标准答案往后学的所有复杂分析都是变形题。5.2 为什么迭代算法一定会停下来一个很自然的疑问前面说从某个初值不断迭代凭什么最后会停在稳定状态直观原因是程序里的定义、变量、表达式都是有限个所以集合族有限。每次迭代交融运算要么向集合里加元素并集要么从集合里删元素交集单调地变化而集合不可能无限增大或无限减小所以最终必然达到一个固定点。更深一层是因为传递函数是单调的如果输入集合是另一个输入集合的子集或超集处理后的输出相应地保持包含关系。单调性保证了迭代不会来回震荡只会朝一个方向走。并用格的理论可以进一步区分最小不动点和最大不动点分别对应哪些分析这里先不展开。课程里后续会专门讲格理论和不动点定理你会发现那些看上去纯粹数学的内容用来解释数据流分析收敛性时意外地好用。我在学到这里时最大的感受是不要嫌弃理论抽象它能帮你判断一个自定义数据流分析能不能收敛、初值该填什么。5.3 框架视角下的工程实现从实现角度讲数据流分析框架的代码是可以复用得非常彻底。一个通用的迭代引擎只需要输入 CFG、方向和传递函数、交汇运算就能跑出结果。我自己实习时写过一个很小的静态分析玩具核心迭代循环就十几行for each block B: IN[B] OUT[B] 初始值 while (集合发生变化): for each block B (按方向决定的遍历顺序): if 前向: IN[B] meet(OUT[pred(B)]) OUT[B] transfer_B(IN[B]) else: OUT[B] meet(IN[succ(B)]) IN[B] transfer_B(OUT[B])不同分析之间的差异最后只落在三处初值、meet 函数、transfer 函数。所以当你理解了框架相当于一次性会写了三类分析器后面遇到新的分析需求也很容易判断能不能用同一套引擎跑。6. 从课堂到实战我踩过的几个坑6.1 课堂作业里最容易错的三个细节第一个坑是活跃变量的出口边界。后向分析的出口边界是IN[exit] ∅还是OUT[exit] ∅取决于你怎么定义 IN/OUT 的语义。很多教材用IN[B]表示基本块入口处的信息对后向分析来说程序出口处没有后继所以IN[exit]初始化为空集。如果你实现的是OUT[exit]的语义情况就反过来。这个不统一非常容易造成困惑我的建议是写代码前先明确自己用的符号体系并在单元测试里放一个单基本块的小程序验证。第二个坑是块的 use/def 切分。前面 3.2 已经讲过不再重复只补一句如果代码里用一个循环枚举块内所有语句来收集 use 和 def顺序必须是从后往前扫并且遇到定义时把该变量从 use 集合里移除遇到使用时加入 use 集合这样的实现最不容易出错。第三个坑是可用表达式的 kill 集合。很多人只考虑显式赋值忘了表达式本身的变化。比如a b c这一句除了产生b c这个表达式之外还会 kill 掉所有包含a的表达式。因为a的值变了之前缓存的表达式再用到a就不作数了。我在实现时单独写了一个函数用来枚举一个语句定义的所有变量再根据这个变量集合去表达式全集里找需要被 kill 的表达式。6.2 工程实现里的三个提醒第一集合操作建议直接用位向量。三个分析里的元素分别是定义编号、变量编号、表达式编号数量通常不大位向量加按位与或、按位与非速度极快。数据流分析要跑很多轮如果每次都用哈希集合做运算CFG 大的时候性能立刻露馅。第二CFG 的构造质量决定了分析质量。循环、异常处理、return 语句都会产生额外的控制流边边少了分析会不精确边多了则可能慢。我实习时处理过带 try-catch 的代码异常边如果全部忽略活跃变量分析会得到变量在 catch 块里可能被使用的错误结论影响后续优化的正确性。课程先从过程内、无异常的简单 CFG 入手但你要知道工程里还有这些复杂度。第三迭代顺序可以优化。前向分析通常按拓扑序遍历基本块有循环时配合后续遍历后向分析用逆后序。顺序不好只会多几次迭代不会算错但大数据量时可能慢一个量级。6.3 怎么把这些分析串起来用这三个分析不是孤立的它们经常会出现在同一条优化流水线里。比如先做可用表达式分析找出公共子表达式再做到达定值分析确认赋值关系最后用活跃变量分析清理死代码。每一步的输出都是下一步的输入而所有分析又都共享同一套 CFG 和迭代框架。我自己折腾完这三个应用后最大的收获是理解了程序状态在静态分析里不是具体值而是一个格上的抽象信息。只要分析的信息足够保守优化就不会改坏程序只要信息足够精确优化就有用武之地。学数据流分析别光背公式拿一小段程序手推一遍再照着框架写个迭代引擎比看十遍课件都管用。最后分享一个练手的小方法找一段自己写过的、带分支和循环的小函数分别计算到达定值、活跃变量和可用表达式然后用一个随机测试器生成各种 CFG 来检验结果是否符合枚举所有路径的朴素语义。我当初就是这么做的虽然一开始对不上但每次对不上其实都逼着我更精确地理解了一遍传递函数和交汇运算。这个过程比任何习题都值得做。