From 51f1f8f4b871e3b52eb0c5d18b03f362a2b37791 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 25: add separate compilation and simplify SSA construction Introduce Chapter 25 with separately compiled Simple modules, serialized IR, cross-compilation-unit linking, and native system-library integration. This also completes a broad parser and type-system cleanup needed to make graph construction independent of incomplete parse-time type information. Separate compilation and linking - Add compilation-unit Start/Stop nodes and track functions, classes, aliases, and global indices across compilation-unit boundaries. - Serialize canonical types and ideal graph nodes into ELF objects, including dependency metadata, relocations, global/local bitset remapping, and dense memory-alias information. - Load dependent objects on demand, recursively resolve source and object paths, relink calls and function pointers, and preserve external C symbols. - Distinguish the post-optimization ownership hook from unknown callers so private call graphs can remain precise while public functions remain externally callable. - Add command-line and build support for compiling modules and the reusable `sys` object library. Parser, constructors, and SSA - Replace inline constructor expansion with a hidden default `` followed by an explicit user constructor declared as `new Type = { ... }`. - Keep the default constructor private, pass private object memory through constructor calls, and require user constructors to initialize non-default fields before the object escapes. - Track possibly-uninitialized fields in parser `Var` state and diagnose early reads without encoding parser-only constraints in Load and Store nodes. - Make ordinary parser memory bulk and recover precise alias slices in the optimizer using `MemMerge`, `MemPhi`, and `BulkMemPhi` nodes. - Remove parser-supplied type constraints from Loads and ordinary Phis, defer integer/float arithmetic selection, and keep call shape driven by syntax instead of provisional inferred types. - Preserve chained field declarations as static parser information when flow types are not yet available, including postfix field updates through calls. Types, functions, and escape analysis - Add `TypeScalar` as the common lattice family for integer, float, memory pointer, and function-pointer values, with scalar TOP/BOT values for generic Loads, Stores, parameters, and invalid intermediate expressions. - Represent unresolved struct definitions directly with the `TypeStruct` forward-reference flag while retaining the separate open-structure concept; close and canonicalize recursive structures without side maps. - Add explicit `FunPtrNode` references so constant function pointers retain a graph edge to their Return, and keep referenced functions alive until Opto proves the pointer dead. - Refine public-function and class-initializer escape handling, including public-only fallback escape sets and monotone compilation-unit summaries. - Add guards, proof casts, read-only propagation, pointer-to-integer conversion for non-null FFI arguments, and consistent deep mutability checks at calls. Optimization and code generation - Make weak and unresolved graph inputs compute conservatively and monotonically throughout iterative peepholes and SCCP. - Preserve independent memory slices when sharpening Stores, retain control on conditional Stores, and freeze Store widths from their target field types. - Extend serialization for new node kinds, scalar types, Store modes, function pointers, and memory partitions, preserving serialize/deserialize bijection. - Complete native selection and encoding support across x86-64, RISC-V, and ARM, including FFI pointer conversion and missing integer operations. - Fix x86 immediate multiply REX encoding and assorted scheduling, register allocation, spilling, relocation, and constant-pool issues exposed by the larger linked graphs. System library, tests, and documentation - Compile and link the Simple `sys` library, including libc bindings, I/O, scanners, strings, vectors, array helpers, and executable entry points. - Add Chapter 25 module, serialization, constructor, forward-reference, postfix-update, system, Hello World, and Bubble Sort coverage; update golden graphs and spill expectations for the new IR shape. - Add module and type-system documentation, parser-simplification design notes, grammar updates, examples, diagrams, and graph visualization assets. The resulting compiler passes the raw Chapter 1-24 suite and the Chapter 25 system and separate-compilation tests, including a freshly rebuilt `sys.o` and the native Bubble Sort example. --- skills/chapter25-codex-notes.md | 164 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 164 insertions(+) create mode 100644 skills/chapter25-codex-notes.md (limited to 'skills/chapter25-codex-notes.md') diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md new file mode 100644 index 00000000..4753d2e9 --- /dev/null +++ b/skills/chapter25-codex-notes.md @@ -0,0 +1,164 @@ +# Codex notes for Simple Chapter 25 + +This file is intentionally AI-facing. It records durable invariants, debugging +habits, and project-owner preferences that are easy to miss when reading only +the implementation. `WIP-HANDOFF.md` and `parser-simplification-plan.md` retain +the detailed history; portions of their old branch/status reports are stale +after the Chapter 25 squash. + +## Collaboration preferences + +- Cliff often debugs the same failure in parallel. If asked to work in a side + repository, update `tmp/` and do not edit the live files he is debugging. +- Stop and discuss before changing a central lattice, constructor, memory, or + call-graph invariant if the required fix starts cascading. Reduced tests and + concrete node-number traces are preferred over speculative broad rewrites. +- Printers are valid debugging tools. If printing changes behavior, fixing the + printer/accessor side effect is immediately high priority. +- Preserve unrelated dirty changes. Emacs lock/backup files are common and are + not permission to clean the tree. +- Do not push without explicit approval. Prefer commits at meaningful test + frontiers with messages describing the architectural change. + +## Central parser rule + +Simple parses directly to SSA without an AST. Forward declarations mean types +can be incomplete during parsing. The governing rule is: + +> Syntax and resolved lexical binding choose SSA topology. Types may sharpen, +> optimize, and reject the graph, but provisional types must not choose its +> shape. + +Consequences: + +- `compute()` must accept the weakest legal inputs and remain monotonic. +- Parser-only lower bounds such as the old Load/Phi `_con` fields are suspect. +- Calls keep syntactic shape. `ptr.field(args)` supplies `ptr` in the hidden + self slot even before the eventual function kind is known. +- Numeric operations carry an unresolved mode until graph evidence settles + integer versus floating behavior. +- A Load flow type is not guaranteed during parsing. Static declaration facts + may instead be recovered from symbolic field offsets or lexical `Var` state. + +## Constructors + +- A user constructor is declared `new N = { args -> body }` and invoked as + `new N(args)`. +- Allocation first calls the hidden private ``, then the user constructor. +- Constructor hidden arguments are public memory at index 1, self at index 2, + private self-memory at index 3, followed by user arguments. +- Constructors return private self-memory. `EscapeNode`s publish it into public + memory after construction. +- The hidden initializer supplies defaults/poison. User constructors must set + non-defaultable fields on every exit before the object escapes. +- Constructor field state is tracked in parser `Var` metadata. Early reads of + possibly-uninitialized fields are errors. +- Recursive constructors may reasonably be rejected; constructor chaining must + preserve private-memory initialization state. + +## Memory and alias invariants + +- The parser carries one ordinary bulk-memory value. Precise alias partitioning + belongs to the graph and optimizer, not nested parser Scope state. +- Alias `#1` is bulk/unresolved memory. A precise alias is `#N`, with `N != 1`. +- `MemMerge` inputs are disjoint slices whose union covers all memory. Its + default input means all aliases not explicitly split out. +- `BulkMemPhi` carries `All - exclusions`; parallel `MemPhiNode`s carry the + aliases in the exclusion set. +- A precise consumer may select `MemMerge.alias(N)`. A bulk consumer may not + silently replace a `MemMerge` with `alias(1)` because that discards every + precise side effect. +- In particular, Store-after-MemMerge bypass is valid only when the Store + already has a precise alias. This is covered by Chapter25Test's chained + `grow(1).buf[len++]` regression. +- When an unresolved Store sharpens, rebuild a precise Store plus `MemMerge`; + do not mutate a whole-memory Store in place after users have treated it as + the complete memory state. +- Stores retain control when it represents conditional execution. Removing + the control from the Store after an early return can make the write execute + unconditionally. +- Store width is semantic state (1/2/4/8 bytes, with 0 unresolved) and comes + from the target field declaration, never from the stored value's GLB or the + removed parser constraint. + +## Types and monotonicity + +- The type lattice must remain complete, symmetric, and bounded. Run TypeTest + after changing Type/Field equality, hashing, duality, meet/join, interning, + serialization, or gather sets. +- `TypeScalar` contains the scalar values ordinary Loads and Stores handle: + integers, floats, memory pointers, and function pointers. Scalar TOP/BOT sit + inside global TOP/BOT and avoid interpreting global BOT as all functions. +- `TypeStruct._open` means fields may still be discovered. `_fref` means the + named structure has been referenced but never authoritatively defined. A + real definition meets away `_fref`; field discovery alone does not. +- Moving an unresolved pointer or checking it for null is valid. Operations + requiring layout or fields must eventually diagnose a never-defined struct. +- `TypeNil` owns pointer nullability. Required pointer fields begin nullable as + an initialization poison and must become their declared non-null type. +- One-step idealization must preserve the type knowledge already established. + `IterPeeps.progressOnList` and `Opto.worklistCheck` are invariant checks, not + assertions to weaken. +- Worklist order must not affect semantics. Rotate deterministic seeds to + expose missing dependencies; never fix a bug by merely favoring one order. + +## Functions and escape analysis + +- A constant Simple function address must be a `FunPtrNode`, not an ordinary + `ConstantNode`, so the pointer retains an edge to the function Return. +- Before Opto, a live FunPtr keeps its function callable even if no Call is + currently linked. After Opto, an orphan FunPtr may remain as a null/equality + sentinel while the function body becomes dead; this deserves careful error + checking rather than a pre-Opto deletion. +- Extern C functions have no Simple FunNode/Return and are handled only while + linking. +- Unknown-caller Start edges and post-Opto compilation-unit ownership are + separate concepts. Do not overload Start edges merely to keep surviving + functions attached to a compilation unit. +- A global escape fallback means all public functions, not all functions. + Public `` functions escape when their class and all ancestor names + are public (no direct name component begins with `_`). +- Escape summaries are monotone discovery facts. If a later SCCP state widens + to FULL/public-only, it must not forget precise private bits discovered from + the same Return earlier. + +## Serialization and code generation + +- Object files carry canonical types plus ideal Simple IR. Every new semantic + type field, node field, tag, alias map, or mode needs balanced serialization, + deserialization, type upgrading, equality, and bijection testing. +- Avoid smart peepholes after Opto. Machine selection briefly has incomplete + graph edges, and GVN already guarantees uniqueness where required. +- `PtrToIntNode` is the explicit non-null pointer-to-integer conversion used for + C FFI calls. User code must handle null before converting. +- x86 REX arguments are `(ModRM.reg, ModRM.r/m, SIB.index)`. Keep that ordering + aligned with `modrm`; reversing it silently selects the wrong extended + registers. The Chapter 25 Bubble Sort failure exposed this in `MulIX86`. + +## Debugging workflow + +1. Reduce the first semantic or invariant failure before changing architecture. +2. Refer to graph nodes by class and node ID, e.g. `Store#107`. +3. Find the first phase or IterPeeps count where the graph becomes wrong. +4. For memory bugs, verify both exactly-once alias coverage and that a precise + consumer never requests an alias excluded from bulk without a parallel slice. +5. Distinguish ideal-graph correctness from selection, scheduling, register + allocation, and byte encoding. Compare IR, `CodeGen.asm()`, and `objdump`. +6. Rebuild `sys.o` after compiler changes that affect serialized IR or native + code; stale system objects can make results appear inconsistent. + +Useful test ladder: + +```text +focused test +chapter test +make tests_raw0 +make tests_raw1 +make tests_alone +TypeTest after lattice changes +serialize/deserialization bijection after persisted graph changes +``` + +As of the Chapter 25 squash preparation, `make tests_raw0` passes 360 tests and +Chapter25Test passes its system, Hello World, and Bubble Sort coverage with a +freshly rebuilt `sys.o`. -- cgit v1.2.3