Retire Evalutator

Minor rounding bug in eval2

5 files changed, 49 insertions, 1004 deletions

diff --git a/chapter27/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter27/src/test/java/com/seaofnodes/simple/Chapter19Test.java
index 337dbc62..b0dce8ef 100644
--- a/chapter27/src/test/java/com/seaofnodes/simple/Chapter19Test.java
+++ b/chapter27/src/test/java/com/seaofnodes/simple/Chapter19Test.java
@@ -13,6 +13,42 @@ import org.junit.Test;
 import static org.junit.Assert.*;
 
 public class Chapter19Test {
+    @Test public void testNarrowStores() {
+        // Return the allocation so Load forwarding cannot hide a bad Store.
+        for( String type : new String[]{"u8","i8","u16","i16","u32","i32","int","f32","flt"} ) {
+            boolean flt = type.equals("f32") || type.equals("flt");
+            String init = flt ? "flt v=arg; " : "";
+            if( type.equals("f32") ) init+="f32 w=v; ";
+            String value = type.equals("f32") ? "w" : flt ? "v" : "arg";
+            for( boolean array : new boolean[]{false,true} ) {
+                String src = array
+                    ? "var a=new "+type+"[1]; a[0]="+value+"; return a;"
+                    : "struct S { "+type+" x; }; var s=new S; s.x="+value+"; return s;";
+                CodeGen code = new CodeGen(init+src).driver(CodeGen.Phase.TypeCheck);
+                long[] args = flt ? new long[]{0,1,-1,16777217,-16777217}
+                    : new long[]{0,1,-1,0x180,0x18000,0x180000000L,Long.MIN_VALUE,Long.MAX_VALUE};
+                for( long arg : args ) {
+                    Object expected = switch( type ) {
+                    case "u8"  -> arg & 0xffL;
+                    case "i8"  -> (long)(byte)arg;
+                    case "u16" -> arg & 0xffffL;
+                    case "i16" -> (long)(short)arg;
+                    case "u32" -> arg & 0xffffffffL;
+                    case "i32" -> (long)(int)arg;
+                    case "f32" -> (double)(float)arg;
+                    case "flt" -> (double)arg;
+                    default    -> arg;
+                    };
+                    String msg = type+" array="+array+" arg="+arg;
+                    String printed = array
+                        ? (type.equals("u8") ? ""+(char)(long)(Long)expected : (type.equals("int") ? "i64" : type)+"[ "+expected+"]")
+                        : "S{x="+expected+"}";
+                    assertEquals(msg,printed,Eval2.eval(code,arg));
+                }
+            }
+        }
+    }
+
     @Test public void testPrintingFunctionLookup() {
         var code = new CodeGen("return 0;").parse();
         var tfp = TypeFunPtr.make((byte)2,false,new Type[]{TypeInteger.constant(987654)},TypeInteger.constant(123456),XInt.make(1000));
diff --git a/chapter27/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter27/src/test/java/com/seaofnodes/simple/Eval2.java
index b32a5175..abfe8133 100644
--- a/chapter27/src/test/java/com/seaofnodes/simple/Eval2.java
+++ b/chapter27/src/test/java/com/seaofnodes/simple/Eval2.java
@@ -410,6 +410,14 @@ public abstract class Eval2 {
             ? offToIdx(x(st.off()),tmp._obj)
             : tmp._obj.find(st._name);
         Object val = val(st.val());
+        // Idealization can remove conversions already performed by the store.
+        Type type = st._declaredType;
+        if( type instanceof TypeInteger ti ) {
+            int shift = 64-(8 << type.log_size());
+            long x = (Long)val << shift;
+            val = ti._min < 0 ? x >> shift : x >>> shift;
+        } else if( type instanceof TypeFloat && type.log_size()==2 )
+            val = (double)(float)(double)(Double)val;
         fs[idx] = val;
         return "$mem";
     }
diff --git a/chapter27/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter27/src/test/java/com/seaofnodes/simple/SchedulerTest.java
index 6156700d..ab6e81eb 100644
--- a/chapter27/src/test/java/com/seaofnodes/simple/SchedulerTest.java
+++ b/chapter27/src/test/java/com/seaofnodes/simple/SchedulerTest.java
@@ -1,9 +1,6 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.codegen.CodeGen;
-import com.seaofnodes.simple.evaluator.Evaluator;
-import com.seaofnodes.simple.node.StopNode;
-import org.junit.Assert;
 import org.junit.Ignore;
 import org.junit.Test;
 
@@ -31,13 +28,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() {
@@ -52,8 +42,7 @@ if (arg) v.f=1;
 return i;
 """);
         code.parse();//.iter().opto().iterPostOpto().finalizeIR();
-        var eval = new Evaluator(code._stop);
-        assertEquals(2L, eval.evaluate(1, 10));
+        assertEquals("2", Eval2.eval(code, 1, 10));
     }
 
     @Test
@@ -67,9 +56,8 @@ if(arg) v0.f=1;
 return v0;
 """);
         code.driver(CodeGen.Phase.FinalizeIR);
-        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
@@ -86,9 +74,8 @@ if (arg) v.f=1;
 return i;
 """);
         code.driver(CodeGen.Phase.FinalizeIR);
-        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/chapter27/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter27/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
deleted file mode 100644
index 3f4613ff..00000000
--- a/chapter27/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ /dev/null
@@ -1,381 +0,0 @@
-package com.seaofnodes.simple.evaluator;
-
-import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.*;
-import com.seaofnodes.simple.util.Utils;
-import java.util.*;
-
-public class Evaluator {
-
-    private static final Object MEMORY = new Object();
-
-    public record Obj(TypeStruct struct, Object[] fields) {
-        private void init(IdentityHashMap<Obj, Integer> 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<Obj, Integer> 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<Obj, Integer> 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<fields.length; i++) {
-                    var v = fields[i];
-                    if (v == null) v = 0;
-                    assert v instanceof Number;
-                    var n = ((Number)v).byteValue() & 0xFF;
-                    if (n >= 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; i++) {
-                sb.append(nextIndent).append(struct._fields[i]._fname).append("=");
-                id = p(sb, objs, id, nextIndent, step, sep, fields[i]);
-                sb.append(sep);
-            }
-            sb.append(nextIndent).append(struct._fields[e]._fname).append("=");
-            if (struct.isAry()) {
-                sb.append("[");
-                if (fields.length > 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<Obj, Integer>();
-            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<fields.length; i++) {
-                    var v = fields[i];
-                    if (v == null) v = 0;
-                    assert v instanceof Number;
-                    var n = ((Number)v).byteValue() & 0xFF;
-                    sb.append((char)n);
-                }
-                return sb.toString();
-            }
-            return p(new StringBuilder(), "", "", ",").toString();
-        }
-        public String pretty() {
-            return p(new StringBuilder(), "\n", "  ", "").toString();
-        }
-    }
-
-    private static int getFieldIndex(TypeStruct struct, MemOpNode memop, long off) {
-        int idx = struct.find(memop._name);
-        if( idx >= 0 ) return idx;
-        throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name);
-    }
-
-    public enum Status {
-        TIMEOUT,
-        FALLTHROUGH
-    }
-
-    /**
-     * Find the start node from some node in the graph or null if there is no start node
-     */
-    private static StartNode findStart(BitSet visit, Node node) {
-        if (node == null) return null;
-        if( visit.get(node._nid) ) return null;
-        visit.set(node._nid);
-        StartNode start = node instanceof StartNode ? (StartNode) node : null;
-        for( Node def : node._inputs ) {
-            var res = findStart(visit,def);
-            if( res != null ) start = res;
-        }
-        for( Node use : node._outputs ) {
-            var res = findStart(visit,use);
-            if( res != null ) start = res;
-        }
-        return start;
-    }
-
-    private final Object[] values;
-    private final ArrayList<Object> phiCache = new ArrayList<>();
-    private final StartNode start;
-    private final Scheduler.Block startBlock;
-
-    public Evaluator(Node graph) {
-        var visited = new BitSet();
-        this.start = findStart(visited, graph);
-        if (this.start == null) {
-            this.values = null;
-            this.startBlock = null;
-            return;
-        }
-        this.startBlock = Scheduler.schedule(this.start);
-        this.values = new Object[visited.length()];
-    }
-
-    private long div(DivNode div) {
-        long in2 = vall(div.in(2));
-        return in2 == 0 ? 0 : vall(div.in(1)) / in2;
-    }
-    private 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]._t;
-            if (elem instanceof TypeInteger) {
-                for (int i=0; i<n; i++) body[i+1] = 0L;
-            } else if (elem instanceof TypeFloat) {
-                for (int i = 0; i < n; i++) body[i+1] = 0D;
-            } else {
-                assert elem instanceof TypeMemPtr;
-            }
-            // Length value
-            body[0] = n;
-        } else {
-            body = new Object[num = type._fields.length];
-            for( int i=0; i<num; i++ )
-                body[i] = switch( alloc._ptr._obj._fields[i]._t ) {
-                case TypeInteger ti -> 0L;
-                case TypeFloat tf -> 0D;
-                default -> null;
-                };
-        }
-        return new Object[]{new Obj(type,body),null};
-    }
-
-    private Object load(LoadNode load) {
-        var from = (Obj)val(load.ptr());
-        var off = vall(load.off());
-        var idx = getFieldIndex(from.struct, load, (Long)off);
-        if( idx==from.struct._fields.length-1 && from.struct.isAry() ) {
-            long len = from.fields.length - from.struct._fields.length + 1;
-            long i = offToIdx(off, from.struct);
-            if( 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 EscapeNode esc -> null;
-            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<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 .expr());
-            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 phi)) break;
-                    var val = region instanceof FunNode fun && "main".equals(fun._name) && ((ParmNode)phi)._idx==2 && exit==1
-                            ? parameter
-                            : val(phi.in(exit));
-                    phiCache.add(val);
-                }
-                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/chapter27/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter27/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
deleted file mode 100644
index c837bd6f..00000000
--- a/chapter27/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
+++ /dev/null
@@ -1,605 +0,0 @@
-package com.seaofnodes.simple.evaluator;
-
-import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.util.Utils;
-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;
-        }
-        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<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) && !(node instanceof XCtrlNode);
-    }
-
-    /**
-     * 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 instanceof CFGNode || 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 MemOpNode l && l._isLoad) {
-                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 = data.node.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 MemOpNode ld && ld._isLoad)) {
-                        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 MemOpNode s && !s._isLoad) {
-                // Store nodes have anti-deps to load nodes.
-                // So decrease the uses of these loads when the store is placed.
-                for (var out: ((Node)s).in(1)._outputs) {
-                    if (out instanceof MemOpNode ld && ld._isLoad) 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 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<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));
-        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<BasicBlock>();
-                    int depth = 0;
-                    for(int i=1; i<r.nIns(); i++) {
-                        if( !od(r.in(i)).isPresent() ) continue;
-                        BasicBlock bb = d(r.in(i)).block;
-                        prev.add(bb);
-                        depth = Math.max(depth,bb.depth);
-                    }
-                    yield new BasicBlock(r, depth+1, prev.toArray(BasicBlock[]::new));
-            }
-            case IfNode 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<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 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<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 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; 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 instanceof CFGNode)) markAlive(dataQueue, in, false);
-            }
-            if (node instanceof MemOpNode s && !s._isLoad) 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 MemOpNode ld && ld._isLoad) 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 CFGNode findSingleCFGOut(Node node) {
-        if (node instanceof StartNode) {
-            for(var n:node._outputs)
-                if (n instanceof FunNode fun && "main".equals(fun._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<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 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 Block schedule(StartNode start) {
-        var scheduler = new Scheduler();
-        scheduler.doMarkAlive(start);
-        scheduler.doBuildCTF(start);
-        scheduler.doSchedule();
-        return scheduler.build(start);
-    }
-
-}