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
|
# Simple
A Simple showcase for the Sea-of-Nodes compiler IR
This repo is intended to demonstrate the Sea-of-Nodes compiler IR.
The Sea-of-Nodes is the core IR inside of HotSpot's C2 compiler
and Google's V8 compiler and Sun/Oracle's Graal compiler.
Since we are show casing the SoN IR, the *language* being implemented is less
important. We're using a very simple language similar to C or Java, but with
far fewer features. Simple is strongly typed, object-oriented, with first-class
*functions* not *closures*. Object references are pointers, and null
pointer exceptions are disallowed by the typing system. Arrays will probably
be range-checked at some point, making Simple a fully safe language. Simple
has a minimal syntax that can be parsed with a recursive descent parser.
The Sea-of-Nodes is used for machine code generation in these industrial
strength systems - but for this demonstration the backend is both difficult and
less important. This repo targets X86, RISC5 and ARM64 at least with
ahead-of-time compilation - but with an eye towards JIT compilation.
This repo also is not intended to be a complete language in any sense, and so
the backend starts with levering Java: the Evaluator (first appears in Chapter
10a) directly slowly interprets the SoN IR. Code-gen first appears in Chapter
19.
## Chapters
The following is a rough plan, subject to change.
Each chapter will be self-sufficient and complete; in the sense that each
chapter will fully implement a subset of the Simple language, and include
everything that was created in the previous chapter. Each chapter will also
include a detailed commentary on relevant aspects of the Sea Of Nodes
intermediate representation.
The Simple language is styled after a subset of C or Java.
* [Chapter 1](docs/chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement.
* [Chapter 2](docs/chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division
with constants. Peephole optimization / simple constant folding.
* [Chapter 3](docs/chapter03/README.md): Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a
constant.
* [Chapter 4](docs/chapter04/README.md): A non-constant external variable input
named `arg`. Binary and Comparison operators involving constants and `arg`.
Non-zero values will be truthy. Peephole optimizations involving algebraic
simplifications.
* [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction.
* [Chapter 6](docs/chapter06/README.md): Peephole optimization around dead control flow.
* [Chapter 7](docs/chapter07/README.md): `while` statement; looping constructs - eager phi approach.
* [Chapter 8](docs/chapter08/README.md): Looping constructs continued, lazy phi creation, `break` and `continue` statements.
* [Chapter 9](docs/chapter09/README.md): Global Value Numbering. Iterative peepholes to fixpoint. Worklists.
* Chapter 10a: User defined structs, pointers and null
analysis. One memory value in SSA. Loads, stores, and an executable evaluator.
* Chapter 10b: Equivalence class aliasing. Lazy memory
partitioning with `MemMerge`, `MemPhi`, and `BulkMemPhi`.
* Chapter 11: Global Code Motion - Scheduling.
* Chapter 12: Float type.
* Chapter 13: Nested references in Structs.
* Chapter 14: Narrow primitive types (e.g. bytes)
* Chapter 15: One dimensional static length array type, with array loads and stores.
* Chapter 16: Constructors
* Chapter 17: Mutability & Syntax Sugar: `var`, `val`, `x+=y`, `for(init; test; next) body`
* Chapter 18: Functions and calls.
* Chapter 19: Instruction selection and portable compilation
* Chapter 20: Graph Coloring Register Allocation
* Chapter 21: Instruction Encodings & ELF
* Chapter 22: A Simple Hello, World!
* Chapter 23: Methods and Types Revisited
* Chapter 24: Chained conditionals and SCCP
* Chapter 25: Modules, Separate Compilation, and SSA Construction with Incomplete Types
## Building across chapters
The optional [interactive graph viewer](graph/README.md) is shared in `graph/`.
Chapters 10a, 10b, and 18–25 launch it with `make view` from the chapter directory.
The top-level Makefile runs each chapter's `tests`, `tags` (also `tag`),
`release`, or `lib` target. Start with `make lib` on a fresh checkout, then
`make tests`.
The [chapter backport queue](docs/chapter-backports.md) records proposed small
corrections and the per-chapter test/review workflow. Larger architectural moves
are tracked separately there. The 10a/10b split is complete; forwarding 10b's
memory representation through Chapters 11-24 remains pending. Those snapshots
still use their earlier parser-managed alias chains.
To build and test just the memory chapters:
```sh
make lib tests release CHAPTERS="chapter10a chapter10b"
```
The root Maven reactor also includes both modules. Each chapter has its own
IDEA module descriptor and depends on the shared `graph` module. Chapter
directories with letter suffixes participate in the normal Make chapter discovery
and in the linear-history workflow.
|
