llvm dev - Apr 2010 - [LLVMdev] Proposal: stack/context switching within a thread

On Mon, Apr 12, 2010 at 6:15 AM, Kenneth Uildriks <kennethuil at
gmail.com> wrote:
> I created a wiki at http://code.google.com/p/llvm-stack-switch/
>
> Right now I just copied and formatted the document as-is... I'll go
> back over it with your comments in mind soon.  One more question,
> which you can answer here or there:
>
>> Point 4 is a bit confusing. Normally, it's fine for a thread to
share
>> some of its stack space with another thread, but your wording seems to
>> prohibit that.
>
> Really?  How does that work?
void thread1() {
  Foo shared_var;
  queue.send(&shared_var);
  int result = otherqueue.recv();
  return;
}

void thread2() {
  Foo* shared_var = queue.recv();
  otherqueue.send(work_on(shared_var));
}

is legal with posix threads. It's just illegal to return out of a
function while its stack space is used by another thread. I've seen
this used inside a condition variable implementation, among other
places.
>> I'll forward your next draft back to the stackless folks, unless
you
>> want to pick up the thread with them.
>
> If you're willing to be the go-between, I really appreciate it..  I
> don't think I have the time to really get involved with Stackless
> Python, especially as I would have to learn regular Python first.
Sure.

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.

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.

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.

_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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.