Forward port lazy mem eval to ch18

7 files changed, 283 insertions, 13 deletions

diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index daeea36d..d0d33663 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter18/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/chapter18/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
new file mode 100644
index 00000000..01bce801
--- /dev/null
+++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
@@ -0,0 +1,65 @@
+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() throws ReflectiveOperationException {
+        // 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).parse();
+            var field = IterPeeps.class.getDeclaredField("WORK");
+            field.setAccessible(true);
+            Object work = field.get(null);
+            field = work.getClass().getDeclaredField("_R");
+            field.setAccessible(true);
+            ((java.util.Random)field.get(work)).setSeed(seed);
+            code.opto();
+            assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4));
+        }
+    }
+}
diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java
index 86f5007d..1c6e5ae7 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java
+++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java
@@ -152,7 +152,7 @@ if( iss[arg] )
 return rez;
 """);
         try { code.parse().opto().typeCheck(); fail(); }
-        catch( Exception e ) { assertEquals("Might be null accessing 'y'",e.getMessage()); }
+        catch( Exception e ) { assertEquals("Might be null accessing '[]'",e.getMessage()); }
     }
 
     @Test
diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java
index 83d34b2e..3dd37f33 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java
+++ b/chapter18/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/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index 9582ecce..d13514b5 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -421,4 +421,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/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java
index 50207d8c..c517ce6e 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java
+++ b/chapter18/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 )
@@ -347,7 +347,7 @@ public abstract class Eval2 {
         int num = type._fields.length;
         Object[] ptr = new Object[num];
         for( int i=0; i<num; i++ )
-            ptr[i] = val(alloc.in(2+i+num));
+            ptr[i] = val(alloc.in(3+i));
         return ptr;
     }
 
@@ -438,9 +438,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/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 92b424df..1e2a08a7 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/chapter18/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,17 +199,14 @@ public class Evaluator {
                 assert elem instanceof TypeMemPtr;
             }
             // Length value
-            body[0] = vall(alloc.in(2+2));
+            body[0] = vall(alloc.in(3));
         } else {
             body = new Object[num = type._fields.length];
             for (int i=0; i<num; i++)
-                body[i] = val(alloc.in(2+i+num));
+                body[i] = val(alloc.in(3+i));
         }
-        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) {