CPR Analysis is too conservative for certain inductive cases

changed milestone to %⊥

changed weight to 5

added CPR/boxity analysis Ttask Trac import labels

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!)

To expand on the "Return pattern specialisation" thing:

SpecConstr	CPR+WW
Multiple specialisations	One 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 specialisations	Doesn'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.

added Pnormal label

Allowing more specializations might also save code size in cases where the wrapper does not cancel out with the surrounding code.

This happens for example in the power benchmark of nofib.

There we call what I assume are the specialized Num methods for Ratio Integer (GHC.Real.$w$s$c[/+-*]), but out of 10 calls 9 immediately box the result.

Now the wrappers are rather small, but still it's code duplication that would go away and might be a interesting case to look at.

mentioned in merge request !2929 (closed)

This comment in !2929 (closed) gives another example of a similar kind to the Description of this ticket; see also #4267 (closed)

mentioned in issue #4267 (closed)

marked this issue as related to #4267 (closed)

removed the relation with #4267 (closed)

marked this issue as related to #4267 (closed)

mentioned in commit 8dd78b90

mentioned in commit fb01a5d0

mentioned in commit 54250f2d

changed title from Make CPR Analysis more aggressive for inductive cases to CPR Analysis is too conservative for certain inductive cases

mentioned in merge request !1866 (closed)

changed the description

marked this issue as related to #18174 (closed)

changed the description

mentioned in issue #18615 (closed)

It's interesting that the recent gripes with CPR WW and sharing in #13331 (closed), #19276 are of no issue to return-pattern specialisation.

mentioned in issue #19351

mentioned in issue #19888 (closed)

marked this issue as related to #19888 (closed)

removed the relation with #19888 (closed)

marked this issue as related to #19888 (closed)

In #19888 (closed) I reported a missed optimization opportunity that could probably be resolved by return-pattern specialisation. I think it is pretty common that users use traverse with f (t ()) as return type, where the t () is immediately discarded, e.g. as an non-bind statement in a do block, when combined with void, or in functions like execState. That means that building up the t () is redundant and that can cause a significant performance penalty.

The example that was reported is:

import Control.Monad.State

sumState:: [Int] -> Int
sumState xs = execState (traverse f xs) 0
    where f n = modify (n+)

main :: IO ()
main = do
  print $ sumState [1..1000000000]

In this extract of the resulting core you can see that it unnecessarily builds up a list of unit tuples during the traversal:

