Why g++ still optimizes tail recursion when the recursion function result is multiplied?

Question

They say, the tail recursion optimization works only when the the call is just before return from the function. So they show this code as example of what shouldn't be optimized by C compilers:

long long f(long long n) {
    return n > 0 ? f(n - 1) * n : 1;
}

because there the recursive function call is multiplied by n which means the last operation is multiplication, not recursive call. However, it is even on -O1 level:

recursion`f:
    0x100000930 <+0>:  pushq  %rbp
    0x100000931 <+1>:  movq   %rsp, %rbp
    0x100000934 <+4>:  movl   $0x1, %eax
    0x100000939 <+9>:  testq  %rdi, %rdi
    0x10000093c <+12>: jle    0x10000094e               
    0x10000093e <+14>: nop    
    0x100000940 <+16>: imulq  %rdi, %rax
    0x100000944 <+20>: cmpq   $0x1, %rdi
    0x100000948 <+24>: leaq   -0x1(%rdi), %rdi
    0x10000094c <+28>: jg     0x100000940               
    0x10000094e <+30>: popq   %rbp
    0x10000094f <+31>: retq

They say that:

Your final rules are therefore sufficiently correct. However, return n * fact(n - 1) does have an operation in the tail position! This is the multiplication *, which will be the last thing the function does before it returns. In some languages, this might actually be implemented as a function call which could then be tail-call optimized.

However, as we see from ASM listing, multiplication is still an ASM instruction, not a separate function. So I really struggle to see difference with accumulator approach:

int fac_times (int n, int acc) {
    return (n == 0) ? acc : fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times(n, 1);
}

This produces

recursion`fac_times:
    0x1000008e0 <+0>:  pushq  %rbp
    0x1000008e1 <+1>:  movq   %rsp, %rbp
    0x1000008e4 <+4>:  testl  %edi, %edi
    0x1000008e6 <+6>:  je     0x1000008f7               
    0x1000008e8 <+8>:  nopl   (%rax,%rax)
    0x1000008f0 <+16>: imull  %edi, %esi
    0x1000008f3 <+19>: decl   %edi
    0x1000008f5 <+21>: jne    0x1000008f0               
    0x1000008f7 <+23>: movl   %esi, %eax
    0x1000008f9 <+25>: popq   %rbp
    0x1000008fa <+26>: retq

Am I missing something? Or it's just compilers became smarter?

Of course, f(n-1)*n is n*f(n-1). I don't see how this comes as a surprise. — MSalters
@MSalters I'm not surprised about multiplication commutativity as it's the basic math rule. My question was why is this optimized when the actual result is not a recursive function call result, but multiplication (since you put operands first, one of which is recursive call, and then you do multiplication over them, i. e. a f() * in postfix notation). This was a surprise for my colleagues as well. But it seems if a math action is done between function call and a constant, it is an easy task for optimizer. — efpies
What is the source of the quotes, i.e. who is "they"? To me, it seems like the optimizer is at least smarter than your source... — anderas

anderas anderas · Accepted Answer · 2016-03-22T09:52:43

As you see in the assembly code, the compiler is smart enough to turn your code into a loop that is basically equivalent to (disregarding the different data types):

int fac(int n)
{
    int result = n;
    while (--n)
        result *= n;
    return result;
}

GCC is smart enough to know that the state needed by each call to your original f can be kept in two variables (n and result) through the whole recursive call sequence, so that no stack is necessary. It can transform f to fac_times, and both to fac, so to say. This is most likely not only a result of tail call optimization in the strictest sense, but one of the loads of other heuristics that GCC uses for optimization.

(I can't go more into detail regarding the specific heuristics that are used here since I don't know enough about them.)

Why g++ still optimizes tail recursion when the recursion function result is multiplied?

2 Answers