strictness of unused arguments

Max Bolingbroke batterseapower at hotmail.com
Thu Mar 11 16:33:35 EST 2010


On 11 March 2010 12:50, Roman Beslik <beroal at ukr.net> wrote:
> I also can force the analyzer to think that "x1" and "x0" are strict by
> eta-expanding "f3":

There seem to be two issues here.

1) GHC only figures out and records strictness information on lambdas
that are syntactically together. I'm not sure how hard it would be to
change this, but probably not totally straightforward
2) GHC does not seem to be eta-expanding as much as it could get away
with. Generally eta expansion has the following effects:
a) Decreases work sharing, by pushing let-binding and case
decomposition within the lambda
b) Increases the efficiency of function calls and of the strictness
analyser by pushing together several lambdas

In this case the work that would be lost by eta expanding looks pretty
minimal (its generally very cheap primops that we could easily
recompute). However, to spot that this is actually safe GHC has to
eta-expand all of the "f" functions simultaneously, because they are
mutually recursive, and it turns out that their "cheapness" depends on
the "cheapness" of every other function in the loop. The simplifier is
not smart enough for this - you need a fixed point analysis.

I did toy with an arity analysis that has been proposed to spot such
opportunities, but I found that it could in some cases lose unbounded
amounts of ostensibly "cheap" work - and it didn't seem to have much
effect on nofib anyway, so this went nowhere.

Looking at the Core, I think that if the arities were fixed up the
strictness analyser *would* do the Right Thing here - so this might be
another vote for an arity analysis :-) (See the "Arity" section of
http://hackage.haskell.org/trac/ghc/wiki/Status/SLPJ-Tickets - it
might be worth filing a bug on GHC Trac with your nice simple example
too).

Out of curiosity, did you spot this in a real program?

Cheers,
Max


p.s. full Core output follows for those playing along at home:

==================== Demand analysis ====================
lvl_shD :: GHC.Types.Int -> GHC.Types.Int
LclId
[Arity 1
 Str: DmdType S]
lvl_shD = \ (x0_ado [ALWAYS Just S] :: GHC.Types.Int) -> x0_ado

Rec {
StrictUnusedArg.f4 [ALWAYS LoopBreaker Nothing] :: GHC.Types.Int
                                                   -> GHC.Types.Int
                                                   -> GHC.Types.Int
                                                   -> GHC.Types.Int
                                                   -> GHC.Types.Int
LclIdX
[Arity 2
 Str: DmdType U(L)L]
StrictUnusedArg.f4 =
  \ (x3_ads [ALWAYS Just U(L)] :: GHC.Types.Int)
    (eta_B1 [ALWAYS Just L] :: GHC.Types.Int) ->
    case x3_ads of _ { GHC.Types.I# x_ahS [ALWAYS Just L] ->
    case x_ahS of wild_X5 [ALWAYS Just L] {
      __DEFAULT ->
        let {
          a_sir [ALWAYS Just L] :: GHC.Prim.Int#
          LclId
          [Str: DmdType]
          a_sir = GHC.Prim.-# wild_X5 1 } in
        let {
          y_shm [ALWAYS Just D(L)] :: GHC.Types.Int
          LclId
          [Str: DmdType m]
          y_shm = GHC.Types.I# a_sir } in
        \ (x1_adv [ALWAYS Just L] :: GHC.Types.Int)
          (x0_adw [ALWAYS Just L] :: GHC.Types.Int) ->
          StrictUnusedArg.f4
            y_shm
            eta_B1
            x1_adv
            (case x0_adw of _ { GHC.Types.I# y_ai9 [ALWAYS Just L] ->
             GHC.Types.I# (GHC.Prim.+# a_sir y_ai9)
             });
      0 -> StrictUnusedArg.f3 eta_B1
    }
    }
StrictUnusedArg.f3 [ALWAYS LoopBreaker Nothing] :: GHC.Types.Int
                                                   -> GHC.Types.Int
                                                   -> GHC.Types.Int
                                                   -> GHC.Types.Int
LclIdX
[Arity 1
 Str: DmdType U(L)]
StrictUnusedArg.f3 =
  \ (x2_adq [ALWAYS Just U(L)] :: GHC.Types.Int) ->
    case x2_adq of _ { GHC.Types.I# x_ahS [ALWAYS Just L] ->
    case x_ahS of wild_B1 [ALWAYS Just L] {
      __DEFAULT ->
        let {
          a_siv [ALWAYS Just L] :: GHC.Prim.Int#
          LclId
          [Str: DmdType]
          a_siv = GHC.Prim.-# wild_B1 1 } in
        let {
          y_shy [ALWAYS Just S(L)] :: GHC.Types.Int
          LclId
          [Str: DmdType m]
          y_shy = GHC.Types.I# a_siv } in
        StrictUnusedArg.f4 y_shy y_shy;
      0 -> StrictUnusedArg.f2
    }
    }
StrictUnusedArg.f2 [ALWAYS LoopBreaker Nothing] :: GHC.Types.Int
                                                   -> GHC.Types.Int
                                                   -> GHC.Types.Int
LclIdX
[Arity 1
 Str: DmdType U(L)]
StrictUnusedArg.f2 =
  \ (x1_adj [ALWAYS Just U(L)] :: GHC.Types.Int) ->
    case x1_adj of _ { GHC.Types.I# x_ahS [ALWAYS Just L] ->
    case x_ahS of wild_B1 [ALWAYS Just L] {
      __DEFAULT ->
        let {
          a_six [ALWAYS Just L] :: GHC.Prim.Int#
          LclId
          [Str: DmdType]
          a_six = GHC.Prim.-# wild_B1 1 } in
        let {
          y_shB [ALWAYS Just S(L)] :: GHC.Types.Int
          LclId
          [Str: DmdType m]
          y_shB = GHC.Types.I# a_six } in
        StrictUnusedArg.f3 y_shB y_shB;
      0 -> lvl_shD
    }
    }
end Rec }


More information about the Glasgow-haskell-users mailing list