数据流分析

数据流分析为程序点建立事实，例如某次赋值可能到达哪里、一个值之后是否还会使用、某表达式是否在所有路径上已算过。它把执行路径压缩为可计算的抽象信息，并在控制流图 CFG 上传播。

结果应当保守地服务用途：用于删除代码的证明不能漏掉潜在行为，用于报告可能错误的分析则可以接受一定误报。保守不等于随便猜测，而是明确抽象结果与真实执行的包含关系。

从分支汇合理解 may 与 must

若问 x 可能来自哪次定义，就合并两条路径的候选；若问表达式 a+b 是否必然已计算，则两条路径都要提供该事实。对经典集合分析，前者常用并集，后者常用交集。

但 may/must 并不要求所有抽象域都简单用集合并交。格的偏序、top/bottom 与 join/meet 命名也会随约定变化，应先给出含义，再写公式。

统一框架需要五项定义

Gen/Kill 是许多位向量分析的便利形式，不是所有传递函数的唯一形式。即使用交集汇合的 must 分析，也不意味着要把传递函数内部的 gen ∪ ... 改成交集。

到达定义：前向 may 分析

定义 d 到达点 p，表示存在一条从 d 到 p 的路径，其间没有重新定义同一个变量。给每条赋值独立编号，而不是只记录变量名。

IN[B] = ∪ OUT[P]，P 遍历 B 的前驱。

OUT[B] = GEN[B] ∪ (IN[B] − KILL[B])。

GEN 包含块内能存活到出口的定义；KILL 包含被本块赋值覆盖的同变量其他定义。若块内依次 d1: x=1; d2: x=2，d1 不在出口 GEN 中，d2 在其中。

入口通常还要建模参数或外部初值的定义；教学模型若以空集开始，应说明这些不在分析范围。SSA 的标量使用直接关联唯一静态定义，但内存中的别名写入仍然需要单独分析。

活跃变量：后向 may 分析

一个值在点 p 活跃，表示存在后续路径先使用该值、再重新定义它。因为问题看未来，所以从后继向前传播。

OUT[B] = ∪ IN[S]，S 遍历 B 的后继。

IN[B] = USE[B] ∪ (OUT[B] − DEF[B])。

USE 是块内在首次定义前使用的变量；DEF 是块内定义的变量，⁠不要求该定义之前从未使用过⁠。

例如块 x=x+1; y=x; return y，USE={x}、DEF={x,y}。出口 OUT=∅ 时，入口 IN={x}。x 同时存在于 USE 与 DEF 完全合理：进入块的旧 x 需要用于第一条指令，块内也产生了一个新 x。

循环会让活跃信息跨回边传播。一个值的活跃范围是相关 CFG 路径上的程序点集合，不是把源码中的定义行到最后使用行简单连成直线。

可用表达式：前向 must 分析

表达式 e 在 p 可用，表示每条进入 p 的相关路径都计算过 e，并且之后没有修改其操作数。纯标量模型下：

IN[B] = ∩ OUT[P]。

OUT[B] = GEN[B] ∪ (IN[B] − KILL[B])。

注意 x=x+y 并不会让基于新 x 的 x+y 在出口可用：右侧计算使用旧 x，而赋值改变了 x。构造 GEN 时必须考虑块内后续赋值及该语句自身定义。

入口通常为空，其他可达块可从表达式全集开始向下收缩。不可达块和无前驱节点需要明确处理，不能随便对空集合族取交集后把假事实传播出去。

Worklist：只重新计算受到影响的邻居

以前向分析为例，初始化边界和各块状态，把待处理块入队；取出 B，重新合并前驱输出并应用传递函数；若 OUT 改变，将后继入队。后向分析则在 IN 改变时通知前驱。

在有限高度的格上，以正确初值进行单调迭代可终止。仅“有最大元素”不意味着高度有限；无限高度的区间域等可能需要 widening。轮数受 CFG、循环和域影响，没有固定三到五轮保证。Clang 数据流分析介绍

循环中的到达定义：第一次经过头部还没有全部答案

只分析变量 x 的两个定义：入口 E 执行 d0：x=0，循环体 B 执行 d1：x=x+1。循环头 H 可以进入 B，也可以到出口 X；B 再回到 H。条件和其他变量不在本模型的定义集合内。

第一次从 E 到 H 时，只知道 d0。扫描 B 后发现 d1；把它沿回边送到 H，H 才知道 x 也可能来自上一轮的 d1。这里 d1 是一条静态赋值语句的身份⁠，并不为每次动态循环执行生成无限个定义编号。

下面实现 worklist。状态采用定义集合的包含序，所有块从空集开始；入口没有前驱，由 GEN 产生 d0。所有节点都可达，因此这里不额外处理不可达输入。

from collections import deque

succ = {"E": ["H"], "H": ["B", "X"], "B": ["H"], "X": []}
pred = {b: [p for p in succ if b in succ[p]] for b in succ}
gen = {"E": {"d0"}, "H": set(), "B": {"d1"}, "X": set()}
kill = {"E": {"d1"}, "H": set(), "B": {"d0"}, "X": set()}


