Loweringimplementation

Lowering Coroutines

A function that can pause and resume cannot keep its locals in a stack frame, because the frame does not survive the pause. The compiler splits the function at every suspension point and moves the surviving locals into a heap object, turning the body into a resumable state machine.

The question

What does the compiler do to a function containing yield so that it can stop in the middle and continue later?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

Before: an ordinary function body with a yield in it, and locals in a stack frame. After: a heap-allocated *state object* holding a state tag plus every local that is live across a suspension point, and a resume(state) function whose body is a switch on the tag that jumps into the middle of what used to be straight-line code. The state object exists to answer the question a stack frame cannot: what did this function know, at a moment when it is not running and no frame of its exists.

What this phase may assume or do

The split preserves observable behavior only if every value live across a suspension point is stored in the state object and restored on resume, if the resumption point is exactly the instruction after the yield rather than the start of any enclosing statement, and if the effects that must not be repeated — the ones already performed before the suspension — are behind states the switch cannot re-enter. A local that is dead across the suspension may stay in a register and be recomputed; a local whose address was taken may not be moved at all unless every holder of that address is also rewritten.

Key points

  • A coroutine suspends and its frame does not survive, so every local live across the suspension must move into a heap-allocated state object.
  • The function body becomes a resume(state) whose entry is a switch on a state tag, jumping into the middle of what was structured control flow.
  • Which locals become fields is a liveness question computed over the CFG, with suspension points as edges control leaves and re-enters.
  • Variables live at disjoint suspension points can share a field, which is how implementations keep the state object small.
  • Stackless coroutines pay this transformation and get one small object per instance; stackful coroutines skip it and pay a whole stack per instance.
  • Function colouring is a consequence of the transformation being per-function, not an arbitrary language restriction.
  • A local whose address escaped cannot simply be relocated, which is the self-reference problem that pinning exists to express.

Why the frame cannot hold it

implementationWhich model a language uses is a language-level decision with visible consequences. Python generators, C++20 coroutines, Rust async blocks, JavaScript generators and C# iterators are all stackless and use the transformation in this lesson. Go goroutines and Lua coroutines are stackful, with a real (growable) stack per instance, which is why a Go function does not need any annotation to block — there is nothing to colour. Kotlin sits in between: suspend functions are compiled to a state machine, but the compiler threads a continuation parameter rather than allocating one object per function.

A stack frame is created by a call and destroyed by a return. That is the entire contract, and it is why locals are cheap. A coroutine breaks the contract in the same way a closure does, but harder: the function stops halfway, gives control back to its caller, and expects to continue from the same point later with all its locals intact.

There is no way to do that with a frame that has been popped. Either the frame must not be popped — which is what a real stack-switching coroutine implementation does, giving each coroutine its own stack — or the locals must be moved somewhere that outlives the frame. The second answer is the compiler-side one, and it is what "stackless coroutines" means: no separate stack, one heap object per coroutine instance, and a function that can be re-entered.

The distinction matters because the two have completely different costs. Stackful coroutines are cheap for the compiler and expensive for memory: a stack per coroutine, sized in advance for the deepest call it might make. Stackless coroutines are cheap for memory — the state object holds exactly the live locals of one function — and expensive for the compiler, which must perform this transformation, and restrictive for the programmer, because a suspension can only happen in a function that was compiled as a coroutine. That last restriction is what people mean by "function colouring", and it is a direct consequence of the lowering.

The transformation

Take the smallest interesting generator: one that yields twice with a local that must survive both suspensions. The compiler numbers the suspension points, computes which locals are live across each of them, and builds a struct with a state tag and one field per surviving local. The body becomes a switch on the tag, with a case per state that jumps to the resumption point.

Read the after side for two things that are easy to miss. First, the entry into the middle of the loop: state 1 resumes *after* the yield, inside the loop body, not at the top of the loop — the switch jumps into the middle of a structured construct, which is why this transformation is much easier on a CFG than on an AST. Second, i became a field. It was a loop induction variable, the sort of thing that lives in a register forever, and it is now a heap load and a heap store per iteration.

That second point is the performance story of the whole lesson. Any local live across a suspension leaves the register allocator. A coroutine whose hot loop crosses a suspension point pays memory traffic on its induction variable, which is why the optimization work in real coroutine implementations is overwhelmingly about *reducing the size of the state* and getting the non-suspending paths back into registers.

A two-suspension generator becomes a state machine
Before
fn counter(limit: int) -> generator<int> {
    let total = 0
    for i in 0..limit {
        total = total + i
        yield i          // suspension point 1
    }
    yield total          // suspension point 2
}
After
struct CounterState {
    state: int      // 0 = not started, 1 = after yield 1, 2 = after yield 2, 3 = done
    limit: int      // live across both suspensions
    total: int      // live across both suspensions
    i:     int      // live across suspension 1
}

