WEP: NIR Interpreter (niri)

Context

The optimizer reduces what the source made constant to the value it denotes. Three mechanisms share that job.

• The hash-cons pool folds pure scalar arithmetic at intern time, holding the invariant that no node in the pool is a foldable constant.
• The ValueGraph carries everything flow-sensitive: reaching definitions, branch merges, loop and heap-write invalidation, field store-to-load seeding.
• niri runs bodies. A callee's body against constant arguments, or a self-contained region against an environment the walker can prove.

niri is the compile-time executor, and its unit of work is a frame with a heap of its own. It is not the engine that answers what a NIR expression evaluates to; the pool answers that for arithmetic. Its lattice layer re-derives scalar folding over skeleton expressions. That is what remains of an older framing, and it shrinks to a pool bridge as pure node kinds leave the skeleton.

The prize is compile-time string formatting. An interpolation that does not fold costs a buffer allocation, a Formatter, and a digit-count and division loop on every evaluation, and it keeps the formatting code alive in the binary. Every ${} over constants, every to_string() on a literal and every constant assert message pays that. Measured at -Os on a program that prints one interpolation, against the same program printing the literal, which costs 1 997 bytes:

The first two rows fold to the literal. char, {:x} and floats do not. The roadmap is ordered against a census of the corpus rather than against this document's guesses.

Decision

niri is a partial evaluator: it reduces what it can and leaves a residual otherwise. Reduction is monotone and idempotent, and the optimizer's fixed-point loop is the only fixed point; niri does not iterate internally. Each extension keeps the engine's work bounded in the size of what it is asked about. Watch for a rule whose cost is quadratic in body size, or that rebuilds a large value on every query.

Where the line falls

The pool folds pure values. The ValueGraph carries flow. niri executes bodies.

The boundary against the ValueGraph is load-bearing: niri once carried its own per-local field map, and that map was retired once the ValueGraph covered the same ground. A proposal to teach niri about control flow between statements is a sign the fact belongs on the other side of the line.

The line does not forbid a store over the values the engine itself built. Inside a frame niri executes statements in order, so a value the frame built, which nothing outside it reaches, can be written through and read back. The program's heap stays the ValueGraph's; the engine's own is the engine's.

Effects are the purity gate

A function admitted for compile-time evaluation is one the effect system called pure. A bug there lets an impure function run at compile time, which is the same trust already placed in effect checking elsewhere.

Determinism

• A NaN's bit pattern is host-defined, so NaN-producing arithmetic folds to the canonical NaN (WEP: Behavior Classes).
• v128 and relaxed-SIMD have host-defined corner cases; SIMD CTFE is deferred to a later WEP.
• Integer wrapping matches Wasm. Division by zero and a signed MIN / -1 trap at every width, so they are left unfolded and the runtime trap survives. A signed MIN % -1 folds to 0.
• Float zero carries no sign through a fold: -0.0 and +0.0 are equal, so if cond { -0.0 } else { 0.0 } collapses to one of the two. A caller needing bit-precise zeros should get a per-operation equality predicate rather than a globally weakened fold.

What the engine evaluates

Values: integer, float, bool and char scalars with their operators and casts; structs and tuples whose every field is constant, and the field reads projecting back out of one; enums, whose discriminant is the whole value, and variants, which carry a case and its payload. The lattice has three states: unevaluated, constant, non-constant. So an unreachable branch contributes nothing and a trapping arm does not contaminate a fold. An aggregate leaves the engine as the literal tree the lower phase would have emitted for it, where the node it replaces yields an object nothing else reaches.

Bindings: immutable locals and globals whose initializer is constant, plus a global's separately known fields, such as a sequence global's length; and a global whose value is not in its slot but in the assignment that fills it, which is what an extracted initializer and body globalization leave behind. Nothing is read off a local or global something writes through, since global without mut forbids reassignment, not in-place mutation. A borrow denotes its referent, whether the binding is mutable or not: what makes an alias safe is that nothing displaces it, which holds of a let mut nothing reassigns. Which locals carry one is decided once per body over the whole arena, so a read folds through a binding an in-place rewrite displaced, and an index more than one binder names carries nothing.

