Forward port mem stuff to ch21

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

15 files changed, 585 insertions, 29 deletions

diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index 14cf6e01..7da1354f 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.codegen.CodeGen;
 import org.junit.Test;
+import com.seaofnodes.simple.node.*;
+import java.util.BitSet;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
@@ -450,4 +452,121 @@ return 0;
         assertEquals("return 0;", code.print());
     }
 
+    @Test public void testReadBeforeStores() {
+        var code = new CodeGen("""
+            struct S { int x; int y; };
+            S !a = new S; S !b = new S;
+            a.x = 11; b.x = 22;
+            S !p = a; if (arg) p = b;
+            int before = p.x;
+            a.y = 55; b.y = 66;
+            a.x = 33; b.x = 44;
+            return before*100 + p.x;
+            """).parse().opto();
+        StopNode stop = code._stop;
+        assertEquals("1133",Eval2.eval(code,0));
+        assertEquals("2244",Eval2.eval(code,1));
+    }
+
+    static final String NESTED_MEMORY = """
+            struct S { int x; int y; int z; };
+            S !s = new S;
+            s.x = 5; s.y = 7; s.z = 11;
+            while (arg > 0) {
+                s.x = s.x + 1;
+                int j = 3;
+                while (j > 0) {
+                    j = j - 1;
+                    if (j == 1) continue;
+                    s.y = s.y + arg;
+                    if (arg == 2) break;
+                    s.z = s.z + 1;
+                }
+                arg = arg - 1;
+            }
+            return s;
+            """;
+
+    @Test public void testMemoryAcrossNestedLoops() {
+        var code = new CodeGen(NESTED_MEMORY).parse().opto();
+        StopNode stop = code._stop;
+        for (int arg=0; arg<7; arg++) {
+            assertEquals("S{x="+(5L+arg)+",y="+(7L+arg*(arg+1)-(arg>=2 ? 2 : 0))+
+                         ",z="+(11L+2*arg-(arg>=2 ? 2 : 0))+"}",Eval2.eval(code,arg));
+        }
+    }
+
+    @Test public void testMemoryAtEarlyReturns() {
+        var code = new CodeGen("""
+            struct S { int x; int y; int z; };
+            S !s = new S;
+            s.x = 3; s.y = 5; s.z = 7;
+            if (arg) { s.x = 11; s.z = 13; return s; }
+            s.y = 17;
+            return s;
+            """).parse().opto();
+        StopNode stop = code._stop;
+        for (int arg=0; arg<2; arg++) {
+            assertEquals(arg==0 ? "S{x=3,y=17,z=7}" : "S{x=11,y=5,z=13}",Eval2.eval(code,arg));
+        }
+    }
+
+    @Test public void testKeepLoadsAtMerge() {
+        var code = new CodeGen("""
+            struct S { int x; };
+            S !a = new S; S !b = new S;
+            a.x = arg; b.x = arg+1;
+            S !p = a; S !q = b;
+            if (arg<0) { p=b; q=a; }
+            int v;
+            if (arg>1) v=p.x; else v=q.x;
+            return v;
+            """).parse().opto();
+        StopNode stop = code._stop;
+        // The one-step safety check stops at the memory aggregate.
+        assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+        assertEquals("-1",Eval2.eval(code,-1));
+        assertEquals("1",Eval2.eval(code,0));
+        assertEquals("3",Eval2.eval(code,3));
+    }
+
+    @Test public void testDropStores() {
+        var code = new CodeGen("""
+            struct S { int x; };
+            S !s = new S;
+            if (arg) s.x=arg+1; else s.x=arg+2;
+            return s;
+            """).parse().opto();
+        StopNode stop = code._stop;
+        assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet()));
+        assertEquals("S{x=2}",Eval2.eval(code,0));
+        assertEquals("S{x=4}",Eval2.eval(code,3));
+    }
+
+    @Test public void testKeepReadsBeforeWrites() {
+        var code = new CodeGen("""
+            struct S { int x; int y; };
+            S !a = new S; S !b = new S;
+            a.x=arg; b.x=arg+1;
+            S !p=a; S !q=b;
+            if (arg<0) { p=b; q=a; }
+            int v;
+            if (arg>1) { v=p.x; p.x=41; p.y=5; }
+            else       { v=q.x; q.x=42; }
+            return v;
+            """).parse().opto();
+        StopNode stop = code._stop;
+        assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+        assertEquals("-1",Eval2.eval(code,-1));
+        assertEquals("1",Eval2.eval(code,0));
+        assertEquals("3",Eval2.eval(code,3));
+    }
+
+    private static int countMemoryNodes(Node n, Class<?> kind, BitSet seen) {
+        if (n==null || seen.get(n._nid)) return 0;
+        seen.set(n._nid);
+        int cnt=kind.isInstance(n) ? 1 : 0;
+        for (Node def : n._inputs) cnt+=countMemoryNodes(def,kind,seen);
+        return cnt;
+    }
 }
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
new file mode 100644
index 00000000..5d78ae06
--- /dev/null
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
@@ -0,0 +1,60 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.*;
+import com.seaofnodes.simple.node.*;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class Chapter10bTest {
+    @Test public void testIndependentField() {
+        var code = new CodeGen("""
+            struct S { int x; int y; };
+            S !s = new S;
+            s.x = 42;
+            while (arg > 0) { s.y = s.y + arg; arg = arg - 1; }
+            return s.x;
+            """).parse().opto();
+        var stop = code._stop;
+        assertEquals("return 42;",stop.toString());
+        assertEquals("42",Eval2.eval(code,5));
+        assertNull(stop.walk(n -> n instanceof LoadNode ? n : null));
+    }
+
+    @Test public void testParallelMemoryPhis() {
+        var code = new CodeGen("""
+            struct S { int x; int y; int z; };
+            S !a = new S; S !b = new S;
+            S !p = a; if (arg) p = b;
+            while (arg > 0) {
+                a.x = p.x + arg;
+                a.y = p.y + 2;
+                a.z = p.z + 3;
+                arg = arg - 1;
+            }
+            return a;
+            """).parse().opto();
+        var stop = code._stop;
+        int[] phis = {0};
+        stop.walk(n -> {
+            if (n instanceof MemPhiNode) phis[0]++;
+            if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b)
+                for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1))
+                    assertTrue(a<m.nIns() && m.in(a)!=null);
+            assertFalse(n instanceof PhiNode && n.isMem() &&
+                !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode) && !(n instanceof ParmNode));
+            return null;
+        });
+        assertTrue(phis[0]>=3);
+        assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4));
+    }
+
+    @Test public void testLateSliceWorklist() {
+        // Seed 97 exposed a store selecting a bulk predecessor without queuing
+        // it. Keep both the worklist assertion and the final heap check.
+        for (int seed : new int[]{0,97,123,456}) {
+            var code = new CodeGen(Chapter10Test.NESTED_MEMORY,com.seaofnodes.simple.type.TypeInteger.BOT,seed).parse();
+            code.opto();
+            assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4));
+        }
+    }
+}
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java
index 7af35b56..b83516e3 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java
@@ -174,7 +174,7 @@ while(v1) break;
 return v1;
 """);
         code.parse().opto();
-        assertEquals("return Phi(Loop,(((1<<arg)&1)&Shl),0);", code.print());
+        assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", code.print());
         assertEquals("1", Eval2.eval(code,  0));
     }
 
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java
index 5899763f..571a0d54 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java
@@ -255,4 +255,27 @@ return new Square;
         assertEquals("Square{side=3.0,diag=1.7320508075688772}", Eval2.eval(code,  3));
         assertEquals("Square{side=4.0,diag=2.0}", Eval2.eval(code, 4));
     }
+    static final String CONSTRUCTOR_MEMORY = """
+        struct S { int x; int y; };
+        struct T { int z=arg+40; };
+        T !t = new T;
+        S !a = new S { x=11; y=7; };
+        S !b = new S { x=22; y=9; };
+        S !p=a;
+        if (arg) p=b;
+        int before=p.x;
+        S !c = new S {
+            x=p.x+1;
+            { int i=0; while (i<2) { p.y=p.y+1; i=i+1; } }
+            y=p.y;
+        };
+        p.x=33;
+        return before*10000+c.x*100+c.y+t.z;
+        """;
+
+    @Test public void testConstructorMemory() {
+        var code = new CodeGen(CONSTRUCTOR_MEMORY).parse().opto();
+        assertEquals("111249",Eval2.eval(code,0));
+        assertEquals("222352",Eval2.eval(code,1));
+    }
 }
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java
index 78515083..5de4ec3c 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java
@@ -368,7 +368,7 @@ var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; };
 return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0"
 """);
         code.parse().opto();
