> TCO makes a lot of sense for interpreters and state machines. The reason that performant impl...

10000truths • yesterday at 8:47 PM • 1 reply • view on HN

> TCO makes a lot of sense for interpreters and state machines.

The reason that performant implementations prefer TCO is because the only reliable knob that clang and gcc provide to control which locals are spilled to stack vs. kept in registers is via calling convention constraints. One could accomplish the same performance without TCO'd recursion if there existed an annotation for local variables designating them as spill/no-spill. But that doesn't exist in clang or gcc - the "register" keyword in the C standard was supposed to be for exactly that, but it's ignored in both compilers.

Replies

sparkie • today at 12:35 AM

That's not entirely true, but it's a valid reason to prefer using musttail.

`register` is a hint if you don't specify which register you want to use - however, if you specify the register it will clobber it.

    noinline void bar() 
    {
        register void *parent __asm__("r10");
        ...
    }

You can also use GCCs extended asm syntax to clobber a register for specific portions of code - such as the start of a function where you expect a register to have been given a value from the caller just before the call. Use `volatile` to prevent the compiler from making certain assumptions that might remove or reorder the instruction - as long as it is at the top it should execute immediately after the function prelude and before any of the function body.

    noinline void bar() 
    {
        void *volatile parent;
        // set parent = %r10 before anything else.
        asm volatile ("mov{q}\t{%%r10, %0|%0, r10}" : "=r"(parent) : : "r10");
        ...
    }

Note that this will probably be less efficient than the former example, but maybe useful where you want to limit the scope in which `r10` is clobbered.

In both cases you would set the register immediately before making the call, again using `volatile`. Since `r10` is not used by a typical call in SYSV - it's the static chain pointer in the SYSV convention, but otherwise usable as a GP register, a call will not overwrite it.

    void foo()
    {
        struct foo_frame {
            int x;
        } locals = { 
            .x = 999
        };

        // Set `r10` to our function's local frame
        asm volatile("mov{q}\t{%0, %%r10|r10, %0}" : : "r"(&locals) : "r10")
        
        bar();
    }

That's pretty ugly but we can write a few macros to implement it more tersely - we can use this to have efficient closures in C without requiring an executable stack. (There's also `__builtin_call_with_static_chain`, but I've found it more troublesome to use than the manual way).

Demo: https://godbolt.org/z/cM9d8e1r5

For other registers which are part of the regular calling convention, we might be able to clobber them if they wouldn't normally be used for the call. Eg, if our function takes regular 2 arguments, they would be in `rdi` and `rsi` - so we could use `rdx`, `rcx`, `r8`, `r9` like the above, but if our function took 6 or more regular arguments we wouldn't be able to use any of these in this way. If we wanted a custom calling convention we could just make all functions have zero-arguments and perform all of the setting and capturing ourself - which gives us more control than using [[musttail]] - though less portable, and may prevent optimizations the compiler could otherwise make.

alt Hacker News

Replies