第6章 优化（让代码更好）

一、导读

1.1 本章学习目标

理解代码优化的定义、分类（局部/全局、机器无关/机器相关）及正确性保证（语义等价性）

掌握常量传播（Constant Propagation）与常量折叠（Constant Folding）的原理与实现

掌握死代码消除（Dead Code Elimination）的识别方法与安全性保证

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

掌握数据流分析（Data Flow Analysis）的框架：传递函数、meet 运算、迭代求解

理解到达定值（Reaching Definitions）、活跃变量（Live Variables）、可用表达式（Available Expressions）三种经典数据流分析

了解 SSA 形式对优化算法的简化作用及基于 SSA 的优化技术

掌握优化 Pass 的组织与管理：Pass 依赖关系、执行顺序、迭代收敛性

1.2 为什么本章如此重要

代码优化是编译器最具技术深度和工程价值的环节。优化器的目标是在不改变程序可观察语义的前提下，变换程序以提高其执行效率（减少运行时间）或减小代码体积（减少内存占用）。一个优秀的优化器可以将程序性能提升数倍甚至数十倍，使得高级语言编写的程序能够与甚至超越手工优化的汇编代码。在现代计算环境中，优化器的重要性更加突出——移动设备的电池寿命、数据中心的能源消耗、实时系统的响应延迟——这些关键指标都直接受到代码优化质量的影响。

从理论角度来看，代码优化涉及计算机科学中一些最优美的算法思想。数据流分析将程序的语义属性建模为约束方程组，通过迭代求解获得近似最优的分析结果。这种"将程序行为抽象为数学模型，再通过算法求解"的方法论，不仅适用于编译器优化，还广泛应用于程序验证、安全分析、并行化等领域。图论、格论（Lattice Theory）和不动点定理（Fixed-Point Theorem）为数据流分析的正确性和收敛性提供了严格的数学保证。

从工程实践角度来看，优化器是编译器中代码量最大、复杂度最高的模块。GCC 包含超过 200 个优化 Pass，LLVM 包含超过 100 个优化 Pass，每个 Pass 实现一种特定的优化变换。这些 Pass 之间存在复杂的依赖关系和交互效应——一个 Pass 的输出可能是另一个 Pass 的输入，多个 Pass 的组合可能产生意想不到的效果。如何组织和管理这些 Pass，使它们以最优的顺序执行并达到最佳的优化效果，是编译器工程中的核心挑战之一。

1.3 核心问题引导

编译器如何保证优化不会改变程序的语义？"语义等价"的精确定义是什么？

常量传播如何在整个程序范围内工作？它与简单的局部常量折叠有什么区别？

死代码消除如何判断一段代码是"死的"？在存在副作用（如 I/O 操作）的情况下如何安全地消除死代码？

循环优化为什么对程序性能如此重要？循环不变量外提的安全性条件是什么？

数据流分析的"精度"和"效率"之间存在什么权衡？如何提高分析的精度？

为什么优化 Pass 的执行顺序很重要？能否找到一种"最优"的 Pass 执行顺序？

SSA 形式如何简化优化算法？基于 SSA 的优化与传统优化相比有什么优势？

二、核心概念详解

2.1 常量传播与常量折叠

常量传播（Constant Propagation）是一种将已知常量值替换到使用该变量的所有位置的优化技术。当一个变量在某个程序点只有一个可能的值时（即该变量在该点被"定值为常量"），编译器可以将该变量在后续使用处直接替换为其常量值。

常量传播的典型场景如下：源代码 int x = 5; int y = x + 3; 经过常量传播后变为 int x = 5; int y = 5 + 3;，再经过常量折叠（Constant Folding，在编译期计算常量表达式的值）后变为 int x = 5; int y = 8;。如果 x 在后续代码中不再被修改，则所有使用 x 的地方都可以替换为 5。

常量传播的实现基于数据流分析框架。对于每个程序点，分析器维护每个变量的值状态：TOP（未确定，可能是任何值）、某个具体的常量值、或 BOTTOM（不确定，变量的值取决于不同的执行路径）。分析器从程序入口开始，沿着控制流方向传播值信息。在定值点（如 x = 5），将 x 的状态更新为常量 5；在控制流合并点，使用 meet 运算合并来自不同路径的值信息——如果两条路径给出相同的常量值，则合并结果为该常量；如果给出不同的常量值，则合并结果为 BOTTOM（不确定）。

常量传播的优化效果可以非常显著。它不仅减少了运行时的计算开销，更重要的是，它暴露了更多的优化机会——常量值被传播后，可能使得条件分支的判断结果在编译期就可以确定，从而触发死代码消除（删除永远不会执行的分支）和函数内联（当函数调用的参数为常量时，某些优化只在特定参数值下才有效）。

