#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