From 29fb671e69f90ad3b04c6fa8d746caf857f89e77 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 22 Sep 2026 11:25:05 -0700 Subject: Add shared graph viewer to all chapters --- .../com/seaofnodes/simple/GraphVisualizer.java | 177 --------------------- .../main/java/com/seaofnodes/simple/Parser.java | 25 ++- .../java/com/seaofnodes/simple/node/AddNode.java | 2 - .../java/com/seaofnodes/simple/node/DivNode.java | 2 - .../java/com/seaofnodes/simple/node/MinusNode.java | 2 - .../java/com/seaofnodes/simple/node/MulNode.java | 2 - .../main/java/com/seaofnodes/simple/node/Node.java | 28 ++-- .../java/com/seaofnodes/simple/node/SubNode.java | 2 - .../simple/print/SimpleGraphAdapter.java | 47 ++++++ .../simple/print/SimpleGraphObserver.java | 38 +++++ .../java/com/seaofnodes/simple/Chapter02Test.java | 4 - .../java/com/seaofnodes/simple/Chapter03Test.java | 4 +- 12 files changed, 117 insertions(+), 216 deletions(-) delete mode 100644 chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java create mode 100644 chapter03/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java create mode 100644 chapter03/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java (limited to 'chapter03/src') diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java deleted file mode 100644 index 9dfac52d..00000000 --- a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ /dev/null @@ -1,177 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; - -import java.util.*; - -/** - * Simple visualizer that outputs GraphViz dot format. - * The dot output must be saved to a file and run manually via dot to generate the SVG output. - * Currently, this is done manually. - */ -public class GraphVisualizer { - - 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 chapter03 {\n"); - sb.append("/*\n"); - sb.append(parser.src()); - sb.append("\n*/\n"); - - // To keep the Scopes below the graph and pointing up into the graph we - // need to group the Nodes in a subgraph cluster, and the scopes into a - // different subgraph cluster. THEN we can draw edges between the - // scopes and nodes. If we try to cross subgraph cluster borders while - // still making the subgraphs DOT gets confused. - sb.append("\trankdir=BT;\n"); // Force Nodes before Scopes - - // Preserve node input order - sb.append("\tordering=\"in\";\n"); - - // Merge multiple edges hitting the same node. Makes common shared - // nodes much prettier to look at. - sb.append("\tconcentrate=\"true\";\n"); - - // Just the Nodes first, in a cluster no edges - nodes(sb, all); - - // Now the scopes, in a cluster no edges - scopes(sb, parser._scope); - - // Walk the Node edges - nodeEdges(sb, all); - - // Walk the Scope edges - scopeEdges(sb, parser._scope); - - sb.append("}\n"); - return sb.toString(); - } - - - private void nodes(StringBuilder sb, Collection all) { - // 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 ScopeNode ) - continue; // Do not emit, rolled into Scope cluster already - sb.append("\t\t").append(n.uniqueName()).append(" [ "); - String lab = n.glabel(); - // control nodes have box shape - // other nodes are ellipses, i.e. default shape - if( n.isCFG() ) - sb.append("shape=box style=filled fillcolor=yellow "); - sb.append("label=\"").append(lab).append("\" "); - sb.append("];\n"); - } - sb.append("\t}\n"); // End Node cluster - } - - private void scopes( StringBuilder sb, ScopeNode scopenode) { - sb.append("\tnode [shape=plaintext];\n"); - int level=0; - for( HashMap scope : scopenode._scopes ) { - 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\n"); - // Add the scope level - sb.append("\t\t\t"); - for( String name : scope.keySet() ) - sb.append(""); - sb.append("\n"); - sb.append("\t\t\t
").append(level).append("").append(name).append("
>];\n"); - level++; - } - // 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 - } - - private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } - private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } - - // Walk the node edges - private void nodeEdges(StringBuilder sb, Collection all) { - // All them edge labels - sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); - for( Node n : all ) { - // In this chapter we do display the Constant->Start edge; - // ScopeNodes are done separately - if( n instanceof ScopeNode ) - continue; - int i=0; - for( Node def : n._inputs ) { - if( def != null ) { - // Most edges land here use->def - sb.append('\t').append(n.uniqueName()).append(" -> "); - sb.append(def.uniqueName()); - // Number edges, so we can see how they track - sb.append("[taillabel=").append(i); - if( n instanceof ConstantNode && def instanceof StartNode ) - sb.append(" style=dotted"); - // control edges are colored red - else if( def.isCFG() ) - sb.append(" color=red"); - sb.append("];\n"); - } - i++; - } - } - } - - // Walk the scope edges - private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { - 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)); - if( def==null ) continue; - sb.append("\t") - .append(scopeName).append(":") - .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted - .append(" -> "); - sb.append(def.uniqueName()); - sb.append(";\n"); - } - level++; - } - } - - /** - * Finds all nodes in the graph. - */ - private Collection findAll(Parser parser) { - final StartNode start = Parser.START; - final HashMap all = new HashMap<>(); - for( Node n : start._outputs ) - walk(all, n); - // Scan symbol tables - for( HashMap scope : parser._scope._scopes ) - for (Integer i : scope.values()) - walk(all, parser._scope.in(i)); - return all.values(); - } - - /** - * Walk a subgraph and populate distinct nodes in the all list. - */ - private void walk(HashMap all, Node n) { - if(n == null ) return; - if (all.get(n._nid) != null) return; // Been there, done that - all.put(n._nid, n); - for (Node c : n._inputs) - if (c != null) - walk(all, c); - for (Node c : n._outputs) - if (c != null) - walk(all, c); - } -} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index fa1a852c..e6cb84f8 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.graph.GraphObserver; + import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -14,6 +16,12 @@ import java.util.*; */ public class Parser { + // Current compilation context; the observer belongs to the parser. + public static Parser PARSER; + public GraphObserver _obs; + public int pos() { return _lexer._position; } + + /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode @@ -43,6 +51,7 @@ public class Parser { public Parser(String source) { _lexer = new Lexer(source); + PARSER = this; Node.reset(); _scope = new ScopeNode(); START = new StartNode(); @@ -50,11 +59,9 @@ public class Parser { String src() { return new String( _lexer._input ); } - public ReturnNode parse() { return parse(false); } - public ReturnNode parse(boolean show) { + public ReturnNode parse() { var ret = (ReturnNode) parseBlock(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); - if( show ) showGraph(); return ret; } @@ -73,7 +80,7 @@ public class Parser { Node n = null; while (!peek('}') && !_lexer.isEOF()) { Node n0 = parseStatement(); - if (n0 != null) n = n0; // Allow null returns from eg showGraph + if (n0 != null) n = n0; // Empty statements can return null }; // Exit scope _scope.pop(); @@ -92,7 +99,6 @@ public class Parser { if (matchx("return") ) return parseReturn(); else if (matchx("int")) return parseDecl(); else if (match ("{" )) return require(parseBlock(),"}"); - else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); } @@ -110,14 +116,7 @@ public class Parser { return new ReturnNode(START, expr).peephole(); } - /** - * Dumps out the node graph - * @return {@code null} - */ - private Node showGraph() { - System.out.println(new GraphVisualizer().generateDotOutput(this)); - return null; - } + /** * Parses an expression statement diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java index 7c1968c5..814b99b8 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -7,8 +7,6 @@ public class AddNode extends Node { @Override public String label() { return "Add"; } - @Override public String glabel() { return "+"; } - @Override StringBuilder _print1(StringBuilder sb) { in(1)._print0(sb.append("(")); diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java index e3c3616a..fc893e27 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -8,8 +8,6 @@ public class DivNode extends Node { @Override public String label() { return "Div"; } - @Override public String glabel() { return "//"; } - @Override StringBuilder _print1(StringBuilder sb) { in(1)._print0(sb.append("(")); diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 0d59ef25..b83c41a5 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -8,8 +8,6 @@ public class MinusNode extends Node { @Override public String label() { return "Minus"; } - @Override public String glabel() { return "-"; } - @Override StringBuilder _print1(StringBuilder sb) { in(1)._print0(sb.append("(-")); diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java index 26c28281..b2b2f9c0 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -8,8 +8,6 @@ public class MulNode extends Node { @Override public String label() { return "Mul"; } - @Override public String glabel() { return "*"; } - @Override StringBuilder _print1(StringBuilder sb) { in(1)._print0(sb.append("(")); diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index 6e4617ff..3922533c 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; + import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; @@ -66,13 +68,9 @@ public abstract class Node { // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" public abstract String label(); - // Unique label for graph visualization, e.g. "Add12" or "Region30" or "EQ99" + // Unique label for debugging, e.g. "Add12" or "Region30" or "EQ99" public String uniqueName() { return label() + _nid; } - // Graphical label, e.g. "+" or "Region" or "==" - public String glabel() { return label(); } - - // ------------------------------------------------------------------------ // Debugger Printing. @@ -211,7 +209,7 @@ public abstract class Node { } // Mostly used for asserts and printing. - boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + public boolean isDead() { return isUnused() && nIns()==0 && _type==null; } /** * We allow disabling peephole opt so that we can observe the * full graph, vs the optimized graph. @@ -229,12 +227,22 @@ public abstract class Node { *
  • we ask the Node for a better replacement (again, none enabled in this chapter)
    • * */ - public final Node peephole( ) { + public final Node peephole() { + var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(this); + Type old = _type; + Node n = peepholeOpt(); + Node rez = n == null ? this : n; + if( obs != null ) obs.after(this, n == null && old == _type ? null : rez, false); + return rez; + } + + private Node peepholeOpt() { // Compute initial or improved Type Type type = _type = compute(); if (_disablePeephole) - return this; // Peephole optimizations turned off + return null; // Peephole optimizations turned off // Replace constant computations from non-constants with a constant node if (!(this instanceof ConstantNode) && type.isConstant()) { @@ -248,8 +256,8 @@ public abstract class Node { Node n = idealize(); if( n != null ) return n; - return this; // No progress - } + return null; // No progress + } /** * This function needs to be diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java index d2e32c61..1d2ddaa0 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -8,8 +8,6 @@ public class SubNode extends Node { @Override public String label() { return "Sub"; } - @Override public String glabel() { return "-"; } - @Override StringBuilder _print1(StringBuilder sb) { in(1)._print0(sb.append("(")); diff --git a/chapter03/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter03/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java new file mode 100644 index 00000000..a615741d --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -0,0 +1,47 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphAdapter; +import com.seaofnodes.graph.GraphSnapshot; +import com.seaofnodes.graph.GraphSnapshot.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.Node; +import java.util.ArrayList; + +/** Chapter 3's view of the IR; browser, transport and layout are shared. */ +public class SimpleGraphAdapter extends GraphAdapter { + @Override protected boolean dead(Node n) { return n.isDead(); } + @Override protected int id(Node n) { return n._nid; } + @Override protected int nIns(Node n) { return n.nIns(); } + @Override protected Node in(Node n, int idx) { return n.in(idx); } + @Override protected int nOuts(Node n) { return n.nOuts(); } + @Override protected Node out(Node n, int idx) { return n.out(idx); } + + private ArrayList edges(Node n) { + var edges = new ArrayList(); + String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null; + for( int i = 0; i < n.nIns(); i++ ) { + String name = names == null || i >= names.length ? null : names[i]; + edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); + } + return edges; + } + + @Override protected GraphSnapshot.Node desc(Node n) { + Projection proj = null; + String label = n.label(); + return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label, + n._type == null ? null : n._type.toString(), kind(n), edges(n), proj); + } + + private Kind kind(Node n) { + if( n instanceof ScopeNode ) return Kind.SCOPE; + if( n instanceof StartNode ) return Kind.CTRL; + return n.isCFG() ? Kind.CTRL : Kind.DATA; + } + + private Role role(Node n, int i) { + if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; + if( i == 0 ) return Role.CTRL; + return Role.DATA; + } +} diff --git a/chapter03/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/chapter03/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java new file mode 100644 index 00000000..0e24e15d --- /dev/null +++ b/chapter03/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -0,0 +1,38 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphCapture; +import com.seaofnodes.graph.GraphViewer; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; +import java.util.ArrayList; +import java.io.IOException; + +/** Chapter 3's compilation context; capture and event bookkeeping are shared. */ +public class SimpleGraphObserver extends GraphCapture { + private Parser _parser; + private Node _ret; + private String _phase; + public SimpleGraphObserver() { super(new SimpleGraphAdapter()); } + public static void main(String[] args) throws IOException { + GraphViewer.run(new SimpleGraphObserver()); + } + @Override protected void compile(String src) { + _parser = new Parser(src); + _parser._obs = this; + _phase = "Parse"; + _ret = _parser.parse(); + phase(_phase); + } + @Override protected String phase() { return _phase; } + @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; } + @Override protected void detach() { + if( _parser != null ) _parser._obs = null; + _parser = null; + _ret = null; + } + @Override protected void roots(ArrayList roots) { + roots.add(Parser.START); + roots.add(_parser._scope); + roots.add(_ret); + } +} diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 60ee8874..9de09d21 100644 --- a/chapter03/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -14,8 +14,6 @@ public class Chapter02Test { Node._disablePeephole = true; // disable peephole so we can observe full graph ReturnNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); Node._disablePeephole = false; } @@ -59,8 +57,6 @@ public class Chapter02Test { Parser parser = new Parser("return 1+2*3+-5;"); ReturnNode ret = parser.parse(); assertEquals("return 2;", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); } } diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 3b8b3449..b42f1433 100644 --- a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -30,7 +30,7 @@ public class Chapter03Test { @Test public void testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c; "); Node._disablePeephole = true; ReturnNode ret = parser.parse(); Node._disablePeephole = false; @@ -39,7 +39,7 @@ public class Chapter03Test { @Test public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); "); ReturnNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } -- cgit v1.2.3