feat(codegen): promote top-level bindings to chunk locals under a two-tier storage budget#246
Merged
Merged
Conversation
…pvalues) Extract the hard per-function limits of the target Lua VM (200 locals, 60 upvalues for the 5.1 floor) from named constants in Lua.Localize into a LuaLimits record (Language.PureScript.Backend.Lua.Limits), threaded from the CLI through Backend.compileModules and Lua.Optimizer.optimizeChunk into the storage passes. Other Lua targets raise these limits (5.2+ allows 255 upvalues), so the budgets the passes enforce must be configurable rather than baked in. The config surface carries the hard target limits; the working ceilings the passes budget against (hard limit minus headroom, 180/55 by default) remain derived, pass-side logic. Defaults reproduce the previous output byte for byte: the golden corpus is unchanged. Part of #174 (stage 2 groundwork).
Red against the skeleton (13 examples, 8 failures): promotion to chunk locals, self-recursive/mutually-recursive pre-declaration, the locals and upvalue budgets, name-collision decline, and the module-table stability precondition all fail against the identity placeholder; the two limits-driven end-to-end eval cases pass trivially (M always survives when the pass is a no-op).
…-tier storage budget (#174) M.foo = e becomes local foo = e for bindings that are read at least once, ranked by static read count and promoted while the chunk's locals budget allows (Localize.hs's workingLocalCeiling). A bottom-up upvalue-demand accounting per function proto (own outer-local references unioned with children's pass-through demand) demotes individual field references back to M.x — mirroring the binding into M so demoted reads still find it — whenever a proto would exceed the upvalue ceiling, cheapest reads first. Self-recursive and mutually recursive forward references are pre-declared. Every budget overflow degrades to exactly today's M-only form, so the target's per-function limits (#19) stay handled by construction; a chunk that fits the budgets loses the M table entirely. Runs before stage 1's per-function field caching in optimizeChunk, so that pass now only ever caches the M traffic promotion left behind. Localize.hs exports its stability precondition (moduleTableStable) and name collector (namesInBlock) for reuse. ADR 0001 updated from "planned" to record the implemented design.
#174) 50 of the corpus's 62 modules move: promoted bindings print as chunk locals, and 35 of them drop the M table entirely once every read is a local/upvalue access. Where M survives it holds only fields that are written but never read within the chunk, or, for FieldCaching/UncurriedLift/Uncurry, cases exercising stage 1's own caching on the residual M traffic. The unread fields are a golden-harness artifact: compileCorefn always IR-links a module AsModule, rooting DCE at every export, even when that module is Lua-linked AsApplication for its eval check, so a derived instance like DerivedFunctor.Test's functorEither survives as an export after its one call site gets constant-folded away. A production AsApplication build roots DCE at the entry point instead and would prune these before Lua codegen sees them. All 31 eval oracles are byte-identical (never auto-accepted).
Contributor
There was a problem hiding this comment.
Pull request overview
This PR implements issue #174 stage 2 by adding a Lua-level optimization pass which promotes frequently-read top-level M.x bindings into chunk locals (with budget-aware fallback to the existing module-table representation), wires target Lua VM limits through the pipeline/CLI, and updates specs + goldens accordingly.
Changes:
- Add
Lua.Promotetwo-tier storage pass and run it before stage-1Lua.Localizecaching inoptimizeChunk. - Introduce
LuaLimits(defaults to Lua 5.1) and thread limits through CLI, backend, optimizer, and golden/spec harnesses. - Update ADR/changelog and regenerate structural golden Lua outputs to reflect the new storage scheme.
Reviewed changes
Copilot reviewed 60 out of 64 changed files in this pull request and generated 1 comment.
Show a summary per file
| File | Description |
|---|---|
lib/Language/PureScript/Backend/Lua/Promote.hs |
New stage-2 promotion pass (chunk locals + budget-aware demotion/mirroring). |
lib/Language/PureScript/Backend/Lua/Limits.hs |
New LuaLimits type and derived working ceilings for budgeting. |
lib/Language/PureScript/Backend/Lua/Optimizer.hs |
Run promotion before localization; optimizeChunk now takes LuaLimits. |
lib/Language/PureScript/Backend/Lua/Localize.hs |
Budget stage-1 caching against LuaLimits; export shared stability/name utilities. |
lib/Language/PureScript/Backend.hs |
Thread LuaLimits into compileModules and optimizeChunk. |
exe/Cli.hs |
Add --max-locals / --max-upvalues and construct LuaLimits. |
exe/Main.hs |
Pass parsed luaLimits into Backend.compileModules. |
pslua.cabal |
Expose new Lua.Limits/Lua.Promote modules; include new spec module. |
test/Main.hs |
Register the new Lua.Promote spec suite. |
test/Language/PureScript/Backend/Lua/Promote/Spec.hs |
New unit + end-to-end tests for promotion/demotion/limits behavior. |
test/Language/PureScript/Backend/Lua/Localize/Spec.hs |
Update to call localizeChunk with lua51Limits. |
test/Language/PureScript/Backend/Lua/Golden/Spec.hs |
Thread lua51Limits into golden compilation and optimizeChunk. |
docs/adr/0001-top-level-binding-storage.md |
Update ADR to reflect that stage 2 is implemented and document details. |
changelog.d/20260712_110000_unisay_two_tier_storage.md |
Changelog fragment documenting two-tier storage promotion behavior. |
test/ps/output/Golden.Uncurry.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.UncurriedLift.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Unbinding.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.TestReturnTableField/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.TailRecM2Shadow.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.StringEscapes.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.RecordsUpdate.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.RecordsAccess.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.RecGroupOrder.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.RecDataDefs.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.ProfunctorDictLens.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Primops.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.PatternMatching.Test2/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Newtype.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Nested.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.NameShadowing.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.MaybeChainModule.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.MaybeChain.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Loopification.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.LongReaderBind.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.LongEitherBind.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.LongDoBlock.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.LongBindFlipped.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.LongApplyChain.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Issue37.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Inline.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.HelloPrelude.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.GenericEqTwoTypes.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.ForeignSharing.Token/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.ForeignSharing.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Foreign.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Foreign.Lib/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.FloatIn.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.FieldCaching.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Fibonacci.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.DerivedFunctor.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.CharLiterals.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.BugListGenericEq.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.ArrayPatternMatch.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.ArrayOfUnits.Test/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Annotations.M2/golden.lua |
Golden Lua updated for chunk-local promotion. |
test/ps/output/Golden.Annotations.M1/golden.lua |
Golden Lua updated for chunk-local promotion. |
… promotion (#174) Dropping the M table line and promoting bindings to chunk locals moves the generated code up by one or two lines, relocating every FNEW site and bytecode end-state entry in the LuaJIT counter reports. The semantic counters are untouched: total FNEW and prototype counts, abort reasons, and compiled/blacklisted tallies are identical; trace_curried_step does not move at all.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Closes #174.
What
Every top-level binding currently lives in the module-scope table
M, so every inter-binding reference is a hash lookup. This addsLanguage.PureScript.Backend.Lua.Promote, a Lua-level pass that promotes the bindings actually worth it to real chunk locals:M.foo = ebecomeslocal foo = e, and reads become local/upvalue accesses.M.x = estatement, is read at least once, and its name isn't used as a variable anywhere else in the chunk (a name collision, which only hand-written FFI produces, declines rather than renames). Qualifying bindings are promoted in descending static read count while the chunk's locals budget allows.demand(f) = ownOuterRefs(f) ∪ children's pass-through demand), lexically resolved. When a proto would exceed the upvalue ceiling, promoted-field references inside it demote back toM.x, cheapest reads first, and the binding is mirrored intoM(M.x = xright afterlocal x = e) so the demoted reads still find it.M-only form, so the target's per-function limits (Function at line XXX has more than NNN upvalues #19) stay handled by construction rather than by assuming programs stay small.Promotion runs before the existing stage-1 per-function field caching (
Language.PureScript.Backend.Lua.Localize) inoptimizeChunk, so that pass now only ever caches whateverMtraffic promotion left behind. ADR 0001 is updated from "stage 2 planned" to record the implemented design.Red → green
The spec commit lands first against the existing identity-placeholder skeleton: 13 examples, 8 failures (promotion, pre-declaration, both budgets, the collision decline, and the stability precondition all red; the two limits-driven end-to-end eval cases pass trivially since
Malways survives a no-op). The feat commit turns all 13 green.Corpus
50 of the corpus's 62 golden modules move; 35 of those drop the
Mtable entirely once every read in the chunk is a local/upvalue access. Net -39 lines. WhereMsurvives, it's either the budget-pressure cases (FieldCaching,UncurriedLift,Uncurry) exercising stage 1's own caching on the residual traffic, or a genuine zero-read field, which is a golden-harness artifact rather than a production one:compileCorefnalways IR-links a moduleAsModule, rooting DCE at every export, even when that module is Lua-linkedAsApplicationfor its eval check.DerivedFunctor.Test'sfunctorEitherdictionary survives IR-level DCE as an export even after the one call site that used it gets constant-folded away, so it reaches Lua codegen with no readers left; promotion correctly leaves a zero-read field inMrather than spending a local slot on a dead store. A productionAsApplicationbuild roots IR-level DCE at the entry point instead and would prune these before Lua codegen ever sees them. All 31 eval oracles are byte-identical (never auto-accepted), andluacheckis clean under the same flags the test suite uses.