Forward port lazy mem eval to ch18

9 files changed, 234 insertions, 34 deletions

diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java
index dfd3569f..36727a8f 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -84,7 +84,10 @@ public class Chapter04Test {
         StopNode stop = parser.parse();
         ReturnNode ret = stop.ret();
         assertTrue(ret.in(0) instanceof CProjNode);
-        assertTrue(ret.in(1) instanceof  ProjNode);
+        assertTrue(ret.in(1) instanceof ProjNode);
+        assertEquals(1, ((ProjNode)ret.in(1))._idx);
+        assertTrue(ret.in(2) instanceof ProjNode);
+        assertEquals(2, ((ProjNode)ret.in(2))._idx);
     }
 
     @Test
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index e3d8b177..86a9937f 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -1,7 +1,8 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.evaluator.Evaluator;
-import com.seaofnodes.simple.node.StopNode;
+import com.seaofnodes.simple.node.*;
+import java.util.BitSet;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
@@ -452,4 +453,120 @@ return 0;
         assertEquals("return 0;", stop.toString());
     }
 
+    @Test public void testReadBeforeStores() {
+        var stop = new Parser("""
+            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().iterate();
+        assertEquals(1133L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0));
+        assertEquals(2244L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,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 stop = new Parser(NESTED_MEMORY).parse().iterate();
+        for (int arg=0; arg<7; arg++) {
+            var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj)
+                com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg);
+            org.junit.Assert.assertArrayEquals(new Object[] {
+                5L+arg, 7L+arg*(arg+1)-(arg>=2 ? 2 : 0), 11L+2*arg-(arg>=2 ? 2 : 0)
+            }, obj.fields());
+        }
+    }
+
+    @Test public void testMemoryAtEarlyReturns() {
+        var stop = new Parser("""
+            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().iterate();
+        for (int arg=0; arg<2; arg++) {
+            var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj)
+                com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg);
+            org.junit.Assert.assertArrayEquals(arg==0 ? new Object[]{3L,17L,7L} : new Object[]{11L,5L,13L}, obj.fields());
+        }
+    }
+
+    @Test public void testKeepLoadsAtMerge() {
+        StopNode stop = new Parser("""
+            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().iterate();
+        // The one-step safety check stops at the memory aggregate.
+        assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+        assertEquals(-1L,Evaluator.evaluate(stop,-1));
+        assertEquals(1L,Evaluator.evaluate(stop,0));
+        assertEquals(3L,Evaluator.evaluate(stop,3));
+    }
+
+    @Test public void testDropStores() {
+        StopNode stop = new Parser("""
+            struct S { int x; };
+            S !s = new S;
+            if (arg) s.x=arg+1; else s.x=arg+2;
+            return s;
+            """).parse().iterate();
+        assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet()));
+        assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]);
+        assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]);
+    }
+
+    @Test public void testKeepReadsBeforeWrites() {
+        StopNode stop = new Parser("""
+            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().iterate();
+        assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+        assertEquals(-1L,Evaluator.evaluate(stop,-1));
+        assertEquals(1L,Evaluator.evaluate(stop,0));
+        assertEquals(3L,Evaluator.evaluate(stop,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/chapter17/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
new file mode 100644
index 00000000..fd6fdf36
--- /dev/null
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10bTest.java
@@ -0,0 +1,64 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.evaluator.Evaluator;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class Chapter10bTest {
+    @Test public void testIndependentField() {
+        var stop = new Parser("""
+            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().iterate();
+        assertEquals("return 42;",stop.toString());
+        assertEquals(42L,Evaluator.evaluate(stop,5));
+        assertNull(stop.walk(n -> n instanceof LoadNode ? n : null));
+    }
+
+    @Test public void testParallelMemoryPhis() {
+        var stop = new Parser("""
+            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().iterate();
+        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));
+            return null;
+        });
+        assertTrue(phis[0]>=3);
+        assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
+    }
+
+    @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 parser = new Parser(Chapter10Test.NESTED_MEMORY);
+            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);
+            var stop = parser.parse().iterate();
+            assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields());
+        }
+    }
+}
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java
index 862b75e3..a1fdeb3a 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java
@@ -183,7 +183,7 @@ return new S1.s=new S2;
 struct I {int i;};
 struct P { I? pi; };
 P !p1 = new P;
-P p2 = new P;
+P !p2 = new P;
 p2.pi = new I;
 p2.pi.i = 2;
 if (arg) p1 = new P;
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java
index 23c82358..6846e7af 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java
@@ -175,7 +175,7 @@ while(v1) break;
 return v1;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", stop.toString());
+        assertEquals("return Phi(Loop,(((1<<arg)&1)&Shl),0);", stop.toString());
         assertEquals(1L, Evaluator.evaluate(stop,  0));
     }
 
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java
index 4e2682dc..e66a009b 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java
@@ -130,7 +130,7 @@ else {
 return rez;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region,1.2,Phi(Region,2.3,3.14));", stop.toString());
