From 87cd60a6a4894d71eb27603f7c7d697c71975684 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 | 54 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 349 +++++++++- .../com/seaofnodes/simple/codegen/CompUnit.java | 100 ++- .../com/seaofnodes/simple/codegen/ElfReader.java | 245 +++++++ .../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 | 190 ++++++ .../simple/codegen/GlobalCodeMotion.java | 60 +- .../java/com/seaofnodes/simple/codegen/IFG.java | 14 +- .../com/seaofnodes/simple/codegen/InstSelect.java | 2 +- .../java/com/seaofnodes/simple/codegen/Iter.java | 74 ++- .../seaofnodes/simple/codegen/ListScheduler.java | 6 +- .../com/seaofnodes/simple/codegen/LocalIds.java | 47 -- .../java/com/seaofnodes/simple/codegen/Module.java | 98 +++ .../java/com/seaofnodes/simple/codegen/Opto.java | 44 +- .../com/seaofnodes/simple/codegen/ParseAll.java | 219 ++++++- .../com/seaofnodes/simple/codegen/Serialize.java | 716 +++++++++++++++++++++ .../com/seaofnodes/simple/codegen/StaticData.java | 8 +- .../com/seaofnodes/simple/codegen/TypeCheck.java | 10 +- .../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 | 11 +- .../com/seaofnodes/simple/node/CLInitNode.java | 97 ++- .../java/com/seaofnodes/simple/node/CProjNode.java | 14 +- .../com/seaofnodes/simple/node/CallEndNode.java | 127 ++-- .../java/com/seaofnodes/simple/node/CallNode.java | 32 +- .../com/seaofnodes/simple/node/ConFldOffNode.java | 2 +- .../com/seaofnodes/simple/node/ConstantNode.java | 7 +- .../com/seaofnodes/simple/node/ConvertNode.java | 17 +- .../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 | 43 +- .../com/seaofnodes/simple/node/FunPtrNode.java | 10 +- .../seaofnodes/simple/node/GlobalEscapeNode.java | 35 + .../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 | 85 ++- .../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 | 2 +- .../com/seaofnodes/simple/node/StopCUNode.java | 22 +- .../java/com/seaofnodes/simple/node/StopNode.java | 13 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 17 +- .../java/com/seaofnodes/simple/node/SubNode.java | 2 +- .../com/seaofnodes/simple/node/SummaryNode.java | 69 ++ .../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 | 119 ++++ .../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 | 34 +- .../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 +- 103 files changed, 3397 insertions(+), 462 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/GlobalEscapeNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/SummaryNode.java (limited to 'src/main/java/com/seaofnodes') diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 39230eb2..a018c3ee 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 3b5a8ce7..cef7091a 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(); @@ -2916,6 +2926,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 3784b6b8..9a544685 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; @@ -28,6 +28,7 @@ public class ClassInitDependencies { private final int[] _pres; private final int[] _lows; private final int[] _stk ; + private final int[] _spos; // Stack position; FIDX -> stack slot + 1, or 0 when absent. private int _sp; private int _pre; @@ -39,6 +40,7 @@ public class ClassInitDependencies { _pres = new int[code._linker._len]; _lows = new int[code._linker._len]; _stk = new int[code._linker._len]; + _spos = new int[code._linker._len]; // BitSet visit = code.visit(); // Visit set per-fcn @@ -51,13 +53,23 @@ 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); - // An unknown callback can call any escaped local function. Zero is - // this outside-world vertex, not an executable function identity. + + // 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(); - for( FunNode fun : code._linker ) - if( fun!=null && !fun.isDead() && !fun.isClz() && XInt.bit(escaped,fun.sig().fidx()) ) - callees.push(fun.sig().fidx()); + // 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(); } @@ -65,12 +77,14 @@ public class ClassInitDependencies { // 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); @@ -124,7 +138,8 @@ public class ClassInitDependencies { // Return an error string, or null if no cycle contains multiple clinits. public String check() { Arrays.fill(_pres,0); - _sp = 0; + // A prior check may have stopped with a cycle still on the stack. + while( _sp>0 ) _spos[_stk[--_sp]] = 0; _pre = 1; int idx = -1; @@ -183,6 +198,7 @@ public class ClassInitDependencies { int scc( int fidx ) { // Assign pre-order number _lows[fidx] = _pres[fidx] = _pre++; + _spos[fidx] = _sp+1; _stk[_sp++] = fidx; // walk outbound edges if( _edgess[fidx]!=null ) { @@ -192,28 +208,22 @@ public class ClassInitDependencies { int idx = scc(edge); if( idx != -1 ) return idx; // Found a cycle _lows[fidx] = Math.min(_lows[fidx],_lows[edge]); - } else if( _edgess[edge]!=null && onStk(edge) ) { + } else if( _edgess[edge]!=null && _spos[edge]!=0 ) { _lows[fidx] = Math.min(_lows[fidx],_pres[edge]); } } } // Found a cycle if( _lows[fidx] == _pres[fidx] ) { - int idx = find(fidx); + int idx = _spos[fidx]-1; if( hasClzCycle(idx) ) return idx; // Found a class cycle - // Pop stack, including fidx - _sp = idx; + // Pop stack, including fidx, should be a really short loop + while( _sp>idx ) _spos[_stk[--_sp]] = 0; } return -1; // No cycle } - private int find(int e) { - for( int i=0; i<_sp; i++ ) if( _stk[i] == e ) return i; - return -1; - } - private boolean onStk(int e) { return find(e) != -1; } - private boolean hasClzCycle(int idx) { int clinits = 0; for( int i=idx; i<_sp; i++ ) { diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index a3de2ec8..998989b1 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 @@ -111,15 +122,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. @@ -129,6 +140,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 @@ -151,7 +163,10 @@ 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. Choose combined in-memory output before + // Encoding; otherwise saved IR requests separate object encodings. // No code emission, just IR generation public CodeGen driver( Phase phase ) { return driver(phase,null,null,false,false,0); } @@ -171,7 +186,8 @@ 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. + // 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); @@ -183,12 +199,17 @@ public class CodeGen { step(target, Phase.FinalizeIR, this::finalizeIR, dump); // Final error check - bad programs fail here step(target, Phase.TypeCheck, this::typeCheck, dump); - // Replace "fat" nodes with their exploded explicit IR; this can - // introduce CFG diamonds - step(target, Phase.Lower, this::lower, dump); + // Save reloadable ideal IR for a later seperate compilation + step(target, Phase.Serialize, () -> Serialize.forTarget(this,target,inMemory), dump); + // Eval2 executes ideal operations, including CLInit, directly. Only + // machine compilation expands them before scheduling. + step(target, Phase.Lower, () -> { if( cpu!=null ) lower(); }, dump); // Compute the loop-tree, used for approximating exec frequencies for // scheduling and register allocation step(target, Phase.LoopTree, this::loopTree, dump); + // Detach call-graph edges; ideal execution retains unloaded summaries + // as dispatch targets and schedules their bodies on first use. + step(target, Phase.Unlink, () -> unlink(cpu!=null), dump); // Instruction selection step(target, Phase.Select, () -> instSelect(cpu,callingConv), dump); // Global Code Motion @@ -198,8 +219,8 @@ public class CodeGen { // Register allocation 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 + step(target, Phase.Encoding, () -> encode(inMemory), dump); + // Export bits (and serialized IR) into ELF files step(target, Phase.Export, () -> exportELF(inMemory,emitEntrySymbol), dump); return this; } @@ -216,6 +237,8 @@ public class CodeGen { // Record elapsed time even on failure, but report completion only on success. CodeGen phase(Phase next, boolean ordered, Runnable work) { assert ordered : "Cannot run "+next+" after "+_phase; + // Serialize reads the checked graph; other phases can change it. + if( next!=Phase.Serialize ) _classInitDependencies = null; _phase = next; long t0 = System.currentTimeMillis(); work.run(); // Do The Phase @@ -255,13 +278,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<>(); @@ -269,14 +307,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); } @@ -295,6 +333,9 @@ public class CodeGen { // Start and Stop; end points of the generated IR public StartNode _start; public StopNode _stop; + // Iter creates this shared analysis result. Start's unused backedge slot + // roots it until Unlink; serialized Stops retain its escape facts instead. + public GlobalEscapeNode _globalEscapes; // Global Value Numbering. Hash over opcode and inputs; hits in this table // are structurally equal. @@ -327,13 +368,13 @@ public class CodeGen { public void link(FunNode fun) { int fidx = fun.sig().fidx(); _linker.setX(fidx,fun); + add(_globalEscapes); // A new or replacement summary may expose escapes. } // "Linker" mapping from constant TypeFunPtrs to heads of function. These // 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<>(); @@ -349,13 +390,17 @@ 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); } + 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 @@ -382,10 +427,83 @@ 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); + } + + // TypeCheck saves its successful analysis for Serialize. Loading bodies + // or entering another graph-changing phase discards it. + ClassInitDependencies _classInitDependencies; + 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()); @@ -401,17 +519,22 @@ 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 || _phase==Phase.TypeCheck || _phase==Phase.Serialize), + () -> _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 @@ -440,7 +563,16 @@ public class CodeGen { } // --------------------------- - + public void unlink() { + unlink(true); + } + private void unlink(boolean removeImports) { + phase(Phase.Unlink, _phase==Phase.LoopTree, () -> { + _start.setDef(2,null); // Releases the compiler-only escape analysis. + if( removeImports ) Unlink.run(this,true); + else Unlink.forEval(this,_start,_stop); + }); + } // --------------------------- // Control Flow Graph in Reverse Post Order. @@ -448,7 +580,7 @@ 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)); } // --------------------------- @@ -479,21 +611,174 @@ 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 encode(false); } + private CodeGen encode(boolean inMemory) { return phase(Phase.Encoding, _phase==Phase.RegAlloc, () -> { + // Saved ideal IR requests one object per unit, including when the + // driver stopped at Serialize and resumed later. In-memory linking + // explicitly requests one combined image instead. + if( inMemory || _serials.isEmpty() ) { _encoding = new Encoding(this).encode(); return; } + for( CompUnit cu : _serials.keySet() ) { + _emitUnit = cu; + Encoding enc = new Encoding(this).encode(); + _encodings.put(cu,enc); + if( cu._fname.equals(_srcName==null ? "Test" : _srcName) ) _encoding = enc; + } + _emitUnit = null; + }); } // --------------------------- // Exporting to external formats ElfWriter _elf; 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); + if( inMemory ) { + assert _encodings.isEmpty() : "In-memory output must be selected before Encoding"; + new LinkMem(this).link(_encoding); + } + else { + if( _serials.isEmpty() ) + throw new IllegalStateException("ELF export needs ideal IR: request Export from the driver, or Serialize before Lower"); + assert !_encodings.isEmpty() : "File output must be selected before Encoding"; + Encoding entry = _encoding; + BAOS serial = _serial; + try { + 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..1dced3a8 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java @@ -0,0 +1,245 @@ +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) { + code._classInitDependencies = null; // Loaded bodies can change init edges. + 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; + + // Identities not owned by this compilation. Reserved bits are not foreign. + public int[] foreign() { + int[] foreign = XInt.alloc((_local>>>5)+2); + Arrays.fill(foreign,1,foreign.length,-1); + for( int i = 0; i<_local; i++ ) { + String owner = _local2Clz.at(i); + if( owner==null || !owner.startsWith("C:") ) + foreign[(i>>>5)+1] &= ~(1< 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 ba3743e3..a1ac4e67 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -10,31 +10,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); @@ -60,8 +76,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 @@ -137,7 +153,7 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ - // Scheduling is not recursive. Retain scratch capacity between schedules, + // Scheduling is not recursive. Retain scratch capacity between objects, // but release graph references and reset only the entries we used. private static CFGNode[] LATE = new CFGNode[1]; // Load NIDs at their CFG block choices, checked against Store blocks. @@ -147,7 +163,7 @@ public abstract class GlobalCodeMotion { private static final Ary ANTIDEPS = new Ary<>(Node.class); private static final WorkList WORK = new WorkList<>(); - private static void schedLate( CodeGen code ) { + private static void schedLate( CodeGen code, StopNode stop ) { assert TOUCHED.isEmpty() && PLACED.isEmpty() && WORK.isEmpty(); if( code.UID() > LATE.length ) { int len = Math.max(code.UID(),LATE.length<<1); @@ -157,7 +173,7 @@ public abstract class GlobalCodeMotion { WORK.clear(); // Breadth-first scheduling // Early scheduling has released the shared visit bits. - breadth(code._stop,PLACED,LATE,ANTI,ANTIDEPS,code.visit()); + breadth(stop,PLACED,LATE,ANTI,ANTIDEPS,code.visit()); // Copy the best placement choice into the control slot for( Node n : PLACED ) @@ -209,7 +225,6 @@ public abstract class GlobalCodeMotion { // All uses done, schedule _doSchedLate(n,placed,late,anti,antideps); } - TOUCHED.push(n._nid); // A use just finished; reconsider its inputs and waiting loads, @@ -312,7 +327,8 @@ public abstract class GlobalCodeMotion { lca = anti_dep(load,late[mem._nid],mem.cfg0(),lca,mem,anti); } } - // Release this load's marks before another compilation reuses IDs. + // This load's marks are no longer needed; leave scratch clean even + // when the next compilation reuses these node IDs. for( CFGNode cfg = marked; cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = 0; return lca; diff --git a/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/src/main/java/com/seaofnodes/simple/codegen/IFG.java index bcdb14bf..d15e66da 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -172,6 +172,16 @@ abstract public class IFG { // Check use-side for self-conflict; if so we MUST split selfConflict(alloc,def,lrg1); + // All operands are live together, regardless of their input order. + TMP.put(lrg1,def); + } + + // Check fixed-register uses after gathering every operand. An indirect + // call's target comes after its arguments, but must also avoid their + // fixed registers (and may need to move from its incoming register). + for( int i=1; 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..5b4fb983 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -2,16 +2,25 @@ 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. + assert code._globalEscapes==null; + code._globalEscapes = new GlobalEscapeNode(); + code._start.setDef(2,code._globalEscapes); + // The phase shift closes all parser-in-progress states and freezes + // unknown external inputs. Imported nodes carry post-Opto escape + // precision, but Iter is a fresh pessimistic solve: memory escape + // summaries must restart at FULL so newly discovered private escapes + // can only be removed, never added. Seed the complete graph once. + boolean hasImports = code._externPaths != null; code._start.walk(n -> { - 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 +43,58 @@ 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); + // Recompute each imported unit's contribution from its reset inputs. + 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 29157631..00000000 --- a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java +++ /dev/null @@ -1,47 +0,0 @@ -package com.seaofnodes.simple.codegen; - -import com.seaofnodes.simple.type.XInt; -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<>(); - - // All registered Simple identities are local; native storage and the - // unallocated tail belong to the outside world. Reserved IDs are excluded. - public int[] foreign() { - int[] foreign = XInt.alloc((_next>>>5)+2); - Arrays.fill(foreign,1,foreign.length,-1); - for( int i = 0; i<_next; i++ ) { - String owner = _owners.atX(i); - if( owner==null || !owner.startsWith("C:") ) - foreign[(i>>>5)+1] &= ~(1<=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 e1282883..8c8827c6 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -40,17 +40,19 @@ abstract public class Opto { // OPTIMISTIC INTERPROCEDURAL SCCP sccp(code, oldTypes, changes, deps); - // Settle modes, then resume SCCP on affected nodes without resetting types. - // Any further type changes must still fall; BOTTOM results stay BOTTOM. + // Settle unresolved modes using SCCP's int/float evidence. Some + // computes wait at TOP until a mode is known; others already return + // BOTTOM and stay there. Resume SCCP only on the affected nodes; + // types are not reset, and any further changes must still fall. resolveNumericModes(code,modes); if( !code._iter._work.isEmpty() ) sccp(code, oldTypes, changes, deps); + Node dep; + while( (dep=deps.pop())!=null ) code.add(dep); // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. - Node dep; - while( (dep=deps.pop())!=null ) code.add(dep); moveChangesToWorklist(code, oldTypes, changes); for( ReturnNode ret : returns ) code.add(ret.unkeep()); } @@ -63,7 +65,8 @@ abstract public class Opto { // Opto ends Parm.inProgress(), enabling constant folding even // when a parameter's type was already constant before SCCP. if( x instanceof ParmNode && x._type.isHighOrConst() ) deps.push(x); - // SCCP adds call edges and default arguments, not numeric operations. + // SCCP adds call edges and default arguments, not numeric + // operations. Gather unresolved modes on this required walk. if( x instanceof ModeNode mode && mode.mode()==0 ) modes.push(x); // Change snapshot, not a bound: Opto adds foreign identities. oldTypes.setX(x._nid,x._type); @@ -74,25 +77,22 @@ abstract public class Opto { } - // Rediscover ordinary functions through calls and escapes. This chapter - // retains initializer entries until opaque CLInit obligations are lowered. + // 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