Let a rewrite-budget exhaustion stop the enclosing pass fixpoint #352

Problem

pslua's IR optimizer runs its passes inside fixpoint combinators: RunFixpoint "optimize+dce" re-runs optimize and dce until a whole round reports no change, bounded by maxFixpointIterations (1000). Whether a round changed anything comes from each pass's WasRewritten flag, which the fixpoint trusts:

      loop ∷ Natural → UberModule → SupplyM UberModule
      loop 0 uber = pure uber -- cap reached: accept (see the module doc)
      loop n uber =
        runRound passRun uber (toList passes) >>= \case
          (uber', Rewritten) → loop (n - 1) uber'
          (uber', Unmodified) → pure uber'

Below that sits the rewrite driver rewriteExpBottomUpM, which re-applies the rule set at a node until it stops firing — now bounded by maxNestedRewrites (100) so that a term with no normal form cannot livelock it (#348). When that budget runs out the driver abandons the redex and reports Rewritten, which is accurate: it did change the term. But it is also indistinguishable from ordinary progress, so the enclosing fixpoint keeps iterating, advances the same non-converging term by another 100 steps per round, and only stops at its own 1000-round cap.

How it shows up

As wasted work on inputs the optimizer cannot finish, and it is measurable in the test suite that #348 came from. The IR Optimizer spec group used to cost 0.35 s; it now costs about 3 s at every hspec seed, because the example-based regression test added with #348 deliberately drives the budget to exhaustion twice:

$ for s in $(seq 1 500); do timeout 60 $SPEC --match "IR Optimizer" --seed $s; done
worst_elapsed=6s
failures:

The three seeds whose generated draw contains the diverging term add ~2 s on top of that floor (109 → 6 s, 152 and 478 → 5 s). Full-suite wall clock absorbs it at 88 s, so this is a cost worth removing rather than an emergency.

The diagnostic side is the more interesting half. With invariant checking on — runStepsChecked, used by the test suite always and by the CLI behind --lint-ir — the exhausted budget currently surfaces one level too high, as the fixpoint reporting that it never converged:

optimizedUberModuleChecked mempty original
  === Left (FixpointDivergence "optimize+dce" maxFixpointIterations)

That names the fixpoint but not the culprit. The driver knows exactly which node it gave up on and which rule kept firing on it; none of that reaches the report.

Approach

Let budget exhaustion be a distinct outcome rather than collapsing into Rewritten, and let the fixpoint stop on it instead of iterating into its cap.

The plumbing is the cost. rewriteExpBottomUpM returns m (RawExp ann, WasRewritten) and would need a third component (or a richer accumulator in its WriterT); Pass's passRun ∷ UberModule → SupplyM (UberModule, WasRewritten) would need the same, which touches every pass constructed in Language.PureScript.Backend.IR.Optimizer and all three runners in Language.PureScript.Backend.IR.Pass (runSteps, runStepsChecked, runStepsTraced). Language.PureScript.Backend.IR.DCE also drives the bottom-up rewriter and would have to pass the signal through.

Two properties must survive the change. The production runner must keep accepting the module it has reached — every pass is semantics-preserving, so an early stop costs optimization and never correctness, and a compiler that refused to emit code for a term it could not fully normalize would be strictly worse. And Unmodified must keep meaning "structurally identical", since runStepsChecked compares a module a pass claims unchanged against its input and fails with PassUnreportedChange.

The payoff is both halves of the problem at once: the fixpoint stops at the first exhausted round instead of spending 1000, and the checked runner can name the pass, the rule and the node rather than only the fixpoint.

Verification / Measurement

The wall-clock claim is the check: $SPEC --match "IR Optimizer" --seed 109 should drop from ~6 s toward the ~0.35 s the group cost before #348, and the every-seed floor should drop with it. Record before/after numbers rather than asserting an improvement.

The golden corpus must stay byte-identical. No real compilation exhausts the budget — PureScript's type system rejects every term without a normal form — so a change that moves any golden.ir or golden.lua has altered ordinary convergence, not just the give-up path.

The diagnostic improvement wants a test of its own: the #348 regression module should report the offending pass and node, replacing the current assertion that only names optimize+dce.

Prerequisites / Relations

Depends on #348, which is merged: maxNestedRewrites and the give-up path it introduced are what this change makes legible.

Builds on #351, which puts the same bound on the sibling top-down driver: if both drivers end up reporting exhaustion they should report it the same way, so #351 is worth doing first, or the signal designed for both at once. Not a hard blocker — this change stands alone if #351 is dropped.

Acceptance criteria

• An exhausted rewrite budget stops the enclosing fixpoint on the round it happens, instead of iterating to maxFixpointIterations.
• The production pipeline still returns the module reached, with no error path added for a term it could not normalize.
• Under runStepsChecked the report identifies the pass and the abandoned node, not just the fixpoint's name.
• Before/after timings for the IR Optimizer group are recorded, at seed 109 and at a seed that does not draw a diverging term.