Chapter 7: While Statementlinear-chapter07

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

1 files changed, 70 insertions, 46 deletions

diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index b30dd450..07f1af21 100644
--- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -11,13 +11,22 @@ import java.util.*;
  */
 public class GraphVisualizer {
 
+    /**
+     * If set to true we put the control nodes in a separate cluster from
+     * data nodes.
+     */
+    boolean _separateControlCluster = false;
+
+    public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; }
+    public GraphVisualizer() { this(false); }
+
     public String generateDotOutput(Parser parser) {
 
         // Since the graph has cycles, we need to create a flat list of all the
         // nodes in the graph.
         Collection<Node> all = findAll(parser);
         StringBuilder sb = new StringBuilder();
-        sb.append("digraph chapter06 {\n");
+        sb.append("digraph chapter07 {\n");
         sb.append("/*\n");
         sb.append(parser.src());
         sb.append("\n*/\n");
@@ -36,42 +45,48 @@ public class GraphVisualizer {
         // nodes much prettier to look at.
         sb.append("\tconcentrate=\"true\";\n");
 
+        // Force nested scopes to order
+        sb.append("\tcompound=\"true\";\n");
+
         // Just the Nodes first, in a cluster no edges
         nodes(sb, all);
 
         // Now the scopes, in a cluster no edges
-        for (ScopeNode sn: parser._xScopes)
-            scopes(sb, sn);
+        for( ScopeNode scope : parser._xScopes )
+            scope( sb, scope );
 
         // Walk the Node edges
         nodeEdges(sb, all);
 
-        // Walk the Scope edges
-        for (ScopeNode sn: parser._xScopes)
-            scopeEdges(sb, sn);
+        // Walk the active Scope edges
+        for( ScopeNode scope : parser._xScopes )
+            scopeEdges( sb, scope );
 
         sb.append("}\n");
         return sb.toString();
     }
 
-
-    private void nodes(StringBuilder sb, Collection<Node> all) {
+    private void nodesByCluster(StringBuilder sb, boolean doCtrl, Collection<Node> all) {
+        if (!_separateControlCluster && doCtrl) // all nodes in 1 cluster
+            return;
         // Just the Nodes first, in a cluster no edges
-        sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
-        for( Node n : all ) {
-            if( n instanceof ProjNode || n instanceof ScopeNode )
+        sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name
+        for (Node n : all) {
+            if (n instanceof ProjNode || n instanceof ScopeNode)
                 continue; // Do not emit, rolled into MultiNode or Scope cluster already
+            if (_separateControlCluster && doCtrl && !n.isCFG()) continue;
+            if (_separateControlCluster && !doCtrl && n.isCFG()) continue;
             sb.append("\t\t").append(n.uniqueName()).append(" [ ");
             String lab = n.glabel();
-            if( n instanceof MultiNode ) {
+            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");
@@ -79,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>");
                     }
                 }
@@ -94,41 +109,46 @@ public class GraphVisualizer {
             } else {
                 // control nodes have box shape
                 // other nodes are ellipses, i.e. default shape
-                if( n.isCFG() )
-                    sb.append("shape=box style=filled fillcolor=yellow ");
-                if( n instanceof PhiNode )
-                    sb.append("style=filled fillcolor=lightyellow ");
+                if (n.isCFG()) sb.append("shape=box style=filled fillcolor=yellow ");
+                else if (n instanceof PhiNode) sb.append("style=filled fillcolor=lightyellow ");
                 sb.append("label=\"").append(lab).append("\" ");
             }
             sb.append("];\n");
         }
-
-        // Force Region & Phis to line up
-        for( Node n : all ) {
-            if( n instanceof RegionNode region ) {
-                sb.append("\t\t{ rank=same; ");
-                sb.append(region).append(";")     ;
-                for( Node phi : region._outputs )
-                    if( phi instanceof PhiNode )
-                        sb.append(phi.uniqueName()).append(";");
-                sb.append("}\n");
+        if (!_separateControlCluster) {
+            // Force Region & Phis to line up
+            for (Node n : all) {
+                if (n instanceof RegionNode region) {
+                    sb.append("\t\t{ rank=same; ");
+                    sb.append(region).append(";");
+                    for (Node phi : region._outputs)
+                        if (phi instanceof PhiNode) sb.append(phi.uniqueName()).append(";");
+                    sb.append("}\n");
+                }
             }
         }
-
         sb.append("\t}\n");     // End Node cluster
     }
 
-    private void scopes( StringBuilder sb, ScopeNode scopenode) {
+    private void nodes(StringBuilder sb, Collection<Node> all) {
+        nodesByCluster(sb, true, all);
+        nodesByCluster(sb, false, all);
+    }
+
+    // Build a nested scope display, walking the _prev edge
+    private void scope( StringBuilder sb, ScopeNode scope ) {
         sb.append("\tnode [shape=plaintext];\n");
-        int level=0;
-        for( HashMap<String,Integer> scope : scopenode._scopes ) {
-            String scopeName = makeScopeName(scopenode, level);
+        int level=1;
+        for( int idx = scope._scopes.size()-1; idx>=0; idx-- ) {
+            var syms = scope._scopes.get(idx);
+            String scopeName = makeScopeName(scope, level);
             sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name
             sb.append("\t\t").append(scopeName).append(" [label=<\n");
             sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n");
             // Add the scope level
-            sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>");
-            for( String name : scope.keySet() )
+            int scopeLevel = scope._scopes.size()-level;
+            sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(scopeLevel).append("</TD>");
+            for(String name: syms.keySet())
                 sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>");
             sb.append("</TR>\n");
             sb.append("\t\t\t</TABLE>>];\n");
@@ -137,7 +157,7 @@ public class GraphVisualizer {
         // Scope clusters nest, so the graphics shows the nested scopes, so
         // they are not closed as they are printed; so they just keep nesting.
         // We close them all at once here.
-        sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters
+        sb.append( "\t}\n".repeat( level-1 ) ); // End all Scope clusters
     }
 
     private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; }
@@ -153,8 +173,8 @@ public class GraphVisualizer {
             // ScopeNodes are done separately
             if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode )
                 continue;
-            int i=0;
-            for( Node def : n._inputs ) {
+            for( int i=0; i<n.nIns(); i++ ) {
+                Node def = n.in(i);
                 if( n instanceof PhiNode && def instanceof RegionNode ) {
                     // Draw a dotted use->def edge from Phi to Region.
                     sb.append('\t').append(n.uniqueName());
@@ -173,21 +193,25 @@ public class GraphVisualizer {
                     // control edges are colored red
                     if( def.isCFG() )
                         sb.append(" color=red");
+                    // Backedges do not add a ranking constraint
+                    if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) )
+                        sb.append(" constraint=false");
                     sb.append("];\n");
                 }
-                i++;
             }
         }
     }
 
     // Walk the scope edges
-    private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) {
+    private void scopeEdges( StringBuilder sb, ScopeNode scope ) {
         sb.append("\tedge [style=dashed color=cornflowerblue];\n");
-        int level=0;
-        for( HashMap<String,Integer> scope : scopenode._scopes ) {
-            String scopeName = makeScopeName(scopenode, level);
-            for( String name : scope.keySet() ) {
-                Node def = scopenode.in(scope.get(name));
+        int level=1;
+        for( int i = scope._scopes.size()-1; i>=0; i-- ) {
+            var syms = scope._scopes.get(i);
+            String scopeName = makeScopeName(scope, level);
+            for( String name : syms.keySet() ) {
+                int idx = syms.get(name);
+                Node def = scope.in(idx);
                 if( def==null ) continue;
                 sb.append("\t")
                   .append(scopeName).append(":")