diff options
Diffstat (limited to 'chapter28b/src/main/java')
22 files changed, 600 insertions, 179 deletions
diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java index e65ef6d9..42e6695e 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -78,6 +78,7 @@ public class IterPeeps { CallEndNode cend; while( (cend=_workInline.pop()) != null) { if( cend.isDead() ) continue; + if( cend.loadForInline() ) { inlined=true; break; } byte inline = cend.maybeInline(); if( inline == -1 ) defer.add(cend); if( inline > 0 ) { 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 6c70b71d..45d65514 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -12,14 +12,14 @@ import java.util.*; // Build the inits-graph, a call-graph plus CLInits plus class parents. -// (1) Scan all functions f, building _edges[f][]: the set of <cinit> fcns from -// CompUnits from CLInitNodes, and the set of fcn call targets in f and the -// class parent. These are all reported as fidxs (ints). +// (1) Scan all functions f, building _edges[f][]: the set of <clinit> fcns +// from CompUnits from CLInitNodes, and the set of fcn call targets in f and +// the class parent. These are all reported as fidxs (ints). // -// (2) Walk the _edges graph using Tarjans SCC. Reject cycles containing more +// (2) Walk the _edges graph using Tarjans SCC. Reject cycles containing more // than one <clinit>. // -// (3) Report on <clinit> cycles +// (3) Report on <clinit> cycles, if any // public class ClassInitDependencies { private final CodeGen _code; @@ -56,12 +56,14 @@ public class ClassInitDependencies { // Return the outgoing init edge set for this function private static int[] walk( CodeGen code, FunNode fun, Ary<CFGNode> work, IntHashMap iset, BitSet visit, Ary<Parser.Lexer> sites) { + if( fun.summary()!=null ) return fun.summary()._classDependencyFIDXs; // Walk function body, looking for outgoing init edges assert iset .isEmpty(); // int hash set for de-dup assert visit.isEmpty(); // needs a visit set, because loops assert work .isEmpty(); // needs a worklist, because DAG, parallel explore paths - // Children classes always dependent on parents + // Keep the structural parent prerequisite even if a known-true flag + // folds the check in the child's body. Cycles still require diagnosis. if( fun.isClz() && fun._compunit._par != null ) iset.put(code.link(fun._compunit._par).sig().fidx(),1); @@ -123,6 +125,16 @@ public class ClassInitDependencies { return null; } + // A condition-producing helper outside the SCC can eliminate a cycle. + // Before reporting one, restore the full-IR precision of the original check. + Ary<CompUnit> cycleImports() { + Ary<CompUnit> units = new Ary<>(CompUnit.class); + if( check()==null ) return units; + for( FunNode fun : _code._linker ) + if( fun!=null && fun.summary()!=null && units.find(fun._compunit)==-1 ) units.add(fun._compunit); + return units; + } + // Every internal edge of an SCC belongs to a cycle. Print all of them: // stack order is not a path, and enumerating all cycle paths can explode. // This bookkeeping and formatting are only needed on an error. 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 8302ede6..07ca7e2b 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -259,6 +259,7 @@ public class CodeGen { // The Generic driver public CodeGen driver( Phase target, String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol, int dump ) { + _splitObjects = target.ordinal()>=Phase.Export.ordinal() && !inMemory; // Parse a Simple file, and for mentioned external symbols either load // from .o or recursively parse step(target, Phase.Parse, this::parse, dump); @@ -272,6 +273,8 @@ public class CodeGen { step(target, Phase.FinalizeIR, this::finalizeIR, dump); // Final error check - bad programs fail here step(target, Phase.TypeCheck, this::typeCheck, dump); + if( cpu==null && target.ordinal()>=Phase.Lower.ordinal() && _phase.ordinal()<Phase.Lower.ordinal() ) + loadAllIR(); // Ideal evaluation needs code for calls left out of line. // Save reloadable ideal IR for a later seperate compilation step(target, Phase.Serialize, () -> Serialize.forTarget(this,target,inMemory), dump); // Replace "fat" nodes with their exploded explicit IR; this can @@ -456,9 +459,12 @@ public class CodeGen { return externFunc(fidx); } - public boolean owns(FunNode fun) { - return fun._compunit != null && fun._compunit._src != null; - } + // Select which source CompUnit's object this encoding pass emits. + CompUnit _emitUnit; + boolean emits(CompUnit cu) { return cu!=null && cu._src!=null && (_emitUnit==null || _emitUnit==cu); } + boolean emits(FunNode fun) { return emits(fun._compunit); } + private boolean _splitObjects; + final LinkedHashMap<CompUnit,Encoding> _encodings = new LinkedHashMap<>(); // --------------------------- @@ -491,6 +497,82 @@ 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. + 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., + // this code is being run by the evaluator, and so doesn't get a link step. + // If, instead, the code was going to run natively, it would first go + // through a link step which would resolve all these call sites to code + // generated in other object files. Since no link step, we need acess to + // that other code right now. + public void loadAllIR() { + boolean loaded = false; + for( CompUnit cu : _compunits.values() ) { + if( cu._src!=null || cu._obj==null ) continue; + ElfReader elf = getElf(cu._obj); + if( elf._nodes!=null ) continue; + ParseAll.loadCompUnit(this,cu); + loaded=true; + } + if( !loaded ) return; + analyzeImports(); + if( _phase.ordinal()<Phase.FinalizeIR.ordinal() ) return; + Phase prior = _phase; + try { + _phase=Phase.IterPostOpto; + _iter.iterate(this); + _phase=Phase.FinalizeIR; + FinalizeIR.run(this); + _phase=Phase.TypeCheck; + TypeCheck.run(this); + } finally { _phase=prior; } + } + + void resolveInitCycles() { + while( true ) { + 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; + _iter.iterate(this); + _phase=Phase.FinalizeIR; + FinalizeIR.run(this); + } finally { _phase=prior; } + } + } + public CodeGen finalizeIR() { return phase(Phase.FinalizeIR, _phase==Phase.IterPostOpto, () -> FinalizeIR.run(this)); } // Root a surviving function without claiming that it has unknown callers. @@ -529,6 +611,7 @@ public class CodeGen { // --------------------------- public BAOS _serial; + final LinkedHashMap<CompUnit,BAOS> _serials = new LinkedHashMap<>(); public void serialize() { phase(Phase.Serialize, _phase==Phase.TypeCheck, () -> Serialize.serialize(this)); } @@ -576,6 +659,13 @@ public class CodeGen { return phase(Phase.Schedule, (_phase==Phase.Unlink || _phase==Phase.Select), () -> GlobalCodeMotion.buildCFG(this)); } + // Evaluation branches from checked ideal IR directly to scheduling. + // CLInit remains an executable ideal operation; no Lower or Select pass. + public CodeGen scheduleForEval() { + return phase(Phase.Schedule, (_phase==Phase.TypeCheck || _phase==Phase.Serialize), + () -> _cfg=GlobalCodeMotion.forEval(this,_start,_stop)); + } + // --------------------------- // Local (basic block) scheduler phase, a classic list scheduler public CodeGen localSched() { return phase(Phase.LocalSched, _phase==Phase.Schedule, () -> ListScheduler.sched(this)); } @@ -604,7 +694,17 @@ public class CodeGen { // --------------------------- // Encoding public Encoding _encoding; - public CodeGen encode() { return phase(Phase.Encoding, _phase==Phase.RegAlloc, () -> _encoding = new Encoding(this).encode()); } + public CodeGen encode() { return phase(Phase.Encoding, _phase==Phase.RegAlloc, () -> { + if( !_splitObjects ) { _encoding = new Encoding(this).encode(); return; } + try { + for( CompUnit cu : _serials.keySet() ) { + _emitUnit = cu; + Encoding enc = new Encoding(this).encode(); + _encodings.put(cu,enc); + if( cu._fname.equals(_srcName) ) _encoding = enc; + } + } finally { _emitUnit = null; } + }); } // --------------------------- // Exporting to external formats @@ -612,7 +712,31 @@ public class CodeGen { public CodeGen exportELF( boolean inMemory, boolean emitEntrySymbol ) { return phase(Phase.Export, _phase==Phase.Encoding, () -> { if( inMemory ) new LinkMem(this).link(_encoding); - else _elf = new ElfWriter(this).export(emitEntrySymbol); + else { + if( _serials.isEmpty() ) + throw new IllegalStateException("ELF export needs ideal IR: request Export from the driver, or Serialize before Lower"); + Encoding entry = _encoding; + BAOS serial = _serial; + try { + if( _encodings.isEmpty() ) for( CompUnit cu : _serials.keySet() ) { + _emitUnit=cu; + _encodings.put(cu,new Encoding(this).encode()); + } + for( var e : _encodings.entrySet() ) { + _emitUnit = e.getKey(); + _encoding = e.getValue(); + _serial = _serials.get(_emitUnit); + _elf = new ElfWriter(this).export(emitEntrySymbol && _emitUnit._fname.equals(_srcName)); + } + // Mutually dependent units built together must not become + // stale merely because their files were written in sequence. + long time = System.currentTimeMillis(); + for( CompUnit cu : _encodings.keySet() ) { + File obj = new File(_buildDir+"/"+cu._fname+".o"); + if( !obj.setLastModified(time) ) throw new IllegalStateException("Cannot timestamp "+obj); + } + } finally { _emitUnit=null; _encoding=entry; _serial=serial; } + } }); } @@ -631,6 +755,7 @@ public class CodeGen { // State machine elements; the outermost element is _externPaths private int _extPathIdx; // Search index into the extern path list private final Ary<File> _files = new Ary<>(File.class); // Files in the current extern path being searched + private final HashSet<File> _seenFiles = new HashSet<>(); private int _extFileIdx; // Index into _files public ElfReader findExternalSimple( String name ) { @@ -685,6 +810,12 @@ public class CodeGen { // Publish definitions only; referenced classes belong to other objects. for( String fname : elf._units ) _externSymbols.putIfAbsent(Parser.addClzPrefix(fname.replace('/','.')),elf); + // A -L object can name dependencies alongside itself. They + // need metadata discovery even when no directory was supplied. + for( String dep : elf._deps ) { + File file = elf.dependencyFile(dep); + if( file.isFile() ) addExtFile(file); + } break; default: throw Utils.TODO("should not reach here"); @@ -709,12 +840,17 @@ public class CodeGen { for( File f : dir.listFiles() ) fillExtFiles(f); else if( dir.getName().endsWith(".o") ) - _files.add(dir); + addExtFile(dir); + } + + private void addExtFile(File file) { + file=file.toPath().toAbsolutePath().normalize().toFile(); + if( _seenFiles.add(file) ) _files.add(file); } // Map from object file names to ElfReaders public final HashMap<String,ElfReader> _elfs = new HashMap<>(); - ElfReader getElf(File f) { + public ElfReader getElf(File f) { ElfReader elf = _elfs.get(f.getPath()); if( elf != null ) return elf; diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java index 10720300..1f0e803d 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java @@ -38,6 +38,8 @@ public class ElfReader { public TypeStruct[] _pubTypes; // Nodes read in this Elf public Ary<Node> _nodes; + Serialize.TypeRead _types; + FunctionSummary[] _functions; // Load an Elf file (mostly lazily) public static ElfReader load( File f, CompUnit cu ) { @@ -67,7 +69,7 @@ public class ElfReader { if( ".simple".equals(sec._name) ) simple = sec; _simple = simple; - _bais = new BAOS(_buf, (int)_simple._offset); + _bais = _simple==null ? null : new BAOS(_buf, (int)_simple._offset); } // For Serialize self-test @@ -92,6 +94,12 @@ public class ElfReader { Serialize.read_public_strs(this); } + File dependencyFile(String unit) { + File root = _file; + for( String part : _units[0].split("/") ) root=root.getParentFile(); + return new File(root,unit+".o"); + } + // Loads the entire IR public TypeStruct loadSimple(CodeGen code) { Serialize.readAll(code, this, code._aliases, code._fidxs, code._rpcs); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java index 5a280723..fcf5c287 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -193,12 +193,13 @@ public class ElfWriter { for( Node stopcu : stop._inputs ) { for( Node ret : stopcu._inputs ) { FunNode fun = ((ReturnNode)ret).fun(); - if( !_code.owns(fun) ) + if( !_code.emits(fun) ) continue; int end = enc.opStart(fun.ret()) + enc.opLen(fun.ret()); long value = enc.opStart(fun); long size = end - value; - if( fun._name != null ) { // Anonymous functions have no name + // Stable FIDX names are exported separately below. + if( fun._name != null && !fun._name.equals(_code._fidxs.symbol(fun.sig().fidx())) ) { // The C runtime owns `main` and adapts argc/argv into // a normal Simple array. Keep the Simple function on // its native ABI under a private entry symbol. @@ -217,7 +218,7 @@ public class ElfWriter { FunNode clinit = null; String entryName = _code.entryClinitName(); for( FunNode fun : _code._linker ) - if( fun != null && _code.owns(fun) ) { + if( fun != null && _code.emits(fun) ) { if( "main".equals(fun._name) ) return; // encodeFunctions exported this as simple_main if( entryName.equals(fun._name) ) @@ -368,7 +369,7 @@ public class ElfWriter { // anonymous functions which have no source-level exported name. HashMap<String,Integer> dataSymbols=new HashMap<>(); for( FunNode fun : _code._linker ) - if( fun!=null && !fun.isDead() && _code.owns(fun) && enc.opStart(fun)>=0 ) { + if( fun!=null && !fun.isDead() && _code.emits(fun) && enc.opStart(fun)>=0 ) { String name=_code._fidxs.symbol(fun.sig().fidx()); dataSymbols.put(name,symbols.symbol(name,text._index,SYM_BIND_GLOBAL,SYM_TYPE_FUNC,enc.opStart(fun),0)); } @@ -446,7 +447,7 @@ public class ElfWriter { assert out.position() == size; - String objName = _code._buildDir + "/" + _code._srcName + ".o"; + String objName = _code._buildDir + "/" + (_code._emitUnit==null ? _code._srcName : _code._emitUnit._fname) + ".o"; File file = new File(objName); if( file.getParentFile()!=null ) file.getParentFile().mkdirs(); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 06bf14f5..067f431a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -162,7 +162,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // Source is a Call, destination in the Fun. public Encoding relo( CallNode call ) { FunNode fun = _code.link(call.tfp()); - if( fun != null && !_code.owns(fun) ) + if( fun != null && !_code.emits(fun) ) _externals.put(call,fun._name); else _internals.put(call,fun); @@ -176,7 +176,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { String nativeName = _code.externFunc(tfp.fidx()); if( nativeName!=null ) return external(fptr,nativeName); FunNode fun = _code.link(tfp); - if( fun != null && !_code.owns(fun) ) + if( fun != null && !_code.emits(fun) ) _externals.put(fptr,fun._name); else _internals.put(fptr,fun); @@ -249,7 +249,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { FunNode entry = null; String entryName = _code.entryClinitName(); for( FunNode fun : _code._linker ) { - if( fun != null && !fun.isDead() && _code.owns(fun) ) { + if( fun != null && !fun.isDead() && _code.emits(fun) ) { if( fun.isClz() ) { if( fun._name.equals(entryName) ) entry = fun; diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FunctionSummary.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FunctionSummary.java new file mode 100644 index 00000000..6cd4035d --- /dev/null +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FunctionSummary.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +// The small, eagerly readable part of a function's serialized implementation. +record FunctionSummary(TypeFunPtr sig, TypeTuple state, String name, int size, int[] classDependencyFIDXs) { + void install(CodeGen code, CompUnit cu) { + FunNode fun = new FunNode(null,sig,name,cu,null,cu._start); + fun._approxUIDs=size; + fun.init(); + // First user stays in output slot zero until the summary is removed. + SummaryNode body = new SummaryNode(state,classDependencyFIDXs,fun); + ParmNode rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,code.con(TypeRPC.BOT)).init(); + ParmNode mem = new ParmNode("$mem",1,TypeMem.BOT,fun,cu._start.proj(1)).init(); + body.addDef(mem); + for( int i = 0; i<sig.nargs(); i++ ) + body.addDef(new ParmNode("arg"+i,i+2,sig.arg(i),fun,code.con(sig.arg(i))).init()); + body.init(); + Node ctrl = new CProjNode(body,0,"ctrl").init(); + Node memory = new ProjNode(body,1,"mem").init(); + Node value = new ProjNode(body,2,"value").init(); + ReturnNode ret = new ReturnNode(ctrl,memory,value,rpc,fun).init(); + fun.setRet(ret); + cu._stop.addDef(ret); + code.link(fun); + } +} diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 09eb8d33..8708818b 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -9,31 +9,47 @@ import java.util.*; public abstract class GlobalCodeMotion { + // Ideal execution needs a schedule, but neither CLInit lowering nor + // interprocedural optimization. Each loaded object is prepared once. + public static Ary<CFGNode> forEval(CodeGen code, StartNode start, StopNode stop) { + Ary<FunNode> funs = Unlink.forEval(start,stop); + start.buildLoopTree(funs,stop); + return buildCFG(code,start,stop); + } + // Arrange that the existing isCFG() Nodes form a valid CFG. The // Node.use(0) is always a block tail (either IfNode or head of the // following block). There are no unreachable infinite loops. public static void buildCFG( CodeGen code ) { + code._cfg = buildCFG(code,code._start,code._stop); + } + + // Schedule one graph, including an object loaded while Eval2 is running. + // Other graphs (and their active evaluation frames) are left untouched. + public static Ary<CFGNode> buildCFG(CodeGen code, StartNode start, StopNode stop) { Ary<CFGNode> rpo = new Ary<>(CFGNode.class); - _rpo_cfg(null, code._start, code.visit(), rpo); + _rpo_cfg(null, start, code.visit(), rpo); // Reverse in-place for( int i=0; i< rpo.size()>>1; i++ ) rpo.swap(i,rpo.size()-1-i); - // Set global CFG - code._cfg = rpo; - - schedEarly(code); + schedEarly(code,start,rpo); // Break up shared global constants by functions - breakUpGlobalConstants(code._start); + breakUpGlobalConstants(start); code._visit.clear(); - schedLate(code); + schedLate(code,stop); + return rpo; } // Post-Order of CFG private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, Ary<CFGNode> rpo) { if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) ) return; // Been there, done that + // A shared dead-control node can also reach an unloaded function's + // Return. Its wrapper is a dispatch target, not executable code. + if( cfg instanceof FunNode fun && fun.summary()!=null || + cfg instanceof ReturnNode ret && ret.fun().summary()!=null ) return; assert !( def instanceof ReturnNode && use instanceof CallEndNode ); // All calls unwired now assert !( def instanceof CallNode && use instanceof FunNode ); // All calls unwired now visit.set(cfg._nid); @@ -59,8 +75,8 @@ public abstract class GlobalCodeMotion { for( Node use : con._outputs.asAry() ) { if( use==null || globals.containsKey(use) ) continue; FunNode fun = useFun(use); - if( fun==null ) continue; // Global metadata has no function owner. - assert CodeGen.CODE._mach==null || CodeGen.CODE.owns(fun); // Ideal evaluation includes imported bodies. + if( fun==null || fun.summary()!=null ) continue; // Metadata has no executable owner. + assert CodeGen.CODE._mach==null || fun.isFromSource(); // Ideal evaluation includes imported bodies. var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); Node copy = cloneGlobal(con,fun,globals,local); for( int i=0; i<use.nIns(); i++ ) @@ -98,36 +114,36 @@ public abstract class GlobalCodeMotion { // (except at loops). Since defs are visited first - and hoisted as early // as possible, when we come to a use we place it just after its deepest // input. - private static void schedEarly(CodeGen code) { + private static void schedEarly(CodeGen code, StartNode start, Ary<CFGNode> cfgs) { // Reverse Post-Order on CFG - for( CFGNode cfg : code._cfg ) { + for( CFGNode cfg : cfgs ) { cfg.loopDepth(); for( Node n : cfg._inputs ) - _schedEarly(n,code ); + _schedEarly(n,code,start ); // In dead infinite loops, entire code blocks may be unreachable // from below. Reach down from the CFG to their Phis so their // inputs are scheduled too. if( cfg instanceof RegionNode ) for( Node phi : cfg._outputs ) if( phi instanceof PhiNode ) - _schedEarly(phi,code ); + _schedEarly(phi,code,start ); } } - private static void _schedEarly(Node n, CodeGen code) { + private static void _schedEarly(Node n, CodeGen code, StartNode start) { if( n==null || code._visit.get(n._nid) ) return; // Been there, done that - assert !(n instanceof CFGNode); + assert !(n instanceof CFGNode) : n.getClass().getSimpleName()+"#"+n._nid+" outside scheduled CFG"; code._visit.set(n._nid); // Schedule inputs first, except Phis: following their backedges would // enter a data cycle before its control has been scheduled. for( Node def : n._inputs ) if( def!=null && !(def instanceof PhiNode) ) - _schedEarly(def,code); + _schedEarly(def,code,start); // An existing edge 0 already supplies control (or a Phi/Proj binding). if( n.in(0)==null ) { // Schedule at deepest input - CFGNode early = code._start; // Maximally early, lowest idepth + CFGNode early = start; // Maximally early, lowest idepth for( int i=1; i<n.nIns(); i++ ) if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() ) early = n.in(i).cfg0(); // Latest/deepest input @@ -136,7 +152,7 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ - private static void schedLate( CodeGen code ) { + private static void schedLate( CodeGen code, StopNode stop ) { CFGNode[] late = new CFGNode[code.UID()]; Node[] ns = new Node[code.UID()]; // Record Load NIDs at all their CFG block choices, then check against @@ -144,7 +160,7 @@ public abstract class GlobalCodeMotion { int[] anti = new int[code.UID()]; Ary<Node> antideps = new Ary<>(Node.class); // Breadth-first scheduling - breadth(code._stop,ns,late,anti, antideps); + breadth(stop,ns,late,anti, antideps); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) 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 c5120370..a9f4206a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -14,8 +14,9 @@ abstract class Iter { // can only be removed, never added. Seed the complete graph once. boolean hasImports = code._externPaths != null; code._start.walk(n -> { - if( !(n instanceof ConstantNode) ) - n._type = hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); + // 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; }); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java index b6b3a22c..3b1d3182 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java @@ -108,8 +108,12 @@ public abstract class ListScheduler { // List schedule every block public static void sched( CodeGen code ) { + sched(code._cfg); + } + + public static void sched(Ary<CFGNode> cfgs) { XS.clear(); - for( CFGNode bb : code._cfg ) + for( CFGNode bb : cfgs ) if( bb.blockHead() ) local(bb,false); } 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 3b3f9f19..dc5742f7 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -142,7 +142,7 @@ abstract public class Opto { // Function is now reachable by unknown callers through Start. The // default inputs must therefore use conservative declared types. - private static void linkStart( CodeGen code, FunNode fun ) { + static void linkStart( CodeGen code, FunNode fun ) { assert !fun.isDead(); StartCUNode start = fun._compunit._start; if( !fun.unknownCallers() ) { 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 d7c0f7e2..016e4062 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -103,7 +103,7 @@ public abstract class ParseAll { // Load all pre-compiled CompUnits for( CompUnit cu : NEEDS_LOAD ) - loadCompUnit(code,cu); + loadSummaries(code,cu); // Many types will have been declared cyclically either internally or // across multiple compilation units. @@ -239,7 +239,7 @@ public abstract class ParseAll { try { NEEDS_LOAD.add(cunit); // Load dependent classes - ElfReader elf = ElfReader.load(cunit._obj,cunit); + ElfReader elf = code.getElf(cunit._obj); elf.loadPublicSymbols(); // Register bundled definitions before resolving dependencies or IR. for( String fname : elf._units ) @@ -270,12 +270,26 @@ public abstract class ParseAll { return elf == null ? null : elf._file; } - private static void loadCompUnit(CodeGen code, CompUnit cunit) { + private static void loadSummaries(CodeGen code, CompUnit cu) { + ElfReader elf = code.getElf(cu._obj); + elf.loadPublicTypes(code); + cu._clz = elf._clz; + cu.setStart(code); + new ProjNode(cu._start,1,"$mem").init(); + for( FunctionSummary summary : elf._functions ) summary.install(code,cu); + } + + public static void loadCompUnit(CodeGen code, CompUnit cunit) { // Expecting a previously compiled object file assert cunit._obj != null; // Extract published symbols and put them in the internal tables; // cross-references will pick them up there. - ElfReader elf = ElfReader.load(cunit._obj,cunit); + ElfReader elf = code.getElf(cunit._obj); + if( elf._nodes!=null ) return; + StartCUNode oldStart = cunit._start; + StopCUNode oldStop = cunit._stop; + ProjNode oldMem = oldStart==null ? null : oldStart.proj(1); + if( oldMem!=null && oldMem.iskeep() ) oldMem.unkeep(); elf.loadSimple(code); cunit._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cunit._cname)); StartNode lstart = (StartNode)elf._nodes.at(0); @@ -291,7 +305,17 @@ public abstract class ParseAll { for( Node ret : stop._inputs ) { FunNode fun = ((ReturnNode)ret).fun(); + FunNode old = code._link(fun.sig().fidx()); code.link(fun); + if( old!=null && old.summary()!=null && !old.isDead() ) { + old.ret().keep(); + for( int i = 1; i<old.nIns(); i++ ) + if( old.in(i) instanceof CallNode call ) { + call.unlink(old,i--); + call.link(fun); + } + old.ret().unkeep().subsume(fun.ret()); + } } } @@ -299,6 +323,12 @@ public abstract class ParseAll { for( Node lstopcu : lstop._inputs ) code._stop.addDef(lstopcu); lstart.subsume(code._start); + if( oldStart!=null && oldStart!=cunit._start ) { + int idx = code._stop._inputs.find(oldStop); + if( idx!=-1 ) code._stop.delDef(idx); + oldStart.subsume(cunit._start); + } + code.addAll(elf._nodes); // Add the new top-level loaded class Parser.TYPES.put(cunit._clz._name,cunit._clz); @@ -401,7 +431,7 @@ public abstract class ParseAll { } catch( IOException ioe ) { throw new RuntimeException(ioe); } - ElfReader typedElf = ElfReader.load(cunit._obj,cunit); + ElfReader typedElf = code.getElf(cunit._obj); if( typedElf != null ) typedElf.loadPublicTypes(code); TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); if( clz == null ) diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 5a74ded2..9984d99d 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -16,28 +16,30 @@ abstract public class Serialize { } static void serialize( CodeGen code ) { + // Anonymous functions also need names when another object refers to them. + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() && fun._name==null ) + fun._name=code._fidxs.symbol(fun.sig().fidx()); + ArrayList<CompUnit> units = new ArrayList<>(code._compunits.values()); + units.sort(Comparator.comparing(cu -> cu._fname)); + for( CompUnit cu : units ) { + if( cu._src==null ) continue; + BAOS serial = serialize(code,cu); + code._serials.put(cu,serial); + if( cu._fname.equals(code._srcName==null ? "Test" : code._srcName) ) code._serial=serial; + } + } - // Get all Nodes in a sane order - Ary<Node> nodes = nodeOrder(code); - - // Array of dependent file names + private static BAOS serialize(CodeGen code, CompUnit top) { + Ary<Node> nodes = nodeOrder(code,top); HashSet<String> xdeps = new HashSet<>(); - for( CompUnit cu : code._compunits.values() ) { - if( cu._deps != null ) - for( CompUnit cudep : cu._deps ) - xdeps.add(cudep._fname); - } - String[] deps = xdeps.toArray(new String[xdeps.size()]); + // Retain build dependencies even when their calls were inlined away. + if( top._deps!=null ) for( CompUnit dep : top._deps ) + if( dep!=top ) xdeps.add(dep._fname); + if( top._par!=null ) xdeps.add(top._par._fname); + String[] deps = xdeps.toArray(new String[0]); Arrays.sort(deps); - Ary<String> owned = new Ary<>(String.class); - for( CompUnit cu : code._compunits.values() ) - if( cu._src!=null ) owned.add(cu._fname); - String[] units = owned.asAry(); - Arrays.sort(units); - - // Top-level clazz being reported - String topName = code._srcName == null ? "Test" : code._srcName; - CompUnit top = code._compunits.get(topName); + String[] units = {top._fname}; TypeStruct clz = top._clz; // Preserve which same-named structs are the source-level declarations. @@ -67,7 +69,7 @@ abstract public class Serialize { // --- Expensive bijection assert // Record serialized IR for later ELF writing - code._serial = baos; + return baos; } // -------------------------------------------------- @@ -90,6 +92,7 @@ abstract public class Serialize { // Count unique Types var types = new HashMap<Type,Integer>(); + IdentityHashMap<FunNode,TypeTuple> summaries = new IdentityHashMap<>(); // Count published types *first*, so can align with published strings types.put(Type.TOP,0); types.put( clz, types.size() ); @@ -103,7 +106,18 @@ abstract public class Serialize { for( Node n : nodes ) { n._type.gather(types); if( n instanceof CallEndNode cend ) cend._rpc.gather(types); - if( n instanceof FunNode fun ) fun.sig().gather(types); + if( n instanceof FunNode fun ) { + fun.sig().gather(types); + TypeTuple state = (TypeTuple)fun.ret()._type; + TypeMem mem = (TypeMem)state.mem(); + // Retention can happen on a path that never returns. The + // unit's escape summary includes those native-call effects. + TypeMem escaped = (TypeMem)((TypeTuple)fun._compunit._stop._type).mem(); + mem=mem.makeFrom(XInt.meet(mem._escFs,escaped._escFs),XInt.meet(mem._escAs,escaped._escAs)); + state=state.makeFrom(1,mem); + summaries.put(fun,state); + state.gather(types); + } if( n instanceof ParmNode parm ) parm._declaredType.gather(types); if( n instanceof TypeNode con ) con._con .gather(types); } @@ -205,6 +219,22 @@ abstract public class Serialize { } + // Function summaries precede the graph, so declarations and call + // behavior are available without allocating the implementation nodes. + ClassInitDependencies init = new ClassInitDependencies(CodeGen.CODE); + int nfuncs = 0; + for( Node n : nodes ) if( n instanceof FunNode ) nfuncs++; + baos.packed4(nfuncs); + for( Node n : nodes ) if( n instanceof FunNode fun ) { + baos.packed2(types.get(fun.sig())); + baos.packed2(types.get(summaries.get(fun))); + baos.packed2(fun._name==null ? 0 : strs.get(fun._name)); + baos.packed4(fun._approxUIDs); + int[] edges = init._edgess[fun.sig().fidx()]; + baos.packed4(edges==null ? 0 : edges.length); + if( edges!=null ) for( int edge : edges ) baos.packed4(edge); + } + // D - Write the nodes. Since this is expected to be the bulk of the // data, we might want to explore various options. @@ -306,6 +336,7 @@ abstract public class Serialize { record TypeRead(Type[] types, String[] strs, GlobalBits fileAliases, GlobalBits fileFidxs, GlobalBits fileRpcs) {} static TypeRead readTypes( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { + if( elf._types!=null ) return elf._types; BAOS bais = elf._bais; // Initialize the mapping from bits/tags to types Type.TAGOFFS(); @@ -384,7 +415,17 @@ abstract public class Serialize { TypeStruct ts = elf._pubTypes[i] = (TypeStruct)types[pubTypeIds[i]]; Parser.TYPES.put(ts._name,ts); } - return new TypeRead(types,strs,fileAliases,fileFidxs,fileRpcs); + elf._functions = new FunctionSummary[bais.packed4()]; + for( int i = 0; i<elf._functions.length; i++ ) { + TypeFunPtr sig = (TypeFunPtr)types[bais.packed2()]; + TypeTuple state = (TypeTuple)types[bais.packed2()]; + String name = strs[bais.packed2()]; + int size = bais.packed4(); + int[] edges = new int[bais.packed4()]; + for( int j = 0; j<edges.length; j++ ) edges[j]=fidxs.map(fileFidxs,bais.packed4()); + elf._functions[i]=new FunctionSummary(sig,state,name.isEmpty() ? fidxs.symbol(sig.fidx()) : name,size,edges); + } + return elf._types = new TypeRead(types,strs,fileAliases,fileFidxs,fileRpcs); } static void readAll( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { @@ -394,76 +435,83 @@ abstract public class Serialize { String[] strs = tread.strs(); GlobalBits fileAliases = tread.fileAliases(); - // D - Read the nodes - - // Number of nodes - int num = bais.packed4(); - // Packed array of nodes - Ary<Node> nodes = new Ary<>(Node.class); - CompUnit cu = null; - for( int i=0; i<num; i++ ) { - Node.Tag tag = Node.Tag.VALS[bais.packed1()]; - Type t = types[bais.packed2()]; - Node n = tag.make(bais,strs,types,fileAliases,aliases); - n._type = t; - nodes.push(n); - // A little extra for FunNodes - if( n instanceof StartCUNode startcu ) { - cu = code._compunits.get(startcu._fname==null ? (code._srcName==null ? "Test" : code._srcName) : startcu._fname); - assert cu != null; - } - if( n instanceof StopCUNode stopcu ) { - cu = null; - } - if( n instanceof FunNode fun ) { - assert cu != null; - fun._compunit = cu; - } - if( n instanceof ExternNode ext && ext._con instanceof TypeFunPtr tfp && tfp.isConstant() ) { - String old = code.externFunc(tfp.fidx()); - if( old == null ) - code.externFunc(tfp.fidx(), ext._extern); - else - assert old.equals(ext._extern); + CodeGen.Phase prior = code._phase; + code._phase=CodeGen.Phase.Parse; // Constructors must tolerate an incomplete graph. + try { + // D - Read the nodes + + // Number of nodes + int num = bais.packed4(); + // Packed array of nodes + Ary<Node> nodes = new Ary<>(Node.class); + CompUnit cu = null; + for( int i = 0; i<num; i++ ) { + Node.Tag tag = Node.Tag.VALS[bais.packed1()]; + Type t = types[bais.packed2()]; + Node n = tag.make(bais,strs,types,fileAliases,aliases); + n._type = t; + nodes.push(n); + // A little extra for FunNodes + if( n instanceof StartCUNode startcu ) { + cu = code._compunits.get(startcu._fname==null ? (code._srcName==null ? "Test" : code._srcName) : startcu._fname); + assert cu != null; + } + if( n instanceof StopCUNode stopcu ) { + cu = null; + } + if( n instanceof FunNode fun ) { + assert cu != null; + fun._compunit = cu; + if( fun._name==null || fun._name.isEmpty() ) fun._name=fidxs.symbol(fun.sig().fidx()); + } + if( n instanceof ExternNode ext && ext._con instanceof TypeFunPtr tfp && tfp.isConstant() ) { + String old = code.externFunc(tfp.fidx()); + if( old == null ) + code.externFunc(tfp.fidx(), ext._extern); + else + assert old.equals(ext._extern); + } } - } - // Node edges - for( Node n : nodes ) { - int len = n.nIns(); - for( int i=0; i<len; i++ ) { - int idx = bais.packed2(); - Node def = idx==0 ? null : nodes.at(idx-1); - // MemMerge precise aliases are encoded by their input slot. - // Remap populated file-local slots into this compilation's - // local alias numbering; null holes carry no identity. - int local = i; - if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) { - if( def == null ) continue; - local = aliases.map(fileAliases,i); + // Node edges + for( Node n : nodes ) { + int len = n.nIns(); + for( int i = 0; i<len; i++ ) { + int idx = bais.packed2(); + Node def = idx==0 ? null : nodes.at(idx-1); + // MemMerge precise aliases are encoded by their input slot. + // Remap populated file-local slots into this compilation's + // local alias numbering; null holes carry no identity. + int local = i; + if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) { + if( def == null ) continue; + local = aliases.map(fileAliases,i); + } + n.setDefX(local,def); + // Call's output[0] is always the CallEnd + if( n instanceof CallEndNode cend && i==0 ) { + var outs = cend.call()._outputs; + outs.swap(0,outs._len-1); + } } - n.setDefX(local,def); - // Call's output[0] is always the CallEnd - if( n instanceof CallEndNode cend && i==0 ) { - var outs = cend.call()._outputs; - outs.swap(0,outs._len-1); + // A little extra for FunNodes + if( n instanceof FunNode fun ) { + // Return is hooked like an edge + ReturnNode ret = (ReturnNode)nodes.at(bais.packed2()-1); + fun.setRet(ret); + ret._fun = fun; } } - // A little extra for FunNodes - if( n instanceof FunNode fun ) { - // Return is hooked like an edge - ReturnNode ret = (ReturnNode)nodes.at(bais.packed2()-1); - fun.setRet(ret); - ret._fun = fun; - } - } - // Add edge from Start to Stop - StartNode start = (StartNode)nodes.at(0); - StopNode stop = (StopNode)nodes.last(); - start.setDef(1,stop); - - assert check(code,nodes); - elf._nodes = nodes; + // Add edge from Start to Stop + StartNode start = (StartNode)nodes.at(0); + StopNode stop = (StopNode)nodes.last(); + start.setDef(1,stop); + + // A body materialized after SCCP joins a different analysis context. + // Its saved types are reset and checked by the ensuing fixed-point solve. + assert prior!=CodeGen.Phase.Parse || check(code,nodes); + elf._nodes = nodes; + } finally { code._phase=prior; } } // Check loaded types and nodes are consistent @@ -501,16 +549,22 @@ abstract public class Serialize { BitSet visit = code.visit(); Ary<Node> nodes = new Ary<>(Node.class); visit.set(code._stop._nid); + // Return-linked function constants are global. Do not walk through + // them from one function into stores or calls in a different unit. + for( Node n : code._start._outputs ) if( n!=null && n.isConst() ) visit.set(n._nid); // Walk all listed functions, in this single compilation unit for( FunNode fun : code._linker ) if( fun!=null && !fun.isDead() && fun._compunit == cu ) _funWalk(fun,nodes,visit); + for( Node n : code._start._outputs ) if( n!=null && n.isConst() ) visit.clear(n._nid); + // Just constants used by the listed functions Ary<Node> cons = new Ary<>(Node.class); cons.add(code._start); for( Node n : code._start._outputs ) { - if( n instanceof ConstantNode con && !visit.get(con._nid) ) { + Node con = n; + if( con.isConst() && !visit.get(con._nid) ) { for( Node use : con.outs() ) { // PtrToInt is another zero-code value rooted at a global // constant. Its array-body Add is the value used by the diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java index 616753d4..a4147576 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java @@ -37,7 +37,7 @@ public final class StaticData { StaticData(Encoding enc) { this.enc=enc; - prefix=enc._code.entryClinitName()+"$DATA$"; + prefix=(enc._code._emitUnit==null ? enc._code.entryClinitName() : enc._code._emitUnit._cname)+"$DATA$"; } static boolean isClass(Type t) { @@ -68,7 +68,7 @@ public final class StaticData { String symbol=clz ? ((TypeStruct)t)._name.substring(Parser.CLZ.length())+".$class" : t instanceof TypeFunPtr fp ? functionSymbol(fp) : prefix+objects.size(); ObjectData obj=new ObjectData(t,symbol,!clz && (!(t instanceof TypeStruct ts) || ts.isConstant()), - owner!=null && owner._src==null); + owner!=null && !enc._code.emits(owner)); objects.put(key,obj); // Register before following fields: class objects may refer to each other. if( !obj.external && t instanceof TypeStruct ts ) @@ -96,7 +96,7 @@ public final class StaticData { // Definitions belong to their compilation unit, even if every local use folded. ArrayList<CompUnit> units=new ArrayList<>(enc._code._compunits.values()); units.sort(Comparator.comparing(cu -> cu._cname==null ? "" : cu._cname)); - for( CompUnit cu : units ) if( cu._src!=null && cu._clz!=null ) object(cu._clz); + for( CompUnit cu : units ) if( enc._code.emits(cu) && cu._clz!=null ) object(cu._clz); for( ObjectData obj : entries() ) { if( obj.external ) continue; BAOS bits=obj.readOnly ? enc._cpool : enc._sdata; @@ -157,7 +157,7 @@ public final class StaticData { if( ext!=null ) address=enc.externalAddress(ext); else if( fun==null ) address=address(object(fp),cpool,sdata); else { - if( !enc._code.owns(fun) ) throw new IllegalArgumentException("Unlinked function "+functionSymbol(fp)); + if( !fun.isFromSource() ) throw new IllegalArgumentException("Unlinked function "+functionSymbol(fp)); address=enc.opStart(fun); } } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index 9b4b0995..fb82ef0c 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -9,6 +9,7 @@ import com.seaofnodes.simple.util.Ary; // obligations. Queue surviving CLInits during the same walk for Lower's Iter. abstract class TypeCheck { static void run(CodeGen code) { + code.resolveInitCycles(); // Check for class-init cycles first; such a cycle can prevent other // things from resolving types. The dependency graph is temporary. String clzInitCycle = new ClassInitDependencies(code).check(); 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 fb1c4a6f..17f8107a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java @@ -1,20 +1,66 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.util.Ary; // Discard call-graph edges after LoopTree. Machine selection keeps only this // object's bodies; ideal evaluation keeps imports so their calls can execute. abstract class Unlink { + // Disconnect compiler-only interprocedural edges before scheduling. Keep + // signatures in the linker; runtime calls resolve FIDXs, not graph edges. + static Ary<FunNode> forEval(StartNode start, StopNode stop) { + Ary<Node> nodes = new Ary<>(Node.class); + start.walk(n -> { nodes.add(n); return null; }); + Ary<FunNode> funs = new Ary<>(FunNode.class); + for( Node n : nodes ) + if( n instanceof FunNode fun ) { + fun.ret().keep(); + if( fun.summary()==null ) funs.add(fun); + } + for( Node n : nodes ) { + if( n instanceof CallNode call ) call.unlink_all(); + if( n instanceof FunPtrNode ptr && ptr.ret()!=null ) ptr.setDef(1,null); + } + for( FunNode fun : funs ) { + // Keep bodies rooted for scheduling after their callers detach. + if( fun.nIns()==1 ) { + fun.addDef(fun._compunit._start); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) { + ConstantNode con = ConstantNode.raw(parm._type); + con.setDef(0,start); + parm.addDef(con); + } + } + restoreRPC(fun); + } + // 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++ ) { + StopCUNode unit = (StopCUNode)stop.in(i); + boolean summary = false; + for( Node r : unit._inputs ) + summary |= ((ReturnNode)r).fun().summary()!=null; + if( summary ) { + unit.start().setDef(0,null); + stop.delDef(i--); + } + } + for( Node n : nodes ) + if( n instanceof FunNode fun ) fun.ret().unkeep(); + return funs; + } + private static void unlinkImports(CodeGen code) { // Imported function constants keep their symbolic identity, not an // embedded copy of the other object's Return and body. for( Node n : code._start._outputs.asAry() ) - if( n instanceof FunPtrNode ptr && ptr.ret()!=null && !code.owns(ptr.fun()) ) { + if( n instanceof FunPtrNode ptr && ptr.ret()!=null && !ptr.fun().isFromSource() ) { ptr.liftType(ptr._type); ptr.setDef(1,null); } for( FunNode fun : code._linker ) { - if( fun==null || fun.isDead() || code.owns(fun) ) + if( fun==null || fun.isDead() || fun.isFromSource() ) continue; for( int i=1; i<fun.nIns(); i++ ) if( fun.in(i) instanceof CallNode call ) @@ -43,7 +89,7 @@ abstract class Unlink { // Imported functions are not emitted by this object. Ideal // evaluation retains them so their calls can actually execute. - if( removeImports && !code.owns(fun) ) { + if( removeImports && !fun.isFromSource() ) { while( fun.nIns() > 1 ) { if( fun.in(1) instanceof CallNode call ) call.unlink(fun,1); @@ -88,15 +134,7 @@ abstract class Unlink { // Unlink from Call for( int i=2; i<fun.nIns(); i++ ) ((CallNode)fun.in(i)).unlink(fun,i--); - if( fun.rpc()==null ) { // Ensure valid RPC - // First make sure a valid RPC; single-call into multi-fun will have each - // function having a single call site, so the RPC becomes a constant and - // folds - but since multiple targets, the Call never inlines. Recreate a - // valid RPC so codegen (and Eval2) understands the calling convention. - ParmNode rpc = new ParmNode( "$rpc", 0, ret.rpc()._type, fun ); - rpc.addDef(ret.rpc()); - ret.setDef( 3, rpc.init() ); - } + restoreRPC(fun); } code._stop.walk(n -> { @@ -109,4 +147,15 @@ abstract class Unlink { return 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 + // call cannot inline it. Restore the parameter for codegen and for + // Eval2's continuation, now that calls no longer supply graph edges. + ReturnNode ret = fun.ret(); + ParmNode rpc = new ParmNode("$rpc",0,ret.rpc()._type,fun); + rpc.addDef(ret.rpc()); + ret.setDef(3,rpc.init()); + } } 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 7bc17c75..d33670d1 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -115,24 +115,8 @@ public class CLInitNode extends CFGNode implements MultiNode { Node ctrl = in(0); Node memory = mem(); - // A child body may assume its parent has finished. Establish that - // requirement first, then test the child's flag in the resulting memory. - CompUnit parent = cu()._par; - if( parent!=null ) { - Node ptr = CodeGen.CODE.con(TypeMemPtr.make((byte)2,parent._clz,true)); - Field flag = parent._clz.field("$init"); - Node off = CodeGen.CODE.con(parent._clz.offset(parent._clz.find("$init"))); - Node parentReady = CodeGen.CODE.add(new LoadNode(_loc,"$init",flag._alias,ctrl,memory,ptr,off).init()); - CLInitNode init = CodeGen.CODE.add(new CLInitNode(_loc,ctrl,memory,ptr,parentReady).init()); - ctrl = CodeGen.CODE.add(new CProjNode(init,0,ScopeNode.CTRL).init()); - memory = CodeGen.CODE.add(new ProjNode(init,1,ScopeNode.MEM0).init()); - } - - Node childOff = CodeGen.CODE.con(cu()._clz.offset(cu()._clz.find("$init"))); - // Read the child's flag after establishing its parent's memory effects. - Node ready = CodeGen.CODE.add(new LoadNode(_loc,"$init",flag()._alias,ctrl,memory,ptr(),childOff).init()); - - IfNode iff = CodeGen.CODE.add(new IfNode(ctrl,ready).init()); + // The callee establishes its parent before setting its own flag. + IfNode iff = CodeGen.CODE.add(new IfNode(ctrl,ready()).init()); Node done = CodeGen.CODE.add(new CProjNode(iff,0,"True").init()); Node cold = CodeGen.CODE.add(new CProjNode(iff,1,"False").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 fc6effdc..73f67479 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -160,7 +160,7 @@ public class CallEndNode extends CFGNode implements MultiNode { } public byte maybeInline() { - byte inline = inlineCandidate(); + byte inline = inlineCandidate(false); if( CodeGen.CODE._midAssert ) return inline; _inline = inline; @@ -170,8 +170,23 @@ public class CallEndNode extends CFGNode implements MultiNode { return _inline; } - // Check if candidate right now, sets no flags - private byte inlineCandidate() { + // This CallEnd might be an inline candidate, but the actual code is in + // another CompUnit and needs loading to decide. Called at an empty worklist. + public boolean loadForInline() { + CodeGen code = CodeGen.CODE; + if( code._phase!=CodeGen.Phase.IterPostOpto || nIns()!=2 || + !(in(1) instanceof ReturnNode ret) || ret.fun().summary()==null ) return false; + // Fetch bodies only for calls in functions compiled from source here. + // Calls inside imported functions become eligible when inlined into one. + if( !(in(0) instanceof CallNode call) || !call.fun().isFromSource() || + inlineCandidate(true)<=0 ) return false; + code.loadForInline(ret.fun()._compunit); + return true; + } + + // Check if candidate right now, sets no flags. Loading uses the same + // policy, but can only estimate the size of a summarized body. + private byte inlineCandidate(boolean loading) { if( _inline < -2 ) return -2; // Never if( _folding ) return -2; // No, and will collapse anyways if( !(in(0) instanceof CallNode call) ) return -2; // malformed because mid-death @@ -210,10 +225,12 @@ public class CallEndNode extends CFGNode implements MultiNode { // A large parse can leave only a tiny initializer. Recognize that // and await cleanup to shrink the body. if( fun._approxUIDs >= maxSize ) { - if( !smallBody(fun) ) return -1; - } else if( fun.body().cardinality() >= maxSize ) // Expensive size check + if( fun.summary()!=null || !smallBody(fun) ) return -1; + } else if( fun.summary()==null && fun.body().cardinality() >= maxSize ) // Expensive size check return -1; // Try later (if cleanup makes the real body small enough) + if( fun.summary()!=null ) return loading ? (byte)1 : (byte)-1; + // Can be cloned but not trivial if( fun.nIns() > 2 ) { addDep(fun); return 2; } 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 edde247a..fe3c3162 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -82,6 +82,13 @@ public class FunNode extends RegionNode { } public ParmNode rpc() { return parm(0); } + // An unloaded body's Summary is constructed before every other user. + public SummaryNode summary() { return nOuts()>0 && out(0) instanceof SummaryNode summary ? summary : null; } + + // This invocation compiles the defining CompUnit from source. Imported + // functions still belong to a CompUnit, but its _src is null. + public boolean isFromSource() { return _compunit!=null && _compunit._src!=null; } + // Cannot create the Return and Fun at the same time; one has to be first. // So setting the return requires a second step. public void setRet(ReturnNode ret) { _ret=ret; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index df686bcf..45f7a6fa 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -45,7 +45,7 @@ public class LoopNode extends RegionNode { x = x.idom(); } // Found a no-exit loop. Insert an exit - NeverNode iff = (NeverNode)new NeverNode(1.2f,back()).peephole(); // Ideal never-branch + NeverNode iff = new NeverNode(1.2f,back()).init(); // Ideal never-branch CProjNode t = new CProjNode(iff,0,"True" ).init(); CProjNode f = new CProjNode(iff,1,"False").init(); setDef(2,t); // True continues loop, False (never) exits loop @@ -55,7 +55,10 @@ public class LoopNode extends RegionNode { // Now fold control into the exit. Might have 1 valid exit, or an // XCtrl or a bunch of prior NeverNode exits. - Node top = ConstantNode.make(Type.TOP).peephole(); + // Scheduling can prepare a newly loaded object while other code is + // executing. Keep synthetic nodes local; do not GVN into that graph. + Node top = ConstantNode.raw(Type.TOP); + top.setDef(0,fun); Node memout = new MemMergeNode(); memout.addDef(f); // placeholder for control memout.addDef(top); 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 43acf631..a88adee2 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -97,6 +97,9 @@ public class StopCUNode extends StopNode { // 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))); + for( FunNode fun : CodeGen.CODE._linker ) + if( fun!=null && fun.summary()!=null && !fun.summary().isDead() ) + xmem=publicBottom(xmem.escapes(fun.summary().exposed(this))); assert xmem._alias==1 && !xmem._one; return TypeTuple.make(Type.CONTROL,xmem,Type.BOTTOM); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java new file mode 100644 index 00000000..426174e7 --- /dev/null +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.*; +import java.util.HashMap; + +// Analysis of an imported function whose implementation has not been loaded. +// This is never an inlineable or executable body. +public class SummaryNode extends CFGNode implements MultiNode { + + public TypeTuple _state; + // Callees and touched class initializers, by FIDX, for class-init cycle checks. + public final int[] _classDependencyFIDXs; + + public SummaryNode(TypeTuple state, int[] classDependencyFIDXs, Node... inputs) { + super(inputs); + _state = state; + _classDependencyFIDXs = classDependencyFIDXs; + } + + @Override public String label() { return "Summary"; } + @Override public boolean blockHead() { return true; } + @Override public Type compute() { + if( in(0)._type.isHigh() ) return TypeTuple.STATE.dual(); + // A library summary does not forget escapes already present in the caller. + TypeMem mem = in(1)._type instanceof TypeMem m ? m : in(1)._type.isHigh() ? TypeMem.TOP : TypeMem.BOT; + mem = (TypeMem)mem.meet(_state.mem()); + for( int i = 2; i<nIns(); i++ ) mem=mem.escapes(in(i)._type); + return TypeTuple.make(_state.ctl(),mem,_state.ret()); + } + @Override public Node idealize() { return null; } + public TypeMem exposed(Node dep) { + dep.addDepForwards(this); + if( dep.addDepForwards(in(0))._type.isHigh() ) return TypeMem.START; + TypeMem mem = (TypeMem)_state.mem(); + for( int i = 2; i<nIns(); i++ ) mem=mem.escapes(dep.addDepForwards(in(i))._type); + return TypeMem.make(1,Type.BOTTOM,false,false,false,mem._escFs,mem._escAs); + } + @Override boolean _upgradeType(HashMap<String,Type> types) { + TypeTuple state = (TypeTuple)_state.upgradeType(types); + if( state==_state ) return false; + unlock(); + _state=state; + return true; + } + // Materialize an object and publish real FIDX targets without rewriting + // callers or reoptimizing their active graphs. The evaluator schedules + // this object's checked ideal IR before entering any of its functions. + public static ElfReader load(CodeGen code, FunNode fun) { + assert fun.summary()!=null; + ElfReader elf = code.getElf(fun._compunit._obj); + assert elf._nodes==null; // Not loaded yet, or we would already have code for `fun` + elf.loadSimple(code); // Load all the IR, including code for `fun` + StopNode stop = (StopNode)elf._nodes.last(); + for( Node n : stop._inputs ) { + StopCUNode stopcu = (StopCUNode)n; + for( Node r : stopcu._inputs ) { + FunNode target = ((ReturnNode)r).fun(); + target._compunit._start = stopcu.start(); + target._compunit._stop = stopcu; + code.link(target); + } + } + return elf; + } +} |