#11731: Demand analysis: Thunk wrongly determined single-entry -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): {{{ Entries Alloc Alloc'd #Alloc Single Multiple Non- void Arguments STG Name 4096 0 65536 2048 0 2048 0 sat_s2vw{v} (main@main:GamtebMain) (thk,se) in r2uq }}} The relevant `-ddump-prep` code is this: {{{ let { sat_s2vw [Occ=Once, Dmd=] :: GamtebType.Random [LclId, Str=DmdType] = \s srt:SRT:[r4K :-> Utils.$wgenRand] [] case Utils.$wgenRand w_s2ux of _ [Occ=Dead] { (#,#) ww5_s2vu [Occ=Once] _ [Occ=Dead] -> ww5_s2vu; }; } in TransPort.$wtransPort lvl2_r2ut lvl2_r2ut lvl2_r2ut lvl2_r2ut lvl1_r2us lvl2_r2ut lvl1_r2us w1_s2uz ww2_s2vk lvl_r2ur sat_s2vw ww17_s2vn ww19_s2vp ww22_s2vs; }}} The relevant code for `$wtransPort` ist {{{ TransPort.$wtransPort [InlPrag=[0], Occ=LoopBreaker] :: GamtebType.Coord -> GamtebType.Coord -> GamtebType.Coord -> GamtebType.Coord -> GamtebType.Coord -> GamtebType.Coord -> GamtebType.Weight -> GamtebType.Energy -> GamtebType.Indx -> GHC.Types.Int -> GamtebType.Random -> GamtebType.Prob -> GamtebType.Prob -> GHC.Prim.Double# -> (# [GamtebType.Result], [GamtebType.Stat] #) [GblId, Arity=14, Str=DmdType , Unf=OtherCon []] = \r srt:SRT:[r4K :-> Utils.$wgenRand, r5x :-> Compton.$wcompton, r5O :-> Pair.$wpair, r3Df :-> TransPort.$wtransPort, r3Dr :-> lvl11_r3Dr] [ww_s3Dy ww1_s3Dz ww2_s3DA ww3_s3DB ww4_s3DC ww5_s3DD ww6_s3DE ww7_s3DF ww8_s3DG ww9_s3DH ww10_s3DI ww11_s3DJ ww12_s3DK ww13_s3DL] case Utils.$wgenRand ww10_s3DI of _ [Occ=Dead] { (#,#) ww15_s3DN [Occ=Once!] ww16_s3DO -> }}} Note how the strictness signature say that the `Random` argument is used at most once (`1*U(U)`). The call to `$wgenRand` is indeed the only use of `ww10_s3DI`. So here is the code of `$wgenRand`: {{{ Utils.$wgenRand [InlPrag=[0]] :: GamtebType.Random -> (# GamtebType.Random, GamtebType.Random #) [GblId, Arity=1, Str=DmdType , Unf=OtherCon []] = \r srt:SRT:[015 :-> GHC.Integer.Type.timesInteger, 017 :-> GHC.Integer.Type.negateInteger, 01j :-> GHC.Integer.Type.divInteger, 01x :-> GHC.Integer.Type.shiftLInteger] [w_s3BX] let { sat_s3CT [Occ=Once] :: GamtebType.Random [LclId, Str=DmdType] = \u srt:SRT:[015 :-> GHC.Integer.Type.timesInteger, 017 :-> GHC.Integer.Type.negateInteger, 01j :-> GHC.Integer.Type.divInteger, 01x :-> GHC.Integer.Type.shiftLInteger] [] case w_s3BX of _ [Occ=Dead] { GHC.Types.D# y_s3Cs [Occ=Once] -> ... }; } in let { sat_s3Cq [Occ=Once] :: GamtebType.Random [LclId, Str=DmdType] = \u srt:SRT:[015 :-> GHC.Integer.Type.timesInteger, 017 :-> GHC.Integer.Type.negateInteger, 01j :-> GHC.Integer.Type.divInteger, 01x :-> GHC.Integer.Type.shiftLInteger] [] case w_s3BX of _ [Occ=Dead] { GHC.Types.D# y_s3BZ [Occ=Once] -> ... }; } in (#,#) [sat_s3Cq sat_s3CT]; }}} So `$wgenRand` may evaluate its argument more than once (as its strictness signature says). On what grounds does `$wtransPort` then claim the argument is used at most once? Now if the argument to `$wgenRand` were a complex expression, this would be valid reasoning, as it would be let-bound and then shared. But trivial expressions, when passed as arguments, are _not_ shared at this point, so the information that the argument may be used multiple times should be propagated out. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Good point! For example, if the demand analyser saw {{{ let y = factorial v in let x = y in x + x }}} I think it'd conclude that `x` was demanded many times, but `y` was demanded only once. (Which is correct). But if we substitute for `x`, and then use call-by-name for `y` we'll evaluate the `factorial` twice. Urk. It seems to affect bindings like {{{ x = y -- Or perhaps y |> gamma etc; exprIsTrivial anyway }}} where * The demand signature on `x` is '''not''' marked "used-once" * The demand signature on `y` '''is''' marked "used-once" Under these circumstances, the binding for `x` is serving a useful role, to memo-ise the computation of `y`. Perhaps we should simply refrain from inlining `x` under these circumstances, leaving the trivial let in place. The fix would be in `postInlineUnonditionally`, `postInlineUnonditionally`, and `callSiteInline`. Would you like to try that? I think it'd fix this bug. But it would then be important to know how many trivial lets were thereby retained. Perhaps not many. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): I’ve created a test case for this; if you run `T11731`, it will print `Evaluated` twice.

