Re: [GHC] #14068: Loopification using join points

23 Mar 2018

      #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):

 I've been playing around with `wip/T14068-inline`, and the behavior I was
 seeing occurs with this simple example:

 {{{
 countDown n = case n of
     0 -> 0
     n -> countDown (n - 1)

 ... countDown 10 {- non-tail call -} ...
 }}}

 countDown satisfies our `RecursiveTailCalled` requirement right out of the
 gate, and is marked as such by OccurAnal.

 With loopification turned off, the first simplification pass will give us:

 {{{
 countDown :: forall t p. (Eq t, Num t, Num p) => t -> p
 [LclIdX,
  Arity=4,
  Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
          WorkFree=True, Expandable=True,
          Guidance=IF_ARGS [30 90 30 0] 550 0}]
 countDown
   = \ (@ t_a2HQ)
       (@ p_a1vP)
       ($dEq_a2OT :: Eq t_a2HQ)
       ($dNum_a2OU :: Num t_a2HQ)
       ($dNum_a2OV :: Num p_a1vP)
       (eta_B1 :: t_a2HQ) ->
       letrec {
         countDown_a1vH [Occ=LoopBreaker] :: t_a2HQ -> p_a1vP
         [LclId, Arity=1]
         countDown_a1vH
           = \ (n_aX3 :: t_a2HQ) ->
               case ==
                      @ t_a2HQ $dEq_a2OT n_aX3 (fromInteger @ t_a2HQ
 $dNum_a2OU 0)
               of {
                 False ->
                   countDown_a1vH
                     (- @ t_a2HQ $dNum_a2OU n_aX3 (fromInteger @ t_a2HQ
 $dNum_a2OU 1));
                 True -> fromInteger @ p_a1vP $dNum_a2OV 0
               }; } in
       countDown_a1vH eta_B1
 }}}

 Thanks to the eta-expansion, `countDown_a1vH` can now be turned into a
 full join point. Thus, we didn't gain anything by performing loopification
 so early, though we also lose nothing since we end up with the same code
 after some clean up... just a small observation.

 A more troubling behavior I've spotted happens in `queens`, where we end
 up with some good looking code after we loopify and then inline the once-
 called `safe`, but all of that progress seems to be undone by FloatOut.
 Simplification will then redo all of that work. I wonder if it would be
 more efficient to use loopification after outward let-floating?

 Also: I think I've narrowed down where the slowdown comes from in
 `queens`. I'll post the details in a later comment since I need to be up
 early tomorrow.

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