diff options
Diffstat (limited to 'chapter29/src')
47 files changed, 539 insertions, 401 deletions
diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 3547b86c..9c954197 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -100,7 +100,9 @@ public class ClassInitDependencies { // CLInit adds a class init requirement to this function // (plus all parent classes) - if( cfg instanceof CLInitNode init ) { + // An invalid receiver can still be Scalar.BOT here. Its Load + // reports the error at TypeCheck; it does not name a class to init. + if( cfg instanceof CLInitNode init && init.cu()!=null ) { FunNode clz = code.link(init.cu()); // <clinit> referred to iset.put(clz.sig().fidx(),1); // Add to edge set if( sites!=null && sites.atX(clz.sig().fidx())==null ) sites.setX(clz.sig().fidx(),init._loc); 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 6e1c0af5..ba7c0c1d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -102,11 +102,10 @@ public class CodeGen { } 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>. + // Private-memory helpers are reached through their allocator. if( fld._fname.charAt(0)=='_' || fld._t==Type.TOP || - (hasCtor && clz.hiddenInit(fld)) ) continue; + clz.hiddenInit(fld) ) continue; if( classFields ) _publicAliases = XInt.make(_publicAliases,fld._alias); if( fld._t instanceof TypeFunPtr tfp ) _publicFIDXs = XInt.meet(_publicFIDXs,tfp._fidxs); @@ -125,14 +124,13 @@ public class CodeGen { } private int[] _publicFIDXs, _publicAliases; + private TypeMem _publicEscapes; /** - * 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". + * 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; @@ -157,12 +155,21 @@ public class CodeGen { 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 @@ -428,7 +435,12 @@ public class CodeGen { // being called. public void link(FunNode fun) { int fidx = fun.sig().fidx(); + FunNode old = _linker.atX(fidx); + if( old!=null && old!=fun ) old.moveDepsToWorklist(); _linker.setX(fidx,fun); + // Calls waiting for an unloaded target depend on Start until there + // is a FunNode to depend on. Installing a body lets them retry. + if( _start!=null ) _start.moveDepsToWorklist(); add(_globalEscapes); // A new or replacement summary may expose escapes. } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Iter.java index 1f53d3e4..35bc62ac 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -11,57 +11,14 @@ public abstract class Iter { assert code._globalEscapes==null; code._globalEscapes = new GlobalEscapeNode(); code._start.setDef(2,code._globalEscapes); - // The phase shift closes all parser-in-progress states and freezes - // unknown external inputs. Imported nodes carry post-Opto escape - // precision, but Iter is a fresh pessimistic solve: memory escape - // summaries must restart at FULL so newly discovered private escapes - // can only be removed, never added. Seed the complete graph once. - boolean hasImports = code._externPaths != null; - code._start.walk(n -> { - // Type import can reconcile a constant's declaration. - n._type = n instanceof ConstantNode ? n.compute() - : hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); - code.add(n); - return null; - }); + // Parsing queues initialized nodes and phase-sensitive peepholes. + // Only the new escape summary needs seeding here. + code.add(code._globalEscapes); code._iter.iterate(code); // Expensive assert. assert !CodeGen.expensiveAssert() || Opto.fixedPointCheck(code); } - // Stabilize existing node types before releasing source error obligations. - // No rewrites: even an unused illegal Load must still be checked here. - public static void types(CodeGen code) { - // Definite initialization needs the optimistic solution around loops: - // an unchanged initialized field must not be stuck at its old BOT seed. - Ary<Node> typed = new Ary<>(Node.class); - code._start.walk(n -> { typed.add(n); n._type = Type.TOP; code.add(n); return null; }); - Node n; - while( (n = code._iter._work.pop())!=null ) { - if( n.isDead() ) continue; - Type t = n._type.meet(n.compute()); - if( t==n._type ) continue; - n._type = t; - code.addAll(n._outputs); - n.moveDepsToWorklist(); - } - code.addAll(typed); - } - - private static Type iterEscapeReset(Type t) { - if( t instanceof TypeMem mem ) - return mem._one ? mem : mem.makeFrom(XInt.FULL,XInt.FULL); - if( t instanceof TypeTuple tt ) { - TypeTuple rez = tt; - for( int i=0; i<tt._types.length; i++ ) { - Type tx = iterEscapeReset(tt._types[i]); - if( tx != tt._types[i] ) rez = rez.makeFrom(i,tx); - } - return rez; - } - return t; - } - private static Type iterImportReset(Type t) { if( t.isHigh() ) return t.dual(); @@ -88,18 +45,13 @@ 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. - for( Node n : nodes ) - if( n instanceof StopCUNode && !n.isDead() ) n._type = n.compute(); code.addAll(nodes); repair(code); } - // Repair the monotonicity assert after loading new nodes (from a file via - // Serialize). Only widening types here makes it safe to resume the usual - // lifting peeps. The worklist already contains changed edges and their - // neighbors. + // Loading a body or linking a call changes the graph and can widen + // existing bounds. Repair only queued nodes and affected neighbors before + // resuming the usual lifting peeps; this does not walk the graph. public static void repair(CodeGen code) { // Gather changes for a normal IterPeeps once the graph has its // monotonicity property back. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java index 543a69df..985cd4d2 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java @@ -165,7 +165,7 @@ public class IterPeeps { Node changed = code._stop.walk( n -> { // Ignore most in-progress things if( n.iskeep() ) return null; - // Types must be forwards, even if on the worklist. + // Types must lift, even if on the worklist. Type nval = n.compute(); assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n; if( list.on(n) ) 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 aa997204..0c37ce39 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.IterPeeps.WorkList; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; @@ -30,7 +31,8 @@ abstract public class Opto { 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,24 +52,73 @@ abstract public class Opto { // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. moveChangesToWorklist(code, oldTypes, changes); + // Unknown callers and concrete call edges have now been rediscovered. + 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 ) { + // Transition from Iter's pessimistic graph to SCCP's optimistic solve in + // one walk. Parsing has closed the named types; install them in the IR + // and resolve forward references before resetting each value to TOP. + // Do not run peepholes here: neighboring nodes may not yet be upgraded or + // reset. SCCP sees the completed setup, and IterPostOpto handles rewrites. + // + // The same walk preserves Returns while call edges are rebuilt, remembers + // old types for incremental cleanup, and gathers numeric modes and phase + // dependencies. These are setup duties, not separate graph passes. + private static void resetToTop(CodeGen code, Ary<Type> oldTypes, Ary<Node> modes, WorkList<Node> deps, Ary<ReturnNode> returns ) { code._start.walk( x -> { + // A snapshot for change detection, not an upper bound: closing + // recursive declarations can change types in either direction. + oldTypes.setX(x._nid,x._type); + if( x.upgradeType(Parser.TYPES) ) deps.push(x); + if( x instanceof FRefNode fref ) resolveForward(code,fref); + // Rebuilding call edges must not DCE a temporarily uncalled body. + // Type-level function references can rediscover it later in SCCP. + 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); + // 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); // 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 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; } ); } + private static void resolveForward(CodeGen code, FRefNode fref) { + if( fref.nIns()!=1 ) return; + boolean alloc = fref._name.endsWith(".<new>"); + String clzName = alloc + ? fref._name.substring(0,fref._name.length()-".<new>".length()).intern() + : fref._name; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); + if( clz==null ) return; + Node con; + if( alloc ) { + Field ctor = clz.field("<new>"); + if( ctor==null || !(ctor._t instanceof TypeFunPtr tfp) ) { + String name = clzName.startsWith(TypeStruct.CLZ) + ? clzName.substring(TypeStruct.CLZ.length()) : clzName; + int dot = name.lastIndexOf('.'); + throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); + } + FunNode fun = code._link(tfp); + if( fun==null ) return; + con = new FunPtrNode(tfp,code._start,fun.ret()); + con._type = Type.BOTTOM; // No Iter bound; the Return may already be reset. + } else { + con = new ConstantNode(TypeMemPtr.make((byte)2,clz,true)); + } + // The new input is visited by the reset walk too. Let SCCP propagate + // its value; replacing the FRef is a later peephole. + fref.addDef(con); + } + // Only entry initializers start with unknown callers. Discover every // other function through calls or escaping values during SCCP. @@ -90,8 +141,9 @@ 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); + // The reset walk keeps Returns alive. Use normal edge + // editing so cleanup also revisits an emptied StopCU. + stop.delDef(i--); } // Unlink the existing conservative call linkages. for( int j=1; j<fun.nIns(); j++ ) @@ -133,10 +185,10 @@ 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. + // Unknown values can later refine to private callbacks too. + // FULL must cover every live target, just like the finite case. for( FunNode fun : code._linker ) - if( fun != null && code.publicFIDX(fun.sig().fidx()) ) + if( fun != null && !fun.isDead() ) linkStart(code,fun); return; } @@ -184,8 +236,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 +317,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/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 2958332b..b77b224c 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -119,52 +119,9 @@ public abstract class ParseAll { if( cu._ext==null ) cu._clz = (TypeStruct)Parser.TYPES.get(TypeStruct.addClzPrefix(cu._cname)); - // Walk over all Nodes, and upgrade the internal constants to the - // closed-over types. - code._stop.walk( (Node n) -> { - n.upgradeType(Parser.TYPES); - if( n instanceof FRefNode fref ) { - boolean alloc = fref._name.endsWith(".<new>"); - String clzName = alloc - ? fref._name.substring(0,fref._name.length()-".<new>".length()).intern() - : fref._name; - TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); - if( clz == null ) - return null; - Node con; - if( alloc ) { - Field ctor = clz.field("<new>"); - if( ctor == null || !(ctor._t instanceof TypeFunPtr tfp) ) { - String name = clzName.startsWith(TypeStruct.CLZ) - ? clzName.substring(TypeStruct.CLZ.length()) : clzName; - int dot = name.lastIndexOf('.'); - throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); - } - FunNode fun = code.link(tfp); - if( fun == null ) return null; - con = new FunPtrNode(tfp,code._start,fun.ret()).peephole(); - } else { - // Class pointer constant: - TypeMemPtr clzptr = TypeMemPtr.make((byte)2,clz,true); - con = code.con(clzptr); - } - // Replace and optimize - fref.addDef(con); - code.add(fref); - } - // Adds sort by NIDs, which just got shuffled - if( n instanceof AddNode add ) - code.add(add); - // All imported bodies are loaded; link them before Iter checks types. - if( n instanceof CallNode call && !NEEDS_LOAD.isEmpty() ) - code.add(call).idealize(); - 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.P.checkConstruction(); code.freezePublicInterface(); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index ac792988..f1aa18ef 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -425,6 +425,21 @@ public class RegAlloc { Node[] conflicts = lrg._selfConflicts.keySet().toArray(new Node[0]); Arrays.sort(conflicts, (x,y) -> x._nid - y._nid ); + // A commutative two-address tie may join a whole chain to a Phi even + // when only the Phi and an earlier def actually overlap. Reuse the + // failed-range walk to find those ties before inserting copies. + // A Split's single use is artificial: leave earlier splitting intact. + findAllLRG(lrg); + for( int i = 0; i<_ns._len; i++ ) { + Node n = _ns.at(i); + if( lrg(n)==lrg && n instanceof MachNode mach && mach.twoAddress()==1 && + mach.commutes() && !(n.in(2) instanceof SplitNode) && + n.in(2).nOuts()==1 && lrg(n.in(2))!=lrg ) + n.swap12(); + else _ns.remove(i--); + } + // Reuse the scratch list to remember just the ties we broke. + // First encounter with a loop Phi: try only cold splits this round. // Remember the Phi across rounds so a persistent self-conflict forces // the hot def/backedge splits on the next encounter. @@ -466,7 +481,9 @@ public class RegAlloc { insertBefore(phi,i,"use/self/phi",round,lrg); } // Split before two-address ops which extend the live range - if( def instanceof MachNode mach && mach.twoAddress()!= 0 ) + // A commuted operand already broke this tie. Rebuild it in the + // next normal coloring round instead of copying the old range. + if( def instanceof MachNode mach && mach.twoAddress()!=0 && _ns.find(def)==-1 ) insertBefore(def,mach.twoAddress(),"use/self/two",round,lrg); } return true; 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 abd8628d..30e1415e 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -19,10 +19,12 @@ abstract class TypeCheck { code._classInitDependencies = deps; // Serialize reuses this checked graph. Ary<Node> errs = new Ary<>(Node.class); + Ary<ConstructNode> constructs = new Ary<>(ConstructNode.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); return null; }); @@ -30,25 +32,35 @@ abstract class TypeCheck { // Prefer an originating error over a secondary error caused by a // BOTTOM input. If all errors are downstream-poisoned, retain // the old first-error behavior. - Node min = null; - for( Node n : errs ) - if( noBottomInputs(n) ) - { min = n; break; } - if( min==null ) - min = errs.at(0); + Node min = errs.at(0); for( Node n : errs ) if( n!=min && - noBottomInputs(n) && + (errorRank(n)<errorRank(min) || (errorRank(n)==errorRank(min) && ((n instanceof MemOpNode nmop && min instanceof MemOpNode mmop && nmop._loc.before(mmop._loc)) || + (n instanceof ConstructNode nc && min instanceof ConstructNode mc && + nc._loc!=null && nc._loc.before(mc._loc)) || (n instanceof CFGNode ncfg && min instanceof CFGNode mincfg && - ncfg.idepth() < mincfg.idepth())) ) + ncfg.idepth() < mincfg.idepth())))) ) min = n; if( code._obs != null ) code._obs.error(min, min.err().getMessage()); throw min.err(); } + // Checked construction boundaries 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)); + } + + private static int errorRank(Node n) { + // Bad memory access originates the error. Missing construction fields + // in turn explain generic-scalar arithmetic further downstream. + if( n instanceof MemOpNode && noBottomInputs(n) ) return 0; + if( n instanceof ConstructNode ) return 1; + return noBottomInputs(n) ? 2 : 3; } private static boolean noBottomInputs(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 f510be39..f8c1c925 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -75,7 +75,10 @@ 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); 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 fcadd0e4..18be3488 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -7,6 +7,7 @@ import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Iter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeRPC; @@ -28,6 +29,9 @@ public class CallNode extends CFGNode { super(nodes); _loc = loc; CodeGen.CODE._calls.add(this); + // Imported targets may be installed after this call is parsed. + // Retry linking when Iter drains the parser's worklist. + CodeGen.CODE.add(this); CodeGen.CODE.add(CodeGen.CODE._globalEscapes); } public CallNode(CallNode call) { super(call); _loc = call._loc; } @@ -82,22 +86,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) { @@ -165,7 +153,8 @@ public class CallNode extends CFGNode { // Walk the bits and link for( int fidx = XInt.next(fidxs,0); fidx > 0; fidx = XInt.next(fidxs,fidx) ) { FunNode fun = CodeGen.CODE.link(fidx); - if( fun!=null && !fun._folding && !linked(fun) ) + if( fun==null ) addDepForwards(CodeGen.CODE._start); + if( fun!=null && !addDep(fun)._folding && !linked(fun) ) progress = link(fun); } } @@ -256,6 +245,9 @@ 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 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); // Constructors return private memory and carry hidden self and // selfMem arguments ahead of the source-level arguments. int argno = i - (tfp.ret() instanceof TypeMem ? 2 : 0); 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 52e3eb54..3984e48f 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java @@ -1,28 +1,70 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.parser.Parser; +import com.seaofnodes.simple.parser.Lexer; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.print.ExprPrinter; /** The source new boundary. Own fields have been constructed, but an incomplete * actual argument keeps this result incomplete. Unlike a callee's merged Return, - * this transfer describes one allocation site. Erased after source checks. */ + * this transfer describes one allocation site. The partial-only form gives + * constructor self and ^ formals their restricted body view even after + * inlining substitutes complete actual arguments. Erased after source checks. */ public class ConstructNode extends Node { + public final Lexer _loc; + private final boolean _explicit; + public final boolean _partial; public ConstructNode(Node value, Ary<Node> args) { - super(null,value); + super(null,value,null); + _loc = null; + _explicit = false; + _partial = false; for( Node arg : args ) addDef(arg); } + // Inside the allocator: keep the final private memory with the result, + // so inlining cannot discard the constructor-completion check. + public ConstructNode(Node value, Node mem, Lexer loc, boolean explicit) { + super(null,value,mem); + _loc = loc; + _explicit = explicit; + _partial = false; + } + // The constructor body sees self and ^ formals through this restricted view. + public ConstructNode(Node value) { + super(null,value,null); + _loc = null; + _explicit = false; + _partial = true; + } @Override public String label() { return "Construct"; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("construct(").n(in(1)).p(")"); } @Override public Type compute() { Type t = in(1)._type; + if( in(2)!=null && in(2)._type.isHigh() ) return Type.TOP; if( !(t instanceof TypeMemPtr ptr) ) return t; - boolean partial = false; - for( int i = 2; i<nIns(); i++ ) partial |= TypeMemPtr.mayBePartial(in(i)._type); + boolean partial = _partial; + for( int i = 3; i<nIns(); i++ ) partial |= TypeMemPtr.mayBePartial(in(i)._type); return ptr.withPartial(partial); } @Override public Node idealize() { - return CodeGen.CODE._phase==CodeGen.Phase.Parse ? null : in(1); + // Wait for Opto to install closed field types. Afterwards, a proven + // identity with initialized fields has no remaining error obligation. + return !_partial && CodeGen.CODE._phase.ordinal()>=CodeGen.Phase.Opto.ordinal() && _type==in(1)._type && err()==null ? in(1) : null; + } + @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; + for( Field fld : ptr._obj._fields ) { + if( fld._extern ) continue; + Field actual = mem instanceof TypeMem tm && tm._t instanceof TypeStruct ts ? ts.field(fld._fname) : null; + if( actual==null || actual._t==TypeScalar.BOT || actual._t==Type.BOTTOM ) + return Parser.error("'"+ptr._obj._name+"' is not fully initialized, field '"+fld._fname+ + (_explicit ? "' is only partially set in the constructor" : "' needs to be set in a constructor"),_loc); + } + return null; } + @Override public boolean eq(Node n) { return _explicit==((ConstructNode)n)._explicit && _partial==((ConstructNode)n)._partial; } + @Override int hash() { return (_explicit ? 1 : 0) | (_partial ? 2 : 0); } } 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 ee911398..47c8ecbe 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -39,6 +39,7 @@ public class ConvertNode extends Node { @Override public Type compute() { 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; 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 3e95fffb..02f08c19 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/chapter29/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.publicEscapes(); + 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/chapter29/src/main/java/com/seaofnodes/simple/node/FRefNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/FRefNode.java index 3906f7be..583a4300 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/FRefNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/FRefNode.java @@ -34,6 +34,8 @@ public class FRefNode extends ConstantNode { @Override public String label() { return "FRef"+_name; } + @Override public Type compute() { return nIns()==1 ? _con : in(1)._type; } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("FRef_").p(_name); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/FldOffNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/FldOffNode.java index 223ca79e..09e5eac8 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/FldOffNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/FldOffNode.java @@ -13,13 +13,13 @@ import java.util.HashMap; /** * A field offset. This becomes a constant *after* other optimizations which * determine field sizes - some fields might be dead, or hold only zeros or - * small values. + * small values. The base is data in slot 1; slot 0 is reserved for control. */ public class FldOffNode extends TypeNode { public final String _fname; // Field name public final Lexer _loc; // - public FldOffNode( Node base, String fname, Lexer loc ) { super(TypeInteger.BOT,base); _fname = fname; _loc=loc; } + public FldOffNode( Node base, String fname, Lexer loc ) { super(TypeInteger.BOT,null,base); _fname = fname; _loc = loc; } @Override public Tag serialTag() { throw Utils.TODO("should not reach here"); } @Override public String label() { @@ -36,7 +36,7 @@ public class FldOffNode extends TypeNode { @Override public Node idealize() { // When base() gets typed, this xforms into a ConFldOffNode - if( in(0)._type instanceof TypeMemPtr tmp ) + if( in(1)._type instanceof TypeMemPtr tmp ) return new ConFldOffNode(tmp._obj,_fname); return null; } @@ -48,7 +48,7 @@ public class FldOffNode extends TypeNode { @Override int hash() { return super.hash() * _fname.hashCode(); } @Override public Parser.ParseException err() { - if( in(0)._type instanceof TypeMemPtr tmp && tmp._obj._fref ) + if( in(1)._type instanceof TypeMemPtr tmp && tmp._obj._fref ) return Parser.error("Unknown struct type '"+tmp._obj._name+"'",null); return null; } 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 d76d80b5..de32bea9 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -170,7 +170,7 @@ public class FunNode extends RegionNode { } // Upgrade inferred or user-written return type to actual - if( _ret!=null && _ret._type instanceof TypeTuple tt && + if( _ret!=null && addDep(_ret)._type instanceof TypeTuple tt && tt.ret() != _sig.ret() && tt.ret().isa(_sig.ret()) ) { setSig(_sig.makeFrom(tt.ret())); return this; @@ -180,12 +180,19 @@ public class FunNode extends RegionNode { // - Must be past pessimistic Iter, which discovers and links calls // through class-field loads and other initially imprecise values. // - FIDX is not in the escape set - // - Not called anywhere else; post Opto called-not-escaped functions need to still be hooked to start + // Concrete callers keep the body alive; FinalizeIR retains surviving + // functions for emission without giving them unknown callers. if( !isRoot() && in(1) instanceof StartCUNode start ) { boolean preOpto = CodeGen.CODE._phase == null || CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal(); - if( !preOpto && !start.escapedFIDX(_sig.fidx()) && nIns()<=2 && _ret!=null ) { - _compunit._stop.delDef(_compunit._stop._inputs.find(ret())); + if( !preOpto && !start.escapedFIDX(_sig.fidx()) && _ret!=null ) { + // CLInit has a call edge but no Return edge. Keep a called + // body's Return rooted even after dropping unknown callers. + if( !isClz() || nIns()<=2 ) { + StopCUNode stop = _compunit._stop; + CODE.add(stop).delDef(stop._inputs.find(ret())); + CODE.addAll(stop._outputs); // The outer Stop can drop an empty unit. + } return removeDeadPath(1); } else { addDep(start); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java index dab48530..740b0895 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/GlobalEscapeNode.java +++ b/chapter29/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/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 4b09d2e9..d62152e5 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -225,7 +225,7 @@ 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); + ptr = address(ptr); Field fld; boolean external = ptr._type instanceof TypeMemPtr tmp && (fld=tmp._obj.field(_name))!=null && fld._extern; @@ -238,13 +238,21 @@ public class LoadNode extends MemOpNode { // 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())) && off()==st.off() ) { + // 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 ) { + Type value = addDep(st.val())._type; + if( ptr()._type.isFinal() || declaredType().isFinal() ) value = value.makeRO(); + if( !value.isa(_type) ) 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; 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; @@ -256,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 PhiNode phi: if( phi instanceof ParmNode || (!(phi instanceof MemPhiNode) && !(phi._type instanceof TypeMem tm && tm._one)) ) return null; @@ -299,6 +307,16 @@ 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) { + while( ptr instanceof ReadOnlyNode || ptr instanceof ConstructNode con && con._partial ) { + 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/chapter29/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/MulNode.java index 04fcf1c2..87141456 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -29,7 +29,7 @@ public class MulNode extends ArithNode { // Integer strength reductions require two integer operands. In // particular Scalar.BOT * 0 must retain its unresolved input. - if( _mode!=1 || !(t1 instanceof TypeInteger && t2 instanceof TypeInteger) ) + if( _mode==2 || !(t1 instanceof TypeInteger && t2 instanceof TypeInteger) ) return super.idealize(); // Move constants to RHS: con*arg becomes arg*con diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter29/src/main/java/com/seaofnodes/simple/node/Node.java index cbd35592..2815dfba 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/Node.java @@ -525,7 +525,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { } @SuppressWarnings("unchecked") - public <N extends Node> N init() { _type = compute(); return (N)this; } + public <N extends Node> N init() { _type = compute(); CODE.add(this); return (N)this; } /** * This function rewrites the current Node into a more "idealized" form. @@ -753,14 +753,16 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { // If a Type upgrade happens, put on worklist boolean _upgradeType( HashMap<String,Type> TYPES ) { return false; } - public final void upgradeType( HashMap<String,Type> TYPES ) { + public final boolean upgradeType( HashMap<String,Type> TYPES ) { Type old = _type; _type = _type.upgradeType(TYPES); boolean progress = _upgradeType(TYPES); if( progress || old != _type ) { CODE.add(this); CODE.addAll(_outputs); if( _deps!=null ) CODE.addAll(_deps); + return true; } + return false; } /** 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 1d8bd484..9c40c75d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -67,16 +67,11 @@ public class ParmNode extends PhiNode { if( !(region() instanceof RegionNode r) ) 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. - boolean privateMem = _idx==3 && _declaredType instanceof TypeMem mem && mem._one && !mem._clz; - if( privateMem && fun().unknownCallers() && nIns()==2 && CodeGen.CODE._phase!=CodeGen.Phase.Parse ) - return TypeMem.TOP; - if( (!privateMem && r.inProgress()) || in(nIns()-1)==null || (privateMem && fun().unknownCallers() && nIns()==2) ) + if( r.inProgress() || in(nIns()-1)==null ) return _declaredType; // Set type to local top of the starting type Type t = Type.TOP; - // Internal construction memory is supplied by allocation/initializer - // calls, not by the fictitious external caller used to keep a body live. - for( int i = privateMem && fun().unknownCallers() ? 2 : 1; i < nIns(); i++ ) { + for( int i = 1; i < nIns(); i++ ) { // If the region's control input is live, add this as a dependency // to the control because we can be peeped should it become dead. Type ctrl = addDep(r.in(i))._type; @@ -94,10 +89,6 @@ public class ParmNode extends PhiNode { if( t instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() ) t = ti.same_but_slightly_wider_than(); t = t.join(_declaredType); - // ^ is a restriction inside the constructor even if every currently - // known caller passes a complete object. Inlining may later remove it. - if( t instanceof TypeMemPtr ptr && _declaredType instanceof TypeMemPtr decl && decl._partial ) - t = ptr.withPartial(true); return t==Type.TOP && _declaredType instanceof TypeMem ? TypeMem.TOP : t; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/PhiNode.java index a4aaaa07..f45c7325 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -200,7 +200,7 @@ public class PhiNode extends Node { private Node drop_same_op() { Node op = in(1), cp = op.copyEmpty(); cp._type = null; - cp.addDef(null); + cp._inputs.add(null); for( int j=1; j<op.nIns(); j++ ) { Node x = op.in(j); boolean different = false; @@ -217,25 +217,52 @@ public class PhiNode extends Node { // Do not introduce an operand Phi mixing incompatible type families. if( t==Type.BOTTOM || t==TypeScalar.BOT ) { for( int i=1; i<ins.length; i++ ) addDep(ins[i]); - cp.kill(); + discardTrial(cp); return null; } PhiNode phi = j==1 && op instanceof MemOpNode mem - ? new MemPhiNode(_label,mem._alias,ins) - : PhiNode.make(_label,t,ins); - x = phi.peephole(); + ? new MemPhiNode(_label,mem._alias) + : PhiNode.make(_label,t); + // Compute the trial without changing any existing use lists. + // Rejecting and killing a wired trial would wake our own + // dependencies and retry the same unsuccessful fold forever. + for( Node in : ins ) phi._inputs.add(in); + phi._type = phi.compute(); + x = phi; } - cp.addDef(x); + cp._inputs.add(x); } // Factoring must not widen the result (e.g. correlated And operands). - if( cp.compute().isa(compute()) ) return cp; + if( cp.compute().isa(compute()) ) { + for( int j=1; j<cp.nIns(); j++ ) { + Node x = cp.in(j); + if( x instanceof PhiNode && x.isUnused() ) { + for( Node in : x._inputs ) + if( in!=null ) in.addUse(x); + x = x.peephole(); + cp._inputs.set(j,x); + } + if( x!=null ) x.addUse(cp); + } + return cp; + } for( int i=1; i<nIns(); i++ ) for( int j=1; j<in(i).nIns(); j++ ) if( in(i).in(j)!=null ) addDep(in(i).in(j)); - cp.kill(); + discardTrial(cp); return null; } + // Trial inputs have no matching use edges yet, so ordinary kill is wrong. + private static void discardTrial(Node cp) { + for( Node x : cp._inputs ) + if( x instanceof PhiNode && x.isUnused() ) { + x._inputs.clear(); + x._type = null; + } + cp._inputs.clear(); + } + /** * If only single unique input, return it */ diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java index d528b53b..8c2bc069 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMemPtr; +import com.seaofnodes.simple.type.TypeScalar; /** @@ -22,6 +23,7 @@ public class PtrToIntNode extends Node { @Override protected String format() { return "(i64*)%1"; } @Override public Type compute() { + if( in(1)._type==Type.BOTTOM || in(1)._type==TypeScalar.BOT ) return in(1)._type; return in(1)._type.isHigh() ? TypeInteger.TOP : TypeInteger.BOT; } 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 a6116e93..8a554390 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter29/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.escapes(tret.ret()); + 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/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 47984ed6..4114b47c 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -80,7 +80,7 @@ public class StoreNode extends MemOpNode { Type mem0 = mem()._type; Type ptr0 = ptr()._type; // Validate argument types - if( ptr0.isHigh() ) + if( ptr0.isHigh() || mem0.isHigh() ) return TypeMem.TOP; if( !(mem0 instanceof TypeMem mem) || !(ptr0 instanceof TypeMemPtr ptr) ) @@ -88,16 +88,16 @@ public class StoreNode extends MemOpNode { // Sharpen memory value; required for narrowing stores where the parser // inserts zero/sign masking and somebody reads the TypeMem type. - // A source Load of an unwritten field is kept and checked separately; - // this declared bound does not excuse that earlier read. + // A declared bound must not turn an unwritten value into an + // initialized integer, float, or pointer. Type decl = declaredType(); if( decl instanceof TypeMemPtr ptrType ) decl = ptrType.withPartial(TypeMemPtr.mayBePartial(val)); - if( decl != Type.BOTTOM ) + if( decl != Type.BOTTOM && val!=Type.BOTTOM && val!=TypeScalar.BOT ) { assert decl != Type.TOP; val = val.join(decl); } // A constructor can itself be a field. Its result memory contains // 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 = decl; + if( mem._one && decl instanceof TypeFunPtr && val instanceof TypeFunPtr ) val = decl; // 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. @@ -107,7 +107,10 @@ public class StoreNode extends MemOpNode { if( fld==null && off() instanceof ConFldOffNode off ) fld = off._ts.field(_name); if( _alias!=1 && ptr._one && TypeStruct.startsClzPrefix(ptr._obj._name) && fld!=null && fld._final && decl.isConstant() ) - return TypeMem.make(_alias,val,true,true,true,mem._escFs,mem._escAs).escapesFrom(val); + // 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); // Allocation uses a private TypeMem and nothing else does. This // memory is truly private; a temporary singleton until it escapes - diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index 151a326e..472fff7b 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeScalar; public class ToFloatNode extends Node { @@ -15,6 +16,7 @@ public class ToFloatNode extends Node { @Override public Type compute() { if( in(1)._type.isHigh() ) return TypeFloat.F64.dual(); + if( in(1)._type==Type.BOTTOM || in(1)._type==TypeScalar.BOT ) return in(1)._type; if( in(1)._type == Type.NIL ) return TypeFloat.FZERO; if( in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) return TypeFloat.constant(i0.value()); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java index 33806300..2ae45740 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeScalar; // Truncate toward zero, saturating overflow; NaN converts to zero. public class ToIntegerNode extends Node { @@ -14,6 +15,7 @@ public class ToIntegerNode extends Node { @Override public Type compute() { Type t = in(1)._type; if( t.isHigh() ) return TypeInteger.TOP; + if( t==Type.BOTTOM || t==TypeScalar.BOT ) return t; if( t instanceof TypeFloat tf && tf.isConstant() ) return TypeInteger.constant((long)tf.value()); return TypeInteger.BOT; 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 b8db4f4c..0eda2c62 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java @@ -47,13 +47,12 @@ final class Allocations { if( clz==null ) throw P.error("Unknown struct type '" + ts._name + "'"); Field afld = clz.field("<new>"); - P.construction.allocation(afld==null ? null : (TypeFunPtr)afld._t,ctorArgs,P.loc()); Node alloc; if( afld != null ) { TypeFunPtr tfp = (TypeFunPtr)afld._t; FunNode fun = P._code.link(tfp); alloc = fun==null - ? new FRefNode((TypeStruct.addClzPrefix(typeName)+".<new>").intern(),P.loc()) + ? new FRefNode((TypeStruct.addClzPrefix(typeName)+".<new>").intern(),P.loc()).init() : new FunPtrNode(tfp,P._code._start,fun.ret()).peephole(); } else { if( !ts._fref ) @@ -62,7 +61,7 @@ final class Allocations { for( int i = 0; i<ctorArgs._len; i++ ) sig[i] = ctorArgs.at(i)._type; alloc = new FRefNode((TypeStruct.addClzPrefix(typeName)+".<new>").intern(),P.loc(), - TypeFunPtr.make(false,sig,TypeMemPtr.make(ts))); + TypeFunPtr.make(false,sig,TypeMemPtr.make(ts))).init(); } Ary<Node> args = new Ary<>(Node.class); args.add(P.ctrl()); args.add(P.mem()); @@ -175,6 +174,13 @@ final class Allocations { priv = new ProjNode(cend,2,"#selfMem").peephole(); } + // Hidden construction helpers have only allocator callers. + if( initRet.fun().unknownCallers() ) initRet.fun().removeDeadPath(1); + if( ctor!=null ) { + FunNode cfun = P._code.link(ctor); + if( cfun.unknownCallers() ) cfun.removeDeadPath(1); + } + priv.keep(); for( Field field : ts._fields ) { Type storage = field._t.makeStorage(); @@ -187,8 +193,9 @@ final class Allocations { pub.unkeep(); pub = next; } - priv.unkill(); - ReturnNode ret = (ReturnNode)new ReturnNode(ctl,pub,self,rpc,fun).peephole(); + Node finished = new ConstructNode(self,priv,P.loc(),ctor!=null).peephole(); + priv.unkeep(); + ReturnNode ret = (ReturnNode)new ReturnNode(ctl,pub,finished,rpc,fun).peephole(); fun.setRet(ret); fun._approxUIDs = P._code.UID() - oldUID; P._ref.addFun(P._code,fun); 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 799ca6fc..2720ad3d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java @@ -1,9 +1,7 @@ package com.seaofnodes.simple.parser; -import com.seaofnodes.simple.codegen.Iter; 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 @@ -26,8 +24,8 @@ import com.seaofnodes.simple.util.Ary; * * Incompleteness lives in TypeMemPtr, not a parser provenance graph. Ordinary * Phis carry it around loops, conversions preserve it, and ConstructNode types - * each allocation result from its actual arguments. Source obligations retain - * their operands until the type fixed point, but hold no separate flow facts. + * each allocation result from its actual arguments. Errors belong to the IR + * nodes and are checked at TypeCheck; the parser keeps no source-use lists. * * The qualifier is a two-point lattice: complete meets incomplete to incomplete. * Constructor self and ^ formals seed incomplete; a ^ formal stays restricted @@ -36,7 +34,7 @@ import com.seaofnodes.simple.util.Ary; * while new Child(null) and new Child(oldParent) are complete, even though all * three calls share the same constructor Return. The raw allocator result is * complete after its own fields have been checked; ConstructNode adds the - * caller's restriction and disappears after source checking. + * caller's restriction and disappears after TypeCheck. * * Reading a pointer field through a completed receiver gives a completed view * of that field too: its object's construction could only retain incomplete @@ -46,17 +44,20 @@ import com.seaofnodes.simple.util.Ary; * 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. * - * Iter.types also solves qualifier cycles optimistically. For p = null followed + * The existing SCCP pass solves qualifier cycles optimistically. For p = null followed * by p = new Link(p) in a loop, nothing introduces incompleteness, so the loop * stays complete. A backedge carrying self makes the Phi and its uses incomplete. * Both cases use the ordinary worklist; no recursive Load/Phi/Call query remains. + * A partial-only ConstructNode supplies the body view of self and ^ formals. + * The Parm itself merges callers normally; inlining cannot erase the view. + * 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. */ final class Construction { private final Parser P; boolean _borrowed; // Source ^ parameters; separate compilation is still deferred. - private final Ary<Node> _kept = new Ary<>(Node.class); - private final Ary<Use> _uses = new Ary<>(Use.class); - private final Ary<LoadNode> _reads = new Ary<>(LoadNode.class); Frame _frame; Construction(Parser P) { this.P = P; } @@ -66,7 +67,6 @@ final class Construction { final Node _self; Frame(boolean owner, Node self) { _owner = owner; _self = self; } } - private record Use(Node ctrl, Node value, String operation, Lexer loc) {} Frame enter(FunNode fun, boolean owner) { Frame old = _frame; @@ -74,37 +74,8 @@ final class Construction { return old; } - private Node keep(Node n) { _kept.add(n.keep()); return n; } - - void complete(Node value, String operation, Lexer loc) { - if( !_frame._owner ) return; - _uses.add(new Use(keep(P.ctrl()),keep(value),operation,loc)); - } - - void ordinaryCall(Ary<Node> args, Lexer loc) { - TypeFunPtr sig = args.last()._type instanceof TypeFunPtr tfp ? tfp : null; - for( int i = 2; i<args.size()-1; i++ ) { - if( i==2 && sig!=null && sig.nargs()>0 && sig.arg(0)==TypePtr.PTR ) continue; - complete(args.at(i),"pass to an ordinary function",loc); - } - } - - Node memory(Node ptr, String field, Lexer loc) { - if( own(ptr) ) return selfMem(); - complete(ptr,"read field '"+field+"'",loc); - return P.mem(); - } - - Node loaded(LoadNode load) { - if( _frame._owner ) _reads.add((LoadNode)keep(load)); - return P.peep(load); - } - - void allocation(TypeFunPtr sig, Ary<Node> args, Lexer loc) { - if( !_frame._owner ) return; - for( int i = 0; i<args.size(); i++ ) - if( sig==null || i>=sig.nargs() || !(sig.arg(i) instanceof TypeMemPtr ptr && ptr._partial) ) - complete(args.at(i),"pass to a constructor parameter without '^'",loc); + Node memory(Node ptr) { + return own(ptr) ? selfMem() : P.mem(); } Node selfMem() { @@ -113,7 +84,7 @@ final class Construction { } boolean own(Node ptr) { - while( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) ptr = ptr.in(1); + while( 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; } @@ -124,20 +95,6 @@ final class Construction { else P.storeMem(st,alias,prior); } - void check() { - Iter.types(P._code); - for( LoadNode load : _reads ) - if( load.err()!=null ) throw load.err(); - for( Use use : _uses ) - if( !use.ctrl._type.isHigh() && TypeMemPtr.mayBePartial(use.value._type) ) - throw Parser.error("Cannot "+use.operation+" with an incomplete object",use.loc); - P.structs.checkInitFields(); - for( Node n : _kept ) n.unkeep(); - _kept.clear(); - _uses.clear(); - _reads.clear(); - } - void checkSerializable() { if( _borrowed ) throw P.error("Separate compilation of constructors 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 4d597b8d..50775349 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java @@ -114,7 +114,6 @@ final class Functions { // Unkeep them all for( Node arg : args ) arg.unkeep(); - P.construction.ordinaryCall(args,site); return functionCall(args,site); } @@ -292,7 +291,9 @@ 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 - P._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); + Node parm = new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(t).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); } return fun; diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java index 93c3932b..4d140e55 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java @@ -25,7 +25,6 @@ public class Parser { final Conversions conversions = new Conversions(this); final Construction construction = new Construction(this); - public void checkConstruction() { construction.check(); } public void checkConstructionSerializable() { construction.checkSerializable(); } // Compile driver diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md b/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md index d1125842..3a8e8e64 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md @@ -14,8 +14,8 @@ productions to their entry points. | `Declarations.java` | Bindings, initializers, mutability modifiers, and native declarations. | | `Types.java` | Type syntax, qualified-name lookup, arrays, function types, and forward types. | | `Functions.java` | Function expressions, parameters, arguments, calls, and function entry/return graphs. | -| `Structs.java` | Struct and constructor declarations, field discovery, and initialization checks. | -| `Construction.java` | Source checks for field initialization and incomplete references; its comment explains BOT fields, the TypeMemPtr qualifier, and allocation boundaries. | +| `Structs.java` | Struct and constructor declarations, field discovery, and initialization Stores. | +| `Construction.java` | Selects private self memory during parsing; its comment explains BOT fields, the TypeMemPtr qualifier, and checks deferred to TypeCheck. | | `References.java` | Bare-name and field resolution, implicit receivers, assignments, and forward references. | | `Allocations.java` | Allocation expressions, strings, and declaration-side allocation helpers. | | `ControlFlow.java` | Guarded scope merging shared by `if`, `?:`, `&&`, and `||`. | 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 4851d8b5..737ba4c9 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java @@ -139,13 +139,6 @@ final class References { // Update P._scope.update(name,lift); - // Check for storing into an instance field instead of a local var - int kx = P._scope.kindx(def); // Declaration scope - int fx = P._scope.enclosingFunction(); // Enclosing function scope - Kind kk = P._scope._kinds.at(kx); - if( kx<fx && !(P.structs.inExplicitConstructor() && kx+1==fx && - kk instanceof Kind.Func owner && FunNode.isInstance(owner._name)) ) - P.construction.complete(lift,"store outside the construction group",P.loc()); lift.unkill(); // Return un-lifted expr @@ -200,7 +193,7 @@ final class References { if( fld==null && ts!=null && !TypeStruct.startsClzPrefix(ts._name) ) { Type clz0 = Parser.TYPES.get(TypeStruct.addClzPrefix(ts._name)); if( clz0 instanceof TypeStruct clz && (fld = P.types.latestStruct(clz).field(name)) != null ) { - expr.unkeep(); + expr.unkill(); ts = P.types.latestStruct(clz); expr = P.con(TypeMemPtr.make((byte)2,ts,true)).keep(); } @@ -233,10 +226,6 @@ final class References { if( pre==0 && P.matchOpx('=','=') ) { // Field assignment Node val = P.expressions.parseAssignment().keep(); - if( !P.construction.own(expr) ) { - P.construction.complete(expr,"write through an unfinished reference",site); - P.construction.complete(val,"store into an ordinary object",site); - } // Lift value for store Node lift = fld==null ? val : new ConvertNode(fld._t,val).peephole(); // Memory for store, post assignment expression @@ -254,19 +243,18 @@ final class References { } // Memory for load - Node mem = P.construction.memory(expr,name,site); + Node mem = P.construction.memory(expr); // Loading from a constant array, the declared type is the // meet-over-elements and not the array itself. if( name=="[]" && decl instanceof TypeConAry conary ) decl = conary.elem(); // Load field - Node load = P.construction.loaded(new LoadNode(P.loc(),name,alias,P.ctrl(),mem,expr,off)); + Node load = P.peep(new LoadNode(P.loc(),name,alias,P.ctrl(),mem,expr,off)); // Check for assign-update, "ptr.fld += expr" or "ary[idx]++" char ch = pre==0 ? P._lexer.matchOperAssign() : (char)pre; if( ch!=0 ) { - if( !P.construction.own(expr) ) P.construction.complete(expr,"write through an unfinished reference",site); if( fld!=null && decl==Type.BOTTOM ) throw P.error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor" ); Node op = P.expressions.opAssign(ch,load, decl ).keep(); @@ -315,7 +303,10 @@ final class References { for( FRefNode fref : _frefs ) { if( fref.nIns() != 1 && fref._con == FRefNode.FREF_TYPE ) continue; CompUnit cu = ParseAll.findCompUnitOrThrow(P._code,P._ref,fref._name); - fref._con = TypeMemPtr.make((byte)2,TypeStruct.make(TypeStruct.addClzPrefix(cu._cname),true),true); + // Name lookup may already know this class's fields. Do not replace + // that information with an empty placeholder before Iter runs. + if( fref._con==FRefNode.FREF_TYPE ) + fref.liftType(TypeMemPtr.make((byte)2,TypeStruct.make(TypeStruct.addClzPrefix(cu._cname),true),true)); frefs.push(fref); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java index 3360d85e..a5262440 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java @@ -54,13 +54,16 @@ final class Structs { : TypeStruct.make(clzName,false,fld,ctorFld); if( flag!=null ) ts = ts.add(flag); TypeFunPtr alloc = P.allocations.makeAllocator((TypeStruct)Parser.TYPES.get(fullName),ret,ctorFld); + // The visible constructor name denotes allocation, not the hidden initializer. + sig = alloc; + ts = ts.replace(fld.makeFrom(alloc)); ts = ts.add(Field.make("<new>",alloc,P._code.alias(P._ref._cname),true)); Parser.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. - P._scope.define(typeName, sig, true, new FunPtrNode(sig,P._code._start,ret).peephole(), P.loc()); + P._scope.define(typeName, sig, true, new FunPtrNode(sig,P._code._start,P._code.link(alloc).ret()).peephole(), P.loc()); Var binding = P._scope.lookup(typeName); declareField(binding,P._scope.in(binding),false); @@ -256,42 +259,6 @@ final class Structs { P.functions._returnScope.mem(mmm); } - // addReturn already merged every exit. Inspect the completed helpers, - // after parsing has discovered all fields and torn down their scopes. - void checkInitFields() { - P._code._stop.walk(n -> { - if( n instanceof ReturnNode ret && ret.fun().isInstance() ) checkInitFields(ret); - return null; - }); - } - - private void checkInitFields(ReturnNode init) { - if( init.ctrl()._type.isHigh() || init.expr()._type.isHigh() ) return; - TypeStruct ts = ((TypeMemPtr)init.fun().sig().arg(0))._obj; - TypeStruct clz = (TypeStruct)Parser.TYPES.get(TypeStruct.addClzPrefix(ts._name)); - Field ctor = clz==null ? null : clz.field("<ctor>"); - // The older same-named function binding is parsed immediately, so - // fields declared after it are supplied by the declaration initializer. - Field legacy = ts.field(initFieldName(ts._name)); - if( ctor!=null ) checkInitFields(ts,init,P._code.link((TypeFunPtr)ctor._t).ret()); - if( legacy!=null && legacy._t instanceof TypeFunPtr sig ) - checkInitFields(ts,init,P._code.link(sig).ret()); - else if( ctor==null ) checkInitFields(ts,init,init); - } - - private void checkInitFields(TypeStruct ts, ReturnNode init, ReturnNode ret) { - if( ret.ctrl()._type.isHigh() || ret.expr()._type.isHigh() ) return; - for( Field fld : ts._fields ) { - if( fld._extern ) continue; - Type mem = ret.expr()._type; - Field actual = mem instanceof TypeMem tm && tm._t instanceof TypeStruct shape ? shape.field(fld._fname) : null; - if( actual==null || actual._t==TypeScalar.BOT || actual._t==Type.BOTTOM ) - throw Parser.error("'"+ts._name+"' is not fully initialized, field '"+fld._fname+ - (ret==init ? "' needs to be set in a constructor" : - "' is only partially set in the constructor"),ret.fun()._loc); - } - } - // Instance declarations establish field metadata and emit their default // Stores immediately. Required fields emit no Store until assigned. void declareField(Var var, Node value, boolean uninit) { 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 c72740a9..79543e56 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -99,6 +99,16 @@ 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) { + TypeStruct ts = t instanceof TypeMemPtr ptr ? ptr._obj : t instanceof TypeStruct obj ? obj : null; + if( ts!=null && ts._open && ts._fref && !ts.isAry() ) + return makeFrom(XInt.meet(_escFs,defaults._escFs),XInt.meet(_escAs,defaults._escAs)); + return escapesFrom(t); + } public TypeMem escapesAliases(Type t) { return make(_alias,_t,_one,_clz,_final, _escFs, escapeAlias(_escAs,t)); } 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 d0ac55aa..d699e365 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -123,13 +123,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. + // Hidden initializer/constructor helpers receive private memory. Only the + // allocator has a source-callable signature; TypeMem is not a source type. public boolean hiddenInit(Field fld) { - if( field("<ctor>") == null || !startsClzPrefix(_name) ) return false; - int idx = _name.lastIndexOf('.'); - String name = _name.substring(idx<0 ? CLZ.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/chapter29/src/test/java/com/seaofnodes/simple/ArithNodeTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ArithNodeTest.java index b28a6af3..1e6c6fc0 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/ArithNodeTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/ArithNodeTest.java @@ -15,7 +15,8 @@ public class ArithNodeTest { Node zero = ConstantNode.seed(TypeInteger.ZERO); for( Node op : new Node[]{new MulNode(x,zero,(byte)1),new AndNode(null,x,zero), new SubNode(x,x,(byte)1),new BoolNode.EQ(x,x,(byte)1), - new BoolNode.NE(x,x,(byte)1),new BoolNode.ULT(x,x),new NotNode(x)} ) { + new BoolNode.NE(x,x,(byte)1),new BoolNode.ULT(x,x),new NotNode(x), + new ConvertNode(TypeInteger.BOT,x),new ToIntegerNode(x),new ToFloatNode(x),new PtrToIntNode(x)} ) { assertSame(op.label(),TypeScalar.BOT,op.compute()); Node replacement = op.idealize(); assertTrue(op.label(),replacement==null || !replacement.compute().isConstant()); diff --git a/chapter29/src/test/java/com/seaofnodes/simple/CallEndTest.java b/chapter29/src/test/java/com/seaofnodes/simple/CallEndTest.java index a174bdf7..f57fd96a 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/CallEndTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/CallEndTest.java @@ -7,6 +7,60 @@ import org.junit.Test; import static org.junit.Assert.*; public class CallEndTest { + // An unknown value can become a private object or callback. Both escape + // sinks must reserve those possibilities before the value is known. + @Test public void testUnknownEscapesRefineToPrivateValues() { + CodeGen code = new CodeGen("return 0;").parse(); + code._phase = CodeGen.Phase.IterPostOpto; + StopCUNode stop = code.compunit()._stop; + stop._type = TypeTuple.make(Type.CONTROL,TypeMem.START,Type.BOTTOM); + ReturnNode ret = (ReturnNode)stop.in(0); + TypeFunPtr callback = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,TypeInteger.BOT,100); + TypeMemPtr object = TypeMemPtr.make(TypeStruct.make("_Private",false, + Field.make("callback",callback,100,false))); + code.externFunc(101,"retain"); + TypeFunPtr retain = TypeFunPtr.make1((byte)2,true, + new Type[]{TypeScalar.BOT},TypeInteger.BOT,101); + Node value = ConstantNode.raw(TypeScalar.BOT); + CallNode call = new CallNode(null,ConstantNode.raw(Type.CONTROL), + ConstantNode.raw(TypeMem.START),value,ConstantNode.raw(retain)); + call._type = Type.CONTROL; + GlobalEscapeNode global = new GlobalEscapeNode(); + global._type = TypeMem.START; + for( Type broad : new Type[]{Type.BOTTOM,TypeScalar.BOT} ) { + value._type = broad; + ret._type = TypeTuple.make(Type.CONTROL,TypeMem.START,broad); + TypeTuple unknownStop = stop.compute(); + TypeMem unknownGlobal = global.compute(); + assertSame(XInt.FULL,((TypeMem)unknownStop.mem())._escFs); + assertSame(XInt.FULL,((TypeMem)unknownStop.mem())._escAs); + assertSame(XInt.FULL,unknownGlobal._escFs); + assertSame(XInt.FULL,unknownGlobal._escAs); + for( Type precise : new Type[]{object,callback} ) { + assertTrue(precise.isa(broad)); + value._type = precise; + ret._type = TypeTuple.make(Type.CONTROL,TypeMem.START,precise); + assertTrue(stop.compute().isa(unknownStop)); + assertTrue(global.compute().isa(unknownGlobal)); + } + } + } + + @Test public void testUnresolvedOffsetInInlineBody() { + CodeGen code = new CodeGen("val f = { int[] data -> return data#; }; return f;").parse(); + for( FunNode fun : code._linker ) + if( fun!=null && "f".equals(fun._name) ) { + // Keep the offset unresolved: an early inline must copy it + // with its data parameter, not share it with the old body. + FldOffNode off = new FldOffNode(fun.parm(3),"<<",null).init(); + fun.ret().setDef(2,off); + assertSame(Type.BOTTOM,off._type); + assertTrue("Unresolved field offset belongs to the function",fun.body().get(off._nid)); + return; + } + fail("Missing test function"); + } + @Test public void testReturnWideningMonotonicity() { new CodeGen("return 0;").parse(); TypeFunPtr sig = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,TypeInteger.I32,100); diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 1a954110..eadaf9fe 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -158,7 +158,7 @@ else return v; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Test.Vector2D; return MemTop; return Test.Vector2D; ]", code.print()); + assertEquals("Stop[ return Test.Vector2D; return Test.Vector2D; ]", code.print()); } @Test @@ -196,7 +196,7 @@ while (arg) { return bar.a; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MemTop; return Test.Bar; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return Test.Bar; ]", code.print()); } @Test @@ -245,10 +245,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 @@ -318,7 +318,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 MemTop; return Test.Iter; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return Test.Iter; ]", code.print()); } @@ -337,7 +337,7 @@ while(arg) { return ret; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MemTop; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return Test.s0; ]", code.print()); } @Test @@ -390,7 +390,7 @@ s0 b = new s0(); return a.x * 100 + b.x * 10 + cnt; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return 112; return MemTop; return Test.s0; ]", code.print()); + assertEquals("Stop[ return 112; return Test.s0; ]", code.print()); } @@ -433,7 +433,7 @@ else return new s0; if(new s0.f0) return 0; """); code.driver(CodeGen.Phase.TypeCheck); - assertEquals("Stop[ return Test.s0; return MemTop; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Test.s0; return Test.s0; ]", code.print()); } @Test @@ -461,7 +461,7 @@ s0 v1 = v0; return v1; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return (const)Test.s0; return MemTop; return Test.s0; ]", code.print()); + assertEquals("Stop[ return (const)Test.s0; return Test.s0; ]", code.print()); } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 156e091d..c6817308 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -79,6 +79,19 @@ return f0.i.f.i.i; assertEquals("return 17;", code.print()); } + @Test public void testPrivateRecursiveReturn() { + CodeGen code = new CodeGen(""" + struct _A { !Test._B? !b; }; + struct _B { !_A? !a; }; + !_A !_a = new _A; + !_B !_b = new _B; + _a.b = _b; + _b.a = _a; + return _a.b.a.b; + """).driver(CodeGen.Phase.TypeCheck); + assertEquals("return Test._B;",code.print()); + } + @Test public void testNullRef0() { CodeGen code = new CodeGen( @@ -101,7 +114,7 @@ N n = new N(new M); return n.next; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return (const)Test.M; return MemTop; return Test.M; return MemTop; return MemTop; return Test.N; ]", code.print()); + assertEquals("Stop[ return (const)Test.M; return Test.M; return Test.N; ]", code.print()); } @Test diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 1e99bcd9..98197b77 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -293,7 +293,9 @@ struct A { !B !b; new A = { -> A x = new A; """); try { code.driver(CodeGen.Phase.TypeCheck); fail(); } - catch( Exception e ) { assertEquals("Field 'b' might not be initialized",e.getMessage()); } + // The unused constructor return value can die; its unwritten field + // still fails the completion check at TypeCheck. + catch( Exception e ) { assertEquals("'Test.A' is not fully initialized, field 'b' is only partially set in the constructor",e.getMessage()); } } @Test @@ -305,7 +307,7 @@ A x = new A; "new A = { -> }; !B !b;", // Field declared later } ) { CodeGen code = new CodeGen("struct B {}; struct A { "+fields+" }; return 0;"); - try { code.parse(); fail(fields); } + try { code.driver(CodeGen.Phase.TypeCheck); fail(fields); } catch( Parser.ParseException e ) { assertEquals("'Test.A' is not fully initialized, field 'b' is only partially set in the constructor",e.getMessage()); } } } @@ -314,7 +316,7 @@ A x = new A; public void testDefaultConstructorFields() { for( String field : new String[] { "!B !b;", "!B !b;" } ) { CodeGen code = new CodeGen("struct B {}; struct A { "+field+" }; return new A;"); - try { code.parse(); fail(field); } + try { code.driver(CodeGen.Phase.TypeCheck); fail(field); } catch( Parser.ParseException e ) { assertEquals("'Test.A' is not fully initialized, field 'b' needs to be set in a constructor",e.getMessage()); } } for( String fields : new String[] { @@ -550,7 +552,7 @@ struct _A { }; return new _A; """); - code.driver(CodeGen.Phase.FinalizeIR); + code.driver(CodeGen.Phase.TypeCheck); assertEquals("return Test._A;", code.print()); assertEquals("Test._A{f1=null,f2=null}", Eval2.eval(code,0)); } @@ -565,7 +567,7 @@ struct _A { }; return new _A(new !B?[0]).array_of_b; """); - code.driver(CodeGen.Phase.FinalizeIR); + code.driver(CodeGen.Phase.TypeCheck); assertEquals("return []*B?;", code.print()); assertEquals("*B {}?[]", Eval2.eval(code,0)); } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter19Test.java index e6249d82..50ca8922 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter29/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 MemTop; return MemTop; 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/chapter29/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 66a318ae..6cf92dc3 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -79,6 +79,7 @@ return f(s); @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); } + @Test public void testAllocatorCommutativeLoop() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativeLoop(); } @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); } @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); } @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java index cea6ca91..b5bbfce8 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java @@ -21,7 +21,7 @@ public class ConstructionGroupTest { private void rejects(String src, String message) { try { - new CodeGen(src).parse(); + new CodeGen(src).driver(CodeGen.Phase.TypeCheck); fail("Accepted: "+src); } catch( Parser.ParseException e ) { assertTrue(e.getMessage(),e.getMessage().contains(message)); @@ -40,12 +40,25 @@ public class ConstructionGroupTest { .driver(CodeGen.Phase.Encoding,TestC.CPU_PORT,TestC.CALL_CONVENTION,true,false,0); } - @Test public void testNoIncompleteLookupOrEscape() { + @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"); - rejects(parent("payload = 1; child = new Child(self); int x = child.parent==null;")+"return 0;","incomplete object"); + } + + @Test public void testInitializerFeedsConstructor() { + // Private memory comes from the initializer's real call edge. An + // unknown-caller default must neither erase it nor poison its fields. + String src = "struct C { int !x = 7; new C = { -> x = x+1; }; }; return new C().x;"; + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.TypeCheck); + assertEquals("8",Eval2.eval(code,0)); + assertEquals("Stop[ return 8; return Test.C; ]",code.print()); + } + } + + @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"); @@ -54,7 +67,7 @@ public class ConstructionGroupTest { 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 = { -> int y = next.x; x = 7; }; }; return 0;", + rejects("struct C { C next = self; int~ x; new C = { -> x = next.x; }; }; return new C().x;", "incomplete object"); } @@ -115,14 +128,16 @@ public class ConstructionGroupTest { @Test public void testDeclaredQualifierAndOwnReceiver() { // A complete caller does not grant permission to read a ^ formal. - rejects(""" + 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(""" struct Parent { int payload = 7; }; struct Child { int value; - new Child = { Parent ^par -> value = par.payload; }; + new Child = { Parent ^par -> BODY }; }; return new Child(new Parent).value; - ""","incomplete object"); + """.replace("BODY",body),"incomplete object"); // The self exception belongs to the receiver, not every pointer of its class. rejects(""" struct C { @@ -132,4 +147,15 @@ public class ConstructionGroupTest { return new C(new C(null)).value; ""","incomplete object"); } + + @Test public void testUnusedIncompleteReadCanDie() { + String src = """ + struct Parent { int payload = 7; }; + struct Child { int value = 5; + new Child = { Parent ^par -> int unused = par.payload; }; + }; + return new Child(new Parent).value; + """; + assertEquals("5",Eval2.eval(new CodeGen(src).driver(CodeGen.Phase.TypeCheck),0)); + } } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/ConstructorCompletionTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ConstructorCompletionTest.java index cbb9ee37..a5fc236b 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/ConstructorCompletionTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/ConstructorCompletionTest.java @@ -30,10 +30,10 @@ public class ConstructorCompletionTest { "int~ x; int y = x*0; new A = { -> x = 7; };", // Constructor entry includes the initializer's early return. // Its later Store of 2 must not excuse the earlier read of x. - "int~ x; if(arg) return 0; x = 1; new A = { -> int y = x; x = 2; };" + "int~ x; int seen; if(arg) return 0; x = 1; new A = { -> seen = x; x = 2; };" } ) try { - new CodeGen("struct A { "+body+" }; return 0;").parse(); + new CodeGen("struct A { "+body+" }; return 0;").driver(CodeGen.Phase.TypeCheck); fail("Read a field before its constructor wrote it"); } catch( Parser.ParseException e ) { assertTrue(e.getMessage(),e.getMessage().contains("might not be initialized")); @@ -51,7 +51,7 @@ public class ConstructorCompletionTest { private void rejects(String fields, String field, boolean explicit) { String src = "struct B {}; struct A { "+fields+" }; return 0;"; try { - new CodeGen(src).parse(); + new CodeGen(src).driver(CodeGen.Phase.TypeCheck); fail(src); } catch( Parser.ParseException e ) { assertEquals("'Test.A' is not fully initialized, field '"+field+ @@ -95,8 +95,8 @@ public class ConstructorCompletionTest { @Test public void testNonreturningPaths() { // An initializer parsed in dead enclosing code can have TOP memory // rather than a struct-shaped result. - new CodeGen("while(false) { struct A { int x; }; } return 0;").parse(); - new CodeGen("struct A { int~ x; new A = { -> while(true) {} }; }; return 0;").parse(); + new CodeGen("while(false) { struct A { int x; }; } return 0;").driver(CodeGen.Phase.TypeCheck); + new CodeGen("struct A { int~ x; new A = { -> while(true) {} }; }; return 0;").driver(CodeGen.Phase.TypeCheck); rejects("int~ x; new A = { -> if(arg) return 0; while(true) {} };","x",true); CodeGen code = new CodeGen(""" struct A { @@ -113,7 +113,7 @@ public class ConstructorCompletionTest { // Its Return lacks that field, so completion must consult <init> too. rejects("val A = { -> }; B b;","b",true); rejects("int~ x; val A = { -> if(arg) x = 1; };","x",true); - new CodeGen("struct B {}; struct A { val A = { -> }; B b = new B; }; return 0;").parse(); - new CodeGen("struct A { val A = { -> while(true) {} }; int~ x; }; return 0;").parse(); + new CodeGen("struct B {}; struct A { val A = { -> }; B b = new B; }; return 0;").driver(CodeGen.Phase.TypeCheck); + new CodeGen("struct A { val A = { -> while(true) {} }; int~ x; }; return 0;").driver(CodeGen.Phase.TypeCheck); } } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter29/src/test/java/com/seaofnodes/simple/TypeTest.java index 68239396..16b75fdc 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -7,6 +7,26 @@ import static org.junit.Assert.assertSame; public class TypeTest { + @Test public void testOpaqueExternalEscapes() { + TypeMem defaults = TypeMem.START.makeFrom(XInt.make(2),XInt.make(3)); + TypeMem prior = TypeMem.START.makeFrom(XInt.make(5),XInt.make(7)); + TypeMemPtr opaque = TypeMemPtr.makeNullable(TypeStruct.forward("OpaqueExternal")); + TypeMem escaped = prior.escapesFrom(opaque,defaults); + assertSame(XInt.meet(prior._escFs,defaults._escFs),escaped._escFs); + assertSame(XInt.meet(prior._escAs,defaults._escAs),escaped._escAs); + // Before type closure the same name might still resolve locally. + assertSame(XInt.FULL,prior.escapesFrom(opaque,TypeMem.BOT)._escFs); + for( Type unknown : new Type[]{Type.BOTTOM,TypeScalar.BOT,TypePtr.PTR, + TypeMemPtr.make(TypeStruct.open("LocalStillOpen"))} ) { + TypeMem broad = prior.escapesFrom(unknown,defaults); + assertSame(XInt.FULL,broad._escFs); + assertSame(XInt.FULL,broad._escAs); + } + // Concrete private callbacks must not be restricted to public names. + TypeFunPtr callback = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,TypeInteger.BOT,11); + assertSame(XInt.make(11),TypeMem.START.escapesFrom(callback,defaults)._escFs); + } + // Aggregate finality is carried by its fields. Canonicalizing the unused // aggregate bit must commute with dual, even for named (non-high) structs. @Test public void testAggregateMemoryDual() { diff --git a/chapter29/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter29/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 292f1ae7..adbb10a5 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.SubX86; import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; import com.seaofnodes.simple.type.TypeInteger; import static org.junit.Assert.*; @@ -124,6 +125,30 @@ public class RegAllocTestSupport { assertTrue(BuildLRG.run(0,new RegAlloc(code))); } + public static void commutativeLoop() { + for( String op : new String[]{"+","*","^","&","|"} ) + for( boolean reversed : new boolean[]{false,true} ) { + String src = "return { u8[] data -> int h = 1; for(int i = 0; i < data#; i++) " + + "h = ((h<<5)-h) "+op+" data[i]; return h; };"; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.LocalSched,"x86_64_v2","SystemV"); + // Exercise both destructive operands regardless of ideal-node + // numbering. The shifted value overlaps the old loop hash. + int found = 0; + for( CFGNode bb : code._cfg ) + for( Node n : bb.outs() ) + if( n instanceof MachNode mach && mach.commutes() && mach.twoAddress()==1 && + (n.in(1) instanceof SubX86 || n.in(2) instanceof SubX86) ) { + if( (n.in(1) instanceof SubX86)==reversed ) n.swap12(); + found++; + } + assertEquals(op,1,found); + code.driver(CodeGen.Phase.RegAlloc,"x86_64_v2","SystemV"); + checkRegisters(code); + assertEquals(op+" reversed="+reversed,8,code._regAlloc._spillScaled); + code.encode(); + } + } + private static class CallOp extends CallNode implements MachNode { CallOp(Node ctrl, Node def) { super(null,ctrl,null,def,def); } @Override public RegMask regmap(int i) { return i==2 ? A : i==3 ? B : null; } |