def solve(order):
    out = {b: set() for b in succ}
    work = deque(order)
    queued = set(order)
    history = []
    while work:
        b = work.popleft()
        queued.remove(b)
        incoming = set().union(*(out[p] for p in pred[b]))
        new = gen[b] | (incoming - kill[b])
        if new != out[b]:
            out[b] = new
            history.append((b, tuple(sorted(new))))
            for nxt in succ[b]:
                if nxt not in queued:
                    work.append(nxt)
                    queued.add(nxt)
    return out, history


expected = {"E": {"d0"}, "H": {"d0", "d1"}, "B": {"d1"}, "X": {"d0", "d1"}}
out, history = solve(["E", "H", "B", "X"])
assert out == expected
assert [v for b, v in history if b == "H"] == [("d0",), ("d0", "d1")]
assert solve(["X", "B", "H", "E"])[0] == expected
# 不仅与预期对照，还检查最终每个块都满足原方程。
for b in succ:
    incoming = set().union(*(out[p] for p in pred[b]))
    assert out[b] == gen[b] | (incoming - kill[b])

工作队列顺序改变中间过程，但在这个有限、单调的框架与相同边界条件下，最终解相同。若只遍历 CFG 一次，H 可能永远看不到回边；若发现任何节点未改变就停止，也可能遗漏队列中其他节点带来的新信息。

回边上的事实，什么时候才能传回出口？

下面的按钮不是规定顺序的课程步骤，而是待处理集合里的真实分析任务。可以先处理出口，让它暂时得到空集；入口或回边随后产生新事实时，出口仍会经由后继重新入队。一次不变只说明该次计算没有新增信息，全局停止条件是队列为空。模型中的 d1 始终是一条静态赋值身份。

$$\mathrm{IN}[B]=\bigcup _{P\in \mathrm{pred}(B)}\mathrm{OUT}[P],\mathrm{OUT}[B]=\mathrm{GEN}[B]\cup (\mathrm{IN}[B]\setminus \mathrm{KILL}[B])$$

不动点与按路径求解：哪里损失精度

MOP 先沿各条 CFG 路径变换再汇合；迭代方程则会在中途汇合路径，再继续变换。在传递函数对汇合可分配等条件下，两者一致；否则提前合并可能丢掉关联信息。

例如两条路径分别得到 (x=1,y=2) 和 (x=2,y=1)，随后计算 z=x+y。逐路径计算都得 3；非关系常量传播先汇合时把 x、y 都标成非常量，就可能推不出 z=3。保留变量间关系的抽象域可以改善精度，代价更高。

MOP 也通常遍历 CFG 中的语法路径，其中可能包含实际上无法同时满足条件的路径，所以不能直接称作真实程序语义的完美解。MFP 与 MOP 的大小方向依赖采用的格序，不应脱离约定记一个不等号。

丢掉相关性以后，不能再把所有组合都当作真实路径

把前面的两条路径直接写成集合，精确路径状态为 {(1,2),(2,1)}；分别保留 x、y 的可能值后，两者都变成 {1,2}。之后再做笛卡尔积，会额外引入 (1,1) 与 (2,2)，从而得到并不真实存在的和 2、4。

paths = {(1, 2), (2, 1)}
xs, ys = {x for x, y in paths}, {y for x, y in paths}
precise = {x + y for x, y in paths}
nonrelational = {x + y for x in xs for y in ys}
assert precise == {3}
assert nonrelational == {2, 3, 4}
assert precise <= nonrelational

非关系结果仍包含真实结果，因此可以保守地说“z 可能属于 {2,3,4}”，却不能证明 z 恒为 3。这个精度损失来自抽象状态没有保存配对关系；再增加几轮 worklist 也恢复不了已经丢弃的信息。要改善，需改变抽象域、延迟汇合或利用路径条件，而不只是反复运行同一方程。

分别记住 x、y，丢掉了什么？

将具体路径画成二维坐标中的点，可以准确定位“相关性丢失”。分别投影到 x、y 轴后再组合，真实的两点可能扩成四点；多出来的点不是新发现的执行路径，而是抽象允许的额外状态。修改第二条路径，还能看到什么时候不会产生额外组合。重复相同迭代不能重新找回已经丢失的配对关系。

$$R\subseteq {\pi }_x(R)\times {\pi }_y(R)$$

SSA 与稀疏分析

SSA 使标量 def-use 显式化，很多事实可以沿相关值传播，减少在无关 CFG 边上的工作。但 φ 输入与前驱边有关，循环仍可能需要不动点，内存仍有别名和副作用。SSA 不是“所有分析退化为支配树单遍遍历”的保证。

速查

相关章节：经典优化、寄存器分配、SSA。

参考

• Clang：Data Flow Analysis。
• LLVM 分析与变换 Pass。

Keywords: dataflow, CFG, may, must, gen, kill, liveness, reaching definitions, available expressions, fixed point, MOP