第6章 代码优化（让程序跑得更快） Code Optimization

一、导读

1.1 本章学习目标

理解代码优化的基本原则：等价性、有效性、可行性与收益评估

掌握局部优化的主要技术：常量折叠、常量传播、公共子表达式消除、死代码消除

深入理解数据流分析（Data Flow Analysis）的理论框架：到达-定义、可用表达式、活性变量分析

掌握全局优化技术：跨基本块的常量传播、全局公共子表达式消除、全局死代码消除

理解循环优化的核心策略：循环不变量外提、强度削弱、归纳变量消除

掌握函数内联的原理、收益评估与实现方法

了解优化 Pass 的组织方式：Pass 排序、迭代执行与收敛性保证

1.2 为什么本章如此重要

代码优化是编译器最具"魔力"的部分——它能让同一份源代码在不改变语义的前提下，运行速度提升数倍甚至数十倍。从科学计算中的矩阵运算到 Web 服务中的请求处理，从嵌入式设备的功耗控制到数据中心的吞吐量优化，编译器的优化能力直接影响着软件的性能表现和资源效率。

优化的重要性还体现在它与硬件发展的协同关系中。现代处理器的流水线、分支预测、缓存层次、SIMD 指令等特性，如果没有编译器的精心优化，程序无法发挥硬件的潜力。反之，硬件设计的许多决策（如超标量执行、乱序执行）也需要编译器配合才能发挥最大效益。

从理论角度看，代码优化涉及程序分析的核心问题：如何精确地推断程序的行为（数据流分析），如何在信息不完全时做出安全的决策（保守近似），如何在优化收益和编译时间之间权衡（优化级别）。这些问题不仅是编译器的核心挑战，也是程序验证、静态分析、安全检测等领域的基础。

1.3 核心问题引导

为什么代码优化必须是"等价变换"？如何严格定义两个程序的等价性？

局部优化和全局优化的区别是什么？为什么全局优化需要数据流分析？

数据流分析中的"保守近似"（Conservative Approximation）是什么意思？为什么宁可少优化也不能优化错误？

循环不变量外提如何识别？外提后如何保证程序语义不变？

函数内联总是能提高性能吗？在什么情况下内联反而会降低性能？

为什么优化 Pass 的执行顺序很重要？某些 Pass 之间是否存在依赖关系？

为什么编译器提供不同的优化级别（-O0、-O1、-O2、-O3）？更高级别一定更好吗？

二、核心概念详解

2.1 局部优化技术（约 700 字）

局部优化（Local Optimization）在单个基本块内进行，不需要考虑跨基本块的控制流关系。虽然作用范围有限，但局部优化实现简单、开销低，且能捕获大量常见的低效模式。

常量折叠（Constant Folding）在编译期计算常量表达式的值。例如，将 3 + 4 替换为 7，将 2 * 3.14 替换为 6.28。常量折叠可以递归应用：如果 a = 2 * 3 被折叠为 a = 6，后续使用 a 的表达式也可以进一步折叠。常量折叠不仅适用于算术运算，还适用于比较运算（3 < 5 折叠为 true）和逻辑运算（true && false 折叠为 false）。

常量传播（Constant Propagation）将已知为常量的变量替换为其值。例如，如果分析发现 x = 5 且到某使用点之间 x 没有被重新赋值，则可以将该使用点的 x 替换为 5。常量传播与常量折叠协同工作：传播后可能产生新的常量表达式，进而触发更多折叠。

公共子表达式消除（Common Subexpression Elimination, CSE）识别程序中计算结果相同的表达式，将重复计算替换为对第一次计算结果的复用。例如，如果 a = b + c 和 d = b + c 之间 b 和 c 没有被修改，则可以将 d 的赋值替换为 d = a。CSE 的关键是判断表达式的"可用性"——即在当前点，该表达式之前已被计算且其操作数未被修改。

死代码消除（Dead Code Elimination, DCE）删除计算结果永远不会被使用的代码。死代码有两种：不可达代码（Unreachable Code），即控制流永远无法到达的代码（如 return 之后的语句）；以及结果无用代码，即计算结果不被任何后续使用的指令（如 t = a + b 但 t 从未被引用）。DCE 不仅减少代码体积，还可能暴露更多优化机会（消除死代码后，某些变量可能变成死的，引发级联消除）。

强度削弱（Strength Reduction）将高代价运算替换为等价的低代价运算。例如，将 x * 2 替换为 x << 1（位移代替乘法），将 x ** 2 替换为 x * x（乘法代替幂运算），将循环中的 i * stride 替换为累加（归纳变量优化）。强度削弱需要了解目标机器的指令代价模型。

2.2 数据流分析框架（约 800 字）

