purescript-lua · Unisay · Jul 12, 2026 · Jul 11, 2026 · Jul 12, 2026 · Jul 12, 2026
diff --git a/bench/goldens/fnew_Bench.ArrayFoldl.txt b/bench/goldens/fnew_Bench.ArrayFoldl.txt
@@ -5,10 +5,10 @@ function-body FNEW: 9
 total FNEW: 14
 prototypes: 15
 function-body FNEW sites:
-  Bench.ArrayFoldl.lua:11
   Bench.ArrayFoldl.lua:10
-  Bench.ArrayFoldl.lua:21
+  Bench.ArrayFoldl.lua:9
   Bench.ArrayFoldl.lua:20
+  Bench.ArrayFoldl.lua:19
   Bench.ArrayFoldl.lua:44
   Bench.ArrayFoldl.lua:43
   Bench.ArrayFoldl.lua:42

diff --git a/bench/goldens/fnew_Bench.BindChain.txt b/bench/goldens/fnew_Bench.BindChain.txt
@@ -5,5 +5,5 @@ function-body FNEW: 2
 total FNEW: 6
 prototypes: 7
 function-body FNEW sites:
-  Bench.BindChain.lua:23
   Bench.BindChain.lua:22
+  Bench.BindChain.lua:21
diff --git a/bench/goldens/trace_array_foldl.txt b/bench/goldens/trace_array_foldl.txt
@@ -4,8 +4,8 @@ workload: n=5000000 reps=2 result=12500002500000
 aborts (distinct site -- reason):
   Bench.ArrayFoldl.lua:50 -- NYI: bytecode FNEW
 bytecode end state (J*=compiled, I*=blacklisted):
-  Bench.ArrayFoldl.lua:18 IFORL
-  Bench.ArrayFoldl.lua:29 JLOOP
+  Bench.ArrayFoldl.lua:17 IFORL
+  Bench.ArrayFoldl.lua:28 JLOOP
   Bench.ArrayFoldl.lua:49 IFUNCF
   Bench.ArrayFoldl.lua:50 JFUNCF
   array_foldl.lua:13 JFORI

diff --git a/bench/goldens/trace_bind_chain.txt b/bench/goldens/trace_bind_chain.txt
@@ -2,14 +2,14 @@ spec: bind_chain
 runtime: LuaJIT 2.1.1741730670
 workload: n=1000000 reps=2 result=3000000
 aborts (distinct site -- reason):
+  Bench.BindChain.lua:21 -- NYI: bytecode FNEW
   Bench.BindChain.lua:22 -- NYI: bytecode FNEW
-  Bench.BindChain.lua:23 -- NYI: bytecode FNEW
 bytecode end state (J*=compiled, I*=blacklisted):
-  Bench.BindChain.lua:14 JFUNCF
+  Bench.BindChain.lua:1 JFUNCF
+  Bench.BindChain.lua:13 JFUNCF
+  Bench.BindChain.lua:17 IFUNCF
   Bench.BindChain.lua:18 IFUNCF
-  Bench.BindChain.lua:19 IFUNCF
-  Bench.BindChain.lua:2 JFUNCF
-  Bench.BindChain.lua:5 JFUNCF
+  Bench.BindChain.lua:4 JFUNCF
   bind_chain.lua:10 IFORL
   bind_chain.lua:17 JFORI
   bind_chain.lua:17 JFORL

diff --git a/bench/goldens/trace_fibonacci.txt b/bench/goldens/trace_fibonacci.txt
@@ -5,7 +5,7 @@ aborts (distinct site -- reason):
   Bench.Fib.lua:5 -- call unroll limit reached
   fibonacci.lua:11 -- call unroll limit reached
 bytecode end state (J*=compiled, I*=blacklisted):
-  Bench.Fib.lua:2 JFUNCF
+  Bench.Fib.lua:1 JFUNCF
   Bench.Fib.lua:5 JFUNCF
   fibonacci.lua:11 JFUNCF
 counts: aborts=2 compiled=3 blacklisted=0
