[GHC] #15631: Lost opportunity to eliminate seq

Wed Sep 12 08:46:53 UTC 2018

#15631: Lost opportunity to eliminate seq
-------------------------------------+-------------------------------------
           Reporter:  simonpj        |             Owner:  (none)
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:  8.6.1
          Component:  Compiler       |           Version:  8.4.3
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 Consider this:
 {{{
 f xs = let ys = reverse xs in
        ys `seq` length xs +
                 length (reverse (case ys of { a:as -> as; [] -> [] }))
 }}}
 We end up with this
 {{{
 Foo.$wf
     = \ (@ a_s4a0) (w_s4a1 :: [a_s4a0]) ->
 (1)   case GHC.List.reverse1 @ a_s4a0 w_s4a1 (GHC.Types.[] @ a_s4a0)
          of ys_ap9 { __DEFAULT ->
       case GHC.List.$wlenAcc @ a_s4a0 w_s4a1 0#
          of ww2_a49t { __DEFAULT ->
 (2)   case ys_ap9 of {
         [] ->
           case Foo.f1 @ a_s4a0 of { GHC.Types.I# v1_B2 ->
           GHC.Prim.+# ww2_a49t v1_B2
           };
         : a1_aK8 as_aK9 ->
           case GHC.List.$wlenAcc
                  @ a_s4a0
                  (GHC.List.reverse1 @ a_s4a0 as_aK9 (GHC.Types.[] @
 a_s4a0))
                  0#
           of ww1_X49V
           { __DEFAULT ->
           GHC.Prim.+# ww2_a49t ww1_X49V
           } } } }
 }}}
 The case expression (1) is the `seq` on ys.  The case marked (2) is the
 case analysis in the argument of the second `reverse`.

 But that first `seq` is redundant!  We could equally well say
 {{{
 Foo.$wf
     = \ (@ a_s4a0) (w_s4a1 :: [a_s4a0]) ->
       case GHC.List.$wlenAcc @ a_s4a0 w_s4a1 0#
          of ww2_a49t { __DEFAULT ->
 (2)   case GHC.List.reverse1 @ a_s4a0 w_s4a1 (GHC.Types.[] @ a_s4a0) of {
         [] ->
           case Foo.f1 @ a_s4a0 of { GHC.Types.I# v1_B2 ->
           GHC.Prim.+# ww2_a49t v1_B2
           };
         : a1_aK8 as_aK9 ->
           case GHC.List.$wlenAcc
                  @ a_s4a0
                  (GHC.List.reverse1 @ a_s4a0 as_aK9 (GHC.Types.[] @
 a_s4a0))
                  0#
           of ww1_X49V
           { __DEFAULT ->
           GHC.Prim.+# ww2_a49t ww1_X49V
           } } } }
 }}}
 That's better because we generate code for only two evals rather than
 three.

 The general pattern is
 {{{
   case <scrut> of b { DEFAULT -> <body> }
 ==>
   let b = <scrut> in <body>
 }}}
 where the case binder `b` is used strictly in `<body>`.  In this case it's
 safe to switch to a `let` (marked as strict) which can now be inlined
 or floated in a way that `case` expressions cannot.

 We already do this transformation, here in `Simplify.rebuildCase`:
 {{{
 rebuildCase env scrut case_bndr alts@[(_, bndrs, rhs)] cont
 ...
   | all_dead_bndrs
   , if isUnliftedType (idType case_bndr)
     then exprOkForSpeculation scrut
     else exprIsHNF scrut || scrut_is_demanded_var scrut
   = ...turn case into let...
 }}}
 The key bit (for this situation) is `scrut_is_demanded_var`.
 '''But it only fires if `<scrut>` is a variable'''.

 I see no reason for this restriction.  I think it's sound
 regardless.  Yes, if we decide to inline the binding `b = <scrut>` we
 might change which exception appears; but that is within the semantics
 of exceptions; and it's still true if `<scrut>` is a variable.

 So I think we can safely replace `scrut_is_demand_var` with just
 `case_bndr_is_demanded`, independent of what `scrut` looks like.

 I dug back into ghc history to see how the current code came about, bu it
 had a long evolution and I didn't find any reason for sticking to a
 variable here.

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