理解编译器是如何优化的

在本小节中，我们将了解编译器在多次遍历高级 C++ 代码时所采用的各种优化技术。编译器通常会先进行局部优化，然后再尝试在全局范围内优化这些较小的代码段。这一过程会在预处理、编译、链接和优化等阶段，对翻译后的机器代码进行多次处理。

总体来说，大多数编译器优化技术遵循一些共同的原则，这些原则之间有时会重叠，有时也可能互相冲突，下面我们就来具体看看。

优化常见路径（common case）

这一概念也适用于软件开发，并有助于编译器更好地优化代码。如果编译器能理解程序在哪些路径上花费最多时间，就可以优先优化这些常用路径，即使会牺牲那些很少执行的路径的性能。这样总体性能仍能得到提升。

然而，编译器通常难以在编译时判断哪些路径更可能被执行，除非开发者提供提示来标明哪些路径在运行时更常用。我们将在后文介绍如何向编译器提供这些提示。

最小化分支（branching）

现代处理器会在指令或数据被真正需要之前预取（prefetch）它们，以尽可能快速地执行程序。

但当程序存在跳转和分支（条件或非条件）时，处理器无法 100% 确定将要执行哪些指令。这意味着处理器有时会错误预测分支方向，导致预取的数据和指令是错误的。

一旦发生错误预测，处理器就必须清除错误指令并重新加载正确的数据和指令，这将导致性能损耗。

为减少分支预测错误带来的性能问题，可以使用循环展开（loop unrolling）、内联（inlining）和分支预测提示等技术。

有些情况下，开发者可以通过对代码进行重构来避免分支，实现相同的功能。由于开发者比编译器更了解代码逻辑，因此有时这些优化只能由开发者完成。

一个简单的去分支（branchless）示例如下，它展示了如何通过数组索引代替条件分支：

我们有一个枚举类型 Side 表示买/卖方向，还有变量记录最近的买卖数量和持仓变化：

#include <cstdio>
#include <cstdint>
#include <cstdlib>

enum class Side : int16_t { BUY = 1, SELL = -1 };

int main() {
    const auto fill_side = (rand() % 2 ? Side::BUY : Side::SELL);
    const int fill_qty = 10;
    printf("fill_side:%s fill_qty:%d.\n", 
        (fill_side == Side::BUY ? "BUY" : (fill_side == Side::SELL ? "SELL" : "INVALID")),
        fill_qty);

    { // 有分支版本
        int last_buy_qty = 0, last_sell_qty = 0, position = 0;
        if (fill_side == Side::BUY) {
            position += fill_qty;
            last_buy_qty = fill_qty;
        } else if (fill_side == Side::SELL) {
            position -= fill_qty;
            last_sell_qty = fill_qty;
        }
        printf("With branching - position:%d last-buy:%d last-sell:%d.\n", 
            position, last_buy_qty, last_sell_qty);
    }

    { // 无分支版本
        int last_qty[3] = {0, 0, 0}, position = 0;
        auto sideToInt = [](Side side) noexcept {
            return static_cast<int16_t>(side);
        };
        const auto int_fill_side = sideToInt(fill_side);
        position += int_fill_side * fill_qty;
        last_qty[int_fill_side + 1] = fill_qty;
        printf("Without branching - position:%d last-buy:%d last-sell:%d.\n",
            position,
            last_qty[sideToInt(Side::BUY) + 1],
            last_qty[sideToInt(Side::SELL) + 1]);
    }
}

运行结果显示两种实现方式的计算结果完全一致：

fill_side:BUY fill_qty:10.
With branching - position:10 last-buy:10 last-sell:0.
Without branching - position:10 last-buy:10 last-sell:0.

指令重排与调度（Reordering and Scheduling Instructions）

编译器可以通过重新排序指令来利用现代处理器的并行处理能力，包括指令级、内存级和线程级的并行。编译器能够识别代码块之间的依赖关系，并对其重排，使程序逻辑不变但执行更快。

虽然现代处理器本身也能进行指令重排，但如果编译器能提前帮助安排顺序，将进一步提升性能。其核心目标是避免现代处理器中的“气泡”（bubbles）和“停顿”（stalls），这些现象会影响流水线处理效率。

例如，下列表达式：

x = a + b + c + d + e + f;

由于前后操作存在数据依赖，因此会被顺序执行，大概耗费 5 个时钟周期：

x = a + b;
x = x + c;
x = x + d;
x = x + e;
x = x + f;

但可以将其重排如下，如果处理器每个周期可以并行完成两次加法，那么只需 3 个周期：

x = a + b;
p = c + d;
q = e + f;
x = x + p;
x = x + q;

注意，这只是一个简化示例，实际效果取决于具体的编译器和处理器架构。

根据架构使用特殊指令

