From 01f87c30c97c12237cc7b63d620e204a5fc79d41 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 27 Oct 2026 14:50:02 -0700 Subject: Remove several instances of extra whole-graph walks --- .../simple/codegen/ClassInitDependencies.java | 41 +++++++--- .../com/seaofnodes/simple/codegen/CodeGen.java | 32 +------- .../com/seaofnodes/simple/codegen/FinalizeIR.java | 5 +- .../java/com/seaofnodes/simple/codegen/Iter.java | 39 ++++++++- .../java/com/seaofnodes/simple/codegen/Opto.java | 17 ++-- .../com/seaofnodes/simple/codegen/ParseAll.java | 12 ++- .../java/com/seaofnodes/simple/codegen/Unlink.java | 14 +++- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 18 +++++ .../java/com/seaofnodes/simple/node/CFGNode.java | 1 + .../com/seaofnodes/simple/node/CLInitNode.java | 65 +++++++++++++-- .../com/seaofnodes/simple/node/CallEndNode.java | 94 +++++++--------------- .../java/com/seaofnodes/simple/node/CallNode.java | 28 +++++++ .../java/com/seaofnodes/simple/node/FunNode.java | 11 ++- .../com/seaofnodes/simple/node/ReturnNode.java | 8 +- .../java/com/seaofnodes/simple/node/StartNode.java | 6 -- .../com/seaofnodes/simple/node/StopCUNode.java | 37 ++++++--- .../seaofnodes/simple/node/cpus/arm/CallRRARM.java | 9 ++- .../simple/node/cpus/riscv/CallRRISC.java | 5 +- .../simple/node/cpus/x86_64_v2/CallRX86.java | 7 +- .../main/java/com/seaofnodes/simple/type/XInt.java | 12 ++- 20 files changed, 308 insertions(+), 153 deletions(-) (limited to 'chapter28b/src/main/java/com/seaofnodes') 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() 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 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 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 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 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()=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 with no internal dots: // "sys." is a module, but "sys.io." 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 is an allocation helper, never an externally - // callable constructor when a user constructor exists. Otherwise - // the same no-arg 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=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 -- cgit v1.2.3