Dominance 支配关系算子集

算子类别：Dominance（有向图支配关系与支配边界）

算法数量：2 个

适用阶段：控制流分析、流程依赖分析、程序结构分析、关键控制节点识别、路径必经关系判断、支配边界计算

产品定位：为“从入口节点出发，哪些节点一定会经过 / 谁支配谁 / 控制流在哪里发生合流 / 变量或状态影响范围在哪里结束”提供统一的有向图支配关系分析能力底座。

---

一、算子集概述

Dominance 算子集主要面向有向图中的支配关系分析，常见于程序控制流图、流程图、状态转移图、任务依赖图等场景。

在一个有向图中，给定入口节点 start，如果从 start 到某个节点 v 的所有路径都必须经过节点 u，则称 u 支配 v。这类关系可以帮助回答：

1. 必经节点分析

   • 从入口到目标节点，哪些节点是必经节点？
   • 某个节点是否控制了后续一批节点的可达路径？
   • 典型算法：immediate_dominators

2. 直接支配关系

   • 谁是某个节点最近的必经上游？
   • 如何构建支配树？
   • 典型算法：immediate_dominators

3. 控制流合流边界

   • 一个节点的影响范围在哪里发生分叉或合流？
   • 变量定义、状态变化或控制条件的影响边界在哪里？
   • 典型算法：dominance_frontiers

---

二、算子能力分类

能力类型	对应算子	功能描述
直接支配关系	immediate_dominators	计算每个节点的直接支配节点，用于构建支配树
支配边界	dominance_frontiers	计算每个节点的支配边界，用于识别控制流合流点和影响范围边界

---

三、通用输入输出约定

3.1 输入（Input）

• G：有向图 DiGraph
• start：入口节点 / 起始节点
  • 支配关系是相对于入口节点定义的
  • 只有从 start 可达的节点才具有清晰的支配关系语义

3.2 输出（Output）

• immediate_dominators：dict[node, node]

  • key：节点
  • value：该节点的直接支配节点
  • 通常 start 的直接支配节点是它自身

• dominance_frontiers：dict[node, set[node]]

  • key：节点
  • value：该节点的支配边界节点集合

说明：支配关系主要用于有向图。如果图中存在从 start 不可达的节点，这些节点通常不会出现在支配关系结果中，或需要在业务层单独处理。

---

四、算子详细说明

1. immediate_dominators —— 直接支配节点

功能说明
计算从入口节点 start 出发时，每个可达节点的直接支配节点。

如果节点 u 支配节点 v，表示从 start 到 v 的所有路径都必须经过 u。而 v 的直接支配节点是所有支配 v 的节点中距离 v 最近的那个支配者。

产品价值

• 识别流程中的必经控制点
• 构建支配树，理解流程或程序的控制结构
• 找出某个节点对后续节点的控制范围
• 判断某些步骤是否一定发生在另一些步骤之前

典型场景

• 程序控制流分析：判断基本块之间的必经关系
• 编译器优化：构建支配树，为 SSA 转换和优化做准备
• 审批流程：识别所有路径都会经过的关键审批节点
• 任务流程：判断某任务是否是到达后续任务的必经步骤
• 状态机分析：识别进入某状态前必经的状态节点

关键参数

• G：有向图
• start：入口节点

适用与特性

• 图类型：有向图
• 输出：dict[node, node]
• 复杂度：通常接近线性级别，适合控制流图和流程图分析
• 注意：结果只对从 start 可达的节点具有明确意义

可直接回答的问题

• “从入口节点开始，哪些节点是到达目标节点的必经节点？”
• “每个节点最近的必经上游是谁？”
• “这个流程图的支配树是什么？”
• “某个审批节点是否支配后续所有关键节点？”

---

2. dominance_frontiers —— 支配边界

功能说明
计算每个节点的支配边界。对于节点 u，其支配边界可以理解为：u 的支配影响开始“失效”或发生合流的位置。

