Skip to content

CPR-style worker/wrapper on results: constructed products as Lua multiple values - #280

Merged
Unisay merged 7 commits into
mainfrom
issue-206/cpr-result-worker-wrapper
Jul 16, 2026
Merged

CPR-style worker/wrapper on results: constructed products as Lua multiple values#280
Unisay merged 7 commits into
mainfrom
issue-206/cpr-result-worker-wrapper

Conversation

@Unisay

@Unisay Unisay commented Jul 15, 2026

Copy link
Copy Markdown
Collaborator

Closes #206.

Problem

A function whose every return path builds the same constructor allocates a table per call even when every caller immediately takes the result apart. A State-shaped step pays one Tuple per call, an uncons-style helper pays one product per element. The allocation exists only to carry two or three values across a return boundary that Lua can cross natively with multiple return values.

What this does

The result-side twin of the #24 arity split. A binding whose right-hand side is a single n-ary lambda, with every return path ending in one fixed saturated constructor (an Exception path never returns, so it is compatible with any shape), splits into a worker f$r that returns the fields as multiple values and a wrapper under the original name that reboxes them:

local branchy_S_r = function(n)
  ...
  return b1 + b3 + b5 + b7, b2 + b4 + b6 + b8
end

Call sites that immediately deconstruct the result are rewritten by the pass itself to bind the components straight off the worker call, so the table never exists:

M.Golden_CprResult_Test_useBranchy = function(n)
  local _S_v577, _S_v578 = Golden_CprResult_Test_branchy_S_r(n)
  return _S_v577 - _S_v578
end

Callers that consume the product as a first-class value keep going through the wrapper, unchanged. When every site goes to the worker directly and the binding is module-internal, the wrapper is dead code and DCE drops it.

How it lands

  • Two new IR nodes carry the convention: Values is the multi-value return and LetValues is the multi-value binding (local p1, ..., pn = rhs). Note [Multi-value results] defines where a Values may sit, and a new WellApplied violation (ValuesOutsideTail) rejects one outside a return-or-bind position at every checked pass boundary, because a leak there would be silent Lua truncation. LetValues is a binder form, so every scope-aware traversal (uniquify, freshen, alphaEq, free-ref counting, linter, DCE, CSE) learned it.
  • The pass (IR/Cpr.hs) mirrors the uncurrying split: module-wide top-level candidates, per-site local candidates, deterministic $r/$p/$v names, rerun-safe wrapper recognition, and a split gate of at least one deconstructing site. It rewrites those sites itself because the call-site inliner unwinds only unary spines and would never paste a wrapper of an n-ary worker. Constructor tails are recognised through every post-uncurry shape via the recogniser now shared with the known-constructor folds (Query.resolveKnownCtorApp).
  • Four optimizer rules cancel the planted reboxes in a new specialize+dce-post-cpr fixpoint; the actual cancellation is done by the existing known-constructor machinery (propagateKnownCtorThroughLet, reduceKnownConstructor). The call-site inliner declines any multi-value body: a pasted worker or wrapper would lower to a per-call IIFE, which is the exact cost the split removes.

Deliberate v1 boundaries

  • Only let-bound deconstructing sites are rewritten. A read applied directly to the call (fst (step n) without a binding) would put the rewritten shape in expression position, where it lowers to an IIFE, so those sites keep calling the wrapper.
  • Self- and sibling-tail-calling candidates decline: every tail must be the fixed constructor. Extending the tail language so workers tail-call workers (multiple values propagate through return f(...) natively) is a follow-up.
  • Golden.CprState (a real Control.Monad.State do-block) is byte-identical: the StateT dictionary bind chain is not collapsed by the budgeted inliner, so no manifest Tuple-returning candidate exists there yet. The golden pins that boundary; the win applies once chain collapsing reaches those shapes.

