diff options
Diffstat (limited to 'src/test/java/com/seaofnodes')
5 files changed, 104 insertions, 19 deletions
diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 26bbb62a..b59eee93 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -165,7 +165,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString()); } @Test @@ -217,7 +217,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region15,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region16,null,new Bar);", stop.toString()); } @Test @@ -233,7 +233,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region32,4,3);", stop.toString()); + assertEquals("return Phi(Region34,4,3);", stop.toString()); } @Test @@ -286,9 +286,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - // The preceding len store keeps the initial x load on the bulk chain. - assertEquals("return Phi(Loop13,0,(Phi(Loop,.x,(Phi_x+1))+Phi_sum));", stop.toString()); - assertEquals(10L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,5)); + assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -308,7 +306,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); } @Test @@ -325,7 +323,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 +340,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); } @Test @@ -476,8 +474,7 @@ return 0; assertEquals(2244L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,1)); } - @Test public void testMemoryAcrossNestedLoops() { - var stop = new Parser(""" + 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; @@ -494,7 +491,10 @@ return 0; arg = arg - 1; } return s; - """).parse().iterate(); + """; + + @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); diff --git a/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..6f094cfb --- /dev/null +++ b/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/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index c9eb2747..f9c580cc 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -22,10 +22,23 @@ public class TypeTest { Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1, s1.dual().glb()); - assertEquals(TypeStruct.BOT, s1.meet(s2)); - assertEquals(TypeMem.BOT, TypeMem.TOP.meet(TypeMem.BOT)); - assertEquals(TypeMem.TOP, TypeMem.BOT.dual()); - assertEquals(TypeMem.BOT, TypeMem.TOP.dual()); + TypeMem m1 = TypeMem.make(1); + TypeMem m2 = TypeMem.make(2); + TypeMem m3 = TypeMem.make(3); + TypeMem m4 = TypeMem.make(4); + + Assert.assertNotEquals(m1, m2); + Assert.assertNotEquals(m2, m3); + Assert.assertNotEquals(m3, m4); + + Assert.assertEquals(TypeStruct.BOT, s1.meet(s2)); + Assert.assertEquals(TypeMem .BOT, m1.meet(m2)); + Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); + Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); + + Assert.assertEquals(TypeMem.BOT, m1.glb()); + Assert.assertEquals(m1, m1.dual()); + Assert.assertEquals(TypeMem.TOP, m1.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index eaeb061b..e49e0303 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -138,6 +138,7 @@ public class Evaluator { case CastNode cast -> val(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); + case MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx]; default -> throw new AssertionError("Unexpected node " + node); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 674d12f5..48ac0562 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -215,7 +215,7 @@ public class Scheduler { private void refinePlacement(NodeData data, BasicBlock block) { assert !isPinnedNode(data); data.block = data.block == null ? block : dom(data.block, block); - assert isValid(data); + assert isValid(data) : data.node.uniqueName()+" at "+data.block.entry.uniqueName(); } /** @@ -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); } } } @@ -467,7 +473,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++); } } } |