Method selectors aren't floated out of loops

Here is a small example:

foo :: Num a => [a] -> [a]
foo as = filter (/=0) (map (\x -> x-x) as)

Here is the code that the current HEAD generates for the loop:

go_smy =
  \ (ds_akN :: [a_aiw]) ->
    case ds_akN of _ {
      [] -> GHC.Types.[] @ a_aiw;
      : y_akS ys_akT ->
        let {
          x_smA :: a_aiw
          x_smA = GHC.Num.- @ a_aiw $dNum_ajk y_akS y_akS } in
        case GHC.Classes./= @ a_aiw lvl_smu x_smA lit_smw of _ {
          GHC.Bool.False -> go_smy ys_akT;
          GHC.Bool.True -> GHC.Types.: @ a_aiw x_smA (go_smy ys_akT)
        }

Note that the Eq dictionary is inspected by (/=) in every loop iteration. Floating out GHC.Classes./= @ a_aiw lvl_smu (and, perhaps, GHC.Num.- @ a_aiw $dNum_ajk) should solve this. In fact, I wonder why that isn't happening already. Do method selectors have a wrong arity?

FWIW, in GHC 6.10 LiberateCase moves the method selection out of the loop (not ideal, but it gets the job done) so !NoSlow shows this as a slight performance regression.

Trac metadata

Trac field	Value
Version	6.13
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added Tbug Trac import labels

It's hard to know what the right thing to do here is. At the moment GHC treats (op d) as cheap, where op is a class operation and d is a dictionary. If we don't, we get lots of

f = \d. let h1 = op1 d in \x. ...(h1 x)...

So 'f' gets arity 1. And indeed there is some sharing that would be gotten if you had map (f dInt) xs, because the selection from dInt would happen just once. But in general it's much better to have one function with arity 2 rather than two functions of arity 1.

Same thing for a recursive function. If method selection isn't cheap you get lots of

f = \d. let h1 = op1 d
        in letrec fr = \x. ...(h1 x)...fr x'...
        in fr

If you inline h1, we can make f have arity 2.

So it's a hard call. I suppose that what we ultimately want is: share the method selection if doing so doesn't decrease arity. That could be done by running float-out near the end of optimisation (which it is) with a few twiddles to seek out those method selections. Worth thinking about.

Simon

changed milestone to %6.14 branch

removed milestone

changed milestone to %7.0.2

changed milestone to %7.2.1

changed milestone to %7.4.1

changed milestone to %7.6.1

changed weight to 3

Trac metadata

Trac field	Value
Priority	normal → low

changed milestone to %7.6.2

closed

With todays HEAD, I get good code:

T3697.foo =
  \ (@ a)
    ($dEq :: GHC.Classes.Eq a)
    ($dNum :: GHC.Num.Num a)
    (as :: [a]) ->
    let {
      ds :: a
      [LclId, Str=DmdType]
      ds = GHC.Num.fromInteger @ a $dNum T3697.foo1 } in
    let {
      lvl :: a -> a -> GHC.Types.Bool
      [LclId, Str=DmdType]
      lvl = GHC.Classes./= @ a $dEq } in
    let {
      lvl1 :: a -> a -> a
      [LclId, Str=DmdType]
      lvl1 = GHC.Num.- @ a $dNum } in
    letrec {
      go [Occ=LoopBreaker] :: [a] -> [a]
      [LclId, Arity=1, Str=DmdType <S,1*U>]
      go =
        \ (ds1 :: [a]) ->
          case ds1 of _ [Occ=Dead] {
            [] -> GHC.Types.[] @ a;
            : y ys ->
              let {
                x :: a
                [LclId, Str=DmdType]
                x = lvl1 y y } in
              case lvl x ds of _ [Occ=Dead] {
                GHC.Types.False -> go ys;
                GHC.Types.True -> GHC.Types.: @ a x (go ys)
              }
          }; } in
    go as

Given the age of the bug, I don’t dare to guess what has fixed this. Also, hard to make a useful testcase here.

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

added runtime perf label

added Plow label

added Arity and eta conversion label