[GHC] #16335: Make CPR Analysis more aggressive for inductive cases

[GHC]

#16335: Make CPR Analysis more aggressive for inductive cases
-------------------------------------+-------------------------------------
           Reporter:  sgraf          |             Owner:  (none)
               Type:  task           |            Status:  new
           Priority:  normal         |         Milestone:  ⊥
          Component:  Compiler       |           Version:  8.6.3
           Keywords:  CPRAnalysis    |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 While investigating the generated Core for a simple toy benchmark, I came
 up with the following minimal example:

 {{{#!hs

 data Expr
   = Lit Int
   | Plus Expr Expr

 eval :: Expr -> Int
 eval (Lit n) = n
 eval (Plus a b) = eval a + eval b
 }}}

 resulting in the following Core:

 {{{
 eval
   = \ (ds_d112 :: Expr) ->
       case ds_d112 of {
         Lit n_aXf -> n_aXf;
         Plus a_aXg b_aXh ->
           case eval a_aXg of { GHC.Types.I# x_a1bK ->
           case eval b_aXh of { GHC.Types.I# y_a1bO ->
           GHC.Types.I# (GHC.Prim.+# x_a1bK y_a1bO)
           }
           }
       }
 }}}

 Note that this needlessly unboxes and boxes primitive Ints. Lifting this
 is precisely the job of CPR, but `eval` doesn't exactly have the CPR
 property: the `Lit` case doesn't return a product. But we're punishing
 ourselves for the base case when ''even the function itself'' recurses
 multiple times!

 The code resulting from WWing here wouldn't even look bad in the `Lit`
 case:

 {{{
 Foo.$weval
   = \ (w_s1cn :: Expr) ->
       case w_s1cn of {
         Lit dt_d11b -> case dt_d11b { I# ds_abcd -> ds_abcd };
         Plus a_aXf b_aXg ->
           case Foo.$weval a_aXf of ww_s1cq { __DEFAULT ->
           case Foo.$weval b_aXg of ww1_X1dh { __DEFAULT ->
           GHC.Prim.+# ww_s1cq ww1_X1dh
           }
           }
       }

 eval
   = \ (w_s1cn :: Expr) ->
       case Foo.$weval w_s1cn of ww_s1cq { __DEFAULT ->
       GHC.Types.I# ww_s1cq
       }
 }}}

 Granted, this is bad for the case where there is no recursion happening
 and we need the result of `eval` boxed, but that's a small price to pay
 IMO.

 I begin to think of CPR more of as the "dual" to SpecConstr than to
 Strictness Analysis. Return pattern specialisation, so to speak.

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