diff options
Diffstat (limited to 'chapter17/src/test/java/com/seaofnodes')
9 files changed, 234 insertions, 34 deletions
diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java index dfd3569f..36727a8f 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter17/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/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java index e3d8b177..86a9937f 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,7 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.node.*; +import java.util.BitSet; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -452,4 +453,120 @@ 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(); + assertEquals(1,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/chapter17/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..fd6fdf36 --- /dev/null +++ b/chapter17/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/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 862b75e3..a1fdeb3a 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -183,7 +183,7 @@ return new S1.s=new S2; struct I {int i;}; struct P { I? pi; }; P !p1 = new P; -P p2 = new P; +P !p2 = new P; p2.pi = new I; p2.pi.i = 2; if (arg) p1 = new P; diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 23c82358..6846e7af 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -175,7 +175,7 @@ while(v1) break; return v1; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", stop.toString()); + assertEquals("return Phi(Loop,(((1<<arg)&1)&Shl),0);", stop.toString()); assertEquals(1L, Evaluator.evaluate(stop, 0)); } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 4e2682dc..e66a009b 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -130,7 +130,7 @@ else { return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,1.2,Phi(Region,2.3,3.14));", stop.toString()); + assertEquals("return Phi(Region,1.2,Phi(Region,2.3,.y));", stop.toString()); assertEquals(3.14, Evaluator.evaluate(stop, 0)); assertEquals(1.2 , Evaluator.evaluate(stop, 1)); } @@ -156,7 +156,7 @@ if( iss[arg] ) return rez; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'y'",e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null accessing '[]'",e.getMessage()); } } @Test diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 36510737..d9edf0e6 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -254,4 +254,27 @@ return new Square; assertEquals("Obj<Square>{side=3.0,diag=1.7320508075688772}", Evaluator.evaluate(stop, 3).toString()); assertEquals("Obj<Square>{side=4.0,diag=2.0}", Evaluator.evaluate(stop, 4).toString()); } + static final String CONSTRUCTOR_MEMORY = """ + struct S { int x; int y; }; + struct T { int z=arg+40; }; + T !t = new T; + S !a = new S { x=11; y=7; }; + S !b = new S { x=22; y=9; }; + S !p=a; + if (arg) p=b; + int before=p.x; + S !c = new S { + x=p.x+1; + { int i=0; while (i<2) { p.y=p.y+1; i=i+1; } } + y=p.y; + }; + p.x=33; + return before*10000+c.x*100+c.y+t.z; + """; + + @Test public void testConstructorMemory() { + StopNode stop = new Parser(CONSTRUCTOR_MEMORY).parse().iterate(); + assertEquals(111249L,Evaluator.evaluate(stop,0)); + assertEquals(222352L,Evaluator.evaluate(stop,1)); + } } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 72f84fa2..30af9895 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -187,7 +187,7 @@ public class Evaluator { Object[] body=null; int num; if( type.isAry() ) { - long sz = (Long)val(alloc.in(1)); + long sz = (Long)val(alloc.size()); long n = offToIdx(sz, type); if( n < 0 ) throw new NegativeArraySizeException(""+n); @@ -201,17 +201,13 @@ public class Evaluator { assert elem instanceof TypeMemPtr; } // Length value - body[0] = vall(alloc.in(2+2)); + body[0] = vall(alloc.in(3)); } else { body = new Object[num = type._fields.length]; for (int i=0; i<num; i++) - body[i] = val(alloc.in(2+i+num)); + body[i] = val(alloc.in(3+i)); } - Object[] mems = new Object[type._fields.length+2]; - // mems[0] is control - mems[1] = new Obj(type,body); // the ref - // mems[2+...] are memory aliases - return mems; + return new Object[]{new Obj(type,body),MEMORY}; } private Object load(LoadNode load) { @@ -304,10 +300,10 @@ 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]; - case ScopeMinNode mem -> null; case ReadOnlyNode ro -> val(ro.in(1)); default -> throw new AssertionError("Unexpected node " + node); }; @@ -331,7 +327,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/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 06169e2c..afcc700f 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -31,6 +31,8 @@ import java.util.*; */ public class Scheduler { + private final HashMap<Node,ArrayList<NodeData>> readers = new HashMap<>(); + /** * A basic block with a schedule of the containing nodes. * @@ -252,7 +254,7 @@ public class Scheduler { // but they did not refine the placement // so do that now. var mem = l.in(1); - for(var out : mem._outputs) { + for(var out : l.antiDeps()) { if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { @@ -270,13 +272,9 @@ public class Scheduler { for(var in:data.node._inputs) { if (in!=null) update(d(in), data.block); } - if (data.node instanceof StoreNode s) { - // 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); - } - } + var loads = readers.get(data.node); + if (loads != null) + for (var load : loads) decUsers(load); } // Now all nodes should be placed and have a block assigned @@ -442,7 +440,6 @@ public class Scheduler { private void doMarkAlive(Node node) { var cfgQueue = new Stack<NodeData>(); var dataQueue = new Stack<NodeData>(); - var mem = new Stack<NodeData>(); markAlive(cfgQueue, node, true); // Mark all CFG nodes. while (!cfgQueue.isEmpty()) { @@ -467,16 +464,16 @@ public class Scheduler { } else { for (var in : node._inputs) if (in != null && !(in instanceof CFGNode)) markAlive(dataQueue, in, false); } - if (node instanceof StoreNode) mem.push(data); - } - // Handle store nodes and increase load with an anti-dep to the store. - while (!mem.isEmpty()) { - var data = mem.pop(); - node = data.node; - for(var out:node.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(d->d.users++); - } } + // Writes, including New behind an aggregate, schedule before their + // anti-dependent reads in this reverse scheduling pass. + for (var load : data.values()) + if (load.node instanceof LoadNode l) + for (var use : l.antiDeps()) + if ((use instanceof StoreNode || use instanceof NewNode) && data.containsKey(use)) { + load.users++; + readers.computeIfAbsent(use,k->new ArrayList<>()).add(load); + } } /** |