编译器优化（一）

本讲义主要探讨编译器的优化技术与数据流分析方法。

1 学习目标与课程引言

本课程的核心学习目标包括：

• 了解在编译器的不同阶段（抽象语法树 AST、静态单赋值中间表示 SSA IR、后端 Backend）通常执行的各类优化示例。
• 分析哪些优化能够带来最大的性能收益。
• 针对特定的动态语言（如 Snake），探讨一种程序分析与优化方法：可能值分析与断言消除（Assertion Removal）。

2 优化的层级与时机

优化可以在编译过程的不同层级和阶段应用，不同阶段适用不同类型的优化策略：

• 高层级（High Level）：主要在抽象语法树（AST）层面进行。
  • 典型优化：函数内联（Inlining）、函数特化（Function specialization）、常量折叠（Constant folding）、常量传播（Constant propagation）、值编号（Value numbering）。
• 中层级（Mid Level）：主要在中间表示（IR）或规范化中间表示（Canonical IR）层面进行。
  • 典型优化：死代码消除（Dead code elimination）、循环不变量代码外提（Loop-invariant code motion）、公共子表达式消除（Common sub-expression elimination）、强度削弱（Strength Reduction）。此外，还会执行常量折叠与传播、分支预测与优化。
• 低层级（Low Level）：主要在抽象汇编（Abstract assembly）或具体汇编（Assembly）层面进行。
  • 典型优化：寄存器分配（Register allocation）、循环展开（Loop unrolling）、缓存优化（Cache optimization）。

3 优化的安全性

执行任何优化的首要前提是安全，即优化不能改变程序的语义。

• 一个优化是否安全，很大程度上取决于编程语言本身的语义。为程序员提供较弱保证的语言允许进行更多的优化，但其程序行为也存在更多歧义。
• 例如，在 C 语言中，读取未初始化的内存属于未定义行为（Undefined Behavior），因此如果程序读取了未初始化的数据，编译器可以进行任意处理。
• 相反，在 Java 中，尾调用优化（将递归函数调用转换为循环）通常是无效的，这主要是因为 Java 具有“栈检查（Stack inspection）”的安全机制。
• 安全性考量示例：考虑循环不变量代码外提的场景。如果将不变代码 z = y / x; 提取到 while(b) 循环的外部，这种做法是否安全？如果不经判断地提取，且 x 的值为 0，而原循环条件 b 一开始就是 false，那么这种优化会导致原本不会执行的除零错误提前爆发。因此必须进行严格的安全分析。

4 基础优化技术 (Basic Optimizations)

4.1 常量折叠 (Constant Folding)

• 核心理念：如果操作数在编译时是已知的常量，则直接在静态编译阶段执行该操作。例如，将 int x = (2 + 3) * y 转换为 int x = 5 * y；将 b & false 直接折叠为 false。
• 此操作会在优化的每一个阶段重复执行，因为常量表达式可能由早期的代码转换或其他优化生成。例如，数组访问 A[2] 可能会被展开为 MEM[MEM[A] + 2 * 4]，通过常量折叠可以简化为 MEM[MEM[A] + 8]。
• 条件语句的常量折叠：
  • if (true) S 可以简化为 S。
  • if (false) S 可以简化为无操作（;）。
  • if (true) S else S' 简化为 S；if (false) S else S' 简化为 S'。
  • while (false) S 可以简化为无操作。

4.2 代数化简 (Algebraic Simplification)

作为常量折叠的更一般形式，利用数学上合理的化简规则来精简代码：

• 数学恒等式：例如 a * 1 -> a，a + 0 -> a，a * 0 -> 0，a - 0 -> a，以及布尔运算 b | false -> b，b & true -> b。
• 重新结合与交换律：如 (a + 1) + 2 -> a + (1 + 2) -> a + 3。
• 强度削弱（Strength Reduction）：用计算成本低的指令替换昂贵的指令。
  • a * 4 -> a << 2（乘法替换为位移）。
  • a * 7 -> (a << 3) - a（乘法替换为位移加减法）。
  • 除法替换：a / 32767 以及涉及位移的叠加组合等。
• 注意事项：
  1. 必须小心处理浮点数（因可能引发舍入误差）和整数运算（需考虑溢出/下溢）。
  2. 多次迭代这些优化会非常有效，但必须确保重写规则能够终止，避免由于交换律造成类似 x + y -> y + x -> x + y 的无限循环。

