From 8f460340cfe01a4945635251bcd33b257b699bf7 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 5 Nov 2026 15:51:41 -0800 Subject: Remove a bunch of extra graph walks pre-Opto Removed most; moved a few into Opto setup pass. Lots of modest bug fixes --- chapter29/README.md | 6 +- chapter29/docs/construction-groups.md | 29 +- chapter29/docs/deferred-construction.md | 380 +++++++++++++++++++++ .../simple/codegen/ClassInitDependencies.java | 4 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 30 +- .../java/com/seaofnodes/simple/codegen/Iter.java | 60 +--- .../com/seaofnodes/simple/codegen/IterPeeps.java | 2 +- .../java/com/seaofnodes/simple/codegen/Opto.java | 73 +++- .../com/seaofnodes/simple/codegen/ParseAll.java | 43 --- .../com/seaofnodes/simple/codegen/RegAlloc.java | 19 +- .../com/seaofnodes/simple/codegen/TypeCheck.java | 28 +- .../com/seaofnodes/simple/node/CLInitNode.java | 5 +- .../java/com/seaofnodes/simple/node/CallNode.java | 26 +- .../com/seaofnodes/simple/node/ConstructNode.java | 52 ++- .../com/seaofnodes/simple/node/ConvertNode.java | 1 + .../com/seaofnodes/simple/node/EscapeNode.java | 8 +- .../java/com/seaofnodes/simple/node/FRefNode.java | 2 + .../com/seaofnodes/simple/node/FldOffNode.java | 8 +- .../java/com/seaofnodes/simple/node/FunNode.java | 15 +- .../seaofnodes/simple/node/GlobalEscapeNode.java | 11 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 28 +- .../java/com/seaofnodes/simple/node/MulNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 6 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 13 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 43 ++- .../com/seaofnodes/simple/node/PtrToIntNode.java | 2 + .../com/seaofnodes/simple/node/StopCUNode.java | 52 +-- .../java/com/seaofnodes/simple/node/StoreNode.java | 15 +- .../com/seaofnodes/simple/node/ToFloatNode.java | 2 + .../com/seaofnodes/simple/node/ToIntegerNode.java | 2 + .../com/seaofnodes/simple/parser/Allocations.java | 17 +- .../com/seaofnodes/simple/parser/Construction.java | 69 +--- .../com/seaofnodes/simple/parser/Functions.java | 5 +- .../java/com/seaofnodes/simple/parser/Parser.java | 1 - .../java/com/seaofnodes/simple/parser/README.md | 4 +- .../com/seaofnodes/simple/parser/References.java | 23 +- .../java/com/seaofnodes/simple/parser/Structs.java | 43 +-- .../java/com/seaofnodes/simple/type/TypeMem.java | 10 + .../com/seaofnodes/simple/type/TypeStruct.java | 10 +- .../java/com/seaofnodes/simple/ArithNodeTest.java | 3 +- .../java/com/seaofnodes/simple/CallEndTest.java | 54 +++ .../java/com/seaofnodes/simple/Chapter10Test.java | 20 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 15 +- .../java/com/seaofnodes/simple/Chapter17bTest.java | 12 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 1 + .../seaofnodes/simple/ConstructionGroupTest.java | 40 ++- .../simple/ConstructorCompletionTest.java | 14 +- .../test/java/com/seaofnodes/simple/TypeTest.java | 20 ++ .../simple/codegen/RegAllocTestSupport.java | 25 ++ skills/chapter25-codex-notes.md | 68 +++- 51 files changed, 1001 insertions(+), 422 deletions(-) create mode 100644 chapter29/docs/deferred-construction.md diff --git a/chapter29/README.md b/chapter29/README.md index 28925606..9bd5843e 100644 --- a/chapter29/README.md +++ b/chapter29/README.md @@ -40,8 +40,10 @@ merges and `addReturn`; field values are no longer copied into memory at exit. Fresh fields start at `TypeScalar.BOT`, which preserves a missing live arm at a merge. Forward memory types supply the initialization proof at Loads and merged -Returns. Checks run after parsing and an optimistic type solve; there is no -separate initialization walk or field-state map. Class singleton initialization +Returns. Checks run at TypeCheck using the existing optimization passes; there +is no extra construction solve, initialization walk, or field-state map. +Known failures are recorded in [the late-check notes](docs/deferred-construction.md). +Class singleton initialization retains its existing store-at-exit path. `ConstructorCompletionTest` covers partial assignments, early returns, loops, diff --git a/chapter29/docs/construction-groups.md b/chapter29/docs/construction-groups.md index c817626e..8dccdf6d 100644 --- a/chapter29/docs/construction-groups.md +++ b/chapter29/docs/construction-groups.md @@ -20,15 +20,18 @@ memory; the explicit constructor receives the declaration initializer's merged result, including early exits. There is no backwards initialization query, per-field parser state, call-site snapshot, or store-all instance exit. -After parsing closes loops and resolves names, `Iter.types` computes an -optimistic fixed point using the existing node types, compute methods, and -worklist, without graph rewrites. Optimism matters: an initialized field carried -unchanged around a loop must not remain stuck at a pessimistic BOT seed. Numeric -fields in loop memory widen as scalar loop values do. Constructor Loads remain -kept until checking, so an unused or folded result cannot hide an illegal read. -BOT describes the incoming field contents, not a taint on later computations. -Conversions and numeric Stores retain their existing declared-type bounds; -their narrowing cannot excuse the original Load, which is checked independently. +The existing Iter/Opto passes propagate these types; TypeCheck reports errors. +There is no extra construction type solve or retained source-use list. An +initialized field carried unchanged around a loop needs the optimistic SCCP +solution. Numeric fields in loop memory widen as scalar loop values do. +Arithmetic, conversions, and numeric Stores preserve Scalar.BOT, so a live bad +read cannot disappear merely because it is multiplied by zero. Genuinely unused +reads may be removed by DCE. + +The allocator's ConstructNode retains the constructor's final private memory +for its completion check. TypeCheck gathers these nodes during its existing +error walk and removes checked boundaries before lowering. The pass removal +exposes known failures; see [the late-check notes](deferred-construction.md). Internal construction memory parameters use actual allocation/initializer call edges; the hypothetical external caller does not supply their memory. They @@ -99,7 +102,7 @@ A small `ConstructNode` wraps each source `new`. Its runtime value is the allocator result; its type adds the OR of that call's actual argument qualifiers. This distinguishes `new Child(self)` from `new Child(null)` even when both call the same constructor. Looking only at the shared callee Return would lose this -distinction. The node disappears after source checking, before lowering. +distinction. The node disappears after TypeCheck, before lowering. A completed receiver gives a completed view of its pointer fields. Construction may retain incomplete references but cannot publish them, so reaching the root @@ -108,13 +111,13 @@ There is no group identity or traversal to mark members complete. Conversely, object-reference fields read through incomplete self remain conservative, even if the particular stored reference was complete. -The optimistic `Iter.types` solve also handles qualifier cycles. For +The existing optimistic SCCP solve also handles qualifier cycles. For `p = null; while (n--) p = new Link(p);`, no input introduces incompleteness, so `p` stays complete and a subsequent field read is allowed. A backedge carrying self instead makes the Phi and its uses incomplete. -`Construction` retains source operands and diagnostic sites until checking; -it stores no flow facts and performs no recursive Load/Phi/Call query. The old +`Construction` selects private self memory during parsing; it retains no +source-use lists or flow facts and performs no recursive Load/Phi/Call query. The old root and allocation bitsets are gone. There are no field-requirement sets, hidden `^` memory arguments, or runtime group objects. diff --git a/chapter29/docs/deferred-construction.md b/chapter29/docs/deferred-construction.md new file mode 100644 index 00000000..ff0a2765 --- /dev/null +++ b/chapter29/docs/deferred-construction.md @@ -0,0 +1,380 @@ +# Deferring construction checks: experiment + +The extra construction pass is removed from the working implementation. +`Construction.check()`, its retained source-use lists, `Iter.types()`, and the +separate constructor-Return walk are gone. Errors now belong to the existing +TypeCheck walk; ConstructNode retains final private memory for completion checks. +No additional whole-graph pass was added. Constructor rejection tests remain active. + +## Constant folding + +`TypeScalar.BOT` is not an initialized integer. Arithmetic, comparisons, +negation, numeric conversions, and typed Stores must preserve it rather than +manufacturing an integer or floating-point result. In particular, `x*0` and +`x==x` cannot become constants while `x` has this type. An initialized unknown +integer still permits those folds. + +The scan found and changed these related cases: + +- Multiplication by zero now folds in `compute`, after checking numeric inputs. + Integer strength reduction also waits for integer operands; an unfinished + loop Phi could eventually become a float. +- Same-input comparisons fold in `compute`. Floating comparisons keep NaN + semantics; `x==x` is not necessarily true. The integer range implementation + of `!=` also had the equality answers reversed. +- Arithmetic pushed through Phis uses each copied operation's `compute`, + including floating-point constants, instead of an unchecked integer cast. +- Known array length offsets and element shifts fold in + `ConFldOffNode.compute`, rather than its `idealize`. +- `Not`, unary minus, conversions, and Stores preserve unknown initialization. + `RoundF32` already passed that type through. + +This does not ban creating constant *operands* in rewrites such as `x*8` to +`x<<3`. Memory forwarding still has cases that return a stored constant or an +array's zero-filled element; these were inspected but not rewritten into a new +memory analysis. `Load.idealize` retains a `Scalar.BOT` load. + +The changes exposed a rejected-Phi-fold worklist cycle. Factoring +`Phi(bool & 7, integer & bool)` widens the result from `bool` to `[0-7]` and +must fail. Building and then killing the candidate woke the same dependencies +forever. The trial now computes its types before registering use edges. + +## Preserving the constructor body through optimization + +This regression must reject a live incomplete lookup: + +```simple +struct Child { + Test.Parent? parent; + new Child = { Test.Parent? ^par -> parent = par; }; +}; +struct Parent { + Child child; + int~ payload; + new Parent = { -> + child = new Child(self); + payload = child.parent == null; + }; +}; +return new Parent().payload; +``` + +`child` is incomplete because its constructor received incomplete `self`. +Reading `child.parent` must therefore fail. The read supplies the final result; +this is not a discarded local or dead-code issue. + +The decisive failure was private-memory Parm typing. During Iter, inlining +removed a real caller while the function still had its unknown-caller edge. +The special case returned MemTop anyway. That erased the memory merge, Store, +and the bad Load feeding it, before TypeCheck could report the error. + +Parms now use their normal merge. Hidden initializer/constructor helpers have +only actual allocator callers; the source-visible constructor binding denotes +the allocator. Public allocators still receive unknown callers, so unused public +constructor bodies remain checked. This also avoids poisoning a helper's private +memory with a fictitious external default. + +Inlining presents a second issue: a complete actual pointer must not grant +permission to read a restricted formal. A partial-only ConstructNode gives +self and ^ parameters their body view independently of Parm typing. It remains +until TypeCheck. Load's alias search recognizes that this view preserves the +address, while compute/err continue to see the qualified pointer. + +A smaller regression reads an unwritten field through a self cycle: + +```simple +struct C { + C next = self; + int~ x; + new C = { -> x = next.x; }; +}; +return new C().x; +``` + +Both examples now reject at TypeCheck. A positive regression initializes x to +7, increments it in the constructor, and checks that the result folds to 8. + +The broader run exposed a function-lifetime bug during SCCP: unlinking calls +could delete a body subsequently rediscovered from a type-level function +reference. Returns are kept during the existing reset walk and released once +call edges have been rebuilt. No additional graph walk is needed. + +Class-init dependency discovery also skips a CLInit whose receiver has not +resolved to a class. A Scalar.BOT receiver is left for its Load's TypeCheck +error, rather than dereferencing a null class name. + +The trial successfully uses the existing passes to prove a chain built from +`null` complete. It also rejects direct `par.payload`, `par.payload*0`, and +`int x = par.payload; value = x*0` after the arithmetic/conversion repairs. + +Genuinely unused reads are allowed to disappear under late-check semantics. +Rejection tests must keep the read live. `testUnusedIncompleteReadCanDie` checks +that an unused `par.payload` read is eliminated and the program returns 5. + +## Optimization differences and register allocation + +`Chapter18Test.testFcn9` exposed an independent escape bug. StopCU treated the +class initializer's synthetic self as an object already held by an external +caller. Its broad function-valued field type exposed the local x function even +though the initializer never returned and x had no callers after inlining. +Skipping that synthetic argument restores the empty escape set for x and the +expected `return Top;`. Actual public-call arguments still escape normally. + +That correction exposed `Chapter18Test.testFcn8`: a Store computed from TOP +memory interpreted its optimistic singleton bit as established private memory. +It widened a function value to the declared signature, then narrowed its FIDX +set when memory resolved. Store now returns TOP while its memory is TOP, so +SCCP remains monotone. + +The String differences have a different cause. In Chapter19, the private +_hashCodeString body dies; the surviving functions are the initializer, +allocator, equals, and public hashCode. Its golden string now omits the two dead +private-helper MemTop Returns and matches the current addition order. +`Add.spine_cmp` breaks this tie by node ID. Strength reduction creates the Sub +in IterPostOpto, after the byte Load (Sub#594 versus Load#504 in one traced copy), +so the Sub sorts to the left. This is node ordering, not a lost value type. + +In the Chapter20/21 fixtures, _hashCodeString really escapes through the implicit +return, and hashCode contains an inlined copy. Before the allocator repair, both loops needed an extra x86 +register copy with the new addition operand order. A disposable probe +swapped only `((hash<<5)-hash) + byte` to `byte + ((hash<<5)-hash)` after Unlink: +no types or live functions changed, but the weighted split score fell from 37 +to 21. Each hash body fell from 17 to 9; the allocator stayed at 3. + +Reconstructing the earlier source by reversing the saved construction-pass +removal patch reproduces the expected 29. Its standalone _hashCodeString costs +17, inlined hashCode costs 9, and allocator costs 3. Before the allocator repair, +these costs were 17, 17, and 3. Both versions contain two hash loops; no inlining decision changed. +Current code emits two fewer functions, the dead initializer/constructor helpers, +which contributed zero. Thus the entire increase is one loop-weighted register +copy in the inlined hashCode body, not another retained function or stack spill. + +With the old operand order, the byte Load can write the loop's hash register +and Add accumulates the shifted/subtracted value into it. With the new order, +Add's destructive input is the Sub result. Its two-address tie plus the Phi +backedge joins the shift/Sub/Add chain to the old hash live range, which overlaps +the shifted value at the subtraction. `RegAlloc.splitSelfConflict` inserts a +`use/self/two` copy before Add. The existing commute heuristic in `splitByLoop` +is not reached: self conflicts take an earlier splitting path. Commuting Add +before splitting is the concrete optimization opportunity. + +The allocator now does this in `splitSelfConflict`, using the existing failed- +range traversal and scratch list. It commutes two-address operators when the +RHS has one use and belongs to a different live range, then omits the copy for +the tie it broke. An allocator-generated Split is excluded: its single use can +hide a longer-lived value, and commuting onto it can undo an earlier repair. +The existing coloring retry rebuilds live ranges. There is no new whole-IR pass +or analysis structure. The machine's `commutes()` hook covers Add, Mul, Xor, +And, and Or (and commutative floating instructions). + +The String score is now 21: each hash body costs 9 and the allocator costs 3. +The three x86 expectations are updated to 21. A single regression exercises +all five integer operators in both machine operand orders, checks register +constraints, and encodes the results. Existing testFlags2 guards against the +Split-operand regression. + +## Incremental Iter setup + +Iter no longer resets and requeues the whole graph after parsing. `Node.init()` +queues initialized nodes, and Calls queue themselves so Iter can link targets +loaded after the call was parsed. Iter seeds its new global escape summary, +then drains the worklist. Import loading still resets the newly loaded nodes +and repairs affected neighbors. + +Removing the sweep also exposed an unused receiver left behind when field +lookup switches from an instance to its class. That path now releases the keep +and kills the receiver if unused. + +FldOffNode's base is data in slot 1. Slot 0 is reserved for control; putting a +data parameter there made inliner body discovery exclude an unresolved offset. +The regression `CallEndTest.testUnresolvedOffsetInInlineBody` checks that the +offset belongs to the function body even before its type resolves. + +## Type upgrades in Opto setup + +ParseAll still closes the named types and freezes the public interface after +loading all units. It no longer walks the IR. Opto installs those closed types +and resolves forward references during its existing reset walk. Setup runs no +peepholes against the partly reset graph: resolved FRefs propagate their input +type in SCCP and disappear during subsequent peepholes. Construction identities +also wait until this setup has installed complete field declarations. + +That walk retains Returns while call edges are rebuilt, gathers unresolved +numeric modes, and records dependencies for cleanup after SCCP. Type upgrades +also register cleanup dependencies, even if the eventual value type is unchanged. +Old Iter types are snapshots for change detection, not upper bounds after +recursive declarations have been closed. SCCP still asserts monotone falling +types and a complete worklist within its own solve. + +The move exposed assumptions formerly hidden by early upgrades. Resolving an +already known class name must retain its known fields instead of replacing them +with an empty placeholder. A Load must not forward a stored pointer whose open +shape is weaker than the Load's computed type. Escape must retain escapes from +the actual private value before narrowing it to its declared field type, so +selecting a Store out of a MemMerge does not introduce new escapes. + +An unknown return or memory effect carries FULL escape sets. StopCU and +GlobalEscape preserve that bound: narrowing it to public names would omit +private objects and callbacks that a subsequent load-forwarding rewrite can +reveal. Both summaries recompute from their inputs without retaining previous +escape sets. Refining a value removes possibilities; it never adds escapes +outside the old bound. IterPeeps has no special summary handling, and its +worklist assertion requires every node's type to lift, including queued nodes. +`testUnknownEscapesRefineToPrivateValues` checks both escape sinks; +`testPrivateRecursiveReturn` covers cyclic private objects and field loads. + +The ordinary dependency mechanism also covers signature refinement and lazy +imports. FunNode depends on its Return when refining its signature. Calls +depend on their target FunNode; while a target is absent, they depend on Start +and retry when a linker mapping is installed. Loading bodies and adding call +edges still use `Iter.repair` for graph changes, not for value refinement. + +SCCP's Start linking honors FULL for private targets too. Incoming arguments +are not themselves outgoing escapes; Stores, Returns, and external-call +arguments describe those effects. Constant singleton field slices carry the +stored value's escapes, not unrelated bulk-memory escapes frozen at the time +of folding. This preserves precision for local recursive callbacks. + +As bounds sharpen after SCCP, FunNode removes unknown callers even if concrete +callers remain. Called initializers retain their Return through StopCU because +CLInit has no Return edge. Removing an uncalled function queues the affected +Stops, and compilation-unit wrappers retain distinct identities even when +empty. These are worklist notifications and ownership rules, not extra passes. + +### Remaining precision issue with FULL escapes + +The monotone bounds expose a feedback problem in the existing grand cycle. +In `Chapter12Test.testPrivateRecursiveReturn`, SCCP sees BOTTOM for the final +load chain and therefore FULL escapes. These feed through Start's memory into +the function memory results. Post-SCCP forwarding resolves the return to `_B`, +but that memory cycle remains at MemBot and keeps private constructors callable +by unknown callers. This is conservative, but loses the previous dead-function +elimination. It does not justify narrowing BOTTOM to public names or adding +the IterPeeps widening repair back. + +For this example, the root Return goes from `[Ctrl, MemBot, Bot]` after Opto to +`[Ctrl, MemBot, *_B]` after TypeCheck; Stop's memory remains MemBot. The remaining +design question is how to avoid this feedback while retaining conservative +bounds and the existing pass budget. The current experiment leaves the printed +IR expectations unchanged so they continue to expose this loss of precision. + +The source-validity audit separates these cases from Chapter10 `testIfOrNull`. +That test originally returned the nullable pointer itself. A historical edit +changed it to `return bar.a;` without adding TypeCheck, leaving a real null +error hidden behind a printed-IR assertion. It now again returns `bar`, runs +through TypeCheck, and passes with `return Phi(Region,null,Test._Bar);`. + +All four remaining programs pass TypeCheck. The Chapter12 recursive-object +tests have one pending bad Load after Opto; forwarding eliminates every Load +and resolves the result to `17`, `_B`, or `_R`, while escape memory stays MemBot. + +The two Chapter17b forward-type tests now pass their original IR expectations +and explicitly run TypeCheck. Their undeclared `B` is an opaque external type, +not an arbitrary unknown local value. EscapeNode uses the frozen public +interface as its fallback for that type, preserving escapes already present +in its private and public memory inputs. This applies to both the actual private +value and the declared field bound: in `testForward1`, the private array element +type is already `B?`. Bounding only FIDXs is insufficient; FULL aliases expose +private class fields, which then expose their constructor FIDXs. + +CodeGen caches the fallback when ParseAll freezes the public interface. It +returns FULL until Opto's existing reset walk installs the closed types into +the IR. Only then does an open `_fref` reliably denote an external object. +Ordinary open local structs, `TypeScalar.BOT`, and abstract pointers still +require FULL. No new pass or IterPeeps hook is involved. + +### Escape-bound audit + +All Chapter29 `escapesFrom`, `XInt.FULL`, and `TypeMem.BOT` uses were reviewed, +including the equivalent `escapes` helper and indirect `makePrivate` uses. +The following remaining sites warrant work; they have not been narrowed here: + +* **StoreNode's three `escapesFrom(val)` paths.** The singleton constant, + private instance, and ordinary aliasing paths still treat an opaque external + value as FULL. A concrete example is: + + ```simple + struct _A { B? !b; new _A = { B? p -> b=p; }; }; + val wrap = { B? b -> return new _A(b); }; + return wrap; + ``` + + This passes TypeCheck, but the surviving Stores of `b` have FULL FIDX and + alias sets and keep an extra `_A` allocator. Do not mechanically substitute + the public default: singleton slices deliberately discard unrelated incoming + memory escapes. A narrower opaque bound must retain private values previously + given to external code, without freezing unrelated transient escapes into + singleton constants. Ordinary aliasing Stores already retain incoming sets. + +* **StopCU return values, CallNode external arguments, and SummaryNode arguments.** + These use `escapes`, which currently duplicates the unbounded `escapesFrom`. + `val identity = { B? b -> return b; }; return identity;` passes TypeCheck but + gives StopCU MemBot. Likewise, + `val send = { B? b -> { B? -> int } retain = "C"; return retain(b); }; return send;` + gives the native CallEnd MemBot. These are concrete instances of the same + opaque-type precision loss. A future change can share the bounded helper, + while retaining incoming/returned memory, explicit private arguments, and + imported-summary effects. StopCU's public function seed and `escapesAliases` + class seed describe known declarations; GlobalEscape's `escapes` calls merely + union already computed TypeMem sets. + +* **CLInitNode's possible-initialization result.** Even a known initializer + yields TypeMem.BOT until its ready flag is true; only the initialized flag's + slice is precise. This loses both memory-content and escape precision. + CLInit has an analysis call edge but no Return edge supplying callee effects. + Improving it needs a dependency on the initializer's effects, including + recursive dependencies. The public interface alone is not a safe cap: that + initializer can publish private callbacks. Its unresolved-flag BOT fallback + is also conservative, but normally disappears when the receiver resolves. + +* **CallEndNode's unknown or unlinked target result.** Both return TypeMem.BOT. + The unlinked case covers invalid calls and transient missing edges; SCCP links + valid finite targets before computing CallEnd. Truly unknown targets can be + local private functions as well as external functions, so a public-only cap + would be wrong. Native calls already use CallNode's argument/memory effects. + Any refinement must distinguish target provenance and retain explicit private + arguments; it is not the same small fix as an opaque external object. + +The other broad defaults appear justified: + +* TypeMem's generic BOTTOM/scalar/pointer cases and TypeStruct's unknown scalar + fields must include private callbacks that later value refinement can reveal. + Private-memory declarations/Phis use `makePrivate(BOTTOM)` for the same reason. + MemMerge's `makePrivate(struct)` describes actual fields, not an external + opaque object. +* Parser/function memory declarations, initial node types, TypeTuple.STATE, + and low-family error fallbacks in Store, MemMerge, BulkMemPhi, Start, and + TypeTuple need worst-case memory. CallNode and SummaryNode likewise cannot + promise bounded effects when their inputs are still arbitrary low values. +* Iter's import reset gives newly loaded nonconstant memory FULL before repairing + affected neighbors. Saved types belong to another caller context; constants + retain their own computed types. This is a safe pessimistic seed, though it + can contribute to the existing memory-cycle precision problem. +* TypeFunPtr's FULL signatures and TypeRPC.BOT describe unknown function/return + targets. Serialization/remapping preserves the FULL sentinel; type gathering + exercises it; LoopNode's `isa(TypeMem.BOT)` is a type-family check. These do + not independently manufacture an escape effect. + +Ignoring assertions, the remaining whole-node walks through TypeCheck are +Opto's setup/reset and TypeCheck's error scan. Class-init checking separately +scans function control flow and runs SCC over the resulting dependency graph. + +## Validation + +Chapter29's latest run tested 594 active cases with assertions: 590 passed and +four printed-IR comparisons failed. `make -k tests` ran raw0 (400/404), raw1 +(38), standalone (13), system (29), and fuzzer (1); the aggregate group (109) +was run separately because Make skips it after a prerequisite failure. +The remaining failures retain extra private constructors: Chapter12 `testCoRecur`, +`testCoRecur2`, `testCoRecur3`, and `testPrivateRecursiveReturn`. Both Chapter17b +forward tests pass unchanged goldens. TypeTest.testOpaqueExternalEscapes checks +both fallback sets, preservation of prior private escapes, and FULL for ordinary +unknowns. System, spill, import, callback, and constructor tests pass. The only +golden changed during the earlier source-validity audit belongs to the restored +`return bar;` source; none were changed to accept extra functions. + +The offset regression fails with the old slot-0 layout. Constructor and +boundary tests pass, including both missed rejections and the prior NPE. +Printed-IR expectations omit the dead private-helper MemTop Returns; no +rejection expectations were relaxed. The three String spill checks now expect +21 on x86, with the same live functions and inlining decisions. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 3547b86c..9c954197 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -100,7 +100,9 @@ public class ClassInitDependencies { // CLInit adds a class init requirement to this function // (plus all parent classes) - if( cfg instanceof CLInitNode init ) { + // An invalid receiver can still be Scalar.BOT here. Its Load + // reports the error at TypeCheck; it does not name a class to init. + if( cfg instanceof CLInitNode init && init.cu()!=null ) { FunNode clz = code.link(init.cu()); // referred to iset.put(clz.sig().fidx(),1); // Add to edge set if( sites!=null && sites.atX(clz.sig().fidx())==null ) sites.setX(clz.sig().fidx(),init._loc); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 6e1c0af5..ba7c0c1d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -102,11 +102,10 @@ public class CodeGen { } private void gatherPublicFields(TypeStruct clz, boolean classFields) { - boolean hasCtor = clz.field("") != null; for( Field fld : clz._fields ) { - // With a user constructor, class:N.N is the private . + // Private-memory helpers are reached through their allocator. if( fld._fname.charAt(0)=='_' || fld._t==Type.TOP || - (hasCtor && clz.hiddenInit(fld)) ) continue; + clz.hiddenInit(fld) ) continue; if( classFields ) _publicAliases = XInt.make(_publicAliases,fld._alias); if( fld._t instanceof TypeFunPtr tfp ) _publicFIDXs = XInt.meet(_publicFIDXs,tfp._fidxs); @@ -125,14 +124,13 @@ public class CodeGen { } private int[] _publicFIDXs, _publicAliases; + private TypeMem _publicEscapes; /** - * Collect every possible public escape - after ParseAll is done - in case - * some code calls a generic function. Example: - * var apply = = { {int->int} f, int x -> f(x); }; // Generic apply() call - * The CallEnd from `f(x)` has to use generic TypeMem.BOT, which - * immediately escapes *everything* including known private functions. - * As weak as this is, its still sharper than "everything". + * Snapshot the public interface after ParseAll for interface checks and + * the default escapes of opaque external types. This is not an upper + * bound on all escapes: a public function can return a private object or + * callback. Escape flow preserves those actual values separately. */ void freezePublicInterface() { assert _publicFIDXs==null && _publicAliases==null; @@ -157,12 +155,21 @@ public class CodeGen { fidxs = XInt.make(fidxs,fidx); } _publicFIDXs = fidxs; + _publicEscapes = TypeMem.START.makeFrom(_publicFIDXs,_publicAliases); } public int[] publicFIDXs() { assert _publicFIDXs !=null; return _publicFIDXs; } public int[] publicAliases(){ assert _publicAliases!=null; return _publicAliases; } public boolean publicInterfaceFrozen() { return _publicFIDXs != null; } + // Before Opto upgrades the IR, a forward reference might still name a + // local class. Afterwards, unresolved names describe external objects. + public TypeMem publicEscapes() { + if( _phase==null || _phase.ordinal() { - // Type import can reconcile a constant's declaration. - n._type = n instanceof ConstantNode ? n.compute() - : hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); - code.add(n); - return null; - }); + // Parsing queues initialized nodes and phase-sensitive peepholes. + // Only the new escape summary needs seeding here. + code.add(code._globalEscapes); code._iter.iterate(code); // Expensive assert. assert !CodeGen.expensiveAssert() || Opto.fixedPointCheck(code); } - // Stabilize existing node types before releasing source error obligations. - // No rewrites: even an unused illegal Load must still be checked here. - public static void types(CodeGen code) { - // Definite initialization needs the optimistic solution around loops: - // an unchanged initialized field must not be stuck at its old BOT seed. - Ary typed = new Ary<>(Node.class); - code._start.walk(n -> { typed.add(n); n._type = Type.TOP; code.add(n); return null; }); - Node n; - while( (n = code._iter._work.pop())!=null ) { - if( n.isDead() ) continue; - Type t = n._type.meet(n.compute()); - if( t==n._type ) continue; - n._type = t; - code.addAll(n._outputs); - n.moveDepsToWorklist(); - } - code.addAll(typed); - } - - private static Type iterEscapeReset(Type t) { - if( t instanceof TypeMem mem ) - return mem._one ? mem : mem.makeFrom(XInt.FULL,XInt.FULL); - if( t instanceof TypeTuple tt ) { - TypeTuple rez = tt; - for( int i=0; i { // Ignore most in-progress things if( n.iskeep() ) return null; - // Types must be forwards, even if on the worklist. + // Types must lift, even if on the worklist. Type nval = n.compute(); assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n; if( list.on(n) ) diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java index aa997204..0c37ce39 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; @@ -30,7 +31,8 @@ abstract public class Opto { WorkList deps = new WorkList<>(); WorkList changes = new WorkList<>(); Ary modes = new Ary<>(Node.class); - resetToTop(code,oldTypes,modes,deps); + Ary returns = new Ary<>(ReturnNode.class); + resetToTop(code,oldTypes,modes,deps,returns); unlinkStart(code); // OPTIMISTIC INTERPROCEDURAL SCCP @@ -50,24 +52,73 @@ abstract public class Opto { // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. moveChangesToWorklist(code, oldTypes, changes); + // Unknown callers and concrete call edges have now been rediscovered. + for( ReturnNode ret : returns ) code.add(ret.unkeep()); } - // Reset Types before running the worklist algorithm - private static void resetToTop(CodeGen code, Ary oldTypes, Ary modes, WorkList deps ) { + // Transition from Iter's pessimistic graph to SCCP's optimistic solve in + // one walk. Parsing has closed the named types; install them in the IR + // and resolve forward references before resetting each value to TOP. + // Do not run peepholes here: neighboring nodes may not yet be upgraded or + // reset. SCCP sees the completed setup, and IterPostOpto handles rewrites. + // + // The same walk preserves Returns while call edges are rebuilt, remembers + // old types for incremental cleanup, and gathers numeric modes and phase + // dependencies. These are setup duties, not separate graph passes. + private static void resetToTop(CodeGen code, Ary oldTypes, Ary modes, WorkList deps, Ary returns ) { code._start.walk( x -> { + // A snapshot for change detection, not an upper bound: closing + // recursive declarations can change types in either direction. + oldTypes.setX(x._nid,x._type); + if( x.upgradeType(Parser.TYPES) ) deps.push(x); + if( x instanceof FRefNode fref ) resolveForward(code,fref); + // Rebuilding call edges must not DCE a temporarily uncalled body. + // Type-level function references can rediscover it later in SCCP. + if( x instanceof ReturnNode ret ) returns.add(ret.keep()); // Opto ends Parm.inProgress(), enabling constant folding even // when a parameter's type was already constant before SCCP. if( x instanceof ParmNode && x._type.isHighOrConst() ) deps.push(x); + // Construction identities may fold after the optimistic solve. + // Adds may need sorting after imported node IDs were assigned. + if( x instanceof ConstructNode || x instanceof AddNode ) deps.push(x); // SCCP adds call edges and default arguments, not numeric // operations. Gather unresolved modes on this required walk. if( x instanceof ModeNode mode && mode.mode()==0 ) modes.push(x); - oldTypes.setX(x._nid,x._type); // Compare the final SCCP type with Iter's type x._type = Type.TOP; // Reset all Nodes to TOP code._iter.add(x); // Visit everybody at least once; most Nodes produce better than TOP return null; } ); } + private static void resolveForward(CodeGen code, FRefNode fref) { + if( fref.nIns()!=1 ) return; + boolean alloc = fref._name.endsWith("."); + String clzName = alloc + ? fref._name.substring(0,fref._name.length()-".".length()).intern() + : fref._name; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); + if( clz==null ) return; + Node con; + if( alloc ) { + Field ctor = clz.field(""); + if( ctor==null || !(ctor._t instanceof TypeFunPtr tfp) ) { + String name = clzName.startsWith(TypeStruct.CLZ) + ? clzName.substring(TypeStruct.CLZ.length()) : clzName; + int dot = name.lastIndexOf('.'); + throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); + } + FunNode fun = code._link(tfp); + if( fun==null ) return; + con = new FunPtrNode(tfp,code._start,fun.ret()); + con._type = Type.BOTTOM; // No Iter bound; the Return may already be reset. + } else { + con = new ConstantNode(TypeMemPtr.make((byte)2,clz,true)); + } + // The new input is visited by the reset walk too. Let SCCP propagate + // its value; replacing the FRef is a later peephole. + fref.addDef(con); + } + // Only entry initializers start with unknown callers. Discover every // other function through calls or escaping values during SCCP. @@ -90,8 +141,9 @@ abstract public class Opto { // Unhook from Stop without treating the ReturnNode as // DEAD. It stays in limbo until Opto links when a caller // is discovered (or not, and the function is really dead). - stop._inputs.del(i--); - ret.delUse(stop); + // The reset walk keeps Returns alive. Use normal edge + // editing so cleanup also revisits an emptied StopCU. + stop.delDef(i--); } // Unlink the existing conservative call linkages. for( int j=1; j"); - String clzName = alloc - ? fref._name.substring(0,fref._name.length()-".".length()).intern() - : fref._name; - TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); - if( clz == null ) - return null; - Node con; - if( alloc ) { - Field ctor = clz.field(""); - if( ctor == null || !(ctor._t instanceof TypeFunPtr tfp) ) { - String name = clzName.startsWith(TypeStruct.CLZ) - ? clzName.substring(TypeStruct.CLZ.length()) : clzName; - int dot = name.lastIndexOf('.'); - throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); - } - FunNode fun = code.link(tfp); - if( fun == null ) return null; - con = new FunPtrNode(tfp,code._start,fun.ret()).peephole(); - } else { - // Class pointer constant: - TypeMemPtr clzptr = TypeMemPtr.make((byte)2,clz,true); - con = code.con(clzptr); - } - // Replace and optimize - fref.addDef(con); - code.add(fref); - } - // Adds sort by NIDs, which just got shuffled - if( n instanceof AddNode add ) - code.add(add); - // All imported bodies are loaded; link them before Iter checks types. - if( n instanceof CallNode call && !NEEDS_LOAD.isEmpty() ) - code.add(call).idealize(); - return null; - } ); - // The complete public interface is now known. Keep this independent // of later graph/linker liveness so SCCP computations remain local and // monotonic. - code.P.checkConstruction(); code.freezePublicInterface(); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index ac792988..f1aa18ef 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -425,6 +425,21 @@ public class RegAlloc { Node[] conflicts = lrg._selfConflicts.keySet().toArray(new Node[0]); Arrays.sort(conflicts, (x,y) -> x._nid - y._nid ); + // A commutative two-address tie may join a whole chain to a Phi even + // when only the Phi and an earlier def actually overlap. Reuse the + // failed-range walk to find those ties before inserting copies. + // A Split's single use is artificial: leave earlier splitting intact. + findAllLRG(lrg); + for( int i = 0; i<_ns._len; i++ ) { + Node n = _ns.at(i); + if( lrg(n)==lrg && n instanceof MachNode mach && mach.twoAddress()==1 && + mach.commutes() && !(n.in(2) instanceof SplitNode) && + n.in(2).nOuts()==1 && lrg(n.in(2))!=lrg ) + n.swap12(); + else _ns.remove(i--); + } + // Reuse the scratch list to remember just the ties we broke. + // First encounter with a loop Phi: try only cold splits this round. // Remember the Phi across rounds so a persistent self-conflict forces // the hot def/backedge splits on the next encounter. @@ -466,7 +481,9 @@ public class RegAlloc { insertBefore(phi,i,"use/self/phi",round,lrg); } // Split before two-address ops which extend the live range - if( def instanceof MachNode mach && mach.twoAddress()!= 0 ) + // A commuted operand already broke this tie. Rebuild it in the + // next normal coloring round instead of copying the old range. + if( def instanceof MachNode mach && mach.twoAddress()!=0 && _ns.find(def)==-1 ) insertBefore(def,mach.twoAddress(),"use/self/two",round,lrg); } return true; diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index abd8628d..30e1415e 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -19,10 +19,12 @@ abstract class TypeCheck { code._classInitDependencies = deps; // Serialize reuses this checked graph. Ary errs = new Ary<>(Node.class); + Ary constructs = new Ary<>(ConstructNode.class); code._stop.walk( n -> { if( n.err() != null ) errs.add(n); if( n instanceof CLInitNode ) code.add(n); + if( n instanceof ConstructNode con ) constructs.add(con); return null; }); @@ -30,25 +32,35 @@ abstract class TypeCheck { // Prefer an originating error over a secondary error caused by a // BOTTOM input. If all errors are downstream-poisoned, retain // the old first-error behavior. - Node min = null; - for( Node n : errs ) - if( noBottomInputs(n) ) - { min = n; break; } - if( min==null ) - min = errs.at(0); + Node min = errs.at(0); for( Node n : errs ) if( n!=min && - noBottomInputs(n) && + (errorRank(n)=0; fidx = XInt.next(tfp.fidxs(),fidx) ) { - FunNode fun = CodeGen.CODE._link(fidx); - if( fun!=null && !fun.isClz() ) { - dep.addDepForwards(fun); - if( fun.unknownCallers() ) return true; - } - } - return false; - } - // As in the escape chapter, native code may retain an argument even if // this path never returns. StopCU reads this independently of CallEnd. TypeMem exposed(Node dep) { @@ -165,7 +153,8 @@ public class CallNode extends CFGNode { // Walk the bits and link for( int fidx = XInt.next(fidxs,0); fidx > 0; fidx = XInt.next(fidxs,fidx) ) { FunNode fun = CodeGen.CODE.link(fidx); - if( fun!=null && !fun._folding && !linked(fun) ) + if( fun==null ) addDepForwards(CodeGen.CODE._start); + if( fun!=null && !addDep(fun)._folding && !linked(fun) ) progress = link(fun); } } @@ -256,6 +245,9 @@ public class CallNode extends CFGNode { // Check for args for( int i=0; i