Tarjan的支配树算法

孙子平

最近更新于 2021年10月23日 8 分钟阅读时长静态分析

这篇文章介绍了Tarjan的快速支配算法¹。这个算法很有洞察力地利用了”半支配“的性质。

流图 $G = (V, E, r)$ 上进行深度优先搜索后，节点按照发现顺序编号（论文从1编号）。搜索产生了以 $r$ 为根的搜索树 $T$ ，编号正是前序遍历序号。本文假设所有节点以此序号标识。

G

上的两节点

v, w

，满足

v \leq w

，那么任何

v

到

w

的路径一定经过

v, w

在

T

上的共同祖先。

定义 2半支配者

sdom (w)

定义为：

$sdom (w) = min {v ∣ 存在路径 v = v_{0}, v_{1}, \dots, v_{k} = w 满足 \forall i (1 \leq i \leq k - 1 \to v_{i} > w)}$

本文中的 $x \overset{*}{\to} y$ 是指在 $T$ 上， $x$ 是 $y$ 的祖先。 $x \overset{+}{\to} y$ 是指在 $T$ 上， $x$ 是 $y$ 的祖先且 $x \neq y$ 。

引理 3对任何

w \neq r

，

idom (w) \overset{+}{\to} w

。

引理 4对任何

w \neq r

，

sdom (w) \overset{+}{\to} w

。

证明 4由于

G

上存在路径

parent (w) \to w

，由定义 2知

sdom (w) \leq parent (w) < w

。由引理 1，

sdom (w)

到

w

的路径一定经过

sdom (w), w

的共同祖先。共同祖先

\leq sdom (w)

，故而共同祖先只能是

sdom (w)

。

引理 5对任何

w \neq r

，

idom (w) \overset{*}{\to} sdom (w)

。

证明 5

sdom (w)

取到的路径上，除了

sdom (w), w

没有

w

的祖先，故而都不是

idom (w)

而路径

r \overset{*}{\to} sdom (w)

拼接上

sdom (w)

取到的路径组成的路径上一定有

idom (w)

，故而

idom (w) \overset{*}{\to} sdom (w)

引理 6节点

v, w

满足

v \overset{*}{\to} w

，那么

v \overset{*}{\to} idom (w)

或

idom (w) \overset{*}{\to} idom (v)

。

证明 6其实这条定理是说

idom (w)

不可能位于

idom (v)

与

v

之间。反之，

idom (v)

到

v

存在不经过

sdom (w)

的路径，将这个路径拼接上

r \overset{*}{\to} idom (v)

和

v \overset{*}{\to} (w)

，就得到了不经过

sdom (w)

到达

w

的路径，矛盾。

定理 7对于

w \neq r

，如果对于所有满足

sdom (w) \overset{+}{\to} u \overset{*}{\to} w

的

u

，都有

sdom (u) \geq sdom (w)

，那么

idom (w) = sdom (w)

。

证明 7只需要证明

sdom (w)

支配

w

。任取从

r

到

w

的路径，现在证明路径上一定有

sdom (w)

。令

x

是这个路径上最后一个满足

x < sdom (w)

的节点，如果不存在，那么

sdom (w) = r

，原命题成立。令

y

是这个路径上第一个满足

sdom (w) \overset{*}{\to} y \overset{*}{\to} w

的节点。对于路径上

x

与

y

之间的节点

v

，一定有

v > y

。否则的话路径上有

v, y

且

\neq y

的共同祖先，且该祖先

\geq sdom (w)

，那么这与

y

的选取矛盾。故而

sdom (y) \leq x < sdom (w)

，所以只可能

y = sdom (w)

，即路径一定包括

sdom (w)

。

定理 8对于

w \neq r

，令

u

是满足

sdom (w) \overset{+}{\to} u \overset{*}{\to} w

的节点中

sdom (u)

最小的那个，那么

sdom (u) \leq sdom (w)

且

idom (u) = idom (w)

。

证明 8对于

sdom (w) \to z \overset{*}{\to} w

，

sdom (z) \leq sdom (w)

，所以一定有

