[GHC] #14068: Loopification using join points

[GHC]

#14068: Loopification using join points
-------------------------------------+-------------------------------------
        Reporter:  nomeata           |                Owner:  nomeata
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:  JoinPoints
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #13966 #14067     |  Differential Rev(s):  Phab:D3811
  #14827                             |
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by kavon):

 Here are the details on FloatOut: Using `wip/T14068-inline`, I compiled
 `queens` with `-O2 -ddump-occur-anal -ddump-simpl-iterations -ddump-call-
 arity -dverbose-core2core` to watch every Core transformation, and noticed
 that after Specialize, we have nicely inlined the "safe" loop
 (`safe_s5vS`) into the folding function:

 {{{
 ...  inside gen ...
 GHC.Base.foldr
   @ [Int]
   @ a_d3jr
   (\ (ds_d3jv :: [Int]) (ds_d3ju [OS=OneShot] :: a_d3jr) ->
     GHC.Base.foldr
       @ Int
       @ a_d3jr
       (\ (ds_d3jx :: Int)
          (ds_d3jw [OS=OneShot] :: a_d3jr) ->
          case joinrec {
                 safe_s5vS [Occ=LoopBreaker]
                   :: Int -> Int -> [Int] -> Bool
                 [LclId[JoinId(3)], Arity=3]
                 safe_s5vS (x_X14P :: Int)
                           (d_X14R :: Int)
                           (ds_X3kg :: [Int])
                   = ... BODY OF SAFE ... } in
               jump safe_s5vS
                 ds_d3jx (GHC.Types.I# 1#) ds_d3jv
          of {
            False -> ds_d3jw;
            True ->
              c_d3js
                (GHC.Types.: @ Int ds_d3jx ds_d3jv) ds_d3jw
          })
 }}}

 Right after Specialize, SetLevels tells FloatOut to move that join point
 to the top level:

 {{{
   GHC.Base.foldr
    @ [GHC.Types.Int]
    @ a_d3jr
    (\ <ds_d3jv,<2,0>> <ds_d3ju,<2,0>> ->
       GHC.Base.foldr
         @ GHC.Types.Int
         @ a_d3jr
         (\ <ds_d3jx,<3,0>> <ds_d3jw,<3,0>> ->
            case letrec {
                   <safe_s5w0,F<0,0>>
                   <safe_s5w0,F<0,0>>
                     = \ <x_X14P,<1,0>>
                         <d_X14R,<1,0>>
                         <ds_X3kg,<1,0>> -> ...
 }}}

 So we end up with an ordinary top-level Rec:

 {{{
   Rec {
 safe_s5w0 [Occ=LoopBreaker] :: Int -> Int -> [Int] -> Bool
 [LclId, Arity=3]
 safe_s5w0
   = \ (x_X14P :: Int) (d_X14R :: Int) (ds_X3kg :: [Int]) -> ...

 ...

 GHC.Base.foldr
   @ Int
   @ a_d3jr
   (\ (ds_d3jx :: Int)
      (ds_d3jw [OS=OneShot] :: a_d3jr) ->
      case safe_s5w0 ds_d3jx lvl_s5w1 ds_d3jv of {
        False -> ds_d3jw;
        True ->
          c_d3js
            (GHC.Types.: @ Int ds_d3jx ds_d3jv) ds_d3jw
      })
      ...
 }}}

 We end up recovering the good code that existed before FloatOut after two
 further iterations of Simplification.

 FloatOut does try to float join points (see the Note [Join points] in its
 file). Perhaps there's something wrong with the "join ceiling" (Note [Join
 ceiling]) implementation in SetLevels?

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