[llvm-dev] [RFC] LLVM Coroutines

[Sanjoy Das via llvm-dev]

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