feat(optimizer): gate inlining with Complexity/Capture lattices#244
Merged
Conversation
Red against the skeleton (106 examples, 6 failures): the Deref tier, both KnownSize substitution paths, and the three Capture-context examples fail; the sharing pins and every pre-existing spec pass. Capture/Usage ship as compile-ready skeletons (exact totals, CaptureNone context) so the specs build before the real analysis.
Contributor
There was a problem hiding this comment.
Pull request overview
This PR enhances the IR optimizer’s inlining guard by introducing two analysis lattices—Complexity (to model duplication cost) and Capture (to model whether a use is unconditional vs under a branch/closure). This refines when the optimizer is allowed to inline/duplicate expressions in withBinding, betaReduce, and local-let inlining, aiming to reduce unnecessary shared bindings while avoiding pathological duplication under closures (notably related to #204).
Changes:
- Add
Capture/Usageanalysis andcountFreeRefUsageto track both how many uses occur and the strongest capture context of any use. - Add
Complexityclassification (complexityOf) plus a small-budget “Deref tier” and a local-only “KnownSize tier” (isDuplicatableClosedAbs) to gate inlining beyond simple use-count checks. - Extend optimizer spec coverage for the new gating rules and update golden IR/Lua outputs to reflect the new inlining decisions.
Reviewed changes
Copilot reviewed 23 out of 23 changed files in this pull request and generated no comments.
Show a summary per file
| File | Description |
|---|---|
lib/Language/PureScript/Backend/IR/Types.hs |
Introduces Capture, Usage, and countFreeRefUsage to enrich reference counting with capture context. |
lib/Language/PureScript/Backend/IR/Optimizer.hs |
Implements Complexity, a small inlining budget, and integrates Complexity/Capture into the shared inlining guard used by beta-reduction and local binding inlining. |
test/Language/PureScript/Backend/IR/Optimizer/Spec.hs |
Adds regression/spec tests for #231 (Complexity/Capture gating) and verifies countFreeRefUsage behavior. |
test/ps/output/Golden.Uncurry.Test/golden.ir |
Golden update reflecting additional inlining/simplification enabled by the new guard. |
test/ps/output/Golden.Uncurry.Test/golden.lua |
Golden update reflecting reduced worker bindings and simplified arithmetic at call sites. |
test/ps/output/Golden.UncurriedLift.Test/golden.ir |
Golden update reflecting optimizer reshaping after gating changes. |
test/ps/output/Golden.UncurriedLift.Test/golden.lua |
Golden update corresponding to IR changes. |
test/ps/output/Golden.TailRecM2Shadow.Test/golden.ir |
Golden update reflecting let/closure reshaping and reduced intermediate bindings. |
test/ps/output/Golden.TailRecM2Shadow.Test/golden.lua |
Golden update corresponding to IR changes. |
test/ps/output/Golden.StringCodePoints.Test/golden.ir |
Golden update reflecting reduced intermediate lets in tuple construction. |
test/ps/output/Golden.StringCodePoints.Test/golden.lua |
Golden update corresponding to IR changes. |
test/ps/output/Golden.Loopification.Test/golden.ir |
Golden update (primarily binder renaming / shape changes downstream of optimizer decisions). |
test/ps/output/Golden.Loopification.Test/golden.lua |
Golden update corresponding to IR changes. |
test/ps/output/Golden.Issue37.Test/golden.ir |
Golden update reflecting reduced cached field bindings / restructured binds. |
test/ps/output/Golden.Issue37.Test/golden.lua |
Golden update corresponding to IR changes. |
test/ps/output/Golden.GenericEqTwoTypes.Test/golden.ir |
Golden update reflecting factoring of generic equality worker and updated call structure. |
test/ps/output/Golden.GenericEqTwoTypes.Test/golden.lua |
Golden update corresponding to IR changes. |
test/ps/output/Golden.FieldCaching.Test/golden.ir |
Golden update (binder renaming / minor reshaping). |
test/ps/output/Golden.FieldCaching.Test/golden.lua |
Golden update corresponding to IR changes. |
test/ps/output/Golden.BugListGenericEq.Test/golden.ir |
Golden update reflecting restructuring around generic-eq encoding and binding placement. |
test/ps/output/Golden.BugListGenericEq.Test/golden.lua |
Golden update corresponding to IR changes. |
test/ps/output/Golden.ArrayPatternMatch.Test/golden.ir |
Golden update reflecting inlining of a multi-use empty array literal under the new Deref/Trivial tier. |
test/ps/output/Golden.ArrayPatternMatch.Test/golden.lua |
Golden update corresponding to IR changes. |
Two lattices sharpen the shared inlining guard: Complexity prices duplicating an expression, Capture locates a binding's use sites relative to branches and closures. The Deref tier pastes projection chains over write-once tables at any use count; the KnownSize tier substitutes a small closed lambda whose uses all sit outside branches and closures, so a locally-bound combinator beta-reduces at every site. A NonTrivial body is never duplicated. Capture is computed per reference by countFreeRefUsage, Complexity by a bottom-up classifier next to expSize. The leak-guard spec fixture moves to an annotated application: a projection-shaped field now inlines on its own merit, so only a non-trivial fixture still proves the annotation does not leak. See Note [Complexity and Capture gate inlining].
…es (#231) 10 of 62 modules move, net -223 lines of generated Lua: multi-use projection aliases dissolve and small closed local lambdas beta-reduce at their sites, cascading into used-once whole-binding inlining of tiny uncurried workers. All 31 eval oracles are byte-identical (never auto-accepted), and no added line pattern grew its occurrence count against the old goldens.
051204f to
2d0079f
Compare
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 #231.
What
Two small analysis lattices sharpen the shared inlining guard:
Complexity = Trivial < Deref < KnownSize < NonTrivial(complexityOf, a bottom-up classifier next toexpSize)Capture = CaptureNone < CaptureBranch < CaptureClosure(countFreeRefUsage, a per-site variant ofcountFreeRefreporting the strongest wrapper crossed between the root and each reference)Two new tiers feed the guard shared by
withBinding,betaReduceandinlineLocalBinding(Note [Complexity and Capture gate inlining]):Derefand size under 16 pastes at any use count. Records and module tables are write-once, so re-reading a projection chain preserves semantics. Multi-use projection aliases dissolve.CaptureNonegate refuses to move a lambda literal into a branch or closure (the per-call closure-allocation pathology of LuaJIT blacklists loopified self-recursion while the loop body still allocates closures #204), so closedness and small size alone do not admit duplication.A
NonTrivialbody is never duplicated. The@inlinepragmas, the used-once path, theForeignImportveto and the module-level count map are untouched;inlineSizeBudget = 64stays the call-site ceiling.Red → green
The spec commit lands first with a compile-ready skeleton (exact totals,
CaptureNonecontext): 106 examples, 6 failures. Failing were the Deref tier, both KnownSize substitution paths and the three capture-context examples; the sharing pins and every pre-existing spec passed. The feat commit turns the six green without touching the pins.One pre-existing fixture moved: the #131 leak-guard test used a projection-shaped field, which the Deref tier now inlines on its own merit regardless of annotation. The fixture is an annotated application now, so only a leaked
Just Alwayscan make the binding inlinable and the guard keeps its teeth.Corpus
10 of 62 golden modules move, net -223 lines of generated Lua. All 31 eval oracles pass unchanged (they are never auto-accepted), luacheck passes, and the checked pipeline lints every pass boundary. A scan of the churn found no added line pattern whose occurrence count grew against the old goldens: nothing non-trivial got duplicated.
The Uncurry module shows the intended end shape: tiny uncurried workers like
add$w = function(x, y) return x + y enddisappear and their call sites fold to+. The collapse is a domino cascade rather than a direct admission: a new tier dissolves a cheap binding, the next binding becomes used-once for the existing rule, and the pass fixpoint rolls forward. A minimal probe confirms a twice-used worker still survives on its own, and the cascade surfaced a separate gap in the call-site inliner (n-ary heads), filed as a follow-up.Left for follow-ups
Per-use-kind counters (call/access/case) and an admission for a projection used only in call position. #239 and #240 consume the Capture and exact-use groundwork this PR lays.