# Suspendable Functions (`async`, `async*` and `sync*`)

This document describes the implementation of _suspendable_ functions (functions with `async`,
`async*` or `sync*` modifier) in Dart VM. The execution of such functions can be suspended in
the middle at `await`/`yield`/`yield*` and resumed afterwards.

When suspending a function, its local execution state (local variables and temporaries) is saved
and the control is returned to the caller of the suspended function.
When resuming a function, its local execution state is restored and execution continues within
the suspendable function from the point where it was suspended.

In order to minimize code size, the implementation is built using a variety of _stubs_ - reusable
snippets of machine code generated by the VM/AOT.
The high-level Dart logic used to implement suspendable functions (such as managing
Futures/Streams/Iterators) is factored into helper Dart methods in core library.

The rest of the document is organized as follows: first, general mechanisms for implementation of
suspendable functions are described.
After that, `async`, `async*` and `sync*` implementations are outlined using the general
mechanisms introduced before.

# Building blocks common to all suspendable functions

## SuspendState objects

SuspendState objects are allocated on the heap and encapsulate the saved state of a suspended
function. When suspending a function, its local frame (including local variables, spill slots
and expression stack) is copied from the stack to a SuspendState object on the heap.
When resuming a function, the frame is recreated and copied back from the SuspendState object
into the stack.

SuspendState objects have variable size and keep frame in the "payload" following a few fixed
fields.

In addition to a stack frame, SuspendState records a PC in the code of the suspended function
where execution was suspended and can be resumed.
The PC is also used by GC to find a stack map and scan through the pointers in the copied frame.

SuspendState object also holds data and callbacks specific to a particular kind of suspendable
function.

SuspendState object is allocated during the first suspension and can be reused for the subsequent
suspensions of the same function.

