Re: [GHC] #14816: Missed Called Arity opportunity?

21 Feb 2018

      #14816: Missed Called Arity opportunity?
-------------------------------------+-------------------------------------
        Reporter:  dfeuer            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler          |              Version:  8.2.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by sgraf):

 OK, that didn't work, but for reasons I didn't expect. If we apply that
 change, suddenly some bindings get *worse* *strictness* annotations,
 although it should only make for *less conservative* (possibly unsound)
 *usage* annotations, as `reuseEnv` will only affect usage information.

 It turns out that this is due to the interaction between the lazy fv hack
 and the fix-pointing algorithm. An example is adapted from T876:

 {{{
 foo :: Int -> Int
 foo n = sum [ length [i..n] | i <- [1..n] ]

 main = print (foo 100)
 }}}

 The variant that does get rid of the call to `reuseEnv` altogether will
 produce something like this code:

 {{{
 foo
   = \ (n_aYV [Dmd=<L,U(U)>] :: Int) ->
       joinrec {
         go_a2c3 [Occ=LoopBreaker] :: [Int] -> Int -> Int
         [LclId[JoinId(2)],
          Arity=2,
          Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True,
                  WorkFree=True, Expandable=True, Guidance=IF_ARGS [30 20]
 137 0}]
         go_a2c3 (ds_a2c4 [Dmd=<S,1*U>] :: [Int])
                 (eta_B1 [Dmd=<L,1*U(U)>] :: Int)
           = case ds_a2c4 of {
               [] -> eta_B1;
               : y_a2c9 [Dmd=<L,1*U(U)>] ys_a2ca ->
                 jump go_a2c3
                   ys_a2ca
                   (case eta_B1 of { GHC.Types.I# x_a3ii [Dmd=<S,U>] ->
                    case y_a2c9 of { GHC.Types.I# x_a3jq [Dmd=<S,U>] ->
                    case n_aYV of { GHC.Types.I# y_a3jz [Dmd=<S,U>] ->
                    case GHC.List.$wlenAcc @ Int (GHC.Enum.eftInt x_a3jq
 y_a3jz) 0#
                    of ww2_a4JP [Dmd=<S,U>]
                    { __DEFAULT ->
                    GHC.Types.I# (GHC.Prim.+# x_a3ii ww2_a4JP)
                    }
                    }
                    }
                    })
             }; } in
       jump go_a2c3
         (case n_aYV of { GHC.Types.I# y_a3jz [Dmd=<S,U>] ->
          GHC.Enum.eftInt 1# y_a3jz
          })
         lvl_s4Jd
 }}}

 Note that `go` is clearly strict in `n` (that's what HEAD finds out), but
 this variant is too conservative. Some printfs revealed that's due to
 abortion of fix-pointing. This is a log for the `lazy_fv`s and the
 `sig_fv` envs:

 {{{
 dmdAnalRhsLetDown go_a2c3 [] []
 dmdAnalRhsLetDown go_a2c3 [] [aYV :-> <L,1*U(U)>]
 dmdAnalRhsLetDown go_a2c3 [aYV :-> <L,U(U)>] []
 dmdAnalRhsLetDown go_a2c3 [] [aYV :-> <L,1*U(U)>]
 dmdAnalRhsLetDown go_a2c3 [aYV :-> <L,U(U)>] []
 dmdAnalRhsLetDown go_a2c3 [] [aYV :-> <L,1*U(U)>]
 dmdAnalRhsLetDown go_a2c3 [aYV :-> <L,U(U)>] []
 dmdAnalRhsLetDown go_a2c3 [] [aYV :-> <L,1*U(U)>]
 dmdAnalRhsLetDown go_a2c3 [aYV :-> <L,U(U)>] []
 dmdAnalRhsLetDown go_a2c3 [] [aYV :-> <L,1*U(U)>]
 dmdAnalRhsLetDown go_a2c3 [] [aYV :-> <L,1*U(U)>]
 dmdAnalRhsLetDown foo [] []
 }}}

 It flip flops between putting `n`s demand into the `sig_fv` and the
 `lazy_fv`. That's decided by `isWeakDmd`, which amounts to checking if the
 demand is equivalent to `<L,U>` and will thus no longer change during fix-
 pointing. After the initial iteration, we find that `n` is called once and
 gets tagged onto the strictness signature. The second iteration sees that
 `n` is called an additional time, demand `<L,U(U)>`. This means it no
 longer has an interesting demand and goes into `lazy_fv`. But here's the
 culprit: The fix-pointer only compares the strictness signature for
 changes! It will start a third iteration, completely forget about any
 `lazy_fv` and flop back to the state of the first iteration.

 There's two ways out:

 1. Also check `lazy_fvs` for changes. This is the thing we wanted to avoid
 in the first place. Also this is LetUp in disguise, which purposefully
 isn't equipped to deal with recursive bindings.
 2. Don't check `lazy_fvs`. These are outer bindings only, so they don't
 actually need to play a role in fix-pointing. Also everything in
 `lazy_fvs` is already top-ish, so it suffices to check if a variable in a
 prior signature is now part of `lazy_fvs` and exclude them from the check.

 I'll try 2. tomorrow.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14816#comment:12>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler