llvm dev - Jun 2016 - [RFC] LLVM Coroutines

I think I got it. Original model (with coro.fork and two-way coro.suspend)
will work with a tiny tweak.

In the original model, I was replacing coro.suspend with br %return in original
function. The problem was coming from potential phi-nodes introduces into
return block during optimizations.

Let's make sure that there is only entry into the return block.
In the original model, ReturnBB had two entries, one from coro.fork,
another from fall-through from the delete block.

  T coro() {
    %mem = malloc(...);
    if (!coro.fork()) {
      Body Of The Coroutine
      With Suspends and All The Fun
  DeleteBB:
      free(%mem)
      coro.end()
    }
  ReturnBB:
    return some_code_creating_T();
  }

In the original model,
  coro.end is replaced with `no-op` in start, 'ret void' in clones (*)
  suspend is replaced with `br %return` in start, 'ret void' in clones

Let's tweak it. Add an i1 %fallthru parameter to coro.end. Now the behavior
is:
  in clones coro.end behaves as before: replaced with 'ret void' (*)
  in original:
    coro.end(false) => no-op (as before). (*)
    coro.end(true) => 'br %return'

Now the body of the coroutine will look like this:

T coro() {
    %mem = malloc(...);
    if (coro.fork()) {
ReturnBB:
      return some_code_creating_T();
    }
    Body Of The Coroutine
    With Suspends and All The Fun
DeleteBB:
    free(%mem)
    coro.end(true)
    UNREACHABLE
  }

Now I don't think any code that has side effects can sneak up from the
"Body of The Coroutine" into ReturnBB. So we are good, right?

Gor

-----------------
(*) There are two uses for coro.end. One is for the fallthrough point in
the delete block. Another, in unwind code responsible for cleanup in
the original function if there is an exception **BEFORE** coroutine had a
chance to suspend.

coro.end in unwind blocks is replaced with appropriate 'unwind to
caller'
instruction, cutting the rest out.

On Sun, Jun 12, 2016 at 9:31 AM, Gor Nishanov via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Let's tweak it. Add an i1 %fallthru parameter to coro.end. Now the
behavior is:
>   in clones coro.end behaves as before: replaced with 'ret void'
(*)
>   in original:
>     coro.end(false) => no-op (as before). (*)
>     coro.end(true) => 'br %return'
>
> Now the body of the coroutine will look like this:
>
> T coro() {
>     %mem = malloc(...);
>     if (coro.fork()) {
> ReturnBB:
>       return some_code_creating_T();
>     }
>     Body Of The Coroutine
>     With Suspends and All The Fun
> DeleteBB:
>     free(%mem)
>     coro.end(true)
>     UNREACHABLE
>   }
I may have missed something obvious here, but in this case doesn't the
transformed function have a path (DeleteBB -> ReturnBB) that is not
present in the original program?  This is problematic since it will
allow the optimizer to do things to the program that will be invalid
once you transform the program.  One example is that SSA construction
will be wrong:

T coro() {
    %t = alloca
    %mem = malloc(...);
    (*%t) = 10
    if (coro.fork()) {
ReturnBB:
      %val = *%t
      return some_code_creating_T(%val);
    }
    Body Of The Coroutine
    With Suspends and All The Fun
DeleteBB:
    free(%mem)
    (*%t) = 20
    coro.end(true)
    UNREACHABLE
  }


Now in the above CFG %val can be folded to 10, but in reality you need
a PHI of 10 and 20.

Generally (if I understand your idea), you have a program above whose
ultimate execution cannot be "explained" by these intrinsics executing
like normal function calls; i.e. there is a "magic" edge from DeleteBB
to ReturnBB that isn't present in the CFG.

The thought experiment relevant here is that **could** you implement
your semantics with reasonable bodies for the llvm.coro intrinsics?
It does not ultimately matter whether you do that or you do some fancy
program transformation, but assuming the program **could** have had
the semantics you wanted from the very beginning will (by principle)
prevent the optimizer from breaking you.

-- Sanjoy

Hi Sanjoy:
>> Now in the above CFG %val can be folded to 10, but in reality you need
>> a PHI of 10 and 20
Quick answer: folding %val to 10 is OK, but, I would prefer it to be
'undef'
or even catch it in the verifier as it is a programmer/frontend error.

