[coroutines] Part 2 of N: Adding Coroutine Intrinsics

[GorNishanov]

Summary

This is the second patch in the coroutine series. It adds coroutine intrinsics and updates intrinsic cost in TargetTransformInfoImpl.h.

Documentation and overview is here: https://reviews.llvm.org/D22603

Upstreaming sequence (rough plan)

1. Add documentation.
2. Add coroutine intrinsics. <= we are here
3. Add empty coroutine passes.
4. Add coroutine devirtualization + tests.
5. Add CGSCC restart trigger + tests.
6. Add coroutine heap elision + tests.
7. Add the rest of the logic (split into more patches)

[majnemer]

include/llvm/IR/Intrinsics.td

606–607

What happens if there are two calls to llvm.coro.begin in a function?

609

I don't know if IntrNoMem is right here but NoCapture<0> is probably fine.

618–620

How is coro.param sensitive to non-parameter stores?

627–629

NoMem seems wrong, what is your rationale?
I think you can nocapture the pointer parameter.

633–634

Is it possible for optimizations to come across this intrinsic. If so, what semantics does it have?

[GorNishanov]

include/llvm/IR/Intrinsics.td

606–607

TLDR:

coro.begin(*,*,*, null) - must have exactly one, broken IR otherwise
coro.begin(*,*,*, not-null) - can have as many or as little as inliner wants

Longer explanation:

The last argument of coro.begin is null when coming out of the frontend. Later, CoroSplit pass sets it to a pointer to a constant array containing pointers to outlined parts of the coroutine. Let's call a coro.begin with null "pre-slit coro.begin", and the one with a pointer to const array, "post-split coro.begin".

Coming out of the frontend, a coroutine has exactly one coro.begin. (Verifier can check for that). Later inliner can inline calls to other coroutines and it may bring more coro.begins into a function, but, those, will be always post-split, since CoroSplit pass runs together with the Inliner in the same CGPassManager.

CoroSplit pass only cares about pre-split coro.begin and there is exactly one. Other coro.begins are there for the benefit of CoroElide pass that devirtualizes and elides heap allocations where possible.

All intrinsics that stay in the coroutine after CoroSplit pass (coro.alloc and coro.free) are linked to coro.begin, so CoroElide pass knows which coroutine they belong to.

609

Ack on NoCapture<0>.
With respect to IntrNoMem my thinking was:

coro.free(%hdl) can be lowered in one of three ways:

1. null - if CoroElide pass elides dynamic allocations
2. %hdl - if coroutine handle points to the beginning of the memory block
3. gep on %hdl - that adjusts the pointer to point to the beginning of the memory block.

Wait, you are right, gep may not be a constant gep, if some of the allocas in the coroutine have alignment requirements that exceed the alignment guarantees provided by the allocation function (second parameter to coro.begin), then, indeed, coro.free would have to read some adjustment value from the memory pointed by handle to do the correct adjustment.

Okay, then,

[IntrReadMem, NoCapture<0>]

it is.

618–620

To double check:

You are asking why [IntrReadMem] and not [IntrNoMem]?

I think it is safe to mark it [IntrNoMem].
It is always lowered to a Boolean constant, and the only purpose for the first and second argument is to tie those two allocas together, in case, I want to elide parameter copy and need to RAUW one with another.

627–629

Ack on NoCapture<0>.

It is NoReadMem, since it is always lowered to a constant gep.

633–634

The life of coro.subfn.addr looks like this:

CoroEarly replaces:

call i8* llvm.coro.resume(i8* %Arg)

with

%0 = call i8* llvm.coro.subfn.addr(i8* %Arg, i8 0)
%1 = bitcast i8* %0 to void(i8*)*
call fastcc void %1 (i8* %Arg)

CoroElide may replace coro.subfn.addr with a f.resume function pointer, so it will be constant folded to:

call fastcc void @f.resume (i8* %Arg)

If CoroElide wasn't able to do devirtualize it, it will stay intact until CoroCleanup pass run at EP_OptimizerLast. CoroCleanup will replace it with: gep + load to get the address of the appropriate resume function at runtime.

