Garbage Collection

How a frontend with a collector gets allocation, safepoints, write barriers and root tracking into Esper IR, and what the IR cannot do for it.

This page describes the current SSA builder and backend implementation. Its unversioned esp examples are compatibility snapshots, still accepted by the reader. Start with the new text walkthrough for esper 1 syntax and the roadmap for the library-first migration boundary.

Esper has no garbage collector, no safepoint opcode and no root map. That is the honest starting point for this page, and most of what follows is a consequence of it: a collector reaches the IR as a set of ordinary extern functions, and the frontend decides where the calls go.

Three of the four things a collector needs work well that way. Allocation is a call. A safepoint poll is a call. A write barrier is a call. The optimizer treats all three as effects, so none of them is deleted, merged or moved out of a loop.

The fourth is roots, and it is the one Esper cannot help with. There is no liveness analysis in the library, no stack map in any backend, and no way to ask which SSA values hold live pointers at a given call. A precise collector therefore needs the frontend to keep its roots in memory it controls. The roots section says what that costs and what the alternatives are.

Allocation

The collector’s allocator is an extern declaration like any other. Declare it, call it, initialise the object through the pointer it returns.

func makePair(_ a: Int32, _ b: Int32) -> Pair {
    Pair(first: a, second: b)     // allocated in the collected heap
}
static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef alloc_params[1] = {ESP_TYPE_I64};
  EsperTypeRef alloc_rets[1] = {ESP_TYPE_PTR};
  esper_func_declare(unit, "gc_alloc", alloc_params, 1, alloc_rets, 1, true);

  EsperTypeRef params[2] = {ESP_TYPE_I32, ESP_TYPE_I32};
  EsperTypeRef rets[1] = {ESP_TYPE_PTR};
  EsperBuilder *b = esper_build_begin(unit, "make_pair", params, 2, rets, 1);
  esper_build_bind(b, esper_build_block(b, "entry"));

  // One collector header word, then the two i32 fields behind it.
  EsperVal size = esper_build_ldi(b, ESP_TYPE_I64, 16);
  EsperVal obj = esper_build_call(b, ESP_TYPE_PTR, "gc_alloc", &size, 1);

  EsperVal eight = esper_build_ldi(b, ESP_TYPE_I64, 8);
  EsperVal first = esper_build_binary(b, ESP_OP_ADD, ESP_TYPE_I64, obj, eight);
  esper_build_store(b, ESP_OP_STORE, ESP_TYPE_I32, first,
                    esper_build_param(b, 0));

  EsperVal twelve = esper_build_ldi(b, ESP_TYPE_I64, 12);
  EsperVal second = esper_build_binary(b, ESP_OP_ADD, ESP_TYPE_I64, obj, twelve);
  esper_build_store(b, ESP_OP_STORE, ESP_TYPE_I32, second,
                    esper_build_param(b, 1));

  esper_build_ret(b, &obj, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "make_pair: %s\n", esper_builder_last_error(b));

  esper_builder_free(b);
}
func extern $gc_alloc(i64) -> ptr
func $make_pair(%0 i32, %1 i32) -> ptr {
entry:
  %2 = ldi i64 16
  %3 = call ptr $gc_alloc, %2
  %4 = ldi i64 8
  %5 = add i64 %3, %4
  store i32 %5, %0
  %7 = ldi i64 12
  %8 = add i64 %3, %7
  store i32 %8, %1
  ret ptr %3
}

The size is the frontend’s to compute, including whatever header word the collector wants in front of the payload. Esper’s type table will compute the payload part: declare the object as a struct and esper_type_size reports the laid-out size, so the frontend adds its header rather than hard-coding a total. Call esper_unit_layout_for first when the target’s pointer width differs from the host’s, since that is what an aggregate’s size depends on. The structs guide has the layout rules.

An unused call is never removed. Dead code elimination pins calls as side-effecting, so an allocation whose result is dropped still happens, which is what a frontend wants when allocation is what triggers a collection.

What halloc, salloc and alloc do instead

Esper’s own memory opcodes exist, and none of them reaches a collector. It is worth being precise about what each one is, because the names invite the wrong assumption.

halloc calls esp_halloc in Esper’s runtime, which is malloc with an allocation counter and optional tracing on top. free calls esp_free, which is free. There is no header word, no type information, and nothing that a collector could scan or move. It is the allocator for a frontend that does not have a collector.

salloc asks for storage that lives as long as the call frame. The LLVM backend emits alloca; the C backend currently emits malloc with no matching free, so a salloc in a hot function leaks there. That divergence matters for the root frames below, and it is the one place on this page where the backends do not agree.

