The expression-tree fold

--tree-fold, off by default. tools/toyvm/tree-fold.js, the pass in compileProgram, test/test-toyvm-tree-fold.js.

Verdict up front. It works and it is not yet worth turning on. It removes 16.8% of BRW's dispatches and buys 12.7% there; on the other five programs measured it removes under 2% and loses 5-14% to the flat cost of installing a module mid-run, for a geomean of −3.8%. Frames are identical on all six witnesses and on 190 of 191 corpus programs; the two programs that moved (one --auto-key menu, one self-patcher) both reproduce the plain build exactly when the install schedule changes, so nothing here computes a wrong value — it changes when things happen, which on this VM is audible. Read What it costs and What is next: the fold is static, and a hotness gate is the change that would make the rest of it pay.

Since then, two things have been added and each has its own section. The hotness gate (--tree-fold-hot=N) removes the flat install cost from the programs that were never going to earn it. DOS-tailored: partial registers and flags as values (--tree-fold-relax=) widens what is eligible to include the 8/16-bit ops and the adc/setcc/dec-jnz chains 16-bit real-mode code is actually written in — partial-reg falls from 3515 to 15 on BRW and the flag consumer bucket empties entirely. The verdict above is unchanged: the default is still OFF.

What it is, and what makes it different from the other two folds

The VM already collapses two shapes. Superinstructions join exactly two ops. Spin loops collapse a block that is one branch back to its own head and does nothing. Both are fixed patterns: they match a shape and swap in a handler that was generated when the module was built.

This one is not a pattern. It takes the straight-line interior of a basic block — a run of full-width mov/lea/ALU/shift/widening ops — and generates a wasm function for that particular run, at run time, and installs it. Four ops or four hundred, the run costs one dispatch and its intermediates never touch the guest register file.

The static census is what says that is worth doing, and the bench is what says how much. This document is the implementation: what is eligible, how a run becomes a handler, how the clock is kept, and what it measured.

Eligibility

This section describes the rule set the fold shipped with, which is now --tree-fold-relax=none. Two of the restrictions below — the narrow-op one and the flag-consumer one — are lifted by default today; see DOS-tailored: partial registers and flags as values. Everything measured in What it measures is the =none rule set.

The rule set is expr-fold-census.js's classify(), imported, not reimplemented. The census measured the population this fold exists for; a fold whose eligibility had drifted from the census's would be answering a different question from the one that justified building it. In summary, an op is foldable when it is:

• a full-width mov, lea, add, sub, and, or, xor, neg, not, inc, dec, shl/shr/sar by an immediate, imul2/imul3, or a movzx/movsx that widens — register or memory operands, either direction;
• at the block's own width (16-bit in real mode, 32-bit under a 32-bit code segment). A narrower op ends the run: AL and AH are subfields of AX in the register file, so an 8-bit write inside a 16-bit run is an overlap the fold does not model.

and it is not any of: a branch, a call, a ret, an int, a string op, a stack op, a mul/div, a segment load, a port access, an x87 op, a setcc, a cmp/test, an adc/sbb, a rotate, a shift by CL, or anything that writes flags a later op in the same run reads.

Two rules are about the run rather than the op:

• Memory keeps its source order. Every load and store stays a $rd*/$wr* call in the order it was emitted, so a run may contain as many as it likes.
• ...but a store followed by a load ends the run. Nothing here proves two addresses miss each other, so every load after a store is assumed to alias. This is the most expensive rule in the set and the first candidate for relaxation (below).

And three the fold adds on top, asked of the lowered body rather than the opcode, because the handler in the arena may be a flagless or specialized twin rather than the base op:

• it must not read the dispatch clock ($steps, $slice_budget, $vga_status, $port_in/$port_out) — the interpreter would have charged a step per op before it and the fold charges the whole run at once, so a clock read inside would see a different number;
• it must not be able to leave the handler ($halt, $slice_exit, $fault, $jlook, a bare (return), or an $ip write that is not the operand advance) — an early exit would leave $ip parked in the middle of the run's operand words;
• its operands must fold (foldOperands in trace-jit.js must recognise the ops(n) prologue shape).

The minimum run length is four, --tree-fold-min=N. Four is the census's own threshold — in >=4-fold blocks is the column that varies fifty-fold across the corpus and decides which programs the fold can pay on.

The terminator is not in the fold. The block's branch, and the cmp or dec that feeds it, stay exactly the ops they were. That is deliberate, and § Why the loop is not folded in place below is the reason.

How a run becomes a handler

The lowering is trace-jit.js's emitTier3, which is the region JIT's own code generator. Five passes, each bought with a bisect, and a second copy of them here would have been a second set of bugs:

promoteRegs declines outright if any call in the run is not on its allow-list, so a run that could change a segment base or the stack pointer never gets promoted; it is still folded, just without the locals.

The emitted body is four parts:

  (global.set $steps (i32.sub (global.get $steps) (i32.const N-1)))   ;; the step charge
  <pro>                                     ;; live-in registers -> locals, once
  <the run, straight-line, in locals>
  <epi>                                     ;; live-out registers -> globals, once
  (global.set $ip (i32.add (global.get $ip) (i32.const ARITY*4)))

The handler is appended to the table the way a JIT region is — opts.regions, past HANDLERS.length, so every existing index keeps its meaning — and its ordinal is resolved through vm.regionBase at substitution time rather than remembered, because only the built module knows where its extras landed.

Two runs with the same ops and the same operand words are the same handler (treeKey). Without that, a program that recompiles its hot loop eighty thousand times would generate eighty thousand identical functions.

Flags

