From 2d80a348bad4b1e3165bd955ceaff3e18a96e516 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 25 Oct 2026 14:20:11 -0700 Subject: Retire Evalutator Minor rounding bug in eval2 --- chapter18/README.ja.md | 2 +- chapter18/README.md | 4 +- .../java/com/seaofnodes/simple/BrainFuckTest.java | 1 - .../java/com/seaofnodes/simple/Chapter08Test.java | 1 - .../java/com/seaofnodes/simple/Chapter09Test.java | 1 - .../com/seaofnodes/simple/Chapter14FloatTest.java | 1 - .../java/com/seaofnodes/simple/Chapter16Test.java | 1 - .../java/com/seaofnodes/simple/Chapter17aTest.java | 1 - .../java/com/seaofnodes/simple/SchedulerTest.java | 23 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 378 ------------- .../com/seaofnodes/simple/evaluator/Scheduler.java | 606 --------------------- 11 files changed, 9 insertions(+), 1010 deletions(-) delete mode 100644 chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java delete mode 100644 chapter18/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java (limited to 'chapter18') diff --git a/chapter18/README.ja.md b/chapter18/README.ja.md index e8025c92..b4f122e7 100644 --- a/chapter18/README.ja.md +++ b/chapter18/README.ja.md @@ -221,6 +221,6 @@ code.driver(CodeGen.Phase.LocalSched); その後 [ListScheduler](src/main/java/com/seaofnodes/simple/ListScheduler.java) が各ブロックを順序付けます。未スケジュールの局所依存を数え、準備のできた演算を選び、依存が満たされるにつれてそのユーザーを準備済みにします。Phi は入口に、制御移動は出口に属します。ここには機械のタイミングモデルがなく、さまざまな改善の余地がありますが、この章の範囲外です。目標は、引き続き合法な実行順序です。 -[Eval2](src/test/java/com/seaofnodes/simple/Eval2.java) はそのスケジュールを実行し、IR の演算を、無制限の値スロットを持つ命令として扱います。各呼び出しには独自のフレームがあるため、同じノードの再帰的な呼び出しも異なる値を保持します。呼び出し時には、呼び出し元のフレームと復帰地点を保存し、呼び出される側のフレームを作り、選ばれた関数に移ります。return 時には呼び出し元を復元し、その CallEnd に値を渡します。Region では、結果を代入する前に、選ばれたすべての Phi 入力を読みます。そのため並列代入は正しさを保ちます。 +[Eval2](src/test/java/com/seaofnodes/simple/Eval2.java) は、この章から以前の `Evaluator` とその専用テストスケジューラを置き換えます。コンパイラが作ったスケジュールを実行し、IR の演算を、無制限の値スロットを持つ命令として扱います。各呼び出しには独自のフレームがあるため、同じノードの再帰的な呼び出しも異なる値を保持します。呼び出し時には、呼び出し元のフレームと復帰地点を保存し、呼び出される側のフレームを作り、選ばれた関数に移ります。return 時には呼び出し元を復元し、その CallEnd に値を渡します。Region では、結果を代入する前に、選ばれたすべての Phi 入力を読みます。そのため並列代入は正しさを保ちます。 これでスケジュールされた関数からなる実行可能なプログラムができましたが、演算はまだ機械に依存しません。[第19章](../chapter19/README.ja.md)では、スケジューリング前に命令選択を挿入します。これらの理想的な演算は、選んだ CPU のレジスタ制約と呼び出し規約を持つ命令になります。 diff --git a/chapter18/README.md b/chapter18/README.md index 1094209b..9e7aa84a 100644 --- a/chapter18/README.md +++ b/chapter18/README.md @@ -363,7 +363,9 @@ belong at entry and control transfers at exit. There is room for all sorts of improvements - there is no machine timing model here, but this is out of scope for this chapter. The goal remains a legal execution order. -[Eval2](src/test/java/com/seaofnodes/simple/Eval2.java) executes that schedule, +[Eval2](src/test/java/com/seaofnodes/simple/Eval2.java) replaces the earlier +`Evaluator` and its separate test scheduler starting in this chapter. It executes +the compiler's schedule, treating IR operations as instructions with an unlimited supply of value slots. Each invocation has its own frame, so recursive invocations of the same nodes keep distinct values. At a call it saves the caller's frame and return diff --git a/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 43314312..72e5412c 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import java.nio.charset.StandardCharsets; import org.junit.Test; import static org.junit.Assert.assertEquals; diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 379bb55b..7919e3a3 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -1,6 +1,5 @@ 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; diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 410e32cd..d6ced4e0 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index 473a06fa..f6c79c2f 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Ignore; import org.junit.Test; diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java index d2ef9357..beb1f464 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Ignore; import org.junit.Test; diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17aTest.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17aTest.java index 52f20ace..cc3ba810 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17aTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17aTest.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; import static org.junit.Assert.assertEquals; diff --git a/chapter18/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter18/src/test/java/com/seaofnodes/simple/SchedulerTest.java index 95c062b5..c9c3e2ec 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -1,8 +1,5 @@ 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; @@ -30,13 +27,6 @@ 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() { @@ -51,8 +41,7 @@ if (arg) v.f=1; return i; """); code.parse();//.iter(); - var eval = new Evaluator(code._stop); - assertEquals(2L, eval.evaluate(1, 10)); + assertEquals("2", Eval2.eval(code, 1, 10)); } @Test @@ -66,9 +55,8 @@ if(arg) v0.f=1; return v0; """); code.parse().iter(); - var eval = new Evaluator(code._stop); - assertObj(eval.evaluate(0, 10), "S", 0L); - assertObj(eval.evaluate(1, 10), "S", 1L); + assertEquals("S{f=0}", Eval2.eval(code, 0, 10)); + assertEquals("S{f=1}", Eval2.eval(code, 1, 10)); } @Test @@ -85,9 +73,8 @@ if (arg) v.f=1; return i; """); code.parse().iter(); - var eval = new Evaluator(code._stop); - assertEquals(2L, eval.evaluate(0, 10)); - assertEquals(2L, eval.evaluate(1, 10)); + assertEquals("2", Eval2.eval(code, 0, 10)); + assertEquals("2", Eval2.eval(code, 1, 10)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java deleted file mode 100644 index 7dbc551e..00000000 --- a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ /dev/null @@ -1,378 +0,0 @@ -package com.seaofnodes.simple.evaluator; - -import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.*; - -import java.util.*; - -public class Evaluator { - - private static final Object MEMORY = new Object(); - - public record Obj(TypeStruct struct, Object[] fields) { - private void init(IdentityHashMap objs) { - var oid = objs.get(this); - if (oid != null) { - if (oid != 0) objs.put(this, 0); - return; - } - objs.put(this, -1); - for (var obj : fields) { - if (obj instanceof Obj o) o.init(objs); - } - } - private static int p(StringBuilder sb, IdentityHashMap objs, int id, String indentation, String step, String sep, Object obj) { - if (obj instanceof Obj o) return o.p(sb, objs, id, indentation, step, sep); - sb.append(obj); - return id; - } - private int p(StringBuilder sb, IdentityHashMap objs, int id, String indentation, String step, String sep) { - var cid = objs.get(this); - assert cid != null; - if (cid > 0) { - sb.append("obj@").append(cid); - return id; - } - if (struct._name.equals("[u8]")) { - sb.append('"'); - for (int i=struct._fields.length-1; i= 0x20 && n < 0x80) { - if (n == 0x22 || n == 0x5C) sb.append("\\"); - sb.append((char)n); - } else { - sb.append("\\x").append("0123456789abcdef".charAt(n >> 4)).append("0123456789abcdef".charAt(n & 0xF)); - } - } - sb.append('"'); - return id; - } - sb.append("Obj<").append(struct._name).append(">"); - if (cid == 0) { - cid = id++; - objs.put(this, cid); - sb.append("@").append(cid); - } - sb.append("{"); - if (struct._fields.length == 0) { - assert !struct.isAry(); - sb.append("}"); - return id; - } - String nextIndent = indentation + step; - int e = struct._fields.length - 1; - for(int i=0; i e) { - String innerIndent = nextIndent + step; - sb.append(innerIndent); - id = p(sb, objs, id, nextIndent, step, sep, fields[e]); - for (int i = e+1; i < fields.length; i++) { - sb.append(sep).append(innerIndent); - id = p(sb, objs, id, nextIndent, step, sep, fields[i]); - } - sb.append(nextIndent); - } - sb.append("]"); - } else { - id = p(sb, objs, id, nextIndent, step, sep, fields[e]); - } - sb.append(indentation).append("}"); - return id; - } - private StringBuilder p(StringBuilder sb, String indentation, String step, String sep) { - var objs = new IdentityHashMap(); - init(objs); - p(sb, objs, 1, indentation, step, sep); - return sb; - } - @Override - public String toString() { - if (struct._name.equals("[u8]")) { - var sb = new StringBuilder(); - for (int i=struct._fields.length-1; i= 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 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 double div(DivFNode div) { - double in2 = vald(div.in(2)); - return in2 == 0 ? 0 : vald(div.in(1)) / in2; - } - - private static long offToIdx(long off, TypeStruct t) { - off -= t.aryBase(); - int scale = t.aryScale(); - long mask = (1L << scale)-1; - assert (off & mask) == 0; - return off>>scale; - } - - private Object alloc(NewNode alloc) { - TypeStruct type = alloc._ptr._obj; - Object[] body=null; - int num; - if( type.isAry() ) { - long sz = (Long)val(alloc.size()); - long n = offToIdx(sz, type); - if( n < 0 ) - throw new NegativeArraySizeException(""+n); - body = new Object[(int)n+1]; // Array body - var elem = type._fields[1]._type; - if (elem instanceof TypeInteger) { - for (int i=0; i= len ) - throw new ArrayIndexOutOfBoundsException("Array index out of bounds " + i + " < " + len); - return from.fields[(int)i+from.struct._fields.length-1]; - - } else - return from.fields[idx]; - } - - private Object store(StoreNode store) { - var to = (Obj)val(store.ptr()); - var off = vall(store.off()); - var val = val(store.val()); - var idx = getFieldIndex(to.struct, store, (Long)off); - if( idx==to.struct._fields.length-1 && to.struct.isAry() ) { - long len = to.fields.length - to.struct._fields.length + 1; - long i = offToIdx(off, to.struct); - if( i < 0 || i >= len ) - throw new RuntimeException("Array index out of bounds " + off + " <= " + len); - to.fields[(int)i+to.struct._fields.length-1] = val; - } else - 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 double vald(Node node) { - var v = val(node); - if (v instanceof Number n) return n.doubleValue(); - if( v == null ) return 0; - throw new AssertionError("Not a double " + v); - } - - private Object cons(ConstantNode cons) { - var type = cons.compute(); - if (type instanceof TypeInteger i) return i.isConstant() ? i.value() : Integer.MAX_VALUE; - if (type instanceof TypeFloat i) return i.value(); - 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 AddFNode add -> vald(add.in(1)) + vald(add.in(2)); - case BoolNode.EQF eq -> vald(eq.in(1)) == vald(eq.in(2)) ? 1L : 0L; - case BoolNode.LEF le -> vald(le.in(1)) <= vald(le.in(2)) ? 1L : 0L; - case BoolNode.LTF lt -> vald(lt.in(1)) < vald(lt.in(2)) ? 1L : 0L; - 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 DivFNode div -> div(div); - case MinusNode minus -> -vall(minus.in(1)); - case MinusFNode minus -> -vald(minus.in(1)); - case MulNode mul -> vall(mul.in(1)) * vall(mul.in(2)); - case MulFNode mul -> vald(mul.in(1)) * vald(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 SubFNode sub -> vald(sub.in(1)) - vald(sub.in(2)); - case ShlNode shl -> vall(shl.in(1)) << vall(shl.in(2)); - case ShrNode shr -> vall(shr.in(1)) >>> vall(shr.in(2)); - case SarNode sar -> vall(sar.in(1)) >> vall(sar.in(2)); - case AndNode and -> vall(and.in(1)) & vall(and.in(2)); - case OrNode or -> vall(or .in(1)) | vall(or .in(2)); - case XorNode xor -> vall(xor.in(1)) ^ vall(xor.in(2)); - case CastNode cast -> val(cast.in(1)); - case RoundF32Node rnd -> (double)(float)vald(rnd.in(1)); - case ToIntegerNode cvt -> (long)vald(cvt.in(1)); - case ToFloatNode cast -> (double)vall(cast.in(1)); - case LoadNode load -> load(load); - case StoreNode store -> store(store); - case NewNode alloc -> alloc(alloc); - case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; - case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; - case MemMergeNode mem -> null; - case ReadOnlyNode ro -> val(ro.in(1)); - case CallNode call -> Utils.TODO(); // should not reach here, go the IfNode route - 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] = MEMORY; - s[2] = parameter; - values[start._nid] = s; - int i=0; - Scheduler.Block block = this.startBlock; - for(;;) { - for(; i 0 && region.nIns() > exit; - block = block.next()[0]; - assert block != null; - for (; i < block.nodes().length; i++) { - if (!(block.nodes()[i] instanceof PhiNode phi)) break; - var val = region instanceof FunNode fun && "main".equals(fun.sig()._name) && ((ParmNode)phi)._idx==2 && exit==1 - ? parameter - : val(phi.in(exit)); - phiCache.add(val); - } - 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; - } - BasicBlock(Node entry, BasicBlock prev) { - this(entry,prev.depth+1,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) && !(node instanceof XCtrlNode); - } - - /** - * 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 if (node instanceof XCtrlNode) { - 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)); - while (!queue.isEmpty()) { - var data = queue.pop(); - var node = data.node; - assert node instanceof CFGNode; - BasicBlock block = switch (node) { - case StartNode s -> new BasicBlock(s, 0); - case LoopNode l -> new BasicBlock(l, d(l.in(1)).block); - case RegionNode r -> { - var prev = new ArrayList(); - int depth = 0; - for(int i=1; i d(i.in(0)).block; - case ReturnNode ret -> d(ret .in(0)).block; - case CallNode call -> throw Utils.TODO(); - default -> new BasicBlock(node, 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 FunNode fun ) { - // Cannot find CFG user from fun via a naive search, because always find - // Return but Return is not always the one CFG user. - CFGNode n = fun.uctrl(); - assert isCFGNodeReady(n) && d(n).block==null; - queue.push(d(n)); - } else if( !(node instanceof ReturnNode) ) { - for (Node n : node._outputs) - if(n instanceof CFGNode && 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 instanceof CFGNode == 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 instanceof CFGNode; - if (!(node instanceof ReturnNode) ) { - for (var out : node._outputs) if (out!=null && out instanceof CFGNode && isNotXCtrl(out)) markAlive(cfgQueue, out, true); - } - for (var in : node._inputs) if(in!=null && !(in instanceof CFGNode) && isNotXCtrl(in)) markAlive(dataQueue, in, false); - } - // Mark all other nodes. - while (!dataQueue.isEmpty()) { - var data = dataQueue.pop(); - node = data.node; - assert !(node instanceof CFGNode); - 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 CFGNode findSingleCFGOut(Node node) { - if (node instanceof StartNode) { - for(var n:node._outputs) - if (n instanceof FunNode fun && "main".equals(fun.sig()._name) ) - return fun; - return null; - } - if( node instanceof FunNode fun ) return fun.uctrl(); - assert node._outputs.stream().filter(x -> x instanceof CFGNode).limit(2).count()<=1; - for(var n:node._outputs) if(n instanceof CFGNode cfg) return cfg; - 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 instanceof CFGNode && 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, r._inputs.find(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 CProjNode 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); - } - -} -- cgit v1.2.3