-        assertEquals("return Phi(Region,.x,0);", code.print());
+        assertEquals("return Phi(Region,.x,0,.x);", code.print());
         assertEquals("0", Eval2.eval(code, 0));
         assertEquals("1", Eval2.eval(code, 1));
         assertEquals("2", Eval2.eval(code, 2));
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index 5743546e..e1e254fe 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -438,4 +438,70 @@ return p.coffee_count;
         assertEquals("1", Eval2.eval(code,  2));
     }
 
+    static final String CALL_MEMORY = """
+        struct S { int x; int y; };
+        val bump = { S s, int d -> int old=s.x; s.x=old+d; return old; };
+        S !a = new S { x=10; y=7; };
+        S !b = new S { x=20; y=9; };
+        S !p=a; if (arg) p=b;
+        int before=p.x;
+        int old=bump(p,3);
+        int after=p.x;
+        bump(a,5);
+        return before*1000000+old*10000+after*100+a.x+a.y;
+        """;
+
+    @Test public void testCallMemory() {
+        var code = new CodeGen(CALL_MEMORY).parse().opto();
+        int[] calls={0};
+        code._stop.walk(n -> { if(n instanceof CallNode) calls[0]++; return null; });
+        assertEquals(2,calls[0]); // Keep real calls so this checks scheduling across them.
+        assertEquals("10101325",Eval2.eval(code,0));
+        assertEquals("20202322",Eval2.eval(code,1));
+        code._stop.walk(n -> {
+            if(n instanceof CallNode call) {
+                assertEquals(5,call.nIns()); // No scheduling edges may become extra arguments.
+                assertTrue(call.fptr()._type instanceof TypeFunPtr);
+            }
+            return null;
+        });
+    }
+
+    static final String RECURSIVE_MEMORY = """
+        struct S { int x; };
+        val rec = { S s, int n ->
+            if (n==0) return s.x;
+            int before=s.x;
+            s.x=before+1;
+            return before+rec(s,n-1);
+        };
+        S !s=new S { x=10; };
+        int value=rec(s,arg);
+        return value*100+s.x;
+        """;
+
+    @Test public void testRecursiveMemory() {
+        var code = new CodeGen(RECURSIVE_MEMORY).parse().opto();
+        for(int n=0; n<7; n++)
+            assertEquals(Long.toString((10L*(n+1)+n*(n+1)/2)*100+10+n),Eval2.eval(code,n));
+    }
+
+    static final String INLINE_MEMORY = """
+        struct S { int x; int y; };
+        val make = { S s ->
+            S t = new S { x=s.x+1; y=3; };
+            s.y=9;
+            return t;
+        };
+        S !a = new S { x=arg+40; y=7; };
+        S t=make(a);
+        return a.x*10000+a.y*100+t.x+t.y;
+        """;
+
+    @Test public void testInlineAllocationMemory() {
+        var code = new CodeGen(INLINE_MEMORY).parse().opto();
+        assertNull(code._stop.walk(n -> n instanceof CallNode ? n : null));
+        assertEquals("400944",Eval2.eval(code,0));
+        assertEquals("420946",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 1c427d4f..1149c518 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java
@@ -350,4 +350,72 @@ return sq(arg) + sq(3);
         code.driver(Phase.LocalSched,"x86_64_v2", "SystemV");
         assertEquals("Stop[ return (add,#2,#2); return (mul,Parm_x(sq,int),x); ]", code.print());
     }
+
+    @Test public void testSelectedMemory() {
+        for( String cpu : new String[]{"x86_64_v2","riscv","arm"} )
+            for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY,
+                                          Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY} ) {
+                var code = new CodeGen(src).parse().opto().typeCheck();
+                var aliases = memoryPhis(code._stop);
+                code.loopTree().instSelect(cpu,"SystemV");
+                assertEquals(aliases,memoryPhis(code._stop));
+                code.GCM().localSched();
+                code._stop.walk(n -> {
+                    if( !(n instanceof CFGNode) && !(n instanceof ProjNode) )
+                        assertTrue(n.in(0) instanceof CFGNode);
+                    if( n instanceof NewNode nn ) {
+                        assertEquals(2,((TypeTuple)nn._type)._types.length);
+                        assertTrue(nn.mem() instanceof MemMergeNode);
+                        assertNull(nn.mem().in(1)); // Partial allocation input.
+                        nn.cacheRegs(code);
+                        MachNode mach = (MachNode)nn;
+                        assertNull(mach.regmap(1));
+                        assertNotNull(mach.regmap(2));
+                        assertNotNull(mach.outregmap(0));
+                        assertNull(mach.outregmap(1));
+                    }
+                    if( n instanceof CallNode call ) {
+                        assertEquals(4,call.nIns()); // ctrl, memory, two args; direct target is embedded.
+                    }
+                    return null;
+                });
+            }
+    }
+
+    private static java.util.ArrayList<String> memoryPhis(Node stop) {
+        var phis = new java.util.ArrayList<String>();
+        stop.walk(n -> {
+            if( n instanceof MemPhiNode phi ) phis.add("alias:"+phi._alias);
+            if( n instanceof BulkMemPhiNode phi ) phis.add("bulk:"+phi._aliases);
+            assertFalse(n instanceof PhiNode && n.isMem() &&
+                !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode) && !(n instanceof ParmNode));
+            return null;
+        });
+        java.util.Collections.sort(phis);
+        return phis;
+    }
+
+    @Test public void testFoldedReadBeforeWrites() {
+        var code = new CodeGen("""
+            struct S { int x; };
+            S !a = new S { x=11; }; S !b = new S { x=22; };
+            S !p = a; if( arg ) p = b;
+            int before = p.x + arg;
+            a.x=33; b.x=44;
+            return before;
+            """).parse().opto().typeCheck().loopTree().instSelect("x86_64_v2","SystemV").GCM().localSched();
+        var read = (MemOpNode)code._stop.walk(n ->
+            n instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.AddMemX86 ? n : null);
+        assertNotNull(read);
+        int writes = 0;
+        for( Node use : read.antiDeps() )
+            if( use instanceof MemOpNode st && st.isMem() ) {
+                assertSame(read.cfg0(),st.cfg0());
+                assertTrue(st._inputs.find(read)>=0);
+                assertTrue(read.cfg0()._outputs.find(read)<st.cfg0()._outputs.find(st));
+                assertNull(((MachNode)st).regmap(st._inputs.find(read)));
+                writes++;
+            }
+        assertEquals(1,writes); // The next Store follows this first clobber through memory.
+    }
 }
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index 0691d4a2..250acaa2 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -142,9 +142,9 @@ return sqrt(farg) + sqrt(farg+2.0);
     @Test
     public void testAlloc2() {
         String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];";