fn resume(s: *CounterState) -> Option<int> {
    switch s.state {
      case 0: s.total = 0; s.i = 0; goto loop_head
      case 1: goto after_yield_1        // re-enters the middle of the loop
      case 2: goto after_yield_2
      case 3: return None
    }
loop_head:
    if s.i >= s.limit { goto tail }
    s.total = s.total + s.i
    s.state = 1; return Some(s.i)       // suspend
after_yield_1:
    s.i = s.i + 1; goto loop_head
tail:
    s.state = 2; return Some(s.total)   // suspend
after_yield_2:
    s.state = 3; return None
}
Legal only when

Only if the live-across-suspension set is computed correctly — every value the code after a yield reads must be a field, or it reads whatever the register happened to hold on some unrelated later call. The resumption label must be the point immediately after the yield, so effects performed before it are not repeated. The state tag must cover every suspension point plus the not-started and completed states, and resuming a completed coroutine must be defined rather than falling through into live code.

Illegal when

If a local whose address was taken is moved into the state object without rewriting the holders of that address — a pointer into the old frame then refers to freed memory, and this is exactly the self-referential-coroutine problem that Rust's Pin exists to make expressible. It is also wrong if the transformation restarts an enclosing statement rather than resuming after the yield: a yield inside the middle of an expression with side effects on both sides must not re-run the left side. And it is wrong to omit a variable that is only read on an error path, since liveness must be computed over all paths and not the common one.

Computing the state, and why it is a data-flow question

Which locals go in the state object is exactly a liveness question: a variable is in the state if it is live at some suspension point, meaning some path from that point reads it before writing it. That is [[liveness-analysis]], run over the coroutine's CFG with the suspension points treated as places where control leaves and may re-enter.

Two refinements are what separate a naive implementation from a good one. Variables live at *disjoint* suspension points can share a field, exactly as values with disjoint live ranges can share a register — the state object gets a union-like layout and shrinks, sometimes dramatically. And variables that are dead across every suspension stay in registers entirely and never appear in the object, which means the non-suspending fast path in a coroutine can be as good as ordinary code.

Getting the object small matters because it is allocated per coroutine instance, and coroutines are frequently created in large numbers — one per connection, one per row, one per request. A hundred thousand in-flight coroutines each holding a needlessly large frame is a real memory problem, and it is a problem that appears as "this service uses more memory than it should" rather than as anything identifiable in the source.

Liveness across suspension decides the state fields
  1. c0entryentry
    total = 0
i = 0
    Both defined here.
  2. c1loop head
    if i >= limit -> tail
    i and limit live.
  3. c2body
    total = total + i
SUSPEND 1 (yield i)
    At the suspension: total, i, limit all live afterwards. All three become fields.
  4. c3after yield 1
    i = i + 1
    Resumption target. Entry point of state 1.
  5. c4tail
    SUSPEND 2 (yield total)
    At this suspension only nothing is live afterwards — but total is read here, so it must have survived suspension 1.
  6. c5done
    state = 3
return None
Edges
  • c0→c1
  • c1→c2
  • c1→c4i >= limit
  • c2→c3resume
  • c3→c1
  • c4→c5resume

Read it asThe suspension edges are the interesting ones: control leaves at c2 and re-enters at c3, which is why the resumption target is a block boundary rather than the top of the loop. A variable is a state field if it is live on any suspension edge. i is; limit is; total is, because it is read at c4 after crossing suspension 1. If total had only been used before the first yield, it would have stayed in a register.

What the transformation gives away

The generated code is unrecognisable, and that has consequences beyond aesthetics. A stack trace taken inside a resumed coroutine shows resume rather than the source function, unless the toolchain emits enough metadata to reconstruct the source position — and because the coroutine's logical caller is not its physical caller, the *chain* above the coroutine is a fiction that has to be rebuilt from the state objects rather than walked from the stack pointer. This is why async stack traces are a separate feature in every runtime that has them, rather than a thing that just works.

Debugging is affected the same way. A breakpoint inside a coroutine body maps to a point inside the switch, and stepping past a yield returns to the caller rather than continuing to the next line, which is correct and confusing. Debuggers that handle this well have been taught the shape of the transformation by the compiler.

And the coloured-function property that people complain about is not a language whim: because the transformation applies to one function, only a function that was compiled this way can suspend. A plain function called from a coroutine has an ordinary frame, and nothing can pause it. Stackful implementations do not have this restriction because they do not do this transformation — they suspend by switching stacks, which works regardless of how the function was compiled.

  • Stack traces show the resume function, not the source function, unless the toolchain reconstructs them from state objects.
  • The logical caller chain is not on the stack; it is a linked structure through the coroutine states.
  • Stepping over a yield returns to the caller, which is correct and surprises everyone once.
  • Only functions compiled as coroutines can suspend — the transformation is per-function, so the property is per-function.
  • Locals live across a suspension leave register allocation, so hot loops that cross a yield pay memory traffic.

