[GHC] #3116: missed opportunity for call-pattern specialisation

[GHC]

#3116: missed opportunity for call-pattern specialisation
-----------------------------------------+----------------------------------
    Reporter:  duncan                    |        Owner:                  
        Type:  run-time performance bug  |       Status:  new             
    Priority:  normal                    |    Milestone:                  
   Component:  Compiler                  |      Version:  6.10.1          
    Severity:  normal                    |   Resolution:                  
    Keywords:                            |   Difficulty:  Unknown         
    Testcase:                            |           Os:  Unknown/Multiple
Architecture:  Unknown/Multiple          |  
-----------------------------------------+----------------------------------
Comment (by duncan):

 Replying to [comment:3 simonpj]:
 > Can't do much better than that.  Expect a patch shortly.

 Woo hoo! That is indeed perfect. Thanks very much! I will update that
 example in my thesis accordingly! :-)

 > I don't understand your recent comment above, though.  The RULES
 generated from the specialisations are indeed applied in the original
 function!

 Yes, of course. Sorry, I was not very clear.

 > Can you give a standalone example showing what happens, and what you
 want to happen instead?

 Ok, so with your fix we're getting essentially:

 {{{
 go_chunk n p fpc o l bs'
   = case l of
       1  -> go        (n+1) bs'
       _  -> go_chunk  (n+1) p fpc (o+1) (l-1) bs'

 go !n bs
   = case bs of
       Empty                -> n
       Chunk p fpc o l bs'  ->
         case l of
           1  -> go        (n+1) bs'
           _  -> go_chunk  (n+1) p fpc (o+1) (l-1) bs'
 }}}

 The body of `go` contains a full unfolded instance of `go_chunk`
 (obviously, because that's the way `go` was defined and `go_chunk` was
 derived from a portion of the body of `go`).

 But what if it turned out that calling `go_chunk` was better than having
 `go_chunk` unfolded into the body of `go`?

 That is, it might be that this turns out to be the faster code:

 {{{
 go_chunk n p fpc o l bs'
   = case l of
       1  -> go        (n+1) bs'
       _  -> go_chunk  (n+1) p fpc (o+1) (l-1) bs'

 go n bs
   = case bs of
       Empty                -> n
       Chunk p fpc o l bs'  -> go_chunk b p fpc o l bs'
 }}}

 Currently, when we do the specialisation we leave the original defintion
 unmodified. Of course subsequently we apply the rules to it etc, but
 initially it's just kept in it's original form.

 The suggestion is that perhaps it is profitable to substitute calls to the
 specialised versions of the function into the original definition. We can
 always recover the original definition if the inliner decides it's the
 right thing to do.

 So, in this example, we start with the definition:

 {{{
 go !n bs = case bs of
   Empty                -> n
   Chunk p fpc o l bs'  ->
     case l of
       1  -> go (n+1) bs'
       _  -> go (n+1) (Chunk p fpc (o+1) (l-1) bs')
 }}}

 Then we construct the specialised versions:

 {{{
 go_empty n = n

 go_chunk n p fpc o l bs'
   = case l of
       1  -> go (n+1) bs'
       _  -> go (n+1) (Chunk p fpc (o+1) (l-1) bs')
 }}}

 Of course we also make the rules. In the current system we then just move
 on to applying the specialisation rules in the body of these functions and
 the original.

 But suppose instead that we first redefine the original `go` in terms of
 it's specialisations:

 {{{
 go !n bs = case bs of
   Empty                -> go_empty n
   Chunk p fpc o l bs'  -> go_chunk n p fpc o l bs'
 }}}

 I do not mean doing this by rewrite rules, I mean just doing it directly
 as part of the procedure of generating specialised versions. Pick a
 pattern, lift the correspoding portion of the body out to become the
 specialised function and replace it with a call to the new specialised
 function. (That's an over-simplification of course but hopefully
 illustrates the idea).

 Then we move on as normal to apply rules and do ordinary simplification.
 This now gives the inliner the choice. It can choose to inline `go_chunk`
 in the body of `go` or it can choose to keep it as a call. If `go_chunk`
 is quite large then it might be better to keep it as a call. In the
 existing scheme it has no choice because the original function definition
 is never changed, it always contains the full body of each of its
 specialisations.

 Does that make any sense?

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