更直观地说，如果 u 支配某些路径上的前驱节点，但不严格支配某个合流节点，那么这个合流节点通常会出现在 u 的支配边界中。

产品价值

• 识别控制流合流点
• 判断变量、状态或条件影响范围的边界
• 支持程序分析中的 SSA φ 函数插入位置判断
• 帮助分析流程分支在哪里重新汇合

典型场景

• 编译器 SSA 构建：确定 φ 函数插入位置
• 程序控制流图：识别 if/else、循环等结构的合流节点
• 审批流程：识别不同审批路径重新汇合的位置
• 状态机分析：找出状态影响范围的边界
• 数据流分析：判断变量定义影响到哪些合流点

关键参数

• G：有向图
• start：入口节点

适用与特性

• 图类型：有向图
• 输出：dict[node, set[node]]
• 通常基于直接支配关系进一步计算
• 适合控制流、流程流转、依赖图中的合流结构分析

可直接回答的问题

• “某个控制条件的影响边界在哪里？”
• “流程分支在哪里重新汇合？”
• “哪些节点需要合并来自不同路径的状态？”
• “在控制流图中，哪些位置需要插入 φ 函数？”

---

五、推荐使用指南（怎么选）

• 想知道谁是每个节点最近的必经上游：使用 immediate_dominators
• 想构建支配树，分析流程控制结构：使用 immediate_dominators
• 想知道分支或状态影响在哪里合流：使用 dominance_frontiers
• 想做程序控制流、SSA、变量定义影响范围分析：先用 immediate_dominators，再用 dominance_frontiers
• 图中存在多个入口时：建议新增一个虚拟入口节点，连接所有入口后再计算支配关系
• 图中存在不可达节点时：建议先从 start 做可达性过滤，再分析支配关系

---

六、可直接回答的典型问题

• “从入口节点 S 出发，每个节点的直接支配节点是谁？”
• “目标节点 T 的所有路径是否都必须经过节点 A？”
• “这个流程图的支配树是什么？”
• “哪些节点是流程中的关键必经控制点？”
• “某个条件分支的影响范围在哪里结束？”
• “流程中哪些节点是多个分支的合流点？”
• “在控制流图中，哪些位置需要插入 φ 函数？”
• “多个入口的流程图如何统一做支配关系分析？”

---

七、工程落地注意事项

1. 支配关系必须指定入口节点

   • 支配关系不是图的绝对属性，而是相对于 start 定义的。
   • 不同入口节点可能产生完全不同的支配树和支配边界。

2. 只分析从入口可达的节点

   • 从 start 不可达的节点不具备明确支配语义。
   • 工程中建议先过滤出可达子图，或将不可达节点单独标记。

3. 多个入口建议增加虚拟入口

   • 如果流程有多个起点，可以新增 virtual_start。
   • 从 virtual_start 指向所有真实入口，再计算支配关系。

4. 支配不等于父子关系

   • 支配关系表示“所有路径都必须经过”。
   • 它不一定等同于原图中的直接边关系，也不等同于业务层级父子关系。

5. 支配边界适合分析合流点

   • dominance_frontiers 常用于识别分支汇合、状态合并、变量合并位置。
   • 在普通业务流程中，可解释为“某个控制节点影响力开始失去唯一控制的位置”。

6. 有环图也可以分析，但要注意解释

   • 控制流图通常包含循环，支配算法可以处理这类结构。
   • 但业务解释时需要区分循环体入口、回边和普通流程边。

7. 适合与 DAG / Path / Connectivity 类算法配合

   • 可先用可达性或连通性算法确认入口可达范围。
   • 再用 Dominance 分析必经节点与合流边界。
   • 对流程图还可结合拓扑、环检测、强连通分量等能力做结构诊断。

---

八、算子清单

序号	算子名称	中文说明
1	immediate_dominators	直接支配节点计算
2	dominance_frontiers	支配边界计算