How it works

The steps, in the order the compiler takes them.

  • Identify every suspension point in the function body and assign each a distinct state number, plus states for not-started and completed.
  • Build the CFG and run liveness with suspension points treated as points where control exits and may later re-enter at the following instruction.
  • Collect the variables live across any suspension edge; allocate a field for each, overlapping variables whose suspension-crossing live ranges are disjoint.
  • Rewrite every use of a state variable as a load or store on the state object, leaving variables that never cross a suspension in registers.
  • Replace the function entry with a switch on the state tag that transfers to the block following the corresponding suspension point.
  • Replace each suspension with a store of the next state tag followed by a return of the yielded value; the block after it becomes a resumption target.
  • Emit debug metadata mapping each state and each field back to the source position and source variable, or the debugger sees only the switch.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A value read after a resume is garbage, because liveness missed a path — typically a variable used only on an error branch after the yield — and it was never stored in the state.
  • Code before a suspension runs twice: the resumption target was placed at the start of the enclosing statement rather than immediately after the yield, so an already-performed side effect repeats.
  • A stack trace from inside a coroutine shows the generated resume function and stops, giving no indication of who created the coroutine or where in the source it paused.
  • Memory usage scales with the number of in-flight coroutines far worse than expected, because the state object holds every local in the function rather than the ones that actually cross a suspension.
  • A previously fast loop slows down markedly once a yield is added inside it, because the induction variable is now a heap field written on every iteration.
  • A coroutine holding a pointer to one of its own locals reads freed memory after a resume, because the state object was moved and the pointer was not updated.
  • Resuming an already-completed coroutine falls into live code instead of returning the completed signal, and the body runs again with stale state.

When it helps

  • Producing a sequence lazily, where materialising the whole thing would cost memory proportional to the input — parsers, tokenizers, streaming readers.
  • Expressing a state machine as straight-line code, so the states are implicit in the control flow rather than encoded by hand in an enum and a switch.
  • Interleaving many logical tasks in one thread, where a state object per task is far cheaper than a stack per task.
  • Producer/consumer structures where the natural expression is two functions that hand control back and forth.

When it hurts

  • In hot loops that cross a suspension, where the induction variable leaves the register allocator and every iteration touches memory.
  • When the state object ends up large and the number of instances is large, turning an elegant design into a memory problem.
  • When debugging matters and the toolchain does not reconstruct source-level stacks — the generated shape is genuinely hard to read.
  • When the code must interoperate with functions that cannot be recompiled as coroutines, since a plain function cannot suspend.

What it costs

Every one of these is paid by something.

  • Stackless lowering buys a state object sized to the live locals of one function, and pays function colouring plus a substantial compiler transformation that every debugger and profiler must then be taught about.
  • Stackful coroutines buy the ability to suspend anywhere in any function, with no transformation and no colouring, and pay a whole stack per instance — pre-sized or growable, and either choice costs memory or costs a growth check.
  • Overlapping state fields buys a smaller object and pays in debug information: a field now means different source variables in different states, which the debugger must be told or it will print the wrong one.
  • Keeping non-crossing locals in registers buys a fast non-suspending path and pays in transformation complexity, because the split now depends on a data-flow result rather than on syntax.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Write the state machine by hand: an explicit enum, an explicit struct of surviving variables, and a switch. Exactly what the compiler generates, with no colouring and no toolchain surprises, and unreadable past three or four states.
  • Stackful coroutines or green threads, where suspension is a stack switch. No compiler transformation, no colouring, and memory proportional to stacks rather than to live variables.
  • Callbacks and continuation-passing: pass the rest of the computation as a function. This is the manual form of the same idea and produces the nesting that coroutine syntax exists to remove.
  • An operating-system thread per task, which needs no language support at all and costs a kernel stack plus a context switch — correct up to some thousands of tasks and not beyond.

See it for yourself

