[GHC] #15560: Full laziness destroys opportunities for join points

[GHC]

#15560: Full laziness destroys opportunities for join points
-------------------------------------+-------------------------------------
        Reporter:  AndreasK          |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.6.1
       Component:  Compiler          |              Version:  8.4.3
  (CodeGen)                          |
      Resolution:                    |             Keywords:  JoinPoints
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #14287 #13286     |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 > I assume you are talking about removing the stack check here with the
 optimisation?

 I wasn't very clear. My idea is to ''ignore'' whether a top-level binding
 started life as a join point, and instead optimise ''all'' top-level
 bindings the same way.

 There are three things in play:

 1. '''Eliminating the closure and info-table for some top-level
 functions'''.  Consider a top-level binding
 {{{
 f = \xy. e
 }}}
   When can we do without a closure and info table for `f`?  Answer: if
       * All calls to `f` are known, saturated calls (no partial
 applications).
       * `f` is not exported

     NB 1: it's fine if the call to `f` is in a lazy context, e.g.
 {{{
 g y = let t = f (y+1) in Just t
 }}}

     NB 2: for a ''nested'', let-bound function, we do need a function
 closure, even if all the calls are known, saturated calls.  Why?  Because
 we need a heap-allocated container for its free variables.  So we need the
 info table.  But if all the calls are known, saturated, we do ''not'' need
 any slow-entry code, so the code pointer for the info table could be
 "crash" (will never happen).

 2. '''Eliminating stack checks'''.  Join points already don't have a stack
 check; regular let-bindings do (of course).  Idea: extend to the stack-
 check elimination to more functions; that is, absorb any stack use for
 that function into its call site.  When can we do this?  Answer:
       * All calls to `f` are known, saturated calls (no partial
 applications).
       * `f` is not exported
       * `f` is not recursive; or `f` is top-level and tail-calls itself
 (or is part of a top-level tail-recursive nest).

     NB 1: this works for ''non-top-level'' functions too. Example:
 {{{
 g x = let f y = blah
           t = f 4 + f 5
       in Just t
 }}}
     Currently the thunk for `t` will do a stack check, and `f` will do its
 own stack check too.  We could absorb `f`'s check into `t`.

     NB 2: why not recursive functions?  Consider
 {{{
    let f x = if x==0 then 0 else 1 + f (x-1)
 }}}
     Clearly the stack grows, so we can't eliminate the stack check.  But
 if `f` is a join point there is no problem, and similarly at top level
 (i.e. not a join point) if it tail-calls itself or some other top-level
 function with the same property.... let's call these "top-level join
 points".


 3.  '''Eliminating heap checks'''.   Idea: absorb the heap check for a
 function into its caller.  When can we do this?
     * All calls to `f` are known, saturated calls (no partial
 applications).
     * `f` is not exported
     * `f` is not recursive. Reason: if it's recursive, one of its call
 sites is in its own RHS, so we can't statically bound how much heap it
 uses.

     NB 1: absorbing the heap check is ''not'' currently done even for join
 points. (Reason: it only works for ''non-recursive'' functions.)


 NB: None of these optimisations rely on `f` being a join point.

 All of this is STG-level/code-gen level optimisation, not Core.

 These would be interesting ideas to try out. If you feel motivated, I
 could advise.

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