The $rec_* calls are kept verbatim, in source order, which satisfies the census's per-FIELD last-writer rule by construction rather than by analysis. The recorder is not one value: $rec_add/$rec_sub write fop/fa/fb/fu/ fr/fw; $rec_logic writes only fop/fr/fw; $rec_inc/$rec_dec materialize CF first and then write fcf. So after add then xor, the rule and the result come from the xor and the carry still comes from the add — which is exactly what falls out of running the two recorders in order.

The compiler's own dead-flag pass (docs/toyvm-dead-flags.md) has already run over these words, across block edges, with a real liveness fixpoint, and swapped every provably-dead flag writer for its flagless twin. So whatever recorder is still in the run is one some successor may read, and the fold runs it. emitTier3's own deadflags pass is turned off for that reason (and because it is written for the eager scheme and would find nothing anyway).

test/test-toyvm-tree-fold.js prints the six arithmetic FLAGS bits alongside the registers precisely because this is the part a naive fold gets wrong silently: hoist the run into locals and write the register file back at the end, and the picture is right while pushf is wrong.

The clock, and why the arena does not change shape

Two properties make --tree-fold a transformation that can be regression- tested rather than a retiming that has to be re-photographed.

1. The fold charges the dispatches it removes. $next charged one step to dispatch into the tree; the run it replaces retired N. So the body charges N−1 more, inline, up front. $steps at the block transfer is therefore identical to what an unfolded compile would leave, and the block transfer is where $slice_exit tests the budget, where an IRQ is injected, where the Sound Blaster's DMA is fetched and where a handback is taken.

2. The arena is byte-for-byte the same size. Unlike fusion, which splices the second op's word out, this overwrites the run's first word with the tree's handler index and leaves every other word of the run where it is, as operands the tree steps over. Word count, block boundaries, fixup indices and — the one that matters — the arena-recycle point are all identical to an unfolded compile. A moved recycle boundary is what shifted CONTAGIO, AQUAPHOB, COUNTDWN and ZOKDTPLN under fusion; it cannot happen here.

Why the loop is not folded in place

Superseded. It is now, for a self-loop block whose whole body folds — see Folding the terminator below. The objection in this section was right about the hazard and wrong about the conclusion: the fix is not to leave the terminator alone, it is to take the region JIT's boundary test with it. The paragraph is kept because the hazard it names is still what the loop fold has to answer for.

The scope this could have had is "fold the whole self-loop and iterate inside the handler while the terminator's condition holds". It does not, and the reason is region-live.js's DREAM row: a fold that loops in place absorbs block transfers, and a block transfer is where the guest's slice can end. Absorbing them moves every later slice boundary, and therefore every audio render, for the rest of the run — an identical picture and a different wav from the install on. Looping in place is the region JIT's job and it already has it.

Self-modifying code

Nothing new is needed. The block was decoded normally, so covered already names its bytes and the code bitmap already covers them; a store into any of them raises $smc, dos-loop.js drops the whole compiled program, and the fold goes with it.

What does change is the fast operand repair. CodeCache.repairProg walks prog.wordIp per instruction and checks that the arena's handler at each word is the decoded op, one of its twins, or the fused pair. A tree word is none of those, so it declines with handler differs and the store falls back to dropping the program and recompiling it. That is a cost, not a hazard — it degrades to what the VM did before operand repair existed — but it is a real regression on the self-patching class (CYCLE, CYBOMAN2), and it is the reason the fold is opt-in rather than on.

Installing without costing the run a handback

A fold cannot be installed by writing a word: the handler has to exist in the module's table, and a wasm module is not editable after the fact. So the shape is region-live.js's, in miniature:

1. compile — a block wants a tree; want() records it and the block compiles unfolded and runs. Nothing is stalled.
2. pump — between two slices, off the guest clock: build a module with every wanted tree appended, instantiate it over the same memory, carryState the globals, vm.rebind, machine.setVmExports, re-apply the VGA programming.
3. drop — exactly the programs holding a block that wanted a tree, then compile those heads back here, on the host's turn, and re-point the shadow return stack rather than cutting it.

Step 3 is the whole care. A block the cache does not hold is a handback; a handback cuts its slice short; the unspent remainder shifts every later slice boundary. cache.flush() would have been one line and would have moved the audio of every program in the corpus.

The install policy is the difference between winning and losing

A run discovers its foldable blocks a few at a time over thousands of slices, so "install as soon as something wants a tree" means a module build per tree — and every install moves the guest onto a cold instance the engine has to re-tier from scratch. Measured on ACCIDENT at 8M dispatches:

So batching is not an optimization, it is what makes the fold usable at all. A batch goes in when it is big enough to be worth a build (--tree-fold-batch=64) or when it has stopped growing (--tree-fold-wait=400 slices — the second half matters, or a program that finds only three foldable blocks would never install any of them), and a run installs at most four times (--tree-fold-installs=4) and generates at most 256 trees (--tree-fold-max).

--tree-fold and --region-jit used to be mutually exclusive: both append to the handler table through opts.regions, so whichever built last owned the ordinals the other's arena words were written against. They are not any more — see One allocator for the handler table's tail below.

Gates

1. The existing suite, flag off and flag on

All 23 test/test-toyvm-*.js run individually, twice: once normally, once with TOYVM_TREE_FOLD=1 (the environment override exists for this gate alone — the tests shell out to run-dos.js with argument lists of their own).

off: 23/23 passed
on:  23/23 passed

Both arms pass every suite. test-toyvm-operand-patch.js is the one worth naming: it is the suite that exercises the self-modifying-code plan cache, and it passes with the fold on because a folded block declines the in-place repair and falls back to drop-and-recompile rather than repairing the wrong word.

2. test/test-toyvm-tree-fold.js