Would you like to try that? I think it'd fix this bug.

I’m not sure I like that path. This means that the strictness signatures will now not only ''describe'' the actual semantics of the code, but rather ''affect'' it. We would lose the invariant that the semantics of the program does not change if we remove all strictness signatures. Feels wrong to me. But nevertheless, I see if that indeed fixes the problem. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Humph. I was thinking that if a function has a particular strictness signature we can't change it. Certainly we can't change the strictness signature for an imported function. BUT we CAN change the strictness signatures of local functions and actually those are the ones that matter, because their sharing properties may worsen, as above. Indeed we already have the idea of running the demand analyser just before code generation: `-flate-dmd-anal`. (Main motivation: discover used-once thunks that weren't previously used-once.) Does using `-flate-dmd-anal` fix the problem? It may not becuase there is a simplifer run afterwards; but cleraly this bug only shows up rarely anyway, so running it late might actually fix it Thinking about it * ''Until'' code generation, the used-once info is ignored; only one- shot-call info is used * ''During'' code generation, the used-once info is used; and the one- shot-call info is ignored. So perhaps * We should not even ''generate'' used-once info in the main run of the demand analyser, since it is so easily invalidated. * In the run of the simplifier after late demand analysis we should be careful not to eliminate the dangerous lets. I tried the test program with `-O`; but it only prints `"Evaluated"` once. So, strangely, I can't reproduce the bug. What exact commands did you use? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata):

I tried the test program with -O; but it only prints "Evaluated" once. So, strangely, I can't reproduce the bug. What exact commands did you use?

Well spotted! I ran with `-O2`, and indeed, it does not happen with `-O`, but with `-O -fspec-constr`. Nothing deep here, it’s just that constructor specialization is required in this particular example to massage the code into the shape we want.

Does using -flate-dmd-anal fix the problem?

