From ce3b04603d7af995004291d9a7eb668f313e6772 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 6 Nov 2026 16:06:02 -0800 Subject: Cleanup public escapes Drop "frozen" public escapes, and recompute in Start/Stop so Opto gets a precise escape set. Rename XInt.free -> XInt.alloc Fix some String tests to not escape by default --- chapter29/README.md | 6 +- chapter29/docs/deferred-construction.md | 5 + chapter29/docs/escape-flow.md | 147 +++++++++++++++++++++ .../com/seaofnodes/simple/codegen/CodeGen.java | 69 ---------- .../com/seaofnodes/simple/codegen/GlobalBits.java | 13 ++ .../java/com/seaofnodes/simple/codegen/Opto.java | 24 ++-- .../com/seaofnodes/simple/codegen/ParseAll.java | 5 - .../com/seaofnodes/simple/node/CLInitNode.java | 20 ++- .../com/seaofnodes/simple/node/CallEndNode.java | 15 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 4 +- .../com/seaofnodes/simple/node/ConvertNode.java | 11 +- .../com/seaofnodes/simple/node/EscapeNode.java | 2 +- .../java/com/seaofnodes/simple/node/FunNode.java | 11 ++ .../java/com/seaofnodes/simple/node/LoadNode.java | 46 +++++-- .../java/com/seaofnodes/simple/node/ParmNode.java | 7 +- .../java/com/seaofnodes/simple/node/StartNode.java | 13 ++ .../com/seaofnodes/simple/node/StopCUNode.java | 2 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 7 +- .../com/seaofnodes/simple/node/SummaryNode.java | 6 +- .../com/seaofnodes/simple/parser/Functions.java | 2 +- .../java/com/seaofnodes/simple/parser/Types.java | 4 +- .../main/java/com/seaofnodes/simple/type/Type.java | 5 +- .../com/seaofnodes/simple/type/TypeFunPtr.java | 4 + .../java/com/seaofnodes/simple/type/TypeMem.java | 13 +- .../com/seaofnodes/simple/type/TypeStruct.java | 2 +- .../main/java/com/seaofnodes/simple/type/XInt.java | 17 +-- .../java/com/seaofnodes/simple/Chapter20Test.java | 23 ++-- .../java/com/seaofnodes/simple/Chapter21Test.java | 38 +++--- .../java/com/seaofnodes/simple/Chapter25Test.java | 66 ++++++--- .../simple/ClassInitDependenciesTest.java | 22 +++ .../java/com/seaofnodes/simple/EscapeFlowTest.java | 112 ++++++++++++++++ 31 files changed, 547 insertions(+), 174 deletions(-) create mode 100644 chapter29/docs/escape-flow.md create mode 100644 chapter29/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java (limited to 'chapter29') diff --git a/chapter29/README.md b/chapter29/README.md index 9bd5843e..5dae8de6 100644 --- a/chapter29/README.md +++ b/chapter29/README.md @@ -42,7 +42,11 @@ 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 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). +The earlier experiments are recorded in [the late-check notes](docs/deferred-construction.md). +The [outside-world escape flow](docs/escape-flow.md) now restores the four +recursive-class IR expectations and gives hidden class receivers their owning +singleton as the unknown-caller default. The frozen public-interface inventory +is removed; late imported identities remain a precision follow-up. Class singleton initialization retains its existing store-at-exit path. diff --git a/chapter29/docs/deferred-construction.md b/chapter29/docs/deferred-construction.md index ff0a2765..104ab9e9 100644 --- a/chapter29/docs/deferred-construction.md +++ b/chapter29/docs/deferred-construction.md @@ -1,5 +1,10 @@ # 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 diff --git a/chapter29/docs/escape-flow.md b/chapter29/docs/escape-flow.md new file mode 100644 index 00000000..8ad49f15 --- /dev/null +++ b/chapter29/docs/escape-flow.md @@ -0,0 +1,147 @@ +# 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 `` 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. 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 ba7c0c1d..b4c93e1e 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -96,80 +96,11 @@ public class CodeGen { return null; } - // Frozen after ParseAll: public initializers and function-valued fields. - public boolean publicFIDX(int fidx) { - return fidx >= GlobalBits.RESERVED && XInt.bit(publicFIDXs(),fidx); - } - - private void gatherPublicFields(TypeStruct clz, boolean classFields) { - for( Field fld : clz._fields ) { - // Private-memory helpers are reached through their allocator. - if( fld._fname.charAt(0)=='_' || fld._t==Type.TOP || - clz.hiddenInit(fld) ) continue; - if( classFields ) _publicAliases = XInt.make(_publicAliases,fld._alias); - if( fld._t instanceof TypeFunPtr tfp ) - _publicFIDXs = XInt.meet(_publicFIDXs,tfp._fidxs); - } - } - public static boolean hasUserConstructor(TypeStruct self) { Type t = Parser.TYPES.get(TypeStruct.addClzPrefix(self._name)); return t instanceof TypeStruct clz && clz.field("") != null; } - // A forward reference has a placeholder class, not a definition yet. - private static boolean resolvedClass(TypeStruct clz) { - Type t = Parser.TYPES.get(clz._name.substring(TypeStruct.CLZ.length())); - return !(t instanceof TypeStruct ts) || !ts._fref; - } - - private int[] _publicFIDXs, _publicAliases; - private TypeMem _publicEscapes; - - /** - * 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; - _publicFIDXs = _publicAliases = XInt.EMPTY; - for( Type t : Parser.TYPES.values() ) - if( t instanceof TypeStruct clz && - TypeStruct.startsClzPrefix(clz._name) && - TypeStruct.isPublicClassName(clz._name) && - resolvedClass(clz) ) { - // Gather function pointers from public fields of both class - // and instance objects. - gatherPublicFields(clz,true); - Type self = Parser.TYPES.get(clz._name.substring(TypeStruct.CLZ.length())); - if( self instanceof TypeStruct ts ) gatherPublicFields(ts,false); - } - // Limit broad function types to known FIDXs, excluding reserved bits. - // Public class initializers are roots without needing a field reference. - int[] fidxs = XInt.EMPTY; - for( int fidx = GlobalBits.RESERVED; fidx<_linker._len; fidx++ ) { - FunNode fun = _linker.atX(fidx); - if( XInt.bit(_publicFIDXs,fidx) || (fun!=null && fun.isClz() && fun.isPublic()) ) - 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()>>5)+2); + Arrays.fill(foreign,1,foreign.length,-1); + for( int i = 0; i<_local; i++ ) { + String owner = _local2Clz.at(i); + if( owner==null || !owner.startsWith("C:") ) + foreign[(i>>>5)+1] &= ~(1< oldTypes = new Ary<>(Type.class); WorkList deps = new WorkList<>(); @@ -158,11 +161,9 @@ abstract public class Opto { private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { if( tfp.nargs() != call.nargs() ) return; // Error calls hit this int[] fidxs = tfp.fidxs(); - // An unresolved forward call can still carry the infinite, inferred - // function set into Opto. There is no finite call graph to link yet; - // type checking will report the unresolved reference afterwards. This - // can yet be valid if the call is eventually dead. - // `if( false ) frefCall(args);` + // An infinite target set uses the outside continuation. Escaped local + // callbacks are called through Start; their effects feed that same + // outside state. Do not attach unrelated same-arity function bodies. if( XInt.isHigh(fidxs) ) return; for( int fidx = XInt.next(fidxs,0); fidx >=0; fidx = XInt.next(fidxs,fidx) ) { // unlinkStart deliberately leaves uncalled functions in a @@ -185,10 +186,10 @@ abstract public class Opto { TypeMem tmem = (TypeMem)tt._types[1]; int[] fidxs = tmem._escFs; if( XInt.isHigh(fidxs) ) { - // Unknown values can later refine to private callbacks too. - // FULL must cover every live target, just like the finite case. + // A cofinite set includes foreign identities but can exclude local + // functions. Honor those exclusions just as in the finite case. for( FunNode fun : code._linker ) - if( fun != null && !fun.isDead() ) + if( fun != null && !fun.isDead() && XInt.bit(fidxs,fun.sig().fidx()) ) linkStart(code,fun); return; } @@ -200,7 +201,8 @@ abstract public class Opto { } // Function is now reachable by unknown callers through Start. The - // default inputs must therefore use conservative declared types. + // Memory and callback defaults read Start's changing outside state. + // Scalar defaults remain constants; hidden self uses the owning class. static void linkStart( CodeGen code, FunNode fun ) { assert !fun.isDead(); StartCUNode start = fun._compunit._start; @@ -212,7 +214,9 @@ abstract public class Opto { code._iter.add(fun); for( Node p : fun._outputs ) if( p instanceof ParmNode parm ) { - Node defalt = parm._idx==1 ? start.proj(1) : ConstantNode.seed(parm._declaredType).peephole(); + Type t = parm._idx<2 ? parm._declaredType : fun.defaultArg(parm._idx-2); + Node defalt = parm._idx==1 || parm._declaredType instanceof TypeFunPtr + ? start.proj(1) : ConstantNode.seed(t).peephole(); parm.insertDef(1,defalt); code.add(parm); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index b77b224c..5f8a0ec0 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -118,11 +118,6 @@ public abstract class ParseAll { for( CompUnit cu : code._compunits.values() ) if( cu._ext==null ) cu._clz = (TypeStruct)Parser.TYPES.get(TypeStruct.addClzPrefix(cu._cname)); - - // The complete public interface is now known. Keep this independent - // of later graph/linker liveness so SCCP computations remain local and - // monotonic. - code.freezePublicInterface(); } // Parse one Simple source code file. Add all the FRefs produced to the worklist. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/CLInitNode.java index f8c1c925..fb762ff3 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -84,10 +84,20 @@ public class CLInitNode extends CFGNode implements MultiNode { return TypeTuple.make(in(0)._type,mem()._type,mem()._type,Type.XCONTROL); Field flag = flag(); Type slice = flag==null ? TypeMem.BOT : TypeMem.make(flag._alias,TypeInteger.TRUE); - // The initializer may write arbitrary public memory. Only its flag - // has a guaranteed value on the normal continuation. - Type bulk = ready()._type.isHigh() ? TypeMem.TOP : + // Before Opto, the initializer has conservative effects. Once linked, + // its Return supplies them through the ordinary dependency worklist. + // Meet with incoming memory for the path that was already initialized. + Type bulk = ready()._type.isHigh() || mem()._type.isHigh() ? TypeMem.TOP : ready()._type==TypeInteger.TRUE ? mem()._type : TypeMem.BOT; + if( bulk==TypeMem.BOT && ready()._type!=TypeInteger.TRUE && + CodeGen.CODE._phase.ordinal()>=CodeGen.Phase.Opto.ordinal() ) { + FunNode target = CodeGen.CODE.link(cu()); + if( target!=null && target.ret()!=null ) { + Type result = addDepForwards(target.ret())._type; + Type effects = result instanceof TypeTuple tt ? tt.mem() : result.isHigh() ? TypeMem.TOP : TypeMem.BOT; + bulk = mem()._type.meet(effects); + } + } Type call = ready()._type.isHigh() || ready()._type==TypeInteger.TRUE ? Type.XCONTROL : in(0)._type; return TypeTuple.make(in(0)._type,bulk,slice,call); } @@ -181,6 +191,10 @@ public class CLInitNode extends CFGNode implements MultiNode { // Replace the analysis edge with the ordinary call. Its arguments // are the same ones already analyzed before lowering. call.link(target); + // Publish the linked effects before projections can feed callers. + // The unlinked CallEnd's pessimistic seed is not the replacement for + // the precise initializer effects already analyzed above. + end.setType(end.compute()); unlink(); Node called = CodeGen.CODE.add(new CProjNode(end,0,ScopeNode.CTRL).init()); Node after = CodeGen.CODE.add(new ProjNode(end,1,ScopeNode.MEM0).init()); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 4056e24e..b5156c2d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -86,9 +86,15 @@ public class CallEndNode extends CFGNode implements MultiNode { // Mid-fold, just take the inlined callee's return. if( _folding ) return in(1)._type; - // Unknown targets can change any memory and return the declared type. - if( XInt.isHigh(tfp.fidxs()) ) - return TypeTuple.make(Type.CONTROL,TypeMem.BOT,tfp.ret()); + // The outside continuation reads Start directly: Call can remain + // CONTROL while its possible returned identities change. + if( XInt.isHigh(tfp.fidxs()) ) { + TypeMem outside = CodeGen.CODE._start.outside(this).escapes(call.exposed(this)); + TypeTuple state = TypeTuple.make(Type.CONTROL,outside,outside.outside(tfp.ret())); + for( int i = 1; i