CPR-style worker/wrapper on results: constructed products as Lua multiple values - #280
Merged
Merged
Conversation
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.
Contributor
There was a problem hiding this comment.
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) andLetValues(multi-bind) nodes, guarded by a newWellAppliedviolation (ValuesOutsideTail). - Introduce and wire a new optimizer pass
IR.Cprthat 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. |
- 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))
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 #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
Tupleper call, anuncons-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
Exceptionpath never returns, so it is compatible with any shape), splits into a workerf$rthat returns the fields as multiple values and a wrapper under the original name that reboxes them: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:
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
Valuesis the multi-value return andLetValuesis the multi-value binding (local p1, ..., pn = rhs). Note [Multi-value results] defines where aValuesmay sit, and a newWellAppliedviolation (ValuesOutsideTail) rejects one outside a return-or-bind position at every checked pass boundary, because a leak there would be silent Lua truncation.LetValuesis a binder form, so every scope-aware traversal (uniquify, freshen, alphaEq, free-ref counting, linter, DCE, CSE) learned it.IR/Cpr.hs) mirrors the uncurrying split: module-wide top-level candidates, per-site local candidates, deterministic$r/$p/$vnames, 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).specialize+dce-post-cprfixpoint; 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
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.return f(...)natively) is a follow-up.Golden.CprState(a realControl.Monad.Statedo-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
WasRewritten) at 200 cases each.Golden.CprResultpins the end-to-end shapes quoted above; everyeval/golden.txtoracle across the suite is byte-identical (cabal test all: 980 examples, 0 failures).specConstrPassrides in the post-cpr fixpoint with the same members as the main specialize fixpoint,Golden.SpecConstrstays byte-identical (its specialized workers are recursive, which this pass declines), and the census commit carries thetnew_Bench.TupleFold.txtbaseline for the artifact SpecConstr: specialize recursive functions on known-constructor call patterns #279 added.tnew_Bench.StateStep.txtfunction-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 curriedintModforeign; the win here is allocation, not trace formation.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 linkedBench.StateStepruns 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.