diff options
Diffstat (limited to 'chapter13')
| -rw-r--r-- | chapter13/README.md | 8 | ||||
| -rw-r--r-- | chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java | 11 | ||||
| -rw-r--r-- | chapter13/src/test/java/com/seaofnodes/simple/SchedulerTest.java | 21 |
3 files changed, 36 insertions, 4 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/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; |