From 736c658c274404084b15b450b2ab72d0e7569586 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Fri, 3 Nov 2023 21:21:54 +0000 Subject: Backport changes in Chapter 5 to previous chapters and update Chapter5 documentation (#34) * Backport changes from chapter 5 to older chapters (#30) * Fix wrong indent * Backport to chapter 4 * Backport to chapter 3 * Backport to chapter 2 * Backport to chapter 1 * Add if statement to comment (#32) * Update visuals for chapters 1,2 & 3. Reenable drawing of edges from constants to Start for these chapters. * Update visuals for chapters 4. Revise text to explain the labeling of edges in graphs and that we omit edge from Constant to Start nodes from chapter 4. * Add code snippets for if statement parsing and the duplication and merging of ScopeNodes. Explain how scopeNodes are duplicated and merged. * Add constant check to minus node (#31) * Fix closing root block with } (#33) * Backport fix closing root block with } to chapter 4 and 3 (#35) * Show use-def edge from Phi to Region as dotted edge. Add example of Phi peephole. Update visuals. Add more examples. * Fix visuals in chapter 1 and README in chapter 4. * Remove subheading * Adjust spaces --------- Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> --- .../com/seaofnodes/simple/GraphVisualizer.java | 85 ++++++++++----- .../main/java/com/seaofnodes/simple/Parser.java | 114 ++++++++++++++------- .../java/com/seaofnodes/simple/node/AddNode.java | 20 ++-- .../com/seaofnodes/simple/node/ConstantNode.java | 12 +-- .../java/com/seaofnodes/simple/node/Control.java | 9 -- .../java/com/seaofnodes/simple/node/DivNode.java | 25 ++--- .../java/com/seaofnodes/simple/node/MinusNode.java | 15 ++- .../java/com/seaofnodes/simple/node/MulNode.java | 24 ++--- .../main/java/com/seaofnodes/simple/node/Node.java | 111 +++++++++++--------- .../com/seaofnodes/simple/node/ReturnNode.java | 9 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 32 +++--- .../java/com/seaofnodes/simple/node/StartNode.java | 16 +-- .../java/com/seaofnodes/simple/node/SubNode.java | 20 ++-- .../java/com/seaofnodes/simple/type/TypeBot.java | 4 +- .../com/seaofnodes/simple/type/TypeInteger.java | 4 +- 15 files changed, 289 insertions(+), 211 deletions(-) delete mode 100644 chapter03/src/main/java/com/seaofnodes/simple/node/Control.java (limited to 'chapter03/src/main/java/com/seaofnodes') diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index dc5358f4..a85a670e 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -18,6 +18,9 @@ public class GraphVisualizer { Collection all = findAll(parser); StringBuilder sb = new StringBuilder(); sb.append("digraph chapter03 {\n"); + sb.append("/*\n"); + sb.append(parser.src()); + sb.append("\n*/\n"); // To keep the Scopes below the graph and pointing up into the graph we // need to group the Nodes in a subgraph cluster, and the scopes into a @@ -25,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); @@ -47,12 +57,15 @@ 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 ScopeNode ) + continue; // Do not emit, rolled into Scope cluster already sb.append("\t\t").append(n.uniqueName()).append(" [ "); + String lab = n.glabel(); // control nodes have box shape // other nodes are ellipses, i.e. default shape - if( n instanceof Control ) + if( n.isCFG() ) sb.append("shape=box style=filled fillcolor=yellow "); - sb.append("label=\"").append(n.label()).append("\" "); + sb.append("label=\"").append(lab).append("\" "); sb.append("];\n"); } sb.append("\t}\n"); // End Node cluster @@ -62,12 +75,12 @@ public class GraphVisualizer { sb.append("\tnode [shape=plaintext];\n"); int level=0; for( HashMap 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\n"); // Add the scope level - sb.append("\t\t\t"); + sb.append("\t\t\t"); for( String name : scope.keySet() ) sb.append(""); sb.append("\n"); @@ -79,23 +92,37 @@ 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 makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } // Walk the node edges private void nodeEdges(StringBuilder sb, Collection all) { - for( Node n : all ) - for( Node out : n._inputs ) - if( out != null ) { - sb.append('\t').append(n.uniqueName()).append(" -> ").append(out.uniqueName()); - // Control edges are colored red - if( n instanceof ConstantNode && out instanceof StartNode ) - sb.append(" [style=dotted]"); - else if( n instanceof Control && out instanceof Control ) - sb.append(" [color=red]"); - sb.append(";\n"); + // All them edge labels + sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); + for( Node n : all ) { + // In this chapter we do display the Constant->Start edge; + // ScopeNodes are done separately + if( n instanceof ScopeNode ) + continue; + int i=0; + for( Node def : n._inputs ) { + if( def != null ) { + // Most edges land here use->def + sb.append('\t').append(n.uniqueName()).append(" -> "); + sb.append(def.uniqueName()); + // Number edges, so we can see how they track + sb.append("[taillabel=").append(i); + if( n instanceof ConstantNode && def instanceof StartNode ) + sb.append(" style=dotted"); + // control edges are colored red + else if( def.isCFG() ) + sb.append(" color=red"); + sb.append("];\n"); } + i++; + } + } } // Walk the scope edges @@ -103,19 +130,23 @@ public class GraphVisualizer { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=0; for( HashMap scope : scopenode._scopes ) { - String scopeName = makeScopeName(level); - for( String name : scope.keySet() ) - sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scopenode.in(scope.get(name)).uniqueName()).append(";\n"); + String scopeName = makeScopeName(scopenode, level); + for( String name : scope.keySet() ) { + Node def = scopenode.in(scope.get(name)); + if( def==null ) continue; + sb.append("\t") + .append(scopeName).append(":") + .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted + .append(" -> "); + sb.append(def.uniqueName()); + sb.append(";\n"); + } level++; } } /** - * Walks the whole graph, starting from Start. - * Since Start is the input to all constants - we look at the outputs for - * Start, but for then subsequently we look at the inputs of each node. - * During graph construction not all nodes are reachable this way, so we - * also scan the symbol tables. + * Finds all nodes in the graph. */ private Collection findAll(Parser parser) { final StartNode start = Parser.START; @@ -133,10 +164,14 @@ public class GraphVisualizer { * Walk a subgraph and populate distinct nodes in the all list. */ private void walk(HashMap all, Node n) { + if(n == null ) return; if (all.get(n._nid) != null) return; // Been there, done that all.put(n._nid, n); for (Node c : n._inputs) if (c != null) walk(all, c); + for (Node c : n._outputs) + if (c != null) + walk(all, c); } } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index 3d06a9c3..c8195882 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -23,6 +23,7 @@ public class Parser { */ public static StartNode START; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** @@ -31,17 +32,35 @@ public class Parser { */ public ScopeNode _scope; + /** + * List of keywords disallowed as identifiers + */ + private final HashSet KEYWORDS = new HashSet<>(){{ + add("int"); + add("return"); + }}; + + public Parser(String source) { _lexer = new Lexer(source); - _scope = new ScopeNode(); Node.reset(); + _scope = new ScopeNode(); START = new StartNode(); } - public ReturnNode parse() { - return (ReturnNode) parseBlock(false); - } + String src() { return new String( _lexer._input ); } + public ReturnNode parse() { return parse(false); } + public ReturnNode parse(boolean show) { + try { + var ret = (ReturnNode) parseBlock(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + return ret; + } + finally { + if( show ) showGraph(); + } + } /** * Parses a block @@ -49,23 +68,17 @@ public class Parser { * 
      *     '{' statements '}'
      *
+ * 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; @@ -77,32 +90,34 @@ public class Parser { * 
      *     returnStatement | declStatement | blockStatement | expressionStatement
      *
+ * @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(); } /** - * Parses returnStatement; "return" already parsed + * Parses a return statement; "return" already parsed. * * 
      *     'return' expr ;
      *
+ * @return an expression {@link Node}, never {@code null} */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - return new ReturnNode(START, expr); + return new ReturnNode(START, expr).peephole(); } /** * Dumps out the node graph + * @return {@code null} */ private Node showGraph() { - require(";"); System.out.println(new GraphVisualizer().generateDotOutput(this)); return null; } @@ -113,6 +128,7 @@ public class Parser { * 
      *     name '=' expression ';'
      *
+ * @return an expression {@link Node}, never {@code null} */ private Node parseExpressionStatement() { var name = requireId(); @@ -129,6 +145,7 @@ public class Parser { * 
      *     'int' name = expression ';'
      *
+ * @return an expression {@link Node}, never {@code null} */ private Node parseDecl() { // Type is 'int' for now @@ -146,8 +163,9 @@ public class Parser { * 
      *     expr : additiveExpr
      *
+ * @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() {return parseAddition();} + private Node parseExpression() { return parseAddition(); } /** * Parse an additive expression @@ -155,6 +173,7 @@ public class Parser { * 
      *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
      *
+ * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { var lhs = parseMultiplication(); @@ -169,6 +188,7 @@ public class Parser { * 
      *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
      *
+ * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { var lhs = parseUnary(); @@ -183,6 +203,7 @@ public class Parser { * 
      *     unaryExpr : ('-') unaryExpr | primaryExpr
      *
+ * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { if (match("-")) return new MinusNode(parseUnary()).peephole(); @@ -195,15 +216,16 @@ public class Parser { * 
      *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
      *
+ * @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; + 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 + "'"); } /** @@ -221,17 +243,21 @@ 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 - private void require(String syntax) {require(null, syntax);} + private void require(String syntax) { require(null, syntax); } private Node require(Node n, String syntax) { if (match(syntax)) return n; throw errorSyntax(syntax); @@ -313,11 +339,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(); @@ -341,7 +380,7 @@ public class Parser { String snum = new String(_input, start, --_position - start); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); - return new TypeInteger(Long.parseLong(snum)); + return TypeInteger.constant(Long.parseLong(snum)); } // First letter of an identifier @@ -367,8 +406,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/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java index 015779dc..6784ad60 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -3,17 +3,16 @@ 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 _print(StringBuilder sb) { - in(1)._print(sb.append("(")); - in(2)._print(sb.append("+")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("+")); return sb.append(")"); } @@ -21,8 +20,9 @@ public class AddNode extends Node { @Override public Type compute() { if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) - return new TypeInteger(i0._con + i1._con); + in(2)._type instanceof TypeInteger i1 ) { + return TypeInteger.constant(i0.value()+i1.value()); + } return TypeBot.BOTTOM; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 798d40d5..ec85bf1f 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -16,25 +16,25 @@ import com.seaofnodes.simple.type.Type; * The Constant's value is the value stored in it. */ public class ConstantNode extends Node { - + Type _con; public ConstantNode( Type type ) { super(Parser.START); - _type = type; + _con = type; } @Override - public String label() { return "#"+_type; } + public String label() { return "#"+_con; } @Override public String uniqueName() { return "Con_" + _nid; } @Override - StringBuilder _print(StringBuilder sb) { - return _type._print(sb); + StringBuilder _print1(StringBuilder sb) { + return _con._print(sb); } @Override - public Type compute() { return _type; } + public Type compute() { return _con; } @Override public Node idealize() { return null; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Control.java deleted file mode 100644 index 48cf2b7a..00000000 --- a/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java index 0056c42d..ca7df79c 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -5,17 +5,16 @@ 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 _print(StringBuilder sb) { - in(1)._print(sb.append("(")); - in(2)._print(sb.append("/")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("/")); return sb.append(")"); } @@ -23,11 +22,9 @@ public class DivNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { - if (i0.isConstant() && i1.isConstant()) - return i1._con == 0 - ? TypeInteger.ZERO - : new TypeInteger(i0._con/i1._con); - return new TypeInteger(i0._con / i1._con); + return i1.value() == 0 + ? TypeInteger.ZERO + : TypeInteger.constant(i0.value()/i1.value()); } return TypeBot.BOTTOM; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 7fab83b0..834f4c11 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -5,23 +5,22 @@ 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 _print(StringBuilder sb) { - in(1)._print(sb.append("(-")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(-")); return sb.append(")"); } @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) - return new TypeInteger(-i0._con); + return TypeInteger.constant(-i0.value()); return TypeBot.BOTTOM; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java index e1a26858..0fa54966 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -5,25 +5,25 @@ 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); - } - - @Override - public String label() { return "Mul"; } + public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Mul"; } + @Override public String glabel() { return "*"; } + @Override - StringBuilder _print(StringBuilder sb) { - in(1)._print(sb.append("(")); - in(2)._print(sb.append("*")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("*")); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) - return new TypeInteger(i0._con * i1._con); + in(2)._type instanceof TypeInteger i1) { + return TypeInteger.constant(i0.value()*i1.value()); + } return TypeBot.BOTTOM; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index 9c71c424..a778687d 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/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 { *

* 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 _inputs; @@ -40,6 +38,13 @@ public abstract class Node { */ public final ArrayList _outputs; + + /** + * Current computed type for this Node. This value changes as the graph + * changes and more knowledge is gained about the program. + */ + public Type _type; + /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multi-threaded, this field will have to move into a TLS. @@ -47,34 +52,47 @@ public abstract class Node { * */ private static int UNIQUE_ID = 1; - protected Node(Node ...inputs) { + protected Node(Node... inputs) { _nid = UNIQUE_ID++; // allocate unique dense ID _inputs = new ArrayList<>(); Collections.addAll(_inputs,inputs); _outputs = new ArrayList<>(); for( Node n : _inputs ) if( n != null ) - n._outputs.add( this ); - // Do an initial type computation - _type = compute(); + 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 - return uniqueName(); + 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. + // 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 _print(new StringBuilder()).toString(); + 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); } - abstract StringBuilder _print(StringBuilder sb); + // Every Node implements this. + abstract StringBuilder _print1(StringBuilder sb); /** @@ -86,25 +104,21 @@ 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 check and replace: + * possible. We compute a {@link Type} and then check and replace: *

    *
  • if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}
    • *
  • in a future chapter we will look for a @@ -114,36 +128,27 @@ public abstract class Node { *
*/ public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + if (_disablePeephole) return this; // Peephole optimizations turned off // Replace constant computations from non-constants with a constant node - Type type = compute(); if (!(this instanceof ConstantNode) && type.isConstant()) { kill(); // Kill `this` because replacing with a Constant - return new ConstantNode(type); + return new ConstantNode(type).peephole(); } // Future chapter: Global Value Numbering goes here - // Ask each node for a replacement + // Ask each node for a better replacement Node n = idealize(); if( n != null ) return n; return this; // No progress } - /** - * Kill a Node with no uses, by setting all of its defs - * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #set_def}. - */ - public void kill( ) { - assert nOuts()==0; // Has no uses, so it is dead - for( int i=0; idef into a Node. Keeps the edges correct, by removing * the corresponding use->def edge. This may make the original @@ -151,6 +156,7 @@ public abstract class Node { * * @param idx which def to set * @param new_def the new definition + * @return this for flow coding */ Node set_def(int idx, Node new_def ) { Node old_def = in(idx); @@ -159,10 +165,10 @@ 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 + old_def.kill(); // Kill old def // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); // Return self for easy flow-coding @@ -181,11 +187,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); } @@ -194,10 +199,10 @@ public abstract class Node { // Error is 'use' does not exist; ok for 'use' to be null. private boolean delUse( Node use ) { ArrayList outs = _outputs; - int lidx = outs.size()-1; // Last index + int lidx = outs.size()-1; // Last index // This 1-line hack compresses an element out of an ArrayList // without having to copy the contents. The last element is - // stuffed over the deleted element, and then the size is reduced. + // stuffed over the deleted element, and then the size is reduced. outs.set(outs.indexOf(use),outs.get(lidx)); outs.remove(lidx); // Reduce ArrayList size without copying anything return lidx==0; @@ -209,17 +214,26 @@ public abstract class Node { for( int i=0; iuses, by setting all of its defs + * to null. This may recursively kill more Nodes and is basically dead + * code elimination. This function is co-recursive with {@link #pop_n}. */ - public Type _type; - + public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + pop_n(nIns()); // Set all inputs to null, recursively killing unused Nodes + _type=null; // Flag as dead + assert isDead(); // Really dead now + } + + // Mostly used for asserts and printing. + boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + /** * This function needs to be * Monotonic @@ -245,9 +259,4 @@ public abstract class Node { * 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/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c188ca79..18f5eed9 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -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 @@ -11,7 +11,7 @@ import com.seaofnodes.simple.type.TypeBot; *

* 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); @@ -24,10 +24,11 @@ public class ReturnNode extends Node implements Control { public String label() { return "Return"; } @Override - StringBuilder _print(StringBuilder sb) { - return expr()._print(sb.append("return ")).append(";"); + StringBuilder _print1(StringBuilder sb) { + return expr()._print0(sb.append("return ")).append(";"); } + @Override public boolean isCFG() { return true; } @Override public TypeBot compute() { diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index c7d6edb9..5f5d66a0 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.TypeBot; -import java.util.HashMap; -import java.util.Stack; +import java.util.*; /** * The Scope node is a purely parser helper - it tracks names to nodes with a @@ -17,12 +17,15 @@ public class ScopeNode extends Node { * The top of this stack represents current scope. */ public final Stack> _scopes = new Stack<>(); - - @Override - public String label() { return "Scope"; } - + + // Reverse lookup for nicer graph printing + private final ArrayList _rlabels = new ArrayList<>(); + + @Override public String label() { return "Scope"; } + @Override - StringBuilder _print(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb) { + sb.append(label()); for( HashMap scope : _scopes ) { sb.append("["); boolean first=true; @@ -32,22 +35,21 @@ public class ScopeNode extends Node { sb.append(name).append(":"); Node n = in(scope.get(name)); if( n==null ) sb.append("null"); - else n._print(sb); + else n._print0(sb); } sb.append("]"); } return sb; } - + @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 push() { + return _scopes.push(new HashMap<>()); } // Remove the current lexical scope, killing all unused nodes. @@ -61,6 +63,7 @@ public class ScopeNode extends Node { HashMap scope = _scopes.lastElement(); if( scope.put(name,nIns()) != null ) return null; // Double define + _rlabels.add(name); return add_def(n); } @@ -73,7 +76,7 @@ public class ScopeNode extends Node { return null; } - + // 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--) { @@ -85,5 +88,4 @@ public class ScopeNode extends Node { return null; } - } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java index 8d8031bb..08b8333a 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,11 +3,13 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.TypeBot; /** - * The Start node represents the start of the function. For now, we do not have any inputs to Start because our function does not - * yet accept parameters. When we add parameters the value of Start will be a tuple, and will require Projections to extract the values. - * We discuss this in detail in Chapter 9: Functions and Calls. + * The Start node represents the start of the function. For now, we do not + * have any inputs to Start because our function does not yet accept + * parameters. When we add parameters the value of Start will be a tuple, and + * will require Projections to extract the values. We discuss this in detail + * in Chapter 9: Functions and Calls. */ -public class StartNode extends Node implements Control { +public class StartNode extends Node { public StartNode(/*arguments go here*/) { super(); @@ -17,10 +19,12 @@ public class StartNode extends Node implements Control { public String label() { return "Start"; } @Override - StringBuilder _print(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb) { return sb.append(label()); } - + + @Override public boolean isCFG() { return true; } + @Override public TypeBot compute() { return TypeBot.BOTTOM; diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java index 2d7db8d3..71d70fa6 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -5,25 +5,25 @@ 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 _print(StringBuilder sb) { - in(1)._print(sb.append("(")); - in(2)._print(sb.append("-")); + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append("-")); return sb.append(")"); } @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) - return new TypeInteger(i0._con - i1._con); + in(2)._type instanceof TypeInteger i1) { + return TypeInteger.constant(i0.value()-i1.value()); + } return TypeBot.BOTTOM; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java index 5284884a..bc191241 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java @@ -8,7 +8,7 @@ public class TypeBot extends Type { @Override public String toString() { return "Bottom"; } - - @Override + + @Override public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); } } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 06cac15e..ff6e865b 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -14,6 +14,8 @@ public class TypeInteger extends Type { public TypeInteger(long con) { _con = con; } + public static TypeInteger constant(long con) { return new TypeInteger(con); } + @Override public String toString() { return _print(new StringBuilder()).toString(); @@ -25,7 +27,7 @@ public class TypeInteger extends Type { @Override public boolean isConstant() { return true; } - public long getConstant() { return _con; } + public long value() { return _con; } @Override public boolean equals( Object o ) { -- cgit v1.2.3

").append(level).append("
").append(level).append("").append(name).append("