diff --git a/changelog.d/20260712_110000_unisay_two_tier_storage.md b/changelog.d/20260712_110000_unisay_two_tier_storage.md
@@ -0,0 +1,14 @@
+### Changed
+
+- Top-level bindings the linked program actually reads are now promoted to
+  real Lua chunk locals instead of living exclusively in the module-scope
+  table `M` (#174 stage 2, `Language.PureScript.Backend.Lua.Promote`).
+  Bindings are ranked by static read count and promoted while a locals
+  budget allows; a bottom-up upvalue accounting per function proto demotes
+  individual references back to `M.x` (mirroring the binding into `M`) when
+  a function would otherwise exceed the target's upvalue limit, so the
+  worst case is exactly today's `M`-only output. A program whose bindings
+  and references all fit the budgets emits no `M` table at all. Runs before
+  the existing per-function field caching (#174 stage 1), so that pass now
+  only ever caches the residual `M` traffic. Structural goldens churn
+  mechanically; eval goldens are unchanged.
diff --git a/docs/adr/0001-top-level-binding-storage.md b/docs/adr/0001-top-level-binding-storage.md
@@ -4,9 +4,9 @@ Date: 2026-07-07
 
 ## Status
 
-Accepted. Stage 1 (per-function field caching) is implemented; stage 2
-(budget-aware two-tier storage) is designed here and tracked in issue
-[#174].
+Accepted. Both stages of issue [#174] are implemented: stage 1
+(per-function field caching, `Lua.Localize`) and stage 2 (budget-aware
+two-tier storage, `Lua.Promote`).
 
 [#174]: https://github.com/purescript-lua/purescript-lua/issues/174
 
@@ -111,28 +111,64 @@ guides. The details that keep it sound and limit-proof:
   shadowing declarations (shapes only hand-written FFI could produce).
   Otherwise the chunk is left byte-identical.
 
-### Stage 2: two-tier storage with budget accounting (planned)
-
-Top-K bindings by static reference count are emitted as real chunk
-locals; the tail stays in `M`; exported bindings are mirrored into the
-export surface. Two budgets are computed over the finished Lua AST
-before printing:
-
-1. **Locals**: a chunk-local counter with a ceiling of ~180 (200 minus
-   fixture locals and headroom). Overflow keeps the binding in `M`.
-2. **Upvalues**: the killer of the pre-#19 design. Accounting runs
-   bottom-up over the function tree:
-   `upvals(f) = |own outer-local references ∪ children's pass-through
-   demands|`. When a function proto would exceed ~55, individual
-   references are demoted — printed as `M.x` — while the binding stays
-   a local for everyone else.
-
-A program that fits the budgets (like `Data.Array` with 124 bindings)
-loses the `M` table entirely: pure locals, with the module export
-table referencing them directly. `K` for larger programs is chosen
-from #172's measurements. Stage 2 lands only with that measurement
-backing; until then stage 1's caching already removes the per-loop and
-per-call read cost where it matters.
+### Stage 2: two-tier storage with budget accounting (implemented)
+
+A Lua-level pass (`Language.PureScript.Backend.Lua.Promote`, run from
+`optimizeChunk` *before* stage 1) promotes top-level bindings to real
+chunk locals; the tail stays in `M`:
+
+```lua
+local Data_Array_index = function(arr) … end
+local Data_Array_span = function(p, arr)
+  local v = Data_Array_index(arr)(i)
+  …
+return { span = Data_Array_span, … }
+```
+
+- **Selection (the locals budget).** A binding qualifies when its
+  field is initialized by exactly one top-level `M.x = e` statement,
+  is read at least once, and its name is not used as a variable
+  anywhere in the chunk — the promoted local keeps the field's name,
+  and on a collision (a shape only hand-written FFI produces) the pass
+  declines rather than renames. Qualifying bindings are promoted in
+  descending static read count while the chunk's local slots —
+  pre-existing declarations plus one per promotion — stay under the
+  locals ceiling; the original "top-K" knob from the issue *is* this
+  budget bound. Zero-read bindings stay in `M`: a local for a binding
+  nobody reads spends a scarce slot on a dead store.
+- **Upvalue accounting (the demotion budget).** The killer of the
+  pre-#19 design was pass-through accumulation, so the pass computes
+  every function proto's upvalue demand bottom-up:
+  `demand(f) = ownOuterRefs(f) ∪ {b ∈ demand(child) | b not bound by
+  f}`, counting *all* outer-local references (function locals and
+  parameters included), resolved lexically — a name referenced before
+  its declaration resolves outside it. When a proto's demand exceeds
+  the upvalue ceiling, promoted-binding references within its subtree
+  are demoted — printed as `M.x` again — cheapest reads first (ties to
+  the earlier-declared binding), and the binding is mirrored into the
+  table (`M.x = x` right after `local x = e`) so demoted reads still
+  observe it. Demoting swaps the binding's upvalue for `M`'s, so the
+  first demotion pays off only once `M` is already demanded; the
+  fitting loop accounts for that. The binding stays a local for every
+  proto that affords it.
+- **Recursion.** A binding read before its initializer — the
+  self-reference of a recursive function, or an earlier member of a
+  mutually recursive group — is pre-declared (`local x` before the
+  first referencing statement) and initialized by plain assignment;
+  only the forward-referenced group members are pre-declared.
+- **Preconditions.** Stage 1's chunk-wide stability precondition,
+  plus: the module table is declared exactly once, as `local M = {}`,
+  before any other occurrence of the name. Otherwise the chunk is left
+  byte-identical.
+- **Ordering.** Promotion runs before stage-1 caching: whatever stays
+  in `M` after promotion — the unpromoted tail plus demoted
+  references — is exactly what per-function caching still speeds up.
+
+A program that fits the budgets loses the `M` table entirely: pure
+locals, with the module export table referencing them directly. In the
+golden corpus 35 of 50 modules drop `M`; the rest keep it only to hold
+bindings that are written but never read (dead stores the IR-level DCE
+did not see).
 
 ## Rejected alternatives
 
@@ -146,13 +182,21 @@ per-call read cost where it matters.
 
 ## Consequences
 
-- Generated functions gain an entry `local … = M.…` statement when
-  they read fields repeatedly; goldens churn mechanically but runtime
+- In-budget programs emit no `M` table at all: inter-binding
+  references are upvalue/register accesses, and the export table
+  references the locals directly. Where a binding stays in `M`,
+  generated functions still gain stage-1 entry caches (`local … =
+  M.…`) for repeated reads; goldens churn mechanically but runtime
   behavior is unchanged (eval goldens are the check).
 - Hot loops produced by loopification (#181) read loop-invariant
   bindings from locals, which LuaJIT hoists into registers; the win
   compounds with uncurrying (#24) as real loops become traceable.
-- The `M` table remains the single upvalue of every generated closure
-  until stage 2; nothing about FFI, linking, or DCE changes.
-- The budgets live in `Localize.hs` as named constants; stage 2 reuses
-  the same ceilings for its chunk-level accounting.
+- Nothing about FFI, linking, or DCE changes. A binding that is
+  written but never read keeps `M` alive for the whole chunk;
+  eliminating such dead init stores would be a separate, Lua-level
+  DCE concern.
+- The hard target limits live in
+  `Language.PureScript.Backend.Lua.Limits` as a `LuaLimits` record,
+  configurable per target (`--max-locals` / `--max-upvalues`, Lua 5.1
+  defaults); both passes budget against working ceilings derived from
+  them (hard limit minus headroom, 180/55 by default).
diff --git a/exe/Cli.hs b/exe/Cli.hs
@@ -7,10 +7,12 @@ import Data.List.NonEmpty qualified as NE
 import Data.Tagged (Tagged (..))
 import Data.Text (splitOn)
 import Data.Text qualified as Text
+import Language.PureScript.Backend.Lua.Limits (LuaLimits (..), lua51Limits)
 import Language.PureScript.Backend.Types (AppOrModule (..))
 import Language.PureScript.Names qualified as PS
 import Options.Applicative
   ( Parser
+  , ReadM
   , eitherReader
   , execParser
   , flag
@@ -47,6 +49,7 @@ data Args = Args
   , outputIR ∷ Maybe ExtraOutput
   , outputLuaAst ∷ Maybe ExtraOutput
   , lintIR ∷ Tagged "lint-ir" Bool
+  , luaLimits ∷ LuaLimits
   , appOrModule ∷ AppOrModule
   , runEntry ∷ Maybe AppOrModule
   }
@@ -117,6 +120,30 @@ options = do
             <> linebreak
             <> bold "Default: false"
       ]
+  targetMaxLocals ←
+    option positiveInt . fold $
+      [ metavar "N"
+      , long "max-locals"
+      , value (maxLocals lua51Limits)
+      , helpDoc . Just $
+          "Target Lua VM's hard limit on local variables"
+            <> softbreak
+            <> "per function (LUAI_MAXVARS)."
+            <> linebreak
+            <> bold "Default: 200 (Lua 5.1)"
+      ]
+  targetMaxUpvalues ←
+    option positiveInt . fold $
+      [ metavar "N"
+      , long "max-upvalues"
+      , value (maxUpvalues lua51Limits)
+      , helpDoc . Just $
+          "Target Lua VM's hard limit on upvalues"
+            <> softbreak
+            <> "per function (LUAI_MAXUPVALUES)."
+            <> linebreak
+            <> bold "Default: 60 (Lua 5.1)"
+      ]
   appOrModule ←
     option (eitherReader parseAppOrModule) . fold $
       [ metavar "ENTRY"
@@ -150,7 +177,20 @@ options = do
             , green $ indent 2 "Example: Acme.App.main"
             ]
       ]
-  pure Args {..}
+  pure
+    Args
+      { luaLimits =
+          LuaLimits
+            { maxLocals = targetMaxLocals
+            , maxUpvalues = targetMaxUpvalues
+            }
+      , ..
+      }
+
+positiveInt ∷ ReadM Int
+positiveInt = eitherReader \s → case readMaybe s of
+  Just n | n > 0 → Right n
+  _ → Left ("expected a positive integer, got: " <> s)
 
 {- | `--run` must name an application entry point (`<Module>.<binding>`): there
 is nothing to execute without a binding, so a bare module name is rejected.

diff --git a/exe/Main.hs b/exe/Main.hs
@@ -33,6 +33,7 @@ main = Utf8.withUtf8 do
     , outputIR
     , outputLuaAst
     , lintIR
+    , luaLimits
     , psOutputPath
     , appOrModule
     , runEntry
@@ -56,7 +57,7 @@ main = Utf8.withUtf8 do
     -- Stay silent in run mode so the program's own stdout isn't polluted (the
     -- output may be piped); Spago already logs the run/build phases itself.
     when (isNothing runEntry) $ putTextLn "PS Lua: compiling ..."
-    Backend.compileModules psOutputPath foreignDir lintIR entry
+    Backend.compileModules psOutputPath foreignDir lintIR luaLimits entry
       & handleModuleNotFoundError
       & handleModuleDecodingError
       & handleCoreFnError

diff --git a/lib/Language/PureScript/Backend.hs b/lib/Language/PureScript/Backend.hs
@@ -13,6 +13,7 @@ import Language.PureScript.Backend.IR.Optimizer
 import Language.PureScript.Backend.IR.Pass (PassCheckFailure)
 import Language.PureScript.Backend.Lua qualified as Lua
 import Language.PureScript.Backend.Lua.ForeignLift qualified as ForeignLift
+import Language.PureScript.Backend.Lua.Limits (LuaLimits)
 import Language.PureScript.Backend.Lua.NestingCheck (exceedsNestingLimit)
 import Language.PureScript.Backend.Lua.Optimizer (optimizeChunk)
 import Language.PureScript.Backend.Lua.Types qualified as Lua
@@ -38,9 +39,10 @@ compileModules
   ⇒ Tagged "output" (SomeBase Dir)
   → Tagged "foreign" (Path Abs Dir)
   → Tagged "lint-ir" Bool
+  → LuaLimits
   → AppOrModule
   → ExceptT (Variant e) IO CompilationResult
-compileModules outputDir foreignDir lintIR appOrModule = do
+compileModules outputDir foreignDir lintIR limits appOrModule = do
   let entryModuleName = entryPointModule appOrModule
   cfnModules ← CoreFn.readModuleRecursively outputDir entryModuleName
   let dataDecls = IR.collectDataDeclarations cfnModules
@@ -64,7 +66,7 @@ compileModules outputDir foreignDir lintIR appOrModule = do
   -- took over). The unfinished module is parked on the 'lua-dce-wip' branch;
   -- its known defects are documented there in
   -- Note [Graph-based dead code elimination for Lua].
-  let optimizedChunk = optimizeChunk chunk
+  let optimizedChunk = optimizeChunk limits chunk
   -- Safety net: reject a chunk that nests too deeply for Lua 5.1's parser
   -- rather than emit Lua that cannot be loaded (issue #104). Catches whatever
   -- 'flattenDeepBinds' bailed on, plus not-yet-flattened deep constructs.

diff --git a/lib/Language/PureScript/Backend/Lua/Limits.hs b/lib/Language/PureScript/Backend/Lua/Limits.hs
@@ -0,0 +1,49 @@
+{- | Hard per-function limits of the target Lua VM.
+
+The storage passes ("Language.PureScript.Backend.Lua.Localize") budget
+their emission against these limits so that generated chunks stay
+loadable on the target (issues #19, #174). The limits are configurable
+(@--max-locals@ / @--max-upvalues@) because they differ between Lua
+implementations: PUC Lua 5.1 — the floor pslua compiles for, see
+@docs/QUIRKS.md@ — ships @LUAI_MAXVARS = 200@ and
+@LUAI_MAXUPVALUES = 60@, while e.g. Lua 5.2+ raises the upvalue limit
+to 255.
+-}
+module Language.PureScript.Backend.Lua.Limits
+  ( LuaLimits (..)
+  , lua51Limits
+  , workingLocalCeiling
+  , workingUpvalueCeiling
+  ) where
+
+-- | Hard per-function limits of the target Lua VM.
+data LuaLimits = LuaLimits
+  { maxLocals ∷ Int
+  {- ^ Local variables per function (@LUAI_MAXVARS@), the chunk's main
+  function included.
+  -}
+  , maxUpvalues ∷ Int
+  {- ^ Upvalues per function (@LUAI_MAXUPVALUES@), amplified in Lua 5.1
+  by pass-through accumulation: a nested function reading an outer
+  local costs an upvalue slot in every intermediate function.
+  -}
+  }
+  deriving stock (Eq, Show)
+
+-- | The Lua 5.1 limits: the compilation floor and the CLI default.
+lua51Limits ∷ LuaLimits
+lua51Limits = LuaLimits {maxLocals = 200, maxUpvalues = 60}
+
+{- | The locals ceiling the storage passes actually budget against: the
+hard limit minus headroom for slots the passes do not model (locals of
+hand-written FFI headers, runtime fixtures).
+-}
+workingLocalCeiling ∷ LuaLimits → Int
+workingLocalCeiling LuaLimits {maxLocals} = maxLocals - 20
+
+{- | The upvalue ceiling the storage passes actually budget against:
+the hard limit minus headroom, since the passes over-approximate
+upvalue demand rather than replicate the target's exact accounting.
+-}
+workingUpvalueCeiling ∷ LuaLimits → Int
+workingUpvalueCeiling LuaLimits {maxUpvalues} = maxUpvalues - 5