blob: bb15e828daef6c738b471734f833f7c489863567 (
plain)
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
|
# Chapter 1
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.
### 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.
|
