Small peep to drop simple store-updates out of loops

10 files changed, 72 insertions, 18 deletions

diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
index 1c354d5c..787333d9 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
@@ -36,6 +36,11 @@ public class MemPhiNode extends PhiNode {
                 setDef(i,CodeGen.CODE.add(mem.alias(_alias)));
                 return this;
             }
+        if( nIns()==3 && region() instanceof LoopNode loop && !loop.inProgress() &&
+            in(2) instanceof StoreNode st && st.mem()==this ) {
+            Node sink = st.sink(this);
+            if( sink!=null ) return sink;
+        }
         return super.idealize();
     }
 
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 4e4ab202..4e1d7ce3 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -109,6 +109,46 @@ public class StoreNode extends MemOpNode {
         return null;
     }
 
+    // Phi(mem, Store(phi,ptr,off,val)) -> Store(mem,ptr,off,Phi(load(mem),val)).
+    // With no observers of the backedge store, only the last value matters.
+    // The entry load preserves the field even when the loop takes zero trips.
+    Node sink(MemPhiNode phi) {
+        phi.addDepForwards(this);
+        if( nOuts()!=1 ) return null;
+        phi.addDep(ptr());
+        // Start with a fixed field of an allocation dominating the loop.
+        // In particular, do not sink stores through a loop-varying address.
+        if( !(ptr() instanceof ProjNode p) || !(p.in(0) instanceof NewNode obj) ||
+            !(ptr()._type instanceof TypeMemPtr tmp) || tmp._obj.isAry() ||
+            !(off() instanceof ConstantNode) || err()!=null ) return null;
+        LoopNode loop = (LoopNode)phi.region();
+        // Bulk splitting identifies precise slices by Region/alias. Finish it
+        // before replacing this memory point with a Store.
+        for( Node use : loop._outputs )
+            if( use instanceof BulkMemPhiNode ) {
+                phi.addDepForwards(use);
+                return null;
+            }
+        phi.addDep(obj);
+        CFGNode ctrl = loop.entry();
+        while( ctrl!=null && ctrl!=obj.cfg0() ) {
+            phi.addDep(ctrl);
+            ctrl=ctrl.idom(phi);
+        }
+        if( ctrl==null ) return null;
+
+        Node mem = phi.in(1);
+        Node init = new LoadNode(_loc,_name,_alias,_declaredType,mem,ptr(),off()).peephole();
+        Node value = CodeGen.CODE.add(new PhiNode(_name,_declaredType,loop,init,val()).peephole());
+        Node sink = new StoreNode(_loc,_name,_alias,_declaredType,mem,ptr(),off(),value,_init);
+        // Break the memory cycle, killing the old store. Keep the Phi alive
+        // even if that store was its last use, until our caller replaces it.
+        phi.keep();
+        phi.setDef(2,mem);
+        phi.unkeep();
+        return sink;
+    }
+
     // Check that "mem" has no uses except "this"
     private boolean checkOnlyUse(Node mem) {
         if( mem.nOuts()==1 ) return true;
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index e93da54b..3d5d2686 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -36,7 +36,8 @@ public class Chapter11Test {
         var stop = code._stop;
         int[] phis = {0};
         stop.walk(n -> {
-            if (n instanceof MemPhiNode) phis[0]++;
+            // Store sinking can replace field memory Phis with value Phis.
+            if (n instanceof PhiNode) 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);
@@ -44,7 +45,7 @@ public class Chapter11Test {
                 !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode) && !(n instanceof ParmNode));
             return null;
         });
