Memory management

How heap allocations are reclaimed on each backend. The user writes no annotations and sees no defaults — every reclaim point is computed from the Core IR.

Guarantee to the user

Every heap-allocated cell — ADT constructor, boxed primitive, string — is reclaimed once it is no longer reachable, on every backend, with no manual free, no manual Rc::clone, no manual null assignment, no GC hint.

Identical reclaim semantics across all five backends. The mechanism differs by target:

Backend	Reclaim mechanism
JVM	Host JVM garbage collector (G1/ZGC)
CLR	Host CLR generational garbage collector
JS	Host JS engine garbage collector (V8/JSC)
LLVM	Compiler-emitted reference counting over libc malloc / free
WASM	Compiler-emitted reference counting over a per-size-bin freelist in linear memory

Why reference counting on LLVM and WASM

Tracing GC needs precise root identification, type information at every heap block, and (on WASM) a shadow stack. Reference counting needs only a header on each heap block and a balanced inc/dec discipline. Three language-level invariants make the latter sufficient:

1. Immutability. A field cannot be rewritten after construction, so the cell graph is acyclic. Reference counting is complete; no mark-sweep fallback is needed.
2. Closed world after defunctionalization. No first-class function value survives Awsum.Defunctionalize and Awsum.LowerClosures. Every pointer flow is visible in Core, so the compiler can place the right inc/dec at every transfer.
3. Uniform heap-block shape. Every heap block is one of: ADT cell (CCon lowering), structural-sum cell (CRow lowering, a 1-field constructor), boxed primitive, or string. All four are positional [tag, field₀, …]-style blocks reachable through a uniform header.

Heap-block layout on LLVM and WASM

Each heap block carries a 12-byte header preceding the user-visible pointer:

  offset       field        size
  -12          flag         i32
   -8          refcount     i32
   -4          shape        i32
    0          user data    …

The user-facing pointer always points 12 bytes past the block start. Readers (string-length headers, ADT-tag at slot 0, constructor fields at slot 1+) operate on the user pointer and are unaware of the header.

• flag identifies the block class.
  • flag == 0: literal in static data (@.str.N on LLVM, (data …) on WASM). __inc_ref / __free_recursive / __free all short-circuit. The block is never reclaimed.
  • flag == 1 on LLVM: heap block from __alloc, releasable via free.
  • flag == <power-of-2> on WASM (8, 16, 32, …, 4096): heap block whose size identifies which bin to push it onto on free.
• refcount is initialised to 1 by __alloc (the single owner returned to the caller). Adjusted by __inc_ref and __free_recursive.
• shape is the number of pointer fields starting at slot 1. Used by __free_recursive to recurse into children. A shape == 0 block (boxed primitive, nullary constructor, string) has no child pointers; a Cons-shaped block has shape == 2; a Tuple3 has shape == 3; and so on.

String literals carry the same header in static data with flag = refcount = shape = 0, so CDrop on a binder that may hold either a literal or a heap string is uniformly safe.

The header lives at [Awsum.Codegen.LLVM](../src/Awsum/Codegen/LLVM.hs) and [Awsum.Codegen.WASM](../src/Awsum/Codegen/WASM.hs).

Runtime helpers

Four helpers are emitted once per program (gated on whether the program references them):

• __alloc(size, shape) — allocate a block.

  • LLVM: malloc(size + 12), write flag=1, refcount=1, shape, return user_ptr = raw + 12.
  • WASM: __alloc_shaped(size, shape) rounds size up to the next power of two (min 8), pops the matching bin if non-empty (reinitialising the header), otherwise bump-allocates and grows linear memory on demand. Bin head pointers live in linear memory at offsets 24 + (ctz(rounded) - 3) * 4 for size classes 8 through 4096. Bumping past memory.grow == -1 traps via unreachable.

• __free(p) — return a block.

  • LLVM: if flag == 1, call libc free(p - 12); otherwise no-op.
  • WASM: if flag == 0, no-op; if flag > 4096, leak (no matching bin); otherwise push the block onto bin[flag], storing the previous head as the next-pointer at block offset 8 (user_ptr - 4).

• __inc_ref(p) — increment the refcount at user_ptr - 8. No-op on literals (flag == 0).

