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 --- .../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 +++--- 24 files changed, 243 insertions(+), 201 deletions(-) (limited to 'chapter28b/src/main') 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