diff options
Diffstat (limited to 'chapter28b/src/main/java/com')
20 files changed, 308 insertions, 153 deletions
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 45d65514..46a726b3 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -29,6 +29,7 @@ public class ClassInitDependencies { private final int[] _lows; private final int[] _stk ; private int _sp; + private int _pre; // Build once; tests can inspect the graph independently of cycle checking. @@ -50,6 +51,24 @@ public class ClassInitDependencies { if( fun!=null && !fun.isDead() ) // Visit function and collect direct class touches and callees _edgess[fun.sig().fidx()] = walk(code,fun,work,iset,visit,null); + + // FIDX zero represents escapees - an unknown callee, including a + // callback supplied by another compilation. Its code can call any + // exposed function. Keep this edge in saved summaries so later + // applications contribute their callbacks too. + + // Filter escapees by dead and not a class (class initializers are + // reached through bodies, not directly callable function pointers). + int[] escaped = ((TypeTuple)code._stop._type).mem()._escFs; + AryInt callees = new AryInt(); + // An imported Stop can still carry FULL (only local bodies have edges) + // so limit by existing FIDXs. + int limit = code._linker._len; + for( int fidx = XInt.next(escaped,0,limit); fidx >= 0; fidx = XInt.next(escaped,fidx,limit) ) { + FunNode fun = code.link(fidx); // Discard dead bodies and external C functions. + if( fun!=null && !fun.isClz() ) callees.push(fidx); + } + _edgess[0] = callees.isEmpty() ? null : callees.asAry(); visit.clear(); } @@ -62,8 +81,8 @@ public class ClassInitDependencies { assert visit.isEmpty(); // needs a visit set, because loops assert work .isEmpty(); // needs a worklist, because DAG, parallel explore paths - // Keep the structural parent prerequisite even if a known-true flag - // folds the check in the child's body. Cycles still require diagnosis. + // Children require their parents to init first; + // add child->parent edge if( fun.isClz() && fun._compunit._par != null ) iset.put(code.link(fun._compunit._par).sig().fidx(),1); @@ -86,9 +105,12 @@ public class ClassInitDependencies { // Calls union all their fptr fidxs into the callee set if( cfg instanceof CallNode call && call.fptr()._type instanceof TypeFunPtr fp ) { - assert !XInt.isHigh(fp.fidxs()) && fp.nfcns()>0; // Call is alive with valid targets + if( XInt.isHigh(fp.fidxs()) ) { + iset.put(0,1); + if( sites!=null && sites.atX(0)==null ) sites.setX(0,call._loc); + } // Union call targets into the callee set - for( int dstx = XInt.next(fp.fidxs(),0); dstx>=0; dstx=XInt.next(fp.fidxs(),dstx) ) { + else for( int dstx = XInt.next(fp.fidxs(),0); dstx>=0; dstx=XInt.next(fp.fidxs(),dstx) ) { iset.put(dstx,1); if( sites!=null && sites.atX(dstx)==null ) sites.setX(dstx,call._loc); } @@ -115,10 +137,10 @@ public class ClassInitDependencies { public String check() { Arrays.fill(_pres,0); _sp = 0; - _pres[0] = 1; // Preorders stored in pres[0] and start at 1 + _pre = 1; int idx = -1; - for( int fidx = 1; fidx < _edgess.length; fidx++ ) + for( int fidx = 0; fidx < _edgess.length; fidx++ ) if( _pres[fidx] == 0 && // Already visited (idx = scc(fidx)) != -1 ) // And found a cycle return report(idx); // Report cycle @@ -155,7 +177,7 @@ public class ClassInitDependencies { FunNode fun = _code.link(src); Arrays.fill(sites._es,null); sites.clear(); - walk(_code,fun,work,iset,visit,sites); + if( fun!=null ) walk(_code,fun,work,iset,visit,sites); if( _edgess[src]!=null ) for( int dst : _edgess[src] ) if( members.get(dst) ) { @@ -163,7 +185,7 @@ public class ClassInitDependencies { Parser.Lexer loc = sites.atX(dst); if( loc!=null && loc._cu!=null ) sb.p('\n').p(SourceError.format(loc._cu,loc.pos(),"cyclic class initialization")); - else if( fun.isClz() && fun._compunit._par==_code.link(dst)._compunit ) + else if( fun!=null && fun.isClz() && dst!=0 && fun._compunit._par==_code.link(dst)._compunit ) sb.p("\n parent initialization requirement"); } } @@ -171,6 +193,7 @@ public class ClassInitDependencies { } private String name(int fidx) { + if( fidx==0 ) return "unknown call"; FunNode fun = _code.link(fidx); String owner=fun._compunit._cname; if( fun.isClz() ) return owner; @@ -181,7 +204,7 @@ public class ClassInitDependencies { // Tarjan SCC int scc( int fidx ) { // Assign pre-order number - _lows[fidx] = _pres[fidx] = _pres[0]++; + _lows[fidx] = _pres[fidx] = _pre++; _stk[_sp++] = fidx; // walk outbound edges if( _edgess[fidx]!=null ) { diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 07ca7e2b..24338927 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -497,35 +497,11 @@ public class CodeGen { public CodeGen iterPostOpto() { return phase(Phase.IterPostOpto, _phase==Phase.Opto, () -> _iter.iterate(this)); } - // Materialize a requested inline candidate at an empty worklist, then - // reanalyze before CallEnd decides whether the real body should inline. + // Materialize an inline candidate at an empty worklist. Loading queues + // the new body and affected callers before CallEnd considers inlining. public void loadForInline(CompUnit cu) { assert _phase==Phase.IterPostOpto && _iter._work.isEmpty(); ParseAll.loadCompUnit(this,cu); - analyzeImports(); - } - - private void analyzeImports() { - Phase prior = _phase; - try { - _phase=Phase.Iter; - // Newly loaded calls can revive previously uncalled summaries. - // Restore their pessimistic inputs before solving; SCCP removes - // the unknown-caller edges again once all calls are available. - for( FunNode fun : _linker ) - if( fun!=null && fun.summary()!=null ) { - Opto.linkStart(this,fun); - for( Node use : fun._outputs ) - if( use instanceof ParmNode parm ) parm._type=parm._declaredType; - } - for( CompUnit cu : _compunits.values() ) { - ProjNode mem = cu._start.proj(1); - if( mem!=null && mem.iskeep() ) mem.unkeep(); - } - Iter.run(this); - _phase=Phase.Opto; - Opto.opto(this); - } finally { _phase=prior; } } // Evaluation needs implementations even for calls left out of line. E.g., @@ -544,7 +520,6 @@ public class CodeGen { loaded=true; } if( !loaded ) return; - analyzeImports(); if( _phase.ordinal()<Phase.FinalizeIR.ordinal() ) return; Phase prior = _phase; try { @@ -562,7 +537,6 @@ public class CodeGen { Ary<CompUnit> units = new ClassInitDependencies(this).cycleImports(); if( units.isEmpty() ) return; for( CompUnit cu : units ) ParseAll.loadCompUnit(this,cu); - analyzeImports(); Phase prior = _phase; try { _phase=Phase.IterPostOpto; @@ -576,7 +550,7 @@ public class CodeGen { public CodeGen finalizeIR() { return phase(Phase.FinalizeIR, _phase==Phase.IterPostOpto, () -> FinalizeIR.run(this)); } // Root a surviving function without claiming that it has unknown callers. - void keepInCompUnit(FunNode fun) { + public void keepInCompUnit(FunNode fun) { StopCUNode stop = fun._compunit._stop; if( stop._inputs.find(fun.ret()) == -1 ) add(stop).addDef(fun.ret()); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java index 923486c6..aeb64543 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java @@ -32,8 +32,11 @@ abstract class FinalizeIR { code.keepInCompUnit(fun); } for( CompUnit cu : code._compunits.values() ) { + // A private unit may have no unknown callers, hence no Fun using + // its Start. Keep the wrapper until Unlink installs scheduling hooks. + if( !cu._start.iskeep() ) cu._start.keep(); ProjNode mem = cu._start.proj(1); - if( mem != null ) code.add(mem.unkeep()); + if( mem!=null && mem.iskeep() ) code.add(mem.unkeep()); } // Stable print order: initializers first, then other Returns by NID. for( Node stop : code._stop._inputs ) diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java index a9f4206a..1ce5b051 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -2,10 +2,11 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; // Establish a pessimistic fixed point after parsing/loading. Later Iter runs // reuse the worklist and types produced by the preceding phase. -abstract class Iter { +public abstract class Iter { static void run(CodeGen code) { // The phase shift closes all parser-in-progress states and freezes // unknown external inputs. Imported nodes carry post-Opto escape @@ -58,4 +59,40 @@ abstract class Iter { } return t; } + + // Saved types belong to a different caller context. Reset only the new + // graph, then repair any affected bounds before peepholes consume them. + static void imports(CodeGen code, Ary<Node> nodes) { + 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. + public static void repair(CodeGen code) { + // Gather changes for a normal IterPeeps once the graph has its + // monotonicity property back. + Ary<Node> peeps = new Ary<>(Node.class); + Node n; + while( (n = code._iter._work.pop())!=null ) { + if( n.isDead() ) continue; + peeps.add(n); + // Meet over existing and new; only drops + Type t = n._type.meet(n.compute()); + if( t==n._type ) continue; + n._type = t; + code.addAll(n._outputs); + n.moveDepsToWorklist(); + } + code.addAll(peeps); + } } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index dc5742f7..19450e86 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -56,9 +56,8 @@ abstract public class Opto { } - // If wholeWorld, remove the Start inputs to functions - they are not - // called unless they get linked (hence go dead and can be removed). If - // not wholeWorld, keep only public methods (and not the std lib). + // Only entry initializers start with unknown callers. Discover every + // other function through calls or escaping values during SCCP. private static void unlinkStart(CodeGen code) { // Keep the Start & Start.ProjMem alive even as we remove all uses for( CompUnit cu : code._compunits.values() ) { @@ -66,18 +65,13 @@ abstract public class Opto { if( mem!=null ) mem.keep(); } - // Iterate the Stop-of-Stops + // Iterate all functions. + // TODO: use CodeGen _link list for( Node stop : code._stop._inputs ) { for( int i=0; i<stop.nIns(); i++ ) { ReturnNode ret = (ReturnNode)stop.in(i); FunNode fun = ret.fun(); - // Start is a semantic unknown-caller edge. Public functions - // keep it; closed-world functions must be reached by a - // concrete Call edge discovered during SCCP. Initializers, - // including private/imported ones, are called by opaque CLInit - // obligations whose Call edges are introduced only in Lower. - if( !fun.isClz() && - !code.publicFIDX(fun.sig().fidx()) && + if( !fun.isRoot() && fun.in(1) instanceof StartNode ) { fun.removeDeadPath(1); // Unhook from Stop without treating the ReturnNode as @@ -171,6 +165,7 @@ abstract public class Opto { if( n.isDead() ) continue; count++; Type oval = n._type, nval = n.compute(); + if( n instanceof CLInitNode init ) init.link(); 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); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 016e4062..996d5b8b 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -313,6 +313,10 @@ public abstract class ParseAll { if( old.in(i) instanceof CallNode call ) { call.unlink(old,i--); call.link(fun); + } else if( old.in(i) instanceof CProjNode proj && proj.in(0) instanceof CLInitNode init ) { + init.unlink(); + init.link(); + i--; } old.ret().unkeep().subsume(fun.ret()); } @@ -324,11 +328,17 @@ public abstract class ParseAll { code._stop.addDef(lstopcu); lstart.subsume(code._start); if( oldStart!=null && oldStart!=cunit._start ) { + if( oldStart.iskeep() ) oldStart.unkeep(); int idx = code._stop._inputs.find(oldStop); if( idx!=-1 ) code._stop.delDef(idx); oldStart.subsume(cunit._start); } - code.addAll(elf._nodes); + // Saved types describe the library's original compilation. Repair + // only the newly loaded graph; ordinary dependencies carry changes + // into its callers without restarting whole-program analysis. + ProjNode startMem = cunit._start.proj(1); + if( startMem!=null && !startMem.iskeep() ) startMem.keep(); + Iter.imports(code,elf._nodes); // Add the new top-level loaded class Parser.TYPES.put(cunit._clz._name,cunit._clz); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java index 17f8107a..fe3710e1 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java @@ -19,6 +19,7 @@ abstract class Unlink { } for( Node n : nodes ) { if( n instanceof CallNode call ) call.unlink_all(); + if( n instanceof CLInitNode init ) init.unlink(); if( n instanceof FunPtrNode ptr && ptr.ret()!=null ) ptr.setDef(1,null); } for( FunNode fun : funs ) { @@ -34,6 +35,8 @@ abstract class Unlink { } restoreRPC(fun); } + for( Node n : nodes ) + if( n instanceof StartCUNode unitStart ) releaseStart(unitStart); // A summary is a dispatch target, not a schedulable implementation. // Retain its own wrapper graph without including it in this schedule. for( int i = 0; i<stop.nIns(); i++ ) { @@ -41,7 +44,7 @@ abstract class Unlink { boolean summary = false; for( Node r : unit._inputs ) summary |= ((ReturnNode)r).fun().summary()!=null; - if( summary ) { + if( summary || unit.nIns()==0 ) { unit.start().setDef(0,null); stop.delDef(i--); } @@ -136,6 +139,8 @@ abstract class Unlink { ((CallNode)fun.in(i)).unlink(fun,i--); restoreRPC(fun); } + for( CompUnit cu : code._compunits.values() ) + if( cu._start!=null && !cu._start.isDead() ) releaseStart(cu._start); code._stop.walk(n -> { if( n instanceof CallEndNode cend ) @@ -148,6 +153,13 @@ abstract class Unlink { }); } + private static void releaseStart(StartCUNode start) { + if( start.iskeep() ) start.unkeep(); + // An unused unit can lose its outer Stop edge during optimization. + // Detach its empty wrapper from the scheduling root as well. + if( start.in(1) instanceof StopCUNode stop && stop.nIns()==0 ) start.setDef(0,null); + } + private static void restoreRPC(FunNode fun) { if( fun.rpc()!=null ) return; // A single-call target can have a folded RPC even when a multi-target diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index c6a6ff3b..538b1a18 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.XInt; import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; @@ -202,6 +203,13 @@ public class BulkMemPhiNode extends PhiNode { // duplicate for the same Region/alias pair. Node mem = precisePhi(alias); assert ((TypeMem)mem._type)._alias==alias; + // A parallel Phi may still be waiting for its inputs' type changes. + // Do not replace this memory with slices carrying weaker escape facts. + if( !readySlice(mem) ) return null; + for( int old = _aliases.nextSetBit(0); old>=0; old = _aliases.nextSetBit(old+1) ) { + Node prior = precisePhi(old); + if( !readySlice(prior) ) return null; + } BitSet aliases = ((BitSet)_aliases.clone()); aliases.set(alias); @@ -222,6 +230,16 @@ public class BulkMemPhiNode extends PhiNode { return aggregate(bulk,alias,mem); } + private boolean readySlice(Node precise) { + TypeMem mem = (TypeMem)_type; + TypeMem part = (TypeMem)precise._type; + if( !XInt.bit(mem._escAs,part._alias) || mem.meet(part).isa(mem) ) return true; + precise.setType(precise.compute()); + if( mem.meet(precise._type).isa(mem) ) return true; + addDep(precise); + return false; + } + // Build aggregate memory over a bulk Phi, preserving every precise slice // which the bulk has already excluded. The named alias is newly supplied // (or replaces its old slice). diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 4f225fbe..7740df79 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -288,6 +288,7 @@ public abstract class CFGNode extends Node { // Do not walk from a Call to linked Fun's. return usecfg instanceof XCtrlNode || (this instanceof CallNode && usecfg instanceof FunNode) || + (this instanceof CProjNode proj && proj._idx==3 && proj.in(0) instanceof CLInitNode && usecfg instanceof FunNode) || (this instanceof ReturnNode && usecfg instanceof CallEndNode); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java index d33670d1..f7b48fbe 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.codegen.Iter; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.BAOS; import java.util.*; @@ -16,7 +17,7 @@ public class CLInitNode extends CFGNode implements MultiNode { public Parser.Lexer _loc; // For error reporting // Inputs: control, whole memory, class pointer, loaded $init flag - // Results: control, whole memory, known-true flag alias memory. + // Results: control, whole memory, known-true flag alias memory, call control. // For field references, the ptr might be the dst clz ptr or not. public CLInitNode(Parser.Lexer loc, Node ctrl, Node mem, Node ptr, Node ready) { super(ctrl,mem,ptr,ready); @@ -75,19 +76,21 @@ public class CLInitNode extends CFGNode implements MultiNode { @Override public Type compute() { if( in(0)._type.isHigh() || ptr()._type.isHigh() ) - return TypeTuple.make(Type.XCONTROL,TypeMem.TOP,TypeMem.TOP); + return TypeTuple.make(Type.XCONTROL,TypeMem.TOP,TypeMem.TOP,Type.XCONTROL); if( instance() ) - return TypeTuple.make(in(0)._type,mem()._type,mem()._type); + return TypeTuple.make(in(0)._type,mem()._type,mem()._type,Type.XCONTROL); Field flag = flag(); Type slice = flag==null ? TypeMem.BOT : TypeMem.make(flag._alias,TypeInteger.TRUE); // The initializer may write arbitrary public memory. Only its flag // has a guaranteed value on the normal continuation. Type bulk = ready()._type.isHigh() ? TypeMem.TOP : ready()._type==TypeInteger.TRUE ? mem()._type : TypeMem.BOT; - return TypeTuple.make(in(0)._type,bulk,slice); + Type call = ready()._type.isHigh() || ready()._type==TypeInteger.TRUE ? Type.XCONTROL : in(0)._type; + return TypeTuple.make(in(0)._type,bulk,slice,call); } @Override public Node pcopy(int idx, Node dep) { + if( idx==3 ) return null; // Analysis call edge, removed before scheduling. dep.addDep(ptr()); dep.addDep(ready()); if( instance() ) return idx==0 ? in(0) : mem(); @@ -100,12 +103,60 @@ public class CLInitNode extends CFGNode implements MultiNode { } @Override public Node idealize() { + if( CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Opto.ordinal() ) return null; + if( CodeGen.CODE._phase.ordinal()<CodeGen.Phase.Lower.ordinal() ) return link() ? this : null; if( CodeGen.CODE._phase!=CodeGen.Phase.Lower || bypass() || in(0)._type.isHigh() ) return null; if( CodeGen.CODE._midAssert ) return this; // Until entry arguments become arrays, ordinary initializers receive zero. return expand(CodeGen.CODE.con(TypeInteger.ZERO)); } + // Before lowering, expose the conditional call to interprocedural analysis. + // No Return edge is needed: CLInit already conservatively models its effects. + public boolean link() { + if( in(0)._type.isHigh() || ptr()._type.isHigh() || ready()._type.isHigh() || bypass() ) return false; + FunNode target = CodeGen.CODE.link(cu()); + if( target==null ) return false; // Forward class reference during parsing. + assert !target.isDead() : "dead initializer "+target._name; + CProjNode call = cproj(3); + if( call!=null && target._inputs.find(call)!=-1 ) return false; + if( CodeGen.CODE._midAssert ) return true; + if( call==null ) call = CodeGen.CODE.add(new CProjNode(this,3,"InitCall").init()); + CodeGen.CODE.keepInCompUnit(target); + CodeGen.CODE.add(target).addDef(call); + for( Node use : target._outputs ) + if( use instanceof ParmNode parm ) { + Node arg = switch( parm._idx ) { + case 0 -> CodeGen.CODE.con(TypeRPC.BOT); + case 1 -> mem(); + case 2 -> ptr(); + case 3 -> CodeGen.CODE.con(TypeInteger.ZERO); + default -> throw new IllegalStateException("initializer parameter"); + }; + CodeGen.CODE.add(parm).addDef(arg); + } + if( CodeGen.CODE._phase.ordinal()>CodeGen.Phase.Opto.ordinal() ) { + boolean repair = !target.compute().isa(target._type); + for( Node use : target._outputs ) + if( use instanceof ParmNode && !use.compute().isa(use._type) ) repair = true; + if( repair ) Iter.repair(CodeGen.CODE); + } + return true; + } + + public void unlink() { + CProjNode call = cproj(3); + if( call==null ) return; + keep(); + for( Node use : call._outputs.asAry() ) + if( use instanceof FunNode target ) { + CodeGen.CODE.add(target); + target.removeDeadPath(target._inputs.find(call)); + } + call.isKill(); + unkeep(); + } + // Called only after cycle/type checking. The initialized arm skips the // call; both arms rejoin with whole memory and a known-true flag slice. private Node expand(Node arg) { @@ -123,9 +174,11 @@ public class CLInitNode extends CFGNode implements MultiNode { Node fptr = new FunPtrNode(target.sig(),CodeGen.CODE._start,target.ret()).peephole(); CallNode call = CodeGen.CODE.add(new CallNode(_loc,cold,memory,ptr(),arg,fptr).init()); CallEndNode end = new CallEndNode(call,TypeRPC.constant(CodeGen.CODE.rpc(_loc._cu._cname))); - // This is a lowered call, after interprocedural analysis. Do not add - // new parameter flows to a body already optimized by SCCP. CodeGen.CODE.add(end.init()); + // Replace the analysis edge with the ordinary call. Its arguments + // are the same ones already analyzed before lowering. + call.link(target); + unlink(); Node called = CodeGen.CODE.add(new CProjNode(end,0,ScopeNode.CTRL).init()); Node after = CodeGen.CODE.add(new ProjNode(end,1,ScopeNode.MEM0).init()); RegionNode region = CodeGen.CODE.add(new RegionNode(_loc,null,done,called).init()); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 73f67479..b7b26265 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -75,83 +75,51 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public Type compute() { + // Something is dead or busted, early exit with high/dead result if( !(in(0) instanceof CallNode call) || call._type != Type.CONTROL ) return TypeTuple.STATE.dual(); - // Grab the TFP and use the functions declared return type. - // If the call.fptr() is a FRef, return will be BOTTOM. + // The function pointer carries a result type even without a body. Type ftype = addDep(call.fptr())._type; + // Something is dead or busted, early exit with high/dead result if( !(ftype instanceof TypeFunPtr tfp) ) return ftype.isHigh() ? TypeTuple.STATE.dual() : TypeTuple.STATE; - // Mid-fold, just take the one single callers' return type - if( _folding ) { - TypeTuple tt = (TypeTuple)in(1)._type; - return tt.makeFrom(2,tt.ret()); - } + // Mid-fold, just take the inlined callee's return. + if( _folding ) return in(1)._type; - // Here, if I can figure out I've linked *all* callers, then I can meet - // across the linked returns and join with the function return type. + // Unknown targets can change any memory and return the declared type. + if( XInt.isHigh(tfp.fidxs()) ) + return TypeTuple.make(Type.CONTROL,TypeMem.BOT,tfp.ret()); - // External functions have an exact FIDX but deliberately no local - // FunNode/Return edge. They conservatively crush public memory and - // produce their declared return type. A missing non-external target - // is still an unresolved/error call. + // Check for making a "C" call int externs = 0; - // The signature bounds widening (e.g. an i32 result stays i32). - // Use the callee signature, not FunPtrNode's live recursive range. - Type bound = tfp.ret(); - if( !XInt.isHigh(tfp.fidxs()) ) { - bound = Type.TOP; - for( int fidx = XInt.next(tfp.fidxs(),0); fidx >= 0; fidx = XInt.next(tfp.fidxs(),fidx) ) { - if( CodeGen.CODE.externFunc(fidx)!=null ) - externs++; - FunNode fun = CodeGen.CODE._link(fidx); - bound = bound.meet(fun==null ? tfp.ret() : addDep(fun).sig().ret()); - } - } - boolean hasExtern = externs != 0; - - // If we have an error-call, e.g. wrong args, then we never link. - // Pre-Opto this looks like a missing target fcn, and we assume it will - // appear later - meanwhile, we use a conservative approx of memory - // effects. - if( (nIns()-1)+externs < tfp.nfcns() ) { - // If during Opto, assume call won't be called and thus won't return anything. - // Lowered calls deliberately have no links into optimized bodies. - boolean opto = CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() && - CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Lower.ordinal(); - Type tmem = opto ? TypeMem.TOP : TypeMem.BOT; - Type ret = opto ? Type.TOP : tfp.ret(); - // Use the same widening before and after linking a callee. - return TypeTuple.make(Type.CONTROL,tmem,widenResult(ret,bound)); + for( int fidx = XInt.next(tfp.fidxs(),0); fidx >= 0; fidx = XInt.next(tfp.fidxs(),fidx) ) + if( CodeGen.CODE.externFunc(fidx)!=null ) externs++; + if( externs!=0 ) { + // C calls have no Return edges. Simple calls have an extra self + // argument, so the two cannot be targets of the same valid call. + assert externs==tfp.nfcns(); + return TypeTuple.make(Type.CONTROL,call.exposed(this),tfp.ret()); } - // A linked function for every concrete function - TypeTuple state = hasExtern - ? TypeTuple.make(Type.CONTROL,call.exposed(this),tfp.ret()) - : TypeTuple.STATE.dual(); + // An unlinked target may have effects, so early conservative return. + // This also covers invalid calls (e.g. wrong arity), which never link. + // SCCP links valid finite targets as soon as they become known, before + // computing their CallEnd, so this check does not trigger during SCCP. + if( nIns()-1 < tfp.nfcns() ) + return TypeTuple.make(Type.CONTROL,TypeMem.BOT,tfp.ret()); + + // Start at a high tuple (matching Returns' tuple) + TypeTuple state = TypeTuple.STATE.dual(); + // Meet over all Returns for( int i=1; i<nIns(); i++ ) state = (TypeTuple)state.meet(in(i)._type); - // A reachable call whose presently linked exits are all unreachable - // keeps a conservative continuation. In particular, do not let a - // transient no-return result tear down the caller before/during SCCP. - // If the call remains out-of-line, its continuation can conservatively - // contribute class-init dependencies even though it never executes. + // Keep a live continuation even before any callee exit is reachable. + // Otherwise a transient no-return result can tear down the caller + // and lose class-init dependencies before SCCP finds those exits. if( state.ctl()==Type.XCONTROL ) return TypeTuple.make(Type.CONTROL,TypeMem.TOP,Type.TOP); - // Join before widening: FunPtrNode follows the live Return type, so - // joining it afterward would undo the widening. - return state.makeFrom(2,widenResult(state.ret().join(tfp.ret()),bound)); - } - - private static Type widenResult(Type ret, Type bound) { - // Recursion is a loop in disguise. For f(x-1)+1, the result - // flows Return -> CallEnd -> Add -> Phi -> Return, without - // crossing ParmNode.compute's widening point. Widen here too, - // using the loop rule in PhiNode.compute. Keep constants and - // above-center ranges narrow. - if( ret instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() ) - ret = ti.same_but_slightly_wider_than().join(bound); - return ret; + // Final JOIN over the signature guarentee and meet-over-returns + return state.makeFrom(2,state.ret().join(tfp.ret())); } @Override diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java index bcb756fa..12c7f1e3 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Iter; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeMem; @@ -75,6 +76,22 @@ 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) { @@ -169,6 +186,17 @@ public class CallNode extends CFGNode { } // Call end points to function return CodeGen.CODE.add(cend()).addDef(fun.ret()); + // Loading/inlining can reveal a target after SCCP. Its new caller + // may bring escapes absent from the cached formal parameter types. + // Repair affected bounds before the next type-lifting peephole. + CodeGen code = CodeGen.CODE; + if( code._phase.ordinal()>CodeGen.Phase.Opto.ordinal() && + code._phase.ordinal()<CodeGen.Phase.Lower.ordinal() ) { + boolean repair = !fun.compute().isa(fun._type) || !cend().compute().isa(cend()._type); + for( Node use : fun._outputs ) + if( use instanceof ParmNode && !use.compute().isa(use._type) ) repair = true; + if( repair ) Iter.repair(code); + } return this; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java index fe3c3162..6a8d5d50 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -100,6 +100,8 @@ public class FunNode extends RegionNode { assert sig.isa(_sig) || resolvesForwardSelf(sig,_sig); if( _sig != sig ) { CODE.add(this); + // Return uses the signature to bound recursive-result widening. + CODE.add(_ret); // Changing the signature can allow more inlining if( _ret != null ) for( Node use : ret().outs() ) @@ -178,8 +180,7 @@ public class FunNode extends RegionNode { // 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 - // Opaque CLInit obligations need their bodies even without Call edges. - if( !isClz() && in(1) instanceof StartCUNode start ) { + 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 ) { @@ -219,6 +220,12 @@ public class FunNode extends RegionNode { // Always in-progress until we run out of unknown callers public boolean unknownCallers() { return nIns()>=2 && in(1) instanceof StartNode; } + // The starting initializer and public source classes are external entry + // points. Privacy stops at the first private class in the name's path. + public boolean isRoot() { + return isClz() && (CODE.entryClinitName().equals(_name) || (isFromSource() && isPublic())); + } + public boolean isModInit( ) { // The one top-level <clinit> with no internal dots: // "sys.<clinit>" is a module, but "sys.io.<clinit>" is not. diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 0431f7d5..311a7ea4 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -49,7 +49,13 @@ public class ReturnNode extends CFGNode { @Override public Type compute() { - return TypeTuple.make(ctrl()._type,mem()._type,expr()._type); + Type ret = expr()._type; + // Recursive results can grow around Return -> CallEnd -> Add -> Phi + // without crossing Parm's widening point. Widen here, so FunPtr and + // CallEnd agree on the result, bounded by the declared signature. + if( ret instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() ) + ret = ti.same_but_slightly_wider_than(); + return TypeTuple.make(ctrl()._type,mem()._type,ret.join(addDep(_fun).sig().ret())); } @Override public Node idealize() { diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 495be0a2..a7ea4ac1 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -55,16 +55,10 @@ public class StartNode extends LoopNode implements MultiNode { } boolean escapedFIDX(int fidx) { - // Public class fields are callable by the unknown external world - // regardless of the current SCCP approximation of Start memory. - if( CodeGen.CODE.publicFIDX(fidx) ) return true; if( !(_type instanceof TypeTuple tt) ) return !_type.isHigh(); // TOP never escapes, BOTTOM always escapes TypeMem tmem = (TypeMem)tt._types[1]; - if( tmem == TypeMem.BOT ) return false; if( tmem == TypeMem.TOP ) return false; - if( XInt.isHigh(tmem._escFs) ) - return false; return XInt.bit(tmem._escFs,fidx); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index a88adee2..61970aa0 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -55,10 +55,9 @@ public class StopCUNode extends StopNode { FunNode fun = ret.fun(); boolean noUserCtor = fun.isInstance() && !CodeGen.hasUserConstructor(((TypeMemPtr)fun.sig().arg(0))._obj); - // Instance <init> is an allocation helper, never an externally - // callable constructor when a user constructor exists. Otherwise - // the same no-arg <init> is the public constructor. - boolean pub = fun.isPublic() && (fun.isClz() || noUserCtor); + // Only entry initializers seed escape discovery. Constructors + // and methods are discovered through escaping class/instance fields. + boolean pub = fun.isRoot(); TypeFunPtr sig = fun.sig(); // If public init, the function escapes and the related class escapes if( pub ) { @@ -83,23 +82,36 @@ public class StopCUNode extends StopNode { // 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 = 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 = xmem.escapes(tret.ret()); - xmem = publicBottom(xmem); + xmem = publicBottom(xmem.escapes(tret.ret()),xmem); xmem = (TypeMem)xmem.meet(publicBottom(tret.mem(),xmem)); } } - // Native retention is shared by the whole program, including calls - // on paths with no Return. A class boundary must not hide it. + // Native and unknown-caller retention includes calls on paths with + // no Return. A class boundary must not hide it. for( CallNode call : CodeGen.CODE._calls ) - if( !call.isDead() ) xmem=publicBottom(xmem.escapes(call.exposed(this))); + if( !call.isDead() ) { + xmem = 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 = publicBottom(xmem.escapes(addDepForwards(call.arg(i+2))._type),xmem); + } for( FunNode fun : CodeGen.CODE._linker ) - if( fun!=null && fun.summary()!=null && !fun.summary().isDead() ) - xmem=publicBottom(xmem.escapes(fun.summary().exposed(this))); + if( fun!=null && fun.summary()!=null && !fun.summary().isDead() ) { + xmem = publicBottom(xmem.escapes(fun.summary().exposed(this)),xmem); + // A reachable unloaded body can call these targets, including + // private initializers. Its arguments are unavailable here. + // Preserve these precise dependencies after normalizing FULL. + if( fun._type==Type.CONTROL ) + for( int fidx : fun.summary()._classDependencyFIDXs ) + if( fidx!=0 ) xmem = xmem.makeFrom(XInt.meet(xmem._escFs,XInt.make(fidx)),xmem._escAs); + } assert xmem._alias==1 && !xmem._one; return TypeTuple.make(Type.CONTROL,xmem,Type.BOTTOM); } @@ -107,7 +119,6 @@ public class StopCUNode extends StopNode { // FULL escape sets arise from global BOTTOM. Across a compilation-unit // boundary global BOTTOM exposes every public field, while retaining any // private escapes already discovered precisely. - private TypeMem publicBottom(TypeMem mem) { return publicBottom(mem,mem); } private TypeMem publicBottom(TypeMem mem, TypeMem prior) { // The pessimistic Iter pass naturally lifts transient FULL inputs to // precise finite sets. Replacing FULL early there would let a later diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java index 1949ae46..96a64cd0 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java @@ -3,14 +3,17 @@ package com.seaofnodes.simple.node.cpus.arm; import com.seaofnodes.isa.Arm64; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.util.SB; public class CallRRARM extends CallNode implements MachNode { - CallRRARM(CallNode call) { super(call); } + final TypeFunPtr _tfp; + CallRRARM(CallNode call) { super(call); _tfp = call.tfp(); } + @Override public TypeFunPtr tfp() { return _tfp; } @Override public String op() { return "callr"; } @Override public String label() { return op(); } @Override public RegMask regmap(int i) { - return i==_inputs._len + return i==_inputs._len-1 ? arm.RMASK // Function call target : arm.callInMask(tfp(),i,fun()._maxArgSlot); // Normal argument } @@ -19,7 +22,7 @@ public class CallRRARM extends CallNode implements MachNode { @Override public void encoding( Encoding enc ) { // Needs a register, typically a jump-and-link-register opcode // blr - short self = enc.reg(this); + short self = enc.reg(fptr()); enc.add4(Arm64.blr(Arm64.OP_CALLRARM, self)); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java index cda4bc79..68f1016a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java @@ -3,10 +3,13 @@ package com.seaofnodes.simple.node.cpus.riscv; import com.seaofnodes.isa.RiscV; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.util.SB; public class CallRRISC extends CallNode implements MachNode { - CallRRISC( CallNode call ) { super(call); } + final TypeFunPtr _tfp; + CallRRISC( CallNode call ) { super(call); _tfp = call.tfp(); } + @Override public TypeFunPtr tfp() { return _tfp; } @Override public String op() { return "callr"; } @Override public String label() { return op(); } @Override public RegMask regmap(int i) { diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java index f97163eb..3109df63 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java @@ -4,14 +4,17 @@ import com.seaofnodes.isa.X86; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.CallNode; import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.util.SB; public class CallRX86 extends CallNode implements MachNode { - CallRX86( CallNode call ) { super(call); } + final TypeFunPtr _tfp; + CallRX86( CallNode call ) { super(call); _tfp = call.tfp(); } + @Override public TypeFunPtr tfp() { return _tfp; } @Override public String op() { return "callr"; } @Override public String label() { return op(); } @Override public RegMask regmap(int i) { - return i==_inputs._len + return i==_inputs._len-1 ? x86_64_v2.WMASK // Function call target : x86_64_v2.callInMask(tfp(),i,fun()._maxArgSlot); // Normal argument } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/type/XInt.java b/chapter28b/src/main/java/com/seaofnodes/simple/type/XInt.java index 752c1419..3e74df84 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/type/XInt.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -213,11 +213,17 @@ public abstract class XInt { // for( int bit = XInt.next(bits,0); bit >=0; bit = XInt.next(bits,bit) ) {...bit...} public static int next(int[] xs, int x) { assert !isHigh(xs); // No iterating infinite bitsets - x++; // Skip current - for( ; !bit(xs,x); x++ ) + return next(xs,x,Integer.MAX_VALUE); + } + + // Next set bit below limit, or -1. Allows bounded walks of infinite sets. + public static int next(int[] xs, int x, int limit) { + while( ++x < limit ) { + if( bit(xs,x) ) return x; if( idx(x)>=xs.length ) return -1; - return x; + } + return -1; } // Remap all bits |