• __free_recursive(p) — decrement the refcount. On reaching zero, read shape, push slots 1..shape-1 onto the global worklist (see below), iterate the outer loop with slot[shape] as the new p, and return the current block via __free. When the current cell does no cascading work (literal, refcount > 0, shape == 0) the helper pops the next pending pointer from the worklist; on empty it returns. System-stack footprint is O(1) regardless of cascade shape. Immutability makes the cell graph acyclic, so the cascade terminates.

  The worklist lives off the system stack — a heap-allocated pointer buffer, doubled on overflow (initial 16 entries), single-threaded global state shared across all __free_recursive calls. On LLVM, three module-level globals (@__free_worklist, @__free_worklist_top, @__free_worklist_cap) plus a @__free_worklist_push helper backed by realloc. On WASM, three WASM globals ($__wl_buf, $__wl_top, $__wl_cap) plus a $__free_worklist_push helper backed by __alloc_shaped (old buffers ≤ 4096 bytes return to a bin via __free; larger ones leak with total leak ≤ 2× current capacity because doubling halves each predecessor). top is 0 between every top-level __free_recursive call — the helper drains its own pushes before returning — so no state leaks across calls. Awsum is single-threaded and runtime helpers never call user code, so the global buffer is non-reentrant by construction.

The inc/dec discipline

Every cell follows a balanced +1 / -1 history:

• Allocation brings +1 (the owner returned by __alloc).
• Transfer brings +1 per new holder. A transfer position is any place a borrowed binder is stored into long-lived state — CCall arg, CCon field, CRow value, CContinue arg, CReuse field, CCase arm-binder extract. Codegen emits __inc_ref whenever the source expression resolves to a borrowed local or function parameter (see borrowedSource / emitIncIfCVar in Awsum.Codegen.LLVM) — except at a CContinue back-edge, where a binder that is also dropped there and forwarded linearly is moved into the next-iteration slot, eliding this inc (the back-edge move carve-out below). Fresh-allocation sources need no inc — they bring their own +1 from __alloc. This includes CCon, CCall, CIntLit, CString, and CVar references to top-level CValDefs (each such reference lowers to a call @v_name() whose body re-allocates a fresh cell).
• Built-in CCall uses callee-owns args: every built-in helper dec's its incoming pointers at the end via __free_recursive, and the caller adds the same inc-on-CVar rule that applies to user calls. The discipline is uniform between user and built-in calls.
• Drop brings -1. Drop placement is described next.

JVM, CLR, and JS do not participate in this discipline: the host GC tracks references and the codegen for those backends never emits inc.

Drop insertion

Awsum.Lifetime.insertDrops runs once after Awsum.Tco, annotating the Core IR with CDrop k n body nodes. The semantics is "evaluate body; after its value has been produced, dec n". Two classes of drop are emitted:

1. Parameter drop at every CContinue. Each parameter that is overwritten by the next loop iteration is wrapped in CDrop immediately before the CContinue. Codegen emits the dec after the next-iteration argument values are computed but before they are stored into the parameter slots, so the staged values are still readable when the dec fires.
2. Arm-binder drop at every CCase / CRowCase arm. Each pattern binder is wrapped in CDrop around the arm body. Codegen pairs this with an inc on the extracted slot at the binding site, so the matched cell's slots do not hold stale references after the dec cascade.

A third class of decs — for parameters that survive to a non-CContinue terminal in the function body — is handled directly by codegen rather than by inserting CDrop here. Outer-wrapping the whole body in a CDrop per parameter would shadow inner CContinue drops (the inner drop would see the parameter as already-dropped via outerDropped and skip emit). Codegen tracks parameters explicitly and dec's each one before the value-tail return, with a move-semantics carve-out: if the tail expression is a CVar p that names a parameter, __inc_ref is emitted on the result before the dec, so ownership is transferred to the caller instead of the cell being freed and the caller receiving a dangling pointer.

The same move semantics fires on the loop back-edge. At a CContinue, a pending binder — a parameter, a let, or a case-arm binder — that is forwarded as a bare borrowed CVar argument exactly once is moved into its destination parameter slot on LLVM and WASM: its existing reference is donated, so codegen elides both the forward __inc_ref and the paired CDrop free the uniform discipline would otherwise emit. The load-bearing extract-inc that protects an arm binder from its dying scrutinee's cascade stays — only the redundant inc/free pair is cut. Both preconditions are load-bearing: linearity, because one donated reference has exactly one destination (a binder forwarded to two slots keeps the ordinary inc-per-use plus single drop); and drop-set membership, because with no paired drop to cancel, skipping the inc would leak. This is the back-edge analogue of the value-tail move above. See transferMoves in Awsum.Codegen.LLVM and transferMovesW in Awsum.Codegen.WASM.Assemble.

