Unwinding frame but do not return in C

Question

My programming language compiles to C, I want to implement tail recursion optimization. The question here is how to pass control to another function without "returning" from the current function.

It is quite easy if the control is passed to the same function:

void f() {
    __begin:
    do something here...
    goto __begin; // "call" itself
}

As you can see there is no return value and no parameters, those are passed in a separate stack adressed by a global variable.

Another option is to use inline assembly:

#ifdef __clang__
    #define tail_call(func_name) asm("jmp " func_name " + 8");
#else
    #define tail_call(func_name) asm("jmp " func_name " + 4");
#endif

void f() {
    __begin:
    do something here...
    tail_call(f); // "call" itself
}

This is similar to goto but as goto passes control to the first statement in a function, skipping the "entry code" generated by a compiler, jmp is different, it's argument is a function pointer, and you need to add 4 or 8 bytes to skip the entry code.

The both above will work but only if the callee and the caller use the same amount of stack for local variables which is allocated by the entry code of the callee.

I was thinking to do leave manually with inline assembly, then replace the return address on the stack, then do a legal function call like f(). But my attempts all crashed. You need to modify BP and SP somehow.

So again, how to implement this for x64? (Again, assuming functions have no arguments and return void). Portable way without inline assembly is better, but assembly is accepted. Maybe longjump can be used?

Maybe you can even push the callee address on the stack, replacing the original return address and just ret?

Answer 1

Do not try to do this yourself. A good C compiler can perform tail-call elimination in many cases and will do so. In contrast, a hack using inline assembly has a good chance of going wrong in a way that is difficult to debug.

For example, see this snippet on godbolt.org. To duplicate it here:

The C code I used was:

int foo(int n, int o)
{
    if (n == 0) return o;
    puts("***\n");
    return foo(n - 1, o + 1);
}

This compiles to:

.LC0:
  .string "***\n"
foo:
  test edi, edi
  je .L4
  push r12
  mov r12d, edi
  push rbp
  mov ebp, esi
  push rbx
  mov ebx, edi
.L3:
  mov edi, OFFSET FLAT:.LC0
  call puts
  sub ebx, 1
  jne .L3
  lea eax, [r12+rbp]
  pop rbx
  pop rbp
  pop r12
  ret
.L4:
  mov eax, esi
  ret

Notice that the tail call has been eliminated. The only call is to puts.

Answer 2

Since you don't need arguments and return values, how about combining all function into one and use labels instead of function names?

f:
    __begin:
    ...
    CALL(h); // a macro implementing traditional call
    ...
    if (condition_ret)
       RETURN; // a macro implementing traditional return
    ...
    goto g; // tail recurse to g

The tricky part here is RETURN and CALL macros. To return you should keep yet another stack, a stack of setjump buffers, so when you return you call longjump(ret_stack.pop()), and when you call you do ret_stack.push(setjump(f)). This is poetical rendition ofc, you'll need to fill out the details.

gcc can offer some optimization here with computed goto, they are more lightweight than longjump. Also people who write vms have similar problems, and seemingly have asm-based solutions for those even on MSVC, see example here.

And finally such approach even if it saves memory, may be confusing to compiler, so can cause performance anomalies. You probably better off generating for some portable assembler-like language, llvm maybe? Not sure, should be something that has computed goto.

Answer 3

The venerable approach to this problem is to use trampolines. Essentially, every compiled function returns a function pointer (and maybe an arg count). The top level is a tight loop that, starting with your main, simply calls the returned function pointer ad infinitum. You could use a function that longjmps to escape the loop, i.e., to terminate the progam.

See this SO Q&A. Or Google "recursion tco trampoline."

For another approach, see Cheney on the MTA, where the stack just grows until it's full, which triggers a GC. This works once the program is converted to continuation passing style (CPS) since in that style, functions never return; so, after the GC, the stack is all garbage, and can be reused.

Answer 4

I will suggest a hack. The x86 call instruction, which is used by the compiler to translate your function calls, pushes the return address on the stack and then performs a jump.

What you can do is a bit of a stack manipulation, using some inline assembly and possibly some macros to save yourself a bit of headache. You basically have to overwrite the return address on the stack, which you can do immediately in the function called. You can have a wrapper function which overwrites the return address and calls your function - the control flow will then return to the wrapper which then moves to wherever you pointed it to.