Chapter 11: Global Code Motionlinear-chapter11

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

29 files changed, 740 insertions, 139 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
new file mode 100644
index 00000000..14540d46
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -0,0 +1,238 @@
+ package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+import java.util.*;
+
+public abstract class GlobalCodeMotion {
+
+    // Arrange that the existing isCFG() Nodes form a valid CFG.  The
+    // Node.use(0) is always a block tail (either IfNode or head of the
+    // following block).  There are no unreachable infinite loops.
+    public static void buildCFG( StopNode stop ) {
+        fixLoops(stop);
+        schedEarly();
+        Parser.SCHEDULED = true;
+        schedLate(Parser.START);
+    }
+
+    // ------------------------------------------------------------------------
+    // Backwards walk on the CFG only, looking for unreachable code - which has
+    // to be an infinite loop.  Insert a bogus never-taken exit to Stop, so the
+    // loop becomes reachable.  Also, set loop nesting depth
+    private static void fixLoops(StopNode stop) {
+        // Backwards walk from Stop, looking for unreachable code
+        BitSet visit = new BitSet();
+        HashSet<CFGNode> unreach = new HashSet<>();
+        unreach.add(Parser.START);
+        for( Node ret : stop._inputs )
+            ((ReturnNode)ret).walkUnreach(visit,unreach);
+        if( unreach.isEmpty() ) return;
+
+        // Forwards walk from unreachable, looking for loops with no exit test.
+        visit.clear();
+        for( CFGNode cfg : unreach )
+            walkInfinite(cfg,visit,stop);
+        // Set loop depth on remaining graph
+        unreach.clear();
+        visit.clear();
+        for( Node ret : stop._inputs )
+            ((ReturnNode)ret).walkUnreach(visit,unreach);
+        assert unreach.isEmpty();
+    }
+
+
+    // Forwards walk over previously unreachable, looking for loops with no
+    // exit test.
+    static private void walkInfinite( CFGNode n, BitSet visit, StopNode stop ) {
+        if( visit.get(n._nid) ) return; // Been there, done that
+        visit.set(n._nid);
+        if( n instanceof LoopNode loop )
+            loop.forceExit(stop);
+        for( Node use : n._outputs )
+            if( use instanceof CFGNode cfg )
+                walkInfinite(cfg,visit,stop);
+    }
+
+    // ------------------------------------------------------------------------
+    private static void schedEarly() {
+        ArrayList<CFGNode> rpo = new ArrayList<>();
+        BitSet visit = new BitSet();
+        _rpo_cfg(Parser.START, visit, rpo);
+        // Reverse Post-Order on CFG
+        for( int j=rpo.size()-1; j>=0; j-- ) {
+            CFGNode cfg = rpo.get(j);
+            cfg.loopDepth();
+            for( Node n : cfg._inputs )
+                _schedEarly(n,visit);
+            // Strictly for dead infinite loops, we can have entire code blocks
+            // not reachable from below - so we reach down, from above, one
+            // step.  Since _schedEarly modifies the output arrays, the normal
+            // region._outputs ArrayList iterator throws CME.  The extra edges
+            // are always *added* after any Phis, so just walk the Phi prefix.
+            if( cfg instanceof RegionNode region ) {
+                int len = region.nOuts();
+                for( int i=0; i<len; i++ )
+                    if( region.out(i) instanceof PhiNode phi )
+                        _schedEarly(phi,visit);
+            }
+        }
+    }
+
+    // Post-Order of CFG
+    private static void _rpo_cfg(Node n, BitSet visit, ArrayList<CFGNode> rpo) {
+        if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) )
+            return;             // Been there, done that
+        visit.set(cfg._nid);
+        for( Node use : cfg._outputs )
+            _rpo_cfg(use,visit,rpo);
+        rpo.add(cfg);
+    }
+
+    private static void _schedEarly(Node n, BitSet visit) {
+        if( n==null || visit.get(n._nid) ) return; // Been there, done that
+        visit.set(n._nid);
+        // Schedule not-pinned not-CFG inputs before self.  Since skipping
+        // Pinned, this never walks the backedge of Phis (and thus spins around
+        // a data-only loop, eventually attempting relying on some pre-visited-
+        // not-post-visited data op with no scheduled control.
+        for( Node def : n._inputs )
+            if( def!=null && !def.isPinned() )
+                _schedEarly(def,visit);
+        // If not-pinned (e.g. constants, projections, phi) and not-CFG
+        if( !n.isPinned() ) {
+            // Schedule at deepest input
+            CFGNode early = Parser.START; // Maximally early, lowest idepth
+            for( int i=1; i<n.nIns(); i++ )
+                if( n.in(i).cfg0().idepth() > early.idepth() )
+                    early = n.in(i).cfg0(); // Latest/deepest input
+            n.setDef(0,early);              // First place this can go
+        }
+    }
+
+    // ------------------------------------------------------------------------
+    private static void schedLate(StartNode start) {
+        CFGNode[] late = new CFGNode[Node.UID()];
+        Node[] ns = new Node[Node.UID()];
+        _schedLate(start,ns,late);
+        for( int i=0; i<late.length; i++ )
+            if( ns[i] != null )
+                ns[i].setDef(0,late[i]);
+    }
+
+    // Forwards post-order pass.  Schedule all outputs first, then draw an
+    // idom-tree line from the LCA of uses to the early schedule.  Schedule is
+    // legal anywhere on this line; pick the most control-dependent (largest
+    // idepth) in the shallowest loop nest.
+    private static void _schedLate(Node n, Node[] ns, CFGNode[] late) {
+        if( late[n._nid]!=null ) return; // Been there, done that
+        // These I know the late schedule of, and need to set early for loops
+        if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0);
+        if( n instanceof PhiNode phi ) late[n._nid] = phi.region();
+
+        // Walk Stores before Loads, so we can get the anti-deps right
+        for( Node use : n._outputs )
+            if( isForwardsEdge(use,n) &&
+                use._type instanceof TypeMem )
+                _schedLate(use,ns,late);
+        // Walk everybody now
+        for( Node use : n._outputs )
+            if( isForwardsEdge(use,n) )
+                _schedLate(use,ns,late);
+        // Already implicitly scheduled
+        if( n.isPinned() ) return;
+        // Need to schedule n
+
+        // Walk uses, gathering the LCA (Least Common Ancestor) of uses
+        CFGNode early = (CFGNode)n.in(0);
+        assert early != null;
+        CFGNode lca = null;
+        for( Node use : n._outputs )
+            lca = use_block(n,use, late).idom(lca);
+
+        // Loads may need anti-dependencies, raising their LCA
+        if( n instanceof LoadNode load )
+            lca = find_anti_dep(lca,load,early,late);
+
+        // Walk up from the LCA to the early, looking for best place.  This is the
+        // lowest execution frequency, approximated by least loop depth and
+        // deepest control flow.
+        CFGNode best = lca;
+        lca = lca.idom();       // Already found best for starting LCA
+        for( ; lca != early.idom(); lca = lca.idom() )
+            if( better(lca,best) )
+                best = lca;
+        assert !(best instanceof IfNode);
+        ns  [n._nid] = n;
+        late[n._nid] = best;
+    }
+
+    // Block of use.  Normally from late[] schedule, except for Phis, which go
+    // to the matching Region input.
+    private static CFGNode use_block(Node n, Node use, CFGNode[] late) {
+        if( !(use instanceof PhiNode phi) )
+            return late[use._nid];
+        CFGNode found=null;
+        for( int i=1; i<phi.nIns(); i++ )
+            if( phi.in(i)==n )
+                if( found==null ) found = phi.region().cfg(i);
+                else Utils.TODO(); // Can be more than once
+        assert found!=null;
+        return found;
+    }
+
+
+    // Least loop depth first, then largest idepth
+    private static boolean better( CFGNode lca, CFGNode best ) {
+        return lca._loopDepth < best._loopDepth ||
+                (lca.idepth() > best.idepth() || best instanceof IfNode);
+    }
+
+    // Skip iteration if a backedge
+    private static boolean isForwardsEdge(Node use, Node def) {
+        return use != null && def != null &&
+            !(use.nIns()>2 && use.in(2)==def && (use instanceof LoopNode || (use instanceof PhiNode phi && phi.region() instanceof LoopNode)));
+    }
+
+    private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) {
+        // We could skip final-field loads here.
+        // Walk LCA->early, flagging Load's block location choices
+        for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() )
+            cfg._anti = load._nid;
+        // Walk load->mem uses, looking for Stores causing an anti-dep
+        for( Node mem : load.mem()._outputs ) {
+            switch( mem ) {
+            case StoreNode st:
+                lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st);
+                break;
+            case PhiNode phi:
+                // Repeat anti-dep for matching Phi inputs.
+                // No anti-dep edges but may raise the LCA.
+                for( int i=1; i<phi.nIns(); i++ )
+                    if( phi.in(i)==load.mem() )
+                        lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null);
+                break;
+            case LoadNode ld: break; // Loads do not cause anti-deps on other loads
+            case ReturnNode ret: break; // Load must already be ahead of Return
+            default: throw Utils.TODO();
+            }
+        }
+        return lca;
+    }
+
+    //
+    private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) {
+        // Walk store blocks "reach" from its scheduled location to its earliest
+        for( ; stblk != defblk.idom(); stblk = stblk.idom() ) {
+            // Store and Load overlap, need anti-dependence
+            if( stblk._anti==load._nid ) {
+                lca = stblk.idom(lca); // Raise Loads LCA
+                if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved,
+                    st.addDef(load);   // Add anti-dep as well
+                return lca;            // Cap this stores' anti-dep to here
+            }
+        }
+        return lca;
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index cfe6d5cc..604770a4 100644
--- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.node.*;
 
 import java.util.*;
@@ -27,7 +28,7 @@ public class GraphVisualizer {
         // nodes in the graph.
         Collection<Node> all = findAll(stop, scope);
         StringBuilder sb = new StringBuilder();
-        sb.append("digraph chapter10 {\n");
+        sb.append("digraph chapter11 {\n");
         sb.append("/*\n");
         sb.append(stop._src);
         sb.append("\n*/\n");
@@ -79,7 +80,7 @@ public class GraphVisualizer {
         // Just the Nodes first, in a cluster no edges
         sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
         for (Node n : all) {
-            if (n instanceof ProjNode || n instanceof ScopeNode)
+            if (n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL)
                 continue; // Do not emit, rolled into MultiNode or Scope cluster already
             if (_separateControlCluster && doCtrl && !n.isCFG()) continue;
             if (_separateControlCluster && !doCtrl && n.isCFG()) continue;
@@ -100,9 +101,16 @@ public class GraphVisualizer {
                             sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n");
                             sb.append("\t\t\t\t<TR>");
                         }
-                        sb.append("<TD PORT=\"p").append(proj._idx).append("\"");
-                        if (proj.isCFG()) sb.append(" BGCOLOR=\"yellow\"");
-                        sb.append(">").append(proj.glabel()).append("</TD>");
+                        sb.append("<TD PORT=\"p").append(proj._idx).append("\">").append(proj.glabel()).append("</TD>");
+                    }
+                    if (use instanceof CProjNode proj) {
+                        if (!doProjTable) {
+                            doProjTable = true;
+                            sb.append("<TD>").append("\n");
+                            sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n");
+                            sb.append("\t\t\t\t<TR>");
+                        }
+                        sb.append("<TD PORT=\"p").append(proj._idx).append("\" BGCOLOR=\"yellow\">").append(proj.glabel()).append("</TD>");
                     }
                 }
                 if (doProjTable) {
@@ -178,7 +186,7 @@ public class GraphVisualizer {
             // Do not display the Constant->Start edge;
             // ProjNodes handled by Multi;
             // ScopeNodes are done separately
-            if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode )
+            if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL )
                 continue;
             for( int i=0; i<n.nIns(); i++ ) {
                 Node def = n.in(i);
@@ -191,9 +199,12 @@ public class GraphVisualizer {
                 } else if( def != null ) {
                     // Most edges land here use->def
                     sb.append('\t').append(n.uniqueName()).append(" -> ");
-                    if( def instanceof ProjNode proj ) {
+                    if( def instanceof CProjNode proj ) {
                         String mname = proj.ctrl().uniqueName();
                         sb.append(mname).append(":p").append(proj._idx);
+                    } else if( def instanceof ProjNode proj ) {
+                        String mname = proj.in(0).uniqueName();
+                        sb.append(mname).append(":p").append(proj._idx);
                     } else sb.append(def.uniqueName());
                     // Number edges, so we can see how they track
                     sb.append("[taillabel=").append(i);
@@ -231,7 +242,7 @@ public class GraphVisualizer {
                   .append(scopeName).append(":")
                   .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted
                   .append(" -> ");
-                if( def instanceof ProjNode proj ) {
+                if( def instanceof CProjNode proj ) {
                     String mname = proj.ctrl().uniqueName();
                     sb.append(mname).append(":p").append(proj._idx);
                 } else sb.append(def.uniqueName());
diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java
index f08f3208..43c6c9f7 100644
--- a/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -1,11 +1,10 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.node.LoopNode;
-import com.seaofnodes.simple.node.Node;
-import com.seaofnodes.simple.node.ProjNode;
-
+import com.seaofnodes.simple.node.*;
+import java.lang.StringBuilder;
 import java.util.ArrayList;
 import java.util.BitSet;
+import java.util.HashMap;
 
 public class IRPrinter {
 
@@ -20,12 +19,12 @@ public class IRPrinter {
         }
         for( Node def : n._inputs )
             sb.append(def==null ? "____ " : "%4d ".formatted(def._nid));
-        for( int i = n._inputs.size(); i<3; i++ )
+        for( int i = n._inputs.size(); i<4; i++ )
             sb.append("     ");
         sb.append(" [[  ");
         for( Node use : n._outputs )
             sb.append(use==null ? "____ " : "%4d ".formatted(use._nid));
-        int lim = 5 - Math.max(n._inputs.size(),3);
+        int lim = 6 - Math.max(n._inputs.size(),4);
         for( int i = n._outputs.size(); i<lim; i++ )
             sb.append("     ");
         sb.append(" ]]  ");
@@ -68,7 +67,9 @@ public class IRPrinter {
     }
 
     public static String prettyPrint(Node node, int depth) {
-        return prettyPrint( node, depth, false );
+        return Parser.SCHEDULED
+            ? prettyPrintScheduled( node, depth, false )
+            : prettyPrint( node, depth, false );
     }
 
     // Another bulk pretty-printer.  Makes more effort at basic-block grouping.
@@ -185,4 +186,81 @@ public class IRPrinter {
             return false;
         }
     }
+
+    // Bulk pretty printer, knowing scheduling information is available
+    public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) {
+        // Backwards DFS walk to depth.
+        HashMap<Node,Integer> ds = new HashMap<>();
+        _walk(ds,node,depth);
+        // Print by block with least idepth
+        StringBuilder sb = new StringBuilder();
+        ArrayList<Node> bns = new ArrayList<>();
+        while( !ds.isEmpty() ) {
+            CFGNode blk = null;
+            for( Node n : ds.keySet() ) {
+                CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : (CFGNode)n.in(0);
+                if( blk==null || cfg.idepth() < blk.idepth() )
+                    blk = cfg;
+            }
+            ds.remove(blk);
+
+            // Print block header
+            sb.append("%-13.13s".formatted(label(blk)+":"));
+            sb.append( "     ".repeat(4) ).append(" [[  ");
+            if( blk instanceof RegionNode || blk instanceof StopNode )
+                for( int i=(blk instanceof StopNode ? 0 : 1); i<blk.nIns(); i++ )
+                    label(sb,blk.cfg(i));
+            else if( !(blk instanceof StartNode) )
+                label(sb,blk.cfg(0));
+            sb.append(" ]]  \n");
+
+            // Collect block contents that are in the depth limit
+            bns.clear();
+            int xd = Integer.MAX_VALUE;
+            for( Node use : blk._outputs ) {
+                Integer i = ds.get(use);
+                if( i!=null && !(use instanceof CFGNode cfg && cfg.blockHead()) ) {
+                    bns.add(use);
+                    xd = Math.min(xd,i);
+                }
+            }
+            // Print Phis up front, if any
+            for( int i=0; i<bns.size(); i++ )
+                if( bns.get(i) instanceof PhiNode phi )
+                    printLine( phi, sb, llvmFormat,bns,i--,ds);
+
+            // Print block contents in depth order, bumping depth until whole block printed
+            for( ; !bns.isEmpty(); xd++ )
+                for( int i=0; i<bns.size(); i++ )
+                    if( ds.get(bns.get(i))==xd )
+                        printLine( bns.get(i), sb, llvmFormat, bns, i--, ds );
+            sb.append("\n");
+        }
+        return sb.toString();
+    }
+
+    private static void _walk( HashMap<Node,Integer> ds, Node node, int d ) {
+        Integer nd = ds.get(node);
+        if( nd!=null && d <= nd ) return; // Been there, done that
+        ds.put(node,d);
+        if( d == 0 ) return;    // Depth cutoff
+        for( Node def : node._inputs )
+            if( def != null )
+                _walk(ds,def,d-1);
+    }
+
+    static String label( CFGNode blk ) {
+        if( blk instanceof StartNode ) return "START";
+        return (blk instanceof LoopNode ? "LOOP" : "L")+blk._nid;
+    }
+    static void label( StringBuilder sb, CFGNode blk ) {
+        if( !blk.blockHead() ) blk = blk.cfg(0);
+        sb.append( "%-9.9s ".formatted( label( blk ) ) );
+    }
+    static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList<Node> bns, int i, HashMap<Node,Integer> ds ) {
+        printLine( n, sb, llvmFormat );
+        Utils.del(bns,i);
+        ds.remove(n);
+    }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java
index 1cee1ccb..b2b76777 100644
--- a/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -94,6 +94,7 @@ public abstract class IterPeeps {
 
         if( show )
             System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null));
+        GlobalCodeMotion.buildCFG(stop);
         return stop;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index fc84c9d9..e367f499 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -23,8 +23,14 @@ public class Parser {
      */
     public static StartNode START;
 
+    public static ConstantNode ZERO;
+    public static XCtrlNode XCTRL;
+
     public StopNode STOP;
 
+    // Debugger Printing.
+    public static boolean SCHEDULED; // True if debug printer can use schedule info
+
     // The Lexer.  Thin wrapper over a byte[] buffer with a cursor.
     private final Lexer _lexer;
 
@@ -77,11 +83,14 @@ public class Parser {
         Node.reset();
         IterPeeps.reset();
         OBJS.clear();
+        SCHEDULED = false;
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
         _continueScope = _breakScope = null;
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
         STOP = new StopNode(source);
+        ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep();
+        XCTRL= new XCtrlNode().peephole().keep();
     }
 
     public Parser(String source) {
@@ -105,9 +114,11 @@ public class Parser {
         _xScopes.push(_scope);
         // Enter a new scope for the initial control and arguments
         _scope.push();
-        _scope.define(ScopeNode.CTRL, Type.CONTROL   , new ProjNode(START, 0, ScopeNode.CTRL).peephole());
-        _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 1, ScopeNode.ARG0).peephole());
+        _scope.define(ScopeNode.CTRL, Type.CONTROL   , new CProjNode(START, 0, ScopeNode.CTRL).peephole());
+        _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new  ProjNode(START, 1, ScopeNode.ARG0).peephole());
         parseBlock();
+        if( ctrl()._type==Type.CONTROL )
+            STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole());
         _scope.pop();
         _xScopes.pop();
         if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
@@ -236,8 +247,8 @@ public class Parser {
         // IfNode takes current control and predicate
         Node ifNode = new IfNode(ctrl(), pred).peephole();
         // Setup projection nodes
-        Node ifT = new ProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
-        Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole();
+        Node ifT = new CProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
+        Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole();
 
         // Clone the body Scope to create the break/exit Scope which accounts for any
         // side effects in the predicate.  The break/exit Scope will be the final
@@ -283,7 +294,7 @@ public class Parser {
 
     private ScopeNode jumpTo(ScopeNode toScope) {
         ScopeNode cur = _scope.dup();
-        ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope
+        ctrl(XCTRL); // Kill current scope
         // Prune nested lexical scopes that have depth > than the loop head
         // We use _breakScope as a proxy for the loop head scope to obtain the depth
         while( cur._scopes.size() > _breakScope._scopes.size() )
@@ -319,8 +330,8 @@ public class Parser {
         // IfNode takes current control and predicate
         Node ifNode = new IfNode(ctrl(), pred).peephole();
         // Setup projection nodes
-        Node ifT = new ProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
-        Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
+        Node ifT = new CProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
+        Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
         // In if true branch, the ifT proj node becomes the ctrl
         // But first clone the scope and set it as current
         int ndefs = _scope.nIns();
@@ -366,7 +377,7 @@ public class Parser {
     private Node parseReturn() {
         var expr = require(parseExpression(), ";");
         Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr, _scope).peephole());
-        ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control
+        ctrl(XCTRL);            // Kill control
         return ret;
     }
 
@@ -568,7 +579,7 @@ public class Parser {
         if( _lexer.isNumber() ) return parseIntegerLiteral();
         if( match("(") ) return require(parseExpression(), ")");
         if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole();
-        if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole();
+        if( matchx("false") ) return ZERO;
         if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole();
         if( matchx("new") ) {
             String structName = requireId();
@@ -586,12 +597,11 @@ public class Parser {
     /**
      * Return a NewNode but also generate instructions to initialize it.
      */
-    private Node newStruct( TypeStruct obj ) {
+    private Node newStruct(TypeStruct obj) {
         Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep();
-        Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole();
         int alias = START._aliasStarts.get(obj._name);
         for( Field field : obj._fields ) {
-            memAlias(alias, new StoreNode(field._fname, alias, memAlias(alias), n, initValue).peephole());
+            memAlias(alias, new StoreNode(field._fname, alias, ctrl(), memAlias(alias), n, ZERO).peephole());
             alias++;
         }
         return n.unkeep();
@@ -629,7 +639,7 @@ public class Parser {
             if( peek('=') ) _lexer._position--;
             else {
                 Node val = parseExpression();
-                memAlias(alias, new StoreNode(name, alias, memAlias(alias), expr, val).peephole());
+                memAlias(alias, new StoreNode(name, alias, ctrl(), memAlias(alias), expr, val).peephole());
                 return expr;        // "obj.a = expr" returns the expression while updating memory
             }
         }
@@ -740,7 +750,16 @@ public class Parser {
          * Return the next non-white-space character
          */
         private void skipWhiteSpace() {
-            while (isWhiteSpace()) _position++;
+            while( true ) {
+                if( isWhiteSpace() ) _position++;
+                // Skip // to end of line
+                else if( _position+2 < _input.length &&
+                         _input[_position  ] == '/' &&
+                         _input[_position+1] == '/') {
+                    _position += 2;
+                    while( !isEOF() && _input[_position] != '\n' ) _position++;
+                } else break;
+            }
         }
 
 
@@ -822,8 +841,9 @@ public class Parser {
             return new String(_input, start, --_position - start);
         }
 
+        //
         private boolean isPunctuation(char ch) {
-            return "=;[]<>(){}+-/*!".indexOf(ch) != -1;
+            return "=;[]<>()+-/*".indexOf(ch) != -1;
         }
 
         private String parsePunctuation() {
diff --git a/src/main/java/com/seaofnodes/simple/Utils.java b/src/main/java/com/seaofnodes/simple/Utils.java
index 4f2af769..f3ac25b1 100644
--- a/src/main/java/com/seaofnodes/simple/Utils.java
+++ b/src/main/java/com/seaofnodes/simple/Utils.java
@@ -55,11 +55,4 @@ public class Utils {
 
     // Fold a 64bit hash into 32 bits
     public static int fold( long x ) { return (int)((x>>32) ^ x); }
-
-    public static boolean eq(String s0, String s1) {
-        if( s0==s1 ) return true;
-        assert s0==s0.intern();
-        assert s1==s1.intern();
-        return false;
-    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java
new file mode 100644
index 00000000..b605071b
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -0,0 +1,92 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.Utils;
+
+import java.util.BitSet;
+import java.util.HashSet;
+import java.util.HashMap;
+
+/** Control Flow Graph Nodes
+ * <p>
+ *  CFG nodes have a immediate dominator depth (idepth) and a loop nesting
+ *  depth(loop_depth).
+ * <p>
+ *  idepth is computed lazily upon first request, and is valid even in the
+ *  Parser, and is used by peepholes during parsing and afterward.
+ * <p>
+ *  loop_depth is computed after optimization as part of scheduling.
+ *
+ */
+public abstract class CFGNode extends Node {
+
+    public CFGNode(Node... nodes) { super(nodes); }
+
+    @Override public boolean isCFG() { return true; }
+    @Override public boolean isPinned() { return true; }
+
+    public CFGNode cfg(int idx) { return (CFGNode)in(idx); }
+
+    // Block head is Start, Region, CProj, but not e.g. If, Return, Stop
+    public boolean blockHead() { return false; }
+
+    // Should be exactly 1 tail from a block head
+    public CFGNode blockTail() {
+        assert blockHead();
+        for( Node n : _outputs )
+            if( n instanceof CFGNode cfg )
+                return cfg;
+        return null;
+    }
+
+    // ------------------------------------------------------------------------
+    /**
+     * Immediate dominator tree depth, used to approximate a real IDOM during
+     * parsing where we do not have the whole program, and also peepholes
+     * change the CFG incrementally.
+     * <p>
+     * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
+     */
+    public int _idepth;
+    public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
+
+    // Return the immediate dominator of this Node and compute dom tree depth.
+    public CFGNode idom() { return cfg(0); }
+
+    // Return the LCA of two idoms
+    public CFGNode idom(CFGNode rhs) {
+        if( rhs==null ) return this;
+        CFGNode lhs = this;
+        while( lhs != rhs ) {
+            var comp = lhs.idepth() - rhs.idepth();
+            if( comp >= 0 ) lhs = lhs.idom();
+            if( comp <= 0 ) rhs = rhs.idom();
+        }
+        return lhs;
+    }
+
+    // Loop nesting depth
+    public int _loopDepth;
+    public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; }
+
+    // Anti-dependence field support
+    public int _anti;           // Per-CFG field to help find anti-deps
+
+    // ------------------------------------------------------------------------
+    // Support routines for Global Code Motion
+
+    // Tik-tok recursion pattern.  This method is final, and every caller does
+    // this work.
+    public final void walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) {
+        if( visit.get(_nid) ) return;
+        visit.set(_nid);
+        _walkUnreach(visit,unreach);
+        unreach.remove(this); // Since we reached here... Node was not unreachable
+    }
+
+    // Tik-tok recursion pattern; not-final; callers override this.
+    void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) {
+        cfg(0).walkUnreach(visit,unreach);
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java
new file mode 100644
index 00000000..fb0ff879
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java
@@ -0,0 +1,61 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+import com.seaofnodes.simple.type.TypeTuple;
+import java.util.BitSet;
+
+public class CProjNode extends CFGNode {
+
+    // Which slice of the incoming multipart value
+    public final int _idx;
+
+    // Debugging label
+    public final String _label;
+
+    public CProjNode(Node ctrl, int idx, String label) {
+        super(ctrl);
+        _idx = idx;
+        _label = label;
+    }
+
+    @Override public String label() { return _label; }
+
+    @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); }
+
+    @Override public boolean isMultiTail() { return in(0).isMultiHead(); }
+    @Override public boolean blockHead() { return true; }
+
+    public CFGNode ctrl() { return cfg(0); }
+
+    @Override
+    public Type compute() {
+        Type t = ctrl()._type;
+        return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        if ( ctrl() instanceof IfNode iff ) {
+            if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL )
+                return iff.in(0); // We become our input control
+
+            // Flip a negating if-test, to remove the not
+            if( iff.pred().addDep(this) instanceof NotNode not )
+                return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True");
+        }
+        return null;
+    }
+
+    @Override
+    public Node getBlockStart() {
+        return ctrl() instanceof IfNode ? this : ctrl().getBlockStart();
+    }
+    @Override
+    boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; }
+
+    @Override
+    int hash() { return _idx; }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index ca42c2dc..cf1a76b0 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -36,6 +36,8 @@ public class ConstantNode extends Node {
     }
 
     @Override public boolean isMultiTail() { return true; }
+    // The special forever-zero is pinned, all others can sink
+    @Override public boolean isPinned() { return this==Parser.ZERO; }
 
     @Override
     public Type compute() { return _con; }
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 1cf4ddaf..5457ac6e 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -5,8 +5,9 @@ import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 import com.seaofnodes.simple.type.TypeTuple;
 import java.util.BitSet;
+import java.util.HashSet;
 
-public class IfNode extends MultiNode {
+public class IfNode extends CFGNode implements MultiNode {
 
     public IfNode(Node ctrl, Node pred) {
         super(ctrl, pred);
@@ -22,7 +23,6 @@ public class IfNode extends MultiNode {
         return in(1)._print0(sb, visited).append(" )");
     }
 
-    @Override public boolean isCFG() { return true; }
     @Override public boolean isMultiHead() { return true; }
 
     public Node ctrl() { return in(0); }
@@ -52,11 +52,20 @@ public class IfNode extends MultiNode {
         // Hunt up the immediate dominator tree.  If we find an identical if
         // test on either the true or false branch, that side wins.
         if( !pred()._type.isHighOrConst() )
-            for( Node dom = idom(), prior=this; dom!=null;  prior = dom, dom = dom.idom() )
-                if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) {
+            for( CFGNode dom = idom(), prior=this; dom!=null;  prior = dom, dom = dom.idom() )
+                if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) {
                     setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole());
                     return this;
                 }
         return null;
     }
+
+    @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) {
+        for( Node proj : _outputs )
+            if( ((CProjNode)proj)._loopDepth == 0 )
+                unreach.add((CProjNode)proj);
+        super._walkUnreach(visit,unreach);
+    }
+
+    @Override public Node getBlockStart() { return ctrl().getBlockStart(); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 53ae1096..296237f4 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -21,7 +21,7 @@ public class LoadNode extends MemOpNode {
      * @param memPtr The ptr to the struct from where we load a field
      */
     public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) {
-        super(name, alias, memSlice, memPtr, null);
+        super(name, alias, null, memSlice, memPtr);
         _declaredType = glb;
     }
 
@@ -45,7 +45,7 @@ public class LoadNode extends MemOpNode {
         // Simple Load-after-Store on same address.
         if( mem() instanceof StoreNode st &&
             ptr() == st.ptr() ) { // Must check same object
-            assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
+            assert _name.equals(st._name); // Equiv class aliasing is perfect
             return st.val();
         }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index ea1489c4..c662dee6 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -1,15 +1,17 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
-
+import com.seaofnodes.simple.type.TypeInteger;
 import java.util.BitSet;
+import java.util.HashSet;
 
 public class LoopNode extends RegionNode {
-
     public LoopNode( Node entry ) { super(null,entry,null); }
 
-    Node entry() { return in(1); }
-    Node back () { return in(2); }
+    public CFGNode entry() { return cfg(1); }
+    public CFGNode back () { return cfg(2); }
 
     @Override
     public String label() { return "Loop"; }
@@ -25,7 +27,51 @@ public class LoopNode extends RegionNode {
         return inProgress() ? null : super.idealize();
     }
 
-    // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0)
-    @Override int idepth() { return _idepth(1); }
-    @Override Node idom() { return entry(); }
+    // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
+    @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
+    // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
+    @Override public CFGNode idom() { return entry(); }
+
+    @Override public int loopDepth() {
+        if( _loopDepth!=0 ) return _loopDepth; // Was already set
+        _loopDepth = entry()._loopDepth+1;     // Entry depth plus one
+        // One-time tag loop exits
+        for( CFGNode idom = back(); idom!=this; idom = idom.idom() ) {
+            // Walk idom in loop, setting depth
+            idom._loopDepth = _loopDepth;
+            // Loop exit hits the CProj before the If, instead of jumping from
+            // Region directly to If.
+            if( idom instanceof CProjNode proj ) {
+                assert proj.in(0) instanceof IfNode; // Loop exit test
+                // Find the loop exit CProj, and set loop_depth
+                for( Node use : proj.in(0)._outputs )
+                    if( use instanceof CProjNode proj2 && proj2 != idom )
+                        proj2._loopDepth = _loopDepth-1;
+            }
+        }
+        return _loopDepth;
+    }
+
+    // If this is an unreachable loop, it may not have an exit.  If it does not
+    // (i.e., infinite loop), force an exit to make it reachable.
+    public void forceExit( StopNode stop ) {
+        // Walk the backedge, then immediate dominator tree util we hit this
+        // Loop again.  If we ever hit a CProj from an If (as opposed to
+        // directly on the If) we found our exit.
+        CFGNode x = back();
+        while( x != this ) {
+            if( x instanceof CProjNode exit )
+                return;         // Found an exit, not an infinite loop
+            x = x.idom();
+        }
+        // Found a no-exit loop.  Insert an exit
+        NeverNode iff = new NeverNode(back());
+        for( Node use : _outputs )
+            if( use instanceof PhiNode phi )
+                iff.addDef(use);
+        CProjNode t = new CProjNode(iff,0,"True" );
+        CProjNode f = new CProjNode(iff,1,"False");
+        setDef(2,f);
+        stop.addDef(new ReturnNode(t,Parser.ZERO,null));
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 08e08bbf..551d2aa9 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -12,8 +12,8 @@ public abstract class MemOpNode extends Node {
     public final String _name;
     public final int _alias;
 
-    public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
-        super(null, memSlice, memPtr, value);
+    public MemOpNode(String name, int alias, Node... nodes) {
+        super(nodes);
         _name  = name;
         _alias = alias;
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index 2743bd19..379e140d 100644
--- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -1,12 +1,10 @@
 package com.seaofnodes.simple.node;
 
-public abstract class MultiNode extends Node {
-
-    public MultiNode(Node... inputs) { super(inputs); }
+public interface MultiNode extends OutNode {
 
     // Find a projection by index
-    ProjNode proj( int idx ) {
-        for( Node out : _outputs )
+    default ProjNode proj( int idx ) {
+        for( Node out : outs() )
             if( out instanceof ProjNode prj && prj._idx==idx )
                 return prj;
         return null;
diff --git a/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/src/main/java/com/seaofnodes/simple/node/NeverNode.java
new file mode 100644
index 00000000..f50d3503
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java
@@ -0,0 +1,19 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.type.Type;
+import java.util.BitSet;
+
+// "Never true" for infinite loop exits
+public class NeverNode extends IfNode {
+    public NeverNode(Node ctrl) { super(ctrl,Parser.ZERO); }
+
+    @Override public String label() { return "Never"; }
+
+    @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Never"); }
+
+    @Override public Type compute() { return TypeInteger.BOT; }
+
+    @Override public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java
index 352689b5..0724ec56 100644
--- a/src/main/java/com/seaofnodes/simple/node/NewNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java
@@ -26,6 +26,8 @@ public class NewNode extends Node {
         return sb.append(_ptr._obj.str());
     }
 
+    @Override public boolean isPinned() { return true; }
+
     @Override
     public Type compute() { return _ptr; }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index bb698860..fc49ad6a 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.IRPrinter;
+import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
@@ -13,7 +14,7 @@ import java.util.function.Function;
  * The Node class provides common functionality used by all subtypes.
  * Subtypes of Node specialize by overriding methods.
  */
-public abstract class Node {
+public abstract class Node implements OutNode {
 
     /**
      * Each node has a unique dense Node ID within a compilation context
@@ -128,6 +129,7 @@ public abstract class Node {
      */
     public Node in(int i) { return _inputs.get(i); }
     public Node out(int i) { return _outputs.get(i); }
+    @Override public ArrayList<Node> outs() { return _outputs; }
 
     public int nIns() { return _inputs.size(); }
 
@@ -135,9 +137,7 @@ public abstract class Node {
 
     public boolean isUnused() { return nOuts() == 0; }
 
-    public boolean isCFG() { return false; }
-
-    public boolean isMem() { return false; }
+    public CFGNode cfg0() { return (CFGNode)in(0); }
 
     /**
      * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
@@ -164,11 +164,11 @@ public abstract class Node {
         // the new_def might get killed if the old node kills it recursively.
         if( new_def != null )
             new_def.addUse(this);
+        // Set the new_def over the old (killed) edge
+        _inputs.set(idx,new_def);
         if( old_def != null &&  // If the old def exists, remove a def->use edge
             old_def.delUse(this) ) // If we removed the last use, the old def is now dead
             old_def.kill();     // Kill old def
-        // Set the new_def over the old (killed) edge
-        _inputs.set(idx,new_def);
         moveDepsToWorklist();
         // Return self for easy flow-coding
         return new_def;
@@ -196,7 +196,7 @@ public abstract class Node {
      * @param new_def the new definition, appended to the end of existing definitions
      * @return new_def for flow coding
      */
-    Node addDef(Node new_def) {
+    public Node addDef(Node new_def) {
         unlock();
         // Add use->def edge
         _inputs.add(new_def);
@@ -323,8 +323,8 @@ public abstract class Node {
         Type old = setType(compute());
 
         // Replace constant computations from non-constants with a constant node
-        if( !(this instanceof ConstantNode) && _type.isHighOrConst() )
-            return new ConstantNode(_type).peepholeOpt();
+        if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() )
+            return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt();
 
         // Global Value Numbering
         if( _hash==0 ) {
@@ -531,6 +531,20 @@ public abstract class Node {
     // Subclasses add extra hash info (such as ConstantNodes constant)
     int hash() { return 0; }
 
+    // ------------------------------------------------------------------------
+    //
+
+    /** Is this Node control-flow-graph related */
+    public boolean isCFG() { return false; }
+
+    /** Is this Node Memory related */
+    public boolean isMem() { return false; }
+
+    /** Return block start from a isCFG() */
+    public Node getBlockStart() { return null; }
+
+    /** Pinned in the schedule */
+    public boolean isPinned() { return false; }
 
     // ------------------------------------------------------------------------
     // Peephole utilities
@@ -561,20 +575,6 @@ public abstract class Node {
     }
 
 
-    /**
-     * Immediate dominator tree depth, used to approximate a real IDOM depth
-     * during parsing where we do not have the whole program, and also
-     * peepholes change the CFG incrementally.
-     * <p>
-     * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
-     */
-    public int _idepth;         // IDOM depth approx; Zero is unset; non-zero is cached legit
-    final int _idepth(int idx) { return _idepth==0 ? (_idepth=in(idx).idepth()+1) : _idepth; }
-    int idepth() { return _idepth(0); }
-
-    // Return the immediate dominator of this Node.
-    Node idom() { return in(0); }
-
     // Make a shallow copy (same class) of this Node, with given inputs and
     // empty outputs and a new Node ID.  The original inputs are ignored.
     // Does not need to be implemented in isCFG() nodes.
diff --git a/src/main/java/com/seaofnodes/simple/node/OutNode.java b/src/main/java/com/seaofnodes/simple/node/OutNode.java
new file mode 100644
index 00000000..7e531145
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/OutNode.java
@@ -0,0 +1,7 @@
+package com.seaofnodes.simple.node;
+
+import java.util.ArrayList;
+
+public interface OutNode {
+    ArrayList<Node> outs();
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index dd67bd06..a07dc140 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -35,10 +35,10 @@ public class PhiNode extends Node {
         return sb;
     }
 
-    Node region() { return in(0); }
+    public CFGNode region() { return (CFGNode)in(0); }
     @Override public boolean isMultiTail() { return true; }
-    @Override
-    public boolean isMem() { return _declaredType instanceof TypeMem; }
+    @Override public boolean isMem() { return _declaredType instanceof TypeMem; }
+    @Override public boolean isPinned() { return true; }
 
     @Override
     public Type compute() {
@@ -102,9 +102,9 @@ public class PhiNode extends Node {
                 Node val = in(3-nullx);
                 if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) {
                     // Must walk the idom on the null side to make sure we hit False.
-                    Node idom = region().in(nullx);
+                    CFGNode idom = (CFGNode)region().in(nullx);
                     while( idom.in(0) != iff ) idom = idom.idom();
-                    if( idom instanceof ProjNode proj && proj._idx==1 )
+                    if( idom instanceof CProjNode proj && proj._idx==1 )
                         return val;
                 }
             }
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 735fcdf3..f94e98a7 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -14,7 +14,7 @@ public class ProjNode extends Node {
     // Debugging label
     public final String _label;
 
-    public ProjNode(MultiNode ctrl, int idx, String label) {
+    public ProjNode(Node ctrl, int idx, String label) {
         super(ctrl);
         _idx = idx;
         _label = label;
@@ -26,11 +26,9 @@ public class ProjNode extends Node {
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); }
 
-    @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
     @Override public boolean isMultiTail() { return in(0).isMultiHead(); }
     @Override public boolean isMem() { return _type instanceof TypeMem; }
-
-    public MultiNode ctrl() { return (MultiNode)in(0); }
+    @Override public boolean isPinned() { return true; }
 
     @Override
     public Type compute() {
@@ -38,18 +36,7 @@ public class ProjNode extends Node {
         return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
     }
 
-    @Override
-    public Node idealize() {
-        if ( ctrl() instanceof IfNode iff ) {
-            if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL )
-                return iff.in(0); // We become our input control
-
-            // Flip a negating if-test, to remove the not
-            if( iff.pred().addDep(this) instanceof NotNode not )
-                return new ProjNode((MultiNode)new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True");
-        }
-        return null;
-    }
+    @Override public Node idealize() { return null; }
 
     @Override
     boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; }
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 42501118..dcc7ccef 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -1,14 +1,15 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
-
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.BitSet;
+import java.util.HashSet;
 
-public class RegionNode extends Node {
+public class RegionNode extends CFGNode {
 
     public RegionNode(Node... nodes) { super(nodes); }
 
@@ -20,8 +21,8 @@ public class RegionNode extends Node {
         return sb.append(label()).append(_nid);
     }
 
-    @Override public boolean isCFG() { return true; }
     @Override public boolean isMultiHead() { return true; }
+    @Override public boolean blockHead() { return true; }
 
     @Override
     public Type compute() {
@@ -57,7 +58,7 @@ public class RegionNode extends Node {
                         IterPeeps.addAll(phi._outputs);
                     }
             }
-            return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path);
+            return isDead() ? Parser.XCTRL : delDef(path);
         }
         // If down to a single input, become that input
         if( nIns()==2 && !hasPhi() )
@@ -89,31 +90,31 @@ public class RegionNode extends Node {
     }
 
     // Immediate dominator of Region is a little more complicated.
-    @Override int idepth() {
+    @Override public int idepth() {
         if( _idepth!=0 ) return _idepth;
         int d=0;
         for( Node n : _inputs )
             if( n!=null )
-                d = Math.max(d,n.idepth());
+                d = Math.max(d,((CFGNode)n).idepth()+1);
         return _idepth=d;
     }
 
-    @Override Node idom() {
-        if( nIns()==2 ) return in(1); // 1-input is that one input
-        if( nIns()!=3 ) return null;  // Fails for anything other than 2-inputs
+    @Override public CFGNode idom() {
+        CFGNode lca = null;
         // Walk the LHS & RHS idom trees in parallel until they match, or either fails.
         // Because this does not cache, it can be linear in the size of the program.
-        Node lhs = in(1);
-        Node rhs = in(2);
-        while( lhs != rhs ) {
-          if( lhs==null || rhs==null ) return null;
-          var comp = lhs.idepth() - rhs.idepth();
-          if( comp >= 0 ) lhs = lhs.idom();
-          if( comp <= 0 ) rhs = rhs.idom();
-        }
-        return lhs;
+        for( int i=1; i<nIns(); i++ )
+            lca = cfg(i).idom(lca);
+        return lca;
+    }
+
+    @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) {
+        for( int i=1; i<nIns(); i++ )
+            cfg(i).walkUnreach(visit,unreach);
     }
 
+    @Override public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(1).loopDepth()) : _loopDepth; }
+
     // True if last input is null
     public final boolean inProgress() {
         return nIns()>1 && in(nIns()-1) == null;
@@ -123,4 +124,6 @@ public class RegionNode extends Node {
     @Override boolean eq( Node n ) {
         return !inProgress();
     }
+
+    @Override public Node getBlockStart() { return this; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 92bda5bf..444b76a8 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -13,16 +13,18 @@ import java.util.BitSet;
  * <p>
  * The Return's output is the value from the data node.
  */
-public class ReturnNode extends Node {
+public class ReturnNode extends CFGNode {
 
     public ReturnNode(Node ctrl, Node data, ScopeNode scope) {
         super(ctrl, data);
         // We lookup memory slices by the naming convention that they start with $
         // We could also use implicit knowledge that all memory projects are at offset >= 2
-        String[] names = scope.reverseNames();
-        for (String name: names) {
-            if (!name.equals("$ctrl") && name.startsWith("$"))
-                addDef(scope.lookup(name));
+        if( scope != null ) {
+            String[] names = scope.reverseNames();
+            for (String name: names) {
+                if (!name.equals("$ctrl") && name.startsWith("$"))
+                    addDef(scope.lookup(name));
+            }
         }
     }
 
@@ -39,8 +41,6 @@ public class ReturnNode extends Node {
         return sb.append(";");
     }
 
-    @Override public boolean isCFG() { return true; }
-
     @Override
     public Type compute() {
         return TypeTuple.make(ctrl()._type,expr()._type);
@@ -52,4 +52,6 @@ public class ReturnNode extends Node {
             return ctrl();
         return null;
     }
+
+    @Override public Node getBlockStart() { return ctrl().getBlockStart(); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 4b7e02a8..62fc8a6b 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -5,6 +5,7 @@ import com.seaofnodes.simple.type.*;
 import java.util.Arrays;
 import java.util.BitSet;
 import java.util.HashMap;
+import java.util.HashSet;
 
 /**
  * The Start node represents the start of the function.
@@ -13,7 +14,7 @@ import java.util.HashMap;
  * In ch10 we also add mem aliases as structs get defined; each field in struct
  * adds a distinct alias to Start's tuple.
  */
-public class StartNode extends MultiNode {
+public class StartNode extends CFGNode implements MultiNode {
 
     // This field is NOT final, because the tuple expands as we add memory aliases
     TypeTuple _args;
@@ -63,8 +64,8 @@ public class StartNode extends MultiNode {
       return sb.append(label());
     }
 
-    @Override public boolean isCFG() { return true; }
     @Override public boolean isMultiHead() { return true; }
+    @Override public boolean blockHead() { return true; }
 
     @Override
     public TypeTuple compute() { return _args; }
@@ -73,6 +74,12 @@ public class StartNode extends MultiNode {
     public Node idealize() { return null; }
 
     // No immediate dominator, and idepth==0
-    @Override int idepth() { return 0; }
-    @Override Node idom() { return null; }
+    @Override public int idepth() { return 0; }
+    @Override public CFGNode idom() { return null; }
+
+    @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { }
+
+    @Override public int loopDepth() { return (_loopDepth=1); }
+
+    @Override public Node getBlockStart() { return this; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 3b5a7ce3..94b2ad6d 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -5,7 +5,7 @@ import com.seaofnodes.simple.IterPeeps;
 
 import java.util.BitSet;
 
-public class StopNode extends Node {
+public class StopNode extends CFGNode {
 
     public final String _src;
 
@@ -28,7 +28,7 @@ public class StopNode extends Node {
         return sb.append("]");
     }
 
-    @Override public boolean isCFG() { return true; }
+    @Override public boolean blockHead() { return true; }
 
     // If a single Return, return it.
     // Otherwise, null because ambiguous.
@@ -51,7 +51,17 @@ public class StopNode extends Node {
         return null;
     }
 
-    @Override public Node idom() { return null; }
+    @Override public int idepth() {
+        if( _idepth!=0 ) return _idepth;
+        int d=0;
+        for( Node n : _inputs )
+            if( n!=null )
+                d = Math.max(d,((CFGNode)n).idepth()+1);
+        return _idepth=d;
+    }
+    @Override public CFGNode idom() { return null; }
+
+    @Override public int loopDepth() { return (_loopDepth=1); }
 
     public Node addReturn(Node node) {
         return addDef(node);
@@ -64,4 +74,6 @@ public class StopNode extends Node {
         if( err != null ) throw new RuntimeException(err);
         return this;
     }
+
+    @Override public Node getBlockStart() { return this; }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 8d264601..db8e2ce6 100644
--- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -17,8 +17,8 @@ public class StoreNode extends MemOpNode {
      * @param memPtr The ptr to the struct where we will store a value
      * @param value Value to be stored
      */
-    public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
-        super(name, alias, memSlice, memPtr, value);
+    public StoreNode(String name, int alias, Node ctrl, Node memSlice, Node memPtr, Node value) {
+        super(name, alias, ctrl, memSlice, memPtr, value);
     }
 
     @Override
@@ -48,7 +48,7 @@ public class StoreNode extends MemOpNode {
             // Must have exactly one use of "this" or you get weird
             // non-serializable memory effects in the worse case.
             st.checkNoUseBeyond(this) ) {
-            assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
+            assert _name.equals(st._name); // Equiv class aliasing is perfect
             setDef(1,st.mem());
             return this;
         }
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index b87115cd..5ddcdb68 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
diff --git a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java
new file mode 100644
index 00000000..83779dd2
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java
@@ -0,0 +1,13 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+import java.util.BitSet;
+
+public class XCtrlNode extends CFGNode {
+    public XCtrlNode( ) { super(Parser.START); }
+    @Override public String label() { return "Xctrl"; }
+    @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Xctrl"); }
+    @Override  public Type compute() { return Type.XCONTROL; }
+    @Override public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java
index 56626482..e1c337d4 100644
--- a/src/main/java/com/seaofnodes/simple/type/Field.java
+++ b/src/main/java/com/seaofnodes/simple/type/Field.java
@@ -47,7 +47,7 @@ public class Field extends Type {
 
     boolean eq(Type t) {
         Field f = (Field)t;
-        return Utils.eq(_fname,f._fname) && _type==f._type;
+        return _fname.equals(f._fname) && _type==f._type;
     }
 
 
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index d57f6c98..01bcbe9f 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -58,8 +58,7 @@ public class TypeTuple extends Type {
         for( Type t : _types )
             t.typeName(sb).append(",");
         sb.setLength(sb.length()-1);
-        sb.append("]");
-        return sb;
+        return sb.append("]");
     }
 
     public static final TypeTuple IF_BOTH    = make(new Type[]{Type. CONTROL,Type. CONTROL});