From b2663f1ca36a07f9a31a1dde3f069f233b20e090 Mon Sep 17 00:00:00 2001 From: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Date: Sun, 5 May 2024 19:14:27 +0200 Subject: Ch10 Evaluator (#77) * Update graph evaluator for ch10 * Update tests to use the new evaluator * Fix anti-dep issue * Fix anti-dep issue * Add comments to the scheduler * Use j.u.Stack and rename BuildBlock --- .../java/com/seaofnodes/simple/GraphEvaluator.java | 181 ------- .../java/com/seaofnodes/simple/Chapter08Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter09Test.java | 11 +- .../java/com/seaofnodes/simple/SchedulerTest.java | 74 +++ .../com/seaofnodes/simple/evaluator/Evaluator.java | 229 ++++++++ .../com/seaofnodes/simple/evaluator/Scheduler.java | 592 +++++++++++++++++++++ .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 42 +- 7 files changed, 931 insertions(+), 203 deletions(-) delete mode 100644 chapter10/src/main/java/com/seaofnodes/simple/GraphEvaluator.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/SchedulerTest.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java (limited to 'chapter10') diff --git a/chapter10/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/chapter10/src/main/java/com/seaofnodes/simple/GraphEvaluator.java deleted file mode 100644 index 9fc51c8e..00000000 --- a/chapter10/src/main/java/com/seaofnodes/simple/GraphEvaluator.java +++ /dev/null @@ -1,181 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeInteger; - -import java.util.Arrays; -import java.util.BitSet; -import java.util.HashMap; - -public class GraphEvaluator { - - public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT } - - public record Result(ResultType type, long value) {} - - /** - * 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 (node instanceof StartNode start) return start; - if( visit.get(node._nid) ) return null; - visit.set(node._nid); - for( Node def : node._inputs ) { - var res = findStart(visit,def); - if( res != null ) return res; - } - for( Node use : node._outputs ) { - var res = findStart(visit,use); - if( res != null ) return res; - } - return null; - } - - /** - * Find the control output from a control node - */ - private static Node findControl(Node control) { - for( Node use : control._outputs ) { - if (use.isCFG()) return use; - } - return null; - } - - /** - * Find the projection for a node - */ - private static ProjNode findProjection(Node node, int idx) { - for( Node use : node._outputs ) { - if (use instanceof ProjNode proj && proj._idx == idx) return proj; - } - return null; - } - - /** - * Cache values for phi and parameter projection nodes. - */ - private final HashMap cacheValues = new HashMap<>(); - /** - * Cache for loop phis as they can depend on itself or other loop phis - */ - private long[] loopPhiCache = new long[16]; - - private GraphEvaluator() { - } - - private long div(DivNode div) { - long in2 = getValue(div.in(2)); - return in2 == 0 ? 0 : getValue(div.in(1)) / in2; - } - - /** - * Calculate the value of a node - */ - private long getValue(Node node) { - var cache = cacheValues.get(node); - if (cache != null) return cache; - return switch (node) { - case ConstantNode cons -> ((TypeInteger)cons.compute()).value(); - case AddNode add -> getValue(add.in(1)) + getValue(add.in(2)); - case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0; - case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0; - case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0; - case DivNode div -> div(div); - case MinusNode minus -> -getValue(minus.in(1)); - case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2)); - case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0; - case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2)); - default -> throw Utils.TODO("Unexpected node " + node); - }; - } - - /** - * Special case of latchPhis when phis can depend on phis of the same region. - */ - private void latchLoopPhis(RegionNode region, Node prev) { - int idx = Utils.find(region._inputs, prev); - assert idx > 0; - int i = 0; - for( Node use : region._outputs ) { - if (use instanceof PhiNode phi) { - var value = getValue(phi.in(idx)); - if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2); - loopPhiCache[i++] = value; - } - } - i = 0; - for( Node use : region._outputs ) { - if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]); - } - } - - /** - * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region. - */ - private void latchPhis(RegionNode region, Node prev) { - int idx = Utils.find(region._inputs, prev); - assert idx > 0; - for( Node use : region._outputs ) { - if (use instanceof PhiNode phi) { - var value = getValue(phi.in(idx)); - cacheValues.put(phi, value); - } - } - } - - /** - * Run the graph until either a return is found or the number of loop iterations are done. - */ - private Result evaluate(StartNode start, long parameter, int loops) { - var parameter1 = findProjection(start, 1); - if (parameter1 != null) cacheValues.put(parameter1, parameter); - Node control = findProjection(start, 0); - Node prev = start; - while (control != null) { - Node next; - switch (control) { - case RegionNode region -> { - if (region instanceof LoopNode && region.in(1) != prev) { - if (loops--<=0) return new Result(ResultType.TIMEOUT, 0); - latchLoopPhis(region, prev); - } else { - latchPhis(region, prev); - } - next = findControl(region); - } - case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1); - case ReturnNode ret -> { - return new Result(ResultType.VALUE, getValue(ret.in(1))); - } - case ProjNode ignored -> next = findControl(control); - default -> throw Utils.TODO("Unexpected control node " + control); - } - prev = control; - control = next; - } - return new Result(ResultType.FALLTHROUGH, 0); - } - - public static long evaluate(Node graph) { - return evaluate(graph, 0); - } - - public static long evaluate(Node graph, long parameter) { - return evaluate(graph, parameter, 1000); - } - - public static long evaluate(Node graph, long parameter, int loops) { - var res = evaluateWithResult(graph, parameter, loops); - if (res.type== ResultType.TIMEOUT) throw new RuntimeException("Timeout"); - return res.value; - } - - public static Result evaluateWithResult(Node graph, long parameter, int loops) { - var start = findStart(new BitSet(), graph); - if (start == null) return new Result(ResultType.TIMEOUT, 0); - var evaluator = new GraphEvaluator(); - return evaluator.evaluate(start, parameter, loops); - } - -} 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 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 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 + *
+ * This scheduler is used for tests and is not the final scheduler. + *
+ *
+ * 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. + *
+ * 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 if 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. + *
+ *
+ * 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 a.depth < b.depth 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 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 data = new IdentityHashMap<>(); + /** + * List of nodes which can be placed since all users are placed. + */ + private final Stack 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 + * Optional.empty() for null or dead nodes. + */ + Optional 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 a and b + * @param a Block a + * @param b Block b + * @return The dominator of a and b + */ + 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{ + // 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; id.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 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; iupdate(d(in), d.block)); + } + } + } + + /** + * Build the control flow graph. + * @param start The start node. + */ + private void doBuildCTF(StartNode start) { + var queue = new Stack(); + var phiQueue = new Stack(); + 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(); + for(int i=1; iprev.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 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(); + var dataQueue = new Stack(); + var mem = new Stack(); + 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; id.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(); + var queue = new Stack(); + 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(); + 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