letrec {
  $s$wgo
    = \ sc sc1 ->
        let {
          ds2
            = case ==# sc1 y of {
                __DEFAULT ->
                  case $s$wgo (+# sc1 sc) (+# sc1 1#) of { (# ww1, ww2 #) ->
                  (ww1, ww2) `cast` <Co:6>
                  };
                1# -> ([], I# (+# sc1 sc)) `cast` <Co:9>
              } } in
        (# : () (case ds2 `cast` <Co:5> of { (x1, s'') -> x1 }),
           case ds2 `cast` <Co:5> of { (x1, s'') -> s'' } #); } in
case $s$wgo 0# 1# of { (# ww1, ww2 #) ->
case ww2 of { I# ww4 ->
case $wshowSignedInt 0# ww4 [] of { (# ww6, ww7 #) -> : ww6 ww7 }

Which runs in about 18 seconds on my machine. If I replace traverse by traverse_ then that drops to about 900 ms, so that is a performance improvement of about 20x.

so that is a performance improvement of about 20x.

That's pretty compelling :-).

Some thoughts about looking at the example in the ticket above:

If we’d unroll the loop once, we’d be able to distinguish between “returning Lit directly to the caller”, were CPR might be bad, and “returning Lit in a recursive call”, where we can see all the uses, and thus know that it’s save to CPR. Doesn’t do GHC some form of unrolling-recursive-functions?
Sebastian, if you want a dual for SpecConstr that looks at how the result is used, and takes actual callers into account, isn’t that roughly what Demand Analysis does? Or where would the main difference be?

Doesn’t do GHC some form of unrolling-recursive-functions?

You might be thinking of LiberateCase (which is the only such pass I'm aware of). It would recursive calls to eval with letrec eval = ... in eval, thus duplicating the recursive body at each call site and making the original recursive function non-recursive so that it can inline. I think we'd get something like

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

after CSEing the two different eval' bindings. If we did demand analysis on this definition, demand analysis indeed would see (I think) that whenever eval' is called, its result is unboxed, too. That is pretty much the situation that "return-pattern specialisation" as above would exploit, yes. We could basically do Nested CPR even though the Lit's Int doesn't have the CPR property. I did something very similar in !1866 (closed), but termination info only.

Great insight! Although I'm a bit doubtful that LiberateCase will even trigger on eval, because there's no case on a free variable. Also the CSE required to get above form is non-trivial.

Edit: I think the whole LiberateCase/loop pealing idea is reminiscent of partial redundancy elimination. LiberateCase exploits that unrolling the loop once makes a case on a free variable fully redundant. Here, we try to make the unboxing demand fully redundant.

Thanks for pointing me to LiberateCase. Heh, I like that this pass has a “To think about (Apr 94)” note therein :-)

I could imagine a pass that does this loop peeling without duplicating the body, to avoid relying on CSE. We have a bunch of analyses that work best if all use-sites are known (Call Arity, Demand analysis). Such a transformation would make sure that all recursive functions have all their call sites known. So maybe there are more corners that could benefit from such a transformation. But it’s a lot of code duplication, of course.

mentioned in issue #2289

marked this issue as related to #2289

In https://github.com/haskell/vector/issues/156, where I'm trying to fuse a filter and a map over streams without Skip constructor, I'm encountering core like this:

letrec {
  $wstep'_s3Uf :: Int# -> Id (Step Int Double)
  $wstep'_s3Uf
    = \ (ww2_s3Ud :: Int#) ->
        case >=# ww2_s3Ud ipv1_s3Po of {
          __DEFAULT -> case indexDoubleArray# ipv2_s3Pp (+# ipv_s3Pn ww2_s3Ud) of wild2_i3d4 { __DEFAULT ->
            case >## wild2_i3d4 10.0## of {
              __DEFAULT -> $wstep'_s3Uf (+# ww2_s3Ud 1#);
              1# ->
                (Yield (D# wild2_i3d4) (I# (+# ww2_s3Ud 1#))) `cast` <Co:5>
            }};
          1# -> Done `cast` <Co:5>
        }; } in
joinrec {
  $s$wfoldlM'_loop_s3WN :: State# RealWorld -> Int# -> Int# -> Vector Double
  $s$wfoldlM'_loop_s3WN (sc_s3WM :: State# RealWorld) (sc1_s3WK :: Int#) (sc2_s3WJ :: Int#)
    = case ($wstep'_s3Uf sc1_s3WK) `cast` <Co:4> of { -- <<< $wstep' can't be a join point
        Yield x_a3P4 s'_a3P5 ->
          case x_a3P4 of { D# x1_a2wq ->
          case writeDoubleArray# ipv4_i3En sc2_s3WJ (+## x1_a2wq x1_a2wq) (sc_s3WM `cast` <Co:5>)
          of s'#_i3S3 { __DEFAULT ->
          case s'_a3P5 of { I# ww3_X4 ->
          jump $s$wfoldlM'_loop_s3WN (s'#_i3S3 `cast` <Co:4>) ww3_X4 (+# sc2_s3WJ 1#)
          } } };
        Done ->
          case unsafeFreezeByteArray# ipv4_i3En (sc_s3WM `cast` <Co:5>) of
          { (# ipv5_i3ci, ipv6_i3cj #) ->
          (Vector 0# sc2_s3WJ ipv6_i3cj) `cast` <Co:5>
          }
      }; } in
jump $s$wfoldlM'_loop_s3WN (ipv3_i3Em `cast` <Co:4>) 0# 0#

Is this also a case where return pattern specialization would help? Or does the sum type mess things up?

mentioned in issue #14259

I think your code can be handled by "MultiSum" CPR; see my comment over in #14259 (comment 454824).

Fixing your code doesn't need return-pattern specialisation, I think, because $wstep's definition is already in a "good form" (namely has a deep CPR property) where the call sites don't actually matter. FWIW, the call site of $wstep never keeps the result in a box either, so we could unbox $wstep deeply even if it returned a box it didn't construct itself, like the Int from the Lit constructor in the OP, all without duplicating code (unlike in the OP).

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

CPR Analysis is too conservative for certain inductive cases

Child items 0

Activity

CPR Analysis is too conservative for certain inductive cases

Blocks

Relates to

Activity