Chapter 13: Global Code Motion

Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

28 files changed, 717 insertions, 150 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..78a0dcde
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -0,0 +1,275 @@
+ package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.IterPeeps.WorkList;
+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 ) {
+        schedEarly();
+        Parser.SCHEDULED = true;
+        schedLate( stop);
+    }
+
+    // ------------------------------------------------------------------------
+    // 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
+    public 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);
+    }
+
+    // ------------------------------------------------------------------------
+    // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses
+    // (except at loops).  Since defs are visited first - and hoisted as early
+    // as possible, when we come to a use we place it just after its deepest
+    // input.
+    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);
+            // In dead infinite loops, entire code blocks may be unreachable
+            // from below.  Reach down from the CFG to their Phis so their
+            // inputs are scheduled too.
+            if( cfg instanceof RegionNode ) {
+                int len = cfg.nOuts();
+                for( int i=0; i<len; i++ )
+                    if( cfg.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 inputs first, except Phis: following their backedges would
+        // enter a data cycle before its control has been scheduled.
+        for( Node def : n._inputs )
+            if( def!=null && !(def instanceof PhiNode) )
+                _schedEarly(def,visit);
+        // An existing edge 0 already supplies control (or a Phi/Proj binding).
+        if( n.in(0)==null ) {
+            // Schedule at deepest input
+            CFGNode early = Parser.START; // Maximally early, lowest idepth
+            for( int i=1; i<n.nIns(); i++ )
+                if( n.in(i)!=null && 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( StopNode stop) {
+        CFGNode[] late = new CFGNode[Node.UID()];
+        Node[] ns = new Node[Node.UID()];
+        // Record Load NIDs at all their CFG block choices, then check against
+        // Store block choices to force a Load above an anti-dependent Store.
+        int[] anti = new int[Node.UID()];
+        // Breadth-first scheduling
+        breadth(stop,ns,late,anti);
+
+        // Copy the best placement choice into the control slot
+        for( int i=0; i<late.length; i++ )
+            if( ns[i] != null )
+                ns[i].setDef(0,late[i]);
+    }
+
+    private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) {
+        // Things on the worklist have some (but perhaps not all) uses done.
+        WorkList<Node> work = new WorkList<>();
+        work.push(stop);
+        Node n;
+        outer:
+        while( (n = work.pop()) != null ) {
+            assert late[n._nid]==null; // No double visit
+            // 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);
+            else if( n instanceof PhiNode phi ) late[n._nid] = phi.region();
+            // These nodes have a fixed late placement at their original control.
+            else if( n instanceof ProjNode || n instanceof NewNode || n==Parser.ZERO || n instanceof CastNode ) late[n._nid] = n.cfg0();
+            else {
+
+                // All uses done?
+                for( Node use : n._outputs )
+                    if( use!=null && late[use._nid]==null )
+                        continue outer; // Nope, await all uses done
+
+                // Loads need their memory inputs' uses also done
+                if( n instanceof LoadNode ld )
+                    for( Node memuse : ld.mem()._outputs )
+                        if( antiUse(ld,memuse) && late[memuse._nid]==null )
+                            continue outer;
+
+                // All uses done, schedule
+                _doSchedLate(n,ns,late,anti);
+            }
+
+            // A use just finished; reconsider its inputs and waiting loads,
+            // even when the shared memory input was already scheduled.
+            for( Node def : n._inputs ) {
+                if( def==null ) continue;
+                if( late[def._nid]==null ) work.push(def);
+                for( Node out : def._outputs )
+                    if( out instanceof LoadNode ld && late[ld._nid]==null )
+                        work.push(ld);
+            }
+            if( n instanceof LoopNode loop )
+                for( Node phi : loop._outputs )
+                    if( phi instanceof PhiNode && late[phi._nid]==null )
+                        work.push(phi);
+        }
+    }
+
+    private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) {
+        // 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).domLCA(lca,null);
+
+        // Loads may need anti-dependencies, raising their LCA
+        if( n instanceof LoadNode load )
+            lca = find_anti_dep(lca,load,early,late,anti);
+
+        // 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 )
+                found = phi.region().cfg(i).domLCA(found,null); // Can be more than one matching input.
+        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 instanceof NeverNode ||
+            lca.idepth() > best.idepth() ||
+            best instanceof IfNode;
+    }
+
+    // Only a store or memory Phi covering this alias can constrain a load.
+    // MemMerge packages slices without overwriting them.
+    private static boolean antiUse(LoadNode load, Node use) {
+        return switch( use ) {
+        case StoreNode st -> st._alias==load._alias;
+        case MemPhiNode phi -> phi._alias==load._alias;
+        case BulkMemPhiNode phi -> !phi.isSplit(load._alias);
+        default -> false;
+        };
+    }
+
+    private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) {
+        // 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() )
+            anti[cfg._nid] = load._nid;
+        // Walk load->mem uses, looking for Stores causing an anti-dep
+        for( Node mem : load.mem()._outputs ) {
+            if( !antiUse(load,mem) ) continue;
+            switch( mem ) {
+            case StoreNode st:
+                assert late[st._nid]!=null;
+                lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti);
+                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,anti);
+                break;
+            default: throw Utils.TODO();
+            }
+        }
+        return lca;
+    }
+
+    //
+    private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) {
+        // Preserve the full store range for the earlier evaluator scheduler.
+        // It places nodes independently of GCM and may hoist this store.
+        for( ; stblk != defblk.idom(); stblk = stblk.idom() ) {
+            // Store and Load overlap, need anti-dependence
+            if( anti[stblk._nid]==load._nid ) {
+                lca = stblk.domLCA(lca,null); // 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/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java
index d5ab15fe..7e93e9da 100644
--- a/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -8,7 +8,6 @@ public final class IRPrinter extends IRAdapter<Node> {
     private static final com.seaofnodes.print.IRPrinter<Node> PRINT =
         new com.seaofnodes.print.IRPrinter<>(new IRPrinter());
     @Override public String type(Node n) { return n._type==null ? "" : n._type.str(); }
-    @Override public int inputColumns() { return 3; }
     @Override public String inputMark(Node n, Node def) { return n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "; }
     @Override public Kind kind(Node n) {
         if( n instanceof StartNode ) return Kind.START;
@@ -18,13 +17,15 @@ public final class IRPrinter extends IRAdapter<Node> {
         if( n instanceof PhiNode ) return Kind.PHI;
         if( n instanceof ReturnNode ) return Kind.RETURN;
         if( n instanceof ConstantNode ) return Kind.CONSTANT;
-        if( n instanceof ProjNode ) return n.isCFG() ? Kind.CPROJ : Kind.PROJ;
-        if( n.isCFG() ) return Kind.CTRL;
+        if( n instanceof CProjNode ) return Kind.CPROJ;
+        if( n instanceof ProjNode ) return n instanceof CFGNode ? Kind.CPROJ : Kind.PROJ;
+        if( n instanceof CFGNode ) return Kind.CTRL;
         if( n instanceof MultiNode ) return Kind.MULTI;
         return Kind.DATA;
     }
     @Override public int index(Node n) {
         if( n instanceof ProjNode p ) return p._idx;
+        if( n instanceof CProjNode p ) return p._idx;
         return n._nid;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index a25edeb1..3c8d8f40 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -31,12 +31,18 @@ public class Parser {
      */
     public static StartNode START;
 
+    public static ConstantNode ZERO;
+    public static XCtrlNode XCTRL;
+
     public StopNode STOP;
 
     // Field identities are independent of the memory graph and Start's tuple.
     private final HashMap<String,Integer> _aliases = new HashMap<>();
     private int _alias = 2;
 
+    // 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;
 
@@ -82,7 +88,7 @@ public class Parser {
     ScopeNode _continueScope;
     ScopeNode _breakScope;
 
-    // Authoritative declarations, indexed by type name.
+    // Mapping from a type name to a Type.
     public static HashMap<String, Type> TYPES = new HashMap<>();
 
     public Parser(String source, TypeInteger arg) {
@@ -91,11 +97,14 @@ public class Parser {
         IterPeeps.reset();
         TYPES.clear();
         TYPES.put("int",TypeInteger.BOT);
+        SCHEDULED = false;
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
         _continueScope = _breakScope = null;
         START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg });
         STOP = new StopNode(source);
+        ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep();
+        XCTRL= new XCtrlNode().peephole().keep();
     }
 
     public Parser(String source) {
@@ -118,8 +127,8 @@ 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, 2, 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, 2, ScopeNode.ARG0).peephole());
         _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole());
         parseBlock();
         if( ctrl()._type==Type.CONTROL )
@@ -187,7 +196,7 @@ public class Parser {
     }
 
     /**
-     * Parse a complete struct declaration.
+     * Parse a struct declaration, and return the following statement.
      * Only allowed in top level scope.
      * Structs cannot be redefined.
      *
@@ -252,8 +261,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
@@ -299,7 +308,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() )
@@ -335,8 +344,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();
@@ -353,7 +362,7 @@ public class Parser {
         // Parse the false side
         _scope = fScope;        // Restore scope, then parse else block if any
         ifF.unkeep();           // fScope already owns the false control
-        _scope.upcast(ifF,pred,true); // Up-cast predicate, also without an else
+        _scope.upcast(ifF,pred,true); // Up-cast predicate
         if (matchx("else")) {
             parseStatement();
             fScope = _scope;
@@ -383,7 +392,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;
     }
 
@@ -436,7 +445,8 @@ public class Parser {
         return _scope.update(name,expr);
     }
 
-    // Parse a type-or-null
+    // Parse a "type id" and return "type" (and re-parse "id" in caller) or
+    // return null.
     private Type type() {
         int old = _lexer._position;
         String tname = _lexer.matchId();
@@ -457,6 +467,7 @@ public class Parser {
         return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t;
     }
 
+
     /**
      * Parse an expression of the form:
      *
@@ -527,7 +538,7 @@ public class Parser {
      * @return a multiply expression {@link Node}, never {@code null}
      */
     private Node parseMultiplication() {
-        var lhs = parseUnary();
+        var lhs = parseUnary();  boolean mul;
         while( true ) {
             if( false ) ;
             else if( match("*") ) lhs = new MulNode(lhs,null);
@@ -562,10 +573,10 @@ public class Parser {
      * @return a primary {@link Node}, never {@code null}
      */
     private Node parsePrimary() {
-        if( _lexer.isNumber(_lexer.peek()) ) return parseIntegerLiteral();
+        if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral();
         if( match("(") ) return require(parseExpression(), ")");
         if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole();
-        if( matchx("false") ) return new ConstantNode(TypeInteger.ZERO).peephole();
+        if( matchx("false") ) return ZERO;
         if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole();
         if( matchx("new") ) {
             String structName = requireId();
@@ -600,7 +611,7 @@ public class Parser {
 
     private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) {
         Node prior = mem().keep();
-        Node st = new StoreNode(name,alias,glb,null,prior,ptr,val,init).peephole();
+        Node st = new StoreNode(name,alias,glb,ctrl(),prior,ptr,val,init).peephole();
         mem(new MemMergeNode(prior,alias,st).peephole());
         if( prior.unkeep().isUnused() ) prior.kill();
     }
@@ -649,7 +660,7 @@ public class Parser {
      *     integerLiteral: [1-9][0-9]* | [0]
      * </pre>
      */
-    private ConstantNode parseIntegerLiteral() {
+    private ConstantNode parseLiteral() {
         return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole();
     }
 
@@ -744,7 +755,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;
+            }
         }
 
 
@@ -826,8 +846,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/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index e993a20e..eb7e2793 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -103,6 +103,7 @@ public class AddNode extends Node {
     static Node phiCon(Node op, boolean rotate) {
         Node lhs = op.in(1);
         Node rhs = op.in(2);
+        if( rhs._type==TypeInteger.TOP ) return null;
         // LHS is either a Phi of constants, or another op with Phi of constants
         PhiNode lphi = pcon(lhs,op);
         if( rotate && lphi==null && lhs.nIns() > 2 ) {
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..c690a83c
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -0,0 +1,96 @@
+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; }
+
+    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 char _idepth;
+    public int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); }
+    // Zero depth means uncached. Check before narrowing so overflow cannot wrap.
+    final int cacheIDepth(int depth) {
+        assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535";
+        return _idepth = (char)depth;
+    }
+
+
+    // Return the immediate dominator of this Node and compute dom tree depth.
+    public CFGNode idom(Node dep) { return cfg(0); }
+    public final CFGNode idom() { return idom(null); }
+
+    // Return the LCA of two idoms
+    public CFGNode domLCA(CFGNode rhs, Node dep) {
+        if( rhs==null ) return this;
+        CFGNode lhs = this;
+        while( lhs != rhs ) {
+            if( lhs==null || rhs==null ) return null;
+            int comp = lhs.idepth() - rhs.idepth();
+            if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom();
+            if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom();
+        }
+        return lhs;
+    }
+
+    // Loop nesting depth
+    public int _loopDepth;
+    public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; }
+
+    // ------------------------------------------------------------------------
+    // 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..ff5d1a76
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java
@@ -0,0 +1,62 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.print.ExprPrinter;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+import com.seaofnodes.simple.type.TypeTuple;
+
+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 protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_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/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java
index c1faf210..9ade5a50 100644
--- a/src/main/java/com/seaofnodes/simple/node/CastNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java
@@ -20,6 +20,7 @@ public class CastNode extends Node {
     @Override public String label() { return "("+_t.str()+")"; }
 
 
+
     @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
         return p.p(label()).n(in(1));
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 426736ed..9ecd1152 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -38,6 +38,7 @@ public class ConstantNode extends Node {
     }
 
     @Override public boolean isMultiTail() { return true; }
+    // The special forever-zero is pinned, all others can sink
 
     @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 45f695a5..70340f7f 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -5,8 +5,10 @@ import com.seaofnodes.simple.IterPeeps;
 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);
@@ -18,7 +20,6 @@ public class IfNode extends MultiNode {
 
     @Override protected String format() { return "if( %1 )"; }
 
-    @Override public boolean isCFG() { return true; }
     @Override public boolean isMultiHead() { return true; }
 
     public Node ctrl() { return in(0); }
@@ -48,11 +49,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 b2ee6939..277644f5 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -5,7 +5,6 @@ import com.seaofnodes.print.ExprPrinter;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.Field;
 
 
 /**
@@ -43,9 +42,7 @@ public class LoadNode extends MemOpNode {
         return false;
     }
 
-    @Override
-    public String label() { return "Load"; }
-
+    @Override public String  label() { return     _name; }
     @Override
     protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(".").p(_name); }
 
@@ -65,7 +62,7 @@ public class LoadNode extends MemOpNode {
         // Simple Load-after-Store on same address.
         if( mem() instanceof StoreNode st &&
             ptr() == st.ptr() && _alias==st._alias ) { // 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();
         }
 
@@ -81,9 +78,13 @@ public class LoadNode extends MemOpNode {
             if( profit(memphi,2) ||
                 // Else must not be a loop to count profit on LHS.
                 (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) {
-                Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole();
-                Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole();
-                return new PhiNode(_name,_type,memphi.region(),ld1,ld2);
+                if( ptr() instanceof NewNode || !(ptr() instanceof CastNode) ) {
+                    if( !(ptr() instanceof NewNode) ) throw Utils.TODO(); // Validate
+
+                    Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole();
+                    Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole();
+                    return new PhiNode(_name,_type,memphi.region(),ld1,ld2);
+                }
             }
         }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index a0ba973e..a0e988dd 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,54 @@ 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!=0 ? _idepth : cacheIDepth(entry().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 : cacheIDepth(entry().idepth()+1); }
+    // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
+    @Override public CFGNode idom(Node dep) { 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 && exit.in(0) instanceof IfNode iff ) {
+                Node other = iff.cproj(1-exit._idx);
+                if( !(other.out(0) instanceof LoopNode loop) || loop.entry()==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/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index 2743bd19..ac9c0045 100644
--- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -1,14 +1,20 @@
 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;
     }
+
+    // Find a projection by index
+    default CProjNode cproj( int idx ) {
+        for( Node out : outs() )
+            if( out instanceof CProjNode 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..7e42ccf9
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java
@@ -0,0 +1,22 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.print.ExprPrinter;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
+
+
+// "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 protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Never"); }
+
+    @Override public Type compute() { return TypeTuple.IF_BOTH; }
+
+    @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 857920bc..74ba5184 100644
--- a/src/main/java/com/seaofnodes/simple/node/NewNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java
@@ -22,6 +22,7 @@ public class NewNode extends Node {
         return p.p("new ").p(_ptr._obj.str());
     }
 
+
     @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 999e38fd..2c8596fa 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -17,7 +17,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 extends BaseNode<Node> implements Cloneable {
+public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable {
 
     /**
      * Inputs to the node. These are use-def references to Nodes.
@@ -83,6 +83,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
      */
     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(); }
 
@@ -90,7 +91,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
 
     public boolean isUnused() { return nOuts() == 0; }
 
-    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
@@ -117,11 +118,11 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
         // 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;
@@ -149,7 +150,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
      * @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);
@@ -269,8 +270,8 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
         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 ) {
@@ -485,6 +486,17 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
     int hash() { return 0; }
 
     // ------------------------------------------------------------------------
+    //
+
+    /** Is this Node control-flow-graph related */
+
+    /** Is this Node Memory related */
+    public boolean isMem() { return false; }
+
+    /** Return block start from a isCFG() */
+    public Node getBlockStart() { return null; }
+
+    // ------------------------------------------------------------------------
     // Peephole utilities
 
     // Swap inputs without letting either input go dead during the swap.
@@ -512,38 +524,6 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
         return true;
     }
 
-    /**
-     * 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 char _idepth;         // IDOM depth approx; Zero is unset; non-zero is cached legit
-
-    // Find the lowest common ancestor in the current dominator tree.
-    Node domLCA(Node rhs) {
-        if( rhs==null ) return this;
-        Node lhs = this;
-        while( lhs != rhs ) {
-            if( lhs==null || rhs==null ) return null;
-            int comp = lhs.idepth() - rhs.idepth();
-            if( comp >= 0 ) lhs = lhs.idom();
-            if( comp <= 0 ) rhs = rhs.idom();
-        }
-        return lhs;
-    }
-
-    int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); }
-    // Zero depth means uncached. Check before narrowing so overflow cannot wrap.
-    final int cacheIDepth(int depth) {
-        assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535";
-        return _idepth = (char)depth;
-    }
-
-    // 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 6995cc2f..8dfa04cf 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -32,10 +32,9 @@ public class PhiNode extends Node {
         return p.unchar(',').close();
     }
 
-    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 Type compute() {
@@ -83,11 +82,11 @@ public class PhiNode extends Node {
             if( in(2)._type == in(2)._type.makeInit() ) nullx = 2;
             if( nullx != -1 ) {
                 Node val = in(3-nullx);
-                if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) {
+                if( region().idom(this) 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);
-                    while( idom.in(0) != iff ) idom = idom.idom();
-                    if( idom instanceof ProjNode proj && proj._idx==1 )
+                    CFGNode idom = (CFGNode)region().in(nullx);
+                    while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom();
+                    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 a2632110..e82c69b3 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -15,7 +15,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;
@@ -27,30 +27,16 @@ public class ProjNode extends Node {
     @Override
     protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_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 Type compute() {
         Type t = in(0)._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 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 8b52494a..cdfd10ad 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -3,13 +3,15 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.print.ExprPrinter;
 
 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 +22,8 @@ public class RegionNode extends Node {
         return p.p(label()).p(_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 +59,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,23 +91,30 @@ 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 depth=0;
         for( Node n : _inputs )
             if( n!=null )
-                depth = Math.max(depth,n.idepth()+1);
+                depth = Math.max(depth,((CFGNode)n).idepth()+1);
         return cacheIDepth(depth);
     }
 
-    @Override Node idom() {
-        Node lca = null;
+    @Override public CFGNode idom(Node dep) {
+        CFGNode lca = null;
         // Recompute from predecessors: CFG edits can change the dominator.
         for( int i=1; i<nIns(); i++ )
-            lca = in(i).domLCA(lca);
+            lca = cfg(i).domLCA(lca,dep);
         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;
@@ -115,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 ef4ddb3a..161cc7d6 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -6,10 +6,11 @@ import com.seaofnodes.simple.type.*;
 
 
 /** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */
-public class ReturnNode extends Node {
+public class ReturnNode extends CFGNode {
 
     public ReturnNode(Node ctrl, Node data, ScopeNode scope) {
-        super(ctrl, scope.lookup("$mem"), data);
+        // A synthetic never-taken loop exit has no source scope.
+        super(ctrl, scope == null ? null : scope.lookup("$mem"), data);
     }
 
     public Node ctrl() { return in(0); }
@@ -26,8 +27,6 @@ public class ReturnNode extends Node {
         return p.p(";");
     }
 
-    @Override public boolean isCFG() { return true; }
-
     @Override
     public Type compute() {
         // Return exposes the complete memory state.
@@ -40,4 +39,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 3404f111..a5d4923f 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -3,10 +3,13 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.print.ExprPrinter;
 
 import com.seaofnodes.simple.type.*;
+import java.util.BitSet;
+import java.util.HashSet;
 
-/** The entry tuple: control, initial whole-memory state, and argument. */
-public class StartNode extends MultiNode {
-    final TypeTuple _args;
+/** Start supplies control, whole memory, and the argument, in that order. */
+public class StartNode extends CFGNode implements MultiNode {
+
+    private final TypeTuple _args;
 
     public StartNode(Type[] args) {
         super();
@@ -20,8 +23,8 @@ public class StartNode extends MultiNode {
         return p.p(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; }
@@ -30,6 +33,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(Node dep) { 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 4b4e9615..202afbd2 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -6,9 +6,10 @@ import com.seaofnodes.simple.Parser;
 
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.GlobalCodeMotion;
 
 
-public class StopNode extends Node {
+public class StopNode extends CFGNode {
 
     public final String _src;
 
@@ -31,7 +32,7 @@ public class StopNode extends Node {
         return p.p("]");
     }
 
-    @Override public boolean isCFG() { return true; }
+    @Override public boolean blockHead() { return true; }
 
     // If a single Return, return it.
     // Otherwise, null because ambiguous.
@@ -54,13 +55,23 @@ 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 cacheIDepth(d);
+    }
+    @Override public CFGNode idom(Node dep) { return null; }
+
+    @Override public int loopDepth() { return (_loopDepth=1); }
 
     public Node addReturn(Node node) {
         return addDef(node);
     }
 
-    public StopNode iterate() { return IterPeeps.iterate(this).typeCheck(); }
+    public StopNode iterate() { return IterPeeps.iterate(this).typeCheck().GCM(); }
     public StopNode typeCheck() {
         var obs = Parser.PARSER == null ? null : Parser.PARSER._obs;
         String err = walk(n -> {
@@ -72,4 +83,13 @@ public class StopNode extends Node {
         if( obs != null ) obs.phase("TypeCheck");
         return this;
     }
+    StopNode GCM() {
+        // Break infinite loops, forcing a Never-branch to exit
+        GlobalCodeMotion.fixLoops(this);
+
+        GlobalCodeMotion.buildCFG(this);
+        return this;
+    }
+
+    @Override public Node getBlockStart() { 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 6fa87a07..1589abe7 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 
+import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
@@ -27,6 +28,7 @@ public class SubNode extends Node {
             if (i0.isConstant() && i1.isConstant())
                 return TypeInteger.constant(i0.value()-i1.value());
         }
+
         return TypeInteger.BOT;
     }
 
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..056dfba1
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java
@@ -0,0 +1,14 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.print.ExprPrinter;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+
+public class XCtrlNode extends CFGNode {
+    public XCtrlNode( ) { super(Parser.START); }
+    @Override public String label() { return "Xctrl"; }
+    @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Xctrl"); }
+    @Override  public Type compute() { return Type.XCONTROL; }
+    @Override public Node idealize() { return null; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
index 92d970d8..e65963db 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -6,13 +6,13 @@ import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.node.Node;
 import com.seaofnodes.simple.type.TypeMem;
 
-/** Chapter 10's view of the IR; browser, transport and layout are shared. */
+/** Chapter 12's view of the IR; browser, transport and layout are shared. */
 public class SimpleGraphAdapter extends GraphAdapter<Node> {
 
     @Override protected String[] edgeNames(Node n) {
         return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null;
     }
-    @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; }
+    @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : n instanceof CProjNode p ? p._idx : -1; }
 
     @Override protected Kind kind(Node n) {
         if( n instanceof StopNode ) return Kind.STOP;
@@ -25,9 +25,9 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> {
     }
 
     @Override protected Role role(Node n, int i) {
-        if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC;
+        if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof XCtrlNode ) return Role.ASSOC;
         if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA;
-        if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA;
+        if( n instanceof ProjNode || n instanceof CProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA;
         if( n instanceof RegionNode && i == 0 ) return Role.ASSOC;
         if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL;
         if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM;
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
index 5c852f94..3aabd79f 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
@@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 import java.io.IOException;
 
-/** Chapter 12's compilation context; capture and event bookkeeping are shared. */
+/** Chapter 13's compilation context; capture and event bookkeeping are shared. */
 public class SimpleGraphObserver extends GraphCapture<Node> {
     private Parser _parser;
     private Node _ret;
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index 0aa019a7..783f3f60 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -37,12 +37,11 @@ public class TypeTuple extends Type {
         return make(ts);
     }
 
-    @Override
-    public StringBuilder print(StringBuilder sb) {
-        sb.append("[");
+    @Override public StringBuilder print(StringBuilder sb) {
+        sb.append("[  ");
         for( Type t : _types )
-            t.print(sb).append(",");
-        sb.setLength(sb.length()-1);
+            t.print(sb).append(", ");
+        sb.setLength(sb.length()-2);
         sb.append("]");
         return sb;
     }
@@ -58,8 +57,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});