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: fuhsnn <66062782+fuhsnn@users.noreply.github.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>

17 files changed, 395 insertions, 39 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 2fa4514e..367cb2c0 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -66,6 +66,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
@@ -78,15 +96,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 4c79fa0b..aaf261d5 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -42,7 +42,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 08dea003..f6b4e03e 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -31,4 +31,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..3b644bec
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -0,0 +1,33 @@
+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 protected String format() { return "if( %1 )"; }
+
+    @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 e866cf24..a881bd96 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -40,4 +40,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 bd72c8e4..72469ad2 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -213,7 +213,7 @@ public abstract class Node extends BaseNode<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.
@@ -308,6 +308,20 @@ public abstract class Node extends BaseNode<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..da3917c7
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -0,0 +1,74 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.print.ExprPrinter;
+
+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
+    protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
+        p.p("Phi(");
+        for( Node in : _inputs )
+            p.n(in).p(",");
+        return p.unchar(',').close();
+    }
+
+    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 063f9edc..8917fbd4 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -25,7 +25,7 @@ public class ProjNode extends Node {
     @Override
     protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_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..e29254ad
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.print.ExprPrinter;
+
+import com.seaofnodes.simple.type.Type;
+
+public class RegionNode extends Node {
+    public RegionNode(Node... inputs) { super(inputs); }
+
+    @Override
+    public String label() { return "Region"; }
+
+    @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
+        return p.p(label()).p(_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 6ffa8939..90b97bae 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -133,4 +133,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..9ae0acb4
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -0,0 +1,48 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.print.ExprPrinter;
+
+import com.seaofnodes.simple.type.Type;
+
+public class StopNode extends Node {
+    public StopNode(Node... inputs) {
+        super(inputs);
+    }
+
+    @Override
+    public String label() {
+        return "Stop";
+    }
+
+    @Override
+    protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
+        if( ret()!=null ) return p.n(ret());
+        p.p("Stop[ ");
+        for( Node ret : _inputs )
+            p.n(ret).p(" ");
+        return p.p("]");
+    }
+
+    @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 43e684a1..7a6e1a4b 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -50,4 +50,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 b68012dc..930d5376 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -5,7 +5,7 @@ import com.seaofnodes.graph.GraphSnapshot.*;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.node.Node;
 
-/** 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 String[] edgeNames(Node n) {
@@ -13,10 +13,21 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> {
     }
     @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; }
 
-    @Override protected Kind kind(Node n) { return n instanceof ScopeNode ? Kind.SCOPE : n.isCFG() ? Kind.CTRL : Kind.DATA; }
+    @Override protected 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;
+    }
+
     @Override protected Role role(Node n, int i) {
-        return n instanceof ScopeNode || n instanceof ConstantNode ? Role.ASSOC
-            : n instanceof ProjNode ? (n.isCFG() ? Role.CTRL : Role.DATA)
-            : i==0 ? Role.CTRL : Role.DATA;
+        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 466fb739..6b9130ba 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -41,13 +41,12 @@ public class Type {
 
     public boolean isConstant() { return _type == TTOP; }
 
+    public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
+
+    public Type meet(Type other) { return BOTTOM; }
+
     @Override
     public final String toString() {
         return print(new StringBuilder()).toString();
     }
-
-    public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
-
-    public Type meet(Type other) { return Type.BOTTOM; }
-
 }
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});
 }