Chapter 5: If Statement, Phi, and Region

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
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: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.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: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: David Rubin <87927264+Rexicon226@users.noreply.github.com>

22 files changed, 645 insertions, 73 deletions

diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 487afee9..359d0175 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.graph.GraphObserver;
+
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 
@@ -15,6 +16,11 @@ import java.util.*;
  */
 public class Parser {
 
+    // Current compilation context; the observer belongs to the parser.
+    public static Parser PARSER;
+    public GraphObserver<Node> _obs;
+    public int pos() { return _lexer._position; }
+
 
     /**
      * A Global Static, unique to each compilation.  This is a public, so we
@@ -24,17 +30,23 @@ public class Parser {
      * To make the compiler multithreaded, this field will have to move into a TLS.
      */
     public static StartNode START;
-    // Current compilation context, like START; the observer belongs to the parser.
-    public static Parser PARSER;
-    public GraphObserver<Node> _obs;
-    public int pos() { return _lexer._position; }
+
+    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;
 
@@ -42,18 +54,28 @@ 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) {
         PARSER = this;
         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) {
@@ -72,17 +94,21 @@ public class Parser {
 
     private Node ctrl(Node n) { return _scope.ctrl(n); }
 
-    public ReturnNode parse() {
+    public StopNode parse() {
+        _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());
-        return ret;
+        STOP.peephole();
+        return STOP;
     }
 
+
     /**
      * Parses a block
      *
@@ -95,21 +121,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; // Empty statements can return null
-        };
+        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}
      */
@@ -117,11 +140,59 @@ 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(";")) 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
+        fScope.ctrl(ifF);       // The pending arm already starts at False
+        _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
+        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.
      *
@@ -132,7 +203,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;
     }
@@ -250,13 +321,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 0291a900..2772c4c5 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -70,6 +70,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 spine via rotates, to gather similar things together.
 
         // Do we rotate (x + y) + z
@@ -82,15 +100,22 @@ public class AddNode extends Node {
 
     // Compare two off-spine 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 spine_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 143a6fde..87acc6cc 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -43,7 +43,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 bffa4b44..f80f092d 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -35,4 +35,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 60103b8b..b1d9e44a 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -44,4 +44,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 fdde869b..e17d7b9a 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -250,7 +250,7 @@ public abstract class Node {
             return deadCodeElim(n.peephole());
 
         return null;            // No progress
-    }
+        }
 
     // m is the new Node, self is the old.
     // Return 'm', which may have zero uses but is alive nonetheless.
@@ -346,6 +346,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..b3b5462d
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -0,0 +1,74 @@
+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
+    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() {
+        Type t = in(1)._type;
+        for( int i=2; i<nIns(); i++ )
+            t = t.meet(in(i)._type);
+        return t;
+    }
+
+    @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 c831a798..bd43bc6c 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -54,4 +54,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/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
index a0ad7be0..0c2ac4b0 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 
-/** Chapter 4's view of the IR; no knowledge of browser, transport or layout. */
+/** Chapter 5's view of the IR; browser, transport and layout are shared. */
 public class SimpleGraphAdapter extends GraphAdapter<Node> {
     @Override protected boolean dead(Node n) { return n.isDead(); }
     @Override protected int id(Node n) { return n._nid; }
@@ -17,23 +17,37 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> {
     @Override protected Node out(Node n, int idx) { return n.out(idx); }
 
     private ArrayList<Edge> edges(Node n) {
-        String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null;
         var edges = new ArrayList<Edge>();
+        String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null;
         for( int i = 0; i < n.nIns(); i++ ) {
-            Role role = n instanceof ScopeNode || n instanceof ConstantNode ? Role.ASSOC
-                : n instanceof ProjNode ? (n.isCFG() ? Role.CTRL : Role.DATA)
-                : i == 0 ? Role.CTRL : Role.DATA;
-            edges.add(new Edge(i, ref(n.in(i)), role, names == null ? null : names[i]));
+            String name = names == null || i >= names.length ? null : names[i];
+            edges.add(new Edge(i, ref(n.in(i)), role(n, i), name));
         }
         return edges;
     }
 
     @Override protected GraphSnapshot.Node desc(Node n) {
-        Projection proj = n instanceof ProjNode p
-            ? new Projection(n.nIns() == 0 ? 0 : ref(n.in(0)), p._idx) : null;
-        Kind kind = n instanceof ScopeNode ? Kind.SCOPE : n.isCFG() ? Kind.CTRL : Kind.DATA;
+        Projection proj = n instanceof ProjNode p ? new Projection(ref(n.in(0)), p._idx) : null;
         String label = n.label();
         return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label,
-                                      n._type == null ? null : n._type.toString(), kind, edges(n), proj);
+                                      n._type == null ? null : n._type.toString(), kind(n), edges(n), proj);
+    }
+
+    private Kind kind(Node n) {
+        if( n instanceof StopNode ) return Kind.STOP;
+        if( n instanceof ScopeNode ) return Kind.SCOPE;
+        if( n instanceof StartNode ) return Kind.CTRL;
+        if( n instanceof RegionNode ) return Kind.REGION;
+        if( n instanceof PhiNode ) return Kind.PHI;
+        return n.isCFG() ? Kind.CTRL : Kind.DATA;
+    }
+
+    private Role role(Node n, int i) {
+        if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC;
+        if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : Role.DATA;
+        if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : Role.DATA;
+        if( n instanceof RegionNode && i == 0 ) return Role.ASSOC;
+        if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL;
+        return Role.DATA;
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
index d655ed4a..a7604165 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java
@@ -7,10 +7,11 @@ import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 import java.io.IOException;
 
-/** Chapter 4 needs only a parser; it has no worklist or distant dependencies. */
+/** Chapter 5's compilation context; capture and event bookkeeping are shared. */
 public class SimpleGraphObserver extends GraphCapture<Node> {
     private Parser _parser;
     private Node _ret;
+    private String _phase;
     public SimpleGraphObserver() { super(new SimpleGraphAdapter()); }
     public static void main(String[] args) throws IOException {
         GraphViewer.run(new SimpleGraphObserver());
@@ -18,11 +19,12 @@ public class SimpleGraphObserver extends GraphCapture<Node> {
     @Override protected void compile(String src) {
         _parser = new Parser(src);
         _parser._obs = this;
+        _phase = "Parse";
         _ret = _parser.parse();
-        phase("Parse");
+        phase(_phase);
     }
-    @Override protected String phase() { return "Parse"; }
-    @Override protected int pos() { return _parser.pos(); }
+    @Override protected String phase() { return _phase; }
+    @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; }
     @Override protected void detach() {
         if( _parser != null ) _parser._obs = null;
         _parser = null;
@@ -31,6 +33,8 @@ public class SimpleGraphObserver extends GraphCapture<Node> {
     @Override protected Node scope() { return _parser._scope; }
     @Override protected void roots(ArrayList<Node> roots) {
         roots.add(Parser.START);
+        roots.add(_parser.STOP);
+        roots.addAll(_parser._xScopes);
         roots.add(_ret);
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index 1e50bdda..6b9130ba 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 52befa38..da701865 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 6c816a23..a6075b75 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -11,49 +11,49 @@ public class Chapter02Test {
     @Test
     public void testParseGrammar() {
         Parser parser = new Parser("return 1+2*3+-5;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
     }
 
     @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());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 46b1ca33..c3cd43c3 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -11,28 +11,28 @@ 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());
     }
 
     @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);");
-        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 195afbb7..e5840622 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -11,77 +11,78 @@ public class Chapter04Test {
     @Test
     public void testPeephole() {
         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 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;");
-        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 testSub0() {
         Parser parser = new Parser("return arg-0;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return arg;", ret.print());
     }
 
     @Test
     public void test0Sub() {
         Parser parser = new Parser("return 0-arg;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (-arg);", ret.print());
     }
 
     @Test
     public void testSubNeg() {
         Parser parser = new Parser("return 3--arg;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testNegSub() {
         Parser parser = new Parser("return -arg-3;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (-(arg+3));", ret.print());
     }
 
     @Test
     public void testVarArg() {
-        Parser parser = new Parser("return arg;", TypeInteger.BOT);
-        ReturnNode ret = parser.parse();
+        Parser parser = new Parser("return arg;");
+        StopNode stop = parser.parse();
+        ReturnNode ret = stop.ret();
         assertTrue(ret.in(0) instanceof ProjNode);
         assertTrue(ret.in(1) instanceof ProjNode);
     }
@@ -89,49 +90,49 @@ public class Chapter04Test {
     @Test
     public void testConstantArg() {
         Parser parser = new Parser("return arg;", 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;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testCompEq2() {
         Parser parser = new Parser("return 3==4;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq() {
         Parser parser = new Parser("return 3!=3;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testCompNEq2() {
         Parser parser = new Parser("return 3!=4;");
-        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;");
-        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;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (arg+1);", ret.print());
     }
 
@@ -148,14 +149,14 @@ 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());
     }
 
     @Test
     public void testBug5() {
         Parser parser = new Parser("return arg--2;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (arg--2);", 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..31ca56a0
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -0,0 +1,210 @@
+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;
+}
+return a;""");
+        StopNode ret = parser.parse();
+        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();
+        assertEquals("return Phi(Region16,4,3);", ret.toString());
+    }
+
+    @Test
+    public void testReturn2() {
+        Parser parser = new Parser(
+"""
+if( arg==1 )
+    return 3;
+else
+    return 4;
+""", 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();
+        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();
+        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;
+""", 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;
+""", 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();
+        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());
+        }
+    }
+
+}