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> --- chapter01/README.md | 4 +- chapter01/docs/01-graph.gv | 14 +++- chapter01/docs/01-graph.svg | 47 ++++++------ .../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 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 41 +++++----- 10 files changed, 126 insertions(+), 132 deletions(-) delete mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/Control.java (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index e09b61a3..f5f31f82 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -164,5 +164,7 @@ return 1; ![Sea of Nodes Visual](./docs/01-graph.svg) -* Control nodes appear as square boxes +* Control nodes appear as square boxes with yellow background * Control edges are in bold red +* The edges from Constants to Start are shown in dotted lines as these are not true control edges +* We label each edge with its position in the `_inputs` array, thus `0` means the edge is `_inputs[0]`. diff --git a/chapter01/docs/01-graph.gv b/chapter01/docs/01-graph.gv index 82d1b40a..df256f52 100644 --- a/chapter01/docs/01-graph.gv +++ b/chapter01/docs/01-graph.gv @@ -1,11 +1,17 @@ digraph chapter01 { +/* +return 1; +*/ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; - Con12 [ label="Con1" ]; + Con_2 [ label="#1" ]; Return3 [ shape=box style=filled fillcolor=yellow label="Return" ]; } - Con12 -> Start1 [style=dotted]; - Return3 -> Start1 [color=red]; - Return3 -> Con12; + edge [ fontname=Helvetica, fontsize=8 ]; + Con_2 -> Start1[taillabel=0 style=dotted]; + Return3 -> Start1[taillabel=0 color=red]; + Return3 -> Con_2[taillabel=1]; } diff --git a/chapter01/docs/01-graph.svg b/chapter01/docs/01-graph.svg index 8e478f4d..7f511966 100644 --- a/chapter01/docs/01-graph.svg +++ b/chapter01/docs/01-graph.svg @@ -4,50 +4,53 @@ - + chapter01 - + cluster_Nodes - + Start1 - -Start + +Start - + -Con12 - -Con1 +Con_2 + +#1 - + -Con12->Start1 - - +Con_2->Start1 + + +0 Return3 - -Return + +Return Return3->Start1 - - + + +0 - + -Return3->Con12 - - +Return3->Con_2 + + +1 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; } + } diff --git a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java index ce8c2822..cb5a8a69 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -1,15 +1,11 @@ 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.*; import org.junit.Rule; import org.junit.Test; import org.junit.rules.ExpectedException; -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.fail; +import static org.junit.Assert.*; public class Chapter01Test { @@ -21,11 +17,11 @@ public class Chapter01Test { Parser parser = new Parser("return 1;"); ReturnNode ret = parser.parse(); StartNode start = Parser.START; - + assertEquals(start, ret.ctrl()); Node expr = ret.expr(); - if (expr instanceof ConstantNode con) { - assertEquals(start, con.in(0)); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); assertEquals(1, con._value); } else { fail(); @@ -44,16 +40,22 @@ public class Chapter01Test { @Test public void testBad1() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error, expected return: ret"); - new Parser("ret").parse(); + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected return: ret",e.getMessage()); + } } @Test public void testBad2() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error: integer values cannot start with '0'"); - new Parser("return 0123;").parse(); + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } } @Test @@ -65,9 +67,12 @@ public class Chapter01Test { @Test public void testBad4() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error, expected ;:"); - new Parser("return 100").parse(); + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } } // Negative numbers require unary operator support that is not in scope -- cgit v1.2.3