[GHC] #13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Runtime Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: #13014 Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- [https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts... #specialize-inline The user's guide] for `SPECIALIZE INLINE` states it will do a "type-based unrolling" of a recursive function over GADTs. It gives an example, which I've munged a bit to simplify and listed here. {{{#!hs {-# Language GADTs #-} module C where data Arr e where ArrInt :: !Int -> Arr Int ArrPair :: Arr e1 -> Arr e2 -> Arr (e1, e2) (!:) :: Arr e -> Int -> e {-# SPECIALISE INLINE (!:) :: Arr Int -> Int -> Int #-} {-# SPECIALISE INLINE (!:) :: Arr (a, b) -> Int -> (a, b) #-} (ArrInt ba) !: i = ba * i (ArrPair a1 a2) !: i = (a1 !: i, a2 !: i) }}} {{{#!hs module D where import C example = ArrPair (ArrInt 2) (ArrInt 3) !: 5 }}} The specialize rule for pairs fires, but it does not get inlined. This is because the specialization for pairs is marked as a loopbreaker. This behavior contradicts the text from the users guide, emphasis mine: Here, `(!:)` is a recursive function that indexes arrays of type `Arr e`. Consider a call to `(!:)` at type `(Int,Int)`. The second specialisation will fire, ''and the specialised function will be inlined''. It has two calls to `(!:)`, both at type `Int`. Both these calls fire the first specialisation, whose body is also inlined. The result is a type-based unrolling of the indexing function. If I move the `SPECIALIZE INLINE` pragma to the downstream module, then it is not marked as a loopbreaker and we see the expected type-based unrolling. Two possible ways to resolve this ticket: * `SPECIALIZE INLINE` should always achieve supercompilation even if declared in the defining module; the specialization should not be marked as a loopbreaker. * The docs should be updated to say the pragma must be declared in a separate module. I suggest the former. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by mpickering): * cc: mpickering (added) * keywords: => Inlining -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: dfeuer (added) Comment: This doesn't ''sound'' very complicated, but I can't seem to find the code where it's handled. Anyone have a hint? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Just for the heck of it, I decided to try translating this into class style: {{{#!hs class BangColon e where (!:) :: Arr e -> Int -> e instance BangColon Int where {-# SPECIALISE INLINE (!:) :: Arr Int -> Int -> Int #-} ArrInt ba !: i = ba * i instance (BangColon a, BangColon b) => BangColon (a, b) where {-# SPECIALISE INLINE (!:) :: (BangColon a, BangColon b) => Arr (a, b) -> Int -> (a, b) #-} ArrPair a1 a2 !: i = (a1 !: i, a2 !: i) }}} Written this way, the specializations inline as requested, producing {{{#!hs Dp.example2 :: Int [GblId, Caf=NoCafRefs, Str=m, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 20}] Dp.example2 = GHC.Types.I# 10# -- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0} Dp.example1 :: Int [GblId, Caf=NoCafRefs, Str=m, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 20}] Dp.example1 = GHC.Types.I# 15# -- RHS size: {terms: 3, types: 2, coercions: 0, joins: 0/0} example :: (Int, Int) [GblId, Caf=NoCafRefs, Str=m, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}] example = (Dp.example2, Dp.example1) }}} So the problem seems confined to the GADT function case. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): FYI, it looks like the GADT thing was actually mentioned in the original commit that implemented `SPECIALISE INLINE`: 958924a2b338aebbcc8a88ba2cab511517762a19. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by mpickering): It still isn't clear what is going on here but there seems to be some kind of interaction with `SpecConstr`. If you turn it off with `-fno-spec- constr` then the same module example doesn't get super compiled. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014, #10346 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by mpickering): * related: #13014 => #13014, #10346 Comment: And of course, the reason that it doesn't work across modules is that `SpecConstr` doesn't work across modules (see #10346). After this analysis, I understand operationally how the program is optimised but I don't understand how the pragma is meant to achieve the unrolling if it relies on `SpecConstr` to inline a loop breaker using a RULE. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by mpickering): * related: #13014, #10346 => #13014 Comment: In fact, removing the `SPECIALISE INLINE` pragmas then `SpecConstr` still super compiles the example (in the same module) so really this is a duplicate of #10346 ? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): mpickering, I don't think it's quite a duplicate. In particular, I believe we want `SPECIALIZE INLINE` to actually ''force'' the specialization, even if it makes a lot of code and even if it risks an infinite loop in the simplifier. The idea here seems pretty cool: it lets you get the guaranteed loop unrolling you'd get from the class-based definition I wrote above when the types are known, but falls back on recursion when they're not. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by mpickering): I discussed this on IRC with David briefly. {{{ mpickering> dfeuer: I don't think SPECIALISE INLINE ever worked like you are suggesting. I think it just works like SPECIALISE and then marks the specialisation with an INLINE pragma 10:07 PM <mpickering> I was under the impression that SpecConstr allowed you to force this unrolling to happen 10:08 PM <mpickering> The manual states that "and applies even if the function is recursive." 10:09 PM <mpickering> but I don't know what this means or how it works as there is no special check in the simplifier to inline specialisations arising from SPECIALISE INLINE pragmas 10:09 PM <dfeuer> mpickering: I'm just going off of the documentation that was added when SPECIALISE INLINE was. 10:09 PM <dfeuer> The only way I know to push really hard for SpecConstr is using that funky pseudo-argument. 10:10 PM <mpickering> there is another deprecated way 10:10 PM <mpickering> but yes you have to use that argument or use a flag I think 10:11 PM <dfeuer> mpickering: well, if the documentation is just wrong, and wasn't intended to be right, then we need to fix the documentation. 10:11 PM <mpickering> indeed, I've just been trying to work out the intention, implementation and documentation line up with each other 10:11 PM <mpickering> as they clearly don't at the moment 10:12 PM <dfeuer> But I do think it's worth considering; the funny special argument is highly unlikely to appear in any other (future) Haskell implementation, so using it is screaming "GHC only forever". }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by mpickering): I also confirmed that b61562feb87689a202118ca08ef270422c69dcc2 causes SpecConstr to fire on this example when it didn't before. Here is the snippet of the core which was produced *before* this patch. {{{ T13016.exampleMODULE2 :: Arr (Int, Int) [GblId, Caf=NoCafRefs, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}] T13016.exampleMODULE2 = T13016.ArrPair @ (Int, Int) @ Int @ Int @~ <(Int, Int)>_N T13016.exampleMODULE4 T13016.exampleMODULE3 T13016.exampleMODULE1 :: Int [GblId, Caf=NoCafRefs, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 20}] T13016.exampleMODULE1 = I# 5# exampleMODULE :: (Int, Int) [GblId, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=False, ConLike=False, WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 50 30}] exampleMODULE = case T13016.$w$s!: @ Int @ Int T13016.exampleMODULE2 T13016.exampleMODULE1 of _ [Occ=Dead] { (# ww1_sAJ, ww2_sAK #) -> (ww1_sAJ, ww2_sAK) } }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by andrewthad): I also feel the behavior of `SPECIALIZE INLINE` is weird in this situation, and I would prefer that it not be marked as a loop breaker. Here's an example that I was toying with that led me to this ticket: {{{!#hs {-# language DataKinds #-} {-# language GADTs #-} {-# language KindSignatures #-} {-# OPTIONS_GHC -O2 -fforce-recomp -ddump-simpl -dsuppress-all #-} import Data.Kind data Nat = Succ Nat | Zero data SNat :: Nat -> Type where SZero :: SNat 'Zero SSucc :: SNat n -> SNat ('Succ n) {-# SPECIALISE INLINE exponentiate :: SNat ('Succ n) -> Int -> Int #-} {-# SPECIALISE INLINE exponentiate :: SNat 'Zero -> Int -> Int #-} exponentiate :: SNat n -> Int -> Int exponentiate SZero x = 1 exponentiate (SSucc s) x = x * (exponentiate s x) main :: IO () main = print (exponentiate (SSucc (SSucc (SSucc (SSucc SZero)))) 3) }}} I would expect that the call to `exponentiate` be supercompiled, but it is not. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13016: SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function -------------------------------------+------------------------------------- Reporter: nfrisby | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Inlining Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #13014 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by mpickering): I don't think the earlier comments in this ticket are resolved. I would just expect `SPECIALISE INLINE` to be totally broken until they are. If you are blocked then you can achieve the same thing in your example using type classes. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13016#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC