From 48ce51174de5636232ad642d1080c8872d245f93 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 3 Dec 2023 23:23:04 +0000 Subject: Chapter 7: While Statement Co-authored-by: Cliff Click Co-authored-by: Thalia Archibald Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Robert Obkircher --- .../com/seaofnodes/simple/GraphVisualizer.java | 116 +++++++++++++-------- 1 file changed, 70 insertions(+), 46 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/GraphVisualizer.java') 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 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 all) { + private void nodesByCluster(StringBuilder sb, boolean doCtrl, Collection 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\n"); sb.append("\t\t\t\n"); sb.append("\t\t\t"); 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(""); } sb.append(""); } } @@ -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 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 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
").append(lab).append("
").append("\n"); @@ -79,7 +94,7 @@ public class GraphVisualizer { sb.append("\t\t\t\t
").append(proj.glabel()).append("
\n"); // Add the scope level - sb.append("\t\t\t"); - for( String name : scope.keySet() ) + int scopeLevel = scope._scopes.size()-level; + sb.append("\t\t\t"); + for(String name: syms.keySet()) sb.append(""); sb.append("\n"); sb.append("\t\t\t
").append(level).append("
").append(scopeLevel).append("").append(name).append("
>];\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; idef 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 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(":") -- cgit v1.2.3