Verification

  • 19 unit tests pin the split shapes, the declines (non-constructor tails, mixed constructors, constructor functions, vetoed names, no deconstructing site, self-tail-calls), the rerun contract, and three Hedgehog properties (GUC/WellApplied preservation, idempotence, precise WasRewritten) at 200 cases each.
  • Golden.CprResult pins the end-to-end shapes quoted above; every eval/golden.txt oracle across the suite is byte-identical (cabal test all: 980 examples, 0 failures).
  • Rebased on top of SpecConstr: specialize recursive functions on known-constructor call patterns #279: call-pattern specialization composes cleanly. specConstrPass rides in the post-cpr fixpoint with the same members as the main specialize fixpoint, Golden.SpecConstr stays byte-identical (its specialized workers are recursive, which this pass declines), and the census commit carries the tnew_Bench.TupleFold.txt baseline for the artifact SpecConstr: specialize recursive functions on known-constructor call patterns #279 added.
  • The new static TNEW/TDUP census (first commit) is the allocation counter the issue asked for. tnew_Bench.StateStep.txt function-body count drops 1 → 0 across the accept commit: the per-step table is gone from the hot loop. The trace report moves only in line numbers, since the loop was already interpreter-bound by the curried intMod foreign; the win here is allocation, not trace formation.
  • Wall-clock for the pattern in isolation (bench/micro/state_step.lua, boxed vs multi-value, n=1e7): PUC Lua 5.1 0.58s to 0.22s, LuaJIT -joff 0.41s to 0.09s. The linked Bench.StateStep runs at 0.0142s (LuaJIT) and 0.025s (PUC 5.1) for n=1e5 after the change.

Commits

The census tool and the pinned baselines land first, so the per-step table allocation is recorded with the pre-split compiler. The IR nodes and the pass land behaviour-neutral, the pipeline wiring flips the behaviour in a one-hunk commit, and the accept commit is the reviewable before/after diff.