2.2 死代码消除

死代码（Dead Code）是指程序中永远不会被执行或执行结果永远不会被使用的代码。死代码消除（Dead Code Elimination, DCE）通过删除这些无用代码来减小程序体积、减少编译时间，并可能暴露更多的优化机会。

死代码分为两类。不可达代码（Unreachable Code）是由于控制流结构的原因永远不会被执行的代码，如 return 语句之后的代码、条件永远为假的分支、break/continue 之后的代码。无用代码（Unused Code）是执行结果不被任何地方使用的代码，如计算结果不被引用的赋值语句、副作用为零且结果不被使用的函数调用。

不可达代码的检测基于控制流分析——如果一个基本块从程序入口不可达（即不存在从入口块到该块的控制流路径），则该块中的代码是不可达的。这可以通过简单的图遍历算法（如 BFS 或 DFS）来实现。

无用代码的检测基于活跃变量分析（Live Variable Analysis）的逆过程——有用性分析（Usefulness Analysis）。从程序的出口（返回值、输出操作等" sinks"）开始，反向追踪数据的依赖关系：如果一个定值被某个有用的使用所引用，则该定值是有用的；如果一个定值没有被任何有用的使用所引用，且该定值没有副作用，则该定值是死的，可以安全删除。

在存在副作用的情况下，死代码消除需要格外小心。例如，int x = foo(); 中，即使 x 后续不被使用，如果 foo() 有副作用（如修改全局变量、执行 I/O 操作），则该调用不能被删除。编译器需要通过副作用分析（Side Effect Analysis）来判断函数调用是否可以安全删除。

2.3 循环优化

循环是程序性能的关键瓶颈——大多数程序的执行时间集中在少数几个热点循环中。循环优化通过变换循环结构来减少循环体内的计算量，对程序性能的提升效果往往最为显著。

循环不变量外提（Loop Invariant Code Motion, LICM）将循环体内不随迭代变化的计算移到循环外。一个操作是循环不变的，当且仅当它的所有操作数在循环中不变（或是循环不变量计算的结果）。例如，在循环 for (i = 0; i < n; i++) { a[i] = b[i] + c * d; } 中，c * d 是循环不变量，可以外提到循环之前计算。安全性条件包括：不变量操作必须在循环的所有迭代中产生相同的结果（无副作用变化）；外提后的代码必须在循环的每次执行中都被执行（即使循环体执行零次）。

强度削弱（Strength Reduction）用计算代价更低的操作替代代价更高的操作。最经典的例子是将循环中的乘法替换为加法：for (i = 0; i < n; i++) { a[i * 4] = 0; } 可以改写为 int t = 0; for (i = 0; i < n; i++) { a[t] = 0; t += 4; }，将每次迭代的乘法 i * 4 替换为加法 t += 4。类似的，x * 2 可以替换为 x << 1（左移一位），x % 8 可以替换为 x & 7（位与操作）。

归纳变量消除（Induction Variable Elimination）识别并优化循环中的归纳变量——其值在每次迭代中按固定步长递增或递减的变量。基本归纳变量是循环控制变量（如 i++），导出归纳变量是基本归纳变量的线性函数（如 j = 4 * i + 1）。通过识别归纳变量之间的关系，编译器可以消除冗余的归纳变量计算，减少循环体内的指令数量。

2.4 数据流分析框架

数据流分析（Data Flow Analysis, DFA）是一类在控制流图上传播程序属性信息的静态分析技术的总称。它为编译器优化提供了关键的分析基础——优化器需要知道在程序每个点上哪些变量是常量、哪些变量是活跃的、哪些表达式是可用的，才能安全地执行相应的优化变换。

数据流分析的核心框架包括以下要素。分析域（Domain）：每个程序点的分析结果是一个数据流值，如到达定值集合、活跃变量集合等。传递函数（Transfer Function）：每个基本块定义了一个从输入数据流值到输出数据流值的映射函数。Meet 运算：在控制流合并点，使用 meet 运算（如集合的交集或并集）合并来自不同前驱的数据流值。方向：分析可以是前向的（从入口到出口，如到达定值分析）或后向的（从出口到入口，如活跃变量分析）。

数据流分析的求解通常采用迭代算法。对于前向分析，初始化所有块的数据流值为边界条件（入口块为初始值，其他块为 TOP 或 BOTTOM），然后反复对每个块应用传递函数并更新后继块的值，直到所有块的值不再变化（达到不动点）。迭代算法的收敛性由分析域的格（Lattice）结构保证——如果分析域满足升链/降链条件（Chain Condition），则迭代必然在有限步内收敛。

