diff options
Diffstat (limited to 'chapter25/README.md')
| -rw-r--r-- | chapter25/README.md | 371 |
1 files changed, 129 insertions, 242 deletions
diff --git a/chapter25/README.md b/chapter25/README.md index bbe0c50e..1dda8928 100644 --- a/chapter25/README.md +++ b/chapter25/README.md @@ -1,264 +1,151 @@ -# Chapter 25: Modules, Separate Compilation, and SSA Construction +# Chapter 25: SSA Before Types Are Known English | [日本語](README.ja.md) -[Previous: Chapter 24](../chapter24/README.md) | -[Chapter index](../README.md#chapters) +[Previous: Chapter 24b](../chapter24b/README.md) | +[Next: Chapter 26](../chapter26/README.md) -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. +The previous compiler solved for recursive types and calls, but its parser +still needs types to choose e.g. float-vs-integer arithmetic instructions or +field types. Forward references, external references, or even simple loop +structures can hide what's needed. -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). +This chapter records the operations first and resolves their type-dependent +parts later. Scalar types, numeric modes, conversions, guards, symbolic +fields, and unbounded value Phis and Loads have to get typed *together*, as +they all have mutually interlocking type dependencies. -Here is the [complete language grammar](docs/25-grammar.md) for this chapter. -## Compilation units and names +## A definition can follow its use -`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; +```simple +val add = { Later p -> return p.x + 1; }; +struct Later { flt x; }; +return add(new Later { x = 2.5; }); ``` -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 +When parsing `p.x + 1`, the compiler knows the receiver's name (type `Later`), +but not its fields! It makes a Load with a symbolic field offset `FldOff` and +an `Add` whose numeric mode is still unset: might be an integer add or a +floating-point add. Later we parse `Later`, which supplies the field and its +storage type. Type propagation then selects floating-point addition and +converts the integer `1` operand. The result is some floating point math +`2.5 + (flt)1`, which folds to `3.5`. + +Forward writes work the same way. Until a field is known, its Store carries +whole memory - it aliases everything until we know what it aliases. Once +resolved, the Store converts its value to the declared field type and updates +that field's alias, which generally will result in a cascade of peepholes +sharpening the memory edges. Resolving the alias preserves the Store's control +input. Update operators such as `x += y` work like `x = x + y`, while evaluating +the destination only once. Storing into a `u8` field may narrow an integer +result; storing into an `f64` field may instead convert it to floating point. + +`FldOff` deserves more mention: it represents a named field reference (Load or +Store) to an incomplete `TypeStruct`. In the example above, that's `p.x`: field +`x` of a `Later` whose fields are not yet declared. The struct can gain more +fields, and the field type itself is still unknown, so +`FldOff` really knows very little about what's going on. It's more of a *shape* +placeholder, and awaits stronger types to peephole into a "real" field +reference. + + +## Values need their own bounds + +The parser always knows when it has *values* vs memory or control, but maybe +not whether something is an int or a flt until much later. Instead it uses +`TypeScalar` for this. `TypeScalar` contains integers, floats, object +pointers, and function pointers. These are classic *values* in the sense that +they represent small concrete things that typically fit in a machine register. +Values exclude control and memory. Scalar bottom says that a value's family is +not known; its top represents an unreachable scalar result. A scalar union can +still be tested for truth, even when its alternatives use different families; +integers, floats, and pointers all carry a notion of zero. + +A scalar Phi now meets its live inputs; it no longer carries a parser-supplied +lower bound. An unfinished loop Phi starts at scalar bottom because its +backedge is missing. Parameters retain their declared interface types, and +memory Phis retain their memory role. Loop Phis, Parms, and recursive CallEnds +still do widening. + + +## Record conversions and branch facts + +The parser ends up inserting `Convert` nodes where it used to directly convert +values. This includes converting integers to match float operators and narrowing +values stored into integer fields. Loads derive their value types from memory; +they no longer impose a parser-supplied bound. A bad load or store still produces +bottom. Type checking looks through a conversion with an already-broken input +so it can report the original error. + +`Convert` records a known destination type, such as a local declaration or +function parameter. It waits for its input type to sharpen, and then peepholes +into a widening, truncation, permission check, or no operation. + +`Guard` records a branch fact: zero/null or nonzero/non-null. Its value family +comes from its input when known. The control edge keeps the fact on the path +where it was proved. A guard output is the same runtime value as its input; it +emits no instruction, just the sharpened type result. Guards are typically +used to track not-null pointer tests across large areas. + +Arithmetic nodes carry a `mode`: a 3-state enum tracking an unset, integer, or +floating-point mode. Known inputs can settle it during peepholes. SCCP +resolves remaining recursive numeric components, then propagates the result +again. Once the mode is known, the machine instruction selection sections will +pick the correct machine ops. + + +## Complete declarations, then update the graph + +```simple +val foo = { A a -> a.b; }; +struct A { B b; }; ``` -`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]); -``` +When parsing `foo`, we know that `a` points to an `A`, but not the fields of +`A` or the type of `a.b`. The load records that `A` must have a field named `b`. +Forward shapes (`A`) remain *open* until their declaration, as in prior +chapters. When parsing `struct A` we find `B`, but `B` here is never declared... and +does not need to be. -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. +After parsing, the compiler *closes* all declarations as a group, including +type cycles (such as a `struct LinkedList` having a `next` field typed as a +`LinkedList`) and references through function signatures. It then replaces old +type shapes in cached node types and stored declarations, preserving pointer +permissions and nullability. Declared types now have their complete field sets. +An undeclared type such as `B` may remain opaque: this example only passes its +pointer around and does not need to allocate a `B` or access its fields. -## Lazy class initialization +Closing declarations does not itself prove the program will type-check. -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. +At this point `FldOff` can begin to peephole into a `ConFldOff` - moving +from a symbolic field reference of an incomplete type to a concrete +field of a known type. Later, after structures get a *layout*, `ConFldOff` +will become a concrete field offset, a number like `4` or `8`. -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 construction boundary + +This snapshot keeps the preceding chapter's constructor model: collect field +values in the constructor scope, check completion, then allocate and initialize. +An unknown expression type is no longer evidence of an unwritten field, so the +completion check follows explicit missing-initialization values through merges. -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 `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. +Allocation helpers, hidden initializer calls, private self-memory, and explicit +publication belong to the next chapter. Escape discovery, source modules, lazy +class initialization, and serialized ideal IR follow later. These changes use +the existing conservative policy for functions exposed to unknown callers. +Method binding retains the preceding parser's requirement that the owner's +field declaration be known. Forward data fields are resolved here; moving +method and initializer bodies out of that parser scope is construction work. ## 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](../docs/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. +Run `make lib tests CTAGS=` here, or from the repository root run +`make tests CHAPTERS=chapter25 CTAGS=`. +`IncompleteTypesTest` exercises a forward field with deferred numeric mode and +a forward store whose byte width must be resolved. The inherited suite covers +recursive objects, null guards, initialization errors, loops, all three code +generators, and native calls. Earlier parse-only graph expectations now show +conversions that disappear after type propagation. |