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.
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/Eitherchainscollapse to straight-line code). It is a loss when there is nothing to fold
against: a product-type monad or transformer inlines its
bindand the statethreading just unrolls, growing the code with no payoff.
Example
Golden.LongStateBindisState Int Int, i.e.StateT Int Identity. The bindis roughly:
Tupleis a single-constructor product, so there is no tag to test and no branchto eliminate. Inlining
bindStateTat each of the 300 steps replaces a compactbindStateT(m, f)call with the lambda body, and since nothing folds it, theresult is larger than the call. Over 300 steps that is net growth.
Contrast
Maybe/Either:bind (Just x) finlines tocase (Just x) of Nothing -> Nothing; Just a -> f a, the scrutinee is a knownconstructor, 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 (downfrom 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
inlineSaturatedCalldecides to paste a worker it cannot tellwhether 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 genericbindfirst resolves todict.bindand the concrete method with the tag testonly 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-
specializesnapshot of each binding; if the
specialize+dcefixpoint grew it past somefactor with no offsetting collapse, revert that binding. Simpler than per-site
speculation but a blunter instrument.