[GHC] #9374: Investigate Static Argument Transformation

[GHC]

#9374: Investigate Static Argument Transformation
-------------------------------------+-------------------------------------
              Reporter:  jstolarek   |            Owner:
                  Type:  task        |           Status:  new
              Priority:  lowest      |        Milestone:
             Component:  Compiler    |          Version:  7.9
            Resolution:              |         Keywords:
      Operating System:              |     Architecture:  Unknown/Multiple
  Unknown/Multiple                   |       Difficulty:  Unknown
       Type of failure:              |       Blocked By:
  None/Unknown                       |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 I found an email summarising a conversation Max and I had about SAT, back
 in 2009.  Here it is verbatim, FWIW:

 SAT can lose; eg
  * few static args (can spot)
  * few loop iterations (hard to spot)
  * SAT changes SpecConstr opportunity into CaseLib opportunity; and the
 latter is not good at the moment
  * SATing exposes new loop-invariant sub-expressions e.g.
 {{{
 f x y = if y==0 then 0 else g x + f x (y-1)
 }}}
  That is potentially good.  But float-out can be bad for cold branches,
 and this can be bad.

 Hence want to focus on SAT in situations where it’s most likely to
 benefit.

 SAT has benefits of two kinds:
  1. More efficient loops, when there are a lot of static args.  This is a
 pretty small effect.
  2. Specialisation from (a) SAT makes recursive function non-rec; (b) then
 inlining can happen.  This is the big gain.

 Evidence for (2): most benefits happen even if you SAT *only* if at least
 one SAT-d argument has function type.

 Four exceptions, where SATing non-function-typed args was worthwhile:

  * Atom.  f x y = (x,y) : f x y. Satting this makes an loopy list; result
 97% reduction  in runtime.

  * SAT may make a function small enough to fit inside inlining threshold.

  * Puzzle.  Recursive SAT-able function called just once outside.  After
 SAT, it can be inlined, and hence specialised for the (single) call site.

 One program got worse when SATing non-function-typed args

  * Listcompr.  The cold-branch problem happens.


 Thoughts:
  * No point in SAT if function is big.  Maybe SAT only if EITHER small OR
 single call site outside.
  * Max’s idea:
    * Lambda lift everything
    * !SpecConstr
    * Lambda-drop
    * Export unfoldings
    * Selectively lambda-lift (lambda-lift functions of only one argument)
 [SLPJ: this is Nick Frisby's work]
    * Codegen

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