path: root/docs/chapter25/README.md

# Chapter 25: Modules, Separate Compilation, and SSA Construction

English | [日本語](README.ja.md)

[Previous: Chapter 24](../chapter24/README.md) |
[Chapter index](../../README.md#chapters)

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.

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).

Here is the [complete language grammar](25-grammar.md) for this chapter.

## 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.

Explicit numeric C declarations bind directly to mutable native storage:

```java
i32 counter = "C";
counter += 1;
return counter;
```

The native linker resolves `counter`. Reads and writes access that C variable;
the declaration neither copies nor initializes it. Repeated declarations and
module imports share the same storage alias. Integer and floating-point data
bindings are supported; pointer and aggregate data bindings are not yet supported.
External fields carry a storage flag and occupy no bytes in their declaring
class. Layout resolves their field offsets to `ExternOffset` symbols; instruction
selection replaces class-base-plus-offset with the native symbol address.
Native object output uses the existing AMD64 ELF writer; ARM and RISC-V support
these addresses through the in-memory linker. Thread-local variables and C macros
need accessor functions: the system library exposes `libc.errno()` through a small
native runtime accessor.

Native function pointers still occupy four bytes. A native library can live
above that address range, so the AMD64 ELF writer gives each address-taken
native function a small entry in Simple's low-address code. The entry tail-jumps
through the native symbol's PLT entry; arguments and the return address pass
through unchanged. Direct calls still use the native symbol directly.

Static class fields and addresses computed in code both refer to that entry.
Its stable weak symbol, `__simple_native$<name>`, lets separately compiled
objects agree on one pointer when linked into an executable. The class image
uses a four-byte relocation to this defined entry, instead of a four-byte
relocation to a dynamic native symbol in writable data, which GNU ld rejects.
Constant field Stores can still fold away. The entry is a Simple function
identity; it need not equal the raw address obtained by native code.

`StaticDataTest.testNativeFunctionIdentity` reads two separately compiled class
images before their initializers run, compares their stored and computed
addresses, and calls the native function. It checks both object-link orders.

## 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.

The external-field flag and symbolic offsets change the serialized layout.
The magic remains `C0DE`; there is no separate format version yet. Rebuild all
Simple object files before importing them with this compiler.

## 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 separates optimization from lowering:

```text
Parse -> Iter -> Opto -> IterPostOpto -> FinalizeIR -> TypeCheck
      -> Serialize (when producing an object) -> Lower -> LoopTree
      -> Unlink -> Select -> Schedule -> LocalSched -> RegAlloc -> Encoding
```

`Opto` runs SCCP and resolves numeric modes. `IterPostOpto` applies peepholes
and inlining using those results; `FinalizeIR` settles field layouts and offsets.
Type checking sees the optimized ideal graph. Serialization saves that graph
before lowering introduces implementation details such as initialization guards.
For machine compilation, `Unlink` detaches imported function bodies before
instruction selection; calls retain the symbols needed for linking. Ideal-IR
evaluation keeps those bodies available and skips machine selection.

## 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.

## Lazy class initialization

File-level code is represented by a class initializer (`<clinit>`), distinct
from instance initialization. An active class-field access ensures that the
class is initialized. Taking a class reference is passive: it identifies the
class without running its body. Initialization runs once, on the path that
first needs it, and a parent initializes before its child.

For example, if `B.smp` computes `value`, then this code initializes B only
when `take` is true; the second access reuses the initialized class:

```java
return take ? B.value + B.value : 0;
```

The compiler represents the obligation with an opaque `CLInit` node. It carries
control, whole-memory effects, the class pointer, and a load of the hidden
`$init` flag. Its results include a memory slice where that flag is known true.
Ordinary memory SSA and load simplification can therefore remove repeated
checks, including after a merge when every incoming path has initialized the
class. Calls conservatively account for arbitrary memory effects.

After optimization, the compiler builds a graph containing function calls,
class touches, and parent requirements. A strongly connected component with
more than one class initializer is an error. Ordinary recursion and helper
cycles involving just one initializer are allowed. Checking after optimization
means eliminated branches and call targets do not create false dependencies.
Diagnostics show the cyclic edges and their source locations, including calls
through helpers and imported code.

Object files preserve opaque initialization nodes and their source locations.
Imported ideal bodies participate in the combined cycle check before lowering.
Lower then expands each remaining obligation into a flag test, a conditional
initializer call, and control/memory merges. The initializer owns the flag store;
the store is at body entry to support permitted same-class reentry. Cross-class
cycles have already been rejected. This is a single-threaded protocol.

The selected entry class receives the current integer `arg`; other initializers
receive zero. Planned argument arrays and further initialization optimizations
are described in the [roadmap](ROADMAP.md).

## 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 `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.

Serialized IR uses the `C0DE` header; pointer types include an independent
read-only access bit. The format is not versioned yet, so rebuild object files
after format changes. Backward compatibility is not currently supported.

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.

A single-use function address in the same block gets priority for
rematerialization when it is separated from its use.  Moving that address
calculation next to the use adds no instruction and avoids preserving a
callee-save register merely to hold the constant.  Adjacent uses and multi-use
addresses retain the area/cost ranking.

Rows are fixed test cohorts; columns are compiler chapters. Each cell gives
**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for
allocator copies/rematerializations, and x86's loop-weighted split-move estimate.
**Cases D / X** counts measured dynamic program/target cases and x86 compilations;
membership and inputs stay fixed across columns. Native-library work is excluded.
Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each
metric; see the [measurement details](../regalloc-spills.md) for coverage.

<!-- spill-matrix:start -->
| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | Ch 25: Ops / RA / X |
|---|---:|---:|---:|---:|---:|---:|---:|
| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | 58,965 / 9,076 / 208 |
| Ch 21 | 20 / 18 |  | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | 6,196 / 219 / 534 |
| Ch 22 | 14 / 8 |  |  | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | 252 / 92 / 11 |
| Ch 23 | 14 / 8 |  |  |  | 630 / 160 / 36 | 630 / 160 / 36 | 864 / 358 / 36 |
| Ch 24 | 36 / 20 |  |  |  |  | 4,923 / 1,341 / 790 | 4,646 / 1,335 / 609 |
| Ch 25 | 2 / 12 |  |  |  |  |  | 20 / 0 / 1,856 |
<!-- spill-matrix:end -->


Chapter25 introduces several features, which when run on the older tests
generate a lot more code, which in turn generates more spills.

Class initialization, inlining, escape analysis, and library adaptations
all change the graphs.  To help with this, we adjust the inlining
heursitics to try and get all the boilerplate to inline and optimize.