diff options
Diffstat (limited to 'chapter12/src/test/java')
12 files changed, 253 insertions, 57 deletions
diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java index a3109ff7..14d31245 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -84,7 +84,10 @@ public class Chapter04Test { StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof CProjNode); - assertTrue(ret.in(1) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + assertEquals(1, ((ProjNode)ret.in(1))._idx); + assertTrue(ret.in(2) instanceof ProjNode); + assertEquals(2, ((ProjNode)ret.in(2))._idx); } @Test diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 8d15493f..91efc3d6 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -22,7 +22,7 @@ else { return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region20,(arg+2),(arg-3));", ret.toString()); + assertEquals("return Phi(Region21,(arg+2),(arg-3));", ret.toString()); } @Test @@ -37,7 +37,7 @@ if (arg == 1) { } return c;""", TypeInteger.BOT); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region18,4,3);", ret.toString()); + assertEquals("return Phi(Region19,4,3);", ret.toString()); } @Test @@ -65,7 +65,7 @@ else b=a+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((arg*2)+Phi(Region23,2,3));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region24,2,3));", ret.toString()); } @Test @@ -80,7 +80,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region34,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + assertEquals("return ((Phi(Region35,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @Test @@ -100,7 +100,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region38,Phi(Region24,2,3),Phi(Region36,4,5));", stop.toString()); + assertEquals("return Phi(Region39,Phi(Region25,2,3),Phi(Region37,4,5));", stop.toString()); } @Test @@ -116,7 +116,7 @@ if( arg==0 ) return arg+a+b; """, TypeInteger.BOT); StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region15,1,0))+Phi(Region30,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region31,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region18,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region19,3,2));", ret.toString()); } @Test diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 7b11bc35..df0f2848 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -30,7 +30,7 @@ if (arg) return (arg < a) < 3; """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg<Phi(Region14,2,1))<3);", stop.toString()); + assertEquals("return ((arg<Phi(Region15,2,1))<3);", stop.toString()); } @Test @@ -65,7 +65,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region39,42,5);", stop.toString()); + assertEquals("return Phi(Region40,42,5);", stop.toString()); } @Test @@ -84,7 +84,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region32,2,5);", stop.toString()); + assertEquals("return Phi(Region33,2,5);", stop.toString()); } @Test @@ -144,7 +144,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region43,3,Phi(Region41,4,5));", stop.toString()); + assertEquals("return Phi(Region44,3,Phi(Region42,4,5));", stop.toString()); } @Test @@ -200,7 +200,7 @@ if( arg ) { return a+b; """); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region26,4,1);", ret.toString()); + assertEquals("return Phi(Region27,4,1);", ret.toString()); } @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region38,Phi(Region25,2,3),0)+Phi(Region,3,1));", ret.toString()); + assertEquals("return (Phi(Region39,Phi(Region26,2,3),0)+Phi(Region,3,1));", ret.toString()); } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 177b54d1..222982e7 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -18,7 +18,7 @@ public class Chapter07Test { return arg; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -35,7 +35,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region26,1,Phi(Loop15,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region27,1,Phi(Loop16,1,(Phi_a+1)));", stop.toString()); } @Test @@ -55,7 +55,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,0,Phi(Loop22,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + assertEquals("return Phi(Loop11,0,Phi(Loop23,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -71,7 +71,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,2,Phi(Region29,Phi_b,4));", stop.toString()); + assertEquals("return Phi(Loop11,2,Phi(Region30,Phi_b,4));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -90,7 +90,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,2,(Phi(Region29,Phi_b,4)+1));", stop.toString()); + assertEquals("return Phi(Loop11,2,(Phi(Region30,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -107,7 +107,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -123,7 +123,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -136,7 +136,7 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop9,1,2);", stop.toString()); + assertEquals("return Phi(Loop10,1,2);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -149,7 +149,7 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,1,2);", stop.toString()); + assertEquals("return Phi(Loop10,1,2);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -165,7 +165,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -181,7 +181,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -198,7 +198,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -215,7 +215,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 6aa74125..8c644977 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -23,7 +23,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region36,Phi(Region26,Phi(Loop8,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertEquals("return Phi(Region37,Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5L, Evaluator.evaluate(stop, 1)); Assert.assertEquals(10L, Evaluator.evaluate(stop, 6)); @@ -46,7 +46,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,1,Phi(Region41,Phi_a,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Loop10,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -65,7 +65,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region34,Phi(Loop8,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region35,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -81,7 +81,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region26,Phi(Loop8,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -100,7 +100,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop8,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -117,7 +117,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop8,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -185,7 +185,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region29,Phi(Loop9,1,(Phi_a+1)),Add);", stop.toString()); + assertEquals("return Phi(Region30,Phi(Loop10,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -201,7 +201,7 @@ while(1) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop9,1,Add)+1);", stop.toString()); + assertEquals("return (Phi(Loop10,1,Add)+1);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 ); } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 64bbf245..49ee75a2 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -69,7 +69,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+2));", stop.toString()); + assertEquals("return Phi(Loop10,arg,(Phi_arg+2));", stop.toString()); Assert.assertEquals(11L, Evaluator.evaluate(stop, 1)); } @@ -86,7 +86,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+4));", stop.toString()); + assertEquals("return Phi(Loop11,arg,(Phi_arg+4));", stop.toString()); Assert.assertEquals(13L, Evaluator.evaluate(stop, 1)); } @@ -115,7 +115,7 @@ while (arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop17,arg,(Phi_arg+1));", stop.toString()); } @Test @@ -185,7 +185,7 @@ while(arg) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,0,(-(Phi_a+3)));", stop.toString()); + assertEquals("return Phi(Loop12,0,(-(Phi_a+3)));", stop.toString()); } @Test @@ -283,7 +283,7 @@ return v1+v0; public void testFuzz8() { Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop8,arg,(Phi_arg-1));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg-1));", stop.toString()); } @Test diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 9ac1f1e6..38aceb84 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -3,6 +3,10 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.LoadNode; +import com.seaofnodes.simple.node.StoreNode; +import com.seaofnodes.simple.evaluator.Evaluator; +import java.util.BitSet; import org.junit.Test; import java.util.Arrays; @@ -165,7 +169,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString()); } @Test @@ -217,7 +221,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region16,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region17,null,new Bar);", stop.toString()); } @Test @@ -233,7 +237,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region33,4,3);", stop.toString()); + assertEquals("return Phi(Region35,4,3);", stop.toString()); } @Test @@ -287,7 +291,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -308,7 +312,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); } @Test @@ -325,7 +329,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); } @@ -342,7 +346,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop12,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); } @Test @@ -460,4 +464,121 @@ return 0; assertEquals("return 0;", stop.toString()); } + @Test public void testReadBeforeStores() { + var stop = new Parser(""" + struct S { int x; int y; } + S a = new S; S b = new S; + a.x = 11; b.x = 22; + S p = a; if (arg) p = b; + int before = p.x; + a.y = 55; b.y = 66; + a.x = 33; b.x = 44; + return before*100 + p.x; + """).parse().iterate(); + assertEquals(1133L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0)); + assertEquals(2244L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,1)); + } + + static final String NESTED_MEMORY = """ + struct S { int x; int y; int z; } + S s = new S; + s.x = 5; s.y = 7; s.z = 11; + while (arg > 0) { + s.x = s.x + 1; + int j = 3; + while (j > 0) { + j = j - 1; + if (j == 1) continue; + s.y = s.y + arg; + if (arg == 2) break; + s.z = s.z + 1; + } + arg = arg - 1; + } + return s; + """; + + @Test public void testMemoryAcrossNestedLoops() { + var stop = new Parser(NESTED_MEMORY).parse().iterate(); + for (int arg=0; arg<7; arg++) { + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(new Object[] { + 5L+arg, 7L+arg*(arg+1)-(arg>=2 ? 2 : 0), 11L+2*arg-(arg>=2 ? 2 : 0) + }, obj.fields()); + } + } + + @Test public void testMemoryAtEarlyReturns() { + var stop = new Parser(""" + struct S { int x; int y; int z; } + S s = new S; + s.x = 3; s.y = 5; s.z = 7; + if (arg) { s.x = 11; s.z = 13; return s; } + s.y = 17; + return s; + """).parse().iterate(); + for (int arg=0; arg<2; arg++) { + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(arg==0 ? new Object[]{3L,17L,7L} : new Object[]{11L,5L,13L}, obj.fields()); + } + } + + @Test public void testKeepLoadsAtMerge() { + StopNode stop = new Parser(""" + struct S { int x; } + S a = new S; S b = new S; + a.x = arg; b.x = arg+1; + S p = a; S q = b; + if (arg<0) { p=b; q=a; } + int v; + if (arg>1) v=p.x; else v=q.x; + return v; + """).parse().iterate(); + // The one-step safety check stops at the memory aggregate. + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals(-1L,Evaluator.evaluate(stop,-1)); + assertEquals(1L,Evaluator.evaluate(stop,0)); + assertEquals(3L,Evaluator.evaluate(stop,3)); + } + + @Test public void testDropStores() { + 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. + 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]); + } + + @Test public void testKeepReadsBeforeWrites() { + StopNode stop = new Parser(""" + struct S { int x; int y; } + S a = new S; S b = new S; + a.x=arg; b.x=arg+1; + S p=a; S q=b; + if (arg<0) { p=b; q=a; } + int v; + if (arg>1) { v=p.x; p.x=41; p.y=5; } + else { v=q.x; q.x=42; } + return v; + """).parse().iterate(); + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals(-1L,Evaluator.evaluate(stop,-1)); + assertEquals(1L,Evaluator.evaluate(stop,0)); + assertEquals(3L,Evaluator.evaluate(stop,3)); + } + + private static int countMemoryNodes(Node n, Class<?> kind, BitSet seen) { + if (n==null || seen.get(n._nid)) return 0; + seen.set(n._nid); + int cnt=kind.isInstance(n) ? 1 : 0; + for (Node def : n._inputs) cnt+=countMemoryNodes(def,kind,seen); + return cnt; + } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..6f094cfb --- /dev/null +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java @@ -0,0 +1,64 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.evaluator.Evaluator; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter10bTest { + @Test public void testIndependentField() { + var stop = new Parser(""" + struct S { int x; int y; } + S s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().iterate(); + assertEquals("return 42;",stop.toString()); + assertEquals(42L,Evaluator.evaluate(stop,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var stop = new Parser(""" + struct S { int x; int y; int z; } + S a = new S; S b = new S; + S p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().iterate(); + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a<m.nIns() && m.in(a)!=null); + assertFalse(n instanceof PhiNode && n.isMem() && + !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode)); + return null; + }); + assertTrue(phis[0]>=3); + assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + + @Test public void testLateSliceWorklist() throws ReflectiveOperationException { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var parser = new Parser(Chapter10Test.NESTED_MEMORY); + var field = IterPeeps.class.getDeclaredField("WORK"); + field.setAccessible(true); + Object work = field.get(null); + field = work.getClass().getDeclaredField("_R"); + field.setAccessible(true); + ((java.util.Random)field.get(work)).setSeed(seed); + var stop = parser.parse().iterate(); + assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + } +} diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 5a60c8b4..0e492591 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -325,7 +325,7 @@ while( prime <= arg ) { return primeCount; """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return Phi(Loop19,1,Phi(Region81,Phi_primeCount,Phi(Region76,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); + assertEquals("Stop[ return 0; return Phi(Loop20,1,Phi(Region82,Phi_primeCount,Phi(Region77,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2 assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3 @@ -367,7 +367,7 @@ if (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region31,.f,0);", stop.toString()); + assertEquals("return Phi(Region34,.f,0);", stop.toString()); } @Test @@ -473,7 +473,7 @@ while(arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,arg,Phi(Region35,.f,0));", stop.toString()); + assertEquals("return Phi(Loop15,arg,Phi(Region39,.f,0));", stop.toString()); } @Test @@ -524,7 +524,7 @@ else if (arg == 1) s.f = 1; return s.f; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,1,Phi(Region33,1,0));", stop.toString()); + assertEquals("return Phi(Region41,1,Phi(Region36,1,0));", stop.toString()); assertEquals(1L, Evaluator.evaluate(stop, 0)); assertEquals(1L, Evaluator.evaluate(stop, 1)); assertEquals(0L, Evaluator.evaluate(stop, 2)); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 9da4a4b8..e577c8c3 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -65,7 +65,7 @@ while( 1 ) { return guess; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); + assertEquals("return Phi(Loop10,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); assertEquals(3.0, Evaluator.evaluate(stop, 9)); assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2)); } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 3512d2e9..40a2f78d 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -154,6 +154,7 @@ public class Evaluator { case ToFloatNode cast -> (double)vall(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); + case MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; @@ -167,8 +168,8 @@ public class Evaluator { public Object evaluate(long parameter, int loops) { if (start == null) return Status.TIMEOUT; var s = new Object[start.compute()._types.length]; - s[1] = parameter; - for(int i=2;i<s.length;i++) s[i] = MEMORY; + s[1] = MEMORY; + s[2] = parameter; values[start._nid] = s; int i=0; Scheduler.Block block = this.startBlock; @@ -179,7 +180,7 @@ public class Evaluator { case null: return Status.FALLTHROUGH; case ReturnNode ret: - return val(ret.in(1)); + return val(ret.expr()); case IfNode ifn: block = block.next()[isTrue(val(ifn.in(1))) ? 0 : 1]; if (block == null) return Status.FALLTHROUGH; diff --git a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 8b86d67a..d16f4300 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -250,6 +250,12 @@ public class Scheduler { // so do that now. var mem = l.in(1); for(var out : mem._outputs) { + // Aggregates describe partitions; they do not overwrite + // memory. Only users of this alias constrain the load. + if (out instanceof MemMergeNode || out instanceof ReturnNode) continue; + if (out instanceof StoreNode s && s._alias != l._alias) continue; + if (out instanceof MemPhiNode p && p._alias != l._alias) continue; + if (out instanceof BulkMemPhiNode p && p.isSplit(l._alias)) continue; if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { @@ -271,7 +277,7 @@ public class Scheduler { // Store nodes have anti-deps to load nodes. // So decrease the uses of these loads when the store is placed. for (var out: s.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(this::decUsers); + if (out instanceof LoadNode l && l._alias==s._alias) od(out).ifPresent(this::decUsers); } } } @@ -469,7 +475,8 @@ public class Scheduler { var data = mem.pop(); node = data.node; for(var out:node.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(d->d.users++); + if (out instanceof LoadNode l && l._alias==((StoreNode)node)._alias) + od(out).ifPresent(d->d.users++); } } } |