Forward port mem stuff to ch21

Also a minor reg-alloc improvement for BrainFuck, ported up to ch25

5 files changed, 56 insertions, 4 deletions

diff --git a/chapter25/README.md b/chapter25/README.md
index 6d1d5e99..4feef80f 100644
--- a/chapter25/README.md
+++ b/chapter25/README.md
@@ -163,6 +163,20 @@ first allocator. Shared legality fixes still start in the earliest affected
 chapter. The final audit corrected fixed-neighbor color bias in 20-25, narrow
 store masks in 20-21, and ARM register-bank/float-memory encoding in 21-25.
 
+Chapter 21's adjacent-copy forwarding carries forward here as well: a copy
+used only by the next instruction is removed when the operand accepts its
+source register and is not tied to the instruction's result.
+
+The table below is the **earlier audit**, before adjacent-copy forwarding.
+The current replay has ten String-constructor parse failures, also reproduced
+with the original allocator. On the identical 216 successful allocations,
+forwarding reduces 2,563 / 5,496 moves / weighted moves to 2,494 / 5,399.
+This is a partial comparison, not a replacement complete-suite total. The
+current cohort 25 has 14 allocations, including later C return ABI checks;
+the historical table has ten. Native cohort-25 checks and fresh system-library
+encoding pass in both runs. See the [backport record](../docs/chapter-backports.md)
+for the pending fixture failures.
+
 Run `make spill-stats`. Each row uses **Chapter 25's compiler**. The first five
 rows preserve the earlier 212 program/target entries, adapted to this chapter's
 syntax and library organization; the [fixture notes](src/test/java/com/seaofnodes/simple/spill/README.md)
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 196a1142..97bde2c9 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -694,8 +694,8 @@ public class RegAlloc {
                 if( defreg != usereg && splitBypass(bb,j,n,defreg) )
                     usereg = lrg(n.in(1))._reg;
 
-                // Split has same reg?  Useless!  Can remove it!
-                if( defreg == usereg ) {
+                // Same register, or the next instruction can use the source directly.
+                if( defreg == usereg || splitForward(bb,j,n,usereg) ) {
                     n.removeSplit();
                     j--;
                     continue;
@@ -708,6 +708,18 @@ public class RegAlloc {
         }
     }
 
+    // A sole, adjacent use can read the source register directly.  Nothing can
+    // clobber it in between; only the operand mask and two-address tie remain.
+    private boolean splitForward( CFGNode bb, int j, Node split, int reg ) {
+        if( split.nOuts()!=1 || j+1==bb.nOuts() ) return false;
+        Node use = split.out(0);
+        if( use!=bb.out(j+1) || use instanceof PhiNode || use instanceof CFGNode ||
+            !(use instanceof MachNode mach) ) return false;
+        int i = use._inputs.find(split);
+        RegMask mask = mach.regmap(i);
+        return mask!=null && mask.test(reg) && mach.twoAddress()!=i;
+    }
+
     private boolean splitBypass( CFGNode bb, int j, Node lo, int defreg ) {
         // Attempt to bypass split
         Node hi = lo.in(1);
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index 5ea198ef..ce604cf1 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -225,7 +225,7 @@ val _hashCodeString = { String self ->
 """;
         testCPU(src,"x86_64_v2", "SystemV",21,null);
         testCPU(src,"riscv"    , "SystemV",10,null);
-        testCPU(src,"arm"      , "SystemV",10,null);
+        testCPU(src,"arm"      , "SystemV",8,null);
     }
 
     @Test
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 88e963c0..b88e8af9 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -169,6 +169,7 @@ public class Chapter21Test {
 
 
     @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); }
+    @Test public void testCopyForward() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyForward(); }
 
     @Test public void testArmSubtractRegisters() {
         EvalArm64 cpu = new EvalArm64(new byte[16],16);
@@ -339,7 +340,7 @@ val _hashCodeString = { String self ->
 """;
         testCPU(src,"x86_64_v2", "SystemV",21,null);
         testCPU(src,"riscv"    , "SystemV",10,null);
-        testCPU(src,"arm"      , "SystemV",10,null);
+        testCPU(src,"arm"      , "SystemV",8,null);
     }
 
     @Test public void testStringExport() throws IOException {
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
index 6c6b9ad5..873578c2 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
@@ -251,6 +251,31 @@ public class RegAllocTestSupport {
         }
     }
 
+    public static void copyForward() throws Exception {
+        // Forwarding, fixed operand, two-address tie, intervening clobber,
+        // another user, and a scheduling-only edge.
+        for( int kind=0; kind<6; kind++ ) {
+            CodeGen code = graph();
+            RegAlloc alloc = new RegAlloc(code);
+            Op def = new Op(A,null,null,false,code._start);
+            alloc.newLRG(def,null)._reg=0;
+            SplitNode copy = code._mach.split(null,"test",(byte)0);
+            copy.setDef(0,code._start); copy.setDef(1,def);
+            alloc.newLRG(copy,null)._reg=1;
+            if( kind==3 ) new Op(null,null,A,false,code._start);
+            int twoAddress = kind==2 ? 1 : 0;
+            RegMask mask = kind==1 ? B : kind==5 ? null : new RegMask(3L);
+            Op use = new Op(null,mask,null,false,code._start,copy) {
+                @Override public int twoAddress() { return twoAddress; }
+            };
+            if( kind==4 ) new Op(null,B,null,false,code._start,copy);
+            var post = RegAlloc.class.getDeclaredMethod("postColor");
+            post.setAccessible(true); post.invoke(alloc);
+            assertSame("copy case "+kind,kind==0 ? def : copy,use.in(1));
+            assertEquals(kind==0 ? 0 : 1,alloc._spills);
+        }
+    }
+
     public static void coalescing() {
         // Merge, incompatible masks, interference, capacity, and adjacency remapping.
         for( int kind=0; kind<5; kind++ ) {