alloc is neither until escape analysis has run over it. The pass walks the uses of each allocation and rewrites the opcode:

                                   entry:                       // never leaves
entry:                        ->     %1 = salloc %0             // the function
  %1 = alloc %0                      store i32 %1, %2
  store i32 %1, %2                   %4 = load i32 %1
  %4 = load i32 %1

                                   entry:                       // passed to an
entry:                        ->     %1 = halloc %0             // extern callee
  %1 = alloc %0                      call $gc_register, %1
  call $gc_register, %1

That is the behaviour to be careful about. An object the frontend intends the collector to own, allocated with alloc and never leaked in a way the intraprocedural analysis can see, becomes stack storage that the collector will never hear about and that disappears on return. Route collected objects through a call to your allocator and leave alloc for the things the language already knows are unmanaged. Optimization Passes has the full classification.

One more asymmetry follows from the same place. Dead code elimination will remove a halloc together with the free that consumes it, since the pair has no other effect. It will not remove a call to gc_alloc, because it cannot know what the call does. Conflating the two allocators means conflating those two behaviours.

Safepoints

A safepoint is a point where the mutator is willing to be stopped. A collector that moves objects, or that walks a thread’s roots, needs the thread to be at one, and the frontend decides where those are.

The usual rule is a poll on every loop back edge and at every function entry that is not a leaf, which is enough to bound the time until a request to stop is noticed. Esper does not insert them, and would not know where to: it has no notion of which calls can collect.

func sumTo(_ n: Int32) -> Int32 {
    var acc: Int32 = 0
    for i in 0..<n { gcPoll(); acc += i }
    return acc
}
static void esper_doc_build(EsperUnit *unit) {
  esper_func_declare(unit, "gc_poll", NULL, 0, NULL, 0, true);

  EsperTypeRef params[1] = {ESP_TYPE_I32};
  EsperTypeRef rets[1] = {ESP_TYPE_I32};
  EsperBuilder *b = esper_build_begin(unit, "sum_to", params, 1, rets, 1);

  EsperBlockId entry = esper_build_block(b, "entry");
  EsperBlockId header = esper_build_block(b, "header");
  EsperBlockId body = esper_build_block(b, "body");
  EsperBlockId done = esper_build_block(b, "done");

  esper_build_bind(b, entry);
  EsperVal zero = esper_build_ldi(b, ESP_TYPE_I32, 0);
  EsperVal seed[2] = {zero, zero};
  esper_build_jmp_args(b, header, seed, 2);

  esper_build_bind(b, header);
  EsperVal acc = esper_build_block_param(b, ESP_TYPE_I32);
  EsperVal i = esper_build_block_param(b, ESP_TYPE_I32);
  EsperVal test = esper_build_binary(b, ESP_OP_LT_S, ESP_TYPE_I32, i,
                                     esper_build_param(b, 0));
  esper_build_jmp_if(b, test, body, done);

  esper_build_bind(b, body);

  // The back edge is where the collector is allowed to stop this thread.
  esper_build_call(b, ESP_TYPE_VOID, "gc_poll", NULL, 0);

  EsperVal next_acc = esper_build_binary(b, ESP_OP_ADD, ESP_TYPE_I32, acc, i);
  EsperVal one = esper_build_ldi(b, ESP_TYPE_I32, 1);
  EsperVal next_i = esper_build_binary(b, ESP_OP_ADD, ESP_TYPE_I32, i, one);
  EsperVal carry[2] = {next_acc, next_i};
  esper_build_jmp_args(b, header, carry, 2);

  esper_build_bind(b, done);
  esper_build_ret(b, &acc, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "sum_to: %s\n", esper_builder_last_error(b));

  esper_builder_free(b);
}
func extern $gc_poll()
func $sum_to(%0 i32) -> i32 {
entry:
  %1 = ldi i32 0
  jmp header(%1, %1)

header(%3 i32, %4 i32):
  %5 = lt.s i32 %4, %0
  jmp.if %5 body done

body:
  call $gc_poll
  %8 = add i32 %3, %4
  %9 = ldi i32 1
  %10 = add i32 %4, %9
  jmp header(%8, %10)

done:
  ret i32 %3
}

The poll survives the passes that would otherwise be a worry. Loop-invariant code motion excludes calls from what it hoists, so the poll stays inside the loop while the ldi beside it is hoisted out; common subexpression elimination and global value numbering give two calls to the same function distinct congruence classes, so back-to-back polls are not collapsed into one; and dead code elimination keeps a call whose result is unused. Nothing needs to be marked.

