GHC inliner doesn't

[guest]

Compile this program

{-# OPTIONS_GHC -O2 -ddump-simpl #-}
module Foo where

class C a where
    to' :: a -> Int
    from' :: Int -> a

{-# NOINLINE to #-}
to :: (C a) => a -> Int
to = to'

{-# NOINLINE from #-}
from :: (C a) => Int -> a
from = from'

{-# INLINE foo #-}
foo :: (C a) => (Int -> Int) -> a -> a
foo f x = from (f (to x))

bar :: (C a) => (Int -> Int) -> a -> a
bar f = foo f . foo f
 

Study the output. It contains

...
Foo.foo =
  __inline_me (\ (@ a_a6n) ($dC_a6t :: Foo.C a_a6n) ->
...

and

...
Foo.bar =
  \ (@ a_a6w) ($dC_a6G :: Foo.C a_a6w) ->
    let {
      foo1_s7S [ALWAYS Just L] :: (GHC.Base.Int -> GHC.Base.Int) -> a_a6w -> a_a6w
      [Str: DmdType]
      foo1_s7S = Foo.foo @ a_a6w $dC_a6G
...

Why isn't foo inlined?

Note that if the export list is changed to only export bar, then foo does get inlined.

[simonpj]

GHC deliberately doesn't inline a function, even if there's an INLINE pragma, if there is nothing "interesting" about the arguments or context. For example

   f x y = g (h x y)

Here GHC won't inline h even if h has an INLINE pragma. Why? Because doing so just increases code duplication.

However, GHC does take account of context too. If g has a RULE, then h will be inlined in case that inlining allows g's RULE to match.

It's possible that even this isn't enough in some circumstances. Perhaps you have such a case in mind.

But as things stand, it's deliberate.

Simon

[guest]

If it is deliberate, why does exporting foo make a difference? That's rather unintuitive.

I'm not sure I buy that argument that not inlining foo is the right decision here. Look at the difference in code without and with inlining. I think the inlined version looks better.

-- No inline
Foo.bar =
  \ (@ a_a6v) ($dC_a6F :: Foo.C a_a6v) ->
    let {
      foo1_s7R [Just L] :: (GHC.Base.Int -> GHC.Base.Int) -> a_a6v -> a_a6v
      [Str: DmdType]
      foo1_s7R = Foo.foo @ a_a6v $dC_a6F } in
    \ (f_a5Y :: GHC.Base.Int -> GHC.Base.Int) ->
      let {
        f1_s7T [Just L] :: a_a6v -> a_a6v
        [Str: DmdType]
        f1_s7T = foo1_s7R f_a5Y } in
      \ (x_a6R :: a_a6v) -> f1_s7T (f1_s7T x_a6R)

-- Inline (because foo was not exported)
Foo.bar =
  \ (@ a_a6v) ($dC_a6F :: Foo.C a_a6v) ->
    let {
      from1_s7I [Just L] :: GHC.Base.Int -> a_a6v
      [Str: DmdType]
      from1_s7I = Foo.from @ a_a6v $dC_a6F } in
    let {
      to1_s7G [Just L] :: a_a6v -> GHC.Base.Int
      [Str: DmdType]
      to1_s7G = Foo.to @ a_a6v $dC_a6F } in
    \ (f_a5Y :: GHC.Base.Int -> GHC.Base.Int) (eta_s6T :: a_a6v) ->
      from1_s7I (f_a5Y (to1_s7G (from1_s7I (f_a5Y (to1_s7G eta_s6T)))))

Also, if INLINE doesn't really inline, then I'd like a REALLYINLINE pragma. Sometimes I know what I'm doing, and I'd like the compiler to obey.

[guest]

Add the rule below to the example above. With the code as given above the rule doesn't fire since foo isn't inlined. With just bar exported the rule does fire, because foo is inlined.

-- XXX Add -fno-method-sharing to the command line.  It's a static flag. :(
{-# RULES "to/from" forall x . to (from x) = x #-}

[simonpj]

A function that is only called once (and not exported) is always inlined, since that causes no code duplication. Does that explain the difference.

Simon

[guest]

As you can see, the original program uses foo twice, so that doesn't explain the inlining.

[simonpj]

Yes, but as you point out, the "method-sharing" thing commons up the two occurrences of 'foo'. If we export foo, we get

Foo.bar =
  \ (@ a_a6x) ($dC_a6H :: Foo.C a_a6x) ->
    let {
      foo1_s7T [ALWAYS Just L] :: (GHC.Base.Int -> GHC.Base.Int) -> a_a6x -> a_a6x
      [Str: DmdType]
      foo1_s7T = Foo.foo @ a_a6x $dC_a6H
    } in 
      \ (f_a60 :: GHC.Base.Int -> GHC.Base.Int) ->
        let {
          f1_s7V [ALWAYS Just L] :: a_a6x -> a_a6x
          [Str: DmdType]
          f1_s7V = foo1_s7T f_a60
        } in  \ (x_a6T :: a_a6x) -> f1_s7V (f1_s7V x_a6T)

Notice just one call to foo. If foo is not exported, this is the only call to foo so it gets inlined.

It's delicate, I grant you. Maybe I should experiment with making INLINE inline always (at least if saturated). I'm a bit reluctant to further complicate the interface with REALLYINLINE.

Simon

[guest]

In this case you need to inline foo, and then there will be a second opportunity to inline foo inside the inlined body. It's the first and second inlining of foo that meet in the rule. This indicates that current heuristic for not inlining is broken.

I don't really want REALLYINLINE either, but in this case inlining must happen for the rule to apply, so there has to be a way to make the compiler obey the pragma.

As you say, it's delicate. Far too delicate.

[Isaac Dupree]

IIRC, one can use RULES (and duplicate the function implementation) as a inline-for-sure equivalent. Not very pleasant, obviously.

[ross]

I think I've just tripped over this one. In Data.Foldable, there is

toList :: Foldable t => t a -> [a]
toList t = build (\ c n -> Data.Foldable.foldr c n t)

so I would expect

f :: Foldable t => t a -> [a]
f xs = last (map (:[]) (toList xs))

(only using last to simplify the example) to deforest to the equivalent of

f xs = last (Data.Foldable.foldr (\ x -> [x]:) [] xs)

but it doesn't, because toList isn't inlined until too late, even if I give it an INLINE pragma.

[reinerp]

With 7.0.0-rc1, foo is inlined. The core for bar is (a wrapper of)

Foo.$wbar =
  \ (@ a_acS)
    (ww_sl0 :: a_acS -> GHC.Types.Int)
    (ww1_sl1 :: GHC.Types.Int -> a_acS)
    (w_sl3 :: GHC.Types.Int -> GHC.Types.Int)
    (w1_sl4 :: a_acS) ->
    let {
      $dC_sld :: Foo.C a_acS
      [LclId]
      $dC_sld = Foo.D:C @ a_acS ww_sl0 ww1_sl1 } in
    Foo.from
      @ a_acS
      $dC_sld
      (w_sl3
         (Foo.to
            @ a_acS
            $dC_sld
            (Foo.from
               @ a_acS $dC_sld (w_sl3 (Foo.to @ a_acS $dC_sld w1_sl4)))))

Also with ghc-7.0.0-rc1, ross's code behaves as desired: f has Core

Foo.$wf =
  \ (@ t_acQ::* -> *)
    (@ a_acR)
    (ww_skO
       :: forall a1_ag3 b_ag4.
          (a1_ag3 -> b_ag4 -> b_ag4) -> b_ag4 -> t_acQ a1_ag3 -> b_ag4)
    (w_skT :: t_acQ a_acR) ->
    case ww_skO
           @ a_acR @ [[a_acR]] (Foo.f1 @ a_acR) (GHC.Types.[] @ [a_acR]) w_skT
    of _ {
      [] -> GHC.List.last2 @ [a_acR];
      : x_aeY xs_aeZ -> GHC.List.last1 @ [a_acR] x_aeY xs_aeZ
    }

[simonpj]

Thank you for testing this. This is all part of the great INLINE fix.

It's tricky to think of a regression test for this, so I think I'll just close it.

Simon