在编译器进行后端优化的时候，会使用支配树来构造SSA。支配树的生成算法有好几种，这里我们介绍一下最暴力的方法。（Opcache则是使用其他算法来实现，我们可以搜索论文A Simple, Fast Dominance Algorithm找到）
基本定义
支配
在一个图里面，有两个点u和w，如果从图的源顶点出发，必须经过u才能到达w，那么我们称u支配w。
如下图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| ┌────────────┐
│ 1 │
│ │
└────────────┘
│
│
│
│
▼
┌────────────┐
│ 2 │
│ │
└────────────┘
│
┌───────────────────────┴───────────────────────┐
│ │
▼ ▼
┌────────────┐ ┌────────────┐
│ 3 │ │ 4 │
│ │ │ │
└────────────┘ └────────────┘
│ │
│ │
└────────────────────────┬───────────────────────┘
│
▼
┌────────────┐
│ 5 │
│ │
└────────────┘
|
那么有如下支配关系：
1
2
| 1支配2，1支配3，1支配4，1支配5
2支配3，2支配4，2支配5
|
因为3和4都可以到达5，所以3和4不支配5。
直接支配
如果u支配w，而w的其他支配者支配u，则节点u被认为是节点w的直接支配者，表示为idom (w)。
如下图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| ┌────────────┐
│ 1 │
│ │
└────────────┘
│
│
│
│
▼
┌────────────┐
│ 2 │
│ │
└────────────┘
│
┌───────────────────────┴───────────────────────┐
│ │
▼ ▼
┌────────────┐ ┌────────────┐
│ 3 │ │ 4 │
│ │ │ │
└────────────┘ └────────────┘
│ │
│ │
└────────────────────────┬───────────────────────┘
│
▼
┌────────────┐
│ 5 │
│ │
└────────────┘
|
那么有如下直接支配关系：
1
2
| 1直接支配2
2直接支配3，2直接支配4，2直接支配5
|
我们发现，1和2都支配着3、4、5。但是，因为1支配了2，所以，按照直接支配的定义，2才是3、4、5的直接支配。
定理
1.除了图的源点外，其他点至少有一个点支配着它。
我们从上面的直接支配点可以看出，2、3、4、5都被支配着。
2.除了图的源点外，其他点只有一个点直接支配着它。（我们可以结合上面的例子来理解）
支配树
我们可以通过edges {(idom(w),w)}来得到支配树。其中，有向图的源点就是支配树的根。
生成支配树的算法
DFS树
可以通过DFS来遍历有向图：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public function domDFS(Vertex $vertex)
{
if (!$this->isVisited($vertex)) {
$this->visitedVertexs[$vertex->name] = true;
foreach ($vertex->nexts as $next) {
if (!$this->isVisited($next)) $this->domDFS($next);
}
}
}
public function computeDominatorTree()
{
foreach ($this->predOrder as $parent) {
$this->visitedVertexs = [];
$this->visitedVertexs[$parent->name] = true;
$this->domDFS($this->predOrder[0]);
foreach ($this->predOrder as $child) {
if (!$this->isVisited($child)) {
$child->dominator = $parent;
}
}
}
}
|
实际上，这个算法很好理解，非常的直观暴力，但是我们还是来解释下。
前提，对图进行深度优先遍历，得到一组序列。
从第一个序列开始，每次取出一个序列，我们记作s。然后重新对图进行深度优先遍历，但是，如果遇到了当前这个点s，就停止往s这个点后面的点深度遍历了，开始回退，深度遍历其他的点。我们把每一个遍历到的点保存下来，比如放在一个visitedMap里面。最后，我们和所有的点进行对比，不在visitedMap里面的点，就是被当前s这个点支配的。一直重复下去，可以得到每一个点的直接支配点。最终，得到支配树。
在演算的过程中我们发现，对于这个算法，如果有两个点（记作v1、v2）可以到达第三个点（记作v3）。那么，当选取v1或者v2进行深度遍历的时候，visitedMap会保存所有的顶点。也就意味着，v1和v2不支配任何点。
