diff options
| author | Cliff Click <cliffc@acm.org> | 2026-11-06 16:06:02 -0800 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-11-06 16:06:02 -0800 |
| commit | ce3b04603d7af995004291d9a7eb668f313e6772 (patch) | |
| tree | 45d3b45026c54e0a35aa3bd37069c7cccb0729bf | |
| parent | 8f460340cfe01a4945635251bcd33b257b699bf7 (diff) | |
| download | Simple-ce3b04603d7af995004291d9a7eb668f313e6772.tar.gz Simple-ce3b04603d7af995004291d9a7eb668f313e6772.zip | |
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
100 files changed, 1691 insertions, 719 deletions
diff --git a/chapter26/src/main/java/com/seaofnodes/simple/type/XInt.java b/chapter26/src/main/java/com/seaofnodes/simple/type/XInt.java index 17fc4bd3..a69783be 100644 --- a/chapter26/src/main/java/com/seaofnodes/simple/type/XInt.java +++ b/chapter26/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -92,7 +92,7 @@ public abstract class XInt { int len = Math.max(xs.length,idx+1); if( (x&31)==31 && idx+1==len ) len++; - int[] ys = free(len); + int[] ys = alloc(len); System.arraycopy(xs,1,ys,1,xs.length-1); ys[idx] |= mask(x); return intern(ys); @@ -112,7 +112,7 @@ public abstract class XInt { len--; // Replace with trimmed if( len < xs.length ) { - var ys = free(len); + var ys = alloc(len); System.arraycopy(xs,1,ys,1,len-1); xs = _free(xs,ys); } @@ -146,8 +146,9 @@ public abstract class XInt { FREES.setX(len, xss = new Ary<>(int[].class)); return xss; } - // Pull free array from free list - static int[] free(int len) { + // Allocate a zeroed mutable array, reusing the free list. + // Pass it to intern after filling; do not retain a mutable reference. + public static int[] alloc(int len) { int[] xs = _xss(len).pop(); if( xs==null ) { NEWS++; xs = new int[len]; } @@ -176,7 +177,7 @@ public abstract class XInt { if( isX ) return xs; if( isY ) return ys; // Get a free one - int[] ms = free(max); + int[] ms = alloc(max); for( int i=1; i<min; i++ ) ms[i] = xs[i] | ys[i]; for( int i=min; i<ms.length; i++ ) { @@ -189,7 +190,7 @@ public abstract class XInt { // Dual: flip all the bits public static int[] dual(int[] xs) { - int[] ds = free(xs.length); + int[] ds = alloc(xs.length); for( int i=1; i<xs.length; i++ ) ds[i] = ~xs[i]; return intern(ds); diff --git a/chapter27/src/main/java/com/seaofnodes/simple/type/XInt.java b/chapter27/src/main/java/com/seaofnodes/simple/type/XInt.java index 17fc4bd3..a69783be 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/type/XInt.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -92,7 +92,7 @@ public abstract class XInt { int len = Math.max(xs.length,idx+1); if( (x&31)==31 && idx+1==len ) len++; - int[] ys = free(len); + int[] ys = alloc(len); System.arraycopy(xs,1,ys,1,xs.length-1); ys[idx] |= mask(x); return intern(ys); @@ -112,7 +112,7 @@ public abstract class XInt { len--; // Replace with trimmed if( len < xs.length ) { - var ys = free(len); + var ys = alloc(len); System.arraycopy(xs,1,ys,1,len-1); xs = _free(xs,ys); } @@ -146,8 +146,9 @@ public abstract class XInt { FREES.setX(len, xss = new Ary<>(int[].class)); return xss; } - // Pull free array from free list - static int[] free(int len) { + // Allocate a zeroed mutable array, reusing the free list. + // Pass it to intern after filling; do not retain a mutable reference. + public static int[] alloc(int len) { int[] xs = _xss(len).pop(); if( xs==null ) { NEWS++; xs = new int[len]; } @@ -176,7 +177,7 @@ public abstract class XInt { if( isX ) return xs; if( isY ) return ys; // Get a free one - int[] ms = free(max); + int[] ms = alloc(max); for( int i=1; i<min; i++ ) ms[i] = xs[i] | ys[i]; for( int i=min; i<ms.length; i++ ) { @@ -189,7 +190,7 @@ public abstract class XInt { // Dual: flip all the bits public static int[] dual(int[] xs) { - int[] ds = free(xs.length); + int[] ds = alloc(xs.length); for( int i=1; i<xs.length; i++ ) ds[i] = ~xs[i]; return intern(ds); diff --git a/chapter28a/README.md b/chapter28a/README.md index d46a24d7..3dec4c4f 100644 --- a/chapter28a/README.md +++ b/chapter28a/README.md @@ -145,8 +145,8 @@ that private fields are visible only inside their declaring class, not to siblings or parents. A private enclosing class also keeps its children out of the public interface. -The current compiler uses these names to choose the public interface and seed -escape analysis, but does not yet enforce the source access rule. For example, +The current compiler uses these names to select public fields and initializer +roots for escape discovery, but does not yet enforce the source access rule. For example, a sibling can currently read `A._secret`. Rejecting that access is still needed; the underscore alone is not an enforced boundary in this snapshot. @@ -236,6 +236,29 @@ sets the flag. Generated calls have conservative memory effects and do not reopen SCCP's analysis of the optimized bodies. +### Escaping or the Start/Stop Cycle + +The semantics of Stop/CU are that execution has left the current compilation, +and proceeded out into the unknown World. The reverse happens at Start/CU: we +enter the known code from the outside World. This endless cycle, Start -> +known code -> Stop -> Start, lets us model escaping local functions and aliases +into the outside, and then seeing them again coming in as callbacks, or +arguments or side-effects. Tracking this exactly lets us know when we have +"escaped" a otherwise private function to the World, which might then call it +directly, or pass it back to us as an argument, or store it for later. + +`LocalIds` tracks foreign identities, excluding the local IDs. Calls and +escaping values add local identities as SCCP converges. Unknown callback +parameters and results read this state. A class function's hidden receiver +defaults to its class singleton, while its signature keeps the generic hidden +slot used by the calling convention. + +Public constructor fields expose the allocator. Initializers and constructor +helpers that accept private memory stay internal. Class-init checks read their +initializer's memory effects, and unknown callbacks participate in class-init +cycle detection through the functions that have escaped. + + ## Emitting code and data After cleanup by `FinishCalls`, the live code and data from the discovered diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/Parser.java b/chapter28a/src/main/java/com/seaofnodes/simple/Parser.java index 6bd02363..3b5a8ce7 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/Parser.java @@ -291,7 +291,7 @@ public class Parser { for( int i=0; i<ids.length; i++ ) { Type t = sig.arg(i); // Args take a default input if called from Start/external-world - _scope.define(ids[i], t, (i==0 && ids[0]=="self") || (finals!=null && finals.get(i)), new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(t).peephole()).peephole(), loc); + _scope.define(ids[i], t, (i==0 && ids[0]=="self") || (finals!=null && finals.get(i)), new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(fun.defaultArg(i)).peephole()).peephole(), loc); } if( isCtor && !isInit ) { @@ -1333,13 +1333,16 @@ public class Parser { : TypeStruct.make(clzName,false,fld,ctorFld); if( flag!=null ) ts=ts.add(flag); TypeFunPtr alloc = makeAllocator((TypeStruct)TYPES.get(fullName),ret,ctorFld); + // Publish the source-callable allocator, not the private-memory helper. + sig = alloc; + ts = ts.replace(fld.makeFrom(alloc)); ts = ts.add(Field.make("<new>",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 = <init>" + // This is basically sugar for "val CLZNAME = <new>" // 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/chapter28a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 6c70b71d..3784b6b8 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -29,6 +29,7 @@ public class ClassInitDependencies { private final int[] _lows; private final int[] _stk ; private int _sp; + private int _pre; // Build once; tests can inspect the graph independently of cycle checking. @@ -50,6 +51,14 @@ public class ClassInitDependencies { if( fun!=null && !fun.isDead() ) // Visit function and collect direct class touches and callees _edgess[fun.sig().fidx()] = walk(code,fun,work,iset,visit,null); + // An unknown callback can call any escaped local function. Zero is + // this outside-world vertex, not an executable function identity. + int[] escaped = ((TypeTuple)code._stop._type).mem()._escFs; + AryInt callees = new AryInt(); + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() && !fun.isClz() && XInt.bit(escaped,fun.sig().fidx()) ) + callees.push(fun.sig().fidx()); + _edgess[0] = callees.isEmpty() ? null : callees.asAry(); visit.clear(); } @@ -84,9 +93,12 @@ public class ClassInitDependencies { // Calls union all their fptr fidxs into the callee set if( cfg instanceof CallNode call && call.fptr()._type instanceof TypeFunPtr fp ) { - assert !XInt.isHigh(fp.fidxs()) && fp.nfcns()>0; // Call is alive with valid targets + if( XInt.isHigh(fp.fidxs()) ) { + iset.put(0,1); + if( sites!=null && sites.atX(0)==null ) sites.setX(0,call._loc); + } // Union call targets into the callee set - for( int dstx = XInt.next(fp.fidxs(),0); dstx>=0; dstx=XInt.next(fp.fidxs(),dstx) ) { + else for( int dstx = XInt.next(fp.fidxs(),0); dstx>=0; dstx=XInt.next(fp.fidxs(),dstx) ) { iset.put(dstx,1); if( sites!=null && sites.atX(dstx)==null ) sites.setX(dstx,call._loc); } @@ -113,10 +125,10 @@ public class ClassInitDependencies { public String check() { Arrays.fill(_pres,0); _sp = 0; - _pres[0] = 1; // Preorders stored in pres[0] and start at 1 + _pre = 1; int idx = -1; - for( int fidx = 1; fidx < _edgess.length; fidx++ ) + for( int fidx = 0; fidx < _edgess.length; fidx++ ) if( _pres[fidx] == 0 && // Already visited (idx = scc(fidx)) != -1 ) // And found a cycle return report(idx); // Report cycle @@ -143,7 +155,7 @@ public class ClassInitDependencies { FunNode fun = _code.link(src); Arrays.fill(sites._es,null); sites.clear(); - walk(_code,fun,work,iset,visit,sites); + if( fun!=null ) walk(_code,fun,work,iset,visit,sites); if( _edgess[src]!=null ) for( int dst : _edgess[src] ) if( members.get(dst) ) { @@ -151,7 +163,7 @@ public class ClassInitDependencies { Parser.Lexer loc = sites.atX(dst); if( loc!=null && loc._cu!=null ) sb.p('\n').p(SourceError.format(loc._cu,loc.pos(),"cyclic class initialization")); - else if( fun.isClz() && fun._compunit._par==_code.link(dst)._compunit ) + else if( fun!=null && fun.isClz() && dst!=0 && fun._compunit._par==_code.link(dst)._compunit ) sb.p("\n parent initialization requirement"); } } @@ -159,6 +171,7 @@ public class ClassInitDependencies { } private String name(int fidx) { + if( fidx==0 ) return "unknown call"; FunNode fun = _code.link(fidx); String owner=fun._compunit._cname; if( fun.isClz() ) return owner; @@ -169,7 +182,7 @@ public class ClassInitDependencies { // Tarjan SCC int scc( int fidx ) { // Assign pre-order number - _lows[fidx] = _pres[fidx] = _pres[0]++; + _lows[fidx] = _pres[fidx] = _pre++; _stk[_sp++] = fidx; // walk outbound edges if( _edgess[fidx]!=null ) { diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 8b3857a1..a3de2ec8 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -86,85 +86,11 @@ public class CodeGen { return null; } - // True when fidx is published through a public class or instance field. - public boolean publicFIDX(int fidx) { - if( fidx < LocalIds.RESERVED ) return false; - // A public class initializer is itself an external root; unlike - // constructors and methods, it is not reached through a class field. - FunNode fun = _linker.atX(fidx); - if( fun != null && fun.isClz() && fun.isPublic() ) - return true; - // Include instance methods even while their constant function fields - // are stored in each instance rather than on the class object. - for( Type t : Parser.TYPES.values() ) - if( t instanceof TypeStruct clz && - Parser.startsClzPrefix(clz._name) && - Parser.isPublicClassName(clz._name) && - resolvedClass(clz) ) { - if( publicFieldFIDX(clz,fidx) ) return true; - Type self = Parser.TYPES.get(clz._name.substring(Parser.CLZ.length())); - if( self instanceof TypeStruct ts && publicFieldFIDX(ts,fidx) ) return true; - } - return false; - } - - private static boolean publicFieldFIDX(TypeStruct clz, int fidx) { - boolean hasCtor = clz.field("<ctor>") != null; - for( Field fld : clz._fields ) - if( fld._fname.charAt(0)!='_' && fld._t instanceof TypeFunPtr tfp && - // With a user constructor, class:N.N is the private <init>. - !(hasCtor && clz.hiddenInit(fld)) && - XInt.bit(tfp._fidxs,fidx) ) - return true; - return false; - } - public static boolean hasUserConstructor(TypeStruct self) { Type t = Parser.TYPES.get(Parser.addClzPrefix(self._name)); return t instanceof TypeStruct clz && clz.field("<ctor>") != null; } - // A forward reference gets a class object and constructor signature so - // parsing can proceed, but it has no callable 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; - - /** - * Freeze the externally visible portion of the program after ParseAll has - * loaded every compilation unit and closed/upgraded all types. Later - * optimization can remove linker entries and create inline-only fidxs; - * neither operation changes this interface. - */ - void freezePublicInterface() { - assert _publicFIDXs==null && _publicAliases==null; - int[] fidxs = XInt.EMPTY; - for( int fidx=LocalIds.RESERVED; fidx<_linker._len; fidx++ ) - if( publicFIDX(fidx) ) - fidxs = XInt.make(fidxs,fidx); - int[] aliases = XInt.EMPTY; - for( Type t : Parser.TYPES.values() ) - if( t instanceof TypeStruct clz && - Parser.startsClzPrefix(clz._name) && - Parser.isPublicClassName(clz._name) && - resolvedClass(clz) ) { - boolean hasCtor = clz.field("<ctor>") != null; - for( Field fld : clz._fields ) - if( fld._fname.charAt(0)!='_' && fld._t!=Type.TOP && - !(hasCtor && clz.hiddenInit(fld)) ) - aliases = XInt.make(aliases,fld._alias); - } - _publicFIDXs = fidxs; - _publicAliases = aliases; - } - - 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/chapter28a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java index 462248dd..29157631 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.type.XInt; import java.util.HashMap; import java.util.Arrays; @@ -11,6 +12,19 @@ public class LocalIds { private final com.seaofnodes.simple.util.Ary<String> _owners=new com.seaofnodes.simple.util.Ary<>(String.class); private final HashMap<String,int[]> _slots=new HashMap<>(); + // All registered Simple identities are local; native storage and the + // unallocated tail belong to the outside world. Reserved IDs are excluded. + public int[] foreign() { + int[] foreign = XInt.alloc((_next>>>5)+2); + Arrays.fill(foreign,1,foreign.length,-1); + for( int i = 0; i<_next; i++ ) { + String owner = _owners.atX(i); + if( owner==null || !owner.startsWith("C:") ) + foreign[(i>>>5)+1] &= ~(1<<i); + } + return XInt.intern(foreign); + } + public int next(String owner) { return next(owner,-1); } public int next(String owner, int slot) { int[] ids=_slots.get(owner); diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 6370bf5b..e1282883 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -25,12 +25,16 @@ abstract public class Opto { // get a fairly precise set of Call Graph edges between CallNodes and // FunNodes. public static void opto(CodeGen code) { + int[] foreign = code._fidxs.foreign(); + for( int fidx : code._externFunc.keySet() ) foreign = XInt.make(foreign,fidx); + code._start._foreign = TypeMem.START.makeFrom(foreign,code._aliases.foreign()); // Reset Types before running the worklist algorithm Ary<Type> oldTypes = new Ary<>(Type.class); WorkList<Node> deps = new WorkList<>(); WorkList<Node> changes = new WorkList<>(); Ary<Node> modes = new Ary<>(Node.class); - resetToTop(code,oldTypes,modes,deps); + Ary<ReturnNode> returns = new Ary<>(ReturnNode.class); + resetToTop(code,oldTypes,modes,deps,returns); unlinkStart(code); // OPTIMISTIC INTERPROCEDURAL SCCP @@ -48,17 +52,21 @@ abstract public class Opto { Node dep; while( (dep=deps.pop())!=null ) code.add(dep); 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<Type> oldTypes, Ary<Node> modes, WorkList<Node> deps ) { + private static void resetToTop(CodeGen code, Ary<Type> oldTypes, Ary<Node> modes, WorkList<Node> deps, Ary<ReturnNode> 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. 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; @@ -66,9 +74,8 @@ abstract public class Opto { } - // If wholeWorld, remove the Start inputs to functions - they are not - // called unless they get linked (hence go dead and can be removed). If - // not wholeWorld, keep only public methods (and not the std lib). + // Rediscover ordinary functions through calls and escapes. This chapter + // retains initializer entries until opaque CLInit obligations are lowered. private static void unlinkStart(CodeGen code) { // Keep the Start & Start.ProjMem alive even as we remove all uses for( CompUnit cu : code._compunits.values() ) { @@ -81,20 +88,17 @@ abstract public class Opto { for( int i=0; i<stop.nIns(); i++ ) { ReturnNode ret = (ReturnNode)stop.in(i); FunNode fun = ret.fun(); - // Start is a semantic unknown-caller edge. Public functions - // keep it; closed-world functions must be reached by a - // concrete Call edge discovered during SCCP. Initializers, + // Start is a semantic unknown-caller edge. Ordinary functions + // are discovered through calls and escaped values. Initializers, // including private ones, are called by opaque CLInit // obligations whose Call edges are introduced only in Lower. if( !fun.isClz() && - !code.publicFIDX(fun.sig().fidx()) && fun.in(1) instanceof StartNode ) { fun.removeDeadPath(1); // 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<fun.nIns(); j++ ) @@ -109,11 +113,8 @@ 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);` + // Infinite targets use the outside continuation. Escaped local + // callbacks are reached through Start, and their effects feed Stop. 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 @@ -136,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; } @@ -151,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. private static void linkStart( CodeGen code, FunNode fun ) { assert !fun.isDead(); StartCUNode start = fun._compunit._start; @@ -163,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); } @@ -185,8 +187,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 +267,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.add(n); code.addAll(n._inputs); diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 6ae4e4bb..58983663 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -138,10 +138,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/chapter28a/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/CLInitNode.java index 0a0de3cf..0482484a 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -67,16 +67,27 @@ 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() ) + 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); if( instance() ) return TypeTuple.make(in(0)._type,mem()._type,mem()._type); 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); + } + } return TypeTuple.make(in(0)._type,bulk,slice); } @@ -132,9 +143,10 @@ public class CLInitNode extends CFGNode implements MultiNode { Node fptr = new FunPtrNode(target.sig(),CodeGen.CODE._start,target.ret()).peephole(); CallNode call = CodeGen.CODE.add(new CallNode(_loc,cold,memory,ptr(),arg,fptr).init()); CallEndNode end = new CallEndNode(call,TypeRPC.constant(CodeGen.CODE.rpc(_loc._cu._cname))); - // This is a lowered call, after interprocedural analysis. Do not add - // new parameter flows to a body already optimized by SCCP. CodeGen.CODE.add(end.init()); + call.link(target); + // Publish the linked effects before constructing memory projections. + end.setType(end.compute()); Node called = CodeGen.CODE.add(new CProjNode(end,0,ScopeNode.CTRL).init()); Node after = CodeGen.CODE.add(new ProjNode(end,1,ScopeNode.MEM0).init()); RegionNode region = CodeGen.CODE.add(new RegionNode(_loc,null,done,called).init()); diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 4422265f..3be22c09 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -73,6 +73,16 @@ public class CallEndNode extends CFGNode implements MultiNode { return tt.makeFrom(2,tt.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<nIns(); i++ ) + state = (TypeTuple)state.meet(in(i)._type); + return state; + } + // Here, if I can figure out I've linked *all* callers, then I can meet // across the linked returns and join with the function return type. @@ -93,7 +103,11 @@ public class CallEndNode extends CFGNode implements MultiNode { bound = bound.meet(fun==null ? tfp.ret() : addDep(fun).sig().ret()); } } - boolean hasExtern = externs != 0; + if( externs!=0 ) { + assert externs==tfp.nfcns(); + TypeMem outside = CodeGen.CODE._start.outside(this).escapes(call.exposed(this)); + return TypeTuple.make(Type.CONTROL,outside,outside.outside(tfp.ret())); + } // If we have an error-call, e.g. wrong args, then we never link. // Pre-Opto this looks like a missing target fcn, and we assume it will @@ -111,9 +125,7 @@ public class CallEndNode extends CFGNode implements MultiNode { } // A linked function for every concrete function - TypeTuple state = hasExtern - ? TypeTuple.make(Type.CONTROL,call.exposed(this),tfp.ret()) - : TypeTuple.STATE.dual(); + TypeTuple state = TypeTuple.STATE.dual(); for( int i=1; i<nIns(); i++ ) state = (TypeTuple)state.meet(in(i)._type); // A reachable call whose presently linked exits are all unreachable diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/CallNode.java index f791225a..1a8da215 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -69,10 +69,18 @@ public class CallNode extends CFGNode { TypeMem exposed(Node dep) { dep.addDepForwards(this); dep.addDepForwards(fptr()); - if( _type!=Type.CONTROL || !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<nIns()-1; i++ ) escaped=escaped.escapes(dep.addDepForwards(arg(i))._type); + if( _type.isHigh() ) return TypeMem.START; + // A broad scalar target can refine to a function pointer during Iter. + // It cannot yet promise that the call exposes nothing. + if( _type!=Type.CONTROL ) return TypeMem.BOT; + if( !(fptr()._type instanceof TypeFunPtr) ) + return fptr()._type.isHigh() ? TypeMem.START : TypeMem.BOT; + if( !external() ) return TypeMem.START; + Type input = dep.addDepForwards(mem())._type; + TypeMem escaped = input instanceof TypeMem m ? m : input.isHigh() ? TypeMem.TOP : TypeMem.BOT; + TypeMem outside = CodeGen.CODE._start.outside(dep); + for( int i = 2; i<nIns()-1; i++ ) + escaped = escaped.escapesFrom(dep.addDepForwards(arg(i))._type,outside); return TypeMem.make(1,Type.BOTTOM,false,false,false,escaped._escFs,escaped._escAs); } diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index 078c50ec..f5803fe7 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -36,7 +36,12 @@ public class ConvertNode extends Node { @Override public Type compute() { Type src = val()._type; if( src.isHigh() ) return Type.TOP; - if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; + if( _dst instanceof TypeMemPtr ptr ) { + // Keep non-nullness before the identity rewrite; shape and access + // still follow the declaration so compute stays monotone. + return src instanceof TypeMemPtr actual && actual.notNull() ? ptr.nonZero() : ptr; + } + if( src.isa(_dst) ) return src; return _dst; } diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index f7518184..9561eba8 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; @@ -68,7 +69,12 @@ public class EscapeNode extends TypeNode { Type t = tpriv.meet(tpub).join(fld._t); int[] fidxes = XInt.meet(mpriv._escFs, mpub._escFs); int[] aliases = XInt.meet(mpriv._escAs, mpub._escAs); - return TypeMem.make(fld._alias, t, false, false, fld._final, fidxes, aliases).escapesFrom(t); + // Keep escapes from the actual private value before narrowing it to + // the declaration. Selecting its Store from a MemMerge must preserve + // this result, including Scalar.BOT's unknown pointer escapes. + TypeMem defaults = CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ? TypeMem.BOT : mpub; + return TypeMem.make(fld._alias, t, false, false, fld._final, fidxes, aliases) + .escapesFrom(tpriv,defaults).escapesFrom(t,defaults); } @Override public Node idealize() { diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/FunNode.java index 15626a07..c5954f23 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -71,6 +71,17 @@ public class FunNode extends RegionNode { // Signature can improve over time public TypeFunPtr sig() { return _sig; } + // A class function's hidden receiver defaults to its owning singleton. + // Keep PTR in the signature: it marks the hidden ABI slot and permits + // uniform call syntax, including callbacks forwarded by another class. + public Type defaultArg(int idx) { + Type t = sig().arg(idx); + if( idx!=0 || t!=TypePtr.PTR ) return t; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(_compunit._cname)); + assert clz!=null; + return TypeMemPtr.make((byte)2,clz,true); + } + public void setSig( TypeFunPtr sig ) { assert sig.isa(_sig) || resolvesForwardSelf(sig,_sig); if( _sig != sig ) { diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/LoadNode.java index e1a495ad..14ac8c37 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -87,6 +87,14 @@ public class LoadNode extends MemOpNode { if( mem._alias==_alias ) t = t.join(mem._t); + if( !mem._one ) t = mem.outside(t); + // Store forwarding is also a value fact during SCCP. Waiting for the + // later rewrite can turn a known non-null stored pointer into a + // nullable declaration, then BOTTOM at the next dereference. + if( t instanceof TypeMemPtr && pfld._alias>1 && + find(mem(),ptr(),null,null,t) instanceof StoreNode st ) + t = addDepForwards(st.val())._type; + // A deeply read-only base produces a deeply read-only value. The // generic declared field type must not cast this information away. if( ptr0.isFinal() || readonly ) @@ -205,30 +213,50 @@ public class LoadNode extends MemOpNode { // the unchanged loop memory, or a merge whose every arm folds. Null fails. // Register dependencies so a later pointer/offset rewrite retries the query. private Node find(Node mem, Node ptr, Node stop, BitSet visit) { - if( ptr instanceof ReadOnlyNode ro ) ptr=ro.in(1); - Field fld; - boolean external = ptr._type instanceof TypeMemPtr tmp && - (fld=tmp._obj.field(_name))!=null && fld._extern; + return find(mem,ptr,stop,visit,_type); + } + + private Node find(Node mem, Node ptr, Node stop, BitSet visit, Type expected) { + ptr = address(ptr); + Field fld = ptr._type instanceof TypeMemPtr owner ? owner._obj.field(_name) : null; + int alias = fld==null ? _alias : fld._alias; + boolean external = fld!=null && fld._extern; while( mem!=null ) { addDep(mem); if( mem==stop ) return mem; switch( mem ) { - case MemMergeNode merge: mem=merge.alias(_alias); break; + case MemMergeNode merge: mem=merge.alias(alias); break; case StoreNode st: // Alias 1 is still unresolved, not a proven different field. if( st._alias==1 ) return null; addDep(st.ptr()); - if( _alias==st._alias && (ptr==st.ptr() || ptr==st.nnptr()) && off()==st.off() ) { + if( alias==st._alias && (ptr==address(st.ptr()) || ptr==address(st.nnptr())) && + ((!_name.equals("[]") && _name.equals(st._name)) || off()==st.off() || + (addDep(off())._type.isConstant() && off()._type==addDep(st.off())._type)) ) { + // Forwarding must preserve the pointer type already seen + // by users: completion, read-only view, and recursive shape. + // Open declarations can disagree until Opto upgrades them. + if( expected instanceof TypeMemPtr ) { + Type value = addDep(st.val())._type; + if( ptr()._type.isFinal() || declaredType().isFinal() ) value = value.makeRO(); + if( !value.isa(expected) ) return null; + } // A full-width load cannot narrow the forwarded value. if( declaredType() instanceof TypeInteger ti && ti.log_size()==3 && - !addDep(st.val())._type.isa(_type) ) return null; + !addDep(st.val())._type.isa(expected) ) return null; return st; } - if( (external || _alias==st._alias) && (external || !neverAlias(ptr,st.ptr())) && + if( (external || alias==st._alias) && (external || !neverAlias(ptr,address(st.ptr()))) && !addDep(off())._type.join(addDep(st.off())._type).isHigh() ) return null; mem=st.mem(); break; case ProjNode proj: + if( proj._idx==1 && proj.in(0) instanceof CLInitNode init ) { + Node prior = init.pcopy(1,this); + if( prior==null ) return null; + mem = prior; + break; + } // New's memory is private; public memory is joined at Escape. if( external || !(proj.in(0) instanceof NewNode nnn) ) return null; if( declaredType()==Type.BOTTOM ) return null; @@ -236,8 +264,8 @@ public class LoadNode extends MemOpNode { case EscapeNode esc: if( external ) return null; addDep(esc.self()); - if( esc.self()==ptr ) { mem=esc.priv(); break; } - if( neverAlias(ptr,esc.self()) ) { mem=esc.pub(); break; } + if( address(esc.self())==ptr ) { mem=esc.priv(); break; } + if( neverAlias(ptr,address(esc.self())) ) { mem=esc.pub(); break; } return null; case MemPhiNode phi: addDep(phi.region()); @@ -278,6 +306,25 @@ public class LoadNode extends MemOpNode { return ld.peephole(); } + // Type views preserve the address. Keep the actual Load pointer qualified + // for compute/err; only alias comparisons see through these views. + private Node address(Node ptr) { + // A pointer Load with a proven reaching Store denotes the stored + // address even before the later peephole replaces the Load itself. + if( ptr instanceof LoadNode ld && addDepForwards(ld)._type instanceof TypeMemPtr && + ld.ptr()._type instanceof TypeMemPtr base && base.notNull() && ld.err()==null && + ld.find(ld.mem(),ld.ptr(),null,null) instanceof StoreNode st ) + ptr = addDepForwards(st.val()); + if( ptr instanceof ConvertNode conv && addDep(conv.val())._type instanceof TypeMemPtr src && + src.isa(addDep(conv)._type) && src.accessISA(conv._type) ) + ptr = conv.val(); + while( ptr instanceof ReadOnlyNode ) { + addDep(ptr); + ptr = ptr.in(1); + } + return ptr; + } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { return ptr1.in(0) != ptr2.in(0) && // Unrelated allocations diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 316efb93..b92c93bb 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -50,7 +50,7 @@ public class ParmNode extends PhiNode { @Override public Type compute() { if( !(region() instanceof RegionNode r) ) - return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; + return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_declaredType instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. if( r.inProgress() || in(nIns()-1)==null ) return _declaredType; @@ -63,7 +63,12 @@ public class ParmNode extends PhiNode { if( ctrl != Type.XCONTROL && ctrl != Type.TOP ) { if( in(i)._type==Type.BOTTOM ) return Type.BOTTOM; - t = t.meet(in(i)._type); + Type arg = in(i)._type; + // The unknown-caller callback input is Start's memory + // projection, interpreted using this parameter's signature. + if( i==1 && r.in(i) instanceof StartNode && _idx>1 && arg instanceof TypeMem outside ) + arg = outside.outside(_declaredType); + t = t.meet(arg); } } // Recursion is a loop in disguise. A Parm merges the first argument @@ -73,7 +78,8 @@ public class ParmNode extends PhiNode { // widening this Parm alone cannot stop f(x-1)+1 from growing its result. if( t instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() ) t = ti.same_but_slightly_wider_than(); - return t.join(_declaredType); + t = t.join(_declaredType); + return t==Type.TOP && _declaredType instanceof TypeMem ? TypeMem.TOP : t; } @Override diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/StartNode.java index 3c605e30..283da7df 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -26,6 +26,9 @@ import java.util.HashSet; public class StartNode extends LoopNode implements MultiNode { final Type _arg; + // Immutable foreign identity seed, installed with Opto's reset. Actual + // local escapes arrive through Stop, not through a frozen public list. + public TypeMem _foreign = TypeMem.START; public StartNode(StartNode start, StopNode stop, Type arg) { super(null,start,stop); _arg = arg; } public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; } @@ -55,16 +58,10 @@ public class StartNode extends LoopNode implements MultiNode { } boolean escapedFIDX(int fidx) { - // Public class fields are callable by the unknown external world - // regardless of the current SCCP approximation of Start memory. - if( CodeGen.CODE.publicFIDX(fidx) ) return true; if( !(_type instanceof TypeTuple tt) ) return !_type.isHigh(); // TOP never escapes, BOTTOM always escapes TypeMem tmem = (TypeMem)tt._types[1]; - if( tmem == TypeMem.BOT ) return false; if( tmem == TypeMem.TOP ) return false; - if( XInt.isHigh(tmem._escFs) ) - return false; return XInt.bit(tmem._escFs,fidx); } @@ -73,12 +70,22 @@ public class StartNode extends LoopNode implements MultiNode { TypeMem tmem = stop._type instanceof TypeTuple tt ? tt.mem() : stop._type.isHigh() ? TypeMem.START : TypeMem.BOT; + if( !(this instanceof StartCUNode) ) tmem = tmem.escapes(_foreign); + else if( in(0) instanceof StartNode start ) tmem = tmem.escapes(start.outside(this)); assert tmem._alias==1 && !tmem._one; return TypeTuple.make(Type.CONTROL,tmem,_arg); } @Override public Node idealize() { return null; } + // Consumers register against the value they read, even when their Call's + // control remains unchanged as more identities escape. + public TypeMem outside(Node dep) { + if( CodeGen.CODE._phase==null || CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ) return TypeMem.BOT; + Type t = dep.addDepForwards(this)._type; + return t instanceof TypeTuple tt ? tt.mem() : t.isHigh() ? _foreign : TypeMem.BOT; + } + // No immediate dominator, and idepth==0 @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index 53c2325c..ae7abbb4 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -12,6 +12,9 @@ public class StopCUNode extends StopNode { public StopCUNode(StopNode stop) { super(stop); } + // Each compilation unit owns its Stop by identity. + @Override public boolean eq(Node n) { return false; } + public StartCUNode start() { for( Node use : _outputs ) if( use instanceof StartCUNode start ) @@ -27,17 +30,10 @@ public class StopCUNode extends StopNode { return TypeTuple.STATE; StartCUNode start = start(); - // Memory start from all returns + // Recompute from inputs, not our previous result. Unknown values carry + // FULL escape sets: restricting them to public names would lose private + // objects/functions which a later load-forwarding rewrite can reveal. TypeMem xmem = TypeMem.START; - // Escape summaries are monotone discovery facts. In Opto, a Return - // can widen from a precise set to FULL; the public-only normalization - // below must not forget private bits already discovered precisely from - // that Return on an earlier SCCP step. - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() && - CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.Lower.ordinal() && - _type instanceof TypeTuple old && old.mem() instanceof TypeMem omem ) - xmem = xmem.makeFrom(XInt.meet(xmem._escFs,omem._escFs), - XInt.meet(xmem._escAs,omem._escAs)); for( Node def : _inputs ) { ReturnNode ret = (ReturnNode)def; @@ -48,10 +44,9 @@ public class StopCUNode extends StopNode { FunNode fun = ret.fun(); boolean noUserCtor = fun.isInstance() && !CodeGen.hasUserConstructor(((TypeMemPtr)fun.sig().arg(0))._obj); - // Instance <init> is an allocation helper, never an externally - // callable constructor when a user constructor exists. Otherwise - // the same no-arg <init> is the public constructor. - boolean pub = fun.isPublic() && (fun.isClz() || noUserCtor); + // Only entry initializers seed escape discovery. Constructors + // and methods are discovered through escaping class/instance fields. + boolean pub = fun.isClz() && (CodeGen.CODE.entryClinitName().equals(fun._name) || fun.isPublic()); TypeFunPtr sig = fun.sig(); // If public init, the function escapes and the related class escapes if( pub ) { @@ -72,48 +67,21 @@ public class StopCUNode extends StopNode { // here as its effects are not visible to the outside world. addDepForwards(start); // Check again if function escapes if( pub || start.escapedFIDX(sig.fidx()) ) { - // External callers already hold their object arguments, so - // writes through those arguments expose addresses too. - for( Node use : fun._outputs ) - if( use instanceof ParmNode p && p._idx>=2 ) - xmem=publicBottom(xmem.escapes(addDepForwards(p)._type)); if( tret.ctl().isHigh() ) continue; // Return not reachable // Capture (precisely?) all escaping pointer aliases and fidxs. // Escaped fidxs means the linked world can call that function; // escaped aliases means the linked world can R/W those aliases. - xmem = xmem.escapes(tret.ret()); - xmem = publicBottom(xmem); - xmem = (TypeMem)xmem.meet(publicBottom(tret.mem(),xmem)); + xmem = xmem.escapesFrom(tret.ret(),start.outside(this)); + xmem = (TypeMem)xmem.meet(tret.mem()); } } - // Native retention is shared by the whole program, including calls - // on paths with no Return. A class boundary must not hide it. + // Calls can retain arguments even on paths with no Return. for( CallNode call : CodeGen.CODE._calls ) - if( !call.isDead() ) xmem=publicBottom(xmem.escapes(call.exposed(this))); + if( !call.isDead() ) xmem = xmem.escapes(call.exposed(this)); assert xmem._alias==1 && !xmem._one; return TypeTuple.make(Type.CONTROL,xmem,Type.BOTTOM); } - // FULL escape sets arise from global BOTTOM. Across a compilation-unit - // boundary global BOTTOM exposes every public field, while retaining any - // private escapes already discovered precisely. - private TypeMem publicBottom(TypeMem mem) { return publicBottom(mem,mem); } - private TypeMem publicBottom(TypeMem mem, TypeMem prior) { - // The pessimistic Iter pass naturally lifts transient FULL inputs to - // precise finite sets. Replacing FULL early there would let a later - // input refinement add bits, reversing Iter's monotonic direction. - // This normalization is needed only for Opto's optimistic grand cycle. - if( CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() || - CodeGen.CODE._phase.ordinal() > CodeGen.Phase.Lower.ordinal() ) return mem; - int[] escFs = XInt.isHigh(mem._escFs) - ? XInt.meet(prior._escFs,CodeGen.CODE.publicFIDXs()) - : mem._escFs; - int[] escAs = XInt.isHigh(mem._escAs) - ? XInt.meet(prior._escAs,CodeGen.CODE.publicAliases()) - : mem._escAs; - return escFs==mem._escFs && escAs==mem._escAs ? mem : mem.makeFrom(escFs,escAs); - } - @Override public Node idealize() { int len = nIns(); diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/StoreNode.java index bdd07c8d..8cad3259 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -76,6 +76,7 @@ public class StoreNode extends MemOpNode { Type decl = declaredType(); if( decl != Type.BOTTOM ) { assert decl != Type.TOP; val = val.join(decl); } + TypeMem outside = TypeMem.opaque(val) ? CodeGen.CODE._start.outside(this) : TypeMem.BOT; // A singleton class's final constant field lives in the static image. // Its precise memory slice is a constant too; ordinary peepholes can // replace this Store before scheduling or instruction selection. @@ -84,14 +85,16 @@ public class StoreNode extends MemOpNode { Field fld = ptr._obj.field(_name); if( _alias!=1 && ptr._one && Parser.startsClzPrefix(ptr._obj._name) && fld!=null && fld._final && decl.isConstant() ) - return TypeMem.make(_alias,val,true,true,true,mem._escFs,mem._escAs).escapesFrom(val); + // A constant slice contains only this value's escapes. Copying + // bulk escapes here would freeze a transient FULL into it. + return TypeMem.make(_alias,val,true,true,true,null,null).escapesFrom(val,outside); // Allocation uses a private TypeMem and nothing else does. This // memory is truly private; a temporary singleton until it escapes - // which is never does in a constructor. if( !_name.equals("[]") && mem._one ) // Just track the stored value - return TypeMem.make(_alias,val,true,false,_init,null,null).escapesFrom(val); + return TypeMem.make(_alias,val,true,false,_init,null,null).escapesFrom(val,outside); // Normal aliasing Store. assert mem._alias==1 || mem._alias==_alias; // Perfect aliasing @@ -106,7 +109,7 @@ public class StoreNode extends MemOpNode { // Bulk memory's final bit describes its conservative remainder, not // this newly precise slice. Slice finality comes from the field. boolean xfinal = fld != null && fld._final; - return TypeMem.make(_alias,t,mem._one,mem._clz,xfinal,mem._escFs,mem._escAs).escapesFrom(val); + return TypeMem.make(_alias,t,mem._one,mem._clz,xfinal,mem._escFs,mem._escAs).escapesFrom(val,outside); } @Override diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 301fcc8b..2303af49 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -78,6 +78,10 @@ public class TypeFunPtr extends TypeNil { @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } public TypeFunPtr makeFrom( int fidx ) { return make1(_nil,_open,_sig,_ret,fidx); } + public TypeFunPtr restrictFIDXs(int[] fidxs) { + int[] ids = XInt.dual(XInt.meet(XInt.dual(_fidxs),XInt.dual(fidxs))); + return ids==_fidxs ? this : make(_nil,_open,_sig,_ret,ids); + } public TypeFunPtr makeFrom( Type arg, int idx ) { // Alter named arg Type[] sig = _sig.clone(); diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeMem.java index a0079eae..bd0585c8 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -90,10 +90,29 @@ public class TypeMem extends Type { public TypeMem escapesFrom(Type t) { return make(_alias,_t,_one,_clz,_final, escapeFIDX(_escFs,t), escapeAlias(_escAs,t)); } + // An opaque external object can expose the public interface and whatever + // private values have already escaped. It cannot invent access to other + // private definitions here. The caller supplies FULL until local forward + // types are resolved. Ordinary unknown values still require FULL. + public TypeMem escapesFrom(Type t, TypeMem defaults) { + if( opaque(t) ) + return makeFrom(XInt.meet(_escFs,defaults._escFs),XInt.meet(_escAs,defaults._escAs)); + return escapesFrom(t); + } + public static boolean opaque(Type t) { + TypeStruct ts = t instanceof TypeMemPtr ptr ? ptr._obj : t instanceof TypeStruct obj ? obj : null; + return ts!=null && ts._open && ts._fref && !ts.isAry(); + } public TypeMem escapesAliases(Type t) { return make(_alias,_t,_one,_clz,_final, _escFs, escapeAlias(_escAs,t)); } + // A value supplied by the outside world, bounded by its declared family. + // Foreign identities remain possible even when no local function escapes. + public Type outside(Type declared) { + return declared instanceof TypeFunPtr fun ? fun.restrictFIDXs(_escFs) : declared; + } + public static final TypeMem TOP = make(1, Type.TOP ,true ,true, true , XInt.EMPTY, XInt.EMPTY); public static final TypeMem BOT = make(1, Type.BOTTOM,false,false,true , XInt.FULL , XInt.FULL ); public static final TypeMem START= make(1,Type.BOTTOM,false,false,false, XInt.EMPTY, XInt.EMPTY); diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 67169009..d6531be2 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -98,7 +98,7 @@ public class TypeStruct extends Type { maxAlias = Math.max(maxAlias,f._alias); int len = XInt.idx(maxAlias)+1; if( (maxAlias&31)==31 ) len++; - int[] xs = XInt.free(len); + int[] xs = XInt.alloc(len); for( Field f : _fields ) if( f._fname.charAt(0) != '_' && // Skip private fields. !hiddenInit(f) && // Skip private allocation helper. @@ -122,13 +122,11 @@ public class TypeStruct extends Type { return (_fidxs = xs); } - // With a user constructor, the same-named function field is the hidden - // default <init> allocation helper, not part of the public class surface. + // Initializer/constructor helpers receive private memory. Only the + // allocator has a source-callable signature. public boolean hiddenInit(Field fld) { - if( field("<ctor>") == null || !_name.startsWith("class:") ) return false; - int idx = _name.lastIndexOf('.'); - String name = _name.substring(idx<0 ? "class:".length() : idx+1); - return fld._fname.equals(name); + return fld._t instanceof TypeFunPtr tfp && tfp.nargs()>=2 && + tfp.arg(1) instanceof TypeMem; } // New open struct with no fields diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/type/XInt.java b/chapter28a/src/main/java/com/seaofnodes/simple/type/XInt.java index 126a4e64..898ed97a 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/type/XInt.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -92,7 +92,7 @@ public abstract class XInt { int len = Math.max(xs.length,idx+1); if( (x&31)==31 && idx+1==len ) len++; - int[] ys = free(len); + int[] ys = alloc(len); System.arraycopy(xs,1,ys,1,xs.length-1); ys[idx] |= mask(x); return intern(ys); @@ -112,7 +112,7 @@ public abstract class XInt { len--; // Replace with trimmed if( len < xs.length ) { - var ys = free(len); + var ys = alloc(len); System.arraycopy(xs,1,ys,1,len-1); xs = _free(xs,ys); } @@ -146,8 +146,9 @@ public abstract class XInt { FREES.setX(len, xss = new Ary<>(int[].class)); return xss; } - // Pull free array from free list - static int[] free(int len) { + // Allocate a zeroed mutable array, reusing the free list. + // Pass it to intern after filling; do not retain a mutable reference. + public static int[] alloc(int len) { int[] xs = _xss(len).pop(); if( xs==null ) { NEWS++; xs = new int[len]; } @@ -176,7 +177,7 @@ public abstract class XInt { if( isX ) return xs; if( isY ) return ys; // Get a free one - int[] ms = free(max); + int[] ms = alloc(max); for( int i=1; i<min; i++ ) ms[i] = xs[i] | ys[i]; for( int i=min; i<ms.length; i++ ) { @@ -189,7 +190,7 @@ public abstract class XInt { // Dual: flip all the bits public static int[] dual(int[] xs) { - int[] ds = free(xs.length); + int[] ds = alloc(xs.length); for( int i=1; i<xs.length; i++ ) ds[i] = ~xs[i]; return intern(ds); diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 39c7040e..04e66a6f 100644 --- a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -156,7 +156,7 @@ else return v; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Test.Vector2D; return MEM[ 2:___ 3:.x=0; 4:.y=0;]; return Test.Vector2D; ]", code.print()); + assertEquals("Stop[ return Test.Vector2D; return Test.Vector2D; ]", code.print()); } @Test @@ -194,7 +194,7 @@ while (arg) { return bar.a; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MEM[ 2:___ 3:.a=0;]; return Test.Bar; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return Test.Bar; ]", code.print()); } @Test @@ -243,10 +243,10 @@ struct _Bar { int a; }; !_Bar? !bar = new _Bar; if (arg) bar = null; if( bar ) bar.a = 1; -return bar.a; +return bar; """); - code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Region,1,.a);", code.print()); + code.driver(CodeGen.Phase.TypeCheck); + assertEquals("return Phi(Region,null,Test._Bar);", code.print()); } @Test @@ -316,7 +316,7 @@ while( i.x < i.len ) { return sum; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return MEM[ 2:___ 3:.x=0; 4:.len=0;]; return Test.Iter; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return Test.Iter; ]", code.print()); } @@ -335,7 +335,7 @@ while(arg) { return ret; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MEM[ 2:___ 3:.v0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return Test.s0; ]", code.print()); } @Test @@ -387,7 +387,7 @@ s0 b = new s0(); return a.x * 100 + b.x * 10 + cnt; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return 112; return MEM[ 2:___ 3:___ 4:.x=1;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return 112; return Test.s0; ]", code.print()); } @@ -430,7 +430,7 @@ else return new s0; if(new s0.f0) return 0; """); code.driver(CodeGen.Phase.TypeCheck); - assertEquals("Stop[ return Test.s0; return MEM[ 2:___ 3:.f0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Test.s0; return Test.s0; ]", code.print()); } @Test @@ -458,7 +458,7 @@ s0 v1 = v0; return v1; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return (const)Test.s0; return MEM[ 2:___ 3:.f0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return (const)Test.s0; return Test.s0; ]", code.print()); } diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter12Test.java index fae7611d..973b15d9 100644 --- a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -101,7 +101,7 @@ N n = new N(new M); return n.next; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return (const)Test.M; return MEM[ 2:___ 3:.m=0;]; return Test.M; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:.next=Parm_m(Test.N.N,*Test.M {i64 !m; }); 8:.i=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:___ 8:.i=0;]; return Test.N; ]", code.print()); + assertEquals("Stop[ return (const)Test.M; return Test.M; return Test.N; ]", code.print()); } @Test diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 632b9539..8e109991 100644 --- a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -345,7 +345,7 @@ for(;;) { } """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return Top; return Parm_i(x,i64); ]", code.print()); + assertEquals("return Top;", code.print()); assertNull( Eval2.eval( code, 0 ) ); // Infinite loop, <clinit> never exits } diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter19Test.java index d5fe207a..3cc00922 100644 --- a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -118,7 +118,7 @@ val hashCode = { !String self -> hashCode(new String("Hello, World!")); """; CodeGen code = new CodeGen(src).driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return MEM[ 2:___ 3:___ 4:___ 5:.cs=Parm_s(Test.String.String,*[]u8[final]); 6:._hashCode=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:._hashCode=0;]; return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); + assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); assertEquals("4029215624828139541", Eval2.eval(code, 2)); } diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter20Test.java index cdfd16a7..7eb1f255 100644 --- a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -241,13 +241,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -255,9 +248,17 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; """; + // Return the public hashCode wrapper; keep its helper private. testCPU(src,"x86_64_v2", "SystemV",12,null); - testCPU(src,"riscv" , "SystemV",6,null); + testCPU(src,"riscv" , "SystemV",8,null); testCPU(src,"arm" , "SystemV",6,null); } diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 2fcf65e9..e15c2581 100644 --- a/chapter28a/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter28a/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -368,13 +368,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -382,9 +375,17 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; """; + // Return the public hashCode wrapper; keep its helper private. testCPU(src,"x86_64_v2", "SystemV",12,null); - testCPU(src,"riscv" , "SystemV",6,null); + testCPU(src,"riscv" , "SystemV",8,null); testCPU(src,"arm" , "SystemV",6,null); } @@ -407,13 +408,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -421,6 +415,13 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; """; TestC.runC(src, "stringHash", "",12); } diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java index 6b4a987d..c8a00d19 100644 --- a/chapter28a/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java +++ b/chapter28a/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java @@ -132,6 +132,28 @@ public class ClassInitDependenciesTest { assertTrue(touches(code,deps,"Root/B","Root")); } + @Test public void testUnknownCallbackCycle() throws Exception { + for( long seed : new long[]{1,123,987654321} ) { + try { + compile("A",Map.of( + "A", """ + { {int->int} -> {int->int} } bounce="C"; + val callback_noInline={int n -> B.value;}; + val f=bounce(callback_noInline); + int value=f(1); + """, + "B", "int value=A.value;"),seed); + fail("Expected callback initialization cycle"); + } catch( Parser.ParseException ex ) { + String message=ex.getMessage(); + assertTrue(message,message.startsWith("Cyclic class initialization:")); + assertTrue(message,message.contains(" -> unknown call")); + assertTrue(message,message.contains("unknown call -> ")); + assertTrue(message,message.contains("Root.B -> Root.A")); + } + } + } + @Test public void testCycles() throws Exception { cycle("A",Map.of("A","val get_noInline={ ->\n B.value;\n};\nint value=get_noInline();", "B","int value=A.value;"),"A -> B -> A"); diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java new file mode 100644 index 00000000..71a281b5 --- /dev/null +++ b/chapter28a/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java @@ -0,0 +1,112 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class EscapeFlowTest { + // A cofinite outside set must not revive private allocation helpers. + @Test public void testOpaqueRoundTrip() { + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(""" + struct _A { B? !b; new _A = { B? p -> b=p; }; }; + val wrap = { B? b -> return new _A(b); }; + return wrap; + """,seed,true).driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(XInt.isHigh(outside._escFs)); + assertNotSame(XInt.FULL,outside._escFs); + for( FunNode fun : code._linker ) + if( fun!=null && fun._name!=null && fun._name.contains("_A.") ) + assertFalse(fun._name,fun.unknownCallers()); + } + } + + // Foreign callbacks remain possible. The default callback argument reads + // Start memory rather than a frozen declaration constant. + @Test public void testUnknownCallerCallback() { + CodeGen code = new CodeGen(""" + val _hidden_noInline = { int n -> return n+2; }; + val apply_noInline = { {int->int} f,int n -> return f(n); }; + return apply_noInline; + """).parse(); + TypeMemPtr self = (TypeMemPtr)named(code,"apply_noInline").parm(2).in(1)._type; + assertTrue(self._one); + assertEquals("class:Test",self._obj._name); + code.driver(CodeGen.Phase.TypeCheck); + FunNode apply = named(code,"apply_noInline"); + assertTrue(apply.unknownCallers()); + ParmNode callback = apply.parm(3); + assertTrue(callback.in(1) instanceof ProjNode); + TypeFunPtr type = (TypeFunPtr)callback._type; + assertTrue(XInt.isHigh(type.fidxs())); + assertSame(TypeInteger.BOT,apply.ret().expr()._type); + // Only <clinit> and apply escape; forwarding #self must not expose _hidden. + assertEquals("Stop[ return { apply_noInline}; return #2; ]",code.print()); + } + + @Test public void testNativeCallbackRoundTrip() { + CodeGen code = new CodeGen(""" + val _callback_noInline = { int n -> return n+1; }; + { {int->int} -> {int->int} } bounce = "C"; + return bounce(_callback_noInline)(arg); + """).driver(CodeGen.Phase.TypeCheck); + FunNode callback = named(code,"_callback_noInline"); + assertTrue(callback.unknownCallers()); + assertTrue(XInt.bit(((TypeTuple)code._start._type).mem()._escFs,callback.sig().fidx())); + } + + // Call remains CONTROL. Changing only the outside set must wake CallEnd + // and extend the possible callback returned by the native factory. + @Test public void testOutsideReturnDependency() { + CodeGen code = new CodeGen("return 0;").parse(); + code._phase = CodeGen.Phase.Opto; + code.externFunc(100,"factory"); + TypeFunPtr callback = TypeFunPtr.make(false,TypeFunPtr.TEMPTY,TypeInteger.BOT); + TypeFunPtr factory = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,callback,100); + CallNode call = new CallNode(null,ConstantNode.raw(Type.CONTROL), + ConstantNode.raw(TypeMem.START),ConstantNode.raw(factory)).init(); + CallEndNode end = new CallEndNode(call,TypeRPC.BOT); + int[] foreign = XInt.dual(XInt.make(7)); + code._start._type = TypeTuple.make(Type.CONTROL,TypeMem.START.makeFrom(foreign,XInt.EMPTY),TypeInteger.BOT); + TypeTuple before = (TypeTuple)end.compute(); + assertFalse(XInt.bit(((TypeFunPtr)before.ret()).fidxs(),7)); + boolean depends = false; + for( int i = 0; i<code._start.nDeps(); i++ ) depends |= code._start.dep(i)==end; + assertTrue(depends); + code._start._type = TypeTuple.make(Type.CONTROL,TypeMem.START.makeFrom(XInt.FULL,XInt.EMPTY),TypeInteger.BOT); + TypeTuple after = (TypeTuple)end.compute(); + assertTrue(before.isa(after)); + assertTrue(XInt.bit(((TypeFunPtr)after.ret()).fidxs(),7)); + } + + // Public construction exposes the allocator; private-memory helpers + // remain internal and can inline into it. + @Test public void testPublicAllocator() { + CodeGen code = new CodeGen(""" + struct Box { int n; new Box = { int x -> n=x; }; }; + return new Box(arg).n; + """).parse(); + FunNode allocator = named(code,"Test.Box.<new>"); + int[] helpers = XInt.EMPTY; + for( FunNode fun : code._linker ) + if( fun!=null && fun.sig().ret() instanceof TypeMem ) + helpers = XInt.make(helpers,fun.sig().fidx()); + assertNotSame(XInt.EMPTY,helpers); + code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(allocator.unknownCallers()); + assertTrue(XInt.bit(outside._escFs,allocator.sig().fidx())); + for( int fidx = XInt.next(helpers,0); fidx>=0; fidx = XInt.next(helpers,fidx) ) + assertFalse(XInt.bit(outside._escFs,fidx)); + assertEquals("42",Eval2.eval(code,42)); + } + + private static FunNode named(CodeGen code, String name) { + for( FunNode fun : code._linker ) + if( fun!=null && name.equals(fun._name) ) return fun; + throw new AssertionError("Missing function "+name); + } +} diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/ModulesTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/ModulesTest.java index be54b43d..69f8d862 100644 --- a/chapter28a/src/test/java/com/seaofnodes/simple/ModulesTest.java +++ b/chapter28a/src/test/java/com/seaofnodes/simple/ModulesTest.java @@ -11,6 +11,9 @@ import com.seaofnodes.simple.node.CallNode; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.LoopNode; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.XInt; +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeTuple; import com.seaofnodes.simple.util.Ary; import java.io.File; import java.io.FileWriter; @@ -71,27 +74,56 @@ public class ModulesTest { for( long seed : new long[]{1,123,987654321} ) { CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.Parse); FunNode visible = null; + int[] privateFidxs = XInt.EMPTY; int checked = 0; for( FunNode fun : code._linker ) { if( fun==null || fun._name==null ) continue; if( fun._name.equals("visible") ) { - assertTrue(code.publicFIDX(fun.sig().fidx())); visible = fun; checked++; } if( fun._name.equals("_hidden") || fun._name.equals("hiddenClassMethod") ) { - assertFalse(code.publicFIDX(fun.sig().fidx())); + privateFidxs = XInt.make(privateFidxs,fun.sig().fidx()); checked++; } } assertEquals(3,checked); code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(XInt.bit(outside._escFs,visible.sig().fidx())); + for( int fidx = XInt.next(privateFidxs,0); fidx>=0; fidx = XInt.next(privateFidxs,fidx) ) + assertFalse(XInt.bit(outside._escFs,fidx)); assertTrue(visible.unknownCallers()); assertEquals(TypeInteger.U8,visible.parm(3)._type); assertEquals("0",Eval2.eval(code,0)); } } + @Test public void testPublicFunctionAlias() { + CodeGen code = new CodeGen(""" + val _hidden = { int x -> x; }; + val visible = _hidden; + val _private = { int x -> x+1; }; + return 0; + """).parse(); + int published = -1, unpublished = -1; + for( FunNode fun : code._linker ) { + if( fun==null || fun._name==null ) continue; + if( fun._name.equals("_hidden") ) published = fun.sig().fidx(); + if( fun._name.equals("_private") ) unpublished = fun.sig().fidx(); + } + assertTrue(published>=0 && unpublished>=0); + var clz = code.compunit()._clz; + code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + // A public field can publish a privately named function. + assertTrue(XInt.bit(outside._escFs,published)); + assertFalse(XInt.bit(outside._escFs,unpublished)); + assertTrue(XInt.bit(outside._escAs,clz.field("visible")._alias)); + assertFalse(XInt.bit(outside._escAs,clz.field("_hidden")._alias)); + assertFalse(XInt.bit(outside._escAs,clz.field("_private")._alias)); + } + @Test public void testNeverReturnPointerRiscV() { new CodeGen(""" struct _S { int x; }; 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<ids.length; i++ ) { Type t = sig.arg(i); // Args take a default input if called from Start/external-world - _scope.define(ids[i], t, (i==0 && ids[0]=="self") || (finals!=null && finals.get(i)), new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(t).peephole()).peephole(), loc); + _scope.define(ids[i], t, (i==0 && ids[0]=="self") || (finals!=null && finals.get(i)), new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(fun.defaultArg(i)).peephole()).peephole(), loc); } if( isCtor && !isInit ) { @@ -1343,13 +1343,16 @@ public class Parser { : TypeStruct.make(clzName,false,fld,ctorFld); if( flag!=null ) ts=ts.add(flag); TypeFunPtr alloc = makeAllocator((TypeStruct)TYPES.get(fullName),ret,ctorFld); + // Publish the source-callable allocator, not the private-memory helper. + sig = alloc; + ts = ts.replace(fld.makeFrom(alloc)); ts = ts.add(Field.make("<new>",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 = <init>" + // This is basically sugar for "val CLZNAME = <new>" // 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("<ctor>") != null; - for( Field fld : clz._fields ) { - // With a user constructor, class:N.N is the private <init>. - 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("<ctor>") != 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<<i); + } + return XInt.intern(foreign); + } + GlobalBits() { _local = RESERVED; // Reserved null-class bits are global identities and are never diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java index 4085ebff..5b4fb983 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -69,8 +69,7 @@ public abstract class Iter { for( Node n : nodes ) if( !n.isDead() ) n._type = n instanceof ConstantNode ? n.compute() : iterImportReset(n._type); - // Stop normalizes unknown memory into the unit's visible escapes. - // Do not publish a transient FULL Stop merely because we reset its body. + // Recompute each imported unit's contribution from its reset inputs. for( Node n : nodes ) if( n instanceof StopCUNode && !n.isDead() ) n._type = n.compute(); code.addAll(nodes); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 511e0027..8c8827c6 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -25,12 +25,16 @@ abstract public class Opto { // get a fairly precise set of Call Graph edges between CallNodes and // FunNodes. public static void opto(CodeGen code) { + int[] foreign = code._fidxs.foreign(); + for( int fidx : code._externFunc.keySet() ) foreign = XInt.make(foreign,fidx); + code._start._foreign = TypeMem.START.makeFrom(foreign,code._aliases.foreign()); // Reset Types before running the worklist algorithm Ary<Type> oldTypes = new Ary<>(Type.class); WorkList<Node> deps = new WorkList<>(); WorkList<Node> changes = new WorkList<>(); Ary<Node> modes = new Ary<>(Node.class); - resetToTop(code,oldTypes,modes,deps); + Ary<ReturnNode> 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<Type> oldTypes, Ary<Node> modes, WorkList<Node> deps ) { + private static void resetToTop(CodeGen code, Ary<Type> oldTypes, Ary<Node> modes, WorkList<Node> deps, Ary<ReturnNode> 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<fun.nIns(); j++ ) @@ -106,11 +113,8 @@ 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);` + // Infinite targets use the outside continuation. Escaped local + // callbacks are reached through Start, and their effects feed Stop. 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 @@ -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<nIns(); i++ ) + state = (TypeTuple)state.meet(in(i)._type); + return state; + } // Check for making a "C" call int externs = 0; @@ -98,7 +104,8 @@ public class CallEndNode extends CFGNode implements MultiNode { // C calls have no Return edges. Simple calls have an extra self // argument, so the two cannot be targets of the same valid call. assert externs==tfp.nfcns(); - return TypeTuple.make(Type.CONTROL,call.exposed(this),tfp.ret()); + TypeMem outside = CodeGen.CODE._start.outside(this).escapes(call.exposed(this)); + return TypeTuple.make(Type.CONTROL,outside,outside.outside(tfp.ret())); } // An unlinked target may have effects, so early conservative return. diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java index 29d4f6aa..23188e84 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -81,22 +81,6 @@ public class CallNode extends CFGNode { return false; } - // Unknown callers contribute declared argument types to the parameters. - // Those broad types can hide a particular private callback supplied here. - // Expose actual arguments too, including calls through library summaries. - boolean exposesArguments(Node dep) { - if( external() ) return true; - if( !(fptr()._type instanceof TypeFunPtr tfp) ) return false; - for( int fidx = XInt.next(tfp.fidxs(),0); fidx>=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<nIns()-1; i++ ) escaped = escaped.escapes(dep.addDepForwards(arg(i))._type); + TypeMem outside = CodeGen.CODE._start.outside(dep); + for( int i = 2; i<nIns()-1; i++ ) + escaped = escaped.escapesFrom(dep.addDepForwards(arg(i))._type,outside); return TypeMem.make(1,Type.BOTTOM,false,false,false,escaped._escFs,escaped._escAs); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index 7f5398ef..6e338756 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -39,7 +39,12 @@ public class ConvertNode extends Node { @Override public Type compute() { Type src = val()._type; if( src.isHigh() ) return Type.TOP; - if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; + if( _dst instanceof TypeMemPtr ptr ) { + // Keep non-nullness before the identity rewrite; shape and access + // still follow the declaration so compute stays monotone. + return src instanceof TypeMemPtr actual && actual.notNull() ? ptr.nonZero() : ptr; + } + if( src.isa(_dst) ) return src; return _dst; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index 3e95fffb..f7a88df1 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; @@ -75,7 +76,12 @@ public class EscapeNode extends TypeNode { Type t = tpriv.meet(tpub).join(fld._t); int[] fidxes = XInt.meet(mpriv._escFs, mpub._escFs); int[] aliases = XInt.meet(mpriv._escAs, mpub._escAs); - return TypeMem.make(fld._alias, t, false, false, fld._final, fidxes, aliases).escapesFrom(t); + // Keep escapes from the actual private value before narrowing it to + // the declaration. Selecting its Store from a MemMerge must preserve + // this result, including Scalar.BOT's unknown pointer escapes. + TypeMem defaults = CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ? TypeMem.BOT : mpub; + return TypeMem.make(fld._alias, t, false, false, fld._final, fidxes, aliases) + .escapesFrom(tpriv,defaults).escapesFrom(t,defaults); } @Override public Node idealize() { diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java index 6a8d5d50..62915373 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -96,6 +96,17 @@ public class FunNode extends RegionNode { // Signature can improve over time public TypeFunPtr sig() { return _sig; } + // A class function's hidden receiver defaults to its owning singleton. + // Keep PTR in the signature: it marks the hidden ABI slot and permits + // uniform call syntax, including callbacks forwarded by another class. + public Type defaultArg(int idx) { + Type t = sig().arg(idx); + if( idx!=0 || t!=TypePtr.PTR ) return t; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(_compunit._cname)); + assert clz!=null; + return TypeMemPtr.make((byte)2,clz,true); + } + public void setSig( TypeFunPtr sig ) { assert sig.isa(_sig) || resolvesForwardSelf(sig,_sig); if( _sig != sig ) { diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java index dab48530..740b0895 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java @@ -16,19 +16,14 @@ public class GlobalEscapeNode extends Node { @Override public Node idealize() { return null; } @Override public TypeMem compute() { - TypeMem xmem = StopCUNode.priorEscapes(_type); + TypeMem xmem = TypeMem.START; for( CallNode call : CodeGen.CODE._calls ) if( !call.isDead() ) { - xmem = StopCUNode.publicBottom(xmem.escapes(call.exposed(this)),xmem); - // FULL memory normalizes to public bits. Preserve precise - // private arguments independently of that normalization. - if( call._type==Type.CONTROL && call.exposesArguments(this) ) - for( int i = 0; i<call.nargs(); i++ ) - xmem = StopCUNode.publicBottom(xmem.escapes(addDepForwards(call.arg(i+2))._type),xmem); + xmem = xmem.escapes(call.exposed(this)); } for( FunNode fun : CodeGen.CODE._linker ) if( fun!=null && fun.summary()!=null && !fun.summary().isDead() ) { - xmem = StopCUNode.publicBottom(xmem.escapes(fun.summary().exposed(this)),xmem); + xmem = xmem.escapes(fun.summary().exposed(this)); // A reachable unloaded body can call these targets, including // private initializers. Its arguments are unavailable here. if( fun._type==Type.CONTROL ) diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index c58bba39..22836d90 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -93,6 +93,14 @@ public class LoadNode extends MemOpNode { if( mem._alias==_alias ) t = t.join(mem._t); + if( !mem._one ) t = mem.outside(t); + // Store forwarding is also a value fact during SCCP. Waiting for the + // later rewrite can turn a known non-null stored pointer into a + // nullable declaration, then BOTTOM at the next dereference. + if( t instanceof TypeMemPtr && pfld._alias>1 && + find(mem(),ptr(),null,null,t) instanceof StoreNode st ) + t = addDepForwards(st.val())._type; + // A deeply read-only base produces a deeply read-only value. The // generic declared field type must not cast this information away. if( ptr0.isFinal() || readonly ) @@ -211,30 +219,50 @@ public class LoadNode extends MemOpNode { // the unchanged loop memory, or a merge whose every arm folds. Null fails. // Register dependencies so a later pointer/offset rewrite retries the query. private Node find(Node mem, Node ptr, Node stop, BitSet visit) { - if( ptr instanceof ReadOnlyNode ro ) ptr=ro.in(1); - Field fld; - boolean external = ptr._type instanceof TypeMemPtr tmp && - (fld=tmp._obj.field(_name))!=null && fld._extern; + return find(mem,ptr,stop,visit,_type); + } + + private Node find(Node mem, Node ptr, Node stop, BitSet visit, Type expected) { + ptr = address(ptr); + Field fld = ptr._type instanceof TypeMemPtr owner ? owner._obj.field(_name) : null; + int alias = fld==null ? _alias : fld._alias; + boolean external = fld!=null && fld._extern; while( mem!=null ) { addDep(mem); if( mem==stop ) return mem; switch( mem ) { - case MemMergeNode merge: mem=merge.alias(_alias); break; + case MemMergeNode merge: mem=merge.alias(alias); break; case StoreNode st: // Alias 1 is still unresolved, not a proven different field. if( st._alias==1 ) return null; addDep(st.ptr()); - if( _alias==st._alias && (ptr==st.ptr() || ptr==st.nnptr()) && off()==st.off() ) { + if( alias==st._alias && (ptr==address(st.ptr()) || ptr==address(st.nnptr())) && + ((!_name.equals("[]") && _name.equals(st._name)) || off()==st.off() || + (addDep(off())._type.isConstant() && off()._type==addDep(st.off())._type)) ) { + // Forwarding must preserve the pointer type already seen + // by users: completion, read-only view, and recursive shape. + // Open declarations can disagree until Opto upgrades them. + if( expected instanceof TypeMemPtr ) { + Type value = addDep(st.val())._type; + if( ptr()._type.isFinal() || declaredType().isFinal() ) value = value.makeRO(); + if( !value.isa(expected) ) return null; + } // A full-width load cannot narrow the forwarded value. if( declaredType() instanceof TypeInteger ti && ti.log_size()==3 && - !addDep(st.val())._type.isa(_type) ) return null; + !addDep(st.val())._type.isa(expected) ) return null; return st; } - if( (external || _alias==st._alias) && (external || !neverAlias(ptr,st.ptr())) && + if( (external || alias==st._alias) && (external || !neverAlias(ptr,address(st.ptr()))) && !addDep(off())._type.join(addDep(st.off())._type).isHigh() ) return null; mem=st.mem(); break; case ProjNode proj: + if( proj._idx==1 && proj.in(0) instanceof CLInitNode init ) { + Node prior = init.pcopy(1,this); + if( prior==null ) return null; + mem = prior; + break; + } // New's memory is private; public memory is joined at Escape. if( external || !(proj.in(0) instanceof NewNode nnn) ) return null; if( declaredType()==Type.BOTTOM ) return null; @@ -242,8 +270,8 @@ public class LoadNode extends MemOpNode { case EscapeNode esc: if( external ) return null; addDep(esc.self()); - if( esc.self()==ptr ) { mem=esc.priv(); break; } - if( neverAlias(ptr,esc.self()) ) { mem=esc.pub(); break; } + if( address(esc.self())==ptr ) { mem=esc.priv(); break; } + if( neverAlias(ptr,address(esc.self())) ) { mem=esc.pub(); break; } return null; case MemPhiNode phi: addDep(phi.region()); @@ -284,6 +312,25 @@ public class LoadNode extends MemOpNode { return ld.peephole(); } + // Type views preserve the address. Keep the actual Load pointer qualified + // for compute/err; only alias comparisons see through these views. + private Node address(Node ptr) { + // A pointer Load with a proven reaching Store denotes the stored + // address even before the later peephole replaces the Load itself. + if( ptr instanceof LoadNode ld && addDepForwards(ld)._type instanceof TypeMemPtr && + ld.ptr()._type instanceof TypeMemPtr base && base.notNull() && ld.err()==null && + ld.find(ld.mem(),ld.ptr(),null,null) instanceof StoreNode st ) + ptr = addDepForwards(st.val()); + if( ptr instanceof ConvertNode conv && addDep(conv.val())._type instanceof TypeMemPtr src && + src.isa(addDep(conv)._type) && src.accessISA(conv._type) ) + ptr = conv.val(); + while( ptr instanceof ReadOnlyNode ) { + addDep(ptr); + ptr = ptr.in(1); + } + return ptr; + } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { return ptr1.in(0) != ptr2.in(0) && // Unrelated allocations diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 91c471c0..99b6ad11 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -64,7 +64,7 @@ public class ParmNode extends PhiNode { @Override public Type compute() { if( !(region() instanceof RegionNode r) ) - return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; + return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_declaredType instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. if( r.inProgress() || in(nIns()-1)==null ) return _declaredType; @@ -77,7 +77,12 @@ public class ParmNode extends PhiNode { if( ctrl != Type.XCONTROL && ctrl != Type.TOP ) { if( in(i)._type==Type.BOTTOM ) return Type.BOTTOM; - t = t.meet(in(i)._type); + Type arg = in(i)._type; + // The unknown-caller callback input is Start's memory + // projection, interpreted using this parameter's signature. + if( i==1 && r.in(i) instanceof StartNode && _idx>1 && arg instanceof TypeMem outside ) + arg = outside.outside(_declaredType); + t = t.meet(arg); } } // Recursion is a loop in disguise. A Parm merges the first argument @@ -87,7 +92,8 @@ public class ParmNode extends PhiNode { // widening this Parm alone cannot stop f(x-1)+1 from growing its result. if( t instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() ) t = ti.same_but_slightly_wider_than(); - return t.join(_declaredType); + t = t.join(_declaredType); + return t==Type.TOP && _declaredType instanceof TypeMem ? TypeMem.TOP : t; } @Override diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/StartNode.java index a7ea4ac1..0acc1d48 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -26,6 +26,9 @@ import java.util.HashSet; public class StartNode extends LoopNode implements MultiNode { final Type _arg; + // Immutable foreign identity seed, installed with Opto's reset. Actual + // local escapes arrive through Stop, not through a frozen public list. + public TypeMem _foreign = TypeMem.START; public StartNode(StartNode start, StopNode stop, Type arg) { super(null,start,stop); _arg = arg; } public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; } @@ -67,12 +70,22 @@ public class StartNode extends LoopNode implements MultiNode { TypeMem tmem = stop._type instanceof TypeTuple tt ? tt.mem() : stop._type.isHigh() ? TypeMem.START : TypeMem.BOT; + if( !(this instanceof StartCUNode) ) tmem = tmem.escapes(_foreign); + else if( in(0) instanceof StartNode start ) tmem = tmem.escapes(start.outside(this)); assert tmem._alias==1 && !tmem._one; return TypeTuple.make(Type.CONTROL,tmem,_arg); } @Override public Node idealize() { return null; } + // Consumers register against the value they read, even when their Call's + // control remains unchanged as more identities escape. + public TypeMem outside(Node dep) { + if( CodeGen.CODE._phase==null || CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ) return TypeMem.BOT; + Type t = dep.addDepForwards(this)._type; + return t instanceof TypeTuple tt ? tt.mem() : t.isHigh() ? _foreign : TypeMem.BOT; + } + // No immediate dominator, and idepth==0 @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index a6116e93..ead635dd 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -19,6 +19,10 @@ public class StopCUNode extends StopNode { return stop; } + // CompUnit owns this wrapper by identity. Even empty units must not share + // a Stop: doing so can merge their Starts and their kept memory projections. + @Override public boolean eq(Node n) { return false; } + public StartCUNode start() { for( Node use : _outputs ) if( use instanceof StartCUNode start ) @@ -34,8 +38,10 @@ public class StopCUNode extends StopNode { return TypeTuple.STATE; StartCUNode start = start(); - // Memory start from all returns - TypeMem xmem = priorEscapes(_type instanceof TypeTuple old ? old.mem() : _type); + // Recompute from inputs, not our previous result. Unknown values carry + // FULL escape sets: restricting them to public names would lose private + // objects/functions which a later load-forwarding rewrite can reveal. + TypeMem xmem = TypeMem.START; for( Node def : _inputs ) { ReturnNode ret = (ReturnNode)def; @@ -69,59 +75,23 @@ public class StopCUNode extends StopNode { // here as its effects are not visible to the outside world. addDepForwards(start); // Check again if function escapes if( pub || start.escapedFIDX(sig.fidx()) ) { - // External callers already hold their object arguments, so - // writes through those arguments expose addresses too. - for( Node use : fun._outputs ) - if( use instanceof ParmNode p && p._idx>=2 ) - xmem = publicBottom(xmem.escapes(addDepForwards(p)._type),xmem); if( tret.ctl().isHigh() ) continue; // Return not reachable // Capture (precisely?) all escaping pointer aliases and fidxs. // Escaped fidxs means the linked world can call that function; // escaped aliases means the linked world can R/W those aliases. - xmem = publicBottom(xmem.escapes(tret.ret()),xmem); - xmem = (TypeMem)xmem.meet(publicBottom(tret.mem(),xmem)); + xmem = xmem.escapesFrom(tret.ret(),start.outside(this)); + xmem = (TypeMem)xmem.meet(tret.mem()); } } // All units share escapes from calls and unloaded bodies, including // paths with no Return. Revisit only when that shared result changes. GlobalEscapeNode global = CodeGen.CODE._globalEscapes; if( global!=null && !global.isDead() ) - xmem = publicBottom(xmem.escapes(addDepForwards(global)._type),xmem); + xmem = xmem.escapes(addDepForwards(global)._type); assert xmem._alias==1 && !xmem._one; return TypeTuple.make(Type.CONTROL,xmem,Type.BOTTOM); } - // FULL escape sets arise from global BOTTOM. Across a compilation-unit - // boundary global BOTTOM exposes every public field, while retaining any - // private escapes already discovered precisely. - static TypeMem publicBottom(TypeMem mem, TypeMem prior) { - // The pessimistic Iter pass naturally lifts transient FULL inputs to - // precise finite sets. Replacing FULL early there would let a later - // input refinement add bits, reversing Iter's monotonic direction. - // This normalization is needed only for Opto's optimistic grand cycle. - if( CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() || - CodeGen.CODE._phase.ordinal() > CodeGen.Phase.Lower.ordinal() ) return mem; - int[] escFs = XInt.isHigh(mem._escFs) - ? XInt.meet(prior._escFs,CodeGen.CODE.publicFIDXs()) - : mem._escFs; - int[] escAs = XInt.isHigh(mem._escAs) - ? XInt.meet(prior._escAs,CodeGen.CODE.publicAliases()) - : mem._escAs; - return escFs==mem._escFs && escAs==mem._escAs ? mem : mem.makeFrom(escFs,escAs); - } - - // In Opto, a precise escape set can widen to FULL. Public-only - // normalization must retain private bits discovered on an earlier step. - static TypeMem priorEscapes(Type old) { - TypeMem mem = TypeMem.START; - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() && - CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.Lower.ordinal() && - old instanceof TypeMem prior ) - mem = mem.makeFrom(XInt.meet(mem._escFs,prior._escFs), - XInt.meet(mem._escAs,prior._escAs)); - return mem; - } - @Override public Node idealize() { int len = nIns(); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 5fa0b99f..2c62db7d 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -89,6 +89,7 @@ public class StoreNode extends MemOpNode { Type decl = declaredType(); if( decl != Type.BOTTOM ) { assert decl != Type.TOP; val = val.join(decl); } + TypeMem outside = TypeMem.opaque(val) ? CodeGen.CODE._start.outside(this) : TypeMem.BOT; // A singleton class's final constant field lives in the static image. // Its precise memory slice is a constant too; ordinary peepholes can // replace this Store before scheduling or instruction selection. @@ -97,14 +98,16 @@ public class StoreNode extends MemOpNode { Field fld = ptr._obj.field(_name); if( _alias!=1 && ptr._one && Parser.startsClzPrefix(ptr._obj._name) && fld!=null && fld._final && decl.isConstant() ) - return TypeMem.make(_alias,val,true,true,true,mem._escFs,mem._escAs).escapesFrom(val); + // A constant slice contains only this value's escapes. Copying + // bulk escapes here would freeze a transient FULL into it. + return TypeMem.make(_alias,val,true,true,true,null,null).escapesFrom(val,outside); // Allocation uses a private TypeMem and nothing else does. This // memory is truly private; a temporary singleton until it escapes - // which is never does in a constructor. if( !_name.equals("[]") && mem._one ) // Just track the stored value - return TypeMem.make(_alias,val,true,false,_init,null,null).escapesFrom(val); + return TypeMem.make(_alias,val,true,false,_init,null,null).escapesFrom(val,outside); // Normal aliasing Store. assert mem._alias==1 || mem._alias==_alias; // Perfect aliasing @@ -119,7 +122,7 @@ public class StoreNode extends MemOpNode { // Bulk memory's final bit describes its conservative remainder, not // this newly precise slice. Slice finality comes from the field. boolean xfinal = fld != null && fld._final; - return TypeMem.make(_alias,t,mem._one,mem._clz,xfinal,mem._escFs,mem._escAs).escapesFrom(val); + return TypeMem.make(_alias,t,mem._one,mem._clz,xfinal,mem._escFs,mem._escAs).escapesFrom(val,outside); } @Override diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java index c22b4bdd..483aab89 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java @@ -26,7 +26,8 @@ public class SummaryNode extends CFGNode implements MultiNode { // A library summary does not forget escapes already present in the caller. TypeMem mem = in(1)._type instanceof TypeMem m ? m : in(1)._type.isHigh() ? TypeMem.TOP : TypeMem.BOT; mem = (TypeMem)mem.meet(_state.mem()); - for( int i = 2; i<nIns(); i++ ) mem=mem.escapes(in(i)._type); + TypeMem outside = CodeGen.CODE._start.outside(this); + for( int i = 2; i<nIns(); i++ ) mem = mem.escapesFrom(in(i)._type,outside); return TypeTuple.make(_state.ctl(),mem,_state.ret()); } @Override public Node idealize() { return null; } @@ -34,7 +35,8 @@ public class SummaryNode extends CFGNode implements MultiNode { dep.addDepForwards(this); if( dep.addDepForwards(in(0))._type.isHigh() ) return TypeMem.START; TypeMem mem = (TypeMem)_state.mem(); - for( int i = 2; i<nIns(); i++ ) mem=mem.escapes(dep.addDepForwards(in(i))._type); + TypeMem outside = CodeGen.CODE._start.outside(dep); + for( int i = 2; i<nIns(); i++ ) mem = mem.escapesFrom(dep.addDepForwards(in(i))._type,outside); return TypeMem.make(1,Type.BOTTOM,false,false,false,mem._escFs,mem._escAs); } @Override boolean _upgradeType(HashMap<String,Type> types) { diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter28b/src/main/java/com/seaofnodes/simple/type/Type.java index 980daf0f..11e847d8 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -622,11 +622,12 @@ public class Type /*implements Cloneable*/ { private static int[] remapBits(GlobalBits fileBits, GlobalBits bits, int[] fileLocals, int firstMapped ) { if( fileLocals == XInt.EMPTY || fileLocals == XInt.FULL ) return fileLocals; - assert !XInt.isHigh(fileLocals); + boolean complement = XInt.isHigh(fileLocals); + if( complement ) fileLocals = XInt.dual(fileLocals); int[] locals = XInt.EMPTY; for( int fileLocal = XInt.next(fileLocals,-1); fileLocal >=0; fileLocal = XInt.next(fileLocals,fileLocal) ) locals = XInt.make(locals,fileLocal < firstMapped ? fileLocal : bits.map(fileBits,fileLocal)); - return locals; + return complement ? XInt.dual(locals) : locals; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 56f47bff..19ec5019 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -79,6 +79,10 @@ public class TypeFunPtr extends TypeNil { @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } public TypeFunPtr makeFrom( int fidx ) { return make1(_nil,_open,_sig,_ret,fidx); } + public TypeFunPtr restrictFIDXs(int[] fidxs) { + int[] ids = XInt.dual(XInt.meet(XInt.dual(_fidxs),XInt.dual(fidxs))); + return ids==_fidxs ? this : make(_nil,_open,_sig,_ret,ids); + } public TypeFunPtr makeFrom( Type arg, int idx ) { // Alter named arg Type[] sig = _sig.clone(); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 278a3ea0..cd0ae5d7 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -90,10 +90,29 @@ public class TypeMem extends Type { public TypeMem escapesFrom(Type t) { return make(_alias,_t,_one,_clz,_final, escapeFIDX(_escFs,t), escapeAlias(_escAs,t)); } + // An opaque external object can expose the public interface and whatever + // private values have already escaped. It cannot invent access to other + // private definitions here. The caller supplies FULL until local forward + // types are resolved. Ordinary unknown values still require FULL. + public TypeMem escapesFrom(Type t, TypeMem defaults) { + if( opaque(t) ) + return makeFrom(XInt.meet(_escFs,defaults._escFs),XInt.meet(_escAs,defaults._escAs)); + return escapesFrom(t); + } + public static boolean opaque(Type t) { + TypeStruct ts = t instanceof TypeMemPtr ptr ? ptr._obj : t instanceof TypeStruct obj ? obj : null; + return ts!=null && ts._open && ts._fref && !ts.isAry(); + } public TypeMem escapesAliases(Type t) { return make(_alias,_t,_one,_clz,_final, _escFs, escapeAlias(_escAs,t)); } + // A value supplied by the outside world, bounded by its declared family. + // Foreign identities remain possible even when no local function escapes. + public Type outside(Type declared) { + return declared instanceof TypeFunPtr fun ? fun.restrictFIDXs(_escFs) : declared; + } + public static final TypeMem TOP = make(1, Type.TOP ,true ,true, true , XInt.EMPTY, XInt.EMPTY); public static final TypeMem BOT = make(1, Type.BOTTOM,false,false,true , XInt.FULL , XInt.FULL ); public static final TypeMem START= make(1,Type.BOTTOM,false,false,false, XInt.EMPTY, XInt.EMPTY); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 4c5ae6ea..7574022a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -98,7 +98,7 @@ public class TypeStruct extends Type { maxAlias = Math.max(maxAlias,f._alias); int len = XInt.idx(maxAlias)+1; if( (maxAlias&31)==31 ) len++; - int[] xs = XInt.free(len); + int[] xs = XInt.alloc(len); for( Field f : _fields ) if( f._fname.charAt(0) != '_' && // Skip private fields. !hiddenInit(f) && // Skip private allocation helper. @@ -122,13 +122,11 @@ public class TypeStruct extends Type { return (_fidxs = xs); } - // With a user constructor, the same-named function field is the hidden - // default <init> allocation helper, not part of the public class surface. + // Initializer/constructor helpers receive private memory. Only the + // allocator has a source-callable signature. public boolean hiddenInit(Field fld) { - if( field("<ctor>") == null || !_name.startsWith("class:") ) return false; - int idx = _name.lastIndexOf('.'); - String name = _name.substring(idx<0 ? "class:".length() : idx+1); - return fld._fname.equals(name); + return fld._t instanceof TypeFunPtr tfp && tfp.nargs()>=2 && + tfp.arg(1) instanceof TypeMem; } // New open struct with no fields diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/type/XInt.java b/chapter28b/src/main/java/com/seaofnodes/simple/type/XInt.java index 3e74df84..06c9d466 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/type/XInt.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -92,7 +92,7 @@ public abstract class XInt { int len = Math.max(xs.length,idx+1); if( (x&31)==31 && idx+1==len ) len++; - int[] ys = free(len); + int[] ys = alloc(len); System.arraycopy(xs,1,ys,1,xs.length-1); ys[idx] |= mask(x); return intern(ys); @@ -112,7 +112,7 @@ public abstract class XInt { len--; // Replace with trimmed if( len < xs.length ) { - var ys = free(len); + var ys = alloc(len); System.arraycopy(xs,1,ys,1,len-1); xs = _free(xs,ys); } @@ -146,8 +146,9 @@ public abstract class XInt { FREES.setX(len, xss = new Ary<>(int[].class)); return xss; } - // Pull free array from free list - static int[] free(int len) { + // Allocate a zeroed mutable array, reusing the free list. + // Pass it to intern after filling; do not retain a mutable reference. + public static int[] alloc(int len) { int[] xs = _xss(len).pop(); if( xs==null ) { NEWS++; xs = new int[len]; } @@ -176,7 +177,7 @@ public abstract class XInt { if( isX ) return xs; if( isY ) return ys; // Get a free one - int[] ms = free(max); + int[] ms = alloc(max); for( int i=1; i<min; i++ ) ms[i] = xs[i] | ys[i]; for( int i=min; i<ms.length; i++ ) { @@ -189,7 +190,7 @@ public abstract class XInt { // Dual: flip all the bits public static int[] dual(int[] xs) { - int[] ds = free(xs.length); + int[] ds = alloc(xs.length); for( int i=1; i<xs.length; i++ ) ds[i] = ~xs[i]; return intern(ds); @@ -203,7 +204,7 @@ public abstract class XInt { } public static int[] packed(BAOS bais) { int len = bais.packed1(); - int[] xs = free(len); + int[] xs = alloc(len); for( int i=1; i<len; i++ ) xs[i] = bais.packed4(); return intern(xs); @@ -230,7 +231,7 @@ public abstract class XInt { public static int[] remap( int[] xs, AryInt map ) { if( xs==FULL ) return xs; assert !isHigh(xs); - int[] ys = free(xs.length); + int[] ys = alloc(xs.length); for( int bit = next(xs,0); bit >=0; bit = next(xs,bit) ) { int bat = map.at(bit); ys[idx(bat)] |= mask(bat); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6892db0c..165eba21 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -157,7 +157,7 @@ else return v; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Test.Vector2D; return MEM[ 2:___ 3:.x=0; 4:.y=0;]; return Test.Vector2D; ]", code.print()); + assertEquals("Stop[ return Test.Vector2D; return Test.Vector2D; ]", code.print()); } @Test @@ -195,7 +195,7 @@ while (arg) { return bar.a; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MEM[ 2:___ 3:.a=0;]; return Test.Bar; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return Test.Bar; ]", code.print()); } @Test @@ -244,10 +244,10 @@ struct _Bar { int a; }; !_Bar? !bar = new _Bar; if (arg) bar = null; if( bar ) bar.a = 1; -return bar.a; +return bar; """); - code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Region,1,.a);", code.print()); + code.driver(CodeGen.Phase.TypeCheck); + assertEquals("return Phi(Region,null,Test._Bar);", code.print()); } @Test @@ -317,7 +317,7 @@ while( i.x < i.len ) { return sum; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return MEM[ 2:___ 3:.x=0; 4:.len=0;]; return Test.Iter; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return Test.Iter; ]", code.print()); } @@ -336,7 +336,7 @@ while(arg) { return ret; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MEM[ 2:___ 3:.v0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return Test.s0; ]", code.print()); } @Test @@ -389,7 +389,7 @@ s0 b = new s0(); return a.x * 100 + b.x * 10 + cnt; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return 112; return MEM[ 2:___ 3:___ 4:.x=1;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return 112; return Test.s0; ]", code.print()); } @@ -432,7 +432,7 @@ else return new s0; if(new s0.f0) return 0; """); code.driver(CodeGen.Phase.TypeCheck); - assertEquals("Stop[ return Test.s0; return MEM[ 2:___ 3:.f0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Test.s0; return Test.s0; ]", code.print()); } @Test @@ -460,7 +460,7 @@ s0 v1 = v0; return v1; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return (const)Test.s0; return MEM[ 2:___ 3:.f0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return (const)Test.s0; return Test.s0; ]", code.print()); } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index fae7611d..973b15d9 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -101,7 +101,7 @@ N n = new N(new M); return n.next; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return (const)Test.M; return MEM[ 2:___ 3:.m=0;]; return Test.M; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:.next=Parm_m(Test.N.N,*Test.M {i64 !m; }); 8:.i=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:___ 8:.i=0;]; return Test.N; ]", code.print()); + assertEquals("Stop[ return (const)Test.M; return Test.M; return Test.N; ]", code.print()); } @Test diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 632b9539..8e109991 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -345,7 +345,7 @@ for(;;) { } """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return Top; return Parm_i(x,i64); ]", code.print()); + assertEquals("return Top;", code.print()); assertNull( Eval2.eval( code, 0 ) ); // Infinite loop, <clinit> never exits } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter19Test.java index d5fe207a..3cc00922 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -118,7 +118,7 @@ val hashCode = { !String self -> hashCode(new String("Hello, World!")); """; CodeGen code = new CodeGen(src).driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return MEM[ 2:___ 3:___ 4:___ 5:.cs=Parm_s(Test.String.String,*[]u8[final]); 6:._hashCode=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:._hashCode=0;]; return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); + assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); assertEquals("4029215624828139541", Eval2.eval(code, 2)); } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 66a318ae..7eb1f255 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -241,13 +241,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -255,11 +248,18 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; """; - // The implicit return exposes _hashCodeString, so retain its body too. - testCPU(src,"x86_64_v2", "SystemV",21,null); - testCPU(src,"riscv" , "SystemV",9,null); - testCPU(src,"arm" , "SystemV",7,null); + // Return the public hashCode wrapper; keep its helper private. + testCPU(src,"x86_64_v2", "SystemV",12,null); + testCPU(src,"riscv" , "SystemV",8,null); + testCPU(src,"arm" , "SystemV",6,null); } @Test diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java index f1dc54e2..e15c2581 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -368,13 +368,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -382,11 +375,18 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; """; - // The implicit return exposes _hashCodeString, so retain its body too. - testCPU(src,"x86_64_v2", "SystemV",21,null); - testCPU(src,"riscv" , "SystemV",9,null); - testCPU(src,"arm" , "SystemV",7,null); + // Return the public hashCode wrapper; keep its helper private. + testCPU(src,"x86_64_v2", "SystemV",12,null); + testCPU(src,"riscv" , "SystemV",8,null); + testCPU(src,"arm" , "SystemV",6,null); } @Test public void testStringExport() throws IOException { @@ -408,13 +408,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -422,8 +415,15 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; """; - TestC.runC(src, "stringHash", "",21); + TestC.runC(src, "stringHash", "",12); } @Test public void testLoop2() { diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java index f5eba8f5..1ad1e129 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -12,6 +12,8 @@ import com.seaofnodes.simple.node.CallNode; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.LoopNode; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeTuple; import com.seaofnodes.simple.type.XInt; import com.seaofnodes.simple.util.Ary; import java.io.File; @@ -73,21 +75,25 @@ public class Chapter25Test { for( long seed : new long[]{1,123,987654321} ) { CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.Parse); FunNode visible = null; + int[] privateFidxs = XInt.EMPTY; int checked = 0; for( FunNode fun : code._linker ) { if( fun==null || fun._name==null ) continue; if( fun._name.equals("visible") ) { - assertTrue(code.publicFIDX(fun.sig().fidx())); visible = fun; checked++; } if( fun._name.equals("_hidden") || fun._name.equals("hiddenClassMethod") ) { - assertFalse(code.publicFIDX(fun.sig().fidx())); + privateFidxs = XInt.make(privateFidxs,fun.sig().fidx()); checked++; } } assertEquals(3,checked); code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(XInt.bit(outside._escFs,visible.sig().fidx())); + for( int fidx = XInt.next(privateFidxs,0); fidx>=0; fidx = XInt.next(privateFidxs,fidx) ) + assertFalse(XInt.bit(outside._escFs,fidx)); assertTrue(visible.unknownCallers()); assertEquals(TypeInteger.U8,visible.parm(3)._type); assertEquals("0",Eval2.eval(code,0)); @@ -101,25 +107,52 @@ public class Chapter25Test { val _private = { int x -> x+1; }; return 0; """).parse(); - int checked = 0; + int published = -1, unpublished = -1; for( FunNode fun : code._linker ) { if( fun==null || fun._name==null ) continue; - if( fun._name.equals("_hidden") ) { - // A public field can publish a privately named function. - assertTrue(code.publicFIDX(fun.sig().fidx())); - checked++; - } - if( fun._name.equals("_private") ) { - assertFalse(code.publicFIDX(fun.sig().fidx())); - checked++; - } + if( fun._name.equals("_hidden") ) published = fun.sig().fidx(); + if( fun._name.equals("_private") ) unpublished = fun.sig().fidx(); } - assertEquals(2,checked); + assertTrue(published>=0 && unpublished>=0); var clz = code.compunit()._clz; - assertTrue(XInt.bit(code.publicAliases(),clz.field("visible")._alias)); - assertFalse(XInt.bit(code.publicAliases(),clz.field("_hidden")._alias)); - assertFalse(XInt.bit(code.publicAliases(),clz.field("_private")._alias)); code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + // A public field can publish a privately named function. + assertTrue(XInt.bit(outside._escFs,published)); + assertFalse(XInt.bit(outside._escFs,unpublished)); + assertTrue(XInt.bit(outside._escAs,clz.field("visible")._alias)); + assertFalse(XInt.bit(outside._escAs,clz.field("_hidden")._alias)); + assertFalse(XInt.bit(outside._escAs,clz.field("_private")._alias)); + } + + @Test public void testImportedEscapeExclusions() throws IOException { + Path build=Path.of("build/objs"); + Files.createDirectories(build); + Path dir=Files.createTempDirectory(build,"escape_exclusions_"); + CodeGen library=new CodeGen(null,dir.toString(),null,"Lib",""" + val _hidden_noInline={int n -> n+100;}; + val apply_noInline={{int->int} f,int n -> f(n);}; + return apply_noInline; + """,123,true,TypeInteger.BOT).driver("x86_64_v2","win64",false,false); + int savedHidden=((com.seaofnodes.simple.type.TypeFunPtr) + library.compunit()._clz.field("_hidden_noInline")._t).fidx(); + // Allocate unrelated IDs before loading Lib so saved exclusions must + // remap by owner/slot, not by their numeric positions in the file. + CodeGen code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Client",""" + val _other={int n -> n-1;}; + val inc={int n -> n+1;}; + return Lib.apply_noInline(inc,arg); + """,987654321,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + var clz=(com.seaofnodes.simple.type.TypeStruct)Parser.TYPES.get("class:Lib"); + int hidden=((com.seaofnodes.simple.type.TypeFunPtr)clz.field("_hidden_noInline")._t).fidx(); + assertNotEquals(savedHidden,hidden); + TypeMem outside=((TypeTuple)code._start._type).mem(); + assertTrue(XInt.isHigh(outside._escFs)); + assertFalse(XInt.bit(outside._escFs,hidden)); + assertEquals("42",Eval2.eval(code,41)); + Files.delete(dir.resolve("Lib.o")); + Files.delete(dir); } @Test public void testNeverReturnPointerRiscV() { diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java index 38b4d8a2..dfd7a78c 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java @@ -157,6 +157,28 @@ public class ClassInitDependenciesTest { assertTrue(touches(code,deps,"Root/B","Root")); } + @Test public void testUnknownCallbackCycle() throws Exception { + for( long seed : new long[]{1,123,987654321} ) { + try { + compile("A",Map.of( + "A", """ + { {int->int} -> {int->int} } bounce="C"; + val callback_noInline={int n -> B.value;}; + val f=bounce(callback_noInline); + int value=f(1); + """, + "B", "int value=A.value;"),seed); + fail("Expected callback initialization cycle"); + } catch( Parser.ParseException ex ) { + String message=ex.getMessage(); + assertTrue(message,message.startsWith("Cyclic class initialization:")); + assertTrue(message,message.contains(" -> unknown call")); + assertTrue(message,message.contains("unknown call -> ")); + assertTrue(message,message.contains("Root.B -> Root.A")); + } + } + } + @Test public void testCycles() throws Exception { cycle("A",Map.of("A","val get_noInline={ ->\n B.value;\n};\nint value=get_noInline();", "B","int value=A.value;"),"A -> B -> A"); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java new file mode 100644 index 00000000..71a281b5 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java @@ -0,0 +1,112 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class EscapeFlowTest { + // A cofinite outside set must not revive private allocation helpers. + @Test public void testOpaqueRoundTrip() { + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(""" + struct _A { B? !b; new _A = { B? p -> b=p; }; }; + val wrap = { B? b -> return new _A(b); }; + return wrap; + """,seed,true).driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(XInt.isHigh(outside._escFs)); + assertNotSame(XInt.FULL,outside._escFs); + for( FunNode fun : code._linker ) + if( fun!=null && fun._name!=null && fun._name.contains("_A.") ) + assertFalse(fun._name,fun.unknownCallers()); + } + } + + // Foreign callbacks remain possible. The default callback argument reads + // Start memory rather than a frozen declaration constant. + @Test public void testUnknownCallerCallback() { + CodeGen code = new CodeGen(""" + val _hidden_noInline = { int n -> return n+2; }; + val apply_noInline = { {int->int} f,int n -> return f(n); }; + return apply_noInline; + """).parse(); + TypeMemPtr self = (TypeMemPtr)named(code,"apply_noInline").parm(2).in(1)._type; + assertTrue(self._one); + assertEquals("class:Test",self._obj._name); + code.driver(CodeGen.Phase.TypeCheck); + FunNode apply = named(code,"apply_noInline"); + assertTrue(apply.unknownCallers()); + ParmNode callback = apply.parm(3); + assertTrue(callback.in(1) instanceof ProjNode); + TypeFunPtr type = (TypeFunPtr)callback._type; + assertTrue(XInt.isHigh(type.fidxs())); + assertSame(TypeInteger.BOT,apply.ret().expr()._type); + // Only <clinit> and apply escape; forwarding #self must not expose _hidden. + assertEquals("Stop[ return { apply_noInline}; return #2; ]",code.print()); + } + + @Test public void testNativeCallbackRoundTrip() { + CodeGen code = new CodeGen(""" + val _callback_noInline = { int n -> return n+1; }; + { {int->int} -> {int->int} } bounce = "C"; + return bounce(_callback_noInline)(arg); + """).driver(CodeGen.Phase.TypeCheck); + FunNode callback = named(code,"_callback_noInline"); + assertTrue(callback.unknownCallers()); + assertTrue(XInt.bit(((TypeTuple)code._start._type).mem()._escFs,callback.sig().fidx())); + } + + // Call remains CONTROL. Changing only the outside set must wake CallEnd + // and extend the possible callback returned by the native factory. + @Test public void testOutsideReturnDependency() { + CodeGen code = new CodeGen("return 0;").parse(); + code._phase = CodeGen.Phase.Opto; + code.externFunc(100,"factory"); + TypeFunPtr callback = TypeFunPtr.make(false,TypeFunPtr.TEMPTY,TypeInteger.BOT); + TypeFunPtr factory = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,callback,100); + CallNode call = new CallNode(null,ConstantNode.raw(Type.CONTROL), + ConstantNode.raw(TypeMem.START),ConstantNode.raw(factory)).init(); + CallEndNode end = new CallEndNode(call,TypeRPC.BOT); + int[] foreign = XInt.dual(XInt.make(7)); + code._start._type = TypeTuple.make(Type.CONTROL,TypeMem.START.makeFrom(foreign,XInt.EMPTY),TypeInteger.BOT); + TypeTuple before = (TypeTuple)end.compute(); + assertFalse(XInt.bit(((TypeFunPtr)before.ret()).fidxs(),7)); + boolean depends = false; + for( int i = 0; i<code._start.nDeps(); i++ ) depends |= code._start.dep(i)==end; + assertTrue(depends); + code._start._type = TypeTuple.make(Type.CONTROL,TypeMem.START.makeFrom(XInt.FULL,XInt.EMPTY),TypeInteger.BOT); + TypeTuple after = (TypeTuple)end.compute(); + assertTrue(before.isa(after)); + assertTrue(XInt.bit(((TypeFunPtr)after.ret()).fidxs(),7)); + } + + // Public construction exposes the allocator; private-memory helpers + // remain internal and can inline into it. + @Test public void testPublicAllocator() { + CodeGen code = new CodeGen(""" + struct Box { int n; new Box = { int x -> n=x; }; }; + return new Box(arg).n; + """).parse(); + FunNode allocator = named(code,"Test.Box.<new>"); + int[] helpers = XInt.EMPTY; + for( FunNode fun : code._linker ) + if( fun!=null && fun.sig().ret() instanceof TypeMem ) + helpers = XInt.make(helpers,fun.sig().fidx()); + assertNotSame(XInt.EMPTY,helpers); + code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(allocator.unknownCallers()); + assertTrue(XInt.bit(outside._escFs,allocator.sig().fidx())); + for( int fidx = XInt.next(helpers,0); fidx>=0; fidx = XInt.next(helpers,fidx) ) + assertFalse(XInt.bit(outside._escFs,fidx)); + assertEquals("42",Eval2.eval(code,42)); + } + + private static FunNode named(CodeGen code, String name) { + for( FunNode fun : code._linker ) + if( fun!=null && name.equals(fun._name) ) return fun; + throw new AssertionError("Missing function "+name); + } +} 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 `<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. 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("<ctor>") != 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()<Phase.Opto.ordinal() ) return TypeMem.BOT; - assert _publicEscapes!=null; - return _publicEscapes; - } - // --------------------------- // Very common nodes, cached here diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java index bc9c9d39..acd2eee5 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java +++ b/chapter29/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<<i); + } + return XInt.intern(foreign); + } + GlobalBits() { _local = RESERVED; // Reserved null-class bits are global identities and are never diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 0c37ce39..f841e75b 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -26,6 +26,9 @@ abstract public class Opto { // get a fairly precise set of Call Graph edges between CallNodes and // FunNodes. public static void opto(CodeGen code) { + int[] foreign = code._fidxs.foreign(); + for( int fidx : code._externFunc.keySet() ) foreign = XInt.make(foreign,fidx); + code._start._foreign = TypeMem.START.makeFrom(foreign,code._aliases.foreign()); // Reset Types before running the worklist algorithm Ary<Type> oldTypes = new Ary<>(Type.class); WorkList<Node> 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<nIns(); i++ ) + state = (TypeTuple)state.meet(in(i)._type); + return state; + } // Check for making a "C" call int externs = 0; @@ -98,7 +104,8 @@ public class CallEndNode extends CFGNode implements MultiNode { // C calls have no Return edges. Simple calls have an extra self // argument, so the two cannot be targets of the same valid call. assert externs==tfp.nfcns(); - return TypeTuple.make(Type.CONTROL,call.exposed(this),tfp.ret()); + TypeMem outside = CodeGen.CODE._start.outside(this).escapes(call.exposed(this)); + return TypeTuple.make(Type.CONTROL,outside,outside.outside(tfp.ret())); } // An unlinked target may have effects, so early conservative return. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/CallNode.java index 18be3488..552af499 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -100,7 +100,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<nIns()-1; i++ ) escaped = escaped.escapes(dep.addDepForwards(arg(i))._type); + TypeMem outside = CodeGen.CODE._start.outside(dep); + for( int i = 2; i<nIns()-1; i++ ) + escaped = escaped.escapesFrom(dep.addDepForwards(arg(i))._type,outside); return TypeMem.make(1,Type.BOTTOM,false,false,false,escaped._escFs,escaped._escAs); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index 47c8ecbe..b9fbc4d2 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -40,8 +40,15 @@ public class ConvertNode extends Node { Type src = val()._type; if( src.isHigh() ) return Type.TOP; if( src==Type.BOTTOM || src==TypeScalar.BOT ) return src; - if( _dst instanceof TypeMemPtr ptr ) return ptr.withPartial(TypeMemPtr.mayBePartial(src)); - if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; + if( _dst instanceof TypeMemPtr ptr ) { + // Assigning to a nullable field does not make a non-null value + // null. Keep this fact during SCCP, before idealize removes us. + // Shape/access still follow the declaration: switching between + // the entire source and destination types is not monotone. + if( src instanceof TypeMemPtr actual && actual.notNull() ) ptr = (TypeMemPtr)ptr.nonZero(); + return ptr.withPartial(TypeMemPtr.mayBePartial(src)); + } + if( src.isa(_dst) ) return src; return _dst; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index 02f08c19..f7a88df1 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -79,7 +79,7 @@ public class EscapeNode extends TypeNode { // Keep escapes from the actual private value before narrowing it to // the declaration. Selecting its Store from a MemMerge must preserve // this result, including Scalar.BOT's unknown pointer escapes. - TypeMem defaults = CodeGen.CODE.publicEscapes(); + TypeMem defaults = CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ? TypeMem.BOT : mpub; return TypeMem.make(fld._alias, t, false, false, fld._final, fidxes, aliases) .escapesFrom(tpriv,defaults).escapesFrom(t,defaults); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/FunNode.java index de32bea9..6422f7f1 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -97,6 +97,17 @@ public class FunNode extends RegionNode { // Signature can improve over time public TypeFunPtr sig() { return _sig; } + // A class function's hidden receiver defaults to its owning singleton. + // Keep PTR in the signature: it marks the hidden ABI slot and permits + // uniform call syntax, including callbacks forwarded by another class. + public Type defaultArg(int idx) { + Type t = sig().arg(idx); + if( idx!=0 || t!=TypePtr.PTR ) return t; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(TypeStruct.addClzPrefix(_compunit._cname)); + assert clz!=null; + return TypeMemPtr.make((byte)2,clz,true); + } + public void setSig( TypeFunPtr sig ) { assert sig.isa(_sig) || resolvesForwardSelf(sig,_sig); if( _sig != sig ) { diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java index d62152e5..caede11f 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -97,6 +97,13 @@ public class LoadNode extends MemOpNode { t = mem._alias==_alias ? mem._t : actual==null ? TypeScalar.BOT : actual._t; } else if( mem._alias==_alias ) t = t.join(mem._t); + if( !mem._one ) t = mem.outside(t); + // Store forwarding is also a value fact during SCCP. Waiting for the + // later rewrite can turn a known non-null stored pointer into a + // nullable declaration, then BOTTOM at the next dereference. + if( t instanceof TypeMemPtr && pfld._alias>1 && + find(mem(),ptr(),null,null,t) instanceof StoreNode st ) + t = addDepForwards(st.val())._type; // A deeply read-only base produces a deeply read-only value. The // generic declared field type must not cast this information away. @@ -225,38 +232,50 @@ public class LoadNode extends MemOpNode { // the unchanged loop memory, or a merge whose every arm folds. Null fails. // Register dependencies so a later pointer/offset rewrite retries the query. private Node find(Node mem, Node ptr, Node stop, BitSet visit) { + return find(mem,ptr,stop,visit,_type); + } + + private Node find(Node mem, Node ptr, Node stop, BitSet visit, Type expected) { ptr = address(ptr); - Field fld; - boolean external = ptr._type instanceof TypeMemPtr tmp && - (fld=tmp._obj.field(_name))!=null && fld._extern; + Field fld = ptr._type instanceof TypeMemPtr owner ? owner._obj.field(_name) : null; + int alias = fld==null ? _alias : fld._alias; + boolean external = fld!=null && fld._extern; while( mem!=null ) { addDep(mem); if( mem==stop ) return mem; switch( mem ) { - case MemMergeNode merge: mem=merge.alias(_alias); break; + case MemMergeNode merge: mem=merge.alias(alias); break; case StoreNode st: // Alias 1 is still unresolved, not a proven different field. if( st._alias==1 ) return null; addDep(st.ptr()); - if( _alias==st._alias && (ptr==address(st.ptr()) || ptr==address(st.nnptr())) && off()==st.off() ) { + if( alias==st._alias && (ptr==address(st.ptr()) || ptr==address(st.nnptr())) && + (!_name.equals("[]") && _name.equals(st._name) || off()==st.off() || + addDep(off())._type.isConstant() && off()._type==addDep(st.off())._type) ) { // Forwarding must preserve the pointer type already seen // by users: completion, read-only view, and recursive shape. // Open declarations can disagree until Opto upgrades them. - if( _type instanceof TypeMemPtr ) { + if( expected instanceof TypeMemPtr ) { Type value = addDep(st.val())._type; if( ptr()._type.isFinal() || declaredType().isFinal() ) value = value.makeRO(); - if( !value.isa(_type) ) return null; + if( !value.isa(expected) ) return null; } // A full-width load cannot narrow the forwarded value. if( declaredType() instanceof TypeInteger ti && ti.log_size()==3 && - !addDep(st.val())._type.isa(_type) ) return null; + !addDep(st.val())._type.isa(expected) ) return null; return st; } - if( (external || _alias==st._alias) && (external || !neverAlias(ptr,address(st.ptr()))) && + if( (external || alias==st._alias) && (external || !neverAlias(ptr,address(st.ptr()))) && !addDep(off())._type.join(addDep(st.off())._type).isHigh() ) return null; mem=st.mem(); break; case ProjNode proj: + if( proj._idx==1 && proj.in(0) instanceof CLInitNode init ) { + Node prior = init.pcopy(1,this); + if( prior==null ) return null; + mem = prior; + break; + } // New's memory is private; public memory is joined at Escape. if( external || !(proj.in(0) instanceof NewNode nnn) ) return null; if( declaredType()==Type.BOTTOM ) return null; @@ -310,6 +329,15 @@ public class LoadNode extends MemOpNode { // Type views preserve the address. Keep the actual Load pointer qualified // for compute/err; only alias comparisons see through these views. private Node address(Node ptr) { + // A pointer Load with a proven reaching Store denotes the stored + // address even before the later peephole replaces the Load itself. + if( ptr instanceof LoadNode ld && addDepForwards(ld)._type instanceof TypeMemPtr && + ld.ptr()._type instanceof TypeMemPtr base && base.notNull() && ld.err()==null && + ld.find(ld.mem(),ld.ptr(),null,null) instanceof StoreNode st ) + ptr = addDepForwards(st.val()); + if( ptr instanceof ConvertNode conv && addDep(conv.val())._type instanceof TypeMemPtr src && + src.isa(addDep(conv)._type) && src.accessISA(conv._type) ) + ptr = conv.val(); while( ptr instanceof ReadOnlyNode || ptr instanceof ConstructNode con && con._partial ) { addDep(ptr); ptr = ptr.in(1); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 9c40c75d..1b7aded1 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -78,7 +78,12 @@ public class ParmNode extends PhiNode { if( ctrl != Type.XCONTROL && ctrl != Type.TOP ) { if( in(i)._type==Type.BOTTOM ) return Type.BOTTOM; - t = t.meet(in(i)._type); + Type arg = in(i)._type; + // The unknown-caller callback input is Start's memory + // projection, interpreted using this parameter's signature. + if( i==1 && r.in(i) instanceof StartNode && _idx>1 && arg instanceof TypeMem outside ) + arg = outside.outside(_declaredType); + t = t.meet(arg); } } // Recursion is a loop in disguise. A Parm merges the first argument diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/StartNode.java index 78bd8219..36583884 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -26,6 +26,9 @@ import java.util.HashSet; public class StartNode extends LoopNode implements MultiNode { final Type _arg; + // Immutable foreign identity seed, installed with Opto's reset. Actual + // local escapes arrive through Stop, not through a frozen public list. + public TypeMem _foreign = TypeMem.START; public StartNode(StartNode start, StopNode stop, Type arg) { super(null,start,stop); _arg = arg; } public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; } @@ -67,12 +70,22 @@ public class StartNode extends LoopNode implements MultiNode { TypeMem tmem = stop._type instanceof TypeTuple tt ? tt.mem() : stop._type.isHigh() ? TypeMem.START : TypeMem.BOT; + if( !(this instanceof StartCUNode) ) tmem = tmem.escapes(_foreign); + else if( in(0) instanceof StartNode start ) tmem = tmem.escapes(start.outside(this)); assert tmem._alias==1 && !tmem._one; return TypeTuple.make(Type.CONTROL,tmem,_arg); } @Override public Node idealize() { return null; } + // Consumers register against the value they read, even when their Call's + // control remains unchanged as more identities escape. + public TypeMem outside(Node dep) { + if( CodeGen.CODE._phase==null || CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ) return TypeMem.BOT; + Type t = dep.addDepForwards(this)._type; + return t instanceof TypeTuple tt ? tt.mem() : t.isHigh() ? _foreign : TypeMem.BOT; + } + // No immediate dominator, and idepth==0 @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index 8a554390..ead635dd 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -79,7 +79,7 @@ public class StopCUNode extends StopNode { // Capture (precisely?) all escaping pointer aliases and fidxs. // Escaped fidxs means the linked world can call that function; // escaped aliases means the linked world can R/W those aliases. - xmem = xmem.escapes(tret.ret()); + xmem = xmem.escapesFrom(tret.ret(),start.outside(this)); xmem = (TypeMem)xmem.meet(tret.mem()); } } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 4114b47c..2574d801 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -98,6 +98,7 @@ public class StoreNode extends MemOpNode { // that field again; retain the declared signature instead of unfolding // successively sharper copies of its private-memory return type. if( mem._one && decl instanceof TypeFunPtr && val instanceof TypeFunPtr ) val = decl; + TypeMem outside = TypeMem.opaque(val) ? CodeGen.CODE._start.outside(this) : TypeMem.BOT; // A singleton class's final constant field lives in the static image. // Its precise memory slice is a constant too; ordinary peepholes can // replace this Store before scheduling or instruction selection. @@ -110,14 +111,14 @@ public class StoreNode extends MemOpNode { // This singleton slice contains just the stored value. Copying // bulk memory's escapes would freeze a transient FULL bound into // the constant, permanently exposing unrelated private functions. - return TypeMem.make(_alias,val,true,true,true,null,null).escapesFrom(val); + return TypeMem.make(_alias,val,true,true,true,null,null).escapesFrom(val,outside); // Allocation uses a private TypeMem and nothing else does. This // memory is truly private; a temporary singleton until it escapes - // which is never does in a constructor. if( !_name.equals("[]") && mem._one ) // Just track the stored value - return TypeMem.make(_alias,val,true,false,fld==null ? _init : fld._final,null,null).escapesFrom(val); + return TypeMem.make(_alias,val,true,false,fld==null ? _init : fld._final,null,null).escapesFrom(val,outside); // Normal aliasing Store. assert mem._alias==1 || mem._alias==_alias; // Perfect aliasing @@ -132,7 +133,7 @@ public class StoreNode extends MemOpNode { // Bulk memory's final bit describes its conservative remainder, not // this newly precise slice. Slice finality comes from the field. boolean xfinal = fld != null && fld._final; - return TypeMem.make(_alias,t,mem._one,mem._clz,xfinal,mem._escFs,mem._escAs).escapesFrom(val); + return TypeMem.make(_alias,t,mem._one,mem._clz,xfinal,mem._escFs,mem._escAs).escapesFrom(val,outside); } @Override diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/SummaryNode.java index c22b4bdd..483aab89 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/SummaryNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/SummaryNode.java @@ -26,7 +26,8 @@ public class SummaryNode extends CFGNode implements MultiNode { // A library summary does not forget escapes already present in the caller. TypeMem mem = in(1)._type instanceof TypeMem m ? m : in(1)._type.isHigh() ? TypeMem.TOP : TypeMem.BOT; mem = (TypeMem)mem.meet(_state.mem()); - for( int i = 2; i<nIns(); i++ ) mem=mem.escapes(in(i)._type); + TypeMem outside = CodeGen.CODE._start.outside(this); + for( int i = 2; i<nIns(); i++ ) mem = mem.escapesFrom(in(i)._type,outside); return TypeTuple.make(_state.ctl(),mem,_state.ret()); } @Override public Node idealize() { return null; } @@ -34,7 +35,8 @@ public class SummaryNode extends CFGNode implements MultiNode { dep.addDepForwards(this); if( dep.addDepForwards(in(0))._type.isHigh() ) return TypeMem.START; TypeMem mem = (TypeMem)_state.mem(); - for( int i = 2; i<nIns(); i++ ) mem=mem.escapes(dep.addDepForwards(in(i))._type); + TypeMem outside = CodeGen.CODE._start.outside(dep); + for( int i = 2; i<nIns(); i++ ) mem = mem.escapesFrom(dep.addDepForwards(in(i))._type,outside); return TypeMem.make(1,Type.BOTTOM,false,false,false,mem._escFs,mem._escAs); } @Override boolean _upgradeType(HashMap<String,Type> types) { diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java index 50775349..5dd66730 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java @@ -291,7 +291,7 @@ final class Functions { for( int i = 0; i<ids.length; i++ ) { Type t = sig.arg(i); // Args take a default input if called from Start/external-world - Node parm = new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(t).peephole()).peephole(); + Node parm = new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(fun.defaultArg(i)).peephole()).peephole(); if( t instanceof TypeMemPtr ptr && ptr._partial ) parm = new ConstructNode(parm).peephole(); P._scope.define(ids[i], t, (i==0 && ids[0]=="self") || (finals!=null && finals.get(i)), parm, loc); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java index 3cb474b1..ffd3a0f4 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java @@ -146,8 +146,8 @@ final class Types { Type t0 = parseType(); // Either return or first arg if( t0==null ) return P.posT(old); // Not a function Ary<Type> ts = new Ary<>(Type.class); - // Always reserve a receiver slot. Outside constructor scopes it is - // broad and unused, so call sites can uniformly pass their self. + // Always reserve a receiver slot. Outside constructor scopes the + // broad signature also marks the hidden slot for the machine ABI. ts.push(implicitSelfType()); if( P.match("}") ) // No-arg function { -> type } return TypeFunPtr.make(P.match("?"),ts.asAry(),t0); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter29/src/main/java/com/seaofnodes/simple/type/Type.java index 6c8a3e8d..0f655f49 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/Type.java @@ -623,11 +623,12 @@ public class Type /*implements Cloneable*/ { private static int[] remapBits(GlobalBits fileBits, GlobalBits bits, int[] fileLocals, int firstMapped ) { if( fileLocals == XInt.EMPTY || fileLocals == XInt.FULL ) return fileLocals; - assert !XInt.isHigh(fileLocals); + boolean complement = XInt.isHigh(fileLocals); + if( complement ) fileLocals = XInt.dual(fileLocals); int[] locals = XInt.EMPTY; for( int fileLocal = XInt.next(fileLocals,-1); fileLocal >=0; fileLocal = XInt.next(fileLocals,fileLocal) ) locals = XInt.make(locals,fileLocal < firstMapped ? fileLocal : bits.map(fileBits,fileLocal)); - return locals; + return complement ? XInt.dual(locals) : locals; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 56f47bff..19ec5019 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -79,6 +79,10 @@ public class TypeFunPtr extends TypeNil { @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } public TypeFunPtr makeFrom( int fidx ) { return make1(_nil,_open,_sig,_ret,fidx); } + public TypeFunPtr restrictFIDXs(int[] fidxs) { + int[] ids = XInt.dual(XInt.meet(XInt.dual(_fidxs),XInt.dual(fidxs))); + return ids==_fidxs ? this : make(_nil,_open,_sig,_ret,ids); + } public TypeFunPtr makeFrom( Type arg, int idx ) { // Alter named arg Type[] sig = _sig.clone(); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 79543e56..5faa7107 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -104,15 +104,24 @@ public class TypeMem extends Type { // private definitions here. The caller supplies FULL until local forward // types are resolved. Ordinary unknown values still require FULL. public TypeMem escapesFrom(Type t, TypeMem defaults) { - TypeStruct ts = t instanceof TypeMemPtr ptr ? ptr._obj : t instanceof TypeStruct obj ? obj : null; - if( ts!=null && ts._open && ts._fref && !ts.isAry() ) + if( opaque(t) ) return makeFrom(XInt.meet(_escFs,defaults._escFs),XInt.meet(_escAs,defaults._escAs)); return escapesFrom(t); } + public static boolean opaque(Type t) { + TypeStruct ts = t instanceof TypeMemPtr ptr ? ptr._obj : t instanceof TypeStruct obj ? obj : null; + return ts!=null && ts._open && ts._fref && !ts.isAry(); + } public TypeMem escapesAliases(Type t) { return make(_alias,_t,_one,_clz,_final, _escFs, escapeAlias(_escAs,t)); } + // A value supplied by the outside world, bounded by its declared family. + // Foreign identities remain possible even when no local function escapes. + public Type outside(Type declared) { + return declared instanceof TypeFunPtr fun ? fun.restrictFIDXs(_escFs) : declared; + } + public static final TypeMem TOP = make(1, Type.TOP ,true ,true, true , XInt.EMPTY, XInt.EMPTY); public static final TypeMem BOT = make(1, Type.BOTTOM,false,false,true , XInt.FULL , XInt.FULL ); public static final TypeMem START= make(1,Type.BOTTOM,false,false,false, XInt.EMPTY, XInt.EMPTY); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index d699e365..7c9758bd 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -99,7 +99,7 @@ public class TypeStruct extends Type { maxAlias = Math.max(maxAlias,f._alias); int len = XInt.idx(maxAlias)+1; if( (maxAlias&31)==31 ) len++; - int[] xs = XInt.free(len); + int[] xs = XInt.alloc(len); for( Field f : _fields ) if( f._fname.charAt(0) != '_' && // Skip private fields. !hiddenInit(f) && // Skip private allocation helper. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/type/XInt.java b/chapter29/src/main/java/com/seaofnodes/simple/type/XInt.java index 3e74df84..06c9d466 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/XInt.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -92,7 +92,7 @@ public abstract class XInt { int len = Math.max(xs.length,idx+1); if( (x&31)==31 && idx+1==len ) len++; - int[] ys = free(len); + int[] ys = alloc(len); System.arraycopy(xs,1,ys,1,xs.length-1); ys[idx] |= mask(x); return intern(ys); @@ -112,7 +112,7 @@ public abstract class XInt { len--; // Replace with trimmed if( len < xs.length ) { - var ys = free(len); + var ys = alloc(len); System.arraycopy(xs,1,ys,1,len-1); xs = _free(xs,ys); } @@ -146,8 +146,9 @@ public abstract class XInt { FREES.setX(len, xss = new Ary<>(int[].class)); return xss; } - // Pull free array from free list - static int[] free(int len) { + // Allocate a zeroed mutable array, reusing the free list. + // Pass it to intern after filling; do not retain a mutable reference. + public static int[] alloc(int len) { int[] xs = _xss(len).pop(); if( xs==null ) { NEWS++; xs = new int[len]; } @@ -176,7 +177,7 @@ public abstract class XInt { if( isX ) return xs; if( isY ) return ys; // Get a free one - int[] ms = free(max); + int[] ms = alloc(max); for( int i=1; i<min; i++ ) ms[i] = xs[i] | ys[i]; for( int i=min; i<ms.length; i++ ) { @@ -189,7 +190,7 @@ public abstract class XInt { // Dual: flip all the bits public static int[] dual(int[] xs) { - int[] ds = free(xs.length); + int[] ds = alloc(xs.length); for( int i=1; i<xs.length; i++ ) ds[i] = ~xs[i]; return intern(ds); @@ -203,7 +204,7 @@ public abstract class XInt { } public static int[] packed(BAOS bais) { int len = bais.packed1(); - int[] xs = free(len); + int[] xs = alloc(len); for( int i=1; i<len; i++ ) xs[i] = bais.packed4(); return intern(xs); @@ -230,7 +231,7 @@ public abstract class XInt { public static int[] remap( int[] xs, AryInt map ) { if( xs==FULL ) return xs; assert !isHigh(xs); - int[] ys = free(xs.length); + int[] ys = alloc(xs.length); for( int bit = next(xs,0); bit >=0; bit = next(xs,bit) ) { int bat = map.at(bit); ys[idx(bat)] |= mask(bat); diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 6cf92dc3..f5eb2b36 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -242,13 +242,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -256,11 +249,19 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + """; - // The implicit return exposes _hashCodeString, so retain its body too. - testCPU(src,"x86_64_v2", "SystemV",21,null); - testCPU(src,"riscv" , "SystemV",9,null); - testCPU(src,"arm" , "SystemV",7,null); + // Return the public hashCode wrapper; keep its helper private. + testCPU(src,"x86_64_v2", "SystemV",12,null); + testCPU(src,"riscv" , "SystemV",8,null); + testCPU(src,"arm" , "SystemV",6,null); } @Test diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter21Test.java index f1dc54e2..e15c2581 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -368,13 +368,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -382,11 +375,18 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; """; - // The implicit return exposes _hashCodeString, so retain its body too. - testCPU(src,"x86_64_v2", "SystemV",21,null); - testCPU(src,"riscv" , "SystemV",9,null); - testCPU(src,"arm" , "SystemV",7,null); + // Return the public hashCode wrapper; keep its helper private. + testCPU(src,"x86_64_v2", "SystemV",12,null); + testCPU(src,"riscv" , "SystemV",8,null); + testCPU(src,"arm" , "SystemV",6,null); } @Test public void testStringExport() throws IOException { @@ -408,13 +408,6 @@ val equals = { !String !self, !String s -> return true; }; -// Return the String hashCode (cached, and never 0) -val hashCode = { !String self -> - self._hashCode - ? self._hashCode - : (self._hashCode = _hashCodeString(self)); -}; - val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) @@ -422,8 +415,15 @@ val _hashCodeString = { !String self -> if( !hash ) hash = 123456789; return hash; }; + +// Return the String hashCode (cached, and never 0) +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; """; - TestC.runC(src, "stringHash", "",21); + TestC.runC(src, "stringHash", "",12); } @Test public void testLoop2() { diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter25Test.java index f5eba8f5..5f615282 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -5,6 +5,7 @@ import com.seaofnodes.isa.eval.EvalRisc5; import com.seaofnodes.isa.eval.EvalArm64; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.ElfReader; import com.seaofnodes.simple.codegen.ParseAll; @@ -12,6 +13,8 @@ import com.seaofnodes.simple.node.CallNode; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.LoopNode; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeTuple; import com.seaofnodes.simple.type.XInt; import com.seaofnodes.simple.util.Ary; import java.io.File; @@ -73,21 +76,25 @@ public class Chapter25Test { for( long seed : new long[]{1,123,987654321} ) { CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.Parse); FunNode visible = null; + int[] privateFidxs = XInt.EMPTY; int checked = 0; for( FunNode fun : code._linker ) { if( fun==null || fun._name==null ) continue; if( fun._name.equals("visible") ) { - assertTrue(code.publicFIDX(fun.sig().fidx())); visible = fun; checked++; } if( fun._name.equals("_hidden") || fun._name.equals("hiddenClassMethod") ) { - assertFalse(code.publicFIDX(fun.sig().fidx())); + privateFidxs = XInt.make(privateFidxs,fun.sig().fidx()); checked++; } } assertEquals(3,checked); code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(XInt.bit(outside._escFs,visible.sig().fidx())); + for( int fidx = XInt.next(privateFidxs,0); fidx>=0; fidx = XInt.next(privateFidxs,fidx) ) + assertFalse(XInt.bit(outside._escFs,fidx)); assertTrue(visible.unknownCallers()); assertEquals(TypeInteger.U8,visible.parm(3)._type); assertEquals("0",Eval2.eval(code,0)); @@ -101,25 +108,52 @@ public class Chapter25Test { val _private = { int x -> x+1; }; return 0; """).parse(); - int checked = 0; + int published = -1, unpublished = -1; for( FunNode fun : code._linker ) { if( fun==null || fun._name==null ) continue; - if( fun._name.equals("_hidden") ) { - // A public field can publish a privately named function. - assertTrue(code.publicFIDX(fun.sig().fidx())); - checked++; - } - if( fun._name.equals("_private") ) { - assertFalse(code.publicFIDX(fun.sig().fidx())); - checked++; - } + if( fun._name.equals("_hidden") ) published = fun.sig().fidx(); + if( fun._name.equals("_private") ) unpublished = fun.sig().fidx(); } - assertEquals(2,checked); + assertTrue(published>=0 && unpublished>=0); var clz = code.compunit()._clz; - assertTrue(XInt.bit(code.publicAliases(),clz.field("visible")._alias)); - assertFalse(XInt.bit(code.publicAliases(),clz.field("_hidden")._alias)); - assertFalse(XInt.bit(code.publicAliases(),clz.field("_private")._alias)); code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + // A public field can publish a privately named function. + assertTrue(XInt.bit(outside._escFs,published)); + assertFalse(XInt.bit(outside._escFs,unpublished)); + assertTrue(XInt.bit(outside._escAs,clz.field("visible")._alias)); + assertFalse(XInt.bit(outside._escAs,clz.field("_hidden")._alias)); + assertFalse(XInt.bit(outside._escAs,clz.field("_private")._alias)); + } + + @Test public void testImportedEscapeExclusions() throws IOException { + Path build=Path.of("build/objs"); + Files.createDirectories(build); + Path dir=Files.createTempDirectory(build,"escape_exclusions_"); + CodeGen library=new CodeGen(null,dir.toString(),null,"Lib",""" + val _hidden_noInline={int n -> n+100;}; + val apply_noInline={{int->int} f,int n -> f(n);}; + return apply_noInline; + """,123,true,TypeInteger.BOT).driver("x86_64_v2","win64",false,false); + int savedHidden=((com.seaofnodes.simple.type.TypeFunPtr) + library.compunit()._clz.field("_hidden_noInline")._t).fidx(); + // Allocate unrelated IDs before loading Lib so saved exclusions must + // remap by owner/slot, not by their numeric positions in the file. + CodeGen code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Client",""" + val _other={int n -> n-1;}; + val inc={int n -> n+1;}; + return Lib.apply_noInline(inc,arg); + """,987654321,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + var clz=(com.seaofnodes.simple.type.TypeStruct)Parser.TYPES.get("class:Lib"); + int hidden=((com.seaofnodes.simple.type.TypeFunPtr)clz.field("_hidden_noInline")._t).fidx(); + assertNotEquals(savedHidden,hidden); + TypeMem outside=((TypeTuple)code._start._type).mem(); + assertTrue(XInt.isHigh(outside._escFs)); + assertFalse(XInt.bit(outside._escFs,hidden)); + assertEquals("42",Eval2.eval(code,41)); + Files.delete(dir.resolve("Lib.o")); + Files.delete(dir); } @Test public void testNeverReturnPointerRiscV() { diff --git a/chapter29/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java index 88ebb6b7..dae64fb0 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java @@ -158,6 +158,28 @@ public class ClassInitDependenciesTest { assertTrue(touches(code,deps,"Root/B","Root")); } + @Test public void testUnknownCallbackCycle() throws Exception { + for( long seed : new long[]{1,123,987654321} ) { + try { + compile("A",Map.of( + "A", """ + { {int->int} -> {int->int} } bounce="C"; + val callback_noInline={int n -> B.value;}; + val f=bounce(callback_noInline); + int value=f(1); + """, + "B", "int value=A.value;"),seed); + fail("Expected callback initialization cycle"); + } catch( Parser.ParseException ex ) { + String message=ex.getMessage(); + assertTrue(message,message.startsWith("Cyclic class initialization:")); + assertTrue(message,message.contains(" -> unknown call")); + assertTrue(message,message.contains("unknown call -> ")); + assertTrue(message,message.contains("Root.B -> Root.A")); + } + } + } + @Test public void testCycles() throws Exception { cycle("A",Map.of("A","val get_noInline={ ->\n B.value;\n};\nint value=get_noInline();", "B","int value=A.value;"),"A -> B -> A"); diff --git a/chapter29/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java b/chapter29/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java new file mode 100644 index 00000000..71a281b5 --- /dev/null +++ b/chapter29/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java @@ -0,0 +1,112 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class EscapeFlowTest { + // A cofinite outside set must not revive private allocation helpers. + @Test public void testOpaqueRoundTrip() { + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(""" + struct _A { B? !b; new _A = { B? p -> b=p; }; }; + val wrap = { B? b -> return new _A(b); }; + return wrap; + """,seed,true).driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(XInt.isHigh(outside._escFs)); + assertNotSame(XInt.FULL,outside._escFs); + for( FunNode fun : code._linker ) + if( fun!=null && fun._name!=null && fun._name.contains("_A.") ) + assertFalse(fun._name,fun.unknownCallers()); + } + } + + // Foreign callbacks remain possible. The default callback argument reads + // Start memory rather than a frozen declaration constant. + @Test public void testUnknownCallerCallback() { + CodeGen code = new CodeGen(""" + val _hidden_noInline = { int n -> return n+2; }; + val apply_noInline = { {int->int} f,int n -> return f(n); }; + return apply_noInline; + """).parse(); + TypeMemPtr self = (TypeMemPtr)named(code,"apply_noInline").parm(2).in(1)._type; + assertTrue(self._one); + assertEquals("class:Test",self._obj._name); + code.driver(CodeGen.Phase.TypeCheck); + FunNode apply = named(code,"apply_noInline"); + assertTrue(apply.unknownCallers()); + ParmNode callback = apply.parm(3); + assertTrue(callback.in(1) instanceof ProjNode); + TypeFunPtr type = (TypeFunPtr)callback._type; + assertTrue(XInt.isHigh(type.fidxs())); + assertSame(TypeInteger.BOT,apply.ret().expr()._type); + // Only <clinit> and apply escape; forwarding #self must not expose _hidden. + assertEquals("Stop[ return { apply_noInline}; return #2; ]",code.print()); + } + + @Test public void testNativeCallbackRoundTrip() { + CodeGen code = new CodeGen(""" + val _callback_noInline = { int n -> return n+1; }; + { {int->int} -> {int->int} } bounce = "C"; + return bounce(_callback_noInline)(arg); + """).driver(CodeGen.Phase.TypeCheck); + FunNode callback = named(code,"_callback_noInline"); + assertTrue(callback.unknownCallers()); + assertTrue(XInt.bit(((TypeTuple)code._start._type).mem()._escFs,callback.sig().fidx())); + } + + // Call remains CONTROL. Changing only the outside set must wake CallEnd + // and extend the possible callback returned by the native factory. + @Test public void testOutsideReturnDependency() { + CodeGen code = new CodeGen("return 0;").parse(); + code._phase = CodeGen.Phase.Opto; + code.externFunc(100,"factory"); + TypeFunPtr callback = TypeFunPtr.make(false,TypeFunPtr.TEMPTY,TypeInteger.BOT); + TypeFunPtr factory = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,callback,100); + CallNode call = new CallNode(null,ConstantNode.raw(Type.CONTROL), + ConstantNode.raw(TypeMem.START),ConstantNode.raw(factory)).init(); + CallEndNode end = new CallEndNode(call,TypeRPC.BOT); + int[] foreign = XInt.dual(XInt.make(7)); + code._start._type = TypeTuple.make(Type.CONTROL,TypeMem.START.makeFrom(foreign,XInt.EMPTY),TypeInteger.BOT); + TypeTuple before = (TypeTuple)end.compute(); + assertFalse(XInt.bit(((TypeFunPtr)before.ret()).fidxs(),7)); + boolean depends = false; + for( int i = 0; i<code._start.nDeps(); i++ ) depends |= code._start.dep(i)==end; + assertTrue(depends); + code._start._type = TypeTuple.make(Type.CONTROL,TypeMem.START.makeFrom(XInt.FULL,XInt.EMPTY),TypeInteger.BOT); + TypeTuple after = (TypeTuple)end.compute(); + assertTrue(before.isa(after)); + assertTrue(XInt.bit(((TypeFunPtr)after.ret()).fidxs(),7)); + } + + // Public construction exposes the allocator; private-memory helpers + // remain internal and can inline into it. + @Test public void testPublicAllocator() { + CodeGen code = new CodeGen(""" + struct Box { int n; new Box = { int x -> n=x; }; }; + return new Box(arg).n; + """).parse(); + FunNode allocator = named(code,"Test.Box.<new>"); + int[] helpers = XInt.EMPTY; + for( FunNode fun : code._linker ) + if( fun!=null && fun.sig().ret() instanceof TypeMem ) + helpers = XInt.make(helpers,fun.sig().fidx()); + assertNotSame(XInt.EMPTY,helpers); + code.driver(CodeGen.Phase.TypeCheck); + TypeMem outside = ((TypeTuple)code._start._type).mem(); + assertTrue(allocator.unknownCallers()); + assertTrue(XInt.bit(outside._escFs,allocator.sig().fidx())); + for( int fidx = XInt.next(helpers,0); fidx>=0; fidx = XInt.next(helpers,fidx) ) + assertFalse(XInt.bit(outside._escFs,fidx)); + assertEquals("42",Eval2.eval(code,42)); + } + + private static FunNode named(CodeGen code, String name) { + for( FunNode fun : code._linker ) + if( fun!=null && name.equals(fun._name) ) return fun; + throw new AssertionError("Missing function "+name); + } +} diff --git a/docs/roadmap.md b/docs/roadmap.md index 81bb8abb..0fa3933b 100644 --- a/docs/roadmap.md +++ b/docs/roadmap.md @@ -40,8 +40,15 @@ Remaining work: object should cost only for that graph and any affected existing nodes. - Make `GlobalEscapeNode`'s shared call/summary scan incremental. Compilation unit Stops now reuse its result, but updating that result still scans all - calls and unloaded summaries. Review the phase-dependent escape normalization - and reliance on the previous result before changing propagation further. + calls and unloaded summaries. Handle contributors changing or disappearing, + rather than only accumulating unions. The + [outside-world escape flow](../chapter29/docs/escape-flow.md), now in + Chapters 28a/28b/29, has removed the + frozen public inventory and previous-result escape normalization; the shared + scan remains. +- Improve precision for identities discovered after Opto's foreign seed is + established. They currently remain in the cofinite foreign tail. Preserve + monotone propagation and imported callback behavior when refining this bound. Whole-program TypeCheck is acceptable for now; incremental checking is an optional later improvement. Expensive assertion walks are outside this diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index ac3b1c5a..bd68060a 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -18,7 +18,100 @@ The [incremental build design](incremental-builds.md) expands the roadmap's dependency and output-ownership requirements. For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.md). -## Current workspace (2026-11-02) +## Restart handoff (2026-11-06) + +Cliff requested this handoff before restarting. Active branch is `escape-flow`, +tracking `origin/escape-flow`; HEAD is `8f460340c`. `ch29-cleanup` was previously +fast-forwarded into local `main`, then this branch was created. The escape-flow +implementation is still **uncommitted and unstaged**. Preserve all working-tree +changes, including untracked `chapter29/docs/escape-flow.md` and +`chapter29/src/test/java/com/seaofnodes/simple/EscapeFlowTest.java`. No commit, +push, or chapter split is currently requested. Cliff thinks this may deserve +its own chapter; keep working in Chapter29 until that decision is made. + +Read [the escape-flow design](../chapter29/docs/escape-flow.md) first. It is the +current account; the later sections of deferred-construction.md retain older +failed experiments and are explicitly superseded. The implementation is a +tested first pass, not a claim that all outside-value precision is solved. + +Important implementation choices for review/resumption: + +- The frozen public function/alias inventory and `freezePublicInterface` have + been removed. Public-method and public-alias tests now check the converged + Start escape sets, including private exclusions. +- Cliff requested the escape-flow backport to 28a/28b. Both now use the same + outside-value bounds and singleton hidden-receiver defaults. Keep their + existing parser and construction model. 28a retains its initializer roots + through lowering and uses LocalIds; 28b remaps cofinite saved escape sets. +- `GlobalBits.foreign()` builds the complement of registered owned identities; + Opto installs it on outer Start, adding known native function IDs. StartCU + merges the shared outside state. Infinite sets must preserve local exclusions. +- Callback default Parms use Start's existing memory Proj, interpreted through + their declared signature. Other scalar defaults remain constants. CallEnd + reads Start with `addDepForwards`, because changes to escapes need not change + Call's CONTROL type. No new CallEnd slot or synthetic Fun/Return was added. +- An infinite call uses the outside continuation. Do not directly link every + same-arity local function: incompatible parameter/result families caused + generic-scalar errors in imported callback tests during that experiment. +- CLInit depends on its initializer Return. It must wait when incoming memory + is high; otherwise SCCP can lift from START back to TOP. Lowering computes the + linked replacement CallEnd type before constructing its output projections. +- Convert keeps input non-nullness, not the entire source pointer type: the + latter failed ConvertNodeTest.testMonotoneCompute. Load reuses its forwarding + search during compute; resolved named-field aliases and already-bypassed + CLInit memory must work before post-SCCP rewrites/layout. + +The hidden class receiver default is now the owning class singleton, supplied +by `FunNode.defaultArg` during parsing and when Opto reconnects unknown callers. +Keep TypePtr.PTR in the signature: backends recognize it as the hidden ABI +slot, and callback annotations must not acquire the annotating class's receiver +type. Explicit calls still pass their actual receiver. The printed-IR assertion +in EscapeFlowTest.testUnknownCallerCallback now proves that only `<clinit>` and +`apply_noInline` escape, excluding `_hidden_noInline`. A private local +object/callback merge can also have an abstract pointer type, so do not cap +arbitrary TypePtr values at outside escapes. + +Validation saved under ignored `build/`: + +- `xint-alloc-build.log` and `xint-alloc-chapter*.log`: all five XInt chapters + (26/27/28a/28b/29) rebuild; 134 focused type, escape, module, and import tests + pass after renaming the pooled allocator to `XInt.alloc` and using it for + the three foreign-set builders. It returns zeroed mutable storage to fill + and pass to `intern`; `_free` still returns storage to the pool. +- `escape-string-reorder-final.log`: full 28a/28b/29 suites pass after the + String declaration reorder and measured spill expectations (538/578/601 + active tests), plus shared printer and ISA checks. +- `escape-backport-final.log`: combined full Make run for 28a/28b/29, + respectively 538/578/601 active tests pass with assertions, plus shared + printer and ISA checks. Added allocator, unknown-callback cycle, and saved + private-function exclusion coverage. Destination baselines are recorded in + `escape-backport-baseline.log` (531 in 28a, 571 in 28b). +- `remove-public-interface-tests.log`: full Chapter29 `make -k tests CTAGS=`, + all 598 active tests pass after removing the frozen public-interface inventory + and moving its test coverage to the converged escape sets. +- `class-self-default-tests.log`: full Chapter29 `make -k tests CTAGS=`, all + 598 active tests pass after sharpening the hidden receiver default, including + the retained escape-exclusion assertion. No printed-IR golden changed. +- `escape-flow-complete.log`: full Chapter29 `make -k tests`, all 598 active + tests pass with assertions (404 raw0, 38 raw1, 13 standalone, 29 system, + 1 fuzzer, 113 aggregate). +- `escape-flow-last-check.log`: 26 tests pass after the final small CLInit guard + cleanup: ClassInitDependenciesTest, ConvertNodeTest, EscapeFlowTest. +- `EscapeSeeds.java` / `.class`: four recursive programs across four worklist + seeds, 16 checks pass against unchanged expected IR. Sources are in + `build/remaining-failures/*.smp`. The four are Chapter12 testCoRecur, + testCoRecur2, testCoRecur3, and testPrivateRecursiveReturn. +- `EscapeLoads.java` and `OutsideCallback.java` are disposable diagnostic + harnesses; `escape-flow-*.log` includes intermediate failures. Use the final + logs above, not an earlier trial, as the validation baseline. + +Run Make from `chapter29`; use the existing JUnit classpath +`build/classes/main;build/classes/test;lib/*`. No tests/JVMs are left running. +Do not recreate tmp/* experiment directories. No new whole-IR passes, side IR, +IterPeeps escape-repair hooks, or relaxed goldens were introduced. There is no +need to rerun unchanged checks merely because the conversation restarted. + +## Current workspace (2026-11-06) Chapter 29 is **Tech Debt Cleanup**. Cliff approved keeping the parser split and moving it into this new snapshot; continue parser work there. Chapter 28b @@ -86,23 +179,25 @@ woken when a linker mapping is installed. FldOffNode's data base belongs in slot 1, not control slot 0; otherwise inliner body discovery can exclude an unresolved field offset. -The FULL-escape experiment is not yet at test parity: the latest run passes -590/594 tests (raw0 400/404). Chapter10 `testIfOrNull` is restored to its valid -original `return bar;` and runs TypeCheck. Both Chapter17b forward tests now pass -their original goldens: EscapeNode uses cached public FIDX and alias defaults -for opaque external types, preserving prior input escapes. Before Opto installs -closed IR types, the default remains FULL; only open `_fref` structs get the -narrower fallback afterwards. Ordinary unknown values still require FULL. -The four remaining failing programs pass TypeCheck but retain extra private -constructors. In -`Chapter12Test.testPrivateRecursiveReturn`, SCCP gives the root Return BOTTOM -and FULL escapes. Post-SCCP forwarding fixes its value to `_B`, but FULL persists -through Start's incoming-memory cycle. Do not bless those extra functions in -the goldens or restore the nonmonotone public-only cap. The details and failing -test names are in `chapter29/docs/deferred-construction.md`. Its escape audit -also records concrete opaque Store/Return/native-argument precision losses, -CLInit's unconditional worst-case effects, and unknown CallEnd effects. Do not -blindly cap these at public sets: explicit private escapes must survive. +On branch `escape-flow`, Chapter29 uses a cofinite foreign-identity seed on +Start and discovers local escapes through the Start/Stop cycle. Frozen public +sets have been removed; tests check converged escape sets. Callback defaults read +Start's memory projection; unknown/native CallEnds depend directly on Start. +Opaque external values use the dynamic bound; arbitrary local unknowns still +require FULL. Cofinite linking honors exclusions; serialization remaps them. +CLInit reads its initializer Return's effects and preserves those effects when +lowering to a linked CallEnd. Do not restore unconditional MemBot there. + +All four recursive-class goldens now pass unchanged. Convert retains non-null +pointer facts during compute without conditionally returning the whole source +shape (which is nonmonotone). Load reuses its Store-forwarding search during +compute, including resolved field names and bypassed CLInit memory. The change +adds no whole-program pass. Hidden class `#self` defaults to its owning +singleton while the signature retains the generic hidden ABI slot. Do not +globally cap abstract local values at the outside bound. +See `chapter29/docs/escape-flow.md` for the design and remaining limitations. +The full Chapter29 suite passes 601 active tests with assertions; the 28a/28b +backports pass 538/578 active tests respectively. Incomplete references now have only a yes/no restriction. Constructor self and `C ^arg` / `C? ^arg` are incomplete; a new result is incomplete iff an actual @@ -345,8 +440,10 @@ and a small game with graphics, keyboard input, and sound. Precise alias recovery can still be deferred. See `chapter28a/README.md`. Runtime lowering is implemented above; argument arrays remain deferred. Public function fields on instances of public classes must retain Start, just like class-object - fields. publicFIDX now checks both; this fixes sys.scan.match losing Start - while building sys.o and subsequently widening after import. + fields. The earlier publicFIDX check covered both, fixing sys.scan.match + losing Start while building sys.o and subsequently widening after import. + Chapter29 now derives that reachability from Start/Stop escape flow instead + of a frozen public-interface inventory. Do not weaken assertions or reset imported types to conceal incorrect public classification. Future optimization: move final, always-constant instance fields to the class @@ -398,6 +495,24 @@ and a small game with graphics, keyboard input, and sound. ## Tutorial backports +- The escape-flow replacement is backported to 28a/28b at Cliff's request. + LocalIds supplies the foreign seed in 28a; GlobalBits remaps finite exclusions + in 28b. Neither uses `publicFIDX`, `freezePublicInterface`, `publicBottom`, or + previous-result escape accumulation. Visible constructor fields now publish + allocators, allowing their private-memory helpers to inline. Unknown callback + edges participate in 28a's class-init cycle detection. Keep the earlier + constructor model and parser layout; Chapter27 is unchanged. + The old testIfOrNull read a nullable pointer without TypeCheck; its port uses + Chapter29's valid nullable-result case. Printed goldens drop private helper + Returns and a never-published loop-local function. The String fixture's old + implicit return exposed `_hashCodeString`: its standalone body added two + register moves weighted 8+1 on x86, raising 12 to 21. Cliff reordered the + declarations to return the public `hashCode` wrapper instead; the allocation, + encoding, and native-export fixtures in 28a/28b/29 now follow that order and + use measured expectations of 12/8/6 (x86/RISC-V/ARM), with 12 for native x86 + export. RISC-V also measures 8 with this declaration order before the + backport, so restoring its old 6 would fail independently of escape-flow. + - Chapter 18 is the evaluator cutover: use `Eval2` and the compiler's schedule from that chapter onward. The old `evaluator/Evaluator` and its private `Scheduler` remain only in Chapters 10-17b; do not forward-port or revive them. @@ -1093,15 +1208,24 @@ Consequences: - Unknown-caller Start edges and post-Opto compilation-unit ownership are separate concepts. Do not overload Start edges merely to keep surviving functions attached to a compilation unit. -- A global escape fallback means all public functions, not all functions. +- In the older snapshots, a global escape fallback means all public functions, + not all functions. Chapter29 instead propagates the outside value's bound; + arbitrary unknown local values still require FULL. Public `<clinit>` functions escape when their class and all ancestor names are public (no direct name component begins with `_`). -- Escape summaries are monotone discovery facts. If a later SCCP state widens +- In those older snapshots, escape summaries are monotone discovery facts. If a later SCCP state widens to FULL/public-only, it must not forget precise private bits discovered from the same Return earlier. ## Shared escape analysis and the rejected phase-hook experiment +The phase-hook warning below records the historical Chapter28b experiment. +The [escape-flow replacement](../chapter29/docs/escape-flow.md), now in 28a/28b/29, +carries outside bounds through values, removes `priorEscapes`/`publicBottom` +and the frozen public inventory, and supplies a class-singleton `#self` default. +Its remaining scan and late-import precision work are in the roadmap. The old +warning to retain the hooks is superseded by this complete value-flow change. + Chapter 28b shares one `GlobalEscapeNode` across compilation units. It scans calls and unloaded summaries, registers reads with `addDepForwards`, and wakes StopCUs when its type changes. New calls/functions/summaries must also queue it: |