数据流分析（Data Flow Analysis, DFA）是全局优化的理论基础。它通过在控制流图上传播"数据流信息"来推断程序各点的属性，如哪些变量在某点可用、哪些定义能到达某点、哪些变量在某点之后会被使用等。

数据流分析的核心框架由以下要素组成：

域（Domain）：分析所关注的信息集合。例如，到达-定义分析的域是所有"定义-变量"对的集合的幂集；可用表达式分析的域是所有表达式的集合的幂集。

方向（Direction）：分析传播的方向。前向分析（Forward Analysis）从入口向出口传播信息，如到达-定义分析（定义从定义点向后传播）；后向分析（Backward Analysis）从出口向入口传播信息，如活性变量分析（使用信息从使用点向前传播）。

传递函数（Transfer Function）：描述数据流信息通过一个基本块后如何变化。对于块 B，传递函数 f_B 将入口信息 IN[B] 映射为出口信息 OUT[B]：OUT[B] = f_B(IN[B])。传递函数通常具有形式 f_B(X) = Gen_B ∪ (X - Kill_B)，其中 Gen_B 是块 B 生成的信息，Kill_B 是块 B 消除的信息。

汇合运算（Meet Operator）：当多个前驱块的信息汇合到一个块时，使用汇合运算合并信息。对于"必须"分析（Must Analysis，如可用表达式），使用交集；对于"可能"分析（May Analysis，如到达-定义），使用并集。

迭代算法：数据流分析通过迭代求解数据流方程。初始化所有块的信息为空集（或全集），然后反复应用传递函数和汇合运算，直到信息不再变化（达到不动点，Fixed Point）。对于有限域上的单调函数，迭代必然终止。

三种经典的数据流分析：

到达-定义分析（Reaching Definitions）：前向、可能分析。在点 p 到达的定义是那些存在一条从定义点到 p 的路径上定义未被"杀死"的定义。用于常量传播、死代码消除等。

可用表达式分析（Available Expressions）：前向、必须分析。在点 p 可用的表达式是那些在所有到达 p 的路径上都已被计算且操作数未被修改的表达式。用于公共子表达式消除。

活性变量分析（Live Variables）：后向、可能分析。在点 p 活跃的变量是那些在 p 之后某处被使用的变量。用于寄存器分配（不活跃的变量可以释放寄存器）和死代码消除。

2.3 循环优化（约 700 字）

循环是程序性能的瓶颈所在——程序的大部分执行时间通常花费在少量关键循环中。因此，循环优化对程序性能的提升效果最为显著。

循环不变量外提（Loop-Invariant Code Motion）将循环体内计算结果不随循环迭代变化的代码移到循环外部。例如：

for (i = 0; i < n; i++) {
  a[i] = b[i] + x * y;  // x * y 是循环不变量
}

优化后：

t = x * y;
for (i = 0; i < n; i++) {
  a[i] = b[i] + t;
}

识别循环不变量需要分析变量的定义点：如果表达式的所有操作数的所有到达定义都在循环外部，则该表达式是循环不变量。外提时需要确保语义正确：外提的代码不能在循环中有副作用，且外提后的位置必须支配循环的所有出口。

强度削弱针对循环中的归纳变量（Induction Variable）——即每次迭代以固定步长变化的变量（如 i = i + 1 中的 i）。对于循环中形如 c = i * a + b 的表达式（其中 i 是归纳变量，a 和 b 是循环不变量），可以用另一个归纳变量替代：在循环外初始化 t = 0 * a + b = b，在循环内每次迭代 t = t + a，用 t 替代原表达式。这将乘法替换为加法，显著降低了循环体内的计算代价。

归纳变量消除在强度削弱之后进行：如果原始归纳变量（如 i）在循环中除了计算被强度削弱的表达式外没有其他用途，则可以完全消除原始归纳变量，只保留强度削弱后的变量。这进一步减少了循环体内的指令数。

循环展开（Loop Unrolling）通过复制循环体减少循环控制开销和分支预测失败。展开 k 次意味着每次迭代执行 k 个循环体的副本，循环次数减少为原来的 1/k。展开减少了分支指令的比例，增加了指令级并行度，但增加了代码体积。

2.4 函数内联（约 600 字）

函数内联（Function Inlining）将函数调用替换为函数体的副本，消除函数调用的开销（参数传递、栈帧创建、跳转和返回）。更重要的是，内联为其他优化提供了更多上下文：调用者和被调用者的代码合并后，常量传播、死代码消除等优化可以跨越原来的函数边界进行。

例如：

int square(int x) { return x * x; }
int main() { int y = square(5); }

内联后：

int main() { int y = 5 * 5; }  // 进一步折叠为 int y = 25;

内联的决策需要权衡收益和代价。收益包括：消除调用开销、暴露更多优化机会、改善指令缓存局部性。代价包括：增加代码体积（可能导致指令缓存未命中增加）、增加编译时间。

