diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-07 19:10:51 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-07 19:10:51 -0700 |
| commit | 2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc (patch) | |
| tree | c297b19a448bc3e0780437122646183240437a30 /docs/chapter-backports.md | |
| parent | aaec6f8136df6f7020bfc05f79ff5273adf73de1 (diff) | |
| download | Simple-2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc.tar.gz Simple-2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc.zip | |
Towrds getting RA spill counts comparable
Ignore JIGs. Get test suites more conical, so reg alloc spill counts are comparable
Diffstat (limited to 'docs/chapter-backports.md')
| -rw-r--r-- | docs/chapter-backports.md | 129 |
1 files changed, 124 insertions, 5 deletions
diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 4b516036..fdc4eff4 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -465,6 +465,25 @@ lines beyond the original extraction. ## Pending corrections +- **Chapter 25 deterministic inlining (deferred until after the Chapter 25 split).** + As of 2026-10-07, ordinary functions reject `_approxUIDs >= 100` before checking + the optimized body. `_approxUIDs` counts node IDs consumed during parsing and + is not refreshed after optimization. In the now-private Chapter 20 String + replay, `_hashCodeString` is rejected at 100 although its live body has 25 + nodes. MergeSort's `_merge` is rejected at 182 although its body has 54; + both are below the ordinary live-body threshold of 100. A shadow build removing + only that early rejection inlines both helpers and drops their out-of-line + bodies; MergeSort retains its recursive `_split_merge` as expected. The + ordinary-function policy is unchanged. Cliff deferred the larger repair until + after splitting Chapter 25: converge shrinking rewrites, then choose one growing + inline deterministically using current body sizes cached per convergence round. + Stable call-site provenance must break ties rather than randomized worklist + order or newly assigned node IDs. Avoid dependencies on every body node and + repeated scans during each peephole. The bounded boilerplate check below is + the small interim heuristic; the larger constructor parse allowance was replaced. + Evidence: + `build/ra-repair/inlining{,-ablation}.log`. + - **Chapter 24 Load BOTTOM-on-error backport, unwound/deferred (2026-09-28).** Cliff requested starting with 24 and analyzing failures before proceeding. Literal global BOTTOM memory/pointer inputs already propagate BOTTOM. The @@ -579,9 +598,11 @@ Chapter 25 suite, including `make -j 4 tests`. ## Register allocation: completed chapter progression -The allocator review is complete through Chapter 25. Each README ends with the -introduced technique, measured program cohorts, and commentary. `make spill-stats` -reports actual retained moves, per target and cohort, with assertions enabled. +The allocator review is complete through Chapter 25; Cliff reviewed Chapter 23 +on 2026-10-07. Each README ends with the introduced technique, a triangular +matrix of fixed cohorts across compiler chapters, and commentary. The current +[spill-cost matrix](regalloc-spills.md) is regenerated by root `make spill-stats`, +which checks matching test/CPU/ABI membership with assertions enabled. | Chapter | Additional technique | Final cohort sizes | |---|---|---| @@ -590,7 +611,7 @@ reports actual retained moves, per target and cohort, with assertions enabled. | 22 | Stronger copy-chain/backedge bias and cheap-spill ordering | 39, 52, 26 | | 23 | Group popular single-def uses by compatible register classes | 39, 52, 26, 30 | | 24 | One cold-only attempt for loop-Phi self-conflicts, then mandatory fallback | 39, 52, 26, 30, 67 | -| 25 | Existing area/cost ranking and later conflict strategies | 39, 52, 24, 30, 67, 14 | +| 25 | Existing area/cost ranking and later conflict strategies | 39, 52, 26, 30, 67, 14 | Shared corrections include RegMask/LRG bookkeeping, null use masks, kills without an output LRG, self-conflict splitting, compatible rematerialization, clobber-aware @@ -614,7 +635,7 @@ registers removes that conflict. Encoding must then use the allocated register bank, with five-bit register numbers, for both immediate and indexed loads/stores. The emulator must preserve floating bits and scale double offsets by eight. -Chapter 25 freezes the 212 earlier compilation entries in +Chapter 25 freezes the 214 earlier compilation entries in [documented source fixtures](../chapter25/src/test/java/com/seaofnodes/simple/spill/README.md). Constructor/library adaptations change IR, so this is a program-cohort comparison, not identical machine graphs. Those rows replay allocation and legality checks; @@ -656,6 +677,104 @@ The top-level runner accepts explicit chapter lists, e.g. ## Validation record +- **Ignore debugging Jigs (2026-10-07).** All `testJig*` methods are scratch + placeholders, not regression tests. Added missing `@Ignore` annotations in + Chapters 14-25, preserving their bodies, and removed all 15 Jig entries and + four unused frozen sources from Chapter 25's replay corpus. Cohorts 23/24 now + have 24/58 allocations; the corpus has 199 entries. The debug Fibonacci in + Chapters 22-24's `progs/jig.smp` uses private `_fib`; `fib.smp` and the genuine + `testFibExport` fixtures retain their exports, as confirmed by Cliff. + Full Make suites pass in all 13 affected snapshots, including 17a/17b and + Chapter 25's native groups, plus shared printer/ISA checks. Fresh spill reports + pass in 20-25, and every retained raw/scaled allocation record matches its + prior measurement. Cohort 23 is now 103/103/152 across compilers 23/24/25; + cohort 24 is 1,387/1,503 across 24/25. The historical heuristic comparison was + recomputed from saved records with the same exclusions. All tables refreshed. + A Chapter 25 allocation probe confirms the private debug Fibonacci leaves + only `<clinit>`, with no separate Fibonacci body. Logs: `build/jig-cleanup/`. + +- **Tiny-body inlining backport, Chapters 20-24 (2026-10-07).** Preserved Cliff's + reusable static 15-node worklist and Return-input/prefix dependencies. These + chapters previously supported only single-caller inlining, so the port adds + restricted copying of straight-line Store/MemMerge bodies, substituting call + arguments and control directly. Growing inlines run from a separate worklist + after ordinary peepholes settle; existing single-caller inlining is unchanged. + Constructor defaults already expand directly in these chapters; they have no + Chapter 25-style constructor calls or parse-size gate to relax. All full Make + suites pass: 406/445/466/488/518 tests respectively, plus each fuzzer wrapper. + The existing `Chapter18Test.testInline` graph now contains literal `1` on one + branch; no new permanent tests were added. Disposable two-call store probes + pass with seeds 123/456/789 in all five chapters, including an intervening store + to another alias. All 39/91/117/147/214 allocation records, including raw and + scaled costs, match the prior reports exactly. Logs: `build/tiny-inline/final*.log`. + Chapter 25 code and the deferred general inliner redesign are unchanged. + +- **Bounded tiny-body inlining (2026-10-07).** Replaced the constructor-specific + 1,000-node parse allowance with a conservative at-most-15-node check when the + parse estimate exceeds the normal limit. It recognizes entry/parameter/store/ + memory-merge/Return boilerplate, follows uses to avoid sparse alias arrays, + bounds fanout, and stops at Return. Dependencies watch Return inputs and only + the inspected prefix/frontier; failed checks can retry after folding. Actual + body limits remain 100, or 200 for `<new>` and instance `<init>`. All six replay + constructor calls still fold, and all 228 raw/scaled allocation records match + the preceding allowance trial. Full Chapter 25 Make tests pass, as do fresh + Win64/SystemV library compilations. Disposable probes force parse estimates + to 10,000 on Bubble Sort initializers and verify successful inlining/allocation + on all three targets. A dependency probe verifies requeueing without a Return + type change, rejection above the small-body bound, and acceptance after a + memory-chain fold. Logs: `build/tiny-inline/`. The general inliner redesign + remains deferred until after the chapter split. + +- **Chapter 25 constructor inlining allowance (2026-10-07).** `<new>` and + instance `<init>` share a 200-node optimized-body limit, including the cloning + assertion. A 1,000-node parse-time cutoff accommodates nested-method and + memory construction overhead; ordinary functions stay at 100 for both gates. + The initial 200/200 trial changed none of 228 allocation records. The larger + parse allowance removes all six remaining constructor calls in the frozen + replay sources (Bubble Sort), while public constructor definitions remain. + Cohorts 20-23 are unchanged; cohort 24 improves 1,637 to 1,634, while cohort 25 + rises 1,829 to 1,862. Win64 sys improves 842 to 809, Dijkstra 584 to 582; + FileIO rises 293 to 361. Fresh SystemV sys improves 803 to 777. These static + move costs do not establish a runtime improvement. Full Chapter 25 Make tests + pass (405 + 39 + 9 + 23 + 1 + 19), and the complete spill report passes its + 214 replay allocations and native/system tests. No goldens, replay sources, + seeds or memberships changed during this experiment. Matrices are refreshed. + Earlier compiler snapshots are unchanged: 20-24 have single-use non-cloning + inlining rather than this size-based cloning gate. Logs: `build/ctor-inline/`. + +- **Chapter 25 function constants and private helpers (2026-10-07).** + Single-use, single-definition function addresses separated from their use in + the same block get priority for rematerialization over spilling callee-save + registers. Adjacent, multi-use and cross-block cases keep the existing ranking. + On unchanged inputs this removes all 28 C-return initializer moves, plus 13 + weighted moves from cohort 24 and 22 from cohort 25, with no other cohort + changes. Eleven replay fixtures separately mark local helpers/classes private; + exported interfaces stay public. Final Ch25 weighted costs by cohort are + 491 / 1,077 / 71 / 380 / 1,637 / 1,829, with unchanged membership and counts. + The fixture README and matrix document the changed visibility baseline. + Full `make -C chapter25 tests` passes (405 + 39 + 9 + 23 + 1 + 19 tests), + as do both complete spill reports and fresh SystemV sys encoding on Windows + (327 raw / 803 weighted moves). The reports each include 214 replay allocations, + fresh Win64 library encoding and 23 native/system tests. No inlining-policy + change or earlier-chapter allocator change was made. Logs: `build/ra-repair/`. + +- **Spill matrices and bounded CI processes (2026-10-07).** Reran Chapter 20-25 + statistics with fixed cohort sizes 39, 52, 26, 30, 67, and 14. Chapter 25 now + includes the two Chapter 22 C-return ABI cases missing from its old manifest. + The matrix generator checks the multiset of test/CPU/ABI identities and emits + no totals row; each README shows columns through its chapter. Chapter 23's + copied Java implementation snippets are replaced with direct source links. + CI run 37675851863 timed out in `nm` after 10 seconds; run 37678408500 passed. + The bounded GCC/nm/test-executable calls now allow 60 seconds and retain + forced termination and captured stdout/stderr, with PID/CPU-time diagnostics. + CLI subprocesses retain their existing unbounded behavior. Root `make + spill-stats` passes and reproduces the matrix; the reporter rejects changed + membership even when counts match, and rejects failed runs. All 23 Chapter 25 + system tests pass. An 11-second subprocess passes the new bound; an intentional + hang is killed at a short test deadline with diagnostics and no live child. + Logs: `build/spill-stats/`, `build/ci-timeout-60-tests.log`, and + `build/ci-timeout-60-probe.log`. + - **Numeric assignment conversions and evaluators (2026-10-07).** Chapters 14-25 accept float-to-integer assignment using ToIntegerNode: truncate toward zero, saturate to i64 on overflow, map NaN to zero, then apply the declared |
