Backport some of the code refactoring to previous chapters (#50)

* #44 Revise docs and comments

* #44 Add starting scope to xScopes

* #44 back some of the code refactoring port to previous chapters

* #44 add_def should not be public

* #44 add_def should not be public. Rename method names so that they are camelcase

21 files changed, 356 insertions, 224 deletions

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 01b5aeeb..1c3e314c 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -40,14 +40,14 @@ public class GraphVisualizer {
         nodes(sb, all);
         
         // Now the scopes, in a cluster no edges
-        for (ScopeNode sn: parser._allScopes)
+        for (ScopeNode sn: parser._xScopes)
             scopes(sb, sn);
 
         // Walk the Node edges
         nodeEdges(sb, all);
 
         // Walk the Scope edges
-        for (ScopeNode sn: parser._allScopes)
+        for (ScopeNode sn: parser._xScopes)
             scopeEdges(sb, sn);
         
         sb.append("}\n");
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
index 0461dc69..3de0e9b8 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -14,11 +14,6 @@ import java.util.*;
  */
 public class Parser {
 
-    /**
-     * The control is a name that binds to the currently active control
-     * node in the graph
-     */
-    public static final String CTRL = "$ctrl";
   
     /**
      * A Global Static, unique to each compilation.  This is a public, so we
@@ -44,7 +39,7 @@ public class Parser {
      * <p>
      * We keep a list of all ScopeNodes so that we can show them in graphs.
      * @see #parseIf()
-     * @see #_allScopes
+     * @see #_xScopes
      */
     public ScopeNode _scope;
 
@@ -65,14 +60,13 @@ public class Parser {
      * We clone ScopeNodes when control flows branch; it is useful to have
      * a list of all active ScopeNodes for purposes of visualization of the SoN graph
      */
-    public final Stack<ScopeNode> _allScopes = new Stack<>();
+    public final Stack<ScopeNode> _xScopes = new Stack<>();
 
     public Parser(String source, TypeInteger arg) {
-        _lexer = new Lexer(source);
         Node.reset();
+        _lexer = new Lexer(source);
         _scope = new ScopeNode();
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
-        START.peephole();
         STOP = new StopNode();
     }
 
@@ -80,30 +74,35 @@ public class Parser {
         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) {
-        _allScopes.push(_scope);
+	    _xScopes.push(_scope);
+        // Enter a new scope for the initial control and arguments
         _scope.push();
-        try {
-            _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole());
-            _scope.define("arg", new ProjNode(START, 1, "arg").peephole());
-            parseBlock();
-            if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
-            return STOP;
-        }
-        finally {
-            _scope.pop();
-            _allScopes.pop();
-            if( show ) showGraph();
-        }
+        _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
      *
@@ -116,14 +115,11 @@ public class Parser {
     private Node parseBlock() {
         // Enter a new scope
         _scope.push();
-        Node n = null;
-        while (!peek('}') && !_lexer.isEOF()) {
-            Node n0 = parseStatement();
-            if (n0 != null) n = n0; // Allow null returns from eg showGraph
-        };
+        while (!peek('}') && !_lexer.isEOF())
+            parseStatement();
         // Exit scope
         _scope.pop();
-        return n;
+        return null;
     }
 
     /**
@@ -164,7 +160,7 @@ public class Parser {
         // But first clone the scope and set it as current
         int ndefs = _scope.nIns();
         ScopeNode fScope = _scope.dup(); // Duplicate current scope
-        _allScopes.push(fScope); // For graph visualization we need all scopes
+        _xScopes.push(fScope); // For graph visualization we need all scopes
 
         // Parse the true side
         ctrl(ifT);              // set ctrl token to ifTrue projection
@@ -174,14 +170,17 @@ public class Parser {
         // Parse the false side
         _scope = fScope;        // Restore scope, then parse else block if any
         ctrl(ifF);              // Ctrl token is now set to ifFalse projection
-        if (matchx("else")) parseStatement();
+        if (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;
-        _allScopes.pop();       // Discard pushed from graph display
+        _xScopes.pop();       // Discard pushed from graph display
 
         return ctrl(tScope.mergeScopes(fScope));
     }
@@ -267,12 +266,12 @@ public class Parser {
      */
     private Node parseComparison() {
         var lhs = parseAddition();
-        if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole();
-        if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole();
-        if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole();
-        if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole();
-        if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole();
-        if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole();
+        if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole();
+        if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole();
+        if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole();
+        if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole();
+        if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole();
+        if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole();
         return lhs;
     }
 
@@ -520,7 +519,4 @@ public class Parser {
             return new String(_input, start, 1);
         }
     }
-
-    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
-    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Utils.java b/chapter05/src/main/java/com/seaofnodes/simple/Utils.java
new file mode 100644
index 00000000..4d663c25
--- /dev/null
+++ b/chapter05/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/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
index f6c49abf..87304f28 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -72,7 +72,7 @@ public class AddNode extends Node {
         if( lhs.in(2)._type.isConstant() && t2.isConstant() )
             return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
 
-        if( lhs.in(2) instanceof PhiNode phi && phi.all_cons() &&
+        if( lhs.in(2) instanceof PhiNode phi && phi.allCons() &&
             // Do we have ((x + (phi cons)) + con) ?
             // Do we have ((x + (phi cons)) + (phi cons)) ?
             // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
@@ -80,7 +80,7 @@ public class AddNode extends Node {
             // Note that this is the exact reverse of Phi pulling a common op
             // down to reduce total op-count.  We don't get in an endless push-
             // up push-down peephole cycle because the constants all fold first.
-            (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.all_cons()) ) ) {
+            (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) {
             Node[] ns = new Node[phi.nIns()];
             ns[0] = phi.in(0);
             // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
@@ -109,8 +109,8 @@ public class AddNode extends Node {
         if( lo._type.isConstant() ) return false;
         if( hi._type.isConstant() ) return true ;
             
-        if( lo instanceof PhiNode && lo.all_cons() ) return false;
-        if( hi instanceof PhiNode && hi.all_cons() ) return true ;
+        if( lo instanceof PhiNode && lo.allCons() ) return false;
+        if( hi instanceof PhiNode && hi.allCons() ) return true ;
 
         if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true;
         if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false;
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 0ba5e7b0..61259d2c 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -46,10 +46,7 @@ abstract public class BoolNode extends Node {
         return null;
     }
 
-    public static class EQNode extends BoolNode { public EQNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQNode(lhs,rhs); } }
-    public static class NENode extends BoolNode { public NENode(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 NENode(lhs,rhs); } }
-    public static class LTNode extends BoolNode { public LTNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } Node copy(Node lhs, Node rhs) { return new LTNode(lhs,rhs); } }
-    public static class LENode extends BoolNode { public LENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LENode(lhs,rhs); } }
-    public static class GTNode extends BoolNode { public GTNode(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 GTNode(lhs,rhs); } }
-    public static class GENode extends BoolNode { public GENode(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 GENode(lhs,rhs); } }
+    public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } }
+    public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } }
+    public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } }
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index ec85bf1f..ba6f55d7 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -23,7 +23,7 @@ public class ConstantNode extends Node {
     }
     
     @Override
