[GHC] #14152: Float exit paths out of recursive functions

[GHC]

#14152: Float exit paths out of recursive functions
-------------------------------------+-------------------------------------
        Reporter:  nomeata           |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.1
      Resolution:                    |             Keywords:  JoinPoints
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #14137 #10918     |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by simonpj):

 * keywords:   => JoinPoints


Old description:

> This is a spin off of a discussion from #14137.
>
> == The problem ==
>
> We generally avoid inlining or floating a binding into a recursive
> function, because we do not want to duplicat work/allocations.
>
> But sometimes the binding is only used inside the recursive function on
> the “exit path”. In which case it would be good to inline. Example:
>
> {{{#!hs
>   let x = f x0
>   in let go 10 = h x
>          go i = go (i+1)
>      in go (0::Int) + 100
> }}}
>
> It would be beneficial to inline `x`.
>
> The problem is that it is not very obvious that this occurence of `x` is
> ok for inlining. In particular, it is not syntactically visible.
>
> == Proposed solution ==
>
> If we apply loopification (#14068), this would turn into
>
> {{{#!hs
>   let x = f x0
>   in let go n =
>        joinrec jgo 10 = h x
>                jgo i = call jgo (i+1)
>        in call jgo n
>      in go (0::Int) + 100
> }}}
>
> I’d like to call this ''first joinrec normal form'', defined as “every
> recursive function where all recursive calls are tail-recursive is a
> recursive join point”.
>
> This ticket proposes to transform this even further and ''float out all
> case alternatives that do not mention `jgo` as non-recursive join-
> points'', as so:
>
> {{{#!hs
>   let x = f x0
>   in let go n =
>        join jexit = h x
>        joinrec jgo 10 = call jexit
>                jgo i = call jgo (i+1)
>        in call jgo n
>      in go (0::Int) + 100
> }}}
>
> I’d like to call this ''second `joinrec` normal form'', defined as “in
> first `joinrec` normal form, and all subexpressions of a recursive join
> point `j` that are in tail-call position and do not mention `j` are join
> calls”.
>
> If the floated expression has free variables that are bound inside the
> `joinrec`, they turn into parameters of the newly created joinpoint.
>
> At this point, GHC can tell that `go` is called at most once, and will
> therefore happily inline `x` into the right hand side of `jexit.
>
> == Alternative solutions ==
>
> Ticket #10918 uses Call Arity results to learn that `x` is one-Shot, and
> inline it even in the original code. This works, but the problem is that
> float-out will undo this. See [ticket:10918#comment:5].
>
> == Limitation ===
>
> It only works for recursive functions that are join points, or can be
> turned into join points by loopification (#14068). It does not work
> forexample for
>
> {{{#!hs
> let x = f x0
> let go 0 = h x
>     go n = (go (n-1) + 1
> in go 10
> }}}
>
> although it would be equally desirable to float  `h x` out of `go` so
> that `x` can be inlined.
>
> == Preservation ==
>
> A remaining tricky point is that we need to stop one of these carefully-
> constructed non-recursive join points being inlined into a recursive join
> point, even if it is invoked at just one place. That should not be hard.
> And in a final run of the simplifer (or in CorePrep) we could switch off
> that restriction and let it inline. (Ticket #14137 is about inlining
> ''more'' join points into recursive join points, so it is the antithesis
> to the present ticket.)

New description:

 This is a spin off of a discussion from #14137.

 == The problem ==

 We generally avoid inlining or floating a binding into a recursive
 function, because we do not want to duplicat work/allocations.

 But sometimes the binding is only used inside the recursive function on
 the “exit path”. In which case it would be good to inline. Example:

 {{{#!hs
   let x = f x0
   in let go 10 = h x
          go i = go (i+1)
      in go (0::Int) + 100
 }}}

 It would be beneficial to inline `x`.

 The problem is that it is not very obvious that this occurence of `x` is
 ok for inlining. In particular, it is not syntactically visible.

 == Proposed solution ==

 If we apply loopification (#14068), this would turn into

 {{{#!hs
   let x = f x0
   in let go n =
        joinrec jgo 10 = h x
                jgo i = call jgo (i+1)
        in call jgo n
      in go (0::Int) + 100
 }}}

 I’d like to call this ''first joinrec normal form'', defined as “every
 recursive function where all recursive calls are tail-recursive is a
 recursive join point”.

 This ticket proposes to transform this even further and ''float out all
 case alternatives that do not mention `jgo` as non-recursive join-
 points'', as so:

 {{{#!hs
   let x = f x0
   in let go n =
        join jexit = h x
        joinrec jgo 10 = call jexit
                jgo i = call jgo (i+1)
        in call jgo n
      in go (0::Int) + 100
 }}}

 I’d like to call this ''second `joinrec` normal form'', defined as “in
 first `joinrec` normal form, and all subexpressions of a recursive join
 point `j` that are in tail-call position and do not mention `j` are join
 calls”.

 If the floated expression has free variables that are bound inside the
 `joinrec`, they turn into parameters of the newly created joinpoint.

 At this point, GHC can tell that `go` is called at most once, and will
 therefore happily inline `x` into the right hand side of `jexit.

 == Alternative solutions ==

 Ticket #10918 uses Call Arity results to learn that `x` is one-Shot, and
 inline it even in the original code. This works, but the problem is that
 float-out will undo this. See [ticket:10918#comment:5].

 == Limitation ==

 It only works for recursive functions that are join points, or can be
 turned into join points by loopification (#14068). It does not work
 forexample for

 {{{#!hs
 let x = f x0
 let go 0 = h x
     go n = (go (n-1) + 1
 in go 10
 }}}

 although it would be equally desirable to float  `h x` out of `go` so that
 `x` can be inlined.

 == Preservation ==

 A remaining tricky point is that we need to stop one of these carefully-
 constructed non-recursive join points being inlined into a recursive join
 point, even if it is invoked at just one place. That should not be hard.
 And in a final run of the simplifer (or in CorePrep) we could switch off
 that restriction and let it inline. (Ticket #14137 is about inlining
 ''more'' join points into recursive join points, so it is the antithesis
 to the present ticket.)

--

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