Chapter 11: Splitting Memory

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

5 files changed, 109 insertions, 21 deletions

diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index f39b1e78..9a5e4677 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -169,7 +169,7 @@ while (arg) {
 return bar.a;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop10,0,(Phi_$mem+2));", stop.toString());
+        assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString());
     }
 
     @Test
@@ -221,7 +221,7 @@ if( bar ) bar.a = 1;
 return bar;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region15,null,new Bar);", stop.toString());
+        assertEquals("return Phi(Region16,null,new Bar);", stop.toString());
     }
 
     @Test
@@ -237,7 +237,7 @@ else bar.a = 1;
 return rez;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region32,4,3);", stop.toString());
+        assertEquals("return Phi(Region34,4,3);", stop.toString());
     }
 
     @Test
@@ -290,9 +290,8 @@ while( i.x < i.len ) {
 return sum;
 """);
         StopNode stop = parser.parse().iterate();
-        // The preceding len store keeps the initial x load on the bulk chain.
-        assertEquals("return Phi(Loop13,0,(Phi(Loop,.x,(Phi_x+1))+Phi_sum));", stop.toString());
-        assertEquals(10L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,5));
+        assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_$2+1))+Phi_sum));", stop.toString());
+        assertEquals(10L,Evaluator.evaluate(stop,5));
     }
 
 
@@ -312,7 +311,7 @@ while(arg) {
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop10,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop11,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString());
     }
 
     @Test
@@ -329,7 +328,7 @@ while(arg) {
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop13,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString());
     }
 
 
@@ -346,7 +345,7 @@ while(arg < 10) {
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop10,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop11,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString());
     }
 
     @Test
@@ -480,8 +479,7 @@ return 0;
         assertEquals(2244L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,1));
     }
 
-    @Test public void testMemoryAcrossNestedLoops() {
-        var stop = new Parser("""
+    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;
@@ -498,7 +496,10 @@ return 0;
                 arg = arg - 1;
             }
             return s;
-            """).parse().iterate();
+            """;
+
+    @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);
@@ -524,7 +525,7 @@ return 0;
         }
     }
 
-    @Test public void testDropLoads() {
+    @Test public void testKeepLoadsAtMerge() {
         StopNode stop = new Parser("""
             struct S { int x; }
             S a = new S; S b = new S;
@@ -535,7 +536,8 @@ return 0;
             if (arg>1) v=p.x; else v=q.x;
             return v;
             """).parse().iterate();
-        assertEquals(1,countMemoryNodes(stop,LoadNode.class,new BitSet()));
+        // 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));
@@ -548,6 +550,7 @@ return 0;
             if (arg) s.x=arg+1; else s.x=arg+2;
             return s;
             """).parse().iterate();
+        // Releasing the old aggregate exposes the overwritten initializing Store.
         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]);
diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
new file mode 100644
index 00000000..5f92c9c1
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.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 Chapter11Test {
+    @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/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java
index c9eb2747..f9c580cc 100644
--- a/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/src/test/java/com/seaofnodes/simple/TypeTest.java
@@ -22,10 +22,23 @@ public class TypeTest {
         Assert.assertNotEquals(s1, s1.dual());
         Assert.assertEquals(s1, s1.dual().glb());
 
-        assertEquals(TypeStruct.BOT, s1.meet(s2));
-        assertEquals(TypeMem.BOT, TypeMem.TOP.meet(TypeMem.BOT));
-        assertEquals(TypeMem.TOP, TypeMem.BOT.dual());
-        assertEquals(TypeMem.BOT, TypeMem.TOP.dual());
+        TypeMem m1 = TypeMem.make(1);
+        TypeMem m2 = TypeMem.make(2);
+        TypeMem m3 = TypeMem.make(3);
+        TypeMem m4 = TypeMem.make(4);
+
+        Assert.assertNotEquals(m1, m2);
+        Assert.assertNotEquals(m2, m3);
+        Assert.assertNotEquals(m3, m4);
+
+        Assert.assertEquals(TypeStruct.BOT, s1.meet(s2));
+        Assert.assertEquals(TypeMem   .BOT, m1.meet(m2));
+        Assert.assertEquals(TypeMem   .BOT, m2.meet(m3));
+        Assert.assertEquals(TypeMem   .BOT, m3.meet(m4));
+
+        Assert.assertEquals(TypeMem.BOT, m1.glb());
+        Assert.assertEquals(m1, m1.dual());
+        Assert.assertEquals(TypeMem.TOP, m1.glb().dual());
 
         TypeMemPtr ptr1 = TypeMemPtr.make(s1);
         Assert.assertEquals(s1, ptr1._obj);
diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index bddcc596..ac7c5e09 100644
--- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -138,6 +138,7 @@ public class Evaluator {
             case CastNode     cast  -> val(cast.in(1));
             case LoadNode     load  -> load(load);
             case StoreNode    store -> store(store);
+            case MemMergeNode merge -> MEMORY;
             case NewNode      alloc -> alloc(alloc);
             case ProjNode     proj  -> ((Object[])val(proj.ctrl()))[proj._idx];
             default                 -> throw new AssertionError("Unexpected node " + node);
diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
index 674d12f5..48ac0562 100644
--- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
+++ b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
@@ -215,7 +215,7 @@ public class Scheduler {
     private void refinePlacement(NodeData data, BasicBlock block) {
         assert !isPinnedNode(data);
         data.block = data.block == null ? block : dom(data.block, block);
-        assert isValid(data);
+        assert isValid(data) : data.node.uniqueName()+" at "+data.block.entry.uniqueName();
     }
 
     /**
@@ -250,6 +250,12 @@ public class Scheduler {
                 // so do that now.
                 var mem = l.in(1);
                 for(var out : mem._outputs) {
+                    // Aggregates describe partitions; they do not overwrite
+                    // memory. Only users of this alias constrain the load.
+                    if (out instanceof MemMergeNode || out instanceof ReturnNode) continue;
+                    if (out instanceof StoreNode s && s._alias != l._alias) continue;
+                    if (out instanceof MemPhiNode p && p._alias != l._alias) continue;
+                    if (out instanceof BulkMemPhiNode p && p.isSplit(l._alias)) continue;
                     if (out instanceof PhiNode p) {
                         var r = p.in(0);
                         for (int i = 1; i < p.nIns(); i++) {
@@ -271,7 +277,7 @@ public class Scheduler {
                 // 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);
+                    if (out instanceof LoadNode l && l._alias==s._alias) od(out).ifPresent(this::decUsers);
                 }
             }
         }
@@ -467,7 +473,8 @@ public class Scheduler {
             var data = mem.pop();
             node = data.node;
             for(var out:node.in(1)._outputs) {
-                if (out instanceof LoadNode) od(out).ifPresent(d->d.users++);
+                if (out instanceof LoadNode l && l._alias==((StoreNode)node)._alias)
+                    od(out).ifPresent(d->d.users++);
             }
         }
     }