diff options
Diffstat (limited to 'chapter05')
20 files changed, 78 insertions, 148 deletions
diff --git a/chapter05/pom.xml b/chapter05/pom.xml index d952e5ca..75f352a3 100644 --- a/chapter05/pom.xml +++ b/chapter05/pom.xml @@ -13,5 +13,6 @@ <name>Chapter 5</name> <properties> <simple.graph.directory>${project.basedir}/../graph</simple.graph.directory> + <simple.print.directory>${project.basedir}/../print</simple.print.directory> </properties> </project> 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 2772c4c5..367cb2c0 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.*; public class AddNode extends Node { @@ -7,12 +8,7 @@ public class AddNode extends Node { @Override public String label() { return "Add"; } - @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("+")); - return sb.append(")"); - } + @Override protected String format() { return "(%1+%2)"; } @Override 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 87acc6cc..aaf261d5 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -14,11 +16,8 @@ abstract public class BoolNode extends Node { @Override public String label() { return getClass().getSimpleName(); } - @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append(op())); - return sb.append(")"); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.open().n(in(1)).p(op()).n(in(2)).close(); } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 85277d82..5efe29b7 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; @@ -22,15 +24,16 @@ public class ConstantNode extends Node { _con = type; } - @Override - public String label() { return ""+_con; } + @Override protected String repeatName() { + return _con==null || _con.toString().length()<=32 ? null : uniqueName(); + } @Override - public String uniqueName() { return "Con_" + _nid; } + public String label() { return "Con"; } - @Override - StringBuilder _print1(StringBuilder sb) { - return _con.print(sb); + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(_con); } @Override 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 f80f092d..f6b4e03e 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -8,12 +9,7 @@ public class DivNode extends Node { @Override public String label() { return "Div"; } - @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("/")); - return sb.append(")"); - } + @Override protected String format() { return "(%1/%2)"; } @Override public Type compute() { diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java index 6124b893..3b644bec 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; @@ -13,11 +14,7 @@ public class IfNode extends MultiNode { @Override public String label() { return "If"; } - @Override - StringBuilder _print1(StringBuilder sb) { - sb.append("if( "); - return in(1)._print0(sb).append(" )"); - } + @Override protected String format() { return "if( %1 )"; } @Override public boolean isCFG() { return true; } 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 ad6e513a..bb5f155d 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -8,11 +9,7 @@ public class MinusNode extends Node { @Override public String label() { return "Minus"; } - @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(-")); - return sb.append(")"); - } + @Override protected String format() { return "(-%1)"; } @Override public Type compute() { 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 b1d9e44a..a881bd96 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -8,12 +9,7 @@ public class MulNode extends Node { @Override public String label() { return "Mul"; } - @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("*")); - return sb.append(")"); - } + @Override protected String format() { return "(%1*%2)"; } @Override public Type compute() { 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 e17d7b9a..72469ad2 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.BaseNode; + import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; @@ -10,14 +12,7 @@ import java.util.*; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node { - - /** - * Each node has a unique dense Node ID within a compilation context - * The ID is useful for debugging, for using as an offset in a bitvector, - * as well as for computing equality of nodes (to be implemented later). - */ - public final int _nid; +public abstract class Node extends BaseNode<Node> { /** * Inputs to the node. These are use-def references to Nodes. @@ -39,7 +34,6 @@ public abstract class Node { */ public final ArrayList<Node> _outputs; - /** * Current computed type for this Node. This value changes as the graph * changes and more knowledge is gained about the program. @@ -54,7 +48,7 @@ public abstract class Node { private static int UNIQUE_ID = 1; protected Node(Node... inputs) { - _nid = UNIQUE_ID++; // allocate unique dense ID + super(UNIQUE_ID++); // allocate unique dense ID _inputs = new ArrayList<>(); Collections.addAll(_inputs,inputs); _outputs = new ArrayList<>(); @@ -66,36 +60,7 @@ public abstract class Node { // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" public abstract String label(); - // Unique label for debugging, e.g. "Add12" or "Region30" or "EQ99" - public String uniqueName() { return label() + _nid; } - - // ------------------------------------------------------------------------ - - // Debugger Printing. - - // {@code toString} is what you get in the debugger. It has to print 1 - // line (because this is what a debugger typically displays by default) and - // has to be robust with broken graph/nodes. - @Override - public final String toString() { return print(); } - - // This is a *deep* print. This version will fail on cycles, which we will - // correct later when we can parse programs with loops. We print with a - // tik-tok style; the common _print0 calls the per-Node _print1, which - // calls back to _print0; - public final String print() { - return _print0(new StringBuilder()).toString(); - } - // This is the common print: check for DEAD and print "DEAD" else call the - // per-Node print1. - final StringBuilder _print0(StringBuilder sb) { - return isDead() - ? sb.append(uniqueName()).append(":DEAD") - : _print1(sb); - } - // Every Node implements this. - abstract StringBuilder _print1(StringBuilder sb); - + @Override public String typeName() { return _type==null ? null : _type.toString(); } /** * Gets the ith input node @@ -112,8 +77,6 @@ public abstract class Node { public boolean isUnused() { return nOuts() == 0; } - public boolean isCFG() { return false; } - /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing * the corresponding <em>use->def</em> edge. This may make the original @@ -334,7 +297,6 @@ public abstract class Node { */ public abstract Node idealize(); - // ------------------------------------------------------------------------ // Peephole utilities diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java index 6a56ff64..a9781ce1 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -8,11 +9,7 @@ public class NotNode extends Node { @Override public String label() { return "Not"; } - @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(!")); - return sb.append(")"); - } + @Override protected String format() { return "(!%1)"; } @Override public Type compute() { 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 b3b5462d..da3917c7 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; public class PhiNode extends Node { @@ -11,13 +13,11 @@ public class PhiNode extends Node { @Override public String label() { return "Phi_"+_label; } @Override - StringBuilder _print1(StringBuilder sb) { - sb.append("Phi("); + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + p.p("Phi("); for( Node in : _inputs ) - in._print0(sb).append(","); - sb.setLength(sb.length()-1); - sb.append(")"); - return sb; + p.n(in).p(","); + return p.unchar(',').close(); } Node region() { return in(0); } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 2826d192..8917fbd4 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; @@ -21,7 +23,7 @@ public class ProjNode extends Node { public String label() { return _label; } @Override - StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_label); } @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } 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 5d520d65..e29254ad 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; public class RegionNode extends Node { @@ -8,9 +10,8 @@ public class RegionNode extends Node { @Override public String label() { return "Region"; } - @Override - StringBuilder _print1(StringBuilder sb) { - return sb.append(label()).append(_nid); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(label()).p(_nid); } @Override public boolean isCFG() { return true; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c9d6c9c8..c5dc532d 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.*; /** @@ -24,8 +26,8 @@ public class ReturnNode extends Node { public String label() { return "Return"; } @Override - StringBuilder _print1(StringBuilder sb) { - return expr()._print0(sb.append("return ")).append(";"); + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p("return ").n(expr()).p(";"); } @Override public boolean isCFG() { return true; } 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 32045fbc..90b97bae 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import java.util.*; @@ -33,22 +35,22 @@ public class ScopeNode extends Node { @Override public String label() { return "Scope"; } @Override - StringBuilder _print1(StringBuilder sb) { - sb.append(label()); + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + p.p(label()); for( HashMap<String,Integer> scope : _scopes ) { - sb.append("["); + p.p("["); boolean first=true; for( String name : scope.keySet() ) { - if( !first ) sb.append(", "); + if( !first ) p.p(", "); first=false; - sb.append(name).append(":"); + p.p(name).p(":"); Node n = in(scope.get(name)); - if( n==null ) sb.append("null"); - else n._print0(sb); + if( n==null ) p.p("null"); + else p.n(n); } - sb.append("]"); + p.p("]"); } - return sb; + return p; } /** diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java index 022e276d..c9f53abd 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; @@ -23,9 +25,8 @@ public class StartNode extends MultiNode { @Override public String label() { return "Start"; } - @Override - StringBuilder _print1(StringBuilder sb) { - return sb.append(label()); + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(label()); } @Override public boolean isCFG() { return true; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java index a30256f9..9ae0acb4 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.type.Type; public class StopNode extends Node { @@ -13,12 +15,12 @@ public class StopNode extends Node { } @Override - StringBuilder _print1(StringBuilder sb) { - if( ret()!=null ) return ret()._print0(sb); - sb.append("Stop[ "); + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + if( ret()!=null ) return p.n(ret()); + p.p("Stop[ "); for( Node ret : _inputs ) - ret._print0(sb).append(" "); - return sb.append("]"); + p.n(ret).p(" "); + return p.p("]"); } @Override public boolean isCFG() { return true; } 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 bd43bc6c..7a6e1a4b 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; + import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; @@ -8,12 +9,7 @@ public class SubNode extends Node { @Override public String label() { return "Sub"; } - @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("-")); - return sb.append(")"); - } + @Override protected String format() { return "(%1-%2)"; } @Override public Type compute() { diff --git a/chapter05/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter05/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 0c2ac4b0..930d5376 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -1,39 +1,19 @@ 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 5'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); } - private ArrayList<Edge> edges(Node n) { - var edges = new ArrayList<Edge>(); - 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 String[] edgeNames(Node n) { + return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; } + @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; } - @Override protected GraphSnapshot.Node desc(Node n) { - Projection proj = n instanceof ProjNode 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) { + @Override protected Kind kind(Node n) { if( n instanceof StopNode ) return Kind.STOP; if( n instanceof ScopeNode ) return Kind.SCOPE; if( n instanceof StartNode ) return Kind.CTRL; @@ -42,7 +22,7 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { return n.isCFG() ? Kind.CTRL : Kind.DATA; } - private Role role(Node n, int i) { + @Override protected Role role(Node n, int i) { if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : Role.DATA; if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : Role.DATA; diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 674e2ba9..d6c91a4a 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -78,7 +78,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse(); - assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString()); + assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @Test |