Re: [GHC] #14068: Turn tail-recursive functions into recursive jointpoints

1 Aug 2017

      #14068: Turn tail-recursive functions into recursive jointpoints
-------------------------------------+-------------------------------------
        Reporter:  nomeata           |                Owner:  mpickering
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #13966 #14067     |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by nomeata):

 Just noting down some thoughts.

 How does this work for mutually recursive bindings?
 {{{
 let f x y = case y of
               A -> f x' y'
               B -> g (x', y')
               C -> e3
     g p = case p of (x, y) -> f x' y'
 in f 1 2 + g 3 4
 }}}
 Here `f` and `g` look like they might be join points. One way of doing
 that would be
 {{{
 let f x y = joinrec $j1 x y = case y of
                                 A -> $j1 x' y'
                                 B -> $j2  (x', y')
                                 C -> e3
                     $j2 p = case p of (x, y) -> f x' y'
             in $j1 x y
     g p   = joinrec $j1 x y = case y of
                                 A -> $j1 x' y'
                                 B -> $j2  (x', y')
                                 C -> e3
                     $j2 p = case p of (x, y) -> f x' y'
             in $j2 p
 in f 1 2 + g 3 4
 }}}
 but such code duplication is clearly not desired.

 The next best thing I can think of is some encoding
 {{{
 let f_g arg = joinrec $j1 x y = case y of
                                   A -> $j1 x' y'
                                   B -> $j2  (x', y')
                                   C -> e3
                       $j2 p = case p of (x, y) -> f x' y'
               in case arg of Left (x,y) -> $j1 x y
                              Right p    -> $j2 p
     f x y = f_h (Left (x,y))
     g p   = f_g (Right p)
 in f 1 2 + g 3 4
 }}}
 (maybe using unboxed sums for the parameter encoding).

 This would have the desired effect, but I guess it goes too far. So I
 conclude this ticket should focus on the singly recursive case.

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