diff options
| author | Cliff Click <cliffc@acm.org> | 2026-11-15 11:20:40 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-11-15 11:20:40 -0800 |
| commit | f0a6c6757a795b8e186de0076836a87acef59fa7 (patch) | |
| tree | ef45c1b58093420bbd2de6647274139e46539bfe /chapter30/docs | |
| parent | 7e66b7ae6b00a2e1652db32f01f0bf480508ef05 (diff) | |
| download | Simple-f0a6c6757a795b8e186de0076836a87acef59fa7.tar.gz Simple-f0a6c6757a795b8e186de0076836a87acef59fa7.zip | |
Graphics now allow resizemain
Reorganize docs.
Fix bugs X86 LOad+cmp scheduling.
Math intrinsics
Diffstat (limited to 'chapter30/docs')
| -rw-r--r-- | chapter30/docs/30-grammar.ja.md | 2 | ||||
| -rw-r--r-- | chapter30/docs/30-grammar.md | 2 | ||||
| -rw-r--r-- | chapter30/docs/construction-groups.md | 241 | ||||
| -rw-r--r-- | chapter30/docs/deferred-construction.md | 385 | ||||
| -rw-r--r-- | chapter30/docs/escape-flow.md | 147 |
5 files changed, 2 insertions, 775 deletions
diff --git a/chapter30/docs/30-grammar.ja.md b/chapter30/docs/30-grammar.ja.md index 13fd500d..89e4793e 100644 --- a/chapter30/docs/30-grammar.ja.md +++ b/chapter30/docs/30-grammar.ja.md @@ -47,7 +47,7 @@ constructorParameterList : (constructorParameter ','?)+ ; constructorParameter : type '^'? bindingModifier? IDENTIFIER ; // ^ accepts an unfinished struct reference; ? independently permits null. // Only self may be read while incomplete; ^ arguments may be stored/forwarded. -// A new result is incomplete iff an actual argument is. See construction-groups.md. +// A new result is incomplete iff an actual argument is. See ../../chapter29/README.md#incomplete-types. // A method is an ordinary fixed function binding in a struct definition. // The compiler supplies self; it is not written in parameterList. diff --git a/chapter30/docs/30-grammar.md b/chapter30/docs/30-grammar.md index 3bddfb87..189a7c04 100644 --- a/chapter30/docs/30-grammar.md +++ b/chapter30/docs/30-grammar.md @@ -56,7 +56,7 @@ constructorParameterList : (constructorParameter ','?)+ ; constructorParameter : type '^'? bindingModifier? IDENTIFIER ; // ^ accepts an unfinished struct reference; ? independently permits null. // Only self may be read while incomplete; ^ arguments may be stored/forwarded. -// A new result is incomplete iff an actual argument is. See construction-groups.md. +// A new result is incomplete iff an actual argument is. See ../../chapter29/README.md#incomplete-types. // A method is an ordinary fixed function binding in a struct definition. // The compiler supplies self; it is not written in parameterList. diff --git a/chapter30/docs/construction-groups.md b/chapter30/docs/construction-groups.md deleted file mode 100644 index 197a6082..00000000 --- a/chapter30/docs/construction-groups.md +++ /dev/null @@ -1,241 +0,0 @@ -# Construction: field types and incomplete references - -Instance constructors use ordinary field Loads and Stores. There are two checks: -whether a field has a value, and whether an object reference is usable outside -construction. Neither requires a collection of constructor-group identities. - -## Field initialization - -New produces private `TypeMem` containing the object's `TypeStruct`, with -`TypeScalar.BOT` for fresh fields. Defaults emit ordinary Stores: zero for an -ordinary integer, null for a nullable pointer, no Store for a required field. -An assignment strongly updates its field in private memory. Phi meets the -incoming memories; a missing live arm survives because `BOT.meet(7) == BOT`. -An initialized unknown integer has `TypeInteger.BOT`, not `TypeScalar.BOT`. -Arrays retain their language-level zero filling. - -One `#selfMem` binding carries this memory through scopes and returns. A Load -checks its incoming field type. Constructor completion checks the merged Return -memory; the explicit constructor receives the declaration initializer's merged -result, including early exits. There is no backwards initialization query, -per-field parser state, or store-all instance exit. - -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 -retain their memory family when there are no live callers. Function-valued -fields retain their declared signatures in private summaries, avoiding repeated -unfolding of a constructor whose returned memory contains its own function field. -Class singleton initialization keeps its older store-at-exit implementation. - -## Partial references and readable fields - -`self` and incoming `C ^arg` parameters are incomplete references. `C? ^arg` -also accepts null. Ordinary functions and constructors accept the qualifier on -struct parameters; arrays cannot be qualified this way. - -- An allocation result is incomplete if any actual argument is incomplete. -- With only completed arguments, including null, the result is complete. -- An incomplete reference may be stored into self or passed to a `^` parameter. -- Ordinary calls and stores into other objects require completed references. -- A borrowed partial can read fields its incoming type proves initialized. - It cannot write fields, even non-finals. Exact local aliases of self retain - the original constructor's access to its current private memory. -- An object-reference field read through a partial is conservatively - incomplete, with no initialized-field guarantees for its referent. There is - no inference of initialized-field requirements on `^` arguments. - Arrays are already initialized and cannot receive - incomplete elements, so an initialized array field can be used normally. - -For example: - -```simple -struct Child { - Test.Parent? parent; - new Child = { Test.Parent? ^par -> parent = par; }; -}; -struct Parent { - Child child; - int~ payload; - new Parent = { int n -> - child = new Child(self); // Incomplete result: self is incomplete. - // Retention does not authorize reading parent.payload through child. - payload = n; - }; -}; -val parent = new Parent(arg); -val local = new Child(parent); // Complete argument, complete result. -return local.parent==parent; // Lookup is allowed. -``` - -Here `Test` names the source unit. After the root Parent constructor completes, -the entire cycle is usable: all members have initialized their own fields, and -none could expose an incomplete reference to ordinary code during construction. -The Child constructor still treats its `^par` as incomplete when the actual -argument is complete. This public constructor also has unknown callers, whose -partial arguments promise no initialized fields, so `par.payload` is unreadable. - -## Forward field views - -At a use of self, `InitViewNode` combines the pointer with that program point's -private memory. Its TypeMemPtr contains declared types for initialized fields -and Scalar.BOT for missing fields. The node retains the declaration separately -from the incoming flow shape, so an exact self alias captured before a Store -can receive a fresh view afterward. Earlier calls retain their earlier views. - -For example, a private helper can read `x` while `y` is still unset: - -```simple -struct _C { - int~ x; - int~ y; - new _C = { int n -> x=n; y=_read(self); }; -}; -val _read = { _C ^p -> return p.x; }; -return new _C(arg).y; -``` - -Parm meets the incoming shapes using the normal type flow. If any live caller -lacks `x`, Scalar.BOT survives and the Load reports the missing initialization. -Unknown callers supply an empty field promise. Parsing must also start borrowed -parameters at that bound: otherwise early folding of `p.x*0` could hide a bad -read before SCCP. The hidden constructor receiver retains its declaration; -its private memory supplies its read checks and precise field updates. - -Values still come from normal memory. Before a call borrowing self, EscapeNode -borrow slices carry the current constructor Stores onto the ordinary call -memory edge. These slices are aliasable and do not publish the private identity -or its fields into the global escape sets. No hidden partial-memory arguments, -field bitsets, additional passes, or recursive flow queries are introduced. - -InitView folds before TypeCheck when its input already has the same type and -retains a structural partial view. Nested partial-only Construct wrappers also -collapse. A Parm's current partial type alone is insufficient: inlining may -later substitute a complete actual argument, which must not grant the borrowed -parameter permission to write or publish that object. The completion form of -Construct already folds once its memory proves initialization and its result -type matches its input. - -TypeCheck checks the consumers and erases remaining InitViews along with the -checked Construct boundaries in its existing walk. A surviving field view is -not necessarily erroneous: a reader may need only the initialized subset. -Construct remains necessary for -final-field completion and for the partial qualifier of each source `new`. -Alias Phis and nested reference loads are conservative; they do not acquire -the original constructor's write permission. This prototype adds no general -ban on overlapping allocations of the same class: only the owning receiver -uses private memory, while borrowed reads use aliasable memory. - -## Aliases and loops - -Incomplete is a property of a value, not just the current contents of a parser -Var. Consider `while (n--) { use(p); p = self; }`: the backedge introduces an -incomplete value after `use(p)` has been parsed. `TypeMemPtr._partial` carries -that restriction through ordinary forward typing. It is an independent -two-point lattice: meet ORs the restriction and dual complements it. Copies, -conversions, Stores, and Phis preserve it; a merge is incomplete if any live -input is incomplete. A `^` formal stays incomplete even when its known callers -are complete. The receiver's private memory identifies the own-self exception; -another incomplete pointer of the same class has no such permission. - -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 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 -`new` boundary with complete arguments makes the entire reachable cycle usable. -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 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` 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. - -`PartialReadTest` exercises field reads, missing fields, forwarding, merged -callers, loops, exact aliases, constructor retention, and borrowed write and -publication restrictions. `ConstructionGroupTest` exercises cycles, complete/null arguments, prohibited -lookups/publication, aliases, branch merges, complete and incomplete loop -backedges, and declared restrictions with only complete callers, including an -uninlined constructor through machine encoding. `ConstructorCompletionTest`, -`FinalConstructionTest`, and `BoundaryTest` exercise field-memory semantics. -The former inferred-requirement litmus tests are preserved, explicitly deferred, -in `ConstructionRequirementsTest`. Separate compilation of `^` functions is -still deliberately unsupported. The pointer qualifier has an object-file -representation, but importing and checking the full construction contract is -outside this experiment. Rebuild chapter 29 object files after the type-format -change. - -## Deferred field-aware contracts (2026-11-07) - -Decision: do not implement inferred contracts now. Cliff considers the required -infrastructure too large for the feature alone; revisit when a general -backwards/liveness flow is justified, potentially for memory management. -The later forward-field-view prototype above does not implement this contract -discovery proposal. Separate compilation of `^` interfaces remains rejected. - -The intended extension would let functions and constructors receive partially -initialized objects, read initialized fields, retain partial references with -their restrictions, and write non-final fields. Only the original constructor -would retain permission to initialize/reassign its own final fields; passing a -pointer must not pass that permission. Final-field reads during construction -would not establish value stability against later writes by that constructor. - -The proposed contract representation uses normal types, not a separate field -bitset. For a function reading only `P.pi`, its unknown-caller default would be -schematically `Partial{pi:declared-pi-type, name:TypeScalar.BOT}`. Scalar.BOT -means no initialization guarantee, not a requirement that the caller leave the -field unset. Required fields receive their declared types, covering every legal -external caller. MEET with actual arguments preserves those guarantees only -when the callers satisfy them; extra initialized fields supplied by locals do -not strengthen the body beyond the external contract. TypeStruct/Field already -meet field contents, and nested/cyclic types can represent nested contracts. -TOP is not the missing-initialization marker. - -Cliff proposed discovering conservative, context-insensitive requirements after -Iter and before SCCP. Freeze the resulting default argument types on functions; -SCCP consumes them without refining the contracts. Reads on branches SCCP later -eliminates may still impose requirements, as may reads following assignments. -That rejection of some valid programs is acceptable for an opt-in `^` feature. -Combine compatible requirement shapes with JOIN; combine possible caller states -with MEET. Keep the contract distinct from the merged Parm type, and check each -actual argument against it for a call-site diagnostic such as -"foo requires Partial.pi to be initialized". Serialize contracts with declaration -metadata so checking imported calls does not require loading bodies. - -The complication is discovering and propagating those contracts. Local SSA -aliases share values; Phi demands reach every input. A demand on a loaded field -becomes a nested receiver requirement. Calls substitute actual arguments for -formals, and recursive forwarding needs a convergent propagation rule. Cyclic -types represent recursive requirements but do not by themselves prevent a -discovery algorithm from unfolding progressively deeper paths. Indirect calls -need contracts available through their callable interfaces; returns need usable -guarantees without retroactively strengthening an exported contract for a client. -Stored references and helper writes also require a coherent account of private -construction memory and object identity; that discussion was deliberately left -unfinished. None of this requires H-M or bidirectional type inference, but it -does require a substantial backwards demand analysis to handle well. - -The ignored ConstructionRequirementsTest retains useful litmus cases, not an -approved implementation plan. Do not restart this work without a new request. diff --git a/chapter30/docs/deferred-construction.md b/chapter30/docs/deferred-construction.md deleted file mode 100644 index 104ab9e9..00000000 --- a/chapter30/docs/deferred-construction.md +++ /dev/null @@ -1,385 +0,0 @@ -# Deferring construction checks: experiment - -The [escape-flow continuation](escape-flow.md) supersedes the frozen-public -fallback and remaining recursive-test failures described later in these notes. -All four recursive examples now pass their original printed-IR expectations. -The older audit below records the evidence that led to this change. - -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/chapter30/docs/escape-flow.md b/chapter30/docs/escape-flow.md deleted file mode 100644 index 8ad49f15..00000000 --- a/chapter30/docs/escape-flow.md +++ /dev/null @@ -1,147 +0,0 @@ -# Outside-world escape flow - -The `escape-flow` branch developed this design in Chapter29 and backported it -to Chapters 28a/28b. Chapter28a uses `LocalIds` and its existing initializer -root/lowering protocol; Chapter28b adds saved summaries and cofinite identity -remapping. Neither port imports Chapter29's deferred-construction model. - -## The cycle - -The outside world's access to local objects and functions is a value in the -Start/Stop cycle. Public declarations are not that value. The frozen public -interface inventory has been removed; public-method and public-alias tests -check the converged outside escape sets directly. - -At Opto setup, the outer Start receives a constant foreign-identity seed: - -``` -foreign identities = FULL minus identities owned by this compilation -outside identities = foreign identities union discovered local escapes -``` - -Known native function and storage identities are foreign too. The infinite -tail permits future foreign functions even when no local callback has escaped. -The finite exclusions include registered imported identities, including bodies -represented by summaries. This scans identity tables, not the IR. Opto's -existing reset/worklist solve discovers the local escapes. - -StartCU includes the shared outside state. Infinite FIDX sets must retain their -exclusions: `Opto.linkStart` checks each local function's membership rather than -treating every cofinite set as FULL. Serialization remaps a cofinite set by -remapping its finite exclusions and complementing again. - -Before Opto, outside queries remain pessimistic. During SCCP, a consumer can -read the foreign seed before Start has run: otherwise a temporary finite set -can turn a generic foreign callback into an unrelated local function with the -same arity. No previous escape result is accumulated to repair value flow. - -## Consumers and dependencies - -* Memory and callback defaults for unknown callers use Start's memory - projection. Parm applies its declared callback signature to the escaping - FIDX set. Defaults whose values do not depend on escapes remain constants. -* Unknown/native CallEnd results use the outside state and the current call's - exposed arguments. Callback results are bounded by their declared signature - and the outside FIDX set. Explicit linked Return effects are retained. -* CallEnd registers a direct dependency on Start. Depending only on Call is - insufficient: Call can stay CONTROL while the outside set changes. This - first implementation uses `addDepForwards`; it does not change CallEnd's - input layout or introduce a synthetic Fun/Return pair. -* Infinite calls use the outside continuation. Escaped local functions remain - callable through Start, and their effects return through Stop. Attaching - every same-arity body to an infinite call is incorrect: argument/result - families may differ despite the equal arity. -* Outgoing Call argument exposure is independent of CallEnd, including a call - that never returns. The shared fixed point also permits immediate callback - round trips and reentrant calls. -* Opaque external values in Escape, Store, Return, and imported-summary paths - use the current outside/input-memory bound. Explicit private values and - already accumulated escapes remain included. Arbitrary local BOTTOM values - still require FULL. -* Function-valued Loads use their memory input's FIDX bound, joined with the - field declaration. They do not independently manufacture an escape set. - -CLInit was another unconditional producer of FULL. During Opto it now depends -on the known initializer's Return and merges those effects with incoming -memory. It waits for live memory before publishing effects. Lowering computes -the replacement CallEnd's linked type before exposing its projections, so a -temporary unlinked MemBot cannot widen the already analyzed caller. - -## Why the recursive tests needed local precision too - -All four former Chapter12 printed-IR failures pass their original expectations. -The problem was not solely an outside-call default: - -1. Convert widened a non-null pointer to a nullable declaration until its later - identity rewrite. It now preserves non-nullness in compute. Preserving the - entire source shape conditionally failed the existing monotonicity test; - shape and access still follow the declaration. -2. A Load could wait until post-SCCP Store forwarding to recover that non-null - pointer. In the meantime the next dereference produced BOTTOM, which fed - FULL around the memory cycle and revived private constructors. -3. Forwarded addresses, resolved field aliases, and already-bypassed CLInit - projections were also waiting for graph rewrites. - -Load's existing forwarding search now supplies pointer value facts during -compute, without constructing or rewriting nodes. It can recognize a stored -address through a valid pointer conversion or a proven forwarded Load, use a -resolved named field before layout, and follow an existing CLInit bypass. -The same dependency mechanism reruns the search when its evidence changes. -Nullable/incomplete access checks still precede this sharpening; arbitrary -memory Phis and unknown stores remain barriers. This adds local queries, not a -new whole-program pass, analysis map, or second IR. - -## Hidden class receivers - -A class function's hidden `#self` defaults to its owning class singleton. -Seeding that input with TypePtr.PTR used to give FULL escapes when forwarded -to an unknown callback. For example: - -```simple -val _hidden_noInline = { int n -> return n+2; }; -val apply_noInline = { {int->int} f,int n -> return f(n); }; -return apply_noInline; -``` - -`FunNode.defaultArg` now supplies the Test class singleton for this receiver, -both during parsing and when Opto reconnects unknown callers. The callback -parameter still reads Start dynamically. The printed-IR regression verifies -that only `<clinit>` and `apply_noInline` escape; `_hidden_noInline` stays private. - -The function signature retains TypePtr.PTR in this slot. The backends use it -to identify the hidden ABI argument, and callback annotations must not bind -the receiver to the class where the annotation appears. Explicit calls still -supply their actual receiver; instance methods keep their declared object -type. This sharpens the default input, not every abstract pointer: a local -merge of a private object and private callback can also have an abstract -pointer type, so capping arbitrary TypePtr values at outside escapes is unsound. - -## Remaining design question - -Late imported identities also deserve further precision work: identities not -registered when Opto starts lie in the foreign tail. Existing import tests -exercise correctness, but this can remain conservative when bodies arrive -later. This limitation is not repaired by resetting the whole IR. - -## Validation - -The combined `make -k tests CHAPTERS="chapter28a chapter28b chapter29" CTAGS=` -run passes with assertions: 538 active tests in Chapter28a, 578 in Chapter28b, -and 601 in Chapter29. Shared printer and ISA checks pass too. The log is saved -under ignored `build/escape-backport-final.log`. - -`EscapeFlowTest` covers opaque wrappers with three worklist seeds, foreign -callback parameters, private callbacks passed to and returned from native code, -and a CallEnd dependency that responds when only Start's escape set changes. -It also checks that public allocators escape while their private-memory helpers -do not. Class-init tests cover unknown callback cycles; saved-library tests in -28b/29 verify private-function exclusions survive identity remapping. -The existing suites cover nonreturning native calls, class-init cycles, -constructor rejection, serialization, imported callbacks, and three backends. -The four recursive-class examples also pass a separate 16-case worklist-seed -check. Backport IR expectations now retain public allocator Returns instead of -private-memory helper Returns. The String allocation/encoding/export fixtures -in 28a/28b/29 now declare `_hashCodeString` before the public `hashCode` wrapper, -so the implicit return exposes the wrapper. Their measured spill expectations -are 12/8/6 (x86/RISC-V/ARM); native x86 export expects 12. The reordered fixture -also measures 8 on RISC-V before the backport, versus the old order's 6. |
