diff options
Diffstat (limited to 'chapter15')
7 files changed, 122 insertions, 7 deletions
diff --git a/chapter15/README.md b/chapter15/README.md index 1ce5badf..e384e7ce 100644 --- a/chapter15/README.md +++ b/chapter15/README.md @@ -127,6 +127,12 @@ from a distinct New can bypass the allocation to its memory input. Mere node inequality is insufficient: a Phi or cast can still denote the allocated object. Array length is set by a subsequent Store; the array body is zeroed by New. Array accesses retain their existing control input as the bounds-check proxy. +When pushing a Load through a memory Phi, its control must dominate the +Region's immediate dominator, so both predecessor loads can retain that check. +A check at the Region or below it cannot be copied onto the predecessors. +For example, a Load guarded by `if (a# > 1)` must not move above that branch +just because its memory comes from an earlier Phi. Memory ordering alone does +not prove that `a[1]` is in bounds. Both schedulers follow an alias through MemMerge to find New's memory effect. MemMerge itself does not overwrite memory, but must not hide the ordering of diff --git a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index d17ec3b6..4c9fc779 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -246,10 +246,11 @@ public abstract class GlobalCodeMotion { lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; case PhiNode phi: - // Repeat anti-dep for matching Phi inputs. - // No anti-dep edges but may raise the LCA. + // Inputs carrying different memory might overwrite this alias. + // Raise the LCA for those paths; unchanged memory does not + // clobber the load. No scheduling edge to the Phi. for( int i=1; i<phi.nIns(); i++ ) - if( phi.in(i)==load.mem() ) + if( phi.in(i)!=load.mem() ) lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); break; default: throw Utils.TODO(); @@ -262,7 +263,9 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) { // Preserve the full store range for the earlier evaluator scheduler. // It places nodes independently of GCM and may hoist this store. - for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { + // Another Phi input need not be dominated by this memory definition. + // Include its depth, and retain the sentinel for an entry's null idom. + for( ; stblk != defblk.idom() && stblk.idepth() >= defblk.idepth(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( anti[stblk._nid]==load._nid ) { lca = stblk.domLCA(lca,null); // Raise Loads LCA diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java index b0517a4c..86d79845 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -122,6 +122,9 @@ public class LoadNode extends MemOpNode { // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && + // Retain control on both copies only if it dominates both paths. + // The Region itself, or a later range check, cannot move to its inputs. + (in(0)==null || cfg0().domLCA(memphi.region().idom(this),this)==cfg0()) && off() instanceof ConstantNode ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 485491c0..11c865a8 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -91,4 +91,12 @@ public class StoreNode extends MemOpNode { Type t = val()._type; return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } + + // Do not GVN Stores. Two equal Stores on two of three paths are the easy + // failure: sharing them makes GCM place the Store on all three paths. + // Sharing is safe only if every exit path goes through an original Store, + // or GCM splits the shared Store to keep it on those paths. Stores must + // sink, not run on extra paths. GVN does not check this; GCM does not split. + // Identity also disables generic Phi factoring of Stores. + @Override boolean eq(Node n) { return this == n; } } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java index a5e3a9e0..3f34c448 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -11,6 +11,26 @@ import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter10Test { + @Test public void testConditionalStoreSharing() { + // Sharing the writes on two of three paths must not write on the third. + // Return the object so Load forwarding cannot hide the physical Store. + String src = """ + struct S { int x; }; + S a = new S; + a.x = 10; + if (arg == 1) a.x = 9; + else if (arg == 2) a.x = 9; + return a; + """; + var stop = new Parser(src).parse().iterate(); + for( int arg : new int[]{0,1,2,3} ) { + long expected = (arg==1 || arg==2) ? 9 : 10; + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + assertEquals(expected,obj.fields()[0]); + } + } + @Test public void testDeadReferenceReturn() { for( String body : new String[] { "return new S; return 0;", @@ -541,14 +561,15 @@ return 0; assertEquals(3L,Evaluator.evaluate(stop,3)); } - @Test public void testDropStores() { + @Test public void testKeepBranchStores() { StopNode stop = new Parser(""" struct S { int x; } S s = new S; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // Keep each Store on its own branch. + assertEquals(2,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/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java index d0e02eeb..5000a994 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -12,6 +12,57 @@ import static org.junit.Assert.fail; public class Chapter15Test { + @Test public void testArrayLoadDominatingControl() { + String src = """ + int[] a=new int[arg+1]; a[arg]=7; + if(a#>1) { + if(arg==2) a[1]=9; + return a[1]; + } + return 42; + """; + StopNode stop = new Parser(src).parse(); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") ? ld : null); + org.junit.Assert.assertNotNull(load); + // The parser uses current control as a placeholder for a range check. + // Model an explicit check already performed before the inner diamond: + // both predecessors are below the a#>1 true projection. + var region = (com.seaofnodes.simple.node.RegionNode)load.in(0); + var checked = region.idom().cfg(0); + org.junit.Assert.assertTrue(checked instanceof com.seaofnodes.simple.node.CProjNode); + load.setDef(0,checked); + IterPeeps.iterate(stop).typeCheck(); + org.junit.Assert.assertTrue("Common dominating control permits Phi splitting",load.isDead()); + var split = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") ? ld : null); + org.junit.Assert.assertNotNull(split); + org.junit.Assert.assertSame("The surviving read retains the earlier check",checked,split.in(0)); + stop.iterate(); + assertEquals(42L,Evaluator.evaluate(stop,0)); + assertEquals(7L,Evaluator.evaluate(stop,1)); + assertEquals(9L,Evaluator.evaluate(stop,2)); + } + + + @Test public void testArrayLoadControl() { + // With arg==0, a has length 1 and a[1] must not execute. The memory + // merge must not pull the read above its array-length guard. + String src = """ + int n=1; if(arg) n=2; + int[] a=new int[n]; a[arg]=7; + if(arg) a[1]=9; + if(a#>1) return a[1]; + return 42; + """; + StopNode stop = new Parser(src).parse(); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") ? ld : null); + org.junit.Assert.assertNotNull(load); + org.junit.Assert.assertNotNull("Element loads carry their range-check control",load.in(0)); + stop.iterate(); + assertEquals(42L,Evaluator.evaluate(stop,0)); + assertEquals(9L,Evaluator.evaluate(stop,1)); + } + + @Test public void testPartialAllocationMemory() { StopNode stop = new Parser(""" struct Other { int a; int b; int c; } @@ -99,7 +150,9 @@ if (arg) { return b[0] + b[1]; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region72,1,0);", stop.toString()); + // Controlled element loads stay below the merge until their range + // checks can be proved redundant. + assertEquals("return (.[]+.[]);", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 0)); assertEquals(1L, Evaluator.evaluate(stop, 1)); } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java index ad595822..55aa5d2b 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -10,6 +10,27 @@ import static org.junit.Assert.assertEquals; public class SchedulerTest { + @Test public void testMemoryPhiAcrossSiblingBranch() { + // The inner memory Phi defines the load's memory. The outer Phi's + // other input comes from a branch not dominated by that definition. + String src = """ + struct S { int x; }; S a=new S; S b=new S; + a.x=10; b.x=20; S p=a; if(arg>3) p=b; + int result=0; + if(arg>0) { + if(arg>2) p.x=30; else p.x=40; + result=a.x; + } + return result; + """; + StopNode stop = new Parser(src).parse().iterate(); + var eval = new Evaluator(stop); + long[] expected = {0,40,40,30,10,10}; + for( int arg=0; arg<expected.length; arg++ ) + assertEquals(expected[arg],eval.evaluate(arg,100)); + } + + private static void assertObj(Object obj, String name, Object... fields) { assertEquals(Evaluator.Obj.class, obj.getClass()); var o = (Evaluator.Obj)obj; |