[GHC] #13236: Improve floating for join points

7 Feb 2017

      #13236: Improve floating for join points
-------------------------------------+-------------------------------------
           Reporter:  simonpj        |             Owner:
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.0.1
           Keywords:  JoinPoints     |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 Having looked at the code in `SetLevels`, am very uncomfortable.  My nose
 tells me that there is far too much chuffing about; it all makes my head
 spin.

 '''Question 1'''.  Why do we ever "ruin" a join point? See
 {{{
 Note [When to ruin a join point]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Generally, we protect join points zealously. However, there are two
 situations
 in which it can pay to promote a join point to a function:

 1. If the join point has no value arguments, then floating it outward will
 make
    it a *thunk*, not a function, so we might get increased sharing.
 2. If we float the join point all the way to the top level, it still won't
 be
    allocated, so the cost is much less.

 Refusing to lose a join point in either of these cases can be disastrous
 ---for
 instance, allocation in imaginary/x2n1 *triples* because $w$s^ becomes too
 big
 to inline, which prevents Float In from making a particular binding
 strictly
 demanded.
 }}}
 But I don't agree at all.  If we have
 {{{
 let-join j = e in b
 }}}
 then we can leave `j` in place as a join point.  We can float `e` (via
 `lvlMFE`) if doing so would
 increase sharing.  Indeed this applies uniformly to all join points. For
 example
 {{{
 f x = let g y = let-join j z1 z2 = expensive x
                 in case y of
                    A p q -> j p q
                    B r   -> j r r
                    C     -> True
 }}}
 Here it would make sense to float `(expensive x)` out of the `\y`
 abstrction:
 {{{
 f x = let lvl = expensive x
           g y = let-join j z1 z2 = lvl
                 in case y of
                    A p q -> j p q
                    B r   -> j r r
                    C     -> True
 }}}
 But doing so does not affect the join point `j`.  Nullary join points are
 no different.

 This includes floating to the top level.  Incidentally the RHS of the join
 point then becomes tiny, so the join point will be inlined.

 In short, I think we can just delete all this special code.

 '''Question 2''': `Note [Join points and MFEs]`.  Whe do we ''ever'' float
 out a MFE that has a free join variable?  SLPJ claim: if there is a free
 join variable, do not float it anywhere.

 '''Question 3''': Do we actually need to float join points ''at all''?
 Why?

 I thik the reason is just to make them small
 {{{
 let-join j1 x = let-join j2 y = y+1
                 in ...
 }}}
 Here perhaps if we float `j2` out of `j1` that might make `j1` small
 enough to inline.  But if that is the only motivation (unlike most of
 `FloatOut` which is about saving work) we'd better say so loud and clear.
 And the question is a bit more complicated; e.g. we might want to abstract
 over Ids to achieve this.  e.g.
 {{{
 let-join j1 x = let-join j2 y = x+y
                 in ...
 ===>
 let-join j2' x y = x+y
          j1 x = let-join j2 y = j2' x y
                 in ...
 }}}
 Now we can inline `j2`.  (The example would be more realistic if the `x+y`
 was a big expression.)  It's not just join parameters; we can abstract
 over any free variables:
 {{{
 let-join j1 x = let p = x+y in
                 let-join j2 z = p+z
                 in ....
 }}}
 Here we could abstract `j2` over `p` in order to float it.

 It is not clear how best to do this; but I worry that we are asking
 `FloatOut` to do too much.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13236
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler

GHC

GHC

GHC

GHC

GHC

GHC

GHC

tags

participants (1)