diff options
Diffstat (limited to 'chapter04/src/main/java')
17 files changed, 259 insertions, 181 deletions
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index f73bfd3c..f624cbde 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeControl; import java.util.*; @@ -29,6 +28,13 @@ public class GraphVisualizer { // 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); @@ -51,10 +57,10 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for( Node n : all ) { - if( n instanceof ProjNode ) - continue; // Do not emit, rolled into MultiNode already + 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"); @@ -71,8 +77,8 @@ public class GraphVisualizer { sb.append("\t\t\t\t<TR>"); } sb.append("<TD PORT=\"p").append(proj._idx).append("\""); - if( proj._idx==0 ) sb.append(" BGCOLOR=\"yellow\""); - sb.append(">").append(proj.label()).append("</TD>"); + if( proj.isCFG() ) sb.append(" BGCOLOR=\"yellow\""); + sb.append(">").append(proj.glabel()).append("</TD>"); } } if (doProjTable) { @@ -86,7 +92,7 @@ public class GraphVisualizer { } else { // control nodes have box shape // other nodes are ellipses, i.e. default shape - if( n instanceof Control ) + if( n.isCFG() ) sb.append("shape=box style=filled fillcolor=yellow "); sb.append("label=\"").append(lab).append("\" "); } @@ -99,8 +105,8 @@ public class GraphVisualizer { sb.append("\tnode [shape=plaintext];\n"); int level=0; for( HashMap<String,Integer> scope : scopenode._scopes ) { - sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name - String scopeName = makeScopeName(level); + 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<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); // Add the scope level @@ -116,31 +122,38 @@ public class GraphVisualizer { // We close them all at once here. sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters } - - private String makeScopeName(int level) { return "scope" + level; } - private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } - private boolean isControlEdge(Node def) { - return def._type instanceof TypeControl; - } + 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 ) { - if( n instanceof ConstantNode || n instanceof ProjNode ) - continue; // Do not display the Constant->Start edge; ProjNodes handled by Multi - for( Node def : n._inputs ) + // Do not display the Constant->Start edge; + // ProjNodes handled by Multi; + // ScopeNodes are done separately + if( n instanceof ConstantNode || n instanceof ProjNode || 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(" -> "); if( def instanceof ProjNode proj ) { String mname = proj.ctrl().uniqueName(); sb.append(mname).append(":p").append(proj._idx); } else sb.append(def.uniqueName()); - // Control edges are colored red - if( isControlEdge(def) ) - sb.append(" [color=red]"); - sb.append(";\n"); + // Number edges, so we can see how they track + sb.append("[taillabel=").append(i); + // control edges are colored red + if( def.isCFG() ) + sb.append(" color=red"); + sb.append("];\n"); } + i++; + } } } @@ -149,7 +162,7 @@ public class GraphVisualizer { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=0; for( HashMap<String,Integer> scope : scopenode._scopes ) { - String scopeName = makeScopeName(level); + String scopeName = makeScopeName(scopenode, level); for( String name : scope.keySet() ) { Node def = scopenode.in(scope.get(name)); if( def==null ) continue; diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java index 275a4ebd..b505c2c5 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java @@ -15,6 +15,12 @@ import java.util.*; public class Parser { /** + * The control is a name that binds to the currently active control + * node in the graph + */ + public static final String CTRL = "$ctrl"; + + /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode * through the entire parser and optimizer. @@ -23,6 +29,7 @@ public class Parser { */ public static StartNode START; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** @@ -31,10 +38,19 @@ public class Parser { */ public ScopeNode _scope; + /** + * List of keywords disallowed as identifiers + */ + private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("int"); + add("return"); + }}; + + public Parser(String source, TypeInteger arg) { _lexer = new Lexer(source); - _scope = new ScopeNode(); Node.reset(); + _scope = new ScopeNode(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); START.peephole(); } @@ -45,17 +61,23 @@ public class Parser { String src() { return new String( _lexer._input ); } + private Node ctrl() { return _scope.ctrl(); } + private Node ctrl(Node n) { return _scope.ctrl(n); } - public ReturnNode parse() { + public ReturnNode parse() { return parse(false); } + public ReturnNode parse(boolean show) { _scope.push(); try { - _scope.define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole()); - _scope.define("arg" , new ProjNode(START, 1, "arg" ).peephole()); - return (ReturnNode) parseBlock(false); + _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole()); + _scope.define("arg", new ProjNode(START, 1, "arg").peephole()); + var ret = (ReturnNode) parseBlock(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + return ret; } finally { _scope.pop(); + if( show ) showGraph(); } } @@ -65,23 +87,17 @@ public class Parser { * <pre> * '{' statements '}' * </pre> + * Does not parse the opening or closing '{}' + * @return a {@link Node} or {@code null} */ - private Node parseBlock(boolean requireClosingBracket) { + private Node parseBlock() { // Enter a new scope _scope.push(); Node n = null; - do { - if (match("}")) { - if (requireClosingBracket) break; - else throw error("unexpected '}' token"); - } else if (_lexer.isEOF()) { - if (requireClosingBracket) require("}"); - else break; - } - + while (!peek('}') && !_lexer.isEOF()) { Node n0 = parseStatement(); if (n0 != null) n = n0; // Allow null returns from eg showGraph - } while (true); + }; // Exit scope _scope.pop(); return n; @@ -93,12 +109,13 @@ public class Parser { * <pre> * returnStatement | declStatement | blockStatement | expressionStatement * </pre> + * @return a {@link Node} or {@code null} */ private Node parseStatement() { - if (match("return")) return parseReturn(); - else if (match("int")) return parseDecl(); - else if (match("{")) return parseBlock(true); - else if (match("#showGraph")) return showGraph(); + 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 return parseExpressionStatement(); } @@ -109,19 +126,20 @@ public class Parser { * <pre> * 'return' expr ; * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - Node ret = new ReturnNode(_scope.lookup("$ctrl"), expr); - _scope.update("$ctrl",null); + Node ret = new ReturnNode(ctrl(), expr).peephole(); + ctrl(null); // Kill control return ret; } /** * Dumps out the node graph + * @return {@code null} */ private Node showGraph() { - require(";"); System.out.println(new GraphVisualizer().generateDotOutput(this)); return null; } @@ -132,6 +150,7 @@ public class Parser { * <pre> * name '=' expression ';' * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseExpressionStatement() { var name = requireId(); @@ -148,6 +167,7 @@ public class Parser { * <pre> * 'int' name = expression ';' * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseDecl() { // Type is 'int' for now @@ -163,11 +183,20 @@ public class Parser { * Parse an expression of the form: * * <pre> - * expr : additiveExpr + * expr : compareExpr * </pre> + * @return an expression {@link Node}, never {@code null} */ private Node parseExpression() { return parseComparison(); } + /** + * Parse an expression of the form: + * + * <pre> + * expr : additiveExpr op additiveExpr + * </pre> + * @return an comparator expression {@link Node}, never {@code null} + */ private Node parseComparison() { var lhs = parseAddition(); if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); @@ -185,6 +214,7 @@ public class Parser { * <pre> * additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)* * </pre> + * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { var lhs = parseMultiplication(); @@ -199,6 +229,7 @@ public class Parser { * <pre> * multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)* * </pre> + * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { var lhs = parseUnary(); @@ -213,6 +244,7 @@ public class Parser { * <pre> * unaryExpr : ('-') unaryExpr | primaryExpr * </pre> + * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { if (match("-")) return new MinusNode(parseUnary()).peephole(); @@ -225,15 +257,16 @@ public class Parser { * <pre> * primaryExpr : integerLiteral | Identifier | '(' expression ')' * </pre> + * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - if (_lexer.isNumber()) return parseIntegerLiteral(); - if (match("(")) return require(parseExpression(), ")"); - String name = requireId(); - Node id = _scope.lookup(name); - if( id==null ) - throw error("Undefined name '" + name + "'"); - return id.peephole(); + if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( match("(") ) return require(parseExpression(), ")"); + String name = _lexer.matchId(); + if( name == null) throw errorSyntax("an identifier or expression"); + Node n = _scope.lookup(name); + if( n!=null ) return n; + throw error("Undefined name '" + name + "'"); } /** @@ -251,13 +284,17 @@ public class Parser { // Utilities for lexical analysis // Return true and skip if "syntax" is next in the stream. - private boolean match(String syntax) { return _lexer.match(syntax); } + private boolean match (String syntax) { return _lexer.match (syntax); } + // Match must be "exact", not be followed by more id letters + private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + // Return true and do NOT skip if 'ch' is next + private boolean peek(char ch) { return _lexer.peek(ch); } // Require and return an identifier private String requireId() { String id = _lexer.matchId(); - if (id != null) return id; - throw error("identifier"); + if (id != null && !KEYWORDS.contains(id) ) return id; + throw error("Expected an identifier, found '"+id+"'"); } // Require an exact match @@ -343,11 +380,24 @@ public class Parser { int len = syntax.length(); if (_position + len > _input.length) return false; for (int i = 0; i < len; i++) - if ((char) _input[_position + i] != syntax.charAt(i)) return false; + if ((char) _input[_position + i] != syntax.charAt(i)) + return false; _position += len; return true; } + boolean matchx(String syntax) { + if( !match(syntax) ) return false; + if( !isIdLetter(peek()) ) return true; + _position -= syntax.length(); + return false; + } + + private boolean peek(char ch) { + skipWhiteSpace(); + return peek()==ch; + } + // Return an identifier or null String matchId() { skipWhiteSpace(); @@ -397,8 +447,7 @@ public class Parser { private String parsePunctuation() { int start = _position; - if (isPunctuation(nextChar())) ; - return new String(_input, start, --_position - start); + return new String(_input, start, 1); } } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java index 8b157a9c..d4d15bef 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter04/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) { @@ -36,37 +35,64 @@ public class AddNode extends Node { Type t1 = lhs._type; Type t2 = rhs._type; + // Already handled by peephole constant folding + assert !(t1.isConstant() && t2.isConstant()); + // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) - if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 ) + if( t2 instanceof TypeInteger i && i.value()==0 ) return lhs; - - // Move constants to RHS: con+arg becomes arg+con - if ( t1.isConstant() && !t2.isConstant() ) { - Node tmp = in(1); // Swap inputs without letting either input go dead during the swap - _inputs.set(1,in(2)); - _inputs.set(2,tmp); - return this; - } - + + // Add of same to a multiply by 2 + if( lhs==rhs ) + return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + // Goal: a left-spine set of adds, with constants on the rhs (which then fold). - // Do we have (x + con1) + con2 ? - // Rotate to x +(con1 + con2) - // The constants will fold on the next peephole. - if (t2.isConstant() && lhs instanceof AddNode && lhs.in(2)._type.isConstant() ) - return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + // Move non-adds to RHS + if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) + return swap12(); - // Do we have x + (y + con) ? - // Swap to (x + y) + con - if (rhs instanceof AddNode add && add.in(2)._type.isConstant() ) - return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) - // Add of same to a multiply by 2 - if( lhs==rhs ) - return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + // Do we have x + (y + z) ? + // Swap to (x + y) + z + // Rotate (add add add) to remove the add on RHS + if( rhs instanceof AddNode add ) + return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + + // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add) + if( !(lhs instanceof AddNode) ) + return spline_cmp(lhs,rhs) ? swap12() : null; + + // Now we only see (add add non) + + // Do we have (x + con1) + con2? + // Replace with (x + (con1+con2) which then fold the constants + if( lhs.in(2)._type.isConstant() && t2.isConstant() ) + return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + + // Now we sort along the spline via rotates, to gather similar things together. + + // Do we rotate (x + y) + z + // into (x + z) + y ? + if( spline_cmp(lhs.in(2),rhs) ) + return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); return null; } + + // Compare two off-spline nodes and decide what order they should be in. + // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? + // Generally constants always go right, then others. + // Ties with in a category sort by node ID. + // TRUE if swapping hi and lo. + static boolean spline_cmp( Node hi, Node lo ) { + if( lo._type.isConstant() ) return false; + if( hi._type.isConstant() ) return true ; + + // Same category of "others" + return lo._nid > hi._nid; + } } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java index b0e0bf42..02eb7ce9 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -13,7 +13,10 @@ abstract public class BoolNode extends Node { abstract String op(); // String opcode name @Override - public String label() { return op(); } + public String label() { return getClass().getSimpleName(); } + + @Override + public String glabel() { return op(); } @Override StringBuilder _print1(StringBuilder sb) { diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Control.java deleted file mode 100644 index 48cf2b7a..00000000 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/Control.java +++ /dev/null @@ -1,9 +0,0 @@ -package com.seaofnodes.simple.node; - - -/** - * Control interface is a marker interface to be implemented - * by Control nodes. - */ -public interface Control { -} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java index 1f562378..ae87deac 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 04084d0f..533155d9 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter04/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) { @@ -21,7 +20,7 @@ public class MinusNode extends Node { @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) - return TypeInteger.constant(-i0.value()); + return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; return TypeBot.BOTTOM; } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java index e3e83b38..5f6c1ad8 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter04/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) { @@ -43,12 +42,8 @@ public class MulNode extends Node { return lhs; // Move constants to RHS: con*arg becomes arg*con - if ( t1.isConstant() && !t2.isConstant() ) { - Node tmp = in(1); // Swap inputs without letting either input go dead during the swap - _inputs.set(1,in(2)); - _inputs.set(2,tmp); - return this; - } + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); return null; } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java index e517c3d5..fe3fddf8 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -4,10 +4,6 @@ import com.seaofnodes.simple.type.Type; public abstract class MultiNode extends Node { - public MultiNode(Node... inputs) { - super(inputs); - } - - // Return the ProjNode with the idx - abstract ProjNode proj(int idx); + public MultiNode(Node... inputs) { super(inputs); } + } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java index 7cc9291c..804d30e0 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java @@ -2,8 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import java.util.ArrayList; -import java.util.Collections; +import java.util.*; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -24,8 +23,7 @@ public abstract class Node { * <p> * Generally fixed length, ordered, nulls allowed, no unused trailing space. * Ordering is required because e.g. "a/b" is different from "b/a". - * The first input (offset 0) is often a Control node. - * @see Control + * The first input (offset 0) is often a {@link #isCFG} node. */ public final ArrayList<Node> _inputs; @@ -61,13 +59,18 @@ public abstract class Node { _outputs = new ArrayList<>(); for( Node n : _inputs ) if( n != null ) - n._outputs.add( this ); + n.addUse( 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 @@ -101,24 +104,18 @@ public abstract class Node { public int nIns() { return _inputs.size(); } - /** - * Gets the ith output node - * @param i Offset of the output node - * @return Output node (not null) - */ - public Node out(int i) { return _outputs.get(i); } - public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } + public boolean isCFG() { return false; } + /** * We allow disabling peephole opt so that we can observe the * full graph, vs the optimized graph. */ public static boolean _disablePeephole = false; - /** * Try to peephole at this node and return a better replacement Node if * possible. We compute a {@link Type} and then check and replace: @@ -197,7 +194,7 @@ public abstract class Node { // This needs to happen before removing the old node's def->use edge as // the new_def might get killed if the old node kills it recursively. if( new_def != null ) - new_def._outputs.add(this); + new_def.addUse(this); if( old_def != null && // If the old def exists, remove a def->use edge old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def @@ -219,11 +216,10 @@ public abstract class Node { _inputs.add(new_def); // If new def is not null, add the corresponding def->use edge if( new_def != null ) - new_def._outputs.add(this); + new_def.addUse(this); return new_def; } - // Breaks the edge invariants, used temporarily private void addUse(Node n) { _outputs.add(n); } @@ -266,7 +262,7 @@ public abstract class Node { // Mostly used for asserts and printing. boolean isDead() { return isUnused() && nIns()==0 && _type==null; } - + /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -332,14 +328,21 @@ public abstract class Node { */ public abstract Node idealize(); + + // ----------------------- + // Peephole utilities + + // Swap inputs without letting either input go dead during the swap. + Node swap12() { + Node tmp = in(1); + _inputs.set(1,in(2)); + _inputs.set(2,tmp); + return this; + } + /** * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ public static void reset() { UNIQUE_ID = 1; } - - /* - * hashCode and equals implementation to be added in later chapter. - */ - } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java index be37c514..be0556ed 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -22,7 +22,9 @@ public class ProjNode extends Node { public String label() { return _label; } @Override - StringBuilder _print1(StringBuilder sb) { return sb.append("Proj_" +_nid); } + StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } + + @Override public boolean isCFG() { return _idx==0; } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c94115bb..e20d01e5 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeBot; +import com.seaofnodes.simple.type.*; /** * The Return node has two inputs. The first input is a control node and the @@ -12,7 +11,7 @@ import com.seaofnodes.simple.type.TypeBot; * <p> * The Return's output is the value from the data node. */ -public class ReturnNode extends Node implements Control { +public class ReturnNode extends Node { public ReturnNode(Node ctrl, Node data) { super(ctrl, data); @@ -29,10 +28,11 @@ public class ReturnNode extends Node implements Control { return expr()._print0(sb.append("return ")).append(";"); } + @Override public boolean isCFG() { return true; } @Override public Type compute() { - return expr().compute(); + return new TypeTuple(TypeControl.CONTROL,expr()._type); } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 8bd81e82..45966791 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.TypeBot; import java.util.*; @@ -16,12 +17,15 @@ public class ScopeNode extends Node { * The top of this stack represents current scope. */ 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) { + sb.append(label()); for( HashMap<String,Integer> scope : _scopes ) { sb.append("["); boolean first=true; @@ -41,12 +45,11 @@ 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 void push() { - _scopes.push(new HashMap<>()); + public HashMap<String, Integer> push() { + return _scopes.push(new HashMap<>()); } // Remove the current lexical scope, killing all unused nodes. @@ -60,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); } @@ -72,7 +76,15 @@ public class ScopeNode extends Node { return null; } + public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); } + + public Node ctrl(Node n) { + assert lookup(Parser.CTRL)==in(0); + set_def(0,n); + return n; + } + // If the name is present in any scope, then redefine public Node update(String name, Node n) { for (int i = _scopes.size() - 1; i >= 0; i--) { @@ -84,5 +96,4 @@ public class ScopeNode extends Node { return null; } - } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java index b59e3375..91573de8 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -11,7 +11,7 @@ import com.seaofnodes.simple.type.TypeTuple; * will require Projections to extract the values. We discuss this in detail * in Chapter 9: Functions and Calls. */ -public class StartNode extends MultiNode implements Control { +public class StartNode extends MultiNode { final TypeTuple _args; @@ -27,20 +27,12 @@ public class StartNode extends MultiNode implements Control { StringBuilder _print1(StringBuilder sb) { return sb.append(label()); } - + + @Override public boolean isCFG() { return true; } + @Override public TypeTuple compute() { return _args; } @Override public Node idealize() { return null; } - - - @Override - public ProjNode proj( int idx ) { - for( Node proj : _outputs ) - if( ((ProjNode)proj)._idx==idx ) - return (ProjNode)proj; - return null; - } - } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java index e5939e1b..42ddc1c1 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index b53b1b29..63c46035 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -26,7 +26,7 @@ public class TypeInteger extends Type { @Override public String toString() { - return _print(new StringBuilder()).toString(); + return _print(new StringBuilder()).toString(); } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index ef87a415..036147a2 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.type; public class TypeTuple extends Type { - + public final Type[] _types; - public TypeTuple(Type[] _types) { + public TypeTuple(Type... _types) { this._types = _types; } |