13 Loop Optimizations¶

循环优化是编译器后端最重要的优化之一——程序的大部分执行时间集中在循环中，因此优化循环对整体性能影响巨大。核心流程分两步：先在控制流图中识别循环，再对循环体应用变换（如代码外提）。

13.1 Loops and Dominators¶

在做任何优化之前，编译器必须精确知道"循环在哪里"。这需要从控制流图 (CFG) 中构建支配关系的数学模型。

13.1.1 What is a Loop¶

在编译器的优化阶段，"循环"不是源码层面的 while/for 语法结构，而是 CFG 中具有特定结构的一组节点。

定义：设 CFG 中有一组节点 \(S\) 和一个头节点 (Header) \(h\)。\(S\) 构成一个循环，当且仅当满足以下三个条件：

可达性：\(S\) 中任意节点都有一条路径到达 \(h\)。
连通性：从 \(h\) 出发有路径到达 \(S\) 中任意节点。
唯一入口：除 \(h\) 外，没有来自 \(S\) 外部的边指向 \(S\) 内部的节点。

关键性质：循环必须有且仅有一个入口（头节点），但可以有多个出口。

13.1.2 Dominators¶

支配关系是识别循环的数学基础。

定义：节点 \(d\) 支配 (Dominate) 节点 \(n\)，记作 \(d \text{ dom } n\)，当且仅当从 CFG 入口节点到 \(n\) 的每一条路径都必须经过 \(d\)。

基本性质：

每个节点支配它自己：\(d \text{ dom } d\)（自反性）
若 \(a \text{ dom } b\) 且 \(b \text{ dom } c\)，则 \(a \text{ dom } c\)（传递性）
入口节点支配所有节点

以上图为例，d dom n 从流图的入口结点 s0 到结点 n 的每条路径都经过节点 d

直接支配节点 (Immediate Dominator, idom)：节点 \(n\) 的直接支配节点是离 \(n\) 最近的那个严格支配 \(n\) 的节点。记作 \(\text{idom}(n)\)。除入口节点外，每个节点有唯一的直接支配节点。

支配集的计算 — 迭代不动点算法：

\[ D[s_0] = \{s_0\} \qquad D[n] = \{n\} \cup \left( \bigcap_{p \in \text{pred}[n]} D[p] \right) \quad \text{for } n \neq s_0 \]

入口节点 \(s_0\) 仅支配自身。
其他节点 \(n\) 的支配集 = \(\{n\} \cup\)（所有前驱节点支配集的交集）。

算法步骤：先假设除入口外所有节点的 \(D[n]\) 为全集，然后按上述公式迭代更新，直到所有 \(D[n]\) 不再变化（到达不动点）。直观理解：\(n\) 的支配者必须是每个前驱的支配者——如果某节点没有支配某个前驱，那它就无法保证支配 \(n\)。

13.1.3 Dominator Tree¶

将直接支配关系组织成树结构，即支配树 (Dominator Tree)：

树的边 \(d \to n\) 表示 \(\text{idom}(n) = d\)。
支配树将复杂的 CFG 转化为树形结构，便于分析嵌套关系和快速判断支配性。

13.1.4 Natural Loops¶

编译器优化通常针对自然循环 (Natural Loop)——一种结构良好、易于分析的循环形式。

回边 (Back Edge)：边 \(n \to h\) 满足 \(h \text{ dom } n\)（边的终点支配起点）。回边是识别循环的关键信号。

构造自然循环：给定回边 \(n \to h\)，其自然循环包含所有满足以下条件的节点 \(x\)：

\(h \text{ dom } x\)（\(h\) 支配 \(x\)）
存在从 \(x\) 到 \(n\) 的路径，且该路径不经过 \(h\)

其实就是先选一个回边，然后从 \(x\) 开始沿着前驱节点把路过的节点全部抓进环里

构造回边 x→h 的自然环：
1. Loop ← {h}
2. WorkList ← {x}
3. 当 WorkList 非空时：
    - 取出节点 p
    - 如果 p ∉ Loop：
    - 将 p 加入 Loop
    - 将 p 的所有前驱节点加入
WorkList (但不包括回边 x→h)

特点：自然循环具有唯一的头节点作为入口，所有优化变换都在自然循环上进行。

在右下图中, {a, b, c} 是一个 natural loop 吗？

图中存在两条回边：c→a（a dom c）和 d→b（b dom d）。

{a, b, c} 不是自然循环：因为存在 d→b 这条边，使得从外部可以直接跳入 b——进入 {a,b,c} 的路有两条（经 a 或经 d），b 不是唯一入口，不满足唯一入口条件。