4.3 常量传播与复制传播 (Constant & Copy Propagation)

• 常量传播：如果已知某个变量为常量，则将程序后续使用该变量的地方直接替换为该常量。该值必须从赋值点向前传播（例如 int x = 5; int y = x * 2; 传播为 int y = 5 * 2;）。为了达到最佳效果，应与常量折叠交替使用。
• 复制传播：如果将一个变量赋值给另一个变量（如 x = y），则将后续对被赋值变量的使用替换为原变量的副本。这与语言的作用域规则密切相关。复制传播通常能使得最初的赋值语句变为死代码。

4.4 死代码消除与不可达代码 (Dead/Unreachable Code)

• 死代码消除 (Dead Code Elimination)：如果一个没有外部可见副作用的语句的结果永远无法被观察到，那么可以安全地消除该语句。如果一个变量在定义后从未被使用，则认定为死变量。寻找这种定义和使用的关系是程序分析的关键部分。死代码也经常由于其他优化的执行而产生。
• 纯粹的计算（不产生抛出异常、修改全局变量、死循环、控制台打印或网络发包等副作用）才可以被丢弃。在这方面，纯函数式语言（如 Haskell）使得验证优化的安全性变得更容易。
• 不可达代码：如果在控制流图中，某基本块无法通过任何合法路径从起点到达，则该块不可达，可以在 IR 或汇编级别被删除，这能直接改善缓存和 TLB 性能。

4.5 内联 (Inlining)

• 核心理念：将对函数的调用直接替换为该函数的内部实现体，并将传入参数重写为局部变量（可能需要对变量重命名以避免作用域捕获冲突）。
• 优势：消除了函数调用的开销（如栈操作、跳转），并暴露了更多上下文，有助于触发进一步的优化。
• 劣势：可能会增加整体代码体积。内联最适合在 AST 或相对高层级的 IR 阶段进行。

4.6 代码特化 (Code Specialization)

当一个函数被来自不同位置的不同参数调用时，创建该函数的特化版本。

• 典型场景包括面向对象语言的接口分发。如果静态已知运行时的确切类型（例如，明确知道调用的是实现类 A 还是实现类 B 的方法），编译器可以生成专门分发到特定类方法的特化代码，或者直接内联该方法。

4.7 公共子表达式消除 (Common Subexpression Elimination, CSE)

• 核心理念：将冗余计算合并处理。从某种意义上说，这是内联的逆操作。
• 示例：编译 a[i] = a[i] + 1 会产生两次计算 a + i * 4 的操作。公共子表达式消除会引入临时变量 t = a + i * 4; 然后执行 [t] = [t] + 1，从而去除了多余的加法和乘法。
• 安全性缺陷：必须确保共享表达式在这两个位置始终具有相同的值。如果在两次计算的间隙，依赖的内存值或数组元素被修改，则提取公共子表达式是不安全的。

5 循环优化 (Loop Optimizations)

大多数程序的执行时间通常集中在循环（尤其是内层循环）中，这也契合著名的 90/10 法则（90% 的执行时间花费在 10% 的代码上）。因此，针对循环体代码的优化投入能带来极高的回报率。

5.1 循环不变量代码外提 (Loop Invariant Code Motion)

这是另一种形式的冗余消除。如果一条纯粹语句或表达式的结果在整个循环执行期间不发生改变，编译器会将其提升到循环体的外部。这对于源层级不可见的数组元素寻址代码（如对 a.length 的重复求值）尤为有效。

5.2 循环的强度削弱

在循环中，可以引入依赖的归纳变量。例如，原本循环步长为 1，但在计算数组索引时每次都乘以 3（i * 3）。优化时可以引入新的归纳变量 j = 0，并在每次循环末尾通过 j = j + 3 递增，从而将乘法计算彻底替换为便宜的加法。

5.3 循环展开 (Loop Unrolling)

条件分支的开销非常高，通过展开循环可以减少分支判断的次数。例如，将单次迭代处理的循环展开为每次处理 4 个元素，并添加一个处理剩余迭代的尾部循环。

• 展开 k 次能够消除 (k-1)/k 的条件分支。
• 这是一个空间与时间的权衡（Space-time tradeoff）。如果循环体本身极其庞大，或者循环总次数较小，循环展开并不是一个好主意。此外，该优化也可能与硬件的指令缓存和分支预测器产生复杂的相互作用。

6 优化的有效性分析

