3

LISP 或 ML 如何实现尾调用优化？

4

2 回答 2

6

我不能谈论不同编译器/解释器的确切实现细节，但是一般来说尾调用优化是这样操作的：

通常，函数调用涉及以下内容：

  1. 为返回分配堆栈空间
  2. 将当前指令指针压入堆栈
  3. 为函数参数分配堆栈空间并适当设置它们
  4. 调用你的函数
  5. 要返回它适当地设置它的返回空间，弹出它应该返回的指令指针并跳转到它

但是，当一个函数处于尾部位置时，这几乎意味着您正在返回您将要调用的函数的结果，您可能会很棘手并且做

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

请注意，#1 和#2 实际上不涉及任何工作，#3 可能很棘手或简单，具体取决于您的实现，并且 4-7 不涉及您正在调用的函数的任何特殊内容。另请注意，所有这些都会导致相对于您的调用堆栈的堆栈增长为 0，因此这允许无限递归并通常加快速度。

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

于 2012-10-22T19:01:45.930 回答
3

它取决于 CPU 架构和/或操作系统，可以对尾调用进行优化。这是因为调用约定（用于传递函数参数和/或在函数之间转移控制）在 CPU 和/或操作系统之间有所不同。它通常归结为尾调用中传递的任何内容是否必须来自堆栈。举个例子，像这样的函数：

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

如果您-O8 -fomit-frame-pointer在 32 位 x86 (Linux) 上编译它，即使经过高度优化 ( )，您会得到：

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"
即一个经典函数，具有堆栈框架设置/拆卸（subl $12, %esp/ addl $12, %esp）和ret函数的显式。

在 64 位 x86 (Linux) 中，这看起来像：

do_a_tailcall:
        movq    %rdi, %rsi
        xorl    %eax, %eax
        movl    $.LC0, %edi
        jmp     printf
.LC0:
        .string "Doing a tailcall here; you said: %s\n"
所以它得到了尾部优化。

在完全不同类型的 CPU 架构 (SPARC) 上，这看起来像（我在其中留下了编译器的注释）：


.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
还有一个……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
这里的区别在于参数的传递方式和控制的转移方式：

  • 32 位 x86（stdcall/cdecl类型调用）在堆栈上传递参数，因此尾调用优化的潜力非常有限 - 除了特定的极端情况，它只可能发生在精确的参数传递或完全不带参数的尾调用函数时.

  • 64 位 x86（UNIXx86_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在尾递归上使用 (branch) 而不是“调用”等价物 ( bl, branch-and-link)。

在所有至少可以在寄存器中传递一些参数的架构中，编译器可以将尾调用优化应用于各种函数。

于 2012-10-23T11:10:03.607 回答