#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