diff options
Diffstat (limited to 'chapter01')
8 files changed, 82 insertions, 125 deletions
diff --git a/chapter01/README.md b/chapter01/README.md index e5b79493..69a09328 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -71,34 +71,39 @@ at very little cost (nearly always small constant time) because all dependencies ### Unique Node ID -Each node is assigned a unique dense integer Node ID when created. This ID is useful for debugging and e.g. as -an index into a bit vector, which in turn is used to efficiently visit a (possibly cyclic) graph. -The ID is also used to efficiently compute equality of nodes; a subject that we discuss in Chapter 8 Global Value Numbering. +Each node is assigned a unique dense integer Node ID when created. This ID is +useful for debugging, efficiently computing equality and e.g. as an index into +a bit vector, which in turn is used to efficiently visit a (possibly cyclic) +graph. We discuss Node equality in Chapter 8 Global Value Numbering. ### Start Node -The Start node represents the start of the function. For now, we do not have any values in the Start node, this is because our function does not -yet accept parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. +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. ### Constant Node -The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore the Constant node contains -an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. +A Constant node represents a constant value. At present, the only constants +that we allow are integer literals; therefore Constants contain an integer +value. As we add other types of constants, we refactor how we represent +Constants. -The Constant node has no inputs. However, we set the Start node as an input to the Constant node to enable forward graph walk. This edge carries no semantic meaning, -it is present _solely_ to allow visitation. +Constants have no semantic inputs. However, we set Start as an input to +Constants to enable a forward graph walk. This edge carries no semantic +meaning, and it is present _solely_ to allow visitation. -The Constant node's output is the value stored in it. +The Constant's value is the value stored in it. ### Return Node -The Return node has two inputs. The first input is a control node. The second input is the data node that supplies the return value. +The Return node has two inputs. The first input is a control node and the +second is the data node that supplies the return value. -In this presentation, the Return node functions as the Stop node, since we are compiling a single unnamed function. -A separate Stop node is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. +In this presentation, Return functions as a Stop node, since we are compiling a single unnamed function. +A separate Stop is not necessary. Compiling multiple functions is covered in Chapter 9: Functions and Calls. -The output of the Return node is the value it obtained from the data node. +The Return's output is the value from the data node. ### Representation @@ -111,4 +116,4 @@ return 1;  * Control nodes appear as square boxes -* Control edges are in bold red
\ No newline at end of file +* Control edges are in bold red diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index 2feeddf9..4da758b2 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -18,14 +18,8 @@ public class Parser { */ private Token _curTok; - private final NodeIDGenerator _idGenerator; - private StartNode _startNode; - public Parser() { - _idGenerator = new NodeIDGenerator(); - } - public StartNode parse(String source) { Lexer lexer = new Lexer(source); nextToken(lexer); @@ -33,7 +27,7 @@ public class Parser { } private StartNode parseProgram(Lexer lexer) { - _startNode = new StartNode(_idGenerator); + _startNode = new StartNode(); parseReturnStatement(lexer); return _startNode; } @@ -49,7 +43,7 @@ public class Parser { matchIdentifier(lexer, "return"); var returnExpr = parseExpression(lexer); matchPunctuation(lexer, ";"); - return new ReturnNode(_idGenerator, _startNode, returnExpr); + return new ReturnNode(_startNode, returnExpr); } /** @@ -109,7 +103,7 @@ public class Parser { * </pre> */ private ConstantNode parseIntegerLiteral(Lexer lexer) { - var constantNode = new ConstantNode(_idGenerator, _curTok._num.longValue(), _startNode); + var constantNode = new ConstantNode(_curTok._num.longValue(), _startNode); nextToken(lexer); return constantNode; } @@ -159,8 +153,7 @@ public class Parser { public final Kind _kind; /** - * String representation of a token - always - * populated + * String representation of a token - always populated */ public final String _str; /** @@ -189,6 +182,7 @@ public class Parser { */ public static Token EOF = new Token(Kind.EOZ, "", null); + @Override public String toString() { return _str; } @@ -236,13 +230,13 @@ public class Parser { * Note that EOF is not whitespace! */ private boolean isWhiteSpace(char c) { - return c == ' ' || - c == '\t' || - c == '\n' || - c == '\r'; + return c == ' ' || + c == '\t' || + c == '\n' || + c == '\r'; } - private void skipWhitespace() { + private void skipWhiteSpace() { while (isWhiteSpace(_cur)) nextToken(); } @@ -296,7 +290,7 @@ public class Parser { * Gets the next token */ public Token next() { - skipWhitespace(); + skipWhiteSpace(); if (_cur == 0) return Token.EOF; if (Character.isDigit(_cur)) 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 31718a1d..e7a3b3f2 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -13,8 +13,8 @@ public class ConstantNode extends Node { public final long _value; - public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) { - super(idGenerator, OP_CONSTANT, startNode); + public ConstantNode(long value, StartNode startNode) { + super(startNode); _value = value; } } 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 e78ab19a..bafa58f4 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -2,32 +2,14 @@ package com.seaofnodes.simple.node; import java.util.ArrayList; import java.util.Arrays; -import java.util.List; +import java.util.Collections; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public class Node { - - /** - * @see StartNode - */ - static final byte OP_START = 1; - /** - * @see ReturnNode - */ - static final byte OP_RETURN = 2; - /** - * @see ConstantNode - */ - static final byte OP_CONSTANT = 3; - - /** - * The opcode for this node - */ - public final byte _opCode; +public abstract class Node { /** * Each node has a unique dense Node ID within a compilation context @@ -40,34 +22,40 @@ public class Node { * Inputs to the node. These are use-def references to Nodes. * <p> * Generally fixed length, ordered, nulls allowed, no unused trailing space. - * The first input (offset 0) must be a Control nodes. + * 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 */ - public final List<Node> _inputs; + public final ArrayList<Node> _inputs; /** - * Outputs reference Nodes that are not null and - * have this Node as an input. These nodes are users of this - * node, thus these are def-use references to Nodes. + * Outputs reference Nodes that are not null and have this Node as an + * input. These nodes are users of this node, thus these are def-use + * references to Nodes. * <p> - * Note that the outputs are derived from inputs, it appears that - * outputs are therefore a performance optimization to make it easier to - * traverse the graph. The Sea of Nodes documentation in chapter 1 does not - * mention these outputs list. + + * Outputs directly match inputs, making a directed graph that can be + * walked in either direction. These outputs are typically used for + * efficient optimizations but otherwise have no semantics meaning. */ - public final List<Node> _outputs; + public final ArrayList<Node> _outputs; + + /** + * 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. + * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. + * */ + private static int UNIQUE_ID = 1; - protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) - { - _nid = idGenerator.newNodeID(); // allocate unique dense ID - _opCode = opCode; - _inputs = Arrays.asList(inputs); + protected Node(Node ...inputs) { + _nid = UNIQUE_ID++; // allocate unique dense ID + _inputs = new ArrayList<>(); + Collections.addAll(_inputs,inputs); _outputs = new ArrayList<>(); - for (int i = 0; i < _inputs.size(); i++) { - Node n = _inputs.get(i); - if (n != null) - n._outputs.add(this); - } + for( Node n : _inputs ) { + if( n != null ) + n._outputs.add( this ); + } } /** @@ -77,17 +65,11 @@ public class Node { */ public Node in(int i) { return _inputs.get(i); } - public int numInputs() { return _inputs.size(); } + public int nIns() { return _inputs.size(); } public Node out(int i) { return _outputs.get(i); } - public int numOutputs() { return _outputs.size(); } - - /** - * Is this a control node, all control nodes are marked with - * the interface Control. - */ - public boolean isControl() { return this instanceof Control; } + public int nOuts() { return _outputs.size(); } /* * hashCode and equals implementation to be added in later chapter. diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java deleted file mode 100644 index 96a292df..00000000 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java +++ /dev/null @@ -1,19 +0,0 @@ -package com.seaofnodes.simple.node; - -/** - * Nodes are given unique dense ids. - */ -public class NodeIDGenerator { - /** - * Counter for node IDs, do not hand out NID 0 - * (Presumably) because it is used for the control node? - */ - private int nodeIDCounter = 1; - - public int newNodeID() { - if (nodeIDCounter > 100000) { - throw new RuntimeException("infinite node create loop"); - } - return nodeIDCounter++; - } -} 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 0b62cd4c..eafcab94 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -10,7 +10,7 @@ package com.seaofnodes.simple.node; */ public class ReturnNode extends Node implements Control { - public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_RETURN, inputs); + public ReturnNode(Node ctrl, Node data) { + super(ctrl,data); } } 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 7a9233a8..6944e8fc 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -7,7 +7,7 @@ package com.seaofnodes.simple.node; */ public class StartNode extends Node implements Control { - public StartNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_START, inputs); + public StartNode(/*arguments go here*/) { + super(); } } diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java index ad420ece..9bc2fc1c 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java @@ -1,9 +1,6 @@ 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.Assert; import org.junit.Test; @@ -14,22 +11,20 @@ public class ParserTest { Parser parser = new Parser(); StartNode startNode = parser.parse("return 1;"); Assert.assertNotNull(startNode); - Assert.assertTrue(startNode.isControl()); - Assert.assertEquals(2, startNode.numOutputs()); - for (int i = 0; i < startNode.numOutputs(); i++) { - Node out = startNode.out(i); - if (out instanceof ReturnNode) { - Assert.assertEquals(2, out.numInputs()); - Assert.assertEquals(startNode, out.in(0)); - Assert.assertTrue(out.isControl()); - Assert.assertTrue(out.in(1) instanceof ConstantNode); - } - else if (out instanceof ConstantNode cn) { - Assert.assertEquals(1, cn._value); - Assert.assertEquals(1, cn.numInputs()); - Assert.assertEquals(startNode, cn.in(0)); - } - else { + Assert.assertEquals(2, startNode.nOuts()); + for (int i = 0; i < startNode.nOuts(); i++) { + switch( startNode.out(i) ) { + case ReturnNode ret: + Assert.assertEquals(2, ret.nIns()); + Assert.assertEquals(startNode, ret.in(0)); + Assert.assertTrue(ret.in(1) instanceof ConstantNode); + break; + case ConstantNode con: + Assert.assertEquals(1, con._value); + Assert.assertEquals(1, con.nIns()); + Assert.assertEquals(startNode, con.in(0)); + break; + default: throw new IllegalStateException(); } } |