Re: [GHC] #14287: Early inlining causes potential join points to be missed

29 Sep 2017

      #14287: Early inlining causes potential join points to be missed
-------------------------------------+-------------------------------------
        Reporter:  jheek             |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.1
      Resolution:                    |             Keywords:
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 simonpj):

 A major goal in GHC is to avoid sensitivity to ordering of
 transformations.  Otherwise things
 become too finely balanced.

 Here are three programs
 {{{
 -- Recursive function
 -- go is not a join point
 f1 x = letrec go s = case s of
                         Done -> Done
                         Yield x s' | pred x    -> Yield x s'
                                    | otherwise -> go s'
        in case go s2 of ...

 -- Same but float inwards
 -- Now go becomes a join point
 f2 x = case letrec go s = case s of
                         Done -> Done
                         Yield x s' | pred x    -> Yield x s'
                                    | otherwise -> go s'
              in go s2 of ...

 -- Same but float outwards
 -- Now go becomes top-level
 go pred s = case s of
                Done -> Done
                Yield x s' | pred x    -> Yield x s'
                     | otherwise -> go s'
 f3 x = case go pred s2 of ...
 }}}
 Points to note:

 * Float-in can create join points; see the transition from `f1` to `f2`

 * Even though `go` is a join point in `f2`, we need a run of the
 Simplifier to mark it as such.  Once it is marked as a join point, it'll
 stay that way.

 * Float-out is currently pretty aggressive about floating things to top
 level, and so will tend to generate `f3`.  By itself that is not too bad.
 But now the `case` in `f3` can't fuse with the loop.

 * Don't forget that the user might write the program in the `f3` form in
 the first place.   Ideally we want all forms to optimise the same way.

 I think that the Right Solution to these fragilities is the loopification
 plan in #14068.  Then, even in the top-level form we'd get
 {{{
 go pred s = letrec go' s = case s of
                              Done -> Done
                              Yield x s' | pred x    -> Yield x s'
                                         | otherwise -> go' s'
             in go' s
 f3 x = case go pred s2 of ...
 }}}
 Now (a) `go'` is a join point, and (b) `go` is non-recursive and will
 inline.

-- 
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14287#comment:6
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler