Skip to content

定义Definition

单调数据流分析

施工中 · 内容逐步修订

Monotone dataflow analysis · Monotone framework · Data-flow equations

在控制流图上以单调 transfer 和合流方程求解前向或后向程序事实。

形式陈述 ​

分析框架的四个部件 ​

单调数据流框架包含控制流图 G=(V,E)、性质完备格 (L,⊑)、每个节点或边的单调 transfer fv:L→L,以及边界值。

前向 may 分析的典型方程是

IN[v]=Bv⊔⨆u∈pred(v)OUT[u],OUT[v]=fv(IN[v]).

其中 Bv 是边界贡献:入口取允许输入的抽象值,其余点通常取 ⊥。后向分析把前驱换成后继,并在相应出口放置边界值,方程方向反转。must 分析可能使用 meet 或反向信息序;符号 ⊔ 的语义必须与“更大代表更多可能”约定一致。

方程整体定义 LV 上的单调算子,因此由Knaster–Tarski 定理有最小不动点。算法目标是计算或可靠逼近该解。

直觉

reaching definitions 的轨迹 ​

分析每个程序点可能到达的赋值定义集合。格为定义集合的幂集,次序是包含,join 是并集。赋值节点 v 的 transfer 为

fv(X)=genv∪(X∖killv).

程序先有 d1: x:=0,随后分支一执行 d2: x:=1,分支二不改 x。到汇合点,第一条路径的 OUT 含 d2,第二条含 d1,join 得 {d1,d2}。

这不表示两个定义会在同一次运行同时给 x 赋值为当前值;它表示任一者都可能是汇合处最近到达定义。may 事实用并集合流正是为了覆盖两条路径。

若后续执行 d3: x:=2,kill 删除 d1,d2,gen 加入 d3,输出只含 d3。漏掉 kill 会保持可靠却产生多余定义,错误多做 kill 则可能漏掉真实到达定义。

例子与边界

Worklist 求解 ​

固定有限CFG与边界值,将全部 IN/OUT 初始化为 ⊥,并把所有保留节点至少放入初始worklist一次。每次取出节点,先按方程把边界贡献 Bv 与前驱输出合流,再执行transfer重算 IN/OUT;只有输出改变时,才把受影响后继重新入队。队列中的工作须实际处理完,不能无限搁置某项。

首次调度全部方程很重要:非严格transfer可以从 ⊥ 产生gen事实。若只排入口,而入口输出恰好未变,它的后继可能永远没被访问;即使图上可达,局部生成也会漏掉。若要省去某些初始队列项,必须另证其方程已经满足且后续变化会触发它们。

从底元开始,边界贡献固定,前驱输出只增,单调transfer保证每次更新不下降。有限高度格上,每个节点值只能严格上升有限次,变化才触发的入队总数因此有限;全部队列处理后每个方程都稳定,故算法终止。对任一不动点解,按更新次数作数学归纳:底元不超过该解,每次更新由单调性继续保持这个界,所以所得稳定值是最小不动点。若最大链高为 h,节点值的严格变化总次数受 O(|V|h) 控制;队列取出和方程重算还包括值未变的访问,不能把这个界直接当作总运行时间,单次 transfer 和 join 成本也要另计。

worklist 顺序影响中间更新次数,不影响有限单调框架的最小不动点。循环头优先、reverse postorder 常更快,但不是正确性的必要条件。

单调数据流 Worklist 收敛

无限高度域不保证普通迭代有限停止,但某个具体算子仍可能很快稳定。若不能单独证明有限收敛,可使用widening或其他有终止保证的加速,并核验所得结果是可靠的前不动点;普通“值看起来变化很小”不是合法停止标准。

推论与应用

MFP 与 MOP ​

maximum fixed-point/minimum fixed-point solution(依次序约定也称 MFP)是数据流方程的不动点结果。meet-over-all-paths(MOP)则对从入口出发的每条有限 CFG 图路径分别复合 transfer,再在目标点合流。

单调性通常保证迭代解对 MOP 可靠,但二者未必相等。若 transfer 对合流运算分配,例如

f(x⊔y)=f(x)⊔f(y),

在格有限高度、只处理入口在图上可达的节点且正确加入边界值的经典框架中,可得到 MFP=MOP。若还保留不可达节点,须另处理空路径族,例如要求相应 transfer 严格保持 ⊥;否则非严格的 gen 操作可能在不可达区域凭空生成事实并传入汇合点。只有单调而不分配时,先合流再 transfer 可能比逐路径后合流更粗。

MOP 仍按 CFG 路径计算,可能包含语义上不可行路径。要逼近真正收集语义,还需 path feasibility 或更强关系分析;“对所有图路径”不等于“对所有真实执行且仅这些执行”。

跨过程时还要排除调用与返回不匹配的图路径。IFDS利用有限事实域及分配律,把集合transfer拆成单事实边和零事实边,再按合法调用返回路径求解;IDE在边上保存值函数,进一步处理copy-constant等环境问题。这些条件比单调性更强,不能把任意已有worklist问题直接替换为IFDS或IDE。

边界与实现责任 ​

transfer 必须匹配节点粒度:基本块 transfer 应按块内语句顺序复合,不能把非交换赋值当集合无序处理。异常边、调用返回和别名写入若不在 CFG/transfer 中,会破坏全局可靠性。

前向/后向描述信息传播方向,不直接等于 may/must。reaching definitions 是前向 may,liveness 是后向 may;available expressions 常是前向 must。两个维度要分别声明。

分析结果是程序点性质,不是运行时监控日志。它以静态全称覆盖换取保守性,具体警报能否消除取决于格和 transfer 的表达精度。

稀疏分析会只在定义—使用链或 SSA 值变化处传播,而不为每个 CFG 节点保存同样事实。它可以减少无效更新,但需要证明稀疏图与原数据流方程等价。把节点删少并不自动保持解;phi 节点、异常使用和内存别名若遗漏,稀疏结果可能比原方程更“漂亮”却不可靠。

三个经典实例现在分别给出可执行细节:到达定义保留可能来源,活跃性反向传播未来需求,可用表达式以前向全路径交保留复用条件。同图优化终点把这些事实交给具体变换,并由SCCP接上控制边与SSA值的共同求解。

参考资料
  • Gary A. Kildall, “A Unified Approach to Global Program Optimization,” POPL, 1973, pp. 194–206。
  • Kam and Ullman, “Monotone Data Flow Analysis Frameworks,” Acta Informatica 7, 1977, pp. 305–317。
  • Flemming Nielson, Hanne Riis Nielson, and Chris Hankin, Principles of Program Analysis, Springer, 1999, Chs. 2–3。
关系图谱31 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系