5

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?

Improve this question
16
  • 4
    A related question: here Commented Jul 24, 2017 at 15:32
  • 7
    Whether or not the frame pointer is required is dictated by the platform ABI. In general, no, it is not required, and so optimizing compilers eliminate this code. That includes Clang, so it's somewhat surprising to see that your disassembly includes it. If I remember correctly, Michael Petch investigated this a while back and determined that, on macOS, the frame pointer is typically used, so Clang does not eliminate it like it normally would on other platforms. I can't remember if it is required by the macOS ABI, or just customary. Are you, in fact, on macOS? Commented Jul 24, 2017 at 15:37
  • Also note that compiler may inline its own strlen (or even optimize to a constant) while this can not be inlined. I would expect the two inc instructions in the loop to be also quite bad. Furthermore, depending on expected string length, there are other optimizations to be had :) Commented Jul 24, 2017 at 15:38
  • 3
    @Michael Be careful making the question into something it is not. The question isn't, "how can I optimize this code further?" It is, as the title says, is the stack frame required on x86-64? Both are valid questions, of course, but only one question should be asked/answered at a time. So we don't really need the source code to determine whether a stack frame is required. Commented Jul 24, 2017 at 15:54
  • 1
    @Serge But then I have to know which function to jump back to. The return address could be stored in a processor register though, instead of the stack. But C always uses the call instruction when calling functions. Commented Jul 24, 2017 at 16:09

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

So, it seems that it just inlined the function, did it?
1

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.