Control flow: a constant if condition collapses to the chosen arm, and a side-effect-free condition whose arms denote the same constant collapses to it. A constant match scrutinee selects the first arm that provably matches. A provably exhaustive match whose arms all denote one constant collapses to it, since exhaustiveness is what keeps the implicit no-match trap alive. Patterns decided: wildcard, binding, integer / bool / char literal, range, or-patterns, constant-valued, struct, and exact-arity tuple.

Calls: a free call runs at compile time when its arguments are all constant and its callee is pure, non-async and monomorphic. The body executes statement by statement, so let sequences, assignments, decided branches, early returns, labeled blocks and loops all reach a value; a loop needs no constant trip count, since the work budget bounds it. A statement counts as executed only when everything it evaluates lands on a constant, so an unfolded call, a global write or a would-be trap leaves work undone and stepping past it would drop it. A result that may carry the caller's storage is withheld, but the writes still land. A unit-returning call runs for its writes, and a &mut argument is written back on return.

Sequences: the array backing a String or a List is a value, built from a byte-string literal or a fully-constant array literal, up to a maximum length past which building one costs more than any fold it enables. A write goes into the value where it lies rather than rebuilding the container around it, so filling a sequence is not quadratic in its length, and the backing is shared until something writes it.

Regions

A block is self-contained when it builds its value in locals of its own, reads and writes only those, and yields the result. Such a block runs as a frame the engine starts from scratch, and that is what folds a constant string template to the literal the source could have written.

Self-containment is decided before the run, since the run copies the enclosing body while the checks only walk the block. That costs one thing: a mention on a statically dead path counts, because no scan can tell it from a live one. An outer local the region only reads is seeded from the walker's environment when it is constant there. A write position refuses the region, and so does a scalar under a reference the program can write through: seeding one would put a value where the program holds an alias. A shared reference is not one of those, since nothing writes through it.

Two shapes are not regions, and both look like one.

• A block that leaves nothing on the Wasm stack. Unit is the inlined statement call, whose result stands where the program expects none. Never is the else of a let ... else { panic("…") }, which builds a constant message and then diverges. Neither has a value to fold to.
• The { G = <const>; G } pair constant-object globalization leaves where it names a constant at a use site. Folding it writes the literal back over the naming construct and undoes the sharing globalization arranged.

A region that contains such a store can still fold. The condition is that every mention of the global in the package is one half of such a pair. Folding the region then deletes the store and the only read it serves together, so no read is left depending on a store that went away. A count of stores would not do: inlining copies the pair, so two sites are as safe as one, while a global with a single store and a distant read is not safe at all. The check lives in niri rather than in the globalization pass, which cannot know whether the region around its store will fold.

Fold the region, not the call

A region constructs its own buffer, so every value inside it is concrete, and folding it claims nothing beyond one concrete evaluation. The call-level fold claims more: that the callee appends the same bytes to every buffer. It rewrites one fmt over a constant into push_str(<literal>), which is what a template mixing constant and runtime interpolations needs. That is a separate mechanism with a separate trust story, so it is staged after the region fold rather than under it.

Where that claim is needed, it comes from #[compiler_item], as it already does for push_str. Mark Formatter's write primitives, not Display::fmt: marking the trait would extend the trust to every user-written impl, where nothing is checkable. A marked primitive declares a region append: everything it does to the buffer happens at or above the length the buffer had on entry, and what lies below is neither read nor moved. That covers the stdlib's three formatting idioms (prepare_int_write, mark / apply_padding, fpfmt's reserving writers) unchanged, where a strictly-append contract would not. What a particular fmt body does is then derived: run it against a buffer the engine built, and admit the result when every buffer access went through a marked primitive or landed inside a region one just returned.

How a missed fold is found

There are three instruments, and the roadmap is ordered by what they count rather than by what looks important.