Details are in the second half of my reply. I would like to start
with the thought experiment you suggested, as it might help to explain
the behavior a little better.
>> The thought experiment relevant here is that **could** you implement
>> your semantics with reasonable bodies for the llvm.coro intrinsics?
I can emulate **control flow** very closely with user mode thread switching
APIs like make_context, jump_context. Memory behavior not so much.

Library emulation
================
Let's build a fiber abstraction out of make_context, jump_context.

i1 fiber_fork(i8* %mem) - clones this function into a fiber
                          returns 0 - in a fiber
                          returns 1 - in a thread
                          uses %mem to store fiber context + fiber stack

i1 fiber_suspend()      - suspends current fiber, switches back to thread
                          stores the fiber context to be able to resume later

void fiber_join(i8* %mem i1 %val) - switches to fiber stack identified by %mem,
                          fiber_suspend will return %val when resumed

void fiber_end() noreturn
                        - switches back to a thread, does not remember fiber
                          context and does not touch %mem.
                          (Thus you can use this after %mem is freed)


Detail: fiber_fork(i8* %mem)
----------------------------
  * Prepares fcontext in %mem utilizing the rest of the memory for stack.
  * Saves current thread context on a current thread stack.
    (We should not store if in %mem, otherwise we won't be
     able to switch back after fiber memory is freed)
  * Sets up **current thread** context, so that when resumed it will proceed
    as if fiber_fork returned true
  * Sets up **fiber** context so that when resumed, the fiber will proceed
    as if fiber_fork returned false.
  * Clones the locals on the thread stack to a fiber stack
    (This is very approximate behavior, and won't work if we took address of
     alloca and stashed it somewhere, but let's ignore it for now as we
     are focusing on control flow)
  * Switches to fiber

Okay, let's map it to our intrinsics:

coro.fork == fiber_fork
coro.suspend == fiber_suspend
coro.end(true) == fiber_end
coro.resume = fiber_join(%mem, i1 false)
coro.destroy = fiber_join(%mem, i1 true)
coro.size == 1,000,000 (or some other big number)

Now let's walk through this example in the fiber model:

   T coro() {
       %t = alloca
       %mem = malloc(...);
       (*%t) = 10
       if (coro.fork()) { // switches to fiber at label Start
   ReturnBB:
         %val = *%t // will be 10, as fiber has its own copy
         return some_code_creating_T(%val);
       }
   Start:
       Body Of The Coroutine
       With Suspends and All The Fun
   DeleteBB:
       (*%t) = 15 ; // fine, copy of %t on a fiber stack updated
       free(%mem)
       (*%t) = 20 ; // undef: as the fiber memory is freed already
       coro.end(true) // switches back to the thread at ReturnBB
       UNREACHABLE // <== never reaches here. So we are honest with optimizer
     }


Back to the LLVM based implementation
====================================
In your example, there will be a path from the block where %t is used to
where %t is defined that crosses a suspend point. Therefore %t will be part of
the coroutine frame. So before the split, the program will be transformed into:

   coro.frame = type { int %t }

   T coro() {
       %t = alloca
       %mem = malloc(...);
       %s = (coro.frame*)coro.init(%mem)
       s->%t = 10
       if (coro.fork()) {
   ReturnBB:
         %val = 10 // const.prop as 10, OK, but really undef
         return some_code_creating_T(%val);
       }
       Body Of The Coroutine
       With Suspends and All The Fun
   DeleteBB:
       free(%mem)
       s->%t = 20 //// BOOM writing to freed memory
       coro.end(true)
       UNREACHABLE
     }

Accessing anything in the coroutine frame after coro.fork "true" is
undefined.
As by the time you get to returnBB, the coroutine frame could already
be destroyed.

Both problems can be statically detected in the Verifier.

Alternatively, in CoroEarly pass that runs at EP_EarlyAsPossible extension
point, we can replace:

         %val = *%t
             with
         %val = undef (used after coro.fork() returned true)

              and

       free(%mem)
       (*%t) = 20
            with
       @llvm.trap() ; used after frame is destroyed


--Gor