第9章代码优化

导读

代码优化是编译器中最复杂、最有挑战性，也是最能体现编译器设计者功力的环节。优化的目标是在保持程序语义不变的前提下，生成运行更快、占用空间更小或能耗更低的代码。

代码优化是一个NP完全问题——理论上不可能找到最优解。因此，实际编译器采用各种启发式方法，在合理的时间内获得"足够好"的优化结果。不同的优化技术在不同的场景下效果不同，编译器设计者需要根据目标平台和程序特点选择合适的优化组合。

本章将系统地介绍代码优化的理论和实践。我们将从优化的基本分类开始，学习局部优化、全局优化和循环优化的各种技术；然后深入探讨数据流分析这一重要的优化基础理论；最后介绍一些高级优化技术，如过程间优化、多面体模型等。

通过本章的学习，你将理解编译器是如何在不改变程序行为的前提下提升性能的，你将掌握各种优化技术的原理和适用场景，你也将了解为什么某些优化可能失败以及它们的局限性。

核心概念详解

9.1 优化的分类

代码优化可以从多个维度进行分类：

按作用范围分类：

局部优化（Local Optimization）：在单个基本块内进行

全局优化（Global Optimization）：跨越基本块边界，在整个函数内进行

过程间优化（Interprocedural Optimization）：跨越过程/函数边界

按优化目标分类：

速度优化：减少执行时间

空间优化：减少代码大小或内存占用

能耗优化：减少能量消耗（移动设备重要）

按优化阶段分类：

机器无关优化：不依赖目标机器特性

机器相关优化：利用目标机器的特定特性

9.2 基本块与控制流图

基本块（Basic Block）是最小的优化单位，它是一个连续的指令序列，具有以下性质：

控制流只能从第一条指令进入
控制流只能从最后一条指令离开

基本块的划分算法：

确定领导指令（leader）：

- 程序的第一条指令

- 条件或无条件跳转的目标

- 紧跟在条件或无条件跳转之后的指令

每个基本块从一个领导指令开始，到下一个领导指令之前（或程序结束）

控制流图（Control Flow Graph, CFG）是有向图，节点是基本块，边表示控制流的可能转移。

示例:
    B1: if x < y goto B3
    B2: z = z + 1
        goto B4
    B3: z = z - 1
    B4: ...

控制流图:
    B1 → B2 → B4
     ↓
    B3 → B4

9.3 局部优化

局部优化在单个基本块内进行，不需要考虑控制流信息。

1. 常量折叠（Constant Folding）

在编译时计算常量表达式的值。

优化前: x = 3 + 5
优化后: x = 8

2. 常量传播（Constant Propagation）

将已知为常量的变量替换为该常量。

优化前:
    x = 5
    y = x + 3
优化后:
    x = 5
    y = 8

3. 公共子表达式消除（Common Subexpression Elimination, CSE）

如果表达式 a + b 之前已经计算过且 a、b 未被修改，则复用之前的结果。

优化前:
    t1 = a + b
    t2 = a + b  // 公共子表达式
    x = t1 * t2
优化后:
    t1 = a + b
    x = t1 * t1

4. 死代码消除（Dead Code Elimination）

删除计算结果从未被使用的代码。

优化前:
    x = 5
    y = 10
    z = x + y  // z从未被使用
    return x
优化后:
    x = 5
    return x

5. 代数化简（Algebraic Simplification）

利用代数恒等式简化表达式。

x = x + 0      →  x = x（删除）
x = x * 1      →  x = x（删除）
x = x * 0      →  x = 0
x = x ** 2     →  x = x * x（乘法代替幂运算）
x = x / 2      →  x = x >> 1（移位代替除法）

9.4 全局优化

全局优化跨越基本块边界，需要考虑整个函数的控制流。

1. 全局公共子表达式消除

在整个函数范围内消除公共子表达式。

B1: t1 = a + b
    if cond goto B3
B2: t2 = a + b  // 全局公共子表达式
    ...
B3: ...

2. 循环不变量外提（Loop-Invariant Code Motion）

将循环中不变的计算移到循环外。

优化前:
for (i = 0; i < n; i++) {
    a[i] = b[i] + c * d;  // c*d是循环不变量
}

优化后:
t = c * d;  // 外提到循环外
for (i = 0; i < n; i++) {
    a[i] = b[i] + t;
}

3. 归纳变量优化（Induction Variable Optimization）

识别和优化循环中的归纳变量。

优化前:
i = 0
for (...) {
    x = i * 4  // 强度削减
    i = i + 1
}

优化后:
t = 0
for (...) {
    x = t      // 用加法代替乘法
    t = t + 4
}

