diff options
Diffstat (limited to 'chapter10/src/test/java/com')
6 files changed, 931 insertions, 22 deletions
diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 05485d8c..adcb6b59 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; @@ -26,8 +27,8 @@ return arg; StopNode stop = parser.parse().iterate(true); assertEquals("return Phi(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); - Assert.assertEquals(5, GraphEvaluator.evaluate(stop, 1)); - Assert.assertEquals(10, GraphEvaluator.evaluate(stop, 6)); + Assert.assertEquals(5L, Evaluator.evaluate(stop, 1)); + Assert.assertEquals(10L, Evaluator.evaluate(stop, 6)); } diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 8e198218..b0b48990 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -43,8 +44,8 @@ return x; """); StopNode stop = parser.parse(true); assertEquals("Stop[ return (arg*2); return (Mul+1); ]", stop.toString()); - Assert.assertEquals(2, GraphEvaluator.evaluate(stop, 1)); - Assert.assertEquals(23, GraphEvaluator.evaluate(stop, 11)); + Assert.assertEquals(2L, Evaluator.evaluate(stop, 1)); + Assert.assertEquals(23L, Evaluator.evaluate(stop, 11)); } @Test @@ -55,7 +56,7 @@ return arg*arg-arg*arg; """); StopNode stop = parser.parse(true); assertEquals("return 0;", stop.toString()); - Assert.assertEquals(0, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(0L, Evaluator.evaluate(stop, 1)); } @Test @@ -70,7 +71,7 @@ return arg; """); StopNode stop = parser.parse(true).iterate(true); assertEquals("return Phi(Loop7,arg,(Phi_arg+2));", stop.toString()); - Assert.assertEquals(11, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(11L, Evaluator.evaluate(stop, 1)); } @Test @@ -87,7 +88,7 @@ return arg; """); StopNode stop = parser.parse(true).iterate(true); assertEquals("return Phi(Loop8,arg,(Phi_arg+4));", stop.toString()); - Assert.assertEquals(13, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(13L, Evaluator.evaluate(stop, 1)); } @Test diff --git a/chapter10/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter10/src/test/java/com/seaofnodes/simple/SchedulerTest.java new file mode 100644 index 00000000..3720dd68 --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -0,0 +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));
+ }
+
+}
diff --git a/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java new file mode 100644 index 00000000..15f65f39 --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -0,0 +1,229 @@ +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 final MethodHandle get_MemOpNode_field;
+
+ static {
+ try {
+ var MemOpNode = Class.forName("com.seaofnodes.simple.node.MemOpNode");
+ var field = MemOpNode.getDeclaredField("_field");
+ field.setAccessible(true);
+ get_MemOpNode_field = MethodHandles.lookup().unreflectGetter(field);
+ } catch (Exception e) {
+ throw new ExceptionInInitializerError(e);
+ }
+ }
+
+ private static int getFieldIndex(TypeStruct struct, Node memop) {
+ Field field;
+ try {
+ field = (Field)get_MemOpNode_field.invoke(memop);
+ } catch (Throwable e) {
+ throw new RuntimeException(e);
+ }
+ for(int i=0;i<struct._fields.length;i++) {
+ if (struct._fields[i]._alias == field._alias) return i;
+ }
+ throw new AssertionError("Field "+field._fname+" of struct " +field._sname + " 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 new file mode 100644 index 00000000..cd9271aa --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -0,0 +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);
+ }
+
+}
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 56933248..29a6853c 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,11 +1,12 @@ package com.seaofnodes.simple.fuzzer; -import com.seaofnodes.simple.GraphEvaluator; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import java.util.ArrayList; +import java.util.Objects; import java.util.Random; import java.util.function.Consumer; @@ -53,21 +54,30 @@ public class Fuzzer { System.out.flush(); } + private static boolean neq(Object a, Object b) { + if (Objects.equals(a, b)) return false; + if (a instanceof Evaluator.Obj ea && b instanceof Evaluator.Obj eb) { + if (ea.struct() != eb.struct()) return true; + for(int i=0;i<ea.fields().length;i++) { + if (neq(ea.fields()[i], eb.fields()[i])) return true; + } + return false; + } + return true; + } + /** * Check that two graphs result in the same output when supplied with a value - * @param stop1 Stop node of the first graph - * @param stop2 Stop node of the second graph + * @param e1 Evaluator for the first graph + * @param e2 Evaluator for the second graph * @param in The input value to both graphs to test for an equal output */ - private static void checkGraphs(StopNode stop1, StopNode stop2, long in) { - if (true) return; - var e1 = GraphEvaluator.evaluateWithResult(stop1, in, EVAL_TIMEOUT); - var e2 = GraphEvaluator.evaluateWithResult(stop2, in, EVAL_TIMEOUT); - if (e1.type() == GraphEvaluator.ResultType.TIMEOUT || e2.type() == GraphEvaluator.ResultType.TIMEOUT) return; - if (e1.type() != e2.type()) - throw new RuntimeException("Different calculations types " + e1.type() + " vs " + e2.type()); - if (e1.value() != e2.value()) - throw new RuntimeException("Different calculations values " + e1.value() + " vs " + e2.value()); + private static void checkGraphs(Evaluator e1, Evaluator e2, long in) { + var r1 = e1.evaluate(in, EVAL_TIMEOUT); + var r2 = e2.evaluate(in, EVAL_TIMEOUT); + if (r1 == Evaluator.Status.TIMEOUT || r2 == Evaluator.Status.TIMEOUT) return; + if (neq(r1, r2)) + throw new RuntimeException("Different calculations values " + r1 + " vs " + r2); } /** @@ -94,9 +104,11 @@ public class Fuzzer { throw e1; } var stop2 = FuzzerUtils.parse(script, true); - checkGraphs(stop1, stop2, 0); - checkGraphs(stop1, stop2, 1); - checkGraphs(stop1, stop2, 10); + var e1 = new Evaluator(stop1); + var e2 = new Evaluator(stop2); + checkGraphs(e1, e2, 0); + checkGraphs(e1, e2, 1); + checkGraphs(e1, e2, 10); } /** |