Opened 3 years ago

Last modified 20 months ago

#13016 new bug

SPECIALIZE INLINE doesn't necessarily inline specializations of a recursive function

Reported by: nfrisby Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.0.1
Keywords: Inlining Cc: mpickering, dfeuer
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #13014 Differential Rev(s):
Wiki Page:

Description

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.

{-# 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)
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.

Change History (12)

comment:1 Changed 3 years ago by mpickering

Cc: mpickering added
Keywords: Inlining added

comment:2 Changed 2 years ago by dfeuer

Cc: dfeuer added

This doesn't sound very complicated, but I can't seem to find the code where it's handled. Anyone have a hint?

comment:3 Changed 2 years ago by dfeuer

Just for the heck of it, I decided to try translating this into class style:

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

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.

comment:4 Changed 2 years ago by dfeuer

FYI, it looks like the GADT thing was actually mentioned in the original commit that implemented SPECIALISE INLINE: 958924a2b338aebbcc8a88ba2cab511517762a19.

comment:5 Changed 2 years ago 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.

comment:6 Changed 2 years ago by mpickering

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.

comment:7 Changed 2 years ago by mpickering

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 ?

comment:8 Changed 2 years ago 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.

comment:9 Changed 2 years ago 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".

comment:10 Changed 2 years ago 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)
  }

comment:11 Changed 20 months ago 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:

{-# 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.

Last edited 20 months ago by andrewthad (previous) (diff)

comment:12 in reply to:  11 Changed 20 months ago 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.

Note: See TracTickets for help on using tickets.