Collapse non-Effect/ST monadic chains via budgeted call-site inlining#219
Merged
Conversation
) 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).
Contributor
There was a problem hiding this comment.
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 likePrim.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. |
- lib/Language/PureScript/Backend/IR/DCE.hs:386 — update stale `m Prim.undefined` comment to the `EffectRunArg` marker (#219 (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 #180.
A non-
Effect/STdoblock (overMaybe,Either, and friends) compiled to atower of
bindclosures. This adds a post-magic-do pass that inlines thedictionary method at each call site so the case-of-known-constructor folds
(#177/#213/#214) can fire, and a
Maybe/Eitherchain then collapses tostraight-line code. A size budget keeps the growth in check.
The pass runs as a
specialize+dcefixpoint after magic-do, so dead-codeelimination and beta reduction had to learn to leave magic-do's lowered
Effect/STstatements 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 xcompiles toa reference to the
Data.Either.Rightworker, whose right-hand side is a bareCtornode, not a lambda, so the call-site inliner leaves it in place.propagateKnownCtorThroughLetnow looks the reference up in the inlineenvironment to read its tag and arity. Without this an inlined
bind's tag testnever folds, and
Golden.LongEitherBindstayed a >180-deepif/lettree thatoverflowed 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 anordinary nullary thunk.
isEffectRuncould not tell the two apart, so betareduction refused to reduce a whole class of pure thunks (superclass-dictionary
accessors,
runIdentitynewtype coercions) that a non-Effectmonad likeStateinlines, leaving them to bloat the output. Magic-do now uses its ownEffectRunArgmarker, soisEffectRunis exact and those pure thunks reduceaway. This more than halved the
Stategrowth on its own.Distribute a tag read through a conditional. An inlined comparison
(
compare,>=) is an if-tree ofOrderingconstructors.reduceKnownConstructornow pushes areflectCtorread into the branches (onlywhen every branch folds), so the tree becomes tag-string comparisons instead of
building an
Orderingtable 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:
LongEitherBind731 to 77 lines,LongReaderBind513 to 40,ProfunctorDictLens122 to 17.The exceptions are the deep monad-transformer stress tests, where inlining a
StateT/Exceptbindunrolls the state threading with no sum-type tag tofold against:
LongStateBind+282,LongStackBind+277,TailRecM2Shadow+112lines. 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-iffolding (#220) and inlining that only fires whenit pays for itself (#221).
Verification
cabal test all). Every eval oracle passes, so the runtimeoutput is unchanged; only the structural goldens moved.
fix, green with it).
fourmoluandhlintclean.