Fold constant chains within a sweep instead of one fixpoint round per layer - #361

Closes #328.

The problem

The IR optimizer runs several of its passes as fixpoints: a group of passes is applied to the whole linked module over and over until a round changes nothing. One of them, specialize+dce, is where a monadic bind chain collapses — call-site inlining pastes the bind method bodies in, and the case-of-known-constructor folds then reduce the resulting matches to straight-line code.

That fixpoint took 301 rounds on Golden.LongBindFlipped, a ~300-deep chain of =<< over Maybe, and 3–4 rounds on everything else in the corpus. One round per layer, measured by tracing the round count of every fixpoint in the pipeline:

("ROUNDS","optimize+dce",4)
("ROUNDS","optimize+dce-post-merge",2)
("ROUNDS","optimize+dce-post-uncurry",2)
("ROUNDS","specialize+dce",301)          <-- ~300-deep chain, ~300 rounds
("ROUNDS","specialize+dce-post-cpr",1)

Each round is a sweep of the whole module, so compile time was O(depth × module size). #327 raised the fixpoint's iteration backstop (maxFixpointIterations, the cap that stops a genuinely looping pass from spinning forever) from 100 to 1000 to keep the invariant-checking test runner from reporting these legitimate rounds as divergence — which also meant a real loop bug had to burn 1000 whole-module sweeps before being reported.

Why one layer per round

Not the growth veto and not the nested-rewrite bound — instrumenting both showed no sweep was ever vetoed, and the chain shrank by ~10 nodes per round, exactly one layer. Dumping the expression before and after one sweep of round 2 shows what actually blocks:

BEFORE (innermost layer)                    AFTER (same sweep)
  Let (a$4504 = Just 2)                       Let ($field4527 = 2)
    (if justTag == reflectCtor a$4504            (Just 3)
       then Just (arg0 a$4504 + 1)
       else Nothing)

The fold worked — the match collapsed, the payload was inlined, 2 + 1 folded to 3. But it left $field4527 behind: propagateKnownCtorThroughLet, the rule that pushes a known constructor into a let-bound scrutinee's reads, binds each read field to a fresh $field binder (so an argument read at several sites is evaluated once, not copied). When the reads then fold away, that binder is unreferenced — and nothing in the rewrite rule set dropped an unreferenced Let binding. Only the separate dce pass did, one pass later in the round. That matches the per-pass trace: specialize and dce each reported Rewritten on 300 consecutive rounds, then both went quiet.

While the residue stands, the enclosing layer's right-hand side is a Let rather than the Just 3 it wraps, so propagateKnownCtorThroughLet declines there — it needs a saturated constructor. The chain advances one layer, dce clears the residue, and the next round advances one more.

The change

Dropping an unread binding becomes a rewrite as well, so a cascade completes inside the sweep that starts it:

removeUnusedLetBindings ∷ Applicative m ⇒ RewriteRuleM m Ann
removeUnusedLetBindings =
  pure . \case
    Let ann groupings body
      | let kept = snd (foldr keep (countFreeRefs body, []) groupings)
      , length kept < length groupings →
          Just case nonEmpty kept of
            Nothing → body
            Just keptNE → Let ann keptNE body
    _ → Nothing