-        testTarget(src,"x86_64_v2","SystemV",3,"return .[];");
+        testTarget(src,"x86_64_v2","SystemV",4,"return .[];");
         testTarget(src,"riscv","SystemV",8,"return .[];");
-        testTarget(src,"arm","SystemV",10,"return .[];");
+        testTarget(src,"arm","SystemV",9,"return .[];");
     }
 
     @Test
@@ -160,7 +160,7 @@ for( int i=0; i<ary#-1; i++ )
     ary[i+1] += ary[i];
 return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6
 """;
-        testTarget(src,"x86_64_v2", "SystemV",9,"return .[];");
+        testTarget(src,"x86_64_v2", "SystemV",7,"return .[];");
         testTarget(src,"riscv"    , "SystemV",7,"return (add,.[],(mul,.[],1000));");
         testTarget(src,"arm"      , "SystemV",5,"return (add,.[],(mul,.[],1000));");
     }
@@ -203,9 +203,9 @@ s.cs[0] =  67; // C
 s.cs[1] = 108; // l
 hashCode(s);
 """;
-        testTarget(src,"x86_64_v2", "SystemV",14,null);
-        testTarget(src,"riscv"    , "SystemV", 14,null);
-        testTarget(src,"arm"      , "SystemV", 13,null);
+        testTarget(src,"x86_64_v2", "SystemV",15,null);
+        testTarget(src,"riscv"    , "SystemV", 10,null);
+        testTarget(src,"arm"      , "SystemV", 10,null);
     }
 
     @Test