Drop lowering per backend

• LLVM: CDrop _ n body lowers to call void @__free_recursive(ptr %n) after body's value is produced — except a binder linearly moved across a CContinue back-edge (above), whose free is elided along with its forward inc. See Awsum.Codegen.LLVM.
• WASM: same shape, calling $__free_recursive in WAT and the corresponding function index in the binary assembler. See Awsum.Codegen.WASM and Awsum.Codegen.WASM.Assemble.
• JVM: parameter drop becomes aconst_null; astore <slot>. Arm-binder drops are no-ops — case-binders live in block-scoped slots that the host GC reclaims when the arm exits. Operand-stack net effect per pair is zero, so staged CContinue arguments stay in order. See Awsum.Codegen.JVM.
• CLR: parameter drop becomes ldnull; starg.s <i>. Same shape and rationale as JVM. See Awsum.Codegen.CLR.
• JS: parameter drop becomes <param> = null;. Arm-binders are declared with const and cannot be reassigned; their slots die with the lexical scope. See Awsum.Codegen.JS.

Stack safety of the cascade

__free_recursive makes O(1) use of the system stack on every cascade shape: non-last children of cells with shape > 1 are pushed onto the global worklist (see the __free_recursive(p) entry above) and processed in the helper's own outer loop, instead of recursed via call __free_recursive. The previous implementation tail-jumped only on the last slot and called recursively on the rest; that required a 256 MiB stack reservation (-Wl,-stack_size,0x10000000 on POSIX, -W max-wasm-stack=268435456 on wasmtime) sized to the iteration count, which is wrong — stack size should be a function of the program, not of how many times its loops run. With the worklist the reservation is gone; platform-default stacks (typically 8 MiB on POSIX, 1 MiB inside wasmtime) cover the residual user-call graph already bounded by Awsum.StackSafety.

The worklist itself grows on the heap with each cascade's max in-flight frontier — a function of data shape, not iteration count.

Cell reuse

Awsum.Reuse.insertReuse runs after insertDrops and recognises the canonical Lean 4-style pattern of a scrut drop inside the arm of a linear case-scrutinee:

CCase (CVar n) [..., (tag_in, [v1..vk], CDrop _ n inner), ...]

where inner contains a CCon t fields with length fields == k (matching the arm's pattern arity). Such a CCon is rewritten to CReuse n t fields, and the outer CDrop n is stripped. The pass distributes into nested CCase / CRowCase arms — each arm independently rewrites if its path contains a scrut drop; arms without it keep their original allocation. Per arm at most one CCon is rewritten (there is only one cell to give back).

insertDrops produces the in-arm scrut drop in two places. A parameter is dropped at every CContinue (addContinueDrops) — the original producer, covering the TCO'd loop whose argument pack is rebuilt each iteration. A binder whose sole use is the scrutinee of an inner case on its scope's spine (a case every execution reaches — one only some paths reach keeps the scope wrap, or the bypassing paths would leak the binder) has its drop sunk into that case's arms instead of wrapping its scope (soleScrutineeUse / sinkScrutDrop — the dec still fires after the chosen arm's value, the same point the scope wrap expressed). The second producer is what makes the continuation cells of $scc$-merged CPS functions reusable: the merged loop's case on $args binds the K-cell $k, the inner case on $k rebuilds a same-arity K-cell inside the pack rebuild, and both cells die there.

The match is innermost-first (a constructor's fields are searched before the constructor itself): nested scrutinees' passes run before their enclosing case's, so an inner cell pairs with the inner reconstruction and leaves the enclosing cell to the enclosing scrut — with equal arities (a two-field pack carrying a two-field list cell, the reverse shape) the outermost-first order would let the inner pass steal the pack. The result is nested reuse, CReuse n_outer t [", CReuse n_inner t' […]]: a mirror/reverse-style hot loop rebuilds both its pack and its data cell in place and allocates nothing.

