[GHC] #13331: Worker/wrapper can lead to sharing failure

[GHC]

#13331: Worker/wrapper can lead to sharing failure
-------------------------------------+-------------------------------------
        Reporter:  dfeuer            |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.4.1
       Component:  Compiler          |              Version:  8.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 I suspect the solution will be to expand the "box-demand analysis"
 described in the demand analysis paper ever so slightly. Instead of
 choosing between just passing the box/tuple and passing (some of) its
 contents, I think we want to add a third option: pass the box ''and''
 (some of) its contents. This is a good option to have when we only need
 the box sometimes, and indeed is even important in cases where we
 ''always'' (eventually) need the box:

 {{{#!hs
 f :: Int -> [Int] -> [Int]
 f !n [] = [n]
 f n (x : xs)
   | x > 1000 = n : f x xs
   | otherwise = x : f n xs
 }}}

 This simplifies to

 {{{
 Rec {
 -- RHS size: {terms: 41, types: 48, coercions: 0, joins: 0/0}
 $wf :: Int# -> [Int] -> (# Int, [Int] #)
 $wf
   = \ (ww_s2b5 :: Int#) (w_s2b2 :: [Int]) ->
       case w_s2b2 of {
         [] -> (# I# ww_s2b5, [] #);
         : ipv_s29V ipv1_s29W ->
           case ipv_s29V of wild1_a2a8 { I# x_a2aa ->
           case tagToEnum# (># x_a2aa 1000#) of {
             False ->
               (# wild1_a2a8,
                  case $wf ww_s2b5 ipv1_s29W of { (# ww2_s2bb, ww3_s2bc #)
 ->
                  : ww2_s2bb ww3_s2bc
                  } #);
             True ->
               (# I# ww_s2b5,
                  case $wf x_a2aa ipv1_s29W of { (# ww2_s2bb, ww3_s2bc #)
 ->
                  : ww2_s2bb ww3_s2bc
                  } #)
           }
           }
       }
 end Rec }

 -- RHS size: {terms: 13, types: 15, coercions: 0, joins: 0/0}
 f :: Int -> [Int] -> [Int]
 f = \ (w_s2b1 :: Int) (w1_s2b2 :: [Int]) ->
       case w_s2b1 of { I# ww1_s2b5 ->
       case $wf ww1_s2b5 w1_s2b2 of { (# ww3_s2bb, ww4_s2bc #) ->
       : ww3_s2bb ww4_s2bc
       }
       }
 }}}

 Whoops! Even this keeps losing boxes it ends up needing again. Indeed,
 this example demonstrates that we can lose a bunch of boxes when we will
 ''always'' end up needing to reconstruct them. A better transformation
 would give `$wf` a type like `Int# -> Int -> [Int] -> (# Int, [Int] #)`.

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