The loops that are worth folding are not the ones that stop

How this question came up

The spin fold does not run a loop that cannot end. Widening it — a body of several provably pure ops instead of exactly one — was the obvious next move, and toyvm-spin-loops.md records that it has no beneficiary at all: zero samples, in 199 programs. A loop whose body changes nothing has nowhere to put a counter, and fusion already collapsed that shape to one op.

The census built to answer that question (tools/toyvm/spin-census.js) was then pointed at the general case, and the general case is large.

What a self-loop census cannot see

The first version only recognised a loop that branches back to its own block head. That is one basic block, and almost nothing real is one basic block: a blitter is a bounds check, a body and a counter, which is two or three.

Generalising to "a backward edge to any earlier block head in the same region" needs one bound to be useful. Without it the edge swallows every block in between and reports the enclosing function: measured on BRW, the top six rows came back as 69-72 block, ~200-op "loops" whose bodies were full of call_rel. So the census counts inner loops — --max-blocks=8 --max-ops=64 — and every number below is a floor for that reason and one more: a loop whose head was compiled into a different region is invisible to it.

Measured

$ip samples, so shares are weighted by work rather than by sites.

node tools/toyvm/spin-census.js --dir=/tmp/demos --dispatches=2m

That last row is an upper bound and the real predicate is a third of it. tools/toyvm/loop-match.js summarizes each loop from handler-effects.js — induction variables, memory streams, trip count, leftover side effects — and applies the fold's actual conditions:

199 programs, 10007 inner-loop sites
matched 1480 sites, 11124 samples -- 8.1% of the run
  LUT_RUN 4.2%   SCAN_RUN 2.8%   FILL_RUN 0.8%   COPY_RUN 0.2%

8.1% corpus-wide, and 2.9% on the core ten against the coarse test's 10.0%. A 3.4x over-count is exactly the failure tools/match-loops.js exists to prevent for the production interpreter, whose own note is that a loose regex reads stack-counter loops as lut. Quote the predicate, not the shape guess.

The decline histogram is the work list:

   1737  in_8            \  a port read: a real loop with a real exit
    930  retf_imm         |
    903  ret              |  1834 sites where the "loop" spans a function
    603  call_rel         |  boundary -- see the caveat below
    229  call_far        /
    704  touches the stack
    544  no memory stream
    344  mixed access widths
    291  writes a segment register

Read the ret/call rows sceptically. A ret inside a loop body more likely means the backward-edge interval stitched across a function boundary than that a real loop contains a return. That subset wants re-reading before it is treated as headroom. And per §4.4 of loop-idiom-superops-design.md a loop containing a call is not Design B's territory either — a body op that can re-enter the emulator must disqualify the block, because a wrapper holds ip across iterations and a nested decode can flush the arena underneath it. Loops with calls are an inlining problem, not a loop-lowering one.

"Stream-shaped" is deliberately coarse — a memory write, plus an induction variable or a memory read, and nothing that leaves the loop's own control (no call, no interrupt, no port, no return). It says the ops are the right kind, not that the addresses line up. It is the toy VM's cheap analogue of what tools/match-loops.js asks of a PE for the production interpreter, and the real predicate will accept fewer.

It is concentrated rather than universal, which matters for what to build:

The family, and where the cost actually is

Corpus-wide the top shapes are one family, ~140 sites of it:

mov_rm8  lodsb  mov_rr8  push_r16  mov_rr16  sub_rr16  cli  rep_movsb  sti  pop_r16 ...

Read a count byte, point DS:SI and ES:DI at the run, rep movsb it, repeat. An RLE sprite blit — the same shape tools/find-rle-nests.js found in Caesar III for the production interpreter.

And rep_movsb is already one op that copies the whole run inside WAT. So the per-run cost is not the copying; it is the ten ops of setup around it, paid once per run, where a run is often only a few bytes. That is exactly the situation RLE_RUN addresses in src/07b-loop-match.wat, measured there at +7% batches/s and +21% API/s on Caesar. rect_run in the same family is +12% end-to-end.

BRW's smaller one is worth reading too — lodsb32 sh5_r8 or_rr8_jz stosb32 loop32 is load, shift, branch if zero, store, count down: a transparent-pixel blit, which is LUT_RUN's shape.

What the fold has to prove

The production matcher's guards apply unchanged, and they are the work:

• The streams must not alias. Source and destination ranges are computed once from the induction variables and the trip count, and the fold is declined if they intersect — otherwise a copy that overlaps itself byte by byte gives a different answer than a bulk move.
• The induction variables must be affine in the trip count, so the final register state can be written directly rather than iterated to.
• Step parity is not optional. A folded loop must charge exactly the steps the unfolded one spent, the way fusion charges its swallowed dispatch inline and the spin fold writes (v % S) - S. Without it $steps moves, slice boundaries move, interrupts land on different instructions, every frame in the corpus legitimately changes, and the 199-program diff stops being a check on the transformation. That check is the only reason any of this is verifiable.
• The budget is spent inside the loop, not around it. A fold that runs an unbounded trip count in one op can overrun a slice by an arbitrary amount; the trip count has to be clamped to what the remaining budget pays for, with the rest resumed on the next entry.

