构建数据依赖的实现
这篇文章总结了DFST、支配、归约的各种性质和算法，并最终给出路径摘要的方案。上一篇文章的链接在这里：从CFG直接构建GSA的算法。
注意：未经许可，禁止转载。通过OpenTimestamps，我已经获得了该文最早的区块链时间戳。有且只有我（me@szp.io）持有其证明。因此如果你能伪造区块链，请你投计算机顶会；如果不能，不要未经我的许可，转载文章内容，否则我保留追究权利。
数据依赖的定义
- 如果该边是循环回边：以该边结束，从该基本块到其本身的简单回路成立的条件；
- 如果该边不是循环回边：以该边结束，从该基本块的立即支配者到其本身的简单路径成立的条件。
本文中的控制流图（CFG）是指带入口节点$Entry$、可以有重边、可以有自环的有向图；此外还需要满足可达性，即存在从$Entry$到任意节点的路径。
我们用$N$表示CFG的节点集合，$E$表示CFG的边集合。
| 边的ID | 数据依赖条件 |
|---|---|
| 6 | $(P\land\neg R)\lor(\neg P\land Q\land\neg R)$ |
| 7 | $R$ |
| 9 | $\neg P\land Q$ |
| 10 | $\neg P\land\neg Q\land\neg T$ |
| 13 | $\neg P\land\neg Q\land T$ |
| 17 | $P$ |
接下来，我将讲解可归约CFG上路径摘要算法的原理和实现。路径摘要算法可以用于快速地求解数据依赖条件，也可以用于求解某些
路径摘要算法的步骤
路径摘要算法是多步骤的。具体各个步骤的依赖关系见
各步骤的输出及目的见
| 编号 | 名称 | 输出 |
|---|---|---|
| 1 | 深度优先生成树 | 以入口基本块为根的生成树，识别出非循环边和回边 |
| 2 | 支配树 | 每个基本块的立即支配者 |
| 3 | 识别循环 | 每个基本块所属的最近循环头 |
| 4 | 归约序列 | 找到一个序列，序列的每个节点可以归约到后面的节点 |
| 5 | 路径摘要 | 按照归约序列，计算从立即支配者出发的路径条件 |
算法的各个步骤
深度优先生成树（DFST）
DFST边的类别
一个有向图的边可以按照其某个生成树分类：
- 树边：终点是起点的父亲
- 前向边：终点是起点的子孙，且不是自环边或树边
- 回边：终点是起点的祖父，且不是自环边
- 自环边：起始与终止节点相同
- 交叉边：终点既不是起点的子孙，也不是起点的祖父
形象的分类见
例子见
自环边和回边我们统称为循环边，而树边、前向边和交叉边统称为非循环边。
DFST边的性质
- 树边：$\mathrm{PreOrder}(u)<\mathrm{PreOrder}(v)$
（指向还未搜索过的节点，构成生成树） - 自环：$\mathrm{PreOrder}(u)=\mathrm{PreOrder}(v)$
- 其他边：$\mathrm{PreOrder}(u)>\mathrm{PreOrder}(v)$
（指向已经搜索过的节点，回溯）
逆命题同样成立：任何一棵生成树，如果有$\mathrm{PreOrder}$满足了上面的三个性质，它就可以是以$\mathrm{PreOrder}$为发现顺序的深度优先生成树。
$$\mathrm{RevPostOrder}(u)>\mathrm{RevPostOrder}(v)$$
进一步，非循环边组成的子图是一个DAG，其拓扑排序的一种结果是$\mathrm{RevPostOrder}$。
最后，我们很关心的一个问题是：回边集合和非循环边集合会不会随DFST变化。遗憾的是，确实可能会发生变化。最小的例子见
但如果CFG可归约，那么DFST对应的回边集合和非循环边集合是不会变的。这也就是
支配树
支配的概念
CFG上，节点$x$支配节点$y$，是指从$Entry$到$y$的每条路径都经过了$x$。由于具有自反性
非入口节点$x$的立即支配者$y$就是所有严格支配者中极大的
非入口节点的立即支配者存在且唯一，和支配的偏序关系是支配的两条独立性质。通过这两条性质，就能知道支配关系组成了一棵带根树，根即为$Entry$。这颗树我们称为支配树。
支配算法
DAG CFG的直接支配算法
实际计算中，如果用bit vector作为集合，其集合的交并运算非常复杂，并且没有完全利用支配的“树”的性质。注意到：
$$\mathrm{StrictDoms}(x)=\{\mathrm{idom}(x),\mathrm{idom}(\mathrm{idom}(x)),\dots\}$$
且该集合是全序的，立即支配者为最大元素：
$$\mathrm{idom}(x)=\max(\mathrm{StrictDoms}(x))$$
因此就可以得到一个时间、空间上更有效的计算方法：
这里$\mathrm{LCA}$是指支配者树上的最低公共祖先。总结一下，就得到了下面的算法：
- 将$Entry$节点构成一颗单节点树$DomTree$
（初始化） - 循环：如果还存在一个基本块$x$，满足$x\notin DomTree\land\mathrm{Pred}(x)\subseteq DomTree$：
- 以$\mathrm{LCA}(\mathrm{Pred}(x))$为父亲，将$x$插入到$DomTree$上
实际实现中，按拓扑序进行插入即可避免
$\mathrm{LCA}$的计算
未加说明的话，以下讨论是对于一般的CFG，不仅限于DAG形式的。
多元素集合上的$\mathrm{LCA}(S)$可以归结为两个变量的$\mathrm{LCA}(a, b)$
$$\begin{cases}\mathrm{Ancestors}_{DomTree}(x)\equiv\mathrm{Doms}(x)\subseteq\mathrm{Ancestors}_{DFST}(x)\\\mathrm{Descendants}_{DomTree}(x)\equiv\mathrm{Doms}^{-1}(x)\subseteq\mathrm{Descendants}_{DFST}(x)\end{cases}$$
类似地，我们也有：
$$\mathrm{StrictAncestors}_{DomTree}(x)\equiv\mathrm{StrictDoms}(x)\subseteq\mathrm{StrictAncestors}_{DFST}(x)$$
注意：其实许多符号既有图论版本的表述，又有控制流版本的表述，它们是等价的，例如：
$$\begin{align*}\mathrm{Ancestors}_{DomTree}&\equiv\mathrm{Doms}\\\mathrm{StrictAncestors}_{DomTree}&\equiv\mathrm{StrictDoms}\\\mathrm{Parent}_{DomTree}&\equiv\mathrm{idom}\end{align*}$$
形象地来说，支配者树比DFST更加扁。一个等价的描述是：如果将树的自上而下视作一个偏序关系，那么支配树的偏序关系是DFST偏序关系的子集；另一个更有趣的描述是：支配树的偏序关系是所有DFST偏序关系的交。个人最喜欢的描述是：支配树是DFST中的某些支干重新接到了祖先上形成的新树。而这个描述将很好地体现在
基于此，可以下面的定理：
$$\forall y(y\in\mathrm{Descendants}_{DomTree}(x)\rightarrow\mathrm{RevPostOrder}(y)\geq\mathrm{RevPostOrder}(x))$$
有些时候我们会想能不能得到更强的定理：支配树上也一定存在一种先序遍历
基于
- 依据DFST上的逆后序遍历对基本块进行编号，记这个编号为$\mathrm{RevPostOrder}(x)$
- 循环：如果$a\neq b$：
- 如果$\mathrm{RevPostOrder}(a)<\mathrm{RevPostOrder}(b)$：
- $b\leftarrow\mathrm{Parent}_{DomTree}(b)$
（分支1）
- $b\leftarrow\mathrm{Parent}_{DomTree}(b)$
- 否则：
（一定有$\mathrm{RevPostOrder}(a)>\mathrm{RevPostOrder}(b)$） - $a\leftarrow\mathrm{Parent}_{DomTree}(a)$
（分支2）
- $a\leftarrow\mathrm{Parent}_{DomTree}(a)$
- 如果$\mathrm{RevPostOrder}(a)<\mathrm{RevPostOrder}(b)$：
- 返回$a$
这个算法不仅简单，而且性能不错，因为能使用连续的数组提高缓存命中率。注意，分支1和分支2可能会交替执行，这其实是前文中“不能得到更强的定理”导致的：例如
- 找到$N_4$的父亲$N_1$
（分支2） - 找到$N_3$的父亲$N_0$
（分支1） - 找到$N_1$的父亲$N_0$
（分支2） - 得出：$\mathrm{LCA}(N_4,N_3) = N_0$
一般CFG的迭代支配算法
对于一般的CFG，
$$\begin{cases}\mathrm{X}(x)=\varnothing,&\text{if}~x=Entry\\\mathrm{X}(x)=\bigcap_{y\in\mathrm{Pred}(x)}y\cup\mathrm{X}(y),&\text{if}~x\neq Entry\end{cases}$$
会得到若干解，那么对于任意基本块$x$，每个解一定满足：
$$\mathrm{X}(x)\subseteq\mathrm{StrictDoms}(x)$$
$$\mathrm{X}(x)=(w_{k-1}\cup((w_{k-2}\cup((\cdots)\cap\cdots))\cap\cdots$$
因此，我们可以得到：
$$\mathrm{X}(x)\subseteq\{w_i\mid 0\leq i\leq k-1\}$$
故$y\notin\mathrm{X}(x)$，与假设矛盾。
基于
考虑
- 用某个DFST初始化$DomTree$
（初始化） - 循环：如果树上有一个节点$x$，满足$\mathrm{Parent}_{DomTree}(x)\neq\mathrm{LCA}(\mathrm{Pred}(x))$：
- 更新$\mathrm{Parent}_{DomTree}(x)$为$\mathrm{LCA}(\mathrm{Pred}(x))$
（移动了一整棵子树到某个祖先上）
- 更新$\mathrm{Parent}_{DomTree}(x)$为$\mathrm{LCA}(\mathrm{Pred}(x))$
实现上，由于循环体可能会触发很多节点重新计算，一般是多次逆后序遍历，直到一次更改也不发生。这个算法正是
一般CFG的增量支配算法
已知某CFG的支配树，能否快速求出新增节点或边后新CFG的支配树吗？
先考虑新增一个节点$x$。为了保证CFG的可达性，在新增节点的同时还需要新增一条边$(s, x)$。此时，以$s$为父亲，插入$x$到$DomTree$上即可。
再考虑新增一条边的情况。需要下面的定理来导出算法。
$$\begin{cases}\mathrm{Ancestors}_{DomTree’}(x)\subseteq\mathrm{Ancestors}_{DomTree}(x)\\\mathrm{Descendants}_{DomTree’}(x)\subseteq\mathrm{Descendants}_{DomTree}(x)\end{cases}$$
依据
- 新增一条边后，如何快速地找出需要更新的节点？见
。 - 以什么顺序添加节点和边能较快地增量构造支配树？见
。
为了缩减篇幅，下文的$\mathrm{Ancestors}_{DomTree}$、$\mathrm{Parent}_{DomTree}$和$\mathrm{StrictAncestors}_{DomTree}$不再加下标。
支配树上最小范围的更新传播
新增一条边后$(s, x)$，只有$x$的前驱集可能发生了变化，即：
$$\mathrm{Pred}’(x)=\mathrm{Pred}(x)\cup\{s\}$$
所以我们只需要更新$x$的父亲为：
注意：
实际实现时，
$$\mathrm{Parent}(x)\in\mathrm{Ancestors}(s)$$
等价的控制流表述为：
$$\mathrm{idom}(x)\in\mathrm{Doms}(s)$$
- 向CFG添加重边不会使支配树发生变化，由
即证； - 反证法：假设$\mathrm{idom}(x)\notin\mathrm{Doms}(s)$，那么存在不经过$\mathrm{\mathrm{idom}(x)}$的路径$Entry\xrightarrow{*}s\rightarrow x$，矛盾。
形象地来说，
随着$x$的父亲变更，CFG上所有从$x$出发可达的节点都可能需要更新父亲。这部分节点是哪些？它们的父亲又应当更新为哪个节点呢？
$$\mathrm{DomUpdate}(\mathcal{X},q):=\{y\mid{}\begin{aligned}[t]&~q\in\mathrm{StrictAncestors}(\mathrm{Parent}(y))\\\land&~\exists x(\begin{aligned}[t]&~x\in\mathcal{X}\\\land&~x\notin\mathrm{Ancestors}(y)\\\land&~\exists z(z\in\mathrm{Pred}(y)\land x\in\mathrm{Ancestors}(z)))\}\end{aligned}\end{aligned}$$
并且对于属于$\mathrm{DomUpdate}(\mathcal{X},q)$且不属于$\mathcal{X}$的$y$有：
$$\mathrm{LCA’}(\mathrm{Pred}(y))=q$$
先证明属于$\mathrm{DomUpdate}(\mathcal{X},q)$且不属于$\mathcal{X}$的$y$满足$\mathrm{LCA’}(\mathrm{Pred}(y))=q$。$y$有前导在$\mathcal{X}$的某个元素$x$的子树中，而由$x\notin\mathrm{Ancestors}(y)$可以知道$y$也有前导不在$x$的子树中，这样$\mathrm{LCA}’(\mathrm{Pred}(y))=\mathrm{LCA}(\mathrm{Parent}(y),q)$。又由于$q\in\mathrm{StrictAncestors}(\mathrm{Parent}(y))$，可得$\mathrm{LCA}(\mathrm{Parent}(y),q)=q$。
再证明不在$\mathcal{X}$且不在$\mathrm{DomUpdate}(\mathcal{X},q)$中的$y$满足$\mathrm{LCA}’(\mathrm{Pred}(y))\neq\mathrm{Parent}(y)$：
- $q\notin\mathrm{StrictAncestors}(\mathrm{Parent}(y))$：对于$\mathcal{X}$中的所有$x$，一定有$\mathrm{Pred}(y)$不全在$x$的子树上
（否则$\mathrm{LCA}(\mathrm{Pred}(y))$也在$x$的子树上，则$x$支配$y$，由于更新前$p_x$严格支配$x$且$q$严格支配$p_x$，故$q\in\mathrm{StrictAncestors}(\mathrm{Parent}(y))$，矛盾） 。- 若$\forall x\in\mathcal{X}$，$\mathrm{Pred}(y)$都不在$x$的子树上：$\mathrm{LCA}(\mathrm{Pred})(y)$不变。
- 若$\exists x\in\mathcal{X}$，存在$u\in\mathrm{Pred}(y)$在$x$的子树上：一定有$\mathrm{LCA}(\mathrm{Pred}(y))\in\mathrm{Ancestors}(q)$
（既有前驱在$x$的子树上，又有前驱不在$x$的子树上，因此$\mathrm{LCA}(\mathrm{Pred}(y))\in\mathrm{Ancestors}(p_x)$，由$q\in\mathrm{StrictAncestors}(p_x)$，所以要么$\mathrm{LCA}(\mathrm{Pred}(y))\in\mathrm{Ancestors}(q)$，要么$q\in\mathrm{StrictAncestors}(\mathrm{LCA}(\mathrm{Pred}(y)))$，后者与假设矛盾） ，由此更新后，$\mathrm{LCA}(\mathrm{Pred}(y))$是$\mathrm{Pred}(y)$的公共祖先。现要证明更新后，$\mathrm{LCA}(\mathrm{Pred}(y))$的孩子中，有至少两个是$\mathrm{Pred}(y)$某元素的祖先。- 若$\mathrm{LCA}(\mathrm{Pred}(y))=q$：取$\mathrm{Pred}(y)$中在$x$子树中的元素$u$和不在$x$子树中的元素$v$，更新后$u$到达$q$经过$x$，$v$到达$q$则不经过$x$。
- 若$\mathrm{LCA}(\mathrm{Pred}(y))\in\mathrm{StrictAncestors}(q)$：所有$\mathrm{Pred}(y)$到达$\mathrm{LCA}(\mathrm{Pred}(y))$经过的孩子是不变的
（$\mathrm{Pred}(y)$中那些在$\mathcal{X}$某元素子树中的本来就有祖先$q$；不在任何$\mathcal{X}$元素子树中的祖先集合就没变） 。
- $\forall x(x\in\mathcal{X}\rightarrow x\in\mathrm{Ancestors}(y)\lor\forall z(z\in\mathrm{Pred}(y)\rightarrow x\notin\mathrm{Ancestors}(z)))$：
- 若$\forall x\in\mathcal{X}$，$\mathrm{Pred}(y)$都不在$x$的子树上：$\mathrm{LCA}(\mathrm{Pred})(y)$不变。
- 若有至少一个$\mathcal{X}$的元素是$y$的祖先：令它们的$\max$为$x$，则$\mathrm{Pred}(y)$都在$x$的子树上，子树不变，所以$\mathrm{LCA}(\mathrm{Pred}(y))$不变。
- 将$(s, x)$添加到CFG上
- $q\leftarrow\mathrm{LCA}(\mathrm{Parent}(x),s)$
- 如果$\mathrm{Parent}(x)\neq q$
- $\mathrm{Parent}(x)\leftarrow q$
- $\mathcal{X}\leftarrow\{x\}$
- 循环：$\mathcal{X}\leftarrow\mathrm{DomUpdate}(\mathcal{X}, q)$，如果$\mathcal{X}\neq\varnothing$：
- 循环：对于$y\in\mathcal{X}$：
- $\mathrm{Parent}(y)\leftarrow q$
- 循环：对于$y\in\mathcal{X}$：
首先，我们会发现：
这告诉我们，挨个算的结果也一样。进一步，由于并的结合律和交换率，只要避免$\mathrm{DomUpdate}$重复计算，可以FIFO，可以LIFO，都能有一样的结果。那么如何避免重复计算？先应用更改即$\mathrm{Parent}(y)\leftarrow q$，再enqueue即可。这样就无需任何散列表之类的数据结构。
接着，我们来考虑优化$\mathrm{DomUpdate}(\{x\})$的计算。
- 判断$x\notin\mathrm{Ancestors}(y)\land\exists z(z\in\mathrm{Pred}(y)\land x\in\mathrm{Ancestors}(z)))$：可以搜索$x$的子孙，找到流出其控制区域的出边
（这个概念几乎就是支配边界） 。这就有两个问题：如何搜索子孙？如何判断边$(w,y)$流出控制区域？前者稍后说，先考虑后者。借助，知$\mathrm{Parent}(y)$支配$w$。由于$x$也支配$w$，故而要么$\mathrm{Parent}(y)$严格支配$x$，要么$x$支配$\mathrm{Parent}(y)$。前者说明是流出控制区域，只需要用 即可快速分辨。 - 判断$q\in\mathrm{StrictAncestors}(\mathrm{Parent}(y))$：先前的检测确保了$\mathrm{Parent}(y)$严格支配$x$，由于$q$也严格支配$x$，故而要么$q$严格支配$\mathrm{Parent}(y)$，要么$\mathrm{Parent}(y)$支配$q$，前者就是我们想要的，同样只需要用
即可快速分辨。
如何所搜$x$的子孙？构建支配树时我们会维护一个动态的$\mathrm{Parent}$数组，如果还要维护动态的$\mathrm{Children}$数组太慢了。可否顺着CFG遍历？答案是可行的，因为支配子树的节点可以从子树的根出发，不经过子树外的节点遍历完。然而这需要散列表之类的数据结构标记是否遍历过。有没有更好的？答案就是顺着DFST遍历。
进一步，遍历子树可以和$\mathrm{DomUpdate}$的迭代共享一个工作队列，最后优化的算法如下：
- 将$(s, x)$添加到CFG上，并初始化$S$为工作队列
- $q\leftarrow\mathrm{LCA}(\mathrm{Parent}(x),s)$
- 如果：$\mathrm{Parent}(x)\neq q$
- $S.\mathrm{push}((x, \mathrm{Parent}(x)))$
- $\mathrm{Parent}(x)\leftarrow q$
- 循环：如果$S$非空：
- $(t, p)\leftarrow S.\mathrm{pop}()$
- 循环：对于$t$的每个出边$e=(t, y)$：
- $p_y\leftarrow\mathrm{Parent}(y)$
- 如果：$\mathrm{RevPostOrder}(p_y)\leq\mathrm{RevPostOrder}(p)$
- 如果：$\mathrm{RevPostOrder}(p_y)>\mathrm{RevPostOrder}(q)$：
- $S.\mathrm{push}((y, p_y))$
- $\mathrm{Parent}(y)\leftarrow q$
- 如果：$\mathrm{RevPostOrder}(p_y)>\mathrm{RevPostOrder}(q)$：
- 否则如果：$e$是DFST的树边：
- $S.\mathrm{push}((y, p))$
快速CFG增量顺序
算法比较
支配边界算法
$$\mathrm{DF}(x)=\{y|x\notin\mathrm{StrictDoms}(y)\land\exists p(p\in\mathrm{Pred(y)}\land x\in\mathrm{Doms}(p))\}$$
按定义，有可能$x\in\mathrm{DF}(x)$。直观理解支配边界就是支配从有到无的界线。接着对于节点$x$，我们引入序列：
$$\begin{cases}\mathrm{DF}^{(i)}(x)\equiv\mathrm{DF}(x),&i=0\\\mathrm{DF}^{(i)}(x)=\mathrm{DF}^{(i-1)}(x)\cup\bigcup_{y\in\mathrm{DF}^{(i-1)}(x)}\mathrm{DF}(y),&i=1,2,\dots\end{cases}$$
注意到：
- 序列单调递增：$\mathrm{DF}^{(i)}(x)\subseteq\mathrm{DF}^{(i+1)}(x),i=0,1,\dots$
- 序列有上界，且上界为有限集：$\mathrm{DF}^{(i)}(x)\subseteq N,i=0,1,\dots$
故存在最小上界，称作$x$的支配边界闭包，记作$\mathrm{DF}^+(x)$。