三种经典的数据流分析包括：到达定值分析（Reaching Definitions）——在程序每个点上，哪些定值可能到达（即该定值可能是在该点之前最后一次对该变量的赋值）；活跃变量分析（Live Variables）——在程序每个点上，哪些变量的当前值在后续还可能被使用；可用表达式分析（Available Expressions）——在程序每个点上，哪些表达式的值已经被计算且其操作数在后续未被重新定值。

2.5 基于 SSA 的优化

SSA 形式为编译器优化带来了根本性的简化。在 SSA 形式下，每个变量只有一个定值点，这消除了传统 IR 中"哪个定值到达了哪个使用点"的不确定性，使得许多优化算法可以更简单、更高效地实现。

基于 SSA 的常量传播（Sparse Constant Propagation）不再需要传统的数据流迭代算法。由于每个变量只有一个定值，分析器可以直接从定值点出发，沿着定义-使用链（Def-Use Chain）传播常量信息。如果一个变量的定值是常量，且所有到达该定值的路径都经过该定值点（通过支配关系判定），则该变量是常量，其所有使用点都可以替换为该常量值。这种"稀疏"方法只访问相关的程序点，避免了传统方法中对所有程序点的迭代计算。

基于 SSA 的死代码消除同样简单。如果一个变量的定值不被任何使用引用（即定义-使用链为空），且该定值没有副作用，则可以直接删除。删除一个定值可能导致其他变量的使用变为无用，触发级联删除。这种基于使用计数的方法比传统的活跃变量分析更加精确和高效。

值编号（Value Numbering）是基于 SSA 的另一种重要优化。它通过为每个计算结果分配一个唯一的值编号来识别冗余计算。如果两个计算的操作数具有相同的值编号且运算符相同，则它们的计算结果也相同，可以共享同一个值编号。全局值编号（Global Value Numbering, GVN）能够消除跨基本块的冗余计算，是编译器中最有效的优化之一。

三、深入分析与讨论

3.1 优化 Pass 的组织与管理

现代编译器包含数十到数百个优化 Pass，如何组织这些 Pass 的执行顺序是一个复杂的工程问题。Pass 之间存在多种关系：某些 Pass 会暴露新的优化机会（如常量传播可能暴露死代码消除的机会），某些 Pass 之间存在依赖关系（如 SSA 构造必须在某些优化之前执行），某些 Pass 之间可能存在冲突（如一个 Pass 的优化可能被另一个 Pass 撤销）。

GCC 和 LLVM 都采用了 Pass 管理器的架构来组织优化流程。Pass 管理器负责按照预定义的顺序执行各个 Pass，处理 Pass 之间的依赖关系，管理 IR 的验证和统计信息的收集。LLVM 的新 Pass 管理器（New Pass Manager）引入了 Pass 管道（Pass Pipeline）的概念，允许用户通过命令行参数精确控制 Pass 的执行顺序和配置。

优化级别（Optimization Level）是 Pass 组织的另一种抽象。-O0 不执行任何优化，-O1 执行基本优化（如死代码消除和简单常量传播），-O2 执行标准优化（包括大部分机器无关优化），-O3 执行激进优化（包括向量化、函数内联等代价较高的优化）。每个优化级别对应一个预定义的 Pass 管道，用户无需了解具体的 Pass 细节即可获得合理的优化效果。

3.2 优化的正确性与安全性

优化的正确性是编译器设计中最关键的要求之一。一个不正确的优化可能悄悄改变程序的语义，导致生成的程序产生错误的结果，而这类错误极其难以调试——因为源代码看起来是正确的。

优化的安全性通常基于形式化的正确性条件。每个优化变换都必须保证：变换后的程序与变换前的程序在所有可能的输入下产生相同的可观察行为（Same Observable Behavior）。可观察行为包括：程序的输出结果、与外部环境的交互（I/O 操作）、程序的终止行为（是否终止、是否抛出异常）。

未定义行为（Undefined Behavior, UB）为优化提供了额外的空间。C/C++ 标准允许编译器假设程序中不存在未定义行为，从而进行激进的优化。例如，如果有符号整数溢出在 C 中是未定义行为，编译器可以假设 x + 1 > x 永远为真（因为如果溢出则属于 UB，编译器假设不会发生），从而删除相关的溢出检查代码。这种优化虽然合法，但经常导致令人困惑的 bug，是 C/C++ 社区长期争论的话题。

四、实践案例

4.1 循环不变量外提的实际效果

以矩阵乘法为例，展示循环不变量外提的优化效果。原始代码：

for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    for (k = 0; k < N; k++)
      C[i][j] += A[i][k] * B[k][j];

在最内层循环中，C[i][j] 和 A[i][k] 的基地址计算涉及循环不变量。外提后：

for (i = 0; i < N; i++)
  for (k = 0; k < N; k++) {
    temp = A[i][k];
    for (j = 0; j < N; j++)
      C[i][j] += temp * B[k][j];
  }