For the declaration of SuspendState see [object.h](https://github.com/dart-lang/sdk/blob/main/runtime/vm/object.h#:~:text=class%20SuspendState),
UntaggedSuspendState is declared in [raw_object.h](https://github.com/dart-lang/sdk/blob/main/runtime/vm/raw_object.h#:~:text=class%20UntaggedSuspendState).

There is also a corresponding Dart class `_SuspendState`, declared in [async_patch.dart](https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/async_patch.dart#:~:text=class%20_SuspendState).
It contains Dart methods which are used to customize implementation for a particular kind of
suspendable function.

## Frame of a suspendable function

Suspendable functions are never inlined into other functions, so their local state is not mixed
with the state of their callers (but other functions may be inlined into them).

In order to have a single contiguous region of memory to copy during suspend/resume, parameters of
suspendable functions are always copied into the local frame in the function prologue (see uses of
`Function::MakesCopyOfParameters()` predicate).

In order to keep and reuse SuspendState object, each suspendable function has an artificial local
variable `:suspend_state` (see uses of `ParsedFunction::suspend_state_var()`), which is always
allocated at the fixed offset in frame. It occupies the first local variable slot
(`SuspendState::kSuspendStateVarIndex`) in case of unoptimized code or the first spill slot
in case of optimized code (see `FlowGraphAllocator::AllocateSpillSlotForSuspendState`).
The fixed location helps to find this variable in various stubs and runtime.

## Prologue and InitSuspendableFunction stub

At the very beginning of a suspendable function `null` is stored into `:suspend_state` variable.
This guarantees that `:suspend_state` variable can be accessed any time by GC and exception
handling.

After checking bounds of type arguments and types of arguments, suspendable functions call
InitSuspendableFunction stub.

InitSuspendableFunction stub does the following:

- It calls a static generic Dart method specific to a particular kind of suspendable function.
  The argument of the stub is passed as type arguments to that method.
  Dart method performs initialization specific to a particular kind of suspendable function
  (for example, it creates `_Future<T>()` for async functions).
  It returns the instance which is used as a function-specific data.

- Stub puts the function-specific data to `:suspend_state` variable, where it can be found by
  Suspend or Return stubs later.

## Suspend stub

Suspend stub is called from a suspendable function when its execution should be suspended.

Suspend stub does the following:

- It inspects `:suspend_state` variable and checks if it contains an instance of SuspendState.
  If it doesn't, then stub allocates a new instance with a payload sufficient to hold a frame of
  the suspendable function. The newly allocated SuspendState is stored into `:suspend_state`
  variable, and previous value of `:suspend_state` (coming from InitSuspendableFunction stub) is
  saved to `SuspendState.function_data`.

- In JIT mode, size of the frame may vary over time - expression stack depth varies during
  execution of unoptimized code and frame size may change during deoptimization and OSR.
  In AOT mode size of the stack frame stays the same.
  So, if stub finds an existing SuspendState object in JIT mode, it also checks if its frame
  payload has a sufficient size to hold a frame of the suspendable function. If it is not
  large enough, suspend stub calls `AllocateSuspendState` runtime entry to allocate a larger
  SuspendState object. The same runtime entry is called for slow path when allocating
  SuspendState for the first time.

- The return address from Suspend stub to the suspendable function is saved to `SuspendState.pc`.
  It will be used to resume execution later.

- The contents of the stack frame of the suspendable function between FP and SP is copied into
  SuspendState.

- Write barrier: if SuspendState object resides in the old generation, then
  EnsureRememberedAndMarkingDeferred runtime entry is called.

- If implementation of particular kind of suspendable function uses a customized Dart method
  for the suspension, then that method is called.
  Suspend stub supports passing one argument to the customization method.
  The result of the method is returned back to the caller of the suspendable function - it's
  the result of the suspendable function.
  If such method is not used, then Suspend stub returns its argument (so suspendable function
  could customize its return value).

- On architectures other than x64/ia32, the frame of the suspendable function is removed and
  stub returns directly to the caller of the suspendable function.
  On x64/ia32, in order to maintain call/return balance and avoid performance penalty,
  Suspend stub returns to the suspendable function which immediately returns to its caller.

For more details see `StubCodeCompiler::GenerateSuspendStub` in [stub_code_compiler.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/compiler/stub_code_compiler.cc#:~:text=StubCodeCompiler::GenerateSuspendStub).

## Resume stub

Resume stub is tail-called from `_SuspendState._resume` recognized method (which is called
from Dart helpers). It is used to resume execution of the previously suspended function.

Resume stub does the following:

- Allocates Dart frame on the stack, using `SuspendState.frame_size` to calculate its size.

- Copies frame contents from SuspendState to the stack.

- In JIT mode restores pool pointer (PP).

- Checks for the following cases and calls ResumeFrame runtime entry if any of this is true:
  + If resuming with an exception.
  + In JIT mode, if Code of the suspendable function is disabled (deoptimized).
  + In JIT mode, if there is a resumption breakpoint set by debugger.

- Otherwise, jumps to `SuspendState.pc` to resume execution of the suspended function.
  On x64/ia32 the continuation PC is adjusted by adding `SuspendStubABI::kResumePcDistance`
  to skip over the epilogue which immediately follows the Suspend stub call to maintain
  call/return balance.

ResumeFrame runtime entry is called as if it was called from suspended function at continuation PC.
It handles all corner cases by throwing an exception, lazy deoptimizing or calling into
the debugger.

For more details see `StubCodeCompiler::GenerateResumeStub` in [stub_code_compiler.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/compiler/stub_code_compiler.cc#:~:text=StubCodeCompiler::GenerateResumeStub)
and `ResumeFrame` in [runtime_entry.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/runtime_entry.cc#:~:text=ResumeFrame).

## Return stub

Suspendable functions can use Return stub if they need to do something when execution of
a function ends (for example, complete a Future or close a Stream). In such a case,
suspendable function jumps to the Return stub instead of returning.

Return stub does the following:

- Removes the frame of the suspendable function (as if function epilogue was executed).

- Calls a Dart method specific to a particular kind of suspendable function.
  The customization method takes a value of `:suspend_state` variable and a return value
  passed from the body of the suspendable function to the stub.

- The value returned from the customization method is used as the result of
  the suspendable function.

For more details see `StubCodeCompiler::GenerateReturnStub` in [stub_code_compiler.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/compiler/stub_code_compiler.cc#:~:text=StubCodeCompiler::GenerateReturnStub).

## Exception handling and AsyncExceptionHandler stub

Certain kinds of suspendable functions (async and async*) may need to catch all thrown exceptions
which are not caught within the function body, and perform certain actions (such as completing
the Future with an error).

This is implemented by setting `has_async_handler` bit on `ExceptionHandlers` object.
When looking for an exception handler, runtime checks if this bit is set and uses
AsyncExceptionHandler stub as a handler (see `StackFrame::FindExceptionHandler`).

AsyncExceptionHandler stub does the following:

- It inspects the value of `:suspend_state` variable. If it is `null` (meaning the prologue has not
  finished yet), the exception should not be handled and it is rethrown.
  This makes it possible for argument type checks to throw an exception  synchronously
  instead of completing a Future with an error.

- Otherwise, stub removes the frame of the suspendable function (as if function epilogue was
  executed) and calls `_SuspendState._handleException` Dart method. AsyncExceptionHandler stub
  does not use separate Dart helper methods for async and async* functions as exception handling is
  not performance sensitive and currently uses only one bit in `ExceptionHandlers` to select
  a stub handler for simplicity.

- The value returned from `_SuspendState._handleException` is used as the result of the
  suspendable function.

For more details see `StubCodeCompiler::GenerateAsyncExceptionHandlerStub` in [stub_code_compiler.cc](https://github.com/dart-lang/sdk/blob/main/runtime/vm/compiler/stub_code_compiler.cc#:~:text=StubCodeCompiler::GenerateAsyncExceptionHandlerStub).

## IL instructions

When compiling suspendable functions, the following IL instructions are used:

- `Call1ArgStub` instruction is used to call one-argument stubs such as InitSuspendableFunction.

- `Suspend` instruction is used to call Suspend stub. After calling Suspend stub,
  on x64/ia32 it also generates an epilogue right after the stub, in order to
  return to the caller after suspending without disrupting call/return balance.
  Due to this extra epilogue following the Suspend stub call, the resumption PC is
  not the same as the return address of the Suspend stub. So `Suspend` instruction
  uses 2 distinct deopt ids for the Suspend stub call and resumption PC.

- `Return` instruction jumps to a Return stub instead of returning for certain kinds
  of suspendable functions (async and async*).

# Combining all pieces together

## Async functions

See [async_patch.dart](https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/async_patch.dart) for the corresponding Dart source code.

Async functions use the following customized stubs:

### InitAsync stub

InitAsync = InitSuspendableFunction stub which calls `_SuspendState._initAsync`.

`_SuspendState._initAsync` creates a `_Future<T>` instance which is used as the result of
the async function. This `_Future<T>` instance is kept in `:suspend_state` variable until
`_SuspendState` instance is created during the first `await`, and then kept in
`_SuspendState._functionData`. This instance is returned from `_SuspendState._await`,
`_SuspendState._returnAsync`, `_SuspendState._returnAsyncNotFuture` and
`_SuspendState._handleException` methods to serve as the result of the async function.

### Await stub

Await = Suspend stub which calls `_SuspendState._await`. It implements the `await` expression.

`_SuspendState._await` allocates 'then' and 'error' callback closures when called for
the first time. These callback closures resume execution of the async function via Resume stub.
It is possible to create callbacks eagerly in the InitAsync stub, but there is a significant
fraction of async functions which don't have `await` at all, so creating callbacks lazily during
the first `await` makes those functions more efficient.
If an argument of `await` is a Future, then `_SuspendState._await` attaches 'then' and 'error'
callbacks to that Future. Otherwise it schedules a micro-task to continue execution of
the suspended function later.

### ReturnAsync stub

ReturnAsync stub = Return stub which calls `_SuspendState._returnAsync`.
It is used to implement `return` statement (either explicit or implicit when reaching
the end of function).

`_SuspendState._returnAsync` completes `_Future<T>` which is used as the result of
the async function.

### ReturnAsyncNotFuture stub

ReturnAsyncNotFuture stub = Return stub which calls `_SuspendState._returnAsyncNotFuture`.

ReturnAsyncNotFuture is similar to ReturnAsync, but used when compiler can prove that
return value is not a Future. It bypasses the expensive `is Future` test.

### Execution flow in async functions

The following diagram depicts how the control is passed in a typical async function:

```
Caller          Future<T> foo() async           Stubs        Dart _SuspendState methods
  |
  *-------------------> |
                    (prologue) -------------> InitAsync
                                                  |
                                                  *----------> _initAsync
                                                              (creates _Future<T>)
                                                  | <---------
                        | <-----------------------*
                        |
                        |
                      (await) ----------------> AwaitAsync
                                                  |
                                                  *----------> _await
                                                              (setups resumption)
                                                              (returns _Future<T>)
                                                  | <---------
  | <---------------------------------------------*

Awaited Future is completed
  |
  *------------------------------------------> Resume
                                                  |
                    (after await) <---------------*
                        |
                        |
                      (return) ---------------> ReturnAsync/ReturnAsyncNotFuture
                                                  |
                                                  *----------> _returnAsync/_returnAsyncNotFuture
                                                              (completes _Future<T>)
                                                              (returns _Future<T>)
                                                  | <---------
  | <---------------------------------------------*
```

## Async* functions

See [async_patch.dart](https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/async_patch.dart)
for the corresponding Dart source code.

Async* functions use the following customized stubs:

### InitAsyncStar stub

InitAsyncStar = InitSuspendableFunction stub which calls `_SuspendState._initAsyncStar`.

`_SuspendState._initAsyncStar` creates `_AsyncStarStreamController<T>` instance which is used
to control the Stream returned from the async* function. `_AsyncStarStreamController<T>` is kept
in `_SuspendState._functionData` (after the first suspension at the beginning of async* function).

## YieldAsyncStar stub and `yield`/`yield*`

YieldAsyncStar = Suspend stub which calls `_SuspendState._yieldAsyncStar`.

This stub is used to suspend async* function at the beginning (until listener is attached to
the Stream returned from async* function), and at `yield` / `yield*` statements.

When `_SuspendState._yieldAsyncStar` is called at the beginning of async* function it creates
a callback closure to resume body of the async* function (via Resume stub), creates and
returns `Stream`.

`yield` / `yield*` statements are implemented in the following way:

```
_AsyncStarStreamController controller = :suspend_state._functionData;
if (controller.add/addStream(<expr>)) {
  return;
}
if (YieldAsyncStar()) {
  return;
}
```

`_AsyncStarStreamController.add`, `_AsyncStarStreamController.addStream` and YieldAsyncStar stub
can return `true` to indicate that Stream doesn't have a listener anymore and execution of
async* function should end.

Note that YieldAsyncStar stub returns a value passed to a Resume stub when resuming async*
function, so the 2nd hasListeners check happens right before the async* function is resumed.

See `StreamingFlowGraphBuilder::BuildYieldStatement` for more details about `yield` / `yield*`.

### Await stub

Async* functions use the same Await stub which is used by async functions.

### ReturnAsyncStar stub

ReturnAsyncStar stub = Return stub which calls `_SuspendState._returnAsyncStar`.

`_SuspendState._returnAsyncStar` closes the Stream.

### Execution flow in async* functions

The following diagram depicts how the control is passed in a typical async* function:

```
Caller          Stream<T> foo() async*          Stubs        Dart helper methods
  |
  *-------------------> |
                    (prologue) -------------> InitAsyncStar
                                                  |
                                                  *----------> _SuspendState._initAsyncStar
                                                              (creates _AsyncStarStreamController<T>)
                                                  | <---------
                        | <-----------------------*
                        * ------------------> YieldAsyncStar
                                                  |
                                                  *----------> _SuspendState._yieldAsyncStar
                                                              (setups resumption)
                                                              (returns _AsyncStarStreamController.stream)
                                                  | <---------
  | <---------------------------------------------*

Stream is listened
  |
  *------------------------------------------> Resume
                                                  |
                  (after prologue) <--------------*
                        |
                        |
                      (yield) --------------------------------> _AsyncStarStreamController.add
                                                              (adds value to Stream)
                                                              (checks if there are listeners)
                        | <-----------------------------------
                        * ------------------> YieldAsyncStar
                                                  |
                                                  *----------> _SuspendState._yieldAsyncStar
                                                  | <---------
  | <---------------------------------------------*

Micro-task to run async* body
  |
  *----------------------------------------------------------> _AsyncStarStreamController.runBody
                                                              (checks if there are listeners)
                                                Resume <-------
                                                  |
                    (after yield) <---------------*
                        |
                        |
                      (return) ---------------> ReturnAsyncStar
                                                  |
                                                  *----------> _SuspendState._returnAsyncStar
                                                              (closes _AsyncStarStreamController)
                                                  | <---------
  | <---------------------------------------------*
```

## Sync* functions

See [async_patch.dart](https://github.com/dart-lang/sdk/blob/main/sdk/lib/_internal/vm/lib/async_patch.dart)
for the corresponding Dart source code.

Sync* functions use the following customized stubs:

### InitSyncStar stub

InitSyncStar = InitSuspendableFunction stub which calls `_SuspendState._initSyncStar`.

`_SuspendState._initSyncStar` creates a `_SyncStarIterable<T>` instance which is returned
from sync* function.

### SuspendSyncStarAtStart stub

SuspendSyncStarAtStart = Suspend stub which calls `_SuspendState._suspendSyncStarAtStart`.

This stub is used to suspend execution of sync* at the beginning. It is called after
InitSyncStar in the sync* function prologue. The body of sync* function doesn't run
until Iterator is not obtained from Iterable (`_SyncStarIterable<T>`) which is returned from
the sync* function.

### CloneSuspendState stub

This stub creates a copy of SuspendState object. It is used to clone state of sync*
function (suspended at the beginning) for each Iterator instance obtained from
Iterable.

See `StubCodeCompiler::GenerateCloneSuspendStateStub`.

### SuspendSyncStarAtYield stub and `yield`/`yield*`

SuspendSyncStarAtYield = Suspend stub which doesn't call helper Dart methods.

SuspendSyncStarAtYield is used to implement `yield` / `yield*` statements in sync* functions.

`yield` / `yield*` statements are implemented in the following way:

```
_SyncStarIterator iterator = :suspend_state._functionData;

iterator._current = <expr>;             // yield <expr>
  OR
iterator._yieldStarIterable = <expr>;   // yield* <expr>

SuspendSyncStarAtYield(true);
```

See `StreamingFlowGraphBuilder::BuildYieldStatement` for more details about `yield` / `yield*`.

The value passed to SuspendSyncStarAtYield is returned back from the invocation of
Resume stub. `true` indicates that iteration can continue.

### Returning from sync* functions.

Sync* function do not use Return stubs. Instead, return statements are rewritten to return `false`
in order to indicate that iteration is finished.

### Execution flow in sync* functions

The following diagram depicts how the control is passed in a typical sync* function:

```
Caller          Iterable<T> foo() sync*          Stubs        Dart helpers
  |
  *-------------------> |
                    (prologue) -------------> InitSyncStar
                                                  |
                                                  *----------> _SuspendState._initSyncStar
                                                              (creates _SyncStarIterable<T>)
                                                  | <---------
                        | <-----------------------*
                        * ------------------> SuspendSyncStarAtStart
                                                  |
                                                  *----------> _SuspendState._suspendSyncStarAtStart
                                                              (remembers _SuspendState at start)
                                                              (returns _SyncStarIterable<T>)
                                                  | <---------
  | <---------------------------------------------*

Iterable.iterator is called
  |
  *----------------------------------------------------------> _SyncStarIterable<T>.iterator
                                                              (creates _SyncStarIterator<T>)
                                                                |
                                      CloneSuspendState <-------*
                                      (makes a copy of _SuspendState at start)
                                                  |
                                                  *-----------> |
  | <------------------------------------------------------- (returns _SyncStarIterator<T>)

Iterator.moveNext is called
  |
  *----------------------------------------------------------> _SyncStarIterator<T>.moveNext
                                                              (iterates over the cached yield* iterator, if any)
                                                              (resumes sync* body to get the next element)
                                                Resume <-------
                                                  |
                  (after prologue) <--------------*
                        |
                        |
                      (yield) ---------------> SuspendSyncStarAtYield(true)
                                                  |
                                                  *---------->
                                                              (the next element is cached in _SyncStarIterator<T>._current)
                                                              (returns true indicating that the next element is available)
  | <----------------------------------------------------------

Iterator.moveNext is called
  |
  *----------------------------------------------------------> _SyncStarIterator<T>.moveNext
                                                              (iterates over the cached yield* iterator, if any)
                                                              (resumes sync* body to get the next element)
                                                Resume <-------
                                                  |
                  (after yield) <-----------------*
                        |
                        |
                  (return false) ----------------------------->
                                                              (returns false indicating that iteration is finished)
  | <----------------------------------------------------------
```