1. 数据流分析在做什么
一句话总结： 数据流分析沿控制流图传播「程序点上成立的事实」，直到所有事实不再变化，为优化提供依据。
优化器需要回答一系列全局问题：某个变量在这一点上是否还被用到？某个表达式的值在这里是不是常量？这条赋值能不能被消除？这些问题的共同点是——答案取决于控制流可达的整片区域，而不是单条指令。数据流分析就是回答这类问题的统一框架：把「事实」建模成集合，把指令的语义建模成集合的传递函数，沿控制流图反复传播直到不动点。
# 数据流分析的统一骨架 (正向, 并集合并)
def solve_forward(cfg, transfer, gen, kill, init, all_facts):
IN = {n: set() for n in cfg} # 块入口的事实
OUT = {n: set() for n in cfg} # 块出口的事实
for n in cfg:
OUT[n] = set(init)
changed = True
while changed:
changed = False
for n in cfg:
merged = set()
for p in preds(cfg, n): # 汇合前驱
merged |= OUT[p]
IN[n] = merged
new_out = transfer(gen[n], kill[n], IN[n], all_facts)
if new_out != OUT[n]:
OUT[n] = new_out
changed = True
return IN, OUT
def preds(cfg, n):
return [p for p, succs in cfg.items() if n in succs]
四个要素决定了一个数据流问题：方向（前向/后向）、合并方式（并集/交集）、传递函数（gen/kill 或更复杂的映射）、初始值（空集或全集）。把这四个旋钮调好，剩下的就是套模板。理解了这套模板，再看寄存器分配里的活跃性分析、循环优化里的归纳变量识别、SSA 构造中的支配边界，会发现它们全是同一个框架的不同实例。
| 问题 | 方向 | 合并 | 事实含义 |
|---|---|---|---|
| 到达定值 | 前向 | 并集 | 哪些赋值可能到达此处 |
| 活跃变量 | 后向 | 并集 | 此处之后还会被读的变量 |
| 可用表达式 | 前向 | 交集 | 此处之前必已计算且未被破坏 |
| 常量传播 | 前向 | 交集 | 此处该变量必为某常量 |
2. 格、偏序与单调性
一句话总结： 数据流分析的收敛性由格的有限高度与传递函数的单调性共同保证，二者缺一不可。
把「事实」组织成格（lattice）是数据流分析的理论基础。一个格由偏序集 (L, ⊑) 构成，任意两个元素都有上确界（join，记 ⊔）与下确界（meet，记 ⊓）。到达定值用幂集格：元素是「定值集合」，偏序是子集关系，join 是并集；常量传播用平坦格：每个变量取值来自 {⊤, c1, c2, ..., ⊥}，⊤ 表示「还不确定」，⊥ 表示「已确认不是常量」，从 ⊤ 向下走代表信息变精确。
# 常量传播的平坦格 (flat lattice)
TOP, BOTTOM = "TOP", "BOTTOM"
def join(a, b):
if a == b: return a # 相同: 保持
if a == TOP: return b # TOP 与任何值 join 得该值
if b == TOP: return a
return BOTTOM # 两个不同常量: 退化为未知
print(join(TOP, 5), join(5, 5), join(5, 7), join(BOTTOM, 5))
# TOP与5 join -> 5; 5与5 -> 5; 5与7 -> BOTTOM; BOTTOM与5 -> BOTTOM
def transfer_const(state, stmt):
"""state: 变量 -> 常量格元素; 返回执行 stmt 后的新状态."""
out = dict(state)
if stmt[0] == "const": # x = 常量
out[stmt[1]] = stmt[2]
elif stmt[0] == "assign": # x = y op z
_, x, op, y, z = stmt
a = state.get(y, BOTTOM) if not isinstance(y, int) else y
b = state.get(z, BOTTOM) if not isinstance(z, int) else z
out[x] = eval_binop(op, a, b)
else: # 有副作用: 全部降级
out = {k: BOTTOM for k in state}
return out
def eval_binop(op, a, b):
if a == BOTTOM or b == BOTTOM: return BOTTOM
if a == TOP or b == TOP: return TOP
return {"+": a + b, "-": a - b, "*": a * b}[op]
单调性是收敛的关键。传递函数 f 必须满足 x ⊑ y ⟹ f(x) ⊑ f(y)：更精确的输入只能得到不更差的结果。结合格的高度有限（幂集格高度等于变量数，平坦格高度为 3），迭代序列 ⊥ ⊑ f(⊥) ⊑ f²(⊥) ⊑ ... 必然在有限步内稳定。若传递函数非单调，或格有无限升链，迭代就可能永不收敛——这是写自定义分析时最容易犯的错。
| 概念 | 含义 | 在本框架中的角色 |
|---|---|---|
偏序 ⊑ | 信息精确度的比较 | 定义「更精确」 |
上确界 ⊔ | 两个事实的最小公共上界 | 控制流汇合处的合并 |
最小元 ⊥ | 信息最少（乐观起点） | 迭代初值 |
| 单调函数 | 保序映射 | 保证收敛 |
| 有限高度 | 无无限升链 | 保证有限步收敛 |
3. 到达定值与活跃变量
一句话总结： 到达定值向前传播「哪些赋值可能到达」，活跃变量向后传播「哪些变量还将被使用」，二者是数据流框架最经典的两个实例。
到达定值（reaching definitions）问的是：在程序点 p，变量 x 的当前值可能来自哪些赋值语句？它把每条赋值语句编号作为事实元素，正向传播，在控制流汇合处取并集，遇到对 x 的新赋值就把所有旧的 x 定值「杀死」。它是常量传播与定值-使用链（def-use chain）的基础。
def reaching_defs(cfg, defs_of, uses_of, all_defs):
"""defs_of[n]: 块 n 中定义的 (变量, 定值编号); uses_of[n]: 块 n 中使用的变量."""
IN = {n: set() for n in cfg}
OUT = {n: set() for n in cfg}
changed = True
while changed:
changed = False
for n in cfg:
merged = set()
for p in preds(cfg, n):
merged |= OUT[p]
IN[n] = merged
gen = {d for _, d in defs_of[n]}
killed_vars = {v for v, _ in defs_of[n]}
kill = {d for d in all_defs
if any(all_defs[d] == v for v in killed_vars)}
new_out = gen | (IN[n] - kill)
if new_out != OUT[n]:
OUT[n], changed = new_out, True
return IN, OUT
all_defs = {1: "x", 2: "y", 3: "x", 4: "z"}
cfg = {0: [1], 1: [2], 2: [3, 4], 3: [4], 4: []}
defs_of = {0: [], 1: [("x", 1)], 2: [("y", 2)], 3: [("x", 3)], 4: [("z", 4)]}
uses_of = {0: [], 1: [], 2: ["x"], 3: [], 4: ["x", "y", "z"]}
for n, s in zip(*reaching_defs(cfg, defs_of, uses_of, all_defs)):
print(n, sorted(s))
活跃变量（liveness）方向相反：变量 x 在点 p 活跃，当且仅当存在一条从 p 出发的路径，在 x 被重新定义之前读到了 x。它后向传播，方程是 live_in = use ∪ (live_out − def)。活跃性分析直接服务于寄存器分配（冲突图）与死代码消除（定值后不活跃即为死代码），是优化后端出现频率最高的分析。
| 对比项 | 到达定值 | 活跃变量 |
|---|---|---|
| 方向 | 前向 | 后向 |
| 事实单位 | 赋值语句编号 | 变量名 |
| 合并 | 并集 | 并集 |
| 传递 | gen ∪ (in − kill) | use ∪ (out − def) |
| 主要用途 | 常量传播、def-use 链 | 寄存器分配、死代码消除 |
两者看似对称，实则语义不同：到达定值关心「值从哪来」，活跃变量关心「值还要到哪去」。一个常见的误解是「变量被定义了但从未使用」等价于「变量不活跃」——不活跃的定义更弱，它只要求「从这里出发的每条路径上，读取都发生在重定义之后」，一个死变量在它被定义的那条指令之后确实不活跃，但在定义点之前可能仍是活跃的（因为别处有读取）。
4. 可用表达式与常量传播
一句话总结： 可用表达式用交集合并表达「必经」语义，常量传播在格上做前向求值，两者共同支撑公共子表达式消除与常量折叠。
可用表达式（available expressions）问的是：在点 p，表达式 x + y 是否在之前的所有路径上都被计算过，且其操作数此后未被改写？注意「所有路径」——这要求合并用交集而非并集。这是数据流框架里「must analysis」（必然成立）与「may analysis」（可能成立）的分水岭：may 分析初值取空集、合并取并集；must 分析初值取全集、合并取交集。
def available_exprs(cfg, gen_of, kill_of, all_exprs):
IN = {n: set(all_exprs) for n in cfg} # must 分析: 初值取全集
OUT = {n: set(all_exprs) for n in cfg}
changed = True
while changed:
changed = False
for n in cfg:
if not preds(cfg, n):
merged = set() # 入口块没有前驱, 无可用表达式
else:
merged = set(all_exprs)
for p in preds(cfg, n):
merged &= OUT[p] # must: 交集
IN[n] = merged
new_out = gen_of[n] | (IN[n] - kill_of[n])
if new_out != OUT[n]:
OUT[n], changed = new_out, True
return IN, OUT
# 一个表达式在点 p 可用, 说明可以复用它已算出的值
exprs = {"t1", "t2", "t3"}
cfg = {0: [1], 1: [2, 3], 2: [4], 3: [4], 4: []}
gen_of = {0: set(), 1: {"t1"}, 2: {"t2"}, 3: set(), 4: set()}
kill_of = {0: set(), 1: set(), 2: set(), 3: {"t1"}, 4: set()}
IN, OUT = available_exprs(cfg, gen_of, kill_of, exprs)
print("块4 入口可用:", sorted(IN[4])) # t1 在分支 3 被 kill, 故不可用
常量传播（constant propagation）是另一种形态：它不使用集合，而是用变量到格元素的映射，逐条指令做前向求值。若某变量的格元素收敛为具体常量，就可以在后续使用处直接替换，再触发常量折叠与不可达分支消除。把常量传播与分支可达性结合，就是经典的稀疏条件常量传播（SCCP）：它维护「某条边是否可达」，不可达的边不参与合并，从而比朴素常量传播更精确。
def reachable_edges(cfg, cond_const, entry):
"""cond_const[block] 为分支条件已知的常量, None 表示未知."""
seen, work = set(), [entry]
while work:
n = work.pop()
if n in seen: continue
seen.add(n)
c, succs = cond_const.get(n), cfg[n]
if c is True: work.append(succs[0]) # 只走真分支
elif c is False: work.append(succs[-1]) # 只走假分支
else: work.extend(succs) # 两条都走
return seen
print(reachable_edges({0: [1, 2], 1: [3], 2: [3], 3: []}, {0: True}, 0))
# {0, 1, 3}: 分支 2 因条件恒真而不可达
| 分析类型 | 合并算子 | 初值 | 语义 |
|---|---|---|---|
| may（可能） | 并集 | 空集 | 存在一条路径成立 |
| must（必然） | 交集 | 全集 | 所有路径都成立 |
| 常量传播 | 格 join | 每变量 ⊤ | 所有路径都取同一常量 |
may 与 must 的选择直接决定优化的正确性方向：用 may 分析的结果做「必然成立」的假设，会生成错误的代码；反之用 must 分析做「可能成立」的假设，只会错过优化机会，是安全的。工程上宁可保守也不要激进，因为漏优化只是性能损失，错优化是正确性事故。
5. 支配树与 SSA 稀疏分析
一句话总结： 支配树刻画「哪个块必经哪个块」，SSA 形式让每个变量只有一个定义点，使数据流事实可以挂在定义点上做稀疏传播。
支配（dominance）是控制流图的骨架概念：若从入口到块 n 的每条路径都经过块 d，则称 d 支配 n。把每个块连到它的直接支配者（idom），得到一棵支配树。支配信息用途极广：识别循环（回边的头必然支配尾）、计算支配边界（放置 phi 节点的位置）、做代码移动的安全性判定。
def compute_idom(cfg, entry):
"""迭代求直接支配者: 用交集算法, 朴素但直观."""
dom = {n: set(cfg) for n in cfg}
dom[entry] = {entry}
changed = True
while changed:
changed = False
for n in cfg:
if n == entry: continue
ps = preds(cfg, n)
new = {n} | set.intersection(*(dom[p] for p in ps)) if ps else {n}
if new != dom[n]:
dom[n], changed = new, True
idom = {}
for n in cfg:
if n == entry: continue
strict = dom[n] - {n}
# 直接支配者: 严格支配者中不被其他严格支配者支配的那个
idom[n] = next(d for d in strict
if all(d == s or d in dom[s] for s in strict))
return idom
cfg = {0: [1], 1: [2, 3], 2: [4], 3: [4], 4: [1, 5], 5: []}
print(compute_idom(cfg, 0))
def dominance_frontier(cfg, idom, entry):
"""支配边界: 若 d 支配 n 的某个前驱但不严格支配 n, 则 n 在 d 的边界上."""
df = {n: set() for n in cfg}
for n in cfg:
ps = preds(cfg, n)
if len(ps) < 2: continue # 只有多前驱块才产生边界
for p in ps:
runner = p
while runner is not None and runner != idom.get(n):
df[runner].add(n)
runner = idom.get(runner)
return df
idom = compute_idom(cfg, 0)
print(dominance_frontier(cfg, idom, 0))
支配边界是 SSA 构造的钥匙：某个变量若在块 d 中被定义，且 d 的支配边界中存在块 n，那么 n 的入口就需要为这个变量插入 phi 节点。这解释了为什么 SSA 构造可以在近似线性时间内完成——不需要对每条边做数据流传播，只需要在支配边界这个稀疏的点集上插 phi。
稀疏分析是 SSA 带来的最大红利。传统数据流分析在每个基本块的入口出口都维护事实集合，事实数量与「块数 × 变量数」成正比；而在 SSA 形式下，每个变量只有唯一一个定义点，事实可以只挂在定义点上，沿着 def-use 链直接传播，复杂度降到与「定义数 + 使用数」成正比。基于 SSA 的稀疏分析把活跃性、常量传播、值编号等问题从「块级」提升到「定义级」，是现代编译器（LLVM、Go 编译器、HotSpot C2）的标准做法。
| 概念 | 定义 | 用途 |
|---|---|---|
| 支配 | 所有路径都经过 | 循环识别、安全性判定 |
| 直接支配者 | 最近的严格支配者 | 构造支配树 |
| 支配边界 | 支配关系的「失效边界」 | 确定 phi 插入点 |
| SSA 稀疏化 | 事实挂在定义点 | 降低分析复杂度 |
6. Worklist 算法
一句话总结： worklist 算法只把「结果发生变化」的节点重新入队，避免整图反复扫描，是数据流分析的工程标准实现。
教科书式的迭代算法每轮扫描所有基本块，绝大多数块的结果并不会变化，白白浪费。worklist 算法用一个待处理队列替代全量扫描：初始把所有块入队，每次取出一个块计算其输出，只有输出发生变化时才把它的后继（前向分析）入队。实践表明这能把迭代次数降低一个数量级，在大型函数上尤其明显。
from collections import deque
def worklist_forward(cfg, entry, transfer, init):
IN = {n: set() for n in cfg}
OUT = {n: dict(init) for n in cfg}
wl = deque(cfg.keys())
in_queue = set(cfg.keys())
while wl:
n = wl.popleft()
in_queue.discard(n)
merged = set()
for p in preds(cfg, n):
merged |= OUT[p]
IN[n] = merged
new_out = transfer(n, IN[n])
if new_out != OUT[n]:
OUT[n] = new_out
for s in cfg[n]: # 只把后继入队
if s not in in_queue:
wl.append(s)
in_queue.add(s)
return IN, OUT
def transfer(n, in_set):
# 示例: 到达定值风格的 gen/kill
return in_set | {n}
# 优先队列版本: 按逆后序处理能进一步减少迭代
def rpo(cfg, entry):
order, seen = [], set()
def dfs(n):
seen.add(n)
for s in cfg[n]:
if s not in seen: dfs(s)
order.append(n)
dfs(entry)
return order[::-1]
cfg = {0: [1], 1: [2, 3], 2: [4], 3: [4], 4: []}
print("逆后序:", rpo(cfg, 0))
worklist 的另一个常见优化是按逆后序（reverse postorder）初始化队列。逆后序保证一个块在被处理时，它在控制流上的大多数前驱都已经处理过，因此第一次处理往往就能得到接近最终的结果。对后向分析（活跃性）则使用后序或逆逆后序，原理相同。
| 实现方式 | 复杂度 | 特点 |
|---|---|---|
| 朴素全扫描 | O(块数 × 高度 × 块大小) | 实现最简单，常数大 |
| worklist | 同上但常数小得多 | 工程标准 |
| 逆后序初始化 | 减少首次迭代的无效重算 | 与 worklist 叠加 |
| SSA 稀疏 | 与定义数成正比 | 最快，需 SSA |
需要说明的是，数据流分析在最坏情况下的复杂度上界并不好看：以到达定值做位向量实现为例，复杂度是 O(块数² × 位数)。但实际程序的控制流图很少退化成最坏形态，配合 worklist 与逆后序，绝大多数真实函数的分析时间都在微秒级。真正拖慢编译的是超大型函数（自动生成的解析器、机器学习模型导出的代码），工程上靠函数大小阈值、分析预算与缓存来兜底。
7. 从分析到优化
一句话总结： 分析结果本身不是终点，把「事实」翻译成「变换」才是优化，而这中间隔着正确性与收益的权衡。
数据流分析的产物是一张「程序性质表」，把它变成优化需要三步：确认变换的前提条件、执行变换、验证变换未破坏后续分析依赖的事实。以公共子表达式消除为例，前提是「该表达式在此处可用」，变换是用前一次计算的结果替换本次计算，验证是要保证替换后该表达式的定值仍然可用。
def cse(block, available):
"""在块内做公共子表达式消除: 复用已计算过的表达式."""
table, out = {}, []
for stmt in block:
if stmt[0] == "assign" and stmt[2] in ("+", "-", "*"):
key = (stmt[2], stmt[3], stmt[4])
if key in table and key in available:
out.append(("copy", stmt[1], table[key])) # 复用
continue
table[key] = stmt[1]
out.append(stmt)
return out
print(cse([("assign", "a", "+", "x", "y"),
("assign", "b", "+", "x", "y")], {"+xy"}))
| 优化 | 依赖的分析 | 前提条件 |
|---|---|---|
| 常量折叠 | 常量传播 | 操作数均为已知常量 |
| 公共子表达式消除 | 可用表达式 | 表达式已计算且未被 kill |
| 死代码消除 | 活跃变量 | 定值后变量不活跃且无副作用 |
| 代码移动 | 支配树 | 目标位置支配所有使用点 |
| 循环不变量外提 | 循环识别 + 支配 | 计算与循环无关且安全 |
| 分支消除 | 常量传播 + 可达性 | 条件恒真/恒假 |
实践中最容易出问题的是分析结果的时效性：变换改变了控制流图或定值集合，此前算出的 IN/OUT 立刻作废。成熟的编译器把每个分析封装成独立对象，附上「失效通知」机制——任何 pass 修改了函数，依赖该函数的分析自动被标记为 stale，下次访问时重算。LLVM 的 AnalysisManager 与 PreservedAnalyses 就是这个机制的工业化实现：pass 声明自己保留了哪些分析，其余自动失效。这套设计避免了「改完还在用旧结果」这一类极其隐蔽的错误。
8. 总结
| 环节 | 要点 |
|---|---|
| 框架要素 | 方向、合并算子、传递函数、初值四要素 |
| 格与偏序 | 有限高度 + 单调函数保证收敛 |
| may 分析 | 初值空集、合并并集，语义是「可能成立」 |
| must 分析 | 初值全集、合并交集，语义是「必然成立」 |
| 到达定值 | 前向，回答「值从哪来」，支撑 def-use 链 |
| 活跃变量 | 后向，回答「值到哪去」，支撑寄存器分配 |
| 常量传播 | 平坦格上的前向求值，配合可达性做 SCCP |
| 支配树 | 循环识别与 phi 插入点计算的基础 |
| SSA 稀疏分析 | 事实挂在定义点，复杂度与定义数成正比 |
| worklist | 只重算变化的节点，逆后序初始化进一步提速 |
| 结果时效性 | 变换后分析失效，需显式失效通知机制 |
数据流分析是编译器优化的「公共基础设施」：它把「程序在某个点满足什么性质」变成可以机械计算的问题，让后续的常量传播、死代码消除、公共子表达式消除、寄存器分配都能建立在一个统一的抽象之上。掌握了框架的四要素与收敛性论证，再看任何一个陌生的分析，都能迅速判断它属于 may 还是 must、前向还是后向、格是什么、传递函数是否单调。下一篇进入一个更具体的优化战场——向量化与 SIMD，看看编译器如何把标量循环改造成一次处理多个数据的向量代码。
延伸阅读
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。