sdom (u) \leq sdom (w)

。接下来证明

idom (u) = idom (w)

。由引理 6，一定有

idom (w) \overset{*}{\to} idom (u)

，接下来证明

idom (u)

支配

w

。任取从

r

到

w

的路径，现在证明路径上一定有

idom (u)

。令

x

是这个路径上最后一个满足

x < idom (u)

的节点，如果不存在，那么

idom (u) = r

，原命题成立。令

y

是这个路径上第一个满足

idom (u) \overset{*}{\to} y \overset{*}{\to} w

的节点。对于路径上

x

与

y

之间的节点

v

，一定有

v > y

，证明同定理 7的相关证明。故而

sdom (y) \leq x < idom (u) \leq sdom (u)

。然而

u

是满足

sdom (w) \overset{+}{\to} u \overset{*}{\to} w

，

sdom (u)

最小的，故

idom (u) \overset{*}{\to} y \overset{*}{\to} sdom (w) \overset{+}{\to} u

。然而

y

不可能在

idom (u)

和

u

的中间。否则

r \overset{*}{\to} sdom (y)

拼接上

sdom (y)

取的路径再拼接上

y \overset{+}{\to} u

形成的路径，避开了

idom (u)

。所以只可能

y = idom (u)

，即路径一定包括

idom (u)

。

推论 9对于

w \neq r

，令

u

是满足

sdom (w) \overset{+}{\to} u \overset{*}{\to} w

的节点中

sdom (u)

最小的那个，那么：

$idom (w) = {\begin{cases} sdom (w) & if sdom (w) = sdom (u) \\ idom (u) & otherwise \end{cases}$

定理 10对于

w \neq r

：

$sdom (w) = min ({v ∣ (v, w) \in E \land v < w} \cup {sdom (u) ∣ u > w \land (v, w) \in E \land u \overset{*}{\to} v})$

证明 10令

x

是上式右侧。先证明

sdom (w) \leq x

。如果

x

满足

(x, w) \in E \land x < w

，那么由定义 2，

sdom (w) \leq x

。如果

x

满足

x = sdom (u) \land u > w \land (v, w) \in E \land u \overset{*}{\to} v

，那么

sdom (u)

选的路径中间的点

> u > w

，

u \overset{*}{\to} v

上的点

\geq u > w

，最后这两条路径拼接上

(v, w)

的到的路径满足

sdom (w)

的候选路径，故而

sdom (w) \leq x

。

接着证明 $sdom (w) \geq x$ 。如果 $sdom (w)$ 所选的路径 $sdom (w) = v_{0}, v_{1}, \dots, v_{k} = w$ 长度为1，那么 $(sdom (w), w) \in E \land sdom (w) < w$ ，故而 $sdom (w) \geq x$ 。如果 $sdom (w)$ 所选的路径长度大于1。令 $j \geq 1$ 是 $v_{j} \overset{*}{\to} v_{k - 1}$ 最小的，那么对于 $1 \leq i \leq j - 1$ ，一定有 $v_{i} > v_{j}$ 。否则，取 $i$ 满足 $1 \leq i \leq j - 1$ 且 $v_{i}$ 最小。那么有 $v_{i}$ 到 $v_{j}$ 的路径经过了共同祖先，那么 $v_{i}$ 由于最小，一定是共同祖先，那么 $v_{i} \overset{+}{\to} v_{j}$ ，与 $j$ 的选取矛盾。此时就有 $sdom (w) \geq sdom (v_{j}) \geq x$ 。

定理 10其实是说， $sdom (w)$ 所选的路径，一定是：

树边、前向边开始
接着若干（ $n \geq 0$ ）：
1. 若干树边（ $n \geq 0$ ）
2. 回边或者交叉边，到比上一步小的节点

Lengauer, Thomas, and Robert Endre Tarjan. “A fast algorithm for finding dominators in a flowgraph.” ACM Transactions on Programming Languages and Systems (TOPLAS) 1.1 (1979): 121-141. ↩︎

编辑本页

静态分析

Tarjan的支配树算法

孙子平

静态分析方向研究生

相关