Six hand-assembled .COM programs, each one shape, each run twice and required to print an identical AX/BX/CX/DX/SI/DI/FLAGS line:

The positive cases additionally assert that a handler was generated and substituted; the negative ones that nothing at all folded.

PASS test-toyvm-tree-fold:
  dot       12345678FA2CA3B4A97FA97E0045   2 fold(s)/1 tree(s)
  addrloop  0F0E607800004050021000000044   2 fold(s)/2 tree(s)
  incloop   003C01C0000001C0001000000044   2 fold(s)/2 tree(s)
  partial   123700AA129D0000000000000044   no fold
  alias     1234567800001234000000000044   no fold
  flagcons  1234567868ACD110000000000044   no fold

Two notes for whoever edits that test. Its rel8/rel16 helpers measure the displacement from the byte after the whole instruction, not from where the argument is written — get that wrong and the program runs forever at a plausible-looking address instead of failing. And the alias case needs a nop between the loop-counter prologue and the body, because the prologue's own store is foldable and will otherwise join the body's first three ops and fold a run the case is supposed to refuse.

3. The corpus, flag off vs flag on

sweep-dos.js --dir=/tmp/demos --reps=1 --variants=tailcall --dispatches=8m, once plain and once with --tree-fold, then sweep-diff.js:

191 programs
REGRESSIONS: 0
WENT BLANK: 1   COLORS.EXE
changed (frame and/or dispatches moved, still drawing): 42
  -- 41 of those are identical frame, identical pixel count, identical dispatches
  -- 1 real: ZOKDTPLN.COM  frame 39fca965 -> 2c2fdb2b, px 63885 -> 63887
recovered: 1    QUARTZ.EXE (timeout -> ok; the known QUARTZ flake)
unchanged: 147

42 programs folded at least one tree and both movers are install timing, not a folded value. The proof is the same experiment in both cases: change nothing but when the batch installs (--tree-fold-batch=1, which installs a handful of trees early instead of 64 later) and the arm reproduces the plain build exactly.