• A remark, over the remarks infrastructure, names a block that computes a constant at run time and what stopped it: the calls that survived inside it, or the fact that refused it as a frame. It fires from the final IR, never from a refusal a pass recorded, so it retires itself as the fold reaches each shape.
• WADO_TRACE=ctfe_call names what each declined call wanted that the frame could not give, ctfe_stmt the statement a frame abandoned at, and region_seed every refusal along the fold path, under the function it walked. The remark reports the region, the traces the call and the statement inside it.
• mise run report-const-regions counts the remarks over the benchmark and wasm-size corpora and the Wado packages.

What the remark names is a call on the region's own path. A call under a cold_path marker is not one: push carries grow behind its capacity check, so a region filling a pre-sized container would name a call it never reaches and bury the one it does. A remark that names nothing is itself an answer: the fold is waiting on a value the engine cannot represent, not on a body it cannot run. That is where the statement trace takes over.

A count is worth nothing until something independent agrees with it. The formatting work is measured in bytes as well, which is what a census miscount cannot reach.

Roadmap

The census counts 1 041 surviving regions across 9 of 22 files:

Two Gale-generated files hold 976 of them. That concentration is not a Gale fact: what generated code does is call the same missing capability often.

The largest row is also the least specific. A region naming no call is waiting on a value the engine cannot represent rather than a body it cannot run. It says which instrument to reach for next, not which capability is missing, so only ctfe_stmt turns those 753 into work.

1. The aggregate exit

The engine represented an aggregate all along and had nowhere to put it, a String's backing being the one shape it could write back. The exit gave it one, and the recount says which half of the census that was: the silent row fell 900 → 753 and every named callee stayed where it was. So the four List<T> builders the census names — push_encoded_ranges (34), union_char_ranges (4), binary_property_ranges (4), general_category_ranges (2) — were never waiting on the write-back. They are calls the engine still declines to run, which is stages 2 and 3.

What it writes

commit_fold is where a folded value becomes IR. A scalar promotes to a pooled operand; everything else goes to a walk of the value against its type, emitting the literal node NIR already has for each shape.

wir_build lowers all five node forms already, and ArrayLiteral was added for a consumer of exactly this kind.

Field order is load-bearing: wir_build lowers a struct literal's fields positionally, and SROA asserts their indices cover 0..N once. So the writer emits in field_index order and refuses a value whose fields do not, which the lattice's reader makes unreachable — a NIR aggregate literal lists every field.

The engine has no shape source

Reading a literal into a value drops what writing one back needs. A StructLiteral field carries a name, a VariantConstruct a case index, and a pooled scalar operand the TypeId extraction reads its width from. Value keys a field by index, a case by name, and a scalar by PrimitiveType, which cannot name the enum, flags or newtype a field is declared as. Guessing a type is not a lost fold but a wrong one: wir_build resolves a tuple literal's struct type from its element types.

NirPackage's structs and variants hold the names, the case indices and the per-instance field types, and are where wir_build reads them. The exit takes the same information as a TypeId → fields index, built once per pass and carried on ProgramFacts, where an absent fact already costs folds rather than correctness. A tuple needs none of it: its element types are its own type_args.

The writer answers whether it changed anything

Recognizing a literal tree does not answer "is this already the literal the rewrite writes". A List<u8> written [1, 2, 3] reaches the engine as an ArrayLiteral of constants, and the writer's form for it is a PackedArray, which packs into a data segment — a literal tree the rewrite must still change. Only the writer knows which it would emit, so it decides: the walk compares each node against the node it would put there, allocates where they differ, and reports whether anything did. Nothing settles the question separately, so nothing can drift from it. Materializing leaves a tree the walk then matches, so the next visit writes nothing and reduction stays monotone and idempotent.

The cost gate stays separate and may stay conservative: asking the lattice for a container literal's value is what seq_literal_value decides, and over-asking costs a query the writer then declines, never a loop.

Identity

