73

特别是如果我有以下代码：

func sum(n: Int, acc: Int) -> Int {
  if n == 0 { return acc }
  else { return sum(n - 1, acc + n) }
}

Swift 编译器会将其优化为循环吗？在下面一个更有趣的案例中是这样吗？

func isOdd(n: Int) -> Bool {
  if n == 0 { return false; }
  else { return isEven(n - 1) }
}

func isEven(n: Int) -> Bool {
  if n == 0 { return true }
  else { return isOdd(n - 1) }
}
4

2 回答 2

79

最好的检查方法是检查编译器生成的汇编语言代码。我把上面的代码编译成：

swift -O3 -S tco.swift >tco.asm

输出的相关部分

.globl    __TF3tco3sumFTSiSi_Si
    .align    4, 0x90
__TF3tco3sumFTSiSi_Si:
    pushq    %rbp
    movq    %rsp, %rbp
    testq    %rdi, %rdi
    je    LBB0_4
    .align    4, 0x90
LBB0_1:
    movq    %rdi, %rax
    decq    %rax
    jo    LBB0_5
    addq    %rdi, %rsi
    jo    LBB0_5
    testq    %rax, %rax
    movq    %rax, %rdi
    jne    LBB0_1
LBB0_4:
    movq    %rsi, %rax
    popq    %rbp
    retq
LBB0_5:
    ud2

    .globl    __TF3tco5isOddFSiSb
    .align    4, 0x90
__TF3tco5isOddFSiSb:
    pushq    %rbp
    movq    %rsp, %rbp
    testq    %rdi, %rdi
    je    LBB1_1
    decq    %rdi
    jo    LBB1_9
    movb    $1, %al
LBB1_5:
    testq    %rdi, %rdi
    je    LBB1_2
    decq    %rdi
    jo    LBB1_9
    testq    %rdi, %rdi
    je    LBB1_1
    decq    %rdi
    jno    LBB1_5
LBB1_9:
    ud2
LBB1_1:
    xorl    %eax, %eax
LBB1_2:
    popq    %rbp
    retq

    .globl    __TF3tco6isEvenFSiSb
    .align    4, 0x90
__TF3tco6isEvenFSiSb:
    pushq    %rbp
    movq    %rsp, %rbp
    movb    $1, %al
LBB2_1:
    testq    %rdi, %rdi
    je    LBB2_5
    decq    %rdi
    jo    LBB2_7
    testq    %rdi, %rdi
    je    LBB2_4
    decq    %rdi
    jno    LBB2_1
LBB2_7:
    ud2
LBB2_4:
    xorl    %eax, %eax
LBB2_5:
    popq    %rbp
    retq

生成的代码中没有调用指令，只有条件跳转（je/// ）。这清楚地表明 Swift 在这两种情况下都进行了尾调用优化。jnejojno

此外，isOdd/isEven函数的有趣之处在于编译器似乎不仅执行 TCO，而且在每种情况下都内联其他函数。

于 2014-06-17T22:42:31.787 回答
24

是的，swift 编译器在某些情况下会执行尾调用优化：

func sum(n: Int, acc: Int) -> Int {
    if n == 0 { return acc }
    else { return sum(n - 1, acc: acc + 1) }
}

作为一个全局函数，这将使用“最快”优化级别 ( -O) 上的常量堆栈空间。

如果它在结构内部，它仍将使用常量堆栈空间。然而，在一个类中，编译器不会执行 tco，因为该方法可能在运行时被覆盖。

Clang 还支持 Objective-C 的 tco，但通常release在递归调用之后调用 ARC，从而阻止了这种优化，有关更多详细信息，请参阅Jonathon Mah 的这篇文章。

ARC 似乎也阻止了 Swift 中的 TCO：

func sum(n: Int, acc: Int, s: String?) -> Int {
    if n == 0 { return acc }
    else { return sum(n - 1, acc + 1, s) }
}

在我的测试中没有执行 TCO。

于 2014-06-12T06:16:32.800 回答