From 8b8cdf8873b30fd21f9012a479a42809c079eb42 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 14:06:27 +0100 Subject: Revise grammar for chapter 1. Start writing up Chapter 1. --- chapter01/README.md | 44 ++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 42 insertions(+), 2 deletions(-) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index a641c4ad..b6a3d823 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -1,5 +1,45 @@ # Chapter 1 -Simple start and end node for basic empty script. +In this chapter we aim to compile simple scripts such as: + +``` +return 1; +``` + +The first statement to be implemented in the language is the `return` statement. +The `return` statement shall accept an argument, which must be an `expression`. +For this chapter, the language shall only have one type of `expression` - an integer literal, as +shown in the example above. + +Here is the [complete grammar](docs/01-grammar.md) of the language for this chapter. + +To implement this simple language, we will need to introduce several components and data +structures. + +## Implementation Language + +Our implementation language is Java. We chose Java as it is widely available and understood. + +## Architecture + +We will design our parser and compiler to illustrate some key aspects of the Sea of Nodes +Intermediate Representation: + +* We will construct the intermediate representation directly as we +parse the language. There will not be an intermediate Abstract Syntax Tree representation. + +* The compiler will perform a few basic local optimizations as we build the +IR; this is a key benefit of the Sea of Nodes IR. + +## Data Structures + +Our data structures will be based upon the descriptions provided in following papers: + +* [From Quads to Graphs: An Intermediate Representation's Journey](http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR93366-S.pdf) +* [Combining Analyses, Combining Optimzations](https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf) +* [A Simple Graph-Based Intermediate Representation](https://www.oracle.com/technetwork/java/javase/tech/c2-ir95-150110.pdf) +* [Global Code Motion Global Value Numbering](https://courses.cs.washington.edu/courses/cse501/06wi/reading/click-pldi95.pdf) + +Following the lead from above, we will represent our intermediate representation using an object oriented data model. Details of the +representation follow. -* [Grammar](docs/01-grammar.md) \ No newline at end of file -- cgit v1.2.3 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 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) (limited to 'chapter01/README.md') 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. + -- cgit v1.2.3 From d4e6ddb5084c0ef295adad6172e10c664a275260 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 16:09:37 +0100 Subject: Initial definition of nodes that will be relevant for chapter 1. --- chapter01/README.md | 35 +++++++++++++++++++++++++++++------ 1 file changed, 29 insertions(+), 6 deletions(-) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index bb15e828..0dee71be 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -56,15 +56,38 @@ There are two types of Nodes in the representation. 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 | +| 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 node value | 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. +### Unique Node ID + +Each node will be assigned a unique Node ID upon creation. The Node ID will be allocated in a particular compilation context. + +### Node Comparisons + +Nodes will by default be compared such that two nodes are equal if they have the same class type, and if all input nodes have the same Node ID. + +### Start Node + +TODO + +### Region Node + +TODO + +### Return Node + +TODO + +### Constant Node + +TODO \ No newline at end of file -- cgit v1.2.3 From 00af1bb88668791e9da5d43c921e38348beec421 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 17:13:01 +0100 Subject: Revised based on feedback Added descriptions of the nodes. --- chapter01/README.md | 31 +++++++++++++++++-------------- 1 file changed, 17 insertions(+), 14 deletions(-) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index 0dee71be..62fafcd0 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -6,14 +6,14 @@ In this chapter we aim to compile simple scripts such as: return 1; ``` -The first statement to be implemented in the language is the `return` statement. -The `return` statement shall accept an argument, which must be an `expression`. -For this chapter, the language shall only have one type of `expression` - an integer literal, as +We will be implementing the `return` statement first. +The `return` statement accepts an `expression` as an argument. +For this chapter, the language only has one type of `expression` - an integer literal, as shown in the example above. Here is the [complete grammar](docs/01-grammar.md) of the language for this chapter. -To implement this simple language, we will need to introduce several components and data +To implement this simple language, we will introduce several components and data structures. ## Implementation Language @@ -59,14 +59,14 @@ 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 node value | 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. +Within a traditional basic block, instructions are executed in sequence. In the Sea of Nodes model, the correct sequence of instructions is determined by a scheduling +algorithm that depends only on dependencies between nodes (including control dependencies) that are explicit as edges in the graph. This enables a number of optimizations +at very little cost (nearly always small constant time) because all dependencies are always available. ### Unique Node ID @@ -78,16 +78,19 @@ Nodes will by default be compared such that two nodes are equal if they have the ### Start Node -TODO +The Start node represents the start of the function. For now, we do not have any values in the Start node, because in this chapter our function does not +accept any parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. However, +this will be subject of a later chapter. -### Region Node +### Constant Node -TODO +The Constant node represents the constant value. At present the only constants we allow are integer literals, hence the Constant node contains +an integer value. As we add other types of constants, we will need to refactor how we represent Constant nodes. -### Return Node +The Constant node has no inputs. Its output is the value stored in it. -TODO +### Return Node -### Constant Node +The Return node has two inputs. The first input is a control node. The second input is the data node that will supply the return value. -TODO \ No newline at end of file +The output of the Return node is the value it obtained from the data node. -- cgit v1.2.3 From e1ca5e63053d5d67fb77b35c773bb81ac502a58c Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 17:21:39 +0100 Subject: Fix typos --- chapter01/README.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index 62fafcd0..1d83c226 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -74,7 +74,7 @@ Each node will be assigned a unique Node ID upon creation. The Node ID will be a ### Node Comparisons -Nodes will by default be compared such that two nodes are equal if they have the same class type, and if all input nodes have the same Node ID. +Nodes will by default be compared such that two nodes are equal if they have the same class type, and all input nodes have the same Node ID. ### Start Node -- cgit v1.2.3 From e839f9b639e85d0383d3227f78118f55193518b3 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 17:26:08 +0100 Subject: Revised text --- chapter01/README.md | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index 1d83c226..6b2aebd1 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -6,10 +6,9 @@ In this chapter we aim to compile simple scripts such as: return 1; ``` -We will be implementing the `return` statement first. +We will implement the `return` statement first. The `return` statement accepts an `expression` as an argument. -For this chapter, the language only has one type of `expression` - an integer literal, as -shown in the example above. +For this chapter, the only `expression` type is an integer literal, as shown in the example above. Here is the [complete grammar](docs/01-grammar.md) of the language for this chapter. @@ -78,13 +77,13 @@ Nodes will by default be compared such that two nodes are equal if they have the ### Start Node -The Start node represents the start of the function. For now, we do not have any values in the Start node, because in this chapter our function does not -accept any parameters. When we add parameters, the value of the Start node will be a tuple, and will require Projection nodes to extract the values. However, +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. However, this will be subject of a later chapter. ### Constant Node -The Constant node represents the constant value. At present the only constants we allow are integer literals, hence the Constant node contains +The Constant node represents the constant value. At present, the only constants 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 has no inputs. Its output is the value stored in it. -- cgit v1.2.3 From 149c78c4921d5a653e3ff83ec3b1d02a90d0a42c Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 19:27:47 +0100 Subject: Add diagram --- chapter01/README.md | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index 6b2aebd1..4bd0c798 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -93,3 +93,13 @@ The Constant node has no inputs. Its output is the value stored in it. The Return node has two inputs. The first input is a control node. The second input is the data node that will supply the return value. The output of the Return node is the value it obtained from the data node. + +### Representation + +Here is visualization of the program: + +``` +return 1; +``` + +![Sea of Nodes Visual](./docs/02-graph.svg) -- cgit v1.2.3 From 7ec5a9425c7585a67dc834cfb762470e86695b41 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 20:53:53 +0100 Subject: Revise text and update diagram. Remove the detail re inputs to a node from the diagram. --- chapter01/README.md | 64 +++++++++++++++++++++++++++++------------------------ 1 file changed, 35 insertions(+), 29 deletions(-) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index 4bd0c798..679a5d5e 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -6,40 +6,42 @@ In this chapter we aim to compile simple scripts such as: return 1; ``` -We will implement the `return` statement first. +We implement the `return` statement. The `return` statement accepts an `expression` as an argument. -For this chapter, the only `expression` type is an integer literal, as shown in the example above. +The only `expression` type is an integer literal, as shown in the example above. -Here is the [complete grammar](docs/01-grammar.md) of the language for this chapter. +Here is the [complete language grammar](docs/01-grammar.md) for this chapter. -To implement this simple language, we will introduce several components and data -structures. +To implement this simple language, we introduce a few key components and data structures. ## Implementation Language Our implementation language is Java. We chose Java as it is widely available and understood. +## Assumptions + +We assume that the reader is familiar with traditional linear intermediate representations, and is familiar with terms such as Basic Block, Control Flow Graph, etc. No attempt is made to explain these topics. +If necessary the reader can consult a standard compiler text book. + ## Architecture -We will design our parser and compiler to illustrate some key aspects of the Sea of Nodes +We design our parser and compiler to illustrate some key aspects of the Sea of Nodes Intermediate Representation: -* We will construct the intermediate representation directly as we -parse the language. There will not be an intermediate Abstract Syntax Tree representation. +* We construct the intermediate Sea of Nodes representation directly as we parse the language. There is no Abstract Syntax Tree representation. -* The compiler will perform a few basic local optimizations as we build the -IR; this is a key benefit of the Sea of Nodes IR. +* The compiler will perform a few basic local optimizations as we build the IR; this is a key benefit of the Sea of Nodes IR. This aspect is more fully explored from Chapter 2 onwards. ## Data Structures -Our data structures will be based upon the descriptions provided in following papers: +Our data structures are based upon the descriptions provided in following papers: * [From Quads to Graphs: An Intermediate Representation's Journey](http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR93366-S.pdf) * [Combining Analyses, Combining Optimzations](https://scholarship.rice.edu/bitstream/handle/1911/96451/TR95-252.pdf) * [A Simple Graph-Based Intermediate Representation](https://www.oracle.com/technetwork/java/javase/tech/c2-ir95-150110.pdf) * [Global Code Motion Global Value Numbering](https://courses.cs.washington.edu/courses/cse501/06wi/reading/click-pldi95.pdf) -Following the lead from above, we will represent our intermediate representation using an object oriented data model. Details of the +Following the lead from above, we represent our intermediate representation using an object oriented data model. Details of the representation follow. ### Intermediate Representation as a Graph of Nodes @@ -53,15 +55,15 @@ 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. +The following control and data nodes appear 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 | -| Return | Control | Represents the termination of a function | Predecessor control node, Data node value | Return value of the function | -| Constant | Data | Represents constants such as integer literals | None | Value of the constant | +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|-----------------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Return | Control | Represents the termination of a function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Represents constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | -All control nodes will implement a marker interface named `Control`. +All control nodes 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 instructions is determined by a scheduling algorithm that depends only on dependencies between nodes (including control dependencies) that are explicit as edges in the graph. This enables a number of optimizations @@ -69,28 +71,29 @@ at very little cost (nearly always small constant time) because all dependencies ### Unique Node ID -Each node will be assigned a unique Node ID upon creation. The Node ID will be allocated in a particular compilation context. - -### Node Comparisons - -Nodes will by default be compared such that two nodes are equal if they have the same class type, and all input nodes have the same 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. ### 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. However, -this will be subject of a later chapter. +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. +We discuss this in detail in Chapter 9: Functions and Calls. ### Constant Node -The Constant node represents the constant value. At present, the only constants we allow are integer literals; therefore the Constant node contains +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 has no inputs. Its output is the value stored in it. +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. + +The Constant node'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 will supply the return value. +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 output of the Return node is the value it obtained from the data node. @@ -103,3 +106,6 @@ return 1; ``` ![Sea of Nodes Visual](./docs/02-graph.svg) + +* Control nodes appear as square boxes +* Control edges are in bold red \ No newline at end of file -- cgit v1.2.3 From a62c095bd2451a6c7341bcddd32c0073b9c78ac7 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 21:05:19 +0100 Subject: Revise description of Return node. --- chapter01/README.md | 3 +++ 1 file changed, 3 insertions(+) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index 679a5d5e..e5b79493 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -95,6 +95,9 @@ The Constant node's output is the value stored in it. 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. +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. + The output of the Return node is the value it obtained from the data node. ### Representation -- 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(-) (limited to 'chapter01/README.md') 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 From b1d28a7d1d7996aaaef67b7823725c47e97a7d88 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 18 Sep 2023 16:48:25 -0700 Subject: More edits to Chpt 1 Add the Evil static global var, with appriopriate comments. Drop the singleton class, and every place it had to be passed. Much smaller code now, and will be a LOT smaller as the project grows. Drop the opcode; minor usages in prior implementations for performance, not needed here. Use the preview pattern match in test code to simplify. --- chapter01/README.md | 35 ++++++++++++++++++++--------------- 1 file changed, 20 insertions(+), 15 deletions(-) (limited to 'chapter01/README.md') 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; ![Sea of Nodes Visual](./docs/02-graph.svg) * Control nodes appear as square boxes -* Control edges are in bold red \ No newline at end of file +* Control edges are in bold red -- cgit v1.2.3 From cecb62d847da7dc937b52857ae2fd4b41af98a7c Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Tue, 19 Sep 2023 21:30:41 +0100 Subject: Do not parse negative integers, - will be treated as unary operator. Update the comments for Return node. Sync comments with README. --- chapter01/README.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'chapter01/README.md') diff --git a/chapter01/README.md b/chapter01/README.md index 5a59ace8..f3231d8c 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -100,8 +100,8 @@ The Constant's value is the value stored in it. 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, 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. +In this presentation, Return functions as a Stop node, since multiple `return` statements are not possible. +The Stop node will be introduced in Chapter 6 when we implement `if` statements. The Return's output is the value from the data node. -- cgit v1.2.3