[GHC] #14137: Do more inlining into non-recursive join points

[GHC]

#14137: Do more inlining into non-recursive join points
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  nomeata
            Type:  bug               |               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:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by nomeata):

 Also note that floating out the exit code paths from recursive join points
 greatly improves the effectivity of the demand analyser, possibly to the
 point of making Call Arity obsolete (at least in some common cases).
 Consider this code:

 {{{
 let t = f a -- a thunk
 in let go 0 y = t y + 5
        go n y = go (n-1) (y*y)
    in case go 100 2 of …
 }}}

 The cardinality analysis is not able to eta-expand `t` because it has to
 assume it is used multiple times. Call Arity, with the rather complicate
 co-call graph analysis finds that `t` is called at most once and allows
 for its eta-expansion.

 But let’s see what happens if we apply some of the ideas from this tickets
 and from #14068. First we apply #14068:
 {{{
 let t = f a -- a thunk
 in let go n y = joinrec j 0 y = t y + 5
                         j n y = call j (n-1) (y*y)
                 in call j n y
    in case go 100 2 of …
 }}}
 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”.

 Next we apply the idea above of floating out all expressions not
 mentioning the join point
 {{{
 let t = f a -- a thunk
 in let go n y = join jexit y = t y + 5
                 joinrec j 0 y = call jexit y
                         j n y = call j (n-1) (y*y)
                 in call j n y
    in case go 100 2 of …
 }}}
 I’d like to call this ''second joinrec normal form'', defined as “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 invocations a
 join point”.

 This form minimizes the amount of code that is inside the `joinrec`, which
 is good, as many parts of the compiler (simplifier, demand analyzer) have
 to make conservative assumptions with recursion.

 Now the normal demand analyser can infer that the non-recursive `go` is
 called at most once, hence the join-point `jexit` is called at most once
 (by virtue of being a join-point, it can do so without looking at its use-
 site, which are inside a recursive group), and hence `t` is used at most
 once. Success!

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