From 2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Wed, 7 Oct 2026 19:10:51 -0700
Subject: Towrds getting RA spill counts comparable

Ignore JIGs.  Get test suites more conical, so reg alloc spill counts are comparable
---
 chapter22/README.md                                | 77 +++++-------------
 .../main/java/com/seaofnodes/simple/IterPeeps.java | 19 ++++-
 .../com/seaofnodes/simple/node/CallEndNode.java    | 93 ++++++++++++++++++++++
 .../java/com/seaofnodes/simple/Chapter12Test.java  |  2 +
 .../com/seaofnodes/simple/Chapter14FloatTest.java  |  2 +
 .../java/com/seaofnodes/simple/Chapter14Test.java  |  2 +
 .../java/com/seaofnodes/simple/Chapter15Test.java  |  2 +
 .../java/com/seaofnodes/simple/Chapter16Test.java  |  2 +
 .../java/com/seaofnodes/simple/Chapter17bTest.java |  2 +
 .../java/com/seaofnodes/simple/Chapter18Test.java  |  3 +-
 .../java/com/seaofnodes/simple/Chapter19Test.java  |  2 +
 .../java/com/seaofnodes/simple/Chapter20Test.java  |  1 +
 .../test/java/com/seaofnodes/simple/progs/jig.smp  |  4 +-
 13 files changed, 151 insertions(+), 60 deletions(-)

(limited to 'chapter22')

diff --git a/chapter22/README.md b/chapter22/README.md
index 34fb4d20..1f839de5 100644
--- a/chapter22/README.md
+++ b/chapter22/README.md
@@ -190,64 +190,29 @@ returned values and memory as well as successful execution.
 
 ## RegAlloc improvements: better color bias
 
-Chapter 21 introduced conservative copy coalescing. Here we improve the register
-preferences used when related live ranges cannot coalesce. A copy chain can take
+Chapter 21 introduced conservative copy coalescing.  Here we improve the register
+preferences used when related live ranges cannot coalesce.  A copy chain can take
 an already assigned register even at its terminal definition; a loop Phi prefers
 its backedge's register, avoiding a move on each iteration when possible.
 
 When no live range is trivially colorable, cheap values make better spill
-candidates. We favor a cloneable definition with distant or multiple uses over
+candidates.  We favor a cloneable definition with distant or multiple uses over
 one already adjacent to its only use, then callee-save values whose long spans
-are cheap to split. Register order breaks ties between callee saves. These are
-small preferences, not a general cost model. Grouping popular values by register
-class is left for Chapter 23, cold loop splits for 24, and area/cost ranking for 25.
-
-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 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
-compiler**, default worklist seed 123, and the same source/target combinations
-as the earlier cohort. The Windows run combines x86 SystemV/Win64 and RISC-V/ARM
-SystemV. Diagnostic graphs and mask regressions do not contribute to the totals.
-
-| Program cohort | Compilations | Retained moves | Loop-weighted moves |
-|---|---:|---:|---:|
-| Chapter 20 | 39 | 324 | 443 |
-| Chapter 21 | 52 | 432 | 964 |
-| Chapter 22 | 26 | 67 | 67 |
-| **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
-memory traffic. The reporter also prints individual allocations and CPU/ABI sums.
-Chapter 21's original `int age` person example is preserved as `person21`; this
-chapter's `i32 age` version and revised infinite-loop example belong to cohort 22.
-
-Before adjacent-copy forwarding, a controlled comparison of the same compiler and correctness fixes with
-Chapter 21's color preferences and spill ordering produce 885 moves and 1,543
-weighted moves. This chapter saves **47 weighted moves (3.0%)**. RISC-V BrainFuck
-improves from 42 to 28 and ARM from 34 to 28 in each of its two cohorts. Some
-MergeSort cases and RISC-V Sieve each cost one more move. Summing the whole suite
-shows whether those local tradeoffs pay off.
-
-The original Chapter 22 snapshot, which mixed several later heuristics, produced
-854 moves and 1,736 weighted moves on these same 115 compilations. The corrected,
-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 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:
-shuffling optimizer worklists should normalize to essentially the same graph,
-so repeating allocation on those graphs adds little coverage. Use seed variation
-when investigating optimizer normalization or worklist-order failures.
-
-The [backport record](../docs/chapter-backports.md) documents the resolved
-String fall-through and returned-function retention/relocation failures,
-including their reproductions and validation history.
+are cheap to split.  Register order breaks ties between callee saves.  These
+are small preferences, not a general cost model.  Grouping popular values by
+register class is left for Chapter 23, cold loop splits for 24, and area/cost
+ranking for 25.
+
+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.
+
+<!-- spill-matrix:start -->
+| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 |
+|---|---:|---:|---:|---:|
+| Ch 20 | 39 | 360 | 576 | 430 |
+| Ch 21 | 52 |  | 1,072 | 960 |
+| Ch 22 | 26 |  |  | 63 |
+<!-- spill-matrix:end -->
diff --git a/chapter22/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter22/src/main/java/com/seaofnodes/simple/IterPeeps.java
index ded3da7e..7c2f1b0c 100644
--- a/chapter22/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter22/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/chapter22/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index 264a506e..94f5ee49 100644
--- a/chapter22/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -103,6 +103,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/chapter22/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index 9b41d77f..d8b072a2 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/chapter22/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/chapter22/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
index 23d0ef37..6377bc14 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java
+++ b/chapter22/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/chapter22/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter14Test.java
index da7e50bc..c342eeed 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter14Test.java
+++ b/chapter22/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/chapter22/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter15Test.java
index 0e928d5d..074cd8ba 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter15Test.java
+++ b/chapter22/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/chapter22/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter16Test.java
index 884597cf..362388d6 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter16Test.java
+++ b/chapter22/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/chapter22/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
index e7f5849d..e8f6e0bd 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
+++ b/chapter22/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/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index 9a7c53d3..6eb4d6f4 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -115,6 +115,7 @@ public class Chapter18Test {
     }
 
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen(
@@ -454,7 +455,7 @@ if (i2i) return i2i(arg);
 return f2f(o)(1);
 """);
         code.driver(Phase.LocalSched);
-        assertEquals("Stop[ return Parm_i(i2i.o,int); return Phi(Region,#2,#2); ]", code._stop.toString());
+        assertEquals("Stop[ return Parm_i(i2i.o,int); return Phi(Region,#2,1); ]", code._stop.toString());
         assertEquals("1", Eval2.eval(code,  2));
     }
 
diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java
index dee7d928..4564e513 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java
+++ b/chapter22/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/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index 2ec29f99..3575e461 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -92,6 +92,7 @@ return f(s);
     }
 
 
+    @Ignore
     @Test
     public void testJig() {
         CodeGen code = new CodeGen("return 0;");
diff --git a/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp b/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp
index f7a5d202..29987d8e 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp
+++ b/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp
@@ -1,5 +1,5 @@
 // -*- mode: java;  -*-
-val fib = {int n ->
+val _fib = {int n ->
     int temp=0;
     int f1=1;
     int f2=1;
@@ -13,4 +13,4 @@ val fib = {int n ->
     return f2;
 };
 
-fib(10);
+_fib(10);
-- 
cgit v1.2.3