Skip to content

feat(codegen): promote top-level bindings to chunk locals under a two-tier storage budget#246

Merged
Unisay merged 5 commits into
mainfrom
issue-174/stage2-two-tier-storage
Jul 12, 2026
Merged

feat(codegen): promote top-level bindings to chunk locals under a two-tier storage budget#246
Unisay merged 5 commits into
mainfrom
issue-174/stage2-two-tier-storage

Conversation

@Unisay

@Unisay Unisay commented Jul 12, 2026

Copy link
Copy Markdown
Collaborator

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 adds Language.PureScript.Backend.Lua.Promote, a Lua-level pass that promotes the bindings actually worth it to real chunk locals: M.foo = e becomes local foo = e, and reads become local/upvalue accesses.

  • Selection: a binding qualifies when its field is written by exactly one top-level M.x = e statement, 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.
  • Upvalue accounting: the pass computes every function proto's upvalue demand bottom-up (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 to M.x, cheapest reads first, and the binding is mirrored into M (M.x = x right after local x = e) so the demoted reads still find it.
  • Recursion: a binding read before its own initializer (self-recursion, or an earlier member of a mutually recursive group) is pre-declared and initialized by plain assignment instead.
  • Budgets are pure degradation: every overflow, whether locals, upvalues, or a name collision, falls back to exactly today's 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) in optimizeChunk, so that pass now only ever caches whatever M traffic 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 M always 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 M table entirely once every read in the chunk is a local/upvalue access. Net -39 lines. Where M survives, 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: compileCorefn always IR-links a module AsModule, rooting DCE at every export, even when that module is Lua-linked AsApplication for its eval check. DerivedFunctor.Test's functorEither dictionary 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 in M rather than spending a local slot on a dead store. A production AsApplication build 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), and luacheck is clean under the same flags the test suite uses.

Unisay added 4 commits July 12, 2026 10:40
…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).
@Unisay Unisay requested a review from Copilot July 12, 2026 09:36
@Unisay Unisay marked this pull request as ready for review July 12, 2026 09:37

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.Promote two-tier storage pass and run it before stage-1 Lua.Localize caching in optimizeChunk.
  • 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.

Comment thread lib/Language/PureScript/Backend/Lua/Promote.hs
… 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.
@Unisay Unisay merged commit cd164cb into main Jul 12, 2026
2 checks passed
@Unisay Unisay deleted the issue-174/stage2-two-tier-storage branch July 12, 2026 11:29
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Revisit M-table binding storage: per-function caching and budget-aware chunk locals

2 participants