diff options
Diffstat (limited to 'chapter16/src')
34 files changed, 152 insertions, 383 deletions
diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java deleted file mode 100644 index de6d65a3..00000000 --- a/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ /dev/null @@ -1,288 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; - -import java.util.*; - -import static com.seaofnodes.simple.Utils.TODO; - -/** - * 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 { - - /** - * 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 parse) { return generateDotOutput(parse.STOP,parse._scope,parse._xScopes); } - public String generateDotOutput(StopNode stop, Node scope, Stack<ScopeNode> xScopes) { - - // Since the graph has cycles, we need to create a flat list of all the - // nodes in the graph. - Collection<Node> all = findAll(stop, scope); - StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter11 {\n"); - sb.append("/*\n"); - sb.append(stop._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 - - // CNC - turned off Apr/8/2024, gives more flex in the layout and - // removes some of the more ludicrous layout choices. - // 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"); - - // 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 - if( xScopes != null ) - for( ScopeNode xscope : xScopes ) - if( !xscope.isDead() ) - scope( sb, xscope ); - - // Walk the Node edges - nodeEdges(sb, all); - - // Walk the active Scope edges - if( xScopes != null ) - for( ScopeNode xscope : xScopes ) - if( !xscope.isDead() ) - scopeEdges( sb, xscope ); - - sb.append("}\n"); - return sb.toString(); - } - - 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(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 CProjNode || n instanceof ScopeMinNode || n==Parser.XCTRL) - continue; // Do not emit, rolled into MultiNode or Scope cluster already - if( _separateControlCluster && doCtrl && !(n instanceof CFGNode) ) continue; - if( _separateControlCluster && !doCtrl && (n instanceof CFGNode) ) continue; - sb.append("\t\t").append(n.uniqueName()).append(" [ "); - String lab = n.glabel(); - 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; - n._outputs.sort((x,y) -> x instanceof ProjNode xp && y instanceof ProjNode yp ? (xp._idx - yp._idx) : (x._nid - y._nid)); - for (Node use : n._outputs) { - if (use instanceof ProjNode proj) { - if (!doProjTable) { - doProjTable = true; - sb.append("<TD>").append("\n"); - sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n"); - sb.append("\t\t\t\t<TR>"); - } - sb.append("<TD PORT=\"p").append(proj._idx).append("\">").append(proj.glabel()).append("</TD>"); - } - if (use instanceof CProjNode proj) { - if (!doProjTable) { - doProjTable = true; - sb.append("<TD>").append("\n"); - sb.append("\t\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">").append("\n"); - sb.append("\t\t\t\t<TR>"); - } - sb.append("<TD PORT=\"p").append(proj._idx).append("\" BGCOLOR=\"yellow\">").append(proj.glabel()).append("</TD>"); - } - } - if (doProjTable) { - sb.append("</TR>").append("\n"); - sb.append("\t\t\t\t</TABLE>").append("\n"); - sb.append("\t\t\t</TD>"); - } - 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 - if( n instanceof CFGNode ) 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"); - } - 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 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 last = scope.nIns(); - int max = scope._lexSize.size(); - for( int i = 0; i < max; i++ ) { - int level = max-i-1; - String scopeName = makeScopeName(scope, level); - sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name - // Special for memory ScopeMinNode - if( level==0 ) { - ScopeMinNode n = scope.mem(); - sb.append("\t\t").append(n.uniqueName()).append(" [label=\"").append(n.glabel()).append("\"];\n"); - } - 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>"); - int lexStart=scope._lexSize.at(level); - for( int j=lexStart; j<last; j++ ) { - var v = scope._vars.at(j); - sb.append("<TD PORT=\"").append(makePortName(scopeName, v._name)).append("\">").append(v._name).append("</TD>"); - } - last = lexStart; - sb.append("</TR>\n"); - sb.append("\t\t\t</TABLE>>];\n"); - } - // 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( max ) ); // 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<Node> all) { - // All them edge labels - sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); - for( Node n : all ) { - // Do not display the Constant->Start edge; - // ProjNodes handled by Multi; - // ScopeNodes are done separately - if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL ) - continue; - 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()); - sb.append(" -> "); - sb.append(def.uniqueName()); - sb.append(" [style=dotted taillabel=").append(i).append("];\n"); - } else if( def != null ) { - // Most edges land here use->def - sb.append('\t').append(n.uniqueName()).append(" -> "); - if( def instanceof CProjNode proj ) { - String mname = proj.ctrl().uniqueName(); - sb.append(mname).append(":p").append(proj._idx); - } else if( def instanceof ProjNode proj ) { - String mname = proj.in(0).uniqueName(); - sb.append(mname).append(":p").append(proj._idx); - } else sb.append(def.uniqueName()); - // Number edges, so we can see how they track - sb.append("[taillabel=").append(i); - // The edge from New to ctrl is just for anchoring the New - if ( n instanceof NewNode ) - sb.append(" color=green"); - // control edges are colored red - else if( def instanceof CFGNode ) - sb.append(" color=red"); - else if( def.isMem() ) - sb.append(" color=blue"); - // Backedges do not add a ranking constraint - if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) ) - sb.append(" constraint=false"); - sb.append("];\n"); - } - } - } - } - - // Walk the scope edges - private void scopeEdges( StringBuilder sb, ScopeNode scope ) { - sb.append("\tedge [style=dashed color=cornflowerblue];\n"); - int level=0; - for( var v : scope._vars ) { - Node def = scope.in(v._idx); - while( def instanceof ScopeNode lazy ) - def = lazy.in(v._idx); - if( def==null ) continue; - while( level < scope._lexSize.size() && v._idx >= scope._lexSize.at(level) ) - level++; - String scopeName = makeScopeName(scope, level-1); - sb.append("\t") - .append(scopeName).append(":") - .append('"').append(makePortName(scopeName, v._name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted - .append(" -> "); - if( def instanceof CProjNode proj ) { - sb.append(def.in(0).uniqueName()).append(":p").append(proj._idx); - } else if( def instanceof ProjNode proj ) { - sb.append(def.in(0).uniqueName()).append(":p").append(proj._idx); - } else sb.append(def.uniqueName()); - sb.append(";\n"); - } - } - - /** - * Finds all nodes in the graph. - */ - private Collection<Node> findAll(Node stop, Node scope) { - final HashMap<Integer, Node> all = new HashMap<>(); - for( Node n : stop._inputs ) - walk(all, n); - if( scope != null ) - for( Node n : scope._inputs ) - walk(all, n); - return all.values(); - } - - /** - * Walk a subgraph and populate distinct nodes in the all list. - */ - private void walk(HashMap<Integer,Node> 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) - walk(all, c); - for( Node c : n._outputs ) - walk(all, c); - } -} diff --git a/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java index 96ae350e..cabc4a15 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -65,9 +65,14 @@ public abstract class IterPeeps { while( (n=WORK.pop()) != null ) { if( n.isDead() ) continue; cnt++; // Useful for debugging, searching which peephole broke things + var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(n); Node x = n.peepholeOpt(); if( x != null ) { - if( x.isDead() ) continue; + if( x.isDead() ) { + if( obs != null ) obs.after(n, x, true); + continue; + } // peepholeOpt can return brand-new nodes, needing an initial type set if( x._type==null ) x.setType(x.compute()); // Changes require neighbors onto the worklist @@ -90,6 +95,7 @@ public abstract class IterPeeps { } if( n.isUnused() && !(n instanceof StopNode) ) n.kill(); // Just plain dead + if( obs != null ) obs.after(n, x, true); } return stop; diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java index a8064e17..b52767cc 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter16/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.*; import static com.seaofnodes.simple.Utils.TODO; @@ -15,6 +17,12 @@ import java.util.*; */ public class Parser { + // Current compilation context; the observer belongs to the parser. + public static Parser PARSER; + public GraphObserver<Node> _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 @@ -103,6 +111,7 @@ public class Parser { public Parser(String source, TypeInteger arg) { + PARSER = this; Node.reset(); IterPeeps.reset(); SCHEDULED = false; @@ -150,8 +159,7 @@ public class Parser { private Node ctrl() { return _scope.ctrl(); } private Node ctrl(Node n) { return _scope.ctrl(n); } - public StopNode parse() { return parse(false); } - public StopNode parse(boolean show) { + public StopNode parse() { _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); @@ -174,7 +182,6 @@ public class Parser { INITS.clear(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); STOP.peephole(); - if( show ) showGraph(); return STOP; } @@ -214,7 +221,6 @@ public class Parser { else if (matchx("break") ) return parseBreak(); else if (matchx("continue")) return parseContinue(); else if (matchx("struct") ) return parseStruct(); - else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";") ) return null; // Empty statement // declarations of vars with struct type are handled in parseExpressionStatement due // to ambiguity @@ -394,14 +400,7 @@ public class Parser { return ret; } - /** - * Dumps out the node graph - * @return {@code null} - */ - Node showGraph() { - System.out.println(new GraphVisualizer().generateDotOutput(STOP,_scope,_xScopes)); - return null; - } + /** Parse: name [=expr] */ diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/AddFNode.java index 7d4e2910..5d0a473a 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -10,8 +10,6 @@ public class AddFNode extends Node { @Override public String label() { return "AddF"; } - @Override public String glabel() { return "+"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/AddNode.java index 97d2bb9b..e0d3d204 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -9,8 +9,6 @@ public class AddNode extends Node { @Override public String label() { return "Add"; } - @Override public String glabel() { return "+"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/AndNode.java index 17a4e0ca..8ab44858 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -10,8 +10,6 @@ public class AndNode extends Node { @Override public String label() { return "And"; } - @Override public String glabel() { return "&"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 06c10a79..5d2212b0 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -22,9 +22,6 @@ abstract public class BoolNode extends Node { public String label() { return getClass().getSimpleName(); } @Override - public String glabel() { return op(); } - - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); in(2)._print0(sb.append(op()), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 36fd4524..6c0c2eb3 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -10,8 +10,6 @@ public class DivFNode extends Node { @Override public String label() { return "DivF"; } - @Override public String glabel() { return "/"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/DivNode.java index 76e98678..d13dcacf 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -10,8 +10,6 @@ public class DivNode extends Node { @Override public String label() { return "Div"; } - @Override public String glabel() { return "//"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java index d15d4f83..60be3baa 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -23,11 +23,8 @@ public class LoadNode extends MemOpNode { super(name, alias, glb, mem, ptr, off); } - // GraphVis DOT code (must be valid Java identifiers) and debugger labels + // Debugger label @Override public String label() { return "ld_"+mlabel(); } - // GraphVis node-internal labels - @Override public String glabel() { return "." +_name; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/MinusFNode.java index 9727f58b..7cacf2c9 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -10,8 +10,6 @@ public class MinusFNode extends Node { @Override public String label() { return "MinusF"; } - @Override public String glabel() { return "-"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("(-"), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 8a2c9406..7e95088f 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -10,8 +10,6 @@ public class MinusNode extends Node { @Override public String label() { return "Minus"; } - @Override public String glabel() { return "-"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("(-"), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 2d44a9fb..4b753ba7 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -10,8 +10,6 @@ public class MulFNode extends Node { @Override public String label() { return "MulF"; } - @Override public String glabel() { return "*"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/MulNode.java index 949af27a..65898907 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -10,8 +10,6 @@ public class MulNode extends Node { @Override public String label() { return "Mul"; } - @Override public String glabel() { return "*"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java index ddb1e09a..77800be2 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -32,12 +32,8 @@ public class NewNode extends Node implements MultiNode { } @Override public String label() { - return "new_"+glabel(); + return "new_"+(_ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str()); } - @Override public String glabel() { - return _ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str(); - } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("new "); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java index daf5994c..31db0f9f 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter16/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.Ary; import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.IterPeeps; @@ -72,17 +74,11 @@ public abstract class Node implements OutNode { // 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() { - // Get rid of $ as graphviz doesn't like it - String label = label().replaceAll("\\$", ""); - return label + _nid; + return label() + _nid; } - // Graphical label, e.g. "+" or "Region" or "==" - public String glabel() { return label(); } - - // ------------------------------------------------------------------------ // Debugger Printing. @@ -292,13 +288,14 @@ public abstract class Node implements OutNode { * Try to peephole at this node and return a better replacement Node. * Always returns some not-null Node (often this). */ - public final Node peephole( ) { - if (_disablePeephole) { - _type = compute(); - return this; // Peephole optimizations turned off - } + public final Node peephole() { + if( _disablePeephole ) { _type = compute(); return this; } + var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(this); Node n = peepholeOpt(); - return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress + Node rez = n == null ? this : deadCodeElim(n.peephole()); + if( obs != null ) obs.after(this, n == null ? null : rez, false); + return rez; } /** @@ -456,6 +453,8 @@ public abstract class Node implements OutNode { // retry the peephole. Track a set of Nodes dependent on `this`, and // revisit them if `this` changes. Ary<Node> _deps; + public int nDeps() { return _deps == null ? 0 : _deps.size(); } + public Node dep(int idx) { return _deps.get(idx); } /** * Add a node to the list of dependencies. Only add it if its not an input @@ -466,6 +465,8 @@ public abstract class Node implements OutNode { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( IterPeeps.midAssert() ) return this; + var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.dep(this, dep); if( _deps==null ) _deps = new Ary<>(Node.class); if( _deps .find(dep) != -1 ) return this; // Already on list if( _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/NotNode.java index ffd3e01e..9e4cc324 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -9,8 +9,6 @@ public class NotNode extends Node { @Override public String label() { return "Not"; } - @Override public String glabel() { return "!"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("(!"), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/OrNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/OrNode.java index b572346f..301514f4 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -10,8 +10,6 @@ public class OrNode extends Node { @Override public String label() { return "Or"; } - @Override public String glabel() { return "|"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6cd9efb0..f533a7a4 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -18,8 +18,6 @@ public class PhiNode extends Node { @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } - @Override public String glabel() { return "φ_"+_label; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { if( !(region() instanceof RegionNode r) || r.inProgress() ) diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java b/chapter16/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java index 44d3a587..3dd7cbf0 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java @@ -10,8 +10,6 @@ public class RoundF32Node extends Node { @Override public String label() { return "RoundF32"; } - @Override public String glabel() { return "(f32)"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return in(1)._print0(sb.append("((f32)"), visited).append(")"); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/SarNode.java index 5dc26ad3..25ef55e3 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -10,8 +10,6 @@ public class SarNode extends Node { @Override public String label() { return "Sar"; } - @Override public String glabel() { return ">>"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ShlNode.java index b67d985a..1f558b8f 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -10,8 +10,6 @@ public class ShlNode extends Node { @Override public String label() { return "Shl"; } - @Override public String glabel() { return "<<"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 22eb45a0..e8ae2c1c 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -10,8 +10,6 @@ public class ShrNode extends Node { @Override public String label() { return "Shr"; } - @Override public String glabel() { return ">>>"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StopNode.java index d5b00011..aed4a8e6 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.GlobalCodeMotion; -import com.seaofnodes.simple.GraphVisualizer; import java.util.BitSet; @@ -69,18 +68,16 @@ public class StopNode extends CFGNode { return addDef(node); } - public StopNode iterate( ) { return IterPeeps.iterate(this).typeCheck().GCM(false); } - public StopNode iterate(boolean show) { return IterPeeps.iterate(this).typeCheck().GCM(show ); } + public StopNode iterate() { return IterPeeps.iterate(this).typeCheck().GCM(); } StopNode typeCheck() { String err = walk( Node::err ); if( err != null ) throw new RuntimeException(err); return this; } - StopNode GCM(boolean show) { + StopNode GCM() { // Break infinite loops, forcing a Never-branch to exit GlobalCodeMotion.fixLoops(this); - if( show ) - System.out.println(new GraphVisualizer().generateDotOutput(this,null,null)); + GlobalCodeMotion.buildCFG(this); return this; } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 7b1bddd5..efa4dba5 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -25,10 +25,8 @@ public class StoreNode extends MemOpNode { _init = init; } - // GraphVis DOT code and debugger labels + // Debugger label @Override public String label() { return "st_"+mlabel(); } - // GraphVis node-internal labels - @Override public String glabel() { return "." +_name+"="; } @Override public boolean isMem() { return true; } public Node val() { return in(4); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/SubFNode.java index b591718d..27bbda8d 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -10,8 +10,6 @@ public class SubFNode extends Node { @Override public String label() { return "SubF"; } - @Override public String glabel() { return "-"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/SubNode.java index 009fb30e..9eb30089 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -11,8 +11,6 @@ public class SubNode extends Node { @Override public String label() { return "Sub"; } - @Override public String glabel() { return "-"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index 1d147cf6..fde483d6 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -11,8 +11,6 @@ public class ToFloatNode extends Node { @Override public String label() { return "ToFloat"; } - @Override public String glabel() { return "(flt)"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return in(1)._print0(sb.append("(flt)"), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/XorNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/XorNode.java index 191933f9..71dce586 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -10,8 +10,6 @@ public class XorNode extends Node { @Override public String label() { return "Xor"; } - @Override public String glabel() { return "^"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter16/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java new file mode 100644 index 00000000..6d281535 --- /dev/null +++ b/chapter16/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -0,0 +1,63 @@ +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 com.seaofnodes.simple.type.TypeMem; +import java.util.ArrayList; + +/** Chapter 16's view of the IR; browser, transport and layout are shared. */ +public class SimpleGraphAdapter extends GraphAdapter<Node> { + @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); } + @Override protected int nDeps(Node n) { return n.nDeps(); } + @Override protected Node dep(Node n, int idx) { return n.dep(idx); } + + private ArrayList<Edge> edges(Node n) { + var edges = new ArrayList<Edge>(); + for( int i = 0; i < n.nIns(); i++ ) { + String name = n instanceof ScopeNode scope && i < scope._vars.size() + ? scope._vars.get(i)._name : null; + edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); + } + return edges; + } + + @Override protected GraphSnapshot.Node desc(Node n) { + Projection proj = n instanceof ProjNode p ? new Projection(ref(n.in(0)), p._idx) + : n instanceof CProjNode p ? new Projection(ref(n.in(0)), p._idx) : 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; + if( n instanceof LoopNode ) return Kind.LOOP; + if( n instanceof RegionNode ) return Kind.REGION; + if( n instanceof PhiNode ) return Kind.PHI; + return n instanceof CFGNode ? Kind.CTRL : isMem(n) ? Kind.MEM : Kind.DATA; + } + + private Role role(Node n, int i) { + if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof XCtrlNode ) return Role.ASSOC; + if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof ProjNode || n instanceof CProjNode ) + return n instanceof CFGNode ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; + if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; + if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM; + Node def = n.in(i); + if( def != null && isMem(def) ) return Role.MEM; + return Role.DATA; + } + + private boolean isMem(Node n) { return n.isMem() || n._type instanceof TypeMem; } +} diff --git a/chapter16/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/chapter16/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java new file mode 100644 index 00000000..8ca8f7ad --- /dev/null +++ b/chapter16/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -0,0 +1,43 @@ +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 16's compilation context; capture and event bookkeeping are shared. */ +public class SimpleGraphObserver extends GraphCapture<Node> { + 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); + _phase = "Iter"; + com.seaofnodes.simple.IterPeeps.iterate(_parser.STOP); + 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<Node> roots) { + roots.add(Parser.START); + roots.add(_parser.STOP); + roots.add(_parser._scope); + roots.addAll(_parser._xScopes); + roots.add(_ret); + } +} diff --git a/chapter16/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter16/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index d5ffe835..29ef8732 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -74,7 +74,7 @@ while (pc < program#) { } return output; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("Hello World!\n", Evaluator.evaluate(stop, 0, 10000).toString()); } } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java index a40dbe90..2b07234f 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -81,7 +81,7 @@ if( (arg/13)==0 ) { int r = g+h; return p-r; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 0;", stop.toString()); } @@ -101,7 +101,7 @@ bar.a = 1; bar.a = 2; return bar.a; """); - StopNode stop = parser.parse(false).iterate(); + StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); } @@ -117,7 +117,7 @@ else v.y = 3; return v; """); - StopNode stop = parser.parse(false).iterate(); + StopNode stop = parser.parse().iterate(); assertEquals("return Vector2D;", stop.toString()); } @@ -207,7 +207,7 @@ if (arg) bar = null; if( bar ) bar.a = 1; return bar; """); - StopNode stop = parser.parse(false).iterate(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region38,(*void)Phi(Region24,null,Bar),null);", stop.toString()); } @@ -223,7 +223,7 @@ if( !bar ) rez=4; else bar.a = 1; return rez; """); - StopNode stop = parser.parse(false).iterate(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region44,4,3);", stop.toString()); } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 73fff8fd..aa496030 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -189,7 +189,7 @@ p2.pi.i = 2; if (arg) p1 = new P; return p1.pi.i + 1; """); - try { parser.parse(false).iterate(); fail(); } + try { parser.parse().iterate(); fail(); } catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } } |