diff options
14 files changed, 79 insertions, 60 deletions
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 79d98792..903a0684 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -32,6 +32,10 @@ public class GraphVisualizer { // 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); @@ -59,7 +63,7 @@ public class GraphVisualizer { 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(); + 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"); @@ -77,7 +81,7 @@ public class GraphVisualizer { } sb.append("<TD PORT=\"p").append(proj._idx).append("\""); if( proj.isCFG() ) sb.append(" BGCOLOR=\"yellow\""); - sb.append(">").append(proj.label()).append("</TD>"); + sb.append(">").append(proj.glabel()).append("</TD>"); } } if (doProjTable) { @@ -93,10 +97,24 @@ public class GraphVisualizer { // 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 "); 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; "); + for( Node phi : region._outputs ) + if( phi instanceof PhiNode ) + sb.append(phi.uniqueName()).append(";"); + sb.append("}\n"); + } + } + sb.append("\t}\n"); // End Node cluster } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index 92b1f0d5..9993c48c 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -86,7 +86,8 @@ public class Parser { private Node ctrl(Node n) { return _scope.ctrl(n); } - public StopNode parse() { + public StopNode parse() { return parse(false); } + public StopNode parse(boolean show) { _allScopes.push(_scope); _scope.push(); try { @@ -98,6 +99,7 @@ public class Parser { finally { _scope.pop(); _allScopes.pop(); + if( show ) showGraph(); } } @@ -135,7 +137,7 @@ public class Parser { else if (matchx("int")) return parseDecl(); else if (match ("{" )) return parseBlock(); else if (matchx("if" )) return parseIf(); - else if (matchx("#showGraph")) return showGraph(); + else if (matchx("#showGraph")) return require(showGraph(),";"); else return parseExpressionStatement(); } @@ -203,7 +205,6 @@ public class Parser { * @return {@code null} */ private Node showGraph() { - require(";"); System.out.println(new GraphVisualizer().generateDotOutput(this)); return null; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java index 1e9cc6c9..e4ed83a6 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -3,12 +3,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; public class AddNode extends Node { - public AddNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - @Override - public String label() { return "Add"; } + @Override public String label() { return "Add"; } + + @Override public String glabel() { return "+"; } @Override StringBuilder _print1(StringBuilder sb) { @@ -87,7 +86,8 @@ public class AddNode extends Node { // Push constant up through the phi: x + (phi con0+con0 con1+con1...) for( int i=1; i<ns.length; i++ ) ns[i] = new AddNode(phi.in(i),t2.isConstant() ? rhs : rhs.in(i)).peephole(); - return new AddNode(lhs.in(1),new PhiNode(ns).peephole()); + String label = phi._label + (rhs instanceof PhiNode rphi ? rphi._label : ""); + return new AddNode(lhs.in(1),new PhiNode(label,ns).peephole()); } // Now we sort along the spline via rotates, to gather similar things together. diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 250231f9..02eb7ce9 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -16,6 +16,9 @@ abstract public class BoolNode extends Node { public String label() { return getClass().getSimpleName(); } @Override + public String glabel() { return op(); } + + @Override StringBuilder _print1(StringBuilder sb) { in(1)._print0(sb.append("(")); in(2)._print0(sb.append(op())); diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java index 1f562378..ae87deac 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -5,13 +5,12 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class DivNode extends Node { - public DivNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Div"; } + + @Override public String glabel() { return "//"; } - @Override - public String label() { return "Div"; } - @Override StringBuilder _print1(StringBuilder sb) { in(1)._print0(sb.append("(")); diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 04084d0f..834f4c11 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -5,12 +5,11 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MinusNode extends Node { - public MinusNode(Node in) { - super(null, in); - } + public MinusNode(Node in) { super(null, in); } - @Override - public String label() { return "Minus"; } + @Override public String label() { return "Minus"; } + + @Override public String glabel() { return "-"; } @Override StringBuilder _print1(StringBuilder sb) { diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java index e3e83b38..dcc21b2e 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -5,12 +5,11 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class MulNode extends Node { - public MulNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - @Override - public String label() { return "Mul"; } + @Override public String label() { return "Mul"; } + + @Override public String glabel() { return "*"; } @Override StringBuilder _print1(StringBuilder sb) { diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 28d054a6..fe3fddf8 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -4,8 +4,6 @@ import com.seaofnodes.simple.type.Type; public abstract class MultiNode extends Node { - public MultiNode(Node... inputs) { - super(inputs); - } + public MultiNode(Node... inputs) { super(inputs); } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java index dc4d7a33..e34b4cd5 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java @@ -62,10 +62,15 @@ public abstract class Node { n._outputs.add( this ); } + // 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" public String uniqueName() { return label() + _nid; } + // Graphical label, e.g. "+" or "Region" or "==" + public String glabel() { return label(); } + @Override public final String toString() { // TODO: This needs a lot of work diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8e0c9a79..5eb110e7 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -5,14 +5,13 @@ import com.seaofnodes.simple.type.TypeBot; public class PhiNode extends Node { - public PhiNode(Node... inputs) { - super(inputs); - } + final String _label; + + public PhiNode(String label, Node... inputs) { super(inputs); _label = label; } - @Override - public String label() { - return "Phi"; - } + @Override public String label() { return "Phi_"+_label; } + + @Override public String glabel() { return "φ_"+_label; } @Override StringBuilder _print1(StringBuilder sb) { @@ -48,8 +47,8 @@ public class PhiNode extends Node { lhss[i] = in(i).in(1); rhss[i] = in(i).in(2); } - Node phi_lhs = new PhiNode(lhss).peephole(); - Node phi_rhs = new PhiNode(rhss).peephole(); + Node phi_lhs = new PhiNode(_label,lhss).peephole(); + Node phi_rhs = new PhiNode(_label,rhss).peephole(); return op.copy(phi_lhs,phi_rhs); } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java index d29cbd57..ae8724b9 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -4,14 +4,10 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeControl; public class RegionNode extends Node { - public RegionNode(Node... inputs) { - super(inputs); - } + public RegionNode(Node... inputs) { super(inputs); } @Override - public String label() { - return "Region"; - } + public String label() { return "Region"; } @Override StringBuilder _print1(StringBuilder sb) { 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 b3cca3da..b854c627 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -18,8 +18,10 @@ public class ScopeNode extends Node { */ public final Stack<HashMap<String, Integer>> _scopes = new Stack<>(); - @Override - public String label() { return "Scope"; } + // Reverse lookup for nicer graph printing + private final ArrayList<String> _rlabels = new ArrayList<>(); + + @Override public String label() { return "Scope"; } @Override StringBuilder _print1(StringBuilder sb) { @@ -43,8 +45,7 @@ public class ScopeNode extends Node { @Override public TypeBot compute() { return TypeBot.BOTTOM; } - @Override - public Node idealize() { return null; } + @Override public Node idealize() { return null; } // Add an empty lexical scope public HashMap<String, Integer> push() { @@ -62,6 +63,7 @@ public class ScopeNode extends Node { HashMap<String,Integer> scope = _scopes.lastElement(); if( scope.put(name,nIns()) != null ) return null; // Double define + _rlabels.add(name); return add_def(n); } @@ -105,9 +107,10 @@ public class ScopeNode extends Node { public ScopeNode dup() { ScopeNode dup = new ScopeNode(); for( HashMap<String, Integer> tab : _scopes ) - dup._scopes.push(new HashMap<String, Integer>(tab)); + dup._scopes.push(new HashMap<>(tab)); for( int i=0; i<nIns(); i++ ) dup.add_def(in(i)); + dup._rlabels.addAll(_rlabels); return dup; } @@ -115,7 +118,7 @@ public class ScopeNode extends Node { RegionNode r = (RegionNode)ctrl(new RegionNode(ctrl(), that.ctrl()).peephole()); for( int i=1; i<nIns(); i++ ) if( in(1) != that.in(i) ) // No need for redundant Phis - set_def(i,new PhiNode(r, in(i), that.in(i)).peephole()); + set_def(i,new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole()); that.kill(); // Kill merged scope return r; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java index e5939e1b..42ddc1c1 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -5,12 +5,11 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeInteger; public class SubNode extends Node { - public SubNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } - @Override - public String label() { return "Sub"; } + @Override public String label() { return "Sub"; } + + @Override public String glabel() { return "-"; } @Override StringBuilder _print1(StringBuilder sb) { diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index a4bf89ec..cd350db5 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -51,15 +51,15 @@ return c; @Test public void testChapter5IfMergeB() { - Parser parser = new Parser("int a=arg+1; int b=0; if( arg==1 ) b=a; else b=a+1; return a+b; #showGraph;"); - StopNode ret = parser.parse(); + Parser parser = new Parser("int a=arg+1; int b=0; if( arg==1 ) b=a; else b=a+1; return a+b;"); + StopNode ret = parser.parse(true); assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); } @Test public void testChapter5IfMerge2() { - Parser parser = new Parser("int a=arg+1; int b=arg+2; if( arg==1 ) b=b+a; else a=b+1; return a+b; #showGraph;"); - StopNode ret = parser.parse(); + Parser parser = new Parser("int a=arg+1; int b=arg+2; if( arg==1 ) b=b+a; else a=b+1; return a+b;"); + StopNode ret = parser.parse(true); assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString()); } |