perf: drive optimizer fixpoints by change flags instead of whole-module Eq - #156
Merged
Conversation
Unisay
force-pushed
the
issue-144/fixpoint-change-flag
branch
from
July 4, 2026 15:21
c932082 to
b91aad2
Compare
Unisay
marked this pull request as ready for review
July 4, 2026 15:29
Contributor
There was a problem hiding this comment.
Pull request overview
This PR updates the IR pass framework and optimizer fixpoint execution to stop iterating based on per-pass change flags rather than deep structural Eq of whole UberModules, eliminating repeated whole-module equality checks while adding explicit checks for dishonest change reporting in the checked runner.
Changes:
- Extend
Pass.passRunto return(UberModule, Any)and implement flag-driven fixpoint looping with a hard cap (maxFixpointIterations). - Add checked-runner enforcement for under-reporting (
PassUnreportedChange) and non-converging fixpoints (FixpointDivergence), with corresponding CLI rendering and tests. - Update Optimizer/DCE to report precise change flags (optimize aggregates rewrite-driver flags + top-level inlining; DCE reports expression rewrites plus drops/prunes).
Reviewed changes
Copilot reviewed 6 out of 6 changed files in this pull request and generated no comments.
Show a summary per file
| File | Description |
|---|---|
lib/Language/PureScript/Backend/IR/Pass.hs |
Reworks pass runner API and fixpoint convergence to use change flags; adds checked-runner failures and iteration cap. |
lib/Language/PureScript/Backend/IR/Optimizer.hs |
Threads change flags through optimize pass via WriterT Any; updates pipeline pass definitions for new passRun signature. |
lib/Language/PureScript/Backend/IR/DCE.hs |
Makes DCE return (UberModule, Any) and aggregates precise flags for rewrites/drops/prunes. |
test/Language/PureScript/Backend/IR/Pass/Spec.hs |
Updates tests for new PassCheckFailure shape and adds coverage for under-reporting and divergence behavior. |
test/Language/PureScript/Backend/IR/DCE/Spec.hs |
Updates DCE tests to assert both output and correctness of the change flag. |
changelog.d/20260704_140000_unisay_fixpoint_change_flag.md |
Documents the behavioral change and new checked-runner failure modes. |
Unisay
commented
Jul 4, 2026
| -- The binding is dropped from the module in favor of the | ||
| -- substituted copies: a change even when it had no | ||
| -- occurrences left to substitute. | ||
| tell (Any True) |
Collaborator
Author
There was a problem hiding this comment.
I think this expression is not telling about its purpose: I'd like to see a self documenting code, something like:
registerRewrite
where registerRewrite could be defined at the bottom or elsewhere as registerRewrite = tell (Any True)
or even better, avoid "boolean blindness" and use a dedicated data type with its own monoid instance, i.e.
data Rewrite = Rewritten | Unmodified
instance Monoid Rewrite ...
-- then
tell Rewritten -- <- reads much better, no explanatory comment needed
Unisay
commented
Jul 4, 2026
| optimizedExpressionM = fmap fst . optimizedExpressionFlagM | ||
|
|
||
| -- | 'optimizedExpressionM' plus the driver's change flag (issue #144). | ||
| optimizedExpressionFlagM ∷ Exp → SupplyM (Exp, Any) |
Collaborator
Author
There was a problem hiding this comment.
Follow up to the comment above, this reads much nicer:
optimizedExpressionFlagM ∷ Exp → SupplyM (Exp, Rewrite)
Try to find a better name for the datatype that reflects the property of AST that it has been rewritten in one word, or maybe WasRewritten is really non-ambigous
…back) Boolean blindness: 'tell (Any True)' needed a comment to say what the boolean means. Introduce a dedicated type next to the drivers — data WasRewritten = Rewritten | Unmodified with a 'Rewritten wins' Semigroup and 'Unmodified' mempty — so the drivers return (RawExp ann, WasRewritten) and use sites read 'tell Rewritten' / case-match on the outcome without commentary. Also trims issue references from comments down to genuine bug pointers, per the same review.
…le Eq Closes #144. Every passRun now returns (UberModule, Any): 'Any False' asserts the output is structurally identical to the input, 'Any True' says it may differ. The fixpoint members report precisely — optimize aggregates the driver flag across all expressions plus every top-level inlining; dce combines its driver flag with top-level binding/foreign drops and ForeignImport name-list pruning. Run-once passes report a conservative 'Any True', which nothing consumes. A fixpoint stops on the first round reporting no change, bounded by maxFixpointIterations (100); no runner compares whole modules anymore. The dishonesty directions are split per runner: the checked runner (test suite, --lint-ir) fails with PassUnreportedChange when a pass changes the module while claiming it didn't (the one surviving, targeted Eq — paid only in checked mode and only on a no-change claim), and with FixpointDivergence at the cap; the production runner accepts the module reached at the cap — every pass is semantics-preserving, so an early stop costs optimization, never correctness, and production can no longer hang. 'idempotently' stays as the semantic reference (a property test pins the flag-driven fixpoint to it for honest flags); fixpointM is gone. Since the golden harness runs the checked pipeline, every fixpoint round of every golden now asserts flag honesty. No golden moved: with honest flags the fixpoint stops at exactly the round the Eq oracle did.
Unisay
force-pushed
the
issue-144/fixpoint-change-flag
branch
from
July 4, 2026 15:59
b91aad2 to
5f85684
Compare
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 #144. Builds on the bottom-up driver (#155, merged).
fixpointMdetected convergence by deepEqon the wholeUberModuleevery round. Now that the rewrite driver reports precisely whether it rewrote anything, the passes can just say so:Any:data WasRewritten = Rewritten | Unmodifiedwith a "Rewritten wins" Semigroup, so use sites readtell Rewrittenand signatures readSupplyM (Exp, WasRewritten).passRunreturns(UberModule, WasRewritten).Unmodifiedasserts the output is structurally identical to the input;Rewrittensays it may differ. The fixpoint members report precisely: optimize aggregates the driver signal across all expressions plus every top-level inlining, and dce combines its driver signal with top-level binding/foreign drops andForeignImportname-list pruning. Run-once passes report a conservativeRewritten, which nothing consumes.Unmodified, bounded bymaxFixpointIterations(100). No runner compares whole modules anymore.--lint-ir) compares the one module a pass claims unchanged against its input and fails withPassUnreportedChange. Over-reporting (said it changed but didn't) would spin the loop, so at the cap the checked runner fails withFixpointDivergencewhile the production runner accepts the module reached so far. Every pass is semantics-preserving, so an early stop costs optimization, never correctness, and production can no longer hang.idempotentlystays as the semantic reference: a property test checks that the signal-driven fixpoint computes exactly what the Eq-driven reference computes when the signal is precise.fixpointMis gone.Since the golden harness runs the checked pipeline, every fixpoint round of every golden test now asserts the signal's precision for free. No golden moved: the fixpoint stops at exactly the round the Eq oracle did, drawing the same supply names.
To be honest about the payoff: the raw perf win is modest, since
Eqshort-circuits on the first difference and only pays a full traversal on the final converged round. The real gains are a precise per-pass signal, loud failures when it misreports, and the per-pass delta that #142/#143 can build on.