Dissolve small pure workers into saturated call sites (#211) - #285
Merged
Conversation
#211) The bare-primop unfolding (#281) required a single primop node over Trivial operands, so a worker like add3$w(x, y, z) = (x + y) + z — or one whose body is a bare parameter reference or a projection chain — kept costing a Lua call per saturated site. The predicate now admits a tree of primops, equality tests and negations over leaves of complexity at most Deref, possibly under nested lambdas, with the paste bounded by smallInlineBudget. IfThenElse bodies stay excluded: a decision tree in expression position lowers to a per-call IIFE (issue #203), worse than the shared worker call.
Uncurry.Test loses add3$w / alwaysFirst$w / adderOf$w — every saturated site folds to the inline expression and constant arguments fold at compile time (add3$w(1, 2, 3) emits 6, adderOf$w(1, 2)(3) emits 6). UncurriedLift.Test folds the lifted uncurried add3 sites the same way, and Unbinding.Test computes its constant-bodied worker's result outright. Recursive workers (evenSteps$w, oddSteps$w, go$w) keep sharing: their bodies apply a function. Eval oracles unchanged.
- lib/Language/PureScript/Backend/IR/Optimizer.hs:1623 — use strict < against smallInlineBudget, matching isCheapProjection and isDuplicatableClosedAbs (#285 (comment)) - lib/Language/PureScript/Backend/IR/Optimizer.hs:1663 — reword isCheapWorkerBody haddock: allocation parity with the worker call, not "no allocation" (#285 (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 #211.
Problem
Issue #211 predates two changes that reshaped its landscape: the Capture/Complexity inlining lattices (#231) and the bare-primop worker unfolding (#281). #281 already dissolves
sub$w(v, 1)intov - 1, but its predicate demands a single primop node overTrivialoperands, so anything one step richer kept paying a Lua call per saturated site:(x + y) + zis a nested primop (the left operand is notTrivial),return xis not a primop at all, and a projection-chain operand liker.foopricesDeref, one notch aboveTrivial. All three declined.Change
isBarePrimOpBodybecomesisCheapWorkerBody: a tree of primops, equality tests and negations over leavescomplexityOfclassifies at mostDeref(parameter references, scalar literals, cheap projection chains), possibly under nested lambdas. The paste is additionally bounded bysmallInlineBudget— the constant whose documented meaning is exactly "duplication at every use site":Everything else rides on existing machinery: the n-ary
AbsNroot is pasted under the originalAppN, the exact-aritybetaReduceconsumes it in the same pass, andconstantFoldingfinishes the job where arguments are literal. The former call sites inGolden.Uncurry.Test:and the partially-applied residual closure folds its constants too:
All three workers above are gone from the output entirely: once every saturated site is inlined, DCE drops the worker, and the late uncurry run leaves the surviving manifest chain alone because a binding with no saturated site is never split.
What deliberately stays shared
IfThenElsebodies are not admitted, deviating from the issue's original allowed list: anIfThenElsein expression position lowers throughchunkToExpressionto a per-call IIFE — the exact allocation the case-of-case rules of #203 exist to remove — so pasting a decision tree would trade a named call for a closure allocation plus a call. Application bodies (sumTo$w,evenSteps$w,logShow$w, the monad workers), allocating bodies (Ctor, non-empty literals,Let) and oversized trees also keep sharing, each declining through thecomplexityOffallback or the budget. Value-position uses are untouched by construction: the rule fires only at saturatedAppNheads, so the sharing-vs-Capture concern that #231 codified for the local tiers never arises (no lambda literal lands in a branch or closure position — it is consumed bybetaReduceon the spot).The issue's original sketch — extending the shared
isInlinableExprguard so the binding dissolves before uncurry — would have bypassed theCaptureNonegate ofisDuplicatableClosedAbsand pasted lambda literals into value positions (the #204 trace-abort pathology). Keeping the admission per-call-site delivers the same end state for call uses while leaving every value use a shared reference, so this lands as a completion of #211 in the post-#231/#281 architecture rather than a literal transcription.Testing
Unit tests mirror the #281 spec block: three positives (nested primop tree, parameter-selecting body,
Deref-leaf operands — red before the change) and three negatives pinning the exclusions (application body, branching body, over-budget tree — green before and after). Golden churn is limited toGolden.Uncurry.Test,Golden.UncurriedLift.TestandGolden.Unbinding.Test; every eval oracle passes unchanged, and the full suite is stable across four hspec seeds (1,42,20260716,999983).