内联决策的启发式规则通常考虑：函数体大小（小函数优先内联）、调用频率（热点调用优先内联）、是否递归（递归函数通常不内联，或限制内联深度）、是否有特殊属性（如 inline 关键字、always_inline 属性）。

现代编译器的内联决策远比简单规则复杂。GCC 和 LLVM 使用代价模型（Cost Model）评估内联的收益：估计内联后能节省的指令数、暴露的优化机会数量，与增加的代码体积进行权衡。只有当净收益为正时才执行内联。

三、深入分析与讨论

3.1 数据流分析的收敛性与精度（约 500 字）

数据流分析的迭代算法必须保证两个性质：终止性（Termination）和正确性（Correctness）。

终止性由域的有限性和传递函数的单调性保证。数据流分析的域通常是某个有限集合的幂集（如所有变量定义的集合的幂集），因此域的升链条件（Ascending Chain Condition）成立。传递函数的单调性保证每次迭代不会"回退"信息。在有限格（Lattice）上的单调函数迭代必然在有限步内达到不动点。

正确性要求分析结果是安全的（Safe）：对于"可能"分析（如到达-定义），分析结果必须包含所有真实情况（宁可多报，不可漏报）；对于"必须"分析（如可用表达式），分析结果必须是真实情况的子集（宁可少报，不可多报）。这种保守近似（Conservative Approximation）确保了基于分析结果的优化不会改变程序语义。

分析的精度（Precision）直接影响优化的效果。更精确的分析能发现更多优化机会，但通常需要更多的计算资源。例如，流敏感分析（Flow-Sensitive）考虑控制流顺序，比流不敏感分析（Flow-Insensitive）更精确但更昂贵。路径敏感分析（Path-Sensitive）进一步考虑可行路径，精度更高但开销更大。编译器需要在精度和效率之间做出工程权衡。

3.2 优化 Pass 的组织与调度（约 500 字）

现代编译器包含数十到数百个优化 Pass，它们的执行顺序对最终代码质量有显著影响。某些 Pass 之间存在协同效应：常量传播可能暴露新的死代码，死代码消除可能暴露新的常量传播机会。某些 Pass 之间存在依赖关系：循环不变量外提需要在循环识别之后进行，寄存器分配需要在指令选择之前进行。

GCC 的优化 Pass 调度使用 Pass Manager，按照预定义的顺序执行各个 Pass，某些 Pass 在特定条件下会重复执行。LLVM 的 Pass Manager 支持 Pass 的依赖声明和动态调度，新 Pass 可以声明它需要哪些分析结果，Pass Manager 自动确保这些分析在 Pass 执行前完成。

优化级别（如 -O0、-O1、-O2、-O3、-Os、-Oz）本质上是 Pass 集合和迭代次数的不同配置。-O0 不执行任何优化，-O1 执行基本的局部优化，-O2 增加全局优化和循环优化，-O3 进一步增加激进的优化（如向量化、激进的内联），-Os/-Oz 侧重代码体积优化。更高级别不一定总是更好：-O3 的激进优化可能增加代码体积，导致指令缓存未命中增加，在某些场景下反而比 -O2 慢。

3.3 基于 Profile 的优化（约 400 字）

传统的编译器优化基于静态分析，无法准确预测程序的运行时行为（如哪些分支更频繁、哪些函数是热点）。基于 Profile 的优化（Profile-Guided Optimization, PGO）通过收集程序的实际运行信息来指导优化决策。

PGO 的流程分三步：首先用 Profile 插桩选项编译程序，运行代表性负载收集 Profile 数据（如基本块执行频率、分支跳转概率、函数调用次数、值分布等）；然后用 Profile 数据指导第二次编译，优化器根据实际执行频率决定优化策略（如将热路径放在前面以改善指令缓存局部性、只对热点函数执行激进内联、根据分支概率优化分支预测提示）。

PGO 通常能带来 10%-30% 的额外性能提升，因为它使优化器从"猜测"变为"知情决策"。Linux 内核和大型 C++ 项目（如 Chromium）的构建广泛使用 PGO。

四、实践案例

4.1 案例一：常量传播与死代码消除的协同（约 400 字）

考虑以下代码：

int debug = 0;
void process() {
  int x = 10;
  int y = x * 2;
  if (debug) {
    printf("y = %d\n", y);
  }
  return y;
}

优化过程：首先，常量传播发现 debug = 0（全局常量），将 if (debug) 替换为 if (0)。然后，条件分支分析发现 if (0) 的 then 分支不可达，触发死代码消除，删除 printf 调用。接着，分析发现 debug 变量除了初始化外不再被使用（因为 printf 被删除），触发进一步的死代码消除，删除 debug 的定义。最终代码简化为：