0 - f.resume
1 - f.destroy

P.S.

Frontend does not emit coro.subfn.addr directly, as we would like to hide the details of the calling convention for the coroutine sub-functions.

[majnemer]

include/llvm/IR/Intrinsics.td

606–607

Can't earlier transforms clone a block containing a coro.begin call?

609

SGTM

618–620

Cool, IntrNoMem sounds good to me.

633–634

Ah, ok.

[GorNishanov]

Relaxed memory access attributes on coro.begin, coro.free, coro.done and coro.subfn.addr intrinsics.

include/llvm/IR/Intrinsics.td

606–607

I just found a very useful attribute. NoDuplicate.
CoroEarly can mark the coro.begin CallSite as NoDuplicate.
CoroSplit will remove that attribute, so PostSplit coro.begins could be duplicated after split.

Alternatively, we can break coro.begin into two distinct intrinsics:

coro.begin (with NoDuplicate always, and only three parameters, no last parameters)
coro.begin.postsplit (without NoDuplicate attribute and without Promise parameter)

[GorNishanov]

Documentation updated to state that coro.alloc is required to have heap allocation elision.
Intrinsics attributes tweaked:
coro.alloc is now [], (when it was IntrNoMem, multiple coro.allocs belonging to different coroutines were coalesced into one, breaking the semantics)
coro.begin is now capturing the promise parameter, otherwise, GVN won't recognize operations that may write to the promise.

[majnemer]

In D22659#495738, @GorNishanov wrote:

coro.begin is now capturing the promise parameter, otherwise, GVN won't recognize operations that may write to the promise.

coro.begin semantically stores the promise parameter somewhere? The semantics portion of the coro.begin intrinsic doesn't describe what happens when the promise parameter is provided.

include/llvm/IR/Intrinsics.td

605

Each coro.alloc is neither a distinct alloca or null right? I think we can mark the function return with noalias.

[GorNishanov]

In D22659#495774, @majnemer wrote:

In D22659#495738, @GorNishanov wrote:

coro.begin is now capturing the promise parameter, otherwise, GVN won't recognize operations that may write to the promise.

coro.begin semantically stores the promise parameter somewhere? The semantics portion of the coro.begin intrinsic doesn't describe what happens when the promise parameter is provided.

coro.begin does not do anything with the promise on lowering, apart from letting the promise alloca "escape" due to taking it as an argument.
This property comes from the semantic of the promise itself. Promise alloca is directly accessible from outside of the coroutine.

The issue I ran into was that in expected.cpp: https://github.com/GorNishanov/clang/blob/coro/test/Coroutines/expected.cpp, await_suspend stores the error value in the promise.

void await_suspend(std::coroutine_handle<promise_type> h) { 
  h.promise().data.error =std::move(data.error); 
  h.destroy(); 
}

To llvm it looks like:

%4 = call noalias nonnull i8* @llvm.coro.begin(i8* nonnull %3, i32 0, i8* %promise, i8* null)
...
; inlined from call await_suspend(%awaiter_this, %4)
%error4.i = getelementptr inbounds i8, i8* %4, i32 16
%5 = bitcast i8* %error4.i to i32*
store i32 42, i32* %5, align 4, !tbaa !15 ; stores into promise, 
                                          ; GVN did not know that promise escaped due to NoCapture in coro.begin
                                          ; and thought in the block below that the error value is undef
...
AfterCoroEnd:                                     ; Copy expected<int,int> back to result of the function
  %val.i = getelementptr inbounds %struct.expected, %struct.expected* %agg.result, i32 0, i32 0, i32 0
  %val4.i = getelementptr inbounds %"struct.expected<int, int>::promise_type", %"struct.expected<int, int>::promise_type"* %promise, i32 0, i32 0, i32 0
  %9 = load i32, i32* %val4.i, align 4, !tbaa !14
  store i32 %9, i32* %val.i, align 4, !tbaa !1
  %error.i = getelementptr inbounds %struct.expected, %struct.expected* %agg.result, i32 0, i32 0, i32 1
  %error6.i = getelementptr inbounds %"struct.expected<int, int>::promise_type", %"struct.expected<int, int>::promise_type"* %promise, i32 0, i32 0, i32 1
  %10 = load i32, i32* %error6.i, align 4, !tbaa !14
  store i32 %10, i32* %error.i, align 4, !tbaa !6
  ret void
}

