数据流分析

编译优化的前置分析层:在控制流图上迭代传播数据流事实直到收敛。同一套 gen/kill/meet/worklist 框架,换一个方向和 meet 运算,就求解 liveness、reaching defs、available expressions 三个不同问题。

概述

编译器要知道"在程序的每一点,哪些变量正在被使用、哪些定义能到达这里、哪些表达式已经被计算过"——这些信息不能从单条指令得出,必须在整个控制流上传播。⁠数据流分析(data flow analysis) 就是在一个程序的控制流图(CFG)上,迭代传播数据流事实,直到所有点都收敛。

把这件事抽象成统一框架⁠(Kildall, 1973)的做法,让同一套迭代算法通过换"方向""meet 运算""传递函数"就能求解多类分析。这篇讲这个统一框架,然后展开三个最核心的实例:reaching definitions、liveness、available expressions——它们也是 经典优化 的直接前置知识。

统一框架

数据流分析的四个组件:

• may 分析⁠(∪):问"有可能是什么"——过近似,宁可多报不少报。reaching definitions 是 may:一个定义"可能"到达某点。
• must 分析⁠(∩):问"一定是什么"——欠近似,宁可不报不错报。available expressions 是 must:一个表达式"一定"已被计算过。

传递函数总写成一式:out[B] = gen[B] ∪ (in[B] - kill[B])(或 ∩ 替代 ∪,取决于 meet)。gen 是本节点"产生"的新事实,kill 是本节点"作废"的旧事实。

迭代求解:worklist 算法

对整个 CFG 反复扫描,直到稳定(不动点):

for each block B: out[B] = ∅ (或 top)
worklist = all blocks
while worklist not empty:
    B = worklist.pop()
    in[B] = meet(out[predecessors of B])
    old_out = out[B]
    out[B] = gen[B] ∪ (in[B] - kill[B])     ← 传递函数
    if out[B] changed:
        worklist.push(successors of B)        ← 只传播变化

终止性由两个条件保证:⁠格(lattice)高度有限⁠(事实集合有最大元素)且传递函数单调⁠(新 in → 新 out 不会小于旧的)——不动点定理。对工程上的 CFG,收敛很快(通常 3–5 轮)。

worklist 的排序影响收敛速度——先处理前驱已更新的节点(用 CFG 拓扑序近似)比随机更高效。

三大经典分析

Reaching Definitions (前向, may, ∪)

问题⁠:在程序点 p,有哪些赋值(definition)可能未被后续赋值覆盖而到达 p?

gen[B]:  本块中最后赋值给变量 x 的语句 (早的被后面的覆盖)
kill[B]: 所有在其他地方对 x 的赋值, 被本块的新赋值"杀死"

构造 use-def 链的基础——SSA 形式 出现后,reaching definitions 在 SSA IR 上变成稀疏的、不再需要迭代求解;但在常规 IR 上仍是必需。

Liveness (后向, may, ∪)

问题⁠:在程序点 p,变量 x 的值是否会在未来被使用(在下次定义之前)?

方向改为 backward:从出口向前驱传播
gen[B]:  本块中被"使用"但本次使用前未被本块"重新定义"的变量
kill[B]: 本块中被"重新定义"但本次定义前未被本块"使用"的变量 (新值覆盖旧值)

活度分析直接决定寄存器分配:⁠两个变量不同时活跃就可以共享同一寄存器⁠(见 寄存器分配)。这是编译优化里做的最频繁的分析。

Available Expressions (前向, must, ∩)

问题⁠:在程序点 p,表达式 x + y 是否一定已被计算过且 x 和 y 都没被重新赋值?

gen[B]:  本块中计算的表达式 (且之后 x/y 未被重定义)
kill[B]: 所有含 x 或 y 的表达式, 在本块中对 x 或 y 有赋值后被作废
meet:   ∩ (must)——入点的可用表达式 = 所有前驱出点的交集

available expressions 的信息直接用于 CSE(公共子表达式消除)——如果 x + y 在当前点可用,就直接用上次的结果而不重算。

MOP vs MFP:理想解和不动点解之间的差距

• MOP(Meet Over all Paths):对程序点 p,收集"所有可能路径到达 p 时携带的事实",再对这些事实做 meet。这是理想解。
• MFP(Maximal Fixed Point):迭代不动点算法得到的解。MFP ≤ MOP(在格序意义上,MFP 可能更保守)。

对于可分配(distributive)的传递函数⁠——即 f(a meet b) == f(a) meet f(b) 的函数——MFP = MOP,不动点就是理想解。reaching definitions 和 liveness 的传递函数都是可分配的;constant propagation 的传递函数不是可分配的,所以 MFP 比 MOP 更保守。

SSA 下的稀疏数据流

整个迭代不动点框架在 SSA 形式 下大幅简化:

• 每个变量只定义一次 → reaching definition 退化为"这个使用的定义在哪儿"(直接 def-use 链,不用分析)。
• liveness 可以在 def-use 图上做——每个定义点能到达的所有使用点就是其 live range,不再需要在整个 CFG 上迭代。
• 很多"传播事实到整个 CFG"的 pass 在 SSA 退化为"在 dominator tree 上单遍传播"。

这就是 SSA 被叫"稀疏分析"的原因——数据流事实只附着在 def 和 use 点上,而不是 CFG 的每一条边上。

参考

• Kildall (1973): "A Unified Approach to Global Program Optimization" — 数据流分析的统一框架
• Dragon Book: Chapter 9, Machine-Independent Optimizations — 含完整的 gen/kill 表和不动点算法
• Cooper/Torczon: "Engineering a Compiler", Chapters 8–10

Keywords: data flow analysis, gen/kill, meet operator, forward/backward, may/must, reaching definitions, liveness, available expressions, fixed-point iteration, worklist algorithm, lattice, monotonicity, MOP, MFP, distributive function, sparse analysis, SSA