The counted delay loop

A pure body behind a loop/loop32 is the fourth row above — 0.7% of the corpus, three sites, and all of the weight is one program (ALABTRO.COM spends 96.3% of its run in nop -> nop -> loop32). The arithmetic differs from the spin fold's because the loop ends: the trip count is in CX, so it is min(cx * S, budget_remaining), CX decremented by what was run, and a fall through to the not-taken edge when it reaches zero.

Note it still has to charge the steps. A delay loop is the guest deliberately buying time; making it free would advance the guest past its own timer ticks. What the fold buys is that the host spends near-zero real CPU getting there — the same trade the spin fold makes.

Three sites in 199 programs is not a general primitive, so this is written down rather than built. If it happens, it should fall out of the counted-loop case of the stream fold above, not be a special case of its own.

The other two designs, and why one of them looks better

Folding an idiom is Design A in loop-idiom-superops-design.md. Two alternatives apply here and both are cheaper to be right about.

Design B — wrap the loop, run the same ops. No shape library: if a block branches to its own head, a wrapper op drives the body in a native loop. It cannot be semantically wrong, since it runs the same ops in the same order, and it fires on far more than 8.1% of the corpus — a wrapper does not care about streams, aliasing or access widths, so the only disqualifier is a body op that re-enters the emulator. loop-match.js scores that population separately:

wrappable (B/C): 6005 sites, 57431 samples 41.6% of the run
  mean body 15.5 ops behind one wrapper dispatch
  not wrappable:   953 sites  ret        \
                   934 sites  retf_imm    |  the backward-edge walk stitching
                   609 sites  call_rel    |  across a function boundary

Ports are deliberately allowed — a port read leaves to the host and comes straight back without compiling anything, so it cannot flush the arena under a wrapper holding ip in a local.

And a generic wrapper is still worth approximately nothing, which is the finding. The saving was supposed to be N $next preambles plus one trip through the back edge — the branch handler returning out to $run, the run preamble, a cache_lookup — and that round trip was its largest single item. It does not exist in this VM. Branch targets are resolved to arena addresses by a compile-time fixup, so GO() is:

(global.set $gip <guest>)
(if <budget and smc ok> (then (global.set $ip <arena>)) (else (call $slice_exit)))

A back edge is a store to $ip. What is left for a wrapper to remove is the per-op preamble, which every shell spells the same way:

(global.set $steps (i32.sub (global.get $steps) (i32.const 1)))
(if (global.get $halt) (then (return)))
(local.set $fn (i32.load (global.get $ip)))
(global.set $ip (i32.add (global.get $ip) (i32.const 4)))
(return_call_indirect $h (type $void) (local.get $fn))

— a decrement, a test, an add. The indirect dispatch stays, once per op. That is the same trade toyvm-superinstructions.md rejected for the block-head "charge the whole block's steps at once" op, and the same one the $next dispatch work measured at zero twice over: the cost is the mispredicted indirect branch, not the bookkeeping around it.

Design C — B on the switch shell was the attempt to fix that, on the grounds that a switch build has no indirect call, only an indirect branch inside one function. It does not help either, and for the same reason: the branch is still there and still mispredicted. Read toyvm-dispatch-shootout.md before assuming a number from the shell alone — switch measured +11.9% corpus geomean but +5.4% on the programs that actually rendered, bimodally (DSTNFO +40.1%, COPPER −26.0%, both reproduced).

So the only wrapper worth having is one that removes the dispatch, which means inlining the body — and that is codegen, not a table swap.

Inlining per body shape, statically, is capped too. loop-match.js --body-shapes finds 500 distinct matched body shapes corpus-wide:

  top    4 shapes cover 38.3% of matched weight  (= 3.1% of the whole run)
  top   16 shapes cover 81.8% of matched weight  (= 6.6% of the whole run)
  top   32 shapes cover 94.0% of matched weight  (= 7.6% of the whole run)

32 generated handlers to reach 7.6% of the run, against a generic wrapper that covers 41.6% and buys nothing. And the hottest shapes are single-program — the top one is four sites in daretro.exe. A static shape library is the worst of both.

That leaves the dispatch-removing wrapper generated at run time, per hot loop, which is toyvm-trace-jit.md's territory: its tier 3 lowers the body to micro-ops that do not match x86 — the addressing-mode br_table folded away, the registers living in wasm locals for the length of the loop — and measures 1.16-1.23x on top of tier 2's own optimizer.