在编译过程中，编译器可以选择使用哪些 CPU 指令来实现高级程序逻辑。当编译器为某一特定架构生成可执行文件时，它可以利用该架构支持的特殊指令。这意味着可以生成更加高效的指令序列，充分利用架构提供的特殊功能。

我们将在“学习编译器优化标志”部分中介绍如何指定使用这些特殊指令。

向量化（Vectorization）

现代处理器可以使用向量寄存器，对多个数据同时进行多次计算。例如，SSE2 指令集拥有 128 位的向量寄存器，可用于同时处理多个整数或浮点数运算（具体取决于数据类型的大小）。

更进一步的如 AVX2 指令集，其向量寄存器为 256 位，能支持更高级别的向量化操作。技术上，这种优化方式可以看作是“根据架构使用特殊指令”的一种扩展。

为了更好地理解向量化，我们来看一个简单的例子：一个循环将两个数组相加的结果存入第三个数组（Chapter3/vector.cpp）：

const size_t size = 1024;
float x[size], a[size], b[size];
for (size_t i = 0; i < size; ++i) {
    x[i] = a[i] + b[i];
}

对于支持 SSE2 指令集等向量寄存器的架构，一个向量寄存器可同时容纳 4 个 4 字节的浮点数，并一次性完成 4 次加法。在这种情况下，编译器可以利用向量化技术，通过循环展开来改写上述代码，使用 SSE2 指令集：

for (size_t i = 0; i < size; i += 4) {
    x[i]     = a[i]     + b[i];
    x[i + 1] = a[i + 1] + b[i + 1];
    x[i + 2] = a[i + 2] + b[i + 2];
    x[i + 3] = a[i + 3] + b[i + 3];
}

降低运算强度（Strength Reduction）

运算强度降低是一种编译器优化技术，指的是将复杂而昂贵的操作替换为更简单、更高效的指令以提升性能。

一个经典的例子是：将除法运算转换为乘以其倒数。另一个例子是：将乘法替换为加法（例如乘以循环索引时）。

我们来看一个简单的例子，将价格从浮点数格式转换为整数格式，通过除以最小价格单位来实现。经过优化后的方式是使用乘法代替除法：

#include <cstdint>

int main() {
    const auto price = 10.125; // 示例价格如：10.125, 10.130, 10.135 ...
    constexpr auto min_price_increment = 0.005;
    [[maybe_unused]] int64_t int_price = 0;

    // 未优化（使用除法）
    int_price = price / min_price_increment;

    // 已优化（使用乘法）
    constexpr auto inv_min_price_increment = 1 / min_price_increment;
    int_price = price * inv_min_price_increment;
}

注意：inv_min_price_increment = 1 / min_price_increment; 是一个 constexpr 表达式，因此它在编译期间就会被求值，不会影响运行时性能。

内联（Inlining）

调用函数是有开销的，之前我们已经提到过，调用函数涉及多个步骤：

1. 保存当前变量状态和执行位置

2. 加载被调用函数的变量和指令

3. 执行函数代码，并（可选地）返回值

4. 恢复调用点，继续程序执行

编译器会尽可能地用函数体替换函数调用，从而避免这些函数调用所带来的额外开销，并提升性能。

不仅如此，当函数体被嵌入到调用点后，编译器还能对这个更大的代码块进行进一步优化，因为它现在可以看到更多上下文。

常量折叠与常量传播

**常量折叠（Constant Folding）**是一种非常简单直接的优化技术，适用于那些其输出可以完全在编译时计算的表达式（即不依赖运行时分支或变量的表达式）。在这种情况下，编译器会在编译时就计算出表达式的结果，并用这个常量值替代表达式的运行时计算。

与之密切相关的还有常量传播（Constant Propagation）。这是一种编译器优化技术，编译器会跟踪代码中已知为编译时常量的值，并将这些值传播到代码中，以开启更多的优化可能。例如，如果编译器可以确定循环迭代器的起始值、步进值或终止值，就可能展开循环（loop unrolling）。

死代码消除（Dead Code Elimination, DCE）

DCE 是指编译器能够检测出对程序行为没有影响的代码块。这可能是因为这些代码块永远不会被执行，或者它们的计算结果从未被使用。一旦发现这些死代码，编译器就可以将它们移除以提高程序性能。现代编译器通常会在某段代码的运行结果未被使用时发出警告，从而帮助开发者发现这类问题。不过，编译器无法在编译阶段检测出所有死代码，因此在生成机器码之后仍有进一步进行死代码消除的空间。

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

CSE 是一种优化技术，编译器会查找重复的计算或指令集合。通过只计算一次并重用结果来消除冗余操作，从而提升效率。

窥孔优化（Peephole Optimization）