• COLORS.EXE is an interactive setup menu (video type, sound card, port, IRQ) answered by --auto-key, whose keystrokes are scheduled off the dispatch clock. With the default batching it exits cleanly at 2.5M with the menu still on screen — a keystroke landed on a different prompt. With --tree-fold-batch=1 it is byte-identical to the plain arm: same frame 7eb1ed94, same 28081 pixels, same 8.0M dispatches, same cs:ip. A fold computing a wrong value could not reproduce the baseline frame hash in either configuration.
• ZOKDTPLN.COM is the COUNTDWN self-patcher, and it moves by 2 pixels of
  63885. Its stats name the path: 1301 self-modify breaks and 10 volatile paragraphs plain, 1308 and 20 folded. A folded block declines the in-place operand repair, so more paragraphs get promoted to volatile and the patch lands a frame boundary away. --tree-fold-batch=1 (3 substitutions instead of
  160. restores frame 39fca965.

Both are the cost of installing a module into a running machine, and both are arguments for the hotness gate in What is next rather than for a different handler body.

4. Six witnesses at 80M

Each witness run twice at --dispatches=80m --pit-clock --auto-key --sound-pref=sb --env=ULTRASND=220,1,1,11,7 --audio=FILE, comparing the frame hash and the sha256 of the rendered wav.

The frame is identical on all six. Two wavs are not, and the two have different causes; both are timing, neither is a wrong value.

ACME-BIG is the slice grid, and it is provable. The audio renderer advances by budget - left at each handback, so the sample boundaries are wherever the slices happen to cut. An install is a handback the other arm does not take — 1812 handbacks off against 1817 on at 20M — so from the first install onward the two arms resample the same GUS voices at different offsets. That predicts one thing: anchor the grid and the difference disappears. Re-run both arms with --lattice-clock, which cuts every slice and renders audio on fixed multiples of the dispatch clock, and ACME-BIG's wav is identical (572514130dbaf435). The 83% raw byte agreement with no clean time shift is what re-quantization looks like, not what different audio looks like.

CONTAGIO survives the lattice, and its cause is arena pressure. Same frame, but the wav still differs and is 24 bytes shorter, so the guest reached a different point per dispatch. The stats name the mechanism: the folded arm carries 860KB of arena against 563KB and takes 1 arena recycle where the plain arm takes 0, and downstream of that recycle the two arms make different rep-widening decisions (10850 widened runs off, 9930 on) and form different traces (706 vs 797). A widened rep bills a different number of dispatches for the same guest bytes than the loop it replaces, so once the widening decisions diverge the dispatch clock is no longer measuring the same thing in both arms, and the audio re-times. Capping at --tree-fold-max=64 cuts the fold's WAT to 126KB but does not get the recycle back, so this is not a knob away.

For contrast, --region-jit — which installs modules mid-run through the same recipe — reproduces ACME-BIG's baseline wav byte for byte. The install machinery is not what does this; the extra handback and the extra arena are.

So this gate is 4/6 as specified, 5/6 once the clock grid is held fixed, and 6/6 on the picture. That is the single strongest argument for the flag defaulting off: the fold does not change any value the guest computes, but on a program that is already near an arena boundary it changes when things happen, and on this VM when things happen is what the speaker plays.

What it measures

What it removes (load-independent)

One run per program at --dispatches=20m --tree-fold, with the tree handlers' own entries read straight out of the handler histogram, so "trips through $next removed" is Σ entries(tree) × (ops(tree) − 1) — a count, not a time.

BRW's three hottest trees are six ops each and run 222,909 / 222,909 / 222,904 times — one blitter, three blocks of it. That single loop is most of the 16.8%. CYCLE is the other extreme and the most instructive row: 14 handlers were generated, 6 were substituted, and they were entered three times in twenty million dispatches. The fold is static; nothing in it asks whether a block is hot.

What it costs (interleaved A/B)

bench-dos.js --variants=tailcall,tailcall+treefold --reps=5 --dispatches=20m --cpu-time --dispatch-drift=4096, arms alternating every rep with the order rotated, minimum of five. Frames identical on all six.

The fold as it stands is a net loss, and the two columns explain each other. Benefit tracks the removed-dispatch share and nothing else: BRW removes 16.8% of its dispatches and gains 12.7%, which is about the right size for a dispatch that costs ~8ns against a ~15ns average. Cost does not track it — B-STEEL removes 0.21% and loses 13.9%, DHADREN removes 0.64% and loses 13.1%. That is a flat per-run charge of roughly 5-14% for having installed a module at all: the guest resumes on a fresh wasm instance the engine has to re-tier, and it is a bigger instance than the one it left. DTM2, which folds nothing and never installs, is the control and comes back at +0.6%/−0.5% — the noise floor.

So the shape of the result is: one program in six is worth it, and it is the one whose folds are hot. Everything in What is next is aimed at one of those two terms — the three relaxations raise the removed share, the hotness gate removes the charge from the programs that were never going to earn it.

Load was 6.6-6.8 throughout and the per-arm spread ran to 91% on the noisiest row, which is why only the interleaved minimum is quoted here and no wall clock appears anywhere in this table.

Why the other blocks declined

Every block the pass looks at and refuses is counted by reason. Across the six 20M runs, as a share of all declines:

partial-reg and too short are the two biggest buckets in every program, and flag consumer + terminator together are the next. Those are exactly the three relaxations below, in that order. stack, call and ret are not relaxations at all — a block that pushes, calls or returns is a control-flow question, and this fold is deliberately a straight-line one.

The unsupported op tail is long and thin: cdq, cwd, cbw, cwde, xchg, shld/shrd, nop, bts/btr, lar/lsl, and the protected-mode mov cr/lgdt/lidt/ltr/smsw group. Most of them are one line in the lowering table each, and none of them is worth adding until a census says a folded run actually ends on one.

The hotness gate (--tree-fold-hot=N)

The static fold above compiles a tree for every foldable run it meets at decode time. That is why its cost is flat and unrelated to trees executed: CYCLE built 14 handlers for 3 tree entries, ACCIDENT built 167 handlers (437.5KB of WAT, the install cap) to remove 1.84% of its dispatches, and both paid the whole build + re-tier bill anyway. --tree-fold-hot=N makes the fold pay only for blocks the guest actually re-enters.

The signal

region-jit decides hotness by sampling $ip at slice expiry (region-live.js, sampleAfter/profileFor both 6e6). That is free, but at a 2e6-dispatch slice it takes about ten samples per 20M dispatches — nowhere near enough to rank individual blocks. The gate therefore uses the exact counter we already have: --block-hits, one u32 per arena word at isa.IPHIST_BASE, bumped at the top of $next (emit.js ipHistBump). It is per-block-entry and exact.

Its per-dispatch cost is what makes it usable only as a window. Interleaved against plain, the blockhits arm reads +3.1% min / −1.7% paired across the six programs — i.e. inside this box's noise, but certainly not free forever. So the gate profiles on a --block-hits build and then takes the profiler away: the fold's own instance swap installs a build with ipHist off, which is a transition it was already making.

Three phases

1. warm — the guest runs on the profiling build. compile.js still calls tf.want(key, run, lin, addr) for every foldable run, but want only records a candidate: the run, the guest linear addresses it covers, and the arena addresses to read counters from. Nothing is built.
2. window close at warmFrom + warmFor dispatches (--tree-fold-warm, default 10e6). Every candidate's counters are read; a candidate whose hottest arena address has fewer than N entries is dropped as cold (<N entries). The survivors publish their guest addresses into hotLins, and their blocks are dropped so the next compile of them can want a tree.
3. closed — the install fires (always, even with zero survivors, so the profiler comes out on programs where nothing is hot), and from then on want accepts a run only if hotLins has its guest address; everything else is declined as cold block (outside the hot set).

The verdict keys on guest addresses, not arena words. The first design promoted the captured run and then substituted almost nothing — ACCIDENT built 88 handlers for 3 substitutions, BRW 1 tree for 0. A run is a list of arena words, and fusion, the cross-block dead-flag pass and trace formation all emit different words for the same guest bytes depending on compile context, so treeKey no longer matched after the drop-and-recompile. Keying on the guest address and letting the recompile hand its own run to the install fixed it: ACCIDENT went 167 handlers/437.5KB → 2/4.3KB, BRW 96/185.8KB → 10/19.0KB with 98 substitutions.

The window has to be placed where the hot code exists. BRW's blitter is not compiled until ~6-10M dispatches in, so --tree-fold-warm defaults to 10e6, not the 2e6 the first version used.

The arena keeps the shape the design requires: an install that lands on a block already executing is handback-neutral by the same recipe region-live installs use (dropWanting() recompiles dropped heads on the host's turn and repairs the shadow return stack rather than cutting it), and the run's first word still becomes the tree ordinal with every later word left in place as an operand the handler steps over.

Load-independent counts, 20M dispatches

The bill (handlers built, WAT bytes) against the yield (dispatches removed):

The gate's own ledger, from the tree gate: line:

DHADREN is the row that explains the static arm's −13.1%: its hottest foldable candidate is entered twice. Every tree the static fold built for it was build cost against a block that never ran again. The gate builds nothing there, and DHADREN goes from −6.4% min / −9.5% paired (static) to +0.8% / +2.3%.

BRW keeps 81% of the static arm's yield (13.58% of dispatches removed against 16.81%) for 10% of its code size.

Three-arm timing, interleaved --reps=5, --cpu-time, 20M dispatches

Baseline is plain tailcall. Positive is faster.

Read the counts, not the percentages. This box sits at load 20-40 and the timing says so: the unchanged static arm read −3.8% geomean in the run in the previous section and +2.7% here, and the blockhits control — which cannot be faster than plain, it only adds a store per dispatch — reads +3.1% min. Both numbers are noise. The defensible timing claim is the shape: the gate takes the static fold's roughly −5% paired loss back to about parity, it is the only arm that wins on BRW under both statistics, and it stops the three programs the static fold regressed from regressing.

Corpus and witnesses

Corpus sweep, 191 programs at 8M dispatches, tailcall off against --tree-fold --tree-fold-hot=64: 191 unchanged, 0 regressions, 0 went blank, 0 frame hashes moved, 0 bucket moves. (The static fold's own sweep was 190/191 with one explained mover; the gate is clean outright, because on most of the corpus it now builds nothing at all.)

Six 80M audio witnesses, plain against --tree-fold --tree-fold-hot=64. All six frame hashes are identical between the arms and match the recorded values (DADEMO3 36128ac7, RUNDEMO 08502c5c, BLIQ a12d718a, ACME-BIG 362275f5, CONTAGIO 163af616, CATWALK 19cfa368). Four of the six wavs are byte-identical too; BLIQ and CONTAGIO differ.

That difference is the install schedule, not a wrong value. An install is an instance swap — a handback at a point the plain arm does not have one — and a handback cuts its slice short and shifts every later slice boundary, which is what the audio clock is paced by. Re-running the two at several different install schedules shows exactly that signature:

A wrong value would be one stable wrong answer. This is a different answer per schedule, with two schedules landing back on plain byte for byte, and the frame hash pinned at a12d718a / 163af616 through all of it. It is the same audio-timing sensitivity region-live installs already have, and it is the reason the fold's install policy batches and waits.

Verdict

--tree-fold stays default OFF, and so does the gate. The gate is a strict improvement on the static fold — it removes the flat build cost, keeps most of the yield on the one program that has one, and turns three regressions into non-events — but the gated arm is not >= plain on every program (DTM2, the control, reads −3.9%/−6.1%, and CYCLE −6.6% paired), and the whole-corpus argument for turning it on is still one program wide. Flipping the default is the user's call regardless.

Remaining declines, gated

BRW, N=64: partial-reg 22009, too short 19603, terminator 10169, flag consumer 9172, muldiv 2620, alias 2589, stack 1608, cold block (outside the hot set) 606, cold (<64 entries) 87.

ACCIDENT, N=64: stack 3708, too short 3606, terminator 2986, partial-reg 1924, call 1316, segment 648, flag consumer 592, alias 445, ret 431, io 311, muldiv 275, cold (<64 entries) 264.

The two gate buckets are a rounding error next to partial-reg, too short, terminator, stack and flag consumer — the gate is not what is limiting coverage, the eligibility rules are, and the work list below is unchanged by it.

DOS-tailored: partial registers and flags as values

Everything above is measured with the rule set the fold shipped with. Two of the three relaxations the work list asks for are now implemented, behind --tree-fold-relax=:

bench-dos.js carries the same arms as tailcall+treefoldexact and tailcall+treefoldhotexact, and sweep-dos.js takes the flag corpus-wide.

Neither one needed a new model

That is the whole reason they are one change each rather than a rewrite, and it is worth saying why, because "8-bit writes into a 32-bit local" and "flags as values" both sound like new machinery.

Partial registers. emit.js already spells an 8-bit register read as an extract and an 8-bit write as a mask-and-or insert over the full-width global ($rget8/$rset8, and $rset16 for a 16-bit write inside a 32-bit block). trace-jit.js's foldRegisterFile/foldRegisterFileWide already collapse those to a direct access once the register index is a constant, which it is inside a tree, and promoteRegs then rewrites that global into the run's wasm local. So AL is bits 0-7 of the promoted AX local by construction, not by a second copy of the register file. 8- and 16-bit loads and stores keep their $rd8/$wr8 calls in source order like every other memory op, so they carry the same fault and segment semantics as the per-op handlers.

Flags. Flags here are lazy: a producer calls $rec_* to record its inputs, a consumer calls $get_cf/$cond* to materialize the one field it wants. The fold keeps both calls verbatim and in source order inside the generated handler, and deliberately leaves the flag globals out of the register promotion set — so the per-FIELD last-writer state at the run's end is exactly what an unfolded compile would have left for the terminator and the successor blocks to read.

So both are ACCEPTANCE changes. classify() in expr-fold-census.js already tags each declined op with the relaxation that would take it; eligibleRuns now consults a relaxation set instead of refusing outright.

What stays a barrier, and why: rol/ror at any width (narrow is not on its own a licence); lahf/sahf/pushf/popf and the BCD group, which want the architectural FLAGS word including AF, which the record does not carry as a value; and a shift by CL, whose flag effect is undefined at count zero and so is not a function of the recorded operands alone. The decline histogram now splits the old flag consumer bucket into shift by CL and flags word: <stem> so what is left is still a work list rather than one opaque number.

Before and after, load-independent

One run per program at --dispatches=20m --tree-fold --tree-fold-hot=64 --handler-hist=1 --pit-clock --auto-key --sound-pref=sb --env=ULTRASND=220,1,1,11,7, three arms: =none / =partial / =partial,flags. Counts, so the load does not enter.

Every frame hash is identical down all three arms, which is the contract.

The two buckets the relaxations were aimed at empty out almost exactly:

flag consumer goes to zero everywhere because the bucket is now split: what is left of it shows up as shift by CL (BRW 25, DHADREN 68, ACCIDENT 8) and flags word: cli/sti/cld/clc/stc/sh2/sh3/cmc/sahf (BRW 141 across six stems, ACCIDENT 149 across nine). The residual partial-reg is rol/ror at 8 and 16 bits, which is a deliberate keep-out.

The hot blocks column is the one to read for reach, and the $next removed column for what that reach was worth here. DTM2's hot set goes 4 → 18 and CYCLE's 4 → 16 — four times the eligible population — while their removed share stays 0.00%, because those blocks are still not the blocks those programs actually spend their dispatches in. ACCIDENT is the one program where the extra eligibility lands on hot code: 0.28% → 0.74%, from 3 substitutions to 10.

BRW is the row that does not do what the census predicted. The relaxations move its hottest foldable candidate from 990 entries to 200,259 — a 200x — and it still records zero tree dispatches, because the substituted blocks are not re-entered after the install in this configuration. Its frame is identical at both 20M and 60M, so this is a reach-versus-use gap and not a correctness one, but it is unexplained and it is why the timing row below should not be read as "the relaxations bought BRW 38%".

Timing, and why it is not quotable here

bench-dos.js --variants=tailcall,tailcall+treefoldhotexact,tailcall+treefoldhot --reps=5 --cpu-time --dispatches=20m --dispatch-drift=4096, arms alternating every rep with the order rotated, minimum of five, guest CPU only. Load 11-13 throughout.

None of these percentages are quotable, and the table says so itself. DHADREN folds nothing, installs nothing and substitutes nothing in any of the three arms — it is the control — and it reads +11.3% min / +18.4% paired. The per-arm spread ran 17% to 134%. A control that moves by more than the effect means the box, not the fold, is what got measured; this is the load-20-40 machine the rest of the doc keeps warning about. The load-independent counts above are the result of this work. The timing rows are recorded so the next person does not re-run them expecting an answer.

Corpus and witnesses

Six 80M audio witnesses, plain against --tree-fold --tree-fold-hot=64 with the relaxations on, --pit-clock --auto-key --sound-pref=sb --env=ULTRASND=220,1,1,11,7 --audio=FILE:

All six frame hashes are identical between the arms and match the recorded values. BLIQ and CONTAGIO were already install-schedule movers before this change (see the gate's own witness table above). CATWALK is new, and it has the same signature: at --tree-fold-batch=1 its wav is byte-identical to plain (9268efa36e4ed39d), as is BLIQ's (e1c772ec7df8ae65, the same value the gate's table recorded). ACME-BIG, which the static fold moved, is identical here outright. A wrong value would be one stable wrong answer; this is a different answer per install schedule with the frame pinned, which is the audio-timing sensitivity documented above.

What still declines

With both relaxations on, the largest buckets at N=64, 20M:

BRW: too short 5438, terminator 3569, alias 2020, cold block 1140, muldiv 795, stack 698, call 348, io 282, ret 251.

ACCIDENT: too short 3841, stack 3628, terminator 2939, call 1292, segment 638, alias 633, ret 411, cold (<64 entries) 348, io 311, muldiv 266.

The work list has changed shape. partial-reg and flag consumer are gone from the top; what is left is too short, stack, terminator, alias and call — and too short is now the largest single bucket in both programs, which is a different kind of problem from the other four. A run that ends at three ops does so because something a few ops away is still a barrier, so the remaining buckets feed it: every alias pair that is proved disjoint, and every stack op that is modelled, joins two short runs into one long one rather than adding a run of its own. Alias disjointness (below) is therefore worth more than its own 2020/633 suggests.

Folding the terminator

terminator is the second- or third-largest decline bucket in every program above, and it is not one barrier but two questions. The first — may the terminator's own cmp join the run? — is answered by the flags relaxation. The second is the one Why the loop is not folded in place declined: may the tree keep iterating, so a loop costs one dispatch per LOOP instead of one per iteration?

It may, and it needed no new machinery — only the discipline to stop writing one. A self-loop block whose whole body is one eligible run is lowered by handing that run to region-jit.js's own buildRegion, as a one-block closed region whose last nexts entry is the block's head. Nothing in buildRegion requires the block to have come from a profiling trace, and the looping protocol that comes with it is the protocol this doc's objection asked for:

• The slice boundary is the interpreter's, on every lowered edge. region-jit.js's exact path publishes $gip and tests $smc || $halt || $steps < 0 at each edge, in the interpreter's order, and leaves through $out when it holds — where the epilogue's leave calls $slice_exit, exactly as GO would. The back edge uses the interpreter's >= 0, not a stricter > 0.
• Steps are billed per op per iteration, with the entry refund that gives back the one step $next charged to dispatch in. So a loop that runs 1000 iterations of 5 ops charges 5000, which is what the interpreter charged.
• $ip is re-resolved on the way out through (call $jlook (global.get $gip)), never from a baked arena address.

That last point is also what keeps this doc's other invariant. Because the exit re-resolves $ip, the block's trailing arena words are dead — the tree never steps over them and nothing else reads them — so the arena is still byte-for-byte the size an unfolded compile produced, and a fixup landing inside the block resolves harmlessly into a word nobody reads.

--no-tree-fold-loops turns just this half off; it is the A/B partner for everything below.

What it reaches

Of the six programs in the table above, only BRW builds loop trees (2 of its 5 handlers, covering 8 guest ops at 2 sites that --no-tree-fold-loops leaves as 3 handlers / 8 substitutions / 43 ops). The six witness programs are where the shape actually lives:

One run each at 20M with --handler-hist=1, gated against --no-tree-fold-loops. handler entries is the number to read — it is the real count of trips through dispatch, and it is the only one that can price a loop tree at all: the tree entries: line reports a loop tree's entries on their own and explicitly does not count its iterations, so $next trips removed understates the loop fold by exactly the trip count it removed.

CATWALK is what the feature is for: three loop handlers take a tenth of every dispatch the program makes, and no straight-line fold can reach them because the run they replace ends at the terminator. DADEMO3 builds the most loop trees (16) and gets the least out of them, which is the --handler-hist lesson again: count how often a shape runs, not how many of it exist. The frame hash is identical between the two arms in every row (the flag-off comparison for these six is the 80M witness table below).

The decline bucket was deliberately split per stem (loop: body breaks at <op>), so it is a work list rather than a wall. The measured answer is that the terminator was never the main barrier — the string group is: movsb/movsb32, lodsb/lodsw/lodsb32, stosb/stosb32, rep/repne account for most declines in every program (DADEMO3: 18 movsb32, 5 lodsb32, 1 lodsw32; B-STEEL: 7 lodsw, 2 lodsb, 1 repne), followed by out/in, the CL-shift stems and div. A DOS inner loop is usually a string loop, and a string op is not an expression.

The one thing it changes, and what it is not

Every frame hash is identical, everywhere it was checked — all six programs at 20M in all five arms, and all six witnesses at 80M. Interrupt counts, vector counts, dispatch counts and guest seconds are identical too.

What moves is DADEMO3's wav, and unlike the movers in the table above it is not install schedule: at --tree-fold-batch=1 it is the same moved value (442a46e9), not the flag-off one. --no-tree-fold-loops restores the flag-off wav byte for byte, so this is the loop fold and nothing else. The mechanism is visible in the report:

The interpreter was taking a handback at those blocks — one of them on a jump-table miss — 5918 times each. The folded loop iterates through them in place, so those handbacks do not happen; and because Machine.audioNow stamps port writes relative to the slice start and audioAdvance runs per handback, the same sound is rendered against a different slice grid.

This is the class region-live.js documents as "audio only": same picture, same interrupt count, a wav rendered against slices that started and ended elsewhere. It is not the $steps bug that class used to also contain — that one is fixed, by the exact protocol this fold inherits — it is the residue of removing a handback at all. --lattice-clock, which anchors the slice grid and the audio render to a quantum instead of to the last handback, is the instrument for it, and it is passed to both arms or to neither:

CATWALK and BLIQ are answered outright: anchor the grid and the two arms render byte-identical wavs, so what moved was the grid and not a value. --no-tree-fold-loops restores the flag-off wav for all three on the shipped clock, so the loop fold is the whole of the effect either way.

DADEMO3 is not, and that is the failing witness. Under the lattice clock its two wavs are the same length and agree byte for byte for the first 74% of the run, then differ in 4785 bytes of the remaining 184KB (2.6% of that tail). Interrupt counts are identical (177, plus 629 host-raised vectors), as are the frame, the dispatch count and the guest seconds.

The guest event that moves is the host's interrupt injection point, which is quantized to handbacks and not to the clock. --lattice-clock anchors where audio is rendered; it cannot anchor where an IRQ is delivered, because the host can only inject one between slices. Absorbing 18,228 handbacks coarsens that grain from 1703 to 2783 steps, DADEMO3's timer ISR is what drives its playback — out_8 is its single hottest handler at 16.4% of all dispatches — and so its port writes are stamped a few hundred steps from where they were. CATWALK and BLIQ do not have that dependency, which is why the lattice clock finishes the job for them and not for this one.

So the honest statement is: folding the terminator is frame-exact, interrupt-count-exact and $steps-exact, and it is not handback-exact, because absorbing a block transfer is the whole point of it. On a program whose audio is driven from an interrupt handler that is the last 26% of one wav. That is the same trade the region JIT already ships with as a page default; it is why --tree-fold stays opt-in, and why --no-tree-fold-loops is a documented switch rather than a bisector.

One allocator for the handler table's tail

--tree-fold and --region-jit were mutually exclusive, and the reason was two bugs at once. Both append their generated handlers through opts.regions, and both computed their first ordinal as HANDLERS.length — so their ordinals overlapped, and each one's module build passed only its own list, so whichever built last shipped a table that did not contain the other's handlers at all. An arena word written against a tree ordinal would then call a region, or call nothing.

The fix is tools/toyvm/extras.js: one append-only Extras allocator, owning the shared tail past HANDLERS.length, handed to both the TreeFolder and the LiveJit by run-dos.js. Both commit into it, every module build is handed the whole list, and an ordinal is never reused. The one hazard left is a straddle — the region JIT prepares a module (picking ordinals) at one slice and installs it at a later one, and the fold may commit in between — so the prepared bundle carries an extrasEpoch and install() declines and re-profiles if the epoch moved. Regions are named from their shared-tail ordinal (region_${base + idx}) rather than from 0, so a second install cannot emit a duplicate wasm function name.

Measured at 20M with the gate at 64, --tree-fold --tree-fold-hot=64 --region-jit against each flag alone:

BRW is the row that proves it: a region installed at 0x7adc and five tree handlers, two of them loops, live in one handler table in one run, and the frame is the flag-off frame.

Two tests pin it. test/test-toyvm-tree-fold.js runs its GATE_COM case under both flags at once — the region JIT declines on a program that small, so what that one guarantees is that both allocators run in one process and the screen is still the flag-off screen. test/test-toyvm-region-live.js adds the arm that matters: its side-exit program, which is built to make the JIT install, run with --tree-fold as well, asserting 1 region install and 3 tree handlers in one table and bx/si/bp and the frame identical to the interpreter's. Values are the assertion there and timing deliberately is not — a loop tree absorbs handbacks, so the wav grid is expected to move, while an ordinal collision shows up as arithmetic.

Which program the sampler picks moves between arms (ACCIDENT and CYCLE install alone and decline with the fold; B-STEEL declines either way). That is expected and not a regression: the fold changes what the profiling arms execute, so the region gate sees a different program. The frame is the invariant, and it holds in all four arms of all six programs.

The six witnesses at 80M, with both items in

--dispatches=80m --pit-clock --auto-key --sound-pref=sb --env=ULTRASND=220,1,1,11,7 --audio=FILE, plain against --tree-fold --tree-fold-hot=64:

All six frame hashes are identical between the arms and match the recorded baselines. BLIQ and CONTAGIO were already install-schedule movers before any of this work; CATWALK and BLIQ are proven grid-only by --lattice-clock above; DADEMO3 is the one witness whose wav is neither, and its mechanism is named above.

Timing

Not measured, and deliberately so. The three-arm table above was taken at load 11-13 and its control still moved 18%; the box was at load 62 while these counts were collected. Every number in these two sections is a count or a hash, and counts are the same on a loaded box. --handler-hist entries, handbacks and frame hashes are what this feature should be argued about, and interleaving on an idle machine is what a timing claim would need.

The arms for that run exist, so nobody has to reconstruct them. tools/toyvm/bench-dos.js gained two switches: treefoldhotnoloops, which holds the straight-line fold fixed and moves only whether a self-loop iterates inside its tree, and regionjit, which is now composable because the ordinals are. So the four-arm command is

node tools/toyvm/bench-dos.js PROG.EXE --reps=5 --cpu-time --dispatches=20m \
  --dispatch-drift=4096 \
  --variants=tailcall,tailcall+treefoldhot,tailcall+treefoldhotnoloops,tailcall+regionjit+treefoldhot

and it runs (checked on CATWALK). Read its control before reading its arms.

The corpus, gated, with all four items in

sweep-dos.js --dir=/tmp/demos --dispatches=8m --reps=1 --variants=tailcall, once plain and once --tree-fold --tree-fold-hot=64, then sweep-diff.js:

191 programs
REGRESSIONS: 0
WENT BLANK: 0
changed (frame and/or dispatches moved, still drawing): 0
recovered: 1    QUARTZ.EXE (timeout -> ok; the known QUARTZ flake)
unchanged: 190

Nothing in the corpus moves. This is a stronger result than the ungated sweep recorded above (42 changed, COLORS.EXE blank, ZOKDTPLN.COM two pixels), and the reason is the gate rather than anything about partial registers, flags, loops or ordinals: at --tree-fold-hot=64 over an 8M budget, most programs install nothing at all, and the ones that do install late enough that the install-schedule sensitivity those two rows documented never gets a chance to fire. The ungated numbers are the ones to quote for "what does substituting a module into a running machine cost"; these are the ones to quote for "is the shipping configuration safe".

One measurement error is worth recording because it is easy to repeat. sweep-dos.js takes --dispatches=, not --budget=; a --budget=8m is silently ignored and the run falls back to the default guest-seconds budget (44.06M dispatches here) and the default --reps=3. Comparing that against an 8M/1-rep baseline reports three regressions, one blank and 166 changed, every one of which is the 5.5x budget and none of which is the fold. Check the opts object recorded in both JSONs before running sweep-diff.js on them — it is there for exactly this.

What is next

The decline histogram is the work list, and the three relaxations it points at, in the order the corpus argues for them. Two of the three are now implemented — see DOS-tailored: partial registers and flags as values above — and are described here as they were originally argued for. Two further items that were not on this list are also in: the terminator now folds for a self-loop block (Folding the terminator), and the fold stacks on --region-jit (One allocator for the handler table's tail). What the terminator work leaves behind is a decline bucket split by stem, and it says the next thing to reach for is the string group — movsb/lodsw/stosb/rep are most of what stops a DOS inner loop from folding, ahead of out/in, CL shifts and div — and that those are not expression-tree material at all. They are rep-widening's territory, and the two mechanisms currently compete for the same blocks (DADEMO3's widened byte count drops from 844KB to 274KB when the fold takes them).

1. Alias disjointness. Today every load after a store in the same run is assumed to alias, and the run ends there. Most of those pairs are provably disjoint at compile time — two absolute addresses, two displacements off the same base register with different constants, a stack slot against a data segment. Each of those is a decision the compiler can already make from the operand words it has in hand, and each one that holds joins two runs into one.

2. Partial registers as insert/extract. An 8-bit write inside a 16-bit run is not unmodellable, it is unmodelled: AL is bits 0-7 of the promoted AX local and an 8-bit write is a mask-and-or on it. partial-reg is one of the two largest buckets in every program measured, so this is the biggest single number in the histogram — and it is also the one most likely to introduce a wrong answer, because it is the only relaxation that changes what a value means rather than merely what may be joined.

3. Flags as values. The fold refuses any op that reads flags, so a cmp in the middle of a run, an adc chain, and a shift by CL all end it. Inside a generated handler there is no reason for the flag state to live in globals at all: it could be locals, computed where a reader needs it and materialized only on the way out. That subsumes the flag consumer bucket and, more importantly, is what would let the terminator's own cmp join the run.

Beyond the three: the fold is static. It generates a handler for any block whose shape qualifies, hot or cold, which is why ACCIDENT generates 167 trees and 437KB of WAT to remove 1.8% of its dispatches while BRW generates 96 and 186KB to remove 16.8%. A hotness gate — fold only a block the run has actually entered often — would cut the module size and the build time by most of that, and the block-hit census (--block-hits) is already the signal.