Skip to content

Bound call-site inlining growth on non-collapsing monad chains #221

Description

@Unisay

Follow-up from #180. The budgeted call-site inliner is a clear win when the
inlined method meets a known constructor and folds away (Maybe/Either chains
collapse to straight-line code). It is a loss when there is nothing to fold
against: a product-type monad or transformer inlines its bind and the state
threading just unrolls, growing the code with no payoff.

Example

Golden.LongStateBind is State Int Int, i.e. StateT Int Identity. The bind
is roughly:

bindStateT m f = \s -> case m s of Tuple a s' -> (f a) s'

Tuple is a single-constructor product, so there is no tag to test and no branch
to eliminate. Inlining bindStateT at each of the 300 steps replaces a compact
bindStateT(m, f) call with the lambda body, and since nothing folds it, the
result is larger than the call. Over 300 steps that is net growth.

Contrast Maybe/Either: bind (Just x) f inlines to
case (Just x) of Nothing -> Nothing; Just a -> f a, the scrutinee is a known
constructor, the tag test folds, the case disappears, and you are left with
f x. Sum types collapse; products unroll.

After the effect-run marker fix in #180 the remaining growth is
LongStateBind +282, LongStackBind +277, TailRecM2Shadow +112 lines (down
from 8x before). These are 300-step or fully polymorphic stress tests, they stay
correct and load fine, but on principle the inliner should not grow code that
does not collapse.

Why a local check does not work

At the point inlineSaturatedCall decides to paste a worker it cannot tell
whether a fold will follow: the collapse is multi-stage and depends on the
call-site context (whether the scrutinee becomes a known constructor, which only
shows up after other inlines and folds run). A naive "only inline a worker whose
body has a ReflectCtor" gate breaks the good cases too, because the generic
bind first resolves to dict.bind and the concrete method with the tag test
only appears a step later, so the gate would block the cascade that eventually
collapses Maybe/Either.

Proposed directions

  • Speculative inlining with rollback (GHC's approach). Tentatively inline,
    run the local simplifier (folds + DCE), measure the result. Keep it if it is
    no larger than the call site, otherwise revert. Principled and uniform across
    product, polymorphic, and transformer cases. Cost: the optimizer is currently
    a single-pass bottom-up rewrite, so this needs a try-measure-commit loop per
    candidate.

  • A per-binding growth cap (cheaper, coarser). Retain the pre-specialize
    snapshot of each binding; if the specialize+dce fixpoint grew it past some
    factor with no offsetting collapse, revert that binding. Simpler than per-site
    speculation but a blunter instrument.

Metadata

Metadata

Assignees

No one assigned

    Labels

    OptimisationA Compiler Optimisationarea: irIR / optimizer / DCE / inliner

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions