MagicDo: recognize Effect/ST chains by qualified name - #259
Merged
Conversation
inlineLocalBinding's use-once path pasted a magic-do effect-run RHS (x = m $magicDoRun) into the Let body. Dead-code elimination deliberately keeps such statements even when their binder is unreferenced, so the paste left two copies -- the surviving statement and the pasted one -- and the effect executed twice at runtime. Decline the paste, mirroring the existing DCE and beta-reduction guards on isEffectRun. Golden.TailRecM2Shadow shrinks accordingly: its main previously re-ran the entire tailRecM machinery inside the log argument, on top of the kept binding of the same computation.
The Let case of freshenBinders renamed bound names through a single name-keyed map. A magic-do-lowered thunk binds several statements to the GUC-exempt discard binder `_`, so they all shared one map entry and every discard binding of the Let was renamed to the same fresh name -- a genuine duplicate binder the exemption no longer covers, caught by the checked pipeline as a DuplicateBinder failure of the specialize pass whenever such a thunk was pasted at a call site. The discard binder now stays out of the rename map entirely: nothing may reference it, so it needs no rename at all.
Three new golden modules committed at current output, so the diff of the upcoming by-name recognition change is its own demonstration: - Golden.EffectPureChain.Test: an Effect chain with a mid-chain `x <- pure ...` and a pure-terminated tail. The chain lowers, but every pure step keeps its dictionary-application residue (`Test_pure(...)()` calls through `applicativeEffect.pure`). - Golden.STDoBlock.Test: a dedicated ST do-chain (no such coverage existed), pure-terminated, run with ST.run over an STRef. - Golden.MixedEffectSTDo.Test: Effect and ST blocks in one module, a canary for a purs-CSE partial dictionary prefix shared across the two monads' dictionaries. The eval oracles are hand-written and pin runtime behaviour across the upcoming re-accept.
Canonicalize Effect/ST dictionary applications into applications of the real foreign methods (Effect.bindE/pureE, Control.Monad.ST.Internal's bind_/pure_) -- compile-time dictionary projection, exact by the instance definitions, and unmatched residuals stay executable at runtime. Two tiers: at CoreFn translation (applications build bottom-up, so nested pairs compose, covering cross-module uses and the purs CSE floats) and as an optimizer rewrite rule (a same-module dictionary reference is Local until the linker requalifies it). See Note [Canonical Effect/ST heads]. Magic-do consumes the canonical heads by name through three lenses -- a direct reference, the dissolved foreign-accessor read, one top-level alias hop -- replacing the fueled spine unwinding, alias chasing, dictionary-literal projection and speculative beta-reduction. With substituteMoveM gone the pass is pure and draws no supply names. New: the pure run peephole. Running a canonical pure is the identity on its argument, so App (pure x) EffectRunArg rewrites to x -- collapsing pure-terminated chain tails, mid-chain `x <- pure e` statements, and the pre-existing runs of the foreign lifter's run*Fn wrappers. Emission (peelChain/buildThunk, 150-statement chunking, EffectRunArg) and the pipeline order are unchanged; the pre-magicDo SkipCallSites stays as conservative caution rather than a recognition constraint.
Structural goldens re-accepted after the canonicalization; every eval/golden.txt oracle is untouched and passing. Highlights: - Golden.EffectPureChain: mid-chain `x <- pure (n + 1)` is a plain `local x = n + 1` and the pure tail a direct return; the Effect dictionary web and the PSLUA_runtime_lazy fixture are DCE'd away. - Golden.UncurriedLift: sumST collapses to `return a + b`, and the lazy ST dictionary web disappears. - Golden.LongDoBlock is byte-identical (was already lowered). - LongMaybe/Either/Writer/State/Stack Bind goldens are byte-identical; LongExcept/LongReader move by supply renumbering only (their mains are Effect-typed) -- the discard rewrite did not leak into non-Effect monads. - No golden gained a closure, and no golden.lua keeps bindEffect/bindST/applicative* method-call residue in chain position. - bench/ci fnew counters match the committed oracles (zero delta).
Contributor
There was a problem hiding this comment.
Pull request overview
This PR strengthens the PureScript→Lua IR “magic-do” lowering for Effect/ST by switching chain recognition from fragile syntactic-shape matching to qualified-name matching via canonicalization of dictionary applications (issue #182). It also includes two correctness fixes uncovered while building the new coverage, plus new unit and golden tests demonstrating the previously-missed shapes.
Changes:
- Canonicalize
Effect/STdictionary applications to the real foreign method heads (bindE/pureE,bind_/pure_) during CoreFn→IR translation and again in the optimizer (post-linker requalification). - Update MagicDo to match canonical heads (direct ref / dissolved foreign accessor / one-hop alias) and add a peephole to collapse
App (pure x) EffectRunArgtox. - Add new unit/golden tests and re-accept goldens to reflect the new lowering and the two bug fixes (freshening discard binders; preventing local inlining of effect-run statements).
Reviewed changes
Copilot reviewed 68 out of 68 changed files in this pull request and generated no comments.
Show a summary per file
| File | Description |
|---|---|
| test/ps/src/Golden/STDoBlock/Test.purs | New golden source for ST do-chain lowering. |
| test/ps/src/Golden/MixedEffectSTDo/Test.purs | New golden source mixing Effect/ST chains. |
| test/ps/src/Golden/EffectPureChain/Test.purs | New golden source exercising mid-chain/tail pure. |
| test/ps/output/Golden.Uncurry.Test/golden.lua | Re-accepted Lua output (supply/shape changes). |
| test/ps/output/Golden.Uncurry.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.UncurriedLift.Test/golden.lua | Re-accepted Lua output; ST core simplified. |
| test/ps/output/Golden.UncurriedLift.Test/golden.ir | Re-accepted IR output for lifted/ST simplification. |
| test/ps/output/Golden.TailRecM2Shadow.Test/golden.lua | Re-accepted Lua output reflecting effect-run fixes/canonical heads. |
| test/ps/output/Golden.STDoBlock.Test/golden.lua | New golden Lua output for ST do-chain. |
| test/ps/output/Golden.STDoBlock.Test/golden.ir | New golden IR output for ST do-chain. |
| test/ps/output/Golden.STDoBlock.Test/eval/golden.txt | New ST golden eval oracle output. |
| test/ps/output/Golden.STDoBlock.Test/eval/.gitignore | Ignore actual eval output for ST golden. |
| test/ps/output/Golden.STDoBlock.Test/corefn.json | New CoreFn fixture for ST golden. |
| test/ps/output/Golden.Primops.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.Primops.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.NumberIsNaN.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.NumberIsNaN.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.MixedEffectSTDo.Test/golden.lua | New golden Lua output for mixed Effect/ST module. |
| test/ps/output/Golden.MixedEffectSTDo.Test/golden.ir | New golden IR output for mixed Effect/ST module. |
| test/ps/output/Golden.MixedEffectSTDo.Test/eval/golden.txt | New mixed-module eval oracle output. |
| test/ps/output/Golden.MixedEffectSTDo.Test/eval/.gitignore | Ignore actual eval output for mixed golden. |
| test/ps/output/Golden.MixedEffectSTDo.Test/corefn.json | New CoreFn fixture for mixed golden. |
| test/ps/output/Golden.MaybeChain.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.MaybeChain.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.Loopification.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.Loopification.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.LongReaderBind.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.LongReaderBind.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.LongExceptBind.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.FloatIn.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.FieldCaching.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.FieldCaching.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.EffectPureChain.Test/golden.lua | New golden Lua output showing pure collapse. |
| test/ps/output/Golden.EffectPureChain.Test/golden.ir | New golden IR output for pure collapse coverage. |
| test/ps/output/Golden.EffectPureChain.Test/eval/golden.txt | New Effect+pure eval oracle output. |
| test/ps/output/Golden.EffectPureChain.Test/eval/.gitignore | Ignore actual eval output for EffectPureChain golden. |
| test/ps/output/Golden.EffectPureChain.Test/corefn.json | New CoreFn fixture for EffectPureChain golden. |
| test/ps/output/Golden.Issue37.Test/golden.lua | Re-accepted Lua output reflecting canonical pureE usage. |
| test/ps/output/Golden.Issue37.Test/golden.ir | Re-accepted IR output reflecting canonical pureE usage. |
| test/ps/output/Golden.HelloPrelude.Test/golden.lua | Re-accepted Lua output; eliminates unused Effect dictionary scaffolding. |
| test/ps/output/Golden.HelloPrelude.Test/golden.ir | Re-accepted IR output consistent with simplified Effect usage. |
| test/ps/output/Golden.GenericEqTwoTypes.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.DerivedFunctor.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.CharLiterals.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.CharLiterals.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.BugListGenericEq.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.BugListGenericEq.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.ArrayPatternMatch.Test/golden.lua | Re-accepted Lua output (binder renumbering). |
| test/ps/output/Golden.ArrayPatternMatch.Test/golden.ir | Re-accepted IR output (binder renumbering). |
| test/ps/output/Golden.ArrayOfUnits.Test/golden.lua | Re-accepted Lua output reflecting canonical pureE usage. |
| test/ps/output/Golden.ArrayOfUnits.Test/golden.ir | Re-accepted IR output reflecting canonical pureE usage. |
| test/Main.hs | Wires the new MagicDo spec into the test suite. |
| test/Language/PureScript/Backend/IR/Types/Spec.hs | Adds regression for discard binder freshening. |
| test/Language/PureScript/Backend/IR/Spec.hs | Adds translation-tier canonicalization unit tests. |
| test/Language/PureScript/Backend/IR/Optimizer/Spec.hs | Adds optimizer-tier canonicalization + no-inline effect-run regression. |
| test/Language/PureScript/Backend/IR/MagicDo/Spec.hs | New unit tests for name-based MagicDo and peephole/chunking. |
| pslua.cabal | Exposes new EffectNames module and MagicDo tests. |
| lib/Language/PureScript/Backend/Lua/ForeignLift.hs | Updates allowlist warning to reflect name-based MagicDo recognition. |
| lib/Language/PureScript/Backend/IR/Types.hs | Adds rewriteExpTopDown and tightens freshenBinders around discard binders; documents effect-run invariants. |
| lib/Language/PureScript/Backend/IR/Optimizer.hs | Adds canonicalization rewrite rule; prevents inlining effect-run statements; updates pipeline docs. |
| lib/Language/PureScript/Backend/IR/EffectNames.hs | New module defining canonical heads + dictionary-application canonicalizer. |
| lib/Language/PureScript/Backend/IR.hs | Applies canonicalization during CoreFn→IR application construction. |
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 #182.
MagicDo used to recognize Effect/ST do-chains by syntactic shape: unwinding application spines with fuel, chasing aliases, projecting fields out of dictionary literals, and speculatively beta-reducing. Any rewrite that changed a chain's shape could silently starve it, and a miss fell back to thunk-nested closures. This PR switches recognition to qualified names.
The change canonicalizes Effect/ST dictionary applications into applications of the real foreign methods (
Effect.bindE/pureE,Control.Monad.ST.Internal.bind_/pure_). This is compile-time dictionary projection, exact by the instance definitions (bindEffect.bind = bindEand so on), and any residual magicDo never lowers stays executable at runtime. The rewrite runs in two tiers: at CoreFn translation (applications build bottom-up, so nested pairs compose; covers cross-module uses and the purs CSE floats) and as an optimizer rule (a same-module dictionary reference isLocaluntil the linker requalifies it). Details inNote [Canonical Effect/ST heads].MagicDo then matches the canonical heads through three lenses: a direct reference, the dissolved foreign-accessor read, and one top-level alias hop. The fueled unwinding, alias chasing, dictionary projection and speculative beta are gone, and with
substituteMoveMout the pass is pure. New on top: a pure run peephole,App (pure x) EffectRunArg -> x, which collapses pure-terminated tails, mid-chainx <- pure estatements, and the pre-existing runs from the foreign lifter'srun*Fnwrappers. Emission (chunking,EffectRunArg) and pipeline order are unchanged.Two pre-existing miscompiles, found and fixed first
Two of the new golden modules tripped the checked pipeline's
DuplicateBinderlint onmain, and once compiling, one printed its effects twice. The branch therefore starts with two independent fixes, each demonstrated red first by a unit test:inlineLocalBinding's use-once path pasted an effect-run RHS (x = m $magicDoRun) into the Let body. DCE deliberately keeps such statements even when unreferenced, so the paste left two copies and the effect executed twice at runtime.Golden.TailRecM2Shadowwas affected onmain: itsmainre-ran the wholetailRecMmachinery inside the log argument, on top of the kept binding of the same computation.freshenBindersrenamed all Let-bound names through one name-keyed map. A pasted magicDo thunk binds several statements to the GUC-exempt discard binder_, so they all collapsed to the same fresh name, and the checked pipeline failed withDuplicateBinderin the specialize pass.Commits
fix(optimizer): keep effect runs out of local inlining (the double-execution bug).fix(ir): keepfreshenBindersfrom collapsing discard binders.test(golden): pin the missed shapes at current output (EffectPureChain, STDoBlock, MixedEffectSTDo, with hand-written eval oracles), so the feature's re-accept diff is its own demonstration.feat(ir): the canonicalization + name-based MagicDo + unit specs (written red against the old code where they could compile).test(golden): re-accept, net -1632 golden lines.Verification
eval/golden.txtoracle untouched and passing.Golden.LongDoBlockbyte-identical.LongMaybe/Either/Writer/State/Stackbind goldens byte-identical;LongExcept/LongReadermove by supply renumbering only (their mains are Effect-typed), so the discard rewrite did not leak into non-Effect monads.golden.luakeepsbindEffect/bindST/applicative*method-call residue in chain position.bench/cifnew counters match the committed oracles.Sample of the payoff,
Golden.EffectPureChain(104 -> 30 lines, whole Effect dictionary web and thePSLUA_runtime_lazyfixture DCE'd away):And
Golden.UncurriedLift'ssumSTcollapses toreturn a + b.Follow-ups deliberately left out: flipping
SkipCallSitespre-magicDo (now conservative caution rather than a recognition constraint) and lifting the Effect/ST core behind the canonical names (#228).