实际的嵌套结构： - 内层自然循环 {b, c, d} — 回边 d→b，头节点 b。除 b 外无外部边进入 c 或 d。 - 外层自然循环 {a, b, c, d} — 回边 c→a，头节点 a。整个区域只有 a 一个外部入口。

13.1.5 Loop-Nest Tree¶

循环之间可能存在嵌套关系。循环嵌套树 (Loop-Nest Tree) 描述这种层次结构：

如果循环 \(B\) 的所有节点都包含在循环 \(A\) 内部，则 \(B\) 是 \(A\) 的子循环。
最内循环 (Innermost Loop)：不包含任何子循环的叶子节点——通常是最热的优化目标。
不相交的循环（头节点不同且区域不重叠）在树中是兄弟关系。

比如说上图中，{8, 9} 就是 {5, 8, 9, 10} 的内层子循环。

构造算法：

计算 CFG 的支配关系，构建支配树。
找出所有自然循环，确定所有循环头节点。
对每个循环头节点 \(h\)，将其关联的所有自然循环合并为 \(\text{loop}[h]\)。
按包含关系构建树：若 \(h_2 \in \text{loop}[h_1]\)，则 \(h_1\) 在树中位于 \(h_2\) 之上（\(h_1\) 是外层，\(h_2\) 是内层）。

树中每个节点代表一个循环或一组循环的集合，父子关系即嵌套关系。

13.1.6 Loop Preheader¶

前置首结点 (Preheader) 是在循环头节点之前插入的一个额外基本块。所有从循环外部进入循环的边都先经过 preheader，再到达头节点。

作用：preheader 是代码外提等优化的插入点——外提的代码放置在 preheader 中，保证在循环开始前只执行一次。所有进入循环的路径都经过它，避免了沿部分路径重复执行的问题。

13.2 Loop Invariant Hoisting¶

循环不变代码外提是最经典也最有效的循环优化——将循环体内每次迭代结果都相同的计算移到循环外部，只算一次。

13.2.1 Definition¶

循环不变量 (Loop Invariant)：对于语句 x := v1 op v2，如果 v1 和 v2 的值在循环的任意两次迭代之间保持不变，则该语句计算的是循环不变量。

优化变换：

// 优化前                       // 优化后
while (condition) {             t := a + b        // 外提到 preheader
    ...                         while (condition) {
    x := a + b    // 每次迭代     ...              // 直接使用 t
    ...                都重算      ...
}                               }

13.2.2 Identifying Invariants¶

判定语句 x := v1 op v2 是否为循环不变量，满足以下任一条件即可：

操作数是常量 — v1 和 v2 都是常量字面量。
定义在循环外 — 到达该语句的 v1（或 v2）的所有定义都在循环外部。
唯一的内部定义也是不变量 — 存在唯一定义到达该语句，且该定义本身已被判定为循环不变量。

示例:
    i := 0              // 循环外定义
    n := 100            // 循环外定义
    while (i < n) {
        x := n * 2      // 不变量 ★ — n 定义在循环外, 2 是常量
        y := x + i      // 非不变量 — i 每次迭代都变
        i := i + 1
    }

条件 3 支持传递判定——一旦 x := n * 2 被标记为不变量，后续使用 x 的语句 z := x + 5 也可被判定为不变量。

13.2.3 Safety Criteria¶

外提看似简单，但直接移动代码可能改变程序语义。必须同时满足以下三个条件才能安全外提：

条件 1：支配条件 (Dominance Condition)¶

外提语句的定义点必须支配循环中所有使用该变量的位置，否则外提后某些路径上变量未经定义就被使用。

如果错误地提升了这个赋值，无论如何t都会被赋值为a + b，改变了程序行为

条件 2：唯一定义条件 (Uniqueness Condition)¶

循环体内必须只有一个对该变量的定义。

条件 3：前置首结点非活跃条件 (Preheader Condition)¶

变量在循环入口（preheader 处）不能是活跃的 (live-in)。

三个条件共同保证：外提后程序对所有可能的执行路径产生完全相同的结果。

Comparison¶

	识别循环	支配分析	代码外提
输入	CFG	CFG (节点+边)	自然循环体
核心结构	回边 + 自然循环	支配树 (idom)	支配性 + 定义链
输出	循环集合 / 嵌套树	每个节点的支配者集合	外提后的优化代码
关键算法	DFS + 支配判定	迭代数据流 (Lengauer-Tarjan)	不变量判定 + 安全三条件

循环优化的核心思想可以概括为：用支配关系在 CFG 中精确定位循环结构，再将循环内每次迭代不变的代码提升到前置首结点，消除冗余计算。

评论区

对你有帮助的话请给我个赞和 star =>

欢迎跟我探讨！！！