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.)