Chapter 7: While Statement

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

21 files changed, 486 insertions, 110 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index b30dd450..07f1af21 100644
--- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -11,13 +11,22 @@ import java.util.*;
  */
 public class GraphVisualizer {
 
+    /**
+     * If set to true we put the control nodes in a separate cluster from
+     * data nodes.
+     */
+    boolean _separateControlCluster = false;
+
+    public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; }
+    public GraphVisualizer() { this(false); }
+
     public String generateDotOutput(Parser parser) {
 
         // Since the graph has cycles, we need to create a flat list of all the
         // nodes in the graph.
         Collection<Node> all = findAll(parser);
         StringBuilder sb = new StringBuilder();
-        sb.append("digraph chapter06 {\n");
+        sb.append("digraph chapter07 {\n");
         sb.append("/*\n");
         sb.append(parser.src());
         sb.append("\n*/\n");
@@ -36,42 +45,48 @@ public class GraphVisualizer {
         // nodes much prettier to look at.
         sb.append("\tconcentrate=\"true\";\n");
 
+        // Force nested scopes to order
+        sb.append("\tcompound=\"true\";\n");
+
         // Just the Nodes first, in a cluster no edges
         nodes(sb, all);
 
         // Now the scopes, in a cluster no edges
-        for (ScopeNode sn: parser._xScopes)
-            scopes(sb, sn);
+        for( ScopeNode scope : parser._xScopes )
+            scope( sb, scope );
 
         // Walk the Node edges
         nodeEdges(sb, all);
 
-        // Walk the Scope edges
-        for (ScopeNode sn: parser._xScopes)
-            scopeEdges(sb, sn);
+        // Walk the active Scope edges
+        for( ScopeNode scope : parser._xScopes )
+            scopeEdges( sb, scope );
 
         sb.append("}\n");
         return sb.toString();
     }
 
-
-    private void nodes(StringBuilder sb, Collection<Node> all) {
+    private void nodesByCluster(StringBuilder sb, boolean doCtrl, Collection<Node> all) {
+        if (!_separateControlCluster && doCtrl) // all nodes in 1 cluster
+            return;
         // Just the Nodes first, in a cluster no edges
-        sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
-        for( Node n : all ) {
-            if( n instanceof ProjNode || n instanceof ScopeNode )
+        sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
+        for (Node n : all) {
+            if (n instanceof ProjNode || n instanceof ScopeNode)
                 continue; // Do not emit, rolled into MultiNode or Scope cluster already
+            if (_separateControlCluster && doCtrl && !n.isCFG()) continue;
+            if (_separateControlCluster && !doCtrl && n.isCFG()) continue;
             sb.append("\t\t").append(n.uniqueName()).append(" [ ");
             String lab = n.glabel();
-            if( n instanceof MultiNode ) {
+            if (n instanceof MultiNode) {
                 // Make a box with the MultiNode on top, and all the projections on the bottom
                 sb.append("shape=plaintext label=<\n");
                 sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n");
                 sb.append("\t\t\t<TR><TD BGCOLOR=\"yellow\">").append(lab).append("</TD></TR>\n");
                 sb.append("\t\t\t<TR>");
                 boolean doProjTable = false;
-                for( Node use : n._outputs ) {
-                    if( use instanceof ProjNode proj ) {
+                for (Node use : n._outputs) {
+                    if (use instanceof ProjNode proj) {
                         if (!doProjTable) {
                             doProjTable = true;
                             sb.append("<TD>").append("\n");
@@ -79,7 +94,7 @@ public class GraphVisualizer {
                             sb.append("\t\t\t\t<TR>");
                         }
                         sb.append("<TD PORT=\"p").append(proj._idx).append("\"");
-                        if( proj.isCFG() ) sb.append(" BGCOLOR=\"yellow\"");
+                        if (proj.isCFG()) sb.append(" BGCOLOR=\"yellow\"");
                         sb.append(">").append(proj.glabel()).append("</TD>");
                     }
                 }
@@ -94,41 +109,46 @@ public class GraphVisualizer {
             } else {
                 // control nodes have box shape
                 // other nodes are ellipses, i.e. default shape
-                if( n.isCFG() )
-                    sb.append("shape=box style=filled fillcolor=yellow ");
-                if( n instanceof PhiNode )
-                    sb.append("style=filled fillcolor=lightyellow ");
+                if (n.isCFG()) sb.append("shape=box style=filled fillcolor=yellow ");
+                else if (n instanceof PhiNode) sb.append("style=filled fillcolor=lightyellow ");
                 sb.append("label=\"").append(lab).append("\" ");
             }
             sb.append("];\n");
         }
-
-        // Force Region & Phis to line up
-        for( Node n : all ) {
-            if( n instanceof RegionNode region ) {
-                sb.append("\t\t{ rank=same; ");
-                sb.append(region).append(";")     ;
-                for( Node phi : region._outputs )
-                    if( phi instanceof PhiNode )
-                        sb.append(phi.uniqueName()).append(";");
-                sb.append("}\n");
+        if (!_separateControlCluster) {
+            // Force Region & Phis to line up
+            for (Node n : all) {
+                if (n instanceof RegionNode region) {
+                    sb.append("\t\t{ rank=same; ");
+                    sb.append(region).append(";");
+                    for (Node phi : region._outputs)
+                        if (phi instanceof PhiNode) sb.append(phi.uniqueName()).append(";");
+                    sb.append("}\n");
+                }
             }
         }
-
         sb.append("\t}\n");     // End Node cluster
     }
 
-    private void scopes( StringBuilder sb, ScopeNode scopenode) {
+    private void nodes(StringBuilder sb, Collection<Node> all) {
+        nodesByCluster(sb, true, all);
+        nodesByCluster(sb, false, all);
+    }
+
+    // Build a nested scope display, walking the _prev edge
+    private void scope( StringBuilder sb, ScopeNode scope ) {
         sb.append("\tnode [shape=plaintext];\n");
-        int level=0;
-        for( HashMap<String,Integer> scope : scopenode._scopes ) {
-            String scopeName = makeScopeName(scopenode, level);
+        int level=1;
+        for( int idx = scope._scopes.size()-1; idx>=0; idx-- ) {
+            var syms = scope._scopes.get(idx);
+            String scopeName = makeScopeName(scope, level);
             sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name
             sb.append("\t\t").append(scopeName).append(" [label=<\n");
             sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n");
             // Add the scope level
-            sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>");
-            for( String name : scope.keySet() )
+            int scopeLevel = scope._scopes.size()-level;
+            sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(scopeLevel).append("</TD>");
+            for(String name: syms.keySet())
                 sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>");
             sb.append("</TR>\n");
             sb.append("\t\t\t</TABLE>>];\n");
@@ -137,7 +157,7 @@ public class GraphVisualizer {
         // Scope clusters nest, so the graphics shows the nested scopes, so
         // they are not closed as they are printed; so they just keep nesting.
         // We close them all at once here.
-        sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters
+        sb.append( "\t}\n".repeat( level-1 ) ); // End all Scope clusters
     }
 
     private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; }
@@ -153,8 +173,8 @@ public class GraphVisualizer {
             // ScopeNodes are done separately
             if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode )
                 continue;
-            int i=0;
-            for( Node def : n._inputs ) {
+            for( int i=0; i<n.nIns(); i++ ) {
+                Node def = n.in(i);
                 if( n instanceof PhiNode && def instanceof RegionNode ) {
                     // Draw a dotted use->def edge from Phi to Region.
                     sb.append('\t').append(n.uniqueName());
@@ -173,21 +193,25 @@ public class GraphVisualizer {
                     // control edges are colored red
                     if( def.isCFG() )
                         sb.append(" color=red");
+                    // Backedges do not add a ranking constraint
+                    if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) )
+                        sb.append(" constraint=false");
                     sb.append("];\n");
                 }
-                i++;
             }
         }
     }
 
     // Walk the scope edges
-    private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) {
+    private void scopeEdges( StringBuilder sb, ScopeNode scope ) {
         sb.append("\tedge [style=dashed color=cornflowerblue];\n");
-        int level=0;
-        for( HashMap<String,Integer> scope : scopenode._scopes ) {
-            String scopeName = makeScopeName(scopenode, level);
-            for( String name : scope.keySet() ) {
-                Node def = scopenode.in(scope.get(name));
+        int level=1;
+        for( int i = scope._scopes.size()-1; i>=0; i-- ) {
+            var syms = scope._scopes.get(i);
+            String scopeName = makeScopeName(scope, level);
+            for( String name : syms.keySet() ) {
+                int idx = syms.get(name);
+                Node def = scope.in(idx);
                 if( def==null ) continue;
                 sb.append("\t")
                   .append(scopeName).append(":")
diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java
new file mode 100644
index 00000000..2a6dbefd
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -0,0 +1,124 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.LoopNode;
+import com.seaofnodes.simple.node.Node;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+
+public class IRPrinter {
+
+    // Another bulk pretty-printer.  Makes more effort at basic-block grouping.
+    public static String prettyPrint(Node node, int depth) {
+        // First, a Breadth First Search at a fixed depth.
+        BFS bfs = new BFS(node,depth);
+        // Convert just that set to a post-order
+        ArrayList<Node> rpos = new ArrayList<>();
+        BitSet visit = new BitSet();
+        for( int i=bfs._lim; i< bfs._bfs.size(); i++ )
+            postOrd( bfs._bfs.get(i), rpos, visit, bfs._bs);
+        // Reverse the post-order walk
+        StringBuilder sb = new StringBuilder();
+        boolean gap=false;
+        for( int i=rpos.size()-1; i>=0; i-- ) {
+            Node n = rpos.get(i);
+            if( n.isCFG() || n.isMultiHead() ) {
+                if( !gap ) sb.append("\n"); // Blank before multihead
+                n._printLine(sb); // Print head
+                while( --i >= 0 ) {
+                    Node t = rpos.get(i);
+                    if( !t.isMultiTail() ) { i++; break; }
+                    t._printLine(sb);
+                }
+                sb.append("\n"); // Blank after multitail
+                gap = true;
+            } else {
+                n._printLine( sb );
+                gap = false;
+            }
+        }
+        return sb.toString();
+    }
+
+    private static void postOrd(Node n, ArrayList<Node> rpos, BitSet visit, BitSet bfs) {
+        if( !bfs.get(n._nid) )
+            return;  // Not in the BFS visit
+        if( visit.get(n._nid) ) return; // Already post-order walked
+        visit.set(n._nid);
+        // First walk the CFG, then everything
+        if( n.isCFG() ) {
+            for( Node use : n._outputs )
+                if( use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) )
+                    postOrd(use, rpos,visit,bfs);
+            for( Node use : n._outputs )
+                if( use.isCFG() )
+                    postOrd(use,rpos,visit,bfs);
+        }
+        for( Node use : n._outputs )
+            postOrd(use, rpos,visit,bfs);
+        // Post-order
+        rpos.add(n);
+    }
+
+    // Breadth-first search, broken out in a class to keep in more independent.
+    // Maintains a root-set of Nodes at the limit (or past by 1 if MultiHead).
+    public static class BFS {
+        // A breadth first search, plus MultiHeads for any MultiTails
+        public final ArrayList<Node> _bfs;
+        public final BitSet _bs; // Visited members by node id
+        public final int _depth; // Depth limit
+        public final int _lim; // From here to _bfs._len can be roots for a reverse search
+        public BFS( Node base, int d ) {
+            _depth = d;
+            _bfs = new ArrayList<>();
+            _bs = new BitSet();
+
+            add(base);                 // Prime the pump
+            int idx=0, lim=1;          // Limit is where depth counter changes
+            while( idx < _bfs.size() ) { // Ran out of nodes below depth
+                Node n = _bfs.get(idx++);
+                for( Node def : n._inputs )
+                    if( def!=null && !_bs.get(def._nid) )
+                        add(def);
+                if( idx==lim ) {    // Depth counter changes at limit
+                    if( --d < 0 )
+                        break;      // Ran out of depth
+                    lim = _bfs.size();  // New depth limit
+                }
+            }
+            // Toss things past the limit except multi-heads
+            while( idx < _bfs.size() ) {
+                Node n = _bfs.get(idx);
+                if( n.isMultiHead() ) idx++;
+                else del(idx);
+            }
+            // Root set is any node with no inputs in the visited set
+            lim = _bfs.size();
+            for( int i=_bfs.size()-1; i>=0; i-- )
+                if( !any_visited(_bfs.get(i)) )
+                    swap( i,--lim);
+            _lim = lim;
+        }
+        void swap( int x, int y ) {
+            if( x==y ) return;
+            Node tx = _bfs.get(x);
+            Node ty = _bfs.get(y);
+            _bfs.set(x,ty);
+            _bfs.set(y,tx);
+        }
+        void add(Node n) {
+            _bfs.add(n);
+            _bs.set(n._nid);
+        }
+        void del(int idx) {
+            Node n = Utils.del(_bfs, idx);
+            _bs.clear(n._nid);
+        }
+        boolean any_visited( Node n ) {
+            for( Node def : n._inputs )
+                if( def!=null && _bs.get(def._nid) )
+                    return true;
+            return false;
+        }
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 1a15efa3..cfb4deb4 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -52,6 +52,7 @@ public class Parser {
             add("int");
             add("return");
             add("true");
+            add("while");
         }};
 
 
@@ -134,12 +135,81 @@ public class Parser {
         else if (matchx("int")) return parseDecl();
         else if (match ("{"  )) return require(parseBlock(),"}");
         else if (matchx("if" )) return parseIf();
+        else if (matchx("while")) return parseWhile();
         else if (matchx("#showGraph")) return require(showGraph(),";");
         else if (matchx(";")) return null; // Empty statement
         else return parseExpressionStatement();
     }
 
     /**
+     * Parses a while statement
+     *
+     * <pre>
+     *     while ( expression ) statement
+     * </pre>
+     * @return a {@link Node}, never {@code null}
+     */
+    private Node parseWhile() {
+        require("(");
+
+        // Loop region has two control inputs, the first is the entry
+        // point, and second is back edge that is set after loop is parsed
+        // (see end_loop() call below).  Note that the absence of back edge is
+        // used as an indicator to switch off peepholes of the region and
+        // associated phis; see {@code inProgress()}.
+
+        ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here
+
+        // At loop head, we clone the current Scope (this includes all
+        // names in every nesting level within the Scope).
+        // We create phis eagerly for all the names we find, see dup().
+
+        // Save the current scope as the loop head
+        ScopeNode head = _scope.keep();
+        // Clone the head Scope to create a new Scope for the body.
+        // Create phis eagerly as part of cloning
+        _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis
+
+        // Parse predicate
+        var pred = require(parseExpression(), ")");
+        // IfNode takes current control and predicate
+        IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole();
+        // Setup projection nodes
+        Node ifT = new ProjNode(ifNode, 0, "True" ).peephole();
+        ifNode.unkeep();
+        Node ifF = new ProjNode(ifNode, 1, "False").peephole();
+
+        // Clone the body Scope to create the exit Scope
+        // which accounts for any side effects in the predicate
+        // The exit Scope will be the final scope after the loop,
+        // And its control input is the False branch of the loop predicate
+        // Note that body Scope is still our current scope
+        var exit = _scope.dup();
+        _xScopes.push(exit);
+        exit.ctrl(ifF);
+
+        // Parse the true side, which corresponds to loop body
+        // Our current scope is the body Scope
+        ctrl(ifT);              // set ctrl token to ifTrue projection
+        parseStatement();       // Parse loop body
+
+        // The true branch loops back, so whatever is current control (_scope.ctrl) gets
+        // added to head loop as input. endLoop() updates the head scope,
+        // and goes through all the phis that were created earlier. For each
+        // phi, it sets the second input to the corresponding input from the back edge.
+        // If the phi is redundant, it is replaced by its sole input.
+        head.endLoop(_scope, exit);
+        head.unkeep().kill();
+
+        _xScopes.pop();       // Cleanup
+        _xScopes.pop();       // Cleanup
+
+        // At exit the false control is the current control, and
+        // the scope is the exit scope after the exit test.
+        return (_scope = exit);
+    }
+
+    /**
      * Parses a statement
      *
      * <pre>
@@ -369,7 +439,7 @@ public class Parser {
 
     // Require an exact match
     private void require(String syntax) { require(null, syntax); }
-    private Node require(Node n, String syntax) {
+    private <N extends Node> N require(N n, String syntax) {
         if (match(syntax)) return n;
         throw errorSyntax(syntax);
     }
@@ -378,7 +448,7 @@ public class Parser {
         return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
     }
 
-    static RuntimeException error(String errorMessage) {
+    public static RuntimeException error( String errorMessage ) {
         return new RuntimeException(errorMessage);
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index b37785f6..8f3e5a98 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.*;
 
+import java.util.BitSet;
+
 public class AddNode extends Node {
     public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
@@ -10,9 +12,9 @@ public class AddNode extends Node {
     @Override public String glabel() { return "+"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append("+"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("+"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index a9ec6838..0c32d50d 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 abstract public class BoolNode extends Node {
 
     public BoolNode(Node lhs, Node rhs) {
@@ -18,9 +20,9 @@ abstract public class BoolNode extends Node {
     public String glabel() { return op(); }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append(op()));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append(op()), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 1086037d..13006bfb 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.Type;
 
+import java.util.BitSet;
+
 /**
  * A Constant node represents a constant value.  At present, the only constants
  * that we allow are integer literals; therefore Constants contain an integer
@@ -29,10 +31,12 @@ public class ConstantNode extends Node {
     public String uniqueName() { return "Con_" + _nid; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
         return _con._print(sb);
     }
 
+    @Override public boolean isMultiTail() { return true; }
+
     @Override
     public Type compute() { return _con; }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 519a8c8a..7207fd48 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class DivNode extends Node {
     public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
@@ -11,9 +13,9 @@ public class DivNode extends Node {
     @Override public String glabel() { return "//"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append("/"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("/"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 34846e99..0f414c08 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -4,6 +4,8 @@ import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 import com.seaofnodes.simple.type.TypeTuple;
 
+import java.util.BitSet;
+
 public class IfNode extends MultiNode {
 
     public IfNode(Node ctrl, Node pred) {
@@ -14,12 +16,13 @@ public class IfNode extends MultiNode {
     public String label() { return "If"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
         sb.append("if( ");
-        return in(1)._print0(sb).append(" )");
+        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); }
     public Node pred() { return in(1); }
@@ -27,7 +30,8 @@ public class IfNode extends MultiNode {
     @Override
     public Type compute() {
         // If the If node is not reachable then neither is any following Proj
-        if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER;
+        if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM )
+            return TypeTuple.IF_NEITHER;
         // If constant is 0 then false branch is reachable
         // Else true branch is reachable
         if (pred()._type instanceof TypeInteger ti && ti.isConstant()) {
diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
new file mode 100644
index 00000000..81f707ec
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+import java.util.BitSet;
+
+public class LoopNode extends RegionNode {
+
+    public LoopNode( Node entry ) { super(null,entry,null); }
+
+    Node entry() { return in(1); }
+    Node back () { return in(2); }
+
+    @Override
+    public String label() { return "Loop"; }
+
+    @Override
+    public Type compute() {
+        return inProgress() ? Type.CONTROL : super.compute();
+    }
+
+    @Override
+    public Node idealize() {
+        return inProgress() ? null : super.idealize();
+    }
+
+    @Override Node idom() { return entry(); }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 0d59ef25..3d944fd4 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class MinusNode extends Node {
     public MinusNode(Node in) { super(null, in); }
 
@@ -11,8 +13,8 @@ public class MinusNode extends Node {
     @Override public String glabel() { return "-"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("(-"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("(-"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 0380c079..2e701a4e 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class MulNode extends Node {
     public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
@@ -11,9 +13,9 @@ public class MulNode extends Node {
     @Override public String glabel() { return "*"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append("*"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("*"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 97ba68ab..35b07781 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -98,18 +98,51 @@ public abstract class Node {
     // tik-tok style; the common _print0 calls the per-Node _print1, which
     // calls back to _print0;
     public final String print() {
-        return _print0(new StringBuilder()).toString();
+        return _print0(new StringBuilder(), new BitSet()).toString();
     }
-    // This is the common print: check for DEAD and print "DEAD" else call the
-    // per-Node print1.
-    final StringBuilder _print0(StringBuilder sb) {
+    // This is the common print: check for repeats, check for DEAD and print
+    // "DEAD" else call the per-Node print1.
+    final StringBuilder _print0(StringBuilder sb, BitSet visited) {
+        if (visited.get(_nid))
+            return sb.append(label());
+        visited.set(_nid);
         return isDead()
             ? sb.append(uniqueName()).append(":DEAD")
-            : _print1(sb);
+            : _print1(sb, visited);
+    }
+    // Every Node implements this; a partial-line recursive print
+    abstract StringBuilder _print1(StringBuilder sb, BitSet visited);
+
+
+    // Print a node on 1 line, columnar aligned, as:
+    // NNID NNAME DDEF DDEF  [[  UUSE UUSE  ]]  TYPE
+    // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt
+    public void _printLine(StringBuilder sb ) {
+        sb.append("%4d %-7.7s ".formatted(_nid,label()));
+        if( _inputs==null ) {
+            sb.append("DEAD\n");
+            return;
+        }
+        for( Node def : _inputs )
+            sb.append(def==null ? "____ " : "%4d ".formatted(def._nid));
+        for( int i = _inputs.size(); i<3; i++ )
+            sb.append("     ");
+        sb.append(" [[  ");
+        for( Node use : _outputs )
+            sb.append("%4d ".formatted(use._nid));
+        int lim = 5 - Math.max(_inputs.size(),3);
+        for( int i = _outputs.size(); i<lim; i++ )
+            sb.append("     ");
+        sb.append(" ]]  ");
+        if( _type!= null ) _type._print(sb);
+        sb.append("\n");
     }
-    // Every Node implements this.
-    abstract StringBuilder _print1(StringBuilder sb);
 
+    public boolean isMultiHead() { return false; }
+    public boolean isMultiTail() { return false; }
+
+    // ------------------------------------------------------------------------
+    // Graph Node & Edge manipulation
 
     /**
      * Gets the ith input node
@@ -230,6 +263,20 @@ public abstract class Node {
     public <N extends Node> N keep() { return addUse(null); }
     // Remove bogus null.
     public <N extends Node> N unkeep() { delUse(null); return (N)this; }
+
+
+    // Replace self with nnn in the graph, making 'this' go dead
+    void subsume( Node nnn ) {
+        assert nnn!=this;
+        while( nOuts() > 0 ) {
+            Node n = _outputs.removeLast();
+            int idx = Utils.find(n._inputs, this);
+            n._inputs.set(idx,nnn);
+            nnn.addUse(n);
+        }
+        kill();
+    }
+
     // ------------------------------------------------------------------------
     // Graph-based optimizations
 
diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java
index e3683646..39df410d 100644
--- a/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class NotNode extends Node {
     public NotNode(Node in) { super(null, in); }
 
@@ -11,8 +13,8 @@ public class NotNode extends Node {
     @Override public String glabel() { return "!"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("(!"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("(!"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 15088e08..2a4ff52a 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
 
+import java.util.BitSet;
+
 public class PhiNode extends Node {
 
     final String _label;
@@ -13,19 +15,27 @@ public class PhiNode extends Node {
     @Override public String glabel() { return "&phi;_"+_label; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        if( region().inProgress() )
+            sb.append("Z");
         sb.append("Phi(");
-        for( Node in : _inputs )
-            in._print0(sb).append(",");
+        for( Node in : _inputs ) {
+            if (in == null) sb.append("____");
+            else in._print0(sb, visited);
+            sb.append(",");
+        }
         sb.setLength(sb.length()-1);
         sb.append(")");
         return sb;
     }
 
-    Node region() { return in(0); }
+    RegionNode region() { return (RegionNode)in(0); }
+    @Override public boolean isMultiTail() { return true; }
 
     @Override
     public Type compute() {
+        if( !(region() instanceof RegionNode r) || r.inProgress() )
+            return Type.BOTTOM;
         Type t = Type.TOP;
         for (int i = 1; i < nIns(); i++)
             t = t.meet(in(i)._type);
@@ -34,6 +44,9 @@ public class PhiNode extends Node {
 
     @Override
     public Node idealize() {
+        if( !(region() instanceof RegionNode r ) || r.inProgress() )
+            return null;
+
         // If we have only a single unique input, become it.
         Node live = singleUniqueInput();
         if (live != null)
@@ -79,5 +92,10 @@ public class PhiNode extends Node {
         return live;
     }
 
-
+    @Override
+    boolean allCons() {
+        if( !(region() instanceof RegionNode r) || r.inProgress() )
+            return false;
+        return super.allCons();
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 85f28037..3c3f73b8 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeTuple;
 
+import java.util.BitSet;
+
 public class ProjNode extends Node {
 
     // Which slice of the incoming multi-part value
@@ -21,9 +23,10 @@ public class ProjNode extends Node {
     public String label() { return _label; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) { return sb.append(_label); }
+    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(); }
 
     public MultiNode ctrl() { return (MultiNode)in(0); }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index bb7998a3..acaadaf1 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -3,21 +3,26 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
+import java.util.BitSet;
+
 public class RegionNode extends Node {
-    public RegionNode(Node... inputs) { super(inputs); }
+
+    public RegionNode(Node... nodes) { super(nodes); }
 
     @Override
     public String label() { return "Region"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
         return sb.append(label()).append(_nid);
     }
 
     @Override public boolean isCFG() { return true; }
+    @Override public boolean isMultiHead() { return true; }
 
     @Override
     public Type compute() {
+        if( inProgress() ) return Type.CONTROL;
         Type t = Type.XCONTROL;
         for (int i = 1; i < nIns(); i++)
             t = t.meet(in(i)._type);
@@ -26,6 +31,7 @@ public class RegionNode extends Node {
 
     @Override
     public Node idealize() {
+        if( inProgress() ) return null;
         int path = findDeadInput();
         if( path != 0 ) {
             for( Node phi : _outputs )
@@ -72,4 +78,9 @@ public class RegionNode extends Node {
         _idepth = lhs._idepth+1;
         return (_idom=lhs);
     }
+
+    // True if last input is null
+    public final boolean inProgress() {
+        return in(nIns()-1) == null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 6130d050..312058b9 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.*;
 
+import java.util.BitSet;
+
 /**
  * The Return node has two inputs.  The first input is a control node and the
  * second is the data node that supplies the return value.
@@ -24,8 +26,8 @@ public class ReturnNode extends Node {
     public String label() { return "Return"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        return expr()._print0(sb.append("return ")).append(";");
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        return expr()._print0(sb.append("return "), visited).append(";");
     }
 
     @Override public boolean isCFG() { return true; }
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index a7a04a42..a4fcbe65 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -33,22 +33,16 @@ public class ScopeNode extends Node {
     @Override public String label() { return "Scope"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        sb.append(label());
-        for( HashMap<String,Integer> scope : _scopes ) {
-            sb.append("[");
-            boolean first=true;
-            for( String name : scope.keySet() ) {
-                if( !first ) sb.append(", ");
-                first=false;
-                sb.append(name).append(":");
-                Node n = in(scope.get(name));
-                if( n==null ) sb.append("null");
-                else n._print0(sb);
-            }
-            sb.append("]");
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        sb.append("Scope[ ");
+        String[] names = reverseNames();
+        for( int j=0; j<nIns(); j++ ) {
+            sb.append(names[j]).append(":");
+            Node n = in(j);
+            n._print0(sb, visited).append(" ");
         }
-        return sb;
+        sb.setLength(sb.length()-1);
+        return sb.append("]");
     }
 
     /**
@@ -139,7 +133,8 @@ public class ScopeNode extends Node {
      * <p>
      * The new Scope is a full-fledged Node with proper use<->def edges.
      */
-    public ScopeNode dup() {
+    public ScopeNode dup() { return dup(false); }
+    public ScopeNode dup(boolean loop) {
         ScopeNode dup = new ScopeNode();
         // Our goals are:
         // 1) duplicate the name bindings of the ScopeNode across all stack levels
@@ -147,9 +142,19 @@ public class ScopeNode extends Node {
         // 3) Ensure that the order of defs is the same to allow easy merging
         for( HashMap<String,Integer> syms : _scopes )
             dup._scopes.push(new HashMap<>(syms));
+
         dup.addDef(ctrl());      // Control input is just copied
-        for( int i=1; i<nIns(); i++ )
-            dup.addDef(in(i));
+        for( int i=1; i<nIns(); i++ ) {
+            if ( !loop ) { dup.addDef(in(i)); }
+            else {
+                String[] names = reverseNames(); // Get the variable names
+                // Create a phi node with second input as null - to be filled in
+                // by endLoop() below
+                dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole());
+                // Ensure our node has the same phi in case we created one
+                setDef(i, dup.in(i));
+            }
+        }
         return dup;
     }
 
@@ -172,4 +177,21 @@ public class ScopeNode extends Node {
         return r.unkeep().peephole();
     }
 
+    // Merge the backedge scope into this loop head scope
+    // We set the second input to the phi from the back edge (i.e. loop body)
+    public void endLoop(ScopeNode back, ScopeNode exit ) {
+        Node ctrl = ctrl();
+        assert ctrl instanceof LoopNode loop && loop.inProgress();
+        ctrl.setDef(2,back.ctrl());
+        for( int i=1; i<nIns(); i++ ) {
+            PhiNode phi = (PhiNode)in(i);
+            assert phi.region()==ctrl && phi.in(2)==null;
+            phi.setDef(2,back.in(i));
+            // Do an eager useless-phi removal
+            Node in = phi.peephole();
+            if( in != phi )
+                phi.subsume(in);
+        }
+        back.kill();            // Loop backedge is dead
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index c5a45876..01f1485a 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeTuple;
 
+import java.util.BitSet;
+
 /**
  * The Start node represents the start of the function.  For now, we do not
  * have any inputs to Start because our function does not yet accept
@@ -24,11 +26,12 @@ public class StartNode extends MultiNode {
     public String label() { return "Start"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
       return sb.append(label());
     }
 
     @Override public boolean isCFG() { return true; }
+    @Override public boolean isMultiHead() { return true; }
 
     @Override
     public TypeTuple compute() { return _args; }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 01574dc7..417790d9 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
 
+import java.util.BitSet;
+
 public class StopNode extends Node {
     public StopNode(Node... inputs) {
         super(inputs);
@@ -13,11 +15,11 @@ public class StopNode extends Node {
     }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        if( ret()!=null ) return ret()._print0(sb);
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        if( ret()!=null ) return ret()._print0(sb, visited);
         sb.append("Stop[ ");
         for( Node ret : _inputs )
-            ret._print0(sb).append(" ");
+            ret._print0(sb, visited).append(" ");
         return sb.append("]");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 475b3790..af66b950 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class SubNode extends Node {
     public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
@@ -11,9 +13,9 @@ public class SubNode extends Node {
     @Override public String glabel() { return "-"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append("-"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("-"), visited);
         return sb.append(")");
     }