void process() {
  return 20;  // x * 2 被常量折叠
}

这个案例展示了多种优化技术的协同效应：常量传播触发死代码消除，死代码消除暴露更多常量传播和折叠机会。这种级联优化在实际编译器中非常常见。

4.2 案例二：循环不变量外提与强度削弱（约 400 字）

考虑以下数组缩放代码：

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

优化步骤：首先，识别 scale 和 offset 是循环不变量（在循环外定义且循环内不修改），外提到循环前：

// scale 和 offset 已经是循环不变量，无需外提
for (int i = 0; i < n; i++) {
  a[i] = b[i] * scale + offset;
}

然后，对地址计算进行强度削弱。&a[i] 等价于 a + i * sizeof(element)，其中 i * sizeof(element) 是归纳变量表达式。引入临时变量 pa = a，每次迭代 pa += sizeof(element)，用 pa 替代 &a[i]。类似地处理 &b[i]。

最终优化后的代码使用指针递增替代数组索引，消除了每次迭代的乘法运算：

int *pa = a, *pb = b;
int *pa_end = a + n;
while (pa < pa_end) {
  *pa = *pb * scale + offset;
  pa++;
  pb++;
}

五、常见误区与注意事项

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

优化并不总是带来性能提升。某些优化（如循环展开、激进内联）增加代码体积，可能导致指令缓存未命中增加。某些优化（如寄存器压力增加）可能导致更多内存访问。此外，优化增加编译时间，在开发阶段可能降低开发效率。因此，需要根据场景选择合适的优化级别。

5.2 误区二：优化不会改变程序行为

虽然优化在理论上保持程序语义等价，但某些"优化"可能暴露程序中的未定义行为（Undefined Behavior）。例如，C 语言中的有符号整数溢出是未定义行为，编译器可能假设它不会发生并据此优化。如果程序确实依赖溢出行为，优化可能导致错误的结果。编写可移植、正确的代码是获得正确优化的前提。

5.3 误区三：手动优化比编译器更好

现代编译器的优化能力远超大多数程序员的手工优化。编译器能进行全局分析、跨过程优化、指令调度等人类难以手工完成的工作。过早的手动优化不仅浪费时间，还可能干扰编译器的优化决策，导致最终性能反而下降。正确的做法是：先写清晰的代码，让编译器优化；只在 Profile 确认的性能热点处进行有针对性的手动优化。

5.4 注意事项：优化的可调试性

优化后的代码与源代码的对应关系可能非常复杂（指令重排、内联、消除等），这使得调试变得困难。编译器通过生成调试信息（如 DWARF 格式）来建立优化后代码与源代码的映射，但调试优化后的程序仍然比调试未优化程序更困难。在开发阶段使用 -O0，在发布阶段使用 -O2 或 -O3 是常见的实践。

六、本章小结

本章系统讲解了编译器代码优化的核心技术和理论基础。局部优化（常量折叠、常量传播、公共子表达式消除、死代码消除）在基本块内消除冗余计算。数据流分析为全局优化提供了理论框架，通过到达-定义、可用表达式、活性变量等分析推断程序各点的属性。循环优化（不变量外提、强度削弱、归纳变量消除）针对程序的性能热点进行重点优化。函数内联通过消除调用开销和暴露跨函数优化机会提升性能。优化 Pass 的组织、调度和级别选择是工程实践中的重要决策。基于 Profile 的优化利用运行时信息指导编译决策，进一步提升优化效果。掌握这些优化技术，是构建高性能编译器的核心能力。

七、思考题与练习

对以下代码进行常量传播和常量折叠，写出优化后的结果：int a = 3; int b = a + 2; int c = b * a; if (c > 10) { ... } else { ... }

为以下代码构建控制流图，并进行到达-定义分析和活性变量分析：x = 1; y = 2; if (cond) { x = 3; } else { y = 4; } z = x + y;

对以下循环进行不变量外提和强度削弱：for (i = 0; i < n; i++) { a[i] = b[i] + c * d + e; }（其中 c、d、e 是循环不变量）

实现一个基本块内的公共子表达式消除算法，使用哈希表记录已计算的表达式。

分析函数内联的代价模型：考虑调用开销、代码体积增长和暴露的优化机会，设计一个启发式内联决策算法。

调研 GCC 或 LLVM 的优化 Pass 列表（gcc -O2 -fdump-passes 或 opt -O2 --print-passes），说明各 Pass 的执行顺序和作用。

比较"可能"分析和"必须"分析的区别，说明为什么到达-定义是"可能"分析而可用表达式是"必须"分析。

设计一个基于 Profile 的内联决策策略：如何利用基本块执行频率和函数调用次数来决定是否内联？