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. --- chapter25/src/main/smp/sys.smp | 9 +++++ chapter25/src/main/smp/sys/Ary.smp | 10 ++++++ chapter25/src/main/smp/sys/Scan.smp | 36 +++++++++++++++++++ chapter25/src/main/smp/sys/aryi64.smp | 63 +++++++++++++++++++++++++++++++++ chapter25/src/main/smp/sys/aryu8.smp | 66 +++++++++++++++++++++++++++++++++++ chapter25/src/main/smp/sys/io.smp | 32 +++++++++++++++++ chapter25/src/main/smp/sys/libc.smp | 20 +++++++++++ 7 files changed, 236 insertions(+) create mode 100644 chapter25/src/main/smp/sys.smp create mode 100644 chapter25/src/main/smp/sys/Ary.smp create mode 100644 chapter25/src/main/smp/sys/Scan.smp create mode 100644 chapter25/src/main/smp/sys/aryi64.smp create mode 100644 chapter25/src/main/smp/sys/aryu8.smp create mode 100644 chapter25/src/main/smp/sys/io.smp create mode 100644 chapter25/src/main/smp/sys/libc.smp (limited to 'chapter25/src/main/smp') diff --git a/chapter25/src/main/smp/sys.smp b/chapter25/src/main/smp/sys.smp new file mode 100644 index 00000000..815212ab --- /dev/null +++ b/chapter25/src/main/smp/sys.smp @@ -0,0 +1,9 @@ +// -*- mode: java; -*- + +// top-level default standard library import + +var libc = libc; +var io = io; +var aryu8 = aryu8; +var Scan = Scan; +var aryi64 = aryi64; diff --git a/chapter25/src/main/smp/sys/Ary.smp b/chapter25/src/main/smp/sys/Ary.smp new file mode 100644 index 00000000..0f667695 --- /dev/null +++ b/chapter25/src/main/smp/sys/Ary.smp @@ -0,0 +1,10 @@ +// -*- mode: java; -*- + +// Array utilities + +// Copy byte array contents +val copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> + for( int i=0; i + buf = b; + }; + + // Skip whitespace + val skip = { -> + while( x < buf# && buf[x] <= ' ' ) + x++; + return self; + }; + + // True if find required character, and skip it; else False. + val match = { u8 c -> + skip(); + if( buf[x] != c ) return false; + x++; + return true; + }; + + // Parse a simple number + val number = { -> + skip(); + bool neg = match('-'); + i64 n = 0; + while( '0' <= buf[x] & buf[x] <= '9' ) + n = n*10 + (buf[x++] - '0'); + return neg ? -n : n; + }; +}; diff --git a/chapter25/src/main/smp/sys/aryi64.smp b/chapter25/src/main/smp/sys/aryi64.smp new file mode 100644 index 00000000..499431d8 --- /dev/null +++ b/chapter25/src/main/smp/sys/aryi64.smp @@ -0,0 +1,63 @@ +// -*- mode: java; -*- + +// Ary/Vector of i64s +struct aryi64 { + u32 !len = 0; + i64[] !buf; + + new aryi64 = { i64[] b -> + buf = b; + }; + + // Grow as needed + val _grow = { int len2 -> + if( len+len2 < buf# ) return self; + int newlen = buf# * 2; + while( len+len2 >= newlen ) newlen *= 2; + i64[] !buf2 = new i64[newlen]; + for( int i=0; i + _grow(1).buf[len++] = c; + self; + }; + + // Write to aryu8 + val str = { -> + // TODO: clunky default constructor syntax + var str = new aryu8(new u8[1]).add('['); + for( int i=0; i + Scan !s = new Scan(str); + if( !s.match('[') ) return null; + // Array of parsed results + var nums = new aryi64(new i64[1]); + + // Parse a list of numbers + if( s.match(']') ) // Handle the empty list + return nums; + + // Parse number commas "123, " until something else + while( s.x < s.buf# ) { + nums.add(s.number()); + if( !s.match(',') ) + break; + }; + // Close the list + return s.match(']') ? nums : null; +}; diff --git a/chapter25/src/main/smp/sys/aryu8.smp b/chapter25/src/main/smp/sys/aryu8.smp new file mode 100644 index 00000000..0ce4bd23 --- /dev/null +++ b/chapter25/src/main/smp/sys/aryu8.smp @@ -0,0 +1,66 @@ +// -*- mode: java; -*- + +// Ary/Vector of u8s - a resizable array of bytes. +struct aryu8 { + u32 !len = 0; + u8[] !buf; + + new aryu8 = { u8[] b -> + buf = b; + }; + + // Grow as needed + val _grow = { int len2 -> + if( len+len2 < buf# ) return self; + int newlen = buf# * 2; + while( len+len2 >= newlen ) newlen *= 2; + u8[] !buf2 = new u8[newlen]; + Ary.copy(buf2,0,buf,0,buf#); + buf = buf2; + self; + }; + + val clear = { -> len = 0; self; }; + + // Add a character to aryu8 + val add = { u8 c -> + _grow(1).buf[len++] = c; + self; + }; + + // Add all of a plain array to the aryu8 + val addAry = { u8[~] ary -> + _grow(ary#); + Ary.copy(buf,len,ary,0,ary#); + len += ary#; + self; + }; + + // Remove x bytes from the tail. + val undo = { int x -> + len = len >= x ? len-x : 0; + self; + }; + + // Print ASCII number into aryu8 + val num = { i64 x -> + if( !x ) { add('0'); return self; } + if( x < 0 ) { add('-'); x = -x; } + i64 ten = 1, log = 0; + while( ten <= x ) { ten *= 10; log++; } + for( int i=0; i + i64 ptr = buf; // Cast buffer pointer to i64 for native C call + libc.write(fd,ptr,len); + }; +}; diff --git a/chapter25/src/main/smp/sys/io.smp b/chapter25/src/main/smp/sys/io.smp new file mode 100644 index 00000000..b94e89fa --- /dev/null +++ b/chapter25/src/main/smp/sys/io.smp @@ -0,0 +1,32 @@ +// -*- mode: java; -*- + +// Simple I/O Library + +// Write byte array to stdout +val p = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + return libc.write(1,ptr,str#); +}; + +val p_noInline = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + return libc.write(1,ptr,str#); +}; + +// Return stdin as a u8[]. +val stdin = { -> + var buf = new u8[8*1024]; + i64 ptr = buf; + int len = 0; + while( true ) { + int rez = libc.read(0,ptr,buf#); + if( rez < 0 ) libc._exit(libc.errno); + len += rez; + if( rez < buf# ) + break; + libc._exit(-2); // Need to implement for more than 8K input + } + // Compress + var dst = new u8[len]; + return Ary.copy(dst,0,buf,0,len); +}; diff --git a/chapter25/src/main/smp/sys/libc.smp b/chapter25/src/main/smp/sys/libc.smp new file mode 100644 index 00000000..42fc7313 --- /dev/null +++ b/chapter25/src/main/smp/sys/libc.smp @@ -0,0 +1,20 @@ +// -*- mode: java; -*- + +// libc bindings: +// https://www.man7.org/linux/man-pages/man2/.2.html + +// fd buf len -> len +{ i32 i64 u32 -> u32 } write = "C"; +// fd buf len -> len +{ i32 i64 u32 -> u32 } read = "C"; +// status +{ i32 -> i32 } _exit = "C"; +// addr len prot flags fd off -> void* +{ i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; +// mmap flags +i32 PROT_EXEC = 4; +i32 PROT_READ = 1; +i32 PROT_WRITE= 2; +i32 PROT_NONE = 0; +i32 MAP_PRIVATE = 2; +i32 MAP_ANON = 32; -- cgit v1.2.3