Opened 6 years ago

Last modified 3 years ago

#8589 new bug

Bad choice of loop breaker with INLINABLE/INLINE

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

Description

Take the following program, which defines a pair of lists recursively:

module Test(xs, ys) where

pair :: ([Bool], [Bool])
pair = (False:xs, True:ys)
  where
    (xs, ys) = pair

(xs, ys) = pair

GHC is clever enough to disentangle xs from ys and with -ddump-simpl -O I get:

Rec {
xs [Occ=LoopBreaker] :: [Bool]
[GblId, Caf=NoCafRefs, Str=DmdType]
xs = : False xs
end Rec }

Rec {
ys [Occ=LoopBreaker] :: [Bool]
[GblId, Caf=NoCafRefs, Str=DmdType]
ys = : True ys
end Rec }

However, if I mark pair as INLINABLE or INLINE (it doesn't matter which), I get much worse code where xs and ys go through pair:

Rec {
pair [InlPrag=INLINABLE[ALWAYS], Occ=LoopBreaker]
  :: ([Bool], [Bool])
[GblId,
 Str=DmdType m,
 Unf=Unf{Src=InlineStable, TopLvl=True, Arity=0, Value=True,
         ConLike=True, WorkFree=False, Expandable=True,
         Guidance=IF_ARGS [] 50 30
         Tmpl= (: False
                  (case pair of _ { (xs1_Xf6 [Occ=Once], _) -> xs1_Xf6 }),
                : True (case pair of _ { (_, ys1_Xf6 [Occ=Once]) -> ys1_Xf6 }))}]
pair = (a1_rgo, a_rgn)

ys_ys :: [Bool]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, WorkFree=True, Expandable=True,
         Guidance=IF_ARGS [] 10 0}]
ys_ys = case pair of _ { (xs1_XeW, ys1_Xf7) -> ys1_Xf7 }

a_rgn :: [Bool]
[GblId, Str=DmdType]
a_rgn = : True ys_ys

xs_xs :: [Bool]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, WorkFree=True, Expandable=True,
         Guidance=IF_ARGS [] 10 0}]
xs_xs = case pair of _ { (xs1_XeW, ys1_XeS) -> xs1_XeW }

a1_rgo :: [Bool]
[GblId, Str=DmdType]
a1_rgo = : False xs_xs
end Rec }

ys :: [Bool]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(unsat_ok=True,boring_ok=True)}]
ys = ys_ys

xs :: [Bool]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(unsat_ok=True,boring_ok=True)}]
xs = xs_xs

It seems that GHC chooses pair as the loop breaker, which stops the simplifier in its tracks.

It might seem a bit silly to mark pair as INLINE, since it's not mutually recursive. The function I really had was polymorphic with a typeclass constraint, and I wrote INLINABLE to get it specialised at its call site. (Also, pair is mutually recursive in the Core, so you would expect GHC to avoid using it as a loop breaker if I mark it INLINE.)

Attachments (1)

Test.hs (206 bytes) - added by NickSmallbone 6 years ago.

Download all attachments as: .zip

Change History (9)

Changed 6 years ago by NickSmallbone

Attachment: Test.hs added

comment:1 Changed 6 years ago by tibbe

Aside: I've seen other cases where INLINE and INLINABLE makes things worse that are related to other optimizations being inhibited (i.e. not due to code size increase). I find it slightly worrying that INLINE has other effects than making an expression look cheap (i.e. the original, unoptimized core is inlined, at which point it might be too late for optimization to happen). I understand the reason (rules) we made INLINE behave differently, but perhaps we need two pragmas?

comment:2 Changed 6 years ago by carter

I may have a nontrivial example of a related problem in INLINE/INLINEABLE + mutually recursive functions, i'll try to reconstruct it and add it to this ticket if i can reproduce the problem in HEAD

comment:3 Changed 6 years ago by simonpj

Explanation of what is happening.

  • Remember that each Id has one, and only one, inlining attached to it.
  • With INLINABLE/INLINE, the pair's inlining is used to store the original RHS.
  • But since the group is recursive, pair is chosen as loop breaker, and never gets inlined.

Why does it work without an INLINE pragma? Because we don't snapshot the original RHS we are free to optimise it, which we do by "floating out" some local let bindings, thus exposing the pair. And we are careful never to choose a visible pair as a loop breaker unless we absolutely have to.

What to do. I'm now pretty sure that INLINEABE should really be "SPECIALISABLE", and should be stored quite separately from the Id's inlining. Then they would not get in each others way. See #5928 for another example.

INLINE is a bit less obvious. The simple cases are already fine:

  • For non-recursive functions, if you say INLINE, you really mean to inline it, so it seems stupid to keep a separate snapshot.
  • Recursive functions never inline anyway, so an INLINE pragma is stupid.

A recursive group with INLINE is tricky,and that is the case here. I'm still thinking about how it should go.

comment:4 Changed 6 years ago by carter

@simon, so would that imply specializable would (then) be usable on functions that don't have any type class parameters?

comment:5 Changed 6 years ago by simonpj

What would it mean to specialise a function with no type-class parameters. Example?

comment:6 Changed 6 years ago by carter

sorry, let me clarify, you said "INLINEABLE should really be like SPECIALIZABLE", could you expand on that?

so I'm asking you to sort of expand on what you mean, and how such a modified INLINEABLE would work on typeclass-free code (ie just a polymorphic function like apply :: (a -> b )-> a -> b ).

Last edited 6 years ago by carter (previous) (diff)

comment:7 Changed 6 years ago by simonpj

Currently the only (useful) behaviour of INLINEABLE for recursive functions is to allow type-class-overloaded functions to be specialised. That's why I think a name-change might be in order.

We never specialise non-overloaded functions; doing so would simply generate two copies of the same machine code.

comment:8 Changed 3 years ago by mpickering

Keywords: Inlining added
Note: See TracTickets for help on using tickets.