Float exit paths out of recursive functions
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:
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
let x = f x0
in let go n =
joinrec jgo 10 = h x
jgo i = call jgo (i+1)
in jump 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:
let x = f x0
in let go n =
join jexit = h x
joinrec jgo 10 = call jexit
jgo i = call jgo (i+1)
in jump 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.)