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 +++++++++++++++++++++++++-------------------- chapter01/docs/02-graph.gv | 28 +++----------------- chapter01/docs/02-graph.svg | 40 ++++++++++++---------------- 3 files changed, 55 insertions(+), 77 deletions(-) (limited to 'chapter01') 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 diff --git a/chapter01/docs/02-graph.gv b/chapter01/docs/02-graph.gv index a47c23fe..40181544 100644 --- a/chapter01/docs/02-graph.gv +++ b/chapter01/docs/02-graph.gv @@ -1,29 +1,9 @@ digraph chapter01 { - start [shape=none, label=< - - - - - - - -
Inputs
Start
- >]; + start [shape=box, label="Start"]; constant [label="Constant 1"]; - return [shape=none, label=< - - - - - - - - - -
Inputs01
Return
- >]; - constant -> return:input1; + return [shape=box, label="Return"]; + constant -> return; edge [color=red]; - start -> return:input0 [style=bold]; + start -> return [style=bold]; } \ No newline at end of file diff --git a/chapter01/docs/02-graph.svg b/chapter01/docs/02-graph.svg index 1ced4870..fbf92d7d 100644 --- a/chapter01/docs/02-graph.svg +++ b/chapter01/docs/02-graph.svg @@ -4,48 +4,40 @@ - - + + chapter01 - + start - -Inputs - -Start + +Start return - -Inputs - -0 - -1 - -Return + +Return -start->return:input0 - - +start->return + + constant - -Constant 1 + +Constant 1 -constant->return:input1 - - +constant->return + + -- cgit v1.2.3