函数式编程语言中的尾调用优化是如何在汇编级别实现的？

Question

LISPs或MLs如何实现尾调用优化？

- mcandre

---

在提问之前，你做过任何研究吗？ - Patrick

这里是一个开始查找的地方：https://en.wikipedia.org/wiki/Tail_call#Implementation_methods - huon

你也可以在SICP书中阅读相关内容，5.4.2 序列求值和尾递归。 - Patrick

Answer 1

我无法详细说明不同编译器/解释器的具体实现细节，但通常情况下尾调用优化的操作方式如下所示：

通常函数调用涉及以下内容： 1.为返回值分配堆栈空间 2.将当前指针压入堆栈中 3.为函数参数分配堆栈空间并适当设置它们 4.调用您的函数 5.为了返回，设置其返回空间，弹出应该返回到的指针并跳转到该指针

然而，当一个函数处于尾部位置时，这基本上意味着您正在返回要调用的函数的结果，可以使用以下技巧：

1.重复使用为自己的返回值分配的堆栈空间，作为为即将调用的函数分配的返回值的堆栈空间 2.重复使用您应该返回的指针作为函数即将调用的指针的指针 3.释放自己的参数堆栈空间 4.为参数分配空间并适当设置 5.设置参数的值 6.调用函数 7.当它返回时，它将直接返回给您的调用者。

注意，#1和#2实际上并不涉及任何工作，#3根据您的实现可能会很棘手或简单，并且4-7并不涉及要调用的函数中的任何特殊内容。还要注意，所有这些都导致相对于您的调用堆栈而言堆栈增长为0，因此这允许无限递归，通常加速一些东西。

另请注意，这种优化不仅可以应用于直接递归函数，还可以应用于共递归函数，实际上是所有在尾部位置的调用。

- hexist

Answer 2

哪些函数可以进行尾调用优化取决于CPU体系结构和/或操作系统。这是因为不同的“调用约定”（用于传递函数参数和/或在函数之间传输控制）在CPU和/或操作系统之间存在差异。通常归结为尾调用中是否必须从堆栈中传递任何内容。例如，考虑以下函数：

void do_a_tailcall(char *message)
{
    printf("Doing a tailcall here; you said: %s\n", message);
}

If you compile this, even with high optimization (-O8 -fomit-frame-pointer), on 32bit x86 (Linux), you get:

do_a_tailcall:
        subl    $12, %esp
        movl    16(%esp), %eax
        movl    $.LC0, (%esp)
        movl    %eax, 4(%esp)
        call    printf
        addl    $12, %esp
        ret
.LC0:
        .string "Doing a tailcall here; you said: %s\n"

i.e. a classical function, with stackframe setup/teardown (subl $12, %esp / addl $12, %esp) and an explicit ret from the function.

In 64bit x86 (Linux), this looks like:

do_a_tailcall:
        movq    %rdi, %rsi
        xorl    %eax, %eax
        movl    $.LC0, %edi
        jmp     printf
.LC0:
        .string "Doing a tailcall here; you said: %s\n"

so it got tail-optimized.

On an entirely different type of CPU architecture (SPARC), this looks like (I've left the compiler's comment in):

.L16:
        .ascii  "Doing a tailcall here; you said: %s\n\000"
!
! SUBROUTINE do_a_tailcall
!
.global do_a_tailcall
do_a_tailcall:
         sethi   %hi(.L16),%o5
         or      %g0,%o0,%o1
         add     %o5,%lo(.L16),%o0
         or      %g0,%o7,%g1
         call    printf  ! params =  %o0 %o1     ! Result =      ! (tail call)
         or      %g0,%g1,%o7

Yet another one ... ARM (Linux EABI):

.LC0:
        .ascii  "Doing a tailcall here; you said: %s\012\000"
do_a_tailcall:
        @ args = 0, pretend = 0, frame = 0
        @ frame_needed = 0, uses_anonymous_args = 0
        @ link register save eliminated.
        mov     r1, r0
        movw    r0, #:lower16:.LC0
        movt    r0, #:upper16:.LC0
        b       printf

The differences here are the way arguments are passed, and control is transferred:

• 32位x86（stdcall / cdecl类型调用）在堆栈上传递参数，因此尾部调用优化的潜力非常有限 - 除了特定的边角情况，只有在精确的参数传递或调用不需要任何参数的函数时，才有可能发生。

• 64位x86（UNIX x86_64风格，但在Win64上并没有太大区别）在寄存器中传递一定数量的参数，这使得编译器可以更自由地调用而无需传递任何内容到堆栈。通过jmp进行控制转移只需使尾部调用的函数继承堆栈 - 包括最顶层的值，它将是原始调用者do_a_tailcall的返回地址。

• SPARC不仅在寄存器中传递函数参数，还传递返回地址（它使用一个链接寄存器，%o7）。因此，虽然您通过call进行控制转移，但实际上这并不强制产生新的堆栈帧，因为它只是设置链接寄存器和程序计数器...通过 SPARC 的另一个奇怪特性 - 所谓的延迟槽指令（or %g0,%g1,%o7 - sparc-ish for mov %g1,%o7 - 在call之后但在达到call目标之前执行）。上述代码是从旧版本编译器生成的...并不像理论上那样优化...

• ARM与SPARC类似，它使用链接寄存器，尾递归函数将其传递未修改/未触及的尾调用。它也类似于x86，通过尾递归使用b（分支）而不是“call”等效项（bl，分支和链接）。

在至少一些参数传递可以在寄存器中发生的所有体系结构中，编译器可以对各种函数应用尾调用优化。

- FrankH.