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>

21 files changed, 631 insertions, 56 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});
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java
index 3d568337..547c36f8 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java
@@ -11,8 +11,9 @@ public class Chapter01Test {
     @Test
     public void testSimpleProgram() {
         Parser parser = new Parser("return 1;");
-        ReturnNode ret = parser.parse();
+        StopNode stop = parser.parse();
         StartNode start = Parser.START;
+        ReturnNode ret = (ReturnNode)stop.in(0);
 
         assertTrue(ret.ctrl() instanceof ProjNode);
         Node expr = ret.expr();
diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
index 60ee8874..4085ed7e 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -12,7 +12,7 @@ public class Chapter02Test {
     public void testParseGrammar() {
         Parser parser = new Parser("return 1+2*3+-5;");
         Node._disablePeephole = true; // disable peephole so we can observe full graph
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (1+((2*3)+(-5)));", ret.print());
         GraphVisualizer gv = new GraphVisualizer();
         System.out.println(gv.generateDotOutput(parser));
@@ -22,42 +22,42 @@ public class Chapter02Test {
     @Test
     public void testAddPeephole() {
         Parser parser = new Parser("return 1+2;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 3;", ret.print());
     }
 
     @Test
     public void testSubPeephole() {
         Parser parser = new Parser("return 1-2;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return -1;", ret.print());
     }
 
     @Test
     public void testMulPeephole() {
         Parser parser = new Parser("return 2*3;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 6;", ret.print());
     }
 
     @Test
     public void testDivPeephole() {
         Parser parser = new Parser("return 6/3;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
     }
 
     @Test
     public void testMinusPeephole() {
         Parser parser = new Parser("return 6/-3;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return -2;", ret.print());
     }
 
     @Test
     public void testExample() {
         Parser parser = new Parser("return 1+2*3+-5;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
         GraphVisualizer gv = new GraphVisualizer();
         System.out.println(gv.generateDotOutput(parser));
diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 950d87fe..407fbe48 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -11,21 +11,21 @@ public class Chapter03Test {
     @Test
     public void testVarDecl() {
         Parser parser = new Parser("int a=1; return a;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testVarAdd() {
         Parser parser = new Parser("int a=1; int b=2; return a+b;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 3;", ret.print());
     }
 
     @Test
     public void testVarScope() {
         Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 4;", ret.print());
     }
 
@@ -33,7 +33,7 @@ public class Chapter03Test {
     public void testVarScopeNoPeephole() {
         Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;");
         Node._disablePeephole = true;
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         Node._disablePeephole = false;
         assertEquals("return (1+3);", ret.print());
     }
@@ -41,7 +41,7 @@ public class Chapter03Test {
     @Test
     public void testVarDist() {
         Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 8;", ret.print());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
index 9f1535b3..cde23324 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -11,49 +11,50 @@ public class Chapter04Test {
     @Test
     public void testPeephole() {
         Parser parser = new Parser("return 1+arg+2; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testPeephole2() {
         Parser parser = new Parser("return (1+arg)+2;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testAdd0() {
         Parser parser = new Parser("return 0+arg;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return arg;", ret.print());
     }
 
     @Test
     public void testAddAddMul() {
         Parser parser = new Parser("return arg+0+arg;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (arg*2);", ret.print());
     }
 
     @Test
     public void testPeephole3() {
         Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return ((arg*2)+6);", ret.print());
     }
 
     @Test
     public void testMul1() {
         Parser parser = new Parser("return 1*arg;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return arg;", ret.print());
     }
 
     @Test
     public void testVarArg() {
-        Parser parser = new Parser("return arg; #showGraph;", TypeInteger.BOT);
-        ReturnNode ret = parser.parse();
+        Parser parser = new Parser("return arg; #showGraph;");
+        StopNode stop = parser.parse();
+        ReturnNode ret = stop.ret();
         assertTrue(ret.in(0) instanceof ProjNode);
         assertTrue(ret.in(1) instanceof ProjNode);
     }
@@ -61,49 +62,49 @@ public class Chapter04Test {
     @Test
     public void testConstantArg() {
         Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2));
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
     }
 
     @Test
     public void testCompEq() {
         Parser parser = new Parser("return 3==3; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testCompEq2() {
         Parser parser = new Parser("return 3==4; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq() {
         Parser parser = new Parser("return 3!=3; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq2() {
         Parser parser = new Parser("return 3!=4; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testBug1() {
         Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testBug2() {
         Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (arg+1);", ret.print());
     }
 
@@ -120,7 +121,7 @@ public class Chapter04Test {
     @Test
     public void testBug4() {
         Parser parser = new Parser("return -arg;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (-arg);", ret.print());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
new file mode 100644
index 00000000..b5fcbeaf
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -0,0 +1,212 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+public class Chapter05Test {
+
+    @Test
+    public void testIfStmt() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+if (arg == 1)
+    a = arg+2;
+else {
+    a = arg-3;
+    #showGraph;
+}
+#showGraph;
+return a;""");
+        StopNode ret = parser.parse(true);
+        assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
+    }
+
+    @Test
+    public void testTest() {
+        Parser parser = new Parser(
+"""
+int c = 3;
+int b = 2;
+if (arg == 1) {
+    b = 3;
+    c = 4;
+}
+return c;""", TypeInteger.BOT);
+        StopNode ret = parser.parse(true);
+        assertEquals("return Phi(Region16,4,3);", ret.toString());
+    }
+
+    @Test
+    public void testReturn2() {
+        Parser parser = new Parser(
+"""
+if( arg==1 )
+    return 3;
+else
+    return 4;
+#showGraph;""", TypeInteger.BOT);
+        StopNode stop = parser.parse();
+        assertEquals("Stop[ return 3; return 4; ]", stop.toString());
+    }
+
+    @Test
+    public void testIfMergeB() {
+        Parser parser = new Parser(
+"""
+int a=arg+1;
+int b=0;
+if( arg==1 )
+    b=a;
+else
+    b=a+1;
+return a+b;""");
+        StopNode ret = parser.parse(true);
+        assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString());
+    }
+
+    @Test
+    public void testIfMerge2() {
+        Parser parser = new Parser(
+"""
+int a=arg+1;
+int b=arg+2;
+if( arg==1 )
+    b=b+a;
+else
+    a=b+1;
+return a+b;""");
+        StopNode ret = parser.parse(true);
+        assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString());
+    }
+
+    @Test
+    public void testMerge3() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+#showGraph;""", TypeInteger.BOT);
+        StopNode stop = parser.parse();
+        assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString());
+    }
+
+    @Test
+    public void testMerge4() {
+        Parser parser = new Parser(
+"""
+int a=0;
+int b=0;
+if( arg )
+    a=1;
+if( arg==0 )
+    b=2;
+return arg+a+b;
+#showGraph;""", TypeInteger.BOT);
+        StopNode stop = parser.parse();
+        assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString());
+    }
+
+    @Test
+    public void testMerge5() {
+        Parser parser = new Parser(
+"""
+int a=arg==2;
+if( arg==1 )
+{
+    a=arg==3;
+}
+return a;""");
+        StopNode ret = parser.parse(true);
+        assertEquals("return (arg==Phi(Region16,3,2));", ret.toString());
+    }
+
+    @Test
+    public void testTrue() {
+      StopNode stop = new Parser("return true;").parse();
+      assertEquals("return 1;",stop.toString());
+    }
+
+    @Test
+    public void testHalfDef() {
+        try {
+            new Parser("if( arg==1 ) int b=2; return b;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Cannot define a new name on one arm of an if",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testHalfDef2() {
+        try {
+            new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Undefined name 'b'",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testRegress1() {
+        try {
+            new Parser("if(arg==2) int a=1; else int b=2; return a;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Cannot define a new name on one arm of an if",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testBadNum() {
+        try {
+            new Parser("return 1-;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testKeyword1() {
+        try {
+            new Parser("int true=0; return true;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Expected an identifier, found 'true'",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testKeyword2() {
+        try {
+            new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Expected an identifier, found 'else'",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testKeyword3() {
+        try {
+            new Parser("int a=1; ififif(arg)inta=2;return a;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected =: (",e.getMessage());
+        }
+    }
+
+}