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 --- 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 +- 34 files changed, 1315 insertions(+), 559 deletions(-) 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 (limited to 'chapter24') diff --git a/chapter24/README.md b/chapter24/README.md index 58e13f39..59a893d9 100644 --- a/chapter24/README.md +++ b/chapter24/README.md @@ -5,10 +5,12 @@ where `score` in the middle does not have to be repeated. The main compiler change is Interprocedural Sparse Conditional Constant Propagation (SCCP): an optimistic type solve which also discovers call-graph -edges. This snapshot still uses the earlier parser/type and memory machinery; -Chapter 25 currently contains the larger incomplete-types SSA redesign and -separate compilation. Independent correctness fixes will move backward first; -see the [backport review queue](../docs/chapter-backports.md). +edges. Memory follows Chapter 10b's lazy partitioning: BulkMemPhi represents +whole memory, MemPhi merges precise aliases, and allocations consume and produce +partial memory for their instance fields. During SCCP, memory Phis ignore +unreachable inputs and allocation results stay high until control reaches them. +Chapter 25 retains the larger incomplete-types SSA redesign, private constructor +memory, and separate compilation; see the [backport review queue](../docs/chapter-backports.md). You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter24) 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-chapter23...linear-chapter24) it to the previous chapter. @@ -299,22 +301,22 @@ both the cheaper first attempt and the mandatory fallback. 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`. All rows use **Chapter 24's compiler**, optimizer seed 123, and the same source/target combinations as the earlier cohort tables. These Windows results combine x86 SystemV/Win64 and RISC-V/ARM SystemV, -remeasured on 2026-09-28 after the function-pointer lifetime backport. +remeasured after the lazy memory forward port. | Program cohort | Compilations | Retained moves | Loop-weighted moves | |---|---:|---:|---:| -| Chapter 20 | 39 | 319 | 431 | -| Chapter 21 | 52 | 425 | 957 | +| Chapter 20 | 39 | 320 | 439 | +| Chapter 21 | 52 | 420 | 952 | | Chapter 22 | 26 | 67 | 67 | -| Chapter 23 | 30 | 81 | 228 | -| Chapter 24 | 67 | 418 | 1,286 | -| **Total** | **214** | **1,310** | **2,969** | +| Chapter 23 | 30 | 78 | 225 | +| Chapter 24 | 67 | 422 | 1,325 | +| **Total** | **214** | **1,307** | **3,008** | `_spills` counts retained SplitNodes, including register moves. `_spillScaled` weights those moves by `8^loopDepth`; it is a cost estimate, not measured memory diff --git a/chapter24/src/main/java/com/seaofnodes/simple/Parser.java b/chapter24/src/main/java/com/seaofnodes/simple/Parser.java index 14af367d..432ec137 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter24/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 the sys import _lexer = new Lexer(sys.SYS); @@ -222,7 +222,7 @@ public class Parser { // Build a multi-exit return point for all function returns RegionNode r = new RegionNode( 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); @@ -235,11 +235,8 @@ public class Parser { // external calls. _scope.push(new Kind.Func()); 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