Opened 7 months ago

Last modified 7 months ago

#16335 new task

Make CPR Analysis more aggressive for inductive cases

Reported by: sgraf Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.6.3
Keywords: CPRAnalysis Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Change History (2)

comment:1 Changed 7 months ago by simonpj

Nicely characterised.

CPR (to one level) is always sound; it may just do some unnecessary reboxing.

So we could just try saying that a function has the CPR property if any of its case branches do, rather than (as now) if 'all' do. That would, I assume, be a rather easy experiment to try.

(It'd be lovely to know what are the hot branches!)

comment:2 Changed 7 months ago by sgraf

To expand on the "Return pattern specialisation" thing:

SpecConstr CPR+WW
Multiple specialisationsOne specialisation
Looks at how much the definition scrutinises its arguments in any of its case expressions (unless -fspec-constr-keen)Looks at how deep the constructed products are in all its return branches (mostly since we only do one specialisation)
Compares that to how the function is called and only allows matching specialisationsDoesn't look at calls, but only provides the most conservative specialisation anyway

Put another way: If we allowed multiple specialisations, we could have the following two specialisations, no reboxing happening (no promises made on correctness):

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
  = \ (ds_d112 :: Expr) ->
      case ds_d112 of {
        Lit n_aXf -> n_aXf;
        Plus a_aXg b_aXh ->
          case $weval a_aXg of ww_s1cq { __DEFAULT ->
          case $weval b_aXh of ww1_X1dh { __DEFAULT ->
          GHC.Types.I# (GHC.Prim.+# ww_s1cq ww1_X1dh)
          }
          }
      }

Note that we were able to rewrite both inductive calls in terms of $weval, but still have the vanilla version around if we ever need the boxed result of eval.

Last edited 7 months ago by sgraf (previous) (diff)
Note: See TracTickets for help on using tickets.