diff options
Diffstat (limited to 'chapter17b')
5 files changed, 97 insertions, 2 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<m.nIns() && m.in(a)!=null); @@ -42,7 +43,7 @@ public class Chapter11Test { !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode)); return null; }); - assertTrue(phis[0]>=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<data#; i++ ) data[i]=arg+i; + for( int i=0; i<(arg<data# ? arg : data#); i++ ) { + t.sum = t.sum + data[i]; + t.visits++; + } + return t; + """).parse().iterate(); + stop.typeCheck(); + int[] stores = {0}; + stop.walk(n -> { + 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;"); |