6

Experimenting with tail call optimization (tco), I stumbled upon the following curious example:

unsigned long long int fac1(unsigned long long int n){
  if (n==0)
    return 1;
  return n*fac1(n-1);
}

actually, I was impressed, that gcc was able to perform the tco here (with -O2 flag), because it is not that straight forward:

fac1(unsigned long long):
        testq   %rdi, %rdi
        movl    $1, %eax
        je      .L4
.L3:
        imulq   %rdi, %rax
        subq    $1, %rdi
        jne     .L3
        rep ret
.L4:
        rep ret

However, after the change of the return type from unsigned long long int to unsigned int gcc was not able to perform tlo:

unsigned int fac2(unsigned long long int n){
  if (n==0)
    return 1;
  return n*fac2(n-1);
}

we can clearly see the recursive call in the resulting assembly:

fac2(unsigned long long):
        testq   %rdi, %rdi
        jne     .L16
        movl    $1, %eax
        ret
.L16:
        pushq   %rbx
        movq    %rdi, %rbx
        leaq    -1(%rdi), %rdi
        call    fac2(unsigned long long)
        imull   %ebx, %eax
        popq    %rbx
        ret

At first, I dismissed this as a missed optimization, but now I'm not that sure, because clang isn't able to perform this optimization as well. So maybe there are subtlities of the language I'm not aware of which prevent this optimization.

Why doesn't gcc perform the tail-call-optimization for the function fac2 but only for fac1?

It is clear to me, that in the second version, the result must be downcasted. Obviously this is the only difference. But why should this be a problem and prevent tlo?

For example, if I help the compiler and rewrite my function as a classic tail-recursion (which should produce identical results to version fac2):

unsigned int tlo_fac(unsigned long long int n, unsigned long long int cur){
  if (n==0)
    return cur;
  return tlo_fac(n-1, n*cur);
}

unsigned int fac(unsigned long long int n){
  return tlo_fac(n,1);
}

I get a tlo-optimized version which is identical to fac1 (the high 32bit are allowed to contain garbage, so imulq can be used after inlining):

fac(unsigned long long):
        testq   %rdi, %rdi
        movl    $1, %eax
        je      .L10
.L11:
        imulq   %rdi, %rax
        subq    $1, %rdi
        jne     .L11
.L10:
        rep ret
ead
  • 32,758
  • 6
  • 90
  • 153

1 Answers1

2

In fact2(), after recursion is completed a cast will be needed from unsigned long long int to unsigned int

unsigned int fac2(unsigned int n) produces the below assembly,

fac2(unsigned int):
        testl   %edi, %edi
        movl    $1, %eax
        je      .L10
.L9:
        imull   %edi, %eax
        subl    $1, %edi
        jne     .L9
        rep ret
.L10:
        rep ret
Gaurav Sehgal
  • 7,422
  • 2
  • 18
  • 34
  • 2
    This may confuse GCC, but it does not *fundamentally* prevent rewriting it to iteration – harold Oct 25 '17 at 11:59
  • I'm aware, that a cast is needed and also that changing input parameter type to the output type would lead to a tlo'ed version. But it is not clear to me, why this would prevent TLO. – ead Oct 25 '17 at 12:21
  • 1
    @ead To perform tail call optimization, the recursive call should be the last thing to be done from the function, `return n*fac1(n-1);`, the last thing is not the function call `fact(n-1)`, but the casting of result. – Gaurav Sehgal Oct 25 '17 at 12:35
  • 2
    actually, the order is: recur-call, multiplication, casting. So even without casting the recur-call is not the last thing done in the function (and this is the part which impressed me in the first place) – ead Oct 25 '17 at 12:56