From 358188c421cb82cf9f0bcc8b2cdca032fc4ffa16 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 28b: Separate Compilation Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- src/main/java/com/seaofnodes/simple/IterPeeps.java | 1 + src/main/java/com/seaofnodes/simple/Parser.java | 40 +- .../simple/codegen/ClassInitDependencies.java | 61 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 387 ++++++++++- .../com/seaofnodes/simple/codegen/CompUnit.java | 100 ++- .../com/seaofnodes/simple/codegen/ElfReader.java | 244 +++++++ .../com/seaofnodes/simple/codegen/ElfWriter.java | 20 +- .../com/seaofnodes/simple/codegen/Encoding.java | 6 +- .../com/seaofnodes/simple/codegen/FinalizeIR.java | 8 +- .../com/seaofnodes/simple/codegen/FinishCalls.java | 57 -- .../seaofnodes/simple/codegen/FunctionSummary.java | 28 + .../com/seaofnodes/simple/codegen/GlobalBits.java | 177 +++++ .../simple/codegen/GlobalCodeMotion.java | 54 +- .../com/seaofnodes/simple/codegen/InstSelect.java | 2 +- .../java/com/seaofnodes/simple/codegen/Iter.java | 72 +- .../seaofnodes/simple/codegen/ListScheduler.java | 6 +- .../com/seaofnodes/simple/codegen/LocalIds.java | 33 - .../java/com/seaofnodes/simple/codegen/Module.java | 98 +++ .../java/com/seaofnodes/simple/codegen/Opto.java | 23 +- .../com/seaofnodes/simple/codegen/ParseAll.java | 219 +++++- .../com/seaofnodes/simple/codegen/Serialize.java | 750 +++++++++++++++++++++ .../com/seaofnodes/simple/codegen/StaticData.java | 8 +- .../com/seaofnodes/simple/codegen/TypeCheck.java | 1 + .../java/com/seaofnodes/simple/codegen/Unlink.java | 174 +++++ .../java/com/seaofnodes/simple/node/AddNode.java | 2 +- .../java/com/seaofnodes/simple/node/AndNode.java | 2 +- .../java/com/seaofnodes/simple/node/ArithNode.java | 5 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 15 +- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 42 ++ .../java/com/seaofnodes/simple/node/CFGNode.java | 1 + .../com/seaofnodes/simple/node/CLInitNode.java | 92 ++- .../java/com/seaofnodes/simple/node/CProjNode.java | 14 +- .../com/seaofnodes/simple/node/CallEndNode.java | 138 ++-- .../java/com/seaofnodes/simple/node/CallNode.java | 41 +- .../com/seaofnodes/simple/node/ConFldOffNode.java | 2 +- .../com/seaofnodes/simple/node/ConstantNode.java | 7 +- .../java/com/seaofnodes/simple/node/CtrlNode.java | 2 +- .../java/com/seaofnodes/simple/node/DivNode.java | 2 +- .../com/seaofnodes/simple/node/EscapeNode.java | 7 + .../com/seaofnodes/simple/node/ExternNode.java | 15 +- .../seaofnodes/simple/node/ExternOffsetNode.java | 7 +- .../com/seaofnodes/simple/node/FldOffNode.java | 2 +- .../java/com/seaofnodes/simple/node/FunNode.java | 41 +- .../com/seaofnodes/simple/node/FunPtrNode.java | 10 +- .../java/com/seaofnodes/simple/node/GuardNode.java | 6 + .../java/com/seaofnodes/simple/node/IfNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 8 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 11 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 5 +- .../java/com/seaofnodes/simple/node/MemOpNode.java | 19 + .../com/seaofnodes/simple/node/MemPhiNode.java | 18 + .../java/com/seaofnodes/simple/node/MinusNode.java | 6 +- .../java/com/seaofnodes/simple/node/MulNode.java | 2 +- .../java/com/seaofnodes/simple/node/NeverNode.java | 2 +- .../java/com/seaofnodes/simple/node/NewNode.java | 10 +- src/main/java/com/seaofnodes/simple/node/Node.java | 80 ++- .../java/com/seaofnodes/simple/node/NotNode.java | 2 +- .../java/com/seaofnodes/simple/node/OrNode.java | 2 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 16 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 14 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 14 +- .../com/seaofnodes/simple/node/PtrToIntNode.java | 2 +- .../com/seaofnodes/simple/node/ReadOnlyNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 5 +- .../com/seaofnodes/simple/node/ReturnNode.java | 10 +- .../com/seaofnodes/simple/node/RoundF32Node.java | 2 +- .../java/com/seaofnodes/simple/node/SarNode.java | 2 +- .../java/com/seaofnodes/simple/node/ShlNode.java | 2 +- .../java/com/seaofnodes/simple/node/ShrNode.java | 2 +- .../com/seaofnodes/simple/node/StartCUNode.java | 15 +- .../java/com/seaofnodes/simple/node/StartNode.java | 8 +- .../com/seaofnodes/simple/node/StopCUNode.java | 45 +- .../java/com/seaofnodes/simple/node/StopNode.java | 10 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 17 +- .../java/com/seaofnodes/simple/node/SubNode.java | 2 +- .../com/seaofnodes/simple/node/SummaryNode.java | 66 ++ .../com/seaofnodes/simple/node/ToFloatNode.java | 2 +- .../com/seaofnodes/simple/node/ToIntegerNode.java | 2 +- .../java/com/seaofnodes/simple/node/TypeNode.java | 1 + .../java/com/seaofnodes/simple/node/XCtrlNode.java | 2 +- .../java/com/seaofnodes/simple/node/XorNode.java | 2 +- .../seaofnodes/simple/node/cpus/arm/CallRRARM.java | 4 +- .../simple/node/cpus/riscv/CallRRISC.java | 2 +- .../simple/node/cpus/x86_64_v2/CallRX86.java | 2 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 2 +- .../java/com/seaofnodes/simple/type/Field.java | 14 +- src/main/java/com/seaofnodes/simple/type/Type.java | 118 ++++ .../com/seaofnodes/simple/type/TypeConAry.java | 14 +- .../com/seaofnodes/simple/type/TypeConAryB.java | 1 - .../java/com/seaofnodes/simple/type/TypeFloat.java | 21 + .../com/seaofnodes/simple/type/TypeFunPtr.java | 28 + .../com/seaofnodes/simple/type/TypeInteger.java | 32 + .../java/com/seaofnodes/simple/type/TypeMem.java | 26 +- .../com/seaofnodes/simple/type/TypeMemPtr.java | 14 + .../java/com/seaofnodes/simple/type/TypePtr.java | 9 + .../java/com/seaofnodes/simple/type/TypeRPC.java | 20 + .../com/seaofnodes/simple/type/TypeScalar.java | 12 + .../com/seaofnodes/simple/type/TypeStruct.java | 17 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 14 + src/main/java/com/seaofnodes/simple/type/XInt.java | 36 +- 100 files changed, 3397 insertions(+), 421 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/codegen/ElfReader.java delete mode 100644 src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java create mode 100644 src/main/java/com/seaofnodes/simple/codegen/FunctionSummary.java create mode 100644 src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java delete mode 100644 src/main/java/com/seaofnodes/simple/codegen/LocalIds.java create mode 100644 src/main/java/com/seaofnodes/simple/codegen/Module.java create mode 100644 src/main/java/com/seaofnodes/simple/codegen/Serialize.java create mode 100644 src/main/java/com/seaofnodes/simple/codegen/Unlink.java create mode 100644 src/main/java/com/seaofnodes/simple/node/SummaryNode.java (limited to 'src/main/java/com') diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index e65ef6d9..42e6695e 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/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/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 6bd02363..83bef882 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.node.ScopeNode.Kind; import static com.seaofnodes.simple.util.Utils.TODO; @@ -308,9 +309,18 @@ public class Parser { } } - // The initializer owns its run-once flag store. Parent initialization - // is a structural requirement, executed before this body by CLInit lowering. + // Each initializer establishes its parent before setting its own + // run-once flag. Keep this in the body so every execution strategy + // shares the same ordering, including direct entry into a child. if( fun.isClz() ) { + if( _ref._par!=null ) { + String pname = addClzPrefix(_ref._par._cname); + TypeStruct parent = (TypeStruct)TYPES.get(pname); + if( parent==null ) parent=TypeStruct.make(pname,true); + Node ptr = con(TypeMemPtr.make((byte)2,parent,true)).keep(); + classInit(loc,ptr); + ptr.unkeep(); + } Node self = fun.parm(2); Field flag = ((TypeMemPtr)self._type)._obj.field("$init"); Node prior = mem().keep(); @@ -2913,6 +2923,32 @@ public class Parser { } + public static void gather(Lexer loc, HashMap strs) { + if( loc==null || loc._cu==null ) return; + Serialize.gather(strs,loc._cu._cname); + String file=loc._cu.sourceFile(); + if( file!=null ) Serialize.gather(strs,file); + } + + public static void packed(Lexer loc, BAOS out, HashMap strs) { + if( loc==null || loc._cu==null ) { out.packed4(0); return; } + out.packed4(loc._position+1); + out.packed4(strs.get(loc._cu._cname)); + String file=loc._cu.sourceFile(); + out.packed4(file==null ? 0 : strs.get(file)); + } + + public static Lexer unpack(BAOS in, String[] strs) { + int pos=in.packed4(); + if( pos==0 ) return null; + String owner=strs[in.packed4()]; + String file=strs[in.packed4()]; + CompUnit cu=CodeGen.CODE._compunits.get(owner.replace('.','/')); + assert cu!=null : owner; + if( !file.isEmpty() ) cu._sourceFile=file; + return new Lexer(cu,pos-1); + } + /** * Copy a lexer from a lexer */ diff --git a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 6c70b71d..46a726b3 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/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 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 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 . // -// (3) Report on cycles +// (3) Report on cycles, if any // public class ClassInitDependencies { private final CodeGen _code; @@ -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,18 +51,38 @@ 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(); } // Return the outgoing init edge set for this function private static int[] walk( CodeGen code, FunNode fun, Ary work, IntHashMap iset, BitSet visit, Ary 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 + // 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); @@ -84,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); } @@ -113,16 +137,26 @@ 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 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 cycleImports() { + Ary 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. @@ -143,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) ) { @@ -151,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"); } } @@ -159,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; @@ -169,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/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 8b3857a1..dea75b2e 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -29,8 +29,10 @@ public class CodeGen { IterPostOpto, // Peepholes and inlining using SCCP results FinalizeIR, // Field layout, offset cleanup, function/CU roots TypeCheck, // Last check for bad programs + Serialize, // Save ideal IR, including opaque class initialization Lower, // Expand checked class initialization to ordinary IR LoopTree, // Build a loop tree; break infinite loops + Unlink, // Unlink call sites before machine code generation Select, // Convert to target hardware nodes Schedule, // Global schedule (code motion) nodes LocalSched, // Local schedule @@ -64,7 +66,12 @@ public class CodeGen { public final String _modDir; // Module Build Root public final String _buildDir; - // Slashed path from source root to the entry file, without ".smp". + // Search path from CWD for `.o` files containing external symbols and types. + // This can contain archives, zips and other .o file containers. + public final Ary _externPaths; + + // Dotted path from module root to file containing the source, sans ".smp". + // e.g. module root: "sys", nested source name "sys.io". public final String _srcName; // Only available for tests, otherwise source comes from the CompUnit @@ -73,8 +80,12 @@ public class CodeGen { // Current Working Directory; default module base private final String _cwd; - // Source files discovered in this invocation. All live initializers - // participate in cycle checking, including fully inlined bodies. + // Compilation Units used in this compile; typically one per source/object + // file, although you can nest structs and get more than one. These are all + // required to compile, and are expected to have their source timestamps + // ahead of their obj file. Some of these may entirely be dead or inlined + // in this CompUnit and thus not needed in any linking stage. All the + // alive ones (inlined away or not) participate in class init cycle checks. public HashMap _compunits; // Test shortcut for only one compilation unit @@ -88,7 +99,7 @@ public class CodeGen { // True when fidx is published through a public class or instance field. public boolean publicFIDX(int fidx) { - if( fidx < LocalIds.RESERVED ) return false; + if( fidx < GlobalBits.RESERVED ) return false; // A public class initializer is itself an external root; unlike // constructors and methods, it is not reached through a class field. FunNode fun = _linker.atX(fidx); @@ -134,15 +145,17 @@ public class CodeGen { private int[] _publicFIDXs, _publicAliases; /** - * Freeze the externally visible portion of the program after ParseAll has - * loaded every compilation unit and closed/upgraded all types. Later - * optimization can remove linker entries and create inline-only fidxs; - * neither operation changes this interface. + * Collect every possible public escape - after ParseAll is done - in case + * some code calls a generic function. Example: + * var apply = = { {int->int} f, int x -> f(x); }; // Generic apply() call + * The CallEnd from `f(x)` has to use generic TypeMem.BOT, which + * immediately escapes *everything* including known private functions. + * As weak as this is, its still sharper than "everything". */ void freezePublicInterface() { assert _publicFIDXs==null && _publicAliases==null; int[] fidxs = XInt.EMPTY; - for( int fidx=LocalIds.RESERVED; fidx<_linker._len; fidx++ ) + for( int fidx=GlobalBits.RESERVED; fidx<_linker._len; fidx++ ) if( publicFIDX(fidx) ) fidxs = XInt.make(fidxs,fidx); int[] aliases = XInt.EMPTY; @@ -185,15 +198,15 @@ public class CodeGen { // Test setup; no module nor file; can alter seed & argument; can re-run same CodeGen public CodeGen( String src, Type arg ) { - this(null,null,null, src, 126L, true, arg); + this(null,null,null,null, src, 126L, true, arg); } // Test setup; no module nor file; can alter seed & argument; can re-run same CodeGen public CodeGen( String src, long workListSeed, boolean resetTypes ) { - this(null,null,null, src, workListSeed, resetTypes, TypeInteger.BOT); + this(null,null,null,null, src, workListSeed, resetTypes, TypeInteger.BOT); } // Generic CodeGen, including full module setup - public CodeGen( String modDir, String buildDir, + public CodeGen( String modDir, String buildDir, Ary externPaths, String srcName, String src, long workListSeed, boolean resetTypes, Type arg ) { // Public singleton to avoid passing about this state to a huge count // of places. Probably becomes a TLS at some point. @@ -203,6 +216,7 @@ public class CodeGen { _cwd = System.getProperty("user.dir")+"/"; _modDir = modDir == null ? _cwd : modDir; _buildDir = buildDir == null ? _cwd : buildDir; + _externPaths = externPaths; _srcName = srcName; _callingConv = null; // Calling convention // Source code from test strings, not files @@ -225,7 +239,9 @@ public class CodeGen { } - // Run the requested phases. ELF output contains machine code and data. + // Run requested phases. File export must request Serialize before Lower; + // requesting Export up front does that automatically. Encoding alone does + // not retain reloadable ideal IR. // No code emission, just IR generation public CodeGen driver( Phase phase ) { return driver(phase,null,null,false,false,0); } @@ -245,7 +261,9 @@ public class CodeGen { // The Generic driver public CodeGen driver( Phase target, String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol, int dump ) { - // Parse the entry source and discover all referenced source files. + _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); // Run peepholes to a fixed point step(target, Phase.Iter, this::iter, dump); @@ -257,12 +275,18 @@ 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() Serialize.forTarget(this,target,inMemory), dump); // Replace "fat" nodes with their exploded explicit IR; this can // introduce CFG diamonds step(target, Phase.Lower, this::lower, dump); // Compute the loop-tree, used for approximating exec frequencies for // scheduling and register allocation step(target, Phase.LoopTree, this::loopTree, dump); + // Drop imports for machine selection, retain them for ideal evaluation. + step(target, Phase.Unlink, () -> unlink(cpu!=null), dump); // Instruction selection step(target, Phase.Select, () -> instSelect(cpu,callingConv), dump); // Global Code Motion @@ -273,7 +297,7 @@ public class CodeGen { step(target, Phase.RegAlloc, this::regAlloc, dump); // Encode machine instructions into bits step(target, Phase.Encoding, this::encode, dump); - // Export machine code and data into one ELF file + // Export bits (and serialized IR) into ELF files step(target, Phase.Export, () -> exportELF(inMemory,emitEntrySymbol), dump); return this; } @@ -329,13 +353,28 @@ public class CodeGen { } - // Allocate dense alias/function/call IDs within this invocation. - // Class slots let a forward reference reserve an initializer's identity. - public final LocalIds _aliases = new LocalIds(); + // These next fields all 2-way map some *global* program feature to a + // local dense index, suitable for packing in BitSets. The mapping takes a + // global value - always a {source file/class} name, and an order number + // counting up per feature in the same file. The dense local index can be + // different in different compilations. + + // The global info allows loading the same remote class info from different + // paths and aligning them. Example: Compiling A loads pre-compiled B and + // C, both of which load pre-compiled D. The 2 different D loads unify via + // this global info. + + // These mappings are all trivial identities when compiling one file; they + // only become complex when loading separately compiled code. + + // Compute local function index (FIDX) from global function info. This is + // called *in order* during parsing, and that order is part of the global + // unique mapping + public final GlobalBits _aliases = new GlobalBits(); public int alias(String clz) { return _aliases.next(clz); } // C storage has one global alias per symbol, including across object files. - public int externAlias(String name) { return _aliases.next("C:"+name,LocalIds.RESERVED); } + public int externAlias(String name) { return _aliases.next("C:"+name,GlobalBits.RESERVED); } // External data addresses supplied by an in-memory linker (image offsets). public final HashMap _externDataAddresses = new HashMap<>(); @@ -343,14 +382,14 @@ public class CodeGen { // Compute local function index (FIDX) from global function info. This is // called *in order* during parsing, and that order is part of the global // unique mapping - public final LocalIds _fidxs = new LocalIds(); + public final GlobalBits _fidxs = new GlobalBits(); // Return local index for specific global file & order. Used to find fidxs for e.g. FREF class fcns public int fidx( String clz, int order ) { return _fidxs.next(clz, order); } // New fidx in the current file public int fidx( String clz ) { return fidx(clz, -1); } // Compute local RPC index from global RPC info, one per call - public final LocalIds _rpcs = new LocalIds(); + public final GlobalBits _rpcs = new GlobalBits(); public int rpc( String clz ) { return _rpcs.next(clz); } @@ -407,7 +446,6 @@ public class CodeGen { // TFPs all have exact single fidxs and their return is wiped to BOTTOM (so // the return is not part of the match). public final Ary _linker = new Ary<>(FunNode.class); - public final Ary _calls = new Ary<>(CallNode.class); // Extern function declarations; input is the FIDX assigned to the name. final HashMap _externFunc = new HashMap<>(); @@ -423,13 +461,18 @@ 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 _encodings = new LinkedHashMap<>(); // --------------------------- // Parser object + public final Ary _calls = new Ary<>(CallNode.class); + public final Parser P; // Parse ASCII text into Sea-of-Nodes IR @@ -456,10 +499,122 @@ public class CodeGen { public CodeGen iterPostOpto() { return phase(Phase.IterPostOpto, _phase==Phase.Opto, () -> _iter.iterate(this)); } + // 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); + } + + // 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; + if( _phase.ordinal() units = new ClassInitDependencies(this).cycleImports(); + if( units.isEmpty() ) return; + for( CompUnit cu : units ) ParseAll.loadCompUnit(this,cu); + 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)); } + // Cross-phase `keep()`s belong here! We have a few nodes which we can + // lose all uses of, but later find them and want to re-add output edges. + // If we don't `keep()` them, they'll dead-code-elimnate. + + // These are mostly around adding and removal functions from other + // compilation units. E.g. a StartCU, when all his functions are exactly + // called with no escapes and no default input. Those functions will still + // go out in their own ELF, and will later hook on to the StartCU during + // code emission. Between e.g. Opto and code emission the StartCU has no + // direct users - but we're going to want the StartCU at elf-writer time! + + // The Parser and `idealize()` `keep()`s remain locally balanced. + + // We make a few collections of these cross-phase `keep()`s. + + // A few more cross-phase example lifetimes: + + // Until FinalizeIR: Opto and import loading retain StartCU's memory + // projection while unknown-caller edges disappear and may be rebuilt. + // CompUnit._start.proj(1) finds it; Opto.linkStart uses it for the memory + // Parm, found by scanning fun._outputs. FinalizeIR first holds the StartCU + // itself, then releases these projections and queues ordinary dead cleanup. + + // Until Unlink: FinalizeIR retains StartCU even if it has no users left. + // CompUnit._start is the non-graph reference used by Serialize and Unlink. + // Unlink.run/forEval install scheduling edges before releasing these holds. + // A Java reference alone does not protect a node from graph deletion. + // + // Replacement is the exception to those release points: ParseAll must + // release our old wrapper/projection holds before subsuming the wrapper. + // It registers the replacement projection for the next FinalizeIR call. + private final Ary _keptUntilFinalize = new Ary<>(Node.class); + private final Ary _keptUntilUnlink = new Ary<>(Node.class); + + void keepUntilFinalize(Node n) { keepOnce(_keptUntilFinalize,n); } + void keepUntilUnlink (Node n) { keepOnce(_keptUntilUnlink ,n); } + private static void keepOnce(Ary kept, Node n) { + if( kept.find(n)==-1 ) kept.add(n.keep()); + } + + // FinalizeIR has retained the wrappers; unused projections may now die. + void releaseFinalizedNodes() { + for( Node n : _keptUntilFinalize ) add(n.unkeep()); + _keptUntilFinalize.clear(); + } + + // Unlink has installed the scheduling edges. No optimization is needed. + void releaseUnlinkedNodes() { + for( Node n : _keptUntilUnlink ) n.unkeep(); + _keptUntilUnlink.clear(); + } + + // Only release our holds. A caller's temporary keep is a separate owner. + void releaseReplacedNode(Node n) { + releaseReplacedNode(_keptUntilFinalize,n); + releaseReplacedNode(_keptUntilUnlink,n); + } + private static void releaseReplacedNode(Ary kept, Node n) { + int idx = kept.find(n); + if( idx!=-1 ) kept.del(idx).unkeep(); + } + // 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()); @@ -475,17 +630,21 @@ public class CodeGen { // --------------------------- // TypeCheck queued surviving CLInits during its existing error walk. public CodeGen lower() { - return phase(Phase.Lower, _phase==Phase.TypeCheck, () -> _iter.iterate(this)); + return phase(Phase.Lower, (_phase==Phase.TypeCheck || _phase==Phase.Serialize), () -> _iter.iterate(this)); } // --------------------------- // Build the loop tree; break never-exit loops public CodeGen loopTree() { - return phase(Phase.LoopTree, _phase==Phase.Lower, () -> { _start.buildLoopTree(_linker,_stop); FinishCalls.run(this); }); + return phase(Phase.LoopTree, _phase==Phase.Lower, () -> _start.buildLoopTree(_linker,_stop)); } // --------------------------- - + public BAOS _serial; + final LinkedHashMap _serials = new LinkedHashMap<>(); + public void serialize() { + phase(Phase.Serialize, _phase==Phase.TypeCheck, () -> Serialize.serialize(this)); + } // --------------------------- // Code generation CPU target @@ -514,7 +673,12 @@ public class CodeGen { } // --------------------------- - + public void unlink() { + unlink(true); + } + private void unlink(boolean removeImports) { + phase(Phase.Unlink, _phase==Phase.LoopTree, () -> Unlink.run(this,removeImports)); + } // --------------------------- // Control Flow Graph in Reverse Post Order. @@ -522,7 +686,14 @@ public class CodeGen { // Global schedule (code motion) nodes public CodeGen GCM() { - return phase(Phase.Schedule, (_phase==Phase.LoopTree || _phase==Phase.Select), () -> GlobalCodeMotion.buildCFG(this)); + 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)); } // --------------------------- @@ -553,7 +724,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 @@ -561,13 +742,153 @@ 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; } + } }); } // --------------------------- + // Search a external path list, each path is recursively searched for .o + // files, which are partially loaded and searched for public symbols. + + // This is a state machine which lazily searches down the set of search + // paths until the requested module is class is found. + + // Map from external Strings to either partially read Simple ElfFile or ExternNode + public final HashMap _externSymbols = new HashMap<>(); + + // State machine elements; the outermost element is _externPaths + private int _extPathIdx; // Search index into the extern path list + private final Ary _files = new Ary<>(File.class); // Files in the current extern path being searched + private final HashSet _seenFiles = new HashSet<>(); + private int _extFileIdx; // Index into _files + + public ElfReader findExternalSimple( String name ) { + return findExternalSymbol(name) instanceof ElfReader elf ? elf : null; + } + + public ExternNode findExternal( String name ) { + return findExternalSymbol(name) instanceof ExternNode extern ? extern : null; + } + + // Search the search-path for the name; return an ElfReader if found in a + // Simple-made ELF; return an ExternNode if from another ELF, or null if + // not found. + private Object findExternalSymbol( String name ) { + // State Machine! + + while( true ) { + // Check for an immediate hit + switch( _externSymbols.get(name) ) { + + case ExternNode extern: + // Name maps to an ExternNode + return extern; + + case ElfReader elf: + return elf; + + case null: + // Name is unknown. Advance the file-system search, pulling + // out new ELF files from the search directory list and loading + // their published symbols. + + // The last directory was mined out, so get the next search + // directory and find all ELF-like files. + if( _extFileIdx >= _files._len ) { + if( _externPaths==null || _extPathIdx >= _externPaths._len ) + return null; // A true miss in the whole search path + loadExtPath(); // Load next batch file of files + break; + } + // Load and parse an ELF header + ElfReader elf = getElf(_files.at(_extFileIdx++)); + if( elf == null ) break; // Not an ELF + // Load public symbols from the ELF + elf.loadPublicSymbols(); + if( elf._strs==null ) break; // No .simple section with strings + // Put public symbol in global table; first names shadow all others + // Map from symbol string to ELFReader; most lookups + // will miss and no need to unpack ElfReader types + _externSymbols.putIfAbsent(elf._strs[1],elf); + + // 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"); + } + } + } + + // Load all the .o files in the next external path. + private void loadExtPath() { + _files.clear(); + _extFileIdx = 0; + String extpath = _externPaths.at(_extPathIdx++); + File f = new File(extpath); + if( !f.isAbsolute() ) + f = new File(_cwd+extpath); + fillExtFiles(f); + } + + // Recursive search (TODO: gzip, archives) and gather all .o files. + private void fillExtFiles(File dir) { + if( dir.isDirectory() ) + for( File f : dir.listFiles() ) + fillExtFiles(f); + else if( dir.getName().endsWith(".o") ) + 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 _elfs = new HashMap<>(); + public ElfReader getElf(File f) { + ElfReader elf = _elfs.get(f.getPath()); + if( elf != null ) + return elf; + _elfs.put(f.getPath(), elf = ElfReader.load(f,null)); + return elf; + } + + // --------------------------- public boolean _asmLittle=true; public String asm() { return asm(new SB()).toString(); } SB asm(SB sb) { diff --git a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java index c8b0a82c..8b303008 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -12,23 +12,30 @@ import java.nio.file.Path; import java.util.*; import static com.seaofnodes.simple.codegen.CodeGen.CODE; -// A source file and its class. Parent links follow the source directory tree. +// A compilation-unit, which is an external reference and source and object +// files. These are mirrored over a file system tree (so form a tree), both +// the source tree and build/object tree. public class CompUnit { public final CompUnit _par; // Parent, e.g. A/B final String _fname; // Full slashed file name starting from module root, e.g. A/B/C final public String _cname; // Full dotted class name starting from module root, e.g. A.B.C final String _name; // Base name, e.g. C + final ExternNode _ext; // Found in external libs; e.g. libc final File _smp; // Simple source file, e.g. module_root/A/B/C.smp + public final File _obj; // ELF output file, e.g. build/A/B/C.o final public String _src; // Source code, from file or test case + // Original source path from an imported diagnostic location. Does not + // affect discovery/rebuild decisions, which use _smp and _src. + public String _sourceFile; public String sourceFile() { - return _smp!=null ? _smp.getAbsolutePath() : null; + return _smp!=null ? _smp.getAbsolutePath() : _sourceFile; } public TypeStruct _clz; // The one TypeStruct being published // _deps records units required for types, code, or class references, - // without requiring their initializers to run. These source + // without requiring their initializers to run. These discovery/rebuild // dependencies may form a cycle. Ary _deps; @@ -45,17 +52,16 @@ public class CompUnit { _fname= fname; _cname= cname; _name = name; - _smp = source(fname); + _ext = null; + _smp = new File( CODE. _modDir + "/" + fname + ".smp"); + _obj = new File( CODE._buildDir + "/" + fname + ".o" ); - _src = _smp.exists() ? Files.readString(_smp.toPath()) : null; - } - - // The bundled library is ordinary source. A local sys tree can replace it; - // this chapter never loads Simple code from an object file. - static File source(String fname) { - File file=new File(CODE._modDir,fname+".smp"); - if( file.exists() || !(fname.equals("sys") || fname.startsWith("sys/")) ) return file; - return new File("src/main/smp",fname+".smp"); + boolean mustCompile = _smp.exists() && // Has source to compile + ( fname.equals(CODE._srcName) || // Explicit input is a compilation request + !_obj.exists() || // No object file + _smp.lastModified() > _obj.lastModified() || // Out-of-date with source? + !current(_obj,new HashSet<>()) ); // Out-of-date anywhere in its inputs? + _src = mustCompile ? new String(Files.readAllBytes(_smp.toPath())) : null; } // Test case. No source file. Source code passed in as a String. Fake @@ -65,11 +71,75 @@ public class CompUnit { _name = fname; _fname= fname; _cname= fname; + _ext = null; _smp = null; + _obj = null; _src = src; } - // Record source discovery without adding an initialization edge. + // External CompUnit, pulled in from an external library like libc + CompUnit( ExternNode ext, String symbol ) { + _par = null; + _name = symbol; + _fname= _name; + _cname= null; + _ext = ext; + _smp = null; + _obj = null; + _src = null; + } + + // External Simple object file, or namespace parent, found on an external search path. + CompUnit( File obj, CompUnit par, String fname, String cname, String name ) { + _par = par; + _name = name; + _fname= fname; + _cname= cname; + _ext = null; + _smp = null; + _obj = obj; + _src = null; + } + + // Check source-backed inputs before importing any saved types or IR. + // A dependency's source can be newer while its object is unchanged. + // Use a fresh visited set for each root: encountering a cycle is safe, but + // caching a provisional "current" answer from inside it would not be. + private static boolean current(File obj, HashSet visit) { + if( obj==null || !obj.isFile() ) return false; + if( !visit.add(obj.getAbsoluteFile()) ) return true; + ElfReader elf = CODE.getElf(obj); + if( elf==null ) return false; + elf.loadPublicSymbols(); + if( elf._units==null ) return false; + long time = obj.lastModified(); + for( String unit : elf._units ) { + // Never import another copy of a unit explicitly being compiled. + CompUnit cu = CODE._compunits.get(unit); + if( unit.equals(CODE._srcName) || (cu!=null && cu._src!=null) ) return false; + File src = new File(CODE._modDir+"/"+unit+".smp"); + if( !src.isFile() || src.lastModified()>time ) return false; + } + for( String dep : elf._deps ) { + if( Arrays.asList(elf._units).contains(dep) ) continue; // Owned by this object. + File file = dependencyObj(dep,true); + if( file==null || !file.isFile() || file.lastModified()>time ) return false; + // Object-only libraries are supplied as a coherent build. Their + // input versions cannot be inferred from installation timestamps. + if( file.equals(new File(CODE._buildDir+"/"+dep+".o")) && !current(file,visit) ) return false; + } + return true; + } + + // Resolve dependencies the same way for freshness checks and actual loads. + static File dependencyObj(String fname, boolean local) { + File obj = new File(CODE._buildDir+"/"+fname+".o"); + if( local && (obj.isFile() || new File(CODE._modDir+"/"+fname+".smp").isFile()) ) return obj; + ElfReader elf = CODE.findExternalSimple(Parser.addClzPrefix(fname.replace('/','.'))); + return elf==null ? null : elf._file; + } + + // Add a discovered dependency, for later writing out in an ELF file, ".simple" section void addDep(CompUnit dep) { if( _deps == null ) _deps = new Ary<>(CompUnit.class); _deps.add(dep); @@ -91,7 +161,9 @@ public class CompUnit { @Override public String toString() { String x = "{"+_cname; if( _smp!=null && _smp.exists()) x += ",hasSMP"; + if( _obj!=null && _obj.exists()) x += ",hasObj"; if( _src!=null ) x += ",hasSrc"; + if( _ext != null ) x += ",isExt"; x += "}"; return x; } diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java new file mode 100644 index 00000000..1f0e803d --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java @@ -0,0 +1,244 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeMemPtr; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; +import com.seaofnodes.simple.util.Utils; +import java.io.*; +import java.nio.file.Files; +import java.util.HashMap; + +public class ElfReader { + + public final File _file; + public final byte[] _buf; + int _x; // Cursor into buffer + // ELF Header + public final ElfHeader _header; + // All sections + public final Section[] _sections; + // Simple section, if available + public final Section _simple; + // Byte array in/out stream - used as a reader + public final BAOS _bais; + // Compilation unit; written into FunNodes + public final CompUnit _compunit; + + // Strings from the Simple section, either small public set or whole set + public String[] _strs; + // Dependent file names + public String[] _deps; + // Compilation units defined by this object, independent of init analysis. + public String[] _units; + // Only published symbol this file + public TypeStruct _clz; + // Canonical named types, distinct from optimized same-named graph states. + public TypeStruct[] _pubTypes; + // Nodes read in this Elf + public Ary _nodes; + Serialize.TypeRead _types; + FunctionSummary[] _functions; + + // Load an Elf file (mostly lazily) + public static ElfReader load( File f, CompUnit cu ) { + try { return new ElfReader(f,cu); } + catch( IOException ioe ) { return null; } + } + + // Load the Simple section from the ELF file + private ElfReader( File f, CompUnit cu ) throws IOException { + _file = f; + _compunit = cu; + _buf = Files.readAllBytes(f.toPath()); + _header = new ElfHeader(); + // No attempt is made to parse the program header table. + _sections = new Section[_header._shnum]; + for( int i=0; i<_header._shnum; i++ ) + _sections[i] = new Section(i); + + // Load section names + Section secstr = _sections[_header._shstrndx]; + for( Section sec : _sections ) + if( sec._type != 0 ) + sec._name = secstr.str(sec._noff); + + Section simple = null; + for( Section sec : _sections ) + if( ".simple".equals(sec._name) ) + simple = sec; + _simple = simple; + _bais = _simple==null ? null : new BAOS(_buf, (int)_simple._offset); + } + + // For Serialize self-test + ElfReader( BAOS bais ) { + _file = null; + _compunit = null; + _buf = bais.buf(); + _header = null; + _sections = null; + _simple = null; + _bais = bais; + } + + // Load the public symbols and dependent objs, but not the whole IR + void loadPublicSymbols() { + // Check already loaded and cached + if( _strs == null && _simple != null ) + // Read only the published public strings, for speed purposes when + // scanning a large count of ELF files but getting hits in only a + // few of them. i.e. optimizing (prematurely?) for the traditional + // case of linking a small file against a large library + 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); + return _clz; + } + + // Loads strings, mappings, and types, but not Nodes. Used after the + // public-string scan finds a matching Simple ELF, so parsing can resolve + // imported field/array aliases before the full graph is linked in later. + public TypeStruct loadPublicTypes(CodeGen code) { + Serialize.readTypes(code, this, code._aliases, code._fidxs, code._rpcs); + return _clz; + } + + int u1() { return _buf[_x++]&0xFF; } + int magic() { // Big endian + return (u1() << 24) | (u1() << 16) | (u1() << 8) | u1(); + } + int u2() { return u1() | (u1()<<8); } // Little endian + int u4() { // Little endian + return u1() | (u1() << 8) | (u1() << 16) | (u1() << 24); + } + long u8() { return u4() | ((long)u4()<<32); } + void skip(int skip) { _x += skip; } + + + public class ElfHeader { + final int _magic; + final boolean _format32; // Format32 or format64 + final byte _osabi; + final boolean _little; // True if little endian, false if big endian + final char _type; + final char _machine; + final long _entry; // Process entry point + final long _phoff; // Program header table offset, from file start + final long _shoff; // Section header table offset, from file start + final int _flags; // Flags + final int _phnum; // Number of program header entries + final int _shentsize; + final int _shnum; // Number of section header entries + final int _shstrndx; // Section header index contains section names + + + ElfHeader() throws IOException { + _x = 0; + if( (_magic = magic()) != 0x7F454C46 ) bad("magic number",_magic); + byte EI_CLASS = (byte)u1(); + if( EI_CLASS != 1 && EI_CLASS != 2 ) bad("EI_CLASS",EI_CLASS); + _format32 = (EI_CLASS==1); + byte EI_DATA = (byte)u1(); + if( EI_DATA != 1 && EI_DATA != 2 ) bad("EI_DATA",EI_DATA); + _little = EI_DATA == 1; + if( u1() != 1 ) bad("version",1); + if( (_osabi=(byte)u1()) != 0 ) bad("EI_VERSION",_osabi); + byte abiversion = (byte)u1(); + if( abiversion != 0 ) bad("EI_ABIVERSION",abiversion); + skip(7); // Pad + + // Endian matters now + if( !_little ) throw new IOException("TODO: Big endian"); + if( (_type = (char)u2()) != 1 ) bad("ET_REL",_type); + if( (_machine = (char)u2()) != 0x3E ) bad("AMD x86-64",_machine); + int ver = u4(); + if( ver != 1 ) bad("Version",ver); + // Format32 matters now + if( _format32 ) bad("Format",1); + _entry = u8(); // Process entry point + _phoff = u8(); // Program header table offset + _shoff = u8(); // Section header table offset + _flags = u4(); // Flags + int ehsize = u2(); + if( ehsize != 0x40 ) bad("EHSIZE",ehsize); + int phentsize = u2(); + if( phentsize != 0x38 && phentsize != 0 ) bad("PHENTSIZE",phentsize); + _phnum = u2(); + _shentsize = u2(); + if( _shentsize != 0x40 ) bad("SHENTSIZE",_shentsize); + _shnum = u2(); + // String section + _shstrndx = u2(); + assert _x == ehsize; + } + } + + public class Section { + final int _noff; // Offset in string section for name + final int _type; // Section type + final long _flags; + final long _addr; // Offset in virtual mem, if loaded + final long _offset; // Offset in file + final long _size; // Size in bytes + final int _link; // Associated section index, varies + final int _info; // Varies + final byte _align; // Log2 alignment + final int _esize; // Element size, if non-zero + String _name; + + Section(int sidx) throws IOException { + _x = (int)(_header._shoff + (sidx * _header._shentsize)); + _noff = u4(); + _type = u4(); + _flags = u8(); + _addr = u8(); + _offset= u8(); + _size = u8(); + _link = u4(); + _info = u4(); + long align = u8(); + if( align==0 ) align=1; + _align = (byte)Long.numberOfTrailingZeros(align); + if( (1L << _align ) != align ) + throw new IOException("Bad section alignment: "+align); + _esize = (int)u8(); + } + + String str(int off) { + assert _type == 3/*SHT_STRTAB*/; // String table section header + int start = (int)(_offset+off); + int x = start; + while( _buf[x++] !=0 ) ; + return new String(_buf,start,x-start-1); + } + } + + private static void bad(String msg, int val) throws IOException { + throw new IOException("Bad "+msg+": "+val); + } + + + + //public TypeMemPtr lookup( String name ) { + // if( _simple == null ) return null; + // BAOS baos = new BAOS(_buf, (int)_simple._offset); + // Ary strs = Serialize.read_strs(baos); + // + // + // + // Ary nodes = Serialize.read_types(baos); + // + // throw Utils.TODO("Elf load symbol "+name); + //} +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java index c52209dd..fcf5c287 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -27,6 +27,7 @@ public class ElfWriter { static final int SHT_SYMTAB = 2; static final int SHT_STRTAB = 3; static final int SHT_RELA = 4; + static final int SHT_SIMPLE = 10; // Simple section final String _name; final int _type, _entsize, _index, _name_pos, _flags; @@ -192,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. @@ -216,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) ) @@ -275,6 +277,9 @@ public class ElfWriter { public static final int SECTION_HDR_SIZE = 64; // ------------------------------------------------------------------------ + public class SimpleSection extends DataSection { + SimpleSection(BAOS serial) { super(".simple", SHT_SIMPLE, serial, 0); } + } // ------------------------------------------------------------------------ @@ -300,6 +305,8 @@ public class ElfWriter { } public ElfWriter export(boolean emitEntrySymbol) { + if( _code._serial==null ) + throw new IllegalStateException("ELF export needs ideal IR: request Export from the driver, or Serialize before Lower"); // Sections are created in the order they are emitted. _sections = new Ary<>(Section.class); @@ -311,7 +318,7 @@ public class ElfWriter { _strtab = new StringSection(); // place all the symbols - int nlocals = 1/*null*/+9/*number of sections*/; + int nlocals = 1/*null*/+9/*number of sections*/+1/*Simple section*/; SymbolSection symbols = new SymbolSection(nlocals); // we've already constructed these entire sections in the encoding phase @@ -362,7 +369,7 @@ public class ElfWriter { // anonymous functions which have no source-level exported name. HashMap 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)); } @@ -392,6 +399,7 @@ public class ElfWriter { } // Create a "Simple" section for Simple types and ir + SimpleSection simple = new SimpleSection(_code._serial); // Write the local section header symbols assert nlocals == 1+_sections._len; @@ -439,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/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 06bf14f5..067f431a 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/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/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java index 923486c6..69e0104d 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java +++ b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java @@ -31,10 +31,10 @@ abstract class FinalizeIR { } code.keepInCompUnit(fun); } - for( CompUnit cu : code._compunits.values() ) { - ProjNode mem = cu._start.proj(1); - if( mem != null ) code.add(mem.unkeep()); - } + // Hand off the wrapper lifetime before releasing its memory projection. + for( CompUnit cu : code._compunits.values() ) + code.keepUntilUnlink(cu._start); + code.releaseFinalizedNodes(); // Stable print order: initializers first, then other Returns by NID. for( Node stop : code._stop._inputs ) Arrays.sort(stop._inputs._es,0,stop.nIns(), diff --git a/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java b/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java deleted file mode 100644 index 7ba696d3..00000000 --- a/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java +++ /dev/null @@ -1,57 +0,0 @@ -package com.seaofnodes.simple.codegen; - -import com.seaofnodes.simple.node.*; - -// Detach analysis call edges after building the loop tree. Every live body -// belongs to this invocation; preserve it for scheduling and emission. -abstract class FinishCalls { - - - static void run(CodeGen code) { - - // The remaining passes assume all calls are unlinked; i.e. we are throwing - // away the Call Graph here. Functions only reachable from internal calls - // need to be re-hooked to stop/start less they go dead. - for( FunNode fun : code._linker ) { - // Already linked to start, not going dead - if( fun==null || fun.isDead() ) - continue; - - // Insert the post-Opto code-generation hook. Unlike an Opto-time - // Start input, this no longer carries unknown-caller semantics. - ReturnNode ret = fun.ret(); - StartNode start = fun._compunit._start; - assert start!=null; - if( fun.nIns() <= 1 || fun.in(1) != start ) { - fun.insertDef(1,start); - for( Node use : fun._outputs ) - if( use instanceof ParmNode parm ) - parm.insertDef(1,ConstantNode.raw(parm._type)); - if( fun._compunit._stop._inputs.find(ret) == -1 ) - fun._compunit._stop.addDef(ret); - } - // Unlink from Call - for( int i=2; i { - if( n instanceof CallEndNode cend ) - for( int i=1; i _clzOrder2Local = new HashMap<>(); + private final Ary _local2Clz = new Ary<>(String.class); + private final AryInt _local2Order = new AryInt(); + // Local dense index + private int _local; + + GlobalBits() { + _local = RESERVED; + // Reserved null-class bits are global identities and are never + // remapped. + int[] xs = new int[RESERVED]; + xs[0] = RESERVED; // Per-class next order counter + for( int i=0; i 0 ) xs[i] = i; + _local2Clz .setX(i,null); + _local2Order.setX(i,i); + } + _clzOrder2Local.put(null,xs); + } + + // Get a next local index for this clz + int next( String clz ) { return next(clz,-1); } + + // Given a clz and order, return an existing local index or make a new + // mapping and return that. + int next(String clz, int order ) { + // Get the per-clz Order->Local mapping + int[] xs = _clzOrder2Local.get(clz); + if( xs == null ) + xs = new int[]{RESERVED,1}; // Make, if it does not exist + // Caller does not have an order in mind, just take the next one stored + // in xs[0] + if( order == -1 ) + order = xs[0]++; + // Order exists from prior compilation, but not recorded locally + else if( order >= xs[0] ) + xs[0] = order+1; + // Grow as needed + while( xs.length <= order ) + xs = Arrays.copyOf(xs,xs.length*2); + // Have a local mapping already? + if( xs[order] != 0 ) + return xs[order]; + int local = _local++; + bind(local,clz,order); + return local; // The dense local index + } + + // Bind a specific dense local index to {clz,order}. Used by both fresh + // allocation and deserialization, where local indexes must not compact + // across holes because XInt bitsets are serialized against this space. + private void bind( int local, String clz, int order ) { + if( _local <= local ) + _local = local+1; + _local2Clz .setX(local,clz ); + _local2Order.setX(local,order); + + // Inline-only fidx holes are represented as {null,0}. They need the + // reverse mapping above, but no forward map because xs[0] is the + // per-class next-order counter. + if( clz==null && order==0 ) + return; + + int[] xs = _clzOrder2Local.get(clz); + if( xs == null ) + xs = new int[]{RESERVED,1}; + if( order >= xs[0] ) + xs[0] = order+1; + while( xs.length <= order ) + xs = Arrays.copyOf(xs,xs.length*2); + _clzOrder2Local.put(clz,xs); + xs[order] = local; + } + + // A file-local function that will inline, and never write to disk + public int nextInline( ) { + int local = _local++; + _local2Clz .setX(local,null); + _local2Order.setX(local,0); + return local; + } + // Get a next local index for the same clz as this old index + public int next( int old ) { return next(_local2Clz.at(old)); } + + // Map a file-local dense index to this compilation unit's local dense index. + public int map( GlobalBits fileBits, int fileLocal ) { + if( fileLocal >= fileBits._local2Clz.size() ) + throw new ArrayIndexOutOfBoundsException(""+fileLocal+" >= "+fileBits._local2Clz.size()); + return findOrNext(fileBits._local2Clz.at(fileLocal), fileBits._local2Order.at(fileLocal)); + } + + // Map a global {clz,order} to a local one; keep any existing mapping or + // make a new one as needed. + private int findOrNext(String clz, int order ) { + // Reserved null-class identities are not represented in xs[order], + // because xs[0] is the next-order counter. + if( clz==null && order < _local2Clz.size() && _local2Order.at(order)==order && _local2Clz.at(order)==null ) + return order; + int[] xs = _clzOrder2Local.get(clz); + if( xs != null && order < xs.length ) { + int local = xs[order]; + if( local < _local2Clz.size() && _local2Order.at(local)==order && Objects.equals(_local2Clz.at(local),clz) ) + return local; + } + return next(clz,order); + } + + // Stable native symbol identity, independent of this compilation's dense IDs. + String owner(int local) { return _local2Clz.at(local); } + String symbol(int local) { + return _local2Clz.at(local)+"$F$"+_local2Order.at(local); + } + + // Write out to BAOS enough bits to unwind the local back to global index + void packed( BAOS baos, HashMap strs ) { + // Unwind a local index to the clz. + baos.packed2(_local2Clz.size()); + for( int i=RESERVED; i<_local2Clz.size(); i++ ) { + String clz = _local2Clz.at(i); + baos.packed2(clz==null ? 0 : strs.get(clz)); + baos.packed2( _local2Order.at(i) ); + } + } + + void gather( HashMap strs ) { + for( int i=RESERVED; i<_local2Clz.size(); i++ ) + Serialize.gather(strs,_local2Clz.at(i)); + } + + // Read in the BAIS bits needed to make a file-local -> global mapping + static GlobalBits packed( BAOS bais, String[] strs ) { + var gb = new GlobalBits(); + int n = bais.packed2(); + for( int i=RESERVED; i 0 ) sb.p(','); + sb.p(i).p(" <-> ").p(_local2Clz.at(i)).p('#').p(_local2Order.at(i)); + } + return sb.p(']').toString(); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 4477025b..42999894 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/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 forEval(CodeGen code, StartNode start, StopNode stop) { + Ary funs = Unlink.forEval(code,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 buildCFG(CodeGen code, StartNode start, StopNode stop) { Ary 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 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); + 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 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 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 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 new InstSelect(code).run(cpu,callingConv,base)); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/src/main/java/com/seaofnodes/simple/codegen/Iter.java index 1ffd9737..1ce5b051 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -2,16 +2,22 @@ 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. Later Iter runs +// 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) { - // Close parser-in-progress states. Seed a fresh pessimistic solve; - // exposure sets start at FULL and can only shrink during Iter. + // The phase shift closes all parser-in-progress states and freezes + // unknown external inputs. Imported nodes carry post-Opto escape + // precision, but Iter is a fresh pessimistic solve: memory escape + // summaries must restart at FULL so newly discovered private escapes + // can only be removed, never added. Seed the complete graph once. + boolean hasImports = code._externPaths != null; code._start.walk(n -> { - if( !(n instanceof ConstantNode) ) - 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; }); @@ -34,5 +40,59 @@ abstract class Iter { return t; } + private static Type iterImportReset(Type t) { + if( t.isHigh() ) + return t.dual(); + if( t instanceof TypeMem mem ) + return TypeMem.make(mem._alias,iterImportReset(mem._t),mem._one,mem._clz,mem._final,XInt.FULL,XInt.FULL); + if( t instanceof TypeMemPtr ) + return t.makeStorage(); + if( t instanceof TypeStruct ) + return t.makeStorage(); + if( t instanceof TypeTuple tt ) { + TypeTuple rez = tt; + for( int i=0; i 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/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java index b6b3a22c..3b1d3182 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java +++ b/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 cfgs) { XS.clear(); - for( CFGNode bb : code._cfg ) + for( CFGNode bb : cfgs ) if( bb.blockHead() ) local(bb,false); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java b/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java deleted file mode 100644 index 462248dd..00000000 --- a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java +++ /dev/null @@ -1,33 +0,0 @@ -package com.seaofnodes.simple.codegen; - -import java.util.HashMap; -import java.util.Arrays; - -// Dense IDs for this invocation. A class slot can be reserved before its file -// is parsed; every later reference to that slot gets the same ID. -public class LocalIds { - public static final int RESERVED=2; - private int _next=RESERVED; - private final com.seaofnodes.simple.util.Ary _owners=new com.seaofnodes.simple.util.Ary<>(String.class); - private final HashMap _slots=new HashMap<>(); - - public int next(String owner) { return next(owner,-1); } - public int next(String owner, int slot) { - int[] ids=_slots.get(owner); - if( ids==null ) ids=new int[]{RESERVED,1}; - if( slot==-1 ) slot=ids[0]++; - else if( slot>=ids[0] ) ids[0]=slot+1; - if( slot>=ids.length ) ids=Arrays.copyOf(ids,Math.max(slot+1,ids.length*2)); - if( ids[slot]==0 ) { ids[slot]=_next++; _owners.setX(ids[slot],owner); } - _slots.put(owner,ids); - return ids[slot]; - } - public String owner(int id) { return _owners.atX(id); } - public String symbol(int id) { return owner(id)+".$fun"+id; } - public int nextInline() { return _next++; } - public int next(int old) { - int id=_next++; - _owners.setX(id,owner(old)); - return id; - } -} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Module.java b/src/main/java/com/seaofnodes/simple/codegen/Module.java new file mode 100644 index 00000000..a5d85dbc --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Module.java @@ -0,0 +1,98 @@ +package com.seaofnodes.simple.codegen; + + +/*** + Modules!?!?!? + + Goal: under no circumstances can you load from an uninitialized variable + (although you can see default inits for fields that have defaults). + Goal: nested tree-structured name spaces, to control complexity. + Goal: field decl order within a file is fairly flexible. + + A Module a root-level SMP file, and the full file path must be provided on + the command line. All other Simple structs are relative to this file. + + Example: "simple /user/Dave/hello.smp" + + Defines a module "hello" in directory "/user/Dave", compiles and produces + a `hello` or `hello.exe` output file, and runs it. + + A SMP file has some file-init code which is static-global. + This code is executed on "first touch" of the file (defined below). + + Example: hello.smp contains: + sys.io.p("Hello World!"); + On first-touch, will print "Hello World!". + + A SMP file is a lexical scope, and code inside it can reference those names. + + Example: hello.smp contains: + val greet = "Hello World!"; // Declare file-scoped variable + sys.io.p(greet); // Reference file-scoped variable + + Static code is NOT allowed to have forward-references AND be executed + before the finishes initializing all variables. After var + initialization, a singleton instance of the implied file struct is made, + and then code can call anything. + + Example: + sys.io.p(greet); // Illegal forward reference + val greet = "Oops!"; + + Example: + val delay = { -> greet }; // Legal forward ref, but cannot execute (yet) + val greet = "Hello World!"; // Ref is resolved + sys.io.p(delay()); // Allowed to call delay() + val nprimes = { N -> + // compute number of primes < N + } + // Can otherwise execute any code in a + sys.io.p(nprimes(100)); + + Inside a directory, you can have sibling SMP files: + File hello.smp contains: + sys.io.p(I9A.GREETING); // File hello references sibling file I9A static globals + File I9A.smp contains: + val GREETING = translate("Hello World!"); + val translate = { str msg -> ... }; + + code cannot reference sibling files (nor child files, see below) + until all static variables are initialized. This prevents cyclic + initialization bugs, where file A uses vars from file B and vice-versa. + + File Chicken.smp contains: + val lay = Egg.hatch; // Illegal, defining var 'lay' after calling sibling Egg + File Egg.smp contains: + val hatch = Chicken.lay; // Illegal + + You can make cross references, if they get delayed until after all fields + are declared. + + File Chicken.smp contains: + int lay = 2; + lay = Egg.egg; + + File Egg.smp contains: + int egg = 3; + egg = Chicken.lay; + + The problem here, of course, is that you need to touch one of Chicken or + Egg first. + + + Inside a SMP file, you can define structs; structs are also a lexical + scope. Bare code in the struct is part of the struct's and only + runs when an instance is created. Structs do not have static (nor + ). Structs cannot have any forward references, and locally + declared functions cannot have both forward references and be executed (or + passed along to a possibly-executing function). + + In the same directory as a SMP file, Simple allows other directories with + names matching SMP files. Inside these dirs can be more SMP files that are + lexically nested, similar to embedded structs. + + +*/ + +public abstract class Module { +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 4db277df..440ffabb 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -56,28 +56,22 @@ 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 + // CodeGen owns these until FinalizeIR; linkStart may need them again. for( CompUnit cu : code._compunits.values() ) { ProjNode mem = cu._start.proj(1); - if( mem!=null ) mem.keep(); + if( mem!=null ) code.keepUntilFinalize(mem); } - // Iterate the Stop-of-Stops + // Iterate all functions. + // TODO: use CodeGen _link list for( Node stop : code._stop._inputs ) { for( int i=0; i= 0 ) { + String head = name.substring(0,idx); + CompUnit sub = makeCUnit(code,par,head,external ? externalObj(code,par,head) : null,external); + return makeCUnit(code,sub,name.substring(idx+1).intern(),obj,external); + } + + String fname = par==null ? name : (par._fname + "/" + name).intern(); + CompUnit cunit = code._compunits.get(fname); + if( cunit != null ) return cunit; + String cname = par==null ? name : (par._cname + "." + name).intern(); + code._compunits.put(fname, cunit = external ? new CompUnit(obj,par,fname,cname,name) : new CompUnit(par,fname,cname,name)); + return cunit; + } // Parse a top-level string, used for e.g. testing static void parseSource( CodeGen code, String src ) { @@ -69,22 +82,29 @@ public abstract class ParseAll { } private static void enqueue(CompUnit cu) { - if( cu._par!=null ) enqueue(cu._par); + if( cu._par!=null && (cu._par._src!=null || (cu._par._obj!=null && cu._par._obj.exists())) ) enqueue(cu._par); if( cu._start==null && WORK.find(cu)==-1 ) WORK.add(cu); } private static void parseAll(CodeGen code, CompUnit cunit) { WORK.clear(); // Cleanup from prior tests + NEEDS_LOAD.clear(); // Prime the pump with the first CompUnit enqueue(cunit); // Work through all unparsed compilation units and parse while( !WORK.isEmpty() ) { CompUnit cu = WORK.remove(0); - if( cu._src==null ) - throw new RuntimeException("Missing source file '"+cu._fname+".smp'"); - parseOne(code,cu); + // No source code? Means we do not need to parse, but instead need to load the symbols as-if we parsed + if( cu._src==null || cu._src.isEmpty() ) + loadDeps(code,cu); // Load recursive dependents + else + parseOne( code, cu ); // Parse } + // Load all pre-compiled CompUnits + for( CompUnit cu : NEEDS_LOAD ) + loadSummaries(code,cu); + // Many types will have been declared cyclically either internally or // across multiple compilation units. @@ -97,7 +117,8 @@ public abstract class ParseAll { for( TypeStruct ts : tss ) Parser.TYPES.put(ts._name,ts); for( CompUnit cu : code._compunits.values() ) - cu._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cu._cname)); + if( cu._ext==null ) + cu._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cu._cname)); // Walk over all Nodes, and upgrade the internal constants to the // closed-over types. @@ -135,6 +156,9 @@ public abstract class ParseAll { // Adds sort by NIDs, which just got shuffled if( n instanceof AddNode add ) code.add(add); + // All imported bodies are loaded; link them before Iter checks types. + if( n instanceof CallNode call && !NEEDS_LOAD.isEmpty() ) + code.add(call).idealize(); return null; } ); @@ -157,6 +181,8 @@ public abstract class ParseAll { // Search the module for the fref try { CompUnit xcunit = findCUnitModule(code,cunit,fref._name); + if( xcunit == null ) + xcunit = findCUnitExternalSimple(code,fref._name); if( xcunit != null ) { // Replace the FRef with the discovered class name. fref._name = Parser.addClzPrefix(xcunit._cname); @@ -196,9 +222,126 @@ public abstract class ParseAll { if( xcunit != null ) return xcunit; } - return null; + return findCUnitExternalSimple(code,typeName); } + // Load the public symbols for this CompUnit, and add dependent CompUnits to the NEEDS_LOAD list. + private static void loadDeps(CodeGen code, CompUnit cunit) { + // Load IR after parsing + if( NEEDS_LOAD.find(cunit) != -1 ) + return; // Already on the to-be-loaded list? + for( CompUnit loaded : NEEDS_LOAD ) + if( loaded._obj.equals(cunit._obj) ) return; // Another class in the same object. + try { + NEEDS_LOAD.add(cunit); + // Load dependent classes + ElfReader elf = code.getElf(cunit._obj); + elf.loadPublicSymbols(); + // Register bundled definitions before resolving dependencies or IR. + for( String fname : elf._units ) + makeCUnit(code,null,fname,cunit._obj); + for( String fname : elf._deps ) { + // Check CompUnit for being up to date + CompUnit sub = code._compunits.get(fname); + if( sub==null ) sub=makeCUnit(code,null,fname,depObj(code,cunit,fname)); + // If not seen before or out of date, parse the new nested cunit + if( sub._clz == null && WORK.find(sub)==-1 && NEEDS_LOAD.find(sub)==-1 ) + enqueue(sub); + } + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + } + + private static File depObj(CodeGen code, CompUnit cunit, String fname) { + File obj = CompUnit.dependencyObj(fname,cunit._smp!=null); + if( obj == null ) + throw new RuntimeException("Cannot find Simple dependency '"+fname+"'"); + return cunit._smp!=null && obj.equals(new File(code._buildDir+"/"+fname+".o")) ? null : obj; + } + + private static File externalObj(CodeGen code, CompUnit par, String name) { + String cname = par==null ? name : par._cname + "." + name; + ElfReader elf = code.findExternalSimple(Parser.addClzPrefix(cname)); + return elf == null ? null : elf._file; + } + + 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 = 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 ) code.releaseReplacedNode(oldMem); + elf.loadSimple(code); + cunit._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cunit._cname)); + StartNode lstart = (StartNode)elf._nodes.at(0); + StopNode lstop = ( StopNode)elf._nodes.last(); + + // Add all new loaded functions to the linker table + for( Node n : lstop._inputs ) { + StopCUNode stop = (StopCUNode)n; + StartCUNode start = stop.start(); + CompUnit cu = code._compunits.get(start._fname); + cu._start = start; + cu._stop = stop ; + + 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 _pubTypes = new HashSet<>(); + private final HashMap> _classes = new HashMap<>(); + + private Serialize(CodeGen code) { + _init = new ClassInitDependencies(code); + // Preserve the canonical declarations, distinct from sharper graph + // types with the same names. Gather/sort them once for all objects. + TreeMap named = new TreeMap<>(); + for( Type type : Parser.TYPES.values() ) + if( type instanceof TypeStruct ts ) named.put(ts._name,ts); + for( TypeStruct ts : named.values() ) { + _pubTypes.add(ts); + CompUnit cu = classOwner(code,ts); + if( cu!=null && cu._src!=null ) + _classes.computeIfAbsent(cu,k -> new Ary<>(TypeStruct.class)).add(ts); + } + } + + // Encoding/emulation need only machine code. File export also needs ideal + // IR for a later compiler to import; an explicit Serialize request stops here. + static void forTarget(CodeGen code, CodeGen.Phase target, boolean inMemory) { + if( target==CodeGen.Phase.Serialize || (target.ordinal()>=CodeGen.Phase.Export.ordinal() && !inMemory) ) + code.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 units = new ArrayList<>(code._compunits.values()); + units.sort(Comparator.comparing(cu -> cu._fname)); + Serialize writer = new Serialize(code); + for( CompUnit cu : units ) { + if( cu._src==null ) continue; + BAOS serial = writer.serialize(code,cu); + code._serials.put(cu,serial); + if( cu._fname.equals(code._srcName==null ? "Test" : code._srcName) ) code._serial=serial; + } + } + + private BAOS serialize(CodeGen code, CompUnit top) { + Ary nodes = nodeOrder(code,top); + HashSet xdeps = new HashSet<>(); + // 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); + String[] units = {top._fname}; + TypeStruct clz = top._clz; + + // Compress into bytes + Ary classes = _classes.get(top); + BAOS baos = write(nodes, clz, classes, deps, units, code._aliases, code._fidxs, code._rpcs, code._externFunc); + + // --- Expensive bijection assert + if( false ) { + // Inflate into POJOs; renumbers everything + ElfReader elf = new ElfReader(new BAOS(baos.toByteArray())); + readAll(code,elf, code._aliases, code._fidxs, code._rpcs); + BAOS baos2 = write(elf._nodes,elf._clz,classes,elf._deps,elf._units, code._aliases, code._fidxs, code._rpcs, code._externFunc); + + // Bi-jection + for( int i=0; iglobal bit mappings. + aliases.gather(strs); + fidxs .gather(strs); + rpcs .gather(strs); + for( String extern : externFunc.values() ) + gather(strs,extern); + // Count strings from nodes + for( Node n : nodes ) + n.gather(strs); + // Radix sort by string ID# + String[] astrs = new String[strs.size()]; + for( String s : strs.keySet() ) + astrs[strs.get(s)] = s; + + // Check that published strings and types align + assert astrs[1] == ((TypeStruct)atypes[1])._name; + if( depobjs != null ) + for( int i=0; iglobal mappings + aliases.packed(baos,strs); + fidxs .packed(baos,strs); + rpcs .packed(baos,strs); + ArrayList externFidxs = new ArrayList<>(externFunc.keySet()); + Collections.sort(externFidxs); + baos.packed2(externFidxs.size()); + for( int fidx : externFidxs ) { + baos.packed2(fidx); + baos.packed2(strs.get(externFunc.get(fidx))); + } + + // C - Write unique Types + baos.packed4(atypes.length); + baos.packed2(writtenPubs._len); + for( TypeStruct ts : writtenPubs ) + baos.packed4(types.get(ts)); + // Write Types in ID# order, no children + for( Type t : atypes ) + t.packed(baos,strs); + // Write Types in ID# order, only child IDs + for( Type t : atypes ) { + int nkids = t.nkids(); + for( int i=0; i nodes) { + if( n instanceof ParmNode parm ) n=parm.fun(); + if( (n instanceof FunNode || n instanceof CallEndNode) && i>0 ) + return nodes.containsKey(n.in(i)); + if( n instanceof StopNode ) return nodes.containsKey(n.in(i)); + return true; + } + + public static int nIns(Node n, IdentityHashMap nodes) { + int len=0; + for( int i=0; i void gather( HashMap strs, T s) { + if( s!=null && !strs.containsKey(s) ) + strs.put(s,strs.size()); + } + public static void gather( AryInt is, int s) { + if( is.atX(s)==0 ) { + int cnt=0; + for( int i=1; iglobal mappings. Further down we will map + // Elf file-local -> global, then global -> CodeGen.CODE local + GlobalBits fileAliases = GlobalBits.packed(bais,strs); + GlobalBits fileFidxs = GlobalBits.packed(bais,strs); + GlobalBits fileRpcs = GlobalBits.packed(bais,strs); + int nexterns = bais.packed2(); + for( int i=0; i nodes = new Ary<>(Node.class); + CompUnit cu = null; + for( int i = 0; 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); + } + } + // 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); + + // 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 + private static boolean check( CodeGen code, Ary nodes ) { + // Loaded nodes are complete, unlike nodes still being built by the + // parser. Recompute them with post-parse semantics. The compilation- + // unit Stop is the exception: its escape type depends on the complete + // program's public interface, which ParseAll freezes only after every + // compilation unit has been loaded. + boolean good = true; + CodeGen.Phase phase = code._phase; + code._phase = CodeGen.Phase.Opto; + try { + for( Node n : nodes ) { + if( n instanceof StopCUNode && !code.publicInterfaceFrozen() ) + continue; + // Cross-object calls are relinked only after every body has + // loaded. Their saved return types cannot be recomputed yet. + if( n instanceof CallEndNode end && end.call().fptr()._type instanceof TypeFunPtr fp && + end.nIns()<=fp.nfcns() ) continue; + Type nval = n.compute(); + if( nval != n._type ) { + System.err.println("Node "+n+" read in as "+n._type+" but computes as "+nval); + good = false; + } + } + } finally { + code._phase = phase; + } + return good; + } + + // -------------------------------------------------- + public static Ary nodeOrder( CodeGen code, CompUnit cu ) { + BitSet visit = code.visit(); + Ary nodes = new Ary<>(Node.class); + visit.set(code._stop._nid); + // FinalizeIR attached every surviving function to its unit's Stop. + for( Node ret : cu._stop._inputs ) + _funWalk(((ReturnNode)ret).fun(),nodes,visit); + + // Gather constants and shared expressions through this unit's inputs. + // Walking their users instead would search other units and miss new + // kinds of shared expressions unless we special-cased each one. + Ary cons = new Ary<>(Node.class); + cons.add(code._start); + visit.set(code._start._nid); + visit.set(cu._start._nid); + for( Node n : cu._start._outputs ) + if( n instanceof ProjNode ) visit.set(n._nid); + for( Node n : nodes ) + for( int i = 0; i0 && !visit.get(parm.fun().in(i)._nid) ) continue; + constantInputs(n.in(i),cons,visit); + } + // StartCU and memory projection + cons.add(cu._start); + for( Node n : cu._start._outputs ) + if( n instanceof ProjNode ) cons.add(n); + // All the innards of functions + cons.addAll(nodes); + // StopCU, Stop + cons.add(cu._stop); + cons.add(code._stop); + visit.clear(); + return cons; + } + + private static void constantInputs(Node n, Ary cons, BitSet visit) { + if( n==null || visit.get(n._nid) ) return; + // Call graph edges lead to other functions, not shared values. + if( n instanceof CFGNode && !n.isConst() ) return; + visit.set(n._nid); + cons.add(n); + // A FunPtr's Return edge must not pull in the callee's body. + if( !n.isConst() ) + for( Node def : n._inputs ) constantInputs(def,cons,visit); + } + + // -------------------------------------------------- + public static Ary nodeOrder( CodeGen code ) { + Ary nodes = new Ary<>(Node.class); + BitSet visit = code.visit(); + nodes.add(code._start); + + // All the global constants + for( Node n : code._start._outputs ) { + if( n.isConst() ) { + visit.set( n._nid ); + nodes.add( n ); + // Special for Cast:BOT + for( Node cast : n._outputs ) + if( cast != null && cast.nIns() == 2 && cast.in( 0 ) == null ) { + visit.set( cast._nid ); + nodes.add( cast ); + // Array pointer conversion adds the body offset after + // the zero-code PtrToInt. Both nodes are global-value + // descendants of the constant and otherwise have no + // function-local root from which to walk them. + if( cast instanceof PtrToIntNode ) + for( Node add : cast.outs() ) + if( add instanceof AddNode && !visit.get(add._nid) ) { + visit.set(add._nid); + nodes.add(add); + } + } + } + } + + // All the CompUnits + for( CompUnit cu : code._compunits.values() ) { + // Whole CompUnits have no users, went dead + if( cu._src!=null && cu._start != null && !cu._start.isDead() ) { + nodes.add(cu._start); + // A memory-free, nonreturning unit can lose its memory projection. + ProjNode mem=cu._start.proj(1); + if( mem!=null ) nodes.add(mem); + // All the functions, including internal ones, in comp-unit order + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() && fun._compunit == cu ) + _funWalk(fun,nodes,visit); + nodes.add(cu._stop); + } + } + + nodes.add(code._stop); + visit.clear(); + return nodes; + } + + // Walk and print whole functions at a time, in CG order + private static void _funWalk( FunNode fun, Ary rpo, BitSet visit ) { + int start = rpo._len; + _funRPO(fun,rpo,visit); + // A nonreturning function still owns a Return, even before LoopTree + // inserts synthetic exits. No loop-depth ordering is needed on disk. + _funRPO(fun.ret(),rpo,visit); + int len = rpo._len - start; + for( int i=0; i< len>>1; i++ ) + rpo.swap(start+i,start+len-1-i); + } + + // Walk and gather RPO nodes. + private static void _funRPO(Node n, Ary rpo, BitSet visit ) { + // Return-linked constants can have users in other compilation units. + if( n.isConst() ) return; + if( visit.get(n._nid) ) return; // Been there, done that + visit.set(n._nid); // Stop recursion + // Walk outputs ordered + if( n instanceof CFGNode ncfg ) { + if( n instanceof IfNode iff ) { + CProjNode c0 = iff.cproj(0); + CProjNode c1 = iff.cproj(1); + _funRPO(c0,rpo,visit); + _funRPO(c1,rpo,visit); + } else if( n instanceof StopNode ) { + // nothing + } else { + // CFG to CFG before CFG to data + for( Node use : n._outputs ) + if( use instanceof CFGNode usecfg && !ncfg.skip(usecfg) ) // Do not walk from Call to Fun + _funRPO(use,rpo,visit); + } + // Walk CFG to data eventually + for( Node use : n._outputs ) + if( !(use instanceof CFGNode) ) + _funRPO(use,rpo,visit); + } else { + // Do not walk from a non-CFG to a CFG; CFGs walk to CFGs to + // preserve CFG order. Do not walk *into* Phis; wait for the + // Region to walk the Phis (otherwise you visit some of the + // Phis ahead of others forcing the Phis to be spread around). + for( Node use : n._outputs ) { + if( use!=null && !(use instanceof CFGNode) && !(use instanceof PhiNode) ) + _funRPO(use,rpo,visit); + } + } + + // If parent is a Multi, do not add (yet). + // If self is a Multi, add self and children. + if( multiChild(n) || n instanceof CallEndNode ) { + // nothing; delay until Multi-head or CallNode + } else if( n instanceof MultiNode ) { + // Now lump all multi/projections together + printMulti(n,rpo); + } else if( n instanceof CallNode call ) { + printMulti(call.cend(),rpo); + rpo.add(call); + } else if( n instanceof RegionNode ) { + // Now lump all Phis together + int old = rpo._len; + for( Node use : n._outputs ) + if( use instanceof PhiNode ) + rpo.add(use); + // Sort by label? Want Phis before control outputs + Arrays.sort( rpo._es, old, rpo._len, (x,y) -> y.label().compareTo(x.label()) ); + rpo.add(n); + } else if( n instanceof StopNode ) { + // nothing + } else { + rpo.add(n); // Post-order add + } + } + + private static boolean multiChild(Node n) { + return n instanceof Proj || n instanceof PhiNode; + } + + private static void printMulti(Node n, Ary rpo) { + // Now lump all multi/projections together + for( Node use : n._outputs ) + rpo.add(use); + // Sort by projection order + if( !(n instanceof StartNode) ) + Arrays.sort( rpo._es,rpo._len-n.nOuts(),rpo._len, + (x,y) -> x instanceof ProjNode px && y instanceof ProjNode py ? (py.idx() - px.idx()) : (y._nid - x._nid) ); + rpo.add(n); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java index 616753d4..a4147576 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java +++ b/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 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/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index 9b4b0995..fb82ef0c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/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/src/main/java/com/seaofnodes/simple/codegen/Unlink.java b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java new file mode 100644 index 00000000..bb9a6196 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java @@ -0,0 +1,174 @@ +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 forEval(CodeGen code, StartNode start, StopNode stop) { + Ary nodes = new Ary<>(Node.class); + start.walk(n -> { nodes.add(n); return null; }); + Ary 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 CLInitNode init ) init.unlink(); + 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); + } + code.releaseUnlinkedNodes(); + for( Node n : nodes ) + if( n instanceof StartCUNode unitStart ) detachEmptyStart(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 1 ) { + if( fun.in(1) instanceof CallNode call ) + call.unlink(fun,1); + else + fun.removeDeadPath(1); + } + StartCUNode start = fun._compunit._start; + StopCUNode stop = fun._compunit._stop; + // Unhook the Stop->Return edge also + ReturnNode ret = fun.ret(); + int idx = stop._inputs.find(ret); + if( idx != -1 ) { + stop._inputs.del(idx); + ret.delUse(stop); + } + // + if( stop.nIns()==0 ) { + idx = code._stop._inputs.find(stop); + if( idx != -1 ) + code._stop.delDef(idx); + if( start.nIns() > 0 && start.in(0) != null ) + start.setDef(0,null); + if( start.nIns() > 1 && start.in(1) != null ) + start.setDef(1,null); + } + continue; + } + + // Insert the post-Opto code-generation hook. Unlike an Opto-time + // Start input, this no longer carries unknown-caller semantics. + ReturnNode ret = fun.ret(); + StartNode start = fun._compunit._start; + assert start!=null; + if( fun.nIns() <= 1 || fun.in(1) != start ) { + fun.insertDef(1,start); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) + parm.insertDef(1,ConstantNode.raw(parm._type)); + if( fun._compunit._stop._inputs.find(ret) == -1 ) + fun._compunit._stop.addDef(ret); + } + // Unlink from Call + for( int i=2; i { + if( n instanceof CallEndNode cend ) + for( int i=1; i strs, HashMap types, IdentityHashMap anodes) { + baos.packed1(_mode); + } abstract String op(); @Override protected ExprPrinter _print1(ExprPrinter p) { diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index dd0bc996..73e786e3 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; import java.util.IdentityHashMap; @@ -17,7 +18,9 @@ abstract public class BoolNode extends Node implements ModeNode { public BoolNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public BoolNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs); _mode = mode; } - + @Override public void packed(BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes) { + baos.packed1(_mode); + } abstract public String op(); // String opcode name @@ -116,7 +119,7 @@ abstract public class BoolNode extends Node implements ModeNode { public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } public EQ(Node lhs, Node rhs, byte mode) { super(lhs,rhs, mode); } - + @Override public Tag serialTag() { return Tag.EQ; } public String op() { return "=="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; @@ -130,7 +133,7 @@ abstract public class BoolNode extends Node implements ModeNode { public static class NE extends BoolNode { public NE(Node lhs, Node rhs) { super(lhs,rhs); } public NE(Node lhs, Node rhs, byte mode) { super(lhs,rhs,mode); } - + @Override public Tag serialTag() { return Tag.NE; } public String op() { return "!="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; @@ -144,7 +147,7 @@ abstract public class BoolNode extends Node implements ModeNode { public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } public LT(Node lhs, Node rhs, byte mode) { super(lhs,rhs, mode); } - + @Override public Tag serialTag() { return Tag.LT; } public String op() { return "<" ; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max < i2._min ) return TRUE; @@ -158,7 +161,7 @@ abstract public class BoolNode extends Node implements ModeNode { public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } public LE(Node lhs, Node rhs, byte mode) { super(lhs,rhs,mode); } - + @Override public Tag serialTag() { return Tag.LE; } public String op() { return "<="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max <= i2._min ) return TRUE; @@ -176,7 +179,7 @@ abstract public class BoolNode extends Node implements ModeNode { super(lhs,rhs,(byte)1); assert mode==1; } - + @Override public Tag serialTag() { return Tag.ULT; } public String op() { return "u<" ; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( Long.compareUnsigned(i1._max,i2._min) < 0 ) return TRUE; diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index df9e4fff..538b1a18 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -1,8 +1,11 @@ package com.seaofnodes.simple.node; 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; import java.util.BitSet; @@ -44,6 +47,28 @@ public class BulkMemPhiNode extends PhiNode { public boolean isSplit(int alias) { return _aliases.get(alias); } + @Override public Tag serialTag() { return Tag.BulkMemPhi; } + + @Override + public void packed(BAOS baos, HashMap strs, HashMap types, + IdentityHashMap anodes) { + super.packed(baos,strs,types,anodes); + baos.packed2(_aliases.cardinality()); + for( int alias = _aliases.nextSetBit(0); alias >= 0; alias = _aliases.nextSetBit(alias+1) ) + baos.packed2(alias); + } + + static Node make(BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases) { + Node[] ins = new Node[bais.packed1()]; + String label = strs[bais.packed2()]; + BitSet bits = new BitSet(); + for( int i=bais.packed2(); i>0; i-- ) { + int alias = bais.packed2(); + if( alias >= GlobalBits.RESERVED ) alias = aliases.map(fileAliases,alias); + bits.set(alias); + } + return new BulkMemPhiNode(label,bits.isEmpty() ? EMPTY : bits,ins); + } @Override public Type compute() { @@ -178,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); @@ -198,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/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 4f225fbe..7740df79 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/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/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java index 0a0de3cf..f7b48fbe 100644 --- a/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -4,7 +4,9 @@ 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.*; // Track class initializers - the code just after this point expects the named @@ -15,13 +17,19 @@ 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); _loc = loc; } + CLInitNode(BAOS bais, String[] strs) { super(null,null,null,null); _loc=Parser.Lexer.unpack(bais,strs); } + @Override public Tag serialTag() { return Tag.CLInit; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + Parser.Lexer.packed(_loc,baos,strs); + } + @Override public void gather(HashMap strs) { Parser.Lexer.gather(_loc,strs); } public CLInitNode(CLInitNode init) { super(init); @@ -68,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(); @@ -93,12 +103,60 @@ public class CLInitNode extends CFGNode implements MultiNode { } @Override public Node idealize() { + if( CodeGen.CODE._phase.ordinal() 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) { @@ -108,33 +166,19 @@ 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()); 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/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index 2bd48d92..073e4658 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -3,8 +3,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -23,7 +25,14 @@ public class CProjNode extends CFGNode implements Proj { _label = label; } public CProjNode(CProjNode c) { super(c); _idx = c._idx; _label = c._label; } - + @Override public Tag serialTag() { return Tag.CProj; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed1(_idx); + baos.packed2(_label==null ? 0 : strs.get(_label)); + } + static Node make( BAOS bais, String[] strs ) { + return new CProjNode(null, bais.packed1(), strs[bais.packed2()] ); + } @Override public String label() { return _label; } @@ -70,4 +79,7 @@ public class CProjNode extends CFGNode implements Proj { @Override public int idx() { return _idx; } + @Override public void gather( HashMap strs ) { + Serialize.gather(strs,_label); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 4422265f..b7b26265 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -37,7 +38,21 @@ public class CallEndNode extends CFGNode implements MultiNode { super(new Node[nIns]); _rpc = rpc; } - + @Override public Tag serialTag() { return Tag.CallEnd; } + public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed1(Serialize.nIns(this,anodes)); + // Linked CallEnds depend on Return types which depend on CallEnds; + // break the cycle + baos.packed2(types.get(_type)); + baos.packed2(types.get(_rpc)); + } + static Node make( BAOS bais, Type[] types ) { + int nIns = bais.packed1(); + Type type = types[bais.packed2()]; + Node cend = new CallEndNode(nIns,(TypeRPC)types[bais.packed2()]); + cend._type = type; + return cend; + } @Override public boolean blockHead() { return true; } @@ -60,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 @@ -145,7 +128,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; @@ -155,8 +138,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 @@ -195,10 +193,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/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index f791225a..12c7f1e3 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -4,11 +4,13 @@ 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; import com.seaofnodes.simple.type.TypeRPC; import com.seaofnodes.simple.type.XInt; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; import java.util.IdentityHashMap; @@ -23,7 +25,16 @@ public class CallNode extends CFGNode { public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc=loc; CodeGen.CODE._calls.add(this); } public CallNode(CallNode call) { super(call); _loc = call._loc; } - + @Override public Tag serialTag() { return Tag.Call; } + public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed1(nIns()); + Parser.Lexer.packed(_loc,baos,strs); + } + @Override public void gather(HashMap strs) { Parser.Lexer.gather(_loc,strs); } + static Node make( BAOS bais, String[] strs ) { + int nIns = bais.packed1(); + return new CallNode(Parser.Lexer.unpack(bais,strs),new Node[nIns]); + } @Override protected ExprPrinter _print1(ExprPrinter p) { String fname = name(); @@ -44,6 +55,7 @@ public class CallNode extends CFGNode { } + Node ctrl() { return in(0); } Node mem () { return in(1); } // Args mapped 1-to-1 on inputs, so conceptually start at 2 @@ -64,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) { @@ -158,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() strs, HashMap types, IdentityHashMap anodes ) { + baos.packed2(types.get(_con)); // NPE if fails lookup + } + static Node make( BAOS bais, Type[] types) { return raw(types[bais.packed2()]); } // Semantic constant construction through Lower. A unique internal // function identity carries a lifetime edge to the function's Return. diff --git a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java index 813e6fcb..62140873 100644 --- a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java @@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.Type; public class CtrlNode extends CFGNode { public CtrlNode() { super(CodeGen.CODE._start); } - + @Override public Tag serialTag() { throw com.seaofnodes.simple.util.Utils.TODO(); } @Override public String label() { return "Ctrl"; } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p("Cctrl"); } @Override public boolean isConst() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 0db2b7a2..f173f0ef 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -9,7 +9,7 @@ public class DivNode extends ArithNode { @Override boolean allowFloat() { return true; } public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public DivNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } - + @Override public Tag serialTag() { return Tag.Div; } @Override public String op() { return _mode==1 ? "//" : "/"; } diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index f7518184..3e95fffb 100644 --- a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -35,6 +35,13 @@ public class EscapeNode extends TypeNode { public Node pub () { return in(3); } public Field fld() { return (Field)_con; } + @Override public Tag serialTag() { return Tag.Escape; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed2(types.get(_con)); + } + static Node make( BAOS bais, Type[] types) { + return new EscapeNode((Field)types[bais.packed2()], null,null,null); + } @Override protected ExprPrinter _print1(ExprPrinter p) { diff --git a/src/main/java/com/seaofnodes/simple/node/ExternNode.java b/src/main/java/com/seaofnodes/simple/node/ExternNode.java index 2d1dc29f..978298fc 100644 --- a/src/main/java/com/seaofnodes/simple/node/ExternNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ExternNode.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import java.util.BitSet; @@ -17,11 +19,20 @@ public class ExternNode extends ConstantNode { // Its lifetime and eventual relocation are carried by the extern symbol // and CodeGen's FIDX-to-extern mapping instead. public ExternNode(Type t, String ex) { super(t,true); _extern = ex; } - + @Override public Tag serialTag() { return Tag.Extern; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed2(types.get(_con )); + baos.packed2( strs.get(_extern)); + } + static Node make( BAOS bais, String[] strs, Type[] types) { + return new ExternNode(types[bais.packed2()], strs[bais.packed2()]); + } @Override public String label() { return "#"+_con+":"+_extern; } @Override public boolean eq(Node n) { return this==n; } - + @Override public void gather( HashMap strs ) { + Serialize.gather(strs,_extern); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java b/src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java index 23ed5468..409ce5d1 100644 --- a/src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -10,7 +11,9 @@ import java.util.IdentityHashMap; // selection replaces it with this symbol's address and a zero displacement. public class ExternOffsetNode extends ExternNode { public ExternOffsetNode(String name) { super(TypeInteger.BOT,name); } - + @Override public Tag serialTag() { return Tag.ExternOffset; } @Override public Node copy() { return new ExternOffsetNode(_extern); } - + @Override public void packed(BAOS baos, HashMap strs, HashMap types, IdentityHashMap nodes) { + baos.packed2(strs.get(_extern)); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/FldOffNode.java b/src/main/java/com/seaofnodes/simple/node/FldOffNode.java index 535241a6..a9f8d692 100644 --- a/src/main/java/com/seaofnodes/simple/node/FldOffNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FldOffNode.java @@ -19,7 +19,7 @@ public class FldOffNode extends TypeNode { public final String _fname; // Field name public final Parser.Lexer _loc; // public FldOffNode( Node base, String fname, Parser.Lexer loc ) { super(TypeInteger.BOT,base); _fname = fname; _loc=loc; } - + @Override public Tag serialTag() { throw Utils.TODO("should not reach here"); } @Override public String label() { return _fname == " len" ? "sizeof()" : "#"+_fname; diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index ad79130e..6a8d5d50 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; import java.util.Arrays; @@ -41,7 +42,24 @@ public class FunNode extends RegionNode { _compunit = fun._compunit; _extern = fun._extern; } - + @Override public Tag serialTag() { return Tag.Fun; } + @Override public void packed(BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + assert !_folding; + baos.packed1(Serialize.nIns(this,anodes)); // Object-local linked calls + baos.packed2(types.get(_sig)); // NPE if fails lookup + baos.packed2(_name==null ? 0 : strs.get(_name)); + baos.packed2(_approxUIDs); + // _compunit set from context on loading, do not write + } + static Node make( BAOS bais, String[] strs, Type[] types) { + Node[] ins = new Node[bais.packed1()]; + TypeFunPtr sig = (TypeFunPtr)types[bais.packed2()]; + String name = strs[bais.packed2()]; + FunNode fun = new FunNode(null,sig,name,null,ins); + fun._approxUIDs = bais.packed2(); + // _compunit set from context on loading, do not read + return fun; + } @Override public String label() { return _name == null ? "$fun"+_sig.fidx() : _name; } @@ -64,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; } @@ -75,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() ) @@ -153,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 ) { @@ -194,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 with no internal dots: // "sys." is a module, but "sys.io." is not. @@ -460,4 +492,7 @@ public class FunNode extends RegionNode { return slotRotate*8; } + @Override public void gather( HashMap strs ) { + Serialize.gather(strs,_name); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java index 3d6031b8..82053fd8 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -14,8 +15,13 @@ public class FunPtrNode extends TypeNode { super(tfp,start,ret); } public FunPtrNode(FunPtrNode fptr) { super(fptr); } - - + @Override public Tag serialTag() { return Tag.FunPtr; } + @Override public void packed(BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes) { + baos.packed2(types.get(_con)); + } + static Node make(BAOS bais, Type[] types) { + return new FunPtrNode((TypeFunPtr)types[bais.packed2()],null,null); + } public ReturnNode ret() { return (ReturnNode)in(1); } public FunNode fun() { return ret().fun(); } diff --git a/src/main/java/com/seaofnodes/simple/node/GuardNode.java b/src/main/java/com/seaofnodes/simple/node/GuardNode.java index e985da72..0ce504d9 100644 --- a/src/main/java/com/seaofnodes/simple/node/GuardNode.java +++ b/src/main/java/com/seaofnodes/simple/node/GuardNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeScalar; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; @@ -24,6 +25,11 @@ public class GuardNode extends Node { _nonZero = guard._nonZero; } + @Override public Tag serialTag() { return Tag.Guard; } + @Override public void packed(BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes) { + baos.write(_nonZero ? 1 : 0); + } + static Node make(BAOS bais) { return new GuardNode(bais.read()!=0,null,null); } @Override public String label() { return _nonZero ? "(!=0)" : "(==0)"; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 471a28fe..c83c81d0 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -13,7 +13,7 @@ public class IfNode extends CFGNode implements MultiNode { CodeGen.CODE.add(this); // Because idoms are complex, just add it } public IfNode(IfNode iff) { super(iff); } - + @Override public Tag serialTag() { return Tag.If; } @Override protected ExprPrinter _print1(ExprPrinter p) { diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index e1a495ad..c58bba39 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -4,7 +4,9 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.BitSet; @@ -25,7 +27,11 @@ public class LoadNode extends MemOpNode { public LoadNode(Parser.Lexer loc, String name, int alias, Node ctrl, Node mem, Node ptr, Node off) { super(loc, name, alias, true, Type.BOTTOM, ctrl, mem, ptr, off); } - + LoadNode( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { + super(bais,strs,types,fileAliases,aliases,true); + _con = Type.BOTTOM; // Serialized slot retained while MemOps share TypeNode + } + @Override public Tag serialTag() { return Tag.Load; } @Override boolean canDrop(MemOpNode other, Node dep) { return super.canDrop(other,dep) && !clobbered(dep); diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 005a6624..45f7a6fa 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -11,7 +12,8 @@ import java.util.IdentityHashMap; public class LoopNode extends RegionNode { public LoopNode( Parser.Lexer loc, Node xctrl, Node entry ) { super(loc,xctrl,entry,null); } public LoopNode( LoopNode loop ) { super(loop); } - + @Override public Tag serialTag() { return Tag.Loop; } + public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { } public CFGNode entry() { return cfg(1); } public CFGNode back () { return cfg(2); } @@ -43,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 @@ -53,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/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index cbf19c55..dfe8794d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Utils; @@ -17,7 +18,9 @@ public class MemMergeNode extends Node { public MemMergeNode( Node ...nodes) { super(nodes); _type = TypeMem.BOT; } public MemMergeNode(MemMergeNode mem) { super(mem); } - + @Override public Tag serialTag() { return Tag.MemMerge; } + public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { baos.packed1(nIns()); } + static Node make( BAOS bais ) { Node mem = new MemMergeNode(); mem.setDefX(bais.packed1()-1,null); return mem; } @Override public String label() { return "ALLMEM"; } @Override public boolean isMem() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index fa399e1d..bfbd46c3 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.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.GlobalBits; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; import java.lang.StringBuilder; @@ -60,6 +61,24 @@ public abstract class MemOpNode extends TypeNode { _isLoad= mop._isLoad; } + MemOpNode( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases, boolean isLoad ) { + this(null, + strs[bais.packed2()], + mapAlias(bais,fileAliases,aliases),isLoad, + types[bais.packed2()],null,null,null,null); + } + + private static int mapAlias( BAOS bais, GlobalBits fileAliases, GlobalBits aliases ) { + int alias = bais.packed2(); + return alias < GlobalBits.RESERVED ? alias : aliases.map(fileAliases,alias); + } + + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed2(_name==null ? 0 : strs.get(_name)); + baos.packed2(_alias); + baos.packed2(types.get(_con)); // NPE if fails lookup + assert _isLoad == this instanceof LoadNode; // No machine ops + } static String mlabel(String name) { return "[]"==name ? "ary" : ("#"==name ? "len" : name); } String mlabel() { return mlabel(_name); } diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index 5ae716a7..aaaedb89 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.codegen.GlobalBits; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -22,6 +24,22 @@ public class MemPhiNode extends PhiNode { _alias = phi._alias; } + @Override public Tag serialTag() { return Tag.MemPhi; } + + @Override + public void packed(BAOS baos, HashMap strs, HashMap types, + IdentityHashMap anodes) { + super.packed(baos,strs,types,anodes); + baos.packed2(_alias); + } + + static Node make(BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases) { + Node[] ins = new Node[bais.packed1()]; + String label = strs[bais.packed2()]; + int alias = bais.packed2(); + if( alias >= GlobalBits.RESERVED ) alias = aliases.map(fileAliases,alias); + return new MemPhiNode(label,alias,ins); + } @Override public Type compute() { diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 4d7e3ddb..e84eb611 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; import java.util.IdentityHashMap; @@ -14,7 +15,10 @@ public class MinusNode extends Node implements ModeNode { public MinusNode(Node in) { super(null, in); } public MinusNode(Node in, byte mode) { super(null, in); _mode = mode; } - + @Override public void packed(BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes) { + baos.packed1(_mode); + } + @Override public Tag serialTag() { return Tag.Minus; } @Override public byte mode() { return _mode; } @Override public Node setMode(byte mode) { diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 49c6432a..bb99cad5 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -9,7 +9,7 @@ public class MulNode extends ArithNode { @Override boolean allowFloat() { return true; } public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public MulNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } - + @Override public Tag serialTag() { return Tag.Mul; } @Override public String op() { return "*"; } diff --git a/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/src/main/java/com/seaofnodes/simple/node/NeverNode.java index a7b4cf65..ba1dab8c 100644 --- a/src/main/java/com/seaofnodes/simple/node/NeverNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java @@ -12,7 +12,7 @@ import com.seaofnodes.simple.type.TypeTuple; public class NeverNode extends IfNode { public NeverNode(NeverNode ctrl) { super(ctrl); } public NeverNode(float ignore, Node ctrl) { super(ctrl,null); } - + @Override public Tag serialTag() { return Tag.Never; } @Override public String label() { return "Never"; } diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 5cbe1b61..fe80f690 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import java.util.HashMap; import java.util.IdentityHashMap; @@ -22,7 +23,14 @@ public class NewNode extends Node implements MultiNode { // --- Serialization public NewNode(NewNode nnn) { super(nnn); _ts = nnn._ts; } - + @Override public Tag serialTag() { return Tag.New; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed2(types.get(_ts)); + } + static Node make( BAOS bais, Type[] types) { + TypeStruct ts = (TypeStruct)types[bais.packed2()]; + return new NewNode(ts,null,null); + } @Override public String label() { return "new_"+(_ts.isAry() ? "ary_"+_ts._fields[1]._t.str() : _ts.str()); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index de39ca80..8718f351 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.BaseNode; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.print.IRPrinter; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; @@ -67,8 +68,84 @@ public abstract class Node extends BaseNode implements Cloneable { _hash = 0; } + // Disk/serialized opcode tags + public enum Tag { + Add,And,BulkMemPhi,EQ,NE,LT,LE,ULT, + CallEnd,Call,ConFldOff,Con,CLInit,CProj, + Div,Escape,Extern,ExternOffset,Fun,FunPtr,Guard, + If,Load,Loop,MemMerge,MemPhi,Minus,Mul, + New,Never,Not,Or,Parm,Phi,Proj,PtrToInt, + ReadOnly,Return,Region,RoundF32, + Sar,Shl,Shr,Start,StartCU,StopCU,Stop,Store,Sub, + ToInteger,ToFloat,XCtrl,Xor; + public static final Tag[] VALS = values(); + public Node make( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { + return switch(this) { + case Add -> new AddNode(null,null,(byte)bais.packed1()); + case And -> { int mode=bais.packed1(); assert mode==1; yield new AndNode(null,null,null); } + case Div -> new DivNode(null,null,(byte)bais.packed1()); + case Guard -> GuardNode.make(bais); + case If -> new IfNode(null,null); + case Loop -> new LoopNode(null,null,null); + case Minus -> new MinusNode(null,(byte)bais.packed1()); + case Mul -> new MulNode(null,null,(byte)bais.packed1()); + case Never -> new NeverNode(1.2f, null); + case Not -> new NotNode(null); + case Or -> { int mode=bais.packed1(); assert mode==1; yield new OrNode(null,null,null); } + case ReadOnly-> new ReadOnlyNode((Node)null); + case Return ->new ReturnNode(null,null,null,null,null); + case RoundF32-> new RoundF32Node(null); + case PtrToInt-> new PtrToIntNode((Node)null); + case Sar -> { int mode=bais.packed1(); assert mode==1; yield new SarNode(null,null,null); } + case Shl -> { int mode=bais.packed1(); assert mode==1; yield new ShlNode(null,null,null); } + case Shr -> { int mode=bais.packed1(); assert mode==1; yield new ShrNode(null,null,null); } + case Start -> new StartNode(null,null,TypeInteger.BOT); + case Sub -> new SubNode(null,null,(byte)bais.packed1()); + case ToFloat-> new ToFloatNode(null); + case ToInteger-> new ToIntegerNode(null); + case XCtrl -> new XCtrlNode(); + case Xor -> { int mode=bais.packed1(); assert mode==1; yield new XorNode(null,null,null); } + + case EQ -> new BoolNode.EQ (null,null,(byte)bais.packed1()); + case NE -> new BoolNode.NE (null,null,(byte)bais.packed1()); + case LT -> new BoolNode.LT (null,null,(byte)bais.packed1()); + case LE -> new BoolNode.LE (null,null,(byte)bais.packed1()); + case ULT -> new BoolNode.ULT(null,null,(byte)bais.packed1()); + + case Call -> CallNode.make(bais,strs); + case CallEnd-> CallEndNode.make(bais ,types); + case CLInit -> new CLInitNode(bais,strs); + case CProj -> CProjNode.make(bais,strs); + case Con -> ConstantNode.make(bais ,types); + case Escape-> EscapeNode.make(bais ,types); + case Extern-> ExternNode.make(bais,strs,types); + case ExternOffset-> new ExternOffsetNode(strs[bais.packed2()]); + case FunPtr-> FunPtrNode.make(bais, types); + case Fun -> FunNode.make(bais,strs,types); + case Load -> new LoadNode(bais,strs,types,fileAliases,aliases); + case MemMerge->MemMergeNode.make(bais); + case MemPhi-> MemPhiNode.make(bais,strs,types,fileAliases,aliases); + case BulkMemPhi-> BulkMemPhiNode.make(bais,strs,types,fileAliases,aliases); + case New -> NewNode.make(bais ,types); + case Parm -> ParmNode.make(bais,strs,types); + case Phi -> PhiNode.make(bais,strs,types); + case Proj -> ProjNode.make(bais,strs); + case Store -> new StoreNode(bais,strs,types,fileAliases,aliases); + case Stop -> StopNode.make(bais); + case StartCU-> StartCUNode.make(bais,strs,types); + case StopCU -> StopCUNode.make(bais); + case Region-> RegionNode.make(bais); + + default -> throw Utils.TODO("Should not reach here"); + }; + } + }; + public Tag serialTag() { throw Utils.TODO(); } + // Serialize extra data, including input counts + public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) {} + // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" - public String label() { return getClass().getSimpleName().replace("Node",""); } + public String label() { return serialTag().toString(); } public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } @@ -667,6 +744,7 @@ public abstract class Node extends BaseNode implements Cloneable { return null; } + public void gather(HashMap strs ) { } // If a Type upgrade happens, put on worklist boolean _upgradeType( HashMap TYPES ) { return false; } diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index e22d16b6..2328c287 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.util.Utils; public class NotNode extends Node { public NotNode(Node in) { super(null, in); } - + @Override public Tag serialTag() { return Tag.Not; } @Override protected String format() { return "(!%1)"; } diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index 263c3e87..9d50d1a9 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class OrNode extends ArithNode { public OrNode( Parser.Lexer loc, Node lhs, Node rhs) { super(loc,lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Or; } @Override public String label() { return "Or"; } @Override public String op() { return "|"; } diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 316efb93..91c471c0 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.Serialize; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -20,7 +22,19 @@ public class ParmNode extends PhiNode { _type = declaredType; } public ParmNode(ParmNode parm) { super(parm, parm._label ); _idx = parm._idx; _declaredType = parm._declaredType; } - + @Override public Tag serialTag() { return Tag.Parm; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed1(Serialize.nIns(this,anodes)); // Object-local linked calls + baos.packed2(_label==null ? 0 : strs.get(_label)); + baos.packed2(types.get(_declaredType)); // NPE if fails lookup + baos.packed1(_idx); + } + static Node make( BAOS bais, String[] strs, Type[] types) { + Node[] ins = new Node[bais.packed1()]; + String label = strs[bais.packed2()]; + Type minType = types[bais.packed2()]; + return new ParmNode(label, bais.packed1(), minType, ins); + } @Override public String label() { return MemOpNode.mlabel(_label); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 61e4b468..3cf6f854 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; import java.util.HashMap; @@ -35,7 +36,15 @@ public class PhiNode extends Node { while( nIns() < r.nIns() ) addDef(sample); } - + @Override public Tag serialTag() { return Tag.Phi; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed1(nIns()); + baos.packed2(_label==null ? 0 : strs.get(_label)); + } + static Node make( BAOS bais, String[] strs, Type[] types) { + Node[] ins = new Node[bais.packed1()]; + return new PhiNode(strs[bais.packed2()], ins); + } @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @@ -272,4 +281,7 @@ public class PhiNode extends Node { return Parser.error(sb.unchar(5).toString(),null); } + @Override public void gather( HashMap strs ) { + Serialize.gather(strs,_label); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index a0142379..fcc113a8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -2,9 +2,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeTuple; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -22,7 +24,14 @@ public class ProjNode extends Node implements Proj { _label = label; } public ProjNode(ProjNode p) { super(p); _idx = p._idx; _label = p._label; } - + @Override public Tag serialTag() { return Tag.Proj; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed1(_idx); + baos.packed2(_label==null ? 0 : strs.get(_label)); + } + static Node make( BAOS bais, String[] strs ) { + return new ProjNode(null, bais.packed1(), strs[bais.packed2()] ); + } @Override public String label() { return _label; } @@ -56,4 +65,7 @@ public class ProjNode extends Node implements Proj { @Override public int idx() { return _idx; } + @Override public void gather( HashMap strs ) { + Serialize.gather(strs,_label); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java b/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java index 094734fa..d3d38060 100644 --- a/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java @@ -18,7 +18,7 @@ public class PtrToIntNode extends Node { public PtrToIntNode(Node ptr) { super(null,ptr); } public PtrToIntNode(PtrToIntNode ptr) { super(ptr); } - + @Override public Tag serialTag() { return Tag.PtrToInt; } @Override protected String format() { return "(i64*)%1"; } @Override public Type compute() { diff --git a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java index ab7e0ae0..0a720d5b 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java @@ -10,7 +10,7 @@ import com.seaofnodes.simple.type.TypeMemPtr; public class ReadOnlyNode extends Node { public ReadOnlyNode( Node n ) { super(null,n); } public ReadOnlyNode( ReadOnlyNode n ) { super(n); } - + @Override public Tag serialTag() { return Tag.ReadOnly; } @Override protected String format() { return "(const)%1"; } @Override public Type compute() { diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 923773c4..8883ba8e 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.BAOS; import java.util.*; public class RegionNode extends CFGNode { @@ -14,7 +15,9 @@ public class RegionNode extends CFGNode { public RegionNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } public RegionNode(RegionNode r, Parser.Lexer loc) { super(r); _loc = loc; } public RegionNode(RegionNode r) { super(r); if( r!=null ) _loc = r._loc; } - + @Override public Tag serialTag() { return Tag.Region; } + public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { baos.packed1(nIns()); } + static Node make( BAOS bais ) { return new RegionNode(null,new Node[bais.packed1()]); } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(label()); diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 0bb090ee..311a7ea4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -28,7 +28,7 @@ public class ReturnNode extends CFGNode { _fun = fun; } public ReturnNode( ReturnNode ret, FunNode fun ) { super(ret); _fun = fun; } - + @Override public Tag serialTag() { return Tag.Return; } public Node ctrl() { return in(0); } public Node mem () { return in(1); } @@ -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/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java index 02d3bbaa..65f10a79 100644 --- a/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java +++ b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.type.TypeFloat; public class RoundF32Node extends Node { public RoundF32Node(Node lhs) { super(null, lhs); } - + @Override public Tag serialTag() { return Tag.RoundF32; } @Override protected String format() { return "((f32)%1)"; } diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index fa63334b..737b531f 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class SarNode extends ArithNode { public SarNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Sar; } @Override public String op() { return ">>"; } @Override long doOp( long x, long y ) { return x >> y; } diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 380fc246..f657cf51 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class ShlNode extends ArithNode { public ShlNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Shl; } @Override public String op() { return "<<"; } @Override long doOp( long x, long y ) { return x << y; } diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 17170a1f..e93ea0e8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class ShrNode extends ArithNode { public ShrNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Shr; } @Override public String op() { return ">>>"; } @Override long doOp( long x, long y ) { return x >>> y; } diff --git a/src/main/java/com/seaofnodes/simple/node/StartCUNode.java b/src/main/java/com/seaofnodes/simple/node/StartCUNode.java index 0f7a322a..cd51f603 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartCUNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartCUNode.java @@ -1,7 +1,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -11,12 +13,21 @@ public class StartCUNode extends StartNode { public final String _fname; public StartCUNode(StartNode start, StopCUNode stop, Type arg, String fname) { super(start,stop,arg); _fname = fname; } public StartCUNode(StartCUNode start) { super(start); _fname = start._fname; } - + @Override public Tag serialTag() { return Tag.StartCU; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + baos.packed2(types.get(_arg)); + baos.packed2(strs.get(_fname)); + } + static Node make( BAOS bais, String[] strs, Type[] types ) { + return new StartCUNode(null,null,types[bais.packed2()],strs[bais.packed2()]); + } @Override public CFGNode cfg0() { return (CFGNode)in(0); } // IDom is cfg0() and depth is always Start+1 which is 0+1 or 1 @Override public int idepth() { return 1; } @Override public CFGNode idom(Node dep) { return cfg0(); } - + @Override public void gather( HashMap strs ) { + Serialize.gather(strs,_fname); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 3c605e30..a7ea4ac1 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -29,7 +29,7 @@ public class StartNode extends LoopNode implements MultiNode { public StartNode(StartNode start, StopNode stop, Type arg) { super(null,start,stop); _arg = arg; } public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; } - + @Override public Tag serialTag() { return Tag.Start; } public Type arg() { return _arg; } @Override protected ExprPrinter _print1(ExprPrinter p) { @@ -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/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index 53c2325c..61970aa0 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -10,7 +11,13 @@ import java.util.IdentityHashMap; public class StopCUNode extends StopNode { public StopCUNode() { super(); } public StopCUNode(StopNode stop) { super(stop); } - + @Override public Tag serialTag() { return Tag.StopCU; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { baos.packed1(nIns()); } + static Node make( BAOS bais ) { + StopCUNode stop = new StopCUNode(); + stop.setDefX(bais.packed1()-1,null); + return stop; + } public StartCUNode start() { for( Node use : _outputs ) @@ -48,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 ) { @@ -76,20 +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 strs, HashMap types, IdentityHashMap anodes ) { baos.packed1(Serialize.nIns(this,anodes)); } + static Node make( BAOS bais ) { + StopNode stop = new StopNode(); + stop.setDefX(bais.packed1()-1,null); + return stop; + } @Override protected ExprPrinter _print1(ExprPrinter p) { diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index bdd07c8d..5fa0b99f 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -4,7 +4,9 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; import java.util.IdentityHashMap; @@ -35,7 +37,18 @@ public class StoreNode extends MemOpNode { _init = init; _size = size; } - + StoreNode( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { + super(bais,strs,types,fileAliases,aliases,false); + addDef(null); + _init = bais.read() != 0; + _size = (byte)bais.read(); + } + @Override public Tag serialTag() { return Tag.Store; } + @Override public void packed( BAOS baos, HashMap strs, HashMap types, IdentityHashMap anodes ) { + super.packed(baos,strs,types, anodes ); + baos.write(_init ? 1 : 0); + baos.write(_size); + } @Override boolean canDrop(MemOpNode other, Node dep) { return super.canDrop(other,dep) && _init==((StoreNode)other)._init; @@ -114,7 +127,7 @@ public class StoreNode extends MemOpNode { // Freeze the semantic Store variant as soon as the pointer exposes a // canonical field declaration. Waiting until after structural memory // peeps can lose the declaration to a flow-sensitive constant field - // state. + // state. Imported Stores already carry a serialized non-zero width. if( _size==0 && (_size= storageType()) != 0 ) { unlock(); // Width participates in the cached hash. return init(); diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index adad2ed5..8eb1f4cc 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -9,7 +9,7 @@ public class SubNode extends ArithNode { @Override boolean allowFloat() { return true; } public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public SubNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs,mode); } - + @Override public Tag serialTag() { return Tag.Sub; } @Override public String op() { return "-"; } diff --git a/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java new file mode 100644 index 00000000..426174e7 --- /dev/null +++ b/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 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; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index 1acf55b6..151a326e 100644 --- a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class ToFloatNode extends Node { public ToFloatNode(Node lhs) { super(null, lhs); } - + @Override public Tag serialTag() { return Tag.ToFloat; } @Override protected String format() { return "(flt)%1"; } diff --git a/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java b/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java index 9136aacc..33806300 100644 --- a/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.type.TypeInteger; // Truncate toward zero, saturating overflow; NaN converts to zero. public class ToIntegerNode extends Node { public ToIntegerNode(Node lhs) { super(null,lhs); } - + @Override public Tag serialTag() { return Tag.ToInteger; } @Override public String label() { return "ToInteger"; } @Override protected String format() { return "(int)%1"; } diff --git a/src/main/java/com/seaofnodes/simple/node/TypeNode.java b/src/main/java/com/seaofnodes/simple/node/TypeNode.java index 970472da..3ab2d6f9 100644 --- a/src/main/java/com/seaofnodes/simple/node/TypeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/TypeNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.BitSet; import java.util.HashMap; diff --git a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java index 3792e224..32e1deb9 100644 --- a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.Type; public class XCtrlNode extends CFGNode { public XCtrlNode() { super(new Node[]{CodeGen.CODE._start}); } - + @Override public Tag serialTag() { return Tag.XCtrl; } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p("Xctrl"); } @Override public boolean isConst() { return true; } @Override public Type compute() { return Type.XCONTROL; } diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index e9cd13a5..c825f396 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class XorNode extends ArithNode { public XorNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Xor; } @Override public String op() { return "^"; } @Override long doOp( long x, long y ) { return x ^ y; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java index 856af3b8..96a64cd0 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java @@ -1,14 +1,14 @@ package com.seaofnodes.simple.node.cpus.arm; -import com.seaofnodes.simple.type.TypeFunPtr; 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 { final TypeFunPtr _tfp; - CallRRARM( CallNode call ) { super(call); _tfp = call.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(); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java index 4ab69430..68f1016a 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.node.cpus.riscv; -import com.seaofnodes.simple.type.TypeFunPtr; 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 { diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java index c204f25c..3109df63 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; -import com.seaofnodes.simple.type.TypeFunPtr; 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 { diff --git a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 58506e9c..e8218afd 100644 --- a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -7,9 +7,9 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.BAOS; import java.util.ArrayList; import com.seaofnodes.simple.codegen.Encoding; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; /** Machine-specific facts; traversal, columns and byte display live in print/. */ diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index ec4a588d..beaa719c 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import java.util.*; @@ -130,7 +131,18 @@ public class Field extends Type { @Override public Type at( int idx ) { return _t; } @Override public void set( int idx, Type t ) { _t = t; } // Tags: final/!final; +alias+name+external-storage flag - + @Override int TAGOFF() { return 2; } + @Override public void packed( BAOS baos, HashMap strs ) { + baos.write(TAGOFFS[_type] + (_final ? 1 : 0)); + baos.packed2(_alias); + baos.packed2(strs.get(_fname)); + baos.write(_extern ? 1 : 0); + } + static Field packed( int tag, BAOS bais, String[] strs ) { + int alias = bais.packed2(); + String fname = strs[bais.packed2()]; + return malloc(fname,null,alias,(tag&1)==1,bais.read()!=0); + } @Override public SB _print( SB sb, BitSet visit, boolean html ) { diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 1979368e..980daf0f 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.util.*; import java.util.*; @@ -512,6 +513,123 @@ public class Type /*implements Cloneable*/ { Type _upgradeType(HashMap TYPES) { assert is_nokids(); return this; } + // Recursively gather all types + public void gather(HashMap types ) { + if( types.containsKey(this) ) return; // TEST + types.put(this,types.size()); // SET + int nkids = nkids(); + for( int i=0; i strs ) { + assert is_simple(); + baos.write(_type); + } + static Type packed( int tag ) { + return switch( tag ) { + case TBOT -> BOTTOM; + case TTOP -> TOP; + case TCTRL -> CONTROL; + case TXCTRL->XCONTROL; + case TNIL -> NIL; + default -> throw Utils.TODO("Should not reach here: unknown simple type tag"); + }; + } + + // Produce a type with null child types + static Type packed( BAOS bais, String[] strs ) { + int x = bais.read(); + int type = Arrays.binarySearch( TAGOFFS, x ); + if( type < 0 ) type = -(type+1)-1; + int off = x - TAGOFFS[type]; + return switch( type ) { + case 0, 1, 2, 3, 4, 5 -> Type.packed( off ); + case TSCALAR -> TypeScalar .packed( off ); + case TPTR -> TypePtr .packed( off ); + case TINT -> TypeInteger.packed( off, bais ); + case TFLT -> TypeFloat .packed( off, bais ); + case TCONARY -> TypeConAry .packed( off, bais ); + case TRPC -> TypeRPC .packed( off, bais ); + case TMEMPTR -> TypeMemPtr .packed( off, bais ); + case TFUNPTR -> TypeFunPtr .packed( off, bais ); + case TMEM -> TypeMem .packed( off, bais ); + case TFLD -> Field .packed( off, bais, strs ); + case TSTRUCT -> TypeStruct .packed( off, bais, strs ); + case TTUPLE -> TypeTuple .packed( off, bais ); + default -> throw Utils.TODO("Should not reach here: unknown packed type tag"); + }; + } + + // Read a packed Type array + public static Type[] packed( BAOS bais, String[] strs, int ntypes, HashMap existingTypes, + GlobalBits fileAliases, GlobalBits aliases, + GlobalBits fileFidxs , GlobalBits fidxs , + GlobalBits fileRpcs , GlobalBits rpcs ) { + Type[] types = new Type[ntypes]; + // Read Types in ID# order, no children + for( int i=0; i= GlobalBits.RESERVED ) + fld._alias = aliases.map(fileAliases,fld._alias); + } + if( types[i] instanceof TypeFunPtr tfp ) + tfp._fidxs = remapBits(fileFidxs,fidxs,tfp._fidxs,GlobalBits.RESERVED); + if( types[i] instanceof TypeRPC rpc ) + rpc._rpcs = remapBits(fileRpcs,rpcs,rpc._rpcs,GlobalBits.RESERVED); + if( types[i] instanceof TypeMem mem ) { + if( mem._alias >= GlobalBits.RESERVED ) + mem._alias = aliases.map(fileAliases,mem._alias); + mem._escFs = remapBits(fileFidxs ,fidxs ,mem._escFs,GlobalBits.RESERVED); + mem._escAs = remapBits(fileAliases,aliases,mem._escAs,GlobalBits.RESERVED); + } + } + + // Intern them all at once + BOTTOM.recurClose(types); + return types; + } + + private static int[] remapBits(GlobalBits fileBits, GlobalBits bits, int[] fileLocals, int firstMapped ) { + if( fileLocals == XInt.EMPTY || fileLocals == XInt.FULL ) + return fileLocals; + assert !XInt.isHigh(fileLocals); + int[] locals = XInt.EMPTY; + for( int fileLocal = XInt.next(fileLocals,-1); fileLocal >=0; fileLocal = XInt.next(fileLocals,fileLocal) ) + locals = XInt.make(locals,fileLocal < firstMapped ? fileLocal : bits.map(fileBits,fileLocal)); + return locals; + } + + // ---------------------------------------------------------- // Size in bits to hold an instance of this type. diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index 860cefc5..c9093e3b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -74,7 +74,17 @@ public abstract class TypeConAry extends TypeScalar { public abstract long at8(int idx); public abstract int len(); @Override public abstract int log_size(); - - public void write( BAOS baos ) { throw Utils.TODO("Should not reach here: abstract constant array cannot be written"); } + + // Reserve tags for u8 array + @Override int TAGOFF() { return 1; } + @Override public void packed( BAOS baos, HashMap strs ) { + assert log_size()==0 && !_any; + baos.write(TAGOFFS[TCONARY]+0); + baos.packed4(len()); + baos.write((byte[])_ary); + } + static TypeConAry packed( int tag, BAOS bais ) { + return TypeConAryB.make(bais.read(new byte[bais.packed4()])); + } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java index bddcb1fb..5877c309 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -16,6 +16,5 @@ public class TypeConAryB extends TypeConAry { @Override public String str() { return "[\""+new String(_ary)+"\"]"; } @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && _widen==ary._widen && Arrays.equals(_ary,ary._ary); } @Override int hash() { return Arrays.hashCode(_ary); } - @Override public void write( BAOS baos ) { baos.write(_ary); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index 8638b8c9..d410e9cf 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.AryInt; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; import java.util.HashMap; @@ -98,6 +99,26 @@ public class TypeFloat extends TypeScalar { @Override public Type makeZero() { return FZERO; } + // Reserve tags for F64,F32,constant + @Override int TAGOFF() { return 3; } + @Override public void packed( BAOS baos, HashMap strs ) { + if( this==F64 ) baos.write(TAGOFFS[_type] + 0); + else if( this==F32 ) baos.write(TAGOFFS[_type] + 1); + else { + assert isConstant(); + baos.write(TAGOFFS[_type] + 2); + baos.packed8(Double.doubleToLongBits(_con)); + } + } + + static Type packed( int tag, BAOS bais ) { + return switch( tag ) { + case 0 -> F64; + case 1 -> F32; + case 2 -> constant(Double.longBitsToDouble(bais.packed8())); + default -> throw Utils.TODO("Should not reach here: unknown float type tag"); + }; + } @Override int hash() { return (int)(Double.hashCode(_con) ^ _sz ^ (1<<17)); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 301fcc8b..56f47bff 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -75,6 +75,7 @@ public class TypeFunPtr extends TypeNil { } + @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } public TypeFunPtr makeFrom( int fidx ) { return make1(_nil,_open,_sig,_ret,fidx); } @@ -236,6 +237,33 @@ public class TypeFunPtr extends TypeNil { else _sig[idx] = t; } + // Reserve tags for null/not and open/close, one fidx/bitset, 0-6 args + // Tags 0-5 - not,close,1 fidx, 0-5 args (+fidx) + // Tag 6 - not ,close+fidxs+nargs + // Tag 7 - null,close+fidxs+nargs + @Override int TAGOFF() { return 8; } + @Override public void packed( BAOS baos, HashMap strs ) { + assert _open; // Open: Passing extra args is fine, and extras ignored. + if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx() < 64 ) { + baos.write(TAGOFFS[_type] + nargs()); + baos.packed2(fidx()); + } else { + baos.write(TAGOFFS[_type] + 6 + (_nil==2 ? 0 : 1)); + baos.packed1(nargs()); + XInt.packed(baos,_fidxs); + } + } + static TypeFunPtr packed( int tag, BAOS bais ) { + if( tag < 6 ) { + int fidx = bais.read(); + assert fidx < 64; // Need a larger fidx space + return malloc((byte)2,true,new Type[tag],null, XInt.make(fidx)); + } + byte nil = (byte)(tag==6 ? 2 : 3); + int nargs = bais.packed1(); + int[] fidxs = XInt.packed(bais); + return malloc(nil,true,new Type[nargs],null,fidxs); + } @Override int hash() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index a2cf08b0..a0c2266d 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.AryInt; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; import java.util.HashMap; @@ -176,7 +177,38 @@ public class TypeInteger extends TypeScalar { if( _isConstant() ) return BOT; return isHigh() ? dual() : this; } + // Reserve tags for I64,I32,U32,0,constant,generic + @Override int TAGOFF() { return 7; } + @Override public void packed( BAOS baos, HashMap strs ) { + if( this==BOT ) baos.write(TAGOFFS[_type] + 0); + else if( this==I32 ) baos.write(TAGOFFS[_type] + 1); + else if( this==U32 ) baos.write(TAGOFFS[_type] + 2); + else if( this==BOOL) baos.write(TAGOFFS[_type] + 3); + else if( this==ZERO) baos.write(TAGOFFS[_type] + 4); + else if( isConstant() ) { + baos.write(TAGOFFS[_type] + 5); + baos.packed8(_min); + } else { + baos.write(TAGOFFS[_type] + 6); + baos.packed8(_min); + baos.packed8(_max); + assert -3 <= _widen && _widen <= 3; + baos.packed1(_widen + 3); + } + } + static Type packed( int tag, BAOS bais ) { + return switch( tag ) { + case 0 -> BOT; + case 1 -> I32; + case 2 -> U32; + case 3 -> BOOL; + case 4 -> ZERO; + case 5 -> constant(bais.packed8()); + case 6 -> make(bais.packed8(),bais.packed8(),(byte)(bais.packed1()-3)); + default -> throw Utils.TODO("Should not reach here: unknown integer type tag"); + }; + } @Override int hash() { return Utils.fold(_min) * Utils.fold(_max) + _widen; } @Override public boolean eq( Type t ) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 4234a5e5..9ae68bcf 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -173,7 +173,31 @@ public class TypeMem extends Type { @Override public int nkids() { return 1; } @Override public Type at( int idx ) { return _t; } @Override public void set( int idx, Type t ) { _t = t; } - + // one tag for alias#1, one tag for generic alias. + // tag bit for _one, another bit for _final. + @Override int TAGOFF() { return 12; } + @Override public void packed( BAOS baos, HashMap strs ) { + baos.write(TAGOFFS[_type] + + (_alias==1 ? 0 : 1) + + (!_final ? 0 : 2) + + (!_one ? 0 : (_clz ? 4 : 8))); + if( _alias!=1 ) { + // generic alias + assert _alias <= 255; + baos.packed1( _alias ); + } + XInt.packed(baos,_escFs); + XInt.packed(baos,_escAs); + } + static TypeMem packed( int tag, BAOS bais ) { + int alias = (tag&1)==0 ? 1 : bais.packed1(); + boolean xfinal= (tag&2)==2; + boolean one = (tag&12)!=0; + boolean clz = (tag&4)==4; + int[] escFs = XInt.packed(bais); + int[] escAs = XInt.packed(bais); + return malloc(alias,null,one,clz,xfinal,escFs,escAs); + } @Override public SB _print(SB sb, BitSet visit, boolean html) { if( this==BOT ) return sb.p("MemBot"); diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 73ca6190..175b1c63 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.BAOS; import java.util.*; /** @@ -162,6 +163,19 @@ public class TypeMemPtr extends TypeNil { @Override public Type at( int idx ) { return _obj; } @Override public void set( int idx, Type t ) { _obj = (TypeStruct)t; } + // Reserve tags for null/not, one/general, public/private and read-only access + @Override int TAGOFF() { return 16; } + @Override public void packed( BAOS baos, HashMap strs ) { + assert _nil>=2; + baos.write(TAGOFFS[_type] + + (_nil==2 ? 0 : 1) + + (!_one ? 0 : 2) + + (!_pub ? 0 : 4) + + (!_ro ? 0 : 8) ); + } + static TypeMemPtr packed( int tag, BAOS bais ) { + return malloc((byte)((tag&1)+2),null,(tag&2)==2,(tag&4)==4).access((tag&8)==8); + } @Override public String str() { if( this==BOT ) return "PtrBot"; diff --git a/src/main/java/com/seaofnodes/simple/type/TypePtr.java b/src/main/java/com/seaofnodes/simple/type/TypePtr.java index 7e9e70e4..38941ed1 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypePtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypePtr.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.util.BAOS; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; @@ -52,6 +53,14 @@ public class TypePtr extends TypeNil { @Override TypePtr _makeStorage() { return PTR; } + // Reserve 2 tags, PTR and NPTR + @Override int TAGOFF() { return 2; } + @Override public void packed( BAOS baos, HashMap strs ) { + assert _nil>=2; + baos.write(TAGOFFS[_type] + (_nil==2 ? 0 : 1)); + } + static TypePtr packed( int tag ) { return tag==0 ? NPTR : PTR; } + @Override public String str() { return STRS[_nil]; } @Override public SB _print(SB sb, BitSet visit, boolean html) { return sb.p(str()); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeRPC.java b/src/main/java/com/seaofnodes/simple/type/TypeRPC.java index 7acc99de..8a12f50a 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeRPC.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeRPC.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; import java.util.*; /** @@ -74,6 +75,25 @@ public class TypeRPC extends Type { @Override boolean _isConstant() { return XInt.isConstant(_rpcs); } @Override TypeRPC _makeStorage() { return this; } + // Reserve tags for ALL, singleton, generic + @Override int TAGOFF() { return 3; } + @Override public void packed( BAOS baos, HashMap strs ) { + if( this==BOT ) { + baos.write( TAGOFFS[_type] + 0 ); + } else if( XInt.isConstant(_rpcs) ) { // Singleton + baos.write(TAGOFFS[_type] + 1); + baos.packed2(rpc()); + } else { // Generic + assert !XInt.isHigh(_rpcs); // Not serializing above-center RPC + baos.write(TAGOFFS[_type] + 2); + XInt.packed(baos,_rpcs); + } + } + static TypeRPC packed( int tag, BAOS bais ) { + if( tag==0 ) return BOT; + if( tag==1 ) return malloc(XInt.make(bais.packed2())); + return malloc(XInt.packed(bais)); + } @Override int hash() { return XInt.hash(_rpcs); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeScalar.java b/src/main/java/com/seaofnodes/simple/type/TypeScalar.java index e369e6a5..eaba0a1c 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeScalar.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeScalar.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import java.util.ArrayList; @@ -39,6 +40,17 @@ public class TypeScalar extends Type { @Override public boolean isHigh() { return this == TOP; } @Override Type _makeStorage() { return BOT; } + // Reserve tags for both lattice endpoints. Unlike most concrete scalar + // families, generic scalar TOP can survive into a serialized graph. + @Override int TAGOFF() { return 2; } + @Override public void packed(BAOS baos, HashMap strs) { + assert this == BOT || this == TOP; + baos.write(TAGOFFS[_type] + (this == BOT ? 0 : 1)); + } + static TypeScalar packed(int tag) { + assert tag == 0 || tag == 1; + return tag == 0 ? BOT : TOP; + } @Override public String str() { return isHigh() ? "~scalar" : "scalar"; } @Override SB _print(SB sb, BitSet visit, boolean html) { return sb.p(str()); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 67169009..4c5ae6ea 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -528,7 +528,22 @@ public class TypeStruct extends Type { // Tags 5 - closed(+ nflds +name) // Tags 6-10- open +#nflds (+name) // Tags 11 - open (+ nflds +name) - + @Override int TAGOFF() { return 24; } + @Override public void packed( BAOS baos, HashMap strs ) { + baos.write(TAGOFFS[_type]+ (_fref ? 12 : 0) + (_open ? 6 : 0) + Math.min(5,_fields.length)); + if( _fields.length >= 5 ) + baos.packed2(_fields.length); + baos.packed2(strs.get(_name)); + // TODO: Write aliases summary + } + static TypeStruct packed( int tag, BAOS bais, String[] strs ) { + boolean fref = tag >= 12; + if( fref ) tag -= 12; + int ntag = tag >= 6 ? tag-6 : tag; + int nflds = ntag < 5 ? ntag : bais.packed2(); + String name = strs[bais.packed2()]; + return malloc(name,ntag!=tag,fref,new Field[nflds]); + } @Override SB _print(SB sb, BitSet visit, boolean html ) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 0d70bdf2..075698dc 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -124,6 +124,20 @@ public class TypeTuple extends Type { @Override public Type at( int idx ) { return _types[idx]; } @Override public void set( int idx, Type t ) { _types[idx] = t; } + // Reserve tags for tuples with 2,3,generic + @Override int TAGOFF() { return 4; } + @Override public void packed( BAOS baos, HashMap strs ) { + if( _types.length==2 ) baos.write(TAGOFFS[_type] + 0); + else if( _types.length==3 ) baos.write(TAGOFFS[_type] + 1); + else if( _types.length==4 ) baos.write(TAGOFFS[_type] + 2); + else baos.write(TAGOFFS[_type] + 3).packed2(_types.length); + } + static TypeTuple packed( int tag, BAOS bais ) { + if( tag==0 ) return malloc(new Type[2]); + if( tag==1 ) return malloc(new Type[3]); + if( tag==2 ) return malloc(new Type[4]); + return malloc(new Type[bais.packed2()]); + } @Override SB _print(SB sb, BitSet visit, boolean html ) { if( this==TOP ) return sb.p("[TOP]"); diff --git a/src/main/java/com/seaofnodes/simple/type/XInt.java b/src/main/java/com/seaofnodes/simple/type/XInt.java index 126a4e64..3e74df84 100644 --- a/src/main/java/com/seaofnodes/simple/type/XInt.java +++ b/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -196,18 +196,48 @@ public abstract class XInt { } + public static void packed(BAOS baos, int[] xs) { + baos.packed1(xs.length); + for( int i=1; 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 + public static int[] remap( int[] xs, AryInt map ) { + if( xs==FULL ) return xs; + assert !isHigh(xs); + int[] ys = free(xs.length); + for( int bit = next(xs,0); bit >=0; bit = next(xs,bit) ) { + int bat = map.at(bit); + ys[idx(bat)] |= mask(bat); + } + return intern(ys); + } + public static String str(int[] xs) { return str(new SB(),xs).toString(); } -- cgit v1.2.3