From 81b654d76444d747fdf1d053760e507b50f26e18 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 5 Oct 2026 15:38:06 -0700 Subject: Small peep to drop simple store-updates out of loops --- .../java/com/seaofnodes/simple/node/LoadNode.java | 1 + .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter17bTest.java | 48 +++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 1 + .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 5 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 1 + .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 14 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 1 + .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 14 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 1 + .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 4 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 6 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 1 + .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 4 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 6 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 1 + .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter23Test.java | 4 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 6 +- .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter23Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter24Test.java | 4 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 6 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 5 +- .../com/seaofnodes/simple/node/MemPhiNode.java | 5 + .../java/com/seaofnodes/simple/node/StoreNode.java | 40 +++++ .../java/com/seaofnodes/simple/Chapter21Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter23Test.java | 4 +- docs/2026_REBASE/README.md | 5 +- docs/2026_REBASE/assets/memory-final.json | 198 ++++++++------------- docs/2026_REBASE/assets/memory-final.svg | 136 +++++++------- docs/2026_REBASE/slides.js | 6 +- docs/chapter-backports.md | 28 +++ .../main/java/com/seaofnodes/print/IRPrinter.java | 2 +- 65 files changed, 762 insertions(+), 280 deletions(-) diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 85ad243b..eaab680c 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -52,6 +52,7 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { + if( ptr()._type==Type.TOP ) return Type.TOP; // Dead pointer, not a type error. Type t = MemMergeNode.contents(mem(),_alias,this); // Update declared forward ref to the actual. if( _declaredType.isFRef() && t instanceof TypeMemPtr tmp && !tmp.isFRef() ) diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index 6aae00f9..693ad944 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -34,6 +34,11 @@ public class MemPhiNode extends PhiNode { setDef(i,IterPeeps.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/chapter17b/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index a5f04dd2..962618ef 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -101,6 +101,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) { + addDepForwards(phi); + if( nOuts()!=1 ) return null; + ptr().addDep(phi); + // 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 ) { + use.addDepForwards(phi); + return null; + } + obj.addDep(phi); + CFGNode ctrl = loop.entry(); + while( ctrl!=null && ctrl!=obj.cfg0() ) { + ctrl.addDep(phi); + ctrl=ctrl.idom(phi); + } + if( ctrl==null ) return null; + + Node mem = phi.in(1); + Node init = new LoadNode(_name,_alias,_declaredType,mem,ptr(),off()).peephole(); + Node value = new PhiNode(_name,_declaredType,loop,init,val()).peephole(); + Node sink = new StoreNode(_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/chapter17b/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter17b/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 60ff05d8..f0caed02 100644 --- a/chapter17b/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter17b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -34,7 +34,8 @@ public class Chapter11Test { """).parse().iterate(); 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=3); + assertTrue(phis[0]>=4); // Three fields and the loop counter. assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); } diff --git a/chapter17b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter17b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 976691fc..08c210fb 100644 --- a/chapter17b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter17b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.node.StoreNode; import org.junit.Test; import org.junit.Ignore; import static org.junit.Assert.assertEquals; @@ -9,6 +10,53 @@ import static org.junit.Assert.fail; public class Chapter17bTest { + @Test public void testSinkLoopStores() { + StopNode stop = new Parser(""" + struct Totals { int sum; int visits; }; + val t = new Totals { sum=7; visits=2; }; + val data = new int[4]; + for( int i=0; i { + if( n instanceof StoreNode st && !st._name.equals("[]") ) { + assertEquals(stop.in(0).in(0),st.in(0)); // Both stores at the exit. + stores[0]++; + } + return null; + }); + assertEquals(2,stores[0]); + for( int arg : new int[]{-1,0,1,3,4,5} ) { + long n = Math.max(0,Math.min(arg,4)); + var obj = (Evaluator.Obj)Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(new Object[]{7+n*arg+n*(n-1)/2,2+n},obj.fields()); + } + } + + @Test public void testKeepObservedLoopStore() { + StopNode stop = new Parser(""" + struct S { int x; }; + val a = new S; + val b = new S; + val p = arg ? a : b; + int sum=0; + for( int i=0; i<4; i++ ) { + a.x=i+1; + sum+=p.x; + } + return sum; + """).parse().iterate(); + stop.typeCheck(); + assertEquals(0L,Evaluator.evaluate(stop,0)); + assertEquals(10L,Evaluator.evaluate(stop,1)); + } + @Test public void testJig() { Parser parser = new Parser("return 1;"); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java index edde1dc1..5190bf08 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -53,6 +53,7 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { + if( ptr()._type==Type.TOP ) return Type.TOP; // Dead pointer, not a type error. Type t = MemMergeNode.contents(mem(),_alias,this); // Update declared forward ref to the actual. if( _declaredType.isFRef() && t instanceof TypeMemPtr tmp && !tmp.isFRef() ) diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index 6aae00f9..693ad944 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -34,6 +34,11 @@ public class MemPhiNode extends PhiNode { setDef(i,IterPeeps.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/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 3c0b0e73..de17bbad 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -104,6 +104,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) { + addDepForwards(phi); + if( nOuts()!=1 ) return null; + ptr().addDep(phi); + // 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 ) { + use.addDepForwards(phi); + return null; + } + obj.addDep(phi); + CFGNode ctrl = loop.entry(); + while( ctrl!=null && ctrl!=obj.cfg0() ) { + ctrl.addDep(phi); + 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 = 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/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 01e37a43..9fd392d2 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -35,7 +35,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=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/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 1991c62c..a06d1291 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -51,6 +51,7 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { + if( ptr()._type==Type.TOP ) return Type.TOP; // Dead pointer, not a type error. Type t = MemMergeNode.contents(mem(),_alias,this); // Update declared forward ref to the actual. if( _declaredType.isFRef() && t instanceof TypeMemPtr tmp && !tmp.isFRef() ) diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index 411370e1..38cbcd5b 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/chapter19/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/chapter19/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 0d39980a..86c759bd 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -88,6 +88,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) { + addDepForwards(phi); + if( nOuts()!=1 ) return null; + ptr().addDep(phi); + // 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 ) { + use.addDepForwards(phi); + return null; + } + obj.addDep(phi); + CFGNode ctrl = loop.entry(); + while( ctrl!=null && ctrl!=obj.cfg0() ) { + ctrl.addDep(phi); + 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 = 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/chapter19/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 9dddb9cf..14819869 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -35,7 +35,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=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/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 1bc5175d..7111c50e 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -483,13 +483,21 @@ return sq(arg) + sq(3); private static java.util.ArrayList memoryPhis(Node stop) { var phis = new java.util.ArrayList(); - 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(); + work.add(stop); + for( int i=0; i 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) { + addDepForwards(phi); + if( nOuts()!=1 ) return null; + ptr().addDep(phi); + // 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 ) { + use.addDepForwards(phi); + return null; + } + obj.addDep(phi); + CFGNode ctrl = loop.entry(); + while( ctrl!=null && ctrl!=obj.cfg0() ) { + ctrl.addDep(phi); + 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 = 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/chapter20/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter11Test.java index a38e93c1..439333ca 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter20/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=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/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java index f7329e63..3cc7d5ab 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -452,13 +452,21 @@ return sq(arg) + sq(3); private static java.util.ArrayList memoryPhis(Node stop) { var phis = new java.util.ArrayList(); - 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(); + work.add(stop); + for( int i=0; i 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/chapter21/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter11Test.java index a38e93c1..439333ca 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter21/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=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/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java index c230e615..0a92dc20 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -384,13 +384,21 @@ return sq(arg) + sq(3); private static java.util.ArrayList memoryPhis(Node stop) { var phis = new java.util.ArrayList(); - 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(); + work.add(stop); + for( int i=0; i { diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java index f1a9cb07..3084b4f7 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -51,6 +51,7 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { + if( ptr()._type==Type.TOP ) return Type.TOP; // Dead pointer, not a type error. Type t = MemMergeNode.contents(mem(),_alias,this); // Update declared forward ref to the actual. if( _declaredType.isFRef() && t instanceof TypeMemPtr tmp && !tmp.isFRef() ) diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index e5a29329..1349cadb 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/chapter22/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/chapter22/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/StoreNode.java index eecaf8f7..ecda014b 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -105,6 +105,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/chapter22/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter11Test.java index a38e93c1..439333ca 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter22/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=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/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java index e7b72e0a..dee7d928 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -385,13 +385,21 @@ return sq(arg) + sq(3); private static java.util.ArrayList memoryPhis(Node stop) { var phis = new java.util.ArrayList(); - 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(); + work.add(stop); + for( int i=0; i { diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 0a9dae59..06226df0 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -52,6 +52,7 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { + if( ptr()._type==Type.TOP ) return Type.TOP; // Dead pointer, not a type error. if( !(mem()._type instanceof TypeMem mem) ) return _declaredType; // No memory yet? Declared type assert !_declaredType.isFRef(); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index 7e54f50f..bada20ac 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/chapter23/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/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 5d3e10e5..603a0607 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java index e93da54b..3d5d2686 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter23/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=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/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java index c388726c..d1e5fa70 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -385,13 +385,21 @@ return sq(arg) + sq(3); private static java.util.ArrayList memoryPhis(Node stop) { var phis = new java.util.ArrayList(); - 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(); + work.add(stop); + for( int i=0; i { 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=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 memoryPhis(Node stop) { var phis = new java.util.ArrayList(); - 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(); + work.add(stop); + for( int i=0; i { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 3e618472..dfe8794d 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -104,6 +104,9 @@ public class MemMergeNode extends Node { // Collapse stacked merged-mem if( in(1) instanceof MemMergeNode mem ) { + // A dead memory cycle can lose its last use when we bypass mem. + // Keep the peephole's result alive until the worklist sees it. + keep(); // Goal is to swap my default mem with mem's default mem for( int i=2; i 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 || _alias==1 || _size==0 || _init ) 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,null,mem,ptr(),off()).peephole(); + Node value = CodeGen.CODE.add(new PhiNode(_name,loop,init,val()).peephole()); + Node sink = new StoreNode(_loc,_name,_alias,_con,null,mem,ptr(),off(),value,_init,_size); + // 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/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index bfce93b9..4d610a42 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -283,8 +283,8 @@ return new _s0.v1; @Test public void testInfinite() { 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;"); } @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 7c46567a..053621bd 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -279,7 +279,7 @@ return _s.peek('q'); CodeGen code = new CodeGen(src).parse().opto().typeCheck(); assertEquals("return Phi(Region,0,1);", code.print()); assertEquals("1", Eval2.eval(code, 0)); - testCPU(src,"x86_64_v2", "win64",1,null); + testCPU(src,"x86_64_v2", "win64",23,null); }; @Test @@ -334,7 +334,7 @@ return _s.require('['); CodeGen code = new CodeGen(src).parse().opto().typeCheck(); assertEquals("return (.[]==91);", code.print()); assertEquals("1", Eval2.eval(code, 0)); - testCPU(src,"x86_64_v2", "win64", 0, null); + testCPU(src,"x86_64_v2", "win64",4, null); }; diff --git a/docs/2026_REBASE/README.md b/docs/2026_REBASE/README.md index 925be1ed..4c3b5114 100644 --- a/docs/2026_REBASE/README.md +++ b/docs/2026_REBASE/README.md @@ -140,13 +140,16 @@ show the global scheduler moving instructions. Discuss GCM from the slide. |---|---|---| | [arithmetic.smp](demos/arithmetic.smp) | 04 | Final expression `2*arg+6`; 51 capture frames | | [control.smp](demos/control.smp) | 08 | Sum 1 through `abs(arg)`; 65 frames | -| [memory.smp](demos/memory.smp) | 17b | Two loops, array/object memory; 319 frames, 54 final nodes | +| [memory.smp](demos/memory.smp) | 17b | Two loops; final totals stored after the loop; 333 frames, 52 final nodes | | [aliases.smp](demos/aliases.smp) | 17b | Short follow-up: writing `p.y` leaves `p.x` unchanged; result 0 | | [inline.smp](demos/inline.smp) | 18 | Two single-caller functions disappear; `return 11;`; 161 frames | | [sccp.smp](demos/sccp.smp) | 24; viewer 25 | Return value 1 verified in the final graph; 76 frames, about 0.38 MB | The large memory example has runtime result `4*arg+10`. It retains loops and memory operations; that formula is not its claimed optimized graph. +The `sum` and `visits` fields become scalar loop Phis, with one store each +afterward. Their memory Phis disappear, and GCM can also place the `Totals` +allocation after the loop. The array initialization still needs its memory Phi. For SCCP, proving a constant result alone does not license deleting effects or a possibly nonterminating loop. diff --git a/docs/2026_REBASE/assets/memory-final.json b/docs/2026_REBASE/assets/memory-final.json index e2f378ed..3900b426 100644 --- a/docs/2026_REBASE/assets/memory-final.json +++ b/docs/2026_REBASE/assets/memory-final.json @@ -1,7 +1,7 @@ { "ver": 1, "comp": "rebase-memory", - "step": 318, + "step": 332, "roots": [ 2, 3 @@ -989,45 +989,6 @@ ], "proj": null }, - { - "id": 94, - "label": "st_sum", - "type": "MEM#2:Bot", - "kind": "MEM", - "edges": [ - { - "idx": 0, - "def": 0, - "role": "CTRL", - "label": null - }, - { - "idx": 1, - "def": 104, - "role": "MEM", - "label": null - }, - { - "idx": 2, - "def": 15, - "role": "DATA", - "label": null - }, - { - "idx": 3, - "def": 4, - "role": "DATA", - "label": null - }, - { - "idx": 4, - "def": 88, - "role": "DATA", - "label": null - } - ], - "proj": null - }, { "id": 99, "label": "Add", @@ -1042,7 +1003,7 @@ }, { "idx": 1, - "def": 138, + "def": 141, "role": "DATA", "label": null }, @@ -1055,45 +1016,6 @@ ], "proj": null }, - { - "id": 100, - "label": "st_visits", - "type": "MEM#3:Bot", - "kind": "MEM", - "edges": [ - { - "idx": 0, - "def": 0, - "role": "CTRL", - "label": null - }, - { - "idx": 1, - "def": 132, - "role": "MEM", - "label": null - }, - { - "idx": 2, - "def": 15, - "role": "DATA", - "label": null - }, - { - "idx": 3, - "def": 51, - "role": "DATA", - "label": null - }, - { - "idx": 4, - "def": 99, - "role": "DATA", - "label": null - } - ], - "proj": null - }, { "id": 103, "label": "Add", @@ -1121,33 +1043,6 @@ ], "proj": null }, - { - "id": 104, - "label": "MemPhi_2", - "type": "MEM#2:Bot", - "kind": "PHI", - "edges": [ - { - "idx": 0, - "def": 65, - "role": "ASSOC", - "label": null - }, - { - "idx": 1, - "def": 16, - "role": "MEM", - "label": null - }, - { - "idx": 2, - "def": 94, - "role": "MEM", - "label": null - } - ], - "proj": null - }, { "id": 106, "label": "MemMerge", @@ -1168,13 +1063,13 @@ }, { "idx": 2, - "def": 104, + "def": 146, "role": "MEM", "label": null }, { "idx": 3, - "def": 132, + "def": 142, "role": "MEM", "label": null }, @@ -1207,7 +1102,7 @@ }, { "idx": 1, - "def": 138, + "def": 141, "role": "DATA", "label": null }, @@ -1302,9 +1197,9 @@ "proj": null }, { - "id": 132, - "label": "MemPhi_3", - "type": "MEM#3:Bot", + "id": 141, + "label": "Phi_visits", + "type": "int", "kind": "PHI", "edges": [ { @@ -1313,6 +1208,33 @@ "role": "ASSOC", "label": null }, + { + "idx": 1, + "def": 4, + "role": "DATA", + "label": null + }, + { + "idx": 2, + "def": 99, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 142, + "label": "st_visits", + "type": "MEM#3:int", + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, { "idx": 1, "def": 16, @@ -1321,34 +1243,58 @@ }, { "idx": 2, - "def": 100, - "role": "MEM", + "def": 15, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 51, + "role": "DATA", + "label": null + }, + { + "idx": 4, + "def": 141, + "role": "DATA", "label": null } ], "proj": null }, { - "id": 138, - "label": "Phi_visits", - "type": "int", - "kind": "PHI", + "id": 146, + "label": "st_sum", + "type": "MEM#2:int", + "kind": "MEM", "edges": [ { "idx": 0, - "def": 65, - "role": "ASSOC", + "def": 0, + "role": "CTRL", "label": null }, { "idx": 1, + "def": 16, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 15, + "role": "DATA", + "label": null + }, + { + "idx": 3, "def": 4, "role": "DATA", "label": null }, { - "idx": 2, - "def": 99, + "idx": 4, + "def": 131, "role": "DATA", "label": null } @@ -1389,15 +1335,11 @@ 91, 92, 93, - 94, 99, - 100, 103, - 104, 112, 131, - 132, - 138 + 141 ] } ] diff --git a/docs/2026_REBASE/assets/memory-final.svg b/docs/2026_REBASE/assets/memory-final.svg index 205fea1b..47daa792 100644 --- a/docs/2026_REBASE/assets/memory-final.svg +++ b/docs/2026_REBASE/assets/memory-final.svg @@ -1,4 +1,4 @@ -#3[0] → #115 · CTRL#4[0] → #2 · ASSOC#5[0] → #2 · ASSOC#12[0] → #2 · ASSOC#13[2] → #7 · MEM#13[3] → #7 · MEM#14[0] → #6 · CTRL#14[1] → #13 · MEM#14[2] → #12 · DATA#14[3] → #4 · DATA#14[4] → #4 · DATA#18[0] → #2 · ASSOC#24[0] → #2 · ASSOC#26[4] → #7 · MEM#26[5] → #7 · MEM#27[0] → #6 · CTRL#27[1] → #26 · MEM#27[2] → #24 · DATA#27[3] → #18 · DATA#27[4] → #4 · DATA#32[1] → #6 · CTRL#32[2] → #41 · CTRL#34[1] → #4 · DATA#34[2] → #60 · DATA#35[1] → #34 · DATA#35[2] → #18 · DATA#40[0] → #32 · CTRL#40[1] → #35 · DATA#46[0] → #2 · ASSOC#51[0] → #2 · ASSOC#52[0] → #2 · ASSOC#53[1] → #34 · DATA#53[2] → #52 · DATA#54[1] → #53 · DATA#54[2] → #51 · DATA#56[1] → #34 · DATA#56[2] → #8 · DATA#57[0] → #41 · CTRL#57[1] → #124 · MEM#57[2] → #28 · DATA#57[3] → #54 · DATA#57[4] → #56 · DATA#60[1] → #34 · DATA#60[2] → #46 · DATA#65[1] → #42 · CTRL#65[2] → #74 · CTRL#67[1] → #4 · DATA#67[2] → #103 · DATA#68[1] → #67 · DATA#68[2] → #18 · DATA#73[0] → #65 · CTRL#73[1] → #68 · DATA#88[1] → #131 · DATA#88[2] → #93 · DATA#91[1] → #67 · DATA#91[2] → #52 · DATA#92[1] → #91 · DATA#92[2] → #51 · DATA#93[0] → #74 · CTRL#93[1] → #124 · MEM#93[2] → #28 · DATA#93[3] → #92 · DATA#99[1] → #141 · DATA#99[2] → #46 · DATA#103[1] → #67 · DATA#103[2] → #46 · DATA#106[1] → #7 · MEM#106[2] → #146 · MEM#106[3] → #142 · MEM#106[4] → #29 · MEM#106[5] → #124 · MEM#112[1] → #141 · DATA#112[2] → #131 · DATA#115[0] → #75 · CTRL#115[1] → #106 · MEM#115[2] → #112 · DATA#124[1] → #29 · MEM#124[2] → #57 · MEM#131[1] → #4 · DATA#131[2] → #88 · DATA#141[1] → #4 · DATA#141[2] → #99 · DATA#142[1] → #16 · MEM#142[2] → #15 · DATA#142[3] → #51 · DATA#142[4] → #141 · DATA#146[1] → #16 · MEM#146[2] → #15 · DATA#146[3] → #4 · DATA#146[4] → #131 · DATAStart  #2[ Ctrl, MemBot, int]#2 Start [ Ctrl, MemBot, int] [0] → — ASSOC [1] → — CTRL -[2] → — CTRL012Stop  #3#3 Stop +[2] → — CTRL012Stop  #3#3 Stop Bot [0] → #115 CTRL0Con  #40#4 Con 0 -[0] → #2 ASSOC0Xctrl  #5~Ctrl#5 Xctrl +[0] → #2 ASSOC0Xctrl  #5~Ctrl#5 Xctrl ~Ctrl [0] → #2 ASSOC0$ctrl  #6/0Ctrl#6 $ctrl @@ -95,28 +95,28 @@ MemBot [0] → — CTRL [1] → — DATA [2] → #7 MEM -[3] → #7 MEM0123new_Totals  #14[ *Totals {int !sum; int !visits; }, MemBot]#14 new_Totals +[3] → #7 MEM0123new_Totals  #14[ *Totals {int !sum; int !visits; }, MemBot]#14 new_Totals [ *Totals {int !sum; int !visits; }, MemBot] [0] → #6 CTRL [1] → #13 MEM [2] → #12 DATA [3] → #4 DATA -[4] → #4 DATA01234Totals  #15/0*Totals {int !sum; int !visits; }#15 Totals +[4] → #4 DATA01234Totals  #15/0*Totals {int !sum; int !visits; }#15 Totals Projection 0 of #14 *Totals {int !sum; int !visits; } -[0] → #14 DATA$mem  #16/1MemBot#16 $mem +[0] → #14 DATA$mem  #16/1MemBot#16 $mem Projection 1 of #14 MemBot [0] → #14 MEMCon  #184#18 Con 4 -[0] → #2 ASSOC0Con  #2440#24 Con +[0] → #2 ASSOC0Con  #2440#24 Con 40 -[0] → #2 ASSOC0MemMerge  #26MemBot#26 MemMerge +[0] → #2 ASSOC0MemMerge  #26MemBot#26 MemMerge MemBot [0] → — CTRL @@ -124,197 +124,187 @@ MemBot [2] → — DATA [3] → — DATA [4] → #7 MEM -[5] → #7 MEM012345new_ary_int  #27[ *[int] {int #; int ![]; }, MemBot]#27 new_ary_int +[5] → #7 MEM012345new_ary_int  #27[ *[int] {int #; int ![]; }, MemBot]#27 new_ary_int [ *[int] {int #; int ![]; }, MemBot] [0] → #6 CTRL [1] → #26 MEM [2] → #24 DATA [3] → #18 DATA -[4] → #4 DATA01234[int]  #28/0*[int] {int #; int ![]; }#28 [int] +[4] → #4 DATA01234[int]  #28/0*[int] {int #; int ![]; }#28 [int] Projection 0 of #27 *[int] {int #; int ![]; } -[0] → #27 DATA$mem  #29/1MemBot#29 $mem +[0] → #27 DATA$mem  #29/1MemBot#29 $mem Projection 1 of #27 MemBot -[0] → #27 MEMLoop  #32Ctrl#32 Loop +[0] → #27 MEMLoop  #32Ctrl#32 Loop Ctrl [0] → — ASSOC [1] → #6 CTRL -[2] → #41 CTRL012Phi_i  #34int#34 Phi_i +[2] → #41 CTRL012Phi_i  #34int#34 Phi_i int [0] → #32 ASSOC [1] → #4 DATA -[2] → #60 DATA[0] → #32012LT  #35bool#35 LT +[2] → #60 DATA[0] → #32012LT  #35bool#35 LT bool [0] → — CTRL [1] → #34 DATA -[2] → #18 DATA012If  #40[ Ctrl, Ctrl]#40 If +[2] → #18 DATA012If  #40[ Ctrl, Ctrl]#40 If [ Ctrl, Ctrl] [0] → #32 CTRL -[1] → #35 DATA01True  #41/0Ctrl#41 True +[1] → #35 DATA01True  #41/0Ctrl#41 True Projection 0 of #40 Ctrl -[0] → #40 CTRLFalse  #42/1Ctrl#42 False +[0] → #40 CTRLFalse  #42/1Ctrl#42 False Projection 1 of #40 Ctrl -[0] → #40 CTRLCon  #461#46 Con +[0] → #40 CTRLCon  #461#46 Con 1 -[0] → #2 ASSOC0Con  #518#51 Con +[0] → #2 ASSOC0Con  #518#51 Con 8 -[0] → #2 ASSOC0Con  #523#52 Con +[0] → #2 ASSOC0Con  #523#52 Con 3 -[0] → #2 ASSOC0Shl  #53int#53 Shl +[0] → #2 ASSOC0Shl  #53int#53 Shl int [0] → — CTRL [1] → #34 DATA -[2] → #52 DATA012Add  #54int#54 Add +[2] → #52 DATA012Add  #54int#54 Add int [0] → — CTRL [1] → #53 DATA -[2] → #51 DATA012Add  #56int#56 Add +[2] → #51 DATA012Add  #56int#56 Add int [0] → — CTRL [1] → #34 DATA -[2] → #8 DATA012st_ary  #57MEM#5:Bot#57 st_ary +[2] → #8 DATA012st_ary  #57MEM#5:Bot#57 st_ary MEM#5:Bot [0] → #41 CTRL [1] → #124 MEM [2] → #28 DATA [3] → #54 DATA -[4] → #56 DATA01234Add  #60int#60 Add +[4] → #56 DATA01234Add  #60int#60 Add int [0] → — CTRL [1] → #34 DATA -[2] → #46 DATA012Loop  #65Ctrl#65 Loop +[2] → #46 DATA012Loop  #65Ctrl#65 Loop Ctrl [0] → — ASSOC [1] → #42 CTRL -[2] → #74 CTRL012Phi_i  #67int#67 Phi_i +[2] → #74 CTRL012Phi_i  #67int#67 Phi_i int [0] → #65 ASSOC [1] → #4 DATA -[2] → #103 DATA[0] → #65012LT  #68bool#68 LT +[2] → #103 DATA[0] → #65012LT  #68bool#68 LT bool [0] → — CTRL [1] → #67 DATA -[2] → #18 DATA012If  #73[ Ctrl, Ctrl]#73 If +[2] → #18 DATA012If  #73[ Ctrl, Ctrl]#73 If [ Ctrl, Ctrl] [0] → #65 CTRL -[1] → #68 DATA01True  #74/0Ctrl#74 True +[1] → #68 DATA01True  #74/0Ctrl#74 True Projection 0 of #73 Ctrl -[0] → #73 CTRLFalse  #75/1Ctrl#75 False +[0] → #73 CTRLFalse  #75/1Ctrl#75 False Projection 1 of #73 Ctrl -[0] → #73 CTRLAdd  #88int#88 Add +[0] → #73 CTRLAdd  #88int#88 Add int [0] → — CTRL [1] → #131 DATA -[2] → #93 DATA012Shl  #91int#91 Shl +[2] → #93 DATA012Shl  #91int#91 Shl int [0] → — CTRL [1] → #67 DATA -[2] → #52 DATA012Add  #92int#92 Add +[2] → #52 DATA012Add  #92int#92 Add int [0] → — CTRL [1] → #91 DATA -[2] → #51 DATA012ld_ary  #93int#93 ld_ary +[2] → #51 DATA012ld_ary  #93int#93 ld_ary int [0] → #74 CTRL [1] → #124 MEM [2] → #28 DATA -[3] → #92 DATA0123st_sum  #94MEM#2:Bot#94 st_sum -MEM#2:Bot - -[0] → — CTRL -[1] → #104 MEM -[2] → #15 DATA -[3] → #4 DATA -[4] → #88 DATA01234Add  #99int#99 Add +[3] → #92 DATA0123Add  #99int#99 Add int [0] → — CTRL -[1] → #138 DATA -[2] → #46 DATA012st_visits  #100MEM#3:Bot#100 st_visits -MEM#3:Bot - -[0] → — CTRL -[1] → #132 MEM -[2] → #15 DATA -[3] → #51 DATA -[4] → #99 DATA01234Add  #103int#103 Add +[1] → #141 DATA +[2] → #46 DATA012Add  #103int#103 Add int [0] → — CTRL [1] → #67 DATA -[2] → #46 DATA012MemPhi_2  #104MEM#2:Bot#104 MemPhi_2 -MEM#2:Bot - -[0] → #65 ASSOC -[1] → #16 MEM -[2] → #94 MEM[0] → #65012MemMerge  #106MemBot#106 MemMerge +[2] → #46 DATA012MemMerge  #106MemBot#106 MemMerge MemBot [0] → — CTRL [1] → #7 MEM -[2] → #104 MEM -[3] → #132 MEM +[2] → #146 MEM +[3] → #142 MEM [4] → #29 MEM -[5] → #124 MEM012345Add  #112int#112 Add +[5] → #124 MEM012345Add  #112int#112 Add int [0] → — CTRL -[1] → #138 DATA -[2] → #131 DATA012Return  #115[ Ctrl, MemBot, int]#115 Return +[1] → #141 DATA +[2] → #131 DATA012Return  #115[ Ctrl, MemBot, int]#115 Return [ Ctrl, MemBot, int] [0] → #75 CTRL [1] → #106 MEM -[2] → #112 DATA012MemPhi_5  #124MEM#5:Bot#124 MemPhi_5 +[2] → #112 DATA012MemPhi_5  #124MEM#5:Bot#124 MemPhi_5 MEM#5:Bot [0] → #32 ASSOC [1] → #29 MEM -[2] → #57 MEM[0] → #32012Phi_sum  #131int#131 Phi_sum +[2] → #57 MEM[0] → #32012Phi_sum  #131int#131 Phi_sum int [0] → #65 ASSOC [1] → #4 DATA -[2] → #88 DATA[0] → #65012MemPhi_3  #132MEM#3:Bot#132 MemPhi_3 -MEM#3:Bot - -[0] → #65 ASSOC -[1] → #16 MEM -[2] → #100 MEM[0] → #65012Phi_visits  #138int#138 Phi_visits +[2] → #88 DATA[0] → #65012Phi_visits  #141int#141 Phi_visits int [0] → #65 ASSOC [1] → #4 DATA -[2] → #99 DATA[0] → #65012Loop  #32Loop · 12 nodes−Fold regionLoop  #65Loop · 19 nodes−Fold region +[2] → #99 DATA[0] → #65012st_visits  #142MEM#3:int#142 st_visits +MEM#3:int + +[0] → — CTRL +[1] → #16 MEM +[2] → #15 DATA +[3] → #51 DATA +[4] → #141 DATA01234st_sum  #146MEM#2:int#146 st_sum +MEM#2:int + +[0] → — CTRL +[1] → #16 MEM +[2] → #15 DATA +[3] → #4 DATA +[4] → #131 DATA01234Loop  #32Loop · 12 nodes−Fold regionLoop  #65Loop · 15 nodes−Fold region diff --git a/docs/2026_REBASE/slides.js b/docs/2026_REBASE/slides.js index de888f13..9ed9729e 100644 --- a/docs/2026_REBASE/slides.js +++ b/docs/2026_REBASE/slides.js @@ -116,7 +116,7 @@ id:'memory',label:'9–17b · Values, memory, scheduling',section:'Chapters 9–17b',minutes:5,steps:2,demo:'aliases', body:state=>'

Memory is dataflow, too.

'+source(state.demo||'aliases',true)+'

Partition memory into
equivalence classes.

'+memoryPartition(state)+states(state.demo==='memory'?[ '
data[i]Array element memory is another slice.
', - '
t.sum / t.visitsSeparate field classes carry separate dependencies.
', + '
t.sum / t.visitsCarry values around the loop; store the final totals once.
', '
4*arg + 10Runtime result; the graph still contains loops.
' ]:[ '
p.x → Pair.xAll Pair.x fields share one equivalence class.
', @@ -127,9 +127,9 @@ '0:00–0:45: Briefly show Domains and Memory types, then return to Examples. Use the partition picture: Pair.x, Pair.y, and the rest are disjoint equivalence classes whose union is whole memory. The classes group locations across all instances, not one class per object.', '0:45–1:15: Run make -C chapter17b view. Paste Short alias example. Show that p.y changes while p.x does not, and the result becomes zero.', '1:15–3:15: Trace the Loads and Store through their field equivalence classes. Same-class accesses may alias; different classes cannot. MemMerge recombines the slices without emitting an instruction. Explain why writing p.y does not clobber p.x. Read-only access would not make a Load independent of memory.', - '3:15–4:30: Switch back to this slide, select Array + object loops, Copy code, then compile it in the same viewer. Jump Last, fold/unfold the loops, and inspect loop-carried memory and the sum and visits aliases.', + '3:15–4:30: Switch back to this slide, select Array + object loops, Copy code, then compile it in the same viewer. Jump Last: array writes still carry memory around the first loop. The second loop carries sum and visits as scalar Phis; their stores move after the loop and their memory Phis disappear.', '4:30–5:00: GCM uses these dependencies to choose legal placements; it does not guess ordering from source order. Return to slides.' - ],'

The graph viewer captures parsing/optimization/type checking, not GCM execution. The large graph has 54 nodes at its final checkpoint; do not step through all 319 frames.

Research context: Diwan, McKinley, and Moss, Type-Based Alias Analysis, PLDI 1998, sections 3.5–3.6 (p. 113). A runtime upper bound left at most an average 2.5% more heap loads eliminable beyond their analysis on eight Modula-3 benchmarks. This is a load-elimination bound, not a speedup percentage. More static opportunities did not translate into corresponding runtime gains. This supports choosing useful, inexpensive alias distinctions; it does not establish that this exact equivalence-class scheme is optimal for Java. The study is a close match to the recalled oracle experiment, not an identified IBM/Java paper.

') + ],'

The graph viewer captures parsing/optimization/type checking, not GCM execution. The large graph has 52 nodes at its final checkpoint; do not step through all 333 frames.

Research context: Diwan, McKinley, and Moss, Type-Based Alias Analysis, PLDI 1998, sections 3.5–3.6 (p. 113). A runtime upper bound left at most an average 2.5% more heap loads eliminable beyond their analysis on eight Modula-3 benchmarks. This is a load-elimination bound, not a speedup percentage. More static opportunities did not translate into corresponding runtime gains. This supports choosing useful, inexpensive alias distinctions; it does not establish that this exact equivalence-class scheme is optimal for Java. The study is a close match to the recalled oracle experiment, not an identified IBM/Java paper.

') }, { id:'inline',label:'18 · Functions and Calls',section:'Chapter 18',minutes:5,steps:2,demo:'inline', diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index a8be1e24..53fd6a9c 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -109,6 +109,34 @@ Existing spill expectations changed in the String fixture: These records describe completed work, not outstanding implementation tasks. Historical chapter numbers and measurements below refer to their original runs. +### Loop store sinking: Chapters 17b-25 (2026-10-05) + +The Chapter 17b presentation peephole is forwarded through Chapter 25. A loop +memory Phi whose backedge is a sole-use Store becomes a Store of a scalar Phi. +An entry Load preserves zero-trip behavior. The address must be a constant +field offset of an allocation dominating the loop; array elements are excluded. +Wait for parallel bulk-memory splitting before replacing the precise Phi. +Chapter 25 preserves the Store's frozen width and excludes unresolved aliases, +undecided widths, and constructor initialization Stores. + +Existing suites exposed three small supporting fixes: Loads through a TOP +pointer stay TOP in 17b-23; Chapter 25 keeps a MemMerge alive while flattening a +dead memory cycle; the shared printer computes placement for constants even +when they have no cached block. Existing graph assertions now count reachable +definitions and allow scalar field Phis. The synthetic-exit fixture uses a +varying pointer so it still exercises loop-carried memory after store sinking. +No new test methods were added for the forward port. Spill expectations were +updated for the changed graphs, including the infinite-loop, String, and Scan +fixtures; runtime and register-correctness assertions remain enabled. + +Validation: full Make suites pass in 17b (306 including its fuzzer wrapper), +18 (339), 19 (383), 20 (405), 21 (444), 22 (465), 23 (487), and 24 (517), plus +the separate fuzzer wrappers in 18-24. Chapter 25 passes all six suite groups +(403, 39, 9, 23, 1, and 19), including rebuilt sys.o, native execution, and +the existing fuzzer seeds. Shared printer and ISA checks pass. Logs are in +`build/rebase-talk/loop-store-*.log`. The presentation example still has 333 +capture frames and 52 final nodes, with both Totals stores outside the loop. + ### Shared ISA encoders and evaluators: Chapters 21-25 Issue #257's extraction is implemented in [`isa/`](../isa/README.md). `X86` diff --git a/print/src/main/java/com/seaofnodes/print/IRPrinter.java b/print/src/main/java/com/seaofnodes/print/IRPrinter.java index b974ebe1..be5be16d 100644 --- a/print/src/main/java/com/seaofnodes/print/IRPrinter.java +++ b/print/src/main/java/com/seaofnodes/print/IRPrinter.java @@ -253,7 +253,7 @@ public final class IRPrinter> { IdentityHashMap placed) { Integer old=placed.get(n); if( old!=null ) return old; - int early=blocks.get(n); + int early=block(n,nodes,blocks); placed.put(n,early); // Close data cycles without changing compiler state. if( _a.control(n) || _a.phi(n) || _a.projection(n) || _a.global(n) || _a.input0(n)!=null ) return early; -- cgit v1.2.3