| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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 `<init>` 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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* #44 Start on chapter 7
* #44
Temp hack on printing to not break on cycles.
Parse while statement.
* #44 Remove unnecessary method
* #44 Remove unnecessary phi map
* #44 Phi should have existing nodes from both scopes as input
* #44 We need to only insert phis once for each name that is looked up. To do so,
we need to know when a named is looked up first time inside the loop body.
The phi must have its second input added later on after the loop is fully parsed.
* #44 Add phi also when update() is called.
Only add phi if name was known at loop start
* #44 Only create phi in loop body if var binding in head != body.
During finish() lookup in body directly.
* #44 Update the print output to make it similar to that in Xmilia's fork
* #44 Disable peephole for phis & region involved in while loop
* Fix broken tests
Remove "disablePeephole" set in some tests, and remaining set for other tests, so a bulk test-all fails because disablePeephole is true for all.
Reset disablePeephole in Node.reset
Switch HashSet for BitSet (touches all).
* Restructure Node class
Group printing, group node & edge manipulations, group optimizations.
Also, fix LoopRegion idom, it does not use Region idom but uses the original
* #44 Node printing
* #44 Node printing
* #44 Fix control edges in loop region
Change label of loop region
Fix the output count in dump
* #44 Revise dump output
* #44 When a LoopRegionNode is duplicated, ensure the dupe is also a LoopRegionNode
* #44 When a LoopScopeNode is merged, we merge the names set too
* #44 When a LoopScopeNode is merged, we merge the names set too
* #44 Fix print1() on RegionNode to use label()
* #44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created
* Revert "#44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created"
This reverts commit 5f729709855046c5c10904f08385fd1aec9a298a.
* #44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created
* #44 when we create a phi incrementally for a loop region, all scopes that are cloned from the original must get the same phi update
* #44 test case
* #44 test case
* Squashed commit of the following:
commit 15666e287e6bbc39b3fcc49939165a1e908d43b2
Author: Cliff Click <cliffc@acm.org>
Date: Mon Nov 27 09:45:40 2023 -0800
lazy/eager phis
Eager phis by default, but can flip Parser.LAZY to switch to lazy phis. Several tests golden answers change when flipping this flag due to minor node renumbering.
Phi combines same_inputs and singleUniqueInput.
Fancier basic-block-like printing. Uses isMultiHead & isMultiTail which show up in many Nodes.
Remove blanks in triple-quote strings.
commit 6ea70182a92b7db4fe5a1fdc2c4491842ef77ee5
Author: Cliff Click <cliffc@acm.org>
Date: Sun Nov 26 11:13:22 2023 -0800
Remove dead scopes
Add a debug find
commit a52c06a47bf1e56866d8b4d043290838f053ad76
Author: Cliff Click <cliffc@acm.org>
Date: Sun Nov 26 10:21:48 2023 -0800
No constraints on backedges
nicer loopy graphs
commit b5ab550098355f0b66bf24b40adf2e5ba4d86e4e
Author: Cliff Click <cliffc@acm.org>
Date: Sun Nov 26 10:13:22 2023 -0800
Fix regression
commit 30a7f5c734c686c02d3ca479914c9427b65cc469
Author: Cliff Click <cliffc@acm.org>
Date: Sat Nov 25 21:51:47 2023 -0800
minor cleanup
commit ad742b795ce0c93cfc82b2b11740261cfd923d02
Author: Cliff Click <cliffc@acm.org>
Date: Sat Nov 25 21:47:05 2023 -0800
Fixes lazy phi
Scope now takes a 'loop' option on dupping; the dup'ed Scope is filled with "Lazy Phi" sentinels - markers to indicate a Phi is need if this variable is ever referenced. If its never referenced, at the loop exit the "Lazy Phi" unwinds back to the original value. Lookup and update calls lazily insert concrete Phis over "Lazy Phis" at first touch.
Rename _allScopes to _xScopes its "active" not "all" scopes now.
Remove try/finally block at end, because a compiler bug throws, then attempts a GraphViz on a broken graph, then throws again, hiding the original bug.
Removed 1 extra layer of Scopes.
Scope printing now prints in edge order; added a reversemap for printing.
More touches to ascii printing.
* Remove flag to parseBlock
* Bugfix for lazy on empty loop body
Remove extra phi name-matching code
* Keep head alive until entire end_loop merging is done
* Create chapter 8 as a copy of chapter 7
* #44 Chapter 7 is now eager phis only (#46)
* #44 Chapter 7 is now eager phis only
* MOVE IR Printing to dedicated class to declutter Node. Remove Ary (#49)
* #44 Move IR printing to dedicated class to declutter Node, and remove Ary
* #44 refactor Node.delUse() to use common del()
* #44 Some cleanups
* #44 Some cleanups
* #44 Some cleanups
* #44 Some cleanups
* Revert "#44 Some cleanups"
This reverts commit 2702c338c8bdaa5ef2128000e26f1a8496baf34a.
* #44 Some cleanups
* #44 Some cleanups
* #44 Some cleanups
* #44 Fix typo
* #44 Fix markdown formatting
* #44 Remove line numbers from code snippets
---------
Co-authored-by: Cliff Click <cliffc@acm.org>
|
