循环优化与必经节点

循环定义

循环 = 强连通子图 + 唯一入口节点（两条件必须同时满足）。

• 强连通：子图中任意两节点间均有路径
• 唯一入口：从循环外进入循环只能经过该节点

重点 循环两条件：强连通子图 + 唯一入口。

必经节点（Dominance）

定义

节点 $d$ 是节点 $n$ 的必经节点（$d$ dom $n$），当且仅当从程序入口到 $n$ 的所有路径都经过 $d$。

性质（偏序关系）

• 自反性：$n$ dom $n$
• 传递性：若 $a$ dom $b$ 且 $b$ dom $c$，则 $a$ dom $c$
• 反对称性：若 $a$ dom $b$ 且 $b$ dom $a$，则 $a=b$

必经节点集迭代算法

重点 必经节点集迭代算法（常用大题）。

$$D(n)=\{n\}\cup \left(\bigcap _{p\in P(n)}D(p)\right)$$

其中 $P(n)$ 是 $n$ 的所有前驱节点。

初始化：

• $D(n_0)=\{n_0\}$
• $D(n)=\{所有节点\}$（对 $n\ne n_0$）

迭代直到不动点：

• 对每个 $n\ne n_0$：$D(n)=\{n\}\cup {\bigcap }_{p\in P(n)}D(p)$

回边（Back Edge）

定义：边 $A\to B$ 是回边，当且仅当 $B$ dom $A$（$B$ 是 $A$ 的必经节点）。

重点 回边：$A\to B$ 且 $B$ dom $A$。

从回边找循环的栈算法

对每条回边 $A\to B$：

1. 初始化 $loop=\{B,A\}$
2. 从 $A$ 出发沿控制流图反向（前驱方向）DFS，将遇到的节点加入 $loop$
3. 重复直到到达 $B$ 为止
4. 最终 $loop$ 即为该回边对应的循环

找循环三步总结

重点 三步法是考试核心流程。

1. 计算必经节点集 $D(n)$（迭代至不动点）
2. 查找所有回边（$A\to B$ 且 $B$ dom $A$）
3. 从回边找循环（栈/DFS 反向搜索）

完成循环查找后，需通过 数据流分析 确定循环内变量的定值-引用关系，进而应用 循环优化算法（代码外提、强度削弱、归纳变量删除）进行循环优化。