循环优化与数据流分析

循环——优化的黄金地带

for (int i = 0; i < n; i++) {
    a[i] = b[i] * 2 + c[i];
}

如果 n = 1000000，循环体执行一百万次——哪怕每行代码只优化一条指令，累积效果也极其显著。这就是为什么编译器把大量精力花在循环优化上。

🏫 类比：工厂流水线 循环优化就像优化流水线的每个工位——如果一个动作节省 1 秒，乘以每天 10000 件产品，一天就省了近 3 小时。

循环不变代码外提

如果循环内某个表达式在每次迭代中结果相同，把它移到循环外面：

// 优化前
for (int i = 0; i < n; i++) {
    a[i] = b[i] * (PI / 180);  // PI / 180 每次循环都一样
}

// 优化后
double scale = PI / 180;          // 移到外面，只算一次
for (int i = 0; i < n; i++) {
    a[i] = b[i] * scale;
}

强度削弱

把开销大的运算替换为开销小的：

// 优化前
for (int i = 0; i < n; i++) {
    a[i] = i * 4;  // 乘法
}

// 优化后——用加法代替乘法
int t = 0;
for (int i = 0; i < n; i++) {
    a[i] = t;      // 没有乘法
    t += 4;        // 加法比乘法快得多
}

循环展开

减少循环控制开销——把多次迭代合并成一次：

// 优化前——每次迭代开销：比较、跳转
for (int i = 0; i < 100; i++) {
    a[i] = 0;
}

// 优化后——每次迭代做 4 次，减少 75% 循环控制开销
for (int i = 0; i < 100; i += 4) {
    a[i] = 0;
    a[i+1] = 0;
    a[i+2] = 0;
    a[i+3] = 0;
}

💡 GCC 的 -O3 会自动做循环展开。

数据流分析

数据流分析（Data Flow Analysis） 是优化编译器的”眼睛”——它分析程序中数据的流向，为优化提供依据。

; 数据流分析要回答的问题：
; 1. 这个变量在这行还"活着"吗？（活跃分析）
; 2. 这个表达式的值能确定吗？（可用表达式分析）
; 3. 这个变量肯定被赋值了吗？（到达定值分析）

活跃变量分析

// 活跃分析：变量从定义到最后一次使用之间是"活跃"的
int x = 1;    // x 开始活跃
int y = x + 1; // x 最后一次使用 → x 不再活跃
int z = y + 1; // y 最后一次使用 → y 不再活跃

到达定值分析

// 到达定值：这条赋值语句的结果能到达哪些程序点？
int x = 1;    // 定值 1 到达以下所有使用点
x = x + 1;    // 定值 2 覆盖了定值 1——后面使用的是定值 2 的值
y = x * 2;    // 使用的 x 来自定值 2

数据流方程

数据流分析用数学方程描述信息的流动：

IN[B] = GEN[B] ∪ (OUT[B] - KILL[B])
OUT[B] = ∪ IN[s]  （s 是 B 的后继基本块）

• IN[B]：进入基本块 B 时的数据流信息
• OUT[B]：离开基本块 B 时的数据流信息
• GEN[B]：基本块 B 自己生成的信息
• KILL[B]：基本块 B 杀死的信息

💡 这些方程通过不动点迭代求解——反复计算直到结果不再变化。

小结

优化	原理	收益
循环不变代码外提	把不变计算移出循环	减少 n-1 倍计算
强度削弱	用廉价运算替代昂贵运算	加减法代替乘除法
循环展开	减少循环控制次数	减少分支开销
数据流分析	分析数据在程序中的流向	为所有优化提供信息

为什么先学这个？ 编译原理最后一节——指令调度。循环优化让程序执行更少指令，指令调度让每条指令执行得更快。