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 +++++++++++++++++-------------- chapter01/docs/01-grammar.md | 2 +- 2 files changed, 18 insertions(+), 15 deletions(-) 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. diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md index 63816e2e..7c5cb57a 100644 --- a/chapter01/docs/01-grammar.md +++ b/chapter01/docs/01-grammar.md @@ -20,6 +20,6 @@ primaryExpression ; INTEGER_LITERAL - : [0-9]+ + : [1-9][0-0]* ; ``` \ No newline at end of file -- cgit v1.2.3