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

8 files changed, 104 insertions, 62 deletions

diff --git a/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index ce3522bc..64ffc771 100644
--- a/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -52,7 +52,6 @@ public class GraphVisualizer {
         nodes(sb, all);
         
         // Now the scopes, in a cluster no edges
-        scope(sb,parser._scope );
         for( ScopeNode scope : parser._xScopes )
             scope( sb, scope );
 
@@ -60,7 +59,6 @@ public class GraphVisualizer {
         nodeEdges(sb, all);
 
         // Walk the active Scope edges
-        scopeEdges( sb, parser._scope );
         for( ScopeNode scope : parser._xScopes )
             scopeEdges( sb, scope );
         
diff --git a/chapter07/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter07/src/main/java/com/seaofnodes/simple/IRPrinter.java
index dc6d9f4f..2a6dbefd 100644
--- a/chapter07/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/chapter07/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -24,16 +24,16 @@ public class IRPrinter {
             Node n = rpos.get(i);
             if( n.isCFG() || n.isMultiHead() ) {
                 if( !gap ) sb.append("\n"); // Blank before multihead
-                n._print_line(sb); // Print head
+                n._printLine(sb); // Print head
                 while( --i >= 0 ) {
                     Node t = rpos.get(i);
                     if( !t.isMultiTail() ) { i++; break; }
-                    t._print_line(sb);
+                    t._printLine(sb);
                 }
                 sb.append("\n"); // Blank after multitail
                 gap = true;
             } else {
-                n._print_line( sb );
+                n._printLine( sb );
                 gap = false;
             }
         }
diff --git a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java
index 99594c95..c3972be9 100644
--- a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java
@@ -87,12 +87,14 @@ public class Parser {
 
     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();
@@ -148,16 +150,23 @@ public class Parser {
     private Node parseWhile() {
         require("(");
 
-        // Loop region has two control inputs, the first one is the entry
-        // point, and second one is back edge that is set after loop is parsed
+        // 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.
-        
-        ctrl(new LoopNode(ctrl(),null).peephole());
-        ScopeNode head = _xScopes.push(_scope).keep(); // Save the current scope as the loop head
-        // Make a new Scope for the body.
-        _scope = _scope.dup(true);
+
+        ctrl(new LoopNode(ctrl(),null).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 = _xScopes.push(_scope).keep();
+        // Clone the head Scope to create a new Scope for the body.
+        // Create phis eagerly as part of cloning
+        _scope = _scope.dup(true); // The true argument triggers creating phis
 
         // Parse predicate
         var pred = require(parseExpression(), ")");
@@ -167,21 +176,31 @@ public class Parser {
         Node ifT = new ProjNode(ifNode, 0, "True" ).peephole();
         ifNode.unkeep();
         Node ifF = new ProjNode(ifNode, 1, "False").peephole();
-        // The exit scope, accounting for any side effects in the predicate
+
+        // Clone the body Scope to create the exit Scope
+        // which accounts for any side effects in the predicate
+        // The 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
         var exit = _scope.dup();
         _xScopes.push(exit);
         exit.ctrl(ifF);
 
         // Parse the true side, which corresponds to loop body
+        // Our current scope is the body Scope
         ctrl(ifT);              // set ctrl token to ifTrue projection
         parseStatement();       // Parse loop body
 
-        // The true branch loops back, so whatever is current control gets
-        // added to head loop as input
+        // The true branch loops back, so whatever is current control (_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.
         head.endLoop(_scope, exit);
         head.unkeep().kill();
-        _xScopes.pop();
-        _xScopes.pop();       // Discard pushed from graph display
+
+        _xScopes.pop();       // Cleanup
+        _xScopes.pop();       // Cleanup
 
         // At exit the false control is the current control, and
         // the scope is the exit scope after the exit test.
diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 85d7b20e..d23fa7c5 100644
--- a/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -5,9 +5,7 @@ import com.seaofnodes.simple.type.*;
 import java.util.BitSet;
 
 public class AddNode extends Node {
-    public AddNode(Node lhs, Node rhs) {
-        super(null, lhs, rhs);
-    }
+    public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
     @Override public String label() { return "Add"; }
     
@@ -132,7 +130,7 @@ public class AddNode extends Node {
     }
 
     static PhiNode pcon(Node op) {
-        return op instanceof PhiNode phi && phi.all_cons() ? phi : null;
+        return op instanceof PhiNode phi && phi.allCons() ? phi : null;
     }
         
     // Compare two off-spline nodes and decide what order they should be in.
@@ -144,8 +142,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/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java
index fcc8df85..4cd1b3d2 100644
--- a/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -117,7 +117,7 @@ public abstract class Node {
     // 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 _print_line( StringBuilder sb ) {
+    public void _printLine(StringBuilder sb ) {
         sb.append("%4d %-7.7s ".formatted(_nid,label()));
         if( _inputs==null ) {
             sb.append("DEAD\n");
@@ -177,7 +177,7 @@ public abstract class Node {
      * @param new_def the new definition
      * @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
@@ -212,7 +212,7 @@ public abstract class Node {
      * @param new_def the new definition, appended to the end of existing definitions
      * @return new_def for flow coding
      */
-    public 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
@@ -234,7 +234,7 @@ public abstract class Node {
 
     // 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.removeLast();
             if( old_def != null &&     // If it exists and
@@ -246,11 +246,11 @@ 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
     }
@@ -419,7 +419,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;
diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 202dbe37..e6cf338b 100644
--- a/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -93,9 +93,9 @@ public class PhiNode extends Node {
     }
 
     @Override
-    boolean all_cons() {
+    boolean allCons() {
         if( !(region() instanceof RegionNode r) || r.inProgress() )
             return false;
-        return super.all_cons();
+        return super.allCons();
     }
 }
diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index cc6af152..b5ce997b 100644
--- a/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -35,7 +35,7 @@ public class ScopeNode extends Node {
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
         sb.append("Scope[ ");
-        String[] names = reverse_names();
+        String[] names = reverseNames();
         for( int j=0; j<nIns(); j++ ) {
             sb.append(names[j]).append(":");
             Node n = in(j);
@@ -45,8 +45,14 @@ public class ScopeNode extends Node {
         return sb.append("]");
     }
 
-    // Expensive...
-    public String[] reverse_names() {
+    /**
+     * 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() )
@@ -59,29 +65,50 @@ public class ScopeNode extends Node {
     @Override public Node idealize() { return null; }
 
     public void push() { _scopes.push(new HashMap<>());  }
-    public void pop() { pop_n(_scopes.pop().size());  }
-    
-    // Create a new name in the current scope
+    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 add_def(n);
+        return addDef(n);
     }
-
-    // Lookup a name.  It is recursive to support lazy Phis on loops (coming in chapter 8).
-    public Node lookup(String name) { return update(name,null,_scopes.size()-1);  }  
-    // If the name is present in any scope, then redefine else null
-    public Node update(String name, Node n) { return update(name,n,_scopes.size()-1); }
-    // Both recursive lookup and update.
-    private Node update( String name, Node n, int i ) {
-        if( i<0 ) return null;  // Missed in all scopes, not found
-        var syms = _scopes.get(i);
+    /**
+     * 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,i-1); // Missed in this scope, recursively look
+        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
-        return n==null ? old : set_def(idx,n);
+        // 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() { return in(0); }
@@ -96,7 +123,7 @@ public class ScopeNode extends Node {
      *
      * @return Node that was bound
      */
-    public Node ctrl(Node n) { return set_def(0,n); }
+    public Node ctrl(Node n) { return setDef(0,n); }
 
     /**
      * Duplicate a ScopeNode; including all levels, up to Nodes.  So this is
@@ -115,16 +142,16 @@ public class ScopeNode extends Node {
         // 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));
-        String[] reverse = reverse_names();
-        dup.add_def(ctrl());      // Control input is just copied
+        String[] names = reverseNames(); // Get the variable names
+        dup.addDef(ctrl());      // Control input is just copied
         for( int i=1; i<nIns(); i++ ) {
-            if ( !loop ) { dup.add_def(in(i)); }
+            if ( !loop ) { dup.addDef(in(i)); }
             else {
                 // Create a phi node with second input as null - to be filled in
                 // by endLoop() below
-                dup.add_def(new PhiNode(reverse[i], ctrl(), in(i), null).peephole());
+                dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole());
                 // Ensure our node has the same phi in case we created one
-                set_def(i, dup.in(i));
+                setDef(i, dup.in(i));
             }
         }
         return dup;
@@ -140,11 +167,11 @@ public class ScopeNode extends Node {
      */
     public Node mergeScopes(ScopeNode that) {
         RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep());
-        String[] ns = reverse_names();
+        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(ns[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.unkeep().peephole();
     }
@@ -154,11 +181,11 @@ public class ScopeNode extends Node {
     public void endLoop(ScopeNode back, ScopeNode exit ) {
         Node ctrl = ctrl();
         assert ctrl instanceof LoopNode loop && loop.inProgress();
-        ctrl.set_def(2,back.ctrl());
+        ctrl.setDef(2,back.ctrl());
         for( int i=1; i<nIns(); i++ ) {
             PhiNode phi = (PhiNode)in(i);
             assert phi.region()==ctrl && phi.in(2)==null;
-            phi.set_def(2,back.in(i));
+            phi.setDef(2,back.in(i));
             // Do an eager useless-phi removal
             Node in = phi.peephole();
             if( in != phi )
diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java
index c4375771..a0aacf2b 100644
--- a/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -47,7 +47,7 @@ public class StopNode extends Node {
     }
 
     public Node addReturn(Node node) {
-        return add_def(node);
+        return addDef(node);
     }
 
 }