Skip to content

refactor!: bottom-up Maybe-based rewrite driver with a precise change flag - #155

Merged
Unisay merged 2 commits into
mainfrom
issue-145/bottom-up-rewrite-driver
Jul 4, 2026
Merged

refactor!: bottom-up Maybe-based rewrite driver with a precise change flag#155
Unisay merged 2 commits into
mainfrom
issue-145/bottom-up-rewrite-driver

Conversation

@Unisay

@Unisay Unisay commented Jul 4, 2026

Copy link
Copy Markdown
Collaborator

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/Stop conflated two concerns: whether a rule changed anything, and whether the driver should descend. Since the driver descended on NoChange anyway, "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 every ParamUnused lambda (#145), the DCE Let rule and inlineLocalBindings on every Let. That over-reporting is what blocked #144.

The new shape, following the uniplate/lens idiom:

  • Rules are RawExp ann → m (Maybe (RawExp ann)): Nothing means "did not fire", Just means "rewrote". The honesty contract (return Just only 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.
  • rewriteExpBottomUpM is rewriteMOf subexpressions plus a WriterT Any change 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 collapsing Let can only expose an already-processed body.
  • rewriteExpTopDownM survives (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.
  • inlineLocalBindings now 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.

…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.
@Unisay
Unisay requested a review from Copilot July 4, 2026 15:06
@Unisay Unisay self-assigned this Jul 4, 2026
@Unisay
Unisay marked this pull request as ready for review July 4, 2026 15:06
@Unisay
Unisay deleted the branch main July 4, 2026 15:06
@Unisay Unisay closed this Jul 4, 2026
@Unisay Unisay reopened this Jul 4, 2026
@Unisay
Unisay changed the base branch from refactor/ir-traversals to main July 4, 2026 15:09

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 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/Stop rule result type with Maybe (Nothing = didn’t fire, Just = rewrote) and document/enforce the “honesty” contract.
  • Add a bottom-up rewriteExpBottomUp(M) runner built on rewriteMOf with a WriterT Any change 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').
@Unisay
Unisay merged commit bfb785d into main Jul 4, 2026
2 checks passed
@Unisay
Unisay deleted the issue-145/bottom-up-rewrite-driver branch July 4, 2026 15:29
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.

IR DCE performs a no-op rewrite on every Abs with ParamUnused

2 participants