[GHC] #2940: Do CSE after CorePrep

[GHC]

#2940: Do CSE after CorePrep
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  simonpj
            Type:  bug               |               Status:  new
        Priority:  lowest            |            Milestone:  8.0.1
       Component:  Compiler          |              Version:  6.10.1
      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 osa1):

 Simon, I was experimenting with CSE and unless I'm missing something I
 think
 current CSE is basically useless and we can just remove it.

 As far as I understand from the implementation, current CSE implementation
 never introduces a let binding. So for example if I have something like:

 {{{#!haskell
 g x = (x + 1, x + 1)
 }}}

 Current implementation never does CSE here. What's worse is that even if I
 have
 a let binding like this:

 {{{#!haskell
 g x = let x_1 = x + 1
        in (x_1, x + 1)
 }}}

 Most of the time CSE can't do anything, because some other pass
 inlines/unfolds
 `x_1` here(even with -O0). `g` above is compiled to this:

 {{{#!haskell
 g :: Int -> (Int, Int)
 g =
   \ (x_atS :: Int) ->
     (case x_atS of _ { I# x_a1IL -> I# (+# x_a1IL 1#) },
      case x_atS of _ { I# x_a1IL -> I# (+# x_a1IL 1#) })
 }}}

 See how let binding is removed. CSE can't do anything here. Funny thing is
 even
 if I mark this let binding as `NOINLINE` CSE can't work, because of Note
 [CSE
 for INLINE and NOINLINE]. This is what happens when I mark `x_1` as
 `NOINLINE`:

 {{{#!haskell
 g' :: Int -> (Int, Int)
 g' =
   \ (x_av2 :: Int) ->
     let {
       x_1_s1Jd :: Int
       x_1_s1Jd = case x_av2 of _ { I# x_a1IL -> I# (+# x_a1IL 1#) } } in
     (case x_av2 of _ { I# x_a1IL -> I# (+# x_a1IL 1#) }, x_1_s1Jd)
 }}}

 There's a clear CSE opportunity missed because of Note [CSE for INLINE and
 NOINLINE].


 So unless we actually run this after `CorePrep` it just can't do anything.

 I tried on a couple of examples and it seems like current CSE
 implementation
 actually maintains invariants at least some of the time. For example, it
 works
 find on the code in the code above. Do we have something like `CoreLint`
 but
 fore `CorePrep` invariants?

 ----

 In the examples I tried CSE never worked before the `CorePrep` step. After
 `CorePrep` it worked some of the time. For example, `g` above is compiled
 to
 this:

 {{{#!haskell
 -- RHS size: {terms: 17, types: 8, coercions: 0}
 g :: Int -> (Int, Int)
 g =
   \ (x_s2nV :: Int) ->
     let {
       sat_s2o3 :: Int
       sat_s2o3 =
         case x_s2nV of wild_s2o0 { I# x1_s2o1 ->
         case +# x1_s2o1 1# of sat_s2o2 { __DEFAULT -> I# sat_s2o2 }
         } } in
     let {
       sat_s2nZ :: Int
       sat_s2nZ = sat_s2o3 } in
     (sat_s2o3, sat_s2o3)
 }}}

 `h` also CSEs nicely if we run it after `CorePrep`:

 {{{#!haskell
 -- RHS size: {terms: 23, types: 8, coercions: 0}
 h :: Int# -> (Int, Int)
 h =
   \ (x_s2nq :: Int#) ->
     case +# x_s2nq 1# of sat_s2nt { __DEFAULT ->
     case *# sat_s2nt 2# of sat_s2nu { __DEFAULT ->
     let {
       sat_s2nv :: Int
       sat_s2nv = I# sat_s2nu } in
     case sat_s2nt of sat_s2nr { __DEFAULT ->
     let {
       sat_s2ns :: Int
       sat_s2ns = I# sat_s2nt } in
     (sat_s2ns, sat_s2nv)
     }
     }
     }
 }}}

 It doesn't work on `rev`, because of how `CorePrep` generates a program
 without
 any CSE opportunity:

 {{{#!haskell
 -- RHS size: {terms: 23, types: 19, coercions: 0}
 Main.rev :: [GHC.Types.Bool] -> [GHC.Types.Bool]
 Main.rev =
   \ (xs_s2nl :: [GHC.Types.Bool]) ->
     let {
       sat_s2np :: [GHC.Types.Bool]
       sat_s2np =
         case GHC.List.reverse1
                @ GHC.Types.Bool xs_s2nl (GHC.Types.[] @ GHC.Types.Bool)
         of sat_s2no { __DEFAULT ->
         GHC.List.filter
           @ GHC.Types.Bool (GHC.Base.id @ GHC.Types.Bool) sat_s2no
         } } in
     case GHC.List.reverse1
            @ GHC.Types.Bool xs_s2nl (GHC.Types.[] @ GHC.Types.Bool)
     of sat_s2nm { __DEFAULT ->
     case GHC.List.reverse1
            @ GHC.Types.Bool sat_s2nm (GHC.Types.[] @ GHC.Types.Bool)
     of sat_s2nn { __DEFAULT ->
     GHC.Base.++ @ GHC.Types.Bool sat_s2nn sat_s2np
     }
     }
 }}}

 Ideally we'd like to generate a binding for `GHC.List.reverse1 @
 GHC.Types.Bool xs_s2nl (GHC.Types.[] @ GHC.Types.Bool)` but since this
 expression is not bound to a let-binder we can't CSE.

 (This would work if had the invariant of having only variables(and
 literals) in
 scrutinee position)

 For the record, this is what's generated by CSE after `CorePrep`:

 {{{#!haskell
 rev :: [Bool] -> [Bool]
 rev =
   \ (xs_s2nl :: [Bool]) ->
     let {
       sat_s2np :: [Bool]
       sat_s2np =
         case reverse1 @ Bool xs_s2nl ([] @ Bool) of sat_s2no { __DEFAULT
 ->
         filter @ Bool (id @ Bool) sat_s2no
         } } in
     case reverse1 @ Bool xs_s2nl ([] @ Bool) of sat_s2nm { __DEFAULT ->
     case reverse1 @ Bool sat_s2nm ([] @ Bool)
     of sat_s2nn { __DEFAULT ->
     ++ @ Bool sat_s2nn sat_s2np
     }
     }
 }}}

 ----

 I want to work on running CSE after CorePrep, but before that I'm planning
 implementing a CoreLint-like pass for checking CorePrep invariants. Simon,
 does
 that make sense? Any ideas? Am I missing anything in my observations?

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