diff options
Diffstat (limited to 'chapter29/src')
38 files changed, 711 insertions, 217 deletions
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..6d653835 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<>(); @@ -80,7 +83,7 @@ abstract public class Opto { if( x instanceof ParmNode && x._type.isHighOrConst() ) deps.push(x); // Construction identities may fold after the optimistic solve. // Adds may need sorting after imported node IDs were assigned. - if( x instanceof ConstructNode || x instanceof AddNode ) deps.push(x); + if( x instanceof ConstructNode || x instanceof InitViewNode || x instanceof AddNode ) 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); @@ -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/codegen/TypeCheck.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index 30e1415e..a86cd18a 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -20,11 +20,13 @@ abstract class TypeCheck { Ary<Node> errs = new Ary<>(Node.class); Ary<ConstructNode> constructs = new Ary<>(ConstructNode.class); + Ary<InitViewNode> views = new Ary<>(InitViewNode.class); code._stop.walk( n -> { if( n.err() != null ) errs.add(n); if( n instanceof CLInitNode ) code.add(n); if( n instanceof ConstructNode con ) constructs.add(con); + if( n instanceof InitViewNode view ) views.add(view); return null; }); @@ -48,11 +50,13 @@ abstract class TypeCheck { if( code._obs != null ) code._obs.error(min, min.err().getMessage()); throw min.err(); } - // Checked construction boundaries have no runtime behavior. Gathered + // Checked construction boundaries and views have no runtime behavior. Gathered // above during the existing error walk; no separate graph pass/solve. for( ConstructNode con : constructs ) if( !con.isDead() ) con.subsume(con.in(1)); + for( InitViewNode view : views ) + if( !view.isDead() ) view.subsume(view.in(1)); } private static int errorRank(Node n) { 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..91d27330 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); } @@ -244,7 +246,7 @@ public class CallNode extends CFGNode { // Check for args for( int i=0; i<tfp.nargs(); i++ ) - if( !arg(i+2)._type.isa(tfp.arg(i)) || !arg(i+2)._type.accessISA(tfp.arg(i)) ) { + if( !arg(i+2)._type.isa(tfp.arg(i) instanceof TypeMemPtr p ? p.partialBound() : tfp.arg(i)) || !arg(i+2)._type.accessISA(tfp.arg(i)) ) { if( arg(i+2)._type instanceof TypeMemPtr actual && actual._partial && tfp.arg(i) instanceof TypeMemPtr formal && !formal._partial ) return Parser.error("Cannot pass an incomplete object to a parameter without '^' (ordinary function or constructor)",_loc); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java index 3984e48f..0af37a02 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java @@ -49,10 +49,17 @@ public class ConstructNode extends Node { return ptr.withPartial(partial); } @Override public Node idealize() { - // Wait for Opto to install closed field types. Afterwards, a proven - // identity with initialized fields has no remaining error obligation. + // Restricting an already restricted view is redundant, including after + // inlining. A partial Parm type alone can later sharpen to complete. + if( _partial && partialView(in(1)) ) return in(1); + // Wait for Opto to install closed field types. Afterwards, a proven + // identity with initialized fields is good, and can be removed. + // Otherwise we're keeping this Node until we error report. return !_partial && CodeGen.CODE._phase.ordinal()>=CodeGen.Phase.Opto.ordinal() && _type==in(1)._type && err()==null ? in(1) : null; } + static boolean partialView(Node n) { + return n instanceof InitViewNode || n instanceof ConstructNode con && con._partial; + } @Override public Parser.ParseException err() { if( in(2)==null || in(2)._type.isHigh() || !(in(1)._type instanceof TypeMemPtr ptr) ) return null; Type mem = in(2)._type; 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..7616932d 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,17 @@ 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(); + ptr = ptr.withPartial(TypeMemPtr.mayBePartial(src)); + return src instanceof TypeMemPtr actual && actual._partial && actual._obj._name==ptr._obj._name + ? ptr.initialized(actual._obj) : ptr; + } + 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..57340609 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -9,19 +9,26 @@ import java.util.HashMap; import java.util.IdentityHashMap; /** - * Merge public and private aliases. + * Merge public and private aliases. A borrow orders partial-reader calls + * after constructor Stores without adding the private values to escape sets. * 0 - control * 1 - private pointer * 2 - private alias * 3 - public alias */ public class EscapeNode extends TypeNode { + public final boolean _borrow; public EscapeNode(Field fld, Node self, Node priv, Node pub ) { + this(fld,self,priv,pub,false); + } + public EscapeNode(Field fld, Node self, Node priv, Node pub, boolean borrow ) { super(fld,null,self,priv,pub); + _borrow = borrow; } public EscapeNode(EscapeNode esc ) { super(esc); // Copy constructor + _borrow = esc._borrow; // Except we do not want/need self ptr past Opto. // *NOTE* the weird direct stomp; this is correct because this // constructor does NOT set the backedges, because it is used to @@ -38,6 +45,7 @@ public class EscapeNode extends TypeNode { @Override public Tag serialTag() { return Tag.Escape; } @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + assert !_borrow; // Source ^ interfaces cannot yet be serialized. baos.packed2(types.get(_con)); } static Node make( BAOS bais, Type[] types) { @@ -73,13 +81,20 @@ public class EscapeNode extends TypeNode { // t is meet of pub & priv. Pub memory can be very weak (e.g. alias 1) // and we're no worse than the declared field type - Type t = tpriv.meet(tpub).join(fld._t); + Type bound = fld._t; + if( _borrow && bound instanceof TypeMemPtr ptr && TypeMemPtr.mayBePartial(tpriv) ) + bound = ptr.withPartial(true).partialBound(); + Type t = tpriv.meet(tpub).join(bound); + // Lending memory to a local read-only partial argument is an ordering + // edge, not publication to unknown callers. Keep the public escape sets. + if( _borrow ) + return TypeMem.make(fld._alias,t,false,false,false,mpub._escFs,mpub._escAs); int[] fidxes = XInt.meet(mpriv._escFs, mpub._escFs); int[] aliases = XInt.meet(mpriv._escAs, mpub._escAs); // 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); } @@ -112,11 +127,12 @@ public class EscapeNode extends TypeNode { } @Override public boolean eq(Node n) { + if( _borrow!=((EscapeNode)n)._borrow ) return false; if( fld()._alias!=((EscapeNode)n).fld()._alias ) return false; assert _con == ((EscapeNode)n)._con; return true; } - @Override int hash() { return _con.hashCode(); } + @Override int hash() { return _con.hashCode() ^ (_borrow ? 1024 : 0); } } 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..8b6b347e 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,19 @@ 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( t instanceof TypeMemPtr ptr && ptr._partial && + !(idx==0 && sig().nargs()>1 && sig().arg(1) instanceof TypeMem) ) return ptr.partialBound(); + 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/InitViewNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/InitViewNode.java new file mode 100644 index 00000000..46988a99 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/InitViewNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.*; + +/** A program-point view of self. Memory proves which slots may be read; + * their values still come from ordinary Loads. Erased after TypeCheck. */ +public class InitViewNode extends TypeNode { + public InitViewNode(TypeMemPtr declared, Node self, Node mem) { super(declared,null,self,mem); } + @Override public String label() { return "InitView"; } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("initView(").n(in(1)).p(")"); } + @Override public Type compute() { + Type ptr = in(1)._type, mem = in(2)._type; + if( ptr.isHigh() || mem.isHigh() ) return Type.TOP; + if( !(ptr instanceof TypeMemPtr p) ) return ptr; + TypeStruct state = mem instanceof TypeMem m && m._one && m._t instanceof TypeStruct ts + ? ts : p._obj.makeInit(); + // An earlier alias can have fewer initialized slots. The declaration + // supplies field types; this program point's memory supplies the proof. + return p.makeFrom(((TypeMemPtr)_con)._obj).withPartial(true).initialized(state); + } + @Override public Node idealize() { + // Closed declarations and settled memory must prove this view redundant. + // Keep a structural partial restriction: a Parm's current partial type + // alone is not enough, since inlining can substitute a complete caller. + return CodeGen.CODE._phase.ordinal()>=CodeGen.Phase.Opto.ordinal() && + _type==in(1)._type && ConstructNode.partialView(in(1)) ? in(1) : null; + } +} 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..85ab29f9 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -76,7 +76,6 @@ public class LoadNode extends MemOpNode { return Type.BOTTOM; // Error in is error out if( !(ptr0 instanceof TypeMemPtr tmp) ) return scalar(mem._t); - if( tmp._partial && (!mem._one || mem._clz) ) return TypeScalar.BOT; if( tmp.nullable() ) return Type.BOTTOM; // Load from nil-able is error @@ -87,6 +86,8 @@ public class LoadNode extends MemOpNode { if( pfld == null ) return tmp.isHigh() || tmp._obj.isHigh() ? TypeScalar.TOP : TypeScalar.BOT; + if( tmp._partial && (!mem._one || mem._clz) && pfld._t==TypeScalar.BOT ) return TypeScalar.BOT; + Type t = pfld._t; boolean readonly = t instanceof TypeMemPtr view && view._ro; // Load member of constant array @@ -97,6 +98,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. @@ -104,7 +112,10 @@ public class LoadNode extends MemOpNode { t = t.makeRO(); // A completed receiver gives a completed view of its reachable fields. // Through self, keep object references restricted until the root new. - if( t instanceof TypeMemPtr value ) t = value.withPartial(tmp._partial && !value._obj.isAry()); + if( t instanceof TypeMemPtr value ) { + value = value.withPartial(tmp._partial && !value._obj.isAry()); + t = value._partial ? value.partialBound() : value; + } return scalar(t); } @@ -225,38 +236,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,7 +333,16 @@ 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) { - while( ptr instanceof ReadOnlyNode || ptr instanceof ConstructNode con && con._partial ) { + // 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 InitViewNode || ptr instanceof ReadOnlyNode || ptr instanceof ConstructNode con && con._partial ) { addDep(ptr); ptr = ptr.in(1); } @@ -347,7 +379,7 @@ public class LoadNode extends MemOpNode { Parser.ParseException err = super.err(); if( err!=null ) return err; if( (in(0)==null || !in(0)._type.isHigh()) && _type==TypeScalar.BOT && - mem()._type instanceof TypeMem mem && mem._one && !mem._clz ) + mem()._type instanceof TypeMem mem && ((mem._one && !mem._clz) || (ptr()._type instanceof TypeMemPtr p && p._partial)) ) return Parser.error("Field '"+_name+"' might not be initialized",_loc); return null; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index b453550d..35183380 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -123,7 +123,7 @@ public abstract class MemOpNode extends TypeNode { // Already an error, but better error messages come from elsewhere if( ptr == Type.BOTTOM ) return null; if( ptr.isHigh() ) return null; // Assume it will fall to not-null - if( ptr instanceof TypeMemPtr p && p._partial && + if( !_isLoad && ptr instanceof TypeMemPtr p && p._partial && !(mem()._type instanceof TypeMem m && m._one && !m._clz) ) return Parser.error("Cannot access field '"+_name+"' through an incomplete object",_loc); // Better be a not-nil TMP 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..aea402f6 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -20,7 +20,7 @@ public class ParmNode extends PhiNode { super(label, inputs); _idx = idx; _declaredType = declaredType; - _type = declaredType; + _type = declaredBound(); } public ParmNode(ParmNode parm) { super(parm, parm._label ); _idx = parm._idx; _declaredType = parm._declaredType; } @Override public Tag serialTag() { return Tag.Parm; } @@ -49,6 +49,12 @@ public class ParmNode extends PhiNode { public FunNode fun() { return (FunNode)in(0); } + // The hidden constructor receiver has private memory for checking reads. + // Only borrowed source parameters need an initially empty field promise. + private Type declaredBound() { + return !(_idx==2 && "self".equals(_label)) && _declaredType instanceof TypeMemPtr ptr ? ptr.partialBound() : _declaredType; + } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { if( fun()._name!=null && fun()._name.endsWith("<clinit>") && _label.equals("arg") ) @@ -68,7 +74,7 @@ public class ParmNode extends PhiNode { 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; + return declaredBound(); // Set type to local top of the starting type Type t = Type.TOP; for( int i = 1; i < nIns(); i++ ) { @@ -78,7 +84,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 @@ -88,7 +99,7 @@ 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(); - t = t.join(_declaredType); + t = t.join(declaredBound()); return t==Type.TOP && _declaredType instanceof TypeMem ? TypeMem.TOP : t; } 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..010d5f61 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 @@ -330,6 +331,8 @@ public class StoreNode extends MemOpNode { public Parser.ParseException err() { Parser.ParseException err = super.err(); if( err != null ) return err; + if( !_init && ptr()._type instanceof TypeMemPtr p && p._partial ) + return Parser.error("Cannot modify a field through an incomplete object outside its constructor",_loc); if( TypeMemPtr.mayBePartial(val()._type) && !(mem()._type instanceof TypeMem mem && mem._one && !mem._clz) ) return Parser.error("Cannot store an incomplete object into an ordinary object",_loc); 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/Allocations.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java index 0eda2c62..be68e10e 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java @@ -150,7 +150,7 @@ final class Allocations { new ProjNode(P._ref._start,1,ScopeNode.MEM0).peephole()).peephole(); Node[] parms = new Node[nargs]; for( int i = 0; i<nargs; i++ ) - parms[i] = new ParmNode("arg"+i,i+2,atypes[i],fun,ConstantNode.seed(atypes[i]).peephole()).peephole(); + parms[i] = new ParmNode("arg"+i,i+2,atypes[i],fun,ConstantNode.seed(fun.defaultArg(i)).peephole()).peephole(); NewNode nnn = new NewNode(ts,fun,ConFldOffNode.make(ts," len")).init(); Node self = new ProjNode(nnn,0,ts.str()).init(); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java index 2720ad3d..6dec8ac1 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; /** * Field initialization is ordinary forward typing: New supplies Scalar.BOT @@ -10,17 +11,18 @@ import com.seaofnodes.simple.type.*; * initialized integer. Loads and merged Returns inspect these types after the * parser closes loops and compute() stabilizes. No backwards initialization walk. * - * References have just a yes/no restriction. Constructor self and ^ parameters - * are incomplete. An allocation result is incomplete iff an actual argument is - * incomplete. Copies and Phis preserve this restriction. Only self may be read - * while incomplete; object-reference fields read from self conservatively remain - * incomplete. Arrays are born initialized and cannot contain incomplete refs. - * Ordinary calls and stores outside self require complete references. + * Constructor self and ^ parameters are incomplete. InitViewNode combines self + * with its current private memory: set fields carry their declared types and + * missing fields carry Scalar.BOT. Local ^ parameters meet these shapes through + * ordinary forward flow; unknown callers promise no initialized fields. Only + * the original constructor may write through an incomplete pointer. * - * This permits cycles to be assembled but not traversed until the root new - * returns. A new with only complete arguments, including null, returns complete. - * A ^ formal is always restricted inside its constructor, even when a caller - * passes a complete argument. No field requirements are inferred. + * Calls borrowing self receive its Stores on the ordinary public memory edge, + * using aliasable Escape slices without publishing its identity. Field values + * come from memory, not the pointer's initialization shape. Incomplete values + * may be retained only in private construction memory. Nested object references + * conservatively promise no initialized fields; arrays are born initialized. + * No field requirements are inferred and no extra memory arguments are added. * * Incompleteness lives in TypeMemPtr, not a parser provenance graph. Ordinary * Phis carry it around loops, conversions preserve it, and ConstructNode types @@ -39,7 +41,7 @@ import com.seaofnodes.simple.type.*; * Reading a pointer field through a completed receiver gives a completed view * of that field too: its object's construction could only retain incomplete * references from the enclosing construction. There is no group ID to clear. - * A read through incomplete self conservatively returns an incomplete reference + * A read through an incomplete pointer conservatively returns an incomplete reference * (except initialized arrays), even when the stored value happens to be complete. * Own-self access is identified by the receiver and its private memory, not by * the nominal class: a ^ argument of the same class cannot use that exception. @@ -53,7 +55,8 @@ import com.seaofnodes.simple.type.*; * Hidden helpers have only allocator callers, while the public constructor * binding denotes the allocator. Private-memory Parms therefore need no * fictitious external default or constructor-specific transfer function. - * There is no extra construction pass; see docs/deferred-construction.md. + * InitView and Construct are erased by the existing TypeCheck walk. There is + * no extra construction pass; see docs/construction-groups.md. */ final class Construction { private final Parser P; @@ -83,8 +86,33 @@ final class Construction { return P._scope.in(P._scope.update(mem,null)); } + Node view(Node ptr) { + return own(ptr) ? new InitViewNode((TypeMemPtr)((ParmNode)_frame._self)._declaredType,ptr,selfMem()).peephole() : ptr; + } + + // Carry the constructor's Stores on the call's ordinary memory edge. + // The borrowed receiver is read-only; this does not publish its identity. + Node callMemory(Ary<Node> args, Node pub) { + if( !_frame._owner ) return pub; + boolean lends = false; + for( int i=2; i<args.size()-1; i++ ) lends |= own(args.at(i)); + if( !lends ) return pub; + Node self = _frame._self; + TypeStruct ts = (TypeStruct)Parser.TYPES.get(((TypeMemPtr)self._type)._obj._name); + Node priv = selfMem().keep(); + for( Field fld : ts._fields ) { + pub.keep(); + Node loan = new EscapeNode(fld,self,priv,pub,true).peephole(); + Node next = P.mergeAlias(pub,fld._alias,loan); + pub.unkeep(); + pub = next; + } + priv.unkeep(); + return pub; + } + boolean own(Node ptr) { - while( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode || (ptr instanceof ConstructNode con && con._partial) ) ptr = ptr.in(1); + while( ptr instanceof InitViewNode || ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode || (ptr instanceof ConstructNode con && con._partial) ) ptr = ptr.in(1); return _frame._owner && ptr==_frame._self; } @@ -97,6 +125,6 @@ final class Construction { void checkSerializable() { if( _borrowed ) - throw P.error("Separate compilation of constructors with '^' parameters is not supported yet"); + throw P.error("Separate compilation of functions with '^' parameters is not supported yet"); } } 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..14dee33b 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java @@ -74,8 +74,8 @@ final class Functions { Type t = P.types.parseType(); // Arg type if( t==null ) break; if( P.match("^") ) { - if( !constructor || !(t instanceof TypeMemPtr ptr) || ptr._obj.isAry() ) - throw P.error("'^' requires a struct parameter of a constructor"); + if( !(t instanceof TypeMemPtr ptr) || ptr._obj.isAry() ) + throw P.error("'^' requires a struct parameter"); t = ptr.withPartial(true); P.construction._borrowed = true; } @@ -131,6 +131,7 @@ final class Functions { } // Into the call + args.set(1,P.construction.callMemory(args,args.at(1))); CallNode call = (CallNode)new CallNode(site, args.asAry()).peephole(); // Post-call setup CallEndNode cend = (CallEndNode)new CallEndNode(call,TypeRPC.constant(P._code.rpc(P._ref._cname))).peephole(); @@ -291,7 +292,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/References.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java index 737ba4c9..483bd7a8 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java @@ -94,7 +94,7 @@ final class References { int selfx = P._scope.kindFcn(var)._lexSize; // Might be a method call from inside a method, so no explicit "self". // Pass the in-scope "self" - return P.expressions.parsePostfixMethod(rvalue,P._scope.in(P._scope.update(P._scope.var(selfx),null))); + return P.expressions.parsePostfixMethod(P.construction.view(rvalue),P._scope.in(P._scope.update(P._scope.var(selfx),null))); } // Assign-update direct into Scope if( var._final && !P._scope.canInit(var) ) 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/TypeMemPtr.java b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 943710d1..d9e11f8f 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -91,6 +91,25 @@ public class TypeMemPtr extends TypeNil { return partial==_partial ? this : make(_nil,_obj,_one,_pub,_ro,partial); } + // A partial declaration promises no initialized slots. Actual callers may + // supply a sharper shape; the declaration must not manufacture those facts. + public TypeMemPtr partialBound() { return _partial ? makeFrom(_obj.makeInit()) : this; } + + // Project field initialization onto declared field types, not stored + // constants. A pointer field being set does not complete its referent. + public TypeMemPtr initialized(TypeStruct state) { + TypeStruct shape = _obj; + for( Field fld : _obj._fields ) { + Field actual = state.field(fld._fname); + Type t = actual==null ? TypeScalar.BOT : actual._t; + if( t==Type.BOTTOM || t==TypeScalar.BOT ) t = TypeScalar.BOT; + else if( t.isHigh() ) t = TypeScalar.TOP; + else t = fld._t==Type.BOTTOM ? TypeScalar.BOT : fld._t==Type.TOP ? TypeScalar.TOP : fld._t; + shape = shape.replace(fld.makeFrom(t)); + } + return makeFrom(shape); + } + // Conservative on unresolved scalar/pointer families; null is complete. public static boolean mayBePartial(Type t) { return t instanceof TypeMemPtr ptr ? ptr._partial 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/ConstructionGroupTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java index b5bbfce8..e544fcad 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java @@ -41,10 +41,11 @@ public class ConstructionGroupTest { } @Test public void testIncompleteChildReadAfterInlining() { - // This lookup supplies a live result. Inlining must not turn self - // complete inside the body before checking the use of child. - rejects(parent("child = new Child(self); payload = child.parent==null;")+ - "return new Parent(arg).payload;","incomplete object"); + // Child's own slots are initialized, even though its parent remains + // partial. Reading that slot does not complete the parent reference. + String src = parent("child = new Child(self); payload = child.parent==null;")+ + "return new Parent(arg).payload;"; + assertEquals("0",Eval2.eval(new CodeGen(src).driver(CodeGen.Phase.TypeCheck),0)); } @Test public void testInitializerFeedsConstructor() { @@ -61,14 +62,14 @@ public class ConstructionGroupTest { @Test public void testNoIncompleteLookupOrEscape() { rejects(parent("payload = 1; child = new Child(self); read(child);")+"return 0;","ordinary function"); rejects(parent("payload = 1; child = new Child(self);").replace("parent = par;","parent = par; value = par.payload;")+ - "return 0;","incomplete object"); + "return 0;","Might be null"); rejects(""" struct Box { Test.C? value; }; val box = new Box; struct C { int~ x; new C = { -> box.value = self; x = 1; }; }; return 0; ""","ordinary object"); rejects("struct C { C next = self; int~ x; new C = { -> x = next.x; }; }; return new C().x;", - "incomplete object"); + "might not be initialized"); } @Test public void testAliasesAndLoopBackedges() { @@ -82,8 +83,8 @@ public class ConstructionGroupTest { "return 0;","ordinary function"); } - @Test public void testConstructorOnlyQualifier() { - rejects("struct C {}; val f = { C ^c -> return 0; }; return 0;","constructor"); + @Test public void testPartialQualifier() { + new CodeGen("struct C {}; val f = { C ^c -> return 0; }; return 0;").driver(CodeGen.Phase.TypeCheck); rejects("struct C { new C = { int ^x -> }; }; return 0;","struct parameter"); rejects(parent("payload = 1; child = new Child(self);").replace("^par","par")+"return 0;","without '^'"); CodeGen code = new CodeGen(parent("payload = 1; child = new Child(self);")+"return 0;") @@ -127,7 +128,7 @@ public class ConstructionGroupTest { } @Test public void testDeclaredQualifierAndOwnReceiver() { - // A complete caller does not grant permission to read a ^ formal. + // A public constructor's unknown callers promise no initialized slots. for( String body : new String[]{"value = par.payload;", "value = par.payload*0;", "int x = par.payload; value = x*0;", "value = par.payload==par.payload;"} ) rejects(""" @@ -137,7 +138,7 @@ public class ConstructionGroupTest { new Child = { Parent ^par -> BODY }; }; return new Child(new Parent).value; - """.replace("BODY",body),"incomplete object"); + """.replace("BODY",body),"might not be initialized"); // The self exception belongs to the receiver, not every pointer of its class. rejects(""" struct C { 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/chapter29/src/test/java/com/seaofnodes/simple/PartialReadTest.java b/chapter29/src/test/java/com/seaofnodes/simple/PartialReadTest.java new file mode 100644 index 00000000..a6230b69 --- /dev/null +++ b/chapter29/src/test/java/com/seaofnodes/simple/PartialReadTest.java @@ -0,0 +1,155 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.InitViewNode; +import com.seaofnodes.simple.node.ConstructNode; +import com.seaofnodes.simple.parser.Parser; +import org.junit.Test; +import static org.junit.Assert.*; + +public class PartialReadTest { + private static String program(String body, String helper) { + return "struct _C { int~ x; int~ y; new _C = { int n -> " + body + + " }; }; val _read_noInline = { _C ^p -> " + helper + + " }; return new _C(arg).y;"; + } + private static void rejects(String source, String message) { + try { + new CodeGen(source).driver(CodeGen.Phase.TypeCheck); + fail("Accepted " + source); + } catch( Parser.ParseException e ) { + assertTrue(e.getMessage(),e.getMessage().contains(message)); + } + } + @Test public void testLocalRead() { + String src = program("x=n; y=_read_noInline(self);", "return p.x;"); + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.TypeCheck); + assertNull(code._stop.walk(n -> n instanceof InitViewNode ? n : null)); + assertEquals("42",Eval2.eval(code,42)); + } + new CodeGen(src).driver(CodeGen.Phase.Encoding,TestC.CPU_PORT,TestC.CALL_CONVENTION,true,false,0); + } + @Test public void testRedundantViewsFoldBeforeTypeCheck() { + String src=program("x=n; y=0; y=_read_noInline(self);", "return p.x;"); + CodeGen code=new CodeGen(src).driver(CodeGen.Phase.IterPostOpto); + assertNull(code._stop.walk(n -> n instanceof InitViewNode ? n : null)); + assertNull(code._stop.walk(n -> n instanceof ConstructNode c && !c._partial ? n : null)); + code.driver(CodeGen.Phase.TypeCheck); + assertEquals("31",Eval2.eval(code,31)); + + // Here the view still masks y. A valid program need not initialize + // every field before lending self, so survival is not itself an error. + code=new CodeGen(program("x=n; y=_read_noInline(self);", "return p.x;")) + .driver(CodeGen.Phase.IterPostOpto); + assertNotNull(code._stop.walk(n -> n instanceof InitViewNode ? n : null)); + code.driver(CodeGen.Phase.TypeCheck); + assertEquals("31",Eval2.eval(code,31)); + } + @Test public void testInliningKeepsBorrowRestriction() { + rejects(""" + struct _C { + int !x; + new _C={ int n -> x=n; if(!n) _write(self); }; + }; + val _write={ !_C ^p -> if(p.x) p.x=9; return p.x; }; + val a=new _C(0); val b=new _C(1); + return _write(b)+a.x; + ""","incomplete object"); + } + @Test public void testMissingAndBranchField() { + for( String use : new String[]{"p.x", "p.x*0", "p.x==p.x"} ) + rejects(program("y=_read_noInline(self); x=n;", "return "+use+";"),"might not be initialized"); + rejects(program("if(n) x=n; y=_read_noInline(self); x=0;", "return p.x;"),"might not be initialized"); + } + @Test public void testActualValueFromMemory() { + for( String body : new String[]{"x=1; val p=self; x=2; y=_read_noInline(p);", + "val p=self; x=2; y=_read_noInline(p);"} ) { + CodeGen code = new CodeGen(program(body,"return p.x;")).driver(CodeGen.Phase.TypeCheck); + assertEquals("2",Eval2.eval(code,0)); + } + } + @Test public void testBorrowedWrite() { + rejects(program("x=n; y=_read_noInline(self);", "p.x=9; return p.x;") + .replace("int~ x", "int !x").replace("_C ^p", "!_C ^p"),"incomplete object"); + } + @Test public void testUnknownCallerCannotRead() { + rejects(program("x=n; y=_read_noInline(self);", "return p.x;") + .replace("_read_noInline","read_noInline"),"might not be initialized"); + } + @Test public void testForwardingAndMergedCallers() { + String src = program("x=n; y=_read_noInline(self);", "return _next_noInline(p);") + + " val _next_noInline = { _C ^p -> return p.x; };"; + assertEquals("17",Eval2.eval(new CodeGen(src).driver(CodeGen.Phase.TypeCheck),17)); + rejects(program("y=_read_noInline(self); x=n; y=_read_noInline(self);", "return p.x;"),"might not be initialized"); + } + @Test public void testLoops() { + String src = program("x=1; for(int i=0; i<n; i++) x+=2; y=_read_noInline(self);", "return p.x;"); + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.TypeCheck); + assertEquals("7",Eval2.eval(code,3)); + assertEquals("1",Eval2.eval(code,0)); + } + rejects(program("for(int i=0; i<n; i++) x=n; y=_read_noInline(self); x=0;", "return p.x;"),"might not be initialized"); + } + @Test public void testNoPublication() { + rejects("struct Box { Test._C? !p; }; val box=new Box; " + + program("x=n; y=_read_noInline(self);", "box.p=p; return p.x;"),"ordinary object"); + } + @Test public void testConstructorReadAndRetention() { + String src = """ + struct _Child { + Test._Parent parent; + int~ seen; + new _Child = { Test._Parent ^p -> parent=p; seen=p.x; }; + }; + struct _Parent { + int~ x; + _Child child; + new _Parent = { int n -> x=n; child=new _Child(self); }; + }; + val p=new _Parent(arg); return p.child.seen+p.child.parent.x; + """; + assertEquals("22",Eval2.eval(new CodeGen(src).driver(CodeGen.Phase.TypeCheck),11)); + rejects(src.replace("x=n; child=new _Child(self);","child=new _Child(self); x=n;"),"might not be initialized"); + } + @Test public void testInlineReadAndWrite() { + String src=program("x=n; y=_read_noInline(self);","return p.x;").replace("_noInline",""); + assertEquals("19",Eval2.eval(new CodeGen(src).driver(CodeGen.Phase.TypeCheck),19)); + rejects(src.replace("return p.x;","p.x=9; return p.x;").replace("int~ x","int !x").replace("_C ^p","!_C ^p"),"incomplete object"); + rejects(src.replace("x=n; y=", "y=").replace("(self);", "(self); x=n;"),"might not be initialized"); + } + @Test public void testArrayAndNestedReference() { + String src=""" + struct _C { + int[] data; + int~ y; + new _C = { int n -> data=new int[1]; data[0]=n; y=_read_noInline(self); }; + }; + val _read_noInline={ _C ^p -> return p.data[0]; }; + return new _C(arg).y; + """; + assertEquals("23",Eval2.eval(new CodeGen(src).driver(CodeGen.Phase.TypeCheck),23)); + // A set reference slot is not proof that its referent is initialized. + rejects("struct D { int x=7; }; "+src.replace("int[] data","D data") + .replace("data=new int[1]; data[0]=n;","data=new D;") + .replace("p.data[0]","p.data.x"),"might not be initialized"); + } + @Test public void testCompleteBorrowCannotPublishPartial() { + rejects(""" + struct _C { int x=7; }; + struct Box { _C? p; }; val box=new Box; + val _store={ !_C ^dst, _C ^src -> box.p=src; return dst.x; }; + return _store(new _C,new _C); + ""","ordinary object"); + } + @Test public void testSameClassMemory() { + String src=program("x=n; y=n ? _read_noInline(self) : x;", + "val other=new _C(0); return p.x+other.y;"); + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code=new CodeGen(src,seed,true).driver(CodeGen.Phase.TypeCheck); + assertEquals("29",Eval2.eval(code,29)); + assertEquals("0",Eval2.eval(code,0)); + } + } +} |