SpecConstr: specialize recursive functions on known-constructor call patterns - #279

Closes #208.

A recursive function with a constructor accumulator builds the box on every iteration and takes it apart at the top of the next one. This PR brings GHC's SpecConstr discipline to the IR: when a recursive-group member scrutinizes a parameter and its recursion passes a known constructor at that position, the pass mints a specialized copy that takes the constructor's fields as separate parameters, then rewrites every qualifying call site to it. The boxed original survives as the entry point for callers that don't know the constructor.

The canonical fold now compiles to a loop with no allocation in it. Before:

go = function(acc)
  while true do
    local i = acc[2]
    if i < n then
      acc = Data_Tuple_Tuple_S_w(acc[1] + i, i + 1)  -- a table per iteration
    else
      return acc
    end
  end
end

After:

go_S_sc1Tuple = function(s, i)
  while true do
    if i < n then
      s, i = s + i, i + 1
    else
      return { s, i }  -- the box exists only where it escapes
    end
  end
end

How it works

The pass itself folds nothing. The specialized body is a binder-freshened copy of the original with every read of the specialized parameter replaced by a rebox (Tuple f1 f2 over the new field parameters). It rides in the specialize+dce fixpoint, so the next optimize round's case-of-known-constructor folds (#177/#214) collapse the reboxes at eliminating reads into the tag string and the field references. A rebox at a whole-value read (the exit path above) stays, which is exactly right: it allocates where the box escapes, not per iteration.

Guards follow GHC's: recursive bindings only, the scrutiny requirement (specializing an unscrutinized box would just move the allocation), the pattern must come from the group's own call sites, and a per-binding cap (specConstrLimit = 3, the -fspec-constr-count analogue). Instead of iterating to a fixpoint internally, one run mints one specialization layer and the enclosing specialize+dce fixpoint provides the bounded iteration. Specializations are pattern-keyed by name (<f>$sc<pos><Ctor>), so a rerun that meets a known pattern reuses the existing binding instead of minting a duplicate, and the pass reports Unmodified once no unhandled pattern remains.

Rewriting applies module-wide, not just inside the group: the entry call go (Tuple 0 0) qualifies too, which is what lets DCE drop the boxed entry entirely when nobody boxed is left calling it (visible in the golden: sumCount keeps only the specialized loop).

The known-constructor resolution cluster (resolveKnownCtorApp and friends) moved from the optimizer into IR.Query so the new pass can share it without an import cycle. It now returns a CtorShape record instead of a tuple, since the specializer needs the constructor's identity to rebuild the rebox, not just its tag.

Covered shapes

The golden test pins four cases: a product-type Tuple accumulator (fully unboxed, boxed entry DCE'd), a sum-type Maybe accumulator (only the Just pattern recurs, tag tests fold away, the Nothing arm stays on the boxed entry), a mutually recursive ping/pong pair carrying the same pattern (both specialize, and the pair loops boxlessly), and a negative control whose boxed parameter is dead (left alone).

Measurements

New tuple_fold macro benchmark, n = 5e6:

PUC Lua gets ~2.5x from dropping the per-iteration table build. LuaJIT is unchanged, and that's expected: its allocation sinking already elided the box inside the trace. The win there is structural (the loop bytecode carries no TNEW, so nothing depends on sinking succeeding) rather than a headline number. The remaining PUC gap to ideal is the add$w worker calls the loop still makes instead of inline +, a pre-existing shape (the main-branch build has the same calls) unrelated to this pass.

Counter goldens pin the specialized shape: Bench.TupleFold.lua:8 JLOOP, blacklisted=0, and the loop body free of table construction.

Tests

cabal test all: 928 examples, 0 failures, including the checked pipeline runner (per-pass invariant linting) over every golden module and the hand-verified eval oracles. Property specs re-run across several seeds. bench/ci counters match the committed goldens, and the twelve pre-existing counter files are byte-identical, so no other benchmark shape moved.

https://claude.ai/code/session_01FwfS3b4MkgCj54u47ruzU4