1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
# Chapter 1
In this chapter we aim to compile simple scripts such as:
```
return 1;
```
We implement the `return` statement.
The `return` statement accepts an `expression` as an argument.
The only `expression` type is an integer literal, as shown in the example above.
Here is the [complete language grammar](docs/01-grammar.md) for this chapter.
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 design our parser and compiler to illustrate some key aspects of the Sea of Nodes
Intermediate 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. This aspect is more fully explored from Chapter 2 onwards.
## Data Structures
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 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 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, however Start node is set as input to enable graph walking | Value of the constant |
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
at very little cost (nearly always small constant time) because all dependencies are always available.
### 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.
### Start Node
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 Constant contains an integer value.
As we add other types of constants, we will refactor Constants.
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's output is the value stored in it.
### Return Node
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 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 is the value it obtained from the data node.
### Representation
Here is visualization of the program:
```
return 1;
```
* Control nodes appear as square boxes
* Control edges are in bold red
|
