diff options
28 files changed, 755 insertions, 28 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)); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java index 41a3fcaa..b4cfaaf3 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java @@ -910,7 +910,7 @@ public class Parser { // Arrays include control, as a proxy for a safety range check // Structs don't need this; they only need a NPE check which is // done via the type system. - //if( base.isAry() ) load.setDef(0,ctrl()); + if( base.isAry() ) load.setDef(0,ctrl()); return parsePostfix(load.peephole()); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 8d604b28..ab53aa6a 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter16/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/chapter16/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 63bdcce7..90d401f5 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -9,6 +9,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)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter17a/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 85ad243b..5970783c 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -127,6 +127,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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter17a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter17a/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 452a1051..2c824175 100644 --- a/chapter17a/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter17a/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -9,6 +9,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)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index eaab680c..98d076b8 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -128,6 +128,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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter17b/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter17b/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 452a1051..2c824175 100644 --- a/chapter17b/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter17b/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -9,6 +9,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)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 5190bf08..268bf3d8 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -138,6 +138,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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 5b8e0fea..f95d72c6 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -6,6 +6,59 @@ import static org.junit.Assert.*; 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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + 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); + code.driver(CodeGen.Phase.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)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("7",Eval2.eval(code,1)); + assertEquals("9",Eval2.eval(code,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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + 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)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("9",Eval2.eval(code,1)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java index a06d1291..ec0a81c9 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -143,6 +143,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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter15Test.java index ec6bce5d..21f4bce8 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -6,6 +6,59 @@ import static org.junit.Assert.*; 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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + 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); + code.driver(CodeGen.Phase.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)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("7",Eval2.eval(code,1)); + assertEquals("9",Eval2.eval(code,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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + 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)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("9",Eval2.eval(code,1)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/LoadNode.java index b9905912..9b86c696 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -143,6 +143,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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 7da8fe0f..cbbcefad 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -7,6 +7,64 @@ import static org.junit.Assert.*; 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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? 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); + code.driver(CodeGen.Phase.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.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(split); + org.junit.Assert.assertSame("The surviving read retains the earlier check",checked,split.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("7",Eval2.eval(code,1)); + assertEquals("9",Eval2.eval(code,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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(load); + org.junit.Assert.assertNotNull("Element loads carry their range-check control",load.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("9",Eval2.eval(code,1)); + } + + @Ignore @Test public void testJig() { 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 3084b4f7..c48c4896 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -89,8 +89,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 && - // Array access control must not be moved across the merge. - in(0)==null && + // 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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java index fbbb6c9d..4265aecc 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -10,6 +10,64 @@ import static org.junit.Assert.*; 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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? 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); + code.driver(CodeGen.Phase.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.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(split); + org.junit.Assert.assertSame("The surviving read retains the earlier check",checked,split.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("7",Eval2.eval(code,1)); + assertEquals("9",Eval2.eval(code,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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(load); + org.junit.Assert.assertNotNull("Element loads carry their range-check control",load.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("9",Eval2.eval(code,1)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 3084b4f7..c48c4896 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -89,8 +89,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 && - // Array access control must not be moved across the merge. - in(0)==null && + // 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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 1f47ee10..c67d1eac 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -10,6 +10,64 @@ import static org.junit.Assert.*; 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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? 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); + code.driver(CodeGen.Phase.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.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(split); + org.junit.Assert.assertSame("The surviving read retains the earlier check",checked,split.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("7",Eval2.eval(code,1)); + assertEquals("9",Eval2.eval(code,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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(load); + org.junit.Assert.assertNotNull("Element loads carry their range-check control",load.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("9",Eval2.eval(code,1)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 06226df0..ad478d55 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -103,8 +103,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 && - // Array access control must not be moved across the merge. - in(0)==null && + // 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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 5331809f..a74a1113 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -10,6 +10,64 @@ import static org.junit.Assert.*; 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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? 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); + code.driver(CodeGen.Phase.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.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(split); + org.junit.Assert.assertSame("The surviving read retains the earlier check",checked,split.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("7",Eval2.eval(code,1)); + assertEquals("9",Eval2.eval(code,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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(load); + org.junit.Assert.assertNotNull("Element loads carry their range-check control",load.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("9",Eval2.eval(code,1)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java index b3204cff..e057ef1c 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -114,8 +114,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 && - // Array access control must not be moved across the merge. - in(0)==null && + // 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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java index d452fbfd..9aaafc28 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -10,6 +10,64 @@ import static org.junit.Assert.*; 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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? 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); + code.driver(CodeGen.Phase.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.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(split); + org.junit.Assert.assertSame("The surviving read retains the earlier check",checked,split.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("7",Eval2.eval(code,1)); + assertEquals("9",Eval2.eval(code,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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + var main = code.link(code._main); + var load = stop.walk(n -> n instanceof com.seaofnodes.simple.node.LoadNode ld && ld._name.equals("[]") && + ld.in(0)!=null && ld.cfg0().fun()==main ? ld : null); + org.junit.Assert.assertNotNull(load); + org.junit.Assert.assertNotNull("Element loads carry their range-check control",load.in(0)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("9",Eval2.eval(code,1)); + } + + @Ignore @Test public void testJig() { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 0a997083..c58bba39 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -169,8 +169,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 && - // Array access control must not be moved across the merge. - in(0)==null && + // 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()) && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 25f00474..c2071cb6 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -10,6 +10,59 @@ import static org.junit.Assert.*; 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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + 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); + code.driver(CodeGen.Phase.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)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("7",Eval2.eval(code,1)); + assertEquals("9",Eval2.eval(code,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; + """; + var code = new CodeGen(src).parse(); + var stop = code._stop; + 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)); + code.driver(CodeGen.Phase.LocalSched); + assertEquals("42",Eval2.eval(code,0)); + assertEquals("9",Eval2.eval(code,1)); + } + + @Ignore @Test public void testJig() { diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 1f15afaa..d10dc761 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -4,6 +4,37 @@ This file tracks pending backports and deferred work. Completed work and old validation results belong in Git history. Reusable implementation constraints live in the [AI notes](../skills/chapter25-codex-notes.md). +## Investigate next + +These are candidates, not confirmed missing correctness fixes. Establish an +earlier-chapter failure before changing compiler behavior. + +### Conditional Store control + +Compare conditional field writes under each destination's memory-Phi and alias +model. Chapter 24 attaches control to array stores but lets ordinary field +stores rely on memory dependencies. Chapter 25's explicit Store control input +is not by itself evidence that the earlier representation is wrong. + +Keep this investigation separate from GCM's memory-Phi anti-dependency walk. +Use the existing read-before-conditional-store regression as a guard, and find +a distinct failing program before adding more control constraints. + +### SCCP function revival: Chapter 24 + +`Opto.linkCG` uses `code.link(fidx)`, which clears a linker entry when its +function is structurally dead. Chapter 25 uses the non-cleaning `_link(fidx)` +while discovering calls, so temporarily disconnected functions can be revived. +Chapter 24 already has `_link`; the question is whether its own unlinking and +SCCP sequence can expose the same failure. + +Trace a function from removal of its unknown-caller edge through discovery of +a real call. Preserve the distinction between unreachable control and a +structurally deleted node. No earlier-chapter failure is established yet. +Dependency propagation already exists in Chapter 24's SCCP; only port a +specific missing dependency with a reproducer. Keep Chapter 25's escape and +external-caller machinery out of this investigation. + ## Deferred until the Chapter 25 split ### Deterministic inlining @@ -36,20 +67,16 @@ Preserve the current contracts until the parser, conversions, loop bounds, and diagnostics can move together. Do not weaken narrowing assertions or expected errors to make an isolated backport pass. -### Other candidates requiring a concrete earlier-chapter failure +### Representation changes -These are investigation candidates, not promised wholesale ports: - -| Candidate | Boundary to establish | -|---|---| -| Conditional Store and array Load control | Reproduce under the destination chapter's alias model. | -| SCCP dependencies, function revival, reachability | Separate corrections applicable to Chapter 24 from Chapter 25's guards, escape analysis, and external-caller machinery. | -| Incomplete types, numeric modes, guards, symbolic fields, private constructor memory | Choose chapter boundaries and move the required invariants together. | +Incomplete types, numeric modes, guards, symbolic fields, and private +constructor memory need explicit teaching boundaries and coordinated +invariants. They are not independent fixes to copy into earlier snapshots. Serialization, global identity remapping, and module escape summaries stay with separate compilation. Escape analysis stays in Chapter 25 pending the split. -## Chapter 25 follow-ups +## Work that stays in Chapter 25 Class-cycle checking and CLInit runtime lowering stay in Chapter 25. The [chapter README](../chapter25/README.md#lazy-class-initialization) explains the @@ -58,9 +85,6 @@ implementation; future work lives in the Native code cannot receive classes; a native-startup/class-handoff policy is not planned. Current data pointers remain eight bytes. -Allocator tuning and additional emulator measurement coverage are closed. -Current allocation measurements live in [regalloc-spills.md](regalloc-spills.md). - ## Backport validation Introduce an independent fix in the earliest applicable chapter and propagate diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 1801ffed..f66b2c65 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -56,6 +56,10 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m ## Mutability and chapter boundaries +- The class-init-cycle project is closed. Cycle checking, diagnostics, + serialization/import handling, and runtime lowering are complete for the + agreed scope. Argument arrays and initialization optimizations remain + separate ROADMAP work; they do not keep this project open. - Native boundary decision (2026-10-18): no classes for native code; do not design a native-startup policy. Ordinary supported FFI calls are separate. Chapter 25's README owns the tutorial explanation of class initialization; @@ -88,8 +92,8 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m The selected entry gets the external arg; other clinits get zero for now. The planned array ABI uses non-null entry args and null elsewhere; not yet implemented. Eval2 shares singleton class objects and retains imported bodies. - Full Chapter 25 Make validation: 509 tests, including native cold/hot calls, - parent order, ARM/RISC-V encoding and nonreturning object reload. + Execution coverage includes native cold/hot calls, parent order, + ARM/RISC-V encoding, and nonreturning object reload. - Chapter 25 phase structure: Opto only runs SCCP, numeric-mode resolution and worklist seeding. IterPostOpto does peepholes/inlining; FinalizeIR does field layout/offset cleanup and function/CU finalization. @@ -123,8 +127,8 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m Runtime lowering is implemented above; argument arrays remain deferred. Public function fields on instances of public classes must retain Start, just like class-object fields. publicFIDX now checks both; this fixes sys.scan.match losing Start - while building sys.o and subsequently widening after import. All Chapter 25 - Make suites pass (505 tests). Do not weaken assertions or reset imported types + while building sys.o and subsequently widening after import. + Do not weaken assertions or reset imported types to conceal incorrect public classification. Future optimization: move final, always-constant instance fields to the class or fold them to constants and omit their instance storage. Access semantics @@ -191,6 +195,18 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m filter by alias and ignore MemMerge as a clobber; keep the evaluator's same alias filtering too. MemMerge still needs ordinary data-dependency placement. +- From Chapter 15, an array element Load's control stands for its range check. + Keep that edge during parsing and rewriting. A Load can push through a + memory Phi when its control is null or dominates the Region's idom; retain + that control on both copies. The Region itself or a later check cannot + supply control to predecessor loads. Dropping it permits an out-of-bounds + speculative read. The parser currently attaches the current control as a + placeholder, which can be the Region itself even in a valid graph. + `Chapter15Test.testArrayLoadControl` checks a guarded read after a memory + merge; `testArrayLoadDominatingControl` checks successful splitting under + an earlier common check. Length loads have no index; + Chapters 19+ already leave them unpinned, independently of element control. + - Chapter 15 New consumes `{ctrl, $mem, size}` and produces `{ptr, $mem}`: no control result, pointer slot 0, memory slot 1. Its TypeStruct/TypeMemPtr defines the covered field aliases. Use a partial input MemMerge (null default), |