支配树是基于控制流图（CFG）构建的有根树，用于刻画节点间支配关系：若从入口节点到w的所有路径必经v，则v支配w；其核心用途包括SSA构造（插入ϕ函数）、循环优化与DCE等。
支配树是什么，和控制流图有什么关系
支配树（Dominator Tree）不是语法树或调用树，而是对有向图中“控制依赖”关系的压缩表达：节点 v 支配节点 w（记作 v dom w），当且仅当从起点（通常为入口节点 entry）到 w 的每条路径都必须经过 v。在编译器中，它直接用于构建控制流图（CFG）上的 SSA 形式、死代码消除、循环优化等——所以你看到的 llvm::DominatorTree 或 GCC 的 dom_info，底层都在算这个。
注意：支配关系只定义在**单一起点**的有向图上；若 CFG 有多个入口（如异常分发块），需先做图变换（例如加虚拟入口）再运行算法。
Lengauer-Tarjan 算法的核心步骤怎么写
它本质是基于深度优先搜索（DFS）的并查集加速算法，时间复杂度接近线性 O(E α(E,V))，比朴素的迭代数据流方法快得多。关键不在于背公式，而在于三步不能错：
- 第一步：对 CFG 做 DFS，记录
dfs_num和parent，生成 DFS 树，并反向标记每个节点的 children（即 DFS 树中的子节点） - Second step：按
dfs_num降序处理所有节点（除入口外），对每个节点v，执行eval(v)找其当前“半支配点”sdom(v)；eval内部用带路径压缩的并查集（但 union 按dfs_num小者为根） - Third step：按
dfs_num升序重新扫描节点，用sdom和已确定的idom更新直接支配者idom(v)：若sdom(w) == sdom(v)，则idom(v) = sdom(v)；否则idom(v) = idom(w)
别跳过 eval 中的“找最小 sdom”逻辑——它要遍历所有前驱（非 DFS 树边），并在并查集里 find 它们的 sdom 值，不是简单取 min。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
常见实现坑点：DFS 树方向、并查集 union 规则、sdom 初始化
三个最容易导致支配树错误的地方：
-
sdom(v)初始值必须设为v自身（不是INF），否则升序更新idom阶段会误判；Lengauer-Tarjan 原文明确写 “sdom[v] ← v” - 并查集的
union必须按dfs_num小者为根（不是按节点 ID），否则路径压缩后find返回的不是编号最小的祖先，sdom计算就偏了 - DFS 树必须以入口节点为根跑一次完整遍历；如果图不连通（比如 unreachable basic block），那些节点的
dfs_num为 0，应直接跳过处理——否则eval会访问未初始化内存
示例片段（伪代码关键行）：
sdom[v] = v;
for (u : predecessors(v))
if (dfs_num[u] != 0)
sdom[v] = min(sdom[v], dfs_num[find(u)]);
用现成库还是手写？Clang/LLVM 和 Boost.Graph 怎么选
除非你在写教学编译器或需要定制支配关系（比如支持多入口或带条件支配），否则别手写 Lengauer-Tarjan。LLVM 的 llvm::DominatorTreeBase 已高度优化，支持增量更新，且自动处理 PHI 节点语义；Boost.Graph 的 lengauer_tarjan_dominator_tree() 接口清晰但只输出静态树，不维护支配关系缓存。
如果你用 LLVM IR：
- 确保 CFG 是合法的（
BasicBlock有唯一TerminatorInst，无悬空分支） - 调用前先
DT.recalculate(F)，其中F是Function*；不要复用旧DominatorTree对象处理修改后的 CFG - 查询时用
DT.dominates(A, B)或DT.getNode(A)->getIDom()，后者返回的是DominatorTreeNode*，不是原始BasicBlock*
手写版本真正难的不是算法主干，而是把 CFG 抽象成 std::vector<:vector>></:vector> 后，前驱边（preds）的预计算容易漏边——尤其 PHI 指令引入的跨块边，必须显式建逆邻接表。
