# Reachability Analysis & Codegen Specialization (RTA) This directory implements the whole-program reachability analysis and monomorphization/specialization pass for the Zena self-hosted compiler. ## Design Overview In WebAssembly GC, having concrete struct and vtable definitions is required before code generation. To minimize the compiled code size and Wasm type section complexity, Zena utilizes a whole-program reachability analysis that performs **Rapid Type Analysis (RTA)**. Instead of generating structures and function signatures for every class/interface or generic overload, the reachability pass starts at entry point roots (e.g. `main` or exports) and iteratively traverses reached functions and types. As new instantiations (`new Point()`) and dynamic dispatches are encountered, the pass resolves implementing virtual method overloads and queues them for traversal. ## Component Subsystems To keep the codebase maintainable and maintain low AST traversal overhead, the reachability analysis is broken down into four cooperating modules: ```mermaid graph TD Analysis["ReachabilityAnalysis (analysis.zena)"] Visitor["ReachabilityVisitor & TypeLowerer (visitor.zena)"] Specializer["Specializer (specialization.zena)"] CHA["ClassHierarchyAnalysis (hierarchy.zena)"] Analysis -->|Delegates AST walks| Visitor Analysis -->|Triggers specialization| Specializer Analysis -->|Queries class hierarchies| CHA Specializer -->|Queries subclass implementations| CHA Visitor -->|Discovers types / registers methods| Specializer ``` ### 1. Central Coordinator: `ReachabilityAnalysis` (`analysis.zena`) - Main entry point that manages RTA traversal queues (`reachableQueue`, `checkableQueue`). - Configures and instantiates the helper subsystems in its constructor. - Coordinates the overall compilation passes: - Pre-registers declared types to handle circular definitions. - Walks traversed functions iteratively until no new reachable symbols/methods are found. - Performs structural linker steps like linking base class vtables and resolving property getters/setters. ### 2. AST Visitor & Type Lowerer: `ReachabilityVisitor` & `TypeLowerer` (`visitor.zena`) - **`ReachabilityVisitor`**: Traverses reached function and method bodies, discovering global dependencies, closures, and interface usage, and queues any newly referenced virtual members. - **`TypeLowerer`**: Resolves structural types (`RecordType`, `TupleType`, etc.), array classes, and class/interface types to concrete WebAssembly types. - **A reached body is walked one of two ways.** A body the checker recorded dependencies for gets `registerLiterals` and `registerInstantiations`, with the records standing in for the rest; any other body gets the full `discoverNodeTypes` walk. The records name symbols only: they hold no instantiations, string literals or interface members. So a new fact RTA collects from nodes has to be collected in both walks, as `noteInterfaceDispatch` is. - **Look a member access up by `accessKeyOf(model, expr)`** (`semantic-model.zena`). A member declared with a symbol is keyed by that symbol's identity (`:act_368`), which only the checker can resolve and which it records on the access node. A key built as `":" + property.name` matches only the symbols the compiler invokes itself (`:dispose`, `:iterator`), whose keys are fixed (`SymbolType.protocolKey`). ### 3. Monomorphizer: `Specializer` (`specialization.zena`) - Performs generic class and interface specialization. - Maintains lists of instantiated classes. When a generic class is instantiated, it generates specialized vtables, structs, and physical methods corresponding to that concrete type argument combination. - Instantiates specialized generic function signatures. ### 4. Class Hierarchy Analysis: `ClassHierarchyAnalysis` (`hierarchy.zena`) - Manages caches for subclass relationships (`isSubclassOf`). - Resolves dynamic overrides, locating the concrete `MethodDefinition`, `AccessorDeclaration`, or `FieldDefinition` that implements a virtual slot on a subclass. - Collects implementing interfaces transitively. ## An Erasure Is Not a Specialization A type parameter lowers to `anyref`, so `Store` named from inside generic code is discovered as `Store` — which `isConcrete` accepts, because anyref is a type (and a real one: `let x: anyref = "hi"`). It must not become a specialization. Every value the mention stands for is some real specialization, discovered on its own, while believing in the erasure makes it a fan-out target for every reached member of the generic class and, once instantiated, gives it a class vtable global whose slots force-reach an erased body of every method — none of which lower when the class uses `hash`/`eq`, which dispatch on their operand's type. The mentions that fabricate one are plumbing, not code that runs: `#linkSuperAndVT` naming a subclass template's supertype, and the walk of a generic class's own template naming its field types. `containsErasedType` (in `codegen-utils.zena`) is what asks whether a type IS an erasure — `ErasedType` in `types.zena` is a distinct codegen-internal type, so this is a fact about the type rather than a guess about which walk produced the mention. The erased class's struct is still registered, because erased signatures and fields refer to it. Nothing is emitted at an erasure, including the erasure of a generic FUNCTION. `fill(v)` named from inside `outer`'s body is not a call site, it is the template of one: every value it stands for belongs to some `fill` a real call site names. `noOpenTypeParameters` (`visitor.zena`) refuses to specialize on arguments that are still bare type parameters, so `fill_spec_erased` is never minted, and with it goes the only thing that ever ran `new Full` as `new Full`. `walkingTemplateOf` does not cover this and structurally cannot: it is `ClassType | null`, set only for a non-concrete class referrer, so it is always null while walking a generic top-level function. So `registerSpecializedClass` stops after the struct for an erasure — no vtable slots, no methods, no constructor — `#buildClassInterfaceVTables` skips it (an erasure passes `isConcrete` but has nothing to put in a trampoline slot), and a member referrer whose class is an erasure registers nothing. The struct itself is still registered, because erased signatures and fields name it. The two halves check each other. Mint an erased function specialization without the class half and lowering fails loudly — `constructor missing for Full_s867_erased @fill_spec_erased` — instead of emitting a dead body that happens not to be called. In the compiler's own module this removed 87 functions (15,155 → 15,068), every one of them unreferenced from any non-erased body. A trap when measuring this: `getTypeKeyForSpecialization` maps a bare `TypeParameterType` and an `ErasedType` to the SAME key, `"erased"`. So `fill_spec_erased` may have been minted with a raw `T` and never an `ErasedType` at all, and a `containsErasedType` probe will not see it. `Array` and `Array` are likewise one class, `Array_s777_erased` — which is why `containsErasedType` answers true for a bare type parameter too. ## A Specialization Is Keyed by Representation and Ownership `getTypeKeyForSpecialization` keys a type alias by its target and an enum by its backing type, except for the aliases that decide what a body may do with a value (`specializesApart`): `Borrow` and `Unmanaged` on a restricted type, which key apart from `Own` (that is, `R`), and `Scoped`, which keys apart from `T`. So `C>`, `C>` and `C>` are three specializations of `C` with one layout, and a body's `T` names its instantiation's own handle. See owner-futures.md §"Specialization". Three things have to agree for that to hold, and a new key or erasure has to keep them agreeing: - **The erasure of a type argument.** `eraseTypeParameters` erases a handle to its resource, which is right for a value's type and wrong for a type argument, since discovery registers specializations from erased types and lowering often looks them up unerased. Class, interface and mixin arguments go through `eraseTypeArgument` (`type-mapping.zena`), which keeps the aliases a key keeps, inside tuples, unions, records, arrays and function types too. So inside a specialization `Own` reads as a bare `R`, and `holdsOwner` (`types.zena`) counts a bare resource class as an owner. - **The discovery key.** `getTypeUniqueKey` dedupes discovered types. An alias instance's target is its declaration's `T`, the same for every handle, so it keys a kept-apart alias by its kind and what it wraps. - **The specialization key** above. An alias instance keeps its declaration's unsubstituted target, so "its target" means `instantiatedAliasTarget` (`codegen-utils.zena`): for `opaque type Own = T` and the other handles, the argument. Read as the bare target, every handle was the erasure of `T`, and a generic function called at one was minted as an erasure (#789). `isConcrete` and `containsErasedType` read it the same way. The hybrid mode planned in docs/design/generic-specialization-strategy.md, which shares one body across reference type arguments, keeps this axis: arguments share a body only within one ownership kind. ## A Synthesized Member Is Replayed by Name A member reached on a generic class is recorded against the generic and replayed for each specialization that arrives later (`recordReachedClassMember`, `noteSpecialization`), keyed by its AST node. A member the checker synthesized has no node: a case class's `==` and `hashCode`, and a release member (`:dispose` of a resource with only owner fields, `[release]` of a `scoped T` class). A reached release is recorded by class (`#reachedSyntheticReleases`) and `noteSpecialization` replays it before its duplicate check, since discovery can list a specialization that is only instantiated later. Read the synthesized flag off the declaration, `synthesizedRelease(ct)`, never off an instantiation: an instantiation copies `hasSyntheticRelease` when it is made, and one made before its class finished registering (`Some` while `zena:core` registers) holds a stale false. ## A Generic Method Exists Only Per Specialization A method's OWN type parameters are a separate axis from its class's. `registerGenericMethodUse` mints `map_spec_i32` per call site; the unspecialized registration — the body at the method's erasure — is not a function, so: - it gets no class-vtable slot (a slot is one `ref.func` of one signature, and a generic method has no single signature), and - the member referrer in `processQueues` does not reach it (`isGenericAtErasure`). Emitting it anyway put one dead body per specialization of the class in every module (80 `Array.map` in the compiler's own, referenced by nothing), and those bodies' `new Array` were the only thing that ever made an erasure look constructible — which is why the rule above can be flat. It is also what `zir unsupported: method not found` found where a specialization should have been. See §15 of `docs/design/binary-size.md`. Virtual calls follow the same per-specialization rule on both interfaces and classes: - **Interface receivers**: a generic method called through an interface-typed receiver records a `GenericInterfaceMethodDemand` (visitor → `demandGenericInterfaceMethod`), and each demand becomes one interface vtable slot named by the same `getSpecializedName` mangle. Slots are appended and per-class trampolines built inside the `#buildClassInterfaceVTables` fixpoint — a class can join a demand's interface in any round, so the fan-out to implementing classes happens at trampoline build, not at demand time. Trampolines adapt covariant class-typed results (pack through the pair vtable) and `this`-narrowed callback parameters (a synthesized closure forwarder). See `docs/design/generic-interface-dispatch.md`. - **Class receivers**: a non-static generic method called through a class-typed receiver records a `GenericClassMethodDemand` rooted at `getMemberRootClass(targetClass, methName)` (visitor → `demandGenericClassMethod`). `#syncGenericClassSlots` appends the specialized slot name to `classVtable` across the root class's hierarchy, specializes overrides (or registers a vtable slot stub when abstract) on subclasses, and re-orders laid-out `vtableStructType` fields root-first so `#fillReachedSlots` and `#pruneUndispatchedSlots` treat the specialized slot identically to a non-generic method slot. ## An Interface Slot Exists Only When Something Calls It An interface vtable struct starts empty. A member gets a slot when reachable code calls it through the interface, recorded by `demandInterfaceMember`, or through an interface it extends: an upcast (`repackInterface`) copies the target's slots out of the source's vtable by name, so `#interfaceLineage` makes a demand on an interface count for every interface below it. `#syncInterfaceSlots` appends the slots inside the class-interface vtable fixpoint, and pair vtables built earlier get trampolines for the new tail. Each slot is a trampoline per packed class, and each trampoline reaches a method, so a slot nothing dispatches through used to keep that method and whatever it constructed (#425). Trampolines are also the only thing that reaches an implementation through an interface: a class never packed as an interface cannot be dispatched to through it. So **a new interface dispatch in lowering needs a demand**, or it fails with `interface member not in vtable: `. Node-level dispatches go in `noteInterfaceDispatch` (visitor), which both body walks run — most bodies get `registerInstantiations` and the checker's dependency records, not `discoverNodeTypes`, and the records hold no interface members. Dispatches a construct implies without naming them (a generator's `next`, an async frame's `run`, `:toString` in a template) are demanded where that construct is registered. See §19 of `docs/design/binary-size.md`. A class-interface vtable exists only for a specialization something packs. `demandPackPair` marks the pair a pack site resolves to, `(Box, Shape)`, and the vtable phase builds `Box`'s vtable only if a pack of `Box` marks it too. A pair that still holds a type parameter or an erasure marks nothing: it comes from a walk of a generic body under its own parameters, and the walk under each substitution marks the real pair. Marking the generic pair instead built 3,749 vtables and 9,487 trampolines in the self-compile, of which 195 and 812 survived harvest (#815). ## A Class Nothing Reaches Specializes Nothing `#layoutClassStructs` lays out every declared class in every loaded module, emitted or not — the layout is what registers a class's members, and a class can pick up evidence after its turn. But laying one out walks its members' signatures, and a signature's mention of `Completer` is not a `new Completer()`. `layingOutUnemittedClass` is set for the classes with no emission evidence — the same question the type section is rooted from: instantiated, or named by reached code. Under it a mention still registers the specialization's struct, because fields and signatures name it, and stops there: `discoverType` neither instantiates it nor puts it on the generic's `specializedClassTypes` list. Being on that list is what makes a specialization travel. `instantiateClassType` instantiates every listed sibling, and `recordReachedClassMember` fans each newly reached member of the generic out over all of them — so one unreachable class's field type was enough to emit `Completer`, `Future` and `Box` whole at type arguments no reachable code names. To keep passing over a mention from losing a real specialization, the list is no longer built by discovery alone: `noteSpecialization` is also called from `instantiateClassType`, so a specialization rejoins the register at the `new` that makes it real. See §18 of `docs/design/binary-size.md`. ## Interface Type Tests Read Per-Class Tables `x is I`, `x as I` and `case I` mean "the class of `x` implements `I`", answered from a `TypeInfo` table hung off the class vtable rather than a `ref.test` of the interface's fat pointer struct, which only says how the value is held. The visitor records each site with its operand's static type (`noteTypeTestSites`), `#markTypeTestPairs` turns the sites into the `(class, interface)` pairs that can answer true once the instantiated classes are known (inside the late vtable fixpoint, since each pair needs its class-interface vtable), and `#layoutTypeTests`, after slot pruning, lays out `TypeInfo`, `VTableBase`, `Object` and `FatPtrBase` for exactly those classes and orders the globals so the initializers' `global.get`s point backwards. A program that tests no interface emits none of it. See `docs/design/interface-type-tests.md`. ## Code Generation Pipeline Integration The reachability pass is run in [module-generator.zena](../module-generator.zena): ```zena let pass = new ReachabilityAnalysis(this.program, wasm, this.target); pass.run(); ``` After `pass.run()`, the `WasmModule` contains exactly the functions, struct layouts, and vtable allocations that are actually reached during execution, drastically reducing the Wasm module size.