Fixed

Fixed Perceus Reference Counting

Status: Draft v0.1 Specifies: the reference-counting strategy, RC-insertion algorithm, reuse analysis (FBIP), drop specialization, borrowing inference, and effect-handler memory management for Fixed v0.4.4 source. Last revised: 2026-04-30

1. Scope

This document specifies how the compiler manages heap memory for runtime values: when reference counts are incremented or decremented, when memory is reused in place, when allocations and frees are elided, and how all of the above interacts with QTT quantities, capabilities, and effects. Concretely:

It does not specify:

2. Dependencies and theoretical basis

Theoretical basis:

3. The Perceus model

3.1 Heap-object layout (Rule PR3.1)

Every heap-allocated runtime value carries a header:

{
    rc: i64,            // refcount; high bit reserved for atomic-mode flag
    tag: i8,            // variant discriminator for sum types; 0 for product types
    pad: [N x i8],      // padding to natural alignment
    payload: <variant fields>
}

Stack-allocated and quantity-0 values have no header. Stack allocation occurs when:

Rule PR3.1.a (SCC × quantity-1 priority — resolves C6). When a value's data type is a member of a non-singleton SCC of mutually recursive data types (spec/type_system.md §7.5, this doc §10), stack allocation is gated on whether the value escapes the current frame:

  1. If the value's lifetime is bounded by the current call frame (no return, no closure capture, no escaping reference) and its quantity is 1 and its serialized size fits the stack budget, stack-allocate. The compiler may co-allocate other quantity-1 SCC members in the same frame as a small ad-hoc arena.
  2. If the value escapes (returned, captured, or stored in a heap-resident outer value), heap-allocate per §10.1's SCC unified layout regardless of quantity.

The conservative default for v0.4.5 is rule (2) — heap-allocate any SCC member — until escape analysis is implemented in Phase 4. Rule (1) is the target behavior; implementations may opt in once they can soundly identify non-escaping quantity-1 SCC values.

Single-member SCCs (a self-recursive data T: whose only recursive member is itself) are not affected by this rule — the size budget alone gates their stack-allocation per the bullets above.

Rationale: heap-allocating quantity-1 SCC values "just because they're recursive" is a real performance regression for small bounded trees. The escape-analysis gate keeps the soundness story (escaping references must be heap-tracked) while admitting the optimization where it pays off.

3.2 dup and drop primitives (Rule PR3.2)

The IR has two RC primitives:

dup and drop are emitted by the compiler at points determined by the algorithm in §5; they are not user-visible.

3.3 Last-use semantics (Rule PR3.3)

The Perceus invariant: for every binding x introduced into a scope at program point P, the compiler emits exactly the dup/drop pairs needed to balance refcount changes between P and the end of x's lifetime. The owning scope is responsible for dropping; transferring ownership (e.g., passing x to a function as a non-borrowed argument) transfers the drop obligation.

The "last use" of a binding is the last program point in source/IR order where the binding is referenced. The compiler emits drop immediately after the last use (or at branch joins, per §5).

3.4 Quantity ω is the standard case (Rule PR3.4)

Bindings with QTT quantity ω (spec/quantities.md §3) carry standard Perceus RC. They have headers, dup/drop pairs, and full reuse-analysis treatment. Most user code lives here.

3.5 Quantity 1 is consume (Rule PR3.5)

A quantity-1 binding has no dup and no refcount-aware drop. Its single use is a consume — the value is moved (not copied) at the use site, and the binding is dead afterward. If the value's representation is stack-allocated, consume is a no-op (the stack frame holds it); if heap-allocated (a quantity-1 binding may still be on the heap due to size), consume transfers ownership.

This is what makes FBIP guaranteed for quantity-1 bindings: at the consume site, the memory is unique to this code path.

4. Quantity-driven simplification

Fixed's per-quantity strategy collapses three runtime treatments:

Quantity Allocation RC ops Reuse
0 None None N/A — value doesn't exist at runtime.
1 Stack or heap (size-driven) No dup; no refcount drop. consume at use site. Guaranteed FBIP — last use is the only use.
ω Heap with refcount header dup at share, drop at last use. Conditional FBIP — at runtime, reuse if rc == 1.

This integration is the main value of pairing QTT with Perceus: only ω-quantity values incur the full RC overhead. The compiler statically proves quantity-0 erasure (Rule Q6.1) and quantity-1 linearity (Rule Q7.1), so those bindings skip RC entirely.

