Skip to content

Collapse non-Effect/ST monadic chains via budgeted call-site inlining#219

Merged
Unisay merged 2 commits into
mainfrom
issue-180/dict-method-inlining
Jul 10, 2026
Merged

Collapse non-Effect/ST monadic chains via budgeted call-site inlining#219
Unisay merged 2 commits into
mainfrom
issue-180/dict-method-inlining

Conversation

@Unisay

@Unisay Unisay commented Jul 10, 2026

Copy link
Copy Markdown
Collaborator

Closes #180.

A non-Effect/ST do block (over Maybe, Either, and friends) compiled to a
tower of bind closures. This adds a post-magic-do pass that inlines the
dictionary method at each call site so the case-of-known-constructor folds
(#177/#213/#214) can fire, and a Maybe/Either chain then collapses to
straight-line code. A size budget keeps the growth in check.

The pass runs as a specialize+dce fixpoint after magic-do, so dead-code
elimination and beta reduction had to learn to leave magic-do's lowered
Effect/ST statements alone.

What made it work

Getting the chain to actually collapse (rather than half-inline into a deeply
nested tree) took three supporting changes:

Resolve imported constructor references. A source-level Right x compiles to
a reference to the Data.Either.Right worker, whose right-hand side is a bare
Ctor node, not a lambda, so the call-site inliner leaves it in place.
propagateKnownCtorThroughLet now looks the reference up in the inline
environment to read its tag and arity. Without this an inlined bind's tag test
never folds, and Golden.LongEitherBind stayed a >180-deep if/let tree that
overflowed the Lua parser's nesting cap.

A dedicated effect-run marker. Magic-do ran a thunk by applying it to
Prim.undefined, which is also the argument PureScript passes to force an
ordinary nullary thunk. isEffectRun could not tell the two apart, so beta
reduction refused to reduce a whole class of pure thunks (superclass-dictionary
accessors, runIdentity newtype coercions) that a non-Effect monad like
State inlines, leaving them to bloat the output. Magic-do now uses its own
EffectRunArg marker, so isEffectRun is exact and those pure thunks reduce
away. This more than halved the State growth on its own.

Distribute a tag read through a conditional. An inlined comparison
(compare, >=) is an if-tree of Ordering constructors.
reduceKnownConstructor now pushes a reflectCtor read into the branches (only
when every branch folds), so the tree becomes tag-string comparisons instead of
building an Ordering table at runtime just to read the tag back off it.

Result

Across the golden corpus the net is a large reduction (the diff is about 35k
lines removed against 24k added). Realistic monadic code collapses hard:
LongEitherBind 731 to 77 lines, LongReaderBind 513 to 40,
ProfunctorDictLens 122 to 17.

The exceptions are the deep monad-transformer stress tests, where inlining a
StateT/Except bind unrolls the state threading with no sum-type tag to
fold against: LongStateBind +282, LongStackBind +277, TailRecM2Shadow +112
lines. These are 300-step or fully polymorphic stress cases, they stay correct
and load fine, and the growth is 1.3 to 1.7x (down from 8x before the effect-run
marker). Two follow-up optimizations that would shrink them further are filed
separately: Eq-through-if folding (#220) and inlining that only fires when
it pays for itself (#221).

Verification

  • Full suite green (cabal test all). Every eval oracle passes, so the runtime
    output is unchanged; only the structural goldens moved.
  • A focused unit test pins the constructor-reference resolution (red without the
    fix, green with it).
  • fourmolu and hlint clean.

)

After magic-do, a budgeted specialize+dce fixpoint inlines dictionary
methods at their call sites so the case-of-known-constructor folds
(#177/#213/#214) fire, turning Maybe/Either bind cascades into
straight-line code. Growth is bounded by inlineSizeBudget. The pass runs
after magic-do, so DCE and beta reduction are made effect-aware to leave
magic-do's lowered Effect/ST statements alone.

- propagateKnownCtorThroughLet resolves an imported constructor reference
  through the inline environment. A source-level `Right x` stays a Ref to
  the Data.Either.Right worker (a bare Ctor, not a lambda, so
  inlineSaturatedCall leaves it in place); without the resolution an
  inlined bind's tag test never folds and the chain stayed a >180-deep
  if/let tree that overflowed the Lua parser (Golden.LongEitherBind).

- Magic-do effect runs carry a dedicated EffectRunArg marker, distinct
  from the Prim.undefined argument that forces an ordinary nullary thunk,
  so isEffectRun is precise. Beta reduction then collapses the
  coincidentally nullary thunks (a superclass-dictionary accessor, a
  runIdentity newtype coercion) a non-Effect monad such as State inlines,
  which were left un-reduced and bloating the output.

- reduceKnownConstructor distributes a tag read through a conditional of
  constructors, so an inlined comparison's Ordering if-tree folds to tag
  strings instead of allocating an Ordering table at runtime to read the
  tag back off it.

Structural goldens updated; eval oracles unchanged (semantics preserved).
@Unisay Unisay requested a review from Copilot July 10, 2026 07:57
@Unisay Unisay self-assigned this Jul 10, 2026

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 improves the PureScript-to-Lua backend’s optimization pipeline by adding budgeted call-site inlining of dictionary methods after magic-do, enabling existing known-constructor folds to collapse non-Effect/ST monadic do chains (e.g. Maybe/Either) into straighter-line IR/Lua while bounding code growth.

Changes:

  • Introduces a dedicated magic-do effect-run marker (EffectRunArg) and teaches Lua codegen to erase it like Prim.undefined, while letting optimizer passes precisely recognize effect runs.
  • Updates DCE (and related optimizer behavior) to preserve magic-do effect-run statements and avoid invalid post-magic-do rewrites that would break chunking/limits.
  • Updates optimizer unit tests and refreshes many golden outputs to reflect the new optimization results.

Reviewed changes

Copilot reviewed 60 out of 73 changed files in this pull request and generated 1 comment.

Show a summary per file
File Description
test/ps/output/Golden.Uncurry.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.TailRecM2Shadow.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.RecordsAccess.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.RecordsAccess.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.RecGroupOrder.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.RecGroupOrder.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.ProfunctorDictLens.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.Primops.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.Nested.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.Nested.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.MaybeChain.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.MaybeChain.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.Loopification.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.LongWriterBind.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.LongWriterBind.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.LongMaybeBind.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.LongMaybeBind.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.LongDoBlock.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.LongCallbackChain.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.LongCallbackChain.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.LongBindFlipped.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.LongApplyChain.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.Issue37.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.Issue37.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.HelloPrelude.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.HelloPrelude.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.ForeignSharing.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.ForeignSharing.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.FloatIn.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.FieldCaching.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.DerivedFunctor.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.CharLiterals.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.CharLiterals.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.CaseStatements.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.CaseStatements.Test/golden.ir Updated golden IR output after new optimization behavior.
test/ps/output/Golden.BugListGenericEq.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.ArrayPatternMatch.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.ArrayOfUnits.Test/golden.lua Updated golden Lua output after new optimization behavior.
test/ps/output/Golden.ArrayOfUnits.Test/golden.ir Updated golden IR output after new optimization behavior.
test/Language/PureScript/Backend/IR/Optimizer/Spec.hs Adds/adjusts optimizer tests and updates optimizeModule call-site inlining parameterization.
lib/Language/PureScript/Backend/Lua.hs Treats EffectRunArg as an erased thunk argument alongside Prim.undefined.
lib/Language/PureScript/Backend/IR/Types.hs Introduces EffectRunArg and isEffectRun for precise post-magic-do handling.
lib/Language/PureScript/Backend/IR/MagicDo.hs Uses EffectRunArg when running effect thunks, instead of Prim.undefined.
lib/Language/PureScript/Backend/IR/DCE.hs Preserves effect-run statements during DCE and treats effect runs as dependencies of Let.
changelog.d/20260710_100000_unisay_collapse_monadic_chains.md Changelog entry describing the optimization and supporting changes.

Comment thread lib/Language/PureScript/Backend/IR/DCE.hs
- lib/Language/PureScript/Backend/IR/DCE.hs:386 — update stale `m Prim.undefined`
  comment to the `EffectRunArg` marker
  (#219 (comment))
@Unisay Unisay merged commit 1f18cc1 into main Jul 10, 2026
2 checks passed
@Unisay Unisay deleted the issue-180/dict-method-inlining branch July 10, 2026 09:03
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.

Budgeted call-site inlining of dictionary methods to collapse non-Effect/ST monadic chains

2 participants