编译器优化：尾调用优化

尾调用（tail call）是一个作为函数最后一个动作发生的调用 —— 在它返回之后，函数里再无事可做。当编译器识别出这个模式时，它可以把调用替换成一次跳转，复用当前栈帧而不是分配新的一个。结果是：递归函数可以用和循环相同的栈深度执行。

原理：GCD

求最大公约数的欧几里得算法是一个干净的例子：

unsigned int gcd(unsigned int a, unsigned int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

递归调用 gcd(b, a % b) 是一个尾调用：gcd 在它返回之后什么都不做，只是把结果传回去。编译器可以认识到：在这次调用处，当前栈帧已经不再需要。

GCC 和 Clang 在 -O2 下会生成类似这样的代码：

gcd:
    mov eax, edi          ; eax = a
    test esi, esi
    je .done              ; b == 0 则返回 a
    mov edx, esi
.loop:
    mov ecx, edx          ; ecx = b
    xor edx, edx
    div ecx               ; eax = a / b，edx = a % b
    mov eax, ecx          ; a = b
    test edx, edx
    jne .loop             ; 余数非 0 则继续
    mov eax, ecx
.done:
    ret

没有 call 指令。递归被完全替换成循环。不论算法需要多少次迭代，栈深度保持不变。

TCO 的条件

并非每次递归调用都够格。编译器只有在以下条件成立时才能应用尾调用优化：

调用是函数返回之前的最后一个操作。
被调用方的返回值被直接返回（没有再变换）。
调用之后，当前帧的局部变量不再被需要。

结构越干净，越有可能应用 TCO。在递归调用之后加一点计算 —— 哪怕是 return 1 + gcd(b, a % b) 这样小的东西 —— 都会让这个调用不是尾调用，因为那次加法必须发生在递归返回之后。

对其他函数的尾调用

TCO 适用于对其他函数的调用，不只是自递归。如果函数 f 以 return g(x) 结尾、g 的调用约定相同或兼容，编译器可以生成一条到 g 的 jmp，而不是 call。f 的调用方直接看到 g 的返回值。

这在状态机和类协程模式中很有用 —— 控制在各个处理器之间转移，栈不增长。

保证 TCO：clang::musttail

编译器把 TCO 作为一种可选优化。在调试构建或关闭优化时，它通常不会发生。如果你的程序的正确性依赖尾调用被消除 —— 比如一个深度递归转移链的状态机 —— 你需要一个保证。

Clang 提供了 [[clang::musttail]] 属性：

[[clang::musttail]] return next_handler(state);

如果编译器不能对这次调用应用 TCO，它会发出错误，而不是悄悄生成普通调用。对于”栈溢出是正确性问题、不仅是性能问题”的代码，这是一个编译期的安全网。

参数顺序影响效率

当一个函数以改动过的参数对自己做尾调用时，编译器需要在跳转前更新参数寄存器。如果新的参数恰好已经在正确的寄存器里，跳转是免费的；如果不是，编译器就得做一些 shuffle，可能需要临时量或额外的 move。

在 GCD 的例子里，两个参数是 b 和 a % b。除法之后，b 在 ecx，余数在 edx。编译器需要把它们放到 edi 和 esi 以供下一次迭代使用。这增加了一点寄存器搬动，但仍远比函数调用和栈帧分配便宜。

设计期望被尾调用优化的递归函数时，可以考虑能否安排参数顺序以最小化寄存器搬动。

应用：解释器派发

TCO 在高性能解释器和 CPU 模拟器中有更高级的用法。字节码解释器的传统结构是：

while (running) {
    switch (fetch_opcode()) {
        case OP_ADD: execute_add(); break;
        case OP_JUMP: execute_jump(); break;
        // ...
    }
}

这个结构只有一个间接分支点 —— 那个 switch —— 必须对所有可能的 opcode 做预测。分支预测器在同一条程序计数器位置上看到一串剧烈变化的目标，很难预测好。

用 TCO 的一种替代：

void execute_add(State* s) {
    // 执行 add
    [[clang::musttail]] return dispatch(s);
}

void execute_jump(State* s) {
    // 执行 jump
    [[clang::musttail]] return dispatch(s);
}

其中 dispatch 取出下一条 opcode 并尾调用对应的处理器。在应用 TCO 后，每个处理器以一次”来自它自己调用点”的间接跳转结尾。分支预测器现在每个 opcode 处理器看到一个间接分支 —— 关键是，每个都有自己独立的预测历史。一个 CMP 后几乎总跟着 BNE，就能让 execute_cmp 处理器里的预测器对那个模式做特化。

这种技术有时被称为”threaded code”或”computed goto dispatch”，Python、Ruby 的实现、许多模拟器都因此采用它。

小结

尾调用优化把递归结构转换为迭代执行，消除栈增长，让这类代码也能享受循环才有的 CPU 级优化。当调用结构满足条件时它自动应用，当正确性需要时可以用 [[clang::musttail]] 强制保证。除了简单的递归消除，TCO 还让某些架构性的模式 —— 比如解释器中的按 opcode 派发 —— 变得可行，否则就需要手写汇编或依赖平台特有技巧。