Skip to content

feat(optimizer): gate inlining with Complexity/Capture lattices#244

Merged
Unisay merged 4 commits into
mainfrom
issue-231/complexity-capture-lattice
Jul 12, 2026
Merged

feat(optimizer): gate inlining with Complexity/Capture lattices#244
Unisay merged 4 commits into
mainfrom
issue-231/complexity-capture-lattice

Conversation

@Unisay

@Unisay Unisay commented Jul 11, 2026

Copy link
Copy Markdown
Collaborator

Closes #231.

What

Two small analysis lattices sharpen the shared inlining guard:

  • Complexity = Trivial < Deref < KnownSize < NonTrivial (complexityOf, a bottom-up classifier next to expSize)
  • Capture = CaptureNone < CaptureBranch < CaptureClosure (countFreeRefUsage, a per-site variant of countFreeRef reporting the strongest wrapper crossed between the root and each reference)

Two new tiers feed the guard shared by withBinding, betaReduce and inlineLocalBinding (Note [Complexity and Capture gate inlining]):

  • Deref tier: an expression of complexity at most Deref and 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.
  • KnownSize tier (local sites only): a closed lambda under 16 nodes whose bound name is used only outside branches and closures substitutes at every site, so a locally bound combinator beta-reduces everywhere. The CaptureNone gate 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 NonTrivial body is never duplicated. The @inline pragmas, the used-once path, the ForeignImport veto and the module-level count map are untouched; inlineSizeBudget = 64 stays the call-site ceiling.

Red → green

The spec commit lands first with a compile-ready skeleton (exact totals, CaptureNone context): 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 Always can 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 end disappear 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.

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.
@Unisay Unisay requested a review from Copilot July 12, 2026 07:55
@Unisay Unisay self-assigned this Jul 12, 2026
@Unisay Unisay marked this pull request as ready for review July 12, 2026 07:55

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 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/Usage analysis and countFreeRefUsage to track both how many uses occur and the strongest capture context of any use.
  • Add Complexity classification (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.

Unisay added 2 commits July 12, 2026 10:10
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.
@Unisay Unisay force-pushed the issue-231/complexity-capture-lattice branch from 051204f to 2d0079f Compare July 12, 2026 08:10
@Unisay Unisay merged commit 41401fb into main Jul 12, 2026
2 checks passed
@Unisay Unisay deleted the issue-231/complexity-capture-lattice branch July 12, 2026 08:27
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.

Enrich IR analysis with a Complexity/Capture lattice to gate inlining and unpacking

2 participants