Towrds getting RA spill counts comparable

Ignore JIGs.  Get test suites more conical, so reg alloc spill counts are comparable

12 files changed, 150 insertions, 99 deletions

diff --git a/chapter21/README.md b/chapter21/README.md
index b8d065ff..63b02ae9 100644
--- a/chapter21/README.md
+++ b/chapter21/README.md
@@ -135,109 +135,34 @@ excluded from the spill totals.
 
 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)
-checks that the ranges do not interfere, intersects their allowed-register masks,
-and combines their neighbors. It merges only when the resulting neighbor count
-is smaller than the number of available registers. This simple conservative rule
-preserves a color choice even if every neighbor takes a different register.
-
-Merging also updates neighboring adjacency lists and removes sample references
-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.
+checks that the ranges do not interfere, intersects their allowed-register
+masks, and combines their neighbors.  It merges only when the resulting
+neighbor count is smaller than the number of available registers - meaning it
+can always color.
 
 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
+`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
-for Chapter 22, popular-use grouping for 23, cold-first loop splitting for 24,
-and area/cost ranking for 25.
+For looking at allocator progress, we will keep a table of weighted spill costs
+a chapters' tests - and use the later chapter compiler and register allocator
+on them.  The later chapters also modify the graph (sometimes adding boiler
+plate graph) so its not really a 100% fair comparison of how well this
+*heuristic* does, but it does give us some idea that we're not losing ground.
 
-These are measured sums with **this chapter's compiler**, default optimizer seed
-123, on Windows x86-64. A split is a retained `SplitNode`, including register
-moves; it is not necessarily a memory spill. Weighted counts multiply each split
-by `8^loopDepth`.
+Rows are fixed test cohorts; columns are the compiler/allocator chapters.  Each
+cell is the sum of `_spillScaled`: retained split moves, including register
+copies, weighted by loopDepth.  Lower is better.  **# tests counts
+compilations** (program/CPU/ABI cases), including zero-spill cases, rather than
+JUnit methods.  The count and membership of each row stay fixed across columns.
 
-| Program cohort | Compilations | Retained moves | Loop-weighted moves |
+<!-- spill-matrix:start -->
+| Test cohort | # tests | Ch 20 | Ch 21 |
 |---|---:|---:|---:|
-| Chapter 20 | 39 | 380 | 576 |
-| Chapter 21 | 52 | 467 | 1,076 |
-| **Total** | **91** | **847** | **1,652** |
-
-The Chapter 20 row freezes all 13 original inputs, including BrainFuck and
-MergeSort, on three SystemV targets. They live in `Chapter20Test`. The revised
-sources/ABI cases previously in that file are retained in `Chapter21AllocTest`;
-together with `Chapter21Test` and the native BrainFuck/MergeSort tests they form
-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.
-
-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.
-
-Restoring GCM's anti-dependence dominator walk subsequently changes each
-RISC-V BrainFuck row from 35 / 42 to 48 / 146, giving the current table above.
-A conditional writer need not dominate a later Load placement, so checking
-only the writer's exact block misses required ordering. The restored walk
-fixes a read-before-conditional-store program that returned 140 instead of 120.
-Both BrainFuck execution checks and the complete 91-entry spill audit pass;
-the increased move count is recorded without changing allocator heuristics.
-
-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 |
-|---|---:|---:|
-| 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
-reports nine changed spill goldens and exits unsuccessfully, as intended.
-Coalescing saves 230 moves (21.5%) and 433 weighted moves (22.9%). Local increases
-can still occur; the aggregate, rather than one example, judges the tradeoff.
-
-The final audit backported narrow x86/RISC-V store masks and corrected ARM
-register-bank selection and floating-point memory operations. Restricting byte
-stores to legal registers lowers RISC-V BrainFuck from 211 to 42 weighted moves
-in each of its two cohorts, reducing the previous table by 44 raw / 338 weighted
-moves. These correctness fixes are included on both sides of the comparison.
-Earlier measurements made with the broader masks are historical, not the current
-baseline. Chapter 20's 357 weighted moves are not a coalescing baseline either:
-Chapter 21 changes machine lowering and implements native ABI obligations.
+| Ch 20 | 39 | 360 | 576 |
+| Ch 21 | 52 |  | 1,072 |
+<!-- spill-matrix:end -->
+
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java
index ded3da7e..7c2f1b0c 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -46,7 +46,12 @@ public class IterPeeps {
 
     private final WorkList<Node> _work;
 
-    public IterPeeps( long seed ) { _work = new WorkList<>(seed); }
+    private final WorkList<CallEndNode> _workInline;
+
+    public IterPeeps( long seed ) {
+        _work = new WorkList<>(seed);
+        _workInline = new WorkList<>(seed);
+    }
 
     @SuppressWarnings("unchecked")
     public <N extends Node> N add( N n ) { return (N)_work.push(n); }
@@ -57,12 +62,24 @@ public class IterPeeps {
      * Iterate peepholes to a fixed point
      */
     public void iterate( CodeGen code ) {
+        while( true ) {
+            iteratePeeps(code);
+            CallEndNode cend;
+            while( (cend=_workInline.pop())!=null )
+                if( cend.inlineSmall() ) break;
+            if( cend==null ) return;
+        }
+    }
+
+    // Only try growing inlines once the shrinking peepholes reach a fixed point.
+    private void iteratePeeps( CodeGen code ) {
         assert progressOnList(code);
         int cnt=0;
 
         Node n;
         while( (n=_work.pop()) != null ) {
             if( n.isDead() )  continue;
+            if( n instanceof CallEndNode cend ) _workInline.push(cend);
             cnt++;              // Useful for debugging, searching which peephole broke things
             var obs = CodeGen.CODE._obs;
             if( obs != null ) obs.before(n);
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index 81992327..47e80ca9 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -99,6 +99,99 @@ public class CallEndNode extends CFGNode implements MultiNode {
         return null;
     }
 
+    // Clone only tiny, straight-line boilerplate, after ordinary peeps settle.
+    // Larger bodies still use the existing single-caller, non-cloning inline.
+    public boolean inlineSmall() {
+        if( isDead() || _folding || nIns()!=2 || !(in(0) instanceof CallNode call) ) return false;
+        Node fptr = call.fptr();
+        if( !(fptr instanceof ConstantNode) ||
+            !(fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && tfp.isConstant()) )
+            { addDep(fptr); return false; }
+        if( call.err()!=null ) return false;
+        ReturnNode ret = (ReturnNode)in(1);
+        FunNode fun = ret.fun();
+        if( fun._folding ) return false;
+        int len = smallBody(fun);
+        if( len==0 ) return false;
+        // All callers consume the three normal return projections.
+        for( Node use : _outputs )
+            if( !((use instanceof ProjNode p && p._idx>=0 && p._idx<3) ||
+                  (use instanceof CProjNode cp && cp._idx==0)) ) return false;
+
+        // Substitute control and arguments directly; no new function identity,
+        // parameter Phis, or return address is needed for this straight line.
+        Node[] copy = new Node[len];
+        for( int i=0; i<len; i++ ) {
+            Node n = TINYBODY[i];
+            copy[i] = n==fun ? call.ctrl() :
+                n instanceof ParmNode parm ? (parm._idx==0 ? null : call.arg(parm._idx)) :
+                n==ret ? null : n.copyEmpty();
+        }
+        for( int i=0; i<len; i++ ) {
+            Node n = TINYBODY[i];
+            if( n instanceof StoreNode || n instanceof MemMergeNode ) {
+                for( Node in : n._inputs ) copy[i].addDef(mapped(in,copy));
+                CodeGen.CODE.add(copy[i]);
+            }
+        }
+        Node[] result = new Node[3];
+        for( int i=0; i<3; i++ ) result[i] = mapped(ret.in(i),copy).keep();
+        keep();
+        call.unlink_all();
+        CodeGen.CODE.add(fun);
+        CodeGen.CODE.addAll(fun._outputs);
+        // subsume kills each projection; retain CallEnd until all are replaced.
+        while( nOuts()>1 ) {
+            Node use = out(0)==null ? out(1) : out(0);
+            int idx = use instanceof ProjNode p ? p._idx : ((CProjNode)use)._idx;
+            CodeGen.CODE.addAll(use._outputs);
+            use.subsume(result[idx]);
+        }
+        unkill();
+        for( Node n : result ) n.unkill();
+        CodeGen.CODE.invalidateIDepthCaches();
+        return true;
+    }
+
+    private static Node mapped(Node n, Node[] copy) {
+        for( int i=0; i<copy.length; i++ )
+            if( TINYBODY[i]==n ) return copy[i];
+        return n;               // Constants outside the body are shared.
+    }
+
+    // Bounded recognition of initializer boilerplate. Walk uses from the entry
+    // and stop at Return, never following callers or constant inputs. This also
+    // avoids scanning sparse MemMerge input arrays while a large body shrinks.
+    // Watch this small prefix, including an unsupported node that may fold.
+    private static final Node[] TINYBODY = new Node[15]; // Tiny worklist
+    private int smallBody(FunNode fun) {
+        ReturnNode ret = fun.ret();
+        for( Node in : ret._inputs )
+            if( in!=null ) addDep(in);
+        if( ret.ctrl()!=fun ) return 0;
+        TINYBODY[0] = fun;
+        int len=1;
+        for( int i=0; i<len; i++ ) {
+            Node n = TINYBODY[i];
+            addDep(n);
+            if( n==ret ) continue;
+            if( n instanceof ParmNode parm && parm.region()!=fun ) return 0;
+            if( n!=fun && !(n instanceof ParmNode) &&
+                !(n instanceof StoreNode) && !(n instanceof MemMergeNode) )
+                return 0;
+            if( n.nOuts()>TINYBODY.length ) return 0;
+            for( Node use : n._outputs ) {
+                if( use==null ) continue;
+                int j=0;
+                while( j<len && TINYBODY[j]!=use ) j++;
+                if( j<len ) continue;
+                if( len==TINYBODY.length ) { addDep(use); return 0; }
+                TINYBODY[len++] = use;
+            }
+        }
+        return len;
+    }
+
     @Override public Node pcopy(int idx) {
         return _folding ? in(1).in(idx) : null;
     }
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index ec7b3cb3..0b4ad8ec 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -1,11 +1,13 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.codegen.CodeGen;
+import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
 public class Chapter12Test {
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen(
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
index 23d0ef37..6377bc14 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
@@ -2,6 +2,7 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.StopNode;
+import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
@@ -47,6 +48,7 @@ public class Chapter14FloatTest {
     }
 
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen(
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java
index 3a514763..f0fe7dcd 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java
@@ -2,12 +2,14 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.StopNode;
+import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
 public class Chapter14Test {
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen(
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java
index 94187d1c..cb92277f 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java
@@ -4,11 +4,13 @@ import com.seaofnodes.simple.codegen.CodeGen;
 import java.io.IOException;
 import java.nio.file.Files;
 import java.nio.file.Path;
+import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.*;
 
 public class Chapter15Test {
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen(
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java
index 884597cf..362388d6 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java
@@ -3,12 +3,14 @@ package com.seaofnodes.simple;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.evaluator.Evaluator;
 import com.seaofnodes.simple.node.StopNode;
+import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
 public class Chapter16Test {
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen(
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
index e7f5849d..e8f6e0bd 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
@@ -1,12 +1,14 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.codegen.CodeGen;
+import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
 public class Chapter17bTest {
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen(
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index 173fb653..7c0af028 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -115,6 +115,7 @@ public class Chapter18Test {
     }
 
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen(
@@ -453,7 +454,7 @@ if (i2i) return i2i(arg);
 return f2f(o)(1);
 """);
         code.driver(Phase.LocalSched);
-        assertEquals("Stop[ return Phi(Region,#2,#2); return Parm_i(o,int); ]", code._stop.toString());
+        assertEquals("Stop[ return Phi(Region,#2,1); return Parm_i(o,int); ]", code._stop.toString());
         assertEquals("1", Eval2.eval(code,  2));
     }
 
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java
index 0a92dc20..c53a8e11 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java
@@ -8,6 +8,7 @@ import com.seaofnodes.simple.codegen.CodeGen;
 import java.io.IOException;
 import java.nio.file.Files;
 import java.nio.file.Path;
+import org.junit.Ignore;
 import org.junit.Test;
 import static org.junit.Assert.*;
 
@@ -32,6 +33,7 @@ public class Chapter19Test {
     }
 
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen("""
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index be945a0b..e63fb32e 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -89,6 +89,7 @@ return f(s);
     }
 
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen("return 0;");