Compiler Changelog
A record of the compiler's internal quality-of-implementation work — LLVM passes, the memory-model chronology, in-place reuse, structured parallelism, resource safety, and codegen. None of it changes the language specification; it is the "what was done and why" history behind the behavior described in Compiler Architecture and the IR Reference.
Entries below describe the implementation at the time each item landed. In particular, the early arena-only, erased-drop, old closure-layout, and "no runtime RC" entries are historical and are superseded by RC Perceus migration below. Use the architecture and IR references for the current contract.
Contents
Completed work catalog
All original audit findings have been addressed. This table is the compact catalog, not a strict chronological narrative: related follow-up work is kept near the subsystem it refined. The RC Perceus migration deep dive preserves the longer sequence of decisions, measurements, and corrections where that context matters.
Ownership, placement, and async
| Area | What was done |
|---|---|
| Transparent aliases and zero-cost nominal types | Added parameterized type alias Name(a) = ... declarations with cycle-safe expansion and stable ASH039 diagnostics, plus nominal type Name(a) = Constructor(payload) declarations distinguished from ordinary ` |
| Explicit module interfaces | Added optional declarative export (...) interfaces for values, abstract types, selected/all constructors, and nested inline modules. Project stitching now validates duplicate/unknown entries and filters whole-module, alias, selector, qualified-constructor, and pattern access through one surface; LSP completion and definitions honor it. Compatibility export-all remains the default. Ashes.Collection.Map now hides its AVL representation/helpers and Ashes.Text.Regex hides its compiled-handle constructor and compiler-reserved PCRE2 primitives. |
| RC Perceus migration | Escaping ordinary graphs now use compiler-inferred ownership and runtime RC: per-function borrowed/consumed summaries, last-use/branch-entry RcDrop, late RcDup, layout-aware recursive drops, uniqueness specialization, and DropReuse/AllocReusing with a fresh-allocation null fallback. Complete-graph normalization prevents mixed-lifetime parents and children. Small cells use dense per-thread RC chunks plus constant-time exact-size free-list bins; large cells return directly to the OS. Compiler-proven scratch, task/capability state, mmap-backed views, parallel publication copies, and the persistent Map/HashMap to-space retain explicitly classified regions with multi-scale RSS gates. See the RC Perceus migration deep dive. |
| Canonical lowered-temp ownership facts | Replaced the parallel _runtimeManagedResultTemps set and IsRuntimeManagedResultTemp's linear emitted-instruction scan with one frame-local LoweredTempOwnershipFact table updated at emission time. Facts retain representation, owner/source temp, resolved type and outer layout, drop capability, borrow/transfer/production mode, source/function origin, location, and a stable transition reason. Borrow, RcDup, borrowed Bytes views, joins, calls, copy-out normalization, TCO installation, frame restoration, synthesized function frames, and deferred instruction rewrites now propagate or refine that record. Runtime-result instructions implement a shared registration contract, with reflection coverage that fails when a new producer omits it; DropReuse remains explicitly excluded because it produces a reuse token rather than an ordinary value. |
| Stable pattern-binding ownership identity | Pattern-derived TCO escape facts are keyed by each binder's exact Pattern.Var syntax-node identity before lowering and transported to its distinct local slot when the pattern is emitted. The late protective-dup fix-up consumes only slot identity. Lexical reference resolution across lets, recursive lets, lambdas, nested matches, and handler arms prevents same-named binders in sibling arms or nested scopes from inheriting one another's escape verdict. |
| Pattern-binding ownership shadow analysis | Generalized the function ownership summary with immutable per-binding facts for references extracted from TCO parameters. Each fact retains stable binder and root-parameter ordinals, parent-binding lineage, extraction depth and source location, and distinguishes structural or ordinary-call borrows, unchanged same-parameter transfer, embedding, independent escape, closure capture, and conservative unknowns. Pattern emission transports exact binder identity to the local slot; the late protective-dup fix-up retains the final placement outcome and a typed comparison against CollectEscapingDirectPatternBindings. The legacy result remains authoritative until the next cutover, so this observability addition does not change emitted ownership operations. Coverage includes helper-call borrows, constructor embedding, same-parameter forwarding, nested list/tuple/ADT chains, copy fields, closure capture, and same-named binders in disjoint arms. |
| Pattern-binding Perceus cutover | Replaced the legacy direct-pattern escape re-walk, pending nested-alias chain, and source-name-keyed TCO alias activation bookkeeping with the canonical PatternBindingOwnershipFact. Exact binder identity now joins directly to its emitted local slot; embedded and independently escaping references become ordinary lexical owners whose guarded RcDup and CFG-placed final RcDrop are promoted only when the root parameter resolves to runtime RC. Borrowed and copy-typed bindings remain erased. An unchanged same-parameter successor does not receive a lexical owner; its exact back edge retains one reference before releasing the old parameter graph. This removed roughly 700 lines of classifier and activation machinery. Focused ownership, lifetime-placement, arena, and native nested-pattern tests pass; fannkuch-redux retained correct N=8/N=9 output while peak RSS changed from the pre-cutover baseline's roughly 8/247 MB to roughly 16/107 MB on the validation host. |
| Canonical ordinary heap layout capability | Replaced the recursive layout questions duplicated across ADT copy-out, record and heterogeneous-ADT RC eligibility, tuple drops, and TCO list/ADT normalization with one cycle-guarded OrdinaryHeapLayoutCapability. The immutable result records structural copy kind and size, recursive drop support, constructor-specific child offsets and drop kinds, runtime outer-cell reuse support, and stable resource/borrowed-view, unsupported-child, unresolved-type, and unsupported-reuse rejections. Lowered-temp ownership facts snapshot the resolved capability, while tuple/ADT drop emission, TCO child copying, and runtime-reuse cleanup consume its child descriptors. Construction freshness, top-cell freshness, and TCO profitability remain separate caller policies. |
| Reportable ownership causes | Re-keyed conservative function escape state by exact lexical FuncKey and supplemented the positive ownership summary with immutable call-census, per-parameter move-safety, and result-reach outcomes. Stable flags distinguish escape and incomplete/ambiguous census, linearity and capture failures, transitive or unsafe seeds, global/unmodelled reach, internal sharing, and conservative unknowns without weakening fail-closed analysis; poisoned callees remain conservative while forwarding any known parameter aliases. Reuse entry-copy elision and runtime-managed call-result placement now retain evaluated and positive decision facts (including the concrete result-layout predicate) plus the outcome, establishing an inspectable boundary for the later --explain work without making semantics write report prose. |
| Reportable reuse-specialization decisions | Reuse specialization generation and IsFullyReusing reset-safety qualification now retain immutable ReuseDecision records with stable outcomes/reasons, the reuse-root parameter, generated/source function lineage, related recursive function, and source location. Reset-safety distinguishes concrete fresh-allocation, copy-out, raw-allocation, and escaping-closure blockers instead of collapsing every rejection into a transient boolean. The old GetOrCreateReuseSpecializationDebugDump environment-variable console output and /tmp IR dumps were removed; later --explain reuse formatting can consume the retained facts without reconstructing intent from instructions. |
| Reportable reuse entry decisions | Entry-copy decisions are now recorded at the final post-body decision point rather than inferred from the earlier ownership predicate. Direct and specialization paths distinguish retained copies, ownership-proven elision, and profitability omission when a direct reader produced no structural reuse; records retain source/generated function lineage, parameter and local-slot identity, location, and exact move-safety cause flags. Reuse-token production also records whether its source is statically unique or whether DropReuse.RuntimeManaged requires a runtime uniqueness check, together with source value, semantic IR temp, and pattern location. The structured candidate model separates parameters, values, and tokens for the later --explain reuse correlation path without changing emitted IR. |
| Reportable specialization rejection and constructor layouts | Registered, saturated reuse-specialization calls now retain concrete rejection facts without treating internal recursive self-calls as missed external opportunities. Records identify the caller, target function, candidate value or call-result source, local slot and call location, and distinguish missing uniqueness/freshness proofs, unavailable bindings, unsupported fresh-accumulator layouts, and result shapes that do not rebuild the accumulator. The central reuse-token matcher also retains every accepted and rejected constructor-layout comparison, including token source/temp, allocation site, target constructor, field counts, list-cell identity, runtime-management regimes, and the exact mismatch. These records mirror the existing routing and TryConsumeReuseToken predicates and do not change their outcomes. |
| Reportable reuse-token lifecycle and fallbacks | Every DropReuse production now retains its source value, token identity, layout, runtime-uniqueness regime, function lineage, and location. Each token receives one terminal disposition: consumed by a correlated AllocReusing, conditionally released when a runtime uniqueness check produced a live token, discarded when an arena token remains unused, or reclassified as discarded when direct-reader profitability removes tentative nullary reuse. Fresh arena, runtime-RC, and specialization to-space fallbacks are recorded separately from the runtime AllocReusing null-token fallback, with stable outcomes and reasons. Direct profitability finalization removes tentative dynamic fallback facts when it rewrites the allocation, so the immutable records describe final semantic lowering rather than an abandoned intermediate decision. Validation against the pre-change dddaff0 baseline produced byte-identical -O0/-O2 reuse fixtures and byte-identical challenge executables. Fannkuch-redux retained its N=8–11 reference outputs with flat 8.2 MB RSS; binary-trees N=21 used 196 MB; reverse-complement on the 1M FASTA input used 740 MB; and 1BRC at 10M/100M rows used 6.85/8.88 GB with unchanged output on the validation host. |
| Exact mutual-recursion result provenance | Replaced query-order recursion guarding with a whole-program SCC-aware monotone fixpoint over exact lexical FuncKey forwarding edges. Fresh-base mutual components now converge to the same RC-eligible result fact as equivalent acyclic forwarding, while pure forwarding cycles, parameter results, unresolved calls, and unmodelled terminals remain fail-closed. Saturated exact self-recursive arms stay neutral. Eligibility requires a reachable independently eligible result and every exact forward target to remain admitted. The stable one-hop ForwardsTo value is retained only for one exact immediate target; a component with several edges is never assigned an arbitrary representative. |
| TCO arena self-containment fact | Split two previously conflated successor-argument questions without changing lowering decisions. TcoParamStructuralFacts.ArenaSelfContainedListRebuild now records, across exact FuncKey self-calls, the bounded whole-list rebuild shape recognized by IsArenaSelfContainedListRebuildExpr; ExpressionFreshness remains the stricter reference-alias fact. A helper result may therefore be arena-self-contained while retaining an input tail, whereas direct head :: oldAccumulator construction remains rejected. Shadow comparison uses the new fact for the old fresh-list classifier instead of misreporting these helper calls as freshness disagreements. The concrete GetTcoCopyOutKind/TcoBackEdge* reset decision remains a downstream, resolved-layout classifier. |
| Canonical TCO loop-invariant facts | Cut TcoParamOwnership.LoopInvariant over from its dedicated AST re-walk to FunctionOwnershipSummary.TcoParamFacts.UnchangedPassthrough. Structural facts are now positional: parameter ordinals keep duplicate curried names distinct in the immutable summary while source names remain diagnostic metadata. The self-call walk threads lexical parameter bindings through let and pattern scopes, and the live back edge confirms a pass-through variable resolves to the expected local slot. Because the innermost lowering scope exposes only the last same-named curried slot, migrated positive facts fail closed for duplicated names instead of joining ambiguously. The superseded CollectLoopInvariantParams derivation was removed. |
| Canonical TCO growing-cons facts | Cut TcoParamOwnership.AffineConsList over from its name-keyed AST re-walk to positional TcoParamFacts.GrownCons. Classifier-A eligibility and resolved back-edge promotion now consume the same binding-aware summary, while per-edge cons-tail recognition and runtime-RC tail transfer resolve the expected local slot. The reset path also resolves single-cell tail and predecessor-alias checks by slot rather than source spelling. Live TCO call recognition resolves the curried self-reference to its generated root label (or the transported self slot in synthesized coroutine loops), preventing a same-named local function from becoming a back edge and inheriting the outer loop's ownership facts. Let/pattern shadows remain conservative, duplicate names fail closed at the live slot join, and the superseded CollectAffineConsListParams derivation was removed. |
| Canonical TCO consumed-tail facts | Cut TcoParamOwnership.ConsumedListTail over from its name-keyed AST re-walk to positional TcoParamFacts.ConsumedTail. Exact self-call identity, parameter/tail ordinals, and lexical let/pattern scopes now determine the whole-loop ownership fact consumed by RC eligibility, promotion, reset, normalization, and cleanup. A same-named immutable rebinding of the exact recursive function participates in the all-edge shape join, while same-named aliases of other functions and differently named aliases remain ordinary calls. Duplicate parameter names fail closed at the live slot join. The orthogonal inspect-only BorrowableConsumedList refinement remains structural, but its candidate/result transport and resolved promotion join are ordinal-keyed; its tail-transfer exception now uses the same exact lexical function identity and checks match guards for escapes. The superseded CollectConsumedListTailParams derivation and the live name-to-first-ordinal lookup were removed. |
| Canonical TCO borrow-inspection use mode | Moved the consumed-list inspect-only refinement into FunctionOwnershipSummary.TcoParamFacts as TcoParamUseMode.BorrowInspectOnly, separate from the ConsumedTail successor shape. The analysis now carries head/tail ownership through a lexical environment that replaces same-named let and pattern bindings, retains exact FuncKey self-call identity, and treats guards as executable uses. Lowering consumes the fact by parameter ordinal before applying the all-inline-copy record-layout gate. The source-name-taint CollectBorrowableConsumedListParams walk and its private transport field were removed. |
| Canonical affine string reuse facts | Moved affine self-append legality into positional FunctionOwnershipSummary.TcoParamFacts as TcoParamReuseAffinity.SelfAppendOnly, separate from successor shape and borrow mode. The ownership walk now identifies exact lexical self-calls, tracks parameter bindings through let and pattern scopes, permits unrestricted exit-path uses, and rejects any other continuing-path reference. Lowering transports the fact by ordinal and keys reservation locals by the distinct parameter slot, so duplicate source names cannot share an affinity verdict or reservation pair. The source-name-keyed CollectAffineAccumulators walk was removed; resolved string lowering still combines the fact with the loop watermark before emitting ConcatStrTip. |
| Canonical TCO fresh-list rebuild facts | Cut TcoParamOwnership.FreshRebuiltList over from its name-keyed AST re-walk to positional TcoParamFacts.ArenaSelfContainedListRebuild. The whole-loop fact joins every exact self-call argument independently of reference freshness, so a helper result can remain Shape = Mixed while still licensing a bounded whole-list copy-out; a grown cons or any mixed non-rebuild edge rejects the fact. Same-named non-self calls cannot disqualify or inherit the exact recursive fact, and duplicate parameter names remain distinct in the summary but fail closed at the lowering slot join. The superseded CollectFreshRebuiltListParams derivation was removed. The per-edge IsArenaSelfContainedListRebuildExpr-equivalent reset predicate remains because concrete reset/normalization legality still depends on the actual edge and resolved representation. |
| Canonical TCO fresh-closure rebuild facts | Completed the five-category classifier-A cutover by sourcing closure rebuilds from positional TcoParamFacts.FreshClosureRebuild. This fact is intentionally independent of Shape: a freshly allocated lambda may capture an input and remain Shape = Mixed, while every exact self-call edge can still be proven to construct a closure. Runtime promotion additionally requires the resolved parameter type to be TFun; each concrete edge retains its closure-producer and capture-safety checks, so arena-backed captures are never reclassified. Same-named non-self calls cannot disqualify the exact recursive fact, duplicate parameter names fail closed at the live slot join, and late-resolved closure promotion remained disabled until the subsequent active-slot/prologue cutover. The superseded CollectFreshClosureParams, its shared name-only collector, and the completed TCO structural shadow comparator were removed. |
| Positional TCO parameter slots | Replaced the final source-name joins between positional TcoParamFacts and TCO lowering state. Lambda labels and parameter types are recorded by curried ordinal; every ordinal gets a distinct back-edge slot, while only the last lexically visible occurrence of a duplicated name joins the real local binding. Shadowed occurrences keep non-participating slots so their facts cannot alias or normalize the visible same-named value. Deferred runtime-argument ownership flags now retain the resolved local slot instead of re-running ParamNames.IndexOf, and all five structural classifier-A facts previously disabled for duplicate names now drive the correct visible slot. |
| Explicit TCO placement decisions | Split immutable positional TcoParamStaticFacts from representation orchestration. One evaluator now produces TcoParamPlacementDecision values at provisional loop entry, resolved back edges, and post-body type refresh, retaining stable eligibility/restriction reasons, resolved layout, dynamic-boundary input, frame-profitability blocker, transition, and first-promotion stage. The former scope-typed and resolved-edge frame-veto copies now share normalized inputs, and the concrete back-edge reset classifier consumes the placement decision while preserving its per-edge layout and producer checks. Weaker later type evidence cannot replace an already accepted concrete runtime type. Immutable per-function traces retain current and superseded decisions for the planned compiler-report handoff without changing code generation. |
| Scoped capability-handler ownership | Replaced the whole-program _programHasDynamicCapabilityDispatch ownership gate with an identity-correct per-function “may execute under a live handler post” effect. Functions that install handlers seed the effect; the existing exact call census propagates it to known callees, and an affected unresolved higher-order call conservatively includes escaped function values. Entry and generated functions receive the same explicit placement context, while BeginLivePostsGuard/LivePostsIndex remain at the concrete pending-post boundary. The immutable FunctionOwnershipSummary retains the effect for later reporting. A handler no longer forces unrelated functions onto arena placement, while direct helpers, post-resume TCO calls, and possible higher-order targets remain guarded. The call census now visits perform and handler bodies/arms, including pattern shadowing, closing the analysis gap exposed by this cutover. |
| Empty-list-tolerant reference counting | The empty list is the null pointer and carries no reference-count header, so a runtime-managed RcDup/RcDrop on a possibly-empty list read memory 16 bytes below address zero. Three separate mechanisms guarded parts of this in emitted IR — an inline null check around the TCO back-edge retain, another around the pattern-binding owner duplicate, and none at all around the aggregate-embedding duplicate or the owner's final drop, which is where a list-typed pattern binding crashed. All three are replaced by one MayBeEmpty fact on RcDup/RcDrop, computed from the resolved type where a marker is promoted to runtime RC and consumed by codegen. The duplicate stays identity-preserving, so an empty value is its own result and needs no merge. This removes five instructions and a basic-block boundary per guarded site. |
| Qualified references in re-lowered bodies | An inlined helper body or a reuse specialization re-lowers an expression outside the declaration scope it was written in, where a stitched module binding is no longer on the scope chain; a module-qualified reference then reported the module as unknown. Qualified resolution now falls back to the same lowered top-level function reference an unqualified backward reference already used there. A top-level value has no such by-label form, so inlining additionally requires every top-level binding the candidate body reads to be resolvable at the site and otherwise leaves the call to the ordinary call path. This restores reuse specialization for stitched standard-library modules, which a narrower registration condition had disabled, and with it the persistent-map to-space reuse the plateau gate asserts. |
| Callee representation at an ownership-transferring call | A caller may take ownership of a known function's result only when the callee's compiled body really produced a reference-counted value. FunctionResultProvenance is an AST-level fact computed before lowering, so it reports an RC-eligible result for a function whose body compiled to a region value under its own placement context. While ordinary RC placement was gated on a whole-program async flag the two could not disagree; scoping that gate to coroutine reachability let them, and an async block completing without suspending — lowered inline, outside the coroutine-body context — then skipped the copy-out at a call boundary. The result pointed into a region that ReclaimArenaChunks had already reclaimed, and its owner released it as a counted value, writing a free-list link sixteen bytes below a region string and overwriting the neighbouring string's length word: "A" + build(7) + "!" returned A7abcdefg! instead of A7abcdefgh!. The transfer now additionally requires the callee's recorded compiled representation, consulted only when the program uses async so that programs without it keep byte-identical output. All thirteen challenge executables are byte-identical across the fix. |
| Ordinary placement inside coroutine bodies | Lifted all eight in-coroutine ownership gates, so a value inside a coroutine uses whichever representation its own placement chose. What made that safe is normalizing the coroutine's result in one place: the value leaving through the task's result slot is copied back to the region where the body's value becomes that result, because it crosses a boundary with no owner on the other side. Gating the producers instead cannot converge — closing them one at a time found four separate sites that decide the representation of a value on its way out, and any producer can be the one whose value reaches the boundary. A value dead before the suspend now gets ordinary placement and an ordinary drop; one live across it is saved by the frame with the descriptor and dropper the task-frame work added. Seven of the thirty-two coroutines in the test corpus now carry reference-counted operations, against none before. Every measured leak shape is flat at 2 000 and 100 000 iterations, nine async fixtures are clean under Memcheck, twelve of thirteen challenge executables are byte-identical, and http_echo serves 3000/3000 with an unchanged peak resident set. |
| Coroutine-body values stay off the stack | A closure or ADT used only as a direct callee or scrutinee was stack-allocated even inside a coroutine body, whose frame does not survive its own suspension: the coroutine returns to the scheduler and is re-entered later on a fresh frame, so a use after an await read storage the scheduler had already unwound. It surfaced as heap exhaustion on the TestRunner's lowered pipeline and as a segfault on the optimized one, and reproduced before the task-frame work. Both now stay region-backed inside a coroutine. |
| Non-suspending async bodies lower as coroutine bodies | An async block whose body contains no await compiles to an eagerly completed task, and its body was lowered as ordinary code rather than as a coroutine body. A call inside it therefore took the runtime-RC result path and produced a counted allocation per task, which the enclosing region reset could not reclaim and no owner released: a workload creating one such task per iteration grew from 256 KB to 6144 KB across 2 000 to 100 000 iterations. The suspending form has always lowered its body region-backed; the two now agree, and the flag's control-flow meaning is unreachable in this branch because it is selected by the body containing no await. All thirteen challenge executables are byte-identical. Linux_backend_llvm_async_coroutine_value_memory_should_plateau gained the shape, and fails by 1280 KB without the change. A body that binds the value with a let before returning it still leaks and is recorded as remaining work. |
| Async coroutine memory gate | Added Linux_backend_llvm_async_coroutine_value_memory_should_plateau, covering a coroutine whose result is a freshly built string and one whose captured string the task frame owns. Neither shape had a growth gate: the async fixtures preserve copy scalars across awaits, so an unreleased heap value still produces the right answer. The gate measures peak resident set through /usr/bin/time rather than the shared Python wrapper, whose subprocess.run forks before exec so the child's ru_maxrss inherits the interpreter image and floors the measurement around 13.5 MB — too coarse to resolve a leak of roughly a megabyte across 50 000 iterations. It also optimizes the IR first, so the measurement describes what CompileToImage hands to the backend. It fails deterministically when in-coroutine reference counting is enabled without a task-result ownership contract, and passes with the current gate in place. |
| Task-frame ownership and teardown | Gave the coroutine task frame an explicit ownership description and a teardown path. StateMachineTransform publishes where it saves each temp and local; lowering turns those offsets and the capture words into CoroutineFrameSlot descriptors recording owner, type-directed release, empty-list tolerance and a stable reason, retained as CoroutineRepresentationRecord values for the later report. A frame that owns references gets a generated dropper that releases each owned word and clears it, so scheduler completion, ashes_cancel_task (covering race losers and recursive cancellation of an awaited child) and spawned-task reaping may each reach it without double-releasing; resource cleanup keeps its own path. Ownership moves rather than being shared: task creation clears the live-variable region so a word the coroutine never reached reads as absent, a suspend hands its saved values to the frame, the matching resume clears each word as it restores it, and completion clears the word holding the result it transfers. Every task creator now zeroes the new FrameDropper header word — a leaf or composite task allocates only the header and would otherwise carry region memory into an indirect call. |
| Coroutine-scoped async ownership | Replaced the whole-program "this program uses async" gate on ordinary RC placement with a per-function "may execute inside a coroutine" effect computed beside the handler-post effect: an async body seeds the functions written inside it and the functions it references, the existing call census propagates, and an unresolvable call inside such a body conservatively includes every escaped function. Creating one task no longer forces unrelated functions onto region placement, and a value such a function owns and captures becomes a frame-owned reference the dropper releases — the first coroutine values to use runtime reference counting. _inCoroutineBody still gates the coroutine body itself, and _usesAsync keeps its control-flow purpose of choosing between AwaitTask and RunTask. Two arena-classification tests reached the region path through an unrelated async(1), which is exactly the coupling this removes; they now route the value through the async body. Challenge output, wall time and peak RSS are unchanged, and a 10x growing async workload holds a flat 256 KB resident set. |
| Coroutine lifetime placement before the split | Moved ordinary-value lifetime placement for coroutines ahead of StateMachineTransform.Transform, onto the linear body whose AwaitTask is still an ordinary control-flow edge. Placement previously ran program-wide over the state-dispatch form, where a suspend returns to the scheduler and its resume state is entered by a later invocation rather than a CFG successor, so an owner's region was reconstructed from dispatch chains and resume prologues; a looping coroutine received three drops for one owner where one exit-edge drop is correct. IrFunction.LifetimesPlaced records the completed placement and the program-wide pass skips those functions instead of placing them twice. Live-across-await owners are saved and restored by the existing transform because a placed drop counts as a use of its owner. Erased arena markers keep the emitted behaviour of async programs unchanged today; the correct regions are the prerequisite for narrowing async allocation. Non-async programs, including every non-server challenge, compiled byte-identically at -O0 and -O2, and the TCP and HTTP echo servers retained their throughput and peak resident set. |
| Late-resolved TCO closures | Enabled fresh-closure placement at post-body type refresh. An unannotated closure accumulator first proven as TFun after body inference now receives an active local, with its inactive initialization retroactively spliced into the one-time TCO entry prologue. Exit and deferred back-edge consumers read the explicit placement state and treat an absent active local conservatively instead of indexing a missing dictionary entry. Concrete back edges still require a licensed runtime-RC closure producer and capture graph, so the new path changes placement timing without weakening closure-transfer safety. |
Core compiler and runtime
| Area | What was done |
|---|---|
| LLVM passes | LLVM 22 standard New Pass Manager pipelines (default<O1>, default<O2>, default<O3>) at O1–O3; O0 runs no module passes. The former targeted pipeline was retired after the alleged simplifycfg/vectorization inline-assembly failure could not be reproduced and the implicit TLS reads/thread-pointer writes were given complete memory-clobber semantics. PLT32 + PE relocation support. Freestanding builtins (memcpy, memset, strlen, memcmp, bcmp) emitted per module. |
| Memory allocator | OS-backed mmap/VirtualAlloc chunks (4 MB each, on demand; a single allocation larger than one chunk grows a variable-sized chunk to fit). Bounds checking with clean error. |
| Arena deallocation | Phase 1: scope watermarks for copy-type results. Phase 2a: TCO per-iteration reset for copy-type args. Phase 2b: copy-out (CopyOutArena IR instruction) for TStr scope results. Phase 2c: TCO copy-out for TStr and TList(copy-type) args. Phase 2d: abandoned OS chunk reclamation via ReclaimArenaChunks (split from RestoreArenaState to prevent use-after-free — restore resets pointers, reclaim frees chunks after copy-out completes). Phase 3: per-function-call watermarks. Phase 4: extended copy-out — CopyOutList (deep cons-chain copy for TList with copy-type element), CopyOutClosure (closure struct + env copy; 24-byte closure layout {code, env, env_size}), ADT with copy-type fields. Phase 5: extended TCO copy-out — CopyOutTcoListCell for TList(TStr) and TList(TList(copy-type)) args (single-cell + head copy), closure and ADT args via CopyOutClosure/CopyOutArena. |
| Extended TCO copy-out | Replaced CanCopyOutTcoArg with GetTcoCopyOutKind in Lowering.cs. Added CopyOutTcoListCell IR instruction for single-cell + head copy-out, and ListHeadCopyKind enum (Inline, String, InnerList). TList(TStr) via CopyOutTcoListCell(String), TList(TList(copy-type)) via CopyOutTcoListCell(InnerList), closures via CopyOutClosure, ADTs via CopyOutArena(staticSizeBytes). |
| Linkage-aware Byte.indexOf | Ashes.Byte.indexOf no longer unconditionally imports libc memchr on Linux (which made every scan-using image dynamically linked). Images that already carry the glibc-linked TLS runtime keep glibc's SIMD memchr (marker global __ashes_glibc_runtime); all other images use a freestanding per-module SWAR word scan (__ashes_memchr_swar, Hacker's-Delight zero-byte mask, absolute-address alignment so unaligned Byte views are safe) and stay fully static. |
| String operations | EmitCopyBytes → LLVMBuildMemCpy. Comparison → memcmp/bcmp. Literals → .rodata global constants (no heap alloc). |
| Pattern matching | Tag/zero/non-zero checks → single CmpIntEq/CmpIntNe + one conditional jump. |
| Function attributes | nounwind on all functions. willreturn, noalias, nonnull, readonly, memory(read) on builtins. |
| CPU targeting | --target-cpu CLI flag; native auto-detects via LLVMGetHostCPUName/LLVMGetHostCPUFeatures only when host and target architectures match. Cross-compilation accepts explicit target CPUs or the generic default and rejects native. |
| IR optimizer | Constant folding (with cross-label propagation), identity/strength reduction, unreachable code elimination, dead code elimination. |
| Compile-time evaluation | IrCompileTimeEval runs first in IrOptimizer.Optimize — best-effort partial evaluation that removes work LLVM cannot (it never folds a recursive function to a constant). A straight-line caller scan finds a CallClosure/CallKnown whose closure and argument are compile-time constants and whose callee is pure-and-modeled, runs a small concrete IR interpreter, and replaces the call with a LoadConst*; the existing DCE + arena-bracket passes then delete the now-dead closure/argument construction. Evaluability is a whole-program least fixpoint (ComputeEvaluableFunctions, same shape as ComputeNonAllocatingFunctions): a function is evaluable iff every reachable instruction is modeled and side-effect-free (no IO / FFI / capability-handler / async / resource / transcendental / big-int / bytes / raw-memory op) and every function it references by label is evaluable; CallClosure targets are checked dynamically at eval time. Because the interpreter executes the real modeled instruction semantics, a completed evaluation yields exactly the runtime value; any unmodeled/impure instruction, budget overrun, or non-scalar result bails and keeps the original runtime code — best-effort, never an error, no new syntax, no spec change. Memoization on (label, env, arg) makes pure recursion cheap (fib(40) is ~41 evaluations, not 331M). Step (50M) and depth (20k) budgets bound compiler work; the interpreter runs on a 512 MB-stack thread so the depth cap turns runaway recursion into a clean bail rather than an uncatchable StackOverflowException that would abort the compiler (found via a 2M-deep linear recursion core-dumping the compiler). Scope: scalar results (Int/Bool/Float) and closures without a captured environment; string/aggregate result embedding is outside this pass's current scope. Toggles: ASHES_NO_COMPILE_TIME_EVAL disables the pass, ASHES_EXPLAIN_COMPILE_TIME traces each decision. Measured: fib(40) ~268 ms of runtime work → a printed constant (~60 µs, and constant regardless of N); fib(35) 24.3 ms → 56 µs; typical intrinsic/IO-bound programs unchanged (identical output and binary); compile time unchanged within noise. The e2e TestRunner now uses the optimized semantic pipeline by default, and full CI uses --pipeline both to verify this pass alongside raw lowered IR; -O0 through -O3 select LLVM optimization independently. The IrOptimizerTests Compile_time_eval_* cases also call IrOptimizer.Optimize directly to verify folding fires; correctness across real programs is verified by a -O2-vs--O0 differential and on linux-x64, linux-arm64 (qemu), win-x64 (Wine). Regressions: tests/compile_time_eval_recursive.ash, tests/compile_time_eval_factorial.ash. |
| Borrow elision | ElideBorrowsForConstants in IrOptimizer.cs. Temp aliasing infrastructure: use-def chain tracking per temp (copy-type producers via LoadConst* scan, per-temp use count via CollectUsedTemps). Copy-type elision: Borrow instructions whose source is produced by LoadConstInt/LoadConstFloat/LoadConstBool are removed; all uses of the borrow target remapped to the original source temp. Single-use elision: non-copy Borrow instructions whose target is used exactly once are also elided. Transitive chain resolution via ResolveTemp. RemapSourceTemps helper rewrites all source-temp references in any IrInst variant using with record syntax. |
| Drop elision | ElideRedundantDrops in IrOptimizer.cs (Pass 4). Removes non-resource-type Drop instructions (String, List, Tuple, Function, non-resource ADTs) — these are no-ops in codegen since arena deallocation handles bulk memory reclamation. Resource-type drops (Socket) are always preserved for platform-specific cleanup. Also removes the associated LoadLocal when its target temp is only used by the elided Drop, and StoreLocal instructions to slots with no remaining LoadLocal references — cascading dead code cleanup in a single pass. Uses BuiltinRegistry.IsResourceTypeName to distinguish resource types. |
| TCO | IR-level tail recursion → loop. LLVMSetTailCall on tail-position calls. |
| Escape analysis | Conservative stack allocation for proven non-escaping values. Added AllocStack, AllocAdtStack, and MakeClosureStack IR instructions plus LLVM alloca codegen. Closures are stack-allocated when used only as direct callees within scope (including captured-env closures), and ADTs are stack-allocated for immediate single-arm constructor destructuring (`match Box(42) with |
| Debug info | DW_TAG_auto_variable for locals, DW_TAG_formal_parameter for lambda args. Custom DWARF language code 0x8001. isOptimized wired to -O level. |
| Decision-tree matching | Matches over >4 single-ADT constructor arms (distinct tags, trivial sub-patterns, no guards) lower to one SwitchTag IR instruction → LLVM switch. O(n) tag-comparison chain → O(log n) (or O(1) where LLVM picks a jump table). |
| Jump-table linking | The image linkers apply switch jump-table relocations (R_X86_64_64 in .rela.rodata, IMAGE_REL_AMD64_ADDR64 in .rdata, defensive R_AARCH64_ABS64), so LLVM's O(1) table dispatch links and runs correctly; the no-jump-tables attribute was removed. |
| String-literal interning | Identical string-literal .rodata globals are content-addressed and emitted once per module (LlvmTargetContext.GetOrAddStringLiteralGlobal), shared across all functions and internal call sites. Compile-time, bounded, leak-free. |
| Mutual-recursion TCO | Eligible let recursive … and … groups (same arity, identical parameter types, a cross-member tail call) are merged into one self-recursive dispatch function with thin per-member wrappers, so the existing single-function TCO turns mutual recursion into a loop. Ineligible groups keep the closure path. Design constraint: members can legally have different parameter types (ping: Int → Str tail-calls pong: Str → Str), which a single shared typed parameter list cannot merge without unifying incompatible types; hence the same-arity + identical-parameter-types gate (verified against each member's inferred type). Heterogeneous-parameter generalization would need distinct per-member slots (an IR-level slot-union loop) or opaque-coercion dispatch. |
| In-place reuse (Perceus-style) | Immutable recursive-ADT accumulators are rebuilt in place instead of reallocated: a one-time defensive deep copy at loop entry makes the accumulator uniquely owned, then matched-and-rebuilt-with-the-same-constructor cells are overwritten (AllocReusing). Covers direct accumulators, helper-rebuild inlining, recursive-function specialization, the full Ashes.Map.set shape (multi-param / nested-recursive-returning / helper-rebuilding / intermediate-value linearity), recursive scalar-list rewriters (untagged cons-cell reuse), and an immediate rewriter over a fresh call-produced list of single-constructor records. The latter overwrites the fresh spine and record heads inside their shared arena call window. At a TCO RC boundary, a same-length fresh list of copy-only records may also reuse the preceding runtime-owned graph: the compiler first checks the complete old spine and every record head for uniqueness, then overwrites fields while preserving RC headers; a mismatch, shared node, or pointer field keeps the normalize-and-drop fallback. Fresh heap leaf fields (Str/Bytes/tuple keys & values) are materialized into a persistent to-space/blob on insert and overwritten in place on update; a genuinely-new insert node also lands in to-space. Pure readers (result type ≠ the accumulator, e.g. Map.get : … → Maybe) are kept off the reuse path so their result cell isn't stranded in the never-reset to-space. A conservative IsFullyReusing gate + AccumulatorIsFullyPersistent guard the per-iteration arena reset (extended to admit reset-safe accumulators + scalar resource-handle args). Result: string/int/tuple-valued Map.set folds and scalar-list rewrite loops are constant-memory. The nested-re-entry leak is addressed by the move/linearity reuse-copy elision entry below. |
Measured optimization and correctness audit
These entries retain their original CO-* identifiers where the audit assigned one.
| Area | What was done |
|---|---|
| Move/linearity reuse-copy elision | The reuse entry deep-copy (the specialization f$reuse path and the direct-reuse prologue) is elided when a whole-program move analysis (Lowering.MoveAnalysis.cs) proves the accumulator is uniquely owned at every external call site; the copy stays on any uncertainty, so it can only leak, never corrupt. An accumulator argument is a move when it is a sole-nullary seed, a fully-fresh construction, a move-linear reference to a move-safe accumulator parameter, a let-bound fresh value proven dead-after-use, or a registered-function call admitted by the result-reachability (may-alias) summary. That summary (ComputeResultReach, a monotone least fixpoint) records, per function, which of its own parameters the result may alias (per-parameter multiplicity capped at 2 — internal sharing poisons via hierarchical path tokens + per-binding identity tokens) plus a poison flag; f(args) is a move iff not poisoned and every reached parameter's argument is itself a move (IsResultAliasMove). Covers result-fresh builders (reach {}, incl. recursive let recursive build), wrap-style result-alias builders (reach {x}), higher-order / closure-produced seeds (capture-aware over-application reach), and Ashes.Map.set-shape reuse-rewriting results (nested-recursive-return registration; reach {map,key,value}). Remaining conservative (the correct boundary short of full ownership): a result the summary poisons — reaches a global or an unmodeled shape. Measured: nested Map.set re-entry O(batches×size)→constant; a recursive-builder-seeded fold 504 MB→4.7 MB; a Map.set-result-seeded fold ≈2× (200k-key). |
| Deterministic resource safety | File/socket/process handles are closed deterministically without GC/RC (Ground Rule 6), via an affine ownership model: recursive Drop for resource-bearing aggregates (Result(_,FileHandle), Some(Socket), tuple/list of resources), move-on-destructure and move-on-construction (no double-close), resource drops at the TCO back-edge (fixes the loop-over-files fd leak), termination and reaping of live Process values on drop, and deterministic close of resources captured by an escaping closure (a dropper at closure+24 invoked when the closure is dropped). All runtime gaps closed & verified (fd-bounded under ulimit -n 64). |
| Use-after-close for match-arm-bound resources | The static use-after-close check (ASH006) already tracks resources whether bound by let or by a match arm, but the FileHandle read intrinsics (Ashes.File.readChunk, Ashes.File.readLine) never consulted it, so a handle destructured from Ok(fh) and read after an explicit Ashes.File.close compiled silently (it stayed runtime-safe — the read after close returns an Error). Wired CheckUseAfterDrop into both file-read intrinsics, so a read after close on a match-arm-bound (or let-bound) FileHandle is now flagged at compile time, matching the existing socket/process behaviour. |
| Parallel tunables | The two hard-coded parallelism knobs are now configurable, defaults unchanged. Per-worker stack size: the --parallel-stack-size <size> CLI flag (byte count or K/M/G suffix), threaded BackendCompileOptions.ParallelWorkerStackBytes → LlvmTargetContext → codegen; unset = 1 MiB on linux (mmap) and the OS default on win-x64 (CreateThread). Grain size for map/reduce: exposed as an explicit library parameter — Ashes.Parallel.mapGrained(grain) / reduceGrained(grain), with map/reduce = grain 1 (the original split-to-singleton behavior). |
Structured parallelism (Ashes.Parallel.both) | Genuinely parallel fork/join of two pure thunks on all three targets, deterministic (result identical to sequential) and memory-bounded, via per-thread bump arenas + worker threads + deep-copy-on-join. Per-thread arena mechanism: linux-x64 a GS-segment TCB (arch_prctl); win-x64 the TEB ArbitraryUserPointer (gs:0x28); linux-arm64 real ELF TLS (thread_local arena cursors, TPIDR_EL0, PT_TLS + R_AARCH64_TLSLE relocs resolved in the in-house linker; the entry prologue sets TPIDR_EL0 only when a loader has not — see the arm64 networking + parallelism coexistence entry below). Threads: clone/futex (linux) / CreateThread/WaitForSingleObject (win); a lock xadd/ldxr-stxr worker counter caps concurrency and over-budget forks run inline. both forks only at a concrete result type (deep-copy-on-join needs it); abstract results run sequential. Worker-stack lifetime on linux is tied to true thread exit via CLONE_CHILD_CLEARTID: the kernel zeroes a ctid word and futex-wakes it only after the worker has fully left its stack, and the parent waits on that (non-private FUTEX_WAIT) before reclaiming the stack/TCB/arena — distinct from the result-ready word, so the join still consumes the result immediately. (win-x64 already gates reclamation on WaitForSingleObject, which waits for full exit.) |
| arm64 networking + parallelism coexistence | The arm64 per-thread arena is real ELF TLS (PT_TLS + local-exec cursors) and is now enabled for every arm64 image, including dynamically linked (networking / external) ones — so both can hand a worker its own arena even in a program that also dlopens rustls. The apparent conflict was never in the TLS layout: a dynamically linked image's local-exec PT_TLS is reserved by the loader in the static-TLS block (at the same TPREL the in-house linker bakes in), independently of the DTV that backs the dlopen'd module's dynamic TLS. The only real hazard was the old entry prologue unconditionally msr-ing TPIDR_EL0 to a private BSS block, which on a dynamic image clobbered the loader's thread pointer (breaking rustls/libc TLS). Fix: the prologue now reads TPIDR_EL0 and self-initialises it only when zero (an unloaded static image); a dynamic image keeps the loader's pointer and resolves its arena cursors through the loader-reserved local-exec slot. Verified under qemu-aarch64-static -L <sysroot>: networking-only (HTTPS loopback, external) still runs; a program linking rustls and using both runs correctly and memory-bounded (PT_TLS + dlopen'd rustls both present); parallelism forks genuinely (clone/futex observed via qemu -strace) in dynamically linked images. Caveat (separate, pre-existing, target-independent): a both does not temporally overlap an in-flight async I/O — the async runtime is synchronous/blocking, so a fork runs before or after a live TLS session, never concurrently with one. (The earlier wording here — that both "runs inline" in an async program — was a misdiagnosis: a concrete-result both forks normally regardless of async usage; see the cooperative async runtime entry below for the detailed analysis.) That temporal coupling is orthogonal to the arm64 TLS/arena coexistence solved here. |
| win-x64 parallelism + networking coexistence | The win-x64 per-thread arena is the TEB ArbitraryUserPointer scratch slot (gs:0x28), not PE thread-local storage, so — unlike arm64's real-ELF-PT_TLS arena — it does not collide with rustls's Windows TLS: Rust's std TLS goes through the standard PE .tls / TlsAlloc path (the TEB ThreadLocalStoragePointer), which never touches ArbitraryUserPointer. Consequently win-x64 keeps both genuinely forking in networking programs (the fork runtime is emitted unconditionally, with no networking gate). Empirically verified under Wine: a program that runs heavy both fork/join both before and after a full rustls loopback TLS handshake produces correct results on both sides with no crash/corruption (tests/parallel_tls_coexist.ash); the fork is genuine (~2.4× wall-clock speedup, two independent CPU-bound thunks: sequential ≈ 860 ms vs parallel ≈ 355 ms) and memory-bounded (peak RSS flat at ~27 MB across 300 → 30 000 outer iterations — ~2 M forks — on par with the linux-x64 baseline). No arm64-TLS-style conflict exists on win-x64. |
Data-parallel map/reduce | Ashes.Parallel.map/reduce (and the grain-parameterized mapGrained/reduceGrained) are now genuinely data-parallel via call-site monomorphization: above the grain threshold their bodies split the list in half and evaluate the two halves through both, and a saturated call at a concrete element type generates a monomorphic self-recursive specialization whose both splits see a concrete result and fork (at or below grain they run the sequential plSeqMap/plSeqReduce). Used polymorphically or partially applied they degrade to a correct sequential evaluation (the polymorphic copy, whose both sees an abstract result). The specialization references the module's top-level list helpers by-label (static code, empty env) so nothing arena-allocated crosses a fork. Verified deterministic (result identical to sequential, incl. heap-Str deep-copy on join) and memory-bounded on all three targets (linux-x64 native, linux-arm64 qemu, win-x64 wine). |
| TCO back-edge reset of a relocated reuse accumulator | The Ashes.Map "sorted-key SIGSEGV" was misdiagnosed as an AVL/balance bug and a stack overflow — both disproven: balancing is O(log n) (height 18 at 200k sorted keys) and direct sorted inserts of 200k keys run clean; the gdb backtrace showed 2–3 frames faulting on a garbage child pointer (corruption, not exhaustion). The real defect was a use-after-free at the TCO back-edge plain arena reset. An accumulator marked reset-safe (its in-place reuse specialization rewrites it below the loop watermark) was assumed address-stable from its param name alone, but the reset never checked that the back-edge argument expression actually preserved that address. When the value threaded back went through a nested reuse fold whose entry deep-copy was not elided (a retained/declined seed — the move/linearity reuse-copy elision's conservative case), the accumulator was a copy relocated above the watermark each iteration; the plain reset then freed the live tree, and the next round's deep-copy read the dangling source while bump-allocating over it → SIGSEGV (growing key sets shift the layout and expose it; a fixed key set survives by accident). Fix (Lowering.cs): the plain reset now additionally requires the back-edge argument to be provably address-stable — a bare accumulator Var (live-scope slot check), an in-place reuse call whose last arg is stable, or a call to a fold proven to thread its accumulator through at a stable address (elided entry copy + every tail leaf stable, recorded by definition span). When stability can't be proven, control falls through to the existing sound fallback (no reset; the arena grows for the loop's duration). Fully-elided nested reuse folds keep the fast reset (verified RSS-flat at 200k rounds). Regression: tests/reuse_map_tco_reset_declined_seed.ash (growing keys, retained seed — crashed pre-fix, prints 7 post-fix). |
| TCO back-edge argument slot mis-mapping | The reported "recursive ADT accumulator in a non-last curried position → SIGSEGV" was misdiagnosed on the trigger (a lone recursive/copy-field ADT in a non-last position is fine, at 1 iteration and at scale) but pointed at a real, position-keyed TCO miscompile. A recursive function's per-iteration parameter slots (tco.ParamSlots) were built in capture-discovery order (the order free variables first appear in the body), but the back-edge stored argument i into ParamSlots[i] assuming parameter-declaration order (as do the copy-out and the back-edge reset's own address-stability check above). When the two orders differ — e.g. loop s xs n whose body mentions s before xs while a string and a list are both threaded — the string and list pointers were written into each other's slots (a swap); the next iteration then read a list through the string slot and vice versa, corrupting both accumulators and crashing after a single back-edge. It only surfaced with two heap accumulators of different kinds in the "wrong" order (same-kind pairs and copy-type args happened to stay consistent), which is why it looked ADT/position-specific. Fix (Lowering.cs): build ParamSlots in parameter order by resolving each tco.ParamNames[i] through the loop-entry scope (the innermost param resolves to its arg slot, captured params to their freshly-bound locals), so ParamSlots[i] is always the i-th parameter's (and i-th back-edge argument's) slot. Proven with gdb: pre-fix the list slot held the string's address; the swap is eliminated. Regression: tests/tco_multi_heap_accumulator_arg_order.ash (string+list and string+reuse-ADT in reversed capture order — both SIGSEGV'd pre-fix, print 11 15 post-fix). |
Cooperative async runtime — both overlaps in-flight I/O | The original "both lowers inline inside an async state machine" framing was a misdiagnosis (a concrete-result both always forks); the real gap was temporal — the async runtime was eager/synchronous (await/run = a blocking RunTask, and the suspending-coroutine path was dead code), so a both fork could only run before or after an I/O, never during one. Closed by building a real cooperative runtime in slices: (a-1) async(E) with an await now lowers through StateMachineTransform into a suspending coroutine (captures free vars; await → AwaitTask; emits CreateTask), driven by RunTask — behavior-preserving. (a-2) cooperative sleep — a sleeping leaf yields (WaitKind = WaitTimer, remaining ms in SleepDurationMs); the list scheduler waits only to the earliest deadline then decrements, so tasks interleave across sleeps; also fixed the list driver to resolve a coroutine's awaited sub-task before resuming (it read a stale result otherwise). (b-1/2/3) networking overlap: the leaf tasks were already non-blocking (epoll/IOCP/WSAPoll), so with the a-2 driver fix a loopback HTTP/HTTPS request in Ashes.Async.all overlaps a sibling task — verified on linux-x64, win-x64 (Wine), linux-arm64 (qemu). (c) a genuinely-parallel both fork inside an async segment runs concurrently with another task's live I/O, all results correct and memory-bounded on all three targets. Regressions: tests/async_sleep_interleave.ash, async_http_overlap.ash, async_https_overlap.ash, parallel_async_overlap.ash, and AsyncCoroutinePathTests. |
u8 → Int widening | Ashes.Bytes.get returns u8 and there was no way to convert it to Int for arithmetic (b - 48 failed ASH002 … got u8 and Int), so byte-level integer parsing was impossible — code had to slice each field into a Str and parseInt, allocating per row. Added Ashes.UInt.toInt(value) : Int (a new Ashes.UInt builtin module): every uN is a width-masked i64, so the widening is value-preserving for u8/u16/u32 (a bit-reinterpret for u64) and lowers to a retype with no runtime instruction — the saturated call accepts any unsigned width (checked in LowerUIntToInt, not via the reference scheme, which is u8 → Int). A byte from Bytes.get can now feed Int arithmetic directly, enabling the branchless byte parse the 1BRC temperature field wants. Regressions: tests/uint_to_int.ash (u8 get, byte-sum fold, scaled-int parse, getU16Le) and tests/uint_to_int_type_error.ash (a non-unsigned argument is rejected with a clear diagnostic). |
SIMD byte scan — Bytes.indexOf via libc memchr | At the time, the stdlib byte-scan loops were scalar and the LLVM loop-vectorizer was disabled because it was believed to miscompile freestanding parallelism inline assembly. LLVM 22 integration work later failed to reproduce that claim, corrected implicit-memory constraints, and enabled the standard pipelines; this row records the historical motivation for the explicit memchr path. Ashes.Bytes.indexOf delegates to glibc memchr on Linux (SSE2/AVX2), keeping the freestanding scalar loop on Windows (no libc memchr wired there; selected by TargetTriple). memchr added to the shared linux dynamic-import dict (covers linux-x64 and linux-arm64); from is clamped into [0, len] so the size_t length can't underflow, and a NULL result maps to -1. Measured 50× faster on a long scan (4 KB line, ';' near the end, 2M iterations) — but only ~3% on 1BRC brc, whose per-line scans are ~15 bytes (too short for SIMD to beat the call overhead; output byte-identical). Correct on linux-x64, linux-arm64 (qemu), win-x64 (Wine). String.compare / Bytes.hash were assessed and deferred: 1BRC keys/hashes are also short, so memcmp/hashing SIMD would be marginal there, and FNV is inherently sequential. Regression: tests/co13_indexof_memchr.ash. |
Zero-copy mmap file input — Ashes.File.mmap (mmap half) | Added Ashes.File.mmap(path) : Result(Str, Bytes) — memory-map a file read-only and return a zero-copy Bytes view over the mapping, reusing the existing string/bytes view representation ({len|VIEWFLAG, backingPtr}, built for the uncons zero-copy work) via EmitStringView. No read()/copy: the mapping's pages fault in on access, so a data-parallel fold touching different chunks faults them in parallel, and the single mapping is shared read-only across worker threads (verified: the deep-copy-on-fork does not materialize the whole-file view — 8-worker RSS is unchanged, not +8×file). Program-lifetime mapping, so slices into it stay valid. Linux (x64 + arm64) maps the file; Windows falls back to the capped readAllBytes read. challenges/1brc/brc_parallel.ash now uses it: byte-identical output and ~2% faster than the readAllBytes copy (2.68 s → 2.61 s at 10M). The 1BRC win is small because the fold reads every byte (so all pages are resident and the read was already ~1% of the time), but it is a general zero-copy capability (sparse/large-file access, parallel-fault I/O) and the direct answer to "parallelize the read". Regression: tests/file_mmap.ash (linux-x64, linux-arm64 qemu, win-x64 Wine). |
| Loop-invariant heap arg reset-safety — parallel fold made constant-memory | The data-parallel brc was not constant-memory (13.4 GB @ 10M, OOM @ 100M), while the sequential brc is 50 MB flat — with the same Ashes.Map.set. Root cause (distinct from the HashMap.set reuse-eligibility gap closed later by the eta-applied-shape reuse-eligibility entry below): the per-worker fold foldLines(bytes)(pos)(hi)(map) threads the Bytes view unchanged, and the TCO back-edge arena reset requires all args reset-safe. bytes (a heap type) was not recognized as reset-safe, and the accumulator Map is not copy-out-able, so neither the plain-reset nor the copy-out path fired → the loop's arena never reset → every iteration's Map.set scratch leaked. But bytes is loop-invariant — passed as its own unchanged Var at every tail self-call — so it only ever holds the value passed into the loop (below the watermark) and survives a plain reset. Fix (Lowering.cs): compute the set of params passed unchanged at every tail self-call (CollectLoopInvariantParams, with shadow tracking) and treat such a back-edge arg as reset-safe in ArgResetSafe. Result: parallel brc is now near-constant-memory — 10M: 13.4 GB → 1.6 GB; 100M: OOM → 16.9 s / 2.9 GB, byte-identical to sequential (and 7.5× faster than the 127 s sequential run). Verified: full C#/e2e suites, a growing-key UAF stress test (tests/tco_loop_invariant_heap_arg.ash, 400k distinct keys with the invariant Bytes read every iteration), all three targets. (Note: foldLines puts the recursive call directly in each match arm; a let m2 = match … in loop(m2) accumulator is still not recognized — a separate, smaller follow-up.) |
| Data-parallel chunked fold — the full 1BRC | A streaming fold is single-threaded; the data-parallel chunked fold splits a large input into per-core chunks, folds each on a worker, and merges — and it works via the existing Ashes.Parallel.reduce with no new combinator: represent the input as a list of (bytes, lo, hi) chunk tuples split at newline boundaries and call reduce(merge)(emptyAcc)(foldChunk)(chunks). The monomorphized reduce forks each chunk's fold via both at the concrete Map result type, workers read the shared read-only Bytes, and the partial Maps are deep-copied across the fork and merged — byte-identical to the sequential fold (purity makes it order-independent). Sharp edges: foldChunk must be a top-level, non-capturing function (thread bytes through the chunk tuple, not a closure crossing the fork); a worker that reads out of bounds deadlocks the join. Enabled by Ashes.File.readAllBytes (uncapped whole-file Bytes; a standalone mmap on Linux, since a single arena allocation can't exceed one chunk) and preferably Ashes.File.mmap (zero-copy); made constant-memory per worker by the loop-invariant reset-safety fix above. Result: challenges/1brc/brc_parallel.ash runs the 1BRC ultimate goal — 1,000,000,000 rows in 2 m 36 s at 15.9 GB, correct (41,343 stations), ≈8× parallelism (the 8-worker cap) (100M: 16.9 s / 2.9 GB; 10M: 2.6 s / 1.6 GB, 4.9× the sequential brc). Before this arc the parallel path OOM'd past ~15M rows and 1e9 was impossible. Regressions: tests/parallel_chunked_fold.ash, tests/file_read_all_bytes.ash. |
Three-way byte compare intrinsic (Ashes.Bytes.compare) | String.compare was a byte-at-a-time TCO loop (Bytes.get per byte) executed ~2×tree-depth times per keyed-map operation. Added the BytesCompare IR instruction + emitter (one memcmp over min(len), length tie-break, normalized -1/0/1, view-aware) and rewired Ashes.String.compare to delegate through Bytes.fromText. Sequential 1BRC 13.6 s → 12.1 s @10M. Regression: tests/bytes_compare.ash. |
Known-closure devirtualization (IrInst.CallKnown) | Every helper call was MakeClosure (a 32-byte arena alloc) + an indirect call *(reg) through the closure's code pointer — opaque to LLVM's inliner. New IR pass (IrOptimizer.DevirtualizeKnownClosureCalls): a CallClosure whose closure temp is a single-definition MakeClosure/MakeClosureStack (and whose env temp is single-definition) becomes CallKnown(label, env, arg) → a direct LLVM call that inlines; stranded MakeClosures are removed by dead-code elimination. Debug builds give locationless CallKnowns an artificial line-0 !dbg (LLVM requires locations on inlinable calls). |
| Redundant arena-bracket elision | Lowering brackets function bodies and copy-type-returning helper calls in SaveArenaState/RestoreArenaState/ReclaimArenaChunks; for tiny accessors (Map.height) the reclaim's munmap loop + dynamic stack slot made them ~78 instructions and ineligible for LLVM inlining. New interprocedural pass: a whole-program non-allocation fixpoint (explicit whitelist; CallKnown via callee summary), then (a) every bracket in a provably non-allocating function is removed, and (b) straight-line Save…Restore(+Reclaim) triples guarding only non-allocating instructions are removed. With devirtualization: sequential 1BRC 12.1 s → 6.5 s @10M (helpers now inline into the reuse spec). The straight-line rule takes the bracket's ReclaimArenaChunks with the save and restore wherever the close placed it — right after the restore, or past the conditional copy-out block a call window puts between the two — since a reclaim left behind reads the slots the removed instructions no longer write (found by the self-hosted backend, whose local slots are not zero-initialized). |
Runtime worker-cap detection + --parallel-workers (completion) | The fork gate compared against a hard-coded cap of 8. The cap is now the machine's core count, detected once at first fork and cached in a global (__ashes_parallel_cap_get: linux x64/arm64 sched_getaffinity + SWAR popcount of the 128-byte mask — respects taskset/cgroup masks; win-x64 GetSystemInfo.dwNumberOfProcessors, new PE import; fallback 8 when detection reports nothing). --parallel-workers <n> pins a fixed cap at compile time (threaded BackendCompileOptions.ParallelWorkerCap → fork-gate constant). On a 32-core box the parallel 1BRC went 8-way → ~29-way. |
Zero-copy byte slices — Ashes.Bytes.subView (explicit half) | subText copies its result; per-record name slices in scan loops paid an alloc + memcpy per row. subView returns the existing zero-copy view representation ({len|VIEW, ptr}) over the same clamped range — O(1), no byte copy. Lifetime is explicit (backing must outlive the view; mmap backings are program-lifetime, and values stored into structures are materialized by the copy-out/blob paths), so an automatic escape-analysis variant (inferring a safe zero-copy view without an explicit call) remains open, unimplemented follow-on work. Regression: tests/bytes_subview.ash. |
Str-specialized map operations (Ashes.Map.getStr/setStr/upsertStr) | get/set take a comparator closure — two indirect calls per node visit that no analysis could devirtualize (the closure is a parameter). The Str-keyed variants compare with the Bytes.compare intrinsic inline (UTF-8 byte order, same total order as String.compare); upsertStr(key)(missValue)(onHit) folds the lookup and the update into one traversal. All three are reuse-specializable like set (the upsertStr spec fires fullyReusing). Regression: tests/map_upsertstr.ash. |
| User-file functions join the reuse machinery | Only stitched module (Ashes_*) functions were ever registered for reuse specialization — the stitcher renders the user program as a nested let-pyramid in the entry body, which RegisterInlinableFunctions never saw, so a user-defined Map.set-shaped fold silently missed in-place reuse (9 KB/row leak). RegisterEntryBodyFunctions now walks the entry body's leading let-chain and registers specializable shapes, gated on (a) no shadowing anywhere in the body (binder-count walk) and (b) the lambda's free variables all resolving to stitched top-level bindings (a spec lowers in an isolated scope where only by-label/inline resolution works). The inline path also accepts qualified stdlib callees (Ashes.Map.makeNode inside a user spec). Two supporting soundness/precision fixes: (1) a constructor field that is any non-variable expression in a spec arm (e.g. an upsert's onHit(value) result) is now materialized into the persistent blob — previously only fresh-input variables were, so an in-arm computed value dangled past the reset (caught as scale-dependent corruption); (2) IsFullyReusing accepts a fresh in-arm Alloc that is only written into, field-read, borrowed, moved through single-store locals, and finally materialized (CopyFixedInto/CopyOutArenaToSpace). Regression: tests/reuse_user_fold_specialization.ash. |
| 1BRC result after this arc | challenges/1brc/brc_parallel.ash (subView slices + user upsertMeasurement + auto worker cap, 32 chunks): 1e9 rows in 24.7 s (was 2 m 36 s — 6.3×), byte-identical output, 41,343 stations, ~29× parallelism on a 32-thread box. Sequential brc.ash (getStr/setStr): 10M in 6.5 s (was 12.8–13.6 s), still ~50 MB flat. |
16-ary hash trie (Ashes.HashTrie) — reaching the sub-10 s 1BRC goal without the originally-planned compiler generalization | The sub-10-s blocker was framed as "a trie descent must thread the shifted hash, so the reuse spec needs a multi-parameter inner go". The shipped design sidesteps it: each TrieNode16 carries its own nibble shift (HAMT-style path compression, splits at the first differing nibble of the two hashes; equal-hash collisions chain through the leaf's next), so the descent is a single-parameter go and the existing specialization machinery applies unchanged. Enabler in the compiler: AccumulatorIsFullyPersistent generalized from its MapTree special-case to a structural check (every constructor field is the accumulator ADT itself or a reuse-materializable leaf type), which admits Trie (and any similar user ADT) to the per-iteration arena reset. Found + fixed en route: a reuse-token/blob-aliasing hazard (later closed by the reuse-token liveness gate below) — the trie's split arm builds two same-arity TrieLeafs, and the fresh-value leaf stole the matched cell's reuse token, so its in-place value materialization clobbered the old leaf's blob cell while the sibling rebuild still referenced it (silent cross-key stat corruption at scale); Ashes.HashTrie avoids it by binding the rebuild first (it takes the token and writes its own value pointer back), and the general compiler-side gate is the reuse-token liveness gate below. Result: 1BRC 1e9 rows 24.7 s → 12.2 s (challenges/1brc/brc_trie.ash; sequential fold 3.9 s → 1.6 s @10M), byte-identical output, constant memory per worker. Regression: tests/stdlib_hashtrie.ash. |
| Reuse-token liveness gate | The in-place value materialization (CopyFixedInto over the matched cell's blob) assumed the token-consuming constructor supersedes the old value — false when the arm also rebuilds the matched cell as a sibling (the hash-trie leaf split), where the fresh-value constructor stole the token and clobbered a blob the sibling still referenced (silent cross-key corruption). Gate: at token issuance each variable-bound field records (local slot, total references in the arm body); LowerVar counts references as they lower (lowering order = evaluation order within a path); the in-place path is taken only when every reference to the superseded binding has been accounted for, else the update materializes a fresh blob cell (bounded — one extra cell per such arm, e.g. per trie split). Branch handling: while lowering one arm of an if/match, sibling-branch references are pre-credited as seen (mutually exclusive at runtime), and on branch exit the seen-map is restored to its entry snapshot — rolling back both the credits and the branch's own increments, so a sibling (or the join) never observes path-local references; totals are shadow-unaware over-counts and seen is slot-keyed, so every imprecision forces the safe fallback. Debugged via a 200-key repro: two prior unsound iterations (stale counters across re-lowerings of the same function — reset at issuance; then-branch increments leaking into the else — snapshot restore) each manifested as wrong gate verdicts in the compile-time [co23] trace. Ashes.HashTrie's split now uses the natural construction order (the fresh leaf first), exercising the gate in production; 1e9-row 1BRC unchanged (12.2 s / same RSS — the hot hit-arm update keeps the in-place path). Regression: tests/reuse_split_sibling_value.ash. |
| 1BRC parallel-efficiency investigation + worker-slot release at completion | The measurement plan ran in full on the 32-thread reference box (Ryzen 9 9950X3D — 16 cores / 32 HT in two asymmetric CCDs: CCD0 has 96 MB V-cache L3, CCD1 32 MB). (1) Per-worker tail (100 ms /proc/<pid>/task/*/stat sampling): all 32 HT saturate to ~8.7 s, then a ~4 s decay tail — and the finish order partitions almost perfectly by CCD: V-cache workers need 8.4–9.1 s CPU per equal chunk, CCD1 workers 10.5–11.9 s (~1.4×). Cause is L3 fit: 16 workers × ~5 MB trie working set sits inside CCD0's 96 MB but thrashes CCD1's 32 MB; the workload is latency- not bandwidth-bound (~5–10 GB/s of ~80). (2) Isolation runs (taskset, whole file): CCD0-16HT 21.1 s / 229 s CPU, CCD1-16HT 29.1 s / 340 s, CCD0-8-solo 22.0 s / 164 s, CCD1-8-solo 35.9 s / 229 s → SMT is worth ~1.4× throughput per CCD; an optimal static CCD-proportional split computes to ≈ the observed baseline, i.e. OS placement already achieves it — placement/affinity is a wash, the loss is fork-join packing. (3) Root cause of the chunk-count dead end: the worker-slot counter was released in the parent's join cleanup, so the cap counted un-joined descriptors, not running workers — an exited worker freed no capacity until the static join tree happened to reach its join, so finer chunking could never rebalance. Fix: release __ashes_parallel_active in the worker trampoline right after the result is published (all three flavors); cleanup now only reclaims OS resources. At the default 32-chunk config this is behavior-neutral by construction (31 forks never exceed the cap, so every fork spawned before and after — interleaved A/B confirms parity within noise at ~12.2–12.9 s), but it makes the cap honest and is a prerequisite for any queued scheduler. Chunk counts above the cap were remeasured with the new semantics (48/64/96/128/256): slot turnover now genuinely works (129 threads spawned over a 256-chunk run; 256 chunks improved ~13.1 → ~12.5 s) but every such config still loses to 32 chunks — a fork-join tree without work stealing blocks parents at joins, so freed slots idle whenever no thread has a pending fork to shed. Ceiling analysis: saturated-phase throughput is 3.26 chunks/s → ~9.8 s fold floor + 0.4–0.7 s serial merge/sort/format tail ≈ 10.2–10.5 s is this fork-join runtime's ceiling on this box; sub-10 s needs a work-conserving scheduler and likely per-worker working-set reduction below CCD1's per-worker L3 share on top. Also fixed en route: win-x64 parallel compilation had been broken since the auto-cap commit — EmitParallelWorkerCapFn named the void GetSystemInfo call, failing LLVM module verification on every program that forks; unnoticed because wine-target tests are not in the default suite. All 8 parallel e2e tests now pass under wine, and the arm64 both coverage passes under qemu. |
Work-conserving queued Parallel.reduce | A saturated 4-arg Parallel.reduce at a concrete, worker-liftable result type now lowers to a runtime chunk queue instead of the grained fork-join tree (reduceGrained keeps the tree — an explicit grain requests the divide-and-conquer shape; abstract result types still fall back to the sequential combinator). New IR ParallelQueueStart/Await/Cleanup: __ashes_parallel_queue_start snapshots the list into one zeroed OS region (header, elements, per-index results, per-index publish flags, 64-byte worker records) and spawns min(cap, n) workers under the same active-slot counter as both — when not a single slot is claimable the caller drains the whole queue inline, so nested queued reduces cannot deadlock. Workers pull element indexes from a shared atomic counter (lock xadd on x64, ldaxr/stlxr on arm64), evaluate f(elem) in their own per-thread arena, and publish each result under its flag word (atomic-increment release + futex wake; win-x64 awaits by Sleep(1) poll — results arrive at chunk granularity, so the poll is cold). The caller awaits indexes in ascending order and left-folds combine as results arrive — the merge overlaps the remaining fold — deep-copying each raw result before cleanup frees the worker stacks, arena chains, TCBs, and the region. Determinism: fixed list-order merge under the same associative-combine contract the tree already assumed; empty list yields the identity, a singleton yields f(x) alone, exactly like plSeqReduce. The both clone/trampoline machinery is reused (worker records mirror the fork-descriptor offsets 32–56, so the hardcoded ctid asm serves both layouts). Measured at 1e9 rows (interleaved A/B, chunk sweep 32/48/64/96/128/192/256): the per-thread timeline is now the flat 32-active band the parallel-efficiency investigation above asked for (~0.2 s head, ~10.5 s fully-packed fold, then a decay tail of last-chunk stragglers plus the parent's serial merges), 128 chunks is the sweet spot, and the wall is ~11.9–12.5 s vs ~12.5–14.8 s for the fork-join baseline in the same interleaved session with byte-identical output (256 chunks regresses to ~13.8 s — the serial in-order merge becomes the bottleneck; CPU% drops as workers finish while the parent still merges). Sub-10 s was not reached, and the parallel-efficiency investigation's estimate above is falsified by measurement: the ~9.8 s fold-floor arithmetic assumed total fold CPU stays ~285–300 s, but at a full 32-wide pack the same fold costs ~335–345 s CPU — per-row cost inflates under sustained full LLC/bandwidth pressure, i.e. the idle that the queue eliminated had been partly hiding contention (at 32 chunks queue-vs-tree total CPU is identical, ~320 s; the growth appears exactly when packing tightens). Wall floor is therefore ~10.7 s + merge tail even with perfect scheduling. Remaining levers, per this measurement: per-worker working-set reduction below CCD1's per-worker L3 share (attacks the contention itself; the earlier investigation estimated it insufficient alone), and a deterministic pairwise parallel merge (removes the serial tail that dominates ≥192 chunks); likely both are needed together for sub-10 on this box. Tests: tests/parallel_reduce_queue.ash (empty/singleton/order-sensitive-combine/n-above-cap; passes on linux-x64 and under wine), arm64 qemu coverage test for list-order merging, plus the existing parallel suite on all three flavors. challenges/1brc/brc_trie.ash raised from 32 to 128 chunks. |
Deterministic pairwise parallel merge for the queued reduce | The work-conserving queued reduce above ran all n−1 combine merges serially on the awaiting caller, the measured bottleneck above ~192 chunks (256 chunks: ~13.8 s while workers idled and CPU% sagged) and the cap on chunk granularity — which matters because finer chunks are the queue's straggler defense. Now the workers merge: the queue region carries an item slot and a publish flag for every node of the merge tree (S = n + ceil(n/2) + … + 1 slots, arrays laid round-major), and the drain loop gains a second phase — once the element counter is exhausted, workers claim merge tasks from a second atomic counter in round-major order, wait on the task's two operand flags (futex; Sleep(1) poll on win-x64; at most one waiter per flag since every item has exactly one consumer), and publish combine(left)(right) — or promote an odd round's trailing item — under the output's flag. Round-major claim order is topological, which makes the scheme deadlock-free by construction: the claimed prefix is contiguous (fetch-add), so the earliest incomplete task is always claimed and its operands (all in earlier rounds) are already published. The tree pairs adjacent indexes per round, so its shape depends only on n and respects list order — deterministic under the same associative-combine contract, byte-identical 1BRC output (md5-verified at 100M and 1e9). The caller now awaits only the root and deep-copies once (was: n per-result copies + n−1 serial combines) and no longer competes as a 33rd runnable thread; intermediate merge results live in the arenas of whichever workers computed them (mixed-arena trees are fine — every worker arena stays live until cleanup, which runs after the root copy). Measured at 1e9 rows (interleaved, 3 rounds, vs the pre-merge-fix compiler): 128 chunks 11.83–11.87 s vs 11.78–12.03 s (parity with a tighter spread — at 128 the overlapped serial merge had not yet been the bottleneck), and the ≥192-chunk regression is gone: 256 chunks 12.19–12.35 s (was ~13.8 s), 384 chunks 12.6–12.7 s, with CPU% flat at ~2900% for every chunk count (the workers-idle-while-parent-merges dip no longer exists) and the post-fold decay tail down from ~1.7 s to ~0.6 s (what remains is last-chunk straggler spread plus the constant ~0.4 s sequential sort/format epilogue). The 128-chunk wall is unchanged, as the earlier analysis predicted: the binding constraint is fold CPU under full LLC/bandwidth pressure, and finer chunks still cost more total CPU (~345 s at 128, ~355 s at 256, ~368 s at 384) — per-worker working-set reduction is now the single remaining sub-10 lever. Tests: order-sensitive odd-count merges (promotion rounds) added to tests/parallel_reduce_queue.ash (n = 13) and the arm64 qemu coverage (n = 7); full suites green on all three flavors. |
| Per-worker working-set reduction investigated and falsified — the 1BRC sub-10 s question is closed on this box | Measurement first: the per-worker hot set was computed exactly by replaying the trie build offline (station set parsed from the reference output; FNV-1a 64 replicated; HashTrie's split/chain algorithm simulated) — 41,343 stations make 13.2k TrieNode16 internals (1.90 MB at 144 B each, average occupancy 4.1 of 16 slots, 56% of nodes hold exactly 2 children), 41.3k leaves (1.65 MB), 41.3k boxed stats tuples (1.32 MB), key view headers (0.66 MB) = 5.5 MB structural (confirming the earlier parallel-efficiency investigation's ~5 MB estimate), plus ~2.6 MB of scattered file-map cache lines touched by the per-row leaf memcmp against stored zero-copy subView keys. Two reduction experiments were then built and A/B-measured at 1e9 rows, both byte-identical to the reference output: (1) packed stats + dense keys — min/max/count bit-packed into one word (value cells 32 → 16 B) and inserted keys copied via subText so stored keys live densely in the blob instead of 41k scattered file positions (~3.3 MB effective reduction): parity on the full box (12.19–12.47 s vs 12.30–13.20 s interleaved) and — decisively — 3% slower when pinned to the small-L3 CCD alone (27.1 vs 26.3 s on CCD1's 16 HT, where footprint pressure is maximal); (2) inline-value leaves — a TrieLeafP(hash, key, w1, w2, next) packed-leaf constructor storing both stat words inline, eliminating the per-row boxed-value dependent load and its cell: ~5% slower (12.86–13.38 s vs 12.20–12.36 s) — the extra scalar-closure call and wider leaf cost more than the removed cache line saved. Conclusion: the fold is bound by the length and latency of the serialized dependent-load chain per row (~4–6 loads through node hops, leaf, and key bytes), not by the working set's byte count — shrinking footprint by ~40% changed nothing even under maximal L3 pressure, and shortening the chain by one link cost more in call overhead than it saved. With scheduling fully solved (/26) and footprint falsified, sub-10 s at 1e9 rows is closed as not reachable on this box with the current per-row upsert architecture; the wall stands at ~11.9 s. Any future attempt needs a different shape entirely (e.g. row batching that overlaps multiple independent descents to hide latency — nontrivial in a pure per-row fold). Experiment code was reverted (repo unchanged except this analysis); kept: a debug print in IsFullyReusing's instruction-kind reject path. Reuse-machinery landmines hit en route, recorded for the in-place-reuse-eligibility and entry-body-helper-inlining work below: a copy-type-returning closure parameter called inside a specialized go gets an arena-bracket CopyOutArena that disqualifies IsFullyReusing (silent 55 GB leak); an accumulator ADT whose type still carries an unresolved type variable (a phantom V never constrained by the packed operations) fails AccumulatorIsFullyPersistent and silently disables the per-iteration reset — pin such parameters to a concrete type; a pair-returning update closure destructured in a spec arm leaks its 16 B tuple per row into to-space. |
| In-place-reuse eligibility generalized to the eta-applied shape | The constant-memory reuse specialization fired only for the Map.set structural shape (outer params, then let recursive go = … in go returned bare). Ashes.HashMap.set writes the equivalent worker differently — given k -> given v -> given map -> (let target = hashKey(k) in let recursive go tree = … in go(map)) — so a HashMap-keyed fold was not specialized and leaked 9.6 GB at 1M inserts (vs Map's constant ~9 MB). Two independent gaps, both fixed in Lowering.cs: (1) detection — TryGetNestedRecursiveReturn now peels a leading chain of non-recursive lets before the let recursive and accepts the eta return … in go(lastOuterParam) (the accumulator arrives as the last outer argument and is forwarded verbatim into the worker, whose own parameter stays the linear reuse root; argCount = outerParams for the eta form vs outerParams + 1 for the bare form). (2) IsFullyReusing — HashMap's per-node composite-key descent inlines strCompare's own let recursive go i = … in go(0) helper, whose closure is MakeClosure → StoreLocal → LoadLocal → CallClosure (a stored-then-called recursive helper under an arena bracket that yields a scalar and never escapes into the rebuilt tree). The old check rejected any MakeClosure whose reader was not a direct CallClosure callee; it now accepts a closure that is consumed as a call target through a single-store local slot or Borrow (mirroring the existing SafelyConsumed walk), while still rejecting a closure passed as a call argument (which could be captured or returned). With both fixes the Ashes_HashMap_set__reuse spec is fullyReusing and the fold is constant memory: 9.3 MB at 1M and 9.1 MB at 4M inserts into a bounded keyspace, output identical to Map. Verified for correctness (not just footprint) by a growing-key insert+update+readback checksum against an independently computed value. The change is general — any user function with the eta shape and a stored-then-called helper is now specializable (confirmed on a synthetic user tree). Regression: tests/reuse_hashmap_set_bounded.ash (200k growing string keys, every 7th updated, spread-readback checksum). |
Let-bound match/if accumulator recognized for the loop arena reset | The per-iteration arena reset requires the loop's back-edge accumulator to be provably address-stable (IsStableAccumulatorExpr), which only held when the recursive call sat directly in each match/if arm (` |
| Entry-body helper inlining via a transitive free-variable closure | Entry-file functions (user declarations, which the import stitcher renders as the program body's nested let-chain rather than top-level items) were registered for reuse only as specializations, and only when self-contained — every free variable had to be a stitched module binding. So a user fold that called its own local makeNode-style rebuild helper was rejected outright (the helper is a user sibling, not a stitched name) and leaked (1.48 GB at 1M inserts vs constant when the helper was Ashes.Map.makeNode); user-local helpers were never registered as inlinable at all. Fix (Lowering.cs RegisterEntryBodyFunctions): collect the entry let-chain's single-binder lambda candidates, then compute the maximal registerable set by fixpoint — a candidate is registerable iff every free variable of its body is globally resolvable at an inline/spec site (a stitched module binding, a constructor, or an already-registered function) or is itself another registerable candidate. Each registerable function is then registered exactly like a flat top-level item: the nested-recursive-return / single-param-recursive shapes become reuse specializations, and any other non-recursive helper with an allocating body becomes an inlinable rebuild helper (into _inlinableFunctions / _inlinableDefiningValues). Soundness: the fixpoint's key property is that a registerable function captures nothing that isn't globally resolvable, so it lowers as an empty-env by-label callee (reaching _topLevelFunctionRefs) and its body resolves when inlined inside another function's specialization — which is exactly the scope hazard the old all-stitched gate existed to avoid (registering helpers naively had produced ASH001). Verified in both directions: a three-deep chain upd → mkNode → hgt (each helper referencing the next, bottoming out at constructors) specializes to fullyReusing constant memory (1.4 MB at 500k inserts), while a helper that captures a plain value binding is correctly left unregistered and still compiles and runs correctly. Correctness checked (not just footprint) by a growing-key insert+update+full-readback checksum whose totalSum = n(n-1)/2 and totalCt = n are shape-independent. Regression: tests/reuse_user_local_helper_specialization.ash. |
| Debug info combines with any optimization level | --debug capped optimization at -O1, and the -O1 pipeline runs no inliner, so a sampled profile of a debug build systematically exaggerated call overhead vs the real -O2 binary (1BRC helpers showed ~30% self at O1-debug but inline at O2). Fix: the CLI cap is removed — --debug still defaults to -O0, but an explicit -O1/-O2/-O3 is now honored (both the compile and run arg parsers). Two backend pieces keep the optimized debug output valid: (1) the artificial line-0 fallback that previously covered only a devirtualized CallKnown now applies to every unlocated instruction in a scope — the -O2/-O3 inliner stitches each inlined instruction's !dbg into an inlined-at chain rooted at the call site, so any call left without a location produces invalid debug info; line 0 is the DWARF convention for compiler-generated code. (2) When debug info is emitted the backend re-verifies the module after the passes (the existing verify runs only on the unoptimized module), so an inliner-mangled location fails the build instead of shipping as broken DWARF. Verified: compile --debug -O2 is llvm-dwarfdump --verify-clean, gdb sets file:line breakpoints and shows correct backtraces identically to --debug -O0 (both map lines 2/3/6/7/9/11 and break at _start_main), the optimized debug binary is far smaller than the O0 debug binary (109 KB vs 178 KB — the inliner ran) and its wall time equals plain -O2 (0.49 s vs 0.49 s on a 2e8-iteration loop), and O1/O2/O3 debug builds all run correctly. Docs: DEBUGGING.md and COMPILER_CLI_SPEC.md updated. Regression: OptimizationLevelTests.Debug_info_combines_with_every_optimization_level (O0–O3, helper/recursive calls driving the inliner; the post-pass verify throws on bad debug IR). |
Ashes.Parallel.splitChunks record-boundary chunker | The data-parallel byte-scan (1BRC) hand-rolled a buildChunks helper to split the mmap'd buffer into (bytes, lo, hi) sub-ranges at newline boundaries before Parallel.reduce. The original design framed this as a reduceChunks(bytes)(sep)(n)(identity)(foldChunk)(merge) combinator; the prerequisite it named — a stdlib module importing another Ashes.* module — is now already supported (post the inline-modules work: import Ashes.Bytes inside lib/Ashes/Parallel.ash compiles and runs). But a measurement falsified the wrapping combinator: Parallel.reduce gets its parallelism by monomorphizing the user's call at a concrete result type, so wrapping it in a polymorphic stdlib reduceChunks degrades the inner reduce to the sequential fallback — measured 99% CPU / 0.54 s vs a direct call's 2342% CPU / 0.04 s (same result, 13x slower). The fix ships the splitting as a pure helper and leaves reduce at the caller: Ashes.Parallel.splitChunks(bytes)(sep)(n) : List((Bytes, Int, Int)) (importing Ashes.Bytes for indexOf/length), used as reduce(merge)(identity)(foldChunk)(splitChunks(bytes)(sep)(n)). This keeps the ergonomic win (the buildChunks boilerplate is gone) with no parallelism footgun — measured 1864% CPU / 0.05 s on the same scan, and challenges/1brc/brc_parallel.ash now calls splitChunks(bytes)(10)(32) in place of its buildChunks, byte-identical output (md5-verified at 10M) and still parallel. Regression: tests/parallel_split_chunks.ash (chunk count, per-chunk fold sum, and exact buffer tiling via a spans-sum). Docs: STANDARD_LIBRARY.md. |
Ashes.Regex backed by PCRE2 | The self-hosted combinator regex engine is replaced by PCRE2. The 8-bit library (Unicode on, JIT off) is compiled from source to per-target LLVM bitcode (scripts/download-pcre2.sh → runtimes/<rid>/libpcre2.bc), stripped to the exposed API with internalize+globaldce, and linked into a program only when it uses Ashes.Regex, after the program's own optimization passes — mirroring the openlibm model. PCRE2's malloc/free route to an emitted bump allocator over a lazily-mmap'd 64 MiB region; a compiled pattern (pcre2_code*) persists there (stable handle — the arena never relocates it) and per-match scratch is reclaimed by a region cursor save/restore. Five backend intrinsics (RegexCompile/RegexCompileError/RegexFind/RegexCaptures/RegexSubstitute) back the pattern-string API (compile/isMatch/find/findAll/captures/replace). The Windows payload uses the windows-gnu triple (MS x64 ABI, >4-arg calls) with vendored declaration-only stub headers + a memchr/strchr/ctype shim, so no MinGW sysroot is needed. Byte-identical on linux-x64/arm64/win-x64. Pinned via <Pcre2Version>; payloads git-tracked like libopenlibm.bc. |
Overload-generic == / != / + helpers (superseded by traits) | This historical bridge made a non-recursive helper applying ==, !=, or + directly to two parameters usable at several primitive types by inlining a type-resolved body at concrete call sites. The trait implementation removed this correctness path: constrained functions now receive ordinary Eq(a) or Add(a) evidence, and primitive calls retain their specialized IR. |
String/Json/Rpc on Bytes primitives | The stdlib string hot paths scanned char-by-char via Text.uncons (a string-view allocation per character), and String.split was O(n²) (its substring re-walks per field). Rewritten on the Bytes layer (memchr-backed Ashes.Bytes.indexOf, byte slicing): String.startsWith/indexOf/contains/split/trim*, a no-escape string fast path in Json.parseQuotedStr, and Rpc.parseContentLength. Measured ~1000× (String.split) and ~900× (Json.parse of a string-heavy payload) faster at the same or smaller binary size, with no PCRE2 dependency. A benchmark confirmed a regex-backed stdlib would instead be slower and +300 KB on every consumer (PCRE2 links whenever any lowered function uses a regex intrinsic, even uncalled). indexOf still returns a code-point index; public API and Unicode behavior unchanged. |
Local type declarations coexist with stitched imports | A user file that both imports a stitched module (import Ashes.String, ...) and declares its own ADT (type Shape = ...) failed with ASH003 Expected expression but found EOF, forcing user programs to piggyback on stdlib ADTs. The type declarations were in fact already hoisted to the very top of the combined source; the failure was in the entry-body placement: BuildCompilationLayoutCore only parenthesized the entry body when the entry had no type declarations, so a type-declaring entry was appended bare after the stitched module bindings — where a flat declaration block cannot parse (the paren wrap is exactly what routes the entry through the parser's parenthesized flat-entry-block path, and after a legacy binding chain's trailing in a bare flat block never parses). Fix: parenthesize the entry body whenever any module binding precedes it, independent of hoisted type declarations; the paren branch now carries the entry's type-declaration length as the layout's BodyStart so diagnostic span mapping keeps working, and the entry-only-type-declarations case (no stitched bindings) still appends bare — an ordinary flat program with exact original offsets for the type region. Verified: flat entries (types + lets + trailing expression, including a type declared between lets with constructors used across declarations) and legacy pyramid entries both compile and run with stitched imports; stitched-module calls resolve in both flat let values and the trailing expression. Regressions: tests/type_decl_with_stitched_import.ash, tests/type_decl_with_stitched_import_pyramid.ash. Noted en route (pre-existing, unchanged): referencing a nonexistent member of an imported stitched module reports a misleading Unknown module 'Ashes.String' instead of an unknown-export error. |
Growing whole-value accumulator reclamation — fixed loop-entry watermark + BigInt copy-out | A TCO loop re-saves its arena watermark at the loop-body label, so the mark advances past the threaded accumulator each iteration. For a cons-list that is correct and O(N) (only the fresh top cell is copied; the shared tail stays below the mark), but for a growing whole-value accumulator (String, BigInt) the whole value is copied to the new mark each iteration and the previous copy is stranded below it forever → O(N²) resident memory (pidigits N=1000 = 168 MB; a growing-String fold = 195 MB @ 20k iters). Two changes: (a) a BigInt is a self-contained {header, limbs} buffer with no internal pointers, so it is copied out across the reset like a String — a BigIntSize sentinel on CopyOutArena reads the byte size from the header limb count — reclaiming the loop's intermediate BigInt garbage; (b) a loop threading only non-sharing whole-value accumulators (copy type, resource handle, String, BigInt — never a TList, whose shared tail needs the advancing mark) saves a second fixed loop-entry watermark and resets to it, so each grown accumulator overwrites the previous one in place. Result: pidigits 168 MB → constant 0.25 MB at every N (only the O(N³) long-division time remains); a growing-String accumulator loop 195 MB → 0.25 MB; output unchanged. Fixed en route (correctness, challenges/fannkuch): the shallow single-cell TCO list copy-out preserved only a list's top cons cell, so a rebuilt/multi-cell list left interior cells dangling (dropped early ADT return, then segfault at N≥3) — the reset is now disqualified for any list accumulator that is not a single fresh cons. Regressions: tests/bigint_tco_accumulator.ash, tco_fixed_watermark_whole_value_accumulators.ash, tco_multi_fresh_list_accumulator.ash. |
| Fixed-shape pointer-bearing accumulator reclamation — deep-copy-out for ADTs and tuples | A pointer-bearing accumulator that is a fixed-shape (non-recursive) ADT (fannkuch's State(perm, count)) or a tuple (fasta's (seed, output)) returned CopyOutKind.None, so any loop threading one disqualified the arena reset entirely and every per-iteration transient leaked (fannkuch N=10 = 4.6 GB; a (seed, String) fold O(N²)). Such a value is carried across the reset by a recursive deep copy (the existing synthesized ADT copier / EmitDeepCopy tuple rebuild) — a self-contained clone whose list/string fields are fully copied, which breaks any tail-sharing with the previous accumulator and so is fixed-watermark safe. Added CopyOutKind.DeepAdt + a CanDeepCopyOutAdt predicate in GetTcoCopyOutKind; self-recursive ADTs (trees like MapTree) are excluded — an unbounded per-iteration deep copy would be O(size)/iter and those shapes are owned by the in-place reuse specialization (deep-copying one out from under it corrupts it, caught by the reuse_* suite — hence a path-based cycle check that declines any self-recursive ADT). Result: fannkuch 4.6 GB (N=10) → constant 0.25 MB, N≥11 now reachable (time-bound only); a (Int, String) tuple accumulator bounded (fasta's natural form). Regressions: tests/tco_deep_adt_accumulator.ash, tco_tuple_accumulator.ash. |
Ashes.String.substring from O(start + count²) to O(start + count) | substring was take(drop(text)(start))(count): drop walks start codepoints via Text.uncons, and take rebuilds count codepoints with per-character string concatenation (each an O(count) copy), so a sliding k-mer window (k-nucleotide) was catastrophic — ~63 s at 8000 characters. Rewrote it as a single codepoint→byte-offset walk (reusing the UTF-8 start-byte rule: a byte is a codepoint start iff < 128 or >= 192) plus one Ashes.Bytes.subText, so it is O(start + count) with no concatenation and stays codepoint-correct (verified on multibyte UTF-8). The same 8000-character window now runs in 0.03 s (~2000×). It is still O(position) per call because strings are not byte-indexable; the standard-library reference now steers repeated indexed slicing to the byte-indexed Ashes.Bytes.subText (O(count) per slice). Regression: tests/stdlib_substring.ash. |
| Variable-sized heap chunks — a single allocation larger than one chunk no longer OOMs | The arena grows in fixed 4 MiB OS chunks, and EmitHeapEnsureSpace loops grow→recheck until a request fits — but EmitHeapGrow always allocated exactly one 4 MiB chunk, so any single allocation larger than 4 MiB never fit and grew one chunk per iteration forever, exhausting memory (surfaced by regex-redux: chaining Ashes.Regex.replace on a >1.5 MB subject allocated the 2*subject + 256 substitute buffer, which exceeds a chunk, and blew up to a constant ~28 GB before the OS refused — even with a non-matching pattern, since the fault is in accepting the large subject; the same trap applied to any large String/Bytes allocation). Chunks are now variable-sized: EmitHeapGrow sizes an oversized chunk to max(4 MiB, request + overhead). Because the abandoned-chunk reclaim walk reconstructed a chunk's base as end − 4 MiB (a fixed size), each chunk now carries an 8-byte header (the previous chunk's end, for the backward link) and an 8-byte footer at its usable end (its own base), so the walk recovers a chunk's base from its end pointer with no size assumption. All chunk sites share one format via a new EmitHeapChunkSetup: the main arena init/grow/reclaim, the per-thread to-space, and the parallel worker arena setup + parent-side worker-chunk free walk (LlvmCodegenParallel). Result: the ~5 MiB regex chain completes in bounded memory, and 1000 iterations of a reclaimed >4 MiB temporary stay flat under a 2 GB cap (no leak, no corruption) on all three targets. Regression: tests/regex_large_subject_chain.ash. |
List(ADT) accumulator reclamation + the DeepAdt two-pass overlap fix | Completes the fixed-shape pointer-bearing accumulator reclamation above: a TCO loop threading a List(fixed-shape-ADT) accumulator (n-body's List(Body)) previously disqualified the arena reset entirely (CopyOutKind.None), so every per-iteration transient leaked — O(N) growth for a constant-state loop. A synthesized recursive list deep-copier (SynthesizeListDeepCopier, cached per element type; nil passes through, each head deep-copies via EmitDeepCopy — e.g. through the element ADT's synthesized copier — and the tail recurses via the self-closure at env[0]) clones the list whole, so GetTcoCopyOutKind classifies List(deep-copyable-element) as DeepAdt and the loop takes the fixed loop-entry watermark. Measured: a 5-record List(Body) advanced 3,000,000 steps runs at 0.25 MB max RSS (was 4.27 GB at 1e6). Root-caused en route (a first attempt had been reverted on a wrong "async interaction" diagnosis): the two-pass back-edge copy-out's disjointness argument has a hole for DeepAdt — Phase B writes its down-copy at [W, W+S) while reading the Phase-A up-copy at [W+B, W+B+S) (B = the loop body's allocations that iteration), overlapping whenever B < S. Shallow kinds are safe because the fresh accumulator itself was just body-allocated (B >= S); a deep clone's size adds copier env/closure overhead beyond the raw value, and a list-tail argument may not be body-allocated at all (B ~ 0). At B = 0 the copy self-overwrites at zero skew — each write lands on its own source byte with an identical value, accidentally benign, which is why optimized builds masked it; the test runner compiles unoptimized IR, where one dead 24-byte MakeClosure in the loop body skewed the overlap and corrupted the clone (readme_showcase priced 41.00 instead of 12.50). Fix: DeepAdt Phase A clones twice (a clone of the clone — the second starts at least one full clone-size above W), making Phase B's destination end W+S provably below its source start W+B+S for any B >= 0 and any number of DeepAdt args; this also closes the same latent hazard for the already-shipped ADT/tuple DeepAdt copy-outs. Verified on all three targets and on both the optimized and unoptimized pipelines. Regression: tests/tco_list_of_adt_accumulator.ash; tests/readme_showcase.ash guards the capability+async shape. Amended (same branch): the whole-list clone is licensed per ARGUMENT, not per type. Cloning a list at every back-edge costs O(length) per iteration, affordable only when the body already paid O(length) REBUILDING the list that iteration (n-body's advance(dt)(bodies) call result — a callee's list result is copied out of its arena scope on return, so it is self-contained; likewise list literals and cons spines ending in one of those, per IsArenaSelfContainedListRebuildExpr). A threaded/consumed shape — a bare var, a pattern-derived tail, a cons onto the accumulator — can share unbounded structure with the previous iteration, and the per-back-edge clone multiplies the loop's cost by the list length: 1brc's merge phase (a List(tuple) walked by pattern tails) regressed ~400x in time and ~27x in memory (0.25 s / 2.1 GB -> 85 s / 54 GB on a 12 MB input, OOM-killed on the real file) before the gate. Non-fresh list args now downgrade to CopyOutKind.None at the back-edge (the no-reset behavior this entry's own fix above started from). |
| BigInt division: Knuth Algorithm D in base 2^32 | bignum_divmod was bit-by-bit binary long division — one full compare/subtract pass over the divisor per dividend bit — making pidigits O(N^3) time (its memory was already constant via the growing-accumulator watermark fix above). Rewritten as Algorithm D in base 2^32, the Hacker's Delight divmnu64 formulation: one quotient digit per outer iteration (normalize so the top divisor digit has its high bit set; estimate qhat from the top two dividend digits with a native 64/32 divide; correct it at most twice with the short-circuited overshoot check; multiply-subtract with a signed borrow; rare add-back when qhat was still one too large). Digits are the 32-bit halves of the 64-bit limbs, so every intermediate fits native i64 arithmetic — deliberately NOT base 2^64, whose qhat estimation needs 128/64 division and LLVM lowers udiv i128 to a __udivti3 libcall that a freestanding zero-runtime binary does not have. Single-digit divisors take a short-division path (one 64/32 divide per digit). The helper gains a caller-allocated scratch buffer (normalized divisor + working dividend, la+lb+4 words). Measured: pidigits N=1000 3.46 s -> 0.027 s (~128x), N=500 0.41 s -> 0.007 s, N=2000 0.11 s — output byte-identical. Edge coverage in tests/bigint_divmod_algorithm_d.ash: the canonical Hacker's Delight add-back trigger, the qhat correction loop, odd digit counts (top limb < 2^32 on either side), exact division, equal magnitudes, the short path, and truncated-toward-zero signs — expected values computed independently, remainder recovered as a - a/b*b so the mul/sub round-trip is checked too; verified on all three targets. Schoolbook mul is now the next asymptotic ceiling (Karatsuba deferred — no benchmark currently hits it). |
| Loop-invariant pass-through args + deferred TCO reset decisions | Two independent holes let growing-accumulator loops leak quadratically despite the fixed watermark above. (a) A loop-invariant heap argument disqualified the fixed mark: fasta's randomFasta threads its table CLOSURE unchanged through the loop; TFun was not in the fixed-watermark whitelist, so the loop fell back to the ADVANCING mark and stranded every iteration's copy of the growing output string — 6.8 GB at N=20000, 27 GB at N=40000. A pass-through arg (the param's own unchanged Var at every tail self-call, per the existing LoopInvariantParams analysis, which the plain-reset path already honored but the copy-out path ignored) holds the pre-loop value — below even the fixed loop-entry watermark — so it needs no copy-out and is now exempt from both the copyability scan and the fixed-mark qualification. Also unlocks loops threading an invariant LIST (previously allCopyable=false, no reset at all). fasta: constant 3.8 MB at every N (output identical). (b) A late-typed accumulator silently lost its reset entirely: the back-edge copy-out decision dispatches on argument types, but an accumulator constrained only by a deferred + (or by the caller) is still an unresolved inference variable when the back-edge lowers — e.g. whenever the stable [] -> acc match leaf lowers before the cons arm — and GetTcoCopyOutKind(TVar) = None declined the whole block: 1.76 GB for a 60k-iteration string fold, silently. The back-edge now emits an IrInst.TcoResetPending placeholder (no temps; never reaches the backend) with the AST/scope-dependent facts captured eagerly (pass-through, single-fresh-cons, stable-accumulator — the scope is gone by resolution time) and live TypeRefs; ResolveDeferredTcoResets, running after the deferred-operator resolutions at the end of lowering, re-runs the decision on the pruned types and splices the real block in place (swapping _inst and the temp/local counters per target function, the established synthesis pattern). The block emission itself was refactored into EmitTcoBackEdgeArenaBlock, shared by the inline (types-known) and deferred paths. 0.25 MB constant. Also re-measured the historical "growing cons-list O(N^2)" shapes: single- and multi-cons string builders and reverse-complement are all LINEAR today (~23–96 B/elem); what remains is the fat list-of-small-Str constant (in-place-reuse milestone) and copy-per-iteration O(N^2) TIME. Regressions: tests/tco_loop_invariant_args.ash, tests/tco_late_typed_accumulator.ash (the test runner's unoptimized pipeline is exactly where a wrong splice would miscompile). |
| Amortized fixed-watermark compaction | The fixed-watermark path copied the WHOLE accumulator at every back-edge — O(live) copy work per iteration, so a growing accumulator costs O(N^2) time in copies alone, and the List(ADT) accumulator reclamation loop above paid three deep clones per iteration for a constant-size value. The back-edge now skips the entire copy-out + reset while the arena has grown less than 2x the live size recorded at the last compaction (+4 KB slack): skipped iterations just keep allocating above W (exactly the no-reset behavior every non-qualifying loop already has — trivially sound), and each compaction reclaims at least as much garbage as it copies, so total copy work is linear in bytes allocated (the doubling amortization) while resident memory stays bounded by ~3x live. The live size is measured exactly and for free at the only moment that is possible: right after a compaction, [W, cursor) holds precisely the down-copies, so M = cursor - W — computing it per-iteration would require walking deep structures, which is the very O(N^2) being eliminated. The slack is a thrash guard, not a correctness knob: with M ~ 0 (empty/tiny accumulators) a bare 2M threshold would compact every iteration; 4 KB lets tiny-live loops batch hundreds of iterations of garbage per compaction. The trigger is a handful of i64 instructions (cursor read via SaveArenaState, subtract, shift, compare, branch) emitted only on the fixed-watermark two-pass path — the advancing-mark path is NOT amortized (its single-cell list copies must track the moving mark every iteration), and the all-copy-type plain reset needs no amortization (it copies nothing). Measured: the List(Body) 3M-iteration loop 0.289 s -> 0.054 s (5.4x) at an unchanged 0.25 MB; fasta ~1.5x faster at 1 MB constant (its remaining O(N^2) time is the immutable out + ch concat itself — each concat copies the whole string; that needs in-place unique-string growth, i.e. the ownership milestone). Verified on all three targets; full suites green. |
| Affine in-place string growth | The first concrete affine-ownership analysis beyond ADT reuse: immutable acc + x copies the whole accumulator per iteration by definition, so every growing string fold was O(N^2) TIME no matter what the arena did. Uniqueness is proven by two facts composed: (a) the affine analysis (CollectAffineAccumulators) — along every loop-continuing path the accumulator param is consumed at most once, and only as the leftmost leaf of the + chain producing its own tail-call argument (exit-path uses are unrestricted: nothing extends after the loop ends); (b) the watermark boundary — a value at/above the fixed loop-entry watermark W is loop-created, so the caller cannot alias it (this replaces the hard global half of the uniqueness proof; the caller-passed seed simply sits below W and falls back). Growth is reservation-based: each affine param gets a reservation slot pair (start/end locals, zeroed at loop entry). An armed append lowers to ConcatStrTip, whose emitter extends in place iff the left operand IS the reservation start and the appended bytes fit within the reserved end — memcpy onto the accumulator's end, grow the length header, cursor untouched — so the fast path is immune to interleaved per-iteration allocations (uncons views, scratch values) that land between the accumulator and the arena tip. When the check fails, the fallback allocates the concatenation with 2x headroom, copies once, and records the new reservation bounds — classic doubling, amortized O(1) per appended byte. Three interplay rules with the amortized fixed-watermark compaction above keep it sound and linear: (1) reservation spans are netted out of the growth measurement in the back-edge trigger — else every capacity doubling reads as arena growth and re-triggers a compaction that reclaims the fresh reservation (threshold resonance: compact, zero, re-reserve, compact); (2) the compaction zeroes the reservation slots it reclaims; (3) the compaction's Phase-B down-copy of an affine accumulator is itself a reserving ConcatStrTip (empty right operand against the just-zeroed slots) — without this, an accumulator larger than the watermark chunk's remainder re-reserves in ANOTHER chunk on the first post-compaction append, and the cross-chunk guard then forces a full copy EVERY back-edge (a measured cliff: fasta N=320000 took 34 s). Chunk mechanics: oversized chunks get 2x headroom (virtual-only cost — pages fault lazily), and on a chunk crossing the compaction rebases W via the chunk footer (usable end -> own base) to the new chunk's allocation start, preserving the B >= S two-pass disjointness. Also fixed en route: the amortized compaction's cursor - W arithmetic was garbage across chunks (distinct mmaps) — the trigger now forces a compaction on chunk crossing and the live-size recording is chunk-guarded. The deferred-+ path participates via AddInt.AffineResvStartSlot/AffineResvEndSlot (a late-typed accumulator's armed adds patch to ConcatStrTip in ResolveDeferredAdds). Measured: a 3M-iteration acc + "xy" fold (6 MB result, crossing chunks): >120 s/OOM -> 0.003 s; a 960k-iteration closure-call append fold: >120 s -> 0.002 s; fasta N=80000: 67 s -> 0.013 s, N=320000 0.050 s, N=1280000 0.53 s at 41 MB RSS — all LINEAR, both program halves on the fast path. Regression: tests/tco_affine_string_append.ash (in-place growth, closure-call operands, chains, chunk crossing, on the unoptimized pipeline). |
| Large-list copy-out stack overflow fixed | The scope-exit list copier (CopyOutList / inner-list copy-out) cached every head value in a dynamic stack alloca of 8 bytes per cell — a list past ~1M cells burned 8 MB+ of stack in one shot, and entry-frame allocas are never popped, so consecutive top-level list bindings compounded: two 1M-list lets (e.g. let xs = build(...) then let ys = reverse(xs)) overflowed the default 8 MB stack and segfaulted. Surfaced by re-running the mandelbrot benchmark (the packed-bitmap list is N^2/8 cells: N=2500 crashed; N=2000 survived at 8.0 MB by luck). Head caches larger than 32 KB now spill to a dedicated OS allocation (mmap/VirtualAlloc) released as soon as the destination list is built; small lists keep the stack path. mandelbrot N=16000 (32M-cell list) and multi-million-element List.reverse at top level now run on all three targets. Regression: tests/list_copyout_large.ash (1.5M-element build + reverse, two copies in one frame). |
| Diagnostic source mapping — combined-source spans render at the user's coordinates | Compilation runs on the stitched combined source (imported source modules + reshaped entry), so diagnostic spans are offsets into it — but the CLI rendered them against the original file text, producing positions past EOF (line 71 in a 66-line file, columns in the thousands pointing into the stitched single-line prefix) whenever the entry sat behind a stitched module, and off-by-the-import-header positions even for simple files. ProjectSupport.MapDiagnosticsToOriginal now maps spans back before rendering, using the property that makes this a contained fix rather than full source-map infrastructure: the entry region of the combined source is line/column-preserving with respect to the user's file (imports blanked keeping newlines, hoisted declarations blanked via BlankSpans, alias preludes overwriting blank import lines) — entry spans map by line/column arithmetic. Hoisted entry type/capability/provide declarations map exactly via a fragment table recorded as TryShapeFlatModule extracts them (CombinedCompilationLayout.EntryTypeDeclFragments); spans inside a stitched (reconstructed) non-entry module region render header-only, attributed to the owning file via ModuleOffsets. Measured: x + "oops" behind an Ashes.List import went from 9:2568 (blank caret past EOF) to the exact 6:9 with the right line text and underline; multi-error files locate every error. Unit tests cover the three mapping paths (ProjectSupportTests.MapDiagnosticsToOriginal_*). |
| Formatter fidelity — standalone comments preserved, trailing whitespace eliminated | The canonical formatter is AST-based and the AST carries no trivia, so CLI fmt -w silently deleted every // comment outside the leading header block; it also left trailing whitespace after =/->/in/else wherever the tree writers appended structural padding before breaking the line. Comments: the anchor-based reinsertion the LSP's format-document path already had was formatter-domain logic living in a consumer — moved to Ashes.Formatter.CommentReinserter and wired into CLI fmt, so both paths behave identically (each standalone comment line is re-anchored to the surrounding significant lines by a whitespace-insensitive token signature; a comment whose anchor disappears falls back to the previous anchor, then the top of the file — never dropped; idempotent; a comment whose anchor line the formatter collapsed into a longer line, a multi-line definition joined onto one, is matched against that line's head or tail tokens instead of falling back). Whitespace: Formatter.FinishOutput trims every line (safe — string literals are emitted single-line with escaped \n), landed with the coordinated ~400-file repo-wide reformat it was deferred for (verified whitespace-only via git diff --ignore-space-at-eol and idempotent). Gotcha recorded: fmt -w itself does not honor // fmt-skip: (only scripts/verify.sh's check loop does) — bulk fmt -w runs must exclude those fixtures. |
| fannkuch-redux constant memory | RC-header tracing identified two complementary ownership errors: a pattern owner was retained before a call even when the callee declined RC ownership and copied the argument, and iteration-local RC children borrowed by an arena aggregate were released before successor normalization. Pattern owners now use the callee ownership flag for conditional retains; purely local arena aggregates borrow pattern children, while owning or tail-result aggregates retain them until normalization; and TCO iteration drops are emitted after all successor RC graphs are established but before arena reset. The isolated aggregate/call repro is flat through 100k iterations; the full challenge is constant at about 8.2 MB for N=8 through N=11 with unchanged results. |
| Same-trait evidence identity | Hidden evidence was previously selected by qualified trait name alone, so requires {Eq(a), Eq(b)} could alias both slots and either fail with a misleading type mismatch or use the wrong method binding. Dictionary ABI slots now retain canonical full-constraint identity; active method lookup, abstract call threading, recursive forwarding, and concrete dictionary construction match pruned type arguments as well as the trait. Regressions cover primitive operators, explicit methods, generic forwarding, recursion, and cross-module evidence at Eq(Int) plus Eq(Str). |
| Meet-over-paths constant propagation, including local-slot state | FoldConstants cleared all known-constant state at any label with more than one predecessor rather than computing the meet (a fact survives only if every incoming edge agrees). Fixed by accumulating a state snapshot per predecessor edge — explicit Jump/JumpIfFalse branches, plus one edge per SwitchTag case/default, plus fall-through — and, once every edge into a label has been observed, intersecting them; a label with an edge not yet observed at that point in the forward scan (a loop back-edge) still clears conservatively, matching the historical behavior for loop headers. The initial raw-temp-only version of this fix shipped correct (all its unit tests passed) but folded zero real if/match results: every such join in Ashes IR is lowered through a StoreLocal (one per producing arm) and a LoadLocal at the point of use, never through a raw temp reused directly across a label, so the meet had nothing to observe — caught only by compiling the task's own worked example and inspecting --emit-ir final, not by its passing tests. Extended in the same change to also track local-slot constant state (a slot holds at most one of Int/Float/Bool at a time; a store of an unknown or non-scalar value kills stale knowledge for that slot), which is what makes the meet observable in practice: SwitchTag case/default labels also inherit pre-switch state as a free consequence of the same mechanism. Measured, using a temporary pre-change baseline build: the worked example (let tag = if n < 0 then 0 else 0 in tag) collapsed from 12 optimized instructions to 2 at -O0; a 200M-iteration hot-loop benchmark exercising the pattern ran 0.598 s -> 0.444 s at -O0 (~26% faster), and 0.005 s -> 0.005 s at -O2 (identical) — LLVM's own SCCP/mem2reg already fully subsumes this specific case at -O1+, matching this optimization's predicted LLVM-boundary classification (real value at -O0/debug builds and --emit-ir fidelity). Full suites green (C# 2326/2326, LSP 70/70, e2e test tests --pipeline both 639/0/54-skipped). |
| Constant-condition branch folding | FoldConstants tracked known-constant booleans (the meet-over-paths constant propagation above) but never consulted them to eliminate a JumpIfFalse whose condition is statically known. Fixed: HandleJumpIfFalse rewrites a known-false condition's branch to an unconditional Jump, or drops a known-true condition's branch entirely (falling through to the surviving arm) — both cases fold away the whole boolean-comparison scaffolding along with it, since that meet-over-paths pass's local-slot tracking already resolves the condition before this pass sees it. Two gaps surfaced during implementation, both by measuring against real compiled output rather than trusting passing unit tests: (1) the "known false" rewrite must still propagate its edge's state snapshot to the target label (the edge is preserved, just made unconditional) — omitting this broke five pre-existing tests relying on state flowing through what is now a folded branch; (2) ElideUnreachableCode unconditionally treats every Label as re-establishing reachability, so a known-true fold's now-orphaned false-arm survived physically in the output (dead but not removed) — fixed by recomputing predecessor edges fresh over the post-fold instruction list before deciding whether a label is still reachable. Measured: the worked example's shape went from 15 to 8 optimized instructions (~47%) in an isolated probe. Runtime, against a temporary pre-task baseline: no difference at -O2 (LLVM already eliminates it); at -O0, a 200M-iteration hot-loop benchmark showed a small, consistent, not fully root-caused ~3% regression (0.510s -> 0.526s) despite fewer instructions — most likely -O0's naive stack-layout sensitivity to slot renumbering, not an unsoundness (full suites, including the RC-sensitive e2e corpus, are green). Unlike the meet-over-paths pass above, this task's real measured benefit is IR/code-size quality, not hot-loop throughput: a compile-time-constant, always-same-direction branch predicts perfectly on real hardware, so removing it doesn't move steady-state speed. |
| Re-forward algebraic-identity copies | ReduceIdentitiesAndStrength (pass 6 of the per-function sequence) rewrites an algebraic identity (x+0, 0+x, x-0 -> x) into a Borrow copy rather than retargeting downstream uses directly, but ElideTrivialOwnershipCopies (the pass that erases an unneeded copy) runs earlier (pass 1), so within one Optimize() invocation that new copy was never revisited. Fixed with the minimal, low-risk approach: a second call to ElideTrivialOwnershipCopies immediately after ReduceIdentitiesAndStrength — safe because that pass is a pure function of its input (fresh use-def facts every call), needing no special interaction handling. Unlike the two entries above, this one needed no follow-up correction: it worked as designed, no pre-existing tests broke. Measured with a real compiled probe (n + 0) against a temporary pre-task baseline: 3 optimized instructions collapsed to 2 (the Borrow — a real load+store pair at codegen — fully erased). Runtime, a 200M-iteration hot-loop benchmark with a per-iteration identity: -O0 0.491s -> 0.424s (~14% faster); -O2 identical (LLVM already folds the loop away regardless). Full suites green (C# 2330/2330, LSP 70/70, e2e 639/0/54-skipped). |
Reusable CFG infrastructure — IrControlFlowGraph | The only real block/dominator builder in the compiler was a private nested Block class inside PerceusLifetimePlacement.cs; every IrOptimizer.cs pass needing predecessor/successor reasoning approximated it with a weaker per-pass heuristic (e.g. the constant-propagation and identity-copy passes above used a CountBranchRefsToLabels-based predecessor counting). Extracted the block-building and dominator algorithms into a new shared IrControlFlowGraph.cs: IrCfgBlock (Start/End/Successors/Predecessors), Build, IndexLabels, ComputeDominators, and a new addition, ComputePostDominators (reverse-CFG technique with a virtual exit node connected from every no-successor block) — all generic over an IHasCfgEdges interface so PerceusLifetimePlacement's own liveness-augmented block type can share the same algorithms without duplicating them. PerceusLifetimePlacement.Block now wraps an IrCfgBlock (sharing its edge-list references directly) while keeping its liveness-specific mutable state local to itself, since Perceus RC liveness has different semantics from general instruction liveness. ElideUnreachableCode was ported onto the shared CFG's predecessor count in place of its ad hoc fresh-recompute, provably equivalent for that specific gated use. Measured, since this task's completion bar is zero behavior change rather than a performance win: full suites unaffected (C# 2338/2338, LSP 70/70, e2e 639/0/54-skipped), and beyond trusting the test suite, --emit-ir final output and the compiled binary for a representative program are byte-for-byte identical before and after against a temporary pre-task baseline. 7 new unit tests directly on IrControlFlowGraph. |
Shared whole-program fixpoint skeleton — WholeProgramFixpoint (narrowed scope) | Several independent whole-program analyses each hand-rolled the same bool changed = ...; while (changed) { changed = false; ...; } control structure: ComputeNonAllocatingFunctions (IrOptimizer.cs), ComputeEvaluableFunctions (IrCompileTimeEval.cs), PropagateLiveHandlerEffects (Lowering.HandlerEffects.cs), PropagateCoroutineEffects (Lowering.CoroutineEffects.cs). The original design proposed a fuller unification (one generic FunctionSummary record with pluggable fact slots, computed by an SCC-ordered driver FunctionOwnershipSummary, ComputeNonAllocatingFunctions, and HandlerEffects would all share). Investigation found this doesn't fit cleanly: HandlerEffects runs during AST-to-IR lowering over AST-level FuncKey nodes with its own call graph, while ComputeNonAllocatingFunctions/ComputeEvaluableFunctions run post-lowering over IR-level string labels with no explicit call graph at all (every pass re-scans every function); neither is actually SCC-ordered (both just re-iterate the whole node set to a naive fixpoint); and the propagation directions and per-iteration shapes differ (a growing live-set with an "entry" special case vs. a shrinking candidate set with none). Forcing these into one generic node/graph abstraction across a phase boundary that doesn't naturally invite it was judged real risk (this is exactly the class of interprocedural-analysis code this project's history shows produces multi-session debugging efforts) for a benefit neither of the task's two concrete completion-criteria consumers needs yet. Shipped instead: extracted only the piece all four provably share — the repeat-until-no-change control structure — as WholeProgramFixpoint.RunToFixpoint(Func<bool> iteration), and migrated all four fixpoints onto it (pure mechanical substitutions; the loop bodies are unchanged). A true SCC-ordered/pluggable-fact-slot framework and DirectCalleeAnalysis's generalization remain future work if a later task's own needs require them. Measured, since this task's completion bar is zero behavior change: full suites unaffected (C# 2342/2342, LSP 70/70, e2e 639/0/54-skipped), and --emit-ir final output plus the compiled binary for two representative programs (one async/coroutine/handler-heavy, one recursive/branching) are byte-for-byte identical before and after against a temporary pre-task baseline. 4 new unit tests directly on WholeProgramFixpoint. |
| Local CSE for pure calls and field loads | No hash-consing existed for redundant GetAdtField reads or redundant calls to a provably pure function within a straight-line block. New pass EliminateLocalRedundantComputation, run per function after FoldConstants/ReduceIdentitiesAndStrength and before ElideDeadCode, reusing IrCompileTimeEval's whole-program purity oracle (ComputeEvaluableFunctions, widened from private to internal) as the CallKnown eligibility check — no second purity analysis built. Two real gaps surfaced only by testing against actual compiled output, not the unit tests (which passed regardless): (1) a literal "keyed by raw operand temps" design folds nothing in real code — let x = p.x in let y = p.x produces two different LoadLocal temps for the same slot, the same lesson the meet-over-paths constant propagation entry above already learned; fixed by canonicalizing operands through a LoadLocal/StoreLocal/Borrow/RcDup alias map, plus seeding a synthetic identity for a function's own env/arg slots (0/1), since the backend's entry prologue populates them via a native store the IR-level optimizer never sees as an explicit StoreLocal (LlvmCodegen.cs:1623-1627). (2) Even after (1), the same example still didn't merge: every let binding brackets its scope in SaveArenaState/RestoreArenaState/ReclaimArenaChunks, and the pass's conservative "invalidate on anything not proven safe" cache policy treated these as potentially-aliasing — they don't write through any pointer, they only move an allocator cursor, so treating them as safe was necessary for the pass to fire on almost any real Ashes program. Honestly reported gap, not fixed by this task: a perimeter(r) + perimeter(r)-style example does not benefit, because it compiles to CallClosure, not CallKnown — DevirtualizeKnownClosureCalls only recognizes a closure temp defined directly by MakeClosure/MakeClosureStack with no intervening local-slot round-trip, a condition essentially no let-bound function call satisfies; CallKnown CSE is implemented and proven structurally correct (5 raw-IR unit tests incl. two negative cases) but is reachable only in the narrow case devirtualization already handles today — a separate, pre-existing gap this task deliberately did not expand scope to fix. Measured: --emit-ir final on a redundant-field-read example goes from two GetAdtField to one, verified against a temporary pre-task baseline. A 20M-iteration hot-loop built around the same pattern (four redundant field reads/iteration reduced to two) ran 105.6 ms -> 99.7 ms at -O0 (~6% faster, hyperfine 15+ runs); identical at -O2 within noise (LLVM already subsumes it there). Full suites green (C# 2348/2348, LSP 70/70, e2e test --pipeline both 641/0/54-skipped). |
| Store-to-load / projection forwarding | Co-located with the local CSE pass above (same EliminateLocalRedundantComputation/FieldCache — co-locating turned out to be natural, no separate pass needed): a SetAdtField through a pointer proven fresh in the same block (an AllocAdt/AllocAdtStack target, tracked in a new FreshPointers set — nothing that existed before such an instruction could hold a reference to memory that didn't exist yet) now populates FieldCache directly from the write, so an immediately-following GetAdtField of the same field forwards the stored value instead of round-tripping through memory. A write through any other pointer keeps the existing fully-conservative invalidate-everything fallback. A real, serious bug was found only by compiling and running actual .ash source, not by this task's own unit tests: the first implementation cached the write's alias-canonicalized identity, which can resolve to a synthetic, negative sentinel (the local CSE pass's own EntrySlotIdentity) when the value traces back to a function's own argument with no real defining instruction visible to the pass — exactly the case for let p = Point(x = n, ...) in ... p.x with n a parameter. A sentinel is only safe as a cache key; emitting it as a forwarded value produced Borrow(target, -2), an out-of-range temp reference that crashed at codegen (IndexOutOfRangeException, verified by reverting the fix and reproducing the crash). Fixed by caching the write's raw, unresolved source temp instead — always real and live, exactly like the existing read-side caches already do. Three of that pass's own negative tests needed updating, not as regressions but because this task correctly strengthens what gets eliminated (both reads of a written-then-rewritten field now forward from their respective writes rather than surviving as reads); their assertions moved from instruction counts to execution-correctness checks where the specific mechanism could legitimately vary. Measured: a construct-then-destructure shape (with a real function parameter, not a literal) goes from 2 GetAdtField to 0 in --emit-ir final, verified against a temporary pre-task baseline; a literal swap example does not benefit as written, since the allocation and the destructuring are in different functions at the call site (this pass is intra-procedural) — the far more common within-one-function shape works. A 20M-iteration hot-loop: 128.9 ms -> 119.3 ms at -O0 (~7% faster, hyperfine 15+ runs); identical at -O2 within noise. Full suites green (C# 2352/2352, LSP 70/70, e2e test --pipeline both 642/0/54-skipped) — especially meaningful given the bug found would have been a hard crash, not a silent miscompile. |
| CFG simplification suite — jump threading, redundant-jump elision, unreferenced-label removal | New pass SimplifyControlFlow in IrOptimizer.cs, positioned after ElideUnreachableCode: redirects a branch through an empty-label chain (a label immediately followed only by an unconditional Jump) straight to its final destination, drops labels with zero remaining references, and elides a Jump immediately followed by its own target label. Every rewrite is locally safe without reachability analysis. A real gap surfaced only by testing against actual compiled output, not the unit tests written first: a single "simplify, then sweep unreachable code" pass does not reach a full fixed point — redirecting several distinct branches to the same final label (the exact shape of a real match compiled to a cascading match_arm_cleanup_N -> match_next_M chain, one hop per non-matching arm) stacks multiple unconditional Jumps back-to-back once their separating labels are dropped as unreferenced; removing the newly-unreachable ones can then expose a further redundant-fallthrough opportunity only a subsequent pass sees. Caught by a hand-built 3-hop chain unit test and confirmed at scale on a real 4-constructor match (one redundant Jump/Label pair survived per arm after a single pass). Fixed by iterating SimplifyControlFlow and ElideUnreachableCode together to a genuine fixed point (safe and bounded: both are pure functions of their input, and the instruction count strictly decreases each iteration that changes anything). Two pre-existing tests needed updating — not regressions, but earlier passes' own output correctly collapsing further once genuinely redundant (a constant-condition branch folding test's surviving-arm Jump was itself a redundant fallthrough once the dead arm was stripped; a SinkRuntimeRcDupsIntoDiamonds test used a literal branch condition purely for a deterministic shape, and once its resulting always-taken branch's Jump/Label pair collapsed, its label-name-based lookup broke even though the compiled program stayed correct — fixed by switching to the same non-foldable RcIsUnique condition its own sibling test already used, for exactly the reason that sibling's comment already explains). Measured: a real 4-constructor match cascade shows zero occurrences of either target pattern in --emit-ir final at -O0 (scripted scan), versus 4 empty-hop labels and 4 redundant fallthrough jumps in the pre-task compiler on the same program (208 -> 200 instructions). Runtime, against a temporary pre-task baseline on a 5M-iteration hot-loop built around the same match-cascade shape: no meaningful difference at either -O0 or -O2 (both within noise) — a code-size/IR-quality win, not a hot-loop speed win, matching this task's own prediction and the constant-condition branch folding entry's own precedent above (a well-predicted branch costs little on real hardware regardless of whether it's physically present). Full suites green (C# 2357/2357, LSP 70/70, e2e test --pipeline both 642/0/54-skipped). |
Guaranteed stack-bounded general tail calls — musttail upgrade (part (b) only) | A non-loop tail call between distinct functions (e.g. a heterogeneous mutually-tail-recursive group that fails TryLowerMutualRecursionTco's identical-parameter-type eligibility check) previously got only LLVM's advisory Tail marker — a hint for sibling-call optimization, not a guarantee. DetermineTailCallKind now emits MustTail instead for a call already proven CanEmitNativeTailCall-eligible (exact CallKnown-immediately-followed-by-matching-Return adjacency), gated by a new whole-function scan, FunctionAllocatesNativeStackMemory, for any AllocStack instruction — stricter than a simpler EnvironmentIsStackAllocated check alone would be. Reading the lowering code confirmed AllocStack-backed values can only ever be used as an immediate match scrutinee or a direct callee, so the only hazard EnvironmentIsStackAllocated alone doesn't cover is a capability/effect-handler frame (Lowering.Capabilities.cs) whose pointer is installed into a dynamically-scoped global for the whole handle body's extent — a span that can include a later tail call in the same function; musttail would let LLVM reuse the caller's frame immediately, leaving that global dangling. Emitting the musttail call also required bypassing Ashes' universal StoreTemp/LoadTemp round-trip for the fused call+return pair specifically, since LLVM's verifier requires a musttail call to syntactically precede its ret with nothing in between — TryEmitMustTailCallAndReturn emits the call and the ret directly from the raw SSA value, then the caller loop skips the now-redundant Return. Validated against real compiled output, not just unit assertions: --emit-ir final on a mutually-tail-recursive pair whose entire body is one unconditional tail call confirms CanEmitNativeTailCall's narrow adjacency requirement does fire on realistic source. The crash-vs-fix distinction itself was demonstrated with a deliberately minimal raw-IR fixture rather than that source example: at the CLI's default -O2, LLVM's own TailCallElim IR pass already promotes the advisory tail marker to a real sibling call, making pre-fix and post-fix output identical, matching the prediction that this is "primarily valuable for -O0/--debug builds." At -O0, a 10,000,000-deep raw-IR mutual ping/pong chain segfaults without the fix and completes correctly with it. The equivalent source-compiled chain surprisingly did not crash on the unfixed baseline even at 100,000,000 deep at -O0 — LLVM's sibling-call codegen already succeeds for this simple, uniform-ABI, single-basic-block shape from just the advisory marker in this particular case; the raw-IR fixture was deliberately engineered to hit a case where the heuristic does decline, since musttail's value is the hard guarantee against exactly that class of silent bail-out, not a claim that every eligible real program crashes without it. Two further tests close the newly-discovered capability-handler-frame hazard (a function that itself allocates stack memory correctly falls back to advisory tail; a capability-handler frame installed via raw IR survives across a non-musttail call) — an honest note: neither empirically demonstrates corruption with the gate removed on this specific reproduction, so the gate is kept as a defensive measure matching LLVM's documented contract rather than because corruption was directly observed. Full suites green (C# 2360/2360, LSP 70/70, e2e test tests 643/0/54-skipped). Part (a) (widening mutual-TCO loop-merge eligibility to heterogeneous parameter shapes) was not attempted. |
| Closure environment scalarization for a single scalar capture (N=1 only) | Every closure packed its captures into a struct pointer even after DevirtualizeKnownClosureCalls proved a call site's target statically, so a closure capturing exactly one value still paid for an allocation, a store, and a pointer dereference to move that one value across a call. New whole-program pass ScalarizeSingleCaptureStackClosures (IrOptimizer.cs), sequenced after the per-function pipeline and before arena-bracket stripping: when a stack-allocated closure's environment holds exactly one 8-byte value and its only use is already a devirtualized CallKnown, the environment allocation is skipped entirely and the captured value is passed directly as the call's existing "env" argument — no new calling convention needed, since the existing 3-word CallKnown ABI already has that slot free for a single scalar. Scope is narrowed to exactly one capture (N=1), not a general N-capture form: every Ashes-callable function shares one fixed LLVM call signature so CallClosure's indirect dispatch stays uniform regardless of capture count, and an N-ary direct-call-only variant would need a new IR call-instruction shape and calling convention — the same class of change the musttail upgrade entry above deferred as its own part (a). A new callee variant is generated per target label (memoized across call sites), never rewriting the original in place, since the same label can still be used elsewhere in a way that needs the pointer-based form. A real gap was found only by testing against actual compiled .ash output, not this task's own unit tests (which all passed regardless, since they were built around the wrong shape): the pass was originally built to recognize a hand-constructed LoadLocal(_, 0) + LoadMemOffset dereference pair, but --emit-ir final on a real closure showed this shape never occurs in actual (non-coroutine) lowered code — real closures read a capture via the dedicated LoadEnv(Target, Index) instruction, which dereferences local slot 0 implicitly inside its own codegen. Rewritten to match LoadEnv directly (simpler than the original design, and a capture referenced more than once, e.g. n + n, is now handled for free rather than declined); a coroutine callee is excluded (its state-machine transform rewrites LoadEnv into a LoadMemOffset against its own frame/state-struct temp instead — a materially different, riskier shape) and a callee reading the env slot as a raw value outside of LoadEnv is conservatively declined. Measured: a real immediately-invoked single-capture closure goes from AllocStack + StoreMemOffset + an arena bracket + CallKnown(EnvironmentIsStackAllocated: true) to a bare allocation-free CallKnown in --emit-ir final, with the arena bracket also disappearing as a free consequence of the pre-existing StripRedundantArenaBrackets pass now seeing a non-allocating call. A 20,000,000-iteration hot loop building and calling a single-capture closure per iteration, against a temporary pre-task baseline (hyperfine, 10+ runs): 104.1 ms -> 69.1 ms at -O0 (~1.51x faster), and — unlike every prior task in this arc — 9.8 ms -> 3.7 ms at -O2 (~2.65x faster): LLVM's own SROA/mem2reg already eliminates the trivial stack allocation itself at -O1+, but not the genuine runtime arena-cursor bookkeeping around it, which is what this task's own change removes. All four baseline/fixed × -O0/-O2 binaries produce identical, correct output. Full suites green (C# 2366/2366, LSP 70/70, e2e test tests --pipeline both 643/0/54-skipped). |
| Recursive decision-tree match compilation, one grouping level, plus sound dead-arm elimination | TryPlanTagSwitch only fired for a flat, guard-free, single-ADT match with more than four arms and every sub-pattern trivial — a single nested constructor sub-pattern anywhere, or two arms sharing a tag, disqualified the entire match from tag-switch dispatch, forcing a fully linear chain that redundantly re-tested every preceding arm's tag. New TryPlanTagGroupSwitch/LowerMatchArmsViaTagGroupSwitch (Lowering.Patterns.cs), tried between the existing fast path and the linear fallback, never replacing either: cases are grouped by outer constructor tag in first-seen order (unlike TryPlanTagSwitch, more than one case may share a tag), sharing one GetAdtTag/SwitchTag test across every case with that tag; a group with exactly one fully-trivial case reuses TryPlanTagSwitch's own no-redundant-retest per-arm emission (refactored to take a constructor symbol directly rather than a plan array, so this second call site could reuse it unmodified); a group needing more (more than one case, or a single non-trivial case) falls back to linear per-case testing scoped to that group only, reusing LowerMatchArmsLinear's own per-arm functions completely unmodified. The central risk-reduction choice: no case is ever reordered or duplicated across leaves, so the reuse-token/ownership machinery's implicit one-arm-one-emission-site assumption is never disturbed; ReuseTokenTests.cs/ReuseDecisionTests.cs (25/25, 14/14) needed zero changes. Column reordering, multi-level column selection, and guard interaction within a group are explicitly out of scope for now, kept deliberately incremental. Also closes a dead-arm-elimination attempt reverted twice earlier for two confirmed soundness bugs: investigation found a fully recursive, per-field-position coverage engine (TryGetMissingPatternCore/TryGetMissingAdtPattern) already existed, wired only to the "Missing case" diagnostic — new TrimProvablyUnreachableTrailingCases reuses it (never a top-level-tag-only check, which the earlier attempt used and which is unsound here) to soundly drop a trailing run of cases already proven unreachable, called after the existing arm-reachability diagnostics run (so they still see and report on the untrimmed list exactly as before) and before any lowering happens for a dropped arm. The same unresolved-scrutinee-type timing issue that broke the earlier attempt (bug 2: gating on the type already being concretely resolved made the trim never fire for the common case of an ordinary function's own parameter, not just a recursive one) recurred exactly as predicted — fixed by having the trim perform the same unification arm-by-arm lowering would do moments later, before checking; Unify is idempotent, so this only moves already-necessary work earlier. Two e2e regression tests built from that earlier attempt's exact failure shapes (tests/match_dead_arm_elimination_nested_result_bool.ash for the tag-only-coverage bug, tests/match_dead_arm_elimination_recursive_param.ash for the type-timing bug) confirm both the trim fires and every reachable arm still produces correct output. A real interaction bug was caught by the existing C# suite: placing the trim before ValidateReachableMatchArms silently removed the exact arms that diagnostic exists to report as unreachable, breaking Match_arms_after_wildcard_report_unreachable_arm_error — fixed by reordering. Measured against a temporary pre-task baseline (hyperfine, 10+ runs): a repeated-tag example (`Node(Leaf,_,Leaf) |
| Prune dead closure captures at lowering time | A closure's capture set came straight from the lambda body's syntactic free variables and was never revisited: IsDeadInstruction removes dead constant loads, dead StoreLocals and dead MakeClosures, but never Alloc/AllocStack/StoreMemOffset, so a capture the body no longer reads (most commonly after inlining or specialization deleted the reads it was created for) paid for a real allocation and fill on every closure creation regardless. LowerLambdaCoreBuildEnvAllocation now records each capture's instruction range at the creation site (from right before LowerVar(captures[i]) through its StoreMemOffset fill) instead of only emitting it. Once the body is lowered and its IrFunction is registered, LowerLambdaCorePruneDeadCaptures scans it for every LoadEnv — including one reached through the trait-dictionary reference path, which turned out to emit the same instruction, so no second oracle was needed — to find which capture indices the body actually reads; a fully-used env returns unchanged, otherwise the dead ranges are deleted (last-to-first, so earlier recorded indices stay valid), the survivors' StoreMemOffset offsets and the body's LoadEnv indices are renumbered to a compact 0..k-1, and the Alloc/AllocStack's SizeBytes shrinks to match — after which MakeClosure's resource-capture and runtime-managed-dropper bookkeeping, which recompute every offset from the (now pruned) captures list's own enumeration order, need no further patching. A capture requiring a Borrow (an owned outer value) has its ActiveBorrows accounting decremented when its fill is deleted, so the outer scope's later drop/borrow-release placement doesn't assume a borrow with no corresponding instruction. Declines a self-referential lambda (its own Binding.Self reconstructs a closure over this exact env using a size recorded before pruning could run) and a mutual-recursion group (the env is shared and filled once at the group site, not per-member); a coroutine body never reaches this code path at all, since it's built through an entirely separate capture/env mechanism in Lowering.Builtins.cs that is never routed through LowerLambdaCore. Measured: the mutual_recursion self-hosting parity fixture's mutual-recursion dispatch closure shrank from a 2-capture, 16-byte environment to a 1-capture, 8-byte one (__recgroup_dispatch_2's Alloc/MakeClosure EnvSizeBytes 16 -> 8) — and, as a genuinely emergent side effect of nothing but a smaller, more accurate captures list, unlocked AttachRuntimeManagedClosureNormalizer (previously blocked because the other, now-pruned capture wasn't runtime-normalizable, and one non-normalizable capture disqualifies the whole closure), synthesizing a $env_normalize helper that hadn't existed before. A 200,000,000-iteration driver repeatedly entering that same mutual-recursion group (isEven/isOdd mutually tail-recursive, called fresh from a separate recursive driver loop each iteration) ran, against a temporary pre-task baseline: 1.02s -> 0.88s at the CLI's default -O2 (~14% faster, 3 runs each side, <15ms spread) — unlike most tasks in this arc, the -O2 win survives because it removes a genuine allocation LLVM's own passes have no way to invent; LLVM can only optimize what Ashes chose to lower, and a smaller env is a decision made before LLVM ever sees the program. Full suites green (C# 2371/2371, LSP 70/70, e2e test tests --pipeline both 645/0/54-skipped); the selfhost/parity/semantics/lowered-ir/mutual_recursion.ir fixture was regenerated (ASHES_UPDATE_PARITY_FIXTURES=1) to match the new, correctly-pruned lowered shape. |
| Fold left-nested string-concatenation chains into one N-ary allocation (stage 1 of the affine string-building work) | A left-nested chain of string-concatenation calls (((a ++ b) ++ c) ++ d) paid one allocation and one growing copy per link — n-1 allocations and O(n^2) total bytes copied for n parts, since each intermediate result gets copied again by every subsequent link. New ConcatStrN(Target, Parts, RuntimeManaged) instruction plus FoldConcatStrChains, run as the last step of IrOptimizer.Optimize (after every other pass, entry and every function) so no earlier pass ever needs to learn the new instruction shape — only the backend does. The peephole walks each chain's Left operand backward while it is single-use and itself concatenation-defined, then emits one ConcatStrN at the chain's outermost position; new EmitStringConcatN (LlvmCodegenMemory.cs) sums every part's length, allocates once, and copies each part directly into its final offset. A real, serious correctness bug was found only by running the compiled output of a realistic chain, not by this task's own hand-built unit tests, which initially passed against the wrong implementation: a single-use/def-count safety check alone is necessary but not sufficient — folding delays reading an earlier part's string until the new instruction's position at the very end of the chain, and if a later part's own computation (e.g. an inlined helper call, each with its own arena SaveArenaState/RestoreArenaState/ReclaimArenaChunks bracket) reclaims the bump-allocator cursor back past where the earlier part was allocated, the later part's own allocation can land at the exact same address the delayed read still needs — invisible to single-use analysis, since each temp really is used exactly once; the hazard is when it's read relative to a reclaim, not how many times. A 4-call chain of an inlined intToStr helper folded to one plausible-looking ConcatStrN that compiled and ran, printing "4 4 4 4" instead of "1 2 3 4" — every position showing the last part's value. Fixed by RangeContainsArenaOrControlFlow: scan every instruction from the innermost part's own definition through the fold point for an arena bracket, stack-pointer save/restore, or any branch/label instruction, and decline the whole chain if any appear (conservative on purpose — it does not attempt to prove a specific reclaim's range excludes a specific part's address, or that a specific part is RC-managed and therefore not actually at risk). Two regression tests lock this in, one of which (a compile-and-run correctness assertion on the exact intToStr-chain shape) is the one that would have caught the original bug — the IR-shape-only assertions alone still looked plausible against the buggy implementation. Consequence, honestly reported: this materially narrows real-world applicability — any chain part computed via a real function call typically carries its own arena bracket, so the fold now mainly fires for chains built from literals and other allocation-free intermediate values, not general "each part is an arbitrary expression" chains; extending coverage further would need real interval/liveness reasoning about specific reclaim ranges, not the "no new analysis" framing this task started with. Measured, against a temporary pre-task baseline: a representative in-scope case ("user " + "has " + "42 " + "items " + "today", 5 literal parts, inside a 20,000,000-iteration recursive driver) ran 0.90s -> 0.40s at -O0 (~2.25x faster) and 0.32s -> 0.02s at the CLI's default -O2 (~15-17x faster) — unlike most tasks in this arc, the -O2 win dominates rather than being subsumed by LLVM, since LLVM cannot invent away a real allocator call with observable side effects that the unfolded chain pays every iteration. Full suites green (C# 2377/2377, LSP 70/70, e2e test tests --pipeline both 645/0/54-skipped). Stage 2 (widening the existing affine-accumulator ConcatStrTip reservation path beyond its TCO-back-edge-only arming) was not attempted. |
| Devirtualize closure calls past a single definition (single-agreeing-label case only) | DevirtualizeKnownClosureCalls required a closure temp's single definition to be a MakeClosure, so a curried call's second and later applications (add(10)(32)) never devirtualized: add(10)'s result temp is defined by a CallKnown, not a MakeClosure. The design doc's own "Evidence" section pointed at RecordReturnedClosureLabel's bookkeeping as directly reusable — tracing the code found this is not actually true: that bookkeeping is a private, in-memory field of the Lowering class instance, never persisted onto IrFunction/IrProgram, and Lowering has already gone out of scope by the time IrOptimizer runs. New ComputeKnownReturnedClosureLabels instead recomputes the equivalent fact directly from the IR — a whole-program least fixpoint (reusing the existing WholeProgramFixpoint.RunToFixpoint helper ComputeNonAllocatingFunctions already uses, generalized from a shrinking candidate set to a growing known-label map) determining, per function, whether every Return is provably the same closure label, either directly from a MakeClosure or transitively through a CallKnown to another function already proven to return that label. Deliberately excludes MakeClosureStack as a "known label" source, reasoned through before writing any code, not found by a wrong answer: a stack closure's environment lives in its defining function's own frame, gone once that function returns, so treating one as a "known return value" would let a later caller dereference a dangling pointer after devirtualization — traced from EmitCallClosure's own {code, env, size, dropper} field layout before implementing, the same discipline that would have prevented this arc's OPT-017(b) arena-reclaim bug if applied there first. At the rewrite site, a new LoadMemOffset(envTemp, closureTemp, 8) extracts the environment (matching that same field layout) immediately before a direct CallKnown, at the exact position the original CallClosure occupied, so existing RC/ownership placement for that temp — computed earlier in the pipeline, unaware this pass would run — stays correct unmodified; each function iterates the rewrite to its own local fixpoint so a curry deeper than two arguments (verified on a 3-argument curry, all three applications becoming CallKnown) fully resolves in one pass. Scope narrowed from the design doc: only the single-agreeing-label case is implemented; a proposed 2-4-label lambda-set-specialization dispatch (a new multi-arm dispatch shape, not a rewrite within the existing CallClosure-to-CallKnown shape) was not attempted. Two hand-built raw-IR tests cover this (real .ash source does not reliably reach this pass's precondition through the test suite's minimal bootstrapping — a plain top-level let-bound closure is read via StoreLocal/LoadLocal, not a MakeClosure/CallKnown definition, a pre-existing gap in the original single-definition devirtualization this task did not set out to close): one confirms the add(10)(32) positive case; one confirms a disagreeing-origin negative case declines correctly, guarded by a condition read from the callee's own argument rather than a literal (a literal condition is foldable by an earlier pass in the same pipeline and would silently resolve the intended "disagreement" away before this pass ever saw it — found while writing the test). Measured: the doc's own worked example confirms both applications become CallKnown via --emit-ir final on real compiled source. A representative hot-loop case (add(k)(1) inside a 30,000,000-iteration TCO loop) confirmed the devirtualization firing correctly inside the loop body, but showed no measurable wall-clock difference at either -O0 or -O2, reported honestly rather than replaced with a more favorable benchmark: for a single-instruction callee body called through a target that never changes across iterations, the indirect-call overhead this task removes appears small relative to the loop's own TCO/arena-bracket mechanics, and modern indirect-branch prediction already handles a stable-target indirect call cheaply — this task's defensible value is structural (visibility to LLVM's inliner and to constant folding), which a program with a non-trivial curried-callee body would be expected to benefit from measurably, though that was not separately constructed and measured. Full suites green (C# 2381/2381, LSP 70/70, e2e test tests --pipeline both 645/0/54-skipped). |
| Release a runtime-RC successor passed by name to a tail self-call | challenges/fannkuch-redux was back at 2.4 GB peak RSS at N=10 (27 GB at N=11) on a build with every gate green. Traced at the IR level on a 25-line reduction (match advance(k)(st) with | Continue(next, r) -> loop(k - 1)(next)): the Continue scrutinee is a fresh runtime-RC value, so TrackRuntimeManagedMatchScrutineeOwner gives the extracted next its own independent runtime-managed owner (TrackIndependentlyOwnedMatchFields) and drops the wrapper shallowly, excluding that field — correct so far. The tail self-call's argument evaluation then retains next for the successor parameter (DuplicateRuntimeManagedOwnedValueForTransfer, whose contract is "retain the successor before the current lexical owner is released"), but LowerCallTcoMarkMovedArgs marked the same owner as moved — a rule written so a resource is not closed and a closure's dropper not run at the back-edge — which IsDropped then reads as "already released", silently excluding it from CollectTcoBackEdgeOwnedDrops. Net effect per iteration: one retain, no release; the next iteration's parameter drop finds the old state shared, takes the decrement-only path, and the whole permutation graph (state shell plus both lists) is never reclaimed. A gdb watchpoint on the state's count header confirmed the count going 1 -> 2 at the retain and never back. Pattern-bound owners (PerceusPatternOwner) were already excluded from the moved rule and get exactly this retain-then-release pair, so plain runtime-RC data now follows the same contract: LowerCallTcoMarkMovedArgs skips it, and the deferred back-edge drop (emitted after every successor is normalized and the predecessor released) balances the retain with a shared-path decrement. Resources, resource-bearing aggregates and closures keep the moved rule unchanged. Plateau regression LinuxBackendCoverageTests.Linux_backend_llvm_match_field_successor_tco_argument_memory_should_plateau (fails without the change: 12.4 -> 32.8 MB across 2k/10k/50k iterations) and tests/tco_match_field_successor_argument.ash. Measured: fannkuch-redux N=10 2,416 MB -> 8.2 MB (2.50 s), N=11 27 GB -> 8.2 MB (36.9 s), outputs 73196 / 38 and 556355 / 51 unchanged; binary-trees, n-body, spectral-norm, pidigits, mandelbrot and fasta unchanged in output and RSS. A second, independent shape still leaks and is not addressed here: a let-bound closure-call result passed by name (let next = advance(k)(st) in loop(k - 1)(next), ~80 B/iteration) — the merged result of LowerCallConditionalCopyOutResult is runtime-RC on both branches but is never marked as such, so its owner is not tracked as runtime-managed and the back-edge deep-copies it without releasing the original. Full suites green (C# 2382/2382, LSP 70/70, e2e test tests --pipeline both 645/0/54-skipped plus the new test). |
| Tag-group match: a failed nested sub-pattern must fall through to the trailing default | Found by re-running the challenge benchmarks: challenges/reverse-complement printed only the first FASTA header and exited 0 on every input, and a 12-line reduction (match text.uncons(line) with | Some(('>', _)) -> "header" | _ -> "seq") segfaulted. Bisected to the recursive decision-tree match compilation: TryPlanTagGroupSwitch accepts a trailing wildcard/variable case as the switch default, but LowerMatchArmsViaTagGroupSwitch handed every group noMatchLabel as the failure target of its last case. When the outer tag matched and the nested literal/tuple/constructor test then failed, control went to the exhaustiveness-failure path — a 0 result standing in for a string — instead of the wildcard arm that covers exactly that case (as the linear lowering, whose per-case fail labels chain into the next case, always did). The group failure target is now the default arm's label whenever a default exists. Correctness regression tests: DecisionTreeMatchTests.GroupLastCaseFailingNestedSubPattern_FallsThroughToTrailingDefault (compile-and-run for the matching, tag-matching-but-literal-failing, and other-tag cases) and tests/match_tag_group_nested_literal_falls_to_default.ash. reverse-complement is correct again (rc(rc(x)) byte-identical to x on the 250k fixture, headers preserved): 250k 0.053 s / 45 MB, 1M 0.21 s / 164 MB, 25M 5.76 s / 3.91 GB. Full suites green (C# 2385/2385, LSP 70/70, e2e test tests --pipeline both 647/0/54-skipped including the new test). |
| Lay out single-constructor ADTs without a tag word | Every ADT cell carried a leading tag word even for a type with exactly one constructor, where the tag can only ever hold one value — a wasted word per instance and a provably-constant tag test on every match. Such a type (one non-nullary constructor; not a builtin, zero-cost newtype, resource, or resource-bearing type) is now laid out per a new HeapLayouts.TaglessAdt descriptor (payload at offset 0), decided in one predicate (Lowering.TaglessAdt.cs, IsTaglessAdt) that every ADT emission site consults. The IR carries no types, so a Tagless flag was added to the six ADT instructions (AllocAdt, AllocAdtStack, AllocAdtToSpace, AllocReusing, GetAdtField, SetAdtField) and threaded from each of the ~60 lowering sites — constructor application, record update, pattern-field extraction, record field access, structural droppers, synthesized deep copiers, TCO back-edge normalization, and the raw LoadMemOffset/StoreMemOffset in the ADT copier and layout-capability walker — so the backend never consults a type to compute an offset. A tagless cell's tag is never read: a match against such a type emits no GetAdtTag/SwitchTag (the tag-switch, tag-group and EmitRequireTagMatch lowerings short-circuit on the constructor, resolved by name — never on the scrutinee's inferred type, which can still be an unresolved variable there), and synthesized droppers/copiers materialize the sole constructor's tag as a literal, which a new constant-SwitchTag fold in FoldConstants (mirroring the existing constant-branch fold) collapses to a jump. Reuse tokens gained a layout dimension: a tagless cell is one word smaller than a tagged cell of the same field count, so TryConsumeReuseToken rejects a tagless/tagged mismatch as ConstructorCellKindMismatch in both directions. The pre-existing zero-cost newtype form (type UserId = UserId(Int)) is untouched and composes unchanged; this covers the ` |
| Hoist backend scratch allocas to the entry block (fixes an -O0 TCO-loop stack overflow) | A TCO loop that allocated a fresh heap cell each iteration overflowed the native stack at -O0 — a 1,000,000-element List(Point) build-then-fold segfaulted, and a gdb single-step showed rsp dropping exactly 112 bytes per iteration and never recovering (7 dynamic 16-byte allocations, none freed). The backend's memory helpers (EmitAcquireRuntimeRcBlock, EmitRuntimeRcFreeListBinSlot, EmitAllocDynamic, the copy-out/reclaim/BigInt-format helpers — ~50 BuildAlloca sites in LlvmCodegenMemory.cs) emitted their fixed-size scratch slots at the current insertion point, i.e. inside the loop body. LLVM's canonical rule is that every alloca belongs in the function entry block, where it becomes one fixed frame slot allocated once in the prologue; a fixed-size alloca in a non-entry block is lowered at -O0 as a runtime stack-pointer adjustment reclaimed only by function return or llvm.stackrestore, so one per loop iteration leaks the whole stack. -O2 never showed it (mem2reg/SROA promotes the scratch allocas away), which is why every challenge and the e2e suite (both run at -O2) missed it. New EmitEntryScratchSlot positions the builder before the entry block's first instruction of the current function — derived from the builder's own insert block via LLVMGetBasicBlockParent, not the outer state.Function (some runtime helpers are synthesized into their own function, where using state.Function would produce a cross-function alloca and fail verification) — emits the alloca, and restores the insert point; every fixed-size scratch slot in LlvmCodegenMemory.cs routes through it. EmitStackAlloc (the genuine AllocStack path, a real per-execution allocation the loop's SaveStackPointer/RestoreStackPointer bracket manages) deliberately stays a loop-body alloca. Three new LLVM-C imports (GetEntryBasicBlock, GetFirstInstruction, PositionBuilderBefore, plus GetBasicBlockParent). After the fix rsp is bit-stable across iterations; the -O0 program runs clean at N=1M and N=4M (16 GB list, exit 0), and -O2 output is unchanged. Regression LinuxBackendCoverageTests.Linux_backend_llvm_tco_loop_allocating_a_heap_cell_does_not_grow_the_stack_at_o0 compiles a 1M build/sum at -O0 explicitly (an .ash test would not guard it — the e2e runner defaults to -O2) and is verified to crash without the fix. The three pipeline snapshots' ElfSha256 updated (binary bytes changed; behavior identical). |
Arm in-place string-accumulator growth for the let-bound form | The idiomatic let acc2 = acc + "x" in loop (n - 1) acc2 accumulator loop took the copying ConcatStr path — O(n^2) time and bytes, measured at 4.77 s / 19.9 GB peak RSS for 200,000 iterations at the default -O2 — while the equivalent inline form loop (n - 1) (acc + "x") already ran allocation-free via the reservation-growing ConcatStrTip (0.00 s / 8.5 MB). Four coordinated changes arm the same in-place path for the let form: (1) the affine-self-append move analysis follows a single-use let alias of a candidate parameter (AppendAliases in ComputeAffineSelfAppendOrdinals, gated by a fail-closed occurrence counter that counts any unrecognized expression shape as a second use); (2) PushSequentialLet arms the append context around the let value (TryArmAffineAppendForLetValue) instead of the tail-call argument, which is the already-computed binding; (3) the armed let's scope-exit arena reclaim is suppressed (the bound value is the loop accumulator, released by the TCO back-edge reset); (4) loads of the armed binding carry the ConcatStrTip producer fact (_affineAppendResultSlots, keyed by function origin and slot) so the back edge recognizes the argument as the in-place-grown accumulator and skips the predecessor release. Part (4) is the correctness core: the RuntimeManaged ConcatStrTip grows the RC accumulator in place and consumes the old parameter's reference, but the argument reaches the back edge as an RcDup of a Borrow of a LoadLocal that carried no such fact, so the back edge released the old parameter a second time — a net −1 refcount per iteration on the one live accumulator, crashing exactly when the string outgrew its first free-list chunk (between 2,000 and 3,000 iterations). Two debugging traps worth recording: an analyzer-rejected temporary debug print made dotnet run silently reuse a stale compiler build (a "fix didn't work" signal that was really "fix wasn't built"), and the TCO reset resolution replays each function's instructions with every per-temp ownership fact cleared and re-derived from the instructions alone — an out-of-band fact stamped at initial lowering evaporates there, so a new LoadLocal case in the central per-Emit fact recorder re-establishes it from the durable slot map, and IsRuntimeManagedConcatStrTipResult follows RcDup/Borrow source chains. Measured: the let form now matches the inline form — 0.00 s / 8.5 MB at 200,000 iterations; 4,000,000 iterations in 0.00 s / 13.3 MB (genuinely O(n)). An 8-case adversarial battery is correct, including the shapes that must decline arming (a binding also consumed on the exit path; a binding whose length is read before the tail call) — both stay on the copying path, slow but correct, via the single-use gate. New e2e regressions: tests/tco_affine_string_append_let_bound.ash (30x past the historical crash threshold, exact-content and multi-part-chain cases) and tests/tco_affine_let_two_uses_declines.ash; the pre-existing inline-form regression is unchanged and green. Full suites green (C# 2393/2393, LSP 70/70, e2e test tests, format clean). |
| Release read-builtin-consumed RC call results (fixes a 32 B/iteration leak) | A closure call whose string result is consumed by a read-only builtin — Ashes.Text.byteLength(f(i)), print, write — leaked one RC cell per evaluation when nothing owned the result: the conditionally RC-normalized call result (CopyOutArena/CopyOutList with Purpose=RcNormalization, or the callee's own RC return) is a fresh, unowned reference, and no release site existed for it (PerceusLifetimePlacement only moves owner-anchored drops, never invents them; a let-bound result is owned and was already released correctly). Measured: a loop-body let f = given n -> fromInt(n) + "!" in ... byteLength(f(i)) grew to 163 MB over 5,000,000 iterations (32 B/iter) against the 8.2 MB floor, at both -O0 and -O2. Three propagation gaps closed together, because the second and third silently re-open the first one layer up: (1) the concatenation-operand release helper was generalized (ReleaseConsumedOwnedOperand) and read-only builtins (TextByteLength, PrintStr, WriteStr, WriteErrorStr) now release a NewlyProduced RC argument after the read — a borrowed binding or literal declines by its recorded ownership kind, no new analysis; (2) a control-flow join (if/match merge) now keeps the merged value NewlyProduced when every branch was itself a fresh RC value (one borrowed or owned arm — including an arm returning a runtime-managed TCO parameter, which is RC but owned — poisons it, since releasing a merged owned value would free memory still in use); the per-arm bool list became a two-fact record to carry this; (3) a let-scope result reload (RecordFrameRestoreTemp, the save/reload PopLetScope emits around scope-exit drops) preserves NewlyProduced the same way. Verified on a 14-case probe battery (direct, let-bound, double-read adversarial, match-joined, nested two-level if through an inlined callee) — all flat at the 8.2 MB floor with byte-identical outputs, where the un-fixed compiler held 163 MB. New Linux_backend_llvm_read_builtin_consumed_call_result_memory_should_plateau (three low-floor growth programs: direct nested-helper result, match-joined result, let-scope-reloaded result) plus two e2e correctness tests (tests/rc_release_read_builtin_call_result.ash, tests/rc_release_match_joined_call_result.ash). Full suites green (C# incl. the new plateau test, LSP 70/70, e2e 650/0/54-skipped); challenge outputs byte-identical (fannkuch-redux, fasta, n-body, reverse-complement SHA-matched; binary-trees, k-nucleotide clean). Found while measuring a closure-helper tail-contification baseline — the worked example showed no closure-cost gap at all once this leak was fixed. |
| Extend in-place reuse borrowing across a statically-resolved, provably inspect-only callee | A traversal that hands its tail to any function outside the closed reuse registry — even a same-shape read-only helper called from an arithmetic expression or a match guard — always took the defensive CopyOutArena{Purpose:RcNormalization} path, regardless of what the callee actually did with the value. The existing FunctionOwnershipSummary.ParameterOwnership fact does not answer this question: it is computed by a walk narrowly scoped to resource borrow-read builtins (file/socket ops), not a general "does this function only inspect its RC argument" property — running it on a plain inspecting helper still classifies the parameter Consumed. The fact that does answer it already existed: BorrowInspectExpression/BorrowInspectOnly, the walker that already lets a TCO loop borrow its own tail parameter across match/head/tail structural uses and its own tail self-call — but it fired only for a parameter consumed at a function's own self-call, never for a hand-off to a different function. New ComputeOpenWorldInspectOnlyParams computes the same inspect-only proof for every parameter of every registered function via a monotone least fixpoint (the existing WholeProgramFixpoint.RunToFixpoint helper): a hand-off to a callee already proven inspect-only in the previous pass is approved, so a chain of self-contained helpers converges over several passes while a genuine mutual cycle never does. BorrowInspectCall gained one new branch consulting this table (excluding the self-function — a partial self-application is a separate question); every existing consumer (ComputeTcoParamFacts's ConsumedTail gate, and through it IsBorrowableInspectOnlyList) sees through a proven hand-off automatically with no changes of its own. Measured: a 200-iteration driver folding a 200,000-element List(Body) (returning a scalar, one arm also calling a sibling counting/predicate helper on the tail) went from defensively normalizing to fully borrowing — 32.8 MB -> 20.5 MB peak RSS (~60%), 0.23 s -> 0.05 s (~4.6x); a genuinely unsafe hand-off (a helper returning its argument directly) was verified to still normalize. Two pre-existing tests asserted the old, over-conservative "still normalizes" behavior for exactly the hand-off shapes this now proves safe; both were repurposed to assert the corrected outcome, each paired with a new negative test using a genuinely retaining callee to keep the original regression boundary. A third pre-existing test's continued normalization was traced (not assumed) to an unrelated, separate limitation — a constructor pattern destructured directly in a cons head (Body(x, mass) :: rest) is not re-tainted by the existing pattern-binding walk, which only handles a cons head/tail bound to a plain variable or wildcard — with a companion positive test confirming the hand-off itself is approved once that limitation is avoided. Full suites green (C# 2397/2397, LSP 70/70, e2e test tests --pipeline both 652/0/54-skipped, format clean); the full challenge soak (fannkuch-redux N=10/N=11, binary-trees N=18/N=21, fasta, n-body, reverse-complement, k-nucleotide, mandelbrot, spectral-norm, pidigits) run to completion with output hashes and peak RSS unchanged from their known-good baselines. |
| Merge mutually tail-recursive groups of differing parameter shapes into the dispatch loop | TryLowerMutualRecursionTco required every member of a let recursive … and … group to have the same arity and structurally identical parameter types, because the synthesized dispatch lambda gives each parameter position one shared, HM-typed slot that every member's parameter unifies with. Any other group — a parser whose members carry accumulators of different types, or a pair like ping: Int -> Str -> … / pong: Int -> Int -> … — fell back to the curried closure chain, where each cross-member "tail call" is two CallClosures around a heap-allocated intermediate closure inside an arena bracket with a post-call CopyOutArena, so it is not a tail call at all and grows the native stack on every hop: a 50,000,000-deep heterogeneous ping/pong chain segfaulted at both -O2 and -O0. The dispatch now carries one slot per parameter position where all members agree (exactly the previous layout, so every group that merged before lowers identically) and one slot per distinct type where they do not, or where only some members have a parameter at that position at all — members no longer need to share an arity. A tail call fills the callee's slots with its arguments and every other slot with that slot type's default value (0, false, 0.0, "", the zero rune, the zero fixed-width unsigned, or []), which is why a non-shared slot's type must have a constructible default: a user-declared type, tuple, function, or unresolved type variable in a non-shared slot still declines the whole group. Filling inactive slots with defaults rather than passing the caller's own parameters through keeps every dispatch parameter single-use in each arm, so the loop's existing owned-parameter drop/normalize machinery and the move-analysis that arms in-place accumulator growth see exactly the shapes they already handle; and because the default is a plain literal, its per-hop RC normalization is an arena bump allocation the loop's own reset reclaims, not a heap round-trip. Also found and fixed on the way: the gate never compared members' result types, yet every member body becomes one arm of the dispatch match, so a valid group whose non-tail-calling third member returned a different type (a/b mutually tail-recursive returning Int, c returning Str) failed to compile with a bogus ASH004 Type mismatch: Int vs Str … in match arm 3 pointing into the standard library; members with differing result types now decline. Measured: the 50,000,000-deep heterogeneous chain goes from a segmentation fault at both levels to a correct result in 0.01 s / 8.2 MB RSS at -O2 and 0.32 s / 8.2 MB at -O0 (the homogeneous control at the same depth: 0.00 s / 0.16 s), and a 10,000,001-deep differing-arity group (countDown: Int -> List(Int) / collect: Int -> List(Int) -> List(Int)) completes in 10 ms. New e2e fixtures cover the heterogeneous and differing-arity loops at 10,000,000+ depth, the result-type regression, and a user-ADT slot that correctly keeps the closure path; MutualRecursionTcoTests gains slot-layout, differing-arity, no-default decline, and result-type decline cases. |
| Resolve non-tail sibling references inside a merged mutual-recursion dispatch | The merged dispatch lambda's body is every member body with only its tail in-group calls rewritten into dispatch calls; any other reference to a sibling — a call whose result the member inspects (match findCycle(name)(decls)(path) with … before its own tail call), a partial application, or a reference from a nested lambda — is left as a plain variable reference. The closure-lowered member bodies resolve such references by symbol through the group's RecursiveGroupContext, but the dispatch lambda was lowered with a scope holding only the dispatch's own name, so the reference fell through to LowerVarUnbound and, because the member is a top-level binding, reported the Model-A forward-reference diagnostic ASH014 Binding 'findCycle' is not yet declared at this point. on a well-formed program. The gap predates the heterogeneous-slot widening (a same-shape ping/pong pair whose pong probes ping(0)(acc) before its tail call failed identically), but that widening made the self-hosted semantics package's findSupertraitCycleInRequirements/findSupertraitCycle group eligible for merging and broke the selfhost/tests/semantics build. The dispatch body is now lowered with every member name bound to its already-emitted closure slot (RecursiveGroupSetup.Slots, monomorphic recordTypes — the schemes are generalized only after this transform), exactly as the continuation scope later binds the names to the wrapper slots, so a non-tail reference captures and calls the ordinary closure member while tail calls keep looping through the dispatch. Regression fixtures: tests/mutual_recursion_tco_non_tail_sibling_call.ash (both the cycle-finder shape from the self-hosted compiler and the ping/pong probe) and MutualRecursionTcoTests.NonTailSiblingReference_LowersInsideDispatch. |
| Gate dead-arm trimming to pattern shapes the coverage engine analyzes exactly | The decision-tree match work reused the "Missing case" coverage engine to drop a trailing run of provably unreachable cases, on the premise that the engine is a sound, fully recursive per-field-position exhaustiveness check. It is not: it is a deliberate under-approximation of what is missing, which is exactly right for a diagnostic (it must never report a false "Missing case") and exactly wrong for deleting code. Two concrete gaps, both found by compiling and running the self-hosted semantics package rather than by any hand-built fixture: a constructor's argument positions are checked independently of one another (`(true, false) |
A let bound to a borrowed read of an RC loop parameter must not become an owner | TrackLetOwnership decided a let's runtime-managed ownership from its value temp's representation alone (IsRuntimeManagedResultTemp: the fact says RC), so let r = acc inside a TCO loop whose acc had been RC-normalized registered r as an independent runtime-managed owner — while the LoadLocal that produced it is stamped Borrowed and never retained, and acc is not an OwnershipInfo the alias rule could redirect to (loop parameters are released by the back edge's flag-gated parameter drops, a separate mechanism). Every path that leaves the let scope then released the same reference twice: the back edge dropped the old parameter and the let's owning scope-exit drop (RcDrop OwnerSlot=<r> RuntimeManaged), and the then r return path dropped r before the exit transfer handed the result out. A trivial let r = acc in … loop(n-1)(r + "x") already double-dropped on every iteration (the 532bca29 compiler reproduces it) but happened not to fault; the same shape inside a match arm over Ashes.Text.unconsText faults reliably, and the heterogeneous mutual-recursion merge synthesizes exactly this shape (let result = __recgroup_arg2, let tail = __recgroup_arg0) for every member arm, which is how the self-hosted ProjectDependencyGraph.pascalCaseCharacters/continuePascalCase and relativeSourcePath/continueRelativeSourcePath groups crashed the selfhost/tests/projects binary (bus error) once #593 merged them. Found by bisecting that binary to #593, dumping the lowered IR of the merged groups at #592 vs #593, reducing to a 40-line single-file crasher, and diffing the lowered IR of crashing and non-crashing variants until the only difference left was the extra LoadLocal/RcDrop OwnerSlot pair. Fix: a let owns a runtime-RC reference only when its value temp is a fresh producer or a transferred value (IsRuntimeManagedResultTemp && !IsBorrowedOwnershipTemp); a borrowed read keeps the erased-marker tracking it always had for non-RC values, so the slot's real owner remains the only release. Regression fixtures: tests/tco_let_alias_of_rc_parameter.ash (the plain alias loop, the match-arm alias loop, and the full pascalCase mutual group) and OwnershipTests.Let_alias_of_rc_loop_parameter_does_not_become_an_owner. |
| Retain a runtime-managed owned binding stored inside a tail self-call argument | let label = helper(...) in loop(n - 1)(Wrapped(instruction = Jump(label), location = None) :: acc) inside a TCO loop stored the let-bound RC call result into the constructor with a plain SetAdtField (no RcDup) and then released it through the let's owning scope-exit drop at the back edge, so the accumulator carried a freed reference into the next iteration: silently wrong values when the callee returned a literal (the drop corrupted the RC free list, and later iterations' records overwrote earlier ones), Runtime error: failed to allocate heap memory from OS when it returned an RC string and anything allocated afterwards. Pre-existing (the 532bca29 compiler reproduces it); found when the self-hosted optimizer's known-tag switch fold built exactly this shape and its test binary crashed. The retain for this case already existed — DuplicateRuntimeManagedOwnedValueForTransfer, applied to a constructor argument whose request carries TransfersRuntimeManagedChildren — but that flag was set only at function-return boundaries (WithEscapingConsumerOwnership), never for a tail self-call argument, although that value escapes every binding scope of the iteration exactly like a result escapes its callee. LowerCallTcoEvalArg now marks its request as transferring runtime-managed children, and the constructor-argument path (RetainEscapingConstructorArgument) applies the owned-binding retain whenever that flag is set, independently of the owning-consumer condition that gates the Perceus pattern-owner duplicate, so existing pattern-owner behavior is unchanged. Diagnosed by reducing the crashing self-hosted test to a 45-line standalone program and cutting it down variant by variant (record wrapper, helper call, literal vs. RC result, tagless vs. tagged layout, reuse on/off, --pipeline both) until only the let-bound call result inside the constructor remained, then reading the final IR of the loop. Regression fixture: tests/tco_let_call_result_in_accumulator_record.ash (with allocation churn after the loop so a dangling label cannot survive by luck) and OwnershipTests.Let_bound_call_result_in_tco_argument_constructor_is_retained. A sibling shape — a record pattern binding a string field directly on a list element (Case { label = l } :: rest) handed to a storing callee — still crashes and is tracked separately. |
| Scalarize two-capture stack closures and devirtualize let-bound helper calls through their slot | Closure environment scalarization was limited to one capture on the premise that the shared three-word call signature (env, arg, ownership flag) had only the env word free. The flag word is free too whenever the CallKnown passes no ownership flag and the callee's body never reads one, so a second capture now travels there: the caller-side gate accepts a 16-byte AllocStack filled by exactly one store per 8-byte capture and used nowhere else, and the callee variant reads the second capture through LoadArgumentOwnership, which the backend lowers as a raw read of that same parameter (no truncation), with the flag temp carrying the capture's own temp. Three or more captures keep their environment — there is no further free word without a per-function calling convention. LoadArgumentOwnership joins the non-allocating instruction set; without that, the variant was classified as allocating and the arena bracket around the scalarized call survived, which is exactly what the first measurement showed (no speedup until the whitelist was fixed). Separately, DevirtualizeKnownClosureCalls only recognized a closure temp defined directly by MakeClosure/MakeClosureStack, so a let-bound local helper (let step = given x -> ... in step(1)), whose call always goes through a StoreLocal/LoadLocal round trip, never devirtualized at all — the common shape was unreachable while the rarer immediately-applied lambda was. It now resolves through a slot written by exactly one StoreLocal (lowering only reads a binding's slot inside the binding's own scope, after the store), drops the load it made dead, and removes the scope-exit CleanupResource(Function) of a stack closure that never received a dropper (no store to the closure object's dropper word at offset 24; the backend treats a zero dropper as a no-op), so the slot, the closure construction, and the environment die in the ordinary dead-code sweep and both captures scalarize. Measured against the pre-change IrOptimizer.cs, 20,000,000-iteration loops, hyperfine 15 runs: let-bound two-capture helper 11.3 ms -> 4.1 ms at -O2 (2.76x), 151.7 ms -> 96.7 ms at -O0; immediately-applied two-capture lambda 10.0 -> 4.1 ms / 128.2 -> 96.5 ms; let-bound one-capture helper (newly reachable through the slot) 11.3 -> 4.1 ms / 128.9 -> 84.6 ms; the already-scalarized one-capture immediately-applied control is unchanged (3.8 vs 4.1 ms within noise, identical at -O0). The -O2 win is the same arena-bracket removal the single-capture case already showed — LLVM eliminates the stack environment itself but cannot prove the arena-cursor bookkeeping dead. New e2e fixtures cover the two-capture direct call, a helper both called directly and escaping into List.map (heap closure, must still devirtualize the direct call and drop correctly), and a three-capture helper (devirtualized, not scalarized); IrOptimizerTests gains flag-word scalarization shape and execution cases, a decline when the callee reads the ownership flag, a three-capture decline, slot-forwarded devirtualization with execution, a multiply-stored-slot decline, and a dropper-installed cleanup that must survive. One existing test that asserted the non-folded recursive call stayed a CallClosure now accepts CallKnown — the call is still a runtime call, just direct. |
| Resolve a concrete trait requirement inside a constrained function from the requirement, not from the function's own dictionary | A function that takes a hidden trait dictionary (let both sourceTemp singleDefs knownLabels = match lookup(sourceTemp)(singleDefs) with ..., polymorphic in sourceTemp) has every reference to another dictionary-taking function of the same trait rewritten by a syntax-only pre-pass (RewriteTraitDictionaryFunctionReferences) to pass its own __trait_evidence_N parameter, matching by trait name alone, and TryLowerExplicitTraitDictionaryFunctionCall then applied that evidence unconditionally. So lookup("bui" + "ld")(knownLabels) in the same body — the key instantiated at Str — compared strings with whatever Eq the caller of both had supplied: with Eq(Int) that is a pointer comparison, which happens to succeed for two interned literals and fails for any computed string (a silent None); with the roles reversed ((sourceTemp: Int) and a polymorphic value looked up second) the Eq(v) dictionary compared integers as strings and segfaulted. The active-parameter lookup that lowering falls back to (FindActiveTraitDictionaryParameter) had the same hole one level down: with no exact constraint match it handed out the sole active parameter of that trait for any requirement, concrete or structured. Found only by compiling and running the self-hosted optimizer, whose returned-closure devirtualization looked a CallKnown label (a Str field) up in a List((Str, Str)) from inside a function polymorphic in the temp key: the lookup succeeded on hand-built fixtures (interned labels) and failed on collector-built ones, and an IsExactCoveragePattern-style bisection of the pass was a dead end until the probe known=None manual=Some(leaf) pointed at the string comparison; a 20-line single-file reduction then reproduced both the wrong None and the segfault. Fix: the explicit-evidence call path lowers the real arguments first (their unification pins the instantiated constraints) and keeps the threaded parameter only for a requirement that is still a bare type variable — anything concrete, or structured over the parameter's variable, is resolved by ResolveTraitEvidence/BuildTraitDictionary from the requirement itself; and BuildResolvedTraitDictionaryValues now short-circuits only on an exact active parameter match, so a concrete requirement always reaches static resolution while an abstract one still comes back as a Parameter plan that the lone-parameter fallback supplies. Regression fixtures: tests/trait_concrete_requirement_inside_polymorphic_function.ash (both orderings, with a computed string key so pointer equality cannot pass by luck) and TraitEvidenceLoweringTests.ConcreteRequirementInsideAConstrainedFunctionResolvesStaticallyInsteadOfTakingItsDictionary. |
| Keep operator operands out of tail position | In a self-recursive function that has at least one genuine tail self-call (so lowering runs it as a TCO loop), a self-call that is an operand of an operator in another branch — then 1 + countEvens(tail) else countEvens(tail), countRight(n - 1) + 1, a comparison operand, a negation operand — was lowered as a tail jump too: the operator lowerings (LowerAdd and every other binary, unary, and pipe operator in Lowering.Operators.cs) lowered their operands with a plain LowerExpr, inheriting the InTailPosition flag the operator expression itself legitimately carries, while call arguments, let values, match scrutinees, and constructor fields had each grown their own TcoTailPositionScope save-and-clear. The back edge then stored the argument and jumped, the operator applied to a dummy result in unreachable code after the jump, and the loop's base case returned alone: countEvens([1, 2, 3, 4]) was 0, sumTo-style functions with no genuine tail call were unaffected (never a TCO loop, which is why the whole .ash suite passed), and a let-bound call in the same position was fine. Found only by compiling and running the self-hosted optimizer's own local-CSE tests, whose countGetAdtField helper is exactly a 1 + count(tail) / count(tail) pair over a list. Fix: every operand lowering in Lowering.Operators.cs opens a TcoTailPositionScope, restored at the operator's exit. Regression fixtures: tests/tco_non_tail_self_call_in_operator_operand.ash (left and right operand, list and record-pattern walks, a comparison under negation) and CallArgumentTailPositionTests.Recursive_call_used_as_operator_operand_is_not_lowered_as_tail_call. |
| Retain runtime-managed children stored into an escaping tuple, list literal, or cons cell | A runtime-RC tuple owns its children (its drop releases them) and an escaping arena aggregate carries them out of the scopes that own them, yet LowerTupleLit only applied the Perceus pattern-owner duplicate to its elements, LowerRuntimeManagedListElement retained an owned-binding head only for a runtime-RC list, and LowerCons never retained an arena cell's tail — while the ADT constructor path already retained both owned bindings and loop parameters. So a TCO loop returning (xs, ys) from two list accumulators handed out a tuple whose lists the loop's exit drop had just released (the exit only recognizes a parameter that is the result, by pointer equality), a non-TCO function returning (ys, zs) of two let-bound lists returned freed lists, [xs, ys] lost its second element, and (left :: rights, absorbed) crashed the self-hosted optimizer's concatenation-chain walk (its parts and absorbed-link lists were garbage once the freed cells were reused). Every shape read back correctly on a small program and only failed once later allocations reused the cells, which is why a churn allocation after the call is part of the regression fixture. A loop parameter is not an ownership-scope entry and its placement (arena or runtime-RC) is decided only after the body is lowered, so the retain is an erased RcDup marker recorded per parameter slot (DuplicateRuntimeManagedTcoParameterForAggregate) that FinalizeTcoParameterAggregateRetains upgrades to a runtime-managed duplicate when the final placement is RC — the same late-upgrade idea the Perceus pattern-owner markers use — and never inside a tail self-call's arguments, where the back edge moves the old parameter into the successor. The tuple decides up front that it transfers its children (the transfer flag, the tail position of a TCO loop body, or a runtime-RC tuple request) and passes that decision to its elements so a nested cons retains its own tail; list literals and cons cells do the same in tail position. Found by compiling and running the self-hosted optimizer's own tests; reduced to a 25-line walk, then to walk n xs ys = if n == 0 then (xs, ys) else walk(n - 1)(n :: xs)(n :: ys). A related, pre-existing gap stays open: a caller never releases the aggregate result (tuple or ADT alike) of a TCO loop, so such a call leaks its result per call; it is tracked as its own item. Regression fixtures: tests/aggregate_result_retains_runtime_managed_children.ash and OwnershipTests.Tuple_result_of_a_tco_loop_retains_its_runtime_managed_parameters. |
Walk Ashes.Text.split, trimStart, and trimEnd with explicit parameters instead of a capturing local closure | The stdlib split scanned its text with a nested let recursive go from that captured the whole Bytes of the text, and every recursive call — one per piece — copied that capture through the closure-environment normalization, so splitting a 100 KB text into 4,000 lines mapped 3,342 arena chunks, peaked at 632 MB of resident memory, and took 110 ms; trimStart/trimEnd had the same shape per whitespace byte. The self-hosting phase benchmark surfaced it: the self-hosted import-header pass, which splits each file into lines, ran 71 times slower than the .NET one and spent 195 ms on the 190 KB TypeInference.ash alone, almost all of it in mmap/munmap (one 233 KB copy and one 4 MiB chunk per line, seen with strace -c and a catch syscall mmap backtrace into <std:Ashes.Text>). The three walks are now top-level tail-recursive functions taking the buffer as a parameter: the same split maps 9 chunks, stays at the 8 MB runtime floor, and finishes in under a millisecond, and the header pass on that file drops from 195 ms to 2 ms. The general cause — a self-recursive local closure copying a large captured buffer on every call — stays open as a compiler item; the stdlib no longer depends on it. Regression fixture: LinuxBackendCoverageTests.Linux_backend_llvm_text_split_of_a_large_text_memory_stays_bounded. |
| Check an inlined helper's references transitively before inlining it in a reuse arm | Inside a match arm with a live reuse token (or a reuse specialization) a saturated call to an inlinable top-level helper is inlined, and InlinedBodyReferencesResolveHere first checks that every free name of the helper's body resolves in that isolated scope — lexically, by known label, as a constructor, or by being inlinable itself. That last case took inlinability as proof of resolvability. A stitched stdlib helper that calls a module sibling through the stitcher's alias name (trimEnd calling dropTrailingWhiteSpace after the split above) is inlinable but resolves nowhere outside its own module: the outer helper (formatInstructionDescription in the self-hosted IR printer) was inlined, the inner call was declined, and — the wrapper capturing the alias, so never registered as a label-callable function — the plain call reported Ashes_Text_trimEnd as not yet declared, breaking every self-hosted project that formats IR. The check now follows inlinable references into their own bodies (a helper already visited on the walk counts as resolved; non-recursive lets cannot form a cycle), so the outer helper stays an ordinary call when its chain does not resolve. Regression fixture: ReuseInlineResolutionTests.StitchedHelperCallingAStdlibHelperThroughItsModuleAliasIsNotAForwardReference. |
| Devirtualize calls through captured closures and collapse saturated curried chains into one call over a caller-frame environment | A stitched module's functions reach each other through alias bindings captured in closure environments, so nearly every call in a self-hosted package was a CallClosure through a LoadEnv (9,894 CallClosure against 542 CallKnown in the stage-1 phase benchmark), and a saturated call to a curried function paid one heap environment and one closure object per stage on the way to the body. Two whole-program passes in IrOptimizer.ClosureEnvironments.cs now run before scalarization. DevirtualizeCapturedClosureCalls collects, per function, every creation site of its environment (a MakeClosure/MakeClosureStack over a fresh single-store environment, or the CallKnown the per-function devirtualization already turned an immediately-called closure into) and resolves each slot's stored value to a closure label directly, through a local slot, through a captured slot of the creating function (a whole-program fixpoint over the capture graph), or through a call to a function with a known returned label; a slot every site agrees on lets the CallClosure through its LoadEnv become LoadMemOffset(closure, 8) plus CallKnown, any disagreement or unresolvable site leaves it indirect. InlineCurryingStages then recognizes a stage function that only copies its captures and argument into a fresh environment and returns a closure over the next stage, and rewrites a caller that immediately extracts that closure's environment and calls the next stage directly into a stack environment filled by the caller, so f(a)(b)(c) reaches the body with no intermediate allocation and each chain is re-examined to a fixpoint; a stage that does anything else (a retain, a computation) is left alone. The benchmark's lexer row went from 7.6x to 3.1x of the .NET lexer (298 ms to 117 ms over the corpus, 16 ms to 9 ms on TypeInference.ash) and the parser row from 2.9x to 1.4x (441 ms to 203 ms) with no source change; both passes together cost about 0.85 s of the 31 s -O2 build of the stage-1 program. Hand-built IR tests cover the positive shape, the disagreeing-sites decline, the stage collapse, and the impure-stage decline (IrOptimizerTests). |
| Take ownership of a runtime-managed ADT argument that a callee keeps in its result | A closure call passes a reference-counted argument under a runtime protocol: the caller reads the callee closure's "accepts a runtime-managed argument" bit, hands over a retained reference only when it is set, and drops its own reference after the call either way; a callee that advertises the bit normalizes its parameter at entry (LoadArgumentOwnership: keep an owned reference, copy a borrowed one). Only a Str parameter that always reached the result ever advertised (LowerLambdaCoreNormalizeAlwaysReturnedStringParameter), so a module function keeping any other reference-counted argument in its result, a curried stage capturing it for the closure it returns (lexerToken(kind)(text)... in the self-hosted lexer) or a plain wrap k = Some(k), held a pointer the caller then freed; the freed cell was reused by the next allocation of the same size, so every token's kind read as the last kind allocated. The self-hosted lexer had carried a deepCopy of every token as a workaround since its first port. The normalization now covers every parameter type the runtime RC layer can copy into an owned value, the records and ADTs CanCopyOutAdt/CanRuntimeManageTcoAdt admit alongside Str (LowerLambdaCoreNormalizeAlwaysReturnedParameter, IsRuntimeNormalizableParameterType); the reachability walk was already correct. Regression fixtures: tests/rc_adt_argument_kept_by_callee_result.ash (curried builder in one file) and LinuxBackendCoverageTests.Linux_backend_llvm_module_function_keeping_an_rc_adt_argument_in_its_result_owns_it (module function through its alias closure). |
| Map stitched dependency-module IR locations to the module's own file lines | Project compilation stitches every module into one combined source, and Lowering.SetSourceContext(CombinedCompilationLayout) resolved an instruction's location by finding its module region and counting lines within the region's text. That is exact for the entry file, whose region is kept line-for-line (import lines blanked, hoisted declarations replaced by blank lines), but a dependency module's region is a re-rendering: the export block and header are gone, type declarations are hoisted into a separate prefix, and each binding is rendered as let <generated> = (<value with renamed identifiers>). So every dependency-module location carried a line counted inside the rendered text: a small module collapsed onto lines 1-2 (gdb: "Line number 17 is out of range for Tok.ash", "No compiled code for line 24"), a large one was shifted by the number of stripped lines, breakpoints in dependency modules could not be placed, and perf/gdb line attribution on the self-hosted packages was unreliable. The stitcher now records a SourceLineAnchor for every fragment of reconstructed text (each rendered binding value, each hoisted declaration): the combined range it occupies and the file line/column where that text starts. Renaming never adds or removes a line break, so within a fragment a position maps by line delta from its anchor; ResolveSourceLocation consults the anchors first, leaves positions in an anchored region but outside every anchor (the generated binding name, wrapping parentheses) unlocated like the existing inter-region glue, and keeps the region-relative mapping for regions without anchors (the entry body). Verified with breakpoints on a two-file project compiled at -O0 --debug: break Tok.ash:24 goes from "No compiled code for line" to a hit in makeTok's first stage with the entry file's breakpoints unchanged. Match-arm bodies that lower to a single allocation still get no line-table entry of their own, in single-file programs too; that is a separate codegen detail. Tests: StitchedSourceLocationTests (layout anchors per fragment; lowered locations of a dependency module lie within its declarations' own file lines). |
| Keep the source line of an instruction whose codegen hoists a scratch slot into the entry block | EmitEntryScratchSlot repositions the builder before the entry block's first instruction to place an alloca, and LLVM's IRBuilder::SetInsertPoint(Instruction*) also adopts that instruction's debug location; the entry-block allocas are emitted with the location cleared, so the builder came back from every hoist with no location and every instruction emitted afterwards for the same IR instruction carried none (line 0 in the table). A reference-counted constructor allocation hoists its result and free-list slots first, so a match arm whose whole body is such an allocation (` |
| Keep an owned binding alive across the whole curried call chain that captured it, and never release a borrowed call argument as a consumed result | Lifetime placement follows an owned reference-counted binding through borrows, alias slots, closure environments, and a partial application whose argument is the alias, so the binding stays live until the closure that captured it is applied. It did not follow a partial application whose closure is the alias: in scan(bytes)(n)(0)([])([]) the first stage captures bytes and every later stage copies it into the closure it returns, so tracking stopped after the second application and the RcDrop landed before stages three to five ran the body, a use-after-free once the value was large enough to leave the arena (a 192 KB source string; the self-hosted lexer never hit it because its callers keep the source alive). CollectOwnerAliases now treats applying an alias-holding closure (CallClosure on an alias, CallKnown over an alias-holding environment) as producing an alias while the result is applied again. Separately, LowerAppliedClosureCall counted any non-variable argument temp with a reference-counted representation as a consumed fresh result and released it after the call, including a borrowed read of an owned binding such as Ashes.Byte.fromText(source) written at the call site, whose release the binding's own drop already covers: a second release. A borrowed temp (IsBorrowedOwnershipTemp) is now neither transferred to the callee nor released as consumed. Regression fixture tests/rc_owned_binding_survives_curried_call_chain.ash covers the Str parameter, the let-bound byte view, and the call-site byte view; all three crashed at -O0, -O2, and with reuse disabled. The checklist item that attributed this to the fromText view was wrong about the cause and is removed. |
RC Perceus migration deep dive
Migration phases
The migration completed on 2026-07-23. It replaced the arena/copy-out model as the general lifetime mechanism for escaping ordinary values while retaining regions only where their owner and reclamation boundary are explicit. The current contract lives in Compiler Architecture and IR Reference; this section preserves why the implementation took its present shape.
The work was grounded in the PLDI 2021 paper and extended report, Perceus: Garbage Free Reference Counting with Reuse. Ashes adopted precise owned/borrowed environments, late dup, early drop, recursive drop specialization, uniqueness, and reuse tokens without exposing ownership syntax in the language.
| Phase | Lasting result |
|---|---|
| 0 — decision and inventory | Classified language heap values, runtime buffers, layouts, allocation sites, ABI constraints, and the intended RC header. |
| 1 — ownership summaries | Replaced fragile call-site reasoning with FunctionOwnershipSummary: consumed/borrowed parameters, result reach, captures, and uniqueness. |
| 2 — explicit lifetime IR | Separated ordinary RcDup/RcDrop from deterministic resource cleanup and introduced control-flow-precise PerceusLifetimePlacement. |
| 3 — first runtime family | Added the 16-byte RC header, runtime counts, and type-directed recursive drops for ADTs and lists while preserving payload offsets. |
| 4 — specialization and fusion | Added constructor/deep-unique drop paths, branch sinking, safe dup/drop fusion, and the per-thread exact-size free list after native profiling exposed per-cell OS map/unmap as untenable. |
| 5 — reuse tokens | Made DropReuse return a compatible unique cell or null after decrementing a shared cell; AllocReusing consumes the token or allocates fresh, including field-transfer rules. |
| 6 — broader heap coverage | Added runtime ownership for Strings, Bytes, BigInts, result containers, tuples, records, user ADTs, lists, and supported closure environments. |
| 7 — arena retirement | Propagated ownership through scopes, calls, higher-order results, matches, closures, and TCO; normalized complete graphs so an RC parent never owns an arena child; confined to-space operations to persistent Map/HashMap. |
| 8 — conformance and documentation | Classified every remaining copy by CopyOutPurpose, compared the implementation with the paper, resolved ordinary-value blockers, and audited permanent documentation. |
Migration validation
The migration tests found correctness problems that output-only tests did not: branch-local releases suppressed by other arms, mixed RC/arena graphs, premature parent drops during payload transfer, unreturned TCO owners, and linear growth in String, closure, async HTTP, and persistent-collection workloads. Each fix gained focused IR/native coverage. Memory tests use 2K/10K/50K workloads to bound total and late ru_maxrss growth while checking output at every scale; the 1BRC gate additionally uses 75K/150K/300K-row inputs. The permanent method and matrix are documented under Compiler Memory Regressions.
The final exit gates were:
dotnet build Ashes.slnx --no-restore: zero warnings and errors;dotnet format Ashes.slnx --verify-no-changes --no-restore: clean;- compiler suite: 1,641 passed, zero failed, including native RSS/CPU gates;
- linux-x64 native execution, linux-arm64/qemu coverage, win-x64/Wine coverage, and a win-arm64 PE machine-field smoke test;
- README showcase and the VitePress production documentation build.
Post-migration challenge sweep
Status: the exit gates above did not initially run the opt-in
challenges/suite. A fresh pre/post A/B then surfaced P1 ownership failures plus severe scaling and peak-RSS regressions across it. All of them have since been resolved — each fix is narrated in the chronology below and locked by a regression test undertests/. A laterRuneAPI migration temporarily left fasta and reverse-complement stale; the renewed full-suite sweep fixed both sources and one associated TCO ownership bug. The subsequent buffered-stdout work closed the final verified audit gap.
Rune challenge repair
The Rune challenge repair also closed the last unexplained reverse-complement memory result. Both challenges now convert the Rune returned by Text.uncons explicitly, and reverse-complement stores List(Rune) rather than one heap string per base. Enabling its natural tail-consuming output loop exposed a compiler bug: final string-concat promotion could change a back-edge argument to runtime-RC after the pending TCO reset had captured its ownership facts, so the reset copied an already-RC string out of the arena and retained the original. The final reset refresh now recognizes every runtime-managed result, not only ConcatStrTip. A focused IR regression rejects that redundant copy. At the standard fasta N=25,000,000 workload, reverse-complement completes in 8.22 seconds at 4.27 GB peak RSS and a second transform reproduces the 254,166,745-byte input exactly. The roughly 34 bytes per base in the largest live sequence matches the isolated List(Rune) working set; no unexplained retained temporary remains.
Buffered line-oriented stdout
The final challenge-suite gap was line-oriented stdout. Ashes.IO.writeBuffered and writeBufferedLine now share a process-wide 64 KiB buffer, with Ashes.IO.flush for explicit delivery. Pending output is also flushed when full, before direct stdout operations, on normal exit, and before panic/runtime termination; oversized values bypass the empty buffer. A fair ticket lock serializes access on linux-x64, linux-arm64, win-x64, and win-arm64. Boundary, mixed-order, exit, panic, cross-target, and oversized-write regressions cover the behavior. A 1,000-line trace dropped from 2,000 write syscalls to one, while reverse-complement at fasta N=125,000 dropped from 20,840 to 20 with byte-identical output. On the standard N=25,000,000 workload, three runs improved from 7.55 s to 7.09 s mean (1.06x), and the buffered output remains an exact involution.
Performance and scaling corrections
Closure-call ownership adoption
The first post-migration scaling correction removed repeated RC graph normalization across ordinary closure calls. A second ownership bit in the closure's packed metadata now advertises that the direct parameter entry can adopt an RC-owned argument. The caller transfers a fresh result directly or conditionally retains a non-fresh root, then passes the ownership bit through the closure ABI; the callee adopts that reference or keeps the defensive arena-to-RC copy for unknown inputs. Only the direct lifted-function parameter advertises adoption; earlier curried parameters have already been captured in closure environments. Late-inferred TCO parameter eligibility resolves pending call flags before code generation. This restored reverse-complement from quadratic time (4.80 seconds at fasta N=30,000) to linear scaling (0.01 seconds at N=30,000; 0.06 seconds at N=100,000), with byte-identical output.
Reference-counted spines for non-tail recursive producers
A non-tail recursive list producer — let recursive makeList (count: Int) = if count == 0 then [] else 7 :: makeList(count - 1) — built one cell per recursion level in the arena. Every level's call site opens its own arena window, and a window whose result is arena-placed is torn down by copying that result out first, so each level copied the whole list built below it: peak memory quadratic in the length. Measured 70 MB at 2,000 elements, 1,010 MB at 8,000 and 6.26 GB at 20,000, against 320 KB of actual data.
Removing the window is not the fix, and the reason is worth keeping: the per-call window is where an arena-placed call result is normalized to reference-counted, and every enclosing bracket is emitted assuming that already happened. Suppressing it inside a match arm leaves the arm's own save/reclaim pair — taken before the call — freeing the result the arm just stored. Five variants of that approach each passed the whole test gate while corrupting real programs.
The copy is instead made unnecessary. A call site's copy-out is already a run-time branch on the callee's result-ownership bit, so a producer whose cells are reference-counted from the start skips it and every enclosing bracket stays correct. Two narrow changes get there. A recursive function's own call sites built their callee closure from the self binding before the body's ownership verdict existed, so a self-closure always claimed an arena result and always took the copy branch; the verdict is now written back into that instruction once known. And a cons whose tail is a call to a member of the enclosing recursive group is recognized as such a spine, so those cells — and only those — are requested on the reference-counted heap. The tail is reference-counted on both sides of the call's branch, so the cell never mixes an arena tail into a reference-counted spine.
Peak memory became linear: 8.5 MB at 2,000, 9.6 MB at 8,000, 11.6 MB at 20,000. Programs without the shape are unaffected — the self-hosted semantics test binary measures 424.4 MB against 424.5 MB at identical wall time — while the same binary gained 6.3% from the ownership-bit half alone, which fires at 605 self-call sites in one compile.
Exact-size RC allocator bins
The next scaling correction replaced the RC allocator's single unsorted exact-size free list with per-size bins for cached blocks up to 4 KiB. The old allocator linearly searched every differently sized released block, so workloads such as Ashes.Text.join became quadratic despite correct ownership and stable RSS. Direct bin lookup restored 1BRC to 0.01/0.03 seconds at 10,000/30,000 rows, matching the pre-migration timings with byte-identical output. A variable-size recycling CPU gate covers the allocator shape.
Borrowed scalar-list cursors
Scalar folds received a separate borrowed-cursor correction. A tail-recursive walk over List(Float) had been normalized to RC and then duplicated/dropped one cons cell per iteration, even though inline list heads have no child ownership to transfer. Such cursors now borrow the caller-owned graph, and scalar-only frames omit the otherwise-redundant arena reset at the back edge. Spectral norm N=5,500 returned from 10.95 seconds to a 4.639-second median, matching the pre-migration 4.683-second control with byte-identical output. Pointer-bearing consumed lists remain runtime-managed unless the traversal is proven inspect-only (see the n-body borrow below). The same rule removed Mandelbrot's duplicate packed-bitmap representation: N=16,000 peak RSS returned from 2,756,764 KB to 1,757,596 KB, within 0.23% of the 1,753,536 KB pre-migration control.
Lazy task-arena footers
Task-private arenas received a lazy-footer correction after their chunk-reclamation fix. Spawned handlers map a 4 MiB initial chunk; eagerly writing its footer touched the far page even when the handler used only its frame page, adding one recurring minor fault per connection. Reapers now derive the fixed first chunk from the task address, while genuinely grown chunks retain the common footer/previous-end chain. Minor faults for the 1,000-request diagnostic returned from 2,416 to the 1,215 pre-migration level, and three interleaved 50,000-request TCP runs matched the pre-migration throughput at concurrency 1, 8, and 64. A native minor-fault gate and an 8 MiB receive stress cover the short-task and grown-chunk paths.
TCO string exits in pidigits
The final standard-workload sweep found a scale-dependent TCO string-exit defect that small pidigits probes missed. Unreachable dummy stores after tail jumps obscured a returned-accumulator join, and its sibling exit concat retained stale arena provenance after late RC parameter promotion. Control-flow reachability now excludes those stores, derived exit concatenations adopt the managed regime, and runtime-managed ConcatStrTip consumes its predecessor uniformly across in-place and fallback paths. Standard N=10,000 is byte-identical and completes in 3.26 seconds.
Fresh-result helper inlining
Fresh-result helpers used directly as TCO successor arguments are now inlined into the back edge. This retains their aggregate inside the loop arena until the existing copy/reset boundary instead of normalizing it to RC at an intermediate helper return. Ownership-summary freshness is the gate, and capture expansion supplies any functions referenced by the inlined helper. Combined with local list-and-record reuse, n-body's N=5,000,000 diagnostic improved from 4.05–4.11 seconds to 3.62–3.72 seconds with byte-identical output and flat 8.2 MB peak RSS.
Borrowed record-list traversal in n-body
The remaining gap closed by borrowing the inspected acceleration graph. Profiling the saturated accel call located a defensive whole-graph deep copy at every entry: accel's others argument is allBodies, and because its Body element is a heap record the consumed-tail rule normalized the list — one 64-byte copy and one runtime-managed cons cell per element — even though accel only reads inline Float fields and returns a Float tuple. The borrowed-cursor rule now extends to pointer-bearing elements: a consumed-tail List(record) parameter whose recursive body only inspects the list (every bound head and tail is a match scrutinee or the same-position tail self-call argument, never returned, consed, stored, or passed in an owning position — proven by a structural escape analysis) and whose element is an all-inline-copy-field record is borrowed from the caller instead of normalized. This is the ordinary Perceus borrowed-vs-owned parameter distinction for a read-only traversal; owning traversals (updateVel/updatePos rebuild the list; energy hands its tail to potential) are excluded automatically, and the aliased allBodies read is preserved because a borrowed graph is never overwritten. n-body's N=5,000,000 diagnostic improved from 3.37 seconds to a 1.56-second median — below the roughly 2.00-second pre-migration control — with byte-identical output through the standard N=50,000,000 workload and a flat RSS slope. Regressions: ReuseTokenTests.Inspect_only_record_list_traversal_borrows_instead_of_normalizing and its escaping counterpart.
Ownership and lifetime corrections
Pointer-bearing TCO accumulator reuse
Arena in-place reuse of a TCO accumulator's ADT cell is now declined when the ADT carries runtime-managed (pointer-bearing) children. Such an accumulator's cell is arena-managed while its children are RC, so the back-edge deferred drop releases the previous value by re-reading THIS cell's fields — but an arena AllocReusing had already overwritten them with the new children, freeing the live new children (a child rebuilt from a shared tail, value :: rest, lost cells across iterations). Keeping the old cell intact by rebuilding fresh lets the deferred drop release the real old value; the runtime-managed reuse path, which manages its children explicitly, is unaffected. The extra per-iteration cell is bounded (the deferred drop reclaims it). Regression: EndToEndNativeBackendTests.Tco_adt_with_shared_tail_list_children_survives_across_iterations and the native tests/runtime_rc_tco_positional_adt_children.ash.
Borrows transported through local slots
The lifetime placement now follows an owner's borrow through a local slot. The conditional runtime-argument retain (EmitConditionallyRetainedRuntimeArgument, used when a non-fresh runtime-managed value is passed to a closure that may adopt it) stores the borrowed owner into a fresh slot and reloads it for the call, so the drop-placement alias walk — which followed Borrow but not StoreLocal/LoadLocal — lost the borrow and placed the owner's drop before the call: a use-after-free that segfaulted or corrupted every JSON keyword/literal parse (Ashes.Text.Json.parse and hand-written string parsers). CollectOwnerAliases now also follows an alias through any slot it is stored into and reloaded from, to a fixpoint. This only lengthens liveness (the drop lands after the last real use, never earlier), so it cannot introduce a premature free. Regression: EndToEndNativeBackendTests.Runtime_managed_string_passed_through_identity_then_consuming_call_is_not_freed plus the recovered tests/stdlib_json.ash and tests/namespace_nested_modules.ash.
Borrows captured by closures
The same alias walk now also follows an owner captured into a closure. A runtime-managed value borrowed into a transient closure's arena/stack environment (StoreMemOffset of a borrow into an env pointer, then MakeClosure/MakeClosureStack), or into a curried partial application (CallClosure(f, x) whose result is itself applied again), must stay live until that closure is APPLIED — the borrow lives in the env until then. Previously the drop landed right after the capture, before the application read the value back: benign for a string recycled on the free list but a use-after-free (segfault) for one larger than the 4 KiB RC cache, whose independent mmap the drop munmaps. CollectOwnerAliases now follows an alias through a closure env and through a partial-application result, so the owner's drop lands after the closure's application. Recovers tests/regex_large_subject_chain.ash (chained Ashes.Text.Regex.replace over a >4 KiB subject — the subject was freed before the substitute read it). Regression: EndToEndNativeBackendTests.Large_runtime_managed_string_captured_into_closure_survives_until_applied.
TCO string accumulators returned in tuples
A TCO loop's string accumulator returned inside a tuple is now copied out of the reused arena. A tail-recursive parser step such as readWord acc text = ... | Some((h, t)) -> if h == " " then (acc, t) else readWord(acc + h)(t) returns its String accumulator (and the match-bound suffix tail) in a tuple. Both live in the callee's arena, which the loop resets in place on every back-edge; a directly-returned String is copied out at the return boundary, but a String nested in a tuple field was not, so a second call reusing the same arena overwrote the first call's word (value=value instead of name=value). MaterializeEscapingStringTupleElement now copies such a field out to an independent RC string — but only inside a TCO loop (_tcoCtx set), only for a bare variable with no RC ownership of its own (an already-owned value like let text = fromInt(42) in (text, 2) stays arena-managed, preserving the borrowed-pointer-tuple contract), and skipping any element the ownership system already keeps alive. Because inference is interleaved with lowering the accumulator's element type is often an unresolved type variable at this point (indistinguishable from a scalar accumulator's), so the copy-out is emitted provisionally with a DeferredElementType and a post-inference pass (ResolveDeferredTupleMaterializations) keeps it when the type resolved to Str or rewrites it to a plain Borrow alias when it resolved to a scalar — a scalar field is never byte-copied as a length-prefixed string. The same hazard when the tuple is wrapped in an ADT constructor (Ok((acc, tail)), which every hand-written parser's parseStringBody returns) is handled by recursing ProducesFreshTuple into constructor arguments so the tuple flag is set through the wrapper. Recovers tests/text_json_parser_smoke.ash (a hand-written JSON parser whose object keys and member suffixes were both corrupted). Regressions: EndToEndNativeBackendTests.Tco_loop_string_accumulator_returned_in_tuple_survives_next_call, its _adt_wrapped_tuple_ counterpart, and Tco_loop_int_accumulator_returned_in_tuple_is_not_corrupted_as_string.
Heap-bearing product shells across TCO back edges
Arena in-place reuse of a TCO-parameter ADT cell is now declined for any ADT with a heap child. A tail-recursive loop that destructures and rebuilds a single-constructor product around its back edge (fannkuch-redux's nextPerm rebuilding S(perm, count)) had its product shell rebuilt with an arena AllocReusing reusing the destructured cell; the back-edge RestoreArenaState then freed that shell before it became the next iteration's parameter — a use-after-free (segfault, or a corrupt count read returning a premature result). The reuse-decline gate now fires whenever a matched constructor has a field that is not an inline copy scalar (List/String/Bytes/BigInt/Tuple/nested ADT): such a child is RC-normalized at runtime even when the ADT is flat-copy-out-able (S(List(Int))'s Int-element list still becomes an RC list), so the arena shell cannot survive the reset. This supersedes the earlier narrower !CanCopyOutAdt gate, which missed the copy-out-able-but-heap-bearing case. The constructor is read from the match pattern, since the scrutinee's inferred type is often still an unresolved type variable at the reuse decision. Recovers challenges/fannkuch-redux (hung at N=3, segfaulted at N≥4 at every optimization level). Regression: EndToEndNativeBackendTests.Tco_positional_product_with_list_child_survives_back_edge_reset.
Self-recursive ADT representation consistency
A later full-suite challenge rerun (long after the phases above shipped and every exit gate was green) found binary-trees regressed from 192 MB to 7.3 GB peak RSS at N=21 and fannkuch-redux from 0.2 MB to 47 GB at N=11 — both previously-clean benchmarks, on a build with 0/0 failing tests. Root cause (binary-trees): ProducesFreshRuntimeManageableAdt (used by LowerEscapingResult to decide whether a function's returned ADT should be promoted from the arena to an RC cell so it survives the callee's own arena reset) recurses through a function body's if/match arms and treats the whole expression as "escaping-fresh" if any arm independently satisfies IsFreshRuntimeManageableAdtExpression — sound for a tail-recursive funnel (an arm that fails the check but is itself a self-call eventually reaches the same fresh arm), but unsound for a genuinely branching self-recursive ADT: binary-trees' make depth = if depth == 0 then Leaf else Node(make(depth - 1))(make(depth - 1)) has a trivially "fresh" nullary base case (Leaf, no fields to check) on one arm and a recursive case whose fields are ordinary calls — not nested constructor literals — on the other, so Node independently fails freshness. The OR let Leaf's triviality alone flag the function, promoting every Leaf cell to RC while every Node cell stayed arena. An arena cell's drop is a no-op (arena reclamation is scope-exit watermark reset, not per-cell), so it never walks into RC-managed children — every Leaf reachable through a tree discarded by the arena reset leaked its RC cell forever (check(make(depth)) in a loop leaks 2^depth RC cells per iteration). Fix: ProducesFreshRuntimeManageableAdt now collects every terminal arm reachable through the same if/match/let traversal and, for each candidate "fresh" arm, requires that no other arm constructing the same parent type fails freshness independently (a funneling self-call arm, which builds nothing, never conflicts) — so Leaf and Node are now uniformly arena-managed, both reclaimed by the ordinary watermark reset. Verified via a minimal repro (let t = make(14) in loop(...), an otherwise-unused binding inside a TCO loop) that went from 57 GB to 512 KB at 200,000 iterations, and the full benchmark: binary-trees N=21 back to 1.51 s / 196 MB (matching the 1.41 s / 192 MB pre-migration control). Regression: OwnershipTests.Self_recursive_adt_nullary_and_recursive_arms_share_runtime_managed_flag (asserts every AllocAdt for a shared self-recursive type carries the same RuntimeManaged flag) and tests/ownership_self_recursive_adt_build_discard.ash.
TCO pattern-alias retention
The initial free-list diagnosis was incomplete. A deterministic list-of-tuples reproducer and a complete size-32 heap census showed that the allocator did pop and recycle released blocks: after one iteration, 12 of 16 allocations were back on the bin. The four absent blocks were still-live list head values, not released blocks lost by the allocator. Two TCO alias paths retained them:
- a pattern alias whose runtime-RC placement was already known and handled by
_runtimeManagedTcoPatternAliasescould also receive the laterc_tco_nested_alias_duplicatedfixup, adding a second reference for the same transfer; LowerCallTcoTransferPatternAliasescounted every appearance inside a back-edge argument as an ownership transfer, including a bare argument to an ordinary qualified call such asAshes.Text.byteLength, even though that call only borrows it.
The extra reference made the eventual structural drop observe a shared child and stop after decrementing it, retaining the child graph forever. Late fixup now skips an alias slot already covered by the ordinary path, and the ordinary path subtracts borrow-only plain and qualified call uses before emitting transfer dups. The shared runtime free-list code is unchanged. Regressions: NestedTcoPatternAliasTests.Early_resolved_direct_alias_is_not_also_protected_by_the_late_fixup, Qualified_inspection_of_a_direct_alias_does_not_transfer_ownership, and the restored strict plateau gate in Linux_backend_llvm_runtime_rc_owned_head_list_TCO_memory_should_plateau. The real challenge gate is restored: fannkuch-redux N=9, N=10, and N=11 produce 8629 / 30, 73196 / 38, and 556355 / 51 respectively at a flat 8.2 MB peak RSS on the validation host.
Current scope and deliberate exclusions
The paper comparison found no unresolved blocker inside the declared Ashes memory model. The scope is intentionally hybrid:
- ordinary escaping acyclic graphs use RC Perceus ownership;
- proven non-escaping scratch may use scoped arenas;
- task/capability state remains scheduler-region-owned because suspension is non-linear;
- RC counts are thread-local, so worker publication uses independent copies until
tsharemarking or an atomic transition exists; - borrowed mmap-backed
Bytesviews remain tied to their mapping/resource; - persistent
Map/HashMapreuse retains a measured specialized region; - language resources keep affine
CleanupResource, separate from ordinary RC; - cyclic graphs require future cycle handling and are not admitted to RC.
These are named IR boundaries with bounded-memory regressions, not implicit fallbacks. Consequently Ashes claims the Perceus ownership invariant for admitted RC graphs, not that every byte of mixed runtime state is governed by the paper's formal calculus.
Runtime string interning remains rejected. The original arena-only design could neither retain dynamic entries safely nor reclaim a permanent intern table. RC Perceus removes the first obstacle, but a strong table reference would still keep every distinct dynamic string alive. A bounded implementation now requires weak table entries or eviction, removal synchronization, and a workload demonstrating that the lookup cost wins back enough allocation. Ashes therefore still interns only the finite, compile-time-known literal set. This is a performance decision, not a claim that reference counting is unavailable.