From c4dcf6f751b35c7a2a3b46fa2d69b95d37d082a6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 30 Sep 2026 19:25:04 -0700 Subject: Finish forward-port mem ops thru ch25 --- README.md | 9 +- chapter22/README.md | 18 +- .../main/java/com/seaofnodes/simple/Parser.java | 105 +++++---- .../simple/codegen/GlobalCodeMotion.java | 55 +++-- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 240 +++++++++++++++++++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 200 +++++++++-------- .../java/com/seaofnodes/simple/node/LoopNode.java | 11 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 209 ++++++------------ .../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 | 96 +++++---- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/ReturnNode.java | 13 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 81 ++++--- .../java/com/seaofnodes/simple/node/StartNode.java | 11 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 34 ++- .../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 +- .../simple/print/SimpleGraphAdapter.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 119 ++++++++++ .../java/com/seaofnodes/simple/Chapter10bTest.java | 60 ++++++ .../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 | 70 +++++- .../java/com/seaofnodes/simple/Chapter20Test.java | 29 ++- .../java/com/seaofnodes/simple/Chapter21Test.java | 6 +- .../src/test/java/com/seaofnodes/simple/Eval2.java | 6 +- .../test/java/com/seaofnodes/simple/EvalArm64.java | 7 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 178 +++++++++++++++ .../com/seaofnodes/simple/evaluator/Evaluator.java | 12 +- chapter23/README.md | 16 +- .../main/java/com/seaofnodes/simple/Parser.java | 111 +++++----- .../simple/codegen/GlobalCodeMotion.java | 55 +++-- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 240 +++++++++++++++++++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 197 +++++++++-------- .../java/com/seaofnodes/simple/node/LoopNode.java | 11 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 210 ++++++------------ .../java/com/seaofnodes/simple/node/MemOpNode.java | 35 +++ .../com/seaofnodes/simple/node/MemPhiNode.java | 44 ++++ .../java/com/seaofnodes/simple/node/NewNode.java | 66 ++---- .../main/java/com/seaofnodes/simple/node/Node.java | 13 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 113 ++++++---- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/ReturnNode.java | 13 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 90 ++++---- .../java/com/seaofnodes/simple/node/StartNode.java | 11 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 35 ++- .../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 +- .../simple/print/SimpleGraphAdapter.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 119 ++++++++++ .../java/com/seaofnodes/simple/Chapter10bTest.java | 60 ++++++ .../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 | 25 ++- .../src/test/java/com/seaofnodes/simple/Eval2.java | 8 +- .../test/java/com/seaofnodes/simple/EvalArm64.java | 7 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 178 +++++++++++++++ .../com/seaofnodes/simple/evaluator/Evaluator.java | 12 +- chapter24/README.md | 24 ++- .../main/java/com/seaofnodes/simple/Parser.java | 111 +++++----- .../simple/codegen/GlobalCodeMotion.java | 55 +++-- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 240 +++++++++++++++++++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 197 +++++++++-------- .../java/com/seaofnodes/simple/node/LoopNode.java | 11 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 207 ++++++------------ .../java/com/seaofnodes/simple/node/MemOpNode.java | 35 +++ .../com/seaofnodes/simple/node/MemPhiNode.java | 44 ++++ .../java/com/seaofnodes/simple/node/NewNode.java | 76 ++----- .../main/java/com/seaofnodes/simple/node/Node.java | 13 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 113 ++++++---- .../com/seaofnodes/simple/node/RegionNode.java | 8 +- .../com/seaofnodes/simple/node/ReturnNode.java | 13 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 90 ++++---- .../java/com/seaofnodes/simple/node/StartNode.java | 11 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 35 ++- .../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 +- .../simple/print/SimpleGraphAdapter.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 119 ++++++++++ .../java/com/seaofnodes/simple/Chapter10bTest.java | 60 ++++++ .../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 | 27 ++- .../java/com/seaofnodes/simple/Chapter24Test.java | 4 +- .../src/test/java/com/seaofnodes/simple/Eval2.java | 8 +- .../test/java/com/seaofnodes/simple/EvalArm64.java | 7 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 177 +++++++++++++++ .../com/seaofnodes/simple/evaluator/Evaluator.java | 12 +- chapter25/README.md | 18 +- .../simple/codegen/GlobalCodeMotion.java | 49 ++--- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 238 ++++++++++---------- .../java/com/seaofnodes/simple/node/MemOpNode.java | 34 +++ .../main/java/com/seaofnodes/simple/node/Node.java | 1 + .../java/com/seaofnodes/simple/node/PhiNode.java | 106 ++++----- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 4 + .../simple/node/cpus/x86_64_v2/LoadX86.java | 5 + .../java/com/seaofnodes/simple/Chapter11Test.java | 2 + .../java/com/seaofnodes/simple/Chapter20Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 4 +- .../test/java/com/seaofnodes/simple/EvalArm64.java | 7 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 104 +++++++++ docs/chapter-backports.md | 86 ++++++-- skills/chapter25-codex-notes.md | 30 ++- 119 files changed, 4410 insertions(+), 1839 deletions(-) create mode 100644 chapter22/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java create mode 100644 chapter22/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java create mode 100644 chapter22/src/test/java/com/seaofnodes/simple/Chapter10bTest.java create mode 100644 chapter22/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java create mode 100644 chapter23/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java create mode 100644 chapter23/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java create mode 100644 chapter23/src/test/java/com/seaofnodes/simple/Chapter10bTest.java create mode 100644 chapter23/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java create mode 100644 chapter24/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java create mode 100644 chapter24/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter10bTest.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java diff --git a/README.md b/README.md index 056d0c2e..e75fa42a 100644 --- a/README.md +++ b/README.md @@ -83,10 +83,11 @@ 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 21, including constructors, -mutability, whole-memory function calls, instruction selection, and register -allocation and machine-code execution. Chapter 21 is ready for review; Chapters 22-24 still use their earlier -parser-managed alias chains. +memory representation now runs through Chapter 24, including constructors, +mutability, whole-memory function calls, machine-code execution, cyclic field +types, and SCCP. Chapters 22-25 are ready for review. Chapter 25 includes the +related Load-search, Phi-factoring, and scheduling corrections while retaining +its separate constructor-memory and incomplete-type SSA design. To build and test just the memory chapters: diff --git a/chapter22/README.md b/chapter22/README.md index 96c02ef1..426db34f 100644 --- a/chapter22/README.md +++ b/chapter22/README.md @@ -29,6 +29,12 @@ Let's break it down. pool*, and from there in an ELF file's RODATA section. +Chapter 10b's lazy memory partitioning continues here: the parser carries one +`$mem`, and BulkMemPhi/MemPhi discover field aliases during optimization. +Allocations consume a partial MemMerge and produce `{ptr, $mem}`; calls carry +whole memory. The loop Load search follows every arm of a memory merge, so +BrainFuck's invariant program length folds out of its main loop. + You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter22) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter21...linear-chapter22) it to the previous chapter. @@ -192,7 +198,7 @@ class is left for Chapter 23, cold loop splits for 24, and area/cost ranking for Chapter 21's adjacent-copy forwarding also carries forward: after coloring, a sole use in the next instruction can read the source register when its operand mask permits it and no two-address tie is broken. The table below -includes this cleanup. Cohort 22 now also includes the two zero-move C return +includes this cleanup and the lazy memory forward port. Cohort 22 now also includes the two zero-move C return ABI checks added since the earlier audit (26 entries instead of 24). Run `make spill-stats` in this directory. Each row below uses **this chapter's @@ -202,10 +208,10 @@ SystemV. Diagnostic graphs and mask regressions do not contribute to the totals. | Program cohort | Compilations | Retained moves | Loop-weighted moves | |---|---:|---:|---:| -| Chapter 20 | 39 | 321 | 433 | -| Chapter 21 | 52 | 438 | 970 | +| Chapter 20 | 39 | 324 | 443 | +| Chapter 21 | 52 | 432 | 964 | | Chapter 22 | 26 | 67 | 67 | -| **Total** | **117** | **826** | **1,470** | +| **Total** | **117** | **823** | **1,474** | `_spills` counts retained SplitNodes, including register moves; `_spillScaled` weights each by `8^loopDepth`. These are compiler estimates, not measured runtime @@ -225,7 +231,9 @@ The original Chapter 22 snapshot, which mixed several later heuristics, produced staged version saves 240 weighted moves (13.8%). Neither comparison should be confused with comparing entire compiler chapters: lowering also changes. For example, the frozen Chapter 20 String input has no explicit return, and Chapter -22's default-return handling eliminates that workload at the default seed. +22's default-return handling eliminated that workload in the earlier audit. +With lazy memory, some target compilations retain callable bodies; the current +table includes their moves. The full suite and statistics runner pass. Routine backend comparisons use a fixed optimizer seed: diff --git a/chapter22/src/main/java/com/seaofnodes/simple/Parser.java b/chapter22/src/main/java/com/seaofnodes/simple/Parser.java index 8132f782..7a60a2dc 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/Parser.java @@ -137,7 +137,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 the sys import _lexer = new Lexer(com.seaofnodes.simple.sys.SYS); @@ -207,7 +207,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); @@ -219,11 +219,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