Chapter 6 (#38)

* #37 Create chapter 6 skeleton

* #37 Revise type system - TOP, BOTTOM, CONTROL are now directly implemented in Type, XCONTROL is a new type and that's implemented directly too.
We have a _type field that is like an enum.

* #37 Revise Type.meet() - this is now final.
Subclasses can override xmeet() which is protected but
now handles simple types in Type itself.

* #37 Basic test for peephole of CFG

* #37 Revise compute of if

* #37 Revise compute of if

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP fix the chars inserted by IntelliJ

* #37 WIP Fix compute type in IfNode

* #37 WIP Null check region inputs

* #37 WIP Fix where we choose great grand parent instead of grand parent
Add new test

* #37 WIP More fixes and tests

* #37 WIP Some minor adjustments

* Cleanup folding dead IF tests

Remove isDeadCtrl & just test for the constant.
Remove DEAD_CTRL, doesn't properly reset between tests.
Move keep/unkeep to Node.
PhiNode has a proper compute() call.
ProjNode ideal is a lot simpler.
Region doesn't ever get a null.
Move the mergeScopes Region peep till after all Phis are added.
Type TOP and XCONTROL count as constants.
TypeTuple gets a toString

* #37 WIP Upate README

* #37 WIP Region node should check if one of its inputs is a region that needs to be peepholed

* #37 WIP If node should check if its ctrl input is a Region that has only 1 live input so can be peepholed

* #37 WIP Further update to README to make the peephole logic clearer. Also discuss the relationship between Region and Phi nodes

* Region removes dead input paths

Remove region-folding in Return, If.
Add a Makefile.
Reformat triple-quote lines to be emacs-friendly.

* StopNode idealize

Return type sharpens to include control input.

* Remove !=, >=, >; use Not and <, <=, ==

Fix bug mixing rotating different ops.
Generalize Add fold constants; apply to Mul, EQ.
Fix Div.copy

* Fix bug rotating e.g. < or <=

Peep is only valid for associative ops

* #37 WIP Doc updates

* Work over the Ch6 Readme

Major issue: Region inputs align 1-to-1 with Phi inputs, but a Region can have zero to many Phis.  When we lose a Region input (dead path), we need to lose the same inputs to each Phi - but we don't lose the Phis themselves, unless we're folding away down to the last live input.

* Update chapter06/README.md

Co-authored-by: Yichen Yan <oraluben@outlook.com>

* Update chapter06/README.md

Co-authored-by: Yichen Yan <oraluben@outlook.com>

* #37 Backport type system changes to chapter 2

* #37 Backport type system changes to chapter 3

* #37 Backport type system changes to chapter 4

* #37 Backport type system changes to chapter 5

* #37 Merge chapter 5 updates from main.
Remove language grammar module as we describe the grammar incrementally in each chapter.

* #37 Chapter 6 doc updates - added visuals to show effects of CFG peephole

* #37 Sync some updates to chapter 2

* #37 Sync some updates to chapter 3

* #37 Sync some updates to chapter 4

---------

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Yichen Yan <oraluben@outlook.com>

23 files changed, 2285 insertions, 0 deletions

diff --git a/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
new file mode 100644
index 00000000..c1c1c4c9
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -0,0 +1,235 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+
+import java.util.*;
+
+/**
+ * Simple visualizer that outputs GraphViz dot format.
+ * The dot output must be saved to a file and run manually via dot to generate the SVG output.
+ * Currently, this is done manually.
+ */
+public class GraphVisualizer {
+
+    public String generateDotOutput(Parser parser) {
+
+        // Since the graph has cycles, we need to create a flat list of all the
+        // nodes in the graph.
+        Collection<Node> all = findAll(parser);
+        StringBuilder sb = new StringBuilder();
+        sb.append("digraph chapter06 {\n");
+        sb.append("/*\n");
+        sb.append(parser.src());
+        sb.append("\n*/\n");
+        
+        // To keep the Scopes below the graph and pointing up into the graph we
+        // need to group the Nodes in a subgraph cluster, and the scopes into a
+        // different subgraph cluster.  THEN we can draw edges between the
+        // scopes and nodes.  If we try to cross subgraph cluster borders while
+        // still making the subgraphs DOT gets confused.
+        sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes
+
+        // Preserve node input order
+        sb.append("\tordering=\"in\";\n");
+
+        // Merge multiple edges hitting the same node.  Makes common shared
+        // nodes much prettier to look at.
+        sb.append("\tconcentrate=\"true\";\n");
+        
+        // Just the Nodes first, in a cluster no edges
+        nodes(sb, all);
+        
+        // Now the scopes, in a cluster no edges
+        for (ScopeNode sn: parser._allScopes)
+            scopes(sb, sn);
+
+        // Walk the Node edges
+        nodeEdges(sb, all);
+
+        // Walk the Scope edges
+        for (ScopeNode sn: parser._allScopes)
+            scopeEdges(sb, sn);
+        
+        sb.append("}\n");
+        return sb.toString();
+    }
+
+
+    private void nodes(StringBuilder sb, Collection<Node> all) {
+        // Just the Nodes first, in a cluster no edges
+        sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
+        for( Node n : all ) {
+            if( n instanceof ProjNode || n instanceof ScopeNode )
+                continue; // Do not emit, rolled into MultiNode or Scope cluster already
+            sb.append("\t\t").append(n.uniqueName()).append(" [ ");
+            String lab = n.glabel();
+            if( n instanceof MultiNode ) {
+                // Make a box with the MultiNode on top, and all the projections on the bottom
+                sb.append("shape=plaintext label=<\n");
+                sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n");
+                sb.append("\t\t\t<TR><TD BGCOLOR=\"yellow\">").append(lab).append("</TD></TR>\n");
+                sb.append("\t\t\t<TR>");
+                boolean doProjTable = false;
+                for( Node use : n._outputs ) {
+                    if( use instanceof ProjNode proj ) {
+                        if (!doProjTable) {
+                            doProjTable = true;
+                            sb.append("<TD>").append("\n");
+                            sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n");
+                            sb.append("\t\t\t\t<TR>");
+                        }
+                        sb.append("<TD PORT=\"p").append(proj._idx).append("\"");
+                        if( proj.isCFG() ) sb.append(" BGCOLOR=\"yellow\"");
+                        sb.append(">").append(proj.glabel()).append("</TD>");
+                    }
+                }
+                if (doProjTable) {
+                    sb.append("</TR>").append("\n");
+                    sb.append("\t\t\t\t</TABLE>").append("\n");
+                    sb.append("\t\t\t</TD>");
+                }
+                sb.append("</TR>\n");
+                sb.append("\t\t\t</TABLE>>\n\t\t");
+                
+            } else {
+                // control nodes have box shape
+                // other nodes are ellipses, i.e. default shape
+                if( n.isCFG() )
+                    sb.append("shape=box style=filled fillcolor=yellow ");
+                if( n instanceof PhiNode )
+                    sb.append("style=filled fillcolor=lightyellow ");
+                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
+    }
+
+    private void scopes( StringBuilder sb, ScopeNode scopenode) {
+        sb.append("\tnode [shape=plaintext];\n");
+        int level=0;
+        for( HashMap<String,Integer> scope : scopenode._scopes ) {
+            String scopeName = makeScopeName(scopenode, level);
+            sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name
+            sb.append("\t\t").append(scopeName).append(" [label=<\n");
+            sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n");
+            // Add the scope level
+            sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>");
+            for( String name : scope.keySet() )
+                sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>");
+            sb.append("</TR>\n");
+            sb.append("\t\t\t</TABLE>>];\n");
+            level++;
+        }
+        // Scope clusters nest, so the graphics shows the nested scopes, so
+        // they are not closed as they are printed; so they just keep nesting.
+        // We close them all at once here.
+        sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters
+    }
+
+    private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; }
+    private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; }
+
+    // Walk the node edges
+    private void nodeEdges(StringBuilder sb, Collection<Node> all) {
+        // All them edge labels
+        sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n");
+        for( Node n : all ) {
+            // Do not display the Constant->Start edge;
+            // ProjNodes handled by Multi;
+            // ScopeNodes are done separately
+            if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode )
+                continue;
+            int i=0;
+            for( Node def : n._inputs ) {
+                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 ) {
+                        String mname = proj.ctrl().uniqueName();
+                        sb.append(mname).append(":p").append(proj._idx);
+                    } else sb.append(def.uniqueName());
+                    // Number edges, so we can see how they track
+                    sb.append("[taillabel=").append(i);
+                    // control edges are colored red
+                    if( def.isCFG() )
+                        sb.append(" color=red");
+                    sb.append("];\n");
+                }
+                i++;
+            }
+        }
+    }
+    
+    // Walk the scope edges
+    private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) {
+        sb.append("\tedge [style=dashed color=cornflowerblue];\n");
+        int level=0;
+        for( HashMap<String,Integer> scope : scopenode._scopes ) {
+            String scopeName = makeScopeName(scopenode, level);
+            for( String name : scope.keySet() ) {
+                Node def = scopenode.in(scope.get(name));
+                if( def==null ) continue;
+                sb.append("\t")
+                  .append(scopeName).append(":")
+                  .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted
+                  .append(" -> ");
+                if( def instanceof ProjNode proj ) {
+                    String mname = proj.ctrl().uniqueName();
+                    sb.append(mname).append(":p").append(proj._idx);
+                } else sb.append(def.uniqueName());
+                sb.append(";\n");
+            }
+            level++;
+        }
+    }
+    
+    /**
+     * Finds all nodes in the graph.
+     */
+    private Collection<Node> findAll(Parser parser) {
+        final StartNode start = Parser.START;
+        final HashMap<Integer, Node> all = new HashMap<>();
+        for( Node n : start._outputs )
+            walk(all, n);
+        // Scan symbol tables
+        for( HashMap<String,Integer> scope : parser._scope._scopes )
+            for (Integer i : scope.values())
+                walk(all, parser._scope.in(i));
+        return all.values();
+    }
+
+    /**
+     * Walk a subgraph and populate distinct nodes in the all list.
+     */
+    private void walk(HashMap<Integer, Node> all, Node n) {
+        if(n == null ) return;
+        if (all.get(n._nid) != null) return; // Been there, done that
+        all.put(n._nid, n);
+        for (Node c : n._inputs)
+            if (c != null)
+                walk(all, c);
+        for (Node c : n._outputs)
+            if (c != null)
+                walk(all, c);
+    }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java
new file mode 100644
index 00000000..b08c3c56
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java
@@ -0,0 +1,528 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+
+import java.util.*;
+
+/**
+ * The Parser converts a Simple source program to the Sea of Nodes intermediate
+ * representation directly in one pass. There is no intermediate Abstract
+ * Syntax Tree structure.
+ * <p>
+ * This is a simple recursive descent parser. All lexical analysis is done here as well.
+ */
+public class Parser {
+
+    /**
+     * The control is a name that binds to the currently active control
+     * node in the graph
+     */
+    public static final String CTRL = "$ctrl";
+  
+    /**
+     * A Global Static, unique to each compilation.  This is a public, so we
+     * can make constants everywhere without having to thread the StartNode
+     * through the entire parser and optimizer.
+     * <p>
+     * To make the compiler multithreaded, this field will have to move into a TLS.
+     */
+    public static StartNode START;
+
+    public StopNode STOP;
+
+    // The Lexer.  Thin wrapper over a byte[] buffer with a cursor.
+    private final Lexer _lexer;
+
+    /**
+     * 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 #_allScopes
+     */
+    public ScopeNode _scope;
+
+    /**
+     * 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> _allScopes = new Stack<>();
+
+    public Parser(String source, TypeInteger arg) {
+        _lexer = new Lexer(source);
+        Node.reset();
+        _scope = new ScopeNode();
+        START = new StartNode(new Type[]{ Type.CONTROL, arg });
+        START.peephole();
+        STOP = new StopNode();
+    }
+
+    public Parser(String source) {
+        this(source, TypeInteger.BOT);
+    }
+
+    String src() { return new String( _lexer._input ); }
+
+    private Node ctrl() { return _scope.ctrl(); }
+
+    private Node ctrl(Node n) { return _scope.ctrl(n); }
+
+    public StopNode parse() { return parse(false); }
+    public StopNode parse(boolean show) {
+        _allScopes.push(_scope);
+        _scope.push();
+        try {
+            _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole());
+            _scope.define("arg", new ProjNode(START, 1, "arg").peephole());
+            parseBlock();
+            if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
+            return STOP;
+        }
+        finally {
+            _scope.pop();
+            _allScopes.pop();
+            STOP.peephole();
+            if( show ) showGraph();
+        }
+    }
+
+    /**
+     * Parses a block
+     *
+     * <pre>
+     *     '{' statements '}'
+     * </pre>
+     * Does not parse the opening or closing '{}'
+     * @return a {@link Node} or {@code null}
+     */
+    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
+        };
+        // Exit scope
+        _scope.pop();
+        return n;
+    }
+
+    /**
+     * Parses a statement
+     *
+     * <pre>
+     *     returnStatement | declStatement | blockStatement | ifStatement | expressionStatement
+     * </pre>
+     * @return a {@link Node} or {@code null}
+     */
+    private Node parseStatement() {
+        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 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();
+        ifNode.unkeep();
+        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
+        _allScopes.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();
+
+        if( tScope.nIns() != ndefs || fScope.nIns() != ndefs )
+            throw error("Cannot define a new name on one arm of an if");
+        
+        // Merge results
+        _scope = tScope;
+        _allScopes.pop();       // Discard pushed from graph display
+
+        return ctrl(tScope.mergeScopes(fScope));
+    }
+
+
+    /**
+     * Parses a return statement; "return" already parsed.
+     * The $ctrl edge is killed.
+     *
+     * <pre>
+     *     'return' expr ;
+     * </pre>
+     * @return an expression {@link Node}, never {@code null}
+     */
+    private Node parseReturn() {
+        var expr = require(parseExpression(), ";");
+        Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole());
+        ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control
+        return ret;
+    }
+
+    /**
+     * Dumps out the node graph
+     * @return {@code null}
+     */
+    private Node showGraph() {
+        System.out.println(new GraphVisualizer().generateDotOutput(this));
+        return null;
+    }
+
+    /**
+     * Parses an expression statement
+     *
+     * <pre>
+     *     name '=' expression ';'
+     * </pre>
+     * @return an expression {@link Node}, never {@code null}
+     */
+    private Node parseExpressionStatement() {
+        var name = requireId();
+        require("=");
+        var expr = require(parseExpression(), ";");
+        if( _scope.update(name, expr)==null )
+            throw error("Undefined name '" + name + "'");
+        return expr;
+    }
+
+    /**
+     * Parses a declStatement
+     *
+     * <pre>
+     *     'int' name = expression ';'
+     * </pre>
+     * @return an expression {@link Node}, never {@code null}
+     */
+    private Node parseDecl() {
+        // Type is 'int' for now
+        var name = requireId();
+        require("=");
+        var expr = require(parseExpression(), ";");
+        if( _scope.define(name,expr) == null )
+            throw error("Redefining name '" + name + "'");
+        return expr;
+    }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * <pre>
+     *     expr : compareExpr
+     * </pre>
+     * @return an expression {@link Node}, never {@code null}
+     */
+    private Node parseExpression() { return parseComparison(); }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * <pre>
+     *     expr : additiveExpr op additiveExpr
+     * </pre>
+     * @return an comparator expression {@link Node}, never {@code null}
+     */
+    private Node parseComparison() {
+        var lhs = parseAddition();
+        if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole();
+        if (match("!=")) return new NotNode(new BoolNode.EQNode(lhs, parseComparison()).peephole()).peephole();
+        if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole();
+        if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole();
+        if (match(">" )) return new BoolNode.LTNode(parseComparison(), lhs).peephole();
+        if (match(">=")) return new BoolNode.LENode(parseComparison(), lhs).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse an additive expression
+     *
+     * <pre>
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     * </pre>
+     * @return an add expression {@link Node}, never {@code null}
+     */
+    private Node parseAddition() {
+        var lhs = parseMultiplication();
+        if (match("+")) return new AddNode(lhs, parseAddition()).peephole();
+        if (match("-")) return new SubNode(lhs, parseAddition()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse an multiplicativeExpr expression
+     *
+     * <pre>
+     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     * </pre>
+     * @return a multiply expression {@link Node}, never {@code null}
+     */
+    private Node parseMultiplication() {
+        var lhs = parseUnary();
+        if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole();
+        if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole();
+        return lhs;
+    }
+
+    /**
+     * Parse a unary minus expression.
+     *
+     * <pre>
+     *     unaryExpr : ('-') unaryExpr | primaryExpr
+     * </pre>
+     * @return a unary expression {@link Node}, never {@code null}
+     */
+    private Node parseUnary() {
+        if (match("-")) return new MinusNode(parseUnary()).peephole();
+        return parsePrimary();
+    }
+
+    /**
+     * Parse a primary expression:
+     *
+     * <pre>
+     *     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);
+        if( n!=null ) return n;
+        throw error("Undefined name '" + name + "'");
+    }
+
+    /**
+     * Parse integer literal
+     *
+     * <pre>
+     *     integerLiteral: [1-9][0-9]* | [0]
+     * </pre>
+     */
+    private ConstantNode parseIntegerLiteral() {
+        return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole();
+    }
+
+    //////////////////////////////////
+    // Utilities for lexical analysis
+
+    // Return true and skip if "syntax" is next in the stream.
+    private boolean match (String syntax) { return _lexer.match (syntax); }
+    // Match must be "exact", not be followed by more id letters
+    private boolean matchx(String syntax) { return _lexer.matchx(syntax); }
+    // Return true and do NOT skip if 'ch' is next
+    private boolean peek(char ch) { return _lexer.peek(ch); }
+
+    // Require and return an identifier
+    private String requireId() {
+        String id = _lexer.matchId();
+        if (id != null && !KEYWORDS.contains(id) ) return id;
+        throw error("Expected an identifier, found '"+id+"'");
+    }
+
+    // Require an exact match
+    private void require(String syntax) { require(null, syntax); }
+    private Node require(Node n, String syntax) {
+        if (match(syntax)) return n;
+        throw errorSyntax(syntax);
+    }
+
+    RuntimeException errorSyntax(String syntax) {
+        return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    }
+
+    static RuntimeException error(String errorMessage) {
+        return new RuntimeException(errorMessage);
+    }
+
+    ////////////////////////////////////
+    // Lexer components
+
+    private static class Lexer {
+
+        // Input buffer; an array of text bytes read from a file or a string
+        private final byte[] _input;
+        // Tracks current position in input buffer
+        private int _position = 0;
+
+        /**
+         * Record the source text for lexing
+         */
+        public Lexer(String source) {
+            this(source.getBytes());
+        }
+
+        /**
+         * Direct from disk file source
+         */
+        public Lexer(byte[] buf) {
+            _input = buf;
+        }
+
+        // Very handy in the debugger, shows the unparsed program
+        @Override
+        public String toString() {
+            return new String(_input, _position, _input.length - _position);
+        }
+
+        // True if at EOF
+        private boolean isEOF() {
+            return _position >= _input.length;
+        }
+
+        // Peek next character, or report EOF
+        private char peek() {
+            return isEOF() ? Character.MAX_VALUE   // Special value that causes parsing to terminate
+                    : (char) _input[_position];
+        }
+
+        private char nextChar() {
+            char ch = peek();
+            _position++;
+            return ch;
+        }
+
+        // True if a white space
+        private boolean isWhiteSpace() {
+            return peek() <= ' '; // Includes all the use space, tab, newline, CR
+        }
+
+        /**
+         * Return the next non-white-space character
+         */
+        private void skipWhiteSpace() {
+            while (isWhiteSpace()) _position++;
+        }
+
+
+        // Return true, if we find "syntax" after skipping white space; also
+        // then advance the cursor past syntax.
+        // Return false otherwise, and do not advance the cursor.
+        boolean match(String syntax) {
+            skipWhiteSpace();
+            int len = syntax.length();
+            if (_position + len > _input.length) return false;
+            for (int i = 0; i < len; i++)
+                if ((char) _input[_position + i] != syntax.charAt(i))
+                    return false;
+            _position += len;
+            return true;
+        }
+
+        boolean matchx(String syntax) {
+            if( !match(syntax) ) return false;
+            if( !isIdLetter(peek()) ) return true;
+            _position -= syntax.length();
+            return false;
+        }
+
+        private boolean peek(char ch) {
+            skipWhiteSpace();
+            return peek()==ch;
+        }
+        
+        // Return an identifier or null
+        String matchId() {
+            skipWhiteSpace();
+            return isIdStart(peek()) ? parseId() : null;
+        }
+
+        // Used for errors
+        String getAnyNextToken() {
+            if (isEOF()) return "";
+            if (isIdStart(peek())) return parseId();
+            if (isPunctuation(peek())) return parsePunctuation();
+            return String.valueOf(peek());
+        }
+
+        boolean isNumber() {return isNumber(peek());}
+        boolean isNumber(char ch) {return Character.isDigit(ch);}
+
+        private Type parseNumber() {
+            int start = _position;
+            while (isNumber(nextChar())) ;
+            String snum = new String(_input, start, --_position - start);
+            if (snum.length() > 1 && snum.charAt(0) == '0')
+                throw error("Syntax error: integer values cannot start with '0'");
+            return TypeInteger.constant(Long.parseLong(snum));
+        }
+
+        // First letter of an identifier 
+        private boolean isIdStart(char ch) {
+            return Character.isAlphabetic(ch) || ch == '_';
+        }
+
+        // All characters of an identifier, e.g. "_x123"
+        private boolean isIdLetter(char ch) {
+            return Character.isLetterOrDigit(ch) || ch == '_';
+        }
+
+        private String parseId() {
+            int start = _position;
+            while (isIdLetter(nextChar())) ;
+            return new String(_input, start, --_position - start);
+        }
+
+        // 
+        private boolean isPunctuation(char ch) {
+            return "=;[]<>()+-/*".indexOf(ch) != -1;
+        }
+
+        private String parsePunctuation() {
+            int start = _position;
+            return new String(_input, start, 1);
+        }
+    }
+
+    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
+    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java
new file mode 100644
index 00000000..61359d64
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -0,0 +1,154 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.*;
+
+public class AddNode extends Node {
+    public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Add"; }
+    
+    @Override public String glabel() { return "+"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("+"));
+        return sb.append(")");
+    }
+  
+
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1 ) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()+i1.value());
+            return i0.meet(i1);
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize () {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+
+        // Already handled by peephole constant folding
+        assert !(t1.isConstant() && t2.isConstant());
+
+        // Add of 0.  We do not check for (0+x) because this will already
+        // canonicalize to (x+0)
+        if( t2 instanceof TypeInteger i && i.value()==0 )
+            return lhs;
+              
+        // Add of same to a multiply by 2
+        if( lhs==rhs )
+            return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole());
+
+        // Goal: a left-spine set of adds, with constants on the rhs (which then fold).
+        
+        // Move non-adds to RHS
+        if( !(lhs instanceof AddNode) && rhs instanceof AddNode )
+            return swap12();
+
+        // Now we might see (add add non) or (add non non) or (add add add) but never (add non add)
+
+        // Do we have  x + (y + z) ?
+        // Swap to    (x + y) + z
+        // Rotate (add add add) to remove the add on RHS
+        if( rhs instanceof AddNode add )
+            return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2));
+
+        // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add)
+        if( !(lhs instanceof AddNode) )
+            return spline_cmp(lhs,rhs) ? swap12() : null;
+
+        // Now we only see (add add non)
+        
+        // Do we have (x + con1) + con2?
+        // Replace with (x + (con1+con2) which then fold the constants
+        if( lhs.in(2)._type.isConstant() && t2.isConstant() )
+            return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
+
+
+        // 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...)
+        Node phicon = phiCon(this,true);
+        if( phicon!=null ) return phicon;
+
+        // Now we sort along the spline via rotates, to gather similar things together.
+        
+        // Do we rotate (x + y) + z
+        // into         (x + z) + y ?
+        if( spline_cmp(lhs.in(2),rhs) )
+            return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2));
+        
+        return null;
+    }
+
+    // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or.
+    // Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)) ?
+    // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+    static Node phiCon(Node op, boolean rotate) {
+        Node lhs = op.in(1);
+        Node rhs = op.in(2);
+        // LHS is either a Phi of constants, or another op with Phi of constants
+        PhiNode lphi = pcon(lhs);
+        if( rotate && lphi==null && lhs.nIns() > 2 ) {
+            // Only valid to rotate constants if both are same associative ops
+            if( lhs.getClass() != op.getClass() ) return null;
+            lphi = pcon(lhs.in(2)); // Will rotate with the Phi push
+        }
+        if( lphi==null ) return null;
+        
+        // RHS is a constant or a Phi of constants
+        if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null )
+            return null;
+        
+        // If both are Phis, must be same Region
+        if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) )
+            return null;
+
+        // 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.
+        Node[] ns = new Node[lphi.nIns()];
+        ns[0] = lphi.in(0);
+        // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+        for( int i=1; i<ns.length; i++ )
+            ns[i] = op.copy(lphi.in(i), rhs instanceof PhiNode ? rhs.in(i) : rhs).peephole();
+        String label = lphi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
+        Node phi = new PhiNode(label,ns).peephole();
+        // Rotate needs another op, otherwise just the phi
+        return lhs==lphi ? phi : op.copy(lhs.in(1),phi);
+    }
+
+    static PhiNode pcon(Node op) {
+        return op instanceof PhiNode phi && phi.all_cons() ? phi : null;
+    }
+        
+    // 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 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.all_cons() ) return false;
+        if( hi instanceof PhiNode && hi.all_cons() ) 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/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java
new file mode 100644
index 00000000..bbcc742d
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -0,0 +1,58 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+abstract public class BoolNode extends Node {
+
+    public BoolNode(Node lhs, Node rhs) {
+        super(null, lhs, rhs);
+    }
+
+    abstract String op();       // String opcode name
+    
+    @Override
+    public String label() { return getClass().getSimpleName(); }
+
+    @Override
+    public String glabel() { return op(); }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append(op()));
+        return sb.append(")");
+    }
+
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1 ) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
+            return i0.meet(i1);
+        }
+        return Type.BOTTOM;
+    }
+
+    abstract boolean doOp(long lhs, long rhs);
+
+    @Override
+    public Node idealize() {
+        // Compare of same 
+        if( in(1)==in(2) )
+            return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
+
+        // 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...)
+        Node phicon = AddNode.phiCon(this,false);
+        if( phicon!=null ) return phicon;
+
+        return null;
+    }
+
+    public static class EQNode extends BoolNode { public EQNode(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 EQNode(lhs,rhs); } }
+    public static class LTNode extends BoolNode { public LTNode(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 LTNode(lhs,rhs); } }
+    public static class LENode extends BoolNode { public LENode(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 LENode(lhs,rhs); } }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
new file mode 100644
index 00000000..bc92b540
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -0,0 +1,41 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+
+/**
+ * A Constant node represents a constant value.  At present, the only constants
+ * that we allow are integer literals; therefore Constants contain an integer
+ * value. As we add other types of constants, we will refactor how we represent
+ * Constants.
+ * <p>
+ * Constants have no semantic inputs. However, we set Start as an input to
+ * Constants to enable a forward graph walk.  This edge carries no semantic
+ * meaning, and it is present <em>solely</em> to allow visitation.
+ * <p>
+ * The Constant's value is the value stored in it.
+ */
+public class ConstantNode extends Node {
+    Type _con;
+    public ConstantNode( Type type ) {
+        super(Parser.START);
+        _con = type;
+    }
+    
+    @Override
+    public String label() { return "#"+_con; }
+  
+    @Override
+    public String uniqueName() { return "Con_" + _nid; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return _con._print(sb);
+    }
+    
+    @Override
+    public Type compute() { return _con; }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java
new file mode 100644
index 00000000..01314c74
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -0,0 +1,37 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class DivNode extends Node {
+    public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Div"; }
+
+    @Override public String glabel() { return "//"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("/"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1) {
+            if (i0.isConstant() && i1.isConstant())
+                return i1.value() == 0
+                    ? TypeInteger.ZERO
+                    : TypeInteger.constant(i0.value()/i1.value());
+            return i0.meet(i1);
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+  
+    @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java
new file mode 100644
index 00000000..9e88710c
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -0,0 +1,44 @@
+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() {
+        // If the If node is not reachable then neither is any following Proj
+        if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER;
+        // If constant is 0 then false branch is reachable
+        // Else true branch is reachable
+        if (pred()._type instanceof TypeInteger ti && ti.isConstant()) {
+            if (ti.value() == 0)          return TypeTuple.IF_FALSE;
+            else                          return TypeTuple.IF_TRUE;
+        }
+        return TypeTuple.IF_BOTH;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java
new file mode 100644
index 00000000..08924563
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class MinusNode extends Node {
+    public MinusNode(Node in) { super(null, in); }
+
+    @Override public String label() { return "Minus"; }
+  
+    @Override public String glabel() { return "-"; }
+  
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("(-"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0)
+            return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java
new file mode 100644
index 00000000..31683a4e
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -0,0 +1,56 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class MulNode extends Node {
+    public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Mul"; }
+  
+    @Override public String glabel() { return "*"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("*"));
+        return sb.append(")");
+    }
+
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()*i1.value());
+            return i0.meet(i1);
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+        
+        // Mul of 1.  We do not check for (1*x) because this will already
+        // canonicalize to (x*1)
+        if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 )
+            return lhs;
+        
+        // Move constants to RHS: con*arg becomes arg*con
+        if ( t1.isConstant() && !t2.isConstant() )
+            return swap12();
+
+        // 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...)
+        Node phicon = AddNode.phiCon(this,true);
+        if( phicon!=null ) return phicon;
+
+        return null;
+    }
+    @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java
new file mode 100644
index 00000000..fe3fddf8
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -0,0 +1,9 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+public abstract class MultiNode extends Node {
+    
+    public MultiNode(Node... inputs) { super(inputs); }
+
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java
new file mode 100644
index 00000000..fd1b870c
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -0,0 +1,380 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+
+import java.util.*;
+
+/**
+ * All Nodes in the Sea of Nodes IR inherit from the Node class.
+ * The Node class provides common functionality used by all subtypes.
+ * Subtypes of Node specialize by overriding methods.
+ */
+public abstract class Node {
+
+    /**
+     * Each node has a unique dense Node ID within a compilation context
+     * The ID is useful for debugging, for using as an offset in a bitvector,
+     * as well as for computing equality of nodes (to be implemented later).
+     */
+    public final int _nid;
+
+    /**
+     * Inputs to the node. These are use-def references to Nodes.
+     * <p>
+     * Generally fixed length, ordered, nulls allowed, no unused trailing space.
+     * Ordering is required because e.g. "a/b" is different from "b/a".
+     * The first input (offset 0) is often a {@link #isCFG} node.
+     */
+    public final ArrayList<Node> _inputs;
+
+    /**
+     * Outputs reference Nodes that are not null and have this Node as an
+     * input.  These nodes are users of this node, thus these are def-use
+     * references to Nodes.
+     * <p>
+     * Outputs directly match inputs, making a directed graph that can be
+     * walked in either direction.  These outputs are typically used for
+     * efficient optimizations but otherwise have no semantics meaning.
+     */
+    public final ArrayList<Node> _outputs;
+
+
+    /**
+     * Current computed type for this Node.  This value changes as the graph
+     * changes and more knowledge is gained about the program.
+     */
+    public Type _type;
+
+    /**
+     * A private Global Static mutable counter, for unique node id generation.
+     * To make the compiler multithreaded, this field will have to move into a TLS.
+     * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
+     * */
+    private static int UNIQUE_ID = 1;
+
+    protected Node(Node... inputs) {
+        _nid = UNIQUE_ID++; // allocate unique dense ID
+        _inputs = new ArrayList<>();
+        Collections.addAll(_inputs,inputs);
+        _outputs = new ArrayList<>();
+        for( Node n : _inputs )
+            if( n != null )
+                n.addUse( this );
+    }
+
+    // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ"
+    public abstract String label();
+
+    // Unique label for graph visualization, e.g. "Add12" or "Region30" or "EQ99"
+    public String uniqueName() { return label() + _nid; }
+
+    // Graphical label, e.g. "+" or "Region" or "=="
+    public String glabel() { return label(); }
+    
+    @Override
+    public final String toString() {
+        // TODO: This needs a lot of work
+        return print();
+    }
+
+    // This is a *deep* print.  This version will fail on cycles, which we will
+    // correct later when we can parse programs with loops.  We print with a
+    // tik-tok style; the common _print0 calls the per-Node _print1, which
+    // calls back to _print0;
+    public final String print() {
+        return _print0(new StringBuilder()).toString();
+    }
+    // This is the common print: check for DEAD and print "DEAD" else call the
+    // per-Node print1.
+    final StringBuilder _print0(StringBuilder sb) {
+        return isDead()
+            ? sb.append(uniqueName()).append(":DEAD")
+            : _print1(sb);
+    }
+    // Every Node implements this.
+    abstract StringBuilder _print1(StringBuilder sb);
+
+    
+    /**
+     * Gets the ith input node
+     * @param i Offset of the input node
+     * @return Input node or null
+     */
+    public Node in(int i) { return _inputs.get(i); }
+
+    public int nIns() { return _inputs.size(); }
+
+    public int nOuts() { return _outputs.size(); }
+
+    public boolean isUnused() { return nOuts() == 0; }
+
+    public boolean isCFG() { return false; }
+  
+    /**
+     * We allow disabling peephole opt so that we can observe the
+     * full graph, vs the optimized graph.
+     */
+    public static boolean _disablePeephole = false;
+
+    /**
+     * Try to peephole at this node and return a better replacement Node if
+     * possible.  We compute a {@link Type} and then check and replace:
+     * <ul>
+     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
+     * <li>in a future chapter we will look for a
+     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
+     * to eliminate.</li>
+     * <li>we ask the Node for a better replacement.  The "better replacement"
+     * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes
+     * {@code (x+(1+2))}.  By canonicalizing expressions we fold common addressing
+     * math constants, remove algebraic identities and generally simplify the
+     * code. </li>
+     * </ul>
+     */
+    public final Node peephole( ) {
+        // Compute initial or improved Type
+        Type type = _type = compute();
+        
+        if (_disablePeephole)
+            return this;        // Peephole optimizations turned off
+
+        // Replace constant computations from non-constants with a constant node
+        if (!(this instanceof ConstantNode) && type.isConstant())
+            return deadCodeElim(new ConstantNode(type).peephole());
+
+        // Future chapter: Global Value Numbering goes here
+        
+        // Ask each node for a better replacement
+        Node n = idealize();
+        if( n != null )         // Something changed
+            // Recursively optimize
+            return deadCodeElim(n.peephole());
+        
+        return this;            // No progress
+    }
+
+    // m is the new Node, self is the old.
+    // Return 'm', which may have zero uses but is alive nonetheless.
+    // If self has zero uses (and is not 'm'), {@link #kill} self.
+    private Node deadCodeElim(Node m) {
+        // If self is going dead and not being returned here (Nodes returned
+        // from peephole commonly have no uses (yet)), then kill self.
+        if( m != this && isUnused() ) {
+            // Killing self - and since self recursively kills self's inputs we
+            // might end up killing 'm', which we are returning as a live Node.
+            // So we add a bogus extra null output edge to stop kill().
+            m.addUse(null); // Add bogus null use to keep m alive
+            kill();            // Kill self because replacing with 'm'
+            m.delUse(null);    // Remove bogus null.
+        }
+        return m;
+    }
+
+    
+    /**
+     * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
+     * the corresponding <em>use->def</em> edge.  This may make the original
+     * <em>def</em> go dead.  This function is co-recursive with {@link #kill}.
+     * <p>
+     
+     * This method is the normal path for altering a Node, because it does the
+     * proper default edge maintenance.  It also <em>immediately</em> kills
+     * Nodes that lose their last use; at times care must be taken to avoid
+     * killing Nodes that are being used without having an output Node.  This
+     * definitely happens in the middle of recursive {@link #peephole} calls.
+     *     
+     * @param idx which def to set
+     * @param new_def the new definition
+     * @return this for flow coding
+     */
+    Node set_def(int idx, Node new_def ) {
+        Node old_def = in(idx);
+        if( old_def == new_def ) return this; // No change
+        // If new def is not null, add the corresponding def->use edge
+        // This needs to happen before removing the old node's def->use edge as
+        // the new_def might get killed if the old node kills it recursively.
+        if( new_def != null )
+            new_def.addUse(this);
+        if( old_def != null &&  // If the old def exists, remove a def->use edge
+            old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+            old_def.kill();     // Kill old def
+        // Set the new_def over the old (killed) edge
+        _inputs.set(idx,new_def);
+        // Return self for easy flow-coding
+        return this;
+    }
+  
+    // Remove the numbered input, compressing the inputs in-place.  This
+    // shuffles the order deterministically - which is suitable for Region and
+    // Phi, but not for every Node.
+    void delDef(int idx) {
+        Node old_def = in(idx);
+        if( old_def != null &&  // If the old def exists, remove a def->use edge
+            old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+            old_def.kill();     // Kill old def
+        // Set the new_def over the old (killed) edge
+        int last = nIns()-1;
+        _inputs.set(idx,in(last));
+        _inputs.remove(last);
+    }
+
+    /**
+     * Add a new def to an existing Node.  Keep the edges correct by
+     * adding the corresponding <em>def->use</em> edge.
+     *
+     * @param new_def the new definition, appended to the end of existing definitions
+     * @return new_def for flow coding
+     */
+    Node add_def(Node new_def) {
+        // Add use->def edge
+        _inputs.add(new_def);
+        // If new def is not null, add the corresponding def->use edge
+        if( new_def != null )
+            new_def.addUse(this);
+        return new_def;
+    }
+
+    // Breaks the edge invariants, used temporarily
+    protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; }
+    // Shortcuts to stop DCE mid-parse
+    public <N extends Node> N keep() { return addUse(null); }
+    public Node unkeep() { delUse(null); return this; }
+
+    // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place.
+    // Return true if the output list is empty afterward.
+    // Error is 'use' does not exist; ok for 'use' to be null.
+    protected boolean delUse( Node use ) {
+        ArrayList<Node> outs = _outputs;
+        int lidx = outs.size()-1; // Last index            
+        // This 1-line hack compresses an element out of an ArrayList
+        // without having to copy the contents.  The last element is
+        // stuffed over the deleted element, and then the size is reduced.            
+        outs.set(outs.indexOf(use),outs.get(lidx));
+        outs.remove(lidx);  // Reduce ArrayList size without copying anything
+        return lidx==0;
+    }
+
+    // Shortcut for "popping" n nodes.  A "pop" is basically a
+    // set_def(last,null) followed by lowering the nIns() count.
+    void pop_n(int n) {
+        for( int i=0; i<n; i++ ) {
+            Node old_def = _inputs.remove(_inputs.size()-1);
+            if( old_def != null &&     // If it exists and
+                old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+                old_def.kill();        // Kill old def
+        }
+    }
+  
+    /**
+     * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
+     * to null.  This may recursively kill more Nodes and is basically dead
+     * code elimination.  This function is co-recursive with {@link #pop_n}.
+     */
+    public void kill( ) {
+        assert isUnused();      // Has no uses, so it is dead
+        pop_n(nIns());          // Set all inputs to null, recursively killing unused Nodes
+        _type=null;             // Flag as dead
+        assert isDead();        // Really dead now
+    }
+
+    // Mostly used for asserts and printing.
+    boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
+  
+    /**
+     * This function needs to be
+     * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
+     * as it is part of a Monotone Analysis Framework.
+     * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>.
+     * <p>
+     * For Chapter 2, all our Types are really integer constants, and so all
+     * the needed properties are trivially true, and we can ignore the high
+     * theory.  Much later on, this will become important and allow us to do
+     * many fancy complex optimizations trivially... because theory.
+     * <p>
+     * compute() needs to be stand-alone, and cannot recursively call compute
+     * on its inputs programs are cyclic (have loops!) and this will just
+     * infinitely recurse until stack overflow.  Instead, compute typically
+     * computes a new type from the {@link #_type} field of its inputs.
+     */
+    public abstract Type compute();
+
+    /**
+     * This function rewrites the current Node into a more "idealized" form.
+     * This is the bulk of our peephole rewrite rules, and we use this to
+     * e.g. turn arbitrary collections of adds and multiplies with mixed
+     * constants into a normal form that's easy for hardware to implement.
+     * Example: An array addressing expression:
+     * <pre>   ary[idx+1]</pre>
+     * might turn into Sea-of-Nodes IR:
+     * <pre>   (ary+12)+((idx+1) * 4)</pre>
+     * This expression can then be idealized into:
+     * <pre>   ary + ((idx*4) + (12 + (1*4)))</pre>
+     * And more folding:
+     * <pre>   ary + ((idx<<2) + 16)</pre>
+     * And during code-gen:
+     * <pre>   MOV4 Rary,Ridx,16 // or some such hardware-specific notation </pre>
+     * <p>
+     * {@link #idealize} has a very specific calling convention:
+     * <ul>
+     * <li>If NO change is made, return {@code null}
+     * <li>If ANY change is made, return not-null; this can be {@code this}
+     * <li>The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it.
+     * <li>Any NEW nodes that are not directly returned DO call {@link #peephole}.
+     * </ul>
+     * <p>
+     * Examples:
+     * <table border="3">
+     * <tr><th>    before       </th><th>       after     </th><th>return </th><th>comment  </th></tr>
+     * <tr><td>{@code (x+5)    }</td><td>{@code   (x+5)  }</td><td>{@code null  }</td><td>No change</td></tr>
+     * <tr><td>{@code (5+x)    }</td><td>{@code   (x+5)  }</td><td>{@code this  }</td><td>Swapped arguments</td></tr>
+     * <tr><td>{@code ((x+1)+2)}</td><td>{@code (x+(1+2))}</td><td>{@code (x+_) }</td><td>Returns 2 new Nodes</td></tr>
+     * </table>
+     *
+     * The last entry deserves more discussion.  The new Node {@code (1+2)}
+     * created in {@link #idealize} calls {@link #peephole} (which then folds
+     * into a constant).  The other new Node {@code (x+3)} does not call
+     * peephole, because it is returned and peephole itself will recursively
+     * call peephole.
+     * <p>
+     * Since idealize calls peephole and peephole calls idealize, you must be
+     * careful that all idealizations are <em>monotonic</em>: all transforms remove
+     * some feature, so that the set of available transforms always shrinks.
+     * If you don't, you risk an infinite peephole loop!
+     *
+     * @return Either a new or changed node, or null for no changes.
+     */
+    public abstract Node idealize();
+
+
+    // -----------------------
+    // Peephole utilities
+    
+    // Swap inputs without letting either input go dead during the swap.
+    Node swap12() {
+        Node tmp = in(1);
+        _inputs.set(1,in(2));
+        _inputs.set(2,tmp);
+        return this;
+    }
+    
+    // does this node contain all constants?
+    // Ignores in(0), as is usually control.
+    boolean all_cons() {
+        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 Parser.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.
+     */
+    public static void reset() { UNIQUE_ID = 1; }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/NotNode.java
new file mode 100644
index 00000000..5dd6a86e
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class NotNode extends Node {
+    public NotNode(Node in) { super(null, in); }
+
+    @Override public String label() { return "Not"; }
+  
+    @Override public String glabel() { return "!"; }
+  
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("(!"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 )
+            return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java
new file mode 100644
index 00000000..a5750922
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -0,0 +1,98 @@
+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() {
+        Type t = Type.TOP;
+        for (int i = 1; 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);
+
+        // If only 1 of our input values have live control
+        // then return that as phi is dead
+        Node live = singleLiveInput();
+        if (live != null)
+            return live;
+
+        // 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;
+    }
+
+    /**
+     * If only 1 of the inputs is live then return it
+     */
+    private Node singleLiveInput() {
+        Node live = null;
+        for( int i=1; i<nIns(); i++ )
+            // The control type is in the region
+            if( region().in(i)._type != Type.XCONTROL )
+                if (live == null)
+                    live = in(i);
+                else
+                    return null;
+        return live;
+    }
+
+
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java
new file mode 100644
index 00000000..424a1e9b
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -0,0 +1,50 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
+
+public class ProjNode extends Node {
+
+    // Which slice of the incoming multi-part value
+    public final int _idx;
+
+    // Debugging label
+    public final String _label;
+    
+    public ProjNode(MultiNode ctrl, int idx, String label) {
+        super(ctrl);
+        _idx = idx;
+        _label = label;
+    }
+
+    @Override
+    public String label() { return _label; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) { return sb.append(_label); }
+
+    @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
+
+    public MultiNode ctrl() { return (MultiNode)in(0); }
+
+    @Override
+    public Type compute() {
+        Type t = ctrl()._type;
+        return getType(t);
+    }
+
+    private Type getType(Type t) {
+        return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        if( ctrl()._type instanceof TypeTuple tt ) {
+            if( tt._types[_idx]==Type.XCONTROL )
+                return new ConstantNode(Type.XCONTROL).peephole(); // We are dead
+            if( tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes
+                return ctrl().in(0);               // We become our input control
+        }
+        return null;
+    }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java
new file mode 100644
index 00000000..1ddf520b
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -0,0 +1,56 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+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("Region").append(_nid);
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+    @Override
+    public Type compute() {
+        Type t = Type.XCONTROL;
+        for (int i = 1; i < nIns(); i++)
+            t = t.meet(in(i)._type);
+        return t;
+    }
+
+    @Override
+    public Node idealize() {
+        int path = findDeadInput();
+        if( path != 0 ) {
+            for( Node phi : _outputs )
+                if( phi instanceof PhiNode )
+                    phi.delDef(path);
+            delDef(path);
+
+            // If down to a single input, become that input - but also make all
+            // Phis an identity on *their* single input.
+            if( nIns()==2 ) {
+                for( Node phi : _outputs )
+                    if( phi instanceof PhiNode )
+                        // Currently does not happen, because no loops
+                        throw Parser.TODO();
+                return in(1);
+            }
+            return this;
+        }
+        return null;
+    }
+
+    private int findDeadInput() {
+        for( int i=1; i<nIns(); i++ )
+            if( in(i)._type==Type.XCONTROL )
+                return i;
+        return 0;               // All inputs alive
+    }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
new file mode 100644
index 00000000..ba2b83ac
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -0,0 +1,44 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.*;
+
+/**
+ * The Return node has two inputs.  The first input is a control node and the
+ * second is the data node that supplies the return value.
+ * <p>
+ * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible.
+ * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements.
+ * <p>
+ * The Return's output is the value from the data node.
+ */
+public class ReturnNode extends Node {
+
+    public ReturnNode(Node ctrl, Node data) {
+        super(ctrl, data);
+    }
+
+    public Node ctrl() { return in(0); }
+    public Node expr() { return in(1); }
+  
+    @Override
+    public String label() { return "Return"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return expr()._print0(sb.append("return ")).append(";");
+    }
+
+    @Override public boolean isCFG() { return true; }
+  
+    @Override
+    public Type compute() {
+        return new TypeTuple(ctrl()._type,expr()._type);
+    }
+
+    @Override
+    public Node idealize() {
+        if( ctrl()._type==Type.XCONTROL )
+            return ctrl();
+        return null;
+    }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
new file mode 100644
index 00000000..eecab9f9
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -0,0 +1,138 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+
+import java.util.*;
+
+/**
+ * The Scope node is a purely parser helper - it tracks names to nodes with a
+ * stack of scopes.
+ */
+public class ScopeNode extends Node {
+
+    /**
+     * Stack of lexical scopes, each scope is a symbol table
+     * that binds variable names to Nodes.
+     * The top of this stack represents current scope.
+     */
+    public final Stack<HashMap<String, Integer>> _scopes = new Stack<>();
+
+    // Reverse lookup for nicer graph printing
+    private final ArrayList<String> _rlabels = new ArrayList<>();
+    
+    @Override public String label() { return "Scope"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        sb.append(label());
+        for( HashMap<String,Integer> scope : _scopes ) {
+            sb.append("[");
+            boolean first=true;
+            for( String name : scope.keySet() ) {
+                if( !first ) sb.append(", ");
+                first=false;
+                sb.append(name).append(":");
+                Node n = in(scope.get(name));
+                if( n==null ) sb.append("null");
+                else n._print0(sb);
+            }
+            sb.append("]");
+        }
+        return sb;
+    }
+  
+    @Override
+    public Type compute() { return Type.BOTTOM; }
+
+    @Override public Node idealize() { return null; }
+
+    // Add an empty lexical scope
+    public HashMap<String, Integer> push() {
+        return _scopes.push(new HashMap<>());
+    }
+
+    // Remove the current lexical scope, killing all unused nodes.
+    public void pop() {
+        HashMap<String,Integer> scope = _scopes.pop();
+        pop_n(scope.size());
+    }
+
+    // Create a new name in the current scope
+    public Node define( String name, Node n ) {
+        HashMap<String,Integer> scope = _scopes.lastElement();
+        if( scope.put(name,nIns()) != null )
+            return null;        // Double define
+        _rlabels.add(name);
+        return add_def(n);
+    }
+
+    // Lookup a name in all scopes
+    public Node lookup(String name) {
+        for (int i = _scopes.size() - 1; i >= 0; i--) {
+            var idx = _scopes.get(i).get(name);
+            if (idx != null) return in(idx);
+        }
+        return null;
+    }
+
+    public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); }
+    
+    public Node ctrl(Node n) {
+        assert lookup(Parser.CTRL)==in(0);
+        set_def(0,n);
+        return n;
+    }
+
+  
+    // If the name is present in any scope, then redefine
+    public Node update(String name, Node n) {
+        for (int i = _scopes.size() - 1; i >= 0; i--) {
+            HashMap<String, Integer> scope = _scopes.get(i);
+            Integer idx = scope.get(name);
+            if (idx != null)           // Found prior def
+                return set_def(idx,n); // Update def in scope
+        }
+        return null;
+    }
+
+    /**
+     * 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() {
+        // 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
+        ScopeNode dup = new ScopeNode();
+        for( HashMap<String, Integer> tab : _scopes )
+            dup._scopes.push(new HashMap<>(tab));
+        for( int i=0; i<nIns(); i++ )
+            dup.add_def(in(i));
+        dup._rlabels.addAll(_rlabels);
+        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()).keep());
+        for (int i = 1; i < nIns(); i++)
+            if (in(i) != that.in(i)) // No need for redundant Phis
+                set_def(i, new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole());
+        that.kill();            // Kill merged scope
+        return r.unkeep().peephole();
+    }
+
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java
new file mode 100644
index 00000000..85c6cd34
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -0,0 +1,37 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
+
+/**
+ * The Start node represents the start of the function.  For now, we do not
+ * have any inputs to Start because our function does not yet accept
+ * parameters.  When we add parameters the value of Start will be a tuple, and
+ * will require Projections to extract the values.  We discuss this in detail
+ * in Chapter 9: Functions and Calls.
+ */
+public class StartNode extends MultiNode {
+
+    final TypeTuple _args;
+    
+    public StartNode(Type[] args) {
+        super();
+        _args = new TypeTuple(args);
+    }
+
+    @Override
+    public String label() { return "Start"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+      return sb.append(label());
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+    @Override
+    public TypeTuple compute() { return _args; }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java
new file mode 100644
index 00000000..f17c7ec7
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -0,0 +1,51 @@
+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() {
+        int len = nIns();
+        for( int i=0; i<nIns(); i++ )
+            if( in(i)._type==Type.XCONTROL )
+                delDef(i--);
+        if( len != nIns() ) return this;
+        return null;
+    }
+
+    public Node addReturn(Node node) {
+        return add_def(node);
+    }
+
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/SubNode.java
new file mode 100644
index 00000000..41d7d092
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -0,0 +1,41 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class SubNode extends Node {
+    public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Sub"; }
+
+    @Override public String glabel() { return "-"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append("-"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0 &&
+            in(2)._type instanceof TypeInteger i1) {
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()-i1.value());
+            return i0.meet(i1);
+        }
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        // Sub of same is 0
+        if( in(1)==in(2) )
+            return new ConstantNode(TypeInteger.constant(0));
+
+        return null;
+    }
+
+    @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java
new file mode 100644
index 00000000..78908375
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -0,0 +1,77 @@
+package com.seaofnodes.simple.type;
+
+
+/**
+ * These types are part of a Monotone Analysis Framework,
+ * @see <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>.
+ * <p> 
+ * The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a>
+ * <p>
+ * This wild lattice theory will be needed later to allow us to easily beef up
+ * the analysis and optimization of the Simple compiler... but we don't need it
+ * now, just know that it is coming along in a later Chapter.
+ * <p>g
+ * One of the fun things here is that while the theory is deep and subtle, the
+ * actual implementation is darn near trivial and is generally really obvious
+ * what we're doing with it.  Right now, it's just simple integer math to do
+ * simple constant folding e.g. 1+2 == 3 stuff.
+ */    
+
+public class Type {
+
+    // ----------------------------------------------------------
+    // Simple types are implemented fully here.  "Simple" means: the code and
+    // type hierarchy are simple, not that the Type is conceptually simple.
+    static final byte TBOT    = 0; // Bottom (ALL)
+    static final byte TTOP    = 1; // Top    (ANY)
+    static final byte TCTRL   = 2; // Ctrl flow bottom
+    static final byte TXCTRL  = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all)
+    static final byte TSIMPLE = 4; // End of the Simple Types
+    static final byte TINT    = 5; // All Integers; see TypeInteger
+    static final byte TTUPLE  = 6; // Tuples; finite collections of unrelated Types, kept in parallel
+
+    public final byte _type;
+
+    public boolean is_simple() { return _type < TSIMPLE; }
+    private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL","~CONTROL"};
+    protected Type(byte type) { _type = type; }
+
+    public static final Type BOTTOM   = new Type( TBOT   ); // ALL
+    public static final Type TOP      = new Type( TTOP   ); // ANY
+    public static final Type CONTROL  = new Type( TCTRL  ); // Ctrl
+    public static final Type XCONTROL = new Type( TXCTRL ); // ~Ctrl
+
+    public boolean isConstant() { return _type == TTOP || _type == TXCTRL; }
+
+    public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
+
+    public final Type meet(Type t) {
+        // Shortcut for the self case
+        if( t == this ) return this;
+        // Same-type is always safe in the subclasses
+        if( _type==t._type ) return xmeet(t);
+        // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this".
+        if(   is_simple() ) return this.xmeet(t   );
+        if( t.is_simple() ) return t   .xmeet(this);
+        return BOTTOM;        // Mixing 2 unrelated types
+    }
+
+    // Compute meet right now.  Overridden in subclasses.
+    // Handle cases where 'this.is_simple()' and unequal to 't'.
+    // Subclassed xmeet calls can assert that '!t.is_simple()'.
+    protected Type xmeet(Type t) {
+        assert is_simple(); // Should be overridden in subclass
+        // ANY meet anything is thing; thing meet ALL is ALL
+        if( _type==TBOT || t._type==TTOP ) return this;
+        if( _type==TTOP || t._type==TBOT ) return    t;
+        // 'this' is {TCTRL,TXCTRL}
+        if( !t.is_simple() ) return BOTTOM;
+        // 't' is {TCTRL,TXCTRL}
+        return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL;
+    }
+
+    @Override
+    public final String toString() {
+        return _print(new StringBuilder()).toString();
+    }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
new file mode 100644
index 00000000..93f5eae3
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -0,0 +1,63 @@
+package com.seaofnodes.simple.type;
+
+/**
+ * Integer Type
+ */
+public class TypeInteger extends Type {
+
+    public final static TypeInteger TOP = new TypeInteger(false, 0);
+    public final static TypeInteger BOT = new TypeInteger(false, 1);
+    public final static TypeInteger ZERO= new TypeInteger(true, 0);
+
+    private final boolean _is_con;
+
+    /**
+     * The constant value or
+     * if not constant then 0=bottom, 1=top.
+     */
+    private final long _con;
+
+    public TypeInteger(boolean is_con, long con) {
+        super(TINT);
+        _is_con = is_con;
+        _con = con;
+    }
+
+    public static TypeInteger constant(long con) { return new TypeInteger(true, con); }
+
+    public boolean isTop() { return !_is_con && _con==0; }
+    public boolean isBot() { return !_is_con && _con==1; }
+
+    @Override 
+    public StringBuilder _print(StringBuilder sb) {
+        if (isTop()) return sb.append("IntTop");
+        if (isBot()) return sb.append("IntBot");
+        return sb.append(_con);
+    }
+
+    @Override
+    public boolean isConstant() { return _is_con; }
+
+    public long value() { return _con; }
+
+    @Override
+    public Type xmeet(Type other) {
+        if( this==other ) return this;
+        if (!(other instanceof TypeInteger i)) return super.meet(other);
+        // BOT wins
+        if (   isBot() ) return this;
+        if ( i.isBot() ) return i   ;
+        // TOP loses
+        if ( i.isTop() ) return this;
+        if (   isTop() ) return i   ;
+        assert isConstant() && i.isConstant();
+        return _con==i._con ? this : TypeInteger.BOT;
+    }
+
+    @Override
+    public boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( !(o instanceof TypeInteger i) ) return false;
+        return _con==i._con && _is_con==i._is_con;
+    }
+}
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
new file mode 100644
index 00000000..2e6152a8
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -0,0 +1,32 @@
+package com.seaofnodes.simple.type;
+
+public class TypeTuple extends Type {
+  
+    public final Type[] _types;
+
+    public TypeTuple(Type... _types) {
+        super(TTUPLE);
+        this._types = _types;
+    }
+
+    @Override
+    public Type xmeet(Type other) {
+        throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented");
+    }
+
+    @Override
+    public StringBuilder _print(StringBuilder sb) {
+        sb.append("[ ");
+        for( Type t : _types )
+            t._print(sb).append(",");
+        sb.setLength(sb.length()-1);
+        sb.append("]");
+        return sb;
+    }
+
+    public static final TypeTuple IF_BOTH    = new TypeTuple(new Type[]{Type.CONTROL, Type.CONTROL});
+    public static final TypeTuple IF_NEITHER = new TypeTuple(new Type[]{Type.XCONTROL,Type.XCONTROL});
+    public static final TypeTuple IF_TRUE    = new TypeTuple(new Type[]{Type.CONTROL, Type.XCONTROL});
+    public static final TypeTuple IF_FALSE   = new TypeTuple(new Type[]{Type.XCONTROL,Type.CONTROL});
+
+}