[GHC] #10918: Float once-used let binding into a recursive function

[GHC]

#10918: Float once-used let binding into a recursive function
-------------------------------------+-------------------------------------
        Reporter:  nomeata           |                Owner:
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.10.2
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
-------------------------------------+-------------------------------------

Comment (by nomeata):

 One effect, which might or might not be the reason for the paraffin
 regression (but certainly obscures the view) is that an inlined expression
 seems to float out further than a let-bound expression. More explicitly,
 consider this code:

 {{{#!hs
 foo :: [[Bool]] -> [Bool]
 --foo input = [ not y | (x:xs) <- input, y <- (x:xs) ]
 foo [] = []
 foo (y:ys) =
     case y of
         [] -> foo ys
         (x:xs) ->
             let z = foo ys in
             let go [] = z
                 go (y':ys') = not y' : go ys'
             in  not x : go xs
 }}}

 With my change, this will be turned into

 {{{#!hs
 foo :: [[Bool]] -> [Bool]
 --foo input = [ not y | (x:xs) <- input, y <- (x:xs) ]
 foo [] = []
 foo (y:ys) =
     case y of
         [] -> foo ys
         (x:xs) ->
             let go [] = foo ys
                 go (y':ys') = not y' : go ys'
             in  not x : go xs
 }}}

 If the compiler would stop here, I’d be happy.

 But instead, something interesting happens. In the pristine case, the
 binding to `z` is not affected by the level set:
 {{{
 (let {
    <z,<1,3>>
    <z,<1,3>> = T10918a.foo ys } in
 }}}
 whereas the plain `foo ys` expression got wrapped in a binding and is
 assigned a level further out:
 {{{
 [] ->
   let {
     <lvl,F<1,1>>
     <lvl,F<1,1>> = T10918a.foo ys } in
   lvl;
 }}}

 The `F<1,1>` is – as expected – the binding site of `ys`.

 But now the first invocation of `foo ys` is in scope of the `lvl`, CSE
 happens, the variable is no longer used at most once, it cannot be inlined
 back and we end up with
 {{{#!hs
 foo :: [[Bool]] -> [Bool]
 --foo input = [ not y | (x:xs) <- input, y <- (x:xs) ]
 foo [] = []
 foo (y:ys) =
     let lvl = foo ys
     case y of
         [] -> lvl
         (x:xs) ->
             let go [] = lvl
                 go (y':ys') = not y' : go ys'
             in  not x : go xs
 }}}
 which is not what I want to see.

 So the issue here seems to be that under some circumstances, an `e` in
 `C[e]` can be floated out further than `let z = e in C[z]`.

 (All this does not look too server in this case, but it happens a few
 times in paraffin, so I hope that this is actually related to the
 allocation increase.)

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