Chapter 5: If Statement, Phi, and Region

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: David Rubin <87927264+Rexicon226@users.noreply.github.com>

16 files changed, 388 insertions, 27 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 62b434f3..c35a4e32 100644
--- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -17,7 +17,7 @@ public class GraphVisualizer {
         // nodes in the graph.
         Collection<Node> all = findAll(parser);
         StringBuilder sb = new StringBuilder();
-        sb.append("digraph chapter04 {\n");
+        sb.append("digraph chapter05 {\n");
         sb.append("/*\n");
         sb.append(parser.src());
         sb.append("\n*/\n");
@@ -40,13 +40,15 @@ public class GraphVisualizer {
         nodes(sb, all);
 
         // Now the scopes, in a cluster no edges
-        scopes(sb, parser._scope);
+        for (ScopeNode sn: parser._xScopes)
+            scopes(sb, sn);
 
         // Walk the Node edges
         nodeEdges(sb, all);
 
         // Walk the Scope edges
-        scopeEdges(sb, parser._scope);
+        for (ScopeNode sn: parser._xScopes)
+            scopeEdges(sb, sn);
 
         sb.append("}\n");
         return sb.toString();
@@ -94,10 +96,25 @@ public class GraphVisualizer {
                 // 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 ");
                 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");
+            }
+        }
+
         sb.append("\t}\n");     // End Node cluster
     }
 
