[GHC] #14844: SpecConstr also non-recursive function
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- In order to fix the regressions introduced by loopification (#14068), we probably need to get !SpecConstr also do something about non-recursive functions. In a first iteration, we might want to enable it for non-recursive functions straight-away, and see if it fixes the regressions introduced by Loopification. But if this turns out to be too slow/too expensive, we should try specializing non-recursive ''local'' functions ''if there is only one call-patterns''. That ought to be a straight win in all cases anyways. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => SpecConstr -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr 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 sgraf): See also my closing thoughts in Trac:855#comment:12. TLDR; Integrate SpecConstr into the simplifier as a fallback for when the inliner bails out. May even apply to non-recursive bindings, at least when there's only one call pattern. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr 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): @sgraf, are you actively working on !SpecConstr, and if so, is your patch going to help with this (specconstring non-recursive functions)? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr 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 have been staring at the !SpecConstr code quite a bit now (which is pretty dense, I must say), and am no longer able to say with certainty that !SpecConstr only works on recursive functions. In fact, it seems that `Note [Local let bindings]` implies local non-recursive lets are being specialized! (despite `Note [Good arguments]` claiming it only works for self-recursive functions… It seems that specialization for non-recursive functions was added in changeset:99f41975ae61fc919638aa389199b32742332eff by Simon PJ (maybe not all notes were updated to reflect this change)? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr 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 stared some more at the code, and learned: * Currently, !SpecConstr does specialize local non-recursive functions, but not top-level non-recursive functions. Comment in the source code about that: “Oddly, we don't seem to specialise top-level non-rec functions”. This can be fixed in `scTopBind`. * Together with loopification, SpecConstr only specialized everything as before if it is run twice, with a simplification in between. Otherwise, it refuses to specialize the outer non-recursive function because it does not see that its parameters are being scrutinized. I hope this can somehow be fixed in `SpecConstr`, so that it anticipates the state after simplifications. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function
-------------------------------------+-------------------------------------
Reporter: nomeata | Owner: (none)
Type: task | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 8.5
Resolution: | Keywords: SpecConstr
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):
And here some details on the second point. After the first run of
SpecConstr, we have somthing like this
{{{
$w$lf_s6DU [InlPrag=NOUSERINLINE[0]]
:: Double -> Double -> GHC.Prim.Int# -> (# Double, Double #)
[LclId, Arity=3, Str=
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr 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 distilled this example to show the effect {{{ module T14844Example (bar1, bar2) where large x = x {-# NOINLINE large #-} foo :: Int -> (a -> b -> Bool) -> (a,b) -> Bool foo 0 _ _ = False foo s f t = l s' t where l 0 t = False l 1 t = case t of (x,y) -> f x y l n (x,y) = l (n-1) (x,y) s' = -- To prevent inlining large $ large $ large $ large $ large $ large $ large $ large $ large $ large $ large $ large $ large $ large $ large $ large $ s bar1 :: Int -> (a -> b -> Bool) -> a -> b -> Bool bar1 s f x y = foo s f (x,y) bar2 :: Int -> (a -> b -> Bool) -> a -> b -> Bool bar2 s f x y = foo (s + 1) f (x,y) }}} This needs to rounds of !SpecConstr to specialize `foo` for the `(x,y)` call pattern; in the first round, `l` is specialized, then the (then non- recursive `l`) gets inlined into `foo`, then `foo` gets specialized. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr 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): So here is an idea that might help here, and that I want to run past people who know !SpecConstr well (is that anyone else but SPJ at this point?). Status quo: `l` gets specialized, because of the two call patterns `s' t0` and `(s-1) (x,y)`, the second one is interesting *and* its second argument gets scrutinized (the `scu_occs` field reports `ScrutOcc` for `t`). But `foo` does not get specialized: It does have an interesting call pattern, but `scu_occs` reports `UnkOcc`, because `foo`’s parameters are just passed to `t`. But: When we decide to !SpecConstr `l`, we know that one of the calls to to `l` is of the shape `s' t0`. This is a boring call, and we do not create a specialization for it. But we create a specialization for `l` using the the other call pattern. This means we know that it would be beneficial if `t0` were a constructor. So can we, at this point, decide to include `t0 ↦ ScrutOcc` in `scu_occs`? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr 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 sgraf): I'm currently on vacation, so I'm afraid I won't be able to write much code. I'm not doing anything targeting non-recursive functions, that in itself should be pretty much independent. But given that you seem to have stumbled over the same "phase dependency" problems, here are some notes: Re: "anticipates the state after simplifications": That's what I figured out, too, and becomes much more crucial once you add lambdas, which does beta-reduction and makes seeing which arguments are scrutinized a little harder. Currently, SpecConstr only gets its `ArgOcc`s (which is a criterion for how deep it's worth to specialise in absence of forced `SPEC`) only considers the original RHS. Specialised RHS' Occs are never considered, although /calls/ from their RHSs are considered. My plan forward is to revise the fix-pointing scheme in a way that we can translate occurences in specialised RHSs back to occurences on the original RHS' arguments. In the case of lambdas, this also involves unification of call patterns with bound variables, which is rather nasty and what I've been fiddling with the last weeks. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14844: SpecConstr also non-recursive function -------------------------------------+------------------------------------- Reporter: nomeata | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.5 Resolution: | Keywords: SpecConstr Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * cc: sgraf (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14844#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC