refactor!: bottom-up Maybe-based rewrite driver with a precise change flag - #155
Merged
Conversation
…nge flag
Replace the bespoke 'Rewritten NoChange/Recurse/Stop' driver — which
conflated change reporting with descent control — with Maybe-based
rules: 'Nothing' means the rule did not fire, 'Just' means it rewrote.
* rewriteExpBottomUpM ('rewriteMOf subexpressions'): children are
normalized before their parent, and a rule is re-applied to its own
result until it no longer fires, so one pass is complete and
idempotent, and the returned Any flag is precise by construction —
the groundwork for replacing the whole-module Eq fixpoint oracle
(#144). Used by the optimize rule chain and DCE (both fixpoint
members).
* rewriteExpTopDownM stays for the two order-sensitive lowerings that
consume a pattern from the outermost head: magicDo and
flattenDeepBinds (a bottom-up driver would dismantle a do-chain from
the inside, nesting one thunk per step). Their rules already computed
a Maybe internally, so they collapse to it.
* The three over-reporting rules are honest now: the DCE Abs rule
requires ParamNamed (fixes #145), the DCE Let rule fires only when a
binder is actually dropped (the #149 rebuild cascade is subsumed by
bottom-up order — the exposed body is already processed), and
inlineLocalBindings fires only when an occurrence was actually
substituted (a zero-occurrence substitution is a no-op).
Golden churn is minted-name renumbering only (the supply is drawn in
bottom-up order now); verified by re-diffing all 50 changed goldens
with $-suffixes normalized — the single remaining diff is a
pretty-printer line wrap. Eval oracles are untouched and pass: runtime
behavior is unchanged.
Contributor
There was a problem hiding this comment.
Pull request overview
This PR refactors the IR rewrite “driver” infrastructure to use a Maybe-based rule interface and introduces a bottom-up, repeat-until-stable rewrite runner that also produces a precise Any change flag. In this codebase, that rewrite machinery underpins key IR optimization passes (Optimizer/DCE) and is intended to support upcoming work to replace whole-module structural Eq fixpoint detection with change reporting (#144) while avoiding no-op rewrites (#145) and the historical “Recurse-escape” class of bugs (#149).
Changes:
- Replace the bespoke
Rewritten NoChange/Recurse/Stoprule result type withMaybe(Nothing= didn’t fire,Just= rewrote) and document/enforce the “honesty” contract. - Add a bottom-up
rewriteExpBottomUp(M)runner built onrewriteMOfwith aWriterT Anychange flag, and switch Optimizer/DCE to it where ordering permits. - Keep (and re-spec) the top-down driver for order-sensitive passes (MagicDo / FlattenDeepBinds), and add unit tests for driver behavior.
Reviewed changes
Copilot reviewed 58 out of 58 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 Maybe-based rewrite rules, adds bottom-up driver with Any flag, and updates top-down semantics to “repeat at node until Nothing”. |
| lib/Language/PureScript/Backend/IR/Optimizer.hs | Switches optimizer rewrites to bottom-up driver; updates rules to Maybe; fixes inlineLocalBindings to be occurrence-aware and honest. |
| lib/Language/PureScript/Backend/IR/DCE.hs | Switches DCE rewrites to bottom-up driver; makes Abs/Let rules honest (avoids no-op rewrites like ParamUnused lambdas). |
| lib/Language/PureScript/Backend/IR/MagicDo.hs | Updates rewrite rule to Maybe and documents why this pass must remain top-down. |
| lib/Language/PureScript/Backend/IR/FlattenDeepBinds.hs | Updates rewrite rule to Maybe and documents why this pass must remain top-down. |
| test/Language/PureScript/Backend/IR/Types/Spec.hs | Adds unit tests covering bottom-up ordering, idempotence, and top-down “repeat-at-node” behavior. |
| test/Language/PureScript/Backend/IR/DCE/Spec.hs | Updates commentary to reflect the bottom-up driver guarantee for exposed Lets. |
| changelog.d/20260704_130000_unisay_bottom_up_rewrite_driver.md | Changelog entry documenting the driver refactor and the no-op rewrite fixes. |
| test/ps/output/Golden.TailRecM2Shadow.Test/golden.lua | Golden output churn (minted-name numbering / formatting-only differences). |
| test/ps/output/Golden.TailRecM2Shadow.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.StringCodePoints.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.StringCodePoints.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.ProfunctorDictLens.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.ProfunctorDictLens.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.MaybeChainModule.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.MaybeChainModule.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.MaybeChain.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.MaybeChain.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.LongWriterBind.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongWriterBind.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.LongStateBind.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongReaderBind.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongReaderBind.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.LongMaybeBindModule.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongMaybeBindModule.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.LongMaybeBind.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongMaybeBind.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.LongExceptBind.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongEitherBind.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongDoBlock.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongDoBlock.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.LongCallbackChain.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.LongCallbackChain.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.LongBindFlipped.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.LongApplyChain.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.Issue37.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.Issue37.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.GenericEqTwoTypes.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.GenericEqTwoTypes.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.FloatIn.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.FloatIn.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.DerivedFunctor.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.DerivedFunctor.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.CharLiterals.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.CharLiterals.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.BugListGenericEq.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.BugListGenericEq.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.ArrayPatternMatch.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.ArrayPatternMatch.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
| test/ps/output/Golden.ArrayOfUnits.Test/golden.lua | Golden output churn (minted-name numbering differences). |
| test/ps/output/Golden.ArrayOfUnits.Test/golden.ir | Golden IR churn (minted-name numbering differences). |
CI hung for five hours on PR #155 (run 28702999696): the 'inlines references' test draws its binder name and inlinee reference from the same seven-name pool, so with probability 1/7 it produces the non-GUC shape 'let x = x in x'. Substituting x := x is a textual no-op — the occurrence count of x never reaches zero — so the bottom-up driver's repeat-until-Nothing re-fired inlineLocalBindings forever. The old top-down driver applied the rule once per node visit and left convergence to the outer Eq fixpoint, which saw identical modules and stopped; the new driver has no such implicit backstop. Guard the rule: a binding whose RHS references its own name is never inlined. Besides restoring termination this also prevents the latent capture bug of the same shape (the pasted copy's free self-reference would be captured by the very binding it names). Under GUC the guard never fires — a Standalone RHS cannot see its own binder — so pipeline behavior and goldens are unchanged; only direct optimizedExpression calls on non-GUC input are affected. The generators of the two inlining tests now respect the non-self- referential domain, and a regression test pins the declining behavior ('declines to inline a self-referential binding').
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 #145. Second PR of the stack on top of the traversal consolidation; the fixpoint oracle switch (#144) builds on this.
The old driver's
Rewritten NoChange/Recurse/Stopconflated two concerns: whether a rule changed anything, and whether the driver should descend. Since the driver descended onNoChangeanyway, "rebuild-and-Recurse" and "NoChange" behaved identically while carrying opposite change bits. As a result, several rules fired on every node of their shape without changing anything: the DCE lambda rule on everyParamUnusedlambda (#145), the DCELetrule andinlineLocalBindingson everyLet. That over-reporting is what blocked #144.The new shape, following the uniplate/lens idiom:
RawExp ann → m (Maybe (RawExp ann)):Nothingmeans "did not fire",Justmeans "rewrote". The honesty contract (returnJustonly on a real change) is now part of the type's meaning, and the checked runner will enforce it mechanically once idempotently detects the fixpoint by deep Eq on the whole UberModule #144 lands.rewriteExpBottomUpMisrewriteMOf subexpressionsplus aWriterT Anychange flag: children are normalized before their parent, and a rule is re-applied to its own result until it stops firing. One pass is complete and idempotent, which also closes the Recurse-escape bug class from First-class passes for the IR pipeline: Pass values, invariant checks, deterministic name supply #149 structurally: the DCE rebuild cascade is gone, because a collapsingLetcan only expose an already-processed body.rewriteExpTopDownMsurvives (Maybe-based) for the two lowerings that genuinely need outside-in order. magicDo and flattenDeepBinds consume chains from the outermost head, and every tail of such a chain is itself a chain head, so a bottom-up driver would rewrite the tails first into per-step nested thunks and defeat the flattening those passes exist for. Both module headers document this.inlineLocalBindingsnow checks the occurrence count before substituting: a zero-occurrence substitution is recognized as the no-op it is, which is also what makes the rule terminate under repeat-until-Nothing.Verification: the golden churn (50 files) is minted-name renumbering only. I re-diffed every changed golden with
$-suffix numbers normalized, and the single remaining diff is a pretty-printer line wrap caused by a name length. The hand-verified eval oracles are untouched and pass, so runtime behavior is unchanged. New driver unit tests cover the flag honesty, bottom-up ordering, one-pass idempotence, and the top-down repeat-at-node behavior.