[LLVMdev] [RFC] Coroutines

[Sanjoy Das]

Hi llvmdev!

I've been working on adding coroutines to LLVM. Mentioned below is the
implementation plan I'm following, for suggestions, flames and other
input. Using segmented stacks is a prerequisite.

The idea is to associate every coroutine with a coroutine descriptor. A
coroutine descriptor consists of four words: w0, w1, w2 and w3.

w0 always contains the _launcher_, and invoking a coroutine always
involves setting a predefined register (%eax or %rax on x86) to point to
the descriptor and calling into w0. The contents of w1, w2 and w3  are
decided by the state the coroutine is in. As of now, there are two
possibilities:

A. The coroutine has just been created:

w0 is set to __launch_coroutine, which starts the coroutine by mallocing
some initial stack space, calling into
__generic_morestack_set_initial_sp (in libgcc) and then finally calling
into the "main" function for that coroutine. Once the "main" function
returns, a cleanup routine frees the stack.

Before calling the "main" function, it also sets w0 to __continue_coroutine.

In this state:

w1 contains a pointer to the "main" function
w2 contains a pointer that is passed as an argument to the "main" function
w3 contains the initial stack size.

B. The coroutine has already been invoked once:

w0 is set to __continue_coroutine. __continue_coroutine sets the stack
pointer correctly, and jumps to where the last coroutine switch left
off. In this state:

w1 contains the IP to jump to.
w2 contains the stack pointer.
w3 is undefined.



Directly based on previous discussions on the list, I think it makes
sense to add the following intrinsics to LLVM:

// Returns the size of a coroutine descriptor.
i32 llvm.coroutine_descriptor_size()

// Creates a new coroutine, which starts off with the function
// `function' being called with the argument `baton'. For this to
// work correctly, function must be of the type `void () (i8 *)'.
// `stack_size' will be the initial stack size. `descriptor' is a
// block of memory with at least as many bytes as returned by
// llvm.coroutine_descriptor_size().

void llvm.coroutine_new(i8 *descriptor, i8 *function, i8 *baton, i32
stack_size)

// Store the state of the current coroutine in `this' and switch to
// the one described by `new'.
void llvm.coroutine_switch(i8 *this, i8 *new)

It should be possible to have the LLVM register allocator correctly
handle persisting the registers by replacing llvm.coroutine_switch with
a pseudo instruction which has every register in its Def list. This will
also have the advantage of not saving unneeded registers.

One issue is deciding a home for __launch_coroutine and
__continue_coroutine. Currently I'm coding based on these two being in a
separate library of their own; but they can be merged into compiler-rt
if required.

Thanks!

-- 
Sanjoy Das
http://playingwithpointers.com