For comparison, a system without QTT (e.g., Koka pre-Perceus integration) treats every value as ω and emits dup/drop for everything, relying on optimizer passes to eliminate redundant pairs. Fixed's QTT pre-pass eliminates them statically.

5. RC insertion algorithm

The compiler implements the Reinking et al. (2021) algorithm with the QTT-driven simplifications above. This section describes the algorithm operationally.

5.1 Input form (Rule PR5.1)

The Perceus pass runs after match-desugaring (spec/pattern_matching.md §8) and consumes the resulting decision tree plus full quantity annotations from the prior pass (spec/quantities.md §4).

Input invariants:

5.2 A-normal form (Rule PR5.2)

The pass first converts the IR to A-normal form (ANF): every non-trivial subexpression is named via let. This makes every argument position a simple variable reference, simplifying live-set tracking.

// Before ANF:
g(f(x), h(x))

// After ANF:
let v1 = f(x)
let v2 = h(x)
g(v1, v2)

After ANF, dup/drop placement reduces to "at every binding's last use, drop; at every share point, dup."

5.3 Live-set computation (Rule PR5.3)

For each program point P, the live set is the set of bindings whose values may still be referenced after P. Computation is a backward dataflow:

  1. At a function's exit point: live set = ∅.
  2. At any other point P: live(P) = (live(successor) ∪ uses(P)) − defs(P).
  3. At branch joins: live(P) = ⋃ live(successor_i) for each branch successor.

The pass uses live-set deltas to insert RC ops:

For quantity-0 bindings: skip — they do not exist at runtime. For quantity-1 bindings: skip dup; rely on the linearity check (Rule Q7.1) to ensure exactly one use; emit consume at that use. For quantity-ω bindings: standard algorithm.

5.4 Branching (Rule PR5.4)

At a branch point (if/match decision tree), for each binding x in the live set:

This ensures every branch's exit has the same "RC budget" — refcount differences are reconciled at branch entry, not exit.

5.5 Function calls (Rule PR5.5)

When a function call site g(a, b, ...) is reached:

5.6 Closures (Rule PR5.6)

A closure capturing a binding y from the enclosing scope:

For quantity-1 captures: the closure carries a unique reference; it cannot be invoked twice (per Rule Q7.1). The closure itself must be quantity 1 if any of its captures is quantity 1.

6. Reuse analysis (FBIP)

FBIP — Functional But In Place — converts allocation-then-free into reuse-of-the-same-memory. This is Perceus's signature optimization.

6.1 Reuse tokens (Rule PR6.1)

When the compiler sees drop x immediately preceding a constructor Cons(args...) of the same heap shape as x, it generates a reuse token: a pointer to x's memory that can be passed to Cons to reuse rather than allocate.

// Original:
match list:
    List.Cons(h, t) => List.Cons(transform(h), recur(t))   // allocates new Cons; drops old
    List.Nil => List.Nil

// After Perceus + reuse:
match list:
    List.Cons(h, t):                                       // matches; binds h, t
        let token = drop_to_reuse(list)                    // reuse-or-drop list
        List.Cons.from_token(token, transform(h), recur(t))  // reuses list's memory
    List.Nil => List.Nil

The runtime check at drop_to_reuse: if list.rc == 1, return the memory pointer; else drop (decrement) and allocate fresh.

6.2 Reuse fingerprints (Rule PR6.2)

Two heap shapes match for reuse iff they have:

The compiler computes a reuse fingerprint for each heap-allocated variant and matches by fingerprint, not by nominal type. This allows reuse across different variants of the same data type (e.g., Cons(h, t) reusing memory from another Cons whose payload differs in element type).

6.3 Quantity-driven reuse (Rule PR6.3)

For quantity-1 bindings, reuse is unconditional — linearity guarantees rc == 1 (the static linearity check eliminates the runtime test). The compiler emits direct memory reuse without the conditional branch.

For quantity-ω bindings, reuse is conditional — the runtime check rc == 1 decides; if false, the new constructor allocates fresh.

6.4 Cross-arm reuse

A match arm may reuse the matched value's memory iff the arm's body constructs a value of a matching fingerprint. If the arm doesn't, the compiler still emits drop for the matched value at arm entry.

7. Drop specialization

7.1 Per-type drop functions (Rule PR7.1)

For each data type, the compiler synthesizes a drop function drop_T(x: T) -> ():

