From 489672dfac7efc78fc239ba7c2dfc82f1c5fbeab Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 24 Oct 2026 15:41:48 -0700 Subject: Finish chapter numbering, retire combined chapter 24, and update documentation --- docs/2026_REBASE/README.md | 6 +- docs/2026_REBASE/deck.js | 4 +- docs/2026_REBASE/slides.js | 2 +- docs/2026_REBASE/stdlib.js | 2 +- docs/2026_REBASE/tools/snapshot-library.py | 4 +- docs/appendices/README.md | 15 ++++ docs/appendices/current-spill-matrix.md | 14 +++ docs/appendices/native-libraries.md | 67 +++++++++++++++ docs/appendices/optimizer-tuning.ja.md | 26 ++++++ docs/appendices/optimizer-tuning.md | 65 ++++++++++++++ docs/chapter-backports.md | 131 ++++++++++++++--------------- docs/chapter-split.md | 100 +++++++++++++++------- docs/incremental-builds.md | 63 ++++++++++++++ docs/regalloc-spills.md | 15 +++- docs/stage-audit.md | 82 ++++++++++++++++++ 15 files changed, 484 insertions(+), 112 deletions(-) create mode 100644 docs/appendices/README.md create mode 100644 docs/appendices/current-spill-matrix.md create mode 100644 docs/appendices/native-libraries.md create mode 100644 docs/appendices/optimizer-tuning.ja.md create mode 100644 docs/appendices/optimizer-tuning.md create mode 100644 docs/incremental-builds.md create mode 100644 docs/stage-audit.md (limited to 'docs') diff --git a/docs/2026_REBASE/README.md b/docs/2026_REBASE/README.md index 4c3b5114..95bd1dea 100644 --- a/docs/2026_REBASE/README.md +++ b/docs/2026_REBASE/README.md @@ -104,7 +104,7 @@ before the session so compilation does not consume stage time: make -C chapter08 build CTAGS= make -C chapter17b build CTAGS= make -C chapter18 build CTAGS= - make -C chapter25 build CTAGS= + make -C chapter28b build CTAGS= The deck's **Copy viewer command** button gives one of these commands: @@ -112,7 +112,7 @@ The deck's **Copy viewer command** button gives one of these commands: make -C chapter08 view make -C chapter17b view make -C chapter18 view - make -C chapter25 view + make -C chapter28b view The Chapter 24 SCCP slide deliberately launches **Chapter 25's viewer** for this talk, using the same example with a separately compiled standard library. @@ -231,7 +231,7 @@ fixed-point theory works” and “It’s a rich lattice, so we get rich results Regenerate with Chapter 24 built and Graphviz installed: ```sh -java -ea --class-path chapter24/build/classes/main docs/2026_REBASE/tools/RichLattice.java +java -ea --class-path chapter24b/build/classes/main docs/2026_REBASE/tools/RichLattice.java dot -Tsvg docs/2026_REBASE/assets/rich-lattice.gv -o docs/2026_REBASE/assets/rich-lattice.svg ``` diff --git a/docs/2026_REBASE/deck.js b/docs/2026_REBASE/deck.js index 06a4e9d5..3250e7ae 100644 --- a/docs/2026_REBASE/deck.js +++ b/docs/2026_REBASE/deck.js @@ -47,8 +47,8 @@ window.REBASE = { }, { "id": "sccp", - "chapter": "chapter24", - "viewerChapter": "chapter25", + "chapter": "chapter24b", + "viewerChapter": "chapter28b", "title": "Prove a loop-carried constant", "code": "int x = 1;\nfor( int i = 0; i < arg; i++ )\n x = 2 - x;\nreturn x;\n", "result": "Return value is always 1", diff --git a/docs/2026_REBASE/slides.js b/docs/2026_REBASE/slides.js index 9ed9729e..a3a8aef6 100644 --- a/docs/2026_REBASE/slides.js +++ b/docs/2026_REBASE/slides.js @@ -186,7 +186,7 @@ ])+'
ValueInitialFixed point
Loop Phi⊤1
2 − Phi⊤1

After SCCP, the program is fully typed.
SCCP is the type analysis pass.

', notes:notes('Optimism earns its keep',[ 'Use the source as a concrete loop, but the equations are SSA pseudocode. The pessimistic fixed point cannot discover x=1 through the cycle.', - 'For this talk, Copy viewer command launches make -C chapter25 view. Chapter 25 demonstrates the same SCCP example using its separately compiled standard library, avoiding Chapter 24’s thousands of library capture frames. The slide topic and lattice remain Chapter 24.', + 'For this talk, Copy viewer command launches make -C chapter28b view. Chapter 25 demonstrates the same SCCP example using its separately compiled standard library, avoiding Chapter 24’s thousands of library capture frames. The slide topic and lattice remain Chapter 24.', 'Use Rich lattice for the big picture, then return to Example. The entry value sharpens the Phi to 1; the backedge evaluates to 1 and confirms it. Explain the direction of monotonicity, not just “assume it works.”', 'Control propagation makes the solve conditional. Chapter 24 also discovers interprocedural call-graph edges; Chapter 18’s local linking was only the beginning.' ],'

Target time: 28:00. Continue to the closing slide, or use Overview → Chapter 25 if two minutes remain and replace the closing discussion.

