diff options
Diffstat (limited to 'chapter10/src/test/java/com')
9 files changed, 895 insertions, 895 deletions
diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 48cc716f..5abfc4cf 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -16,7 +16,7 @@ public class Chapter01Test { StopNode stop = parser.parse(); StartNode start = Parser.START; ReturnNode ret = (ReturnNode)stop.in(0); - + assertTrue(ret.ctrl() instanceof ProjNode); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { @@ -40,7 +40,7 @@ public class Chapter01Test { @Test public void testBad2() { - try { + try { new Parser("return 0123;").parse(); fail(); } catch( RuntimeException e ) { diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 351cdb16..107225ae 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -9,7 +9,7 @@ import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter02Test { - + @Test public void testParseGrammar() { Parser parser = new Parser("return 1+2*3+-5;"); @@ -64,10 +64,10 @@ public class Chapter02Test { GraphVisualizer gv = new GraphVisualizer(); System.out.println(gv.generateDotOutput(parser)); } - + @Test public void testBad1() { - try { + try { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { @@ -82,7 +82,7 @@ public class Chapter02Test { @Test public void testBad4() { - try { + try { new Parser("return 100").parse(); fail(); } catch( RuntimeException e ) { diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 8a11107d..6bcfcc4b 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -9,7 +9,7 @@ import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter03Test { - + @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); @@ -49,7 +49,7 @@ public class Chapter03Test { @Test public void testSelfAssign() { - try { + try { new Parser("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java index ffbbe9a8..5a024e77 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -9,7 +9,7 @@ import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter04Test { - + @Test public void testPeephole() { Parser parser = new Parser("return 1+arg+2; #showGraph;"); @@ -37,7 +37,7 @@ public class Chapter04Test { StopNode ret = parser.parse(); assertEquals("return (arg*2);", ret.print()); } - + @Test public void testPeephole3() { Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); @@ -51,7 +51,7 @@ public class Chapter04Test { StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } - + @Test public void testVarArg() { Parser parser = new Parser("return arg; #showGraph;"); @@ -112,7 +112,7 @@ public class Chapter04Test { @Test public void testBug3() { - try { + try { new Parser("inta=1; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -126,5 +126,5 @@ public class Chapter04Test { StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } - + } diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java index b0b48990..8e651858 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -150,7 +150,7 @@ while(v1+arg) { if(0) while(0) { int arg=arg; while(0) {} -} +} """); StopNode stop = parser.parse().iterate(true); assertEquals("Stop[ ]", stop.toString()); @@ -171,7 +171,7 @@ if(0) while(0) { assertEquals("return 3;", stop.toString()); } - + @Test public void testFuzz0() { Parser parser = new Parser(""" @@ -210,7 +210,7 @@ return -0+0+0; StopNode stop = parser.parse().iterate(true); assertEquals("return 0;", stop.toString()); } - + @Test public void testFuzz3() { Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;"); diff --git a/chapter10/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter10/src/test/java/com/seaofnodes/simple/SchedulerTest.java index 3720dd68..e5961815 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -1,74 +1,74 @@ -package com.seaofnodes.simple;
-
-import com.seaofnodes.simple.evaluator.Evaluator;
-import com.seaofnodes.simple.node.StopNode;
-import org.junit.Assert;
-import org.junit.Ignore;
-import org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-
-public class SchedulerTest {
-
- private static void assertObj(Object obj, String name, Object... fields) {
- assertEquals(Evaluator.Obj.class, obj.getClass());
- var o = (Evaluator.Obj)obj;
- assertEquals(name, o.struct()._name);
- Assert.assertArrayEquals(fields, o.fields());
- }
-
- @Test
- @Ignore
- public void testJig() {
- Parser parser = new Parser("""
-struct S {
- int f;
-}
-S v=new S;
-v.f = 2;
-int i=v.f;
-if (arg) v.f=1;
-return i;
-""");
- StopNode._disablePeephole = true;
- StopNode stop = parser.parse(true);//.iterate(true);
- var eval = new Evaluator(stop);
- assertEquals(2L, eval.evaluate(1, 10));
- }
-
- @Test
- public void testStoreInIf() {
- Parser parser = new Parser("""
-struct S {
- int f;
-}
-S v0=new S;
-if(arg) v0.f=1;
-return v0;
-""");
- StopNode stop = parser.parse(false).iterate(true);
- var eval = new Evaluator(stop);
- assertObj(eval.evaluate(0, 10), "S", 0L);
- assertObj(eval.evaluate(1, 10), "S", 1L);
- }
-
- @Test
- public void testStoreInIf2() {
- Parser parser = new Parser("""
-struct S {
- int f;
-}
-S v=new S;
-v.f = 2;
-int i=new S.f;
-i=v.f;
-if (arg) v.f=1;
-return i;
-""");
- StopNode stop = parser.parse(false).iterate(true);
- var eval = new Evaluator(stop);
- assertEquals(2L, eval.evaluate(0, 10));
- assertEquals(2L, eval.evaluate(1, 10));
- }
-
-}
+package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Assert; +import org.junit.Ignore; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class SchedulerTest { + + private static void assertObj(Object obj, String name, Object... fields) { + assertEquals(Evaluator.Obj.class, obj.getClass()); + var o = (Evaluator.Obj)obj; + assertEquals(name, o.struct()._name); + Assert.assertArrayEquals(fields, o.fields()); + } + + @Test + @Ignore + public void testJig() { + Parser parser = new Parser(""" +struct S { + int f; +} +S v=new S; +v.f = 2; +int i=v.f; +if (arg) v.f=1; +return i; +"""); + StopNode._disablePeephole = true; + StopNode stop = parser.parse(true);//.iterate(true); + var eval = new Evaluator(stop); + assertEquals(2L, eval.evaluate(1, 10)); + } + + @Test + public void testStoreInIf() { + Parser parser = new Parser(""" +struct S { + int f; +} +S v0=new S; +if(arg) v0.f=1; +return v0; +"""); + StopNode stop = parser.parse(false).iterate(true); + var eval = new Evaluator(stop); + assertObj(eval.evaluate(0, 10), "S", 0L); + assertObj(eval.evaluate(1, 10), "S", 1L); + } + + @Test + public void testStoreInIf2() { + Parser parser = new Parser(""" +struct S { + int f; +} +S v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; +"""); + StopNode stop = parser.parse(false).iterate(true); + var eval = new Evaluator(stop); + assertEquals(2L, eval.evaluate(0, 10)); + assertEquals(2L, eval.evaluate(1, 10)); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 8622eb25..3cf5c57b 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -1,209 +1,209 @@ -package com.seaofnodes.simple.evaluator;
-
-import com.seaofnodes.simple.Utils;
-import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.Field;
-import com.seaofnodes.simple.type.TypeInteger;
-import com.seaofnodes.simple.type.TypeMemPtr;
-import com.seaofnodes.simple.type.TypeStruct;
-
-import java.lang.invoke.MethodHandle;
-import java.lang.invoke.MethodHandles;
-import java.util.ArrayList;
-import java.util.BitSet;
-import java.util.Objects;
-
-public class Evaluator {
-
- private static final Object MEMORY = new Object();
-
- public record Obj(TypeStruct struct, Object[] fields) {
- @Override
- public String toString() {
- var sb = new StringBuilder();
- sb.append("Obj<").append(struct._name).append("> {");
- for(int i=0; i<struct._fields.length; i++) {
- sb.append("\n ").append(struct._fields[i]._fname).append("=").append(fields[i]);
- }
- return sb.append("\n}").toString();
- }
- }
-
- private static int getFieldIndex(TypeStruct struct, MemOpNode memop) {
- int idx = struct.find(memop._name);
- if( idx >= 0 ) return idx;
- throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name);
- }
-
- public enum Status {
- TIMEOUT,
- FALLTHROUGH
- }
-
- /**
- * Find the start node from some node in the graph or null if there is no start node
- */
- private static StartNode findStart(BitSet visit, Node node) {
- if (node == null) return null;
- if( visit.get(node._nid) ) return null;
- visit.set(node._nid);
- StartNode start = node instanceof StartNode ? (StartNode) node : null;
- for( Node def : node._inputs ) {
- var res = findStart(visit,def);
- if( res != null ) start = res;
- }
- for( Node use : node._outputs ) {
- var res = findStart(visit,use);
- if( res != null ) start = res;
- }
- return start;
- }
-
- private final Object[] values;
- private final ArrayList<Object> phiCache = new ArrayList<>();
- private final StartNode start;
- private final Scheduler.Block startBlock;
-
- public Evaluator(Node graph) {
- var visited = new BitSet();
- this.start = findStart(visited, graph);
- if (this.start == null) {
- this.values = null;
- this.startBlock = null;
- return;
- }
- this.startBlock = Scheduler.schedule(this.start);
- this.values = new Object[visited.length()];
- }
-
- private long div(DivNode div) {
- long in2 = vall(div.in(2));
- return in2 == 0 ? 0 : vall(div.in(1)) / in2;
- }
-
- private Object alloc(NewNode alloc) {
- var type = ((TypeMemPtr)alloc.compute())._obj;
- return new Obj(type, new Object[type._fields.length]);
- }
-
- private Object load(LoadNode load) {
- var from = (Obj)val(load.in(2));
- var idx = getFieldIndex(from.struct, load);
- return from.fields[idx];
- }
-
- private Object store(StoreNode store) {
- var to = (Obj)val(store.in(2));
- var val = val(store.in(3));
- var idx = getFieldIndex(to.struct, store);
- to.fields[idx] = val;
- return null;
- }
-
- private static boolean isTrue(Object obj) {
- if (obj == null) return false;
- if (obj instanceof Number n) return n.longValue() != 0;
- return true;
- }
-
- private Object val(Node node) {
- return values[node._nid];
- }
-
- private long vall(Node node) {
- var v = val(node);
- if (v instanceof Number n) return n.longValue();
- throw new AssertionError("Not a long " + v);
- }
-
- private Object cons(ConstantNode cons) {
- var type = cons.compute();
- if (type instanceof TypeInteger i) return i.value();
- assert type instanceof TypeMemPtr;
- return null;
- }
-
- private Object exec(Node node) {
- return switch (node) {
- case ConstantNode cons -> cons(cons);
- case AddNode add -> vall(add.in(1)) + vall(add.in(2));
- case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L;
- case BoolNode.LE le -> vall(le.in(1)) <= vall(le.in(2)) ? 1L : 0L;
- case BoolNode.LT lt -> vall(lt.in(1)) < vall(lt.in(2)) ? 1L : 0L;
- case DivNode div -> div(div);
- case MinusNode minus -> -vall(minus.in(1));
- case MulNode mul -> vall(mul.in(1)) * vall(mul.in(2));
- case NotNode not -> isTrue(val(not.in(1))) ? 0L : 1L;
- case SubNode sub -> vall(sub.in(1)) - vall(sub.in(2));
- case CastNode cast -> val(cast.in(1));
- case LoadNode load -> load(load);
- case StoreNode store -> store(store);
- case NewNode alloc -> alloc(alloc);
- case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx];
- default -> throw new AssertionError("Unexpected node " + node);
- };
- }
-
- /**
- * Run the graph until either a return is found or the number of loop iterations are done.
- */
- 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;
- values[start._nid] = s;
- int i=0;
- Scheduler.Block block = this.startBlock;
- for(;;) {
- for(; i<block.nodes().length;i++) values[block.nodes()[i]._nid] = exec(block.nodes()[i]);
- i=0;
- switch (block.exit()) {
- case null:
- return Status.FALLTHROUGH;
- case ReturnNode ret:
- return val(ret.in(1));
- case IfNode ifn:
- block = block.next()[isTrue(val(ifn.in(1))) ? 0 : 1];
- if (block == null) return Status.FALLTHROUGH;
- break;
- case RegionNode region:
- if (loops-- <= 0) return Status.TIMEOUT;
- int exit = block.exitId();
- assert exit > 0 && region.nIns() > exit;
- block = block.next()[0];
- assert block != null;
- for (; i < block.nodes().length; i++) {
- if (!(block.nodes()[i] instanceof PhiNode)) break;
- phiCache.add(val(block.nodes()[i].in(exit)));
- }
- for (i=0; i<phiCache.size(); i++) {
- values[block.nodes()[i]._nid] = phiCache.get(i);
- }
- phiCache.clear();
- break;
- default:
- throw Utils.TODO("Unexpected control node " + block.exit());
- }
- }
- }
-
- public static Object evaluate(StopNode graph) {
- return evaluate(graph, 0);
- }
-
- public static Object evaluate(StopNode graph, long parameter) {
- return evaluate(graph, parameter, 1000);
- }
-
- public static Object evaluate(StopNode graph, long parameter, int loops) {
- var res = evaluateWithResult(graph, parameter, loops);
- if (res == Status.TIMEOUT) throw new RuntimeException("Timeout");
- return res;
- }
-
- public static Object evaluateWithResult(StopNode graph, long parameter, int loops) {
- return new Evaluator(graph).evaluate(parameter, loops);
- }
-
-}
+package com.seaofnodes.simple.evaluator; + +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Field; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeMemPtr; +import com.seaofnodes.simple.type.TypeStruct; + +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.util.ArrayList; +import java.util.BitSet; +import java.util.Objects; + +public class Evaluator { + + private static final Object MEMORY = new Object(); + + public record Obj(TypeStruct struct, Object[] fields) { + @Override + public String toString() { + var sb = new StringBuilder(); + sb.append("Obj<").append(struct._name).append("> {"); + for(int i=0; i<struct._fields.length; i++) { + sb.append("\n ").append(struct._fields[i]._fname).append("=").append(fields[i]); + } + return sb.append("\n}").toString(); + } + } + + private static int getFieldIndex(TypeStruct struct, MemOpNode memop) { + int idx = struct.find(memop._name); + if( idx >= 0 ) return idx; + throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name); + } + + public enum Status { + TIMEOUT, + FALLTHROUGH + } + + /** + * Find the start node from some node in the graph or null if there is no start node + */ + private static StartNode findStart(BitSet visit, Node node) { + if (node == null) return null; + if( visit.get(node._nid) ) return null; + visit.set(node._nid); + StartNode start = node instanceof StartNode ? (StartNode) node : null; + for( Node def : node._inputs ) { + var res = findStart(visit,def); + if( res != null ) start = res; + } + for( Node use : node._outputs ) { + var res = findStart(visit,use); + if( res != null ) start = res; + } + return start; + } + + private final Object[] values; + private final ArrayList<Object> phiCache = new ArrayList<>(); + private final StartNode start; + private final Scheduler.Block startBlock; + + public Evaluator(Node graph) { + var visited = new BitSet(); + this.start = findStart(visited, graph); + if (this.start == null) { + this.values = null; + this.startBlock = null; + return; + } + this.startBlock = Scheduler.schedule(this.start); + this.values = new Object[visited.length()]; + } + + private long div(DivNode div) { + long in2 = vall(div.in(2)); + return in2 == 0 ? 0 : vall(div.in(1)) / in2; + } + + private Object alloc(NewNode alloc) { + var type = ((TypeMemPtr)alloc.compute())._obj; + return new Obj(type, new Object[type._fields.length]); + } + + private Object load(LoadNode load) { + var from = (Obj)val(load.in(2)); + var idx = getFieldIndex(from.struct, load); + return from.fields[idx]; + } + + private Object store(StoreNode store) { + var to = (Obj)val(store.in(2)); + var val = val(store.in(3)); + var idx = getFieldIndex(to.struct, store); + to.fields[idx] = val; + return null; + } + + private static boolean isTrue(Object obj) { + if (obj == null) return false; + if (obj instanceof Number n) return n.longValue() != 0; + return true; + } + + private Object val(Node node) { + return values[node._nid]; + } + + private long vall(Node node) { + var v = val(node); + if (v instanceof Number n) return n.longValue(); + throw new AssertionError("Not a long " + v); + } + + private Object cons(ConstantNode cons) { + var type = cons.compute(); + if (type instanceof TypeInteger i) return i.value(); + assert type instanceof TypeMemPtr; + return null; + } + + private Object exec(Node node) { + return switch (node) { + case ConstantNode cons -> cons(cons); + case AddNode add -> vall(add.in(1)) + vall(add.in(2)); + case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; + case BoolNode.LE le -> vall(le.in(1)) <= vall(le.in(2)) ? 1L : 0L; + case BoolNode.LT lt -> vall(lt.in(1)) < vall(lt.in(2)) ? 1L : 0L; + case DivNode div -> div(div); + case MinusNode minus -> -vall(minus.in(1)); + case MulNode mul -> vall(mul.in(1)) * vall(mul.in(2)); + case NotNode not -> isTrue(val(not.in(1))) ? 0L : 1L; + case SubNode sub -> vall(sub.in(1)) - vall(sub.in(2)); + case CastNode cast -> val(cast.in(1)); + case LoadNode load -> load(load); + case StoreNode store -> store(store); + case NewNode alloc -> alloc(alloc); + case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx]; + default -> throw new AssertionError("Unexpected node " + node); + }; + } + + /** + * Run the graph until either a return is found or the number of loop iterations are done. + */ + 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; + values[start._nid] = s; + int i=0; + Scheduler.Block block = this.startBlock; + for(;;) { + for(; i<block.nodes().length;i++) values[block.nodes()[i]._nid] = exec(block.nodes()[i]); + i=0; + switch (block.exit()) { + case null: + return Status.FALLTHROUGH; + case ReturnNode ret: + return val(ret.in(1)); + case IfNode ifn: + block = block.next()[isTrue(val(ifn.in(1))) ? 0 : 1]; + if (block == null) return Status.FALLTHROUGH; + break; + case RegionNode region: + if (loops-- <= 0) return Status.TIMEOUT; + int exit = block.exitId(); + assert exit > 0 && region.nIns() > exit; + block = block.next()[0]; + assert block != null; + for (; i < block.nodes().length; i++) { + if (!(block.nodes()[i] instanceof PhiNode)) break; + phiCache.add(val(block.nodes()[i].in(exit))); + } + for (i=0; i<phiCache.size(); i++) { + values[block.nodes()[i]._nid] = phiCache.get(i); + } + phiCache.clear(); + break; + default: + throw Utils.TODO("Unexpected control node " + block.exit()); + } + } + } + + public static Object evaluate(StopNode graph) { + return evaluate(graph, 0); + } + + public static Object evaluate(StopNode graph, long parameter) { + return evaluate(graph, parameter, 1000); + } + + public static Object evaluate(StopNode graph, long parameter, int loops) { + var res = evaluateWithResult(graph, parameter, loops); + if (res == Status.TIMEOUT) throw new RuntimeException("Timeout"); + return res; + } + + public static Object evaluateWithResult(StopNode graph, long parameter, int loops) { + return new Evaluator(graph).evaluate(parameter, loops); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index cd9271aa..674d12f5 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -1,592 +1,592 @@ -package com.seaofnodes.simple.evaluator;
-
-import com.seaofnodes.simple.Utils;
-import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.Type;
-
-import java.util.*;
-
-/**
- * A late scheduler for test cases.
- * <br>
- * <br>
- * This scheduler is used for tests and is not the final scheduler.
- * <br>
- * <br>
- * The scheduler schedules not as late as possible. Since it is just for test cases this is fine.
- * A better scheduler will try to place nodes outside of loops. Due to the schedule late strategy
- * this scheduler might place initialization code in loops.
- * <br>
- * We schedule late here since memory edges have some implicit information. There can only be one
- * memory edge (for a field) at a time. However, before <code>if</code> statements this might split.
- * When scheduling early a store might be moved out of the loop but then there are two edges alive.
- * The one through the store node and the adjacent one. This is an invalid schedule and instead of
- * handling this case a late scheduler does not have this problem as memory edges are combined
- * through phi nodes.
- * <br>
- * <br>
- * A bit about this scheduler. It first discovers all alive nodes and allocates side data for them.
- * Then the control flow graph is build. Then, all phis are placed and finally all the remaining nodes
- * in an order where a node is placed when all alive uses are placed. Finally, the output is produced.
- */
-public class Scheduler {
-
- /**
- * A basic block with a schedule of the containing nodes.
- *
- * @param nodes The nodes in the final schedule of this block
- * @param exit The exit node of this block.
- * @param exitId In case the next block is a region this gives the entry id into the region.
- * @param next The next blocks.
- */
- public record Block(Node[] nodes, Node exit, int exitId, Block[] next) {}
-
- /**
- * Definition of a block in the building process.
- */
- private static class BasicBlock {
-
- /**
- * Dominator of this block
- */
- final BasicBlock dom;
- /**
- * Id of this block where <code>a.depth < b.depth</code> means that a is before b or
- * both are in different branches.
- */
- final int depth;
- /**
- * Previous blocks
- */
- final BasicBlock[] prev;
- /**
- * Entry to this block
- */
- final Node entry;
- /**
- * Schedules node in reverse order.
- */
- final ArrayList<Node> reverseSchedule = new ArrayList<>();
-
- /**
- * Initialize the block.
- * @param entry The node that started this block
- * @param depth The depth of this node. All previous nodes need to have a lower value.
- * @param prev The previous blocks.
- */
- BasicBlock(Node entry, int depth, BasicBlock... prev) {
- BasicBlock dom = null;
- int max = -1;
- for(var bb: prev) {
- max = Math.max(max, bb.depth);
- dom = dom==null?bb:dom(dom, bb);
- }
- assert depth > max;
- this.dom = dom;
- this.depth = depth;
- this.entry = entry;
- this.prev = prev;
- }
-
- }
-
- /**
- * Ancillary data for nodes used during the scheduling process.
- */
- private static class NodeData {
-
- /**
- * The node this ancillary data is used for.
- */
- final Node node;
-
- /**
- * Number of alive users not yet scheduled.
- */
- int users = 1;
-
- /**
- * Block into which the node should be placed so far.
- * This will be updated with every placed use.
- */
- BasicBlock block;
-
- /**
- * Initialize ancillary data for a node
- * @param node The node this ancillary data is associated with.
- */
- NodeData(Node node) {
- this.node = node;
- }
-
- }
-
- /**
- * Ancillary data for nodes.
- */
- private final IdentityHashMap<Node, NodeData> data = new IdentityHashMap<>();
- /**
- * List of nodes which can be placed since all users are placed.
- */
- private final Stack<NodeData> scheduleQueue = new Stack<>();
-
- /**
- * Get the ancillary data for an alive node.
- * @param node The node for which the ancillary data is requested.
- * @return The ancillary data for the node.
- */
- NodeData d(Node node) {
- return od(node).orElseThrow(AssertionError::new);
- }
-
- /**
- * Get the ancillary data for a potentially dead node.
- * @param node The node for which the ancillary data is requested.
- * @return The ancillary data for the node an alive node or
- * <code>Optional.empty()</code> for <code>null</code> or dead nodes.
- */
- Optional<NodeData> od(Node node) {
- return Optional.ofNullable(data.get(node));
- }
-
- /**
- * Checks a node for validity
- * @param data The node to check.
- * @return true if all placed inputs are before this node.
- */
- private boolean isValid(NodeData data) {
- return data.node._inputs.stream().map(i->i==null?null:d(i)).map(d->d==null||d.users>0?null:d.block).allMatch(d->d==null||dom(d, data.block)==d);
- }
-
- /**
- * Checks that node is not XCtrl.
- * @param node The node to check.
- * @return true if the node is not XCtrl.
- */
- private static boolean isNotXCtrl(Node node) {
- return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL);
- }
-
- /**
- * Return the dominator of <code>a</code> and <code>b</code>
- * @param a Block a
- * @param b Block b
- * @return The dominator of <code>a</code> and <code>b</code>
- */
- private static BasicBlock dom(BasicBlock a, BasicBlock b) {
- while (a!=b) {
- if (a.depth >= b.depth) a=a.dom;
- if (b.depth > a.depth) b=b.dom;
- }
- return a;
- }
-
- /**
- * Return if a is before b.
- * @param a Block a
- * @param b Block b
- * @return true is a is before b.
- */
- private static boolean isBefore(BasicBlock a, BasicBlock b) {
- while (b.depth > a.depth) {
- while (b.dom.depth > a.depth) b = b.dom;
- for (int i=0; i<b.prev.length-1; i++) {
- if (isBefore(a, b.prev[i])) return true;
- }
- b = b.prev[b.prev.length-1];
- }
- return a == b;
- }
-
- /**
- * Is node placed during the control flow graph build.
- * @param data Node to check.
- * @return true if node is placed during the control flow graph build.
- */
- private static boolean isPinnedNode(NodeData data) {
- return data.node.isCFG() || data.node instanceof PhiNode;
- }
-
- /**
- * Refine placement of a node.
- * @param data The node to refine.
- * @param block The block before the node should be scheduled.
- */
- private void refinePlacement(NodeData data, BasicBlock block) {
- assert !isPinnedNode(data);
- data.block = data.block == null ? block : dom(data.block, block);
- assert isValid(data);
- }
-
- /**
- * Refine placement if before is happening before data
- * @param data The node for which the placement should be refined.
- * @param before The node before which the data node should be placed.
- */
- private void optionalRefinePlacement(NodeData data, Node before) {
- od(before).ifPresent(d->{
- // before might be in a different branch. So check this case with isBefore
- // and only refine the placement if it is not in a different branch.
- if (isBefore(d.block, data.block)) refinePlacement(data, d.block);
- });
- }
-
- /**
- * Schedule all nodes not yet scheduled.
- */
- private void doSchedule() {
- while (!scheduleQueue.isEmpty()) {
- var data = scheduleQueue.pop();
- assert !isPinnedNode(data);
-
- assert data.block != null;
- assert data.users == 0;
-
- if (data.node instanceof LoadNode l) {
- assert isValid(data);
- // Handle anti-deps of load nodes.
- // At this point all anti-dep nodes are scheduled,
- // but they did not refine the placement
- // so do that now.
- var mem = l.in(1);
- for(var out : mem._outputs) {
- if (out instanceof PhiNode p) {
- var r = p.in(0);
- for (int i = 1; i < p.nIns(); i++) {
- if (p.in(i) == mem) optionalRefinePlacement(data, r.in(i));
- }
- } else if (!(out instanceof LoadNode)) {
- optionalRefinePlacement(data, out);
- }
- }
- }
-
- assert isValid(data);
- data.block.reverseSchedule.add(data.node);
-
- 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);
- }
- }
- }
-
- // Now all nodes should be placed and have a block assigned
- assert this.data.values().stream().noneMatch(d->d.block==null);
- }
-
- /**
- * Decrement the not-yet-placed users of a block.
- * @param data The node for which the users should be decremented.
- */
- private void decUsers(NodeData data) {
- assert data.users > 0;
- if (--data.users == 0) {
- assert data.block != null;
- assert isValid(data);
-
- // When all users are gone this node can be scheduled.
- scheduleQueue.push(data);
- }
- }
-
- /**
- * Update the placement of a node
- * @param data The node to update
- * @param block The block before which the node should happen.
- */
- private void update(NodeData data, BasicBlock block) {
- assert block != null;
- if (data.users == 0) {
- assert isPinnedNode(data);
- return;
- }
- refinePlacement(data, block);
- decUsers(data);
- }
-
- /**
- * Checks if a CFG node is ready to be placed. This is used for regions joining branches.
- * @param node The CFG node to check
- * @return true if all parents of a CFG node are placed.
- */
- private boolean isCFGNodeReady(Node node) {
- if (node instanceof LoopNode l) {
- assert d(l.in(1)).block != null;
- } else if (node instanceof RegionNode r) {
- for(int i=1; i<r.nIns(); i++) {
- if (od(r.in(i)).map(d->d.block==null).orElse(false)) return false;
- }
- } else {
- assert d(node.in(0)).block != null;
- }
- return true;
- }
-
- /**
- * Schedule all phi nodes.
- * @param phiQueue List of all the phi nodes to schedule.
- */
- private void schedulePhis(Stack<NodeData> phiQueue) {
- while(!phiQueue.empty()) {
- var data = phiQueue.pop();
- var phi = (PhiNode) data.node;
- var r = phi.in(0);
- data.block = d(r).block;
- for(int i=1; i<phi.nIns(); i++) {
- var in = phi.in(i);
- od(r.in(i)).ifPresent(d->update(d(in), d.block));
- }
- }
- }
-
- /**
- * Build the control flow graph.
- * @param start The start node.
- */
- private void doBuildCTF(StartNode start) {
- var queue = new Stack<NodeData>();
- var phiQueue = new Stack<NodeData>();
- queue.push(d(start));
- int depth = 0;
- while (!queue.isEmpty()) {
- var data = queue.pop();
- var node = data.node;
- assert node.isCFG();
- BasicBlock block;
- switch (node) {
- case StartNode s:
- block = new BasicBlock(s, depth++);
- break;
- case LoopNode l:
- block = new BasicBlock(l, depth++, d(l.in(1)).block);
- break;
- case RegionNode r:
- var prev = new ArrayList<BasicBlock>();
- for(int i=1; i<r.nIns(); i++) {
- od(r.in(i)).ifPresent(d->prev.add(d.block));
- }
- block = new BasicBlock(r, depth++, prev.toArray(BasicBlock[]::new));
- break;
- case IfNode i:
- block = d(i.in(0)).block;
- break;
- case ReturnNode r:
- block = d(r.in(0)).block;
- break;
- default:
- block = new BasicBlock(node, depth++, d(node.in(0)).block);
- }
- data.block = block;
- if (node instanceof RegionNode r) {
- // Regions might have phis which need to be scheduled.
- // Put them on a list for later scheduling.
- for (var out:r._outputs) {
- if (out instanceof PhiNode p) {
- var d = this.data.get(p);
- if (d!=null) {
- d.users=0;
- phiQueue.push(d);
- }
- }
- }
- }
- if (!(node instanceof ReturnNode))
- for (Node n:node._outputs) if (n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n));
- var b = block;
- for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b));
- }
-
- // Schedule all phi nodes.
- schedulePhis(phiQueue);
- }
-
- /**
- * Mark a node alive and create ancillary data for it.
- * @param queue List into which this node should be placed if it needs to be visited.
- * @param node Node which should be marked alive.
- * @param cfg If this node is a CFG node.
- */
- private void markAlive(Stack<NodeData> queue, Node node, boolean cfg) {
- var nd = od(node).orElse(null);
- if (nd != null) {
- // Node was already visited, just increase the users.
- if (nd.users>0) nd.users++;
- return;
- }
- assert node.isCFG() == cfg;
- assert isNotXCtrl(node);
- nd = new NodeData(node);
- if (cfg) nd.users=0;
- data.put(node, nd);
- queue.push(nd);
- }
-
- /**
- * Mark all alive nodes.
- * First all CFG nodes are marked, then all other nodes.
- * @param node THe start node.
- */
- 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()) {
- var data = cfgQueue.pop();
- node = data.node;
- assert node.isCFG();
- if (!(node instanceof ReturnNode)) {
- for (var out : node._outputs) if (out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true);
- }
- for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false);
- }
- // Mark all other nodes.
- while (!dataQueue.isEmpty()) {
- var data = dataQueue.pop();
- node = data.node;
- assert !node.isCFG();
- if (node instanceof PhiNode phi) {
- var r = phi.in(0);
- for (int i=1; i<phi.nIns(); i++) {
- if (od(r.in(i)).isPresent()) markAlive(dataQueue, phi.in(i), false);
- }
- } else {
- for (var in : node._inputs) if (in != null && !in.isCFG()) 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++);
- }
- }
- }
-
- /**
- * Helper function to append the nodes of a block to an array of nodes
- * @param arr The array the nodes of a block should be appended to.
- * @param node A potentially separator node
- * @param block The block from which the nodes should be appended.
- * @return The combined new array.
- */
- private static Node[] appendNodes(Node[] arr, Node node, BasicBlock block) {
- var idx = arr.length;
- arr = Arrays.copyOf(arr, arr.length+block.reverseSchedule.size()+(node==null?0:1));
- if (node != null) arr[idx++] = node;
- for(int i=block.reverseSchedule.size()-1;i>=0;i--) {
- arr[idx++] = block.reverseSchedule.get(i);
- }
- return arr;
- }
-
- /**
- * Find the CFG output of a node
- * @param node The node
- * @return THe CFG output of the node.
- */
- private static Node findSingleCFGOut(Node node) {
- if (node instanceof StartNode) {
- for(var n:node._outputs) if (n instanceof ProjNode p && p._idx==0) return p;
- return null;
- }
- assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1;
- for(var n:node._outputs) if(n.isCFG()) return n;
- return null;
- }
-
- /**
- * Build the final data structure after all the scheduling happened.
- * @param start The start node
- * @return The final schedule.
- */
- private Block build(Node start) {
- var blocks = new IdentityHashMap<Node, Block>();
- var queue = new Stack<NodeData>();
- queue.push(d(start));
-
- // Visit all CFG nodes and create blocks for them.
- // This can combine blocks.
- while(!queue.isEmpty()) {
- var data = queue.pop();
- var first = data.node;
- Node prev;
- var last = first;
- Node[] arr = new Node[0];
- if (first instanceof RegionNode) {
- var nodes = new ArrayList<Node>();
- for(var out: first._outputs) {
- if (out instanceof PhiNode) {
- if(od(out).isPresent()) nodes.add(out);
- }
- }
- arr = nodes.toArray(arr);
- }
- arr = appendNodes(arr, null, data.block);
- assert !(first instanceof IfNode);
- for(;;) {
- prev = last;
- last = findSingleCFGOut(last);
- if (last == null) break;
- if (last instanceof RegionNode) {
- if (blocks.get(last) == null && last != first)
- queue.push(d(last));
- break;
- }
- if (last instanceof ReturnNode) break;
- if (last instanceof IfNode if_) {
- for(var out:if_._outputs) if (out.isCFG() && blocks.get(out) == null) queue.push(d(out));
- break;
- }
- data = d(last);
- arr = appendNodes(arr, data.node, data.block);
- }
- blocks.put(first, switch(last) {
- case null -> new Block(arr, null, -1, new Block[0]);
- case IfNode i -> new Block(arr, i, -1, new Block[2]);
- case RegionNode r -> new Block(arr, r, Utils.find(r._inputs, prev), new Block[1]);
- case ReturnNode r -> new Block(arr, r, -1, new Block[0]);
- default -> throw new AssertionError("Unexpected block exit node");
- });
- }
- // Update the next pointer of all blocks.
- for (var block: blocks.values()) {
- switch(block.exit) {
- case null: break;
- case IfNode i:
- for(var out:i._outputs) if (out instanceof ProjNode p) block.next[p._idx] = blocks.get(p);
- break;
- case RegionNode r:
- block.next[0] = blocks.get(r);
- break;
- default:
- assert block.exit instanceof ReturnNode;
- }
- }
- // And return the block for the start node.
- return blocks.get(start);
- }
-
- /**
- * Create a schedule for the program reachable from start.
- * @param start The start node
- * @return The final schedule.
- */
- public static Scheduler.Block schedule(StartNode start) {
- var scheduler = new Scheduler();
- scheduler.doMarkAlive(start);
- scheduler.doBuildCTF(start);
- scheduler.doSchedule();
- return scheduler.build(start);
- }
-
-}
+package com.seaofnodes.simple.evaluator; + +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; + +import java.util.*; + +/** + * A late scheduler for test cases. + * <br> + * <br> + * This scheduler is used for tests and is not the final scheduler. + * <br> + * <br> + * The scheduler schedules not as late as possible. Since it is just for test cases this is fine. + * A better scheduler will try to place nodes outside of loops. Due to the schedule late strategy + * this scheduler might place initialization code in loops. + * <br> + * We schedule late here since memory edges have some implicit information. There can only be one + * memory edge (for a field) at a time. However, before <code>if</code> statements this might split. + * When scheduling early a store might be moved out of the loop but then there are two edges alive. + * The one through the store node and the adjacent one. This is an invalid schedule and instead of + * handling this case a late scheduler does not have this problem as memory edges are combined + * through phi nodes. + * <br> + * <br> + * A bit about this scheduler. It first discovers all alive nodes and allocates side data for them. + * Then the control flow graph is build. Then, all phis are placed and finally all the remaining nodes + * in an order where a node is placed when all alive uses are placed. Finally, the output is produced. + */ +public class Scheduler { + + /** + * A basic block with a schedule of the containing nodes. + * + * @param nodes The nodes in the final schedule of this block + * @param exit The exit node of this block. + * @param exitId In case the next block is a region this gives the entry id into the region. + * @param next The next blocks. + */ + public record Block(Node[] nodes, Node exit, int exitId, Block[] next) {} + + /** + * Definition of a block in the building process. + */ + private static class BasicBlock { + + /** + * Dominator of this block + */ + final BasicBlock dom; + /** + * Id of this block where <code>a.depth < b.depth</code> means that a is before b or + * both are in different branches. + */ + final int depth; + /** + * Previous blocks + */ + final BasicBlock[] prev; + /** + * Entry to this block + */ + final Node entry; + /** + * Schedules node in reverse order. + */ + final ArrayList<Node> reverseSchedule = new ArrayList<>(); + + /** + * Initialize the block. + * @param entry The node that started this block + * @param depth The depth of this node. All previous nodes need to have a lower value. + * @param prev The previous blocks. + */ + BasicBlock(Node entry, int depth, BasicBlock... prev) { + BasicBlock dom = null; + int max = -1; + for(var bb: prev) { + max = Math.max(max, bb.depth); + dom = dom==null?bb:dom(dom, bb); + } + assert depth > max; + this.dom = dom; + this.depth = depth; + this.entry = entry; + this.prev = prev; + } + + } + + /** + * Ancillary data for nodes used during the scheduling process. + */ + private static class NodeData { + + /** + * The node this ancillary data is used for. + */ + final Node node; + + /** + * Number of alive users not yet scheduled. + */ + int users = 1; + + /** + * Block into which the node should be placed so far. + * This will be updated with every placed use. + */ + BasicBlock block; + + /** + * Initialize ancillary data for a node + * @param node The node this ancillary data is associated with. + */ + NodeData(Node node) { + this.node = node; + } + + } + + /** + * Ancillary data for nodes. + */ + private final IdentityHashMap<Node, NodeData> data = new IdentityHashMap<>(); + /** + * List of nodes which can be placed since all users are placed. + */ + private final Stack<NodeData> scheduleQueue = new Stack<>(); + + /** + * Get the ancillary data for an alive node. + * @param node The node for which the ancillary data is requested. + * @return The ancillary data for the node. + */ + NodeData d(Node node) { + return od(node).orElseThrow(AssertionError::new); + } + + /** + * Get the ancillary data for a potentially dead node. + * @param node The node for which the ancillary data is requested. + * @return The ancillary data for the node an alive node or + * <code>Optional.empty()</code> for <code>null</code> or dead nodes. + */ + Optional<NodeData> od(Node node) { + return Optional.ofNullable(data.get(node)); + } + + /** + * Checks a node for validity + * @param data The node to check. + * @return true if all placed inputs are before this node. + */ + private boolean isValid(NodeData data) { + return data.node._inputs.stream().map(i->i==null?null:d(i)).map(d->d==null||d.users>0?null:d.block).allMatch(d->d==null||dom(d, data.block)==d); + } + + /** + * Checks that node is not XCtrl. + * @param node The node to check. + * @return true if the node is not XCtrl. + */ + private static boolean isNotXCtrl(Node node) { + return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL); + } + + /** + * Return the dominator of <code>a</code> and <code>b</code> + * @param a Block a + * @param b Block b + * @return The dominator of <code>a</code> and <code>b</code> + */ + private static BasicBlock dom(BasicBlock a, BasicBlock b) { + while (a!=b) { + if (a.depth >= b.depth) a=a.dom; + if (b.depth > a.depth) b=b.dom; + } + return a; + } + + /** + * Return if a is before b. + * @param a Block a + * @param b Block b + * @return true is a is before b. + */ + private static boolean isBefore(BasicBlock a, BasicBlock b) { + while (b.depth > a.depth) { + while (b.dom.depth > a.depth) b = b.dom; + for (int i=0; i<b.prev.length-1; i++) { + if (isBefore(a, b.prev[i])) return true; + } + b = b.prev[b.prev.length-1]; + } + return a == b; + } + + /** + * Is node placed during the control flow graph build. + * @param data Node to check. + * @return true if node is placed during the control flow graph build. + */ + private static boolean isPinnedNode(NodeData data) { + return data.node.isCFG() || data.node instanceof PhiNode; + } + + /** + * Refine placement of a node. + * @param data The node to refine. + * @param block The block before the node should be scheduled. + */ + private void refinePlacement(NodeData data, BasicBlock block) { + assert !isPinnedNode(data); + data.block = data.block == null ? block : dom(data.block, block); + assert isValid(data); + } + + /** + * Refine placement if before is happening before data + * @param data The node for which the placement should be refined. + * @param before The node before which the data node should be placed. + */ + private void optionalRefinePlacement(NodeData data, Node before) { + od(before).ifPresent(d->{ + // before might be in a different branch. So check this case with isBefore + // and only refine the placement if it is not in a different branch. + if (isBefore(d.block, data.block)) refinePlacement(data, d.block); + }); + } + + /** + * Schedule all nodes not yet scheduled. + */ + private void doSchedule() { + while (!scheduleQueue.isEmpty()) { + var data = scheduleQueue.pop(); + assert !isPinnedNode(data); + + assert data.block != null; + assert data.users == 0; + + if (data.node instanceof LoadNode l) { + assert isValid(data); + // Handle anti-deps of load nodes. + // At this point all anti-dep nodes are scheduled, + // but they did not refine the placement + // so do that now. + var mem = l.in(1); + for(var out : mem._outputs) { + if (out instanceof PhiNode p) { + var r = p.in(0); + for (int i = 1; i < p.nIns(); i++) { + if (p.in(i) == mem) optionalRefinePlacement(data, r.in(i)); + } + } else if (!(out instanceof LoadNode)) { + optionalRefinePlacement(data, out); + } + } + } + + assert isValid(data); + data.block.reverseSchedule.add(data.node); + + 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); + } + } + } + + // Now all nodes should be placed and have a block assigned + assert this.data.values().stream().noneMatch(d->d.block==null); + } + + /** + * Decrement the not-yet-placed users of a block. + * @param data The node for which the users should be decremented. + */ + private void decUsers(NodeData data) { + assert data.users > 0; + if (--data.users == 0) { + assert data.block != null; + assert isValid(data); + + // When all users are gone this node can be scheduled. + scheduleQueue.push(data); + } + } + + /** + * Update the placement of a node + * @param data The node to update + * @param block The block before which the node should happen. + */ + private void update(NodeData data, BasicBlock block) { + assert block != null; + if (data.users == 0) { + assert isPinnedNode(data); + return; + } + refinePlacement(data, block); + decUsers(data); + } + + /** + * Checks if a CFG node is ready to be placed. This is used for regions joining branches. + * @param node The CFG node to check + * @return true if all parents of a CFG node are placed. + */ + private boolean isCFGNodeReady(Node node) { + if (node instanceof LoopNode l) { + assert d(l.in(1)).block != null; + } else if (node instanceof RegionNode r) { + for(int i=1; i<r.nIns(); i++) { + if (od(r.in(i)).map(d->d.block==null).orElse(false)) return false; + } + } else { + assert d(node.in(0)).block != null; + } + return true; + } + + /** + * Schedule all phi nodes. + * @param phiQueue List of all the phi nodes to schedule. + */ + private void schedulePhis(Stack<NodeData> phiQueue) { + while(!phiQueue.empty()) { + var data = phiQueue.pop(); + var phi = (PhiNode) data.node; + var r = phi.in(0); + data.block = d(r).block; + for(int i=1; i<phi.nIns(); i++) { + var in = phi.in(i); + od(r.in(i)).ifPresent(d->update(d(in), d.block)); + } + } + } + + /** + * Build the control flow graph. + * @param start The start node. + */ + private void doBuildCTF(StartNode start) { + var queue = new Stack<NodeData>(); + var phiQueue = new Stack<NodeData>(); + queue.push(d(start)); + int depth = 0; + while (!queue.isEmpty()) { + var data = queue.pop(); + var node = data.node; + assert node.isCFG(); + BasicBlock block; + switch (node) { + case StartNode s: + block = new BasicBlock(s, depth++); + break; + case LoopNode l: + block = new BasicBlock(l, depth++, d(l.in(1)).block); + break; + case RegionNode r: + var prev = new ArrayList<BasicBlock>(); + for(int i=1; i<r.nIns(); i++) { + od(r.in(i)).ifPresent(d->prev.add(d.block)); + } + block = new BasicBlock(r, depth++, prev.toArray(BasicBlock[]::new)); + break; + case IfNode i: + block = d(i.in(0)).block; + break; + case ReturnNode r: + block = d(r.in(0)).block; + break; + default: + block = new BasicBlock(node, depth++, d(node.in(0)).block); + } + data.block = block; + if (node instanceof RegionNode r) { + // Regions might have phis which need to be scheduled. + // Put them on a list for later scheduling. + for (var out:r._outputs) { + if (out instanceof PhiNode p) { + var d = this.data.get(p); + if (d!=null) { + d.users=0; + phiQueue.push(d); + } + } + } + } + if (!(node instanceof ReturnNode)) + for (Node n:node._outputs) if (n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + var b = block; + for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b)); + } + + // Schedule all phi nodes. + schedulePhis(phiQueue); + } + + /** + * Mark a node alive and create ancillary data for it. + * @param queue List into which this node should be placed if it needs to be visited. + * @param node Node which should be marked alive. + * @param cfg If this node is a CFG node. + */ + private void markAlive(Stack<NodeData> queue, Node node, boolean cfg) { + var nd = od(node).orElse(null); + if (nd != null) { + // Node was already visited, just increase the users. + if (nd.users>0) nd.users++; + return; + } + assert node.isCFG() == cfg; + assert isNotXCtrl(node); + nd = new NodeData(node); + if (cfg) nd.users=0; + data.put(node, nd); + queue.push(nd); + } + + /** + * Mark all alive nodes. + * First all CFG nodes are marked, then all other nodes. + * @param node THe start node. + */ + 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()) { + var data = cfgQueue.pop(); + node = data.node; + assert node.isCFG(); + if (!(node instanceof ReturnNode)) { + for (var out : node._outputs) if (out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); + } + for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false); + } + // Mark all other nodes. + while (!dataQueue.isEmpty()) { + var data = dataQueue.pop(); + node = data.node; + assert !node.isCFG(); + if (node instanceof PhiNode phi) { + var r = phi.in(0); + for (int i=1; i<phi.nIns(); i++) { + if (od(r.in(i)).isPresent()) markAlive(dataQueue, phi.in(i), false); + } + } else { + for (var in : node._inputs) if (in != null && !in.isCFG()) 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++); + } + } + } + + /** + * Helper function to append the nodes of a block to an array of nodes + * @param arr The array the nodes of a block should be appended to. + * @param node A potentially separator node + * @param block The block from which the nodes should be appended. + * @return The combined new array. + */ + private static Node[] appendNodes(Node[] arr, Node node, BasicBlock block) { + var idx = arr.length; + arr = Arrays.copyOf(arr, arr.length+block.reverseSchedule.size()+(node==null?0:1)); + if (node != null) arr[idx++] = node; + for(int i=block.reverseSchedule.size()-1;i>=0;i--) { + arr[idx++] = block.reverseSchedule.get(i); + } + return arr; + } + + /** + * Find the CFG output of a node + * @param node The node + * @return THe CFG output of the node. + */ + private static Node findSingleCFGOut(Node node) { + if (node instanceof StartNode) { + for(var n:node._outputs) if (n instanceof ProjNode p && p._idx==0) return p; + return null; + } + assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1; + for(var n:node._outputs) if(n.isCFG()) return n; + return null; + } + + /** + * Build the final data structure after all the scheduling happened. + * @param start The start node + * @return The final schedule. + */ + private Block build(Node start) { + var blocks = new IdentityHashMap<Node, Block>(); + var queue = new Stack<NodeData>(); + queue.push(d(start)); + + // Visit all CFG nodes and create blocks for them. + // This can combine blocks. + while(!queue.isEmpty()) { + var data = queue.pop(); + var first = data.node; + Node prev; + var last = first; + Node[] arr = new Node[0]; + if (first instanceof RegionNode) { + var nodes = new ArrayList<Node>(); + for(var out: first._outputs) { + if (out instanceof PhiNode) { + if(od(out).isPresent()) nodes.add(out); + } + } + arr = nodes.toArray(arr); + } + arr = appendNodes(arr, null, data.block); + assert !(first instanceof IfNode); + for(;;) { + prev = last; + last = findSingleCFGOut(last); + if (last == null) break; + if (last instanceof RegionNode) { + if (blocks.get(last) == null && last != first) + queue.push(d(last)); + break; + } + if (last instanceof ReturnNode) break; + if (last instanceof IfNode if_) { + for(var out:if_._outputs) if (out.isCFG() && blocks.get(out) == null) queue.push(d(out)); + break; + } + data = d(last); + arr = appendNodes(arr, data.node, data.block); + } + blocks.put(first, switch(last) { + case null -> new Block(arr, null, -1, new Block[0]); + case IfNode i -> new Block(arr, i, -1, new Block[2]); + case RegionNode r -> new Block(arr, r, Utils.find(r._inputs, prev), new Block[1]); + case ReturnNode r -> new Block(arr, r, -1, new Block[0]); + default -> throw new AssertionError("Unexpected block exit node"); + }); + } + // Update the next pointer of all blocks. + for (var block: blocks.values()) { + switch(block.exit) { + case null: break; + case IfNode i: + for(var out:i._outputs) if (out instanceof ProjNode p) block.next[p._idx] = blocks.get(p); + break; + case RegionNode r: + block.next[0] = blocks.get(r); + break; + default: + assert block.exit instanceof ReturnNode; + } + } + // And return the block for the start node. + return blocks.get(start); + } + + /** + * Create a schedule for the program reachable from start. + * @param start The start node + * @return The final schedule. + */ + public static Scheduler.Block schedule(StartNode start) { + var scheduler = new Scheduler(); + scheduler.doMarkAlive(start); + scheduler.doBuildCTF(start); + scheduler.doSchedule(); + return scheduler.build(start); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 29a6853c..51e39cd0 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -134,16 +134,16 @@ public class Fuzzer { new ScriptGenerator(rand, sb, true).genProgram(); try { var parser = new Parser(sb.toString()); - + var stop = parser.parse(); int parse_peeps= Node.ITER_CNT; int parse_nops = Node.ITER_NOP_CNT; double parse_nop_ratio = (double)parse_nops/parse_peeps; int nids = Node.UID(); if( nids <= max_nids ) return max_nids; - + double parse_peeps_per_node = (double)parse_peeps/nids; - + stop.iterate(); int iter_peeps= Node.ITER_CNT; int iter_nops = Node.ITER_NOP_CNT; @@ -174,7 +174,7 @@ public class Fuzzer { check(sb.toString(), valid, seed); } - + /** * Check that no exceptions happened. * @return true if no exception happened |