From a996996a1ad776089a4cb9cbf7744f5f4e8dde6d Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 30 Sep 2026 16:41:07 -0700 Subject: Forward port mem stuff to ch21 Also a minor reg-alloc improvement for BrainFuck, ported up to ch25 --- README.md | 4 +- chapter21/README.md | 77 ++++++- .../main/java/com/seaofnodes/simple/Parser.java | 105 +++++---- .../com/seaofnodes/simple/codegen/CodeGen.java | 2 +- .../simple/codegen/GlobalCodeMotion.java | 55 +++-- .../com/seaofnodes/simple/codegen/RegAlloc.java | 16 +- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 240 +++++++++++++++++++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 194 +++++++++-------- .../java/com/seaofnodes/simple/node/LoopNode.java | 11 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 198 ++++++----------- .../java/com/seaofnodes/simple/node/MemOpNode.java | 35 +++ .../com/seaofnodes/simple/node/MemPhiNode.java | 44 ++++ .../java/com/seaofnodes/simple/node/NewNode.java | 61 ++---- .../main/java/com/seaofnodes/simple/node/Node.java | 13 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 91 +++++--- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/ReturnNode.java | 12 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 75 ++++--- .../java/com/seaofnodes/simple/node/StartNode.java | 11 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 28 +-- .../com/seaofnodes/simple/node/cpus/arm/arm.java | 2 + .../seaofnodes/simple/node/cpus/riscv/riscv.java | 2 + .../simple/node/cpus/x86_64_v2/LoadX86.java | 5 + .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 7 +- .../com/seaofnodes/simple/print/IRPrinter.java | 165 ++++++++++++++ .../simple/print/SimpleGraphAdapter.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 119 ++++++++++ .../java/com/seaofnodes/simple/Chapter10bTest.java | 60 ++++++ .../java/com/seaofnodes/simple/Chapter14Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter16Test.java | 23 ++ .../java/com/seaofnodes/simple/Chapter17Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter18Test.java | 66 ++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 68 ++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 35 ++- .../com/seaofnodes/simple/Chapter21AllocTest.java | 2 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 9 +- .../src/test/java/com/seaofnodes/simple/Eval2.java | 6 +- .../test/java/com/seaofnodes/simple/EvalArm64.java | 9 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 176 +++++++++++++++ .../simple/codegen/RegAllocTestSupport.java | 25 +++ .../com/seaofnodes/simple/evaluator/Evaluator.java | 12 +- chapter22/README.md | 18 +- .../com/seaofnodes/simple/codegen/RegAlloc.java | 16 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 4 +- .../com/seaofnodes/simple/Chapter21AllocTest.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 3 +- .../simple/codegen/RegAllocTestSupport.java | 25 +++ chapter23/README.md | 22 +- .../com/seaofnodes/simple/codegen/RegAlloc.java | 16 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 6 +- .../com/seaofnodes/simple/Chapter21AllocTest.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 3 +- .../com/seaofnodes/simple/Chapter23AllocTest.java | 2 +- .../simple/codegen/RegAllocTestSupport.java | 25 +++ chapter24/README.md | 20 +- .../com/seaofnodes/simple/codegen/RegAlloc.java | 16 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 4 +- .../com/seaofnodes/simple/Chapter21AllocTest.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 3 +- .../com/seaofnodes/simple/Chapter23AllocTest.java | 2 +- .../com/seaofnodes/simple/Chapter24AllocTest.java | 2 +- .../simple/codegen/RegAllocTestSupport.java | 25 +++ chapter25/README.md | 14 ++ .../com/seaofnodes/simple/codegen/RegAlloc.java | 16 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 3 +- .../simple/codegen/RegAllocTestSupport.java | 25 +++ docs/chapter-backports.md | 187 ++++++++++++++-- skills/chapter25-codex-notes.md | 55 ++++- 69 files changed, 2023 insertions(+), 574 deletions(-) create mode 100644 chapter21/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java create mode 100644 chapter21/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter10bTest.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java diff --git a/README.md b/README.md index 115168d9..056d0c2e 100644 --- a/README.md +++ b/README.md @@ -83,9 +83,9 @@ The top-level Makefile runs each chapter's `tests`, `tags` (also `tag`), The [chapter backport queue](docs/chapter-backports.md) records proposed small corrections and the per-chapter test/review workflow. Larger architectural moves are tracked separately there. The 10a/10b split is complete; forwarding 10b's -memory representation now runs through Chapter 20, including constructors, +memory representation now runs through Chapter 21, including constructors, mutability, whole-memory function calls, instruction selection, and register -allocation. Chapter 20 is ready for review; Chapters 21-24 still use their earlier +allocation and machine-code execution. Chapter 21 is ready for review; Chapters 22-24 still use their earlier parser-managed alias chains. To build and test just the memory chapters: diff --git a/chapter21/README.md b/chapter21/README.md index 21f2febf..3e082630 100644 --- a/chapter21/README.md +++ b/chapter21/README.md @@ -74,6 +74,23 @@ relocation are two stages of the same obligation to make references correct. ## Execute the result +Chapter 10b's lazy memory partitioning now carries through encoding. Parameters, +calls, and returns carry whole memory; `BulkMemPhi`, `MemPhi`, and `MemMerge` +discover precise aliases inside each function. New consumes `{ctrl, $mem, size}` +and produces `{ptr, $mem}`. Its memory covers the allocated struct's aliases; +the surrounding merge retains unrelated aliases. Nonzero initialization still +uses explicit Stores. Memory nodes and ordering edges require no registers. + +Scheduling follows aliases through aggregates to order reads before matching +Stores, allocations, and calls. Calls retain their argument lists, with no added +ordering operands. Synthetic loop exits collect precise memory by alias. + +The execution regressions cover constructors, non-inlined and recursive calls, +inlining, and array updates, using native x86 and both emulators. A full-width +x86 load uses the allocated register bank when choosing its encoding, since an +integer may reside in XMM. ARM emulation handles MOVZ/MOVK halfword construction +for the large constants in these checks. + `make tests` includes C harnesses that link and run generated x86 code, and RISC-V/AArch64 emulator checks. The tests compare results as well as spill counts. Native process failures retain their full exit status. Emulator checks must read @@ -85,7 +102,7 @@ is recorded without skipping the remaining targets or execution checks; any such mismatch still makes the command fail. Structural allocator regressions are excluded from the spill totals. -## RegAlloc improvements: conservative copy coalescing +## RegAlloc improvements: eliminating copies A split inserts a copy between two live ranges. If both can safely become one range, the copy can disappear before coloring. [Coalesce.java](src/main/java/com/seaofnodes/simple/codegen/Coalesce.java) @@ -99,6 +116,13 @@ to the deleted copy. A rejected merge restores the original adjacency list. Mask compatibility alone is insufficient: two values that are simultaneously live cannot share a register merely because both permit it. +After coloring, a copy with one use in the immediately following instruction +can also disappear when that operand accepts the source register and is not +its two-address operand. For example, `mov rpc=s8; st1 [rpc+4],s1` becomes +`st1 [s8+4],s1`. Adjacency proves that nothing overwrites the source in between. +Phi and control-flow users are excluded. This local cleanup leaves spill +selection unchanged; it complements coalescing without another CFG analysis. + Chapter 20's legality and progress fixes carry forward, including compatible rematerialization and clobber-aware copy reuse. Chapter 21 retains its native frame and ABI support. Stronger color bias and cheap-spill ranking are reserved @@ -110,11 +134,11 @@ These are measured sums with **this chapter's compiler**, default optimizer seed moves; it is not necessarily a memory spill. Weighted counts multiply each split by `8^loopDepth`. -| Test cohort | Allocations | Splits | Loop-weighted splits | +| Program cohort | Compilations | Retained moves | Loop-weighted moves | |---|---:|---:|---:| -| Chapter 20 | 39 | 379 | 484 | -| Chapter 21 | 52 | 461 | 972 | -| Total | 91 | 840 | 1,456 | +| Chapter 20 | 39 | 367 | 472 | +| Chapter 21 | 52 | 454 | 972 | +| **Total** | **91** | **821** | **1,444** | The Chapter 20 row freezes all 13 original inputs, including BrainFuck and MergeSort, on three SystemV targets. They live in `Chapter20Test`. The revised @@ -124,10 +148,47 @@ the Chapter 21 row. That row includes 17 ARM/SystemV, 17 RISC-V/SystemV, eight x86/SystemV, and ten x86/Win64 compilations. Native host ABI changes affect this row; compare the same host and targets. -| Controlled comparison, same 91 compilations | Splits | Loop-weighted splits | +Before adjacent-copy forwarding, the memory port changed the previous total of 840 / 1,456 to 845 / 1,559, +with identical cohort membership and allocator heuristics. These are all changed +rows; each entry is retained / loop-weighted splits: + +| Cohort / program | Target / ABI | Before | Lazy memory | +|---|---|---:|---:| +| 20 / MergeSort | ARM / SystemV | 44 / 44 | 41 / 41 | +| 20 / BrainFuck | RISC-V / SystemV | 35 / 42 | 37 / 58 | +| 20 / Alloc2 | x86 / SystemV | 3 / 3 | 4 / 4 | +| 20 / Alloc2 | ARM / SystemV | 10 / 10 | 9 / 9 | +| 20 / String | x86 / SystemV | 7 / 14 | 8 / 15 | +| 20 / String | RISC-V / SystemV | 14 / 14 | 10 / 10 | +| 20 / String | ARM / SystemV | 13 / 13 | 10 / 10 | +| 21 / Sieve | x86 / Win64 | 24 / 178 | 24 / 185 | +| 21 / Sieve | RISC-V / SystemV | 19 / 89 | 22 / 92 | +| 21 / Sieve | ARM / SystemV | 23 / 93 | 21 / 91 | +| 21 / BrainFuck | RISC-V / SystemV | 35 / 42 | 46 / 130 | + +RISC-V BrainFuck accounts for most of the weighted increase. A diagnostic run +omitting only read-before-New ordering changes its two rows to 35 / 42 and +37 / 58. That explains most of the cost; the compiler retains the ordering +constraint. No heuristic tuning is included in the memory port. + +The subsequent Load-search improvement folds BrainFuck's fixed program length +through the loop's N-way memory merge. Every backedge arm must fold or return +to unchanged memory for the same pointer. It removes 907 executed heap loads +in the RISC-V Hello World run and reduces stack traffic from 1,006 loads / 572 +stores to 15 / 15. Before copy forwarding, that row had 144 / 165 moves / weighted moves, +and the complete 91-entry total was 943 / 1,594. Adjacent-copy forwarding +reduces these to 35 / 42 and 821 / 1,444 respectively. The RISC-V Hello World +run executes 21,787 instructions instead of 21,920, with unchanged heap and +stack traffic. These are emulator instruction counts, not hardware timings. +The current native BrainFuck test and all runtime assertions are enabled. + +The following coalescing comparison predates lazy memory. Both sides use the +same compiler from that audit; it is not a fresh ablation of the current graph: + +| Earlier controlled comparison, same 91 compilations | Splits | Loop-weighted splits | |---|---:|---:| -| Current compiler with coalescing disabled | 1,070 | 1,889 | -| Current compiler with coalescing | 840 | 1,456 | +| Audit compiler with coalescing disabled | 1,070 | 1,889 | +| Audit compiler with coalescing | 840 | 1,456 | The controlled run disables only `Coalesce.coalesce` in `graphColor`. Allocation, register constraints, and runtime checks pass in both runs. The disabled run diff --git a/chapter21/src/main/java/com/seaofnodes/simple/Parser.java b/chapter21/src/main/java/com/seaofnodes/simple/Parser.java index fb108447..3b502c44 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/Parser.java @@ -138,7 +138,7 @@ public class Parser { _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, null, _lexer); ctrl(XCTRL); - _scope.mem(new MemMergeNode(false)); + _scope.mem(con(TypeMem.BOT)); // Parse whole program, as-if function header "{ int arg -> body }" parseFunctionBody(_code._main,loc(),"arg"); @@ -196,7 +196,7 @@ public class Parser { // Build a multi-exit return point for all function returns RegionNode r = new RegionNode((Lexer)null,null,null).init(); assert r.inProgress(); - PhiNode rmem = new PhiNode(ScopeNode.MEM0,TypeMem.BOT,r,null).init(); + PhiNode rmem = new BulkMemPhiNode(ScopeNode.MEM0,r,null).init(); PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null).init(); ReturnNode ret = new ReturnNode(r, rmem, rrez, rpc, fun).init(); fun.setRet(ret); @@ -208,11 +208,8 @@ public class Parser { // external calls. _scope.push(ScopeNode.Kind.Function); ctrl(fun); // Scope control from function - // Private mem alias tracking per function - MemMergeNode mem = new MemMergeNode(true); - mem.addDef(null); // Alias#0 - mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); // All aliases - _scope.mem(mem); + // Unknown callers supply whole memory; field aliases are discovered lazily. + _scope.mem(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); // All args, "as-if" called externally for( int i=0; i