From adb2ae48c7e92e3a9024b043e476162a11ef9641 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 15:59:44 +0100 Subject: Initial definition of nodes that will be relevant for chapter 1. --- chapter01/README.md | 25 ++++++ .../com/seaofnodes/simple/node/ConstantNode.java | 16 ++++ .../java/com/seaofnodes/simple/node/Control.java | 9 +++ .../main/java/com/seaofnodes/simple/node/Node.java | 94 ++++++++++++++++++++++ .../seaofnodes/simple/node/NodeIDGenerator.java | 19 +++++ .../com/seaofnodes/simple/node/RegionNode.java | 11 +++ .../com/seaofnodes/simple/node/ReturnNode.java | 11 +++ .../java/com/seaofnodes/simple/node/StartNode.java | 11 +++ 8 files changed, 196 insertions(+) create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/Control.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/Node.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java diff --git a/chapter01/README.md b/chapter01/README.md index b6a3d823..bb15e828 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -43,3 +43,28 @@ Our data structures will be based upon the descriptions provided in following pa Following the lead from above, we will represent our intermediate representation using an object oriented data model. Details of the representation follow. +### Intermediate Representation as a Graph of Nodes + +The intermediate representation is a graph of Node objects. The `Node` class is the base type for objects in the IR graph. +The `Node` class provides common capabilities that are inherited by all subtypes. +Each subtype implements semantics relevant to that subtype. + +There are two types of Nodes in the representation. + +* **Control Nodes** - these represent the control flow subgraph (CFG) of the compiled program +* **Data Nodes** - these capture the data semantics + +The following control and data nodes will be created in this chapter. + +| Node Name | Type | Description | Inputs | Value | +| --- | --- |------------------------|--------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Region | Control | Represent a Basic Block | Predecessor control nodes in the CFG | Each region represents one value | +| Return | Control | Represents the termination of a function | Predecessor control node, Data value node | Return value of the function | +| Constant | Data | Represents constants such as integer literals | None | Value of the constant | + +All control nodes will implement a marker interface named `Control`. + +Within a traditional basic block, instructions are executed in sequence. In the Sea of Nodes model, the correct sequence of instruction within a +region will be determined by a scheduling algorithm, to be discussed in later chapters. + diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java new file mode 100644 index 00000000..7f798301 --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -0,0 +1,16 @@ +package com.seaofnodes.simple.node; + +public class ConstantNode extends Node { + + long _value; + + public ConstantNode(int nid, long value) { + super(nid, OP_CONSTANT); + _value = value; + } + + public ConstantNode(NodeIDGenerator idGenerator, long value) { + super(idGenerator, OP_CONSTANT); + _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 new file mode 100644 index 00000000..48cf2b7a --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Control.java @@ -0,0 +1,9 @@ +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 new file mode 100644 index 00000000..0c6cdd3f --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -0,0 +1,94 @@ +package com.seaofnodes.simple.node; + +import java.util.Arrays; +import java.util.List; + +/** + * 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 { + + static final byte OP_START = 1; + static final byte OP_REGION = 2; + static final byte OP_RETURN = 3; + static final byte OP_CONSTANT = 4; + + /** + * The opcode for this node + */ + public final byte _opCode; + + /** + * Each node has a unique ID within a compilation context + */ + public final int _nid; + + /** + * Inputs to the node. + * + * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * The first input (offset 0) must be a Control node. + * @see Control + */ + public final List _inputs; + + protected Node(int nid, byte opCode, Node ...inputs) + { + _nid = nid; + _opCode = opCode; + _inputs = Arrays.asList(inputs); + } + + protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) + { + _nid = idGenerator.newNodeID(); + _opCode = opCode; + _inputs = Arrays.asList(inputs); + } + + /** + * Gets the ith input node + * @param i Offset of the input node + * @return Input node or null + */ + public Node in(int i) { return _inputs != null ? _inputs.get(i) : null; } + + public int numInputs() { return _inputs != null ? _inputs.size() : 0; } + + /** + * Is this a control node, all control nodes are marked with + * the interface Control. + */ + public boolean isControl() { return this instanceof Control; } + + /** + * Hash is function of this nodes type, its _nid and + * inputs, or opcode + input_nids + */ + @Override + public int hashCode() { + int sum = _opCode; + for (int i = 0; i < numInputs(); i++) + if (in(i) != null) + sum ^= in(i)._nid; + return sum; + } + + /** + * Equals is opcode + input nids. + * Note that nodes are compared by reference. + */ + @Override + public boolean equals(Object o) { + if (this == o) return true; + if (!(o instanceof Node n)) return false; + if (_opCode != n._opCode) return false; + if (numInputs() != n.numInputs()) return false; + for (int i = 0; i < numInputs(); i++) + if (in(i) != n.in(i)) + return false; + return true; + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java new file mode 100644 index 00000000..96a292df --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/NodeIDGenerator.java @@ -0,0 +1,19 @@ +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/RegionNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java new file mode 100644 index 00000000..b740deff --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.node; + +public class RegionNode extends Node implements Control { + public RegionNode(int nid, Node... inputs) { + super(nid, OP_REGION, inputs); + } + + public RegionNode(NodeIDGenerator idGenerator, Node... inputs) { + super(idGenerator, OP_REGION, inputs); + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java new file mode 100644 index 00000000..655fd11f --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.node; + +public class ReturnNode extends Node implements Control { + public ReturnNode(int nid, Node... inputs) { + super(nid, OP_RETURN, inputs); + } + + public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { + super(idGenerator, OP_RETURN, 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 new file mode 100644 index 00000000..8117c4f6 --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.node; + +public class StartNode extends Node implements Control { + public StartNode(int nid, Node... inputs) { + super(nid, OP_START, inputs); + } + + public StartNode(NodeIDGenerator idGenerator, Node... inputs) { + super(idGenerator, OP_START, inputs); + } +} -- cgit v1.2.3