jump/jump compilation strategy for stackless functions. (Using a link register manually instead of call/ret)

user_890016 0
Viewed 162

I am familiar with two basic strategies for structuring the function prologue/epilogue:

  1. "Regular" functions: Move the stack pointer to the end of the stack frame (sub rsp, n), do the actual work, then move the stack pointer back (add rsp, n) and ret. (If there are many registers used in the body, there may additionally be some pushing and popping here.)
  2. "Leaf" functions: Same as (1) but don't move the stack pointer, saving two instructions.

With strategy 2, you can't call functions inside the body, unless you move the stack pointer where it is supposed to be, which defeats the savings, which is why it's usually only used for leaf functions.

But it occurs to me that there is a third strategy one could use:

  1. "Stackless" functions: Use mov rsi, AFTER; jump FUNCTION; AFTER: for the call sequence, and in the function just jump rsi at the end.

In this method, we ignore the stack pointer completely, so we have no stack space, but for a small function that might be doable. It also requires a custom calling convention, but compilers can do that if they want to for internal functions.

Since it pairs jump with jump, it doesn't touch the return stack so the branch predictor should not be thrown off (although the indirect jump at the end might be slower than a return), and there is no overhead for the memory writes incurred by call. Additionally, stackless functions can call other stackless functions (although not too much since you eventually run out of registers in which to store the return addresses, and there is a global optimization problem in ensuring that if A calls B then they use different return registers).

My question is: why don't compilers use method (3) more? AFAICT it doesn't ever show up when looking at functions compiled by gcc or clang. Is there a reason this calling convention is not usable?

calling-convention micro-optimization x86 assembly compiler-construction
2 Answers

Here's an attempt to benchmark both options.

    .text
    .align 8
    
subroutine:
    inc %rdx
#ifdef REG_CALL
    jmp *%rsi
#else
    ret
#endif

    reps = 1000000
    .global main
    
main:
    push %rbp
    mov $reps, %ecx
    xor %edx, %edx
    .align 8
top:
    .rept 1000
#ifdef REG_CALL
    lea 0f(%rip), %rsi
    jmp subroutine
0:  
#else
    call subroutine
#endif
    .endr
    dec %ecx
    jnz top

    lea format(%rip), %rdi
    mov %rdx, %rsi
    xor %eax, %eax
    call printf
    xor %eax, %eax
    pop %rbp
    ret

    .data
format: .asciz "%ld calls done\n"

It does 1000 calls to the subroutine from varying return addresses, repeated one million times. Assemble with no options for traditional call/ret, with -DREG_CALL for your indirect jump proposal.

On an i7-8565U CPU @ 1.80GHz, traditional takes 1.6 seconds and REG_CALL takes about 3.2. So your proposal seems to be about twice as slow.

As I mentioned in comments, I suspect the indirect branch predictor can't keep track of where the jmp *%rsi is going to go.

Aside from runtime inefficiencies, Raymond Chen mentions another major disadvantage of this strategy in the comments:

Another problem is register assignment if one stackless function calls another. Not only must they use separate return address registers, their other register usages cannot conflict either. This would be practical only for small functions with few callers, at which point you may as well just inline them.

user_6349190

Conventions are there for a reason and designed so that if each function conforms, then you can call one or many functions from another and for some languages perform recursion.

You are perhaps assuming that compiler optimization is perfect and/or compilers are perfect or something. They are not and are not assumed to be. It is quite common to find missed optimizations in most normal sized projects. (gcc for example has been getting worse not better with each new major revision)

Reducing the number of function calls yourself may (or may not) improve the compiled output rather than hoping the compiler can guess what you wanted it to do.

A leaf function is by definition a leaf function the end of the branch of the tree, if it calls another function it is not a leaf function.

You certainly do not want to break the convention as then that code cannot be used/linked, it must conform or the whole system breaks down. You instead want to perhaps get more inlining happening by controlling the optimization domain. There is no valid reason for a successful compiler to intentionally make broken code, that is why they do not create unconventional functions that cannot be linked or used.

At the end of the day if this is a concern then take the compiler output and hand tune it to remove the instructions or overhead you do not like.

so

Breaking the convention means the whole tool is compromised and it will not make usable programs, that is not an option. Your only two choices are to get the code in question into the same optimization domain, or to hand tune the compiler output yourself.

and

there are at least two major toolchains that are open source, you are free to modify them and or create your own to demonstrate this multi-convention thing with some file format that communicates the convention to the linker plus some other way to communicate the convention to nested functions in some cart before the horse manner. Or perhaps the compiler generates output for each function times the combinations of all function calls within a function. Two conventions, one function calls two other functions that is 2 times 2 times 2, 8 generated implementations of that function in the object file. If a function calls 15 other functions and those functions call other functions and so on you can see one of the problems here. god forbid if you call a function in a loop. It is technically possible if you have the disk/memory space. In the long run it adds very little value but a huge amount of risk, when other, current, solutions meet somewhere in the middle with respect to value/risk.

user_160070
Related