程序依赖图 | Codeboy's Blog

形式陈述

先固定程序和边的含义

程序依赖图把“哪条语句可能给这里提供值”和“哪个判断决定这里是否执行”放在同一张图里。本页采用无循环、单入口单出口的结构化顺序程序：命令只有局部赋值、二路条件和末尾唯一 return。表达式纯粹且总定义，变量取数学整数，所有读取在每条到达路径上都有定义；没有指针、异常、外部 I/O 或并发。因而任一输入都正常终止。

以语句与判断为节点，入口另提供输入变量的定义。数据边 $d\xrightarrow{x}u$ 表示： $d$ 定义 $x$ ， $u$ 读取 $x$ ，存在从 $d$ 到 $u$ 的 CFG 路径，途中没有另一次 $x$ 定义。这里的“存在”先针对图路径，不要求分支条件联合可满足，所以允许保守多报依赖。

控制边采用支配关系的出口版本。记 $\operatorname{PD}(v)$ 为从 $v$ 到唯一出口 $z$ 的每条路径都经过的节点集合，包含 $v$ 本身。如果判断 $b$ 有一条标记为 $\tau$ 的出边 $b\to s$ ，则加入

b\xrightarrow{\tau}_{c}u \quad\Longleftrightarrow\quad u\in\operatorname{PD}(s)\setminus\operatorname{PD}(b).

走这条分支后必须经过 $u$ ，但从判断处出发并非所有分支都必须经过它。边方向是“控制者指向受控者”；并不是 $u$ 指向条件。图记为 $G_D=(V,E_d,E_c)$ ，边要保留类型和变量或分支标签。[1, §3.1]

从 CFG 实际构图

先按逆拓扑顺序计算

\operatorname{PD}(z)=\{z\},\qquad \operatorname{PD}(v)=\{v\}\cup\bigcap_{s\in\operatorname{succ}(v)}\operatorname{PD}(s).

无环性保证处理 $v$ 时全部后继已经算好。对每条判断出边，按上式的集合差发出控制边。数据边则实际调用到达定义分析：对节点 $u$ 读取的每个 $x$ ，从其入口集合筛出 $x$ 的所有定义 $d$ ，发出 $d\xrightarrow{x}u$ 。在本页无环图上，前向拓扑扫描就能完成到达定义，不需反复工作队列。

两项计算各有直接不变量。逆向处理完的后支配集合等于全部后继路径的交；前向处理完的定义集合包含所有可能最后写入。依赖图保留的是这些语义相关来源，并不复制全部顺序边。

直觉

一段程序里的三种箭头

下面的编号是节点身份，缩进给出嵌套关系；0是输入节点，10是正常出口。

text

0  input x, y
1  a := x + 1
2  junk := y * y
3  r := 0
4  if x > 0:
5      if y == a:
6          r := 1
       else:
7          r := 2
8  junk := junk + 1
9  return r

CFG 有顺序边 $1\to2$ ，但2不读取 a，也不受1的条件控制，所以依赖图没有 $1\to2$ 。相反，1到5之间隔了几条语句，仍有数据边 $1\xrightarrow{a}5$ 。判断4决定是否执行5，形成控制边 $4\xrightarrow{T}_c5$ 。

节点8位于所有分支的汇合后，每次执行都会到达它。4虽出现在8前面，却不直接控制8是否执行。这个区别使依赖图比“把前面的语句全留下”更适合分析相关性。

蓝色为数据来源，灰色虚线为控制依赖；返回r的反向闭包排除只影响junk的2和8 — 同一程序的数据边与控制边

例子与边界

逐项复算控制边

只看分支附近，后支配集合为

\begin{aligned} PD(4)&=\{4,8,9,10\},&PD(5)&=\{5,8,9,10\},\\ PD(6)&=\{6,8,9,10\},&PD(7)&=\{7,8,9,10\},\\ PD(8)&=\{8,9,10\}.&& \end{aligned}

4的真边到5，集合差为 $\{5\}$ ；假边到8，集合差为空。5的真、假边分别给 $\{6\}$ 、 $\{7\}$ 。所以全部直接控制边恰为

4\xrightarrow{T}_c5,\qquad5\xrightarrow{T}_c6,\qquad5\xrightarrow{F}_c7.

6的执行间接依赖4，经 $4\to5\to6$ 表达；无需再把传递闭包当直接边全部加上。

逐项复算数据边

除输入0分别向1、2、4、5提供 x,y,x,y 外，数据边还有

1\xrightarrow{a}5,\quad2\xrightarrow{junk}8,\quad 3\xrightarrow r9,\quad6\xrightarrow r9,\quad7\xrightarrow r9.

共9条数据边。3的 r:=0 仍能在4为假时到达9；不能因为其他路径有后续赋值就删去这个来源。8的右侧 junk 由2提供，而非由8这次尚未完成的赋值提供。

图路径可能包含不可能的条件组合。例如 if x>0 内再测 x<0，CFG 仍有通向内层真分支的边。保留它使静态依赖保守，路径求解可另行证明不可行；没做求解时不能默认删掉。

本图并非任意重排许可证

这里只建立值流和控制依赖，足以服务下页的删除式切片。若要任意交换赋值，还可能需要反依赖、输出依赖和内存效果边。例如 a:=x; x:=1 中第一句读取旧 x；仅有定义到使用的边不会禁止交换这两句。本页不从“图上没有边”推出可并行或可交换。

原论文采用严格后支配记法，本页采用含自身的反身集合并限制无环图，避免把文献中关于循环自控制的规则机械照搬。一般循环、多出口和异常退出需重新明确最大执行、终止和观察语义；旧支配页的出口警告仍然适用。

推论与应用

成本和下一步

设 CFG 有 $n$ 个节点、 $m$ 条边，定义记录总数为 $d$ ，各节点读取变量数之和为 $R$ ，原表达式总大小为 $L$ 。按下载脚本的朴素集合扫描实现，单位集合操作的期望成本为常数时，构图时间可保守界为

O\bigl(L+(n+m)(n+d)+Rd\bigr).

其中后支配集合最多 $n$ 项，到达定义集合最多 $d$ 项，每次变量筛选最多扫描 $d$ 项。存储这些集合及边需 $O(L+n(n+d)+m+|E_d|+|E_c|)$ 空间。位集或支配树实现可改善成本，不能把那些改进的界直接写给当前逐元素脚本。

静态程序切片从观察节点逆向遍历两种边，得到必须保留的定义和判断。此处的构图责任与下页的删减正确性责任分开：前者说明来源覆盖，后者说明怎样得到仍可执行且保持特定观察的程序。

迁移练习：把8改成 r:=junk。现在9的唯一到达定义是8，2通过 junk 成为相关节点；3、6、7不再给9提供最终值。请重新计算数据边，再问4和5是否还影响返回值。答案需要重新构图，不能只给旧图添一条边。

参考资料

[1] Jeanne Ferrante、Karl J. Ottenstein、Joe D. Warren，The Program Dependence Graph and Its Use in Optimization，ACM TOPLAS 9(3)，1987，319–349页；§3.1给控制依赖与后支配构造，§3.2讨论数据依赖。本文的无环整数算例、集合成本及删减用途单独限定，不覆盖论文全部优化模型。

形式陈述 ​

先固定程序和边的含义 ​

从 CFG 实际构图 ​

一段程序里的三种箭头 ​

逐项复算控制边 ​

逐项复算数据边 ​

本图并非任意重排许可证 ​

成本和下一步 ​

反向链接