drop_T is emitted as an LLVM function and called by the runtime drop primitive (Rule PR3.2). The compiler may inline it at known-type call sites.

7.2 Inline drops (Rule PR7.2)

When drop x is emitted at a static call site where x's type is fully known, the compiler inlines the drop sequence rather than calling drop_T:

// drop x where x: List of i64, x is List.Cons:
//   inlined sequence:
let h = x.head
let t = x.tail
drop_int(h)         // primitive drop — no-op for i64
drop_T_list(t)      // recursive call (tail call eligible)
free(x)

For unknown-type drops (e.g., behind a capability bound), the runtime dispatch via vtable.

7.3 Recursive drops as tail calls (Rule PR7.3)

A drop function that drops a recursive field as its last operation is a tail call:

fn drop_list(x: List of A) -> () =
    match x:
        List.Nil => free(x)
        List.Cons(h, t) =>
            let t_local = x.tail   // hoist the tail before x is freed
            drop(h)                // drop the head's reference
            free(x)                // free the Cons cell itself
            drop_list(t_local)     // tail-call to drop the rest; constant stack

Field hoisting (let t_local = x.tail) precedes free(x) so the recursive descent retains a valid tail reference after the cell is released. The tail-call to drop_list bounds drop-stack usage even for arbitrarily long lists; the compiler must guarantee tail-call optimization for compiler-emitted drop functions.

8. Borrowing (inferred)

8.1 Borrow analysis (Rule PR8.1)

A function parameter p is borrowed iff:

The compiler runs this check as a fixed-point analysis on the call graph: a parameter is borrowed if all its uses fit the above pattern. Mutually recursive functions are analyzed together.

8.2 Borrow ABI (Rule PR8.2)

Borrowed parameters use a different calling convention:

This eliminates a dup/drop pair per call where borrowing applies. Common cases: predicates (is_empty(list)), accessors (size_of(list)), pure inspectors that don't propagate the value.

8.3 Borrow inference is an optimization

Borrowing is an internal compiler optimization. There is no surface syntax for borrow in v0.4.4 (deferred — see OQ-PR1). The compiler conservatively treats parameters as owned (with full dup/drop) when borrow analysis is unable to prove the borrowed property.

9. Effect handler memory

9.1 Continuation memory (Rule PR9.1)

Per spec/effects.md §7.4, non-abortive effect operations capture the continuation up to the handler frame. Each captured continuation is a heap object with:

The continuation's quantity is 1 by construction (Rule Q5.11) — resume consumes the continuation exactly once per code path. Therefore:

9.2 Linear effect handlers (Rule PR9.2)

A linear effect (spec/effects.md §3.5) imposes a usage budget of ≤ 1 op per code path. The handler installs a single permission per nesting; once the op is intercepted, the permission is consumed.

Memory implication: the handler-frame for a linear effect has lifetime bounded by the SUBJECT's evaluation. After the handler exits, the frame is freed (no residual continuation references can outlive the handler since linearity prevents capturing an unused permission).

Quantity-1 captures across linear arm bodies (Rule PR9.2.a). Per spec/quantities.md Rule Q7.4, a linear-effect arm body has quantity 1 (the at-most-once invariant of the effect propagates to the arm). Quantity-1 outer bindings captured into a linear arm body therefore generate no dup at the capture site — the binding's last-use is consumed by the arm exactly once across all paths reaching the handler. This is consistent with Rule PR3.5 (quantity-1 → no RC overhead) and Rule PR3.6 (no dup/drop for quantity-1 bindings).

Non-linear arm bodies (Console, FileSystem, etc.) remain quantity-ω closures per Rule Q5.7; capturing a quantity-1 outer binding into one is a Rule Q7.1 violation rejected at type-check time, never reaching Perceus.

Both Rule Q7.4 and Rule PR9.2.a are contingent on OQ-Q5 (spec/quantities.md). Implementations should gate them behind the same flag that gates linear effect per spec/effects.md §3.5.

9.3 Tail-resume optimization (Rule PR9.3)

Per spec/effects.md §7.5, when an arm body's resume(expr) is in tail position, the compiler emits a tail-resume that avoids the full continuation roundtrip. From a memory perspective:

This is why tail-resume is the common case in practice (Console.print_line(s) => emit(s); resume(())) and is important for performance.

10. Mutually recursive data — co-allocation

Per spec/type_system.md §7.5, mutually recursive data types form an SCC and are co-allocated. From a Perceus perspective:

