Chapter8 update to sync with latest changes (#53)

* #52 Update chapter8 to align with chapter7

* #52 Update chapter8 to align with chapter7

* #52 Fix spacing

8 files changed, 137 insertions, 80 deletions

diff --git a/chapter08/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter08/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index c823641d..5009264f 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter08/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 );
         
@@ -73,22 +71,22 @@ public class GraphVisualizer {
             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 )
+        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 ) {
+            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 ) {
+                for (Node use : n._outputs) {
+                    if (use instanceof ProjNode proj) {
                         if (!doProjTable) {
                             doProjTable = true;
                             sb.append("<TD>").append("\n");
@@ -96,7 +94,7 @@ public class GraphVisualizer {
                             sb.append("\t\t\t\t<TR>");
                         }
                         sb.append("<TD PORT=\"p").append(proj._idx).append("\"");
-                        if( proj.isCFG() ) sb.append(" BGCOLOR=\"yellow\"");
+                        if (proj.isCFG()) sb.append(" BGCOLOR=\"yellow\"");
                         sb.append(">").append(proj.glabel()).append("</TD>");
                     }
                 }
@@ -107,7 +105,7 @@ public class GraphVisualizer {
                 }
                 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
@@ -119,12 +117,12 @@ public class GraphVisualizer {
         }
         if (!_separateControlCluster) {
             // Force Region & Phis to line up
-            for( Node n : all ) {
-                if( n instanceof RegionNode region ) {
+            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(region).append(";");
+                    for (Node phi : region._outputs)
+                        if (phi instanceof PhiNode) sb.append(phi.uniqueName()).append(";");
                     sb.append("}\n");
                 }
             }
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter08/src/main/java/com/seaofnodes/simple/IRPrinter.java
index dc6d9f4f..2a6dbefd 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/chapter08/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/chapter08/src/main/java/com/seaofnodes/simple/Parser.java b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java
index 28b8f432..41803f24 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java
@@ -89,12 +89,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();
@@ -150,16 +152,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, which has lazy-phi loop markers.
-        _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(), ")");
@@ -169,21 +178,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/chapter08/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 85d7b20e..d23fa7c5 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter08/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/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java
index fcc8df85..4cd1b3d2 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter08/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/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 202dbe37..e6cf338b 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter08/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/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index e486a390..38dfe15d 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -36,7 +36,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);
@@ -50,8 +50,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() )
@@ -64,29 +70,47 @@ 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.
-    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.  If a Lazy Phi is found at any level,
-    // a concrete Phi is inserted at the loop head and also in the current
-    // scope.  The Lazy Phi does a recursive lookup for its input which may
-    // itself be Lazy.
-    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( old instanceof ScopeNode loop ) {
             // Lazy Phi!
@@ -96,10 +120,10 @@ public class ScopeNode extends Node {
                 // 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.set_def(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,i),null).peephole());
-            set_def(idx,old);
+                : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
+            setDef(idx,old);
         }
-        return n==null ? old : set_def(idx,n); // Not lazy, so this is the answer
+        return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer
     }
 
     public Node ctrl() { return in(0); }
@@ -114,7 +138,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
@@ -138,11 +162,23 @@ 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 = Parser.LAZY ? null : reverse_names();
-        dup.add_def(ctrl());      // Control input is just copied
+
+        dup.addDef(ctrl());      // Control input is just copied
         for( int i=1; i<nIns(); i++ ) {
-            dup.add_def(loop ? (Parser.LAZY ? this : new PhiNode(reverse[i],ctrl(),in(i),null).peephole()) : in(i));
-            if( loop && !Parser.LAZY ) set_def(i,dup.in(i));
+            if ( !loop ) { dup.addDef(in(i)); }
+            else if (Parser.LAZY) {
+                // For lazy phi we need to set a sentinel that will
+                // trigger phi creation on update
+                dup.addDef(this); // Add a sentinel which is self
+            }
+            else {
+                String[] names = reverseNames(); // Get the variable names
+                // Create a phi node with second input as null - to be filled in
+                // by endLoop() below
+                dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole());
+                // Ensure our node has the same phi in case we created one
+                setDef(i, dup.in(i));
+            }
         }
         return dup;
     }
@@ -157,13 +193,18 @@ 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
-                Node n1 = Parser.LAZY ? this.lookup(ns[i]) :      in(i); // Must do a lookup to set lazy Phis
-                Node n2 = Parser.LAZY ? that.lookup(ns[i]) : that.in(i); // Must do a lookup to set lazy Phis
-                set_def(i, new PhiNode(ns[i], r, n1, n2).peephole());
+                // If we are in lazy phi mode we need to a lookup
+                // by name as it will triger a phi creation
+                Node phi;
+                if (Parser.LAZY)
+                    phi = new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole();
+                else
+                   phi = new PhiNode(ns[i], r, in(i), that.in(i)).peephole();
+                setDef(i, phi);
             }
         }
         that.kill();            // Kill merged scope
@@ -171,22 +212,23 @@ public class ScopeNode extends Node {
     }
     
     // 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.set_def(2,back.ctrl());
+        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.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 )
                     phi.subsume(in);
             }
             if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also
-                exit.set_def(i,in(i));
+                exit.setDef(i,in(i));
         }
         back.kill();            // Loop backedge is dead
     }
diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/StopNode.java
index c4375771..a0aacf2b 100644
--- a/chapter08/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter08/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);
     }
 
 }