GitHub

ADR-0044: Reachable Unique-Predecessor One-Operation Superblocks

Status: accepted; encoder policy 1.4.0 implemented and evidence-migrated

Date: 2026-07-30

Visibility: private NAUX architecture/governance record. This ADR is not public roadmap material.

Related: ADR-0037, ADR-0041, ADR-0042, ADR-0043

Preserves: target schema, lowering policy, target-plan semantics, ABI, Machine IR provenance, Bounds behavior, and every upstream semantic contract

Context

Encoder policy 1.3 reduced the fixed local Gate B ratio to about 5.87x, but the exact trace still executes:

block visits             51,067,120
tail jumps               38,484,078
frame memops            333,039,802
modeled x64 instructions 483,430,423

Only 53 of 139 target blocks remain reachable after policy-1.3 threading, composition, and compare fusion. The other 86 blocks retain 3,979 of 8,070 raw bytes but contribute no dynamic work. Dead-code pruning alone therefore does not move Gate B.

The weighted graph contains 16 reachable tail edges whose exact target entry:

  • has one reachable predecessor;
  • contains one target operation;
  • then tail-transfers or matches the existing exact compare-tail-branch fusion;
  • is not an external entry or otherwise address-taken label.

Those sites account for:

removable block visits                 13,318,189
removable ingress-copy memops          94,481,606
result store/reload upper opportunity  27,371,525
removable jumps                        13,318,189

Simple substitution into the target’s ordinary result home is unsound for the important F64 add/sub paths: that home overlaps a live-through caller value. The result must remain in a typed encoder-internal register until the final parallel transfer has a proven destructive-copy schedule.

Decision drivers

  • Optimize only reachable work weighted by the unchanged Gate B trace.
  • Preserve target-plan semantics; this is a raw realization policy.
  • Require exact, unique typed substitution at every crossed function boundary.
  • Retain simultaneous tail-assignment and Bounds ordering.
  • Refuse cycles, ambiguous homes, live-through clobbers, unsupported types, or exhausted traversal without weakening the ordinary encoding.
  • Keep the increment narrower than global register allocation.
  • Remove dead encoded bodies only when reachability and predecessor authority are reconstructed from the same encoder policy.

Decision

1. Policy identity

Set:

X64_TARGET_ENCODER_POLICY_VERSION = 1.4.0

The target schema and lowering policy remain unchanged. Policy 1.4 changes only the deterministic realization of the already verified target plan. Acceptance of this encoder policy does not close Gate B.

2. Reconstruct the emitted graph

Before emitting block bodies, reconstruct the finite graph that policy 1.3 would actually target after:

  • exact compare-tail-branch fusion;
  • exact no-op target threading;
  • direct-acyclic empty-tail composition;
  • both arms of every remaining branch.

Starting at the threaded program entry, compute reachability and reachable predecessor counts with checked work bounded by target structural limits. Unknown labels or malformed transfers remain encoding errors. Traversal cycles terminate through a visited set.

Every declared label is still marked exactly once and must retain a unique in-blob offset. An unreachable or uniquely consumed body is represented by one deterministic, unreachable NOP tombstone byte; labels never share an offset. No reachable fixup may target an omitted body.

3. Eligibility

A crossed entry is eligible only when:

  1. it is reachable and has exactly one reachable predecessor;
  2. the predecessor reaches the entry through the canonical selected tail route;
  3. it is not the external program entry;
  4. it contains exactly one supported instruction;
  5. its operands are parameters, the instruction result, or canonical immediates that can be mapped uniquely;
  6. its continuation is a tail transfer or the already proven exact compare-tail-branch shape;
  7. all target labels and callees are exact declared entries;
  8. the complete chain remains bounded and acyclic.

Failure of any item retains the ordinary source terminator and target body.

4. Typed parameter substitution

Map every exact callee parameter home to the corresponding predecessor argument. Substitute only through a unique full X64Home match. Duplicate parameter homes, unbound homes, arity mismatch, or type mismatch refuse the superblock.

