Chapter 9 (#66)

* chapter9 * merge fixes to chapter8 * Ch 9 notes * Ch 9 work Add a Iterate phase, after parsing. Add a Worklist with fast dup removal & rand pull. Add a Node.iter() call which returns progress or null. Peephole calls it. Iter() also asserts that Types make monotonic progress. Intern all types, so we can do a cheap/easy "isa" test. * GVN * rename temporarily * Apply Cliff's worklist changes * Apply Cliff's GVN changes * Revert "GVN" This reverts commit 9dc6db1cac7e40de4a58333cbc3c9c3e7c088e6f. * Revert "Ch 9 work" This reverts commit df5b74e6c017a4f237a5d1a550a83b40a7928876. * Fix 3-1+2 Was computing as 3-(1+2) == 0, not 4 as expected. Add tests. Unlock in swap12. * Missed some cut-n-paste changes * Break up the test file per-chapter * Fix keep-alive while looping expressions Must "hook" LHS prior to calling peepholes * Ch9 Region optimization Bug fix, GVN hits 2 inProgress Loops Bug fix lifetime tracking when parsing dead code Bug fix debug find call GraphViz post-iterate * Readme overhaul Progress on Ch 9 readme * Fix bugs hashcode Was relying on label() hashCode for Phi, Proj; since this is debug-only cannot be relied on. Proj relies on _idx field, Phi needs a !inProgress check. * Constant nodes print "#" before con * Add a farther neighbor check Peeps that check more than the nearest neighbor register a dependency on the Node that failed them. Should that Node later change, the peep root is put back on the worklist and revisited. * Fix addDeps assert Unwind golden test print, print smarter. Unlock edges in subsume * Update README * shuffle adddeps forward one its needed again shortly in another test, so just cover it now * Fix fuzzer bugs Peep x+(-y) to x-y Handle TOP inputs; didn't think it could happen before running an optimistic pass, but fuzzer proved me wrong. Deleting an input can recursively delete the self-node. When checking the compute() type assert, delay setting _type so the method can just be re-run in the debugger. Missing addDep in Phi Parser mis-handling stacked operators like "1+-2" or "1==!=<=<>=>2" Make Work list deterministic between tests. * Update fuzzer to run iterate (#62) * Update fuzzer to run iterate * Work seed is now reset by reset * A few more fuzzer tests Set _type in iter() even later, better debugging. Handle dead active scopes in visiualizer. Region ideal honors Loop invariants; finish Region ideal for single input; inProgress check is a little tighter. Type.isConstant is true strictly for lattice centerline constants. Clean up TypeInteger. ideaj warning removal * Fix all fuzzer bugs iter() does not call peep(), instead peep() is self-recursive. This allows Iterate() to call iter(), and not get into arbitrary recursive peep() changes that do not track on the worklist. Div, Minus, If all monotonic. Catch a bunch of progress issues. Robustify IRPrinter and Iterate and Region ideal * Reducer could run into an infinite loop (#63) * Write up how the Evaluator works (#64) * Write up how the Evaluator works * Some small improvements and a slightly better wrap up. * Series of fuzzer bugs. Fix monotonicity for all data nodes. Generic compute intercept for data nodes, check all inputs for TOP/BOTTOM, and again for IntDataNodes. Fix general progress bug allow high Types as constants. Fix progress Region 1-input has obvious idom. Make shortcut for fuzzer; renames Fuzzer to not have "Test" in the class name. Fix invert comment in TypeInteger * All fuzzer tests pass Turn off expensive assert accidentally turned on CSE needs to join types. Add a type join. Missing dep in Phi * More README * Hacking alternative way to fix the type compute * Node is no longer IntSupplier Renamed Work to WorkList Renamed Iterate to IterOptim Renamed Node.iter() to Node.peepholeOpt() WorkList expects elements to be of Node * Add an example of GVN * Rename the method depsClear to moveDepsToWorklist - to better capture what it actually does. * Add a second example of GVN benefits * Fix typo * Add example of worklist opt * Prepare to allow alternative post parse worklist opt * Alternative WorkList opt that has following differences: 1. It does not require dependencies between nodes 2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step. 3. It is simple * Alternative WorkList opt that has following differences: 1. It does not require dependencies between nodes 2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step. 3. It is simple * The RPO list was incomplete as it only identified the subgraph accessible from the STOP node. * Fix iter count * Add test suggested by Xmilia * Fix bug where after the region is peeped the phis get consistent number of inputs * Fix bug where after the region is peeped the phis get consistent number of inputs * Dump out stats on how many nodes we peepd during the post parse iterative opt. * Make it easy to switch the IterOpt * Use deps based worklist by default * Sharper worklist add * Copy across Cliff's changes * Merge changes to Iterate * Revert failing change * Update readme * Add comments / update docs to explain the patterns where we call addDep(). * As before, unconditionally made dep a dependent of region. * Fix a lot of missing dep issues Rename IterOptim -> IterPeeps Some grammar changes in comments & readme * Bump up fuzzer limits, more testing Missing dep in idom calc in IfNode. Missed idom cache clear on Region edit. * Remove RPO based peeps O(n^2) behavior * Minor updates README * fix compile bug --------- Co-authored-by: Cliff Click <cliffc@acm.org> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Darrick Wiebe <darrickw@untether.ai>
author: Dibyendu Majumdar <dibyendumajumdar@users.noreply.github.com> 2024-03-03 17:55:47 +0000
committer: GitHub <noreply@github.com> 2024-03-03 17:55:47 +0000
commit: c3842e2a01522f52ae4690de3e9c90efa33f0f27 (patch)
tree: bcedc8d459d74a57acc7ea3b1b968aa60db4a5e6 /chapter09/src/main/java
parent: 29bc63423aeba9327b2e60959f8dbb2c8e718a29 (diff)
download: Simple-c3842e2a01522f52ae4690de3e9c90efa33f0f27.tar.gz
Simple-c3842e2a01522f52ae4690de3e9c90efa33f0f27.zip
28 files changed, 3650 insertions, 0 deletions
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/chapter09/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
new file mode 100644
index 00000000..c4b349bd
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/GraphEvaluator.java
@@ -0,0 +1,181 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.HashMap;
+
+public class GraphEvaluator {
+
+    public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT }
+
+    public record Result(ResultType type, long value) {}
+
+    /**
+     * Find the start node from some node in the graph or null if there is no start node
+     */
+    private static StartNode findStart(BitSet visit, Node node) {
+        if (node == null) return null;
+        if (node instanceof StartNode start) return start;
+        if( visit.get(node._nid) ) return null;
+        visit.set(node._nid);
+        for( Node def : node._inputs ) {
+            var res = findStart(visit,def);
+            if( res != null ) return res;
+        }
+        for( Node use : node._outputs ) {
+            var res = findStart(visit,use);
+            if( res != null ) return res;
+        }
+        return null;
+    }
+
+    /**
+     * Find the control output from a control node
+     */
+    private static Node findControl(Node control) {
+        for( Node use : control._outputs ) {
+            if (use.isCFG()) return use;
+        }
+        return null;
+    }
+
+    /**
+     * Find the projection for a node
+     */
+    private static ProjNode findProjection(Node node, int idx) {
+        for( Node use : node._outputs ) {
+            if (use instanceof ProjNode proj && proj._idx == idx) return proj;
+        }
+        return null;
+    }
+
+    /**
+     * Cache values for phi and parameter projection nodes.
+     */
+    private final HashMap<Node, Long> cacheValues = new HashMap<>();
+    /**
+     * Cache for loop phis as they can depend on itself or other loop phis
+     */
+    private long[] loopPhiCache = new long[16];
+
+    private GraphEvaluator() {
+    }
+
+    private long div(DivNode div) {
+        long in2 = getValue(div.in(2));
+        return in2 == 0 ? 0 : getValue(div.in(1)) / in2;
+    }
+
+    /**
+     * Calculate the value of a node
+     */
+    private long getValue(Node node) {
+        var cache = cacheValues.get(node);
+        if (cache != null) return cache;
+        return switch (node) {
+            case ConstantNode cons  -> ((TypeInteger)cons.compute()).value();
+            case AddNode      add   -> getValue(add.in(1)) + getValue(add.in(2));
+            case BoolNode.EQ  eq    -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0;
+            case BoolNode.LE  le    -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0;
+            case BoolNode.LT  lt    -> getValue(lt.in(1)) <  getValue(lt.in(2)) ? 1 : 0;
+            case DivNode      div   -> div(div);
+            case MinusNode    minus -> -getValue(minus.in(1));
+            case MulNode      mul   -> getValue(mul.in(1)) * getValue(mul.in(2));
+            case NotNode      not   -> getValue(not.in(1)) == 0 ? 1 : 0;
+            case SubNode      sub   -> getValue(sub.in(1)) - getValue(sub.in(2));
+            default                 -> throw Utils.TODO("Unexpected node " + node);
+        };
+    }
+
+    /**
+     * Special case of latchPhis when phis can depend on phis of the same region.
+     */
+    private void latchLoopPhis(RegionNode region, Node prev) {
+        int idx = Utils.find(region._inputs, prev);
+        assert idx > 0;
+        int i = 0;
+        for( Node use : region._outputs ) {
+            if (use instanceof PhiNode phi) {
+                var value = getValue(phi.in(idx));
+                if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2);
+                loopPhiCache[i++] = value;
+            }
+        }
+        i = 0;
+        for( Node use : region._outputs ) {
+            if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]);
+        }
+    }
+
+    /**
+     * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region.
+     */
+    private void latchPhis(RegionNode region, Node prev) {
+        int idx = Utils.find(region._inputs, prev);
+        assert idx > 0;
+        for( Node use : region._outputs ) {
+            if (use instanceof PhiNode phi) {
+                var value = getValue(phi.in(idx));
+                cacheValues.put(phi, value);
+            }
+        }
+    }
+
+    /**
+     * Run the graph until either a return is found or the number of loop iterations are done.
+     */
+    private Result evaluate(StartNode start, long parameter, int loops) {
+        var parameter1 = findProjection(start, 1);
+        if (parameter1 != null) cacheValues.put(parameter1, parameter);
+        Node control = findProjection(start, 0);
+        Node prev = start;
+        while (control != null) {
+            Node next;
+            switch (control) {
+                case RegionNode region -> {
+                    if (region instanceof LoopNode && region.in(1) != prev) {
+                        if (loops--<=0) return new Result(ResultType.TIMEOUT, 0);
+                        latchLoopPhis(region, prev);
+                    } else {
+                        latchPhis(region, prev);
+                    }
+                    next = findControl(region);
+                }
+                case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1);
+                case ReturnNode ret -> {
+                    return new Result(ResultType.VALUE, getValue(ret.in(1)));
+                }
+                case ProjNode ignored -> next = findControl(control);
+                default -> throw Utils.TODO("Unexpected control node " + control);
+            }
+            prev = control;
+            control = next;
+        }
+        return new Result(ResultType.FALLTHROUGH, 0);
+    }
+
+    public static long evaluate(Node graph) {
+        return evaluate(graph, 0);
+    }
+
+    public static long evaluate(Node graph, long parameter) {
+        return evaluate(graph, parameter, 1000);
+    }
+
+    public static long evaluate(Node graph, long parameter, int loops) {
+        var res = evaluateWithResult(graph, parameter, loops);
+        if (res.type== ResultType.TIMEOUT) throw new RuntimeException("Timeout");
+        return res.value;
+    }
+
+    public static Result evaluateWithResult(Node graph, long parameter, int loops) {
+        var start = findStart(new BitSet(), graph);
+        if (start == null) return new Result(ResultType.TIMEOUT, 0);
+        var evaluator = new GraphEvaluator();
+        return evaluator.evaluate(start, parameter, loops);
+    }
+
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter09/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
new file mode 100644
index 00000000..657593d2
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -0,0 +1,262 @@
+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 {
+
+    /**
+     * If set to true we put the control nodes in a separate cluster from
+     * data nodes.
+     */
+    boolean _separateControlCluster = false;
+
+    public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; }
+    public GraphVisualizer() { this(false); }
+
+    public String generateDotOutput(Parser parse) { return generateDotOutput(parse.STOP,parse._scope,parse._xScopes); }
+    public String generateDotOutput(StopNode stop, Node scope, Stack<ScopeNode> xScopes) {
+
+        // Since the graph has cycles, we need to create a flat list of all the
+        // nodes in the graph.
+        Collection<Node> all = findAll(stop, scope);
+        StringBuilder sb = new StringBuilder();
+        sb.append("digraph chapter09 {\n");
+        sb.append("/*\n");
+        sb.append(stop._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");
+
+        // Force nested scopes to order
+        sb.append("\tcompound=\"true\";\n");
+
+        // Just the Nodes first, in a cluster no edges
+        nodes(sb, all);
+        
+        // Now the scopes, in a cluster no edges
+        if( xScopes != null )
+            for( ScopeNode xscope : xScopes )
+                if( !xscope.isDead() )
+                    scope( sb, xscope );
+
+        // Walk the Node edges
+        nodeEdges(sb, all);
+
+        // Walk the active Scope edges
+        if( xScopes != null )
+            for( ScopeNode xscope : xScopes )
+                if( !xscope.isDead() )
+                    scopeEdges( sb, xscope );
+        
+        sb.append("}\n");
+        return sb.toString();
+    }
+
+    private void nodesByCluster(StringBuilder sb, boolean doCtrl, Collection<Node> all) {
+        if (!_separateControlCluster && doCtrl) // all nodes in 1 cluster
+            return;
+        // Just the Nodes first, in a cluster no edges
+        sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\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
+            if (_separateControlCluster && doCtrl && !n.isCFG()) continue;
+            if (_separateControlCluster && !doCtrl && n.isCFG()) continue;
+            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 ");
+                else if (n instanceof PhiNode) sb.append("style=filled fillcolor=lightyellow ");
+                sb.append("label=\"").append(lab).append("\" ");
+            }
+            sb.append("];\n");
+        }
+        if (!_separateControlCluster) {
+            // 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 nodes(StringBuilder sb, Collection<Node> all) {
+        nodesByCluster(sb, true, all);
+        nodesByCluster(sb, false, all);
+    }
+
+    // Build a nested scope display, walking the _prev edge
+    private void scope( StringBuilder sb, ScopeNode scope ) {
+        sb.append("\tnode [shape=plaintext];\n");
+        int level=1;
+        for( int idx = scope._scopes.size()-1; idx>=0; idx-- ) {
+            var syms = scope._scopes.get(idx);
+            String scopeName = makeScopeName(scope, 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
+            int scopeLevel = scope._scopes.size()-level;
+            sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(scopeLevel).append("</TD>");
+            for(String name: syms.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-1 ) ); // 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;
+            for( int i=0; i<n.nIns(); i++ ) {
+                Node def = n.in(i);
+                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");
+                    // Backedges do not add a ranking constraint
+                    if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) )
+                        sb.append(" constraint=false");                        
+                    sb.append("];\n");
+                }
+            }
+        }
+    }
+    
+    // Walk the scope edges
+    private void scopeEdges( StringBuilder sb, ScopeNode scope ) {
+        sb.append("\tedge [style=dashed color=cornflowerblue];\n");
+        int level=1;
+        for( int i = scope._scopes.size()-1; i>=0; i-- ) {
+            var syms = scope._scopes.get(i);
+            String scopeName = makeScopeName(scope, level);
+            for( String name : syms.keySet() ) {
+                int idx = syms.get(name);
+                Node def = scope.in(idx);
+                while( def instanceof ScopeNode lazy )
+                    def = lazy.in(idx);
+                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(Node stop, Node scope) {
+        final HashMap<Integer, Node> all = new HashMap<>();
+        for( Node n : stop._inputs )
+            walk(all, n);
+        if( scope != null )
+            for( Node n : scope._inputs )
+                walk(all, n);
+        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)
+            walk(all, c);
+        for( Node c : n._outputs )
+            walk(all, c);
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter09/src/main/java/com/seaofnodes/simple/IRPrinter.java
new file mode 100644
index 00000000..c06ac9d0
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -0,0 +1,125 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.LoopNode;
+import com.seaofnodes.simple.node.Node;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+
+public class IRPrinter {
+
+    // Another bulk pretty-printer.  Makes more effort at basic-block grouping.
+    public static String prettyPrint(Node node, int depth) {
+        // First, a Breadth First Search at a fixed depth.
+        BFS bfs = new BFS(node,depth);
+        // Convert just that set to a post-order
+        ArrayList<Node> rpos = new ArrayList<>();
+        BitSet visit = new BitSet();
+        for( int i=bfs._lim; i< bfs._bfs.size(); i++ )
+            postOrd( bfs._bfs.get(i), rpos, visit, bfs._bs);
+        // Reverse the post-order walk
+        StringBuilder sb = new StringBuilder();
+        boolean gap=false;
+        for( int i=rpos.size()-1; i>=0; i-- ) {
+            Node n = rpos.get(i);
+            if( n.isCFG() || n.isMultiHead() ) {
+                if( !gap ) sb.append("\n"); // Blank before multihead
+                n._printLine(sb); // Print head
+                while( --i >= 0 ) {
+                    Node t = rpos.get(i);
+                    if( !t.isMultiTail() ) { i++; break; }
+                    t._printLine(sb);
+                }
+                sb.append("\n"); // Blank after multitail
+                gap = true;
+            } else {
+                n._printLine( sb );
+                gap = false;
+            }
+        }
+        return sb.toString();
+    }
+
+    private static void postOrd(Node n, ArrayList<Node> rpos, BitSet visit, BitSet bfs) {
+        if( !bfs.get(n._nid) )
+            return;  // Not in the BFS visit
+        if( visit.get(n._nid) ) return; // Already post-order walked
+        visit.set(n._nid);
+        // First walk the CFG, then everything
+        if( n.isCFG() ) {
+            for( Node use : n._outputs )
+                if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) )
+                    postOrd(use, rpos,visit,bfs);
+            for( Node use : n._outputs )
+                if( use!=null && use.isCFG() )
+                    postOrd(use,rpos,visit,bfs);
+        }
+        for( Node use : n._outputs )
+            if( use != null )
+                postOrd(use, rpos,visit,bfs);
+        // Post-order
+        rpos.add(n);
+    }
+
+    // Breadth-first search, broken out in a class to keep in more independent.
+    // Maintains a root-set of Nodes at the limit (or past by 1 if MultiHead).
+    public static class BFS {
+        // A breadth first search, plus MultiHeads for any MultiTails
+        public final ArrayList<Node> _bfs;
+        public final BitSet _bs; // Visited members by node id
+        public final int _depth; // Depth limit
+        public final int _lim; // From here to _bfs._len can be roots for a reverse search
+        public BFS( Node base, int d ) {
+            _depth = d;
+            _bfs = new ArrayList<>();
+            _bs = new BitSet();
+
+            add(base);                 // Prime the pump
+            int idx=0, lim=1;          // Limit is where depth counter changes
+            while( idx < _bfs.size() ) { // Ran out of nodes below depth
+                Node n = _bfs.get(idx++);
+                for( Node def : n._inputs )
+                    if( def!=null && !_bs.get(def._nid) )
+                        add(def);
+                if( idx==lim ) {    // Depth counter changes at limit
+                    if( --d < 0 )
+                        break;      // Ran out of depth
+                    lim = _bfs.size();  // New depth limit
+                }
+            }
+            // Toss things past the limit except multi-heads
+            while( idx < _bfs.size() ) {
+                Node n = _bfs.get(idx);
+                if( n.isMultiHead() ) idx++;
+                else del(idx);
+            }
+            // Root set is any node with no inputs in the visited set
+            lim = _bfs.size();
+            for( int i=_bfs.size()-1; i>=0; i-- )
+                if( !any_visited(_bfs.get(i)) )
+                    swap( i,--lim);
+            _lim = lim;
+        }
+        void swap( int x, int y ) {
+            if( x==y ) return;
+            Node tx = _bfs.get(x);
+            Node ty = _bfs.get(y);
+            _bfs.set(x,ty);
+            _bfs.set(y,tx);
+        }
+        void add(Node n) {
+            _bfs.add(n);
+            _bs.set(n._nid);
+        }
+        void del(int idx) {
+            Node n = Utils.del(_bfs, idx);
+            _bs.clear(n._nid);
+        }
+        boolean any_visited( Node n ) {
+            for( Node def : n._inputs )
+                if( def!=null && _bs.get(def._nid) )
+                    return true;
+            return false;
+        }
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter09/src/main/java/com/seaofnodes/simple/IterPeeps.java
new file mode 100644
index 00000000..8103103c
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -0,0 +1,204 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.ConstantNode;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.node.StopNode;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.Random;
+
+/**
+ * The IterOptim runs after parsing. It iterates the peepholes to a fixed point
+ * so that no more peepholes apply.  This should be linear because peepholes rarely
+ * (never?)  increase code size.  The graph should monotonically reduce in some
+ * dimension, which is usually size.  It might also reduce in e.g. number of
+ * MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper
+ * ones.
+ *
+ * The theoretical overall worklist is mindless just grabbing the next thing and
+ * doing it.  If the graph changes, put the neighbors on the worklist.  Lather,
+ * Rinse, Repeat until the worklist runs dry.
+ *
+ * The main issues we have to deal with:
+ *
+ * <ul>
+ * <li>Nodes have uses; replacing some set of Nodes with another requires more graph
+ *   reworking.  Not rocket science, but it can be fiddly.  Its helpful to have a
+ *   small set of graph munging utilities, and the strong invariant that the graph
+ *   is stable and correct between peepholes.  In our case `Node.subsume` does
+ *   most of the munging, building on our prior stable Node utilities.</li>
+ *
+ * <li>Changing a Node also changes the graph "neighborhood".  The neigbors need to
+ *   be checked to see if THEY can also peephole, and so on.  After any peephole
+ *   or graph update we put a Nodes uses and defs on the worklist.</li>
+ *
+ * <li>Our strong invariant is that for all Nodes, either they are on the worklist
+ *   OR no peephole applies.  This invariant is easy to check, although expensive.
+ *   Basically the normal "iterate peepholes to a fixed point" is linear, and this
+ *   check is linear at each peephole step... so quadratic overall.  Its a useful
+ *   assert, but one we can disable once the overall algorithm is stable - and
+ *   then turn it back on again when some new set of peepholes is misbehaving.
+ *   The code for this is turned on in `IterOptim.iterate` as `assert
+ *   progressOnList(stop);`</li>
+ * </ul>
+ */
+public abstract class IterPeeps {
+
+    private static final WorkList<Node> WORK = new WorkList<>();
+
+    public static <N extends Node> N add( N n ) {
+        return (N)WORK.push(n);
+    }
+
+    public static void addAll( ArrayList<Node> ary ) {
+        WORK.addAll(ary);
+    }
+
+    /**
+     * Iterate peepholes to a fixed point
+     */
+    public static StopNode iterate(StopNode stop, boolean show) {
+        assert progressOnList(stop);
+        int cnt=0;
+
+        Node n;
+        while( (n=WORK.pop()) != null ) {
+            if( n.isDead() )  continue;
+            cnt++;              // Useful for debugging, searching which peephole broke things
+            Node x = n.peepholeOpt();
+            if( x != null ) {
+                if( x.isDead() ) continue;
+                // peepholeOpt can return brand-new nodes, needing an initial type set
+                if( x._type==null ) x.setType(x.compute());
+                // Changes require neighbors onto the worklist
+                if( x != n || !(x instanceof ConstantNode) ) {
+                    // All outputs of n (changing node) not x (prior existing node).
+                    for( Node z : n._outputs ) WORK.push(z);
+                    // Everybody gets a free "go again" in case they didn't get
+                    // made in their final form.
+                    WORK.push(x);
+                    // If the result is not self, revisit all inputs (because
+                    // there's a new user), and replace in the graph.
+                    if( x != n ) {
+                        for( Node z : n. _inputs ) WORK.push(z);
+                        n.subsume(x);
+                    }
+                }
+                // If there are distant neighbors, move to worklist
+                n.moveDepsToWorklist();
+                assert progressOnList(stop); // Very expensive assert
+            }
+        }
+
+        if( show )
+            System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null));
+        return stop;
+    }
+
+    // Visit ALL nodes and confirm the invariant:
+    //   Either you are on the WORK worklist OR running `iter()` makes no progress.
+    
+    // This invariant ensures that no progress is missed, i.e., when the
+    // worklist is empty we have indeed done all that can be done.  To help
+    // with debugging, the {@code assert} is broken out in a place where it is easy to
+    // stop if a change is found.
+
+    // Also, the normal usage of `iter()` may attempt peepholes with distance
+    // neighbors and these should fail, but will then try to add dependencies
+    // {@link #Node.addDep} which is a side effect in an assert.  The {@link
+    // #midAssert} is used to stop this side effect.
+    private static boolean MID_ASSERT;
+    public static boolean midAssert() { return MID_ASSERT; }
+    private static boolean progressOnList(Node stop) {
+        MID_ASSERT = true;
+        int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT;
+        Node changed = stop.walk( n -> {
+                if( WORK.on(n) ) return null;
+                Node m = n.peepholeOpt();
+                if( m==null ) return null;
+                System.err.println("BREAK HERE FOR BUG");
+                return m;
+            });
+        Node.ITER_CNT = old_cnt;  Node.ITER_NOP_CNT = old_nop;
+        MID_ASSERT = false;
+        return changed==null;
+    }
+
+    public static void reset() {
+        WORK.clear();
+    }
+
+    /**
+     * Classic WorkList, with a fast add/remove, dup removal, random pull.
+     * The Node's nid is used to check membership in the worklist.
+     */
+    public static class WorkList<E extends Node> {
+
+        private Node[] _es;
+        private int _len;
+        private final BitSet _on;   // Bit set if Node._nid is on WorkList
+        private final Random _R;    // For randomizing pull from the WorkList
+        private final long _seed;
+
+        /* Useful stat - how many nodes are processed in the post parse iterative opt */
+        private long _totalWork = 0;
+
+        WorkList() { this(123); }
+        WorkList(long seed) {
+            _es = new Node[1];
+            _len=0;
+            _on = new BitSet();
+            _seed = seed;
+            _R = new Random();
+            _R.setSeed(_seed);
+        }
+
+        /**
+         * Pushes a Node on the WorkList, ensuring no duplicates
+         * If Node is null it will not be added.
+         */
+        public E push( E x ) {
+            if( x==null ) return null;
+            int idx = x._nid;
+            if( !_on.get(idx) ) {
+                _on.set(idx);
+                if( _len==_es.length )
+                    _es = Arrays.copyOf(_es,_len<<1);
+                _es[_len++] = x;
+                _totalWork++;
+            }
+            return x;
+        }
+
+        public void addAll( ArrayList<E> ary ) {
+            for( E n : ary )
+                push(n);
+        }
+
+        /**
+         * True if Node is on the WorkList
+         */
+        boolean on( E x ) { return _on.get(x._nid); }
+
+        /**
+         * Removes a random Node from the WorkList; null if WorkList is empty
+         */
+        E pop() {
+            if( _len == 0 ) return null;
+            int idx = _R.nextInt(_len);
+            E x = (E)_es[idx];
+            _es[idx] = _es[--_len]; // Compress array
+            _on.clear(x._nid);
+            return x;
+        }
+
+        public void clear() {
+            _len = 0;
+            _on.clear();
+            _R.setSeed(_seed);
+            _totalWork = 0;
+        }
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/Parser.java b/chapter09/src/main/java/com/seaofnodes/simple/Parser.java
new file mode 100644
index 00000000..5e7da8f8
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/Parser.java
@@ -0,0 +1,660 @@
+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 {
+  
+    /**
+     * 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 #_xScopes
+     */
+    public ScopeNode _scope;
+
+    /**
+     * List of keywords disallowed as identifiers
+     */
+    private final HashSet<String> KEYWORDS = new HashSet<>(){{
+            add("break");
+            add("continue");
+            add("else");
+            add("false");
+            add("if");
+            add("int");
+            add("return");
+            add("true");
+            add("while");
+        }};
+
+    
+    /**
+     * 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<>();
+
+    ScopeNode _continueScope;
+    ScopeNode _breakScope;
+
+    public Parser(String source, TypeInteger arg) {
+        Node.reset();
+        IterPeeps.reset();
+        _lexer = new Lexer(source);
+        _scope = new ScopeNode();
+        _continueScope = _breakScope = null;
+        START = new StartNode(new Type[]{ Type.CONTROL, arg });
+        STOP = new StopNode(source);
+    }
+
+    public Parser(String source) {
+        this(source, TypeInteger.BOT);
+    }
+
+    @Override
+    public String toString() { return _lexer.toString(); }
+  
+    String src() { return new String( _lexer._input ); }
+
+    // Debugging utility to find a Node by index
+    public static Node find(int nid) { return START.find(nid); }
+    
+    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) {
+        _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());
+        parseBlock();
+        _scope.pop();
+        _xScopes.pop();
+        if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
+        STOP.peephole();
+        if( show ) showGraph();
+        return STOP;
+    }
+
+    /**
+     * 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();
+        while (!peek('}') && !_lexer.isEOF())
+            parseStatement();
+        // Exit scope
+        _scope.pop();
+        return null;
+    }
+
+    /**
+     * 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("while")) return parseWhile();
+        else if (matchx("break")) return parseBreak();
+        else if (matchx("continue")) return parseContinue();
+        else if (matchx("#showGraph")) return require(showGraph(),";");
+        else return parseExpressionStatement();
+    }
+
+    /**
+     * Parses a while statement
+     *
+     * <pre>
+     *     while ( expression ) statement
+     * </pre>
+     * @return a {@link Node}, never {@code null}
+     */
+    private Node parseWhile() {
+
+        var savedContinueScope = _continueScope;
+        var savedBreakScope    = _breakScope;
+
+        require("(");
+
+        // Loop region has two control inputs, the first is the entry
+        // point, and second is back edge that is set after loop is parsed
+        // (see end_loop() call below).  Note that the absence of back edge is
+        // used as an indicator to switch off peepholes of the region and
+        // associated phis; see {@code inProgress()}.
+
+        ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here
+
+        // At loop head, we clone the current Scope (this includes all
+        // names in every nesting level within the Scope).
+        // We create phis eagerly for all the names we find, see dup().
+
+        // Save the current scope as the loop head
+        ScopeNode head = _scope.keep();
+        // Clone the head Scope to create a new Scope for the body.
+        // Create phis eagerly as part of cloning
+        _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis
+
+        // Parse predicate
+        var pred = require(parseExpression(), ")");
+        // IfNode takes current control and predicate
+        Node ifNode = new IfNode(ctrl(), pred).peephole();
+        // Setup projection nodes
+        Node ifT = new ProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
+        Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole();
+
+        // Clone the body Scope to create the break/exit Scope which accounts for any
+        // side effects in the predicate.  The break/exit Scope will be the final
+        // scope after the loop, and its control input is the False branch of
+        // the loop predicate.  Note that body Scope is still our current scope.
+        ctrl(ifF);
+        _xScopes.push(_breakScope = _scope.dup());
+
+        // No continues yet
+        _continueScope = null;
+        
+        // Parse the true side, which corresponds to loop body
+        // Our current scope is the body Scope
+        ctrl(ifT.unkeep());     // set ctrl token to ifTrue projection
+        parseStatement();       // Parse loop body
+
+        // Merge the loop bottom into other continue statements
+        if (_continueScope != null) {
+            _continueScope = jumpTo(_continueScope);
+            _scope.kill();
+            _scope = _continueScope;
+        }
+
+        // The true branch loops back, so whatever is current _scope.ctrl gets
+        // added to head loop as input.  endLoop() updates the head scope, and
+        // goes through all the phis that were created earlier.  For each phi,
+        // it sets the second input to the corresponding input from the back
+        // edge.  If the phi is redundant, it is replaced by its sole input.
+        var exit = _breakScope;
+        head.endLoop(_scope, exit);
+        head.unkeep().kill();
+
+        _xScopes.pop();       // Cleanup
+        _xScopes.pop();       // Cleanup
+
+        _continueScope = savedContinueScope;
+        _breakScope = savedBreakScope;
+
+        // At exit the false control is the current control, and
+        // the scope is the exit scope after the exit test.
+        return _scope = exit;
+    }
+
+    private ScopeNode jumpTo(ScopeNode toScope) {
+        ScopeNode cur = _scope.dup();
+        ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope
+        // Prune nested lexical scopes that have depth > than the loop head
+        // We use _breakScope as a proxy for the loop head scope to obtain the depth
+        while( cur._scopes.size() > _breakScope._scopes.size() )
+            cur.pop();
+        // If this is a continue then first time the target is null
+        // So we just use the pruned current scope as the base for the
+        // continue
+        if (toScope == null)
+            return cur;
+        // toScope is either the break scope, or a scope that was created here
+        assert toScope._scopes.size() <= _breakScope._scopes.size();
+        toScope.ctrl(toScope.mergeScopes(cur));
+        return toScope;
+    }
+
+    private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); }
+
+    private Node parseBreak   () { checkLoopActive(); return (   _breakScope = require(jumpTo(    _breakScope ),";"));  }
+    private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";"));  }
+
+    /**
+     * 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
+        Node ifNode = new IfNode(ctrl(), pred).peephole();
+        // Setup projection nodes
+        Node ifT = new ProjNode(ifNode.  keep(), 0, "True" ).peephole().keep();
+        Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep();
+        // In if true branch, the ifT proj node becomes the ctrl
+        // But first clone the scope and set it as current
+        int ndefs = _scope.nIns();
+        ScopeNode fScope = _scope.dup(); // Duplicate current scope
+        _xScopes.push(fScope); // For graph visualization we need all scopes
+
+        // Parse the true side
+        ctrl(ifT.unkeep());     // 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.unkeep());     // Ctrl token is now set to ifFalse projection
+        if (matchx("else")) {
+            parseStatement();
+            fScope = _scope;
+        }
+
+        if( tScope.nIns() != ndefs || fScope.nIns() != ndefs )
+            throw error("Cannot define a new name on one arm of an if");
+        
+        // Merge results
+        _scope = tScope;
+        _xScopes.pop();       // Discard pushed from graph display
+
+        return ctrl(tScope.mergeScopes(fScope));
+    }
+
+
+    /**
+     * Parses a return statement; "return" already parsed.
+     * The $ctrl edge is killed.
+     *
+     * <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}
+     */
+    Node showGraph() {
+        System.out.println(new GraphVisualizer().generateDotOutput(STOP,_scope,_xScopes));
+        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();
+        while( true ) {
+            int idx=0;  boolean negate=false;
+            // Test for any local nodes made, and "keep" lhs during peepholes
+            if( false ) ;
+            else if( match("==") ) { idx=2;  lhs = new BoolNode.EQ(lhs, null); }
+            else if( match("!=") ) { idx=2;  lhs = new BoolNode.EQ(lhs, null); negate=true; }
+            else if( match("<=") ) { idx=2;  lhs = new BoolNode.LE(lhs, null); }
+            else if( match("<" ) ) { idx=2;  lhs = new BoolNode.LT(lhs, null); }
+            else if( match(">=") ) { idx=1;  lhs = new BoolNode.LE(null, lhs); }
+            else if( match(">" ) ) { idx=1;  lhs = new BoolNode.LT(null, lhs); }
+            else break;
+            // Peepholes can fire, but lhs is already "hooked", kept alive
+            lhs.setDef(idx,parseAddition());
+            lhs = lhs.peephole();
+            if( negate )        // Extra negate for !=
+                lhs = new NotNode(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() {
+        Node lhs = parseMultiplication();
+        while( true ) {
+            if( false ) ;
+            else if( match("+") ) lhs = new AddNode(lhs,null);
+            else if( match("-") ) lhs = new SubNode(lhs,null);
+            else break;
+            lhs.setDef(2,parseMultiplication());
+            lhs = lhs.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();
+        while( true ) {
+            if( false ) ;
+            else if( match("*") ) lhs = new MulNode(lhs,null);
+            else if( match("/") ) lhs = new DivNode(lhs,null);
+            else break;
+            lhs.setDef(2,parseUnary());
+            lhs = lhs.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 <N extends Node> N require(N n, String syntax) {
+        if (match(syntax)) return n;
+        throw errorSyntax(syntax);
+    }
+
+    RuntimeException errorSyntax(String syntax) {
+        return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken());
+    }
+
+    public 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);
+        }
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/Utils.java b/chapter09/src/main/java/com/seaofnodes/simple/Utils.java
new file mode 100644
index 00000000..4d663c25
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/Utils.java
@@ -0,0 +1,39 @@
+package com.seaofnodes.simple;
+
+import java.util.ArrayList;
+
+public class Utils {
+    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
+    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
+
+    /**
+     *  Fast, constant-time, element removal.  Does not preserve order
+     *
+     *  @param array ArrayList to modify
+     *  @param i element to be removed
+     *  @return element removed
+     */
+    public static <E> E del(ArrayList<E> array, int i) {
+        if ( i >= 0 && i < array.size() ) {
+            E tmp = array.get(i);
+            E last = array.removeLast();
+            if (i < array.size()) array.set(i, last);
+            return tmp;
+        }
+        return null;
+    }
+
+    /**
+     * Search a list for an element by reference
+     *
+     * @param ary List to search in
+     * @param x Object to be searched
+     * @return >= 0 on success, -1 on failure
+     */
+    public static <E> int find( ArrayList<E> ary, E x ) {
+        for( int i=0; i<ary.size(); i++ )
+            if( ary.get(i)==x )
+                return i;
+        return -1;
+    }
+}
+\ No newline at end of file
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/AddNode.java
new file mode 100644
index 00000000..5ffb821e
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -0,0 +1,174 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.*;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("+"), visited);
+        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 in(1)._type.meet(in(2)._type);
+    }
+
+    @Override
+    public Node idealize () {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t2 = rhs._type;
+
+        // 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();
+
+        // x+(-y) becomes x-y
+        if( rhs instanceof MinusNode minus )
+            return new SubNode(lhs,minus.in(1));
+        
+        // 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) )
+            // Rotate; look for (add (phi cons) con/(phi cons))
+            return spine_cmp(lhs,rhs,this) ? swap12() : phiCon(this,true);
+
+        // Now we only see (add add non)
+
+        // Dead data cycle; comes about from dead infinite loops.  Do nothing,
+        // the loop will peep as dead after a bit.
+        if( lhs.in(1) == lhs )
+            return null;
+        
+        // Do we have (x + con1) + con2?
+        // Replace with (x + (con1+con2) which then fold the constants
+        // lhs.in(2) is con1 here
+        // If lhs.in(2) is not a constant, we add ourselves as a dependency
+        // because if it later became a constant then we could make this
+        // transformation.
+        if( lhs.in(2).addDep(this)._type.isConstant() && rhs._type.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 spine via rotates, to gather similar things together.
+        
+        // Do we rotate (x + y) + z
+        // into         (x + z) + y ?
+        if( spine_cmp(lhs.in(2),rhs,this) )
+            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,op);
+        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),op); // Will rotate with the Phi push
+        }
+        if( lphi==null ) return null;
+        
+        // RHS is a constant or a Phi of constants
+        if( !(rhs instanceof ConstantNode) && pcon(rhs,op)==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);
+    }
+
+    /**
+     * Tests if the op is a phi and has all constant inputs.
+     * If not, returns null.
+     * If op is a phi, but its inputs are not all constants, then dep is added as
+     * a dependency to the phi's non-const input, because if later the input turn into a constant
+     * dep can make progress.
+     */
+    static PhiNode pcon(Node op, Node dep) {
+        return op instanceof PhiNode phi && phi.allCons(dep) ? phi : null;
+    }
+        
+    // 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 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, Node dep ) {
+        if( lo._type.isConstant() ) return false;
+        if( hi._type.isConstant() ) return true ;
+
+        if( lo instanceof PhiNode lphi && lphi.region()._type==Type.XCONTROL ) return false;
+        if( hi instanceof PhiNode hphi && hphi.region()._type==Type.XCONTROL ) return false;
+
+        if( lo instanceof PhiNode && lo.allCons(dep) ) return false;
+        if( hi instanceof PhiNode && hi.allCons(dep) ) 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/chapter09/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/BoolNode.java
new file mode 100644
index 00000000..b4691b27
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -0,0 +1,59 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append(op()), visited);
+        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 in(1)._type.meet(in(2)._type);
+    }
+
+    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 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/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
new file mode 100644
index 00000000..c4ea08b5
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -0,0 +1,58 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.type.Type;
+
+import java.util.BitSet;
+
+/**
+ * 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, BitSet visited) {
+        return _con._print(sb);
+    }
+    
+    @Override public boolean isMultiTail() { return true; }
+    
+    @Override
+    public Type compute() { return _con; }
+
+    @Override
+    public Node idealize() { return null; }
+
+    @Override
+    boolean eq(Node n) {
+        ConstantNode con = (ConstantNode)n; // Contract
+        return _con==con._con;
+    }
+
+    @Override
+    int hash() { return _con.hashCode(); }
+
+    // Dead control is its own idom root
+    Node idom() { return null; }
+
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/DivNode.java
new file mode 100644
index 00000000..ed1a233c
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -0,0 +1,38 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("/"), visited);
+        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 in(1)._type.meet(in(2)._type);
+    }
+
+    @Override
+    public Node idealize() { return null; }
+  
+    @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/IfNode.java
new file mode 100644
index 00000000..52486772
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -0,0 +1,61 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.type.TypeTuple;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        sb.append("if( ");
+        return in(1)._print0(sb, visited).append(" )");
+    }
+
+    @Override public boolean isCFG() { return true; }
+    @Override public boolean isMultiHead() { 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 && ctrl()._type != Type.BOTTOM )
+            return TypeTuple.IF_NEITHER;
+        Node pred = pred();
+        Type t = pred._type;
+        // High types mean NEITHER side is reachable.
+        // Wait until the type falls to decide which way to go.
+        if( t == Type.TOP || t == TypeInteger.TOP )
+            return TypeTuple.IF_NEITHER;
+        // If constant is 0 then false branch is reachable
+        // Else true branch is reachable
+        if (t instanceof TypeInteger ti && ti.isConstant())
+            return ti==TypeInteger.ZERO ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE;
+        
+        return TypeTuple.IF_BOTH;
+    }
+    
+    @Override
+    public Node idealize() {
+        // Hunt up the immediate dominator tree.  If we find an identical if
+        // test on either the true or false branch, that side wins.
+        if( !pred()._type.isHighOrConst() )
+            for( Node dom = idom(), prior=this; dom!=null;  prior = dom, dom = dom.idom() )
+                if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) {
+                    setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole());
+                    return this;
+                }
+        return null;
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java
new file mode 100644
index 00000000..0b84f897
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -0,0 +1,29 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+import java.util.BitSet;
+
+public class LoopNode extends RegionNode {
+
+    public LoopNode( Node entry ) { super(null,entry,null); }
+
+    Node entry() { return in(1); }
+    Node back () { return in(2); }
+
+    @Override
+    public String label() { return "Loop"; }
+
+    @Override
+    public Type compute() {
+        if( inProgress() ) return Type.CONTROL;
+        return entry()._type;
+    }
+
+    @Override
+    public Node idealize() {
+        return inProgress() ? null : super.idealize();
+    }
+
+    @Override Node idom() { return entry(); }    
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/MinusNode.java
new file mode 100644
index 00000000..524f63a0
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -0,0 +1,30 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        in(1)._print0(sb.append("(-"), visited);
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeInteger i0)
+            return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
+        return TypeInteger.TOP.meet(in(1)._type);
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/MulNode.java
new file mode 100644
index 00000000..d63d2cb1
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -0,0 +1,57 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("*"), visited);
+        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 in(1)._type.meet(in(2)._type);
+    }
+
+    @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/chapter09/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/MultiNode.java
new file mode 100644
index 00000000..eced9a14
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -0,0 +1,14 @@
+package com.seaofnodes.simple.node;
+
+public abstract class MultiNode extends Node {
+    
+    public MultiNode(Node... inputs) { super(inputs); }
+
+    // Find a projection by index
+    ProjNode proj( int idx ) {
+        for( Node out : _outputs )
+            if( out instanceof ProjNode prj && prj._idx==idx )
+                return prj;
+        return null;
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java
new file mode 100644
index 00000000..7c82ffd5
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -0,0 +1,639 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IRPrinter;
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.type.Type;
+
+import java.util.*;
+import java.util.function.Function;
+
+/**
+ * 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;
+
+    
+    /**
+     * Immediate dominator tree depth, used to approximate a real IDOM during
+     * parsing where we do not have the whole program, and also peepholes
+     * change the CFG incrementally.
+     * <p>
+     * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
+     */
+    int _idepth;
+    
+    /**
+     * 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;
+    public static int UID() { return UNIQUE_ID; }
+
+    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(); }
+
+
+    // ------------------------------------------------------------------------
+    
+    // Debugger Printing.
+    
+    // {@code toString} is what you get in the debugger.  It has to print 1
+    // line (because this is what a debugger typically displays by default) and
+    // has to be robust with broken graph/nodes.
+    @Override
+    public final String toString() {  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(), new BitSet()).toString();
+    }
+    
+    // This is the common print: check for repeats, check for DEAD and print
+    // "DEAD" else call the per-Node print1.
+    final StringBuilder _print0(StringBuilder sb, BitSet visited) {
+        if (visited.get(_nid) && !(this instanceof ConstantNode) )
+            return sb.append(label());
+        visited.set(_nid);
+        return isDead()
+            ? sb.append(uniqueName()).append(":DEAD")
+            : _print1(sb, visited);
+    }
+    // Every Node implements this; a partial-line recursive print
+    abstract StringBuilder _print1(StringBuilder sb, BitSet visited);
+
+
+    // Print a node on 1 line, columnar aligned, as:
+    // NNID NNAME DDEF DDEF  [[  UUSE UUSE  ]]  TYPE
+    // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt
+    public void _printLine(StringBuilder sb ) {
+        sb.append("%4d %-7.7s ".formatted(_nid,label()));
+        if( _inputs==null ) {
+            sb.append("DEAD\n");
+            return;
+        }
+        for( Node def : _inputs )
+            sb.append(def==null ? "____ " : "%4d ".formatted(def._nid));
+        for( int i = _inputs.size(); i<3; i++ )
+            sb.append("     ");
+        sb.append(" [[  ");
+        for( Node use : _outputs )
+            sb.append(use==null ? "____ " : "%4d ".formatted(use._nid));
+        int lim = 5 - Math.max(_inputs.size(),3);
+        for( int i = _outputs.size(); i<lim; i++ )
+            sb.append("     ");
+        sb.append(" ]]  ");
+        if( _type!= null ) _type._print(sb);
+        sb.append("\n");
+    }
+
+    public String p(int depth) { return IRPrinter.prettyPrint(this,depth); }
+    
+    public boolean isMultiHead() { return false; }
+    public boolean isMultiTail() { return false; }
+    
+    // ------------------------------------------------------------------------
+    // Graph Node & Edge manipulation
+    
+    /**
+     * 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 Node out(int i) { return _outputs.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; }
+  
+    /**
+     * 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 new_def for flow coding
+     */
+    public Node setDef(int idx, Node new_def ) {
+        unlock();
+        Node old_def = in(idx);
+        if( old_def == new_def ) return new_def; // 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 new_def;
+    }
+  
+    // 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.  If the def goes dead, it is recursively
+    // killed, which may include 'this' Node.
+    Node delDef(int idx) {
+        unlock();
+        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
+        old_def.moveDepsToWorklist();
+        Utils.del(_inputs, idx);
+        return this;
+    }
+
+    /**
+     * 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 addDef(Node new_def) {
+        unlock();
+        // 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; }
+
+    // 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 ) {
+        Utils.del(_outputs, Utils.find(_outputs, use));
+        return _outputs.isEmpty();
+    }
+
+    // Shortcut for "popping" n nodes.  A "pop" is basically a
+    // setDef(last,null) followed by lowering the nIns() count.
+    void popN(int n) {
+        unlock();
+        for( int i=0; i<n; i++ ) {
+            Node old_def = _inputs.removeLast();
+            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.
+     */
+    public void kill( ) {
+        unlock();
+        assert isUnused();      // Has no uses, so it is dead
+        _type=null;             // Flag as dead
+        while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes
+            Node old_def = _inputs.removeLast();
+            if( old_def != null ) {
+                IterPeeps.add(old_def);// Revisit neighbor because removed use
+                if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+                    old_def.kill();        // Kill old def
+            }
+        }
+        assert isDead();        // Really dead now
+    }
+
+    // Mostly used for asserts and printing.
+    public boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
+
+    // Shortcuts to stop DCE mid-parse
+    // Add bogus null use to keep node alive
+    public <N extends Node> N keep() { return addUse(null); }
+    // Remove bogus null.
+    public <N extends Node> N unkeep() { delUse(null); return (N)this; }
+
+
+    // Replace self with nnn in the graph, making 'this' go dead
+    public void subsume( Node nnn ) {
+        assert nnn!=this;
+        while( nOuts() > 0 ) {
+            Node n = _outputs.removeLast();
+            n.unlock();
+            int idx = Utils.find(n._inputs, this);
+            n._inputs.set(idx,nnn);
+            nnn.addUse(n);
+        }
+        kill();
+    }
+    
+    // ------------------------------------------------------------------------
+    // Graph-based optimizations
+    
+    /**
+     * 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.
+     * Always returns some not-null Node (often this).
+     */
+    public final Node peephole( ) {
+        if (_disablePeephole) {
+            _type = compute();
+            return this;        // Peephole optimizations turned off
+        }
+        Node n = peepholeOpt();
+        return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress
+    }
+
+    /**
+     * 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>
+     *
+     * Unlike peephole above, this explicitly returns null for no-change, or not-null
+     * for a better replacement (which can be this).
+     * </ul>
+     */
+    public final Node peepholeOpt( ) {
+        ITER_CNT++;
+        // Compute initial or improved Type
+        Type old = setType(compute());
+
+        // Replace constant computations from non-constants with a constant node
+        if (!(this instanceof ConstantNode) && _type.isHighOrConst() )
+            return new ConstantNode(_type).peepholeOpt();
+
+        // Global Value Numbering
+        if( _hash==0 ) {
+            Node n = GVN.get(this); // Will set _hash as a side effect
+            if( n==null )
+                GVN.put(this,this);  // Put in table now
+            else {
+                // Because of random worklist ordering, the two equal nodes
+                // might have different types.  Because of monotonicity, both
+                // types are valid.  To preserve monotonicity, the resulting
+                // shared Node has to have the best of both types.
+                n.setType(n._type.join(_type));
+                _hash = 0; // Clear, since it never went in the table
+                return deadCodeElim(n);// Return previous; does Common Subexpression Elimination
+            }
+        }
+
+        // Ask each node for a better replacement
+        Node n = idealize();
+        if( n != null )         // Something changed
+            return n;           // Report progress
+
+        if( old==_type ) ITER_NOP_CNT++;
+        return old==_type ? null : this; // Report progress
+    }
+    public static int ITER_CNT, ITER_NOP_CNT;
+
+    // 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.keep();      // Keep m alive
+            kill();        // Kill self because replacing with 'm'
+            m.unkeep();    // Okay to peephole m
+        }
+        return m;
+    }
+  
+    /**
+     * 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>
+     * {@link #compute()} needs to be stand-alone, and cannot recursively call compute
+     * on its inputs, because 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();
+
+    // Set the type.  Assert monotonic progress.
+    // If changing, add users to worklist.
+    public Type setType(Type type) {
+        Type old = _type;
+        assert old==null || type.isa(old); // Since _type not set, can just re-run this in assert in the debugger
+        if( old == type ) return old;
+        _type = type;       // Set _type late for easier assert debugging
+        IterPeeps.addAll(_outputs);
+        moveDepsToWorklist();
+        return old;
+    }
+
+    
+    /**
+     * 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();
+
+
+    // Some of the peephole rules get complex, and search further afield than
+    // just the nearest neighbor.  These peepholes can fail the pattern match
+    // on a node some distance away, and if that node ever changes we should
+    // retry the peephole.  Track a set of Nodes dependent on `this`, and
+    // revisit them if `this` changes.
+    ArrayList<Node> _deps;
+
+    /**
+     * Add a node to the list o dependencies. Only add it if its not
+     * an input or output of this node, that is, it is at least one step
+     * away. The node being added must benefit from this node being peepholed.
+     */
+    Node addDep( Node dep ) {
+        // Running peepholes during the big assert cannot have side effects
+        // like adding dependencies.
+        if( IterPeeps.midAssert() ) return this;
+        if( _deps==null ) _deps = new ArrayList<>();
+        if( Utils.find(_deps  ,dep) != -1 ) return this; // Already on list
+        if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors
+        if( Utils.find(_outputs,dep)!= -1 ) return this;
+        _deps.add(dep);
+        return this;
+    }
+
+    // Move the dependents onto a worklist, and clear for future dependents.
+    public void moveDepsToWorklist( ) {
+        if( _deps==null ) return;
+        IterPeeps.addAll(_deps);
+        _deps.clear();
+    }
+    
+    
+    // Global Value Numbering.  Hash over opcode and inputs; hits in this table
+    // are structurally equal.
+    public static final HashMap<Node,Node> GVN = new HashMap<>();
+
+    // Two nodes are equal if they have the same inputs and the same "opcode"
+    // which means the same Java class, plus same internal parts.
+    @Override public final boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( o.getClass() != getClass() ) return false;
+        Node n = (Node)o;
+        int len = _inputs.size();
+        if( len != n._inputs.size() ) return false;
+        for( int i=0; i<len; i++ )
+            if( in(i) != n.in(i) )
+                return false;
+        return eq(n);
+    }
+    // Subclasses add extra checks (such as ConstantNodes have same constant),
+    // and can assume "this!=n" and has the same Java class.
+    boolean eq( Node n ) { return true; }
+
+
+    // Cached hash.  If zero, then not computed AND this Node is NOT in the GVN
+    // table - and can have its edges hacked (which will change his hash
+    // anyway).  If Non-Zero then this Node is IN the GVN table, or is being
+    // probed to see if it can be inserted.  His edges are "locked", because
+    // hacking his edges will change his hash.
+    int _hash;
+
+    // If the _hash is set, then the Node is in the GVN table; remove it.
+    void unlock() {
+        if( _hash==0 ) return;
+        Node old = GVN.remove(this); // Pull from table
+        assert old==this;
+        _hash=0;                // Out of table now
+    }
+
+    
+    // Hash of opcode and inputs
+    @Override public final int hashCode() {
+        if( _hash != 0 ) return _hash;
+        int hash = hash();
+        for( Node n : _inputs )
+            if( n != null )
+                hash = hash ^ (hash<<17) ^ (hash>>13) ^ n._nid;
+        if( hash==0 ) hash = 0xDEADBEEF; // Bad hash, so use some junky thing
+        return (_hash=hash);
+    }
+    // Subclasses add extra hash info (such as ConstantNodes constant)
+    int hash() { return 0; }
+    
+    
+    // ------------------------------------------------------------------------
+    // Peephole utilities
+    
+    // Swap inputs without letting either input go dead during the swap.
+    Node swap12() {
+        unlock();               // Hash is order dependent
+        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.
+     * In an input is not a constant, we add dep as
+     * a dependency to it, because dep can make progress
+     * if the input becomes a constant later.
+     * It is sufficient for one of the non-const
+     * inputs to have the dependency so we don't bother
+     * checking the rest.
+     */
+    boolean allCons(Node dep) {
+        for( int i=1; i<nIns(); i++ )
+            if( !(in(i)._type.isConstant()) ) {
+                in(i).addDep(dep); // If in(i) becomes a constant later, will trigger some peephole
+                return false;
+            }
+        return true;
+    }
+
+    // Return the immediate dominator of this Node and compute dom tree depth.
+    Node idom() {
+        Node idom = in(0);
+        if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth
+        if( _idepth==0 ) _idepth = idom._idepth+1;
+        return idom;
+    }
+
+    // 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.
+     */
+    public static void reset() {
+        UNIQUE_ID = 1;
+        _disablePeephole=false;
+        GVN.clear();
+        ITER_CNT = ITER_NOP_CNT = 0;
+    }
+
+
+    // Utility to walk the entire graph applying a function; return the first
+    // not-null result.
+    private static final BitSet WVISIT = new BitSet();
+    final public <E> E walk( Function<Node,E> pred ) {
+        assert WVISIT.isEmpty();
+        E rez = _walk(pred);
+        WVISIT.clear();
+        return rez;
+    }
+    
+    private <E> E _walk( Function<Node,E> pred ) {
+        if( WVISIT.get(_nid) ) return null; // Been there, done that
+        WVISIT.set(_nid);
+        E x = pred.apply(this);
+        if( x != null ) return x;
+        for( Node def : _inputs  )  if( def != null && (x = def._walk(pred)) != null ) return x;
+        for( Node use : _outputs )  if( use != null && (x = use._walk(pred)) != null ) return x;
+        return null;
+    }
+    
+    /**
+     * Debugging utility to find a Node by index
+     */
+    public Node find(int nid) {
+        return walk( n -> n._nid==nid ? n : null );
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/NotNode.java
new file mode 100644
index 00000000..ab0f4d01
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -0,0 +1,30 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        in(1)._print0(sb.append("(!"), visited);
+        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 TypeInteger.TOP.meet(in(1)._type);
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java
new file mode 100644
index 00000000..2d03b655
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -0,0 +1,125 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        if( !(region() instanceof RegionNode r) || r.inProgress() )
+            sb.append("Z");
+        sb.append("Phi(");
+        for( Node in : _inputs ) {
+            if (in == null) sb.append("____");
+            else in._print0(sb, visited);
+            sb.append(",");
+        }
+        sb.setLength(sb.length()-1);
+        sb.append(")");
+        return sb;
+    }
+
+    Node region() { return in(0); }
+    @Override public boolean isMultiTail() { return true; }
+
+    @Override
+    public Type compute() {
+        if( !(region() instanceof RegionNode r) )
+            return region()._type==Type.XCONTROL ? Type.TOP : _type;
+        if( r.inProgress() ) return Type.BOTTOM;
+        Type t = Type.TOP;
+        for (int i = 1; i < nIns(); i++)
+            // If the region's control input is live, add this as a dependency
+            // to the control because we can be peeped should it become dead.
+            if( r.in(i).addDep(this)._type != Type.XCONTROL && in(i) != this )
+                t = t.meet(in(i)._type);
+        return t;
+    }
+
+    @Override
+    public Node idealize() {
+        if( !(region() instanceof RegionNode r ) )
+            return in(1);       // Input has collapse to e.g. starting control.
+        if( r.inProgress() || r.nIns()<=1 )
+            return null;        // Input is in-progress
+
+        // If we have only a single unique input, become it.
+        Node live = singleUniqueInput();
+        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;
+    }
+
+    /**
+     * If only single unique input, return it
+     */
+    private Node singleUniqueInput() {
+        if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL )
+            return null;    // Dead entry loops just ignore and let the loop collapse
+        Node live = null;
+        for( int i=1; i<nIns(); i++ ) {
+            // If the region's control input is live, add this as a dependency
+            // to the control because we can be peeped should it become dead.
+            if( region().in(i).addDep(this)._type != Type.XCONTROL && in(i) != this )
+                if( live == null || live == in(i) ) live = in(i);
+                else return null;
+        }
+        return live;
+    }
+
+    @Override
+    boolean allCons(Node dep) {
+        if( !(region() instanceof RegionNode r) ) return false;
+        // When the region completes (is no longer in progress) the Phi can
+        // become a "all constants" Phi, and the "dep" might make progress.
+        addDep(dep);
+        if( r.inProgress() ) return false;
+        return super.allCons(dep);
+    }
+
+    // True if last input is null
+    public final boolean inProgress() {
+        return in(nIns()-1) == null;
+    }
+
+    // Never equal if inProgress
+    @Override boolean eq( Node n ) {
+        return !inProgress();
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ProjNode.java
new file mode 100644
index 00000000..115bc1eb
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -0,0 +1,55 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
+
+import java.util.BitSet;
+
+public class ProjNode extends Node {
+
+    // Which slice of the incoming multipart 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, BitSet visited) { return sb.append(_label); }
+
+    @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
+    @Override public boolean isMultiTail() { return in(0).isMultiHead(); }
+
+    public MultiNode ctrl() { return (MultiNode)in(0); }
+
+    @Override
+    public Type compute() {
+        Type t = in(0)._type;
+        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;
+    }
+
+    @Override
+    boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; }
+
+    @Override
+    int hash() { return _idx; }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java
new file mode 100644
index 00000000..9468c395
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -0,0 +1,115 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.type.Type;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.BitSet;
+
+public class RegionNode extends Node {
+
+    public RegionNode(Node... nodes) { super(nodes); }
+    
+    @Override
+    public String label() { return "Region"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        return sb.append(label()).append(_nid);
+    }
+
+    @Override public boolean isCFG() { return true; }
+    @Override public boolean isMultiHead() { return true; }
+
+    @Override
+    public Type compute() {
+        if( inProgress() ) return Type.CONTROL;
+        Type t = Type.XCONTROL;
+        for (int i = 1; i < nIns(); i++)
+            t = t.meet(in(i)._type);
+        return t;
+    }
+
+    @Override
+    public Node idealize() {
+        if( inProgress() ) return null;
+        int path = findDeadInput();
+        if( path != 0 &&
+            // Do not delete the entry path of a loop (ok to remove the back
+            // edge and make the loop a single-entry Region which folds away
+            // the Loop).  Folding the entry path confused the loop structure,
+            // moving the backedge to the entry point.
+            !(this instanceof LoopNode loop && loop.entry()==in(path)) ) {
+            // Cannot use the obvious output iterator here, because a Phi
+            // deleting an input might recursively delete *itself*.  This
+            // shuffles the output array, and we might miss iterating an
+            // unrelated Phi. So on rare occasions we repeat the loop to get
+            // all the Phis.
+            int nouts = 0;
+            while( nouts != nOuts() ) {
+                nouts = nOuts();
+                for( int i=0; i<nOuts(); i++ )
+                    if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() )
+                        phi.delDef(path);
+            }
+            _idom = null;       // Clear idom cache
+            return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path);
+        }
+        // If down to a single input, become that input
+        if( nIns()==2 && !hasPhi() ) {
+            _idom = null;       // Clear idom cache
+            return in(1);       // Collapse if no Phis; 1-input Phis will collapse on their own
+        }
+        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
+    }
+
+    private boolean hasPhi() {
+        for( Node phi : _outputs )
+            if( phi instanceof PhiNode )
+                return true;
+        return false;
+    }
+    
+    // Immediate dominator of Region is a little more complicated.
+    private Node _idom;         // Immediate dominator cache
+    @Override Node idom() {
+        if( _idom != null ) {
+            if( _idom.isDead() ) _idom=null;
+            else return _idom; // Return cached copy
+        }
+        if( nIns()==2 ) return in(1); // 1-input is that one input
+        if( nIns()!=3 ) return null;  // Fails for anything other than 2-inputs
+        // Walk the LHS & RHS idom trees in parallel until they match, or either fails
+        Node lhs = in(1).idom();
+        Node rhs = in(2).idom();
+        while( lhs != rhs ) {
+          if( lhs==null || rhs==null ) return null;
+          var comp = lhs._idepth - rhs._idepth;
+          if( comp >= 0 ) lhs = lhs.idom();
+          if( comp <= 0 ) rhs = rhs.idom();
+        }
+        if( lhs==null ) return null;
+        _idepth = lhs._idepth+1;
+        if( !IterPeeps.midAssert() ) _idom=lhs;
+        return lhs;
+    }
+
+    // True if last input is null
+    public final boolean inProgress() {
+        return nIns()>1 && in(nIns()-1) == null;
+    }
+
+    // Never equal if inProgress
+    @Override boolean eq( Node n ) {
+        return !inProgress();
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
new file mode 100644
index 00000000..c10d82d8
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -0,0 +1,46 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.*;
+
+import java.util.BitSet;
+
+/**
+ * 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, BitSet visited) {
+        return expr()._print0(sb.append("return "), visited).append(";");
+    }
+
+    @Override public boolean isCFG() { return true; }
+  
+    @Override
+    public Type compute() {
+        return TypeTuple.make(ctrl()._type,expr()._type);
+    }
+
+    @Override
+    public Node idealize() {
+        if( ctrl()._type==Type.XCONTROL )
+            return ctrl();
+        return null;
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
new file mode 100644
index 00000000..6f72dea2
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -0,0 +1,226 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.type.Type;
+
+import java.util.*;
+
+/**
+ * The Scope node is purely a parser helper - it tracks names to nodes with a
+ * stack of scopes.
+ */
+public class ScopeNode extends Node {
+
+    /**
+     * The control is a name that binds to the currently active control
+     * node in the graph
+     */
+    public static final String CTRL = "$ctrl";
+    public static final String ARG0 = "arg";
+
+    /**
+     * Names for every input edge
+     */
+    public final Stack<HashMap<String, Integer>> _scopes;
+
+
+    // A new ScopeNode
+    public ScopeNode() {
+        _scopes = new Stack<>();
+        _type = Type.BOTTOM;
+    }
+    
+    
+    @Override public String label() { return "Scope"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        sb.append("Scope[ ");
+        String[] names = reverseNames();
+        for( int j=0; j<nIns(); j++ ) {
+            sb.append(names[j]).append(":");
+            Node n = in(j);
+            while( n instanceof ScopeNode loop ) {
+                sb.append("Lazy_");
+                n = loop.in(j);
+            }
+            n._print0(sb, visited).append(" ");
+        }
+        sb.setLength(sb.length()-1);
+        return sb.append("]");
+    }
+
+    /**
+     * Recover the names for all variable bindings.
+     * The result is an array of names that is aligned with the
+     * inputs to the Node.
+     *
+     * This is an expensive operation.
+     */
+    public String[] reverseNames() {
+        String[] names = new String[nIns()];
+        for( HashMap<String,Integer> syms : _scopes )
+            for( String name : syms.keySet() )
+                names[syms.get(name)] = name;
+        return names;
+    }
+    
+    @Override public Type compute() { return Type.BOTTOM; }
+
+    @Override public Node idealize() { return null; }
+
+    public void push() { _scopes.push(new HashMap<>());  }
+    public void pop() { popN(_scopes.pop().size());  }
+
+    /**
+     * Create a new name in the current scope
+     */
+    public Node define( String name, Node n ) {
+        HashMap<String,Integer> syms = _scopes.lastElement();
+        if( syms.put(name,nIns()) != null )
+            return null;        // Double define
+        return addDef(n);
+    }
+    /**
+     * Lookup a name in all scopes starting from most deeply nested.
+     *
+     * @param name Name to be looked up
+     * @see #update(String, Node, int)
+     */
+    public Node lookup( String name ) { return update(name,null,_scopes.size()-1);  }
+    /**
+     * If the name is present in any scope, then redefine else null
+     *
+     * @param name Name being redefined
+     * @param n    The node to bind to the name
+     */
+    public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); }
+    /**
+     * Both recursive lookup and update.
+     *
+     * A shared implementation allows us to create lazy phis both during
+     * lookups and updates; the lazy phi creation is part of chapter 8.
+     *
+     * @param name  Name whose binding is being updated or looked up
+     * @param n     If null, do a lookup, else update binding
+     * @param nestingLevel The starting nesting level
+     * @return node being looked up, or the one that was updated
+     */
+    private Node update( String name, Node n, int nestingLevel ) {
+        if( nestingLevel<0 ) return null;  // Missed in all scopes, not found
+        var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level
+        var idx = syms.get(name);
+        if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope
+        Node old = in(idx);
+        if( old instanceof ScopeNode loop ) {
+            // Lazy Phi!
+            old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region()
+                // Loop already has a real Phi, use it
+                ? loop.in(idx)
+                // Set real Phi in the loop head
+                // The phi takes its one input (no backedge yet) from a recursive
+                // lookup, which might have insert a Phi in every loop nest.
+                : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
+            setDef(idx,old);
+        }
+        return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer
+    }
+
+    public Node ctrl() { return in(0); }
+
+    /**
+     * The ctrl of a ScopeNode is always bound to the currently active
+     * control node in the graph, via a special name '$ctrl' that is not
+     * a valid identifier in the language grammar and hence cannot be
+     * referenced in Simple code.
+     *
+     * @param n The node to be bound to '$ctrl'
+     *
+     * @return Node that was bound
+     */
+    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>
+     * If the {@code loop} flag is set, the edges are filled in as the original
+     * Scope, as a indication of Lazy Phis at loop heads.  The goal here is to
+     * not make Phis at loop heads for variables which are never touched in the
+     * loop body.
+     * <p>
+     * The new Scope is a full-fledged Node with proper use<->def edges.
+     */
+    public ScopeNode dup() { return dup(false); }
+    public ScopeNode dup(boolean loop) {
+        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++ )
+            // For lazy phis on loops we use a sentinel
+            // that will trigger phi creation on update
+            dup.addDef(loop ? this : 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()).keep());
+        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
+                // If we are in lazy phi mode we need to a lookup
+                // by name as it will trigger a phi creation
+                setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole());
+        that.kill();            // Kill merged scope
+        return r.unkeep().peephole();
+    }
+    
+    // Merge the backedge scope into this loop head scope
+    // We set the second input to the phi from the back edge (i.e. loop body)
+    public void endLoop(ScopeNode back, ScopeNode exit ) {
+        Node ctrl = ctrl();
+        assert ctrl instanceof LoopNode loop && loop.inProgress();
+        ctrl.setDef(2,back.ctrl());
+        for( int i=1; i<nIns(); i++ ) {
+            if( back.in(i) != this ) {
+                PhiNode phi = (PhiNode)in(i);
+                assert phi.region()==ctrl && phi.in(2)==null;
+                phi.setDef(2,back.in(i));
+            }
+            if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also
+                exit.setDef(i,in(i));
+        }
+        back.kill();            // Loop backedge is dead
+        // Now one-time do a useless-phi removal
+        for( int i=1; i<nIns(); i++ ) {
+            if( in(i) instanceof PhiNode phi ) {
+                // Do an eager useless-phi removal
+                Node in = phi.peephole();
+                IterPeeps.addAll(phi._outputs);
+                phi.moveDepsToWorklist();
+                if( in != phi ) {
+                    phi.subsume(in);
+                    setDef(i,in); // Set the update back into Scope
+                }
+            }
+        }
+
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java
new file mode 100644
index 00000000..5693f27b
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -0,0 +1,46 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
+
+import java.util.BitSet;
+
+/**
+ * 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 = TypeTuple.make(args);
+        _type = _args;
+    }
+
+    @Override
+    public String label() { return "Start"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+      return sb.append(label());
+    }
+
+    @Override public boolean isCFG() { return true; }
+    @Override public boolean isMultiHead() { return true; }
+
+    @Override
+    public TypeTuple compute() { return _args; }
+
+    @Override
+    public Node idealize() { return null; }
+
+    // No immediate dominator, and idepth==0
+    @Override
+    Node idom() { return null; }
+
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/StopNode.java
new file mode 100644
index 00000000..dccc90a9
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -0,0 +1,60 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.IterPeeps;
+
+import java.util.BitSet;
+
+public class StopNode extends Node {
+
+    public final String _src;
+    
+    public StopNode(String src) {
+        super();
+        _src = src;
+    }
+
+    @Override
+    public String label() {
+        return "Stop";
+    }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        if( ret()!=null ) return ret()._print0(sb, visited);
+        sb.append("Stop[ ");
+        for( Node ret : _inputs )
+            ret._print0(sb, visited).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 addDef(node);
+    }
+
+    public StopNode iterate(            ) { return IterPeeps.iterate(this,false); }
+    public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ); }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/SubNode.java
new file mode 100644
index 00000000..f81ae6d0
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -0,0 +1,42 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+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, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("-"), visited);
+        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 in(1)._type.meet(in(2)._type);
+    }
+
+    @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/chapter09/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter09/src/main/java/com/seaofnodes/simple/type/Type.java
new file mode 100644
index 00000000..ee6fb741
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -0,0 +1,141 @@
+package com.seaofnodes.simple.type;
+
+import com.seaofnodes.simple.Utils;
+
+import java.util.HashMap;
+
+/**
+ * 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 {
+    static final HashMap<Type,Type> INTERN = new HashMap<>();
+
+    // ----------------------------------------------------------
+    // 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[]{"Bot","Top","Ctrl","~Ctrl"};
+    protected Type(byte type) { _type = type; }
+
+    public static final Type BOTTOM   = new Type( TBOT   ).intern(); // ALL
+    public static final Type TOP      = new Type( TTOP   ).intern(); // ANY
+    public static final Type CONTROL  = new Type( TCTRL  ).intern(); // Ctrl
+    public static final Type XCONTROL = new Type( TXCTRL ).intern(); // ~Ctrl
+
+    // Is high or on the lattice centerline.
+    public boolean isHighOrConst() { return _type==TTOP || _type==TXCTRL; }
+
+    // Strict constant values, things on the lattice centerline.
+    // Excludes both high and low values
+    public boolean isConstant() { return false; }
+
+    public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
+
+    // ----------------------------------------------------------
+
+    // Factory method which interns "this"
+    protected <T extends Type> T intern() {
+        T nnn = (T)INTERN.get(this);
+        if( nnn==null ) 
+            INTERN.put(nnn=(T)this,this);
+        return nnn;
+    }
+    
+    private int _hash;          // Hash cache; not-zero when set.
+    @Override
+    public final int hashCode() {
+        if( _hash!=0 ) return _hash;
+        _hash = hash();
+        if( _hash==0 ) _hash = 0xDEADBEEF; // Bad hash from subclass; use some junk thing
+        return _hash;
+    }
+    // Override in subclasses
+    int hash() { return _type; }
+    
+    @Override
+    public final boolean equals( Object o ) {
+        if( o==this ) return true;
+        if( !(o instanceof Type t)) return false;
+        if( _type != t._type ) return false;
+        return eq(t);
+    }
+    // Overridden in subclasses; subclass can assume "this!=t" and java classes are same
+    boolean eq(Type t) { return true; }
+    
+    
+    // ----------------------------------------------------------
+    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 xmeet(t);        // 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;
+    }
+
+    // True if this "isa" t; e.g. 17 isa TypeInteger.BOT
+    public boolean isa( Type t ) { return meet(t)==t; }
+    
+    // ----------------------------------------------------------
+    // Our lattice is defined with a MEET and a DUAL.
+    // JOIN is dual of meet of both duals.
+    public final Type join(Type t) {
+        if( this==t ) return this;
+        return dual().meet(t.dual()).dual();
+    }
+
+    public Type dual() {
+        return switch( _type ) {
+        case TBOT -> TOP;
+        case TTOP -> BOTTOM;
+        case TCTRL -> XCONTROL;
+        case TXCTRL -> CONTROL;
+        default -> throw Utils.TODO(); // Should not reach here
+        };
+    }
+    
+    // ----------------------------------------------------------
+    @Override
+    public final String toString() {
+        return _print(new StringBuilder()).toString();
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter09/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
new file mode 100644
index 00000000..df41a526
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -0,0 +1,74 @@
+package com.seaofnodes.simple.type;
+
+/**
+ * Integer Type
+ */
+public class TypeInteger extends Type {
+
+    public final static TypeInteger TOP = make(false, 0);
+    public final static TypeInteger BOT = make(false, 1);
+    public final static TypeInteger ZERO= make(true , 0);
+
+    public final boolean _is_con;
+
+    /**
+     * The constant value or
+     * if not constant then 1=bottom, 0=top.
+     */
+    public final long _con;
+
+    private TypeInteger(boolean is_con, long con) {
+        super(TINT);
+        _is_con = is_con;
+        _con = con;
+    }
+    public static TypeInteger make(boolean is_con, long con) {
+        return new TypeInteger(is_con,con).intern();
+    }
+
+    public static TypeInteger constant(long con) { return make(true, con); }
+
+    @Override 
+    public StringBuilder _print(StringBuilder sb) {
+        if( this==TOP ) return sb.append("IntTop");
+        if( this==BOT ) return sb.append("IntBot");
+        return sb.append(_con);
+    }
+
+    @Override
+    public boolean isHighOrConst() { return _is_con || _con==0; }
+
+    @Override
+    public boolean isConstant() { return _is_con; }
+
+    public long value() { return _con; }
+
+    @Override
+    public Type xmeet(Type other) {
+        // Invariant from caller: 'this' != 'other' and same class (TypeInteger)
+        TypeInteger i = (TypeInteger)other; // Contract
+        // BOT wins
+        if ( this==BOT ) return this;
+        if ( i   ==BOT ) return i   ;
+        // TOP loses
+        if ( i   ==TOP ) return this;
+        if ( this==TOP ) return i   ;
+        // Since both are constants, and are never equals (contract) unequals
+        // constants fall to bottom
+        return BOT;
+    }
+
+    @Override
+    public Type dual() {
+        if( isConstant() ) return this; // Constants are a self-dual
+        return _con==0 ? BOT : TOP;
+    }
+    
+    @Override
+    int hash() { return (int)(_con ^ (_is_con ? 0 : 0x4000)); }
+    @Override
+    public boolean eq( Type t ) {
+        TypeInteger i = (TypeInteger)t; // Contract
+        return _con==i._con && _is_con==i._is_con;
+    }
+}
diff --git a/chapter09/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter09/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
new file mode 100644
index 00000000..863c5b7d
--- /dev/null
+++ b/chapter09/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -0,0 +1,60 @@
+package com.seaofnodes.simple.type;
+
+public class TypeTuple extends Type {
+  
+    public final Type[] _types;
+
+    private TypeTuple(Type[] types) { super(TTUPLE); _types = types; }
+    public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); }
+
+    @Override
+    public Type xmeet(Type other) {
+        TypeTuple tt = (TypeTuple)other;     // contract from xmeet
+        assert _types.length == tt._types.length;
+        Type[] ts = new Type[_types.length];
+        for( int i=0; i<_types.length; i++ )
+            ts[i] = _types[i].meet(tt._types[i]);
+        return make(ts);
+    }
+
+    @Override public Type dual() {
+        Type[] ts = new Type[_types.length];
+        for( int i=0; i<_types.length; i++ )
+            ts[i] = _types[i].dual();
+        return make(ts);
+    }
+    
+    @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    = make(new Type[]{Type. CONTROL,Type. CONTROL});
+    public static final TypeTuple IF_NEITHER = make(new Type[]{Type.XCONTROL,Type.XCONTROL});
+    public static final TypeTuple IF_TRUE    = make(new Type[]{Type. CONTROL,Type.XCONTROL});
+    public static final TypeTuple IF_FALSE   = make(new Type[]{Type.XCONTROL,Type. CONTROL});
+
+    @Override
+    int hash() {
+        int sum = 0;
+        for( Type type : _types ) sum ^= type.hashCode();
+        return sum;
+    }
+    
+    @Override
+    boolean eq( Type t ) {
+        TypeTuple tt = (TypeTuple)t; // Contract
+        if( _types.length != tt._types.length ) return false;
+        for( int i=0; i<_types.length; i++ )
+            if( _types[i]!=tt._types[i] )
+                return false;
+        return true;
+    }
+
+
+}
author	Dibyendu Majumdar <dibyendumajumdar@users.noreply.github.com>	2024-03-03 17:55:47 +0000
committer	GitHub <noreply@github.com>	2024-03-03 17:55:47 +0000
commit	c3842e2a01522f52ae4690de3e9c90efa33f0f27 (patch)
tree	bcedc8d459d74a57acc7ea3b1b968aa60db4a5e6 /chapter09/src/main/java
parent	29bc63423aeba9327b2e60959f8dbb2c8e718a29 (diff)
download	Simple-c3842e2a01522f52ae4690de3e9c90efa33f0f27.tar.gz Simple-c3842e2a01522f52ae4690de3e9c90efa33f0f27.zip