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>

21 files changed, 360 insertions, 99 deletions

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; }
+}