tail recursion in gcc without return statement

Question

Apparently the following code works in GCC. I tried that code in onlinegdb.

# include <stdio.h>

int calc_gcd (int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
        calc_gcd (b, r);
    }
}

int main() {
    int a, b, gcd, dividend, divisor;
    printf ("Enter two numbers: ");
    scanf ("%d%d", &a, &b);
    dividend = (a > b) ? a : b;
    divisor = (a < b) ? a : b;
    gcd = calc_gcd (dividend, divisor);
    printf ("GCD = %d\n", gcd);
    return 0;
}

But it fails in clang 13 with following results

tail_recursion_gcd.c:15:1: warning: non-void function does not return a value in all control paths [-Wreturn-type]
}
^
1 warning generated.
Enter two numbers: 15 10
GCD = 127       // garbage

I'm not getting it. Clearly what GCC allows isn't intuitive, you have to return from a function.

I've tried the following but that doesn't work in gcc

# include <stdio.h>

int useless_func()
{
    3050;
}
int main() {
    printf("result = %d", useless_func());
    return 0;
}

The output is result = 0

Answer 1

TL;DR: The GCD function your teacher gave you is not portable.

What you want follows:

int calc_gcd (int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
      return calc_gcd (b, r);
    }
}

What version of GCC are you using, and on what operating system?

GCC is much more lenient than Clang. It looks like GCC decided that the function calc_gcd shouldn't fail and should return the result of calc_gcd(b, r).

When you compiled with Clang, I'm surprised that it didn't return 1. It did when I compiled on an M1 MacBook Pro.

From here:

Flowing off the end of a function is equivalent to a return with no value; this results in undefined behavior in a value-returning function.

On x86_64 Linux, when a function that returns a non-void value is called, space is allocated on the stack for the return value. Thus, with no explicit return statement, some value is still returned.

Note: on x86_64, the return value is stored in RAX (EAX is the lower bits).

I compiled with GCC 7.5.0 on x86_64 Ubuntu Server 18.04. The command I used was gcc -o gcd gcd.c -no-pie -g. Here's the assembly dump for calc_gcd:

   0x00000000004005c7 <+0>:     push   rbp
   0x00000000004005c8 <+1>:     mov    rbp,rsp
   0x00000000004005cb <+4>:     sub    rsp,0x20
   0x00000000004005cf <+8>:     mov    DWORD PTR [rbp-0x14],edi
   0x00000000004005d2 <+11>:    mov    DWORD PTR [rbp-0x18],esi
   0x00000000004005d5 <+14>:    mov    eax,DWORD PTR [rbp-0x14]
   0x00000000004005d8 <+17>:    cdq
   0x00000000004005d9 <+18>:    idiv   DWORD PTR [rbp-0x18]
   0x00000000004005dc <+21>:    mov    DWORD PTR [rbp-0x4],edx
   0x00000000004005df <+24>:    cmp    DWORD PTR [rbp-0x4],0x0
   0x00000000004005e3 <+28>:    jne    0x4005ea <calc_gcd+35>
   0x00000000004005e5 <+30>:    mov    eax,DWORD PTR [rbp-0x18]
   0x00000000004005e8 <+33>:    jmp    0x4005f9 <calc_gcd+50>
   0x00000000004005ea <+35>:    mov    edx,DWORD PTR [rbp-0x4]
   0x00000000004005ed <+38>:    mov    eax,DWORD PTR [rbp-0x18]
   0x00000000004005f0 <+41>:    mov    esi,edx
   0x00000000004005f2 <+43>:    mov    edi,eax
   0x00000000004005f4 <+45>:    call   0x4005c7 <calc_gcd>
   0x00000000004005f9 <+50>:    leave
   0x00000000004005fa <+51>:    ret

And with Clang 6.0.0:

   0x0000000000400540 <+0>:     push   rbp
   0x0000000000400541 <+1>:     mov    rbp,rsp
   0x0000000000400544 <+4>:     sub    rsp,0x20
   0x0000000000400548 <+8>:     mov    DWORD PTR [rbp-0x8],edi
   0x000000000040054b <+11>:    mov    DWORD PTR [rbp-0xc],esi
   0x000000000040054e <+14>:    mov    eax,DWORD PTR [rbp-0x8]
   0x0000000000400551 <+17>:    cdq
   0x0000000000400552 <+18>:    idiv   DWORD PTR [rbp-0xc]
   0x0000000000400555 <+21>:    mov    DWORD PTR [rbp-0x10],edx
   0x0000000000400558 <+24>:    cmp    DWORD PTR [rbp-0x10],0x0
   0x000000000040055c <+28>:    jne    0x40056d <calc_gcd+45>
   0x0000000000400562 <+34>:    mov    eax,DWORD PTR [rbp-0xc]
   0x0000000000400565 <+37>:    mov    DWORD PTR [rbp-0x4],eax
   0x0000000000400568 <+40>:    jmp    0x40057b <calc_gcd+59>
   0x000000000040056d <+45>:    mov    edi,DWORD PTR [rbp-0xc]
   0x0000000000400570 <+48>:    mov    esi,DWORD PTR [rbp-0x10]
   0x0000000000400573 <+51>:    call   0x400540 <calc_gcd>
   0x0000000000400578 <+56>:    mov    DWORD PTR [rbp-0x14],eax
   0x000000000040057b <+59>:    mov    eax,DWORD PTR [rbp-0x4]
   0x000000000040057e <+62>:    add    rsp,0x20
   0x0000000000400582 <+66>:    pop    rbp
   0x0000000000400583 <+67>:    ret

You can see that the compilers made different choices in optimizations.

In fact, with GCC, rbp-0x18 is equal to 0x00000005 by +38. With Clang, rbp-0x4 is equal to something entirely different. On my machine, in pwndbg, it was 0x00007fff.

Answer 2

Your code is bugged. It is allowed to return from an int function without returning a value only if the value will never be consumed. This is a holdover from K&R C that should no longer be used.

int calc_gcd (int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
        calc_gcd (b, r);
    }
}

Clearly incorrect. You want.

int calc_gcd (int a, int b) {
    int r = a % b;
    if (r == 0) {
        return b;
    } else {
        return calc_gcd (b, r);
    }
}

In fact this specific code tends to work at -O0 because the return value is left over left over in the register is the return value you want.