Unisay added 6 commits July 15, 2026 18:19
FNEW counts closure allocations, but table allocations are invisible to
both the FNEW census and the trace report (TNEW/TDUP do not abort trace
recording). Add the analogous static census over the two table-creation
bytecodes, wire it into ./bench/ci with the same double-run byte-stability
check, and commit baselines for the existing artifacts. This is the
counter the result-side worker/wrapper split (#206) is measured with.
Two golden modules and a State-shaped benchmark, compiled with the
current compiler, recording today's behavior: a function whose every
return path builds the same Tuple allocates a table per call, and every
deconstructing caller reads it apart immediately (v[1]/v[2] over a
Data_Tuple_Tuple_S_w call). The StateStep bench pins exactly one
function-body TNEW — the per-iteration pair — in the tnew census, and
its eval-facing arithmetic is cross-checked against a hand-written
multi-value ideal. The result-side worker/wrapper split turns these
shapes into direct worker calls returning multiple values; the diff of
these goldens under that change is the feature's demonstration.
Two new IR constructors expose Lua's native multiple return values:
Values is the multi-value return (return a, b), LetValues the
multi-value binding (local a, b = rhs). Note [Multi-value results]
defines the multi-value slot discipline; the WellApplied lint gains a
ValuesOutsideTail violation so a Values leaking into a single-value
position — silent Lua truncation — fails loudly at every checked pass
boundary.

LetValues is a binder form, so every scope-aware traversal learns it:
countFreeRefs/countFreeRefUsage, alphaEq (positional binder walk),
freshenBinders, Uniquify, the linter's unboundLocals/duplicateBinders
and the trailing-unused-run check, DCE (live binders keep the producing
call reachable, dead suffixes blank, an all-dead LetValues collapses to
its body), CSE (binders are block-bound names and local-slot costs;
alphaKey canonicalizes positionally), and Query.collectBoundNames. The
Lua backend lowers Values to a multi-value return and LetValues to a
multi-name local, dropping trailing unused binders.

No producer exists yet: the pipeline emits neither node, so generated
code is byte-identical. The result-side worker/wrapper split lands on
top of this.
The new Cpr pass splits every binding whose right-hand side is a single
n-ary lambda with every return path ending in one fixed saturated
constructor (Exception paths are compatible) into a worker returning
the fields as Lua multiple values plus a rebox wrapper under the
original name. Constructor tails are recognised through every
post-uncurry shape via the recogniser shared with the known-ctor folds
(resolveCtorApp, extracted to Query together with hasWholeValueRead).

The pass rewrites the deconstructing call sites itself — a let-bound
saturated call whose binder is read only through eliminating reads
becomes a direct worker call under an in-place rebox — because the
call-site inliner unwinds only unary spines and would never paste a
wrapper of an n-ary worker. Splits are gated on at least one such site;
whole-value consumers keep the wrapper. Local Let candidates split in
place per top-level site; recursive-group members with constructor-only
tails split within their group; self-tail-calling candidates, vetoed
names and constructor functions decline. Reruns re-register existing
wrappers instead of re-splitting, so the pass is idempotent.

Four optimizer rules cancel the planted reboxes in the following
fixpoint: cancelLetValuesOfValues (the revert path),
floatLetFromLetValuesRhs, floatLetValuesFromLetRhs (order-preserving
first-grouping split, feeding propagateKnownCtorThroughLet), and
sinkReadIntoLetValues (feeding reduceKnownConstructor). The call-site
inliner and the duplicatable-closed-abs guard decline bodies containing
Values: a pasted worker body would lower to a per-call IIFE.

The pass is not yet wired into the pipeline, so generated code is
byte-identical; unit tests pin the split shapes, the declines, the
rerun contract, and the GUC/WellApplied/idempotence properties.
The pass sits right after the specialize fixpoint — monadic chains are
collapsed, so constructor-tailed candidates and their deconstructing
sites are maximal — followed by a second specialize+dce fixpoint that
cancels the planted reboxes against the known-constructor folds and
drops fully-bypassed wrappers. The call-site inliner's guard widens
from worker bodies to any multi-value body: pasting a wrapper would
put its rebox in expression position, lowering to a per-call IIFE
where the shared wrapper call costs nothing.
Golden.CprResult now pins the split end-to-end: branchy$r and big$r
return their components as multiple values, every deconstructing site
binds them directly (local a, b = branchy$r(n)) with no table on the
path, and the whole-value consumers (pair, keepBranchy, the exports)
keep the reboxing wrappers. Golden.CprState is byte-identical — the
StateT dictionary bind chain is not collapsed by the budgeted inliner,
so no manifest Tuple-returning candidate exists there yet; the module
pins that boundary. Golden.UncurryCtor moves only in $cse numbering
(the post-cpr fixpoint advances the shared supply).

Bench.StateStep's function-body TNEW+TDUP count drops 1 → 0: the
per-step Tuple table is gone from the hot loop, and with step
module-internal nothing keeps the boxing wrapper alive. The trace
report moves only in line numbers — the loop was already
interpreter-bound by the curried intMod foreign, so the win is
allocation, not trace formation. Every eval/golden.txt oracle is
byte-identical.
@Unisay
Unisay requested a review from Copilot July 15, 2026 16:59
@Unisay Unisay self-assigned this Jul 15, 2026
@Unisay
Unisay marked this pull request as ready for review July 15, 2026 16:59

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 a CPR-style (constructed product result) worker/wrapper split for functions which always return the same saturated constructor, leveraging Lua’s multiple return values to eliminate per-call product allocations at deconstructing call sites. It extends the IR and optimizer pipeline accordingly, updates Lua lowering to support multi-value returns/binds, and adds extensive unit/golden/bench coverage (including a new static table-allocation census).

Changes:

  • Add IR support for multi-value results via new Values (multi-return) and LetValues (multi-bind) nodes, guarded by a new WellApplied violation (ValuesOutsideTail).
  • Introduce and wire a new optimizer pass IR.Cpr that performs the result worker/wrapper split and rewrites qualifying deconstructing sites, plus post-pass cleanup rules.
  • Extend Lua backend lowering and test/benchmark harnesses to validate end-to-end behavior and allocation improvements.

Reviewed changes

Copilot reviewed 49 out of 49 changed files in this pull request and generated 1 comment.

Show a summary per file
File Description
test/ps/src/Golden/CprState/Test.purs Adds a State-shaped golden input module.
test/ps/src/Golden/CprResult/Test.purs Adds a shape-catalog golden input module for result CPR.
test/ps/src/Bench/StateStep.purs Adds a benchmark module meant to expose eliminated Tuple allocations.
test/ps/output/Golden.UncurryCtor.Test/golden.lua Updates golden Lua output reflecting new multi-value lowering/optimizations.
test/ps/output/Golden.UncurryCtor.Test/golden.ir Updates golden IR output reflecting new Values/LetValues nodes.
test/ps/output/Golden.CprState.Test/golden.lua Adds golden Lua output for the new State test module.
test/ps/output/Golden.CprState.Test/golden.ir Adds golden IR output for the new State test module.
test/ps/output/Golden.CprState.Test/eval/golden.txt Adds eval oracle for the new State test module.
test/ps/output/Golden.CprState.Test/eval/.gitignore Adds eval gitignore for the new State test module.
test/ps/output/Golden.CprState.Test/corefn.json Adds CoreFn for the new State test module.
test/ps/output/Golden.CprResult.Test/golden.lua Adds golden Lua output for the new CPR result test module.
test/ps/output/Golden.CprResult.Test/golden.ir Adds golden IR output for the new CPR result test module.
test/ps/output/Golden.CprResult.Test/eval/golden.txt Adds eval oracle for the new CPR result test module.
test/ps/output/Golden.CprResult.Test/eval/.gitignore Adds eval gitignore for the new CPR result test module.
test/Main.hs Registers the new IR.Cpr spec module in the test runner.
test/Language/PureScript/Backend/Lua/Spec.hs Adds Lua-lowering tests for Values and LetValues.
test/Language/PureScript/Backend/IR/Uniquify/Spec.hs Adds uniquify scoping test for LetValues (RHS vs body).
test/Language/PureScript/Backend/IR/Types/Spec.hs Adds Values/LetValues tests for alphaEq/free-ref/freshening behavior.
test/Language/PureScript/Backend/IR/Linter/Spec.hs Adds linter tests for ValuesOutsideTail and LetValues scoping.
test/Language/PureScript/Backend/IR/DCE/Spec.hs Adds DCE tests for LetValues binder liveness/blanking/collapse behavior.
test/Language/PureScript/Backend/IR/Cpr/Spec.hs Adds a comprehensive spec suite for the CPR pass and its contracts.
pslua.cabal Exposes Language.PureScript.Backend.IR.Cpr and includes its spec module.
lib/Language/PureScript/Backend/Lua/Types.hs Adds Lua AST helpers for multi-name locals and multi-value returns.
lib/Language/PureScript/Backend/Lua.hs Lowers IR.Values to return a, b and IR.LetValues to local a, b = ....
lib/Language/PureScript/Backend/IR/Uniquify.hs Teaches uniquify about LetValues scoping and binder renaming.
lib/Language/PureScript/Backend/IR/Types.hs Introduces Values/LetValues, helpers, and Note [Multi-value results].
lib/Language/PureScript/Backend/IR/Query.hs Adds hasWholeValueRead helper shared by optimizer rules and CPR census.
lib/Language/PureScript/Backend/IR/Optimizer.hs Wires in CPR pass, adds post-CPR fixpoint and new cleanup rewrite rules.
lib/Language/PureScript/Backend/IR/Linter.hs Adds ValuesOutsideTail and implements the multi-value-slot walk.
lib/Language/PureScript/Backend/IR/DCE.hs Extends DCE to handle LetValues reachability and binder blanking/collapse.
lib/Language/PureScript/Backend/IR/CSE.hs Extends CSE block analysis/canonicalization for LetValues binders and scope.
lib/Language/PureScript/Backend/IR/Cpr.hs Implements the CPR result worker/wrapper split and site rewriting.
changelog.d/20260715_120000_unisay_cpr_result_worker_wrapper.md Adds a changelog fragment describing the CPR result split and benchmark effect.
bench/tools/tnew_census.lua Adds static TNEW/TDUP allocation census tool for LuaJIT bytecode.
bench/README.md Documents the new table-allocation census alongside existing counters.
bench/micro/state_step.lua Adds a micro-benchmark contrasting boxed vs multi-value state step.
bench/macro/state_step.lua Adds a macro-benchmark driver spec for the new Bench.StateStep artifact.
bench/goldens/trace_state_step.txt Adds a pinned trace report golden for the state_step macro benchmark.
bench/goldens/tnew_Bench.TupleFold.txt Adds pinned TNEW/TDUP census golden for TupleFold.
bench/goldens/tnew_Bench.StateStep.txt Adds pinned TNEW/TDUP census golden for StateStep (function-body allocations drop).
bench/goldens/tnew_Bench.Fib.txt Adds pinned TNEW/TDUP census golden for Fib.
bench/goldens/tnew_Bench.EffectStep.txt Adds pinned TNEW/TDUP census golden for EffectStep.
bench/goldens/tnew_Bench.CurriedStep.txt Adds pinned TNEW/TDUP census golden for CurriedStep.
bench/goldens/tnew_Bench.CtorBuild.txt Adds pinned TNEW/TDUP census golden for CtorBuild.
bench/goldens/tnew_Bench.BindChain.txt Adds pinned TNEW/TDUP census golden for BindChain.
bench/goldens/tnew_Bench.ArrayFoldl.txt Adds pinned TNEW/TDUP census golden for ArrayFoldl.
bench/goldens/fnew_Bench.StateStep.txt Updates/adds FNEW census golden for StateStep as part of counter suite.
bench/ci Extends CI counter script to run and compare the new tnew census outputs.

Comment thread test/ps/src/Golden/CprState/Test.purs Outdated
- test/ps/src/Golden/CprState/Test.purs:1 — reword the module header:
  the golden pins the boundary where the result split does not fire
  (uncollapsed StateT dictionary chain), instead of claiming to witness
  the split (#280 (comment))
@Unisay
Unisay merged commit f3ca78a into main Jul 16, 2026
2 checks passed
@Unisay
Unisay deleted the issue-206/cpr-result-worker-wrapper branch July 16, 2026 09:16
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.

CPR-style worker/wrapper on results: return constructed products as Lua multiple values

2 participants