diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/chapter-backports.md | 87 |
1 files changed, 81 insertions, 6 deletions
diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index c5a7841d..159bc9e6 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -69,7 +69,7 @@ Chapter 25 suite, including `make -j 4 tests`. | Group | Eventual home | Why not in the small queue yet | |---|---|---| -| Register allocation and spilling | 20 onward | Chapter 20 correction/support pass complete locally; review before Chapter 21. Staged quality work remains below. | +| Register allocation and spilling | 20 onward | Chapters 20-21 correction/support passes complete locally; review Chapter 21 statistics before Chapter 22. Staged quality work remains below. | | Conditional Store and array Load control | Memory/arrays chapters | Reproduce under the earlier alias model before extracting fixes from the new memory implementation. | | SCCP dependencies, function revival, reachability | 24; some foundations may fit 18 | Separate old-IR corrections from new Guard/Escape/BulkMemPhi and external-caller machinery. | | TypeScalar, numeric modes, guards, symbolic fields, open/forward types | Revisit earlier homes later | A connected incomplete-types architecture, including phase ordering and errors. | @@ -78,8 +78,8 @@ Chapter 25 suite, including `make -j 4 tests`. ## Register allocation: correctness first, staged improvements -Review on 2026-09-20. The staged plan follows; Chapter 20 -has since been implemented and validated as recorded below. Later snapshots +Review on 2026-09-20. The staged plan follows; Chapters 20-21 +have since been implemented and validated as recorded below. Later snapshots remain pending. Compared RegAlloc, BuildLRG, IFG, LRG, Coalesce, RegMask, and split support across 20-25, with the original fix commits. Allocation starts in 20; 19 has instruction selection/register masks @@ -153,16 +153,16 @@ to add persistent deferral state to the first allocator chapter. of the heuristic's exact spill count. - `splitBypass` originally scanned from `j-1` with `idx++` throughout 20-25, reaching its own destination and rejecting nonadjacent bypasses. Corrected - in 20 with intervening kill-mask checks and a regression; 21-25 remain pending. + in 20-21 with intervening kill-mask checks and a regression; 22-25 remain pending. Pre-color copy reuse also checks fixed-register definitions before they have an assigned `_reg`. Chapter 25 is not a complete correctness reference. Suggested execution order: support/measurement, small mask/LRG correctness fixes, constrained-register and self-conflict regressions/fixes, then one quality technique at a time. Run each affected snapshot's full suite at each -accepted boundary. Chapter 20 has now been implemented; do not proceed to 21 until Cliff reviews it. +accepted boundary. Chapters 20-21 have now been implemented; stop for Cliff's review before 22. Review each chapter's README along the way. Chapter 21's encoding discussion -should be shortened when that chapter is reached. End each README with its +has been shortened, with the bit-level notes retained as a separate reference. End each README with its RegAlloc improvement, measured cohort table, and commentary; the Chapter 25 table must have rows for cohorts 20-25 using the Chapter 25 compiler. @@ -206,6 +206,81 @@ Historical results below are dated evidence, not a substitute for a fresh baseline. Logs live in ignored build directories and may no longer exist. Reusable implementation lessons are in `skills/chapter25-codex-notes.md`. +### Inlined return typing and ARM emulator: corrected, 2026-09-20 + +The ARM seed-9 String failure was an optimizer bug: inlining can delete a FunNode +while its Return still carries live control, memory, and data. ReturnNode.compute +mistook the deleted entry for an unreachable return and supplied Top to its +caller. Chapter 20 introduced direct use of the linked Return's type, exposing +this stale guard. Removed it in 20-21, matching the existing 22-25 implementation. +Chapter 19 does not read that linked return type and passes the reduced probe. + +Reduced source: `struct S { int x; }; val f={ S s -> s.x=g(); }; +val g={ -> 123; }; S !s=new S; return f(s);`. The old 20 compiler returns null +instead of 123 at seed 58; 21 fails at seed 8. The regression checks interpreted +results across seeds 0-63 in Chapter20Test in every snapshot 20-25. + +Execution then exposed missing register-register SUB decoding in EvalArm64. +Added the unshifted SUB form already emitted by Simple in 21-25. The matching +Chapter21Test checks positive/negative results, 64-bit overflow, and preserved +flags; it traps with the old emulator. The original String source at seed 9 now +encodes and executes on both ARM and RISC-V, producing the independently computed +hash `-2449306563677080489`. All 1,170 encoding/register checks pass over the frozen +13-program cohort, three targets, and seeds 0-29. + +Fresh baselines passed before edits. Full suites after correction: 20: 376+1; +21: 401+1; 22: 399+1; 23: 418+1; 24: 441+1; 25's six groups: +8, 378, 34, 18, 1, 12. Spill totals are unchanged: Chapter 20 remains 236 splits / +355 weighted; Chapter 21's two cohorts remain 401/653 and 483/1,141. These regressions +are excluded from spill measurements. Logs/reducers are in each affected chapter's +ignored `build/arm-top`; the earlier chapter-by-chapter allocator review gate remains. + +### Chapter 21 allocator: ready for review, 2026-09-20 + +Carries the Chapter 20 legality/progress/support fixes into 21 while retaining +native frame/ABI handling and conservative coalescing. Stronger color bias, +clone/callee-save ranking, and popular-use grouping are deferred to the planned +later chapters. The existing loop-entry-tail treatment remains; removing it +increased weighted counts in a controlled trial. Coalescing's mask, interference, +capacity rollback, and adjacency-remapping checks pass. Five inherited regression +cases fail against the original compiler and pass now: mask iteration/empty masks, +resultless kills, incompatible clone/use classes (round limit), commutative Phi +uses, and copy cleanup across clobbers. The other two inherited cases already pass. + +`make -j 4 tests`: original 385 + 1; corrected 399 + 1 at the allocator boundary (401 + 1 after the return/emulator +corrections above), after forced rebuilds, +including native x86/Win64 and RISC-V/ARM emulator checks. All 1,170 allocation +and register-constraint checks pass for the 13 frozen Chapter 20 inputs, three +CPUs, and seeds 0-29. The subsequent encoding sweep also passes after the return-typing correction +recorded above; the original ARM seed-9 failure is resolved. +Native harnesses now retain full process exit codes, and ARM BrainFuck checks its +own result pointer. `make spill-stats` passes all 45 selected tests (43 at the allocator boundary) and records +91 compilations; spill-golden mismatches are deferred during reporting so they do +not suppress later targets/runtime checks, but still make the command fail. + +| Cohort, all using Chapter 21 | Compilations | Original splits | Current splits | Original weighted | Current weighted | +|---|---:|---:|---:|---:|---:| +| Chapter 20, three SystemV targets | 39 | 340 | 401 | 445 | 653 | +| Chapter 21, fixed Windows native/emulator suite | 52 | 454 | 483 | 1,175 | 1,141 | +| Total | 91 | 794 | 884 | 1,620 | 1,794 | + +Same corrected compiler without coalescing: 1,074 splits / 1,921 weighted; with +coalescing: 884 / 1,794, saving 190 / 127. Relative to the original combined +heuristics, staging costs 174 weighted moves (+10.7%). RISC-V BrainFuck is the +largest regression; sieve improves on all three targets. Do not claim an overall +quality improvement over the original snapshot. Chapter-to-chapter raw totals +also reflect changed lowering and native ABI obligations, not just coalescing. + +Frozen Chapter 20 sources (including original BrainFuck/MergeSort) now reside in +Chapter20Test. The four revised source/ABI cases formerly there are preserved in +Chapter21AllocTest and counted in 21; its native BrainFuck/MergeSort variants also +belong to 21. No diagnostic graphs count toward quality totals. The README now +summarizes encoding/ELF, links the retained encoding reference, and ends with +coalescing, both cohort rows, and the controlled comparison. Logs and isolated +baseline/ablation sources are under `chapter21/build/regalloc-review` (ignored). +The allocator changes remain confined to Chapter 21; the subsequent return/emulator +correction is recorded separately above. Chapter 22 allocator work awaits review. + ### Chapter 20 allocator: ready for review, 2026-09-20 Implemented only in 20, per Cliff's chapter-by-chapter review gate. Corrected |