Logical target-plan homes are not globally reinterpreted. Substitution exists only inside this encoder proof and cannot change plan evaluation or artifact verification.

5. Encoder-internal scalar result

For a tail-continuing one-operation target, evaluate the operation into a typed internal value:

Unit / Bool / I64 -> R8
F64               -> XMM2

F64Array register results and ArrayGetF64Checked are outside the accepted policy. ArrayLenF64 may participate only through its typed frame-resident array input. This keeps both ordered Bounds exits entirely on the ordinary checked-access path.

The internal value has no frame source words. It may be consumed only by the final tail transfer proven in the same superblock. It never appears in target serialization or becomes a general virtual register.

6. Generalized final parallel copy

After substituting the continuation, rerun a deterministic direct-copy schedule:

  • frame sources contribute their exact word locations;
  • the internal register source contributes no frame word;
  • destinations must be unique and non-overlapping;
  • a destination may be written only after its old words are absent from all remaining frame sources;
  • the internal register is written to its exact typed destination when chosen.

If the schedule is cyclic, overlapping, ambiguous, or otherwise incomplete, refuse the complete superblock. Do not stage an internal register through an invented plan home.

7. Compare continuation

For an eligible one-operation target whose continuation is the exact compare-tail-branch shape from ADR-0042, the conservative first policy may:

  1. perform the predecessor’s already validated direct state transfer;
  2. remove the intermediate jump and block boundary;
  3. emit the existing proven compare-branch template in place;
  4. retain the canonical Bool store unless a separate liveness proof removes it.

This does not invent argument state on branch successors.

8. Maximal chains and fallback

Apply eligible crossings transitively to form a maximal deterministic chain. The chain owns a visited set and a hard work bound. Any failure rejects the entire proposed crossing at that point and emits the remaining ordinary route.

Malformed input remains an error. A valid program outside the proof subset retains the cached ordinary encoding. Planning or optimized-emission refusal after ordinary encoding succeeds returns that ordinary encoding deterministically.

Forecast recorded at proposal time

The conservative trace model predicts:

tail-register ingress memops removed      73,509,696
result memops removed                     23,177,156
jumps removed across all 16 sites         13,318,189
modeled x64 instructions removed at least 110,005,041  (22.75%)
frame memops removed                       96,686,852  (29.03%)
block visits removed                       13,318,189  (26.08%)

Static unreachable-body pruning removes 3,979 bytes. Estimated additional internal transfer/jump removal is about 966 bytes before shorter register templates; the expected target is roughly 3,125 bytes. These are predictions, not admitted measurements. The accepted unique-offset invariant retains one NOP byte per omitted label, so the original zero-body estimate was necessarily optimistic. The forecast is retained here to distinguish the original decision basis from the measurements below.

Accepted implementation and measured result

The accepted implementation uses encoder policy 1.4.0 with:

  • reachability and predecessor reconstruction from the same transformed CFG used by emission;
  • maximal disjoint chains of reachable, exact one-operation entries;
  • typed internal R8 and XMM2 generations with stale-generation refusal;
  • word-precise acyclic final-copy scheduling;
  • one-byte NOP tombstones for every unreachable or consumed declared body;
  • cached ordinary-encoding fallback on planning or optimized-emission refusal.

The exact R1-S7a target changes are:

BranchMix code bytes       8,070 -> 3,097  (-61.62%)
BranchMix fixups             162 ->    51
BranchMix semantic bytes  44,863 -> 38,558
Bounds code bytes             726 ->   488  (-32.78%)
Bounds fixups                  14 ->     9

The locked policy-1.4 target identities are:

BranchMix semantic  a642bcc02f2ea3566b0d5f275780e5cbbefe007b46a0eaa5578f3f680f838e95
BranchMix code      ef32051c5c7af81365eee82664636f0a82bef5b1de3a8e3dcc07c2c207d7ce54
Bounds semantic     06e8a4cd6d1a7df57229180248c9f0040c9aa7781e1f38dea60e3f6a8f1c6251
Bounds code         c80220666bc16c99bd2c2a0570e418cc47462e0cdf8c7483530a8c7c149fee19