A literal is a fresh object. Writing one over an expression that yields a shared one leaves the program two objects where it had one, and ref.eq tells them apart. So the exit writes only over a node that yields an object nothing else reaches: a call or a region, which hand back what they built; a literal, which is one already; and the single read of a local nothing borrows, since a second read or a &p beside one is the second reacher. Whether the copy planner would later copy a value read is not knowable here, which is why a second read counts as sharing whatever its type. A reference-shaped leaf is refused outright, at each leaf rather than at the root, since a field can hold one where the whole value does not.

A scratch body needs none of this. It is read for the value it computes and then dropped, so nothing written over it runs.

Storage is not a value

A backing array reaches the IR as its container's field, where the length says how much of it is live, and never as a node of its own: writing a literal over the array_new that opens a buffer would hand the writes that follow a data segment's worth of zeros. For the same reason an empty container is left alone — a literal over one can only trade a buffer for a smaller buffer, and an opened buffer is what the region about to fill it is holding.

Within a container the backing is cut to the length, capacity being an allocation detail. That is what puts a folded string's bytes in a data segment sized to the string.

The budget

The byte path needs none: a PackedArray within MAX_SEQ_ELEMENTS reaches WIR as one array.new_data. A general aggregate has no such floor. A thousand-element List<i32> built by a loop is a dozen instructions, and its literal is a thousand operands, which array.new_fixed packs into a data segment only where the elements are primitive. So the writer counts the operands it would place, charging a byte sequence one, and refuses past MAX_MATERIALIZED_LEAVES.

It is a safety valve rather than a tuning knob. The sweep that chose it, over the benchmark and wasm-size corpora, found every ceiling from 16 up emitting the same bytes on every program: what the exit wrote there was many small values, not a few wide ones.

What it does not reach

The exit writes values; it does not produce them. A callee the engine never folds to a value is unaffected — HighlightVisitor::new builds its table through String::grow, which abandons the evaluation, so it stays a call whatever the writer can emit. That one is stage 3's.

• [x] The TypeId → fields index on ProgramFacts.
• [x] The writer, reporting whether it changed the tree, and the identity, storage and budget gates.
• [x] The leaf ceiling, swept against wasm size.
• [x] The recount, above.
• [ ] A destructuring let; a body containing one is abandoned.

Done when a constant List result and a constant struct result reach the IR as literals, Array::slice's computed bounds fold, and the corpus is recounted.

2. The stores the engine will not read

• [ ] The 240 global writes, which are the stores that fail the materialization property: a global read somewhere that does not store it. Whether that set has a shape of its own, or is a tail of unrelated cases, decides whether there is a mechanism here at all.
• [ ] Whether an unrunnable callee still refuses a region anywhere: impure, generic, async or bodiless. The corpus now counts none, so this is a check that the refusal has no cases left rather than a set to work through. A genuinely impure callee is a correct refusal; a still-generic one after monomorphization is a bug.

3. The frame owns storage

`${'x'}` does not fold, where `${true}` does. The census names no call for it. With `${255:x}` the place-valued field is what still pays for a formatter short of floats, and there the census does name a call.

Every template builds Formatter { …, buf: &mut buffer }, and a &mut in a struct-literal field is a write the frame does not perform, so the buffer is clobbered and the region abandons at its first append. bool::fmt writes the buffer straight, so inlining dissolves its Formatter and a later iteration folds the region; char::fmt reads f.buf back and appends through it, so the field outlives every pass. What the two once also differed by — a branch on f.width that no NIR pass folded — was two gaps in store_load_forward, since fixed, and the branch is gone.

• [x] What distinguishes the char path from the bool one: reading the buffer back out of the &mut field, which is the item below.
• [ ] A place-valued field, so an aggregate can carry a reference. Today such an aggregate is not a constant, since a field holding the referent's value would take a write meant for the referent; what it needs to hold is the place the frame already names elsewhere — place_aliases records exactly that pair for a let-bound borrow, and the gap is carrying one inside a value. The refusal is whole-value, so a scalar field naming no storage is refused with the rest. A template folds today only where inlining and SROA dissolve its Formatter first, which the inliner's pricing decides, not the engine.
• [ ] String::grow, which reshapes the caller's container from a frame of its own and so abandons the evaluation whenever a buffer outgrows its reservation.