') diff --git a/docs/2026_REBASE/stdlib.js b/docs/2026_REBASE/stdlib.js index 22c92fe4..baf3af78 100644 --- a/docs/2026_REBASE/stdlib.js +++ b/docs/2026_REBASE/stdlib.js @@ -1,6 +1,6 @@ /* Generated by tools/snapshot-library.py; local source snapshot. */ window.REBASE.library = { - "origin": "chapter25/src/main/smp", + "origin": "chapter28b/src/main/smp", "files": { "sys.smp": "\n// top-level default standard library import\n\nval adt = adt; // Abstract Data Types\nval ary = ary; // Array utilities\nval aryi64 = aryi64; // Variable sized array of i64\nval aryu8 = aryu8; // Variable sized array of u8\nval char = char; // Character utilities\nval io = io; // IO library\nval libc = libc; // libc FFI bindings\nval scan = scan; // A simple string parser\n", "sys/adt/bitset.smp": "\n// A set of non-negative integers, represented one bit per value.\nstruct bitset {\n i64[] !_bits;\n\n new bitset = { ->\n _bits = new i64[1];\n };\n\n // Return 0 for missing, non-zero for true\n val get = { int bit ->\n if( (bit >> 6) >= _bits# ) return false;\n i64 mask = 1 << (bit & 63);\n return (_bits[bit >> 6] & mask);\n };\n\n val _grow = { int bit ->\n int x = bit >> 6;\n int len = _bits#;\n if( x < len ) return self;\n while( x >= len ) len *= 2;\n var bits = new i64[len];\n for( int i=0; i<_bits#; i++ )\n bits[i] = _bits[i];\n _bits = bits;\n return self;\n };\n\n // Set\n val set = { int bit ->\n i64 mask = 1 << (bit & 63);\n _grow(bit)._bits[bit >> 6] |= mask;\n return self;\n };\n\n // Test and set\n val tset = { int bit ->\n int idx = bit >> 6;\n i64 mask = 1 << (bit & 63);\n if( _grow(bit)._bits[idx] & mask )\n return true; // Already set\n _bits[idx] |= mask;\n return false; // Was false (and now set)\n };\n\n val clr = { int bit ->\n if( (bit >> 6) >= _bits# ) return self;\n i64 mask = 1 << (bit & 63);\n _bits[bit >> 6] &= (mask ^ -1);\n return self;\n };\n\n val clear = { ->\n for( int i=0; i<_bits#; i++ ) _bits[i] = 0;\n return self;\n };\n};\n", diff --git a/docs/2026_REBASE/tools/snapshot-library.py b/docs/2026_REBASE/tools/snapshot-library.py index dee09d2f..1a4b8732 100644 --- a/docs/2026_REBASE/tools/snapshot-library.py +++ b/docs/2026_REBASE/tools/snapshot-library.py @@ -4,10 +4,10 @@ import json deck = Path(__file__).resolve().parents[1] repo = deck.parents[1] -source = repo / "chapter25/src/main/smp" +source = repo / "chapter28b/src/main/smp" paths = [source / "sys.smp", *sorted((source / "sys").rglob("*.smp"))] files = {path.relative_to(source).as_posix(): path.read_text(encoding="utf-8") for path in paths} -bundle = {"origin": "chapter25/src/main/smp", "files": files, +bundle = {"origin": "chapter28b/src/main/smp", "files": files, "methods": (deck / "demos/methods.smp").read_text(encoding="utf-8")} (deck / "stdlib.js").write_text( "/* Generated by tools/snapshot-library.py; local source snapshot. */\n" diff --git a/docs/appendices/README.md b/docs/appendices/README.md new file mode 100644 index 00000000..d7803c97 --- /dev/null +++ b/docs/appendices/README.md @@ -0,0 +1,15 @@ +# Appendices + +These notes supplement the numbered compiler snapshots; they do not introduce +another compiler directory. + +- [Native library construction](native-libraries.md): bundled `sys`, native + symbols and thunks, runtime support, and executable examples in Chapter 28b. +- [Optimizer and backend tuning](optimizer-tuning.md): spill ranking, + rematerialization, inlining, and historical measurements from the split's + original snapshots. [Measurement methods](../regalloc-spills.md) describe + what those numbers include. + +The [roadmap](../roadmap.md), [incremental build design](../incremental-builds.md), +and [review queue](../chapter-backports.md) distinguish future work from current +behavior. The [stage audit](../stage-audit.md) records known limits and cleanup. diff --git a/docs/appendices/current-spill-matrix.md b/docs/appendices/current-spill-matrix.md new file mode 100644 index 00000000..df253a46 --- /dev/null +++ b/docs/appendices/current-spill-matrix.md @@ -0,0 +1,14 @@ +# Current allocator comparison + +`make spill-stats` measures Chapters 20, 21, 22, 23, 24b, and 28b against the +historical test cohorts. Cohort IDs and test names retain their old numbers; +column headings identify the current compiler directories. + +These are separate from the dated [pre-split measurements](../regalloc-spills.md). +After a successful run, `python build-support/spill-matrix.py --reuse --update-docs` +updates only this table. Fresh logs use 24b/28b names so old 24/25 results cannot +silently become measurements of new compiler snapshots. + + +No post-split measurement has been published yet. + diff --git a/docs/appendices/native-libraries.md b/docs/appendices/native-libraries.md new file mode 100644 index 00000000..14cf0c6b --- /dev/null +++ b/docs/appendices/native-libraries.md @@ -0,0 +1,67 @@ +# Native library construction + +The complete compiler is [Chapter 28b](../../chapter28b/README.md). This appendix +collects the library and native support that accompanied the old combined +Chapter 25. The split preserves that functionality in Chapter 28b. + +## Building the library + +From `chapter28b`, run: + +```sh +make lib release +``` + +Make builds `build/release/Simple.jar` and, under the selected CPU/ABI directory, +`sys.o` and `simple_crt.o`. The default CPU is x86-64; the default calling +convention is win64 on Windows and SystemV elsewhere. Rebuild serialized +objects after changing the compiler or object format. + +`src/main/smp/sys.smp` exposes child units for native libc bindings, I/O, +characters, scanners, arrays, growable buffers, and bitsets. These compile into +one `sys.o`. Clients import its declarations and ideal IR and link calls that +remain out of line. Currently selecting that object loads all its saved IR; +member-selective loading and reliable incremental rebuilding remain future work. + +The `simple.sh`, `simple.ps1`, and `simple.bat` launchers set `SIMPLE_HOME` so +the compiler can find the release library. The CLI accepts `-L` for additional +Simple objects or search directories. The chapter README gives an explicit +library/client example that needs no library source in the client root. + +## Native symbols and pointer sizes + +Native function calls and numeric native data symbols have ELF relocations. +The historical `Chapter25Test.testExternDataEncoding` and `testExternDataImports` +exercise native data; `StaticDataTest` covers addresses +and static images. A data symbol names storage, whereas a function symbol names +callable code; loading the former and calling the latter require different IR. + +Simple function pointers currently occupy four bytes. On AMD64, a native +function address names a low-address tail-jump thunk, which can reach native +code outside that range. A weak symbol gives static fields and computed +addresses the same entry across objects; direct calls can still use the native +PLT. This preserves constant initialization of function fields without storing +an eight-byte native address in a four-byte slot. The native linker must place +these Simple entries in the representable address range. + +Data pointers still occupy eight bytes. Compact code/data arenas and distinct +full-width native pointer types are [future designs](../roadmap.md#compact-code-and-data-arenas). + +## Runtime and examples + +`src/main/c/simple_crt.c` supplies the errno accessor and converts native process +arguments to Simple byte arrays for an exported `simple_main` function. This +explicit function entry is distinct from the language's class initializer: +the selected initializer still receives the integer `arg`. General class +initializer argument arrays remain a roadmap item. + +The executable examples live in +[`src/test/smp/examples`](../../chapter28b/src/test/smp/examples): Hello World, +Bubble Sort, Capitalize, Dijkstra, and FileIO. The existing Chapter25Test tests +compile and link them through the native harness. `make tests` builds the +library/runtime prerequisites and runs those checks; a Java-only build does +not produce the native prerequisites. + +The compiler's in-memory evaluator and the native driver have different entry +interfaces. Use the matching harness when comparing their results, especially +for programs taking an argument array or performing I/O. diff --git a/docs/appendices/optimizer-tuning.ja.md b/docs/appendices/optimizer-tuning.ja.md new file mode 100644 index 00000000..96c1b130 --- /dev/null +++ b/docs/appendices/optimizer-tuning.ja.md @@ -0,0 +1,26 @@ +# 最適化とバックエンドの調整 + +These measurements are from the numbered snapshots before the 2026-10 split. +In this historical table, Ch 24 means the retired combined SCCP snapshot and +Ch 25 means the retired combined modules/constructor/import snapshot. +They are not new measurements of the extracted chapters. The implementation +continues in [Separate Compilation](../../chapter28b/README.md). + +## RegAlloc の改良: 生存区間の面積と分割コスト + +第24章はループ Phi の高頻度辺を分割する前に、低頻度のコピーを試しました。この章ではさらに、スピルがスケジュール済みコードのどれだけをレジスタ圧力から解放するかを推定し、新しいコピーの推定コストで割ります。callee-save 区間は関数全体を覆います。複製可能な定数は使用の近くで再構築できます。ループ内のコピーは高コストなので、`8^loopDepth` で重み付けします。特に多数の使用を持つ値については、低コストな近似です。 + +複数の固定レジスタ使用を直接分割する規則や、一部の複数定義区間をより深く分割する規則など、第25章のほかの衝突処理はここに残します。サイズのしきい値はヒューリスティックであり、最初の割り当て器へバックポートすべき一般的不変条件ではありません。共有される合法性修正は、引き続き最も早い該当章から始めます。最終監査は第20〜25章の固定隣接ノードの色バイアス、第20〜21章の狭いストアマスク、第21〜25章の ARM レジスタバンク／浮動小数点メモリエンコーディングを修正しました。 + +第21章の隣接コピー転送も引き継ぎます。次の命令だけで使うコピーは、オペランドがコピー元レジスタを受け入れ、命令の結果に結び付けられていなければ除去します。 + +現在の比較は、固定したテスト群を行、コンパイラの章を列にした +[英語版の測定表](optimizer-tuning.md#regalloc-improvements-live-range-area-and-split-cost) を参照してください。 +各セルは ARM/RISC-V の実行命令数、そのうち割り当て器が生成したコピーなどの命令数、 +x86 のループ重み付き移動数を示します。これらは異なる指標です。 +対象、入力、除外項目は [測定方法](../regalloc-spills.md) にあります。 +古い測定群の集計値と混ぜて比較しないでください。 + +クラス初期化、インライン化、エスケープ解析、ライブラリの変更もグラフを変えます。 +章をまたぐ差を割り当て器だけの品質差と解釈せず、同じ入力とコンパイラで +ヒューリスティックを比較してください。 diff --git a/docs/appendices/optimizer-tuning.md b/docs/appendices/optimizer-tuning.md new file mode 100644 index 00000000..11dbcdf3 --- /dev/null +++ b/docs/appendices/optimizer-tuning.md @@ -0,0 +1,65 @@ +# Optimizer and backend tuning + +These measurements are from the numbered snapshots before the 2026-10 split. +In this historical table, Ch 24 means the retired combined SCCP snapshot and +Ch 25 means the retired combined modules/constructor/import snapshot. +They are not new measurements of the extracted chapters. The implementation +continues in [Separate Compilation](../../chapter28b/README.md). + +## RegAlloc improvements: try cold loop splits first + +A loop Phi and its backedge can belong to one live range even though their +values must coexist at some instruction. This self-conflict requires splitting +the range. Chapter 23 split the Phi's definition and incoming values right away. +This chapter first leaves the hot definition/backedge alone and tries the +outside-loop copies. If coloring succeeds, it avoids moves on every iteration. +Other conflicts, including two-address operations, keep their existing handling. + +The allocator remembers which Phis have had this chance. If the same Phi +self-conflicts again, the next attempt uses the ordinary aggressive splitting. +The record uses Phi identity because live ranges are rebuilt each round. It +also covers a backedge-only conflict where the first attempt inserts no copy: +that attempt must still consume the one permitted delay. A regression checks +both the cheaper first attempt and the mandatory fallback. + +## 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. + + +| 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 | + + + +Chapter 25 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 +heuristics to try to inline and optimize the boilerplate. diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index a7d3cfca..6e6d1d5c 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -4,32 +4,14 @@ This file tracks pending backports and deferred work. Completed work and old validation results belong in Git history. Reusable implementation constraints live in the [AI notes](../skills/chapter25-codex-notes.md). -The [approved chapter split](chapter-split.md) owns the teaching sequence for -the current Chapters 24 and 25. Use descriptive chapter names while the count -changes. Cliff approved starting with the proposed SCCP and construction/escape -boundaries; revisit construction/escape after he can run both snapshots. -Library construction and optimizer tuning move to appendices. - -The first named snapshots are `chapter-sccp`, `chapter-interprocedural-sccp`, -`chapter-incomplete-types`, `chapter-construction`, `chapter-escape`, and -`chapter-modules`. -Local SCCP keeps unknown callers and the call result summaries from pessimistic -analysis; the next chapter discovers calls -and widens recursive arguments and returns. Numbered Chapters 24 and 25 remain -comparison baselines during extraction. - -The incomplete-type snapshot groups numeric modes, conversions, guards, -symbolic fields, and unbounded Load/Phi nodes. Construction now has hidden -initializer/allocator calls, local field values and Phis, exit Stores, and -explicit publication. Private memory carries fields between helpers. Escape -now discovers exposed aliases/functions through the Start/Stop cycle. Review -the construction/escape border as needed. Modules/lazy initialization now has a -runnable snapshot; separate compilation is next. Chained comparisons still need -their move to Chapter 23; allocator tuning and native library material still -need their appendices. -Root Make includes named snapshots in checks. Linear-history publication keeps -the numbered sequence until the complete replacement sequence is ready; switch -its ordering and index links when retiring the comparison baselines. +The [completed split](chapter-split.md) places local/interprocedural SCCP in +24a/24b, incomplete types in 25, construction in 26, escape in 27, and +modules/separate compilation in 28a/28b. The combined old 24/25 snapshots are +retired. Do not backport fixes into those retired copies; their replacements +already retain the constructor, alias, native-exposure and import fixes. + +Native library construction and tuning material live in [appendices](appendices/README.md). +Future incremental builds are specified in [incremental-builds.md](incremental-builds.md). ## Four README intentions to review @@ -60,7 +42,7 @@ may change the construction/escape boundary or later chapter splits. ### Privacy proposal for review Introduce enforced underscore privacy in **Modules and Lazy Class -Initialization** (`chapter-modules`). This is a visible language change: +Initialization** (`chapter28a`). This is a visible language change: earlier snapshots allow underscore field access; from Modules onward, access must obey the declaring class's boundary. The teaching outline already places privacy here, alongside class names, ownership, and the public interface. @@ -121,46 +103,41 @@ After approval, implement and test in Modules, update its English/Japanese READMEs with the explicit language boundary, and run the full module suite including bundled `sys` and native execution. Cover allowed same-class access, rejected cross-class access, private class lookup, and forward receiver types. -Port the rule and library adaptations to the numbered Chapter 25 comparison -snapshot, with import tests preserving the original source owner. Carry it -into the forthcoming separate-compilation chapter. Do not backport the new +Carry the rule and library adaptations into Chapter 28b, with import tests +preserving the original source owner. Do not backport the new language restriction into Chapters 10-24 or the named pre-module snapshots. -## Proven Chapter 25 follow-ups from the module extraction - -Three failures reproduce in the numbered Chapter 25 baseline. The fixes are in -`chapter-modules`, but have not been copied back into that comparison snapshot: - -- A private recursive callback passed to native code retains `base == 2` from - known calls instead of restoring its declared `i64` bound. See - `BoundaryTest.testNativeExposure`. Carry direct Call exposure to StopCU even - on nonreturning paths, and restore Start when a function already has known - callers. `Opto.linkStart` must test unknown callers, not `nIns() < 2`. -- The lazy-table example crashes in `StoreNode.useAlias` when a symbolic class - Store has an EscapeNode user from a later allocation. Like - `BulkMemPhiNode.outputAlias`, use the publication field's alias when the Store - is that Escape's public-memory input. See `BoundaryTest.testLazyTables` and - `chapter-modules/src/test/smp/lazy`. The numbered baseline throws `Untested`. -- Final constructor fields lose writes when their declaration value is constant: - `val x=1; new C={->x=1; x=2;};` still reads back 1. Keep constructor field - declarations broad enough for later values, build loop Phis for final fields, - and preserve the distinction from final local bindings. See - `FinalConstructionTest` in the named snapshots. Recheck serialized declarations - and imported constructors when carrying this to the numbered baseline. - -Disposable reproducer: `build/SplitProbe.java`, compiled against Chapter 25; -arguments `native` and `array` exercise these failures. Port with the baseline's -import tests enabled, since the module snapshot intentionally lacks imports. - -Constructor local SSA, deferred constructor parsing and converted private -summaries also need to survive the final separate-compilation extraction. -These carry the already-reviewed construction design forward; they are not -independent changes for pre-construction chapters. - ## Investigate next Establish an earlier-chapter failure before changing compiler behavior. +### Prefix update of an enclosing class field + +The following returns 11 instead of 21 in numbered Chapter 25, Modules, and +Separate Compilation: + +```simple +int calls=0; +val next_noInline={ -> ++calls; }; +return next_noInline()+10*next_noInline(); +``` + +The prefix path updates an enclosing parser slot instead of class memory. +Postfix `calls++; return calls;` works and is used in the new chapter example. +This is independent of importing IR. The stage audit also reproduced the +instance-method form in Chapter 23, where methods first appear: + +```simple +struct C { int x=0; val inc={ -> ++x; }; }; +var c=new C; +return c.inc()+10*c.inc(); +``` + +It returns 11 instead of 21 in Chapters 23 and 26. Prefix lookup bypasses the +ordinary field-access path. A fix should share name resolution with other +reads/updates while preserving constructor locals, and propagate from 23 +through 28b. No fix is included in the numbering change. + ### Constructor loop with break/continue: worklist assertion This fails in construction and in the unchanged escape compiler before the @@ -214,7 +191,7 @@ and a null type. Thus the observed temporary lack of callers does not trigger `link()` cleanup. Keep this candidate unconfirmed rather than backporting the Chapter 25 lookup change on textual differences alone. -## Deferred until the Chapter 25 split +## Future compiler work ### Deterministic inlining @@ -257,13 +234,31 @@ Serialization, global identity remapping, and imported escape summaries belong with separate compilation. Escape analysis now has its own earlier snapshot after construction; keep its boundary open to review. -## Work that stays in Chapter 25 +### Selective loading of library IR + +Reliable incremental rebuilding is separate future work; see the +[incremental build design](incremental-builds.md) for the stale-dependency +example, required input tracking, rebuild propagation, and validation plan. + +The Separate Compilation README review found that importing only `sys.io.p` +still loads all ten units in the bundled `sys.o`, including `aryu8`, `aryi64`, +`scan`, and `adt.bitset`. All remain loaded through TypeCheck. Loading only +needed library members is a desired improvement, not current behavior. + +Selection works between independent objects: a client of `Counters.o` leaves +an unrelated `Unused.o` unloaded. Once selected, an object's entire saved IR +is reconstructed, and `ParseAll.loadDeps` follows its recorded dependencies. +Splitting the object alone is insufficient while the root's reexports and +unused function bodies still pull in those dependencies. Design member-level +IR loading and dependency discovery together; preserve type identity, +initialization rules, and imported escape summaries. This is separate from +whether imported code is initialized or emitted in the client's object. + +## Modules and separate compilation -Class-cycle checking and CLInit runtime lowering also appear in the new -modules snapshot; they do not belong in the pre-module chapters. The baseline -[chapter README](../chapter25/README.md#lazy-class-initialization) explains the -implementation; future work lives in the -[roadmap](../chapter25/ROADMAP.md#class-initialization-and-compiler-follow-ups). +Class-cycle checking and CLInit runtime lowering belong in 28a/28b. The +[module README](../chapter28a/README.md) explains their semantics; remaining +argument, initialization and pointer plans live in the [roadmap](roadmap.md). Native code cannot receive classes; a native-startup/class-handoff policy is not planned. Current data pointers remain eight bytes. diff --git a/docs/chapter-split.md b/docs/chapter-split.md index 7f257d43..55551b27 100644 --- a/docs/chapter-split.md +++ b/docs/chapter-split.md @@ -1,11 +1,31 @@ # Approved chapter split -Cliff approved this teaching outline on 2026-10-19. It splits the material -currently in Chapters 24 and 25 into seven chapters. Use descriptive chapter -names while the chapter count changes; final numbers can wait. Cliff approved -starting with both proposed implementation boundaries and wants to review the -construction/escape border after the snapshots run. Native library construction -and optimizer tuning belong in appendices for now. +Cliff approved the seven-part split on 2026-10-19 and the final numbering on +2026-10-24. The old combined Chapters 24 and 25 are retired; their history is +available in Git. Every new directory is a complete compiler snapshot. + +| Previous directory | Final chapter | +|---|---| +| chapter-sccp | 24a: SCCP within a function | +| chapter-interprocedural-sccp | 24b: SCCP across functions | +| chapter-incomplete-types | 25: SSA before types are known | +| chapter-construction | 26: Construction and private memory | +| chapter-escape | 27: Escape analysis and unknown callers | +| chapter-modules | 28a: Modules and lazy class initialization | +| chapter-separate-compilation | 28b: Separate compilation | + +Keep 17a/17b. The other paired chapters extend one idea: 24a/24b goes from +local to interprocedural SCCP; 28a/28b goes from compiling modules together to +compiling them independently. Construction and escape remain separate topics; +neither is presented as requiring the other. + +Inherited Java test names such as `Chapter24Test` and `Chapter25Test` retain +their historical identities across snapshots. They are regression cohorts, +not an index of the current teaching sequence. Historical allocator tables +also retain their original labels and dates. + +Native library construction and optimizer tuning are now [appendices](appendices/README.md). +The [roadmap](roadmap.md) and [backport queue](chapter-backports.md) own future work. The teaching pattern is to introduce a difficult idea, then show how to make it useful in a larger setting. Each chapter must remain a complete, runnable @@ -41,8 +61,8 @@ Ordinary loop widening belongs in the first chapter. The second adds argument and result widening for recursion. Use `f(x-1)+1` to explain why these are separate data cycles: the recursive return value never crosses Parm(x). -Chained comparisons do not need their own chapter. Their provisional home is -beside the current Chapter 23 short-circuit expressions: evaluate each operand +Chained comparisons do not need their own chapter. Their home is +beside Chapter 23 short-circuit expressions: evaluate each operand once and evaluate later operands only when earlier comparisons succeed. The current Chapter 24 cold-loop-split allocator improvement belongs with the tuning appendix. @@ -64,7 +84,7 @@ snapshot can publish conservatively; the later one refines that behavior. The name EscapeNode does not require teaching the full escape analysis at the point where publication is introduced. -`chapter-construction` now implements that explicit boundary. Hidden initializer +`chapter26` now implements that explicit boundary. Hidden initializer and allocator functions carry whole private object memory; completion publishes fields into public aliases. The new constructor functions reject early passing or storing of `self`, including self-links, and access through a merged alias. @@ -108,28 +128,21 @@ Keeping a function for emission must not imply arbitrary callers can reach it. This split organizes implemented behavior. Deterministic inlining, argument arrays, static pre-initialization of classes, CFG frequency estimates, and constant instance-field storage remain future work. See the -[backport queue](chapter-backports.md) and [Chapter 25 roadmap](../chapter25/ROADMAP.md). +[backport queue](chapter-backports.md) and [roadmap](roadmap.md). ## Renumbering and validation The first runnable extractions are -[SCCP Within a Function](../chapter-sccp/README.md) and -[SCCP Across Functions](../chapter-interprocedural-sccp/README.md), followed by -[SSA Before Types Are Known](../chapter-incomplete-types/README.md), -[Construction and Private Memory](../chapter-construction/README.md) and -[Escape Analysis and Unknown Callers](../chapter-escape/README.md), and -[Modules and Lazy Class Initialization](../chapter-modules/README.md). -Separate compilation remains to be extracted. Numbered Chapters 24 and 25 -remain comparison baselines during this work. - -Choose final numbers after trying the implementation boundaries above. -Revisit 17a/17b during that pass: they currently separate permissions from useful -syntax. Chapters 10/11 separate whole-memory SSA from useful alias partitioning. -Preserve those teaching boundaries when choosing names and numbers. - -The same progression guides this split: local SCCP to interprocedural SCCP, -private construction to escape discovery, and modules compiled together to -modules compiled independently. +[SCCP Within a Function](../chapter24a/README.md) and +[SCCP Across Functions](../chapter24b/README.md), followed by +[SSA Before Types Are Known](../chapter25/README.md), +[Construction and Private Memory](../chapter26/README.md) and +[Escape Analysis and Unknown Callers](../chapter27/README.md), and +[Modules and Lazy Class Initialization](../chapter28a/README.md), and +[Separate Compilation](../chapter28b/README.md). +All seven main snapshots are extracted and numbered. Chained comparisons now +start in Chapter 23 beside short-circuit expressions. The linear-history +publisher follows the numbered directories, including lettered pairs. Validate each intermediate compiler with its own Make suite, including execution checks. Keep declarations, conversions, diagnostics, and type bounds consistent; @@ -138,13 +151,13 @@ libraries when their compiler or object format changes. ## Escape snapshot ready for boundary review -`chapter-escape` adds function/alias exposure sets to TypeMem and closes the +`chapter27` adds function/alias exposure sets to TypeMem and closes the Start/Stop feedback cycle during SCCP. Known calls propagate memory summaries; exposed returns, fields, external arguments and native calls discover further addresses. Native calls contribute even on paths with no live Return. Function addresses kept entirely in known code no longer imply unknown callers. -The [recursive callback example](../chapter-escape/README.md) now belongs in +The [recursive callback example](../chapter27/README.md) now belongs in that chapter. Its base parameter becomes 2 while recursive calls remain. Returning the callback or a containing object, or handing it to native code, restores conservative arguments. FinalizeIR separates those analysis facts @@ -157,8 +170,8 @@ No modules, class singletons, serialized IR or identity remapping are included. ## Modules snapshot ready for review -`chapter-modules` compiles all discovered source files together. It adds class -singletons, namespaces and privacy, parent initialization, CLInit memory effects, +`chapter28a` compiles all discovered source files together. It adds class +singletons, namespaces and export filtering, parent initialization, CLInit memory effects, cycle diagnostics, runtime lowering, and shared native class storage. Source discovery reads parents as well as referenced children. The bundled modular sys is supplied as source; building reusable libraries remains appendix material. @@ -180,3 +193,28 @@ source/type cycles, rejected initialization cycles, parent order, native cold/ho calls, shared storage, and ARM/RISC-V encoding. The construction/escape border remains open to Cliff's review; this extraction does not settle broader rules for publishing unfinished objects. + +## Separate compilation snapshot ready for review + +`chapter28b` adds saved types and ideal IR, `GlobalBits` +identity remapping, object discovery, imported bodies, and `Unlink`. It carries +Modules' deferred constructor parsing, local final-field values and loop Phis, +converted private memory summaries, native callback exposure, and source-parent +initialization order. Source privacy enforcement remains a separate review. + +The runnable example compiles a library and a client from separate source roots. +The client allocates an imported struct whose constructor updates a final field +in a loop, then calls a retained library function that updates shared state. +The regression checks evaluation under three seeds and native cold/repeated +calls. A second import test preserves unknown callers for a callback passed to +native code. Existing import tests retain initialization-cycle diagnostics, +shared class data, public type reconstruction, and native function thunks. + +Serialization now saves the class declarations of owned nested structs even +when they are absent from the optimized graph's type closure. Otherwise a +client can load the instance type but cannot find its allocation signature. +An explicit source input is always recompiled; dependency objects may still +be reused. The old incremental-rebuild experiment remains ignored. + +All seven main teaching boundaries now have numbered snapshots. Broader +language choices and compiler improvements remain in the review queue. diff --git a/docs/incremental-builds.md b/docs/incremental-builds.md new file mode 100644 index 00000000..201922a0 --- /dev/null +++ b/docs/incremental-builds.md @@ -0,0 +1,63 @@ +# Incremental builds: future work + +Recorded after the Separate Compilation README review, 2026-10-24. This is a +design outline, not a description of implemented incremental builds. + +## Current gap + +`CompUnit` decides whether to reuse an object when the unit is discovered. It +checks its source timestamp and its dependencies' existing object timestamps. +It does not settle the whole dependency graph before accepting saved IR. + +For example: + +1. A depends on B and has inlined some of B. +2. B's source changes, leaving B's object unchanged. +3. A client discovers A. A's check sees the old B object and accepts A's object. +4. Later discovery notices that B needs rebuilding, without reconsidering A. + +The compiler can therefore reuse code based on stale bodies or constants. +An unchanged public signature is insufficient: Simple imports implementation +details for optimization as well as declarations for type checking. + +## Required pieces + +- Discover dependencies, mark changed units, and propagate that decision to + dependents until it settles. Handle cycles as groups. Do this before loading + IR that may be stale; newly discovered dependencies must also join the plan. +- Record actual inputs. An object can own several source units, so track all + of their sources and the objects resolved through library search paths. + The current check assumes `buildDir/name.o`; a missing file has timestamp + zero and does not trigger rebuilding. Missing inputs must invalidate or + produce a useful error rather than silently accepting an old result. +- Record compiler and serialization versions, target, ABI, and relevant + options. Content hashes would also detect changes with preserved timestamps. + Specify which changes require rebuilding source and which reject an + incompatible source-free library. +- Make build targets match output ownership. The old ignored `testModule0` + expects separate A.o and A/B.o, while the current compiler can bundle several + units into one object. The target must identify the complete set it owns. +- Provide an "ensure current" build operation. Explicit source compilation + currently always recompiles. An unchanged build should do no compilation or + linking; a changed object or link input should trigger relinking. +- Publish successful outputs without leaving a partial object accepted after + failure, and keep the recorded inputs consistent with those outputs. + +Initially, rebuilding every dependent of a changed object is a reasonable +conservative rule. Fine-grained interface/body fingerprints can come later. + +## Suggested first implementation + +Put a small build driver around the compiler with explicit object targets, +recorded inputs, and dependency propagation. Keep individual compilation +requests straightforward. A clean build and an incremental build must produce +the same observable program behavior. + +Cover unchanged builds, direct and transitive source edits, inlined constants +and bodies, cyclic dependencies, bundled sources, removed inputs, library-path +changes, compiler/target changes, and failed builds. Use controlled timestamps +or hashes instead of sleeps. Replace the ignored historical experiment with +tests matching the chosen object ownership model. + +Selective library IR loading is separate future work. It can reduce compile +cost, but is not required to make conservative incremental rebuilding correct. diff --git a/docs/regalloc-spills.md b/docs/regalloc-spills.md index 8e83f3ba..71bab467 100644 --- a/docs/regalloc-spills.md +++ b/docs/regalloc-spills.md @@ -1,5 +1,11 @@ # Register allocation across chapters +This is the dated **pre-split** comparison. Its Ch 24/25 columns describe the +retired combined snapshots, not today's Chapter 25 (incomplete types). Current +measurement tools target 24b/28b and publish a +[separate table](appendices/current-spill-matrix.md). The historical numbers +below remain unchanged. + Read a row left to right to follow a fixed cohort through successive compilers. Each cell gives **Ops / RA / X**: @@ -98,7 +104,8 @@ The measured machine graph is stopped before allocation to identify subsequently inserted copies/cloned constants. After encoding, their instruction ranges are matched against the emulator's executed PCs, including multi-instruction expansions. -After a successful run, update the marked tables with: +After a successful run, publish the current compiler table (leaving these +historical tables unchanged) with: ```sh python build-support/spill-matrix.py --reuse --update-docs @@ -106,6 +113,6 @@ python build-support/spill-matrix.py --reuse --update-docs Per-program inputs, results and dynamic counts are written to `build/spill-stats/dynamic-counts.csv`; emulator logs and explicit skips live -under `build/dynamic-stats/{21..25}/dynamic.log`. The x86 records remain in -`build/spill-stats/spill-matrix-{20..25}.log`. The source adaptations for Chapter -25 are documented in the [replay README](../chapter25/src/test/java/com/seaofnodes/simple/spill/README.md). +under `build/dynamic-stats/{21,22,23,24b,28b}/dynamic.log`. The x86 records use +`build/spill-stats/spill-matrix-{20,21,22,23,24b,28b}.log`. The source adaptations for old Chapter +25 are documented in the [replay README](../chapter28b/src/test/java/com/seaofnodes/simple/spill/README.md). diff --git a/docs/stage-audit.md b/docs/stage-audit.md new file mode 100644 index 00000000..c375d159 --- /dev/null +++ b/docs/stage-audit.md @@ -0,0 +1,82 @@ +# Chapter split cleanup audit + +This record distinguishes checked behavior, existing gaps, and future designs +while retiring the old combined Chapters 24/25. The final mapping is in the +[split record](chapter-split.md). Historical Java test names are retained as +regression identities; they do not identify current chapter boundaries. + +## Corrections in this cleanup + +- Chained comparisons now begin in Chapter 23. The early SCCP implementations + incorrectly compared a boolean intermediate with the third operand: + `10 < 30 < 20` returned true. Later implementations preserved the middle + operand but reused the first operator, making `0 < 2 <= 2` false. All current + snapshots from 23 onward now compare adjacent values using each written + operator. Regression cases cover both directions, strict/non-strict mixtures, + single evaluation, side effects, short-circuiting, and mixed-direction errors. +- Chapter 23's inherited, explicitly described fuzzer scratch contains many + comparisons using the former left-associative grammar. It is retained as an + ignored `testJigFuzzer`, consistent with the scratch-test policy; its mixed + directions are no longer valid source. Later snapshots already omitted it. +- Native-library and tuning material is preserved in [appendices](appendices/README.md), + and the former roadmap is now [docs/roadmap.md](roadmap.md). +- The recursive-return diagnostic already passed. It remains enabled in the + earlier snapshots and is enabled again in 28a/28b. The mutual-recursion test had an obsolete graph-string + expectation; it now checks its existing four execution results in 24b–28b. + In 24a, local SCCP cannot infer the recursive return type; the same example + checks that conservative diagnostic instead. This makes the boundary explicit. +- Allocation/runtime measurement runs passed after the comparison correction; + the changed spill goldens record the resulting smaller graphs. Historical + published tables retain their original compiler labels and dates. + +## Implemented, with narrower limits than earlier prose suggested + +- Separate compilation imports types and optimized IR without source parsing; + it reruns analysis and type checking with the new callers. +- Loading is by object and recorded dependencies, not individual used members. + A call to `sys.io.p` loads all ten bundled sys units. Independent, unrelated + objects can remain unloaded. Loading does not imply class initialization. +- Timestamp checks do not yet provide a reliable incremental build system. + The [design note](incremental-builds.md) records the missing pieces. +- Underscores select exports in modules; source privacy checks are still a + proposal awaiting review. Do not treat hidden exports as inaccessible source. +- Constructor-local final fields use SSA values and exit Stores. Reads of an + unfinished object are allowed only for initialized fields. Passing unfinished + self to arbitrary helpers and accepting completion only after SCCP are not + promised by the current chapter boundary. + +## Existing failures and deferred validation + +- Prefix update of a field from a method can lose the write, starting in + Chapter 23 (confirmed by two calls to `inc={ -> ++x; }`). The enclosing + module-field reproducer and the worklist failure below are retained in the + [queue](chapter-backports.md), rather than hidden by the split. +- A constructor loop with both break and continue still reproduces a worklist + assertion in Chapter 26. It is not caused by final-field mutability. +- `testModule0` is an ignored historical incremental-build experiment. It + assumes per-source output objects and unchanged explicit-input builds, neither + of which matches the present compiler's contract. +- Serialization's expensive byte-for-byte round-trip assertion remains disabled. + Ordinary import tests do not establish that stronger property. +- Direct probes of the remaining ignored tests found a stale forward-method + graph expectation and a missing `progs/sieve.smp` fixture in 28b. These and + the interactive stdin test remain ignored. Ignored Jig and + random-fuzzer entry points are intentional scratch/long-running tools. + Audit these separately before advertising their behavior as tested. + +Selective loading, full incremental builds, source privacy, compact pointers, +argument arrays, deterministic inlining, and broader constructor rules remain +future work. They are not prerequisites for completing the chapter numbering. + +## Validation + +The affected snapshots (23, 24a, 24b, 25, 26, 27, 28a, 28b) were checked with +their full Make suites on Windows and Linux, plus focused reruns after updating +test expectations. The final Windows coverage is 4,143 tests plus eight fuzzer +regression runs, with the shared printer and ISA tests also passing. The +native library/client cases and final Chapter 28b release build pass on both OSes. + +A local linear-history dry run produced all 31 tags in teaching order. The +final source snapshot, chapter navigation, Maven module IDs, and reviewed local +documentation links were checked. Measurement capture in 24b and dynamic +measurements in 24b/28b pass; the historical published tables were not rewritten. -- cgit v1.2.3