10.1 Shared header layout (Rule PR10.1)

All members of an SCC share a unified header layout (a tag space wide enough to discriminate every variant of every member). Drop functions for SCC members may share fingerprints (per Rule PR6.2), enabling reuse across SCC members:

// Tree and Node form an SCC:
data Tree:
    Branch(node: Node)
    Leaf

data Node:
    N(tree: Tree, value: i64)

// Reuse: when dropping a Tree.Branch and constructing a new Node.N of the
// same fingerprint, the compiler may reuse the Branch's memory for the new N.

10.2 SCC drop ordering (Rule PR10.2)

The drop functions for SCC members are emitted as a mutually recursive group. Tail-call optimization (Rule PR7.3) extends across the group: a Tree drop calling a Node drop calling a Tree drop... is a single mutually-recursive tail-call chain, with stack-bounded execution.

11. Phase placement

The Perceus pass runs:

Runs after Provides
Quantity inference (spec/quantities.md §4) Per-binding quantities (drives §4 simplification)
Representation selection (spec/type_system.md §6.5) Concrete representations (drives §3.1 and §6.2 fingerprints)
Match desugaring (spec/pattern_matching.md §8) Decision-tree IR (input to §5)
Property verification (spec/properties.md §7) Verified facts (informs reuse: e.g., non_empty implies tail is non-null)
Runs before Consumes
Code generation (LLVM IR emission) Final IR with all dup, drop, reuse_token, consume annotations

The pass is a Recheck-style phase (docs/references/scala3-compiler-reference.md §5.4) over the typed/desugared/quantity-annotated AST. It does not change types or values — it inserts RC operations and reuse tokens. Its output is a valid Fixed IR (with RC ops) ready for codegen.

12. Worked examples

12.1 Simple let-binding (quantity ω)

fn count_pairs(x: i64, y: i64) -> i64 =
    let pair = make_pair(x, y)        // allocates Pair on heap; pair has rc=1
    pair.first + pair.second           // two uses of `pair`; emits dup before first use

After Perceus:

fn count_pairs(x: i64, y: i64) -> i64 =
    let pair = make_pair(x, y)        // alloc; rc=1
    dup(pair)                          // rc=2
    let r = pair.first + pair.second  // both uses consume one ref; rc=0; free
    drop(pair)                         // already rc=0 from consumes — actually, this drop pairs with the dup
    r

Or, equivalently after the optimizer notices the dup/drop pair: the dup is unnecessary because both reads borrow rather than consume — borrow analysis (§8) eliminates the dup/drop pair entirely.

12.2 Match with reuse (FBIP)

fn map(list: List of A, f: A -> B) -> List of B =
    match list:
        List.Cons(h, t) => List.Cons(f(h), map(t, f))
        List.Nil => List.Nil

After Perceus + reuse:

fn map(list: List of A, f: A -> B) -> List of B =
    match list:
        List.Cons(h, t):
            let token = drop_to_reuse(list)            // releases or reuses list's memory
            List.Cons.from_token(token, f(h), map(t, f))
        List.Nil => List.Nil

Effect: when list.rc == 1 at runtime, the new Cons reuses list's memory — no allocation, no free. The list is transformed in place. This is FBIP.

12.3 Quantity-1 (linear) effect handler

linear effect Lock:
    fn release -> ()

fn critical_section(work: () -> () with Lock) -> () =
    work()                            // Lock effect not yet released
    Lock.release                       // exactly one usage of Lock per Rule E3.5.a

After Perceus:

No RC traffic on the lock or its continuation.

13. Open questions

14. Cross-references

Document Relationship
spec/syntax_grammar.ebnf No direct dependency — Perceus runs on lowered IR
spec/type_system.md §6.5 (representation selection) drives §3.1 layouts; §7.5 (SCC) drives §10
spec/quantities.md Rule Q5.X and Q6.1 / Q7.X drive §4 simplification; Q5.11 drives §9.1
spec/effects.md §6 / §7 drive §9; Rule E3.5 drives §9.2; §7.5 (tail-resume) drives §9.3
spec/pattern_matching.md §8 (decision-tree compilation) is the immediate input to §5
spec/properties.md Verified props inform reuse decisions (e.g., bounds elision, non_empty discharge)
docs/references/scala3-compiler-reference.md Recheck pattern (§5.4) for the pass's structure
docs/plans/implementation-plan.md Phase 4 deliverable: perceus/PerceusInserter.scala