A place names the frame's own storage and must not outlive it, so the aggregate exit refuses to write any value carrying one — a leaf gate beside the one that refuses a reference-shaped leaf.

Upstream: the retention-gated temp and write-back carve-outs and divergences D1–D6 in Reference Representation. The engine's notion of a place must be the one that WEP settles, not a second one.

Done when ${'x'} folds.

4. Format coverage to the budget

• [ ] The step budget is per function, and a formatting region spends a large share of it: four in one body all fold, while seven exhaust the budget and five of them stop folding. Whether that is a budget to raise, a cost to cut, or a limit to document is what a recount answers.
• [ ] Floats. fpfmt is the largest size prize by an order of magnitude and the largest engine cost, so the order is the engine's, not the payoff's; if it overruns the budget it becomes a known gap rather than a reason to raise the budget.
• [ ] A wasm-size and benchmark run, recording what the folds buy on whole programs rather than on one interpolation.

Done when a recount shows no refusal reason left that the step budget does not explain.

5. Mixed templates

• [ ] The marked region-append primitive set and the derived-fmt admission rule, per "Fold the region, not the call".

Done when a template mixing constant and runtime interpolations emits the constant parts as literals. The census counts no such template, since a region reading a runtime local is not reported; sizing this needs a count of its own, and a small one demotes the stage to a known gap.

6. The remaining refusals

Each is a small, local refusal the census does not count, so each needs a reason of its own to be worth the code.

• [ ] A switch with a constant scrutinee. A switch is formed before inlining. When inlining later makes its scrutinee constant, nothing revisits it.
• [ ] Closure calls: an indirect call whose closure is known is never resolved to a direct call, so neither inlining nor CTFE reaches through it.
• [ ] Guards decided when the engine is only asked what an expression denotes.

Validation, alongside every stage

• [ ] A fold / no-fold differential oracle in the fuzzer: compile each corpus fixture with and without constant folding and compare observable behaviour.

A wrong constant is a silent miscompile: no trap, no diagnostic, a different answer. Fixtures cover the shapes we thought of; the differential covers the ones we did not, and it is the safety net every stage above leans on.

Known gaps

A wasm-CTFE backend

Whole pure calls run through a real Wasm runtime, with the effect system as the purity gate. It would cover what the in-process engine balks at: recursion beyond a base case, fib(20)-shaped work, lookup-table generation. The cost is ms per call against niri's µs, amortized through a module cache.

Four things stand against it:

• wado-compiler must compile to wasm32-unknown-unknown and cannot link a runtime, so execution has to leave the crate, as Kiln generator execution already does.
• The host's generator entry point is async and the optimizer's fixed-point loop is not.
• Evaluating a call made while compiling needs a compiled module, which is circular.
• No module-cache lifetime is settled.

Unowned because the demand is not visible. No benchmark, stdlib path or corpus program exhibits recursion over constants, and compile-time data providers and Kiln already serve the "compute data at build time" case with a user-visible, content-addressed contract that implicit CTFE cannot match. If it is ever built it shares their host-delegated execution facility rather than adding a third.

Downstream of the same gap: recursion beyond a base case stays unfolded, and a runtime trap inside an unfolded body stays observable.

A write whose place roots in no local

The census counts 13. The frame cannot say where such a write lands, so it refuses the region rather than carry it out. A frame's places cover locals only. The roots it leaves out, such as a global or a call result, have not been counted against the 13.

Comparing two literal strings as a guard

It reaches the engine as a guard over a method call on references. niri folds a constant string comparison in value position; the guard position does not reduce.

Unrolling a loop in the caller

A code-size trade needing a cost model, not an evaluation capability.

User-facing CTFE syntax

#[const_eval], const fn. No demand has shown up; everything the roadmap covers is implicit.

Salsa-style demand-driven reanalysis across compiler runs

Named here so a proposal is measured against the optimizer's own caching decisions rather than raised fresh.