支配树（Dominator Tree）是编译器优化和程序分析中的核心数据结构。在控制流图中，若从入口节点到节点 v 的所有路径都必须经过节点 d，则称 d 支配 v。支配树高效地编码了这种支配关系，广泛应用于静态单赋值形式（SSA）构造、程序切片和死代码消除。
算法原理
- 直接支配者（Immediate Dominator, idom）：严格支配
v且不被任何其他严格支配者支配的节点。 - 支配树：以入口节点为根，每个节点的父节点为其直接支配者。
- Lengauer-Tarjan算法：基于并查集和半支配者（Semi-Dominator）的线性时间算法。
为简化实现，本文采用迭代数据流分析方法求直接支配者，更易于理解。
核心算法实现
import java.util.*;
/**
* 支配树求解器（基于迭代数据流分析）
* 计算有向图中每个节点的直接支配者
*/
public class DominatorTree {
private final int n; // 节点数
private final int start; // 入口节点
private final List<Integer>[] graph; // 原图邻接表
private final List<Integer>[] reverse; // 反向图
private int[] dom; // 直接支配者数组
private Set<Integer>[] domSet; // 支配集（用于调试验证）
@SuppressWarnings("unchecked")
public DominatorTree(int n, int start) {
this.n = n;
this.start = start;
this.graph = new ArrayList[n];
this.reverse = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
reverse[i] = new ArrayList<>();
}
}
/**
* 添加有向边 u -> v
*/
public void addEdge(int u, int v) {
graph[u].add(v);
reverse[v].add(u);
}
/**
* 计算支配树，返回每个节点的直接支配者
*/
public int[] compute() {
dom = new int[n];
Arrays.fill(dom, -1);
dom[start] = start; // 入口节点的直接支配者为自己
// 初始化：非入口节点的初始支配集为全节点集
@SuppressWarnings("unchecked")
Set<Integer>[] D = new HashSet[n];
for (int i = 0; i < n; i++) {
D[i] = new HashSet<>();
for (int j = 0; j < n; j++) D[i].add(j);
}
D[start].clear();
D[start].add(start);
// 迭代数据流方程：D[n] = {n} ∪ (∩ D[p] for p in pred(n))
boolean changed = true;
while (changed) {
changed = false;
for (int v = 0; v < n; v++) {
if (v == start) continue;
Set<Integer> newD = new HashSet<>();
newD.add(v);
// 交集：所有前驱的支配集之交
if (!reverse[v].isEmpty()) {
boolean first = true;
for (int p : reverse[v]) {
if (first) {
newD.addAll(D[p]);
first = false;
} else {
newD.retainAll(D[p]);
}
}
}
if (!newD.equals(D[v])) {
D[v] = newD;
changed = true;
}
}
}
// 从支配集提取直接支配者
for (int v = 0; v < n; v++) {
if (v == start) continue;
// idom(v) 是严格支配v的节点中，离v最近的那个
// 即 D[v] - {v} 中不被其他严格支配者支配的节点
Set<Integer> strict = new HashSet<>(D[v]);
strict.remove(v);
for (int d : new HashSet<>(strict)) {
for (int other : strict) {
if (d != other && D[d].contains(other)) {
strict.remove(other);
}
}
}
// 剩下的唯一节点就是直接支配者
if (!strict.isEmpty()) {
dom[v] = strict.iterator().next();
}
}
this.domSet = D;
return dom;
}
/**
* 获取节点v的直接支配者
*/
public int getIdom(int v) {
return dom[v];
}
/**
* 判断d是否支配v
*/
public boolean dominates(int d, int v) {
return domSet[v].contains(d);
}
/**
* 构建支配树并打印
*/
public void printDominatorTree() {
System.out.println("=== 支配树结构 ===");
for (int v = 0; v < n; v++) {
if (dom[v] != -1) {
System.out.println("节点 " + v + " 的直接支配者: " + dom[v]);
}
}
// 构建树形结构
Map<Integer, List<Integer>> tree = new HashMap<>();
for (int v = 0; v < n; v++) {
if (dom[v] != -1) {
tree.computeIfAbsent(dom[v], k -> new ArrayList<>()).add(v);
}
}
System.out.println("
树形结构（" + start + " 为根）：");
printTree(tree, start, 0);
}
private void printTree(Map<Integer, List<Integer>> tree, int node, int depth) {
System.out.println(" ".repeat(depth) + node);
if (tree.containsKey(node)) {
for (int child : tree.get(node)) {
printTree(tree, child, depth + 1);
}
}
}
public static void main(String[] args) {
// 构建示例控制流图
// 0 -> 1 -> 2 -> 4
// 1 -> 3 -> 4
// 2 -> 3
DominatorTree dt = new DominatorTree(5, 0);
dt.addEdge(0, 1);
dt.addEdge(1, 2);
dt.addEdge(1, 3);
dt.addEdge(2, 4);
dt.addEdge(2, 3);
dt.addEdge(3, 4);
dt.compute();
dt.printDominatorTree();
System.out.println("
验证：");
System.out.println("0 支配 4? " + dt.dominates(0, 4));
System.out.println("1 支配 4? " + dt.dominates(1, 4));
System.out.println("2 支配 4? " + dt.dominates(2, 4));
System.out.println("3 支配 4? " + dt.dominates(3, 4));
}
}
Lengauer-Tarjan算法简介（进阶）
对于大规模图，迭代数据流分析 O(N^2 * E) 的复杂度难以接受。Lengauer-Tarjan算法在 O(E * α(E,N)) 近似线性时间内求解支配树：
- 对图进行DFS，记录每个节点的先序编号。
- 计算每个节点的半支配者（Semi-Dominator），即从祖先可达的最小先序节点。
- 利用并查集维护桶（Bucket）结构，从半支配者推导出直接支配者。
该算法是现代编译器（如LLVM、GCC）中SSA构造的标准实现。
复杂度分析
- 迭代数据流分析：
O(N^2 * E)最坏情况，但收敛速度快，适合中小规模图。 - Lengauer-Tarjan算法：
O(E * α(E,N))，其中α为阿克曼函数反函数，实际接近线性。 - 空间复杂度：
O(N + E)，存储图结构和支配集。
应用场景
- SSA形式构造：编译器将程序转换为静态单赋值形式时，需要在汇合点插入Phi函数，支配树决定插入位置。
- 程序切片：分析变量影响范围时，沿支配树剪枝无关代码。
- 死代码消除：不可达代码块在支配树中表现为无入口分支。
- 控制流扁平化检测：反编译工具利用支配树识别被混淆的控制流。
总结
支配树将复杂的图支配关系编码为简洁的树形结构，是连接图论与编译器优化的重要桥梁。本文通过迭代数据流分析实现了基础版本，展示了支配关系的计算过程。对于生产环境，建议采用Lengauer-Tarjan算法以获得线性时间复杂度。
