Is the stack frame required for all functions in C on x86-64?

Question

I've made a function to calculate the length of a C string (I'm trying to beat clang's optimizer using -O3). I'm running macOS.

_string_length1:
    push rbp
    mov rbp, rsp
    xor rax, rax
.body:
    cmp byte [rdi], 0
    je .exit
    inc rdi
    inc rax
    jmp .body
.exit:
    pop rbp
    ret

This is the C function I'm trying to beat:

size_t string_length2(const char *str) {
  size_t ret = 0;
  while (str[ret]) {
    ret++;
  }
  return ret;
}

And it disassembles to this:

string_length2:
    push rbp
    mov rbp, rsp
    mov rax, -1
LBB0_1:
    cmp byte ptr [rdi + rax + 1], 0
    lea rax, [rax + 1]
    jne LBB0_1
    pop rbp
    ret

Every C function sets up a stack frame using push rbp and mov rbp, rsp, and breaks it using pop rbp. But I'm not using the stack in any way here, I'm only using processor registers. It worked without using a stack frame (when I tested on x86-64), but is it necessary?

Answer 1

No, the stack frame is, at least in theory, not always required. An optimizing compiler might in some cases avoid using the call stack. Notably when it is able to inline a called function (in some specific call site), or when the compiler successfully detects a tail call (which reuses the caller's frame).

Read the ABI of your platform to understand requirements related to the stack.

You might try to compile your program with link time optimization (e.g. compile and link with gcc -flto -O2) to get more optimizations.

In principle, one could imagine a compiler clever enough to (for some programs) avoid using any call stack.

---

BTW, I just compiled a naive recursive long fact(int n) factorial function with GCC 7.1 (on Debian/Sid/x86-64) at -O3 (i.e. gcc -fverbose-asm -S -O3 fact.c). The resulting assembler code fact.s contains no call machine instruction.

Answer 2

Every C function sets up a stack frame using...

This is true for your compiler, not in general. It is possible to compile a C program without using the stack at all—see, for example, the method CPS, continuation passing style. Probably no C compiler on the market does so, but it is important to know that there are other ways to execute programs, in addition to stack-evaluation.

The ISO 9899 standard says nothing about the stack. It leaves compiler implementations free to choose whichever method of evaluation they consider to be the best.