+        assertEquals("return Phi(Region,1.2,Phi(Region,2.3,.y));", stop.toString());
         assertEquals(3.14, Evaluator.evaluate(stop, 0));
         assertEquals(1.2 , Evaluator.evaluate(stop, 1));
     }
@@ -156,7 +156,7 @@ if( iss[arg] )
 return rez;
 """);
         try { parser.parse().iterate(); 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/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java
index 36510737..d9edf0e6 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java
@@ -254,4 +254,27 @@ return new Square;
         assertEquals("Obj<Square>{side=3.0,diag=1.7320508075688772}", Evaluator.evaluate(stop,  3).toString());
         assertEquals("Obj<Square>{side=4.0,diag=2.0}", Evaluator.evaluate(stop, 4).toString());
     }
+    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() {
+        StopNode stop = new Parser(CONSTRUCTOR_MEMORY).parse().iterate();
+        assertEquals(111249L,Evaluator.evaluate(stop,0));
+        assertEquals(222352L,Evaluator.evaluate(stop,1));
+    }
 }
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 72f84fa2..30af9895 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -187,7 +187,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);
@@ -201,17 +201,13 @@ 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),MEMORY};
     }
 
     private Object load(LoadNode load) {
@@ -304,10 +300,10 @@ public class Evaluator {
             case ToFloatNode  cast  -> (double)vall(cast.in(1));
             case LoadNode     load  -> load(load);
             case StoreNode    store -> store(store);
+            case MemMergeNode merge -> MEMORY;
             case NewNode      alloc -> alloc(alloc);
             case CProjNode    cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx];
             case ProjNode     proj  -> ((Object[])val( proj.in(0) ))[ proj._idx];
-            case ScopeMinNode mem   -> null;
             case ReadOnlyNode ro    -> val(ro.in(1));
             default                 -> throw new AssertionError("Unexpected node " + node);
         };
@@ -331,7 +327,7 @@ public class Evaluator {
                 case null:
                     return Status.FALLTHROUGH;
                 case ReturnNode ret:
-                    return val(ret.in(1));
+                    return val(ret.expr());
                 case IfNode ifn:
                     block = block.next()[isTrue(val(ifn.in(1))) ? 0 : 1];
                     if (block == null) return Status.FALLTHROUGH;
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
index 06169e2c..afcc700f 100644
--- a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
+++ b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
@@ -31,6 +31,8 @@ import java.util.*;
  */
 public class Scheduler {
 
+    private final HashMap<Node,ArrayList<NodeData>> readers = new HashMap<>();
+
     /**
      * A basic block with a schedule of the containing nodes.
      *
@@ -252,7 +254,7 @@ public class Scheduler {
                 // but they did not refine the placement
                 // so do that now.
                 var mem = l.in(1);
-                for(var out : mem._outputs) {
+                for(var out : l.antiDeps()) {
                     if (out instanceof PhiNode p) {
                         var r = p.in(0);
                         for (int i = 1; i < p.nIns(); i++) {
@@ -270,13 +272,9 @@ public class Scheduler {
             for(var in:data.node._inputs) {
                 if (in!=null) update(d(in), data.block);
             }
-            if (data.node instanceof StoreNode s) {
-                // Store nodes have anti-deps to load nodes.
-                // So decrease the uses of these loads when the store is placed.
-                for (var out: s.in(1)._outputs) {
-                    if (out instanceof LoadNode) od(out).ifPresent(this::decUsers);
-                }
-            }
+            var loads = readers.get(data.node);
+            if (loads != null)
+                for (var load : loads) decUsers(load);
         }
 
         // Now all nodes should be placed and have a block assigned
@@ -442,7 +440,6 @@ public class Scheduler {
     private void doMarkAlive(Node node) {
         var cfgQueue = new Stack<NodeData>();
         var dataQueue = new Stack<NodeData>();
-        var mem = new Stack<NodeData>();
         markAlive(cfgQueue, node, true);
         // Mark all CFG nodes.
         while (!cfgQueue.isEmpty()) {
@@ -467,16 +464,16 @@ public class Scheduler {
             } else {
                 for (var in : node._inputs) if (in != null && !(in instanceof CFGNode)) markAlive(dataQueue, in, false);
             }
-            if (node instanceof StoreNode) mem.push(data);
-        }
-        // Handle store nodes and increase load with an anti-dep to the store.
-        while (!mem.isEmpty()) {
-            var data = mem.pop();
-            node = data.node;
-            for(var out:node.in(1)._outputs) {
-                if (out instanceof LoadNode) od(out).ifPresent(d->d.users++);
-            }
         }
+        // Writes, including New behind an aggregate, schedule before their
+        // anti-dependent reads in this reverse scheduling pass.
+        for (var load : data.values())
+            if (load.node instanceof LoadNode l)
+                for (var use : l.antiDeps())
+                    if ((use instanceof StoreNode || use instanceof NewNode) && data.containsKey(use)) {
+                        load.users++;
+                        readers.computeIfAbsent(use,k->new ArrayList<>()).add(load);
+                    }
     }
 
     /**