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 --- chapter28b/README.md | 8 ++ .../main/java/com/seaofnodes/simple/Parser.java | 9 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 62 ------------ .../com/seaofnodes/simple/codegen/GlobalBits.java | 13 +++ .../java/com/seaofnodes/simple/codegen/Iter.java | 3 +- .../java/com/seaofnodes/simple/codegen/Opto.java | 38 +++---- .../com/seaofnodes/simple/codegen/ParseAll.java | 4 - .../com/seaofnodes/simple/node/CLInitNode.java | 27 ++++- .../com/seaofnodes/simple/node/CallEndNode.java | 15 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 20 +--- .../com/seaofnodes/simple/node/ConvertNode.java | 7 +- .../com/seaofnodes/simple/node/EscapeNode.java | 8 +- .../java/com/seaofnodes/simple/node/FunNode.java | 11 ++ .../seaofnodes/simple/node/GlobalEscapeNode.java | 11 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 67 ++++++++++-- .../java/com/seaofnodes/simple/node/ParmNode.java | 12 ++- .../java/com/seaofnodes/simple/node/StartNode.java | 13 +++ .../com/seaofnodes/simple/node/StopCUNode.java | 52 ++-------- .../java/com/seaofnodes/simple/node/StoreNode.java | 9 +- .../com/seaofnodes/simple/node/SummaryNode.java | 6 +- .../main/java/com/seaofnodes/simple/type/Type.java | 5 +- .../com/seaofnodes/simple/type/TypeFunPtr.java | 4 + .../java/com/seaofnodes/simple/type/TypeMem.java | 19 ++++ .../com/seaofnodes/simple/type/TypeStruct.java | 12 +-- .../main/java/com/seaofnodes/simple/type/XInt.java | 17 ++-- .../java/com/seaofnodes/simple/Chapter10Test.java | 20 ++-- .../java/com/seaofnodes/simple/Chapter12Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter18Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 22 ++-- .../java/com/seaofnodes/simple/Chapter21Test.java | 38 +++---- .../java/com/seaofnodes/simple/Chapter25Test.java | 65 +++++++++--- .../simple/ClassInitDependenciesTest.java | 22 ++++ .../java/com/seaofnodes/simple/EscapeFlowTest.java | 112 +++++++++++++++++++++ 34 files changed, 477 insertions(+), 260 deletions(-) create mode 100644 chapter28b/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java (limited to 'chapter28b') diff --git a/chapter28b/README.md b/chapter28b/README.md index ce219cc7..d581d868 100644 --- a/chapter28b/README.md +++ b/chapter28b/README.md @@ -114,6 +114,14 @@ compilation indices; this remapping extends everywhere through the loaded code, including recursive types that span several files. Importing skips parsing the original source, but loaded IR is still analyzed within its new context. +The outside escape state includes foreign identities as a cofinite set: +all identities except a finite set of local exclusions. Serialization remaps +those exclusions by owner and slot, then restores the complement. Treating +this set as FULL would expose private library functions. Unknown callback +arguments, results, and unloaded summaries use the evolving Start/Stop state; +no frozen public-function list supplies their bounds. Hidden class receivers +default to the defining class singleton even after import. + `ParseAll` is the workhorse that discovers source and object dependencies. It tracks missing symbol references, looking them up in the search path one by one, and loading the matching files. diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/Parser.java b/chapter28b/src/main/java/com/seaofnodes/simple/Parser.java index 83bef882..cef7091a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/Parser.java @@ -292,7 +292,7 @@ public class Parser { for( int i=0; i",alloc,_code.alias(_ref._cname),true)); TYPES.put(clzName,ts); // Insert a field in the containing class with the nested class type. - // This is basically sugar for "val CLZNAME = " + // This is basically sugar for "val CLZNAME = " // and is a nicer version of updateSelfAsFieldsDiscovered. - _scope.define(typeName, sig, true, new FunPtrNode(sig,_code._start,ret).peephole(), loc()); + _scope.define(typeName, sig, true, new FunPtrNode(sig,_code._start,_code.link(alloc).ret()).peephole(), loc()); require("}"); return require(_code.ZERO,";"); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 67176710..998989b1 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -97,73 +97,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) { - boolean hasCtor = clz.field("") != null; - for( Field fld : clz._fields ) { - // With a user constructor, class:N.N is the private . - if( fld._fname.charAt(0)=='_' || fld._t==Type.TOP || - (hasCtor && 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(Parser.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(Parser.CLZ.length())); - return !(t instanceof TypeStruct ts) || !ts._fref; - } - - private int[] _publicFIDXs, _publicAliases; - - /** - * 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". - */ - void freezePublicInterface() { - assert _publicFIDXs==null && _publicAliases==null; - _publicFIDXs = _publicAliases = XInt.EMPTY; - for( Type t : Parser.TYPES.values() ) - if( t instanceof TypeStruct clz && - Parser.startsClzPrefix(clz._name) && - Parser.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(Parser.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; - } - - public int[] publicFIDXs() { assert _publicFIDXs !=null; return _publicFIDXs; } - public int[] publicAliases(){ assert _publicAliases!=null; return _publicAliases; } - public boolean publicInterfaceFrozen() { return _publicFIDXs != null; } - // --------------------------- // Very common nodes, cached here diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java index bc9c9d39..acd2eee5 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.util.*; +import com.seaofnodes.simple.type.XInt; import java.util.HashMap; import java.util.Arrays; import java.util.Objects; @@ -28,6 +29,18 @@ public class GlobalBits { // Local dense index private int _local; + // Identities not owned by this compilation. Reserved bits are not foreign. + public int[] foreign() { + int[] foreign = XInt.alloc((_local>>>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<>(); 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,18 +54,22 @@ abstract public class Opto { // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. moveChangesToWorklist(code, oldTypes, changes); + 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 ) { + private static void resetToTop(CodeGen code, Ary oldTypes, Ary modes, WorkList deps, Ary returns ) { code._start.walk( x -> { + // Keep bodies alive while SCCP rebuilds their callers. + 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); // 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 + // Change snapshot, not a bound: Opto adds foreign identities. + oldTypes.setX(x._nid,x._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; @@ -90,8 +98,7 @@ 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); + stop.delDef(i--); } // Unlink the existing conservative call linkages. for( int j=1; j=0; fidx = XInt.next(fidxs,fidx) ) { // unlinkStart deliberately leaves uncalled functions in a @@ -133,10 +137,9 @@ abstract public class Opto { TypeMem tmem = (TypeMem)tt._types[1]; int[] fidxs = tmem._escFs; if( XInt.isHigh(fidxs) ) { - // A scalar BOTTOM can flow into memory while compiling an error - // program. It exposes all public functions, not private fields. + // Cofinite sets include foreign identities but can exclude locals. for( FunNode fun : code._linker ) - if( fun != null && code.publicFIDX(fun.sig().fidx()) ) + if( fun != null && !fun.isDead() && XInt.bit(fidxs,fun.sig().fidx()) ) linkStart(code,fun); return; } @@ -148,7 +151,7 @@ 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 inputs read Start; hidden self uses its owning class. static void linkStart( CodeGen code, FunNode fun ) { assert !fun.isDead(); StartCUNode start = fun._compunit._start; @@ -160,7 +163,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); } @@ -184,8 +189,6 @@ abstract public class Opto { if( nval!=oldTypes.atX(n._nid) || n.isUnlocked() ) changes.push(n); if( oval == nval ) continue; assert oval.isa(nval) : "Non-monotonic SCCP: "+n.getClass().getSimpleName()+"#"+n._nid+" "+n+" old="+oval+" new="+nval; // Types start high and always fall - Type pesiVal = oldTypes.atX(n._nid); - assert pesiVal==null || nval.isa(pesiVal) : "SCCP below pessimistic type: "+n.getClass().getSimpleName()+"#"+n._nid+" "+n+" pessimistic="+pesiVal+" new="+nval; // Never fall worse than the pessimistic pass n._type = nval; // Now we have a series of stanzas where we lazily create the Call @@ -267,7 +270,6 @@ abstract public class Opto { if( n.isDead() ) continue; assert n.compute() == n._type; // Hit the fixed point. Type old = oldTypes.atX(n._nid); - assert old==null || n._type.isa(old); if( n._type!=old || n.isUnlocked() ) { code.addAll(n); code.addAll(n._outputs); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 1d9731fc..a6b996f7 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -162,10 +162,6 @@ public abstract class ParseAll { 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.freezePublicInterface(); } // Parse one Simple source code file. Add all the FRefs produced to the worklist. diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java index f7b48fbe..270c0521 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; +import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.CompUnit; import com.seaofnodes.simple.codegen.Iter; @@ -75,16 +75,29 @@ public class CLInitNode extends CFGNode implements MultiNode { public boolean bypass() { return instance() || ready()._type==TypeInteger.TRUE; } @Override public Type compute() { - if( in(0)._type.isHigh() || ptr()._type.isHigh() ) + // The pointer family can be known before its object shape during + // SCCP. Do not commit to a class flag before it can become an instance. + if( in(0)._type.isHigh() || ptr()._type.isHigh() || + (ptr()._type instanceof TypeMemPtr tmp && tmp._obj.isHigh()) ) return TypeTuple.make(Type.XCONTROL,TypeMem.TOP,TypeMem.TOP,Type.XCONTROL); if( instance() ) 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); } @@ -178,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/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index b7b26265..2ce2e4d5 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter28b/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=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) { @@ -111,7 +95,9 @@ public class CallNode extends CFGNode { if( !external() ) return TypeMem.START; Type input = dep.addDepForwards(mem())._type; TypeMem escaped = input instanceof TypeMem m ? m : input.isHigh() ? TypeMem.TOP : TypeMem.BOT; - for( int i = 2; i