diff options
Diffstat (limited to 'chapter28b')
34 files changed, 998 insertions, 369 deletions
diff --git a/chapter28b/Makefile b/chapter28b/Makefile index 954a22a5..ec59a033 100644 --- a/chapter28b/Makefile +++ b/chapter28b/Makefile @@ -165,6 +165,7 @@ $(RELEASE_SYS): $(OBJS)/lib_$(CPU_ABI)/sys.o @echo "copying " $@ @[ -d $(dir $@) ] || mkdir -p $(dir $@) @cp $< $@ + @cp -r $(dir $<)sys $(dir $@) $(RELEASE_CRT): src/main/c/simple_crt.c @echo "compiling " $@ diff --git a/chapter28b/README.ja.md b/chapter28b/README.ja.md index a3221da5..0c565a76 100644 --- a/chapter28b/README.ja.md +++ b/chapter28b/README.ja.md @@ -25,12 +25,35 @@ Store の幅、元のソース位置も保存します。入れ子の構造体 組み合わせを今回の番号へ写します。型とノードに同じ写像を使い、複数ファイルを またぐ再帰型も復元します。 -読み込みの単位は現在オブジェクトです。無関係なオブジェクトは読み込まずに済みますが、選ばれた -オブジェクトの保存済み IR は全体を復元し、記録された依存先も読み込みます。`sys.io.p` だけを -呼ぶ場合でも、`sys.o` にまとめられた十個の単位をすべて読み込み、`aryu8` と `aryi64` も含みます。 -必要なメンバーだけの読み込みは今後の目標です。IR の読み込みだけでクラスが初期化されたり、 -その本体がクライアントの出力にコピーされたりするわけではありません。元のソースの解析は省けますが、 -インポートしたグラフも新しい呼び出し元とともに最適化し、型検査します。 +コンパイル単位ごとに `sys.o`、`sys/io.o`、`sys/libc.o` などを出力します。宣言と関数の +要約は本体より先に保存し、IR を復元せずに読めます。未ロードの関数は `FunNode`、 +`SummaryNode`、`ReturnNode` で表し、戻り値・メモリ・エスケープ情報を解析に使います。 +要約そのものはインライン化しません。ワークリストが空になった時点で、保存したサイズを +参考に本体を要求し、読み込んで解析してから実際のインライン化を判断します。 + +`sys.io.p` を通常の呼び出しとして残す場合、`io` の IR は不要です。`io.o` の本体を +読み込んでも、その中の外部参照には型があり、別の本体を自動的に要求しません。 +メタデータの探索は保守的で、要求したオブジェクト内の関数本体はまとめて読み込みます。 +さらに細かい関数単位の読み込みは今後の目標です。 + +要約には直接呼び出しとクラス初期化の依存辺も保存します。循環の可能性が見つかったら、 +残りの本体をすべて読み込み、最適化後に再検査してからエラーを報告します。循環の外の +ヘルパーが返す定数によって、循環内の辺が消える場合もあるためです。 + +コンパイル直後のネイティブリンクは CompUnit に保存されたオブジェクトのパスを使います。 +コンパイラの状態を持たず保存済みオブジェクトだけをリンクするテストでは、必要な +オブジェクトをすべて明示的に列挙します。必要なファイルが欠けていればリンクに失敗します。 +ネイティブ実行では実行時の動的ロードは行いません。 +Eval2 も実行前の解析時に依存オブジェクトを解決します。型検査済みプログラムの +オブジェクトは、互いに整合するビルドから提供されることを前提とします。 +実行しない分岐からの依存でも、必要なオブジェクトがなければ失敗します。 +Eval2 は型検査済みのプログラムを実行し、呼び出しで必要になったオブジェクトの IR だけを +復元して個別にスケジュールします。これはリンク済みプログラムの準備を遅らせる仕組みで、 +実行中に新しいライブラリを探索するものではありません。実行中のグラフの再最適化は行いません。 +理想ノードの CLInit を直接実行します。子の `<clinit>` は親の初期化を確認してから、 +自分の `$init` フラグを設定し、本体を実行します。Eval2 と Lower 後のコードでこの順序を +共有し、呼び出し側は対象クラスのフラグだけを検査します。 +IR の読み込みだけではクラスの初期化や本体の出力は起こりません。 ## 実行できる例 @@ -90,7 +113,7 @@ java -ea -cp "build/classes/main:build/classes/test:lib/*" \ ## 検証と今後 明示的に指定したソースは常にコンパイルします。他のローカルオブジェクトを再利用する前に、 -記録された依存関係をたどり、各オブジェクトにまとめられた全ソースを検査します。 +記録された依存関係をたどり、各オブジェクトのソースを検査します。 入力の欠落や、より新しいソース・依存オブジェクトがあれば、保存した型や IR を使わず 再解析します。A が B をインライン化していれば、B のオブジェクトが未更新でも、 B のソース変更で A は無効になります。循環は訪問済み集合で処理します。 @@ -110,9 +133,11 @@ make tests CHAPTERS=chapter28b オブジェクトにします。`make release` は jar と標準ライブラリを作り、`make view` は 共通のグラフビューアーを起動します。 -`IncrementalBuildTest` は時刻を明示的に設定し、再利用、間接的な変更、まとめられた +`IncrementalBuildTest` は時刻を明示的に設定し、再利用、間接的な変更、オブジェクト間の 循環、入力の欠落、ライブラリ更新を検査します。変更後のネイティブ実行結果も クリーンビルドと比較します。 +`SelectiveLoadingTest` は要約による呼び出し、インライン化のためのロード、静的リンク、 +初期化循環の再検査を確認します。 保存形式は `C0DE` 以外のバージョン番号をまだ持ちません。コンパイラや形式を変えたら オブジェクトを再構築してください。高コストの往復一致検査は無効のままで、古い増分 diff --git a/chapter28b/README.md b/chapter28b/README.md index 0a7baa68..008f34d2 100644 --- a/chapter28b/README.md +++ b/chapter28b/README.md @@ -5,8 +5,10 @@ English | [日本語](README.ja.md) [Previous: Chapter 28a](../chapter28a/README.md) The previous chapter compiled every discovered source file together. This -chapter lets a library and other code compile separately, and have full type -information. The client needs the library's *object* file, but not its source. +chapter lets a program and the libraries it uses compile separately, with +full type information. To compile a program that uses a library, we need the +library's *object* file, but not its source. + In spirit this is similar to Java's *class* file, with its full execution and type semantics stored in the file; we happen to be using an ELF file for the same reason. The ahead-of-time compiled code is *also* available for the @@ -14,11 +16,11 @@ linking step. An ordinary native object contains machine code, data, symbols, and relocations. Simple adds a `.simple` section with types and the ideal IR. -Importing `.simple` lets the client check types and optimize calls into the +Importing `.simple` lets the compiler check types and optimize calls into the library. Calls that remain out of line use the library's machine code at native link time. -## A library and a client +## A program that uses a library The runnable example has two separate source roots: @@ -76,7 +78,7 @@ java -ea -cp "build/classes/main:build/classes/test:lib/*" \ src/test/smp/separate/library/Counters.smp ``` -Then compile and evaluate the client using that object: +Then compile and evaluate the program using that object: ```sh java -ea -cp "build/classes/main:build/classes/test:lib/*" \ @@ -88,22 +90,27 @@ java -ea -cp "build/classes/main:build/classes/test:lib/*" \ ## What crosses the separate compilation boundary -The optimized IR owned by the object is compactly encoded in the `.simple` -section and fully reconstructed when read back in. The saved state includes -canonical declarations as well as optimized flow types. E.g. `int x=7` has -declared type `int` and initial value `7`. Struct field types (both declared -and optimized), function argument types (both declared and optimized), numeric -modes, store widths, and source locations also survive serialization. - -Each loaded `.simple` section restores its units into the shared `CompUnit` -tree, mirroring the original code layout. A dependency shared by several -objects uses the same `CompUnit`. Loaded aliases and function indices are -renumbered to avoid collisions; all the dense indices end up in the same -namespace. `GlobalBits` has the mapping from the imported file indices to the -local compilation indices; this remapping extends everywhere through the loaded -code, including recursive types that span several files. Importing skips -parsing the original source, but it still analysed and type checked with its -new callers. +Each source compilation unit gets its own object file: compiling `sys.smp` +produces `sys.o`, `sys/io.o`, `sys/libc.o`, and any other discovered classes. +Mutually dependent sources are compiled together and they output to separate +files with a common build timestamp. + +The object file has a compact encoding of the optimized IR in the `.simple` +section. Declarations and function summaries come first so they can be read +without reading all of the IR. The saved state includes canonical declarations +as well as optimized flow types. E.g. `int x=7` has declared type `int` and +initial value `7`. Struct field types (both declared and optimized), function +argument types (both declared and optimized), numeric modes, store widths, and +source locations also survive serialization. + +Each loaded `.simple` section restores `CompUnit`s into the shared tree, +mirroring the original code layout. A dependency shared by several objects +uses the same `CompUnit`. Loaded aliases and function indices are renumbered +to avoid collisions; all the dense indices end up in the same namespace. +`GlobalBits` has the mapping from the imported file indices to the local +compilation indices; this remapping extends everywhere through the loaded code, +including recursive types that span several files. Importing skips parsing the +original source, but loaded IR is still analyzed within its new context. `ParseAll` is the workhorse that discovers source and object dependencies. It tracks missing symbol references, looking them up in the search path one by one, @@ -117,8 +124,8 @@ compilation phases, including peepholes, Opto and TypeCheck. Dependencies between `CompUnit`s are recorded. An explicitly requested source file is always compiled. Before reusing another local object, `CompUnit` walks -its recorded dependencies and checks every source bundled into each local -object. A missing input or a newer source or dependency object forces parsing +its recorded dependencies and checks each local object's source. +A missing input or a newer source or dependency object forces parsing again, before saved types or IR are imported. This includes transitive dependencies: if A has inlined B, editing B's source invalidates A even while B's object is unchanged. A visited set lets this check follow cycles. @@ -129,33 +136,70 @@ cannot establish their compatibility. These checks are not a complete build driver: explicit requests still compile, and input hashes, compiler/ABI versions, and automatic relinking remain future work. -Loading currently works at the object granularity. Unrelated objects can stay -unloaded, but selecting an object loads its entire saved graph and follows its -recorded dependencies. Future work will look at loading sub-parts more -incrementally. +An unloaded function has a `FunNode`, `SummaryNode`, and `ReturnNode`. Its +summary supplies result, memory, and escape information; calls keep the usual +graph structure without requiring the body. Summaries cannot be inlined. +At an empty optimization worklist, an interesting local call can request its +callee's object using saved size information. The compiler loads the bodies, +reconciles identities, and analyzes them before deciding whether to inline. + +For `sys.io.p`, the compiler can leave `p` out of line without loading `io` IR. +Loading `io.o` makes its functions available, but references inside them carry +types without automatically loading other bodies. An unused imported function +does not cause speculative loading of its callees. Metadata discovery remains +conservative, and a requested object still loads all of its function bodies. + + + +## Using library code and shared state + +The compiler can use library IR to optimize a program while leaving the +library's functions and shared data in their own object files. Separate +compilation must also preserve when each class is initialized, even when +several files use it. + +For example, compiling `helloWorld` may load the body of `sys.io.p` to decide +whether to inline it or not. Inlined code becomes part of `helloWorld.o`. +Ifif it was not inlined that call remains using the function in `sys/io.o`. +Loading did not add another stand-alone copy of `p` to `helloWorld.o`. + +In any case, loaded or not, inlined or not, the initialization semantics of +`sys.io` is unchanged; this means we might need CLInit checks in the inlined +code, or where we load `p` from `sys.io`. +If we did load a bunch of IR, but then chose not to inline, that imported code +is still in our compiled graph. We use `Unlink` before code-gen to remove the +imported bodies. The not-inlined call sites will keep the target names around +for the system linker to eventually connect all the code. +Shared state follows the same idea as function calls. In the earlier example, +all calls within the program use the same `Counters.calls` field. The library +also supplies a shared `$init` flag so its class initializer runs once. +Importing types or loading IR does not run that initializer: execution must +reach a use that needs the class. -## Analysis, ownership, and initialization +A nested class's initializer first ensures that its enclosing class is +initialized, then sets its own flag and runs its body. -An imported function can participate in analysis without belonging to the -client's output. Loading the `io` library, with its `p` print function, means -that `p` is part of the analysis - but when writing out the `helloWorld` app, -`p` will not end up in the `helloWorld.o` file directly. It might be inlined -fully, or called out of line, but there won't be a stand-alone copy of it. +The IR represents an initialization check with a `CLInit` node. Simple saves +this form in the object file so the compiler can analyze it when compiling +a program that uses the library. For machine code, `Lower` turns the check +into a flag test and a conditional call; Eval2 performs the same steps +directly. Optimization can remove a check when the class is +already known to be initialized. -After optimization, `Serialize` saves ideal IR before `Lower` expands class -initialization. `Unlink` then detaches imported bodies for machine compilation -and removes analysis call edges. The client emits its own bodies and any code -copied into them by inlining; the -remaining calls refer to symbols supplied by the library object. +The compiler must also reject cycles in which class initializers depend on one +another. Simple keeps *function summaries* that list calls and classes that +may need initialization, so the compiler can check for cycles before loading +bodies. If a possible cycle appears, it loads all remaining bodies, optimizes, +and checks again. A constant returned by a some other code outside the cycle +can make a branch disappear and remove the cycle. -Class initialization follows the previous chapter's rules. Importing a type -does not initialize its class. Active uses retain `CLInit` checks until -lowering (unless optimization clears them out). The library supplies its -shared class object and flag. Initialization checks appear at all the active-touch -locations, whether local or remote; including source locations for error -reporting. +All required object files must be found before execution. Native code is +linked before the program starts. Eval2 can wait until a call needs a body +to decode its IR, but the object's types and dependencies have already been +read. These choices change when code is prepared; both execution paths use +the same shared state and class-initialization rules. ## Building and checking @@ -168,12 +212,14 @@ make tests CHAPTERS=chapter28b The suite includes the preceding constructor and escape regressions, imported constructors, initialization cycles across objects, shared static data, native -function thunks, and native library/client execution. Make also builds the -modular `sys` object used by the library tests. Clients can import that object -with `-L`; they do not need to parse the standard library's source again. -`IncrementalBuildTest` checks reuse, transitive edits, bundled cycles, missing +function thunks, and native programs linked with libraries. Make also builds +the modular `sys` objects used by the library tests. Programs can import +`sys.o` with `-L`, without parsing the standard library's source again. +`IncrementalBuildTest` checks reuse, transitive edits, cycles across objects, missing inputs, and changed library objects using controlled timestamps. It also compares native execution after an edit with a clean build. +`SelectiveLoadingTest` checks summarized calls, loading for inlining, native +link dependencies, and refinement of a potential initialization cycle. `make release` builds the launcher jar and standard library; `make view` starts the shared graph viewer. diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java index e65ef6d9..42e6695e 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -78,6 +78,7 @@ public class IterPeeps { CallEndNode cend; while( (cend=_workInline.pop()) != null) { if( cend.isDead() ) continue; + if( cend.loadForInline() ) { inlined=true; break; } byte inline = cend.maybeInline(); if( inline == -1 ) defer.add(cend); if( inline > 0 ) { diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java index 6c70b71d..45d65514 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -12,14 +12,14 @@ import java.util.*; // Build the inits-graph, a call-graph plus CLInits plus class parents. -// (1) Scan all functions f, building _edges[f][]: the set of <cinit> fcns from -// CompUnits from CLInitNodes, and the set of fcn call targets in f and the -// class parent. These are all reported as fidxs (ints). +// (1) Scan all functions f, building _edges[f][]: the set of <clinit> fcns +// from CompUnits from CLInitNodes, and the set of fcn call targets in f and +// the class parent. These are all reported as fidxs (ints). // -// (2) Walk the _edges graph using Tarjans SCC. Reject cycles containing more +// (2) Walk the _edges graph using Tarjans SCC. Reject cycles containing more // than one <clinit>. // -// (3) Report on <clinit> cycles +// (3) Report on <clinit> cycles, if any // public class ClassInitDependencies { private final CodeGen _code; @@ -56,12 +56,14 @@ public class ClassInitDependencies { // Return the outgoing init edge set for this function private static int[] walk( CodeGen code, FunNode fun, Ary<CFGNode> work, IntHashMap iset, BitSet visit, Ary<Parser.Lexer> sites) { + if( fun.summary()!=null ) return fun.summary()._classDependencyFIDXs; // Walk function body, looking for outgoing init edges assert iset .isEmpty(); // int hash set for de-dup assert visit.isEmpty(); // needs a visit set, because loops assert work .isEmpty(); // needs a worklist, because DAG, parallel explore paths - // Children classes always dependent on parents + // Keep the structural parent prerequisite even if a known-true flag + // folds the check in the child's body. Cycles still require diagnosis. if( fun.isClz() && fun._compunit._par != null ) iset.put(code.link(fun._compunit._par).sig().fidx(),1); @@ -123,6 +125,16 @@ public class ClassInitDependencies { return null; } + // A condition-producing helper outside the SCC can eliminate a cycle. + // Before reporting one, restore the full-IR precision of the original check. + Ary<CompUnit> cycleImports() { + Ary<CompUnit> units = new Ary<>(CompUnit.class); + if( check()==null ) return units; + for( FunNode fun : _code._linker ) + if( fun!=null && fun.summary()!=null && units.find(fun._compunit)==-1 ) units.add(fun._compunit); + return units; + } + // Every internal edge of an SCC belongs to a cycle. Print all of them: // stack order is not a path, and enumerating all cycle paths can explode. // This bookkeeping and formatting are only needed on an error. diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 8302ede6..07ca7e2b 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -259,6 +259,7 @@ public class CodeGen { // The Generic driver public CodeGen driver( Phase target, String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol, int dump ) { + _splitObjects = target.ordinal()>=Phase.Export.ordinal() && !inMemory; // Parse a Simple file, and for mentioned external symbols either load // from .o or recursively parse step(target, Phase.Parse, this::parse, dump); @@ -272,6 +273,8 @@ public class CodeGen { step(target, Phase.FinalizeIR, this::finalizeIR, dump); // Final error check - bad programs fail here step(target, Phase.TypeCheck, this::typeCheck, dump); + if( cpu==null && target.ordinal()>=Phase.Lower.ordinal() && _phase.ordinal()<Phase.Lower.ordinal() ) + loadAllIR(); // Ideal evaluation needs code for calls left out of line. // Save reloadable ideal IR for a later seperate compilation step(target, Phase.Serialize, () -> Serialize.forTarget(this,target,inMemory), dump); // Replace "fat" nodes with their exploded explicit IR; this can @@ -456,9 +459,12 @@ public class CodeGen { return externFunc(fidx); } - public boolean owns(FunNode fun) { - return fun._compunit != null && fun._compunit._src != null; - } + // Select which source CompUnit's object this encoding pass emits. + CompUnit _emitUnit; + boolean emits(CompUnit cu) { return cu!=null && cu._src!=null && (_emitUnit==null || _emitUnit==cu); } + boolean emits(FunNode fun) { return emits(fun._compunit); } + private boolean _splitObjects; + final LinkedHashMap<CompUnit,Encoding> _encodings = new LinkedHashMap<>(); // --------------------------- @@ -491,6 +497,82 @@ public class CodeGen { public CodeGen iterPostOpto() { return phase(Phase.IterPostOpto, _phase==Phase.Opto, () -> _iter.iterate(this)); } + // Materialize a requested inline candidate at an empty worklist, then + // reanalyze before CallEnd decides whether the real body should inline. + public void loadForInline(CompUnit cu) { + assert _phase==Phase.IterPostOpto && _iter._work.isEmpty(); + ParseAll.loadCompUnit(this,cu); + analyzeImports(); + } + + private void analyzeImports() { + Phase prior = _phase; + try { + _phase=Phase.Iter; + // Newly loaded calls can revive previously uncalled summaries. + // Restore their pessimistic inputs before solving; SCCP removes + // the unknown-caller edges again once all calls are available. + for( FunNode fun : _linker ) + if( fun!=null && fun.summary()!=null ) { + Opto.linkStart(this,fun); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) parm._type=parm._declaredType; + } + for( CompUnit cu : _compunits.values() ) { + ProjNode mem = cu._start.proj(1); + if( mem!=null && mem.iskeep() ) mem.unkeep(); + } + Iter.run(this); + _phase=Phase.Opto; + Opto.opto(this); + } finally { _phase=prior; } + } + + // Evaluation needs implementations even for calls left out of line. E.g., + // this code is being run by the evaluator, and so doesn't get a link step. + // If, instead, the code was going to run natively, it would first go + // through a link step which would resolve all these call sites to code + // generated in other object files. Since no link step, we need acess to + // that other code right now. + public void loadAllIR() { + boolean loaded = false; + for( CompUnit cu : _compunits.values() ) { + if( cu._src!=null || cu._obj==null ) continue; + ElfReader elf = getElf(cu._obj); + if( elf._nodes!=null ) continue; + ParseAll.loadCompUnit(this,cu); + loaded=true; + } + if( !loaded ) return; + analyzeImports(); + if( _phase.ordinal()<Phase.FinalizeIR.ordinal() ) return; + Phase prior = _phase; + try { + _phase=Phase.IterPostOpto; + _iter.iterate(this); + _phase=Phase.FinalizeIR; + FinalizeIR.run(this); + _phase=Phase.TypeCheck; + TypeCheck.run(this); + } finally { _phase=prior; } + } + + void resolveInitCycles() { + while( true ) { + Ary<CompUnit> units = new ClassInitDependencies(this).cycleImports(); + if( units.isEmpty() ) return; + for( CompUnit cu : units ) ParseAll.loadCompUnit(this,cu); + analyzeImports(); + Phase prior = _phase; + try { + _phase=Phase.IterPostOpto; + _iter.iterate(this); + _phase=Phase.FinalizeIR; + FinalizeIR.run(this); + } finally { _phase=prior; } + } + } + public CodeGen finalizeIR() { return phase(Phase.FinalizeIR, _phase==Phase.IterPostOpto, () -> FinalizeIR.run(this)); } // Root a surviving function without claiming that it has unknown callers. @@ -529,6 +611,7 @@ public class CodeGen { // --------------------------- public BAOS _serial; + final LinkedHashMap<CompUnit,BAOS> _serials = new LinkedHashMap<>(); public void serialize() { phase(Phase.Serialize, _phase==Phase.TypeCheck, () -> Serialize.serialize(this)); } @@ -576,6 +659,13 @@ public class CodeGen { return phase(Phase.Schedule, (_phase==Phase.Unlink || _phase==Phase.Select), () -> GlobalCodeMotion.buildCFG(this)); } + // Evaluation branches from checked ideal IR directly to scheduling. + // CLInit remains an executable ideal operation; no Lower or Select pass. + public CodeGen scheduleForEval() { + return phase(Phase.Schedule, (_phase==Phase.TypeCheck || _phase==Phase.Serialize), + () -> _cfg=GlobalCodeMotion.forEval(this,_start,_stop)); + } + // --------------------------- // Local (basic block) scheduler phase, a classic list scheduler public CodeGen localSched() { return phase(Phase.LocalSched, _phase==Phase.Schedule, () -> ListScheduler.sched(this)); } @@ -604,7 +694,17 @@ public class CodeGen { // --------------------------- // Encoding public Encoding _encoding; - public CodeGen encode() { return phase(Phase.Encoding, _phase==Phase.RegAlloc, () -> _encoding = new Encoding(this).encode()); } + public CodeGen encode() { return phase(Phase.Encoding, _phase==Phase.RegAlloc, () -> { + if( !_splitObjects ) { _encoding = new Encoding(this).encode(); return; } + try { + for( CompUnit cu : _serials.keySet() ) { + _emitUnit = cu; + Encoding enc = new Encoding(this).encode(); + _encodings.put(cu,enc); + if( cu._fname.equals(_srcName) ) _encoding = enc; + } + } finally { _emitUnit = null; } + }); } // --------------------------- // Exporting to external formats @@ -612,7 +712,31 @@ public class CodeGen { public CodeGen exportELF( boolean inMemory, boolean emitEntrySymbol ) { return phase(Phase.Export, _phase==Phase.Encoding, () -> { if( inMemory ) new LinkMem(this).link(_encoding); - else _elf = new ElfWriter(this).export(emitEntrySymbol); + else { + if( _serials.isEmpty() ) + throw new IllegalStateException("ELF export needs ideal IR: request Export from the driver, or Serialize before Lower"); + Encoding entry = _encoding; + BAOS serial = _serial; + try { + if( _encodings.isEmpty() ) for( CompUnit cu : _serials.keySet() ) { + _emitUnit=cu; + _encodings.put(cu,new Encoding(this).encode()); + } + for( var e : _encodings.entrySet() ) { + _emitUnit = e.getKey(); + _encoding = e.getValue(); + _serial = _serials.get(_emitUnit); + _elf = new ElfWriter(this).export(emitEntrySymbol && _emitUnit._fname.equals(_srcName)); + } + // Mutually dependent units built together must not become + // stale merely because their files were written in sequence. + long time = System.currentTimeMillis(); + for( CompUnit cu : _encodings.keySet() ) { + File obj = new File(_buildDir+"/"+cu._fname+".o"); + if( !obj.setLastModified(time) ) throw new IllegalStateException("Cannot timestamp "+obj); + } + } finally { _emitUnit=null; _encoding=entry; _serial=serial; } + } }); } @@ -631,6 +755,7 @@ public class CodeGen { // State machine elements; the outermost element is _externPaths private int _extPathIdx; // Search index into the extern path list private final Ary<File> _files = new Ary<>(File.class); // Files in the current extern path being searched + private final HashSet<File> _seenFiles = new HashSet<>(); private int _extFileIdx; // Index into _files public ElfReader findExternalSimple( String name ) { @@ -685,6 +810,12 @@ public class CodeGen { // Publish definitions only; referenced classes belong to other objects. for( String fname : elf._units ) _externSymbols.putIfAbsent(Parser.addClzPrefix(fname.replace('/','.')),elf); + // A -L object can name dependencies alongside itself. They + // need metadata discovery even when no directory was supplied. + for( String dep : elf._deps ) { + File file = elf.dependencyFile(dep); + if( file.isFile() ) addExtFile(file); + } break; default: throw Utils.TODO("should not reach here"); @@ -709,12 +840,17 @@ public class CodeGen { for( File f : dir.listFiles() ) fillExtFiles(f); else if( dir.getName().endsWith(".o") ) - _files.add(dir); + addExtFile(dir); + } + + private void addExtFile(File file) { + file=file.toPath().toAbsolutePath().normalize().toFile(); + if( _seenFiles.add(file) ) _files.add(file); } // Map from object file names to ElfReaders public final HashMap<String,ElfReader> _elfs = new HashMap<>(); - ElfReader getElf(File f) { + public ElfReader getElf(File f) { ElfReader elf = _elfs.get(f.getPath()); if( elf != null ) return elf; diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java index 10720300..1f0e803d 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java @@ -38,6 +38,8 @@ public class ElfReader { public TypeStruct[] _pubTypes; // Nodes read in this Elf public Ary<Node> _nodes; + Serialize.TypeRead _types; + FunctionSummary[] _functions; // Load an Elf file (mostly lazily) public static ElfReader load( File f, CompUnit cu ) { @@ -67,7 +69,7 @@ public class ElfReader { if( ".simple".equals(sec._name) ) simple = sec; _simple = simple; - _bais = new BAOS(_buf, (int)_simple._offset); + _bais = _simple==null ? null : new BAOS(_buf, (int)_simple._offset); } // For Serialize self-test @@ -92,6 +94,12 @@ public class ElfReader { Serialize.read_public_strs(this); } + File dependencyFile(String unit) { + File root = _file; + for( String part : _units[0].split("/") ) root=root.getParentFile(); + return new File(root,unit+".o"); + } + // Loads the entire IR public TypeStruct loadSimple(CodeGen code) { Serialize.readAll(code, this, code._aliases, code._fidxs, code._rpcs); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java index 5a280723..fcf5c287 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -193,12 +193,13 @@ public class ElfWriter { for( Node stopcu : stop._inputs ) { for( Node ret : stopcu._inputs ) { FunNode fun = ((ReturnNode)ret).fun(); - if( !_code.owns(fun) ) + if( !_code.emits(fun) ) continue; int end = enc.opStart(fun.ret()) + enc.opLen(fun.ret()); long value = enc.opStart(fun); long size = end - value; - if( fun._name != null ) { // Anonymous functions have no name + // Stable FIDX names are exported separately below. + if( fun._name != null && !fun._name.equals(_code._fidxs.symbol(fun.sig().fidx())) ) { // The C runtime owns `main` and adapts argc/argv into // a normal Simple array. Keep the Simple function on // its native ABI under a private entry symbol. @@ -217,7 +218,7 @@ public class ElfWriter { FunNode clinit = null; String entryName = _code.entryClinitName(); for( FunNode fun : _code._linker ) - if( fun != null && _code.owns(fun) ) { + if( fun != null && _code.emits(fun) ) { if( "main".equals(fun._name) ) return; // encodeFunctions exported this as simple_main if( entryName.equals(fun._name) ) @@ -368,7 +369,7 @@ public class ElfWriter { // anonymous functions which have no source-level exported name. HashMap<String,Integer> dataSymbols=new HashMap<>(); for( FunNode fun : _code._linker ) - if( fun!=null && !fun.isDead() && _code.owns(fun) && enc.opStart(fun)>=0 ) { + if( fun!=null && !fun.isDead() && _code.emits(fun) && enc.opStart(fun)>=0 ) { String name=_code._fidxs.symbol(fun.sig().fidx()); dataSymbols.put(name,symbols.symbol(name,text._index,SYM_BIND_GLOBAL,SYM_TYPE_FUNC,enc.opStart(fun),0)); } @@ -446,7 +447,7 @@ public class ElfWriter { assert out.position() == size; - String objName = _code._buildDir + "/" + _code._srcName + ".o"; + String objName = _code._buildDir + "/" + (_code._emitUnit==null ? _code._srcName : _code._emitUnit._fname) + ".o"; File file = new File(objName); if( file.getParentFile()!=null ) file.getParentFile().mkdirs(); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 06bf14f5..067f431a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -162,7 +162,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // Source is a Call, destination in the Fun. public Encoding relo( CallNode call ) { FunNode fun = _code.link(call.tfp()); - if( fun != null && !_code.owns(fun) ) + if( fun != null && !_code.emits(fun) ) _externals.put(call,fun._name); else _internals.put(call,fun); @@ -176,7 +176,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { String nativeName = _code.externFunc(tfp.fidx()); if( nativeName!=null ) return external(fptr,nativeName); FunNode fun = _code.link(tfp); - if( fun != null && !_code.owns(fun) ) + if( fun != null && !_code.emits(fun) ) _externals.put(fptr,fun._name); else _internals.put(fptr,fun); @@ -249,7 +249,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { FunNode entry = null; String entryName = _code.entryClinitName(); for( FunNode fun : _code._linker ) { - if( fun != null && !fun.isDead() && _code.owns(fun) ) { + if( fun != null && !fun.isDead() && _code.emits(fun) ) { if( fun.isClz() ) { if( fun._name.equals(entryName) ) entry = fun; diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FunctionSummary.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FunctionSummary.java new file mode 100644 index 00000000..6cd4035d --- /dev/null +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/FunctionSummary.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +// The small, eagerly readable part of a function's serialized implementation. +record FunctionSummary(TypeFunPtr sig, TypeTuple state, String name, int size, int[] classDependencyFIDXs) { + void install(CodeGen code, CompUnit cu) { + FunNode fun = new FunNode(null,sig,name,cu,null,cu._start); + fun._approxUIDs=size; + fun.init(); + // First user stays in output slot zero until the summary is removed. + SummaryNode body = new SummaryNode(state,classDependencyFIDXs,fun); + ParmNode rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,code.con(TypeRPC.BOT)).init(); + ParmNode mem = new ParmNode("$mem",1,TypeMem.BOT,fun,cu._start.proj(1)).init(); + body.addDef(mem); + for( int i = 0; i<sig.nargs(); i++ ) + body.addDef(new ParmNode("arg"+i,i+2,sig.arg(i),fun,code.con(sig.arg(i))).init()); + body.init(); + Node ctrl = new CProjNode(body,0,"ctrl").init(); + Node memory = new ProjNode(body,1,"mem").init(); + Node value = new ProjNode(body,2,"value").init(); + ReturnNode ret = new ReturnNode(ctrl,memory,value,rpc,fun).init(); + fun.setRet(ret); + cu._stop.addDef(ret); + code.link(fun); + } +} diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 09eb8d33..8708818b 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -9,31 +9,47 @@ import java.util.*; public abstract class GlobalCodeMotion { + // Ideal execution needs a schedule, but neither CLInit lowering nor + // interprocedural optimization. Each loaded object is prepared once. + public static Ary<CFGNode> forEval(CodeGen code, StartNode start, StopNode stop) { + Ary<FunNode> funs = Unlink.forEval(start,stop); + start.buildLoopTree(funs,stop); + return buildCFG(code,start,stop); + } + // Arrange that the existing isCFG() Nodes form a valid CFG. The // Node.use(0) is always a block tail (either IfNode or head of the // following block). There are no unreachable infinite loops. public static void buildCFG( CodeGen code ) { + code._cfg = buildCFG(code,code._start,code._stop); + } + + // Schedule one graph, including an object loaded while Eval2 is running. + // Other graphs (and their active evaluation frames) are left untouched. + public static Ary<CFGNode> buildCFG(CodeGen code, StartNode start, StopNode stop) { Ary<CFGNode> rpo = new Ary<>(CFGNode.class); - _rpo_cfg(null, code._start, code.visit(), rpo); + _rpo_cfg(null, start, code.visit(), rpo); // Reverse in-place for( int i=0; i< rpo.size()>>1; i++ ) rpo.swap(i,rpo.size()-1-i); - // Set global CFG - code._cfg = rpo; - - schedEarly(code); + schedEarly(code,start,rpo); // Break up shared global constants by functions - breakUpGlobalConstants(code._start); + breakUpGlobalConstants(start); code._visit.clear(); - schedLate(code); + schedLate(code,stop); + return rpo; } // Post-Order of CFG private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, Ary<CFGNode> rpo) { if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) ) return; // Been there, done that + // A shared dead-control node can also reach an unloaded function's + // Return. Its wrapper is a dispatch target, not executable code. + if( cfg instanceof FunNode fun && fun.summary()!=null || + cfg instanceof ReturnNode ret && ret.fun().summary()!=null ) return; assert !( def instanceof ReturnNode && use instanceof CallEndNode ); // All calls unwired now assert !( def instanceof CallNode && use instanceof FunNode ); // All calls unwired now visit.set(cfg._nid); @@ -59,8 +75,8 @@ public abstract class GlobalCodeMotion { for( Node use : con._outputs.asAry() ) { if( use==null || globals.containsKey(use) ) continue; FunNode fun = useFun(use); - if( fun==null ) continue; // Global metadata has no function owner. - assert CodeGen.CODE._mach==null || CodeGen.CODE.owns(fun); // Ideal evaluation includes imported bodies. + if( fun==null || fun.summary()!=null ) continue; // Metadata has no executable owner. + assert CodeGen.CODE._mach==null || fun.isFromSource(); // Ideal evaluation includes imported bodies. var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); Node copy = cloneGlobal(con,fun,globals,local); for( int i=0; i<use.nIns(); i++ ) @@ -98,36 +114,36 @@ public abstract class GlobalCodeMotion { // (except at loops). Since defs are visited first - and hoisted as early // as possible, when we come to a use we place it just after its deepest // input. - private static void schedEarly(CodeGen code) { + private static void schedEarly(CodeGen code, StartNode start, Ary<CFGNode> cfgs) { // Reverse Post-Order on CFG - for( CFGNode cfg : code._cfg ) { + for( CFGNode cfg : cfgs ) { cfg.loopDepth(); for( Node n : cfg._inputs ) - _schedEarly(n,code ); + _schedEarly(n,code,start ); // In dead infinite loops, entire code blocks may be unreachable // from below. Reach down from the CFG to their Phis so their // inputs are scheduled too. if( cfg instanceof RegionNode ) for( Node phi : cfg._outputs ) if( phi instanceof PhiNode ) - _schedEarly(phi,code ); + _schedEarly(phi,code,start ); } } - private static void _schedEarly(Node n, CodeGen code) { + private static void _schedEarly(Node n, CodeGen code, StartNode start) { if( n==null || code._visit.get(n._nid) ) return; // Been there, done that - assert !(n instanceof CFGNode); + assert !(n instanceof CFGNode) : n.getClass().getSimpleName()+"#"+n._nid+" outside scheduled CFG"; code._visit.set(n._nid); // Schedule inputs first, except Phis: following their backedges would // enter a data cycle before its control has been scheduled. for( Node def : n._inputs ) if( def!=null && !(def instanceof PhiNode) ) - _schedEarly(def,code); + _schedEarly(def,code,start); // An existing edge 0 already supplies control (or a Phi/Proj binding). if( n.in(0)==null ) { // Schedule at deepest input - CFGNode early = code._start; // Maximally early, lowest idepth + CFGNode early = start; // Maximally early, lowest idepth for( int i=1; i<n.nIns(); i++ ) if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() ) early = n.in(i).cfg0(); // Latest/deepest input @@ -136,7 +152,7 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ - private static void schedLate( CodeGen code ) { + private static void schedLate( CodeGen code, StopNode stop ) { CFGNode[] late = new CFGNode[code.UID()]; Node[] ns = new Node[code.UID()]; // Record Load NIDs at all their CFG block choices, then check against @@ -144,7 +160,7 @@ public abstract class GlobalCodeMotion { int[] anti = new int[code.UID()]; Ary<Node> antideps = new Ary<>(Node.class); // Breadth-first scheduling - breadth(code._stop,ns,late,anti, antideps); + breadth(stop,ns,late,anti, antideps); // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java index c5120370..a9f4206a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -14,8 +14,9 @@ abstract class Iter { // can only be removed, never added. Seed the complete graph once. boolean hasImports = code._externPaths != null; code._start.walk(n -> { - if( !(n instanceof ConstantNode) ) - n._type = hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); + // Type import can reconcile a constant's declaration. + n._type = n instanceof ConstantNode ? n.compute() + : hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); code.add(n); return null; }); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java index b6b3a22c..3b1d3182 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java @@ -108,8 +108,12 @@ public abstract class ListScheduler { // List schedule every block public static void sched( CodeGen code ) { + sched(code._cfg); + } + + public static void sched(Ary<CFGNode> cfgs) { XS.clear(); - for( CFGNode bb : code._cfg ) + for( CFGNode bb : cfgs ) if( bb.blockHead() ) local(bb,false); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 3b3f9f19..dc5742f7 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -142,7 +142,7 @@ abstract public class Opto { // Function is now reachable by unknown callers through Start. The // default inputs must therefore use conservative declared types. - private static void linkStart( CodeGen code, FunNode fun ) { + static void linkStart( CodeGen code, FunNode fun ) { assert !fun.isDead(); StartCUNode start = fun._compunit._start; if( !fun.unknownCallers() ) { diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index d7c0f7e2..016e4062 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -103,7 +103,7 @@ public abstract class ParseAll { // Load all pre-compiled CompUnits for( CompUnit cu : NEEDS_LOAD ) - loadCompUnit(code,cu); + loadSummaries(code,cu); // Many types will have been declared cyclically either internally or // across multiple compilation units. @@ -239,7 +239,7 @@ public abstract class ParseAll { try { NEEDS_LOAD.add(cunit); // Load dependent classes - ElfReader elf = ElfReader.load(cunit._obj,cunit); + ElfReader elf = code.getElf(cunit._obj); elf.loadPublicSymbols(); // Register bundled definitions before resolving dependencies or IR. for( String fname : elf._units ) @@ -270,12 +270,26 @@ public abstract class ParseAll { return elf == null ? null : elf._file; } - private static void loadCompUnit(CodeGen code, CompUnit cunit) { + private static void loadSummaries(CodeGen code, CompUnit cu) { + ElfReader elf = code.getElf(cu._obj); + elf.loadPublicTypes(code); + cu._clz = elf._clz; + cu.setStart(code); + new ProjNode(cu._start,1,"$mem").init(); + for( FunctionSummary summary : elf._functions ) summary.install(code,cu); + } + + public static void loadCompUnit(CodeGen code, CompUnit cunit) { // Expecting a previously compiled object file assert cunit._obj != null; // Extract published symbols and put them in the internal tables; // cross-references will pick them up there. - ElfReader elf = ElfReader.load(cunit._obj,cunit); + ElfReader elf = code.getElf(cunit._obj); + if( elf._nodes!=null ) return; + StartCUNode oldStart = cunit._start; + StopCUNode oldStop = cunit._stop; + ProjNode oldMem = oldStart==null ? null : oldStart.proj(1); + if( oldMem!=null && oldMem.iskeep() ) oldMem.unkeep(); elf.loadSimple(code); cunit._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cunit._cname)); StartNode lstart = (StartNode)elf._nodes.at(0); @@ -291,7 +305,17 @@ public abstract class ParseAll { for( Node ret : stop._inputs ) { FunNode fun = ((ReturnNode)ret).fun(); + FunNode old = code._link(fun.sig().fidx()); code.link(fun); + if( old!=null && old.summary()!=null && !old.isDead() ) { + old.ret().keep(); + for( int i = 1; i<old.nIns(); i++ ) + if( old.in(i) instanceof CallNode call ) { + call.unlink(old,i--); + call.link(fun); + } + old.ret().unkeep().subsume(fun.ret()); + } } } @@ -299,6 +323,12 @@ public abstract class ParseAll { for( Node lstopcu : lstop._inputs ) code._stop.addDef(lstopcu); lstart.subsume(code._start); + if( oldStart!=null && oldStart!=cunit._start ) { + int idx = code._stop._inputs.find(oldStop); + if( idx!=-1 ) code._stop.delDef(idx); + oldStart.subsume(cunit._start); + } + code.addAll(elf._nodes); // Add the new top-level loaded class Parser.TYPES.put(cunit._clz._name,cunit._clz); @@ -401,7 +431,7 @@ public abstract class ParseAll { } catch( IOException ioe ) { throw new RuntimeException(ioe); } - ElfReader typedElf = ElfReader.load(cunit._obj,cunit); + ElfReader typedElf = code.getElf(cunit._obj); if( typedElf != null ) typedElf.loadPublicTypes(code); TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); if( clz == null ) diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 5a74ded2..9984d99d 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -16,28 +16,30 @@ abstract public class Serialize { } static void serialize( CodeGen code ) { + // Anonymous functions also need names when another object refers to them. + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() && fun._name==null ) + fun._name=code._fidxs.symbol(fun.sig().fidx()); + ArrayList<CompUnit> units = new ArrayList<>(code._compunits.values()); + units.sort(Comparator.comparing(cu -> cu._fname)); + for( CompUnit cu : units ) { + if( cu._src==null ) continue; + BAOS serial = serialize(code,cu); + code._serials.put(cu,serial); + if( cu._fname.equals(code._srcName==null ? "Test" : code._srcName) ) code._serial=serial; + } + } - // Get all Nodes in a sane order - Ary<Node> nodes = nodeOrder(code); - - // Array of dependent file names + private static BAOS serialize(CodeGen code, CompUnit top) { + Ary<Node> nodes = nodeOrder(code,top); HashSet<String> xdeps = new HashSet<>(); - for( CompUnit cu : code._compunits.values() ) { - if( cu._deps != null ) - for( CompUnit cudep : cu._deps ) - xdeps.add(cudep._fname); - } - String[] deps = xdeps.toArray(new String[xdeps.size()]); + // Retain build dependencies even when their calls were inlined away. + if( top._deps!=null ) for( CompUnit dep : top._deps ) + if( dep!=top ) xdeps.add(dep._fname); + if( top._par!=null ) xdeps.add(top._par._fname); + String[] deps = xdeps.toArray(new String[0]); Arrays.sort(deps); - Ary<String> owned = new Ary<>(String.class); - for( CompUnit cu : code._compunits.values() ) - if( cu._src!=null ) owned.add(cu._fname); - String[] units = owned.asAry(); - Arrays.sort(units); - - // Top-level clazz being reported - String topName = code._srcName == null ? "Test" : code._srcName; - CompUnit top = code._compunits.get(topName); + String[] units = {top._fname}; TypeStruct clz = top._clz; // Preserve which same-named structs are the source-level declarations. @@ -67,7 +69,7 @@ abstract public class Serialize { // --- Expensive bijection assert // Record serialized IR for later ELF writing - code._serial = baos; + return baos; } // -------------------------------------------------- @@ -90,6 +92,7 @@ abstract public class Serialize { // Count unique Types var types = new HashMap<Type,Integer>(); + IdentityHashMap<FunNode,TypeTuple> summaries = new IdentityHashMap<>(); // Count published types *first*, so can align with published strings types.put(Type.TOP,0); types.put( clz, types.size() ); @@ -103,7 +106,18 @@ abstract public class Serialize { for( Node n : nodes ) { n._type.gather(types); if( n instanceof CallEndNode cend ) cend._rpc.gather(types); - if( n instanceof FunNode fun ) fun.sig().gather(types); + if( n instanceof FunNode fun ) { + fun.sig().gather(types); + TypeTuple state = (TypeTuple)fun.ret()._type; + TypeMem mem = (TypeMem)state.mem(); + // Retention can happen on a path that never returns. The + // unit's escape summary includes those native-call effects. + TypeMem escaped = (TypeMem)((TypeTuple)fun._compunit._stop._type).mem(); + mem=mem.makeFrom(XInt.meet(mem._escFs,escaped._escFs),XInt.meet(mem._escAs,escaped._escAs)); + state=state.makeFrom(1,mem); + summaries.put(fun,state); + state.gather(types); + } if( n instanceof ParmNode parm ) parm._declaredType.gather(types); if( n instanceof TypeNode con ) con._con .gather(types); } @@ -205,6 +219,22 @@ abstract public class Serialize { } + // Function summaries precede the graph, so declarations and call + // behavior are available without allocating the implementation nodes. + ClassInitDependencies init = new ClassInitDependencies(CodeGen.CODE); + int nfuncs = 0; + for( Node n : nodes ) if( n instanceof FunNode ) nfuncs++; + baos.packed4(nfuncs); + for( Node n : nodes ) if( n instanceof FunNode fun ) { + baos.packed2(types.get(fun.sig())); + baos.packed2(types.get(summaries.get(fun))); + baos.packed2(fun._name==null ? 0 : strs.get(fun._name)); + baos.packed4(fun._approxUIDs); + int[] edges = init._edgess[fun.sig().fidx()]; + baos.packed4(edges==null ? 0 : edges.length); + if( edges!=null ) for( int edge : edges ) baos.packed4(edge); + } + // D - Write the nodes. Since this is expected to be the bulk of the // data, we might want to explore various options. @@ -306,6 +336,7 @@ abstract public class Serialize { record TypeRead(Type[] types, String[] strs, GlobalBits fileAliases, GlobalBits fileFidxs, GlobalBits fileRpcs) {} static TypeRead readTypes( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { + if( elf._types!=null ) return elf._types; BAOS bais = elf._bais; // Initialize the mapping from bits/tags to types Type.TAGOFFS(); @@ -384,7 +415,17 @@ abstract public class Serialize { TypeStruct ts = elf._pubTypes[i] = (TypeStruct)types[pubTypeIds[i]]; Parser.TYPES.put(ts._name,ts); } - return new TypeRead(types,strs,fileAliases,fileFidxs,fileRpcs); + elf._functions = new FunctionSummary[bais.packed4()]; + for( int i = 0; i<elf._functions.length; i++ ) { + TypeFunPtr sig = (TypeFunPtr)types[bais.packed2()]; + TypeTuple state = (TypeTuple)types[bais.packed2()]; + String name = strs[bais.packed2()]; + int size = bais.packed4(); + int[] edges = new int[bais.packed4()]; + for( int j = 0; j<edges.length; j++ ) edges[j]=fidxs.map(fileFidxs,bais.packed4()); + elf._functions[i]=new FunctionSummary(sig,state,name.isEmpty() ? fidxs.symbol(sig.fidx()) : name,size,edges); + } + return elf._types = new TypeRead(types,strs,fileAliases,fileFidxs,fileRpcs); } static void readAll( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { @@ -394,76 +435,83 @@ abstract public class Serialize { String[] strs = tread.strs(); GlobalBits fileAliases = tread.fileAliases(); - // D - Read the nodes - - // Number of nodes - int num = bais.packed4(); - // Packed array of nodes - Ary<Node> nodes = new Ary<>(Node.class); - CompUnit cu = null; - for( int i=0; i<num; i++ ) { - Node.Tag tag = Node.Tag.VALS[bais.packed1()]; - Type t = types[bais.packed2()]; - Node n = tag.make(bais,strs,types,fileAliases,aliases); - n._type = t; - nodes.push(n); - // A little extra for FunNodes - if( n instanceof StartCUNode startcu ) { - cu = code._compunits.get(startcu._fname==null ? (code._srcName==null ? "Test" : code._srcName) : startcu._fname); - assert cu != null; - } - if( n instanceof StopCUNode stopcu ) { - cu = null; - } - if( n instanceof FunNode fun ) { - assert cu != null; - fun._compunit = cu; - } - if( n instanceof ExternNode ext && ext._con instanceof TypeFunPtr tfp && tfp.isConstant() ) { - String old = code.externFunc(tfp.fidx()); - if( old == null ) - code.externFunc(tfp.fidx(), ext._extern); - else - assert old.equals(ext._extern); + CodeGen.Phase prior = code._phase; + code._phase=CodeGen.Phase.Parse; // Constructors must tolerate an incomplete graph. + try { + // D - Read the nodes + + // Number of nodes + int num = bais.packed4(); + // Packed array of nodes + Ary<Node> nodes = new Ary<>(Node.class); + CompUnit cu = null; + for( int i = 0; i<num; i++ ) { + Node.Tag tag = Node.Tag.VALS[bais.packed1()]; + Type t = types[bais.packed2()]; + Node n = tag.make(bais,strs,types,fileAliases,aliases); + n._type = t; + nodes.push(n); + // A little extra for FunNodes + if( n instanceof StartCUNode startcu ) { + cu = code._compunits.get(startcu._fname==null ? (code._srcName==null ? "Test" : code._srcName) : startcu._fname); + assert cu != null; + } + if( n instanceof StopCUNode stopcu ) { + cu = null; + } + if( n instanceof FunNode fun ) { + assert cu != null; + fun._compunit = cu; + if( fun._name==null || fun._name.isEmpty() ) fun._name=fidxs.symbol(fun.sig().fidx()); + } + if( n instanceof ExternNode ext && ext._con instanceof TypeFunPtr tfp && tfp.isConstant() ) { + String old = code.externFunc(tfp.fidx()); + if( old == null ) + code.externFunc(tfp.fidx(), ext._extern); + else + assert old.equals(ext._extern); + } } - } - // Node edges - for( Node n : nodes ) { - int len = n.nIns(); - for( int i=0; i<len; i++ ) { - int idx = bais.packed2(); - Node def = idx==0 ? null : nodes.at(idx-1); - // MemMerge precise aliases are encoded by their input slot. - // Remap populated file-local slots into this compilation's - // local alias numbering; null holes carry no identity. - int local = i; - if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) { - if( def == null ) continue; - local = aliases.map(fileAliases,i); + // Node edges + for( Node n : nodes ) { + int len = n.nIns(); + for( int i = 0; i<len; i++ ) { + int idx = bais.packed2(); + Node def = idx==0 ? null : nodes.at(idx-1); + // MemMerge precise aliases are encoded by their input slot. + // Remap populated file-local slots into this compilation's + // local alias numbering; null holes carry no identity. + int local = i; + if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) { + if( def == null ) continue; + local = aliases.map(fileAliases,i); + } + n.setDefX(local,def); + // Call's output[0] is always the CallEnd + if( n instanceof CallEndNode cend && i==0 ) { + var outs = cend.call()._outputs; + outs.swap(0,outs._len-1); + } } - n.setDefX(local,def); - // Call's output[0] is always the CallEnd - if( n instanceof CallEndNode cend && i==0 ) { - var outs = cend.call()._outputs; - outs.swap(0,outs._len-1); + // A little extra for FunNodes + if( n instanceof FunNode fun ) { + // Return is hooked like an edge + ReturnNode ret = (ReturnNode)nodes.at(bais.packed2()-1); + fun.setRet(ret); + ret._fun = fun; } } - // A little extra for FunNodes - if( n instanceof FunNode fun ) { - // Return is hooked like an edge - ReturnNode ret = (ReturnNode)nodes.at(bais.packed2()-1); - fun.setRet(ret); - ret._fun = fun; - } - } - // Add edge from Start to Stop - StartNode start = (StartNode)nodes.at(0); - StopNode stop = (StopNode)nodes.last(); - start.setDef(1,stop); - - assert check(code,nodes); - elf._nodes = nodes; + // Add edge from Start to Stop + StartNode start = (StartNode)nodes.at(0); + StopNode stop = (StopNode)nodes.last(); + start.setDef(1,stop); + + // A body materialized after SCCP joins a different analysis context. + // Its saved types are reset and checked by the ensuing fixed-point solve. + assert prior!=CodeGen.Phase.Parse || check(code,nodes); + elf._nodes = nodes; + } finally { code._phase=prior; } } // Check loaded types and nodes are consistent @@ -501,16 +549,22 @@ abstract public class Serialize { BitSet visit = code.visit(); Ary<Node> nodes = new Ary<>(Node.class); visit.set(code._stop._nid); + // Return-linked function constants are global. Do not walk through + // them from one function into stores or calls in a different unit. + for( Node n : code._start._outputs ) if( n!=null && n.isConst() ) visit.set(n._nid); // Walk all listed functions, in this single compilation unit for( FunNode fun : code._linker ) if( fun!=null && !fun.isDead() && fun._compunit == cu ) _funWalk(fun,nodes,visit); + for( Node n : code._start._outputs ) if( n!=null && n.isConst() ) visit.clear(n._nid); + // Just constants used by the listed functions Ary<Node> cons = new Ary<>(Node.class); cons.add(code._start); for( Node n : code._start._outputs ) { - if( n instanceof ConstantNode con && !visit.get(con._nid) ) { + Node con = n; + if( con.isConst() && !visit.get(con._nid) ) { for( Node use : con.outs() ) { // PtrToInt is another zero-code value rooted at a global // constant. Its array-body Add is the value used by the diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java index 616753d4..a4147576 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java @@ -37,7 +37,7 @@ public final class StaticData { StaticData(Encoding enc) { this.enc=enc; - prefix=enc._code.entryClinitName()+"$DATA$"; + prefix=(enc._code._emitUnit==null ? enc._code.entryClinitName() : enc._code._emitUnit._cname)+"$DATA$"; } static boolean isClass(Type t) { @@ -68,7 +68,7 @@ public final class StaticData { String symbol=clz ? ((TypeStruct)t)._name.substring(Parser.CLZ.length())+".$class" : t instanceof TypeFunPtr fp ? functionSymbol(fp) : prefix+objects.size(); ObjectData obj=new ObjectData(t,symbol,!clz && (!(t instanceof TypeStruct ts) || ts.isConstant()), - owner!=null && owner._src==null); + owner!=null && !enc._code.emits(owner)); objects.put(key,obj); // Register before following fields: class objects may refer to each other. if( !obj.external && t instanceof TypeStruct ts ) @@ -96,7 +96,7 @@ public final class StaticData { // Definitions belong to their compilation unit, even if every local use folded. ArrayList<CompUnit> units=new ArrayList<>(enc._code._compunits.values()); units.sort(Comparator.comparing(cu -> cu._cname==null ? "" : cu._cname)); - for( CompUnit cu : units ) if( cu._src!=null && cu._clz!=null ) object(cu._clz); + for( CompUnit cu : units ) if( enc._code.emits(cu) && cu._clz!=null ) object(cu._clz); for( ObjectData obj : entries() ) { if( obj.external ) continue; BAOS bits=obj.readOnly ? enc._cpool : enc._sdata; @@ -157,7 +157,7 @@ public final class StaticData { if( ext!=null ) address=enc.externalAddress(ext); else if( fun==null ) address=address(object(fp),cpool,sdata); else { - if( !enc._code.owns(fun) ) throw new IllegalArgumentException("Unlinked function "+functionSymbol(fp)); + if( !fun.isFromSource() ) throw new IllegalArgumentException("Unlinked function "+functionSymbol(fp)); address=enc.opStart(fun); } } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index 9b4b0995..fb82ef0c 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -9,6 +9,7 @@ import com.seaofnodes.simple.util.Ary; // obligations. Queue surviving CLInits during the same walk for Lower's Iter. abstract class TypeCheck { static void run(CodeGen code) { + code.resolveInitCycles(); // Check for class-init cycles first; such a cycle can prevent other // things from resolving types. The dependency graph is temporary. String clzInitCycle = new ClassInitDependencies(code).check(); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java index fb1c4a6f..17f8107a 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java @@ -1,20 +1,66 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.util.Ary; // Discard call-graph edges after LoopTree. Machine selection keeps only this // object's bodies; ideal evaluation keeps imports so their calls can execute. abstract class Unlink { + // Disconnect compiler-only interprocedural edges before scheduling. Keep + // signatures in the linker; runtime calls resolve FIDXs, not graph edges. + static Ary<FunNode> forEval(StartNode start, StopNode stop) { + Ary<Node> nodes = new Ary<>(Node.class); + start.walk(n -> { nodes.add(n); return null; }); + Ary<FunNode> funs = new Ary<>(FunNode.class); + for( Node n : nodes ) + if( n instanceof FunNode fun ) { + fun.ret().keep(); + if( fun.summary()==null ) funs.add(fun); + } + for( Node n : nodes ) { + if( n instanceof CallNode call ) call.unlink_all(); + if( n instanceof FunPtrNode ptr && ptr.ret()!=null ) ptr.setDef(1,null); + } + for( FunNode fun : funs ) { + // Keep bodies rooted for scheduling after their callers detach. + if( fun.nIns()==1 ) { + fun.addDef(fun._compunit._start); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) { + ConstantNode con = ConstantNode.raw(parm._type); + con.setDef(0,start); + parm.addDef(con); + } + } + restoreRPC(fun); + } + // A summary is a dispatch target, not a schedulable implementation. + // Retain its own wrapper graph without including it in this schedule. + for( int i = 0; i<stop.nIns(); i++ ) { + StopCUNode unit = (StopCUNode)stop.in(i); + boolean summary = false; + for( Node r : unit._inputs ) + summary |= ((ReturnNode)r).fun().summary()!=null; + if( summary ) { + unit.start().setDef(0,null); + stop.delDef(i--); + } + } + for( Node n : nodes ) + if( n instanceof FunNode fun ) fun.ret().unkeep(); + return funs; + } + private static void unlinkImports(CodeGen code) { // Imported function constants keep their symbolic identity, not an // embedded copy of the other object's Return and body. for( Node n : code._start._outputs.asAry() ) - if( n instanceof FunPtrNode ptr && ptr.ret()!=null && !code.owns(ptr.fun()) ) { + if( n instanceof FunPtrNode ptr && ptr.ret()!=null && !ptr.fun().isFromSource() ) { ptr.liftType(ptr._type); ptr.setDef(1,null); } for( FunNode fun : code._linker ) { - if( fun==null || fun.isDead() || code.owns(fun) ) + if( fun==null || fun.isDead() || fun.isFromSource() ) continue; for( int i=1; i<fun.nIns(); i++ ) if( fun.in(i) instanceof CallNode call ) @@ -43,7 +89,7 @@ abstract class Unlink { // Imported functions are not emitted by this object. Ideal // evaluation retains them so their calls can actually execute. - if( removeImports && !code.owns(fun) ) { + if( removeImports && !fun.isFromSource() ) { while( fun.nIns() > 1 ) { if( fun.in(1) instanceof CallNode call ) call.unlink(fun,1); @@ -88,15 +134,7 @@ abstract class Unlink { // Unlink from Call for( int i=2; i<fun.nIns(); i++ ) ((CallNode)fun.in(i)).unlink(fun,i--); - if( fun.rpc()==null ) { // Ensure valid RPC - // First make sure a valid RPC; single-call into multi-fun will have each - // function having a single call site, so the RPC becomes a constant and - // folds - but since multiple targets, the Call never inlines. Recreate a - // valid RPC so codegen (and Eval2) understands the calling convention. - ParmNode rpc = new ParmNode( "$rpc", 0, ret.rpc()._type, fun ); - rpc.addDef(ret.rpc()); - ret.setDef( 3, rpc.init() ); - } + restoreRPC(fun); } code._stop.walk(n -> { @@ -109,4 +147,15 @@ abstract class Unlink { return null; }); } + + private static void restoreRPC(FunNode fun) { + if( fun.rpc()!=null ) return; + // A single-call target can have a folded RPC even when a multi-target + // call cannot inline it. Restore the parameter for codegen and for + // Eval2's continuation, now that calls no longer supply graph edges. + ReturnNode ret = fun.ret(); + ParmNode rpc = new ParmNode("$rpc",0,ret.rpc()._type,fun); + rpc.addDef(ret.rpc()); + ret.setDef(3,rpc.init()); + } } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java index 7bc17c75..d33670d1 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -115,24 +115,8 @@ public class CLInitNode extends CFGNode implements MultiNode { Node ctrl = in(0); Node memory = mem(); - // A child body may assume its parent has finished. Establish that - // requirement first, then test the child's flag in the resulting memory. - CompUnit parent = cu()._par; - if( parent!=null ) { - Node ptr = CodeGen.CODE.con(TypeMemPtr.make((byte)2,parent._clz,true)); - Field flag = parent._clz.field("$init"); - Node off = CodeGen.CODE.con(parent._clz.offset(parent._clz.find("$init"))); - Node parentReady = CodeGen.CODE.add(new LoadNode(_loc,"$init",flag._alias,ctrl,memory,ptr,off).init()); - CLInitNode init = CodeGen.CODE.add(new CLInitNode(_loc,ctrl,memory,ptr,parentReady).init()); - ctrl = CodeGen.CODE.add(new CProjNode(init,0,ScopeNode.CTRL).init()); - memory = CodeGen.CODE.add(new ProjNode(init,1,ScopeNode.MEM0).init()); - } - - Node childOff = CodeGen.CODE.con(cu()._clz.offset(cu()._clz.find("$init"))); - // Read the child's flag after establishing its parent's memory effects. - Node ready = CodeGen.CODE.add(new LoadNode(_loc,"$init",flag()._alias,ctrl,memory,ptr(),childOff).init()); - - IfNode iff = CodeGen.CODE.add(new IfNode(ctrl,ready).init()); + // The callee establishes its parent before setting its own flag. + IfNode iff = CodeGen.CODE.add(new IfNode(ctrl,ready()).init()); Node done = CodeGen.CODE.add(new CProjNode(iff,0,"True").init()); Node cold = CodeGen.CODE.add(new CProjNode(iff,1,"False").init()); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index fc6effdc..73f67479 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -160,7 +160,7 @@ public class CallEndNode extends CFGNode implements MultiNode { } public byte maybeInline() { - byte inline = inlineCandidate(); + byte inline = inlineCandidate(false); if( CodeGen.CODE._midAssert ) return inline; _inline = inline; @@ -170,8 +170,23 @@ public class CallEndNode extends CFGNode implements MultiNode { return _inline; } - // Check if candidate right now, sets no flags - private byte inlineCandidate() { + // This CallEnd might be an inline candidate, but the actual code is in + // another CompUnit and needs loading to decide. Called at an empty worklist. + public boolean loadForInline() { + CodeGen code = CodeGen.CODE; + if( code._phase!=CodeGen.Phase.IterPostOpto || nIns()!=2 || + !(in(1) instanceof ReturnNode ret) || ret.fun().summary()==null ) return false; + // Fetch bodies only for calls in functions compiled from source here. + // Calls inside imported functions become eligible when inlined into one. + if( !(in(0) instanceof CallNode call) || !call.fun().isFromSource() || + inlineCandidate(true)<=0 ) return false; + code.loadForInline(ret.fun()._compunit); + return true; + } + + // Check if candidate right now, sets no flags. Loading uses the same + // policy, but can only estimate the size of a summarized body. + private byte inlineCandidate(boolean loading) { if( _inline < -2 ) return -2; // Never if( _folding ) return -2; // No, and will collapse anyways if( !(in(0) instanceof CallNode call) ) return -2; // malformed because mid-death @@ -210,10 +225,12 @@ public class CallEndNode extends CFGNode implements MultiNode { // A large parse can leave only a tiny initializer. Recognize that // and await cleanup to shrink the body. if( fun._approxUIDs >= maxSize ) { - if( !smallBody(fun) ) return -1; - } else if( fun.body().cardinality() >= maxSize ) // Expensive size check + if( fun.summary()!=null || !smallBody(fun) ) return -1; + } else if( fun.summary()==null && fun.body().cardinality() >= maxSize ) // Expensive size check return -1; // Try later (if cleanup makes the real body small enough) + if( fun.summary()!=null ) return loading ? (byte)1 : (byte)-1; + // Can be cloned but not trivial if( fun.nIns() > 2 ) { addDep(fun); return 2; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java index edde247a..fe3c3162 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -82,6 +82,13 @@ public class FunNode extends RegionNode { } public ParmNode rpc() { return parm(0); } + // An unloaded body's Summary is constructed before every other user. + public SummaryNode summary() { return nOuts()>0 && out(0) instanceof SummaryNode summary ? summary : null; } + + // This invocation compiles the defining CompUnit from source. Imported + // functions still belong to a CompUnit, but its _src is null. + public boolean isFromSource() { return _compunit!=null && _compunit._src!=null; } + // Cannot create the Return and Fun at the same time; one has to be first. // So setting the return requires a second step. public void setRet(ReturnNode ret) { _ret=ret; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index df686bcf..45f7a6fa 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -45,7 +45,7 @@ public class LoopNode extends RegionNode { x = x.idom(); } // Found a no-exit loop. Insert an exit - NeverNode iff = (NeverNode)new NeverNode(1.2f,back()).peephole(); // Ideal never-branch + NeverNode iff = new NeverNode(1.2f,back()).init(); // Ideal never-branch CProjNode t = new CProjNode(iff,0,"True" ).init(); CProjNode f = new CProjNode(iff,1,"False").init(); setDef(2,t); // True continues loop, False (never) exits loop @@ -55,7 +55,10 @@ public class LoopNode extends RegionNode { // Now fold control into the exit. Might have 1 valid exit, or an // XCtrl or a bunch of prior NeverNode exits. - Node top = ConstantNode.make(Type.TOP).peephole(); + // Scheduling can prepare a newly loaded object while other code is + // executing. Keep synthetic nodes local; do not GVN into that graph. + Node top = ConstantNode.raw(Type.TOP); + top.setDef(0,fun); Node memout = new MemMergeNode(); memout.addDef(f); // placeholder for control memout.addDef(top); diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index 43acf631..a88adee2 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -97,6 +97,9 @@ public class StopCUNode extends StopNode { // on paths with no Return. A class boundary must not hide it. for( CallNode call : CodeGen.CODE._calls ) if( !call.isDead() ) xmem=publicBottom(xmem.escapes(call.exposed(this))); + for( FunNode fun : CodeGen.CODE._linker ) + if( fun!=null && fun.summary()!=null && !fun.summary().isDead() ) + xmem=publicBottom(xmem.escapes(fun.summary().exposed(this))); assert xmem._alias==1 && !xmem._one; return TypeTuple.make(Type.CONTROL,xmem,Type.BOTTOM); } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java new file mode 100644 index 00000000..426174e7 --- /dev/null +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/SummaryNode.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.*; +import java.util.HashMap; + +// Analysis of an imported function whose implementation has not been loaded. +// This is never an inlineable or executable body. +public class SummaryNode extends CFGNode implements MultiNode { + + public TypeTuple _state; + // Callees and touched class initializers, by FIDX, for class-init cycle checks. + public final int[] _classDependencyFIDXs; + + public SummaryNode(TypeTuple state, int[] classDependencyFIDXs, Node... inputs) { + super(inputs); + _state = state; + _classDependencyFIDXs = classDependencyFIDXs; + } + + @Override public String label() { return "Summary"; } + @Override public boolean blockHead() { return true; } + @Override public Type compute() { + if( in(0)._type.isHigh() ) return TypeTuple.STATE.dual(); + // A library summary does not forget escapes already present in the caller. + TypeMem mem = in(1)._type instanceof TypeMem m ? m : in(1)._type.isHigh() ? TypeMem.TOP : TypeMem.BOT; + mem = (TypeMem)mem.meet(_state.mem()); + for( int i = 2; i<nIns(); i++ ) mem=mem.escapes(in(i)._type); + return TypeTuple.make(_state.ctl(),mem,_state.ret()); + } + @Override public Node idealize() { return null; } + public TypeMem exposed(Node dep) { + dep.addDepForwards(this); + if( dep.addDepForwards(in(0))._type.isHigh() ) return TypeMem.START; + TypeMem mem = (TypeMem)_state.mem(); + for( int i = 2; i<nIns(); i++ ) mem=mem.escapes(dep.addDepForwards(in(i))._type); + return TypeMem.make(1,Type.BOTTOM,false,false,false,mem._escFs,mem._escAs); + } + @Override boolean _upgradeType(HashMap<String,Type> types) { + TypeTuple state = (TypeTuple)_state.upgradeType(types); + if( state==_state ) return false; + unlock(); + _state=state; + return true; + } + // Materialize an object and publish real FIDX targets without rewriting + // callers or reoptimizing their active graphs. The evaluator schedules + // this object's checked ideal IR before entering any of its functions. + public static ElfReader load(CodeGen code, FunNode fun) { + assert fun.summary()!=null; + ElfReader elf = code.getElf(fun._compunit._obj); + assert elf._nodes==null; // Not loaded yet, or we would already have code for `fun` + elf.loadSimple(code); // Load all the IR, including code for `fun` + StopNode stop = (StopNode)elf._nodes.last(); + for( Node n : stop._inputs ) { + StopCUNode stopcu = (StopCUNode)n; + for( Node r : stopcu._inputs ) { + FunNode target = ((ReturnNode)r).fun(); + target._compunit._start = stopcu.start(); + target._compunit._stop = stopcu; + code.link(target); + } + } + return elf; + } +} diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java index 31a616b5..dbb2a5ca 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -198,7 +198,8 @@ public class Chapter25Test { new CodeGen(root.toString(),root.toString(),imported ? paths : null,"Main",src,126,true,TypeInteger.BOT) .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); assertEquals("",TestC.gcc(root+"/Main.o","",TestC.C_DRIVERS_DIR+"extern_data_import.c", - (String)null,new Ary<>(new String[]{dir+"/Globals.o"}),root+"/program"+(TestC.OS.startsWith("Windows") ? ".exe" : ""))); + (String)null,new Ary<>(new String[]{imported ? dir+"/Globals.o" : root+"/Main/Globals.o"}), + root+"/program"+(TestC.OS.startsWith("Windows") ? ".exe" : ""))); } } @@ -389,8 +390,9 @@ public class Chapter25Test { // Elf files are sane // Sys depends on io, libc, char, collections, and array utilities. - assertArrayEquals(new String[]{"sys", "sys/adt", "sys/adt/bitset", "sys/ary", + assertArrayEquals(new String[]{"sys/adt", "sys/ary", "sys/aryi64", "sys/aryu8", "sys/char", "sys/io", "sys/libc", "sys/scan"},sys_elf._deps); + assertArrayEquals(new String[]{"sys"},sys_elf._units); assertSame("class:sys" ,sys_elf._clz._name); } @@ -422,7 +424,7 @@ public class Chapter25Test { PrintStream saved = System.out; try( PrintStream capture = new PrintStream(output,true,StandardCharsets.UTF_8) ) { System.setOut(capture); - Simple.main(new String[]{"-L",SYS_FILE.toString(),"-o","build/objs/helloWorldDriverLibFile/", + Simple.main(new String[]{"-L",SYS_BLDDIR,"-o","build/objs/helloWorldDriverLibFile/", "src/test/smp/examples/A_helloWorld.smp"}); } finally { System.setOut(saved); @@ -444,8 +446,7 @@ public class Chapter25Test { String syms = TestC.exec(TestC.TEST_TIMEOUT_SECONDS,"nm",obj); assertTrue(syms, syms.contains(" U sys.io.p_noInline")); - TestC.linkExe(obj,null,null,new Ary<>(new String[]{SYS_FILE.toString()}),exe); - String rez = TestC.exec(TestC.TEST_TIMEOUT_SECONDS,exe); + String rez = TestC.gcc(code,null,null,null,exe); assertEquals(expected,rez); } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter28bTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter28bTest.java index fb418b9a..e0424573 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter28bTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter28bTest.java @@ -1,23 +1,5 @@ package com.seaofnodes.simple; -// -//import com.seaofnodes.simple.codegen.CodeGen; -//import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; -//import com.seaofnodes.simple.codegen.ElfReader; -//import com.seaofnodes.simple.codegen.ParseAll; -//import com.seaofnodes.simple.node.CallNode; -//import com.seaofnodes.simple.node.FunNode; -//import com.seaofnodes.simple.node.LoopNode; -//import com.seaofnodes.simple.type.TypeInteger; -//import com.seaofnodes.simple.util.Ary; -//import java.io.File; -//import java.io.FileWriter; -//import java.io.IOException; -//import java.io.ByteArrayOutputStream; -//import java.io.PrintStream; -//import java.nio.charset.StandardCharsets; -//import java.nio.file.Files; -//import java.nio.file.Path; import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Ignore; import org.junit.Test; @@ -39,9 +21,9 @@ struct C { }; return new C(arg).x; """; - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"riscv","SystemV"); - assertEquals("return (arg+3);", code.print()); - assertEquals("3",Eval2.eval(code,0)); + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("Stop[ return Phi(Loop,0,Phi(Region,1,Phi_x)); return MEM[ 2:___ 3:.x=Phi(Loop,0,Phi(Region,1,Phi_x));]; return MEM[ 2:___ 3:.x=0;]; return Test.C; ]", code.print()); + assertEquals("1",Eval2.eval(code,3)); } } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java index 47e10f97..7f5fcd38 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java @@ -443,7 +443,7 @@ public class ClassInitDependenciesTest { "Main",src,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); assertNotNull(code._stop.walk(n -> n instanceof CLInitNode ? n : null)); assertEquals("0",Eval2.eval(code,0)); - assertNull(code._stop.walk(n -> n instanceof CLInitNode ? n : null)); + assertNotNull("Eval executes CLInit without lowering it",code._stop.walk(n -> n instanceof CLInitNode ? n : null)); assertEquals("134",Eval2.eval(code,1)); } @@ -468,8 +468,13 @@ public class ClassInitDependenciesTest { @Test public void testParentInitializationExecution() throws Exception { Path dir=tempDir("execution-"); object(dir,dir,"State","int count=0;"); - module(dir,dir,"P",Map.of("P","val C=C; State.count=State.count*10+1;", - "P/C","State.count=State.count*10+2; int value=arg;")); + CodeGen library = module(dir,dir,"P",Map.of("P","val C=C; State.count=State.count*10+1;", + "P/C","State.count=State.count*10+2; int value=arg; return State.count;")); + // Direct entry into the child has no surrounding CLInit call/check. + // Its body must establish the parent itself, including an imported parent. + CodeGen child = new CodeGen(library._modDir,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "P/C",null,123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + assertEquals("12",Eval2.eval(child,99)); for( long seed : new long[]{1,123,987654321} ) { CodeGen code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), "Main","return P.C.value+State.count;",seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); @@ -484,7 +489,8 @@ public class ClassInitDependenciesTest { """); String exe=dir.resolve(TestC.OS.startsWith("Windows") ? "check.exe" : "check").toString(); TestC.linkExe(dir.resolve("Main.o").toString(),TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi", - cfile.toString(),new Ary<>(new String[]{dir.resolve("P.o").toString(),dir.resolve("State.o").toString()}),exe); + cfile.toString(),new Ary<>(new String[]{dir.resolve("P.o").toString(),dir.resolve("P/C.o").toString(), + dir.resolve("State.o").toString()}),exe); assertEquals("",TestC.exec(exe)); } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter28b/src/test/java/com/seaofnodes/simple/Eval2.java index 901a8990..fc87c13a 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Eval2.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.IRPrinter; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; import java.util.*; @@ -11,7 +12,7 @@ import java.util.*; public abstract class Eval2 { // A mapping from Node ID to evaluation data Object. - // Data Objsts are a boxed Long or Double; or an Object[] of fields, which + // Data Objects are a boxed Long or Double; or an Object[] of fields, which // themselves are just more Objects. private static class Frame { private static int UID=1; @@ -77,31 +78,24 @@ public abstract class Eval2 { } } - // Classic Closure; an environment (stack of frames) and an execution point - private static class Closure { - // Where to return too; either a CallEnd or a Function + // A Classic Continuation; the suspended caller and the control point to + // resume after a return. + private static class Continuation { + // Resume a CallEnd or a CLInit's successor, or exit at Stop. final CFGNode _cc; - // Stack frame at the execution point. Includes Closures which + // Stack frame at the execution point. Includes Continuations which // recursively include other stack frames - private Frame _frame; + final Frame _frame; - Closure(CFGNode cc, Frame frame) { - _cc = cc; // One of Fun, CallEnd or Stop (null) + Continuation(CFGNode cc, Frame frame) { + _cc = cc; _frame = frame; assert _frame._refcnt >=0; _frame._refcnt++; } - FunNode fun() { return (FunNode)_cc; } - CallEndNode cend() { return (CallEndNode)_cc; } - boolean isStop() { return _cc instanceof StopNode; } // or Stop - - // - void pushFrame() { - _frame = new Frame(_frame); - _frame._refcnt++; - } + boolean isStop() { return _cc instanceof StopNode; } @Override public String toString() { return _cc.toString(); @@ -119,12 +113,15 @@ public abstract class Eval2 { public static String eval( CodeGen code, long arg ) { return eval(code,arg,1000); } public static String eval( CodeGen code, long arg, int timeout ) { + code.driver(CodeGen.Phase.TypeCheck); if( code._start.uctrl()==null ) return ""; // The empty program SB trace = null; // new SB(); // TRACE, set to null for off, new SB() for on - // Force local scheduling phase - code.driver(CodeGen.Phase.LocalSched); // Set global, so don't have to pass everywhere CODE = code; + // Eval uses checked ideal IR, including CLInit, and does not run Lower. + // Objects loaded later are scheduled independently of this graph. + if( code._phase.ordinal()<CodeGen.Phase.Schedule.ordinal() ) code.scheduleForEval(); + code.driver(CodeGen.Phase.LocalSched); CLASSES.clear(); // Timer for when we run too long. Ticks once per backedge or function call @@ -134,18 +131,12 @@ public abstract class Eval2 { // fields, which themselves are just more Objects. F = new Frame(null); - // Start at the START - CFGNode BB = code._start, prior = null; - // Return from main hits Stop - F.put(BB,new Closure(code._stop,F)); - // For all <clinit> / Clazzes, install their uninitialized memory - for( FunNode fun : code._linker ) - if( fun!=null && fun.isClz() ) { - TypeStruct clz = ((TypeMemPtr)fun.sig().arg(0))._obj; - // Map from the <clinit> self parameter to the - // singleton class structure. - F.put(fun.parm(2),classObject(clz)); - } + FunNode entry = (FunNode)code._start.uctrl(); + VALUE_CACHE.setX(0,"$mem"); + VALUE_CACHE.setX(1,classObject(((TypeMemPtr)entry.sig().arg(0))._obj)); + VALUE_CACHE.setX(2,arg); + CFGNode BB = enter(entry,code._stop); + CFGNode prior = null; // ------------ @@ -158,7 +149,7 @@ public abstract class Eval2 { // Parallel assign Phis int i = BB instanceof RegionNode r - ? parallelAssignPhis(r,prior,arg,trace) + ? parallelAssignPhis(r,prior,trace) : 0; // Compute the data nodes until BB control @@ -170,33 +161,38 @@ public abstract class Eval2 { prior = BB; BB = BB.uctrl(); // Next unique control target switch( prior ) { - case StartNode start: F = new Frame(F); break; // Frame for the call to main, as-if Called case CallNode call : BB = call(call); break; + case CLInitNode init: BB = call(init); break; case NeverNode never: BB = never.cproj(0); break; // Synthetic exit is never taken. case IfNode iff : Object p = val(iff.pred()); BB = iff.cproj( p==null || (p instanceof Long x && x==0L) ? 1 : 0); break; - case ReturnNode ret : if( clj(ret.rpc()).isStop() ) return exit(ret); else BB = ret(ret); break; + case ReturnNode ret : if( continuation(ret).isStop() ) return exit(ret); else BB = ret(ret); break; case FunNode fun : if( loopCnt++ > timeout ) return null; break; // Timeout case LoopNode loop : if( loopCnt++ > timeout ) return null; break; // Timeout case CallEndNode cend: break; case CProjNode cproj: break; case RegionNode r : break; - default: throw Utils.TODO(); + default: throw Utils.TODO("Eval control: "+prior.getClass().getSimpleName()); } if( BB==null ) return null; assert !BB.isDead(); } } - - // Phi cache; size is limited to number of Phis at a merge point - private static final Object[] PHICACHE = new Object[256]; - static int parallelAssignPhis(RegionNode r, CFGNode prior, long arg, SB trace) { + // Scratch values for parallel Phi assignment and call arguments. Each use + // is consumed before the next block executes; loading only schedules code. + private static final Ary<Object> VALUE_CACHE = new Ary<>(Object.class); + static int parallelAssignPhis(RegionNode r, CFGNode prior, SB trace) { + + // enter() assigned parameters, including the return continuation, + // from runtime arguments rather than the compiler's call graph. + if( r instanceof FunNode ) { + int i = 0; + while( i<r.nOuts() && r.out(i) instanceof ParmNode ) i++; + return i; + } // Compute input path on Phis for this Region int path = r._inputs.find( prior ); - // Parameters read from prior frame, Phis from local frame - Frame frame = (r instanceof FunNode ? F._prior : F); - boolean isClz = r instanceof FunNode fun && fun.isClz(); // Parallel assign Phis. First parallel read and cache int i; @@ -205,26 +201,11 @@ public abstract class Eval2 { // non-Phi is the end of all Phis. if( !(r.out(i) instanceof PhiNode phi) ) break; - // Parms read from Call args - - // - except RPC is the actual prior frame - // - except entry <clinit> takes the external program argument - Object val; - if( isClz && prior instanceof StartNode && phi instanceof ParmNode parm && parm._idx==3 ) - PHICACHE[i] = arg; // Reading the initial arguments to <clinit> - else { - Node n = phi instanceof ParmNode parm - // RPC uses the prior Call directly; - // Parms may not be linked, so read call args directly - ? (parm._idx==0 ? prior : prior.in(parm._idx)) - // Phis read from path input - : phi.in(path); - // Read the frame before overwriting - PHICACHE[i] = frame.get(n); - } + VALUE_CACHE.setX(i,F.get(phi.in(path))); } // Parallel assign; might assign before read, so read from cache for( int j=0; j < i; j++ ) - traceData(F.put0(r.out(j),PHICACHE[j]),trace); + traceData(F.put0(r.out(j),VALUE_CACHE.at(j)),trace); // Return point in basic block past last Phi; the Phis have been // evaluated here, and now we need to evaluate the rest of the block return i; @@ -233,27 +214,67 @@ public abstract class Eval2 { // Make a call. private static CFGNode call( CallNode call ) { - // Set up the Return PC and return frame (which is just the current frame). - // Really making a Continuation, but it's just a Closure - Closure cont = new Closure(call.cend(),F); - // Set the return continuation into the current frame RPC - F.put(call, cont ); - // Next Frame to use - F = new Frame(F); - // Target function and environment - return CODE.link(tfp(call.fptr())); + int nargs = call.nargs()+1; // Include memory. + for( int i = 0; i<nargs; i++ ) VALUE_CACHE.setX(i,val(call.in(i+1))); + return enter(CODE.link(tfp(call.fptr())),call.cend()); + } + + // Interpret the flag-test/call diamond that Lower would emit. The taken + // arm uses the ordinary call entry and RPC continuation. The initializer + // itself initializes its parent and sets its own $init flag. + private static CFGNode call(CLInitNode init) { + CompUnit cu = init.cu(); + //if( cu==null ) return init.uctrl(); + assert cu != null; // Post-optimizer the remaining CLInits refer to real classes + Object[] obj = classObject(cu._clz); + if( obj[cu._clz.find("$init")].equals(1L) ) + return init.uctrl(); // Class already initialized! + VALUE_CACHE.setX(0,"$mem"); + VALUE_CACHE.setX(1,obj); + VALUE_CACHE.setX(2,0L); + return enter(CODE.link(cu),init.uctrl()); + } + + + private static FunNode enter(FunNode fun, CFGNode continuation) { + // If we find a Summary, then this Fun's code never got loaded. + // Load it now. + if( fun.summary()!=null ) { + int fidx = fun.sig().fidx(); + // Load the matching .o, and all its CompUnits, and all the + // included FunNodes, including a replacement for this one. + ElfReader elf = SummaryNode.load(CODE,fun); + // Object files contain checked ideal IR, before scheduling. This is + // the first schedule for this object's bodies, even though the caller + // is already executing. Schedule only the new graph: revisiting the + // caller could change nodes whose values live in an active Frame. + // No optimization, CLInit lowering, or finalization. + ListScheduler.sched(GlobalCodeMotion.forEval(CODE,(StartNode)elf._nodes.at(0),(StopNode)elf._nodes.last())); + // Get the new replacement FunNode + fun = CODE.link(fidx); + } + Continuation cont = new Continuation(continuation,F); + F=new Frame(F); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) + F.put0(parm,parm._idx==0 ? cont : VALUE_CACHE.at(parm._idx-1)); + return fun; } private static CFGNode ret( ReturnNode ret ) { // Fetch return expression value and continuation from current frame Object rez = val(ret.expr()); - Closure cont = clj(ret.rpc()); + Continuation cont = continuation(ret); // Lower Frame reference count; might delete frame F.dec(); // Lower ref count // Install replacement Frame; set return result over the CallEnd F = cont._frame; - F.put0(cont._cc,rez); // Set return value into CallEnd - return cont._cc; // Return CallEnd as the new control + if( cont._cc instanceof CallEndNode ) F.put0(cont._cc,rez); + return cont._cc; // Resume after the call. + } + + private static Continuation continuation(ReturnNode ret) { + return (Continuation)val(ret.rpc()); } private static String exit( ReturnNode ret ) { @@ -329,8 +350,6 @@ public abstract class Eval2 { static TypeFunPtr tfp(Node n) { return (TypeFunPtr)F.get(n); } - // Fetch and unbox a closure - static Closure clj(Node n) { return (Closure)F.get(n); } // Java box ints and floats. Other things can just be null or some informative string private static Object con( Type t ) { diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/IncrementalBuildTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/IncrementalBuildTest.java index 501392f3..3c53c004 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/IncrementalBuildTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/IncrementalBuildTest.java @@ -42,23 +42,26 @@ public class IncrementalBuildTest { assertNotNull("Reparse A before loading its stale inlined body",code._compunits.get("App/A")._src); assertNotNull(code._compunits.get("App/B")._src); compile(src,obj,"App/Main"); - checkNative(obj,new Ary<>(new String[]{obj.resolve("App.o").toString()})); + checkNative(obj); Path clean=Files.createDirectory(root.resolve("clean")); assertEquals("9",Eval2.eval(client(src,clean),0)); compile(src,clean,"App/Main"); - checkNative(clean,null); + checkNative(clean); } - @Test public void testBundledSourceChangeAndCycle() throws Exception { + @Test public void testSourceChangeAndCycle() throws Exception { Path root=fixture("bundle-"); Path src=root.resolve("src"), obj=root.resolve("obj"); write(src,"App/A","val value={int n -> n ? B.value(n-1) : 1; };",1000); write(src,"App/B","val value={int n -> n ? A.value(n-1) : 5; };",1000); write(src,"App/Main","return A.value(1);",1000); compile(src,obj,"App/A"); + assertEquals("One build timestamp for the cycle",Files.getLastModifiedTime(obj.resolve("App/A.o")), + Files.getLastModifiedTime(obj.resolve("App/B.o"))); stamp(obj.resolve("App/A.o"),3000); - assertFalse("A owns both sides of the cycle",Files.exists(obj.resolve("App/B.o"))); + assertTrue("Each side of the cycle owns an object",Files.exists(obj.resolve("App/B.o"))); + stamp(obj.resolve("App/B.o"),3000); CodeGen code=client(src,obj); assertEquals("5",Eval2.eval(code,0)); assertNull(code._compunits.get("App/A")._src); @@ -125,13 +128,15 @@ public class IncrementalBuildTest { .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); } - private static void checkNative(Path obj, Ary<String> libs) throws Exception { + private static void checkNative(Path obj) throws Exception { Path driver=obj.resolve("driver.c"); Files.writeString(driver,""" __attribute__((CALL_CONV)) extern long long run(void) __asm__("App.Main.run"); int main(void) { return run()==9 ? 0 : 1; } """); String exe=obj.resolve(TestC.OS.startsWith("Windows")?"test.exe":"test").toString(); + Ary<String> libs = new Ary<>(new String[]{obj.resolve("App.o").toString(), + obj.resolve("App/A.o").toString(),obj.resolve("App/B.o").toString(),obj.resolve("App/C.o").toString()}); TestC.linkExe(obj.resolve("App/Main.o").toString(), TestC.CALL_CONVENTION.equals("win64")?"ms_abi":"sysv_abi",driver.toString(),libs,exe); assertEquals("",TestC.exec(TestC.TEST_TIMEOUT_SECONDS,exe)); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java new file mode 100644 index 00000000..7d42f924 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java @@ -0,0 +1,113 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.Ary; +import java.io.IOException; +import java.nio.file.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class SelectiveLoadingTest { + @Test public void testCycleRefinementLoadsConditionHelper() throws Exception { + Path base = Path.of("build/objs/selective"); + Files.createDirectories(base); + Path root = Files.createTempDirectory(base,"cycle-"); + Path stubs = Files.createDirectory(root.resolve("stubs")); + Path lib = Files.createDirectory(root.resolve("lib")); + object(stubs,null,"A","int value=arg;"); + object(stubs,null,"B","int value=arg;"); + StringBuilder helper = new StringBuilder("val test={bool n -> "); + // Large parse, small final body: it will not request speculative loading. + for( int i = 0; i<80; i++ ) helper.append("val x").append(i).append("=n+0;"); + helper.append("return n;};"); + object(lib,null,"Predicate",helper.toString()); + Ary<String> inputs = new Ary<>(new String[]{stubs.toString(),lib.toString()}); + object(lib,inputs,"A","int value=1; if(Predicate.test(false)) value=B.value;"); + object(lib,inputs,"B","int value=A.value;"); + CodeGen code = new CodeGen(null,root.toString(),new Ary<>(new String[]{lib.toString()}), + "Main","return A.value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.FinalizeIR); + assertNotNull(function(code,"test").summary()); + assertNotNull("Summaries alone report a potential cycle",new ClassInitDependencies(code).check()); + code.driver(CodeGen.Phase.TypeCheck); + assertNull("The helper is outside A/B's apparent cycle",function(code,"test").summary()); + assertEquals("1",Eval2.eval(code,0)); + } + + private static void object(Path dir, Ary<String> paths, String name, String source) { + new CodeGen(null,dir.toString(),paths,name,source,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + } + + @Test public void testSummariesInliningAndStaticLink() throws Exception { + Path base = Path.of("build/objs/selective"); + Files.createDirectories(base); + Path root = Files.createTempDirectory(base,"library-"); + Path src = Files.createDirectory(root.resolve("src")); + Path lib = Files.createDirectory(root.resolve("lib")); + Path app = Files.createDirectory(root.resolve("app")); + write(src,"Lib","val api=Api; val work=Work; val unused=Unused;"); + write(src,"Lib/Api",""" + val p={int n -> Work.write_noInline(n);}; + val p_noInline={int n -> Work.write_noInline(n);}; + """); + write(src,"Lib/Work","val write_noInline={int n -> n+1;};"); + write(src,"Lib/Unused","val f={int n -> n*2;};"); + new CodeGen(src.toString(),lib.toString(),null,"Lib",null,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + for( String unit : new String[]{"Lib","Lib/Api","Lib/Work","Lib/Unused"} ) + assertTrue(unit,Files.isRegularFile(lib.resolve(unit+".o"))); + + Ary<String> paths = new Ary<>(new String[]{lib.toString()}); + CodeGen code = new CodeGen(null,app.toString(),paths,"Main", + "if(arg==0) return -1; return Lib.api.p_noInline(arg);",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + assertNotNull(function(code,"Lib.Api.p_noInline").summary()); + assertNotNull(function(code,"Lib.Work.write_noInline").summary()); + assertNotNull(function(code,"Lib.Unused.f").summary()); + assertEquals("-1",Eval2.eval(code,0)); + assertNotNull("An untaken branch does not load its target",function(code,"Lib.Api.p_noInline").summary()); + assertEquals("42",Eval2.eval(code,41)); + assertNull(function(code,"Lib.Work.write_noInline").summary()); + assertNotNull("Evaluation leaves unrelated objects unloaded",function(code,"Lib.Unused.f").summary()); + assertEquals("6",Eval2.eval(code,5)); + + code=new CodeGen(null,app.toString(),paths,"Main", + "val run={int n -> Lib.api.p(n);}; return run(arg);",123,true,TypeInteger.BOT) + .driver(CodeGen.Phase.TypeCheck); + assertNull("p requested Api's implementation",function(code,"Lib.Api.p").summary()); + assertNotNull("The remaining call needs a signature, not a body",function(code,"Lib.Work.write_noInline").summary()); + assertNotNull("A namespace reexport does not request IR",function(code,"Lib.Unused.f").summary()); + code.driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + Path driver = app.resolve("driver.c"); + Files.writeString(driver,""" + __attribute__((CALL_CONV)) extern long long run(long long); + int main(void) { return run(41)==42 ? 0 : 1; } + """); + String exe = app.resolve(TestC.OS.startsWith("Windows") ? "test.exe" : "test").toString(); + assertTrue("The compiler already resolved this transitive object", + TestC.linkObjs(code).contains(lib.resolve("Lib/Work.o").toRealPath().toString())); + assertEquals("",TestC.gcc(code, + TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi",driver.toString(),null,exe)); + + Files.delete(lib.resolve("Lib/Work.o")); + // Even an untaken branch requires a complete dependency closure for a + // fresh program. + try { + Eval2.eval(new CodeGen(null,app.toString(),paths,"Missing", + "if(arg==0) return -1; return Lib.api.p_noInline(arg);",123,true,TypeInteger.BOT),0); + fail("Missing transitive code must fail before evaluation"); + } catch( RuntimeException ex ) { assertTrue(ex.getMessage(),ex.getMessage().contains("Lib/Work")); } + } + + private static FunNode function(CodeGen code, String name) { + for( FunNode fun : code._linker ) if( fun!=null && name.equals(fun._name) ) return fun; + throw new AssertionError("Missing function "+name); + } + + private static void write(Path src, String unit, String text) throws IOException { + Path file = src.resolve(unit+".smp"); + Files.createDirectories(file.getParent()); + Files.writeString(file,text); + } +} diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java index 4576bc94..4e8a0417 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java @@ -30,6 +30,7 @@ public class SeparateCompilationTest { CodeGen code=new CodeGen(null,null,new Ary<>(new String[]{lib.toString()}), "Client","return Callbacks.run(arg);",123,true,TypeInteger.BOT) .driver(CodeGen.Phase.Opto); + code.loadAllIR(); // This assertion inspects a body, not just its saved summary. assertNull(code._compunits.get("Callbacks")._src); ParmNode base=code._start.walk(n -> n instanceof ParmNode p && p._label.equals("base") ? p : null); assertNotNull(base); diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Simple.java b/chapter28b/src/test/java/com/seaofnodes/simple/Simple.java index 7cfdf57d..1f1e8ab0 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/Simple.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/Simple.java @@ -257,7 +257,7 @@ Options: if ( !TestC.CPU_PORT.equals( cpu ) || !TestC.CALL_CONVENTION.equals( abi ) ) throw bad("cannot run code on not native target"); String exe = TestC.OS.startsWith("Windows") ? outBase+".exe" : outBase; - String result = TestC.gcc(outBase+".o", null, null, "", TestC.linkObjs(externPaths), exe); + String result = TestC.gcc(code, null, null, "", exe); System.out.print(result); } } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/TestC.java b/chapter28b/src/test/java/com/seaofnodes/simple/TestC.java index b08be824..54adf3af 100644 --- a/chapter28b/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter28b/src/test/java/com/seaofnodes/simple/TestC.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.codegen.ElfReader; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.Utils; @@ -10,6 +12,7 @@ import java.io.File; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; +import java.util.HashSet; import java.util.concurrent.TimeUnit; import static org.junit.Assert.*; @@ -117,13 +120,12 @@ public abstract class TestC { // build/objs/foo.exe - linked executable Windows // build/objs/foo - linked executable Linux String pathBase = "build/objs/"+base; - String obj = pathBase+".o"; String exe = pathBase+(OS.startsWith("Windows") ? ".exe" : ""); // Compile simple, emit ELF CodeGen code = new CheckedCodeGen(null,"build/objs",externPaths,base,src,126L,true,TypeInteger.BOT); code.driver( CPU_PORT, simple_conv, false, cfile==null ); - linkExe(obj, c_conv, cfile, linkObjs(externPaths), exe); + linkExe(linkObjs(code), c_conv, cfile, exe); // Allocation quality not degraded SpillStats.checkSpills(spills,code._regAlloc._spillScaled); @@ -137,7 +139,7 @@ public abstract class TestC { public static String gcc( String main, double ignore, String... objs ) throws IOException { String BLDDIR = "build/objs/test0/"; String exe = BLDDIR+main+(OS.startsWith("Windows") ? ".exe" : ""); - linkExe(objs[0],null,null,null,exe); + linkExe(new Ary<>(objs),null,null,exe); // Module tests intentionally use the program exit code as their result. ExecResult result = execute(null,0,exe); return result.exit==0 ? result.out : "exec exit code: "+result.exit; @@ -160,7 +162,21 @@ public abstract class TestC { return execStdin(stdin,0,args); } - public static void linkExe( String obj, String c_conv, String cfile, Ary<String> linkObjs, String exe ) throws IOException { + // Immediate compile/link: the compiler already resolved every Simple object. + public static String gcc(CodeGen code, String c_conv, String cfile, String stdin, String... args) throws IOException { + linkExe(linkObjs(code),c_conv,cfile,args[0]); + return execStdin(stdin,0,args); + } + + // Object-only tests supply every link input explicitly. + public static void linkExe( String entry, String c_conv, String cfile, Ary<String> libraries, String exe ) throws IOException { + Ary<String> objects = new Ary<>(String.class); + objects.add(entry); + if( libraries!=null ) objects.addAll(libraries); + linkExe(objects,c_conv,cfile,exe); + } + + private static void linkExe(Ary<String> objects, String c_conv, String cfile, String exe) throws IOException { // Compile the C program. Compiling code and constants in the low // 2Gig. Pointers are 64b BUT since always in the low 2G all the // high bits are zero - and Simple code can be emitted treating @@ -169,18 +185,16 @@ public abstract class TestC { params.add("gcc"); params.add(OS.startsWith("Windows") ? "-Wl,--image-base,0x400000" : "-no-pie"); if( cfile!=null ) params.add(cfile); // Associated C driver, usually has a `main` - params.add(obj); + params.addAll(objects); // Standalone Simple programs export `simple_main`; the small C // runtime owns the native main symbol and converts argc/argv into a // normal Simple array before making the ABI-qualified call. if( cfile==null ) params.add(runtimeObject()); - if( linkObjs != null ) - params.addAll(linkObjs.asAry()); params.addAll(new String[] { "-lm", // Picks up 'sqrt' for newtonFloat tests to compare - "-g", - "-o", - exe, + "-g", // debug symbols + "-o", // name the output file + exe, // name the output file }); // Calling convention for C calls, if any if( cfile!=null ) { @@ -254,20 +268,15 @@ public abstract class TestC { } } - static Ary<String> linkObjs(Ary<String> externPaths) { - if( externPaths == null ) - return null; - Ary<String> objs = new Ary<>(String.class); - for( String path : externPaths ) { - File file = new File(path); - if( file.isFile() && file.getName().endsWith(".o") ) - objs.add(file.toString()); - else if( file.isDirectory() ) { - File sys = new File(file,"sys.o"); - if( sys.isFile() ) - objs.add(sys.toString()); - } + // Gather all CompUnit files and all externally named symbols + static Ary<String> linkObjs(CodeGen code) throws IOException { + Ary<String> objNames = new Ary<>(String.class); + for( CompUnit cu : code._compunits.values() ) { + File obj = cu._obj; + if( obj==null && cu._src!=null ) // Source supplied as a string. + obj = new File(code._buildDir+"/"+(code._srcName==null ? "Test" : code._srcName)+".o"); + if( obj!=null ) objNames.add(obj.getCanonicalPath()); } - return objs.isEmpty() ? null : objs; + return objNames; } } |