What the frontend does pay for is the call itself. Esper has no inline-poll form, so a safepoint is a real call at every back edge rather than a load and a branch. A frontend that cares can poll on a counter instead, which is ordinary IR: increment, compare, and call only when the counter trips.

Write barriers

A generational or incremental collector needs to hear about a pointer store into an already-allocated object. That is a call before the store, taking the object being written and the value going in.

func setNext(_ node: Node, _ value: Node) {
    gcWriteBarrier(node, value)
    node.next = value
}
static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef barrier_params[2] = {ESP_TYPE_PTR, ESP_TYPE_PTR};
  esper_func_declare(unit, "gc_write_barrier", barrier_params, 2, NULL, 0, true);

  EsperTypeRef params[2] = {ESP_TYPE_PTR, ESP_TYPE_PTR};
  EsperBuilder *b = esper_build_begin(unit, "set_next", params, 2, NULL, 0);
  esper_build_bind(b, esper_build_block(b, "entry"));

  EsperVal owner = esper_build_param(b, 0);
  EsperVal value = esper_build_param(b, 1);

  // The barrier sees the object being written, not the slot inside it.
  EsperVal args[2] = {owner, value};
  esper_build_call(b, ESP_TYPE_VOID, "gc_write_barrier", args, 2);

  EsperVal offset = esper_build_ldi(b, ESP_TYPE_I64, 8);
  EsperVal slot = esper_build_binary(b, ESP_OP_ADD, ESP_TYPE_I64, owner, offset);
  esper_build_store(b, ESP_OP_STORE, ESP_TYPE_PTR, slot, value);

  esper_build_ret(b, NULL, 0);

  if (!esper_build_end(b))
    fprintf(stderr, "set_next: %s\n", esper_builder_last_error(b));

  esper_builder_free(b);
}
func extern $gc_write_barrier(ptr, ptr)
func $set_next(%0 ptr, %1 ptr) {
entry:
  call $gc_write_barrier, %0, %1
  %3 = ldi i64 8
  %4 = add i64 %0, %3
  store ptr %4, %1
  ret
}

The barrier takes the owning object rather than the address of the field, because a card-marking collector wants to mark the card the object sits on and a remembered-set collector wants to record the object. A frontend whose barrier needs the field address computes it once and passes it to both.

The store cannot move across the call. Esper’s passes do not reorder a store past a call, so the barrier-then-store order the frontend wrote is the order the backend sees. What Esper does not provide is a way to say that a store is a pointer store, so a barrier that should be conditional on the value being a heap reference has to be made conditional in the IR, with a compare and a branch, or absorbed into the barrier function.

Where the barrier is cheap enough to inline, emit its body rather than the call. It is ordinary arithmetic on the object address plus a byte store, and inlining it in the frontend is the only way to get it inlined: an extern has no body, so Esper’s inliner cannot reach it.

Roots

This is the part Esper does not do.

A precise collector has to know, at every point where it might run, which machine registers and stack slots hold live references. Compilers that support one emit a stack map for each safepoint, and the collector reads it during the scan. Esper emits nothing of the kind. There is no liveness analysis in the library, no per-call live-value set, no stack-map section in any backend, and no hook that a backend could use to request one. Nor is there a way to mark an SSA value as a managed reference: ptr is one type, and a pointer into the collected heap is indistinguishable from a pointer to a stack slot or to a string literal.

So a frontend targeting Esper has two options, and both put the roots in memory the frontend controls.

A shadow stack. The function allocates a small frame, registers it with the collector on entry, writes each live reference into a slot before any call that might collect, and reads it back afterwards. The collector walks the linked list of frames instead of the machine stack. It is what a source-to-source compiler does for the same reason.

A conservative collector. The collector scans the machine stack and registers for anything that looks like a heap address. No cooperation from the compiler is needed, so this works today with no extra IR at all. The cost is that it cannot move objects, since it cannot tell a reference from an integer that happens to look like one, and it retains whatever a stale word points at.

Here is the shadow-stack shape. The second allocation may collect, so the object from the first is reached through the slot rather than through the SSA value the call returned.

