Wado

WEP: NIR Skeleton Arena (Layer 1)

Context

Worklist-Driven NIR Rewrite Engine fixed the substrate as two layers and put Layer 1 — the effect skeleton — first, as the NIR representation itself. This WEP specifies Layer 1's data structures: the NodeId spaces, how parent and use edges are stored and kept coherent under rewrites, and the seam left for Layer 2. The worklist engine and its rule / fairness / conflict policy stay in the follow-up engine WEP; this WEP only builds the substrate the engine stands on.

Today a function body is an owned tree: NirFunction.body: Option<NirBlock>, NirBlock { stmts: Vec<NirStmt> }, expressions nested through Box<NirExpr> (nir.rs). Two properties the engine needs are absent:

CSE already pays for the missing structural handle: it hand-rolls a CseKey over three node kinds (cse.rs) because NIR offers nothing better.

Decision

A function body becomes a per-function arena, Body, which is the canonical post-lower form (not a structure built on the side — see Migration). Closure __call methods and non-trivial global initializers are bodies too and each own a Body.

Id spaces

Typed ids, one arena (a PrimaryMap-style Vec) per category:

Typed rather than one uniform id so rule signatures read fn(&mut Body, ExprId) and the compiler rejects passing a statement where an expression is expected; the large majority of rules are expr-typed. Records that are never independent rewrite targets — match arms, struct fields, call args — are not id-bearing. They live inline in their parent node as small structs holding child ids (ArmData { pattern: PatId, guard: Option<ExprId>, body: ExprId, span }). The parent of an arm's body is the enclosing Match expr; arms / fields / args are transparent to the parent map.

Node payloads

ExprNode  { kind: ExprKind, type_id: TypeId, span: Span }
StmtNode  { kind: StmtKind, span: Span }
BlockNode { stmts: Vec<StmtId>, span: Span }
PatNode   { kind: PatKind, span: Span }

ExprKind mirrors NirExprKind with every child reference rewritten: Box<NirExpr> → ExprId, Vec<NirExpr> → Vec<ExprId>, NirBlock → BlockId, CallArg { expr, is_mut } → { expr: ExprId, is_mut }. It is a parallel enum, following the repo's TIR / NIR / WIR "separate enums" convention. Making NirExprKind<R> generic over the child reference type was considered and rejected: the node wrapper, and the placement of type_id / span, differ between tree and arena, so a generic over the leaf reference would not actually unify the two forms.

type_id and span stay per node. span feeds diagnostics, optimizer remarks, and DWARF, and is part of skeleton identity — Layer 2 is the span-free layer, not this one.

Variable-arity children are inline Vec<ExprId> / Vec<StmtId> to start. A ListPool (compact, splice-cheap child lists — the Cranelift EntityList shape) is the documented optimization if Vec churn shows up in profiles; it changes the storage, not the node-facing API.

Parent edges

parent: NodeRef -> Option<NodeRef>, stored as one Vec<Option<NodeRef>> per category, indexed by the raw id. Maintained incrementally by the edit API, never recomputed: every operation that points a slot at a child also sets that child's parent. Parent is the nearest id-bearing ancestor; the body root's parent is None. This is the edge the worklist follows to re-enqueue a node's context after it is rewritten.

Use index

Locals are function-scoped (Local { index }), so the use index lives on the Body:

local_uses: index -> { def: Option<StmtId>, reads: Vec<ExprId>, writes: Vec<ExprId> }

reads are Local expr nodes; writes are the place forms — Assign { target: Local }, Local.field = …, &local / &mut local. def is the binding Let / LetDestructure where one exists (params have none). Maintained incrementally: allocating or freeing a node that mentions a local updates the index. The engine reads it to re-enqueue a local's uses when its definition changes — copy propagation, const-fold through a Let, store-to-load forwarding.

Function-level alias facts that gate soundness for many passes — address_taken_locals, stores_aliased_locals, and the locals: Vec<NirLocal> table — travel on Body beside the arena, mirrored from NirFunction.

Edit API and the engine seam

Rules do not touch the category Vecs directly; they go through an edit API that keeps the parent and use indices coherent and records what to re-enqueue:

Stable ids under in-place replacement is exactly what the tree cannot give: the worklist holds NodeRefs, a rule rewrites in place, and the handle stays valid. Every edit enqueues the affected parent[...] and, when a local's def / use set changed, the neighbouring def / use nodes. The queue itself, fairness, and the rule-conflict policy are the engine WEP's concern, not this one.

Nodes are not freed mid-run. Liveness is reachability from root; an optional compaction pass (or the arena → tree lowering during migration) reclaims orphaned subtrees, consistent with DCE being a separate stage around the engine.

Seam for Layer 2

Layer 1 leaves pure expressions as ordinary ExprNodes. When Layer 2 (the hash-consed value e-graph) is built, a referentially-transparent ExprId — classified by optimize/mod_ref.rs, not by node kind — is represented by a value-graph id, and skeleton operands widen to Operand = Skel(ExprId) | Value(ValueId). Nothing in Layer 1's id spaces, parent map, or use index has to change shape for that; the seam is the operand type, introduced later. This WEP does not build it, and whether it is built at all is re-decided after the engine lands (see the engine WEP's sequencing).

Migration

The arena is the canonical representation; the converters below are temporary scaffolding, not a permanent boundary. This is the distinction the engine WEP drew when it rejected a conversion boundary: that design kept the tree as the representation and paid tree ↔ arena translation on every engine run forever. Here the converters exist only to land the arena incrementally and are deleted once the producer and consumer speak arena.

Each phase keeps the full e2e suite and golden WIR fixtures green (tests/generated/fixtures/*.wir.wado), satisfying the engine WEP's "codegen must not regress" requirement.

Phase 1 implementation notes

Decisions pinned before coding, so Phase 1 is mechanical:

Consequences

Benefits

Trade-offs

See also