DomAnalysis：计算支配边界

原论文：An Efficient Method of Computing Static Single Assignment Form

支配相关的概念就不重复叙述了，这里主要记录一下论文里的算法及其证明。

支配边界初始定义：
$$
DF(X)={Y|(\exist P \in pred(Y))(X支配P\ and\ X不支配Y)}
$$
按照该定义计算的话，对每个基本块算法复杂度都是平方级别的，我们希望实现一个线性算法计算一个基本块的DF。

我们把DF(X)拆成两个集合，一个是DF_local(X)，这一部分是X自己无法支配的，另一部分是DF_up(Z)(Z被X直接支配，也就是支配树上X的儿子)，这一部分是X的儿子无法支配的，传递性可知X无法支配。形式化的定义如下：
$$
DF_{local}(X)={Y|X\in pred(Y)\ and\ X不支配Y}
$$

$$
DF_{up}(Z)={Y|Y\in DF(Z)\ and\ X不支配Y}
$$

引理1：DF(X)=DF_local(X) + DF_up(Z)

充分性的证明如下：

首先由于X支配自己，显然DF_local(X)满足DF(X)的条件
其次由于DF_up(Z)要求X不支配Y，因此我们只需要证明X支配Y的一个前驱即可
Y属于DF(Z),说明Z支配Y的一个前驱，又因为X支配Z，由支配关系的传递性可知X支配Y的一个前驱

必要性的证明如下：

对于DF(X)中的一个基本块Y，依照定义，存在Y的一个前驱U，使得X支配U,但X不支配Y
若U=X，这种情况属于DF_local
否则一定存在X的一个儿子支配U(考虑支配树的形状),又因为X不支配Y,因此这个儿子也不支配Y，符合DF(Z)的定义，进而符合DF_up(Z)的定义

证明上述之后，我们需要求出DF_local(X)和DF_up(Z)

DF_local(X)我们改写成：
$$
DF_{local}(X)={Y|X\in pred(Y)\ and\ idom(Y)\neq X}
$$
同理，DF_up(X)我们也如此改写：
$$
DF_{up}(Z)={Y|Z\in DF(Z)\ and\ idom(Y)\neq X}
$$
由此，我们得到了迭代算法，我们自底向上遍历支配树（保证其儿子节点已经计算完DF），对每个节点X，先计算DF_local，再对于每个儿子Z,并上DF_up(Z),由此得到DF(X)

算法复杂度分析（支配树N个节点，E条边）：

计算DF_local时遍历了支配树的每条边，O(E)
传递DF_up时，每条边需要传递一次，每次最坏的情况是传递N个节点，因此最坏的情况O(N^2)
整体复杂度O(E+N^2)

但显然的是，这种最坏情况基本不可能出现，实际情况该算法通常有线性的复杂度