The migrated ordered evidence identities are:

R1-S7a 51-case correspondence  fe9cbcaf67798b502e8405eecb0228b7453d39427e97e4d404c7cd1356c8c49d
R1-S7b native correspondence   73ecf90e2fff7a36a6011e447c0982ca317f591aea45486f55c330d8dc12d22c
R1-S7b isolated process        7700c126528db9bbe810f5396129d155da407d365e1dfa12e346adfbd5df37e1
R1-S8 standalone process       22897dc524804625751f027a820bb75f4da3f7e77afca5183bc1522542418b85

Focused raw-encoder tests pass 25/25, R1-S7a passes 9/9, and R1-S7b passes 10/10. All 51 cases preserve target-plan, in-process native, process-isolated native, and standalone-process outcome/effect parity. Positive and adversarial tests cover fallback, cycles, overlap, multiple-predecessor refusal, stale register generations, Bounds-preserving array exclusion, and label/fixup integrity. Two independent read-only correctness audits found no blocker.

Three policy-1.4 release-mode Gate B observations measured:

run  NAUX median*2  baseline median*2  local ratio  vs policy 1.3
  1      62,402,943           12,939,397     4.822709x     -17.84%
  2      62,537,517           13,038,023     4.796549x     -18.29%
  3      62,297,934           12,753,051     4.884944x     -16.78%

The three ratios span about 1.85%, so the directional improvement is reproducible locally. The first and third runs rejected baseline variance; the second rejected both variance checks. The local-only claim rejection therefore worked as designed: Gate B remains open, and none of these ratios is an admitted portable performance claim.

Admission gates

Policy 1.4 was evaluated against all of the following:

  1. focused positive and adversarial raw-encoder tests;
  2. exact target-plan versus raw-native differential parity;
  3. Bounds, NaN, signed-zero, array-shape, cycle, overlap, multiple-predecessor, and label/fixup rejection coverage;
  4. deterministic byte/hash reproduction;
  5. full R1-S7a, S7b, IPC, R1-S8, ELF, and 51-case process evidence migration;
  6. strict formatting, Clippy, workspace, and governance gates;
  7. the unchanged ADR-0041 Gate B sampler records the directional local improvement while retaining its independent reproducibility and claim- admission checks;
  8. no claim of Gate B closure unless the admitted ratio is <= 2.0x.

Correctness, evidence migration, deterministic replay, fail-closed coverage, and material local improvement passed. The baseline-variance failure rejects Gate B closure, not the encoder-policy improvement. Policy 1.4 is therefore accepted while Gate B remains explicitly open.

Consequences

Positive

  • Removes a material portion of the dominant dynamic stack-home traffic.
  • Establishes a small typed register-residency proof without committing to a general allocator.
  • Prunes code already proven unreachable by the encoder’s own graph.
  • Keeps source semantics, Machine IR, target plan, ABI, and lowering policy unchanged.
  • Provides a bounded bridge toward later supercompilation-style driving and verified regional allocation.

Negative

  • Enlarges the raw encoder and independent replay surface.
  • Requires complete downstream identity migration.
  • Multiple-predecessor one-operation blocks remain unfused.
  • Aggregate register values and cyclic final transfers remain unsupported.
  • Static code layout changes substantially, so fixup and oracle evidence must be regenerated.

Risks and mitigations

  • Live-through value clobber: keep the operation result in a typed internal register and accept only a complete generalized schedule.
  • Graph disagreement: derive reachability, predecessor count, omission, and emission from one canonical post-policy graph.
  • Bounds reordering: retain both checks before any continuation mutation.
  • Silent partial fusion: fail closed at each crossing and keep the ordinary path.
  • Benchmark overclaim: retain local-only claim rejection and the fixed baseline/sampler contract.