diff options
18 files changed, 821 insertions, 127 deletions
diff --git a/chapter25/Makefile b/chapter25/Makefile index aa7f0a17..954a22a5 100644 --- a/chapter25/Makefile +++ b/chapter25/Makefile @@ -15,6 +15,7 @@ # run the tests # # make tests +# make test CLASS=Chapter25Test METHOD=testHelloWorldNoInline ####################################################### # @@ -197,6 +198,13 @@ tests_sys: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(TEST_SYS) $(RELEASE_CRT) @[ -d $(OBJS) ] || mkdir -p $(OBJS) @$(JVM) org.junit.runner.JUnitCore $(test_sys) +# One test method (or the whole class when METHOD is omitted). +CLASS ?= Chapter25Test +METHOD ?= +.PHONY: test +test: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(TEST_SYS) $(RELEASE_CRT) + @$(JVM) com.seaofnodes.simple.TestRunner "$(CLASS)" "$(METHOD)" + fuzzer: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag @echo "fuzzing " @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap diff --git a/chapter25/initialization.md b/chapter25/initialization.md index d03c2eb7..1e5bb509 100644 --- a/chapter25/initialization.md +++ b/chapter25/initialization.md @@ -1,9 +1,10 @@ # Lazy class initialization design -Design proposal, 2026-10-08. This specifies the next implementation; the current -compiler does not yet enforce this protocol. Declared constant final fields -already have static-data lowering, but general lazy run-once initialization, -dependency validation, and initialization guards remain to be implemented. +Design and implementation plan, revised 2026-10-10. Checkpoint 1 implements +post-Opto initialization dependencies and cycle checking for review. Declared +constant final fields already have static-data lowering. General lazy run-once +initialization, serialized dependency validation, and initialization guards +remain to be implemented; the compiler does not yet enforce the full protocol. Initialization metadata belongs with class identity and compilation-unit ownership, not solely on the `<clinit>` FunNode. Represent active touches in @@ -27,13 +28,15 @@ Use one runtime bit in the first, single-threaded implementation. a called function to observe unfinished dynamic state in an ancestor or any other class. - Initialization requirements form a DAG across the complete linked program, - including module boundaries. Reject cycles, including potential cycles - behind runtime conditionals. Ordinary recursive functions are still legal. + including module boundaries. Count only requirements surviving Opto and its + call-graph analysis. Reject cycles behind conditionals that remain unresolved; + eliminated branches and call targets contribute no edges. Ordinary recursive + functions are still legal. - Initialization order follows actual execution and parent requirements, not parser discovery order, worklist seed, or filesystem enumeration order. For example, A conditionally reading `B.foo`, with B initializing `foo` from -`A.bar`, is rejected. Neither an initial zero nor an early evaluation of +`A.bar`, is rejected if that read survives Opto. Neither an initial zero nor an early evaluation of `A.bar` resolves that cycle. If B is A's child, the parent requirement already provides the reverse dependency. @@ -49,36 +52,49 @@ Keep `CompUnit._deps` for source/object discovery and rebuild dependencies. Do not reuse it as the initialization graph: passive references belong there, and its elements are files rather than necessarily individual classes. -Add a small `ClassInit` record owned by a CompUnit. The file class is available -as `CompUnit._init`; a canonical map in CodeGen resolves records by full class -name. Classes nested within a file do not each have a CompUnit today. They can -have records owned by that same unit, including records with no dynamic body. -This avoids treating an instance `<init>` as a class `<clinit>`. +Use CompUnit directly for the current runtime initialization graph. The parser +creates a file `<clinit>` in `parseStruct(true, ...)`; nested struct declarations +use `parseStruct(false, ...)` for instance initialization. Do not introduce a +separate ClassInit object or invent a dynamic class initializer for those +instance constructors. -Suggested information, with names provisional: +Reuse `_cname` for stable identity, `_par` for the filesystem parent, `_clz` for +the canonical class object and hidden field, and existing function identities +for the body. Add only initialization-specific information: | Member | Meaning | |---|---| -| `_name` | Stable, fully qualified class identity | -| `_owner` | Defining CompUnit; owns native data and initializer definitions | -| `_parent` | Enclosing class record, if any | -| `_body` | Optional current `<clinit>` FunNode; absent for unloaded/static-only bodies | -| `_deps` | Lazily allocated, deduplicated direct initialization dependencies | -| `_complete` | All declarations, call effects, and dependency targets resolved | -| `_static` | Proven that this class's own initialization requires no execution | -| `_flagAlias` | Alias of the hidden `$init` field in this class object | - -An absent body is not proof of `_static`: it may simply not have been loaded. -Metadata flags describe compiler knowledge, not additional runtime states. -An explicitly defined namespace-only parent can have an empty initialization -record; a missing parent definition must not silently become such a record. -FunNodes can refer back to their initialization record; the record survives -inlining, dead-function elimination, and conversion of initialization to data. - -`addInitDep(target, reason)` adds a direct edge only once and invalidates the -cached graph validation/order. Retain a source location and, for indirect -dependencies, a call-site witness for diagnostics. Do not turn every dependency -addition into a scan of all initializer bodies. +| `_classInitDeps` | Lazily allocated `Ary<CompUnit>` of direct initialization requirements | +| `_initComplete` | All initializer touches and relevant call targets have resolved | +| `_initStatic` | Proven that this unit's own initializer needs no execution | + +Keep diagnostic witnesses in the checker's temporary function summaries: source +locations and indirect call witnesses where applicable. CompUnit retains only +the edges and analysis flags after validation. Derive the flag alias from `_clz`'s +`$init` field rather than maintaining a duplicate mapping. Locate the body by +its stable function identity; a transient FunNode cache may be useful but does +not define class identity. An unloaded or eliminated FunNode is not proof of +static initialization. + +Static class objects for nested struct declarations keep their existing named +TypeStruct identity and defining CompUnit. Their materialized data need no new +runtime graph vertex; an active use that requires the enclosing file initialized +maps to its CompUnit. Preserve initialization-independent static accesses. If a +future language feature adds an independent dynamic initializer inside one file, +then introduce the additional per-class graph identity that feature needs. + +`CompUnit.addClassInitDep(code, target)` allocates the collection lazily, deduplicates +edges, and invalidates a compilation-wide validation stamp. Keep self-edges so +they can be diagnosed. Explicit namespace-only parents have no dynamic body; +a missing parent definition must not silently become an empty initializer. + +There are two different dataflows. Runtime `$init` values use ordinary memory +aliases and support flag-load/CLInitNode optimization. Dependency discovery +records which initializers may be requested, independently of incoming flag +values and normal return. A dedicated analysis-only memory slice could encode +that second forward dataflow, but the first implementation uses explicit +CompUnit edges plus small function summaries. It does not add a second family +of memory aliases, and it does not infer cycles from runtime `$init` types. ## Discovering and validating dependencies @@ -87,17 +103,30 @@ Topological output therefore places prerequisites before dependents. A dynamic child has a structural dependency on its parent. An active touch of another class during A's initializer contributes an edge; a passive reference does not. -Record semantic touches before inlining and guard elimination. Collect direct -touches in ordinary function bodies too, and propagate their initialization -effects through the call graph with a worklist. Recursive function SCCs reach -a fixed point of finite dependency sets; they are not themselves initialization -cycles. Indirect calls contribute the union of all possible targets' effects. - -The initial policy is conservative: a runtime conditional contributes both -branches' possible requirements. Do not let inlining choices or random peephole -order decide whether a cycle is legal. Dependencies may be added as forward -references and call targets resolve. Before declaring a graph complete, every -reachable initialization-time call must have a complete effect summary. +Insert active touches as CLInitNodes on executable control. After Opto finishes +SCCP, inlining, and cleanup, collect surviving touches and calls. Use final +function-pointer target sets and propagate initialization effects through the +resulting call graph with a worklist. Recursive function SCCs reach a fixed +point of finite dependency sets; they are not themselves initialization cycles. +Indirect calls contribute the union of targets still possible after optimization. + +Do not accumulate historical targets or source touches eliminated by Opto. +There is no side table watching Node replacements or type changes. An inlined +helper's surviving CLInitNodes belong to its caller; an uninlined helper's +summary propagates through its surviving calls. Walk executable control +forwards so touches before nonreturning calls and infinite loops are included. +Preserve initializer boundaries until validation; expanding/inlining CLInit +operations early must not erase the class identity needed for checking. + +A field value becoming constant does not prove its initializer unnecessary. +CLInitNode survives independently of the load. Dead control may remove both; +a static-initialization proof may remove the obligation. Such proofs must not +assume the very acyclicity being checked. + +Acceptance now depends on what Opto proves. Worklist determinism remains an +implementation goal, but preserving every intermediate target set is not the +language rule. Before declaring a graph complete, every surviving required +initialization-time call must have a complete effect summary. An unknown function-pointer target or native callback is not an empty summary. Reject such a call during initialization unless an explicit trusted contract @@ -131,7 +160,7 @@ initialize every possible dependency, or a prefix of the topological list. ## Ideal IR and runtime protocol -Introduce an effectful `CLInitNode` with a stable ClassInit identity: +Introduce an effectful `CLInitNode` with a stable target CompUnit identity: ```text CLInit(C, ctrl, memory) -> (ctrl, memory) @@ -146,8 +175,9 @@ It can execute arbitrary initializer effects, so it is not a pure flag test. At dynamic class-field reads and writes, required instance creation, and calls requiring initialized class state, consult parser flow facts first and insert CLInitNode only if the required initialization is not already established. -Record the semantic requirement even when no check needs inserting. Passive -Simple class references remain subject to checks at their later field accesses. +A check omitted by a valid dominating initialization proof needs no separate +historical dependency record: its prerequisite is represented on the covering +path. Passive Simple class references remain subject to checks at later field accesses. Native escape of class references is a separate boundary described below. Forward references must preserve the pending check until the target is known. @@ -225,7 +255,7 @@ proved; tracking only the flag would lose the initializer's field and I/O effect There are two different facts: -1. **Static body completion:** `_static` proves that C's own initial contents +1. **Static body completion:** `_initStatic` proves that C's own initial contents are supplied by data and there are no remaining initializer effects. Its `$init` field starts true, and its redundant body/store can disappear. 2. **Completion at a program point:** normal return from CLInitNode establishes @@ -253,11 +283,13 @@ control-flow facts become available. A separate late must-analysis is optional, not a prerequisite for removing straightforward redundant checks. Carry known-initialized class identities with parser control flow, for example -as a BitSet in ScopeNode keyed by compilation-local class IDs. These are path -facts, not mutable global properties of ClassInit or its declared TypeStruct: +as a BitSet in ScopeNode keyed by the existing remapped `$init` alias IDs. These +are path facts, not mutable global properties of CompUnit or its declared +TypeStruct: -- On an active touch, record the dependency, then consult the facts. If C and - its required ancestors are known ready, omit the CLInitNode. +- On an active touch, consult the facts. If C and its required ancestors are + known ready, omit the CLInitNode. Otherwise insert the obligation in the IR; + post-Opto analysis collects surviving requirements. - Normal return from CLInit(C) adds C and its required ancestors. Do not add every possible dependency: a conditional initializer may never touch one. - Copy facts on a branch and intersect them at a reachable merge. An abrupt @@ -339,7 +371,8 @@ without materializing every function body. Serialize: Do not serialize transient node references, a cached global topo index, or the runtime value of a dynamic flag as an unconditional type fact. A definition -and its imported declarations must resolve to the same ClassInit record. +and its imported declarations must resolve to the same owning CompUnit and +canonical class/flag identity. On load, register identities first, resolve parent/dependency edges second, then resolve function summaries and IR. Check conflicting owners, missing @@ -354,7 +387,7 @@ importing compiler inlines and removes its local checks. Ordinary function symbols and function-pointer constants are not replaced by checked wrappers. Do not serialize a parser's transient BitSet as unconditional entry knowledge. -Its local class IDs can change on reload; retained checks, control flow, and +Its local alias IDs can change on reload; retained checks, control flow, and explicit entry contracts must support any omitted checks. Recompute flow facts for loaded graphs and verify hidden-field ownership/layout and that the flag store belongs to `<clinit>`, not to each checking caller. @@ -438,37 +471,209 @@ export/startup mechanism is deferred; it must not require the native caller to invoke `<clinit>`. Existing native-linking tests are not evidence that this future initialization guarantee is already implemented. -## Implementation sequence and validation - -1. Add ClassInit identities and a distinct lazy dependency collection; preserve - passive class references. Add direct/function effect summaries and cycle - diagnostics, including unresolved external-call handling. -2. Serialize/load the directory and summaries. Validate combined graphs before - imported-body unlinking and at final composition. Preserve ordinary function - entries; establish startup handling and diagnostics for unsupported native - handoffs before claiming initialization coverage at the FFI boundary. -3. Add serializable CLInitNode IR, the hidden field in each class object, and - the flag Store in `<clinit>`. Use the same node for ordinary checks and - startup. Add parser flow tracking and the basic constant/dominating-check - peepholes as part of this implementation, rather than relying on a later - cleanup pass to remove every repeated check. -4. Refine flow proofs and fully-static classification. Extend constant-memory - lowering only with the required observation/identity proofs. - -Validation should cover the actual boundaries, with a small number of focused -fixtures: parent-before-child order; an untouched branch performing no I/O; -two callers executing one initializer once; direct, indirect, sibling and -cross-module cycle rejection; passive/static reference cycles; a shared class -and flag reached through two separately compiled importers; a join/loop where -the first check cannot be removed; and rejection of unsupported native class -handoffs. Check function-pointer acquisition at the class field, with no new -ordinary function wrapper. Check parser omission and ideal elimination separately: a dominating -check, a true-test branch, an unchecked merge arm, and a zero-trip loop. Verify -one body-owned flag store before inlining, and that folding its early true -value cannot hide a cycle or bypass field initialization checks. Preserve entry -arguments/results and verify after serialization reload. -Run existing Chapter 25 suites and ARM/RISC/native execution checks for each -implementation frontier. No earlier-chapter backport is implied by this design. +## Implementation sequence + +Implement in Chapter 25 only, with the following reviewable checkpoints. Keep +existing source/native entry conventions and pointer widths. Each checkpoint +must build; do not claim the runtime guarantee until the executable protocol, +serialization, and final-composition validation are all present. + +### 1. CompUnit dependencies and cycle checking + +Implemented for review (2026-10-10). Files: `CompUnit.java`, `ParseAll.java`, +`Parser.java`, `ClassInitDependencies.java`, `CLInitNode.java`, `CallEndNode.java`, +`Opto.java`, and `CodeGen.java`. Generic `Node` needs no changes. + +- CompUnit holds direct `_classInitDeps`, `_initComplete`, + and reserved `_initStatic`. Existing file-discovery `_deps` is unchanged. + Diagnostic witnesses remain local to the dependency check. +- Parser inserts a control-flow CLInitNode for an active class-field touch or + a receiver whose class is not yet resolved. Ordinary instance receivers + fold the obligation away when resolved. Passive references and direct + own-initializer field accesses do not insert a check. +- This checkpoint's ideal node has control at input 0 and receiver at input 1; + it neither consumes nor produces memory yet. The full runtime form described + above will add memory at slot 1 and move the receiver to slot 2. No hidden + flag or runtime initialization call is generated in this checkpoint. +- After Opto, the collector walks live control forwards in each surviving + function, reads final call-target sets, and propagates sparse may-touch + summaries. Ordinary helper inlining naturally relocates its checks into the + caller. Class initializers are not inlined before validation. +- Reachable nonreturning calls retain a conservative CallEnd during dataflow. + Calls left out-of-line retain their continuations, so otherwise unreachable + touches after them can contribute initialization dependencies. This extra + ordering is accepted; users can remove such unreachable code. + Inlining discovers bodies forwards from their entry, including non-exiting + paths, and explicitly retains the Return node even when disconnected from + executable control. Nonreturning functions can therefore inline normally. +- TypeCheck builds fresh CompUnit requirements from those summaries and parent + edges. It rejects cycles with source/call witnesses and computes a stable + prerequisite-first order. No source-history or Node watcher table is kept. +- Following validation, the temporary CLInit obligations are erased for the + existing backend. Executable lowering and serialized obligations remain + later checkpoints. The full lazy-initialization runtime guarantee is not + implemented by this batch. + +Imported bodies, native calls, and unresolved targets leave `_initComplete` +false; the returned order covers known edges and is not a completeness +certificate. `_initStatic` remains false until static classification is added. + +Validation covers direct, helper-mediated, forward, conditional, indirect, +sibling, and parent/child cycles; legal ordinary recursion and passive +references; unknown native/imported effects; dependencies eliminated by SCCP; +unused helpers; discarded field values; and effects before versus after a +nonreturning call. Cycle and optimized-target cases run with three worklist +seeds. A bounded Eval2 run verifies that a retained nonreturning call executes +rather than falling through; its x86, ARM, and RISC-V encoding checks also pass. +All 492 tests in the parallel Chapter 25 Make suite pass. The encoding checks +were added afterward and pass in the focused suite. Two existing RISC-V spill +expectations change from 9 to 7; execution and allocation checks pass. +Generated fixtures are under +`chapter25/build/init-deps/`; full-suite logs are under `build/init-deps-opto*.log`. + +### 2. Serializable flags and dependency summaries + +Files: `Parser.java`, `Serialize.java`, `ElfReader.java`, `GlobalBits.java`, +`ParseAll.java`, and `StaticData.java`. + +- Add hidden `$init` fields with the normal field/alias/layout mechanism before + `freezePublicInterface()`. Declared flag type is boolean; initial image value + is false unless static initialization has been proved. Do not make a dynamic + flag's declared type the constant false. +- Serialize per-unit initialization metadata and function may-touch summaries + in `.simple`, early enough for graph validation without loading every body. + Preserve stable owner/alias/function identities and diagnostic witnesses. +- Register imported units first, resolve/remap edges and hidden fields second, + then validate the combined graph. Neither a module-local topological order + nor a summary from an older object file is a final-link proof. +- Keep metadata for fully static or body-eliminated units. Rebuild objects + under the existing unversioned `C0DE` convention; add no compatibility layer. + +Checkpoint: a two-module cycle rejected from source is also rejected after +serialization; an acyclic diamond resolves to one shared class and flag. +Two local topo orders can be merged even when their modules must interleave. + +### 3. CLInitNode and the executable protocol + +Files: new `node/CLInitNode.java`; `Node.java`, `Parser.java`, `CodeGen.java`, +`Serialize.java`, `Eval2.java`, and the printer adapters as needed. + +- Add an effectful, serializable CLInitNode targeting the resolved CompUnit, + with control/memory inputs and outputs in slots 0/1. Pending targets remain + explicit until resolved. Its type computation is conservative about the + initializer's whole memory effects; final normal output guarantees completion. +- Integrate its possible call with existing Call/CallEnd linking, argument and + return propagation, and body liveness. A reference to CompUnit metadata alone + must not let SCCP discard the initializer as uncalled. Reuse the call machinery + or a generated guard helper, rather than implementing a second independent + calling convention in the node. Test an out-of-line imported initializer as + well as an inlined one. +- Insert checks at class-field accesses, including function-pointer loads; + use the same operation for required instance creation and startup. Do not + instrument ordinary function headers or rewrite their function-pointer data. +- Insert `$init = true` once in each dynamic `<clinit>` body, naturally at entry. + The checking node performs the test/conditional call and contains no store. + A false startup test becomes a direct call preserving `arg` and the result. +- Give Eval2 the same shared-object/flag behavior. Lower checks to existing + control, memory, and call IR for machine compilation; use an out-of-line + helper if necessary rather than adding target-specific machine operations. +- Reject the presently unsupported native class/raw-initializer handoffs. Keep + ordinary checked-field function pointers unchanged. Do not add an explicit + initialization obligation to C drivers or other native callers. Direct native + entry into a dynamic class remains outside the new guarantee until a + compiler-managed startup/export mechanism exists. + +Checkpoint: sequential touches run the body once; parent effects precede child +initialization; an untaken branch runs no child code. Verify result/argument +preservation and flag sharing in Eval2, ARM/RISC emulation, and native execution +through Simple startup. Existing direct native tests must not be mistaken for +coverage of the deferred dynamic-export case. + +### 4. Parser flow and ideal simplification + +Files: `ScopeNode.java`, `Parser.java`, `CLInitNode.java`, and existing +control/memory lookup helpers. + +- Add path-local known-initialized facts to ScopeNode. Copy in `dup`, intersect + reachable predecessors in merges, and respect entry/backedge distinctions in + loop completion, break, continue, and return handling. The established + control/memory path must justify each check omitted by the parser. +- Implement constant-true, constant-false, preceding dominating CLInit, and + dominating true-test peepholes. Use dependencies to revisit proofs after SCCP + or inlining sharpens values. Keep remaining parent requirements when only a + child's own body is static. +- Preserve initialization effects when folding field loads into function + constants. Never hoist a check onto a path that previously did not touch the + class. Do not confuse an early true flag inside `<clinit>` with permission + to read that initializer's unfinished fields. +- Add fully-static classification using the initializer body and its effects, + excluding the generated flag store from the test. Emit a true initial flag + only after proof; remove the now-redundant body/store/checks. Extend mutable + constant-field lowering only where observations during initialization remain + correct. Do not use classification to erase evidence of a genuine cycle. + +Checkpoint: distinguish a dominating check from a one-arm-only check, a +zero-trip loop from a definitely executed touch, and a static child from an +unfinished dynamic parent. Check that early flag folding cannot hide a cycle. + +### 5. Phase ordering and final composition + +Files: `CodeGen.java`, `ParseAll.java`, `Serialize.java`, `ElfReader.java`, +`Main.java`, and the native linking path in `TestC.java` as appropriate. + +The current driver runs parse, Iter, Opto, TypeCheck, LoopTree, +`unlinkImports`, serialization, then selection and scheduling. Add explicit +initialization-analysis boundaries without relying on a particular peephole +worklist order: + +1. During parse/load, register identities and represent active initialization + obligations in ideal IR. Ordinary Opto resolves targets and removes dead + control; do not collect a historical union of temporary types or calls. +2. After Opto finishes, collect surviving CLInitNodes and calls, complete + function summaries, classify provably static work without circular + assumptions, and validate the graph. Any remaining unknown required + initialization effects prevent certification. +3. Before `unlinkImports`, retain imported summaries needed for validation and + serialization. Serialize ideal CLInitNodes and their proof-bearing control + and memory edges, plus the independent requirements. +4. Lower remaining CLInitNodes before final loop-tree construction and machine + selection. Because lowering introduces branches/calls, rebuild affected + control information and run ordinary ideal/type validation on that graph. + Move the final LoopTree step if needed rather than using a stale tree from + before expansion. Keep the serialized representation ideal and reloadable. + Ensure the generated call participates in call linking before the final + unlink step; imported bodies may remain represented by symbolic targets. +5. Before native executable composition, load metadata for the exact full + Simple object set being linked, merge requirements, and validate again. + A plain GCC/ELF link is not an initialization-graph checker. Do the same + validation for a complete in-memory image. + +If optimization or loading discovers another target, mark summaries dirty and +rerun validation before emission. No runtime `initializing` state is introduced; +compile-time DFS bookkeeping is independent of the single runtime flag. + +Checkpoint: source, imported ideal IR, and final linked metadata agree on +acceptance/rejection for equivalent optimized graphs. Exercise different +worklist seeds and object-discovery orders to check determinism; eliminated +branches and targets must not leave stale dependencies. Missing required +metadata fails diagnostically. + +### Validation and scope + +Use a small set of focused fixtures covering several boundaries each, plus the +existing full Chapter 25 Make suites. Include effects before a nonreturning +call so dependency checking cannot accidentally depend on returned memory. +Exercise duplicate touches, conditional cycles, native-handoff diagnostics, +serialization alias remapping, class/flag ownership, and normal startup results. +Run the fixed allocation cohorts only after runtime semantics stabilize; graph +and spill changes are expected, and any new golden counts must follow execution +and register-correctness checks. Keep Jig tests ignored. + +Do not backport this feature, change pointer widths, introduce concurrent or +recoverable initialization, add dynamic module loading, or solve the general +native-export policy in these checkpoints. The extra analysis-only alias slice +remains an alternative representation if explicit summaries prove awkward; +implementing both would add work without improving the initial guarantee. ## Module goals retained from the old notes diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java index cd80b3ff..a6afc91f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java @@ -2297,6 +2297,15 @@ public class Parser { fld = fieldOrOpen(ts,name,false); if( fld==null && ts!=null && !latestStruct(ts)._open ) throw error("Accessing unknown field '"+name+"' from '*"+ts._name+"'"); + + // We have to record "active touches" of a new class, to track when we + // need to force class initialization. Basically, we insert an CLInit, + // and if it does not fold away it'll turn into a runtime check. + Kind.Func func = (Kind.Func)_scope._kinds.at(_scope.enclosingFuncOrDecl()); + if( (ts==null || ts==TypeStruct.BOT || ts.isHigh() || startsClzPrefix(ts._name)) && + !(ts!=null && (ts._name+".<clinit>").equals(func._name)) ) + ctrl(new CLInitNode(loc(),name,ctrl(),expr).peephole()); + // With no field, we will update the bulk memory int alias = fld==null ? 1 : fld._alias; Type decl = fld==null ? Type.BOTTOM : fld._t; @@ -2694,6 +2703,8 @@ public class Parser { return that != null && _input == that._input && _position < that._position; } + public String position() { return _line_number+":"+(_position-_line_start+1); } + /** * Record the source text for lexing */ diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java new file mode 100644 index 00000000..96bdbb33 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java @@ -0,0 +1,176 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.*; + +/** Initialization requirements of the optimized, executable graph. */ +public final class ClassInitDependencies { + private final CodeGen code; + private ArrayList<CompUnit> order; + + private static final class Effects { + final FunNode fun; + final TreeMap<String,String> touches = new TreeMap<>(); + final LinkedHashMap<Effects,String> callers = new LinkedHashMap<>(); + boolean complete; + Effects(FunNode fun, boolean complete) { this.fun=fun; this.complete=complete; } + } + + public ClassInitDependencies(CodeGen code) { this.code=code; } + public void invalidate() { order=null; } + + // Resolve named class objects, including static nested class objects in a file. + private CompUnit owner(String name) { + name=name.substring(Parser.CLZ.length()); + CompUnit best=null; + for( CompUnit cu : code._compunits.values() ) + if( cu._cname!=null && (name.equals(cu._cname) || name.startsWith(cu._cname+".")) && + (best==null || cu._cname.length()>best._cname.length()) ) best=cu; + return best; + } + + private static String reason(FunNode fun, String what, Parser.Lexer loc) { + return fun._compunit._cname+" ("+fun.label()+"): "+what+ + (loc==null ? "" : " at "+loc.position()); + } + + // Walk control forwards, not backwards from Return: a live touch before an + // infinite loop or nonreturning call must still contribute. Never cross a + // function boundary through Call -> Fun or Return -> CallEnd graph edges. + private void scan(Effects fx, TreeMap<Integer,Effects> functions) { + ArrayDeque<CFGNode> work=new ArrayDeque<>(); + BitSet seen=new BitSet(); + work.add(fx.fun); + while( !work.isEmpty() ) { + CFGNode cfg=work.remove(); + if( seen.get(cfg._nid) || cfg._type.isHigh() ) continue; + seen.set(cfg._nid); + if( cfg instanceof CLInitNode init ) { + if( init.ptr()._type instanceof TypeMemPtr ptr && ptr._obj!=TypeStruct.BOT && !ptr._obj.isHigh() ) { + if( Parser.startsClzPrefix(ptr._obj._name) ) { + CompUnit target=owner(ptr._obj._name); + if( target==null ) fx.complete=false; + else fx.touches.putIfAbsent(target._cname,reason(fx.fun,"field "+init._field,init._loc)); + } + } else fx.complete=false; + } + if( cfg instanceof CallNode call ) { + String why=reason(fx.fun,"call",call._loc); + if( call.fptr()._type instanceof TypeFunPtr fp && !XInt.isHigh(fp.fidxs()) && fp.nfcns()>0 ) { + for( int id=XInt.next(fp.fidxs(),0); id>=0; id=XInt.next(fp.fidxs(),id) ) { + Effects callee=functions.get(id); + if( callee==null ) { fx.complete=false; continue; } + if( callee.fun.isClz() ) + fx.touches.putIfAbsent(callee.fun._compunit._cname,why); + else callee.callers.putIfAbsent(fx,why); + } + } else fx.complete=false; + } + if( cfg instanceof ReturnNode ) continue; + for( Node use : cfg._outputs ) { + if( !(use instanceof CFGNode next) || next instanceof FunNode || next instanceof StopNode ) continue; + if( next instanceof RegionNode r ) { + if( r._inputs.find(cfg)>0 ) work.add(r); + } else if( next.in(0)==cfg ) work.add(next); + } + } + } + + /** Reject post-Opto cycles; incomplete imports/native effects are NOT certified. */ + public void check() { + if( order!=null ) return; + assert code._phase.ordinal() >= CodeGen.Phase.Opto.ordinal(); + TreeMap<Integer,Effects> functions=new TreeMap<>(); + code._start.walk(n -> { + if( n instanceof FunNode fun && !fun.isDead() && !fun._type.isHigh() ) + functions.put(fun.sig().fidx(),new Effects(fun,code.owns(fun))); + return null; + }); + for( Effects fx : functions.values() ) scan(fx,functions); + + // Recursive ordinary functions converge; only class requirements form + // initialization edges. This uses final call targets, never old types. + ArrayDeque<Effects> work=new ArrayDeque<>(functions.values()); + HashSet<Effects> queued=new HashSet<>(functions.values()); + while( !work.isEmpty() ) { + Effects callee=work.remove(); + queued.remove(callee); + for( var edge : callee.callers.entrySet() ) { + Effects caller=edge.getKey(); + boolean changed=false; + for( var touch : callee.touches.entrySet() ) + if( caller.touches.putIfAbsent(touch.getKey(),edge.getValue()+"; then "+touch.getValue())==null ) changed=true; + if( caller.complete && !callee.complete ) { caller.complete=false; changed=true; } + if( changed && queued.add(caller) ) work.add(caller); + } + } + TreeMap<String,CompUnit> units=new TreeMap<>(); + // Reuse local initializer summaries for diagnostics; no witnesses are + // retained on CompUnit or on this checker after validation returns. + IdentityHashMap<CompUnit,TreeMap<String,String>> reasons=new IdentityHashMap<>(); + for( CompUnit cu : code._compunits.values() ) + if( cu._cname!=null ) { + units.put(cu._cname,cu); + cu._classInitDeps=null; + cu._initComplete=false; // Imported summaries arrive in checkpoint 2. + if( cu._par!=null ) cu.addClassInitDep(code,cu._par); + } + for( Effects fx : functions.values() ) + if( fx.fun.isClz() ) { + CompUnit cu=fx.fun._compunit; + cu._initComplete=fx.complete; + reasons.put(cu,fx.touches); + for( String target : fx.touches.keySet() ) cu.addClassInitDep(code,units.get(target)); + } + ArrayList<CompUnit> sorted=new ArrayList<>(), path=new ArrayList<>(); + IdentityHashMap<CompUnit,Integer> colors=new IdentityHashMap<>(); + for( CompUnit cu : units.values() ) visit(cu,colors,path,sorted,reasons); + for( CompUnit cu : sorted ) + if( cu._classInitDeps!=null ) + for( CompUnit dep : cu._classInitDeps ) cu._initComplete &= dep._initComplete; + order=sorted; + } + + // Temporary checkpoint lowering: retain existing runtime behavior. Later + // this becomes flag-and-call lowering, and obligations survive serialization. + public void eraseChecks() { + ArrayList<CLInitNode> checks=new ArrayList<>(); + code._start.walk(n -> { if( n instanceof CLInitNode init ) checks.add(init); return null; }); + for( CLInitNode init : checks ) + if( !init.isDead() ) init.subsume(init.in(0)); + code.invalidateIDepthCaches(); + } + + private void visit(CompUnit cu, IdentityHashMap<CompUnit,Integer> colors, + ArrayList<CompUnit> path, ArrayList<CompUnit> sorted, + IdentityHashMap<CompUnit,TreeMap<String,String>> reasons) { + Integer color=colors.get(cu); + if( color!=null ) { + if( color==2 ) return; + int start=path.indexOf(cu); + StringBuilder message=new StringBuilder("Cyclic class initialization: "); + for( int i=start; i<path.size(); i++ ) message.append(path.get(i)._cname).append(" -> "); + message.append(cu._cname); + for( int i=start; i<path.size(); i++ ) { + CompUnit from=path.get(i), to=i+1<path.size() ? path.get(i+1) : cu; + message.append("\n ").append(from._cname).append(" -> ").append(to._cname) + .append(": ").append(from._par==to ? "parent of "+from._cname : reasons.get(from).get(to._cname)); + } + throw Parser.error(message.toString(),null); + } + colors.put(cu,1); + path.add(cu); + ArrayList<CompUnit> deps=new ArrayList<>(); + if( cu._classInitDeps!=null ) for( CompUnit dep : cu._classInitDeps ) deps.add(dep); + deps.sort(Comparator.comparing(dep -> dep._cname)); + for( CompUnit dep : deps ) visit(dep,colors,path,sorted,reasons); + path.removeLast(); + colors.put(cu,2); + sorted.add(cu); + } + + /** Prerequisite-first order of the known graph, not a completeness certificate. */ + public ArrayList<CompUnit> order() { check(); return new ArrayList<>(order); } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 6fc66e4f..bc86dc6d 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -82,6 +82,7 @@ public class CodeGen { // Compilation Units in this compile; one per source/object file public HashMap<String,CompUnit> _compunits; + public final ClassInitDependencies _classInitDeps = new ClassInitDependencies(this); // Test shortcut for only one compilation unit public CompUnit compunit() { assert _compunits.size()==1; @@ -534,6 +535,11 @@ public class CodeGen { _phase = Phase.TypeCheck; long t0 = System.currentTimeMillis(); + // Check for class-init cycles first; such a cycle can prevent other + // things from resolving types. Get the classes ordered and init'd + // before reporting other errors. + _classInitDeps.check(); + final Ary<Node> errs = new Ary<>(Node.class); _stop.walk( n -> { if( n.err() != null ) @@ -572,6 +578,7 @@ public class CodeGen { if( _obs != null ) _obs.error(null, err.getMessage()); throw err; } + _classInitDeps.eraseChecks(); if( _obs != null ) _obs.phase("TypeCheck"); return this; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java index d1326cee..6d84c955 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -16,19 +16,38 @@ import static com.seaofnodes.simple.codegen.CodeGen.CODE; // files. These are mirrored over a file system tree (so form a tree), both // the source tree and build/object tree. public class CompUnit { - public final CompUnit _par; // Parent, e.g. A/B + public final CompUnit _par; // Parent, e.g. A/B final String _fname; // Full slashed file name starting from module root, e.g. A/B/C final public String _cname; // Full dotted class name starting from module root, e.g. A.B.C final String _name; // Base name, e.g. C final ExternNode _ext; // Found in external libs; e.g. libc final File _smp; // Simple source file, e.g. module_root/A/B/C.smp - public final File _obj; // ELF output file, e.g. build/A/B/C.o + public final File _obj; // ELF output file, e.g. build/A/B/C.o final public String _src; // Source code, from file or test case - //public Encoding _encoding; // Encoding for output public TypeStruct _clz; // The one TypeStruct being published - //BAOS _serial; // Serialized IR for this ELF file - Ary<CompUnit> _deps; // CompUnits that this CompUnit depends on + + // _deps records units required for types, code, or class references, + // without requiring their initializers to run. These discovery/rebuild + // dependencies may form a cycle. + Ary<CompUnit> _deps; + + // _classInitDeps records units whose initialization this initializer may + // require after Opto, including its parent; these edges must form a DAG. + // Initialization prerequisites are a subset of the units that must be + // available, but not necessarily of the direct _deps list: parent links + // and helper-call effects can add initialization edges to units discovered + // indirectly. + public Ary<CompUnit> _classInitDeps; + + // Set after completing the cycle analysis for the <clinit> (and + // prerequisites). + public boolean _initComplete; + + // This unit's own initializer is proven fully represented by static data + // and needs no execution; its ancestors may still need initialization. + // Reserved for static classification; currently always false. + public boolean _initStatic; // Per-Compilation-Unit Start/StopNodes, keeping alive all exported Nodes. // Null means no code loaded (yet). @@ -123,6 +142,15 @@ public class CompUnit { } + public boolean addClassInitDep(CodeGen code, CompUnit target) { + if( _classInitDeps==null ) _classInitDeps=new Ary<>(CompUnit.class); + if( _classInitDeps.find(target)!=-1 ) return false; + _classInitDeps.add(target); + code._classInitDeps.invalidate(); + return true; + } + + @Override public String toString() { String x = "{"+_cname; if( _smp!=null && _smp.exists()) x += ",hasSMP"; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 132705aa..efdcff6c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -59,7 +59,6 @@ abstract public class Opto { // Propagate field size constants code._iter.iterate(code); - // Retain surviving functions in their CompUnits for later code // emission. Start inputs are semantic: they mean unknown callers. for( FunNode fun : code._linker ) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 90309328..155066a4 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -42,6 +42,7 @@ public abstract class ParseAll { if( cunit != null ) return cunit; String cname = par==null ? name : (par._cname + "." + name).intern(); code._compunits.put(fname, cunit = external ? new CompUnit(obj,par,fname,cname,name) : new CompUnit(par,fname,cname,name)); + code._classInitDeps.invalidate(); return cunit; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 27253c5e..ce546318 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -508,8 +508,9 @@ abstract public class Serialize { // Whole CompUnits have no users, went dead if( cu._start != null && !cu._start.isDead() ) { nodes.add(cu._start); - // Memory proj - nodes.add(cu._start.proj(1)); + // A memory-free, nonreturning unit can lose its memory projection. + ProjNode mem=cu._start.proj(1); + if( mem!=null ) nodes.add(mem); // All the functions, including internal ones, in comp-unit order for( FunNode fun : code._linker ) if( fun!=null && !fun.isDead() && fun._compunit == cu ) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java new file mode 100644 index 00000000..f00d8076 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.*; + +/** An active class touch, retained in control until initialization validation. + * This checkpoint records the obligation only; flag/call lowering comes later. + */ +public class CLInitNode extends CFGNode { + public final Parser.Lexer _loc; + public final String _field; + + public CLInitNode(Parser.Lexer loc, String field, Node ctrl, Node ptr) { + super(ctrl,ptr); + _loc=loc; + _field=field; + } + + public Node ptr() { return in(1); } + @Override public String label() { return "CLInit"; } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("CLInit ").p(ptr()); } + @Override public Type compute() { return in(0)._type; } + @Override public Node idealize() { + // A receiver discovered to be an ordinary instance needs no class init. + if( ptr()._type instanceof TypeMemPtr ptr && ptr._obj!=TypeStruct.BOT && + !ptr._obj.isHigh() && !Parser.startsClzPrefix(ptr._obj._name) ) return in(0); + return null; + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 35180fea..13e7ac12 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -17,8 +17,8 @@ public class CallEndNode extends CFGNode implements MultiNode { // When set true, this Call/CallEnd/Fun/Return is being trivially inlined boolean _folding; - // +2 must clone, so await all cleanup but OK - // +1 trivial now, + // +2: must clone, so await all cleanup but OK + // +1: trivial now, so can inline without cloning and without waiting for cleanup // 0: take a look, // -1: somethings wrong, but might improve // -2: never and stop asking, @@ -122,9 +122,10 @@ public class CallEndNode extends CFGNode implements MultiNode { state = (TypeTuple)state.meet(in(i)._type); // A reachable call whose presently linked exits are all unreachable // keeps a conservative continuation. In particular, do not let a - // transient no-return result tear down the caller during SCCP. - if( state.ctl()==Type.XCONTROL && - CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) + // transient no-return result tear down the caller before/during SCCP. + // If the call remains out-of-line, its continuation can conservatively + // contribute class-init dependencies even though it never executes. + if( state.ctl()==Type.XCONTROL ) return TypeTuple.make(Type.CONTROL,TypeMem.TOP,Type.TOP); // At least as good as the TFP return state.makeFrom(2,state.ret().join(tfp.ret())); @@ -158,7 +159,10 @@ public class CallEndNode extends CFGNode implements MultiNode { ReturnNode ret = (ReturnNode)in(1); FunNode fun = ret.fun(); - // Heuristic forced inlining off via name + // Preserve initializer boundaries until post-Opto cycle validation. + if( fun.isClz() ) return -2; + + // Heuristic forced inlining turned off via name if( fun._name != null && fun._name.endsWith("_noInline") ) return -2; // Never, stop asking @@ -168,7 +172,7 @@ public class CallEndNode extends CFGNode implements MultiNode { if( fun.cfg(i).fun()==fun ) // Check for linked call input inside "fun" { addDep(fun); return -1; } // No, but can lose the recursive edge - // Things that might improve, so not now a candidate + // Things that might improve, but not now a candidate Node fptr = call.fptr(); // Constant Function is being called, and its not-null if( !(fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && tfp.isConstant()) ) @@ -181,16 +185,16 @@ public class CallEndNode extends CFGNode implements MultiNode { // Encouraged inlining because small size and constructor. int maxSize = fun.inlineLimit(); // A large parse can leave only a tiny initializer. Recognize that - // without repeatedly walking the whole body while it shrinks. + // and await cleanup to shrink the body. if( fun._approxUIDs >= maxSize ) { if( !smallBody(fun) ) return -1; - } else if( fun.body().cardinality() >= maxSize ) + } else if( fun.body().cardinality() >= maxSize ) // Expensive size check return -1; // Try later (if cleanup makes the real body small enough) // Can be cloned but not trivial if( fun.nIns() > 2 ) { addDep(fun); return 2; } - // A candidate right now + // A trivial candidate right now return 1; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java index b74f9e6b..1e2ee10a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -252,15 +252,20 @@ public class FunNode extends RegionNode { // Build the function body set public BitSet body() { - // Reverse up (stop to start) CFG only, collect bitmap. + // Iter drains ordinary peeps between inlines; body discovery precedes + // this inline's folding, so function boundaries are stable. + assert !_folding; + // Forward control includes paths that never reach Return. BitSet cfgs = new BitSet(); - cfgs.set(_nid); - walkUp(ret(),cfgs ); + walkCFG(this,cfgs); + cfgs.set(ret()._nid); // Top down (start to stop) all flavors. CFG limit to bitmap. // If data use bottoms out in wrong CFG, returns false - but tries all outputs. // If any output hits an in-CFG use (e.g. phi), then keep node. BitSet body = new BitSet(); + // The function owns its Return even when it has no executable exit. + body.set(ret()._nid); BitSet visit = new BitSet(); int old; do { @@ -271,13 +276,15 @@ public class FunNode extends RegionNode { return body; } - private static void walkUp(CFGNode n, BitSet cfgs) { + private static void walkCFG(CFGNode n, BitSet cfgs) { if( cfgs.get(n._nid) ) return; cfgs.set(n._nid); - if( n instanceof RegionNode r ) - for( int i=1; i<n.nIns(); i++ ) - walkUp(n.cfg(i),cfgs); - else walkUp(n.cfg0(),cfgs); + if( n instanceof ReturnNode ) return; + for( Node use : n._outputs ) { + if( !(use instanceof CFGNode cfg) || cfg instanceof FunNode ) continue; + if( cfg instanceof RegionNode ? cfg._inputs.find(n)>0 : cfg.in(0)==n ) + walkCFG(cfg,cfgs); + } } private static boolean walkDown( Node n, BitSet cfgs, BitSet body, BitSet visit ) { @@ -285,12 +292,12 @@ public class FunNode extends RegionNode { if( visit.get(n._nid) ) return body.get(n._nid); visit.set(n._nid); // Visit self as CFG outside the function - if( n instanceof CFGNode && !cfgs.get(n._nid) && unfolded( n ) ) + if( n instanceof CFGNode && !cfgs.get(n._nid) ) return false; // Pretend the NewNode is a CFG, so its projections stay with it in loops if( n instanceof NewNode nnn ) cfgs.set(n._nid); // Visit n.cfg() outside of function - if( n.in(0)!=null && !cfgs.get(n.in(0)._nid) && unfolded( n.in( 0 ) ) ) + if( n.in(0)!=null && !cfgs.get(n.in(0)._nid) ) return false; // Phis inside the function must have their body flag set BEFORE // recursion walks around a loop and finds them again. @@ -308,15 +315,6 @@ public class FunNode extends RegionNode { return in; } - // A CFG is folding, and so is basically Data - private static boolean unfolded( Node cfg) { - if( cfg instanceof CallNode call && call.cend().folding() ) return false; - if( cfg instanceof CallEndNode cend && cend.folding() ) return false; - if( cfg instanceof FunNode fun && fun._folding ) return false; - if( cfg instanceof ReturnNode ret && ret._fun._folding ) return false; - return true; - } - // Clone function body. Give function a new FIDX. FunNode copyBody() { // Build the function body BitSet @@ -326,8 +324,10 @@ public class FunNode extends RegionNode { IdentityHashMap<Node,Node> map = new IdentityHashMap<>(); BitSet visit = CodeGen.CODE.visit(); bodyCopy( visit, body, map, this ); + bodyCopy( visit, body, map, _ret ); // May be disconnected from executable control. visit.clear(); bodyEdge( visit, body, map, this ); + bodyEdge( visit, body, map, _ret ); visit.clear(); assert map.size()==body.cardinality(); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index b46a54b2..5acfbc8f 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -217,7 +217,7 @@ for( int i=0; i<ary#-1; i++ ) return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; testCPU(src,"x86_64_v2", "SystemV",-1,"return mov(.[]);"); - testCPU(src,"riscv" , "SystemV", 9,"return (add,.[],(mul,.[],1000));"); + testCPU(src,"riscv" , "SystemV", 7,"return (add,.[],(mul,.[],1000));"); testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 0cfdb577..1f4913f0 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -324,7 +324,7 @@ for( int i=0; i<ary#-1; i++ ) return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; testCPU(src,"x86_64_v2", "SystemV",-1,"return mov(.[]);"); - testCPU(src,"riscv" , "SystemV", 9,"return (add,.[],(mul,.[],1000));"); + testCPU(src,"riscv" , "SystemV", 7,"return (add,.[],(mul,.[],1000));"); testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java index 354c6ec2..7522512e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -8,6 +8,8 @@ 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.LoopNode; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; import java.io.File; @@ -43,6 +45,25 @@ public class Chapter25Test { """).driver(CodeGen.Phase.Encoding,"riscv","SystemV"); } + @Test public void testInlineNeverExit() { + String[] sources={ + "val _spin={ -> while(1) {} return 1; }; _spin(); return 2;", + // Two callers require cloning, including the non-exiting arm. + "val _spin={int x -> if(x) while(1) {} return 7; }; return _spin(arg)+_spin(arg);" + }; + for( int i=0; i<sources.length; i++ ) { + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code=new CodeGen(sources[i],seed,true).driver(CodeGen.Phase.TypeCheck); + assertNull("Calls should inline",code._start.walk(n -> n instanceof CallNode ? n : null)); + assertNotNull("The non-exiting path must survive",code._start.walk(n -> n instanceof LoopNode && n!=code._start ? n : null)); + if( i==1 ) assertEquals("14",Eval2.eval(code,0,10)); + assertNull(Eval2.eval(code,1,10)); + } + for( String cpu : new String[]{"x86_64_v2","arm","riscv"} ) + new CheckedCodeGen(sources[i]).driver(CodeGen.Phase.Encoding,cpu,"SystemV"); + } + } + @Test public void testExternData() throws IOException { String src = """ diff --git a/chapter25/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java b/chapter25/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java new file mode 100644 index 00000000..db7c7ae4 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java @@ -0,0 +1,154 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.CompUnit; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.Ary; +import java.nio.file.Files; +import java.nio.file.Path; +import java.util.ArrayList; +import java.util.Comparator; +import java.util.Map; +import org.junit.Rule; +import org.junit.Test; +import org.junit.rules.TestRule; +import org.junit.runners.model.Statement; +import static org.junit.Assert.*; + +public class ClassInitDependenciesTest { + private final ArrayList<Path> dirs = new ArrayList<>(); + + @Rule public final TestRule cleanup = (test, description) -> new Statement() { + @Override public void evaluate() throws Throwable { + // Keep all fixtures if compilation or any later assertion fails. + test.evaluate(); + for( Path dir : dirs ) { + Path[] files; + try( var paths=Files.walk(dir) ) { + files=paths.sorted(Comparator.reverseOrder()).toArray(Path[]::new); + } + for( Path file : files ) Files.delete(file); + } + } + }; + + private Path tempDir(String prefix) throws Exception { + Path build=Path.of("build/init-deps"); + Files.createDirectories(build); + Path dir=Files.createTempDirectory(build,prefix); + dirs.add(dir); + return dir; + } + + private CodeGen compile(String entry, Map<String,String> sources, long seed) throws Exception { + Path root=tempDir("case-"); + Files.writeString(root.resolve("Root.smp"),"val entry="+entry+";"); + for( var source : sources.entrySet() ) { + Path path=root.resolve("Root/"+source.getKey()+".smp"); + Files.createDirectories(path.getParent()); + Files.writeString(path,source.getValue()); + } + return new CodeGen(root.toString(),root.resolve("obj").toString(),null, + "Root",null,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + } + + private void cycle(String entry, Map<String,String> sources, String expected) throws Exception { + expected="Root."+expected.replace(" -> "," -> Root."); + for( long seed : new long[]{1,123,987654321} ) { + try { compile(entry,sources,seed); fail("Expected initialization cycle"); } + catch( Parser.ParseException ex ) { + assertTrue(ex.getMessage(),ex.getMessage().startsWith("Cyclic class initialization: "+expected)); + assertTrue("Include a source witness",ex.getMessage().contains(" at 1:")); + } + } + } + + @Test public void testOrderAndPassiveReferences() throws Exception { + CodeGen code = compile("A",Map.of("A","int value=B.value;", "B","int value=arg|1;"),123); + assertEquals("[Root, Root.B, Root.A]",code._classInitDeps.order().stream().map(c -> c._cname).toList().toString()); + assertTrue(code._compunits.get("Root/A")._initComplete); + code=compile("A",Map.of("A","val b=B;", "B","val a=A;"),123); + for( CompUnit cu : code._classInitDeps.order() ) { + if( cu._par==null ) assertNull(cu._classInitDeps); + else { + assertEquals(1,cu._classInitDeps.size()); + assertSame(cu._par,cu._classInitDeps.at(0)); + } + assertTrue(cu._initComplete); + } + } + + @Test public void testCycles() throws Exception { + cycle("A",Map.of("A","int value=B.value;", "B","int value=A.value;"),"A -> B -> A"); + cycle("A",Map.of("A","val get={ -> B.value; }; int value=get();", + "B","int value=A.value;"),"A -> B -> A"); + cycle("A",Map.of("A","int value=get(); val get={ -> B.value; };", + "B","int value=A.value;"),"A -> B -> A"); + cycle("A",Map.of("A","int value=0; if(arg) value=B.value;", + "B","int value=A.value;"),"A -> B -> A"); + cycle("A",Map.of("A","val f=arg ? { -> B.value; } : { -> 0; }; int value=f();", + "B","int value=A.value;"),"A -> B -> A"); + cycle("P",Map.of("P","int value=A.value;", "P/A","int value=arg;"),"P -> P.A -> P"); + } + + @Test public void testSiblingsAndNonreturningCall() throws Exception { + cycle("P",Map.of("P","val a=A; val b=B;", "P/A","int value=B.value;", + "P/B","int value=A.value;"),"P.A -> P.B -> P.A"); + cycle("A",Map.of("A","val get={ -> val x=B.value; while(1) {} return x; }; int value=get();", + "B","int value=A.value;"),"A -> B -> A"); + // An out-of-line nonreturning call retains its continuation's touches. + cycle("A",Map.of( + "A","int value=1; val stop_noInline={ -> while(1) {} return 1; }; stop_noInline(); return B.value;", + "B","int value=A.value;"),"A -> B -> A"); + String source="val stop_noInline={ -> while(1) {} return 1; }; stop_noInline(); return 2;"; + CodeGen code=new CodeGen(source).driver(CodeGen.Phase.TypeCheck); + assertNull(Eval2.eval(code,0,10)); // Evaluation reaches its loop budget. + for( String cpu : new String[]{"x86_64_v2","arm","riscv"} ) + new CodeGen(source).driver(CodeGen.Phase.Encoding,cpu,"SystemV"); + } + + @Test public void testOptimizedDependencies() throws Exception { + for( long seed : new long[]{1,123,987654321} ) { + // SCCP learns this condition from a call; the parser cannot decide it. + CodeGen code=compile("A",Map.of( + "A","val test_noInline={ -> false; }; int value=1; if(test_noInline()) value=B.value;", + "B","int value=A.value;"),seed); + CompUnit a=code._compunits.get("Root/A"), b=code._compunits.get("Root/B"); + assertTrue(a._initComplete); + assertEquals(-1,a._classInitDeps.find(b)); + assertTrue(b._classInitDeps.find(a)>=0); + + code=compile("A",Map.of( + "A","val test_noInline={ -> false; }; val f=test_noInline() ? { -> B.value; } : { -> 1; }; int value=f();", + "B","int value=A.value;"),seed); + a=code._compunits.get("Root/A"); b=code._compunits.get("Root/B"); + assertTrue(a._initComplete); + assertEquals(-1,a._classInitDeps.find(b)); + + // An unused helper's body must not become an initializer dependency. + code=compile("A",Map.of("A","val unused={ -> B.value; }; int value=1;", + "B","int value=A.value;"),seed); + assertEquals(-1,code._compunits.get("Root/A")._classInitDeps.find(code._compunits.get("Root/B"))); + } + // Discarding the value of a field read cannot discard its active touch. + cycle("A",Map.of("A","int value=1; B.value; return 0;", + "B","int value=2; A.value; return 0;"),"A -> B -> A"); + } + + @Test public void testRecursionAndIncompleteEffects() throws Exception { + CodeGen code=compile("A",Map.of("A","val f={int n -> n ? f(n-1) : B.value; }; int value=f(arg);", + "B","int value=arg|1;"),123); + assertTrue(code._compunits.get("Root/A")._initComplete); + assertTrue(code._compunits.get("Root/A")._classInitDeps.find(code._compunits.get("Root/B"))>=0); + code=compile("A",Map.of("A","{int} native=\"C\"; return native();"),123); + assertFalse("Unknown native effects are not certified empty",code._compunits.get("Root/A")._initComplete); + + Path dir=tempDir("import-"); + new CodeGen(null,dir.toString(),null,"B","int value=1;",123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "A","return B.value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + assertFalse("Imported summaries wait for checkpoint 2",code._compunits.get("B")._initComplete); + assertFalse(code._compunits.get("A")._initComplete); + } +} diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestRunner.java b/chapter25/src/test/java/com/seaofnodes/simple/TestRunner.java new file mode 100644 index 00000000..5389967e --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestRunner.java @@ -0,0 +1,17 @@ +package com.seaofnodes.simple; + +import org.junit.internal.TextListener; +import org.junit.runner.JUnitCore; +import org.junit.runner.Request; + +/** Make's single-class/single-method JUnit entry point. */ +public class TestRunner { + public static void main(String[] args) throws ClassNotFoundException { + String name=args[0]; + Class<?> test=Class.forName(name.contains(".") ? name : "com.seaofnodes.simple."+name); + Request request=args[1].isEmpty() ? Request.aClass(test) : Request.method(test,args[1]); + JUnitCore runner=new JUnitCore(); + runner.addListener(new TextListener(System.out)); + System.exit(runner.run(request).wasSuccessful() ? 0 : 1); + } +} diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index c7b3706e..5b9df53a 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -567,10 +567,42 @@ active touch, after its parent completes. Passive class references do not trigger execution. Reject initialization cycles across modules; there is no early parent-ready point. Untouched classes execute no initialization code. The [lazy initialization design](../chapter25/initialization.md) covers the -proposed ClassInit metadata owned by CompUnit, CLInitNode checks with parser-flow +proposed initialization dependencies directly on CompUnit, CLInitNode checks with parser-flow and ideal simplification, a hidden `$init` field set inside `<clinit>`, static -proofs, and serialization/composition validation. Those mechanisms are -design work, not implemented by the constant-field lowering above. +proofs, and serialization/composition validation. The constant-field lowering +above does not implement the runtime initialization protocol. +The [implementation checkpoints](../chapter25/initialization.md#implementation-sequence) +choose CompUnit dependency edges and function may-touch summaries for cycle +checking, separately from ordinary alias-memory facts for runtime `$init`. +No separate ClassInit object or analysis-only memory slice is planned initially. + +**Checkpoint 1 revised for review (2026-10-10):** initialization cycles now +count only requirements surviving Opto. Parser inserts ideal CLInit obligations +on control; the collector walks optimized function bodies and propagates their +final call-target effects into CompUnit dependencies. Removed branches/targets +leave no historical edges. All generic Node watcher hooks are removed. Parent +edges, cycle witnesses, and stable topological ordering remain. Nonreturning +calls left out-of-line retain conservative continuations; touches after them +can contribute extra initialization ordering. The ideal obligations are erased +after validation for this checkpoint; +runtime flags/calls and serialized summaries are still pending. Imported/native/ +unresolved effects remain explicitly incomplete and `_initStatic` remains false. +All 492 Chapter 25 tests pass, plus focused x86/ARM/RISC-V encoding checks for +the nonreturning-call fix added after the full run. Two existing RISC-V spill +expectations improve from 9 to 7. Log: `build/init-deps-opto-final.log`. +See the [checkpoint notes](../chapter25/initialization.md#1-compunit-dependencies-and-cycle-checking). + +**Non-exiting function inlining (2026-10-10):** general body cloning starts in +Chapter 25. Chapters 20-24 clone only restricted straight-line boilerplate; +their older `FunNode.body()` helpers have no callers. Chapter 25 now discovers +body control forwards from Fun, including infinite-loop arms, and explicitly +copies its Return even when that node has no executable incoming control. +The nonreturning-inline guard is removed. Serialization also permits a unit +whose unused memory projection disappeared. The regression covers a wholly +non-exiting function and a two-call function with both returning and infinite +arms, checking inlining and Eval2 behavior across three seeds and all three +machine encoders with allocation checks. All 493 Chapter 25 tests pass; +log: `build/inline-never-exit.log`. Changing data-pointer width and moving fully initialized class objects to read-only storage remain separate follow-ons. |