Does Swift implement tail call optimization? and in mutual recursion case?

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

Will Swift compiler optimize it to a loop? And does it so 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 examine the assembly language code generated by the compiler. I took the code above and compiled it with:

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

The relevant 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 

There are no call instructions in the generated code, only conditional jumps (je / jne / jo / jno). This clearly suggests that Swift does do tail call optimizations in both cases.

In addition, the isOdd/isEven functions are interesting in that the compiler not only seems to perform TCO but also inlines the other function in each case.