[LLVMdev] Proposal: stack/context switching within a thread

[Kenneth Uildriks]

On Mon, Apr 12, 2010 at 3:48 PM, Lacey, Mark <mark.lacey at intel.com> wrote:
> I'm very interested in seeing support for stack/context switching in LLVM, if only for prototyping language ideas. I'm particularly interested in mechanisms that would make it possible to implement full asymmetric coroutines as described in "Revisiting Coroutines" (Moura & Ierusalimschy, Feb 2009 TOPLAS). From skimming the thread and looking at the llvm-stack-switch wiki, it looks like you're headed more in the direction of symmetric coroutines.

According to the paper you linked, asymmetric coroutines "provide
two control-transfer operations: one for invoking a coroutine and one for
suspending it, the latter returning control to the coroutine invoker. While
symmetric coroutines operate at the same hierarchical level, an asymmetric
coroutine can be regarded as subordinate to its caller, the relationship between
them being somewhat similar to that between a called and a calling
routine."  The constructs proposed for LLVM are intended to support
both symmetric and asymmetric coroutines (along with fibers and other
things) - each context carries a "linked" context that represents the
invoker of the given one, and control can be transferred back to it.
The front-end can support a "coreturn" statement that does this
automatically.

>
> I've read that there is a Lua JIT based on LLVM, but haven't looked into the details of how coroutines are implemented there.
>
> In skimming through this thread I see some apparent requirements that I would hope could be avoided - e.g. the existence of mmap, any memory allocation going on "under the covers", or a requirement that a front-end do CPS conversion - it looks like later email has made this same point, so perhaps this is not being considered any longer.

Right now, I'm envisioning these more as possible strategies to allow
huge numbers of context stacks to exist in a limited address space,
not a requirement imposed by or on LLVM to do the context switching.
As far as I can tell, any conceivable strategy (other than segmented
stacks) really belongs outside of LLVM, and should be handled by a
scheduler, runtime library, or front-end.

>
> One thing I don't think I've seen mentioned so far is the interplay between swapcontext() and register allocation - I would hope a high performance implementation would exist that would only result in registers that are currently live being saved/restored at these points, not just a general save/restore of register state.

I'd like to see that too, and it's one of several things that's
convincing me that simply lowering to the C routines, even in
environments where that would work, is not really what we want to end
up doing unless we need compatibility for some reason.

One simple strategy would be to declare all registers dead at a
swapcontext.  Then *only* live registers get spilled  to the context
stack before and restored afterward.