窥孔优化是一种相对通用的优化技术，编译器会在指令级别上寻找短小指令序列中的局部优化机会。之所以称为“局部”，是因为编译器并不会尝试理解整个程序的全局逻辑，而是专注于优化短范围内的指令序列。不过，通过反复执行窥孔优化，也可以实现一定程度的全局优化。

尾调用优化（Tail Call Optimization）

函数调用本身是有开销的，包括参数传递、返回值处理以及对缓存和处理器流水线的影响。尾调用优化是指将尾递归（递归调用发生在函数的最后一步）优化为循环，从而消除函数调用的开销和栈操作，避免栈溢出。

如下是一个计算阶乘的递归例子（Chapter3/tail_call.cpp）：

auto __attribute__ ((noinline)) factorial(unsigned n) -> unsigned {
    return (n ? n * factorial(n - 1) : 1);
}
int main() {
    [[maybe_unused]] volatile auto res = factorial(100);
}

当开启优化编译（如使用 g++ -S -Wall -O3 tail_call.cpp）时，编译器会将递归转换为循环以提升效率。你将在生成的汇编代码 tail_call.s 中看到 factorial() 被实现为一个循环，而非递归调用。

循环展开（Loop Unrolling）

循环展开是将循环体复制多次，从而减少条件跳转和计数器的维护开销。对于循环体很小或迭代次数可知的情况，编译器可以完全展开循环。这样可以提高性能，类似于函数内联。

其他循环优化

除了展开，编译器还会使用以下优化：

• 循环分裂（Loop Fission）：将一个大循环拆分为多个小循环以改善缓存命中率。

• 循环合并（Loop Fusion）：将多个迭代次数相同的相邻循环合并成一个，以减少循环开销。

• 循环反转（Loop Inversion）：将 while 循环变换为 do-while，以减少跳转次数。

• 循环交换（Loop Interchange）：交换内外层循环，以提高缓存访问效率。

寄存器变量

寄存器是处理器中最快的存储区域。编译器通常会把访问频繁的变量放入寄存器中，比如局部变量、循环计数器、函数参数、常用表达式或归纳变量（如每次迭代递增的变量）。不过，一些变量（如需要取地址的变量）无法存储在寄存器中。

以下是一个通过归纳变量优化的例子（Chapter3/induction.cpp）：

原始代码：

for(auto i = 0; i < 100; ++i)
    a[i] = i * 10 + 12;

优化后：

int temp = 12;
for(auto i = 0; i < 100; ++i) {
    a[i] = temp;
    temp += 10;
}

活跃范围分析（Live Range Analysis）

活跃范围（Live Range） 是指变量在代码中被使用或有效的范围。如果多个变量在相同范围内活跃，它们必须占用不同的存储空间。如果它们的活跃范围不重叠，编译器可以将它们分配到同一个寄存器。

重物化（Rematerialization）

当某个值可以通过简单计算得到时，编译器可能选择重新计算这个值，而不是从内存中读取，从而避免访问缓存或主存。这一优化依赖于寄存器分配，目标是减少访问内存的时间开销。

代数化简（Algebraic Reductions）

编译器会尝试用更简单的形式替代某些表达式，这通常基于代数规则。在某些情况下，开发者写出的表达式可以被进一步简化。注意，浮点运算因为精度问题，通常不会自动进行代数化简，除非开启特定的优化选项。

例子：

if(!a && !b) {}

可以被简化为：

if(!(a || b)) {}

归纳变量分析（Induction Variable Analysis）

这类优化识别出与循环计数器线性相关的表达式，并将其简化为增量操作。例如，访问数组元素时，其地址可以通过加上对象大小来计算。虽然现代处理器有专门的指令处理这些操作，归纳变量优化仍广泛用于其他场景。

循环不变代码外提（Loop Invariant Code Movement）

如果编译器可以确定某段循环中的代码在整个循环过程中结果恒定，它就会把这段代码移到循环之外。即使某些条件分支中的代码结果不变，编译器也能将其提前执行，减少冗余计算。

例子（Chapter3/loop_invariant.cpp）：

原始代码：

for(auto i = 0; i < 100; ++i)
    a[i] = (doSomething(50) + b * 2) + 1;

优化后：

auto temp = (doSomething(50) + b * 2) + 1;
for(auto i = 0; i < 100; ++i)
    a[i] = temp;

静态单赋值（SSA）优化

SSA 是一种程序转换形式，确保每个变量只被赋值一次。这样可以极大简化数据流分析，使编译器能应用更多优化技术。

去虚函数化（Devirtualization）

在 C++ 中，调用虚函数通常依赖虚表（vtable）。去虚函数化是指编译器在编译阶段就能确定应该调用哪个函数，从而将虚函数调用转换为普通函数调用。这在只有一个派生类或某些分支下对象类型唯一时尤为常见，有助于提高性能。