(--body-ops sizes the other static option, a second dispatch site with a smaller arm set: 64 arms cover 98.1% of matched loop-body weight, so it is affordable. It is also pointless for the reason above — the arms would still be generic, so they would still read globals and still dispatch indirectly.)

Read toyvm-dispatch-shootout.md before assuming a number: switch measured +11.9% corpus geomean but +5.4% on the programs that actually rendered, bimodally (DSTNFO +40.1%, COPPER −26.0%, both reproduced), because inlining every body into one function makes the result depend on whether that program's hot handlers fit the engine's budgets.

Why the hoisting is worth doing here when it failed before. toyvm-superinstructions.md rejected a block-head "charge the whole block's steps at once" op on the grounds that DTM2 runs 3.25 ops per block transfer — one added dispatch to save 3.25 decrements. Inside a loop the wrapper is one dispatch amortized over iterations x ops: a 5-op loop running 100 times is 500. Same idea, different arithmetic, and that difference is the entire argument.

But keep the two hoists apart. The per-iteration bookkeeping — steps, halt test, ip advance, arena bound check, back edge — is structural and needs no semantics. Hoisting the memory bounds check needs the address range, which is A's stream analysis. The memory half of the idea rides on the matcher; the dispatch half does not.

Status

Nothing is folded. Two tools are built and are what the decision rests on: tools/toyvm/handler-effects.js (what each handler touches, 87.2% readable) and tools/toyvm/loop-match.js (the predicate, 8.1%).

The order that followed from the population numbers was "B or C first, because they fire on every loop and cannot be wrong, then A on the shapes that match". That order is withdrawn. B and C fire on 41.6% and cannot be wrong, and also cannot pay: this VM resolves branch targets to arena addresses at compile time, so the back-edge round trip they were supposed to remove does not exist, and what is left is three trivial instructions per op with the mispredicted indirect dispatch untouched.

What replaces it: the wrapper has to remove the dispatch, so it has to inline, so it has to be generated — at run time, because 500 body shapes defeat a static library. handler-effects.js and loop-match.js remain the right front end for picking which loop; the back end is the trace JIT.

The one stream that was already a super-op: REP MOVS/STOS (2026-09-02)

Everything above is about loops the guest writes by hand. The guest also writes loops the CPU runs for it, and those were already one dispatch: rep movsb retires its whole count inside one handler. What it was not was wide — each element went through $rd8/$wr8, a call, a segment-base br_table, the address mask, the VGA-window key compare and a code-bitmap probe, per byte.

rep movs{b,w,d} and rep stos{b,w,d} (both address sizes) now open with a guarded fast path: when the run is provably one plain range in RAM it is a single memory.copy / memory.fill (a store loop for a 16/32-bit STOS pattern), and the registers, CX and the step charge come out exactly as the byte loop leaves them. The guards are the byte path's per-element checks, hoisted — DF clear, no offset wrap in the segment (or no 32-bit overflow), the linear range inside the address mask and the wasm memory, clear of the VGA window while the planar key is on, no compiled code under the destination, and no forward overlap unless the destination is exactly one element ahead, which is the memset idiom and a fill with that element. Anything else falls into the unchanged loop. --no-rep-fast is the A/B arm; the summary prints rep widened: N runs, B bytes; declined: ... by guard.

Measured, bench-set-20 at 12M dispatches, both arms: 20/20 identical handbacks, interrupts, frame hash, pixel count and self-modify count; the 8088 single-step corpus (A4-AB, a quarter of its 32000 vectors REP-prefixed with random CX, DF and segment wraps) passes 100%. Speed, 60M dispatches interleaved:

Two corrections to the estimate that motivated this. The "REP share of the dispatch clock" figures (COPPER 85%, DSTNFO 88%, daretro 55%…) were derived as dispatches minus handler entries, and that remainder is not only REP elements — a region or a spin twin also retires many steps per entry — so most of those shares were regions, not string ops. The census above is the real population: COPPER is the one program that moves tens of megabytes through REP, and it is the one that moved. And DSTNFO's 88% (EGA planar) and ADDY_II's 5488 declines are vga/mask: a planar-mode program writing its screen through the graphics controller, which only the byte path's write-mode pipeline can do. A widened planar fill (write mode 0, all-ones bit mask, per-plane memory.fill) is the obvious next form of this and has ADDY_II and DHADREN as beneficiaries.

What remains of the "byte loops" idea after this is the unrolled string op — daretro's 353K lodsb, CONTACT's 783K lodsb + 388K stosb — which sit inside guest loops with real bodies. That is the trace JIT's population, not REP's.

Sized after the fact with the census's declined-bytes figure: ADDY_II declines 1.42 MB per 12M dispatches to the planar guard against 1.29 MB it widens, and DSTNFO 84 KB. So the planar fill is worth at most what the plain widening was worth to ADDY_II (about +10%), not a COPPER-sized win; it stays on the list behind the trace JIT work.