Lower self-recursive tail calls to while loops (loopification) - #205
Merged
Conversation
A self-recursive tail call of an uncurried worker stays a call: PUC Lua runs it in constant stack via TCO, but pays CALL/RET machinery and argument shuffling per iteration, and LuaJIT lacks the stable loop marker its trace compiler wants. Lower block-final self-calls to a 'while true do' loop with simultaneous multiple assignment of the parameters, during Lua code generation (the expression IR keeps no loop node, the same choice magicDo makes for statements). A body that captures a parameter inside a nested closure is left recursive: parameters of a loopified function are shared across iterations, so reassignment would corrupt the captured environment. Immediately-invoked scope wrappers are looked through transparently. The argument explist is balanced to the variable count: nil-padded when trailing Prim.undefined arguments were elided (declined after a multi-value argument), surplus values facing dropped unused parameters removed when syntactically pure, declined otherwise. Applies to any self-recursive recursive-group binding, top-level or Let-bound — an uncurried worker or a plain unary function. Non-tail self-calls and the wrapper indirection stay real calls; the one observable difference is the shape of error tracebacks.
The golden module pins six shapes: a unary self-recursion (loopified without a worker split), the canonical binary accumulator, a local where-bound worker, McCarthy 91 (the tail self-call becomes an iteration while the argument-position one stays a call), a CPS accumulator (the capture veto keeps it recursive — the hand-written eval oracle proves reassignment would have corrupted the captured continuations), and a dead trailing parameter (the surplus argument is dropped from the loop assignment). Unit tests cover the same decision points at the fromUberModule level — top-level and Let-bound groups, non-tail calls, the capture veto, and explist balancing (pure surplus dropped, effectful surplus declined, nil padding, multi-value decline).
The FNEW census moves only by line numbers. The trace report shows the worker's blacklisted function entry (IFUNCF) replaced by a blacklisted loop (ILOOP): the loop shape landed, but its trace still aborts on the per-iteration FNEWs of the curried foreign calls, so the LuaJIT payoff waits for the curried-FFI work (#178, #186). Measured on curried_step (n=2e6, median of the run_macro harness): PUC 0.363s -> 0.348s; LuaJIT 0.196s -> 0.366s — an interim regression on this benchmark until the loop body stops allocating closures.
Contributor
There was a problem hiding this comment.
Pull request overview
Implements Lua-side “loopification” for self-recursive tail calls: eligible tail return f(e1, …, en) sites are rewritten into while true do loops with simultaneous parameter reassignment, avoiding recursive CALL/RET overhead and producing a loop shape that’s friendlier to LuaJIT tracing.
Changes:
- Added
Language.PureScript.Backend.Lua.Loopifyand integrated it into Lua codegen at recursive-group lowering sites (top-level andlet-bound). - Added/updated golden coverage (including a new
Golden.Loopification.Testwith an eval oracle) and expanded unit tests inLua.Specto cover decision points (tail-position detection, capture veto, explist balancing). - Updated benchmark trace goldens to reflect the new loop shape.
Reviewed changes
Copilot reviewed 17 out of 17 changed files in this pull request and generated no comments.
Show a summary per file
| File | Description |
|---|---|
lib/Language/PureScript/Backend/Lua/Loopify.hs |
New loopification transform: tail-position rewrite, capture veto, and argument/parameter explist balancing. |
lib/Language/PureScript/Backend/Lua.hs |
Applies loopification when lowering recursive groups at top-level and inside Let recursive groups. |
pslua.cabal |
Exposes the new Language.PureScript.Backend.Lua.Loopify module in the library stanza. |
test/Language/PureScript/Backend/Lua/Spec.hs |
Adds unit tests and IR fixtures to validate loopification behavior and veto/balancing cases. |
test/ps/src/Golden/Loopification/Test.purs |
New PureScript golden source exercising loopified and non-loopified shapes. |
test/ps/output/Golden.Loopification.Test/corefn.json |
New compiled CoreFn artifact for the loopification golden. |
test/ps/output/Golden.Loopification.Test/golden.ir |
New IR golden (expected unchanged by Lua-only transform, but added for the new test module). |
test/ps/output/Golden.Loopification.Test/golden.lua |
New Lua golden demonstrating the while true do lowering and vetoed CPS case. |
test/ps/output/Golden.Loopification.Test/eval/golden.txt |
New hand-written eval oracle pinning runtime behavior. |
test/ps/output/Golden.Loopification.Test/eval/.gitignore |
Golden eval output ignore rule for actual.txt. |
test/ps/output/Golden.Uncurry.Test/golden.lua |
Updated existing golden to reflect loopified worker output. |
test/ps/output/Golden.StringCodePoints.Test/golden.lua |
Updated existing golden to reflect loopification of a self-recursive worker. |
test/ps/output/Golden.PatternMatching.Test2/golden.lua |
Updated existing golden to reflect unary structural recursion loopification. |
test/ps/output/Golden.LongCallbackChain.Test/golden.lua |
Updated existing golden to reflect loopification in a callback-chain worker. |
changelog.d/20260707_220000_unisay_loopification.md |
Adds a changelog fragment documenting loopification behavior and caveats. |
bench/goldens/trace_curried_step.txt |
Updates the LuaJIT trace report golden to reflect loop lowering (ILOOP). |
bench/goldens/fnew_Bench.CurriedStep.txt |
Updates FNEW site line references after code shape changes. |
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 #181.
What
A self-recursive tail call now lowers to a
while true doloop with simultaneous multiple assignment of the parameters.return go$w(e1, e2)in tail position becomesp1, p2 = e1, e2followed by fall-through to the end of the loop body; every other exit path keeps itsreturn, which leaves the loop.The transform lives in the Lua code generator (new module
Language.PureScript.Backend.Lua.Loopify), applied to recursive-group bindings at the two places they are lowered: top-level groups (self-reference through theMtable) andLet-bound groups (plain local). The expression IR keeps no loop node, the same choice magicDo makes for statements. Foreign code never passes through it.Tail positions are found by walking the block spine of the generated function: the final statement of the body and, recursively, the final statement of each branch of a block-final
if. This is exactly where the code generator puts IR tail positions (throughLetbodies andIfThenElsebranches), and it is what makes fall-through work as "continue" on a target withoutgoto.Two things fell out beyond the issue text:
countdown n = ... countdown (n - 1), and structural recursions likebat (Succ n) = bat n(which becomesn = n.value0).Correctness guards
Capture veto. Lua closures capture variables by reference, and parameters of a loopified function are shared across iterations, so a closure created in one iteration and surviving into the next would observe the reassigned values. A body that references a parameter from inside a nested function literal is therefore not loopified. Immediately-invoked scope wrappers
(function() ... end)()are looked through transparently; without that, the comparison predicates the case compiler emits (IIFEs reading the scrutinee) would veto nearly everything. The golden's CPS accumulator (sumCPS n k = ... sumCPS (n - 1) (\r -> k (r + n))) pins the veto: it stays recursive, and the hand-written eval oracle would catch the corruption if it ever loopified.Explist balancing. The assignment's right-hand explist is balanced to the variable count, because the code generator drops trailing unused parameters and trailing
Prim.undefinedarguments, so the two lists can disagree in length. A short list is padded with explicitnils (declined when the last argument is a call or vararg, whose multiple results the pad would truncate where the call form spreads them); surplus expressions facing dropped parameters are removed when syntactically pure, and decline the rewrite otherwise. This also keeps luacheck's unbalanced-assignment check quiet.Tests
Golden.Loopification.Testwith six shapes (unary countdown, binary accumulator, localwhere-bound worker, McCarthy 91, CPS capture veto, dead trailing parameter) and a hand-written eval oracle.Lua.Speccover the decision points throughfromUberModule: top-level andLet-bound groups, non-tail calls, the capture veto, and all four explist-balancing outcomes.Uncurry(thesumToworker),LongCallbackChain,PatternMatching.Test2, andStringCodePoints(the library'scodePointAtFallbackworker loopifies).golden.irfiles are untouched, since the transform is strictly Lua-side. All eval oracles pass unchanged.Measurements
On
curried_step(n=2e6, medians): PUC Lua 0.363s to 0.348s, the modest constant-factor win the issue predicted, since the loop body is still dominated by curried FFI closure allocation. Under LuaJIT the loop is blacklisted (IFUNCFtoILOOPin the accepted trace report) because those same per-iteration FNEWs abort trace recording, and the benchmark regresses from 0.196s to 0.366s for now. That interim regression should flip once #178/#180/#186 remove the allocations from loop bodies; it is tracked in #204.