The licence to discard an unread binding's right-hand side is the one eliminateDeadCode already takes: an effect run stays (dropping it would silently discard the effect), anything else is evaluated for a value nothing wants.

  keep grouping (refs, kept) = case grouping of
    Standalone (_ann, name, rhs)
      | Local name `Map.notMember` refs
      , not (isEffectRun rhs) →
          (refs, kept)
    _ → (…refs plus this grouping's own references…, grouping : kept)

Bindings are decided right to left and only a kept grouping contributes its references, so a binding kept alive solely by a binding that is itself dropped goes with it. The direction matters because a Let's bindings scope sequentially — a binder is in scope for the groupings after it and the body, never the ones before (Note [Sequential scoping of Let bindings]). Recursive groups are left to dce, which sees a dead group as a whole through module-level reachability.

maxFixpointIterations returns to 100. With convergence no longer depth-scaled the bound can sit close to real work, so a pass that over-reports changes is caught in 100 sweeps instead of 1000.

Verification

Round count, measured the same way as above. The three ~300-deep stress modules now converge in the same number of rounds as a three-deep chain, and the deepest fixpoint anywhere in the 348-example golden corpus takes 4:

The new cap is itself the regression guard: the stress goldens are ~300 layers deep, so any return to per-layer folding exceeds 100 rounds and the checked runner used by the test suite fails with FixpointDivergence rather than merely getting slower.

Compile time, best of three runs each, spec --match <module>:

Unit-level pin (red before the fix, in its own commit). Eight layers nested one in another must fold to their final constant in a single optimizedExpression sweep. Verbatim failure without the fix — one layer folded, the other seven untouched:

expected: Ctor … (CtorName "Just") [LiteralInt Nothing 8]
 but got: Let (v1, Let (v2, … Let (v7,
            Let ($field0 = LiteralInt Nothing 0) (Just [LiteralInt Nothing 1]))
            (if justTag == reflectCtor v7 then Just [arg0 v7 + 1] else Nothing)) …)

Goldens. 346 of 348 byte-identical. Golden.LongWriterBind moves, in the direction the collapse intends: its 200-deep Writer chain used to compile to a nest of closures over tell/discard plus the Data.Identity dictionary tables, and now compiles to straight-line code — 847 lines of Lua down to 234:

-- before
local Data_Identity_applyIdentity = { apply = …, Functor0 = … }
local Data_Identity_applicativeIdentity = { pure = …, Apply0 = … }
local Golden_LongWriterBind_Test_tell = function(x_S_1) return { Data_Unit_unit, x_S_1 } end
local Golden_LongWriterBind_Test_go = (function()
  local _S_kont0 = Golden_LongWriterBind_Test_discard_S_w(Golden_LongWriterBind_Test_tell({
    [1] = 161
  }), function()
    return Golden_LongWriterBind_Test_discard_S_w(Golden_LongWriterBind_Test_tell({
    -- … 200 nested closures …

-- after
local Golden_LongWriterBind_Test_go = {
  42,
  ((function()
    local _S_tmp0 = Data_Semigroup_concatArray({ [1] = 162 })(…)
    -- … flat concatArray spine in A-normalised locals …

The accumulated result is now the literal 42, computed at compile time. The module's eval/golden.txt oracle (42) is unchanged, so the collapse is semantics-preserving where execution checks it.

Four existing expectations in the optimizer spec moved with the rule. Each asserted the pre-dce residue — let1 name inlinee inlinee where the paste had just consumed the body's only reference — and now expects the bare inlinee. They still pin the paste: a result that kept the Let would mean the inlining never happened. One of them becomes identical to its beta-reduced sibling two tests down, which previously already expected the bare literalInt 5.

cabal test all is green (1247 examples). The optimizer's Hedgehog groups were re-run under 14 fresh seeds, all clean with no hangs. A forced full recompile of the library and test suite emits no warnings; hlint reports no hints.

Sibling audit

The shape here is "a rewrite leaves residue only a later pass clears, so a cascade stalls at one layer per round". Searched the rest of the rule set for the same shape:

• LetValues (the multi-value binding CPR introduces) has the same asymmetry: eliminateDeadCode collapses one whose every binder is dead, and no rule in the sweep does. No instance shows up in the corpus — the specialize+dce-post-cpr fixpoint peaks at 2 rounds across all 348 goldens — and this PR's rule deliberately does not cover it, since the red would have to be a shape I invent rather than one the corpus produces. Recorded as a follow-up rather than fixed blind.
• Dead parameter blanking (blankDeadSuffix, also DCE-only) does not gate any fold: the rules match on node structure, not on binder names.
• Top-level binding elimination is per-round by construction, but withBinding folds all bindings in one pass, substituting into later ones, so a chain of top-level bindings does not need a round each. No depth scaling observed.