文档介绍：第七章控制流分析
的形式化分析方法,它是数据流分析,依赖分析的根底.

3种：
用domin下列图来简洁阐述：
〈〈muchnick — 书>p184
思想：任取节点i属于Domin(n)-{n},固定i,依次检查 Domin(n)-{n}-{i}中节点
s,假设s属于Domin(i),贝U从Domin(n)中删除节点s,由于它不可能成为了节点 n的
idominator Domin(n)-{n}-{i} 中剩余节点 s之后,再改变节点 i,
domin(n)-{n}集合中只剩一个节点,该节点就是节点 n
的 idominator.
求Postdominator的算法与求 dominator的算法对称,只要把算法
的pred函数改为了succ函数就行了.
计算dominator的快速算法
该算法的详细介绍见 Lengauer and Tarjan A Fast Algorithm for Finding Dominators
in a Flowgraph
常规算法时间复杂度为了O(),快速算法的时间复杂度为了 O(n . &(e,n)), a
(e,n)是ackermann函数的倒数,增长非常缓慢.
先给一个定义sdom(w):
sdom(w) = min{ u| 存在路径 v0=u,v1, ••- ,vk=w且 vj>w (1<= j<= k-1) }
先对CF酢深度优先搜索,搜索树为了 T,里面的u, w, v1,…,vk都是T中先序遍历的访问顺序,后面经常就用这个顺序号来指代节点.
Sdom(w)表示：节点u有路径到达w,且路径上除u之外的其它节点的序号都大于 w.
取CF(^满足这个条件且序号最小的 u作为了sdom(w).
引入sdo前数的目的是由sdom可以计算idom(w)
由于算法比拟复杂,不能几句话说清晰,
出一些引理和定理,由它们得到sdom(w)的递推计算方法和基于 sdom®数的idom(w) 的递推计算方法,然后根据特定的顺序使用递推计算方法计算得到 sdom^idom.
引理和定理的意义不直观,可能需要了解证明过程才能清晰,可以查看上面的论文,这里只在附录中给出最重要的定理的证明. (引理123可以先跳过不看)
引理1:如果v,w都是 3的点,且v<=w,那么v到w的任何路径都要经过 v和w在深度优先树T上的公共祖先.
引理 2： sdom(w) -- + w; idom(w) -- * sdom(w)
sdom(w) -- + w 表示在 T 上 sdom(w)是 w 的祖先,且 sdom(w)!=w
idom(w) --* sdom(w)表示在 T上idom(w)是 sdom(w)的祖先,且有可能 idom(w)=sdom(w).
引理3:如果v,w满足v --* w , 那么或者有v --* idom(w) 或者有
idom(w) --* idom(v) .
定理1 :假设w!=r
sdom(w) = min(( v| (v,w) 属于 E and v < w } U ( sdom(u)| u>w and 存在边(v,w) 并且满足u --* v })
定理1就是sdom(w)的递推计算式.
定理一的证明：
设X等于上面等式的右边局部
一：证明 sdom(w) ux
如果(x, w)^E 且 x<w,那么,由 sdom 的定义和(x,w)n sdom(w)'x.
如果x = sdom(u) , u满足u〉w且ut *v且(v, w)在E,那么有路径l ：从 sdom(u)到u,从u到v,(u)到u上的节点的序号 auaw, 从u到v的路径上的节点序号也是 >u >w,所以sdom(w) 4 sdom(u) = x
二：证明 sdom(w) _x
sdom(w) =v0,v[,...,vj,vk = w (vj > w , 1壬 j<k—1)
设 k = 1,即(sdom(w), w) w E,且 sdom(w)T +wn sdom(w) < w,由 min 式前半局部有x= min (...)至sdom(w).
假设k A1,那么取j是满足vj T *vk」的那个最小的j ,假设有M苴vj ..1 S苴j —1 , 那么由引理一,存在 v] ...i M l M j — 1是vi和vj的公共祖先,即v] T