4. 复制传播（Copy Propagation）

将 x = y 之后的 x 替换为 y。

优化前:
    x = y
    z = x + 1
优化后:
    x = y
    z = y + 1

9.5 数据流分析

数据流分析（Data Flow Analysis）是全局优化的理论基础。它通过收集程序执行路径上的数据信息来支持各种优化。

数据流分析框架：

控制流图（CFG）：程序的抽象表示

数据流值域：每个基本块关联的数据流信息

传递函数：描述基本块如何转换数据流信息

汇聚函数：合并来自多个前驱的信息（交或并）

方程组：描述数据流值的约束

到达定值分析（Reaching Definitions）：

一个定值 d: x = ... 到达点p，如果存在一条从d到p的路径，且路径上没有对x的其他定值。

IN[B] = ∪ OUT[P]  (P是B的前驱)
OUT[B] = gen[B] ∪ (IN[B] - kill[B])

其中：

gen[B]：B中产生的定值
kill[B]：B中杀死（覆盖）的定值

可用表达式分析（Available Expressions）：

表达式 a + b 在点p可用，如果从入口到p的每条路径上，a + b 都被定值且之后没有被杀死。

OUT[B] = e_gen[B] ∪ (IN[B] - e_kill[B])
IN[B] = ∩ OUT[P]  (P是B的前驱)

活跃变量分析（Live Variables）：

变量x在点p活跃，如果存在一条从p到x的某个使用点的路径。

IN[B] = use[B] ∪ (OUT[B] - def[B])
OUT[B] = ∪ IN[S]  (S是B的后继)

9.6 静态单赋值形式（SSA）与优化

SSA形式是现代编译器进行优化的首选中间表示。在SSA中，每个变量只被赋值一次。

SSA的优势：

显式的数据依赖：变量的定义-使用关系通过φ函数显式表示

简化数据流分析：不需要复杂的到达定值分析

便于优化：许多优化在SSA上更容易实现

SSA上的优化：

SSA上的常量传播：沿φ函数传播常量

SSA上的CSE：利用SSA的唯一性简化CSE

死代码消除：在SSA上更容易识别死代码

从SSA转换回普通形式：

需要消除φ函数，通常通过插入复制语句实现。

9.7 寄存器分配

寄存器分配（Register Allocation）是将程序中的变量映射到有限数量的物理寄存器的过程。

图着色算法：

构建冲突图（Interference Graph）：

- 节点：变量

- 边：两个变量不能同时分配到同一寄存器（活跃范围重叠）

图着色：

- 用K种颜色（K=可用寄存器数）给图着色

- 相邻节点颜色不同

- 如果无法着色，需要溢出（Spill）

溢出处理：

- 选择溢出代价最小的变量

- 在定义时存储到内存，在使用时从内存加载

- 重新构建冲突图，重复着色

示例：

原始代码:
    a = 1
    b = 2
    c = a + b
    d = c * 2
    e = d + a

冲突图:
    a - c, a - e
    b - c
    c - d
    d - e

如果3个寄存器:
    R1: a, d (不冲突)
    R2: b, e (不冲突)
    R3: c

9.8 循环优化

循环是程序中最耗时的部分，循环优化对性能影响最大。

1. 循环展开（Loop Unrolling）

减少循环迭代次数，将多次迭代的代码合并。

优化前:
for (i = 0; i < 100; i++) {
    a[i] = b[i] + c[i];
}

优化后:
for (i = 0; i < 100; i += 4) {
    a[i] = b[i] + c[i];
    a[i+1] = b[i+1] + c[i+1];
    a[i+2] = b[i+2] + c[i+2];
    a[i+3] = b[i+3] + c[i+3];
}

2. 循环融合（Loop Fusion）

将多个具有相同迭代空间的循环合并为一个。

优化前:
for (i = 0; i < N; i++) a[i] = b[i] + 1;
for (i = 0; i < N; i++) c[i] = a[i] * 2;

优化后:
for (i = 0; i < N; i++) {
    a[i] = b[i] + 1;
    c[i] = a[i] * 2;
}

3. 循环分块（Loop Tiling/Blocking）

将循环按块划分，提高缓存利用率。

优化前:
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        c[i][j] = a[i][j] + b[i][j];

优化后（分块大小B）:
for (ii = 0; ii < N; ii += B)
    for (jj = 0; jj < N; jj += B)
        for (i = ii; i < min(ii+B, N); i++)
            for (j = jj; j < min(jj+B, N); j++)
                c[i][j] = a[i][j] + b[i][j];

4. 循环交换（Loop Interchange）

交换嵌套循环的顺序以改善内存访问模式。

