diff options
Diffstat (limited to 'chapter13')
5 files changed, 66 insertions, 6 deletions
diff --git a/chapter13/README.md b/chapter13/README.md index 7df00642..7794c2eb 100644 --- a/chapter13/README.md +++ b/chapter13/README.md @@ -352,6 +352,14 @@ stores, we do the same - until/unless we find stores with the SAME block as the Load's LCA. Then we add the anti-dependency edge to force ordering within the same block. +For a memory Phi, constrain the paths whose inputs differ from the Load's +memory; paths carrying that memory unchanged do not overwrite it. A different +input can come from a sibling branch, so its dominator chain need not reach +the memory definition's block. Stop the walk when it rises above that block's +depth, or reaches its immediate dominator. Include the boundary depth so +same-block ordering is preserved. The immediate-dominator sentinel also handles +a root with no dominator. + See [`antiUse()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L224) for the alias filter, and [`find_anti_dep()`](src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L233) diff --git a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 78a0dcde..b431f82c 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -244,10 +244,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(); @@ -260,7 +261,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/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java index e9eaaf2e..e09c8fd3 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -85,4 +85,12 @@ public class StoreNode extends MemOpNode { Type ptr = val()._type; return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" 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/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6649c0b0..7fa9978d 100644 --- a/chapter13/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter13/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;", @@ -540,14 +560,14 @@ 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(); - // These chapters still bind struct Stores to branch control. + // Two branch Stores plus the initial zero Store. assertEquals(3,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/chapter13/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter13/src/test/java/com/seaofnodes/simple/SchedulerTest.java index ad595822..55aa5d2b 100644 --- a/chapter13/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter13/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; |