循环优化算法

循环优化不考大题（有小题）。

代码外提（Code Hoisting）

将循环内不变运算移至循环外的前置节点。

前置节点

在循环入口节点之前插入一个新基本块（前置节点），存放外提的运算。

不变运算判定

运算 x = y op z 在循环 L 中是不变的，当且仅当：

1. $y$ 和 $z$ 都是常数，或
2. $y$ 和 $z$ 的定值点在循环 L 外部，或
3. $y$ 和 $z$ 的定值点到达该运算且不被循环内语句重定值

代码外提两个大条件

重点 代码外提的两个条件（大题常考点）。

条件一：外提后运算结果在所有路径上保持一致：

• 包含该运算的基本块是循环所有出口的必经节点，或
• 该运算在循环出口后不会被使用（即结果在出口后不活跃）

条件二：外提后不会改变程序语义：

• 该运算的左值（赋值目标）在离开循环后不再活跃
• 该运算在循环内只定值一次

不变运算查找算法

1. 遍历循环内所有四元式，标记初始满足条件 1/2 的运算为”不变”
2. 重复：若某运算的操作数都是常量/循环外定值/已标记为不变的，则标记为”不变”
3. 直到不再有新的不变运算被标记

重点 不变运算判定（常数/循环外定值/循环内不变定值）。

代码外提算法（X2）完整条件

对标记为”不变”的运算 $x=yopz$，能外提的前提（算法 X2 的三个条件）：

• (i) 包含该运算的基本块是循环所有出口的必经节点
• (ii) 该运算的左值 $x$ 在离开循环后不再活跃
• (iii) 该运算在循环内只定值一次

条件(i)的反例：运算在条件分支内（如 if 中），外提后路径上可能错误执行。 条件(ii)的反例：$x$ 在循环出口后被使用，外提后出口路径上 $x$ 未正确赋值。 条件(iii)的反例：循环内多次对 $x$ 定值，外提后后续定值覆盖外提值。

强度削弱（Strength Reduction）

将代价高的运算替换为代价低的运算，典型为乘法 $\to$ 加法。

示例：

• 循环中 T = I * 4 每轮都做乘法
• 削弱后：在循环前置节点中计算 T1 = I0 * 4，循环内每次 T1 = T1 + 4

原理：若归纳变量按等差数列变化，可将乘法替换为每次递增加法。

向量内积强度削弱完整示例

s = 0;
for (i = 1; i <= N; i++)
    s = s + a[i] * b[i];

优化前的中间代码（假设数组元素宽度 $w=4$，$a$ 首地址 $A_a$，$b$ 首地址 $A_b$）：

    s = 0
    i = 1
L1: if i > N goto L4
    T1 = (i - 1) * 4        ; a[i] 偏移（乘法）
    T2 = A_a + T1            ; a[i] 地址
    T3 = *T2                 ; 取 a[i] 值
    T4 = (i - 1) * 4        ; b[i] 偏移（乘法，重复计算）
    T5 = A_b + T4            ; b[i] 地址
    T6 = *T5                 ; 取 b[i] 值
    T7 = T3 * T6             ; a[i] * b[i]
    s = s + T7
    i = i + 1
    goto L1
L4:

强度削弱后：将循环内的乘法 $(i-1)\times 4$ 替换为循环前置节点的初始计算 + 循环内每次加 4：

    s = 0
    i = 1
    T1' = 0                  ; 前置节点：初始偏移（对应 i=1）
L1: if i > N goto L4
    T2 = A_a + T1'           ; a[i] 地址（加法代替乘法）
    T3 = *T2
    T5 = A_b + T1'           ; b[i] 地址（复用同一偏移）
    T6 = *T5
    T7 = T3 * T6
    s = s + T7
    T1' = T1' + 4            ; 偏移递增
    i = i + 1
    goto L1
L4:

优化效果：每次迭代减少 2 次乘法，大 $N$ 时效果显著。

归纳变量删除（Induction Variable Elimination）

基本归纳变量

循环中每次迭代增加/减少固定常量的变量。

归纳变量三元组 $(I,C,D)$

表示变量 $J=C\times I+D$，其中 $I$ 是基本归纳变量。

查找算法

1. 找出基本归纳变量（形如 $I=I\pm C$）
2. 对其他归纳变量，表示为三元组 $(I,C,D)$
3. 记录每个归纳变量的定义和使用

删除算法（W3）

1. 找到归纳变量 $J$ 的使用
2. 删除 $J$ 在循环内的定值
3. 用 $I$ 的表达式替代 $J$ 的使用

强度削弱算法（W2）

对归纳变量 $J=C\times I+D$，其中 $I$ 每轮变化 $\pm 1$：

1. 在循环前置节点中计算初始值 $J_0=C\times I_0+D$
2. 循环内每次迭代 $J_{new}=J_{old}\pm C$
3. 乘法运算被替换为加法运算

重点 归纳变量三元组 $(I,C,D)$ 表示 $J=C\times I+D$。

查找归纳变量算法（W1）

1. 扫描循环内所有四元式，找出形如 $I=I\pm C$ 的基本归纳变量
2. 对每个基本归纳变量 $I$，找出循环内形如 $J=C\times I\pm D$ 的变量，记录为三元组 $(I,C,D)$
3. 递归查找：若 $K=C^{\prime }\times J\pm D^{\prime }$ 且 $J$ 是归纳变量，则 $K$ 也是归纳变量
4. 标记每个归纳变量的所有定值点，确保不被循环内重复定值

循环展开与合并

• 循环展开：复制循环体多次，减少循环控制开销
• 循环合并：将多个相邻循环合并为一个

循环优化的前提是正确识别循环结构（循环优化与必经节点），并通过 数据流分析 获取变量定值-引用信息以判断不变运算和活跃变量。