优化前（行优先存储，列访问不友好）:
for (j = 0; j < N; j++)
    for (i = 0; i < N; i++)
        a[i][j] = 0;

优化后:
for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        a[i][j] = 0;

9.9 函数内联

函数内联（Function Inlining）将函数调用替换为函数体，消除调用开销。

优化前:
int square(int x) { return x * x; }
int y = square(a);

优化后:
int y = a * a;

内联的优点：

消除函数调用开销
暴露更多的优化机会（如常量传播、CSE）
改善指令缓存局部性

内联的缺点：

增加代码大小
可能降低指令缓存命中率
递归函数不能直接内联

内联决策：

小函数（代码量少）倾向于内联
频繁调用的函数倾向于内联
代码大小膨胀有限制（通常不超过阈值）

重要知识点

9.10 优化的正确性

优化的正确性至关重要——错误的优化会导致程序行为改变。

保证优化正确性的原则：

保持语义等价：优化后的程序必须与原始程序在所有可能的输入上行为一致

考虑未定义行为：C/C++的未定义行为可能限制优化

别名分析：指针别名可能阻止某些优化

副作用：函数调用可能有副作用，不能随意删除

优化验证：

形式化验证：使用定理证明器验证优化正确性
测试验证：使用大量测试用例验证
差分测试：比较优化前后的输出

9.11 优化的代价模型

优化不是免费的，需要权衡收益和代价。

编译时间代价：

复杂优化需要更多编译时间
用户可能不愿意等待过长的编译时间
增量编译可以缓解问题

代码大小代价：

某些优化（如内联、循环展开）增加代码大小
代码大小增加可能降低缓存命中率
需要在速度和空间之间权衡

维护代价：

复杂的优化难以调试和维护
需要良好的测试覆盖
需要清晰的文档

9.12 Profile-Guided Optimization (PGO)

PGO利用程序运行时的实际行为信息来指导优化。

PGO的流程：

训练编译：编译时插入性能计数器

训练运行：用典型输入运行程序，收集性能数据

优化编译：根据收集的数据进行优化

PGO可以优化的方面：

分支预测：根据实际分支方向优化代码布局
函数内联：根据实际调用频率决定内联
基本块排序：将频繁执行的路径放在一起
值预测：根据实际值分布优化

常见误区

误区一：优化总是能让程序更快

优化可能适得其反：

过度内联导致代码膨胀，降低缓存命中率
激进的循环展开增加代码大小
不恰当的寄存器分配导致溢出
某些优化在特定输入下反而更慢

误区二：所有优化都是安全的

某些优化在特定条件下不安全：

整数溢出：x * 2 不等于 x << 1（当溢出时）
浮点精度：浮点运算不满足结合律
别名问题：指针别名可能阻止某些优化
信号处理：优化可能改变信号处理的时序

误区三：优化级别越高越好

-O3 不一定比 -O2 更好：

更高的优化级别增加编译时间
可能增加代码大小
某些优化可能引入bug
实际性能提升可能很小

误区四：编译器能优化所有性能问题

编译器无法优化所有问题：

算法复杂度问题需要算法层面的改进
数据结构选择不当需要重新设计
I/O瓶颈需要异步处理
并发问题需要正确的同步机制

实践应用

9.13 实际编译器中的优化

GCC优化选项：

-O0：无优化（默认）
-O1：基本优化
-O2：中等优化（推荐）
-O3：激进优化
-Os：优化代码大小
-Ofast：允许不严格符合标准的优化

LLVM优化管道：

前端生成IR
中间层进行机器无关优化
后端进行机器相关优化
每个阶段都有特定的优化pass

Rust编译器的优化：

零成本抽象
激进的优化（-C opt-level=3）
LTO（链接时优化）
PGO支持

9.14 性能调优的方法论

性能调优的系统方法：

测量：使用性能分析工具识别瓶颈

分析：理解瓶颈的根本原因

优化：针对性地进行优化

验证：确认优化有效且正确

迭代：重复上述过程

本章小结

本章系统介绍了代码优化的理论和实践。核心内容包括：

优化分类：局部优化、全局优化、过程间优化。

局部优化：常量折叠、常量传播、CSE、死代码消除、代数化简。

全局优化：全局CSE、循环不变量外提、归纳变量优化、复制传播。

数据流分析：到达定值、可用表达式、活跃变量分析。

SSA形式：现代编译器优化的首选中间表示。

寄存器分配：图着色算法和溢出处理。

循环优化：循环展开、融合、分块、交换。

函数内联：消除调用开销，暴露优化机会。

代码优化是编译器设计的核心挑战，需要在正确性、编译时间、代码大小和运行速度之间取得平衡。

第9章 代码优化

导读