-    public String label() { return "#"+_con; }
+    public String label() { return ""+_con; }
   
     @Override
     public String uniqueName() { return "Con_" + _nid; }
@@ -38,5 +38,4 @@ public class ConstantNode extends Node {
 
     @Override
     public Node idealize() { return null; }
-    
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java
index b46d37db..6124b893 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -20,7 +20,10 @@ public class IfNode extends MultiNode {
     }
 
     @Override public boolean isCFG() { return true; }
-    
+
+    public Node ctrl() { return in(0); }
+    public Node pred() { return in(1); }
+
     @Override
     public Type compute() {
         return TypeTuple.IF;
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index fe3fddf8..81c90f68 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -1,7 +1,5 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.type.Type;
-
 public abstract class MultiNode extends Node {
     
     public MultiNode(Node... inputs) { super(inputs); }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
index 65151acb..3b841d8c 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,6 +1,6 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
@@ -71,7 +71,15 @@ public abstract class Node {
 
     // 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() {
         // TODO: This needs a lot of work
@@ -105,71 +113,14 @@ public abstract class Node {
 
     public int nIns() { return _inputs.size(); }
 
+    public Node out(int i) { return _outputs.get(i); }
+
     public int nOuts() { return _outputs.size(); }
 
     public boolean isUnused() { return nOuts() == 0; }
 
     public boolean isCFG() { return false; }
   
-    /**
-     * We allow disabling peephole opt so that we can observe the
-     * full graph, vs the optimized graph.
-     */
-    public static boolean _disablePeephole = false;
-
-    /**
-     * Try to peephole at this node and return a better replacement Node if
-     * possible.  We compute a {@link Type} and then check and replace:
-     * <ul>
-     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
-     * <li>in a future chapter we will look for a
-     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
-     * to eliminate.</li>
-     * <li>we ask the Node for a better replacement.  The "better replacement"
-     * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes
-     * {@code (x+(1+2))}.  By canonicalizing expressions we fold common addressing
-     * math constants, remove algebraic identities and generally simplify the
-     * code. </li>
-     * </ul>
-     */
-    public final Node peephole( ) {
-        // Compute initial or improved Type
-        Type type = _type = compute();
-        
-        if (_disablePeephole)
-            return this;        // Peephole optimizations turned off
-
-        // Replace constant computations from non-constants with a constant node
-        if (!(this instanceof ConstantNode) && type.isConstant())
-            return deadCodeElim(new ConstantNode(type).peephole());
-
-        // Future chapter: Global Value Numbering goes here
-        
-        // Ask each node for a better replacement
-        Node n = idealize();
-        if( n != null )         // Something changed
-            // Recursively optimize
-            return deadCodeElim(n.peephole());
-        
-        return this;            // No progress
-    }
-
-    // m is the new Node, self is the old.
-    // Return 'm', which may have zero uses but is alive nonetheless.
-    // If self has zero uses (and is not 'm'), {@link #kill} self.
-    private Node deadCodeElim(Node m) {
-        // If self is going dead and not being returned here (Nodes returned
-        // from peephole commonly have no uses (yet)), then kill self.
-        if( m != this && isUnused() ) {
-            // Killing self - and since self recursively kills self's inputs we
-            // might end up killing 'm', which we are returning as a live Node.
-            // So we add a bogus extra null output edge to stop kill().
-            m.addUse(null); // Add bogus null use to keep m alive
-            kill();            // Kill self because replacing with 'm'
-            m.delUse(null);    // Remove bogus null.
-        }
-        return m;
-    }
 
     
     /**
@@ -186,9 +137,9 @@ public abstract class Node {
      *     
      * @param idx which def to set
      * @param new_def the new definition
-     * @return this for flow coding
+     * @return new_def for flow coding
      */
-    Node set_def(int idx, Node new_def ) {
+    Node setDef(int idx, Node new_def ) {
         Node old_def = in(idx);
         if( old_def == new_def ) return this; // No change
         // If new def is not null, add the corresponding def->use edge
@@ -202,7 +153,7 @@ public abstract class Node {
         // Set the new_def over the old (killed) edge
         _inputs.set(idx,new_def);
         // Return self for easy flow-coding
-        return this;
+        return new_def;
     }
 
     /**
@@ -212,7 +163,7 @@ public abstract class Node {
      * @param new_def the new definition, appended to the end of existing definitions
      * @return new_def for flow coding
      */
-    Node add_def(Node new_def) {
+    Node addDef(Node new_def) {
         // Add use->def edge
         _inputs.add(new_def);
         // If new def is not null, add the corresponding def->use edge
@@ -222,27 +173,21 @@ public abstract class Node {
     }
 
     // Breaks the edge invariants, used temporarily
-    private void addUse(Node n) { _outputs.add(n); }
+    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 ) {
-        ArrayList<Node> outs = _outputs;
-        int lidx = outs.size()-1; // Last index            
-        // This 1-line hack compresses an element out of an ArrayList
-        // without having to copy the contents.  The last element is
-        // stuffed over the deleted element, and then the size is reduced.            
-        outs.set(outs.indexOf(use),outs.get(lidx));
-        outs.remove(lidx);  // Reduce ArrayList size without copying anything
-        return lidx==0;
+        Utils.del(_outputs, Utils.find(_outputs, use));
+        return _outputs.size() == 0;
     }
 
     // Shortcut for "popping" n nodes.  A "pop" is basically a
     // set_def(last,null) followed by lowering the nIns() count.
-    void pop_n(int n) {
+    void popN(int n) {
         for( int i=0; i<n; i++ ) {
-            Node old_def = _inputs.remove(_inputs.size()-1);
+            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
@@ -252,17 +197,85 @@ public abstract class Node {
     /**
      * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
      * to null.  This may recursively kill more Nodes and is basically dead
-     * code elimination.  This function is co-recursive with {@link #pop_n}.
+     * code elimination.  This function is co-recursive with {@link #popN}.
      */
     public void kill( ) {
         assert isUnused();      // Has no uses, so it is dead
-        pop_n(nIns());          // Set all inputs to null, recursively killing unused Nodes
+        popN(nIns());          // Set all inputs to null, recursively killing unused Nodes
         _type=null;             // Flag as dead
         assert isDead();        // Really dead now
     }
 
     // Mostly used for asserts and printing.
     boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
+
+    // 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; }
+    // ------------------------------------------------------------------------
+    // 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 if
+     * possible.  We compute a {@link Type} and then check and replace:
+     * <ul>
+     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
+     * <li>in a future chapter we will look for a
+     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
+     * to eliminate.</li>
+     * <li>we ask the Node for a better replacement.  The "better replacement"
+     * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes
+     * {@code (x+(1+2))}.  By canonicalizing expressions we fold common addressing
+     * math constants, remove algebraic identities and generally simplify the
+     * code. </li>
+     * </ul>
+     */
+    public final Node peephole( ) {
+        // Compute initial or improved Type
+        Type type = _type = compute();
+        
+        if (_disablePeephole)
+            return this;        // Peephole optimizations turned off
+
+        // Replace constant computations from non-constants with a constant node
+        if (!(this instanceof ConstantNode) && type.isConstant())
+            return deadCodeElim(new ConstantNode(type).peephole());
+
+        // Future chapter: Global Value Numbering goes here
+        
+        // Ask each node for a better replacement
+        Node n = idealize();
+        if( n != null )         // Something changed
+            // Recursively optimize
+            return deadCodeElim(n.peephole());
+        
+        return this;            // No progress
+    }
+
+    // m is the new Node, self is the old.
+    // Return 'm', which may have zero uses but is alive nonetheless.
+    // If self has zero uses (and is not 'm'), {@link #kill} self.
+    private Node deadCodeElim(Node m) {
+        // If self is going dead and not being returned here (Nodes returned
+        // from peephole commonly have no uses (yet)), then kill self.
+        if( m != this && isUnused() ) {
+            // Killing self - and since self recursively kills self's inputs we
+            // might end up killing 'm', which we are returning as a live Node.
+            // So we add a bogus extra null output edge to stop kill().
+            m.keep();      // Keep m alive
+            kill();        // Kill self because replacing with 'm'
+            m.unkeep();    // Okay to peephole m
+        }
+        return m;
+    }
   
     /**
      * This function needs to be
@@ -330,7 +343,7 @@ public abstract class Node {
     public abstract Node idealize();
 
 
-    // -----------------------
+    // ------------------------------------------------------------------------
     // Peephole utilities
     
     // Swap inputs without letting either input go dead during the swap.
@@ -343,7 +356,7 @@ public abstract class Node {
     
     // does this node contain all constants?
     // Ignores in(0), as is usually control.
-    boolean all_cons() {
+    boolean allCons() {
         for( int i=1; i<nIns(); i++ )
             if( !(in(i)._type.isConstant()) )
                 return false;
@@ -353,11 +366,31 @@ public abstract class Node {
     // Make a shallow copy (same class) of this Node, with given inputs and
     // empty outputs and a new Node ID.  The original inputs are ignored.
     // Does not need to be implemented in isCFG() nodes.
-    Node copy(Node lhs, Node rhs) { throw Parser.TODO("Binary ops need to implement copy"); }
+    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; }
+    public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; }
+
+    /**
+     * Debugging utility to find a Node by index
+     */
+    public Node find(int nid) { return _find(new BitSet(),nid); }
+    private Node _find(BitSet visit, int nid) {
+        if( _nid==nid ) return this;
+        if( visit.get(_nid) ) return null;
+        visit.set(_nid);
+        for( Node def : _inputs )
+            if( def!=null ) {
+                Node rez = def._find(visit,nid);
+                if( rez != null ) return rez;
+            }
+        for( Node use : _outputs ) {
+            Node rez = use._find(visit,nid);
+            if( rez != null ) return rez;
+        }
+        return null;
+    }
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java
new file mode 100644
index 00000000..5dd6a86e
--- /dev/null
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class NotNode extends Node {
+    public NotNode(Node in) { super(null, in); }
+
+    @Override public String label() { return "Not"; }
+  
+    @Override public String glabel() { return "!"; }
+  
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("(!"));
+        return sb.append(")");
+    }
+  
+    @Override
+    public Type compute() {
+        if( in(1)._type instanceof TypeInteger i0 )
+            return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() { return null; }
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 87c84453..716d03d9 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -22,6 +22,8 @@ public class PhiNode extends Node {
         return sb;
     }
 
+    Node region() { return in(0); }
+
     @Override
     public Type compute() {
         return Type.BOTTOM;
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 86e3b144..b78a3e28 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -30,10 +30,6 @@ public class ProjNode extends Node {
     @Override
     public Type compute() {
         Type t = ctrl()._type;
-        return getType(t);
-    }
-
-    private Type getType(Type t) {
         return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
     }
 
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 354a8f8b..5d520d65 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -10,7 +10,7 @@ public class RegionNode extends Node {
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
-        return sb.append("Region").append(_nid);
+        return sb.append(label()).append(_nid);
     }
 
     @Override public boolean isCFG() { return true; }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 73594d2a..d0d3eb06 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -32,7 +32,7 @@ public class ReturnNode extends Node {
   
     @Override
     public Type compute() {
-      return new TypeTuple(Type.CONTROL,expr()._type);
+        return new TypeTuple(ctrl()._type,expr()._type);
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 93ef54f6..543d0f83 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -1,25 +1,34 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
 
 /**
- * The Scope node is a purely parser helper - it tracks names to nodes with a
+ * The Scope node is purely a parser helper - it tracks names to nodes with a
  * stack of scopes.
  */
 public class ScopeNode extends Node {
 
     /**
-     * Stack of lexical scopes, each scope is a symbol table
-     * that binds variable names to Nodes.
-     * The top of this stack represents current scope.
+     * The control is a name that binds to the currently active control
+     * node in the graph
      */
-    public final Stack<HashMap<String, Integer>> _scopes = new Stack<>();
+    public static final String CTRL = "$ctrl";
+    public static final String ARG0 = "arg";
 
-    // Reverse lookup for nicer graph printing
-    private final ArrayList<String> _rlabels = new ArrayList<>();
+    /**
+     * 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"; }
 
@@ -41,60 +50,86 @@ public class ScopeNode extends Node {
         }
         return sb;
     }
-  
-    @Override
-    public Type compute() { return Type.BOTTOM; }
-
-    @Override public Node idealize() { return null; }
 
-    // Add an empty lexical scope
-    public HashMap<String, Integer> push() {
-        return _scopes.push(new HashMap<>());
+    /**
+     * 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; }
 
-    // Remove the current lexical scope, killing all unused nodes.
-    public void pop() {
-        HashMap<String,Integer> scope = _scopes.pop();
-        pop_n(scope.size());
-    }
+    @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
+    /**
+     * Create a new name in the current scope
+     */
     public Node define( String name, Node n ) {
-        HashMap<String,Integer> scope = _scopes.lastElement();
-        if( scope.put(name,nIns()) != null )
+        HashMap<String,Integer> syms = _scopes.lastElement();
+        if( syms.put(name,nIns()) != null )
             return null;        // Double define
-        _rlabels.add(name);
-        return add_def(n);
+        return addDef(n);
     }
-
-    // Lookup a name in all scopes
-    public Node lookup(String name) {
-        for (int i = _scopes.size() - 1; i >= 0; i--) {
-            var idx = _scopes.get(i).get(name);
-            if (idx != null) return in(idx);
-        }
-        return null;
+    /**
+     * 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 n is null we are looking up rather than updating, hence return existing value
+        return n==null ? old : setDef(idx,n);
     }
 
-    public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); }
-    
-    public Node ctrl(Node n) {
-        assert lookup(Parser.CTRL)==in(0);
-        set_def(0,n);
-        return n;
-    }
+    public Node ctrl() { return in(0); }
 
-  
-    // If the name is present in any scope, then redefine
-    public Node update(String name, Node n) {
-        for (int i = _scopes.size() - 1; i >= 0; i--) {
-            HashMap<String, Integer> scope = _scopes.get(i);
-            Integer idx = scope.get(name);
-            if (idx != null)           // Found prior def
-                return set_def(idx,n); // Update def in scope
-        }
-        return null;
-    }
+    /**
+     * 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
@@ -105,19 +140,19 @@ public class ScopeNode extends Node {
      * The new Scope is a full-fledged Node with proper use<->def edges.
      */
     public ScopeNode dup() {
+        ScopeNode dup = new ScopeNode();
         // Our goals are:
         // 1) duplicate the name bindings of the ScopeNode across all stack levels
         // 2) Make the new ScopeNode a user of all the nodes bound
         // 3) Ensure that the order of defs is the same to allow easy merging
-        ScopeNode dup = new ScopeNode();
-        for( HashMap<String, Integer> tab : _scopes )
-            dup._scopes.push(new HashMap<>(tab));
-        for( int i=0; i<nIns(); i++ )
-            dup.add_def(in(i));
-        dup._rlabels.addAll(_rlabels);
+        for( HashMap<String,Integer> syms : _scopes )
+            dup._scopes.push(new HashMap<>(syms));
+        dup.addDef(ctrl());      // Control input is just copied
+        for( int i=1; i<nIns(); i++ )
+            dup.addDef(in(i));
         return dup;
     }
-
+    
     /**
      * Merges the names whose node bindings differ, by creating Phi node for such names
      * The names could occur at all stack levels, but a given name can only differ in the
@@ -127,10 +162,12 @@ public class ScopeNode extends Node {
      * @return A new node representing the merge point
      */
     public Node mergeScopes(ScopeNode that) {
-        RegionNode r = (RegionNode)ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole());
-        for( int i=1; i<nIns(); i++ )
+        RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole());
+        String[] ns = reverseNames();
+        // Note that we skip i==0, which is bound to '$ctrl'
+        for (int i = 1; i < nIns(); i++)
             if( in(i) != that.in(i) ) // No need for redundant Phis
-                set_def(i,new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole());
+                setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole());
         that.kill();            // Kill merged scope
         return r;
     }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 85c6cd34..e94c24e0 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -17,6 +17,7 @@ public class StartNode extends MultiNode {
     public StartNode(Type[] args) {
         super();
         _args = new TypeTuple(args);
+        _type = _args;
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 9898de88..9ec39373 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -40,7 +40,7 @@ public class StopNode extends Node {
     }
 
     public Node addReturn(Node node) {
-        return add_def(node);
+        return addDef(node);
     }
 
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
index d8cb690b..4cee0d3c 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -32,7 +32,7 @@ public class Type {
     public final byte _type;
 
     public boolean is_simple() { return _type < TSIMPLE; }
-    private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL"};
+    private static final String[] STRS = new String[]{"Bot","Top","Ctrl"};
     protected Type(byte type) { _type = type; }
 
     public static final Type BOTTOM   = new Type( TBOT   ); // ALL
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index 5c8c7049..3037e45f 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -28,11 +28,6 @@ public class TypeInteger extends Type {
     public boolean isTop() { return !_is_con && _con==0; }
     public boolean isBot() { return !_is_con && _con==1; }
 
-    @Override
-    public String toString() {
-        return _print(new StringBuilder()).toString();
-    }
-
     @Override 
     public StringBuilder _print(StringBuilder sb) {
         if (isTop()) return sb.append("IntTop");
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index a991a856..3db639cf 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -16,7 +16,7 @@ public class TypeTuple extends Type {
 
     @Override
     public StringBuilder _print(StringBuilder sb) {
-        sb.append("[ ");
+        sb.append("[");
         for( Type t : _types )
             t._print(sb).append(",");
         sb.setLength(sb.length()-1);
diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index e40136bd..e914f7c5 100644
--- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -12,7 +12,8 @@ public class Chapter05Test {
 
     @Test
     public void testChapter5IfStmt() {
-        Parser parser = new Parser("""
+        Parser parser = new Parser(
+"""
 int a = 1;
 if (arg == 1)
     a = arg+2;
@@ -28,7 +29,8 @@ return a;""");
   
     @Test
     public void testChapter5Test() {
-        Parser parser = new Parser("""
+        Parser parser = new Parser(
+"""
 int c = 3;
 int b = 2;
 if (arg == 1) {
@@ -42,7 +44,8 @@ return c;""", TypeInteger.BOT);
     
     @Test
     public void testChapter5Return2() {
-        Parser parser = new Parser("""
+        Parser parser = new Parser(
+"""
 if( arg==1 ) 
     return 3; 
 else 
@@ -54,7 +57,8 @@ else
     
     @Test
     public void testChapter5IfMergeB() {
-        Parser parser = new Parser("""
+        Parser parser = new Parser(
+"""
 int a=arg+1;
 int b=0;
 if( arg==1 )
@@ -68,7 +72,8 @@ return a+b;""");
 
     @Test
     public void testChapter5IfMerge2() {
-        Parser parser = new Parser("""
+        Parser parser = new Parser(
+"""
 int a=arg+1;
 int b=arg+2;
 if( arg==1 )
@@ -82,7 +87,8 @@ return a+b;""");
 
     @Test
     public void testChapter5Merge3() {
-        Parser parser = new Parser("""
+        Parser parser = new Parser(
+"""
 int a=1;
 if( arg==1 )
     if( arg==2 )
@@ -101,7 +107,8 @@ return a;
 
     @Test
     public void testChapter5Merge4() {
-        Parser parser = new Parser("""
+        Parser parser = new Parser(
+"""
 int a=0;
 int b=0;
 if( arg )
@@ -116,7 +123,8 @@ return arg+a+b;
 
     @Test
     public void testChapter5Merge5() {
-        Parser parser = new Parser("""
+        Parser parser = new Parser(
+"""
 int a=arg==2;
 if( arg==1 )
 {
@@ -333,8 +341,8 @@ return a;""");
 
     @Test
     public void testVarScopeNoPeephole() {
-        Node._disablePeephole = true;
         Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;");
+        Node._disablePeephole = true;
         StopNode ret = parser.parse();
         Node._disablePeephole = false;
         assertEquals("return (1+3);", ret.print());
@@ -359,8 +367,8 @@ return a;""");
 
     @Test
     public void testChapter2ParseGrammar() {
-        Node._disablePeephole = true; // disable peephole so we can observe full graph
         Parser parser = new Parser("return 1+2*3+-5;");
+        Node._disablePeephole = true; // disable peephole so we can observe full graph
         StopNode ret = parser.parse();
         assertEquals("return (1+((2*3)+(-5)));", ret.print());
         GraphVisualizer gv = new GraphVisualizer();