-        assertTrue(phis[0]>=3);
+        assertTrue(phis[0]>=4); // Three fields and the loop counter.
         assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4));
     }
 
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java
index 6196f9af..26bf35d2 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java
@@ -460,13 +460,21 @@ return sq(arg) + sq(3);
 
     private static java.util.ArrayList<String> memoryPhis(Node stop) {
         var phis = new java.util.ArrayList<String>();
-        stop.walk(n -> {
+        // Count only definitions reachable from Stop, as instruction selection does.
+        // A dead Phi cycle can still appear through the reverse use edges.
+        var seen = new java.util.BitSet();
+        var work = new java.util.ArrayList<Node>();
+        work.add(stop);
+        for( int i=0; i<work.size(); i++ ) {
+            Node n = work.get(i);
+            if( n==null || seen.get(n._nid) ) continue;
+            seen.set(n._nid);
+            for( Node def : n._inputs ) work.add(def);
             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;
     }
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index d2bf9df6..fdcc0817 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -237,8 +237,8 @@ s.cs[0] =  67; // C
 s.cs[1] = 108; // l
 hashCode(s);
 """;
-        testTarget(src,"x86_64_v2", "SystemV",0,null);
-        testTarget(src,"riscv"    , "SystemV",0,null);
+        testTarget(src,"x86_64_v2", "SystemV",9,null);
+        testTarget(src,"riscv"    , "SystemV",3,null);
         testTarget(src,"arm"      , "SystemV",0,null);
     }
 
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 9bfb8c3f..5b2c3a54 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -337,8 +337,8 @@ public class Chapter21Test {
     @Test public void testInfinite() {
         String src = "struct S { int i; }; !S !s = new S; while(1) s.i++;";
         testCPU(src,"x86_64_v2", "SystemV",0,"return Top;");
-        testCPU(src,"riscv"    , "SystemV",2,"return Top;");
-        testCPU(src,"arm"      , "SystemV",2,"return Top;");
+        testCPU(src,"riscv"    , "SystemV",0,"return Top;");
+        testCPU(src,"arm"      , "SystemV",0,"return Top;");
     }
 
     @Test
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
index d34b117d..c77221bf 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
@@ -182,8 +182,8 @@ public class Chapter22Test {
     @Test public void testInfiniteReturn() {
         String src = "struct S { int i; }; !S !s = new S; while(1) s.i++; return s.i;";
         testCPU(src,"x86_64_v2","SystemV",0,"return Top;");
-        testCPU(src,"riscv","SystemV",2,"return Top;");
-        testCPU(src,"arm","SystemV",2,"return Top;");
+        testCPU(src,"riscv","SystemV",0,"return Top;");
+        testCPU(src,"arm","SystemV",0,"return Top;");
     }
 
 
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java
index 75e79664..7ad340c2 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java
@@ -362,7 +362,7 @@ return Scan.peek(s,'q');
         CodeGen code = new CodeGen(src).parse().opto().typeCheck();
         assertEquals("return Phi(Region,0,1);", code._stop.toString());
         assertEquals("1", Eval2.eval(code, 0));
-        testCPU(src,"x86_64_v2", "Win64"  ,17,null);
+        testCPU(src,"x86_64_v2", "Win64"  ,23,null);
     };
 
     @Test
@@ -414,7 +414,7 @@ return s.require('[');
         CodeGen code = new CodeGen(src).parse().opto().typeCheck();
         assertEquals("return (.[]==91);", code._stop.toString());
         assertEquals("1", Eval2.eval(code, 0));
-        testCPU(src,"x86_64_v2", "Win64"  ,16,null);
+        testCPU(src,"x86_64_v2", "Win64"  ,4,null);
     };
 
 
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java
index 3a2a957f..58c0d7f8 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java
@@ -624,7 +624,7 @@ return Scan.peek(s,'q');
         CodeGen code = new CodeGen(src).parse().opto().typeCheck();
         assertEquals("return Phi(Region,0,1);", code._stop.toString());
         assertEquals("1", Eval2.eval(code, 0));
-        testCPU(src,"x86_64_v2", "Win64"  ,17,null);
+        testCPU(src,"x86_64_v2", "Win64"  ,23,null);
     };
 
     @Test
@@ -676,7 +676,7 @@ return s.require('[');
         CodeGen code = new CodeGen(src).parse().opto().typeCheck();
         assertEquals("return (.[]==91);", code._stop.toString());
         assertEquals("1", Eval2.eval(code, 0));
-        testCPU(src,"x86_64_v2", "Win64"  ,16,null);
+        testCPU(src,"x86_64_v2", "Win64"  ,4,null);
     };
 
     @Test
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java
index 8e19426c..e97194af 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java
@@ -141,12 +141,12 @@ public class MemoryEncodingTest {
     }
 
     @Test public void testNeverMemory() {
-        // A synthetic exit must retain both precise slices of a no-exit loop.
+        // A varying pointer prevents store sinking: the synthetic exit needs both slices.
         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; }
+                !S !a=new S; !S !b=new S; !S !p=a;
+                if( arg ) while( 1 ) { p.x+=arg; p.y+=p.x; p=p==a ? b : a; }
                 return a.x+a.y;
                 """).driver(CodeGen.Phase.LoopTree);
             assertNotNull(code._stop.walk(n -> {