@@ -364,8 +364,29 @@ return a;
 """;
         testTarget(src,"x86_64_v2", "SystemV",52,null);
         testTarget(src,"riscv"    , "SystemV",44,null);
-        testTarget(src,"arm"      , "SystemV",44,null);
+        testTarget(src,"arm"      , "SystemV",41,null);
 //assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11));
     }
 
+
+    @Test public void testMemoryAllocation() {
+        for( String cpu : new String[]{"x86_64_v2","riscv","arm"} )
+            for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY,
+                                          Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY,
+                                          "int[] !a = new int[3]; a[arg]=arg; return a[0]+1;"} ) {
+                var code = new CodeGen(src).parse().opto().typeCheck().loopTree()
+                    .instSelect(cpu,"SystemV").GCM().localSched().regAlloc();
+                com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code);
+                code._stop.walk(n -> {
+                    // Whole memory, precise Phis, and memory projections need no register.
+                    if( n._type instanceof com.seaofnodes.simple.type.TypeMem )
+                        assertEquals(-1,code._regAlloc.regnum(n));
+                    if( n instanceof com.seaofnodes.simple.node.NewNode nn ) {
+                        assertTrue(code._regAlloc.regnum(nn.proj(0))>=0);
+                        assertEquals(-1,code._regAlloc.regnum(nn.proj(1)));
+                    }
+                    return null;
+                });
+            }
+    }
 }
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java
index 39b410d5..bc300217 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java
@@ -49,7 +49,7 @@ return sqrt(arg) + sqrt(arg+2);
         String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp"));
         Chapter21Test.testCPU(src,"x86_64_v2", "SystemV", 9,null);
         Chapter21Test.testCPU(src,"riscv"    , "SystemV", 3,null);
-        Chapter21Test.testCPU(src,"arm"      , "SystemV", 3,null);
+        Chapter21Test.testCPU(src,"arm"      , "SystemV", 1,null);
     }
 
 }
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 6c943904..a8712a2e 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -217,6 +217,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 testRisc64BitStore() {
         byte[] mem = new byte[24];
         EvalRisc5 cpu = new EvalRisc5(mem,mem.length);
@@ -299,7 +300,7 @@ public class Chapter21Test {
         String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp"));
         testCPU(src,"x86_64_v2", "SystemV", 9,null);
         testCPU(src,"riscv"    , "SystemV", 3,null);
-        testCPU(src,"arm"      , "SystemV", 3,null);
+        testCPU(src,"arm"      , "SystemV", 1,null);
     }
 
     @Test public void testStringExport() throws IOException {
@@ -353,11 +354,11 @@ public class Chapter21Test {
         String sprimes = sb.p("]").toString();
 
         // Compile, link against native C; expect the above string of primes to be printed out by C
-        TestC.run("sieve",sprimes, 178);
+        TestC.run("sieve",sprimes, 185);
 
         // Evaluate on RISC5 emulator; expect return of an array of primes in
         // the simulated heap.
-        EvalRisc5 R5 = TestRisc5.build("sieve", 100, 89, false);
+        EvalRisc5 R5 = TestRisc5.build("sieve", 100, 92, false);
         int trap = R5.step(10000);
         assertEquals(0,trap);
         // Return register A0 holds sieve(100)
@@ -369,7 +370,7 @@ public class Chapter21Test {
 
         // Evaluate on ARM5 emulator; expect return of an array of primes in
         // the simulated heap.
-        EvalArm64 A5 = TestArm64.build("sieve", 100, 93, false);
+        EvalArm64 A5 = TestArm64.build("sieve", 100, 91, false);
         int trap_arm = A5.step(10000);
         assertEquals(0, trap_arm);
         int ary_arm = (int)A5.regs[arm.X0];
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java
index 82839399..dabd63cc 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java
@@ -331,7 +331,7 @@ public abstract class Eval2 {
     private static Object alloc(NewNode alloc) {
         TypeStruct type = alloc._ptr._obj;
         if( type.isAry() ) {
-            long sz = (Long)val(alloc.in(1));
+            long sz = (Long)val(alloc.size());
             long x = offToIdx(sz, type);
             int n = (int)x;
             if( n!=x || n<0 )
@@ -444,9 +444,9 @@ public abstract class Eval2 {
         case TypeRPC rpc -> sb.p(x.toString());
         case TypeMem mem -> sb.p("$mem");
         case TypeTuple tt -> {
-            if( tt._types.length>1 && tt._types[1] instanceof TypeMemPtr )
+            if( tt._types.length>1 && tt._types[0] instanceof TypeMemPtr )
                 // Assume a NewNode
-                yield _print( tt._types[1], x, sb, visit );
+                yield _print( tt._types[0], x, sb, visit );
             throw Utils.TODO();
         }
         case Type tt -> {
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java
index e5aa729b..f8996b00 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java
@@ -116,10 +116,11 @@ public class EvalArm64 {
             }
             // for the opcode we just match for bits[31:24];
             switch(opcode1) {
-                case 0xD2: {
-                    // movz
-                    // get immediate
-                    rval = (ir >> 5) & 0x7FFF;
+                case 0xD2: // MOVZ
+                case 0xF2: { // MOVK preserves the other halfwords
+                    int shift = ((ir >> 21) & 3)*16;
+                    rval = ((ir >> 5) & 0xFFFFL) << shift;
+                    if( opcode1==0xF2 ) rval |= regs[rdid] & ~(0xFFFFL << shift);
                     break;
                 }
                 case 0x38: {
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java
new file mode 100644
index 00000000..0de4e960
--- /dev/null
+++ b/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java
@@ -0,0 +1,176 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.codegen.RegAllocTestSupport;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.node.cpus.arm.arm;
+import com.seaofnodes.simple.node.cpus.riscv.riscv;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+// Execution regressions are separate from the fixed spill-measurement cohorts.
+public class MemoryEncodingTest {
+    @Test public void testLoopLoadSearch() {
+        String[] sources = {
+            """
+            u8[] !program=new u8[106]; u8[] !out=new u8[0];
+            int sum=0;
+            for(int i=0; i<arg; i++) {
+                sum+=program#;
+                if(i==1) out=new u8[i+1];
+                else if(i==3) out=new u8[2];
+            }
+            return sum+out#;
+            """,
+            // One possibly aliasing arm must reject the unchanged-memory proof.
+            """
+            struct S { int x; }; S !a=new S; S !b=new S;
+            a.x=10; b.x=20; S !p=a; if(arg&1) p=b;
+            int sum=0;
+            for(int i=0; i<6; i++) {
+                if(i==2) p.x=30;
+                else if(i==4) b.x=40;
+                sum+=a.x;
+            }
+            return sum;
+            """,
+            // Unchanged memory does not imply an unchanged loop-carried pointer.
+            """
+            struct S { int x; }; S !a=new S; S !b=new S;
+            a.x=10; b.x=20; S !p=a; int sum=0;
+            for(int i=0; i<6; i++) {
+                if(i==2) a.x=30;
+                sum+=p.x;
+                p=b; if(i&1) p=a;
+            }
+            return sum;
+            """,
+            // All arms fold, but their values differ: build a value Phi.
+            """
+            struct S { int x; }; S !a=new S; a.x=1; int sum=0;
+            for(int i=0; i<6; i++) {
+                sum+=a.x;
+                if(i&1) a.x=2;
+                else if(i==2) a.x=3;
+                else a.x=4;
+            }
+            return sum;
+            """
+        };
+        for( int p=0; p<sources.length; p++ ) {
+            CodeGen code=new CodeGen(sources[p]).parse().opto();
+            if( p==0 ) assertNull(code._stop.walk(n ->
+                n instanceof LoadNode ld && ld.ptr() instanceof ProjNode ptr &&
+                ptr.in(0) instanceof NewNode nn &&
+                nn.size()._type==com.seaofnodes.simple.type.TypeInteger.constant(110) ? ld : null));
+            for( int arg=0; arg<7; arg++ ) {
+                long expected=switch(p) {
+                case 0 -> 106*arg+(arg>=2 ? 2 : 0);
+                case 1 -> (arg&1)==0 ? 140 : 60;
+                case 2 -> 130;
+                default -> 16;
+                };
+                assertEquals(Long.toString(expected),Eval2.eval(code,arg));
+            }
+        }
+    }
+
+    private static final String[] SOURCES = {
+        Chapter16Test.CONSTRUCTOR_MEMORY,
+        Chapter18Test.CALL_MEMORY,
+        Chapter18Test.RECURSIVE_MEMORY,
+        Chapter18Test.INLINE_MEMORY,
+        "int[] !a = new int[7]; a[arg]=arg+3; return a[0]+1;",
+        """
+        int[] !a = new int[7];
+        for( int i=0; i<7; i++ ) a[i]=i+arg;
+        for( int i=0; i<6; i++ ) a[i+1]+=a[i];
+        return a[6];
+        """
+    };
+
+    private static long expected(int program, long arg) {
+        return switch(program) {
+        case 0 -> arg==0 ? 111249 : 222351+arg;
+        case 1 -> arg==0 ? 10101325 : 20202322;
+        case 2 -> (10*(arg+1)+arg*(arg+1)/2)*100+10+arg;
+        case 3 -> 400944+arg*10001;
+        case 4 -> arg==0 ? 4 : 1;
+        case 5 -> 21+7*arg;
+        default -> throw new AssertionError();
+        };
+    }
+
+    @Test public void testEmulatedMemory() throws IOException {
+        for( String target : new String[]{"riscv","arm"} )
+            for( int p=0; p<SOURCES.length; p++ ) {
+                CodeGen code = new CodeGen(SOURCES[p]).driver(target,"SystemV",null);
+                RegAllocTestSupport.checkRegisters(code);
+                int entry=0;
+                for( var n : code._start._outputs )
+                    if( n instanceof FunNode fun && "main".equals(fun._name) )
+                        entry=code._encoding._opStart[fun._nid];
+                for( int arg=0; arg<7; arg++ ) {
+                    byte[] image = new byte[1<<20];
+                    byte[] bits = code._encoding.bits();
+                    System.arraycopy(bits,0,image,0,bits.length);
+                    long result;
+                    if( target.equals("riscv") ) {
+                        EvalRisc5 cpu = new EvalRisc5(image,1<<16);
+                        cpu._pc=entry;
+                        cpu.regs[riscv.A0]=arg;
+                        assertEquals(target+" program "+p+" arg "+arg,0,cpu.step(100000));
+                        result=cpu.regs[riscv.A0];
+                    } else {
+                        EvalArm64 cpu = new EvalArm64(image,1<<16);
+                        cpu._pc=entry;
+                        cpu.regs[arm.X0]=arg;
+                        assertEquals(target+" program "+p+" arg "+arg,0,cpu.step(100000));
+                        result=cpu.regs[arm.X0];
+                    }
+                    assertEquals(target+" program "+p+" arg "+arg,expected(p,arg),result);
+                }
+            }
+    }
+
+    @Test public void testNeverMemory() {
+        // A synthetic exit must retain both precise slices of a no-exit loop.
+        // Stop at scheduling: the existing allocator cannot coalesce TOP on
+        // the synthetic scalar return arm.
+        for( String target : new String[]{"x86_64_v2","riscv","arm"} ) {
+            CodeGen code = new CodeGen("""
+                struct S { int x; int y; };
+                S !a=new S;
+                if( arg ) while( 1 ) { a.x+=arg; a.y+=a.x; }
+                return a.x+a.y;
+                """).driver(CodeGen.Phase.LoopTree);
+            assertNotNull(code._stop.walk(n -> {
+                if( n instanceof MemMergeNode mem &&
+                    mem.in(0) instanceof CProjNode exit && exit.in(0) instanceof NeverNode ) {
+                    assertTrue(mem.alias(2) instanceof MemPhiNode);
+                    assertTrue(mem.alias(3) instanceof MemPhiNode);
+                    return mem;
+                }
+                return null;
+            }));
+            code.instSelect(target,"SystemV").GCM().localSched();
+        }
+    }
+
+    @Test public void testNativeMemory() throws IOException {
+        Files.createDirectories(Path.of("build/objs"));
+        for( int p=0; p<SOURCES.length; p++ ) {
+            String file="build/objs/memory"+p;
+            StringBuilder c = new StringBuilder("extern long long memory(long long);\nint main() {\n");
+            for( int arg=0; arg<7; arg++ )
+                c.append("if(memory(").append(arg).append(")!=").append(expected(p,arg)).append("LL) return ").append(arg+1).append(";\n");
+            c.append("return 0;\n}\n");
+            Files.writeString(Path.of(file+".c"),c);
+            TestC._run("val memory = { int arg -> "+SOURCES[p]+" };",
+                TestC.CALL_CONVENTION,"",file+".c",file,"S","",-1);
+        }
+    }
+}
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
index abc2ae82..3f624fcd 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
@@ -166,6 +166,31 @@ public class RegAllocTestSupport {
         assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy));
     }
 
+    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)._reg=0;
+            SplitNode copy = code._mach.split("test",(byte)0,null);
+            copy.setDef(0,code._start); copy.setDef(1,def);
+            alloc.newLRG(copy)._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++ ) {
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index a3b87e90..3f023bb2 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -185,7 +185,7 @@ public class Evaluator {
         Object[] body=null;
         int num;
         if( type.isAry() ) {
-            long sz = (Long)val(alloc.in(1));
+            long sz = (Long)val(alloc.size());
             long n = offToIdx(sz, type);
             if( n < 0 )
                 throw new NegativeArraySizeException(""+n);
@@ -199,21 +199,17 @@ public class Evaluator {
                 assert elem instanceof TypeMemPtr;
             }
             // Length value
-            body[0] = vall(alloc.in(2+2));
+            body[0] = n;
         } else {
             body = new Object[num = type._fields.length];
             for( int i=0; i<num; i++ )
                 body[i] = switch( alloc._ptr._obj._fields[i]._type ) {
                 case TypeInteger ti -> 0L;
-                case TypeFloat tf -> 0;
+                case TypeFloat tf -> 0D;
                 default -> null;
                 };
         }
-        Object[] mems = new Object[type._fields.length+2];
-        // mems[0] is control
-        mems[1] = new Obj(type,body); // the ref
-        // mems[2+...] are memory aliases
-        return mems;
+        return new Object[]{new Obj(type,body),null};
     }
 
     private Object load(LoadNode load) {