Skip to content

Lost opportunity to eliminate seq

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.

Trac metadata
Trac field Value
Version 8.4.3
Type Bug
TypeOfFailure OtherFailure
Priority normal
Resolution Unresolved
Component Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information