Code generation quality for a recursive function

[lovasoa]

After reading this blog post recently, I was very happily surprised with the quality of the code generation for the following function :

fn middle(xs: &[u32]) -> Option<&u32> {
    match xs {
        [_, inner @ .., _] => middle(inner),
        [x] => Some(x),
        [] => None,
    }
}

example::middle:
        cmp     rsi, 2
        jb      .LBB0_2
        add     rsi, -2
        mov     rax, rsi
        and     rax, -2
        lea     rdi, [rdi + 2*rax]
        add     rdi, 4
        and     esi, 1
.LBB0_2:
        xor     eax, eax
        cmp     rsi, 1
        cmove   rax, rdi
        ret

It is amazing what the compiler is able to achieve !

But then, I tried this very slight variation :

pub fn middle(xs: &[u32]) -> Option<u32> {
    match xs {
        [_, inner @ .., _] => middle(inner),
        [x] => Some(*x),
        [] => None,
    }
}

(the only difference is that we are returning an u32 instead of an &u32)

And the generated code changes dramatically:

example::middle:
        push    rax
        cmp     rsi, 1
        jbe     .LBB0_1
        add     rdi, 4
        add     rsi, -2
        call    qword ptr [rip + example::middle@GOTPCREL]
        pop     rcx
        ret
.LBB0_1:
        cmp     rsi, 1
        jne     .LBB0_2
        mov     edx, dword ptr [rdi]
        mov     eax, 1
        pop     rcx
        ret
.LBB0_2:
        xor     eax, eax
        pop     rcx
        ret

Is there something making the optimization harder to apply in the second case, or is it a bug somewhere in the compiler ?

[nikic]

Without looking into it, my guess is that Option<&u32> is just a pointer, while Option is a pair and the extra insertelement/extractelement instructions interfere with TCO.

[lovasoa]

@nikic : This seems to be correct ! Replacing u32 with NonZeroU32 makes the compiler generate the efficient version again.

[lovasoa]

Here is a more simple reproduction of the issue without slice patterns :

pub fn last(xs: &[u32]) -> Option<u32> {
    match xs.len() {
        0 => None,
        1 => Some(xs[0]),
        _ => last(&xs[1..])
    }
}

The compiler fails to apply TCO to the function. If u32 is replaced with NonZeroU32, then TCO is applied again.