这里将 A[i][k] 的加载外提到中间循环，减少了内层循环的内存访问次数。进一步结合循环交换（将 j 循环和 k 循环交换以改善缓存局部性），可以显著提升矩阵乘法的性能。

4.2 数据流分析在常量传播中的应用

以一个包含条件分支的函数为例，展示全局常量传播的工作过程。函数中 x 在两个分支中被赋予不同的值（then 分支 x = 5，else 分支 x = 5），在合并点通过 meet 运算发现两条路径的常量值相同，因此 x 在合并点后仍为常量 5。这使得后续的 y = x + 3 可以被折叠为 y = 8，进一步传播到使用 y 的位置。

如果两个分支赋予不同的值（then 分支 x = 5，else 分支 x = 7），则合并后 x 的状态变为 BOTTOM（不确定），常量传播无法继续。但如果后续代码是 z = x * 0，即使 x 的值不确定，z 的结果也确定为 0——这需要更精细的分析（如值范围分析或符号分析）来捕获这种优化机会。

五、常见误区与注意事项

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

优化并不总是有益的。某些优化可能增加代码体积（如函数内联），导致指令缓存命中率下降；某些优化可能增加编译时间而带来的性能提升微乎其微；某些优化可能使调试更加困难（如变量被优化掉、代码被重排）。工程实践中需要根据具体场景选择合适的优化级别。

5.2 误区二：优化级别越高越好

如前所述，-O3 并不总是优于 -O2。激进优化可能引入未定义行为相关的 bug，增加代码体积，延长编译时间。在某些嵌入式系统中，-Os（优化代码大小）可能比 -O3 更合适。选择优化级别应基于实际的性能测试数据，而非盲目追求最高级别。

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

编译器的优化能力是有限的。算法层面的低效（如 O(n²) 的排序算法）无法通过编译器优化来根本解决；数据结构的不当选择（如使用链表而非数组进行随机访问）也无法通过编译器优化来弥补。程序员应当首先关注算法和数据结构的优化，将编译器优化作为锦上添花的手段。

5.4 注意事项：优化与调试的冲突

高优化级别下，编译器可能将变量优化到寄存器中（不出现在内存中）、将代码重排（执行顺序与源代码不同）、将函数内联（调用栈发生变化）。这些优化使得调试器的行为与源代码不一致——断点可能无法命中、变量可能显示为"<optimized out>"、单步执行可能跳过某些代码行。在调试阶段，应使用 -O0 -g 编译选项关闭优化并保留调试信息。

5.5 注意事项：未定义行为与优化陷阱

C/C++ 的未定义行为为编译器提供了激进的优化空间，但也可能导致令人困惑的 bug。例如，编译器可能基于"有符号整数不会溢出"的假设删除溢出检查代码，导致实际溢出的程序产生错误结果。程序员应当严格遵守语言标准，避免未定义行为，而不是依赖编译器的"宽容"。

六、本章小结

本章系统讲解了编译器中的核心优化技术。常量传播和常量折叠通过在编译期确定变量值来减少运行时计算。死代码消除通过识别和删除无用代码来减小程序体积。循环优化（不变量外提、强度削弱、归纳变量消除）针对程序的性能热点进行重点优化。数据流分析提供了优化所需的程序属性信息，包括到达定值、活跃变量和可用表达式等经典分析。SSA 形式极大地简化了优化算法的实现，使得常量传播、死代码消除和值编号等优化能够更高效地执行。优化 Pass 的组织与管理是编译器工程的核心挑战，需要在优化效果、编译时间和代码质量之间寻求平衡。正确性是所有优化的前提，每个变换都必须保证语义等价性。

七、思考题与练习

对以下代码执行全局常量传播，展示每个程序点的变量状态变化：包含嵌套 if-else 和多个变量赋值的代码段。

实现一个基于活跃变量分析的死代码消除 Pass，处理包含函数调用（可能有副作用）的情况。

对以下循环执行循环不变量外提和强度削弱：for (i = 0; i < n; i++) { a[i] = b[i] * scale + offset; }，其中 scale 和 offset 在循环中不变。

手动执行到达定值分析的迭代算法，验证其在给定控制流图上的收敛过程。

比较基于 SSA 的常量传播与传统的迭代式常量传播在精度和效率上的差异。

调研 LLVM 的 Pass 管理器架构，分析新 Pass 管理器相比旧 Pass 管理器的改进。

分析以下代码中编译器可能进行的优化：包含递归函数调用、循环和条件分支的完整函数，讨论优化的安全性和效果。

讨论"未定义行为"对编译器优化的影响，分析 int x = INT_MAX; x = x + 1; 在不同优化级别下可能的行为。