Skip to content

MagicDo: recognize Effect/ST chains by qualified name - #259

Merged
Unisay merged 5 commits into
mainfrom
issue-182/magic-do-by-qualified-name
Jul 13, 2026
Merged

MagicDo: recognize Effect/ST chains by qualified name#259
Unisay merged 5 commits into
mainfrom
issue-182/magic-do-by-qualified-name

Conversation

@Unisay

@Unisay Unisay commented Jul 13, 2026

Copy link
Copy Markdown
Collaborator

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 = bindE and 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 is Local until the linker requalifies it). Details in Note [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 substituteMoveM out the pass is pure. New on top: a pure run peephole, App (pure x) EffectRunArg -> x, which collapses pure-terminated tails, mid-chain x <- pure e statements, and the pre-existing runs from the foreign lifter's run*Fn wrappers. 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 DuplicateBinder lint on main, 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.TailRecM2Shadow was affected on main: its main re-ran the whole tailRecM machinery inside the log argument, on top of the kept binding of the same computation.
  • freshenBinders renamed 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 with DuplicateBinder in the specialize pass.

Commits

  1. fix(optimizer): keep effect runs out of local inlining (the double-execution bug).
  2. fix(ir): keep freshenBinders from collapsing discard binders.
  3. 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.
  4. feat(ir): the canonicalization + name-based MagicDo + unit specs (written red against the old code where they could compile).
  5. test(golden): re-accept, net -1632 golden lines.

Verification

  • Full suite green (853 examples), checked pipeline linting every pass boundary.
  • Every eval/golden.txt oracle untouched and passing.
  • Golden.LongDoBlock byte-identical. LongMaybe/Either/Writer/State/Stack bind goldens byte-identical; LongExcept/LongReader move by supply renumbering only (their mains are Effect-typed), so the discard rewrite did not leak into non-Effect monads.
  • No golden gained a single closure, and no golden.lua keeps bindEffect/bindST/applicative* method-call residue in chain position.
  • bench/ci fnew counters match the committed oracles.

Sample of the payoff, Golden.EffectPureChain (104 -> 30 lines, whole Effect dictionary web and the PSLUA_runtime_lazy fixture DCE'd away):

M.Golden_EffectPureChain_Test_count = function(n)
  return function()
    local _ = Effect_Console_log(...)()
    local x = n + 1
    local _ = Effect_Console_log(...)()
    return x + x * 2
  end
end

And Golden.UncurriedLift's sumST collapses to return a + b.

Follow-ups deliberately left out: flipping SkipCallSites pre-magicDo (now conservative caution rather than a recognition constraint) and lifting the Effect/ST core behind the canonical names (#228).

Unisay added 5 commits July 12, 2026 23:11
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).
@Unisay Unisay self-assigned this Jul 13, 2026
@Unisay
Unisay requested a review from Copilot July 13, 2026 07:30

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 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/ST dictionary 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) EffectRunArg to x.
  • 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.

@Unisay
Unisay merged commit cf42647 into main Jul 13, 2026
3 checks passed
@Unisay
Unisay deleted the issue-182/magic-do-by-qualified-name branch July 13, 2026 07:56
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.

MagicDo: recognize Effect/ST chains by qualified name at translation instead of by shape (removes the post-DCE ordering constraint)

2 participants