企业官网建设流程全解析

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 的所有定值就全部失效。

对基本块 B，gen[B] 是块内所有"能存活到块尾"的定值，也就是在块内没有被后续覆盖的定值。kill[B] 是块内每条语句 kill 的并集，凡是在 B 里被赋过值的变量，它在全程序中的所有定值都会被 B 杀掉。

这里有个新手容易纠结的点：gen 和 kill 可以有重叠。比如块内连续两条x = 1; x = 2，gen 只包含第二个定值，kill 却包含程序里所有对 x 的定值，包括第一个。传递函数 OUT = gen ∪ (IN − kill) 之所以这样写，就是为了保证块内"存活"的定值不会被自己的 kill 误伤。

3.3 手算一个完整例子

用经典的分支汇合结构来看，程序如下：

+-------+ | entry | +-------+ | v +--------------------------+ | B1: d1: x = 5 | +--------------------------+ | cond?| / \ v v +-------------+ +-------------+ | B2: d2: y=x | | B3: d3:x=2 | +-------------+ +-------------+ \ / \ / vv +--------------------------+ | B4: d4: z = x + y | +--------------------------+ | v +-------+ | exit | +-------+

每个块的 gen、kill 如下：

初始化入口 OUT[entry] = ∅，其余各块 OUT 也从 ∅ 开始。迭代时 B 的 IN 等于所有前驱 OUT 的并集，然后再算 OUT = gen ∪ (IN − kill)。

• B1：IN = ∅，OUT = {d1}
• B2：IN = {d1}，OUT = {d1, d2}
• B3：IN = {d1}，OUT = {d3} （d1 被 kill 掉）
• B4：IN = {d1, d2} ∪ {d3} = {d1, d2, d3}，OUT = {d1, d2, d3, d4}

所以在 B4 入口，x 可能来自 d1 也可能来自 d3，y 来自 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 如下：

从 B4 倒推：

• B4：OUT = IN[exit] = ∅，IN = {x, y} ∪ (∅ − {z}) = {x, y}
• B3：OUT = IN[B4] = {x, y}，IN = ∅ ∪ ({x, y} − {x}) = {y}
• B2：OUT = IN[B3] ∪ IN[B4] = {y} ∪ {x, y} = {x, y}，IN = {x} ∪ ({x, y} − {y}) = {x}
• B1：OUT = IN[B2] ∪ IN[B3] = {x} ∪ {y} = {x, y}，IN = ∅ ∪ ({x, y} − {x}) = {y}

结论很反直觉：程序入口处活跃的只有 y，x 反而在入口处不活跃。原因是 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 = b+c | | e = m+n | +---------+ +---------+ \ / v v +-----------------------------+ | B4: f = b + c | | g = m + n | +-----------------------------+

程序里的表达式全集 U = {b+c, m+n}。初始化 OUT[B2] = OUT[B3] = OUT[B4] = U，OUT[entry] = ∅。

• B1：IN = ∅，OUT = {b+c}
• B2：IN = {b+c}，OUT = {b+c}
• B3：IN = {b+c}，OUT = {b+c, m+n}
• B4：IN = OUT[B2] ∩ OUT[B3] = {b+c} ∩ {b+c, m+n} = {b+c}，OUT = {b+c, m+n}

于是 B4 入口处：b+c 可用，因为两条路径都算过它；m+n 不可用，因为走 B2 那条路径时从没算过 m+n。所以f = b+c可以复用之前的结果，g = m+n必须老老实实重新计算。这个例子直观展示了交集在分支汇合时如何做"全票通过"的裁断。

kill 集合的细节也要注意。可用表达式的 kill 不是杀掉一个表达式，而是杀掉所有包含被赋值变量的表达式。比如块内执行c = ...，那么所有包含 c 的表达式如b+c都失效。这和到达定值的"杀掉同名变量的定值"思路类似，但作用范围是整个表达式集合，初学时容易忘。

5.4 公共子表达式消除

可用表达式的经典应用就是公共子表达式消除（CSE）：如果表达式在某个程序点可用，并且该点的语句正好是求这个表达式，就把这次求值替换成之前保存的结果。

以 B4 为例，f = b+c因为 b+c 可用，在语义上等价于f = 上次算 b+c 的结果，编译器可以插入临时变量复用；如果g = m+n在 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 挪到 exit：

OUT[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 一张表对齐三个分析

这张表值得贴在手边。面试、笔试、做课程作业时，只要把这四列背清楚，基本不会犯方向错误或初始化错误。

工程实现上还有两个实用建议。第一，不要只做一轮复杂的两层循环就交差，至少要打印每一轮的 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 决定集合运算"这两条线牢牢记住，后面每节课都可以用这套框架快速归位。