tail recursion in gcc without return statement-CodePudding

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

CodePudding user response：

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.

CodePudding user response：

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.