[Git][ghc/ghc][wip/T27737] 17 commits: Improve exprOkForSpeculation
Simon Peyton Jones pushed to branch wip/T27737 at Glasgow Haskell Compiler / GHC Commits: 8c947573 by Simon Peyton Jones at 2026-10-16T13:11:53+01:00 Improve exprOkForSpeculation Fixes #27910, which exposed an infelicity in exprOkForSpeculation The new story is carefully described in new Note [exprOkForSpeculation], esp (a-c) and (EOKS1). - - - - - b1623ed2 by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Don't push `case` inside `let` in Gentle simplification Triggered by #27737 this MR arranges for the Simplifier NOT to do K[ let binds in e ] --> let binds in K[ e ] in when `sm_case_case` is on; that is, in the first "gentle" simplication. Needs better documentation, but see discussion on #27737. - - - - - cf59db84 by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Wibble - - - - - 9d8ef33f by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Wibbles and documentation - - - - - 2fe5734e by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Try another way let's see what CI says - - - - - 3aab8640 by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Fix join points Split contininuations *first* - - - - - 574b3e56 by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Deal with runRW# too ToDo: document this - - - - - 883a949d by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Wibbles - - - - - 025075dd by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Eliminate accidental pprTrace - - - - - 343fc71a by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Fix perf hole in exprIsConApp_maybe in subst_bndr. ToDo: document - - - - - e7972340 by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Fix in-scope set violation - - - - - e0aef7c6 by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Attempt to deal with the perf issue in T18223 [skip ci] see `rebuildWithFloats` - - - - - 44d0fa5d by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Work in progress on modifying the Simplifier's FloatBinds ...in collaboration with Claude - - - - - 76031f6e by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 More work in progress ...with Claude Very nice refactor. The hack does about what we hoped. Changes are relative to the original branch (casts always in inner), and only tests that moved by more than 0.5% are listed: ┌──────────────────┬───────────────────────┬───────────────────────────────────────────────────────────────────┐ │ Test │ Casts always in outer │ Hack (cast only into a single-alternative case or a non-join let) │ ├──────────────────┼───────────────────────┼───────────────────────────────────────────────────────────────────┤ │ CoOpt_Read │ +6.9% │ +5.6% (still a regression) │ ├──────────────────┼───────────────────────┼───────────────────────────────────────────────────────────────────┤ │ CoOpt_Singletons │ +6.1% │ 0.0% (fully recovered) │ ├──────────────────┼───────────────────────┼───────────────────────────────────────────────────────────────────┤ │ T13253 │ +3.7% │ +0.1% (recovered) │ ├──────────────────┼───────────────────────┼───────────────────────────────────────────────────────────────────┤ │ T13056 │ +1.1% │ +1.1% │ ├──────────────────┼───────────────────────┼───────────────────────────────────────────────────────────────────┤ │ T5642 │ −1.9% │ −1.9% (fix kept) │ ├──────────────────┼───────────────────────┼───────────────────────────────────────────────────────────────────┤ │ T16577 │ −1.5% │ −1.5% │ ├──────────────────┼───────────────────────┼───────────────────────────────────────────────────────────────────┤ │ T21839c │ −1.0% │ −1.0% │ ├──────────────────┼───────────────────────┼───────────────────────────────────────────────────────────────────┤ │ T19695 │ +0.8% │ −0.1% │ └──────────────────┴───────────────────────┴───────────────────────────────────────────────────────────────────┘ The other 56 tests are within 0.5%. Relative to master, CoOpt_Read is still about 3% better (it was 9% better with casts always pushed inside). CoOpt_Read is the only real loss left. It presumably gains from pushing a cast into a multi-alternative case, or into a join point, which the hack now forbids. The Core Lint bug. My reading is that it's caused by the hack, not latent: a cast pushed into a join point's RHS but not into a multi-alternative case in its body leaves a jump under a cast. The mightBeJoinBind test (no casts into a join-point let) fixes it, and the current tree builds cleanly with it. /tmp/tjoin/JoinCast.hs is a candidate reproducer of that shape: MkN (let j z = ... in case x of {0 -> j 1; 1 -> j 2; _ -> 3}). It passes Lint on master and on the current branch. I haven't yet seen it fail, because that needs the buggy state rebuilt, which means editing Iteration.hs. I'll do that only after your push, if you want it. State you're committing: - FloatBinds work, with addFloatBinds. - Your getFF and Note [LetFloats] changes, plus my comment fixes and the let-can-float and soft-scope assertions. - Soft-scoped ticks floated as FloatTicks. - The push_casts flag, with mightBeJoinBind. - Accepted outputs for T20510 and show-bytecode-hpc. - Tests: - The full testsuite was run before the push_casts change; the only unexpected failures were environmental ones and those two outputs, now accepted. - The push_casts version has only been built, and measured with the perf harness. simplCore and the full testsuite haven't been rerun on it. - - - - - d10a0fc8 by Simon Peyton Jones at 2026-10-16T17:11:24+01:00 Undo the push_casts experiment in splitContArgs Go back to always putting casts in the `inner` continuation when case-of-case is off. The push_casts flag (and mightBeJoinBind) fixed the coercion duplication in T5642, but cost CoOpt_Read, and needed a delicate side condition for join points. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> - - - - - dbf34eb1 by Simon Peyton Jones at 2026-10-16T17:11:44+01:00 Add a small regression test - - - - - e8ec242c by Simon Peyton Jones at 2026-10-16T17:11:44+01:00 Simplifier: tidy up case-floats, casts and float handling (#27737) Casts * splitContArgs: push a cast into `inner` only when it is followed by an application (isAppCont). A cast suffix stays outside, so it is not duplicated into every alternative of a multi-way case, and cast worker/wrapper can still fire. Fixes the quadratic coercion blow-up in T5642, T16577 (derived Generic `from`). Note [Do not push a cast inwards unnecessarily]; invariant on CastIt. Case-floats and single-alternative cases * Restructure reallyRebuildCase: do prepareCase first, then split into rebuildSingleAltCase (no mkDupableCont; returns a case-float) and rebuildMultiAltCase. simplAlt now returns (AltCon, [OutVar], floats, rhs). * rebuildSingleAltCase no longer calls mkCase (removing the buggy (FSC1) fast path). Instead new simplWrapFloats wraps floats using mkCase for each case-float, so case-merging, identity-case elimination etc still happen. It replaces Env.wrapFloats at all Simplifier call sites. Note [Wrapping case-floats with mkCase]. * Invariant (FFC1): a DEFAULT case-float never has a scrutinee for which doCaseToLet holds (it should be a let-float). doCaseToLet moves to Simplify.Env; asserted by okCaseFloat. rebuildSingleAltCase makes a let-float when prepareAlts has pruned a case to a single DEFAULT. Note [Case-floats], Note [Tick-floats]. * contIsDupable: treat a Select with "unpacking alternatives" (case x of K a b -> b, possibly nested) as dupable, so CPR unboxing cancels with the boxing instead of making a join point. Fixes the extra Simplifier iteration in T15304. Note [Duplicating unpacking continuations]. Float representation * Flatten LetFloats into SimplFloats: sfLetFloats :: FloatBinds; no per-group FloatFlag field. New `type LetFloats = OrdList OutBind` (let-bindings only, satisfying let-can-float). New addLetFloat, addCaseFloat, addLetFloats, mkLetSimplFloats; getFF_Case/getFF_Tick gone. Note [LetFloats]. * prepareBinding floats only lazy or ok-for-spec let-bindings (onlyLazyLetFloats, one pass); returns (LetFloats, InScopeSet, rhs). No more strict_bind argument. abstractFloats takes LetFloats, so a case-float can never reach it (was a panic: T27737a). Note [prepareBinding], including the lost addIntC# opportunity (PB4). * prepareRhs/makeTrivial return LetFloats; makeTrivial declines to bind an unlifted, not-ok-for-spec expression (bindingOk). Note [Cannot trivialise] (CT1). Performance details * mkSingleAltCase: skip occCheckExpand when no binder is a TyCoVar. * Force a Case's type only when emitting it: mkCase3 renamed returnCase, which does the seqType; callers don't. Update Note [Avoiding space leaks in OutType]. * Record the (rejected) idea of floating a prefix of the floats: Note [Floating a prefix of the floats]. Notes * Note [LetFloats]: why we have FloatCase (LF1, LF2). Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> - - - - - 15 changed files: - compiler/GHC/Core.hs - compiler/GHC/Core/Opt/Simplify/Env.hs - compiler/GHC/Core/Opt/Simplify/Iteration.hs - compiler/GHC/Core/Opt/Simplify/Utils.hs - compiler/GHC/Core/SimpleOpt.hs - compiler/GHC/Core/Type.hs - compiler/GHC/Core/Utils.hs - compiler/GHC/Driver/Config/Core/Opt/Simplify.hs - testsuite/tests/dmdanal/should_compile/T20510.stderr - testsuite/tests/show-bytecode/show-bytecode-hpc.stdout - testsuite/tests/simplCore/should_compile/T26903.stderr - + testsuite/tests/simplCore/should_compile/T27737a.hs - + testsuite/tests/simplCore/should_compile/T27910.hs - + testsuite/tests/simplCore/should_compile/T27910.stderr - testsuite/tests/simplCore/should_compile/all.T Changes: ===================================== compiler/GHC/Core.hs ===================================== @@ -490,7 +490,7 @@ This is a well-kinded type, in an environment-based scheme. But `typeKind` will panic, because the kind of the body of a forall must not mention the forall'd variable (and the inner forall's body appears to do so). -It might be possible to make `exprType` and `typeKind`` more complicated, so that +It might be possible to make `exprType` and `typeKind` more complicated, so that they do renaming on the fly. But instead we impose INVARIANT (NoTypeShadowing): @@ -1720,10 +1720,19 @@ isEmptyFloatBinds = isNilOL data FloatBind = FloatLet CoreBind + -- let(rec) x = e + -- Invariant: satisfies the let-can-float invariant + | FloatCase CoreExpr CoreBndr AltCon [CoreBndr] -- case e of y { C ys -> ... } -- See Note [Floating single-alternative cases] in GHC.Core.Opt.SetLevels + | FloatTick CoreTickish + -- tick<t> ... + -- Invariant: the tick is always soft-scoped (tickishHasSoftScope holds) + -- Why? We are floating these FloatBinds outwards, bringing more code under + -- the bindigns; that is only OK for soft-scoped ticks. + -- See Note [Scoping ticks and counting ticks] in GHC.Types.Tickish floatsBinders :: FloatBinds -> [Var] floatsBinders fs = foldr ((++) . floatBinders) [] fs ===================================== compiler/GHC/Core/Opt/Simplify/Env.hs ===================================== @@ -38,14 +38,13 @@ module GHC.Core.Opt.Simplify.Env ( -- * Floats SimplFloats(..), emptyFloats, isEmptyFloats, mkRecFloats, - mkFloatBind, addLetFloats, addJoinFloats, addFloats, - extendFloats, wrapFloats, - isEmptyJoinFloats, isEmptyLetFloats, - doFloatFromRhs, getTopFloatBinds, + mkFloatBind, addLetFloat, addLetFloats, addCaseFloat, mkLetSimplFloats, + addJoinFloats, addFloats, addFloatBindsF, + extendFloats, isEmptyJoinFloats, + doFloatFromRhs, getTopFloatBinds, onlyLazyLetFloats, doCaseToLet, -- * LetFloats - LetFloats, FloatEnable(..), letFloatBinds, emptyLetFloats, unitLetFloat, - addLetFlts, mapLetFloats, + LetFloats, FloatEnable(..), emptyLetFloats, mapLetFloats, -- * JoinFloats JoinFloat, JoinFloats, emptyJoinFloats, @@ -65,7 +64,7 @@ import GHC.Core.Subst( substExprSC ) import GHC.Core.Unfold import GHC.Core.TyCo.Subst (emptyIdSubstEnv, mkSubst) import GHC.Core.Multiplicity( Scaled(..), mkMultMul ) -import GHC.Core.Make ( mkWildValBinder, mkCoreLet ) +import GHC.Core.Make ( mkWildValBinder ) import GHC.Core.Type hiding ( substTy, substTyVar, substTyVarBndr, substCo , extendTvSubst, extendCvSubst ) import qualified GHC.Core.Coercion as Coercion @@ -78,6 +77,7 @@ import GHC.Types.Var.Set import GHC.Types.Id as Id import GHC.Types.InlinePragma ( ActivationGhc, CompilerPhase, isActiveInPhase ) import GHC.Types.Basic +import GHC.Types.Tickish ( tickishHasSoftScope ) import GHC.Types.Unique.FM ( pprUniqFM ) import GHC.Data.OrdList @@ -418,9 +418,10 @@ see GHC.Core.Opt.FloatOut. data SimplFloats = SimplFloats - { -- Ordinary let bindings - sfLetFloats :: LetFloats + { -- Ordinary let bindings, case-floats and tick-floats + sfLetFloats :: FloatBinds -- See Note [LetFloats] + -- Invariant: every FloatLet satisfies the let-can-float invariant -- Join points , sfJoinFloats :: JoinFloats @@ -438,19 +439,19 @@ data SimplFloats instance Outputable SimplFloats where ppr (SimplFloats { sfLetFloats = lf, sfJoinFloats = jf, sfInScope = is }) = text "SimplFloats" - <+> braces (vcat [ text "lets: " <+> ppr lf + <+> braces (vcat [ text "lets: " <+> ppr (fromOL lf) , text "joins:" <+> ppr jf , text "in_scope:" <+> ppr is ]) emptyFloats :: SimplEnvIS -> SimplFloats emptyFloats env - = SimplFloats { sfLetFloats = emptyLetFloats + = SimplFloats { sfLetFloats = nilOL , sfJoinFloats = emptyJoinFloats , sfInScope = seInScope env } isEmptyFloats :: SimplFloats -> Bool -- Precondition: used only when sfJoinFloats is empty -isEmptyFloats (SimplFloats { sfLetFloats = LetFloats fs _ +isEmptyFloats (SimplFloats { sfLetFloats = fs , sfJoinFloats = js }) = assertPpr (isNilOL js) (ppr js ) $ isNilOL fs @@ -744,26 +745,159 @@ setSubstEnv env tvs cvs ids = env { seTvSubst = tvs, seCvSubst = cvs, seIdSubst Note [LetFloats] ~~~~~~~~~~~~~~~~ -The LetFloats is a bunch of bindings, classified by a FloatFlag. - -The `FloatFlag` contains summary information about the bindings, see the data -type declaration of `FloatFlag` - +The `sfLetFloats` field of SimplFloats is a bunch of FloatBinds. A FloatBind +can take one of three forms: FloatLet, FloatCase, and FloatTick; see +Note [Case-floats] and Note [Tick-floats]. + +In contrast, the type `LetFloats` (= OrdList OutBind) has let-bindings only. +It is what prepareBinding, prepareRhs and makeTrivial return: they never +produce case-floats or tick-floats. See Note [prepareBinding] in +GHC.Core.Opt.Simplify.Iteration. + +When prepareBinding decides whether to float some let-bindings out of a RHS, +doFloatFromRhs classifies them with a FloatFlag; see the data type declaration +of `FloatFlag`, and Note [FloatFlag for FloatLet]. Case-floats and tick-floats +have no FloatFlag, because prepareBinding never floats them out of a RHS. + +Why do we have FloatCase at all, rather than just let-bindings? + +(LF1) exprIsConApp_maybe looks through single-alternative cases (and lets + and ticks) and returns what it looked through as a [FloatBind]. The + case-of-known-constructor code wants to add these straight to the + Simplifier's floats, so the floats must be able to hold a case. + +(LF2) A single-alternative case is returned as a FloatCase by + rebuildSingleAltCase rather than as an expression, so that the lets in + its alternative are not trapped inside it. Example, with case-of-case + switched off (e.g. in the Gentle phase): + case (case f x s of (# s1, a #) -> + let b = g a in + let c = h b in + (# s1, c #)) + of (# s2, r #) -> body + We simplify the inner case with an empty continuation (see + splitContForNoCaseCase), and get back + floats: [case f x s of (# s1, a #), b = g a, c = h b] + result: (# s1, c #) + Now rebuildWithFloats can do case-of-known-constructor on the result + directly, giving + case f x s of (# s1, a #) -> + let b = g a in + let c = h b in + body[s1/s2, c/r] + If instead the inner case came back as a single expression, then + exprIsConApp_maybe would have to walk down through the case and all the + lets to find the (# s1, c #). With a long chain of such nested binds + (e.g. state-passing code, as in T18223) the scrutinee at each level + contains all the lets from the levels inside it, so the repeated walks + are quadratic (#27737). + See Note [Floating single-alternative cases] in GHC.Core.Opt.Simplify.Iteration. + +Note [FloatFlag for FloatLet] -- see `getFF_Let` +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Examples - NonRec x (y:ys) FltLifted - Rec [(x,rhs)] FltLifted - - NonRec x* (p:q) FltOKSpec -- RHS is WHNF. Question: why not FltLifted? - NonRec x# (y +# 3) FltOkSpec -- Unboxed, but ok-for-spec'n - - NonRec x* (f y) FltCareful -- Strict binding; might fail or diverge - NonRec x# (a /# b) FltCareful -- Might fail; does not satisfy let-can-float invariant - NonRec x# (f y) FltCareful -- Might diverge; does not satisfy let-can-float invariant + NonRec x (y:ys) FltLifted + Rec [(x,rhs)] FltLifted + + NonRec x* (p:q) FltOKSpec -- RHS is WHNF. Question: why not FltLifted? + NonRec x# (y +# 3) FltOkSpec -- Unboxed, but ok-for-spec'n + + NonRec x* (f y) FltCareful -- Strict binding; might fail or diverge + NonRec x# (a /# b) FltCareful -- Might fail; does not satisfy let-can-float invariant + NonRec x# (f y) FltCareful -- Might diverge; does not satisfy let-can-float invariant + + NonRec s "foo"# FltLifted -- Literal string can go to top level + +* (FFL1) Note that a FloatLet can still be FltCareful: the first FltCareful example + above, NonRec x* (f y), where x* is lifted but has a strict demand + (isStrUsedDmd). That is a perfectly valid (lazy) let-binding, but its demand + info is valid only where it is. If we floated it out of the RHS of a lazy + binding + let v = let x* = f y in x*+1 in body + ==> let x* = f y; v = x*+1 in body + then x's demand info would be a lie, and CorePrep, which case-binds a let + whose binder has a strict demand, would evaluate (f y) eagerly. Hence + FltCareful. prepareBinding never floats a FltCareful binding out of a RHS, + even the RHS of a strict binding; see onlyLazyLetFloats. + +* (FFL2) A literal-string binding is marked FltLifted (a bit of a mis-nomer + because it's not a lifted type) because it can go to top level. + See Note [Core top-level string literals] in GHC.Core. + +* A binding that does not satisfy the let-can-float invariant (the last two + examples above) is represented by a FloatCase, not a FloatLet: + FloatCase (a /# b) x# DEFAULT [] + That is done once and for all by `addLetFloat`, so a FloatLet in sfLetFloats + is always a valid let-binding, and `simplWrapFloats` does not need to check. + Such bindings used to arise from `makeTrivial`, because an argument need not + satisfy the let-can-float invariant; but now makeTrivial declines to bind such + an argument (see Note [Cannot trivialise] in GHC.Core.Opt.Simplify.Iteration). + They can also arise because + exprOkForSpeculation is conservative: e.g. it says False for (# s, x #) + where x is lifted, because it checks the arguments against the + (representation-polymorphic) type of the unboxed-tuple worker. + +Note [Case-floats] +~~~~~~~~~~~~~~~~~~ +As well as let-bindings, sfLetFloats can contain single-alternative case +floats (FloatCase), for example + case e of b { (# a, c #) -> <hole> } +A case-float never floats out of the RHS of a let-binding: prepareBinding +floats only let-bindings. See Note [prepareBinding] in +GHC.Core.Opt.Simplify.Iteration, which also describes an opportunity that +we lose as a result. + +(FFC1) Invariant: a DEFAULT FloatCase never has a scrutinee for which doCaseToLet + holds. Such a case-float + FloatCase e b DEFAULT [] -- where doCaseToLet e b + should instead be the let-float (b = e), which satisfies the let-can-float + invariant. It would not actually be /wrong/ to use the FloatCase, just less + good: a let-float can be inlined, and can float out of the RHS of a let-binding + (see Note [prepareBinding]). + + doCaseToLet is the same test that rebuildCase uses to turn a case into a let: + roughly, the scrutinee is ok-for-speculation (if unlifted) or a HNF (if lifted). + But it says No if `b` is a coercion variable, because a coercion variable can + be let-bound only to a Coercion (Note [Core type and coercion invariant] in + GHC.Core); so FloatCase (eq_sel @k @t1 @t2 d) co DEFAULT [] is fine. + + We maintain the invariant thus: + * addLetFloat makes a FloatCase only for a binding that needsCaseBinding, + i.e. an unlifted one whose RHS is not ok-for-speculation. + * rebuildCase turns case e of b { DEFAULT -> body } into a let when + doCaseToLet holds. + * But rebuildCase looks at the alternatives before prepareAlts prunes away + impossible ones; e.g. case x# of b { 1# -> e1; DEFAULT -> e2 } may be + pruned to a single DEFAULT alternative. So rebuildSingleAltCase makes a + let-float, rather than a case-float, for a DEFAULT alternative when + doCaseToLet holds. + * exprIsConApp_maybe makes DEFAULT case-floats (in GHC.Core.SimpleOpt) only + for an unlifted argument that needsCaseBinding, or for a strict field + whose argument is not a HNF (mkFieldSeqFloats). + We check the invariant, with `okCaseFloat`, in addCaseFloat and addFloatBindsF. + + This invariant is only about DEFAULT case-floats. A case-float with pattern + binders, such as case addIntC# x y of (# r, c #) -> <hole>, cannot be a + let-float even when its scrutinee is ok-for-speculation. + +Note [Tick-floats] +~~~~~~~~~~~~~~~~~~ +sfLetFloats can contain a FloatTick for soft-scoped ticks (only -- see the +invariant on FloatTick in GHC.Core); see simplTick. + +Like a case-float, a tick-float never floats out of the RHS of a let-binding, +because prepareBinding floats only let-bindings. For a /counting/ tick (e.g. +an HPC tick) that is essential: floating it out of a lazy RHS would change when +(and how often) it is counted, namely when the let is executed rather than when +the binder is evaluated. For a /non-counting/ tick (e.g. a source note) it +would be fine, but we don't bother. -} -data LetFloats = LetFloats (OrdList OutBind) FloatFlag - -- See Note [LetFloats] +type LetFloats = OrdList OutBind + -- Let-bindings only: no case-floats or tick-floats + -- Invariant: every binding satisfies the let-can-float invariant + -- See Note [LetFloats] type JoinFloat = OutBind type JoinFloats = OrdList JoinFloat @@ -780,17 +914,14 @@ data FloatFlag -- *and* ok-for-speculation -- Hence ok to float out of the RHS -- of a lazy non-recursive let binding - -- (but not to top level, or into a rec group) + -- (but /not/ to top level, or into a rec group) -- NB: consequence: all bindings satisfy let-can-float invariant | FltCareful -- At least one binding is strict (or unlifted) -- and not guaranteed cheap - -- Do not float these bindings out of a lazy let! + -- Never float these bindings out of a RHS -- NB: some bindings may not satisfy let-can-float -instance Outputable LetFloats where - ppr (LetFloats binds ff) = ppr ff $$ ppr (fromOL binds) - instance Outputable FloatFlag where ppr FltLifted = text "FltLifted" ppr FltOkSpec = text "FltOkSpec" @@ -803,9 +934,13 @@ andFF FltOkSpec _ = FltOkSpec andFF FltLifted flt = flt -doFloatFromRhs :: FloatEnable -> TopLevelFlag -> RecFlag -> Bool -> SimplFloats -> OutExpr -> Bool +doFloatFromRhs :: FloatEnable -> TopLevelFlag -> RecFlag + -> LetFloats -> FloatFlag -- The let-bindings and their FloatFlag, + -- from onlyLazyLetFloats + -> OutExpr -> Bool -- If you change this function look also at FloatIn.noFloatIntoRhs -doFloatFromRhs fe lvl rec strict_bind (SimplFloats { sfLetFloats = LetFloats fs ff }) rhs +-- See Note [Floating a prefix of the floats] for a possible improvement +doFloatFromRhs fe lvl rec fs ff rhs = floatEnabled lvl fe && not (isNilOL fs) && want_to_float @@ -817,7 +952,7 @@ doFloatFromRhs fe lvl rec strict_bind (SimplFloats { sfLetFloats = LetFloats fs can_float = case ff of FltLifted -> True FltOkSpec -> isNotTopLevel lvl && isNonRec rec - FltCareful -> isNotTopLevel lvl && isNonRec rec && strict_bind + FltCareful -> False -- onlyLazyLetFloats never returns FltCareful -- Whether any floating is allowed by flags. floatEnabled :: TopLevelFlag -> FloatEnable -> Bool @@ -825,6 +960,38 @@ doFloatFromRhs fe lvl rec strict_bind (SimplFloats { sfLetFloats = LetFloats fs floatEnabled lvl FloatNestedOnly = not (isTopLevel lvl) floatEnabled _ FloatEnabled = True +{- Note [Floating a prefix of the floats] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +prepareBinding floats all of the floats from a RHS, or none of them. It floats +none if any of them is a case-float or tick-float (see Note [prepareBinding] in +GHC.Core.Opt.Simplify.Iteration), or if doFloatFromRhs says no; and doFloatFromRhs +gives a single FloatFlag to the whole group. Consider (T5321FD) + x = let v1 = \ds -> ... in + ... + let v200 = \ds -> ... in + case sampleData of (a :* b) -> ... +where the single-alternative case has become a FloatCase; see +Note [Floating single-alternative cases] in GHC.Core.Opt.Simplify.Iteration. +Because of the FloatCase, none of these floats go to top level, even though the +lets in front of the case are all FltLifted. + +Opportunity: when the group cannot float as a whole, float the longest prefix +of let-bindings that can, and wrap the rest back around the RHS. Taking a +prefix is always fine, because later floats may mention the binders of earlier +ones, but not vice versa. To keep the common path cheap, do the linear +traversal only when the group cannot float as a whole. + +We tried this (#27737). It did restore the top-level floating in T5321FD, but +made little difference to compile time, so we did not keep it. If you try it +again, beware: the sfInScope of the floats describes the scope /inside/ all of +them, which is wrong for the prefix alone. In T5321FD, inside the trapped + case sampleData of (x :* xs) -> ... +binder-swap gives sampleData the unfolding (x :* xs); keeping that sfInScope +let the refined sampleData escape to top level, taking x and xs with it. The +fix is to rebuild sfInScope from the in-scope set outside the RHS, extended +with the binders of the prefix. +-} + {- Note [Float when expandable] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We float when that would leave us with a RHS that is /expandable/ (#26854). @@ -851,10 +1018,7 @@ End of historial aside -} emptyLetFloats :: LetFloats -emptyLetFloats = LetFloats nilOL FltLifted - -isEmptyLetFloats :: LetFloats -> Bool -isEmptyLetFloats (LetFloats fs _) = isNilOL fs +emptyLetFloats = nilOL emptyJoinFloats :: JoinFloats emptyJoinFloats = nilOL @@ -862,19 +1026,83 @@ emptyJoinFloats = nilOL isEmptyJoinFloats :: JoinFloats -> Bool isEmptyJoinFloats = isNilOL -unitLetFloat :: OutBind -> LetFloats --- This key function constructs a singleton float with the right form -unitLetFloat bind = assert (all (not . isJoinId) (bindersOf bind)) $ - LetFloats (unitOL bind) (flag bind) +getFF_Let :: CoreBind -> FloatFlag +-- See Note [FloatFlag for FloatLet] +getFF_Let (Rec {}) = FltLifted +getFF_Let (NonRec bndr rhs) + | not (isStrictId bndr) = FltLifted -- Lazy lifted let + | exprIsTickedString rhs = FltLifted -- See (FFL2) + | exprOkForSpeculation rhs = FltOkSpec -- Unlifted, or strict lifted, and ok-for-spec (e.g. HNF) + | otherwise = FltCareful -- See (FFL1) Strict, e.g. let x* = factorial y + +addLetFloat :: SimplFloats -> OutBind -> SimplFloats +-- Add a non-join binding to the let-floats, and extend the in-scope set. +-- If the binding does not satisfy the let-can-float invariant, it +-- makes a FloatCase. See Note [LetFloats] +addLetFloat floats bind + | NonRec bndr rhs <- bind + , needsCaseBinding (idType bndr) rhs + = -- This should never happen, but currently does because of #27910 + add_float floats (FloatCase rhs bndr DEFAULT []) + + | otherwise + = assert (all (not . isJoinId) (bindersOf bind)) $ + add_float floats (FloatLet bind) + +addCaseFloat :: SimplFloats -> OutExpr -> OutId -> AltCon -> [OutVar] -> SimplFloats +-- Add a single-alternative case float +-- case scrut of bndr { con bndrs -> <hole> } +-- and extend the in-scope set. See Note [LetFloats] +addCaseFloat floats scrut bndr con bndrs + = assertPpr (okCaseFloat flt) (ppr flt) $ + add_float floats flt where - flag (Rec {}) = FltLifted - flag (NonRec bndr rhs) - | not (isStrictId bndr) = FltLifted - | exprIsTickedString rhs = FltLifted - -- String literals can be floated freely. - -- See Note [Core top-level string literals] in GHC.Core. - | exprOkForSpeculation rhs = FltOkSpec -- Unlifted, and lifted but ok-for-spec (eg HNF) - | otherwise = FltCareful + flt = FloatCase scrut bndr con bndrs + +add_float :: SimplFloats -> FloatBind -> SimplFloats +-- Add the float /inside/ the existing let-floats +add_float floats@(SimplFloats { sfLetFloats = fs, sfInScope = in_scope }) flt + = floats { sfLetFloats = fs `snocOL` flt + , sfInScope = in_scope `extendInScopeFromFB` unitOL flt } + +okLetFloat :: OutBind -> Bool +-- Checks the let-can-float invariant; used only in assertions +okLetFloat (NonRec b r) + | isId b, not (isCoVar b) = not (needsCaseBinding (idType b) r) +okLetFloat _ = True + +okCaseFloat :: FloatBind -> Bool +-- Checks invariant (FFC1) in Note [Case-floats] +-- Used only in assertions +okCaseFloat (FloatCase scrut b DEFAULT _) = not (doCaseToLet scrut b) +okCaseFloat _ = True + +doCaseToLet :: OutExpr -- Scrutinee + -> Id -- Case binder; can be InId or OutId + -> Bool +-- The situation is case scrut of b { DEFAULT -> body } +-- Can we transform thus? let { b = scrut } in body +-- See also (FFC1) in Note [Case-floats] +doCaseToLet scrut case_bndr + | isTyCoVar case_bndr -- Respect GHC.Core + = isTyCoArg scrut -- Note [Core type and coercion invariant] + + | isUnliftedType (exprType scrut) + -- We can call isUnliftedType here: scrutinees always have a fixed RuntimeRep (see FRRCase). + -- Note however that we must check 'scrut' (which is an 'OutExpr') and not 'case_bndr' + -- (which may be an 'InId'): see Note [Dark corner with representation polymorphism] + -- in GHC.Core.Opt.Simplify.Iteration. + -- Using `exprType` is typically cheap because `scrut` is typically a variable. + -- We could instead use mightBeUnliftedType (idType case_bndr), but that hurts + -- the brain more. Consider that if this test ever turns out to be a perf + -- problem (which seems unlikely). + = exprOkForSpeculation scrut + + | otherwise -- Scrut has a lifted type + = exprIsHNF scrut + -- || isStrUsedDmd (idDemandInfo case_bndr) + -- We no longer look at the demand on the case binder + -- See Note [Case-to-let for strictly-used binders] in GHC.Core.Opt.Simplify.Iteration unitJoinFloat :: OutBind -> JoinFloats unitJoinFloat bind = assert (all isJoinId (bindersOf bind)) $ @@ -886,50 +1114,65 @@ mkFloatBind :: SimplEnv -> OutBind -> (SimplFloats, SimplEnv) -- These binders may already be in the in-scope set, -- but may have by now been augmented with more IdInfo mkFloatBind env bind - = (floats, env { seInScope = in_scope' }) + = (floats, env { seInScope = sfInScope floats }) where - floats - | isJoinBind bind - = SimplFloats { sfLetFloats = emptyLetFloats - , sfJoinFloats = unitJoinFloat bind - , sfInScope = in_scope' } - | otherwise - = SimplFloats { sfLetFloats = unitLetFloat bind - , sfJoinFloats = emptyJoinFloats - , sfInScope = in_scope' } -- See Note [Bangs in the Simplifier] - !in_scope' = seInScope env `extendInScopeSetBind` bind + !floats = emptyFloats env `extendFloats` bind extendFloats :: SimplFloats -> OutBind -> SimplFloats --- Add this binding to the floats, and extend the in-scope env too -extendFloats (SimplFloats { sfLetFloats = floats - , sfJoinFloats = jfloats - , sfInScope = in_scope }) - bind +-- Add this binding (join point or not) to the floats, +-- and extend the in-scope env too +extendFloats floats@(SimplFloats { sfJoinFloats = jfloats, sfInScope = in_scope }) bind | isJoinBind bind - = SimplFloats { sfInScope = in_scope' - , sfLetFloats = floats - , sfJoinFloats = jfloats' } + = floats { sfJoinFloats = jfloats `addJoinFlts` unitJoinFloat bind + , sfInScope = in_scope `extendInScopeSetBind` bind } | otherwise - = SimplFloats { sfInScope = in_scope' - , sfLetFloats = floats' - , sfJoinFloats = jfloats } - where - in_scope' = in_scope `extendInScopeSetBind` bind - floats' = floats `addLetFlts` unitLetFloat bind - jfloats' = jfloats `addJoinFlts` unitJoinFloat bind + = floats `addLetFloat` bind -addLetFloats :: SimplFloats -> LetFloats -> SimplFloats --- Add the let-floats for env2 to env1; --- *plus* the in-scope set for env2, which is bigger --- than that for env1 -addLetFloats floats let_floats - = floats { sfLetFloats = sfLetFloats floats `addLetFlts` let_floats - , sfInScope = sfInScope floats `extendInScopeFromLF` let_floats } +mkLetSimplFloats :: InScopeSet -> LetFloats -> SimplFloats +-- Make SimplFloats from some let-bindings. +-- Precondition: the InScopeSet already includes the binders of the let-bindings +mkLetSimplFloats in_scope binds + = SimplFloats { sfLetFloats = fmap FloatLet binds + , sfJoinFloats = emptyJoinFloats + , sfInScope = in_scope } -extendInScopeFromLF :: InScopeSet -> LetFloats -> InScopeSet -extendInScopeFromLF in_scope (LetFloats binds _) - = foldlOL extendInScopeSetBind in_scope binds +addLetFloats :: SimplFloats -> LetFloats -> SimplFloats +-- Add the let-bindings /inside/ the existing floats, +-- and extend the in-scope set +-- No need for addLetFloat's needsCaseBinding test: LetFloats satisfy the +-- let-can-float invariant (see the declaration of LetFloats) +addLetFloats floats binds = foldlOL add floats binds + where + add fs bind = assertPpr (okLetFloat bind) (ppr bind) $ + add_float fs (FloatLet bind) + +addFloatBindsF :: FloatBinds -> SimplFloats -> SimplFloats +-- (addFloatBindsF new_fbs floats) adds `new_fbs` /outside/ `floats`; +-- i.e. `new_fbs` scope over `floats` +-- Precondition: every FloatLet in `new_fbs` satisfies the let-can-float +-- invariant (see the FloatBind declaration in GHC.Core), so we can add +-- them directly; see Note [LetFloats] +addFloatBindsF new_fbs floats@(SimplFloats { sfLetFloats = lf_fbs, sfInScope = in_scope }) + | isNilOL new_fbs + = floats + | otherwise + = assertPpr (all ok_float new_fbs) (ppr new_fbs) $ + floats { sfLetFloats = new_fbs `appOL` lf_fbs + , sfInScope = in_scope `extendInScopeFromFB` new_fbs } + where + -- Check the invariants on FloatBind; see its declaration in GHC.Core + ok_float (FloatLet bind) = okLetFloat bind + ok_float (FloatTick t) = tickishHasSoftScope t + ok_float flt@(FloatCase {}) = okCaseFloat flt + +extendInScopeFromFB :: InScopeSet -> FloatBinds -> InScopeSet +extendInScopeFromFB in_scope binds + = foldlOL extend in_scope binds + where + extend in_scope (FloatLet bind) = in_scope `extendInScopeSetBind` bind + extend in_scope (FloatCase _ b _ bs) = in_scope `extendInScopeSetList` (b:bs) + extend in_scope (FloatTick {}) = in_scope addJoinFloats :: SimplFloats -> JoinFloats -> SimplFloats addJoinFloats floats join_floats @@ -943,16 +1186,46 @@ addFloats :: SimplFloats -> SimplFloats -> SimplFloats -- than that for env1 addFloats (SimplFloats { sfLetFloats = lf1, sfJoinFloats = jf1 }) (SimplFloats { sfLetFloats = lf2, sfJoinFloats = jf2, sfInScope = in_scope }) - = SimplFloats { sfLetFloats = lf1 `addLetFlts` lf2 + = SimplFloats { sfLetFloats = lf1 `appOL` lf2 , sfJoinFloats = jf1 `addJoinFlts` jf2 , sfInScope = in_scope } -addLetFlts :: LetFloats -> LetFloats -> LetFloats -addLetFlts (LetFloats bs1 l1) (LetFloats bs2 l2) - = LetFloats (bs1 `appOL` bs2) (l1 `andFF` l2) +onlyLazyLetFloats :: SimplFloats -> LetFloats -> Maybe (LetFloats, FloatFlag) +-- (onlyLazyLetFloats floats extra_binds) returns (Just (binds, ff)) if all the +-- let-floats in `floats`, followed by `extra_binds`, are let-bindings that we are +-- prepared to float out of a RHS: no case-floats or tick-floats, and no +-- FltCareful bindings. The FloatFlag `ff` combines the flags of the `binds`, +-- so it is FltLifted or FltOkSpec. +-- Precondition: there are no join floats +-- See Note [prepareBinding] in GHC.Core.Opt.Simplify.Iteration +onlyLazyLetFloats (SimplFloats { sfLetFloats = fs, sfJoinFloats = jfs }) extra_binds + = assertPpr (isNilOL jfs) (ppr jfs) $ + go FltLifted nilOL (fromOL fs) + where + go ff binds [] = foldlOL add_extra (Just (binds, ff)) extra_binds + go ff binds (FloatLet bind : rest) + | FltCareful <- bind_ff = Nothing + | otherwise = go (ff `andFF` bind_ff) (binds `snocOL` bind) rest + where + bind_ff = getFF_Let bind -- See Note [FloatFlag for FloatLet] + go _ _ _ = Nothing -- Case-float or tick-float -letFloatBinds :: LetFloats -> [CoreBind] -letFloatBinds (LetFloats bs _) = fromOL bs + add_extra Nothing _ = Nothing + add_extra (Just (binds, ff)) bind + | FltCareful <- bind_ff = Nothing + | otherwise = Just (binds `snocOL` bind, ff `andFF` bind_ff) + where + bind_ff = getFF_Let bind + +letFloatBinds :: SimplFloats -> [OutBind] +-- The let-floats, as bindings +-- Precondition: there are no case-floats or tick-floats; true, for example, +-- for floats that have come out of a recursive or top-level RHS +-- (see Note [prepareBinding] in GHC.Core.Opt.Simplify.Iteration) +letFloatBinds (SimplFloats { sfLetFloats = fs }) = map get_bind (fromOL fs) + where + get_bind (FloatLet bind) = bind + get_bind flt = pprPanic "letFloatBinds" (ppr flt) addJoinFlts :: JoinFloats -> JoinFloats -> JoinFloats addJoinFlts = appOL @@ -960,7 +1233,7 @@ addJoinFlts = appOL mkRecFloats :: SimplFloats -> SimplFloats -- Flattens the floats into a single Rec group, -- They must either all be lifted LetFloats or all JoinFloats -mkRecFloats floats@(SimplFloats { sfLetFloats = LetFloats bs _ff +mkRecFloats floats@(SimplFloats { sfLetFloats = bs , sfJoinFloats = jbs , sfInScope = in_scope }) = assertPpr (isNilOL bs || isNilOL jbs) (ppr floats) $ @@ -969,22 +1242,11 @@ mkRecFloats floats@(SimplFloats { sfLetFloats = LetFloats bs _ff , sfInScope = in_scope } where -- See Note [Bangs in the Simplifier] - !floats' | isNilOL bs = emptyLetFloats - | otherwise = unitLetFloat (Rec (flattenBinds (fromOL bs))) + !floats' | isNilOL bs = nilOL + | otherwise = unitOL (FloatLet (Rec (flattenBinds (letFloatBinds floats)))) !jfloats' | isNilOL jbs = emptyJoinFloats | otherwise = unitJoinFloat (Rec (flattenBinds (fromOL jbs))) -wrapFloats :: SimplFloats -> OutExpr -> OutExpr --- Wrap the floats around the expression -wrapFloats (SimplFloats { sfLetFloats = LetFloats bs flag - , sfJoinFloats = jbs }) body - = foldrOL mk_let (wrapJoinFloats jbs body) bs - -- Note: Always safe to put the joins on the inside - -- since the values can't refer to them - where - mk_let | FltCareful <- flag = mkCoreLet -- need to enforce let-can-float-invariant - | otherwise = Let -- let-can-float invariant hold - wrapJoinFloatsX :: SimplFloats -> OutExpr -> (SimplFloats, OutExpr) -- Wrap the sfJoinFloats of the env around the expression, -- and take them out of the SimplEnv @@ -999,19 +1261,18 @@ wrapJoinFloats join_floats body = foldrOL Let body join_floats getTopFloatBinds :: SimplFloats -> [CoreBind] -getTopFloatBinds (SimplFloats { sfLetFloats = lbs - , sfJoinFloats = jbs}) +getTopFloatBinds floats@(SimplFloats { sfJoinFloats = jbs }) = assert (isNilOL jbs) $ -- Can't be any top-level join bindings - letFloatBinds lbs + letFloatBinds floats {-# INLINE mapLetFloats #-} mapLetFloats :: LetFloats -> ((Id,CoreExpr) -> (Id,CoreExpr)) -> LetFloats -mapLetFloats (LetFloats fs ff) fun - = LetFloats fs1 ff +mapLetFloats binds fun + = binds1 where app (NonRec b e) = case fun (b,e) of (b',e') -> NonRec b' e' app (Rec bs) = Rec (strictMap fun bs) - !fs1 = (mapOL' app fs) -- See Note [Bangs in the Simplifier] + !binds1 = mapOL' app binds -- See Note [Bangs in the Simplifier] {- ************************************************************************ ===================================== compiler/GHC/Core/Opt/Simplify/Iteration.hs ===================================== @@ -22,8 +22,7 @@ import GHC.Core.Opt.Simplify.Env import GHC.Core.Opt.Simplify.Inline import GHC.Core.Opt.Simplify.Utils import GHC.Core.Opt.OccurAnal ( occurAnalyseExpr, zapLambdaBndrs ) -import GHC.Core.Make hiding( wrapFloats ) -import qualified GHC.Core.Make +import GHC.Core.Make import GHC.Core.Coercion hiding ( substCo, substCoVar ) import qualified GHC.Core.Coercion as Coercion import GHC.Core.Reduction @@ -40,7 +39,7 @@ import GHC.Core.Utils import GHC.Core.Opt.Arity ( ArityType, exprArity, arityTypeBotSigs_maybe , pushCoTyArg, pushCoValArg, exprIsDeadEnd , typeArity, arityTypeArity, etaExpandAT ) -import GHC.Core.SimpleOpt ( exprIsConApp_maybe, joinPointBinding_maybe, joinPointBindings_maybe ) +import GHC.Core.SimpleOpt ( exprIsConApp_maybe, joinPointBind_maybe ) import GHC.Core.FVs ( mkRuleInfo {- exprsFreeIds -} ) import GHC.Core.Rules ( lookupRule, getRules ) import GHC.Core.Multiplicity @@ -57,7 +56,6 @@ import GHC.Types.Demand import GHC.Types.Unique ( hasKey ) import GHC.Types.Basic import GHC.Types.Tickish -import GHC.Types.Var ( isTyCoVar ) import GHC.Builtin.WiredIn.Prim( realWorldStatePrimTy ) import GHC.Builtin.KnownKeys( runRWKey, seqHashKey ) @@ -66,6 +64,8 @@ import GHC.Builtin.WiredIn.Ids( seqId ) import qualified GHC.Data.List.Infinite as Inf import GHC.Data.Maybe ( isNothing, orElse, mapMaybe ) import GHC.Data.FastString +import GHC.Data.OrdList ( unitOL, isNilOL, appOL, snocOL, foldlOL ) +import GHC.Types.Var.Env ( InScopeSet ) import GHC.Unit.Module ( moduleName ) import GHC.Utils.Outputable import GHC.Utils.Panic @@ -255,6 +255,8 @@ simplRecBind env0 bind_cxt pairs0 ; let new_bndrs = map sndOf3 triples ; (rec_floats, env2) <- enterRecGroupRHSs env1 new_bndrs $ \env -> go env triples + + -- In rec_floats, all the `sfLetFloats` bindings are `FltLifted` ; return (mkRecFloats rec_floats, env2) } where add_rules :: SimplEnv -> (InBndr,InExpr) -> SimplM (SimplEnv, (InBndr, OutBndr, InExpr)) @@ -283,7 +285,8 @@ simplRecOrTopPair :: SimplEnv -> BindContext -> InId -> OutBndr -> InExpr -- Binder and rhs -> SimplM (SimplFloats, SimplEnv) - +-- Invariant: in the returned SimplFloats, +-- all the `sfLetFloats` bindings are `FltLifted` simplRecOrTopPair env bind_cxt old_bndr new_bndr rhs | Just env' <- preInlineUnconditionally env (bindContextLevel bind_cxt) old_bndr (UnSimplified env) rhs MRefl @@ -348,25 +351,27 @@ simplLazyBind top_lvl is_rec (bndr,unf_se) (bndr1,env) (rhs,rhs_se) ; (body_floats0, body0) <- {-#SCC "simplExprF" #-} simplExprF body_env body rhs_cont -- ANF-ise a constructor or PAP rhs - ; (body_floats2, body2) <- {-#SCC "prepareBinding" #-} - prepareBinding env top_lvl is_rec - False -- Not strict; this is simplLazyBind - bndr1 body_floats0 body0 + ; (body_lets, lets_in_scope, body2) + <- {-#SCC "prepareBinding" #-} + prepareBinding env top_lvl is_rec + bndr1 (contResultType rhs_cont) + body_floats0 body0 -- Subtle point: we do not need or want tvs' in the InScope set -- of body_floats2, so we pass in 'env' not 'body_env'. -- Don't want: if tvs' are in-scope in the scope of this let-binding, we may do -- more renaming than necessary => extra work (see !7777 and test T16577). -- Don't need: we wrap tvs' around the RHS anyway. + ; let body_floats2 = mkLetSimplFloats lets_in_scope body_lets ; (rhs_floats, body3) - <- if isEmptyFloats body_floats2 || null tvs then -- Simple floating + <- if isNilOL body_lets || null tvs then -- Simple floating {-#SCC "simplLazyBind-simple-floating" #-} return (body_floats2, body2) else -- Non-empty floats, and non-empty tyvars: do type-abstraction first {-#SCC "simplLazyBind-type-abstraction-first" #-} - do { (poly_binds, body3) <- abstractFloats (seUnfoldingOpts env) top_lvl - tvs' body_floats2 body2 + do { (poly_binds, body3) <- abstractFloats (seUnfoldingOpts env) top_lvl tvs' + lets_in_scope body_lets body2 ; let poly_floats = foldl' extendFloats (emptyFloats env) poly_binds ; return (poly_floats, body3) } @@ -426,7 +431,7 @@ simplAuxBind (saf,env) bndr new_rhs = do { -- ANF-ise the RHS let !occ_fs = getOccFS bndr ; (anf_floats, rhs1) <- prepareRhs env NotTopLevel occ_fs new_rhs - ; unless (isEmptyLetFloats anf_floats) (tick LetFloatFromLet) + ; unless (isNilOL anf_floats) (tick LetFloatFromLet) ; let rhs_floats = emptyFloats env `addLetFloats` anf_floats -- Simplify the binder and complete the binding @@ -628,15 +633,14 @@ tryCastWorkerWrapper env bind_cxt old_bndr bndr (Cast rhs co) = do { uniq <- getUniqueM ; let work_name = mkSystemVarName uniq occ_fs work_id = mkLocalIdWithInfo work_name ManyTy work_ty work_info - is_strict = isStrictId bndr - ; (rhs_floats, work_rhs) <- prepareBinding env top_lvl is_rec is_strict - work_id (emptyFloats env) rhs + ; (rhs_lets, lets_in_scope, work_rhs) + <- prepareBinding env top_lvl is_rec work_id work_ty (emptyFloats env) rhs ; work_unf <- mk_worker_unfolding top_lvl work_id work_rhs ; let work_id_w_unf = work_id `setIdUnfolding` work_unf - floats = rhs_floats `addLetFloats` - unitLetFloat (NonRec work_id_w_unf work_rhs) + floats = mkLetSimplFloats lets_in_scope rhs_lets `addLetFloat` + NonRec work_id_w_unf work_rhs triv_rhs = Cast (Var work_id_w_unf) co @@ -714,10 +718,12 @@ mkCastWrapperInlinePrag prag = prag * * ********************************************************************* -} -prepareBinding :: SimplEnv -> TopLevelFlag -> RecFlag -> Bool - -> Id -- Used only for its OccName; can be InId or OutId +prepareBinding :: SimplEnv -> TopLevelFlag -> RecFlag + -> Id -- Used only for its OccName; can be InId or OutId + -> OutType -- The type of the RHS -> SimplFloats -> OutExpr - -> SimplM (SimplFloats, OutExpr) + -> SimplM (LetFloats, InScopeSet, OutExpr) + -- The InScopeSet includes the binders of the LetFloats -- In (prepareBinding ... bndr floats rhs), the binding is really just -- bndr = let floats in rhs -- Maybe we can ANF-ise this binding and float out; e.g. @@ -728,8 +734,8 @@ prepareBinding :: SimplEnv -> TopLevelFlag -> RecFlag -> Bool -- bndr = K a a tmp -- That's what prepareBinding does -- Precondition: binder is not a JoinId --- Postcondition: the returned SimplFloats contains only let-floats -prepareBinding env top_lvl is_rec strict_bind bndr rhs_floats rhs +-- Postcondition: returns only let-bindings; see Note [prepareBinding] +prepareBinding env top_lvl is_rec bndr rhs_ty rhs_floats rhs = do { -- Never float join-floats out of a non-join let-binding (which this is) -- So wrap the body in the join-floats right now -- Hence: rhs_floats1 consists only of let-floats @@ -745,16 +751,73 @@ prepareBinding env top_lvl is_rec strict_bind bndr rhs_floats rhs ; (anf_floats, rhs2) <- prepareRhs rhs_env top_lvl occ_fs rhs1 -- Finally, decide whether or not to float - ; let all_floats = rhs_floats1 `addLetFloats` anf_floats - ; if doFloatFromRhs (seFloatEnable env) top_lvl is_rec strict_bind all_floats rhs2 - then -- Float! - do { tick LetFloatFromLet - ; return (all_floats, rhs2) } - - else -- Abandon floating altogether; revert to original rhs - -- Since we have already built rhs1, we just need to add - -- rhs_floats1 to it - return (emptyFloats env, wrapFloats rhs_floats1 rhs1) } + -- The anf_floats are already let-bindings, so we need not add them + -- to rhs_floats1 (and its in-scope set) just to check them + ; case onlyLazyLetFloats rhs_floats1 anf_floats of + Just (all_lets, ff) -- Float only lazy or ok-for-spec let-bindings + -- See Note [prepareBinding] + | doFloatFromRhs (seFloatEnable env) top_lvl is_rec all_lets ff rhs2 + -> do { tick LetFloatFromLet + ; let !in_scope = foldlOL extendInScopeSetBind + (sfInScope rhs_floats1) anf_floats + -- rhs_floats1 already has the binders of its own floats + ; return (all_lets, in_scope, rhs2) } + + _ -> -- Abandon floating altogether; revert to original rhs + -- Since we have already built rhs1, we just need to add + -- rhs_floats1 to it + do { rhs' <- simplWrapFloats (seMode env) rhs_floats1 rhs1 rhs_ty + ; return (emptyLetFloats, seInScope env, rhs') } } + +{- Note [prepareBinding] +~~~~~~~~~~~~~~~~~~~~~~~~~ +In (prepareBinding ... bndr floats rhs), the binding is really + bndr = let floats in rhs +and prepareBinding decides whether to float the floats out, so that we get + floats; bndr = rhs +using doFloatFromRhs to make the decision. First it ANF-ises the RHS with +prepareRhs, which may add more floats. + +prepareBinding floats only let-bindings, and only lazy or ok-for-speculation +ones (FltLifted or FltOkSpec): if any of the floats is a case-float, a tick-float, +or a FltCareful let-binding, it floats nothing. So it returns just let-bindings +(LetFloats), and doFloatFromRhs is concerned only with let-bindings. All this is +done by onlyLazyLetFloats, in a single pass over the floats. + +We never float a FltCareful let-binding (a strict one whose RHS is not +ok-for-speculation), even out of the RHS of a strict binding: we just don't +think it is worth it. See (FFL1) in Note [FloatFlag for FloatLet] in +GHC.Core.Opt.Simplify.Env. + +Why not float case-floats and tick-floats too? + +(PB1) If the RHS of a lazy binding is /\tvs. body (with no value lambda), + simplLazyBind strips off the type lambdas, simplifies the body, and calls + prepareBinding on the body. If prepareBinding floats anything, simplLazyBind + must then abstract those floats over the `tvs`, with abstractFloats; see + Note [Floating and type abstraction] in GHC.Core.Opt.Simplify.Utils. But + abstractFloats can only deal with let-bindings: a case-float binds pattern + variables strictly, and cannot be abstracted over the `tvs`. T27737a was a + panic arising from a case-float reaching abstractFloats. + +(PB2) For a tick-float, see Note [Tick-floats] in GHC.Core.Opt.Simplify.Env. + +(PB3) It is simple, and before case-floats existed, a case simply stayed in the + RHS, so we lose nothing compared to that. + +(PB4) Lost opportunity. Consider + x = case addIntC# a b of (# r, c #) -> K r c + The scrutinee is ok-for-speculation, so we /could/ float the case-float out, + to get + case addIntC# a b of (# r, c #) -> let x = K r c in ... + Now x is bound to a value, so case-of-known-constructor can see through it. + That is just what we do for a strict let with an ok-for-speculation RHS (which + is FltOkSpec). But we would need to classify case-floats with a FloatFlag + (FltOkSpec if the scrutinee is ok-for-speculation, otherwise FltCareful), and + to avoid floating them when they must be abstracted over type variables (PB1). + We do not currently do this; the simplicity of returning only let-bindings + seems to be worth more. +-} {- Note [prepareRhs] ~~~~~~~~~~~~~~~~~~~~ @@ -813,7 +876,7 @@ prepareRhs env top_lvl occ rhs0 anfise (App fun arg) = do { (floats1, fun') <- anfise fun ; (floats2, arg') <- makeTrivial env top_lvl topDmd occ arg - ; return (floats1 `addLetFlts` floats2, App fun' arg') } + ; return (floats1 `appOL` floats2, App fun' arg') } anfise (Var fun) = return (emptyLetFloats, Var fun) @@ -879,43 +942,69 @@ makeTrivial env top_lvl dmd occ_fs expr bind = NonRec final_id expr2 ; traceSmpl "makeTrivial" (vcat [text "final_id" <+> ppr final_id, text "rhs" <+> ppr expr2 ]) - ; return ( floats `addLetFlts` unitLetFloat bind, Var final_id ) } + ; return ( assertPpr (not (needsCaseBinding expr_ty expr2)) (ppr bind) $ + -- See bindingOk and Note [Cannot trivialise] + floats `snocOL` bind, Var final_id ) } where id_info = vanillaIdInfo `setDemandInfo` dmd expr_ty = exprType expr bindingOk :: TopLevelFlag -> CoreExpr -> Type -> Bool --- True iff we can have a binding of this expression at this level +-- True iff we can have a let-binding of this expression at this level -- Precondition: the type is the type of the expression +-- See Note [Cannot trivialise] bindingOk top_lvl expr expr_ty | isTopLevel top_lvl = exprIsTopLevelBindable expr expr_ty - | otherwise = True + | otherwise = not (needsCaseBinding expr_ty expr) {- Note [Cannot trivialise] ~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Consider: - f :: Int -> Addr# +The goal of makeTrivial (when called from prepareRhs) is to transform + x = Just (f y) +into + x = let z = f y in Just z +and thence, by floating, into + z = f y + x = Just z +so that x is bound to a value. It returns only let-bindings (LetFloats), so +sometimes it cannot trivialise its argument, and must return it unchanged. + +(CT1) Nested bindings. Suppose that (f y) had type Int#, with a different data + constructor Just' :: Int# -> T. Then we cannot let-bind (f y), because that + would violate the let-can-float invariant (unless (f y) is ok-for-speculation). + We could case-bind it instead, to get + x = case f y of r -> Just' r + but there is no point: x is no more of a value than it was before. So we + lose nothing by not trivialising (f y); CorePrep will case-bind it anyway. + Hence the needsCaseBinding test in bindingOk. (See also #27910.) + + makeTrivialArg, called from mkDupableCont, may therefore return a non-trivial + argument, which may then be duplicated into several branches. That duplicates + code but not work, since only one branch is executed. - foo :: Bar - foo = Bar (f 3) +(CT2) Top-level bindings. Consider: + f :: Int -> Addr# -Then we can't ANF-ise foo, even though we'd like to, because -we can't make a top-level binding for the Addr# (f 3). And if -so we don't want to turn it into - foo = let x = f 3 in Bar x -because we'll just end up inlining x back, and that makes the -simplifier loop. Better not to ANF-ise it at all. + foo :: Bar + foo = Bar (f 3) -Literal strings are an exception. + Then we can't ANF-ise foo, even though we'd like to, because + we can't make a top-level binding for the Addr# (f 3). And if + so we don't want to turn it into + foo = let x = f 3 in Bar x + because we'll just end up inlining x back, and that makes the + simplifier loop. Better not to ANF-ise it at all. - foo = Ptr "blob"# + Literal strings are an exception. -We want to turn this into: + foo = Ptr "blob"# - foo1 = "blob"# - foo = Ptr foo1 + We want to turn this into: -See Note [Core top-level string literals] in GHC.Core. + foo1 = "blob"# + foo = Ptr foo1 + + See Note [Core top-level string literals] in GHC.Core. ************************************************************************ * * @@ -1191,7 +1280,7 @@ simplExprC env expr cont ; -- pprTrace "simplExprC ret" (ppr expr $$ ppr expr') $ -- pprTrace "simplExprC ret3" (ppr (seInScope env')) $ -- pprTrace "simplExprC ret4" (ppr (seLetFloats env')) $ - return (wrapFloats floats expr') } + simplWrapFloats (seMode env) floats expr' (contResultType cont) } -------------------------------------------------- simplExprF :: SimplEnv @@ -1282,18 +1371,20 @@ simplExprF1 env expr@(Lam {}) cont -- NB: countArgs counts all the args (incl type args) -- and likewise drop counts all binders (incl type lambdas) -simplExprF1 env (Case scrut bndr _ alts) cont +simplExprF1 env expr@(Case scrut bndr _ alts) cont + | Just (inner, outer) <- splitContForNoCaseCase env cont + -- See (COC-INV) in Note [sm_case_case: switching off case continuations] + = do { (floats, expr') <- simplExprF env expr inner + ; rebuildWithFloats env floats expr' outer } + + | otherwise = {-#SCC "simplExprF1-Case" #-} simplExprF env scrut (Select { sc_bndr = bndr, sc_alts = alts , sc_env = UnSimplified env, sc_cont = cont }) -simplExprF1 env (Let (Rec pairs) body) cont - | Just pairs' <- joinPointBindings_maybe pairs - = {-#SCC "simplRecJoinPoin" #-} simplRecJoinPoint env pairs' body cont - - | otherwise - = {-#SCC "simplRecE" #-} simplRecE env pairs body cont +-- Let-expressions +-- Try to eiminate the let altogether simplExprF1 env (Let (NonRec bndr rhs) body) cont | Type ty <- rhs -- First deal with type lets (let a = Type ty in e) = {-#SCC "simplExprF1-NonRecLet-Type" #-} @@ -1308,18 +1399,42 @@ simplExprF1 env (Let (NonRec bndr rhs) body) cont tick (PreInlineUnconditionally bndr) ; simplExprF env' body cont } - -- Now check for a join point. It's better to do the preInlineUnconditionally - -- test first, because joinPointBinding_maybe has to eta-expand, so a trivial - -- binding like { j = j2 |> co } would first be eta-expanded and then inlined - -- Better to test preInlineUnconditionally first. - | Just (bndr', rhs') <- joinPointBinding_maybe bndr rhs - = {-#SCC "simplNonRecJoinPoint" #-} - simplNonRecJoinPoint env bndr' rhs' body cont +simplExprF1 env expr@(Let {}) cont + | Just (inner, outer) <- splitContForNoCaseCase env cont + -- See (COC-INV) in Note [sm_case_case: switching off case continuations] + = do { (floats, expr') <- simplExprF env expr inner + ; rebuildWithFloats env floats expr' outer } - | otherwise +-- Now check for a join point. It's better to do the preInlineUnconditionally +-- test first, because joinPointBinding_maybe has to eta-expand, so a trivial +-- binding like { j = j2 |> co } would first be eta-expanded and then inlined +-- Better to test preInlineUnconditionally first. +-- +-- Must be after the seCaseCase stuff: todo: explain why +-- Example GHC.Internal.Debug +simplExprF1 env (Let bind body) cont + | Just bind' <- joinPointBind_maybe bind + = simplJoinPointBind env bind' body cont + +-- Non-recursive let +simplExprF1 env (Let (NonRec bndr rhs) body) cont = {-#SCC "simplNonRecE" #-} simplNonRecE env FromLet bndr (rhs, env) body cont +-- Recursive let +simplExprF1 env (Let (Rec pairs) body) cont + = {-#SCC "simplRecE" #-} + simplRecE env pairs body cont + + +splitContForNoCaseCase :: SimplEnv -> SimplCont + -> Maybe (SimplCont, SimplCont) +-- When seCaseCase is off, this function splits `cont` into (inner, outer), +-- where `inner` has only applications, and `outer` is non-trivial +splitContForNoCaseCase env cont + | seCaseCase env = Nothing + | otherwise = splitContArgs cont + {- Note [Avoiding space leaks in OutType] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Since the simplifier is run for multiple iterations, we need to ensure @@ -1362,6 +1477,13 @@ work. T5631 is a good example of this. emit it into the output program, after obtaining it from contResultType. (The hole type in ApplyToTy is only directly used to form the result type in a new Stop continuation.) + +- In particular, the type annotation on a Case is forced by returnCase in + GHC.Core.Opt.Simplify.Utils, where the Case is finally built (via mkCase, or + directly). Its callers + should not force it themselves: e.g. simplWrapFloats is given the type of the + body, but needs it only if there is a case-float, and forcing it in other + cases can do a lot of unnecessary work. -} --------------------------------- @@ -1473,10 +1595,16 @@ simplTick env tickish expr cont -- push the continuation inside the tick. This has the effect of moving the -- tick to the outside of a case or application context, allowing the normal -- 'case' and 'application' optimisations to fire. + -- + -- We return the tick as a FloatTick, /outside/ the floats from `expr`. + -- So all the code that was covered by the tick (including the floats, + -- notably single-alternative case floats) remains covered, as soft scope + -- requires; and yet `expr'` is exposed to the caller, e.g. for + -- case-of-known-constructor in rebuildWithFloats. + -- See Note [Tick-floats] in GHC.Core.Opt.Simplify.Env | tickishHasSoftScope tickish = do { (floats, expr') <- simplExprF env expr cont - ; return (floats, mkTick tickish expr') - } + ; return (unitOL (FloatTick tickish) `addFloatBindsF` floats, expr') } -- Push tick inside if the context looks like this will allow us to -- do a case-of-case - see Note [case-of-scc-of-case] @@ -1513,9 +1641,8 @@ simplTick env tickish expr cont no_floating_past_tick = do { let (inc,outc) = splitCont cont - ; (floats, expr1) <- simplExprF env expr inc - ; let expr2 = wrapFloats floats expr1 - tickish' = simplTickish env tickish + ; expr2 <- simplExprC env expr inc + ; let tickish' = simplTickish env tickish ; rebuild env (mkTick tickish' expr2) outc } @@ -1601,6 +1728,23 @@ simplTick env tickish expr cont rebuild :: SimplEnv -> OutExpr -> SimplCont -> SimplM (SimplFloats, OutExpr) rebuild env expr cont = rebuild_go (zapSubstEnv env) expr cont +rebuildWithFloats :: SimplEnv -> SimplFloats -> OutExpr -> SimplCont + -> SimplM (SimplFloats, OutExpr) +-- (rebuildWithFloats env floats expr cont) rebuilds (let floats in expr) +-- with continuation `cont`. Used only when seCaseCase is off. +-- See (COC3) in Note [sm_case_case: switching off case continuations] +rebuildWithFloats env floats expr cont + | Select { sc_bndr = bndr, sc_alts = alts, sc_env = se, sc_cont = cont' } <- cont + , isEmptyJoinFloats (sfJoinFloats floats) + , let env1 = zapSubstEnv env `setInScopeFromF` floats + , Just do_it <- knownConCase_maybe (mkAltEnv env1 se) expr bndr alts cont' + = do { (floats2, res) <- do_it + ; return (floats `addFloats` floats2, res) } + + | otherwise + = do { expr' <- simplWrapFloats (seMode env) floats expr (contHoleType cont) + ; rebuild env expr' cont } + rebuild_go :: HasDebugCallStack => SimplEnvIS -> OutExpr -> SimplCont -> SimplM (SimplFloats, OutExpr) -- SimplEnvIS: at this point the substitution in the SimplEnv is irrelevant; @@ -1655,24 +1799,22 @@ completeBindX env from_what bndr rhs body cont = do { (env1, bndr1) <- simplNonRecBndr env bndr -- Lambda binders don't have rules ; (floats, expr') <- simplNonRecBody env1 from_what body cont -- Do not float floats past the Case binder below - ; let expr'' = wrapFloats floats expr' - case_expr = Case rhs bndr1 (contResultType cont) [Alt DEFAULT [] expr''] + ; let res_ty = contResultType cont + ; expr'' <- simplWrapFloats (seMode env) floats expr' res_ty + ; case_expr <- returnCase rhs bndr1 res_ty [Alt DEFAULT [] expr''] ; return (emptyFloats env, case_expr) } | otherwise -- Make a let-binding = do { (env1, bndr1) <- simplNonRecBndr env bndr ; (env2, bndr2) <- addBndrRules env1 bndr bndr1 (BC_Let NotTopLevel NonRecursive) - ; let is_strict = isStrictId bndr2 - -- isStrictId: use simplified binder because the InId bndr might not have - -- a fixed runtime representation, which isStrictId doesn't expect - -- c.f. Note [Dark corner with representation polymorphism] - - ; (rhs_floats, rhs1) <- prepareBinding env NotTopLevel NonRecursive is_strict - bndr2 (emptyFloats env) rhs + ; (rhs_lets, lets_in_scope, rhs1) + <- prepareBinding env NotTopLevel NonRecursive + bndr2 (idType bndr2) (emptyFloats env) rhs -- NB: it makes a surprisingly big difference (5% in compiler allocation -- in T9630) to pass 'env' rather than 'env1'. It's fine to pass 'env', -- because this is completeBindX, so bndr is not in scope in the RHS. + ; let rhs_floats = mkLetSimplFloats lets_in_scope rhs_lets ; let env3 = env2 `setInScopeFromF` rhs_floats ; (bind_float, env4) <- completeBind (BC_Let NotTopLevel NonRecursive) @@ -2015,9 +2157,10 @@ simplNonRecE env from_what bndr (rhs, rhs_se) body cont -- If not, the invariant holds already, and it's optional. -- (FromBeta Lifted) or FromLet: look at the demand info + -- seCaseCase: see (COC-INV) + -- in Note [sm_case_case: switching off case continuations] _ -> seCaseCase env && isStrUsedDmd (idDemandInfo bndr) - ------------------ simplRecE :: SimplEnv -> [(InId, InExpr)] @@ -2085,10 +2228,10 @@ is a join point, and what 'cont' is, in a value of type MaybeJoinCont of a SpecConstr-generated RULE for a join point. -} -simplNonRecJoinPoint :: SimplEnv -> InId -> InExpr +simplJoinPointBind :: SimplEnv -> InBind -> InExpr -> SimplCont -> SimplM (SimplFloats, OutExpr) -simplNonRecJoinPoint env bndr rhs body cont +simplJoinPointBind env (NonRec bndr rhs) body cont = assert (isJoinId bndr ) $ wrapJoinCont env cont $ \ env cont -> do { -- We push join_cont into the join RHS and the body; @@ -2101,12 +2244,7 @@ simplNonRecJoinPoint env bndr rhs body cont ; (floats2, body') <- simplExprF env3 body cont ; return (floats1 `addFloats` floats2, body') } - ------------------- -simplRecJoinPoint :: SimplEnv -> [(InId, InExpr)] - -> InExpr -> SimplCont - -> SimplM (SimplFloats, OutExpr) -simplRecJoinPoint env pairs body cont +simplJoinPointBind env (Rec pairs) body cont = wrapJoinCont env cont $ \ env cont -> do { let bndrs = map fst pairs mult = contHoleScaling cont @@ -2125,18 +2263,13 @@ wrapJoinCont :: SimplEnv -> SimplCont -- Deal with making the continuation duplicable if necessary, -- and with the no-case-of-case situation. wrapJoinCont env cont thing_inside - | contIsStop cont -- Common case; no need for fancy footwork + | contIsStop cont -- Fast path: no need for fancy footwork = thing_inside env cont - | not (seCaseCase env) - -- See Note [Join points with -fno-case-of-case] - = do { (floats1, expr1) <- thing_inside env (mkBoringStop (contHoleType cont)) - ; let (floats2, expr2) = wrapJoinFloatsX floats1 expr1 - ; (floats3, expr3) <- rebuild (env `setInScopeFromF` floats2) expr2 cont - ; return (floats2 `addFloats` floats3, expr3) } - | otherwise -- Normal case; see Note [Join points and case-of-case] + -- Case-of-case should be /on/ here, else we should not + -- be in wrapJoinCont in the first place = do { (floats1, cont') <- mkDupableCont env cont ; (floats2, result) <- thing_inside (env `setInScopeFromF` floats1) cont' ; return (floats1 `addFloats` floats2, result) } @@ -2166,8 +2299,84 @@ trimJoinCont var (JoinPoint arity) cont = pprPanic "completeCall" $ ppr var $$ ppr cont -{- Note [Join points and case-of-case] -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +{- Note [sm_case_case: switching off case continuations] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Normally when we come across a `case` expression, we just push a `Select` +continuation onto the continuation, roughly like this. + simplExprF (Case scrut alts) cont + = simplExprF scrut (Select alts cont) + +There are two reasons that we might NOT want to do this + +1. Loss of full laziness. The case-of-case transformation can hide + opportunities for let-floating (aka full laziness). For example + rec { f = \y. case (expensive x) of (a,b) -> blah } + We might hope to float the (expensive x) out of the \y-loop. + But if we inline `expensive` we might get + \y. case (case x of I# x' -> body) of (a,b) -> blah + Now if we do case-of-case we get + \y. case x if I# x2 -> + case body of (a,b) -> blah + + Sadly, at this point `body` mentions `x2`, so we can't float it out of the \y-loop. + +2. Pushing a `case` inside a `let` can prevent a join point from being + discovered (#27737). For example + case (letrec j x y = ... in id (j p q)) of blah + Here `j` is not /yet/ a join point, because it is not tail called, but it + well become one after we inline `id`. But if we push that `case` inwards + at the same time as inlinine `id` we'll get + letrec j x y = ... in case (j p q) of blah + and now `j` /still/ isn't a join point, and will never become one. This + matters in practice: #27737 + +Solution in both cases: in the "gentle" simplification phase that precedes the +first float-out transformation, never push a `Select` continuation. So we +do not push the `case` inwards. This behaiour is controlled by the `sm_case_case` +field of `SimplMode`, interrogated via `seCaseCase`. + +Some specifics, for when `sm_case_case` is False: + +(COC-INV) When `sm_case_case` is False we obey the following invariant: + The SimplCont never contains + - Select + - StrictBind + - StrictArg + This is achieved by testing `seCaseCase` just before pushing any of + those three constructors. Why StrictBind and StrictArg? Because + they mess with evaluation order in the same way that Select does. + +(COC1) The (COC-INV) also solves #25055, where we pushed a `case` inside `runRW`: + case (runRW# (\s. body)) of (a,b) -> blah + ---> + runRW# (\s. case body of (a,b) -> blah) + Again, we don't want to this when `sm_case_case` is False, but that falls + out as a simple consequence of (COC-INV) + +(COC2) Supose `sm_case_case` is False, and we are simplifying + + case (join j x = <j-rhs> in + case y of + A -> j 1 + B -> j 2 + C -> e) of <outer-alts> + + Usually, we'd push the outer continuation (case . of <outer-alts>) into + both the RHS and the body of the join point j. But since we aren't doing + case-of-case we could end up with this totally bogus result + + join x = case <j-rhs> of <outer-alts> in + case (case y of + A -> j 1 + B -> j 2 + C -> e) of <outer-alts> + + Again, (COC-INV) neatly avoid this bogosity: we never push a Select + onto the continuation. This is much nicer than switching off case-of-case + specifically (which we used to do). + +Note [Join points and case-of-case] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When we perform the case-of-case transform (or otherwise push continuations inward), we want to treat join points specially. Since they're always tail-called and we want to maintain this invariant, we can do this (for any @@ -2198,44 +2407,6 @@ optional! We need to make the continuation E duplicable (since we are duplicating it) with mkDupableCont. -Note [Join points with -fno-case-of-case] -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Supose case-of-case is switched off, and we are simplifying - - case (join j x = <j-rhs> in - case y of - A -> j 1 - B -> j 2 - C -> e) of <outer-alts> - -Usually, we'd push the outer continuation (case . of <outer-alts>) into -both the RHS and the body of the join point j. But since we aren't doing -case-of-case we may then end up with this totally bogus result - - join x = case <j-rhs> of <outer-alts> in - case (case y of - A -> j 1 - B -> j 2 - C -> e) of <outer-alts> - -This would be OK in the language of the paper, but not in GHC: j is no longer -a join point. We can only do the "push continuation into the RHS of the -join point j" if we also push the continuation right down to the /jumps/ to -j, so that it can evaporate there (trimJoinCont). Then, if we are doing -case-of-case, we'll get to: - - join x = case <j-rhs> of <outer-alts> in - case y of - A -> j 1 - B -> j 2 - C -> case e of <outer-alts> - -which is great. - -Bottom line: if case-of-case is off, we must stop pushing the continuation -inwards altogether at any join point. Instead simplify the (join ... in ...) -with a Stop continuation, and wrap the original continuation around the -outside. Surprisingly tricky! ************************************************************************ @@ -2353,49 +2524,14 @@ simplOutId :: SimplEnvIS -> OutId -> SimplCont -> SimplM (SimplFloats, OutExpr) simplOutId env fun cont | fun `hasKey` runRWKey , ApplyToTy { sc_cont = cont1 } <- cont - , ApplyToTy { sc_cont = cont2, sc_arg_ty = hole_ty } <- cont1 - , ApplyToVal { sc_cont = cont3, sc_arg = arg, sc_cast = arg_mco - , sc_env = arg_se, sc_hole_ty = fun_ty } <- cont2 - -- Do this even if (contIsStop cont), or if seCaseCase is off. - -- See Note [No eta-expansion in runRW#] - = do { let (_saf,arg_env) = mkAltEnv env arg_se - - overall_res_ty = contResultType cont3 - -- hole_ty is the type of the current runRW# application - (outer_cont, new_runrw_res_ty, inner_cont) - | seCaseCase env = (mkBoringStop overall_res_ty, overall_res_ty, cont3) - | otherwise = (cont3, hole_ty, mkBoringStop hole_ty) - -- Only when case-of-case is on. See GHC.Driver.Config.Core.Opt.Simplify - -- Note [Case-of-case and full laziness] - - -- If the argument is a literal lambda already, take a short cut - -- This isn't just efficiency: - -- * If we don't do this we get a beta-redex every time, so the - -- simplifier keeps doing more iterations. - -- * Even more important: see Note [No eta-expansion in runRW#] - ; arg' <- case arg of - Lam s body -> do { (env', s') <- simplBinder arg_env s - ; body' <- simplExprC env' body inner_cont - ; return (Lam s' body') } - -- Important: do not try to eta-expand this lambda - -- See Note [No eta-expansion in runRW#] - - _ -> do { s' <- newId (fsLit "s") ManyTy realWorldStatePrimTy - ; let (m,_,_) = splitFunTy fun_ty - env' = arg_env `addNewInScopeIds` [s'] - hole_ty = mkVisFunTy m realWorldStatePrimTy new_runrw_res_ty - ; cont' <- pushCastMCo env' arg_mco $ - ApplyToVal { sc_arg = Var s', sc_cast = MRefl - , sc_env = Simplified OkDup - , sc_cont = inner_cont - , sc_hole_ty = hole_ty } - -- cont' applies to s', then K - ; body' <- simplExprC env' arg cont' - ; return (Lam s' body') } - - ; let rr' = getRuntimeRep new_runrw_res_ty - call' = mkApps (Var fun) [mkTyArg rr', mkTyArg new_runrw_res_ty, arg'] - ; rebuild_go env call' outer_cont } + , ApplyToTy { sc_cont = cont2 } <- cont1 + , ApplyToVal { sc_cont = cont3, sc_arg = arg, sc_env = arg_se + , sc_cast = arg_mco, sc_hole_ty = fun_ty } <- cont2 + = case splitContForNoCaseCase env cont3 of + Nothing -> do { e' <- simplRunRW env fun arg arg_se arg_mco fun_ty cont3 + ; return (emptyFloats env, e') } + Just (ink,outk) -> do { e' <- simplRunRW env fun arg arg_se arg_mco fun_ty ink + ; rebuild env e' outk } -- Normal case for (f e1 .. en) simplOutId env fun cont @@ -2430,6 +2566,51 @@ simplOutId env fun cont ; rebuildCall env arg_info cont } } } } } +simplRunRW :: SimplEnv + -> OutId -- runRW# + -> CoreExpr -- Main value argument `e` of runRW# + -> StaticEnv -- ...and its static envt + -> MOutCoercion -- ...and its MCoercion + -> OutType -- Type of (runRW# @k @ty), always t1->t2 + -> SimplCont -- Continuation to push into body of `e` + -> SimplM OutExpr +simplRunRW env fun arg arg_se arg_mco fun_ty cont + -- Do this even if (contIsStop cont), or if seCaseCase is off. + -- See Note [No eta-expansion in runRW#] + = do { let (_saf,arg_env) = mkAltEnv env arg_se + + overall_res_ty = contResultType cont + -- hole_ty is the type of the current runRW# application + + -- If the argument is a literal lambda already, take a short cut + -- This isn't just efficiency: + -- * If we don't do this we get a beta-redex every time, so the + -- simplifier keeps doing more iterations. + -- * Even more important: see Note [No eta-expansion in runRW#] + ; arg' <- case arg of + Lam s body -> do { (env', s') <- simplBinder arg_env s + ; body' <- simplExprC env' body cont + ; return (Lam s' body') } + -- Important: do not try to eta-expand this lambda + -- See Note [No eta-expansion in runRW#] + + _ -> do { s' <- newId (fsLit "s") ManyTy realWorldStatePrimTy + ; let (m,_,_) = splitFunTy fun_ty + env' = arg_env `addNewInScopeIds` [s'] + hole_ty = mkVisFunTy m realWorldStatePrimTy overall_res_ty + ; cont' <- pushCastMCo env' arg_mco $ + ApplyToVal { sc_arg = Var s', sc_cast = MRefl + , sc_env = Simplified OkDup + , sc_cont = cont + , sc_hole_ty = hole_ty } + -- cont' applies to s', then K + ; body' <- simplExprC env' arg cont' + ; return (Lam s' body') } + + ; let rr' = getRuntimeRep overall_res_ty + call' = mkApps (Var fun) [mkTyArg rr', mkTyArg overall_res_ty, arg'] + ; return call' } + --------------------------------------------------------- -- Dealing with a call site @@ -2460,8 +2641,8 @@ rebuildCall env fun_info , sc_hole_ty = fun_ty, sc_cont = cont }) | UnSimplified arg_env <- arg_se , isStrictArgInfo fun_info -- Strict arguments - , seCaseCase env -- But only when case-of-case is on. - -- See Note [Case-of-case and full laziness] + , seCaseCase env -- But only when case-of-case is on; see (COC-INV) + -- in Note [sm_case_case: switching off case continuations] = simplExprF (arg_env `setInScopeFromE` env) arg $ addCastMCo arg_mco $ StrictArg { sc_fun = fun_info, sc_fun_ty = fun_ty @@ -2469,7 +2650,7 @@ rebuildCall env fun_info , sc_cont = cont } -- Note [Shadowing in the Simplifier] - | otherwise -- Lazy, or already simplified arguments + | otherwise -- Lazy, or already simplified arguments, or -fno-case-of-case -- DO NOT float anything outside, hence simplExprC -- There is no benefit (unlike in a let-binding), and we'd -- have to be very careful about bogus strictness through @@ -2753,14 +2934,10 @@ fireRuleAFTER env rule_match arg_specs cont | RM { rm_rule = rule, rm_rhs = rhs, rm_args = rhs_args , rm_floats = float_bs } <- rule_match = do { let env' = env `addNewInScopeIds` floatsBinders float_bs - ; (floats, e') <- simplExprF env' rhs $ - pushOutArgs (exprType rhs) rhs_args $ - pushArgSpecs (drop (ruleArity rule) arg_specs) cont - ; return $ - if isEmptyFloatBinds float_bs -- Not very pretty - then (floats, e') - else (emptyFloats env', GHC.Core.Make.wrapFloats float_bs $ - wrapFloats floats e') } + ; addFloatBinds (contHoleScaling cont) float_bs $ + simplExprF env' rhs $ + pushOutArgs (exprType rhs) rhs_args $ + pushArgSpecs (drop (ruleArity rule) arg_specs) cont } tryRules :: SimplEnv -> [CoreRule] @@ -3223,41 +3400,9 @@ rebuildCase, reallyRebuildCase -- 1. Eliminate the case if there's a known constructor -------------------------------------------------- -rebuildCase (saf,env) scrut case_bndr alts cont - | Lit lit <- scrut -- No need for same treatment as constructors - -- because literals are inlined more vigorously - , not (litIsLifted lit) - = do { tick (KnownBranch case_bndr) - ; case findAlt (LitAlt lit) alts of - Nothing -> missingAlt env case_bndr alts cont - Just (Alt _ bs rhs) -> simpl_rhs env scrut bs rhs } - - | Just (in_scope', wfloats, con, ty_args, other_args) - <- exprIsConApp_maybe (getUnfoldingInRuleMatch env) scrut - -- Works when the scrutinee is a variable with a known unfolding - -- as well as when it's an explicit constructor application - , let env0 = setInScopeSet env in_scope' - = do { tick (KnownBranch case_bndr) - ; let -- case_bndr_unf: see Note [Do not duplicate constructor applications] - case_bndr_rhs | exprIsTrivial scrut = scrut - | otherwise = con_app - con_app = Var (dataConWorkId con) `mkTyApps` ty_args - `mkApps` other_args - ; wrapDataConFloats env wfloats case_bndr cont $ - case findAlt (DataAlt con) alts of - Nothing -> missingAlt env0 case_bndr alts cont - Just (Alt DEFAULT bs rhs) -> simpl_rhs env0 case_bndr_rhs bs rhs - Just (Alt _ bs rhs) -> knownCon env0 scrut con other_args - case_bndr bs rhs cont - } - where - simpl_rhs env case_bndr_rhs bs rhs - = assert (null bs) $ - do { (floats1, env') <- simplAuxBind (saf,env) case_bndr case_bndr_rhs - -- scrut is a constructor application, - -- hence satisfies let-can-float invariant - ; (floats2, expr') <- simplExprF env' rhs cont - ; return (floats1 `addFloats` floats2, expr') } +rebuildCase saf_env scrut case_bndr alts cont + | Just do_it <- knownConCase_maybe saf_env scrut case_bndr alts cont + = do_it -------------------------------------------------- -- 2. Eliminate the case if scrutinee is evaluated @@ -3318,54 +3463,74 @@ rebuildCase (saf,env) scrut case_bndr alts cont | otherwise = reallyRebuildCase (saf,env) scrut case_bndr alts cont -doCaseToLet :: OutExpr -- Scrutinee - -> InId -- Case binder - -> Bool --- The situation is case scrut of b { DEFAULT -> body } --- Can we transform thus? let { b = scrut } in body -doCaseToLet scrut case_bndr - | isTyCoVar case_bndr -- Respect GHC.Core - = isTyCoArg scrut -- Note [Core type and coercion invariant] - - | isUnliftedType (exprType scrut) - -- We can call isUnliftedType here: scrutinees always have a fixed RuntimeRep (see FRRCase). - -- Note however that we must check 'scrut' (which is an 'OutExpr') and not 'case_bndr' - -- (which is an 'InId'): see Note [Dark corner with representation polymorphism]. - -- Using `exprType` is typically cheap because `scrut` is typically a variable. - -- We could instead use mightBeUnliftedType (idType case_bndr), but that hurts - -- the brain more. Consider that if this test ever turns out to be a perf - -- problem (which seems unlikely). - = exprOkForSpeculation scrut - - | otherwise -- Scrut has a lifted type - = exprIsHNF scrut - -- || isStrUsedDmd (idDemandInfo case_bndr) - -- We no longer look at the demand on the case binder - -- See Note [Case-to-let for strictly-used binders] - -------------------------------------------------- -- 3. Catch-all case -------------------------------------------------- reallyRebuildCase (saf,env) scrut case_bndr alts cont - | not (seCaseCase env) -- Only when case-of-case is on. - -- See GHC.Driver.Config.Core.Opt.Simplify - -- Note [Case-of-case and full laziness] - = do { case_expr <- simplAlts (saf,env) scrut case_bndr alts - (mkBoringStop (contHoleType cont)) - ; rebuild env case_expr cont } - - | otherwise - = do { (floats, env', cont') <- mkDupableCaseCont env alts cont - ; case_expr <- simplAlts (saf,env') scrut - (scaleIdBy holeScaling case_bndr) - (scaleAltsBy holeScaling alts) - cont' - ; return (floats, case_expr) } + = do { (alt_env, scrut', case_bndr', imposs_deflt_cons, in_alts) + <- prepareCase (saf,env) scrut (scaleIdBy holeScaling case_bndr) + (scaleAltsBy holeScaling alts) + ; case in_alts of + [in_alt] -> rebuildSingleAltCase (saf,alt_env) scrut' case_bndr' + imposs_deflt_cons bndr_swap cont in_alt + _ -> rebuildMultiAltCase (saf,alt_env) scrut' case_bndr' + imposs_deflt_cons bndr_swap cont in_alts } where holeScaling = contHoleScaling cont -- Note [Scaling in case-of-case] + bndr_swap = scrutOkForBinderSwap scrut + +rebuildSingleAltCase :: (SimplAltFlag, SimplEnv) + -> OutExpr -> OutId -- Scrutinee and case binder + -> [AltCon] -- Constructors impossible in the DEFAULT alt + -> BinderSwapDecision + -> SimplCont + -> InAlt + -> SimplM (SimplFloats, OutExpr) +-- The arguments are prepared by prepareCase +-- We return the case as a FloatCase float, so that the floats from its RHS +-- are not trapped inside it. See Note [Floating single-alternative cases] +-- There is only one alternative, so no need to make `cont` dupable +rebuildSingleAltCase (saf,alt_env) scrut' case_bndr' imposs_deflt_cons bndr_swap cont in_alt + = do { (con, bs', alt_floats, rhs') <- simplAlt (saf,alt_env) (Just scrut') imposs_deflt_cons + case_bndr' bndr_swap cont in_alt + ; let no_floats = emptyFloats alt_env + case_float + | DEFAULT <- con + , doCaseToLet scrut' case_bndr' + = -- Make a let-float, not a case-float, to maintain invariant + -- (FFC1) of Note [Case-floats] in GHC.Core.Opt.Simplify.Env. + -- We get here (rather than doing case-to-let in rebuildCase) when + -- prepareAlts has pruned away all but the DEFAULT alternative + no_floats `addLetFloat` NonRec case_bndr' scrut' + | otherwise + = addCaseFloat no_floats scrut' case_bndr' con bs' + ; return (case_float `addFloats` alt_floats, rhs') } + +rebuildMultiAltCase :: (SimplAltFlag, SimplEnv) + -> OutExpr -> OutId -- Scrutinee and case binder + -> [AltCon] -- Constructors impossible in the DEFAULT alt + -> BinderSwapDecision + -> SimplCont + -> [InAlt] + -> SimplM (SimplFloats, OutExpr) +-- The arguments are prepared by prepareCase +rebuildMultiAltCase (saf,alt_env) scrut' case_bndr' imposs_deflt_cons bndr_swap cont in_alts + = do { -- NB: pass alt_env, not the env before prepareCase, to mkDupableCaseCont, + -- so that the case binder stays in scope in env' + (floats, env', cont') <- mkDupableCaseCont alt_env in_alts cont + ; traceSmpl "rebuildMultiAltCase" (vcat [ ppr case_bndr' + , text "cont':" <+> ppr cont' + , text "in_scope" <+> ppr (seInScope env') ]) + ; alts' <- forM in_alts $ + simplAltC (saf,env') (Just scrut') imposs_deflt_cons + case_bndr' bndr_swap cont' + ; case_expr <- mkCase (seMode env') scrut' case_bndr' (contResultType cont') alts' + -- mkCase forces the type; see Note [Avoiding space leaks in OutType] + ; return (floats, case_expr) } + {- simplCaseBinder checks whether the scrutinee is a variable, v. If so, try to eliminate uses of v in the RHSs in favour of case_bndr; that @@ -3466,7 +3631,6 @@ robust here. (Otherwise, there's a danger that we'll simply drop the Note [Scaling in case-of-case] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - When two cases commute, if done naively, the multiplicities will be wrong: case (case u of w[1] { (x[1], y[1]) } -> f x y) of w'[Many] @@ -3498,17 +3662,16 @@ scale the entire case we are simplifying, by a scaling factor which can be computed in the continuation (with function `contHoleScaling`). -} -simplAlts :: (SimplAltFlag, SimplEnv) - -> OutExpr -- Scrutinee - -> InId -> [InAlt] -- Alts (non-empty) - -> SimplCont - -> SimplM OutExpr -- Returns the complete simplified case expression - -simplAlts (saf,env0) scrut case_bndr alts cont' - = do { traceSmpl "simplAlts" (vcat [ ppr case_bndr - , text "cont':" <+> ppr cont' - , text "in_scope" <+> ppr (seInScope env0) ]) - ; (env1, case_bndr1) <- simplAltIdBinder (saf,env0) case_bndr +prepareCase :: (SimplAltFlag, SimplEnv) + -> OutExpr -- Scrutinee + -> InId -> [InAlt] -- Case binder and alts (non-empty) + -> SimplM ( SimplEnv -- For the alternatives + , OutExpr -- Scrutinee, perhaps improved by improveSeq + , OutId -- Case binder + , [AltCon] -- Constructors impossible in the DEFAULT alt + , [InAlt] ) -- Alternatives, from prepareAlts +prepareCase (saf,env0) scrut case_bndr alts + = do { (env1, case_bndr1) <- simplAltIdBinder (saf,env0) case_bndr ; let case_bndr2 = case_bndr1 `setIdUnfolding` evaldUnfolding env2 = modifyInScope env1 case_bndr2 -- See Note [Case binder evaluated-ness] @@ -3523,15 +3686,34 @@ simplAlts (saf,env0) scrut case_bndr alts cont' -- NB: pass case_bndr::InId, not case_bndr' :: OutId, to prepareAlts -- See Note [Shadowing in prepareAlts] in GHC.Core.Opt.Simplify.Utils - ; alts' <- forM in_alts $ - simplAlt (saf,alt_env') (Just scrut') imposs_deflt_cons - case_bndr' (scrutOkForBinderSwap scrut) cont' - - ; let alts_ty' = contResultType cont' - -- See Note [Avoiding space leaks in OutType] - ; seqType alts_ty' `seq` - mkCase (seMode env0) scrut' case_bndr' alts_ty' alts' } + ; return (alt_env', scrut', case_bndr', imposs_deflt_cons, in_alts) } +{- Note [Floating single-alternative cases] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +When reallyRebuildCase finds a single-alternative case (after prepareAlts) + case e of b { (# a, c #) -> let x1 = .. in ... let xn = .. in (# e1, e2 #) } +it does not return the case expression; instead it returns + * floats: [FloatCase e b (# a,c #) [a,c], x1 = .., ..., xn = ..] + * result: (# e1, e2 #) +This is done by rebuildSingleAltCase. See Note [LetFloats] in GHC.Core.Opt.Simplify.Env. + +Why? Because a caller (notably rebuildWithFloats, when case-of-case is +switched off) may want to do case-of-known-constructor on the result. If we +returned the whole case, exprIsConApp_maybe would have to walk all the way +down through the case and the lets, which can be quadratic (#27737, T18223). + +This is not restricted to the no-case-of-case path: when case-of-case is on, +the continuation has already been pushed into the alternative, and the +floats are simply wrapped around the result, or floated further out of a +strict let (which a StrictBind continuation would do anyway). The +FloatFlag (FltCareful or FltOkSpec) stops a case-float from floating out of +a lazy let, or to top level; see doFloatFromRhs. + +We do not call mkCase when we build the FloatCase. Instead, simplWrapFloats +calls mkCase when we eventually wrap the FloatCase around an expression, so we +still get case-merging, identity-case elimination, caseRules, etc. +See Note [Wrapping case-floats with mkCase] in GHC.Core.Opt.Simplify.Utils. +-} ------------------------------------ improveSeq :: (FamInstEnv, FamInstEnv) @@ -3552,6 +3734,16 @@ improveSeq _ (_,env) scrut _ case_bndr1 _ ------------------------------------ +simplAltC :: (SimplAltFlag, SimplEnv) -> Maybe OutExpr -> [AltCon] -> OutId + -> BinderSwapDecision -> SimplCont -> InAlt + -> SimplM OutAlt +-- Like simplAlt, but wraps the floats around the RHS +simplAltC env scrut' imposs_deflt_cons case_bndr' bndr_swap' cont' alt + = do { (con, bs, floats, rhs) <- simplAlt env scrut' imposs_deflt_cons + case_bndr' bndr_swap' cont' alt + ; rhs' <- simplWrapFloats (seMode (snd env)) floats rhs (contResultType cont') + ; return (Alt con bs rhs') } + simplAlt :: (SimplAltFlag, SimplEnv) -> Maybe OutExpr -- The scrutinee -> [AltCon] -- These constructors can't be present when @@ -3561,19 +3753,24 @@ simplAlt :: (SimplAltFlag, SimplEnv) -- add unfolding `v :-> bndr |> sym co` -> SimplCont -> InAlt - -> SimplM OutAlt + -> SimplM (AltCon, [OutVar], SimplFloats, OutExpr) + -- Returns the simplified alternative, in pieces + -- The floats scope over the RHS only, and may mention the + -- binders of the alternative. So the caller must either wrap + -- them around the RHS (simplAltC), or put them after a case-float + -- that binds the binders (rebuildSingleAltCase) simplAlt (saf,env) _scrut' imposs_deflt_cons case_bndr' bndr_swap' cont' (Alt DEFAULT bndrs rhs) = assert (null bndrs) $ do { let env' = addDefaultUnfoldings env case_bndr' bndr_swap' imposs_deflt_cons - ; rhs' <- simplAltExprC (saf,env') rhs cont' - ; return (Alt DEFAULT [] rhs') } + ; (floats, rhs') <- simplAltExprF (saf,env') rhs cont' + ; return (DEFAULT, [], floats, rhs') } simplAlt (saf,env) _scrut' _ case_bndr' bndr_swap' cont' (Alt (LitAlt lit) bndrs rhs) = assert (null bndrs) $ do { let env' = addAltUnfoldings env case_bndr' bndr_swap' (Lit lit) - ; rhs' <- simplAltExprC (saf,env') rhs cont' - ; return (Alt (LitAlt lit) [] rhs') } + ; (floats, rhs') <- simplAltExprF (saf,env') rhs cont' + ; return (LitAlt lit, [], floats, rhs') } simplAlt (saf,env) scrut' _ case_bndr' bndr_swap' cont' (Alt (DataAlt con) vs rhs) = do { -- See Note [Adding evaluatedness info to pattern-bound variables] @@ -3591,8 +3788,8 @@ simplAlt (saf,env) scrut' _ case_bndr' bndr_swap' cont' (Alt (DataAlt con) vs rh con_app = mkConApp2 con inst_tys' vs' env'' = addAltUnfoldings env' case_bndr' bndr_swap' con_app - ; rhs' <- simplAltExprC (saf,env'') rhs cont' - ; return (Alt (DataAlt con) vs' rhs') } + ; (floats, rhs') <- simplAltExprF (saf,env'') rhs cont' + ; return (DataAlt con, vs', floats, rhs') } {- Note [Adding evaluatedness info to pattern-bound variables] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -3773,11 +3970,6 @@ simplAltExprF (saf,env) expr cont SAF_Out -> simplOutExpr env expr cont SAF_In -> simplExprF env expr cont -simplAltExprC :: (SimplAltFlag, SimplEnv) -> CoreExpr -> SimplCont -> SimplM OutExpr -simplAltExprC env expr cont - = do { (floats, expr') <- simplAltExprF env expr cont - ; return (wrapFloats floats expr') } - {- Note [Case binder evaluated-ness] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -3854,48 +4046,69 @@ All this should happen in one sweep. Note [FloatBinds from constructor wrappers] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -If we have FloatBinds coming from the constructor wrapper -(as in Note [exprIsConApp_maybe on data constructors with wrappers]), -we cannot float past them. We'd need to float the FloatBind -together with the simplify floats, unfortunately the -simplifier doesn't have case-floats. The simplest thing we can -do is to wrap all the floats here. The next iteration of the -simplifier will take care of all these cases and lets. +exprIsConApp_maybe may return FloatBinds, e.g. coming from a constructor +wrapper (as in Note [exprIsConApp_maybe on data constructors with wrappers]), +or from looking through lets and single-alternative cases in the scrutinee. +These floats scope over the result of case-of-known-constructor. + +Since the Simplifier's floats can contain case-floats as well as let-floats +(see Note [LetFloats] in GHC.Core.Opt.Simplify.Env), we simply add them to +the SimplFloats, outside the floats from simplifying the alternative; see +knownConCase_maybe. We do not wrap them around the result, because then a +subsequent case-of-known-constructor on the result would have to walk +through them all over again, which can be quadratic (#27737). Given data T = MkT !Bool, this allows us to simplify case $WMkT b of { MkT x -> f x } to case b of { b' -> f b' }. - -We could try and be more clever (like maybe `wfloats` only contains -let binders, so we could float them). But the need for the extra -complication is not clear. -} -wrapDataConFloats :: SimplEnv -> FloatBinds -> InId -> SimplCont - -> SimplM (SimplFloats, OutExpr) - -> SimplM (SimplFloats, OutExpr) --- See Note [FloatBinds from constructor wrappers] -wrapDataConFloats env wfloats case_bndr cont thing_inside - | isEmptyFloatBinds wfloats - = thing_inside - | otherwise - = do { (floats, expr) <- thing_inside - ; return ( emptyFloats env - , GHC.Core.Make.wrapFloats (fmap scale_float wfloats) $ - wrapFloats floats expr ) } - where - -- scale_float scales case-floats by the multiplicity of the continuation hole - -- (see Note [Scaling in case-of-case]). - -- Let floats are _not_ scaled, because they are aliases anyway. - scale_float (GHC.Core.FloatCase scrut case_bndr con vars) - = GHC.Core.FloatCase scrut (scale_id case_bndr) con (map scale_id vars) - scale_float flt@(GHC.Core.FloatLet {}) = flt - scale_float flt@(GHC.Core.FloatTick {}) = flt +knownConCase_maybe :: (SimplAltFlag, SimplEnv) + -> OutExpr -- Scrutinee + -> InId -- Case binder + -> [InAlt] -- Alternatives (increasing order) + -> SimplCont + -> Maybe (SimplM (SimplFloats, OutExpr)) +-- Case-of-known-constructor: returns Just if the scrutinee is a literal +-- or (via exprIsConApp_maybe) a constructor application +knownConCase_maybe (saf,env) scrut case_bndr alts cont + | Lit lit <- scrut -- No need for same treatment as constructors + -- because literals are inlined more vigorously + , not (litIsLifted lit) + = Just $ + do { tick (KnownBranch case_bndr) + ; case findAlt (LitAlt lit) alts of + Nothing -> missingAlt env case_bndr alts cont + Just (Alt _ bs rhs) -> simpl_rhs env scrut bs rhs } - scale_id id = scaleVarBy holeScaling id + | Just (in_scope', wfloats, con, ty_args, other_args) + <- exprIsConApp_maybe (getUnfoldingInRuleMatch env) scrut + -- Works when the scrutinee is a variable with a known unfolding + -- as well as when it's an explicit constructor application + , let env0 = setInScopeSet env in_scope' + = Just $ + do { tick (KnownBranch case_bndr) + ; let -- case_bndr_unf: see Note [Do not duplicate constructor applications] + case_bndr_rhs | exprIsTrivial scrut = scrut + | otherwise = con_app + con_app = Var (dataConWorkId con) `mkTyApps` ty_args + `mkApps` other_args + -- The wfloats scope over the result + -- See Note [FloatBinds from constructor wrappers] + ; addFloatBinds hole_scaling wfloats $ + case findAlt (DataAlt con) alts of + Nothing -> missingAlt env0 case_bndr alts cont + Just (Alt DEFAULT bs rhs) -> simpl_rhs env0 case_bndr_rhs bs rhs + Just (Alt _ bs rhs) -> knownCon env0 scrut con other_args + case_bndr bs rhs cont } - holeScaling = contHoleScaling cont `mkMultMul` idMult case_bndr + | otherwise + = Nothing + where + hole_scaling = idMult case_bndr `mkMultMul` contHoleScaling cont + -- See Note [Scaling in case-of-case] + -- This is the contHoleScaling of the original Select continuation -- We are in the following situation -- case[p] case[q] u of { D x -> C v } of { C x -> w } -- And we are producing case[??] u of { D x -> w[x\v]} @@ -3911,6 +4124,33 @@ wrapDataConFloats env wfloats case_bndr cont thing_inside -- Which is ill-typed with respect to linearity. So it needs to be a -- case[Many]. + simpl_rhs env case_bndr_rhs bs rhs + = assert (null bs) $ + do { (floats1, env') <- simplAuxBind (saf,env) case_bndr case_bndr_rhs + -- scrut is a constructor application, + -- hence satisfies let-can-float invariant + ; (floats2, expr') <- simplExprF env' rhs cont + ; return (floats1 `addFloats` floats2, expr') } + +addFloatBinds :: Mult -> FloatBinds + -> SimplM (SimplFloats, a) -> SimplM (SimplFloats, a) +-- (addFloatBinds scaling fbs thing_inside) adds `fbs` outside the floats +-- returned by `thing_inside`. The `scaling` is the multiplicity of the +-- continuation hole, by which case-floats are scaled, because they now +-- scope over that continuation: see Note [Scaling in case-of-case]. +-- Let floats do not need this treatment +addFloatBinds scaling fbs thing_inside + | isEmptyFloatBinds fbs -- Short cut + = thing_inside + | otherwise + = do { (floats, res) <- thing_inside + ; return (fmap scale_float fbs `addFloatBindsF` floats, res) } + where + scale_float (FloatCase scrut b con vars) + = FloatCase scrut (scale_id b) con (map scale_id vars) + scale_float flt = flt + + scale_id id = scaleVarBy scaling id knownCon :: SimplEnv -> OutExpr -- The scrutinee @@ -4149,8 +4389,8 @@ mkDupableContWithDmds env _ -- No need to use mkDupableCont before simplNonRecBody; we -- use cont once here, and then share the result if necessary - ; let join_body = wrapFloats floats1 join_inner - res_ty = contResultType cont + ; let res_ty = contResultType cont + ; join_body <- simplWrapFloats (seMode env) floats1 join_inner res_ty ; mkDupableStrictBind env bndr' join_body res_ty } @@ -4185,7 +4425,8 @@ mkDupableContWithDmds env _ ; arg_bndr <- newId (fsLit "arg") m arg_ty ; let env' = env `addNewInScopeIds` [arg_bndr] ; (floats, join_rhs) <- rebuildCall env' (addValArgTo fun (Var arg_bndr) fun_ty) cont - ; mkDupableStrictBind env' arg_bndr (wrapFloats floats join_rhs) rhs_ty } + ; join_rhs' <- simplWrapFloats (seMode env) floats join_rhs rhs_ty + ; mkDupableStrictBind env' arg_bndr join_rhs' rhs_ty } where thumbsUpPlanA (StrictArg {}) = False thumbsUpPlanA (StrictBind {}) = True @@ -4244,7 +4485,7 @@ mkDupableContWithDmds env _ scaleIdBy cont_scaling case_bndr ; alts' <- forM (scaleAltsBy cont_scaling alts) $ - simplAlt (saf,alt_env1) Nothing [] case_bndr' NoBinderSwap alt_cont + simplAltC (saf,alt_env1) Nothing [] case_bndr' NoBinderSwap alt_cont -- Safe to say that there are no handled-cons for the DEFAULT case -- NB: simplBinder does not zap deadness occ-info, so -- a dead case_bndr' will still advertise its deadness ===================================== compiler/GHC/Core/Opt/Simplify/Utils.hs ===================================== @@ -8,7 +8,7 @@ The simplifier utilities module GHC.Core.Opt.Simplify.Utils ( -- Rebuilding - rebuildLam, mkCase, prepareAlts, + rebuildLam, mkCase, returnCase, prepareAlts, simplWrapFloats, tryEtaExpandRhs, wantEtaExpansion, -- Inlining, @@ -28,7 +28,7 @@ module GHC.Core.Opt.Simplify.Utils ( contIsTrivial, contArgs, contIsRhs, mkBottomCont, hasArgs, countArgs, contOutArgs, dropContArgs, mkBoringStop, mkRhsStop, mkLazyArgStop, - interestingCallContext, + interestingCallContext, splitContArgs, -- ArgInfo ArgInfo(..), ArgSpec(..), RemainingArgDmds, mkArgInfo, @@ -74,12 +74,13 @@ import GHC.Types.InlinePragma import GHC.Types.Tickish import GHC.Types.Demand import GHC.Types.Var.Set +import GHC.Types.Var.Env ( InScopeSet ) import GHC.Types.Basic import GHC.Types.Name.Env import GHC.Data.List.Infinite ( Infinite(..) ) import qualified GHC.Data.List.Infinite as Inf -import GHC.Data.OrdList ( isNilOL ) +import GHC.Data.OrdList ( fromOL ) import GHC.Data.FastString ( fsLit ) import GHC.Utils.Misc @@ -173,10 +174,11 @@ data SimplCont , sc_opt :: Bool -- True <=> sc_co has had optCoercion applied to it -- See Note [Avoid re-simplifying coercions] -- in GHC.Core.Opt.Simplify.Iteration - , sc_cont :: SimplCont } + , sc_cont :: SimplCont } -- Invariant: never a CastIt; successive casts + -- are merged (see pushCast in GHC.Core.Opt.Simplify.Iteration) | ApplyToVal -- (ApplyToVal arg K)[e] = K[ e arg ] - { sc_hole_ty :: OutType -- Type of the function, presumably (forall a. blah) + { sc_hole_ty :: OutType -- Type of the function, presumably (ty1 -> ty2) -- See Note [The hole type in ApplyToTy] , sc_env :: StaticEnv -- See Note [StaticEnv] , sc_arg :: CoreExpr -- The argument @@ -495,12 +497,54 @@ contIsDupable :: SimplCont -> Bool contIsDupable (Stop {}) = True contIsDupable (ApplyToTy { sc_cont = k }) = contIsDupable k contIsDupable (ApplyToVal { sc_env = se }) = okToDupSE se -- See (SE1) in Note [StaticEnv] -contIsDupable (Select { sc_env = se }) = okToDupSE se -- ...ditto... +contIsDupable (Select { sc_env = se, sc_bndr = bndr, sc_alts = alts, sc_cont = k }) + = okToDupSE se -- ...ditto... + || (isUnpackingAlts bndr alts && contIsDupable k) + -- See Note [Duplicating unpacking continuations] contIsDupable (StrictBind { sc_env = se }) = okToDupSE se -- ...ditto... contIsDupable (StrictArg { sc_dup = dup }) = okToDup dup -- ...ditto... contIsDupable (CastIt { sc_cont = k }) = contIsDupable k contIsDupable (TickIt _ k) = contIsDupable k +isUnpackingAlts :: InId -> [InAlt] -> Bool +-- True of the alternatives of case e of b { K x y -> y } +-- and nested versions thereof; see Note [Duplicating unpacking continuations] +isUnpackingAlts case_bndr [Alt _ bndrs rhs] = go (case_bndr : bndrs) rhs + where + go bound (Var v) = v `elem` bound + go bound (Case (Var v) b _ [Alt _ bs rhs]) + | v `elem` bound = go (b : bs ++ bound) rhs + go _ _ = False +isUnpackingAlts _ _ = False + +{- Note [Duplicating unpacking continuations] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Worker/wrapper for CPR produces a worker like this + $wf = \ds -> case (case ds of { A -> R e1; B -> R e2 }) of ww { __DEFAULT -> + case ww of { R y -> y } } +The intention is that the unboxing (case . of R y -> y) cancels with the boxing +(R e1) and (R e2). But the continuation pushed into the inner case is + (Select ww [__DEFAULT -> case ww of { R y -> y }]) +which has more than one alternative to go into, so mkDupableCont would make it +dupable by creating a join point + join $j ww = case ww of { __DEFAULT -> case ww of { R y -> y } } + in case ds of { A -> jump $j (R e1); B -> jump $j (R e2) } +That is terrible if $j fails to inline; and even if it does inline, it takes an +extra Simplifier iteration to tidy up (T15304). + +So contIsDupable treats a Select as dupable if its alternatives are "unpacking +alternatives": a single alternative whose RHS is a variable bound by that +alternative (a pattern variable or the case binder), or a single-alternative case +on such a variable whose own RHS is again unpacking, and so on (to allow for nested +CPR). Such a continuation is tiny, so duplicating it costs nothing, and then +case-of-known-constructor cancels it with the constructor in each branch, giving + $wf = \ds -> case ds of { A -> e1; B -> e2 } + +We insist that the variables are /bound/ by the continuation: a free variable might +be mapped by the substitution in the (UnSimplified env) to a big expression, which +we would then duplicate. +-} + ------------------- contIsTrivial :: SimplCont -> Bool contIsTrivial (Stop {}) = True @@ -632,6 +676,65 @@ contOutArgs env cont -- No more arguments go _ = [] +splitContArgs :: SimplCont -> Maybe (SimplCont, SimplCont) +-- Splits `cont` into (inner, outer), where `inner` has only +-- applications and casts, and `outer` is non-trivial +-- A cast goes in `inner` only if it is followed by an application; +-- see Note [Do not push a cast inwards unnecessarily] +splitContArgs cont@(ApplyToTy { sc_cont = cont1 }) + = do { (inner, outer) <- splitContArgs cont1 + ; return (cont { sc_cont = inner }, outer) } +splitContArgs cont@(ApplyToVal { sc_cont = cont1 }) + = do { (inner, outer) <- splitContArgs cont1 + ; return (cont { sc_cont = inner }, outer) } +splitContArgs cont@(CastIt { sc_cont = cont1 }) + | isAppCont cont1 -- No need for isAppCont to look past a CastIt, because + -- cont1 is never a CastIt; see the invariant on CastIt + = do { (inner, outer) <- splitContArgs cont1 + ; return (cont { sc_cont = inner }, outer) } +splitContArgs outer + | contIsStop outer = Nothing + | otherwise = -- pprTrace "splitContHoleType" (ppr hole_ty) $ + return (mkBoringStop hole_ty, outer) + where + hole_ty = contHoleType outer + +isAppCont :: SimplCont -> Bool +-- True of an application continuation +isAppCont (ApplyToVal {}) = True +isAppCont (ApplyToTy {}) = True +isAppCont _ = False + +{- Note [Do not push a cast inwards unnecessarily] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +When case-of-case is off, splitContArgs splits the continuation into an `inner` +part, which we push into a `case` or `let`, and an `outer` part, which we +rebuild around the result. The point of `inner` is to push applications +inwards, so it should stop as soon as it can. So a cast goes in `inner` only +if it is followed by an application, e.g. (CastIt (ApplyToVal ..)); otherwise, +e.g. (CastIt Stop) or (CastIt (Select ..)), the cast goes in `outer`. +(Successive casts are merged, so we need not look past a CastIt.) Consider + f x = Wrap (case x of { 0 -> g 10; 1 -> g 20; _ -> g 30 }) +where Wrap is a newtype constructor, so we have a cast round the case. +If we pushed the cast into the alternatives we would get + f = \x -> case x of { 0 -> g 10 |> co; 1 -> g 20 |> co; _ -> g 30 |> co } +Then + * We duplicate the coercion in every alternative. The coercion can be big: + for a derived Generic instance, `from` has one alternative per constructor + and the coercion mentions the whole representation type, so the total is + quadratic (T5642, T16577). + * We lose cast worker/wrapper: the RHS is no longer of form (e |> co), so + we never get f = $wf |> co. And nothing ever moves the casts back out + of the alternatives, so the duplication lasts all the way to CorePrep. + +Leaving the cast in `outer` gives + f = \x -> (case x of { 0 -> g 10; 1 -> g 20; _ -> g 30 }) |> co +We do this for every caller of splitContArgs, including a `let` with join +points: if we pushed the cast into a join point's RHS we would have to push +it into every jump too, but the jumps may be in a multi-alternative case +from which we are keeping it out. +-} + dropContArgs :: FullArgCount -> SimplCont -> SimplCont dropContArgs 0 cont = cont dropContArgs n (ApplyToTy { sc_cont = cont }) = dropContArgs (n-1) cont @@ -2408,7 +2511,7 @@ new binding is abstracted. Several points worth noting (Why is it OK to float the unlifted `foo` there? See Note [Core top-level string literals] in GHC.Core; - it is controlled by GHC.Core.Opt.Simplify.Env.unitLetFloat.) + it is controlled by GHC.Core.Opt.Simplify.Env.getFF_Let.) It is also necessary to do dependency analysis, because otherwise (in #24551) we might get `foo = \@_ -> "missing"#` at the @@ -2416,18 +2519,20 @@ new binding is abstracted. Several points worth noting manifestly a literal string. -} -abstractFloats :: UnfoldingOpts -> TopLevelFlag -> [OutTyVar] -> SimplFloats - -> OutExpr -> SimplM ([OutBind], OutExpr) -abstractFloats uf_opts top_lvl main_tvs floats body +abstractFloats :: UnfoldingOpts -> TopLevelFlag -> [OutTyVar] + -> InScopeSet -- Includes the binders of the LetFloats + -> LetFloats -- Let-bindings only: see (PB1) in Note [prepareBinding] + -- in GHC.Core.Opt.Simplify.Iteration + -> OutExpr -> SimplM ([OutBind], OutExpr) +abstractFloats uf_opts top_lvl main_tvs in_scope floats body = assert (notNull body_floats) $ - assert (isNilOL (sfJoinFloats floats)) $ do { let sccs = concatMap to_sccs body_floats ; (subst, float_binds) <- mapAccumLM abstract empty_subst sccs ; return (float_binds, GHC.Core.Subst.substExpr subst body) } where is_top_lvl = isTopLevel top_lvl - body_floats = letFloatBinds (sfLetFloats floats) - empty_subst = GHC.Core.Subst.mkEmptySubst (sfInScope floats) + body_floats = fromOL floats + empty_subst = GHC.Core.Subst.mkEmptySubst in_scope -- See wrinkle (AB5) in Note [Which type variables to abstract over] -- for why we need to re-do dependency analysis @@ -2862,7 +2967,64 @@ and now we can do case-merge again, getting the desired -} -mkCase, mkCase1, mkCase2, mkCase3 +simplWrapFloats :: SimplMode -> SimplFloats + -> OutExpr -- The body + -> OutType -- The type of the body + -> SimplM OutExpr +-- Wrap the floats around the body, using mkCase for case-floats +-- See Note [Wrapping case-floats with mkCase] +simplWrapFloats mode (SimplFloats { sfLetFloats = lfs, sfJoinFloats = jbs }) body body_ty + = go (fromOL lfs) + where + go [] = return (wrapJoinFloats jbs body) + -- Always safe to put the joins on the inside, + -- since the values can't refer to them + go (fb : fbs) = do { body' <- go fbs; wrap fb body' } + + wrap (FloatLet bind) body = return (Let bind body) + wrap (FloatTick t) body = return (mkTick t body) + wrap (FloatCase scrut bndr con bs) body + = mkCase mode scrut bndr body_ty [Alt con bs body] + -- NB: we must not force body_ty if there are no case-floats; that can + -- do a lot of unnecessary work. mkCase forces it when it builds the Case; + -- see Note [Avoiding space leaks in OutType] in GHC.Core.Opt.Simplify.Iteration + -- body_ty: lets, ticks and cases do not change the type, so every + -- case-float has the same result type: the type of the original body. + -- And body_ty comes from outside, so it cannot mention `bs` + +{- Note [Wrapping case-floats with mkCase] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +The Simplifier returns a single-alternative case as a FloatCase, rather than +building it with mkCase; see Note [Floating single-alternative cases] in +GHC.Core.Opt.Simplify.Iteration. So when we eventually wrap the floats around +an expression, simplWrapFloats uses mkCase for each FloatCase, so that we get +all the things that mkCase does: case-merging, identity-case elimination, +caseRules, etc. For example, case-merging turns + case x of b { DEFAULT -> case b of { A -> e1; B -> e2 } } +into case x of b { A -> e1; B -> e2 } +which arises, for example, from x `seq` case x of { A -> e1; B -> e2 }. + +Is the case-merging expensive? mergeCaseAlts looks past lets (wrinkle (MC4) of +Note [Merge Nested Cases] in GHC.Core.Utils), but it stops at anything else, +such as a case that does not scrutinise the case binder. So in a chain + FloatCase e1 b1, lets1, FloatCase e2 b2, lets2, ... +each let is examined by only one FloatCase, and the total cost is linear. + +It could be quadratic if successive FloatCases evaluated the /same/ value: + FloatCase e b1, FloatCase b1 b2, FloatCase b2 b3, lots of lets, case b3 of alts +Then each FloatCase merges with the case below it, floating the lets out again, +so that the next one looks past all of them again. But such a chain does not +survive simplification: a case whose scrutinee is already evaluated (such as +the case binder b1 of an enclosing case) is eliminated by rebuildCase (see +Note [Case to let transformation] in GHC.Core.Opt.Simplify.Iteration) long before +it becomes a FloatCase. (Calling mkCase on every case, as we used to, has +exactly the same theoretical exposure.) + +We do not use simplWrapFloats for the FloatBinds returned by the rule matcher; +GHC.Core.Make.wrapFloats is fine for those. +-} + +mkCase, mkCase1, mkCase2 :: SimplMode -> OutExpr -> OutId -> OutType -> [OutAlt] -- Alternatives in standard (increasing) order @@ -2957,12 +3119,12 @@ mkCase2 mode scrut bndr alts_ty alts -- See Note [Unreachable caseRules alternatives] -- in GHC.Core.Opt.ConstantFold - ; mkCase3 mode scrut' bndr' alts_ty $ + ; returnCase scrut' bndr' alts_ty $ add_default (re_sort alts') } | otherwise - = mkCase3 mode scrut bndr alts_ty alts + = returnCase scrut bndr alts_ty alts where -- We need to keep the correct association between the scrutinee and its -- binder if the latter isn't dead. Hence we wrap rhs of alternatives with @@ -3039,8 +3201,12 @@ in GHC.Core.Opt.ConstantFold) -------------------------------------------------- -- Catch-all -------------------------------------------------- -mkCase3 _mode scrut bndr alts_ty alts - = return (Case scrut bndr alts_ty alts) +returnCase :: OutExpr -> OutId -> OutType -> [OutAlt] -> SimplM OutExpr +-- Build the Case, forcing alts_ty as we emit it into the output program +-- See Note [Avoiding space leaks in OutType] in GHC.Core.Opt.Simplify.Iteration +returnCase scrut bndr alts_ty alts + = seqType alts_ty `seq` + return (Case scrut bndr alts_ty alts) -- See Note [Exitification] and Note [Do not inline exit join points] in -- GHC.Core.Opt.Exitify ===================================== compiler/GHC/Core/SimpleOpt.hs ===================================== @@ -11,7 +11,7 @@ module GHC.Core.SimpleOpt ( simpleOptPgm, simpleOptExpr, simpleOptExprNoInline, simpleOptExprWith, -- ** Join points - joinPointBinding_maybe, joinPointBindings_maybe, + joinPointBinding_maybe, joinPointBindings_maybe, joinPointBind_maybe, -- ** Predicates on expressions exprIsConApp_maybe, exprIsLiteral_maybe, exprIsLambda_maybe, @@ -1199,6 +1199,18 @@ joinPointBindings_maybe :: [(InBndr, InExpr)] -> Maybe [(InBndr, InExpr)] joinPointBindings_maybe bndrs = mapM (uncurry joinPointBinding_maybe) bndrs +joinPointBind_maybe :: InBind -> Maybe InBind +joinPointBind_maybe (NonRec bndr rhs) + | Just (bndr', rhs') <- joinPointBinding_maybe bndr rhs + = Just (NonRec bndr' rhs') + +joinPointBind_maybe (Rec pairs) + | Just pairs' <- joinPointBindings_maybe pairs + = Just (Rec pairs') + +joinPointBind_maybe _other + = Nothing + {- Note [JoinId vs TailCallInfo] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ * Occurrence information is /fundamentally fragile/; that is, it may @@ -1542,7 +1554,8 @@ exprIsConApp_maybe :: HasDebugCallStack => InScopeEnv -> CoreExpr -> Maybe (InScopeSet, FloatBinds, DataCon, [Type], [CoreExpr]) exprIsConApp_maybe ise@(ISE in_scope id_unf) expr - = go (Left in_scope) emptyFloatBinds expr (CC [] MRefl) + = -- pprTrace "exprIsConApp" (ppr expr) $ + go (Left in_scope) emptyFloatBinds expr (CC [] MRefl) where go :: Either InScopeSet Subst -- Left in-scope means "empty substitution" @@ -1655,7 +1668,8 @@ exprIsConApp_maybe ise@(ISE in_scope id_unf) expr | idArity fun == 0 , Just rhs <- expandUnfolding_maybe unfolding , let in_scope' = extend_in_scope (exprFreeVars rhs) - = go (Left in_scope') floats rhs cont + = -- pprTrace "exprIsConApp:unf" (ppr fun <+> ppr rhs) $ + go (Left in_scope') floats rhs cont -- See Note [exprIsConApp_maybe on literal strings] | (fun `hasKey` unpackCStringIdKey) || @@ -1695,17 +1709,21 @@ exprIsConApp_maybe ise@(ISE in_scope id_unf) expr subst_co (Right s) co = GHC.Core.Subst.substCo s co subst_expr (Left {}) e = e - subst_expr (Right s) e = substExpr s e + subst_expr (Right s) e = -- pprTrace "subst_expr" (text "subst" <+> ppr s $$ text "expr" <+> ppr e) $ + substExpr s e - subst_bndr msubst bndr - = (Right subst', bndr') + subst_bndrs subst bs = mapAccumL subst_bndr subst bs + + subst_bndr (Left in_scope) bndr + | bndr `elemInScopeSet` in_scope = subst_bndr1 (mkEmptySubst in_scope) bndr + | otherwise = (Left (in_scope `extendInScopeSet` bndr), bndr) + subst_bndr (Right subst) bndr = subst_bndr1 subst bndr + + subst_bndr1 subst bndr + = -- pprTrace "subst_bndr1" (ppr bndr <+> ppr bndr' $$ ppr subst) $ + (Right subst', bndr') where (subst', bndr') = substBndr subst bndr - subst = case msubst of - Left in_scope -> mkEmptySubst in_scope - Right subst -> subst - - subst_bndrs subst bs = mapAccumL subst_bndr subst bs extend (Left in_scope) v e = Right (extendSubst (mkEmptySubst in_scope) v e) extend (Right s) v e = Right (extendSubst s v e) ===================================== compiler/GHC/Core/Type.hs ===================================== @@ -55,7 +55,7 @@ module GHC.Core.Type ( splitForAllForAllTyBinders, splitForAllForAllTyBinder_maybe, splitForAllTyCoVar_maybe, splitForAllTyCoVar, splitForAllTyVar_maybe, splitForAllCoVar_maybe, - splitPiTy_maybe, splitPiTy, splitPiTys, collectPiTyBinders, + splitPiTy_maybe, splitPiTy, splitPiTys, splitUninstantiatedValArgTys, getRuntimeArgTys, mkTyConBindersPreferAnon, mkPiTy, mkPiTys, @@ -263,7 +263,6 @@ import GHC.Utils.Monad.StrictReader import GHC.Data.FastString import GHC.Data.Maybe ( orElse, isJust ) -import GHC.List (build) -- $type_classification -- #type_classification# @@ -1599,17 +1598,20 @@ splitPiTys ty = split ty ty [] split orig_ty ty bs | Just ty' <- coreView ty = split orig_ty ty' bs split orig_ty _ bs = (reverse bs, orig_ty) -collectPiTyBinders :: Type -> [PiTyBinder] -collectPiTyBinders ty = build $ \c n -> - let - split (ForAllTy b res) = Named b `c` split res - split (FunTy { ft_af = af, ft_mult = w, ft_arg = arg, ft_res = res }) - = Anon (Scaled w arg) af `c` split res - split ty | Just ty' <- coreView ty = split ty' - split _ = n - in - split ty -{-# INLINE collectPiTyBinders #-} +splitUninstantiatedValArgTys :: Type -> [Type] +-- This function takes a type apart, returning all its /value/ +-- argument types (including (forall (co::t1~t2).t) +-- doing no instantiation at all. +-- E.g. splitUinstantiatedValArgTys (forall a. a -> Int -> T a) +-- returns [a, Int] +-- It's a pretty specialised function, hence its long name +splitUninstantiatedValArgTys ty = go ty + where + go (ForAllTy (Bndr b _) res) | isCoVar b = varType b : go res + | otherwise = go res + go (FunTy { ft_arg = arg, ft_res = res }) = arg : go res + go ty | Just ty' <- coreView ty = go ty' + go _ = [] -- | Extracts a list of run-time arguments from a function type, -- looking through newtypes to the right of arrows. ===================================== compiler/GHC/Core/Utils.hs ===================================== @@ -804,6 +804,9 @@ mkSingleAltCase scrut case_bndr con bndrs body body_ty = exprType body case_ty -- See Note [Care with the type of a case expression] + | not (any isTyCoVar bndrs) -- Fast path: only TyCoVars can occur in body_ty + = body_ty + | Just body_ty' <- occCheckExpand bndrs body_ty = body_ty' @@ -2207,6 +2210,8 @@ fun_always_ok _ = True -- | A special version of 'exprOkForSpeculation' used during -- Note [Speculative evaluation]. When the predicate arg `fun_ok` returns False -- for `b`, then `b` is never considered ok-for-spec. +-- +-- This is the whole reason for the fun_ok arg to expr_ok. exprOkForSpecEval :: (Id -> Bool) -> CoreExpr -> Bool exprOkForSpecEval fun_ok = expr_ok fun_ok primOpOkForSpeculation @@ -2240,10 +2245,9 @@ expr_ok fun_ok primop_ok (Case scrut bndr _ alts) && altsAreExhaustive alts expr_ok fun_ok primop_ok other_expr - | (expr, args) <- collectArgs other_expr + | (expr, val_args) <- collectValArgs other_expr = case stripTicksTopE (not . tickishCounts) expr of - Var f -> - app_ok fun_ok primop_ok f args + Var f -> app_ok fun_ok primop_ok f val_args -- 'LitRubbish' is the only literal that can occur in the head of an -- application and will not be matched by the above case (Var /= Lit). @@ -2258,9 +2262,10 @@ expr_ok fun_ok primop_ok other_expr ----------------------------- app_ok :: (Id -> Bool) -> (PrimOp -> Bool) -> Id -> [CoreArg] -> Bool -app_ok fun_ok primop_ok fun args +app_ok fun_ok primop_ok fun val_args | not (fun_ok fun) - = False -- This code path is only taken for Note [Speculative evaluation] + = False -- This code path is only taken for exprOkForSpecEval + -- See Note [Speculative evaluation] | idArity fun > n_val_args -- Partial application: just check passing the arguments is OK @@ -2281,17 +2286,18 @@ app_ok fun_ok primop_ok fun args ClassOpId _ is_terminating_result | is_terminating_result -- See Note [exprOkForSpeculation and type classes] - -> assertPpr (n_val_args == 1) (ppr fun $$ ppr args) $ + -> assertPpr (n_val_args == 1) (ppr fun $$ ppr val_args) $ True -- assert: terminating result type => can't be applied; -- c.f the _other case below PrimOpId op _ | primOpIsDiv op - , Lit divisor <- last args + , Lit divisor <- last val_args -- there can be 2 args (most div primops) or 3 args -- (WordQuotRem2Op), hence the use of last/init - -> not (isZeroLit divisor) && all (expr_ok fun_ok primop_ok) (init args) + -> not (isZeroLit divisor) && + all ok_for_spec (init val_args) -- Special case for dividing operations that fail -- In general they are NOT ok-for-speculation -- (which primop_ok will catch), but they ARE OK @@ -2300,12 +2306,14 @@ app_ok fun_ok primop_ok fun args -- can get rid of a thunk in an inner loop | otherwise -> primop_ok op && args_ok + -- Assumes that the primop does not evaluate its + -- definitely-lifted arguments _other -- Unlifted and terminating types; -- Also c.f. the Var case of exprIsHNF | isTerminatingType fun_ty -- See Note [exprOkForSpeculation and type classes] || definitelyUnliftedType fun_ty - -> assertPpr (n_val_args == 0) (ppr fun $$ ppr args) + -> assertPpr (n_val_args == 0) (ppr fun $$ ppr val_args) True -- Both terminating types (e.g. Eq a), and unlifted types (e.g. Int#) -- are non-functions and so will have no value args. The assert is -- just to check this. @@ -2321,32 +2329,43 @@ app_ok fun_ok primop_ok fun args -- for evaluated-ness of the fun; -- see Note [exprOkForSpeculation and evaluated variables] where - fun_ty = idType fun - n_val_args = valArgCount args - (arg_tys, _) = splitPiTys fun_ty + ok_for_spec = expr_ok fun_ok primop_ok -- Used for recursive calls + + fun_ty = idType fun + n_val_args = length val_args + val_arg_tys = splitUninstantiatedValArgTys fun_ty + -- val_arg_tys are /uninstantiated/; see (EOKS1) -- Even if a function call itself is OK, any unlifted -- args are still evaluated eagerly and must be checked - args_ok = all2Prefix arg_ok arg_tys args - arg_ok :: PiTyVarBinder -> CoreExpr -> Bool - arg_ok (Named _) _ = True -- A type argument - arg_ok (Anon ty _) arg -- A term argument - | definitelyLiftedType (scaledThing ty) - = True -- lifted args are not evaluated eagerly - | otherwise - = expr_ok fun_ok primop_ok arg + -- arg_ok bndr arg = field_ok bndr NotMarkedStrict arg + -- See Note [exprOkForSpeculation] (a,b) + args_ok = all2Prefix arg_ok val_arg_tys val_args + arg_ok :: Type -> CoreExpr -> Bool + arg_ok arg_ty arg = ok_for_spec arg || definitely_lifted arg_ty arg -- Used for strict DataCon worker arguments -- See (SFC1) of Note [Strict fields in Core] - fields_ok str_marks = all3Prefix field_ok arg_tys str_marks args - field_ok :: PiTyVarBinder -> StrictnessMark -> CoreExpr -> Bool - field_ok (Named _) _ _ = True - field_ok (Anon ty _) str arg - | NotMarkedStrict <- str -- iff it's a lazy field - , definitelyLiftedType (scaledThing ty) -- and its type is lifted - = True -- then the worker app does not eval - | otherwise - = expr_ok fun_ok primop_ok arg + -- See Note [exprOkForSpeculation] (a,b) + fields_ok str_marks = all3Prefix field_ok val_arg_tys str_marks val_args + field_ok :: Type -> StrictnessMark -> CoreExpr -> Bool + field_ok arg_ty str arg + = ok_for_spec arg || (definitely_lifted arg_ty arg && str==NotMarkedStrict) + -- The (ok_for_spec arg) test works for /both/ for unlifted types, /and/ + -- for lifted but strict fields. E.g. K (I# 3) is ok-for-spec, + -- even if K is strict + + -- We want to see if the argument type is definitely lifted. + -- But consider + -- (#,#) @rep1 @rep2 @ty1 @ty2 arg1 arg2 + -- We don't /instantiate/ the type of (#,#) (although we could) so we don't + -- know if the argument type is lifted or not. So we look at the type of + -- the /actual/ argument (it's usually a variable) instead. + definitely_lifted uninstantiated_arg_ty arg + = case typeLevity_maybe uninstantiated_arg_ty of + Just Lifted -> True + Just Unlifted -> False + Nothing -> definitelyLiftedType (exprType arg) ----------------------------- altsAreExhaustive :: [Alt b] -> Bool @@ -2390,8 +2409,42 @@ cantEtaReduceFun fun -- Don't undersaturate StrictWorkerIds. -- See Note [CBV Function Ids: overview] in GHC.Types.Id.Info. -{- Note [exprOkForSpeculation and type classes] -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +{- Note [exprOkForSpeculation] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Suppose we have + data T a = K !a Int# a + +Is the call (K e1 e2 e3) ok-for-speculation? Look at the arguments e1..e3, +and their types. The call is ok-for-speculation if each argument satisfies +`field_ok`, namely: + (a) (exprOkForSpeculation arg) holds, OR + (b) Arg type is definitely lifted and it is not marked strict + +For (a) we conservatively assume we are going to evaluate the argument. +If it is ok-for-spec, then fine. + +But if the argument is of a lifted type, and not marked strict (notably by +a data constructor) then (b) holds. For example + Just (reverse xs) +is ok-for-spec. See (EOKS1) for the argument liftedness test. + +If we have a plain variable `x`, is that ok-for-spec? Not if it is lifted: +it might be a thunk! Hence the (definitelyUnliftedType fun_ty) test. +Remember, a naked variable `x` will land in `app_ok x []` with no arguments. +See Note [exprOkForSpeculation and evaluated variables]. + +(EOKS1) To get the lifted-ness or otherwise of the arguments we just look at the + /uninstantiated/ type of the data constructor or primop. We'd get better information + if we instantiated, but it's also more expensive. Example: + (#,#) :: forall r1 r2 (a::TYPE r1) (b::TYPE r2). a -> b -> (# a, b #) + If we have a call + (#,#) @LiftedRep @IntRep @Int @Int# 3 4# + then we could see accurate liftedness by instantiation, but we don't try. + Instead we get the actual type from (exprType arg). That could be expensive, + but it really only happens for unboxed tuples. + +Note [exprOkForSpeculation and type classes] +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Consider (#22745, #15205) \(d :: C a b). case eq_sel (sc_sel d) of @@ -2674,8 +2727,7 @@ exprIsHNFlike is_con is_con_unf rubbish_lit_result e -- PAP: Check unlifted val_args args_hnf = all2Prefix check_arg val_arg_tys val_args - fun_ty = idType id - val_arg_tys = mapMaybe anonPiTyBinderType_maybe (collectPiTyBinders fun_ty) + val_arg_tys = splitUninstantiatedValArgTys (idType id) -- val_arg_tys = map exprType val_args, but much less costly. -- The obvious definition regresses T16577 by 30% so we don't do it. @@ -2700,7 +2752,6 @@ exprIsHNFlike is_con is_con_unf rubbish_lit_result e | otherwise = Nothing - {- Note [exprIsHNF Tick] ~~~~~~~~~~~~~~~~~~~~~ ===================================== compiler/GHC/Driver/Config/Core/Opt/Simplify.hs ===================================== @@ -80,7 +80,7 @@ initGentleSimplMode :: DynFlags -> SimplMode initGentleSimplMode dflags = (initSimplMode dflags InitialPhase "Gentle") { -- Don't do case-of-case transformations. -- This makes full laziness work better - -- See Note [Case-of-case and full laziness] + -- See Note [sm_case_case: switching off case continuations] sm_case_case = False } @@ -90,37 +90,3 @@ floatEnable dflags = (True, True) -> FloatEnabled (True, False)-> FloatNestedOnly (False, _) -> FloatDisabled - - -{- Note [Case-of-case and full laziness] -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Case-of-case can hide opportunities for let-floating (full laziness). -For example - rec { f = \y. case (expensive x) of (a,b) -> blah } -We might hope to float the (expensive x) out of the \y-loop. -But if we inline `expensive` we might get - \y. case (case x of I# x' -> body) of (a,b) -> blah -Now if we do case-of-case we get - \y. case x if I# x2 -> - case body of (a,b) -> blah - -Sadly, at this point `body` mentions `x2`, so we can't float it out of the -\y-loop. - -Solution: don't do case-of-case in the "gentle" simplification phase that -precedes the first float-out transformation. Implementation: - - * `sm_case_case` field in SimplMode - - * Consult `sm_case_case` (via `seCaseCase`) before doing case-of-case - in GHC.Core.Opt.Simplify.Iteration.rebuildCall. - -Wrinkles - -* This applies equally to the case-of-runRW# transformation: - case (runRW# (\s. body)) of (a,b) -> blah - ---> - runRW# (\s. case body of (a,b) -> blah) - Again, don't do this when `sm_case_case` is off. See #25055 for - a motivating example. --} ===================================== testsuite/tests/dmdanal/should_compile/T20510.stderr ===================================== @@ -1,7 +1,7 @@ ==================== Exitification transformation ==================== Result size of Exitification transformation - = {terms: 50, types: 22, coercions: 0, joins: 2/2} + = {terms: 33, types: 15, coercions: 0, joins: 2/2} -- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0} lvl :: Int @@ -11,7 +11,7 @@ lvl :: Int Guidance=IF_ARGS [] 10 10}] lvl = GHC.Internal.Types.I# 0# --- RHS size: {terms: 32, types: 14, coercions: 0, joins: 2/2} +-- RHS size: {terms: 29, types: 12, coercions: 0, joins: 2/2} small :: Int -> Int [LclIdX, Arity=1, @@ -22,7 +22,7 @@ small :: Int -> Int Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=False) Tmpl= \ (x [Dmd=S!P(SL)] :: Int) -> joinrec { - go [InlPrag=[2], Occ=T[2], Dmd=LC(S,C(1,!P(L)))] + go [InlPrag=[2], Occ=Many(T[2]), Dmd=LC(S,C(1,!P(L)))] :: Int -> Int -> Int [LclId[JoinId(2)(Nothing)], Arity=2, @@ -54,11 +54,11 @@ small :: Int -> Int Guidance=IF_ARGS [0 51] 63 10}] $wgo (ww [Occ=Once2] :: GHC.Internal.Prim.Int#) (ww [Occ=Once1!, Dmd=SL] :: GHC.Internal.Prim.Int#) - = case ww of ds { + = case ww of wild { __DEFAULT -> jump go - (GHC.Internal.Types.I# (GHC.Internal.Prim.+# ww ds)) - (GHC.Internal.Types.I# (GHC.Internal.Prim.-# ds 1#)); + (GHC.Internal.Types.I# (GHC.Internal.Prim.+# ww wild)) + (GHC.Internal.Types.I# (GHC.Internal.Prim.-# wild 1#)); 0# -> case x of { GHC.Internal.Types.I# y [Occ=Once1] -> GHC.Internal.Types.I# (GHC.Internal.Prim.*# ww y) @@ -67,13 +67,12 @@ small :: Int -> Int jump go lvl x}] small = \ (x [Dmd=S!P(SL)] :: Int) -> + case x of { GHC.Internal.Types.I# ww [Dmd=SL] -> join { exit :: GHC.Internal.Prim.Int# -> Int [LclId[JoinId(1)(Nothing)]] exit (ww :: GHC.Internal.Prim.Int#) - = case x of { GHC.Internal.Types.I# y -> - GHC.Internal.Types.I# (GHC.Internal.Prim.*# ww y) - } } in + = GHC.Internal.Types.I# (GHC.Internal.Prim.*# ww ww) } in joinrec { $wgo [InlPrag=[2], Occ=LoopBreaker] :: GHC.Internal.Prim.Int# -> GHC.Internal.Prim.Int# -> Int @@ -82,56 +81,17 @@ small Str=<L><SL>, Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True, WorkFree=True, Expandable=True, - Guidance=IF_ARGS [0 32] 43 10}] + Guidance=IF_ARGS [0 32] 33 10}] $wgo (ww :: GHC.Internal.Prim.Int#) (ww [Dmd=SL] :: GHC.Internal.Prim.Int#) - = case ww of ds { + = case ww of wild { __DEFAULT -> jump $wgo - (GHC.Internal.Prim.+# ww ds) (GHC.Internal.Prim.-# ds 1#); + (GHC.Internal.Prim.+# ww wild) (GHC.Internal.Prim.-# wild 1#); 0# -> jump exit ww }; } in - case x of { GHC.Internal.Types.I# ww [Dmd=SL] -> jump $wgo 0# ww } - --- RHS size: {terms: 1, types: 0, coercions: 0, joins: 0/0} -$trModule :: GHC.Internal.Prim.Addr# -[LclId, - Unf=Unf{Src=<vanilla>, TopLvl=True, - Value=True, ConLike=True, WorkFree=True, Expandable=True, - Guidance=IF_ARGS [] 20 0}] -$trModule = "main"# - --- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0} -$trModule :: GHC.Internal.Types.TrName -[LclId, - Unf=Unf{Src=<vanilla>, TopLvl=True, - Value=True, ConLike=True, WorkFree=True, Expandable=True, - Guidance=IF_ARGS [] 10 10}] -$trModule = GHC.Internal.Types.TrNameS $trModule - --- RHS size: {terms: 1, types: 0, coercions: 0, joins: 0/0} -$trModule :: GHC.Internal.Prim.Addr# -[LclId, - Unf=Unf{Src=<vanilla>, TopLvl=True, - Value=True, ConLike=True, WorkFree=True, Expandable=True, - Guidance=IF_ARGS [] 30 0}] -$trModule = "T20510"# - --- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0} -$trModule :: GHC.Internal.Types.TrName -[LclId, - Unf=Unf{Src=<vanilla>, TopLvl=True, - Value=True, ConLike=True, WorkFree=True, Expandable=True, - Guidance=IF_ARGS [] 10 10}] -$trModule = GHC.Internal.Types.TrNameS $trModule - --- RHS size: {terms: 3, types: 0, coercions: 0, joins: 0/0} -T20510.$trModule :: GHC.Internal.Types.Module -[LclIdX, - Unf=Unf{Src=<vanilla>, TopLvl=True, - Value=True, ConLike=True, WorkFree=True, Expandable=True, - Guidance=IF_ARGS [] 10 10}] -T20510.$trModule = GHC.Internal.Types.Module $trModule $trModule + jump $wgo 0# ww + } ===================================== testsuite/tests/show-bytecode/show-bytecode-hpc.stdout ===================================== @@ -59,135 +59,133 @@ objects: arity: 0 literals: label ‘_hpc_tickboxes_Example_hpc’ used items: named item ‘primes’ - object ‘primes2_@name_suffix@’: + object ‘primes’: arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: - object ‘primes2_sat_@name_suffix@’: - arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: - object ‘primes2_sat_@name_suffix@’: - arity: 0 - literals: - label ‘_hpc_tickboxes_Example_hpc’ - word 3 - info table of ‘IS’ - used items: - named item ‘$fNumNatural’ - named item ‘fromInteger’ - named item ‘$fEnumNatural’ - named item ‘enumFrom’ - object ‘primes2_sat_@name_suffix@’: - arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: named item ‘isPrime_@name_suffix@’ - named item ‘filter’ - object ‘isPrime_@name_suffix@’: - arity: 1 literals: label ‘_hpc_tickboxes_Example_hpc’ + info table of ‘(:)’ used items: - object ‘isPrime_sat_@name_suffix@’: + object ‘isPrime_@name_suffix@’: arity: 1 - literals: label ‘_hpc_tickboxes_Example_hpc’ + literals: + label ‘_hpc_tickboxes_Example_hpc’ used items: - object ‘isPrime_sat_@name_suffix@’: + object ‘isPrime_primes_sat_@name_suffix@’: arity: 1 literals: label ‘_hpc_tickboxes_Example_hpc’ used items: - object ‘isPrime_sat_@name_suffix@’: - arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: named item ‘primes’ - object ‘isPrime_sat_@name_suffix@’: + object ‘isPrime_primes_sat_@name_suffix@’: arity: 1 literals: label ‘_hpc_tickboxes_Example_hpc’ used items: - object ‘isPrime_sat_@name_suffix@’: + object ‘isPrime_primes_sat_@name_suffix@’: arity: 0 literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: - object ‘v_@name_suffix@’: - arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: - named item ‘$fIntegralInteger’ - named item ‘$fNumNatural’ - named item ‘(^)’ - object ‘v1_@name_suffix@’: - arity: 0 - literals: - label ‘_hpc_tickboxes_Example_hpc’ - word 2 - info table of ‘IS’ - used items: <none> - object ‘pap_@name_suffix@’: - arity: 3 - literals: <none> - used items: <none> - object ‘isPrime_sat_@name_suffix@’: + used items: named item ‘primes’ + object ‘isPrime_primes_sat_@name_suffix@’: arity: 1 literals: label ‘_hpc_tickboxes_Example_hpc’ used items: - object ‘v_@name_suffix@’: + object ‘isPrime_primes_sat_@name_suffix@’: arity: 0 literals: label ‘_hpc_tickboxes_Example_hpc’ used items: - named item ‘$fOrdNatural’ - named item ‘(<=)’ - object ‘v1_@name_suffix@’: + object ‘v_@name_suffix@’: + arity: 0 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: + named item ‘$fIntegralInteger’ + named item ‘$fNumNatural’ + named item ‘(^)’ + object ‘v1_@name_suffix@’: + arity: 0 + literals: + label ‘_hpc_tickboxes_Example_hpc’ + word 2 + info table of ‘IS’ + used items: <none> + object ‘pap_@name_suffix@’: + arity: 3 + literals: <none> + used items: <none> + object ‘isPrime_primes_sat_@name_suffix@’: arity: 1 literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: <none> + used items: + object ‘v_@name_suffix@’: + arity: 0 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: + named item ‘$fOrdNatural’ + named item ‘(<=)’ + object ‘v1_@name_suffix@’: + arity: 1 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: <none> + object ‘pap_@name_suffix@’: + arity: 3 + literals: <none> + used items: <none> + named item ‘(.)’ + named item ‘takeWhile’ + object ‘isPrime_primes_sat_@name_suffix@’: + arity: 1 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: + object ‘v_@name_suffix@’: + arity: 0 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: object ‘pap_@name_suffix@’: - arity: 3 + arity: 2 literals: <none> - used items: <none> - named item ‘(.)’ - named item ‘takeWhile’ - object ‘isPrime_sat_@name_suffix@’: - arity: 1 + used items: + named item ‘$fIntegralNatural’ + named item ‘divides’ + object ‘v1_@name_suffix@’: + arity: 1 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: <none> + object ‘pap_@name_suffix@’: + arity: 3 + literals: <none> + used items: <none> + named item ‘$fFoldableList’ + named item ‘any’ + named item ‘not’ + object ‘primes_sat_@name_suffix@’: + arity: 1 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: + object ‘primes_sat_@name_suffix@’: + arity: 0 literals: label ‘_hpc_tickboxes_Example_hpc’ used items: - object ‘v_@name_suffix@’: + object ‘primes_sat_@name_suffix@’: arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ + literals: + label ‘_hpc_tickboxes_Example_hpc’ + word 3 + info table of ‘IS’ used items: - object ‘pap_@name_suffix@’: - arity: 2 - literals: <none> - used items: - named item ‘$fIntegralNatural’ - named item ‘divides’ - object ‘v1_@name_suffix@’: - arity: 1 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: <none> - object ‘pap_@name_suffix@’: - arity: 3 - literals: <none> - used items: <none> - named item ‘$fFoldableList’ - named item ‘any’ - named item ‘not’ - object ‘primes’: - arity: 0 - literals: - label ‘_hpc_tickboxes_Example_hpc’ - info table of ‘(:)’ - used items: - named item ‘primes2_@name_suffix@’ - named item ‘primes1_@name_suffix@’ - object ‘primes1_@name_suffix@’: - arity: 0 - literals: - label ‘_hpc_tickboxes_Example_hpc’ - word 2 - info table of ‘IS’ - used items: - named item ‘$fNumNatural’ - named item ‘fromInteger’ + named item ‘$fNumNatural’ + named item ‘fromInteger’ + named item ‘$fEnumNatural’ + named item ‘enumFrom’ + object ‘primes_sat_@name_suffix@’: + arity: 1 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: <none> + named item ‘filter’ + object ‘primes_sat_@name_suffix@’: + arity: 0 + literals: + label ‘_hpc_tickboxes_Example_hpc’ + word 2 + info table of ‘IS’ + used items: + named item ‘$fNumNatural’ + named item ‘fromInteger’ object ‘fibonaccisPtr’: arity: 0 literals: @@ -245,63 +243,59 @@ objects: arity: 0 literals: label ‘_hpc_tickboxes_Example_hpc’ used items: named item ‘fibonaccis’ - object ‘positiveFibonaccis1_@name_suffix@’: + object ‘fibonaccis’: arity: 0 literals: label ‘_hpc_tickboxes_Example_hpc’ info table of ‘(:)’ used items: - named item ‘positiveFibonaccis2_@name_suffix@’ - named item ‘positiveFibonaccis_@name_suffix@’ - object ‘positiveFibonaccis2_@name_suffix@’: - arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: - object ‘positiveFibonaccis2_sat_@name_suffix@’: - arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: named item ‘positiveFibonaccis1_@name_suffix@’ - object ‘positiveFibonaccis2_sat_@name_suffix@’: - arity: 0 + object ‘positiveFibonaccis_@name_suffix@’: + arity: 1 + literals: + label ‘_hpc_tickboxes_Example_hpc’ + info table of ‘(:)’ + used items: + object ‘positiveFibonaccis_fibonaccis_sat_@name_suffix@’: + arity: 1 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: + object ‘positiveFibonaccis_fibonaccis_sat_@name_suffix@’: + arity: 1 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: <none> + object ‘positiveFibonaccis_fibonaccis_sat_@name_suffix@’: + arity: 0 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: named item ‘fibonaccis’ + object ‘positiveFibonaccis_fibonaccis_sat_@name_suffix@’: + arity: 0 + literals: label ‘_hpc_tickboxes_Example_hpc’ + used items: + named item ‘$fNumNatural’ + named item ‘(+)’ + named item ‘zipWith’ + object ‘positiveFibonaccis_fibonaccis_sat_@name_suffix@’: + arity: 0 + literals: + label ‘_hpc_tickboxes_Example_hpc’ + word 1 + info table of ‘IS’ + used items: + named item ‘$fNumNatural’ + named item ‘fromInteger’ + object ‘fibonaccis_sat_@name_suffix@’: + arity: 1 literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: named item ‘fibonaccis’ - object ‘positiveFibonaccis2_sat_@name_suffix@’: + used items: <none> + object ‘fibonaccis_sat_@name_suffix@’: arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ + literals: + label ‘_hpc_tickboxes_Example_hpc’ + word 0 + info table of ‘IS’ used items: named item ‘$fNumNatural’ - named item ‘(+)’ - named item ‘zipWith’ - object ‘fibonaccis’: - arity: 0 - literals: - label ‘_hpc_tickboxes_Example_hpc’ - info table of ‘(:)’ - used items: - named item ‘fibonaccis2_@name_suffix@’ - named item ‘fibonaccis1_@name_suffix@’ - object ‘fibonaccis2_@name_suffix@’: - arity: 0 - literals: label ‘_hpc_tickboxes_Example_hpc’ - used items: named item ‘positiveFibonaccis1_@name_suffix@’ - object ‘positiveFibonaccis_@name_suffix@’: - arity: 0 - literals: - label ‘_hpc_tickboxes_Example_hpc’ - word 1 - info table of ‘IS’ - used items: - named item ‘$fNumNatural’ - named item ‘fromInteger’ - object ‘fibonaccis1_@name_suffix@’: - arity: 0 - literals: - label ‘_hpc_tickboxes_Example_hpc’ - word 0 - info table of ‘IS’ - used items: - named item ‘$fNumNatural’ - named item ‘fromInteger’ + named item ‘fromInteger’ object ‘$dTypeable2_@name_suffix@’: arity: 0 literals: <none> ===================================== testsuite/tests/simplCore/should_compile/T26903.stderr ===================================== @@ -1,35 +1,42 @@ ==================== Tidy Core ==================== Result size of Tidy Core - = {terms: 127, types: 130, coercions: 48, joins: 0/0} + = {terms: 127, types: 130, coercions: 24, joins: 0/0} $dmop - = (\ @a _ $dOrd xs ys -> - case $fOrdList_$ccompare $dOrd xs ys of { - __DEFAULT -> - reverse1 (reverse1 (reverse1 (reverse1 (++ xs ys) []) []) []) []; - GT -> reverse1 (reverse1 (reverse1 (reverse xs) []) []) [] - }) - `cast` <Co:20> :: ... + = \ @a $dC $dOrd xs ys -> + case $fOrdList_$ccompare $dOrd xs ys of { + __DEFAULT -> + (reverse1 (reverse1 (reverse1 (reverse1 (++ xs ys) []) []) []) []) + `cast` <Co:3>; + GT -> + (reverse1 (reverse1 (reverse1 (reverse xs) []) []) []) + `cast` <Co:3> + } $fCInt_$cop - = (\ xs ys -> - case $fOrdList_$s$ccompare xs ys of { - __DEFAULT -> - reverse1 (reverse1 (reverse1 (reverse1 (++ xs ys) []) []) []) []; - GT -> reverse1 (reverse1 (reverse1 (reverse xs) []) []) [] - }) - `cast` <Co:11> :: ... + = \ xs ys -> + case $fOrdList_$s$ccompare xs ys of { + __DEFAULT -> + (reverse1 (reverse1 (reverse1 (reverse1 (++ xs ys) []) []) []) []) + `cast` <Co:3>; + GT -> + (reverse1 (reverse1 (reverse1 (reverse xs) []) []) []) + `cast` <Co:3> + } $fCInt1 = \ xs ys -> case $fOrdList_$s$ccompare xs ys of { __DEFAULT -> - reverse1 (reverse1 (reverse1 (reverse1 (++ xs ys) []) []) []) []; - GT -> reverse1 (reverse1 (reverse1 (reverse xs) []) []) [] + (reverse1 (reverse1 (reverse1 (reverse1 (++ xs ys) []) []) []) []) + `cast` <Co:3>; + GT -> + (reverse1 (reverse1 (reverse1 (reverse xs) []) []) []) + `cast` <Co:3> } -$fCInt = C:C ($fCInt1 `cast` <Co:11> :: ...) +$fCInt = C:C $fCInt1 test4 = reverse1 [] [] @@ -44,8 +51,8 @@ test case $fOrdList_$s$ccompare [] xs of { __DEFAULT -> (reverse1 (reverse1 (reverse1 (reverse1 (++ [] xs) []) []) []) []) - `cast` <Co:3> :: ...; - GT -> test1 `cast` <Co:3> :: ... + `cast` <Co:3>; + GT -> test1 `cast` <Co:3> } ===================================== testsuite/tests/simplCore/should_compile/T27737a.hs ===================================== @@ -0,0 +1,23 @@ +{-# LANGUAGE NoMonoLocalBinds, MagicHash, UnboxedTuples #-} + +-- One of several regression tests arising from the work on #27737. +-- +-- The Simplifier returns a single-alternative case as a case-float +-- (FloatCase). Here the local binding +-- g = /\a. case addIntC# x y of (# r, _ #) -> ([], I# r) +-- is lazy, non-recursive and has a type lambda but no value lambda, so +-- simplLazyBind strips off the /\a and simplifies the body. The case +-- becomes a FloatCase; since addIntC# is ok-for-speculation, the float is +-- FltOkSpec, which doFloatFromRhs allows out of a nested lazy binding. +-- But then the floats must be abstracted over `a` (abstractFloats), which +-- can only handle let-floats: at one stage the compiler panicked +-- with "letFloatBinds". + +module T27737a where + +import GHC.Exts + +f :: Int -> Int -> ([Bool], [Char], Int) +f (I# x) (I# y) = let g = case addIntC# x y of (# r, _ #) -> ([], I# r) + -- g :: forall a. ([a], Int) + in (fst g, fst g, snd g) ===================================== testsuite/tests/simplCore/should_compile/T27910.hs ===================================== @@ -0,0 +1,17 @@ +{-# LANGUAGE UnboxedTuples, MagicHash #-} +module T27910 where +import GHC.Exts + +k1 :: (# Int, Bool #) -> (# Int, Bool #) -> Int +{-# NOINLINE k1 #-} +k1 _ _ = 3 + +k2 :: (# Int#, Int# #) -> (# Int#, Int# #) -> Int +{-# NOINLINE k2 #-} +k2 _ _ = 3 + +lifted :: Int -> Bool -> Int +lifted x y = case (# x, y #) of r -> k1 r r + +unlifted :: Int# -> Int# -> Int +unlifted x y = case (# x, y #) of r -> k2 r r ===================================== testsuite/tests/simplCore/should_compile/T27910.stderr ===================================== @@ -0,0 +1,49 @@ + +==================== FloatOut stats: ==================== +2 Lets floated to top level; 0 Lets floated elsewhere; from 4 Lambda groups + + + +==================== FloatOut stats: ==================== +4 Lets floated to top level; 0 Lets floated elsewhere; from 6 Lambda groups + + + +==================== Grand total simplifier statistics ==================== +Total ticks: 30 + +8 PreInlineUnconditionally + 1 ds + 1 ds + 1 ds + 1 ds + 1 ds + 1 ds + 1 ds + 1 ds +2 PostInlineUnconditionally + 1 r + 1 r +4 UnfoldingDone + 2 GHC.Internal.Prim.void# + 1 T27910.k1 + 1 T27910.k2 +8 BetaReduction + 1 ds + 1 ds + 1 ds + 1 ds + 1 ds + 1 ds + 1 ds + 1 ds +4 KnownBranch + 2 wild + 1 ww + 1 ww +4 CaseElim + 2 ww + 2 ww +9 SimplifierDone 9 + + ===================================== testsuite/tests/simplCore/should_compile/all.T ===================================== @@ -627,5 +627,8 @@ test('T27749', compile, ['-O -g3 -ddump-simpl -dsuppress-uniques']) test('T27629', only_ways(['optasm']), makefile_test, ['T27629']) - test('T27936', normal, compile, ['']) + +# A case-float reaching abstractFloats used to make the Simplifier panic +test('T27737a', normal, compile, ['-O']) +test('T27910', grep_errmsg(r'KnownBranch'), compile, ['-O -dno-typeable-binds -ddump-simpl-stats -dsuppress-uniques']) View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/73392ece21336a1f86181d302fe6c93... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/compare/73392ece21336a1f86181d302fe6c93... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help
participants (1)
-
Simon Peyton Jones (@simonpj)