Does Swift use tail call optimization? and in mutual recursion?

Question

In particular, if I have the following code:

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

Does the Swift compiler optimize it before the loop? And does it in a more interesting case below?

 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) } } 

Answer 1

The best way to check is to learn the assembler language code generated by the compiler. I took the code above and compiled it with:

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

The corresponding part of the output

 .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 

The generated code has no calling instructions, only conditional jumps ( je / jne / jo / jno ). This clearly demonstrates that Swift performs call optimization in both cases.

In addition, the isOdd / isEven interesting in that the compiler not only performs TCO, but also builds a different function in each case.

Answer 2

Yes, the fast compiler in some cases performs tail call optimization:

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

As a global function, this will use a constant stack space at the Fastest ( -O ) level.

If it is inside a structure, it will still use the constant stack space. Inside the class, however, the compiler does not execute tco because the method can be overridden at runtime.

Clang also supports tco for Objective-C, but ARC often calls release after a recursive call, thereby preventing this optimization, see this article by Jonathan Mach for more details.

ARC also seems to prevent TCO in Swift:

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

There was no TCO in my tests.