控制流图中的支配关系

支配节点是到达某处之前无法绕开的检查站。看到一条经过 $d$ 的路径，只能证明 $d$ 可能在途中；必须排除所有绕行路径，才能证明 $d$ 支配目标。这个“所有入口路径”的量词把控制依赖问题变成树结构，也解释了为什么定义点支配使用点是 SSA 中可靠取值的条件。

立即支配点不是图上距离最近的前驱，而是严格支配链中最靠近目标的一项。它甚至不必与目标有直接 CFG 边。支配树压缩了全局必经关系，却不保留所有可能执行顺序；两节点在树上是兄弟，只说明彼此都不是对方的必经点，并不说明它们可以并行或互不可达。

取菱形图 $r\to a,r\to b,a\to j,b\to j,j\to z$。入口到 $j$ 有两条路径，分别绕过 $a$ 与 $b$，故

虽然某次 DFS 可能先走 $r,a,j,z$，$a$ 仍不支配 $j$。只要展示路径 $r\to b\to j$ 就能否定支配；要肯定支配则需论证任意路径。

循环图 $r\to h,h\to b,b\to h,h\to e$ 中，$h$ 支配 $b$ 与 $e$，而 $b$ 不支配 $h$，因为首次到 $h$ 的路径尚未经过 $b$。回边不会破坏自反定义；路径即使可绕循环任意多圈，也都必须先过 $h$ 才能到达循环体。

不可达块需要明确处置。若 $u$ 从 $r$ 不可达，则“每条 $r$ 到 $u$ 的路径都经过 $d$”在经典逻辑中会因路径集合为空而对所有 $d$ 真，从而产生无意义的全体支配。编译器通常先删除不可达块，或为每个不可达区域选择单独根并明确新的入口语义；不能把空真值直接当作有用支配信息。

支配关系支持定义—使用校验、循环头识别、代码移动与 φ 放置。把一项计算上提到 $d$ 时，仅有 $d$ 支配原位置还不够：操作还必须在所有新增执行路径上安全，不能多引发陷阱或副作用。图结构许可和语义许可是两项不同证明责任。

复用已有计算时，支配作用域值编号理路支配作用域值编号Dominance-scoped value numbering · Dominator-based value numbering · DVNT沿 SSA 支配树维护可回退的表达式表，用值代表识别跨块冗余，区分等值与载体可用，保守处理未解循环φ并执行变换后的程序。把支配树直接用作载体作用域：祖先结果可被孩子继承，离开一个子树便撤回局部表达式条目。两个兄弟分支即使算出同值，也不能相互读取尚未执行的名字。这是值等价与名字可得性的区别，不是再定义一种支配关系。

反向控制流上的对应概念是后支配：节点 $p$ 位于从 $v$ 到统一出口的每条路径上。多返回、异常或不终止路径使出口约定变得关键。后支配不是把原支配结论中的箭头机械翻转；必须先构造适合观察目标的反向流图。

程序依赖图理路程序依赖图Program dependence graph · PDG把定义使用与分支控制分成两种有向边，从同一无环程序逐项构造可供静态切片查询的依赖图。在无环、单出口、无异常的明确模型中计算反身后支配集合，并逐条用后继集合差构造控制依赖；再接上定义使用边。静态切片理路程序切片Program slicing · Static backward slicing · 静态后向切片从选定返回值反向闭合数据与控制依赖，构造可执行静态切片，并明确单输入切片与终止异常观察的界限。沿两类边逆向闭合，在保留原分支结构的条件下保持指定返回值，不把任意节点删除说成一般程序等价。

支配还给代码移动一个必要检查。若定义 $d$ 的结果在 $u$ 使用，移动后仍须有新定义点支配 $u$，并且所有操作数的定义支配新位置。不过这只保障值可得；可能 trap 的除法从条件分支内上提到分支前，会让原本不执行除法的路径新增 trap。支配证明结构合法，效果证明才决定变换语义合法。