Swift 是否实现了尾部调用优化? 并且是在相互递归的情况下？

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

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) }
}
10385 次浏览
小开

是的，在某些情况下，快速编译器会执行尾部呼叫优化:

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，但是通常 ARC 在递归调用之后调用 release，因此阻止了这种优化，请参阅 作者: Jonathon Mah了解更多细节。

ARC 似乎也在阻止斯威夫特的 TCO:

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

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

小开
最佳答案

检查的最佳方法是检查编译器生成的汇编语言代码。我采用上面的代码并用以下方式编译:

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/jne/jo/jno)。这清楚地表明 Swift 确实在 都有情况下进行了尾部调用优化。

此外，isOdd/isEven函数很有趣，因为编译器似乎不仅执行 TCO，而且在每种情况下都内联另一个函数。


提交答案