Forward port mem changes to ch 19

8 files changed, 342 insertions, 12 deletions

diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index daeea36d..d0d33663 100644
--- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -1,6 +1,8 @@
 package com.seaofnodes.simple;
 
 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;
 
@@ -449,4 +451,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/chapter19/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
new file mode 100644
index 00000000..abf6c3cf
--- /dev/null
+++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
@@ -0,0 +1,59 @@
+package com.seaofnodes.simple;
+
+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/chapter19/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter14Test.java
index 17708c37..a3025001 100644
--- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter14Test.java
+++ b/chapter19/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/chapter19/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter16Test.java
index 83d34b2e..3dd37f33 100644
--- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter16Test.java
+++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter16Test.java
@@ -254,4 +254,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/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index a70ffd5f..81be3379 100644
--- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -445,4 +445,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/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java
index eef9f460..dc8fa309 100644
--- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java
+++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java
@@ -450,4 +450,71 @@ return sq(arg) + sq(3);
         code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched();
         assertEquals("Stop[ return (add,sq(),sq()); return (mul,Parm_x(sq,int,3,arg),x); ]", code.print());
     }
+
+    @Test public void testSelectedMemory() {
+        for( String cpu : new String[]{"x86_64_v2","riscv"} )
+            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.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.
+                        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().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/chapter19/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter19/src/test/java/com/seaofnodes/simple/Eval2.java
index 24761945..4837fcda 100644
--- a/chapter19/src/test/java/com/seaofnodes/simple/Eval2.java
+++ b/chapter19/src/test/java/com/seaofnodes/simple/Eval2.java
@@ -327,7 +327,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 )
@@ -440,9 +440,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/chapter19/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter19/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index a3b87e90..3f023bb2 100644
--- a/chapter19/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/chapter19/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) {