5.4 数据流分析：全局优化的望远镜

5.4 数据流分析：全局优化的望远镜

本节摘要：数据流分析在流图上求解"每个程序点知道什么"的问题：到达定值分析哪些定义能到达此处，活跃变量分析哪些值还会被用，可用表达式分析哪些计算不必重做。本节用主线语句参与的小流图完整跑一遍活跃变量分析，讲清前向/后向、不动点迭代两大机制，以及分析结论如何发放优化通行证。

阅读完本节，你应当能够：

1. 写出三大经典分析的方程组与边界条件
2. 在小流图上手工迭代求解活跃变量到不动点
3. 说明分析结果如何支撑死代码删除与公共子表达式消除
4. 解释保守近似"宁可少优化不可错优化"的原则

分析在问什么

全局优化每一步都卡在同一个问题上：在程序点 p，我知道什么？"这个变量的值后来还用吗"（活跃变量）、"这个定义能到这儿吗"（到达定值）、"这个表达式在这儿还成立吗"（可用表达式）。数据流分析就是流图上的方程组求解——每个块的入口出口各挂一个集合，方程描述集合如何沿控制流传播。

三大分析一次看全：

手工迭代：活跃变量分析

用主线语句所在的小流图实跑。方程组（后向分析，从出口往入口推）：

块出口活跃集 OUT = 所有后继块入口活跃集 IN 的并集
块入口活跃集 IN = USE 并上 (OUT 减去 DEF)
  USE：块内先引用后定值的变量（引用的是进入块之前的值）
  DEF：块内定值且之前未引用的变量

流图（4 块）：
B1: t1 = cvt_float(qty); t2 = price * t1; t3 = t2 - discount
B2: if t2 < 100 goto B4          ← 分叉
B3: total = t3
B4: return total

各块 USE 与 DEF：
B1  USE: qty price discount   DEF: t1 t2 t3
B2  USE: t2                   DEF: 空
B3  USE: t3                   DEF: total
B4  USE: total                DEF: 空
​

迭代（初值全空，出口处 return 之后无活跃）：

第 1 轮（从 B4 往前）：
B4: OUT 空,        IN {total}
B3: OUT {total},   IN {t3, total}
B2: OUT {t3,total}(后继 B3),  IN {t2, t3, total}
B1: OUT {t2,t3,total}(后继 B2), IN {qty,price,discount,t2,t3,total}
       注意 t2 在 IN 里：B1 先定值 t2 后……不，B1 中 t2 定值前无引用，
       属 DEF，从 OUT 减去。修正：IN {qty, price, discount, t3, total}

第 2 轮：集合不再变化 → 不动点到达，分析结束
​

结论的读法：B3 入口处 t3 活跃——它从 B1 一路活到 B3 的赋值；t1、t2 在 B1 出口处不活跃（B2 只用了 t2……B2 的 USE 是 t2，所以 t2 在 B1 出口活跃，t1 不活跃）。这条结论立刻能换优化：t1 在 B1 出口死亡，B1 里对 t1 的定值若不影响同块内 t2 的计算，其存储可省——第 6 章寄存器分配将直接消费活跃性结论：不活跃的值不必占寄存器。

前向与后向、必经与可能

三个设计旋钮决定一种分析的形态。方向：信息随执行流走是前向（到达定值、可用表达式），逆着走是后向（活跃变量）。边界条件：入口边界决定方程组有解的起点。合取与并取：这是最微妙的——到达定值用并集（任何路径到达都算到达，"可能"语义），可用表达式用交集（所有路径都可用才可用，"必然"语义）。选并还是选交，取决于下游优化要"可能成立就动手"还是"必然成立才动手"。

保守原则贯穿一切：分析允许说错"不"（漏报优化机会），不许说错"是"（错误优化）。活跃变量分析宁可把可能活跃的都算活跃——多留几个寄存器没损失；把实际要用的判成死亡则直接改错程序。

图 活跃变量分析：信息从出口逆流而上

分析结论如何换成优化

三个兑换案例。死代码删除：定值点出口处变量不活跃，且该定值无副作用 → 删除（5.2 节块内版的全局升级）。全局公共子表达式：某表达式在块入口处"可用"（所有路径都算过且操作数未变）→ 块内重算可替换为复用。寄存器分配：两变量的活跃区间不相交 → 可共用一个寄存器（第 6 章图着色的理论根基）。每个案例里，分析发放"通行证"，优化凭票动手——没有票就放棄，这就是全局优化贵在分析、赚在变换的结构。

⚠️ 常见坑：以为不动点迭代会无限循环。方程组是单调框架上的格上迭代，集合只增不减（或只减不增），有穷格保证终止；若自己设计分析时打破了单调性（方程里既有并又有随机删减），迭代就可能震荡——单调性是设计约束，不是免费赠品。

💡 关键直觉：数据流分析是"抽象解释"——把程序在抽象值（集合）上跑一遍，得到真实执行不可能直接给出的全局事实。它宁可模糊（可能到达、可能活跃）也要保真，模糊损失的是优化机会，失真破坏的是正确性。

望远镜的校准问答

问：数据流方程为什么保证收敛？ 因为传递函数单调：集合只会沿迭代增长（并集语义）或收缩（交集语义），而可能的状态有限，有限单调序列必然到达不动点。自己设计新分析时要守住单调性——它不是数学装饰，是算法停机的全部保证，也是正确性证明的骨架。

问：分析结果是精确的吗？ 几乎从不精确。到达定值说某定义可能到达，实际只有一条路径活着；活跃变量说某变量可能活跃，实际从未使用。不精确的方向永远偏向安全一侧（多保留、多计算、少删除）——精确性与终止性的交换，是所有静态分析的宿命，也是抽象解释理论的出发点。

本节要点回顾

• 三大分析：到达定值与可用表达式前向，活跃变量后向，各支撑一族优化
• 方程组：IN 与 OUT 沿控制流传递，USE 与 DEF 是块的本地贡献
• 迭代求解：初值空集起步，反复传递到集合不再变化即不动点
• 并取交取：可能语义用并、必然语义用交，选错直接破坏优化安全
• 保守原则：漏报机会可以，误报事实不行——分析为优化担责

望远镜已就位。下一节换一种中间表示：SSA 让"每个名字只定义一次"，把数据流分析的大部分结论直接写进代码形态里。