include/llvm/IR/Intrinsics.td

605

I am not sure I can do this with within an Intrinsics.td . NoAlias is not defined there.
Currently, I am adding NoAlias and NotNull attributes to the coro.begin calls in CoroEarly pass.

[GorNishanov]

diff reuploaded with -U999999

[GorNishanov]

s/code-block:: C++/code-block:: c++

to fix syntax highlighting on Linux

[GorNishanov]

NoCapture<0> is stripped from coro.begin
NoCapture<0> and NoCapture<1> is stripped from coro.param

[majnemer]

LGTM

docs/Coroutines.rst

 =====================
 
 Coroutine Representation
 ------------------------
 
 Let's look at an example of an LLVM coroutine with the behavior sketched
 by the following pseudo-code.
 
-.. code-block:: C++
+.. code-block:: c++
 
   void *f(int n) {
      for(;;) {
        print(n++);
        <suspend> // returns a coroutine handle on first suspend
      }     
   } 
 

  
 A particular coroutine usage pattern, which is illustrated by the `main` 
 function in the overview section, where a coroutine is created, manipulated and 
 destroyed by the same calling function, is common for coroutines implementing
 RAII idiom and is suitable for allocation elision optimization which avoid 
 dynamic allocation by storing the coroutine frame as a static `alloca` in its 
 caller.
 
-If a coroutine uses allocation and deallocation functions that are known to
-LLVM, unused calls to `malloc` and calls to `free` with `null` argument will be
-removed as dead code. However, if custom allocation functions are used, the
-`coro.alloc` and `coro.free` intrinsics can be used to enable removal of custom
-allocation and deallocation code when coroutine does not require dynamic
-allocation of the coroutine frame.
-
 In the entry block, we will call `coro.alloc`_ intrinsic that will return `null`
-when dynamic allocation is required, and non-null otherwise:
+when dynamic allocation is required, and an address of an alloca on the caller's
+frame where coroutine frame can be stored if dynamic allocation is elided.
 
 .. code-block:: llvm
 
   entry:
     %elide = call i8* @llvm.coro.alloc()
     %need.dyn.alloc = icmp ne i8* %elide, null
     br i1 %need.dyn.alloc, label %coro.begin, label %dyn.alloc
   dyn.alloc:
cleanup:
     br i1 %need.dyn.free, label %dyn.free, label %if.end
   dyn.free:
     call void @CustomFree(i8* %mem)
     br label %if.end
   if.end:
     ...
 
 With allocations and deallocations represented as described as above, after
-coroutine heap allocation elision optimization, the resulting main will end up 
-looking just like it was when we used `malloc` and `free`:
+coroutine heap allocation elision optimization, the resulting main will be:
 
 .. code-block:: llvm
 
   define i32 @main() {
   entry:
     call void @print(i32 4)
     call void @print(i32 5)
     call void @print(i32 6)
     ret i32 0
   }
 
 Multiple Suspend Points
 -----------------------
 
 Let's consider the coroutine that has more than one suspend point:
 