The flag, dump or tool that shows you this directly.

  • Python: gen.gi_frame.f_locals shows a suspended generator's live locals and gi_frame.f_lasti the resumption offset; dis.dis on a generator function shows SEND, YIELD_VALUE and RESUME opcodes marking the split points.
  • C++20: compile a coroutine on Compiler Explorer with -O0 and look for the _Z...resume, ...destroy and frame-allocation symbols; -fcoro-aligned-allocation and the __builtin_coro_* intrinsics in the LLVM IR show the frame before it is split.
  • Rust: rustc -Z unpretty=mir shows the generator as a state machine with a discriminant; std::mem::size_of_val on a future is the state object size, and shrinking it is a routine optimization exercise.
  • C#: any IL decompiler on a method containing yield return shows a generated nested class implementing the iterator with an int <>1__state field and hoisted locals as fields — the transformation in this lesson, verbatim.
  • JavaScript: run a generator through a transpiler targeting ES5; the regenerator output is an explicit switch on a state variable and is the most readable rendering of the transformation available.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "A generator keeps its stack frame alive." It does not have one while suspended. Its live locals are fields of a heap object, and the frame is created afresh on each resume.
  • "Coroutines are threads without the OS." Stackless coroutines are not threads in any sense: there is no stack, no scheduler entitlement, and no preemption. Suspension happens only where the source says it does.
  • "Function colouring is a design mistake someone could have avoided." It follows from lowering per function. The languages without it use stack switching instead and pay for it in memory per instance.
  • "The state object is the size of the frame." It is the size of the locals live across suspensions, which is usually much smaller and occasionally, through a missed liveness refinement, larger than anyone expects.

Misconceptions

The claim, and what is actually true.

A generator is just a function that returns lazily.
It is a heap object plus a re-entrant function. The lazy sequence is the interface; the state machine is the implementation, and the state object is what you pay for.
Adding a yield to a function is a local change.
It changes the function's calling convention, its return type, where its locals live, and what a stack trace through it looks like.
Coroutines avoid allocation because they avoid threads.
They avoid a stack per task and typically allocate one state object per instance. The win is size, not the absence of allocation.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A function with yield in it can stop halfway and continue later. Its local variables cannot stay on the stack, because the stack space is gone the moment it stops. So the compiler puts those variables in a small object on the heap along with a number saying where it stopped, and rewrites the function so that calling it again jumps straight back to that spot with the variables restored.

practical

Two things to expect. First, memory: each live coroutine costs one object holding every variable that survives a pause, so a service with many in-flight coroutines is holding many of these — if memory is higher than expected, measure the state size (size_of_val on a Rust future, the generated class in a .NET decompiler) rather than guessing. Second, tooling: stack traces and stepping behave differently inside a coroutine because the physical call stack is not the logical one. Learn what your runtime offers for async traces before you need it during an incident, not after.

advanced

The hard parts of this transformation are the ones the simple example hides. Destructors and cleanup must run when a suspended coroutine is destroyed without resuming, which means the state object carries enough information to know which locals are currently constructed — effectively a second state machine for cleanup, and the same table-driven machinery as [[stack-unwinding]]. Address-taken locals cannot simply be relocated into the object, and a coroutine that holds a pointer into its own state cannot be moved afterwards, which is why Rust needed Pin to express "this object may not be moved again" in a language whose default is that everything is movable. And the state layout is a register-allocation problem in disguise: overlapping variables with disjoint crossing ranges is graph colouring on a different graph, with the same payoff and the same debug-information cost.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationStackless versus stackful is a per-language decision with different consequences. Python, C#, JavaScript, Rust and C++20 are stackless and perform this transformation, so suspension is limited to functions compiled as coroutines. Go and Lua are stackful, so any function can block and there is no colouring, at the cost of a stack per instance. Kotlin compiles suspend functions to state machines but threads a continuation parameter instead of one object per call. Nothing about the shape of a coroutine in one of these transfers to another.
typicalMainstream implementations allocate the state object on the heap when the coroutine is created, and several then try to elide the allocation when the coroutine provably does not outlive its creator — the C++ standard explicitly permits this elision and compilers perform it inconsistently, so the same code may or may not allocate depending on inlining decisions upstream. Do not treat a measured allocation count for a coroutine as stable across compiler versions.
specThat resumption continues immediately after the suspension point, rather than re-entering the enclosing statement, is specified behaviour in every language with generators — it is what makes side effects before a yield happen once. What is not uniform is what happens when a suspended coroutine is destroyed without being resumed: C++ requires the frame's destructors to run via destroy, Python throws GeneratorExit into the generator, and Rust simply drops the future and runs the state object's drop glue.

If you were asked this in an interview

  • A function contains a yield inside a loop. What does the compiler generate, and where does the loop counter live?
  • Why can a generator only suspend inside a function that was compiled as a generator?
  • How would you decide which locals go into the state object?

Connections

Concurrencycoroutinestasks-vs-threadsthreads
Performanceallocation-profilingmemory-performance
OS & Networkingstack-framesstack-vs-heapstack-overflow
Domains that do not exist yet
  • Programming Languages & Runtime Internals — The scheduler that decides when a suspended coroutine is resumed, and the collector that traces the state object
    The compiler produces a resumable function and an object holding its live state. Who calls resume, in what order, on which thread, and how the collector finds live references inside the state object are runtime questions that this transformation creates and does not answer.