Update visualization to show all the Scope Nodes that are active.

Fix test cases broken due to renaming of ProjNode label.
Cleanup the way we update $ctrl token
Assign an ID to each ScopeNode so that when we visualize we can assign different names

4 files changed, 104 insertions, 52 deletions

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 3470a49a..d277a980 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -34,13 +34,15 @@ public class GraphVisualizer {
         nodes(sb, all);
         
         // Now the scopes, in a cluster no edges
-        scopes(sb, parser._scope);
+        for (ScopeNode sn: parser._allScopes)
+            scopes(sb, sn);
 
         // Walk the Node edges
         nodeEdges(sb, all);
 
         // Walk the Scope edges
-        scopeEdges(sb, parser._scope);
+        for (ScopeNode sn: parser._allScopes)
+            scopeEdges(sb, sn);
         
         sb.append("}\n");
         return sb.toString();
@@ -51,8 +53,8 @@ public class GraphVisualizer {
         // Just the Nodes first, in a cluster no edges
         sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
         for( Node n : all ) {
-            if( n instanceof ProjNode )
-                continue; // Do not emit, rolled into MultiNode already
+            if( n instanceof ProjNode || n instanceof ScopeNode )
+                continue; // Do not emit, rolled into MultiNode or Scope cluster already
             sb.append("\t\t").append(n.uniqueName()).append(" [ ");
             String lab = n.label();
             if( n instanceof MultiNode ) {
@@ -99,8 +101,8 @@ public class GraphVisualizer {
         sb.append("\tnode [shape=plaintext];\n");
         int level=0;
         for( HashMap<String,Integer> scope : scopenode._scopes ) {
-            sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name
-            String scopeName = makeScopeName(level);
+            String scopeName = makeScopeName(scopenode, level);
+            sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name
             sb.append("\t\t").append(scopeName).append(" [label=<\n");
             sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n");
             // Add the scope level
@@ -116,15 +118,15 @@ public class GraphVisualizer {
         // We close them all at once here.
         sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters
     }
-    
-    private String makeScopeName(int level) { return "scope" + level; }
+
+    private String makeScopeName(ScopeNode sn, int level) { return sn.label() + "_" + level; }
     private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; }
 
     // Walk the node edges
     private void nodeEdges(StringBuilder sb, Collection<Node> all) {
         for( Node n : all ) {
-            if( n instanceof ConstantNode || n instanceof ProjNode )
-                continue;       // Do not display the Constant->Start edge; ProjNodes handled by Multi
+            if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode )
+                continue;       // Do not display the Constant->Start edge; ProjNodes handled by Multi; ScopeNodes are done separately
             for( Node def : n._inputs )
                 if( def != null ) {
                     sb.append('\t').append(n.uniqueName()).append(" -> ");
@@ -145,7 +147,7 @@ public class GraphVisualizer {
         sb.append("\tedge [style=dashed color=cornflowerblue];\n");
         int level=0;
         for( HashMap<String,Integer> scope : scopenode._scopes ) {
-            String scopeName = makeScopeName(level);
+            String scopeName = makeScopeName(scopenode, level);
             for( String name : scope.keySet() ) {
                 Node def = scopenode.in(scope.get(name));
                 if( def==null ) continue;
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
index e5d2901e..2953ec26 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -15,6 +15,11 @@ import java.util.*;
 public class Parser {
 
     /**
+     * The control token is a name that binds to the currently active control
+     * node in the graph
+     */
+    private static final String CTRL_TOKEN = "$ctrl";
+    /**
      * A Global Static, unique to each compilation.  This is a public, so we
      * can make constants everywhere without having to thread the StartNode
      * through the entire parser and optimizer.
@@ -39,11 +44,16 @@ public class Parser {
      */
     public ScopeNode _scope;
 
-    public List<ScopeNode> _allScopes = new ArrayList<>();
+    /**
+     * 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 List<ScopeNode> _allScopes = new ArrayList<>();
 
     public Parser(String source, TypeInteger arg) {
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
+        _allScopes.add(_scope);
         Node.reset();
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
         START.peephole();
@@ -55,12 +65,18 @@ public class Parser {
 
     String src() { return new String( _lexer._input ); }
 
+    private Node ctrlToken() {
+        return _scope.lookup(CTRL_TOKEN);
+    }
 
+    private void updateCtrlToken(Node n) {
+        _scope.update(CTRL_TOKEN, n);
+    }
 
     public ReturnNode parse() {
         _scope.push();
         try {
-            _scope.define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole());
+            _scope.define(CTRL_TOKEN, new ProjNode(START, 0, CTRL_TOKEN).peephole());
             _scope.define("arg"  , new ProjNode(START, 1, "arg"  ).peephole());
             return (ReturnNode) parseBlock();
         }
@@ -110,56 +126,58 @@ public class Parser {
         // Parse predicate
         var pred = require(parseExpression(), ")");
         // IfNode takes current control and predicate
-        IfNode ifNode = new IfNode(_scope.lookup("$ctrl"), pred);
+        IfNode ifNode = new IfNode(ctrlToken(), pred);
         // Setup projection nodes
         ProjNode ifT = new ProjNode(ifNode, 0, "True");
         ProjNode ifF = new ProjNode(ifNode, 1, "False");
         // In if true branch, the ifT proj node becomes the ctrl
         // But first clone the scope and set it as current
         ScopeNode savedScope = _scope;
-        ScopeNode ifScope = _scope.dup();  // Duplicate current scope
-        _allScopes.add(ifScope);           // For visualization we need all scopes
-        _scope = ifScope;                  // ifScope is current
-        _scope.define("$ctrl", ifT);
-        var thenStmt = parseStatement();
+        ScopeNode ifScope = _scope.dup();   // Duplicate current scope
+        _allScopes.add(ifScope);            // For graph visualization we need all scopes
+        _scope = ifScope;                   // ifScope is now the current scope
+        updateCtrlToken(ifT);               // set ctrl token to ifTrue projection
+        parseStatement();
         // restore scope
-        _scope = savedScope;
+        _scope = savedScope;                // Restore scope to original, we use this for else block if any
         // Setup ifF as the ctrl
-        _scope.define("$ctrl", ifF);
-        Node elseStmt = null;
-        if (match("else")) elseStmt = parseStatement();
+        updateCtrlToken(ifF);               // Ctrl token is now set to ifFalse projection
+        if (match("else")) parseStatement();
         // Create region node and merge scopes
-        // If a var is in both scopes and different then we need to create PhiNode for it
-        // After merge _scope remains
+        // If a var is in both scopes and has different binding then we need to create PhiNode for it
+        // After merge _scope remains, and ifScope is discarded
         RegionNode region = mergeScopes(ifT, ifScope, ifF, _scope);
-        _scope.update("$ctrl", region);
-        ifScope.clear();
-        _allScopes.remove(ifScope);
+        updateCtrlToken(region);            // Now region becomes the ctrl token
+        ifScope.clear();                    // Clean up ifScope
+        _allScopes.remove(ifScope);         // Discard ifScope
         return region;
     }
 
-    private RegionNode mergeScopes(ProjNode ifT, ScopeNode ifScope, ProjNode ifF, ScopeNode scope) {
+    private RegionNode mergeScopes(ProjNode ifT, ScopeNode ifScope, ProjNode ifF, ScopeNode mergeScope) {
         RegionNode regionNode = new RegionNode(ifT, ifF);
         Set<String> namesDone = new HashSet<>();
         for (int level = ifScope._scopes.size()-1; level >= 0; level--) {
             var tab = ifScope._scopes.get(level);
             for (Map.Entry<String, Integer> e: tab.entrySet()) {
                 String name = e.getKey();
-                if (name.equals("$ctrl")) // ignore
+                if (name.equals(CTRL_TOKEN))    // ignore ctrl token
                     continue;
-                if (namesDone.contains(name)) // don't visit a name twice
+                if (namesDone.contains(name))   // don't visit a name twice
                     continue;
                 namesDone.add(name);
                 Integer idx = e.getValue();
                 Node ifTdef = ifScope.in(idx);
-                Node ifNdef = scope.lookup(name);
+                Node ifNdef = mergeScope.lookup(name);   // Lookup name in merge scope
                 if (ifNdef == null)
                     // The else scope didn't see this name
-                    scope.define(name, ifTdef); // Is this correct? Do we need same level as in ifScope?
-                else if (!ifTdef.equals(ifNdef)) {
+                    // Is this correct? Do we need same level as in ifScope?
+                    // FIXME can this even happen, as all nested scopes should be gone
+                    // so we cannot have a new var in same level anyway
+                    mergeScope.define(name, ifTdef);
+                else if (!ifTdef.equals(ifNdef)) { // FIXME do we need equals or just ID comparison?
                     // Names are mapped to different nodes
                     PhiNode phiNode = new PhiNode(regionNode, ifTdef, ifNdef);
-                    scope.update(name, phiNode);
+                    mergeScope.update(name, phiNode);
                 }
             }
         }
@@ -177,8 +195,8 @@ public class Parser {
      */
     private Node parseReturn() {
         var expr = require(parseExpression(), ";");
-        Node ret = new ReturnNode(_scope.lookup("$ctrl"), expr);
-        _scope.update("$ctrl",null);
+        Node ret = new ReturnNode(ctrlToken(), expr);
+        _scope.update(CTRL_TOKEN,null);
         return ret;
     }
 
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 be5538a3..5ac42c43 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -16,12 +16,24 @@ public class ScopeNode extends Node {
      * The top of this stack represents current scope.
      */
     public final Stack<HashMap<String, Integer>> _scopes = new Stack<>();
+
+    /**
+     * We duplicate ScopeNodes when branches occur, so it is useful to have
+     * a unique name for each ScopeNode; this helps when we want to visualize the
+     * graph
+     */
+    private int _id;
+
+    private static int _idCounter = 0;
+
+    public ScopeNode() { _id = _idCounter++; }
   
     @Override
-    public String label() { return "Scope"; }
+    public String label() { return "Scope" + _id; }
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
+        sb.append(label());
         for( HashMap<String,Integer> scope : _scopes ) {
             sb.append("[");
             boolean first=true;
@@ -84,21 +96,30 @@ public class ScopeNode extends Node {
         return null;
     }
 
-
+    /**
+     * Duplicate a ScopeNode; including all levels.
+     *
+     * We do it in a way that ensures that the new ScopeNode becomes
+     * additional user of all defined names
+     */
     public ScopeNode dup() {
-        ScopeNode sc = new ScopeNode();
+        ScopeNode dupScope = new ScopeNode();
         for (HashMap<String, Integer> tab: _scopes) {
-            sc.push();
+            dupScope.push(); // Create same level in the duplicate
             for (Map.Entry<String, Integer> e: tab.entrySet()) {
                 String name = e.getKey();
                 Integer idx = e.getValue();
                 Node n = in(idx);
-                sc.define(name, n);
+                dupScope.define(name, n); // Ensure that dupScope is a user of n
             }
         }
-        return sc;
+        return dupScope;
     }
 
+    /**
+     * Cleanup the scope and all its levels.
+     * Ensure that the scope is removed as user of all the defs.
+     */
     public void clear() {
         while (!_scopes.empty())
             pop();
diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 0604e9c6..cc5b5871 100644
--- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -15,8 +15,19 @@ public class Chapter05Test {
 
     @Test
     public void testChapter5IfStmt() {
-        Parser parser = new Parser("int a = 1; if (arg == 1) a = arg+2; else a = arg-3; return a; #showGraph;", TypeInteger.BOT);
+        Parser parser = new Parser("""
+                int a = 1;\s
+                if (arg == 1)\s
+                	a = arg+2;\s
+                else {
+                	a = arg-3;\s
+                	#showGraph;
+                }
+                return a;\s
+                #showGraph;
+                """, TypeInteger.BOT);
         ReturnNode ret = parser.parse();
+        assertEquals("return Phi(Region15,(arg3+2),(arg3-3));", ret.toString());
     }
 
 
@@ -24,42 +35,42 @@ public class Chapter05Test {
     public void testChapter4Peephole() {
         Parser parser = new Parser("return 1+arg+2; #showGraph;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();
-        assertEquals("return (Proj_3+3);", ret.print());
+        assertEquals("return (arg3+3);", ret.print());
     }
 
     @Test
     public void testChapter4Peephole2() {
         Parser parser = new Parser("return (1+arg)+2;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();
-        assertEquals("return (Proj_3+3);", ret.print());
+        assertEquals("return (arg3+3);", ret.print());
     }
 
     @Test
     public void testChapter4Add0() {
         Parser parser = new Parser("return 0+arg;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();
-        assertEquals("return Proj_3;", ret.print());
+        assertEquals("return arg3;", ret.print());
     }
 
     @Test
     public void testChapter4AddAddMul() {
         Parser parser = new Parser("return arg+0+arg;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();
-        assertEquals("return (Proj_3*2);", ret.print());
+        assertEquals("return (arg3*2);", ret.print());
     }
   
     @Test
     public void testChapter4Peephole3() {
         Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();
-        assertEquals("return ((Proj_3*2)+6);", ret.print());
+        assertEquals("return ((arg3*2)+6);", ret.print());
     }
 
     @Test
     public void testChapter4Mul1() {
         Parser parser = new Parser("return 1*arg;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();
-        assertEquals("return Proj_3;", ret.print());
+        assertEquals("return arg3;", ret.print());
     }
   
     @Test
@@ -109,14 +120,14 @@ public class Chapter05Test {
     public void testChapter4Bug1() {
         Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();
-        assertEquals("return (Proj_3+3);", ret.print());
+        assertEquals("return (arg3+3);", ret.print());
     }
 
     @Test
     public void testChapter4Bug2() {
         Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;", TypeInteger.BOT);
         ReturnNode ret = parser.parse();
-        assertEquals("return (Proj_3+1);", ret.print());
+        assertEquals("return (arg3+1);", ret.print());
     }
 
     @Test