在评判不同优化阶段对最终运行速度带来的改善时，可以通过基准测试获得直观结果（数据图表参考自 2013 年 PLDI 论文，基于 LLVM 测试用例）。

• 加速比公式：%speedup = (base time / optimized time) - 1 x 100% （例如：基准时间 2 秒，优化后时间 1 秒，意味着加速比为 100%）。
• 有效性占比：
  • mem2reg（将分配的栈槽位提升为临时变量以支持寄存器分配）：这项优化叠加寄存器分配等后端优化后，能提供约 78% 的平均加速比。
  • -O1 级别优化：产生约 100% 的加速。这意味着除去 mem2reg，所有其他基础优化加起来只占了约 22% 的额外提升。
  • -O3 级别优化：产生约 120% 的加速。
• 例如，一个未优化需要执行 10 秒的程序：仅用 mem2reg 优化后预期时间降至 5.6 秒；-O1 下为 5 秒；-O3 下约为 4.5 秒。

7 代码分析与断言消除 (Code Analysis & Assertion Removal)

7.1 动态类型带来的运行时断言

动态类型语言经常在编译时插入大量的运行时断言。例如赋值和四则运算中会频繁出现针对类型的检查（如 assertInt(x)，以确保运算变量是整数类型）。我们的优化目标是：当确信某个断言一定会成功执行时，将其从 SSA 中移除。

7.2 可能值分析 (Possible Values Analysis)

• 确立某个变量运行时取值的安全范围，是进行断言移除的前提。
• 莱斯定理（Rice's theorem） 指出，要精确计算出程序运行时的实际状态集合是不可能的。因此必须进行数学上的近似。
• 近似方向：
  • 下溢近似（Underapproximate）：生成真实结果的一个子集，但有遗漏的风险。
  • 过度近似（Overapproximate）：生成包含真实结果的超集，虽然会混入一些实际不会出现的状态，但不会遗漏任何真实状态。
• 为了断言消除的安全性，必须选择过度近似。如果生成的超集仍然只能是某种合法类型（如仅仅是标记过的整数 Tagged Integer），就可以确信该变量在运行时必然是合法整数。这可能会错失一些可消除的断言，但保证了语义的安全。

7.3 抽象解释 (Abstract Interpretation) 与域构建

• 在 SSA 层面，每个值都是一个 64 位整数。如果使用常规集合来表示可能值，将需要不可理喻的存储空间（$2^{2^{64}}$ bits）。
• 抽象解释通过建立一个精简的 抽象域（Abstract domain） 来压缩空间需求，虽然这不可避免地会损失部分精度：
  • Any（或称 Top）：代表所有可能的 64 位整数集合。
  • Even（或称 TaggedInt）：代表所有偶数 64 位整数（常用于表示带有标签的整数，最低位为 0）。
  • None（或称 Bottom/Empty）：代表空集。

7.4 流函数 (Flow Functions)

在每个程序点上，为每个变量维护一个可能值的近似集合。对于每一种指令，定义相应的“流函数”以声明变量状态的改变。

• 加法的流函数规则：
  • Flow[+](Any, Any) = Any
  • Flow[+](Any, Even) = Any
  • Flow[+](Even, Even) = Even
  • Flow[+](None, ...) = None
• 乘法的流函数规则：
  • Flow[*](Any, Any) = Any
  • Flow[*](Any, Even) = Even （任何数乘以偶数必为偶数）
  • Flow[*](Even, Even) = Even
• 位移的流函数规则（左移 n 位, n >= 1）：
  • Flow[<< n](Any) = Even
  • Flow[<< n](Even) = Even
  • （注：这里的 Even 会丧失一定精度，因为实际上结果应是 4 的倍数或更高阶偶数，但被统一折叠到 Even 的概念中）。
• 断言的流函数规则（assertInt）：
  • Flow[assertInt](Any) = Even
  • Flow[assertInt](Even) = Even

7.5 控制流图与标签检查分析

当分析跨越块和函数边界的属性时：

• 收集跳转至目标节点的所有前驱节点（即控制流图的入边）的信息，并进行“并集”操作。
• 面对循环带来的循环依赖（即函数/块可能成为自身的前驱），采用迭代算法：将信息初始化为最底端的最小值（Bottom / None），然后顺着流函数的规则不断迭代更新，直到结果收敛稳定。这一思路与编译器中的活跃度分析等传统数据流分析如出一辙。