@@ -138,7 +155,13 @@ public class GraphVisualizer {
                 continue;
             int i=0;
             for( Node def : n._inputs ) {
-                if( def != null ) {
+                if( n instanceof PhiNode && def instanceof RegionNode ) {
+                    // Draw a dotted use->def edge from Phi to Region.
+                    sb.append('\t').append(n.uniqueName());
+                    sb.append(" -> ");
+                    sb.append(def.uniqueName());
+                    sb.append(" [style=dotted taillabel=").append(i).append("];\n");
+                } else if( def != null ) {
                     // Most edges land here use->def
                     sb.append('\t').append(n.uniqueName()).append(" -> ");
                     if( def instanceof ProjNode proj ) {
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index ff2c0504..80674d59 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -14,7 +14,6 @@ import java.util.*;
  */
 public class Parser {
 
-
     /**
      * A Global Static, unique to each compilation.  This is a public, so we
      * can make constants everywhere without having to thread the StartNode
@@ -24,12 +23,22 @@ public class Parser {
      */
     public static StartNode START;
 
+    public StopNode STOP;
+
     // The Lexer.  Thin wrapper over a byte[] buffer with a cursor.
     private final Lexer _lexer;
 
     /**
-     * A ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds
+     * Current ScopeNode - ScopeNodes change as we parse code, but at any point of time
+     * there is one current ScopeNode. The reason the current ScopeNode can change is to do with how
+     * we handle branching. See {@link #parseIf()}.
+     * <p>
+     * Each ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds
      * variable names to Nodes.  The top of this stack represents current scope.
+     * <p>
+     * We keep a list of all ScopeNodes so that we can show them in graphs.
+     * @see #parseIf()
+     * @see #_xScopes
      */
     public ScopeNode _scope;
 
@@ -37,17 +46,27 @@ public class Parser {
      * List of keywords disallowed as identifiers
      */
     private final HashSet<String> KEYWORDS = new HashSet<>(){{
+            add("else");
+            add("false");
+            add("if");
             add("int");
             add("return");
+            add("true");
         }};
 
 
+    /**
+     * We clone ScopeNodes when control flows branch; it is useful to have
+     * a list of all active ScopeNodes for purposes of visualization of the SoN graph
+     */
+    public final Stack<ScopeNode> _xScopes = new Stack<>();
+
     public Parser(String source, TypeInteger arg) {
         Node.reset();
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
-        START.peephole();
+        STOP = new StopNode();
     }
 
     public Parser(String source) {
@@ -66,19 +85,23 @@ public class Parser {
 
     private Node ctrl(Node n) { return _scope.ctrl(n); }
 
-    public ReturnNode parse() { return parse(false); }
-    public ReturnNode parse(boolean show) {
+    public StopNode parse() { return parse(false); }
+    public StopNode parse(boolean show) {
+        _xScopes.push(_scope);
         // Enter a new scope for the initial control and arguments
         _scope.push();
         _scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole());
         _scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole());
-        var ret = (ReturnNode) parseBlock();
+        parseBlock();
         _scope.pop();
+        _xScopes.pop();
         if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
+        STOP.peephole();
         if( show ) showGraph();
-        return ret;
+        return STOP;
     }
 
+
     /**
      * Parses a block
      *
@@ -91,21 +114,18 @@ public class Parser {
     private Node parseBlock() {
         // Enter a new scope
         _scope.push();
-        Node n = null;
-        while (!peek('}') && !_lexer.isEOF()) {
-            Node n0 = parseStatement();
-            if (n0 != null) n = n0; // Allow null returns from eg showGraph
-        };
+        while (!peek('}') && !_lexer.isEOF())
+            parseStatement();
         // Exit scope
         _scope.pop();
-        return n;
+        return null;
     }
 
     /**
      * Parses a statement
      *
      * <pre>
-     *     returnStatement | declStatement | blockStatement | expressionStatement
+     *     returnStatement | declStatement | blockStatement | ifStatement | expressionStatement
      * </pre>
      * @return a {@link Node} or {@code null}
      */
@@ -113,12 +133,60 @@ public class Parser {
         if (matchx("return")  ) return parseReturn();
         else if (matchx("int")) return parseDecl();
         else if (match ("{"  )) return require(parseBlock(),"}");
+        else if (matchx("if" )) return parseIf();
         else if (matchx("#showGraph")) return require(showGraph(),";");
         else if (matchx(";")) return null; // Empty statement
         else return parseExpressionStatement();
     }
 
     /**
+     * Parses a statement
+     *
+     * <pre>
+     *     if ( expression ) statement [else statement]
+     * </pre>
+     * @return a {@link Node}, never {@code null}
+     */
+    private Node parseIf() {
+        require("(");
+        // Parse predicate
+        var pred = require(parseExpression(), ")");
+        // IfNode takes current control and predicate
+        IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole();
+        // Setup projection nodes
+        Node ifT = new ProjNode(ifNode, 0, "True" ).peephole();
+        Node ifF = new ProjNode(ifNode, 1, "False").peephole();
+        // 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();
+        ScopeNode fScope = _scope.dup(); // Duplicate current scope
+        _xScopes.push(fScope); // For graph visualization we need all scopes
+
+        // Parse the true side
+        ctrl(ifT);              // set ctrl token to ifTrue projection
+        parseStatement();       // Parse true-side
+        ScopeNode tScope = _scope;
+
+        // Parse the false side
+        _scope = fScope;        // Restore scope, then parse else block if any
+        ctrl(ifF);              // Ctrl token is now set to ifFalse projection
+        if (matchx("else")) {
+            parseStatement();
+            fScope = _scope;
+        }
+
+        if( tScope.nIns() != ndefs || fScope.nIns() != ndefs )
+            throw error("Cannot define a new name on one arm of an if");
+
+        // Merge results
+        _scope = tScope;
+        _xScopes.pop();       // Discard pushed from graph display
+
+        return ctrl(tScope.mergeScopes(fScope));
+    }
+
+
+    /**
      * Parses a return statement; "return" already parsed.
      * The $ctrl edge is killed.
      *
@@ -129,7 +197,7 @@ public class Parser {
      */
     private Node parseReturn() {
         var expr = require(parseExpression(), ";");
-        Node ret = new ReturnNode(ctrl(), expr).peephole();
+        Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole());
         ctrl(null);             // Kill control
         return ret;
     }
@@ -254,13 +322,15 @@ public class Parser {
      * Parse a primary expression:
      *
      * <pre>
-     *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
+     *     primaryExpr : integerLiteral | Identifier | true | false | '(' expression ')'
      * </pre>
      * @return a primary {@link Node}, never {@code null}
      */
     private Node parsePrimary() {
         if( _lexer.isNumber() ) return parseIntegerLiteral();
         if( match("(") ) return require(parseExpression(), ")");
+        if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole();
+        if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole();
         String name = _lexer.matchId();
         if( name == null) throw errorSyntax("an identifier or expression");
         Node n = _scope.lookup(name);
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 5720aca4..081c9276 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -72,6 +72,24 @@ public class AddNode extends Node {
         if( lhs.in(2)._type.isConstant() && t2.isConstant() )
             return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
 
+        if( lhs.in(2) instanceof PhiNode phi && phi.allCons() &&
+            // Do we have ((x + (phi cons)) + con) ?
+            // Do we have ((x + (phi cons)) + (phi cons)) ?
+            // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+
+            // Note that this is the exact reverse of Phi pulling a common op
+            // down to reduce total op-count.  We don't get in an endless push-
+            // up push-down peephole cycle because the constants all fold first.
+            (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) {
+            Node[] ns = new Node[phi.nIns()];
+            ns[0] = phi.in(0);
+            // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+            for( int i=1; i<ns.length; i++ )
+                ns[i] = new AddNode(phi.in(i),t2.isConstant() ? rhs : rhs.in(i)).peephole();
+            String label = phi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
+            return new AddNode(lhs.in(1),new PhiNode(label,ns).peephole());
+        }
+
         // Now we sort along the spline via rotates, to gather similar things together.
 
         // Do we rotate (x + y) + z
@@ -84,15 +102,22 @@ public class AddNode extends Node {
 
     // Compare two off-spline nodes and decide what order they should be in.
     // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ?
-    // Generally constants always go right, then others.
+    // Generally constants always go right, then Phi-of-constants, then muls, then others.
     // Ties with in a category sort by node ID.
     // TRUE if swapping hi and lo.
     static boolean spline_cmp( Node hi, Node lo ) {
         if( lo._type.isConstant() ) return false;
         if( hi._type.isConstant() ) return true ;
 
+        if( lo instanceof PhiNode && lo.allCons() ) return false;
+        if( hi instanceof PhiNode && hi.allCons() ) return true ;
+
+        if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true;
+        if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false;
+
         // Same category of "others"
         return lo._nid > hi._nid;
     }
 
+    @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 05495790..7a4a087e 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -46,7 +46,7 @@ abstract public class BoolNode extends Node {
         return null;
     }
 
-    public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } }
-    public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } }
-    public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } }
+    public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } }
+    public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } }
+    public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 3b3a4436..519a8c8a 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -37,4 +37,6 @@ public class DivNode extends Node {
             return in(1);
         return null;
     }
+
+    @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
new file mode 100644
index 00000000..6124b893
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -0,0 +1,36 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.type.TypeTuple;
+
+public class IfNode extends MultiNode {
+
+    public IfNode(Node ctrl, Node pred) {
+        super(ctrl, pred);
+    }
+
+    @Override
+    public String label() { return "If"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        sb.append("if( ");
+        return in(1)._print0(sb).append(" )");
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+    public Node ctrl() { return in(0); }
+    public Node pred() { return in(1); }
+
+    @Override
+    public Type compute() {
+        return TypeTuple.IF;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 36d5eb3e..2dbdd695 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -46,4 +46,5 @@ public class MulNode extends Node {
 
         return null;
     }
+    @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 9fa0a95a..5412108b 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -349,6 +349,20 @@ public abstract class Node {
         return this;
     }
 
+    // does this node contain all constants?
+    // Ignores in(0), as is usually control.
+    boolean allCons() {
+        for( int i=1; i<nIns(); i++ )
+            if( !(in(i)._type.isConstant()) )
+                return false;
+        return true;
+    }
+
+    // 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.
+    Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); }
+
     /**
      * Used to allow repeating tests in the same JVM.  This just resets the
      * Node unique id generator, and is done as part of making a new Parser.
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
new file mode 100644
index 00000000..374e1183
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -0,0 +1,73 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+public class PhiNode extends Node {
+
+    final String _label;
+
+    public PhiNode(String label, Node... inputs) { super(inputs); _label = label; }
+
+    @Override public String label() { return "Phi_"+_label; }
+
+    @Override public String glabel() { return "&phi;_"+_label; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        sb.append("Phi(");
+        for( Node in : _inputs )
+            in._print0(sb).append(",");
+        sb.setLength(sb.length()-1);
+        sb.append(")");
+        return sb;
+    }
+
+    Node region() { return in(0); }
+
+    @Override
+    public Type compute() {
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        // Remove a "junk" Phi: Phi(x,x) is just x
+        if( same_inputs() )
+            return in(1);
+
+        // Pull "down" a common data op.  One less op in the world.  One more
+        // Phi, but Phis do not make code.
+        //   Phi(op(A,B),op(Q,R),op(X,Y)) becomes
+        //     op(Phi(A,Q,X), Phi(B,R,Y)).
+        Node op = in(1);
+        if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) {
+            Node[] lhss = new Node[nIns()];
+            Node[] rhss = new Node[nIns()];
+            lhss[0] = rhss[0] = in(0); // Set Region
+            for( int i=1; i<nIns(); i++ ) {
+                lhss[i] = in(i).in(1);
+                rhss[i] = in(i).in(2);
+            }
+            Node phi_lhs = new PhiNode(_label,lhss).peephole();
+            Node phi_rhs = new PhiNode(_label,rhss).peephole();
+            return op.copy(phi_lhs,phi_rhs);
+        }
+
+        return null;
+    }
+
+    private boolean same_op() {
+        for( int i=2; i<nIns(); i++ )
+            if( in(1).getClass() != in(i).getClass() )
+                return false;
+        return true;
+    }
+
+    private boolean same_inputs() {
+        for( int i=2; i<nIns(); i++ )
+            if( in(1) != in(i) )
+                return false;
+        return true;
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 2f49fe91..2826d192 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -23,7 +23,7 @@ public class ProjNode extends Node {
     @Override
     StringBuilder _print1(StringBuilder sb) { return sb.append(_label); }
 
-    @Override public boolean isCFG() { return _idx==0; }
+    @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
 
     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
new file mode 100644
index 00000000..5d520d65
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -0,0 +1,27 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+public class RegionNode extends Node {
+    public RegionNode(Node... inputs) { super(inputs); }
+
+    @Override
+    public String label() { return "Region"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return sb.append(label()).append(_nid);
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+    @Override
+    public Type compute() {
+        return Type.CONTROL;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 8ffeac64..32045fbc 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -131,4 +131,45 @@ public class ScopeNode extends Node {
      */
     public Node ctrl(Node n) { return setDef(0,n); }
 
+    /**
+     * Duplicate a ScopeNode; including all levels, up to Nodes.  So this is
+     * neither shallow (would dup the Scope but not the internal HashMap
+     * tables), nor deep (would dup the Scope, the HashMap tables, but then
+     * also the program Nodes).
+     * <p>
+     * The new Scope is a full-fledged Node with proper use<->def edges.
+     */
+    public ScopeNode dup() {
+        ScopeNode dup = new ScopeNode();
+        // Our goals are:
+        // 1) duplicate the name bindings of the ScopeNode across all stack levels
+        // 2) Make the new ScopeNode a user of all the nodes bound
+        // 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));
+        return dup;
+    }
+
+    /**
+     * Merges the names whose node bindings differ, by creating Phi node for such names
+     * The names could occur at all stack levels, but a given name can only differ in the
+     * innermost stack level where the name is bound.
+     *
+     * @param that The ScopeNode to be merged into this
+     * @return A new node representing the merge point
+     */
+    public Node mergeScopes(ScopeNode that) {
+        RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole());
+        String[] ns = reverseNames();
+        // Note that we skip i==0, which is bound to '$ctrl'
+        for (int i = 1; i < nIns(); i++)
+            if( in(i) != that.in(i) ) // No need for redundant Phis
+                setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole());
+        that.kill();            // Kill merged scope
+        return r;
+    }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
new file mode 100644
index 00000000..a30256f9
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -0,0 +1,46 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+public class StopNode extends Node {
+    public StopNode(Node... inputs) {
+        super(inputs);
+    }
+
+    @Override
+    public String label() {
+        return "Stop";
+    }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        if( ret()!=null ) return ret()._print0(sb);
+        sb.append("Stop[ ");
+        for( Node ret : _inputs )
+            ret._print0(sb).append(" ");
+        return sb.append("]");
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+    // If a single Return, return it.
+    // Otherwise, null because ambiguous.
+    public ReturnNode ret() {
+        return nIns()==1 ? (ReturnNode)in(0) : null;
+    }
+
+    @Override
+    public Type compute() {
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+
+    public Node addReturn(Node node) {
+        return addDef(node);
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 58d757ea..475b3790 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -37,4 +37,5 @@ public class SubNode extends Node {
         return null;
     }
 
+    @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index 1687f65a..d0916312 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -43,7 +43,7 @@ public class Type {
 
     public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
 
-    public Type meet(Type other) { return Type.BOTTOM; }
+    public Type meet(Type other) { return BOTTOM; }
 
     @Override
     public final String toString() {
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index 25663dda..33417eb2 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -16,11 +16,13 @@ public class TypeTuple extends Type {
 
     @Override
     public StringBuilder _print(StringBuilder sb) {
-        sb.append("[ ");
+        sb.append("[");
         for( Type t : _types )
             t._print(sb).append(",");
         sb.setLength(sb.length()-1);
         sb.append("]");
         return sb;
     }
+
+    public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL});
 }