CPR Analysis is too conservative for certain inductive cases

While investigating the generated Core for a simple toy benchmark, I came up with the following minimal example:

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.

---

I'll add some more examples here when such a return-pattern specialisation might be useful.

• Nested CPR may not unbox if termination of nested components doesn't permit it to. We leave a -17% improvement in fish on the table here.
• #4267 (closed)

Trac metadata

Trac field	Value
Version	8.6.3
Type	Task
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture