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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
# Chapter 25: Modules, Separate Compilation, and SSA Construction
This chapter compiles Simple source files into reusable object files, loads
their types and ideal IR into later compilations, and links native programs
against a separately built system library. It also contains a substantial
parser, type, and memory-SSA redesign to support incomplete information.
These are the contents of the current snapshot. Independent correctness fixes
will move to earlier chapters first; moving the larger SSA redesign backward,
or splitting this chapter, is deferred. See the [backport queue](../docs/chapter-backports.md).
You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter25)
in the [linear history](https://github.com/SeaOfNodes/Simple/tree/linear) and
[compare it with Chapter 24](https://github.com/SeaOfNodes/Simple/compare/linear-chapter24...linear-chapter25).
## Compilation units and names
`CompUnit` represents a source or object file. `ParseAll` discovers dependencies,
parses needed sources, and loads previously compiled units. Source and build
trees use corresponding relative paths; class names use dotted paths. For
example, `a/b/foo.smp` supplies the namespace `a.b.foo`.
Each unit has Start/Stop nodes. A function's ownership by a compilation unit is
distinct from an edge representing unknown external callers: retaining code
for emission must not imply that arbitrary callers can reach it.
The driver accepts `--root` for the project root, `-o` for output, and `-L` for
external Simple object search paths, including an object file or a directory.
The compiler also resolves external C symbols for native linking. Names beginning
with `_` control privacy; public reachability depends on enclosing names too.
## Object files contain ideal IR
The ELF writer stores native code and a `.simple` section containing canonical
types, ideal graph nodes, and dependencies. The reader reconstructs that graph
so imported functions can participate in optimization, including inlining.
Calls that remain out of line are resolved by native linking.
`GlobalBits` maps file identities and per-file indices to local dense indices
for aliases, function targets, and return points. Equal local numbers from
independent compilations must not be mistaken for equal identities. Types are
closed and upgraded after loading, including cross-unit cyclic references.
Serialization preserves declaration types separately from sharpened flow types.
Every semantic node/type field needs matching read/write support. The source's
expensive serialization bijection check is currently disabled, and the larger
incremental-rebuild test `testModule0` is ignored. Neither is an active
validation guarantee.
## Constructing SSA before types are complete
Simple still parses directly to SSA without an AST. Forward references mean an
expression's eventual type may be unavailable while parsing it. Syntax and
resolved lexical binding therefore choose topology; types subsequently refine,
optimize, and validate the graph.
- Arithmetic nodes defer integer versus floating-point mode selection, including
resolution through recursive graph components after SCCP.
- Calls preserve their syntactic receiver slot before the callee kind is settled.
Symbolic field information defers layout-dependent decisions.
- Loads and ordinary Phis no longer carry parser-supplied lower-bound types.
- `TypeScalar` represents integer, float, memory-pointer, and function-pointer
values separately from global control/memory bottom.
- `TypeStruct._open` describes an incomplete field set; `_fref` records the
absence of an authoritative definition. Discovering fields does not define a type.
- Guards carry branch-proven zero/nonzero facts before the input family is known.
`FunPtrNode` retains an explicit edge to its function's return graph.
The driver runs parsing, pessimistic iteration, SCCP, and final type checking
before serialization and machine selection. Nontrivial inlining is coordinated
with iteration instead of always occurring as an immediate peephole.
## Memory and construction
The parser carries ordinary bulk memory. The optimizer recovers precise aliases
using `MemMerge`, `MemPhi`, and `BulkMemPhi`. A bulk Phi covers all aliases
except its exclusions, represented by parallel precise Phis. Every slice must
be covered exactly once.
User constructors are declared and called as follows:
```java
struct Box {
i64[] values;
new Box = { i64[] initial -> values = initial; };
};
return new Box(new i64[1]);
```
An allocation helper is generated at the declaration. It allocates, calls the
hidden `<init>` and then the user constructor, and publishes initialized private
memory through `EscapeNode`s. Parser `Var` metadata detects early field reads
and missing initialization on constructor exits. Store widths come from target
declarations, not from the values being stored.
File-level code is represented by a class initializer (`<clinit>`), distinct
from instance initialization. The older [module design notes](module.md) and
[roadmap](ROADMAP.md) contain proposals and alternatives, especially concerning
initialization order; they are not a specification of all implemented rules.
## System library and examples
The former single `sys.smp` library is organized into units for libc bindings,
I/O, characters, scanners, arrays, growable buffers, and bitsets. The native
driver supports real program arguments. Examples in `docs/examples` include
Bubble Sort, Capitalize, Dijkstra, and FileIO.
`Chapter25Test` exercises library loading and native linking, including a Hello
World call deliberately kept out of line. That test checks the client's external
symbol before linking against `sys.o`. Other tests cover forward constructors,
field updates through calls, literal escapes, and reduced compiler failures.
Independent regressions are candidates for earlier chapters.
## Building and checking
From this directory, `make lib` supplies Java test dependencies and `make tests`
runs the raw chapter suites, standalone suites, system tests, and fuzzer
regressions. `make release` builds the compiler jar and native library artifacts;
`make tags` builds editor tags. Native tools and the selected CPU/ABI must match
the environment; the Makefile currently defaults to x86-64/win64.
Compiler changes can invalidate both serialized IR and native code in `sys.o`.
Rebuild it before interpreting linked-program test results. A source-only subset
is not equivalent to this chapter's full `make tests`.
## RegAlloc improvements: live-range area and split cost
Chapter 24 tried cold copies before splitting a loop Phi's hot edges. This
chapter also estimates how much scheduled code a spill frees from register
pressure, divided by the estimated cost of the new copies. Callee-save ranges
cover a whole function. Cloneable constants can be rebuilt nearer their uses.
Copies inside loops cost more: the estimate weights them by `8^loopDepth`.
These are inexpensive approximations, especially for values with many uses.
The other Chapter 25 conflict-handling rules remain here: direct splitting of
several fixed-register uses and deeper splits for some multi-definition ranges.
Their size thresholds are heuristics, not general invariants to backport to the
first allocator. Shared legality fixes still start in the earliest affected
chapter. The final audit corrected fixed-neighbor color bias in 20-25, narrow
store masks in 20-21, and ARM register-bank/float-memory encoding in 21-25.
Run `make spill-stats`. Each row uses **Chapter 25's compiler**. The first five
rows preserve the earlier 212 program/target entries, adapted to this chapter's
syntax and library organization; the [fixture notes](src/test/java/com/seaofnodes/simple/spill/README.md)
list those adaptations and the measurement limits. They use optimizer seed 123.
The last row includes nine allocations from `Chapter25Test` at its existing
seeds plus a fresh system-library compilation at the driver's seed 456. Reusing
`sys.o` must not make that substantial workload disappear from the measurements.
These results are from Windows x86-64; earlier cohorts also include RISC-V/ARM
SystemV and x86 SystemV. The reporter prints per-target totals as well.
| Program cohort | Compilations | Split/move count | Loop-weighted count |
|---|---:|---:|---:|
| Chapter 20 | 39 | 381 | 612 |
| Chapter 21 | 52 | 464 | 1,185 |
| Chapter 22 | 24 | 103 | 131 |
| Chapter 23 | 30 | 122 | 346 |
| Chapter 24 | 67 | 744 | 1,479 |
| Chapter 25 | 10 | 783 | 1,826 |
| **Total** | **222** | **2,597** | **5,579** |
`_spills` counts retained SplitNodes, including register-to-register moves;
`_spillScaled` applies the loop weight. Neither measures just memory traffic.
The old cohorts are allocation replays with register-legality checks, not reruns
of their native harnesses. `Chapter25Test` still runs its native/result checks.
Use `make -j 4 tests` for the full chapter, including inherited emulator tests.
### Comments on the measurements
There is no uniform improvement to claim. Substituting Chapter 24's ranking
while keeping the rest of this compiler unchanged saves five moves on the 221
client compilations (2,206 / 4,719 versus 2,211 / 4,724), but fails to allocate
the system library within eight rounds. It is therefore an incomplete comparison,
not a lower valid whole-suite total. The existing area/cost ranking is retained;
the round limit and correctness checks are unchanged. The system library itself
contributes 386 moves / 855 weighted moves.
A trial that favored all multi-use cloneable constants saved one move against
the earlier ranking on those clients, but also failed the fresh library build.
It was rejected. This is why both aggregate statistics and complete compilation
and execution checks matter; a favorable subtotal cannot justify a change.
The earlier-cohort total rises from Chapter 24's 1,332 / 2,956 to 1,814 / 3,753.
Chapter 25 adds class initializers, module ownership, different escape analysis,
and syntax/library adaptations. These are different machine graphs; the increase
cannot be attributed to allocator quality alone. Compare a heuristic within one
compiler and fixed corpus before drawing conclusions from the chapter tables.
|
