From ab76b39f74776e8a0b09d4add10fcacb6668eb2e Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Mon, 18 Sep 2023 23:39:53 +0100 Subject: Remove opcodes Make the IdGenerator an input to the Parser --- .../main/java/com/seaofnodes/simple/Parser.java | 4 +-- .../com/seaofnodes/simple/node/ConstantNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 36 ++++++++-------------- .../seaofnodes/simple/node/NodeIDGenerator.java | 6 +--- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/ParserTest.java | 7 ++--- 7 files changed, 20 insertions(+), 39 deletions(-) diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index 2feeddf9..abaedd05 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -22,8 +22,8 @@ public class Parser { private StartNode _startNode; - public Parser() { - _idGenerator = new NodeIDGenerator(); + public Parser(NodeIDGenerator idGenerator) { + _idGenerator = idGenerator; } public StartNode parse(String source) { 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..bdf3340d 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -14,7 +14,7 @@ public class ConstantNode extends Node { public final long _value; public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) { - super(idGenerator, OP_CONSTANT, startNode); + super(idGenerator, 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..22ff8e3e 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -9,25 +9,8 @@ import java.util.List; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public class Node { +public abstract 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; /** * Each node has a unique dense Node ID within a compilation context @@ -53,18 +36,18 @@ public class Node { * 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. + * mention the outputs list. */ public final List _outputs; - protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) + protected Node(NodeIDGenerator idGenerator, Node ...inputs) { _nid = idGenerator.newNodeID(); // allocate unique dense ID - _opCode = opCode; _inputs = Arrays.asList(inputs); - _outputs = new ArrayList<>(); - for (int i = 0; i < _inputs.size(); i++) { - Node n = _inputs.get(i); + _outputs = new ArrayList<>(); // The outputs will be populated by nodes that use this as input + + // Add this to as output on all nodes that are inputs + for (Node n : _inputs) { if (n != null) n._outputs.add(this); } @@ -79,6 +62,11 @@ public class Node { public int numInputs() { 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 numOutputs() { return _outputs.size(); } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java index 96a292df..5c022160 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java @@ -5,15 +5,11 @@ package com.seaofnodes.simple.node; */ public class NodeIDGenerator { /** - * Counter for node IDs, do not hand out NID 0 - * (Presumably) because it is used for the control node? + * Counter for node IDs, do not hand out NID 0; this is just for safety */ 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..3b539ead 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -11,6 +11,6 @@ package com.seaofnodes.simple.node; public class ReturnNode extends Node implements Control { public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_RETURN, inputs); + super(idGenerator, inputs); } } 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..11043a79 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -8,6 +8,6 @@ package com.seaofnodes.simple.node; public class StartNode extends Node implements Control { public StartNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_START, inputs); + super(idGenerator, inputs); } } diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java index ad420ece..f1a82ec1 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; @@ -11,7 +8,7 @@ public class ParserTest { @Test public void testSimpleProgram() { - Parser parser = new Parser(); + Parser parser = new Parser(new NodeIDGenerator()); StartNode startNode = parser.parse("return 1;"); Assert.assertNotNull(startNode); Assert.assertTrue(startNode.isControl()); -- cgit v1.2.3 From 7e0b33067d83348b87652261845c2f40823012c7 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Mon, 18 Sep 2023 23:45:16 +0100 Subject: Update based on feedback --- chapter01/README.md | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) diff --git a/chapter01/README.md b/chapter01/README.md index e5b79493..2c0febb8 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -77,28 +77,28 @@ The ID is also used to efficiently compute equality of nodes; a subject that we ### 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 values in to Start, this is because our function does not yet accept parameters. +When we add parameters, the value of the 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. +The Constant node represents a constant value. At present, the only constants that we allow are integer literals; therefore Constant contains an integer value. +As we add other types of constants, we will refactor 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. +Constant has no inputs. However, we add Start as an input to Constant to enable forward graph walk. This edge carries no semantic meaning, +it is present solely to allow visitation. -The Constant node's output is the value stored in it. +The Constant's output 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. +Return has two inputs. The first input is a control node. The second input 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, the Return functions as the Stop, 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 output of the Return is the value it obtained from the data node. ### Representation -- cgit v1.2.3