diff options
Diffstat (limited to 'chapter21/src')
7 files changed, 65 insertions, 10 deletions
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java index f1a9cb07..3084b4f7 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter21/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/chapter21/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index e5a29329..1349cadb 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/chapter21/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/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java index d56f1699..a5b09663 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -94,6 +94,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/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<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/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<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/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index f9a6b4fc..a51ae3bc 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -297,8 +297,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/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java index f0a68402..1ce2cd34 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java +++ b/chapter21/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 -> { |