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

24 Aug 2017

      #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
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:  #14137 #10918
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 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
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler

tags

participants (1)