For a binder-target the refcount accounting balances with no new elisions: the binder enters the arm at rc = 2 (the parent cell's slot plus its extract-inc); the enclosing reuse's dec-old of that slot releases the parent's reference; the stripped sunk drop never decs — its +1 becomes the reference the new holder's slot stores (a CReuse result is a fresh source, stored without inc). Arms where the reuse does not fire keep the sunk drop and free the binder exactly where the scope wrap would have.

Every CReuse carries a ReuseMode — the uniqueness evidence the pass attaches by looking at the dying cell's constructor tag:

• ReuseUnique — the tag was minted at or above the pre-Scc nextFreshConTag floor, so the cell is an Scc argument pack or a Cps continuation: created and consumed entirely inside the compiler-generated loop, never stored into user data, never visible to user code. No other holder can exist; every backend mutates in place unconditionally.
• ReuseGuarded — a user-visible cell (a list node, a tree node, an IO step). The local drop only proves the binder's reference dies; the caller may retain the structure — Awsum is pure, so let ys = reverse xs keeps xs readable, and an unconditional in-place rewrite would corrupt it (observed: four backends printing 2e against LLVM's 22 on an eight-line program, pinned by memory_reuse-shared-retained). LLVM and WASM mutate under a runtime uniqueness check with copy-on-write; the managed backends have no refcount header to check and lower the node as the allocation it replaced.

On LLVM and WASM, the guarded lowering of CReuse n t fields is in-place mutation under the refcount check (a ReuseUnique cell takes the in-place sequence with no branch):

• refcount == 1 (uniquely owned): write t into slot 0 and the field values into slots 1..k of the existing cell at n. For each slot, dec the old value before overwriting; for each new CVar field source, inc; for each fresh source (CCon/CCall/CIntLit/CString) no inc (it brings its own +1). The cell's own refcount stays at 1. The pre-existing flag and shape header are left intact.

  Two refcount-bookkeeping elisions fire on this path:

  • Self-move. When a new field is CVar v and v is the arm-pattern binder at the same slot, the slot's stored pointer is already what we'd write — dec-old, inc-new, and store all cancel and are skipped.
  • Permutation-move. When a new field is CVar v where v is an arm-pattern binder at some other slot of the same scrut, the cell still owns v after the rewrite (just at a different slot). Codegen skips the dec-old of v's old slot and the inc-new of its new slot; the store at the new slot is still emitted. The arm-binder's own inc-on-extract and CDrop also vanish when v's only use is this one CReuse field (the linearity precondition is checked by Awsum.Lifetime.elidableArmBinders).

• refcount > 1 (shared with another live holder): copy-on-write. Allocate a fresh cell of the right shape, write t and the fields into it, __free_recursive on n (which dec's its refcount, leaving the other holders intact). Every CVar field gets its own __inc_ref here unconditionally — the fresh cell takes its own reference, and the old cell stays alive at rc-1 still holding its own references; the elisions above apply only to the in-place path.

A field that itself contains a CReuse (the nested-reuse shape) is not pre-evaluated with the other fields on LLVM — it evaluates inside each branch, and only that ordering makes the nested uniqueness check meaningful. On the in-place path the enclosing cell's dec-old has already released the parent-slot reference to the nested target, so its rc is 1 exactly when nothing else holds it; on the copy path no dec has happened, the target still carries the parent-slot reference on top of its extract-inc, the nested check fails, and the nested reuse copies too — leaving the shared original intact. The nested target's rc is the same number in both worlds (the sharing lives one level up, on the enclosing cell), so pre-evaluating would mutate a cell the copy path still needs.

On JVM, CLR, and JS, a ReuseUnique cell lowers to plain field-overwrite of the existing array — aastore on JVM, stelem.ref on CLR, comma-expression (n[0] = tag, n[1] = f₁, …, n) on JS. There is no refcount header on managed-runtime heap blocks, so no runtime branch is possible — which is exactly why a ReuseGuarded cell lowers there as the plain allocation it replaced (the host GC reclaims the dead original).

Pipeline placement

… → Awsum.Tco → Awsum.Lifetime.insertDrops → Awsum.Reuse.insertReuse → Codegen

Both passes run inside elaborateLowerProgram (Awsum.ElaborateLower), after all stack-safety-shaping passes have stabilised the IR. Drop insertion runs first so cell reuse can rely on its drop placement as a proxy for the linear-use precondition.