Dominator Tree

释义 Definition

支配树（dominator tree）：在控制流图（CFG）中，用树结构表示“支配（dominate）”关系的数据结构。若从入口结点到某结点 n 的所有路径都必须经过结点 d，则称 d 支配 n；支配树把每个结点连接到它的直接支配者（immediate dominator），常用于编译器优化、程序分析与 SSA 构造等。

发音 Pronunciation (IPA)

/ˈdɑːmɪneɪtər triː/

例句 Examples

A dominator tree helps identify which blocks must execute before others.
支配树有助于识别哪些基本块必须在其他基本块之前执行。

In SSA construction, we compute the dominator tree of the control-flow graph to place φ-functions efficiently and to reason about dominance frontiers.
在构造 SSA 时，我们会计算控制流图的支配树，以高效放置 φ 函数，并用于分析支配边界。

词源 Etymology

dominator 来自拉丁语 dominari（统治、支配），在图论/程序分析语境中引申为“在所有路径上都必须经过的结点”；tree 表示用树状结构组织这种关系。该术语在编译器的控制流分析中被广泛采用，用来把“支配关系”以便于计算和遍历的形式表示出来。

相关词 Related Words

• Compiler
• Control-Flow Graph
• Dominator
• Immediate Dominator
• Dominance Frontier
• SSA Form
• Basic Block
• Data-Flow Analysis
• Optimization

文学与著作 Literary Works

• Compilers: Principles, Techniques, and Tools（Aho, Lam, Sethi, Ullman，“龙书”）——在控制流与优化相关章节讨论支配关系与相关概念。
• Advanced Compiler Design and Implementation（Steven Muchnick）——系统介绍支配关系、支配树及其在优化中的用途。
• “A Fast Algorithm for Finding Dominators in a Flowgraph”（Lengauer & Tarjan）——经典论文，提出高效求支配者/支配树的方法。
• Engineering a Compiler（Cooper & Torczon）——以工程化视角讲解 CFG、支配树、SSA 等编译器核心分析结构。