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> --- .../main/java/com/seaofnodes/simple/Parser.java | 88 ++++++++++------------ .../com/seaofnodes/simple/node/ConstantNode.java | 6 +- .../java/com/seaofnodes/simple/node/Control.java | 9 --- .../main/java/com/seaofnodes/simple/node/Node.java | 32 +++----- .../com/seaofnodes/simple/node/ReturnNode.java | 12 ++- .../java/com/seaofnodes/simple/node/StartNode.java | 5 +- 6 files changed, 65 insertions(+), 87 deletions(-) delete mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/Control.java (limited to 'chapter01/src/main/java') diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index a71def25..e2c1ca71 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,20 +1,16 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.ConstantNode; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.ReturnNode; -import com.seaofnodes.simple.node.StartNode; +import com.seaofnodes.simple.node.*; /** - * The Parser converts a Simple source program to the Sea of Nodes intermediate representation - * directly in one pass. There is no intermediate Abstract Syntax Tree structure. - * + * The Parser converts a Simple source program to the Sea of Nodes intermediate + * representation directly in one pass. There is no intermediate Abstract + * Syntax Tree structure. + *

* This is a simple recursive descent parser. All lexical analysis is done here as well. */ public class Parser { - private final Lexer _lexer; - /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode @@ -24,6 +20,10 @@ public class Parser { */ public static StartNode START; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. + private final Lexer _lexer; + + public Parser(String source) { _lexer = new Lexer(source); Node.reset(); @@ -31,21 +31,21 @@ public class Parser { } public ReturnNode parse() { + require("return"); return parseReturn(); } /** - * Parses return statement. + * Parses a return statement; "return" already parsed. * * 

-     *     return expr ;
+     *     'return' expr ;
      *
+ * @return an expression {@link Node}, never {@code null} */ private ReturnNode parseReturn() { - require("return"); - var returnExpr = parseExpression(); - require(";"); - return new ReturnNode(START, returnExpr); + var expr = require(parseExpression(), ";"); + return new ReturnNode(START, expr); } /** @@ -54,6 +54,7 @@ public class Parser { * 
      *     expr : primaryExpr
      *
+ * @return an expression {@link Node}, never {@code null} */ private Node parseExpression() { return parsePrimary(); @@ -81,25 +82,28 @@ public class Parser { * */ private ConstantNode parseIntegerLiteral() { - return new ConstantNode(_lexer.parseNumber(), START); - } - - static RuntimeException error(String errorMessage) { - return new RuntimeException(errorMessage); + return new ConstantNode(_lexer.parseNumber()); } ////////////////////////////////// // 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); } // Require an exact match - private void require(String syntax) { - if (match(syntax)) return; - throw error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); + private void require(String syntax) { require(null, syntax); } + private Node require(Node n, String syntax) { + if (match(syntax)) return n; + throw errorSyntax(syntax); + } + + RuntimeException errorSyntax(String syntax) { + return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); + } + + static RuntimeException error(String errorMessage) { + return new RuntimeException(errorMessage); } //////////////////////////////////// @@ -152,8 +156,7 @@ public class Parser { * Return the next non-white-space character */ private void skipWhiteSpace() { - while (isWhiteSpace()) - _position++; + while (isWhiteSpace()) _position++; } @@ -163,8 +166,7 @@ public class Parser { boolean match(String syntax) { skipWhiteSpace(); int len = syntax.length(); - if (_position + len > _input.length) - return false; + if (_position + len > _input.length) return false; for (int i = 0; i < len; i++) if ((char) _input[_position + i] != syntax.charAt(i)) return false; @@ -175,20 +177,13 @@ public class Parser { // Used for errors String getAnyNextToken() { if (isEOF()) return ""; - if (isIdentifierStart(peek())) - return parseIdentifier(); - if (isPunctuation(peek())) - return parsePunctuation(); + if (isIdStart(peek())) return parseId(); + if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } - boolean isNumber() { - return isNumber(peek()); - } - - boolean isNumber(char ch) { - return Character.isDigit(ch); - } + boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} private long parseNumber() { int start = _position; @@ -200,18 +195,18 @@ public class Parser { } // First letter of an identifier - private boolean isIdentifierStart(char ch) { + private boolean isIdStart(char ch) { return Character.isAlphabetic(ch) || ch == '_'; } // All characters of an identifier, e.g. "_x123" - private boolean isIdentifierLetter(char ch) { + private boolean isIdLetter(char ch) { return Character.isLetterOrDigit(ch) || ch == '_'; } - private String parseIdentifier() { + private String parseId() { int start = _position; - while (isIdentifierLetter(nextChar())) ; + while (isIdLetter(nextChar())) ; return new String(_input, start, --_position - start); } @@ -222,8 +217,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/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 7644daf2..21f65084 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; + /** * A Constant node represents a constant value. At present, the only constants * that we allow are integer literals; therefore Constants contain an integer @@ -16,8 +18,8 @@ public class ConstantNode extends Node { public final long _value; - public ConstantNode(long value, StartNode startNode) { - super(startNode); + public ConstantNode(long value) { + super(Parser.START); _value = value; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java deleted file mode 100644 index 48cf2b7a..00000000 --- a/chapter01/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/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java index b6ce3160..cf465e94 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.node; -import java.util.ArrayList; -import java.util.Collections; +import java.util.*; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -22,8 +21,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; @@ -45,17 +43,16 @@ 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 ) { + for( Node n : _inputs ) if( n != null ) n._outputs.add( this ); - } } - + /** * Gets the ith input node * @param i Offset of the input node @@ -65,23 +62,16 @@ 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; } + + /** * 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. - */ + public static void reset() { UNIQUE_ID = 1; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index a2321e2b..5e083cf2 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -9,17 +9,15 @@ package com.seaofnodes.simple.node; *

* 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); } - public Node ctrl() { - return in(0); - } + public Node ctrl() { return in(0); } + public Node expr() { return in(1); } - public Node expr() { - return in(1); - } + @Override public boolean isCFG() { return true; } + } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java index c29ba53c..04bd6bb4 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -5,9 +5,12 @@ package com.seaofnodes.simple.node; * 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(); } + + @Override public boolean isCFG() { return true; } + } -- cgit v1.2.3