diff options
Diffstat (limited to 'chapter15')
| -rw-r--r-- | chapter15/README.md | 6 | ||||
| -rw-r--r-- | chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java | 3 | ||||
| -rw-r--r-- | chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java | 55 |
3 files changed, 63 insertions, 1 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/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/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)); } |