static void esper_doc_build(EsperUnit *unit) {
  EsperTypeRef alloc_params[1] = {ESP_TYPE_I64};
  EsperTypeRef alloc_rets[1] = {ESP_TYPE_PTR};
  esper_func_declare(unit, "gc_alloc", alloc_params, 1, alloc_rets, 1, true);

  EsperTypeRef push_params[2] = {ESP_TYPE_PTR, ESP_TYPE_I32};
  esper_func_declare(unit, "gc_push_frame", push_params, 2, NULL, 0, true);
  esper_func_declare(unit, "gc_pop_frame", NULL, 0, NULL, 0, true);

  EsperTypeRef rets[1] = {ESP_TYPE_PTR};
  EsperBuilder *b = esper_build_begin(unit, "make_cons", NULL, 0, rets, 1);
  esper_build_bind(b, esper_build_block(b, "entry"));

  // One root slot, which is the whole of what the collector will scan.
  EsperVal frame_size = esper_build_ldi(b, ESP_TYPE_I32, 8);
  EsperVal frame = esper_build_unary(b, ESP_OP_SALLOC, ESP_TYPE_PTR, frame_size);
  EsperVal slots = esper_build_ldi(b, ESP_TYPE_I32, 1);
  EsperVal push_args[2] = {frame, slots};
  esper_build_call(b, ESP_TYPE_VOID, "gc_push_frame", push_args, 2);

  EsperVal size = esper_build_ldi(b, ESP_TYPE_I64, 16);
  EsperVal head = esper_build_call(b, ESP_TYPE_PTR, "gc_alloc", &size, 1);
  esper_build_store(b, ESP_OP_STORE, ESP_TYPE_PTR, frame, head);

  // This allocation may collect, so the object is read back from the slot
  // rather than reused out of the SSA value the first call returned.
  EsperVal tail = esper_build_call(b, ESP_TYPE_PTR, "gc_alloc", &size, 1);
  EsperVal moved = esper_build_load(b, ESP_OP_LOAD, ESP_TYPE_PTR, frame);
  EsperVal offset = esper_build_ldi(b, ESP_TYPE_I64, 8);
  EsperVal link = esper_build_binary(b, ESP_OP_ADD, ESP_TYPE_I64, moved, offset);
  esper_build_store(b, ESP_OP_STORE, ESP_TYPE_PTR, link, tail);

  esper_build_call(b, ESP_TYPE_VOID, "gc_pop_frame", NULL, 0);
  esper_build_ret(b, &moved, 1);

  if (!esper_build_end(b))
    fprintf(stderr, "make_cons: %s\n", esper_builder_last_error(b));

  esper_builder_free(b);
}
func extern $gc_alloc(i64) -> ptr
func extern $gc_push_frame(ptr, i32)
func extern $gc_pop_frame()
func $make_cons() -> ptr {
entry:
  %0 = ldi i32 8
  %1 = salloc %0
  %2 = ldi i32 1
  call $gc_push_frame, %1, %2
  %4 = ldi i64 16
  %5 = call ptr $gc_alloc, %4
  store ptr %1, %5
  %7 = call ptr $gc_alloc, %4
  %8 = load ptr %1
  %9 = ldi i64 8
  %10 = add i64 %8, %9
  store ptr %10, %7
  call $gc_pop_frame
  ret ptr %8
}

Two details of that are load-bearing.

%8 is a reload rather than a reuse of %5. If the collector moves objects, %5 is the address before the second allocation ran and the slot holds the address after. A frontend that reuses %5 has a bug that only appears when a collection happens to land on that call, which is the worst kind.

The slot survives optimization because its address is passed to gc_push_frame. Stack-slot promotion only takes a slot whose address is used as nothing but the address operand of a plain load or store, so registering the frame is what keeps it in memory. Drop that call and the slot is exactly the shape mem2reg promotes, and the whole root disappears:

// the same function without gc_push_frame, after mem2reg and DCE
func $make_cons() -> ptr {
entry:
  nop                       // the salloc and its size are gone
  nop
  %2 = ldi i64 16
  %3 = call ptr $gc_alloc, %2
  nop                       // the store into the slot is gone
  %5 = call ptr $gc_alloc, %2
  nop                       // the reload is gone
  %7 = ldi i64 8
  %8 = add i64 %3, %7       // the pre-collection pointer
  store ptr %8, %5
  call $gc_pop_frame
  ret ptr %3
}

Every use of the reload became %3, the value from before the second allocation, which is the bug described above introduced by a pass doing exactly what it is meant to do. If a frontend wants to keep root slots out of the reach of mem2reg without a registration call in every function, volatile accesses do it: a slot touched by one is never promoted, and no pass may delete, merge or move the access.

What is missing

Stated plainly, so that a frontend author can plan around it rather than discover it: Esper cannot today tell a collector which values are live at a safepoint. There is no stack map, no root map, no liveness query in the public API, and no distinct type for a managed reference. Every root a precise collector sees has to be one the frontend put in memory itself, with the cost of a store before each call that might collect and a load after it.

Key takeaways