Skip to content

Missed CSE opportunity in STG

Consider this little program

f x = x `seq` [Just x, Just x]

We get this Core:

f = \ (@a_agO) (x_age :: a_agO) ->
      case x_age of x1_X0 { __DEFAULT ->
      GHC.Types.:
        @(Maybe a_agO)
        (GHC.Maybe.Just @a_agO x1_X0)
        (GHC.Types.:
           @(Maybe a_agO)
           (GHC.Maybe.Just @a_agO x1_X0)
           (GHC.Types.[] @(Maybe a_agO)))
      }

Note the duplicated Just x. Core CSE doesn't catch it because it only looks at enclosing bindings, not peer expressions. We could beef up in CSE in Core. But we have CSE in STG too. Let's see what we get

Foo.f :: forall {a}. a -> [GHC.Maybe.Maybe a]
[GblId, Arity=1, Str=<1L>, Cpr=2, Unf=OtherCon []] =
    {} \r [x_sxC]
        case x_sxC of x1_sxD {
        __DEFAULT ->
        let {
          sat_sxF [Occ=Once1] :: GHC.Maybe.Maybe a_agO
          [LclId] = CCCS GHC.Maybe.Just! [x1_sxD]; } in
        let {
          sat_sxG [Occ=Once1] :: [GHC.Maybe.Maybe a_agO]
          [LclId] = CCCS :! [sat_sxF GHC.Types.[]]; } in
        let {
          sat_sxE [Occ=Once1] :: GHC.Maybe.Maybe a_agO
          [LclId] = CCCS GHC.Maybe.Just! [x1_sxD];
        } in  : [sat_sxE sat_sxG];
        };

Yikes! sat_sxE is identical to sat_sxF and yet we don't CSE them. Why not?

I came across this when debugging a regression in !5504 (merged) (itself from #19672 (closed)), where I found that despite better SpecConstr, the nofib progam real/anna slowed down slightly. Why? Because we'd specialised and unrolled a bit, and got more copies of the same thing, which weren't being CSE'd. For the record, the function was TypeCheck5.tcApply_sub.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information