-.. code-block:: C++
+.. code-block:: c++
 
   void *f(int n) {
      for(;;) {
        print(n++);
        <suspend>
        print(-n);
        <suspend>
      }

 store the current value produced by a coroutine.
 
 .. code-block:: text
 
   define i8* @f(i32 %n) {
   entry:
     %promise = alloca i32
     %pv = bitcast i32* %promise to i8*
+    %elide = call i8* @llvm.coro.alloc()
+    %need.dyn.alloc = icmp ne i8* %elide, null
+    br i1 %need.dyn.alloc, label %coro.begin, label %dyn.alloc
+  dyn.alloc:
     %size = call i32 @llvm.coro.size.i32()
     %alloc = call i8* @malloc(i32 %size)
-    %hdl = call noalias i8* @llvm.coro.begin(i8* %alloc, i32 0, i8* %pv, i8* null)
+    br label %coro.begin
+  coro.begin:
+    %phi = phi i8* [ %elide, %entry ], [ %alloc, %dyn.alloc ]
+    %hdl = call noalias i8* @llvm.coro.begin(i8* %phi, i32 0, i8* %pv, i8* null)
     br label %loop
   loop:
-    %n.val = phi i32 [ %n, %entry ], [ %inc, %loop ]
+    %n.val = phi i32 [ %n, %coro.begin ], [ %inc, %loop ]
     %inc = add nsw i32 %n.val, 1
     store i32 %n.val, i32* %promise
     %0 = call i8 @llvm.coro.suspend(token none, i1 false)
     switch i8 %0, label %suspend [i8 0, label %loop
                                   i8 1, label %cleanup]
   cleanup:
     %mem = call i8* @llvm.coro.free(i8* %hdl)
     call void @free(i8* %mem)
entry:
     call void @print(i32 %val1)
     call void @llvm.coro.resume(i8* %hdl)
     %val2 = load i32, i32* %promise.addr
     call void @print(i32 %val2)
     call void @llvm.coro.destroy(i8* %hdl)
     ret i32 0
   }
 
-After example in this section is compiled, result of the compilation will 
-exactly like the result of the very first example:
+After example in this section is compiled, result of the compilation will be:
 
 .. code-block:: llvm
 
   define i32 @main() {
   entry:
     tail call void @print(i32 4)
     tail call void @print(i32 5)
     tail call void @print(i32 6)
void* coroutine(int n) {
     for (int i = 0; i < n; ++i) {
       current_value = i; <SUSPEND>; // corresponds to "yield i"
     }
     <SUSPEND final=true> // injected final suspend point
   }
 
 and python iterator `__next__` would look like:
 
-.. code-block:: C++
+.. code-block:: c++
 
   int __next__(void* hdl) {
     coro.resume(hdl);
     if (coro.done(hdl)) throw StopIteration();
     return *(int*)coro.promise(hdl, 4, false);
   }
 
 Intrinsics

 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 ::
 
   declare i8* @llvm.coro.begin(i8* <mem>, i32 <align>, i8* <promise>, i8* <fnaddr>)
 
 Overview:
 """""""""
 
-The '``llvm.coro.begin``' intrinsic returns an address of the 
-coroutine frame.
+The '``llvm.coro.begin``' intrinsic returns an address of the coroutine frame.
 
 Arguments:
 """"""""""
 
-The first argument is a pointer to a block of memory in which coroutine frame
-may use if memory for the coroutine frame needs to be allocated dynamically. 
+The first argument is a pointer to a block of memory where coroutine frame
+will be stored.
 
 The second argument provides information on the alignment of the memory returned 
 by the allocation function and given to `coro.begin` by the first argument. If 
 this argument is 0, the memory is assumed to be aligned to 2 * sizeof(i8*).
 This argument only accepts constants.
 
 The third argument, if not `null`, designates a particular alloca instruction to
 be a `coroutine promise`_.
 
 The fourth argument is `null` before coroutine is split, and later is replaced 
 to point to a private global constant array containing function pointers to 
 outlined resume and destroy parts of the coroutine.
 
 Semantics:
 """"""""""
 
 Depending on the alignment requirements of the objects in the coroutine frame
 and/or on the codegen compactness reasons the pointer returned from `coro.begin` 
 may be at offset to the `%mem` argument. (This could be beneficial if 
 instructions that express relative access to data can be more compactly encoded 
 with small positive and negative offsets).
 
-Frontend should emit exactly one `coro.begin` intrinsic per coroutine.
+A frontend should emit exactly one `coro.begin` intrinsic per coroutine.
 
 .. _coro.free:
 
 'llvm.coro.free' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 ::
 
   declare i8* @llvm.coro.free(i8* <frame>)

 
 None
 
 Semantics:
 """"""""""
 
 If the coroutine is eligible for heap elision, this intrinsic is lowered to an 
 alloca storing the coroutine frame. Otherwise, it is lowered to constant `null`.
-This intrinsic only needs to be used if a custom allocation function is used
-(i.e. a function not recognized by LLVM as a memory allocation function) and the
-language rules allow for custom allocation / deallocation to be elided when not
-needed.
+
+A frontend should emit at most one `coro.alloc` intrinsic per coroutine.
 
 Example:
 """"""""
 
 .. code-block:: llvm
 
   entry:
     %elide = call i8* @llvm.coro.alloc()

 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 ::
 
   declare i1 @llvm.coro.param(i8* <original>, i8* <copy>)
 
 Overview:
 """""""""
 
-The '``llvm.coro.param``' is used by the frontend to mark up the code used to
+The '``llvm.coro.param``' is used by a frontend to mark up the code used to
 construct and destruct copies of the parameters. If the optimizer discovers that
 a particular parameter copy is not used after any suspends, it can remove the
 construction and destruction of the copy by replacing corresponding coro.param
 with `i1 false` and replacing any use of the `copy` with the `original`.
 
 Arguments:
 """"""""""
 
 The first argument points to an `alloca` storing the value of a parameter to a 
 coroutine. 
 
 The second argument points to an `alloca` storing the value of the copy of that
 parameter.
 
 Semantics:
 """"""""""
 
 The optimizer is free to always replace this intrinsic with `i1 true`.
 
 The optimizer is also allowed to replace it with `i1 false` provided that the 
 parameter copy is only used prior to control flow reaching any of the suspend
 points. The code that would be DCE'd if the `coro.param` is replaced with 
 `i1 false` is not considered to be a use of the parameter copy.
 
-The frontend can emit this intrinsic if its language rules allow for this 
+A frontend can emit this intrinsic if its language rules allow for this 
 optimization.
 
 Example:
 """"""""
 Consider the following example. A coroutine takes two parameters `a` and `b`
 that has a destructor and a move constructor.
 
-.. code-block:: C++
+.. code-block:: c++
 
   struct A { ~A(); A(A&&); bool foo(); void bar(); };
 
   task<int> f(A a, A b) {
     if (a.foo())
       return 42;
 
     a.bar();

 
 CoroCleanup
 -----------
 This pass runs late to lower all coroutine related intrinsics not replaced by
 earlier passes.
 
 Upstreaming sequence (rough plan)
 =================================
-#. Add documentation. <= we are here
-#. Add coroutine intrinsics.
+#. Add documentation.
+#. Add coroutine intrinsics.  <= we are here
 #. Add empty coroutine passes.
 #. Add coroutine devirtualization + tests.
 #. Add CGSCC restart trigger + tests.
 #. Add coroutine heap elision + tests.
 #. Add custom allocation heap elision + tests.
 #. Add coroutine splitting logic + tests.
 #. Add simple coroutine frame builder + tests.
 #. Add the rest of the logic + tests. (Maybe split further as needed).

include/llvm/Analysis/TargetTransformInfoImpl.h

unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
     case Intrinsic::invariant_end:
     case Intrinsic::lifetime_start:
     case Intrinsic::lifetime_end:
     case Intrinsic::objectsize:
     case Intrinsic::ptr_annotation:
     case Intrinsic::var_annotation:
     case Intrinsic::experimental_gc_result:
     case Intrinsic::experimental_gc_relocate:
+    case Intrinsic::coro_alloc:
+    case Intrinsic::coro_begin:
+    case Intrinsic::coro_free:
+    case Intrinsic::coro_end:
+    case Intrinsic::coro_frame:
+    case Intrinsic::coro_size:
+    case Intrinsic::coro_suspend:
+    case Intrinsic::coro_param:
+    case Intrinsic::coro_subfn_addr:
       // These intrinsics don't actually represent code after lowering.
       return TTI::TCC_Free;
     }
   }
 
   bool hasBranchDivergence() { return false; }
 
   bool isSourceOfDivergence(const Value *V) { return false; }

include/llvm/IR/Intrinsics.td

def int_experimental_gc_statepoint : Intrinsic<[llvm_token_ty],
                                 [Throws]>;
 
 def int_experimental_gc_result   : Intrinsic<[llvm_any_ty], [llvm_token_ty],
                                              [IntrReadMem]>;
 def int_experimental_gc_relocate : Intrinsic<[llvm_any_ty],
                                 [llvm_token_ty, llvm_i32_ty, llvm_i32_ty],
                                 [IntrReadMem]>;
 
-//===-------------------------- Other Intrinsics --------------------------===//
+//===------------------------ Coroutine Intrinsics ---------------===//
+// These are documented in docs/Coroutines.rst
+
+// Coroutine Structure Intrinsics.
+
+def int_coro_alloc : Intrinsic<[llvm_ptr_ty], [], []>;
+def int_coro_begin : Intrinsic<[llvm_ptr_ty], [llvm_ptr_ty, llvm_i32_ty,
+                                llvm_ptr_ty, llvm_ptr_ty],
+                               [WriteOnly<0>, ReadNone<2>, ReadOnly<3>,
+                                NoCapture<0>, NoCapture<3>]>;
+
+def int_coro_free : Intrinsic<[llvm_ptr_ty], [llvm_ptr_ty],
+                              [IntrArgMemOnly, ReadOnly<0>, NoCapture<0>]>;
+def int_coro_end : Intrinsic<[], [llvm_ptr_ty, llvm_i1_ty], []>;
+
+def int_coro_frame : Intrinsic<[llvm_ptr_ty], [], [IntrNoMem]>;
+def int_coro_size : Intrinsic<[llvm_anyint_ty], [], [IntrNoMem]>;
+
+def int_coro_save : Intrinsic<[llvm_token_ty], [llvm_ptr_ty], []>;
+def int_coro_suspend : Intrinsic<[llvm_i8_ty], [llvm_token_ty, llvm_i1_ty], []>;
+
+def int_coro_param : Intrinsic<[llvm_i1_ty], [llvm_ptr_ty, llvm_ptr_ty],
+                               [IntrNoMem, ReadNone<0>, NoCapture<0>,
+                                ReadNone<1>, NoCapture<1>]>;
+
+// Coroutine Manipulation Intrinsics.
+
+def int_coro_resume : Intrinsic<[], [llvm_ptr_ty], [Throws]>;
+def int_coro_destroy : Intrinsic<[], [llvm_ptr_ty], [Throws]>;
+def int_coro_done : Intrinsic<[llvm_i1_ty], [llvm_ptr_ty],
+                              [IntrArgMemOnly, ReadOnly<0>, NoCapture<0>]>;
+def int_coro_promise : Intrinsic<[llvm_ptr_ty],
+                                 [llvm_ptr_ty, llvm_i32_ty, llvm_i1_ty],
+                                 [IntrNoMem, NoCapture<0>]>;
+
+// Coroutine Lowering Intrinsics. Used internally by coroutine passes.
+
+def int_coro_subfn_addr : Intrinsic<[llvm_ptr_ty], [llvm_ptr_ty, llvm_i8_ty],
+                                    [IntrArgMemOnly, ReadOnly<0>,NoCapture<0>]>;
+
+///===-------------------------- Other Intrinsics --------------------------===//
 //
 def int_flt_rounds : Intrinsic<[llvm_i32_ty]>,
                      GCCBuiltin<"__builtin_flt_rounds">;
 def int_trap : Intrinsic<[], [], [IntrNoReturn]>,
                GCCBuiltin<"__builtin_trap">;
 def int_debugtrap : Intrinsic<[]>,
                     GCCBuiltin<"__builtin_debugtrap">;