Indeed it does. It recalculates the demand signature correctly, and will share the `shareMeThunk`. But after `-flate-dmd-anal`, there is another round of worker-wrapper and simplifier. So the principle, the problem could occur again. I would prefer to take a step back and think about what, at the level of Core, the semantics of {{{ let x = y in foo x }}} should be, independent of any possible annotations. Here a digression that follows that train of thought: If this code should indeed guarantee that `y` is evaluated at most once, then rewriting to `foo y` is in general wrong (and may only be justified if we ''know'' that `foo` evaluates its argument only once – this is more conservative than not doing the substitution if we happen to know that it can go wrong). Alternatively, we declare the semantics that a `let` with a trivial RHS should ''not'' (guarantee) sharin (just like a trivial function argument does not indicate sharing!). But then the problem was one step earlier where GHC replaced {{{ let x = case (y,z) of (y,z) -> y in foo x }}} with the trivial let above. Maybe it should have changed it to something like {{{ let x = share y in foo x }}} where `share` is a magic id that is semantically the identity, but prevents the `let` from being trivial. Now `x` can even be safely inlined then `foo (share y)`. The simplifier could know some rules about when occurrences of `share` can be removed (e.g. when the argument is not trivial any more, or when it is itself known to be shared). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Well, it all amounts to the same thing: * Introduce `share` * Use `let` to create sharing The rules for eliminating `share` would be the same as the rules governing inlining of trivial lets. Which is preferable is largely an engineering choice. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Joachim Breitner ): In [changeset:"80d4fdf0756ce7edc534b9277d7c6c63c8ceb501/ghc" 80d4fdf/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="80d4fdf0756ce7edc534b9277d7c6c63c8ceb501" SpecConstr: Transport strictness data to specialization’s argument’s binders This is a result of the discussion in ticket:11731#comment:9. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): I think I nailed it. With the above change, demand information becomes something that we should try to keep hold on. But we don’t: {{{#!hs simplExprF1 env expr@(Lam {}) cont = simplLam env zapped_bndrs body cont -- The main issue here is under-saturated lambdas -- (\x1. \x2. e) arg1 -- Here x1 might have "occurs-once" occ-info, because occ-info -- is computed assuming that a group of lambdas is applied -- all at once. If there are too few args, we must zap the -- occ-info, UNLESS the remaining binders are one-shot where (bndrs, body) = collectBinders expr zapped_bndrs | need_to_zap = map zap bndrs | otherwise = bndrs need_to_zap = any zappable_bndr (drop n_args bndrs) n_args = countArgs cont -- NB: countArgs counts all the args (incl type args) -- and likewise drop counts all binders (incl type lambdas) zappable_bndr b = isId b && not (isOneShotBndr b) zap b | isTyVar b = b | otherwise = zapLamIdInfo b }}} Here, we would remove the demand information from the parameters of a top- level function (unless all of them happen to be one-shot-binders). I don’t fully understand the comment here. Does "occurs-once" refer to occurence information only? But `zapLamInfo` in `IdInfo` also removes Demand information...sometimes. This looks delicate. Why does demand information (which is calculated from the body of the lamda, not how it is being used) need to be zapped in `zapLamInfo` at all? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): I agreed comment:18 is odd, but first why does "demand information become something we should try to keep hold on"? What, specifically, goes wrong? The reasoning here is as follows. Consider {{{ let f = \xy. x+y in ...map (f expensive).... }}} Now, in `f`'s definition `x` and `y` are both marked * `OneOcc not-in-lambda` (syntactically occurring once not inside a lambda; added by the occurrence analyser) * Demanded (added by the demand analyser) These annotations assume that `f` is fully applied But when we inline `f` at this partial application site, we get {{{ ...map (let x = expensive in \y. x+y)... }}} and now `x` jolly well shouldn't be marked as occurring not inside a lambda; nor should it be marked as strictly demanded. Hence the `zapLamIdInfo`. What I had forgotten (and has somehow never arisen) is that this ''also'' happens at `f` definition site. Maybe it doesn't matter. Back to the quesion at the beginning: why does it matter? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Well that's extremely annoying. I'd typed a long comment in, but Trac has binned it somehow. Sigh. I have concluded that the approach in comment:16 (based on my suggestion in comment:5) is too fragile. * As Ben points out there are other `exprIsTrivial` variants. * We'd probably need to do similar surgery for `exprIsCheap`, lest we change sharing by floating something like {{{ x = case v of (p,q) -> p }}} out, aand then discover we know that `v` is a pair `(x,y)`, so it all turns into `x=y` in short, I'm just not confident that we can be sure to maintain this single-entry property. Moreover, ''these restrictions cripple otherwise-useful transformations''. For example, we might end up with a function that claims to evaluate its argument at most once, but to maintain that claim looks like `\x. let y = x in ...body...`. So now two thunks get allocated for every call, one single entry, and one indirection-thunk that does the update. This is bad bad. Much better, I think, to do this: * Allow unrestricted transformation, as now, with no guarantees about maintaining single-entry-nes. Indeed maybe the demand analyser should not even record signle-entry-ness in the Ids, since it is so fragile. * Just before code generation, perhaps even after `CorePrep`, do demand analysis ''but not worker-wrapper''. So all it does is pin on the single- entry-ness to each thunk, just before it is needed in `CoreToStg`. No simplifier pass afterwards to mess it up! That should nail it in a robust way. Note that this final demand-analysis is there solely to attach single- entry-ness. We might still want to do "late demand analysis" with `-O2`, as now, complete with worker/wrapper and subsequent simplification pass, to exploit the usual w/w benefits of strictness exposed at later stages of the pipeline. That becomes an independent choice. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): * The awkwardness of not recording top-level 1* info is that we'd need a demand-analyser flag to tell it whether to do so or not. * I've just realised that this final sweep (dmd anal only) must be just before `CoreTidy`. Reason: currently anyway, `CoreTidy` establishes the exported strictness signatures. We do want to export `f` with a "I use my arg at most once" `1*` annotation. So we want to pin in reliable info just before we freeze it for export, and then not invalidate it. One thing I have longed to do for some time is to get CAF info from the STG form, and combine that CAF info into the `ModIface` bindings. Currently we ''predict'' what it'll be at `CoreTidy`, which is fragile. Maybe the same holds for strictness/usage info. * `OneShot` annotations on lambda binders are a different matter. They say something about the use of the ''function'', not about the use of the binder in the function body. Can a `OneShot` annotation go wrong? Yes if we call that function twice instead of once. But GHC really is pretty paranoid about duplicating arbitrary amounts of work so we are at least much safer here. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Let's be careful to distinguish three kinds of `IdInfo`, all pinned on an `Id`: * `demandInfo`: says how the `Id` is used (demanded) by its scope. * `strictnessInfo`: describes the demand transformer for the `Id`; it tnansforms a demand on the `Id` to a demand on its arguments and free variables. * `oneShotInfo`: for lambda-bound `Id`s only, says whether the function is called at most once. (It says nothing about how the `Id` is used in the body of the lambda.) I think we have decided (#11770) that * only the demand analyser sets `demandInfo` and `strictnessInfo` * only the occurrence analyser sets `oneShotInfo`. The `demandInfo` on an `Id` includes `1*` usage info, which is fragile so perhaps we should erase it. The `strictnessInfo` on an `Id` also contains `1*` usage info, e.g about the function arguments. That too is fragile to transformations of the function body, so perhaps we should erase it too. I've just realised that a convenient place to erase it might be the worker/wrapper pass. So then we'd have * the demand analyser sets `demandInfo` and `strictnessInfo` * the worker-wrapper pass erases 1* info from `demandInfo` and `strictnessInfo` * the occurrence analyser sets `oneShotInfo` -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:26 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):

* It would no longer get erased with `-fstrictness -fno-worker- wrapper`. Although we might argue that this is not a supported configuration.

I'm very dubious about `-no-worker-wrapper`. Maybe we should kill it off.

* Since the worker-wrapper pass happens before the next occurrence analyzer (does it?), the occurrence analyzer no longer sees the `1*` `demandInfo` and thus cannot set the `oneShotInfo`.

False. The occurrence analyser uses call-once `C1` info (the `Count` argument to `UCall`). It does not use the demanded-once `1*` info (the `Count` field to `Use`). It is the latter that we are going to erase, NOT the former.

Why not do it in the occurrence analyser?

By "it" I guess you mean the erasure? Because the occurrence analyser runs repeatedly; no sense in repeatedly erasing info that is already erased. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:28 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Meanwhile, there is a separate issue in comment:20. It seems that for any un-saturated lambda, we nuke (a) the `occInfo` on the binders (fair enough; the next run of the occurrence analyser will regenerate it), and (b) the `demandInfo` on the binders. The reasoning is explained in comment:20. But (b) is permanent; it won't be re-generated until the next run of the demand analyser. And, worse, it applies to function definitions {{{ f = \xy . x+y }}} Here `x` and `y` will be marked as strictly demanded, but that info will get stripped after the first run of the simplifier. Try it on {{{ f :: [Int] -> [Int] -> Int f x y = head x + head y }}} After the demand analyser we have {{{ f = \ (x_amY [Dmd=] :: [Int]) (y_amZ [Dmd=] :: [Int]) -> ... }}} but after the first run of the simplifier we get {{{ f = \ (x_amY :: [Int]) (y_amZ :: [Int]) -> ... }}} (`f` itself still has a strictness signature that says it is strict in both args.) Does this matter? Well, the main reason is that if `f` is inlined, we'd like to get a strict `let`. And now we won't. Happily I think it is easily fixed. The key thing is that when doing beta-reduction, which effectively does `(\x.e) b` into `let x=b in e`, we must kill off x's demand/occurrence info if the lambda is not saturated. So, idea, in `Simplify.hs`: * Give an extra `Bool` to `simplLam` indictating "saturated". * Compute (value) saturation in the `simplExprF1 env expr@(Lam {}) cont`, before calling `simpLam`, but do no zapping. * In `simplLam`, in the beta-reduction case, {{{ simplLam env (bndr:bndrs) body (ApplyToVal { sc_arg = arg, sc_env = arg_se , sc_cont = cont }) = do { tick (BetaReduction bndr) ; simplNonRecE env' (zap_unfolding bndr) (arg, arg_se) (bndrs, body) cont } }}} do the binder-zapping right there, if "saturated" is not true. (That neatly puts it with the unfolding-zapping code.) Now the non-beta-reduced lambdas won't be zapped, which is right. Would you like to try that? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:30 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata):

Sounds like a plan. I am currently checking the effect of a very late, non-ww, demand analyzer.

It does fix the bug here (both as observed in nofib, and the test case I produced here). The numbers for thunks are the same as with `-flate-dmd- anal`, though. I wonder: What else (besides the code-generator) uses the used-once information in a critical way? In particular, `isUsedOnce` is *only* mentioned in `CoreToStg`. Should we even bother removing the information then? Anyways, I implemented it (wip/T11731 for now). I did put the code into DmdAnal.hs, after all, that’s where it belongs, and added a boolean flag to `CoreDoStrictness`. A full validation is running. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:32 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2064 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Crumbs. I see that you are doing an entire pass of the program to erase this info. That does seem like overkill, to remove info that is never examined anyway. I'd much rather not do this. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:34 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):

One clear implementation would have been to adjust the calls to `setIdDemandInfo` in `DmdAnal`, but that would go wrong because of the Cunning Plan with fixed-point iteration, where later iterations use the existing annotations.

Well imagine that the demand analyser simply NEVER attributed single-use to anything; e.g. `mkOnceUsedDmd` returned `Use Many ...`. Then we'd get no useful use-once info from the analyser so we wouldn't need to erase it. Not sure if it's worth it. There are other occurrence of the string `Use One` in `Demand`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:36 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Replying to [comment:37 nomeata]:

Isn’t the information about single-use demand used internally to determine that certain functions are called once?

No, I don't think so. I'm 85% certain! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:38 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Trouble is that there ''are'' other places where `Use One` shows up in `Demand.hs`, and we'd need to look at all of them too. But I think this alone will kill off a lot. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:40 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Answers via skype talk: * No, should not be there. * Yes * WorkWrap (`tryWW`) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:42 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Wow, that's quite remarkable. I ''hope'' that the ticky numbers will show why cichelli and mandel2 are improving . Since this is from the "final run" thing, it must presumably be from increasing the number of single entry thunks we find, right? And that should show up in the ticky numbers you gather. It's curious that other compiler benchmarks don't also worsen. Maybe you are right, but I rather doubt that 5% of compile time is the cost of single run of the demand analyser, unless it's a very pathological program with deeply nested letrecs. Again, it'd be good to try this with a ''stage1'' compiler to isolate the effects. But we'd expect this to speed up a stage2 compiler, so the effect would be more pronounced with stage1. In HEAD Ben has added a bit more time-tracking to passes which may help. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:44 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Yes that's good. For the paper we can talk about the find dmd-anal pass, but in showing the payoff from single-entry etc we will have to compare like with like; i.e. not claim the big wins here as wins for single-entry- ness. We'd also flirted with `-flate-dmd-anal` (complete with worker/wrapper) which could show greater benefits still (from the w/w). I hypothesise that if we did `-flate-dmd-anal` then the final dmd-anal pass would buy very little except the correct single-entry info. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:46 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Joachim Breitner ): In [changeset:"f4fd98c717a7f68d76a3054021b3be65d1ebad82/ghc" f4fd98c/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="f4fd98c717a7f68d76a3054021b3be65d1ebad82" Add a final demand analyzer run right before TidyCore in order to have precise used-once information in the exported strictness signatures, as well as precise used-once information on thunks. This avoids the bad effects of #11731. The subsequent worker-wrapper pass is responsible for removing the demand environment part of the strictness signature. It does not run after the final demand analyzer pass, so remove this also in CoreTidy. The subsequent worker-wrapper pass is also responsible for removing used-once-information from the demands and strictness signatures, as these might not be preserved by the simplifier. This is _not_ done by CoreTidy, because we _do_ want this information, as produced by the last round of the demand analyzer, to be available to the code generator. Differential Revision: https://phabricator.haskell.org/D2073 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:48 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Changes (by nomeata): * status: patch => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:50 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11731: Simplifier: Inlining trivial let can lose sharing -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2073 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: merge => closed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11731#comment:53 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler